Re: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2024-01-10 at 03:07 +0200, Eduard Zingerman wrote:
> On Tue, 2024-01-09 at 09:26 -0800, Yonghong Song wrote:
> [...]
> > 
> > What will happen if there are multiple BPF_JEQ/BPF_JNE? I made a change to one of tests
> > in patch 3:
> > 
> > +SEC("tc")
> > +__success __log_level(2)
> > +__msg("if r3 != r2 goto pc+3         ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)")
> > +__naked void data_plus_const_neq_pkt_end(void)
> > +{
> > +       asm volatile ("                                 \
> > +       r9 = r1;                                        \
> > +       r1 = *(u32*)(r9 + %[__sk_buff_data]);           \
> > +       r2 = *(u32*)(r9 + %[__sk_buff_data_end]);       \
> > +       r3 = r1;                                        \
> > +       r3 += 8;                                        \
> > +       if r3 != r2 goto 1f;                            \
> > +       r3 += 8;                                        \
> > +       if r3 != r2 goto 1f;                            \
> > +       r1 = *(u64 *)(r1 + 0);                          \
> > +1:                                                     \
> > +       r0 = 0;                                         \
> > +       exit;                                           \
> > +"      :
> > +       : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)),
> > +         __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end))
> > +       : __clobber_all);
> > +}
> > 
> > 
> > The verifier output:
> > func#0 @0
> > Global function data_plus_const_neq_pkt_end() doesn't return scalar. Only those are supported.
> > 0: R1=ctx() R10=fp0
> > ; asm volatile ("                                       \
> > 0: (bf) r9 = r1                       ; R1=ctx() R9_w=ctx()
> > 1: (61) r1 = *(u32 *)(r9 +76)         ; R1_w=pkt(r=0) R9_w=ctx()
> > 2: (61) r2 = *(u32 *)(r9 +80)         ; R2_w=pkt_end() R9_w=ctx()
> > 3: (bf) r3 = r1                       ; R1_w=pkt(r=0) R3_w=pkt(r=0)
> > 4: (07) r3 += 8                       ; R3_w=pkt(off=8,r=0)
> > 5: (5d) if r3 != r2 goto pc+3         ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)
> > 6: (07) r3 += 8                       ; R3_w=pkt(off=16,r=0xffffffffffffffff)
> > 7: (5d) if r3 != r2 goto pc+1         ; R2_w=pkt_end() R3_w=pkt(off=16,r=0xffffffffffffffff)
> > 8: (79) r1 = *(u64 *)(r1 +0)          ; R1=scalar()
> > 9: (b7) r0 = 0                        ; R0_w=0
> > 10: (95) exit
> > 
> > from 7 to 9: safe
> > 
> > from 5 to 9: safe
> > processed 13 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 0
> > 
> > insn 5, for this_branch (straight one), r3 range will be 8 and assuming pkt_end is 8.
> > insn 7, r3 range becomes 18 and then we assume pkt_end is 16.
> > 
> > I guess we should handle this case. For branch 5 and 7, it cannot be that both will be true.
> 
> This is an interesting case.
> reg->range is set to AT_PKT_END or BEYOND_PKT_END only in
> try_match_pkt_pointers() (in mark_pkt_end() call).
> And this range mark appears not to be reset by += operation
> (which might add a negative number as well).
> So, once r3 is marked AT_PKT_END it would remain so
> even after r3 += 8, which is obviously not true.
> Not sure what to do yet.

Here is another example which is currently not handled correctly,
even w/o my patch:

SEC("tc")
__success
__naked void pkt_vs_pkt_end_with_bound_change(void)
{
	asm volatile ("					\
	r9 = r1;					\
	r0 = 0;						\
	r1 = *(u32*)(r9 + %[__sk_buff_data]);		\
	r2 = *(u32*)(r9 + %[__sk_buff_data_end]);	\
	r3 = r1;					\
	r3 += 8;					\
	if r3 <= r2 goto 1f;				\
	r3 -= 8;					\
	if r3 >= r2 goto 1f;				\
	r4 = *(u64 *)(r1 + 0);				\
1:	exit;						\
"	:
	: __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)),
	  __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end))
	: __clobber_all);
}

Verifier log:

  0: R1=ctx() R10=fp0
  ; asm volatile ("					\
  0: (bf) r9 = r1                       ; R1=ctx() R9_w=ctx()
  1: (b7) r0 = 0                        ; R0_w=0
  2: (61) r1 = *(u32 *)(r9 +76)         ; R1_w=pkt(r=0) R9_w=ctx()
  3: (61) r2 = *(u32 *)(r9 +80)         ; R2_w=pkt_end() R9_w=ctx()
  4: (bf) r3 = r1                       ; R1_w=pkt(r=0) R3_w=pkt(r=0)
  5: (07) r3 += 8                       ; R3_w=pkt(off=8,r=0)
  6: (bd) if r3 <= r2 goto pc+3         ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xfffffffffffffffe)
  7: (17) r3 -= 8                       ; R3_w=pkt(r=0xfffffffffffffffe)
  8: (3d) if r3 >= r2 goto pc+1         ; R2_w=pkt_end() R3_w=pkt(r=0xfffffffffffffffe)
  10: (95) exit

  from 6 to 10: safe
  processed 11 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

At (6) for this_branch r3 is marked BEYOND_PKT_END,
       packet range is known to be 8;
at (7) it is changed to point back to start of the packet;
at (8) is_pkt_ptr_branch_taken() incorrectly predicts that
       r3 >= r2 (r3 - packet start, r2 - packet end).