From nobody Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f42.google.com (mail-ej1-f42.google.com [209.85.218.42]) (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 954B65293F1 for ; Tue, 8 Sep 2026 13:13:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873244; cv=none; b=TFoyxWeahnUW7yJWX5XOvr6i1Cjv8YhLblrMw/ozeUzHmg2qPLDdjHMHTVZjytrmeDnu01A2bqBWXUGctUWSa95+aFrd7zM3itvO3Pj1DuQAd5Hjtu5W3jlqJZHuggja/2+TeiWgfRfGLaPxFe2SGzbzKWNlmJLDjpPPAgL+6X4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873244; c=relaxed/simple; bh=FYqm+GsASgpEWtygiWMiW+youctcu6LAF2/V64dk65o=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=EqfwEYdY23dfzuB8lO5RURW5Z3wmhy0Nzr0rcZyLGbm4e5xKMmDT2+xaHE+NG8YTJUgKHSevhF9UnlimrwssghH6m2gfzAW0EaAuqx8iRjlzpi1uXq+r3u4L/jgcQPUuISomRxVvq19271uL9p17accqBUjUGI41k9Oup+b9L3o= 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=Px7+P8fU; arc=none smtp.client-ip=209.85.218.42 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="Px7+P8fU" Received: by mail-ej1-f42.google.com with SMTP id a640c23a62f3a-c20e70a0962so585555966b.2 for ; Tue, 08 Sep 2026 06:13:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873232; x=1789478032; 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=45/BFWfpuwLvqqEgE/wDbYZ6sfAlzPF75sDMeqn5VJA=; b=Px7+P8fUviPYHmOOYO1Vhvxjj2V2SeBraW3b0/cz5tYxpjaH49Abh1+PL7mAWbV48o a7rfgrjEOB+FOdZgbMoocp71zmPWawMIUvpnxI0nXJOfv1PqoCy+VnPCK+ZOARIMiO/O z1N/dExphleylTYQVGXidEhnC/c8oa60qHCYtpeXm0/fWRU5WQW5ZVmu+M+4XhzppwUA pWc/eZ01lbc9wSiuP6TXmVqehx9/emmgVEOcndnlNRGdriYmwOq1+Ced0BkFqYO63A58 9kz91Xuu1gG/hJab3Q8Z+XEL1LZjp6/D1wKukad/Xw1x05XU66IjCGahYy+Ef+oLOsBU piMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873232; x=1789478032; 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=45/BFWfpuwLvqqEgE/wDbYZ6sfAlzPF75sDMeqn5VJA=; b=j8lhcNqs75MMbhSXial27cf3mrk4fg2X2m73lqR3wz/d6JJribNLNlY7Ix4xOhuffH rsv9DrAONronumZb/G9h6Xb/y4oOyZ6F0RtQh4I5TIqCQ5sO+L796jzdqkfwobUf3AoT 8PCrqCcFndMKoVKGDeKpynxwT3Jr1Va/8FZ74Lu2Cr38hS3PCc0m5QwmCYJhNBK+ttCc h7TOtDTA2iowboemSa+qfolGWKn50u4BxPP8CkkZkSFlTWWvqVcd3cg+FVJTwHTcmN6j W+lajdi9plNd3aWtVDGldsWnFYMrB8j6ewWFNyQTeAuLPKI9V163APlYBLtUBZ4CmqHR FAuA== X-Forwarded-Encrypted: i=1; AKwUvBw4al24XEVUuD0+N0wnL/3bX2r70A6HfISVPfdOMC0+UbFcfC+fH2OQmlqxulbXdogsP139Z3ccadzHcKc=@vger.kernel.org X-Gm-Message-State: AFuF++kZwVTqYiSHXUQWjuvspTB7Sa3uWP5Y4UFzPngvjHV2KvvM0G5f 6GFpqG5fZRbntkRsVk4qz+3QWEmzxRCeK9w5v9sCSnlqBvyf01O91gOJ X-Gm-Gg: AYBFou0x1th1pnjnXhOm7xWcz0HevvqPCrwNdFnV5TBJQDzhYn6QMfXy5dpzSkvsm41 1oTrW6DbHgmT6uiDMVwQMQ6CZnVwkmLtseXeVNa2gdrKUAHB2wY06LVtfpRPqn55F+tu8BxZNZQ VVPQnPQBbIBevoHt8n+CzJRUIfiAiRqEjEwt1sClBlzKaTrqgpol1jVvv92aWfiBmLEPGcso/Uu KcrzQ7x6qIbN5sl1eMzMnhz4aFL+SUOuvdjk+G4HZXZLAS2qZ81ZuIl9fpRYx3qwIeihoXHfW9y 7I3rgo1JQSMe6VQAyhtJeKIb5+cweOpfYDDfmyiKp2jHIGoBDiMPsv9435Sxsb5DMZm3gLl2j4e I8NQpvgSu/j2FwUf6QU3SOViUaWr5XVWnt428rtuR1s4yjWW/Ft1uzf+D3bv16hRMnZ39cNzRJo +MiYIUNLl9XKvDy50QQ6Np/7TN9t7ie9j1bAHAC+kn/hUvd1I1EIE= X-Received: by 2002:a17:907:9490:b0:c25:c7a9:7b8a with SMTP id a640c23a62f3a-c260c9dfc11mr2001513766b.12.1788873232277; Tue, 08 Sep 2026 06:13:52 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:52 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:34 +0100 Subject: [PATCH RFC v2 01/11] stackdepot: stop preallocating after the final pool 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: <20260908-stackdepot-trie-v2-1-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 depot_init_pool() decides whether another pool is needed before it increments pools_num. When it registers the last allowed pool, pools_num is still one below stack_max_pools, so the existing comparison clears new_pool. With new_pool cleared, stack_depot_save_flags() can allocate another order-2 pool after a lookup miss. depot_keep_new_pool() retains its pointer in the global new_pool, so the allocation is not lost. However, pools_num has already reached stack_max_pools, and depot_init_pool() rejects every attempt to register the pool. It remains allocated and unusable until reboot. The non-NULL pointer prevents later saves from allocating more spare pools. Account for the pool being registered in the limit check so registering the final pool installs STACK_DEPOT_POISON and prevents the extra allocation. Fixes: 31639fd6cebd ("stackdepot: use variable size records for non-evictab= le entries") Signed-off-by: Caleb Kan --- lib/stackdepot.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/stackdepot.c b/lib/stackdepot.c index dd2717ff94bf..90c52f2e0d3f 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -323,7 +323,7 @@ static bool depot_init_pool(void **prealloc) * NULL; do not reset to NULL if we have reached the maximum number of * pools. */ - if (pools_num < stack_max_pools) + if (pools_num + 1 < stack_max_pools) WRITE_ONCE(new_pool, NULL); else WRITE_ONCE(new_pool, STACK_DEPOT_POISON); --=20 Git-155) From nobody Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f51.google.com (mail-ej1-f51.google.com [209.85.218.51]) (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 53CE05476F8 for ; Tue, 8 Sep 2026 13:13:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873249; cv=none; b=PSf5Wi4Kpy8lgS7Ps46S178Z4yLkub+OsLrdfY+IRCGokFVk6JFiqyCxolfMPonSxOJfWT4bFNepYWWGOnpr6bgqD30sd1zRPqorm75/6ZJ78zJtj8nY/JjqlwZsHfV/3rEGr3R4ncttXMAPkNeKYUxqLJYxNU8mWL1ZdnE4CRE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873249; c=relaxed/simple; bh=qNTAB7oPX8OED8WnXC4Pxiv687JkKcIW5xcsxDNCZJQ=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=gP7CAGmKJMGPHnogv2ll8A2D8ppp3IQWUdRm9aUtkMv8QPZU34Qiz0Da9eML3+yBrxEJ/gWrp6tWkBzG6VdZ+jqjQ1N/+jhc2xizrnfXBLc2Ezo2HrhcW+U8DTH0NyqY9mYsDXPYOvXxXedjLH+dPLK6N/GOxJ7eBgaIi5KhBKQ= 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=HhPNSZOY; arc=none smtp.client-ip=209.85.218.51 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="HhPNSZOY" Received: by mail-ej1-f51.google.com with SMTP id a640c23a62f3a-c2637dd37c1so354866866b.0 for ; Tue, 08 Sep 2026 06:13:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873233; x=1789478033; 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=s5+uH0xlKN2hEFrP0JeeUp1z2fKvzaAC1oyZ553cvDk=; b=HhPNSZOYH8KNvW2ywhy2FVQN3DGSRxkO0X9np8iSepnXvleOCdiPbDyAqe/IynYo6h O8+kvMrKifJRPo9sCXv/X+/fKAB8Hq5fd2IiBU4rXRXDJrXd7dg81t7v7EQGEKVMJzAH jyKVFR8CVpSiT7y/B9ZCYKxoz2tBuHV3SNzx+32XNuX4epoD8Qcj5WCWaAt6bsF53byu yNLSz/vT0ngmEouZUKX4+IUTSTmsp7dewRscC30S0nfqo33S5NwtAebSnE0tYeiAy/Fe QxmZt4gCPZgxf3uxhfJS+MBdX/CKcg2MjXhmFgmoHAJwNkhkEcBVNvIQasp6AQqlz1rx yzAA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873233; x=1789478033; 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=s5+uH0xlKN2hEFrP0JeeUp1z2fKvzaAC1oyZ553cvDk=; b=U8CYylk/MLxIbLe5haV1hNZv2LE8pslD0InEIjKaEvtjCx/D5R/jJQSNg1FuHIoEwb +jRL8q1O9JnpC8vTOO8jPKp7dcC1eSHbB56OZBKsZOYJxOC0STAPWnbGCbnWOEICB+G/ K3quT7I+El9CuY0e+JiAWHCsVy/x7jJwBa1L75BkiOqog/0ns91mCduqC2bP9g5cnAi7 dmG27KJ9PLIlGRkzptVunjlY1jgiKnXeE91tW/3qroFmsBQ75nCzlHiCKWDvkR4/+nPF fBLhJQWXH+lSWUHFpHtsWi8EfaM+kfuu59wVnok9WP/ZaQ9zYW1jwzilHyBl7hMYMIZq EddA== X-Forwarded-Encrypted: i=1; AKwUvByE0yF7PbJjKJacki3I++T03tdnlQuMnUH0A9u5xEjHnxIW06Fo5QHYyeJtsIvDgu4dDIg4Q32S4lPwGZo=@vger.kernel.org X-Gm-Message-State: AFuF++lbgjM0gV1HMh6dfwr8xhysBQX1jUchx533+EypYEbvN/QhaCc6 GQhlzsFIsTY3Lcq83NdGtATvtUnmYnDZfeqfJSvl45rqvRBPhVTIgY6m X-Gm-Gg: AYBFou0miPsDa8LpTTKfXuKgUkg0BsmaqY5pwbS71gnyEtnvkL4ssXz1R08g0mq0LAl 17QbqLF58AhEmVcniBNUFu5IgqMsgLp0x0HWr/VsPgoA03GpptlK1xyMMV2nFpdz1UfvEuQxz/a H9BN7m73xfUs2B7Ht9Vbo9Cd7U/xcBk95yokCFnRM27IgHFKWkzDa1H+rrSQFoGZKI6KmUw5KfJ WmYUxYbbUHWV/s9VSCB1oaW4PDh3wBRMie5p2Mh4VlQtNaYVE49IhlioTvkHN3zbDBllzFgLWRh ShGVPvjMpPa3rxdXlFgSQl6JV3mGJe17cEdrvWtp5gb/k2V+bSnbA5Onaq2gU/3WwShAlAAAzO8 rzLZWPj7ShWV9Zox+wcdmGGNgJP9vtQ+N7c7baMUi8O52TZIWXfalf/toT8xnd8gGubLxGSfXRB QyUxNmSG7FPmfodiL9uAMV0E8sKLt6XfQMMcPYLUb1ljLZH3afaw== X-Received: by 2002:a17:907:7281:b0:c25:cb7a:12d6 with SMTP id a640c23a62f3a-c260c9972aemr1109763266b.14.1788873233006; Tue, 08 Sep 2026 06:13:53 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:52 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:35 +0100 Subject: [PATCH RFC v2 02/11] stackdepot: add caller-owned stack trace fetching 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: <20260908-stackdepot-trie-v2-2-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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_fetch() returns a pointer to contiguous storage owned by stack depot. That cannot work for a backend whose frames are not contiguous, so callers need an interface that copies the trace before they can support both backends. Add stack_depot_fetch_into() to copy a complete trace into caller-owned storage. Leave the destination unchanged when it is too small, keep a zero handle as a no-op, and document that callers must keep the handle valid while copying it. Warn if a caller passes a NULL buffer or zero capacity for a valid handle instead of treating the stack as missing. Unpoison the copied entries before returning them because lib/stackdepot.c is not instrumented by KMSAN. Add built-in KUnit tests for exact and oversized destinations, zero handles, and undersized buffers. Later patches add tests for stack depot internals. Signed-off-by: Caleb Kan --- include/linux/stackdepot.h | 36 ++++++++++++++++++ lib/Kconfig.debug | 16 ++++++++ lib/stackdepot.c | 28 ++++++++++++++ lib/tests/Makefile | 1 + lib/tests/stackdepot_kunit.c | 89 ++++++++++++++++++++++++++++++++++++++++= ++++ 5 files changed, 170 insertions(+) diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h index 2cc21ffcdaf9..734529767c8a 100644 --- a/include/linux/stackdepot.h +++ b/include/linux/stackdepot.h @@ -199,6 +199,42 @@ struct stack_record *__stack_depot_get_stack_record(de= pot_stack_handle_t handle) 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 * diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 134b15a44625..fcd74edfd93a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2785,6 +2785,22 @@ config RESOURCE_KUNIT_TEST =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, so KUNIT must also be built in. + + KUnit tests run during boot and output the results to the debug log + in TAP format (https://testanything.org/). Only useful for kernel + developers running the KUnit test harness, and not intended for + inclusion into a production build. + + If unsure, say N. + config SYSCTL_KUNIT_TEST tristate "KUnit test for sysctl" if !KUNIT_ALL_TESTS depends on KUNIT diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 90c52f2e0d3f..4da7279d9f83 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -785,6 +785,34 @@ unsigned int stack_depot_fetch(depot_stack_handle_t ha= ndle, } 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); + + 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; diff --git a/lib/tests/Makefile b/lib/tests/Makefile index 3cac3b63a752..1f72191f98bb 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -48,6 +48,7 @@ obj-$(CONFIG_SCANF_KUNIT_TEST) +=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..b0c44c096976 --- /dev/null +++ b/lib/tests/stackdepot_kunit.c @@ -0,0 +1,89 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include +#include +#include +#include +#include + +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 struct kunit_case stackdepot_test_cases[] =3D { + KUNIT_CASE(stackdepot_fetch_into_roundtrip), + KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack), + {} +}; + +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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f54.google.com (mail-ej1-f54.google.com [209.85.218.54]) (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 9E2C955D898 for ; Tue, 8 Sep 2026 13:13:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873246; cv=none; b=fFECSdKqP9l74IGHS11D0wbGJsz7PF2GVgoXzMK10ThUqOMWS++OcNLohu6Gh+M4JHU+An6WLXhuBAm6p5c0R98Va2VleXse6SUSs05vyxR/DibUjDI0wIIWeguJR7gLUnAlGKvsQ6rwiIbqcY3hrP6gkfBsOexpCSkFqmakg50= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873246; c=relaxed/simple; bh=JuqB+ahMRY2MYOuYVspkxDoewP+Aj8jfvUSogE3zVcU=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=VTotrQ6/5332Hmzl7iahtgNLyhceZLsTIhl2iDOuwWTvnO24w40McrWtkoVFnmTNeXkHS/9N1VHjOa0a9weedjcLeRqautkQo9lx+fWfL9+f58HvkqzMRSLcg49/a+MrU6VnTOwhCpjvzzr4igFZ+M4ip8xfvPxXdbWcr/ruOXs= 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=o3LBq1ei; arc=none smtp.client-ip=209.85.218.54 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="o3LBq1ei" Received: by mail-ej1-f54.google.com with SMTP id a640c23a62f3a-c250c6a6a9aso762630966b.1 for ; Tue, 08 Sep 2026 06:13:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873234; x=1789478034; 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=bplnJXOhH88sJS1R74ulrkJBYzyAx2Jvgtke5umuzc4=; b=o3LBq1eiG5PQ614QfGkuZkc7jVO1smW9WY8GjWkMO1Rr6nLSFrf8eoD4zvWa2j/iwc 6Aj9PinHMW5b5JqlBEBvulT20/3Mr1Ka9r9QgY5z4uzsRCsaoupG9WWuTyCylGWSp7XR Vjsi+elMk3++gMEbr4Qqom/RLVebp0ktpWHtIGgYrdxqYvhI5hKFRf9TCenw2/fnqBmL ioDGx7EJh56q4zHw35XtbA7aFH3VJYtieyVt687F8y/GOnvP4sgT48yWUs0C59q9sP6Q MdPBkKZAb1wUiFa7ZRHKJ1Rux288wwTm/JZzswYkzUbYYWCGB2I/va9XkFpy3Lp1iaC8 S3+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873234; x=1789478034; 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=bplnJXOhH88sJS1R74ulrkJBYzyAx2Jvgtke5umuzc4=; b=kvN6S2RWPF+jLeUBCRjmjLijGHaY0ee0biveTA/s5U2apJVahTQKWRFmXVpjRGqWOO lxOYaWTc0HTyz0l1WNOYOlk2IKJJPPbiX4kXEzv3+3kZc4BtKQ6ZyvYY48UZuMHSSPrT HRejRUamHP7OY+F/gthnrI+3Ses9LSQU32jWcEX4JOwqxyCEWgeADYDtOtUonjx2YYQg IJi3+udWrIsQBKVpKUVBITX3b5JT3M/FUoiNpNDyU97kqlJ+GqwLBLD4iJqOu5nL9zOK /bn2hDcT+3xYJYY6R0HkHo96Afg6QB9XagGdOMD7u+VRjWlOoUG0kySibQ2/3E1qPzRY OJVA== X-Forwarded-Encrypted: i=1; AKwUvByJR40fNdPI2tzEN1Y9NcMS6RvPBQZbRBW7iG8oZVhQiPCu5mM3ACM6IPPHQWs8wdVXdOhylJ2QPPGJRRM=@vger.kernel.org X-Gm-Message-State: AFuF++lreoVTqSNnrA2jJ9aiyitWsbuhx/UGGAdg50eqKrmZeKhpfsXc BRPaEYod/d8WsPaXHnnw7j+D4lJNG3Oxdw6J43GzO4g8YxxRAYcB2qqq X-Gm-Gg: AYBFou1dUpk9g9bP43ewn/YUpbQ1h4F/CRY3YLETkaVsVphk2T8vINBTCnTrSStV7mm 08wmKthlHaoMopPVb9CFJX/ePpnv9/re+IHEoBOXLlslomOqT9xkBQHp0dhxQA4LkZkSzeUbnbP KPEGZjJwJ0XfgIdeMfc64EVDLk91XGEFXUPxsbcJI386LnBC5yVRu6UBq0BOzIHKKkq5F6Ufa2p 1tjFGKAbe4tFa4J3Bg016ksB+nv60fejpoh84TlBFrTcjoLfXuYlnN1s8TjDZNV4MzQNCMgbDy7 DKplcZQv+50cSsWkRIVxQjuaN6zuuTMbIT2vv0zfhtLP4hmJPDiuONZmnS/0KDx9FaSnnq6+4EH ODWXQKMVmjNqGivrp4GvOxaOLib4zUIrHHziGktHO0usNf0jKpOeXesUCCXF/wVJSVqKHWZtXuf bOD5qUlrdIy0lff3jkhunfTDFDAGu7iphOLQN9QMNo+wsvAufXRA== X-Received: by 2002:a17:907:c50e:b0:c25:6c9a:88bc with SMTP id a640c23a62f3a-c260cc0e2a2mr2114388166b.19.1788873233857; Tue, 08 Sep 2026 06:13:53 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:53 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:36 +0100 Subject: [PATCH RFC v2 03/11] 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: <20260908-stackdepot-trie-v2-3-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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. A later patch adds a trie backend, which provides neither a flat record layout nor an independent count field. Add STACK_DEPOT_FLAG_COUNTABLE to keep these records on the hash backend and deduplicate them separately from all non-countable records. Store the discriminator in a new u16 flags field and narrow size to u16. This keeps the record header size unchanged while covering the configured maximum of 256 frames. Do not otherwise split hash-table deduplication: ordinary and GET saves can continue to share records. Make COUNTABLE mutually exclusive with GET because the two flags assign incompatible meanings to the record count. Reject countable records in stack_depot_put() and require COUNTABLE in __stack_depot_get_stack_record(). Mark both page_owner save sites countable so its existing accounting and reporting continue to use stable hash records. Extend the KUnit coverage to verify direct-record access and isolation between countable and non-countable records. Signed-off-by: Caleb Kan --- include/linux/stackdepot.h | 28 +++++++++++++++------- lib/Kconfig.debug | 3 ++- lib/stackdepot.c | 20 +++++++++++++++- lib/tests/stackdepot_kunit.c | 55 ++++++++++++++++++++++++++++++++++++++++= ++++ mm/page_owner.c | 6 +++-- 5 files changed, 100 insertions(+), 12 deletions(-) diff --git a/include/linux/stackdepot.h b/include/linux/stackdepot.h index 734529767c8a..7ff67c70d727 100644 --- a/include/linux/stackdepot.h +++ b/include/linux/stackdepot.h @@ -53,7 +53,8 @@ union handle_parts { struct stack_record { struct list_head hash_list; /* Links in the hash table */ u32 hash; /* Hash in hash table */ - u32 size; /* Number of stored frames */ + u16 size; /* Number of stored frames */ + u16 flags; union handle_parts handle; /* Constant after initialization */ refcount_t count; union { @@ -84,8 +85,9 @@ typedef u32 depot_flags_t; */ #define STACK_DEPOT_FLAG_CAN_ALLOC ((depot_flags_t)0x0001) #define STACK_DEPOT_FLAG_GET ((depot_flags_t)0x0002) +#define STACK_DEPOT_FLAG_COUNTABLE ((depot_flags_t)0x0004) =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. + * * If the provided stack trace comes from the interrupt context, only the = part * up to the interrupt entry is saved. * @@ -178,11 +185,12 @@ depot_stack_handle_t stack_depot_save(unsigned long *= entries, unsigned int nr_entries, gfp_t alloc_flags); =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 * - * 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 */ @@ -260,10 +268,14 @@ int stack_depot_snprint(depot_stack_handle_t handle, = char *buf, size_t size, * * @handle: Stack depot handle returned from stack_depot_save() * - * The stack trace is evicted from stack depot once all references to it 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 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/Kconfig.debug b/lib/Kconfig.debug index fcd74edfd93a..3a78c67b6b36 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2792,7 +2792,8 @@ config STACKDEPOT_KUNIT_TEST default KUNIT_ALL_TESTS help Enable this option to test stack depot API behavior at boot. - This test is built in, so KUNIT must also be built in. + This test is built in because it exercises internal, non-exported + stack depot helpers, so KUNIT must also be built in. =20 KUnit tests run during boot and output the results to the debug log in TAP format (https://testanything.org/). Only useful for kernel diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 4da7279d9f83..66c5e8594566 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -94,6 +94,7 @@ static const char *const counter_names[] =3D { [DEPOT_COUNTER_PERSIST_BYTES] =3D "persistent_bytes", }; static_assert(ARRAY_SIZE(counter_names) =3D=3D DEPOT_COUNTER_COUNT); +static_assert(CONFIG_STACKDEPOT_MAX_FRAMES <=3D U16_MAX); =20 static int __init disable_stack_depot(char *str) { @@ -467,6 +468,7 @@ depot_alloc_stack(unsigned long *entries, unsigned int = nr_entries, u32 hash, dep /* Save the stack trace. */ stack->hash =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 @@ -609,6 +611,9 @@ static inline struct stack_record *find_stack(struct li= st_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 @@ -655,6 +660,9 @@ depot_stack_handle_t stack_depot_save_flags(unsigned lo= ng *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 @@ -751,10 +759,18 @@ 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; =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 unsigned int stack_depot_fetch(depot_stack_handle_t handle, @@ -828,6 +844,8 @@ void stack_depot_put(depot_stack_handle_t handle) if (WARN(!stack, "corrupt handle or unbalanced stack_depot_put()")) return; =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 b0c44c096976..3c526791ef93 100644 --- a/lib/tests/stackdepot_kunit.c +++ b/lib/tests/stackdepot_kunit.c @@ -6,6 +6,60 @@ #include #include =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 { @@ -72,6 +126,7 @@ static void stackdepot_fetch_into_rejects_missing_or_sho= rt_stack(struct kunit *t } =20 static struct kunit_case stackdepot_test_cases[] =3D { + KUNIT_CASE(stackdepot_countable_public), KUNIT_CASE(stackdepot_fetch_into_roundtrip), KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack), {} diff --git a/mm/page_owner.c b/mm/page_owner.c index cfc31c92d765..1fb1998bc129 100644 --- a/mm/page_owner.c +++ b/mm/page_owner.c @@ -119,7 +119,8 @@ static __always_inline depot_stack_handle_t create_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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f42.google.com (mail-ej1-f42.google.com [209.85.218.42]) (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 B92B255D876 for ; Tue, 8 Sep 2026 13:13:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873246; cv=none; b=j1gRJ2S3piaNL8o6/DdLeA2SjHRugKYoMyFngMrhSSktXBEsdLthSFgYe1bJY29exvBFQXloO8U3tLAIvwaapDkX/Cop29oXh5pEsVndnB4q50c8Q55UdGn2Qd7bnGWYyJwXhmmiBbOiHNCeM4raAbcDhEbAD1kMQkKDqEuF39Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873246; c=relaxed/simple; bh=KUMLl8Nlf4ganKmUfRpSqfk9SbXFsUXlAZxjeBAClCg=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=R2TAcPhQfKuIlwmsYQnkB2+DAKmjJTovyc5/mRdiWzYD1y6dOsQH0El8BT3WcivCRizL/4Pmm8r5zneEfdwTAdlXFewoun4b3rbE0gDeABdzxOUR9gz6Oc3pOT5rioBPqa0oYcSr3O4DEp/amfUc5fIquE8tLXe8+X8S9pWKeAk= 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=Jev4xhHY; arc=none smtp.client-ip=209.85.218.42 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="Jev4xhHY" Received: by mail-ej1-f42.google.com with SMTP id a640c23a62f3a-c250f28f1cdso741367166b.0 for ; Tue, 08 Sep 2026 06:13:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873235; x=1789478035; 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=Jev4xhHYniEvbnzhUpYQDjzQioIO7WIey59aJFO6uB9+0oc99TAVPQHI6BysaDkTHJ sa21McQS7Y/vCj5EjkdIysJOPnf8Vw8VL6sTVs6oVtCbwZivSVoUVGoCZDR9y3OFY2R8 3NwSKRM7oDfxIT8trrTcmuGrAmwmecYW49X9tTEK0qmUL5tdKEEdCx3ZjlXLXj56RSw/ dY5ZH5vOKAVtED2J+o5H1P1/uDYaf3nS69H87HP/NNtidF+IIzDfb/JRIXrkp86v7cJE n23xcW/YNW1hrVao/THqTPXSAYTbLYh0drggKHMCujL+KFvnQtu1LD1ABEn3ziRYnxzG n+Cw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873235; x=1789478035; 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=TBWkiTQRj5oFfgRc5/u1AiKKPQh2jOjRYT5qV8ic2tC1fZN7TXi/YWXKrnfLgQLU6L qzP1QaY8Tgfbxsny5U32b0fw25CjUs33sAAHLjr2rUGBRbMoYT7sbFJBCU8cFXt+umXT dH3v778G2YVkY2Om7eqWWIX43NtS4QnSRVon0y1vfw1bOjI4Y5+/dmzkrRUnW51F/DMr Ka2tsPmseWBppb8b/mwotswjRoiTPv0z/KL2gbSRGZbqUT/v9hP2jIrnWaAM6vM5n8av K3eb+sY5uEnC3WtUTlNEqS3N+L0JWvGnlrxPkWcJIBCg9wT1xFu426POLZc2y/K+v/MD SOxg== X-Forwarded-Encrypted: i=1; AKwUvByEugnY/GkB/CbVufwYUUNFLUd2H6bsJT+QBmvNq0tQH6vvKRKuM32PvP8TTxwzDkG/vj2v/ADxeQblAF8=@vger.kernel.org X-Gm-Message-State: AFuF++ldyhQrmlTYcwoxNX7EieuNkg7l3mKqHPDrJW9LxYFlG9yP1xa1 nT4BGmIOY81NoYeTEGkyIJnUT0OFsgSQXcQnb+TNroUcVWmuX7HHEaQ2 X-Gm-Gg: AYBFou3B8XzLF1T5934eKNmzwxp9CCosamArWrOGUjsG/mn7nrxR4UQ8HnFcn6aOKy3 VbEAqn+3qykk8L/JDclqu62/RuucZSOGcb/Q//XROi9OX3cZl+sDWcv3gxReX6/gXOO5RscVMnp pBt9+sbknTeCqYV+ZXwGvUPdC4VZ2ibioBEOmc5T9B+uTZqX8I+3rO8hm4J6n5KSy2yjakOxM3p Zzz1HgQSsgsxRePh6PsV8jbl/89FA/kOczaL8uisUyJUrSt5eM9QO8nNVmGV+sVVrCsU8Y+0NhW Tl5XxoDaS1PqjxXfyRiq/oV19/aTZUmNoLB6DxXsK+7Ieeebjy0i4VbyEDP0qshSVEH8hZkysya YHsWeyipVNc23RO22qVtkZwXZrRwAxdlH9ULtn85CeO9qcQq75MXv1izmUp8VWwNAPbfszipP8Z FRJm7q1njT4kWNtO6CiFF4M8b+0UuaUq/8m50FTxnlmfFXvPG1+g== X-Received: by 2002:a17:906:1004:20b0:c26:2205:e8b9 with SMTP id a640c23a62f3a-c262205ea13mr572772266b.25.1788873234617; Tue, 08 Sep 2026 06:13:54 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:54 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:37 +0100 Subject: [PATCH RFC v2 04/11] 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: <20260908-stackdepot-trie-v2-4-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 Fri Sep 25 21:40:23 2026 Received: from mail-ed2-f12.google.com (mail-ed2-f12.google.com [74.125.228.76]) (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 5D74D559CBC for ; Tue, 8 Sep 2026 13:13:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.228.76 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873249; cv=none; b=th/IM890PIPWYjTR3HKXrHpRXSvZtkaSV7CU3xBx0HtzReGS63kEz6rcV4Zib+kPzUzrL1JkmiAu52FiEwkc61hunHMb5BF75rHg6m/jrbKcclEO+1mGPbiBM3AFyT6vbL/grPVV6/F0pcxsvfqK1fJh2gRAUCvPHd+M0KJn3Rc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873249; c=relaxed/simple; bh=HpBFvtYbBbaBVYOSmjDeMZxcswzVX3gJi0+gdtI6+cQ=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=lAXl7oPCf8C9TPwJhO/R7p55XbmKotbmue3jpE7Ye0r5Mt+yik0o5rQwKIEdOPhA2yyNeIwF3xK3v9hOLb2E+9Xex0pSqc/8/gVxh5DUV36ew+KUxUWRNQrOK1S0ZgtvSpM3NvwpU/iGq/GJoVBSzbTZrK7Fsx9jXi8JZcCW8uE= 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=ip9j/d4z; arc=none smtp.client-ip=74.125.228.76 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="ip9j/d4z" Received: by mail-ed2-f12.google.com with SMTP id 4fb4d7f45d1cf-6a60591bb18so826714a12.1 for ; Tue, 08 Sep 2026 06:13:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873236; x=1789478036; 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=YxLP4rXMEUOlBTXUJ41qDJ2wD0esY5E0fZn3mGsmNX4=; b=ip9j/d4zThDzG/NtkhbEw4JpmAFe+neYygMTqDPaXP34kR1R2mNR+t7CppypNEGdM9 o+cbb1wNIljgIM6kvxsrjuOaGyToON6LpwDtMVlUBgIzDLVMxiWoknQvGj5jKcb6qrnK 45k79ObgE5Qn3OqUwJDUTTwYIYKTP4epHwGYTZYaVs6k2v7tY2lVtEyqeWZJzG+KrhhC P1t750zh9vQkQ6mLxU5r0XATpga8EID+490++RG27SvHWrph1wG5Zcv6Urs9GiZlXb3b 4zKsJORDCAnqJPu78MdS3PkM0RoySN+IzQymTC2uCv1Wx52lfgtE3MANpKNfQnyT4Lge ZTeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873236; x=1789478036; 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=YxLP4rXMEUOlBTXUJ41qDJ2wD0esY5E0fZn3mGsmNX4=; b=kUSy5zd8f4L4d7eBud/WpWdUzrAxCY/OqMnFV7urqXxOvJuov8hoSbbqzBofykaJJJ E6xjskM2kedp08U10mKuDR8oWLWH+j1P2IznZ0YQbbp51owVqgqBjCOzD+I1ECNfgWeK khQKjXpk6kgDj80F3tDZ24rR4hZyG2dizmDpqFyNjaXUDblSH+XQpYFrkDliGMVSm8FL PIHRwlaxJ2e5ZKybJ4VSe+q1iaaKgMvCjM+36ds9Ous20NlgRM+byUG8N/Myi7PrnUu2 S6oHQw7ghLrY+sqkDvPY1IkvTA5HH71njZDBGzSXDVJAMRmH6Jsp/KrpSMa9D3niUrQl lVDg== X-Forwarded-Encrypted: i=1; AKwUvByzVTvys/OMI0QBtlUetcKPvHX028jFTpCloeShih10ZH2yGcQU0HYoOxH8gSBemuMuyUGrJ6ywoqcOXao=@vger.kernel.org X-Gm-Message-State: AFuF++m2C69j9+g6wCmlGGJrC6O5+MN8VV1CWNQw42Tqtef1Ucxv0rhm gBTOT3j7so6yXK2t4+MtzfVaYRz8TFGwe/v61xF848MLaScKsJu/LI2n X-Gm-Gg: AYBFou12f4mAF2N2DT7FT6bi39flLkc3pKJoDwPg3KYtXT5sy9cuiIQH2Bti0a7r4w4 0gEevuQILQM8WJIknVVirxSb1N5D2+dH7hX6Do+iiaD5h/Ok0kOM9muPQSOtptbacJvyemtUfDh UMQVdnsND7Lacmo/9jT+/Ze+hywBExgc+J6Se7bJgj+Khl/PxCe+NL7ah7tsNeZapiZ8XxDKKAQ SIgGgPt+SSCs3Tm/rE1D90oAcLa0I3Qc248Qh7EVKSf5MKEr8EXAdV1TmgOwNUQ8aioYjJ1Nd2y rsDSmdoZd9Gslr3SS47w9JvU8tE9YVwYkp6jdF6Dcfn+oMiS0Wl82XxqwrAPbymiGrwEFyt/C6N S3ax3YyqoQN80VqrTuLjknXOIcgBxqa6h6+FAT73kgj5vG7DRHeuEJeehWXH+POVEQO69GLYYri /zZbPO7C35XWqy2Js/Q0bzlKjp2//bc1Zr2lBNbrTgeEEVIkg67vDy4SW+8OMD X-Received: by 2002:a17:907:3f09:b0:c25:f7db:4bea with SMTP id a640c23a62f3a-c290446b88cmr319041366b.16.1788873235525; Tue, 08 Sep 2026 06:13:55 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:55 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:38 +0100 Subject: [PATCH RFC v2 05/11] 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: <20260908-stackdepot-trie-v2-5-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 in stack depot and retains the resulting persistent handles. Once trie storage is enabled, these handles can refer to trie-backed entries, while kmsan_print_origin() still relies on the hash-only stack_depot_fetch() API. Use one KMSAN_STACK_DEPTH array to materialize each origin and chained stack in turn. Preserve the chain's head and next-origin handles before reusing the array for the chained stack. The array covers both the regular save limit and the smaller synthetic records. Pass the scratch array into a common origin-printing helper. Keep local storage for standalone kmsan_print_origin() calls, but let kmsan_report() reuse its existing stack_entries array after printing the report stack. With x86-64 Clang 19, the regular nested report path uses 752 bytes, below its 768-byte size before this conversion. lib/stackdepot.c is uninstrumented, so stack_depot_fetch_into() unpoisons the successfully copied range before returning it to KMSAN. Remove the now-redundant explicit unpoisoning of chained entries. Origin depth and use-after-free metadata remain in the handle's extra bits and are unchanged. Update test_stackdepot_roundtrip() to use caller-owned storage while retaining its frame-count and kmsan_check_memory() checks. This verifies that the copy-out API returns initialized entries to instrumented callers. Signed-off-by: Caleb Kan --- mm/kmsan/kmsan_test.c | 4 ++-- mm/kmsan/report.c | 28 ++++++++++++++++------------ 2 files changed, 18 insertions(+), 14 deletions(-) diff --git a/mm/kmsan/kmsan_test.c b/mm/kmsan/kmsan_test.c index 31f47cc4dab4..7c04e4b21873 100644 --- a/mm/kmsan/kmsan_test.c +++ b/mm/kmsan/kmsan_test.c @@ -669,7 +669,7 @@ static void test_long_origin_chain(struct kunit *test) */ static void test_stackdepot_roundtrip(struct kunit *test) { - unsigned long src_entries[16], *dst_entries; + unsigned long src_entries[16], dst_entries[16]; unsigned int src_nentries, dst_nentries; EXPECTATION_NO_REPORT(expect); depot_stack_handle_t handle; @@ -680,7 +680,7 @@ static void test_stackdepot_roundtrip(struct kunit *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..0770658ba932 100644 --- a/mm/kmsan/report.c +++ b/mm/kmsan/report.c @@ -83,9 +83,9 @@ static char *pretty_descr(char *descr) return report_local_descr; } =20 -void kmsan_print_origin(depot_stack_handle_t origin) +static void kmsan_print_origin_with_buf(depot_stack_handle_t origin, + unsigned long *entries) { - unsigned long *entries =3D NULL, *chained_entries =3D NULL; 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, KMSAN_STACK_DEPTH); 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, + KMSAN_STACK_DEPTH); + skipnr =3D get_stack_skipnr(entries, chained_nr_entries); + stack_trace_print(entries + skipnr, chained_nr_entries - skipnr, 0); pr_err("\n"); continue; @@ -147,6 +144,13 @@ void kmsan_print_origin(depot_stack_handle_t origin) } } =20 +void kmsan_print_origin(depot_stack_handle_t origin) +{ + unsigned long entries[KMSAN_STACK_DEPTH]; + + kmsan_print_origin_with_buf(origin, entries); +} + void kmsan_report(depot_stack_handle_t origin, void *address, int size, int off_first, int off_last, const void __user *user_addr, enum kmsan_bug_reason reason) @@ -193,7 +197,7 @@ void kmsan_report(depot_stack_handle_t origin, void *ad= dress, int size, 0); pr_err("\n"); =20 - kmsan_print_origin(origin); + kmsan_print_origin_with_buf(origin, stack_entries); =20 if (size) { pr_err("\n"); --=20 Git-155) From nobody Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f46.google.com (mail-ej1-f46.google.com [209.85.218.46]) (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 E1166549393 for ; Tue, 8 Sep 2026 13:14:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873248; cv=none; b=H+TNRqg6i2qLxdXl9kwDDgTsXOk1X6r4NoQq/e7BaTWyiA845fowt4i3GzkvAR5sMkxWq1rA15JK7B/3rAzlvrRJDLQM2ktjj5558veT24Q3R2F6K+YL2C6RMOueq/AI8mKQQgu8GFhLq6JxjmqaEEhMNbJdCIlsorbY2jIgc4U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873248; c=relaxed/simple; bh=xYmnteVtSbEvwPmbuzw2S9jQ0YjnKg/22WBt3FP6+Xw=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=OLqpioxXrP+gBluc3RAebJJKL5e/Now4a78korcREPlfRFhN8EHfNxEKuaQY5xrfMA4f/tNq2Naz0bJyJeFk4+7fcro8LYzjSKOm0xFvDAWC45z3C/aRJ5HLcKGE42SrX3kajPM0Z4xCsawVsfTFLsF2vHQJfhxfBVkuR8rv+Gk= 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=CXvPaTBC; arc=none smtp.client-ip=209.85.218.46 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="CXvPaTBC" Received: by mail-ej1-f46.google.com with SMTP id a640c23a62f3a-c250c6a6a9aso762651266b.1 for ; Tue, 08 Sep 2026 06:14:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873239; x=1789478039; 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=feAXqKN1iMgDWT0yxjPZBEzrVPGz+wLdhMnnl2MxBJE=; b=CXvPaTBC5lgfuAWAh9DSp6XesBiJNbyYspr1va1cPkgCEQ43E6MPr9XrdLLnJ3HIQM +jFIGiDVoaPiXZrjBpd6jn1pXsUNGtTlhPTuQMc8CD4U4SjvLoyqPCfSOMEIG9lkv57z yb+CDOdDwbn1RVwqAm0pPqYaKGH5az8xClgMZiB4wilVS4T+ZIxo1oNOuMeM9Gy0kDGn DZqJQ658yQYoMckA7KXJ4kBD1+OYW2Uhor8vWYmqiOjRQpfMQX6w7ecYAvfsVB54qh3a DpwRgky+KxZjhWNDDw61u5psiCbSQziHVNeWd9ekWcSkg30iDjAO97p0tceU6ujJ19+M XKeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873239; x=1789478039; 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=feAXqKN1iMgDWT0yxjPZBEzrVPGz+wLdhMnnl2MxBJE=; b=emouNLMSx6XYe1TzvYh2dOi73/xnM7ZzeBs7a6qdAMmCmW4c4x+kYGijTbREAtN9K0 LTAhrJiLCVJLotmsCgfjdOHboFwiu95v7eoAoIhquGroGqd7XUpst+t09w1SizoCDhUI /6Z7eRpbQ3NcXOrffz8nfclF8kE+iuIpO5jsoSmOVbV7XH1+eln0f5LiVXS5U3LgCLEp 61InCFMA9jKkciSyXNUUYr+AiFlgetia6XHWHueBsY8Y+bF4U7gkZgX8pzmHBsjzDqsV 4ZVY8iBywOEcqgRkbe9bQfJ4zTJg83/lOCs7yJID7Pqz98S9HYsEPoBZY5Ip8BitH90I glrg== X-Forwarded-Encrypted: i=1; AKwUvByyDO7he9wB8VvehNCJTKNm1igh+oV0MyU+qiWChr/2QBdkOoucYfVDYv8XqqxfbwKkNvwUrlWRwM+dp8s=@vger.kernel.org X-Gm-Message-State: AFuF++kULi6F1g7dPrSFGsNycmKtQGHh3hpfTjlSaepMdZK3NGyYx/ms 9cp3mSNSwHDDE1q0BIAwoljZ1MX94Jgzr28/pkp6UBF6LkJ6wCA5AUE6 X-Gm-Gg: AYBFou17KRE80yqLq5urvsrSxor9BobleSWZY7LjvBNM1BkU2Z1ypsIs1z6KUbsuDOK y+6KaDX5cpb7M7QxKz0coXBkdGaZorKmQibl7fqFPpSA6WkFXPXSKZYIQ0JxigM8Stczg1SyeCl CRzf9s0cAX/gFSWpapuEYJn1Uf0Su4Ewr7ogR4w2kvPh2me4iZntdz70P56X2zWyALN7biY9Bjf sSYIBAmge6PU92vepl/3r2GbyKmhpqS1aifjmqAcXVVra1Xbz4MeuR6s/pXTG1ok4RIPtoNaciL hLlkBiXatgfCZHhiNoy995QjxnQAc1K2r75RWtNc1ISSs0XoeexECgByMK3eqe8BEP3AnC/ctUM hz50mWch6HjlM5LQVoskELviSTxMlKJk8gsndWI2oCm5f/9ra6jhHjAmwfCyLDVfEt5n89Q50cw yCIpVUPAxlw4UGKRld9pStpE5wF+WwCJ8fEHPWRguml41Um0cxFw== X-Received: by 2002:a17:907:d87:b0:c25:504a:1e25 with SMTP id a640c23a62f3a-c260cbd2d02mr1995012366b.13.1788873238868; Tue, 08 Sep 2026 06:13:58 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:56 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:39 +0100 Subject: [PATCH RFC v2 06/11] 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: <20260908-stackdepot-trie-v2-6-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 f9b56cb439e7..4aa1c5a45718 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -8198,12 +8198,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]; } @@ -8211,7 +8211,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]; } @@ -9946,12 +9946,14 @@ static int slab_debugfs_show(struct seq_file *seq, = void *v) #ifdef CONFIG_STACKDEPOT { depot_stack_handle_t handle; - unsigned long *entries; + unsigned long entries[TRACK_ADDRS_COUNT]; unsigned int nr_entries, j; =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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f53.google.com (mail-ej1-f53.google.com [209.85.218.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 2E090560AB7 for ; Tue, 8 Sep 2026 13:14:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873253; cv=none; b=IK1wTcNalpgqSNZQJVAaxrJe1cAvnktb698EZkrL+IlsCkAYCerNoZU6dM8p7pGcHSEMit0Hpw+Q52tEClkDlwtOWcoUCuwWgVeuOp6NXSp5smP+lEdg9ZRbYS+reXhEXr1j6wOi9XERd0T+9Zf8xZNBqxWRlwb0UaDZdSGM2d8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873253; c=relaxed/simple; bh=4Gmxb5iLpVzmxwtAiwm50Wo4ui0NNmlc4p4QOsCkq9g=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=nstl2ArOOtukdeiGsqJApqqVOYaSfR8LrAT3Nj0B6BqG5vaGhZu7QI4l8yVdEea4tPYcLlsBb/DB6A6DmVOBuFpsS3r5BJt6pq8BASX3Z9XbfyAcpAO4YBMoU7ugbQie5elld7vK0wvTRkfEKMjZ1xXjnTUb4FKhqAO25UgD7Pw= 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=dZypczUh; arc=none smtp.client-ip=209.85.218.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="dZypczUh" Received: by mail-ej1-f53.google.com with SMTP id a640c23a62f3a-c253425b253so675116066b.1 for ; Tue, 08 Sep 2026 06:14:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873240; x=1789478040; 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=qpzGXcywvBcmoPFLpe0sjmmkxn8qreN3FEfttSNZISw=; b=dZypczUhnUIa2UAc0aeObyI5RgfI1TIRtY3iFfYGFY+2CFQTkwstfzR7zQEzEpEsRd +48L31fqc4GIFdNW8MaqkEy/Nrow31jH8k+ZnBvZvQZa2AV8ppwNBr/8SmWLvhrZgGUL /WkP+/Uw2yJzMR+r2ixkEUNShOP7VorhS/Rv+cMHREEaSKqbkgEnVTB8h/yBR3wUiSIR /Nk66lgbKR1Eci4QXJ0QhxdBjWNUi5KTXsde+j7srYt/18W9JnktoERNse/0cJe5Itak 3+aWXQ2NCSpTDYiBD0xfN2i5/wWOw1RCgoklQVKPTgGrMAVkDFJTaGOShtzY25ExfipA lTvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873240; x=1789478040; 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=qpzGXcywvBcmoPFLpe0sjmmkxn8qreN3FEfttSNZISw=; b=K/ZiSnvdcgD8Uwg6Z0+qaCwW9L6CTdHM00qkeUKz6PulJlXMwJLfMLkY+E8bRlbZpj uOeAXfIPDSNN+BMEZp5BpM2HTmRJAa+3MS49gjo31IvjHDB7/vXpP3W3zAPivpYU3Bzm kfBrIpiJUuVL5sH9Vlgz5kwbMbmsvRa9qt/B7UzM1I2dGLQB4ZwfeGqi5k0qO/x23n9o aeH5gsZ7HCHZ/rLgkx7fm69WA481xlqJ+18txWs85xDmxgfw7ZNeCqbX/H3nHFYyRI3j 0hOOl6Qvg1o/rVrJKBRqqtdesRcJxSzO4pFY6T+XU1N2zm4D7KHX/Q0e8HDTtEOGVIS8 ASRA== X-Forwarded-Encrypted: i=1; AKwUvBy10mBPrJLI+INezHe5qQLGq3dSiIZfQY4DHdXEjWBF1Or2bM9V0DH0+8HnY0kyEmlEKL6rH+Pt5/O5c+g=@vger.kernel.org X-Gm-Message-State: AFuF++mv/T2mZVIHBb3Wy9LGHotiaTgbrJmlC7hrMJFiEG0A3TN2W44J IDybtsS4UcbGCld9aC+RVBmsHNsT6gEcDZ8vNx7saFd0Giw6bhI4JEwW X-Gm-Gg: AYBFou2SO0moK+N5H5XE6ABLqOz32D3dwzQJMXGMQ9/x2y7S2VpdO1LoBD1OqHYJ0lq eZecpmD7IIeP9WHXpYfaTJcXhuHISFLmYzOLy4woGaNj3zA82XYkS+tL9W5n3cVv4JijEgqfC6C fd3UNVjKSKDkiPIraF+S9ZFOreTkPgH08tEWmirv+yzFTxXy0y/iXufy5VDatp6AhmFxnhFCqNT DSY3KWH3D+fJyvANb9b7kXIezarmUtyk36dNyQFjoT7tjYe7EpKTR8d7tkKTVaI52uktHBp7zkF Xc76Sw62tFf9V1b83hZjDgJ6SisJqe/DthtDU0oXZ1Zyn4RpZCcKWePP9AUfPtsGDqUJxJHvUtR Ls1atL9ftU0g7SjJfAongmwyNXda1zXsV2RqoZ39WFuYrR5Wsav/i4dsV5gw7OsWgHFjYxtRQL5 jxP+X5l3HM80VgYSRKqFh4Cgq3s6y3HWDmxPY3APZ6rOjkG97JoA== X-Received: by 2002:a17:906:c116:b0:c26:19de:9add with SMTP id a640c23a62f3a-c2619dea99emr1021645266b.28.1788873239627; Tue, 08 Sep 2026 06:13:59 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:13:59 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:40 +0100 Subject: [PATCH RFC v2 07/11] 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: <20260908-stackdepot-trie-v2-7-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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(). A later patch allows persistent stack depot saves to return trie-backed handles, while stack_depot_fetch() remains limited to hash-backed records. Use stack_depot_snprint() to format either backend. Keep the PAGE_SIZE buffer and leave the warning text, existing indentation, and backtrace unchanged. Signed-off-by: Caleb Kan --- 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 e14814c30d8c..f48b02379b71 100644 --- a/drivers/gpu/drm/drm_modeset_lock.c +++ b/drivers/gpu/drm/drm_modeset_lock.c @@ -94,16 +94,13 @@ static noinline depot_stack_handle_t __drm_stack_depot_= save(void) static void __drm_stack_depot_print(depot_stack_handle_t stack_depot) { struct drm_printer p =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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f43.google.com (mail-ej1-f43.google.com [209.85.218.43]) (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 9525C55D891 for ; Tue, 8 Sep 2026 13:14:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873257; cv=none; b=j6DBve/s6azgJ/tfajJa9MdfkNZg6560en5iHJdMLrw5PvXLGeDyq1Rpfsp/BW1XsVOnBSiGDN86eOdgNL8mhZQMn2Yb6T37fa7a+iQERaPyEBXfCMaOMM0rvMQ+fcVnpSW38jF+L4ctH0rXYYRtpAAUR6QDhIBhJ56qsCbKZXI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873257; c=relaxed/simple; bh=lv26SAeJxy+BsWe+88/ox4O1QD8JH8gEB6CZwLn5x4U=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=onGhepgzTkYqUe2B1brV86tksYDN05oRHwufwSk8OUbxI/7Iqye+Xhz/Gk3Fxct56ssbK9o6a5Uxkd94aqgkiEJoWS83VERpbGzPmWp7ZYzD0nlt8nmZ4hcYH7E9pKVZxA1n05HBgK6/H4DulW3jdbhxm4Rmc5Exl5XPyd7r8OQ= 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=jnwGr5H3; arc=none smtp.client-ip=209.85.218.43 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="jnwGr5H3" Received: by mail-ej1-f43.google.com with SMTP id a640c23a62f3a-c253425b253so675118966b.1 for ; Tue, 08 Sep 2026 06:14:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873240; x=1789478040; 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=pZmngaVsUToRipCvkV5xzkVfvhYV30Q+0QWGu1nqLPY=; b=jnwGr5H3ZAo5E8jbk/ncQQDxgMRLwVDQYIdi8+T8YfJh67kAOlFriHCA8hO1Ow+9cS J7s0d7l/07H5EwtnsWThW10S4z7DVR7xvuWKETFVT8PqMVVGmVYONfMpeAHtjO3Jrqzj EdUPlFAegdVRpLXjgtlJiZobT2LDF5RSv3Kath95/Gfb/+safwYs1m/DSFniqkOko8XR UiojAv0TYniT36u84cPBasAIOqJVk/HL0VFYdOhmeD0fS4HuGWoiQ0WUoOhEJGy/89+e cdji6JfvrMqR9JRMws6NQnsqpw2et7P0aYREA467yAqT0kSYsVkWfdTRvmjLXx+Ya4cx s7Tw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873240; x=1789478040; 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=pZmngaVsUToRipCvkV5xzkVfvhYV30Q+0QWGu1nqLPY=; b=CPPdROLW2qE+y3aaoRqljN6gW5LLorTxRKcNE4hQDEbkYS3UkkuCzAnodPagevMIYq GufxO28FmZTxAap/CXMIeABUFcZB7Yo3MW0FfwTcc9K0O8yplPx/76mXpXCRh6EzS7lI VUkj1h/si+msUXHA91IhpadmBynBqTR5JV4R2X5wC/E4iGejqJh8zJXQyEiLnF4vwJhE GNZ4pwhKWitbjO9t5mC0zKYT8H6JyNsiPzsgle5IKokdW9dT1mp8VaJcH8erB6mLkGHi sfQce/+SuO/bVrNcJOqE17vPFW5BEEb1SXPElofpRTpcOej+CPvh0XdGcXodT99rhiIU 52xw== X-Forwarded-Encrypted: i=1; AKwUvBxlVTljEenImhJdjKxXBiJExdn94f+QQMC3DjVugOrbXF9QJVWodIsrdo2WbHa0rzX3qlNS3hgXNHfCObk=@vger.kernel.org X-Gm-Message-State: AFuF++kPvfaAlIr7Z1sPKj/AKDKTz6uOThtKnpX1Nd3kxRE8cxkkIzKS F/nNrqeIus3u/OPaQ1qhLgvYAJQag0oghlXpPsHhOGjx/TJ/GFJsdj8C X-Gm-Gg: AYBFou2pmvDkQ7lZ8pjTtEKDgWGMW7UMOJOtGj3r4CKE+vMnu22vOYqImx7RoEdyQvE eFlmWaSu8QMtzjOnBO1ApLpJdk4KVEIvegGDRQMVPD89oakhx41Fa5XvO3n7m/doJHfej1lWU37 3uEEYmS9tQWiGlp19mNGGwFkjWz/3+aJLKXkLp/b3KotCGObA1ugyUQzuF14kRjtCYiqUNSLT4X jiRBTtZESyO8Mw6gEXW+6Sz2vG6qRArD93YZdk8HLHa9lxNK76CfRGXeouThnEM8VDs7jZGrUDM J/jIjMmGd5uHzzAMzJ3dcx1AmIf8xSr8w7WOgzn8/awq+HH8MgLP1fDYnEiSDv3IZGSdxaVv4LG qglRUJbFHnJzvSFlgHkMNLi7SDtm6u0imWjB1FGCgwFEZU8Tgb7in9fh5JeIpns0rx+vbxaXtoO 4El31tD7u8zX5JOJfU5H+XtEuVj8UyoQt/bqsai7VTS3axU3YZBA== X-Received: by 2002:a17:906:2082:b0:c29:18da:43e with SMTP id a640c23a62f3a-c2918da084fmr93675766b.12.1788873240393; Tue, 08 Sep 2026 06:14:00 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.13.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:14:00 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:41 +0100 Subject: [PATCH RFC v2 08/11] 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: <20260908-stackdepot-trie-v2-8-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 reconstruct stacks only from contiguous hash-backed records. A later patch will encode trie-backed handles as dense stack IDs in pool_index_plus_1 and offset. Without an explicit check, a trie handle enters the hash-only out-of-bounds path. Reject pool_index_plus_1 values above stack_max_pools before looking up a hash pool, and report that trie-backed handles are unsupported. Supporting them would require the helper to walk the side table and parent links, which is left for future work. Signed-off-by: Caleb Kan --- 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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f50.google.com (mail-ej1-f50.google.com [209.85.218.50]) (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 1FC9D55D89B for ; Tue, 8 Sep 2026 13:14:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873255; cv=none; b=dnQUjinif4HTVMzjnOypUOxbcoi5gimSV07CgK1vfTumWm5EX9BM/XjiOiWc2qe4p40Utr0It0qzSoGVrWtupLPVrJgdcF+0crD0d5+k8SeWRyBoup0KpAC6gfsNRno7KVzCaRWC0lgWByVUvDdOfUDqBwHhGN3mbAuOmSTdz2E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873255; c=relaxed/simple; bh=qc+jEK7mFoMKlqaFPviVtorgYOoRV33PJN3e/4W/smw=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=O/HTTl88GAiKwJ7XfyFpxznVRgqi0ydCCPxFpnfP6Uznoqa7GlrQMqvdj9sbZZfzAad+05dJjs+M2j8bge7o3GAaov1yWjR7NKHM12qHnBpSmp+oRXyImxXPkWOWirpOi/KpCWede78rF8vBk1/jPDTJSk17oRwiyVh00GY7X0k= 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=eg8Kf3XI; arc=none smtp.client-ip=209.85.218.50 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="eg8Kf3XI" Received: by mail-ej1-f50.google.com with SMTP id a640c23a62f3a-c2533d83e3bso793440366b.2 for ; Tue, 08 Sep 2026 06:14:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873241; x=1789478041; 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=whtEbb8/XqGjTBPOJjMO+bu+KwkFFXfQbBIPnf5a/B4=; b=eg8Kf3XIY18Q/Ovwao0xRReJNz4pbQ8GhuLE8gvujUkhZi/NgaQm5Jr8q4mzdFt5NE 3Nm6SfCu9gNuIdLkrvrm1a+swGVuQrrwhsFT79d+glyoFecdkMLLc5hlmNLfo5WpMH1d ou+B1HCVwvjaanr6gGW4qT1g8fr5ITl0kaQIN/3BFDkCQpBdnffLJpOndbV7P0GegFuY vvGCMNkgPosdvC1lF9VUO14drPLk9HFKcyfbhjDMDbXqJ/kGlAyy+yAkSB1tOl/VKAFI BC2rVCjXW1QLFTbancKSrqbDJcjulNXw6ICJr31oLHEVRgrLM9EZotSWlhwBlYaG+GcD +ecQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873241; x=1789478041; 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=whtEbb8/XqGjTBPOJjMO+bu+KwkFFXfQbBIPnf5a/B4=; b=AvHgVWwJCDm0Gkm1A+Rkx7c3AgLm+v8/GjwAB6yyCuiMUNmmpm7JHnJErCFfOoIRzg ea1np+CfXo/nloVy2Qod+N892qJiDAKYEIwLfWbLttLzi5IFJpeJboA4e4NW7xPTTWuj cSE71GwQk58aSeJNVwCmxiNa1Moe5HZXpQC8w8oVPLU8wd5OJLnDak/TBALLABtziyNv /CoY1YI1i93c9mn3iRXmOMmrLx3s0nXnEcxQ5YBid6Rrqi4NlcazYlGIsRbEVVumJpu9 F4nqAW4PvQ5zJd3TcN6JhA5uQUjJEtvxAWXF4ilewOFSc8jhIWbXvNDaE/wTrqVR1Dgm amlg== X-Forwarded-Encrypted: i=1; AKwUvByg+2oPtborKCHSlLCYh8vW6RQIx8NciIZlm24nK7wxYwvZZuwqa74aUMLNIDOPyR8+sXLEUonIWI2a6ko=@vger.kernel.org X-Gm-Message-State: AFuF++n6Ae3GwG/+u9dRx6hD9ziFl0WQfNmKSBM8W4D3kzDeVj/4Bs0Y 8tGjKQIyoVYUFZULDmouTZSwKlXyuS+jgPfLulJmhPn7eNZ86l3Dibgg X-Gm-Gg: AYBFou2TD9kd4xQNxoZMfm5tKtSNI2sakVF0iT/s8dkXfGFSuRDflCjOuLpXL5dY06I SmOzMLMTkpTTYtqKGFp0+QJhMxQ/AIy/q7uM1++XcmEIb4zZ6lSeP6kfcQxv9AF/0V4Wz8IzLXe pc2+xOtokkN9aQRhzeJxDhipBS+6bJHErulq7ARv7Ub6qbup3yt9n5NCDTaPis7Idh/NbrnkVr9 Z29PQ5fg2jonWWke6Ny9233zv5ozC0/qBNRUFoLK3XI2eAeGS/OHsEaqtHzVYSEFfEIRk/YbCyi 2LqEdG3SsylUcUibtgNLcebEUZCTZ6m3vV5cbYbAP6l6stU/DeCam5fl+S/DpXvNUxeZR+bnV4z au8p8E/0vBW/vjqfWRx0uUJ7Y2Qn75BzYBpUas3i3x/NQejXZPlvtUNnUzR3+ArQePI3UASamtr rNTaBzS9xeWhUa9Cvle3SG5RhrKPmz44VeNTL8d/hHQstao1T6yg== X-Received: by 2002:a17:907:7b8c:b0:c19:49ee:19b9 with SMTP id a640c23a62f3a-c260cbfa1a6mr2202057266b.15.1788873241205; Tue, 08 Sep 2026 06:14:01 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.14.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:14:00 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:42 +0100 Subject: [PATCH RFC v2 09/11] stackdepot: add architecture hooks for compact frame 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: <20260908-stackdepot-trie-v2-9-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 Path-compressed trie nodes can reduce their frame storage further when an architecture can represent kernel text and module addresses in 32 bits. Add architecture hooks that compress a frame only when decompression reproduces the original address exactly. Store arm64 frames as signed 32-bit offsets from _text. This covers the 2 GB module relocation window without depending on a 4 GB high-bit boundary. On x86-64, store the low 32 bits when the upper 32 bits are all set. Keep other frames full-width, and provide a generic implementation that always rejects compression. Make the generic header available to architectures without a specialized implementation and wire it explicitly for UML. Add KUnit coverage for raw fallback, arm64 boundary round trips, and native x86-64 prefix compression. These hooks do not change stack depot behavior until a later patch adds trie storage. Signed-off-by: Caleb Kan --- arch/arm64/include/asm/stackdepot.h | 42 ++++++++++++++++++ arch/um/include/asm/Kbuild | 1 + arch/x86/include/asm/stackdepot.h | 37 ++++++++++++++++ include/asm-generic/Kbuild | 1 + include/asm-generic/stackdepot.h | 19 ++++++++ lib/tests/stackdepot_kunit.c | 86 +++++++++++++++++++++++++++++++++= ++++ 6 files changed, 186 insertions(+) diff --git a/arch/arm64/include/asm/stackdepot.h b/arch/arm64/include/asm/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 2bc00c67dc54..d8402a6afc70 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/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c index 3c526791ef93..e4a7f1c83457 100644 --- a/lib/tests/stackdepot_kunit.c +++ b/lib/tests/stackdepot_kunit.c @@ -3,9 +3,21 @@ #include #include #include +#include #include #include =20 +#include + +#ifdef CONFIG_ARM64 +#include + +static inline unsigned long stackdepot_arm64_frame(long offset) +{ + return (unsigned long)((long)_text + offset); +} +#endif + static void stackdepot_countable_public(struct kunit *test) { unsigned long plain_entries[] =3D { @@ -125,10 +137,84 @@ static void stackdepot_fetch_into_rejects_missing_or_= short_stack(struct kunit *t KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected)); } =20 +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_countable_public), KUNIT_CASE(stackdepot_fetch_into_roundtrip), KUNIT_CASE(stackdepot_fetch_into_rejects_missing_or_short_stack), + KUNIT_CASE(stackdepot_frame_raw_fallback), +#if defined(CONFIG_X86_64) && !defined(CONFIG_UML) + KUNIT_CASE(stackdepot_frame_x86_64), +#endif +#ifdef CONFIG_ARM64 + KUNIT_CASE(stackdepot_frame_arm64), +#endif {} }; =20 --=20 Git-155) From nobody Fri Sep 25 21:40: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 8E1CD5505FB for ; Tue, 8 Sep 2026 13:14:06 +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=1788873257; cv=none; b=A7QwTEC6cXPxc7Wc2ei33JqbmmGeOxxrKF4DR1DNNaeK45qwzFgv3yT8RB3kGNqwe/7UuBeayUc6RQts7v5SEO4kJC+zQAdV2ATC/uByFDZ1jOZd6z0+B11ZFuXWqJQQtaiM34glicTXyOnI83PY4bTfG16uPRbEGyMtT0xOxMY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873257; c=relaxed/simple; bh=d7s9Dgn4qoD7kDN93F+8Q9UmDb2JH+SFThGoC7doNQ8=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=LZgq0yayX2HGdNBsl7Fnvdbe34RPlRdNk4+7z41OS1nFN7qGF1i45MdP5OhCDKb8TK+hGypJMikQ4E/ItPCwQsnPvMB4di7UBTftAXDSLoJ7B01QHPvU0NK9YCcjVzr2hgKPnoHUmBxN31sAkJuMO5RQ6Ke/gmv5ATLVTcUyiqs= 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=chidqMct; 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="chidqMct" Received: by mail-ej1-f45.google.com with SMTP id a640c23a62f3a-c262bc686d9so499333866b.2 for ; Tue, 08 Sep 2026 06:14:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873242; x=1789478042; 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=RUfRfUxHUT8u2SHFALNAL3D42Mb1NExIK5Td/2Q3tMk=; b=chidqMct9dKsJNosqMhMDogMUZnhiQWCJmNA+sRt2lKpJ4ZnSEiOpw1FDyGlQw4Xu+ IzAqkgFWbW1CmNU3mhlwD31ejS32DRO96nyf93PMifAG811dUSqMOn1XBhmOROROV5wQ NxKCizi1vLv/87eVHwiXmSnmXdTJCxlgvI0B7m76baLYUMlCnUnao/0/HOvVMpuQ4kd8 55qaw+1yXo+5p7D28PeFsiKQbx+QtY4s+ATfgRjOO0jEvAws3f+ZBqLZhL3/2wfy+004 2DHiaYGO3szxt/LDPfdxMZWXiniRuOD30Dehbkr5NPlg9FZtWVBOds84QpdPlaXfTBzy ryng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873242; x=1789478042; 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=RUfRfUxHUT8u2SHFALNAL3D42Mb1NExIK5Td/2Q3tMk=; b=YO0dzulxiebciHSfp2qmjnUg/3NYJn1Hv/HIjilxTdDKDkM3l4QGnBLtzPvsy/acjq OO80hKEDgQfFr4YkYEtTN//uRxdQzeREgQJGIuKdsHbMvs9nkum0GmIJRRCtokG5rIZQ dGNF9/xhtcsgiOx+a9dY3P5sW9E1z/sy3Hzx4OIIf0co/JRydqIY6TdJIvHb2+U2ahZg nrN4/meP8/JS1y18hTZfSoAlzRO4lUCD0EXbs774Jpq99Hn+JpvWAcj8IuZNF2JUisK0 jcqloKhLk1g/VeguZ8Uswh0JfoasXKTSxoE/crafQ2P4kheKn0oEJgZRq8L+OwZX0SEu Xoyw== X-Forwarded-Encrypted: i=1; AKwUvBwmuxyyfejkxtXy2YWm8rkGCBz3C5Hn3xik9qhezatf1ExD7wzBSMN24sV+T3+t7S6SZeolE1qu+hcMxOc=@vger.kernel.org X-Gm-Message-State: AFuF++mp1VYzaR+H40fmUarTMDVUjx0mw/3zdz+EmPeDogjaW+I3v4o6 2t5C89lelgUL0eGQDmLKfEtQ8we2oE2sYhv9d8MYvhgYDh28vovr392w X-Gm-Gg: AYBFou2KFag4R+UPEfveJojH8gDCTO3shd9wNiCJ3W+I67x7cycL3vR9ZL1sSHZJ7jo m+iXyNfhmTZ89uwFCxkHmZ3WhhKUpxduFxOXBaFgG3bZdJsY0Wxk+jIv4yjinZh7O2oioWHWlLL 6TBXpk2Pzm8iizaoSasv0ESgx2ERP6/oIWKhSZVPwMjZEFGykiTeJnW3vt/rMupPbx+bdwT7c9o 9lGgzzJPvgVikWgmK/Ad5NIcUBdABu0NDxhSF6qMzmD+6ndFFsf8n/c0sh1WBHJoBDnyz89Xpvi IohdOQ4v1fEYJKAmDCpvvIbzopxRAqb68GHnJ6urM7qoFGW+FOPHz7So0TItEQgLqSNp+MajJHh SYWjrilAodVRAUbDO5ZmiONBHabjao0peXrFVJdcbeJUrBG0YdjIfM1IUuj7G2pQwBcJVjRognH +TGlErE4fZ6ZGGAOOnDII9QI9t19R5r7OwQvNAtXYeGi2rEFuJRA== X-Received: by 2002:a17:906:ee8d:b0:c21:1b58:fa96 with SMTP id a640c23a62f3a-c260c661b83mr1211894666b.3.1788873242075; Tue, 08 Sep 2026 06:14:02 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.14.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:14:01 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:43 +0100 Subject: [PATCH RFC v2 10/11] 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: <20260908-stackdepot-trie-v2-10-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 identical traces, but stores every different trace in full. Persistent traces often share most of their frames, so this wastes memory and can exhaust the pool limit. Once the pools are full, a new trace returns 0 and later diagnostics can lose useful stack information. Add an opt-in path-compressed trie for persistent records saved without STACK_DEPOT_FLAG_GET or STACK_DEPOT_FLAG_COUNTABLE. Store a run of frames in each node and branch only where traces differ. Insertion can descend through an existing path, split a partial match, make an internal node a stored trace, or attach a new suffix. Encode dense stack IDs in pool-index values that cannot name a hash pool. A sparse side table maps each ID to the node where the trace ends. Fetching a trace follows parent links from that node. Stored traces and IDs are not recycled. Use the architecture hooks from the preceding patch to store a frame in 32 bits only when it can be reconstructed exactly. Keep all other frames at full width. Allocate trie nodes and child arrays from contiguous runs of 16-byte slots in the existing order-2 pools. Each pool records an upper bound on its largest free run so the allocator can skip pools that are too fragmented. Search from a next-fit cursor first, then scan the whole pool so released holes and runs that cross the cursor remain visible. Record the exact longest run only after a complete scan fails. A child array must fit in one pool. On a 4 KiB, 64-bit system, one node can have at most 1,024 children. An insertion that would add a 1,025th child returns 0, while existing traces remain valid. The largest node observed on a pre-production server had about 835 children. Take the writer lock before the existing pool lock. Reserve everything that can fail before publishing a trace. Release unpublished node and child slots immediately, but keep registered pools, side-table space, stored traces, and IDs. When a node or child array is replaced, keep it until a later allocating insertion sees that its RCU grace period has ended. An NMI save only looks for an existing trie record and returns 0 on a miss. Outside NMI, a save gets one insertion attempt when STACK_DEPOT_FLAG_CAN_ALLOC is clear or its GFP flags do not allow spinning on raw locks. The attempt uses only pool and side-table space already available. If spinning is allowed, take the writer and pool locks; otherwise try each lock once. Access to the side-table page cache also uses a trylock. The attempt does not allocate, retry, wait for RCU, or fall back to the hash backend. Allocating saves try at most three times. One try can skip preallocation after seeing new_pool, then lose that pool to another save. A maximum-depth insertion can also need two new pools. Trie insertion failure returns 0 instead of consuming hash capacity. Extend stack_depot_fetch_into(), stack_depot_print(), and stack_depot_snprint() to support both backends. Keep stack_depot_fetch() hash-only because it returns a pointer to contiguous depot-owned storage. Print 16 frames at a time so stack use stays fixed instead of growing with CONFIG_STACKDEPOT_MAX_FRAMES. The hash and trie backends share stack_pools and the configured pool limit. A pool used by the trie is unavailable for hash-backed GET and COUNTABLE records. Hash handles reserve pool-index values through stack_depot_max_pools, and trie handles use the remaining values for stack IDs. With 64 KiB pages, the default limit leaves no values for trie IDs, so stack_depot_max_pools must be lowered before enabling the trie. Rename the persistent_count and persistent_bytes debugfs counters with a hash prefix because they do not include trie storage. Add the stackdepot.trie_enabled boot parameter and leave it disabled by default. Initialize the trie root before enabling the static key. If no handle values are available for trie IDs or allocating the root metadata fails, leave the hash backend initialized at its configured capacity. I collected stack depot state from four live KASAN servers using the same kernel revision, 4 KiB pages, and an 8,192-pool limit. The servers ran for 61 to 67 hours and remained active while the values were collected, so the figures below are rounded. arm64 x86-64 trie off trie on trie off trie on Run time (hours) 61 64 65 67 Stored records 162k 87k 498k 217k Registered pools 2,630 925 8,192 1,940 Pool budget used 32% 11% 100% 24% The servers ran different workloads and stored different traces, so this is not a controlled comparison. Exact memory savings depend on the workload. The trie figures came from RFC v1. That version did not insert a new trace when a save could not allocate, so RFC v2 may store more traces and use more pools than shown here. On arm64, the final allocator reduced the median number of bitmap probes from 36,939,363 to 1,529,482 without increasing pool use. The first-fit allocator used a median of 1,101 pools, while the final allocator used 1,100. I also pinned a benchmark to one CPU on KASAN-enabled arm64 and x86-64 systems running the Linux 6.18.48 port. It inserted 32,768 distinct 32-frame traces. Within each group of 64 traces, 75% of the frames were shared, and all frames could be compressed. The insertion order was shuffled. The warm save-hit and fetch tests then repeated the same traces 32 times. arm64 CPU ns/op x86-64 CPU ns/op hash trie hash trie Insertion 777 9,417 792 11,269 Warm save hit 945 1,287 623 1,012 Fetch 251 511 123 476 First insertion was about 12 times slower on arm64 and 14 times slower on x86-64. A warm save hit was 1.4 to 1.6 times slower, and fetch was 2 to 4 times slower. All four runs completed without save failures or validation errors. Signed-off-by: Caleb Kan --- Documentation/admin-guide/kernel-parameters.txt | 7 + include/linux/stackdepot.h | 23 +- lib/stackdepot.c | 1600 +++++++++++++++++++= +++- 3 files changed, 1616 insertions(+), 14 deletions(-) diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentatio= n/admin-guide/kernel-parameters.txt index 68647ff4bdd2..b02bcbaef5dc 100644 --- a/Documentation/admin-guide/kernel-parameters.txt +++ b/Documentation/admin-guide/kernel-parameters.txt @@ -7449,6 +7449,13 @@ Kernel parameters stack traces. Pools are allocated on-demand up to this limit. Default value is 8191 pools. =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/include/linux/stackdepot.h b/include/linux/stackdepot.h index 7ff67c70d727..3126d17b9265 100644 --- a/include/linux/stackdepot.h +++ b/include/linux/stackdepot.h @@ -151,6 +151,12 @@ static inline int stack_depot_early_init(void) { retur= n 0; } * 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 first look up an existing stack, then make= one + * best-effort insertion attempt without allocating. NMI callers stop afte= r the + * lookup. Other callers that cannot spin use trylocks and fail if a requi= red + * lock is unavailable. Trie failures do not fall back to hash storage. + * * If the provided stack trace comes from the interrupt context, only the = part * up to the interrupt entry is saved. * @@ -159,7 +165,7 @@ static inline int stack_depot_early_init(void) { return= 0; } * this is the case for contexts where neither %GFP_ATOMIC nor * %GFP_NOWAIT can be used (NMI, raw_spin_lock). * - * Return: Handle of the stack struct stored in depot, 0 on failure + * Return: Handle of the stack trace stored in depot, 0 on failure */ depot_stack_handle_t stack_depot_save_flags(unsigned long *entries, unsigned int nr_entries, @@ -176,6 +182,10 @@ depot_stack_handle_t stack_depot_save_flags(unsigned 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. * @@ -199,9 +209,14 @@ struct stack_record *__stack_depot_get_stack_record(de= pot_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, @@ -270,8 +285,8 @@ int stack_depot_snprint(depot_stack_handle_t handle, ch= ar *buf, size_t size, * * Drop a reference acquired by stack_depot_save_flags() with * %STACK_DEPOT_FLAG_GET. Calling this for a handle saved without - * %STACK_DEPOT_FLAG_GET is invalid; persistent handles are owned by stack= depot - * for the lifetime of the system. + * %STACK_DEPOT_FLAG_GET is invalid; persistent handles, including trie-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 diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 66c5e8594566..33e475d94131 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -2,9 +2,11 @@ /* * Stack depot - a stack trace storage that avoids duplication. * - * Internally, stack depot maintains a hash table of unique stacktraces. 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 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. @@ -14,13 +16,19 @@ =20 #define pr_fmt(fmt) "stackdepot: " fmt =20 +#include +#include #include +#include #include #include +#include #include +#include #include #include #include +#include #include #include #include @@ -36,9 +44,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 @@ -54,6 +65,9 @@ static bool __stack_depot_early_init_passed __initdata; /* Initial seed for jhash2. */ #define STACK_HASH_SEED 0x9747b28c =20 +/* Bound 64-bit print scratch to 128 bytes while amortizing trie walks. */ +#define STACK_DEPOT_PRINT_CHUNK_FRAMES 16 + /* Hash table of stored stack records. */ static struct list_head *stack_table; /* Fixed order of the number of table buckets. Used when KASAN is enabled.= */ @@ -63,18 +77,18 @@ static unsigned int stack_hash_mask; =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, @@ -90,12 +104,695 @@ 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); + +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); =20 +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) + +static_assert(STACK_DEPOT_TRIE_POOL_SLOTS - 1 <=3D U16_MAX); + +struct stack_depot_trie_pool { + struct list_head list; + unsigned int free_slots; + /* Conservative upper bound on the largest free run. */ + u16 free_run_upper_bound; + /* First physical slot considered by the next reservation. */ + u16 next_slot; + DECLARE_BITMAP(used, STACK_DEPOT_TRIE_POOL_SLOTS); +}; + +#define STACK_DEPOT_TRIE_POOL_FIRST_SLOT \ + DIV_ROUND_UP(sizeof(struct stack_depot_trie_pool), \ + STACK_DEPOT_TRIE_SLOT_SIZE) +#define STACK_DEPOT_TRIE_POOL_USABLE_SIZE \ + ((STACK_DEPOT_TRIE_POOL_SLOTS - STACK_DEPOT_TRIE_POOL_FIRST_SLOT) * \ + STACK_DEPOT_TRIE_SLOT_SIZE) + +static_assert(STACK_DEPOT_TRIE_POOL_FIRST_SLOT < STACK_DEPOT_TRIE_POOL_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); +static bool stack_depot_trie_requested; + +module_param_named(trie_enabled, stack_depot_trie_requested, bool, 0); +MODULE_PARM_DESC(trie_enabled, "Enable stack depot trie storage at boot"); + +#define DEPOT_POOL_INDEX_MASK ((1U << DEPOT_POOL_INDEX_BITS) - 1) +#define DEPOT_OFFSET_MASK ((1U << DEPOT_OFFSET_BITS) - 1) + +/* Retired fixed-size slots remain reserved until their RCU grace period 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. 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 *)) +#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 -> side-table cache lock. */ + +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()); +} + +/* Published capacity remains useful if insertion fails and needs no rollb= ack. */ +static bool +trie_side_table_try_take_cache(struct stack_depot_trie_side_prealloc *prea= lloc, + bool need_dir) +{ + bool taken =3D false; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + lockdep_assert_held(&pool_lock); + + if (!raw_spin_trylock(&trie_side_table_cache_lock)) + return false; + if ((!prealloc->chunk && !trie_side_table_cache.chunk) || + (need_dir && !prealloc->dir && !trie_side_table_cache.dir)) + goto out_unlock; + + if (need_dir && !prealloc->dir) { + prealloc->dir =3D trie_side_table_cache.dir; + trie_side_table_cache.dir =3D NULL; + } + if (!prealloc->chunk) { + prealloc->chunk =3D trie_side_table_cache.chunk; + trie_side_table_cache.chunk =3D NULL; + } + taken =3D true; + +out_unlock: + raw_spin_unlock(&trie_side_table_cache_lock); + return taken; +} + +static u32 +trie_side_table_prepare_stack_slot(struct stack_depot_trie_side_prealloc *= prealloc) +{ + const struct stack_depot_trie_node __rcu **chunk; + struct stack_depot_trie_side_dir *dir; + struct stack_depot_trie_side_root *root_vec; + unsigned int root; + unsigned int idx; + u32 id; + + lockdep_assert_held(&stack_depot_trie_writer_lock); + lockdep_assert_held(&pool_lock); + + id =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) { + if ((!prealloc->dir || !prealloc->chunk) && + !trie_side_table_try_take_cache(prealloc, true)) + return 0; + 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) { + if (!prealloc->chunk && + !trie_side_table_try_take_cache(prealloc, false)) + return 0; + chunk =3D prealloc->chunk; + prealloc->chunk =3D NULL; + rcu_assign_pointer(dir->chunks[idx], chunk); + } + + return id; +} + +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, roo= t_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; + size_t root_bytes; + 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_bytes =3D struct_size_t(struct stack_depot_trie_side_root, dirs, roo= t_size); + root_vec =3D kvzalloc(root_bytes, GFP_KERNEL); + 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) +{ + 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 start =3D pool->next_slot; + unsigned int run =3D 0; + unsigned int longest_run =3D 0; + unsigned int i; + unsigned int slot; + +scan: + run =3D 0; + longest_run =3D 0; + for (slot =3D start; slot < STACK_DEPOT_TRIE_POOL_SLOTS; slot++) { + if (pool->used[slot / BITS_PER_LONG] & + BIT(slot % BITS_PER_LONG)) { + run =3D 0; + continue; + } + run++; + longest_run =3D max(longest_run, run); + 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; + if (slot + 1 =3D=3D STACK_DEPOT_TRIE_POOL_SLOTS) + pool->next_slot =3D STACK_DEPOT_TRIE_POOL_FIRST_SLOT; + else + pool->next_slot =3D slot + 1; + return slot + 1 - nr_slots; + } + + if (start !=3D STACK_DEPOT_TRIE_POOL_FIRST_SLOT) { + /* Keep holes and runs crossing the cursor visible. */ + start =3D STACK_DEPOT_TRIE_POOL_FIRST_SLOT; + goto scan; + } + + pool->free_run_upper_bound =3D longest_run; + return STACK_DEPOT_TRIE_POOL_SLOTS; +} + +/* Allocate at least @size bytes from one contiguous trie-pool slot run. */ +static void *trie_pool_alloc(size_t size, void **prealloc) +{ + struct stack_depot_trie_pool *pool; + unsigned int nr_slots; + unsigned int slot; + + lockdep_assert_held(&pool_lock); + + if (size > STACK_DEPOT_TRIE_POOL_USABLE_SIZE) + return NULL; + nr_slots =3D DIV_ROUND_UP(size, STACK_DEPOT_TRIE_SLOT_SIZE); + list_for_each_entry_reverse(pool, &stack_depot_trie_pools, list) { + if (pool->free_slots < nr_slots || + pool->free_run_upper_bound < nr_slots) + continue; + slot =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; + pool->free_run_upper_bound =3D pool->free_slots; + pool->next_slot =3D 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; + /* A release can join at most two runs bounded by the old value. */ + pool->free_run_upper_bound =3D min(pool->free_slots, + 2 * pool->free_run_upper_bound + nr_slots); +} + +static struct stack_depot_trie_children * +trie_pool_alloc_children(unsigned int capacity, void **prealloc) +{ + struct stack_depot_trie_retired_children *retired; + struct stack_depot_trie_children *children; + + /* Capacity counts child-pointer entries; allocation includes RCU 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); + lockdep_assert_held(&pool_lock); + trie_retire_children(children); + retired =3D trie_retired_children(children); + retired->pending_node =3D node; +} + +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); @@ -147,7 +844,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; @@ -221,11 +918,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); @@ -279,6 +980,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: @@ -643,6 +1353,101 @@ 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); + raw_spin_lock(&pool_lock); + printk_deferred_enter(); + trie_drain_pending_children(); + stack_id =3D stack_depot_trie_insert(entries, nr_entries, + &pool_prealloc, &side_prealloc); + if (pool_prealloc) + depot_keep_new_pool(&pool_prealloc); + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags); + + if (pool_prealloc) + free_pages((unsigned long)pool_prealloc, DEPOT_POOL_ORDER); + trie_side_table_put_prealloc(&side_prealloc); + if (stack_id) + return trie_handle(stack_id); + } + + return 0; +} + +static depot_stack_handle_t +stack_depot_trie_save_constrained(unsigned long *entries, + unsigned int nr_entries, bool trylock) +{ + struct stack_depot_trie_side_prealloc side_prealloc =3D {}; + void *pool_prealloc =3D NULL; + depot_stack_handle_t handle; + unsigned long flags; + u32 stack_id; + + handle =3D trie_find_handle(entries, nr_entries); + if (handle) + return handle; + + if (trylock) { + if (!raw_spin_trylock_irqsave(&stack_depot_trie_writer_lock, flags)) + return 0; + if (!raw_spin_trylock(&pool_lock)) { + raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags); + return 0; + } + } else { + raw_spin_lock_irqsave(&stack_depot_trie_writer_lock, flags); + raw_spin_lock(&pool_lock); + } + + printk_deferred_enter(); + stack_id =3D stack_depot_trie_insert(entries, nr_entries, &pool_prealloc, + &side_prealloc); + printk_deferred_exit(); + raw_spin_unlock(&pool_lock); + raw_spin_unlock_irqrestore(&stack_depot_trie_writer_lock, flags); + + return stack_id ? trie_handle(stack_id) : 0; +} + depot_stack_handle_t stack_depot_save_flags(unsigned long *entries, unsigned int nr_entries, gfp_t alloc_flags, @@ -677,6 +1482,20 @@ depot_stack_handle_t stack_depot_save_flags(unsigned = long *entries, if (unlikely(nr_entries =3D=3D 0) || stack_depot_disabled) return 0; =20 + 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; + if (in_nmi()) { + WARN_ON_ONCE(can_alloc); + return trie_find_handle(entries, nr_entries); + } + if (!can_alloc) + return stack_depot_trie_save_constrained(entries, nr_entries, + !allow_spin); + return stack_depot_trie_save(entries, nr_entries, alloc_flags); + } + hash =3D hash_stack(entries, nr_entries); bucket =3D &stack_table[hash & stack_hash_mask]; =20 @@ -763,6 +1582,8 @@ struct stack_record *__stack_depot_get_stack_record(de= pot_stack_handle_t handle) =20 if (!handle) return NULL; + if (WARN_ON_ONCE(stack_depot_handle_is_trie(handle))) + return NULL; =20 stack =3D depot_fetch_stack(handle); if (!stack) @@ -773,6 +1594,714 @@ struct stack_record *__stack_depot_get_stack_record(= depot_stack_handle_t handle) return stack; } =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; + + /* 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); + } + + return new_stack_id; + +err_release: + if (new_children) + trie_pool_release_children(new_children); + return 0; +} + +static u32 +trie_split_child(const struct stack_depot_trie_children __rcu **slot, + const struct stack_depot_trie_children *children, + const struct stack_depot_trie_node *child, + unsigned int pos, unsigned int matched, + const unsigned long *entries, unsigned int nr_entries, + void **pool_prealloc, + struct stack_depot_trie_side_prealloc *side_prealloc) +{ + struct stack_depot_trie_children *prefix_children =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; + + /* 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; + } + + /* 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); + 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.= */ + promoted_node =3D trie_pool_alloc(node_size, pool_prealloc); + if (!promoted_node) + return 0; + new_children =3D trie_pool_alloc_children(children->capacity, pool_preall= oc); + if (!new_children) + goto out_release_node; + + /* Add the stack ID through a clone, then reparent before retirement. */ + memcpy(promoted_node, child, node_size); + promoted_node->stack_id =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); + 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); + lockdep_assert_held(&pool_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_range(const struct stack_depot_trie_node *n= ode, + unsigned int offset, + unsigned long *entries, + unsigned int max_entries) +{ + const struct stack_depot_trie_node *cur; + unsigned int end; + unsigned int start; + unsigned int total; + unsigned int pos; + unsigned int i; + + total =3D 0; + for (cur =3D node; cur; cur =3D trie_load_parent(cur)) + total +=3D cur->run.nr_entries; + if (offset >=3D total) + return 0; + + max_entries =3D min(max_entries, total - offset); + end =3D offset + max_entries; + pos =3D total; + for (cur =3D node; cur; cur =3D trie_load_parent(cur)) { + pos -=3D cur->run.nr_entries; + start =3D max(pos, offset); + for (i =3D start; i < min(pos + cur->run.nr_entries, end); i++) + stack_depot_trie_node_frame(cur, i - pos, &entries[i - offset]); + } + + return max_entries; +} + +static unsigned int trie_fetch_handle_into(depot_stack_handle_t handle, + unsigned long *entries, + unsigned int max_entries) +{ + const struct stack_depot_trie_node *node; + u32 stack_id; + unsigned int nr_entries; + + stack_id =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; +} + +static unsigned int trie_fetch_handle_range(depot_stack_handle_t handle, + unsigned int offset, + unsigned long *entries, + unsigned int max_entries) +{ + const struct stack_depot_trie_node *node; + u32 stack_id; + unsigned int nr_entries; + + stack_id =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_range(node, offset, entries, max_entries); + rcu_read_unlock_sched_notrace(); + if (nr_entries) + kmsan_unpoison_memory(entries, nr_entries * sizeof(*entries)); + + return nr_entries; +} + unsigned int stack_depot_fetch(depot_stack_handle_t handle, unsigned long **entries) { @@ -787,6 +2316,8 @@ unsigned int stack_depot_fetch(depot_stack_handle_t 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); /* @@ -813,6 +2344,8 @@ unsigned int stack_depot_fetch_into(depot_stack_handle= _t handle, if (stack_depot_disabled) return 0; WARN_ON_ONCE(!entries || !max_entries); + if (stack_depot_handle_is_trie(handle)) + return trie_fetch_handle_into(handle, entries, max_entries); =20 stack =3D depot_fetch_stack(handle); if (!stack) @@ -835,6 +2368,8 @@ void stack_depot_put(depot_stack_handle_t handle) =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); /* @@ -851,11 +2386,53 @@ void stack_depot_put(depot_stack_handle_t handle) } EXPORT_SYMBOL_GPL(stack_depot_put); =20 +static void trie_print(depot_stack_handle_t handle) +{ + unsigned long entries[STACK_DEPOT_PRINT_CHUNK_FRAMES]; + unsigned int nr_entries; + unsigned int offset =3D 0; + + while ((nr_entries =3D trie_fetch_handle_range(handle, offset, entries, + ARRAY_SIZE(entries)))) { + stack_trace_print(entries, nr_entries, 0); + offset +=3D nr_entries; + } +} + +static int trie_snprint(depot_stack_handle_t handle, char *buf, size_t siz= e, + int spaces) +{ + unsigned long entries[STACK_DEPOT_PRINT_CHUNK_FRAMES]; + unsigned int generated; + unsigned int nr_entries; + unsigned int offset =3D 0; + unsigned int total =3D 0; + + while (size && + (nr_entries =3D trie_fetch_handle_range(handle, offset, entries, + ARRAY_SIZE(entries)))) { + generated =3D stack_trace_snprint(buf, size, entries, nr_entries, spaces= ); + total +=3D generated; + if (generated >=3D size) + break; + buf +=3D generated; + size -=3D generated; + offset +=3D nr_entries; + } + + return total; +} + void stack_depot_print(depot_stack_handle_t stack) { unsigned long *entries; unsigned int nr_entries; =20 + if (stack_depot_handle_is_trie(stack)) { + trie_print(stack); + return; + } + nr_entries =3D stack_depot_fetch(stack, &entries); if (nr_entries > 0) stack_trace_print(entries, nr_entries, 0); @@ -868,6 +2445,9 @@ int stack_depot_snprint(depot_stack_handle_t handle, c= har *buf, size_t size, unsigned long *entries; unsigned int nr_entries; =20 + if (stack_depot_handle_is_trie(handle)) + return trie_snprint(handle, buf, size, 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 Fri Sep 25 21:40:23 2026 Received: from mail-ej1-f51.google.com (mail-ej1-f51.google.com [209.85.218.51]) (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 BA3EB54856C for ; Tue, 8 Sep 2026 13:14:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873253; cv=none; b=q1yl4Y91uiKHmxQyGYdnoUy8zTnoGQO3DWUiE3mkwM7aXjqf55fPY8ZEXKzgdlVn4SUkyQGXogADsMk0Mdk/CppnbA1cH68Br3aLvrWdV7FrNSFmdKCBHBbEOkfaTrLFMKnkk4RRUzLSywa61Mnu6uPm0AmU6rsGrzP+f0w3iW0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788873253; c=relaxed/simple; bh=D/H0Upa3SUn7yIlo6iHvitjtLWrcz3qJcknh1OxLSNU=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Bz2DVFtuSyOzsc+U1VAhHdHyHXBautTkr8KQbshyc2uYdH1LCqoa18ZMUY050/Kbp50v9d2weml9pFoXewNTLI/uaNGhxeHdePBDu+HEZaW4u/v6uAFr21N4fz9uZxYRFcufMkG745+4sE549iAdsSrqwir36A/eair4NYhdQpM= 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=bJe6GzCx; arc=none smtp.client-ip=209.85.218.51 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="bJe6GzCx" Received: by mail-ej1-f51.google.com with SMTP id a640c23a62f3a-c2055573c8cso598335866b.3 for ; Tue, 08 Sep 2026 06:14:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788873243; x=1789478043; 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=WAyR6h5/4ojoKsK6CQz1j0Z55ZNB06yaKFwRajx+NlY=; b=bJe6GzCxGT0eMihDyrFTaxaD0V3sqA5UUcOtObytgTqHjxSH1iPCF3x0w+UTwOgiwS Dg7GESMLWyV0wTgxx5mskyox1cnnIKhdWPPWy+bKzcvUPc+j9T+3s8JmhVzCBcrC+teL pyALMoKCM72MrmdYBjKJT8le0vbaNmfMHJ8PScyyP9yNlZjXVzGCWI/hQS+Zux2Hi0bt e741QUS8iij7eZrwIi0JE5S3bf4+cV33KPrHW8rRSxli2TMeU9XgOOHpKsW3TSGmDbES BwaeslIT5rGlC1H0K/zl5pm8ni28aVZ+k2Yy3za1ZCJ/gNVnrjzmgXiOOO0tQ67Z4uzC c1jg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788873243; x=1789478043; 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=WAyR6h5/4ojoKsK6CQz1j0Z55ZNB06yaKFwRajx+NlY=; b=IPNCUgH4W/PY1FO5XggaeREHppZTy87VD0h69pmpMAaelMWhXuakA4gX05/GBJ9r6m gu31aMj62jlUGMuXAFOfWsY2Y6oG6ByBrTfDKu+sHrTVtjp0zVPCPKf+3JZIn+g766jL LP0aJaLi/LtlA5IZdgb/SFIbVC2syNMuIXucD/LdWndgNgZfw2UGAk8J6QRNPtaAJakT S9lrlt3nC87cLv2YT8APQUIO52PIBpgzT47sVEQc9I23crvh8R3yD2ZHaufKQYdKOLVe m+QF69rlQYhbTf4j09gmx6tONJRhI+gw4j3pcwS03/MuscJtmnYfP287kXx7bxD3mrbv 1k9Q== X-Forwarded-Encrypted: i=1; AKwUvByTfNuF3W/TGXUoKBcI/mbJIoO8RJ8a5c4CGVzK0QbSmkLKQ+tYI+RrncXh/UD0Q+9ioRaRMYcuOqY+liE=@vger.kernel.org X-Gm-Message-State: AFuF++mHlq9rPv9+MEd5WxtcRPHgYsKwE6b1AnJBEFgHZkxOOPT7mPxs D9hIH39oOOidcP9ICgnYneOYsIR37zZkbNaAu/C5ni2f+AeUSsrw2pju X-Gm-Gg: AYBFou1Tk1kCiWflVkXOzBXdHaNQ+0oYyFKSWsFXl52kAXtSuTJadJBhu9fdZbVi9oE 3OF/c9kRSLrUUzR3kW5rkr+pRcpfSBSilonUj8LF5SVVjXVS7/qckcC9a5D5MRygl0InrgbQuxo R4VMpy3kKXdMV3FvPaqbI0v0cQ3ciL/QZD6n36jr0x+OkVMwjuGGhli8c2C3wN8O3wkO3g+1Yak n6rH047zdB8rYLdRRVlWhNHlnQd81Wd/e6pfEvckyxxdYGlwBvBbac/NvCZxud28h3udHI/c1WO dANiAL0RJorFmFPhvALD1jX9s3PhgCXVjrwr5iI15fdRbOAxkqWO66BMGfx6CIjHPxaSBJgBVUH JsOdTj7IQbtnyNlQTqy6SL95CKWq662uQ4IlvqVeXZ1UZtVYTpiz7U0FTFLZbvcL8Wop7ckQxLX NlPYeVCGPY5YH/CWQPiNBBi921XBnVMbV0N6rIgp7uyFVKn10AfKQYqujHkYoX X-Received: by 2002:a17:907:7287:b0:c26:1649:47b0 with SMTP id a640c23a62f3a-c261649564fmr960747966b.38.1788873243007; Tue, 08 Sep 2026 06:14:03 -0700 (PDT) Received: from [127.0.0.1] ([2a09:bac6:37a9:1e5a::306:1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c260d6e1c93sm625170866b.63.2026.09.08.06.14.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Sep 2026 06:14:02 -0700 (PDT) From: Caleb Kan Date: Tue, 08 Sep 2026 14:13:44 +0100 Subject: [PATCH RFC v2 11/11] 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: <20260908-stackdepot-trie-v2-11-1996d5cef732@cloudflare.com> References: <20260908-stackdepot-trie-v2-0-1996d5cef732@cloudflare.com> In-Reply-To: <20260908-stackdepot-trie-v2-0-1996d5cef732@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 changes shared topology, but handles returned before later splits, promotions, and child-array replacements must continue to fetch and deduplicate the same traces. Extend the built-in stack depot KUnit suite to test trie storage through the public APIs and direct insertion cases. The public cases continue to run against the hash backend by default and exercise the trie when it is enabled. Cover save and deduplication behavior, maximum-depth and overlong stacks, insertion when allocation is not permitted, GET records, extra bits, caller-owned fetching, and complete and truncated formatted output. Exercise append, descent, split, promotion, child-array growth, and tail-append paths. Verify that handles returned before these changes still fetch the same trace and are returned again when that trace is saved. Add round-trip tests for compressed and full-width frames on arm64 and native x86-64, plus an architecture-independent full-width test. Keep the topology fixtures portable to 32-bit architectures. On 4 KiB arm64 and native x86-64 builds configured for 256 frames, a maximum-depth trace that alternates compressed and full-width frames creates one node per frame and requires more space than one otherwise-empty trie pool. Require stackdepot_kunit.trie_pool_limit to match the stack_depot_max_pools value used at boot before running trie-only cases. This makes backend selection explicit and prevents an initialization failure from silently running the hash tests instead. The save-flags and snprint cases also check that saves return trie handles when a trie pool limit is supplied. Signed-off-by: Caleb Kan --- lib/tests/stackdepot_kunit.c | 352 +++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 352 insertions(+) diff --git a/lib/tests/stackdepot_kunit.c b/lib/tests/stackdepot_kunit.c index e4a7f1c83457..b86b84d56176 100644 --- a/lib/tests/stackdepot_kunit.c +++ b/lib/tests/stackdepot_kunit.c @@ -3,12 +3,19 @@ #include #include #include +#include #include +#include #include +#include #include =20 #include =20 +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 =20 @@ -18,6 +25,222 @@ static inline unsigned long stackdepot_arm64_frame(long= offset) } #endif =20 +static unsigned long stackdepot_test_frame(unsigned int i) +{ +#ifdef CONFIG_ARM64 + return i & 1 ? 0x1000UL + i * 0x1000UL : + stackdepot_arm64_frame(i * 4); +#elif defined(CONFIG_X86_64) && !defined(CONFIG_UML) + return i & 1 ? 0xffff888000000000UL + i * 0x1000UL : + 0xffffffff10000000UL + i * 0x10UL; +#else + return 0x1000UL + i * 0x1000UL; +#endif +} + +static void stackdepot_trie_max_path_roundtrip(struct kunit *test) +{ + union handle_parts parts; + unsigned long *entries; + unsigned long *fetched; + depot_stack_handle_t handle; + size_t size =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++) + entries[i] =3D stackdepot_test_frame(i); + + 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) +{ + union handle_parts parts; + unsigned long entries[] =3D { 0x501000UL, 0x502000UL, 0x503000UL }; + unsigned long get_entries[] =3D { 0x601000UL, 0x602000UL }; + unsigned long missing_entries[] =3D { 0x701000UL, 0x702000UL }; + unsigned long blocking_entries[] =3D { 0x711000UL, 0x712000UL }; + unsigned long fetched[ARRAY_SIZE(entries)] =3D {}; + depot_stack_handle_t blocking_handle; + depot_stack_handle_t noalloc_handle; + depot_stack_handle_t overlong_handle; + depot_stack_handle_t plain_handle; + depot_stack_handle_t get_handle; + depot_stack_handle_t again; + depot_stack_handle_t extra; + gfp_t no_spin =3D GFP_NOWAIT & ~__GFP_RECLAIM; + u32 pool_index_plus_1; + 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); + noalloc_handle =3D stack_depot_save_flags(missing_entries, + ARRAY_SIZE(missing_entries), + GFP_KERNEL, 0); + KUNIT_ASSERT_NE(test, noalloc_handle, (depot_stack_handle_t)0); + if (expected_trie_pool_limit >=3D 0) { + parts.handle =3D noalloc_handle; + pool_index_plus_1 =3D parts.pool_index_plus_1; + KUNIT_EXPECT_GT(test, pool_index_plus_1, + (u32)expected_trie_pool_limit); + } + nr_entries =3D stack_depot_fetch_into(noalloc_handle, fetched, + ARRAY_SIZE(fetched)); + KUNIT_EXPECT_EQ(test, nr_entries, + (unsigned int)ARRAY_SIZE(missing_entries)); + KUNIT_EXPECT_MEMEQ(test, fetched, missing_entries, sizeof(missing_entries= )); + KUNIT_EXPECT_EQ(test, + stack_depot_save_flags(missing_entries, + ARRAY_SIZE(missing_entries), + no_spin, 0), + noalloc_handle); + + blocking_handle =3D stack_depot_save_flags(blocking_entries, + ARRAY_SIZE(blocking_entries), + GFP_KERNEL, 0); + KUNIT_ASSERT_NE(test, blocking_handle, (depot_stack_handle_t)0); + if (expected_trie_pool_limit >=3D 0) { + parts.handle =3D blocking_handle; + pool_index_plus_1 =3D parts.pool_index_plus_1; + KUNIT_EXPECT_GT(test, pool_index_plus_1, + (u32)expected_trie_pool_limit); + } + memset(fetched, 0, sizeof(fetched)); + nr_entries =3D stack_depot_fetch_into(blocking_handle, fetched, + ARRAY_SIZE(fetched)); + KUNIT_EXPECT_EQ(test, nr_entries, + (unsigned int)ARRAY_SIZE(blocking_entries)); + KUNIT_EXPECT_MEMEQ(test, fetched, blocking_entries, + sizeof(blocking_entries)); + + get_handle =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) +{ + const unsigned int nr_entries =3D CONFIG_STACKDEPOT_MAX_FRAMES; + const size_t buf_size =3D nr_entries * (KSYM_SYMBOL_LEN + 4); + unsigned long *entries; + char *expected; + char *actual; + depot_stack_handle_t handle; + unsigned int expected_len; + unsigned int prefix_entries; + unsigned int prefix_len; + size_t output_size; + unsigned int i; + int actual_len; + + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + entries =3D kunit_kmalloc_array(test, nr_entries, sizeof(*entries), + GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, entries); + expected =3D kunit_kzalloc(test, buf_size, GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, expected); + actual =3D kunit_kzalloc(test, buf_size, GFP_KERNEL); + KUNIT_ASSERT_NOT_NULL(test, actual); + for (i =3D 0; i < nr_entries; i++) + entries[i] =3D stackdepot_test_frame(i); + + handle =3D stack_depot_save(entries, nr_entries, GFP_KERNEL); + KUNIT_ASSERT_NE(test, handle, (depot_stack_handle_t)0); + if (expected_trie_pool_limit >=3D 0) { + union handle_parts parts =3D { .handle =3D handle }; + + KUNIT_EXPECT_GT(test, (u32)parts.pool_index_plus_1, + (u32)expected_trie_pool_limit); + } + expected_len =3D stack_trace_snprint(expected, buf_size, entries, + nr_entries, 2); + actual_len =3D stack_depot_snprint(handle, actual, buf_size, 2); + KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len); + KUNIT_EXPECT_STREQ(test, actual, expected); + + prefix_entries =3D nr_entries / 2 + 1; + prefix_len =3D stack_trace_snprint(expected, buf_size, entries, + prefix_entries, 2); + KUNIT_ASSERT_LE(test, (size_t)prefix_len + 2, buf_size); + output_size =3D prefix_len + 2; + memset(expected, 0, buf_size); + memset(actual, 0, buf_size); + expected_len =3D stack_trace_snprint(expected, output_size, entries, + nr_entries, 2); + actual_len =3D stack_depot_snprint(handle, actual, output_size, 2); + KUNIT_EXPECT_EQ(test, actual_len, (int)expected_len); + KUNIT_EXPECT_STREQ(test, actual, expected); +} + static void stackdepot_countable_public(struct kunit *test) { unsigned long plain_entries[] =3D { @@ -137,6 +360,129 @@ static void stackdepot_fetch_into_rejects_missing_or_= short_stack(struct kunit *t KUNIT_EXPECT_MEMEQ(test, fetched, expected, sizeof(expected)); } =20 +static void stackdepot_trie_topology_roundtrip(struct kunit *test, + bool constrained) +{ + union handle_parts parts; + unsigned long seed[] =3D { 0x191000UL, 0x192000UL }; + 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)]; + depot_stack_handle_t seed_handle; + unsigned long fetched[ARRAY_SIZE(stacks[0])]; + gfp_t no_spin =3D GFP_NOWAIT & ~__GFP_RECLAIM; + u32 pool_index_plus_1; + unsigned int j; + unsigned int i; + + if (expected_trie_pool_limit < 0) + kunit_skip(test, "trie pool limit was not provided"); + KUNIT_ASSERT_EQ(test, stack_depot_init(), 0); + if (constrained) { + seed_handle =3D stack_depot_save(seed, ARRAY_SIZE(seed), GFP_KERNEL); + KUNIT_ASSERT_NE(test, seed_handle, (depot_stack_handle_t)0); + for (i =3D 0; i < ARRAY_SIZE(stacks); i++) + for (j =3D 0; j < nr_entries[i]; j++) + stacks[i][j] +=3D 0x10000000UL; + } + + for (i =3D 0; i < ARRAY_SIZE(stacks); i++) { + if (constrained) + handles[i] =3D stack_depot_save_flags(stacks[i], nr_entries[i], + GFP_KERNEL, 0); + else + 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])); + if (constrained) + KUNIT_EXPECT_EQ(test, + stack_depot_save_flags(stacks[i], nr_entries[i], + no_spin, 0), + handles[i]); + else + KUNIT_EXPECT_EQ(test, + stack_depot_save(stacks[i], nr_entries[i], + GFP_KERNEL), + handles[i]); + } +} + +static void stackdepot_trie_topology_allocating(struct kunit *test) +{ + stackdepot_trie_topology_roundtrip(test, false); +} + +static void stackdepot_trie_topology_constrained(struct kunit *test) +{ + stackdepot_trie_topology_roundtrip(test, true); +} + +static void stackdepot_frame_storage_roundtrip(struct kunit *test) +{ + union handle_parts parts; + unsigned long fetched[3] =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; @@ -205,9 +551,15 @@ static void stackdepot_frame_arm64(struct kunit *test) #endif /* CONFIG_ARM64 */ =20 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_allocating), + KUNIT_CASE(stackdepot_trie_topology_constrained), + KUNIT_CASE(stackdepot_frame_storage_roundtrip), KUNIT_CASE(stackdepot_frame_raw_fallback), #if defined(CONFIG_X86_64) && !defined(CONFIG_UML) KUNIT_CASE(stackdepot_frame_x86_64), --=20 Git-155)