Merge branch 'bpf-verifier-fixes'

Edward Cree says:

====================
bpf: verifier fixes

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

v2: added test for write-marks bug (patch #1); reworded comment on
 propagate_liveness() for clarity.
====================

Signed-off-by: David S. Miller <davem@davemloft.net>

3 files changed, 103 insertions, 33 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 91d07efed2ba..b8d200f60a40 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 */
@@ -125,7 +138,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 e42c096ba20d..d690c7dd1f1a 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.
@@ -3433,9 +3417,16 @@ out_free:
         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)
 {
+        bool writes = parent == state->parent; /* Observe write marks */
         bool touched = false; /* any changes made? */
         int i;
 
@@ -3447,7 +3438,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;
                 }
@@ -3460,7 +3453,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;
                 }
@@ -3468,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",
+ * though it requires that parent != state->parent in the call arguments.
+ */
 static void propagate_liveness(const struct bpf_verifier_state *state,
                                struct bpf_verifier_state *parent)
 {
@@ -3496,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;
@@ -3519,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++)
@@ -3550,7 +3565,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;
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index c03542c417db..353d17015641 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -6487,6 +6487,50 @@ static struct bpf_test tests[] = {
                 .result = REJECT,
                 .prog_type = BPF_PROG_TYPE_LWT_IN,
         },
+        {
+                "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,
+        },
+        {
+                "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)