Merge branch 'perf-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git...
[muen/linux.git] / kernel / locking / lockdep.c
index bc35a54ae3d43e8cdf28f28c54db0e550248a9ec..21cb81fe63591b47ec61b6854d2050d0a8eb7153 100644 (file)
 #include <linux/hash.h>
 #include <linux/ftrace.h>
 #include <linux/stringify.h>
+#include <linux/bitmap.h>
 #include <linux/bitops.h>
 #include <linux/gfp.h>
 #include <linux/random.h>
 #include <linux/jhash.h>
 #include <linux/nmi.h>
+#include <linux/rcupdate.h>
 #include <linux/kprobes.h>
 
 #include <asm/sections.h>
@@ -82,6 +84,7 @@ module_param(lock_stat, int, 0644);
  * code to recurse back into the lockdep code...
  */
 static arch_spinlock_t lockdep_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
+static struct task_struct *lockdep_selftest_task_struct;
 
 static int graph_lock(void)
 {
@@ -131,13 +134,17 @@ static inline int debug_locks_off_graph_unlock(void)
 
 unsigned long nr_list_entries;
 static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
+static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
 
 /*
  * All data structures here are protected by the global debug_lock.
  *
- * Mutex key structs only get allocated, once during bootup, and never
- * get freed - this significantly simplifies the debugging code.
+ * nr_lock_classes is the number of elements of lock_classes[] that is
+ * in use.
  */
+#define KEYHASH_BITS           (MAX_LOCKDEP_KEYS_BITS - 1)
+#define KEYHASH_SIZE           (1UL << KEYHASH_BITS)
+static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
 unsigned long nr_lock_classes;
 #ifndef CONFIG_DEBUG_LOCKDEP
 static
@@ -278,11 +285,42 @@ static inline void lock_release_holdtime(struct held_lock *hlock)
 #endif
 
 /*
- * We keep a global list of all lock classes. The list only grows,
- * never shrinks. The list is only accessed with the lockdep
- * spinlock lock held.
+ * We keep a global list of all lock classes. The list is only accessed with
+ * the lockdep spinlock lock held. free_lock_classes is a list with free
+ * elements. These elements are linked together by the lock_entry member in
+ * struct lock_class.
  */
 LIST_HEAD(all_lock_classes);
+static LIST_HEAD(free_lock_classes);
+
+/**
+ * struct pending_free - information about data structures about to be freed
+ * @zapped: Head of a list with struct lock_class elements.
+ * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
+ *     are about to be freed.
+ */
+struct pending_free {
+       struct list_head zapped;
+       DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
+};
+
+/**
+ * struct delayed_free - data structures used for delayed freeing
+ *
+ * A data structure for delayed freeing of data structures that may be
+ * accessed by RCU readers at the time these were freed.
+ *
+ * @rcu_head:  Used to schedule an RCU callback for freeing data structures.
+ * @index:     Index of @pf to which freed data structures are added.
+ * @scheduled: Whether or not an RCU callback has been scheduled.
+ * @pf:        Array with information about data structures about to be freed.
+ */
+static struct delayed_free {
+       struct rcu_head         rcu_head;
+       int                     index;
+       int                     scheduled;
+       struct pending_free     pf[2];
+} delayed_free;
 
 /*
  * The lockdep classes are in a hash-table as well, for fast lookup:
@@ -332,6 +370,11 @@ void lockdep_on(void)
 }
 EXPORT_SYMBOL(lockdep_on);
 
+void lockdep_set_selftest_task(struct task_struct *task)
+{
+       lockdep_selftest_task_struct = task;
+}
+
 /*
  * Debugging switches:
  */
@@ -600,7 +643,7 @@ static int very_verbose(struct lock_class *class)
  * Is this the address of a static object:
  */
 #ifdef __KERNEL__
-static int static_obj(void *obj)
+static int static_obj(const void *obj)
 {
        unsigned long start = (unsigned long) &_stext,
                      end   = (unsigned long) &_end,
@@ -717,6 +760,17 @@ static bool assign_lock_key(struct lockdep_map *lock)
 {
        unsigned long can_addr, addr = (unsigned long)lock;
 
+#ifdef __KERNEL__
+       /*
+        * lockdep_free_key_range() assumes that struct lock_class_key
+        * objects do not overlap. Since we use the address of lock
+        * objects as class key for static objects, check whether the
+        * size of lock_class_key objects does not exceed the size of
+        * the smallest lock object.
+        */
+       BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
+#endif
+
        if (__is_kernel_percpu_address(addr, &can_addr))
                lock->key = (void *)can_addr;
        else if (__is_module_percpu_address(addr, &can_addr))
@@ -736,6 +790,280 @@ static bool assign_lock_key(struct lockdep_map *lock)
        return true;
 }
 
+#ifdef CONFIG_DEBUG_LOCKDEP
+
+/* Check whether element @e occurs in list @h */
+static bool in_list(struct list_head *e, struct list_head *h)
+{
+       struct list_head *f;
+
+       list_for_each(f, h) {
+               if (e == f)
+                       return true;
+       }
+
+       return false;
+}
+
+/*
+ * Check whether entry @e occurs in any of the locks_after or locks_before
+ * lists.
+ */
+static bool in_any_class_list(struct list_head *e)
+{
+       struct lock_class *class;
+       int i;
+
+       for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+               class = &lock_classes[i];
+               if (in_list(e, &class->locks_after) ||
+                   in_list(e, &class->locks_before))
+                       return true;
+       }
+       return false;
+}
+
+static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
+{
+       struct lock_list *e;
+
+       list_for_each_entry(e, h, entry) {
+               if (e->links_to != c) {
+                       printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
+                              c->name ? : "(?)",
+                              (unsigned long)(e - list_entries),
+                              e->links_to && e->links_to->name ?
+                              e->links_to->name : "(?)",
+                              e->class && e->class->name ? e->class->name :
+                              "(?)");
+                       return false;
+               }
+       }
+       return true;
+}
+
+static u16 chain_hlocks[];
+
+static bool check_lock_chain_key(struct lock_chain *chain)
+{
+#ifdef CONFIG_PROVE_LOCKING
+       u64 chain_key = 0;
+       int i;
+
+       for (i = chain->base; i < chain->base + chain->depth; i++)
+               chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+       /*
+        * The 'unsigned long long' casts avoid that a compiler warning
+        * is reported when building tools/lib/lockdep.
+        */
+       if (chain->chain_key != chain_key) {
+               printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
+                      (unsigned long long)(chain - lock_chains),
+                      (unsigned long long)chain->chain_key,
+                      (unsigned long long)chain_key);
+               return false;
+       }
+#endif
+       return true;
+}
+
+static bool in_any_zapped_class_list(struct lock_class *class)
+{
+       struct pending_free *pf;
+       int i;
+
+       for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) {
+               if (in_list(&class->lock_entry, &pf->zapped))
+                       return true;
+       }
+
+       return false;
+}
+
+static bool __check_data_structures(void)
+{
+       struct lock_class *class;
+       struct lock_chain *chain;
+       struct hlist_head *head;
+       struct lock_list *e;
+       int i;
+
+       /* Check whether all classes occur in a lock list. */
+       for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+               class = &lock_classes[i];
+               if (!in_list(&class->lock_entry, &all_lock_classes) &&
+                   !in_list(&class->lock_entry, &free_lock_classes) &&
+                   !in_any_zapped_class_list(class)) {
+                       printk(KERN_INFO "class %px/%s is not in any class list\n",
+                              class, class->name ? : "(?)");
+                       return false;
+               }
+       }
+
+       /* Check whether all classes have valid lock lists. */
+       for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+               class = &lock_classes[i];
+               if (!class_lock_list_valid(class, &class->locks_before))
+                       return false;
+               if (!class_lock_list_valid(class, &class->locks_after))
+                       return false;
+       }
+
+       /* Check the chain_key of all lock chains. */
+       for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
+               head = chainhash_table + i;
+               hlist_for_each_entry_rcu(chain, head, entry) {
+                       if (!check_lock_chain_key(chain))
+                               return false;
+               }
+       }
+
+       /*
+        * Check whether all list entries that are in use occur in a class
+        * lock list.
+        */
+       for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
+               e = list_entries + i;
+               if (!in_any_class_list(&e->entry)) {
+                       printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n",
+                              (unsigned int)(e - list_entries),
+                              e->class->name ? : "(?)",
+                              e->links_to->name ? : "(?)");
+                       return false;
+               }
+       }
+
+       /*
+        * Check whether all list entries that are not in use do not occur in
+        * a class lock list.
+        */
+       for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
+               e = list_entries + i;
+               if (in_any_class_list(&e->entry)) {
+                       printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n",
+                              (unsigned int)(e - list_entries),
+                              e->class && e->class->name ? e->class->name :
+                              "(?)",
+                              e->links_to && e->links_to->name ?
+                              e->links_to->name : "(?)");
+                       return false;
+               }
+       }
+
+       return true;
+}
+
+int check_consistency = 0;
+module_param(check_consistency, int, 0644);
+
+static void check_data_structures(void)
+{
+       static bool once = false;
+
+       if (check_consistency && !once) {
+               if (!__check_data_structures()) {
+                       once = true;
+                       WARN_ON(once);
+               }
+       }
+}
+
+#else /* CONFIG_DEBUG_LOCKDEP */
+
+static inline void check_data_structures(void) { }
+
+#endif /* CONFIG_DEBUG_LOCKDEP */
+
+/*
+ * Initialize the lock_classes[] array elements, the free_lock_classes list
+ * and also the delayed_free structure.
+ */
+static void init_data_structures_once(void)
+{
+       static bool initialization_happened;
+       int i;
+
+       if (likely(initialization_happened))
+               return;
+
+       initialization_happened = true;
+
+       init_rcu_head(&delayed_free.rcu_head);
+       INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
+       INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
+
+       for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
+               list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
+               INIT_LIST_HEAD(&lock_classes[i].locks_after);
+               INIT_LIST_HEAD(&lock_classes[i].locks_before);
+       }
+}
+
+static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
+{
+       unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS);
+
+       return lock_keys_hash + hash;
+}
+
+/* Register a dynamically allocated key. */
+void lockdep_register_key(struct lock_class_key *key)
+{
+       struct hlist_head *hash_head;
+       struct lock_class_key *k;
+       unsigned long flags;
+
+       if (WARN_ON_ONCE(static_obj(key)))
+               return;
+       hash_head = keyhashentry(key);
+
+       raw_local_irq_save(flags);
+       if (!graph_lock())
+               goto restore_irqs;
+       hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
+               if (WARN_ON_ONCE(k == key))
+                       goto out_unlock;
+       }
+       hlist_add_head_rcu(&key->hash_entry, hash_head);
+out_unlock:
+       graph_unlock();
+restore_irqs:
+       raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lockdep_register_key);
+
+/* Check whether a key has been registered as a dynamic key. */
+static bool is_dynamic_key(const struct lock_class_key *key)
+{
+       struct hlist_head *hash_head;
+       struct lock_class_key *k;
+       bool found = false;
+
+       if (WARN_ON_ONCE(static_obj(key)))
+               return false;
+
+       /*
+        * If lock debugging is disabled lock_keys_hash[] may contain
+        * pointers to memory that has already been freed. Avoid triggering
+        * a use-after-free in that case by returning early.
+        */
+       if (!debug_locks)
+               return true;
+
+       hash_head = keyhashentry(key);
+
+       rcu_read_lock();
+       hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
+               if (k == key) {
+                       found = true;
+                       break;
+               }
+       }
+       rcu_read_unlock();
+
+       return found;
+}
+
 /*
  * Register a lock's class in the hash-table, if the class is not present
  * yet. Otherwise we look it up. We cache the result in the lock object
@@ -757,7 +1085,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
        if (!lock->key) {
                if (!assign_lock_key(lock))
                        return NULL;
-       } else if (!static_obj(lock->key)) {
+       } else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
                return NULL;
        }
 
@@ -776,11 +1104,12 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
                        goto out_unlock_set;
        }
 
-       /*
-        * Allocate a new key from the static array, and add it to
-        * the hash:
-        */
-       if (nr_lock_classes >= MAX_LOCKDEP_KEYS) {
+       init_data_structures_once();
+
+       /* Allocate a new lock class and add it to the hash. */
+       class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
+                                        lock_entry);
+       if (!class) {
                if (!debug_locks_off_graph_unlock()) {
                        return NULL;
                }
@@ -789,13 +1118,13 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
                dump_stack();
                return NULL;
        }
-       class = lock_classes + nr_lock_classes++;
+       nr_lock_classes++;
        debug_atomic_inc(nr_unused_locks);
        class->key = key;
        class->name = lock->name;
        class->subclass = subclass;
-       INIT_LIST_HEAD(&class->locks_before);
-       INIT_LIST_HEAD(&class->locks_after);
+       WARN_ON_ONCE(!list_empty(&class->locks_before));
+       WARN_ON_ONCE(!list_empty(&class->locks_after));
        class->name_version = count_matching_names(class);
        /*
         * We use RCU's safe list-add method to make
@@ -803,9 +1132,10 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
         */
        hlist_add_head_rcu(&class->hash_entry, hash_head);
        /*
-        * Add it to the global list of classes:
+        * Remove the class from the free list and add it to the global list
+        * of classes.
         */
-       list_add_tail(&class->lock_entry, &all_lock_classes);
+       list_move_tail(&class->lock_entry, &all_lock_classes);
 
        if (verbose(class)) {
                graph_unlock();
@@ -846,7 +1176,10 @@ out_set_class_cache:
  */
 static struct lock_list *alloc_list_entry(void)
 {
-       if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
+       int idx = find_first_zero_bit(list_entries_in_use,
+                                     ARRAY_SIZE(list_entries));
+
+       if (idx >= ARRAY_SIZE(list_entries)) {
                if (!debug_locks_off_graph_unlock())
                        return NULL;
 
@@ -854,13 +1187,16 @@ static struct lock_list *alloc_list_entry(void)
                dump_stack();
                return NULL;
        }
-       return list_entries + nr_list_entries++;
+       nr_list_entries++;
+       __set_bit(idx, list_entries_in_use);
+       return list_entries + idx;
 }
 
 /*
  * Add a new dependency to the head of the list:
  */
-static int add_lock_to_list(struct lock_class *this, struct list_head *head,
+static int add_lock_to_list(struct lock_class *this,
+                           struct lock_class *links_to, struct list_head *head,
                            unsigned long ip, int distance,
                            struct stack_trace *trace)
 {
@@ -874,6 +1210,7 @@ static int add_lock_to_list(struct lock_class *this, struct list_head *head,
                return 0;
 
        entry->class = this;
+       entry->links_to = links_to;
        entry->distance = distance;
        entry->trace = *trace;
        /*
@@ -956,7 +1293,7 @@ static inline void mark_lock_accessed(struct lock_list *lock,
        unsigned long nr;
 
        nr = lock - list_entries;
-       WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+       WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
        lock->parent = parent;
        lock->class->dep_gen_id = lockdep_dependency_gen_id;
 }
@@ -966,7 +1303,7 @@ static inline unsigned long lock_accessed(struct lock_list *lock)
        unsigned long nr;
 
        nr = lock - list_entries;
-       WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+       WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
        return lock->class->dep_gen_id == lockdep_dependency_gen_id;
 }
 
@@ -1625,29 +1962,18 @@ static const char *state_rnames[] = {
 
 static inline const char *state_name(enum lock_usage_bit bit)
 {
-       return (bit & 1) ? state_rnames[bit >> 2] : state_names[bit >> 2];
+       return (bit & LOCK_USAGE_READ_MASK) ? state_rnames[bit >> 2] : state_names[bit >> 2];
 }
 
 static int exclusive_bit(int new_bit)
 {
-       /*
-        * USED_IN
-        * USED_IN_READ
-        * ENABLED
-        * ENABLED_READ
-        *
-        * bit 0 - write/read
-        * bit 1 - used_in/enabled
-        * bit 2+  state
-        */
-
-       int state = new_bit & ~3;
-       int dir = new_bit & 2;
+       int state = new_bit & LOCK_USAGE_STATE_MASK;
+       int dir = new_bit & LOCK_USAGE_DIR_MASK;
 
        /*
         * keep state, bit flip the direction and strip read.
         */
-       return state | (dir ^ 2);
+       return state | (dir ^ LOCK_USAGE_DIR_MASK);
 }
 
 static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
@@ -1843,6 +2169,24 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
        struct lock_list this;
        int ret;
 
+       if (!hlock_class(prev)->key || !hlock_class(next)->key) {
+               /*
+                * The warning statements below may trigger a use-after-free
+                * of the class name. It is better to trigger a use-after free
+                * and to have the class name most of the time instead of not
+                * having the class name available.
+                */
+               WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
+                         "Detected use-after-free of lock class %px/%s\n",
+                         hlock_class(prev),
+                         hlock_class(prev)->name);
+               WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
+                         "Detected use-after-free of lock class %px/%s\n",
+                         hlock_class(next),
+                         hlock_class(next)->name);
+               return 2;
+       }
+
        /*
         * Prove that the new <prev> -> <next> dependency would not
         * create a circular dependency in the graph. (We do this by
@@ -1919,14 +2263,14 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
         * Ok, all validations passed, add the new lock
         * to the previous lock's dependency list:
         */
-       ret = add_lock_to_list(hlock_class(next),
+       ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
                               &hlock_class(prev)->locks_after,
                               next->acquire_ip, distance, trace);
 
        if (!ret)
                return 0;
 
-       ret = add_lock_to_list(hlock_class(prev),
+       ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
                               &hlock_class(next)->locks_before,
                               next->acquire_ip, distance, trace);
        if (!ret)
@@ -2019,8 +2363,8 @@ out_bug:
        return 0;
 }
 
-unsigned long nr_lock_chains;
 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
+static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
 int nr_chain_hlocks;
 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
 
@@ -2153,6 +2497,33 @@ static int check_no_collision(struct task_struct *curr,
        return 1;
 }
 
+/*
+ * Given an index that is >= -1, return the index of the next lock chain.
+ * Return -2 if there is no next lock chain.
+ */
+long lockdep_next_lockchain(long i)
+{
+       i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
+       return i < ARRAY_SIZE(lock_chains) ? i : -2;
+}
+
+unsigned long lock_chain_count(void)
+{
+       return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
+}
+
+/* Must be called with the graph lock held. */
+static struct lock_chain *alloc_lock_chain(void)
+{
+       int idx = find_first_zero_bit(lock_chains_in_use,
+                                     ARRAY_SIZE(lock_chains));
+
+       if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
+               return NULL;
+       __set_bit(idx, lock_chains_in_use);
+       return lock_chains + idx;
+}
+
 /*
  * Adds a dependency chain into chain hashtable. And must be called with
  * graph_lock held.
@@ -2170,19 +2541,15 @@ static inline int add_chain_cache(struct task_struct *curr,
        int i, j;
 
        /*
-        * Allocate a new chain entry from the static array, and add
-        * it to the hash:
-        */
-
-       /*
-        * We might need to take the graph lock, ensure we've got IRQs
+        * The caller must hold the graph lock, ensure we've got IRQs
         * disabled to make this an IRQ-safe lock.. for recursion reasons
         * lockdep won't complain about its own locking errors.
         */
        if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
                return 0;
 
-       if (unlikely(nr_lock_chains >= MAX_LOCKDEP_CHAINS)) {
+       chain = alloc_lock_chain();
+       if (!chain) {
                if (!debug_locks_off_graph_unlock())
                        return 0;
 
@@ -2190,7 +2557,6 @@ static inline int add_chain_cache(struct task_struct *curr,
                dump_stack();
                return 0;
        }
-       chain = lock_chains + nr_lock_chains++;
        chain->chain_key = chain_key;
        chain->irq_context = hlock->irq_context;
        i = get_first_held_lock(curr, hlock);
@@ -2207,16 +2573,8 @@ static inline int add_chain_cache(struct task_struct *curr,
                        chain_hlocks[chain->base + j] = lock_id;
                }
                chain_hlocks[chain->base + j] = class - lock_classes;
-       }
-
-       if (nr_chain_hlocks < MAX_LOCKDEP_CHAIN_HLOCKS)
                nr_chain_hlocks += chain->depth;
-
-#ifdef CONFIG_DEBUG_LOCKDEP
-       /*
-        * Important for check_no_collision().
-        */
-       if (unlikely(nr_chain_hlocks > MAX_LOCKDEP_CHAIN_HLOCKS)) {
+       } else {
                if (!debug_locks_off_graph_unlock())
                        return 0;
 
@@ -2224,7 +2582,6 @@ static inline int add_chain_cache(struct task_struct *curr,
                dump_stack();
                return 0;
        }
-#endif
 
        hlist_add_head_rcu(&chain->entry, hash_head);
        debug_atomic_inc(chain_lookup_misses);
@@ -2234,19 +2591,16 @@ static inline int add_chain_cache(struct task_struct *curr,
 }
 
 /*
- * Look up a dependency chain.
+ * Look up a dependency chain. Must be called with either the graph lock or
+ * the RCU read lock held.
  */
 static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
 {
        struct hlist_head *hash_head = chainhashentry(chain_key);
        struct lock_chain *chain;
 
-       /*
-        * We can walk it lock-free, because entries only get added
-        * to the hash:
-        */
        hlist_for_each_entry_rcu(chain, hash_head, entry) {
-               if (chain->chain_key == chain_key) {
+               if (READ_ONCE(chain->chain_key) == chain_key) {
                        debug_atomic_inc(chain_lookup_hits);
                        return chain;
                }
@@ -2663,8 +3017,8 @@ mark_lock_irq(struct task_struct *curr, struct held_lock *this,
                enum lock_usage_bit new_bit)
 {
        int excl_bit = exclusive_bit(new_bit);
-       int read = new_bit & 1;
-       int dir = new_bit & 2;
+       int read = new_bit & LOCK_USAGE_READ_MASK;
+       int dir = new_bit & LOCK_USAGE_DIR_MASK;
 
        /*
         * mark USED_IN has to look forwards -- to ensure no dependency
@@ -2688,19 +3042,19 @@ mark_lock_irq(struct task_struct *curr, struct held_lock *this,
         * states.
         */
        if ((!read || !dir || STRICT_READ_CHECKS) &&
-                       !usage(curr, this, excl_bit, state_name(new_bit & ~1)))
+                       !usage(curr, this, excl_bit, state_name(new_bit & ~LOCK_USAGE_READ_MASK)))
                return 0;
 
        /*
         * Check for read in write conflicts
         */
        if (!read) {
-               if (!valid_state(curr, this, new_bit, excl_bit + 1))
+               if (!valid_state(curr, this, new_bit, excl_bit + LOCK_USAGE_READ_MASK))
                        return 0;
 
                if (STRICT_READ_CHECKS &&
-                       !usage(curr, this, excl_bit + 1,
-                               state_name(new_bit + 1)))
+                       !usage(curr, this, excl_bit + LOCK_USAGE_READ_MASK,
+                               state_name(new_bit + LOCK_USAGE_READ_MASK)))
                        return 0;
        }
 
@@ -2710,35 +3064,28 @@ mark_lock_irq(struct task_struct *curr, struct held_lock *this,
        return 1;
 }
 
-enum mark_type {
-#define LOCKDEP_STATE(__STATE) __STATE,
-#include "lockdep_states.h"
-#undef LOCKDEP_STATE
-};
-
 /*
  * Mark all held locks with a usage bit:
  */
 static int
-mark_held_locks(struct task_struct *curr, enum mark_type mark)
+mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
 {
-       enum lock_usage_bit usage_bit;
        struct held_lock *hlock;
        int i;
 
        for (i = 0; i < curr->lockdep_depth; i++) {
+               enum lock_usage_bit hlock_bit = base_bit;
                hlock = curr->held_locks + i;
 
-               usage_bit = 2 + (mark << 2); /* ENABLED */
                if (hlock->read)
-                       usage_bit += 1; /* READ */
+                       hlock_bit += LOCK_USAGE_READ_MASK;
 
-               BUG_ON(usage_bit >= LOCK_USAGE_STATES);
+               BUG_ON(hlock_bit >= LOCK_USAGE_STATES);
 
                if (!hlock->check)
                        continue;
 
-               if (!mark_lock(curr, hlock, usage_bit))
+               if (!mark_lock(curr, hlock, hlock_bit))
                        return 0;
        }
 
@@ -2759,7 +3106,7 @@ static void __trace_hardirqs_on_caller(unsigned long ip)
         * We are going to turn hardirqs on, so set the
         * usage bit for all held locks:
         */
-       if (!mark_held_locks(curr, HARDIRQ))
+       if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ))
                return;
        /*
         * If we have softirqs enabled, then set the usage
@@ -2767,7 +3114,7 @@ static void __trace_hardirqs_on_caller(unsigned long ip)
         * this bit from being set before)
         */
        if (curr->softirqs_enabled)
-               if (!mark_held_locks(curr, SOFTIRQ))
+               if (!mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ))
                        return;
 
        curr->hardirq_enable_ip = ip;
@@ -2883,7 +3230,7 @@ void trace_softirqs_on(unsigned long ip)
         * enabled too:
         */
        if (curr->hardirqs_enabled)
-               mark_held_locks(curr, SOFTIRQ);
+               mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ);
        current->lockdep_recursion = 0;
 }
 
@@ -3122,13 +3469,12 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
        if (DEBUG_LOCKS_WARN_ON(!key))
                return;
        /*
-        * Sanity check, the lock-class key must be persistent:
+        * Sanity check, the lock-class key must either have been allocated
+        * statically or must have been registered as a dynamic key.
         */
-       if (!static_obj(key)) {
-               printk("BUG: key %px not in .data!\n", key);
-               /*
-                * What it says above ^^^^^, I suggest you read it.
-                */
+       if (!static_obj(key) && !is_dynamic_key(key)) {
+               if (debug_locks)
+                       printk(KERN_ERR "BUG: key %px has not been registered!\n", key);
                DEBUG_LOCKS_WARN_ON(1);
                return;
        }
@@ -3338,6 +3684,11 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
        if (nest_lock && !__lock_is_held(nest_lock, -1))
                return print_lock_nested_lock_not_held(curr, hlock, ip);
 
+       if (!debug_locks_silent) {
+               WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
+               WARN_ON_ONCE(!hlock_class(hlock)->key);
+       }
+
        if (!validate_chain(curr, lock, hlock, chain_head, chain_key))
                return 0;
 
@@ -3500,6 +3851,9 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
        unsigned int depth;
        int i;
 
+       if (unlikely(!debug_locks))
+               return 0;
+
        depth = curr->lockdep_depth;
        /*
         * This function is about (re)setting the class of a held lock,
@@ -3538,6 +3892,9 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
        unsigned int depth;
        int i;
 
+       if (unlikely(!debug_locks))
+               return 0;
+
        depth = curr->lockdep_depth;
        /*
         * This function is about (re)setting the class of a held lock,
@@ -4128,29 +4485,131 @@ void lockdep_reset(void)
        raw_local_irq_restore(flags);
 }
 
+/* Remove a class from a lock chain. Must be called with the graph lock held. */
+static void remove_class_from_lock_chain(struct pending_free *pf,
+                                        struct lock_chain *chain,
+                                        struct lock_class *class)
+{
+#ifdef CONFIG_PROVE_LOCKING
+       struct lock_chain *new_chain;
+       u64 chain_key;
+       int i;
+
+       for (i = chain->base; i < chain->base + chain->depth; i++) {
+               if (chain_hlocks[i] != class - lock_classes)
+                       continue;
+               /* The code below leaks one chain_hlock[] entry. */
+               if (--chain->depth > 0) {
+                       memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
+                               (chain->base + chain->depth - i) *
+                               sizeof(chain_hlocks[0]));
+               }
+               /*
+                * Each lock class occurs at most once in a lock chain so once
+                * we found a match we can break out of this loop.
+                */
+               goto recalc;
+       }
+       /* Since the chain has not been modified, return. */
+       return;
+
+recalc:
+       chain_key = 0;
+       for (i = chain->base; i < chain->base + chain->depth; i++)
+               chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+       if (chain->depth && chain->chain_key == chain_key)
+               return;
+       /* Overwrite the chain key for concurrent RCU readers. */
+       WRITE_ONCE(chain->chain_key, chain_key);
+       /*
+        * Note: calling hlist_del_rcu() from inside a
+        * hlist_for_each_entry_rcu() loop is safe.
+        */
+       hlist_del_rcu(&chain->entry);
+       __set_bit(chain - lock_chains, pf->lock_chains_being_freed);
+       if (chain->depth == 0)
+               return;
+       /*
+        * If the modified lock chain matches an existing lock chain, drop
+        * the modified lock chain.
+        */
+       if (lookup_chain_cache(chain_key))
+               return;
+       new_chain = alloc_lock_chain();
+       if (WARN_ON_ONCE(!new_chain)) {
+               debug_locks_off();
+               return;
+       }
+       *new_chain = *chain;
+       hlist_add_head_rcu(&new_chain->entry, chainhashentry(chain_key));
+#endif
+}
+
+/* Must be called with the graph lock held. */
+static void remove_class_from_lock_chains(struct pending_free *pf,
+                                         struct lock_class *class)
+{
+       struct lock_chain *chain;
+       struct hlist_head *head;
+       int i;
+
+       for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
+               head = chainhash_table + i;
+               hlist_for_each_entry_rcu(chain, head, entry) {
+                       remove_class_from_lock_chain(pf, chain, class);
+               }
+       }
+}
+
 /*
  * Remove all references to a lock class. The caller must hold the graph lock.
  */
-static void zap_class(struct lock_class *class)
+static void zap_class(struct pending_free *pf, struct lock_class *class)
 {
+       struct lock_list *entry;
        int i;
 
+       WARN_ON_ONCE(!class->key);
+
        /*
         * Remove all dependencies this lock is
         * involved in:
         */
-       for (i = 0; i < nr_list_entries; i++) {
-               if (list_entries[i].class == class)
-                       list_del_rcu(&list_entries[i].entry);
+       for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
+               entry = list_entries + i;
+               if (entry->class != class && entry->links_to != class)
+                       continue;
+               __clear_bit(i, list_entries_in_use);
+               nr_list_entries--;
+               list_del_rcu(&entry->entry);
+       }
+       if (list_empty(&class->locks_after) &&
+           list_empty(&class->locks_before)) {
+               list_move_tail(&class->lock_entry, &pf->zapped);
+               hlist_del_rcu(&class->hash_entry);
+               WRITE_ONCE(class->key, NULL);
+               WRITE_ONCE(class->name, NULL);
+               nr_lock_classes--;
+       } else {
+               WARN_ONCE(true, "%s() failed for class %s\n", __func__,
+                         class->name);
        }
-       /*
-        * Unhash the class and remove it from the all_lock_classes list:
-        */
-       hlist_del_rcu(&class->hash_entry);
-       list_del(&class->lock_entry);
 
-       RCU_INIT_POINTER(class->key, NULL);
-       RCU_INIT_POINTER(class->name, NULL);
+       remove_class_from_lock_chains(pf, class);
+}
+
+static void reinit_class(struct lock_class *class)
+{
+       void *const p = class;
+       const unsigned int offset = offsetof(struct lock_class, key);
+
+       WARN_ON_ONCE(!class->lock_entry.next);
+       WARN_ON_ONCE(!list_empty(&class->locks_after));
+       WARN_ON_ONCE(!list_empty(&class->locks_before));
+       memset(p + offset, 0, sizeof(*class) - offset);
+       WARN_ON_ONCE(!class->lock_entry.next);
+       WARN_ON_ONCE(!list_empty(&class->locks_after));
+       WARN_ON_ONCE(!list_empty(&class->locks_before));
 }
 
 static inline int within(const void *addr, void *start, unsigned long size)
@@ -4158,55 +4617,175 @@ static inline int within(const void *addr, void *start, unsigned long size)
        return addr >= start && addr < start + size;
 }
 
+static bool inside_selftest(void)
+{
+       return current == lockdep_selftest_task_struct;
+}
+
+/* The caller must hold the graph lock. */
+static struct pending_free *get_pending_free(void)
+{
+       return delayed_free.pf + delayed_free.index;
+}
+
+static void free_zapped_rcu(struct rcu_head *cb);
+
 /*
- * Used in module.c to remove lock classes from memory that is going to be
- * freed; and possibly re-used by other modules.
- *
- * We will have had one sync_sched() before getting here, so we're guaranteed
- * nobody will look up these exact classes -- they're properly dead but still
- * allocated.
+ * Schedule an RCU callback if no RCU callback is pending. Must be called with
+ * the graph lock held.
  */
-void lockdep_free_key_range(void *start, unsigned long size)
+static void call_rcu_zapped(struct pending_free *pf)
+{
+       WARN_ON_ONCE(inside_selftest());
+
+       if (list_empty(&pf->zapped))
+               return;
+
+       if (delayed_free.scheduled)
+               return;
+
+       delayed_free.scheduled = true;
+
+       WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf);
+       delayed_free.index ^= 1;
+
+       call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
+}
+
+/* The caller must hold the graph lock. May be called from RCU context. */
+static void __free_zapped_classes(struct pending_free *pf)
 {
        struct lock_class *class;
-       struct hlist_head *head;
+
+       check_data_structures();
+
+       list_for_each_entry(class, &pf->zapped, lock_entry)
+               reinit_class(class);
+
+       list_splice_init(&pf->zapped, &free_lock_classes);
+
+#ifdef CONFIG_PROVE_LOCKING
+       bitmap_andnot(lock_chains_in_use, lock_chains_in_use,
+                     pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains));
+       bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains));
+#endif
+}
+
+static void free_zapped_rcu(struct rcu_head *ch)
+{
+       struct pending_free *pf;
        unsigned long flags;
-       int i;
-       int locked;
+
+       if (WARN_ON_ONCE(ch != &delayed_free.rcu_head))
+               return;
 
        raw_local_irq_save(flags);
-       locked = graph_lock();
+       if (!graph_lock())
+               goto out_irq;
+
+       /* closed head */
+       pf = delayed_free.pf + (delayed_free.index ^ 1);
+       __free_zapped_classes(pf);
+       delayed_free.scheduled = false;
 
        /*
-        * Unhash all classes that were created by this module:
+        * If there's anything on the open list, close and start a new callback.
         */
+       call_rcu_zapped(delayed_free.pf + delayed_free.index);
+
+       graph_unlock();
+out_irq:
+       raw_local_irq_restore(flags);
+}
+
+/*
+ * Remove all lock classes from the class hash table and from the
+ * all_lock_classes list whose key or name is in the address range [start,
+ * start + size). Move these lock classes to the zapped_classes list. Must
+ * be called with the graph lock held.
+ */
+static void __lockdep_free_key_range(struct pending_free *pf, void *start,
+                                    unsigned long size)
+{
+       struct lock_class *class;
+       struct hlist_head *head;
+       int i;
+
+       /* Unhash all classes that were created by a module. */
        for (i = 0; i < CLASSHASH_SIZE; i++) {
                head = classhash_table + i;
                hlist_for_each_entry_rcu(class, head, hash_entry) {
-                       if (within(class->key, start, size))
-                               zap_class(class);
-                       else if (within(class->name, start, size))
-                               zap_class(class);
+                       if (!within(class->key, start, size) &&
+                           !within(class->name, start, size))
+                               continue;
+                       zap_class(pf, class);
                }
        }
+}
 
-       if (locked)
-               graph_unlock();
+/*
+ * Used in module.c to remove lock classes from memory that is going to be
+ * freed; and possibly re-used by other modules.
+ *
+ * We will have had one synchronize_rcu() before getting here, so we're
+ * guaranteed nobody will look up these exact classes -- they're properly dead
+ * but still allocated.
+ */
+static void lockdep_free_key_range_reg(void *start, unsigned long size)
+{
+       struct pending_free *pf;
+       unsigned long flags;
+       int locked;
+
+       init_data_structures_once();
+
+       raw_local_irq_save(flags);
+       locked = graph_lock();
+       if (!locked)
+               goto out_irq;
+
+       pf = get_pending_free();
+       __lockdep_free_key_range(pf, start, size);
+       call_rcu_zapped(pf);
+
+       graph_unlock();
+out_irq:
        raw_local_irq_restore(flags);
 
        /*
         * Wait for any possible iterators from look_up_lock_class() to pass
         * before continuing to free the memory they refer to.
-        *
-        * sync_sched() is sufficient because the read-side is IRQ disable.
         */
        synchronize_rcu();
+}
 
-       /*
-        * XXX at this point we could return the resources to the pool;
-        * instead we leak them. We would need to change to bitmap allocators
-        * instead of the linear allocators we have now.
-        */
+/*
+ * Free all lockdep keys in the range [start, start+size). Does not sleep.
+ * Ignores debug_locks. Must only be used by the lockdep selftests.
+ */
+static void lockdep_free_key_range_imm(void *start, unsigned long size)
+{
+       struct pending_free *pf = delayed_free.pf;
+       unsigned long flags;
+
+       init_data_structures_once();
+
+       raw_local_irq_save(flags);
+       arch_spin_lock(&lockdep_lock);
+       __lockdep_free_key_range(pf, start, size);
+       __free_zapped_classes(pf);
+       arch_spin_unlock(&lockdep_lock);
+       raw_local_irq_restore(flags);
+}
+
+void lockdep_free_key_range(void *start, unsigned long size)
+{
+       init_data_structures_once();
+
+       if (inside_selftest())
+               lockdep_free_key_range_imm(start, size);
+       else
+               lockdep_free_key_range_reg(start, size);
 }
 
 /*
@@ -4231,14 +4810,12 @@ static bool lock_class_cache_is_registered(struct lockdep_map *lock)
        return false;
 }
 
-void lockdep_reset_lock(struct lockdep_map *lock)
+/* The caller must hold the graph lock. Does not sleep. */
+static void __lockdep_reset_lock(struct pending_free *pf,
+                                struct lockdep_map *lock)
 {
        struct lock_class *class;
-       unsigned long flags;
-       int j, locked;
-
-       raw_local_irq_save(flags);
-       locked = graph_lock();
+       int j;
 
        /*
         * Remove all classes this lock might have:
@@ -4249,27 +4826,104 @@ void lockdep_reset_lock(struct lockdep_map *lock)
                 */
                class = look_up_lock_class(lock, j);
                if (class)
-                       zap_class(class);
+                       zap_class(pf, class);
        }
        /*
         * Debug check: in the end all mapped classes should
         * be gone.
         */
-       if (unlikely(lock_class_cache_is_registered(lock))) {
-               if (debug_locks_off_graph_unlock()) {
-                       /*
-                        * We all just reset everything, how did it match?
-                        */
-                       WARN_ON(1);
+       if (WARN_ON_ONCE(lock_class_cache_is_registered(lock)))
+               debug_locks_off();
+}
+
+/*
+ * Remove all information lockdep has about a lock if debug_locks == 1. Free
+ * released data structures from RCU context.
+ */
+static void lockdep_reset_lock_reg(struct lockdep_map *lock)
+{
+       struct pending_free *pf;
+       unsigned long flags;
+       int locked;
+
+       raw_local_irq_save(flags);
+       locked = graph_lock();
+       if (!locked)
+               goto out_irq;
+
+       pf = get_pending_free();
+       __lockdep_reset_lock(pf, lock);
+       call_rcu_zapped(pf);
+
+       graph_unlock();
+out_irq:
+       raw_local_irq_restore(flags);
+}
+
+/*
+ * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
+ * lockdep selftests.
+ */
+static void lockdep_reset_lock_imm(struct lockdep_map *lock)
+{
+       struct pending_free *pf = delayed_free.pf;
+       unsigned long flags;
+
+       raw_local_irq_save(flags);
+       arch_spin_lock(&lockdep_lock);
+       __lockdep_reset_lock(pf, lock);
+       __free_zapped_classes(pf);
+       arch_spin_unlock(&lockdep_lock);
+       raw_local_irq_restore(flags);
+}
+
+void lockdep_reset_lock(struct lockdep_map *lock)
+{
+       init_data_structures_once();
+
+       if (inside_selftest())
+               lockdep_reset_lock_imm(lock);
+       else
+               lockdep_reset_lock_reg(lock);
+}
+
+/* Unregister a dynamically allocated key. */
+void lockdep_unregister_key(struct lock_class_key *key)
+{
+       struct hlist_head *hash_head = keyhashentry(key);
+       struct lock_class_key *k;
+       struct pending_free *pf;
+       unsigned long flags;
+       bool found = false;
+
+       might_sleep();
+
+       if (WARN_ON_ONCE(static_obj(key)))
+               return;
+
+       raw_local_irq_save(flags);
+       if (!graph_lock())
+               goto out_irq;
+
+       pf = get_pending_free();
+       hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
+               if (k == key) {
+                       hlist_del_rcu(&k->hash_entry);
+                       found = true;
+                       break;
                }
-               goto out_restore;
        }
-       if (locked)
-               graph_unlock();
-
-out_restore:
+       WARN_ON_ONCE(!found);
+       __lockdep_free_key_range(pf, key, 1);
+       call_rcu_zapped(pf);
+       graph_unlock();
+out_irq:
        raw_local_irq_restore(flags);
+
+       /* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
+       synchronize_rcu();
 }
+EXPORT_SYMBOL_GPL(lockdep_unregister_key);
 
 void __init lockdep_init(void)
 {
@@ -4283,20 +4937,24 @@ void __init lockdep_init(void)
        printk("... MAX_LOCKDEP_CHAINS:      %lu\n", MAX_LOCKDEP_CHAINS);
        printk("... CHAINHASH_SIZE:          %lu\n", CHAINHASH_SIZE);
 
-       printk(" memory used by lock dependency info: %lu kB\n",
-               (sizeof(struct lock_class) * MAX_LOCKDEP_KEYS +
-               sizeof(struct list_head) * CLASSHASH_SIZE +
-               sizeof(struct lock_list) * MAX_LOCKDEP_ENTRIES +
-               sizeof(struct lock_chain) * MAX_LOCKDEP_CHAINS +
-               sizeof(struct list_head) * CHAINHASH_SIZE
+       printk(" memory used by lock dependency info: %zu kB\n",
+              (sizeof(lock_classes) +
+               sizeof(classhash_table) +
+               sizeof(list_entries) +
+               sizeof(list_entries_in_use) +
+               sizeof(chainhash_table) +
+               sizeof(delayed_free)
 #ifdef CONFIG_PROVE_LOCKING
-               + sizeof(struct circular_queue)
+               + sizeof(lock_cq)
+               + sizeof(lock_chains)
+               + sizeof(lock_chains_in_use)
+               + sizeof(chain_hlocks)
 #endif
                ) / 1024
                );
 
-       printk(" per task-struct memory footprint: %lu bytes\n",
-               sizeof(struct held_lock) * MAX_LOCK_DEPTH);
+       printk(" per task-struct memory footprint: %zu bytes\n",
+              sizeof(((struct task_struct *)NULL)->held_locks));
 }
 
 static void