[PATCH 23/27] locking/lockdep: Check data structure consistency

[Bart Van Assche]

Debugging lockdep data structure inconsistencies is challenging. Add
disabled code that verifies data structure consistency at runtime.

Signed-off-by: Bart Van Assche <bvanassche@xxxxxxx>
---
 kernel/locking/lockdep.c | 142 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 288a2f6fd0ef..141bb0662ff5 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -72,6 +72,8 @@ module_param(lock_stat, int, 0644);
 #define lock_stat 0
 #endif
 
+static bool check_data_structure_consistency;
+
 /*
  * lockdep_lock: protects the lockdep graph, the hashes and the
  *               class/list/hash allocators.
@@ -736,6 +738,135 @@ static bool assign_lock_key(struct lockdep_map *lock)
 	return true;
 }
 
+/* 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, lock_order_entry) {
+		if (e->links_to != c) {
+			printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
+			       c->name ? : "(?)", 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)
+{
+	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 chain->chain_key == chain_key;
+}
+
+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 list entries that are in use occur in a class
+	 * lock list.
+	 */
+	list_for_each_entry(e, &all_list_entries, alloc_entry) {
+		if (!in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld is not in any class list; class %s <> %s\n",
+			       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.
+	 */
+	list_for_each_entry(e, &free_list_entries, alloc_entry) {
+		if (in_any_class_list(&e->lock_order_entry)) {
+			printk(KERN_INFO "list entry %ld occurs in a class list; class %s <> %s\n",
+			       e - list_entries,
+			       e->class && e->class->name ? e->class->name :
+			       "(?)",
+			       e->links_to && e->links_to->name ?
+			       e->links_to->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->locks_before.next)
+			continue;
+		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;
+	}
+
+	return true;
+}
+
 static void init_lists(void)
 {
 	int i;
@@ -4294,6 +4425,14 @@ static void free_zapped_classes(struct list_head *zapped_classes)
 	unsigned long flags;
 	int locked;
 
+	raw_local_irq_save(flags);
+	locked = graph_lock();
+	if (check_data_structure_consistency)
+		WARN_ON_ONCE(!check_data_structures());
+	if (locked)
+		graph_unlock();
+	raw_local_irq_restore(flags);
+
 	if (list_empty(zapped_classes))
 		return;
 
@@ -4314,6 +4453,9 @@ static void free_zapped_classes(struct list_head *zapped_classes)
 	if (locked)
 		graph_unlock();
 	raw_local_irq_restore(flags);
+
+	if (check_data_structure_consistency)
+		WARN_ON_ONCE(!check_data_structures());
 }
 
 /*
-- 
2.20.0.rc0.387.gc7a69e6b6c-goog