On Mon, Jun 10, 2024 at 11:32 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote: > > On Fri, 2024-06-07 at 17:44 -0700, Alexei Starovoitov wrote: > > From: Alexei Starovoitov <ast@xxxxxxxxxx> > > > > Compilers can generate the code > > r1 = r2 > > r1 += 0x1 > > if r2 < 1000 goto ... > > use knowledge of r2 range in subsequent r1 operations > > > > So remember constant delta between r2 and r1 and update r1 after 'if' condition. > > > > Unfortunately LLVM still uses this pattern for loops with 'can_loop' construct: > > for (i = 0; i < 1000 && can_loop; i++) > > > > The "undo" pass was introduced in LLVM > > https://reviews.llvm.org/D121937 > > to prevent this optimization, but it cannot cover all cases. > > Instead of fighting middle end optimizer in BPF backend teach the verifier > > about this pattern. > > I like this idea. > In theory it could be generalized to handle situations when LLVM > uses two counters in parallel: > > r0 = 0 // as an index > r1 = 0 // as a pointer > ... > r0 += 1 > r1 += 8 I don't see how the verifier can associate r0 and r1. In this example r0 with be a scalar while r1 = ld_imm64 map One reg will be counting loops. Another adding fixed offset to map value. > > > > Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx> > > --- > > [...] > > > @@ -15088,13 +15130,43 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > static void find_equal_scalars(struct bpf_verifier_state *vstate, > > struct bpf_reg_state *known_reg) > > { > > + struct bpf_reg_state fake_reg; > > struct bpf_func_state *state; > > struct bpf_reg_state *reg; > > > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > > - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > + if (reg->type != SCALAR_VALUE || reg == known_reg) > > + continue; > > + if ((reg->id & ~BPF_ADD_CONST) != (known_reg->id & ~BPF_ADD_CONST)) > > + continue; > > + if ((reg->id & BPF_ADD_CONST) == (known_reg->id & BPF_ADD_CONST)) { > > copy_register_state(reg, known_reg); > > + } else if ((reg->id & BPF_ADD_CONST) && reg->off) { > > + /* reg = known_reg; reg += const */ > > + copy_register_state(reg, known_reg); > > + > > + fake_reg.type = SCALAR_VALUE; > > + __mark_reg_known(&fake_reg, reg->off); > > + scalar32_min_max_add(reg, &fake_reg); > > + scalar_min_max_add(reg, &fake_reg); > > + reg->var_off = tnum_add(reg->var_off, fake_reg.var_off); > > + reg->off = 0; > > + reg->id &= ~BPF_ADD_CONST; > > + } else if ((known_reg->id & BPF_ADD_CONST) && known_reg->off) { > > + /* reg = known_reg; reg -= const' */ > > + copy_register_state(reg, known_reg); > > + > > + fake_reg.type = SCALAR_VALUE; > > + __mark_reg_known(&fake_reg, known_reg->off); > > + scalar32_min_max_sub(reg, &fake_reg); > > + scalar_min_max_sub(reg, &fake_reg); > > + reg->var_off = tnum_sub(reg->var_off, fake_reg.var_off); > > + } > > I think that copy_register_state logic is off here, > the copy overwrites reg->off before it is used to update the value. Right. Last minute refactoring got bad :( I had 'u32 off = reg->off' all along and then "refactored". > The following test is marked as safe for me, while it should not: Thanks for the test. Will incorporate.
