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

[Marco Elver]

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