Re: [PATCH v3 bpf-next 08/13] bpf, x86: add support for indirect jumps

Eduard Zingerman
2025-09-20T00:28:48Z

On Thu, 2025-09-18 at 09:38 +0000, Anton Protopopov wrote:
> Add support for a new instruction
>
> BPF_JMP|BPF_X|BPF_JA, SRC=0, DST=Rx, off=0, imm=0
>
> which does an indirect jump to a location stored in Rx. The register
> Rx should have type PTR_TO_INSN. This new type assures that the Rx
> register contains a value (or a range of values) loaded from a
> correct jump table – map of type instruction array.
>
> For example, for a C switch LLVM will generate the following code:
>
> 0: r3 = r1 # "switch (r3)"
> 1: if r3 > 0x13 goto +0x666 # check r3 boundaries
> 2: r3 <<= 0x3 # adjust to an index in array of addresses
> 3: r1 = 0xbeef ll # r1 is PTR_TO_MAP_VALUE, r1->map_ptr=M
> 5: r1 += r3 # r1 inherits boundaries from r3
> 6: r1 = *(u64 *)(r1 + 0x0) # r1 now has type INSN_TO_PTR
> 7: gotox r1[,imm=fd(M)] # jit will generate proper code
^^^^^^^^^^^^
Nit: this part is not needed atm.
>
> Here the gotox instruction corresponds to one particular map. This is
> possible however to have a gotox instruction which can be loaded from
> different maps, e.g.

[...]

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index aca43c284203..607a684642e5 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h

[...]

> @@ -586,6 +597,9 @@ struct bpf_insn_aux_data {
> u8 fastcall_spills_num:3;
> u8 arg_prog:4;
>
> + /* true if jt->off was allocated */
> + bool jt_allocated;
> +

Nit: in clear_insn_aux_data() maybe just check if instruction is a gotox?

> /* below fields are initialized once */
> unsigned int orig_idx; /* original instruction index */
> bool jmp_point;

[...]

> static inline struct bpf_func_info_aux *subprog_aux(struct bpf_verifier_env *env, int subprog)
> diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
> index 0c8dac62f457..4b945b7e31b8 100644
> --- a/kernel/bpf/bpf_insn_array.c
> +++ b/kernel/bpf/bpf_insn_array.c
> @@ -1,7 +1,6 @@
> // SPDX-License-Identifier: GPL-2.0-only
>
> #include <linux/bpf.h>
> -#include <linux/sort.h>

Nit: remove this include from patch #3?

>
> #define MAX_INSN_ARRAY_ENTRIES 256
>

[...]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5c1e4e37d1f8..839260e62fa9 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[...]

> @@ -7620,6 +7644,19 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
>
> regs[value_regno].type = SCALAR_VALUE;
> __mark_reg_known(&regs[value_regno], val);
> + } else if (map->map_type == BPF_MAP_TYPE_INSN_ARRAY) {
> + regs[value_regno].type = PTR_TO_INSN;
> + regs[value_regno].map_ptr = map;
> + regs[value_regno].off = reg->off;
> + regs[value_regno].umin_value = reg->umin_value;
> + regs[value_regno].umax_value = reg->umax_value;
> + regs[value_regno].smin_value = reg->smin_value;
> + regs[value_regno].smax_value = reg->smax_value;
> + regs[value_regno].s32_min_value = reg->s32_min_value;
> + regs[value_regno].s32_max_value = reg->s32_max_value;
> + regs[value_regno].u32_min_value = reg->u32_min_value;
> + regs[value_regno].u32_max_value = reg->u32_max_value;
> + regs[value_regno].var_off = reg->var_off;

This can be shortened to:

copy_register_state(regs + value_regno, reg);
regs[value_regno].type = PTR_TO_INSN;

I think that a check that read is u64 wide is necessary here.
Otherwise e.g. for u8 load you'd need to truncate the bounds set above.
This is also necessary for alignment check at the beginning of this
function (check_ptr_alignment() call).

> } else {
> mark_reg_unknown(env, regs, value_regno);
> }

[...]

> @@ -14628,6 +14672,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
> }
> break;
> case BPF_SUB:
> + if (ptr_to_insn_array) {
> + verbose(env, "Operation %s on ptr to instruction set map is prohibited\n",
> + bpf_alu_string[opcode >> 4]);
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Nit: Just "subtraction", no need for lookup?
Also, maybe put this near the same check for PTR_TO_STACK?

> + return -EACCES;
> + }
> if (dst_reg == off_reg) {
> /* scalar -= pointer. Creates an unknown scalar */
> verbose(env, "R%d tried to subtract pointer from scalar\n",

[...]

> @@ -17733,6 +17783,234 @@ static int mark_fastcall_patterns(struct bpf_verifier_env *env)
> return 0;
> }
>
> +#define SET_HIGH(STATE, LAST) STATE = (STATE & 0xffffU) | ((LAST) << 16)
> +#define GET_HIGH(STATE) ((u16)((STATE) >> 16))
> +
> +static int push_gotox_edge(int t, struct bpf_verifier_env *env, struct bpf_iarray *jt)
> +{
> + int *insn_stack = env->cfg.insn_stack;
> + int *insn_state = env->cfg.insn_state;
> + u16 prev;
> + int w;
> +
> + for (prev = GET_HIGH(insn_state[t]); prev < jt->off_cnt; prev++) {
> + w = jt->off[prev];
> +
> + /* EXPLORED || DISCOVERED */
> + if (insn_state[w])
> + continue;

Suppose there is some other way to reach `w` beside gotox.
Also suppose that `w` had been visited already.
In such case `mark_jmp_point(env, w)` might get omitted for `w`.

> +
> + break;
> + }
> +
> + if (prev == jt->off_cnt)
> + return DONE_EXPLORING;
> +
> + mark_prune_point(env, t);

Nit: do this from visit_gotox_insn() ?

> +
> + if (env->cfg.cur_stack >= env->prog->len)
> + return -E2BIG;
> + insn_stack[env->cfg.cur_stack++] = w;
> +
> + mark_jmp_point(env, w);
> +
> + SET_HIGH(insn_state[t], prev + 1);
> + return KEEP_EXPLORING;
> +}

[...]

> +/*
> + * Find and collect all maps which fit in the subprog. Return the result as one
> + * combined jump table in jt->off (allocated with kvcalloc
^^^
nit: missing ')'

> + */
> +static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
> + int subprog_start, int subprog_end)

[...]

> +static struct bpf_iarray *
> +create_jt(int t, struct bpf_verifier_env *env, int fd)
^^^^^^
fd is unused, same for visit_gotox_insn()

[...]

> @@ -18716,6 +19001,10 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
> case PTR_TO_ARENA:
> return true;
> + case PTR_TO_INSN:
> + /* is rcur a subset of rold? */
> + return (rcur->umin_value >= rold->umin_value &&
> + rcur->umax_value <= rold->umax_value);

I think this should be:

if (rold->off != rcur->off)
return false;
return range_within(old: rold, cur: rcur) &&
tnum_in(a: rold->var_off, b: rcur->var_off);

> default:
> return regs_exact(rold, rcur, idmap);
> }
> @@ -19862,6 +20151,102 @@ static int process_bpf_exit_full(struct bpf_verifier_env *env,
> return PROCESS_BPF_EXIT;
> }
>
> +static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
> + int regno,
> + struct bpf_map *map,
> + u32 *pmin_index, u32 *pmax_index)
> +{
> + struct bpf_reg_state *reg = reg_state(env, regno);
> + u64 min_index, max_index;
> +
> + if (check_add_overflow(reg->umin_value, reg->off, &min_index) ||
> + (min_index > (u64) U32_MAX * sizeof(long))) {
> + verbose(env, "the sum of R%u umin_value %llu and off %u is too big\n",
> + regno, reg->umin_value, reg->off);
> + return -ERANGE;
> + }
> + if (check_add_overflow(reg->umax_value, reg->off, &max_index) ||
> + (max_index > (u64) U32_MAX * sizeof(long))) {
> + verbose(env, "the sum of R%u umax_value %llu and off %u is too big\n",
> + regno, reg->umax_value, reg->off);
> + return -ERANGE;
> + }
> +
> + min_index /= sizeof(long);
> + max_index /= sizeof(long);

Nit: `long` is 32-bit long on x86 (w/o -64), I understand that x86 jit
would just reject gotox, but could you please use `sizeof(u64)` here?

> +
> + if (min_index >= map->max_entries || max_index >= map->max_entries) {
> + verbose(env, "R%u points to outside of jump table: [%llu,%llu] max_entries %u\n",
> + regno, min_index, max_index, map->max_entries);
> + return -EINVAL;
> + }
> +
> + *pmin_index = min_index;
> + *pmax_index = max_index;
> + return 0;
> +}
> +
> +/* 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_reg_state *dst_reg;
> + struct bpf_map *map;
> + u32 min_index, max_index;
> + int err = 0;
> + u32 *xoff;
> + int n;
> + int i;
> +
> + dst_reg = reg_state(env, insn->dst_reg);
> + if (dst_reg->type != PTR_TO_INSN) {
> + verbose(env, "R%d has type %d, expected PTR_TO_INSN\n",
> + insn->dst_reg, dst_reg->type);
> + return -EINVAL;
> + }
> +
> + map = dst_reg->map_ptr;
> + if (verifier_bug_if(!map, env, "R%d has an empty map pointer", insn->dst_reg))
> + return -EFAULT;
> +
> + if (verifier_bug_if(map->map_type != BPF_MAP_TYPE_INSN_ARRAY, env,
> + "R%d has incorrect map type %d", insn->dst_reg, map->map_type))
> + return -EFAULT;
> +
> + err = indirect_jump_min_max_index(env, insn->dst_reg, map, &min_index, &max_index);
> + if (err)
> + return err;
> +
> + xoff = kvcalloc(max_index - min_index + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
> + if (!xoff)
> + return -ENOMEM;

Let's keep a buffer for this allocation in `env` and realloc it when needed.
Would be good to avoid allocating memory each time this gotox is visited.

> +
> + n = copy_insn_array_uniq(map, min_index, max_index, xoff);
> + if (n < 0) {
> + err = n;
> + goto free_off;
> + }
> + if (n == 0) {
> + verbose(env, "register R%d doesn't point to any offset in map id=%d\n",
> + insn->dst_reg, map->id);
> + err = -EINVAL;
> + goto free_off;
> + }
> +
> + for (i = 0; i < n - 1; i++) {
> + other_branch = push_stack(env, xoff[i], env->insn_idx, false);
^^^^^
`is_speculative` has to be inherited from env->cur_state

> + if (IS_ERR(other_branch)) {
> + err = PTR_ERR(other_branch);
> + goto free_off;
> + }
> + }
> + env->insn_idx = xoff[n-1];
> +
> +free_off:
> + kvfree(xoff);
> + return err;
> +}
> +
> static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
> {
> int err;
> @@ -19964,6 +20349,9 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
>
> mark_reg_scratched(env, BPF_REG_0);
> } else if (opcode == BPF_JA) {
> + if (BPF_SRC(insn->code) == BPF_X)
> + return check_indirect_jump(env, insn);
> +

check_indirect_jump() does not check reserved fields (like offset or dst_reg).

> if (BPF_SRC(insn->code) != BPF_K ||
> insn->src_reg != BPF_REG_0 ||
> insn->dst_reg != BPF_REG_0 ||

[...]

> @@ -24215,23 +24625,41 @@ static bool can_jump(struct bpf_insn *insn)
> return false;
> }
>
> -static int insn_successors(struct bpf_prog *prog, u32 idx, u32 succ[2])
> +/*
> + * Returns an array of instructions succ, with succ->off[0], ...,
> + * succ->off[n-1] with successor instructions, where n=succ->off_cnt
> + */
> +static struct bpf_iarray *
> +insn_successors(struct bpf_verifier_env *env, u32 insn_idx)

Nit: maybe put insn_successors refactoring to a separate patch?

> {
> - struct bpf_insn *insn = &prog->insnsi[idx];
> - int i = 0, insn_sz;
> + struct bpf_prog *prog = env->prog;
> + struct bpf_insn *insn = &prog->insnsi[insn_idx];
> + struct bpf_iarray *succ;
> + int insn_sz;
> u32 dst;
>
> - insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
> - if (can_fallthrough(insn) && idx + 1 < prog->len)
> - succ[i++] = idx + insn_sz;
> + if (unlikely(insn_is_gotox(insn))) {
> + succ = env->insn_aux_data[insn_idx].jt;
> + if (verifier_bug_if(!succ, env,
> + "aux data for insn %u doesn't contain a jump table\n",
> + insn_idx))
> + return ERR_PTR(-EFAULT);

Requiring each callsite to check error code for this function is very inconvenient.
Moreover, insn_successors() is hot in liveness.c:update_instance().
Let's just assume that NULL here cannot happen.

> + } else {
> + /* pre-allocated array of size up to 2; reset cnt, as it may be used already */
> + succ = env->succ;
> + succ->off_cnt = 0;
>
> - if (can_jump(insn)) {
> - dst = idx + jmp_offset(insn) + 1;
> - if (i == 0 || succ[0] != dst)
> - succ[i++] = dst;
> - }
> + insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
> + if (can_fallthrough(insn) && insn_idx + 1 < prog->len)
> + succ->off[succ->off_cnt++] = insn_idx + insn_sz;
>
> - return i;
> + if (can_jump(insn)) {
> + dst = insn_idx + jmp_offset(insn) + 1;
> + if (succ->off_cnt == 0 || succ->off[0] != dst)
> + succ->off[succ->off_cnt++] = dst;
> + }
> + }
> + return succ;
> }
>

[...]

> @@ -24489,11 +24921,10 @@ static int compute_scc(struct bpf_verifier_env *env)
> const u32 insn_cnt = env->prog->len;
> int stack_sz, dfs_sz, err = 0;
> u32 *stack, *pre, *low, *dfs;
> - u32 succ_cnt, i, j, t, w;
> + u32 i, j, t, w;
> u32 next_preorder_num;
> u32 next_scc_id;
> bool assign_scc;
> - u32 succ[2];
>
> next_preorder_num = 1;
> next_scc_id = 1;
> @@ -24592,6 +25023,8 @@ static int compute_scc(struct bpf_verifier_env *env)
> dfs[0] = i;
> dfs_continue:
> while (dfs_sz) {
> + struct bpf_iarray *succ;
> +

Nit: please move this declaration up, just to be consistent with other variables.

> w = dfs[dfs_sz - 1];
> if (pre[w] == 0) {
> low[w] = next_preorder_num;
> @@ -24600,12 +25033,17 @@ static int compute_scc(struct bpf_verifier_env *env)
> stack[stack_sz++] = w;
> }
> /* Visit 'w' successors */
> - succ_cnt = insn_successors(env->prog, w, succ);
> - for (j = 0; j < succ_cnt; ++j) {
> - if (pre[succ[j]]) {
> - low[w] = min(low[w], low[succ[j]]);
> + succ = insn_successors(env, w);
> + if (IS_ERR(succ)) {
> + err = PTR_ERR(succ);
> + goto exit;
> +
> + }
> + for (j = 0; j < succ->off_cnt; ++j) {
> + if (pre[succ->off[j]]) {
> + low[w] = min(low[w], low[succ->off[j]]);
> } else {
> - dfs[dfs_sz++] = succ[j];
> + dfs[dfs_sz++] = succ->off[j];
> goto dfs_continue;
> }
> } …