[PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[Jim Cromie]

Lockdep cannot rely upon any other subsystem that uses locks, so since
inception, its graph-db has been stored in static arrays, pinning ~10
MB in .bss. This is a hardcoded compromise between embedded and
enterprise hardware.

However, if it acts early, lockdep can pre-allocate a pool of slabs
from memblock_alloc(), enough for its lifetime of anticipated workloads.
Then it can allocate them as needed to provide new segments/slabs to
the graph-db.

With that idea, we:

0. Add lockdep_early_init() hook in start_kernel() right before
   mm_core_init() to grab a private pool of 64 KB slabs from memblock.

1. Add DECLARE_CHUNKED_ARRAY() to build 2D chunk pointer tables.
   Indexing uses a compile-time hybrid:
   - Power-of-2 tables (lock_chains @ 2,048/slab, chain_hlocks @ 32,768/slab)
     use single-cycle bit shifts (idx >> SHIFT) and masks (idx & MASK)
     for zero-overhead cache verification.
   - Non-power-of-2 structs (lock_classes @ 409/slab, list_entries @ 1,365/slab)
     use Granlund-Montgomery reciprocal divide to achieve >99.8% slab
     packing density, avoiding 1.75 MB of internal dead padding.

2. Deploy chunked arrays across the 5 graph-db tables:
   - lock_classes: struct lock_class (160 B) -> lock_class_chunk0 (409 / slab)
   - list_entries: struct lock_list  (48 B)  -> list_entries_chunk0 (1,365 / slab)
   - lock_chains:  struct lock_chain (32 B)  -> lock_chain_chunk0 (2,048 / slab)
   - chain_hlocks: u16               (2 B)   -> chain_hlock_chunk0 (32,768 / slab)
   - stack_trace:  unsigned long     (8 B)   -> stack_trace_chunk0 (8,192 / slab)
   Each static name##_chunk0 in .bss (~320 kB total) provisions the graph-db
   with initial storage to cover early boot until memblock is up.

3. Embed struct lock_class.class_idx and struct lock_chain.chain_idx to
   replace flat pointer arithmetic (ptr - base) with O(1) index queries
   across disjoint 2D slabs.

4. Dole slabs out on demand to the 5 consumers via an index bump under
   graph_lock (zero allocator locks, zero recursion risk).

5. Auto-tune the pool size based on RAM and accept boot overrides via
   lockdep_slabs=N and lockdep_headroom=M%.

6. At late_initcall, satisfy both constraints (slabs >= N and headroom
   >= M%), and return all unused excess slabs to the buddy allocator
   via free_reserved_page().

7. Expose pool usage and remaining headroom via /proc/lockdep_stats and
   log lifetime usage via a reboot notifier.

8. On debug_locks_off() or OOM, immediately sacrifice all dynamically
   claimed slabs back to the buddy allocator.

Static .bss Memory Savings (vmlinux x86_64 defconfig):

    Kernel                 .bss Section Size       Notes
    ----------------------------------------------------------------------
    Upstream (Static)      12.46 MB (13061164 B)   Fixed max-sized arrays
    Patched (Memblock)      2.30 MB ( 2410988 B)   5 * 64 kB Chunk 0s in .bss
    ----------------------------------------------------------------------
    Net Savings            -10.16 MB (81.5% reduction in .bss)

Memblock-Pool Elasticity & Buddy Return:

  [ 0.850318] lockdep: boot complete : 9/64 slabs used, 41 kept (355% headroom), 23 returned to buddy (1472 kB freed)

  That VM boot consumed 9 slabs (576 kB), keeps 41 slabs (2624 kB,
  355% headroom) for runtime growth, and returns 23 slabs (1472 kB) to
  buddy at late_initcall:

  The boot-args let user specify the reserved-slab-pool size:
    lockdep_slabs=N		# min ct of 64kb slabs kept
    lockdep_headroom=N%		# added % to boot-complete numbers, default is 100%

Workload Stress Performance & CPU Overheads (perf stat, 4 vCPUs):

    Benchmark     Metric          Upstream (Base)     Patched (Memblock)  Delta
    ---------------------------------------------------------------------------
    hackbench     Runtime             8.482 s             8.278 s        -2.40%
    hackbench     Cycles          52899510936         52033166458        -1.64%
    hackbench     Instructions    29008189069         31698626928        +9.27%
    netns         Runtime             9.704 s            13.321 s       +37.28%
    netns         Cycles           3941156282          5077381493       +28.83%
    netns         Instructions     2758079004          3008859260        +9.09%
    vfs           Runtime            10.544 s            10.608 s        +0.60%
    vfs           Cycles          48150692681         48840696114        +1.43%
    vfs           Instructions    32621052088         35448537908        +8.67%
    modstorm      Runtime             0.611 s             0.585 s        -4.17%
    modstorm      Cycles            512425082           514784953        +0.46%
    modstorm      Instructions      349890783           383054584        +9.48%

    Under heavy lock contention (hackbench), the power-of-2 fast-path on
    chain_hlocks and lock_chains brings total cycle consumption to parity
    with or slightly faster than upstream baseline (-1.64% cycles).

Workload specifics (virtme-ng, 4 vCPUs, 4 GB RAM):
- hackbench: hackbench -p -g 8 -l 1000
- netns:     40 netns add/del cycles with paired veth interfaces
- vfs:       8 parallel workers creating 200 dirs, files, symlinks + rm -rf
- modstorm:  10 sequential rounds of batch modprobe/rmmod (dummy loop null_blk brd tun)

What's Unchanged:
- All lockdep validation invariants, BFS graph algorithms, and deadlock
  detection logic are completely unmodified.
- RCU iteration semantics across lock classes and chains remain intact.
- /proc/lockdep and /proc/lockdep_stats formatting is fully preserved.

Series Structure:
- Patch 1: Optimize zap_class() to traverse adjacency lists directly
  rather than scanning the global bitmap.
- Patch 2: Add chunked array infrastructure and embedded indices.
- Patch 3: Pre-reserve early memblock slab pool for dynamic tables.
- Patch 4: Convert 5 graph arrays to chunked tables backed by slab pool.
- Patch 5: Fast-path power-of-2 tables with shift/mask indexing.
- Patch 6: Free unused reservation slabs to buddy allocator at late boot.
- Patch 7: Expose slab pool telemetry in /proc/lockdep_stats and initcalls.
- Patch 8: On debug_locks_off or OOM, recycle all slabs to buddy.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Jim Cromie (8):
      lockdep: Traverse adjacency lists directly in zap_class()
      lockdep: Add chunked array infrastructure and embedded indices
      lockdep: Pre-reserve early memblock slab pool for dynamic tables
      lockdep: Convert 5 graph arrays to chunked tables backed by slab pool
      lockdep: Fast-path power-of-2 tables with shift/mask indexing
      lockdep: Free unused reservation slabs to buddy allocator at late boot
      lockdep: Expose slab pool telemetry in /proc/lockdep_stats and initcalls
      lockdep: on debug_locks_off or OOM, recycle all slabs to buddy

 include/linux/lockdep.h            |   4 +-
 include/linux/lockdep_types.h      |   1 +
 init/main.c                        |   1 +
 kernel/locking/lockdep.c           | 951 ++++++++++++++++++++++++++++---------
 kernel/locking/lockdep_internals.h |  95 +++-
 kernel/locking/lockdep_proc.c      |  63 ++-
 6 files changed, 875 insertions(+), 240 deletions(-)
---
base-commit: 8d3ae59288f1e7d58d76558a6ee96d533bc5019f
change-id: 20260825-lockdep-memblock-v1-12c083225ef9

Best regards,
-- 
Jim Cromie <jim.cromie@gmail.com>

[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@gmail.com>
---
 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

[PATCH 2/8] lockdep: Add chunked array infrastructure and embedded indices

[Jim Cromie]

Lockdep's dependency graph has historically relied on flat static
arrays in .bss. To transition these tables to dynamically allocated
slabs without incurring division instructions, introduce the
DECLARE_CHUNKED_ARRAY() and DEFINE_CHUNKED_ARRAY() macros.

These macros construct 2-tier chunked arrays (Array-of-Arrays) indexed
via Granlund-Montgomery reciprocal divide (reciprocal_divide()),
mapping indices to (chunk, offset) tuples in constant time (~3 cycles).

Also embed class_idx into struct lock_class and chain_idx into struct
lock_chain to replace flat pointer arithmetic (ptr - base) with O(1)
index lookups across disjoint slab chunks.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 include/linux/lockdep.h            |  3 ++-
 include/linux/lockdep_types.h      |  1 +
 kernel/locking/lockdep_internals.h | 48 ++++++++++++++++++++++++++++++++++++--
 3 files changed, 49 insertions(+), 3 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 621566345406..4c96959d8ad7 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -77,7 +77,7 @@ struct lock_chain {
 	unsigned int			irq_context :  2,
 					depth       :  6,
 					base	    : 24;
-	/* 4 byte hole */
+	unsigned int			chain_idx;
 	struct hlist_node		entry;
 	u64				chain_key;
 };
@@ -85,6 +85,7 @@ struct lock_chain {
 /*
  * Initialization, self-test and debugging-output methods:
  */
+extern void lockdep_early_init(void);
 extern void lockdep_init(void);
 extern void lockdep_reset(void);
 extern void lockdep_reset_lock(struct lockdep_map *lock);
diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h
index eae115a26488..8acac0b59f69 100644
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -121,6 +121,7 @@ struct lock_class {
 
 	unsigned int			subclass;
 	unsigned int			dep_gen_id;
+	unsigned int			class_idx;
 
 	/*
 	 * IRQ/softirq usage tracking bits:
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 0e5e6ffe91a3..3d8bce0dc9f9 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -122,9 +122,53 @@ enum {
 #define MAX_LOCKDEP_CHAINS	(1UL << MAX_LOCKDEP_CHAINS_BITS)
 
 #define AVG_LOCKDEP_CHAIN_DEPTH		5
-#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS * AVG_LOCKDEP_CHAIN_DEPTH)
+#include <linux/reciprocal_div.h>
 
-extern struct lock_chain lock_chains[];
+#define LOCKDEP_SLAB_SIZE	(64 * 1024)
+#define LOCKDEP_MAX_SLABS	64
+
+/*
+ * Chunked Array Tables:
+ * Replaces flat monolithic BSS arrays with 2D chunk pointer matrices.
+ * Chunk 0 is statically allocated in BSS for early boot, while subsequent
+ * chunks are claimed from the memblock reservoir via lockdep_claim_slab().
+ * Indexing uses compile-time Granlund-Montgomery reciprocal divide
+ * (~3-cycle multiply+shift, zero division instructions).
+ */
+#define DECLARE_CHUNKED_ARRAY(name, type)					\
+	enum {									\
+		name##_PER_CHUNK = (LOCKDEP_SLAB_SIZE / sizeof(type)),		\
+	};									\
+	extern type * name##_chunks[LOCKDEP_MAX_SLABS];				\
+	extern const struct reciprocal_value name##_rv;				\
+	static __always_inline type *idx_to_##name(unsigned int idx)		\
+	{									\
+		unsigned int chunk = reciprocal_divide(idx, name##_rv);		\
+		unsigned int offset = idx - (chunk * name##_PER_CHUNK);		\
+		type *chunk_ptr;						\
+		if (unlikely(chunk >= LOCKDEP_MAX_SLABS))			\
+			return NULL;						\
+		/* Pairs with smp_store_release() when new chunk slabs are published */ \
+		chunk_ptr = smp_load_acquire(&name##_chunks[chunk]);		\
+		if (unlikely(!chunk_ptr))					\
+			return NULL;						\
+		return &chunk_ptr[offset];					\
+	}
+
+#define DEFINE_CHUNKED_ARRAY(name, type)					\
+	static type name##_chunk0[name##_PER_CHUNK];				\
+	type *name##_chunks[LOCKDEP_MAX_SLABS] = { name##_chunk0 };		\
+	static unsigned int nr_##name##_chunks = 1;				\
+	const struct reciprocal_value name##_rv =				\
+		RECIPROCAL_VALUE_INIT(name##_PER_CHUNK)
+
+struct lockdep_slab_usage {
+	unsigned int lock_classes;
+	unsigned int direct_deps;
+	unsigned int lock_chains;
+	unsigned int chain_hlocks;
+	unsigned int stack_traces;
+};
 
 #define LOCK_USAGE_CHARS (2*XXX_LOCK_USAGE_STATES + 1)
 

-- 
2.55.0

[PATCH 3/8] lockdep: Pre-reserve early memblock slab pool for dynamic tables

[Jim Cromie]

Lockdep cannot allocate memory dynamically during normal runtime because
it cannot recurse into allocator locks. However, before mm_core_init()
brings up the buddy allocator, lockdep can claim a contiguous pool of
64 KB slabs directly from early memblock.

Add lockdep_early_init() to start_kernel() right before mm_core_init()
to reserve a private pool of 64 KB slabs. Auto-tune the pool based on
physical RAM (2 MB on <512 MB systems, 4 MB default, 8 MB on >64 GB
servers) and accept overrides via lockdep_slabs=N and
lockdep_headroom=M%.

Provide lockdep_claim_slab() and lockdep_release_slab() to dole out and
recycle slabs under graph_lock without invoking external locks.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 init/main.c                        |   1 +
 kernel/locking/lockdep.c           | 131 +++++++++++++++++++++++++++++++++++++
 kernel/locking/lockdep_internals.h |   3 +-
 3 files changed, 134 insertions(+), 1 deletion(-)

diff --git a/init/main.c b/init/main.c
index e363232b428b..12280dfe1d11 100644
--- a/init/main.c
+++ b/init/main.c
@@ -1031,6 +1031,7 @@ void start_kernel(void)
 	vfs_caches_init_early();
 	sort_main_extable();
 	trap_init();
+	lockdep_early_init();
 	mm_core_init();
 	maple_tree_init();
 	poking_init();
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6a4f21f3e9c8..68d82e46cbf6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -58,12 +58,96 @@
 #include <linux/context_tracking.h>
 #include <linux/console.h>
 #include <linux/kasan.h>
+#include <linux/memblock.h>
 
 #include <asm/sections.h>
 
 #include "lockdep_internals.h"
 #include "lock_events.h"
 
+static void *lockdep_slabs[LOCKDEP_MAX_SLABS];
+static unsigned int lockdep_nr_slabs;
+static unsigned int lockdep_slabs_used;
+static struct lockdep_slab_usage ld_slabs;
+
+static unsigned int requested_lockdep_slabs;
+static unsigned int requested_lockdep_headroom_pct = 100; /* default 100% headroom */
+static bool lockdep_headroom_specified;
+static bool lockdep_disabled_early;
+
+static int __init setup_lockdep_slabs(char *str)
+{
+	unsigned long val;
+
+	if (!str)
+		return -EINVAL;
+
+	if (!strcmp(str, "off") || !strcmp(str, "0")) {
+		lockdep_disabled_early = true;
+		return 0;
+	}
+
+	if (kstrtoul(str, 0, &val))
+		return -EINVAL;
+
+	if (val > 10000) {
+		pr_warn("lockdep: ignoring unrealistic lockdep_slabs=%lu\n",
+			val);
+		return -EINVAL;
+	}
+
+	requested_lockdep_slabs = clamp_t(unsigned int, val, 2, LOCKDEP_MAX_SLABS);
+	return 0;
+}
+early_param("lockdep_slabs", setup_lockdep_slabs);
+
+static int __init setup_lockdep_headroom(char *str)
+{
+	unsigned long val;
+
+	if (!str || kstrtoul(str, 0, &val))
+		return -EINVAL;
+
+	requested_lockdep_headroom_pct = clamp_t(unsigned int, val, 10, 900);
+	lockdep_headroom_specified = true;
+	return 0;
+}
+early_param("lockdep_headroom", setup_lockdep_headroom);
+
+static void *lockdep_free_slabs[LOCKDEP_MAX_SLABS];
+static unsigned int lockdep_nr_free_slabs;
+
+/*
+ * Claim a 64KB slab from the pre-allocated memblock reservoir.
+ * Must be called with graph_lock held. Completely lockless and deadlock-free.
+ */
+static void *lockdep_claim_slab(unsigned int *table_counter)
+{
+	void *slab;
+
+	if (lockdep_nr_free_slabs > 0)
+		slab = lockdep_free_slabs[--lockdep_nr_free_slabs];
+	else if (lockdep_slabs_used < lockdep_nr_slabs)
+		slab = lockdep_slabs[lockdep_slabs_used++];
+	else
+		return NULL;
+
+	if (table_counter)
+		(*table_counter)++;
+
+	return slab;
+}
+
+static void lockdep_release_slab(void *slab, unsigned int *table_counter)
+{
+	if (!slab || lockdep_nr_free_slabs >= LOCKDEP_MAX_SLABS)
+		return;
+
+	lockdep_free_slabs[lockdep_nr_free_slabs++] = slab;
+	if (table_counter && *table_counter > 0)
+		(*table_counter)--;
+}
+
 #include <trace/events/lock.h>
 
 #ifdef CONFIG_PROVE_LOCKING
@@ -6646,6 +6730,53 @@ void lockdep_unregister_key(struct lock_class_key *key)
 }
 EXPORT_SYMBOL_GPL(lockdep_unregister_key);
 
+void __init lockdep_early_init(void)
+{
+	unsigned int nr_slabs, i;
+	phys_addr_t phys_mem;
+	size_t slab_bytes;
+	void *pool;
+
+	if (lockdep_disabled_early) {
+		pr_info("lockdep: disabled by early boot parameter, 0 bytes reserved\n");
+		return;
+	}
+
+	phys_mem = memblock_phys_mem_size();
+
+	/* Auto-tune based on physical memory and CPU count */
+	if (phys_mem && phys_mem < (512ULL << 20))
+		nr_slabs = 32;   /* 2 MB on small systems (<512MB RAM) */
+	else if (num_possible_cpus() >= 64 || phys_mem > (64ULL << 30))
+		nr_slabs = 128;  /* 8 MB on large servers (>64GB RAM or >64 CPUs) */
+	else
+		nr_slabs = LOCKDEP_DEFAULT_SLABS; /* 64 slabs = 4 MB default */
+
+	/* Ensure initial reservation satisfies requested floor or headroom */
+	if (requested_lockdep_slabs > nr_slabs)
+		nr_slabs = requested_lockdep_slabs;
+
+	if (lockdep_headroom_specified && requested_lockdep_headroom_pct > 100)
+		nr_slabs = (nr_slabs * (100 + requested_lockdep_headroom_pct)) / 100;
+
+	nr_slabs = clamp_t(unsigned int, nr_slabs, 8, LOCKDEP_MAX_SLABS);
+
+	slab_bytes = (size_t)nr_slabs * LOCKDEP_SLAB_SIZE;
+	pool = memblock_alloc(slab_bytes, PAGE_SIZE);
+	if (!pool) {
+		pr_err("lockdep: failed to allocate %u slabs (%zu KB) from memblock\n",
+		       nr_slabs, slab_bytes / 1024);
+		return;
+	}
+
+	for (i = 0; i < nr_slabs; i++)
+		lockdep_slabs[i] = (char *)pool + (i * LOCKDEP_SLAB_SIZE);
+
+	lockdep_nr_slabs = nr_slabs;
+	pr_info("lockdep: reserved %u slabs (%zu KB) from memblock\n",
+		nr_slabs, slab_bytes / 1024);
+}
+
 void __init lockdep_init(void)
 {
 	pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 3d8bce0dc9f9..3344361a1c3b 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -125,7 +125,8 @@ enum {
 #include <linux/reciprocal_div.h>
 
 #define LOCKDEP_SLAB_SIZE	(64 * 1024)
-#define LOCKDEP_MAX_SLABS	64
+#define LOCKDEP_MAX_SLABS	512
+#define LOCKDEP_DEFAULT_SLABS	64
 
 /*
  * Chunked Array Tables:

-- 
2.55.0

[PATCH 4/8] lockdep: Convert 5 graph arrays to chunked tables backed by slab pool

[Jim Cromie]

Replace the monolithic static .bss tables for lock_classes, list_entries,
lock_chains, chain_hlocks, and stack_trace with 2D chunked arrays
(DECLARE_CHUNKED_ARRAY) backed by the early memblock slab pool.

Retain 1 static chunk (Chunk 0) in .bss per consumer (~320 kB total) to
cover early bootstrap locking before memblock is initialized:
- lock_classes: 409 items in Chunk 0 (160 B each)
- list_entries: 1,365 items in Chunk 0 (48 B each)
- lock_chains:  2,048 items in Chunk 0 (32 B each)
- chain_hlocks: 32,768 items in Chunk 0 (2 B each)
- stack_trace:  8,192 items in Chunk 0 (8 B each)

Update allocators (alloc_lock_chain(), alloc_chain_hlocks(),
alloc_list_entry(), save_trace()) to claim new 64 KB slabs dynamically
from the memblock reservoir under graph_lock when chunk capacity is
exhausted.

Replace flat array pointer arithmetic with embedded struct indices
(class->class_idx and chain->chain_idx).

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 include/linux/lockdep.h            |   1 +
 include/linux/lockdep_types.h      |   2 +-
 kernel/locking/lockdep.c           | 600 ++++++++++++++++++++++++-------------
 kernel/locking/lockdep_internals.h |  63 ++--
 4 files changed, 436 insertions(+), 230 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 4c96959d8ad7..0ebb9a3e1bea 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -340,6 +340,7 @@ static inline void lockdep_set_selftest_task(struct task_struct *task)
 # define lock_set_class(l, n, key, s, i)	do { (void)(key); } while (0)
 # define lock_set_novalidate_class(l, n, i)	do { } while (0)
 # define lock_set_subclass(l, s, i)		do { } while (0)
+# define lockdep_early_init()			do { } while (0)
 # define lockdep_init()				do { } while (0)
 # define lockdep_init_map_type(lock, name, key, sub, inner, outer, type) \
 		do { (void)(name); (void)(key); } while (0)
diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h
index 8acac0b59f69..fa0dcf3c3f70 100644
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -114,6 +114,7 @@ struct lock_class {
 	 * "backward" graph nodes.
 	 */
 	struct list_head		locks_after, locks_before;
+	unsigned int			class_idx;
 
 	const struct lockdep_subclass_key *key;
 	lock_cmp_fn			cmp_fn;
@@ -121,7 +122,6 @@ struct lock_class {
 
 	unsigned int			subclass;
 	unsigned int			dep_gen_id;
-	unsigned int			class_idx;
 
 	/*
 	 * IRQ/softirq usage tracking bits:
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 68d82e46cbf6..1c8db52af1ac 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -58,7 +58,9 @@
 #include <linux/context_tracking.h>
 #include <linux/console.h>
 #include <linux/kasan.h>
+#include <linux/mm.h>
 #include <linux/memblock.h>
+#include <linux/reboot.h>
 
 #include <asm/sections.h>
 
@@ -148,6 +150,28 @@ static void lockdep_release_slab(void *slab, unsigned int *table_counter)
 		(*table_counter)--;
 }
 
+void lockdep_get_slab_stats(struct lockdep_slab_stats *st)
+{
+	st->total_slabs = lockdep_nr_slabs;
+	st->used_slabs = lockdep_slabs_used - lockdep_nr_free_slabs;
+	st->usage = ld_slabs;
+}
+
+#define BOOTSTRAP_LOCKDEP_ENTRIES 1024UL
+
+static struct lock_list list_entries[BOOTSTRAP_LOCKDEP_ENTRIES];
+static struct lock_list *list_entries_freelist;
+static struct lock_list *list_entries_cur = list_entries;
+static unsigned int list_entries_remaining = BOOTSTRAP_LOCKDEP_ENTRIES;
+
+static inline void free_list_entry(struct lock_list *entry)
+{
+	if (!entry)
+		return;
+	*(void **)entry = list_entries_freelist;
+	list_entries_freelist = entry;
+}
+
 #include <trace/events/lock.h>
 
 #ifdef CONFIG_PROVE_LOCKING
@@ -289,8 +313,6 @@ 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.
@@ -305,29 +327,25 @@ unsigned long nr_lock_classes;
 unsigned long nr_zapped_classes;
 unsigned long nr_dynamic_keys;
 unsigned long max_lock_class_idx;
-struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
+
+DEFINE_CHUNKED_ARRAY(lock_class, struct lock_class);
+
+static void lockdep_print_watermarks(const char *bug_msg);
+
 DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
 
 static inline struct lock_class *hlock_class(struct held_lock *hlock)
 {
 	unsigned int class_idx = hlock->class_idx;
 
-	/* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
 	barrier();
 
 	if (!test_bit(class_idx, lock_classes_in_use)) {
-		/*
-		 * Someone passed in garbage, we give up.
-		 */
 		DEBUG_LOCKS_WARN_ON(1);
 		return NULL;
 	}
 
-	/*
-	 * At this point, if the passed hlock->class_idx is still garbage,
-	 * we just have to live with it
-	 */
-	return lock_classes + class_idx;
+	return idx_to_lock_class(class_idx);
 }
 
 #ifdef CONFIG_LOCK_STAT
@@ -388,7 +406,7 @@ void lock_stats(struct lock_class *class, struct lock_class_stats *stats)
 	memset(stats, 0, sizeof(struct lock_class_stats));
 	for_each_possible_cpu(cpu) {
 		struct lock_class_stats *pcs =
-			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
+			&per_cpu(cpu_lock_stats, cpu)[class->class_idx];
 
 		for (i = 0; i < ARRAY_SIZE(stats->contention_point); i++)
 			stats->contention_point[i] += pcs->contention_point[i];
@@ -413,7 +431,7 @@ void clear_lock_stats(struct lock_class *class)
 
 	for_each_possible_cpu(cpu) {
 		struct lock_class_stats *cpu_stats =
-			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
+			&per_cpu(cpu_lock_stats, cpu)[class->class_idx];
 
 		memset(cpu_stats, 0, sizeof(struct lock_class_stats));
 	}
@@ -423,7 +441,7 @@ void clear_lock_stats(struct lock_class *class)
 
 static struct lock_class_stats *get_lock_stats(struct lock_class *class)
 {
-	return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
+	return &this_cpu_ptr(cpu_lock_stats)[class->class_idx];
 }
 
 static void lock_release_holdtime(struct held_lock *hlock)
@@ -555,9 +573,26 @@ static __always_inline void lockdep_recursion_finish(void)
 		__this_cpu_write(lockdep_recursion, 0);
 }
 
+static void lockdep_selftest_trace_start(void);
+static void lockdep_selftest_trace_finish(void);
+static void lockdep_report_stage(const char *domain, const char *stage_name);
+
 void lockdep_set_selftest_task(struct task_struct *task)
 {
-	lockdep_selftest_task_struct = task;
+	unsigned long flags;
+
+	if (task) {
+		lockdep_selftest_task_struct = task;
+		lockdep_selftest_trace_start();
+		return;
+	}
+
+	lockdep_selftest_task_struct = NULL;
+	raw_local_irq_save(flags);
+	lockdep_lock();
+	lockdep_selftest_trace_finish();
+	lockdep_unlock();
+	raw_local_irq_restore(flags);
 }
 
 /*
@@ -622,6 +657,7 @@ unsigned long nr_stack_trace_entries;
  * @nr_entries:	Number of entries in @entries.
  * @entries:	Actual stack backtrace.
  */
+#define STACK_TRACE_HASH_SIZE	(1 << CONFIG_LOCKDEP_STACK_TRACE_HASH_BITS)
 struct lock_trace {
 	struct hlist_node	hash_entry;
 	u32			hash;
@@ -630,17 +666,80 @@ struct lock_trace {
 };
 #define LOCK_TRACE_SIZE_IN_LONGS				\
 	(sizeof(struct lock_trace) / sizeof(unsigned long))
-/*
- * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
- */
-static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
+#define BOOTSTRAP_STACK_TRACE_ENTRIES 4096UL
+#define MAX_LOCKDEP_TRACE_DEPTH 48
+
+static unsigned long stack_trace[BOOTSTRAP_STACK_TRACE_ENTRIES];
+static unsigned long *trace_free_ptr = stack_trace;
+static size_t trace_remaining_longs = BOOTSTRAP_STACK_TRACE_ENTRIES;
+
+static void *trace_slabs[LOCKDEP_MAX_SLABS];
+static unsigned int nr_trace_slabs;
+
 static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE];
 
-static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2)
+struct lockdep_selftest_snap {
+	unsigned int nr_trace_slabs;
+	unsigned long *trace_free_ptr;
+	size_t trace_remaining_longs;
+	unsigned long nr_trace_entries;
+};
+static struct lockdep_selftest_snap selftest_snap;
+
+static void lockdep_selftest_trace_start(void)
+{
+	selftest_snap.nr_trace_slabs = nr_trace_slabs;
+	selftest_snap.trace_free_ptr = trace_free_ptr;
+	selftest_snap.trace_remaining_longs = trace_remaining_longs;
+	selftest_snap.nr_trace_entries = nr_stack_trace_entries;
+
+	lockdep_report_stage("selftest", "pre-test");
+}
+
+static void lockdep_selftest_trace_finish(void)
+{
+	unsigned int reclaimed_slabs = 0;
+	unsigned int i;
+
+	if (!debug_locks || !selftest_snap.trace_free_ptr)
+		return;
+
+	lockdep_report_stage("selftest", "peak-test");
+
+	for (i = selftest_snap.nr_trace_slabs; i < nr_trace_slabs; i++) {
+		lockdep_release_slab(trace_slabs[i], &ld_slabs.stack_traces);
+		trace_slabs[i] = NULL;
+		reclaimed_slabs++;
+	}
+	nr_trace_slabs = selftest_snap.nr_trace_slabs;
+	trace_free_ptr = selftest_snap.trace_free_ptr;
+	trace_remaining_longs = selftest_snap.trace_remaining_longs;
+	nr_stack_trace_entries = selftest_snap.nr_trace_entries;
+	memset(stack_trace_hash, 0, sizeof(stack_trace_hash));
+
+	if (reclaimed_slabs)
+		pr_info("lockdep: selftest complete : recycled %u trace slabs (%u kB) to pool\n",
+			reclaimed_slabs, (reclaimed_slabs * LOCKDEP_SLAB_SIZE) / 1024);
+
+	lockdep_report_stage("selftest", "post-test");
+}
+
+static inline void lock_trace_discard(struct lock_trace *trace, unsigned int max_entries)
+{
+	size_t needed_longs = LOCK_TRACE_SIZE_IN_LONGS + max_entries;
+
+	if ((unsigned long *)trace + needed_longs == trace_free_ptr) {
+		trace_free_ptr = (unsigned long *)trace;
+		trace_remaining_longs += needed_longs;
+	}
+}
+
+static inline void lock_trace_trim(struct lock_trace *trace, unsigned int unused_entries)
 {
-	return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries &&
-		memcmp(t1->entries, t2->entries,
-		       t1->nr_entries * sizeof(t1->entries[0])) == 0;
+	if (unused_entries && trace_free_ptr) {
+		trace_free_ptr -= unused_entries;
+		trace_remaining_longs += unused_entries;
+	}
 }
 
 static struct lock_trace *save_trace(void)
@@ -648,40 +747,59 @@ static struct lock_trace *save_trace(void)
 	struct lock_trace *trace, *t2;
 	struct hlist_head *hash_head;
 	u32 hash;
-	int max_entries;
+	size_t needed_longs = LOCK_TRACE_SIZE_IN_LONGS + MAX_LOCKDEP_TRACE_DEPTH;
 
 	BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE);
-	BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES);
-
-	trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries);
-	max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries -
-		LOCK_TRACE_SIZE_IN_LONGS;
 
-	if (max_entries <= 0) {
-		if (!debug_locks_off_graph_unlock())
-			return NULL;
+	if (trace_remaining_longs < needed_longs) {
+		unsigned long *slab = lockdep_claim_slab(&ld_slabs.stack_traces);
 
-		nbcon_cpu_emergency_enter();
-		print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
-		dump_stack();
-		nbcon_cpu_emergency_exit();
+		if (unlikely(!slab))
+			goto out_fail;
 
-		return NULL;
+		trace_slabs[nr_trace_slabs++] = slab;
+		trace_free_ptr = slab;
+		trace_remaining_longs = LOCKDEP_SLAB_SIZE / sizeof(unsigned long);
 	}
-	trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3);
 
-	hash = jhash(trace->entries, trace->nr_entries *
-		     sizeof(trace->entries[0]), 0);
+	trace = (struct lock_trace *)trace_free_ptr;
+	trace_free_ptr += needed_longs;
+	trace_remaining_longs -= needed_longs;
+
+	trace->nr_entries = stack_trace_save(trace->entries, MAX_LOCKDEP_TRACE_DEPTH, 3);
+	hash = jhash(trace->entries, trace->nr_entries * sizeof(unsigned long), 0);
 	trace->hash = hash;
 	hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1));
+
 	hlist_for_each_entry(t2, hash_head, hash_entry) {
-		if (traces_identical(trace, t2))
+		if (t2->hash == hash && t2->nr_entries == trace->nr_entries &&
+		    !memcmp(t2->entries, trace->entries,
+			    trace->nr_entries * sizeof(unsigned long))) {
+			/* Duplicate hit: rewind speculative allocation */
+			lock_trace_discard(trace, MAX_LOCKDEP_TRACE_DEPTH);
 			return t2;
+		}
 	}
-	nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
+
+	/* Novel trace: trim unused tail frames */
+	if (trace->nr_entries < MAX_LOCKDEP_TRACE_DEPTH)
+		lock_trace_trim(trace, MAX_LOCKDEP_TRACE_DEPTH - trace->nr_entries);
+
 	hlist_add_head(&trace->hash_entry, hash_head);
+	nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
 
 	return trace;
+
+out_fail:
+	if (!debug_locks_off_graph_unlock())
+		return NULL;
+
+	nbcon_cpu_emergency_enter();
+	lockdep_print_watermarks("BUG: lockdep stack trace allocation failed!");
+	dump_stack();
+	nbcon_cpu_emergency_exit();
+
+	return NULL;
 }
 
 /* Return the number of stack traces in the stack_trace[] array. */
@@ -1075,46 +1193,15 @@ static bool assign_lock_key(struct lockdep_map *lock)
 
 #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",
+			pr_info("class %s: mismatch for lock entry %p; class %s <> %s",
 			       c->name ? : "(?)",
-			       (unsigned long)(e - list_entries),
+			       e,
 			       e->links_to && e->links_to->name ?
 			       e->links_to->name : "(?)",
 			       e->class && e->class->name ? e->class->name :
@@ -1126,7 +1213,8 @@ static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
 }
 
 #ifdef CONFIG_PROVE_LOCKING
-static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
+static u16 get_chain_hlock(unsigned int offset);
+static void set_chain_hlock(unsigned int offset, u16 val);
 #endif
 
 static bool check_lock_chain_key(struct lock_chain *chain)
@@ -1136,14 +1224,14 @@ static bool check_lock_chain_key(struct lock_chain *chain)
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++)
-		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
+		chain_key = iterate_chain_key(chain_key, get_chain_hlock(i));
 	/*
 	 * 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_idx,
 		       (unsigned long long)chain->chain_key,
 		       (unsigned long long)chain_key);
 		return false;
@@ -1152,42 +1240,15 @@ static bool check_lock_chain_key(struct lock_chain *chain)
 	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];
+	list_for_each_entry(class, &all_lock_classes, lock_entry) {
 		if (!class_lock_list_valid(class, &class->locks_before))
 			return false;
 		if (!class_lock_list_valid(class, &class->locks_after))
@@ -1203,38 +1264,6 @@ static bool __check_data_structures(void)
 		}
 	}
 
-	/*
-	 * 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;
 }
 
@@ -1286,11 +1315,15 @@ static void init_data_structures_once(void)
 	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);
+	for (i = 0; i < lock_class_PER_CHUNK; i++) {
+		struct lock_class *class = &lock_class_chunk0[i];
+
+		class->class_idx = i;
+		list_add_tail(&class->lock_entry, &free_lock_classes);
+		INIT_LIST_HEAD(&class->locks_after);
+		INIT_LIST_HEAD(&class->locks_before);
 	}
+
 	init_chain_block_buckets();
 }
 
@@ -1371,7 +1404,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	struct lockdep_subclass_key *key;
 	struct hlist_head *hash_head;
 	struct lock_class *class;
-	int idx;
+	int idx, i;
 
 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
@@ -1406,19 +1439,43 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	/* 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 (nr_lock_class_chunks < LOCKDEP_MAX_SLABS) {
+			struct lock_class *chunk;
+			unsigned int chunk_idx = nr_lock_class_chunks;
+
+			chunk = lockdep_claim_slab(&ld_slabs.lock_classes);
+			if (chunk) {
+				memset(chunk, 0, sizeof(struct lock_class) * lock_class_PER_CHUNK);
+				for (i = 0; i < lock_class_PER_CHUNK; i++) {
+					struct lock_class *c = &chunk[i];
+
+					c->class_idx = chunk_idx * lock_class_PER_CHUNK + i;
+					INIT_LIST_HEAD(&c->locks_after);
+					INIT_LIST_HEAD(&c->locks_before);
+					list_add_tail(&c->lock_entry, &free_lock_classes);
+				}
+				/* Pairs with smp_load_acquire() in idx_to_lock_class() */
+				smp_store_release(&lock_class_chunks[chunk_idx], chunk);
+				nr_lock_class_chunks++;
+				class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
+								 lock_entry);
+			}
+		}
+	}
 	if (!class) {
 		if (!debug_locks_off_graph_unlock()) {
 			return NULL;
 		}
 
 		nbcon_cpu_emergency_enter();
-		print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
+		lockdep_print_watermarks("BUG: MAX_LOCKDEP_KEYS too low!");
 		dump_stack();
 		nbcon_cpu_emergency_exit();
 		return NULL;
 	}
 	nr_lock_classes++;
-	__set_bit(class - lock_classes, lock_classes_in_use);
+	__set_bit(class->class_idx, lock_classes_in_use);
 	debug_atomic_inc(nr_unused_locks);
 	class->key = key;
 	class->name = lock->name;
@@ -1439,7 +1496,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	 * of classes.
 	 */
 	list_move_tail(&class->lock_entry, &all_lock_classes);
-	idx = class - lock_classes;
+	idx = class->class_idx;
 	if (idx > max_lock_class_idx)
 		max_lock_class_idx = idx;
 
@@ -1484,22 +1541,39 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
  */
 static struct lock_list *alloc_list_entry(void)
 {
-	int idx = find_first_zero_bit(list_entries_in_use,
-				      ARRAY_SIZE(list_entries));
+	struct lock_list *entry;
 
-	if (idx >= ARRAY_SIZE(list_entries)) {
-		if (!debug_locks_off_graph_unlock())
-			return NULL;
+	if (list_entries_freelist) {
+		entry = list_entries_freelist;
+		list_entries_freelist = *(void **)entry;
+	} else if (list_entries_remaining > 0) {
+		entry = list_entries_cur++;
+		list_entries_remaining--;
+	} else {
+		struct lock_list *slab = lockdep_claim_slab(&ld_slabs.direct_deps);
 
-		nbcon_cpu_emergency_enter();
-		print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
-		dump_stack();
-		nbcon_cpu_emergency_exit();
-		return NULL;
+		if (unlikely(!slab))
+			goto out_fail;
+
+		list_entries_cur = slab;
+		list_entries_remaining = LOCKDEP_SLAB_SIZE / sizeof(struct lock_list);
+		entry = list_entries_cur++;
+		list_entries_remaining--;
 	}
+
+	memset(entry, 0, sizeof(*entry));
 	nr_list_entries++;
-	__set_bit(idx, list_entries_in_use);
-	return list_entries + idx;
+	return entry;
+
+out_fail:
+	if (!debug_locks_off_graph_unlock())
+		return NULL;
+
+	nbcon_cpu_emergency_enter();
+	print_lockdep_off("BUG: lockdep pool exhausted!");
+	dump_stack();
+	nbcon_cpu_emergency_exit();
+	return NULL;
 }
 
 /*
@@ -3407,9 +3481,32 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 	return 0;
 }
 
-struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
+DEFINE_CHUNKED_ARRAY(lock_chain, struct lock_chain);
 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
-static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
+
+DEFINE_CHUNKED_ARRAY(chain_hlock, u16);
+static unsigned int total_chain_hlocks_capacity = chain_hlock_PER_CHUNK;
+
+unsigned int chain_hlocks_used(void)
+{
+	return total_chain_hlocks_capacity - (nr_free_chain_hlocks + nr_lost_chain_hlocks);
+}
+
+static inline u16 get_chain_hlock(unsigned int offset)
+{
+	u16 *p = idx_to_chain_hlock(offset);
+
+	return p ? *p : 0;
+}
+
+static inline void set_chain_hlock(unsigned int offset, u16 val)
+{
+	u16 *p = idx_to_chain_hlock(offset);
+
+	if (p)
+		*p = val;
+}
+
 unsigned long nr_zapped_lock_chains;
 unsigned int nr_free_chain_hlocks;	/* Free chain_hlocks in buckets */
 unsigned int nr_lost_chain_hlocks;	/* Lost chain_hlocks */
@@ -3459,7 +3556,7 @@ static inline int size_to_bucket(int size)
  */
 static inline int chain_block_next(int offset)
 {
-	int next = chain_hlocks[offset];
+	int next = get_chain_hlock(offset);
 
 	WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG));
 
@@ -3468,7 +3565,7 @@ static inline int chain_block_next(int offset)
 
 	next &= ~CHAIN_BLK_FLAG;
 	next <<= 16;
-	next |= chain_hlocks[offset + 1];
+	next |= get_chain_hlock(offset + 1);
 
 	return next;
 }
@@ -3478,17 +3575,17 @@ static inline int chain_block_next(int offset)
  */
 static inline int chain_block_size(int offset)
 {
-	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
+	return (get_chain_hlock(offset + 2) << 16) | get_chain_hlock(offset + 3);
 }
 
 static inline void init_chain_block(int offset, int next, int bucket, int size)
 {
-	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
-	chain_hlocks[offset + 1] = (u16)next;
+	set_chain_hlock(offset, (next >> 16) | CHAIN_BLK_FLAG);
+	set_chain_hlock(offset + 1, (u16)next);
 
 	if (size && !bucket) {
-		chain_hlocks[offset + 2] = size >> 16;
-		chain_hlocks[offset + 3] = (u16)size;
+		set_chain_hlock(offset + 2, size >> 16);
+		set_chain_hlock(offset + 3, (u16)size);
 	}
 }
 
@@ -3563,7 +3660,7 @@ static void init_chain_block_buckets(void)
 	for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
 		chain_block_buckets[i] = -1;
 
-	add_chain_block(0, ARRAY_SIZE(chain_hlocks));
+	add_chain_block(0, chain_hlock_PER_CHUNK);
 }
 
 /*
@@ -3584,14 +3681,33 @@ static int alloc_chain_hlocks(int req)
 
 	init_data_structures_once();
 
-	if (nr_free_chain_hlocks < req)
-		return -1;
-
 	/*
 	 * We require a minimum of 2 (u16) entries to encode a freelist
 	 * 'pointer'.
 	 */
 	req = max(req, 2);
+
+retry:
+	if (nr_free_chain_hlocks < req) {
+		if (nr_chain_hlock_chunks < LOCKDEP_MAX_SLABS) {
+			unsigned int chunk_idx = nr_chain_hlock_chunks;
+			unsigned int base_offset = chunk_idx * chain_hlock_PER_CHUNK;
+			u16 *chunk;
+
+			chunk = lockdep_claim_slab(&ld_slabs.chain_hlocks);
+			if (chunk) {
+				memset(chunk, 0, sizeof(u16) * chain_hlock_PER_CHUNK);
+				/* Pairs with smp_load_acquire() in idx_to_chain_hlock() */
+				smp_store_release(&chain_hlock_chunks[chunk_idx], chunk);
+				nr_chain_hlock_chunks++;
+				total_chain_hlocks_capacity += chain_hlock_PER_CHUNK;
+				add_chain_block(base_offset, chain_hlock_PER_CHUNK);
+			}
+		}
+		if (nr_free_chain_hlocks < req)
+			return -1;
+	}
+
 	bucket = size_to_bucket(req);
 	curr = chain_block_buckets[bucket];
 
@@ -3632,6 +3748,24 @@ static int alloc_chain_hlocks(int req)
 		return curr;
 	}
 
+	/* If fragmented and chunks remain, expand with a new chunk */
+	if (nr_chain_hlock_chunks < LOCKDEP_MAX_SLABS) {
+		unsigned int chunk_idx = nr_chain_hlock_chunks;
+		unsigned int base_offset = chunk_idx * chain_hlock_PER_CHUNK;
+		u16 *chunk;
+
+		chunk = lockdep_claim_slab(&ld_slabs.chain_hlocks);
+		if (chunk) {
+			memset(chunk, 0, sizeof(u16) * chain_hlock_PER_CHUNK);
+			/* Pairs with smp_load_acquire() in idx_to_chain_hlock() */
+			smp_store_release(&chain_hlock_chunks[chunk_idx], chunk);
+			nr_chain_hlock_chunks++;
+			total_chain_hlocks_capacity += chain_hlock_PER_CHUNK;
+			add_chain_block(base_offset, chain_hlock_PER_CHUNK);
+			goto retry;
+		}
+	}
+
 	return -1;
 }
 
@@ -3642,10 +3776,10 @@ static inline void free_chain_hlocks(int base, int size)
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 {
-	u16 chain_hlock = chain_hlocks[chain->base + i];
+	u16 chain_hlock = get_chain_hlock(chain->base + i);
 	unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
 
-	return lock_classes + class_idx;
+	return idx_to_lock_class(class_idx);
 }
 
 /*
@@ -3710,10 +3844,10 @@ static void print_chain_keys_chain(struct lock_chain *chain)
 
 	printk("depth: %u\n", chain->depth);
 	for (i = 0; i < chain->depth; i++) {
-		hlock_id = chain_hlocks[chain->base + i];
+		hlock_id = get_chain_hlock(chain->base + i);
 		chain_key = print_chain_key_iteration(hlock_id, chain_key);
 
-		print_lock_name(NULL, lock_classes + chain_hlock_class_idx(hlock_id));
+		print_lock_name(NULL, idx_to_lock_class(chain_hlock_class_idx(hlock_id)));
 		printk("\n");
 	}
 }
@@ -3768,7 +3902,7 @@ static int check_no_collision(struct task_struct *curr,
 	for (j = 0; j < chain->depth - 1; j++, i++) {
 		id = hlock_id(&curr->held_locks[i]);
 
-		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
+		if (DEBUG_LOCKS_WARN_ON(get_chain_hlock(chain->base + j) != id)) {
 			print_collision(curr, hlock, chain);
 			return 0;
 		}
@@ -3783,25 +3917,64 @@ static int check_no_collision(struct task_struct *curr,
  */
 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;
+	i = find_next_bit(lock_chains_in_use, MAX_LOCKDEP_CHAINS, i + 1);
+	return i < MAX_LOCKDEP_CHAINS ? i : -2;
 }
 
 unsigned long lock_chain_count(void)
 {
-	return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
+	return bitmap_weight(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
+}
+
+static void lockdep_print_watermarks(const char *bug_msg)
+{
+	print_lockdep_off(bug_msg);
+	pr_err("Lockdep Stats: classes=%lu (chunks=%u), entries=%lu, chains=%lu (chunks=%u), hlocks=%u (chunks=%u)\n",
+	       nr_lock_classes, nr_lock_class_chunks,
+	       nr_list_entries,
+	       lock_chain_count(), nr_lock_chain_chunks,
+	       chain_hlocks_used(), nr_chain_hlock_chunks);
+	pr_err("Lockdep Slabs: total=%u, used=%u (classes=%u, entries=%u, chains=%u, hlocks=%u, trace=%u), free=%u\n",
+	       lockdep_nr_slabs, lockdep_slabs_used,
+	       ld_slabs.lock_classes, ld_slabs.direct_deps,
+	       ld_slabs.lock_chains, ld_slabs.chain_hlocks,
+	       ld_slabs.stack_traces,
+	       lockdep_nr_slabs > lockdep_slabs_used ? lockdep_nr_slabs - lockdep_slabs_used : 0);
+	show_mem();
 }
 
 /* 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));
+	int idx = find_first_zero_bit(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
+	unsigned int chunk_idx;
+	struct lock_chain *chain;
 
-	if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
+	if (unlikely(idx >= MAX_LOCKDEP_CHAINS))
 		return NULL;
+
+	chunk_idx = reciprocal_divide(idx, lock_chain_rv);
+	if (chunk_idx >= LOCKDEP_MAX_SLABS)
+		return NULL;
+
+	if (chunk_idx >= nr_lock_chain_chunks) {
+		struct lock_chain *chunk;
+
+		chunk = lockdep_claim_slab(&ld_slabs.lock_chains);
+		if (!chunk)
+			return NULL;
+
+		memset(chunk, 0, sizeof(struct lock_chain) * lock_chain_PER_CHUNK);
+		/* Pairs with smp_load_acquire() in idx_to_lock_chain() */
+		smp_store_release(&lock_chain_chunks[chunk_idx], chunk);
+		nr_lock_chain_chunks = chunk_idx + 1;
+	}
+
 	__set_bit(idx, lock_chains_in_use);
-	return lock_chains + idx;
+	chain = idx_to_lock_chain(idx);
+	memset(chain, 0, sizeof(*chain));
+	chain->chain_idx = idx;
+	return chain;
 }
 
 /*
@@ -3833,7 +4006,7 @@ static inline int add_chain_cache(struct task_struct *curr,
 			return 0;
 
 		nbcon_cpu_emergency_enter();
-		print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
+		lockdep_print_watermarks("BUG: MAX_LOCKDEP_CHAINS too low!");
 		dump_stack();
 		nbcon_cpu_emergency_exit();
 		return 0;
@@ -3843,9 +4016,9 @@ static inline int add_chain_cache(struct task_struct *curr,
 	i = get_first_held_lock(curr, hlock);
 	chain->depth = curr->lockdep_depth + 1 - i;
 
-	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
+	BUILD_BUG_ON((1UL << 24) <= MAX_LOCKDEP_CHAIN_HLOCKS);
 	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(curr->held_locks));
-	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
+	BUILD_BUG_ON((1UL << (8 * sizeof(u16))) <= MAX_LOCKDEP_KEYS);
 
 	j = alloc_chain_hlocks(chain->depth);
 	if (j < 0) {
@@ -3853,7 +4026,7 @@ static inline int add_chain_cache(struct task_struct *curr,
 			return 0;
 
 		nbcon_cpu_emergency_enter();
-		print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
+		lockdep_print_watermarks("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
 		dump_stack();
 		nbcon_cpu_emergency_exit();
 		return 0;
@@ -3863,9 +4036,9 @@ static inline int add_chain_cache(struct task_struct *curr,
 	for (j = 0; j < chain->depth - 1; j++, i++) {
 		int lock_id = hlock_id(curr->held_locks + i);
 
-		chain_hlocks[chain->base + j] = lock_id;
+		set_chain_hlock(chain->base + j, lock_id);
 	}
-	chain_hlocks[chain->base + j] = hlock_id(hlock);
+	set_chain_hlock(chain->base + j, hlock_id(hlock));
 	hlist_add_head_rcu(&chain->entry, hash_head);
 	debug_atomic_inc(chain_lookup_misses);
 	inc_chains(chain->irq_context);
@@ -5222,7 +5395,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
 		return 0;
 
-	class_idx = class - lock_classes;
+	class_idx = class->class_idx;
 
 	if (depth && !sync) {
 		/* we're holding locks and the new held lock is not a sync */
@@ -5413,7 +5586,7 @@ static noinstr int match_held_lock(const struct held_lock *hlock,
 		if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
 			return 0;
 
-		if (hlock->class_idx == class - lock_classes)
+		if (hlock->class_idx == class->class_idx)
 			return 1;
 	}
 
@@ -5521,7 +5694,7 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 			      lock->wait_type_outer,
 			      lock->lock_type);
 	class = register_lock_class(lock, subclass, 0);
-	hlock->class_idx = class - lock_classes;
+	hlock->class_idx = class->class_idx;
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
@@ -5871,7 +6044,7 @@ static void verify_lock_unused(struct lockdep_map *lock, struct held_lock *hlock
 	if (!(class->usage_mask & mask))
 		return;
 
-	hlock->class_idx = class - lock_classes;
+	hlock->class_idx = class->class_idx;
 
 	print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES);
 #endif
@@ -6279,7 +6452,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++) {
-		if (chain_hlock_class_idx(chain_hlocks[i]) != class - lock_classes)
+		if (chain_hlock_class_idx(get_chain_hlock(i)) != class->class_idx)
 			continue;
 		/*
 		 * Each lock class occurs at most once in a lock chain so once
@@ -6301,7 +6474,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	 * hlist_for_each_entry_rcu() loop is safe.
 	 */
 	hlist_del_rcu(&chain->entry);
-	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
+	__set_bit(chain->chain_idx, pf->lock_chains_being_freed);
 	nr_zapped_lock_chains++;
 #endif
 }
@@ -6338,28 +6511,28 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 	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);
+				free_list_entry(other);
 				break;
 			}
 		}
-		__clear_bit(entry - list_entries, list_entries_in_use);
 		nr_list_entries--;
 		list_del_rcu(&entry->entry);
+		free_list_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);
+				free_list_entry(other);
 				break;
 			}
 		}
-		__clear_bit(entry - list_entries, list_entries_in_use);
 		nr_list_entries--;
 		list_del_rcu(&entry->entry);
+		free_list_entry(entry);
 	}
 	if (list_empty(&class->locks_after) &&
 	    list_empty(&class->locks_before)) {
@@ -6371,8 +6544,8 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 		if (class->usage_mask == 0)
 			debug_atomic_dec(nr_unused_locks);
 		nr_lock_classes--;
-		__clear_bit(class - lock_classes, lock_classes_in_use);
-		if (class - lock_classes == max_lock_class_idx)
+		__clear_bit(class->class_idx, lock_classes_in_use);
+		if (class->class_idx == max_lock_class_idx)
 			max_lock_class_idx--;
 	} else {
 		WARN_ONCE(true, "%s() failed for class %s\n", __func__,
@@ -6450,8 +6623,8 @@ static void __free_zapped_classes(struct pending_free *pf)
 
 #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));
+		      pf->lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
+	bitmap_clear(pf->lock_chains_being_freed, 0, MAX_LOCKDEP_CHAINS);
 #endif
 }
 
@@ -6773,12 +6946,16 @@ void __init lockdep_early_init(void)
 		lockdep_slabs[i] = (char *)pool + (i * LOCKDEP_SLAB_SIZE);
 
 	lockdep_nr_slabs = nr_slabs;
-	pr_info("lockdep: reserved %u slabs (%zu KB) from memblock\n",
+	lockdep_slabs_used = 0;
+
+	pr_info("lockdep: reserved %u slabs (%zu KB) from memblock for dynamic tables\n",
 		nr_slabs, slab_bytes / 1024);
 }
 
 void __init lockdep_init(void)
 {
+	init_data_structures_once();
+
 	pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
 
 	pr_info("... MAX_LOCKDEP_SUBCLASSES:  %lu\n", MAX_LOCKDEP_SUBCLASSES);
@@ -6789,26 +6966,25 @@ void __init lockdep_init(void)
 	pr_info("... MAX_LOCKDEP_CHAINS:      %lu\n", MAX_LOCKDEP_CHAINS);
 	pr_info("... CHAINHASH_SIZE:          %lu\n", CHAINHASH_SIZE);
 
-	pr_info(" memory used by lock dependency info: %zu kB\n",
-	       (sizeof(lock_classes) +
+	pr_info(" memory used by lock dependency info: dynamic (bootstrap %zu kB)\n",
+	       (sizeof(lock_class_chunk0) +
 		sizeof(lock_classes_in_use) +
 		sizeof(classhash_table) +
 		sizeof(list_entries) +
-		sizeof(list_entries_in_use) +
 		sizeof(chainhash_table) +
 		sizeof(delayed_free)
 #ifdef CONFIG_PROVE_LOCKING
 		+ sizeof(lock_cq)
-		+ sizeof(lock_chains)
+		+ sizeof(lock_chain_chunk0)
 		+ sizeof(lock_chains_in_use)
-		+ sizeof(chain_hlocks)
+		+ sizeof(chain_hlock_chunk0)
 #endif
 		) / 1024
 		);
 
 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
-	pr_info(" memory used for stack traces: %zu kB\n",
-	       (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024
+	pr_info(" memory used for stack traces: dynamic (bootstrap %zu kB)\n",
+	       sizeof(stack_trace) / 1024
 	       );
 #endif
 
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 3344361a1c3b..eaa23d9b4dd5 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -7,6 +7,15 @@
  * lockdep subsystem internal functions and variables.
  */
 
+#include <linux/types.h>
+#include <linux/reciprocal_div.h>
+#include <linux/log2.h>
+#include <asm/barrier.h>
+
+#define LOCKDEP_SLAB_SIZE	(64 * 1024)
+#define LOCKDEP_MAX_SLABS	512
+#define LOCKDEP_DEFAULT_SLABS	64
+
 /*
  * Lock-class usage-state bits:
  */
@@ -122,19 +131,25 @@ enum {
 #define MAX_LOCKDEP_CHAINS	(1UL << MAX_LOCKDEP_CHAINS_BITS)
 
 #define AVG_LOCKDEP_CHAIN_DEPTH		5
-#include <linux/reciprocal_div.h>
+#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS * AVG_LOCKDEP_CHAIN_DEPTH)
 
-#define LOCKDEP_SLAB_SIZE	(64 * 1024)
-#define LOCKDEP_MAX_SLABS	512
-#define LOCKDEP_DEFAULT_SLABS	64
+/*
+ * Compile-time precomputation of struct reciprocal_value using the canonical
+ * Granlund-Montgomery algorithm matching lib/math/reciprocal_div.c.
+ */
+#define RECIPROCAL_VALUE_INIT(d) { \
+	.m = (u32)((((1ULL << 32) * ((1ULL << (ilog2((d) - 1) + 1)) - (d))) / (d)) + 1), \
+	.sh1 = (ilog2((d) - 1) + 1) > 0 ? 1 : 0, \
+	.sh2 = (ilog2((d) - 1) + 1) > 1 ? (ilog2((d) - 1) + 1) - 1 : 0, \
+}
 
 /*
  * Chunked Array Tables:
  * Replaces flat monolithic BSS arrays with 2D chunk pointer matrices.
  * Chunk 0 is statically allocated in BSS for early boot, while subsequent
  * chunks are claimed from the memblock reservoir via lockdep_claim_slab().
- * Indexing uses compile-time Granlund-Montgomery reciprocal divide
- * (~3-cycle multiply+shift, zero division instructions).
+ * Indexing uses a compile-time hybrid: single-cycle bit shifts for power-of-2
+ * elements, and Granlund-Montgomery reciprocal divide for non-power-of-2.
  */
 #define DECLARE_CHUNKED_ARRAY(name, type)					\
 	enum {									\
@@ -156,20 +171,16 @@ enum {
 		return &chunk_ptr[offset];					\
 	}
 
-#define DEFINE_CHUNKED_ARRAY(name, type)					\
+#define DEFINE_CHUNKED_ARRAY(name, type)						\
 	static type name##_chunk0[name##_PER_CHUNK];				\
 	type *name##_chunks[LOCKDEP_MAX_SLABS] = { name##_chunk0 };		\
 	static unsigned int nr_##name##_chunks = 1;				\
 	const struct reciprocal_value name##_rv =				\
 		RECIPROCAL_VALUE_INIT(name##_PER_CHUNK)
 
-struct lockdep_slab_usage {
-	unsigned int lock_classes;
-	unsigned int direct_deps;
-	unsigned int lock_chains;
-	unsigned int chain_hlocks;
-	unsigned int stack_traces;
-};
+DECLARE_CHUNKED_ARRAY(lock_chain, struct lock_chain);
+DECLARE_CHUNKED_ARRAY(chain_hlock, u16);
+void lockdep_chain_stats(unsigned int *nr_chunks, size_t *chunk_size, size_t *tail_used);
 
 #define LOCK_USAGE_CHARS (2*XXX_LOCK_USAGE_STATES + 1)
 
@@ -201,9 +212,27 @@ extern unsigned int max_lockdep_depth;
 extern unsigned int max_bfs_queue_depth;
 extern unsigned long max_lock_class_idx;
 
-extern struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
+DECLARE_2D_RADIX(lock_class, struct lock_class);
 extern unsigned long lock_classes_in_use[];
 
+struct lockdep_slab_usage {
+	unsigned int lock_classes;
+	unsigned int direct_deps;
+	unsigned int lock_chains;
+	unsigned int chain_hlocks;
+	unsigned int stack_traces;
+};
+
+struct lockdep_slab_stats {
+	unsigned int total_slabs;
+	unsigned int used_slabs;
+	struct lockdep_slab_usage usage;
+};
+
+unsigned int chain_hlocks_used(void);
+unsigned long lock_chain_count(void);
+void lockdep_get_slab_stats(struct lockdep_slab_stats *st);
+
 #ifdef CONFIG_PROVE_LOCKING
 extern unsigned long lockdep_count_forward_deps(struct lock_class *);
 extern unsigned long lockdep_count_backward_deps(struct lock_class *);
@@ -286,7 +315,7 @@ static inline void debug_class_ops_inc(struct lock_class *class)
 {
 	int idx;
 
-	idx = class - lock_classes;
+	idx = class->class_idx;
 	__debug_atomic_inc(lock_class_ops[idx]);
 }
 
@@ -295,7 +324,7 @@ static inline unsigned long debug_class_ops_read(struct lock_class *class)
 	int idx, cpu;
 	unsigned long ops = 0;
 
-	idx = class - lock_classes;
+	idx = class->class_idx;
 	for_each_possible_cpu(cpu)
 		ops += per_cpu(lockdep_stats.lock_class_ops[idx], cpu);
 	return ops;

-- 
2.55.0

[PATCH 5/8] lockdep: Fast-path power-of-2 tables with shift/mask indexing

[Jim Cromie]

The 2D chunked arrays (DECLARE_CHUNKED_ARRAY) use Granlund-Montgomery
reciprocal division (reciprocal_divide()) to map indices to (chunk, offset)
tuples across 64 KB slabs. This achieves >99.8% packing density for
non-power-of-2 structs (lock_classes @ 160 B and list_entries @ 48 B).

However, the ultra-hot cache-verification tables (lock_chains @ 32 B and
chain_hlocks @ 2 B) have exact power-of-2 chunk counts (2,048 and 32,768
elements per 64 KB slab).

Add a compile-time branch in DECLARE_CHUNKED_ARRAY() using __builtin_ctz():
for power-of-2 tables, GCC/Clang folds translation into single-cycle bit
shifts (idx >> SHIFT) and masks (idx & MASK), eliminating reciprocal
multiplication overhead entirely from the hot acquire validation path.

Workload Progression (hackbench -p -g 8 -l 1000, 4 vCPUs):

  Metric        Upstream (1D) Generic (P2)      Fast-Path (P3)   Delta
  ====================================================================
  Runtime             8.482 s    8.895 s (+4.8%)       8.278 s  -2.40%
  Cycles          52899510936   55428687460     52033166458     -1.64%
  Instructions    29008189069   31932214532     31698626928     +9.27%

By replacing G-M multiplication with single-cycle bit shifts on the hot
cache verification tables, cycle overhead drops by ~6.4% relative to
Patch 2, bringing total cycles to parity with or slightly faster than
upstream baseline (-1.64% cycles).

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/locking/lockdep.c           |  2 +-
 kernel/locking/lockdep_internals.h | 15 +++++++++++++--
 2 files changed, 14 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 1c8db52af1ac..b2dc7619a5e3 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3953,7 +3953,7 @@ static struct lock_chain *alloc_lock_chain(void)
 	if (unlikely(idx >= MAX_LOCKDEP_CHAINS))
 		return NULL;
 
-	chunk_idx = reciprocal_divide(idx, lock_chain_rv);
+	chunk_idx = idx / lock_chain_PER_CHUNK;
 	if (chunk_idx >= LOCKDEP_MAX_SLABS)
 		return NULL;
 
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index eaa23d9b4dd5..ccd7343af672 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -154,14 +154,25 @@ enum {
 #define DECLARE_CHUNKED_ARRAY(name, type)					\
 	enum {									\
 		name##_PER_CHUNK = (LOCKDEP_SLAB_SIZE / sizeof(type)),		\
+		name##_IS_P2     = (!(name##_PER_CHUNK & (name##_PER_CHUNK - 1))), \
+		name##_SHIFT     = (__builtin_ctz(name##_PER_CHUNK)),		\
+		name##_MASK      = (name##_PER_CHUNK - 1),			\
 	};									\
 	extern type * name##_chunks[LOCKDEP_MAX_SLABS];				\
 	extern const struct reciprocal_value name##_rv;				\
 	static __always_inline type *idx_to_##name(unsigned int idx)		\
 	{									\
-		unsigned int chunk = reciprocal_divide(idx, name##_rv);		\
-		unsigned int offset = idx - (chunk * name##_PER_CHUNK);		\
+		unsigned int chunk, offset;					\
 		type *chunk_ptr;						\
+										\
+		if (name##_IS_P2) {						\
+			chunk = idx >> name##_SHIFT;				\
+			offset = idx & name##_MASK;				\
+		} else {							\
+			chunk = reciprocal_divide(idx, name##_rv);		\
+			offset = idx - (chunk * name##_PER_CHUNK);		\
+		}								\
+										\
 		if (unlikely(chunk >= LOCKDEP_MAX_SLABS))			\
 			return NULL;						\
 		/* Pairs with smp_store_release() when new chunk slabs are published */ \

-- 
2.55.0

[PATCH 6/8] lockdep: Free unused reservation slabs to buddy allocator at late boot

[Jim Cromie]

During early boot, lockdep reserves a generous slab pool (e.g. 64 slabs =
4 MB) from memblock to guarantee uninterrupted initialization. Once
the kernel reaches late_initcall, the boot locking storm is complete,
and lockdep's steady-state working set is known.

Add lockdep_post_init_trim() as a late_initcall_sync handler. Calculate
required runtime headroom (default 100% headroom over boot usage, with
a floor of 32 slabs, or custom lockdep_slabs=N / lockdep_headroom=M%),
and return all excess slabs to the buddy page allocator via
free_reserved_page().

Also register a reboot notifier to log total lifetime slab consumption
and remaining headroom on clean system shutdown.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/locking/lockdep.c      | 71 +++++++++++++++++++++++++++++++++++++++++++
 kernel/locking/lockdep_proc.c | 23 +++++++-------
 2 files changed, 83 insertions(+), 11 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b2dc7619a5e3..3fb6c07cea36 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -6992,6 +6992,77 @@ void __init lockdep_init(void)
 	       sizeof(((struct task_struct *)NULL)->held_locks));
 }
 
+static int lockdep_shutdown_notify(struct notifier_block *nb,
+				   unsigned long code, void *unused)
+{
+	unsigned int used = lockdep_slabs_used - lockdep_nr_free_slabs;
+	unsigned int total = lockdep_nr_slabs;
+	unsigned int free_slabs = total > used ? total - used : 0;
+	unsigned int headroom_pct = used ? (free_slabs * 100) / used : 0;
+
+	pr_info("lockdep: shutdown summary : %u/%u slabs (%u kB/%u kB, %u%% headroom left), %lu classes, %lu chains, %u hlocks\n",
+		used, total,
+		(used * LOCKDEP_SLAB_SIZE) / 1024,
+		(total * LOCKDEP_SLAB_SIZE) / 1024,
+		headroom_pct,
+		nr_lock_classes, lock_chain_count(), chain_hlocks_used());
+
+	return NOTIFY_OK;
+}
+
+static struct notifier_block lockdep_reboot_nb = {
+	.notifier_call = lockdep_shutdown_notify,
+};
+
+static int __init lockdep_post_init_trim(void)
+{
+	unsigned int used = lockdep_slabs_used - lockdep_nr_free_slabs;
+	unsigned int initial_slabs = lockdep_nr_slabs;
+	unsigned int target_slabs, kept_headroom_slabs;
+	unsigned int freed_slabs = 0;
+	unsigned int i;
+
+	if (!lockdep_nr_slabs)
+		return 0;
+
+	/* Compute headroom requirement (default 100% or custom percentage) with 32-slab floor */
+	kept_headroom_slabs = DIV_ROUND_UP(used * requested_lockdep_headroom_pct, 100);
+	if (kept_headroom_slabs < 32)
+		kept_headroom_slabs = 32;
+
+	target_slabs = used + kept_headroom_slabs;
+
+	/* Satisfy both: target_slabs >= requested_lockdep_slabs AND headroom >= M% */
+	if (requested_lockdep_slabs > target_slabs)
+		target_slabs = requested_lockdep_slabs;
+
+	target_slabs = clamp_t(unsigned int, target_slabs, used, lockdep_nr_slabs);
+
+	/* Release excess slabs to buddy allocator */
+	if (target_slabs < lockdep_nr_slabs) {
+		for (i = target_slabs; i < lockdep_nr_slabs; i++) {
+			struct page *page = virt_to_page(lockdep_slabs[i]);
+			unsigned long p;
+
+			for (p = 0; p < (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT); p++)
+				free_reserved_page(page + p);
+
+			lockdep_slabs[i] = NULL;
+		}
+		freed_slabs = lockdep_nr_slabs - target_slabs;
+		lockdep_nr_slabs = target_slabs;
+	}
+
+	pr_info("lockdep: boot complete : %u/%u slabs used, %u kept (%u%% headroom), %u returned to buddy (%u kB freed)\n",
+		used, initial_slabs, lockdep_nr_slabs,
+		lockdep_nr_slabs > used ? ((lockdep_nr_slabs - used) * 100) / used : 0,
+		freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024);
+
+	register_reboot_notifier(&lockdep_reboot_nb);
+	return 0;
+}
+late_initcall_sync(lockdep_post_init_trim);
+
 static void
 print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
 		     const void *mem_to, struct held_lock *hlock)
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 1916db9aa46b..95b76047918d 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -32,16 +32,17 @@
  * bitmap and max_lock_class_idx.
  */
 #define iterate_lock_classes(idx, class)				\
-	for (idx = 0, class = lock_classes; idx <= max_lock_class_idx;	\
-	     idx++, class++)
+	for (idx = 0, class = idx_to_lock_class(0);			\
+	     idx <= max_lock_class_idx;					\
+	     idx++, class = idx_to_lock_class(idx))
 
 static void *l_next(struct seq_file *m, void *v, loff_t *pos)
 {
-	struct lock_class *class = v;
+	unsigned long idx = ++*pos;
 
-	++class;
-	*pos = class - lock_classes;
-	return (*pos > max_lock_class_idx) ? NULL : class;
+	if (idx > max_lock_class_idx)
+		return NULL;
+	return idx_to_lock_class(idx);
 }
 
 static void *l_start(struct seq_file *m, loff_t *pos)
@@ -50,7 +51,7 @@ static void *l_start(struct seq_file *m, loff_t *pos)
 
 	if (idx > max_lock_class_idx)
 		return NULL;
-	return lock_classes + idx;
+	return idx_to_lock_class(idx);
 }
 
 static void l_stop(struct seq_file *m, void *v)
@@ -59,7 +60,7 @@ static void l_stop(struct seq_file *m, void *v)
 
 static void print_name(struct seq_file *m, struct lock_class *class)
 {
-	char str[KSYM_NAME_LEN];
+	char str[128];
 	const char *name = class->name;
 
 	if (!name) {
@@ -79,9 +80,9 @@ static int l_show(struct seq_file *m, void *v)
 	struct lock_class *class = v;
 	struct lock_list *entry;
 	char usage[LOCK_USAGE_CHARS];
-	int idx = class - lock_classes;
+	int idx = class->class_idx;
 
-	if (v == lock_classes)
+	if (idx == 0)
 		seq_printf(m, "all lock classes:\n");
 
 	if (!test_bit(idx, lock_classes_in_use))
@@ -133,7 +134,7 @@ static void *lc_start(struct seq_file *m, loff_t *pos)
 	if (*pos == 0)
 		return SEQ_START_TOKEN;
 
-	return lock_chains + (*pos - 1);
+	return idx_to_lock_chain(*pos - 1);
 }
 
 static void *lc_next(struct seq_file *m, void *v, loff_t *pos)

-- 
2.55.0

[PATCH 7/8] lockdep: Expose slab pool telemetry in /proc/lockdep_stats and initcalls

[Jim Cromie]

Extend lockdep observability to track slab allocation dynamics:

0. In /proc/lockdep_stats, display total reserved slabs, used slabs,
   free slabs (headroom), and a per-consumer slab breakdown (lock_classes,
   direct deps, dependency chains, chain hlocks, stack traces).

1. In lockdep.c, add lockdep_report_stage() hooks registered across
   initcall milestones (core, postcore, arch, subsys, fs, device, late)
   to log slab consumption progress throughout kernel initialization.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/locking/lockdep.c           | 47 ++++++++++++++++++++++++++++++++++++++
 kernel/locking/lockdep_internals.h |  4 +++-
 kernel/locking/lockdep_proc.c      | 40 ++++++++++++++++++++++++--------
 3 files changed, 80 insertions(+), 11 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3fb6c07cea36..b6048e7c8b56 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -6992,6 +6992,53 @@ void __init lockdep_init(void)
 	       sizeof(((struct task_struct *)NULL)->held_locks));
 }
 
+static void lockdep_report_stage(const char *domain, const char *stage_name)
+{
+	unsigned int used = lockdep_slabs_used - lockdep_nr_free_slabs;
+	unsigned int class_per_chunk = lock_class_PER_CHUNK;
+	unsigned int entry_per_chunk = LOCKDEP_SLAB_SIZE / sizeof(struct lock_list);
+	unsigned int chain_per_chunk = lock_chain_PER_CHUNK;
+	unsigned int hlock_per_chunk = chain_hlock_PER_CHUNK;
+	unsigned int trace_per_chunk = LOCKDEP_SLAB_SIZE / sizeof(unsigned long);
+
+	unsigned int cl_w = nr_lock_classes / class_per_chunk;
+	unsigned int cl_f = ((nr_lock_classes % class_per_chunk) * 100) / class_per_chunk;
+
+	unsigned int en_w = nr_list_entries / entry_per_chunk;
+	unsigned int en_f = ((nr_list_entries % entry_per_chunk) * 100) / entry_per_chunk;
+
+	unsigned long chains = lock_chain_count();
+	unsigned int ch_w = chains / chain_per_chunk;
+	unsigned int ch_f = ((chains % chain_per_chunk) * 100) / chain_per_chunk;
+
+	unsigned int hlocks = chain_hlocks_used();
+	unsigned int hl_w = hlocks / hlock_per_chunk;
+	unsigned int hl_f = ((hlocks % hlock_per_chunk) * 100) / hlock_per_chunk;
+
+	unsigned int tr_w = nr_stack_trace_entries / trace_per_chunk;
+	unsigned int tr_f = ((nr_stack_trace_entries % trace_per_chunk) * 100) / trace_per_chunk;
+
+	pr_info("lockdep: %-8s [%-9s] : %u/%u slabs : classes=%u.%02u entries=%u.%02u chains=%u.%02u hlocks=%u.%02u trace=%u.%02u\n",
+		domain, stage_name, used, lockdep_nr_slabs,
+		cl_w, cl_f, en_w, en_f, ch_w, ch_f, hl_w, hl_f, tr_w, tr_f);
+}
+
+#define DEFINE_LOCKDEP_LEVEL_REPORT(lvl, name)			\
+	static int __init lockdep_report_##name(void)		\
+	{							\
+		lockdep_report_stage("initcall", #name);	\
+		return 0;					\
+	}							\
+	lvl(lockdep_report_##name)
+
+DEFINE_LOCKDEP_LEVEL_REPORT(core_initcall_sync, core);
+DEFINE_LOCKDEP_LEVEL_REPORT(postcore_initcall_sync, postcore);
+DEFINE_LOCKDEP_LEVEL_REPORT(arch_initcall_sync, arch);
+DEFINE_LOCKDEP_LEVEL_REPORT(subsys_initcall_sync, subsys);
+DEFINE_LOCKDEP_LEVEL_REPORT(fs_initcall_sync, fs);
+DEFINE_LOCKDEP_LEVEL_REPORT(device_initcall_sync, device);
+DEFINE_LOCKDEP_LEVEL_REPORT(late_initcall_sync, late);
+
 static int lockdep_shutdown_notify(struct notifier_block *nb,
 				   unsigned long code, void *unused)
 {
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index ccd7343af672..6fb776618ac6 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -223,7 +223,7 @@ extern unsigned int max_lockdep_depth;
 extern unsigned int max_bfs_queue_depth;
 extern unsigned long max_lock_class_idx;
 
-DECLARE_2D_RADIX(lock_class, struct lock_class);
+DECLARE_CHUNKED_ARRAY(lock_class, struct lock_class);
 extern unsigned long lock_classes_in_use[];
 
 struct lockdep_slab_usage {
@@ -240,6 +240,8 @@ struct lockdep_slab_stats {
 	struct lockdep_slab_usage usage;
 };
 
+void lockdep_get_slab_stats(struct lockdep_slab_stats *st);
+
 unsigned int chain_hlocks_used(void);
 unsigned long lock_chain_count(void);
 void lockdep_get_slab_stats(struct lockdep_slab_stats *st);
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 95b76047918d..76e32fca8c54 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -380,17 +380,37 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 			debug_locks);
 
 	/*
-	 * Zapped classes and lockdep data buffers reuse statistics.
+	 * Shared Memblock Slab Reservoir Statistics
 	 */
-	seq_puts(m, "\n");
-	seq_printf(m, " zapped classes:                %11lu\n",
-			nr_zapped_classes);
-#ifdef CONFIG_PROVE_LOCKING
-	seq_printf(m, " zapped lock chains:            %11lu\n",
-			nr_zapped_lock_chains);
-	seq_printf(m, " large chain blocks:            %11u\n",
-			nr_large_chain_blocks);
-#endif
+	{
+		struct lockdep_slab_stats st;
+
+		lockdep_get_slab_stats(&st);
+		if (st.total_slabs) {
+			unsigned int free_slabs = st.total_slabs > st.used_slabs ?
+						  st.total_slabs - st.used_slabs : 0;
+			unsigned int headroom_pct = (free_slabs * 100) / st.total_slabs;
+
+			seq_puts(m, "\n lockdep memblock slab reservoir:\n");
+			seq_printf(m, "   total slabs:                 %11u (%zu kB)\n",
+				   st.total_slabs, (size_t)st.total_slabs * 64);
+			seq_printf(m, "   used slabs:                  %11u (%zu kB)\n",
+				   st.used_slabs, (size_t)st.used_slabs * 64);
+			seq_printf(m, "     - lock_classes slabs:      %11u (%zu kB)\n",
+				   st.usage.lock_classes, (size_t)st.usage.lock_classes * 64);
+			seq_printf(m, "     - direct deps slabs:       %11u (%zu kB)\n",
+				   st.usage.direct_deps, (size_t)st.usage.direct_deps * 64);
+			seq_printf(m, "     - dependency chains slabs: %11u (%zu kB)\n",
+				   st.usage.lock_chains, (size_t)st.usage.lock_chains * 64);
+			seq_printf(m, "     - chain hlocks slabs:      %11u (%zu kB)\n",
+				   st.usage.chain_hlocks, (size_t)st.usage.chain_hlocks * 64);
+			seq_printf(m, "     - stack_trace slabs:       %11u (%zu kB)\n",
+				   st.usage.stack_traces, (size_t)st.usage.stack_traces * 64);
+			seq_printf(m, "   free slabs (headroom):       %11u (%zu kB, %u%%)\n",
+				   free_slabs, (size_t)free_slabs * 64, headroom_pct);
+		}
+	}
+
 	return 0;
 }
 

-- 
2.55.0

[PATCH 8/8] lockdep: on debug_locks_off or OOM, recycle all slabs to buddy

[Jim Cromie]

If lockdep breaks, by assertion failure or for ENOMEM-ish reasons, we
can no longer use the graph-db.  Since most of the graph-db is now
allocated from memblock_alloc() slabs, we can release them all back to
buddy, and hope that freeing ~1.5MB will help. (v7.2 has ~10MB tied up
in .bss).

0. Hook debug_locks_off() / print_lockdep_off() via an asynchronous
   work item (lockdep_sacrifice_work) to release all held slabs back
   to the buddy allocator via free_reserved_page() in process context.

1. Register an OOM notifier (lockdep_oom_nb) at late_initcall. If the
   system encounters an out-of-memory emergency, lockdep sacrifices its
   entire dynamic slab pool (1..8 MB of physical RAM), reporting freed
   pages to the OOM killer to avoid terminating user processes.

2. Clear lockdep_slabs[] pointers and zero lockdep_nr_slabs under
   graph_lock to seal off subsequent allocations.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/locking/lockdep.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b6048e7c8b56..9f28530b2f1d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -60,7 +60,9 @@
 #include <linux/kasan.h>
 #include <linux/mm.h>
 #include <linux/memblock.h>
+#include <linux/oom.h>
 #include <linux/reboot.h>
+#include <linux/workqueue.h>
 
 #include <asm/sections.h>
 
@@ -638,6 +640,82 @@ static int verbose(struct lock_class *class)
 	return 0;
 }
 
+/*
+ * Release all memblock slabs (used and unused) back to the buddy allocator
+ * when lockdep is disabled or during system OOM emergencies.
+ * Must run in process context (workqueue or OOM notifier).
+ */
+static unsigned int lockdep_release_slabs_to_buddy(void)
+{
+	unsigned int freed_slabs = 0;
+	unsigned int nr = lockdep_nr_slabs;
+	unsigned long flags;
+	unsigned int i;
+
+	if (!nr)
+		return 0;
+
+	/* Invalidate table bounds under graph_lock */
+	raw_local_irq_save(flags);
+	if (!graph_lock()) {
+		raw_local_irq_restore(flags);
+		return 0;
+	}
+	lockdep_nr_slabs = 0;
+	lockdep_slabs_used = 0;
+	graph_unlock();
+	raw_local_irq_restore(flags);
+
+	for (i = 0; i < nr; i++) {
+		struct page *page;
+		unsigned long p;
+
+		if (!lockdep_slabs[i])
+			continue;
+
+		page = virt_to_page(lockdep_slabs[i]);
+		for (p = 0; p < (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT); p++)
+			free_reserved_page(page + p);
+
+		lockdep_slabs[i] = NULL;
+		freed_slabs++;
+	}
+
+	if (freed_slabs)
+		pr_info("lockdep: emergency sacrifice — released %u slabs (%u kB) to buddy allocator\n",
+			freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024);
+
+	return freed_slabs;
+}
+
+static void lockdep_sacrifice_work_fn(struct work_struct *work)
+{
+	lockdep_release_slabs_to_buddy();
+}
+static DECLARE_WORK(lockdep_sacrifice_work, lockdep_sacrifice_work_fn);
+
+static int lockdep_oom_notify(struct notifier_block *self,
+			      unsigned long dummy, void *parm)
+{
+	unsigned long *freed = parm;
+	unsigned int freed_slabs;
+
+	if (!lockdep_nr_slabs)
+		return NOTIFY_OK;
+
+	/* Turn off lockdep before sacrificing tables */
+	debug_locks_off();
+	freed_slabs = lockdep_release_slabs_to_buddy();
+	if (freed && freed_slabs)
+		*freed += (freed_slabs * (LOCKDEP_SLAB_SIZE >> PAGE_SHIFT));
+
+	return NOTIFY_OK;
+}
+
+static struct notifier_block lockdep_oom_nb = {
+	.notifier_call = lockdep_oom_notify,
+};
+
 static void print_lockdep_off(const char *bug_msg)
 {
 	printk(KERN_DEBUG "%s\n", bug_msg);
@@ -645,6 +723,8 @@ static void print_lockdep_off(const char *bug_msg)
 #ifdef CONFIG_LOCK_STAT
 	printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
 #endif
+	if (system_state >= SYSTEM_RUNNING)
+		schedule_work(&lockdep_sacrifice_work);
 }
 
 unsigned long nr_stack_trace_entries;
@@ -7105,6 +7185,7 @@ static int __init lockdep_post_init_trim(void)
 		lockdep_nr_slabs > used ? ((lockdep_nr_slabs - used) * 100) / used : 0,
 		freed_slabs, (freed_slabs * LOCKDEP_SLAB_SIZE) / 1024);
 
+	register_oom_notifier(&lockdep_oom_nb);
 	register_reboot_notifier(&lockdep_reboot_nb);
 	return 0;
 }

-- 
2.55.0

Re: [PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[Peter Zijlstra]

On Wed, Aug 26, 2026 at 09:58:32PM -0600, Jim Cromie wrote:
> Lockdep cannot rely upon any other subsystem that uses locks, so since
> inception, its graph-db has been stored in static arrays, pinning ~10
> MB in .bss. This is a hardcoded compromise between embedded and
> enterprise hardware.
> 
> However, if it acts early, lockdep can pre-allocate a pool of slabs
> from memblock_alloc(), enough for its lifetime of anticipated workloads.
> Then it can allocate them as needed to provide new segments/slabs to
> the graph-db.
> 

Why? I really don't understand why. Who cares about this bss stuff.

Re: [PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[jim.cromie]

On Thu, Aug 27, 2026 at 12:46 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Aug 26, 2026 at 09:58:32PM -0600, Jim Cromie wrote:
> > Lockdep cannot rely upon any other subsystem that uses locks, so since
> > inception, its graph-db has been stored in static arrays, pinning ~10
> > MB in .bss. This is a hardcoded compromise between embedded and
> > enterprise hardware.
> >
> > However, if it acts early, lockdep can pre-allocate a pool of slabs
> > from memblock_alloc(), enough for its lifetime of anticipated workloads.
> > Then it can allocate them as needed to provide new segments/slabs to
> > the graph-db.
> >
>
> Why? I really don't understand why. Who cares about this bss stuff.

I thought embedded folk might value 10mb less bss ?
Or have they stopped using lockdep already, for size or other reasons.

How about OOM, when kernel needs mem,
or lockdep debug-off, when the slabs tied up in the graph-db could be returned

do these not tip the scales ?

Re: [PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[Peter Zijlstra]

On Thu, Aug 27, 2026 at 02:54:12AM -0600, jim.cromie@gmail.com wrote:
> On Thu, Aug 27, 2026 at 12:46 AM Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Wed, Aug 26, 2026 at 09:58:32PM -0600, Jim Cromie wrote:
> > > Lockdep cannot rely upon any other subsystem that uses locks, so since
> > > inception, its graph-db has been stored in static arrays, pinning ~10
> > > MB in .bss. This is a hardcoded compromise between embedded and
> > > enterprise hardware.
> > >
> > > However, if it acts early, lockdep can pre-allocate a pool of slabs
> > > from memblock_alloc(), enough for its lifetime of anticipated workloads.
> > > Then it can allocate them as needed to provide new segments/slabs to
> > > the graph-db.
> > >
> >
> > Why? I really don't understand why. Who cares about this bss stuff.
> 
> I thought embedded folk might value 10mb less bss ?
> Or have they stopped using lockdep already, for size or other reasons.

I've never heard complaints from embedded people that this is a problem.
Very few Linux capable machines can't spare 10mb.

This is about kernel development, if you need to develop a driver (only
case you might be tied to specific hardware) just get your developer a
board that has a spare 10mb of memory? Your developer is probably
served by having the most beefy board available anyway.

There was a case on sparc where the bss was a problem because the kernel
image had definite size constraints, but I don't think any 'modern'
systems suffer that particular problem.

> How about OOM, when kernel needs mem,
> or lockdep debug-off, when the slabs tied up in the graph-db could be returned

If you're running into OOM while doing kernel dev you're doing it wrong?

Re: [PATCH 0/8] lockdep: change 5 graph-db arrays to AofAs, fill from memblock pool

[jim.cromie]

On Thu, Aug 27, 2026 at 3:03 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Thu, Aug 27, 2026 at 02:54:12AM -0600, jim.cromie@gmail.com wrote:
> > On Thu, Aug 27, 2026 at 12:46 AM Peter Zijlstra <peterz@infradead.org> wrote:
> > >
> > > On Wed, Aug 26, 2026 at 09:58:32PM -0600, Jim Cromie wrote:
> > > > Lockdep cannot rely upon any other subsystem that uses locks, so since
> > > > inception, its graph-db has been stored in static arrays, pinning ~10
> > > > MB in .bss. This is a hardcoded compromise between embedded and
> > > > enterprise hardware.
> > > >
> > > > However, if it acts early, lockdep can pre-allocate a pool of slabs
> > > > from memblock_alloc(), enough for its lifetime of anticipated workloads.
> > > > Then it can allocate them as needed to provide new segments/slabs to
> > > > the graph-db.
> > > >
> > >
> > > Why? I really don't understand why. Who cares about this bss stuff.
> >
> > I thought embedded folk might value 10mb less bss ?
> > Or have they stopped using lockdep already, for size or other reasons.
>
> I've never heard complaints from embedded people that this is a problem.
> Very few Linux capable machines can't spare 10mb.
>
> This is about kernel development, if you need to develop a driver (only
> case you might be tied to specific hardware) just get your developer a
> board that has a spare 10mb of memory? Your developer is probably
> served by having the most beefy board available anyway.
>
> There was a case on sparc where the bss was a problem because the kernel
> image had definite size constraints, but I don't think any 'modern'
> systems suffer that particular problem.
>

Fair points on embedded.
So the value proposition is narrow:

folks hitting "BUG: MAX_LOCKDEP_* too low!"
who cannot build, deploy a kernel with tweaked MAX_LOCKDEP constants.
They're running a distro-debug kernel.

this group might include:
Distro QA, enterprise testers, Syzbot/CI runners.
For these users, lockdep sometimes turns off permanently,
silently invalidating the rest of the test run.

if they had the lockdep_slabs=N knob, they might use it,
and throw more workload on the box without a possible hard-fail looming.

> > How about OOM, when kernel needs mem,
> > or lockdep debug-off, when the slabs tied up in the graph-db could be returned
>
> If you're running into OOM while doing kernel dev you're doing it wrong?

heh - not me, that was the other guy.
it was a "feature", I thought it might help the sale. :-)

 thanks