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

[Vineet Gupta <vineet.gupta@linux.dev>]

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