* [PATCH bpf-next 1/9] bpf: Build the call graph of a prog after the main verification pass
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 2/9] bpf: Use the call graph to find what runs in a callback Alexei Starovoitov
` (8 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
check_max_stack_depth() walks the chains of calls of a prog one by one:
main main -> A -> C -> D
/ \ main -> A -> C -> E
A B main -> B -> C -> D
\ / main -> B -> C -> E
C
/ \
D E
The number of chains grows exponentially with the number of subprogs. When
each of N global functions calls the next one in both branches of an 'if',
the prog executes N calls, and the walk looks at 2^N chains. 24 functions
take 1.3 sec to load, 30 functions take 105 sec.
The walk does more than its name says. It looks for recursion, it finds
the subprogs that get to a tail call, that run in a callback and that can
use a private stack, and it counts frames. None of it depends on a chain.
It depends on who calls whom.
Build that graph: a bitmap of callees for every subprog, and the transitive
closure, which says what a subprog gets to. The edges are what the walk
follows, in dead code too:
- a call of a subprog,
- the address of a subprog, unless it is an async callback,
- what the main verification pass recorded for callx and for helpers that
call callbacks.
'live' are the subprogs that the walk visits: the main prog, the async
callbacks and what they get to.
Move the first two checks. A live subprog that gets to itself is
a recursion. A live subprog cannot call the exception callback. The walk
still does the rest.
No verdict changes. The message names the last call of the cycle. When
several subprogs are on the cycle, it can be another call of that cycle
than before. A prog that breaks two rules can get the other message and
errno. sort_subprogs_topo() and its rerun after the main pass stay: they
also reject some cycles through the address of an async callback.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/verifier.c | 218 ++++++++++++++++++++++++++++++++++--------
1 file changed, 180 insertions(+), 38 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 81ed32a4b048..d94c273aa3b4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5777,6 +5777,167 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)
return round_up(max_t(u32, stack_depth, 1), 32);
}
+/*
+ * A set of subprogs is a bitmap. The call graph has a set for every subprog:
+ * calls + s * BITS_TO_LONGS(cnt) are the subprogs that s calls. Make it
+ * the subprogs that s gets to, through any number of calls.
+ */
+static void close_call_graph(unsigned long *calls, int cnt)
+{
+ int words = BITS_TO_LONGS(cnt);
+ int j, s;
+
+ for (j = 0; j < cnt; j++)
+ for (s = 0; s < cnt; s++)
+ if (test_bit(j, calls + s * words))
+ bitmap_or(calls + s * words, calls + s * words,
+ calls + j * words, cnt);
+}
+
+/*
+ * Who calls whom. It's known after the main verification pass, which finds out
+ * what callx and the helpers that take callbacks call.
+ *
+ * What follows for a subprog from its callers, or from what it calls, is computed
+ * over this graph and not by a walk of one chain of calls after another: the
+ * number of chains grows exponentially.
+ */
+struct bpf_call_graph {
+ int cnt; /* subprogs */
+ int words; /* longs in a set of subprogs */
+ unsigned long *calls; /* calls + s * words: the subprogs that s calls */
+ unsigned long *reach; /* reach + s * words: the subprogs that s gets to */
+ unsigned long *live; /* what the kernel calls and what that gets to */
+};
+
+static unsigned long *subprog_calls(struct bpf_call_graph *cg, int s)
+{
+ return cg->calls + s * cg->words;
+}
+
+static unsigned long *subprog_reach(struct bpf_call_graph *cg, int s)
+{
+ return cg->reach + s * cg->words;
+}
+
+/* add the subprog and what it gets to */
+static void add_reach(struct bpf_call_graph *cg, unsigned long *set, int s)
+{
+ __set_bit(s, set);
+ bitmap_or(set, set, subprog_reach(cg, s), cg->cnt);
+}
+
+static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_insn *insn = env->prog->insnsi;
+ int cnt = env->subprog_cnt, words = BITS_TO_LONGS(cnt);
+ int i, j, s;
+
+ cg->cnt = cnt;
+ cg->words = words;
+ cg->calls = kvcalloc((2 * cnt + 1) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
+ if (!cg->calls)
+ return -ENOMEM;
+ cg->reach = cg->calls + cnt * words;
+ cg->live = cg->reach + cnt * words;
+
+ for (s = 0; s < cnt; s++) {
+ for (i = si[s].start; i < si[s + 1].start; i++) {
+ /* the subprog that takes the address of a subprog counts as its caller */
+ if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
+ continue;
+ j = bpf_find_subprog(env, i + insn[i].imm + 1);
+ if (verifier_bug_if(j < 0, env, "callee not found at insn %d",
+ i + insn[i].imm + 1))
+ return -EFAULT;
+ /*
+ * async callbacks don't increase bpf prog stack size
+ * unless called directly
+ */
+ if (si[j].is_async_cb && !bpf_pseudo_call(insn + i))
+ continue;
+ __set_bit(j, subprog_calls(cg, s));
+ }
+ /* the callees of callx and the callbacks of helpers, see record_callx_edge() */
+ for (j = next_callx_callee(env, s, 0); j >= 0; j = next_callx_callee(env, s, j + 1))
+ __set_bit(j, subprog_calls(cg, s));
+ }
+ memcpy(cg->reach, cg->calls, cnt * words * sizeof(long));
+ close_call_graph(cg->reach, cnt);
+
+ for (s = 0; s < cnt; s++)
+ if (!s || si[s].is_async_cb)
+ add_reach(cg, cg->live, s);
+ return 0;
+}
+
+/* the insn of subprog 'caller' that is the edge to subprog 'callee' */
+static int find_call_insn(struct bpf_verifier_env *env, int caller, int callee)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_insn *insn = env->prog->insnsi;
+ int i, end = si[caller + 1].start;
+
+ for (i = si[caller].start; i < end; i++) {
+ if (!bpf_pseudo_call(insn + i) &&
+ (!bpf_pseudo_func(insn + i) || si[callee].is_async_cb))
+ continue;
+ if (i + insn[i].imm + 1 == si[callee].start)
+ return i;
+ }
+ /* It's not recorded which callx or helper calls what. Take the first one. */
+ for (i = si[caller].start; i < end - 1; i++)
+ if (bpf_is_callx(insn + i) || bpf_calls_callback(env, i))
+ break;
+ return i;
+}
+
+/* The exception callback is an async callback, so only a call is an edge to it */
+static int check_exception_cb(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ int cb = env->exception_callback_subprog, s;
+
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ if (!cb || !test_bit(cb, subprog_calls(cg, s)))
+ continue;
+ verbose(env, "insn %d cannot call exception cb directly\n",
+ find_call_insn(env, s, cb));
+ return -EINVAL;
+ }
+ return 0;
+}
+
+/*
+ * The DFS of sort_subprogs_topo() follows the address of a function like a call, and
+ * tolerates a cycle only when such address closes it, since it doesn't know what it is
+ * taken for. Such cycle counts as a recursion, unless the function is an async callback:
+ * its address is not an edge of the graph. The main verification pass limits the
+ * depth of the recursion, but it doesn't follow calls of global functions.
+ */
+static int check_recursion(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ int j, s;
+
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ if (!test_bit(s, subprog_reach(cg, s)))
+ continue;
+ /* the last call of the cycle */
+ for_each_set_bit(j, subprog_reach(cg, s), cg->cnt)
+ if (test_bit(s, subprog_calls(cg, j)))
+ break;
+ verbose(env, "recursive call from %s() to %s()\n",
+ bpf_subprog_name(env, j), bpf_subprog_name(env, s));
+ bpf_diag_program_structure(
+ env, find_call_insn(env, j, s), "recursive subprogram call",
+ "Rewrite the recursion as an explicit bounded loop, or split the logic so subprogram calls do not form a cycle.",
+ "This call or callback would make the subprogram call graph recursive. "
+ "The verifier requires a finite, acyclic call graph so it can bound stack depth and analysis.");
+ return -EINVAL;
+ }
+ return 0;
+}
+
/* temporary state used for call frame depth calculation */
struct bpf_subprog_call_depth_info {
int ret_insn; /* caller instruction where we return to. */
@@ -5950,10 +6111,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
/* async callbacks don't increase bpf prog stack size unless called directly */
if (!bpf_pseudo_call(insn + i))
continue;
- if (subprog[sidx].is_exception_cb) {
- verbose(env, "insn %d cannot call exception cb directly", i);
- return -EINVAL;
- }
}
/* remember insn to return to */
dinfo[idx].ret_insn = i + 1;
@@ -5961,27 +6118,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
continue;
}
- /*
- * sort_subprogs_topo() tolerates cycles in the call graph that
- * go through the address of a function being taken, since it
- * doesn't know what it is taken for. Such cycle is a recursion
- * unless it's an async callback, which are skipped above.
- * The main verification pass limits the depth of the recursion,
- * but it doesn't follow calls of global functions.
- */
- for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller) {
- if (tmp != sidx)
- continue;
- verbose(env, "recursive call from %s() to %s()\n",
- bpf_subprog_name(env, idx), bpf_subprog_name(env, sidx));
- bpf_diag_program_structure(
- env, i, "recursive subprogram call",
- "Rewrite the recursion as an explicit bounded loop, or split the logic so subprogram calls do not form a cycle.",
- "This call or callback would make the subprogram call graph recursive. "
- "The verifier requires a finite, acyclic call graph so it can bound stack depth and analysis.");
- return -EINVAL;
- }
-
/* store caller info for after we return from callee */
dinfo[idx].frame = frame;
@@ -6064,22 +6200,18 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
enum priv_stack_mode priv_stack_mode = PRIV_STACK_UNKNOWN;
- struct bpf_subprog_call_depth_info *dinfo;
+ struct bpf_subprog_call_depth_info *dinfo = NULL;
struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_call_graph cg = {};
bool priv_stack_supported;
int ret;
- dinfo = kvzalloc_objs(*dinfo, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
- if (!dinfo)
- return -ENOMEM;
-
for (int i = 0; i < env->subprog_cnt; i++) {
if (si[i].has_tail_call) {
/* the stack in arena wouldn't be returned */
if (env->uses_arena_sp) {
verbose(env, "tail_calls are not allowed in programs that use R%d\n",
BPF_REG_ARENA_SP);
- kvfree(dinfo);
return -EINVAL;
}
priv_stack_mode = NO_PRIV_STACK;
@@ -6093,6 +6225,18 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
if (priv_stack_mode == PRIV_STACK_UNKNOWN)
priv_stack_mode = bpf_enable_priv_stack(env->prog);
+ ret = build_call_graph(env, &cg);
+ ret = ret ?: check_exception_cb(env, &cg);
+ ret = ret ?: check_recursion(env, &cg);
+ if (ret)
+ goto out;
+
+ dinfo = kvzalloc_objs(*dinfo, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
+ if (!dinfo) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
/* All async_cb subprogs use normal kernel stack. If a particular
* subprog appears in both main prog and async_cb subtree, that
* subprog will use normal kernel stack to avoid potential nesting.
@@ -6106,10 +6250,8 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
priv_stack_supported = !i && priv_stack_mode == PRIV_STACK_ADAPTIVE;
ret = check_max_stack_depth_subprog(env, i, dinfo,
priv_stack_supported);
- if (ret < 0) {
- kvfree(dinfo);
- return ret;
- }
+ if (ret < 0)
+ goto out;
}
}
@@ -6119,10 +6261,10 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
break;
}
}
-
+out:
kvfree(dinfo);
-
- return 0;
+ kvfree(cg.calls);
+ return ret;
}
static int __check_buffer_access(struct bpf_verifier_env *env,
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 2/9] bpf: Use the call graph to find what runs in a callback
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 1/9] bpf: Build the call graph of a prog after the main verification pass Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 3/9] bpf: Use the call graph to find what gets to a tail call Alexei Starovoitov
` (7 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
A callback cannot use BPF_LD_[ABS|IND] and cannot call bpf_throw(). The
same holds for every subprog that the callback gets to. When the walk of
the chains of calls meets such an insn, it looks for a callback among the
callers in the current chain.
In the call graph it is one set: the live callbacks and what they get to.
Look for these insns in the subprogs of the set. This is done before the
walk, so a prog that breaks two rules can get the other message and errno.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/verifier.c | 58 +++++++++++++++++++++++--------------------
1 file changed, 31 insertions(+), 27 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d94c273aa3b4..ef2af44afb0c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5808,6 +5808,7 @@ struct bpf_call_graph {
unsigned long *calls; /* calls + s * words: the subprogs that s calls */
unsigned long *reach; /* reach + s * words: the subprogs that s gets to */
unsigned long *live; /* what the kernel calls and what that gets to */
+ unsigned long *in_cb; /* callbacks and what they get to */
};
static unsigned long *subprog_calls(struct bpf_call_graph *cg, int s)
@@ -5836,11 +5837,12 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
cg->cnt = cnt;
cg->words = words;
- cg->calls = kvcalloc((2 * cnt + 1) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
+ cg->calls = kvcalloc((2 * cnt + 2) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
if (!cg->calls)
return -ENOMEM;
cg->reach = cg->calls + cnt * words;
cg->live = cg->reach + cnt * words;
+ cg->in_cb = cg->live + words;
for (s = 0; s < cnt; s++) {
for (i = si[s].start; i < si[s + 1].start; i++) {
@@ -5869,6 +5871,10 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
for (s = 0; s < cnt; s++)
if (!s || si[s].is_async_cb)
add_reach(cg, cg->live, s);
+ for_each_set_bit(s, cg->live, cnt) {
+ if (si[s].is_cb)
+ add_reach(cg, cg->in_cb, s);
+ }
return 0;
}
@@ -5938,6 +5944,29 @@ static int check_recursion(struct bpf_verifier_env *env, struct bpf_call_graph *
return 0;
}
+static int check_callbacks(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_insn *insn = env->prog->insnsi;
+ int i, s;
+
+ for_each_set_bit(s, cg->in_cb, cg->cnt) {
+ if (si[s].has_ld_abs) {
+ verbose(env, "cannot use BPF_LD_[ABS|IND] within callback\n");
+ return -EINVAL;
+ }
+ for (i = si[s].start; i < si[s + 1].start; i++) {
+ if (!bpf_is_throw_kfunc(insn + i))
+ continue;
+ verbose(env,
+ "bpf_throw kfunc (insn %d) cannot be called from callback subprog %d\n",
+ i, s);
+ return -EINVAL;
+ }
+ }
+ return 0;
+}
+
/* temporary state used for call frame depth calculation */
struct bpf_subprog_call_depth_info {
int ret_insn; /* caller instruction where we return to. */
@@ -5973,14 +6002,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
subprog[idx].priv_stack_mode = NO_PRIV_STACK;
process_func:
dinfo[idx].callx_insn = -1;
- if (subprog[idx].has_ld_abs) {
- for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller) {
- if (subprog[tmp].is_cb) {
- verbose(env, "cannot use BPF_LD_[ABS|IND] within callback\n");
- return -EINVAL;
- }
- }
- }
/* protect against potential stack overflow that might happen when
* bpf2bpf calls get combined with tailcalls. Limit the caller's stack
@@ -6067,24 +6088,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
for (; i < subprog_end; i++) {
int next_insn, sidx;
- if (bpf_pseudo_kfunc_call(insn + i) && !insn[i].off &&
- bpf_is_throw_kfunc(insn + i)) {
- bool err = false;
-
- for (tmp = idx; tmp >= 0 && !err; tmp = dinfo[tmp].caller) {
- if (subprog[tmp].is_cb) {
- err = true;
- break;
- }
- }
- if (!err)
- continue;
- verbose(env,
- "bpf_throw kfunc (insn %d) cannot be called from callback subprog %d\n",
- i, idx);
- return -EINVAL;
- }
-
if (bpf_is_callx(insn + i) || bpf_calls_callback(env, i)) {
/*
* Walk the callees and the callbacks recorded by
@@ -6228,6 +6231,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
ret = build_call_graph(env, &cg);
ret = ret ?: check_exception_cb(env, &cg);
ret = ret ?: check_recursion(env, &cg);
+ ret = ret ?: check_callbacks(env, &cg);
if (ret)
goto out;
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 3/9] bpf: Use the call graph to find what gets to a tail call
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 1/9] bpf: Build the call graph of a prog after the main verification pass Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 2/9] bpf: Use the call graph to find what runs in a callback Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 4/9] bpf: Use the call graph to find callbacks that take a stack in arena Alexei Starovoitov
` (6 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
JITs pass the tail call counter from the main prog down to the subprog that
has the tail call. Every subprog on the way has to be marked as
tail_call_reachable. It cannot be a callback, cannot have stack arguments
and cannot be called via callx.
The walk of the chains of calls marks and checks all callers in the current
chain when it leaves a subprog that has a tail call or is already marked.
In the call graph these are the live subprogs that have a tail call or get
to one:
main -> A -> C -> tail call main, A, B and C are marked,
main -> B -> C D is not
main -> D
Let callx mark its target in the main verification pass. The walk took
every callee that was recorded for a subprog with a callx insn for a target
of callx, the callbacks of helpers included. That made no difference,
because a callback cannot get to a tail call anyway.
The walk starts at an entry point with "no tail call seen". So it misses
a tail call in an async callback that calls nothing. Such a tail call is
dead code, because an async callback has no ctx for bpf_tail_call(). It is
rejected now, like in all other callbacks.
A prog that breaks two rules can get the other message and errno.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf_verifier.h | 1 +
kernel/bpf/verifier.c | 88 ++++++++++++++++++------------------
2 files changed, 45 insertions(+), 44 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index b56f9969002c..60d6d93c57db 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -987,6 +987,7 @@ struct bpf_subprog_info {
bool has_tail_call: 1;
bool might_throw: 1;
bool can_unwind: 1; /* has unwind_exit */
+ bool via_callx: 1; /* callx calls it */
bool tail_call_reachable: 1;
bool has_ld_abs: 1;
bool is_cb: 1;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ef2af44afb0c..76f4e1f238ba 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5809,6 +5809,7 @@ struct bpf_call_graph {
unsigned long *reach; /* reach + s * words: the subprogs that s gets to */
unsigned long *live; /* what the kernel calls and what that gets to */
unsigned long *in_cb; /* callbacks and what they get to */
+ unsigned long *tail_calls; /* subprogs that have a tail call */
};
static unsigned long *subprog_calls(struct bpf_call_graph *cg, int s)
@@ -5837,12 +5838,13 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
cg->cnt = cnt;
cg->words = words;
- cg->calls = kvcalloc((2 * cnt + 2) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
+ cg->calls = kvcalloc((2 * cnt + 3) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
if (!cg->calls)
return -ENOMEM;
cg->reach = cg->calls + cnt * words;
cg->live = cg->reach + cnt * words;
cg->in_cb = cg->live + words;
+ cg->tail_calls = cg->in_cb + words;
for (s = 0; s < cnt; s++) {
for (i = si[s].start; i < si[s + 1].start; i++) {
@@ -5874,6 +5876,8 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
for_each_set_bit(s, cg->live, cnt) {
if (si[s].is_cb)
add_reach(cg, cg->in_cb, s);
+ if (si[s].has_tail_call)
+ __set_bit(s, cg->tail_calls);
}
return 0;
}
@@ -5967,6 +5971,43 @@ static int check_callbacks(struct bpf_verifier_env *env, struct bpf_call_graph *
return 0;
}
+/*
+ * Mark the subprogs that get to a tail call as tail call reachable subprogs;
+ * this info will be utilized by JIT so that we will be preserving the
+ * tail call counter throughout bpf2bpf calls combined with tailcalls
+ */
+static int check_tail_calls(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ int s;
+
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ if (!si[s].has_tail_call &&
+ !bitmap_intersects(subprog_reach(cg, s), cg->tail_calls, cg->cnt))
+ continue;
+ if (si[s].is_cb) {
+ verbose(env, "cannot tail call within callback\n");
+ return -EINVAL;
+ }
+ if (si[s].stack_arg_cnt) {
+ verbose(env, "tail_calls are not allowed in programs with stack args\n");
+ return -EINVAL;
+ }
+ /*
+ * JITs pass tail call counter in a register that is
+ * not available when the callee is called via callx.
+ */
+ if (si[s].via_callx) {
+ verbose(env, "tail_calls are not allowed in functions called via callx\n");
+ return -EINVAL;
+ }
+ si[s].tail_call_reachable = true;
+ }
+ if (si[0].tail_call_reachable)
+ env->prog->aux->tail_call_reachable = true;
+ return 0;
+}
+
/* temporary state used for call frame depth calculation */
struct bpf_subprog_call_depth_info {
int ret_insn; /* caller instruction where we return to. */
@@ -5974,7 +6015,6 @@ struct bpf_subprog_call_depth_info {
int frame; /* # of consecutive static call stack frames on top of stack */
int callx_insn; /* callx instruction whose callees are being walked */
int callx_next; /* next callee of callx_insn to walk */
- bool via_callx; /* the subprogram is entered via callx */
};
/* starting from main bpf function walk all instructions of the function
@@ -5988,14 +6028,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
struct bpf_subprog_info *subprog = env->subprog_info;
struct bpf_insn *insn = env->prog->insnsi;
int depth = 0, frame = 0, i, subprog_end, subprog_depth;
- bool tail_call_reachable = false;
int arena_depth = 0;
int total;
int tmp;
/* no caller idx */
dinfo[idx].caller = -1;
- dinfo[idx].via_callx = false;
i = subprog[idx].start;
if (!priv_stack_supported)
@@ -6126,7 +6164,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
/* push caller idx into callee's dinfo */
dinfo[sidx].caller = idx;
- dinfo[sidx].via_callx = bpf_is_callx(insn + i);
i = next_insn;
@@ -6134,9 +6171,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
if (!priv_stack_supported)
subprog[idx].priv_stack_mode = NO_PRIV_STACK;
- /* sync tail_call_reachable with callee state on entry */
- tail_call_reachable = subprog[idx].has_tail_call;
-
frame = bpf_subprog_is_global(env, idx) ? 0 : frame + 1;
if (frame >= MAX_CALL_FRAMES) {
verbose(env, "the call stack of %d frames is too deep !\n",
@@ -6145,39 +6179,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
}
goto process_func;
}
- /* if tail call got detected across bpf2bpf calls then mark each of the
- * currently present subprog frames as tail call reachable subprogs;
- * this info will be utilized by JIT so that we will be preserving the
- * tail call counter throughout bpf2bpf calls combined with tailcalls
- */
- if (tail_call_reachable) {
- for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller) {
- if (subprog[tmp].is_cb) {
- verbose(env, "cannot tail call within callback\n");
- return -EINVAL;
- }
- if (subprog[tmp].stack_arg_cnt) {
- verbose(env, "tail_calls are not allowed in programs with stack args\n");
- return -EINVAL;
- }
- /*
- * JITs pass tail call counter in a register that is
- * not available when the callee is called via callx.
- */
- if (dinfo[tmp].via_callx) {
- verbose(env, "tail_calls are not allowed in functions called via callx\n");
- return -EINVAL;
- }
- subprog[tmp].tail_call_reachable = true;
- }
- } else if (!idx && subprog[0].has_tail_call && subprog[0].stack_arg_cnt) {
- verbose(env, "tail_calls are not allowed in programs with stack args\n");
- return -EINVAL;
- }
-
- if (subprog[0].tail_call_reachable)
- env->prog->aux->tail_call_reachable = true;
-
/* end of for() loop means the last insn of the 'subprog'
* was reached. Doesn't matter whether it was JA or EXIT
*/
@@ -6194,9 +6195,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
frame = dinfo[idx].frame;
i = dinfo[idx].ret_insn;
- /* reset tail_call_reachable to the parent's actual state */
- tail_call_reachable = subprog[idx].tail_call_reachable;
-
goto continue_func;
}
@@ -6232,6 +6230,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
ret = ret ?: check_exception_cb(env, &cg);
ret = ret ?: check_recursion(env, &cg);
ret = ret ?: check_callbacks(env, &cg);
+ ret = ret ?: check_tail_calls(env, &cg);
if (ret)
goto out;
@@ -11946,6 +11945,7 @@ static int check_func_callx(struct bpf_verifier_env *env, struct bpf_insn *insn,
err = record_callx_edge(env, caller->subprogno, subprog);
if (err)
return err;
+ env->subprog_info[subprog].via_callx = true;
return check_static_func_call(env, subprog, insn_idx);
}
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 4/9] bpf: Use the call graph to find callbacks that take a stack in arena
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (2 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 3/9] bpf: Use the call graph to find what gets to a tail call Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 5/9] bpf: Use the call graph to choose subprogs with a private stack Alexei Starovoitov
` (5 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
The kernel calls a callback and knows nothing about r12. So a callback
takes a stack in arena at its entry, like the main prog does, when it uses
r12 or calls what uses it. For every subprog that uses r12 the walk of the
chains of calls marks the nearest callback among the callers.
In the call graph the need goes from the callee to the caller and stops at
a callback:
- A subprog that is not a callback counts on r12 of its caller when it
uses r12, or when it calls a subprog that counts on r12.
- A callback that uses r12, or calls a subprog that counts on r12, takes
a stack.
main -> bpf_loop() -> outer_cb -> bpf_loop() -> inner_cb -> A -> B
takes a uses
stack r12
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/verifier.c | 43 +++++++++++++++++++++++++++++++++----------
1 file changed, 33 insertions(+), 10 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 76f4e1f238ba..3e80e60f9883 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5810,6 +5810,7 @@ struct bpf_call_graph {
unsigned long *live; /* what the kernel calls and what that gets to */
unsigned long *in_cb; /* callbacks and what they get to */
unsigned long *tail_calls; /* subprogs that have a tail call */
+ unsigned long *arena_sp; /* subprogs that count on r12 of the caller */
};
static unsigned long *subprog_calls(struct bpf_call_graph *cg, int s)
@@ -5838,13 +5839,14 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
cg->cnt = cnt;
cg->words = words;
- cg->calls = kvcalloc((2 * cnt + 3) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
+ cg->calls = kvcalloc((2 * cnt + 4) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
if (!cg->calls)
return -ENOMEM;
cg->reach = cg->calls + cnt * words;
cg->live = cg->reach + cnt * words;
cg->in_cb = cg->live + words;
cg->tail_calls = cg->in_cb + words;
+ cg->arena_sp = cg->tail_calls + words;
for (s = 0; s < cnt; s++) {
for (i = si[s].start; i < si[s + 1].start; i++) {
@@ -6008,6 +6010,35 @@ static int check_tail_calls(struct bpf_verifier_env *env, struct bpf_call_graph
return 0;
}
+/*
+ * The kernel calls a callback. It knows nothing about r12. So a callback takes a
+ * stack in arena, like the main prog does, when it uses r12 or calls what
+ * does. The callbacks below it are not its business: they take their own.
+ */
+static void mark_arena_stack_entries(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ bool changed;
+ int s;
+
+ do {
+ changed = false;
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ if (test_bit(s, cg->arena_sp) || si[s].arena_stack_entry)
+ continue;
+ if (!si[s].uses_arena_sp &&
+ !bitmap_intersects(subprog_calls(cg, s), cg->arena_sp, cg->cnt))
+ continue;
+ if (si[s].is_cb) {
+ si[s].arena_stack_entry = true;
+ continue;
+ }
+ __set_bit(s, cg->arena_sp);
+ changed = true;
+ }
+ } while (changed);
+}
+
/* temporary state used for call frame depth calculation */
struct bpf_subprog_call_depth_info {
int ret_insn; /* caller instruction where we return to. */
@@ -6060,15 +6091,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
* tailcall will unwind the current stack frame but it will not get rid
* of caller's stack as shown on the example above.
*/
- /* The kernel calls a callback. It knows nothing about r12. */
- if (subprog[idx].uses_arena_sp) {
- for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller) {
- if (!subprog[tmp].is_cb)
- continue;
- subprog[tmp].arena_stack_entry = true;
- break;
- }
- }
arena_depth += subprog[idx].arena_stack_depth;
if (arena_depth > env->max_arena_stack_depth)
env->max_arena_stack_depth = arena_depth;
@@ -6233,6 +6255,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
ret = ret ?: check_tail_calls(env, &cg);
if (ret)
goto out;
+ mark_arena_stack_entries(env, &cg);
dinfo = kvzalloc_objs(*dinfo, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
if (!dinfo) {
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 5/9] bpf: Use the call graph to choose subprogs with a private stack
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (3 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 4/9] bpf: Use the call graph to find callbacks that take a stack in arena Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 6/9] bpf: Use the call graph to compute the depth of chains of calls Alexei Starovoitov
` (4 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
Whether a subprog has its frame in the private stack depends on the prog,
on the size of the frame, and on its callers: no async callback may get to
the subprog. An async callback can run on top of the main prog on the same
cpu, and both would use the same frame.
The walk of the chains of calls gets the last condition from its order. It
starts at the async callbacks and marks what it visits as NO_PRIV_STACK.
The main prog comes last and takes what is not marked.
In the call graph "the async callbacks and what they get to" is a set. The
mode of every subprog is known before the walk starts, and the walk only
adds up the frames.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/verifier.c | 74 +++++++++++++++++++------------------------
1 file changed, 32 insertions(+), 42 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3e80e60f9883..5362687eba8b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5809,6 +5809,7 @@ struct bpf_call_graph {
unsigned long *reach; /* reach + s * words: the subprogs that s gets to */
unsigned long *live; /* what the kernel calls and what that gets to */
unsigned long *in_cb; /* callbacks and what they get to */
+ unsigned long *in_async_cb; /* async callbacks and what they get to */
unsigned long *tail_calls; /* subprogs that have a tail call */
unsigned long *arena_sp; /* subprogs that count on r12 of the caller */
};
@@ -5839,13 +5840,14 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
cg->cnt = cnt;
cg->words = words;
- cg->calls = kvcalloc((2 * cnt + 4) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
+ cg->calls = kvcalloc((2 * cnt + 5) * words, sizeof(long), GFP_KERNEL_ACCOUNT);
if (!cg->calls)
return -ENOMEM;
cg->reach = cg->calls + cnt * words;
cg->live = cg->reach + cnt * words;
cg->in_cb = cg->live + words;
- cg->tail_calls = cg->in_cb + words;
+ cg->in_async_cb = cg->in_cb + words;
+ cg->tail_calls = cg->in_async_cb + words;
cg->arena_sp = cg->tail_calls + words;
for (s = 0; s < cnt; s++) {
@@ -5878,6 +5880,8 @@ static int build_call_graph(struct bpf_verifier_env *env, struct bpf_call_graph
for_each_set_bit(s, cg->live, cnt) {
if (si[s].is_cb)
add_reach(cg, cg->in_cb, s);
+ if (si[s].is_async_cb)
+ add_reach(cg, cg->in_async_cb, s);
if (si[s].has_tail_call)
__set_bit(s, cg->tail_calls);
}
@@ -6053,8 +6057,7 @@ struct bpf_subprog_call_depth_info {
* Ignore jump and exit insns.
*/
static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
- struct bpf_subprog_call_depth_info *dinfo,
- bool priv_stack_supported)
+ struct bpf_subprog_call_depth_info *dinfo)
{
struct bpf_subprog_info *subprog = env->subprog_info;
struct bpf_insn *insn = env->prog->insnsi;
@@ -6067,8 +6070,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
dinfo[idx].caller = -1;
i = subprog[idx].start;
- if (!priv_stack_supported)
- subprog[idx].priv_stack_mode = NO_PRIV_STACK;
process_func:
dinfo[idx].callx_insn = -1;
@@ -6108,19 +6109,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
}
subprog_depth = round_up_stack_depth(env, subprog[idx].stack_depth);
- if (IS_ENABLED(CONFIG_X86_64) && subprog[idx].stack_arg_cnt) {
- /* x86-64 uses R9 for both private stack frame pointer and arg6. */
- subprog[idx].priv_stack_mode = NO_PRIV_STACK;
- } else if (priv_stack_supported) {
- /* Request private stack support only if the subprog stack
- * depth is no less than BPF_PRIV_STACK_MIN_SIZE. This is to
- * avoid jit penalty if the stack usage is small.
- */
- if (subprog[idx].priv_stack_mode == PRIV_STACK_UNKNOWN &&
- subprog_depth >= BPF_PRIV_STACK_MIN_SIZE)
- subprog[idx].priv_stack_mode = PRIV_STACK_ADAPTIVE;
- }
-
if (subprog[idx].priv_stack_mode == PRIV_STACK_ADAPTIVE) {
if (subprog_depth > env->max_stack_depth)
env->max_stack_depth = subprog_depth;
@@ -6190,9 +6178,6 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
i = next_insn;
idx = sidx;
- if (!priv_stack_supported)
- subprog[idx].priv_stack_mode = NO_PRIV_STACK;
-
frame = bpf_subprog_is_global(env, idx) ? 0 : frame + 1;
if (frame >= MAX_CALL_FRAMES) {
verbose(env, "the call stack of %d frames is too deep !\n",
@@ -6226,8 +6211,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
struct bpf_subprog_call_depth_info *dinfo = NULL;
struct bpf_subprog_info *si = env->subprog_info;
struct bpf_call_graph cg = {};
- bool priv_stack_supported;
- int ret;
+ int s, ret;
for (int i = 0; i < env->subprog_cnt; i++) {
if (si[i].has_tail_call) {
@@ -6257,36 +6241,42 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
goto out;
mark_arena_stack_entries(env, &cg);
+ for_each_set_bit(s, cg.live, cg.cnt) {
+ /*
+ * All async_cb subprogs use normal kernel stack. If a particular
+ * subprog appears in both main prog and async_cb subtree, that
+ * subprog will use normal kernel stack to avoid potential nesting.
+ * x86-64 uses R9 for both private stack frame pointer and arg6.
+ */
+ if (priv_stack_mode != PRIV_STACK_ADAPTIVE || test_bit(s, cg.in_async_cb) ||
+ (IS_ENABLED(CONFIG_X86_64) && si[s].stack_arg_cnt)) {
+ si[s].priv_stack_mode = NO_PRIV_STACK;
+ continue;
+ }
+ /*
+ * Request private stack support only if the subprog stack
+ * depth is no less than BPF_PRIV_STACK_MIN_SIZE. This is to
+ * avoid jit penalty if the stack usage is small.
+ */
+ if (round_up_stack_depth(env, si[s].stack_depth) >= BPF_PRIV_STACK_MIN_SIZE) {
+ si[s].priv_stack_mode = PRIV_STACK_ADAPTIVE;
+ env->prog->aux->jits_use_priv_stack = true;
+ }
+ }
+
dinfo = kvzalloc_objs(*dinfo, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
if (!dinfo) {
ret = -ENOMEM;
goto out;
}
- /* All async_cb subprogs use normal kernel stack. If a particular
- * subprog appears in both main prog and async_cb subtree, that
- * subprog will use normal kernel stack to avoid potential nesting.
- * The reverse subprog traversal ensures when main prog subtree is
- * checked, the subprogs appearing in async_cb subtrees are already
- * marked as using normal kernel stack, so stack size checking can
- * be done properly.
- */
for (int i = env->subprog_cnt - 1; i >= 0; i--) {
if (!i || si[i].is_async_cb) {
- priv_stack_supported = !i && priv_stack_mode == PRIV_STACK_ADAPTIVE;
- ret = check_max_stack_depth_subprog(env, i, dinfo,
- priv_stack_supported);
+ ret = check_max_stack_depth_subprog(env, i, dinfo);
if (ret < 0)
goto out;
}
}
-
- for (int i = 0; i < env->subprog_cnt; i++) {
- if (si[i].priv_stack_mode == PRIV_STACK_ADAPTIVE) {
- env->prog->aux->jits_use_priv_stack = true;
- break;
- }
- }
out:
kvfree(dinfo);
kvfree(cg.calls);
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 6/9] bpf: Use the call graph to compute the depth of chains of calls
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (4 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 5/9] bpf: Use the call graph to choose subprogs with a private stack Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 7/9] selftests/bpf: Test what follows from the " Alexei Starovoitov
` (3 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
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>
---
kernel/bpf/verifier.c | 282 +++++++++++++++++++-----------------------
1 file changed, 129 insertions(+), 153 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5362687eba8b..b8f4549da6db 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6045,170 +6045,159 @@ static void mark_arena_stack_entries(struct bpf_verifier_env *env, struct bpf_ca
/* temporary state used for call frame depth calculation */
struct bpf_subprog_call_depth_info {
- int ret_insn; /* caller instruction where we return to. */
- int caller; /* caller subprogram idx */
- int frame; /* # of consecutive static call stack frames on top of stack */
- int callx_insn; /* callx instruction whose callees are being walked */
- int callx_next; /* next callee of callx_insn to walk */
+ int caller; /* the caller that has the most on the stack. -1: the kernel */
+ int depth; /* the most that the frames of the callers take. -1: not known yet */
+ int arena_depth; /* the same in the stack in arena */
+ int frame; /* the most consecutive static call stack frames on top of stack */
};
-/* starting from main bpf function walk all instructions of the function
- * and recursively walk all callees that given function can call.
- * Ignore jump and exit insns.
- */
-static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
- struct bpf_subprog_call_depth_info *dinfo)
+/* what the frame of the subprog adds to the frames of its callers */
+static int subprog_stack_size(struct bpf_verifier_env *env, int s)
{
- struct bpf_subprog_info *subprog = env->subprog_info;
- struct bpf_insn *insn = env->prog->insnsi;
- int depth = 0, frame = 0, i, subprog_end, subprog_depth;
- int arena_depth = 0;
- int total;
- int tmp;
-
- /* no caller idx */
- dinfo[idx].caller = -1;
-
- i = subprog[idx].start;
-process_func:
- dinfo[idx].callx_insn = -1;
-
- /* protect against potential stack overflow that might happen when
- * bpf2bpf calls get combined with tailcalls. Limit the caller's stack
- * depth for such case down to 256 so that the worst case scenario
- * would result in 8k stack size (32 which is tailcall limit * 256 =
- * 8k).
- *
- * To get the idea what might happen, see an example:
- * func1 -> sub rsp, 128
- * subfunc1 -> sub rsp, 256
- * tailcall1 -> add rsp, 256
- * func2 -> sub rsp, 192 (total stack size = 128 + 192 = 320)
- * subfunc2 -> sub rsp, 64
- * subfunc22 -> sub rsp, 128
- * tailcall2 -> add rsp, 128
- * func3 -> sub rsp, 32 (total stack size 128 + 192 + 64 + 32 = 416)
- *
- * tailcall will unwind the current stack frame but it will not get rid
- * of caller's stack as shown on the example above.
- */
- arena_depth += subprog[idx].arena_stack_depth;
- if (arena_depth > env->max_arena_stack_depth)
- env->max_arena_stack_depth = arena_depth;
- if (arena_depth > BPF_ARENA_STACK_MAX) {
- verbose(env, "combined size of the frames in the stack in arena is %d. Too large\n",
- arena_depth);
- return -EACCES;
- }
+ struct bpf_subprog_info *sub = &env->subprog_info[s];
- if (idx && subprog[idx].has_tail_call && depth >= 256) {
- verbose(env,
- "tail_calls are not allowed when call stack of previous frames is %d bytes. Too large\n",
- depth);
- return -EACCES;
- }
+ if (sub->priv_stack_mode == PRIV_STACK_ADAPTIVE)
+ return 0;
+ return round_up_stack_depth(env, sub->stack_depth);
+}
- subprog_depth = round_up_stack_depth(env, subprog[idx].stack_depth);
- if (subprog[idx].priv_stack_mode == PRIV_STACK_ADAPTIVE) {
- if (subprog_depth > env->max_stack_depth)
- env->max_stack_depth = subprog_depth;
- if (subprog_depth > env->stack_limit) {
- verbose(env, "stack size of subprog %d is %d. Too large\n",
- idx, subprog_depth);
- return -EACCES;
- }
- } else {
- depth += subprog_depth;
- if (depth > env->max_stack_depth)
- env->max_stack_depth = depth;
- if (depth > env->stack_limit) {
- total = 0;
- for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller)
- total++;
+/*
+ * A subprog is entered with no more than what one of its callers is entered with plus
+ * the frame of that caller. The graph has no cycles, so this comes to an end.
+ */
+static void compute_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph *cg,
+ struct bpf_subprog_call_depth_info *dinfo)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_subprog_call_depth_info *callee;
+ int depth, arena_depth, frame, j, s;
+ bool changed;
- verbose(env, "combined stack size of %d calls is %d. Too large\n",
- total, depth);
- return -EACCES;
- }
+ for (s = 0; s < cg->cnt; s++) {
+ dinfo[s].caller = -1;
+ dinfo[s].depth = !s || si[s].is_async_cb ? 0 : -1;
}
-continue_func:
- subprog_end = subprog[idx + 1].start;
- for (; i < subprog_end; i++) {
- int next_insn, sidx;
-
- if (bpf_is_callx(insn + i) || bpf_calls_callback(env, i)) {
- /*
- * Walk the callees and the callbacks recorded by
- * the main verification pass one by one, returning to
- * this insn after each.
- */
- if (dinfo[idx].callx_insn != i) {
- dinfo[idx].callx_insn = i;
- dinfo[idx].callx_next = 0;
- }
- sidx = next_callx_callee(env, idx, dinfo[idx].callx_next);
- if (sidx < 0)
+ do {
+ cond_resched();
+ changed = false;
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ if (dinfo[s].depth < 0)
continue;
- dinfo[idx].callx_next = sidx + 1;
- dinfo[idx].ret_insn = i;
- next_insn = subprog[sidx].start;
- } else if (bpf_pseudo_call(insn + i) || bpf_pseudo_func(insn + i)) {
- /* find the callee */
- next_insn = i + insn[i].imm + 1;
- sidx = bpf_find_subprog(env, next_insn);
- if (verifier_bug_if(sidx < 0, env, "callee not found at insn %d", next_insn))
- return -EFAULT;
- if (subprog[sidx].is_async_cb) {
- /* async callbacks don't increase bpf prog stack size unless called directly */
- if (!bpf_pseudo_call(insn + i))
+ depth = dinfo[s].depth + subprog_stack_size(env, s);
+ arena_depth = dinfo[s].arena_depth + si[s].arena_stack_depth;
+ for_each_set_bit(j, subprog_calls(cg, s), cg->cnt) {
+ callee = &dinfo[j];
+ frame = bpf_subprog_is_global(env, j) ? 0 : dinfo[s].frame + 1;
+ if (depth <= callee->depth && arena_depth <= callee->arena_depth &&
+ frame <= callee->frame)
continue;
+ if (depth > callee->depth) {
+ callee->depth = depth;
+ callee->caller = s;
+ }
+ callee->arena_depth = max(callee->arena_depth, arena_depth);
+ callee->frame = max(callee->frame, frame);
+ changed = true;
}
- /* remember insn to return to */
- dinfo[idx].ret_insn = i + 1;
- } else {
- continue;
}
+ } while (changed);
+}
- /* store caller info for after we return from callee */
- dinfo[idx].frame = frame;
+static int check_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph *cg)
+{
+ struct bpf_subprog_info *si = env->subprog_info;
+ struct bpf_subprog_call_depth_info *dinfo;
+ int depth, total, tmp, s, err;
- /* push caller idx into callee's dinfo */
- dinfo[sidx].caller = idx;
+ dinfo = kvzalloc_objs(*dinfo, cg->cnt, GFP_KERNEL_ACCOUNT);
+ if (!dinfo)
+ return -ENOMEM;
+ compute_call_depth(env, cg, dinfo);
- i = next_insn;
+ for_each_set_bit(s, cg->live, cg->cnt) {
+ /* A caller of it is over a limit. That one is reported, not what it calls. */
+ if (dinfo[s].frame > MAX_CALL_FRAMES || dinfo[s].depth > env->stack_limit ||
+ dinfo[s].arena_depth > BPF_ARENA_STACK_MAX)
+ continue;
- idx = sidx;
- frame = bpf_subprog_is_global(env, idx) ? 0 : frame + 1;
- if (frame >= MAX_CALL_FRAMES) {
+ err = -E2BIG;
+ if (dinfo[s].frame >= MAX_CALL_FRAMES) {
verbose(env, "the call stack of %d frames is too deep !\n",
- frame);
- return -E2BIG;
+ dinfo[s].frame);
+ goto out;
}
- goto process_func;
- }
- /* end of for() loop means the last insn of the 'subprog'
- * was reached. Doesn't matter whether it was JA or EXIT
- */
- if (frame == 0 && dinfo[idx].caller < 0)
- return 0;
- if (subprog[idx].priv_stack_mode != PRIV_STACK_ADAPTIVE)
- depth -= round_up_stack_depth(env, subprog[idx].stack_depth);
- arena_depth -= subprog[idx].arena_stack_depth;
- /* pop caller idx from callee */
- idx = dinfo[idx].caller;
+ err = -EACCES;
+ depth = dinfo[s].arena_depth + si[s].arena_stack_depth;
+ if (depth > env->max_arena_stack_depth)
+ env->max_arena_stack_depth = depth;
+ if (depth > BPF_ARENA_STACK_MAX) {
+ verbose(env, "combined size of the frames in the stack in arena is %d. Too large\n",
+ depth);
+ goto out;
+ }
- /* retrieve caller state from its frame */
- frame = dinfo[idx].frame;
- i = dinfo[idx].ret_insn;
+ /*
+ * protect against potential stack overflow that might happen when
+ * bpf2bpf calls get combined with tailcalls. Limit the caller's stack
+ * depth for such case down to 256 so that the worst case scenario
+ * would result in 8k stack size (32 which is tailcall limit * 256 =
+ * 8k).
+ *
+ * To get the idea what might happen, see an example:
+ * func1 -> sub rsp, 128
+ * subfunc1 -> sub rsp, 256
+ * tailcall1 -> add rsp, 256
+ * func2 -> sub rsp, 192 (total stack size = 128 + 192 = 320)
+ * subfunc2 -> sub rsp, 64
+ * subfunc22 -> sub rsp, 128
+ * tailcall2 -> add rsp, 128
+ * func3 -> sub rsp, 32 (total stack size 128 + 192 + 64 + 32 = 416)
+ *
+ * tailcall will unwind the current stack frame but it will not get rid
+ * of caller's stack as shown on the example above.
+ */
+ depth = dinfo[s].depth;
+ if (s && si[s].has_tail_call && depth >= 256) {
+ verbose(env,
+ "tail_calls are not allowed when call stack of previous frames is %d bytes. Too large\n",
+ depth);
+ goto out;
+ }
- goto continue_func;
+ if (si[s].priv_stack_mode == PRIV_STACK_ADAPTIVE) {
+ depth = round_up_stack_depth(env, si[s].stack_depth);
+ if (depth > env->max_stack_depth)
+ env->max_stack_depth = depth;
+ if (depth > env->stack_limit) {
+ verbose(env, "stack size of subprog %d is %d. Too large\n",
+ s, depth);
+ goto out;
+ }
+ continue;
+ }
+ depth = dinfo[s].depth + subprog_stack_size(env, s);
+ if (depth > env->max_stack_depth)
+ env->max_stack_depth = depth;
+ if (depth > env->stack_limit) {
+ total = 0;
+ for (tmp = s; tmp >= 0; tmp = dinfo[tmp].caller)
+ total++;
+
+ verbose(env, "combined stack size of %d calls is %d. Too large\n",
+ total, depth);
+ goto out;
+ }
+ }
+ err = 0;
+out:
+ kvfree(dinfo);
+ return err;
}
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
enum priv_stack_mode priv_stack_mode = PRIV_STACK_UNKNOWN;
- struct bpf_subprog_call_depth_info *dinfo = NULL;
struct bpf_subprog_info *si = env->subprog_info;
struct bpf_call_graph cg = {};
int s, ret;
@@ -6264,21 +6253,8 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
}
}
- dinfo = kvzalloc_objs(*dinfo, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
- if (!dinfo) {
- ret = -ENOMEM;
- goto out;
- }
-
- for (int i = env->subprog_cnt - 1; i >= 0; i--) {
- if (!i || si[i].is_async_cb) {
- ret = check_max_stack_depth_subprog(env, i, dinfo);
- if (ret < 0)
- goto out;
- }
- }
+ ret = check_call_depth(env, &cg);
out:
- kvfree(dinfo);
kvfree(cg.calls);
return ret;
}
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 7/9] selftests/bpf: Test what follows from the chains of calls
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (5 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 6/9] bpf: Use the call graph to compute the depth of chains of calls Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 21:55 ` [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32 Alexei Starovoitov
` (2 subsequent siblings)
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
Add a prog with 32 global functions that call the next one in both branches
of an 'if'. It has 2^32 chains of calls, and its load took 7 minutes. Add
a prog with a tail call in an exception callback that calls nothing. It was
accepted.
The other tests pass before and after the change. No test looked at these
rules: the number of frames and the bytes of the stack in arena when the
second caller has the longer chain, which frame is reported when libbpf
puts a callee in front of its caller, stack arguments two calls above
a tail call, no private stack for a subprog with stack arguments, and which
of two nested callbacks takes a stack in arena.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
.../bpf/progs/test_global_func_deep_stack.c | 49 ++++++++++++
.../bpf/progs/verifier_arena_stack.c | 61 +++++++++++++++
.../bpf/progs/verifier_large_stack.c | 17 ++++
.../bpf/progs/verifier_private_stack.c | 40 ++++++++++
.../selftests/bpf/progs/verifier_tailcall.c | 78 +++++++++++++++++++
5 files changed, 245 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
index edb8a223a3cb..3a852809b078 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
@@ -92,6 +92,55 @@ int XCAT(f, n)(unsigned long a) \
F(37)
+#define ASM_FUNC(linkage, name, insns) \
+linkage __naked __noinline __used int name(void) \
+{ \
+ asm volatile (insns "r0 = 0; exit;" \
+ :: __imm(bpf_get_prandom_u32) : __clobber_all); \
+}
+
+/*
+ * Every function calls the next one in both branches of an 'if': 32 calls are
+ * executed, and there are 2^32 chains of calls.
+ */
+#undef F_0
+#undef FN
+#define F_0 ASM_FUNC(, either0, "")
+#define FN(n, prev) \
+ ASM_FUNC(, either##n, \
+ "call %[bpf_get_prandom_u32];" \
+ "if r0 == 0 goto +2;" \
+ "call either" #prev ";" \
+ "goto +1;" \
+ "call either" #prev ";")
+F(32)
+
+SEC("syscall")
+__success
+__load_if_JITed()
+int global_func_many_chains(void *ctx)
+{
+ return either32();
+}
+
+/*
+ * r1 is the number of calls that follow, so main -> fs7 .. fs0 and main -> fs15 .. fs8
+ * are executed: 9 frames each. main -> fs15 .. fs0 is in the call graph: 17 frames.
+ * libbpf puts fs7() .. fs0() in front of their second caller fs8().
+ */
+#undef F_0
+#undef FN
+#define F_0 ASM_FUNC(static, fs0, "")
+#define FN(n, prev) ASM_FUNC(static, fs##n, "if r1 == 0 goto +2; r1 += -1; call fs" #prev ";")
+F(15)
+
+SEC("syscall")
+__failure __msg("the call stack of 16 frames is too deep !")
+__naked int static_func_deep_stack_second_caller(void)
+{
+ asm volatile ("r1 = 7; call fs7; r1 = 7; call fs15; exit;" ::: __clobber_all);
+}
+
/* Ensure that even 32 levels deep, the function verifies. */
SEC("syscall")
__success
diff --git a/tools/testing/selftests/bpf/progs/verifier_arena_stack.c b/tools/testing/selftests/bpf/progs/verifier_arena_stack.c
index a23ab1ed2f96..1d676da4b5ea 100644
--- a/tools/testing/selftests/bpf/progs/verifier_arena_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_arena_stack.c
@@ -745,6 +745,65 @@ __naked void callback_names_backward(void)
: __clobber_all);
}
+/* adds 10 to what the context points to. callee_with_frame() is two calls away */
+static __naked __noinline __used long far_from_r12_cb(void)
+{
+ asm volatile (
+ "r6 = r2;"
+ "call callee_in_the_middle;"
+ "r1 = *(u64 *)(r6 + 0);"
+ "r1 += r0;"
+ "*(u64 *)(r6 + 0) = r1;"
+ "r0 = 0;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+static __naked __noinline __used long loops_far_from_r12_cb(void)
+{
+ asm volatile (
+ "r3 = r2;"
+ "r1 = 2;"
+ "r2 = far_from_r12_cb ll;"
+ "r4 = 0;"
+ "call %[bpf_loop];"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_loop)
+ : __clobber_all);
+}
+
+SEC("syscall")
+__description("arena stack: the callback that is next to r12 takes a stack")
+__success __retval(60)
+__load_if_JITed()
+/* the end of the main program, the first insn of loops_far_from_r12_cb() */
+__xlated("r0 = r6")
+__xlated("exit")
+__xlated("r3 = r2")
+__xlated("...")
+/* the end of the code that takes a stack, the first insn of far_from_r12_cb() */
+__xlated("r12 = *(u32 *)(r{{[0-9]}} +8)")
+__xlated("r6 = r2")
+__naked void callback_in_callback(void)
+{
+ asm volatile (
+ "r1 = 0;"
+ "*(u64 *)(r10 - 8) = r1;"
+ "r1 = 3;"
+ "r2 = loops_far_from_r12_cb ll;"
+ "r3 = r10;"
+ "r3 += -8;"
+ "r4 = 0;"
+ "call %[bpf_loop];"
+ "r0 = *(u64 *)(r10 - 8);"
+ "exit;"
+ :
+ : __imm(bpf_loop)
+ : __clobber_all);
+}
+
SEC("syscall")
__description("arena stack: call of a callback that uses r12")
__failure __msg("loop_cb() uses R12 and is both called and a callback")
@@ -1009,10 +1068,12 @@ __naked void depth_max(void)
SEC("syscall")
__description("arena stack: more than 32K")
__failure __msg("combined size of the frames in the stack in arena is 32784. Too large")
+/* frame_16() has two callers. The one that has more in the stack in arena counts */
__naked void depth_too_large(void)
{
asm volatile (
".8byte %[adj];"
+ "call frame_16;"
"call frame_16k_calls_16;"
"exit;"
:
diff --git a/tools/testing/selftests/bpf/progs/verifier_large_stack.c b/tools/testing/selftests/bpf/progs/verifier_large_stack.c
index c2a3ddf5ac91..7e4f5e3463a2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_large_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_large_stack.c
@@ -112,6 +112,23 @@ __naked void five_frames_of_512(void)
" ::: __clobber_all);
}
+/* libbpf puts frame_512_leaf() in front of frame_512_depth_2(), which goes over the budget */
+SEC("socket")
+__description("the frame that exceeds the 2 KiB budget is reported, not its callee")
+__load_if_large_stack()
+__failure __msg("combined stack size of 3 calls is 2064. Too large")
+__naked void callee_in_front_of_caller(void)
+{
+ asm volatile (" \
+ r1 = 5; \
+ *(u64 *)(r10 - 1040) = r1; \
+ call frame_512_leaf; \
+ call frame_512_depth_3; \
+ r0 = 0; \
+ exit; \
+" ::: __clobber_all);
+}
+
__used __naked
static void frame_1536_leaf(void)
{
diff --git a/tools/testing/selftests/bpf/progs/verifier_private_stack.c b/tools/testing/selftests/bpf/progs/verifier_private_stack.c
index bbc09f516d92..aa15361bcca5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_private_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_private_stack.c
@@ -70,6 +70,46 @@ __naked void no_private_stack_nested(void)
" ::: __clobber_all);
}
+#ifdef __BPF_FEATURE_STACK_ARGUMENT
+__used
+__naked static long subprog_6args(long a, long b, long c, long d, long e, long f)
+{
+ asm volatile (" \
+ r0 = *(u64 *)(r11 + 8); \
+ *(u64 *)(r10 - 64) = r0; \
+ exit; \
+" ::: __clobber_all);
+}
+
+/* x86-64 has one register for the private stack and for the sixth argument */
+SEC("raw_tp")
+__description("No private stack, stack arguments")
+__success
+__load_if_JITed()
+__arch_x86_64
+__log_level(4) __msg("stack depth max 128")
+__naked void no_private_stack_stack_args(void)
+{
+ asm volatile (" \
+ r1 = 42; \
+ *(u64 *)(r10 - 64) = r1; \
+ *(u64 *)(r11 - 8) = r1; \
+ call subprog_6args; \
+ r0 = 0; \
+ exit; \
+" ::: __clobber_all);
+}
+#else
+SEC("raw_tp")
+__description("No private stack, stack arguments")
+__skip("stack_arg is not supported by compiler")
+__success
+int no_private_stack_stack_args(void)
+{
+ return 0;
+}
+#endif
+
__used
__naked static void cumulative_stack_depth_subprog(void)
{
diff --git a/tools/testing/selftests/bpf/progs/verifier_tailcall.c b/tools/testing/selftests/bpf/progs/verifier_tailcall.c
index 51687da97225..42b90b692dc5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_tailcall.c
+++ b/tools/testing/selftests/bpf/progs/verifier_tailcall.c
@@ -50,6 +50,84 @@ static int subprog_tail_call(void)
: __clobber_all);
}
+/* The exception callback has no ctx, so its tail call can only be dead code */
+__used __noinline
+int exception_cb_tail_call(__u64 cookie)
+{
+ asm volatile (" \
+ r0 = 0; \
+ if r0 == 0 goto +4; \
+ r2 = %[jmp_table] ll; \
+ r3 = 0; \
+ call %[bpf_tail_call]; \
+" :
+ : __imm(bpf_tail_call),
+ __imm_addr(jmp_table)
+ : __clobber_common);
+ return 0;
+}
+
+SEC("tc")
+__description("tail call in an async callback that calls nothing")
+__failure __msg("cannot tail call within callback")
+__attribute__((btf_decl_tag("exception_callback:exception_cb_tail_call")))
+__naked void tail_call_in_async_callback(void)
+{
+ asm volatile (" \
+ r0 = 0; \
+ exit; \
+" ::: __clobber_all);
+}
+
+#if (defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || \
+ (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64)) && \
+ defined(__BPF_FEATURE_STACK_ARGUMENT)
+
+__used __noinline
+static long subprog_6args(long a, long b, long c, long d, long e, long f)
+{
+ return f;
+}
+
+__used __naked
+static int calls_subprog_tail_call(void)
+{
+ asm volatile (" \
+ call subprog_tail_call; \
+ exit; \
+" ::: __clobber_all);
+}
+
+SEC("tc")
+__description("stack arguments two calls above a tail call")
+__failure __msg("tail_calls are not allowed in programs with stack args")
+__load_if_JITed()
+__naked void stack_args_above_tail_call(void)
+{
+ asm volatile (" \
+ r6 = r1; \
+ *(u64 *)(r11 - 8) = 6; \
+ call subprog_6args; \
+ r1 = r6; \
+ call calls_subprog_tail_call; \
+ r0 = 0; \
+ exit; \
+" ::: __clobber_all);
+}
+
+#else
+
+SEC("tc")
+__description("stack arguments two calls above a tail call")
+__skip("stack_arg is not supported by compiler or jit")
+__success
+int stack_args_above_tail_call(void)
+{
+ return 0;
+}
+
+#endif
+
/*
* A tail call unwinds only the frame of the subprog doing it, so the
* frames of its callers stay on the stack. With up to 33 tail calls in
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (6 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 7/9] selftests/bpf: Test what follows from the " Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-04 22:40 ` bot+bpf-ci
2026-11-04 21:55 ` [PATCH bpf-next 9/9] selftests/bpf: Test 32 call frames Alexei Starovoitov
2026-11-05 1:30 ` [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames patchwork-bot+netdevbpf
9 siblings, 1 reply; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
Progs that use Rust crates nest calls deeply and hit the limit of
16 frames. Bump the limit to 32.
The new limit is for JITed progs. A chain of more than 16 frames requires
the JIT, like callx. Such a prog is rejected when the JIT is off, and it
does not fall back to the interpreter when the JIT fails. The check is
a no-op with CONFIG_BPF_JIT_ALWAYS_ON, as on x86-64 and arm64.
A frame number now needs 5 bits. Widen it in bpf_jmp_history_entry and in
the packed linked registers. There the index of a register or a stack slot
loses one bit. The static_assert next to it shows that the index fits.
Widen the mask of frames in liveness.c to 32 bits. Pack struct arg_track
to keep it at 10 bytes: there is an array of them for each insn.
Each verifier state has 16 more pointers. mem_peak of veristat grows by 3%
for sched_ext, by 4% for the selftests, and by 1% for Cilium.
analyze_subprog() follows each chain of calls that passes a pointer to the
stack, before the main pass. At the limit it returns -EINVAL, and the log
has no message. Print which call it is and the message that the main pass
has for too many frames, and return -E2BIG as the main pass does:
f31() passes a pointer to the stack to f32()
the call stack of 33 frames is too deep
analyze_subprog() calls itself for each frame of such a chain. Its frame
has 264 bytes on x86-64 with gcc 13. The 32 frames of the longest chain
take 8.25K of the 16K of the kernel stack.
The progs that test the limit of 16 frames load now. Make their chains of
calls longer:
prog frames result
------------------------------------ ------------------- ----------
global_func3 main, f32 .. f1: 33 rejected
static_func_deep_stack_second_caller 33, 17 are executed rejected
The two tests of the call stack in verifier/calls.c get 16 more calls.
static_func_deep_stack_second_caller and the test of dead code there run
with the JIT only: with the JIT off they get the message about the JIT.
global_func3 accepts 32 and 33 in the message: the main pass counts the
main prog, check_max_stack_depth() does not.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf_verifier.h | 14 +--
kernel/bpf/liveness.c | 11 +-
kernel/bpf/verifier.c | 18 +++-
.../selftests/bpf/progs/test_global_func3.c | 100 +++++++++++++++++-
.../bpf/progs/test_global_func_deep_stack.c | 13 +--
tools/testing/selftests/bpf/verifier/calls.c | 97 +++++++++++++++++
6 files changed, 231 insertions(+), 22 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 60d6d93c57db..d6e41444ab14 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -446,7 +446,9 @@ struct bpf_func_state {
struct loop_stack_entry *loop_stack;
};
-#define MAX_CALL_FRAMES 16
+#define MAX_CALL_FRAMES 32
+/* What the interpreter has stack for. A longer chain of calls requires the JIT. */
+#define MAX_CALL_FRAMES_INTERP 16
/* instruction history flags, used in bpf_jmp_history_entry.flags field.
* Frame number and SPI are stored in dedicated fields of bpf_jmp_history_entry.
@@ -466,24 +468,24 @@ enum {
struct bpf_jmp_history_entry {
/* insn idx can't be bigger than 1 million */
u32 idx : 20;
- u32 frame : 4; /* stack access frame number */
+ u32 frame : 5; /* stack access frame number */
/* special INSN_F_xxx flags */
u32 flags : 4;
- u32 : 4;
+ u32 : 3;
u32 prev_idx : 20;
u32 spi : 12; /* stack slot index */
/*
* Scalar registers and spilled scalars linked to the condition of
* this jump, which need precision tracking together when the jump is
- * backtracked. Each is packed as 4 bits of frame number, one bit
- * telling a register from a stack slot and 11 bits of register or
+ * backtracked. Each is packed as 5 bits of frame number, one bit
+ * telling a register from a stack slot and 10 bits of register or
* slot index, see linked_regs_pack().
*/
u16 linked_regs[BPF_LINKED_REGS_MAX];
u8 linked_regs_cnt;
};
-static_assert(MAX_CALL_FRAMES <= (1 << 4));
+static_assert(MAX_CALL_FRAMES <= (1 << 5));
static_assert(MAX_BPF_STACK_SLOTS <= (1 << 12));
/* Maximum number of bpf_reg_state objects that can exist at once */
diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
index c01037011788..525c0faff1a6 100644
--- a/kernel/bpf/liveness.c
+++ b/kernel/bpf/liveness.c
@@ -818,11 +818,11 @@ static int print_instances(struct bpf_verifier_env *env)
struct arg_track {
union {
s16 off[MAX_ARG_OFFSETS]; /* byte offsets; off_cnt says how many */
- u16 mask; /* arg bitmask when arg == ARG_IMPRECISE */
+ u32 mask; /* arg bitmask when arg == ARG_IMPRECISE */
};
s8 frame; /* absolute frame index, or enum arg_track_state */
s8 off_cnt; /* 0 = offset-imprecise, 1-4 = # of precise offsets */
-};
+} __packed __aligned(2);
enum arg_track_state {
ARG_NONE = -1, /* not derived from any argument */
@@ -1182,7 +1182,7 @@ static struct arg_track fill_from_stack(struct bpf_insn *insn,
int depth)
{
struct arg_track imp = {
- .mask = (1u << (depth + 1)) - 1,
+ .mask = GENMASK(depth, 0),
.frame = ARG_IMPRECISE
};
struct arg_track result = { .frame = ARG_NONE };
@@ -2393,7 +2393,10 @@ static int analyze_subprog(struct bpf_verifier_env *env,
continue;
if (depth == MAX_CALL_FRAMES - 1) {
- err = -EINVAL;
+ verbose(env, "%s() passes a pointer to the stack to %s()\n",
+ bpf_subprog_name(env, subprog), bpf_subprog_name(env, callee));
+ verbose(env, "the call stack of %d frames is too deep\n", depth + 2);
+ err = -E2BIG;
goto out_free;
}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b8f4549da6db..4161ecabfea9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3656,8 +3656,8 @@ static void mark_non_stack_access(struct bpf_verifier_env *env, int idx)
}
/* Layout of one packed linked register in the jump history, see linked_regs_pack() */
-#define LR_FRAMENO_BITS 4
-#define LR_INDEX_BITS 11
+#define LR_FRAMENO_BITS 5
+#define LR_INDEX_BITS 10
#define LR_FRAMENO_MASK ((1u << LR_FRAMENO_BITS) - 1)
#define LR_IS_REG BIT(LR_FRAMENO_BITS)
#define LR_INDEX_OFF (LR_FRAMENO_BITS + 1)
@@ -3693,9 +3693,9 @@ static struct linked_reg *linked_regs_push(struct linked_regs *s)
/*
* Pack linked registers for a jump history entry, one u16 each:
- * - 4 bits frameno
+ * - 5 bits frameno
* - 1 bit is_reg
- * - 11 bits register or stack slot index
+ * - 10 bits register or stack slot index
*/
static void linked_regs_pack(const struct linked_regs *s, u16 *packed)
{
@@ -6127,6 +6127,16 @@ static int check_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph
goto out;
}
+ err = -EOPNOTSUPP;
+ if (dinfo[s].frame >= MAX_CALL_FRAMES_INTERP) {
+ if (!env->prog->jit_requested) {
+ verbose(env, "JIT is required for a call stack of more than %d frames\n",
+ MAX_CALL_FRAMES_INTERP);
+ goto out;
+ }
+ env->prog->jit_required = true;
+ }
+
err = -EACCES;
depth = dinfo[s].arena_depth + si[s].arena_stack_depth;
if (depth > env->max_arena_stack_depth)
diff --git a/tools/testing/selftests/bpf/progs/test_global_func3.c b/tools/testing/selftests/bpf/progs/test_global_func3.c
index b66abb350fb0..16a353195494 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func3.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func3.c
@@ -101,9 +101,105 @@ int f16(struct __sk_buff *skb)
return f15(skb);
}
+static __attribute__ ((noinline))
+int f17(struct __sk_buff *skb)
+{
+ return f16(skb);
+}
+
+static __attribute__ ((noinline))
+int f18(struct __sk_buff *skb)
+{
+ return f17(skb);
+}
+
+static __attribute__ ((noinline))
+int f19(struct __sk_buff *skb)
+{
+ return f18(skb);
+}
+
+static __attribute__ ((noinline))
+int f20(struct __sk_buff *skb)
+{
+ return f19(skb);
+}
+
+static __attribute__ ((noinline))
+int f21(struct __sk_buff *skb)
+{
+ return f20(skb);
+}
+
+static __attribute__ ((noinline))
+int f22(struct __sk_buff *skb)
+{
+ return f21(skb);
+}
+
+static __attribute__ ((noinline))
+int f23(struct __sk_buff *skb)
+{
+ return f22(skb);
+}
+
+static __attribute__ ((noinline))
+int f24(struct __sk_buff *skb)
+{
+ return f23(skb);
+}
+
+static __attribute__ ((noinline))
+int f25(struct __sk_buff *skb)
+{
+ return f24(skb);
+}
+
+static __attribute__ ((noinline))
+int f26(struct __sk_buff *skb)
+{
+ return f25(skb);
+}
+
+static __attribute__ ((noinline))
+int f27(struct __sk_buff *skb)
+{
+ return f26(skb);
+}
+
+static __attribute__ ((noinline))
+int f28(struct __sk_buff *skb)
+{
+ return f27(skb);
+}
+
+static __attribute__ ((noinline))
+int f29(struct __sk_buff *skb)
+{
+ return f28(skb);
+}
+
+static __attribute__ ((noinline))
+int f30(struct __sk_buff *skb)
+{
+ return f29(skb);
+}
+
+static __attribute__ ((noinline))
+int f31(struct __sk_buff *skb)
+{
+ return f30(skb);
+}
+
+static __attribute__ ((noinline))
+int f32(struct __sk_buff *skb)
+{
+ return f31(skb);
+}
+
SEC("tc")
-__failure __msg("the call stack of 17 frames")
+__failure __msg("the call stack of {{3[23]}} frames")
int global_func3(struct __sk_buff *skb)
{
- return f16(skb);
+ return f32(skb);
}
diff --git a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
index 3a852809b078..1b111a65614f 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
@@ -124,21 +124,22 @@ int global_func_many_chains(void *ctx)
}
/*
- * r1 is the number of calls that follow, so main -> fs7 .. fs0 and main -> fs15 .. fs8
- * are executed: 9 frames each. main -> fs15 .. fs0 is in the call graph: 17 frames.
- * libbpf puts fs7() .. fs0() in front of their second caller fs8().
+ * r1 is the number of calls that follow, so main -> fs15 .. fs0 and main -> fs31 .. fs16
+ * are executed: 17 frames each. main -> fs31 .. fs0 is in the call graph: 33 frames.
+ * libbpf puts fs15() .. fs0() in front of their second caller fs16().
*/
#undef F_0
#undef FN
#define F_0 ASM_FUNC(static, fs0, "")
#define FN(n, prev) ASM_FUNC(static, fs##n, "if r1 == 0 goto +2; r1 += -1; call fs" #prev ";")
-F(15)
+F(31)
SEC("syscall")
-__failure __msg("the call stack of 16 frames is too deep !")
+__failure __msg("the call stack of 32 frames is too deep !")
+__load_if_JITed()
__naked int static_func_deep_stack_second_caller(void)
{
- asm volatile ("r1 = 7; call fs7; r1 = 7; call fs15; exit;" ::: __clobber_all);
+ asm volatile ("r1 = 15; call fs15; r1 = 15; call fs31; exit;" ::: __clobber_all);
}
/* Ensure that even 32 levels deep, the function verifies. */
diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index 0af237c02ddf..f9d71e01ddf4 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -1325,6 +1325,54 @@
BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */
BPF_EXIT_INSN(),
/* P */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P1 */
+ BPF_EXIT_INSN(),
+ /* P1 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P2 */
+ BPF_EXIT_INSN(),
+ /* P2 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P3 */
+ BPF_EXIT_INSN(),
+ /* P3 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P4 */
+ BPF_EXIT_INSN(),
+ /* P4 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P5 */
+ BPF_EXIT_INSN(),
+ /* P5 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P6 */
+ BPF_EXIT_INSN(),
+ /* P6 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P7 */
+ BPF_EXIT_INSN(),
+ /* P7 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P8 */
+ BPF_EXIT_INSN(),
+ /* P8 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P9 */
+ BPF_EXIT_INSN(),
+ /* P9 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P10 */
+ BPF_EXIT_INSN(),
+ /* P10 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P11 */
+ BPF_EXIT_INSN(),
+ /* P11 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P12 */
+ BPF_EXIT_INSN(),
+ /* P12 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P13 */
+ BPF_EXIT_INSN(),
+ /* P13 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P14 */
+ BPF_EXIT_INSN(),
+ /* P14 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P15 */
+ BPF_EXIT_INSN(),
+ /* P15 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P16 */
+ BPF_EXIT_INSN(),
+ /* P16 */
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
@@ -1387,10 +1435,59 @@
BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P */
BPF_EXIT_INSN(),
/* P */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P1 */
+ BPF_EXIT_INSN(),
+ /* P1 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P2 */
+ BPF_EXIT_INSN(),
+ /* P2 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P3 */
+ BPF_EXIT_INSN(),
+ /* P3 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P4 */
+ BPF_EXIT_INSN(),
+ /* P4 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P5 */
+ BPF_EXIT_INSN(),
+ /* P5 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P6 */
+ BPF_EXIT_INSN(),
+ /* P6 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P7 */
+ BPF_EXIT_INSN(),
+ /* P7 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P8 */
+ BPF_EXIT_INSN(),
+ /* P8 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P9 */
+ BPF_EXIT_INSN(),
+ /* P9 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P10 */
+ BPF_EXIT_INSN(),
+ /* P10 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P11 */
+ BPF_EXIT_INSN(),
+ /* P11 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P12 */
+ BPF_EXIT_INSN(),
+ /* P12 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P13 */
+ BPF_EXIT_INSN(),
+ /* P13 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P14 */
+ BPF_EXIT_INSN(),
+ /* P14 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P15 */
+ BPF_EXIT_INSN(),
+ /* P15 */
+ BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call P16 */
+ BPF_EXIT_INSN(),
+ /* P16 */
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_XDP,
+ .flags = F_NEEDS_JIT_ENABLED,
.errstr = "call stack",
.result = REJECT,
},
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32
2026-11-04 21:55 ` [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32 Alexei Starovoitov
@ 2026-11-04 22:40 ` bot+bpf-ci
2026-11-05 0:32 ` Alexei Starovoitov
0 siblings, 1 reply; 13+ messages in thread
From: bot+bpf-ci @ 2026-11-04 22:40 UTC (permalink / raw)
To: alexei.starovoitov, bpf
Cc: daniel, andrii, eddyz87, memxor, ast, andrii, daniel, martin.lau,
eddyz87, yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 3042 bytes --]
> bpf: Bump MAX_CALL_FRAMES to 32
TL;DR: Raising MAX_CALL_FRAMES to 32 may let bpf2bpf chains plus tail calls
overflow the kernel stack at run time, since the 256-byte check counts only
BPF stack. The gap predates the patch, which doubles it.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -6127,6 +6127,16 @@ static int check_call_depth(struct bpf_verifier_env *env, struct bpf_call_graph
> goto out;
> }
>
> + err = -EOPNOTSUPP;
> + if (dinfo[s].frame >= MAX_CALL_FRAMES_INTERP) {
> + if (!env->prog->jit_requested) {
> + verbose(env, "JIT is required for a call stack of more than %d frames\n",
> + MAX_CALL_FRAMES_INTERP);
> + goto out;
> + }
> + env->prog->jit_required = true;
> + }
> +
> err = -EACCES;
> depth = dinfo[s].arena_depth + si[s].arena_stack_depth;
> if (depth > env->max_arena_stack_depth)
Can the combination of 32 frames and tail calls overflow the kernel stack
at run time?
The only bound on bpf2bpf calls combined with tail calls is the rule in
check_call_depth() that the summed BPF stack of the callers of a subprog
that tail calls must stay below 256 bytes:
if (s && si[s].has_tail_call && depth >= 256) {
That rule counts only BPF stack, not the kernel stack each JITed frame
takes. On x86-64 a tail_call_reachable subprog uses at least 32 bytes of
kernel stack even with stack_depth 0 (the return address, push rbp in
emit_prologue(), and push rax; push rax in emit_prologue_tail_call()). A
tail call unwinds only the frame that makes it, so the callers' frames stay
on the stack while the next program runs, and the tail call counter is
shared through tcc_ptr, so MAX_TAIL_CALL_CNT (33) tail calls can happen in
one run.
For example, main calls f1 .. f31, all static with no stack, and f31 calls
bpf_tail_call() into a prog array slot holding the same program. f31 is at
frame index 31, below MAX_CALL_FRAMES, so it is accepted.
dinfo[f31].depth is 0, so it passes the 256 check, and the program is
JITed because jit_required is set.
Each tail call level then keeps 31 frames * 32 bytes = 992 bytes. After 33
tail calls that is about 32.7K, twice the 16K THREAD_SIZE and IRQ_STACK_SIZE
on x86-64 without KASAN.
The gap existed before this patch, since with 16 frames the same
construction keeps about 15 * 32 * 33 = 15.8K plus up to 33 * 240 bytes of
BPF stack. But doubling the frame limit doubles the term the 256-byte
check does not count.
The commit message does the stack arithmetic only for the verifier's
analyze_subprog() recursion, not for runtime tail call chains.
Would it make sense to limit tail_call_reachable chains to
MAX_CALL_FRAMES_INTERP frames, or to add a per-frame cost to the 256-byte
tail call check?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41921975876
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32
2026-11-04 22:40 ` bot+bpf-ci
@ 2026-11-05 0:32 ` Alexei Starovoitov
0 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-05 0:32 UTC (permalink / raw)
To: bot+bpf-ci, bpf
Cc: daniel, andrii, eddyz87, memxor, martin.lau, yonghong.song, mason,
ihor.solodrai
On Wed, Nov 04, 2026 at 02:40 PM bot+bpf-ci@kernel.org <bot+bpf-ci@kernel.org> wrote:
> Can the combination of 32 frames and tail calls overflow the kernel stack
> at run time?
Not from this patch. It's an old bug.
MAX_CALL_FRAMES is what the verifier tracks. It doesn't limit the frames
at run time. A call of a global function resets the count since
commit ad95d3c758d8 ("bpf: Only enforce 8 frame call stack limit for all-static stacks").
Make f1 .. f31 global and add more of them. Such prog loads without
this patch.
The follow up (the verifier rewrite) series address it.
> Would it make sense to limit tail_call_reachable chains to
> MAX_CALL_FRAMES_INTERP frames, or to add a per-frame cost to the 256-byte
> tail call check?
No. dinfo[s].frame is 0 in a global function, so a limit on it doesn't help.
A cost per frame rejects progs that load today, like
tail_call_caller_stack_ok() with 240 bytes in the caller.
Not for this series.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH bpf-next 9/9] selftests/bpf: Test 32 call frames
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (7 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 8/9] bpf: Bump MAX_CALL_FRAMES to 32 Alexei Starovoitov
@ 2026-11-04 21:55 ` Alexei Starovoitov
2026-11-05 1:30 ` [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames patchwork-bot+netdevbpf
9 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-11-04 21:55 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor
From: Alexei Starovoitov <ast@kernel.org>
The limit is 32 frames now. Add progs that have exactly 32 frames, and one
that has 33.
prog frames result
------------------------------------ --------------------- ----------
global_func3_32_frames main, f31 .. f1: 32 loads
global_func3_32_frames_stack_pointer main, p1 .. p31: 32 returns 60
global_func3_33_frames_stack_pointer main, p0 .. p31: 33 rejected
static_func_deep_stack_marks main, fm30 .. fm0: 32 rejected
The stack_pointer progs pass a pointer to the stack down the chain.
analyze_subprog() calls itself for each frame of such a chain. It sees the
chain before the main pass, so the 33 frames get its two messages.
static_func_deep_stack_marks has an invalid access in frame 31, on the path
that is verified second. The verifier gets there only if the marks that the
first path leaves have the right frame number. Liveness needs it in the
mask of frames, precision in the jump history and in the linked registers.
No other test depends on a frame number above 15 there.
A chain of more than 16 frames requires the JIT. The two progs that load
run with the JIT only.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
.../selftests/bpf/progs/test_global_func3.c | 81 +++++++++++++++++++
.../bpf/progs/test_global_func_deep_stack.c | 33 ++++++++
2 files changed, 114 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/test_global_func3.c b/tools/testing/selftests/bpf/progs/test_global_func3.c
index 16a353195494..b332704b395c 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func3.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func3.c
@@ -197,6 +197,87 @@ int f32(struct __sk_buff *skb)
return f31(skb);
}
+SEC("tc")
+__success
+__load_if_JITed()
+int global_func3_32_frames(struct __sk_buff *skb)
+{
+ return f31(skb);
+}
+
+#define PTR_FRAME(name, next) \
+static __attribute__ ((noinline)) \
+long name(long *p) \
+{ \
+ *p += 1; \
+ return next(p) + 1; \
+}
+
+static __attribute__ ((noinline))
+long p31(long *p)
+{
+ /* volatile: the compiler must not pass the value in place of the pointer */
+ return *(volatile long *)p;
+}
+
+PTR_FRAME(p30, p31)
+PTR_FRAME(p29, p30)
+PTR_FRAME(p28, p29)
+PTR_FRAME(p27, p28)
+PTR_FRAME(p26, p27)
+PTR_FRAME(p25, p26)
+PTR_FRAME(p24, p25)
+PTR_FRAME(p23, p24)
+PTR_FRAME(p22, p23)
+PTR_FRAME(p21, p22)
+PTR_FRAME(p20, p21)
+PTR_FRAME(p19, p20)
+PTR_FRAME(p18, p19)
+PTR_FRAME(p17, p18)
+PTR_FRAME(p16, p17)
+PTR_FRAME(p15, p16)
+PTR_FRAME(p14, p15)
+PTR_FRAME(p13, p14)
+PTR_FRAME(p12, p13)
+PTR_FRAME(p11, p12)
+PTR_FRAME(p10, p11)
+PTR_FRAME(p9, p10)
+PTR_FRAME(p8, p9)
+PTR_FRAME(p7, p8)
+PTR_FRAME(p6, p7)
+PTR_FRAME(p5, p6)
+PTR_FRAME(p4, p5)
+PTR_FRAME(p3, p4)
+PTR_FRAME(p2, p3)
+PTR_FRAME(p1, p2)
+PTR_FRAME(p0, p1)
+
+/*
+ * What a subprog does with the stack of its callers is found for every chain of calls that
+ * hands a pointer to the stack down. The function that does it calls itself for every frame.
+ */
+SEC("tc")
+__success __retval(60)
+__load_if_JITed()
+int global_func3_32_frames_stack_pointer(struct __sk_buff *skb)
+{
+ long x = 0;
+
+ return p1(&x);
+}
+
+/* That function sees the chain before the main pass does. */
+SEC("tc")
+__failure
+__msg("p30() passes a pointer to the stack to p31()")
+__msg("the call stack of 33 frames is too deep")
+int global_func3_33_frames_stack_pointer(struct __sk_buff *skb)
+{
+ long x = 0;
+
+ return p0(&x);
+}
+
SEC("tc")
__failure __msg("the call stack of {{3[23]}} frames")
int global_func3(struct __sk_buff *skb)
diff --git a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
index 1b111a65614f..11af79aa2ced 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c
@@ -142,6 +142,39 @@ __naked int static_func_deep_stack_second_caller(void)
asm volatile ("r1 = 15; call fs15; r1 = 15; call fs31; exit;" ::: __clobber_all);
}
+/*
+ * fm0() is frame 31. On the path that is verified first fp-16 and r7 are linked, so 'r7 > 7'
+ * bounds fp-16. On the second path they are not. To see that, the verifier needs fp-16 live and
+ * fp-16 and r7 precise in the checkpoint at 'goto +0'. These marks go through all that holds
+ * a frame number: the mask of frames in the liveness pass, for which r1 can point to each of
+ * the 32 frames, the jump history, and the linked registers in it. The liveness pass counts
+ * the frames of a chain of calls that passes a pointer to the stack: here r10 of the main prog.
+ */
+#undef F_0
+#undef FN
+#define F_0 \
+ ASM_FUNC(static, fm0, \
+ "call %[bpf_get_prandom_u32]; r6 = r0; r6 &= 0xff;" \
+ "call %[bpf_get_prandom_u32]; r7 = r0; r7 &= 0xff;" \
+ "call %[bpf_get_prandom_u32];" \
+ "if r0 > 1 goto +1; r7 = r6;" \
+ "*(u64 *)(r10 - 16) = r6; r1 = r10; r1 += -16;" \
+ "r2 = -8; r3 = r10; r3 += r2;" \
+ "*(u64 *)(r3 + 0) = r1; r1 = *(u64 *)(r3 + 0);" \
+ "goto +0;" \
+ "if r7 > 7 goto +3; r2 = *(u64 *)(r1 + 0);" \
+ "if r2 <= 7 goto +1; r0 = *(u8 *)(r2 + 0);")
+#define FN(n, prev) ASM_FUNC(static, fm##n, "call fm" #prev ";")
+F(30)
+
+SEC("syscall")
+__failure __msg("R2 invalid mem access 'scalar'")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked int static_func_deep_stack_marks(void)
+{
+ asm volatile ("r1 = r10; call fm30; exit;" ::: __clobber_all);
+}
+
/* Ensure that even 32 levels deep, the function verifies. */
SEC("syscall")
__success
--
2.55.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames
2026-11-04 21:55 [PATCH bpf-next 0/9] bpf: Check chains of calls over the call graph, allow 32 frames Alexei Starovoitov
` (8 preceding siblings ...)
2026-11-04 21:55 ` [PATCH bpf-next 9/9] selftests/bpf: Test 32 call frames Alexei Starovoitov
@ 2026-11-05 1:30 ` patchwork-bot+netdevbpf
9 siblings, 0 replies; 13+ messages in thread
From: patchwork-bot+netdevbpf @ 2026-11-05 1:30 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: bpf, daniel, andrii, eddyz87, memxor
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Wed, 4 Nov 2026 21:55:14 +0000 you wrote:
> From: Alexei Starovoitov <ast@kernel.org>
>
> check_max_stack_depth() walks the chains of calls of a prog one by one:
>
> main main -> A -> C -> D
> / \ main -> A -> C -> E
> A B main -> B -> C -> D
> \ / main -> B -> C -> E
> C
> / \
> D E
>
> [...]
Here is the summary with links:
- [bpf-next,1/9] bpf: Build the call graph of a prog after the main verification pass
https://git.kernel.org/bpf/bpf-next/c/e4b57476a300
- [bpf-next,2/9] bpf: Use the call graph to find what runs in a callback
https://git.kernel.org/bpf/bpf-next/c/904f23207eb1
- [bpf-next,3/9] bpf: Use the call graph to find what gets to a tail call
https://git.kernel.org/bpf/bpf-next/c/e7e2abda5f28
- [bpf-next,4/9] bpf: Use the call graph to find callbacks that take a stack in arena
https://git.kernel.org/bpf/bpf-next/c/4bf031da4fdb
- [bpf-next,5/9] bpf: Use the call graph to choose subprogs with a private stack
https://git.kernel.org/bpf/bpf-next/c/cfede35c4193
- [bpf-next,6/9] bpf: Use the call graph to compute the depth of chains of calls
https://git.kernel.org/bpf/bpf-next/c/abbf6b7c6626
- [bpf-next,7/9] selftests/bpf: Test what follows from the chains of calls
https://git.kernel.org/bpf/bpf-next/c/b6e223c6435e
- [bpf-next,8/9] bpf: Bump MAX_CALL_FRAMES to 32
https://git.kernel.org/bpf/bpf-next/c/1b00d7dcaa03
- [bpf-next,9/9] selftests/bpf: Test 32 call frames
https://git.kernel.org/bpf/bpf-next/c/32a1783fd695
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 13+ messages in thread