[PATCH bpf-next 1/4] bpf: Mark pending sub-register zero extension before pruning a state

[Daniel Borkmann <daniel@iogearbox.net>]

A 32-bit write records the writing instruction in reg->subreg_def, and a
later 64-bit read of that register calls mark_insn_zext() to record that
the definition has to be zero extended. Architectures whose JIT sets
bpf_jit_needs_zext() rely on that mark to emit the extension.

The mark is produced by walking the path from the definition to the read.
If the walk stops at a state equivalent to an already explored one, the
reads the explored path performs from there on are not repeated for this
path's registers, so a definition whose only 64-bit read lies beyond the
pruning point never gets marked and keeps a garbage upper half.

Example with BPF_F_TEST_STATE_FREQ making every instruction a checkpoint:

      r7 = *(u32 *)(r1 + offsetof(struct __sk_buff, len))
      r6 = 0        /* 64-bit define */
      if r7 != 0 goto l1
      goto l0                              path A, explored first
  l1: w6 = 0        /* 32-bit define */    path B, explored second
  l0: r0 = r6       /* 64-bit read   */
      r0 >>= 32
      exit

Now, path A is the fall-through of the conditional and is explored first.
It reaches l0 with r6 defined by the 64-bit r6 = 0, so reg->subreg_def is
DEF_NOT_SUBREG and the read marks nothing. The walk runs on to exit and
leaves a checkpoint at every instruction along the way. Path B is explored
second. w6 = 0 sets r6->subreg_def to that instruction, so a zero extension
is pending and only the 64-bit read at l0 can resolve it. B then arrives
at l0, where bpf_is_state_visited() finds the checkpoint A left behind:
r6 is the scalar 0 in both states, so they are equivalent and B is pruned
before r0 = r6 is verified.

Without the fix nothing happens at that point, so the one read that would
have called mark_insn_zext() for w6 is never walked and the definition
stays unmarked:

  l1: w6 = 0        /* subreg_def = w6, pending */
  l0: r0 = r6     <--- B pruned, read never walked, w6 stays unmarked

The JIT of an architecture that needs explicit zero extension then emits
none, and the upper half of w6's definition is left undefined (under
BPF_F_TEST_RND_HI32 it holds the randomized half, which r0 >>= 32 returns).
This used to be handled by the registers chain based liveness: the
propagate_liveness() called mark_insn_zext() for every parent register
whose read mark was REG_LIVE_READ64, which carried the requirement across
a pruned state. Commit 107e16979905 ("bpf: disable and remove registers
chain based liveness") removed that machinery and with it the propagation,
leaving the mark dependent on the path actually being walked.

Mark the pending definitions where the walk stops instead, i.e. on the way
into the prune rather than at the read that is no longer reached:

  l1: w6 = 0        /* subreg_def = w6, pending */
  l0: r0 = r6     <--- mark w6, r6 is live here

The set of registers to mark is the one the pruning decision was made on:
func_states_equal() compares the registers live at the instruction, per
insn_aux_data[].live_regs_before, and those are exactly the registers that
can still be read. A register that is not live there is never read again
and needs nothing. This is conservative in one direction: a live register
whose remaining reads are all 32-bit also gets its definition marked,
which costs a zero extension that is not needed. However, it never marks
too little, and it does not weaken pruning. On x86-64 the effect is only
observable with BPF_F_TEST_RND_HI32.

The one live scalar whose subreg_def can point at a call insn is r0 of a
kfunc returning a 32-bit value. Marking that one is harmless, the fixup pass
skips kfunc calls since their zero extension is done by the caller.

Fixes: 107e16979905 ("bpf: disable and remove registers chain based liveness")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h |  2 ++
 kernel/bpf/states.c          |  2 ++
 kernel/bpf/verifier.c        | 38 ++++++++++++++++++++++++++++++++++++
 3 files changed, 42 insertions(+)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index a2a40caca0a0..0952fa5649db 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1212,6 +1212,8 @@ void bpf_clear_singular_ids(struct bpf_verifier_env *env, struct bpf_verifier_st
 int bpf_mark_chain_precision(struct bpf_verifier_env *env,
 			     struct bpf_verifier_state *starting_state,
 			     int regno, bool *changed);
+void bpf_mark_live_subregs_zext(struct bpf_verifier_env *env,
+				struct bpf_verifier_state *vstate);
 
 static inline int bpf_get_spi(s32 off)
 {
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index ea2153cf28d0..24009a606249 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1405,6 +1405,8 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 hit:
 			sl->hit_cnt++;
 
+			bpf_mark_live_subregs_zext(env, cur);
+
 			/* if previous state reached the exit with precision and
 			 * current state is equivalent to it (except precision marks)
 			 * the precision needs to be propagated back in
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 09588b7b08b0..e62b350b37af 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3161,6 +3161,44 @@ static void mark_insn_zext(struct bpf_verifier_env *env,
 	reg->subreg_def = DEF_NOT_SUBREG;
 }
 
+/*
+ * Reaching a state equivalent to an already explored one stops the walk, so a
+ * register that still carries a subreg_def may have its only 64-bit read on
+ * the path that is no longer walked, and without the mark the JIT of an
+ * architecture that needs explicit zero extension leaves the upper half of the
+ * definition undefined. Mark the definitions of the registers live at this
+ * instruction, i.e. the ones the equivalence was decided on and thus the only
+ * ones that can still be read. This is conservative in that a live register
+ * which is only ever read as a sub-register also gets its definition marked,
+ * at the cost of a zero extension that is not needed.
+ *
+ * Only scalars are considered since a live_regs_before bit does not imply that
+ * the register holds a readable value: the caller saved regs of a frame below
+ * the current one are clobbered to NOT_INIT at the call while keeping the
+ * subreg_def of the call insn. Such a definition must not be marked, the call
+ * insn has no destination register to zero extend.
+ */
+void bpf_mark_live_subregs_zext(struct bpf_verifier_env *env,
+				struct bpf_verifier_state *vstate)
+{
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
+	struct bpf_func_state *func;
+	u16 live_regs;
+	int i, j;
+
+	for (i = vstate->curframe; i >= 0; i--) {
+		live_regs = aux[bpf_frame_insn_idx(vstate, i)].live_regs_before;
+		func = vstate->frame[i];
+		for (j = 0; j < BPF_REG_FP; j++) {
+			if (!(live_regs & BIT(j)))
+				continue;
+			if (func->regs[j].type != SCALAR_VALUE)
+				continue;
+			mark_insn_zext(env, &func->regs[j]);
+		}
+	}
+}
+
 static int __check_reg_arg(struct bpf_verifier_env *env, struct bpf_reg_state *regs, u32 regno,
 			   enum bpf_reg_arg_type t)
 {
-- 
2.43.0