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

[Anton Protopopov <a.s.protopopov@gmail.com>]

On 25/09/19 05:28PM, Eduard Zingerman wrote:
> 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.

Thanks, removed.

> > 
> > 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?

Yes, this should work, thanks

> 
> >  	/* 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?

sure, thanks!

> >  
> >  #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).

will fix, thanks!

> >  			} 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?

ok

> 
> > +			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`.

thanks

> > +
> > +		break;
> > +	}
> > +
> > +	if (prev == jt->off_cnt)
> > +		return DONE_EXPLORING;
> > +
> > +	mark_prune_point(env, t);
> 
> Nit: do this from visit_gotox_insn() ?

yes, ok

> > +
> > +	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);

ok, makes sense

> >  	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?

Haven't check, really, but will the jump table contain 8-byte records
for x86_32? I thought they are size of pointers, thus I use long.

Still can replace by 8, yes.

> > +
> > +	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.

Ok (to put it in bpf_subprog_info as suggested in your next letter).
Though, probably it still needs to grow (= realloc).

> > +
> > +	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

Ah, yes, thanks

> > +		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).

Ok, thanks, will fix. Though, maybe, in the visit_gotox, why to wait until here?

(just in case, should be s/dst_reg/src_reg in your comment)

> 
> >  			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?

Yes, makes sense, will do. (In any case thi piece needs to be
carefully rebased after you recent changes.)

> >  {
> > -	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.

Hmm, ok. I will check and fix.

> > +	} 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.

Sure

> >  			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;
> >  				}
> >  			}
> 
> [...]