linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Bart Van Assche <bvanassche@acm.org>
To: mingo@redhat.com
Cc: peterz@infradead.org, tj@kernel.org, longman@redhat.com,
	johannes.berg@intel.com, linux-kernel@vger.kernel.org,
	Bart Van Assche <bvanassche@acm.org>,
	Johannes Berg <johannes@sipsolutions.net>
Subject: [PATCH v3 19/24] locking/lockdep: Check data structure consistency
Date: Thu,  6 Dec 2018 17:11:43 -0800	[thread overview]
Message-ID: <20181207011148.251812-20-bvanassche@acm.org> (raw)
In-Reply-To: <20181207011148.251812-1-bvanassche@acm.org>

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

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Waiman Long <longman@redhat.com>
Cc: Johannes Berg <johannes@sipsolutions.net>
Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
 kernel/locking/lockdep.c | 146 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 146 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6f338f852f7e..78f14c151407 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.
@@ -744,6 +746,148 @@ 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, 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 chain->chain_key == chain_key;
+#else
+	return true;
+#endif
+}
+
+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.
+	 */
+	for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
+		if (test_bit(i, list_entries_being_freed))
+			continue;
+		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 (WARN_ON_ONCE(test_bit(i, list_entries_being_freed)))
+			return false;
+		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;
+		}
+	}
+
+	/* 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;
+}
+
 /*
  * Initialize the lock_classes[] array elements and also the free_lock_classes
  * list.
@@ -4309,6 +4453,8 @@ static void free_zapped_classes(struct callback_head *ch)
 	raw_local_irq_save(flags);
 	locked = graph_lock();
 	rcu_callback_scheduled = false;
+	if (check_data_structure_consistency)
+		WARN_ON_ONCE(!check_data_structures());
 	list_for_each_entry(class, &zapped_classes, lock_entry) {
 		reinit_class(class);
 		nr_lock_classes--;
-- 
2.20.0.rc2.403.gdbc3b29805-goog


  parent reply	other threads:[~2018-12-07  1:14 UTC|newest]

Thread overview: 49+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-07  1:11 [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 01/24] lockdep tests: Display compiler warning and error messages Bart Van Assche
2018-12-11 15:22   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 02/24] lockdep tests: Fix shellcheck warnings Bart Van Assche
2018-12-11 15:23   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 03/24] lockdep tests: Improve testing accuracy Bart Van Assche
2018-12-11 15:23   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 04/24] lockdep tests: Run lockdep tests a second time under Valgrind Bart Van Assche
2018-12-11 15:24   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 05/24] liblockdep: Rename "trywlock" into "trywrlock" Bart Van Assche
2018-12-11 15:24   ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-11 17:19   ` [PATCH v3 05/24] liblockdep: " Sasha Levin
2018-12-11 17:38     ` Bart Van Assche
2018-12-13 19:41       ` Sasha Levin
2018-12-07  1:11 ` [PATCH v3 06/24] liblockdep: Add dummy print_irqtrace_events() implementation Bart Van Assche
2018-12-11 15:25   ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 07/24] lockdep tests: Test the lockdep_reset_lock() implementation Bart Van Assche
2018-12-11 15:26   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 08/24] locking/lockdep: Declare local symbols static Bart Van Assche
2018-12-11 15:26   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 09/24] locking/lockdep: Inline __lockdep_init_map() Bart Van Assche
2018-12-11 15:27   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 10/24] locking/lockdep: Introduce lock_class_cache_is_registered() Bart Van Assche
2018-12-11 15:27   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 11/24] locking/lockdep: Remove a superfluous INIT_LIST_HEAD() statement Bart Van Assche
2018-12-11 15:28   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 12/24] locking/lockdep: Make concurrent lockdep_reset_lock() calls safe Bart Van Assche
2018-12-11 15:29   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 13/24] locking/lockdep: Stop using RCU primitives to access all_lock_classes Bart Van Assche
2018-12-11 15:29   ` [tip:locking/core] locking/lockdep: Stop using RCU primitives to access 'all_lock_classes' tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 14/24] locking/lockdep: Make zap_class() remove all matching lock order entries Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 15/24] locking/lockdep: Reorder struct lock_class members Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 16/24] locking/lockdep: Retain the class key and name while freeing a lock class Bart Van Assche
2018-12-07 10:21   ` Peter Zijlstra
2018-12-07 14:50     ` Waiman Long
2018-12-07 16:23       ` Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 17/24] locking/lockdep: Free lock classes that are no longer in use Bart Van Assche
2018-12-07 12:14   ` Peter Zijlstra
2018-12-07 16:27     ` Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 18/24] locking/lockdep: Reuse list entries " Bart Van Assche
2018-12-07  1:11 ` Bart Van Assche [this message]
2018-12-07  1:11 ` [PATCH v3 20/24] locking/lockdep: Introduce __lockdep_free_key_range() Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 21/24] locking/lockdep: Verify whether lock objects are small enough to be used as class keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 22/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 23/24] kernel/workqueue: Use dynamic lockdep keys for workqueues Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 24/24] lockdep tests: Test dynamic key registration Bart Van Assche
2018-12-07 12:23 ` [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Peter Zijlstra
2018-12-07 16:35   ` Bart Van Assche
2018-12-08 10:26     ` Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20181207011148.251812-20-bvanassche@acm.org \
    --to=bvanassche@acm.org \
    --cc=johannes.berg@intel.com \
    --cc=johannes@sipsolutions.net \
    --cc=linux-kernel@vger.kernel.org \
    --cc=longman@redhat.com \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=tj@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).