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. Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps") Reported-by: STAR Labs SG Signed-off-by: Daniel Borkmann --- kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------ 1 file changed, 35 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index 842c7d1eabcc..081f7003eae6 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -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; } -- 2.43.0 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 Signed-off-by: Daniel Borkmann --- include/linux/bpf_verifier.h | 1 + kernel/bpf/cfg.c | 15 +++++++++++++++ 2 files changed, 16 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 36b65797877d..04bb8f71cabe 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -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; diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index 081f7003eae6..e9910228da58 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -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); -- 2.43.0 create_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 Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps") Signed-off-by: Daniel Borkmann --- include/linux/bpf_verifier.h | 2 + kernel/bpf/cfg.c | 99 +++++++++++++++++++++++------------- 2 files changed, 65 insertions(+), 36 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 04bb8f71cabe..301a47d2b272 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -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; diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index e9910228da58..8aee94689229 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -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; -- 2.43.0 The 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. Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps") Reported-by: James Burton Reported-by: Nuoqi Gui Signed-off-by: Daniel Borkmann --- 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(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 301a47d2b272..baf2e17d7019 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -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; diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index 8aee94689229..879587af8d08 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -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; } diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 72a3f5998dd2..45234e2fbee6 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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 *in return -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]; + + 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], diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c index 5b18c9a27717..3567b29e2378 100644 --- a/tools/testing/selftests/bpf/progs/verifier_gotox.c +++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c @@ -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 (" \ -- 2.43.0 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:OK Summary: 1/12 PASSED, 0 SKIPPED, 0/0 FAILED Signed-off-by: Daniel Borkmann --- .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++ 1 file changed, 266 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c index 0222a9a5d076..c69d44cd4607 100644 --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c @@ -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) -- 2.43.0 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 [...] #616 verifier_gotox:OK Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED Signed-off-by: Daniel Borkmann --- .../selftests/bpf/prog_tests/bpf_insn_array.c | 715 +++++++++++++++++- 1 file changed, 713 insertions(+), 2 deletions(-) diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c index c69d44cd4607..d5a831a75d82 100644 --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-2.0 #include +#include #include #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) -- 2.43.0