On Wed, Dec 12, 2018 at 05:21:35PM -0800, Jakub Kicinski wrote:
> On Tue, 11 Dec 2018 21:28:54 -0800, Alexei Starovoitov wrote:
> > introduce REG_LIVE_DONE to check the liveness propagation
> > and prepare the states for merging
> > See algorithm description in clean_live_states().
> > No difference in tests.
> >
> > Signed-off-by: Alexei Starovoitov <a...@kernel.org>
>
> > @@ -5021,6 +5029,102 @@ static bool check_ids(u32 old_id, u32 cur_id,
> > struct idpair *idmap)
> > return false;
> > }
> >
> > +static void clean_func_state(struct bpf_verifier_env *env,
> > + struct bpf_func_state *st)
> > +{
> > + enum bpf_reg_liveness live;
> > + int i, j;
> > +
> > + for (i = 0; i < BPF_REG_FP; i++) {
> > + live = st->regs[i].live;
> > + if (live & REG_LIVE_DONE)
> > + continue;
>
> Perhaps return; here? Seeing any "done" flag in the state entry
> implies all regs and stack slots are "done", no? Or even check if
> there are any DONE flags in clean_verifier_state() before the loop?
good idea. will do.
> > + /* liveness must not touch this register anymore */
> > + st->regs[i].live |= REG_LIVE_DONE;
> > + if (!(live & REG_LIVE_READ))
> > + /* since the register is unused, clear its state
> > + * to make further comparison simpler
> > + */
> > + __mark_reg_not_init(&st->regs[i]);
> > + }
> > +
> > + for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) {
> > + live = st->stack[i].spilled_ptr.live;
> > + if (live & REG_LIVE_DONE)
> > + continue;
> > + /* liveness must not touch this stack slot anymore */
> > + st->stack[i].spilled_ptr.live |= REG_LIVE_DONE;
> > + if (!(live & REG_LIVE_READ)) {
> > + __mark_reg_not_init(&st->stack[i].spilled_ptr);
> > + for (j = 0; j < BPF_REG_SIZE; j++)
> > + st->stack[i].slot_type[j] = STACK_INVALID;
> > + }
> > + }
> > +}
> > +
> > +static void clean_verifier_state(struct bpf_verifier_env *env,
> > + struct bpf_verifier_state *st)
> > +{
> > + int i;
> > +
> > + for (i = 0; i <= st->curframe; i++)
> > + clean_func_state(env, st->frame[i]);
> > +}
> > +
> > +/* the parentage chains form a tree.
> > + * the verifier states are added to state lists at given insn and
> > + * pushed into state stack for future exploration.
> > + * when the verifier reaches bpf_exit insn some of the verifer states
> > + * stored in the state lists have their final liveness state already,
> > + * but a lot of states will get revised from liveness point of view when
> > + * the verifier explores other branches.
> > + * Example:
> > + * 1: r0 = 1
> > + * 2: if r1 == 100 goto pc+1
> > + * 3: r0 = 2
> > + * 4: exit
> > + * when the verifier reaches exit insn the register r0 in the state list of
> > + * insn 2 will be seen as !REG_LIVE_READ. Then the verifier pops the
> > other_branch
> > + * of insn 2 and goes exploring further. At the insn 4 it will walk the
> > + * parentage chain from insn 4 into insn 2 and will mark r0 as
> > REG_LIVE_READ.
> > + *
> > + * Since the verifier pushes the branch states as it sees them while
> > exploring
> > + * the program the condition of walking the branch instruction for the
> > second
> > + * time means that all states below this branch were already explored and
> > + * their final liveness markes are already propagated.
> > + * Hence when the verifier completes the search of state list in
> > is_state_visited()
> > + * we can call this clean_live_states() function to mark all liveness
> > states
> > + * as REG_LIVE_DONE to indicate that 'parent' pointers of 'struct
> > bpf_reg_state'
> > + * will not be used.
> > + * This function also clears the registers and stack for states that !READ
> > + * to simplify state merging.
> > + *
> > + * Important note here that walking the same branch instruction in the
> > callee
> > + * doesn't meant that the states are DONE. The verifier has to compare
> > + * the callsites
> > + */
>
> Little bike shedding - if I understand Ed's comment I feel the same way
> about "any state we see must be fully done". Different call sites are
> logically different state lists in my mind, we effectively "inline" the
> functions in the verifier walk...
yes, they are logically different, but implementation is only one state
list per insn. So comparing callsites is the "filter" of logical lists.
