[PATCH v3 17/24] locking/lockdep: Free lock classes that are no longer in use

From: Bart Van Assche
Date: Thu Dec 06 2018 - 20:14:23 EST


Instead of leaving lock classes that are no longer in use in the
lock_classes array, reuse entries from that array that are no longer
in use. Maintain a linked list of free lock classes with list head
'free_lock_class'. Initialize that list from inside register_lock_class()
instead of from inside lockdep_init() because register_lock_class() can
be called before lockdep_init() has been called. Only add freed lock
classes to the free_lock_classes list after a grace period to avoid that
a lock_classes[] element would be reused while an RCU reader is
accessing it.

Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Waiman Long <longman@xxxxxxxxxx>
Cc: Johannes Berg <johannes@xxxxxxxxxxxxxxxx>
Signed-off-by: Bart Van Assche <bvanassche@xxxxxxx>
---
include/linux/lockdep.h | 9 +-
kernel/locking/lockdep.c | 242 ++++++++++++++++++++++++++++++++-------
2 files changed, 208 insertions(+), 43 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 9421f028c26c..72b4d5bb409f 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -63,7 +63,8 @@ extern struct lock_class_key __lockdep_no_validate__;
#define LOCKSTAT_POINTS 4

/*
- * The lock-class itself:
+ * The lock-class itself. The order of the structure members matters.
+ * reinit_class() zeroes the key member and all subsequent members.
*/
struct lock_class {
/*
@@ -72,7 +73,9 @@ struct lock_class {
struct hlist_node hash_entry;

/*
- * global list of all lock-classes:
+ * Entry in all_lock_classes when in use. Entry in free_lock_classes
+ * when not in use. Instances that are being freed are on the
+ * zapped_classes list.
*/
struct list_head lock_entry;

@@ -106,7 +109,7 @@ struct lock_class {
unsigned long contention_point[LOCKSTAT_POINTS];
unsigned long contending_point[LOCKSTAT_POINTS];
#endif
-};
+} __no_randomize_layout;

#ifdef CONFIG_LOCK_STAT
struct lock_time {
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 92bdb187987f..ce8abd268727 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -134,8 +134,8 @@ static struct lock_list list_entries[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.
*/
unsigned long nr_lock_classes;
#ifndef CONFIG_DEBUG_LOCKDEP
@@ -277,11 +277,18 @@ 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. The zapped_classes list contains lock
+ * classes that are about to be freed but that may still be accessed by an RCU
+ * reader. 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(zapped_classes);
+static LIST_HEAD(free_lock_classes);
+static bool initialization_happened;
+static bool rcu_callback_scheduled;
+static struct rcu_head free_zapped_classes_rcu_head;

/*
* The lockdep classes are in a hash-table as well, for fast lookup:
@@ -735,6 +742,21 @@ static bool assign_lock_key(struct lockdep_map *lock)
return true;
}

+/*
+ * Initialize the lock_classes[] array elements and also the free_lock_classes
+ * list.
+ */
+static void init_data_structures(void)
+{
+ int i;
+
+ 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);
+ }
+}
+
/*
* 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
@@ -775,11 +797,14 @@ 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) {
+ /* Allocate a new lock class and add it to the hash. */
+ if (unlikely(!initialization_happened)) {
+ initialization_happened = true;
+ init_data_structures();
+ }
+ class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
+ lock_entry);
+ if (!class) {
if (!debug_locks_off_graph_unlock()) {
return NULL;
}
@@ -788,13 +813,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
@@ -804,7 +829,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
/*
* 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();
@@ -1845,6 +1870,13 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
struct lock_list this;
int ret;

+ if (WARN_ON_ONCE(!hlock_class(prev)->hash_entry.pprev) ||
+ WARN_ONCE(!hlock_class(next)->hash_entry.pprev,
+ KERN_INFO "Detected use-after-free of lock class %s\n",
+ 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
@@ -2236,17 +2268,14 @@ 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) {
debug_atomic_inc(chain_lookup_hits);
@@ -3338,6 +3367,9 @@ 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);

+ WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->hash_entry.pprev);
+ WARN_ON_ONCE(!hlock_class(hlock)->hash_entry.pprev);
+
if (!validate_chain(curr, lock, hlock, chain_head, chain_key))
return 0;

@@ -4126,11 +4158,93 @@ void lockdep_reset(void)
raw_local_irq_restore(flags);
}

+/* Must be called with the graph lock held. */
+static void remove_class_from_lock_chain(struct lock_chain *chain,
+ struct lock_class *class)
+{
+ u64 chain_key;
+ int i;
+
+#ifdef CONFIG_PROVE_LOCKING
+ for (i = chain->base; i < chain->base + chain->depth; i++) {
+ if (chain_hlocks[i] != class - lock_classes)
+ continue;
+ 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:
+ /*
+ * Note: calling hlist_del_rcu() from inside a
+ * hlist_for_each_entry_rcu() loop is safe.
+ */
+ if (chain->depth == 0) {
+ /* To do: decrease chain count. See also inc_chains(). */
+ hlist_del_rcu(&chain->entry);
+ return;
+ }
+ 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->chain_key == chain_key)
+ return;
+ hlist_del_rcu(&chain->entry);
+ chain->chain_key = chain_key;
+ hlist_add_head_rcu(&chain->entry, chainhashentry(chain_key));
+#endif
+}
+
+/* Must be called with the graph lock held. */
+static void remove_class_from_lock_chains(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(chain, class);
+ }
+ }
+}
+
+/*
+ * Move a class to the zapped_classes list if it is no longer in use. Must be
+ * called with the graph lock held.
+ */
+static void check_free_class(struct lock_class *class)
+{
+ /*
+ * If the list_del_rcu(&entry->entry) call made both lock order lists
+ * empty, remove @class from the all_lock_classes list and add it to
+ * the zapped_classes list.
+ */
+ if (class->hash_entry.pprev &&
+ list_empty(&class->locks_after) &&
+ list_empty(&class->locks_before)) {
+ list_move_tail(&class->lock_entry, &zapped_classes);
+ hlist_del_rcu(&class->hash_entry);
+ class->hash_entry.pprev = NULL;
+ }
+}
+
/*
* Remove all references to a lock class. The caller must hold the graph lock.
*/
static void zap_class(struct lock_class *class)
{
+ struct lock_class *links_to;
struct lock_list *entry;
int i;

@@ -4141,14 +4255,30 @@ static void zap_class(struct lock_class *class)
for (i = 0, entry = list_entries; i < nr_list_entries; i++, entry++) {
if (entry->class != class && entry->links_to != class)
continue;
+ links_to = entry->links_to;
+ WARN_ON_ONCE(entry->class == links_to);
list_del_rcu(&entry->entry);
}
- /*
- * Unhash the class and remove it from the all_lock_classes list:
- */
- hlist_del_rcu(&class->hash_entry);
- class->hash_entry.pprev = NULL;
- list_del(&class->lock_entry);
+ check_free_class(class);
+ WARN_ONCE(class->hash_entry.pprev,
+ KERN_INFO "%s() failed for class %s\n", __func__,
+ class->name);
+
+ remove_class_from_lock_chains(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)
@@ -4156,6 +4286,38 @@ static inline int within(const void *addr, void *start, unsigned long size)
return addr >= start && addr < start + size;
}

+/*
+ * Free all lock classes that are on the zapped_classes list. Called as an
+ * RCU callback function.
+ */
+static void free_zapped_classes(struct callback_head *ch)
+{
+ struct lock_class *class;
+ unsigned long flags;
+ int locked;
+
+ raw_local_irq_save(flags);
+ locked = graph_lock();
+ rcu_callback_scheduled = false;
+ list_for_each_entry(class, &zapped_classes, lock_entry) {
+ reinit_class(class);
+ nr_lock_classes--;
+ }
+ list_splice_init(&zapped_classes, &free_lock_classes);
+ if (locked)
+ graph_unlock();
+ raw_local_irq_restore(flags);
+}
+
+/* Must be called with the graph lock held. */
+static void schedule_free_zapped_classes(void)
+{
+ if (rcu_callback_scheduled)
+ return;
+ rcu_callback_scheduled = true;
+ call_rcu(&free_zapped_classes_rcu_head, free_zapped_classes);
+}
+
/*
* Used in module.c to remove lock classes from memory that is going to be
* freed; and possibly re-used by other modules.
@@ -4181,29 +4343,26 @@ void lockdep_free_key_range(void *start, unsigned long size)
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 (!class->hash_entry.pprev ||
+ (!within(class->key, start, size) &&
+ !within(class->name, start, size)))
+ continue;
+ zap_class(class);
}
}

+ schedule_free_zapped_classes();
+
if (locked)
graph_unlock();
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_sched();
-
- /*
- * 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.
+ * Do not wait for concurrent look_up_lock_class() calls. If any such
+ * concurrent call would return a pointer to one of the lock classes
+ * freed by this function then that means that there is a race in the
+ * code that calls look_up_lock_class(), namely concurrently accessing
+ * and freeing a synchronization object.
*/
}

@@ -4249,6 +4408,9 @@ void lockdep_reset_lock(struct lockdep_map *lock)
if (class)
zap_class(class);
}
+
+ schedule_free_zapped_classes();
+
/*
* Debug check: in the end all mapped classes should
* be gone.
--
2.20.0.rc2.403.gdbc3b29805-goog