From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f49.google.com (mail-ej1-f49.google.com [209.85.218.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 8B5CD41D202 for ; Mon, 17 Aug 2026 12:43:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970588; cv=none; b=PXwU1Ie2anqBMlN8o8qTLJgyat/K7lBLqUpuHHNWZhO6m4h7NV4KNbQQU/yp9cECECjfRSQnqnHO+cKi1cycxuvaVO67PEYAYvFWjdAJX9Qw88Ri3PPdmdST9ySH5mg0aNOqBy0ASv5ehRUVjeUfx6KKb7NeWRm7ge327tqG6Hg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970588; c=relaxed/simple; bh=y1//r9AsyB0aQNNqYNLBISR0CWIX0Xz5YqTJCCoqw4U=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=rur1wMqeIjDnPvyFHWarB4WiTfiLdKV0lRf8GBLFFZ8YwYFu7Ky/S4LQBYnhVNgeGX59lju+zaMeRBLE953tynuAWXIHkHbvMjhLhiM77tpmZaWzfdaOY0Gcig2Y1znSQiNWzhwF4N6ki1MhkAgdyE/hGZWxsKbCwIlBIumNDog= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=jU42CpbC; arc=none smtp.client-ip=209.85.218.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jU42CpbC" Received: by mail-ej1-f49.google.com with SMTP id a640c23a62f3a-c15d47266baso374741866b.3 for ; Mon, 17 Aug 2026 05:43:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970582; x=1787575382; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=aDMHj0ZBA+aTTncLNP9FPQM+fONDBWUSp9I8gtN+JHE=; b=jU42CpbCOK+ZZ2zafY5RAJzK7KeBXjA//DbMa/poLHy2tTat7PzT1KuswRSzEw00Ns GLIbENA2NbHZM3Upvkz3dOXwYt5PICYMexYYTL2gwi/tZoefs20+hJ/aOXpSQtFm4l4c h7eDfjj8PQZkNl75wg02pYMAsSRFAE7YGQgXRFSKP/eDIQ3dEJfBiJy9oZoAo3TEdRuW zv2tJzn0IlLqWcQPE87xN/7HP3l6CjiwrFTc15ZxcXMPezQBFnMk/1hEX5pE+PuVCN08 qLVka2mU24mcwWdv0UyIx0IDQVrZD2WEUFwMsjx5CWq7ADbbuOeY5j6LwLp60Xvg9LTX M69Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970582; x=1787575382; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=aDMHj0ZBA+aTTncLNP9FPQM+fONDBWUSp9I8gtN+JHE=; b=IC95rU4qw7lIyzXzTqNndPBn+uD7rtUAzd8NhAv9sU6+175Fhi5n4sL5jcl4y13L5s xh6ZfrxvkVQ0sdvjywT5SNOb67VXUAfzAorDZo+y/EkMWGvmZTYogaXO8p84M3cInSoL l39V7EkkDJezdeps+tRwEqxg8tOmXYT1hGA4FR6aHqAo18/OFSbcwerm1byRUJjN98Lb AEjQNRoGN7qK5KOsHHPN/rqMVKfML2bLEilvkkghzfJD0KXX+0gzyjbKpO0G7oFz4ZEi nMOuLgyYOHjpYNXIFJYo3W5wNsjegURyVIBmBK9u/D0QUKRhu7hqGHeaKVqZQZd9x4kC lWNQ== X-Forwarded-Encrypted: i=1; AHgh+RonjeRQxGXUW/RwCe+yzEuLXkKW0hys/X+JpiM25jyuf1cMq7HXgRHBZbnRjwSRX35kQJSRCB4a0BHtS2M=@vger.kernel.org X-Gm-Message-State: AOJu0YzqiQTHkKf1RRnsjGtR3demYH5fkiSAqPaM/sTqULpXVxTQROWx hBMjuxl/DtXZS/Aj9ndjwV3DvWQCrKhvjzrJbWNk1NA5RhsoRSrn3a3d X-Gm-Gg: AR+sD13XizW/7RMTItWdvKEF6K7P3CsBMZMl6uUgbFfplzob1LB9Gdw5NOuYeXEBjGA GKtJzuXPhOe9XEWz9KjZeUneJqeYb8TNO/Z9XZPWHAIpaOMPgKrvKI+6lrg/lY2G2ZxII6xFIQq db4I+aWR1N32dVyq1sCCjK2RvhK91DqT8iVdD2BM9/MsYSiOtrl7pNMYlSAb1lbfln7VZFH9/Ir AoV+vPfOh/6o6IhCrny9N8vt1To4HqClp14ehNZQQMg+FQYv++OF4z4cHznXqfCRCCVNpIlR9QM +M1Gg1ZcuUvD85Gmsj9zC9NubD1gLXaXNEGIY61pHXcUddmUdH7pXtXXpx6YMH4bq8Umk9tzJaT xpYGNyyNyPUaF/F6YzsmVJDqFoLPseY/USRaNUsa9a6u8SnpO4Ba8aAP4hDSTzoBplYd/YOZcdD ZUk+bVmPeQhjuI8wPVUNegBqd9hJTlgVkt+LqXC2Lba7PDXMV6/ss9fJPvV13a1A== X-Received: by 2002:a17:907:d27:b0:c16:7414:4c29 with SMTP id a640c23a62f3a-c212a256f7bmr1029455566b.25.1786970581136; Mon, 17 Aug 2026 05:43:01 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:00 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:41 +0100 Subject: [PATCH RFC 1/9] stackdepot: share persistent stack prefixes with trie storage Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-1-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan Stack depot's hash backend deduplicates only identical stored traces. Persistent, non-refcounted users do not evict records, so distinct traces consume full records even when they share long frame sequences. After pool storage is exhausted, a persistent save of a previously unseen trace returns 0. Add a path-compressed trie as a second backend for these records. Store a run of frames in each node, keep children sorted by their first frame, and support insertion by descending through matches, splitting partial matches, promoting an internal node to a terminal node, or attaching a new suffix. Use otherwise invalid pool-index values in the existing 32-bit handle layout to encode dense stack IDs. Map each ID to its terminal node through a sparse side table so fetch can reconstruct the trace by following parent links. Saved stacks and IDs remain stable and are not recycled. Add architecture hooks for compact frame storage. arm64 uses an exactly round-trippable signed 32-bit offset from _text. Native x86-64 stores the low 32 bits when the upper 32 bits are all set. Keep frames raw when compression would not round trip, and provide a generic implementation that always uses raw frames. Allocate trie nodes and child containers from contiguous runs of 16-byte slots in the existing order-2 stack depot pools. Release unpublished reservations immediately. Retire replaced published storage with RCU grace-period cookies and make its slots available to later insertions only after the grace period completes. Share stack_pools and the configured physical pool limit with the hash backend. Mark pools assigned to trie slots unavailable for hash record allocation, so total stack depot capacity remains bounded by the existing pool budget. Bound insertion to three attempts: another writer may consume the cached new_pool after the lockless check, while a maximum-depth insertion can require two newly registered pools. Serialize writers with a raw spinlock and publish topology through RCU. Complete fallible reservations before publishing a stack. Publish side-table mappings before topology exposes their nodes, and replace child containers for non-tail updates. Allow sorted appends to publish into unused tail capacity before increasing the visible child count. Add stack_depot_fetch_into() to materialize either backend in caller-owned storage. Keep stack_depot_fetch() hash-only because its pointer-returning interface requires contiguous depot-owned records. Make stack_depot_print() and stack_depot_snprint() support both backends. Keep STACK_DEPOT_FLAG_GET records on the hash backend. A trie-eligible save that is not allowed to allocate performs a single lockless lookup and returns 0 on a miss. Trie insertion failures do not fall back to hash storage. Live KASAN observations from the complete series yielded directional estimates of 31.5% lower backend-specific storage per record on arm64 and 42.6% lower on x86-64 with trie storage enabled. One collection in each comparison raced, and the machines saw different stack populations. These are approximate observations, not a matched memory comparison. Misses for traces seen only by non-allocating saves are unobservable, so the measurements do not establish equivalent diagnostic coverage. Do not initialize or enable trie storage in this patch. Existing consumers continue to receive hash handles while later patches make their access paths backend-independent, keep them explicitly hash-backed, or reject trie handles. The final patch adds boot-time activation. Signed-off-by: Caleb Kan --- arch/arm64/include/asm/stackdepot.h | 42 ++ arch/um/include/asm/Kbuild | 1 + arch/x86/include/asm/stackdepot.h | 37 + include/asm-generic/Kbuild | 1 + include/asm-generic/stackdepot.h | 19 + include/linux/stackdepot.h | 67 +- lib/stackdepot.c | 1368 +++++++++++++++++++++++++++++++= +++- 7 files changed, 1521 insertions(+), 14 deletions(-) diff --git a/arch/arm64/include/asm/stackdepot.h b/arch/arm64/include/asm/s= tackdepot.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 +#include + +/* + * 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 payloa= d) +{ + long offset; + + offset =3D (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 =3D (u32)(frame - (unsigned long)_text); + if (arch_stack_depot_frame_from_payload(candidate) !=3D frame) + return false; + + *payload =3D candidate; + return true; +} + +static inline void +arch_stack_depot_frame_decompress(u32 payload, unsigned long *frame) +{ + *frame =3D 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 +=3D preempt.h generic-y +=3D ring_buffer.h generic-y +=3D runtime-const.h generic-y +=3D softirq_stack.h +generic-y +=3D stackdepot.h generic-y +=3D switch_to.h generic-y +=3D topology.h generic-y +=3D trace_clock.h diff --git a/arch/x86/include/asm/stackdepot.h b/arch/x86/include/asm/stack= depot.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 + +#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 reconst= ructs + * 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) !=3D + STACK_DEPOT_X86_64_FRAME_PREFIX) + return false; + + *low =3D (u32)frame; + return true; +} + +static inline void +arch_stack_depot_frame_decompress(u32 low, unsigned long *frame) +{ + *frame =3D STACK_DEPOT_X86_64_FRAME_PREFIX | low; +} + +#else +#include +#endif /* CONFIG_X86_64 */ + +#endif /* _ASM_X86_STACKDEPOT_H */ diff --git a/include/asm-generic/Kbuild b/include/asm-generic/Kbuild index 15df9dcb42a5..ac178162fa11 100644 --- a/include/asm-generic/Kbuild +++ b/include/asm-generic/Kbuild @@ -55,6 +55,7 @@ mandatory-y +=3D serial.h mandatory-y +=3D shmparam.h mandatory-y +=3D simd.h mandatory-y +=3D softirq_stack.h +mandatory-y +=3D stackdepot.h mandatory-y +=3D switch_to.h mandatory-y +=3D timex.h mandatory-y +=3D tlbflush.h diff --git a/include/asm-generic/stackdepot.h b/include/asm-generic/stackde= pot.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 + +static inline bool +arch_stack_depot_frame_try_compress(unsigned long frame, u32 *low) +{ + return false; +} + +static inline void +arch_stack_depot_frame_decompress(u32 low, unsigned long *frame) +{ + /* Generic code never compresses frames, so this hook is unreachable. */ +} + +#endif /* __ASM_GENERIC_STACKDEPOT_H */ diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h index 2cc21ffcdaf9..96544fc684a5 100644 --- a/include/linux/stackdepot.h +++ b/include/linux/stackdepot.h @@ -144,6 +144,10 @@ static inline int stack_depot_early_init(void) { retur= n 0; } * Users of this flag must also call stack_depot_put() when keeping the st= ack * trace is no longer required to avoid overflowing the refcount. * + * When trie storage is enabled, persistent non-refcounted saves use trie + * storage. Constrained callers only look up existing stacks; they do not = insert + * a missing stack. Trie failures do not fall back to hash storage. + * * If the provided stack trace comes from the interrupt context, only the = part * up to the interrupt entry is saved. * @@ -152,7 +156,7 @@ static inline int stack_depot_early_init(void) { return= 0; } * this is the case for contexts where neither %GFP_ATOMIC nor * %GFP_NOWAIT can be used (NMI, raw_spin_lock). * - * Return: Handle of the stack struct stored in depot, 0 on failure + * Return: Handle of the stack trace stored in depot, 0 on failure */ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries, unsigned int nr_entries, @@ -169,6 +173,10 @@ depot_stack_handle_t stack_depot_save_flags(unsigned l= ong *entries, * Does not increment the refcount on the saved stack trace; see * stack_depot_save_flags() for more details. * + * When trie storage is enabled, this can return trie-backed handles. Use + * stack_depot_fetch_into(), stack_depot_print(), or stack_depot_snprint()= for + * backend-independent access to the stack contents. + * * Context: Contexts where allocations via alloc_pages() are allowed; * see stack_depot_save_flags() for more details. * @@ -178,7 +186,7 @@ depot_stack_handle_t stack_depot_save(unsigned long *en= tries, unsigned int nr_entries, gfp_t alloc_flags); =20 /** - * __stack_depot_get_stack_record - Get a pointer to a stack_record struct + * __stack_depot_get_stack_record - Get a hash-backed stack record * * @handle: Stack depot handle * @@ -191,14 +199,55 @@ struct stack_record *__stack_depot_get_stack_record(d= epot_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 acces= s to + * stack contents should use stack_depot_fetch_into(), stack_depot_print()= , or + * stack_depot_snprint(). Passing a trie-backed handle is invalid and may = WARN. + * * Return: Number of frames for the fetched stack */ unsigned int stack_depot_fetch(depot_stack_handle_t handle, unsigned long **entries); =20 +/** + * 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 s= kipped + * 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 refe= rence. + * 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 disa= bled, + * or @max_entries is less than the number of stored frames. + */ +unsigned int stack_depot_fetch_into(depot_stack_handle_t handle, + unsigned long *entries, + unsigned int max_entries); + /** * stack_depot_print - Print a stack trace from stack depot * @@ -224,10 +273,14 @@ int stack_depot_snprint(depot_stack_handle_t handle, = char *buf, size_t size, * * @handle: Stack depot handle returned from stack_depot_save() * - * The stack trace is evicted from stack depot once all references to it h= ave - * been dropped (once the number of stack_depot_evict() calls matches the - * number of stack_depot_save_flags() calls with STACK_DEPOT_FLAG_GET set = for - * this stack trace). + * Drop a reference acquired by stack_depot_save_flags() with + * %STACK_DEPOT_FLAG_GET. Calling this for a handle saved without + * %STACK_DEPOT_FLAG_GET is invalid; persistent handles, including trie-ba= cked + * 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 m= atches + * 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); =20 diff --git a/lib/stackdepot.c b/lib/stackdepot.c index dd2717ff94bf..0278b7a013f1 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -2,9 +2,10 @@ /* * Stack depot - a stack trace storage that avoids duplication. * - * Internally, stack depot maintains a hash table of unique stacktraces. T= he - * 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 us= e the + * legacy hash table with contiguous stack records in stack pools. Persist= ent + * non-refcounted entries can use trie storage when enabled; trie nodes sh= are + * common frame prefixes and are published through RCU children containers. * * Author: Alexander Potapenko * Copyright (C) 2016 Google, Inc. @@ -14,10 +15,15 @@ =20 #define pr_fmt(fmt) "stackdepot: " fmt =20 +#include +#include #include +#include #include #include +#include #include +#include #include #include #include @@ -36,9 +42,12 @@ #include #include =20 +#include + /* * The pool_index is offset by 1 so the first record does not have a 0 han= dle. */ +/* Parsed before mm_core_init(); trie handle decoding assumes this is then= fixed. */ static unsigned int stack_max_pools __read_mostly =3D MIN((1LL << DEPOT_POOL_INDEX_BITS) - 1, 8192); =20 @@ -63,18 +72,18 @@ static unsigned int stack_hash_mask; =20 /* 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) =3D DEPOT_POOL_SIZE; /* Freelist of stack records within stack_pools. */ static __guarded_by(&pool_lock) LIST_HEAD(free_stacks); =20 -/* Statistics counters for debugfs. */ +/* Hash-backend statistics counters for debugfs. */ enum depot_counter_id { DEPOT_COUNTER_REFD_ALLOCS, DEPOT_COUNTER_REFD_FREES, @@ -95,6 +104,552 @@ static const char *const counter_names[] =3D { }; static_assert(ARRAY_SIZE(counter_names) =3D=3D DEPOT_COUNTER_COUNT); =20 +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 form= at. + * Architectures may compress some frames to 32-bit payloads; mixed raw and + * compressed input is split across multiple trie nodes so each node has o= ne + * decoding mode. + */ +struct stack_depot_frame_run { + u16 nr_entries; + u8 mode; +}; + +static_assert(CONFIG_STACKDEPOT_MAX_FRAMES <=3D 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 positio= n. + * Existing child pointers are immutable. Writers may publish into unused = tail + * capacity; other updates publish a replacement container. + */ +struct stack_depot_trie_children { + unsigned int nr_children; + unsigned int capacity; + const struct stack_depot_trie_node __rcu *nodes[]; +}; + +/* Retired children carry an optional node through their RCU grace period.= */ +struct stack_depot_trie_retired_children { + struct list_head list; + unsigned long rcu_state; + const struct stack_depot_trie_node *pending_node; + unsigned char data[]; +}; + +static_assert(IS_ALIGNED(offsetof(struct stack_depot_trie_retired_children= , data), + 1UL << DEPOT_STACK_ALIGN)); + +#define STACK_DEPOT_TRIE_SLOT_SIZE BIT(DEPOT_STACK_ALIGN) +#define STACK_DEPOT_TRIE_POOL_SLOTS \ + (DEPOT_POOL_SIZE / STACK_DEPOT_TRIE_SLOT_SIZE) + +struct stack_depot_trie_pool { + struct list_head list; + unsigned int free_slots; + DECLARE_BITMAP(used, STACK_DEPOT_TRIE_POOL_SLOTS); +}; + +#define STACK_DEPOT_TRIE_POOL_FIRST_SLOT \ + DIV_ROUND_UP(sizeof(struct stack_depot_trie_pool), \ + STACK_DEPOT_TRIE_SLOT_SIZE) +#define STACK_DEPOT_TRIE_POOL_USABLE_SIZE \ + ((STACK_DEPOT_TRIE_POOL_SLOTS - STACK_DEPOT_TRIE_POOL_FIRST_SLOT) * \ + STACK_DEPOT_TRIE_SLOT_SIZE) + +static_assert(STACK_DEPOT_TRIE_POOL_FIRST_SLOT < STACK_DEPOT_TRIE_POOL_SLO= TS); + +static DEFINE_STATIC_KEY_FALSE(stack_depot_trie_enabled); +static const struct stack_depot_trie_children __rcu *stack_depot_trie_root; +static DEFINE_RAW_SPINLOCK(stack_depot_trie_writer_lock); + +#define DEPOT_POOL_INDEX_MASK ((1U << DEPOT_POOL_INDEX_BITS) - 1) +#define DEPOT_OFFSET_MASK ((1U << DEPOT_OFFSET_BITS) - 1) + +/* Retired fixed-size slots remain reserved until their RCU grace period e= nds. */ +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 encodin= gs. + * A handle with pool_index_plus_1 in 1..stack_max_pools names a hash-back= ed + * 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 tab= le + * 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 =3D {}; + u64 pool_index_plus_1; + u32 pool_delta; + u32 index; + + index =3D stack_id - 1; + pool_delta =3D index >> DEPOT_OFFSET_BITS; + pool_index_plus_1 =3D (u64)stack_max_pools + 1 + pool_delta; + + parts.pool_index_plus_1 =3D pool_index_plus_1; + parts.offset =3D index & DEPOT_OFFSET_MASK; + return parts.handle; +} + +static inline bool stack_depot_handle_is_trie(depot_stack_handle_t handle) +{ + union handle_parts parts =3D { .handle =3D handle }; + + return parts.pool_index_plus_1 > stack_max_pools; +} + +static u32 trie_stack_id(depot_stack_handle_t handle) +{ + union handle_parts parts =3D { .handle =3D handle }; + u32 pool_delta; + + pool_delta =3D 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 diagnost= ic + * contexts where taking a lock would be unsafe. Additional directories and + * chunks are published lazily as stack IDs grow. + */ +#define STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE \ + (PAGE_SIZE / sizeof(struct stack_depot_trie_node *)) +#define STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE \ + (PAGE_SIZE / sizeof(struct stack_depot_trie_node **)) + +struct stack_depot_trie_side_dir { + /* Both the chunk pointer and each node pointer in it are RCU-published. = */ + const struct stack_depot_trie_node __rcu * __rcu * + chunks[STACK_DEPOT_TRIE_SIDE_TABLE_DIR_SIZE]; +}; + +struct stack_depot_trie_side_root { + unsigned int dir_capacity; + struct stack_depot_trie_side_dir __rcu *dirs[]; +}; + +struct stack_depot_trie_side_prealloc { + /* Preallocated side-table directory page for sparse growth. */ + struct stack_depot_trie_side_dir *dir; + /* Preallocated side-table pointer chunk for sparse growth. */ + const struct stack_depot_trie_node __rcu **chunk; +}; + +static struct stack_depot_trie_side_root *trie_side_table_root; +static DEFINE_RAW_SPINLOCK(trie_side_table_cache_lock); +/* Zeroed unpublished pages; get/put transfer ownership under the cache lo= ck. */ +static struct stack_depot_trie_side_prealloc trie_side_table_cache; +static u32 trie_side_table_last_stack_id; + +/* Lock order: writer_lock -> pool_lock. The cache lock is never nested. */ + +static inline size_t stack_depot_frame_run_entry_bytes(enum stack_depot_fr= ame_mode mode) +{ + if (mode =3D=3D 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 *r= un) +{ + 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 =3D 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 =3D trie_side_table_root; + if (!root_vec || root >=3D root_vec->dir_capacity) + return NULL; + /* Pairs with side-table directory rcu_assign_pointer(). */ + return rcu_dereference_check(root_vec->dirs[root], + lockdep_is_held(&stack_depot_trie_writer_lock) || + rcu_read_lock_sched_held()); +} + +static inline const struct stack_depot_trie_node __rcu ** +trie_side_table_dir_load_chunk(struct stack_depot_trie_side_dir *dir, + unsigned int idx) +{ + /* Pairs with the chunk rcu_assign_pointer() in stack ID preparation. */ + return rcu_dereference_check(dir->chunks[idx], + lockdep_is_held(&stack_depot_trie_writer_lock) || + rcu_read_lock_sched_held()); +} + +static u32 +trie_side_table_prepare_stack_slot(struct stack_depot_trie_side_prealloc *= prealloc) +{ + const struct stack_depot_trie_node __rcu **chunk; + struct stack_depot_trie_side_dir *dir; + struct stack_depot_trie_side_root *root_vec; + unsigned int root; + unsigned int idx; + u32 id; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + + id =3D trie_side_table_last_stack_id + 1; + if (id > trie_max_stack_id()) + return 0; + + root_vec =3D trie_side_table_root; + root =3D trie_side_table_root_index(id); + dir =3D trie_side_table_load_dir(root); + if (!dir) { + dir =3D prealloc->dir; + prealloc->dir =3D NULL; + /* Publish the zeroed directory before readers can load it locklessly. */ + rcu_assign_pointer(root_vec->dirs[root], dir); + } + + idx =3D trie_side_table_dir_index(id); + chunk =3D trie_side_table_dir_load_chunk(dir, idx); + if (!chunk) { + chunk =3D prealloc->chunk; + prealloc->chunk =3D NULL; + rcu_assign_pointer(dir->chunks[idx], chunk); + } + + return id; +} + +static int trie_side_table_get_prealloc(gfp_t gfp_flags, + struct stack_depot_trie_side_prealloc *prealloc) +{ + unsigned long flags; + + gfp_flags =3D gfp_nested_mask(gfp_flags); + raw_spin_lock_irqsave(&trie_side_table_cache_lock, flags); + prealloc->dir =3D trie_side_table_cache.dir; + prealloc->chunk =3D trie_side_table_cache.chunk; + trie_side_table_cache.dir =3D NULL; + trie_side_table_cache.chunk =3D NULL; + raw_spin_unlock_irqrestore(&trie_side_table_cache_lock, flags); + + if (!prealloc->dir) { + prealloc->dir =3D (void *)get_zeroed_page(gfp_flags); + if (!prealloc->dir) + return -ENOMEM; + } + if (!prealloc->chunk) { + prealloc->chunk =3D (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_prea= lloc *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 =3D prealloc->dir; + prealloc->dir =3D NULL; + } + if (!trie_side_table_cache.chunk) { + trie_side_table_cache.chunk =3D prealloc->chunk; + prealloc->chunk =3D 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 =3D trie_side_table_root_index(id); + dir =3D trie_side_table_load_dir(root); + if (!dir) + return NULL; + chunk =3D trie_side_table_dir_load_chunk(dir, trie_side_table_dir_index(i= d)); + if (!chunk) + return NULL; + + /* Pairs with side-table node publication. */ + return rcu_dereference_check(chunk[trie_side_table_slot_index(id)], + lockdep_is_held(&stack_depot_trie_writer_lock) || + rcu_read_lock_sched_held()); +} + +static inline struct stack_depot_trie_retired_children * +trie_retired_children(const void *ptr) +{ + return container_of(ptr, struct stack_depot_trie_retired_children, data); +} + +static bool depot_init_pool(void **prealloc); + +static unsigned int trie_pool_reserve_slots(struct stack_depot_trie_pool *= pool, + unsigned int nr_slots) +{ + unsigned int run =3D 0; + unsigned int i; + unsigned int slot; + + if (pool->free_slots < nr_slots) + return STACK_DEPOT_TRIE_POOL_SLOTS; + + /* A free run can cross any previous allocation position. */ + for (slot =3D STACK_DEPOT_TRIE_POOL_FIRST_SLOT; + slot < STACK_DEPOT_TRIE_POOL_SLOTS; slot++) { + if (pool->used[slot / BITS_PER_LONG] & + BIT(slot % BITS_PER_LONG)) { + run =3D 0; + continue; + } + if (++run !=3D nr_slots) + continue; + + for (i =3D slot + 1 - nr_slots; i <=3D slot; i++) + pool->used[i / BITS_PER_LONG] |=3D BIT(i % BITS_PER_LONG); + pool->free_slots -=3D nr_slots; + return slot + 1 - nr_slots; + } + + return STACK_DEPOT_TRIE_POOL_SLOTS; +} + +/* Allocate at least @size bytes from one contiguous trie-pool slot run. */ +static void *trie_pool_alloc(size_t size, void **prealloc) +{ + struct stack_depot_trie_pool *pool; + unsigned int nr_slots; + unsigned int slot; + + lockdep_assert_held(&pool_lock); + + if (size > STACK_DEPOT_TRIE_POOL_USABLE_SIZE) + return NULL; + nr_slots =3D DIV_ROUND_UP(size, STACK_DEPOT_TRIE_SLOT_SIZE); + list_for_each_entry_reverse(pool, &stack_depot_trie_pools, list) { + slot =3D trie_pool_reserve_slots(pool, nr_slots); + if (slot !=3D STACK_DEPOT_TRIE_POOL_SLOTS) + return (char *)pool + slot * STACK_DEPOT_TRIE_SLOT_SIZE; + } + + if (!depot_init_pool(prealloc)) + return NULL; + pool =3D stack_pools[pools_num - 1]; + /* Keep hash records out of this bitmap-owned pool. */ + pool_offset =3D DEPOT_POOL_SIZE; + memset(pool, 0, sizeof(*pool)); + pool->free_slots =3D STACK_DEPOT_TRIE_POOL_SLOTS - + STACK_DEPOT_TRIE_POOL_FIRST_SLOT; + list_add_tail(&pool->list, &stack_depot_trie_pools); + + slot =3D 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 =3D page_to_pfn(virt_to_page(ptr)); + pfn &=3D ~(BIT(DEPOT_POOL_ORDER) - 1); + pool =3D page_address(pfn_to_page(pfn)); + slot =3D ((unsigned long)ptr - (unsigned long)pool) >> DEPOT_STACK_ALIGN; + nr_slots =3D DIV_ROUND_UP(size, STACK_DEPOT_TRIE_SLOT_SIZE); + for (i =3D slot; i < slot + nr_slots; i++) + pool->used[i / BITS_PER_LONG] &=3D ~BIT(i % BITS_PER_LONG); + pool->free_slots +=3D 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 metadat= a. */ + retired =3D trie_pool_alloc(trie_children_alloc_size(capacity), prealloc); + if (!retired) + return NULL; + + children =3D (void *)retired->data; + children->nr_children =3D 0; + children->capacity =3D capacity; + return children; +} + +static void +trie_pool_release_children(const struct stack_depot_trie_children *childre= n) +{ + /* 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 s= ame + * 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 =3D (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 *c= hildren) +{ + struct stack_depot_trie_retired_children *retired; + + lockdep_assert_held(&pool_lock); + + retired =3D trie_retired_children(children); + retired->pending_node =3D NULL; + retired->rcu_state =3D 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 *chi= ldren, + const struct stack_depot_trie_node *node) +{ + struct stack_depot_trie_retired_children *retired; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + raw_spin_lock(&pool_lock); + trie_retire_children(children); + retired =3D trie_retired_children(children); + retired->pending_node =3D node; + raw_spin_unlock(&pool_lock); +} + +static const struct stack_depot_trie_node * +stack_depot_trie_lookup(const unsigned long *entries, unsigned int nr_entr= ies); + +static depot_stack_handle_t +trie_find_handle(const unsigned long *entries, unsigned int nr_entries) +{ + depot_stack_handle_t handle =3D 0; + const struct stack_depot_trie_node *node; + + rcu_read_lock_sched_notrace(); + node =3D stack_depot_trie_lookup(entries, nr_entries); + if (node) + handle =3D 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 ca= nnot + * 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 p= arent + * links may change meanwhile. + */ +static void trie_side_table_publish(const struct stack_depot_trie_node *no= de) +{ + const struct stack_depot_trie_node __rcu **chunk; + struct stack_depot_trie_side_dir *dir; + u32 stack_id =3D node->stack_id; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + + dir =3D trie_side_table_load_dir(trie_side_table_root_index(stack_id)); + chunk =3D trie_side_table_dir_load_chunk(dir, + trie_side_table_dir_index(stack_id)); + /* Pairs with trie_side_table_lookup(). */ + rcu_assign_pointer(chunk[trie_side_table_slot_index(stack_id)], node); +} + static int __init disable_stack_depot(char *str) { return kstrtobool(str, &stack_depot_disabled); @@ -323,7 +878,7 @@ static bool depot_init_pool(void **prealloc) * NULL; do not reset to NULL if we have reached the maximum number of * pools. */ - if (pools_num < stack_max_pools) + if (pools_num + 1 < stack_max_pools) WRITE_ONCE(new_pool, NULL); else WRITE_ONCE(new_pool, STACK_DEPOT_POISON); @@ -638,6 +1193,63 @@ static inline struct stack_record *find_stack(struct = list_head *bucket, return ret; } =20 +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 =3D 0; attempt < 3; attempt++) { + struct stack_depot_trie_side_prealloc side_prealloc =3D {}; + void *pool_prealloc =3D NULL; + depot_stack_handle_t handle; + unsigned long flags; + struct page *page; + u32 stack_id =3D 0; + + handle =3D 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 =3D alloc_pages(gfp_nested_mask(alloc_flags), + DEPOT_POOL_ORDER); + if (page) + pool_prealloc =3D page_address(page); + } + + raw_spin_lock_irqsave(&stack_depot_trie_writer_lock, flags); + stack_id =3D stack_depot_trie_insert(entries, nr_entries, + &pool_prealloc, &side_prealloc); + raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags); + + if (pool_prealloc) { + raw_spin_lock_irqsave(&pool_lock, flags); + depot_keep_new_pool(&pool_prealloc); + raw_spin_unlock_irqrestore(&pool_lock, flags); + } + if (pool_prealloc) + free_pages((unsigned long)pool_prealloc, DEPOT_POOL_ORDER); + trie_side_table_put_prealloc(&side_prealloc); + if (stack_id) + return trie_handle(stack_id); + } + + return 0; +} + depot_stack_handle_t stack_depot_save_flags(unsigned long *entries, unsigned int nr_entries, gfp_t alloc_flags, @@ -669,6 +1281,17 @@ depot_stack_handle_t stack_depot_save_flags(unsigned = long *entries, if (unlikely(nr_entries =3D=3D 0) || stack_depot_disabled) return 0; =20 + if (!(depot_flags & STACK_DEPOT_FLAG_GET) && + static_branch_unlikely(&stack_depot_trie_enabled)) { + if (nr_entries > CONFIG_STACKDEPOT_MAX_FRAMES) + nr_entries =3D CONFIG_STACKDEPOT_MAX_FRAMES; + if (in_nmi() || !can_alloc) { + WARN_ON_ONCE(can_alloc); + return trie_find_handle(entries, nr_entries); + } + return stack_depot_trie_save(entries, nr_entries, alloc_flags); + } + hash =3D hash_stack(entries, nr_entries); bucket =3D &stack_table[hash & stack_hash_mask]; =20 @@ -753,10 +1376,689 @@ struct stack_record *__stack_depot_get_stack_record= (depot_stack_handle_t handle) { if (!handle) return NULL; + if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle))) + return NULL; =20 return depot_fetch_stack(handle); } =20 +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 =3D arch_stack_depot_frame_try_compress(entries[0], &payload); + for (i =3D 1; i < nr_entries; i++) { + bool next; + + next =3D arch_stack_depot_frame_try_compress(entries[i], &payload); + if (next !=3D compressed) + break; + } + + /* @i is the first non-matching frame, or @nr_entries if all matched. */ + run->mode =3D compressed ? STACK_DEPOT_FRAME_COMPRESSED : STACK_DEPOT_FRA= ME_RAW; + run->nr_entries =3D 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 =3D=3D 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 =3D=3D STACK_DEPOT_FRAME_COMPRESSED) { + unsigned int i; + + for (i =3D 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 =3D stack_id; + node->run =3D *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 =3D src_node->run; + run.nr_entries =3D nr_entries; + + entry_bytes =3D 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 =3D stack_id; + node->run =3D run; +} + +static unsigned int trie_node_match(const struct stack_depot_trie_node *no= de, + const unsigned long *entries, + unsigned int nr_entries) +{ + unsigned int limit; + unsigned int i; + + limit =3D min(node->run.nr_entries, nr_entries); + if (node->run.mode =3D=3D STACK_DEPOT_FRAME_RAW) { + for (i =3D 0; i < limit; i++) { + unsigned long frame; + + memcpy(&frame, node->data + i * sizeof(frame), sizeof(frame)); + if (frame !=3D entries[i]) + break; + } + + return i; + } + + for (i =3D 0; i < limit; i++) { + unsigned long frame; + + stack_depot_trie_node_frame(node, i, &frame); + if (frame !=3D 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 *s= lot) +{ + 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 *childr= en, + unsigned long frame, unsigned int *pos) +{ + unsigned int left =3D 0; + unsigned int right; + + right =3D READ_ONCE(children->nr_children); + while (left < right) { + unsigned int mid =3D left + (right - left) / 2; + const struct stack_depot_trie_node *node; + unsigned long mid_frame; + + node =3D trie_children_load_child(children, mid); + if (!node) { + /* Tail append may produce a transient lockless lookup miss. */ + right =3D mid; + continue; + } + stack_depot_trie_node_frame(node, 0, &mid_frame); + if (mid_frame < frame) { + left =3D mid + 1; + } else if (mid_frame > frame) { + right =3D mid; + } else { + *pos =3D mid; + return true; + } + } + + *pos =3D 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 =3D old->nr_children; + unsigned int i; + + new->nr_children =3D nr_old; + for (i =3D 0; i < nr_old; i++) + RCU_INIT_POINTER(new->nodes[i], trie_children_load_child(old, i)); + for (i =3D nr_old; i < new->capacity; i++) + RCU_INIT_POINTER(new->nodes[i], NULL); +} + +static void trie_children_insert(struct stack_depot_trie_children *childre= n, + const struct stack_depot_trie_node *node, + unsigned int pos) +{ + unsigned int i; + + for (i =3D 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 =3D 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 f= reed + * 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 =3D 0; i < children->nr_children; i++) { + struct stack_depot_trie_node *child; + + child =3D (struct stack_depot_trie_node *)trie_children_load_child(child= ren, i); + rcu_assign_pointer(child->parent, parent); + } +} + +/* + * Split entries into runs, allocate and initialize each node once, and li= nk + * 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 =3D NULL; + const struct stack_depot_trie_node *path_root =3D NULL; + const struct stack_depot_trie_node *last_node =3D parent; + unsigned int entry =3D 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 =3D trie_pool_alloc(trie_node_bytes(&run), pool_prealloc); + if (!node) + goto err_release; + + trie_node_init(node, last_node, + entry + run.nr_entries =3D=3D nr_entries ? stack_id : 0, + &entries[entry], &run); + entry +=3D run.nr_entries; + last_node =3D node; + if (!path_root) + path_root =3D node; + + if (path_children) + trie_children_insert(path_children, last_node, 0); + if (entry < nr_entries) { + path_children =3D trie_pool_alloc_children(1, pool_prealloc); + if (!path_children) + goto err_release; + RCU_INIT_POINTER(node->children, path_children); + } + } + + *node_out =3D last_node; + return path_root; + +err_release: + while (last_node !=3D parent) { + const struct stack_depot_trie_children *node_children; + const struct stack_depot_trie_node *node =3D last_node; + + last_node =3D trie_load_parent(node); + node_children =3D 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_entr= ies) +{ + const struct stack_depot_trie_children *children; + unsigned int entry =3D 0; + + children =3D trie_load_children(&stack_depot_trie_root); + + while (entry < nr_entries) { + const struct stack_depot_trie_node *node; + unsigned int remaining =3D 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 =3D trie_children_load_child(children, pos); + matched =3D trie_node_match(node, &entries[entry], remaining); + if (matched < node->run.nr_entries) + return NULL; + entry +=3D matched; + if (entry =3D=3D nr_entries) + return node->stack_id ? node : NULL; + + children =3D 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 =3D NULL; + const struct stack_depot_trie_node *path_root; + const struct stack_depot_trie_node *node; + unsigned int capacity =3D 1; + u32 new_stack_id; + bool tail_append =3D false; + + /* + * Reuse spare capacity only for a sorted tail append. Other insertions + * replace the children container without modifying visible pointers. + */ + if (children) { + capacity =3D roundup_pow_of_two(children->nr_children + 1); + tail_append =3D pos =3D=3D 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 =3D trie_side_table_prepare_stack_slot(side_prealloc); + if (!new_stack_id) + return 0; + + raw_spin_lock(&pool_lock); + printk_deferred_enter(); + trie_drain_pending_children(); + + /* Reserve replacement topology before the path, the final fallible step.= */ + if (!tail_append) { + new_children =3D trie_pool_alloc_children(capacity, pool_prealloc); + if (!new_children) + goto err_release; + } + path_root =3D 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 =3D + (struct stack_depot_trie_children *)children; + + /* + * Publish the node before the visible count. Readers may transiently + * see NULL and miss; the writer-lock recheck prevents duplicates. + */ + rcu_assign_pointer(tail_children->nodes[pos], path_root); + WRITE_ONCE(tail_children->nr_children, pos + 1); + } else { + if (children) + trie_children_init(children, new_children); + trie_children_insert(new_children, path_root, pos); + rcu_assign_pointer(*slot, new_children); + if (children) + trie_retire_children(children); + } + + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + return new_stack_id; + +err_release: + if (new_children) + trie_pool_release_children(new_children); + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + return 0; +} + +static u32 +trie_split_child(const struct stack_depot_trie_children __rcu **slot, + const struct stack_depot_trie_children *children, + const struct stack_depot_trie_node *child, + unsigned int pos, unsigned int matched, + const unsigned long *entries, unsigned int nr_entries, + void **pool_prealloc, + struct stack_depot_trie_side_prealloc *side_prealloc) +{ + struct stack_depot_trie_children *prefix_children =3D NULL; + struct stack_depot_trie_children *new_children =3D 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 =3D NULL; + struct stack_depot_trie_node *old_suffix =3D 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 =3D 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 =3D child->run; + run.nr_entries =3D matched; + split_prefix_size =3D trie_node_bytes(&run); + old_suffix_len =3D child->run.nr_entries - matched; + run.nr_entries =3D old_suffix_len; + old_suffix_size =3D trie_node_bytes(&run); + has_new_suffix =3D matched < nr_entries; + nr_suffix_roots =3D has_new_suffix ? 2 : 1; + + raw_spin_lock(&pool_lock); + printk_deferred_enter(); + trie_drain_pending_children(); + + /* Reserve fixed split topology before the optional new suffix path. */ + split_prefix =3D trie_pool_alloc(split_prefix_size, pool_prealloc); + if (!split_prefix) + goto err_release; + old_suffix =3D trie_pool_alloc(old_suffix_size, pool_prealloc); + if (!old_suffix) + goto err_release; + new_children =3D trie_pool_alloc_children(children->capacity, pool_preall= oc); + if (!new_children) + goto err_release; + prefix_children =3D trie_pool_alloc_children(nr_suffix_roots, pool_preall= oc); + 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 =3D 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] =3D old_suffix; + suffix_roots[1] =3D new_suffix; + } else { + suffix_roots[0] =3D new_suffix; + suffix_roots[1] =3D old_suffix; + } + } else { + new_node =3D split_prefix; + suffix_roots[0] =3D old_suffix; + } + + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + + /* Rebuild the old path as prefix -> old suffix and attach suffix roots. = */ + trie_node_init_slice(split_prefix, trie_load_parent(child), + has_new_suffix ? 0 : new_stack_id, child, 0, matched); + trie_node_init_slice(old_suffix, split_prefix, child->stack_id, child, + matched, old_suffix_len); + for (i =3D 0; i < nr_suffix_roots; i++) + trie_children_insert(prefix_children, suffix_roots[i], i); + RCU_INIT_POINTER(old_suffix->children, + trie_load_children(&child->children)); + RCU_INIT_POINTER(split_prefix->children, prefix_children); + + /* Publish IDs, reparent descendants, then replace and retire topology. */ + if (child->stack_id) + trie_side_table_publish(old_suffix); + trie_side_table_publish(new_node); + /* Old and replacement chains contain identical frames during transition.= */ + trie_children_init(children, new_children); + RCU_INIT_POINTER(new_children->nodes[pos], split_prefix); + trie_reparent_children(old_suffix); + rcu_assign_pointer(*slot, new_children); + trie_retire_children_with_node(children, child); + + return new_stack_id; + +err_release: + if (split_prefix) + trie_pool_release(split_prefix, split_prefix_size); + if (old_suffix) + trie_pool_release(old_suffix, old_suffix_size); + if (prefix_children) + trie_pool_release_children(prefix_children); + if (new_children) + trie_pool_release_children(new_children); + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + return 0; +} + +static u32 +trie_promote_child(const struct stack_depot_trie_children __rcu **slot, + const struct stack_depot_trie_children *children, + const struct stack_depot_trie_node *child, + unsigned int pos, void **pool_prealloc, + struct stack_depot_trie_side_prealloc *side_prealloc) +{ + struct stack_depot_trie_children *new_children; + struct stack_depot_trie_node *promoted_node; + size_t node_size; + u32 new_stack_id; + + new_stack_id =3D trie_side_table_prepare_stack_slot(side_prealloc); + if (!new_stack_id) + return 0; + node_size =3D trie_node_bytes(&child->run); + + /* Reserve a clone and replacement children container before publication.= */ + raw_spin_lock(&pool_lock); + printk_deferred_enter(); + trie_drain_pending_children(); + promoted_node =3D trie_pool_alloc(node_size, pool_prealloc); + if (!promoted_node) + goto out_unlock; + new_children =3D trie_pool_alloc_children(children->capacity, pool_preall= oc); + if (!new_children) + goto out_release_node; + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + + /* Add the stack ID through a clone, then reparent before retirement. */ + memcpy(promoted_node, child, node_size); + promoted_node->stack_id =3D new_stack_id; + trie_side_table_publish(promoted_node); + trie_children_init(children, new_children); + RCU_INIT_POINTER(new_children->nodes[pos], promoted_node); + trie_reparent_children(promoted_node); + rcu_assign_pointer(*slot, new_children); + trie_retire_children_with_node(children, child); + + return new_stack_id; + +out_release_node: + trie_pool_release(promoted_node, node_size); +out_unlock: + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + return 0; +} + +static u32 +stack_depot_trie_insert(const unsigned long *entries, + unsigned int nr_entries, void **pool_prealloc, + struct stack_depot_trie_side_prealloc *side_prealloc) +{ + const struct stack_depot_trie_children *children; + const struct stack_depot_trie_children __rcu **slot =3D + &stack_depot_trie_root; + const struct stack_depot_trie_node *child; + struct stack_depot_trie_node *parent =3D NULL; + unsigned int matched; + unsigned int pos; + u32 stack_id; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + + for (;;) { + pos =3D 0; + children =3D trie_load_children(slot); + /* No matching child: attach the remaining path. */ + if (!children || + !trie_children_find_position(children, entries[0], &pos)) { + stack_id =3D trie_insert_path(slot, parent, children, pos, + entries, nr_entries, pool_prealloc, + side_prealloc); + break; + } + + child =3D trie_children_load_child(children, pos); + matched =3D trie_node_match(child, entries, nr_entries); + /* A partial child match requires a prefix/suffix split. */ + if (matched < child->run.nr_entries) { + stack_id =3D 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 =3D=3D nr_entries) { + if (child->stack_id) + return child->stack_id; + stack_id =3D trie_promote_child(slot, children, child, pos, + pool_prealloc, side_prealloc); + break; + } + + /* The child matched completely; continue with the remaining frames. */ + parent =3D (struct stack_depot_trie_node *)child; + slot =3D &parent->children; + entries +=3D matched; + nr_entries -=3D matched; + } + + if (stack_id) + trie_side_table_last_stack_id =3D stack_id; + return stack_id; +} + +static unsigned int trie_fetch_into(const struct stack_depot_trie_node *no= de, + unsigned long *entries, + unsigned int max_entries) +{ + const struct stack_depot_trie_node *cur; + unsigned int total; + unsigned int pos; + unsigned int i; + + total =3D 0; + for (cur =3D node; cur; cur =3D trie_load_parent(cur)) + total +=3D cur->run.nr_entries; + if (max_entries < total) + return 0; + + pos =3D total; + for (cur =3D node; cur; cur =3D trie_load_parent(cur)) { + pos -=3D cur->run.nr_entries; + for (i =3D 0; i < cur->run.nr_entries; i++) + stack_depot_trie_node_frame(cur, i, &entries[pos + i]); + } + + return total; +} + +static unsigned int trie_fetch_handle_into(depot_stack_handle_t handle, + unsigned long *entries, + unsigned int max_entries) +{ + const struct stack_depot_trie_node *node; + u32 stack_id; + unsigned int nr_entries; + + stack_id =3D trie_stack_id(handle); + rcu_read_lock_sched_notrace(); + node =3D 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 =3D trie_fetch_into(node, entries, max_entries); + rcu_read_unlock_sched_notrace(); + if (nr_entries) + kmsan_unpoison_memory(entries, nr_entries * sizeof(*entries)); + + return nr_entries; +} + unsigned int stack_depot_fetch(depot_stack_handle_t handle, unsigned long **entries) { @@ -771,6 +2073,8 @@ unsigned int stack_depot_fetch(depot_stack_handle_t ha= ndle, =20 if (!handle || stack_depot_disabled) return 0; + if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle))) + return 0; =20 stack =3D depot_fetch_stack(handle); /* @@ -785,12 +2089,44 @@ unsigned int stack_depot_fetch(depot_stack_handle_t = handle, } EXPORT_SYMBOL_GPL(stack_depot_fetch); =20 +unsigned int stack_depot_fetch_into(depot_stack_handle_t handle, + unsigned long *entries, + unsigned int max_entries) +{ + struct stack_record *stack; + unsigned int nr_entries; + + if (!handle) + return 0; + if (stack_depot_disabled) + return 0; + WARN_ON_ONCE(!entries || !max_entries); + if (stack_depot_handle_is_trie(handle)) + return trie_fetch_handle_into(handle, entries, max_entries); + + stack =3D depot_fetch_stack(handle); + if (!stack) + return 0; + nr_entries =3D 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; =20 if (!handle || stack_depot_disabled) return; + if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle))) + return; =20 stack =3D depot_fetch_stack(handle); /* @@ -810,6 +2146,15 @@ void stack_depot_print(depot_stack_handle_t stack) unsigned long *entries; unsigned int nr_entries; =20 + if (stack_depot_handle_is_trie(stack)) { + unsigned long trie_entries[CONFIG_STACKDEPOT_MAX_FRAMES]; + + nr_entries =3D trie_fetch_handle_into(stack, trie_entries, + ARRAY_SIZE(trie_entries)); + stack_trace_print(trie_entries, nr_entries, 0); + return; + } + nr_entries =3D stack_depot_fetch(stack, &entries); if (nr_entries > 0) stack_trace_print(entries, nr_entries, 0); @@ -822,6 +2167,15 @@ int stack_depot_snprint(depot_stack_handle_t handle, = char *buf, size_t size, unsigned long *entries; unsigned int nr_entries; =20 + if (stack_depot_handle_is_trie(handle)) { + unsigned long trie_entries[CONFIG_STACKDEPOT_MAX_FRAMES]; + + nr_entries =3D trie_fetch_handle_into(handle, trie_entries, + ARRAY_SIZE(trie_entries)); + return stack_trace_snprint(buf, size, trie_entries, nr_entries, + spaces); + } + nr_entries =3D stack_depot_fetch(handle, &entries); return nr_entries ? stack_trace_snprint(buf, size, entries, nr_entries, spaces) : 0; --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f41.google.com (mail-ej1-f41.google.com [209.85.218.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CD8E041D210 for ; Mon, 17 Aug 2026 12:43:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970586; cv=none; b=DTPt9VMxIx/RQeJhxRutlfnInOUTSgnnftAMO8/b7WdeKDfkQ7qXn17bV430UQ21oDlQYO0TlL/3a/R5VY3om07k0SNXJHbp7PrVPv+aONhs9eA03c9v754EyMvoTPWxYctN//ryQDvQA+Wj0VgE+XibdJNue2BliglUTu6E23I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970586; c=relaxed/simple; bh=WC0iJXT5f8RhSTAZmCV74WvXaWHzLl69Q9rBvDZ3MNk=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=EuI87/do4bn15O/zgsLCpmT3oDteYa1ymwmnMPcGEIOKlwox1WsjcX/G/9J9bYm0xs0shtUDgTlKOWRwhMopBYb5epbD+LWgTjlnw5C+YG3NqYVlwPKTftgar77U46Bxibivr5MARQapeaM1Np4gQK2QtEHEU3RHBE4/FssXLvI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=cTwhhudQ; arc=none smtp.client-ip=209.85.218.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="cTwhhudQ" Received: by mail-ej1-f41.google.com with SMTP id a640c23a62f3a-c2074710751so525426766b.1 for ; Mon, 17 Aug 2026 05:43:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970582; x=1787575382; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=gfHHmTAX9KFDfSupTJahIh3zGovtGMOsbiiwMzb7abo=; b=cTwhhudQjvgkFOmcuSwDlT19beJ8z3mcMbARzIbFXfEW1Qn4a5bORjUS5GvKCOu45Y 1BeHPpBvVvNJUcl+j9cHU0MJ1GI6NJ2Oj46eATYm06D33ldmKOEuHHolZn1KN/VM+bWF zyHsQS7QxB7jzbPZEJT6DP5MKPMj9jiePZEniMbiCNVUju6du5D2IuySnfB5ARBDOQGz LZUP067U5+W6vhJNqpwFxHds2Jcbm1HHjJJCxjM+6ouFTq8wbAhe9jUlaQWYIcS2ylDR 9ZlhRfzaWHC01DWp2gUkJUvbZWoh8O1dUTrNydi+W/aYzIb+rL5Fq79Anz0Xt/ZCWPX4 IprA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970582; x=1787575382; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=gfHHmTAX9KFDfSupTJahIh3zGovtGMOsbiiwMzb7abo=; b=QGbaybwyJ11uQ+WcwQuskkrZGGAZzRwb86cbfV6ysS85WXYVPRiwXbBOQHf/FOfYKJ xQIH43fxDAYDxDopyi5X4Zmjpp53XIZnlPVI9u8sNuoZt35kcIjgtMy96WSCe79AOakz oglIHF1ORaiTfyArqeWORCv/p8EzTaupj0qIlUXhSALouzsrl8uuTQXIqhVQti72xsSo HjryHtPAMzTIZaaTcZVvQ0az7228UNXIzOvHbsBeMQKOpQ1eCN/rcuaEP6jNITt2g0iX edLd6GYCVFhruA/rzeIqwm+j8rO6G+83ZGWo9/ZdeETug4ixqHtBzglDIdKJShQo41hh SecA== X-Forwarded-Encrypted: i=1; AHgh+RoJDYodJk5z8htCx3uLBh6qICQ1BUQS1cFkJuzT+IGxwuWGMhDXJOAqmPBY2c1hlm1B1Wyl6Qxlr9FbxIM=@vger.kernel.org X-Gm-Message-State: AOJu0YzEJg4rS97NHp7KnHzBPt7R2Gkl1XJGgbheLtu8/z0gunUpbnGA mbx3eZbviJ20RVVVYq8vMnFTnWRRT1NzAcOhPKvA7G5gp5Lj2OY8Q09y X-Gm-Gg: AR+sD13zPFS1jWQMMfEfTYJA9lb7RRVOXLphj5dOA1cxqgan+GamzXAAUASNGWD0hRt Etuu0AkT/O1S0zhq5i7k7H3B+fcWwwaQ7GaRnZ0LWg0rvsqBG2kBEAHUmoyIYttvzXZahIgxNUy jeTex3Zv1V0Wbe7MGsiAMSfEqAxt7w+nACKE3poDsU/fYXJHUVb5WMjjWwdGSTR7tsUMgTZIW9S oPVqaQE3zcBKd2R6nUboMVm97UdMPYLHGc7F6Bs3KoMf+KiiwvZ3DQkdrlssvf3amdAoRDmpPmD uyd41yNzNsd/4cIadFmMwMeaKIZm/D5pNgG3COEriXgD3Ps4Y6iP8xFfF5wchvLbVBy8BCNn8/h mynstgr4EHCPN4t9j4QRODjDQzG0ab4LwDc26kbvU7ZlukDNZOL4VzWv9SkdjAy3MVcFA0yJa86 pOBxyIO9ELJs9pTm/H7GsVzCrxPCcW7RZJcVYUmfR9p5ev/Jd49Q== X-Received: by 2002:a17:906:4fc8:b0:c16:66dc:3ab7 with SMTP id a640c23a62f3a-c2129b5b0c3mr1072891266b.10.1786970581919; Mon, 17 Aug 2026 05:43:01 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:01 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:42 +0100 Subject: [PATCH RFC 2/9] stackdepot: add KUnit tests for trie storage Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-2-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan Trie insertion mutates shared topology, but handles returned before later splits, promotions, and child-array replacements must continue to fetch and deduplicate the same traces. Add a built-in KUnit suite for stack depot's public APIs and trie internals. The backend-neutral cases run immediately against hash storage. Once the final patch makes trie activation reachable, the same cases also exercise trie storage. Cover save and deduplication behavior, maximum-depth and overlong stacks, allocation-constrained hits and misses, GET records, extra bits, caller-owned fetching, short destinations, and formatted output. Exercise append, descent, split, promotion, child-array growth, and tail append paths. Also cover lockless duplicate lookups while verifying that earlier handles still materialize and deduplicate after later mutations. Add mixed compressed and raw frame round trips together with generic, arm64, and native x86-64 codec coverage. Keep fixtures portable to 32-bit architectures, skip the native x86 codec case on UML, and require at least three configured frames for the topology fixtures. On 4 KiB arm64 and native x86-64 builds configured for 256 frames, an alternating compressed/raw maximum-depth trace creates one node per frame and exercises a two-pool insertion and its bounded retry path. Build the suite into the kernel because it exercises non-exported stack depot helpers. Skip trie-specific cases unless stackdepot_kunit.trie_pool_limit matches the stack_depot_max_pools value used at boot. On the complete series, run them with stackdepot.trie_enabled=3D1 and matching values for both parameters; this prevents optional initialization failure from silently exercising hash storage. Signed-off-by: Caleb Kan --- lib/Kconfig.debug | 17 ++ lib/tests/Makefile | 1 + lib/tests/stackdepot_kunit.c | 418 +++++++++++++++++++++++++++++++++++++++= ++++ 3 files changed, 436 insertions(+) diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 00921b1676e8..af238949fb7a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2771,6 +2771,23 @@ config RESOURCE_KUNIT_TEST =20 If unsure, say N. =20 +config STACKDEPOT_KUNIT_TEST + bool "KUnit test for stack depot" if !KUNIT_ALL_TESTS + depends on KUNIT=3Dy && STACKDEPOT + depends on STACKDEPOT_MAX_FRAMES >=3D 3 + default KUNIT_ALL_TESTS + help + Enable this option to test stack depot API behavior at boot. + This test is built in because it exercises internal, non-exported + stack depot helpers, so KUNIT must also be built in. + + KUnit tests run during boot and output the results to the debug log + in TAP format (https://testanything.org/). Only useful for kernel + developers running the KUnit test harness, and not intended for + inclusion into a production build. + + If unsure, say N. + config SYSCTL_KUNIT_TEST tristate "KUnit test for sysctl" if !KUNIT_ALL_TESTS depends on KUNIT diff --git a/lib/tests/Makefile b/lib/tests/Makefile index 4ead57602eac..2d40bd21a8ef 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -49,6 +49,7 @@ obj-$(CONFIG_SCANF_KUNIT_TEST) +=3D scanf_kunit.o obj-$(CONFIG_SEQ_BUF_KUNIT_TEST) +=3D seq_buf_kunit.o obj-$(CONFIG_SIPHASH_KUNIT_TEST) +=3D siphash_kunit.o obj-$(CONFIG_SLUB_KUNIT_TEST) +=3D slub_kunit.o +obj-$(CONFIG_STACKDEPOT_KUNIT_TEST) +=3D stackdepot_kunit.o obj-$(CONFIG_TEST_SORT) +=3D test_sort.o CFLAGS_stackinit_kunit.o +=3D $(call cc-disable-warning, switch-unreachabl= e) obj-$(CONFIG_STACKINIT_KUNIT_TEST) +=3D stackinit_kunit.o diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c new file mode 100644 index 000000000000..75fa16268c0b --- /dev/null +++ b/lib/tests/stackdepot_kunit.c @@ -0,0 +1,418 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +static int expected_trie_pool_limit =3D -1; +module_param_named(trie_pool_limit, expected_trie_pool_limit, int, 0); +MODULE_PARM_DESC(trie_pool_limit, "Expected stackdepot hash/trie pool spli= t"); + +#ifdef CONFIG_ARM64 +#include + +static inline unsigned long stackdepot_arm64_frame(long offset) +{ + return (unsigned long)((long)_text + offset); +} +#endif + +static void stackdepot_trie_max_path_roundtrip(struct kunit *test) +{ + union handle_parts parts; + unsigned long *entries; + unsigned long *fetched; + depot_stack_handle_t handle; + size_t size =3D 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 =3D kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES, + sizeof(*entries), GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, entries); + fetched =3D kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES, + sizeof(*fetched), GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, fetched); + for (i =3D 0; i < CONFIG_STACKDEPOT_MAX_FRAMES; i++) { +#ifdef CONFIG_ARM64 + entries[i] =3D i & 1 ? 0x1000UL + i * 0x1000UL : + stackdepot_arm64_frame(i * 4); +#elif defined(CONFIG_X86_64) && !defined(CONFIG_UML) + entries[i] =3D i & 1 ? 0xffff888000000000UL + i * 0x1000UL : + 0xffffffff10000000UL + i * 0x10UL; +#else + entries[i] =3D 0x1000UL + i * 0x1000UL; +#endif + } + + handle =3D stack_depot_save(entries, CONFIG_STACKDEPOT_MAX_FRAMES, + GFP_KERNEL); + KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0); + parts.handle =3D handle; + pool_index_plus_1 =3D parts.pool_index_plus_1; + KUNIT_EXPECT_GT(test, pool_index_plus_1, (u32)expected_trie_pool_limit); + KUNIT_EXPECT_EQ(test, + stack_depot_fetch_into(handle, fetched, + CONFIG_STACKDEPOT_MAX_FRAMES), + (unsigned int)CONFIG_STACKDEPOT_MAX_FRAMES); + KUNIT_EXPECT_MEMEQ(test, fetched, entries, size); + KUNIT_EXPECT_EQ(test, + stack_depot_save(entries, CONFIG_STACKDEPOT_MAX_FRAMES, + GFP_KERNEL), + handle); +} + +static void stackdepot_save_flags_public(struct kunit *test) +{ + unsigned long entries[] =3D { 0x501000UL, 0x502000UL, 0x503000UL }; + unsigned long get_entries[] =3D { 0x601000UL, 0x602000UL }; + unsigned long missing_entries[] =3D { 0x701000UL, 0x702000UL }; + unsigned long fetched[ARRAY_SIZE(entries)] =3D {}; + 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 =3D GFP_NOWAIT & ~__GFP_RECLAIM; + unsigned long *overlong_fetched; + unsigned long *overlong_entries; + unsigned int overlong_nr =3D 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 =3D kunit_kcalloc(test, overlong_nr, + sizeof(*overlong_entries), GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, overlong_entries); + overlong_fetched =3D kunit_kcalloc(test, CONFIG_STACKDEPOT_MAX_FRAMES, + sizeof(*overlong_fetched), GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, overlong_fetched); + for (i =3D 0; i < overlong_nr; i++) + overlong_entries[i] =3D 0x800000UL + i * 0x1000UL; + + plain_handle =3D stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNE= L); + KUNIT_ASSERT_NE(test, plain_handle, (depot_stack_handle_t)0); + again =3D stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL); + KUNIT_EXPECT_EQ(test, again, plain_handle); + + nr_entries =3D 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 =3D stack_depot_save_flags(entries, ARRAY_SIZE(entries), n= o_spin, 0); + KUNIT_EXPECT_EQ(test, noalloc_handle, plain_handle); + if (expected_trie_pool_limit >=3D 0) { + noalloc_handle =3D + stack_depot_save_flags(missing_entries, + ARRAY_SIZE(missing_entries), + no_spin, 0); + KUNIT_EXPECT_EQ(test, noalloc_handle, (depot_stack_handle_t)0); + } + + get_handle =3D 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 =3D stack_depot_save(overlong_entries, overlong_nr, + GFP_KERNEL); + KUNIT_ASSERT_NE(test, overlong_handle, (depot_stack_handle_t)0); + nr_entries =3D stack_depot_fetch_into(overlong_handle, overlong_fetched, + CONFIG_STACKDEPOT_MAX_FRAMES); + KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)CONFIG_STACKDEPOT_MAX_FRA= MES); + overlong_size =3D CONFIG_STACKDEPOT_MAX_FRAMES * sizeof(*overlong_entries= ); + KUNIT_EXPECT_MEMEQ(test, overlong_fetched, overlong_entries, overlong_siz= e); + + extra =3D 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 =3D stack_depot_fetch_into(extra, fetched, ARRAY_SIZE(fetched)= ); + KUNIT_EXPECT_EQ(test, nr_entries, (unsigned int)ARRAY_SIZE(entries)); + KUNIT_EXPECT_MEMEQ(test, fetched, entries, sizeof(entries)); +} + +static void stackdepot_snprint_public(struct kunit *test) +{ + unsigned long entries[] =3D { 0x1000UL, 0x2000UL, 0x3000UL }; + char expected[256]; + char actual[256]; + depot_stack_handle_t handle; + unsigned int expected_len; + int actual_len; + + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + handle =3D stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL); + KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0); + + expected_len =3D stack_trace_snprint(expected, sizeof(expected), entries, + ARRAY_SIZE(entries), 2); + actual_len =3D stack_depot_snprint(handle, actual, sizeof(actual), 2); + KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len); + KUNIT_EXPECT_STREQ(test, actual, expected); +} + +static void stackdepot_fetch_into_roundtrip(struct kunit *test) +{ + unsigned long entries[] =3D { + 0x101000UL, + 0x102000UL, + 0x103000UL, + }; + unsigned long exact[ARRAY_SIZE(entries)] =3D {}; + unsigned long fetched[ARRAY_SIZE(entries) + 1] =3D { + [ARRAY_SIZE(entries)] =3D 0xa5a5a5a5UL, + }; + unsigned long expected_tail =3D fetched[ARRAY_SIZE(entries)]; + depot_stack_handle_t handle; + unsigned int nr_entries; + + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + + handle =3D stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL); + KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0); + + nr_entries =3D 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 =3D 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 ku= nit *test) +{ + unsigned long entries[] =3D { + 0x111000UL, + 0x112000UL, + 0x113000UL, + }; + unsigned long fetched[ARRAY_SIZE(entries)] =3D { + 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 =3D 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 =3D 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 =3D stack_depot_fetch_into(0, NULL, 0); + KUNIT_EXPECT_EQ(test, nr_entries, 0U); + + nr_entries =3D stack_depot_fetch_into(handle, fetched, + ARRAY_SIZE(fetched) - 1); + KUNIT_EXPECT_EQ(test, nr_entries, 0U); + KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected)); +} + +static void stackdepot_trie_topology_roundtrip(struct kunit *test) +{ + union handle_parts parts; + unsigned long stacks[][3] =3D { + { 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[] =3D { 2, 2, 1, 3, 2, 2, 2, 2, 2, 3, 2, 3, 2 }; + depot_stack_handle_t handles[ARRAY_SIZE(stacks)]; + unsigned long fetched[ARRAY_SIZE(stacks[0])]; + u32 pool_index_plus_1; + unsigned int i; + + if (expected_trie_pool_limit < 0) + kunit_skip(test, "trie pool limit was not provided"); + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + + for (i =3D 0; i < ARRAY_SIZE(stacks); i++) { + handles[i] =3D stack_depot_save(stacks[i], nr_entries[i], GFP_KERNEL); + KUNIT_ASSERT_NE(test, handles[i], (depot_stack_handle_t)0); + } + parts.handle =3D handles[0]; + pool_index_plus_1 =3D parts.pool_index_plus_1; + KUNIT_ASSERT_GT(test, pool_index_plus_1, + (u32)expected_trie_pool_limit); + + for (i =3D 0; i < ARRAY_SIZE(stacks); i++) { + memset(fetched, 0, sizeof(fetched)); + KUNIT_EXPECT_EQ(test, + stack_depot_fetch_into(handles[i], fetched, + ARRAY_SIZE(fetched)), + nr_entries[i]); + KUNIT_EXPECT_MEMEQ(test, fetched, stacks[i], + nr_entries[i] * sizeof(fetched[0])); + KUNIT_EXPECT_EQ(test, + stack_depot_save(stacks[i], nr_entries[i], GFP_KERNEL), + handles[i]); + } +} + +static void stackdepot_frame_storage_roundtrip(struct kunit *test) +{ + union handle_parts parts; + unsigned long fetched[3] =3D {}; + depot_stack_handle_t handle; + u32 pool_index_plus_1; + unsigned int nr_entries; +#if defined(CONFIG_ARM64) + unsigned long entries[] =3D { + stackdepot_arm64_frame(S32_MIN), + 0x1000UL, + stackdepot_arm64_frame(S32_MAX), + }; +#elif defined(CONFIG_X86_64) + unsigned long entries[] =3D { + 0xffffffff10001000UL, + 0xffff888000001000UL, + 0xffffffff20002000UL, + }; +#else + unsigned long entries[] =3D { 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 =3D stack_depot_save(entries, ARRAY_SIZE(entries), GFP_KERNEL); + KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0); + parts.handle =3D handle; + pool_index_plus_1 =3D parts.pool_index_plus_1; + KUNIT_ASSERT_GT(test, pool_index_plus_1, + (u32)expected_trie_pool_limit); + + nr_entries =3D 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 =3D 0x1000UL; + bool compressed; + u32 payload; + +#ifdef CONFIG_ARM64 + frame =3D (unsigned long)_text + (unsigned long)S32_MAX + 1UL; +#endif + + compressed =3D 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 =3D 0xffff888000001000UL; + unsigned long frame =3D 0xffffffff81234567UL; + unsigned long out; + bool compressed; + u32 low; + + compressed =3D 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 =3D 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 =3D S32_MIN; + long positive_offset =3D S32_MAX; + long offset =3D 0x123456; + unsigned long frame =3D stackdepot_arm64_frame(offset); + unsigned long out; + bool compressed; + u32 payload; + + compressed =3D 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 =3D stackdepot_arm64_frame(negative_offset); + compressed =3D 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 =3D stackdepot_arm64_frame(positive_offset); + compressed =3D 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[] =3D { + KUNIT_CASE(stackdepot_trie_max_path_roundtrip), + KUNIT_CASE(stackdepot_save_flags_public), + KUNIT_CASE(stackdepot_snprint_public), + KUNIT_CASE(stackdepot_fetch_into_roundtrip), + KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack), + KUNIT_CASE(stackdepot_trie_topology_roundtrip), + KUNIT_CASE(stackdepot_frame_storage_roundtrip), + KUNIT_CASE(stackdepot_frame_raw_fallback), +#if defined(CONFIG_X86_64) && !defined(CONFIG_UML) + KUNIT_CASE(stackdepot_frame_x86_64), +#endif +#ifdef CONFIG_ARM64 + KUNIT_CASE(stackdepot_frame_arm64), +#endif + {} +}; + +static struct kunit_suite stackdepot_test_suite =3D { + .name =3D "stackdepot", + .test_cases =3D stackdepot_test_cases, +}; + +kunit_test_suite(stackdepot_test_suite); + +MODULE_DESCRIPTION("KUnit tests for stack depot"); +MODULE_AUTHOR("Caleb Kan "); +MODULE_LICENSE("GPL"); --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f48.google.com (mail-ej1-f48.google.com [209.85.218.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A4C5241D214 for ; Mon, 17 Aug 2026 12:43:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970586; cv=none; b=hLKpqgaq3cvkr1gouzSKUcFeJxHuzaVTRFuWodz9nhLMBZcUrvByR0D+4URzrc/qxLvCWfF+7+owaAiZqEbS+BUCCZD023xyvBA8kU+goGbHTiMaSSSuMJZ8vh4kvgiaWsPJuduMf9u8/hmUJQRU4MpFgvrWQqkFJ1MIZ+vUoM4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970586; c=relaxed/simple; bh=yMd+Nyj0YGCyXtZjyB4hMk1HNYYp6At+bkx6n1ah7sk=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=lwK1n74Fg6VR1BiwgEC76ZzkShGpuD5ieeYFUjpsoP/nAC4wtW578EbrrKuIQE6b4wS8lUD4shbFA/roJL1kGMwN0VHyHbW+93m0/wV/6LthC895Qo/nBEo/bpSZT7Y1ws6T9xIEtYgm05s1lN/zjWEzFn4Ww9k1JjURvdVEulc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Ud5vbNCc; arc=none smtp.client-ip=209.85.218.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Ud5vbNCc" Received: by mail-ej1-f48.google.com with SMTP id a640c23a62f3a-c20fb91ed0fso509253066b.3 for ; Mon, 17 Aug 2026 05:43:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970583; x=1787575383; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=UVg4/TZVG9ztqc574oLKdjAEtEFRQxE/LsLX/hVOog0=; b=Ud5vbNCc322vlX7pQhpkouN1PjB6GYav95NQyBekXN1Pucy6KLZfuUpI/WuGkdpTFT Q/k/HDYt2oqwPjIycP8DCGG7nnu3jBYUFk1VIK0y77V2Bw+XYlo377ZyUXqv1iIOFBzS seldKnqGoGrB6cF/WRF7Yj3pMcUkmggYTIkFDiFvJP9j/cn8p8zrkxDGXUhYqrvCVkvZ 0asFzuVmtAGII77Dozv09MRIWP8qupvOnjITnLt44eeP5J48VzcLtDS5Sls3rGOZ5t3N 8A2x0is4/YrEnxWHblA4UiwddGlUuqgi93ioIbyDH6M01XWsxMwWCRfAa6UmhV4N+lVs FFaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970583; x=1787575383; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=UVg4/TZVG9ztqc574oLKdjAEtEFRQxE/LsLX/hVOog0=; b=PwWkikPkYIfiC9b7NWRovtCZzqW8XGJtHCy5K/MhqtcMuc9lanhSedhAN0WZ49wizL Xls34dLMRFla3LFLe6uTL8ppJ3RZkLWddoszKEtn5iYGtf9/iMH2AjmtBwM5sV3lf8u3 cnXO6XtGQjDdDouWh3ALnP1uJEUOYnBIFyjje586QPS6QOQ6zyoSaw7qg/xZ0tx5a8MC ngJ4HcFu2GauyhY5TiCW2fC4qgco5mlh7LrWGoqYOqY3ALRd7EEJ6ISle1ddciy3eIyn eBEnoUZQJSMryWNqbsNO9ix1j7Vnct5U6I+D7m5zp825MbYd6dtQFofG5yZFD23QMEeS jhAw== X-Forwarded-Encrypted: i=1; AHgh+RrvBWurB0MVvZgSo8dcp2+Ghcv5icAUWtm6bR9UJU0UJBkqk/BjC0paC/YWjGRF8gH/1prYLKxMS4sUSPs=@vger.kernel.org X-Gm-Message-State: AOJu0YzSIldBLVpRaVQmi1uyyvrYRZT/uK7kS5nggV+xW9Bnd3Qv7/JG snUhCut0PApIijsgS8kSMIGpucIYX9Ze1ikoNvvOkFiKDhjcWrylhNfg X-Gm-Gg: AR+sD100JWoO5xG6Dnp1pCq6NtFpX1LGzKZy/EwLoHANf2WKIa0SyC9xgo9X20vpekA rwtubqQgBbNKlPOS5BMr6c7tB9+eLUq7D1EwHvtOdKzKyhz6RvktLEokEdqHkVVa1VBLMPSLhix Zv22FwY2bilB0VeZ6+N7Ah7hMFExS7hZ5bHZe2Siqe7CtMJwqrqi9pcOW9Cs32OUSLTow0PRxJp F7DBCaoLl2dySpAvE2zDy9L2xmyAv4sUWaWY2hV91UA1y48GTGsCN8FpDeQ7pHbL5xJp0g6Q36J 7f2MGtCxVuXNCFAHuJg4hNqzBV4aHO2nhSxzkCS/F8I6SO/bFBAHfV3jJ+YUpujc1cZDtCFf3Yc 1w9MWEgp1gVAVwtVkc56WJ3Yhmp2j1ZrKxkKTvRLKZKJKXGaP9GxSp9IS+ovM0+QVAlJ+QT/YpH GG9c/iusiK8LLMd/vOBysIye582g5Fy9QhEVo= X-Received: by 2002:a17:907:db03:b0:c1c:3b06:ed1b with SMTP id a640c23a62f3a-c212aa3c3b9mr1120204166b.22.1786970582701; Mon, 17 Aug 2026 05:43:02 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:02 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:43 +0100 Subject: [PATCH RFC 3/9] mm/page_owner: preserve accounting with countable stack depot records Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-3-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan page_owner keeps stable struct stack_record pointers in its stack list. It uses each record's count with a one-count bias to track live base pages and reads the stored entries directly. The trie backend provides neither a flat record layout nor an independent count field. Add STACK_DEPOT_FLAG_COUNTABLE to keep these records on the hash backend and deduplicate them separately from all non-countable records. Store the discriminator in a new u16 flags field and narrow size to u16. This keeps the record header size unchanged while covering the configured maximum of 256 frames. Do not otherwise split hash-table deduplication: ordinary and GET saves can continue to share records. Make COUNTABLE mutually exclusive with GET because the two flags assign incompatible meanings to the record count. Reject countable records in stack_depot_put() and require COUNTABLE in __stack_depot_get_stack_record(). Mark both page_owner save sites countable so its existing accounting and reporting continue to use stable hash records. Extend the KUnit coverage to verify direct-record access and isolation between countable and non-countable records. Signed-off-by: Caleb Kan --- include/linux/stackdepot.h | 14 ++++++++--- lib/stackdepot.c | 30 +++++++++++++++++++----- lib/tests/stackdepot_kunit.c | 55 ++++++++++++++++++++++++++++++++++++++++= ++++ mm/page_owner.c | 6 +++-- 4 files changed, 94 insertions(+), 11 deletions(-) diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h index 96544fc684a5..788737eb0c4a 100644 --- a/include/linux/stackdepot.h +++ b/include/linux/stackdepot.h @@ -53,7 +53,8 @@ union handle_parts { struct stack_record { struct list_head hash_list; /* Links in the hash table */ u32 hash; /* Hash in hash table */ - u32 size; /* Number of stored frames */ + u16 size; /* Number of stored frames */ + u16 flags; union handle_parts handle; /* Constant after initialization */ refcount_t count; union { @@ -84,8 +85,9 @@ typedef u32 depot_flags_t; */ #define STACK_DEPOT_FLAG_CAN_ALLOC ((depot_flags_t)0x0001) #define STACK_DEPOT_FLAG_GET ((depot_flags_t)0x0002) +#define STACK_DEPOT_FLAG_COUNTABLE ((depot_flags_t)0x0004) =20 -#define STACK_DEPOT_FLAGS_NUM 2 +#define STACK_DEPOT_FLAGS_NUM 3 #define STACK_DEPOT_FLAGS_MASK ((depot_flags_t)((1 << STACK_DEPOT_FLAGS_NU= M) - 1)) =20 /* @@ -144,6 +146,11 @@ static inline int stack_depot_early_init(void) { retur= n 0; } * Users of this flag must also call stack_depot_put() when keeping the st= ack * trace is no longer required to avoid overflowing the refcount. * + * If STACK_DEPOT_FLAG_COUNTABLE is set in @depot_flags, stack depot store= s 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 mut= ually + * exclusive with %STACK_DEPOT_FLAG_GET. + * * When trie storage is enabled, persistent non-refcounted saves use trie * storage. Constrained callers only look up existing stacks; they do not = insert * a missing stack. Trie failures do not fall back to hash storage. @@ -190,7 +197,8 @@ depot_stack_handle_t stack_depot_save(unsigned long *en= tries, * * @handle: Stack depot handle * - * This function is only for internal purposes. + * This function is only for internal purposes. @handle must have been sav= ed + * with %STACK_DEPOT_FLAG_COUNTABLE. * * Return: Returns a pointer to a stack_record struct */ diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 0278b7a013f1..1e5b9fc44618 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -2,10 +2,11 @@ /* * Stack depot - a stack trace storage that avoids duplication. * - * Internally, stack depot has two storage backends. Refcounted entries us= e the - * legacy hash table with contiguous stack records in stack pools. Persist= ent - * non-refcounted entries can use trie storage when enabled; trie nodes sh= are - * common frame prefixes and are published through RCU children containers. + * Internally, stack depot has two storage backends. Refcounted entries and + * callers that request STACK_DEPOT_FLAG_COUNTABLE use the legacy hash tab= le with + * contiguous stack records in stack pools. Persistent non-refcounted entr= ies + * can use trie storage when enabled; trie nodes share common frame prefix= es and + * are published through RCU children containers. * * Author: Alexander Potapenko * Copyright (C) 2016 Google, Inc. @@ -1022,6 +1023,7 @@ depot_alloc_stack(unsigned long *entries, unsigned in= t nr_entries, u32 hash, dep /* Save the stack trace. */ stack->hash =3D hash; stack->size =3D nr_entries; + stack->flags =3D 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_entrie= s)); =20 @@ -1164,6 +1166,9 @@ static inline struct stack_record *find_stack(struct = list_head *bucket, list_for_each_entry_rcu(stack, bucket, hash_list) { if (stack->hash !=3D hash || stack->size !=3D size) continue; + /* Page owner countable records have a distinct count lifetime. */ + if ((stack->flags ^ flags) & STACK_DEPOT_FLAG_COUNTABLE) + continue; =20 /* * This may race with depot_free_stack() accessing the freelist @@ -1267,6 +1272,9 @@ depot_stack_handle_t stack_depot_save_flags(unsigned = long *entries, =20 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; =20 /* * If this stack trace is from an interrupt, including anything before @@ -1281,7 +1289,7 @@ depot_stack_handle_t stack_depot_save_flags(unsigned = long *entries, if (unlikely(nr_entries =3D=3D 0) || stack_depot_disabled) return 0; =20 - if (!(depot_flags & STACK_DEPOT_FLAG_GET) && + if (!(depot_flags & (STACK_DEPOT_FLAG_GET | STACK_DEPOT_FLAG_COUNTABLE)) = && static_branch_unlikely(&stack_depot_trie_enabled)) { if (nr_entries > CONFIG_STACKDEPOT_MAX_FRAMES) nr_entries =3D CONFIG_STACKDEPOT_MAX_FRAMES; @@ -1374,12 +1382,20 @@ EXPORT_SYMBOL_GPL(stack_depot_save); =20 struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t h= andle) { + struct stack_record *stack; + if (!handle) return NULL; if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle))) return NULL; =20 - return depot_fetch_stack(handle); + stack =3D depot_fetch_stack(handle); + if (!stack) + return NULL; + if (WARN_ON_ONCE(!(stack->flags & STACK_DEPOT_FLAG_COUNTABLE))) + return NULL; + + return stack; } =20 static void frame_run_init(const unsigned long *entries, @@ -2136,6 +2152,8 @@ void stack_depot_put(depot_stack_handle_t handle) if (WARN(!stack, "corrupt handle or unbalanced stack_depot_put()")) return; =20 + if (WARN_ON_ONCE(stack->flags & STACK_DEPOT_FLAG_COUNTABLE)) + return; if (refcount_dec_and_test(&stack->count)) depot_free_stack(stack); } diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c index 75fa16268c0b..be14cae98fcf 100644 --- a/lib/tests/stackdepot_kunit.c +++ b/lib/tests/stackdepot_kunit.c @@ -167,6 +167,60 @@ static void stackdepot_snprint_public(struct kunit *te= st) KUNIT_EXPECT_STREQ(test, actual, expected); } =20 +static void stackdepot_countable_public(struct kunit *test) +{ + unsigned long plain_entries[] =3D { + 0x141000UL, + 0x142000UL, + 0x143000UL, + }; + unsigned long get_entries[] =3D { + 0x151000UL, + 0x152000UL, + 0x153000UL, + }; + unsigned long fetched[ARRAY_SIZE(plain_entries)] =3D {}; + depot_flags_t countable =3D 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 =3D ARRAY_SIZE(get_entries); + unsigned int plain_nr =3D ARRAY_SIZE(plain_entries); + unsigned int nr_entries; + + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + + plain_handle =3D stack_depot_save(plain_entries, plain_nr, GFP_KERNEL); + KUNIT_ASSERT_NE(test, plain_handle, (depot_stack_handle_t)0); + count_handle =3D stack_depot_save_flags(plain_entries, plain_nr, GFP_KERN= EL, + countable); + KUNIT_ASSERT_NE(test, count_handle, (depot_stack_handle_t)0); + record =3D __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 =3D 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 =3D 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 =3D stack_depot_save_flags(get_entries, get_nr, GFP_KERNEL, + countable); + KUNIT_ASSERT_NE(test, count_handle, (depot_stack_handle_t)0); + record =3D __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[] =3D { @@ -392,6 +446,7 @@ static struct kunit_case stackdepot_test_cases[] =3D { KUNIT_CASE(stackdepot_trie_max_path_roundtrip), KUNIT_CASE(stackdepot_save_flags_public), KUNIT_CASE(stackdepot_snprint_public), + KUNIT_CASE(stackdepot_countable_public), KUNIT_CASE(stackdepot_fetch_into_roundtrip), KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack), KUNIT_CASE(stackdepot_trie_topology_roundtrip), diff --git a/mm/page_owner.c b/mm/page_owner.c index fbbda7ba914b..af37532729b0 100644 --- a/mm/page_owner.c +++ b/mm/page_owner.c @@ -119,7 +119,8 @@ static __always_inline depot_stack_handle_t create_dumm= y_stack(void) unsigned int nr_entries; =20 nr_entries =3D 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); } =20 static noinline void register_dummy_stack(void) @@ -181,7 +182,8 @@ static noinline depot_stack_handle_t save_stack(gfp_t f= lags) =20 set_current_in_page_owner(); nr_entries =3D stack_trace_save(entries, ARRAY_SIZE(entries), 2); - handle =3D stack_depot_save(entries, nr_entries, flags); + handle =3D stack_depot_save_flags(entries, nr_entries, flags, + STACK_DEPOT_FLAG_CAN_ALLOC | STACK_DEPOT_FLAG_COUNTABLE); if (!handle) handle =3D failure_handle; unset_current_in_page_owner(); --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f45.google.com (mail-ej1-f45.google.com [209.85.218.45]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9E92541D22A for ; Mon, 17 Aug 2026 12:43:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970587; cv=none; b=dIDtFxyNVQhtuS1b3p8Ob049pROUqtufgH8z2IVJo8/3KsyDx05X1cLr86qN/g8uw+lbEN43BFMu/W/bEU+4CN78T+OlRNrxFqXXJ8ezs0gDQMv+2Bpn0ycFTw02LyX+PeVHNNcZxYoU+X5fR2rpA/2Y26coAmEgOisyAjJOpJY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970587; c=relaxed/simple; bh=KUMLl8Nlf4ganKmUfRpSqfk9SbXFsUXlAZxjeBAClCg=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=b83cNULEGdAi/JApJ+eVmHlSke4dxEpG+lTIxERixE3L8/hit/W6q4fJ1ogQb+/Bm7IAsu2YF1RAWiDyhGWwktmm1X5DmWDqTKygJT05406oP8o5g73G1vDKa1Sh4GGEII6dZOpA0c45Vnuk9iWOg9xB2aRfnbhUcV8XCcOOfwU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=P+EUHASL; arc=none smtp.client-ip=209.85.218.45 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="P+EUHASL" Received: by mail-ej1-f45.google.com with SMTP id a640c23a62f3a-c1c52d920b8so445131266b.2 for ; Mon, 17 Aug 2026 05:43:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970584; x=1787575384; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=mbEf3V3BeedaNXPvyc7QWrrndht5k6QHT5mMZYzozBE=; b=P+EUHASLaJsC32Wtu4NSGGADf8mrBCWB6iwSloohBBNp+mZN9Ui5nFwK5nYUmVmww2 CxusxVoV9oXGRrOyrAbuHwWyy4cbgTXKFbdyzxdBIulf092nsBZvzKh+DX/ud704nLQJ FzJCiFVtyIXsAFNM22xNreZTDRqJ5QcWo7sP8aWsLYn3BdAM7vgmZ3o/IruYhwVzrxof Qsg+awPBC2aVmtWz3xlgqbTiUTMiQ7fegcQmmLapp5nWhIMHVcKRat8dSc1ST4LPT3VS DCmSgVBddlFOlCgkaDGuRx1vrft/5DV0aE+Fo8YaLtwZlBMeypPYu87lwuUH9yw03MSV pXyA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970584; x=1787575384; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=mbEf3V3BeedaNXPvyc7QWrrndht5k6QHT5mMZYzozBE=; b=RjH+2mmRYrA3b0S9BUrZdxZTw9nrkO8xqhtfd+VpOsI7JNVNfeJDBEWztYHL6LlrBR P4ZQpqEV96y90/tPvfHsVV5T8Vz1jSMhVCElJ/3J+tK3SxLOEv9WoN+1CzFY2vSXglOH 4W/GoNphk9UIvWqbF+WxsMa53mhPzWZrfL6h2C+XKPsQsahCnmHIgiUGLazX2m2A5bNd k0b9wBRGlGmlpHo+uZ2Fdvm32hoYq4lP9954KFeJBNL202v0ItDP3dp+Hdhz8SEg7Jp1 t5bL28X9lYCBGYn85jdBuKrNpbw5CucLRDOcSpQn4LoUjyX/N2cJQsd2tDKmaGu2q+NF 58lg== X-Forwarded-Encrypted: i=1; AHgh+RqdNmUiYPrVVAYhDTKqzGFDS90X1CeUDElzLKLCRvq4KZZ1Ik5MHlHSC0ceyRPPAZLA17Ilo6m8SSgPDVg=@vger.kernel.org X-Gm-Message-State: AOJu0YzOhwwSdX+LSe7L++fmOvp2okgmmtPLC3647jIW6rPCzilcuMPY ckaaPyiH9cDgp9UpTMrSQnSTPwCOKAESGrjLzhlwlwrj3gkVZtDP9IHp X-Gm-Gg: AR+sD105KGdpoCqFYYCFqgytUS3uJqEJXUd8dS7LzP0PbRlNil1Bkhbe26O9kMLBs2m YSTqZZLzGMo+Ij+GluFEhZPkEr3OCstMCfc42783MFg8G6NdMYxZ07XoSxD5fPzBoNgw56X1PtZ HSx+EmBbmKCQE32sBtALoNruF9fGFeyehfmVblgPYMj97s9o98+onXEJbxYZuU6jQWlXhV3dWDz yQgup9u5f/AX1axNdu3YieAlWW2jHz2zuLFfG1fg6MTyxmI7BDaQTshptmq4kck7LUx+Da/lfOw f5tjfWSYSV2RoGVgMlqWbrqqTfHqSWnno4tJTQouXtzKp4C6gNLc12z4mq4I9zCnzrWt280zOrA U7x9QCUtfncQQqpFmLcP8xnAKlS6eerso1GKdmkGFrmj4dvcL2Yb2CJKLFL3NA3vXt5qUF1DJ6i ZRri5ldvY9z+VLlwLy0nIO9zFJJohT+d8xAw9hE1a8xHIPMWHBKQ== X-Received: by 2002:a17:906:f183:b0:c21:82bb:1105 with SMTP id a640c23a62f3a-c2182bb1689mr70810566b.22.1786970583773; Mon, 17 Aug 2026 05:43:03 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:03 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:44 +0100 Subject: [PATCH RFC 4/9] mm/kmemleak: print trie-backed stack depot traces Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-4-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan 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 --- 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; =20 - nr_entries =3D stack_depot_fetch(object->trace_handle, &entries); + nr_entries =3D stack_depot_fetch_into(object->trace_handle, entries, ARRA= Y_SIZE(entries)); warn_or_seq_printf(seq, "unreferenced object%s 0x%08lx (size %zu):\n", __object_type_str(object), object->pointer, object->size); --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f49.google.com (mail-ej1-f49.google.com [209.85.218.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C05F141D236 for ; Mon, 17 Aug 2026 12:43:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970588; cv=none; b=Cin+ho1yrwkFmXIO/ufsBfQ8gOr+cjkj8pj5/NDRKZ6ezDCoKe8b4+2Qa9SY19o/BVpqo/UcZB2w3iK/nEljaTvL2f2EE/V+PXTB7cRjZit8vCYcGYaJWeuNmaxzcIfb15okRa3zzRm4feAE/LnLaHGVg4ezKvqN3qc3c4PeRUg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970588; c=relaxed/simple; bh=0RLaQ+92eQAJAGljPWO672IUauMEYT9qdG3jEOmsWHM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=AuVinPTFe0yByaqNOFsHnxJc/ESs1wsHsPnMoPaGChPFYvj/l8itfeiNaR36RcFomGV55BF6K03mYKYz5fXcBQ6zoksi4+lEW9BQNqoryrlgiU7wDJp/ofz2PDoH7IkKS4yu7ayJUsZnFBbYqgBYoyWhdO41BcGbMNpGV9Kdcc8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ooxdBXKP; arc=none smtp.client-ip=209.85.218.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ooxdBXKP" Received: by mail-ej1-f49.google.com with SMTP id a640c23a62f3a-c15d111ca99so354093566b.0 for ; Mon, 17 Aug 2026 05:43:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970585; x=1787575385; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=ZNN86hXrdrGG1E/YizrMzJjnTH3T1mAw0aE/Reny4I4=; b=ooxdBXKPw70ZILb3zJRUY3jO8R7vCmC+96Me5K7eedsVd3exrATd+fQo5H2e8BHSnR 8gvnrdDJj1zMY75r6zFh1Mveh2NMfHWvr/DbIsWJMjmZ68hAOqKvonggSxYU9qzDtr4O VnR7vpxDpRPiBWj58Ufe8b4a9SHmjaGRs8JZzKZcPsJZkR7tx+jcwsnTlgEsseJh4IBE s5+G8Cdo+EEueJeuduXKTx3eU1Csl/Yw/yEBV/oWdUdGg7WfEswj3c8cWCr/WAFtoc+v wJUPOKANiYbxCphQmNAbtatlj9+hyJllzWGxAG/PSHoDn5/7kfEmdvU4pNsdQjRJf6Dk nb4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970585; x=1787575385; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=ZNN86hXrdrGG1E/YizrMzJjnTH3T1mAw0aE/Reny4I4=; b=P7GYQ7WMxqi6OrLZxKH5DYm1h03u++rEUWjB6qBpVjGI70wSckYFxmSE2E8NZs9DdR 4bjCJHs8Sk4FWw0gbzuTpZmRvDMvxeJ3wthp8VkxUS+UYoCRLKa33BuRzGyXTmC+iTUg Pa6J5K7+/yfg5EGX3ligbEixIQoXaTMduSBjXriDrk8aZyNFY6BntVje0rGwPUwHfU7O tDzWTds97ws5Qagoa+FfPp+jtuVQaGBkJJhGP3p7b9/SKDD6HYvYsudFXuigrcs1AcpC s4Osv+qVBEuYcPuY6sTibv4t/Xc0t/wMAHQBNenbOHJBXwdMhYxG/ZHhmwFOpDo3+7Ac gDDw== X-Forwarded-Encrypted: i=1; AHgh+RomM5llquPg01FRvPIUrfa3UE6tP0IAr6oZS5qKJa6++0a7AKEMhFlfYL6ZIIBYHft4WFjcs1AbRpDQHtc=@vger.kernel.org X-Gm-Message-State: AOJu0YzxltWR8yCB86EBQqibGOLQGzUiXS6JPQbYxDLa0DsjQ6RDg2Sk nLE/svrjiMxwK3MlUo/6XRUTVVtPLPOaKun7b5ReXlv5T6plB1O7ies5 X-Gm-Gg: AR+sD1208U56MtSDuVUSobAZV/Q9p95hP0IfKK6SRWl63k67sxCvyDaFu+7n4KlJQMf 2ywL9NvB0t1M6Cm+lXAI+zlyaMYARBQy2ACz/5hySKoqJs2z4Wz2f77446NX2+iqi5tSGmPvYWJ QbZScUrg6M0h7M+JWO2vlmPDJv7oDyJ4/YInPONHtBs6uLbVHTed8+0+dP74Hnb5VjM2cTDHhau oTiGovN7+502yzhNSUwsLz4RiAOAJeNac27SwTM7Bo9lXAjCQ32/hos1XjZFh5TfIMi53gF4S6q 4SLHd30uMGfVWhH/cklNoqKieDbKG7+g9K3+Xxx7OWgDvPAkbCDDkYMs6fHNy5IOpIoaakYoU3p sv0XKKOLU1iietpss3k/WUDhAaIFh39d2wNr4A6xENwWK+hR/BOoL/hYGRBCZeLxzzLVExiVjdZ J4jQsDpstgfgi+dVXou4Eoe3NSDN64qOPXogyWKWwtVa0yjT6V7Q== X-Received: by 2002:a17:907:608b:b0:c16:73a0:c4ec with SMTP id a640c23a62f3a-c212a26d672mr1059757766b.18.1786970584755; Mon, 17 Aug 2026 05:43:04 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:04 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:45 +0100 Subject: [PATCH RFC 5/9] kmsan: report trie-backed stack depot traces Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-5-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan KMSAN stores ordinary origin stacks and synthetic alloca and chain origins as persistent stack depot records. Once trie storage is enabled, these handles can be trie-backed, while kmsan_print_origin() still relies on the hash-only stack_depot_fetch() API. Use one KMSAN_STACK_DEPTH array to materialize each origin and chained stack in turn. Preserve the chain's head and next-origin handles before reusing the array for the chained stack. The array covers both the regular save limit and the smaller synthetic records. lib/stackdepot.c is uninstrumented, so stack_depot_fetch_into() unpoisons the successfully copied range before returning it to KMSAN. Remove the now-redundant explicit unpoisoning of chained entries. Origin depth and use-after-free metadata remain in the handle's extra bits and are unchanged. Update test_stackdepot_roundtrip() to use caller-owned storage while retaining its frame-count and kmsan_check_memory() checks. This verifies that the copy-out API returns initialized entries to instrumented callers. Signed-off-by: Caleb Kan --- mm/kmsan/kmsan_test.c | 4 ++-- mm/kmsan/report.c | 17 +++++++---------- 2 files changed, 9 insertions(+), 12 deletions(-) diff --git a/mm/kmsan/kmsan_test.c b/mm/kmsan/kmsan_test.c index 31f47cc4dab4..7c04e4b21873 100644 --- a/mm/kmsan/kmsan_test.c +++ b/mm/kmsan/kmsan_test.c @@ -669,7 +669,7 @@ static void test_long_origin_chain(struct kunit *test) */ static void test_stackdepot_roundtrip(struct kunit *test) { - unsigned long src_entries[16], *dst_entries; + unsigned long src_entries[16], dst_entries[16]; unsigned int src_nentries, dst_nentries; EXPECTATION_NO_REPORT(expect); depot_stack_handle_t handle; @@ -680,7 +680,7 @@ static void test_stackdepot_roundtrip(struct kunit *tes= t) stack_trace_save(src_entries, ARRAY_SIZE(src_entries), 1); handle =3D stack_depot_save(src_entries, src_nentries, GFP_KERNEL); stack_depot_print(handle); - dst_nentries =3D stack_depot_fetch(handle, &dst_entries); + dst_nentries =3D stack_depot_fetch_into(handle, dst_entries, ARRAY_SIZE(d= st_entries)); KUNIT_EXPECT_TRUE(test, src_nentries =3D=3D dst_nentries); =20 kmsan_check_memory((void *)dst_entries, diff --git a/mm/kmsan/report.c b/mm/kmsan/report.c index d6853ce08954..c20c24cffde5 100644 --- a/mm/kmsan/report.c +++ b/mm/kmsan/report.c @@ -85,7 +85,7 @@ static char *pretty_descr(char *descr) =20 void kmsan_print_origin(depot_stack_handle_t origin) { - unsigned long *entries =3D NULL, *chained_entries =3D NULL; + unsigned long entries[KMSAN_STACK_DEPTH]; unsigned int nr_entries, chained_nr_entries, skipnr; void *pc1 =3D NULL, *pc2 =3D NULL; depot_stack_handle_t head; @@ -97,7 +97,8 @@ void kmsan_print_origin(depot_stack_handle_t origin) return; =20 while (true) { - nr_entries =3D stack_depot_fetch(origin, &entries); + nr_entries =3D + stack_depot_fetch_into(origin, entries, ARRAY_SIZE(entries)); depth =3D kmsan_depth_from_eb(stack_depot_get_extra_bits(origin)); magic =3D nr_entries ? entries[0] : 0; if ((nr_entries =3D=3D 4) && (magic =3D=3D KMSAN_ALLOCA_MAGIC_ORIGIN)) { @@ -123,14 +124,10 @@ void kmsan_print_origin(depot_stack_handle_t origin) origin =3D entries[2]; pr_err("Uninit was stored to memory at:\n"); chained_nr_entries =3D - stack_depot_fetch(head, &chained_entries); - kmsan_internal_unpoison_memory( - chained_entries, - chained_nr_entries * sizeof(*chained_entries), - /*checked*/ false); - skipnr =3D get_stack_skipnr(chained_entries, - chained_nr_entries); - stack_trace_print(chained_entries + skipnr, + stack_depot_fetch_into(head, entries, + ARRAY_SIZE(entries)); + skipnr =3D get_stack_skipnr(entries, chained_nr_entries); + stack_trace_print(entries + skipnr, chained_nr_entries - skipnr, 0); pr_err("\n"); continue; --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f44.google.com (mail-ej1-f44.google.com [209.85.218.44]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 798E241D217 for ; Mon, 17 Aug 2026 12:43:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.44 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970589; cv=none; b=U9wbLivgkhF0TCtLyyZRjWvpOlY+Rp+skpWBgxuyQK4mF4l4OeKL1zSWPPqU0OjXSdRx8AHbyC9FaEVMeLYRO5WxuzdWHKOpt5UTSahHic96n3a8ebqRJe2kjfaJG5ErwZscXK2ya4w+vHFZ/gJ4m4aanDqKzUZ+SOYKrR0d9mA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970589; c=relaxed/simple; bh=6W8fGILoEK2GVw5txNRHMOz1yEKoSCNedUwlMSGOu64=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=WMksbI52JozRHoJnT0EZggn2H1hLXGgvr7xrYjF5lCCwiux/Vo6S5AxwKkjNcszr0kWEbsDb0zLmvH9xrJEZzIHxm6U0IgLncWgbxmsev3oPabunsqtyp7pbmeDZx1shZk5ig+N+F4MAnYiDD+lzYkxX91azERbNLq81SZBXgn8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kH8Tt7Yw; arc=none smtp.client-ip=209.85.218.44 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kH8Tt7Yw" Received: by mail-ej1-f44.google.com with SMTP id a640c23a62f3a-c2074710751so525439866b.1 for ; Mon, 17 Aug 2026 05:43:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970586; x=1787575386; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=sRrI0ZiNFWDC68LZNy9rl9u6YO6/uPndbIK+uC0O4Y4=; b=kH8Tt7Yw+8Hq0FOylz0GFu1x/m5baZwnw8dACgErXKGrvCi01NjUnctYEtFvyubwdo Qv3Rl3vRq4eVQYEhF45B+kwpGQZ+4cNV12K8NFXxEjlyVEo4s9KSE6NzZBw3CqxTYnoz 4Blrv6Ue+witlxvLa/eyS/3MIv91ijTILpUU5/dTD7DrJO2RQ6smA0tlezhEqmH2NVkG VG0NofrVsMio9qw82ARQq0Te6TzxqhOTCD1AVSj4UNAAsnJbyky5bGfuPk8Ifov9Jytg yc5iGhhzNaML1M3X2NGgtxWRH8GY5Dfd+/3gto9q6wX7ERqCHTjxwcbHUP4jusHqXZms tl0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970586; x=1787575386; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=sRrI0ZiNFWDC68LZNy9rl9u6YO6/uPndbIK+uC0O4Y4=; b=CIxZ/KI6Jv7tQ5j+FYxKoe7n1H1vG629ExnrkfUG4Ylw20pDZnTtdBxdA0kFY6iXFq FcvBGiIuB6sq04TvuJ2tlSfY3jkSRjxswYOoghnaXKkDiOUW6qAJp6auTYr/emQiJLuz 0OZxKqC7/K5Zr2MOkE7R+4QN7Wv6WY+QiUsAqbuKqFDazfIyWpMiefFtClxuQaDeIxRo OdC4x9UXX8zjxpfqSVp/up7aSx5cHJBtZgwx0/G2rbB0Tkq7lOzgEte7S5Ye3Q5KmGic l0r2igR6zHePvqXgu4Uh/TqvQX0kDOxTLhimeRfTtyPeo5DftKsQqC121MOJUvi6Wify rFBQ== X-Forwarded-Encrypted: i=1; AHgh+RrVobjUB+o4SS3TnkHFNo+OhjUpKYO8DWKoZ1EtcGbHux4WaplqXrVoQp4/KIrL2YeY4PqWcESyUtL+Fjs=@vger.kernel.org X-Gm-Message-State: AOJu0Yy2fBvj5ICjAVa4Ia51hWWatWwzuG/QYLTogEA7PHPEcokRP5SB UN3ZYPutteCKYVJ8Lq1JuAYFENxt+cSb8RBEevd+KXCPhXEDA5MS6M0H X-Gm-Gg: AR+sD115CSAqN74l29wUCLLdI5tu6+FNbQ+jz3lqvbwDeNproSWYjCBk9mlxiU16oHa HOAZ4swusjCAYAZcPs5drJ2h3/PefqN/4Pz1o3xr63PcBWag7p+ys7NdZ/m2By6NBQIA7GjkoKC 7eSzf9QxgkZEWOVX/wH2KjASFnOvZH41eLIeKfgUnHtVirOLuHyVxy9h7fatx02dOXCwcgmKf/H FlJ7fMFMXx56T6Yx/vckA8Rt/3q6FrWDCpRBF3IGJi0a4kSYrjudzfqGiScU97cTvtsnKn0iIro JDNRCMOhkyZ6GPzt7T0jxXEW+HkxN6el/XMnbC2NDxAgYN3gRYojaKG2m5W4MRioaaXT7mstizw 7Dj0pPyboJbkq7XiV4bdWGbb4ZuWPU53T3y0evADaS1KsjsxQ8tHg5p1REwK3DQ6wSKLnhKNUWx E4nl06+YBlhzFP5N3H5z+7t4hWAgsPEbLxaFmqL7XOOqNHadFk3A== X-Received: by 2002:a17:907:1609:b0:c16:b87:de64 with SMTP id a640c23a62f3a-c212a1250a6mr1202678666b.15.1786970585499; Mon, 17 Aug 2026 05:43:05 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:05 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:46 +0100 Subject: [PATCH RFC 6/9] mm/slub: materialize trie-backed stack depot traces Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-6-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan 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 --- mm/slub.c | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/mm/slub.c b/mm/slub.c index 422bc3e12c02..138c3bc473c9 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -8093,12 +8093,12 @@ void __kmem_obj_info(struct kmem_obj_info *kpp, voi= d *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; =20 handle =3D READ_ONCE(trackp->handle); if (handle) { - nr_entries =3D stack_depot_fetch(handle, &entries); + nr_entries =3D stack_depot_fetch_into(handle, entries, ARRAY_SIZE(entri= es)); for (i =3D 0; i < KS_ADDRS_COUNT && i < nr_entries; i++) kpp->kp_stack[i] =3D (void *)entries[i]; } @@ -8106,7 +8106,7 @@ void __kmem_obj_info(struct kmem_obj_info *kpp, void = *object, struct slab *slab) trackp =3D get_track(s, objp, TRACK_FREE); handle =3D READ_ONCE(trackp->handle); if (handle) { - nr_entries =3D stack_depot_fetch(handle, &entries); + nr_entries =3D stack_depot_fetch_into(handle, entries, ARRAY_SIZE(entri= es)); for (i =3D 0; i < KS_ADDRS_COUNT && i < nr_entries; i++) kpp->kp_free_stack[i] =3D (void *)entries[i]; } @@ -9815,12 +9815,14 @@ static int slab_debugfs_show(struct seq_file *seq, = void *v) #ifdef CONFIG_STACKDEPOT { depot_stack_handle_t handle; - unsigned long *entries; + unsigned long entries[TRACK_ADDRS_COUNT]; unsigned int nr_entries, j; =20 handle =3D READ_ONCE(l->handle); if (handle) { - nr_entries =3D stack_depot_fetch(handle, &entries); + nr_entries =3D + stack_depot_fetch_into(handle, entries, + ARRAY_SIZE(entries)); seq_puts(seq, "\n"); for (j =3D 0; j < nr_entries; j++) seq_printf(seq, " %pS\n", (void *)entries[j]); --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ej1-f47.google.com (mail-ej1-f47.google.com [209.85.218.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EC2EB41D216 for ; Mon, 17 Aug 2026 12:43:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970589; cv=none; b=n5Ad10wPpUtdoLO8kG2wAgixSmIYE1UlSaH+txA8KAfWkYEIiLe0yBaPrh0pmac8y+qh5PwcLXfAb/p4c639Rdt57M6MBfEG8k4vbvaKPCqElHKDQzKO0G7RdU6QkRFKwXOKa+56gtxSTKYCf7tNUbHT6V/1ab4KFSxHejpYUcg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970589; c=relaxed/simple; bh=8SAvHtTOo7kQQaOBd4rUev2A3jq/7c0IgMr2JVTVr6k=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=TIihodPqYvkBWk+T/x2P+CLc4oDXGDOTFUNIHmNBx8a4gm2e2g+B+utJmqSpMzXYplJZbSev+9gjrowZ6lbi/c3xAbyjQkeRS6EYyVI9HHb++0A7dWs2eR8dp8m6eqk7vnzY6PtO8J6k7TXdq2Uz+sujL+xXRhbv2jHwzeNlvIg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=fLwEb+7g; arc=none smtp.client-ip=209.85.218.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="fLwEb+7g" Received: by mail-ej1-f47.google.com with SMTP id a640c23a62f3a-c1712a04ddaso552198266b.2 for ; Mon, 17 Aug 2026 05:43:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970586; x=1787575386; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=h4fUYxQNQI9siUe9sl4T0IlOWMNDubqmMBb1FSe4NDw=; b=fLwEb+7gfTj5UMYqnrvtSMyRmHlhsRa9ntyr7SV2a48FjqqJeEBYEapx49YWiDSLei TLwbPuZ4+6MjoiCFvgymiXPZtc7MMTA0A0EBsSQUIl9qpTpF8o7iXvu+hTgK8cmfIYuT mf01vi2C80ooiSp6HUKLDuRuFHe1JzspvKvke2GXtloSiVO3TZdW/1bToUJfKPR2TXw+ JLr8Uk5sdW9q9Lnj+8ZiHrMJpgmBpZaaFIZhlTV6GmfkU8rMCRjZqLnxsVzU4rEgIrAX llBfBx3kdfKtIu+hn7Lf6p5ZR6jXQXRHhqldIzWPVRgoTFhwgopR/X6UJIWSV8HXB8e7 O3hw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970586; x=1787575386; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=h4fUYxQNQI9siUe9sl4T0IlOWMNDubqmMBb1FSe4NDw=; b=L8XG0+Mwfy06efCWSMSnKtyjJqunWSZDKwUR+cpu1n2tRKExdBDrZyV7OvY7i6J8Bh SFe6uSGR0yAcB4MYR8xetpiMjHqTFTSooB/91nS8+2Cdvmz4hrAGj5d2qB2dgdzAXjRG SXdBJrWR6MEuuwSzPhDmmCSZf3+n0V+OgCe324vjNxXIONglG8A4khOPFswloLG2cyuQ ynH48ZPgml4MKQ/N+ehCLDspOSmOPGSg8GZ0QE1yZWI4uLmUIGVt5srMx3Qp0gcbalF9 KQcIPoLBkJMzqPbvR07kjHboa+mGtZHIyN5Bh+e6MbKZneWJSi8ErzdU+TK9tg765z0W yf8Q== X-Forwarded-Encrypted: i=1; AHgh+Rrh2XNHsfLRz+t+2AGJldms4ntdHvIw6+49XwUPyi+kW9Na4HknQmEv66aD5WBV+x3csA0lj5YBIY7CVlU=@vger.kernel.org X-Gm-Message-State: AOJu0YyHte0BYbELhgbHEgR+GpU6/ZjHAmTT98ZgVhxLA0qUZfnCwWOn Jo3Gwnr1U9AxVwnBTuGdgZIGz+E8pnQWyFii0cIzoGN1x0HA2a7ot/xO X-Gm-Gg: AR+sD125liitXsRLpG/DHFLCv7L4rFk3ff5J6M8z487RNd8aW/GiH3gNmjpMsNmDuY9 Bv6MIreNFcCWa0mUbVuN35uNTks0uFIaAQRgN+d6INHSOye4OzcMs33L9LhxVr3Qtg4/g2YHvqK mEu9mANmQQlhM4Li25K8nxbtDHAZYchkjwINDPyQE80pwfr+Fs26sD2e73jZl3sSs177Tc9ss+W SGf4cXqub9gK5Litj+cuZ59t3z2VyoTmjkk8dEQbuP/FKfIJ6/+ZEU+L32lqkN6dTKIxHfWHMob 1Uust+1V8GPw9uTLALRG+G31dyprpl0kJpYF3WNf9FWOMkBIcM/BCDCM2C5j3Eem62Z0SC/HWPy rTAMKwM858JrmkuS7J4AQo0RY8iDuH/zdZnO0TWuW/AWMmJs5gZFR1J+b7rEG5tPLphoyQVv8tg clXrv4y4ii5/tbcwl2urAlLqaGbD9+OezcirK1l13f1PQvhGWsqw== X-Received: by 2002:a17:906:fe07:b0:c20:191e:89de with SMTP id a640c23a62f3a-c212a1c7d33mr1077304166b.25.1786970586168; Mon, 17 Aug 2026 05:43:06 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:05 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:47 +0100 Subject: [PATCH RFC 7/9] drm/locking: preserve deadlock diagnostics for trie-backed stacks Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-7-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan When a modeset lock acquisition returns -EDEADLK, DRM saves the call chain and prints it if the caller later attempts another lock or drops its locks without first calling drm_modeset_backoff(). This diagnostic currently fetches the saved stack through stack_depot_fetch(). Persistent stack depot saves can now return trie-backed handles, while stack_depot_fetch() remains limited to hash-backed records. Use stack_depot_snprint() to format either backend. Preserve the PAGE_SIZE buffer, two-space indentation, warning, and backtrace. Signed-off-by: Caleb Kan --- 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_modes= et_lock.c index 2c806b0146d6..a2ddb02b2aea 100644 --- a/drivers/gpu/drm/drm_modeset_lock.c +++ b/drivers/gpu/drm/drm_modeset_lock.c @@ -94,16 +94,13 @@ static noinline depot_stack_handle_t __drm_stack_depot_= save(void) static void __drm_stack_depot_print(depot_stack_handle_t stack_depot) { struct drm_printer p =3D drm_dbg_printer(NULL, DRM_UT_KMS, "drm_modeset_l= ock"); - unsigned long *entries; - unsigned int nr_entries; char *buf; =20 buf =3D kmalloc(PAGE_SIZE, GFP_NOWAIT | __GFP_NOWARN); if (!buf) return; =20 - nr_entries =3D 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); =20 drm_printf(&p, "attempting to lock a contended lock without backoff:\n%s"= , buf); =20 --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D0B3941D63F for ; Mon, 17 Aug 2026 12:43:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970590; cv=none; b=s+ge8+PdxhPSFW+abMiEaQtPcUEaAI3ZMU4XJJxMz9sJ6ZJwxk2VNjlkC5XJxwTxwlix4MwrSi2a06dBQUoTRSsb9Fz9e+RVBbuihR8mg0J70uoDQjCxY3xrNlSOU5hiKW+cY7OQsGFGR/ihW8D6dF8AQBXng/A7XvDIQgwSQoU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970590; c=relaxed/simple; bh=hXSxB88HffoakItr/FZbk2oDQISod625nOxGbRtEfbg=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=NIzVH8ntC3OEPY64/Ez0JnRLZE620OzKLvXiTavXSgvqwmeBn0dwtw/E/vtRAU+IOHaog7uHdw86vojVHRmUmWnkdMTfkKex2hNs0huIFOwm97QG+6cfF8v7LssrPGELTPdYM5YvX6T2EBZgGfXWzJ06odT7/qCtvk1sfQioaUI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=jJFP9fzs; arc=none smtp.client-ip=209.85.208.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jJFP9fzs" Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-6a38098734bso4800504a12.1 for ; Mon, 17 Aug 2026 05:43:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970587; x=1787575387; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=9gAEJlNZVcNXMblqkUJuiyVruC7lTjyCbl+Qw91/T4Y=; b=jJFP9fzsPoPziy2SSp2kE0r8jQWEsZTG0KMz0MULv0yKwNvSyZaeMnsDJzlQRHNUjp i2+Yi0K8vwuv8VOIgHRsGCI41UEprU/n0Y2vSuFJ11cCW604YNUMlv4WTucF0rCd2/D7 LPAOZcDy0XRqKWgLUzeNFiDBIvDRFAG0DPWTW0pjySWSV+Jn4zCht5rVh7hcNrD+YUgn WxSncia8FUlUWbhmaZXkOD6SdcwXSK5Jo8SjtK5UY2rcNuvxHtyXpGvYC8urNW3pUZ1B H4LuttGi/yLhH9JbChai9KHU3GLGyixrHBBwzvs4NlhC48k065KTFXFAKYG9yRKxnQ1v t7Gw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970587; x=1787575387; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=9gAEJlNZVcNXMblqkUJuiyVruC7lTjyCbl+Qw91/T4Y=; b=YnMPoETZ2b7zP5KBYp5sb8ktp2u6SohZuvGFiLyKI4fGa/qN7SvpG+hYtWhZpkiTnk D6sGKRFOfz1yZztVRmm4+EE1eSSSLPXWuObTWEDPEcYVmJMwFd465Dizl1JEkN3d13Q5 PnN46fbnY2OeOl7eQ120il7jBWRXiETqyWk2T7aD47TATfToO07uqy7Ioltz/PdIHaPF OD7vgBmW9bLgz8SySk2iQvEZW3f51xZZev8j9Eh8h1DbRJqk7sNPnFINoGokmxBVEeTp s3fjyVTLm4WQ53MEhjjcPKBZLffWNzjMas6enCEdT9JZEfhjQubyQaHvzIimpqkegTIy SPjg== X-Forwarded-Encrypted: i=1; AHgh+Rofo+LogadBxU4yaOJciUsz4rKd/GHiZ1rrh05GBTMmIEDqby5theVPXoSUlFOjrz1aVZNaSKl6hx7e29s=@vger.kernel.org X-Gm-Message-State: AOJu0YxAcYfIGgpdzcpYLNhLBgXKCJy/cIHQLNla+D3t9oyYXexahDWy bkgFuflMLxLfT36I+sdhTl+vo1OMIumTbL0VLDlAdiFgDU7N793dXEMh X-Gm-Gg: AR+sD13tNKl+0u3xrZ1qHKWIeA5+Xt8M3Sx14+PlLWI3KPLeJSpCZq7424xFywqoFZj fspcsGjOORDJfLhIjsw8YOKw4eHdJV8ErcDGBEOdYZ0E1PtM8hTeOLgVGkmlhv2vy80rTy0gUwA zhHo9UAkyans/Vyrzxy+Mp4d9iPJI3XPmu9dVXfzMYis66EZ3hGyfUf8Sd9Vo1XtQNFYc/y6gzc +0anZgsczsGXd+WzqqNwryTrG3btgw3+lBq/WtxEpV0SoXq4YRxVvwY4GcsS6n43esG804IeeUr Gvh3OlBy1PGWVOOBLc7abir0jQUnhwnZE8UDd4po63YBn9iLw3BHLr+9ML1rR9+SHp517qRa0fG U/2MDrN5ySNR5frf6i3CESOpgxMTMc++onNQVPV+hQk+6jyP98G2Wm9xXdMKGEn3bcN8Yfp8ZSU wrKOE/7PxRs4CT47+ur7lpX5d/7/dTKjUW8Hd8P31z++s3eZArew== X-Received: by 2002:a17:907:e1d1:10b0:c20:1bc5:6ff1 with SMTP id a640c23a62f3a-c212a18c668mr795218466b.5.1786970586864; Mon, 17 Aug 2026 05:43:06 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:06 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:48 +0100 Subject: [PATCH RFC 8/9] scripts/gdb: reject trie-backed stack depot handles Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-8-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan The lx-stack_depot_lookup command can materialize stacks only from contiguous hash-backed records. Trie-backed handles instead encode a dense stack ID in pool_index_plus_1 and offset, so treating them as hash handles misreports a valid handle as an out-of-bounds pool index. Reject pool_index_plus_1 values above stack_max_pools before the hash pool lookup and report that trie-backed handles are unsupported. Supporting them would require side-table and parent-link traversal in the helper, which is left for future work. Signed-off-by: Caleb Kan --- 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 =3D=3D 0: raise gdb.GdbError("handle is 0\n") =20 + stack_max_pools =3D 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 suppor= ted\n") + pool_index =3D parts['pool_index_plus_1'] - 1 if pool_index >=3D pools_num: gdb.write("pool index %d out of bounds (%d) for stack id 0x%08x\n"= % (parts['pool_index'], pools_num, handle)) --=20 Git-155) From nobody Mon Sep 28 21:08:23 2026 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B0F2341DDE4 for ; Mon, 17 Aug 2026 12:43:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970592; cv=none; b=VxOWcWMwm+w3vAHGz/v56Jht06dekH/2NTSZDvlbX3icIl/cfMVbXMfxqLWfzyX4bqJbofyMxCYJJ3QnGIAS7JNrHATt4BcJKzjbcGxp8VXW+szdYiGhPZydgyOF7a0eWySjkg4Jd6neaM6ZmWJGbLRGkfuzs0im/XW3MdbliwM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786970592; c=relaxed/simple; bh=OhqGYzOOkx2OUOWbEylHlwtk71aCWuaxYpNokA4l+LY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=MBOne7P34/0Maomajjy7WaT7D3dEtjXTwpHSZHlDLbabg8mBdARqoROhFBMiNvSnUY6KH6I6SeNEMrrWXdjzgpaAuUI/pFsf+gWgyCNEFL2x2OlmOFNQ/8L6jjFxX/+EmiC4CyOsbGujWmLmL5qNLodLRpU0mdH+EaMPR/O+ORc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=h0oSRTVg; arc=none smtp.client-ip=209.85.208.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="h0oSRTVg" Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-6a374bea882so3024650a12.1 for ; Mon, 17 Aug 2026 05:43:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786970588; x=1787575388; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=MTB1+FCNUBbtk/wxJTJyqubMSGpfxVMNiUg/WWAjSjU=; b=h0oSRTVgf5CIw2bH/vE9mq6fkL73C/34HiMSbzNH/4cGLYiR0ucpTdYUlq5zL02MGT XBsQZXU8D4Xg9qevRWY+yaXqP/VU5sHgRHYKuC3SJcBMsrr1SgycXN6AWE0vK+1mVZwg VZsfhimCmzOWxNHQ/IvFLIxTeZqoF3JOldK+R6zda9UwdOYO4Z754c/DAid6J/YChz7D oBNP2+7bNzJG6H4bSQwRejtuxDwczw7U50G9xnDvgLINN7xN10dQQZsshtP9dN7johpH YWGNNcYXkrVm+gWnLnb1exdrEQGQeQMhGQB0ShN6+T2EZjU9THPYSqInQ7+2/gsyoDXG LMWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786970588; x=1787575388; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=MTB1+FCNUBbtk/wxJTJyqubMSGpfxVMNiUg/WWAjSjU=; b=ZVBNSp4aozFf3cpAOyIbg0346cosU9b0RS/X3opfBM98srNEj7ZIwUXQp4hwFQjwdG /zpqT3ZZs06p7Fm+/oAykOM0JmIC5dl+I0Nh+ENGTM3VEW8SHOBFgNro86SSpT419ROu 8nLIfFSVxpfzNAbVTbFwu0hgiZtAupEnQXePQqJqZAij0anzZ4OPZTL90GjjICTifynk d//1PW9lcDXmFzaQ3MzkHouAD8SKK2XFuCV+0HvbMjUvjvTTI9LXmfjBa1MSa1zegNJd AID53xOR2+1cfrbIHnhoY9WcxopkWNvPpg8gtPukWnwNwO8tjC5pfX3ZwRVgh/YL1pIC F9jg== X-Forwarded-Encrypted: i=1; AHgh+RpRJEMTSORu3be/dkPKuSM9IrfxarYmhFG+XSJ/Rpc+OsBtIDHpLvD84Ou5c3IcKH5jf/PSK3rFqwJBUoE=@vger.kernel.org X-Gm-Message-State: AOJu0YyVxT4AsPhX/pG8cxOWzKmrShjol9+eo7pn8WkdKng/9KrI7VPj QMwo5iid0ozjh9ho22byf145/3GAE57FzcmbEFvwt5mzqvacGbYI8t/2 X-Gm-Gg: AR+sD13i/j3xk8V0S498saU4E/TyTOQ60muX/0tZ6ybiMPr6xToZ3VZFE8hlRts+S5N 48OcJDBdv2byAbcq5xvH9kWEnPyf9x+M9Lr64g8ck+xNpL9ia/TYDIutlz8jHmEwuCFBJs286Qw /UFJvOVUDwl5cyQ8P0VQqPO0NXU0wKrSKNrmm24P/Gf8ZVaNdjHwXE1VZG9HX4oiT1KIW6M514C qowDq6E0vJF7hgsjsEezizqUkTRIeh9jznNccq2Nl0lMTSuoYA54c9mUJIWoVXQzesDqkRv952C SfOV5FYY3DWGeRhdQ+zyVj8599nyFJOxY8zBj82WogVOnW5LMzJso7gfPE1zruPNznUEZExqYHM CZojDS19TPgINPMYwLrFGV4fjI2/QBCY2k8erkVWe2+Saa9NWyFAvXNxi8d3n2GYytK8q5Cz92u bI0nAMZqtyTXLejyer/9isBo274DmMR3nmF3KzUqS/fN84yfDqDg== X-Received: by 2002:a17:907:c788:b0:c15:d0b6:495c with SMTP id a640c23a62f3a-c212a2452admr1247772466b.29.1786970587948; Mon, 17 Aug 2026 05:43:07 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:3861:1e5a::306:a]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c217feb99d4sm52626266b.22.2026.08.17.05.43.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Aug 2026 05:43:07 -0700 (PDT) From: Caleb Kan Date: Mon, 17 Aug 2026 13:42:49 +0100 Subject: [PATCH RFC 9/9] stackdepot: add boot-time activation for trie storage Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260817-stackdepot-trie-v1-9-53870ca1651b@cloudflare.com> References: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> In-Reply-To: <20260817-stackdepot-trie-v1-0-53870ca1651b@cloudflare.com> To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com, Vlastimil Babka , Alexander Potapenko , Marco Elver , Dmitry Vyukov , Andrey Konovalov , Oscar Salvador , Caleb Kan , kernel-team@cloudflare.com X-Mailer: b4 0.16.0 From: Caleb Kan Trie storage cannot be activated while persistent stack depot consumers can pass trie-backed handles to hash-only access paths. The preceding patches make those paths backend-independent, keep the corresponding saves explicitly hash-backed, or make the GDB helper reject trie-backed handles. The trie can now be activated without exposing incompatible handles. Add the boot-only stackdepot.trie_enabled parameter. Keep it disabled by default because lookup-only constrained misses can lose traces and the GDB helper does not decode trie handles. Guard backend selection with a static key so the existing hash-only path does not take a normal runtime branch when the parameter is absent. Document the parameter and its handle-namespace requirements. The available trie ID space depends on stack_depot_max_pools because hash and trie handles share the pool-index field. Configurations that consume the entire field cannot enable the backend. In particular, a 64 KiB page configuration using the default maximum of 8,191 pools must lower stack_depot_max_pools to leave trie ID space. For early stack depot initialization, allocate the trie side-table root, first directory, and first chunk through memblock. For later initialization, allocate the root with kvzalloc and grow directory and chunk pages lazily. Enable the static key only after initialization succeeds. Treat trie initialization as optional. If the handle namespace is empty or metadata allocation fails, warn, clear the request, and continue using the initialized hash backend at its configured capacity. Hash and trie storage continue to share stack_pools and the configured physical pool limit. Pools consumed by trie slots are therefore unavailable to refcounted and countable hash records. Once enabled, saves without STACK_DEPOT_FLAG_GET or STACK_DEPOT_FLAG_COUNTABLE use the trie. GET and COUNTABLE saves remain hash-backed; trie-eligible saves that cannot allocate perform a single lockless lookup, and per-save trie insertion failures do not fall back to hash storage. Signed-off-by: Caleb Kan --- Documentation/admin-guide/kernel-parameters.txt | 7 ++ lib/stackdepot.c | 100 ++++++++++++++++++++= ++-- 2 files changed, 101 insertions(+), 6 deletions(-) diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentatio= n/admin-guide/kernel-parameters.txt index 1af62cd16c9d..ebb7b7e1867f 100644 --- a/Documentation/admin-guide/kernel-parameters.txt +++ b/Documentation/admin-guide/kernel-parameters.txt @@ -7387,6 +7387,13 @@ Kernel parameters stack traces. Pools are allocated on-demand up to this limit. Default value is 8191 pools. =20 + stackdepot.trie_enabled=3D [KNL] + Format: + 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. =20 diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 1e5b9fc44618..1a002063a948 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -28,6 +28,7 @@ #include #include #include +#include #include #include #include @@ -100,8 +101,8 @@ static const char *const counter_names[] =3D { [DEPOT_COUNTER_REFD_FREES] =3D "refcounted_frees", [DEPOT_COUNTER_REFD_INUSE] =3D "refcounted_in_use", [DEPOT_COUNTER_FREELIST_SIZE] =3D "freelist_size", - [DEPOT_COUNTER_PERSIST_COUNT] =3D "persistent_count", - [DEPOT_COUNTER_PERSIST_BYTES] =3D "persistent_bytes", + [DEPOT_COUNTER_PERSIST_COUNT] =3D "hash_persistent_count", + [DEPOT_COUNTER_PERSIST_BYTES] =3D "hash_persistent_bytes", }; static_assert(ARRAY_SIZE(counter_names) =3D=3D DEPOT_COUNTER_COUNT); =20 @@ -180,6 +181,10 @@ static_assert(STACK_DEPOT_TRIE_POOL_FIRST_SLOT < STACK= _DEPOT_TRIE_POOL_SLOTS); static DEFINE_STATIC_KEY_FALSE(stack_depot_trie_enabled); static const struct stack_depot_trie_children __rcu *stack_depot_trie_root; static DEFINE_RAW_SPINLOCK(stack_depot_trie_writer_lock); +static bool stack_depot_trie_requested; + +module_param_named(trie_enabled, stack_depot_trie_requested, bool, 0); +MODULE_PARM_DESC(trie_enabled, "Enable stack depot trie storage at boot"); =20 #define DEPOT_POOL_INDEX_MASK ((1U << DEPOT_POOL_INDEX_BITS) - 1) #define DEPOT_OFFSET_MASK ((1U << DEPOT_OFFSET_BITS) - 1) @@ -236,8 +241,9 @@ static u32 trie_stack_id(depot_stack_handle_t handle) /* * Trie handles encode a dense stack ID. The side table maps that ID to a = node * pointer for lockless fetch and print paths, which can run from diagnost= ic - * contexts where taking a lock would be unsafe. Additional directories and - * chunks are published lazily as stack IDs grow. + * contexts where taking a lock would be unsafe. Initialization installs t= he + * root; early initialization also installs the first directory and chunk. + * Additional directories and chunks are published lazily as stack IDs gro= w. */ #define STACK_DEPOT_TRIE_SIDE_TABLE_CHUNK_SIZE \ (PAGE_SIZE / sizeof(struct stack_depot_trie_node *)) @@ -375,6 +381,75 @@ trie_side_table_prepare_stack_slot(struct stack_depot_= trie_side_prealloc *preall return id; } =20 +static inline unsigned int trie_side_table_root_size_for_max_id(u32 max_st= ack_id) +{ + unsigned int top_size; + + top_size =3D 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 =3D trie_max_stack_id(); + if (!max_stack_id) + return -EINVAL; + root_size =3D trie_side_table_root_size_for_max_id(max_stack_id); + root_bytes =3D struct_size_t(struct stack_depot_trie_side_root, dirs, + root_size); + + root_vec =3D memblock_alloc(root_bytes, __alignof__(*root_vec)); + if (!root_vec) + return -ENOMEM; + first_dir =3D memblock_alloc(PAGE_SIZE, PAGE_SIZE); + if (!first_dir) { + memblock_free(root_vec, root_bytes); + return -ENOMEM; + } + first_chunk =3D 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 =3D root_size; + RCU_INIT_POINTER(root_vec->dirs[0], first_dir); + RCU_INIT_POINTER(first_dir->chunks[0], first_chunk); + trie_side_table_root =3D root_vec; + static_branch_enable(&stack_depot_trie_enabled); + return 0; +} + +static int stack_depot_trie_init(void) +{ + struct stack_depot_trie_side_root *root_vec; + unsigned int root_size; + u32 max_stack_id; + + max_stack_id =3D trie_max_stack_id(); + if (!max_stack_id) + return -EINVAL; + + root_size =3D trie_side_table_root_size_for_max_id(max_stack_id); + root_vec =3D kvzalloc_flex(*root_vec, dirs, root_size); + if (!root_vec) + return -ENOMEM; + + root_vec->dir_capacity =3D root_size; + trie_side_table_root =3D root_vec; + static_branch_enable(&stack_depot_trie_enabled); + return 0; +} + static int trie_side_table_get_prealloc(gfp_t gfp_flags, struct stack_depot_trie_side_prealloc *prealloc) { @@ -702,7 +777,7 @@ static void init_stack_table(unsigned long entries) INIT_LIST_HEAD(&stack_table[i]); } =20 -/* 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 =3D 0; @@ -776,11 +851,15 @@ int __init stack_depot_early_init(void) stack_depot_disabled =3D 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 =3D false; + } =20 return 0; } =20 -/* Allocates a hash table via kvcalloc. Can be used after boot. */ +/* Initializes hash and optional trie storage after boot. */ int stack_depot_init(void) { static DEFINE_MUTEX(stack_depot_init_mutex); @@ -834,6 +913,15 @@ int stack_depot_init(void) kvfree(stack_table); stack_depot_disabled =3D true; ret =3D -ENOMEM; + goto out_unlock; + } + if (stack_depot_trie_requested) { + ret =3D stack_depot_trie_init(); + if (ret) { + pr_warn("trie storage initialization failed, disabling trie storage\n"); + stack_depot_trie_requested =3D false; + ret =3D 0; + } } =20 out_unlock: --=20 Git-155)