[PATCH 1/8] lockdep: Traverse adjacency lists directly in zap_class()

[Jim Cromie]

Lockdep's canonical graph representation is its per-class adjacency
lists (locks_after and locks_before). However, zap_class() operates on
a flat storage-layer projection of the graph: it scans the global
list_entries_in_use bitmap across the entire edge pool.

This global scan has a few defects:

0. Search Inefficiency:

On a typical booted laptop with ~2,000 lock classes and ~6,500 active
dependency list entries, zapping a single class forces 6,500+ table
inspections under graph_lock across 4 KB of bitmap. Zapping a batch of
classes during module unload multiplies this into tens of thousands of
global array iterations.

1. Projection maintenance: the bitmap must be kept up-to-date.
   given 0, its a net burden, but we still need the bitmap elsewhere.

2. Incompatible with Array Segmentation:

The loop relies on contiguous pointer arithmetic (list_entries + i) to
map bitmap indices back to entries. This completely breaks once
list_entries is segmented into dynamic 64 kB memblock slabs residing
on disjoint memory pages.

So just implement the adjacency check literally, per graph-theory.

Real-world lock classes have very short adjacency lists: 3..5 entries
on average for class->locks_after and class->locks_before, rarely
exceeding 15.

Directly walking these lists visits only ~10..15 nodes per zapped
class, replacing 6,500+ global table dereferences with a handful of
cacheline-local pointer hops (>99.8% reduction in loop iterations).

Note: We continue clearing bits in list_entries_in_use for now, as
alloc_list_entry() still queries the bitmap in this commit. The bitmap
itself is eliminated soon

Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
---
 kernel/locking/lockdep.c | 31 ++++++++++++++++++++++++-------
 1 file changed, 24 insertions(+), 7 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2d4c5bab5af8..6a4f21f3e9c8 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -6243,8 +6243,7 @@ static void remove_class_from_lock_chains(struct pending_free *pf,
  */
 static void zap_class(struct pending_free *pf, struct lock_class *class)
 {
-	struct lock_list *entry;
-	int i;
+	struct lock_list *entry, *tmp, *other, *other_tmp;
 
 	WARN_ON_ONCE(!class->key);
 
@@ -6252,11 +6251,29 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 	 * Remove all dependencies this lock is
 	 * involved in:
 	 */
-	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);
+	list_for_each_entry_safe(entry, tmp, &class->locks_after, entry) {
+		list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_before, entry) {
+			if (other->links_to == class) {
+				__clear_bit(other - list_entries, list_entries_in_use);
+				nr_list_entries--;
+				list_del_rcu(&other->entry);
+				break;
+			}
+		}
+		__clear_bit(entry - list_entries, list_entries_in_use);
+		nr_list_entries--;
+		list_del_rcu(&entry->entry);
+	}
+	list_for_each_entry_safe(entry, tmp, &class->locks_before, entry) {
+		list_for_each_entry_safe(other, other_tmp, &entry->links_to->locks_after, entry) {
+			if (other->links_to == class) {
+				__clear_bit(other - list_entries, list_entries_in_use);
+				nr_list_entries--;
+				list_del_rcu(&other->entry);
+				break;
+			}
+		}
+		__clear_bit(entry - list_entries, list_entries_in_use);
 		nr_list_entries--;
 		list_del_rcu(&entry->entry);
 	}

-- 
2.55.0