On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
> >
> > Check __mark_chain_precision() log to verify that scalars with same
> > IDs are marked as precise. Use several scenarios to test that
> > precision marks are propagated through:
> > - registers of scalar type with the same ID within one state;
> > - registers of scalar type with the same ID cross several states;
> > - registers of scalar type with the same ID cross several stack frames;
> > - stack slot of scalar type with the same ID;
> > - multiple scalar IDs are tracked independently.
> >
> > Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> > ---
> > .../selftests/bpf/prog_tests/verifier.c | 2 +
> > .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
> > 2 files changed, 326 insertions(+)
> > create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> >
>
> Great set of tests! I asked for yet another one, but this could be
> easily a follow up. Looks great.
Thanks.
>
> Acked-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
>
> [...]
>
> > +
> > +/* 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("frame0: parent state regs=r0 stack=:")
> > +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
> > +__flag(BPF_F_TEST_STATE_FREQ)
> > +__naked void precision_cross_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;"
> > + /* 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 the previous test
> > + */
>
> not really the only line, goto +0 is that different line ;)
My bad, the comment should be "... this is the only line that differs
compared to precision_cross_state_broken()".
>
> > + "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);
> > +}
> > +
> > +/* Check that precision marks propagate through scalar IDs.
> > + * Use the same scalar ID in multiple stack frames, check that
> > + * precision information is propagated up the call stack.
> > + */
> > +SEC("socket")
> > +__success __log_level(2)
> > +/* bar frame */
> > +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
> > +__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
> > +/* foo frame */
> > +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
> > +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
> > +__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
> > +/* main frame */
> > +__msg("frame0: regs=r0,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")
>
> nice test! in this case we discover r6 and r7 during instruction
> backtracking. Let's add another variant of this multi-frame test with
> a forced checkpoint to make sure that all this works correctly between
> child/parent states with multiple active frames?
Because of BPF_F_TEST_STATE_FREQ new state is created at each prune
point. Prune points are marked for each conditional target and
sub-program entry. I skipped a lot of log lines for brevity, here is a
bigger portion of the log:
8: (85) call pc+1
caller:
frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0
callee:
frame2: R1=scalar(id=1,...) R10=fp0
10: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
11: (0f) r2 += r1
frame2: last_idx 11 first_idx 10 subseq_idx -1 <- current state
frame2: regs=r1 stack= before 10: (bf) r2 = r10
frame2: parent state regs=r1 stack=
frame1: parent state regs=r6,r7 stack= <- (I)
frame0: parent state regs=r6 stack=
frame2: last_idx 8 first_idx 8 subseq_idx 10 <- parent state
frame2: regs=r1 stack= before 8: (85) call pc+1
frame1: parent state regs=r1,r6,r7 stack= <- (II)
frame0: parent state regs=r6 stack=
frame1: last_idx 7 first_idx 6 subseq_idx 8 <- parent state
frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
frame1: parent state regs=r1 stack=
frame0: parent state regs=r6 stack=
frame1: last_idx 4 first_idx 4 subseq_idx 6 <- parent state
frame1: regs=r1 stack= before 4: (85) call pc+1
frame0: parent state regs=r1,r6 stack=
frame0: last_idx 3 first_idx 1 subseq_idx 4 <- parent state
frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
frame0: regs=r0 stack= before 1: (57) r0 &= 255
At (I) frame1.r{6,7} are marked because mark_precise_scalar_ids()
looks for all registers with frame2.r1.id in the current state.
At (II) frame1.r1 is marked because of backtracking of call instruction.
It looks like both baсktracking and cross-state propagation are tested.
Maybe I miss-understand your comment.
>
> > +__flag(BPF_F_TEST_STATE_FREQ)
> > +__naked void precision_many_frames(void)
> > +{
> > + asm volatile (
> > + /* r0 = random number up to 0xff */
> > + "call %[bpf_ktime_get_ns];"
> > + "r0 &= 0xff;"
> > + /* tie r0.id == r1.id == r6.id */
> > + "r1 = r0;"
> > + "r6 = r0;"
> > + "call precision_many_frames__foo;"
> > + "exit;"
> > + :
> > + : __imm(bpf_ktime_get_ns)
> > + : __clobber_all);
> > +}
> > +
> > +static __naked __noinline __attribute__((used))
>
> nit: bpf_misc.h has __used macro defined, we can use that everywhere
>
> > +void precision_many_frames__foo(void)
> > +{
> > + asm volatile (
> > + /* conflate one of the register numbers (r6) with outer frame,
> > + * to verify that those are tracked independently
> > + */
> > + "r6 = r1;"
> > + "r7 = r1;"
> > + "call precision_many_frames__bar;"
> > + "exit"
> > + ::: __clobber_all);
> > +}
> > +
>
> [...]
