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

[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@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>

[PATCH RFC 1/9] stackdepot: share persistent stack prefixes with trie storage

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

Stack depot's hash backend deduplicates only identical stored traces.
Persistent, non-refcounted users do not evict records, so distinct traces
consume full records even when they share long frame sequences. After pool
storage is exhausted, a persistent save of a previously unseen trace
returns 0.

Add a path-compressed trie as a second backend for these records. Store a
run of frames in each node, keep children sorted by their first frame, and
support insertion by descending through matches, splitting partial matches,
promoting an internal node to a terminal node, or attaching a new suffix.

Use otherwise invalid pool-index values in the existing 32-bit handle
layout to encode dense stack IDs. Map each ID to its terminal node through
a sparse side table so fetch can reconstruct the trace by following parent
links. Saved stacks and IDs remain stable and are not recycled.

Add architecture hooks for compact frame storage. arm64 uses an exactly
round-trippable signed 32-bit offset from _text. Native x86-64 stores the
low 32 bits when the upper 32 bits are all set. Keep frames raw when
compression would not round trip, and provide a generic implementation that
always uses raw frames.

Allocate trie nodes and child containers from contiguous runs of 16-byte
slots in the existing order-2 stack depot pools. Release unpublished
reservations immediately. Retire replaced published storage with RCU
grace-period cookies and make its slots available to later insertions only
after the grace period completes.

Share stack_pools and the configured physical pool limit with the hash
backend. Mark pools assigned to trie slots unavailable for hash record
allocation, so total stack depot capacity remains bounded by the existing
pool budget.

Bound insertion to three attempts: another writer may consume the cached
new_pool after the lockless check, while a maximum-depth insertion can
require two newly registered pools.

Serialize writers with a raw spinlock and publish topology through RCU.
Complete fallible reservations before publishing a stack. Publish
side-table mappings before topology exposes their nodes, and replace child
containers for non-tail updates. Allow sorted appends to publish into
unused tail capacity before increasing the visible child count.

Add stack_depot_fetch_into() to materialize either backend in caller-owned
storage. Keep stack_depot_fetch() hash-only because its pointer-returning
interface requires contiguous depot-owned records. Make
stack_depot_print() and stack_depot_snprint() support both backends.

Keep STACK_DEPOT_FLAG_GET records on the hash backend. A trie-eligible
save that is not allowed to allocate performs a single lockless lookup and
returns 0 on a miss. Trie insertion failures do not fall back to hash
storage.

Live KASAN observations from the complete series yielded directional
estimates of 31.5% lower backend-specific storage per record on arm64 and
42.6% lower on x86-64 with trie storage enabled. One collection in each
comparison raced, and the machines saw different stack populations. These
are approximate observations, not a matched memory comparison. Misses for
traces seen only by non-allocating saves are unobservable, so the
measurements do not establish equivalent diagnostic coverage.

Do not initialize or enable trie storage in this patch. Existing
consumers continue to receive hash handles while later patches make their
access paths backend-independent, keep them explicitly hash-backed, or
reject trie handles. The final patch adds boot-time activation.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 arch/arm64/include/asm/stackdepot.h |   42 ++
 arch/um/include/asm/Kbuild          |    1 +
 arch/x86/include/asm/stackdepot.h   |   37 +
 include/asm-generic/Kbuild          |    1 +
 include/asm-generic/stackdepot.h    |   19 +
 include/linux/stackdepot.h          |   67 +-
 lib/stackdepot.c                    | 1368 ++++++++++++++++++++++++++++++++++-
 7 files changed, 1521 insertions(+), 14 deletions(-)

diff --git a/arch/arm64/include/asm/stackdepot.h b/arch/arm64/include/asm/stackdepot.h
new file mode 100644
index 000000000000..df8959d59336
--- /dev/null
+++ b/arch/arm64/include/asm/stackdepot.h
@@ -0,0 +1,42 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __ASM_STACKDEPOT_H
+#define __ASM_STACKDEPOT_H
+
+#include <linux/types.h>
+#include <asm/sections.h>
+
+/*
+ * Modules are allocated inside a 2 GB relocation window containing the
+ * kernel image. Store a signed 32-bit offset from _text so compression is
+ * independent of 4 GB high-bit boundaries crossed by that window.
+ */
+static inline unsigned long arch_stack_depot_frame_from_payload(u32 payload)
+{
+	long offset;
+
+	offset = (s32)payload;
+	if (offset < 0)
+		return (unsigned long)_text - (unsigned long)(-offset);
+	return (unsigned long)_text + (unsigned long)offset;
+}
+
+static inline bool
+arch_stack_depot_frame_try_compress(unsigned long frame, u32 *payload)
+{
+	u32 candidate;
+
+	candidate = (u32)(frame - (unsigned long)_text);
+	if (arch_stack_depot_frame_from_payload(candidate) != frame)
+		return false;
+
+	*payload = candidate;
+	return true;
+}
+
+static inline void
+arch_stack_depot_frame_decompress(u32 payload, unsigned long *frame)
+{
+	*frame = arch_stack_depot_frame_from_payload(payload);
+}
+
+#endif /* __ASM_STACKDEPOT_H */
diff --git a/arch/um/include/asm/Kbuild b/arch/um/include/asm/Kbuild
index 8fdc0bd9ab6f..14778d2457d7 100644
--- a/arch/um/include/asm/Kbuild
+++ b/arch/um/include/asm/Kbuild
@@ -21,6 +21,7 @@ generic-y += preempt.h
 generic-y += ring_buffer.h
 generic-y += runtime-const.h
 generic-y += softirq_stack.h
+generic-y += stackdepot.h
 generic-y += switch_to.h
 generic-y += topology.h
 generic-y += trace_clock.h
diff --git a/arch/x86/include/asm/stackdepot.h b/arch/x86/include/asm/stackdepot.h
new file mode 100644
index 000000000000..9a8d04fa8c1c
--- /dev/null
+++ b/arch/x86/include/asm/stackdepot.h
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _ASM_X86_STACKDEPOT_H
+#define _ASM_X86_STACKDEPOT_H
+
+#include <linux/types.h>
+
+#ifdef CONFIG_X86_64
+/*
+ * Compress canonical kernel text/module addresses whose upper 32 bits are all
+ * ones. Other kernel virtual addresses stay raw, so decompression reconstructs
+ * the original frame by restoring this prefix.
+ */
+#define STACK_DEPOT_X86_64_FRAME_PREFIX	0xffffffff00000000UL
+#define STACK_DEPOT_X86_64_FRAME_LOW_MASK	0x00000000ffffffffUL
+
+static inline bool
+arch_stack_depot_frame_try_compress(unsigned long frame, u32 *low)
+{
+	if ((frame & ~STACK_DEPOT_X86_64_FRAME_LOW_MASK) !=
+	    STACK_DEPOT_X86_64_FRAME_PREFIX)
+		return false;
+
+	*low = (u32)frame;
+	return true;
+}
+
+static inline void
+arch_stack_depot_frame_decompress(u32 low, unsigned long *frame)
+{
+	*frame = STACK_DEPOT_X86_64_FRAME_PREFIX | low;
+}
+
+#else
+#include <asm-generic/stackdepot.h>
+#endif /* CONFIG_X86_64 */
+
+#endif /* _ASM_X86_STACKDEPOT_H */
diff --git a/include/asm-generic/Kbuild b/include/asm-generic/Kbuild
index 15df9dcb42a5..ac178162fa11 100644
--- a/include/asm-generic/Kbuild
+++ b/include/asm-generic/Kbuild
@@ -55,6 +55,7 @@ mandatory-y += serial.h
 mandatory-y += shmparam.h
 mandatory-y += simd.h
 mandatory-y += softirq_stack.h
+mandatory-y += stackdepot.h
 mandatory-y += switch_to.h
 mandatory-y += timex.h
 mandatory-y += tlbflush.h
diff --git a/include/asm-generic/stackdepot.h b/include/asm-generic/stackdepot.h
new file mode 100644
index 000000000000..846975767bdd
--- /dev/null
+++ b/include/asm-generic/stackdepot.h
@@ -0,0 +1,19 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __ASM_GENERIC_STACKDEPOT_H
+#define __ASM_GENERIC_STACKDEPOT_H
+
+#include <linux/types.h>
+
+static inline bool
+arch_stack_depot_frame_try_compress(unsigned long frame, u32 *low)
+{
+	return false;
+}
+
+static inline void
+arch_stack_depot_frame_decompress(u32 low, unsigned long *frame)
+{
+	/* Generic code never compresses frames, so this hook is unreachable. */
+}
+
+#endif /* __ASM_GENERIC_STACKDEPOT_H */
diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h
index 2cc21ffcdaf9..96544fc684a5 100644
--- a/include/linux/stackdepot.h
+++ b/include/linux/stackdepot.h
@@ -144,6 +144,10 @@ static inline int stack_depot_early_init(void)	{ return 0; }
  * Users of this flag must also call stack_depot_put() when keeping the stack
  * trace is no longer required to avoid overflowing the refcount.
  *
+ * When trie storage is enabled, persistent non-refcounted saves use trie
+ * storage. Constrained callers only look up existing stacks; they do not insert
+ * a missing stack. Trie failures do not fall back to hash storage.
+ *
  * If the provided stack trace comes from the interrupt context, only the part
  * up to the interrupt entry is saved.
  *
@@ -152,7 +156,7 @@ static inline int stack_depot_early_init(void)	{ return 0; }
  *          this is the case for contexts where neither %GFP_ATOMIC nor
  *          %GFP_NOWAIT can be used (NMI, raw_spin_lock).
  *
- * Return: Handle of the stack struct stored in depot, 0 on failure
+ * Return: Handle of the stack trace stored in depot, 0 on failure
  */
 depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
 					    unsigned int nr_entries,
@@ -169,6 +173,10 @@ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
  * Does not increment the refcount on the saved stack trace; see
  * stack_depot_save_flags() for more details.
  *
+ * When trie storage is enabled, this can return trie-backed handles. Use
+ * stack_depot_fetch_into(), stack_depot_print(), or stack_depot_snprint() for
+ * backend-independent access to the stack contents.
+ *
  * Context: Contexts where allocations via alloc_pages() are allowed;
  *          see stack_depot_save_flags() for more details.
  *
@@ -178,7 +186,7 @@ depot_stack_handle_t stack_depot_save(unsigned long *entries,
 				      unsigned int nr_entries, gfp_t alloc_flags);
 
 /**
- * __stack_depot_get_stack_record - Get a pointer to a stack_record struct
+ * __stack_depot_get_stack_record - Get a hash-backed stack record
  *
  * @handle: Stack depot handle
  *
@@ -191,14 +199,55 @@ struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle)
 /**
  * stack_depot_fetch - Fetch a stack trace from stack depot
  *
- * @handle:	Stack depot handle returned from stack_depot_save()
+ * @handle:	Hash-backed stack depot handle
  * @entries:	Pointer to store the address of the stack trace
  *
+ * This helper returns a pointer to stackdepot-owned contiguous storage for
+ * legacy hash-backed handles. Callers that need backend-independent access to
+ * stack contents should use stack_depot_fetch_into(), stack_depot_print(), or
+ * stack_depot_snprint(). Passing a trie-backed handle is invalid and may WARN.
+ *
  * Return: Number of frames for the fetched stack
  */
 unsigned int stack_depot_fetch(depot_stack_handle_t handle,
 			       unsigned long **entries);
 
+/**
+ * stack_depot_fetch_into - Fetch a stack trace into caller-owned storage
+ *
+ * @handle:	Stack depot handle
+ * @entries:	Caller-owned buffer to copy the stack trace into
+ * @max_entries:	Number of frames that fit in @entries
+ *
+ * Copies the stored frames into caller-owned @entries. If fewer frames are
+ * stored than @max_entries, only the stored frames are written and their count
+ * is returned. If more frames are stored than @max_entries, the copy is skipped
+ * entirely and 0 is returned.
+ *
+ * Passing a NULL @entries buffer or zero @max_entries for a valid @handle is
+ * invalid. Callers must provide storage for @max_entries frames.
+ *
+ * Callers should size @entries to match the save-side stack depth cap (for
+ * example, %CONFIG_STACKDEPOT_MAX_FRAMES or the local stack_trace_save() limit)
+ * when losing diagnostics on an undersized buffer would be surprising.
+ *
+ * A non-zero invalid @handle, including a post-put handle, may WARN. Its return
+ * value and copied contents are undefined because the record may have been
+ * reused for another stack.
+ *
+ * Callers must ensure @handle remains valid for the duration of this call.
+ * Persistent handles saved without %STACK_DEPOT_FLAG_GET require no extra
+ * reference; handles saved with %STACK_DEPOT_FLAG_GET require a held reference.
+ * Callers must not call stack_depot_put() on persistent handles.
+ * Racing this helper with stack_depot_put() on the same handle is invalid.
+ *
+ * Return: Number of frames copied, 0 if @handle is 0, stack depot is disabled,
+ * or @max_entries is less than the number of stored frames.
+ */
+unsigned int stack_depot_fetch_into(depot_stack_handle_t handle,
+				    unsigned long *entries,
+				    unsigned int max_entries);
+
 /**
  * stack_depot_print - Print a stack trace from stack depot
  *
@@ -224,10 +273,14 @@ int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size,
  *
  * @handle:	Stack depot handle returned from stack_depot_save()
  *
- * The stack trace is evicted from stack depot once all references to it have
- * been dropped (once the number of stack_depot_evict() calls matches the
- * number of stack_depot_save_flags() calls with STACK_DEPOT_FLAG_GET set for
- * this stack trace).
+ * Drop a reference acquired by stack_depot_save_flags() with
+ * %STACK_DEPOT_FLAG_GET. Calling this for a handle saved without
+ * %STACK_DEPOT_FLAG_GET is invalid; persistent handles, including trie-backed
+ * handles, are owned by stack depot for the lifetime of the system.
+ *
+ * The stack trace is evicted once the number of stack_depot_put() calls matches
+ * the number of successful stack_depot_save_flags() calls with
+ * %STACK_DEPOT_FLAG_GET for this stack trace.
  */
 void stack_depot_put(depot_stack_handle_t handle);
 
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index dd2717ff94bf..0278b7a013f1 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -2,9 +2,10 @@
 /*
  * Stack depot - a stack trace storage that avoids duplication.
  *
- * Internally, stack depot maintains a hash table of unique stacktraces. The
- * stack traces themselves are stored contiguously one after another in a set
- * of separate page allocations.
+ * Internally, stack depot has two storage backends. Refcounted entries use the
+ * legacy hash table with contiguous stack records in stack pools. Persistent
+ * non-refcounted entries can use trie storage when enabled; trie nodes share
+ * common frame prefixes and are published through RCU children containers.
  *
  * Author: Alexander Potapenko <glider@google.com>
  * Copyright (C) 2016 Google, Inc.
@@ -14,10 +15,15 @@
 
 #define pr_fmt(fmt) "stackdepot: " fmt
 
+#include <linux/bitmap.h>
+#include <linux/build_bug.h>
 #include <linux/debugfs.h>
+#include <linux/errno.h>
 #include <linux/gfp.h>
 #include <linux/jhash.h>
+#include <linux/jump_label.h>
 #include <linux/kernel.h>
+#include <linux/log2.h>
 #include <linux/kmsan.h>
 #include <linux/list.h>
 #include <linux/mm.h>
@@ -36,9 +42,12 @@
 #include <linux/memblock.h>
 #include <linux/kasan-enabled.h>
 
+#include <asm/stackdepot.h>
+
 /*
  * The pool_index is offset by 1 so the first record does not have a 0 handle.
  */
+/* Parsed before mm_core_init(); trie handle decoding assumes this is then fixed. */
 static unsigned int stack_max_pools __read_mostly =
 	MIN((1LL << DEPOT_POOL_INDEX_BITS) - 1, 8192);
 
@@ -63,18 +72,18 @@ static unsigned int stack_hash_mask;
 
 /* The lock must be held when performing pool or freelist modifications. */
 static DEFINE_RAW_SPINLOCK(pool_lock);
-/* Array of memory regions that store stack records. */
+/* Array of memory regions used by both stack depot backends. */
 static void **stack_pools __pt_guarded_by(&pool_lock);
 /* Newly allocated pool that is not yet added to stack_pools. */
 static void *new_pool;
 /* Number of pools in stack_pools. */
 static int pools_num;
-/* Offset to the unused space in the currently used pool. */
+/* Offset to unused hash storage in the current pool. */
 static size_t pool_offset __guarded_by(&pool_lock) = DEPOT_POOL_SIZE;
 /* Freelist of stack records within stack_pools. */
 static __guarded_by(&pool_lock) LIST_HEAD(free_stacks);
 
-/* Statistics counters for debugfs. */
+/* Hash-backend statistics counters for debugfs. */
 enum depot_counter_id {
 	DEPOT_COUNTER_REFD_ALLOCS,
 	DEPOT_COUNTER_REFD_FREES,
@@ -95,6 +104,552 @@ static const char *const counter_names[] = {
 };
 static_assert(ARRAY_SIZE(counter_names) == DEPOT_COUNTER_COUNT);
 
+enum stack_depot_frame_mode {
+	STACK_DEPOT_FRAME_RAW,
+	STACK_DEPOT_FRAME_COMPRESSED,
+};
+
+/*
+ * A trie node stores one run of frames that all use the same payload format.
+ * Architectures may compress some frames to 32-bit payloads; mixed raw and
+ * compressed input is split across multiple trie nodes so each node has one
+ * decoding mode.
+ */
+struct stack_depot_frame_run {
+	u16 nr_entries;
+	u8 mode;
+};
+
+static_assert(CONFIG_STACKDEPOT_MAX_FRAMES <= U16_MAX);
+
+struct stack_depot_trie_children;
+
+struct stack_depot_trie_node {
+	/* Parent links let fetch rebuild a full stack from a node to the root. */
+	const struct stack_depot_trie_node __rcu *parent;
+	/* Children are RCU-published containers. */
+	const struct stack_depot_trie_children __rcu *children;
+	/* Non-zero when a stored stack ends at this node. */
+	u32 stack_id;
+	struct stack_depot_frame_run run;
+	unsigned char data[];
+};
+
+/*
+ * Child nodes are sorted by first frame and searched by insertion position.
+ * Existing child pointers are immutable. Writers may publish into unused tail
+ * capacity; other updates publish a replacement container.
+ */
+struct stack_depot_trie_children {
+	unsigned int nr_children;
+	unsigned int capacity;
+	const struct stack_depot_trie_node __rcu *nodes[];
+};
+
+/* Retired children carry an optional node through their RCU grace period. */
+struct stack_depot_trie_retired_children {
+	struct list_head list;
+	unsigned long rcu_state;
+	const struct stack_depot_trie_node *pending_node;
+	unsigned char data[];
+};
+
+static_assert(IS_ALIGNED(offsetof(struct stack_depot_trie_retired_children, data),
+			 1UL << DEPOT_STACK_ALIGN));
+
+#define STACK_DEPOT_TRIE_SLOT_SIZE BIT(DEPOT_STACK_ALIGN)
+#define STACK_DEPOT_TRIE_POOL_SLOTS \
+	(DEPOT_POOL_SIZE / STACK_DEPOT_TRIE_SLOT_SIZE)
+
+struct stack_depot_trie_pool {
+	struct list_head list;
+	unsigned int free_slots;
+	DECLARE_BITMAP(used, STACK_DEPOT_TRIE_POOL_SLOTS);
+};
+
+#define STACK_DEPOT_TRIE_POOL_FIRST_SLOT \
+	DIV_ROUND_UP(sizeof(struct stack_depot_trie_pool), \
+		     STACK_DEPOT_TRIE_SLOT_SIZE)
+#define STACK_DEPOT_TRIE_POOL_USABLE_SIZE \
+	((STACK_DEPOT_TRIE_POOL_SLOTS - STACK_DEPOT_TRIE_POOL_FIRST_SLOT) * \
+	 STACK_DEPOT_TRIE_SLOT_SIZE)
+
+static_assert(STACK_DEPOT_TRIE_POOL_FIRST_SLOT < STACK_DEPOT_TRIE_POOL_SLOTS);
+
+static DEFINE_STATIC_KEY_FALSE(stack_depot_trie_enabled);
+static const struct stack_depot_trie_children __rcu *stack_depot_trie_root;
+static DEFINE_RAW_SPINLOCK(stack_depot_trie_writer_lock);
+
+#define DEPOT_POOL_INDEX_MASK ((1U << DEPOT_POOL_INDEX_BITS) - 1)
+#define DEPOT_OFFSET_MASK ((1U << DEPOT_OFFSET_BITS) - 1)
+
+/* Retired fixed-size slots remain reserved until their RCU grace period ends. */
+static LIST_HEAD(stack_depot_trie_pools);
+static LIST_HEAD(pending_trie_children);
+
+/*
+ * stack_max_pools is the split point between hash and trie handle encodings.
+ * A handle with pool_index_plus_1 in 1..stack_max_pools names a hash-backed
+ * stack pool. Larger pool-index values cannot refer to hash pools, so trie
+ * storage uses that handle space to encode a dense stack ID. The side table
+ * maps each stack ID to its trie node.
+ */
+static inline u32 trie_max_stack_id(void)
+{
+	return (DEPOT_POOL_INDEX_MASK - stack_max_pools) <<
+		DEPOT_OFFSET_BITS;
+}
+
+static depot_stack_handle_t trie_handle(u32 stack_id)
+{
+	union handle_parts parts = {};
+	u64 pool_index_plus_1;
+	u32 pool_delta;
+	u32 index;
+
+	index = stack_id - 1;
+	pool_delta = index >> DEPOT_OFFSET_BITS;
+	pool_index_plus_1 = (u64)stack_max_pools + 1 + pool_delta;
+
+	parts.pool_index_plus_1 = pool_index_plus_1;
+	parts.offset = index & DEPOT_OFFSET_MASK;
+	return parts.handle;
+}
+
+static inline bool stack_depot_handle_is_trie(depot_stack_handle_t handle)
+{
+	union handle_parts parts = { .handle = handle };
+
+	return parts.pool_index_plus_1 > stack_max_pools;
+}
+
+static u32 trie_stack_id(depot_stack_handle_t handle)
+{
+	union handle_parts parts = { .handle = handle };
+	u32 pool_delta;
+
+	pool_delta = parts.pool_index_plus_1 - stack_max_pools - 1;
+	return (pool_delta << DEPOT_OFFSET_BITS) + parts.offset + 1;
+}
+
+/*
+ * Trie handles encode a dense stack ID. The side table maps that ID to a node
+ * pointer for lockless fetch and print paths, which can run from diagnostic
+ * contexts where taking a lock would be unsafe. Additional directories and
+ * chunks are published lazily as stack IDs grow.
+ */
+#define STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE \
+	(PAGE_SIZE / sizeof(struct stack_depot_trie_node *))
+#define STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE \
+	(PAGE_SIZE / sizeof(struct stack_depot_trie_node **))
+
+struct stack_depot_trie_side_dir {
+	/* Both the chunk pointer and each node pointer in it are RCU-published. */
+	const struct stack_depot_trie_node __rcu * __rcu *
+		chunks[STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE];
+};
+
+struct stack_depot_trie_side_root {
+	unsigned int dir_capacity;
+	struct stack_depot_trie_side_dir __rcu *dirs[];
+};
+
+struct stack_depot_trie_side_prealloc {
+	/* Preallocated side-table directory page for sparse growth. */
+	struct stack_depot_trie_side_dir *dir;
+	/* Preallocated side-table pointer chunk for sparse growth. */
+	const struct stack_depot_trie_node __rcu **chunk;
+};
+
+static struct stack_depot_trie_side_root *trie_side_table_root;
+static DEFINE_RAW_SPINLOCK(trie_side_table_cache_lock);
+/* Zeroed unpublished pages; get/put transfer ownership under the cache lock. */
+static struct stack_depot_trie_side_prealloc trie_side_table_cache;
+static u32 trie_side_table_last_stack_id;
+
+/* Lock order: writer_lock -> pool_lock. The cache lock is never nested. */
+
+static inline size_t stack_depot_frame_run_entry_bytes(enum stack_depot_frame_mode mode)
+{
+	if (mode == STACK_DEPOT_FRAME_COMPRESSED)
+		return sizeof(u32);
+	return sizeof(unsigned long);
+}
+
+static inline size_t stack_depot_frame_run_bytes(const struct stack_depot_frame_run *run)
+{
+	return run->nr_entries * stack_depot_frame_run_entry_bytes(run->mode);
+}
+
+static inline size_t trie_node_bytes(const struct stack_depot_frame_run *run)
+{
+	return ALIGN(offsetof(struct stack_depot_trie_node, data) +
+		     stack_depot_frame_run_bytes(run), sizeof(unsigned long));
+}
+
+static size_t trie_children_alloc_size(unsigned int capacity)
+{
+	size_t size;
+
+	size = struct_size_t(struct stack_depot_trie_children, nodes,
+			     capacity);
+	return offsetof(struct stack_depot_trie_retired_children, data) +
+		ALIGN(size, sizeof(unsigned long));
+}
+
+static inline unsigned int trie_side_table_root_index(u32 id)
+{
+	return ((id - 1) / STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE) /
+		STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE;
+}
+
+static inline unsigned int trie_side_table_dir_index(u32 id)
+{
+	return ((id - 1) / STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE) %
+		STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE;
+}
+
+static inline unsigned int trie_side_table_slot_index(u32 id)
+{
+	return (id - 1) % STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE;
+}
+
+static struct stack_depot_trie_side_dir *trie_side_table_load_dir(unsigned int root)
+{
+	struct stack_depot_trie_side_root *root_vec;
+
+	root_vec = trie_side_table_root;
+	if (!root_vec || root >= root_vec->dir_capacity)
+		return NULL;
+	/* Pairs with side-table directory rcu_assign_pointer(). */
+	return rcu_dereference_check(root_vec->dirs[root],
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static inline const struct stack_depot_trie_node __rcu **
+trie_side_table_dir_load_chunk(struct stack_depot_trie_side_dir *dir,
+			       unsigned int idx)
+{
+	/* Pairs with the chunk rcu_assign_pointer() in stack ID preparation. */
+	return rcu_dereference_check(dir->chunks[idx],
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static u32
+trie_side_table_prepare_stack_slot(struct stack_depot_trie_side_prealloc *prealloc)
+{
+	const struct stack_depot_trie_node __rcu **chunk;
+	struct stack_depot_trie_side_dir *dir;
+	struct stack_depot_trie_side_root *root_vec;
+	unsigned int root;
+	unsigned int idx;
+	u32 id;
+
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+
+	id = trie_side_table_last_stack_id + 1;
+	if (id > trie_max_stack_id())
+		return 0;
+
+	root_vec = trie_side_table_root;
+	root = trie_side_table_root_index(id);
+	dir = trie_side_table_load_dir(root);
+	if (!dir) {
+		dir = prealloc->dir;
+		prealloc->dir = NULL;
+		/* Publish the zeroed directory before readers can load it locklessly. */
+		rcu_assign_pointer(root_vec->dirs[root], dir);
+	}
+
+	idx = trie_side_table_dir_index(id);
+	chunk = trie_side_table_dir_load_chunk(dir, idx);
+	if (!chunk) {
+		chunk = prealloc->chunk;
+		prealloc->chunk = NULL;
+		rcu_assign_pointer(dir->chunks[idx], chunk);
+	}
+
+	return id;
+}
+
+static int trie_side_table_get_prealloc(gfp_t gfp_flags,
+					struct stack_depot_trie_side_prealloc *prealloc)
+{
+	unsigned long flags;
+
+	gfp_flags = gfp_nested_mask(gfp_flags);
+	raw_spin_lock_irqsave(&trie_side_table_cache_lock, flags);
+	prealloc->dir = trie_side_table_cache.dir;
+	prealloc->chunk = trie_side_table_cache.chunk;
+	trie_side_table_cache.dir = NULL;
+	trie_side_table_cache.chunk = NULL;
+	raw_spin_unlock_irqrestore(&trie_side_table_cache_lock, flags);
+
+	if (!prealloc->dir) {
+		prealloc->dir = (void *)get_zeroed_page(gfp_flags);
+		if (!prealloc->dir)
+			return -ENOMEM;
+	}
+	if (!prealloc->chunk) {
+		prealloc->chunk = (void *)get_zeroed_page(gfp_flags);
+		if (!prealloc->chunk)
+			return -ENOMEM;
+	}
+
+	return 0;
+}
+
+static void trie_side_table_put_prealloc(struct stack_depot_trie_side_prealloc *prealloc)
+{
+	unsigned long flags;
+
+	raw_spin_lock_irqsave(&trie_side_table_cache_lock, flags);
+	if (!trie_side_table_cache.dir) {
+		trie_side_table_cache.dir = prealloc->dir;
+		prealloc->dir = NULL;
+	}
+	if (!trie_side_table_cache.chunk) {
+		trie_side_table_cache.chunk = prealloc->chunk;
+		prealloc->chunk = NULL;
+	}
+	raw_spin_unlock_irqrestore(&trie_side_table_cache_lock, flags);
+
+	if (prealloc->dir)
+		free_page((unsigned long)prealloc->dir);
+	if (prealloc->chunk)
+		free_page((unsigned long)prealloc->chunk);
+}
+
+static const struct stack_depot_trie_node *trie_side_table_lookup(u32 id)
+{
+	const struct stack_depot_trie_node __rcu **chunk;
+	struct stack_depot_trie_side_dir *dir;
+	unsigned int root;
+
+	root = trie_side_table_root_index(id);
+	dir = trie_side_table_load_dir(root);
+	if (!dir)
+		return NULL;
+	chunk = trie_side_table_dir_load_chunk(dir, trie_side_table_dir_index(id));
+	if (!chunk)
+		return NULL;
+
+	/* Pairs with side-table node publication. */
+	return rcu_dereference_check(chunk[trie_side_table_slot_index(id)],
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static inline struct stack_depot_trie_retired_children *
+trie_retired_children(const void *ptr)
+{
+	return container_of(ptr, struct stack_depot_trie_retired_children, data);
+}
+
+static bool depot_init_pool(void **prealloc);
+
+static unsigned int trie_pool_reserve_slots(struct stack_depot_trie_pool *pool,
+					    unsigned int nr_slots)
+{
+	unsigned int run = 0;
+	unsigned int i;
+	unsigned int slot;
+
+	if (pool->free_slots < nr_slots)
+		return STACK_DEPOT_TRIE_POOL_SLOTS;
+
+	/* A free run can cross any previous allocation position. */
+	for (slot = STACK_DEPOT_TRIE_POOL_FIRST_SLOT;
+	     slot < STACK_DEPOT_TRIE_POOL_SLOTS; slot++) {
+		if (pool->used[slot / BITS_PER_LONG] &
+		    BIT(slot % BITS_PER_LONG)) {
+			run = 0;
+			continue;
+		}
+		if (++run != nr_slots)
+			continue;
+
+		for (i = slot + 1 - nr_slots; i <= slot; i++)
+			pool->used[i / BITS_PER_LONG] |= BIT(i % BITS_PER_LONG);
+		pool->free_slots -= nr_slots;
+		return slot + 1 - nr_slots;
+	}
+
+	return STACK_DEPOT_TRIE_POOL_SLOTS;
+}
+
+/* Allocate at least @size bytes from one contiguous trie-pool slot run. */
+static void *trie_pool_alloc(size_t size, void **prealloc)
+{
+	struct stack_depot_trie_pool *pool;
+	unsigned int nr_slots;
+	unsigned int slot;
+
+	lockdep_assert_held(&pool_lock);
+
+	if (size > STACK_DEPOT_TRIE_POOL_USABLE_SIZE)
+		return NULL;
+	nr_slots = DIV_ROUND_UP(size, STACK_DEPOT_TRIE_SLOT_SIZE);
+	list_for_each_entry_reverse(pool, &stack_depot_trie_pools, list) {
+		slot = trie_pool_reserve_slots(pool, nr_slots);
+		if (slot != STACK_DEPOT_TRIE_POOL_SLOTS)
+			return (char *)pool + slot * STACK_DEPOT_TRIE_SLOT_SIZE;
+	}
+
+	if (!depot_init_pool(prealloc))
+		return NULL;
+	pool = stack_pools[pools_num - 1];
+	/* Keep hash records out of this bitmap-owned pool. */
+	pool_offset = DEPOT_POOL_SIZE;
+	memset(pool, 0, sizeof(*pool));
+	pool->free_slots = STACK_DEPOT_TRIE_POOL_SLOTS -
+			   STACK_DEPOT_TRIE_POOL_FIRST_SLOT;
+	list_add_tail(&pool->list, &stack_depot_trie_pools);
+
+	slot = trie_pool_reserve_slots(pool, nr_slots);
+	return (char *)pool + slot * STACK_DEPOT_TRIE_SLOT_SIZE;
+}
+
+/* Release the slots for the byte count originally passed to allocation. */
+static void trie_pool_release(const void *ptr, size_t size)
+{
+	struct stack_depot_trie_pool *pool;
+	unsigned long pfn;
+	unsigned int nr_slots;
+	unsigned int slot;
+	unsigned int i;
+
+	lockdep_assert_held(&pool_lock);
+
+	pfn = page_to_pfn(virt_to_page(ptr));
+	pfn &= ~(BIT(DEPOT_POOL_ORDER) - 1);
+	pool = page_address(pfn_to_page(pfn));
+	slot = ((unsigned long)ptr - (unsigned long)pool) >> DEPOT_STACK_ALIGN;
+	nr_slots = DIV_ROUND_UP(size, STACK_DEPOT_TRIE_SLOT_SIZE);
+	for (i = slot; i < slot + nr_slots; i++)
+		pool->used[i / BITS_PER_LONG] &= ~BIT(i % BITS_PER_LONG);
+	pool->free_slots += nr_slots;
+}
+
+static struct stack_depot_trie_children *
+trie_pool_alloc_children(unsigned int capacity, void **prealloc)
+{
+	struct stack_depot_trie_retired_children *retired;
+	struct stack_depot_trie_children *children;
+
+	/* Capacity counts child-pointer entries; allocation includes RCU metadata. */
+	retired = trie_pool_alloc(trie_children_alloc_size(capacity), prealloc);
+	if (!retired)
+		return NULL;
+
+	children = (void *)retired->data;
+	children->nr_children = 0;
+	children->capacity = capacity;
+	return children;
+}
+
+static void
+trie_pool_release_children(const struct stack_depot_trie_children *children)
+{
+	/* Capacity is immutable and therefore recovers the allocation byte size. */
+	trie_pool_release(trie_retired_children(children),
+			  trie_children_alloc_size(children->capacity));
+}
+
+/*
+ * Return RCU-ready objects before allocating. Pending children are FIFO, so
+ * stop at the first incomplete grace period. A replaced node shares the same
+ * retirement cookie and is released with its former children container.
+ */
+static void trie_drain_pending_children(void)
+{
+	struct stack_depot_trie_retired_children *retired;
+	struct stack_depot_trie_retired_children *tmp;
+	struct stack_depot_trie_children *children;
+
+	lockdep_assert_held(&pool_lock);
+
+	list_for_each_entry_safe(retired, tmp, &pending_trie_children, list) {
+		if (!poll_state_synchronize_rcu(retired->rcu_state))
+			break;
+		children = (void *)retired->data;
+		list_del(&retired->list);
+		if (retired->pending_node)
+			trie_pool_release(retired->pending_node,
+					  trie_node_bytes(&retired->pending_node->run));
+		trie_pool_release_children(children);
+	}
+}
+
+static void trie_retire_children(const struct stack_depot_trie_children *children)
+{
+	struct stack_depot_trie_retired_children *retired;
+
+	lockdep_assert_held(&pool_lock);
+
+	retired = trie_retired_children(children);
+	retired->pending_node = NULL;
+	retired->rcu_state = get_state_synchronize_rcu();
+	list_add_tail(&retired->list, &pending_trie_children);
+}
+
+static void
+trie_retire_children_with_node(const struct stack_depot_trie_children *children,
+			       const struct stack_depot_trie_node *node)
+{
+	struct stack_depot_trie_retired_children *retired;
+
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+	raw_spin_lock(&pool_lock);
+	trie_retire_children(children);
+	retired = trie_retired_children(children);
+	retired->pending_node = node;
+	raw_spin_unlock(&pool_lock);
+}
+
+static const struct stack_depot_trie_node *
+stack_depot_trie_lookup(const unsigned long *entries, unsigned int nr_entries);
+
+static depot_stack_handle_t
+trie_find_handle(const unsigned long *entries, unsigned int nr_entries)
+{
+	depot_stack_handle_t handle = 0;
+	const struct stack_depot_trie_node *node;
+
+	rcu_read_lock_sched_notrace();
+	node = stack_depot_trie_lookup(entries, nr_entries);
+	if (node)
+		handle = trie_handle(node->stack_id);
+	rcu_read_unlock_sched_notrace();
+
+	return handle;
+}
+
+/*
+ * Publish only after the node and its path are fully initialized and all
+ * fallible allocation is complete. Publication commits the path, so it cannot
+ * then be rolled back. Side-table mappings must precede trie topology
+ * publication that makes new or remapped nodes reachable from lookup.
+ * Published storage remains valid until RCU retirement; only descendant parent
+ * links may change meanwhile.
+ */
+static void trie_side_table_publish(const struct stack_depot_trie_node *node)
+{
+	const struct stack_depot_trie_node __rcu **chunk;
+	struct stack_depot_trie_side_dir *dir;
+	u32 stack_id = node->stack_id;
+
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+
+	dir = trie_side_table_load_dir(trie_side_table_root_index(stack_id));
+	chunk = trie_side_table_dir_load_chunk(dir,
+					       trie_side_table_dir_index(stack_id));
+	/* Pairs with trie_side_table_lookup(). */
+	rcu_assign_pointer(chunk[trie_side_table_slot_index(stack_id)], node);
+}
+
 static int __init disable_stack_depot(char *str)
 {
 	return kstrtobool(str, &stack_depot_disabled);
@@ -323,7 +878,7 @@ static bool depot_init_pool(void **prealloc)
 	 * NULL; do not reset to NULL if we have reached the maximum number of
 	 * pools.
 	 */
-	if (pools_num < stack_max_pools)
+	if (pools_num + 1 < stack_max_pools)
 		WRITE_ONCE(new_pool, NULL);
 	else
 		WRITE_ONCE(new_pool, STACK_DEPOT_POISON);
@@ -638,6 +1193,63 @@ static inline struct stack_record *find_stack(struct list_head *bucket,
 	return ret;
 }
 
+static u32
+stack_depot_trie_insert(const unsigned long *entries,
+			unsigned int nr_entries, void **pool_prealloc,
+			struct stack_depot_trie_side_prealloc *side_prealloc);
+
+static depot_stack_handle_t
+stack_depot_trie_save(unsigned long *entries, unsigned int nr_entries,
+		      gfp_t alloc_flags)
+{
+	unsigned int attempt;
+
+	/* Allow one stale pool hint before the two pools a largest insert needs. */
+	for (attempt = 0; attempt < 3; attempt++) {
+		struct stack_depot_trie_side_prealloc side_prealloc = {};
+		void *pool_prealloc = NULL;
+		depot_stack_handle_t handle;
+		unsigned long flags;
+		struct page *page;
+		u32 stack_id = 0;
+
+		handle = trie_find_handle(entries, nr_entries);
+		if (handle)
+			return handle;
+
+		if (trie_side_table_get_prealloc(alloc_flags, &side_prealloc)) {
+			trie_side_table_put_prealloc(&side_prealloc);
+			return 0;
+		}
+
+		/* The hint may race; a missing page is recovered by the retry. */
+		if (!READ_ONCE(new_pool)) {
+			page = alloc_pages(gfp_nested_mask(alloc_flags),
+					   DEPOT_POOL_ORDER);
+			if (page)
+				pool_prealloc = page_address(page);
+		}
+
+		raw_spin_lock_irqsave(&stack_depot_trie_writer_lock, flags);
+		stack_id = stack_depot_trie_insert(entries, nr_entries,
+						   &pool_prealloc, &side_prealloc);
+		raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags);
+
+		if (pool_prealloc) {
+			raw_spin_lock_irqsave(&pool_lock, flags);
+			depot_keep_new_pool(&pool_prealloc);
+			raw_spin_unlock_irqrestore(&pool_lock, flags);
+		}
+		if (pool_prealloc)
+			free_pages((unsigned long)pool_prealloc, DEPOT_POOL_ORDER);
+		trie_side_table_put_prealloc(&side_prealloc);
+		if (stack_id)
+			return trie_handle(stack_id);
+	}
+
+	return 0;
+}
+
 depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
 					    unsigned int nr_entries,
 					    gfp_t alloc_flags,
@@ -669,6 +1281,17 @@ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
 	if (unlikely(nr_entries == 0) || stack_depot_disabled)
 		return 0;
 
+	if (!(depot_flags & STACK_DEPOT_FLAG_GET) &&
+	    static_branch_unlikely(&stack_depot_trie_enabled)) {
+		if (nr_entries > CONFIG_STACKDEPOT_MAX_FRAMES)
+			nr_entries = CONFIG_STACKDEPOT_MAX_FRAMES;
+		if (in_nmi() || !can_alloc) {
+			WARN_ON_ONCE(can_alloc);
+			return trie_find_handle(entries, nr_entries);
+		}
+		return stack_depot_trie_save(entries, nr_entries, alloc_flags);
+	}
+
 	hash = hash_stack(entries, nr_entries);
 	bucket = &stack_table[hash & stack_hash_mask];
 
@@ -753,10 +1376,689 @@ struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle)
 {
 	if (!handle)
 		return NULL;
+	if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle)))
+		return NULL;
 
 	return depot_fetch_stack(handle);
 }
 
+static void frame_run_init(const unsigned long *entries,
+			   unsigned int nr_entries,
+			   struct stack_depot_frame_run *run)
+{
+	u32 payload;
+	unsigned int i;
+	bool compressed;
+
+	compressed = arch_stack_depot_frame_try_compress(entries[0], &payload);
+	for (i = 1; i < nr_entries; i++) {
+		bool next;
+
+		next = arch_stack_depot_frame_try_compress(entries[i], &payload);
+		if (next != compressed)
+			break;
+	}
+
+	/* @i is the first non-matching frame, or @nr_entries if all matched. */
+	run->mode = compressed ? STACK_DEPOT_FRAME_COMPRESSED : STACK_DEPOT_FRAME_RAW;
+	run->nr_entries = i;
+}
+
+static void
+stack_depot_trie_node_frame(const struct stack_depot_trie_node *node,
+			    unsigned int index, unsigned long *frame)
+{
+	u32 payload;
+
+	if (node->run.mode == STACK_DEPOT_FRAME_RAW) {
+		memcpy(frame, node->data + index * sizeof(*frame),
+		       sizeof(*frame));
+		return;
+	}
+
+	memcpy(&payload, node->data + index * sizeof(payload), sizeof(payload));
+	arch_stack_depot_frame_decompress(payload, frame);
+}
+
+static void trie_node_init(struct stack_depot_trie_node *node,
+			   const struct stack_depot_trie_node *parent, u32 stack_id,
+			   const unsigned long *entries,
+			   const struct stack_depot_frame_run *run)
+{
+	if (run->mode == STACK_DEPOT_FRAME_COMPRESSED) {
+		unsigned int i;
+
+		for (i = 0; i < run->nr_entries; i++) {
+			u32 payload;
+
+			arch_stack_depot_frame_try_compress(entries[i], &payload);
+			memcpy(node->data + i * sizeof(payload), &payload,
+			       sizeof(payload));
+		}
+	} else {
+		memcpy(node->data, entries, stack_depot_frame_run_bytes(run));
+	}
+
+	RCU_INIT_POINTER(node->parent, parent);
+	RCU_INIT_POINTER(node->children, NULL);
+	node->stack_id = stack_id;
+	node->run = *run;
+}
+
+static void trie_node_init_slice(struct stack_depot_trie_node *node,
+				 const struct stack_depot_trie_node *parent, u32 stack_id,
+				 const struct stack_depot_trie_node *src_node,
+				 unsigned int start, unsigned int nr_entries)
+{
+	struct stack_depot_frame_run run;
+	size_t entry_bytes;
+
+	run = src_node->run;
+	run.nr_entries = nr_entries;
+
+	entry_bytes = stack_depot_frame_run_entry_bytes(src_node->run.mode);
+	memcpy(node->data, src_node->data + start * entry_bytes,
+	       stack_depot_frame_run_bytes(&run));
+	RCU_INIT_POINTER(node->parent, parent);
+	RCU_INIT_POINTER(node->children, NULL);
+	node->stack_id = stack_id;
+	node->run = run;
+}
+
+static unsigned int trie_node_match(const struct stack_depot_trie_node *node,
+				    const unsigned long *entries,
+				    unsigned int nr_entries)
+{
+	unsigned int limit;
+	unsigned int i;
+
+	limit = min(node->run.nr_entries, nr_entries);
+	if (node->run.mode == STACK_DEPOT_FRAME_RAW) {
+		for (i = 0; i < limit; i++) {
+			unsigned long frame;
+
+			memcpy(&frame, node->data + i * sizeof(frame), sizeof(frame));
+			if (frame != entries[i])
+				break;
+		}
+
+		return i;
+	}
+
+	for (i = 0; i < limit; i++) {
+		unsigned long frame;
+
+		stack_depot_trie_node_frame(node, i, &frame);
+		if (frame != entries[i])
+			break;
+	}
+
+	return i;
+}
+
+static inline const struct stack_depot_trie_node *
+trie_load_parent(const struct stack_depot_trie_node *node)
+{
+	return rcu_dereference_check(node->parent,
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static inline const struct stack_depot_trie_children *
+trie_load_children(const struct stack_depot_trie_children __rcu * const *slot)
+{
+	return rcu_dereference_check(*slot,
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static inline const struct stack_depot_trie_node *
+trie_children_load_child(const struct stack_depot_trie_children *children,
+			 unsigned int pos)
+{
+	return rcu_dereference_check(children->nodes[pos],
+				     lockdep_is_held(&stack_depot_trie_writer_lock) ||
+				     rcu_read_lock_sched_held());
+}
+
+static bool
+trie_children_find_position(const struct stack_depot_trie_children *children,
+			    unsigned long frame, unsigned int *pos)
+{
+	unsigned int left = 0;
+	unsigned int right;
+
+	right = READ_ONCE(children->nr_children);
+	while (left < right) {
+		unsigned int mid = left + (right - left) / 2;
+		const struct stack_depot_trie_node *node;
+		unsigned long mid_frame;
+
+		node = trie_children_load_child(children, mid);
+		if (!node) {
+			/* Tail append may produce a transient lockless lookup miss. */
+			right = mid;
+			continue;
+		}
+		stack_depot_trie_node_frame(node, 0, &mid_frame);
+		if (mid_frame < frame) {
+			left = mid + 1;
+		} else if (mid_frame > frame) {
+			right = mid;
+		} else {
+			*pos = mid;
+			return true;
+		}
+	}
+
+	*pos = left;
+	return false;
+}
+
+/* Initialize an unpublished container from a stable published prefix. */
+static void trie_children_init(const struct stack_depot_trie_children *old,
+			       struct stack_depot_trie_children *new)
+{
+	unsigned int nr_old = old->nr_children;
+	unsigned int i;
+
+	new->nr_children = nr_old;
+	for (i = 0; i < nr_old; i++)
+		RCU_INIT_POINTER(new->nodes[i], trie_children_load_child(old, i));
+	for (i = nr_old; i < new->capacity; i++)
+		RCU_INIT_POINTER(new->nodes[i], NULL);
+}
+
+static void trie_children_insert(struct stack_depot_trie_children *children,
+				 const struct stack_depot_trie_node *node,
+				 unsigned int pos)
+{
+	unsigned int i;
+
+	for (i = children->nr_children; i > pos; i--)
+		RCU_INIT_POINTER(children->nodes[i],
+				 trie_children_load_child(children, i - 1));
+	RCU_INIT_POINTER(children->nodes[pos], node);
+	children->nr_children++;
+}
+
+static void trie_reparent_children(struct stack_depot_trie_node *parent)
+{
+	const struct stack_depot_trie_children *children;
+	unsigned int i;
+
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+
+	children = trie_load_children(&parent->children);
+	if (!children)
+		return;
+	/*
+	 * Replacement nodes reuse unchanged descendant subtrees. Repoint their
+	 * parent links before retiring the old parent so fetch never follows a freed
+	 * node. Lockless fetches may see the new parent before publication, but the
+	 * old and new parent chains contain the same frames and remain RCU-live.
+	 */
+	for (i = 0; i < children->nr_children; i++) {
+		struct stack_depot_trie_node *child;
+
+		child = (struct stack_depot_trie_node *)trie_children_load_child(children, i);
+		rcu_assign_pointer(child->parent, parent);
+	}
+}
+
+/*
+ * Split entries into runs, allocate and initialize each node once, and link
+ * adjacent nodes through singleton children. Both trie locks must be held.
+ * Failure walks the unpublished parent chain and releases local ownership.
+ */
+static const struct stack_depot_trie_node *
+trie_path_alloc(const struct stack_depot_trie_node *parent, u32 stack_id,
+		const unsigned long *entries, unsigned int nr_entries,
+		void **pool_prealloc,
+		const struct stack_depot_trie_node **node_out)
+{
+	struct stack_depot_trie_children *path_children = NULL;
+	const struct stack_depot_trie_node *path_root = NULL;
+	const struct stack_depot_trie_node *last_node = parent;
+	unsigned int entry = 0;
+
+	lockdep_assert_held(&pool_lock);
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+
+	while (entry < nr_entries) {
+		struct stack_depot_frame_run run;
+		struct stack_depot_trie_node *node;
+
+		frame_run_init(&entries[entry], nr_entries - entry, &run);
+		node = trie_pool_alloc(trie_node_bytes(&run), pool_prealloc);
+		if (!node)
+			goto err_release;
+
+		trie_node_init(node, last_node,
+			       entry + run.nr_entries == nr_entries ? stack_id : 0,
+			       &entries[entry], &run);
+		entry += run.nr_entries;
+		last_node = node;
+		if (!path_root)
+			path_root = node;
+
+		if (path_children)
+			trie_children_insert(path_children, last_node, 0);
+		if (entry < nr_entries) {
+			path_children = trie_pool_alloc_children(1, pool_prealloc);
+			if (!path_children)
+				goto err_release;
+			RCU_INIT_POINTER(node->children, path_children);
+		}
+	}
+
+	*node_out = last_node;
+	return path_root;
+
+err_release:
+	while (last_node != parent) {
+		const struct stack_depot_trie_children *node_children;
+		const struct stack_depot_trie_node *node = last_node;
+
+		last_node = trie_load_parent(node);
+		node_children = trie_load_children(&node->children);
+		if (node_children)
+			trie_pool_release_children(node_children);
+		trie_pool_release(node, trie_node_bytes(&node->run));
+	}
+	return NULL;
+}
+
+static const struct stack_depot_trie_node *
+stack_depot_trie_lookup(const unsigned long *entries, unsigned int nr_entries)
+{
+	const struct stack_depot_trie_children *children;
+	unsigned int entry = 0;
+
+	children = trie_load_children(&stack_depot_trie_root);
+
+	while (entry < nr_entries) {
+		const struct stack_depot_trie_node *node;
+		unsigned int remaining = nr_entries - entry;
+		unsigned int matched;
+		unsigned int pos;
+
+		if (!children)
+			return NULL;
+		if (!trie_children_find_position(children, entries[entry], &pos))
+			return NULL;
+
+		node = trie_children_load_child(children, pos);
+		matched = trie_node_match(node, &entries[entry], remaining);
+		if (matched < node->run.nr_entries)
+			return NULL;
+		entry += matched;
+		if (entry == nr_entries)
+			return node->stack_id ? node : NULL;
+
+		children = trie_load_children(&node->children);
+	}
+
+	return NULL;
+}
+
+static u32
+trie_insert_path(const struct stack_depot_trie_children __rcu **slot,
+		 struct stack_depot_trie_node *parent,
+		 const struct stack_depot_trie_children *children,
+		 unsigned int pos, const unsigned long *entries,
+		 unsigned int nr_entries, void **pool_prealloc,
+		 struct stack_depot_trie_side_prealloc *side_prealloc)
+{
+	struct stack_depot_trie_children *new_children = NULL;
+	const struct stack_depot_trie_node *path_root;
+	const struct stack_depot_trie_node *node;
+	unsigned int capacity = 1;
+	u32 new_stack_id;
+	bool tail_append = false;
+
+	/*
+	 * Reuse spare capacity only for a sorted tail append. Other insertions
+	 * replace the children container without modifying visible pointers.
+	 */
+	if (children) {
+		capacity = roundup_pow_of_two(children->nr_children + 1);
+		tail_append = pos == children->nr_children &&
+			children->nr_children < children->capacity;
+	}
+	if (!tail_append && trie_children_alloc_size(capacity) >
+	    STACK_DEPOT_TRIE_POOL_USABLE_SIZE)
+		return 0;
+
+	new_stack_id = trie_side_table_prepare_stack_slot(side_prealloc);
+	if (!new_stack_id)
+		return 0;
+
+	raw_spin_lock(&pool_lock);
+	printk_deferred_enter();
+	trie_drain_pending_children();
+
+	/* Reserve replacement topology before the path, the final fallible step. */
+	if (!tail_append) {
+		new_children = trie_pool_alloc_children(capacity, pool_prealloc);
+		if (!new_children)
+			goto err_release;
+	}
+	path_root = trie_path_alloc(parent, new_stack_id, entries, nr_entries,
+				    pool_prealloc, &node);
+	if (!path_root)
+		goto err_release;
+
+	/* Commit the stack ID before making the path reachable from the trie. */
+	trie_side_table_publish(node);
+	if (tail_append) {
+		struct stack_depot_trie_children *tail_children =
+			(struct stack_depot_trie_children *)children;
+
+		/*
+		 * Publish the node before the visible count. Readers may transiently
+		 * see NULL and miss; the writer-lock recheck prevents duplicates.
+		 */
+		rcu_assign_pointer(tail_children->nodes[pos], path_root);
+		WRITE_ONCE(tail_children->nr_children, pos + 1);
+	} else {
+		if (children)
+			trie_children_init(children, new_children);
+		trie_children_insert(new_children, path_root, pos);
+		rcu_assign_pointer(*slot, new_children);
+		if (children)
+			trie_retire_children(children);
+	}
+
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+	return new_stack_id;
+
+err_release:
+	if (new_children)
+		trie_pool_release_children(new_children);
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+	return 0;
+}
+
+static u32
+trie_split_child(const struct stack_depot_trie_children __rcu **slot,
+		 const struct stack_depot_trie_children *children,
+		 const struct stack_depot_trie_node *child,
+		 unsigned int pos, unsigned int matched,
+		 const unsigned long *entries, unsigned int nr_entries,
+		 void **pool_prealloc,
+		 struct stack_depot_trie_side_prealloc *side_prealloc)
+{
+	struct stack_depot_trie_children *prefix_children = NULL;
+	struct stack_depot_trie_children *new_children = NULL;
+	const struct stack_depot_trie_node *new_node;
+	const struct stack_depot_trie_node *suffix_roots[2];
+	struct stack_depot_frame_run run;
+	struct stack_depot_trie_node *split_prefix = NULL;
+	struct stack_depot_trie_node *old_suffix = NULL;
+	unsigned int nr_suffix_roots;
+	unsigned int old_suffix_len;
+	unsigned int i;
+	size_t split_prefix_size;
+	size_t old_suffix_size;
+	u32 new_stack_id;
+	bool has_new_suffix;
+
+	new_stack_id = trie_side_table_prepare_stack_slot(side_prealloc);
+	if (!new_stack_id)
+		return 0;
+
+	/* Rebuild the child's run as newly allocated prefix and old suffix nodes. */
+	run = child->run;
+	run.nr_entries = matched;
+	split_prefix_size = trie_node_bytes(&run);
+	old_suffix_len = child->run.nr_entries - matched;
+	run.nr_entries = old_suffix_len;
+	old_suffix_size = trie_node_bytes(&run);
+	has_new_suffix = matched < nr_entries;
+	nr_suffix_roots = has_new_suffix ? 2 : 1;
+
+	raw_spin_lock(&pool_lock);
+	printk_deferred_enter();
+	trie_drain_pending_children();
+
+	/* Reserve fixed split topology before the optional new suffix path. */
+	split_prefix = trie_pool_alloc(split_prefix_size, pool_prealloc);
+	if (!split_prefix)
+		goto err_release;
+	old_suffix = trie_pool_alloc(old_suffix_size, pool_prealloc);
+	if (!old_suffix)
+		goto err_release;
+	new_children = trie_pool_alloc_children(children->capacity, pool_prealloc);
+	if (!new_children)
+		goto err_release;
+	prefix_children = trie_pool_alloc_children(nr_suffix_roots, pool_prealloc);
+	if (!prefix_children)
+		goto err_release;
+
+	if (has_new_suffix) {
+		const struct stack_depot_trie_node *new_suffix;
+		unsigned long old_suffix_frame;
+
+		new_suffix = trie_path_alloc(split_prefix, new_stack_id,
+					     &entries[matched], nr_entries - matched,
+					     pool_prealloc, &new_node);
+		if (!new_suffix)
+			goto err_release;
+		stack_depot_trie_node_frame(child, matched, &old_suffix_frame);
+		/* Children remain sorted by the first frame of each suffix. */
+		if (old_suffix_frame < entries[matched]) {
+			suffix_roots[0] = old_suffix;
+			suffix_roots[1] = new_suffix;
+		} else {
+			suffix_roots[0] = new_suffix;
+			suffix_roots[1] = old_suffix;
+		}
+	} else {
+		new_node = split_prefix;
+		suffix_roots[0] = old_suffix;
+	}
+
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+
+	/* Rebuild the old path as prefix -> old suffix and attach suffix roots. */
+	trie_node_init_slice(split_prefix, trie_load_parent(child),
+			     has_new_suffix ? 0 : new_stack_id, child, 0, matched);
+	trie_node_init_slice(old_suffix, split_prefix, child->stack_id, child,
+			     matched, old_suffix_len);
+	for (i = 0; i < nr_suffix_roots; i++)
+		trie_children_insert(prefix_children, suffix_roots[i], i);
+	RCU_INIT_POINTER(old_suffix->children,
+			 trie_load_children(&child->children));
+	RCU_INIT_POINTER(split_prefix->children, prefix_children);
+
+	/* Publish IDs, reparent descendants, then replace and retire topology. */
+	if (child->stack_id)
+		trie_side_table_publish(old_suffix);
+	trie_side_table_publish(new_node);
+	/* Old and replacement chains contain identical frames during transition. */
+	trie_children_init(children, new_children);
+	RCU_INIT_POINTER(new_children->nodes[pos], split_prefix);
+	trie_reparent_children(old_suffix);
+	rcu_assign_pointer(*slot, new_children);
+	trie_retire_children_with_node(children, child);
+
+	return new_stack_id;
+
+err_release:
+	if (split_prefix)
+		trie_pool_release(split_prefix, split_prefix_size);
+	if (old_suffix)
+		trie_pool_release(old_suffix, old_suffix_size);
+	if (prefix_children)
+		trie_pool_release_children(prefix_children);
+	if (new_children)
+		trie_pool_release_children(new_children);
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+	return 0;
+}
+
+static u32
+trie_promote_child(const struct stack_depot_trie_children __rcu **slot,
+		   const struct stack_depot_trie_children *children,
+		   const struct stack_depot_trie_node *child,
+		   unsigned int pos, void **pool_prealloc,
+		   struct stack_depot_trie_side_prealloc *side_prealloc)
+{
+	struct stack_depot_trie_children *new_children;
+	struct stack_depot_trie_node *promoted_node;
+	size_t node_size;
+	u32 new_stack_id;
+
+	new_stack_id = trie_side_table_prepare_stack_slot(side_prealloc);
+	if (!new_stack_id)
+		return 0;
+	node_size = trie_node_bytes(&child->run);
+
+	/* Reserve a clone and replacement children container before publication. */
+	raw_spin_lock(&pool_lock);
+	printk_deferred_enter();
+	trie_drain_pending_children();
+	promoted_node = trie_pool_alloc(node_size, pool_prealloc);
+	if (!promoted_node)
+		goto out_unlock;
+	new_children = trie_pool_alloc_children(children->capacity, pool_prealloc);
+	if (!new_children)
+		goto out_release_node;
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+
+	/* Add the stack ID through a clone, then reparent before retirement. */
+	memcpy(promoted_node, child, node_size);
+	promoted_node->stack_id = new_stack_id;
+	trie_side_table_publish(promoted_node);
+	trie_children_init(children, new_children);
+	RCU_INIT_POINTER(new_children->nodes[pos], promoted_node);
+	trie_reparent_children(promoted_node);
+	rcu_assign_pointer(*slot, new_children);
+	trie_retire_children_with_node(children, child);
+
+	return new_stack_id;
+
+out_release_node:
+	trie_pool_release(promoted_node, node_size);
+out_unlock:
+	printk_deferred_exit();
+	raw_spin_unlock(&pool_lock);
+	return 0;
+}
+
+static u32
+stack_depot_trie_insert(const unsigned long *entries,
+			unsigned int nr_entries, void **pool_prealloc,
+			struct stack_depot_trie_side_prealloc *side_prealloc)
+{
+	const struct stack_depot_trie_children *children;
+	const struct stack_depot_trie_children __rcu **slot =
+		&stack_depot_trie_root;
+	const struct stack_depot_trie_node *child;
+	struct stack_depot_trie_node *parent = NULL;
+	unsigned int matched;
+	unsigned int pos;
+	u32 stack_id;
+
+	lockdep_assert_held(&stack_depot_trie_writer_lock);
+
+	for (;;) {
+		pos = 0;
+		children = trie_load_children(slot);
+		/* No matching child: attach the remaining path. */
+		if (!children ||
+		    !trie_children_find_position(children, entries[0], &pos)) {
+			stack_id = trie_insert_path(slot, parent, children, pos,
+						    entries, nr_entries, pool_prealloc,
+						    side_prealloc);
+			break;
+		}
+
+		child = trie_children_load_child(children, pos);
+		matched = trie_node_match(child, entries, nr_entries);
+		/* A partial child match requires a prefix/suffix split. */
+		if (matched < child->run.nr_entries) {
+			stack_id = trie_split_child(slot, children, child, pos,
+						    matched, entries, nr_entries,
+						    pool_prealloc, side_prealloc);
+			break;
+		}
+
+		/* The input ends here: reuse a stack node or promote an internal one. */
+		if (matched == nr_entries) {
+			if (child->stack_id)
+				return child->stack_id;
+			stack_id = trie_promote_child(slot, children, child, pos,
+						      pool_prealloc, side_prealloc);
+			break;
+		}
+
+		/* The child matched completely; continue with the remaining frames. */
+		parent = (struct stack_depot_trie_node *)child;
+		slot = &parent->children;
+		entries += matched;
+		nr_entries -= matched;
+	}
+
+	if (stack_id)
+		trie_side_table_last_stack_id = stack_id;
+	return stack_id;
+}
+
+static unsigned int trie_fetch_into(const struct stack_depot_trie_node *node,
+				    unsigned long *entries,
+				    unsigned int max_entries)
+{
+	const struct stack_depot_trie_node *cur;
+	unsigned int total;
+	unsigned int pos;
+	unsigned int i;
+
+	total = 0;
+	for (cur = node; cur; cur = trie_load_parent(cur))
+		total += cur->run.nr_entries;
+	if (max_entries < total)
+		return 0;
+
+	pos = total;
+	for (cur = node; cur; cur = trie_load_parent(cur)) {
+		pos -= cur->run.nr_entries;
+		for (i = 0; i < cur->run.nr_entries; i++)
+			stack_depot_trie_node_frame(cur, i, &entries[pos + i]);
+	}
+
+	return total;
+}
+
+static unsigned int trie_fetch_handle_into(depot_stack_handle_t handle,
+					   unsigned long *entries,
+					   unsigned int max_entries)
+{
+	const struct stack_depot_trie_node *node;
+	u32 stack_id;
+	unsigned int nr_entries;
+
+	stack_id = trie_stack_id(handle);
+	rcu_read_lock_sched_notrace();
+	node = trie_side_table_lookup(stack_id);
+	if (WARN_ONCE(!node, "corrupt trie handle %08x\n", handle)) {
+		rcu_read_unlock_sched_notrace();
+		return 0;
+	}
+	nr_entries = trie_fetch_into(node, entries, max_entries);
+	rcu_read_unlock_sched_notrace();
+	if (nr_entries)
+		kmsan_unpoison_memory(entries, nr_entries * sizeof(*entries));
+
+	return nr_entries;
+}
+
 unsigned int stack_depot_fetch(depot_stack_handle_t handle,
 			       unsigned long **entries)
 {
@@ -771,6 +2073,8 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,
 
 	if (!handle || stack_depot_disabled)
 		return 0;
+	if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle)))
+		return 0;
 
 	stack = depot_fetch_stack(handle);
 	/*
@@ -785,12 +2089,44 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,
 }
 EXPORT_SYMBOL_GPL(stack_depot_fetch);
 
+unsigned int stack_depot_fetch_into(depot_stack_handle_t handle,
+				    unsigned long *entries,
+				    unsigned int max_entries)
+{
+	struct stack_record *stack;
+	unsigned int nr_entries;
+
+	if (!handle)
+		return 0;
+	if (stack_depot_disabled)
+		return 0;
+	WARN_ON_ONCE(!entries || !max_entries);
+	if (stack_depot_handle_is_trie(handle))
+		return trie_fetch_handle_into(handle, entries, max_entries);
+
+	stack = depot_fetch_stack(handle);
+	if (!stack)
+		return 0;
+	nr_entries = stack->size;
+	if (WARN_ON_ONCE(!nr_entries))
+		return 0;
+	if (nr_entries > max_entries)
+		return 0;
+
+	memcpy(entries, stack->entries, nr_entries * sizeof(*entries));
+	kmsan_unpoison_memory(entries, nr_entries * sizeof(*entries));
+	return nr_entries;
+}
+EXPORT_SYMBOL_GPL(stack_depot_fetch_into);
+
 void stack_depot_put(depot_stack_handle_t handle)
 {
 	struct stack_record *stack;
 
 	if (!handle || stack_depot_disabled)
 		return;
+	if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle)))
+		return;
 
 	stack = depot_fetch_stack(handle);
 	/*
@@ -810,6 +2146,15 @@ void stack_depot_print(depot_stack_handle_t stack)
 	unsigned long *entries;
 	unsigned int nr_entries;
 
+	if (stack_depot_handle_is_trie(stack)) {
+		unsigned long trie_entries[CONFIG_STACKDEPOT_MAX_FRAMES];
+
+		nr_entries = trie_fetch_handle_into(stack, trie_entries,
+						    ARRAY_SIZE(trie_entries));
+		stack_trace_print(trie_entries, nr_entries, 0);
+		return;
+	}
+
 	nr_entries = stack_depot_fetch(stack, &entries);
 	if (nr_entries > 0)
 		stack_trace_print(entries, nr_entries, 0);
@@ -822,6 +2167,15 @@ int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size,
 	unsigned long *entries;
 	unsigned int nr_entries;
 
+	if (stack_depot_handle_is_trie(handle)) {
+		unsigned long trie_entries[CONFIG_STACKDEPOT_MAX_FRAMES];
+
+		nr_entries = trie_fetch_handle_into(handle, trie_entries,
+						    ARRAY_SIZE(trie_entries));
+		return stack_trace_snprint(buf, size, trie_entries, nr_entries,
+					   spaces);
+	}
+
 	nr_entries = stack_depot_fetch(handle, &entries);
 	return nr_entries ? stack_trace_snprint(buf, size, entries, nr_entries,
 						spaces) : 0;

-- 
Git-155)

[PATCH RFC 2/9] stackdepot: add KUnit tests for trie storage

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

Trie insertion mutates shared topology, but handles returned before later
splits, promotions, and child-array replacements must continue to fetch and
deduplicate the same traces. Add a built-in KUnit suite for stack depot's
public APIs and trie internals. The backend-neutral cases run immediately
against hash storage. Once the final patch makes trie activation reachable,
the same cases also exercise trie storage.

Cover save and deduplication behavior, maximum-depth and overlong stacks,
allocation-constrained hits and misses, GET records, extra bits,
caller-owned fetching, short destinations, and formatted output. Exercise
append, descent, split, promotion, child-array growth, and tail append
paths. Also cover lockless duplicate lookups while verifying that earlier
handles still materialize and deduplicate after later mutations.

Add mixed compressed and raw frame round trips together with generic,
arm64, and native x86-64 codec coverage. Keep fixtures portable to 32-bit
architectures, skip the native x86 codec case on UML, and require at least
three configured frames for the topology fixtures. On 4 KiB arm64 and
native x86-64 builds configured for 256 frames, an alternating
compressed/raw maximum-depth trace creates one node per frame and exercises
a two-pool insertion and its bounded retry path.

Build the suite into the kernel because it exercises non-exported stack
depot helpers. Skip trie-specific cases unless
stackdepot_kunit.trie_pool_limit matches the stack_depot_max_pools
value used at boot. On the complete series, run them with
stackdepot.trie_enabled=1 and matching values for both parameters; this
prevents optional initialization failure from silently exercising hash
storage.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 lib/Kconfig.debug            |  17 ++
 lib/tests/Makefile           |   1 +
 lib/tests/stackdepot_kunit.c | 418 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 436 insertions(+)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 00921b1676e8..af238949fb7a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2771,6 +2771,23 @@ config RESOURCE_KUNIT_TEST
 
 	  If unsure, say N.
 
+config STACKDEPOT_KUNIT_TEST
+	bool "KUnit test for stack depot" if !KUNIT_ALL_TESTS
+	depends on KUNIT=y && STACKDEPOT
+	depends on STACKDEPOT_MAX_FRAMES >= 3
+	default KUNIT_ALL_TESTS
+	help
+	  Enable this option to test stack depot API behavior at boot.
+	  This test is built in because it exercises internal, non-exported
+	  stack depot helpers, so KUNIT must also be built in.
+
+	  KUnit tests run during boot and output the results to the debug log
+	  in TAP format (https://testanything.org/). Only useful for kernel
+	  developers running the KUnit test harness, and not intended for
+	  inclusion into a production build.
+
+	  If unsure, say N.
+
 config SYSCTL_KUNIT_TEST
 	tristate "KUnit test for sysctl" if !KUNIT_ALL_TESTS
 	depends on KUNIT
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 4ead57602eac..2d40bd21a8ef 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -49,6 +49,7 @@ obj-$(CONFIG_SCANF_KUNIT_TEST) += scanf_kunit.o
 obj-$(CONFIG_SEQ_BUF_KUNIT_TEST) += seq_buf_kunit.o
 obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
 obj-$(CONFIG_SLUB_KUNIT_TEST) += slub_kunit.o
+obj-$(CONFIG_STACKDEPOT_KUNIT_TEST) += stackdepot_kunit.o
 obj-$(CONFIG_TEST_SORT) += test_sort.o
 CFLAGS_stackinit_kunit.o += $(call cc-disable-warning, switch-unreachable)
 obj-$(CONFIG_STACKINIT_KUNIT_TEST) += stackinit_kunit.o
diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c
new file mode 100644
index 000000000000..75fa16268c0b
--- /dev/null
+++ b/lib/tests/stackdepot_kunit.c
@@ -0,0 +1,418 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/array_size.h>
+#include <linux/gfp.h>
+#include <linux/limits.h>
+#include <linux/moduleparam.h>
+#include <linux/stackdepot.h>
+#include <linux/stacktrace.h>
+#include <linux/string.h>
+
+#include <asm/stackdepot.h>
+
+static int expected_trie_pool_limit = -1;
+module_param_named(trie_pool_limit, expected_trie_pool_limit, int, 0);
+MODULE_PARM_DESC(trie_pool_limit, "Expected stackdepot hash/trie pool split");
+
+#ifdef CONFIG_ARM64
+#include <asm/sections.h>
+
+static inline unsigned long stackdepot_arm64_frame(long offset)
+{
+	return (unsigned long)((long)_text + offset);
+}
+#endif
+
+static void stackdepot_trie_max_path_roundtrip(struct kunit *test)
+{
+	union handle_parts parts;
+	unsigned long *entries;
+	unsigned long *fetched;
+	depot_stack_handle_t handle;
+	size_t size = CONFIG_STACKDEPOT_MAX_FRAMES * sizeof(*entries);
+	u32 pool_index_plus_1;
+	unsigned int i;
+
+	if (expected_trie_pool_limit < 0)
+		kunit_skip(test, "trie pool limit was not provided");
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+	entries = kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES,
+				sizeof(*entries), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, entries);
+	fetched = kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES,
+				sizeof(*fetched), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, fetched);
+	for (i = 0; i < CONFIG_STACKDEPOT_MAX_FRAMES; i++) {
+#ifdef CONFIG_ARM64
+		entries[i] = i & 1 ? 0x1000UL + i * 0x1000UL :
+			stackdepot_arm64_frame(i * 4);
+#elif defined(CONFIG_X86_64) && !defined(CONFIG_UML)
+		entries[i] = i & 1 ? 0xffff888000000000UL + i * 0x1000UL :
+			0xffffffff10000000UL + i * 0x10UL;
+#else
+		entries[i] = 0x1000UL + i * 0x1000UL;
+#endif
+	}
+
+	handle = stack_depot_save(entries, CONFIG_STACKDEPOT_MAX_FRAMES,
+				  GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+	parts.handle = handle;
+	pool_index_plus_1 = parts.pool_index_plus_1;
+	KUNIT_EXPECT_GT(test, pool_index_plus_1, (u32)expected_trie_pool_limit);
+	KUNIT_EXPECT_EQ(test,
+			stack_depot_fetch_into(handle, fetched,
+					       CONFIG_STACKDEPOT_MAX_FRAMES),
+			(unsigned int)CONFIG_STACKDEPOT_MAX_FRAMES);
+	KUNIT_EXPECT_MEMEQ(test, fetched, entries, size);
+	KUNIT_EXPECT_EQ(test,
+			stack_depot_save(entries, CONFIG_STACKDEPOT_MAX_FRAMES,
+					 GFP_KERNEL),
+			handle);
+}
+
+static void stackdepot_save_flags_public(struct kunit *test)
+{
+	unsigned long entries[] = { 0x501000UL, 0x502000UL, 0x503000UL };
+	unsigned long get_entries[] = { 0x601000UL, 0x602000UL };
+	unsigned long missing_entries[] = { 0x701000UL, 0x702000UL };
+	unsigned long fetched[ARRAY_SIZE(entries)] = {};
+	depot_stack_handle_t noalloc_handle;
+	depot_stack_handle_t overlong_handle;
+	depot_stack_handle_t plain_handle;
+	depot_stack_handle_t get_handle;
+	depot_stack_handle_t again;
+	depot_stack_handle_t extra;
+	gfp_t no_spin = GFP_NOWAIT & ~__GFP_RECLAIM;
+	unsigned long *overlong_fetched;
+	unsigned long *overlong_entries;
+	unsigned int overlong_nr = CONFIG_STACKDEPOT_MAX_FRAMES + 1;
+	unsigned int nr_entries;
+	size_t overlong_size;
+	unsigned int i;
+
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+	overlong_entries = kunit_kcalloc(test, overlong_nr,
+					 sizeof(*overlong_entries), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, overlong_entries);
+	overlong_fetched = kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES,
+					 sizeof(*overlong_fetched), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, overlong_fetched);
+	for (i = 0; i < overlong_nr; i++)
+		overlong_entries[i] = 0x800000UL + i * 0x1000UL;
+
+	plain_handle = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, plain_handle, (depot_stack_handle_t)0);
+	again = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_EXPECT_EQ(test, again, plain_handle);
+
+	nr_entries = stack_depot_fetch_into(plain_handle, fetched,
+					    ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries));
+	KUNIT_EXPECT_MEMEQ(test, fetched, entries, sizeof(entries));
+
+	noalloc_handle = stack_depot_save_flags(entries, ARRAY_SIZE(entries), no_spin, 0);
+	KUNIT_EXPECT_EQ(test, noalloc_handle, plain_handle);
+	if (expected_trie_pool_limit >= 0) {
+		noalloc_handle =
+			stack_depot_save_flags(missing_entries,
+					       ARRAY_SIZE(missing_entries),
+					       no_spin, 0);
+		KUNIT_EXPECT_EQ(test, noalloc_handle, (depot_stack_handle_t)0);
+	}
+
+	get_handle = stack_depot_save_flags(get_entries, ARRAY_SIZE(get_entries),
+					    GFP_KERNEL,
+					    STACK_DEPOT_FLAG_CAN_ALLOC |
+					    STACK_DEPOT_FLAG_GET);
+	KUNIT_ASSERT_NE(test, get_handle, (depot_stack_handle_t)0);
+	stack_depot_put(get_handle);
+
+	overlong_handle = stack_depot_save(overlong_entries, overlong_nr,
+					   GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, overlong_handle, (depot_stack_handle_t)0);
+	nr_entries = stack_depot_fetch_into(overlong_handle, overlong_fetched,
+					    CONFIG_STACKDEPOT_MAX_FRAMES);
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)CONFIG_STACKDEPOT_MAX_FRAMES);
+	overlong_size = CONFIG_STACKDEPOT_MAX_FRAMES * sizeof(*overlong_entries);
+	KUNIT_EXPECT_MEMEQ(test, overlong_fetched, overlong_entries, overlong_size);
+
+	extra = stack_depot_set_extra_bits(plain_handle, 7);
+	KUNIT_ASSERT_NE(test, extra, (depot_stack_handle_t)0);
+	KUNIT_EXPECT_EQ(test, stack_depot_get_extra_bits(extra), 7U);
+	memset(fetched, 0, sizeof(fetched));
+	nr_entries = stack_depot_fetch_into(extra, fetched, ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries));
+	KUNIT_EXPECT_MEMEQ(test, fetched, entries, sizeof(entries));
+}
+
+static void stackdepot_snprint_public(struct kunit *test)
+{
+	unsigned long entries[] = { 0x1000UL, 0x2000UL, 0x3000UL };
+	char expected[256];
+	char actual[256];
+	depot_stack_handle_t handle;
+	unsigned int expected_len;
+	int actual_len;
+
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+	handle = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+
+	expected_len = stack_trace_snprint(expected, sizeof(expected), entries,
+					   ARRAY_SIZE(entries), 2);
+	actual_len = stack_depot_snprint(handle, actual, sizeof(actual), 2);
+	KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len);
+	KUNIT_EXPECT_STREQ(test, actual, expected);
+}
+
+static void stackdepot_fetch_into_roundtrip(struct kunit *test)
+{
+	unsigned long entries[] = {
+		0x101000UL,
+		0x102000UL,
+		0x103000UL,
+	};
+	unsigned long exact[ARRAY_SIZE(entries)] = {};
+	unsigned long fetched[ARRAY_SIZE(entries) + 1] = {
+		[ARRAY_SIZE(entries)] = 0xa5a5a5a5UL,
+	};
+	unsigned long expected_tail = fetched[ARRAY_SIZE(entries)];
+	depot_stack_handle_t handle;
+	unsigned int nr_entries;
+
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+
+	handle = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+
+	nr_entries = stack_depot_fetch_into(handle, exact, ARRAY_SIZE(exact));
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries));
+	KUNIT_EXPECT_MEMEQ(test, exact, entries, sizeof(entries));
+
+	nr_entries = stack_depot_fetch_into(handle, fetched, ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries));
+	KUNIT_EXPECT_MEMEQ(test, fetched, entries, sizeof(entries));
+	KUNIT_EXPECT_EQ(test, fetched[ARRAY_SIZE(entries)], expected_tail);
+}
+
+static void stackdepot_fetch_into_rejects_missing_or_short_stack(struct kunit *test)
+{
+	unsigned long entries[] = {
+		0x111000UL,
+		0x112000UL,
+		0x113000UL,
+	};
+	unsigned long fetched[ARRAY_SIZE(entries)] = {
+		0xa1a1a1a1UL,
+		0xb2b2b2b2UL,
+		0xc3c3c3c3UL,
+	};
+	unsigned long expected[ARRAY_SIZE(fetched)];
+	depot_stack_handle_t handle;
+	unsigned int nr_entries;
+
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+
+	handle = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+	memcpy(expected, fetched, sizeof(expected));
+
+	nr_entries = stack_depot_fetch_into(0, fetched, ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, 0U);
+	KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected));
+
+	nr_entries = stack_depot_fetch_into(0, NULL, 0);
+	KUNIT_EXPECT_EQ(test, nr_entries, 0U);
+
+	nr_entries = stack_depot_fetch_into(handle, fetched,
+					    ARRAY_SIZE(fetched) - 1);
+	KUNIT_EXPECT_EQ(test, nr_entries, 0U);
+	KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected));
+}
+
+static void stackdepot_trie_topology_roundtrip(struct kunit *test)
+{
+	union handle_parts parts;
+	unsigned long stacks[][3] = {
+		{ 0x201000UL, 0x202000UL },
+		{ 0x201000UL, 0x203000UL },
+		{ 0x201000UL },
+		{ 0x201000UL, 0x203000UL, 0x204000UL },
+		{ 0x201000UL, 0x205000UL },
+		{ 0x201000UL, 0x204000UL },
+		{ 0x201000UL, 0x206000UL },
+		{ 0x201000UL, 0x207000UL },
+		{ 0x301000UL, 0x302000UL },
+		{ 0x301000UL, 0x302000UL, 0x303000UL },
+		{ 0x301000UL, 0x304000UL },
+		{ 0x401000UL, 0x402000UL, 0x403000UL },
+		{ 0x401000UL, 0x402000UL },
+	};
+	unsigned int nr_entries[] = { 2, 2, 1, 3, 2, 2, 2, 2, 2, 3, 2, 3, 2 };
+	depot_stack_handle_t handles[ARRAY_SIZE(stacks)];
+	unsigned long fetched[ARRAY_SIZE(stacks[0])];
+	u32 pool_index_plus_1;
+	unsigned int i;
+
+	if (expected_trie_pool_limit < 0)
+		kunit_skip(test, "trie pool limit was not provided");
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+
+	for (i = 0; i < ARRAY_SIZE(stacks); i++) {
+		handles[i] = stack_depot_save(stacks[i], nr_entries[i], GFP_KERNEL);
+		KUNIT_ASSERT_NE(test, handles[i], (depot_stack_handle_t)0);
+	}
+	parts.handle = handles[0];
+	pool_index_plus_1 = parts.pool_index_plus_1;
+	KUNIT_ASSERT_GT(test, pool_index_plus_1,
+			(u32)expected_trie_pool_limit);
+
+	for (i = 0; i < ARRAY_SIZE(stacks); i++) {
+		memset(fetched, 0, sizeof(fetched));
+		KUNIT_EXPECT_EQ(test,
+				stack_depot_fetch_into(handles[i], fetched,
+						       ARRAY_SIZE(fetched)),
+				nr_entries[i]);
+		KUNIT_EXPECT_MEMEQ(test, fetched, stacks[i],
+				   nr_entries[i] * sizeof(fetched[0]));
+		KUNIT_EXPECT_EQ(test,
+				stack_depot_save(stacks[i], nr_entries[i], GFP_KERNEL),
+				handles[i]);
+	}
+}
+
+static void stackdepot_frame_storage_roundtrip(struct kunit *test)
+{
+	union handle_parts parts;
+	unsigned long fetched[3] = {};
+	depot_stack_handle_t handle;
+	u32 pool_index_plus_1;
+	unsigned int nr_entries;
+#if defined(CONFIG_ARM64)
+	unsigned long entries[] = {
+		stackdepot_arm64_frame(S32_MIN),
+		0x1000UL,
+		stackdepot_arm64_frame(S32_MAX),
+	};
+#elif defined(CONFIG_X86_64)
+	unsigned long entries[] = {
+		0xffffffff10001000UL,
+		0xffff888000001000UL,
+		0xffffffff20002000UL,
+	};
+#else
+	unsigned long entries[] = { 0x301000UL, 0x302000UL, 0x303000UL };
+#endif
+
+	if (expected_trie_pool_limit < 0)
+		kunit_skip(test, "trie pool limit was not provided");
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+	handle = stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+	parts.handle = handle;
+	pool_index_plus_1 = parts.pool_index_plus_1;
+	KUNIT_ASSERT_GT(test, pool_index_plus_1,
+			(u32)expected_trie_pool_limit);
+
+	nr_entries = stack_depot_fetch_into(handle, fetched, ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries));
+	KUNIT_EXPECT_MEMEQ(test, fetched, entries, sizeof(entries));
+}
+
+static void stackdepot_frame_raw_fallback(struct kunit *test)
+{
+	unsigned long frame = 0x1000UL;
+	bool compressed;
+	u32 payload;
+
+#ifdef CONFIG_ARM64
+	frame = (unsigned long)_text + (unsigned long)S32_MAX + 1UL;
+#endif
+
+	compressed = arch_stack_depot_frame_try_compress(frame, &payload);
+	KUNIT_EXPECT_FALSE(test, compressed);
+}
+
+#if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
+static void stackdepot_frame_x86_64(struct kunit *test)
+{
+	unsigned long direct_map = 0xffff888000001000UL;
+	unsigned long frame = 0xffffffff81234567UL;
+	unsigned long out;
+	bool compressed;
+	u32 low;
+
+	compressed = arch_stack_depot_frame_try_compress(frame, &low);
+	KUNIT_EXPECT_TRUE(test, compressed);
+	KUNIT_EXPECT_EQ(test, low, (u32)0x81234567);
+	arch_stack_depot_frame_decompress(low, &out);
+	KUNIT_EXPECT_EQ(test, out, frame);
+
+	compressed = arch_stack_depot_frame_try_compress(direct_map, &low);
+	KUNIT_EXPECT_FALSE(test, compressed);
+}
+#endif /* CONFIG_X86_64 && !CONFIG_UML */
+
+#ifdef CONFIG_ARM64
+static void stackdepot_frame_arm64(struct kunit *test)
+{
+	long negative_offset = S32_MIN;
+	long positive_offset = S32_MAX;
+	long offset = 0x123456;
+	unsigned long frame = stackdepot_arm64_frame(offset);
+	unsigned long out;
+	bool compressed;
+	u32 payload;
+
+	compressed = arch_stack_depot_frame_try_compress(frame, &payload);
+	KUNIT_EXPECT_TRUE(test, compressed);
+	KUNIT_EXPECT_EQ(test, payload, (u32)(s32)offset);
+	arch_stack_depot_frame_decompress(payload, &out);
+	KUNIT_EXPECT_EQ(test, out, frame);
+
+	frame = stackdepot_arm64_frame(negative_offset);
+	compressed = arch_stack_depot_frame_try_compress(frame, &payload);
+	KUNIT_EXPECT_TRUE(test, compressed);
+	KUNIT_EXPECT_EQ(test, payload, (u32)(s32)negative_offset);
+	arch_stack_depot_frame_decompress(payload, &out);
+	KUNIT_EXPECT_EQ(test, out, frame);
+
+	frame = stackdepot_arm64_frame(positive_offset);
+	compressed = arch_stack_depot_frame_try_compress(frame, &payload);
+	KUNIT_EXPECT_TRUE(test, compressed);
+	KUNIT_EXPECT_EQ(test, payload, (u32)(s32)positive_offset);
+	arch_stack_depot_frame_decompress(payload, &out);
+	KUNIT_EXPECT_EQ(test, out, frame);
+}
+#endif /* CONFIG_ARM64 */
+
+static struct kunit_case stackdepot_test_cases[] = {
+	KUNIT_CASE(stackdepot_trie_max_path_roundtrip),
+	KUNIT_CASE(stackdepot_save_flags_public),
+	KUNIT_CASE(stackdepot_snprint_public),
+	KUNIT_CASE(stackdepot_fetch_into_roundtrip),
+	KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
+	KUNIT_CASE(stackdepot_trie_topology_roundtrip),
+	KUNIT_CASE(stackdepot_frame_storage_roundtrip),
+	KUNIT_CASE(stackdepot_frame_raw_fallback),
+#if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
+	KUNIT_CASE(stackdepot_frame_x86_64),
+#endif
+#ifdef CONFIG_ARM64
+	KUNIT_CASE(stackdepot_frame_arm64),
+#endif
+	{}
+};
+
+static struct kunit_suite stackdepot_test_suite = {
+	.name = "stackdepot",
+	.test_cases = stackdepot_test_cases,
+};
+
+kunit_test_suite(stackdepot_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for stack depot");
+MODULE_AUTHOR("Caleb Kan <ckan@cloudflare.com>");
+MODULE_LICENSE("GPL");

-- 
Git-155)

[PATCH RFC 3/9] mm/page_owner: preserve accounting with countable stack depot records

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

page_owner keeps stable struct stack_record pointers in its stack list.
It uses each record's count with a one-count bias to track live base pages
and reads the stored entries directly. The trie backend provides neither a
flat record layout nor an independent count field.

Add STACK_DEPOT_FLAG_COUNTABLE to keep these records on the hash backend
and deduplicate them separately from all non-countable records. Store the
discriminator in a new u16 flags field and narrow size to u16. This keeps
the record header size unchanged while covering the configured maximum of
256 frames. Do not otherwise split hash-table deduplication: ordinary and
GET saves can continue to share records. Make COUNTABLE mutually exclusive
with GET because the two flags assign incompatible meanings to the record
count. Reject countable records in stack_depot_put() and require COUNTABLE
in __stack_depot_get_stack_record().

Mark both page_owner save sites countable so its existing accounting and
reporting continue to use stable hash records. Extend the KUnit coverage to
verify direct-record access and isolation between countable and
non-countable records.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 include/linux/stackdepot.h   | 14 ++++++++---
 lib/stackdepot.c             | 30 +++++++++++++++++++-----
 lib/tests/stackdepot_kunit.c | 55 ++++++++++++++++++++++++++++++++++++++++++++
 mm/page_owner.c              |  6 +++--
 4 files changed, 94 insertions(+), 11 deletions(-)

diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h
index 96544fc684a5..788737eb0c4a 100644
--- a/include/linux/stackdepot.h
+++ b/include/linux/stackdepot.h
@@ -53,7 +53,8 @@ union handle_parts {
 struct stack_record {
 	struct list_head hash_list;	/* Links in the hash table */
 	u32 hash;			/* Hash in hash table */
-	u32 size;			/* Number of stored frames */
+	u16 size;			/* Number of stored frames */
+	u16 flags;
 	union handle_parts handle;	/* Constant after initialization */
 	refcount_t count;
 	union {
@@ -84,8 +85,9 @@ typedef u32 depot_flags_t;
  */
 #define STACK_DEPOT_FLAG_CAN_ALLOC	((depot_flags_t)0x0001)
 #define STACK_DEPOT_FLAG_GET		((depot_flags_t)0x0002)
+#define STACK_DEPOT_FLAG_COUNTABLE	((depot_flags_t)0x0004)
 
-#define STACK_DEPOT_FLAGS_NUM	2
+#define STACK_DEPOT_FLAGS_NUM	3
 #define STACK_DEPOT_FLAGS_MASK	((depot_flags_t)((1 << STACK_DEPOT_FLAGS_NUM) - 1))
 
 /*
@@ -144,6 +146,11 @@ static inline int stack_depot_early_init(void)	{ return 0; }
  * Users of this flag must also call stack_depot_put() when keeping the stack
  * trace is no longer required to avoid overflowing the refcount.
  *
+ * If STACK_DEPOT_FLAG_COUNTABLE is set in @depot_flags, stack depot stores the
+ * stack in hash-backed storage for callers that need direct stack_record count
+ * access. This flag does not imply %STACK_DEPOT_FLAG_CAN_ALLOC and is mutually
+ * exclusive with %STACK_DEPOT_FLAG_GET.
+ *
  * When trie storage is enabled, persistent non-refcounted saves use trie
  * storage. Constrained callers only look up existing stacks; they do not insert
  * a missing stack. Trie failures do not fall back to hash storage.
@@ -190,7 +197,8 @@ depot_stack_handle_t stack_depot_save(unsigned long *entries,
  *
  * @handle: Stack depot handle
  *
- * This function is only for internal purposes.
+ * This function is only for internal purposes. @handle must have been saved
+ * with %STACK_DEPOT_FLAG_COUNTABLE.
  *
  * Return: Returns a pointer to a stack_record struct
  */
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index 0278b7a013f1..1e5b9fc44618 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -2,10 +2,11 @@
 /*
  * Stack depot - a stack trace storage that avoids duplication.
  *
- * Internally, stack depot has two storage backends. Refcounted entries use the
- * legacy hash table with contiguous stack records in stack pools. Persistent
- * non-refcounted entries can use trie storage when enabled; trie nodes share
- * common frame prefixes and are published through RCU children containers.
+ * Internally, stack depot has two storage backends. Refcounted entries and
+ * callers that request STACK_DEPOT_FLAG_COUNTABLE use the legacy hash table with
+ * contiguous stack records in stack pools. Persistent non-refcounted entries
+ * can use trie storage when enabled; trie nodes share common frame prefixes and
+ * are published through RCU children containers.
  *
  * Author: Alexander Potapenko <glider@google.com>
  * Copyright (C) 2016 Google, Inc.
@@ -1022,6 +1023,7 @@ depot_alloc_stack(unsigned long *entries, unsigned int nr_entries, u32 hash, dep
 	/* Save the stack trace. */
 	stack->hash = hash;
 	stack->size = nr_entries;
+	stack->flags = flags & STACK_DEPOT_FLAG_COUNTABLE;
 	/* stack->handle is already filled in by depot_pop_free_pool(). */
 	memcpy(stack->entries, entries, flex_array_size(stack, entries, nr_entries));
 
@@ -1164,6 +1166,9 @@ static inline struct stack_record *find_stack(struct list_head *bucket,
 	list_for_each_entry_rcu(stack, bucket, hash_list) {
 		if (stack->hash != hash || stack->size != size)
 			continue;
+		/* Page owner countable records have a distinct count lifetime. */
+		if ((stack->flags ^ flags) & STACK_DEPOT_FLAG_COUNTABLE)
+			continue;
 
 		/*
 		 * This may race with depot_free_stack() accessing the freelist
@@ -1267,6 +1272,9 @@ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
 
 	if (WARN_ON(depot_flags & ~STACK_DEPOT_FLAGS_MASK))
 		return 0;
+	if (WARN_ON_ONCE((depot_flags & STACK_DEPOT_FLAG_GET) &&
+			 (depot_flags & STACK_DEPOT_FLAG_COUNTABLE)))
+		return 0;
 
 	/*
 	 * If this stack trace is from an interrupt, including anything before
@@ -1281,7 +1289,7 @@ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
 	if (unlikely(nr_entries == 0) || stack_depot_disabled)
 		return 0;
 
-	if (!(depot_flags & STACK_DEPOT_FLAG_GET) &&
+	if (!(depot_flags & (STACK_DEPOT_FLAG_GET | STACK_DEPOT_FLAG_COUNTABLE)) &&
 	    static_branch_unlikely(&stack_depot_trie_enabled)) {
 		if (nr_entries > CONFIG_STACKDEPOT_MAX_FRAMES)
 			nr_entries = CONFIG_STACKDEPOT_MAX_FRAMES;
@@ -1374,12 +1382,20 @@ EXPORT_SYMBOL_GPL(stack_depot_save);
 
 struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle)
 {
+	struct stack_record *stack;
+
 	if (!handle)
 		return NULL;
 	if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle)))
 		return NULL;
 
-	return depot_fetch_stack(handle);
+	stack = depot_fetch_stack(handle);
+	if (!stack)
+		return NULL;
+	if (WARN_ON_ONCE(!(stack->flags & STACK_DEPOT_FLAG_COUNTABLE)))
+		return NULL;
+
+	return stack;
 }
 
 static void frame_run_init(const unsigned long *entries,
@@ -2136,6 +2152,8 @@ void stack_depot_put(depot_stack_handle_t handle)
 	if (WARN(!stack, "corrupt handle or unbalanced stack_depot_put()"))
 		return;
 
+	if (WARN_ON_ONCE(stack->flags & STACK_DEPOT_FLAG_COUNTABLE))
+		return;
 	if (refcount_dec_and_test(&stack->count))
 		depot_free_stack(stack);
 }
diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c
index 75fa16268c0b..be14cae98fcf 100644
--- a/lib/tests/stackdepot_kunit.c
+++ b/lib/tests/stackdepot_kunit.c
@@ -167,6 +167,60 @@ static void stackdepot_snprint_public(struct kunit *test)
 	KUNIT_EXPECT_STREQ(test, actual, expected);
 }
 
+static void stackdepot_countable_public(struct kunit *test)
+{
+	unsigned long plain_entries[] = {
+		0x141000UL,
+		0x142000UL,
+		0x143000UL,
+	};
+	unsigned long get_entries[] = {
+		0x151000UL,
+		0x152000UL,
+		0x153000UL,
+	};
+	unsigned long fetched[ARRAY_SIZE(plain_entries)] = {};
+	depot_flags_t countable = STACK_DEPOT_FLAG_CAN_ALLOC |
+				  STACK_DEPOT_FLAG_COUNTABLE;
+	struct stack_record *record;
+	depot_stack_handle_t count_handle;
+	depot_stack_handle_t plain_handle;
+	depot_stack_handle_t get_handle;
+	unsigned int get_nr = ARRAY_SIZE(get_entries);
+	unsigned int plain_nr = ARRAY_SIZE(plain_entries);
+	unsigned int nr_entries;
+
+	KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+
+	plain_handle = stack_depot_save(plain_entries, plain_nr, GFP_KERNEL);
+	KUNIT_ASSERT_NE(test, plain_handle, (depot_stack_handle_t)0);
+	count_handle = stack_depot_save_flags(plain_entries, plain_nr, GFP_KERNEL,
+					      countable);
+	KUNIT_ASSERT_NE(test, count_handle, (depot_stack_handle_t)0);
+	record = __stack_depot_get_stack_record(count_handle);
+	KUNIT_ASSERT_NOT_NULL(test, record);
+	KUNIT_EXPECT_EQ(test, record->size, (u16)plain_nr);
+	KUNIT_EXPECT_MEMEQ(test, record->entries, plain_entries,
+			   sizeof(plain_entries));
+	nr_entries = stack_depot_fetch_into(count_handle, fetched,
+					    ARRAY_SIZE(fetched));
+	KUNIT_EXPECT_EQ(test, nr_entries, plain_nr);
+	KUNIT_EXPECT_MEMEQ(test, fetched, plain_entries, sizeof(plain_entries));
+
+	get_handle = stack_depot_save_flags(get_entries, get_nr, GFP_KERNEL,
+					    STACK_DEPOT_FLAG_CAN_ALLOC |
+					    STACK_DEPOT_FLAG_GET);
+	KUNIT_ASSERT_NE(test, get_handle, (depot_stack_handle_t)0);
+	count_handle = stack_depot_save_flags(get_entries, get_nr, GFP_KERNEL,
+					      countable);
+	KUNIT_ASSERT_NE(test, count_handle, (depot_stack_handle_t)0);
+	record = __stack_depot_get_stack_record(count_handle);
+	KUNIT_ASSERT_NOT_NULL(test, record);
+	KUNIT_EXPECT_MEMEQ(test, record->entries, get_entries, sizeof(get_entries));
+
+	stack_depot_put(get_handle);
+}
+
 static void stackdepot_fetch_into_roundtrip(struct kunit *test)
 {
 	unsigned long entries[] = {
@@ -392,6 +446,7 @@ static struct kunit_case stackdepot_test_cases[] = {
 	KUNIT_CASE(stackdepot_trie_max_path_roundtrip),
 	KUNIT_CASE(stackdepot_save_flags_public),
 	KUNIT_CASE(stackdepot_snprint_public),
+	KUNIT_CASE(stackdepot_countable_public),
 	KUNIT_CASE(stackdepot_fetch_into_roundtrip),
 	KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
 	KUNIT_CASE(stackdepot_trie_topology_roundtrip),
diff --git a/mm/page_owner.c b/mm/page_owner.c
index fbbda7ba914b..af37532729b0 100644
--- a/mm/page_owner.c
+++ b/mm/page_owner.c
@@ -119,7 +119,8 @@ static __always_inline depot_stack_handle_t create_dummy_stack(void)
 	unsigned int nr_entries;
 
 	nr_entries = stack_trace_save(entries, ARRAY_SIZE(entries), 0);
-	return stack_depot_save(entries, nr_entries, GFP_KERNEL);
+	return stack_depot_save_flags(entries, nr_entries, GFP_KERNEL,
+				       STACK_DEPOT_FLAG_CAN_ALLOC | STACK_DEPOT_FLAG_COUNTABLE);
 }
 
 static noinline void register_dummy_stack(void)
@@ -181,7 +182,8 @@ static noinline depot_stack_handle_t save_stack(gfp_t flags)
 
 	set_current_in_page_owner();
 	nr_entries = stack_trace_save(entries, ARRAY_SIZE(entries), 2);
-	handle = stack_depot_save(entries, nr_entries, flags);
+	handle = stack_depot_save_flags(entries, nr_entries, flags,
+					STACK_DEPOT_FLAG_CAN_ALLOC | STACK_DEPOT_FLAG_COUNTABLE);
 	if (!handle)
 		handle = failure_handle;
 	unset_current_in_page_owner();

-- 
Git-155)

[PATCH RFC 4/9] mm/kmemleak: print trie-backed stack depot traces

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

kmemleak stores allocation backtraces as persistent stack depot handles.
When trie storage is enabled, stack_depot_fetch() cannot return a pointer
to contiguous stack-record entries, so leak reports would omit the saved
backtrace.

Use stack_depot_fetch_into() with a MAX_TRACE-sized local array before
formatting the report. MAX_TRACE matches the save-side limit, so every
valid kmemleak trace fits without truncation. Preserve frame order and the
existing report format for hash-backed handles.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 mm/kmemleak.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/mm/kmemleak.c b/mm/kmemleak.c
index 8fa409a4f9fb..c42741a88bd4 100644
--- a/mm/kmemleak.c
+++ b/mm/kmemleak.c
@@ -378,10 +378,10 @@ static void __print_unreferenced(struct seq_file *seq,
 				 bool hex_dump)
 {
 	int i;
-	unsigned long *entries;
+	unsigned long entries[MAX_TRACE];
 	unsigned int nr_entries;
 
-	nr_entries = stack_depot_fetch(object->trace_handle, &entries);
+	nr_entries = stack_depot_fetch_into(object->trace_handle, entries, ARRAY_SIZE(entries));
 	warn_or_seq_printf(seq, "unreferenced object%s 0x%08lx (size %zu):\n",
 			   __object_type_str(object),
 			   object->pointer, object->size);

-- 
Git-155)

[PATCH RFC 5/9] kmsan: report trie-backed stack depot traces

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

KMSAN stores ordinary origin stacks and synthetic alloca and chain origins
as persistent stack depot records. Once trie storage is enabled, these
handles can be trie-backed, while kmsan_print_origin() still relies on the
hash-only stack_depot_fetch() API.

Use one KMSAN_STACK_DEPTH array to materialize each origin and chained
stack in turn. Preserve the chain's head and next-origin handles before
reusing the array for the chained stack. The array covers both the regular
save limit and the smaller synthetic records.

lib/stackdepot.c is uninstrumented, so stack_depot_fetch_into() unpoisons
the successfully copied range before returning it to KMSAN. Remove the
now-redundant explicit unpoisoning of chained entries. Origin depth and
use-after-free metadata remain in the handle's extra bits and are
unchanged.

Update test_stackdepot_roundtrip() to use caller-owned storage while
retaining its frame-count and kmsan_check_memory() checks. This verifies
that the copy-out API returns initialized entries to instrumented callers.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 mm/kmsan/kmsan_test.c |  4 ++--
 mm/kmsan/report.c     | 17 +++++++----------
 2 files changed, 9 insertions(+), 12 deletions(-)

diff --git a/mm/kmsan/kmsan_test.c b/mm/kmsan/kmsan_test.c
index 31f47cc4dab4..7c04e4b21873 100644
--- a/mm/kmsan/kmsan_test.c
+++ b/mm/kmsan/kmsan_test.c
@@ -669,7 +669,7 @@ static void test_long_origin_chain(struct kunit *test)
  */
 static void test_stackdepot_roundtrip(struct kunit *test)
 {
-	unsigned long src_entries[16], *dst_entries;
+	unsigned long src_entries[16], dst_entries[16];
 	unsigned int src_nentries, dst_nentries;
 	EXPECTATION_NO_REPORT(expect);
 	depot_stack_handle_t handle;
@@ -680,7 +680,7 @@ static void test_stackdepot_roundtrip(struct kunit *test)
 		stack_trace_save(src_entries, ARRAY_SIZE(src_entries), 1);
 	handle = stack_depot_save(src_entries, src_nentries, GFP_KERNEL);
 	stack_depot_print(handle);
-	dst_nentries = stack_depot_fetch(handle, &dst_entries);
+	dst_nentries = stack_depot_fetch_into(handle, dst_entries, ARRAY_SIZE(dst_entries));
 	KUNIT_EXPECT_TRUE(test, src_nentries == dst_nentries);
 
 	kmsan_check_memory((void *)dst_entries,
diff --git a/mm/kmsan/report.c b/mm/kmsan/report.c
index d6853ce08954..c20c24cffde5 100644
--- a/mm/kmsan/report.c
+++ b/mm/kmsan/report.c
@@ -85,7 +85,7 @@ static char *pretty_descr(char *descr)
 
 void kmsan_print_origin(depot_stack_handle_t origin)
 {
-	unsigned long *entries = NULL, *chained_entries = NULL;
+	unsigned long entries[KMSAN_STACK_DEPTH];
 	unsigned int nr_entries, chained_nr_entries, skipnr;
 	void *pc1 = NULL, *pc2 = NULL;
 	depot_stack_handle_t head;
@@ -97,7 +97,8 @@ void kmsan_print_origin(depot_stack_handle_t origin)
 		return;
 
 	while (true) {
-		nr_entries = stack_depot_fetch(origin, &entries);
+		nr_entries =
+			stack_depot_fetch_into(origin, entries, ARRAY_SIZE(entries));
 		depth = kmsan_depth_from_eb(stack_depot_get_extra_bits(origin));
 		magic = nr_entries ? entries[0] : 0;
 		if ((nr_entries == 4) && (magic == KMSAN_ALLOCA_MAGIC_ORIGIN)) {
@@ -123,14 +124,10 @@ void kmsan_print_origin(depot_stack_handle_t origin)
 			origin = entries[2];
 			pr_err("Uninit was stored to memory at:\n");
 			chained_nr_entries =
-				stack_depot_fetch(head, &chained_entries);
-			kmsan_internal_unpoison_memory(
-				chained_entries,
-				chained_nr_entries * sizeof(*chained_entries),
-				/*checked*/ false);
-			skipnr = get_stack_skipnr(chained_entries,
-						  chained_nr_entries);
-			stack_trace_print(chained_entries + skipnr,
+				stack_depot_fetch_into(head, entries,
+						       ARRAY_SIZE(entries));
+			skipnr = get_stack_skipnr(entries, chained_nr_entries);
+			stack_trace_print(entries + skipnr,
 					  chained_nr_entries - skipnr, 0);
 			pr_err("\n");
 			continue;

-- 
Git-155)

[PATCH RFC 6/9] mm/slub: materialize trie-backed stack depot traces

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

SLUB owner tracking stores allocation and free stacks as persistent stack
depot handles. Trie-backed handles do not expose contiguous stack-record
entries, so __kmem_obj_info() and the alloc_traces and free_traces debugfs
files cannot use stack_depot_fetch().

Use stack_depot_fetch_into() with TRACK_ADDRS_COUNT-sized local arrays.
This matches the save-side limit. Keep the existing KS_ADDRS_COUNT copy
limit and debugfs formatting unchanged for hash-backed handles. Continue
to copy or print no frames when the fetch returns zero.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 mm/slub.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 422bc3e12c02..138c3bc473c9 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -8093,12 +8093,12 @@ void __kmem_obj_info(struct kmem_obj_info *kpp, void *object, struct slab *slab)
 #ifdef CONFIG_STACKDEPOT
 	{
 		depot_stack_handle_t handle;
-		unsigned long *entries;
+		unsigned long entries[TRACK_ADDRS_COUNT];
 		unsigned int nr_entries;
 
 		handle = READ_ONCE(trackp->handle);
 		if (handle) {
-			nr_entries = stack_depot_fetch(handle, &entries);
+			nr_entries = stack_depot_fetch_into(handle, entries, ARRAY_SIZE(entries));
 			for (i = 0; i < KS_ADDRS_COUNT && i < nr_entries; i++)
 				kpp->kp_stack[i] = (void *)entries[i];
 		}
@@ -8106,7 +8106,7 @@ void __kmem_obj_info(struct kmem_obj_info *kpp, void *object, struct slab *slab)
 		trackp = get_track(s, objp, TRACK_FREE);
 		handle = READ_ONCE(trackp->handle);
 		if (handle) {
-			nr_entries = stack_depot_fetch(handle, &entries);
+			nr_entries = stack_depot_fetch_into(handle, entries, ARRAY_SIZE(entries));
 			for (i = 0; i < KS_ADDRS_COUNT && i < nr_entries; i++)
 				kpp->kp_free_stack[i] = (void *)entries[i];
 		}
@@ -9815,12 +9815,14 @@ static int slab_debugfs_show(struct seq_file *seq, void *v)
 #ifdef CONFIG_STACKDEPOT
 		{
 			depot_stack_handle_t handle;
-			unsigned long *entries;
+			unsigned long entries[TRACK_ADDRS_COUNT];
 			unsigned int nr_entries, j;
 
 			handle = READ_ONCE(l->handle);
 			if (handle) {
-				nr_entries = stack_depot_fetch(handle, &entries);
+				nr_entries =
+					stack_depot_fetch_into(handle, entries,
+							       ARRAY_SIZE(entries));
 				seq_puts(seq, "\n");
 				for (j = 0; j < nr_entries; j++)
 					seq_printf(seq, "        %pS\n", (void *)entries[j]);

-- 
Git-155)

[PATCH RFC 7/9] drm/locking: preserve deadlock diagnostics for trie-backed stacks

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

When a modeset lock acquisition returns -EDEADLK, DRM saves the call chain
and prints it if the caller later attempts another lock or drops its locks
without first calling drm_modeset_backoff(). This diagnostic currently
fetches the saved stack through stack_depot_fetch().

Persistent stack depot saves can now return trie-backed handles, while
stack_depot_fetch() remains limited to hash-backed records. Use
stack_depot_snprint() to format either backend. Preserve the PAGE_SIZE
buffer, two-space indentation, warning, and backtrace.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 drivers/gpu/drm/drm_modeset_lock.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/drivers/gpu/drm/drm_modeset_lock.c b/drivers/gpu/drm/drm_modeset_lock.c
index 2c806b0146d6..a2ddb02b2aea 100644
--- a/drivers/gpu/drm/drm_modeset_lock.c
+++ b/drivers/gpu/drm/drm_modeset_lock.c
@@ -94,16 +94,13 @@ static noinline depot_stack_handle_t __drm_stack_depot_save(void)
 static void __drm_stack_depot_print(depot_stack_handle_t stack_depot)
 {
 	struct drm_printer p = drm_dbg_printer(NULL, DRM_UT_KMS, "drm_modeset_lock");
-	unsigned long *entries;
-	unsigned int nr_entries;
 	char *buf;
 
 	buf = kmalloc(PAGE_SIZE, GFP_NOWAIT | __GFP_NOWARN);
 	if (!buf)
 		return;
 
-	nr_entries = stack_depot_fetch(stack_depot, &entries);
-	stack_trace_snprint(buf, PAGE_SIZE, entries, nr_entries, 2);
+	stack_depot_snprint(stack_depot, buf, PAGE_SIZE, 2);
 
 	drm_printf(&p, "attempting to lock a contended lock without backoff:\n%s", buf);
 

-- 
Git-155)

[PATCH RFC 8/9] scripts/gdb: reject trie-backed stack depot handles

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

The lx-stack_depot_lookup command can materialize stacks only from
contiguous hash-backed records. Trie-backed handles instead encode a dense
stack ID in pool_index_plus_1 and offset, so treating them as hash handles
misreports a valid handle as an out-of-bounds pool index.

Reject pool_index_plus_1 values above stack_max_pools before the hash pool
lookup and report that trie-backed handles are unsupported. Supporting them
would require side-table and parent-link traversal in the helper, which is
left for future work.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 scripts/gdb/linux/stackdepot.py | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/scripts/gdb/linux/stackdepot.py b/scripts/gdb/linux/stackdepot.py
index 37313a5a51a0..82aeb9f532c3 100644
--- a/scripts/gdb/linux/stackdepot.py
+++ b/scripts/gdb/linux/stackdepot.py
@@ -37,6 +37,10 @@ def stack_depot_fetch(handle):
     if handle == 0:
         raise gdb.GdbError("handle is 0\n")
 
+    stack_max_pools = gdb.parse_and_eval('stack_max_pools')
+    if parts['pool_index_plus_1'] > stack_max_pools:
+        raise gdb.GdbError("trie-backed stack depot handles are not supported\n")
+
     pool_index = parts['pool_index_plus_1'] - 1
     if pool_index >= pools_num:
         gdb.write("pool index %d out of bounds (%d) for stack id 0x%08x\n" % (parts['pool_index'], pools_num, handle))

-- 
Git-155)

[PATCH RFC 9/9] stackdepot: add boot-time activation for trie storage

[Caleb Kan]

From: Caleb Kan <ckan@cloudflare.com>

Trie storage cannot be activated while persistent stack depot consumers
can pass trie-backed handles to hash-only access paths. The preceding
patches make those paths backend-independent, keep the corresponding saves
explicitly hash-backed, or make the GDB helper reject trie-backed handles.
The trie can now be activated without exposing incompatible handles.

Add the boot-only stackdepot.trie_enabled parameter. Keep it disabled by
default because lookup-only constrained misses can lose traces and the GDB
helper does not decode trie handles. Guard backend selection with a static
key so the existing hash-only path does not take a normal runtime branch
when the parameter is absent. Document the parameter and its
handle-namespace requirements.

The available trie ID space depends on stack_depot_max_pools because hash
and trie handles share the pool-index field. Configurations that consume
the entire field cannot enable the backend. In particular, a 64 KiB page
configuration using the default maximum of 8,191 pools must lower
stack_depot_max_pools to leave trie ID space.

For early stack depot initialization, allocate the trie side-table root,
first directory, and first chunk through memblock. For later
initialization, allocate the root with kvzalloc and grow directory and
chunk pages lazily. Enable the static key only after initialization
succeeds.

Treat trie initialization as optional. If the handle namespace is empty or
metadata allocation fails, warn, clear the request, and continue using the
initialized hash backend at its configured capacity.

Hash and trie storage continue to share stack_pools and the configured
physical pool limit. Pools consumed by trie slots are therefore unavailable
to refcounted and countable hash records.

Once enabled, saves without STACK_DEPOT_FLAG_GET or
STACK_DEPOT_FLAG_COUNTABLE use the trie. GET and COUNTABLE saves remain
hash-backed; trie-eligible saves that cannot allocate perform a single
lockless lookup, and per-save trie insertion failures do not fall back to
hash storage.

Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
 Documentation/admin-guide/kernel-parameters.txt |   7 ++
 lib/stackdepot.c                                | 100 ++++++++++++++++++++++--
 2 files changed, 101 insertions(+), 6 deletions(-)

diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
index 1af62cd16c9d..ebb7b7e1867f 100644
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -7387,6 +7387,13 @@ Kernel parameters
 			stack traces. Pools are allocated on-demand up to this
 			limit. Default value is 8191 pools.
 
+	stackdepot.trie_enabled= [KNL]
+			Format: <bool>
+			Enable trie storage for persistent, non-refcounted
+			stack depot records at boot. Disabled by default.
+			stack_depot_max_pools must leave unused pool-index
+			values for trie handles.
+
 	stacktrace	[FTRACE]
 			Enable the stack tracer on boot up.
 
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index 1e5b9fc44618..1a002063a948 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -28,6 +28,7 @@
 #include <linux/kmsan.h>
 #include <linux/list.h>
 #include <linux/mm.h>
+#include <linux/moduleparam.h>
 #include <linux/mutex.h>
 #include <linux/poison.h>
 #include <linux/printk.h>
@@ -100,8 +101,8 @@ static const char *const counter_names[] = {
 	[DEPOT_COUNTER_REFD_FREES]	= "refcounted_frees",
 	[DEPOT_COUNTER_REFD_INUSE]	= "refcounted_in_use",
 	[DEPOT_COUNTER_FREELIST_SIZE]	= "freelist_size",
-	[DEPOT_COUNTER_PERSIST_COUNT]	= "persistent_count",
-	[DEPOT_COUNTER_PERSIST_BYTES]	= "persistent_bytes",
+	[DEPOT_COUNTER_PERSIST_COUNT]	= "hash_persistent_count",
+	[DEPOT_COUNTER_PERSIST_BYTES]	= "hash_persistent_bytes",
 };
 static_assert(ARRAY_SIZE(counter_names) == DEPOT_COUNTER_COUNT);
 
@@ -180,6 +181,10 @@ static_assert(STACK_DEPOT_TRIE_POOL_FIRST_SLOT < STACK_DEPOT_TRIE_POOL_SLOTS);
 static DEFINE_STATIC_KEY_FALSE(stack_depot_trie_enabled);
 static const struct stack_depot_trie_children __rcu *stack_depot_trie_root;
 static DEFINE_RAW_SPINLOCK(stack_depot_trie_writer_lock);
+static bool stack_depot_trie_requested;
+
+module_param_named(trie_enabled, stack_depot_trie_requested, bool, 0);
+MODULE_PARM_DESC(trie_enabled, "Enable stack depot trie storage at boot");
 
 #define DEPOT_POOL_INDEX_MASK ((1U << DEPOT_POOL_INDEX_BITS) - 1)
 #define DEPOT_OFFSET_MASK ((1U << DEPOT_OFFSET_BITS) - 1)
@@ -236,8 +241,9 @@ static u32 trie_stack_id(depot_stack_handle_t handle)
 /*
  * Trie handles encode a dense stack ID. The side table maps that ID to a node
  * pointer for lockless fetch and print paths, which can run from diagnostic
- * contexts where taking a lock would be unsafe. Additional directories and
- * chunks are published lazily as stack IDs grow.
+ * contexts where taking a lock would be unsafe. Initialization installs the
+ * root; early initialization also installs the first directory and chunk.
+ * Additional directories and chunks are published lazily as stack IDs grow.
  */
 #define STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE \
 	(PAGE_SIZE / sizeof(struct stack_depot_trie_node *))
@@ -375,6 +381,75 @@ trie_side_table_prepare_stack_slot(struct stack_depot_trie_side_prealloc *preall
 	return id;
 }
 
+static inline unsigned int trie_side_table_root_size_for_max_id(u32 max_stack_id)
+{
+	unsigned int top_size;
+
+	top_size = DIV_ROUND_UP(max_stack_id,
+				STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE);
+	return DIV_ROUND_UP(top_size, STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE);
+}
+
+static int __init stack_depot_trie_init_memblock(void)
+{
+	struct stack_depot_trie_side_root *root_vec;
+	struct stack_depot_trie_side_dir *first_dir;
+	const struct stack_depot_trie_node __rcu **first_chunk;
+	size_t root_bytes;
+	u32 max_stack_id;
+	unsigned int root_size;
+
+	max_stack_id = trie_max_stack_id();
+	if (!max_stack_id)
+		return -EINVAL;
+	root_size = trie_side_table_root_size_for_max_id(max_stack_id);
+	root_bytes = struct_size_t(struct stack_depot_trie_side_root, dirs,
+				   root_size);
+
+	root_vec = memblock_alloc(root_bytes, __alignof__(*root_vec));
+	if (!root_vec)
+		return -ENOMEM;
+	first_dir = memblock_alloc(PAGE_SIZE, PAGE_SIZE);
+	if (!first_dir) {
+		memblock_free(root_vec, root_bytes);
+		return -ENOMEM;
+	}
+	first_chunk = memblock_alloc(PAGE_SIZE, PAGE_SIZE);
+	if (!first_chunk) {
+		memblock_free(first_dir, PAGE_SIZE);
+		memblock_free(root_vec, root_bytes);
+		return -ENOMEM;
+	}
+
+	root_vec->dir_capacity = root_size;
+	RCU_INIT_POINTER(root_vec->dirs[0], first_dir);
+	RCU_INIT_POINTER(first_dir->chunks[0], first_chunk);
+	trie_side_table_root = root_vec;
+	static_branch_enable(&stack_depot_trie_enabled);
+	return 0;
+}
+
+static int stack_depot_trie_init(void)
+{
+	struct stack_depot_trie_side_root *root_vec;
+	unsigned int root_size;
+	u32 max_stack_id;
+
+	max_stack_id = trie_max_stack_id();
+	if (!max_stack_id)
+		return -EINVAL;
+
+	root_size = trie_side_table_root_size_for_max_id(max_stack_id);
+	root_vec = kvzalloc_flex(*root_vec, dirs, root_size);
+	if (!root_vec)
+		return -ENOMEM;
+
+	root_vec->dir_capacity = root_size;
+	trie_side_table_root = root_vec;
+	static_branch_enable(&stack_depot_trie_enabled);
+	return 0;
+}
+
 static int trie_side_table_get_prealloc(gfp_t gfp_flags,
 					struct stack_depot_trie_side_prealloc *prealloc)
 {
@@ -702,7 +777,7 @@ static void init_stack_table(unsigned long entries)
 		INIT_LIST_HEAD(&stack_table[i]);
 }
 
-/* Allocates a hash table via memblock. Can only be used during early boot. */
+/* Initializes hash and optional trie storage during early boot. */
 int __init stack_depot_early_init(void)
 {
 	unsigned long entries = 0;
@@ -776,11 +851,15 @@ int __init stack_depot_early_init(void)
 		stack_depot_disabled = true;
 		return -ENOMEM;
 	}
+	if (stack_depot_trie_requested && stack_depot_trie_init_memblock()) {
+		pr_warn("trie storage initialization failed, disabling trie storage\n");
+		stack_depot_trie_requested = false;
+	}
 
 	return 0;
 }
 
-/* Allocates a hash table via kvcalloc. Can be used after boot. */
+/* Initializes hash and optional trie storage after boot. */
 int stack_depot_init(void)
 {
 	static DEFINE_MUTEX(stack_depot_init_mutex);
@@ -834,6 +913,15 @@ int stack_depot_init(void)
 		kvfree(stack_table);
 		stack_depot_disabled = true;
 		ret = -ENOMEM;
+		goto out_unlock;
+	}
+	if (stack_depot_trie_requested) {
+		ret = stack_depot_trie_init();
+		if (ret) {
+			pr_warn("trie storage initialization failed, disabling trie storage\n");
+			stack_depot_trie_requested = false;
+			ret = 0;
+		}
 	}
 
 out_unlock:

-- 
Git-155)

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

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

[Caleb Kan]

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