Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-03 Thread William Tu 
On Thu, Feb 2, 2017 at 10:19 PM, Alexei Starovoitov
 wrote:
> On Thu, Feb 02, 2017 at 09:31:06PM -0800, William Tu wrote:
>>
>> Yes, this is auto-generated. We want to use P4 2016 as front end to
>> generate ebpf for XDP.
>
> P4 2016 front-end ? is it public? Is there a 2017 version? ;)
> just curious.
>
the P4_16 is the latest version.
https://github.com/p4lang/p4c
it has ebpf backend for tc, we want to add ebpf backend for xdp.

--William

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-03 Thread Daniel Borkmann 

On 02/03/2017 06:31 AM, William Tu wrote:
[...]

Yes, this is auto-generated. We want to use P4 2016 as front end to
generate ebpf for XDP.


[...]

R2 is no longer pkt_end, it's R2 == R0 == 0
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2

So at line 272, it's pkt_ptr = pkt_ptr + 0
thus the following fix works for us.
-   if (imm <= 0) {
+   if (imm < 0) {


Okay, makes sense. I'll wait with ACK for your respin with kselftest
case.

Thanks,
Daniel

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread Alexei Starovoitov 
On Thu, Feb 02, 2017 at 09:31:06PM -0800, William Tu wrote:
> 
> Yes, this is auto-generated. We want to use P4 2016 as front end to
> generate ebpf for XDP.

P4 2016 front-end ? is it public? Is there a 2017 version? ;)
just curious.

> >
> > The line 272 is r4 += r2
> > where R4=imm4 and R2=pkt_end
> 
> R2 is no longer pkt_end, it's R2 == R0 == 0
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
> 
> So at line 272, it's pkt_ptr = pkt_ptr + 0
> thus the following fix works for us.
> -   if (imm <= 0) {
> +   if (imm < 0) {

got it. I forgot that we have:
  if (src_reg->type == CONST_IMM) {
  /* pkt_ptr += reg where reg is known constant */
  imm = src_reg->imm;
  goto add_imm;
  }
and got confused by if (BPF_SRC(insn->code) == BPF_K) bit.
Thanks for explaining!
Could you respin with the extra test for it in the test_verifier.c ?
Since it's a rare case, would be good to keep it working.

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread William Tu 
On Thu, Feb 2, 2017 at 7:46 PM, Alexei Starovoitov
 wrote:
> On Thu, Feb 02, 2017 at 07:26:44PM -0800, William Tu wrote:
>> Thanks. below is my program. The verifier fails at line 272, when
>> writing to ICMP header.
>> -
>> ; ebpf_packetEnd = ((void*)(long)skb->data_end);
>>  206:   r2 = *(u32 *)(r6 + 4)
>> ; ebpf_packetStart = ((void*)(long)skb->data);
>>  207:   r1 = *(u32 *)(r6 + 0)
>> ...
>> r10 is "struct hd" at local stack
>> r1 is skb->data
>> ...
>> ; if (hd.icmp.ebpf_valid) {
>>  261:   r4 = *(u64 *)(r10 - 40)
>>  262:   if r4 == 0 goto 29
>> ; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 
>> 32)) {
>>  263:   r4 = r0
>>  264:   r4 += 32
>>  265:   r4 >>= 3
>>  266:   r5 = r1
>>  267:   r5 += r4
>>  268:   if r5 > r2 goto 23
>> ; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
>> (ebpf_byte) << 0);
>>  269:   r2 = r0
>>  270:   r2 >>= 3
>>  271:   r4 = r1
>>  272:   r4 += r2
>>  273:   r2 = *(u64 *)(r10 - 80)
>>  274:   *(u8 *)(r4 + 0) = r2
>>
>> verifier log
>> 
>> from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
>> R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
>> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 260: (bf) r0 = r7
>> 261: (79) r4 = *(u64 *)(r10 -40)
>> 262: (15) if r4 == 0x0 goto pc+29
>>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
>> R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
>> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 263: (bf) r4 = r0
>> 264: (07) r4 += 32
>> 265: (77) r4 >>= 3
>> 266: (bf) r5 = r1
>> 267: (0f) r5 += r4
>> 268: (2d) if r5 > r2 goto pc+23
>>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
>> R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
>> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
>> R10=fp
>> 269: (bf) r2 = r0
>> 270: (77) r2 >>= 3
>> 271: (bf) r4 = r1
>> 272: (0f) r4 += r2
>> 273: (79) r2 = *(u64 *)(r10 -80)
>> 274: (73) *(u8 *)(r4 +0) = r2
>>
>> ---
>> The full C source code, llvm-objdump, and verifier log.
>> https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
>> https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
>> https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt
>
> thanks for sharing.
> the C program looks auto-generated? Just curious what did you
> use to do it?

Yes, this is auto-generated. We want to use P4 2016 as front end to
generate ebpf for XDP.

>
> The line 272 is r4 += r2
> where R4=imm4 and R2=pkt_end

R2 is no longer pkt_end, it's R2 == R0 == 0
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2

So at line 272, it's pkt_ptr = pkt_ptr + 0
thus the following fix works for us.
-   if (imm <= 0) {
+   if (imm < 0) {

> Right now verifier doesn't accept any arithmetic with pkt_end,
> since it expects the programs to have cannonical form of
> if (ptr > pkt_end)
>   goto fail;
>
> Even if we add it, I'm not sure what 'pkt_end + 4' suppose to do.
> It's a pointer after the valid packet range.
>
> I'm the most puzzled with the diff:
> -   if (imm <= 0) {
> +   if (imm < 0) {
> how is it making the program to pass verifier?
>
> PS
> gentle reminder to avoid top posting.
thanks for letting me know we should avoid top posting.

--William

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread Alexei Starovoitov 
On Thu, Feb 02, 2017 at 07:26:44PM -0800, William Tu wrote:
> Thanks. below is my program. The verifier fails at line 272, when
> writing to ICMP header.
> -
> ; ebpf_packetEnd = ((void*)(long)skb->data_end);
>  206:   r2 = *(u32 *)(r6 + 4)
> ; ebpf_packetStart = ((void*)(long)skb->data);
>  207:   r1 = *(u32 *)(r6 + 0)
> ...
> r10 is "struct hd" at local stack
> r1 is skb->data
> ...
> ; if (hd.icmp.ebpf_valid) {
>  261:   r4 = *(u64 *)(r10 - 40)
>  262:   if r4 == 0 goto 29
> ; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 
> 32)) {
>  263:   r4 = r0
>  264:   r4 += 32
>  265:   r4 >>= 3
>  266:   r5 = r1
>  267:   r5 += r4
>  268:   if r5 > r2 goto 23
> ; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
> (ebpf_byte) << 0);
>  269:   r2 = r0
>  270:   r2 >>= 3
>  271:   r4 = r1
>  272:   r4 += r2
>  273:   r2 = *(u64 *)(r10 - 80)
>  274:   *(u8 *)(r4 + 0) = r2
> 
> verifier log
> 
> from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
> R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
> 260: (bf) r0 = r7
> 261: (79) r4 = *(u64 *)(r10 -40)
> 262: (15) if r4 == 0x0 goto pc+29
>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
> R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
> 263: (bf) r4 = r0
> 264: (07) r4 += 32
> 265: (77) r4 >>= 3
> 266: (bf) r5 = r1
> 267: (0f) r5 += r4
> 268: (2d) if r5 > r2 goto pc+23
>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
> R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
> R10=fp
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
> 273: (79) r2 = *(u64 *)(r10 -80)
> 274: (73) *(u8 *)(r4 +0) = r2
> 
> ---
> The full C source code, llvm-objdump, and verifier log.
> https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
> https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
> https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt

thanks for sharing.
the C program looks auto-generated? Just curious what did you
use to do it?

The line 272 is r4 += r2
where R4=imm4 and R2=pkt_end
Right now verifier doesn't accept any arithmetic with pkt_end,
since it expects the programs to have cannonical form of
if (ptr > pkt_end)
  goto fail;

Even if we add it, I'm not sure what 'pkt_end + 4' suppose to do.
It's a pointer after the valid packet range.

I'm the most puzzled with the diff:
-   if (imm <= 0) {
+   if (imm < 0) {
how is it making the program to pass verifier?

PS
gentle reminder to avoid top posting.

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread William Tu 
Thanks. below is my program. The verifier fails at line 272, when
writing to ICMP header.
-
; ebpf_packetEnd = ((void*)(long)skb->data_end);
 206:   r2 = *(u32 *)(r6 + 4)
; ebpf_packetStart = ((void*)(long)skb->data);
 207:   r1 = *(u32 *)(r6 + 0)
...
r10 is "struct hd" at local stack
r1 is skb->data
...
; if (hd.icmp.ebpf_valid) {
 261:   r4 = *(u64 *)(r10 - 40)
 262:   if r4 == 0 goto 29
; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 32)) {
 263:   r4 = r0
 264:   r4 += 32
 265:   r4 >>= 3
 266:   r5 = r1
 267:   r5 += r4
 268:   if r5 > r2 goto 23
; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
(ebpf_byte) << 0);
 269:   r2 = r0
 270:   r2 >>= 3
 271:   r4 = r1
 272:   r4 += r2
 273:   r2 = *(u64 *)(r10 - 80)
 274:   *(u8 *)(r4 + 0) = r2

verifier log

from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
R8=inv,min_value=0,max_value=0 R9=inv R10=fp
260: (bf) r0 = r7
261: (79) r4 = *(u64 *)(r10 -40)
262: (15) if r4 == 0x0 goto pc+29
 R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
R8=inv,min_value=0,max_value=0 R9=inv R10=fp
263: (bf) r4 = r0
264: (07) r4 += 32
265: (77) r4 >>= 3
266: (bf) r5 = r1
267: (0f) r5 += r4
268: (2d) if r5 > r2 goto pc+23
 R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
R10=fp
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2
273: (79) r2 = *(u64 *)(r10 -80)
274: (73) *(u8 *)(r4 +0) = r2

---
The full C source code, llvm-objdump, and verifier log.
https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt

On Thu, Feb 2, 2017 at 3:46 PM, Daniel Borkmann  wrote:
> On 02/02/2017 08:59 PM, William Tu wrote:
>>
>> When adding a zero value to the packet pointer, the verifer
>> reports the following error:
>>
>> R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12
>> R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
>> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 269: (bf) r2 = r0
>> 270: (77) r2 >>= 3
>> 271: (bf) r4 = r1
>> 272: (0f) r4 += r2
>> addition of negative constant to packet pointer is not allowed
>
>
> How do we get here? I mean compiler is not optimizing this away
> as the reg is populated differently from various branches? Could
> you elaborate more on that resp. how we end up with this? Thanks!
>
>
>> Signed-off-by: William Tu 
>> Cc: Daniel Borkmann 
>> ---
>>   kernel/bpf/verifier.c | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index fb3513b..1a754e5 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct
>> bpf_verifier_env *env,
>> imm = insn->imm;
>>
>>   add_imm:
>> -   if (imm <= 0) {
>> +   if (imm < 0) {
>> verbose("addition of negative constant to packet
>> pointer is not allowed\n");
>> return -EACCES;
>> }
>>
>

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread Daniel Borkmann 

On 02/02/2017 08:59 PM, William Tu wrote:

When adding a zero value to the packet pointer, the verifer
reports the following error:

R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12 
R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx 
R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2
addition of negative constant to packet pointer is not allowed


How do we get here? I mean compiler is not optimizing this away
as the reg is populated differently from various branches? Could
you elaborate more on that resp. how we end up with this? Thanks!


Signed-off-by: William Tu 
Cc: Daniel Borkmann 
---
  kernel/bpf/verifier.c | 2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fb3513b..1a754e5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct bpf_verifier_env 
*env,
imm = insn->imm;

  add_imm:
-   if (imm <= 0) {
+   if (imm < 0) {
verbose("addition of negative constant to packet pointer is 
not allowed\n");
return -EACCES;
}

[PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

2017-02-02 Thread William Tu 
When adding a zero value to the packet pointer, the verifer
reports the following error:

R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12 
R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx 
R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2
addition of negative constant to packet pointer is not allowed

Signed-off-by: William Tu 
Cc: Daniel Borkmann 
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fb3513b..1a754e5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct bpf_verifier_env 
*env,
imm = insn->imm;
 
 add_imm:
-   if (imm <= 0) {
+   if (imm < 0) {
verbose("addition of negative constant to packet 
pointer is not allowed\n");
return -EACCES;
}
-- 
2.7.4