[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@xxxxxxxxx>
---
 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