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>

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.

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 ?

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?

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