[PATCH bpf-next v2 0/3] bpf: track find_equal_scalars history on per-instruction level

[PATCH bpf-next v2 0/3] bpf: track find_equal_scalars history on per-instruction level

[Eduard Zingerman]

This is a fix for precision tracking bug reported in [0].
It supersedes my previous attempt to fix similar issue in commit [1].
Here is a minimized test case from [0]:

    0:  call bpf_get_prandom_u32;
    1:  r7 = r0;
    2:  r8 = r0;
    3:  call bpf_get_prandom_u32;
    4:  if r0 > 1 goto +0;
    /* --- checkpoint #1: r7.id=1, r8.id=1 --- */
    5:  if r8 >= r0 goto 9f;
    6:  r8 += r8;
    /* --- checkpoint #2: r7.id=1, r8.id=0 --- */
    7:  if r7 == 0 goto 9f;
    8:  r0 /= 0;
    /* --- checkpoint #3 --- */
    9:  r0 = 42;
    10: exit;

W/o this fix verifier incorrectly assumes that instruction at label
(8) is unreachable. The issue is caused by failure to infer
precision mark for r0 at checkpoint #1:
- first verification path is:
  - (0-4): r0 range [0,1];
  - (5): r8 range [0,0], propagated to r7;
  - (6): r8.id is reset;
  - (7): jump is predicted to happen;
  - (9-10): safe exit.
- when jump at (7) is predicted mark_chain_precision() for r7 is
  called and backtrack_insn() proceeds as follows:
  - at (7) r7 is marked as precise;
  - at (5) r8 is not currently tracked and thus r0 is not marked;
  - at (4-5) boundary logic from [1] is triggered and r7,r8 are marked
    as precise;
  - => r0 precision mark is missed.
- when second branch of (4) is considered, verifier prunes the state
  because r0 is not marked as precise in the visited state.

Basically, backtracking logic fails to notice that at (5)
range information is gained for both r7 and r8, and thus both
r8 and r0 have to be marked as precise.
This happens because [1] can only account for such range
transfers at parent/child state boundaries.

The solution suggested by Andrii Nakryiko in [0] is to use jump
history to remember which registers gained range as a result of
find_equal_scalars() and use this information in backtrack_insn().
Which is what this patch-set does.

The patch-set uses u64 value as a vector of 10-bit values that
identify registers gaining range in find_equal_scalars().
This amounts to maximum of 6 possible values.
To check if such capacity is sufficient I've instrumented kernel
to track a histogram for maximal amount of registers that gain range
in find_equal_scalars per program verification [2].
Measurements done for verifier selftests and Cilium bpf object files
from [3] show that number of such registers is *always* <= 4 and
in 98% of cases it is <= 2.

When tested on a subset of selftests identified by
selftests/bpf/veristat.cfg and Cilium bpf object files from [3]
this patch-set has minimal verification performance impact:

File                      Program                   Insns   (DIFF)  States (DIFF)
------------------------  ------------------------  --------------  -------------
bpf_host.o                tail_handle_nat_fwd_ipv4    -75 (-0.61%)    -3 (-0.39%)
pyperf600_nounroll.bpf.o  on_event                  +1673 (+0.33%)    +3 (+0.01%)


[0] https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
[1] commit 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")
[2] https://github.com/eddyz87/bpf/tree/find-equal-scalars-in-jump-history-with-stats
[3] https://github.com/anakryiko/cilium

Changes:
- v1 -> v2:
  - patch "bpf: replace env->cur_hist_ent with a getter function" is
    dropped (Andrii);
  - added structure linked_regs and helper functions to [de]serialize
    u64 value as such structure (Andrii);
  - bt_set_equal_scalars() renamed to bt_sync_linked_regs(), moved to
    start and end of backtrack_insn() in order to untie linked
    register logic from conditional jumps backtracking.
    Andrii requested a more radical change of moving linked registers
    processing to bt_set_xxx() functions, I did an experiment in this
    direction:
    https://github.com/eddyz87/bpf/tree/find-equal-scalars-in-jump-history--linked-regs-in-bt-set-reg
    the end result of the experiment seems much uglier than version
    presented in v2.

Revisions:
- v1: https://lore.kernel.org/bpf/20240222005005.31784-1-eddyz87@gmail.com/

Eduard Zingerman (3):
  bpf: track find_equal_scalars history on per-instruction level
  bpf: remove mark_precise_scalar_ids()
  selftests/bpf: tests for per-insn find_equal_scalars() precision
    tracking

 include/linux/bpf_verifier.h                  |   4 +
 kernel/bpf/verifier.c                         | 346 +++++++++++-------
 .../selftests/bpf/progs/verifier_scalar_ids.c | 256 +++++++++----
 .../bpf/progs/verifier_subprog_precision.c    |   2 +-
 .../testing/selftests/bpf/verifier/precise.c  |  28 +-
 5 files changed, 416 insertions(+), 220 deletions(-)

-- 
2.45.2

[PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Eduard Zingerman]

Use bpf_verifier_state->jmp_history to track which registers were
updated by find_equal_scalars() when conditional jump was verified.
Use recorded information in backtrack_insn() to propagate precision.

E.g. for the following program:

            while verifying instructions
  r1 = r0              |
  if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
  if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history
  r2 = r10             |
  r2 += r0             v mark_chain_precision(r0)

            while doing mark_chain_precision(r0)
  r1 = r0              ^
  if r1 < 8  goto ...  | mark r0,r1 as precise
  if r0 > 16 goto ...  | mark r0,r1 as precise
  r2 = r10             |
  r2 += r0             | mark r0 precise

Technically, achieve this as follows:
- Use 10 bits to identify each register that gains range because of
  find_equal_scalars():
  - 3 bits for frame number;
  - 6 bits for register or stack slot number;
  - 1 bit to indicate if register is spilled.
- Use u64 as a vector of 6 such records + 4 bits for vector length.
- Augment struct bpf_jmp_history_entry with field 'linked_regs'
  representing such vector.
- When doing check_cond_jmp_op() remember up to 6 registers that
  gain range because of find_equal_scalars() in such a vector.
- Don't propagate range information and reset IDs for registers that
  don't fit in 6-value vector.
- Push a pair {instruction index, equal scalars vector}
  to bpf_verifier_state->jmp_history.
- When doing backtrack_insn() check if any of recorded linked
  registers is currently marked precise, if so mark all linked
  registers as precise.

This also requires fixes for two test_verifier tests:
- precise: test 1
- precise: test 2

Both tests contain the following instruction sequence:

19: (bf) r2 = r9                      ; R2=scalar(id=3) R9=scalar(id=3)
20: (a5) if r2 < 0x8 goto pc+1        ; R2=scalar(id=3,umin=8)
21: (95) exit
22: (07) r2 += 1                      ; R2_w=scalar(id=3+1,...)
23: (bf) r1 = r10                     ; R1_w=fp0 R10=fp0
24: (07) r1 += -8                     ; R1_w=fp-8
25: (b7) r3 = 0                       ; R3_w=0
26: (85) call bpf_probe_read_kernel#113

The call to bpf_probe_read_kernel() at (26) forces r2 to be precise.
Previously, this forced all registers with same id to become precise
immediately when mark_chain_precision() is called.
After this change, the precision is propagated to registers sharing
same id only when 'if' instruction is backtracked.
Hence verification log for both tests is changed:
regs=r2,r9 -> regs=r2 for instructions 25..20.

Fixes: 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")
Reported-by: Hao Sun <sunhao.th@gmail.com>
Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
Suggested-by: Andrii Nakryiko <andrii@kernel.org>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h                  |   4 +
 kernel/bpf/verifier.c                         | 231 ++++++++++++++++--
 .../bpf/progs/verifier_subprog_precision.c    |   2 +-
 .../testing/selftests/bpf/verifier/precise.c  |  20 +-
 4 files changed, 232 insertions(+), 25 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 2b54e25d2364..da450552c278 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -371,6 +371,10 @@ struct bpf_jmp_history_entry {
 	u32 prev_idx : 22;
 	/* special flags, e.g., whether insn is doing register stack spill/load */
 	u32 flags : 10;
+	/* additional registers that need precision tracking when this
+	 * jump is backtracked, vector of six 10-bit records
+	 */
+	u64 linked_regs;
 };
 
 /* Maximum number of register states that can exist at once */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e25ad5fb9115..ec493360607e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3335,9 +3335,87 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
 	return env->insn_aux_data[insn_idx].jmp_point;
 }
 
+#define ES_FRAMENO_BITS	3
+#define ES_SPI_BITS	6
+#define ES_ENTRY_BITS	(ES_SPI_BITS + ES_FRAMENO_BITS + 1)
+#define ES_SIZE_BITS	4
+#define ES_FRAMENO_MASK	((1ul << ES_FRAMENO_BITS) - 1)
+#define ES_SPI_MASK	((1ul << ES_SPI_BITS)     - 1)
+#define ES_SIZE_MASK	((1ul << ES_SIZE_BITS)    - 1)
+#define ES_SPI_OFF	ES_FRAMENO_BITS
+#define ES_IS_REG_OFF	(ES_SPI_BITS + ES_FRAMENO_BITS)
+#define LINKED_REGS_MAX	6
+
+struct reg_or_spill {
+	u8 frameno:3;
+	union {
+		u8 spi:6;
+		u8 regno:6;
+	};
+	bool is_reg:1;
+};
+
+struct linked_regs {
+	int cnt;
+	struct reg_or_spill entries[LINKED_REGS_MAX];
+};
+
+static struct reg_or_spill *linked_regs_push(struct linked_regs *s)
+{
+	if (s->cnt < LINKED_REGS_MAX)
+		return &s->entries[s->cnt++];
+
+	return NULL;
+}
+
+/* Use u64 as a vector of 6 10-bit values, use first 4-bits to track
+ * number of elements currently in stack.
+ * Pack one history entry for equal scalars as 10 bits in the following format:
+ * - 3-bits frameno
+ * - 6-bits spi_or_reg
+ * - 1-bit  is_reg
+ */
+static u64 linked_regs_pack(struct linked_regs *s)
+{
+	u64 val = 0;
+	int i;
+
+	for (i = 0; i < s->cnt; ++i) {
+		struct reg_or_spill *e = &s->entries[i];
+		u64 tmp = 0;
+
+		tmp |= e->frameno;
+		tmp |= e->spi << ES_SPI_OFF;
+		tmp |= (e->is_reg ? 1 : 0) << ES_IS_REG_OFF;
+
+		val <<= ES_ENTRY_BITS;
+		val |= tmp;
+	}
+	val <<= ES_SIZE_BITS;
+	val |= s->cnt;
+	return val;
+}
+
+static void linked_regs_unpack(u64 val, struct linked_regs *s)
+{
+	int i;
+
+	s->cnt = val & ES_SIZE_MASK;
+	val >>= ES_SIZE_BITS;
+
+	for (i = 0; i < s->cnt; ++i) {
+		struct reg_or_spill *e = &s->entries[i];
+
+		e->frameno =  val & ES_FRAMENO_MASK;
+		e->spi     = (val >> ES_SPI_OFF) & ES_SPI_MASK;
+		e->is_reg  = (val >> ES_IS_REG_OFF) & 0x1;
+		val >>= ES_ENTRY_BITS;
+	}
+}
+
 /* for any branch, call, exit record the history of jmps in the given state */
 static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
-			    int insn_flags)
+			    int insn_flags, u64 linked_regs)
 {
 	u32 cnt = cur->jmp_history_cnt;
 	struct bpf_jmp_history_entry *p;
@@ -3353,6 +3431,10 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
 			  "verifier insn history bug: insn_idx %d cur flags %x new flags %x\n",
 			  env->insn_idx, env->cur_hist_ent->flags, insn_flags);
 		env->cur_hist_ent->flags |= insn_flags;
+		WARN_ONCE(env->cur_hist_ent->linked_regs != 0,
+			  "verifier insn history bug: insn_idx %d linked_regs != 0: %#llx\n",
+			  env->insn_idx, env->cur_hist_ent->linked_regs);
+		env->cur_hist_ent->linked_regs = linked_regs;
 		return 0;
 	}
 
@@ -3367,6 +3449,7 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
 	p->idx = env->insn_idx;
 	p->prev_idx = env->prev_insn_idx;
 	p->flags = insn_flags;
+	p->linked_regs = linked_regs;
 	cur->jmp_history_cnt = cnt;
 	env->cur_hist_ent = p;
 
@@ -3532,6 +3615,11 @@ static inline bool bt_is_reg_set(struct backtrack_state *bt, u32 reg)
 	return bt->reg_masks[bt->frame] & (1 << reg);
 }
 
+static inline bool bt_is_frame_reg_set(struct backtrack_state *bt, u32 frame, u32 reg)
+{
+	return bt->reg_masks[frame] & (1 << reg);
+}
+
 static inline bool bt_is_frame_slot_set(struct backtrack_state *bt, u32 frame, u32 slot)
 {
 	return bt->stack_masks[frame] & (1ull << slot);
@@ -3576,6 +3664,42 @@ static void fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask)
 	}
 }
 
+/* If any register R in hist->linked_regs is marked as precise in bt,
+ * do bt_set_frame_{reg,slot}(bt, R) for all registers in hist->linked_regs.
+ */
+static void bt_sync_linked_regs(struct backtrack_state *bt, struct bpf_jmp_history_entry *hist)
+{
+	struct linked_regs linked_regs;
+	bool some_precise = false;
+	int i;
+
+	if (!hist || hist->linked_regs == 0)
+		return;
+
+	linked_regs_unpack(hist->linked_regs, &linked_regs);
+	for (i = 0; i < linked_regs.cnt; ++i) {
+		struct reg_or_spill *e = &linked_regs.entries[i];
+
+		if ((e->is_reg && bt_is_frame_reg_set(bt, e->frameno, e->regno)) ||
+		    (!e->is_reg && bt_is_frame_slot_set(bt, e->frameno, e->spi))) {
+			some_precise = true;
+			break;
+		}
+	}
+
+	if (!some_precise)
+		return;
+
+	for (i = 0; i < linked_regs.cnt; ++i) {
+		struct reg_or_spill *e = &linked_regs.entries[i];
+
+		if (e->is_reg)
+			bt_set_frame_reg(bt, e->frameno, e->regno);
+		else
+			bt_set_frame_slot(bt, e->frameno, e->spi);
+	}
+}
+
 static bool calls_callback(struct bpf_verifier_env *env, int insn_idx);
 
 /* For given verifier state backtrack_insn() is called from the last insn to
@@ -3615,6 +3739,12 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 		print_bpf_insn(&cbs, insn, env->allow_ptr_leaks);
 	}
 
+	/* If there is a history record that some registers gained range at this insn,
+	 * propagate precision marks to those registers, so that bt_is_reg_set()
+	 * accounts for these registers.
+	 */
+	bt_sync_linked_regs(bt, hist);
+
 	if (class == BPF_ALU || class == BPF_ALU64) {
 		if (!bt_is_reg_set(bt, dreg))
 			return 0;
@@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 			 */
 			bt_set_reg(bt, dreg);
 			bt_set_reg(bt, sreg);
+		} else if (BPF_SRC(insn->code) == BPF_K) {
 			 /* else dreg <cond> K
 			  * Only dreg still needs precision before
 			  * this insn, so for the K-based conditional
@@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 			/* to be analyzed */
 			return -ENOTSUPP;
 	}
+	/* Propagate precision marks to linked registers, to account for
+	 * registers marked as precise in this function.
+	 */
+	bt_sync_linked_regs(bt, hist);
 	return 0;
 }
 
@@ -4624,7 +4759,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 	}
 
 	if (insn_flags)
-		return push_jmp_history(env, env->cur_state, insn_flags);
+		return push_jmp_history(env, env->cur_state, insn_flags, 0);
 	return 0;
 }
 
@@ -4929,7 +5064,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
 		insn_flags = 0; /* we are not restoring spilled register */
 	}
 	if (insn_flags)
-		return push_jmp_history(env, env->cur_state, insn_flags);
+		return push_jmp_history(env, env->cur_state, insn_flags, 0);
 	return 0;
 }
 
@@ -15154,14 +15289,66 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 	return true;
 }
 
-static void find_equal_scalars(struct bpf_verifier_state *vstate,
-			       struct bpf_reg_state *known_reg)
+static void __find_equal_scalars(struct linked_regs *reg_set, struct bpf_reg_state *reg,
+				 u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)
+{
+	struct reg_or_spill *e;
+
+	if (reg->type != SCALAR_VALUE || (reg->id & ~BPF_ADD_CONST) != id)
+		return;
+
+	e = linked_regs_push(reg_set);
+	if (e) {
+		e->frameno = frameno;
+		e->is_reg = is_reg;
+		e->regno = spi_or_reg;
+	} else {
+		reg->id = 0;
+	}
+}
+
+/* For all R being scalar registers or spilled scalar registers
+ * in verifier state, save R in linked_regs if R->id == id.
+ * If there are too many Rs sharing same id, reset id for leftover Rs.
+ */
+static void find_equal_scalars(struct bpf_verifier_state *vstate, u32 id,
+			       struct linked_regs *linked_regs)
+{
+	struct bpf_func_state *func;
+	struct bpf_reg_state *reg;
+	int i, j;
+
+	id = id & ~BPF_ADD_CONST;
+	for (i = vstate->curframe; i >= 0; i--) {
+		func = vstate->frame[i];
+		for (j = 0; j < BPF_REG_FP; j++) {
+			reg = &func->regs[j];
+			__find_equal_scalars(linked_regs, reg, id, i, j, true);
+		}
+		for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
+			if (!is_spilled_reg(&func->stack[j]))
+				continue;
+			reg = &func->stack[j].spilled_ptr;
+			__find_equal_scalars(linked_regs, reg, id, i, j, false);
+		}
+	}
+}
+
+/* For all R in linked_regs, copy known_reg range into R
+ * if R->id == known_reg->id.
+ */
+static void copy_known_reg(struct bpf_verifier_state *vstate, struct bpf_reg_state *known_reg,
+			   struct linked_regs *linked_regs)
 {
 	struct bpf_reg_state fake_reg;
-	struct bpf_func_state *state;
 	struct bpf_reg_state *reg;
+	struct reg_or_spill *e;
+	int i;
 
-	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
+	for (i = 0; i < linked_regs->cnt; ++i) {
+		e = &linked_regs->entries[i];
+		reg = e->is_reg ? &vstate->frame[e->frameno]->regs[e->regno]
+				: &vstate->frame[e->frameno]->stack[e->spi].spilled_ptr;
 		if (reg->type != SCALAR_VALUE || reg == known_reg)
 			continue;
 		if ((reg->id & ~BPF_ADD_CONST) != (known_reg->id & ~BPF_ADD_CONST))
@@ -15187,7 +15374,7 @@ static void find_equal_scalars(struct bpf_verifier_state *vstate,
 			scalar_min_max_add(reg, &fake_reg);
 			reg->var_off = tnum_add(reg->var_off, fake_reg.var_off);
 		}
-	}));
+	}
 }
 
 static int check_cond_jmp_op(struct bpf_verifier_env *env,
@@ -15198,6 +15385,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
 	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
 	struct bpf_reg_state *eq_branch_regs;
+	struct linked_regs linked_regs = {};
 	struct bpf_reg_state fake_reg = {};
 	u8 opcode = BPF_OP(insn->code);
 	bool is_jmp32;
@@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		return 0;
 	}
 
+	/* Push scalar registers sharing same ID to jump history,
+	 * do this before creating 'other_branch', so that both
+	 * 'this_branch' and 'other_branch' share this history
+	 * if parent state is created.
+	 */
+	if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
+		find_equal_scalars(this_branch, src_reg->id, &linked_regs);
+	if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
+		find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
+	if (linked_regs.cnt > 1) {
+		err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
+		if (err)
+			return err;
+	}
+
 	other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
 				  false);
 	if (!other_branch)
@@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	if (BPF_SRC(insn->code) == BPF_X &&
 	    src_reg->type == SCALAR_VALUE && src_reg->id &&
 	    !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
-		find_equal_scalars(this_branch, src_reg);
-		find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
+		copy_known_reg(this_branch, src_reg, &linked_regs);
+		copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);
 	}
 	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
 	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
-		find_equal_scalars(this_branch, dst_reg);
-		find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
+		copy_known_reg(this_branch, dst_reg, &linked_regs);
+		copy_known_reg(other_branch, &other_branch_regs[insn->dst_reg], &linked_regs);
 	}
 
 	/* if one pointer register is compared to another pointer
@@ -17624,7 +17827,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 * the current state.
 			 */
 			if (is_jmp_point(env, env->insn_idx))
-				err = err ? : push_jmp_history(env, cur, 0);
+				err = err ? : push_jmp_history(env, cur, 0, 0);
 			err = err ? : propagate_precision(env, &sl->state);
 			if (err)
 				return err;
@@ -17892,7 +18095,7 @@ static int do_check(struct bpf_verifier_env *env)
 		}
 
 		if (is_jmp_point(env, env->insn_idx)) {
-			err = push_jmp_history(env, state, 0);
+			err = push_jmp_history(env, state, 0, 0);
 			if (err)
 				return err;
 		}
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
index 6a6fad625f7e..9d415f7ce599 100644
--- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
@@ -278,7 +278,7 @@ __msg("mark_precise: frame0: last_idx 14 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
-__msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
+__msg("mark_precise: frame0: regs=r0,r6 stack= before 10: (bf) r6 = r0")
 __msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")
 /* State entering callback body popped from states stack */
 __msg("from 9 to 17: frame1:")
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index 90643ccc221d..64d722199e8f 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -39,11 +39,11 @@
 	.result = VERBOSE_ACCEPT,
 	.errstr =
 	"mark_precise: frame0: last_idx 26 first_idx 20\
-	mark_precise: frame0: regs=r2,r9 stack= before 25\
-	mark_precise: frame0: regs=r2,r9 stack= before 24\
-	mark_precise: frame0: regs=r2,r9 stack= before 23\
-	mark_precise: frame0: regs=r2,r9 stack= before 22\
-	mark_precise: frame0: regs=r2,r9 stack= before 20\
+	mark_precise: frame0: regs=r2 stack= before 25\
+	mark_precise: frame0: regs=r2 stack= before 24\
+	mark_precise: frame0: regs=r2 stack= before 23\
+	mark_precise: frame0: regs=r2 stack= before 22\
+	mark_precise: frame0: regs=r2 stack= before 20\
 	mark_precise: frame0: parent state regs=r2,r9 stack=:\
 	mark_precise: frame0: last_idx 19 first_idx 10\
 	mark_precise: frame0: regs=r2,r9 stack= before 19\
@@ -100,11 +100,11 @@
 	.errstr =
 	"26: (85) call bpf_probe_read_kernel#113\
 	mark_precise: frame0: last_idx 26 first_idx 22\
-	mark_precise: frame0: regs=r2,r9 stack= before 25\
-	mark_precise: frame0: regs=r2,r9 stack= before 24\
-	mark_precise: frame0: regs=r2,r9 stack= before 23\
-	mark_precise: frame0: regs=r2,r9 stack= before 22\
-	mark_precise: frame0: parent state regs=r2,r9 stack=:\
+	mark_precise: frame0: regs=r2 stack= before 25\
+	mark_precise: frame0: regs=r2 stack= before 24\
+	mark_precise: frame0: regs=r2 stack= before 23\
+	mark_precise: frame0: regs=r2 stack= before 22\
+	mark_precise: frame0: parent state regs=r2 stack=:\
 	mark_precise: frame0: last_idx 20 first_idx 20\
 	mark_precise: frame0: regs=r2,r9 stack= before 20\
 	mark_precise: frame0: parent state regs=r2,r9 stack=:\
-- 
2.45.2

Re: [PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Andrii Nakryiko]

On Fri, Jul 5, 2024 at 1:59 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Use bpf_verifier_state->jmp_history to track which registers were
> updated by find_equal_scalars() when conditional jump was verified.
> Use recorded information in backtrack_insn() to propagate precision.
>
> E.g. for the following program:
>
>             while verifying instructions
>   r1 = r0              |
>   if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
>   if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history

linked_scalars? especially now that Alexei added offsets between
linked registers

>   r2 = r10             |
>   r2 += r0             v mark_chain_precision(r0)
>
>             while doing mark_chain_precision(r0)
>   r1 = r0              ^
>   if r1 < 8  goto ...  | mark r0,r1 as precise
>   if r0 > 16 goto ...  | mark r0,r1 as precise
>   r2 = r10             |
>   r2 += r0             | mark r0 precise

let's reverse the order here so it's linear in how the algorithm
actually works (backwards)?

>
> Technically, achieve this as follows:
> - Use 10 bits to identify each register that gains range because of
>   find_equal_scalars():

should this be renamed to find_linked_scalars() nowadays?

>   - 3 bits for frame number;
>   - 6 bits for register or stack slot number;
>   - 1 bit to indicate if register is spilled.
> - Use u64 as a vector of 6 such records + 4 bits for vector length.
> - Augment struct bpf_jmp_history_entry with field 'linked_regs'
>   representing such vector.
> - When doing check_cond_jmp_op() remember up to 6 registers that
>   gain range because of find_equal_scalars() in such a vector.
> - Don't propagate range information and reset IDs for registers that
>   don't fit in 6-value vector.
> - Push a pair {instruction index, equal scalars vector}
>   to bpf_verifier_state->jmp_history.
> - When doing backtrack_insn() check if any of recorded linked
>   registers is currently marked precise, if so mark all linked
>   registers as precise.
>
> This also requires fixes for two test_verifier tests:
> - precise: test 1
> - precise: test 2
>
> Both tests contain the following instruction sequence:
>
> 19: (bf) r2 = r9                      ; R2=scalar(id=3) R9=scalar(id=3)
> 20: (a5) if r2 < 0x8 goto pc+1        ; R2=scalar(id=3,umin=8)
> 21: (95) exit
> 22: (07) r2 += 1                      ; R2_w=scalar(id=3+1,...)
> 23: (bf) r1 = r10                     ; R1_w=fp0 R10=fp0
> 24: (07) r1 += -8                     ; R1_w=fp-8
> 25: (b7) r3 = 0                       ; R3_w=0
> 26: (85) call bpf_probe_read_kernel#113
>
> The call to bpf_probe_read_kernel() at (26) forces r2 to be precise.
> Previously, this forced all registers with same id to become precise
> immediately when mark_chain_precision() is called.
> After this change, the precision is propagated to registers sharing
> same id only when 'if' instruction is backtracked.
> Hence verification log for both tests is changed:
> regs=r2,r9 -> regs=r2 for instructions 25..20.
>
> Fixes: 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")
> Reported-by: Hao Sun <sunhao.th@gmail.com>
> Closes: https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
> Suggested-by: Andrii Nakryiko <andrii@kernel.org>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h                  |   4 +
>  kernel/bpf/verifier.c                         | 231 ++++++++++++++++--
>  .../bpf/progs/verifier_subprog_precision.c    |   2 +-
>  .../testing/selftests/bpf/verifier/precise.c  |  20 +-
>  4 files changed, 232 insertions(+), 25 deletions(-)
>

The logic looks good (though I had a few small questions), I think.

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 2b54e25d2364..da450552c278 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -371,6 +371,10 @@ struct bpf_jmp_history_entry {
>         u32 prev_idx : 22;
>         /* special flags, e.g., whether insn is doing register stack spill/load */
>         u32 flags : 10;
> +       /* additional registers that need precision tracking when this
> +        * jump is backtracked, vector of six 10-bit records
> +        */
> +       u64 linked_regs;
>  };
>
>  /* Maximum number of register states that can exist at once */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index e25ad5fb9115..ec493360607e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3335,9 +3335,87 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
>         return env->insn_aux_data[insn_idx].jmp_point;
>  }
>
> +#define ES_FRAMENO_BITS        3
> +#define ES_SPI_BITS    6
> +#define ES_ENTRY_BITS  (ES_SPI_BITS + ES_FRAMENO_BITS + 1)
> +#define ES_SIZE_BITS   4
> +#define ES_FRAMENO_MASK        ((1ul << ES_FRAMENO_BITS) - 1)
> +#define ES_SPI_MASK    ((1ul << ES_SPI_BITS)     - 1)
> +#define ES_SIZE_MASK   ((1ul << ES_SIZE_BITS)    - 1)

ull for 32-bit arches?

> +#define ES_SPI_OFF     ES_FRAMENO_BITS
> +#define ES_IS_REG_OFF  (ES_SPI_BITS + ES_FRAMENO_BITS)

ES makes no sense now, no? LR or LINKREG or something along those lines?

> +#define LINKED_REGS_MAX        6
> +
> +struct reg_or_spill {

reg_or_spill -> linked_reg ?

> +       u8 frameno:3;
> +       union {
> +               u8 spi:6;
> +               u8 regno:6;
> +       };
> +       bool is_reg:1;
> +};

Do we need these bitfields for unpacked representation? It's going to
use 2 bytes for this struct anyways. If you just use u8 for everything
you end up with 3 bytes. Bitfields are a bit slower because the
compiler will need to do more bit manipulations, so is it really worth
it?

> +
> +struct linked_regs {
> +       int cnt;
> +       struct reg_or_spill entries[LINKED_REGS_MAX];
> +};
> +

[...]

> @@ -3615,6 +3739,12 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
>                 print_bpf_insn(&cbs, insn, env->allow_ptr_leaks);
>         }
>
> +       /* If there is a history record that some registers gained range at this insn,
> +        * propagate precision marks to those registers, so that bt_is_reg_set()
> +        * accounts for these registers.
> +        */
> +       bt_sync_linked_regs(bt, hist);
> +
>         if (class == BPF_ALU || class == BPF_ALU64) {
>                 if (!bt_is_reg_set(bt, dreg))
>                         return 0;
> @@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
>                          */
>                         bt_set_reg(bt, dreg);
>                         bt_set_reg(bt, sreg);
> +               } else if (BPF_SRC(insn->code) == BPF_K) {
>                          /* else dreg <cond> K

drop "else" from the comment then? I like this change.

>                           * Only dreg still needs precision before
>                           * this insn, so for the K-based conditional
> @@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
>                         /* to be analyzed */
>                         return -ENOTSUPP;
>         }
> +       /* Propagate precision marks to linked registers, to account for
> +        * registers marked as precise in this function.
> +        */
> +       bt_sync_linked_regs(bt, hist);

Radical Andrii is fine with this, though I wonder if there is some
place outside of backtrack_insn() where the first
bt_sync_linked_regs() could be called just once?

But regardless, this is only mildly expensive when we do have linked
registers, so unlikely to have any noticeable performance effect.

>         return 0;
>  }
>
> @@ -4624,7 +4759,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>         }
>
>         if (insn_flags)
> -               return push_jmp_history(env, env->cur_state, insn_flags);
> +               return push_jmp_history(env, env->cur_state, insn_flags, 0);
>         return 0;
>  }
>
> @@ -4929,7 +5064,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
>                 insn_flags = 0; /* we are not restoring spilled register */
>         }
>         if (insn_flags)
> -               return push_jmp_history(env, env->cur_state, insn_flags);
> +               return push_jmp_history(env, env->cur_state, insn_flags, 0);
>         return 0;
>  }
>
> @@ -15154,14 +15289,66 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>         return true;
>  }
>
> -static void find_equal_scalars(struct bpf_verifier_state *vstate,
> -                              struct bpf_reg_state *known_reg)
> +static void __find_equal_scalars(struct linked_regs *reg_set, struct bpf_reg_state *reg,
> +                                u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)

we should abandon "equal scalars" terminology, they don't have to be
equal, they are just linked together (potentially with a fixed
difference between them)


how about "collect_linked_regs"?

> +{
> +       struct reg_or_spill *e;
> +
> +       if (reg->type != SCALAR_VALUE || (reg->id & ~BPF_ADD_CONST) != id)

THIS is actually the place where I'd use u32 id:31; + bool
is_linked_reg:1; just so that it's not so easy to accidentally forget
about BPF_ADD_CONST flag (but it's unrelated to your patch)

> +               return;
> +
> +       e = linked_regs_push(reg_set);
> +       if (e) {
> +               e->frameno = frameno;
> +               e->is_reg = is_reg;
> +               e->regno = spi_or_reg;
> +       } else {
> +               reg->id = 0;
> +       }
> +}
> +

[...]

> @@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>                 return 0;
>         }
>
> +       /* Push scalar registers sharing same ID to jump history,
> +        * do this before creating 'other_branch', so that both
> +        * 'this_branch' and 'other_branch' share this history
> +        * if parent state is created.
> +        */
> +       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> +               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
> +       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> +               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
> +       if (linked_regs.cnt > 1) {

if we have just one, should it be even marked as linked?

> +               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
> +               if (err)
> +                       return err;
> +       }
> +
>         other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
>                                   false);
>         if (!other_branch)
> @@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>         if (BPF_SRC(insn->code) == BPF_X &&
>             src_reg->type == SCALAR_VALUE && src_reg->id &&
>             !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
> -               find_equal_scalars(this_branch, src_reg);
> -               find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
> +               copy_known_reg(this_branch, src_reg, &linked_regs);
> +               copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);

I liked the "sync" terminology you used for bt, so why not call this
"sync_linked_regs" ?

>         }
>         if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
>             !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
> -               find_equal_scalars(this_branch, dst_reg);
> -               find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
> +               copy_known_reg(this_branch, dst_reg, &linked_regs);
> +               copy_known_reg(other_branch, &other_branch_regs[insn->dst_reg], &linked_regs);
>         }
>

[...]

Re: [PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Eduard Zingerman]

On Tue, 2024-07-09 at 17:34 -0700, Andrii Nakryiko wrote:
> On Fri, Jul 5, 2024 at 1:59 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > Use bpf_verifier_state->jmp_history to track which registers were
> > updated by find_equal_scalars() when conditional jump was verified.
> > Use recorded information in backtrack_insn() to propagate precision.
> > 
> > E.g. for the following program:
> > 
> >             while verifying instructions
> >   r1 = r0              |
> >   if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
> >   if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history
> 
> linked_scalars? especially now that Alexei added offsets between
> linked registers

Missed this, will update.

> 
> >   r2 = r10             |
> >   r2 += r0             v mark_chain_precision(r0)
> > 
> >             while doing mark_chain_precision(r0)
> >   r1 = r0              ^
> >   if r1 < 8  goto ...  | mark r0,r1 as precise
> >   if r0 > 16 goto ...  | mark r0,r1 as precise
> >   r2 = r10             |
> >   r2 += r0             | mark r0 precise
> 
> let's reverse the order here so it's linear in how the algorithm
> actually works (backwards)?

I thought the arrow would be enough. Ok, can reverse.

> > Technically, achieve this as follows:
> > - Use 10 bits to identify each register that gains range because of
> >   find_equal_scalars():
> 
> should this be renamed to find_linked_scalars() nowadays?

That would be sync_linked_regs() if we use naming that you suggest.
Will update.

[...]

> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index e25ad5fb9115..ec493360607e 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -3335,9 +3335,87 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
> >         return env->insn_aux_data[insn_idx].jmp_point;
> >  }
> > 
> > +#define ES_FRAMENO_BITS        3
> > +#define ES_SPI_BITS    6
> > +#define ES_ENTRY_BITS  (ES_SPI_BITS + ES_FRAMENO_BITS + 1)
> > +#define ES_SIZE_BITS   4
> > +#define ES_FRAMENO_MASK        ((1ul << ES_FRAMENO_BITS) - 1)
> > +#define ES_SPI_MASK    ((1ul << ES_SPI_BITS)     - 1)
> > +#define ES_SIZE_MASK   ((1ul << ES_SIZE_BITS)    - 1)
> 
> ull for 32-bit arches?

Ok

> 
> > +#define ES_SPI_OFF     ES_FRAMENO_BITS
> > +#define ES_IS_REG_OFF  (ES_SPI_BITS + ES_FRAMENO_BITS)
> 
> ES makes no sense now, no? LR or LINKREG or something along those lines?
> 
> > +#define LINKED_REGS_MAX        6
> > +
> > +struct reg_or_spill {
> 
> reg_or_spill -> linked_reg ?

Ok

> 
> > +       u8 frameno:3;
> > +       union {
> > +               u8 spi:6;
> > +               u8 regno:6;
> > +       };
> > +       bool is_reg:1;
> > +};
> 
> Do we need these bitfields for unpacked representation? It's going to
> use 2 bytes for this struct anyways. If you just use u8 for everything
> you end up with 3 bytes. Bitfields are a bit slower because the
> compiler will need to do more bit manipulations, so is it really worth
> it?

Ok, will remove bitfields.

[...]

> > @@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> >                          */
> >                         bt_set_reg(bt, dreg);
> >                         bt_set_reg(bt, sreg);
> > +               } else if (BPF_SRC(insn->code) == BPF_K) {
> >                          /* else dreg <cond> K
> 
> drop "else" from the comment then? I like this change.

This is actually a leftover from v1. I can drop "else" from the
comment or drop this hunk as it is not necessary for the series.

> >                           * Only dreg still needs precision before
> >                           * this insn, so for the K-based conditional
> > @@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> >                         /* to be analyzed */
> >                         return -ENOTSUPP;
> >         }
> > +       /* Propagate precision marks to linked registers, to account for
> > +        * registers marked as precise in this function.
> > +        */
> > +       bt_sync_linked_regs(bt, hist);
> 
> Radical Andrii is fine with this, though I wonder if there is some
> place outside of backtrack_insn() where the first
> bt_sync_linked_regs() could be called just once?

The problem here is that:
- in theory linked_regs could be present for any instruction, thus
  sync() is needed after get_jmp_hist_entry call in
  __mark_chain_precision();
- backtrack_insn() might both remove and add some registers in bt,
  hence, to correctly handle bt_empty() call in __mark_chain_precision
  the sync() is also needed after backtrack_insn().

So, current placement is the simplest I could come up with.

> But regardless, this is only mildly expensive when we do have linked
> registers, so unlikely to have any noticeable performance effect.

Yes, that was my thinking as well.

[...]

> > @@ -15154,14 +15289,66 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >         return true;
> >  }
> > 
> > -static void find_equal_scalars(struct bpf_verifier_state *vstate,
> > -                              struct bpf_reg_state *known_reg)
> > +static void __find_equal_scalars(struct linked_regs *reg_set, struct bpf_reg_state *reg,
> > +                                u32 id, u32 frameno, u32 spi_or_reg, bool is_reg)
> 
> we should abandon "equal scalars" terminology, they don't have to be
> equal, they are just linked together (potentially with a fixed
> difference between them)
> 
> how about "collect_linked_regs"?

Sounds good.

[...]

> > @@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> >                 return 0;
> >         }
> > 
> > +       /* Push scalar registers sharing same ID to jump history,
> > +        * do this before creating 'other_branch', so that both
> > +        * 'this_branch' and 'other_branch' share this history
> > +        * if parent state is created.
> > +        */
> > +       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> > +               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
> > +       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> > +               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
> > +       if (linked_regs.cnt > 1) {
> 
> if we have just one, should it be even marked as linked?

Sorry, I don't understand. Do you suggest to add an additional check
in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?

[...]
> 
> > +               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
> > +               if (err)
> > +                       return err;
> > +       }
> > +
> >         other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
> >                                   false);
> >         if (!other_branch)
> > @@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> >         if (BPF_SRC(insn->code) == BPF_X &&
> >             src_reg->type == SCALAR_VALUE && src_reg->id &&
> >             !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
> > -               find_equal_scalars(this_branch, src_reg);
> > -               find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
> > +               copy_known_reg(this_branch, src_reg, &linked_regs);
> > +               copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);
> 
> I liked the "sync" terminology you used for bt, so why not call this
> "sync_linked_regs" ?

I kept the current name for the function.
Suggested name makes sense, though.

[...]

Re: [PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Andrii Nakryiko]

On Tue, Jul 9, 2024 at 6:21 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2024-07-09 at 17:34 -0700, Andrii Nakryiko wrote:
> > On Fri, Jul 5, 2024 at 1:59 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > Use bpf_verifier_state->jmp_history to track which registers were
> > > updated by find_equal_scalars() when conditional jump was verified.
> > > Use recorded information in backtrack_insn() to propagate precision.
> > >
> > > E.g. for the following program:
> > >
> > >             while verifying instructions
> > >   r1 = r0              |
> > >   if r1 < 8  goto ...  | push r0,r1 as equal_scalars in jmp_history
> > >   if r0 > 16 goto ...  | push r0,r1 as equal_scalars in jmp_history
> >
> > linked_scalars? especially now that Alexei added offsets between
> > linked registers
>
> Missed this, will update.
>
> >
> > >   r2 = r10             |
> > >   r2 += r0             v mark_chain_precision(r0)
> > >
> > >             while doing mark_chain_precision(r0)
> > >   r1 = r0              ^
> > >   if r1 < 8  goto ...  | mark r0,r1 as precise
> > >   if r0 > 16 goto ...  | mark r0,r1 as precise
> > >   r2 = r10             |
> > >   r2 += r0             | mark r0 precise
> >
> > let's reverse the order here so it's linear in how the algorithm
> > actually works (backwards)?
>
> I thought the arrow would be enough. Ok, can reverse.

it's the reverse order compared to what you'd see in the verifier log.
I did see the arrow (though it wasn't all that clear on the first
reading), but still feels like it would be better to have consistent
order with verifier log

[...]

> > > @@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> > >                          */
> > >                         bt_set_reg(bt, dreg);
> > >                         bt_set_reg(bt, sreg);
> > > +               } else if (BPF_SRC(insn->code) == BPF_K) {
> > >                          /* else dreg <cond> K
> >
> > drop "else" from the comment then? I like this change.
>
> This is actually a leftover from v1. I can drop "else" from the
> comment or drop this hunk as it is not necessary for the series.

I'd keep explicit `else if`

>
> > >                           * Only dreg still needs precision before
> > >                           * this insn, so for the K-based conditional
> > > @@ -3862,6 +3993,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> > >                         /* to be analyzed */
> > >                         return -ENOTSUPP;
> > >         }
> > > +       /* Propagate precision marks to linked registers, to account for
> > > +        * registers marked as precise in this function.
> > > +        */
> > > +       bt_sync_linked_regs(bt, hist);
> >
> > Radical Andrii is fine with this, though I wonder if there is some
> > place outside of backtrack_insn() where the first
> > bt_sync_linked_regs() could be called just once?
>
> The problem here is that:
> - in theory linked_regs could be present for any instruction, thus
>   sync() is needed after get_jmp_hist_entry call in
>   __mark_chain_precision();
> - backtrack_insn() might both remove and add some registers in bt,
>   hence, to correctly handle bt_empty() call in __mark_chain_precision
>   the sync() is also needed after backtrack_insn().
>
> So, current placement is the simplest I could come up with.

agreed, let's keep it as is

[...]

> > > @@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > >                 return 0;
> > >         }
> > >
> > > +       /* Push scalar registers sharing same ID to jump history,
> > > +        * do this before creating 'other_branch', so that both
> > > +        * 'this_branch' and 'other_branch' share this history
> > > +        * if parent state is created.
> > > +        */
> > > +       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> > > +               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
> > > +       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> > > +               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
> > > +       if (linked_regs.cnt > 1) {
> >
> > if we have just one, should it be even marked as linked?
>
> Sorry, I don't understand. Do you suggest to add an additional check
> in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?

I find `if (linked_regs.cnt > 1)` check a bit weird and it feels like
it should be unnecessary. As soon as we are left with just one
"linked" register (linked with what? with itself?) it shouldn't be
linked anymore. Is there a point where we break the link between
registers where we can/should drop ID from the singularly linked
register? Why keep that scalar register ID set?

>
> [...]
> >
> > > +               err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
> > > +               if (err)
> > > +                       return err;
> > > +       }
> > > +
> > >         other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx,
> > >                                   false);
> > >         if (!other_branch)
> > > @@ -15336,13 +15539,13 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > >         if (BPF_SRC(insn->code) == BPF_X &&
> > >             src_reg->type == SCALAR_VALUE && src_reg->id &&
> > >             !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
> > > -               find_equal_scalars(this_branch, src_reg);
> > > -               find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
> > > +               copy_known_reg(this_branch, src_reg, &linked_regs);
> > > +               copy_known_reg(other_branch, &other_branch_regs[insn->src_reg], &linked_regs);
> >
> > I liked the "sync" terminology you used for bt, so why not call this
> > "sync_linked_regs" ?
>
> I kept the current name for the function.
> Suggested name makes sense, though.
>
> [...]

Re: [PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Eduard Zingerman]

On Tue, 2024-07-09 at 22:28 -0700, Andrii Nakryiko wrote:

[...]

> > > >   r2 = r10             |
> > > >   r2 += r0             v mark_chain_precision(r0)
> > > > 
> > > >             while doing mark_chain_precision(r0)
> > > >   r1 = r0              ^
> > > >   if r1 < 8  goto ...  | mark r0,r1 as precise
> > > >   if r0 > 16 goto ...  | mark r0,r1 as precise
> > > >   r2 = r10             |
> > > >   r2 += r0             | mark r0 precise
> > > 
> > > let's reverse the order here so it's linear in how the algorithm
> > > actually works (backwards)?
> > 
> > I thought the arrow would be enough. Ok, can reverse.
> 
> it's the reverse order compared to what you'd see in the verifier log.
> I did see the arrow (though it wasn't all that clear on the first
> reading), but still feels like it would be better to have consistent
> order with verifier log

Ok, no problem

> 
> [...]
> 
> > > > @@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> > > >                          */
> > > >                         bt_set_reg(bt, dreg);
> > > >                         bt_set_reg(bt, sreg);
> > > > +               } else if (BPF_SRC(insn->code) == BPF_K) {
> > > >                          /* else dreg <cond> K
> > > 
> > > drop "else" from the comment then? I like this change.
> > 
> > This is actually a leftover from v1. I can drop "else" from the
> > comment or drop this hunk as it is not necessary for the series.
> 
> I'd keep explicit `else if`

Ok, will do

[...]

> > > > @@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > > >                 return 0;
> > > >         }
> > > > 
> > > > +       /* Push scalar registers sharing same ID to jump history,
> > > > +        * do this before creating 'other_branch', so that both
> > > > +        * 'this_branch' and 'other_branch' share this history
> > > > +        * if parent state is created.
> > > > +        */
> > > > +       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> > > > +               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
> > > > +       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> > > > +               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
> > > > +       if (linked_regs.cnt > 1) {
> > > 
> > > if we have just one, should it be even marked as linked?
> > 
> > Sorry, I don't understand. Do you suggest to add an additional check
> > in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?
> 
> I find `if (linked_regs.cnt > 1)` check a bit weird and it feels like
> it should be unnecessary. As soon as we are left with just one
> "linked" register (linked with what? with itself?) it shouldn't be
> linked anymore. Is there a point where we break the link between
> registers where we can/should drop ID from the singularly linked
> register? Why keep that scalar register ID set?

I can push this check inside find_equal_scalars/collect_linked_regs, e.g.:

collect_linked_regs(... linked_regs ...)
{
	...
	if (linked_regs.cnt == 1)
		linked_regs.cnt = 0;
	...
}

But then this particular place would have to be modified as follows:

	if (linked_regs.cnt > 0) {
		err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
		if (err)
			return err;
	}

Or something similar has to be done inside push_jmp_history().

[...]

Re: [PATCH bpf-next v2 1/3] bpf: track find_equal_scalars history on per-instruction level

[Andrii Nakryiko]

On Tue, Jul 9, 2024 at 11:36 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2024-07-09 at 22:28 -0700, Andrii Nakryiko wrote:
>
> [...]
>
> > > > >   r2 = r10             |
> > > > >   r2 += r0             v mark_chain_precision(r0)
> > > > >
> > > > >             while doing mark_chain_precision(r0)
> > > > >   r1 = r0              ^
> > > > >   if r1 < 8  goto ...  | mark r0,r1 as precise
> > > > >   if r0 > 16 goto ...  | mark r0,r1 as precise
> > > > >   r2 = r10             |
> > > > >   r2 += r0             | mark r0 precise
> > > >
> > > > let's reverse the order here so it's linear in how the algorithm
> > > > actually works (backwards)?
> > >
> > > I thought the arrow would be enough. Ok, can reverse.
> >
> > it's the reverse order compared to what you'd see in the verifier log.
> > I did see the arrow (though it wasn't all that clear on the first
> > reading), but still feels like it would be better to have consistent
> > order with verifier log
>
> Ok, no problem
>
> >
> > [...]
> >
> > > > > @@ -3844,6 +3974,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> > > > >                          */
> > > > >                         bt_set_reg(bt, dreg);
> > > > >                         bt_set_reg(bt, sreg);
> > > > > +               } else if (BPF_SRC(insn->code) == BPF_K) {
> > > > >                          /* else dreg <cond> K
> > > >
> > > > drop "else" from the comment then? I like this change.
> > >
> > > This is actually a leftover from v1. I can drop "else" from the
> > > comment or drop this hunk as it is not necessary for the series.
> >
> > I'd keep explicit `else if`
>
> Ok, will do
>
> [...]
>
> > > > > @@ -15312,6 +15500,21 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > > > >                 return 0;
> > > > >         }
> > > > >
> > > > > +       /* Push scalar registers sharing same ID to jump history,
> > > > > +        * do this before creating 'other_branch', so that both
> > > > > +        * 'this_branch' and 'other_branch' share this history
> > > > > +        * if parent state is created.
> > > > > +        */
> > > > > +       if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id)
> > > > > +               find_equal_scalars(this_branch, src_reg->id, &linked_regs);
> > > > > +       if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
> > > > > +               find_equal_scalars(this_branch, dst_reg->id, &linked_regs);
> > > > > +       if (linked_regs.cnt > 1) {
> > > >
> > > > if we have just one, should it be even marked as linked?
> > >
> > > Sorry, I don't understand. Do you suggest to add an additional check
> > > in find_equal_scalars/collect_linked_regs and reset it if 'cnt' equals 1?
> >
> > I find `if (linked_regs.cnt > 1)` check a bit weird and it feels like
> > it should be unnecessary. As soon as we are left with just one
> > "linked" register (linked with what? with itself?) it shouldn't be
> > linked anymore. Is there a point where we break the link between
> > registers where we can/should drop ID from the singularly linked
> > register? Why keep that scalar register ID set?
>
> I can push this check inside find_equal_scalars/collect_linked_regs, e.g.:
>
> collect_linked_regs(... linked_regs ...)
> {
>         ...
>         if (linked_regs.cnt == 1)
>                 linked_regs.cnt = 0;

I mean, fine, that's ok. But you are missing the point I'm making. I'm
saying there is somewhere in the verifier (and I'm too lazy/don't care
to go find where) where we break linked registers link (we reset ID on
one of them, probably). What I am asking is whether we should have a
check there to also reset ID on the last remaining
"kind-of-linked-but-not-really-anymore" register.


Anyways, this doesn't have to be solved right away, so let's do this
fixup you are proposing here and keep clean "linked_regs.cnt > 0"
check below.

>         ...
> }
>
> But then this particular place would have to be modified as follows:
>
>         if (linked_regs.cnt > 0) {

yes, this makes total sense ("are there any linked regs? if not, there
is nothing to push to history")

>                 err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
>                 if (err)
>                         return err;
>         }
>
> Or something similar has to be done inside push_jmp_history().

no need to push this inside push_jmp_history(), why paying the price
of linked_regs_pack() unnecessarily?

>
> [...]

[PATCH bpf-next v2 2/3] bpf: remove mark_precise_scalar_ids()

[Eduard Zingerman]

Function mark_precise_scalar_ids() is superseded by
bt_sync_linked_regs() and equal scalars tracking in jump history.
mark_precise_scalar_ids() propagates precision over registers sharing
same ID on parent/child state boundaries, while jump history records
allow bt_sync_linked_regs() to propagate same information with
instruction level granularity, which is strictly more precise.

This commit removes mark_precise_scalar_ids() and updates test cases
in progs/verifier_scalar_ids to reflect new verifier behavior.

The tests are updated in the following manner:
- mark_precise_scalar_ids() propagated precision regardless of
  presence of conditional jumps, while new jump history based logic
  only kicks in when conditional jumps are present.
  Hence test cases are augmented with conditional jumps to still
  trigger precision propagation.
- As equal scalars tracking no longer relies on parent/child state
  boundaries some test cases are no longer interesting,
  such test cases are removed, namely:
  - precision_same_state and precision_cross_state are superseded by
    equal_scalars_bpf_k;
  - precision_same_state_broken_link and equal_scalars_broken_link
    are superseded by equal_scalars_broken_link.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c                         | 115 ------------
 .../selftests/bpf/progs/verifier_scalar_ids.c | 171 ++++++------------
 .../testing/selftests/bpf/verifier/precise.c  |   8 +-
 3 files changed, 59 insertions(+), 235 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ec493360607e..0c25eecf05f8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4124,96 +4124,6 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
 	}
 }
 
-static bool idset_contains(struct bpf_idset *s, u32 id)
-{
-	u32 i;
-
-	for (i = 0; i < s->count; ++i)
-		if (s->ids[i] == (id & ~BPF_ADD_CONST))
-			return true;
-
-	return false;
-}
-
-static int idset_push(struct bpf_idset *s, u32 id)
-{
-	if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
-		return -EFAULT;
-	s->ids[s->count++] = id & ~BPF_ADD_CONST;
-	return 0;
-}
-
-static void idset_reset(struct bpf_idset *s)
-{
-	s->count = 0;
-}
-
-/* Collect a set of IDs for all registers currently marked as precise in env->bt.
- * Mark all registers with these IDs as precise.
- */
-static int mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
-{
-	struct bpf_idset *precise_ids = &env->idset_scratch;
-	struct backtrack_state *bt = &env->bt;
-	struct bpf_func_state *func;
-	struct bpf_reg_state *reg;
-	DECLARE_BITMAP(mask, 64);
-	int i, fr;
-
-	idset_reset(precise_ids);
-
-	for (fr = bt->frame; fr >= 0; fr--) {
-		func = st->frame[fr];
-
-		bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
-		for_each_set_bit(i, mask, 32) {
-			reg = &func->regs[i];
-			if (!reg->id || reg->type != SCALAR_VALUE)
-				continue;
-			if (idset_push(precise_ids, reg->id))
-				return -EFAULT;
-		}
-
-		bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
-		for_each_set_bit(i, mask, 64) {
-			if (i >= func->allocated_stack / BPF_REG_SIZE)
-				break;
-			if (!is_spilled_scalar_reg(&func->stack[i]))
-				continue;
-			reg = &func->stack[i].spilled_ptr;
-			if (!reg->id)
-				continue;
-			if (idset_push(precise_ids, reg->id))
-				return -EFAULT;
-		}
-	}
-
-	for (fr = 0; fr <= st->curframe; ++fr) {
-		func = st->frame[fr];
-
-		for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
-			reg = &func->regs[i];
-			if (!reg->id)
-				continue;
-			if (!idset_contains(precise_ids, reg->id))
-				continue;
-			bt_set_frame_reg(bt, fr, i);
-		}
-		for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
-			if (!is_spilled_scalar_reg(&func->stack[i]))
-				continue;
-			reg = &func->stack[i].spilled_ptr;
-			if (!reg->id)
-				continue;
-			if (!idset_contains(precise_ids, reg->id))
-				continue;
-			bt_set_frame_slot(bt, fr, i);
-		}
-	}
-
-	return 0;
-}
-
 /*
  * __mark_chain_precision() backtracks BPF program instruction sequence and
  * chain of verifier states making sure that register *regno* (if regno >= 0)
@@ -4346,31 +4256,6 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
 				bt->frame, last_idx, first_idx, subseq_idx);
 		}
 
-		/* If some register with scalar ID is marked as precise,
-		 * make sure that all registers sharing this ID are also precise.
-		 * This is needed to estimate effect of find_equal_scalars().
-		 * Do this at the last instruction of each state,
-		 * bpf_reg_state::id fields are valid for these instructions.
-		 *
-		 * Allows to track precision in situation like below:
-		 *
-		 *     r2 = unknown value
-		 *     ...
-		 *   --- state #0 ---
-		 *     ...
-		 *     r1 = r2                 // r1 and r2 now share the same ID
-		 *     ...
-		 *   --- state #1 {r1.id = A, r2.id = A} ---
-		 *     ...
-		 *     if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
-		 *     ...
-		 *   --- state #2 {r1.id = A, r2.id = A} ---
-		 *     r3 = r10
-		 *     r3 += r1                // need to mark both r1 and r2
-		 */
-		if (mark_precise_scalar_ids(env, st))
-			return -EFAULT;
-
 		if (last_idx < 0) {
 			/* we are at the entry into subprog, which
 			 * is expected for global funcs, but only if
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 13b29a7faa71..639db72b1c55 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -5,54 +5,27 @@
 #include "bpf_misc.h"
 
 /* Check that precision marks propagate through scalar IDs.
- * Registers r{0,1,2} have the same scalar ID at the moment when r0 is
- * marked to be precise, this mark is immediately propagated to r{1,2}.
+ * Registers r{0,1,2} have the same scalar ID.
+ * Range information is propagated for scalars sharing same ID.
+ * Check that precision mark for r0 causes precision marks for r{1,2}
+ * when range information is propagated for 'if <reg> <op> <const>' insn.
  */
 SEC("socket")
 __success __log_level(2)
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (bf) r3 = r10")
-__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
-__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_same_state(void)
-{
-	asm volatile (
-	/* r0 = random number up to 0xff */
-	"call %[bpf_ktime_get_ns];"
-	"r0 &= 0xff;"
-	/* tie r0.id == r1.id == r2.id */
-	"r1 = r0;"
-	"r2 = r0;"
-	/* force r0 to be precise, this immediately marks r1 and r2 as
-	 * precise as well because of shared IDs
-	 */
-	"r3 = r10;"
-	"r3 += r0;"
-	"r0 = 0;"
-	"exit;"
-	:
-	: __imm(bpf_ktime_get_ns)
-	: __clobber_all);
-}
-
-/* Same as precision_same_state, but mark propagates through state /
- * parent state boundary.
- */
-SEC("socket")
-__success __log_level(2)
-__msg("frame0: last_idx 6 first_idx 5 subseq_idx -1")
-__msg("frame0: regs=r0,r1,r2 stack= before 5: (bf) r3 = r10")
+/* first 'if' branch */
+__msg("6: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 4: (25) if r1 > 0x7 goto pc+0")
 __msg("frame0: parent state regs=r0,r1,r2 stack=:")
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
 __msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: parent state regs=r0 stack=:")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+/* second 'if' branch */
+__msg("from 4 to 5: ")
+__msg("6: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 5: (bf) r3 = r10")
+__msg("frame0: regs=r0 stack= before 4: (25) if r1 > 0x7 goto pc+0")
+/* parent state already has r{0,1,2} as precise */
+__msg("frame0: parent state regs= stack=:")
 __flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_cross_state(void)
+__naked void equal_scalars_bpf_k(void)
 {
 	asm volatile (
 	/* r0 = random number up to 0xff */
@@ -61,9 +34,8 @@ __naked void precision_cross_state(void)
 	/* tie r0.id == r1.id == r2.id */
 	"r1 = r0;"
 	"r2 = r0;"
-	/* force checkpoint */
-	"goto +0;"
-	/* force r0 to be precise, this immediately marks r1 and r2 as
+	"if r1 > 7 goto +0;"
+	/* force r0 to be precise, this eventually marks r1 and r2 as
 	 * precise as well because of shared IDs
 	 */
 	"r3 = r10;"
@@ -75,59 +47,18 @@ __naked void precision_cross_state(void)
 	: __clobber_all);
 }
 
-/* Same as precision_same_state, but break one of the
+/* Same as equal_scalars_bpf_k, but break one of the
  * links, note that r1 is absent from regs=... in __msg below.
  */
 SEC("socket")
 __success __log_level(2)
-__msg("frame0: regs=r0,r2 stack= before 5: (bf) r3 = r10")
-__msg("frame0: regs=r0,r2 stack= before 4: (b7) r1 = 0")
-__msg("frame0: regs=r0,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
-__flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_same_state_broken_link(void)
-{
-	asm volatile (
-	/* r0 = random number up to 0xff */
-	"call %[bpf_ktime_get_ns];"
-	"r0 &= 0xff;"
-	/* tie r0.id == r1.id == r2.id */
-	"r1 = r0;"
-	"r2 = r0;"
-	/* break link for r1, this is the only line that differs
-	 * compared to the previous test
-	 */
-	"r1 = 0;"
-	/* force r0 to be precise, this immediately marks r1 and r2 as
-	 * precise as well because of shared IDs
-	 */
-	"r3 = r10;"
-	"r3 += r0;"
-	"r0 = 0;"
-	"exit;"
-	:
-	: __imm(bpf_ktime_get_ns)
-	: __clobber_all);
-}
-
-/* Same as precision_same_state_broken_link, but with state /
- * parent state boundary.
- */
-SEC("socket")
-__success __log_level(2)
-__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
-__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
-__msg("frame0: parent state regs=r0,r2 stack=:")
-__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
-__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
-__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("7: (0f) r3 += r0")
+__msg("frame0: regs=r0 stack= before 6: (bf) r3 = r10")
 __msg("frame0: parent state regs=r0 stack=:")
-__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__msg("frame0: regs=r0 stack= before 5: (25) if r0 > 0x7 goto pc+0")
+__msg("frame0: parent state regs=r0,r2 stack=:")
 __flag(BPF_F_TEST_STATE_FREQ)
-__naked void precision_cross_state_broken_link(void)
+__naked void equal_scalars_broken_link(void)
 {
 	asm volatile (
 	/* r0 = random number up to 0xff */
@@ -136,18 +67,13 @@ __naked void precision_cross_state_broken_link(void)
 	/* tie r0.id == r1.id == r2.id */
 	"r1 = r0;"
 	"r2 = r0;"
-	/* force checkpoint, although link between r1 and r{0,2} is
-	 * broken by the next statement current precision tracking
-	 * algorithm can't react to it and propagates mark for r1 to
-	 * the parent state.
-	 */
-	"goto +0;"
 	/* break link for r1, this is the only line that differs
-	 * compared to precision_cross_state()
+	 * compared to the previous test
 	 */
 	"r1 = 0;"
-	/* force r0 to be precise, this immediately marks r1 and r2 as
-	 * precise as well because of shared IDs
+	"if r0 > 7 goto +0;"
+	/* force r0 to be precise,
+	 * this eventually marks r2 as precise because of shared IDs
 	 */
 	"r3 = r10;"
 	"r3 += r0;"
@@ -164,10 +90,16 @@ __naked void precision_cross_state_broken_link(void)
  */
 SEC("socket")
 __success __log_level(2)
-__msg("11: (0f) r2 += r1")
+__msg("12: (0f) r2 += r1")
 /* Current state */
-__msg("frame2: last_idx 11 first_idx 10 subseq_idx -1")
-__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
+__msg("frame2: last_idx 12 first_idx 11 subseq_idx -1 ")
+__msg("frame2: regs=r1 stack= before 11: (bf) r2 = r10")
+__msg("frame2: parent state regs=r1 stack=")
+__msg("frame1: parent state regs= stack=")
+__msg("frame0: parent state regs= stack=")
+/* Parent state */
+__msg("frame2: last_idx 10 first_idx 10 subseq_idx 11 ")
+__msg("frame2: regs=r1 stack= before 10: (25) if r1 > 0x7 goto pc+0")
 __msg("frame2: parent state regs=r1 stack=")
 /* frame1.r{6,7} are marked because mark_precise_scalar_ids()
  * looks for all registers with frame2.r1.id in the current state
@@ -192,7 +124,7 @@ __msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
 __msg("frame0: parent state regs=r1,r6 stack=")
 /* Parent state */
 __msg("frame0: last_idx 3 first_idx 1 subseq_idx 4")
-__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
+__msg("frame0: regs=r1,r6 stack= before 3: (bf) r6 = r0")
 __msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
 __msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
 __flag(BPF_F_TEST_STATE_FREQ)
@@ -230,7 +162,8 @@ static __naked __noinline __used
 void precision_many_frames__bar(void)
 {
 	asm volatile (
-	/* force r1 to be precise, this immediately marks:
+	"if r1 > 7 goto +0;"
+	/* force r1 to be precise, this eventually marks:
 	 * - bar frame r1
 	 * - foo frame r{1,6,7}
 	 * - main frame r{1,6}
@@ -247,14 +180,16 @@ void precision_many_frames__bar(void)
  */
 SEC("socket")
 __success __log_level(2)
+__msg("11: (0f) r2 += r1")
 /* foo frame */
-__msg("frame1: regs=r1 stack=-8,-16 before 9: (bf) r2 = r10")
+__msg("frame1: regs=r1 stack= before 10: (bf) r2 = r10")
+__msg("frame1: regs=r1 stack= before 9: (25) if r1 > 0x7 goto pc+0")
 __msg("frame1: regs=r1 stack=-8,-16 before 8: (7b) *(u64 *)(r10 -16) = r1")
 __msg("frame1: regs=r1 stack=-8 before 7: (7b) *(u64 *)(r10 -8) = r1")
 __msg("frame1: regs=r1 stack= before 4: (85) call pc+2")
 /* main frame */
-__msg("frame0: regs=r0,r1 stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r1")
-__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r1 stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r1")
+__msg("frame0: regs=r1 stack= before 2: (bf) r1 = r0")
 __msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
 __flag(BPF_F_TEST_STATE_FREQ)
 __naked void precision_stack(void)
@@ -283,7 +218,8 @@ void precision_stack__foo(void)
 	 */
 	"*(u64*)(r10 - 8) = r1;"
 	"*(u64*)(r10 - 16) = r1;"
-	/* force r1 to be precise, this immediately marks:
+	"if r1 > 7 goto +0;"
+	/* force r1 to be precise, this eventually marks:
 	 * - foo frame r1,fp{-8,-16}
 	 * - main frame r1,fp{-8}
 	 */
@@ -299,15 +235,17 @@ void precision_stack__foo(void)
 SEC("socket")
 __success __log_level(2)
 /* r{6,7} */
-__msg("11: (0f) r3 += r7")
-__msg("frame0: regs=r6,r7 stack= before 10: (bf) r3 = r10")
+__msg("12: (0f) r3 += r7")
+__msg("frame0: regs=r7 stack= before 11: (bf) r3 = r10")
+__msg("frame0: regs=r7 stack= before 9: (25) if r7 > 0x7 goto pc+0")
 /* ... skip some insns ... */
 __msg("frame0: regs=r6,r7 stack= before 3: (bf) r7 = r0")
 __msg("frame0: regs=r0,r6 stack= before 2: (bf) r6 = r0")
 /* r{8,9} */
-__msg("12: (0f) r3 += r9")
-__msg("frame0: regs=r8,r9 stack= before 11: (0f) r3 += r7")
+__msg("13: (0f) r3 += r9")
+__msg("frame0: regs=r9 stack= before 12: (0f) r3 += r7")
 /* ... skip some insns ... */
+__msg("frame0: regs=r9 stack= before 10: (25) if r9 > 0x7 goto pc+0")
 __msg("frame0: regs=r8,r9 stack= before 7: (bf) r9 = r0")
 __msg("frame0: regs=r0,r8 stack= before 6: (bf) r8 = r0")
 __flag(BPF_F_TEST_STATE_FREQ)
@@ -328,8 +266,9 @@ __naked void precision_two_ids(void)
 	"r9 = r0;"
 	/* clear r0 id */
 	"r0 = 0;"
-	/* force checkpoint */
-	"goto +0;"
+	/* propagate equal scalars precision */
+	"if r7 > 7 goto +0;"
+	"if r9 > 7 goto +0;"
 	"r3 = r10;"
 	/* force r7 to be precise, this also marks r6 */
 	"r3 += r7;"
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index 64d722199e8f..59a020c35647 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -106,7 +106,7 @@
 	mark_precise: frame0: regs=r2 stack= before 22\
 	mark_precise: frame0: parent state regs=r2 stack=:\
 	mark_precise: frame0: last_idx 20 first_idx 20\
-	mark_precise: frame0: regs=r2,r9 stack= before 20\
+	mark_precise: frame0: regs=r2 stack= before 20\
 	mark_precise: frame0: parent state regs=r2,r9 stack=:\
 	mark_precise: frame0: last_idx 19 first_idx 17\
 	mark_precise: frame0: regs=r2,r9 stack= before 19\
@@ -183,10 +183,10 @@
 	.prog_type = BPF_PROG_TYPE_XDP,
 	.flags = BPF_F_TEST_STATE_FREQ,
 	.errstr = "mark_precise: frame0: last_idx 7 first_idx 7\
-	mark_precise: frame0: parent state regs=r4 stack=-8:\
+	mark_precise: frame0: parent state regs=r4 stack=:\
 	mark_precise: frame0: last_idx 6 first_idx 4\
-	mark_precise: frame0: regs=r4 stack=-8 before 6: (b7) r0 = -1\
-	mark_precise: frame0: regs=r4 stack=-8 before 5: (79) r4 = *(u64 *)(r10 -8)\
+	mark_precise: frame0: regs=r4 stack= before 6: (b7) r0 = -1\
+	mark_precise: frame0: regs=r4 stack= before 5: (79) r4 = *(u64 *)(r10 -8)\
 	mark_precise: frame0: regs= stack=-8 before 4: (7b) *(u64 *)(r3 -8) = r0\
 	mark_precise: frame0: parent state regs=r0 stack=:\
 	mark_precise: frame0: last_idx 3 first_idx 3\
-- 
2.45.2

[PATCH bpf-next v2 3/3] selftests/bpf: tests for per-insn find_equal_scalars() precision tracking

[Eduard Zingerman]

Add a few test cases to verify precision tracking for scalars gaining
range because of find_equal_scalars():
- check what happens when more than 6 registers might gain range in
  find_equal_scalars();
- check if precision is propagated correctly when operand of
  conditional jump gained range in find_equal_scalars() and one of
  linked registers is marked precise;
- check if precision is propagated correctly when operand of
  conditional jump gained range in find_equal_scalars() and a
  other-linked operand of the conditional jump is marked precise;
- add a minimized reproducer for precision tracking bug reported in [0];
- Check that mark_chain_precision() for one of the conditional jump
  operands does not trigger equal scalars precision propagation.

[0] https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/progs/verifier_scalar_ids.c | 165 ++++++++++++++++++
 1 file changed, 165 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 639db72b1c55..993c5affb3d7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -47,6 +47,72 @@ __naked void equal_scalars_bpf_k(void)
 	: __clobber_all);
 }
 
+/* Registers r{0,1,2} share same ID when 'if r1 > ...' insn is processed,
+ * check that verifier marks r{1,2} as precise while backtracking
+ * 'if r1 > ...' with r0 already marked.
+ */
+SEC("socket")
+__success __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("frame0: regs=r0 stack= before 5: (2d) if r1 > r3 goto pc+0")
+__msg("frame0: parent state regs=r0,r1,r2,r3 stack=:")
+__msg("frame0: regs=r0,r1,r2,r3 stack= before 4: (b7) r3 = 7")
+__naked void equal_scalars_bpf_x_src(void)
+{
+	asm volatile (
+	/* r0 = random number up to 0xff */
+	"call %[bpf_ktime_get_ns];"
+	"r0 &= 0xff;"
+	/* tie r0.id == r1.id == r2.id */
+	"r1 = r0;"
+	"r2 = r0;"
+	"r3 = 7;"
+	"if r1 > r3 goto +0;"
+	/* force r0 to be precise, this eventually marks r1 and r2 as
+	 * precise as well because of shared IDs
+	 */
+	"r4 = r10;"
+	"r4 += r0;"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+/* Registers r{0,1,2} share same ID when 'if r1 > r3' insn is processed,
+ * check that verifier marks r{0,1,2} as precise while backtracking
+ * 'if r1 > r3' with r3 already marked.
+ */
+SEC("socket")
+__success __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("frame0: regs=r3 stack= before 5: (2d) if r1 > r3 goto pc+0")
+__msg("frame0: parent state regs=r0,r1,r2,r3 stack=:")
+__msg("frame0: regs=r0,r1,r2,r3 stack= before 4: (b7) r3 = 7")
+__naked void equal_scalars_bpf_x_dst(void)
+{
+	asm volatile (
+	/* r0 = random number up to 0xff */
+	"call %[bpf_ktime_get_ns];"
+	"r0 &= 0xff;"
+	/* tie r0.id == r1.id == r2.id */
+	"r1 = r0;"
+	"r2 = r0;"
+	"r3 = 7;"
+	"if r1 > r3 goto +0;"
+	/* force r0 to be precise, this eventually marks r1 and r2 as
+	 * precise as well because of shared IDs
+	 */
+	"r4 = r10;"
+	"r4 += r3;"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
 /* Same as equal_scalars_bpf_k, but break one of the
  * links, note that r1 is absent from regs=... in __msg below.
  */
@@ -280,6 +346,105 @@ __naked void precision_two_ids(void)
 	: __clobber_all);
 }
 
+SEC("socket")
+__success __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+/* check thar r0 and r6 have different IDs after 'if',
+ * find_equal_scalars() can't tie more than 6 registers for a single insn.
+ */
+__msg("8: (25) if r0 > 0x7 goto pc+0         ; R0=scalar(id=1")
+__msg("9: (bf) r6 = r6                       ; R6_w=scalar(id=2")
+/* check that r{0-5} are marked precise after 'if' */
+__msg("frame0: regs=r0 stack= before 8: (25) if r0 > 0x7 goto pc+0")
+__msg("frame0: parent state regs=r0,r1,r2,r3,r4,r5 stack=:")
+__naked void equal_scalars_too_many_regs(void)
+{
+	asm volatile (
+	/* r0 = random number up to 0xff */
+	"call %[bpf_ktime_get_ns];"
+	"r0 &= 0xff;"
+	/* tie r{0-6} IDs */
+	"r1 = r0;"
+	"r2 = r0;"
+	"r3 = r0;"
+	"r4 = r0;"
+	"r5 = r0;"
+	"r6 = r0;"
+	/* propagate range for r{0-6} */
+	"if r0 > 7 goto +0;"
+	/* make r6 appear in the log */
+	"r6 = r6;"
+	/* force r0 to be precise,
+	 * this would cause r{0-4} to be precise because of shared IDs
+	 */
+	"r7 = r10;"
+	"r7 += r0;"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__failure __log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("regs=r7 stack= before 5: (3d) if r8 >= r0")
+__msg("parent state regs=r0,r7,r8")
+__msg("regs=r0,r7,r8 stack= before 4: (25) if r0 > 0x1")
+__msg("div by zero")
+__naked void equal_scalars_broken_link_2(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"r7 = r0;"
+	"r8 = r0;"
+	"call %[bpf_get_prandom_u32];"
+	"if r0 > 1 goto +0;"
+	/* r7.id == r8.id,
+	 * thus r7 precision implies r8 precision,
+	 * which implies r0 precision because of the conditional below.
+	 */
+	"if r8 >= r0 goto 1f;"
+	/* break id relation between r7 and r8 */
+	"r8 += r8;"
+	/* make r7 precise */
+	"if r7 == 0 goto 1f;"
+	"r0 /= 0;"
+"1:"
+	"r0 = 42;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/* Check that mark_chain_precision() for one of the conditional jump
+ * operands does not trigger equal scalars precision propagation.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("3: (25) if r1 > 0x100 goto pc+0")
+__msg("frame0: regs=r1 stack= before 2: (bf) r1 = r0")
+__naked void cjmp_no_equal_scalars_trigger(void)
+{
+	asm volatile (
+	/* r0 = random number up to 0xff */
+	"call %[bpf_ktime_get_ns];"
+	"r0 &= 0xff;"
+	/* tie r0.id == r1.id */
+	"r1 = r0;"
+	/* the jump below would be predicted, thus r1 would be marked precise,
+	 * this should not imply precision mark for r0
+	 */
+	"if r1 > 256 goto +0;"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
 /* Verify that check_ids() is used by regsafe() for scalars.
  *
  * r9 = ... some pointer with range X ...
-- 
2.45.2