[PATCH bpf-next 0/4] bpf: improve verifier state analysis

[PATCH bpf-next 0/4] bpf: improve verifier state analysis

[Alexei Starovoitov]

Several improvements to verifier state logic.
Patch 1 - trivial optimization
Patch 3 - significant optimization for stack state equivalence
Patch 4 - safety check for liveness and prep for future state merging

Alexei Starovoitov (4):
  bpf: speed up stacksafe check
  selftests/bpf: check insn processed in test_verifier
  bpf: improve stacksafe state comparison
  bpf: add self-check logic to liveness analysis

 include/linux/bpf_verifier.h                |   1 +
 kernel/bpf/verifier.c                       | 125 ++++++++++++++++++--
 tools/testing/selftests/bpf/test_verifier.c |  37 +++++-
 3 files changed, 154 insertions(+), 9 deletions(-)

-- 
2.17.1

[PATCH bpf-next 1/4] bpf: speed up stacksafe check

[Alexei Starovoitov]

don't check the same stack liveness condition 8 times.
once is enough.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8b511a4fe84a..d4db4727a50e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5147,9 +5147,11 @@ static bool stacksafe(struct bpf_func_state *old,
 	for (i = 0; i < old->allocated_stack; i++) {
 		spi = i / BPF_REG_SIZE;
 
-		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ))
+		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)) {
+			i += BPF_REG_SIZE - 1;
 			/* explored state didn't use this */
 			continue;
+		}
 
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;
-- 
2.17.1

[PATCH bpf-next 2/4] selftests/bpf: check insn processed in test_verifier

[Alexei Starovoitov]

teach test_verifier to parse verifier output for insn processed
and compare with expected number

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/testing/selftests/bpf/test_verifier.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index a08c67c8767e..82359cdbc805 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -76,7 +76,7 @@ struct bpf_test {
 	int fixup_percpu_cgroup_storage[MAX_FIXUPS];
 	const char *errstr;
 	const char *errstr_unpriv;
-	uint32_t retval, retval_unpriv;
+	uint32_t retval, retval_unpriv, insn_processed;
 	enum {
 		UNDEF,
 		ACCEPT,
@@ -14444,6 +14444,19 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
 		}
 	}
 
+	if (test->insn_processed) {
+		uint32_t insn_processed;
+		char *proc;
+
+		proc = strstr(bpf_vlog, "processed ");
+		insn_processed = atoi(proc + 10);
+		if (test->insn_processed != insn_processed) {
+			printf("FAIL\nUnexpected insn_processed %u vs %u\n",
+			       insn_processed, test->insn_processed);
+			goto fail_log;
+		}
+	}
+
 	if (fd_prog >= 0) {
 		__u8 tmp[TEST_DATA_LEN << 2];
 		__u32 size_tmp = sizeof(tmp);
-- 
2.17.1

[PATCH bpf-next 3/4] bpf: improve stacksafe state comparison

[Alexei Starovoitov]

if (old->allocated_stack > cur->allocated_stack) check is too conservative.
In some cases explored stack could have allocated more space,
but that stack space was not live.
The test case improves from 19 to 15 processed insns
and improvement on real programs is significant as well:

                       before    after
bpf_lb-DLB_L3.o        1940      1831
bpf_lb-DLB_L4.o        3089      3029
bpf_lb-DUNKNOWN.o      1065      1064
bpf_lxc-DDROP_ALL.o    28052     26309
bpf_lxc-DUNKNOWN.o     35487     33517
bpf_netdev.o           10864     9713
bpf_overlay.o          6643      6184
bpf_lcx_jit.o          38437     37335

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c                       | 13 ++++++------
 tools/testing/selftests/bpf/test_verifier.c | 22 +++++++++++++++++++++
 2 files changed, 29 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d4db4727a50e..6e5ea4c4d8e7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5134,12 +5134,6 @@ static bool stacksafe(struct bpf_func_state *old,
 {
 	int i, spi;
 
-	/* if explored stack has more populated slots than current stack
-	 * such stacks are not equivalent
-	 */
-	if (old->allocated_stack > cur->allocated_stack)
-		return false;
-
 	/* walk slots of the explored stack and ignore any additional
 	 * slots in the current stack, since explored(safe) state
 	 * didn't use them
@@ -5155,6 +5149,13 @@ static bool stacksafe(struct bpf_func_state *old,
 
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;
+
+		/* explored stack has more populated slots than current stack
+		 * and these slots were used
+		 */
+		if (i >= cur->allocated_stack)
+			return false;
+
 		/* if old state was safe with misc data in the stack
 		 * it will be safe with zero-initialized stack.
 		 * The opposite is not true
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 82359cdbc805..f9de7fe0c26d 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -13647,6 +13647,28 @@ static struct bpf_test tests[] = {
 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 		.result = ACCEPT,
 	},
+	{
+		"allocated_stack",
+		.insns = {
+			BPF_ALU64_REG(BPF_MOV, BPF_REG_6, BPF_REG_1),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
+			BPF_ALU64_REG(BPF_MOV, BPF_REG_7, BPF_REG_0),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 5),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -8),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, -8),
+			BPF_STX_MEM(BPF_B, BPF_REG_10, BPF_REG_7, -9),
+			BPF_LDX_MEM(BPF_B, BPF_REG_7, BPF_REG_10, -9),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.result_unpriv = ACCEPT,
+		.insn_processed = 15,
+	},
 	{
 		"reference tracking in call: free reference in subprog and outside",
 		.insns = {
-- 
2.17.1

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

[Alexei Starovoitov]

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>
---
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/verifier.c        | 108 ++++++++++++++++++++++++++++++++++-
 2 files changed, 108 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index c736945be7c5..07a55073c809 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -38,6 +38,7 @@ enum bpf_reg_liveness {
 	REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
 	REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
 	REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
+	REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
 };
 
 struct bpf_reg_state {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6e5ea4c4d8e7..9da0b3f8342a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -339,12 +339,14 @@ static char slot_type_char[] = {
 static void print_liveness(struct bpf_verifier_env *env,
 			   enum bpf_reg_liveness live)
 {
-	if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN))
+	if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN | REG_LIVE_DONE))
 	    verbose(env, "_");
 	if (live & REG_LIVE_READ)
 		verbose(env, "r");
 	if (live & REG_LIVE_WRITTEN)
 		verbose(env, "w");
+	if (live & REG_LIVE_DONE)
+		verbose(env, "D");
 }
 
 static struct bpf_func_state *func(struct bpf_verifier_env *env,
@@ -1074,6 +1076,12 @@ static int mark_reg_read(struct bpf_verifier_env *env,
 		/* if read wasn't screened by an earlier write ... */
 		if (writes && state->live & REG_LIVE_WRITTEN)
 			break;
+		if (parent->live & REG_LIVE_DONE) {
+			verbose(env, "verifier BUG type %s var_off %lld off %d\n",
+				reg_type_str[parent->type],
+				parent->var_off.value, parent->off);
+			return -EFAULT;
+		}
 		/* ... then we depend on parent's value */
 		parent->live |= REG_LIVE_READ;
 		state = parent;
@@ -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;
+		/* 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
+ */
+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;
-- 
2.17.1

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

[Edward Cree]

On 12/12/18 05:28, 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>
This feels a bit magic to me, relying as it does on seeing the state
 again in is_state_visited() after the last continuation is explored
 (rather than the marking happening as soon as the last exit is
 reached).
Also, why do you clean_live_states() in or after the states_equal()
 loop, rather than doing it (in just one place) before it?  AIUI, being
 in is_state_visited() already implies that all explored states are
 DONE, whether any of them match cur_state or not.

A different way I previously thought of was to have a refcount in
 verifier states (at the time we had a single parent rather than per-
 register parents) counting live children, that falls to 0 when all
 continuations have been walked.  That was something I did in my
 bounded loops RFC.
With something like that, we could check refcount != 0 in mark_reg_read
 and check refcount == 0 in explored states in is_state_visited.  Seems
 to me like that gets you the same thing and also adds the guarantee
 that our explored_states really are fully explored.

Rest of series looks good, have my Ack for patches 1-3.
(Though, maybe use a few more capital letters in your commit messages?)

-Ed

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

[Alexei Starovoitov]

On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote:
> On 12/12/18 05:28, 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>
> This feels a bit magic to me, relying as it does on seeing the state
>  again in is_state_visited() after the last continuation is explored
>  (rather than the marking happening as soon as the last exit is
>  reached).

what is "last exit" ?
Around 'process_bpf_exit' bit of code the verifier doesn't know which
state lists are not going to be changed.

> Also, why do you clean_live_states() in or after the states_equal()
>  loop, rather than doing it (in just one place) before it? 

true. can move the call to the beginning of is_state_visited().

> AIUI, being
>  in is_state_visited() already implies that all explored states are
>  DONE, whether any of them match cur_state or not.

Unfortunately not.
That's exactly the issue with liveness that I want to address
with this additional safety check.
For subprograms states_equal() checks callsite equivalence.
That's what is saving the existing liveness from producing incorrect
results.
The states in state lists of subprogs are still going to be changed.

> A different way I previously thought of was to have a refcount in
>  verifier states (at the time we had a single parent rather than per-
>  register parents) counting live children, that falls to 0 when all
>  continuations have been walked.  That was something I did in my
>  bounded loops RFC.
> With something like that, we could check refcount != 0 in mark_reg_read
>  and check refcount == 0 in explored states in is_state_visited.  Seems
>  to me like that gets you the same thing and also adds the guarantee
>  that our explored_states really are fully explored.

refcnt was my initial approach, but it needs to walk parentage chain.
Also push/pop_stack needs full walk of all chains too.
That is too expensive.
What kind of refcnt you had in mind?

> Rest of series looks good, have my Ack for patches 1-3.
> (Though, maybe use a few more capital letters in your commit messages?)

Meaning capitalize first letter of the sentences?

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

[Edward Cree]

On 12/12/18 22:00, Alexei Starovoitov wrote:
> On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote:
>> A different way I previously thought of was to have a refcount in
>>  verifier states (at the time we had a single parent rather than per-
>>  register parents) counting live children, that falls to 0 when all
>>  continuations have been walked.  That was something I did in my
>>  bounded loops RFC.
>> With something like that, we could check refcount != 0 in mark_reg_read
>>  and check refcount == 0 in explored states in is_state_visited.  Seems
>>  to me like that gets you the same thing and also adds the guarantee
>>  that our explored_states really are fully explored.
> refcnt was my initial approach, but it needs to walk parentage chain.
> Also push/pop_stack needs full walk of all chains too.
> That is too expensive.
> What kind of refcnt you had in mind?
Shallow, rather than deep, refcnt means that you only have to walk to the
 parent when your refcnt falls to zero.  push_stack never has to walk at
 all.  The refcnt only counts immediate children, not all descendants.
IIRC that's how I implemented it in my bounded loops RFC; see patch #9
 "bpf/verifier: count still-live children of explored_states" of that
 series.
Maybe it would still be too expensive, but I wonder if we should obtain
 numbers for that rather than guessing that it would or wouldn't.  Note
 that if a process_bpf_exit would walk N states dropping refs, then there
 are N states that would need to be marked DONE by your approach; and you
 re-do clean_live_states() for each one every time is_state_visited()
 comes back to the same insn, rather than just walking them once on exit.

>> Rest of series looks good, have my Ack for patches 1-3.
>> (Though, maybe use a few more capital letters in your commit messages?)
> Meaning capitalize first letter of the sentences?
Yes, that was what I meant.  (Also I think patch #2 is missing a full
 stop at the end of the sentence, but now I'm just being picky ;-)

-Ed

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

[Alexei Starovoitov]

On Wed, Dec 12, 2018 at 10:26:17PM +0000, Edward Cree wrote:
> On 12/12/18 22:00, Alexei Starovoitov wrote:
> > On Wed, Dec 12, 2018 at 08:58:33PM +0000, Edward Cree wrote:
> >> A different way I previously thought of was to have a refcount in
> >>  verifier states (at the time we had a single parent rather than per-
> >>  register parents) counting live children, that falls to 0 when all
> >>  continuations have been walked.  That was something I did in my
> >>  bounded loops RFC.
> >> With something like that, we could check refcount != 0 in mark_reg_read
> >>  and check refcount == 0 in explored states in is_state_visited.  Seems
> >>  to me like that gets you the same thing and also adds the guarantee
> >>  that our explored_states really are fully explored.
> > refcnt was my initial approach, but it needs to walk parentage chain.
> > Also push/pop_stack needs full walk of all chains too.
> > That is too expensive.
> > What kind of refcnt you had in mind?
> Shallow, rather than deep, refcnt means that you only have to walk to the
>  parent when your refcnt falls to zero.  push_stack never has to walk at
>  all.  The refcnt only counts immediate children, not all descendants.
> IIRC that's how I implemented it in my bounded loops RFC; see patch #9
>  "bpf/verifier: count still-live children of explored_states" of that
>  series.

luckily found it in my email archives. next time could you send a link to
make sure we're talking about the same patch?
back then there was no per-register chains and push_stack()
has to do only one live_children++.
With per-register it would need to walk all frames and all regs and
all stack slots.

Old kill_thread() instead of:
+       while (cur && !--cur->live_children)
+               cur = cur->parent;
becomes such inner loop for all frames, all regs and all slots, right?

I have to agree that it is easier to understand to do such kill_thread()
in process_bpf_exit, but the cost seems excessive for safety feature.

> Maybe it would still be too expensive, but I wonder if we should obtain
>  numbers for that rather than guessing that it would or wouldn't.  Note
>  that if a process_bpf_exit would walk N states dropping refs, then there
>  are N states that would need to be marked DONE by your approach; and you
>  re-do clean_live_states() for each one every time is_state_visited()
>  comes back to the same insn, rather than just walking them once on exit.

I can change clean_live_states() to be called only when equivalent state
is not found.
Since that's the place where I want to do state merging.
Since is_state_visited() just walked state lists and all data is hot,
it's the best place to walk them again either for safety check
or for state merging.

As far as state merging I see a pattern when a bunch of states are
overlapping in the register ranges, but not fully contained.
Essentially range_within() is too conservative.
The idea is to merge [1,5] with [3,10] if this is the only difference
between states. Merge, but don't declare it safe yet and proceed further.

To do any merging the verifier needs to be sure that reg_state is DONE.
Essentially the check of callsites with current state and whole idea
of this patch is a precursor of state merging.
I was thinking to enforce this safety first and keep it enforced,
but use clean_live_states() entry point and checks as a gate for
actual merging in the future patches.

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

[Jakub Kicinski]

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;

Re: [PATCH bpf-next 0/4] bpf: improve verifier state analysis

[Jakub Kicinski]

On Tue, 11 Dec 2018 21:28:50 -0800, Alexei Starovoitov wrote:
> Several improvements to verifier state logic.
> Patch 1 - trivial optimization
> Patch 3 - significant optimization for stack state equivalence
> Patch 4 - safety check for liveness and prep for future state merging

One possible optimization, but these seem correct to me.  FWIW:

Acked-by: Jakub Kicinski <jakub.kicinski@netronome.com>

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

[Alexei Starovoitov]

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

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.

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

[Edward Cree]

On 13/12/18 00:00, Alexei Starovoitov wrote:
> luckily found it in my email archives. next time could you send a link to
> make sure we're talking about the same patch?
Sorry, will do.

> back then there was no per-register chains and push_stack()
> has to do only one live_children++.
> With per-register it would need to walk all frames and all regs and
> all stack slots.
Thinking about it, since this is about control flow rather than data flow,
 maybe it makes sense to add in a separate parent pointer on the verifier
 state, and use that for this, rather than shoehorning it into the
 liveness machinery.

> Old kill_thread() instead of:
> +       while (cur && !--cur->live_children)
> +               cur = cur->parent;
> becomes such inner loop for all frames, all regs and all slots, right?
If it's done with the per-reg parent pointers, then yes that's right and
 that does start to look a bit painful, agreed.

> As far as state merging I see a pattern when a bunch of states are
> overlapping in the register ranges, but not fully contained.
> Essentially range_within() is too conservative.
> The idea is to merge [1,5] with [3,10] if this is the only difference
> between states. Merge, but don't declare it safe yet and proceed further.
Yep, makes sense.

-Ed