Re: [PATCH v6 bpf-next 10/17] bpf, x86: add support for indirect jumps

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

On 25/10/21 02:17PM, Eduard Zingerman wrote:
> On Sun, 2025-10-19 at 20:21 +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                   # jit will generate proper code
> > 
> > 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.
> > 
> >     0:   r1 &= 0x1
> >     1:   r2 <<= 0x3
> >     2:   r3 = 0x0 ll                # load from map M_1
> >     4:   r3 += r2
> >     5:   if r1 == 0x0 goto +0x4
> >     6:   r1 <<= 0x3
> >     7:   r3 = 0x0 ll                # load from map M_2
> >     9:   r3 += r1
> >     A:   r1 = *(u64 *)(r3 + 0x0)
> >     B:   gotox r1                   # jump to target loaded from M_1 or M_2
> > 
> > During check_cfg stage the verifier will collect all the maps which
> > point to inside the subprog being verified. When building the config,
> > the high 16 bytes of the insn_state are used, so this patch
> > (theoretically) supports jump tables of up to 2^16 slots.
> > 
> > During the later stage, in check_indirect_jump, it is checked that
> > the register Rx was loaded from a particular instruction array.
> > 
> > Signed-off-by: Anton Protopopov <a.s.protopopov@gmail.com>
> > ---
> 
> LGTM, please, address a few remaining points.
> 
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> 
> [...]
> 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index ae017c032944..d2df21fde118 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> 
> [...]
> 
> > +static struct bpf_iarray *
> > +create_jt(int t, struct bpf_verifier_env *env, int fd)
>   		    	   		    	  ^^^^^^
> 				   This parameter is unused

Ah, yes, no more ->imm. Fixed.

> > +{
> > +	static struct bpf_subprog_info *subprog;
> > +	int subprog_start, subprog_end;
> > +	struct bpf_iarray *jt;
> > +	int i;
> > +
> > +	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 */
> > +	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]",
> > +					t, subprog_start, subprog_end);
> > +			return ERR_PTR(-EINVAL);
> > +		}
> > +	}
> > +
> > +	return jt;
> > +}
> 
> [...]
> 
> > +/* 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;
> > +	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;
> 
> Nit: we discussed this in v5, let's drop the verifier_bug_if() and
>      return -EINVAL?

So, I think this is a verifier bug. We've checked above that the
register is PTR_TO_INSN, so it must have map and map type should
be BPF_MAP_TYPE_INSN_ARRAY. Now this is always true, for future
I added these warnings, just in case. Wdyt?

>      > The program can be written in a way, such that e.g. hash map
>      > pointer is passed as a parameter for gotox, that would be an
>      > incorrect program, not a verifier bug.
> 
>      Also, use reg_type_str() instead of "type %d"?

This is map type, not register? Ah, you maybe meant the first
message, I will fix it, thanks.

> > +
> > +	err = indirect_jump_min_max_index(env, insn->dst_reg, map, &min_index, &max_index);
> > +	if (err)
> > +		return err;
> > +
> > +	/* Ensure that the buffer is large enough */
> > +	if (!env->gotox_tmp_buf || env->gotox_tmp_buf->cnt < max_index - min_index + 1) {
> > +		env->gotox_tmp_buf = iarray_realloc(env->gotox_tmp_buf,
> > +						    max_index - min_index + 1);
> > +		if (!env->gotox_tmp_buf)
> > +			return -ENOMEM;
> > +	}
> > +
> > +	n = copy_insn_array_uniq(map, min_index, max_index, env->gotox_tmp_buf->items);
> 
> Nit: let's not forget about a follow-up to remove this allocation.

Thanks, in the list of followups.

> > +	if (n < 0)
> > +		return n;
> > +	if (n == 0) {
> > +		verbose(env, "register R%d doesn't point to any offset in map id=%d\n",
> > +			     insn->dst_reg, map->id);
> > +		return -EINVAL;
> > +	}
> > +
> > +	for (i = 0; i < n - 1; i++) {
> > +		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
> > +					  env->insn_idx, env->cur_state->speculative);
> > +		if (IS_ERR(other_branch))
> > +			return PTR_ERR(other_branch);
> > +	}
> > +	env->insn_idx = env->gotox_tmp_buf->items[n-1];
> > +	return 0;
> > +}
> > +
> 
> [...]