[PATCH RFC 0/9] Path-compressed trie storage for persistent stack depot records

[Caleb Kan]

Hi,

Stack depot stores kernel stack traces and returns compact handles that
diagnostic subsystems can retain. Some subsystems keep those records for
the lifetime of the system.

The hash backend deduplicates identical traces, but stores every distinct
trace in full. Allocator and sanitizer traces often differ at only one or
two call sites while sharing most frames, so the same frame sequences are
stored repeatedly. This can exhaust stack depot's fixed pool budget; once
that happens, new traces cannot be recorded and diagnostics lose stack
information.

This series adds an opt-in path-compressed trie for persistent,
non-refcounted traces. Related traces can share common frame runs, while
records that need refcounting or direct count access remain hash-backed.

Backend policy
===

Backend selection follows record lifetime and API needs.
STACK_DEPOT_FLAG_GET records remain hash-backed because refcounted eviction
requires record and handle reuse. This series adds
STACK_DEPOT_FLAG_COUNTABLE for page_owner, which needs direct access to a
record count. COUNTABLE records also remain hash-backed, and identical
countable and non-countable traces occupy separate records. With trie
storage enabled, traces saved without either flag use the trie and remain
persistent.

A trie-eligible save that is not allowed to allocate, referred to below as
a constrained save, performs one lockless lookup. It does not wait, take
the writer lock, or insert a missing trace. A hit succeeds; a miss returns
0 until an allocating save inserts the same trace. A trace seen only from
constrained contexts is therefore never recorded. By contrast, the hash
backend can insert into available pool storage and uses a trylock when the
context cannot spin.

Trie insertion failure returns 0 instead of falling back to hash storage.
This keeps eligible persistent records in one backend and avoids hiding
trie exhaustion by consuming hash capacity.

The hash and trie backends draw from the same physical pool array and
stack_depot_max_pools limit. A pool assigned to trie slots cannot hold hash
records, so trie growth can reduce capacity available to GET and COUNTABLE
records.

Design
===

Each trie node stores a run of frames, and branching occurs only where
traces diverge. Children are sorted by their first frame and found by
binary search. A node at which a saved trace ends receives a sequential
stack ID encoded in the handle. Such a node may also have children when one
saved trace is a prefix of another. A sparse side table maps IDs to nodes,
and fetch reconstructs a trace by following parent links.

An architecture hook encodes a frame in 32 bits only when decoding exactly
reproduces the original address. arm64 stores a signed offset from _text,
and x86-64 stores the low 32 bits when the upper 32 bits are all set. Other
frames remain full-width; the generic implementation always uses
full-width frames.

Trie nodes and child arrays occupy contiguous runs of 16-byte slots in the
existing order-2 pools. A writer lock serializes insertion, while RCU
protects lockless lookup and fetch. Each insertion reserves all storage
that can fail before publishing a stack. Unpublished reservations are
released immediately. Replaced nodes and child arrays carry an RCU
grace-period cookie, and later insertions may reuse their slots only after
the grace period completes. Pools, stored stacks, and stack IDs are never
recycled.

API and consumer changes
===

Trie records are not contiguous, so stack_depot_fetch(), which returns a
pointer into depot-owned storage, remains hash-only. Add
stack_depot_fetch_into() to copy either backend into caller-owned storage
and return the number of frames copied. An undersized buffer receives no
partial trace and returns 0. stack_depot_print() and stack_depot_snprint()
also support both backends.

Kmemleak, KMSAN, SLUB, and DRM move to backend-independent accessors.
page_owner remains hash-backed because it keeps stable struct stack_record
pointers and uses the record count for base-page accounting. The GDB helper
rejects trie handles instead of interpreting them as hash pool offsets.

Activation and limits
===

Hash handles reserve pool-index values through stack_depot_max_pools; trie
handles use the remaining values to encode stack IDs. Increasing
stack_depot_max_pools therefore shrinks the trie ID namespace. With 64 KiB
pages, the default maximum reserves every pool-index value, so trie
activation requires lowering stack_depot_max_pools. If optional trie
initialization fails, the hash backend retains its configured capacity.

Patch 9 adds the default-off stackdepot.trie_enabled boot parameter.
Keeping activation in the final patch leaves the trie unreachable while
consumers are converted, so every intermediate commit remains safe and
bisectable.

Testing
===

Stackdepot KUnit passed with trie storage enabled on arm64 with 4 KiB,
16 KiB, and 64 KiB pages and on x86-64 with 256-frame stacks.
PROVE_LOCKING, KCSAN, Generic KASAN, and hash-backed KMSAN configurations
also passed.
Trie-enabled KMSAN reproduced the documented constrained-only misses.
Arm64 boots passed with trie storage disabled and enabled, including a
Generic KASAN plus PROVE_LOCKING configuration. drgn stack
materialization and integrity checks passed in both backend modes.

Results
===

Kernels built from the same revision, with 4 KiB pages and KASAN enabled,
ran for 61 to 67 hours on one trie-disabled and one trie-enabled machine
per architecture. The workloads and stored stack populations were neither
replayed nor matched. Record counts and per-record values cover only
successfully stored persistent records.

The x86-64 trie-disabled machine reached the configured limit of 8,192
pools. The corresponding trie-enabled collection observed approximately
1,943 pools, or 23.7% of the pool budget, but that collection raced. The
full observations were:

                                       arm64                    x86-64
                           trie disabled   enabled  trie disabled   enabled
Uptime (hours)                      60.9      63.9           64.5      66.9
Stored records                  ~161,819    87,088        497,600  ~217,163
Registered pools                  ~2,632       925          8,192    ~1,943
Pool budget used                  ~32.1%     11.3%         100.0%    ~23.7%
Backend bytes/record             ~266.49    182.44         269.73   ~154.76

Values prefixed with '~' came from collections whose start and end markers
differed. Those collections raced with concurrent updates and are unusable
as coherent snapshots or integrity-validation results. They are retained
only as approximate observations.

Backend bytes per record include pool storage and backend-specific
metadata but exclude fixed allocations shared by both configurations.
Using the approximate values in the table gives 31.5% lower backend bytes
per successful persistent record on arm64 and 42.6% lower on x86-64 with
trie enabled. Given the limitations above, these ratios provide directional
context only, not matched estimates of memory reduction. They also do not
establish equivalent diagnostic coverage because constrained-only trie
misses are unobservable.

Both trie-enabled machines remained up throughout the observation. This
uncontrolled soak does not support estimates of CPU overhead, system-level
memory pressure, or overall performance.

Feedback requested
===

Feedback would be especially useful on:

1. Whether lookup-only constrained saves, including the loss of traces seen
   only in constrained contexts, are acceptable for an initial version;
2. Whether stack_depot_fetch_into() is the right migration API while the
   pointer-returning stack_depot_fetch() remains hash-only;
3. Whether trie and hash records should share the physical pool budget;
4. Whether the 64 KiB handle-space limitation requires a different trie
   handle encoding; and
5. Whether retired slots should be reused only when a later insertion
   observes completion of their RCU grace period.

Signed-off-by: Caleb Kan <ckan@xxxxxxxxxxxxxx>
---
Caleb Kan (9):
      stackdepot: share persistent stack prefixes with trie storage
      stackdepot: add KUnit tests for trie storage
      mm/page_owner: preserve accounting with countable stack depot records
      mm/kmemleak: print trie-backed stack depot traces
      kmsan: report trie-backed stack depot traces
      mm/slub: materialize trie-backed stack depot traces
      drm/locking: preserve deadlock diagnostics for trie-backed stacks
      scripts/gdb: reject trie-backed stack depot handles
      stackdepot: add boot-time activation for trie storage

 Documentation/admin-guide/kernel-parameters.txt |    7 +
 arch/arm64/include/asm/stackdepot.h             |   42 +
 arch/um/include/asm/Kbuild                      |    1 +
 arch/x86/include/asm/stackdepot.h               |   37 +
 drivers/gpu/drm/drm_modeset_lock.c              |    5 +-
 include/asm-generic/Kbuild                      |    1 +
 include/asm-generic/stackdepot.h                |   19 +
 include/linux/stackdepot.h                      |   81 +-
 lib/Kconfig.debug                               |   17 +
 lib/stackdepot.c                                | 1484 ++++++++++++++++++++++-
 lib/tests/Makefile                              |    1 +
 lib/tests/stackdepot_kunit.c                    |  473 ++++++++
 mm/kmemleak.c                                   |    4 +-
 mm/kmsan/kmsan_test.c                           |    4 +-
 mm/kmsan/report.c                               |   17 +-
 mm/page_owner.c                                 |    6 +-
 mm/slub.c                                       |   12 +-
 scripts/gdb/linux/stackdepot.py                 |    4 +
 18 files changed, 2168 insertions(+), 47 deletions(-)
---
base-commit: 3b1d6bd7bb11fd040bfa7b712486f5bd41a276cf
change-id: 20260807-stackdepot-trie-2de15a2dcf97

Best regards,
--  
Caleb Kan <ckan@xxxxxxxxxxxxxx>