bpf: add self-check logic to liveness analysis

Introduce REG_LIVE_DONE to check the liveness propagation
and prepare the states for merging.
See algorithm description in clean_live_states().

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>

1 files changed, 107 insertions, 1 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e4724fe8120f..0125731e2512 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -397,12 +397,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,
@@ -1132,6 +1134,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;
@@ -5078,6 +5086,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;
+                /* 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;
+                /* 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;
+
+        if (st->frame[0]->regs[0].live & REG_LIVE_DONE)
+                /* all regs in this state in all frames were already marked */
+                return;
+
+        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)
@@ -5396,6 +5500,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                  */
                 return 0;
 
+        clean_live_states(env, insn_idx, cur);
+
         while (sl != STATE_LIST_MARK) {
                 if (states_equal(env, &sl->state, cur)) {
                         /* reached equivalent register/stack state,