bpf: Use the call graph to compute the depth of chains of calls
Three sums are left in the walk of the chains of calls: the bytes of stack,
the bytes of the stack in arena, and the number of frames since the last
global subprog.
The walk adds them up for every chain. Only the largest sum counts, and it
follows from the largest sums of the callers:
depth(callee) = max over the callers (depth(caller) + frame(caller))
Start with 0 at the main prog and at the async callbacks, and repeat until
nothing changes. The graph has no cycles, so this comes to an end. Then
compare the sums of every live subprog with the limits.
As before, the sums have the frames as the main verification pass leaves
them. What later passes add to a frame, like the inlined bpf_loop(), is not
counted.
Nothing is left in the walk. Remove it.
Time to load N global functions that call the next one in both branches of
an 'if':
N before after
16 4 ms 0.4 ms
20 70 ms 0.5 ms
24 1.3 sec 0.6 ms
28 24 sec 0.7 ms
60 - 1.3 ms
250 - 5.7 ms
250 global functions where each one calls all that follow, 31125 calls,
load in 20 ms.
The messages are the same. The subprog that goes over a limit is reported,
and not what it calls. When several subprogs go over it, the message is
about the first one in the prog and has the numbers of its longest chain,
and not of the chain that the walk got to first. A prog that breaks two
rules can get the other message and errno.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261104215523.1852636-7-alexei.starovoitov@gmail.com
1 file changed