Parsing TCP Header Options In XDP/BPF

Parsing TCP Header Options In XDP/BPF

[Christian Deacon]

Hi everyone,


I wasn't sure whether to submit this under XDP's mailing list or BPF's. 
However, since it's an XDP program, I figured I'd start here. The issue 
has to do with the BPF verifier, though.


I am trying to parse TCP header options within XDP/BPF. In my case, I 
want to locate the 'timestamps' option and read/write to the sender and 
receive timestamps (the option's data, which is eight bytes in total I 
believe). In order to do this, I believe you'll need a loop since the 
TCP header options are dynamic in regards to location in the 
packet/memory, etc. For more information on the TCP timestamps option 
specifically, I found below a good read for those interested.


https://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_timestamps


Everything I've tried so far and the source code is all within a GitHub 
repository I made below. I also included a full BPF fail log in the 
`logs/` directory within the repository.


https://github.com/gamemann/XDP-TCP-Header-Options


In the code, I am trying to locate the timestamp offset within the TCP 
header options. One condition in the loop is when it finds another TCP 
option other than timestamps. In this case, I am trying to increment by 
the option's length (the second field within the option) so we can move 
onto scanning the next TCP option. Whenever I attempt to do so, the BPF 
verifier states I'm trying to access outside of the packet. However, 
I've tried including many checks for this (making sure the length in 
memory is within ctx->data and ctx->data_end for example). You can find 
more information about this below.


https://github.com/gamemann/XDP-TCP-Header-Options#fails


At first, I was only checking to see if the location was outside of 
ctx->data_end, but since that wasn't working, I figured I'd try to see 
if it's within ctx->data and ctx->data_end to see if it made any 
difference (it did not).



The tests I've ran occur for multiple kernels. From 5.14 to 5.10 and 5.4 
(which is the current kernel I'm on and what I performed my documented 
tests under). This is also on an Ubuntu 20.04 VM I have at home and here 
is the output from `uname -r`.


```

root@test02:/home/cdeacon# uname -r
5.4.28-050428-generic

```


I was wondering if anybody had suggestions or could tell me what I'm 
doing wrong in the code above. I apologize if I've missed anything 
obvious as well!

Any help is highly appreciated and thank you for your time!

Re: Parsing TCP Header Options In XDP/BPF

[Rob Sherwood]

Definitely not an expert but no one has replied so I'll throw out my guess :-)

Check out https://lwn.net/Articles/794934/ for more info on 'bounded
loops', but my guess is that the verifier doesn't have enough context
to verify your loop is really bounded.

One trick might be to convert your while loop to a for(;;) loop, e.g.,
instead of :

https://github.com/gamemann/XDP-TCP-Header-Options/blob/master/src/xdp_prog.c#L81
while ( optdata < 40) {... }

you could try:

for (optdata = 0; optdata < 40; optdata ++) { ... }

I know from past attempts that just because it's obvious to humans
that there's not an infinite loop, it's not always obvious to the
verifier.

Hope that helps (and is correct!),

- Rob
.


On Wed, Sep 15, 2021 at 10:36 AM Christian Deacon <gamemann@gflclan.com> wrote:
>
> Hi everyone,
>
>
> I wasn't sure whether to submit this under XDP's mailing list or BPF's.
> However, since it's an XDP program, I figured I'd start here. The issue
> has to do with the BPF verifier, though.
>
>
> I am trying to parse TCP header options within XDP/BPF. In my case, I
> want to locate the 'timestamps' option and read/write to the sender and
> receive timestamps (the option's data, which is eight bytes in total I
> believe). In order to do this, I believe you'll need a loop since the
> TCP header options are dynamic in regards to location in the
> packet/memory, etc. For more information on the TCP timestamps option
> specifically, I found below a good read for those interested.
>
>
> https://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_timestamps
>
>
> Everything I've tried so far and the source code is all within a GitHub
> repository I made below. I also included a full BPF fail log in the
> `logs/` directory within the repository.
>
>
> https://github.com/gamemann/XDP-TCP-Header-Options
>
>
> In the code, I am trying to locate the timestamp offset within the TCP
> header options. One condition in the loop is when it finds another TCP
> option other than timestamps. In this case, I am trying to increment by
> the option's length (the second field within the option) so we can move
> onto scanning the next TCP option. Whenever I attempt to do so, the BPF
> verifier states I'm trying to access outside of the packet. However,
> I've tried including many checks for this (making sure the length in
> memory is within ctx->data and ctx->data_end for example). You can find
> more information about this below.
>
>
> https://github.com/gamemann/XDP-TCP-Header-Options#fails
>
>
> At first, I was only checking to see if the location was outside of
> ctx->data_end, but since that wasn't working, I figured I'd try to see
> if it's within ctx->data and ctx->data_end to see if it made any
> difference (it did not).
>
>
>
> The tests I've ran occur for multiple kernels. From 5.14 to 5.10 and 5.4
> (which is the current kernel I'm on and what I performed my documented
> tests under). This is also on an Ubuntu 20.04 VM I have at home and here
> is the output from `uname -r`.
>
>
> ```
>
> root@test02:/home/cdeacon# uname -r
> 5.4.28-050428-generic
>
> ```
>
>
> I was wondering if anybody had suggestions or could tell me what I'm
> doing wrong in the code above. I apologize if I've missed anything
> obvious as well!
>
> Any help is highly appreciated and thank you for your time!
>

Re: Parsing TCP Header Options In XDP/BPF

[Martin KaFai Lau]

On Wed, Sep 15, 2021 at 09:21:50PM -0700, Rob Sherwood wrote:
> Definitely not an expert but no one has replied so I'll throw out my guess :-)
> 
> Check out https://lwn.net/Articles/794934/  for more info on 'bounded
> loops', but my guess is that the verifier doesn't have enough context
> to verify your loop is really bounded.
> 
> One trick might be to convert your while loop to a for(;;) loop, e.g.,
> instead of :
> 
> https://github.com/gamemann/XDP-TCP-Header-Options/blob/master/src/xdp_prog.c#L81
> while ( optdata < 40) {... }
> 
> you could try:
> 
> for (optdata = 0; optdata < 40; optdata ++) { ... }
Right, bounded loop is one option to try.

There is a bpf_load_hdr_opt() helper which currently is available to
BPF_PROG_TYPE_SOCK_OPS to parse tcp option.  Joanne (cc) is working on
extending it to support BPF_PROG_TYPE_XDP also.

> 
> I know from past attempts that just because it's obvious to humans
> that there's not an infinite loop, it's not always obvious to the
> verifier.
> 
> Hope that helps (and is correct!),
> 
> - Rob
> .
> 
> 
> On Wed, Sep 15, 2021 at 10:36 AM Christian Deacon <gamemann@gflclan.com> wrote:
> >
> > Hi everyone,
> >
> >
> > I wasn't sure whether to submit this under XDP's mailing list or BPF's.
> > However, since it's an XDP program, I figured I'd start here. The issue
> > has to do with the BPF verifier, though.
> >
> >
> > I am trying to parse TCP header options within XDP/BPF. In my case, I
> > want to locate the 'timestamps' option and read/write to the sender and
> > receive timestamps (the option's data, which is eight bytes in total I
> > believe). In order to do this, I believe you'll need a loop since the
> > TCP header options are dynamic in regards to location in the
> > packet/memory, etc. For more information on the TCP timestamps option
> > specifically, I found below a good read for those interested.
> >
> >
> > https://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_timestamps 
> >
> >
> > Everything I've tried so far and the source code is all within a GitHub
> > repository I made below. I also included a full BPF fail log in the
> > `logs/` directory within the repository.
> >
> >
> > https://github.com/gamemann/XDP-TCP-Header-Options
> >
> >
> > In the code, I am trying to locate the timestamp offset within the TCP
> > header options. One condition in the loop is when it finds another TCP
> > option other than timestamps. In this case, I am trying to increment by
> > the option's length (the second field within the option) so we can move
> > onto scanning the next TCP option. Whenever I attempt to do so, the BPF
> > verifier states I'm trying to access outside of the packet. However,
> > I've tried including many checks for this (making sure the length in
> > memory is within ctx->data and ctx->data_end for example). You can find
> > more information about this below.
> >
> >
> > https://github.com/gamemann/XDP-TCP-Header-Options#fails
> >
> >
> > At first, I was only checking to see if the location was outside of
> > ctx->data_end, but since that wasn't working, I figured I'd try to see
> > if it's within ctx->data and ctx->data_end to see if it made any
> > difference (it did not).
> >
> >
> >
> > The tests I've ran occur for multiple kernels. From 5.14 to 5.10 and 5.4
> > (which is the current kernel I'm on and what I performed my documented
> > tests under). This is also on an Ubuntu 20.04 VM I have at home and here
> > is the output from `uname -r`.
> >
> >
> > ```
> >
> > root@test02:/home/cdeacon# uname -r
> > 5.4.28-050428-generic
> >
> > ```
> >
> >
> > I was wondering if anybody had suggestions or could tell me what I'm
> > doing wrong in the code above. I apologize if I've missed anything
> > obvious as well!
> >
> > Any help is highly appreciated and thank you for your time!
> >

Re: Parsing TCP Header Options In XDP/BPF

[Toke Høiland-Jørgensen]

Christian Deacon <gamemann@gflclan.com> writes:

> Hi everyone,
>
>
> I wasn't sure whether to submit this under XDP's mailing list or BPF's. 
> However, since it's an XDP program, I figured I'd start here. The issue 
> has to do with the BPF verifier, though.
>
>
> I am trying to parse TCP header options within XDP/BPF. In my case, I 
> want to locate the 'timestamps' option and read/write to the sender and 
> receive timestamps (the option's data, which is eight bytes in total I 
> believe).

We're doing just this in the 'pping' utility, see code here:
https://github.com/xdp-project/bpf-examples/blob/master/pping/pping_kern.c#L83

-Toke

Re: Parsing TCP Header Options In XDP/BPF

[Christian Deacon]

Hey and I apologize for the late reply!


On 9/15/2021 11:19 PM, Rob Sherwood wrote:
 > Definitely not an expert but no one has replied so I'll throw out my 
guess :-)
 >
 > Check out https://lwn.net/Articles/794934/ for more info on 'bounded 
loops', but my guess is that the verifier doesn't have enough context to 
verify your loop is really bounded.
 >
 > One trick might be to convert your while loop to a for(;;) loop, 
e.g., instead of :
 >
 > 
https://github.com/gamemann/XDP-TCP-Header-Options/blob/master/src/xdp_prog.c#L81
 > while ( optdata < 40) {... }
 >
 > you could try:
 >
 > for (optdata = 0; optdata < 40; optdata ++) { ... }
 >
 > I know from past attempts that just because it's obvious to humans 
that there's not an infinite loop, it's not always obvious to the verifier.
 >
 > Hope that helps (and is correct!),
 >
 > - Rob
 > .

I did try a for loop before, but still ran into the same BPF verifier 
error :( I tried adding checks to prevent an infinite loop along with 
checks to make sure it doesn't go outside of ctx->data_end or below 
ctx->data, but no change. Thank you!

On 9/16/2021 5:32 AM, Toke Høiland-Jørgensen wrote:
 > Christian Deacon <gamemann@gflclan.com> writes:
 >
 >> Hi everyone,
 >>
 >>
 >> I wasn't sure whether to submit this under XDP's mailing list or BPF's.
 >> However, since it's an XDP program, I figured I'd start here. The issue
 >> has to do with the BPF verifier, though.
 >>
 >>
 >> I am trying to parse TCP header options within XDP/BPF. In my case, I
 >> want to locate the 'timestamps' option and read/write to the sender and
 >> receive timestamps (the option's data, which is eight bytes in total I
 >> believe).
 >
 > We're doing just this in the 'pping' utility, see code here:
 > 
https://github.com/xdp-project/bpf-examples/blob/master/pping/pping_kern.c#L83
 >
 > -Toke

This code works great for me so far! Thank you!

Re: Parsing TCP Header Options In XDP/BPF

[Toke Høiland-Jørgensen]

Christian Deacon <gamemann@gflclan.com> writes:

> Hey and I apologize for the late reply!
>
>
> On 9/15/2021 11:19 PM, Rob Sherwood wrote:
>  > Definitely not an expert but no one has replied so I'll throw out my 
> guess :-)
>  >
>  > Check out https://lwn.net/Articles/794934/ for more info on 'bounded 
> loops', but my guess is that the verifier doesn't have enough context to 
> verify your loop is really bounded.
>  >
>  > One trick might be to convert your while loop to a for(;;) loop, 
> e.g., instead of :
>  >
>  > 
> https://github.com/gamemann/XDP-TCP-Header-Options/blob/master/src/xdp_prog.c#L81
>  > while ( optdata < 40) {... }
>  >
>  > you could try:
>  >
>  > for (optdata = 0; optdata < 40; optdata ++) { ... }
>  >
>  > I know from past attempts that just because it's obvious to humans 
> that there's not an infinite loop, it's not always obvious to the verifier.
>  >
>  > Hope that helps (and is correct!),
>  >
>  > - Rob
>  > .
>
> I did try a for loop before, but still ran into the same BPF verifier 
> error :( I tried adding checks to prevent an infinite loop along with 
> checks to make sure it doesn't go outside of ctx->data_end or below 
> ctx->data, but no change. Thank you!
>
> On 9/16/2021 5:32 AM, Toke Høiland-Jørgensen wrote:
>  > Christian Deacon <gamemann@gflclan.com> writes:
>  >
>  >> Hi everyone,
>  >>
>  >>
>  >> I wasn't sure whether to submit this under XDP's mailing list or BPF's.
>  >> However, since it's an XDP program, I figured I'd start here. The issue
>  >> has to do with the BPF verifier, though.
>  >>
>  >>
>  >> I am trying to parse TCP header options within XDP/BPF. In my case, I
>  >> want to locate the 'timestamps' option and read/write to the sender and
>  >> receive timestamps (the option's data, which is eight bytes in total I
>  >> believe).
>  >
>  > We're doing just this in the 'pping' utility, see code here:
>  > 
> https://github.com/xdp-project/bpf-examples/blob/master/pping/pping_kern.c#L83
>  >
>  > -Toke
>
> This code works great for me so far! Thank you!

Awesome! You're welcome :)

-Toke