[PATCH 0/2] tracing: fgraph: cut the cost of the shadow stack retry loop

[PATCH 0/2] tracing: fgraph: cut the cost of the shadow stack retry loop

[Vineet Gupta]

Turning on function-graph tracing, or attaching a kprobe_multi return
probe, hands every thread a shadow stack. alloc_retstack_tasklist()
does that 32 tasks at a time, and since for_each_process_thread() has
no cursor, every sweep restarts from init_task and re-walks the tasks
already served. Total work is quadratic O(N^2) on thread count.

On a 60-core Sapphire Rapids machine with 400000 idle threads the 0 -> 1
transition takes 227 s, inside a single bpf() syscall for the kprobe_multi
case. On Meta fleet this showed up as RCU stalls and softlockup panics.

Patch 1 raises the batch to 1024, dividing the sweeps by 32:
227 s -> 7.2 s at 400000 threads. It helps on every preemption model.

Patch 2 adds a cond_resched() between sweeps. It is supplementary and
separable: a no-op on current x86 and arm64, but on !CONFIG_PREEMPTION
builds it takes soft lockups from 3-of-3 runs to 0-of-3. Dropping it
leaves patch 1 intact.

Neither changes the O(N^2) shape; a cursor-based walk would, but
task_struct lifetime makes that considerably more involved.

Vineet Gupta (2):
  tracing: fgraph: Raise FTRACE_RETSTACK_ALLOC_SIZE to 1024
  tracing: fgraph: Add a cond_resched() to the shadow stack retry loop

 include/linux/ftrace.h | 7 ++++++-
 kernel/trace/fgraph.c  | 8 ++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)

-- 
2.53.0-Meta

[PATCH 1/2] tracing: fgraph: Raise FTRACE_RETSTACK_ALLOC_SIZE to 1024

[Vineet Gupta]

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

[PATCH 2/2] tracing: fgraph: Add a cond_resched() to the shadow stack retry loop

[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

Re: [PATCH 2/2] tracing: fgraph: Add a cond_resched() to the shadow stack retry loop

[Steven Rostedt]

On Tue, 22 Sep 2026 15:55:26 -0700
Vineet Gupta <vineet.gupta@linux.dev> wrote:

> This is supplementary to previous patch and is effective only for
> !PREEMPTION kernels.

FYI, a patch in a series should never mention "the previous patch" as
if it gets committed, order in git history is not easily seen. Thus, a
change log should mention the added functionality itself and not a
patch sent to the mailing list.

But that said, this patch is likely not going to be added because
!PREEMPTION is being deprecated specifically to get rid of
cond_rescheds. Hence, I'm not adding any new ones.

-- Steve