Re: [PATCH bpf-next 4/4] bpf: add self-check logic to liveness analysis

[Jakub Kicinski <jakub.kicinski@netronome.com>]

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 <ast@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?

> +		/* 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... 

> +static void clean_live_states(struct bpf_verifier_env *env, int insn,
> +			      struct bpf_verifier_state *cur)
> +{
> +	struct bpf_verifier_state_list *sl;
> +	int i;
> +
> +	sl = env->explored_states[insn];
> +	if (!sl)
> +		return;
> +
> +	while (sl != STATE_LIST_MARK) {
> +		if (sl->state.curframe != cur->curframe)
> +			goto next;
> +		for (i = 0; i <= cur->curframe; i++)
> +			if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
> +				goto next;
> +		clean_verifier_state(env, &sl->state);
> +next:
> +		sl = sl->next;
> +	}
> +}
> +
>  /* Returns true if (rold safe implies rcur safe) */
>  static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
>  		    struct idpair *idmap)
> @@ -5354,11 +5458,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  			err = propagate_liveness(env, &sl->state, cur);
>  			if (err)
>  				return err;
> +			clean_live_states(env, insn_idx, cur);
>  			return 1;
>  		}
>  		sl = sl->next;
>  		states_cnt++;
>  	}
> +	clean_live_states(env, insn_idx, cur);
>  
>  	if (!env->allow_ptr_leaks && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)
>  		return 0;