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@cloudflare.com>
---
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@cloudflare.com>

On Mon, 17 Aug 2026 at 14:43, Caleb Kan <calebkan1106@gmail.com> wrote:
>
> 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.

Stackdepot's design involves several trade-offs. Changing that needs a
clearer motivation, in particular, which problem did you run into?
Which problem were you unable to solve due to stackdepot's current
design?

The fact we potentially exhaust the pool is known, and the easiest fix
is to increase the max number of pools. Compressing the records
introduces a lot of complexity, whereas the simplest fix is to just
double the pool size. Which environment are you targeting where
doubling pools wouldn't work?

> 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.

It sounds nice in theory, but you omitted the most imporant question
most reviewers would have: what's the performance overhead?

> 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;

Not great; I'd expect changes to stackdepot internals to retain
feature parity and no changes in observable behaviour.

> 2. Whether stack_depot_fetch_into() is the right migration API while the
>    pointer-returning stack_depot_fetch() remains hash-only;

I don't see a better option. One issue is that we're increasing stack
usage where stack_depot_fetch_into() is used, which in some contexts
is already very constrained.

> 3. Whether trie and hash records should share the physical pool budget;

The upper bound on memory budget should not change, and we shouldn't
silently double the budget because there are 2 pools.

> 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.

I'd assume so, otherwise you risk some lifecycle violation?


Thanks,
-- Marco

On Tue, 18 Aug 2026 at 14:18, Marco Elver <elver@google.com> wrote:
> Stackdepot's design involves several trade-offs. Changing that needs a
> clearer motivation, in particular, which problem did you run into?
> Which problem were you unable to solve due to stackdepot's current
> design?
>
> The fact we potentially exhaust the pool is known, and the easiest fix
> is to increase the max number of pools. Compressing the records
> introduces a lot of complexity, whereas the simplest fix is to just
> double the pool size. Which environment are you targeting where
> doubling pools wouldn't work?

We ran into this on Cloudflare servers running Generic KASAN.
Stackdepot exhausted its pool budget even after we raised the limit
from 8,192 to 32,768 pools. Increasing it again would buy more time,
but it would not change the linear growth from storing each distinct
trace in full. I'll make the motivation and exhaustion evidence clearer
in v2.

> It sounds nice in theory, but you omitted the most imporant question
> most reviewers would have: what's the performance overhead?

I do not yet have direct measurements of save, lookup, or fetch overhead.
I'll add controlled hash-versus-trie benchmarks, collect data, and include
the results in v2.

> Not great; I'd expect changes to stackdepot internals to retain
> feature parity and no changes in observable behaviour.

For v2, I'll add a best-effort constrained insertion path analogous to
the hash backend, using only immediately available storage and without
allocating, waiting, or blocking.

> I don't see a better option. One issue is that we're increasing stack
> usage where stack_depot_fetch_into() is used, which in some contexts
> is already very constrained.

I'll measure the compiler-reported stack growth for every converted
caller and reduce it where necessary, then report the results with v2.

Thanks,
Caleb