On Thu, 2023-06-08 at 10:33 -0700, Andrii Nakryiko wrote:
> 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?
Yes good point,
I'll add a few __msg lines and a comment to make this thing clear.
>
> 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);
> > > > +}
> > > > +
> > >
> > > [...]
> >
