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

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

On 25/10/02 12:52PM, Eduard Zingerman wrote:
> On Thu, 2025-10-02 at 09:27 +0000, Anton Protopopov wrote:
> 
> [...]
> 
> > > > @@ -14685,6 +14723,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
> > > >  				dst);
> > > >  			return -EACCES;
> > > >  		}
> > > > +		if (ptr_to_insn_array) {
> > > > +			verbose(env, "R%d subtraction from pointer to instruction prohibited\n",
> > > > +				dst);
> > > > +			return -EACCES;
> > > > +		}
> > > 
> > > Is anything going to break if subtraction is allowed?
> > > The bounds are still maintained, so seem to be ok.
> > 
> > Ok, I just haven't seen any reason to add because such code
> > is not generated on practice. I will add in the next version.
> 
> Just less code and less tests if there is no special case.
> 
> [...]
> 
> > > > @@ -17786,6 +17830,210 @@ static struct bpf_iarray *iarray_realloc(struct bpf_iarray *old, size_t n_elem)
> > > >  	return new;
> > > >  }
> > > >  
> > > > +#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;
> > > > +
> > > 
> > > push_insn() checks if `t` is in range [0, env->prog->len],
> > > is the same check needed here?
> > 
> > You wanted to say `w`? (I think `t` is guaranteed to be a valid one.)
> > In cas of push_gotox_edge `w` is taken from a jump table which is
> > guaranteed to have only correct instructions.
> 
> Yes, I meant `w`, sorry.
> So, the invalid offsets would be rejected at map construction time?
> I'd put a check here just to be consistent with push_insn, but skip it
> if you think it's not really necessary.

I will add a check for consistency.

> [...]
> 
> > > > +static struct bpf_iarray *
> > > > +create_jt(int t, struct bpf_verifier_env *env, int fd)
> > > > +{
> > > > +	static struct bpf_subprog_info *subprog;
> > > > +	int subprog_idx, subprog_start, subprog_end;
> > > > +	struct bpf_iarray *jt;
> > > > +	int i;
> > > > +
> > > > +	if (env->subprog_cnt == 0)
> > > > +		return ERR_PTR(-EFAULT);
> > > > +
> > > > +	subprog_idx = bpf_find_containing_subprog_idx(env, t);
> > > > +	if (subprog_idx < 0) {
> > > > +		verbose(env, "can't find subprog containing instruction %d\n", t);
> > > > +		return ERR_PTR(-EFAULT);
> > > > +	}
> > > 
> > > Nit: There is now verifier_bug() for such cases.
> > >      Also, it seems that all bpf_find_containing_subprog() users
> > >      assume that the function can't fail.
> > >      Like in this case, there is already access `jt = env->insn_aux_data[t].jt;`
> > >      in visit_gotox_insn() that will be an error if `t` is bogus.
> > 
> > Could you please explain this once again? The error from
> > bpf_find_containing_subprog* funcs is checked in this code.
> 
> Point being that there is no need to check if bpf_find_containing_subprog()
> returns error:
> - If we guarantee that `t` is within program bounds it can't fail
>   (which I think we do).  In other places where this function is
>   called it's return value is not checked for errors.
> - In case if we don't guarantee that `t` is within program bounds,
>   then just before call to create_jt() there is an access `jt =
>   env->insn_aux_data[t].jt;` which would read from some undefined
>   location. So, it's already too late to check here.

Ah, ok, I see, thanks.

> [...]
> 
> > >   /* "conditional jump with N edges" */
> > >   static int visit_gotox_insn(int t, struct bpf_verifier_env *env, int fd)
> > >   {
> > >         int *insn_stack = env->cfg.insn_stack;
> > >         int *insn_state = env->cfg.insn_state;
> > >         bool keep_exploring = false;
> > >         struct bpf_iarray *jt;
> > >         int i, w;
> > > 
> > >         jt = env->insn_aux_data[t].jt;
> > >         if (!jt) {
> > >                 jt = create_jt(t, env, fd);
> > >                 if (IS_ERR(ptr: jt))
> > 
> > (BTW, out of curiosity, do these "ptr: jt" type hints and alike
> > come from your environment? What is it, if this is not a secret?)
> 
> Oh... sorry about that, I'll suppress those moving forward.
> It's a copy-paste from tmux window.
> In tmux there is a terminal running emacs in console mode.
> Emacs uses eglot mode to integrate with clangd language server.
> Eglot displays these parameter name hints, provided by clangd.
> The whole thing ends up in copy-paste because in console mode all of
> this is just text. Had I run emacs in gui mode, it wouldn't be
> copy-pasted. But that's a remote machine, so here were are.

Thanks for the explanations. (Also, no problem if this appears.)

> [...]
> 
> > > > +static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > > > +{
> 
> [...]
> 
> > > > +	n = copy_insn_array_uniq(map, min_index, max_index, env->gotox_tmp_buf);
> > > 
> > > I still think this might be a problem for big jump tables if gotox is
> > > in a loop body. Can you check a perf report for such scenario?
> > > E.g. 256 entries in the jump table, some duplicates, dispatched in a loop.
> > 
> > Well, for "big jump tables" I want to follow up with some changes in any case,
> > just didn't get there with this patchset yet. Namely, the `insn_inxed \mapto
> > jump table map` must be optimized, otherwise the JIT spends too much time on
> > this. So, this would require bin/serach or better a hash to optimize this. In
> > the latter case, this piece might also be optimized by caching a lookup
> > (by the "map[start,end]" key).
> 
> Ok, if follow-up is planned, we can stick with a simple implementation
> for this patch.
> 
> [...]