On Fri, 2023-06-02 at 11:50 -0700, Andrii Nakryiko wrote:
[...]
> > > The thread is long. Could you please describe it again in pseudo code?
> >
> > - Add a function mark_precise_scalar_ids(struct bpf_verifier_env *env,
> > struct bpf_verifier_state *st)
> > such that it:
> > - collect PRECISE_IDS: a set of IDs of all registers marked in env->bt
> > - visit all registers with ids from PRECISE_IDS and make sure
> > that these registers are marked in env->bt
> > - Call mark_precise_scalar_ids() from __mark_chain_precision()
> > for each state 'st' visited by states chain processing loop,
> > so that:
> > - mark_precise_scalar_ids() is called for current state when
> > __mark_chain_precision() is entered, reusing id assignments in
> > current state;
> > - mark_precise_scalar_ids() is called for each parent state, reusing
> > id assignments valid at 'last_idx' instruction of that state.
> >
> > The idea is that in situations like below:
> >
> > 4: if (r6 > r7) goto +1
> > 5: r7 = r6
> > --- checkpoint #1 ---
> > 6: <something>
> > 7: if (r7 > X) goto ...
> > 8: r7 = 0
> > 9: r9 += r6
> >
> > The mark_precise_scalar_ids() would be called at:
> > - (9) and current id assignments would be used.
> > - (6) and id assignments saved in checkpoint #1 would be used.
> >
> > If <something> is the code that modifies r6/r7 the link would be
> > broken and we would overestimate the set of precise registers.
> >
>
> To avoid this we need to recalculate these IDs on each new parent
> state, based on requested precision marks. If we keep a simple and
> small array of IDs and do a quick linear search over them for each
> SCALAR register, I suspect it should be very fast. I don't think in
> practice we'll have more than 1-2 IDs in that array, right?
I'm not sure I understand, could you please describe how it should
work for e.g.?:
3: r6 &= 0xf // assume safe bound
4: if (r6 > r7) goto +1
5: r7 = r6
--- checkpoint #1 ---
6: r7 = 0
7: if (r7 > 10) goto exit;
8: r7 = 0
9: r9 += r6
__mark_chain_precision() would get to checkpoint #1 with only r6 as
precise, what should happen next?
As a side note: I added several optimizations:
- avoid allocation of scalar ids for constants;
- remove sole scalar ids from cached states;
- do a check as follows:
if (rold->precise && rold->id && !check_ids(idmap, rold, rcur))
return false;
And I'm seeing almost zero performance overhead now.
So, maybe what we figured so far is good enough.
Need to add more tests, though.
