Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning

[Alexei Starovoitov]

On 8/21/17 2:00 PM, Daniel Borkmann wrote:
> On 08/21/2017 10:44 PM, Edward Cree wrote:
> > On 21/08/17 21:27, Daniel Borkmann wrote:
> > > On 08/21/2017 08:36 PM, Edward Cree wrote:
> > > > On 19/08/17 00:37, Alexei Starovoitov wrote:
> > > [...]
> > > > I'm tempted to just rip out env->varlen_map_value_access and always
> > > > check
> > > >    the whole thing, because honestly I don't know what it was meant
> > > > to do
> > > >    originally or how it can ever do any useful pruning.  While
> > > > drastic, it
> > > >    does cause your test case to pass.
> > >
> > > Original intention from 484611357c19 ("bpf: allow access into map
> > > value arrays") was that it wouldn't potentially make pruning worse
> > > if PTR_TO_MAP_VALUE_ADJ was not used, meaning that we wouldn't need
> > > to take reg state's min_value and max_value into account for state
> > > checking; this was basically due to min_value / max_value is being
> > > adjusted/tracked on every alu/jmp ops for involved regs (e.g.
> > > adjust_reg_min_max_vals() and others that mangle them) even if we
> > > have the case that no actual dynamic map access is used throughout
> > > the program. To give an example on net tree, the bpf_lxc.o prog's
> > > section increases from 36,386 to 68,226 when
> > > env->varlen_map_value_access
> > > is always true, so it does have an effect. Did you do some checks
> > > on this on net-next?
> > I tested with the cilium progs and saw no change in insn count.  I
> >   suspect that for the normal case I already killed this optimisation
> >   when I did my unification patch, it was previously about ignoring
> >   min/max values on all regs (including scalars), whereas on net-next
> >   it only ignores them on map_value pointers; in practice this is
> >   useless because we tend to still have the offset scalar sitting in
> >   a register somewhere.  (Come to think of it, this may have been
> >   behind a large chunk of the #insn increase that my patches caused.)
>
> Yeah, this would seem plausible.
>
> > Since we use umax_value in find_good_pkt_pointers() now (to check
> >   against MAX_PACKET_OFF and ensure our reg->range is really ok), we
> >   can't just stop caring about all min/max values just because we
> >   haven't done any variable map accesses.
> > I don't see a way around this.
>
> Agree, was thinking the same. If there's not really a regression in
> terms of complexity, then lets kill the flag.

+1

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2489e67b65f6..908d13b2a2aa 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3582,7 +3582,7 @@ static int do_check(struct bpf_verifier_env *env)
        init_reg_state(regs);
        state->parent = NULL;
        insn_idx = 0;
-       env->varlen_map_value_access = false;
+       env->varlen_map_value_access = true;

makes _zero_ difference on cilium*.o tests, so let's just kill
that workaround.