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