[PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie

[Caleb Kan <calebkan1106@gmail.com>]

Hi,

This series reduces the memory used by persistent stack depot records by
sharing common frame prefixes in a path-compressed trie.

Cloudflare runs KASAN on pre-production servers so allocation and free
stack traces are available when diagnosing memory-safety bugs. On some of
these servers, stack depot exhausted its pool budget even after we raised
stack_depot_max_pools from 8,192 to 32,768. Once the depot is full, a new
persistent trace returns no handle and a later KASAN report can lose the
history needed to explain the bug.

With 4 KiB pages, 32,768 order-2 pools allow 512 MiB of stack storage.
Doubling the limit again would allow 1 GiB, but it would not change the
linear growth: the hash backend shares identical complete traces, while
two traces that differ by one frame are still stored independently.

The trie is opt-in and disabled by default.

Backend behavior
================

When the trie is enabled, a persistent save uses it unless the caller sets
STACK_DEPOT_FLAG_GET or STACK_DEPOT_FLAG_COUNTABLE. GET records can be
released. COUNTABLE records remain hash-backed because page_owner needs a
stable struct stack_record and its count field.

RFC v1 only looked up existing trie records when a save was not
permitted to allocate. RFC v2 also makes one best-effort insertion
outside NMI using pool and side-table memory that stack depot already has.
It does not allocate, sleep, retry, wait for RCU, or fall back to the
hash backend. If the trace cannot be recorded, the save returns 0.

An NMI save remains lookup-only. It can return an existing trie handle, but
a new trace returns 0. The hash backend can sometimes insert from NMI when
it already has enough pool space.

Both backends share stack_pools and the stack_depot_max_pools limit. A pool
used by the trie is unavailable to hash-backed GET and COUNTABLE records.

Design and API
==============

Each trie node stores a run of frames and branches only where traces
diverge. On arm64 and x86-64, a frame uses a compressed 32-bit payload
only when it can be decoded back to the exact original address. arm64
stores a signed offset from _text. x86-64 stores the low 32 bits when the
upper 32 bits are all set. Other frames remain full-width.

Trie handles contain dense stack IDs. A sparse table maps each ID to the
node where its trace ends. Fetch reconstructs the trace by following parent
links.

Insertion is serialized, while lookup and fetch run under RCU. A new stack
is published only after every required reservation succeeds. Replaced
nodes and child arrays are reused only after their RCU grace period.

Trie records are not contiguous, so stack_depot_fetch() remains hash-only.
The series adds stack_depot_fetch_into() for caller-owned storage and makes
stack_depot_print() and stack_depot_snprint() work with either backend.
Kmemleak, KMSAN, SLUB, and DRM use these interfaces. page_owner remains on
COUNTABLE hash records, and the GDB helper rejects trie handles.

Patch 1 fixes final-pool preallocation. Patches 2 through 9 prepare the
API, consumers, tooling, and architecture hooks. Patch 10 enables
trie-backed handles and adds a boot parameter that is disabled by
default. Patch 11 adds trie KUnit coverage. Trie handles do not become
reachable until all API and consumer changes are in place.

CPU cost
========

The benchmark was pinned to one CPU and inserted 32,768 distinct 32-frame
stacks on KASAN-enabled Linux 6.18.48. Within each group of 64 stacks, 75%
of the frames were shared and all frames were compressible. The insertion
order was shuffled, and the warm save-hit and fetch phases replayed the
stacks 32 times.

                         arm64 CPU ns/op         x86-64 CPU ns/op
                         hash       trie        hash         trie
Insertion                 777      9,417         792       11,269
Warm save hit             945      1,287         623        1,012
Fetch                     251        511         123          476

The main cost is first insertion, which was about 12 times slower on arm64
and 14 times slower on x86-64. A warm save hit was 1.4 to 1.6 times slower,
and fetch was 2 to 4 times slower.

Memory use
==========

I collected stack depot state from four live KASAN servers using the same
kernel revision, 4 KiB pages, and an 8,192-pool limit. The servers remained
active, so the values below are rounded.

                              arm64                 x86-64
                        trie off trie on      trie off trie on
Run time (hours)              61      64            65      67
Stored records              162k     87k          498k    217k
Registered pools           2,630     925         8,192   1,940
Pool budget used             32%     11%          100%     24%

The trie-enabled x86-64 machine used less than a quarter of the pool budget
while the trie-disabled machine reached the limit.

The machines ran different workloads and stored different stacks, so this
is not a controlled comparison. Exact memory savings depend on the
workload.

Stack use and limits
====================

Before this series, the KMSAN report path that prints an origin used 768
bytes of stack on x86-64 with Clang 19. RFC v1 increased it to 1,264
bytes. RFC v2 reuses KMSAN's existing scratch array and uses 752 bytes,
slightly less than the tree before this series.

RFC v1 also materialized as many as 256 frames on the stack. At that depth,
stack_depot_print() and stack_depot_snprint() used 2,072 and 2,104 bytes.
RFC v2 processes 16 frames at a time, reducing them to 184 and 200 bytes.
Kmemleak and the converted SLUB callers each add one fixed 16-frame array,
or 128 bytes on 64-bit systems. DRM uses the bounded snprint path without
adding a trace array.

A node's child array must fit in one pool. Each child represents a
different next frame after a shared prefix. For example, allocator stacks
can share the same initial frames and then diverge at many different call
sites. On a 4 KiB, 64-bit system, one node can hold 1,024 children. The
largest observed node had about 835 children. An insertion that would
add a 1,025th child fails; existing records remain valid.

Trie IDs use handle values left unused by the configured pool limit. With
64 KiB pages, the default stack_depot_max_pools value leaves no such handle
space. The limit must currently be lowered to enable the trie; otherwise
trie initialization fails and the hash backend remains available.

Testing
=======

I ran the common KUnit cases against both backends with a 64-frame maximum.
Trie-specific cases also ran at 8 and 256 frames, including a 64 KiB arm64
configuration. The tests cover public API behavior, each insertion shape,
old handles after topology changes, and compressed and full-width frames.

I also ran the patches with PROVE_LOCKING and KCSAN, ran KMSAN tests with
both backends, built with arm64 GCC and x86-64 Clang, and booted with the
trie disabled and enabled.

Questions
=========

I would particularly appreciate feedback on:

1. Is it acceptable for an NMI save to look up an existing trie record but
   return 0 for a new trace, while a non-NMI save that is not permitted to
   allocate gets one best-effort insertion attempt?

2. Is the roughly 12 to 14 times higher first-insertion cost acceptable for
   an optional backend, given the smaller cost for warm saves and fetches?

3. Should stack depot reserve some of stack_depot_max_pools for hash-backed
   GET and COUNTABLE records, or should both backends continue to share the
   limit on a first-come basis?

4. Is the 1,024-child limit acceptable for an initial implementation, or
   should child arrays be allowed to span multiple pools?

5. On 64 KiB systems, is requiring a lower stack_depot_max_pools value
   acceptable, or should trie IDs use a different handle encoding?

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
Changes in v2:
- Expanded the motivation with KASAN systems that exhausted the
  32,768-pool limit.
- Reordered the series so APIs, consumers, tooling, and architecture hooks
  are ready before trie handles become reachable.
- Added a best-effort insertion outside NMI for saves that are not
  permitted to allocate.
- Reduced trie allocator bitmap scans and added CPU benchmarks.
- Reduced KMSAN and stack depot printing stack use.
- Documented the shared pool budget, child limit, and 64 KiB handle limit.
- Expanded KUnit coverage for public APIs, insertion shapes, trace depths,
  and frame encoding.
- Link to v1: https://patch.msgid.link/20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com

---
Caleb Kan (11):
      stackdepot: stop preallocating after the final pool
      stackdepot: add caller-owned stack trace fetching
      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 architecture hooks for compact frame storage
      stackdepot: share persistent stack prefixes with trie storage
      stackdepot: add KUnit tests 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                      |   83 +-
 lib/Kconfig.debug                               |   17 +
 lib/stackdepot.c                                | 1650 ++++++++++++++++++++++-
 lib/tests/Makefile                              |    1 +
 lib/tests/stackdepot_kunit.c                    |  582 ++++++++
 mm/kmemleak.c                                   |    4 +-
 mm/kmsan/kmsan_test.c                           |    4 +-
 mm/kmsan/report.c                               |   28 +-
 mm/page_owner.c                                 |    6 +-
 mm/slub.c                                       |   12 +-
 scripts/gdb/linux/stackdepot.py                 |    4 +
 18 files changed, 2454 insertions(+), 49 deletions(-)
---
base-commit: d118502628f8b673be9023db8bdf878f64a7ed45
change-id: 20260807-stackdepot-trie-2de15a2dcf97

Best regards,
--  
Caleb Kan <ckan@cloudflare.com>