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

[Jim Cromie <jim.cromie@gmail.com>]

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>