On Thu, Jun 8, 2023 at 9:17 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> 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.
>
>From the set of __msg() tests it's not obvious that (I) is happening.
So just maybe let's messages like below:
__msg("frame1: parent state regs=r6,r7 stack=")
to make it more explicit?
Either way, it's minor. You are right about checkpoint after each
helper call and subprog call.
> >
> > > +__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);
> > > +}
> > > +
> >
> > [...]
>
