[PATCH net-next 0/4] bpf: verifier fixes

[PATCH net-next 0/4] bpf: verifier fixes

[Edward Cree]

Fix a couple of bugs introduced in my recent verifier patches.
Patch #3 does slightly increase the insn count on bpf_lxc.o, but only by
 about a hundred insns (i.e. 0.2%).

Alexei Starovoitov (1):
  selftests/bpf: add a test for a pruning bug in the verifier

Edward Cree (3):
  bpf/verifier: remove varlen_map_value_access flag
  bpf/verifier: when pruning a branch, ignore its write marks
  bpf/verifier: document liveness analysis

 include/linux/bpf_verifier.h                | 14 +++++-
 kernel/bpf/verifier.c                       | 78 +++++++++++++++++------------
 tools/testing/selftests/bpf/test_verifier.c | 28 +++++++++++
 3 files changed, 87 insertions(+), 33 deletions(-)

[PATCH net-next 1/4] selftests/bpf: add a test for a pruning bug in the verifier

[Edward Cree via iovisor-dev]

From: Alexei Starovoitov <ast-b10kYP2dOMg@public.gmane.org>

The test makes a read through a map value pointer, then considers pruning
 a branch where the register holds an adjusted map value pointer.  It
 should not prune, but currently it does.

Signed-off-by: Alexei Starovoitov <ast-b10kYP2dOMg@public.gmane.org>
[ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org: added test-name and patch description]
Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
---
 tools/testing/selftests/bpf/test_verifier.c | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index c03542c..6ca1487 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -6487,6 +6487,34 @@ static struct bpf_test tests[] = {
 		.result = REJECT,
 		.prog_type = BPF_PROG_TYPE_LWT_IN,
 	},
+	{
+		"varlen_map_value_access pruning",
+		.insns = {
+			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+			BPF_LD_MAP_FD(BPF_REG_1, 0),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_map_lookup_elem),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+			BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
+			BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
+			BPF_MOV32_IMM(BPF_REG_1, 0),
+			BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
+			BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 0),
+			BPF_ST_MEM(BPF_DW, BPF_REG_0, 0,
+				   offsetof(struct test_val, foo)),
+			BPF_EXIT_INSN(),
+		},
+		.fixup_map2 = { 3 },
+		.errstr_unpriv = "R0 leaks addr",
+		.errstr = "R0 unbounded memory access",
+		.result_unpriv = REJECT,
+		.result = REJECT,
+		.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
+	}, 
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)

[PATCH net-next 2/4] bpf/verifier: remove varlen_map_value_access flag

[Edward Cree via iovisor-dev]

The optimisation it does is broken when the 'new' register value has a
 variable offset and the 'old' was constant.  I broke it with my pointer
 types unification (see Fixes tag below), before which the 'new' value
 would have type PTR_TO_MAP_VALUE_ADJ and would thus not compare equal;
 other changes in that patch mean that its original behaviour (ignore
 min/max values) cannot be restored.
Tests on a sample set of cilium programs show no change in count of
 processed instructions.

Fixes: f1174f77b50c ("bpf/verifier: rework value tracking")
Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
---
 include/linux/bpf_verifier.h |  1 -
 kernel/bpf/verifier.c        | 41 ++++++++++++-----------------------------
 2 files changed, 12 insertions(+), 30 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 91d07ef..d8f131a 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -125,7 +125,6 @@ struct bpf_verifier_env {
 	u32 id_gen;			/* used to generate unique reg IDs */
 	bool allow_ptr_leaks;
 	bool seen_direct_write;
-	bool varlen_map_value_access;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 };
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e42c096..1e3f56c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -832,11 +832,6 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno,
 	 */
 	if (log_level)
 		print_verifier_state(state);
-	/* If the offset is variable, we will need to be stricter in state
-	 * pruning from now on.
-	 */
-	if (!tnum_is_const(reg->var_off))
-		env->varlen_map_value_access = true;
 	/* The minimum value is only important with signed
 	 * comparisons where we can't assume the floor of a
 	 * value is 0.  If we are using signed variables for our
@@ -3247,9 +3242,8 @@ static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap)
 }
 
 /* Returns true if (rold safe implies rcur safe) */
-static bool regsafe(struct bpf_reg_state *rold,
-		    struct bpf_reg_state *rcur,
-		    bool varlen_map_access, struct idpair *idmap)
+static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
+		    struct idpair *idmap)
 {
 	if (!(rold->live & REG_LIVE_READ))
 		/* explored state didn't use this */
@@ -3281,22 +3275,14 @@ static bool regsafe(struct bpf_reg_state *rold,
 			       tnum_is_unknown(rold->var_off);
 		}
 	case PTR_TO_MAP_VALUE:
-		if (varlen_map_access) {
-			/* If the new min/max/var_off satisfy the old ones and
-			 * everything else matches, we are OK.
-			 * We don't care about the 'id' value, because nothing
-			 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
-			 */
-			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
-			       range_within(rold, rcur) &&
-			       tnum_in(rold->var_off, rcur->var_off);
-		} else {
-			/* If the ranges/var_off were not the same, but
-			 * everything else was and we didn't do a variable
-			 * access into a map then we are a-ok.
-			 */
-			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0;
-		}
+		/* If the new min/max/var_off satisfy the old ones and
+		 * everything else matches, we are OK.
+		 * We don't care about the 'id' value, because nothing
+		 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
+		 */
+		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
+		       range_within(rold, rcur) &&
+		       tnum_in(rold->var_off, rcur->var_off);
 	case PTR_TO_MAP_VALUE_OR_NULL:
 		/* a PTR_TO_MAP_VALUE could be safe to use as a
 		 * PTR_TO_MAP_VALUE_OR_NULL into the same map.
@@ -3380,7 +3366,6 @@ static bool states_equal(struct bpf_verifier_env *env,
 			 struct bpf_verifier_state *old,
 			 struct bpf_verifier_state *cur)
 {
-	bool varlen_map_access = env->varlen_map_value_access;
 	struct idpair *idmap;
 	bool ret = false;
 	int i;
@@ -3391,8 +3376,7 @@ static bool states_equal(struct bpf_verifier_env *env,
 		return false;
 
 	for (i = 0; i < MAX_BPF_REG; i++) {
-		if (!regsafe(&old->regs[i], &cur->regs[i], varlen_map_access,
-			     idmap))
+		if (!regsafe(&old->regs[i], &cur->regs[i], idmap))
 			goto out_free;
 	}
 
@@ -3412,7 +3396,7 @@ static bool states_equal(struct bpf_verifier_env *env,
 			continue;
 		if (!regsafe(&old->spilled_regs[i / BPF_REG_SIZE],
 			     &cur->spilled_regs[i / BPF_REG_SIZE],
-			     varlen_map_access, idmap))
+			     idmap))
 			/* when explored and current stack slot are both storing
 			 * spilled registers, check that stored pointers types
 			 * are the same as well.
@@ -3550,7 +3534,6 @@ 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;
 	for (;;) {
 		struct bpf_insn *insn;
 		u8 class;

Re: [PATCH net-next 2/4] bpf/verifier: remove varlen_map_value_access flag

[Alexei Starovoitov via iovisor-dev]

On 8/22/17 6:26 AM, Edward Cree wrote:
> The optimisation it does is broken when the 'new' register value has a
>  variable offset and the 'old' was constant.  I broke it with my pointer
>  types unification (see Fixes tag below), before which the 'new' value
>  would have type PTR_TO_MAP_VALUE_ADJ and would thus not compare equal;
>  other changes in that patch mean that its original behaviour (ignore
>  min/max values) cannot be restored.
> Tests on a sample set of cilium programs show no change in count of
>  processed instructions.
>
> Fixes: f1174f77b50c ("bpf/verifier: rework value tracking")
> Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>

Acked-by: Alexei Starovoitov <ast-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>

[PATCH net-next 4/4] bpf/verifier: document liveness analysis

[Edward Cree via iovisor-dev]

The liveness tracking algorithm is quite subtle; add comments to explain it.

Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
---
 include/linux/bpf_verifier.h | 13 +++++++++++++
 kernel/bpf/verifier.c        | 28 +++++++++++++++++++++++++++-
 2 files changed, 40 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index d8f131a..b8d200f 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -21,6 +21,19 @@
  */
 #define BPF_MAX_VAR_SIZ	INT_MAX
 
+/* Liveness marks, used for registers and spilled-regs (in stack slots).
+ * Read marks propagate upwards until they find a write mark; they record that
+ * "one of this state's descendants read this reg" (and therefore the reg is
+ * relevant for states_equal() checks).
+ * Write marks collect downwards and do not propagate; they record that "the
+ * straight-line code that reached this state (from its parent) wrote this reg"
+ * (and therefore that reads propagated from this state or its descendants
+ * should not propagate to its parent).
+ * A state with a write mark can receive read marks; it just won't propagate
+ * them to its parent, since the write mark is a property, not of the state,
+ * but of the link between it and its parent.  See mark_reg_read() and
+ * mark_stack_slot_read() in kernel/bpf/verifier.c.
+ */
 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 */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 711bdbd..5fc350e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3417,6 +3417,12 @@ static bool states_equal(struct bpf_verifier_env *env,
 	return ret;
 }
 
+/* A write screens off any subsequent reads; but write marks come from the
+ * straight-line code between a state and its parent.  When we arrive at a
+ * jump target (in the first iteration of the propagate_liveness() loop),
+ * we didn't arrive by the straight-line code, so read marks in state must
+ * propagate to parent regardless of state's write marks.
+ */
 static bool do_propagate_liveness(const struct bpf_verifier_state *state,
 				  struct bpf_verifier_state *parent)
 {
@@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
 	return touched;
 }
 
+/* "parent" is "a state from which we reach the current state", but initially
+ * it is not the state->parent (i.e. "the state whose straight-line code leads
+ * to the current state"), instead it is the state that happened to arrive at
+ * a (prunable) equivalent of the current state.  See comment above
+ * do_propagate_liveness() for consequences of this.
+ * This function is just a more efficient way of calling mark_reg_read() or
+ * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
+ * long as parent != state->parent.
+ */
 static void propagate_liveness(const struct bpf_verifier_state *state,
 			       struct bpf_verifier_state *parent)
 {
@@ -3485,6 +3500,12 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			/* reached equivalent register/stack state,
 			 * prune the search.
 			 * Registers read by the continuation are read by us.
+			 * If we have any write marks in env->cur_state, they
+			 * will prevent corresponding reads in the continuation
+			 * from reaching our parent (an explored_state).  Our
+			 * own state will get the read marks recorded, but
+			 * they'll be immediately forgotten as we're pruning
+			 * this state and will pop a new one.
 			 */
 			propagate_liveness(&sl->state, &env->cur_state);
 			return 1;
@@ -3508,7 +3529,12 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	env->explored_states[insn_idx] = new_sl;
 	/* connect new state to parentage chain */
 	env->cur_state.parent = &new_sl->state;
-	/* clear liveness marks in current state */
+	/* clear write marks in current state: the writes we did are not writes
+	 * our child did, so they don't screen off its reads from us.
+	 * (There are no read marks in current state, because reads always mark
+	 * their parent and current state never has children yet.  Only
+	 * explored_states can get read marks.)
+	 */
 	for (i = 0; i < BPF_REG_FP; i++)
 		env->cur_state.regs[i].live = REG_LIVE_NONE;
 	for (i = 0; i < MAX_BPF_STACK / BPF_REG_SIZE; i++)

Re: [PATCH net-next 4/4] bpf/verifier: document liveness analysis

[Alexei Starovoitov]

On 8/22/17 6:27 AM, Edward Cree wrote:
> The liveness tracking algorithm is quite subtle; add comments to explain it.
>
> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
>  include/linux/bpf_verifier.h | 13 +++++++++++++
>  kernel/bpf/verifier.c        | 28 +++++++++++++++++++++++++++-
>  2 files changed, 40 insertions(+), 1 deletion(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index d8f131a..b8d200f 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -21,6 +21,19 @@
>   */
>  #define BPF_MAX_VAR_SIZ	INT_MAX
>
> +/* Liveness marks, used for registers and spilled-regs (in stack slots).
> + * Read marks propagate upwards until they find a write mark; they record that
> + * "one of this state's descendants read this reg" (and therefore the reg is
> + * relevant for states_equal() checks).
> + * Write marks collect downwards and do not propagate; they record that "the
> + * straight-line code that reached this state (from its parent) wrote this reg"
> + * (and therefore that reads propagated from this state or its descendants
> + * should not propagate to its parent).
> + * A state with a write mark can receive read marks; it just won't propagate
> + * them to its parent, since the write mark is a property, not of the state,
> + * but of the link between it and its parent.  See mark_reg_read() and
> + * mark_stack_slot_read() in kernel/bpf/verifier.c.
> + */

+1

>  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 */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 711bdbd..5fc350e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3417,6 +3417,12 @@ static bool states_equal(struct bpf_verifier_env *env,
>  	return ret;
>  }
>
> +/* A write screens off any subsequent reads; but write marks come from the
> + * straight-line code between a state and its parent.  When we arrive at a
> + * jump target (in the first iteration of the propagate_liveness() loop),
> + * we didn't arrive by the straight-line code, so read marks in state must
> + * propagate to parent regardless of state's write marks.
> + */

+1

>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>  				  struct bpf_verifier_state *parent)
>  {
> @@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>  	return touched;
>  }
>
> +/* "parent" is "a state from which we reach the current state", but initially
> + * it is not the state->parent (i.e. "the state whose straight-line code leads
> + * to the current state"), instead it is the state that happened to arrive at
> + * a (prunable) equivalent of the current state.  See comment above
> + * do_propagate_liveness() for consequences of this.
> + * This function is just a more efficient way of calling mark_reg_read() or
> + * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
> + * long as parent != state->parent.
> + */

i'm confused with 'so long as parent != state->parent' which implies
looping and multiple iterations, whereas 'parent != state->parent'
condition is true only for the first iteration of
'while (do_propagate_liveness(state, parent))' loop.
right ?

>  static void propagate_liveness(const struct bpf_verifier_state *state,
>  			       struct bpf_verifier_state *parent)
>  {
> @@ -3485,6 +3500,12 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  			/* reached equivalent register/stack state,
>  			 * prune the search.
>  			 * Registers read by the continuation are read by us.
> +			 * If we have any write marks in env->cur_state, they
> +			 * will prevent corresponding reads in the continuation
> +			 * from reaching our parent (an explored_state).  Our
> +			 * own state will get the read marks recorded, but
> +			 * they'll be immediately forgotten as we're pruning
> +			 * this state and will pop a new one.
>  			 */

+1

>  			propagate_liveness(&sl->state, &env->cur_state);
>  			return 1;
> @@ -3508,7 +3529,12 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  	env->explored_states[insn_idx] = new_sl;
>  	/* connect new state to parentage chain */
>  	env->cur_state.parent = &new_sl->state;
> -	/* clear liveness marks in current state */
> +	/* clear write marks in current state: the writes we did are not writes
> +	 * our child did, so they don't screen off its reads from us.
> +	 * (There are no read marks in current state, because reads always mark
> +	 * their parent and current state never has children yet.  Only
> +	 * explored_states can get read marks.)
> +	 */

+1

>  	for (i = 0; i < BPF_REG_FP; i++)
>  		env->cur_state.regs[i].live = REG_LIVE_NONE;
>  	for (i = 0; i < MAX_BPF_STACK / BPF_REG_SIZE; i++)
>

Re: [PATCH net-next 4/4] bpf/verifier: document liveness analysis

[Edward Cree]

On 22/08/17 16:42, Alexei Starovoitov wrote:
> On 8/22/17 6:27 AM, Edward Cree wrote:
>>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>                    struct bpf_verifier_state *parent)
>>  {
>> @@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>      return touched;
>>  }
>>
>> +/* "parent" is "a state from which we reach the current state", but initially
>> + * it is not the state->parent (i.e. "the state whose straight-line code leads
>> + * to the current state"), instead it is the state that happened to arrive at
>> + * a (prunable) equivalent of the current state.  See comment above
>> + * do_propagate_liveness() for consequences of this.
>> + * This function is just a more efficient way of calling mark_reg_read() or
>> + * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
>> + * long as parent != state->parent.
>> + */
>
> i'm confused with 'so long as parent != state->parent' which implies
> looping and multiple iterations, whereas 'parent != state->parent'
> condition is true only for the first iteration of
> 'while (do_propagate_liveness(state, parent))' loop.
> right ?
I phrased it badly.  I mean that, the statement "this function is just a
 way to mark_reg_read() all the things" is true only "so long as" (i.e.
 under the condition) parent != state->parent.
How about
/* This function is just a more efficient way of calling mark_reg_read() or
 * mark_stack_slot_read() on each reg in "parent" that is read in "state",
 * though it requires that parent != state->parent in the call arguments.
 */
?

Re: [PATCH net-next 4/4] bpf/verifier: document liveness analysis

[Alexei Starovoitov]

On 8/22/17 8:55 AM, Edward Cree wrote:
> On 22/08/17 16:42, Alexei Starovoitov wrote:
>> On 8/22/17 6:27 AM, Edward Cree wrote:
>>>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>>                    struct bpf_verifier_state *parent)
>>>  {
>>> @@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>>      return touched;
>>>  }
>>>
>>> +/* "parent" is "a state from which we reach the current state", but initially
>>> + * it is not the state->parent (i.e. "the state whose straight-line code leads
>>> + * to the current state"), instead it is the state that happened to arrive at
>>> + * a (prunable) equivalent of the current state.  See comment above
>>> + * do_propagate_liveness() for consequences of this.
>>> + * This function is just a more efficient way of calling mark_reg_read() or
>>> + * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
>>> + * long as parent != state->parent.
>>> + */
>>
>> i'm confused with 'so long as parent != state->parent' which implies
>> looping and multiple iterations, whereas 'parent != state->parent'
>> condition is true only for the first iteration of
>> 'while (do_propagate_liveness(state, parent))' loop.
>> right ?
> I phrased it badly.  I mean that, the statement "this function is just a
>  way to mark_reg_read() all the things" is true only "so long as" (i.e.
>  under the condition) parent != state->parent.

got it.

> How about
> /* This function is just a more efficient way of calling mark_reg_read() or
>  * mark_stack_slot_read() on each reg in "parent" that is read in "state",
>  * though it requires that parent != state->parent in the call arguments.
>  */

Thanks. It's more clear to me. Ack

[PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

[Edward Cree]

The fact that writes occurred in reaching the continuation state does
 not screen off its reads from us, because we're not really its parent.
So detect 'not really the parent' in do_propagate_liveness, and ignore
 write marks in that case.

Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 kernel/bpf/verifier.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1e3f56c..711bdbd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
 static bool do_propagate_liveness(const struct bpf_verifier_state *state,
 				  struct bpf_verifier_state *parent)
 {
+	bool writes = parent == state->parent; /* Observe write marks */
 	bool touched = false; /* any changes made? */
 	int i;
 
@@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
 	for (i = 0; i < BPF_REG_FP; i++) {
 		if (parent->regs[i].live & REG_LIVE_READ)
 			continue;
-		if (state->regs[i].live == REG_LIVE_READ) {
+		if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
+			continue;
+		if (state->regs[i].live & REG_LIVE_READ) {
 			parent->regs[i].live |= REG_LIVE_READ;
 			touched = true;
 		}
@@ -3444,7 +3447,9 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
 			continue;
 		if (parent->spilled_regs[i].live & REG_LIVE_READ)
 			continue;
-		if (state->spilled_regs[i].live == REG_LIVE_READ) {
+		if (writes && (state->spilled_regs[i].live & REG_LIVE_WRITTEN))
+			continue;
+		if (state->spilled_regs[i].live & REG_LIVE_READ) {
 			parent->spilled_regs[i].live |= REG_LIVE_READ;
 			touched = true;
 		}

Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

[Alexei Starovoitov via iovisor-dev]

On 8/22/17 6:27 AM, Edward Cree wrote:
> The fact that writes occurred in reaching the continuation state does
>  not screen off its reads from us, because we're not really its parent.
> So detect 'not really the parent' in do_propagate_liveness, and ignore
>  write marks in that case.
>
> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
> Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
> ---
>  kernel/bpf/verifier.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 1e3f56c..711bdbd 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>  				  struct bpf_verifier_state *parent)
>  {
> +	bool writes = parent == state->parent; /* Observe write marks */
>  	bool touched = false; /* any changes made? */
>  	int i;
>
> @@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>  	for (i = 0; i < BPF_REG_FP; i++) {
>  		if (parent->regs[i].live & REG_LIVE_READ)
>  			continue;
> -		if (state->regs[i].live == REG_LIVE_READ) {
> +		if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
> +			continue;
> +		if (state->regs[i].live & REG_LIVE_READ) {

makes sense to me.
if i understand correctly it not only should make the liveness marking
correct, but improve the numbers, since smaller number of states
will have READ marks.
Do you have a test case for this by any chance?

Acked-by: Alexei Starovoitov <ast-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>

Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

[Edward Cree via iovisor-dev]

On 22/08/17 16:24, Alexei Starovoitov wrote:
> On 8/22/17 6:27 AM, Edward Cree wrote:
>> The fact that writes occurred in reaching the continuation state does
>>  not screen off its reads from us, because we're not really its parent.
>> So detect 'not really the parent' in do_propagate_liveness, and ignore
>>  write marks in that case.
>>
>> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
>> Signed-off-by: Edward Cree <ecree-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
>> ---
>>  kernel/bpf/verifier.c | 9 +++++++--
>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 1e3f56c..711bdbd 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>                    struct bpf_verifier_state *parent)
>>  {
>> +    bool writes = parent == state->parent; /* Observe write marks */
>>      bool touched = false; /* any changes made? */
>>      int i;
>>
>> @@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>      for (i = 0; i < BPF_REG_FP; i++) {
>>          if (parent->regs[i].live & REG_LIVE_READ)
>>              continue;
>> -        if (state->regs[i].live == REG_LIVE_READ) {
>> +        if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
>> +            continue;
>> +        if (state->regs[i].live & REG_LIVE_READ) {
>
> makes sense to me.
> if i understand correctly it not only should make the liveness marking
> correct, but improve the numbers, since smaller number of states
> will have READ marks.
Other way round; it means we sometimes ignore WRITTEN marks, so more states
 get READ marks.  On the cilium progs, the bpf_lxc.o get about 100 extra
 insns processed, the others are unchanged.
> Do you have a test case for this by any chance?
I haven't constructed one; my test was just to put in some debug code that
 checked on each propagate_liveness call whether there were any write marks
 in the first state.
I think something like
    if (cond)
        r0=0;
    if (cond)
        r0=0;
    return r0;
might tickle the bug, but I'm not sure.

Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

[Edward Cree]

On 22/08/17 16:50, Edward Cree wrote:
> On 22/08/17 16:24, Alexei Starovoitov wrote:
>> Do you have a test case for this by any chance?
> I think something like
>     if (cond)
>         r0=0;
>     if (cond)
>         r0=0;
>     return r0;
> might tickle the bug, but I'm not sure.
It turns out that (cond) has to be constructed not to alter our knowledge
 of whatever register we're testing, but apart from that, this works.
    {
        "liveness pruning and write screening",
        .insns = {
            /* Get an unknown value */
            BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
            /* branch conditions teach us nothing about R2 */
            BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
            BPF_MOV64_IMM(BPF_REG_0, 0),
            BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
            BPF_MOV64_IMM(BPF_REG_0, 0),
            BPF_EXIT_INSN(),
        },
        .errstr = "R0 !read_ok",
        .result = REJECT,
        .prog_type = BPF_PROG_TYPE_LWT_IN,
    },
This test fails on net-next, but passes with my patch.
I'll include it in the next spin of the series.

Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

[Alexei Starovoitov via iovisor-dev]

On 8/22/17 11:03 AM, Edward Cree wrote:
> On 22/08/17 16:50, Edward Cree wrote:
>> On 22/08/17 16:24, Alexei Starovoitov wrote:
>>> Do you have a test case for this by any chance?
>> I think something like
>>     if (cond)
>>         r0=0;
>>     if (cond)
>>         r0=0;
>>     return r0;
>> might tickle the bug, but I'm not sure.
> It turns out that (cond) has to be constructed not to alter our knowledge
>  of whatever register we're testing, but apart from that, this works.
>     {
>         "liveness pruning and write screening",
>         .insns = {
>             /* Get an unknown value */
>             BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
>             /* branch conditions teach us nothing about R2 */
>             BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
>             BPF_MOV64_IMM(BPF_REG_0, 0),
>             BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
>             BPF_MOV64_IMM(BPF_REG_0, 0),
>             BPF_EXIT_INSN(),
>         },
>         .errstr = "R0 !read_ok",
>         .result = REJECT,
>         .prog_type = BPF_PROG_TYPE_LWT_IN,
>     },
> This test fails on net-next, but passes with my patch.
> I'll include it in the next spin of the series.

nice. thanks for the test!