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

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2025-08-28 at 09:58 +0000, Anton Protopopov wrote:

[...]

> > > @@ -16943,7 +17016,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > >  		}
> > >  		dst_reg->type = PTR_TO_MAP_VALUE;
> > >  		dst_reg->off = aux->map_off;
> > > -		WARN_ON_ONCE(map->max_entries != 1);
> > > +		WARN_ON_ONCE(map->map_type != BPF_MAP_TYPE_INSN_ARRAY &&
> > > +			     map->max_entries != 1);
> > 
> > Q: when is this necessary?
> 
> For all maps except INSN_ARRAY only (map->max_entries == 1) is
> allowed. This change adds an exception for INSN_ARRAY.

I see, thank you for explaining.

[...]

> > > +static int cmp_ptr_to_u32(const void *a, const void *b)
> > > +{
> > > +	return *(u32 *)a - *(u32 *)b;
> > > +}
> > 
> > This will overflow for e.g. `0 - 8`.
> 
> Why? 0U - 8U = 0xfffffff8U (it's not an UB because values are
> unsigned).  Then it's cast to int on return which is -8.

Uh-oh. Ok, looks like this works.

[...]

> > > +static int jt_from_subprog(struct bpf_verifier_env *env,
> > > +			   int subprog_start,
> > > +			   int subprog_end,
> > > +			   struct jt *jt)
> > > +{
> > > +	struct bpf_map *map;
> > > +	struct jt jt_cur;
> > > +	u32 *off;
> > > +	int err;
> > > +	int i;
> > > +
> > > +	jt->off = NULL;
> > > +	jt->off_cnt = 0;
> > > +
> > > +	for (i = 0; i < env->insn_array_map_cnt; i++) {
> > > +		/*
> > > +		 * TODO (when needed): collect only jump tables, not static keys
> > > +		 * or maps for indirect calls
> > > +		 */
> > > +		map = env->insn_array_maps[i];
> > > +
> > > +		err = jt_from_map(map, &jt_cur);
> > > +		if (err) {
> > > +			kvfree(jt->off);
> > > +			return err;
> > > +		}
> > > +
> > > +		/*
> > > +		 * This is enough to check one element. The full table is
> > > +		 * checked to fit inside the subprog later in create_jt()
> > > +		 */
> > > +		if (jt_cur.off[0] >= subprog_start && jt_cur.off[0] < subprog_end) {
> > 
> > This won't always catch cases when insn array references offsets from
> > several subprograms. Also is one subprogram limitation really necessary?
> 
> This was intentional. If you have a switch or a jump table
> defined in C, then corresponding jump tables belong to one function.
> Also, what if you have a jt which can jump from function f() to g(),
> but then g() is livepatched by another function?

Ok, yes, for gotox such limitation makes sense.

[...]

> > > @@ -18679,6 +19000,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:
> > > +		/* cur ⊆ old */
> > 
> > Out of curiosity: are unicode symbols allowed in kernel source code?
> 
> I've replaced with words, don't see other examples of unicode around
> (but also can't find "don't use unicode" in coding-style.rst).

Personally, I like unicode symbols :)

> > > +		return (rcur->min_index >= rold->min_index &&
> > > +			rcur->max_index <= rold->max_index);
> > >  	default:
> > >  		return regs_exact(rold, rcur, idmap);
> > >  	}
> > > @@ -19825,6 +20150,67 @@ static int process_bpf_exit_full(struct bpf_verifier_env *env,
> > >  	return PROCESS_BPF_EXIT;
> > >  }
> > >  
> > > +/* gotox *dst_reg */
> > > +static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > > +{

[...]

> > > +	if (dst_reg->max_index >= map->max_entries) {
> > > +		verbose(env, "BPF_JA|BPF_X R%d is out of map boundaries: index=%u, max_index=%u\n",
> > > +				insn->dst_reg, dst_reg->max_index, map->max_entries-1);
> > > +		return -EINVAL;
> > > +	}
> > > +
> > > +	xoff = kvcalloc(dst_reg->max_index - dst_reg->min_index + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
> > > +	if (!xoff)
> > > +		return -ENOMEM;
> > > +
> > > +	n = copy_insn_array_uniq(map, dst_reg->min_index, dst_reg->max_index, xoff);
> > 
> > Nit: I'd avoid this allocation and do a loop for(i = min_index; i <= max_index; i++),
> >      with map->ops->map_lookup_elem(map, &i) (or a wrapper) inside it.
> 
> But it should be a list of unique values, how would you sort it
> without allocating memory (in a reqsonable time)?

Because of the push_state() loop below, right?
Makes sense.

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

[...]