* [PATCH RFC v2 01/11] stackdepot: stop preallocating after the final pool
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 02/11] stackdepot: add caller-owned stack trace fetching Caleb Kan
` (9 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
depot_init_pool() decides whether another pool is needed before it
increments pools_num. When it registers the last allowed pool, pools_num
is still one below stack_max_pools, so the existing comparison clears
new_pool.
With new_pool cleared, stack_depot_save_flags() can allocate another
order-2 pool after a lookup miss. depot_keep_new_pool() retains its pointer
in the global new_pool, so the allocation is not lost. However, pools_num
has already reached stack_max_pools, and depot_init_pool() rejects every
attempt to register the pool. It remains allocated and unusable until
reboot. The non-NULL pointer prevents later saves from allocating more
spare pools.
Account for the pool being registered in the limit check so registering
the final pool installs STACK_DEPOT_POISON and prevents the extra
allocation.
Fixes: 31639fd6cebd ("stackdepot: use variable size records for non-evictable entries")
Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
lib/stackdepot.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index dd2717ff94bf..90c52f2e0d3f 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -323,7 +323,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);
--
Git-155)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 02/11] stackdepot: add caller-owned stack trace fetching
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 01/11] stackdepot: stop preallocating after the final pool Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 03/11] mm/page_owner: preserve accounting with countable stack depot records Caleb Kan
` (8 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
stack_depot_fetch() returns a pointer to contiguous storage owned by stack
depot. That cannot work for a backend whose frames are not contiguous, so
callers need an interface that copies the trace before they can support
both backends.
Add stack_depot_fetch_into() to copy a complete trace into caller-owned
storage. Leave the destination unchanged when it is too small, keep a zero
handle as a no-op, and document that callers must keep the handle valid
while copying it. Warn if a caller passes a NULL buffer or zero capacity
for a valid handle instead of treating the stack as missing.
Unpoison the copied entries before returning them because
lib/stackdepot.c is not instrumented by KMSAN. Add built-in KUnit tests for
exact and oversized destinations, zero handles, and undersized buffers.
Later patches add tests for stack depot internals.
Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
include/linux/stackdepot.h | 36 ++++++++++++++++++
lib/Kconfig.debug | 16 ++++++++
lib/stackdepot.c | 28 ++++++++++++++
lib/tests/Makefile | 1 +
lib/tests/stackdepot_kunit.c | 89 ++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 170 insertions(+)
diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h
index 2cc21ffcdaf9..734529767c8a 100644
--- a/include/linux/stackdepot.h
+++ b/include/linux/stackdepot.h
@@ -199,6 +199,42 @@ struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle)
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
*
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 134b15a44625..fcd74edfd93a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2785,6 +2785,22 @@ 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, 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/stackdepot.c b/lib/stackdepot.c
index 90c52f2e0d3f..4da7279d9f83 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -785,6 +785,34 @@ 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);
+
+ 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;
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 3cac3b63a752..1f72191f98bb 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -48,6 +48,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..b0c44c096976
--- /dev/null
+++ b/lib/tests/stackdepot_kunit.c
@@ -0,0 +1,89 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/array_size.h>
+#include <linux/gfp.h>
+#include <linux/stackdepot.h>
+#include <linux/string.h>
+
+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 struct kunit_case stackdepot_test_cases[] = {
+ KUNIT_CASE(stackdepot_fetch_into_roundtrip),
+ KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
+ {}
+};
+
+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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 03/11] mm/page_owner: preserve accounting with countable stack depot records
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 01/11] stackdepot: stop preallocating after the final pool Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 02/11] stackdepot: add caller-owned stack trace fetching Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 04/11] mm/kmemleak: print trie-backed stack depot traces Caleb Kan
` (7 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
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. A later patch adds a trie backend,
which 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 | 28 +++++++++++++++-------
lib/Kconfig.debug | 3 ++-
lib/stackdepot.c | 20 +++++++++++++++-
lib/tests/stackdepot_kunit.c | 55 ++++++++++++++++++++++++++++++++++++++++++++
mm/page_owner.c | 6 +++--
5 files changed, 100 insertions(+), 12 deletions(-)
diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h
index 734529767c8a..7ff67c70d727 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.
+ *
* If the provided stack trace comes from the interrupt context, only the part
* up to the interrupt entry is saved.
*
@@ -178,11 +185,12 @@ 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
*
- * 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
*/
@@ -260,10 +268,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 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/Kconfig.debug b/lib/Kconfig.debug
index fcd74edfd93a..3a78c67b6b36 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2792,7 +2792,8 @@ config STACKDEPOT_KUNIT_TEST
default KUNIT_ALL_TESTS
help
Enable this option to test stack depot API behavior at boot.
- This test is built in, so KUNIT must also be built in.
+ 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
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index 4da7279d9f83..66c5e8594566 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -94,6 +94,7 @@ static const char *const counter_names[] = {
[DEPOT_COUNTER_PERSIST_BYTES] = "persistent_bytes",
};
static_assert(ARRAY_SIZE(counter_names) == DEPOT_COUNTER_COUNT);
+static_assert(CONFIG_STACKDEPOT_MAX_FRAMES <= U16_MAX);
static int __init disable_stack_depot(char *str)
{
@@ -467,6 +468,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));
@@ -609,6 +611,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
@@ -655,6 +660,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
@@ -751,10 +759,18 @@ 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;
- 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;
}
unsigned int stack_depot_fetch(depot_stack_handle_t handle,
@@ -828,6 +844,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 b0c44c096976..3c526791ef93 100644
--- a/lib/tests/stackdepot_kunit.c
+++ b/lib/tests/stackdepot_kunit.c
@@ -6,6 +6,60 @@
#include <linux/stackdepot.h>
#include <linux/string.h>
+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[] = {
@@ -72,6 +126,7 @@ static void stackdepot_fetch_into_rejects_missing_or_short_stack(struct kunit *t
}
static struct kunit_case stackdepot_test_cases[] = {
+ KUNIT_CASE(stackdepot_countable_public),
KUNIT_CASE(stackdepot_fetch_into_roundtrip),
KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
{}
diff --git a/mm/page_owner.c b/mm/page_owner.c
index cfc31c92d765..1fb1998bc129 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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 04/11] mm/kmemleak: print trie-backed stack depot traces
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (2 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 03/11] mm/page_owner: preserve accounting with countable stack depot records Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 05/11] kmsan: report " Caleb Kan
` (6 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 05/11] kmsan: report trie-backed stack depot traces
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (3 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 04/11] mm/kmemleak: print trie-backed stack depot traces Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 06/11] mm/slub: materialize " Caleb Kan
` (5 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
KMSAN stores ordinary origin stacks and synthetic alloca and chain origins
in stack depot and retains the resulting persistent handles. Once trie
storage is enabled, these handles can refer to trie-backed entries, 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.
Pass the scratch array into a common origin-printing helper. Keep local
storage for standalone kmsan_print_origin() calls, but let kmsan_report()
reuse its existing stack_entries array after printing the report stack.
With x86-64 Clang 19, the regular nested report path uses 752 bytes, below
its 768-byte size before this conversion.
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 | 28 ++++++++++++++++------------
2 files changed, 18 insertions(+), 14 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..0770658ba932 100644
--- a/mm/kmsan/report.c
+++ b/mm/kmsan/report.c
@@ -83,9 +83,9 @@ static char *pretty_descr(char *descr)
return report_local_descr;
}
-void kmsan_print_origin(depot_stack_handle_t origin)
+static void kmsan_print_origin_with_buf(depot_stack_handle_t origin,
+ unsigned long *entries)
{
- unsigned long *entries = NULL, *chained_entries = NULL;
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, KMSAN_STACK_DEPTH);
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,
+ KMSAN_STACK_DEPTH);
+ skipnr = get_stack_skipnr(entries, chained_nr_entries);
+ stack_trace_print(entries + skipnr,
chained_nr_entries - skipnr, 0);
pr_err("\n");
continue;
@@ -147,6 +144,13 @@ void kmsan_print_origin(depot_stack_handle_t origin)
}
}
+void kmsan_print_origin(depot_stack_handle_t origin)
+{
+ unsigned long entries[KMSAN_STACK_DEPTH];
+
+ kmsan_print_origin_with_buf(origin, entries);
+}
+
void kmsan_report(depot_stack_handle_t origin, void *address, int size,
int off_first, int off_last, const void __user *user_addr,
enum kmsan_bug_reason reason)
@@ -193,7 +197,7 @@ void kmsan_report(depot_stack_handle_t origin, void *address, int size,
0);
pr_err("\n");
- kmsan_print_origin(origin);
+ kmsan_print_origin_with_buf(origin, stack_entries);
if (size) {
pr_err("\n");
--
Git-155)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 06/11] mm/slub: materialize trie-backed stack depot traces
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (4 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 05/11] kmsan: report " Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 07/11] drm/locking: preserve deadlock diagnostics for trie-backed stacks Caleb Kan
` (4 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
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 f9b56cb439e7..4aa1c5a45718 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -8198,12 +8198,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];
}
@@ -8211,7 +8211,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];
}
@@ -9946,12 +9946,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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 07/11] drm/locking: preserve deadlock diagnostics for trie-backed stacks
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (5 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 06/11] mm/slub: materialize " Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 08/11] scripts/gdb: reject trie-backed stack depot handles Caleb Kan
` (3 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
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().
A later patch allows persistent stack depot saves to return trie-backed
handles, while stack_depot_fetch() remains limited to hash-backed records.
Use stack_depot_snprint() to format either backend. Keep the PAGE_SIZE
buffer and leave the warning text, existing indentation, and backtrace
unchanged.
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 e14814c30d8c..f48b02379b71 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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 08/11] scripts/gdb: reject trie-backed stack depot handles
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (6 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 07/11] drm/locking: preserve deadlock diagnostics for trie-backed stacks Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 09/11] stackdepot: add architecture hooks for compact frame storage Caleb Kan
` (2 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
The lx-stack_depot_lookup command can reconstruct stacks only from
contiguous hash-backed records. A later patch will encode trie-backed
handles as dense stack IDs in pool_index_plus_1 and offset. Without an
explicit check, a trie handle enters the hash-only out-of-bounds path.
Reject pool_index_plus_1 values above stack_max_pools before looking up a
hash pool, and report that trie-backed handles are unsupported. Supporting
them would require the helper to walk the side table and parent links,
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)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 09/11] stackdepot: add architecture hooks for compact frame storage
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (7 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 08/11] scripts/gdb: reject trie-backed stack depot handles Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 10/11] stackdepot: share persistent stack prefixes with trie storage Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 11/11] stackdepot: add KUnit tests for " Caleb Kan
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
Path-compressed trie nodes can reduce their frame storage further when an
architecture can represent kernel text and module addresses in 32 bits.
Add architecture hooks that compress a frame only when decompression
reproduces the original address exactly.
Store arm64 frames as signed 32-bit offsets from _text. This covers the
2 GB module relocation window without depending on a 4 GB high-bit
boundary. On x86-64, store the low 32 bits when the upper 32 bits are all
set. Keep other frames full-width, and provide a generic implementation
that always rejects compression.
Make the generic header available to architectures without a specialized
implementation and wire it explicitly for UML. Add KUnit coverage for raw
fallback, arm64 boundary round trips, and native x86-64 prefix compression.
These hooks do not change stack depot behavior until a later patch adds
trie storage.
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 ++++++++
lib/tests/stackdepot_kunit.c | 86 +++++++++++++++++++++++++++++++++++++
6 files changed, 186 insertions(+)
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 2bc00c67dc54..d8402a6afc70 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/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c
index 3c526791ef93..e4a7f1c83457 100644
--- a/lib/tests/stackdepot_kunit.c
+++ b/lib/tests/stackdepot_kunit.c
@@ -3,9 +3,21 @@
#include <kunit/test.h>
#include <linux/array_size.h>
#include <linux/gfp.h>
+#include <linux/limits.h>
#include <linux/stackdepot.h>
#include <linux/string.h>
+#include <asm/stackdepot.h>
+
+#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_countable_public(struct kunit *test)
{
unsigned long plain_entries[] = {
@@ -125,10 +137,84 @@ static void stackdepot_fetch_into_rejects_missing_or_short_stack(struct kunit *t
KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected));
}
+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_countable_public),
KUNIT_CASE(stackdepot_fetch_into_roundtrip),
KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
+ 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
{}
};
--
Git-155)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 10/11] stackdepot: share persistent stack prefixes with trie storage
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (8 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 09/11] stackdepot: add architecture hooks for compact frame storage Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
2026-09-08 13:13 ` [PATCH RFC v2 11/11] stackdepot: add KUnit tests for " Caleb Kan
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
Stack depot's hash backend deduplicates identical traces, but stores every
different trace in full. Persistent traces often share most of their
frames, so this wastes memory and can exhaust the pool limit. Once the
pools are full, a new trace returns 0 and later diagnostics can lose useful
stack information.
Add an opt-in path-compressed trie for persistent records saved without
STACK_DEPOT_FLAG_GET or STACK_DEPOT_FLAG_COUNTABLE. Store a run of frames
in each node and branch only where traces differ. Insertion can descend
through an existing path, split a partial match, make an internal node a
stored trace, or attach a new suffix.
Encode dense stack IDs in pool-index values that cannot name a hash pool.
A sparse side table maps each ID to the node where the trace ends. Fetching
a trace follows parent links from that node. Stored traces and IDs are not
recycled.
Use the architecture hooks from the preceding patch to store a frame in 32
bits only when it can be reconstructed exactly. Keep all other frames at
full width.
Allocate trie nodes and child arrays from contiguous runs of 16-byte slots
in the existing order-2 pools. Each pool records an upper bound on its
largest free run so the allocator can skip pools that are too fragmented.
Search from a next-fit cursor first, then scan the whole pool so released
holes and runs that cross the cursor remain visible. Record the exact
longest run only after a complete scan fails.
A child array must fit in one pool. On a 4 KiB, 64-bit system, one node can
have at most 1,024 children. An insertion that would add a 1,025th child
returns 0, while existing traces remain valid. The largest node observed on
a pre-production server had about 835 children.
Take the writer lock before the existing pool lock. Reserve everything
that can fail before publishing a trace. Release unpublished node and
child slots immediately, but keep registered pools, side-table space,
stored traces, and IDs. When a node or child array is replaced, keep it
until a later allocating insertion sees that its RCU grace period has
ended.
An NMI save only looks for an existing trie record and returns 0 on a miss.
Outside NMI, a save gets one insertion attempt when
STACK_DEPOT_FLAG_CAN_ALLOC is clear or its GFP flags do not allow spinning
on raw locks. The attempt uses only pool and side-table space already
available. If spinning is allowed, take the writer and pool locks;
otherwise try each lock once. Access to the side-table page cache also uses
a trylock. The attempt does not allocate, retry, wait for RCU, or fall back
to the hash backend.
Allocating saves try at most three times. One try can skip preallocation
after seeing new_pool, then lose that pool to another save. A maximum-depth
insertion can also need two new pools. Trie insertion failure returns 0
instead of consuming hash capacity.
Extend stack_depot_fetch_into(), stack_depot_print(), and
stack_depot_snprint() to support both backends. Keep stack_depot_fetch()
hash-only because it returns a pointer to contiguous depot-owned storage.
Print 16 frames at a time so stack use stays fixed instead of growing with
CONFIG_STACKDEPOT_MAX_FRAMES.
The hash and trie backends share stack_pools and the configured pool limit.
A pool used by the trie is unavailable for hash-backed GET and COUNTABLE
records. Hash handles reserve pool-index values through
stack_depot_max_pools, and trie handles use the remaining values for stack
IDs. With 64 KiB pages, the default limit leaves no values for trie IDs, so
stack_depot_max_pools must be lowered before enabling the trie.
Rename the persistent_count and persistent_bytes debugfs counters with a
hash prefix because they do not include trie storage.
Add the stackdepot.trie_enabled boot parameter and leave it disabled by
default. Initialize the trie root before enabling the static key. If no
handle values are available for trie IDs or allocating the root metadata
fails, leave the hash backend initialized at its configured capacity.
I collected stack depot state from four live KASAN servers using the same
kernel revision, 4 KiB pages, and an 8,192-pool limit. The servers ran for
61 to 67 hours and remained active while the values were collected, so the
figures below are rounded.
arm64 x86-64
trie off trie on trie off trie on
Run time (hours) 61 64 65 67
Stored records 162k 87k 498k 217k
Registered pools 2,630 925 8,192 1,940
Pool budget used 32% 11% 100% 24%
The servers ran different workloads and stored different traces, so this
is not a controlled comparison. Exact memory savings depend on the
workload.
The trie figures came from RFC v1. That version did not insert a new trace
when a save could not allocate, so RFC v2 may store more traces and use
more pools than shown here.
On arm64, the final allocator reduced the median number of bitmap probes
from 36,939,363 to 1,529,482 without increasing pool use. The first-fit
allocator used a median of 1,101 pools, while the final allocator used
1,100.
I also pinned a benchmark to one CPU on KASAN-enabled arm64 and x86-64
systems running the Linux 6.18.48 port. It inserted 32,768 distinct
32-frame traces. Within each group of 64 traces, 75% of the frames were
shared, and all frames could be compressed. The insertion order was
shuffled. The warm save-hit and fetch tests then repeated the same traces
32 times.
arm64 CPU ns/op x86-64 CPU ns/op
hash trie hash trie
Insertion 777 9,417 792 11,269
Warm save hit 945 1,287 623 1,012
Fetch 251 511 123 476
First insertion was about 12 times slower on arm64 and 14 times slower on
x86-64. A warm save hit was 1.4 to 1.6 times slower, and fetch was 2 to 4
times slower. All four runs completed without save failures or validation
errors.
Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
Documentation/admin-guide/kernel-parameters.txt | 7 +
include/linux/stackdepot.h | 23 +-
lib/stackdepot.c | 1600 ++++++++++++++++++++++-
3 files changed, 1616 insertions(+), 14 deletions(-)
diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
index 68647ff4bdd2..b02bcbaef5dc 100644
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -7449,6 +7449,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/include/linux/stackdepot.h b/include/linux/stackdepot.h
index 7ff67c70d727..3126d17b9265 100644
--- a/include/linux/stackdepot.h
+++ b/include/linux/stackdepot.h
@@ -151,6 +151,12 @@ static inline int stack_depot_early_init(void) { return 0; }
* 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 first look up an existing stack, then make one
+ * best-effort insertion attempt without allocating. NMI callers stop after the
+ * lookup. Other callers that cannot spin use trylocks and fail if a required
+ * lock is unavailable. 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.
*
@@ -159,7 +165,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,
@@ -176,6 +182,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.
*
@@ -199,9 +209,14 @@ 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,
@@ -270,8 +285,8 @@ int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size,
*
* 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 are owned by stack depot
- * for the lifetime of the system.
+ * %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
diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index 66c5e8594566..33e475d94131 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -2,9 +2,11 @@
/*
* 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 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.
@@ -14,13 +16,19 @@
#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>
+#include <linux/moduleparam.h>
#include <linux/mutex.h>
#include <linux/poison.h>
#include <linux/printk.h>
@@ -36,9 +44,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);
@@ -54,6 +65,9 @@ static bool __stack_depot_early_init_passed __initdata;
/* Initial seed for jhash2. */
#define STACK_HASH_SEED 0x9747b28c
+/* Bound 64-bit print scratch to 128 bytes while amortizing trie walks. */
+#define STACK_DEPOT_PRINT_CHUNK_FRAMES 16
+
/* Hash table of stored stack records. */
static struct list_head *stack_table;
/* Fixed order of the number of table buckets. Used when KASAN is enabled. */
@@ -63,18 +77,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,
@@ -90,12 +104,695 @@ 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);
+
+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)
+
+static_assert(STACK_DEPOT_TRIE_POOL_SLOTS - 1 <= U16_MAX);
+
+struct stack_depot_trie_pool {
+ struct list_head list;
+ unsigned int free_slots;
+ /* Conservative upper bound on the largest free run. */
+ u16 free_run_upper_bound;
+ /* First physical slot considered by the next reservation. */
+ u16 next_slot;
+ 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);
+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)
+
+/* 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. 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 *))
+#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 -> side-table cache lock. */
+
+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());
+}
+
+/* Published capacity remains useful if insertion fails and needs no rollback. */
+static bool
+trie_side_table_try_take_cache(struct stack_depot_trie_side_prealloc *prealloc,
+ bool need_dir)
+{
+ bool taken = false;
+
+ lockdep_assert_held(&stack_depot_trie_writer_lock);
+ lockdep_assert_held(&pool_lock);
+
+ if (!raw_spin_trylock(&trie_side_table_cache_lock))
+ return false;
+ if ((!prealloc->chunk && !trie_side_table_cache.chunk) ||
+ (need_dir && !prealloc->dir && !trie_side_table_cache.dir))
+ goto out_unlock;
+
+ if (need_dir && !prealloc->dir) {
+ prealloc->dir = trie_side_table_cache.dir;
+ trie_side_table_cache.dir = NULL;
+ }
+ if (!prealloc->chunk) {
+ prealloc->chunk = trie_side_table_cache.chunk;
+ trie_side_table_cache.chunk = NULL;
+ }
+ taken = true;
+
+out_unlock:
+ raw_spin_unlock(&trie_side_table_cache_lock);
+ return taken;
+}
+
+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);
+ lockdep_assert_held(&pool_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) {
+ if ((!prealloc->dir || !prealloc->chunk) &&
+ !trie_side_table_try_take_cache(prealloc, true))
+ return 0;
+ 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) {
+ if (!prealloc->chunk &&
+ !trie_side_table_try_take_cache(prealloc, false))
+ return 0;
+ chunk = prealloc->chunk;
+ prealloc->chunk = NULL;
+ rcu_assign_pointer(dir->chunks[idx], chunk);
+ }
+
+ 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;
+ size_t root_bytes;
+ 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_bytes = struct_size_t(struct stack_depot_trie_side_root, dirs, root_size);
+ root_vec = kvzalloc(root_bytes, GFP_KERNEL);
+ 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)
+{
+ 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 start = pool->next_slot;
+ unsigned int run = 0;
+ unsigned int longest_run = 0;
+ unsigned int i;
+ unsigned int slot;
+
+scan:
+ run = 0;
+ longest_run = 0;
+ for (slot = start; slot < STACK_DEPOT_TRIE_POOL_SLOTS; slot++) {
+ if (pool->used[slot / BITS_PER_LONG] &
+ BIT(slot % BITS_PER_LONG)) {
+ run = 0;
+ continue;
+ }
+ run++;
+ longest_run = max(longest_run, run);
+ 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;
+ if (slot + 1 == STACK_DEPOT_TRIE_POOL_SLOTS)
+ pool->next_slot = STACK_DEPOT_TRIE_POOL_FIRST_SLOT;
+ else
+ pool->next_slot = slot + 1;
+ return slot + 1 - nr_slots;
+ }
+
+ if (start != STACK_DEPOT_TRIE_POOL_FIRST_SLOT) {
+ /* Keep holes and runs crossing the cursor visible. */
+ start = STACK_DEPOT_TRIE_POOL_FIRST_SLOT;
+ goto scan;
+ }
+
+ pool->free_run_upper_bound = longest_run;
+ 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) {
+ if (pool->free_slots < nr_slots ||
+ pool->free_run_upper_bound < nr_slots)
+ continue;
+ 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;
+ pool->free_run_upper_bound = pool->free_slots;
+ pool->next_slot = 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;
+ /* A release can join at most two runs bounded by the old value. */
+ pool->free_run_upper_bound = min(pool->free_slots,
+ 2 * pool->free_run_upper_bound + 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);
+ lockdep_assert_held(&pool_lock);
+ trie_retire_children(children);
+ retired = trie_retired_children(children);
+ retired->pending_node = node;
+}
+
+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);
@@ -147,7 +844,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;
@@ -221,11 +918,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);
@@ -279,6 +980,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:
@@ -643,6 +1353,101 @@ 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);
+ raw_spin_lock(&pool_lock);
+ printk_deferred_enter();
+ trie_drain_pending_children();
+ stack_id = stack_depot_trie_insert(entries, nr_entries,
+ &pool_prealloc, &side_prealloc);
+ if (pool_prealloc)
+ depot_keep_new_pool(&pool_prealloc);
+ printk_deferred_exit();
+ raw_spin_unlock(&pool_lock);
+ raw_spin_unlock_irqrestore(&stack_depot_trie_writer_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;
+}
+
+static depot_stack_handle_t
+stack_depot_trie_save_constrained(unsigned long *entries,
+ unsigned int nr_entries, bool trylock)
+{
+ struct stack_depot_trie_side_prealloc side_prealloc = {};
+ void *pool_prealloc = NULL;
+ depot_stack_handle_t handle;
+ unsigned long flags;
+ u32 stack_id;
+
+ handle = trie_find_handle(entries, nr_entries);
+ if (handle)
+ return handle;
+
+ if (trylock) {
+ if (!raw_spin_trylock_irqsave(&stack_depot_trie_writer_lock, flags))
+ return 0;
+ if (!raw_spin_trylock(&pool_lock)) {
+ raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags);
+ return 0;
+ }
+ } else {
+ raw_spin_lock_irqsave(&stack_depot_trie_writer_lock, flags);
+ raw_spin_lock(&pool_lock);
+ }
+
+ printk_deferred_enter();
+ stack_id = stack_depot_trie_insert(entries, nr_entries, &pool_prealloc,
+ &side_prealloc);
+ printk_deferred_exit();
+ raw_spin_unlock(&pool_lock);
+ raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags);
+
+ return stack_id ? trie_handle(stack_id) : 0;
+}
+
depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
unsigned int nr_entries,
gfp_t alloc_flags,
@@ -677,6 +1482,20 @@ 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 | STACK_DEPOT_FLAG_COUNTABLE)) &&
+ static_branch_unlikely(&stack_depot_trie_enabled)) {
+ if (nr_entries > CONFIG_STACKDEPOT_MAX_FRAMES)
+ nr_entries = CONFIG_STACKDEPOT_MAX_FRAMES;
+ if (in_nmi()) {
+ WARN_ON_ONCE(can_alloc);
+ return trie_find_handle(entries, nr_entries);
+ }
+ if (!can_alloc)
+ return stack_depot_trie_save_constrained(entries, nr_entries,
+ !allow_spin);
+ return stack_depot_trie_save(entries, nr_entries, alloc_flags);
+ }
+
hash = hash_stack(entries, nr_entries);
bucket = &stack_table[hash & stack_hash_mask];
@@ -763,6 +1582,8 @@ 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;
stack = depot_fetch_stack(handle);
if (!stack)
@@ -773,6 +1594,714 @@ struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle)
return stack;
}
+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;
+
+ /* 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);
+ }
+
+ return new_stack_id;
+
+err_release:
+ if (new_children)
+ trie_pool_release_children(new_children);
+ 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;
+
+ /* 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;
+ }
+
+ /* 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);
+ 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. */
+ promoted_node = trie_pool_alloc(node_size, pool_prealloc);
+ if (!promoted_node)
+ return 0;
+ new_children = trie_pool_alloc_children(children->capacity, pool_prealloc);
+ if (!new_children)
+ goto out_release_node;
+
+ /* 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);
+ 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);
+ lockdep_assert_held(&pool_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_range(const struct stack_depot_trie_node *node,
+ unsigned int offset,
+ unsigned long *entries,
+ unsigned int max_entries)
+{
+ const struct stack_depot_trie_node *cur;
+ unsigned int end;
+ unsigned int start;
+ 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 (offset >= total)
+ return 0;
+
+ max_entries = min(max_entries, total - offset);
+ end = offset + max_entries;
+ pos = total;
+ for (cur = node; cur; cur = trie_load_parent(cur)) {
+ pos -= cur->run.nr_entries;
+ start = max(pos, offset);
+ for (i = start; i < min(pos + cur->run.nr_entries, end); i++)
+ stack_depot_trie_node_frame(cur, i - pos, &entries[i - offset]);
+ }
+
+ return max_entries;
+}
+
+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;
+}
+
+static unsigned int trie_fetch_handle_range(depot_stack_handle_t handle,
+ unsigned int offset,
+ 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_range(node, offset, 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)
{
@@ -787,6 +2316,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);
/*
@@ -813,6 +2344,8 @@ unsigned int stack_depot_fetch_into(depot_stack_handle_t handle,
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)
@@ -835,6 +2368,8 @@ void stack_depot_put(depot_stack_handle_t handle)
if (!handle || stack_depot_disabled)
return;
+ if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle)))
+ return;
stack = depot_fetch_stack(handle);
/*
@@ -851,11 +2386,53 @@ void stack_depot_put(depot_stack_handle_t handle)
}
EXPORT_SYMBOL_GPL(stack_depot_put);
+static void trie_print(depot_stack_handle_t handle)
+{
+ unsigned long entries[STACK_DEPOT_PRINT_CHUNK_FRAMES];
+ unsigned int nr_entries;
+ unsigned int offset = 0;
+
+ while ((nr_entries = trie_fetch_handle_range(handle, offset, entries,
+ ARRAY_SIZE(entries)))) {
+ stack_trace_print(entries, nr_entries, 0);
+ offset += nr_entries;
+ }
+}
+
+static int trie_snprint(depot_stack_handle_t handle, char *buf, size_t size,
+ int spaces)
+{
+ unsigned long entries[STACK_DEPOT_PRINT_CHUNK_FRAMES];
+ unsigned int generated;
+ unsigned int nr_entries;
+ unsigned int offset = 0;
+ unsigned int total = 0;
+
+ while (size &&
+ (nr_entries = trie_fetch_handle_range(handle, offset, entries,
+ ARRAY_SIZE(entries)))) {
+ generated = stack_trace_snprint(buf, size, entries, nr_entries, spaces);
+ total += generated;
+ if (generated >= size)
+ break;
+ buf += generated;
+ size -= generated;
+ offset += nr_entries;
+ }
+
+ return total;
+}
+
void stack_depot_print(depot_stack_handle_t stack)
{
unsigned long *entries;
unsigned int nr_entries;
+ if (stack_depot_handle_is_trie(stack)) {
+ trie_print(stack);
+ return;
+ }
+
nr_entries = stack_depot_fetch(stack, &entries);
if (nr_entries > 0)
stack_trace_print(entries, nr_entries, 0);
@@ -868,6 +2445,9 @@ 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))
+ return trie_snprint(handle, buf, size, spaces);
+
nr_entries = stack_depot_fetch(handle, &entries);
return nr_entries ? stack_trace_snprint(buf, size, entries, nr_entries,
spaces) : 0;
--
Git-155)
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH RFC v2 11/11] stackdepot: add KUnit tests for trie storage
2026-09-08 13:13 [PATCH RFC v2 00/11] stackdepot: reduce memory use for persistent stack records with a trie Caleb Kan
` (9 preceding siblings ...)
2026-09-08 13:13 ` [PATCH RFC v2 10/11] stackdepot: share persistent stack prefixes with trie storage Caleb Kan
@ 2026-09-08 13:13 ` Caleb Kan
10 siblings, 0 replies; 12+ messages in thread
From: Caleb Kan @ 2026-09-08 13:13 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, kasan-dev, Vlastimil Babka,
Alexander Potapenko, Marco Elver, Dmitry Vyukov,
Andrey Konovalov, Oscar Salvador, Caleb Kan, kernel-team
From: Caleb Kan <ckan@cloudflare.com>
Trie insertion changes shared topology, but handles returned before later
splits, promotions, and child-array replacements must continue to fetch
and deduplicate the same traces.
Extend the built-in stack depot KUnit suite to test trie storage through
the public APIs and direct insertion cases. The public cases continue to
run against the hash backend by default and exercise the trie when it is
enabled.
Cover save and deduplication behavior, maximum-depth and overlong stacks,
insertion when allocation is not permitted, GET records, extra bits,
caller-owned fetching, and complete and truncated formatted output.
Exercise append, descent, split, promotion, child-array growth, and
tail-append paths. Verify that handles returned before these changes still
fetch the same trace and are returned again when that trace is saved.
Add round-trip tests for compressed and full-width frames on arm64 and
native x86-64, plus an architecture-independent full-width test. Keep the
topology fixtures portable to 32-bit architectures. On 4 KiB arm64 and
native x86-64 builds configured for 256 frames, a maximum-depth trace that
alternates compressed and full-width frames creates one node per frame and
requires more space than one otherwise-empty trie pool.
Require stackdepot_kunit.trie_pool_limit to match the
stack_depot_max_pools value used at boot before running trie-only cases.
This makes backend selection explicit and prevents an initialization
failure from silently running the hash tests instead. The save-flags and
snprint cases also check that saves return trie handles when a trie pool
limit is supplied.
Signed-off-by: Caleb Kan <ckan@cloudflare.com>
---
lib/tests/stackdepot_kunit.c | 352 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 352 insertions(+)
diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c
index e4a7f1c83457..b86b84d56176 100644
--- a/lib/tests/stackdepot_kunit.c
+++ b/lib/tests/stackdepot_kunit.c
@@ -3,12 +3,19 @@
#include <kunit/test.h>
#include <linux/array_size.h>
#include <linux/gfp.h>
+#include <linux/kallsyms.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>
@@ -18,6 +25,222 @@ static inline unsigned long stackdepot_arm64_frame(long offset)
}
#endif
+static unsigned long stackdepot_test_frame(unsigned int i)
+{
+#ifdef CONFIG_ARM64
+ return i & 1 ? 0x1000UL + i * 0x1000UL :
+ stackdepot_arm64_frame(i * 4);
+#elif defined(CONFIG_X86_64) && !defined(CONFIG_UML)
+ return i & 1 ? 0xffff888000000000UL + i * 0x1000UL :
+ 0xffffffff10000000UL + i * 0x10UL;
+#else
+ return 0x1000UL + i * 0x1000UL;
+#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++)
+ entries[i] = stackdepot_test_frame(i);
+
+ 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)
+{
+ union handle_parts parts;
+ unsigned long entries[] = { 0x501000UL, 0x502000UL, 0x503000UL };
+ unsigned long get_entries[] = { 0x601000UL, 0x602000UL };
+ unsigned long missing_entries[] = { 0x701000UL, 0x702000UL };
+ unsigned long blocking_entries[] = { 0x711000UL, 0x712000UL };
+ unsigned long fetched[ARRAY_SIZE(entries)] = {};
+ depot_stack_handle_t blocking_handle;
+ 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;
+ u32 pool_index_plus_1;
+ 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);
+ noalloc_handle = stack_depot_save_flags(missing_entries,
+ ARRAY_SIZE(missing_entries),
+ GFP_KERNEL, 0);
+ KUNIT_ASSERT_NE(test, noalloc_handle, (depot_stack_handle_t)0);
+ if (expected_trie_pool_limit >= 0) {
+ parts.handle = noalloc_handle;
+ pool_index_plus_1 = parts.pool_index_plus_1;
+ KUNIT_EXPECT_GT(test, pool_index_plus_1,
+ (u32)expected_trie_pool_limit);
+ }
+ nr_entries = stack_depot_fetch_into(noalloc_handle, fetched,
+ ARRAY_SIZE(fetched));
+ KUNIT_EXPECT_EQ(test, nr_entries,
+ (unsigned int)ARRAY_SIZE(missing_entries));
+ KUNIT_EXPECT_MEMEQ(test, fetched, missing_entries, sizeof(missing_entries));
+ KUNIT_EXPECT_EQ(test,
+ stack_depot_save_flags(missing_entries,
+ ARRAY_SIZE(missing_entries),
+ no_spin, 0),
+ noalloc_handle);
+
+ blocking_handle = stack_depot_save_flags(blocking_entries,
+ ARRAY_SIZE(blocking_entries),
+ GFP_KERNEL, 0);
+ KUNIT_ASSERT_NE(test, blocking_handle, (depot_stack_handle_t)0);
+ if (expected_trie_pool_limit >= 0) {
+ parts.handle = blocking_handle;
+ pool_index_plus_1 = parts.pool_index_plus_1;
+ KUNIT_EXPECT_GT(test, pool_index_plus_1,
+ (u32)expected_trie_pool_limit);
+ }
+ memset(fetched, 0, sizeof(fetched));
+ nr_entries = stack_depot_fetch_into(blocking_handle, fetched,
+ ARRAY_SIZE(fetched));
+ KUNIT_EXPECT_EQ(test, nr_entries,
+ (unsigned int)ARRAY_SIZE(blocking_entries));
+ KUNIT_EXPECT_MEMEQ(test, fetched, blocking_entries,
+ sizeof(blocking_entries));
+
+ 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)
+{
+ const unsigned int nr_entries = CONFIG_STACKDEPOT_MAX_FRAMES;
+ const size_t buf_size = nr_entries * (KSYM_SYMBOL_LEN + 4);
+ unsigned long *entries;
+ char *expected;
+ char *actual;
+ depot_stack_handle_t handle;
+ unsigned int expected_len;
+ unsigned int prefix_entries;
+ unsigned int prefix_len;
+ size_t output_size;
+ unsigned int i;
+ int actual_len;
+
+ KUNIT_ASSERT_EQ(test, stack_depot_init(), 0);
+ entries = kunit_kmalloc_array(test, nr_entries, sizeof(*entries),
+ GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, entries);
+ expected = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, expected);
+ actual = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, actual);
+ for (i = 0; i < nr_entries; i++)
+ entries[i] = stackdepot_test_frame(i);
+
+ handle = stack_depot_save(entries, nr_entries, GFP_KERNEL);
+ KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0);
+ if (expected_trie_pool_limit >= 0) {
+ union handle_parts parts = { .handle = handle };
+
+ KUNIT_EXPECT_GT(test, (u32)parts.pool_index_plus_1,
+ (u32)expected_trie_pool_limit);
+ }
+ expected_len = stack_trace_snprint(expected, buf_size, entries,
+ nr_entries, 2);
+ actual_len = stack_depot_snprint(handle, actual, buf_size, 2);
+ KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len);
+ KUNIT_EXPECT_STREQ(test, actual, expected);
+
+ prefix_entries = nr_entries / 2 + 1;
+ prefix_len = stack_trace_snprint(expected, buf_size, entries,
+ prefix_entries, 2);
+ KUNIT_ASSERT_LE(test, (size_t)prefix_len + 2, buf_size);
+ output_size = prefix_len + 2;
+ memset(expected, 0, buf_size);
+ memset(actual, 0, buf_size);
+ expected_len = stack_trace_snprint(expected, output_size, entries,
+ nr_entries, 2);
+ actual_len = stack_depot_snprint(handle, actual, output_size, 2);
+ KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len);
+ KUNIT_EXPECT_STREQ(test, actual, expected);
+}
+
static void stackdepot_countable_public(struct kunit *test)
{
unsigned long plain_entries[] = {
@@ -137,6 +360,129 @@ static void stackdepot_fetch_into_rejects_missing_or_short_stack(struct kunit *t
KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected));
}
+static void stackdepot_trie_topology_roundtrip(struct kunit *test,
+ bool constrained)
+{
+ union handle_parts parts;
+ unsigned long seed[] = { 0x191000UL, 0x192000UL };
+ 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)];
+ depot_stack_handle_t seed_handle;
+ unsigned long fetched[ARRAY_SIZE(stacks[0])];
+ gfp_t no_spin = GFP_NOWAIT & ~__GFP_RECLAIM;
+ u32 pool_index_plus_1;
+ unsigned int j;
+ 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);
+ if (constrained) {
+ seed_handle = stack_depot_save(seed, ARRAY_SIZE(seed), GFP_KERNEL);
+ KUNIT_ASSERT_NE(test, seed_handle, (depot_stack_handle_t)0);
+ for (i = 0; i < ARRAY_SIZE(stacks); i++)
+ for (j = 0; j < nr_entries[i]; j++)
+ stacks[i][j] += 0x10000000UL;
+ }
+
+ for (i = 0; i < ARRAY_SIZE(stacks); i++) {
+ if (constrained)
+ handles[i] = stack_depot_save_flags(stacks[i], nr_entries[i],
+ GFP_KERNEL, 0);
+ else
+ 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]));
+ if (constrained)
+ KUNIT_EXPECT_EQ(test,
+ stack_depot_save_flags(stacks[i], nr_entries[i],
+ no_spin, 0),
+ handles[i]);
+ else
+ KUNIT_EXPECT_EQ(test,
+ stack_depot_save(stacks[i], nr_entries[i],
+ GFP_KERNEL),
+ handles[i]);
+ }
+}
+
+static void stackdepot_trie_topology_allocating(struct kunit *test)
+{
+ stackdepot_trie_topology_roundtrip(test, false);
+}
+
+static void stackdepot_trie_topology_constrained(struct kunit *test)
+{
+ stackdepot_trie_topology_roundtrip(test, true);
+}
+
+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;
@@ -205,9 +551,15 @@ static void stackdepot_frame_arm64(struct kunit *test)
#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_countable_public),
KUNIT_CASE(stackdepot_fetch_into_roundtrip),
KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack),
+ KUNIT_CASE(stackdepot_trie_topology_allocating),
+ KUNIT_CASE(stackdepot_trie_topology_constrained),
+ 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),
--
Git-155)
^ permalink raw reply [flat|nested] 12+ messages in thread