On Mon, Jun 10, 2024 at 1:27 PM Alexei Starovoitov <alexei.starovoitov@xxxxxxxxx> wrote: > > 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". Realized that reg->off != known_reg->off where both have add_const bit set is actually possible. This case is mishandled in the above. Will fix it too. pw-bot: cr
