On Thu, Dec 14, 2023 at 6:28 PM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote: > > On Thu, 2023-12-14 at 18:16 -0800, Alexei Starovoitov wrote: > [...] > > > E.g. for the test-case at hand: > > > > > > 0: (85) call bpf_get_prandom_u32#7 ; R0=scalar() > > > 1: (bf) r7 = r0 ; R0=scalar(id=1) R7_w=scalar(id=1) > > > 2: (bf) r8 = r0 ; R0=scalar(id=1) R8_w=scalar(id=1) > > > 3: (85) call bpf_get_prandom_u32#7 ; R0=scalar() > > > --- checkpoint #1 r7.id = 1, r8.id = 1 --- > > > 4: (25) if r0 > 0x1 goto pc+0 ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,...) > > > --- checkpoint #2 r7.id = 1, r8.id = 1 --- > > > 5: (3d) if r8 >= r0 goto pc+3 ; R0=1 R8=0 | record r8.id=1 in jump history > > > 6: (0f) r8 += r8 ; R8=0 > > > > can we detect that any register link is broken and force checkpoint here? > > Should be possible. I'll try this in the morning and check veristat results. > > By the way, I added some stats collection for find_equal_scalars() and see > the following results when run on ./test_progs: > - maximal number of registers with same id per call: 3 > - average number of registers with same id per call: 1.4 What if we keep 8 extra bytes in jump/instruction history and encode up to 8 linked registers/slots: 1. 1 bit to mark whether it's a src_reg set, or dst_reg set 2. 1 bit to mark whether it's a stack slot or register 3. 6 bits (0..63 values) to record register or slot number If we ever need more than 8 linked registers, we can just forcefully some "links" by resetting some IDs? BTW, is it only conditional jumps that need to record this linked register sets? Did we previously discuss why we don't need this for any other operation?
