bpf: Avoid quadratic successor rescan in bpf_compute_scc
Subsystems (4)
Daniel Borkmann
maintainerPATCH 1/6 bpf: Avoid quadratic successor rescan in bpf_compute_scc
The iterative Tarjan DFS in bpf_compute_scc() emulates recursion with an explicit 'dfs' stack: when a successor has not been visited yet, the successor is pushed and the walk restarts at the top of the loop. On the way back to a vertex the successor scan starts over at index zero, so a vertex with k successors rescans up to k successors on each of its up to k descents, i.e. O(k^2) work.
For ordinary instructions k <= 2 and this is irrelevant. For a gotox the successors are the jump table of the containing subprogram, whose size is bounded only by the max_entries of the insn_array map, so k can reach the 1M instruction complexity limit. Loading such a program keeps a CPU busy in the loop for a very long time before verification even begins.
Record in 'dfs_pos' the successor index each frame stopped at and resume the scan there. Each edge is therefore examined a bounded number of times and the walk becomes linear in the number of edges.
--- kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------ 1 file changed, 35 insertions(+), 6 deletions(-)
kernel/bpf/cfg.c +35 -6
@@ -749,7 +749,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)struct bpf_insn_aux_data *aux = env->insn_aux_data;const u32 insn_cnt = env->prog->len;int stack_sz, dfs_sz, err =0 ; -u32 *stack, *pre, *low, *dfs; +u32 *stack, *pre, *low, *dfs, *dfs_pos;u32 i, j, t, w;u32 next_preorder_num;u32 next_scc_id;
@@ -762,13 +762,16 @@ int bpf_compute_scc(struct bpf_verifier_env *env)* - 'stack' accumulates vertices in DFS order, see invariant comment below; * - 'pre[t] == p' => preorder number of vertex 't' is 'p'; * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n'; -* - 'dfs' DFS traversal stack, used to emulate explicit recursion. +* - 'dfs' DFS traversal stack, used to emulate explicit recursion; +* - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its +* successors at index 'j'. */ stack =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); pre =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); low =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); dfs =kvcalloc (insn_cnt,sizeof (*dfs),GFP_KERNEL_ACCOUNT ); -if (!stack || !pre || !low || !dfs) { + dfs_pos =kvcalloc (insn_cnt,sizeof (*dfs_pos),GFP_KERNEL_ACCOUNT ); +if (!stack || !pre || !low || !dfs || !dfs_pos) { err = -ENOMEM ; goto exit; }
@@ -851,6 +854,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env) stack_sz =0 ; dfs_sz =1 ; dfs[0 ] = i; + dfs_pos[0 ] =0 ; dfs_continue:while (dfs_sz) { w = dfs[dfs_sz -1 ];
@@ -860,13 +864,37 @@ int bpf_compute_scc(struct bpf_verifier_env *env) next_preorder_num++; stack[stack_sz++] = w; } -/* Visit 'w' successors */ +/* +* Visit 'w' successors, resuming at the successor this +* frame last descended into. Restarting the scan at zero +* on every return to 'w' would examine each successor +* once per descent, i.e. quadratic in the number of +* successors, which for a gotox is the size of the jump +* table. +* +* Re-folding the successors before that index would be a +* no-op. Such a successor 's' has 'pre[s] != 0' by then, +* so it is never pushed onto 'dfs' again, and low[s] can +* only decrease while 's' is the top of 'dfs'. If 's' is +* still on 'dfs' it sits below 'w' and cannot become the +* top before 'w' is popped; otherwise the only remaining +* write to low[s] is the pop of its SCC, setting it to +* NOT_ON_STACK, for which the min below is a no-op. +*/ succ =bpf_insn_successors (env, w); -for (j =0 ; j < succ->cnt; ++j) { +for (j = dfs_pos[dfs_sz -1 ]; j < succ->cnt; ++j) {if (pre[succ->items[j]]) { low[w] =min (low[w], low[succ->items[j]]); }else { - dfs[dfs_sz++] = succ->items[j]; +/* +* Resume at 'j', not 'j + 1': the successor +* is revisited once its DFS completes, to +* fold its low[] into low[w]. +*/ + dfs_pos[dfs_sz -1 ] = j; + dfs_pos[dfs_sz] =0 ; + dfs[dfs_sz] = succ->items[j]; + dfs_sz++; goto dfs_continue; } }
@@ -916,5 +944,6 @@ int bpf_compute_scc(struct bpf_verifier_env *env)kvfree (pre);kvfree (low);kvfree (dfs); +kvfree (dfs_pos);return err; }
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH 2/6 bpf: Bound the number of indirect jump edges in a program
Every gotox instruction gets its own copy of the jump table of the subprog containing it, and each distinct target in that table is a CFG successor of the instruction. The number of such edges is therefore the number of gotox instructions times the number of distinct targets, and neither factor is bounded by anything except the instruction limit.
What is expensive is a BPF prog whose gotox instructions are themselves the targets, which makes the edge count quadratic. 1024 such gotox are already ~1e6 edges and about 4s of CPU to load.
Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka the limit as the number of instructions the verifier processes. Progs with real switch statements are orders of magnitude below this.
--- include/linux/bpf_verifier.h | 1 + kernel/bpf/cfg.c | 15 +++++++++++++++ 2 files changed, 16 insertions(+)
include/linux/bpf_verifier.h +1 -0
@@ -977,6 +977,7 @@ struct bpf_verifier_env {int cur_stack;/* current position in the insn_postorder vector */ int cur_postorder; +u32 gotox_edges; } cfg;struct backtrack_state bt;struct bpf_jmp_history_entry *cur_hist_ent;
kernel/bpf/cfg.c +15 -0
@@ -9,6 +9,8 @@ #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) +#define BPF_MAX_GOTOX_EDGES BPF_COMPLEXITY_LIMIT_INSNS +/* non-recursive DFS pseudo code * 1 procedure DFS-iterative(G,v): * 2 label v as discovered
@@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)return PTR_ERR (jt); env->insn_aux_data[t].jt = jt; + +if (check_add_overflow (env->cfg.gotox_edges, jt->cnt, + &env->cfg.gotox_edges) || + env->cfg.gotox_edges >BPF_MAX_GOTOX_EDGES ) { +verbose (env,"number of indirect jump edges in the program exceeds %u\n" , +BPF_MAX_GOTOX_EDGES ); +bpf_diag_program_structure ( + env, t,"too many indirect jump edges" , +"Reduce the number of indirect jumps, or the number of distinct targets they can reach." , +"The program has more than %u indirect jump edges in total, counted over every gotox instruction." , +BPF_MAX_GOTOX_EDGES ); +return -E2BIG ; + } }mark_prune_point (env, t);
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [Critical] Integer overflow in jump table size calculation leads to massive out-of-bounds memory access. --
commit 4185a35dbc8e33f3114fd8855cb5ca01b0ecf5a9
Author: Daniel Borkmann <[email protected]>
bpf: Bound the number of indirect jump edges in a program
Bounds the total number of gotox edges across the program at BPF_COMPLEXITY_LIMIT_INSNS to prevent excessive memory and CPU usage during program loading.
[ ... ]
Quoted 11 lines
kernel/bpf/cfg.c +3
-0@@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)return PTR_ERR (jt); env->insn_aux_data[t].jt = jt; + + if (check_add_overflow(env->cfg.gotox_edges, jt->cnt, + &env->cfg.gotox_edges) ||
kernel/bpf/cfg.c static int visit_gotox_insn(int t, struct bpf_verifier_env *env) · line 405
Quoted 10 lines
kernel/bpf/cfg.c +10
-0+ env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) { +verbose (env,"number of indirect jump edges in the program exceeds %u\n" , +BPF_MAX_GOTOX_EDGES ); +bpf_diag_program_structure ( + env, t,"too many indirect jump edges" , +"Reduce the number of indirect jumps, or the number of distinct targets they can reach." , +"The program has more than %u indirect jump edges in total, counted over every gotox instruction." , +BPF_MAX_GOTOX_EDGES ); +return -E2BIG ; + }
[Severity: Critical]
This isn't a bug introduced by this patch, but it is a pre-existing issue in the CFG discovery logic that remains unfixed in this patch series.
Can jt_from_subprog() in kernel/bpf/cfg.c overflow the shift operation when calculating the size for memcpy()?
If a user with CAP_BPF creates an INSN_ARRAY map with a very large max_entries (e.g., 0x20000000) and populates it, jt_cur->cnt can be up to map->max_entries.
In kernel/bpf/cfg.c:jt_from_subprog():
memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
If jt_cur->cnt reaches 0x20000000, the expression jt_cur->cnt << 2 evaluates as a signed 32-bit integer, resulting in -2147483648.
When passed to memcpy(), which expects a size_t, this negative value is sign-extended to 0xFFFFFFFF80000000 on 64-bit systems. memcpy() attempts to copy over 18 exabytes of data, causing a catastrophic page fault.
Additionally, if max_entries is 0x40000000, the shift results in 0, leaving jt->items uninitialized before it is passed to sort_insn_array_uniq().
Quoted 3 lines
kernel/bpf/cfg.c +0
-0}mark_prune_point (env, t);
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Daniel Borkmann
maintainerRe: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program
Quoted 4 lines · On 9/9/26 10:57 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [Critical] Integer overflow in jump table size calculation leads to massive out-of-bounds memory access.
false positive
Quoted 46 lines
commit
4185a35dbc8e33f3114fd8855cb5ca01b0ecf5a9
Author: Daniel Borkmann <[email protected]>bpf: Bound the number of indirect jump edges in a program
Bounds the total number of gotox edges across the program at
BPF_COMPLEXITY_LIMIT_INSNSto prevent excessive memory and CPU usage during program loading.Reported-by STAR Labs SG <[email protected]>[ ... ]
Quoted 11 lines
kernel/bpf/cfg.c +3
-0@@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)return PTR_ERR (jt); env->insn_aux_data[t].jt = jt; + + if (check_add_overflow(env->cfg.gotox_edges, jt->cnt, + &env->cfg.gotox_edges) ||kernel/bpf/cfg.c static int visit_gotox_insn(int t, struct bpf_verifier_env *env) · line 405
Quoted 10 lines
kernel/bpf/cfg.c +10
-0+ env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) { +verbose (env,"number of indirect jump edges in the program exceeds %u\n" , +BPF_MAX_GOTOX_EDGES ); +bpf_diag_program_structure ( + env, t,"too many indirect jump edges" , +"Reduce the number of indirect jumps, or the number of distinct targets they can reach." , +"The program has more than %u indirect jump edges in total, counted over every gotox instruction." , +BPF_MAX_GOTOX_EDGES ); +return -E2BIG ; + }[Severity: Critical]
This isn't a bug introduced by this patch, but it is a pre-existing issue in the CFG discovery logic that remains unfixed in this patch series.Can
jt_from_subprog()inkernel/bpf/cfg.coverflow the shift operation when calculating the size formemcpy()?If a user with
CAP_BPFcreates anINSN_ARRAYmap with a very largemax_entries(e.g.,0x20000000) and populates it,jt_cur->cntcan be up tomap->max_entries.
Quoted 6 lines
In kernel/bpf/cfg.c:jt_from_subprog():
memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);If
jt_cur->cntreaches0x20000000, the expressionjt_cur->cnt<< 2 evaluates as a signed 32-bit integer, resulting in -2147483648.
Anything above max entries of 0x1FFFFFFF gets rejected, so this should not be possible. I tried to reproduce the above and can confirm this is the case.
Quoted 7 lines
When passed to
memcpy(), which expects asize_t, this negative value is sign-extended to0xFFFFFFFF80000000on 64-bit systems.memcpy()attempts to copy over 18 exabytes of data, causing a catastrophic page fault.Additionally, if
max_entriesis0x40000000, the shift results in 0, leavingjt->itemsuninitialized before it is passed tosort_insn_array_uniq().
Re: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program
In reply to Daniel BorkmannQuoted 69 lines · Daniel Borkmann
Every gotox instruction gets its own copy of the jump table of the subprog containing it, and each distinct target in that table is a CFG successor of the instruction. The number of such edges is therefore the number of gotox instructions times the number of distinct targets, and neither factor is bounded by anything except the instruction limit.
What is expensive is a BPF prog whose gotox instructions are themselves the targets, which makes the edge count quadratic. 1024 such gotox are already ~1e6 edges and about 4s of CPU to load.
Bound the total across the program at
BPF_COMPLEXITY_LIMIT_INSNS, aka the limit as the number of instructions the verifier processes. Progs with real switch statements are orders of magnitude below this.Fixes 493d9e0d6083 ("bpf, x86: add support for indirect jumps")Reported-by STAR Labs SG <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>--- include/linux/bpf_verifier.h | 1 + kernel/bpf/cfg.c | 15 +++++++++++++++ 2 files changed, 16 insertions(+)include/linux/bpf_verifier.h +1
-0@@ -977,6 +977,7 @@ struct bpf_verifier_env {int cur_stack;/* current position in the insn_postorder vector */ int cur_postorder; +u32 gotox_edges; } cfg;struct backtrack_state bt;struct bpf_jmp_history_entry *cur_hist_ent;kernel/bpf/cfg.c +15
-0@@ -9,6 +9,8 @@ #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) +#define BPF_MAX_GOTOX_EDGES BPF_COMPLEXITY_LIMIT_INSNS +/* non-recursive DFS pseudo code * 1 procedure DFS-iterative(G,v): * 2 label v as discovered @@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)return PTR_ERR (jt); env->insn_aux_data[t].jt = jt; + +if (check_add_overflow (env->cfg.gotox_edges, jt->cnt, + &env->cfg.gotox_edges) || + env->cfg.gotox_edges >BPF_MAX_GOTOX_EDGES ) { +verbose (env,"number of indirect jump edges in the program exceeds %u\n" , +BPF_MAX_GOTOX_EDGES ); +bpf_diag_program_structure ( + env, t,"too many indirect jump edges" , +"Reduce the number of indirect jumps, or the number of distinct targets they can reach." , +"The program has more than %u indirect jump edges in total, counted over every gotox instruction." , +BPF_MAX_GOTOX_EDGES ); +return -E2BIG ; + } }mark_prune_point (env, t);Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH 3/6 bpf: Cache the jump table of a subprogram during CFG discovery
In reply to Daniel Borkmanncreate_jt() builds the jump table of the subprogram containing a gotox by copying out and sorting every insn_array map of the program, and it does so once per gotox instruction. The cost is therefore the number of gotox instructions times the number of entries in all of the maps. A program of 4003 instructions with 2000 gotox and one 500k entry map holding two distinct targets has 4000 indirect jump edges, 0.4% of the limit, and takes 351s to be rejected. The map costs next to nothing to prepare, as an unset entry is already a valid target. At the insn limit, with a single 1M entry map, the same shape extrapolates to 43 hours.
All gotox instructions of a subprogram share the same jump table, so build the table of every subprogram in a single pass over the maps and hand each gotox a copy of it. Instruction aux data owns its jump table, see bpf_clear_insn_aux_data(), hence the copy; the copies add up to the number of indirect jump edges, which visit_gotox_insn() already bounds.
check_cfg() is then linear in the number of map entries plus the number of indirect jump edges, so what still scales now with the program is what BPF_MAX_GOTOX_EDGES bounds:
gotox map entries edges before after
----------------------------------------------
500 250000 1000 36.55s 0.07s 1000 250000 2000 75.65s 0.07s 2000 250000 4000 153.44s 0.07s 2000 125000 4000 69.61s 0.04s 2000 500000 4000 351.27s 0.15s
--- include/linux/bpf_verifier.h | 2 + kernel/bpf/cfg.c | 99 +++++++++++++++++++++++------------- 2 files changed, 65 insertions(+), 36 deletions(-)
include/linux/bpf_verifier.h +2 -0
@@ -805,6 +805,7 @@ struct bpf_subprog_info {u32 linfo_idx;/* The idx to the main_prog->aux->linfo */ u32 postorder_start;/* The idx to the env->cfg.insn_postorder */ u32 exit_idx;/* Index of one of the BPF_EXIT instructions in this subprogram */ +struct bpf_iarray *jt;/* jump table shared by all gotox of this subprogram */ u16 stack_depth;/* max. stack depth used by this function */ u16 stack_extra;u32 insns_total;
@@ -978,6 +979,7 @@ struct bpf_verifier_env {/* current position in the insn_postorder vector */ int cur_postorder;u32 gotox_edges; +bool subprog_jts_ready; } cfg;struct backtrack_state bt;struct bpf_jmp_history_entry *cur_hist_ent;
kernel/bpf/cfg.c +63 -36
140 lines not on this page · raw message
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery
Is the block comment above accurate? It states the table is "all maps whose targets land inside that subprogram", but the code attributes a map by its first entry only:
Quoted 24 lines
include/linux/bpf_verifier.h +2
-0@@ -805,6 +805,7 @@ struct bpf_subprog_info {u32 linfo_idx;/* The idx to the main_prog->aux->linfo */ u32 postorder_start;/* The idx to the env->cfg.insn_postorder */ u32 exit_idx;/* Index of one of the BPF_EXIT instructions in this subprogram */ +struct bpf_iarray *jt;/* jump table shared by all gotox of this subprogram */ u16 stack_depth;/* max. stack depth used by this function */ u16 stack_extra;u32 insns_total;@@ -978,6 +979,7 @@ struct bpf_verifier_env {/* current position in the insn_postorder vector */ int cur_postorder;u32 gotox_edges; +bool subprog_jts_ready; } cfg;struct backtrack_state bt;struct bpf_jmp_history_entry *cur_hist_ent;kernel/bpf/cfg.c +0
-0
[ ... ]
Quoted 29 lines
kernel/bpf/cfg.c +8
-7@@ -286,15 +286,17 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map) }/* -* Find and collect all maps which fit in the subprog. Return the result as one -* combined jump table in jt->items (allocated with kvcalloc) +* Collect the jump table of every subprogram that has one, as the combined +* table of all maps whose targets land inside that subprogram. All gotox +* instructions of a subprogram share the same table, so this is done in a +* single pass over the maps rather than once per gotox. */ -static struct bpf_iarray *jt_from_subprog (struct bpf_verifier_env *env, -int subprog_start,int subprog_end) +static int compute_subprog_jts (struct bpf_verifier_env *env) { -struct bpf_iarray *jt =NULL ; +struct bpf_subprog_info *subprog; +struct bpf_iarray *jt, *jt_cur;struct bpf_map *map; -struct bpf_iarray *jt_cur; +u32 old_cnt;int i;for (i =0 ; i < env->insn_array_map_cnt; i++) {@@ -305,40 +307,47 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env, map = env->insn_array_maps[i]; jt_cur =jt_from_map (map); -if (IS_ERR (jt_cur)) {
kernel/bpf/cfg.c static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env, · line 317
Quoted 10 lines
kernel/bpf/cfg.c +7
-2-kvfree (jt); -return jt_cur; +if (IS_ERR (jt_cur)) +return PTR_ERR (jt_cur); + + subprog =bpf_find_containing_subprog (env, jt_cur->items[0 ]); +if (!subprog) { +kvfree (jt_cur); +continue ; }
Is the block comment above accurate? It states the table is "all maps whose targets land inside that subprogram", but the code attributes a map by its first entry only:
subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
jt_from_map() sorts and de-duplicates, so items[0] is the map's lowest target. A map whose lowest target is inside subprogram S but whose remaining targets reach past (subprog + 1)->start is still merged into S's table, so S->jt can contain targets that do not land inside S.
This case is not filtered here. The range check that rejects such programs is in create_jt():
for (i = 0; i < jt->cnt; i++)
if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end)
... return ERR_PTR(-EINVAL);The old code's comment explained why testing a single element is
sufficient: "This is enough to check one element. The full table is checked to fit inside the subprog later in create_jt()". The comment above the loop in create_jt() said "Check that the every element of the jump table fits within the given subprogram". Both are now deleted.
After the patch the one-element rationale appears nowhere in the file, while the new comment asserts a stronger invariant than the code provides.
Would it be more accurate to say "all maps whose first target lands inside that subprogram" and keep a note that the full table is validated later in create_jt()?
In the follow-up commit e47f26bec05f ("bpf: Reject indirect jumps that leave their subprogram"), the code is changed to match what this comment already claims. The mismatch exists only at this commit.
Quoted 24 lines
kernel/bpf/cfg.c +8
-12-/* -* This is enough to check one element. The full table is -* checked to fit inside the subprog later in create_jt() -*/ -if (jt_cur->items[0 ] >= subprog_start && jt_cur->items[0 ] < subprog_end) { -u32 old_cnt = jt ? jt->cnt :0 ; - jt =bpf_iarray_realloc (jt, old_cnt + jt_cur->cnt); -if (!jt) { -kvfree (jt_cur); -return ERR_PTR (-ENOMEM ); - } -memcpy (jt->items + old_cnt, jt_cur->items, jt_cur->cnt <<2 ); + old_cnt = subprog->jt ? subprog->jt->cnt :0 ; + jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt); +if (!jt) { + subprog->jt =NULL ; +kvfree (jt_cur); +return -ENOMEM ; } +memcpy (jt->items + old_cnt, jt_cur->items, jt_cur->cnt <<2 ); + subprog->jt = jt;kvfree (jt_cur); }
[ ... ]
kernel/bpf/cfg.c int bpf_check_cfg(struct bpf_verifier_env *env) · line 725
Quoted 8 lines
kernel/bpf/cfg.c +1
-0@@ -693,6 +719,7 @@ int bpf_check_cfg(struct bpf_verifier_env *env) env->prog->aux->might_sleep = env->subprog_info[0 ].might_sleep; err_free: +free_subprog_jts (env);kvfree (insn_state);kvfree (insn_stack); env->cfg.insn_state = env->cfg.insn_stack =NULL ;
---
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/34404843294
Daniel Borkmann
maintainerRe: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery
On 9/9/26 11:34 PM, [email protected] wrote:
[...]
Quoted 3 lines
In the follow-up commit
e47f26bec05f("bpf: Reject indirect jumps that leave their subprogram"), the code is changed to match what this comment already claims. The mismatch exists only at this commit.
Ok, then, will leave as-is unless there is a reason to spin a v2..
Re: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery
In reply to Daniel BorkmannQuoted 206 lines · Daniel Borkmann
create_jt()builds the jump table of the subprogram containing a gotox by copying out and sorting everyinsn_arraymap of the program, and it does so once per gotox instruction. The cost is therefore the number of gotox instructions times the number of entries in all of the maps. A program of 4003 instructions with 2000 gotox and one 500k entry map holding two distinct targets has 4000 indirect jump edges, 0.4% of the limit, and takes 351s to be rejected. The map costs next to nothing to prepare, as an unset entry is already a valid target. At the insn limit, with a single 1M entry map, the same shape extrapolates to 43 hours.All gotox instructions of a subprogram share the same jump table, so build the table of every subprogram in a single pass over the maps and hand each gotox a copy of it. Instruction aux data owns its jump table, see
bpf_clear_insn_aux_data(), hence the copy; the copies add up to the number of indirect jump edges, whichvisit_gotox_insn()already bounds.
check_cfg()is then linear in the number of map entries plus the number of indirect jump edges, so what still scales now with the program is whatBPF_MAX_GOTOX_EDGESbounds:gotox map entries edges before after
----------------------------------------------500 250000 1000 36.55s 0.07s 1000 250000 2000 75.65s 0.07s 2000 250000 4000 153.44s 0.07s 2000 125000 4000 69.61s 0.04s 2000 500000 4000 351.27s 0.15sFixes 493d9e0d6083 ("bpf, x86: add support for indirect jumps")Signed-off-by Daniel Borkmann <[email protected]>--- include/linux/bpf_verifier.h | 2 + kernel/bpf/cfg.c | 99 +++++++++++++++++++++++------------- 2 files changed, 65 insertions(+), 36 deletions(-)include/linux/bpf_verifier.h +2
-0@@ -805,6 +805,7 @@ struct bpf_subprog_info {u32 linfo_idx;/* The idx to the main_prog->aux->linfo */ u32 postorder_start;/* The idx to the env->cfg.insn_postorder */ u32 exit_idx;/* Index of one of the BPF_EXIT instructions in this subprogram */ +struct bpf_iarray *jt;/* jump table shared by all gotox of this subprogram */ u16 stack_depth;/* max. stack depth used by this function */ u16 stack_extra;u32 insns_total;@@ -978,6 +979,7 @@ struct bpf_verifier_env {/* current position in the insn_postorder vector */ int cur_postorder;u32 gotox_edges; +bool subprog_jts_ready; } cfg;struct backtrack_state bt;struct bpf_jmp_history_entry *cur_hist_ent;kernel/bpf/cfg.c +63
-36@@ -286,15 +286,17 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map) }/* -* Find and collect all maps which fit in the subprog. Return the result as one -* combined jump table in jt->items (allocated with kvcalloc) +* Collect the jump table of every subprogram that has one, as the combined +* table of all maps whose targets land inside that subprogram. All gotox +* instructions of a subprogram share the same table, so this is done in a +* single pass over the maps rather than once per gotox. */ -static struct bpf_iarray *jt_from_subprog (struct bpf_verifier_env *env, -int subprog_start,int subprog_end) +static int compute_subprog_jts (struct bpf_verifier_env *env) { -struct bpf_iarray *jt =NULL ; +struct bpf_subprog_info *subprog; +struct bpf_iarray *jt, *jt_cur;struct bpf_map *map; -struct bpf_iarray *jt_cur; +u32 old_cnt;int i;for (i =0 ; i < env->insn_array_map_cnt; i++) {@@ -305,40 +307,47 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env, map = env->insn_array_maps[i]; jt_cur =jt_from_map (map); -if (IS_ERR (jt_cur)) { -kvfree (jt); -return jt_cur; +if (IS_ERR (jt_cur)) +return PTR_ERR (jt_cur); + + subprog =bpf_find_containing_subprog (env, jt_cur->items[0 ]); +if (!subprog) { +kvfree (jt_cur); +continue ; } -/* -* This is enough to check one element. The full table is -* checked to fit inside the subprog later in create_jt() -*/ -if (jt_cur->items[0 ] >= subprog_start && jt_cur->items[0 ] < subprog_end) { -u32 old_cnt = jt ? jt->cnt :0 ; - jt =bpf_iarray_realloc (jt, old_cnt + jt_cur->cnt); -if (!jt) { -kvfree (jt_cur); -return ERR_PTR (-ENOMEM ); - } -memcpy (jt->items + old_cnt, jt_cur->items, jt_cur->cnt <<2 ); + old_cnt = subprog->jt ? subprog->jt->cnt :0 ; + jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt); +if (!jt) { + subprog->jt =NULL ; +kvfree (jt_cur); +return -ENOMEM ; } +memcpy (jt->items + old_cnt, jt_cur->items, jt_cur->cnt <<2 ); + subprog->jt = jt;kvfree (jt_cur); } -if (!jt) { -verbose (env,"no jump tables found for subprog starting at %u\n" , subprog_start); -bpf_diag_program_structure ( - env, subprog_start,"missing jump table" , -"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms." , -"No jump table was found for the subprogram that starts at instruction %u." , - subprog_start); -return ERR_PTR (-EINVAL ); +for (i =0 ; i < env->subprog_cnt; i++) { + jt = env->subprog_info[i].jt; +if (jt) + jt->cnt =sort_insn_array_uniq (jt->items, jt->cnt); } - jt->cnt =sort_insn_array_uniq (jt->items, jt->cnt); -return jt; + env->cfg.subprog_jts_ready = true; +return 0 ; +} + +static void free_subprog_jts (struct bpf_verifier_env *env) +{ +int i; + +for (i =0 ; i <ARRAY_SIZE (env->subprog_info); i++) { +kvfree (env->subprog_info[i].jt); + env->subprog_info[i].jt =NULL ; + } + env->cfg.subprog_jts_ready = false; } static struct bpf_iarray *@@ -347,16 +356,33 @@ create_jt(int t, struct bpf_verifier_env *env)struct bpf_subprog_info *subprog;int subprog_start, subprog_end;struct bpf_iarray *jt; -int i; +int i, err; + +if (!env->cfg.subprog_jts_ready) { + err =compute_subprog_jts (env); +if (err) +return ERR_PTR (err); + } subprog =bpf_find_containing_subprog (env, t); subprog_start = subprog->start; subprog_end = (subprog +1 )->start; - jt =jt_from_subprog (env, subprog_start, subprog_end); -if (IS_ERR (jt)) -return jt; -/* Check that the every element of the jump table fits within the given subprogram */ +if (!subprog->jt) { +verbose (env,"no jump tables found for subprog starting at %u\n" , subprog_start); +bpf_diag_program_structure ( + env, subprog_start,"missing jump table" , +"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms." , +"No jump table was found for the subprogram that starts at instruction %u." , + subprog_start); +return ERR_PTR (-EINVAL ); + } + + jt =bpf_iarray_realloc (NULL , subprog->jt->cnt); +if (!jt) +return ERR_PTR (-ENOMEM ); +memcpy (jt->items, subprog->jt->items, subprog->jt->cnt <<2 ); +for (i =0 ; i < jt->cnt; i++) {if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",@@ -693,6 +719,7 @@ int bpf_check_cfg(struct bpf_verifier_env *env) env->prog->aux->might_sleep = env->subprog_info[0 ].might_sleep; err_free: +free_subprog_jts (env);kvfree (insn_state);kvfree (insn_stack); env->cfg.insn_state = env->cfg.insn_stack =NULL ;Signature · 1 line
2.43.0
Eduard Zingerman
maintainerRe: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery
In reply to Daniel BorkmannOn Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:
...
Quoted 25 lines
kernel/bpf/cfg.c +11
-5@@ -347,16 +356,33 @@ create_jt(int t, struct bpf_verifier_env *env)struct bpf_subprog_info *subprog;int subprog_start, subprog_end;struct bpf_iarray *jt; -int i; +int i, err; + +if (!env->cfg.subprog_jts_ready) { + err =compute_subprog_jts (env); +if (err) +return ERR_PTR (err); + } subprog =bpf_find_containing_subprog (env, t); subprog_start = subprog->start; subprog_end = (subprog +1 )->start; - jt =jt_from_subprog (env, subprog_start, subprog_end); -if (IS_ERR (jt)) -return jt; -/* Check that the every element of the jump table fits within the given subprogram */ +if (!subprog->jt) { +verbose (env,"no jump tables found for subprog starting at %u\n" , subprog_start); + bpf_diag_program_structure( + env, subprog_start, "missing jump table",
kernel/bpf/cfg.c create_jt(int t, struct bpf_verifier_env *env) · line 384
Quoted 10 lines
kernel/bpf/cfg.c +10
-0+"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms." , +"No jump table was found for the subprogram that starts at instruction %u." , + subprog_start); +return ERR_PTR (-EINVAL ); + } + + jt =bpf_iarray_realloc (NULL , subprog->jt->cnt); +if (!jt) +return ERR_PTR (-ENOMEM ); +memcpy (jt->items, subprog->jt->items, subprog->jt->cnt <<2 );
What would it take to change the logic such that insn_aux_data no longer owns the memory? (Thus making the copy unnecessary).
Quoted 4 lines
kernel/bpf/cfg.c +1
-0+for (i =0 ; i < jt->cnt; i++) {if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
...
Daniel Borkmann
maintainerRe: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery
Quoted 1 line · Eduard Zingerman
On Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:
[...]
Quoted 7 lines
kernel/bpf/cfg.c create_jt(int t, struct bpf_verifier_env *env) · line 384
Quoted 4 lines
kernel/bpf/cfg.c +4
-0+ jt =bpf_iarray_realloc (NULL , subprog->jt->cnt); +if (!jt) +return ERR_PTR (-ENOMEM ); +memcpy (jt->items, subprog->jt->items, subprog->jt->cnt <<2 );What would it take to change the logic such that
insn_aux_datano longer owns the memory? (Thus making the copy unnecessary).
I was able to remove it from insn_aux_data and only keep it temporarily in the env during verification, it actually simplifies code a bit. Will post a v2 later today.
Daniel Borkmann
maintainerPATCH 4/6 bpf: Reject indirect jumps that leave their subprogram
In reply to Daniel BorkmannThe jump table of a subprog is collected in compute_subprog_jts() from the insn_array maps of the program, and a map is attributed to the subprog that contains its first entry. check_indirect_jump() instead resolves the targets from the map the gotox register actually points to, bounded only by the index range of that register, and never relates them back to the subprog of the gotox.
The two disagree, so bpf_insn_successors() reports a subset of the edges the BPF program can take and a gotox can enter a subprog the CFG never walked. The x86 epilogue there pops the callee saved registers of its own subprog and leaves the ones pushed by the current prologue unrestored, handing rbx, r13, r14 and r15 to the kernel with the values the BPF program left in them.
Close both ends in check_indirect_jump(): confine the resolved targets to the subprog of the gotox, and require each of them to be present in the jump table the CFG walked, that is, in the successor set bpf_insn_successors() reported for this instruction. The latter is the invariant that actually has to hold, the former is kept because it names the problem the BPF program has.
--- include/linux/bpf_verifier.h | 1 + kernel/bpf/cfg.c | 35 +++++----- kernel/bpf/verifier.c | 65 +++++++++++++++++++ .../selftests/bpf/progs/verifier_gotox.c | 2 +- 4 files changed, 85 insertions(+), 18 deletions(-)
include/linux/bpf_verifier.h +1 -0
@@ -826,6 +826,7 @@ struct bpf_subprog_info { bool keep_fastcall_stack: 1; bool changes_pkt_data: 1; bool might_sleep: 1; + bool jt_spans_subprogs: 1; u8 arg_cnt:4;enum priv_stack_mode priv_stack_mode;
kernel/bpf/cfg.c +18 -17
@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)kvfree (jt_cur);continue ; } +if (jt_cur->items[jt_cur->cnt -1 ] >= (subprog +1 )->start) { + subprog->jt_spans_subprogs = true; +kvfree (jt_cur); +continue ; + } old_cnt = subprog->jt ? subprog->jt->cnt :0 ; jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt);
@@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)for (i =0 ; i <ARRAY_SIZE (env->subprog_info); i++) {kvfree (env->subprog_info[i].jt); env->subprog_info[i].jt =NULL ; + env->subprog_info[i].jt_spans_subprogs = false; } env->cfg.subprog_jts_ready = false; }
@@ -354,9 +360,8 @@ static struct bpf_iarray * create_jt(int t, struct bpf_verifier_env *env) { struct bpf_subprog_info *subprog; -int subprog_start, subprog_end;struct bpf_iarray *jt; -int i, err; +int subprog_start, err;if (!env->cfg.subprog_jts_ready) { err =compute_subprog_jts (env);
@@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env) subprog =bpf_find_containing_subprog (env, t); subprog_start = subprog->start; - subprog_end = (subprog +1 )->start; + +if (subprog->jt_spans_subprogs) { +verbose (env,"jump table of subprog starting at %u spans multiple subprogs\n" , + subprog_start); +bpf_diag_program_structure ( + env, subprog_start,"jump table spans subprograms" , +"Keep every entry of a jump table inside one subprogram." , +"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u." , + subprog_start, (subprog +1 )->start); +return ERR_PTR (-EINVAL ); + }if (!subprog->jt) {verbose (env,"no jump tables found for subprog starting at %u\n" , subprog_start);
@@ -383,20 +398,6 @@ create_jt(int t, struct bpf_verifier_env *env)return ERR_PTR (-ENOMEM );memcpy (jt->items, subprog->jt->items, subprog->jt->cnt <<2 ); -for (i =0 ; i < jt->cnt; i++) { -if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { -verbose (env,"jump table for insn %d points outside of the subprog [%u,%u]\n" , - t, subprog_start, subprog_end); -bpf_diag_program_structure ( - env, t,"jump table target out of range" , -"Keep every jump-table target inside the same subprogram." , -"The jump table for instruction %d points outside subprogram range [%u,%u)." , - t, subprog_start, subprog_end); -kvfree (jt); -return ERR_PTR (-EINVAL ); - } - } -return jt; }
kernel/bpf/verifier.c +65 -0
82 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_gotox.c +1 -1
@@ -318,7 +318,7 @@ __used static int test_subprog(void) } SEC("socket") -__failure __msg("jump table for insn 4 points outside of the subprog [0,10]") +__failure __msg("jump table of subprog starting at 0 spans multiple subprogs") __naked void jump_table_outside_subprog(void) { asm volatile (" \
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram
This isn't a bug, but since the cfg.c restructure appears to accept and reject the same programs as before (the new items[jt_cur->cnt - 1] >= (subprog + 1)->start test in compute_subprog_jts()…
Quoted 53 lines
include/linux/bpf_verifier.h +1
-0@@ -826,6 +826,7 @@ struct bpf_subprog_info { bool keep_fastcall_stack: 1; bool changes_pkt_data: 1; bool might_sleep: 1; + bool jt_spans_subprogs: 1; u8 arg_cnt:4;enum priv_stack_mode priv_stack_mode;kernel/bpf/cfg.c +8
-3@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)kvfree (jt_cur);continue ; } +if (jt_cur->items[jt_cur->cnt -1 ] >= (subprog +1 )->start) { + subprog->jt_spans_subprogs = true; +kvfree (jt_cur); +continue ; + } old_cnt = subprog->jt ? subprog->jt->cnt :0 ; jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt);@@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)for (i =0 ; i <ARRAY_SIZE (env->subprog_info); i++) {kvfree (env->subprog_info[i].jt); env->subprog_info[i].jt =NULL ; + env->subprog_info[i].jt_spans_subprogs = false; } env->cfg.subprog_jts_ready = false; }@@ -354,9 +360,8 @@ static struct bpf_iarray * create_jt(int t, struct bpf_verifier_env *env) { struct bpf_subprog_info *subprog; -int subprog_start, subprog_end;struct bpf_iarray *jt; -int i, err; +int subprog_start, err;if (!env->cfg.subprog_jts_ready) { err =compute_subprog_jts (env);@@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env) subprog =bpf_find_containing_subprog (env, t); subprog_start = subprog->start; - subprog_end = (subprog +1 )->start; +
kernel/bpf/cfg.c create_jt(int t, struct bpf_verifier_env *env) · line 384
Quoted 10 lines
kernel/bpf/cfg.c +10
-0+if (subprog->jt_spans_subprogs) { +verbose (env,"jump table of subprog starting at %u spans multiple subprogs\n" , + subprog_start); +bpf_diag_program_structure ( + env, subprog_start,"jump table spans subprograms" , +"Keep every entry of a jump table inside one subprogram." , +"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u." , + subprog_start, (subprog +1 )->start); +return ERR_PTR (-EINVAL ); + }
This isn't a bug, but since the cfg.c restructure appears to accept and reject the same programs as before (the new items[jt_cur->cnt - 1] >= (subprog + 1)->start test in compute_subprog_jts() accepts exactly the same set of maps as the removed per-entry loop in create_jt()), would it be cleaner to keep this Fixes-tagged patch to the check_indirect_jump() hunks and send the jt_spans_subprogs refactor plus message rename as a separate cleanup?
The functional security fix lives entirely in check_indirect_jump(), while the cfg.c changes only modify the diagnostic wording and timing.
Quoted 79 lines
[ ... ]
kernel/bpf/verifier.c +58
-0@@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,return 0 ; } +/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */ +static bool jt_contains (const struct bpf_iarray *jt,u32 target) +{ +int l =0 , r = jt->cnt -1 , m; + +while (l <= r) { + m = l + (r - l) /2 ; +if (jt->items[m] == target) +return true; +if (jt->items[m] < target) + l = m +1 ; +else + r = m -1 ; + } +return false; +} + +static int reject_gotox_out_of_subprog (struct bpf_verifier_env *env,u32 target, +u32 subprog_start,u32 subprog_end) +{ +verbose (env,"indirect jump from insn %d to %u leaves the subprog [%u,%u)\n" , + env->insn_idx, target, subprog_start, subprog_end); +bpf_diag_program_structure ( + env, env->insn_idx,"indirect jump leaves subprogram" , +"Keep every reachable jump-table target inside the subprogram of the indirect jump." , +"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u)." , + env->insn_idx, target, subprog_start, subprog_end); +return -EINVAL ; +} + +static int reject_gotox_without_cfg_edge (struct bpf_verifier_env *env,u32 target) +{ +verbose (env,"indirect jump from insn %d to %u is not in the jump table of the subprog\n" , + env->insn_idx, target); +bpf_diag_program_structure ( + env, env->insn_idx,"indirect jump target without CFG edge" , +"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump." , +"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram." , + env->insn_idx, target); +return -EINVAL ; +} +/* gotox *dst_reg */ static int check_indirect_jump (struct bpf_verifier_env *env,struct bpf_insn *insn) {struct bpf_verifier_state *other_branch; +struct bpf_subprog_info *subprog; +u32 subprog_start, subprog_end;struct bpf_reg_state *dst_reg; +struct bpf_iarray *jt;struct bpf_map *map;u32 min_index, max_index;int err =0 ;@@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *inreturn -EINVAL ; } + subprog =bpf_find_containing_subprog (env, env->insn_idx); +if (verifier_bug_if (!subprog, env,"no subprog contains insn %d" , env->insn_idx)) +return -EFAULT ; + subprog_start = subprog->start; + subprog_end = (subprog +1 )->start; + + jt = env->insn_aux_data[env->insn_idx].jt; +if (verifier_bug_if (!jt, env,"no jump table for insn %d" , env->insn_idx)) +return -EFAULT ; + +for (i =0 ; i < n; i++) { +u32 target = env->gotox_tmp_buf->items[i]; +
kernel/bpf/verifier.c static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in · line 18282
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+if (target < subprog_start || target >= subprog_end) +return reject_gotox_out_of_subprog (env, target, subprog_start, + subprog_end); +if (!jt_contains (jt, target)) +return reject_gotox_without_cfg_edge (env, target); + } +for (i =0 ; i < n -1 ; i++) {mark_indirect_target (env, env->gotox_tmp_buf->items[i]); other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
This isn't a bug, but would it be worth a sentence in the changelog about the cfg.c side (the new jt_spans_subprogs bit and the renamed verifier message), so readers of the log know why verifier_gotox.c's __msg had to change?
The changelog describes only the kernel/bpf/verifier.c half of the diff, but the patch also changes kernel/bpf/cfg.c: it moves the 'jump table entry outside the subprog' detection from a per-entry loop in create_jt() into a per-map maximum test in compute_subprog_jts(), and replaces the old per-entry rejection with an early flag test in create_jt(). That rewrite changes the user-visible verifier message from 'jump table for insn %d points outside of the subprog [%u,%u]' to 'jump table of subprog starting at %u spans multiple subprogs'.
tools/testing/selftests/bpf/progs/verifier_gotox.c __used static int test_subprog(void) · line 324
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_gotox.c +1
-1@@ -318,7 +318,7 @@ __used static int test_subprog(void) } SEC("socket") -__failure __msg("jump table for insn 4 points outside of the subprog [0,10]") +__failure __msg("jump table of subprog starting at 0 spans multiple subprogs") __naked void jump_table_outside_subprog(void) { asm volatile (" \
---
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/34404843294
Re: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram
In reply to Daniel BorkmannQuoted 7 lines · Daniel Borkmann
The jump table of a subprog is collected in
compute_subprog_jts()from theinsn_arraymaps of the program, and a map is attributed to the subprog that contains its first entry.check_indirect_jump()instead resolves the targets from the map the gotox register actually points to, bounded only by the index range of that register, and never relates them back to the subprog of the gotox.
Quoted 5 lines
The two disagree, so
bpf_insn_successors()reports a subset of the edges the BPF program can take and a gotox can enter a subprog the CFG never walked. The x86 epilogue there pops the callee saved registers of its own subprog and leaves the ones pushed by the current prologue unrestored, handing rbx, r13, r14 and r15 to the kernel with the values the BPF program left in them.
Why only x86? Maybe just remove the three lines above?
Quoted 170 lines
Close both ends in
check_indirect_jump(): confine the resolved targets to the subprog of the gotox, and require each of them to be present in the jump table the CFG walked, that is, in the successor setbpf_insn_successors()reported for this instruction. The latter is the invariant that actually has to hold, the former is kept because it names the problem the BPF program has.Fixes 493d9e0d6083 ("bpf, x86: add support for indirect jumps")Reported-by James Burton <[email protected]>Reported-by Nuoqi Gui <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>--- include/linux/bpf_verifier.h | 1 + kernel/bpf/cfg.c | 35 +++++----- kernel/bpf/verifier.c | 65 +++++++++++++++++++ .../selftests/bpf/progs/verifier_gotox.c | 2 +- 4 files changed, 85 insertions(+), 18 deletions(-)include/linux/bpf_verifier.h +1
-0@@ -826,6 +826,7 @@ struct bpf_subprog_info { bool keep_fastcall_stack: 1; bool changes_pkt_data: 1; bool might_sleep: 1; + bool jt_spans_subprogs: 1; u8 arg_cnt:4;enum priv_stack_mode priv_stack_mode;kernel/bpf/cfg.c +18
-17@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)kvfree (jt_cur);continue ; } +if (jt_cur->items[jt_cur->cnt -1 ] >= (subprog +1 )->start) { + subprog->jt_spans_subprogs = true; +kvfree (jt_cur); +continue ; + } old_cnt = subprog->jt ? subprog->jt->cnt :0 ; jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt);@@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)for (i =0 ; i <ARRAY_SIZE (env->subprog_info); i++) {kvfree (env->subprog_info[i].jt); env->subprog_info[i].jt =NULL ; + env->subprog_info[i].jt_spans_subprogs = false; } env->cfg.subprog_jts_ready = false; }@@ -354,9 +360,8 @@ static struct bpf_iarray * create_jt(int t, struct bpf_verifier_env *env) { struct bpf_subprog_info *subprog; -int subprog_start, subprog_end;struct bpf_iarray *jt; -int i, err; +int subprog_start, err;if (!env->cfg.subprog_jts_ready) { err =compute_subprog_jts (env);@@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env) subprog =bpf_find_containing_subprog (env, t); subprog_start = subprog->start; - subprog_end = (subprog +1 )->start; + +if (subprog->jt_spans_subprogs) { +verbose (env,"jump table of subprog starting at %u spans multiple subprogs\n" , + subprog_start); +bpf_diag_program_structure ( + env, subprog_start,"jump table spans subprograms" , +"Keep every entry of a jump table inside one subprogram." , +"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u." , + subprog_start, (subprog +1 )->start); +return ERR_PTR (-EINVAL ); + }if (!subprog->jt) {verbose (env,"no jump tables found for subprog starting at %u\n" , subprog_start);@@ -383,20 +398,6 @@ create_jt(int t, struct bpf_verifier_env *env)return ERR_PTR (-ENOMEM );memcpy (jt->items, subprog->jt->items, subprog->jt->cnt <<2 ); -for (i =0 ; i < jt->cnt; i++) { -if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) { -verbose (env,"jump table for insn %d points outside of the subprog [%u,%u]\n" , - t, subprog_start, subprog_end); -bpf_diag_program_structure ( - env, t,"jump table target out of range" , -"Keep every jump-table target inside the same subprogram." , -"The jump table for instruction %d points outside subprogram range [%u,%u)." , - t, subprog_start, subprog_end); -kvfree (jt); -return ERR_PTR (-EINVAL ); - } - } -return jt; }kernel/bpf/verifier.c +46
-0@@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,return 0 ; } +/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */ +static bool jt_contains (const struct bpf_iarray *jt,u32 target) +{ +int l =0 , r = jt->cnt -1 , m; + +while (l <= r) { + m = l + (r - l) /2 ; +if (jt->items[m] == target) +return true; +if (jt->items[m] < target) + l = m +1 ; +else + r = m -1 ; + } +return false; +} + +static int reject_gotox_out_of_subprog (struct bpf_verifier_env *env,u32 target, +u32 subprog_start,u32 subprog_end) +{ +verbose (env,"indirect jump from insn %d to %u leaves the subprog [%u,%u)\n" , + env->insn_idx, target, subprog_start, subprog_end); +bpf_diag_program_structure ( + env, env->insn_idx,"indirect jump leaves subprogram" , +"Keep every reachable jump-table target inside the subprogram of the indirect jump." , +"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u)." , + env->insn_idx, target, subprog_start, subprog_end); +return -EINVAL ; +} + +static int reject_gotox_without_cfg_edge (struct bpf_verifier_env *env,u32 target) +{ +verbose (env,"indirect jump from insn %d to %u is not in the jump table of the subprog\n" , + env->insn_idx, target); +bpf_diag_program_structure ( + env, env->insn_idx,"indirect jump target without CFG edge" , +"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump." , +"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram." , + env->insn_idx, target); +return -EINVAL ; +} +/* gotox *dst_reg */ static int check_indirect_jump (struct bpf_verifier_env *env,struct bpf_insn *insn) {struct bpf_verifier_state *other_branch; +struct bpf_subprog_info *subprog; +u32 subprog_start, subprog_end;struct bpf_reg_state *dst_reg; +struct bpf_iarray *jt;struct bpf_map *map;u32 min_index, max_index;int err =0 ;@@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *inreturn -EINVAL ; } + subprog =bpf_find_containing_subprog (env, env->insn_idx);
kernel/bpf/verifier.c static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in · line 18270
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (verifier_bug_if (!subprog, env,"no subprog contains insn %d" , env->insn_idx)) +return -EFAULT ; + subprog_start = subprog->start; + subprog_end = (subprog +1 )->start; + + jt = env->insn_aux_data[env->insn_idx].jt; +if (verifier_bug_if (!jt, env,"no jump table for insn %d" , env->insn_idx)) +return -EFAULT ; + +for (i =0 ; i < n; i++) {
The items[] is sorted. Is this enough to just check 0-th and (n-1)-th elements?
kernel/bpf/verifier.c static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in · line 18277
Quoted 7 lines
kernel/bpf/verifier.c +7
-0+u32 target = env->gotox_tmp_buf->items[i]; + +if (target < subprog_start || target >= subprog_end) +return reject_gotox_out_of_subprog (env, target, subprog_start, + subprog_end); +if (!jt_contains (jt, target)) +return reject_gotox_without_cfg_edge (env, target);
Ah, I see, all elements should be checked because this check was added.
Quoted 20 lines
kernel/bpf/verifier.c +2
-0+ } +for (i =0 ; i < n -1 ; i++) {mark_indirect_target (env, env->gotox_tmp_buf->items[i]); other_branch = push_stack(env, env->gotox_tmp_buf->items[i],tools/testing/selftests/bpf/progs/verifier_gotox.c +1
-1@@ -318,7 +318,7 @@ __used static int test_subprog(void) } SEC("socket") -__failure __msg("jump table for insn 4 points outside of the subprog [0,10]") +__failure __msg("jump table of subprog starting at 0 spans multiple subprogs") __naked void jump_table_outside_subprog(void) { asm volatile (" \Signature · 1 line
2.43.0
Eduard Zingerman
maintainerRe: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram
In reply to Daniel BorkmannOn Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:
...
kernel/bpf/cfg.c static int compute_subprog_jts(struct bpf_verifier_env *env) · line 319
Quoted 10 lines
kernel/bpf/cfg.c +2
-0@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)kvfree (jt_cur);continue ; } +if (jt_cur->items[jt_cur->cnt -1 ] >= (subprog +1 )->start) { + subprog->jt_spans_subprogs = true;
This is a single place where the flag is set, why not report an error here and drop the flag altogether?
Quoted 6 lines
kernel/bpf/cfg.c +3
-0+kvfree (jt_cur); +continue ; + } old_cnt = subprog->jt ? subprog->jt->cnt :0 ; jt =bpf_iarray_realloc (subprog->jt, old_cnt + jt_cur->cnt);
...
Daniel Borkmann
maintainerPATCH 5/6 selftests/bpf: Add tests for the indirect jump edge limit
In reply to Daniel BorkmannBuild programs whose gotox instructions are their own jump table targets, which makes the edge count quadratic.
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t bpf_insn_array [...]
#24/10 bpf_insn_array/too-many-gotox-edges:OK #24/11 bpf_insn_array/gotox-edges-at-limit:OK #24/12 bpf_insn_array/gotox-edges-across-subprogs:OK #24 bpf_insn_array:OK
Summary: 1/12 PASSED, 0 SKIPPED, 0/0 FAILED
--- .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++ 1 file changed, 266 insertions(+)
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +266 -0
@@ -453,6 +453,263 @@ static void check_bpf_no_lookup(void)close (map_fd); } +#define GOTOX_CNT_AT_LIMIT 1000 +#define GOTOX_LOG_SZ (256 * 1024) + +static const char gotox_limit_msg[] = +"number of indirect jump edges in the program exceeds" ; + +static int gotox_jt_create (__u32 first_gotox,__u32 gotox_cnt) +{ +/* the run of gotox itself, plus the exit block right after it */ +const __u32 jt_cnt = gotox_cnt +1 ; +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , jt_cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < jt_cnt; i++) { + val.orig_off = first_gotox + i; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log) +{ +LIBBPF_OPTS (bpf_prog_load_opts, opts); +int prog_fd; + + log[0 ] =0 ; + opts.fd_array = fd_array; + opts.fd_array_cnt = fd_array_cnt; + opts.log_buf = log; + opts.log_size =GOTOX_LOG_SZ ; + opts.log_level =1 ; + + prog_fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, insn_cnt, &opts); +if (prog_fd >=0 ) { +close (prog_fd); +return 0 ; + } +return prog_fd; +} + +/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */ +static void gotox_run_fill (struct bpf_insn *insns,__u32 gotox_cnt) +{ +__u32 i; + + insns[0 ] =BPF_MOV64_IMM (BPF_REG_1 ,0 ); +for (i =1 ; i <= gotox_cnt; i++) + insns[i] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); +} + +static void check_gotox_limit_hit (const char *log,int err) +{ +ASSERT_EQ (err, -E2BIG ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log, gotox_limit_msg,"verifier log" ); +} + +static bool try_load_gotox_prog (__u32 gotox_cnt,char *log,int *err) +{ +const __u32 insn_cnt = gotox_cnt +3 ; +struct bpf_insn *insns; +bool attempted = false; +int map_fd; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) +return false; + +gotox_run_fill (insns, gotox_cnt); + insns[gotox_cnt +1 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[gotox_cnt +2 ] =BPF_EXIT_INSN (); + + map_fd =gotox_jt_create (1 , gotox_cnt); +if (map_fd <0 ) + goto free_insns; + + *err =gotox_prog_load (insns, insn_cnt, &map_fd,1 , log); +close (map_fd); + attempted = true; +free_insns: +free (insns); +return attempted; +} + +/* +* The extra exit target in the jump table makes for gotox_cnt * (gotox_cnt +* + 1) edges, hence the program is over the limit by gotox_cnt edges. +*/ +static void check_too_many_gotox_edges (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT ; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +if (try_load_gotox_prog (gotox_cnt, log, &err)) +check_gotox_limit_hit (log, err); + +free (log); +} + +/* +* A chain of blocks, where block k loads jt[k] and jumps to it. The jump +* table holds the starts of the blocks that follow plus the exit block, +* which is gotox_cnt targets for gotox_cnt gotox, so the program sits +* exactly at the limit and must still load. +*/ +#define GOTOX_BLOCK_SZ 4 + +static void gotox_chain_fill (struct bpf_insn *insns,__u32 gotox_cnt) +{ +struct bpf_insn *at; +__u32 k; + +for (k =0 ; k < gotox_cnt; k++) { + at = insns + k *GOTOX_BLOCK_SZ ; + +/* r1 = &jt[0], by index 0 into fd_array */ + at[0 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + at[1 ] = (struct bpf_insn ) { .imm =0 }; + at[2 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 , k *8 ); + at[3 ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + } + + insns[gotox_cnt *GOTOX_BLOCK_SZ ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[gotox_cnt *GOTOX_BLOCK_SZ +1 ] =BPF_EXIT_INSN (); +} + +static int gotox_chain_jt_create (__u32 gotox_cnt) +{ +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , gotox_cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < gotox_cnt; i++) { + val.orig_off = (i +1 ) *GOTOX_BLOCK_SZ ; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +static void check_gotox_edges_at_limit (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT ; +const __u32 insn_cnt = gotox_cnt *GOTOX_BLOCK_SZ +2 ; +struct bpf_insn *insns; +char *log; +int map_fd, err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) + goto free_log; + +gotox_chain_fill (insns, gotox_cnt); + + map_fd =gotox_chain_jt_create (gotox_cnt); +if (map_fd <0 ) + goto free_insns; + + err =gotox_prog_load (insns, insn_cnt, &map_fd,1 , log); +close (map_fd); + +if (!ASSERT_OK (err,"program at the edge limit should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +free_insns: +free (insns); +free_log: +free (log); +} + +static void check_gotox_edges_across_subprogs (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT *3 /4 ; +const __u32 sub_start = gotox_cnt +3 ; +const __u32 insn_cnt =2 * (gotox_cnt +3 ); +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_insn *insns; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) + goto free_log; + +gotox_run_fill (insns, gotox_cnt); + insns[gotox_cnt +1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 , +BPF_PSEUDO_CALL ,0 , + sub_start - (gotox_cnt +1 ) -1 ); + insns[gotox_cnt +2 ] =BPF_EXIT_INSN (); + +gotox_run_fill (insns + sub_start, gotox_cnt); + insns[sub_start + gotox_cnt +1 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[sub_start + gotox_cnt +2 ] =BPF_EXIT_INSN (); + + map_fd[0 ] =gotox_jt_create (1 , gotox_cnt); +if (map_fd[0 ] <0 ) + goto free_insns; + map_fd[1 ] =gotox_jt_create (sub_start +1 , gotox_cnt); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns, insn_cnt, map_fd,2 , log); +check_gotox_limit_hit (log, err); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_insns: +free (insns); +free_log: +free (log); +} +static void check_bpf_side (void ) {check_bpf_no_lookup ();
@@ -490,6 +747,15 @@ static void __test_bpf_insn_array(void)if (test__start_subtest ("bpf-side-ops" ))check_bpf_side (); + +if (test__start_subtest ("too-many-gotox-edges" )) +check_too_many_gotox_edges (); + +if (test__start_subtest ("gotox-edges-at-limit" )) +check_gotox_edges_at_limit (); + +if (test__start_subtest ("gotox-edges-across-subprogs" )) + check_gotox_edges_across_subprogs(); }#else static void __test_bpf_insn_array (void )
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit
The one-sentence body describes the construction used by only two of the three subtests this patch registers, and it is wrong for the third.
Quoted 4 lines
selftests/bpf: Add tests for the indirect jump edge limit
Build programs whose gotox instructions are their own jump table targets, which makes the edge count quadratic.
The one-sentence body describes the construction used by only two of the three subtests this patch registers, and it is wrong for the third.
'gotox instructions are their own jump table targets' is accurate for check_too_many_gotox_edges() and check_gotox_edges_across_subprogs(), which both build their tables with gotox_jt_create(first_gotox, gotox_cnt) over 'first_gotox + i' while gotox_run_fill() places the gotox run at exactly those offsets:
insns[0] = BPF_MOV64_IMM(BPF_REG_1, 0);
for (i = 1; i <= gotox_cnt; i++)
insns[i] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);It is not accurate for check_gotox_edges_at_limit(), which uses the unrelated chained-block construction in gotox_chain_fill() and gotox_chain_jt_create(). There, block k occupies insns[k * GOTOX_BLOCK_SZ .. k * GOTOX_BLOCK_SZ + 3] with the gotox at k * 4 + 3, while the jump-table entries are
val.orig_off = (i + 1) * GOTOX_BLOCK_SZ;
i.e. 4, 8, ... 4000 - the BPF_LD_IMM64 at the head of each block. The target set {4, 8, ...} and the gotox set {3, 7, ...} are disjoint, so no gotox is its own jump-table target in that test.
The at-limit test also carries the load-bearing detail that the changelog omits entirely: it sits at exactly BPF_MAX_GOTOX_EDGES (1000 gotox x 1000 entries == 1000000) and must still load, which is what pins the 'greater than' rather than 'greater or equal' comparison in visit_gotox_insn(). Likewise the third subtest's point - that env->cfg.gotox_edges accumulates across subprograms rather than per-subprogram - is not mentioned.
Could the changelog be generalized (e.g. 'build programs with quadratic gotox edge counts') or expanded with a clause for the chained at-limit case and the cross-subprog accumulation, so it matches what the three subtests actually construct?
---
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/34404843294
Re: [PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit
In reply to Daniel BorkmannQuoted 303 lines · Daniel Borkmann
Build programs whose gotox instructions are their own jump table targets, which makes the edge count quadratic.
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t
bpf_insn_array[...]#24/10 bpf_insn_array/too-many-gotox-edges:OK #24/11 bpf_insn_array/gotox-edges-at-limit:OK #24/12 bpf_insn_array/gotox-edges-across-subprogs:OK #24 bpf_insn_array:OKSummary: 1/12 PASSED, 0 SKIPPED, 0/0 FAILED
Signed-off-by Daniel Borkmann <[email protected]>--- .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++ 1 file changed, 266 insertions(+)tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +266
-0@@ -453,6 +453,263 @@ static void check_bpf_no_lookup(void)close (map_fd); } +#define GOTOX_CNT_AT_LIMIT 1000 +#define GOTOX_LOG_SZ (256 * 1024) + +static const char gotox_limit_msg[] = +"number of indirect jump edges in the program exceeds" ; + +static int gotox_jt_create (__u32 first_gotox,__u32 gotox_cnt) +{ +/* the run of gotox itself, plus the exit block right after it */ +const __u32 jt_cnt = gotox_cnt +1 ; +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , jt_cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < jt_cnt; i++) { + val.orig_off = first_gotox + i; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log) +{ +LIBBPF_OPTS (bpf_prog_load_opts, opts); +int prog_fd; + + log[0 ] =0 ; + opts.fd_array = fd_array; + opts.fd_array_cnt = fd_array_cnt; + opts.log_buf = log; + opts.log_size =GOTOX_LOG_SZ ; + opts.log_level =1 ; + + prog_fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, insn_cnt, &opts); +if (prog_fd >=0 ) { +close (prog_fd); +return 0 ; + } +return prog_fd; +} + +/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */ +static void gotox_run_fill (struct bpf_insn *insns,__u32 gotox_cnt) +{ +__u32 i; + + insns[0 ] =BPF_MOV64_IMM (BPF_REG_1 ,0 ); +for (i =1 ; i <= gotox_cnt; i++) + insns[i] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); +} + +static void check_gotox_limit_hit (const char *log,int err) +{ +ASSERT_EQ (err, -E2BIG ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log, gotox_limit_msg,"verifier log" ); +} + +static bool try_load_gotox_prog (__u32 gotox_cnt,char *log,int *err) +{ +const __u32 insn_cnt = gotox_cnt +3 ; +struct bpf_insn *insns; +bool attempted = false; +int map_fd; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) +return false; + +gotox_run_fill (insns, gotox_cnt); + insns[gotox_cnt +1 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[gotox_cnt +2 ] =BPF_EXIT_INSN (); + + map_fd =gotox_jt_create (1 , gotox_cnt); +if (map_fd <0 ) + goto free_insns; + + *err =gotox_prog_load (insns, insn_cnt, &map_fd,1 , log); +close (map_fd); + attempted = true; +free_insns: +free (insns); +return attempted; +} + +/* +* The extra exit target in the jump table makes for gotox_cnt * (gotox_cnt +* + 1) edges, hence the program is over the limit by gotox_cnt edges. +*/ +static void check_too_many_gotox_edges (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT ; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +if (try_load_gotox_prog (gotox_cnt, log, &err)) +check_gotox_limit_hit (log, err); + +free (log); +} + +/* +* A chain of blocks, where block k loads jt[k] and jumps to it. The jump +* table holds the starts of the blocks that follow plus the exit block, +* which is gotox_cnt targets for gotox_cnt gotox, so the program sits +* exactly at the limit and must still load. +*/ +#define GOTOX_BLOCK_SZ 4 + +static void gotox_chain_fill (struct bpf_insn *insns,__u32 gotox_cnt) +{ +struct bpf_insn *at; +__u32 k; + +for (k =0 ; k < gotox_cnt; k++) { + at = insns + k *GOTOX_BLOCK_SZ ; + +/* r1 = &jt[0], by index 0 into fd_array */ + at[0 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + at[1 ] = (struct bpf_insn ) { .imm =0 }; + at[2 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 , k *8 ); + at[3 ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + } + + insns[gotox_cnt *GOTOX_BLOCK_SZ ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[gotox_cnt *GOTOX_BLOCK_SZ +1 ] =BPF_EXIT_INSN (); +} + +static int gotox_chain_jt_create (__u32 gotox_cnt) +{ +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , gotox_cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < gotox_cnt; i++) { + val.orig_off = (i +1 ) *GOTOX_BLOCK_SZ ; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +static void check_gotox_edges_at_limit (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT ; +const __u32 insn_cnt = gotox_cnt *GOTOX_BLOCK_SZ +2 ; +struct bpf_insn *insns; +char *log; +int map_fd, err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) + goto free_log; + +gotox_chain_fill (insns, gotox_cnt); + + map_fd =gotox_chain_jt_create (gotox_cnt); +if (map_fd <0 ) + goto free_insns; + + err =gotox_prog_load (insns, insn_cnt, &map_fd,1 , log); +close (map_fd); + +if (!ASSERT_OK (err,"program at the edge limit should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +free_insns: +free (insns); +free_log: +free (log); +} + +static void check_gotox_edges_across_subprogs (void ) +{ +const __u32 gotox_cnt =GOTOX_CNT_AT_LIMIT *3 /4 ; +const __u32 sub_start = gotox_cnt +3 ; +const __u32 insn_cnt =2 * (gotox_cnt +3 ); +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_insn *insns; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + + insns =calloc (insn_cnt,sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"calloc insns" )) + goto free_log; + +gotox_run_fill (insns, gotox_cnt); + insns[gotox_cnt +1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 , +BPF_PSEUDO_CALL ,0 , + sub_start - (gotox_cnt +1 ) -1 ); + insns[gotox_cnt +2 ] =BPF_EXIT_INSN (); + +gotox_run_fill (insns + sub_start, gotox_cnt); + insns[sub_start + gotox_cnt +1 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[sub_start + gotox_cnt +2 ] =BPF_EXIT_INSN (); + + map_fd[0 ] =gotox_jt_create (1 , gotox_cnt); +if (map_fd[0 ] <0 ) + goto free_insns; + map_fd[1 ] =gotox_jt_create (sub_start +1 , gotox_cnt); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns, insn_cnt, map_fd,2 , log); +check_gotox_limit_hit (log, err); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_insns: +free (insns); +free_log: +free (log); +} +static void check_bpf_side (void ) {check_bpf_no_lookup ();@@ -490,6 +747,15 @@ static void __test_bpf_insn_array(void)if (test__start_subtest ("bpf-side-ops" ))check_bpf_side (); + +if (test__start_subtest ("too-many-gotox-edges" )) +check_too_many_gotox_edges (); + +if (test__start_subtest ("gotox-edges-at-limit" )) +check_gotox_edges_at_limit (); + +if (test__start_subtest ("gotox-edges-across-subprogs" )) + check_gotox_edges_across_subprogs(); }#else static void __test_bpf_insn_array (void )Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH 6/6 selftests/bpf: Add tests for indirect jumps across subprograms
In reply to Daniel BorkmannAdd various gotox corner case tests to improve corner case coverage.
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
./test_progs -t bpf_insn_array,verifier_gotox,signed_loader
[...]
#24/13 bpf_insn_array/gotox-tracker-map:OK #24/14 bpf_insn_array/gotox-jt-spans-subprogs:OK #24/15 bpf_insn_array/gotox-jt-spans-with-own-table:OK #24/16 bpf_insn_array/gotox-target-without-cfg-edge:OK #24/17 bpf_insn_array/gotox-target-other-subprog:OK #24/18 bpf_insn_array/gotox-jt-per-subprog:OK #24/19 bpf_insn_array/gotox-span-unreached-entry:OK #24/20 bpf_insn_array/gotox-target-subprog-from-main:OK #24/21 bpf_insn_array/gotox-index-slice-other-subprog:OK #24/22 bpf_insn_array/gotox-target-other-global-subprog:OK #24/23 bpf_insn_array/gotox-callback-leaves-subprog:OK #24 bpf_insn_array:OK
[...]
#616 verifier_gotox:OK
Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED
--- .../selftests/bpf/prog_tests/bpf_insn_array.c | 715 +++++++++++++++++- 1 file changed, 713 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +713 -2
@@ -1,6 +1,7 @@// SPDX-License-Identifier: GPL-2.0 #include <bpf/bpf.h> +#include <bpf/btf.h> #include <test_progs.h> #if defined(__x86_64__) || defined(__powerpc__) || defined(__aarch64__)
@@ -487,8 +488,9 @@ static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)return -1 ; } -static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, -int *fd_array,__u32 fd_array_cnt,char *log) +static int gotox_prog_load_funcs (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log, +int btf_fd,struct bpf_func_info *fi,__u32 fi_cnt) {LIBBPF_OPTS (bpf_prog_load_opts, opts);int prog_fd;
@@ -499,6 +501,12 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt, opts.log_buf = log; opts.log_size =GOTOX_LOG_SZ ; opts.log_level =1 ; +if (fi_cnt) { + opts.prog_btf_fd = btf_fd; + opts.func_info = fi; + opts.func_info_cnt = fi_cnt; + opts.func_info_rec_size =sizeof (*fi); + } prog_fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, insn_cnt, &opts);if (prog_fd >=0 ) {
@@ -508,6 +516,13 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,return prog_fd; } +static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log) +{ +return gotox_prog_load_funcs (insns, insn_cnt, fd_array, fd_array_cnt, log, +-1 ,NULL ,0 ); +} +/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */ static void gotox_run_fill (struct bpf_insn *insns,__u32 gotox_cnt) {
@@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)free (log); } +static int gotox_jt_create_offs (const __u32 *offs,__u32 cnt) +{ +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < cnt; i++) { + val.orig_off = offs[i]; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +#define GOTOX_SUB_START 4 +#define GOTOX_MAIN_TGT 2 +#define GOTOX_SUB_TGT 8 +#define GOTOX_TWO_INSN_CNT 10 + +static void gotox_two_subprogs_fill (struct bpf_insn *insns,__u32 jt_idx,__u32 jt_off) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_SUB_START -1 -1 ); + insns[GOTOX_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_EXIT_INSN (); + +/* r1 = &jt[0], by index 'jt_idx' into fd_array */ + insns[GOTOX_SUB_START ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm = jt_idx, + }; + insns[GOTOX_SUB_START +1 ] = (struct bpf_insn ) { .imm =0 }; + insns[6 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 , jt_off *8 ); + insns[7 ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_SUB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[9 ] =BPF_EXIT_INSN (); +} + +/* +* An insn_array map is not necessarily a jump table: one that tracks +* instruction offsets covers the whole program and is of no subprog. Such a +* map must not keep a program with a gotox elsewhere from loading. +*/ +static void check_gotox_tracker_map (void ) +{ +const __u32 jt_track[] = {0 ,GOTOX_MAIN_TGT ,GOTOX_SUB_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,1 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_track,ARRAY_SIZE (jt_track)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +if (!ASSERT_OK (err,"program with a tracking map should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static void check_gotox_target_other_subprog (void ) +{ +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 7 to 2 leaves the subprog [4,10)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static void check_gotox_jt_per_subprog (void ) +{ +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,1 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err,0 ,"bpf(BPF_PROG_LOAD)" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The spanning map is of no subprog and is dropped, and the entry the gotox +* register can reach is in the subprog of the gotox and in the jump table the +* CFG walked, so nothing unsafe is left and the program loads. +*/ +static void check_gotox_span_unreached_entry (void ) +{ +const __u32 jt_span[] = {GOTOX_MAIN_TGT ,GOTOX_SUB_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,1 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +if (!ASSERT_OK (err,"program with an unreachable spanning entry should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_FWD_GOTOX 11 +#define GOTOX_FWD_OWN_TGT 12 +#define GOTOX_FWD_SUB_START 14 +#define GOTOX_FWD_INSN_CNT 16 + +static void gotox_from_main_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_FWD_SUB_START -1 -1 ); + insns[2 ] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_6 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[3 ] =BPF_JMP_IMM (BPF_JEQ ,BPF_REG_2 ,0 ,4 ); + +/* r1 = &jt_leaves[0], by index 1 into fd_array */ + insns[4 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =1 , + }; + insns[5 ] = (struct bpf_insn ) { .imm =0 }; + insns[6 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + insns[7 ] =BPF_JMP_A (3 ); + +/* r1 = &jt_own[0], by index 0 into fd_array */ + insns[8 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[9 ] = (struct bpf_insn ) { .imm =0 }; + insns[10 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + + insns[GOTOX_FWD_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_FWD_OWN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[13 ] =BPF_EXIT_INSN (); + insns[GOTOX_FWD_SUB_START ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[15 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_target_subprog_from_main (void ) +{ +const __u32 jt_own[] = {GOTOX_FWD_OWN_TGT }; +const __u32 jt_leaves[] = {GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_own,ARRAY_SIZE (jt_own)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_leaves,ARRAY_SIZE (jt_leaves)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 11 to 14 leaves the subprog [0,14)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The only map of the subprog holding the gotox reaches past that subprog, so +* the subprog is left without a jump table at all. +*/ +static void check_gotox_jt_spans_subprogs (void ) +{ +const __u32 jt_span[] = {GOTOX_FWD_OWN_TGT ,GOTOX_FWD_SUB_START }; +const __u32 jt_leaves[] = {GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_leaves,ARRAY_SIZE (jt_leaves)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"jump table of subprog starting at 0 spans multiple subprogs" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The subprog holding the gotox has a well formed jump table of its own and +* also collects a map that reaches past its end. The spanning map is still +* rejected, even though the subprog is not left without a table. +*/ +static void check_gotox_jt_spans_with_own_table (void ) +{ +const __u32 jt_own[] = {GOTOX_FWD_OWN_TGT }; +const __u32 jt_span[] = {GOTOX_FWD_OWN_TGT ,GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_own,ARRAY_SIZE (jt_own)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"jump table of subprog starting at 0 spans multiple subprogs" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_EDGE_MAIN_TGT 2 +#define GOTOX_EDGE_SUB_START 4 +#define GOTOX_EDGE_GOTOX 9 +#define GOTOX_EDGE_BR_TGT 10 +#define GOTOX_EDGE_JT_TGT 11 +#define GOTOX_EDGE_INSN_CNT 12 + +static void gotox_no_edge_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_EDGE_SUB_START -1 -1 ); + insns[GOTOX_EDGE_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_EXIT_INSN (); + + insns[GOTOX_EDGE_SUB_START ] = +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[5 ] =BPF_JMP_IMM (BPF_JNE ,BPF_REG_2 ,0 ,4 ); + +/* r1 = &jt_span[0], by index 0 into fd_array */ + insns[6 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[7 ] = (struct bpf_insn ) { .imm =0 }; + insns[8 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,8 ); + + insns[GOTOX_EDGE_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_EDGE_BR_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[GOTOX_EDGE_JT_TGT ] =BPF_EXIT_INSN (); +} + +/* +* The gotox resolves a target inside its own subprog, but out of a map that +* spans subprogs and is therefore of no subprog. The CFG never walked that +* edge, so the jump has to be rejected even though it stays in the subprog. +*/ +static void check_gotox_target_without_cfg_edge (void ) +{ +const __u32 jt_span[] = {GOTOX_EDGE_MAIN_TGT ,GOTOX_EDGE_BR_TGT }; +const __u32 jt_sub[] = {GOTOX_EDGE_JT_TGT }; +struct bpf_insn insns[GOTOX_EDGE_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_no_edge_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log, +"indirect jump from insn 9 to 10 is not in the jump table of the subprog" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_SLICE_SUB_START 6 +#define GOTOX_SLICE_GOTOX 14 +#define GOTOX_SLICE_SUB_TGT 15 +#define GOTOX_SLICE_INSN_CNT 17 + +static void gotox_slice_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_SLICE_SUB_START -1 -1 ); + insns[2 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[4 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[5 ] =BPF_EXIT_INSN (); + + insns[GOTOX_SLICE_SUB_START ] = +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[7 ] =BPF_ALU64_IMM (BPF_AND ,BPF_REG_2 ,1 ); + insns[8 ] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ); + insns[9 ] =BPF_ALU64_IMM (BPF_LSH ,BPF_REG_2 ,3 ); + +/* r1 = &jt_main[0], by index 0 into fd_array */ + insns[10 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[11 ] = (struct bpf_insn ) { .imm =0 }; + insns[12 ] =BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ); + insns[13 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + + insns[GOTOX_SLICE_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_SLICE_SUB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[16 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_index_slice_other_subprog (void ) +{ +const __u32 jt_main[] = {2 ,3 ,4 }; +const __u32 jt_sub[] = {GOTOX_SLICE_SUB_TGT }; +struct bpf_insn insns[GOTOX_SLICE_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_slice_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 14 to 3 leaves the subprog [6,17)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static int gotox_btf_create (const __u32 *starts,const __u8 *linkage,__u32 cnt, +struct bpf_func_info *fi,struct btf **pbtf) +{ +int int_id, proto_id, id; +struct btf *btf; +char name[24 ]; +__u32 i; + + btf =btf__new_empty (); +if (!ASSERT_OK_PTR (btf,"btf__new_empty" )) +return -1 ; + + int_id =btf__add_int (btf,"int" ,4 ,BTF_INT_SIGNED ); +if (!ASSERT_GT (int_id,0 ,"btf__add_int" )) + goto err; + + proto_id =btf__add_func_proto (btf, int_id); +if (!ASSERT_GT (proto_id,0 ,"btf__add_func_proto" )) + goto err; + +for (i =0 ; i < cnt; i++) { +snprintf (name,sizeof (name),"gotox_f%u" , i); + id =btf__add_func (btf, name, linkage[i], proto_id); +if (!ASSERT_GT (id,0 ,"btf__add_func" )) + goto err; + fi[i].insn_off = starts[i]; + fi[i].type_id = id; + } + +if (!ASSERT_OK (btf__load_into_kernel (btf),"btf__load_into_kernel" )) + goto err; + + *pbtf = btf; +return btf__fd (btf); +err: +btf__free (btf); +return -1 ; +} + +static void check_gotox_target_other_global_subprog (void ) +{ +const __u32 starts[] = {0 ,GOTOX_SUB_START }; +const __u8 linkage[] = {BTF_FUNC_GLOBAL ,BTF_FUNC_GLOBAL }; +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_func_info fi[2 ]; +struct btf *btf =NULL ; +int btf_fd; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,0 ); + + btf_fd =gotox_btf_create (starts, linkage,ARRAY_SIZE (starts), fi, &btf); +if (btf_fd <0 ) + goto free_log; + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_btf; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load_funcs (insns,ARRAY_SIZE (insns), map_fd,2 , log, + btf_fd, fi,ARRAY_SIZE (fi)); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 7 to 2 leaves the subprog [4,10)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_btf: +btf__free (btf); +free_log: +free (log); +} + +#define GOTOX_CB_MAIN_TGT 6 +#define GOTOX_CB_START 8 +#define GOTOX_CB_GOTOX 11 +#define GOTOX_CB_TGT 12 +#define GOTOX_CB_INSN_CNT 14 + +static void gotox_callback_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_1 ,1 ); +/* r2 = &callback */ + insns[1 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_2 , + .src_reg =BPF_PSEUDO_FUNC , + .imm =GOTOX_CB_START -1 -1 , + }; + insns[2 ] = (struct bpf_insn ) { .imm =0 }; + insns[3 ] =BPF_MOV64_IMM (BPF_REG_3 ,0 ); + insns[4 ] =BPF_MOV64_IMM (BPF_REG_4 ,0 ); + insns[5 ] =BPF_EMIT_CALL (BPF_FUNC_loop); + insns[GOTOX_CB_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[7 ] =BPF_EXIT_INSN (); + +/* r1 = &jt_main[0], by index 0 into fd_array */ + insns[GOTOX_CB_START ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[9 ] = (struct bpf_insn ) { .imm =0 }; + insns[10 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + insns[GOTOX_CB_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_CB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[13 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_callback_leaves_subprog (void ) +{ +const __u32 starts[] = {0 ,GOTOX_CB_START }; +const __u8 linkage[] = {BTF_FUNC_GLOBAL ,BTF_FUNC_STATIC }; +const __u32 jt_main[] = {GOTOX_CB_MAIN_TGT }; +const __u32 jt_cb[] = {GOTOX_CB_TGT }; +struct bpf_insn insns[GOTOX_CB_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_func_info fi[2 ]; +struct btf *btf =NULL ; +int btf_fd; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_callback_fill (insns); + + btf_fd =gotox_btf_create (starts, linkage,ARRAY_SIZE (starts), fi, &btf); +if (btf_fd <0 ) + goto free_log; + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_btf; + map_fd[1 ] =gotox_jt_create_offs (jt_cb,ARRAY_SIZE (jt_cb)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load_funcs (insns,ARRAY_SIZE (insns), map_fd,2 , log, + btf_fd, fi,ARRAY_SIZE (fi)); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 11 to 6 leaves the subprog [8,14)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_btf: +btf__free (btf); +free_log: +free (log); +} +static void check_bpf_side (void ) {check_bpf_no_lookup ();
@@ -756,6 +1434,39 @@ static void __test_bpf_insn_array(void)if (test__start_subtest ("gotox-edges-across-subprogs" ))check_gotox_edges_across_subprogs (); + +if (test__start_subtest ("gotox-tracker-map" )) +check_gotox_tracker_map (); + +if (test__start_subtest ("gotox-jt-spans-subprogs" )) +check_gotox_jt_spans_subprogs (); + +if (test__start_subtest ("gotox-jt-spans-with-own-table" )) +check_gotox_jt_spans_with_own_table (); + +if (test__start_subtest ("gotox-target-without-cfg-edge" )) +check_gotox_target_without_cfg_edge (); + +if (test__start_subtest ("gotox-target-other-subprog" )) +check_gotox_target_other_subprog (); + +if (test__start_subtest ("gotox-jt-per-subprog" )) +check_gotox_jt_per_subprog (); + +if (test__start_subtest ("gotox-span-unreached-entry" )) +check_gotox_span_unreached_entry (); + +if (test__start_subtest ("gotox-target-subprog-from-main" )) +check_gotox_target_subprog_from_main (); + +if (test__start_subtest ("gotox-index-slice-other-subprog" )) +check_gotox_index_slice_other_subprog (); + +if (test__start_subtest ("gotox-target-other-global-subprog" )) +check_gotox_target_other_global_subprog (); + +if (test__start_subtest ("gotox-callback-leaves-subprog" )) + check_gotox_callback_leaves_subprog(); }#else static void __test_bpf_insn_array (void )
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf 6/6] selftests/bpf: Add tests for indirect jumps across subprograms
This isn't a bug, but could the changelog say a sentence or two about which rejection paths these 11 subtests pin down? The current form just repeats itself ("various gotox corner case tests to…
Quoted 19 lines
selftests/bpf: Add tests for indirect jumps across subprograms
Add various gotox corner case tests to improve corner case coverage.
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
./test_progs -t bpf_insn_array,verifier_gotox,signed_loader
[...]#24/13 bpf_insn_array/gotox-tracker-map:OK #24/14 bpf_insn_array/gotox-jt-spans-subprogs:OK #24/15 bpf_insn_array/gotox-jt-spans-with-own-table:OK #24/16 bpf_insn_array/gotox-target-without-cfg-edge:OK #24/17 bpf_insn_array/gotox-target-other-subprog:OK #24/18 bpf_insn_array/gotox-jt-per-subprog:OK #24/19 bpf_insn_array/gotox-span-unreached-entry:OK #24/20 bpf_insn_array/gotox-target-subprog-from-main:OK #24/21 bpf_insn_array/gotox-index-slice-other-subprog:OK #24/22 bpf_insn_array/gotox-target-other-global-subprog:OK #24/23 bpf_insn_array/gotox-callback-leaves-subprog:OK #24 bpf_insn_array:OK
Quoted 3 lines
[...]
#616 verifier_gotox:OK
Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED
This isn't a bug, but could the changelog say a sentence or two about which rejection paths these 11 subtests pin down? The current form just repeats itself ("various gotox corner case tests to improve corner case coverage") and then pastes the test_progs output. The names of the subtests are listed, but the message doesn't explain which verifier behaviour each group exercises - things like targets leaving the subprog, targets missing from the CFG jump table, one jump table shared across subprogs, or callback cases. The sibling patch in this series ("selftests/bpf: Add tests for the indirect jump edge limit") does state the shape of the program it builds and why, so the shorter form here stands out within the series.
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +0
-0
[ ... ]
Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +2
-0@@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)free (log); } +static int gotox_jt_create_offs (const __u32 *offs,__u32 cnt) +{
[ ... ]
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c static void check_gotox_edges_across_subprogs(void) · line 786
Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +6
-0+/* +* An insn_array map is not necessarily a jump table: one that tracks +* instruction offsets covers the whole program and is of no subprog. Such a +* map must not keep a program with a gotox elsewhere from loading. +*/ +static void check_gotox_tracker_map (void )
^^^^
This isn't a bug, but would it be worth rewording "is of no subprog" here? Looking at compute_subprog_jts() in kernel/bpf/cfg.c, it does attribute the map to the subprog containing its first entry and sets jt_spans_subprogs there:
subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
if (!subprog) { ...continue; }
if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
subprog->jt_spans_subprogs = true;
...continue;
}Since valid_offsets() already guarantees every entry is less than prog->len, the !subprog branch is effectively unreachable. A spanning map doesn't become any subprog's jump table, but it does mark the subprog holding its first entry. In the three tests using this pattern (check_gotox_tracker_map, check_gotox_span_unreached_entry, check_gotox_target_without_cfg_edge), that subprog happens to be main and the gotox sits in the other subprog, which is why the outcomes are what the tests assert. Had the spanning map's first entry landed in the gotox's own subprog, check_gotox_tracker_map would fail to load and check_gotox_target_without_cfg_edge would be rejected with the "spans multiple subprogs" message instead. Would wording like "does not become any subprog's jump table" make that dependency clearer?
Quoted 1 line
+{
[ ... ]
Quoted 23 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +23
-0+static void check_gotox_target_subprog_from_main (void ) +{ +const __u32 jt_own[] = {GOTOX_FWD_OWN_TGT }; +const __u32 jt_leaves[] = {GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_own,ARRAY_SIZE (jt_own)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_leaves,ARRAY_SIZE (jt_leaves)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log);
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c static void check_gotox_edges_across_subprogs(void) · line 997
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +10
-0+ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 11 to 14 leaves the subprog [0,14)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +}
This isn't a bug, but could these nine near-identical function bodies share a small table-driven helper? The same roughly 20-line body (calloc log, fill insns, two gotox_jt_create_offs() calls, load, assert, close_maps/free_log labels) is repeated verbatim across check_gotox_tracker_map, check_gotox_target_other_subprog, check_gotox_jt_per_subprog, check_gotox_span_unreached_entry, check_gotox_target_subprog_from_main, check_gotox_jt_spans_subprogs, check_gotox_jt_spans_with_own_table, check_gotox_target_without_cfg_edge, and check_gotox_index_slice_other_subprog. The only differences are the two offset arrays, the fill helper, and the final assertion.
This file's own idiom already factors out that kind of boilerplate - try_load_gotox_prog() and check_gotox_limit_hit() were introduced for exactly that purpose in the preceding patch. A small helper taking (fill, jt_a, jt_b, insn_cnt, expected_err, expected_msg), or a table of cases, would collapse most of these bodies.
A side effect of the duplication is that the copies drifted:check_gotox_jt_per_subprog is the only positive test that uses ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)") and does not print the verifier log on failure, while check_gotox_tracker_map and check_gotox_span_unreached_entry both do 'if (!ASSERT_OK(err, ...)) fprintf(stderr, "verifier log: %s\n", log);', and it's also the only new test without an explanatory comment.
[ ... ]
Quoted 31 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +31
-0+static void check_gotox_target_other_global_subprog (void ) +{ +const __u32 starts[] = {0 ,GOTOX_SUB_START }; +const __u8 linkage[] = {BTF_FUNC_GLOBAL ,BTF_FUNC_GLOBAL }; +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_func_info fi[2 ]; +struct btf *btf =NULL ; +int btf_fd; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,0 ); + + btf_fd =gotox_btf_create (starts, linkage,ARRAY_SIZE (starts), fi, &btf); +if (btf_fd <0 ) + goto free_log; + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_btf; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; +
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c static void check_gotox_edges_across_subprogs(void) · line 1302
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +10
-0+ err =gotox_prog_load_funcs (insns,ARRAY_SIZE (insns), map_fd,2 , log, + btf_fd, fi,ARRAY_SIZE (fi)); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 7 to 2 leaves the subprog [4,10)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_btf:
This isn't a bug, but check_gotox_target_other_global_subprog() looks line-for-line identical to check_gotox_target_other_subprog() - same gotox_two_subprogs_fill(insns, 0, 0), same jt_main/jt_sub contents, same asserted error string "indirect jump from insn 7 to 2 leaves the subprog [4,10)". The only delta is the BTF func_info that makes subprog 1 BTF_FUNC_GLOBAL, plus the extra btf_fd/free_btf plumbing. Would a single helper taking the jump tables, the optional BTF/func_info and the expected log substring read better than the two near-copies?
---
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/34404843294
Re: [PATCH bpf 6/6] selftests/bpf: Add tests for indirect jumps across subprograms
In reply to Daniel BorkmannQuoted 4 lines · Daniel Borkmann
Add various gotox corner case tests to improve corner case coverage.
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
./test_progs -t bpf_insn_array,verifier_gotox,signed_loader
signed_loader? :)
Dunno if there is real value in "leaves the subprog" for different types of "leaves"... But nice to see more tests.
Quoted 786 lines
[...]
#24/13 bpf_insn_array/gotox-tracker-map:OK #24/14 bpf_insn_array/gotox-jt-spans-subprogs:OK #24/15 bpf_insn_array/gotox-jt-spans-with-own-table:OK #24/16 bpf_insn_array/gotox-target-without-cfg-edge:OK #24/17 bpf_insn_array/gotox-target-other-subprog:OK #24/18 bpf_insn_array/gotox-jt-per-subprog:OK #24/19 bpf_insn_array/gotox-span-unreached-entry:OK #24/20 bpf_insn_array/gotox-target-subprog-from-main:OK #24/21 bpf_insn_array/gotox-index-slice-other-subprog:OK #24/22 bpf_insn_array/gotox-target-other-global-subprog:OK #24/23 bpf_insn_array/gotox-callback-leaves-subprog:OK #24 bpf_insn_array:OK[...]
#616 verifier_gotox:OK
Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILEDSigned-off-by Daniel Borkmann <[email protected]>--- .../selftests/bpf/prog_tests/bpf_insn_array.c | 715 +++++++++++++++++- 1 file changed, 713 insertions(+), 2 deletions(-)tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +713
-2@@ -1,6 +1,7 @@// SPDX-License-Identifier: GPL-2.0 #include <bpf/bpf.h> +#include <bpf/btf.h> #include <test_progs.h> #if defined(__x86_64__) || defined(__powerpc__) || defined(__aarch64__)@@ -487,8 +488,9 @@ static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)return -1 ; } -static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, -int *fd_array,__u32 fd_array_cnt,char *log) +static int gotox_prog_load_funcs (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log, +int btf_fd,struct bpf_func_info *fi,__u32 fi_cnt) {LIBBPF_OPTS (bpf_prog_load_opts, opts);int prog_fd;@@ -499,6 +501,12 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt, opts.log_buf = log; opts.log_size =GOTOX_LOG_SZ ; opts.log_level =1 ; +if (fi_cnt) { + opts.prog_btf_fd = btf_fd; + opts.func_info = fi; + opts.func_info_cnt = fi_cnt; + opts.func_info_rec_size =sizeof (*fi); + } prog_fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, insn_cnt, &opts);if (prog_fd >=0 ) {@@ -508,6 +516,13 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,return prog_fd; } +static int gotox_prog_load (struct bpf_insn *insns,__u32 insn_cnt, +int *fd_array,__u32 fd_array_cnt,char *log) +{ +return gotox_prog_load_funcs (insns, insn_cnt, fd_array, fd_array_cnt, log, +-1 ,NULL ,0 ); +} +/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */ static void gotox_run_fill (struct bpf_insn *insns,__u32 gotox_cnt) {@@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)free (log); } +static int gotox_jt_create_offs (const __u32 *offs,__u32 cnt) +{ +struct bpf_insn_array_value val = {}; +int map_fd; +__u32 i; + + map_fd =map_create (BPF_MAP_TYPE_INSN_ARRAY , cnt); +if (!ASSERT_GE (map_fd,0 ,"map_create" )) +return map_fd; + +for (i =0 ; i < cnt; i++) { + val.orig_off = offs[i]; +if (!ASSERT_EQ (bpf_map_update_elem (map_fd, &i, &val,0 ),0 , +"bpf_map_update_elem" )) + goto err; + } + +if (!ASSERT_EQ (bpf_map_freeze (map_fd),0 ,"bpf_map_freeze" )) + goto err; + +return map_fd; +err: +close (map_fd); +return -1 ; +} + +#define GOTOX_SUB_START 4 +#define GOTOX_MAIN_TGT 2 +#define GOTOX_SUB_TGT 8 +#define GOTOX_TWO_INSN_CNT 10 + +static void gotox_two_subprogs_fill (struct bpf_insn *insns,__u32 jt_idx,__u32 jt_off) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_SUB_START -1 -1 ); + insns[GOTOX_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_EXIT_INSN (); + +/* r1 = &jt[0], by index 'jt_idx' into fd_array */ + insns[GOTOX_SUB_START ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm = jt_idx, + }; + insns[GOTOX_SUB_START +1 ] = (struct bpf_insn ) { .imm =0 }; + insns[6 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 , jt_off *8 ); + insns[7 ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_SUB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[9 ] =BPF_EXIT_INSN (); +} + +/* +* An insn_array map is not necessarily a jump table: one that tracks +* instruction offsets covers the whole program and is of no subprog. Such a +* map must not keep a program with a gotox elsewhere from loading. +*/ +static void check_gotox_tracker_map (void ) +{ +const __u32 jt_track[] = {0 ,GOTOX_MAIN_TGT ,GOTOX_SUB_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,1 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_track,ARRAY_SIZE (jt_track)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +if (!ASSERT_OK (err,"program with a tracking map should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static void check_gotox_target_other_subprog (void ) +{ +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 7 to 2 leaves the subprog [4,10)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static void check_gotox_jt_per_subprog (void ) +{ +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,1 ,0 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err,0 ,"bpf(BPF_PROG_LOAD)" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The spanning map is of no subprog and is dropped, and the entry the gotox +* register can reach is in the subprog of the gotox and in the jump table the +* CFG walked, so nothing unsafe is left and the program loads. +*/ +static void check_gotox_span_unreached_entry (void ) +{ +const __u32 jt_span[] = {GOTOX_MAIN_TGT ,GOTOX_SUB_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,1 ); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +if (!ASSERT_OK (err,"program with an unreachable spanning entry should load" )) +fprintf (stderr,"verifier log: %s\n" , log); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_FWD_GOTOX 11 +#define GOTOX_FWD_OWN_TGT 12 +#define GOTOX_FWD_SUB_START 14 +#define GOTOX_FWD_INSN_CNT 16 + +static void gotox_from_main_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_FWD_SUB_START -1 -1 ); + insns[2 ] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_6 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[3 ] =BPF_JMP_IMM (BPF_JEQ ,BPF_REG_2 ,0 ,4 ); + +/* r1 = &jt_leaves[0], by index 1 into fd_array */ + insns[4 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =1 , + }; + insns[5 ] = (struct bpf_insn ) { .imm =0 }; + insns[6 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + insns[7 ] =BPF_JMP_A (3 ); + +/* r1 = &jt_own[0], by index 0 into fd_array */ + insns[8 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[9 ] = (struct bpf_insn ) { .imm =0 }; + insns[10 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + + insns[GOTOX_FWD_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_FWD_OWN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[13 ] =BPF_EXIT_INSN (); + insns[GOTOX_FWD_SUB_START ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[15 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_target_subprog_from_main (void ) +{ +const __u32 jt_own[] = {GOTOX_FWD_OWN_TGT }; +const __u32 jt_leaves[] = {GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_own,ARRAY_SIZE (jt_own)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_leaves,ARRAY_SIZE (jt_leaves)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 11 to 14 leaves the subprog [0,14)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The only map of the subprog holding the gotox reaches past that subprog, so +* the subprog is left without a jump table at all. +*/ +static void check_gotox_jt_spans_subprogs (void ) +{ +const __u32 jt_span[] = {GOTOX_FWD_OWN_TGT ,GOTOX_FWD_SUB_START }; +const __u32 jt_leaves[] = {GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_leaves,ARRAY_SIZE (jt_leaves)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"jump table of subprog starting at 0 spans multiple subprogs" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +/* +* The subprog holding the gotox has a well formed jump table of its own and +* also collects a map that reaches past its end. The spanning map is still +* rejected, even though the subprog is not left without a table. +*/ +static void check_gotox_jt_spans_with_own_table (void ) +{ +const __u32 jt_own[] = {GOTOX_FWD_OWN_TGT }; +const __u32 jt_span[] = {GOTOX_FWD_OWN_TGT ,GOTOX_FWD_SUB_START }; +struct bpf_insn insns[GOTOX_FWD_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_from_main_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_own,ARRAY_SIZE (jt_own)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"jump table of subprog starting at 0 spans multiple subprogs" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_EDGE_MAIN_TGT 2 +#define GOTOX_EDGE_SUB_START 4 +#define GOTOX_EDGE_GOTOX 9 +#define GOTOX_EDGE_BR_TGT 10 +#define GOTOX_EDGE_JT_TGT 11 +#define GOTOX_EDGE_INSN_CNT 12 + +static void gotox_no_edge_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_EDGE_SUB_START -1 -1 ); + insns[GOTOX_EDGE_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_EXIT_INSN (); + + insns[GOTOX_EDGE_SUB_START ] = +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[5 ] =BPF_JMP_IMM (BPF_JNE ,BPF_REG_2 ,0 ,4 ); + +/* r1 = &jt_span[0], by index 0 into fd_array */ + insns[6 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[7 ] = (struct bpf_insn ) { .imm =0 }; + insns[8 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,8 ); + + insns[GOTOX_EDGE_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_EDGE_BR_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[GOTOX_EDGE_JT_TGT ] =BPF_EXIT_INSN (); +} + +/* +* The gotox resolves a target inside its own subprog, but out of a map that +* spans subprogs and is therefore of no subprog. The CFG never walked that +* edge, so the jump has to be rejected even though it stays in the subprog. +*/ +static void check_gotox_target_without_cfg_edge (void ) +{ +const __u32 jt_span[] = {GOTOX_EDGE_MAIN_TGT ,GOTOX_EDGE_BR_TGT }; +const __u32 jt_sub[] = {GOTOX_EDGE_JT_TGT }; +struct bpf_insn insns[GOTOX_EDGE_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_no_edge_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_span,ARRAY_SIZE (jt_span)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log, +"indirect jump from insn 9 to 10 is not in the jump table of the subprog" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +#define GOTOX_SLICE_SUB_START 6 +#define GOTOX_SLICE_GOTOX 14 +#define GOTOX_SLICE_SUB_TGT 15 +#define GOTOX_SLICE_INSN_CNT 17 + +static void gotox_slice_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[1 ] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,BPF_PSEUDO_CALL ,0 , +GOTOX_SLICE_SUB_START -1 -1 ); + insns[2 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[3 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[4 ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[5 ] =BPF_EXIT_INSN (); + + insns[GOTOX_SLICE_SUB_START ] = +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct xdp_md , ingress_ifindex)); + insns[7 ] =BPF_ALU64_IMM (BPF_AND ,BPF_REG_2 ,1 ); + insns[8 ] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ); + insns[9 ] =BPF_ALU64_IMM (BPF_LSH ,BPF_REG_2 ,3 ); + +/* r1 = &jt_main[0], by index 0 into fd_array */ + insns[10 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[11 ] = (struct bpf_insn ) { .imm =0 }; + insns[12 ] =BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_2 ); + insns[13 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + + insns[GOTOX_SLICE_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_SLICE_SUB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,1 ); + insns[16 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_index_slice_other_subprog (void ) +{ +const __u32 jt_main[] = {2 ,3 ,4 }; +const __u32 jt_sub[] = {GOTOX_SLICE_SUB_TGT }; +struct bpf_insn insns[GOTOX_SLICE_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_slice_fill (insns); + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_log; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load (insns,ARRAY_SIZE (insns), map_fd,2 , log); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 14 to 3 leaves the subprog [6,17)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_log: +free (log); +} + +static int gotox_btf_create (const __u32 *starts,const __u8 *linkage,__u32 cnt, +struct bpf_func_info *fi,struct btf **pbtf) +{ +int int_id, proto_id, id; +struct btf *btf; +char name[24 ]; +__u32 i; + + btf =btf__new_empty (); +if (!ASSERT_OK_PTR (btf,"btf__new_empty" )) +return -1 ; + + int_id =btf__add_int (btf,"int" ,4 ,BTF_INT_SIGNED ); +if (!ASSERT_GT (int_id,0 ,"btf__add_int" )) + goto err; + + proto_id =btf__add_func_proto (btf, int_id); +if (!ASSERT_GT (proto_id,0 ,"btf__add_func_proto" )) + goto err; + +for (i =0 ; i < cnt; i++) { +snprintf (name,sizeof (name),"gotox_f%u" , i); + id =btf__add_func (btf, name, linkage[i], proto_id); +if (!ASSERT_GT (id,0 ,"btf__add_func" )) + goto err; + fi[i].insn_off = starts[i]; + fi[i].type_id = id; + } + +if (!ASSERT_OK (btf__load_into_kernel (btf),"btf__load_into_kernel" )) + goto err; + + *pbtf = btf; +return btf__fd (btf); +err: +btf__free (btf); +return -1 ; +} + +static void check_gotox_target_other_global_subprog (void ) +{ +const __u32 starts[] = {0 ,GOTOX_SUB_START }; +const __u8 linkage[] = {BTF_FUNC_GLOBAL ,BTF_FUNC_GLOBAL }; +const __u32 jt_main[] = {GOTOX_MAIN_TGT }; +const __u32 jt_sub[] = {GOTOX_SUB_TGT }; +struct bpf_insn insns[GOTOX_TWO_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_func_info fi[2 ]; +struct btf *btf =NULL ; +int btf_fd; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_two_subprogs_fill (insns,0 ,0 ); + + btf_fd =gotox_btf_create (starts, linkage,ARRAY_SIZE (starts), fi, &btf); +if (btf_fd <0 ) + goto free_log; + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_btf; + map_fd[1 ] =gotox_jt_create_offs (jt_sub,ARRAY_SIZE (jt_sub)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load_funcs (insns,ARRAY_SIZE (insns), map_fd,2 , log, + btf_fd, fi,ARRAY_SIZE (fi)); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 7 to 2 leaves the subprog [4,10)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_btf: +btf__free (btf); +free_log: +free (log); +} + +#define GOTOX_CB_MAIN_TGT 6 +#define GOTOX_CB_START 8 +#define GOTOX_CB_GOTOX 11 +#define GOTOX_CB_TGT 12 +#define GOTOX_CB_INSN_CNT 14 + +static void gotox_callback_fill (struct bpf_insn *insns) +{ + insns[0 ] =BPF_MOV64_IMM (BPF_REG_1 ,1 ); +/* r2 = &callback */ + insns[1 ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_2 , + .src_reg =BPF_PSEUDO_FUNC , + .imm =GOTOX_CB_START -1 -1 , + }; + insns[2 ] = (struct bpf_insn ) { .imm =0 }; + insns[3 ] =BPF_MOV64_IMM (BPF_REG_3 ,0 ); + insns[4 ] =BPF_MOV64_IMM (BPF_REG_4 ,0 ); + insns[5 ] =BPF_EMIT_CALL (BPF_FUNC_loop); + insns[GOTOX_CB_MAIN_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[7 ] =BPF_EXIT_INSN (); + +/* r1 = &jt_main[0], by index 0 into fd_array */ + insns[GOTOX_CB_START ] = (struct bpf_insn ) { + .code =BPF_LD |BPF_DW |BPF_IMM , + .dst_reg =BPF_REG_1 , + .src_reg =BPF_PSEUDO_MAP_IDX_VALUE , + .imm =0 , + }; + insns[9 ] = (struct bpf_insn ) { .imm =0 }; + insns[10 ] =BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 ,0 ); + insns[GOTOX_CB_GOTOX ] =BPF_RAW_INSN (BPF_JMP |BPF_JA |BPF_X ,BPF_REG_1 ,0 ,0 ,0 ); + insns[GOTOX_CB_TGT ] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[13 ] =BPF_EXIT_INSN (); +} + +static void check_gotox_callback_leaves_subprog (void ) +{ +const __u32 starts[] = {0 ,GOTOX_CB_START }; +const __u8 linkage[] = {BTF_FUNC_GLOBAL ,BTF_FUNC_STATIC }; +const __u32 jt_main[] = {GOTOX_CB_MAIN_TGT }; +const __u32 jt_cb[] = {GOTOX_CB_TGT }; +struct bpf_insn insns[GOTOX_CB_INSN_CNT ]; +int map_fd[2 ] = {-1 ,-1 }; +struct bpf_func_info fi[2 ]; +struct btf *btf =NULL ; +int btf_fd; +char *log; +int err; + + log =calloc (1 ,GOTOX_LOG_SZ ); +if (!ASSERT_OK_PTR (log,"calloc log" )) +return ; + +gotox_callback_fill (insns); + + btf_fd =gotox_btf_create (starts, linkage,ARRAY_SIZE (starts), fi, &btf); +if (btf_fd <0 ) + goto free_log; + + map_fd[0 ] =gotox_jt_create_offs (jt_main,ARRAY_SIZE (jt_main)); +if (map_fd[0 ] <0 ) + goto free_btf; + map_fd[1 ] =gotox_jt_create_offs (jt_cb,ARRAY_SIZE (jt_cb)); +if (map_fd[1 ] <0 ) + goto close_maps; + + err =gotox_prog_load_funcs (insns,ARRAY_SIZE (insns), map_fd,2 , log, + btf_fd, fi,ARRAY_SIZE (fi)); +ASSERT_EQ (err, -EINVAL ,"program should have been rejected" ); +ASSERT_HAS_SUBSTR (log,"indirect jump from insn 11 to 6 leaves the subprog [8,14)" , +"verifier log" ); + +close_maps: +close (map_fd[0 ]); +close (map_fd[1 ]); +free_btf: +btf__free (btf); +free_log: +free (log); +} +static void check_bpf_side (void ) {check_bpf_no_lookup ();@@ -756,6 +1434,39 @@ static void __test_bpf_insn_array(void)if (test__start_subtest ("gotox-edges-across-subprogs" ))check_gotox_edges_across_subprogs (); + +if (test__start_subtest ("gotox-tracker-map" )) +check_gotox_tracker_map (); + +if (test__start_subtest ("gotox-jt-spans-subprogs" )) +check_gotox_jt_spans_subprogs (); + +if (test__start_subtest ("gotox-jt-spans-with-own-table" )) +check_gotox_jt_spans_with_own_table (); + +if (test__start_subtest ("gotox-target-without-cfg-edge" )) +check_gotox_target_without_cfg_edge (); + +if (test__start_subtest ("gotox-target-other-subprog" )) +check_gotox_target_other_subprog (); + +if (test__start_subtest ("gotox-jt-per-subprog" )) +check_gotox_jt_per_subprog (); + +if (test__start_subtest ("gotox-span-unreached-entry" )) +check_gotox_span_unreached_entry (); + +if (test__start_subtest ("gotox-target-subprog-from-main" )) +check_gotox_target_subprog_from_main (); + +if (test__start_subtest ("gotox-index-slice-other-subprog" )) +check_gotox_index_slice_other_subprog (); + +if (test__start_subtest ("gotox-target-other-global-subprog" )) +check_gotox_target_other_global_subprog (); + +if (test__start_subtest ("gotox-callback-leaves-subprog" )) + check_gotox_callback_leaves_subprog(); }#else static void __test_bpf_insn_array (void )Signature · 1 line
2.43.0
Quoted 13 lines · Daniel Borkmann
The iterative Tarjan DFS in
bpf_compute_scc()emulates recursion with an explicit 'dfs' stack: when a successor has not been visited yet, the successor is pushed and the walk restarts at the top of the loop. On the way back to a vertex the successor scan starts over at index zero, so a vertex with k successors rescans up to k successors on each of its up to k descents, i.e. O(k^2) work.For ordinary instructions k <= 2 and this is irrelevant. For a gotox the successors are the jump table of the containing subprogram, whose size is bounded only by the
max_entriesof theinsn_arraymap, so k can reach the 1M instruction complexity limit. Loading such a program keeps a CPU busy in the loop for a very long time before verification even begins.
Quoted 8 lines
Record in '
dfs_pos' the successor index each frame stopped at and resume the scan there. Each edge is therefore examined a bounded number of times and the walk becomes linear in the number of edges.Fixes 493d9e0d6083 ("bpf, x86: add support for indirect jumps")Reported-by STAR Labs SG <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>---
The change looks correct, but I'd cleanup the comments a bit, to me these look too LLM-ish.
Quoted 45 lines
kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------ 1 file changed, 35 insertions(+), 6 deletions(-)kernel/bpf/cfg.c +7
-3@@ -749,7 +749,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)struct bpf_insn_aux_data *aux = env->insn_aux_data;const u32 insn_cnt = env->prog->len;int stack_sz, dfs_sz, err =0 ; -u32 *stack, *pre, *low, *dfs; +u32 *stack, *pre, *low, *dfs, *dfs_pos;u32 i, j, t, w;u32 next_preorder_num;u32 next_scc_id;@@ -762,13 +762,16 @@ int bpf_compute_scc(struct bpf_verifier_env *env)* - 'stack' accumulates vertices in DFS order, see invariant comment below; * - 'pre[t] == p' => preorder number of vertex 't' is 'p'; * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n'; -* - 'dfs' DFS traversal stack, used to emulate explicit recursion. +* - 'dfs' DFS traversal stack, used to emulate explicit recursion; +* - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its +* successors at index 'j'. */ stack =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); pre =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); low =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL_ACCOUNT ); dfs =kvcalloc (insn_cnt,sizeof (*dfs),GFP_KERNEL_ACCOUNT ); -if (!stack || !pre || !low || !dfs) { + dfs_pos =kvcalloc (insn_cnt,sizeof (*dfs_pos),GFP_KERNEL_ACCOUNT ); +if (!stack || !pre || !low || !dfs || !dfs_pos) { err = -ENOMEM ; goto exit; }@@ -851,6 +854,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env) stack_sz =0 ; dfs_sz =1 ; dfs[0 ] = i; + dfs_pos[0 ] =0 ; dfs_continue:while (dfs_sz) { w = dfs[dfs_sz -1 ];@@ -860,13 +864,37 @@ int bpf_compute_scc(struct bpf_verifier_env *env) next_preorder_num++;
kernel/bpf/cfg.c int bpf_compute_scc(struct bpf_verifier_env *env) · line 873
Quoted 10 lines
kernel/bpf/cfg.c +7
-1stack[stack_sz++] = w; } -/* Visit 'w' successors */ +/* +* Visit 'w' successors, resuming at the successor this +* frame last descended into. Restarting the scan at zero +* on every return to 'w' would examine each successor +* once per descent, i.e. quadratic in the number of +* successors, which for a gotox is the size of the jump +* table.
Please drop the paragraph above, this fact was already stated in the commit message.
kernel/bpf/cfg.c int bpf_compute_scc(struct bpf_verifier_env *env) · line 875
Quoted 2 lines
kernel/bpf/cfg.c +2
-0+* +* Re-folding the successors before that index would be a
I think "visiting" is a better term in this context.
kernel/bpf/cfg.c int bpf_compute_scc(struct bpf_verifier_env *env) · line 883
Quoted 8 lines
kernel/bpf/cfg.c +8
-0+* no-op. Such a successor 's' has 'pre[s] != 0' by then, +* so it is never pushed onto 'dfs' again, and low[s] can +* only decrease while 's' is the top of 'dfs'. If 's' is +* still on 'dfs' it sits below 'w' and cannot become the +* top before 'w' is popped; otherwise the only remaining +* write to low[s] is the pop of its SCC, setting it to +* NOT_ON_STACK, for which the min below is a no-op. +*/
Tbh, I find this paragraph extremely hard to parse. Why not simply /* Visit the next 'w' successor */ ?
kernel/bpf/cfg.c int bpf_compute_scc(struct bpf_verifier_env *env) · line 893
Quoted 12 lines
kernel/bpf/cfg.c +6
-2succ =bpf_insn_successors (env, w); -for (j =0 ; j < succ->cnt; ++j) { +for (j = dfs_pos[dfs_sz -1 ]; j < succ->cnt; ++j) {if (pre[succ->items[j]]) { low[w] =min (low[w], low[succ->items[j]]); }else { - dfs[dfs_sz++] = succ->items[j]; +/* +* Resume at 'j', not 'j + 1': the successor +* is revisited once its DFS completes, to +* fold its low[] into low[w]. +*/
/*
* Once DFS for succ->items[j] is complete, the pre[succ->items[j]] would be non-zero,
* hence resuming at 'j' allows to follow the update low[w] = min(...) branch above. */
Quoted 14 lines
kernel/bpf/cfg.c +5
-0+ dfs_pos[dfs_sz -1 ] = j; + dfs_pos[dfs_sz] =0 ; + dfs[dfs_sz] = succ->items[j]; + dfs_sz++; goto dfs_continue; } }@@ -916,5 +944,6 @@ int bpf_compute_scc(struct bpf_verifier_env *env)kvfree (pre);kvfree (low);kvfree (dfs); +kvfree (dfs_pos);return err; }