Please join us tomorrow for our bi-weekly call. As usual, this meeting is
open to everybody and completely optional.
You might be interested to join if:
You want to know what is going on in BPF land
You are doing something interesting yourself with BPF and would like to share
You want to know what the heck BPF is

=== IO Visor Dev/TSC Meeting ===

Every 2 weeks on Wednesday, from Wednesday, January 25, 2017, to no end date
11:00 am | Pacific Daylight Time (San Francisco, GMT-07:00) | 30 min

https://bluejeans.com/568677804/

https://www.timeanddate.com/worldclock/meetingdetails.html?year=2019&month=4&day=17&hour=18&min=0&sec=0&p1=900

On Thu, Apr 11, 2019 at 8:37 AM Simon <contact@...> wrote:

I finally discover that checksum can be calculated via incremental update. (see RFC 1624)

Using it, I didn't have to deal with dynamic sized payload and so no more issue with the verifier.

Glad you find a solution!

So I go back to use bcc :)

Again, Thx a lot Yonghong for your time !

Please don't forget to keep me in touch about that even if I'm not impacted anymore, I'm curious to know how you move forward on this !

Sure.

(By the way did you get the point about the error just above, is the verifier able to understand this kind of dynamic check ?)

Verifier understands some dynamic check if these dynamic check is
resolved to be constant vs. variable or constant vs. constant compares
during path sensitive verification.

I finally discover that checksum can be calculated via incremental update. (see RFC 1624)

Using it, I didn't have to deal with dynamic sized payload and so no more issue with the verifier.

So I go back to use bcc :)

Again, Thx a lot Yonghong for your time !

Please don't forget to keep me in touch about that even if I'm not impacted anymore, I'm curious to know how you move forward on this !

(By the way did you get the point about the error just above, is the verifier able to understand this kind of dynamic check ?)

Great, will have a look, thanks!

Regards,
Jiong

Hi, Jiong,

To follow up the iovisor meeting discussion, the below is my prototype
for an end_loop
instruction in llvm:
https://github.com/yonghong-song/llvm/commit/b83226772100317092cae6478229ed6ca3b9903c
The goal is to help verifier to just focus on these marked cases,
rejecting any other backedges.

Please let me and John know if you get some better idea for bounded
loop support in llvm/verifier.

Thanks,

Yonghong

On Wed, Apr 3, 2019 at 11:49 AM Brenden Blanco <bblanco@...> wrote:

Hi All,

Thanks for the good discussion today! Below are my notes.

Thanks,
Brenden

=== Discussion ===

[...]

Yonghong:
* Compile once run anywhere work continues
* bitfield handling bugs in IR/debuginfo

Daniel:
* Global support work continues
* BTF side patches submitted to bpf mailing list
* tests included

Jiong:
* 32 bit patch set
* test methodology improvements
* updated patches later in the week
* some concerns around shifts, to be addressed in later improvements

Andrii:
* BTF and compile-once work integration
to share prototype tool with Saeed

Brendan:
* Is there a tool to measure queue latency in qdisc->netdev layer?
* debian/ubuntu are packaging bpftrace
* except libbcc renamed to libbpf_cc
* some issues with mixing iovisor's libbcc and debian's

Jesper:
* Fedora adding packaging support for libbpf

Alexei:
* systemd also adding support for libbpf - link to be provided?

=== Attendees ===
Brenden Blanco
Andril Nakryiko
Daniel Borkmann
Jesper Brouer
Jiong Wang
Marco Leogrande
Michael Savisko
Paul Chaignon
Quentin Monnet
Alexei Starovoitov
Saeed
Flavio
Rony
Jonathan Lemon
Brendan Gregg
Dan Siemon
Joe Stringer
John

I have a need to have a bpftrace script #include headers from a project
directory. In cc, this is like adding -I<path>. Am I blind from reading manuals
or is there a clever way to pass that info down through bpftrace into bpf or
is this a new RFE?
-- richard

Hi All,

Thanks for the good discussion today! Below are my notes.

Thanks,
Brenden

=== Discussion ===

Michael:
* https://github.com/savisko/katran/tree/xdp_off
* Mellanox presentation on XDP + Katran
* offload tc XDP programs to hardware nic
* Example application: Katran from Facebook
* Control is implemented as a C++ library (example is open source)
* Katran DP already implemented in XDP
* Parsing + extract flow ID
* lookup key generation
* counter update
* packet modified to forward to other IP
* Accelerate marking of flows in hardware
* XDP metadata to pass mark field from hardware to xdp program
* struct xdp_md_mark {
__u32 mark)
};
* if (mark_ptr + 1 <= data)
markID = mark_ptr->mark;
* per-CPU XDP map to convert mark -> real flow information
mark == 0 implies new flow
* original XDP slow-path has get_packet_dst() to create LRU mapping
* modified version uses perf event output to notify acceleration helper to
install flow mark in hardware
* perf results:
100 flows: 40+% performance improvements
10k flows: 0-50% performance improvements depending on #rx queues used
Software: 25Mpps
Hardware: 37-39Mpps
* considering changing implementation to mark real server instead of flow
id, to reduce number of entries kept in L1 cache

Yonghong:
* Compile once run anywhere work continues
* bitfield handling bugs in IR/debuginfo

Daniel:
* Global support work continues
* BTF side patches submitted to bpf mailing list
* tests included

Jiong:
* 32 bit patch set
* test methodology improvements
* updated patches later in the week
* some concerns around shifts, to be addressed in later improvements

Andrii:
* BTF and compile-once work integration
to share prototype tool with Saeed

Brendan:
* Is there a tool to measure queue latency in qdisc->netdev layer?
* debian/ubuntu are packaging bpftrace
* except libbcc renamed to libbpf_cc
* some issues with mixing iovisor's libbcc and debian's

Jesper:
* Fedora adding packaging support for libbpf

Alexei:
* systemd also adding support for libbpf - link to be provided?

=== Attendees ===
Brenden Blanco
Andril Nakryiko
Daniel Borkmann
Jesper Brouer
Jiong Wang
Marco Leogrande
Michael Savisko
Paul Chaignon
Quentin Monnet
Alexei Starovoitov
Saeed
Flavio
Rony
Jonathan Lemon
Brendan Gregg
Dan Siemon
Joe Stringer
John

Agenda: discussion on XDP acceleration of Katran LB

Please join us tomorrow for our bi-weekly call. As usual, this meeting is
open to everybody and completely optional.
You might be interested to join if:
You want to know what is going on in BPF land
You are doing something interesting yourself with BPF and would like to share
You want to know what the heck BPF is

=== IO Visor Dev/TSC Meeting ===

Every 2 weeks on Wednesday, from Wednesday, January 25, 2017, to no end date
11:00 am | Pacific Daylight Time (San Francisco, GMT-07:00) | 30 min

https://bluejeans.com/568677804/

https://www.timeanddate.com/worldclock/meetingdetails.html?year=2019&month=4&day=3&hour=18&min=0&sec=0&p1=900

On Tue, Apr 2, 2019 at 10:48 AM Saeed Mahameed
<saeedm@...> wrote:

Hi Brenden,

I am sending this on behalf of Michael Savisko, he is having some
difficulties sending emails to the iovisor list.

Sending to the iovisor-dev mailer is gated by a signup requirement, in
order to reduce spam. The signup process should be pretty painless, I
believe it just requires going through an email validation step:
https://lists.iovisor.org/g/iovisor-dev/join

Michael is working on real world use cases for XDP acceleration.
He would like to present and discuss his work and analysis on
accelerating Katran load balancer [1] via meta data offloads.
He will need 10 minutes and will share some slides, i hope we can push
this to tomorrow's meeting agenda.

Sounds good!

Katran modified code is on Github:
https://github.com/savisko/katran/tree/xdp_off

[1] https://code.fb.com/open-source/open-sourcing-katran-a-scalable-network-load-balancer/
Thanks,
Saeed.

On Wed, Mar 20, 2019 at 3:32 PM Brenden Blanco <bblanco@...> wrote:

Hi all,

Thanks for joining the discussion today. Here are the notes; however, this was
a longer discussion and I'm sure I missed some things.

Cheers,
Brenden

=== Discussion ===

Yonghong:
* Some internal BTF work
* Compiler support for static variables
* Some compile-once-run-everywhere work
* Looking for help with issues regarding libbpf packaging/dependencies
* Issue to continue offline, not concluded on the call
* Issue related to function->function call in bcc and compiler optimizations
* Jiong offers to debug the codegen using 32 bit mode

Saeed:
* XDP driver statistics standardization
* All drivers run same entry point for xdp progs
* Why not account stats here?
* Even though xdp program can implement its own statistics
* Many drivers are already paying stats accounting cost
* Just remove unused stats from driver?
* Stats may be used in debugging, but FB for instance is guarding with
static key, wouldn't want extra stats on by default
* Allocating resources for tx queue/redirect?
* Is there a better way to allocate resources when it isn't known that a
program will need queues
* One approach is to attach dummy bpf program
* Resource allocation point when configuring devmap?
* Seems like a clean enough solution, doesn't solve all cases but moves the
ball forward
* BTF metadata structure registration
* Should be queryable from userspace, don't yet have an API for that
* Netlink vs syscall?
* No silver bullet for all use cases
* Hesitation for creating a new object to describe existing objects (bpf
progs, maps)
* BTF is metadata conceptually different from maps, progs
* ethtool? unlikely due to lack of code ownership
* For buffers, something like devlink is more appropriate
* For BTF, bpf() syscall works
* BTF for statistics description (ethtool replacement?)

Daniel:
* verification of static data is working, patches coming soon

=== Attendees ===
Brenden Blanco
Michael Savisko
Alexei Starovoitov
Daniel Borkmann
Jakub Kicinski
Neerav Parikh
Paul Chaignon
Saeed
Marco Leogrande
Jiong Wang
Andrii Nakryiko
Yonghong Song
William Tu
Joe Stringer
John
Maciej Fijalkowski
Martin Lau
Mauricio Vasquez
Piotr Raczynski
Quillian Rutherford

Hi Brenden,

I am sending this on behalf of Michael Savisko, he is having some
difficulties sending emails to the iovisor list.

Michael is working on real world use cases for XDP acceleration.
He would like to present and discuss his work and analysis on
accelerating Katran load balancer [1] via meta data offloads.
He will need 10 minutes and will share some slides, i hope we can push
this to tomorrow's meeting agenda.

Katran modified code is on Github:
https://github.com/savisko/katran/tree/xdp_off

[1] https://code.fb.com/open-source/open-sourcing-katran-a-scalable-network-load-balancer/
Thanks,
Saeed.

On Wed, Mar 27, 2019 at 1:48 PM Pablo Alvarez via Lists.Iovisor.Org
<palvarez=akamai.com@...> wrote:

Why is it required that llvm compile the BPF code with -O2? That seems
to be part of what is causing these verifier problems...

-O0 won't work as helper call will become an indirect call
static void *(*bpf_map_lookup_elem)(void *map, void *key) =
(void *) BPF_FUNC_map_lookup_elem;
Another reason is below value tracking in verifier.

The verifier does not handle value spill well. It kept track of map
pointers, packet pointers, etc.
But if a particular value is spilled, later on, when reload from
stack, it will become unknown.
For example,
r1 = 10; /* verifier state: r1 = 10 */
*(r10 - 40) = r1;
r2 = *(r10 - 40); /* verifier state: r2, unknown */

The reason is that keep tracking of values could increase verification
time quite a bit.
This is measured sometime back, but it may warrant to do some measurement again
at this moment to see whether can relax this restriction.

So practically -O0 won't work. -O1 may or may not work and most people
do not use it.
-O2 is preferred. Also for performance reasons, we want to make -O2
work as BPF JIT
inside the kernel does not do any optimization, it is simple one insn
each time translation.

On 3/27/19 4:23 PM, Yonghong Song wrote:

On Wed, Mar 27, 2019 at 10:17 AM Jiong Wang <jiong.wang@...> wrote:

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

If you use BPF constructor debug=16 flag, it will print out the
register state for every insn if you are even more curious.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

To resolve this issue, llvm may need to do more:
- prevent/undo optimization which may cause ultimate verifier rejections.
- provide hints (e.g., through BTF) to verifier so verifier may
selectively do some analysis
or enable some tracking for the cases where BTF instructed to
handle. For example,
BTF may tell verifier two register have the same state at a
particular point and verifier
only needs to check these two registers with limited range and no
others, etc.

Regards,
Jiong

Why is it required that llvm compile the BPF code with -O2? That seems to be part of what is causing these verifier problems...

On Wed, Mar 27, 2019 at 10:17 AM Jiong Wang <jiong.wang@...> wrote:

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

If you use BPF constructor debug=16 flag, it will print out the
register state for every insn if you are even more curious.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

To resolve this issue, llvm may need to do more:
- prevent/undo optimization which may cause ultimate verifier rejections.
- provide hints (e.g., through BTF) to verifier so verifier may
selectively do some analysis
or enable some tracking for the cases where BTF instructed to
handle. For example,
BTF may tell verifier two register have the same state at a
particular point and verifier
only needs to check these two registers with limited range and no
others, etc.

Regards,
Jiong

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

Regards,
Jiong

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

On 27 Mar 2019, at 16:11, Jiong Wang via Lists.Iovisor.Org <jiong.wang=netronome.com@...> wrote:

On 27 Mar 2019, at 14:53, Simon <contact@...> wrote:

Hi Jiong,
I didn't succeed to generate .i file using bcc, but since severals days I try to rewrite my code without bcc. (directly with bpf C api / clang / iproute2)

I didn't finished yet, but I have a reduced version compared to the one I written for bcc and I face the same issue, so this time I can get .i file easily.

So the .i file is as attachment.
The corresponding code is available here : https://github.com/sbernard31/udploadbalancer/blob/44fe1ea549a55ab23c7d1b70e9651df6f61fb865/ulb.c

Hi Simon,

Thanks for the .i, I prototyped some byteswap code-gen change, but
seems doesn’t help your issue which could narrow down to the following
general code pattern:

unsigned char cal(unsigned int a, unsigned char *b)
{
if (a < 8 || a > 512)
return 0;

return b[a];
}

LLVM is doing some optimisation, instead of generating two separate comparison,
a < 8 and a > 512, it is combining them because a negative value when casted
into unsigned must be bigger than 504, so above code turned into

unsigned char cal(unsigned int a, unsigned char *b)
{
unsigned tmp = a - 8;
if (tmp > 504)
return 0;

return b[a];
}

The consequence of such optimisation is new variable “tmp” is used for comparison
And verifier now know “tmp”'s value range instead of the original “a” which is used
later adding to a packet pointer. A unknown value range of “a” then caused the
verifier rejection.

So, I suspect any code using above c code pattern will likely be rejected.

1. combinable comparisons
2. the variable involved in the comparison used later in places requiring value range

And in your code, after you insert those printk, they made the following
two comparisons non-combinable any more, so udp_len is used for the
comparison and got correct value range to pass the later pkt pointer
addition check.


if (udp_len < 8) {
return XDP_DROP;
}
if (udp_len > 512) {
return XDP_DROP;
}

Regards,
Jiong

The error is still math between pkt pointer and register with unbounded min value is not allowed

The verifier output is pretty much the same :

27: (71) r4 = *(u8 *)(r1 +23)
28: (b7) r0 = 2
29: (55) if r4 != 0x11 goto pc+15
R0=inv2 R1=pkt(id=0,off=0,r=34,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=34,r=34,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
30: (07) r3 += 8
31: (b7) r0 = 1
32: (2d) if r3 > r2 goto pc+12
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=42,r=42,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
33: (69) r3 = *(u16 *)(r1 +38)
34: (dc) r3 = be16 r3
35: (bf) r4 = r3
36: (07) r4 += -8
37: (57) r4 &= 65535
38: (b7) r0 = 1
39: (25) if r4 > 0x1f8 goto pc+5
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

I'm pretty sure the bcc version I used before linked statically clang/llvm v7.0.
Here I use a v6.0.

The funny part ... This modification about just adding some logs/printk makes this error disappear : https://github.com/sbernard31/udploadbalancer/commit/0145538c7b35e2a6bb92225f69a45f4bee120a6d

All of those erifier errors make me a bit crazy (╥_╥)

HTH

Simon


<ulb.i>