* [PATCH 1/2] tracing: fgraph: Raise FTRACE_RETSTACK_ALLOC_SIZE to 1024
2026-09-22 22:55 [PATCH 0/2] tracing: fgraph: cut the cost of the shadow stack retry loop Vineet Gupta
@ 2026-09-22 22:55 ` Vineet Gupta
2026-09-22 22:55 ` [PATCH 2/2] tracing: fgraph: Add a cond_resched() to the shadow stack retry loop Vineet Gupta
1 sibling, 0 replies; 4+ messages in thread
From: Vineet Gupta @ 2026-09-22 22:55 UTC (permalink / raw)
To: rostedt, mhiramat
Cc: mark.rutland, mathieu.desnoyers, andrii, peterz,
linux-trace-kernel, linux-kernel, bpf, kernel-team, Vineet Gupta,
stable
When ftrace graphing is turned on, all tasks in the system missing
return stack page are assigned one. This is done in a simplistic
multi-sweep loop of FTRACE_RETSTACK_ALLOC_SIZE (currently 32) tasks
at a time as follows:
start_graph_tracing()
do {
alloc_retstack_tasklist
} while (-EAGAIN);
alloc_retstack_tasklist()
alloc x32 # GFP_KERNEL, may sleep
rcu_read_lock() # preempt off
for_each_process_thread walk N_total, no cond_resched
t->ret_stack = new_page
rcu_read_unlock() # preempt enable but no explicit yield
Each successive iteration of loop invokes for_each_process_thread()
which doesn't support cursor based resume and always restarts from the
init_task. Thus each successive loop needs to skip the tasks assigned
ret_stack in prior sweeps and thus take longer and longer to find the
candidate 32 tasks. And while the loop end calls rcu unlock,
and re-enables preemption briefly, there is no explicit yield.
The total number of iterations turn out to be
N_total * N_null / (2 * FTRACE_RETSTACK_ALLOC_SIZE)
where N_total is the number of threads on the system and N_null the number
of those whose ret_stack is still NULL. After boot with no fgraph user that
is every thread.
This is not a tracing-only path. Since commit 4346ba160409 ("fprobe:
Rewrite fprobe on function-graph tracer") fprobe is built on fgraph,
so an ordinary kprobe_multi BPF attach that flips ftrace_graph_active
from 0 to 1 pays the whole cost inside one bpf() syscall. Commit
2c67dc457bc6 ("tracing: fprobe: optimization for entry only case")
narrows that to return and session probes but does not remove it.
A host running hundreds of thousands of threads, with the current batch
size of 32, turns the ftrace_graph_active 0 -> 1 transition into a
multi-second, and eventually multi-minute, operation which showed up as
RCU stall and softlockup_panic on heavily loaded Meta Fleet machines
with preemption disabled.
rcu: INFO: rcu_sched self-detected stall on CPU
rcu: 0-....: (20718 ticks this GP) (t=21000 jiffies g=913 q=8 ncpus=8)
CPU: 0 UID: 0 PID: 160141 Comm: bpftrace
___slab_alloc+0x549/0xa20
kmem_cache_alloc_noprof+0x16c/0x340
register_ftrace_graph+0x3d7/0x6c0
register_fprobe_ips+0x2d5/0x310
bpf_kprobe_multi_link_attach+0x218/0x7e0
__sys_bpf+0x267a/0x27a0
Fix this by raising the batch to 1024.
Measured on a 60-core Sapphire Rapids machine, running a PREEMPT_LAZY
kernel (CONFIG_PREEMPT_DYNAMIC=y, mode lazy) timing the write that
drives the ftrace_graph_active 0 -> 1 transition. Threads are spawned
while fgraph is inactive so every one of them has ret_stack == NULL,
and the loop was instrumented to count passes:
threads batch 32 batch 1024
passes time passes time speedup
100000 3126 15.3 s 98 0.44 s 34.8x
200000 6253 59.1 s 196 1.61 s 36.7x
400000 12503 227.8 s 391 7.25 s 31.4x
At smaller thread counts (<= 200k), speedups are better than expected
due to cache locality, and degrade at 400k threads due to cache misses.
This is a latency fix, specially on preemptible kernels.
On !CONFIG_PREEMPTION builds, where the walk is not preemptible, the
same loop additionally produces RCU stall and soft lockup splats;
those are a separate problem, and raising the batch only helps there
by making the operation too short to trip the thresholds.
The cost is a larger allocation burst. Shadow stacks are
SHADOW_STACK_SIZE (4K) each, so a batch is a 4M GFP_KERNEL burst out
of fgraph_stack_cachep taken while ftrace_lock and fprobe_mutex are
held, and the pointer array kcalloc()'d by start_graph_tracing() grows
from 256 bytes to 8K. Both are still ordinary kmalloc sizes, and any
unused tail of the batch is freed at the end of the pass as before.
1024 was picked to keep that array a single order-1 allocation; going
much higher would need kvmalloc.
This is a constant-factor improvement, not a cure: the retry loop
stays O(N_total * N_null), so wall time still grows quadratically with
the thread count and the batch will need revisiting as hosts get
bigger. Making the walk resume from a cursor instead of restarting
from the head would fix this properly, but task_struct lifetime makes
it considerably more involved, so it is left for later.
Fixes: f201ae2356c7 ("tracing/function-return-tracer: store return stack into task_struct and allocate it dynamically")
Cc: stable@vger.kernel.org
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
include/linux/ftrace.h | 7 ++++++-
1 file changed, 6 insertions(+), 1 deletion(-)
diff --git a/include/linux/ftrace.h b/include/linux/ftrace.h
index bd76a16a63af..d2f8e433ce53 100644
--- a/include/linux/ftrace.h
+++ b/include/linux/ftrace.h
@@ -1317,7 +1317,12 @@ unsigned long *fgraph_get_task_var(struct fgraph_ops *gops);
#define __notrace_funcgraph notrace
#define FTRACE_RETFUNC_DEPTH 50
-#define FTRACE_RETSTACK_ALLOC_SIZE 32
+/*
+ * Batch for handing out Shadow stacks in one sweep.
+ * This bounds how many times task list is walked and the allocation
+ * burst given page size of 4K.
+ */
+#define FTRACE_RETSTACK_ALLOC_SIZE 1024
extern int register_ftrace_graph(struct fgraph_ops *ops);
extern void unregister_ftrace_graph(struct fgraph_ops *ops);
--
2.53.0-Meta
^ permalink raw reply [flat|nested] 4+ messages in thread* [PATCH 2/2] tracing: fgraph: Add a cond_resched() to the shadow stack retry loop
2026-09-22 22:55 [PATCH 0/2] tracing: fgraph: cut the cost of the shadow stack retry loop Vineet Gupta
2026-09-22 22:55 ` [PATCH 1/2] tracing: fgraph: Raise FTRACE_RETSTACK_ALLOC_SIZE to 1024 Vineet Gupta
@ 2026-09-22 22:55 ` Vineet Gupta
2026-09-23 8:47 ` Steven Rostedt
1 sibling, 1 reply; 4+ messages in thread
From: Vineet Gupta @ 2026-09-22 22:55 UTC (permalink / raw)
To: rostedt, mhiramat
Cc: mark.rutland, mathieu.desnoyers, andrii, peterz,
linux-trace-kernel, linux-kernel, bpf, kernel-team, Vineet Gupta
This is supplementary to previous patch and is effective only for
!PREEMPTION kernels.
The preceding patch cuts the number of sweeps over the thread list by
32x, but the loop is still O(N^2). Each pass walks from the same start
init_task under rcu_read_lock() with no reschedule point. On a kernel
that cannot preempt the walk, a large enough thread count lets one task
monopolize a CPU until the walk completes.
Add a cond_resched() between sweeps which is safe since it is outside
the RCU read-side critical section.
It is understood that this is effectively a no-op for CONFIG_PREEMPTION
builds, which is what default x86 and arm64 kernels are today.
A CONFIG_PREEMPT_DYNAMIC build with "preempt={none,voluntary}"
used to work but even that got inhibited since the commit
7dadeaa6e851 ("sched: Further restrict the preemption modes").
Measured on a 60-core machine with a PREEMPT_LAZY kernel and 400000
idle threads, this patch changes neither the runtime nor the yield
count, which stays at zero.
Where it does have effect is !CONFIG_PREEMPTION builds: architectures
that still offer PREEMPT_NONE or PREEMPT_VOLUNTARY, and the stable
kernels where x86 PREEMPT_NONE remains a build-time choice. Verified
on a 6.16 PREEMPT_NONE kernel, 240000 idle threads, three runs each,
with the loop instrumented to count passes and cond_resched() yields:
time yields soft lockup
unpatched 51.3-54.6 s - 3 of 3
cond_resched() 52.7-53.0 s 592-609 0 of 3
The runtime is unchanged and the soft lockups are gone. Every
need_resched() converts to a yield, giving an average of about 98 ms
between reschedules.
There is a second effect on those builds. When cond_resched() does not
reschedule it still calls rcu_all_qs() on !CONFIG_PREEMPT_RCU kernels,
reporting a quiescent state. So the two failures seen in the field are
addressed by two mechanisms: the soft lockup by yielding so the
watchdog can run, and the RCU stall by reporting a quiescent state
even on passes where no yield happens.
This is deliberately separable from the preceding patch. If the view
is that a no-op on the architectures anyone runs is not worth carrying,
dropping this one leaves the batch-size fix intact.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
kernel/trace/fgraph.c | 8 ++++++++
1 file changed, 8 insertions(+)
diff --git a/kernel/trace/fgraph.c b/kernel/trace/fgraph.c
index ed455b53513b..86d11217c584 100644
--- a/kernel/trace/fgraph.c
+++ b/kernel/trace/fgraph.c
@@ -1249,6 +1249,14 @@ static int start_graph_tracing(void)
do {
ret = alloc_retstack_tasklist(ret_stack_list);
+ /*
+ * Each pass rescans the thread list from the head, so the
+ * loop is O(threads^2) overall. The RCU read-side section
+ * ends with the pass, and both locks held here (ftrace_lock,
+ * and fprobe_mutex for fprobe users) are mutexes, so it is
+ * safe to give the CPU up in between.
+ */
+ cond_resched();
} while (ret == -EAGAIN);
if (!ret) {
--
2.53.0-Meta
^ permalink raw reply [flat|nested] 4+ messages in thread