[PATCH bpf-next 0/3] infer packet range for 'if pkt ==/!= pkt_end' instructions

[PATCH bpf-next 0/3] infer packet range for 'if pkt ==/!= pkt_end' instructions

[Eduard Zingerman]

As suggested by Maciej Żenczykowski in [1], extend try_match_pkt_pointers
to allow verification of BPF, generated for C code like below:

  if (data + 42 != data_end) { ... }

Also simplify try_match_pkt_pointers to avoid checking both
'pkt <op> pkt_end' and 'pkt_end <op> pkt' conditions,
as suggested by Andrii Nakryiko.

[1] https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/

Eduard Zingerman (3):
  bpf: simplify try_match_pkt_pointers()
  bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
  selftests/bpf: test packet range inference for 'if pkt ==/!= pkt_end'

 kernel/bpf/verifier.c                         | 112 ++++----------
 .../bpf/progs/verifier_direct_packet_access.c | 138 ++++++++++++++++++
 2 files changed, 170 insertions(+), 80 deletions(-)

-- 
2.43.0

[PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()

[Eduard Zingerman]

Reduce number of cases handled in try_match_pkt_pointers()
to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data>
by flipping opcode.

Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 104 ++++++++++--------------------------------
 1 file changed, 24 insertions(+), 80 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index adbf330d364b..918e6a7912e2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 				   struct bpf_verifier_state *this_branch,
 				   struct bpf_verifier_state *other_branch)
 {
+	int opcode = BPF_OP(insn->code);
+	int dst_regno = insn->dst_reg;
+
 	if (BPF_SRC(insn->code) != BPF_X)
 		return false;
 
@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 	if (BPF_CLASS(insn->code) == BPF_JMP32)
 		return false;
 
-	switch (BPF_OP(insn->code)) {
+	if (dst_reg->type == PTR_TO_PACKET_END ||
+	    src_reg->type == PTR_TO_PACKET_META) {
+		swap(src_reg, dst_reg);
+		dst_regno = insn->src_reg;
+		opcode = flip_opcode(opcode);
+	}
+
+	if ((dst_reg->type != PTR_TO_PACKET ||
+	     src_reg->type != PTR_TO_PACKET_END) &&
+	    (dst_reg->type != PTR_TO_PACKET_META ||
+	     !reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET)))
+		return false;
+
+	switch (opcode) {
 	case BPF_JGT:
-		if ((dst_reg->type == PTR_TO_PACKET &&
-		     src_reg->type == PTR_TO_PACKET_END) ||
-		    (dst_reg->type == PTR_TO_PACKET_META &&
-		     reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
-			/* pkt_data' > pkt_end, pkt_meta' > pkt_data */
-			find_good_pkt_pointers(this_branch, dst_reg,
-					       dst_reg->type, false);
-			mark_pkt_end(other_branch, insn->dst_reg, true);
-		} else if ((dst_reg->type == PTR_TO_PACKET_END &&
-			    src_reg->type == PTR_TO_PACKET) ||
-			   (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
-			    src_reg->type == PTR_TO_PACKET_META)) {
-			/* pkt_end > pkt_data', pkt_data > pkt_meta' */
-			find_good_pkt_pointers(other_branch, src_reg,
-					       src_reg->type, true);
-			mark_pkt_end(this_branch, insn->src_reg, false);
-		} else {
-			return false;
-		}
-		break;
-	case BPF_JLT:
-		if ((dst_reg->type == PTR_TO_PACKET &&
-		     src_reg->type == PTR_TO_PACKET_END) ||
-		    (dst_reg->type == PTR_TO_PACKET_META &&
-		     reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
-			/* pkt_data' < pkt_end, pkt_meta' < pkt_data */
-			find_good_pkt_pointers(other_branch, dst_reg,
-					       dst_reg->type, true);
-			mark_pkt_end(this_branch, insn->dst_reg, false);
-		} else if ((dst_reg->type == PTR_TO_PACKET_END &&
-			    src_reg->type == PTR_TO_PACKET) ||
-			   (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
-			    src_reg->type == PTR_TO_PACKET_META)) {
-			/* pkt_end < pkt_data', pkt_data > pkt_meta' */
-			find_good_pkt_pointers(this_branch, src_reg,
-					       src_reg->type, false);
-			mark_pkt_end(other_branch, insn->src_reg, true);
-		} else {
-			return false;
-		}
-		break;
 	case BPF_JGE:
-		if ((dst_reg->type == PTR_TO_PACKET &&
-		     src_reg->type == PTR_TO_PACKET_END) ||
-		    (dst_reg->type == PTR_TO_PACKET_META &&
-		     reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
-			/* pkt_data' >= pkt_end, pkt_meta' >= pkt_data */
-			find_good_pkt_pointers(this_branch, dst_reg,
-					       dst_reg->type, true);
-			mark_pkt_end(other_branch, insn->dst_reg, false);
-		} else if ((dst_reg->type == PTR_TO_PACKET_END &&
-			    src_reg->type == PTR_TO_PACKET) ||
-			   (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
-			    src_reg->type == PTR_TO_PACKET_META)) {
-			/* pkt_end >= pkt_data', pkt_data >= pkt_meta' */
-			find_good_pkt_pointers(other_branch, src_reg,
-					       src_reg->type, false);
-			mark_pkt_end(this_branch, insn->src_reg, true);
-		} else {
-			return false;
-		}
+		/* pkt_data >/>= pkt_end, pkt_meta >/>= pkt_data */
+		find_good_pkt_pointers(this_branch, dst_reg, dst_reg->type, opcode == BPF_JGE);
+		mark_pkt_end(other_branch, dst_regno, opcode == BPF_JGT);
 		break;
+	case BPF_JLT:
 	case BPF_JLE:
-		if ((dst_reg->type == PTR_TO_PACKET &&
-		     src_reg->type == PTR_TO_PACKET_END) ||
-		    (dst_reg->type == PTR_TO_PACKET_META &&
-		     reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
-			/* pkt_data' <= pkt_end, pkt_meta' <= pkt_data */
-			find_good_pkt_pointers(other_branch, dst_reg,
-					       dst_reg->type, false);
-			mark_pkt_end(this_branch, insn->dst_reg, true);
-		} else if ((dst_reg->type == PTR_TO_PACKET_END &&
-			    src_reg->type == PTR_TO_PACKET) ||
-			   (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
-			    src_reg->type == PTR_TO_PACKET_META)) {
-			/* pkt_end <= pkt_data', pkt_data <= pkt_meta' */
-			find_good_pkt_pointers(this_branch, src_reg,
-					       src_reg->type, true);
-			mark_pkt_end(other_branch, insn->src_reg, false);
-		} else {
-			return false;
-		}
+		/* pkt_data </<= pkt_end, pkt_meta </<= pkt_data */
+		find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
+		mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
 		break;
 	default:
 		return false;
-- 
2.43.0

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

[Eduard Zingerman]

Extend try_match_pkt_pointers() to handle == and != operations.
For instruction:

      .--------------- pointer to packet with some range R
      |     .--------- pointer to packet end
      v     v
  if rA == rB goto ...

It is valid to infer that R bytes are available in packet.
This change should allow verification of BPF generated for
C code like below:

  if (data + 42 != data_end) { ... }

Suggested-by: Maciej Żenczykowski <zenczykowski@gmail.com>
Link: https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 918e6a7912e2..b229ba0ad114 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 				   struct bpf_verifier_state *this_branch,
 				   struct bpf_verifier_state *other_branch)
 {
+	struct bpf_verifier_state *eq_branch;
 	int opcode = BPF_OP(insn->code);
 	int dst_regno = insn->dst_reg;
 
@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 		find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
 		mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
 		break;
+	case BPF_JEQ:
+	case BPF_JNE:
+		/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
+		eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
+		find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
+		mark_pkt_end(eq_branch, dst_regno, false);
+		break;
 	default:
 		return false;
 	}
-- 
2.43.0

[PATCH bpf-next 3/3] selftests/bpf: test packet range inference for 'if pkt ==/!= pkt_end'

[Eduard Zingerman]

Check that the following cases are handled by verifier:
- packet access after 'if pkt_data + const != pkt_end'
  (positive and negative cases);
- packet access after 'if pkt_data + const == pkt_end'
  (positive and negative cases);
- packet metadata access after 'if pkt_meta + const != pkt_data';
- packet metadata access after 'if pkt_data != pkt_meta + const';

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/progs/verifier_direct_packet_access.c | 138 ++++++++++++++++++
 1 file changed, 138 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_direct_packet_access.c b/tools/testing/selftests/bpf/progs/verifier_direct_packet_access.c
index be95570ab382..0ee99d7bc846 100644
--- a/tools/testing/selftests/bpf/progs/verifier_direct_packet_access.c
+++ b/tools/testing/selftests/bpf/progs/verifier_direct_packet_access.c
@@ -800,4 +800,142 @@ l0_%=:	/* exit(0) */					\
 	: __clobber_all);
 }
 
+SEC("tc")
+__success __log_level(2)
+__msg("if r3 != r2 goto pc+1         ; 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;				\
+	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);
+}
+
+SEC("tc")
+__failure __log_level(2)
+__msg("8: R1=pkt(r=0) R2=pkt_end() R3=pkt(off=8,r=0)")
+__msg("invalid access to packet, off=0 size=8, R1(id=0,off=0,r=0)")
+__naked void data_plus_const_neq_pkt_end_negative(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;				\
+	r0 = 0;						\
+	exit;						\
+1:							\
+	r1 = *(u64 *)(r1 + 0);				\
+	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);
+}
+
+SEC("tc")
+__success __log_level(2)
+__msg("8: R1=pkt(r=9) R2=pkt_end() R3=pkt(off=8,r=0xffffffffffffffff)")
+__naked void data_plus_const_eq_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;				\
+	r0 = 0;						\
+	exit;						\
+1:							\
+	r1 = *(u64 *)(r1 + 0);				\
+	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);
+}
+
+SEC("tc")
+__failure __log_level(2)
+__msg("if r3 == r2 goto pc+3         ; R2_w=pkt_end() R3_w=pkt(off=8,r=0)")
+__msg("invalid access to packet, off=0 size=8, R1(id=0,off=0,r=0)")
+__naked void data_plus_const_eq_pkt_end_negative(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;				\
+	r1 = *(u64 *)(r1 + 0);				\
+	r0 = 0;						\
+	exit;						\
+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);
+}
+
+SEC("tc")
+__success
+__naked void pkt_meta_plus_const_neq_pkt_data(void)
+{
+	asm volatile ("					\
+	r9 = r1;					\
+	r1 = *(u32*)(r9 + %[__sk_buff_data_meta]);	\
+	r2 = *(u32*)(r9 + %[__sk_buff_data]);		\
+	r3 = r1;					\
+	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_meta, offsetof(struct __sk_buff, data_meta))
+	: __clobber_all);
+}
+
+SEC("tc")
+__success
+__naked void pkt_data_neq_pkt_meta_plus_const(void)
+{
+	asm volatile ("					\
+	r9 = r1;					\
+	r1 = *(u32*)(r9 + %[__sk_buff_data_meta]);	\
+	r2 = *(u32*)(r9 + %[__sk_buff_data]);		\
+	r3 = r1;					\
+	r3 += 8;					\
+	if r2 != r3 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_meta, offsetof(struct __sk_buff, data_meta))
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

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

[Maciej Żenczykowski]

(I've looked at all 3 patches, and they seem fine... but I don't claim
to understand the intricacies of the verifier/registers/etc well
enough to be certain)

On Mon, Jan 8, 2024 at 5:28 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Extend try_match_pkt_pointers() to handle == and != operations.
> For instruction:
>
>       .--------------- pointer to packet with some range R
>       |     .--------- pointer to packet end
>       v     v
>   if rA == rB goto ...

it's possible this would be better without the 'goto' as just 'if (rA
== rB) ...'

>
> It is valid to infer that R bytes are available in packet.
> This change should allow verification of BPF generated for
> C code like below:
>
>   if (data + 42 != data_end) { ... }

this should probably be:
  if (data + 42 != data_end) return;
  ...

>
> Suggested-by: Maciej Żenczykowski <zenczykowski@gmail.com>
> Link: https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 8 ++++++++
>  1 file changed, 8 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 918e6a7912e2..b229ba0ad114 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>                                    struct bpf_verifier_state *this_branch,
>                                    struct bpf_verifier_state *other_branch)
>  {
> +       struct bpf_verifier_state *eq_branch;
>         int opcode = BPF_OP(insn->code);
>         int dst_regno = insn->dst_reg;
>
> @@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>                 find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
>                 mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
>                 break;
> +       case BPF_JEQ:
> +       case BPF_JNE:
> +               /* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
> +               eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
> +               find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
> +               mark_pkt_end(eq_branch, dst_regno, false);
> +               break;
>         default:
>                 return false;
>         }
> --
> 2.43.0
>

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

[Eduard Zingerman]

On Mon, 2024-01-08 at 05:49 -0800, Maciej Żenczykowski wrote:
> (I've looked at all 3 patches, and they seem fine... but I don't claim
> to understand the intricacies of the verifier/registers/etc well
> enough to be certain)

Thank you.

> On Mon, Jan 8, 2024 at 5:28 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > Extend try_match_pkt_pointers() to handle == and != operations.
> > For instruction:
> > 
> >       .--------------- pointer to packet with some range R
> >       |     .--------- pointer to packet end
> >       v     v
> >   if rA == rB goto ...
> 
> it's possible this would be better without the 'goto' as just 'if (rA
> == rB) ...'

The idea was to show this as BPF asm instruction, which has syntax
'if rA == rB goto C'. I'll wait for more feedback and submit v2
with updated commit message to make it more clear.

> > It is valid to infer that R bytes are available in packet.
> > This change should allow verification of BPF generated for
> > C code like below:
> > 
> >   if (data + 42 != data_end) { ... }
> 
> this should probably be:
>   if (data + 42 != data_end) return;
>   ...

Makes sense, will update commit message.

Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()

[Andrii Nakryiko]

On Mon, Jan 8, 2024 at 5:28 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Reduce number of cases handled in try_match_pkt_pointers()
> to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data>
> by flipping opcode.
>
> Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 104 ++++++++++--------------------------------
>  1 file changed, 24 insertions(+), 80 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index adbf330d364b..918e6a7912e2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>                                    struct bpf_verifier_state *this_branch,
>                                    struct bpf_verifier_state *other_branch)
>  {
> +       int opcode = BPF_OP(insn->code);
> +       int dst_regno = insn->dst_reg;
> +
>         if (BPF_SRC(insn->code) != BPF_X)
>                 return false;
>
> @@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>         if (BPF_CLASS(insn->code) == BPF_JMP32)
>                 return false;
>
> -       switch (BPF_OP(insn->code)) {
> +       if (dst_reg->type == PTR_TO_PACKET_END ||
> +           src_reg->type == PTR_TO_PACKET_META) {
> +               swap(src_reg, dst_reg);
> +               dst_regno = insn->src_reg;
> +               opcode = flip_opcode(opcode);
> +       }
> +
> +       if ((dst_reg->type != PTR_TO_PACKET ||
> +            src_reg->type != PTR_TO_PACKET_END) &&
> +           (dst_reg->type != PTR_TO_PACKET_META ||
> +            !reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET)))
> +               return false;

this inverted original condition just breaks my brain, I can't wrap my
head around it :) I think the original is easier to reason about
because it's two clear allowable patterns for which we do something. I
understand that this early exit reduces nestedness, but at least for
me it would be simpler to have the original non-inverted condition
with a nested switch.


> +
> +       switch (opcode) {
>         case BPF_JGT:
> -               if ((dst_reg->type == PTR_TO_PACKET &&
> -                    src_reg->type == PTR_TO_PACKET_END) ||
> -                   (dst_reg->type == PTR_TO_PACKET_META &&
> -                    reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
> -                       /* pkt_data' > pkt_end, pkt_meta' > pkt_data */
> -                       find_good_pkt_pointers(this_branch, dst_reg,
> -                                              dst_reg->type, false);
> -                       mark_pkt_end(other_branch, insn->dst_reg, true);
> -               } else if ((dst_reg->type == PTR_TO_PACKET_END &&
> -                           src_reg->type == PTR_TO_PACKET) ||
> -                          (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
> -                           src_reg->type == PTR_TO_PACKET_META)) {
> -                       /* pkt_end > pkt_data', pkt_data > pkt_meta' */
> -                       find_good_pkt_pointers(other_branch, src_reg,
> -                                              src_reg->type, true);
> -                       mark_pkt_end(this_branch, insn->src_reg, false);
> -               } else {
> -                       return false;
> -               }
> -               break;

[...]

Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()

[Andrii Nakryiko]

On Mon, Jan 8, 2024 at 4:40 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Jan 8, 2024 at 5:28 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > Reduce number of cases handled in try_match_pkt_pointers()
> > to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data>
> > by flipping opcode.
> >
> > Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  kernel/bpf/verifier.c | 104 ++++++++++--------------------------------
> >  1 file changed, 24 insertions(+), 80 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index adbf330d364b..918e6a7912e2 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >                                    struct bpf_verifier_state *this_branch,
> >                                    struct bpf_verifier_state *other_branch)
> >  {
> > +       int opcode = BPF_OP(insn->code);
> > +       int dst_regno = insn->dst_reg;
> > +
> >         if (BPF_SRC(insn->code) != BPF_X)
> >                 return false;
> >
> > @@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >         if (BPF_CLASS(insn->code) == BPF_JMP32)
> >                 return false;
> >
> > -       switch (BPF_OP(insn->code)) {
> > +       if (dst_reg->type == PTR_TO_PACKET_END ||
> > +           src_reg->type == PTR_TO_PACKET_META) {
> > +               swap(src_reg, dst_reg);
> > +               dst_regno = insn->src_reg;
> > +               opcode = flip_opcode(opcode);
> > +       }
> > +
> > +       if ((dst_reg->type != PTR_TO_PACKET ||
> > +            src_reg->type != PTR_TO_PACKET_END) &&
> > +           (dst_reg->type != PTR_TO_PACKET_META ||
> > +            !reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET)))
> > +               return false;
>
> this inverted original condition just breaks my brain, I can't wrap my
> head around it :) I think the original is easier to reason about
> because it's two clear allowable patterns for which we do something. I
> understand that this early exit reduces nestedness, but at least for
> me it would be simpler to have the original non-inverted condition
> with a nested switch.
>
>
> > +
> > +       switch (opcode) {
> >         case BPF_JGT:
> > -               if ((dst_reg->type == PTR_TO_PACKET &&
> > -                    src_reg->type == PTR_TO_PACKET_END) ||
> > -                   (dst_reg->type == PTR_TO_PACKET_META &&
> > -                    reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
> > -                       /* pkt_data' > pkt_end, pkt_meta' > pkt_data */
> > -                       find_good_pkt_pointers(this_branch, dst_reg,
> > -                                              dst_reg->type, false);
> > -                       mark_pkt_end(other_branch, insn->dst_reg, true);

it seems like you can make a bit of simplification if mark_pkt_end
would just accept struct bpf_reg_state * instead of int regn (you
won't need to keep track of dst_regno at all, right?)

> > -               } else if ((dst_reg->type == PTR_TO_PACKET_END &&
> > -                           src_reg->type == PTR_TO_PACKET) ||
> > -                          (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
> > -                           src_reg->type == PTR_TO_PACKET_META)) {
> > -                       /* pkt_end > pkt_data', pkt_data > pkt_meta' */
> > -                       find_good_pkt_pointers(other_branch, src_reg,
> > -                                              src_reg->type, true);
> > -                       mark_pkt_end(this_branch, insn->src_reg, false);
> > -               } else {
> > -                       return false;
> > -               }
> > -               break;
>
> [...]

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

[Andrii Nakryiko]

On Mon, Jan 8, 2024 at 5:28 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Extend try_match_pkt_pointers() to handle == and != operations.
> For instruction:
>
>       .--------------- pointer to packet with some range R
>       |     .--------- pointer to packet end
>       v     v
>   if rA == rB goto ...
>
> It is valid to infer that R bytes are available in packet.
> This change should allow verification of BPF generated for
> C code like below:
>
>   if (data + 42 != data_end) { ... }
>
> Suggested-by: Maciej Żenczykowski <zenczykowski@gmail.com>
> Link: https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 8 ++++++++
>  1 file changed, 8 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 918e6a7912e2..b229ba0ad114 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>                                    struct bpf_verifier_state *this_branch,
>                                    struct bpf_verifier_state *other_branch)
>  {
> +       struct bpf_verifier_state *eq_branch;
>         int opcode = BPF_OP(insn->code);
>         int dst_regno = insn->dst_reg;
>
> @@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>                 find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
>                 mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
>                 break;
> +       case BPF_JEQ:
> +       case BPF_JNE:
> +               /* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
> +               eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
> +               find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
> +               mark_pkt_end(eq_branch, dst_regno, false);

hm... if pkt_data != pkt_end in this_branch, can we really infer
whether reg->range is BEYOND_PKT_END or AT_PKT_END? What if it's
IN_FRONT_OF_PKT_END?

> +               break;
>         default:
>                 return false;
>         }
> --
> 2.43.0
>

Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()

[Eduard Zingerman]

On Mon, 2024-01-08 at 16:40 -0800, Andrii Nakryiko wrote:
[...]
> > @@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >         if (BPF_CLASS(insn->code) == BPF_JMP32)
> >                 return false;
> > 
> > -       switch (BPF_OP(insn->code)) {
> > +       if (dst_reg->type == PTR_TO_PACKET_END ||
> > +           src_reg->type == PTR_TO_PACKET_META) {
> > +               swap(src_reg, dst_reg);
> > +               dst_regno = insn->src_reg;
> > +               opcode = flip_opcode(opcode);
> > +       }
> > +
> > +       if ((dst_reg->type != PTR_TO_PACKET ||
> > +            src_reg->type != PTR_TO_PACKET_END) &&
> > +           (dst_reg->type != PTR_TO_PACKET_META ||
> > +            !reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET)))
> > +               return false;
> 
> this inverted original condition just breaks my brain, I can't wrap my
> head around it :) I think the original is easier to reason about
> because it's two clear allowable patterns for which we do something. I
> understand that this early exit reduces nestedness, but at least for
> me it would be simpler to have the original non-inverted condition
> with a nested switch.

I'm not sure I understand what you mean by nested switch.
If I write it down like below, would that be more clear?

	bool pkt_data_vs_pkt_end;
    bool pkt_meta_vs_pkt_data;
    ...
    pkt_data_vs_pkt_end =
      dst_reg->type == PTR_TO_PACKET && src_reg->type == PTR_TO_PACKET_END;
    pkt_meta_vs_pkt_data =
      dst_reg->type == PTR_TO_PACKET_META && reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET);

    if (!pkt_data_vs_pkt_end && !pkt_meta_vs_pkt_data)
        return false;

> > +
> > +       switch (opcode) {
> >         case BPF_JGT:
> > -               if ((dst_reg->type == PTR_TO_PACKET &&
> > -                    src_reg->type == PTR_TO_PACKET_END) ||
> > -                   (dst_reg->type == PTR_TO_PACKET_META &&
> > -                    reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
> > -                       /* pkt_data' > pkt_end, pkt_meta' > pkt_data */
> > -                       find_good_pkt_pointers(this_branch, dst_reg,
> > -                                              dst_reg->type, false);
> > -                       mark_pkt_end(other_branch, insn->dst_reg, true);

> it seems like you can make a bit of simplification if mark_pkt_end
> would just accept struct bpf_reg_state * instead of int regn (you
> won't need to keep track of dst_regno at all, right?)

mark_pkt_end() changes the register from either this_branch or other_branch.
I can introduce local pointers dst_this/dst_other and swap those,
but I'm not sure it's worth it.

[...]

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

[Eduard Zingerman]

On Mon, 2024-01-08 at 16:45 -0800, Andrii Nakryiko wrote:
[...]
> > @@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >                 find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
> >                 mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
> >                 break;
> > +       case BPF_JEQ:
> > +       case BPF_JNE:
> > +               /* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
> > +               eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
> > +               find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
> > +               mark_pkt_end(eq_branch, dst_regno, false);
> 
> hm... if pkt_data != pkt_end in this_branch, can we really infer
> whether reg->range is BEYOND_PKT_END or AT_PKT_END? What if it's
> IN_FRONT_OF_PKT_END?

pkt_data != pkt_end in this_branch means that there is an instruction:

  ...
  if pkt_data == pkt_end goto <other_branch>
  ... <this_branch> ...

the 'eq_branch' would be set to 'other_branch' and AT_PKT_END would be set
for dst register in 'other_branch'. What's wrong with this?
Or did you mean something else?

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

[Yonghong Song]

On 1/8/24 5:28 AM, Eduard Zingerman wrote:
> Extend try_match_pkt_pointers() to handle == and != operations.
> For instruction:
>
>        .--------------- pointer to packet with some range R
>        |     .--------- pointer to packet end
>        v     v
>    if rA == rB goto ...
>
> It is valid to infer that R bytes are available in packet.
> This change should allow verification of BPF generated for
> C code like below:
>
>    if (data + 42 != data_end) { ... }
>
> Suggested-by: Maciej Żenczykowski <zenczykowski@gmail.com>
> Link: https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>   kernel/bpf/verifier.c | 8 ++++++++
>   1 file changed, 8 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 918e6a7912e2..b229ba0ad114 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>   				   struct bpf_verifier_state *this_branch,
>   				   struct bpf_verifier_state *other_branch)
>   {
> +	struct bpf_verifier_state *eq_branch;
>   	int opcode = BPF_OP(insn->code);
>   	int dst_regno = insn->dst_reg;
>   
> @@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>   		find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
>   		mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
>   		break;
> +	case BPF_JEQ:
> +	case BPF_JNE:
> +		/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
> +		eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
> +		find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
> +		mark_pkt_end(eq_branch, dst_regno, false);
> +		break;

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.

>   	default:
>   		return false;
>   	}

Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()

[Andrii Nakryiko]

On Mon, Jan 8, 2024 at 4:52 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-01-08 at 16:40 -0800, Andrii Nakryiko wrote:
> [...]
> > > @@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> > >         if (BPF_CLASS(insn->code) == BPF_JMP32)
> > >                 return false;
> > >
> > > -       switch (BPF_OP(insn->code)) {
> > > +       if (dst_reg->type == PTR_TO_PACKET_END ||
> > > +           src_reg->type == PTR_TO_PACKET_META) {
> > > +               swap(src_reg, dst_reg);
> > > +               dst_regno = insn->src_reg;
> > > +               opcode = flip_opcode(opcode);
> > > +       }
> > > +
> > > +       if ((dst_reg->type != PTR_TO_PACKET ||
> > > +            src_reg->type != PTR_TO_PACKET_END) &&
> > > +           (dst_reg->type != PTR_TO_PACKET_META ||
> > > +            !reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET)))
> > > +               return false;
> >
> > this inverted original condition just breaks my brain, I can't wrap my
> > head around it :) I think the original is easier to reason about
> > because it's two clear allowable patterns for which we do something. I
> > understand that this early exit reduces nestedness, but at least for
> > me it would be simpler to have the original non-inverted condition
> > with a nested switch.
>
> I'm not sure I understand what you mean by nested switch.
> If I write it down like below, would that be more clear?
>

Yes, much more clear. What I had in mind was something like:

if (pkt_data_vs_pkt_end || pkt_meta_vs_pkt_data) {
    switch (opcode) {
        ...
    }
}

But what you have below is easy to follow as well


>         bool pkt_data_vs_pkt_end;
>     bool pkt_meta_vs_pkt_data;
>     ...
>     pkt_data_vs_pkt_end =
>       dst_reg->type == PTR_TO_PACKET && src_reg->type == PTR_TO_PACKET_END;
>     pkt_meta_vs_pkt_data =
>       dst_reg->type == PTR_TO_PACKET_META && reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET);
>
>     if (!pkt_data_vs_pkt_end && !pkt_meta_vs_pkt_data)
>         return false;
>
> > > +
> > > +       switch (opcode) {
> > >         case BPF_JGT:
> > > -               if ((dst_reg->type == PTR_TO_PACKET &&
> > > -                    src_reg->type == PTR_TO_PACKET_END) ||
> > > -                   (dst_reg->type == PTR_TO_PACKET_META &&
> > > -                    reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
> > > -                       /* pkt_data' > pkt_end, pkt_meta' > pkt_data */
> > > -                       find_good_pkt_pointers(this_branch, dst_reg,
> > > -                                              dst_reg->type, false);
> > > -                       mark_pkt_end(other_branch, insn->dst_reg, true);
>
> > it seems like you can make a bit of simplification if mark_pkt_end
> > would just accept struct bpf_reg_state * instead of int regn (you
> > won't need to keep track of dst_regno at all, right?)
>
> mark_pkt_end() changes the register from either this_branch or other_branch.
> I can introduce local pointers dst_this/dst_other and swap those,
> but I'm not sure it's worth it.

Ah, I missed that it's other_branch register. Never mind then, it's
fine and it was minor anyways.

>
> [...]

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

[Andrii Nakryiko]

On Mon, Jan 8, 2024 at 4:57 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-01-08 at 16:45 -0800, Andrii Nakryiko wrote:
> [...]
> > > @@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> > >                 find_good_pkt_pointers(other_branch, dst_reg, dst_reg->type, opcode == BPF_JLT);
> > >                 mark_pkt_end(this_branch, dst_regno, opcode == BPF_JLE);
> > >                 break;
> > > +       case BPF_JEQ:
> > > +       case BPF_JNE:
> > > +               /* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */
> > > +               eq_branch = opcode == BPF_JEQ ? other_branch : this_branch;
> > > +               find_good_pkt_pointers(eq_branch, dst_reg, dst_reg->type, true);
> > > +               mark_pkt_end(eq_branch, dst_regno, false);
> >
> > hm... if pkt_data != pkt_end in this_branch, can we really infer
> > whether reg->range is BEYOND_PKT_END or AT_PKT_END? What if it's
> > IN_FRONT_OF_PKT_END?
>
> pkt_data != pkt_end in this_branch means that there is an instruction:
>
>   ...
>   if pkt_data == pkt_end goto <other_branch>
>   ... <this_branch> ...
>
> the 'eq_branch' would be set to 'other_branch' and AT_PKT_END would be set
> for dst register in 'other_branch'. What's wrong with this?
> Or did you mean something else?

Well, first off, I'm very unfamiliar with all these pkt_xxx registers,
so excuse me for stupid questions. I guess what got me confused was
that find_good_pkt_pointer() and mark_pkt_end() previously (for
GT/GE/LT/LE) were working on opposing branches. But here I see they
work on the same "equal" branch. But now I'm wondering what's the
point of even calling find_good_pkt_pointer()? Is there a scenario
where it can derive new information from JEQ/JNE?

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

[Eduard Zingerman]

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.

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

[Eduard Zingerman]

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).