bpf: BPF for lightweight tunnel encapsulation

Register two new BPF prog types BPF_PROG_TYPE_LWT_IN and BPF_PROG_TYPE_LWT_OUT which are invoked if a route contains a LWT redirection of type LWTUNNEL_ENCAP_BPF.

The separate program types are required because manipulation of packet data is only allowed on the output and transmit path as the subsequent dst_input() call path assumes an IP header validated by ip_rcv(). The BPF programs will be handed an skb with the L3 header attached and may return one of the following return codes:

BPF_OK - Continue routing as per nexthop
BPF_DROP - Drop skb and return EPERM
BPF_REDIRECT - Redirect skb to device as per redirect() helper.
(Only valid on lwtunnel_xmit() hook)

The return codes are binary compatible with their TC_ACT_ relatives to ease compatibility.

A new helper bpf_skb_push() is added which allows to preprend an L2 header in front of the skb, extend the existing L3 header, or both. This allows to address a wide range of issues:
- Optimize L2 header construction when L2 information is always static to avoid ARP/NDisc lookup.
- Extend IP header to add additional IP options.
- Perform simple encapsulation where offload is of no concern. (The existing funtionality to attach a tunnel key to the skb and redirect to a tunnel net_device to allow for offload continues to work obviously).

Quoted 4 lines · Thomas Graf

- Perform simple encapsulation where offload is of no concern. (The existing funtionality to attach a tunnel key to the skb and redirect to a tunnel net_device to allow for offload continues to work obviously).

have you tested the adding of headers with large packets hitting gso and fragmentation? Wondering if mtu is used properly when headers are added and the lwt->headroom is not accounted. See 14972cbd34ff668c390cbd2e6497323484c9e812

Register two new BPF prog types BPF_PROG_TYPE_LWT_IN and BPF_PROG_TYPE_LWT_OUT which are invoked if a route contains a LWT redirection of type LWTUNNEL_ENCAP_BPF.

The separate program types are required because manipulation of packet data is only allowed on the output and transmit path as the subsequent dst_input() call path assumes an IP header validated by ip_rcv(). The BPF programs will be handed an skb with the L3 header attached and may return one of the following return codes:

BPF_OK - Continue routing as per nexthop
BPF_DROP - Drop skb and return EPERM
BPF_REDIRECT - Redirect skb to device as per redirect() helper.
(Only valid on lwtunnel_xmit() hook)

The return codes are binary compatible with their TC_ACT_ relatives to ease compatibility.

A new helper bpf_skb_push() is added which allows to preprend an L2 header in front of the skb, extend the existing L3 header, or both. This allows to address a wide range of issues:
- Optimize L2 header construction when L2 information is always static to avoid ARP/NDisc lookup.
- Extend IP header to add additional IP options.
- Perform simple encapsulation where offload is of no concern. (The existing funtionality to attach a tunnel key to the skb and redirect to a tunnel net_device to allow for offload continues to work obviously).

Signed-off-by Thomas Graf <[email protected]>

---

net/Kconfig +1 -0

index 7b6cd34..7554f12 100644
@@ -396,6 +396,7 @@ source "net/nfc/Kconfig"
 
 config LWTUNNEL
 	bool "Network light weight tunnels"
+	depends on IPV6 || IPV6=n
 	---help---
 	  This feature provides an infrastructure to support light weight
 	  tunnels like mpls. There is no netdevice associated with a light

net/core/Makefile +0 -0

index d6508c2..a675fd3 100644

Quoted 6 lines

net/core/Makefile +0 -0

index d6508c2..a675fd3 100644
@@ -23,7 +23,7 @@ obj-$(CONFIG_NETWORK_PHY_TIMESTAMPING) += timestamping.o
 obj-$(CONFIG_NET_PTP_CLASSIFY) += ptp_classifier.o

net/core/Makefile obj-$(CONFIG_NETWORK_PHY_TIMESTAMPING) += timestamping.o · line 26

Quoted 4 lines

net/core/Makefile +1 -1

 obj-$(CONFIG_CGROUP_NET_PRIO) += netprio_cgroup.o
 obj-$(CONFIG_CGROUP_NET_CLASSID) += netclassid_cgroup.o
-obj-$(CONFIG_LWTUNNEL) += lwtunnel.o
+obj-$(CONFIG_LWTUNNEL) += lwtunnel.o lwt_bpf.o

Any reason you want to keep lwt bpf under the main CONFIG_LWTUNNEL infra config ?.
since it is defined as yet another plug-gable encap function, seems like it will be better under a separate CONFIG_LWTUNNEL_BPF or CONFIG_LWT_BPF that depends on CONFIG_LWTUNNEL

Hi Thomas,

[auto build test ERROR on net-next/master]

url: https://github.com/0day-ci/linux/commits/Thomas-Graf/bpf-BPF-for-lightweight-tunnel-encapsulation/20161101-084038
config: arm64-allmodconfig (attached as .config)
compiler: aarch64-linux-gnu-gcc (Debian 6.1.1-9) 6.1.1 20160705
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=arm64

All errors (new ones prefixed by >>):

net/built-in.o: In function `bpf_output':

Quoted 1 line

Quoted 1 line

ncsi-manage.c:(.text+0x8e9f4): undefined reference to `ip6_route_output_flags'

{Open question:
Tom brought up the question on whether it is safe to modify the packet in artbirary ways before dst_output(). This is the equivalent to a raw socket injecting illegal headers. This v2 currently assumes that dst_output() is ready to accept invalid header values. This needs to be verified and if not the case, then raw sockets or dst_output() handlers must be fixed as well. Another option is to mark lwtunnel_output() as read-only for now.}

This series implements BPF program invocation from dst entries via the lightweight tunnels infrastructure. The BPF program can be attached to lwtunnel_input(), lwtunnel_output() or lwtunnel_xmit() and sees an L3 skb as context. input is read-only, output can write, xmit can write, push headers, and redirect.

Motiviation for this work:
- Restricting outgoing routes beyond what the route tuple supports
- Per route accounting byond realms
- Fast attachment of L2 headers where header does not require resolving L2 addresses
- ILA like uses cases where L3 addresses are resolved and then routed in an async manner
- Fast encapsulation + redirect. For now limited to use cases where not setting inner and outer offset/protocol is OK.

A couple of samples on how to use it can be found in patch 04.

I do fear the complexity and debugability introduced by this patch set quite a bit.

I wonder if architecturally it would be more feasible to add a generic (bfp-)hook into into dst_output(_sk) and allow arbitrary metadata to be added into the dsts.

BPF could then be able to access parts of the metadata in the attached metadata dst entries and performing the matching this way?

The reason why I would prefer an approach like this: irregardless of the routing lookup we would process the skb with bpf or not. This gives a single point to debug, where instead in your approach we first must figure out the corresponding bpf program and then check for it specifically.

Quoted 2 lines · Hannes Frederic Sowa

I do fear the complexity and debugability introduced by this patch set quite a bit.

What is the complexity concern? This is pretty straight forward. I agree on debugability. This is being worked on separately as Alexei mentioned, to address this for all BPF integrations.

Quoted 6 lines

I wonder if architecturally it would be more feasible to add a generic (bfp-)hook into into dst_output(_sk) and allow arbitrary metadata to be added into the dsts.

BPF could then be able to access parts of the metadata in the attached metadata dst entries and performing the matching this way?

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

Quoted 4 lines

The reason why I would prefer an approach like this: irregardless of the routing lookup we would process the skb with bpf or not. This gives a single point to debug, where instead in your approach we first must figure out the corresponding bpf program and then check for it specifically.

Not sure I see what kind of advantage this actually provides. You can dump the routes and see which programs get invoked and which section.

If it's based on metadata then you need to know the program logic and associate it with the metadata in the dst. It actually doesn't get much easier than to debug one of the samples, they are completely static once compiled and it's very simple to verify if they do what they are supposed to do.

If you like the single program approach, feel free to load the same program for every dst. Perfectly acceptable but I don't see why we should force everybody to use that model.

Quoted 7 lines · Thomas Graf

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

I thought more of hooks in the actual output/input functions specific to the protocol type (unfortunately again) protected by jump labels? Those hook get part of the dst_entry mapped so they can act on them.

Another idea would be to put the eBPF hooks into the fib rules infrastructure. But I fear this wouldn't get you the hooks you were looking for? There they would only end up in the runtime path if actually activated.

Dumping and verifying which routes get used might actually already be quite complex on its own. Thus my fear.

Quoted 5 lines

If it's based on metadata then you need to know the program logic and associate it with the metadata in the dst. It actually doesn't get much easier than to debug one of the samples, they are completely static once compiled and it's very simple to verify if they do what they are supposed to do.

At the same time you can have lots of those programs and you e.g. would also need to verify if they are acting on the same data structures or have the identical code.

It all reminds me a bit on grepping in source code which makes heavy use of function pointers with very generic and short names.

Quoted 3 lines

If you like the single program approach, feel free to load the same program for every dst. Perfectly acceptable but I don't see why we should force everybody to use that model.

I am concerned having 100ths of BPF programs, all specialized on a particular route, to debug. Looking at one code file and its associated tables seems still easier to me.

E.g. imaging we have input routes and output routes with different BPF programs. We somehow must make sure all nodes kind of behave accordingly to "sane" network semantics. If you end up with an input route doing bpf

processing and the according output node, which e.g. might be needed to reflect ICMP packets, doesn't behave accordingly you at least have two programs to debug already instead of a switch- or if-condition in one single code location. I would like to "force" this kind of symmetry to developers using eBPF, thus I thought meta-data manipulation and verification inside the kernel would be a better attack at this problem, no?

Quoted 9 lines · Hannes Frederic Sowa

Quoted 7 lines · Thomas Graf

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

Quoted 3 lines

I thought more of hooks in the actual output/input functions specific to the protocol type (unfortunately again) protected by jump labels? Those hook get part of the dst_entry mapped so they can act on them.

This has no advantage over installing a BPF program at tc egress and enabling to store/access metadata per dst. The whole point is to execute bpf for a specific route.

Quoted 4 lines

Another idea would be to put the eBPF hooks into the fib rules infrastructure. But I fear this wouldn't get you the hooks you were looking for? There they would only end up in the runtime path if actually activated.

Use of fib rules kills performance so it's not an option. I'm not even sure that would be any simpler.

Quoted 2 lines

Dumping and verifying which routes get used might actually already be quite complex on its own. Thus my fear.

We even have an API to query which route is used for a tuple. What else would you like to see?

Quoted 9 lines

Quoted 5 lines

If it's based on metadata then you need to know the program logic and associate it with the metadata in the dst. It actually doesn't get much easier than to debug one of the samples, they are completely static once compiled and it's very simple to verify if they do what they are supposed to do.

At the same time you can have lots of those programs and you e.g. would also need to verify if they are acting on the same data structures or have the identical code.

This will be addressed with signing AFAIK.

Quoted 2 lines

It all reminds me a bit on grepping in source code which makes heavy use of function pointers with very generic and short names.

Is this statement related to routing? I don't get the reference to function pointers and generic short names.

Quoted 7 lines

Quoted 3 lines

If you like the single program approach, feel free to load the same program for every dst. Perfectly acceptable but I don't see why we should force everybody to use that model.

I am concerned having 100ths of BPF programs, all specialized on a particular route, to debug. Looking at one code file and its associated tables seems still easier to me.

100 programs != 100 source files. A lot more realistic is a single or a handful of programs which get compiled for a particular route with certain pieces enabled/disabled.

Quoted 3 lines

E.g. imaging we have input routes and output routes with different BPF programs. We somehow must make sure all nodes kind of behave accordingly to "sane" network semantics. If you end up with an input route doing bpf

As soon as we have signing, you can verify your programs in testing, sign the programs and then quickly verify on all your nodes whether you are running the correct programs.

Would it help if we allow to store the original source used for bytecode generation. What would make it clear which program was used.

Quoted 7 lines

processing and the according output node, which e.g. might be needed to reflect ICMP packets, doesn't behave accordingly you at least have two programs to debug already instead of a switch- or if-condition in one single code location. I would like to "force" this kind of symmetry to developers using eBPF, thus I thought meta-data manipulation and verification inside the kernel would be a better attack at this problem, no?

Are you saying you want a single gigantic program for both input and output?

That's not possible. The BPF program has different limitations depending on where it runs. On input, any write action on the packet is not allowed, extending the header is only allowed on xmit, and so on.

I also don't see how this could possibly scale if all packets must go through a single BPF program. The overhead will be tremendous if you only want to filter a couple of prefixes.

Quoted 11 lines · Thomas Graf

Quoted 9 lines · Hannes Frederic Sowa

Quoted 7 lines · Thomas Graf

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

Quoted 7 lines

Quoted 3 lines

I thought more of hooks in the actual output/input functions specific to the protocol type (unfortunately again) protected by jump labels? Those hook get part of the dst_entry mapped so they can act on them.

This has no advantage over installing a BPF program at tc egress and enabling to store/access metadata per dst. The whole point is to execute bpf for a specific route.

The advantage I saw here was that in your proposal the tc egress path would have to be chosen by a route. Otherwise I would already have proposed it. :)

Quoted 5 lines

Quoted 4 lines

Another idea would be to put the eBPF hooks into the fib rules infrastructure. But I fear this wouldn't get you the hooks you were looking for? There they would only end up in the runtime path if actually activated.

Quoted 2 lines

Use of fib rules kills performance so it's not an option. I'm not even sure that would be any simpler.

It very much depends on the number of rules installed. If there are just several very few rules, it shouldn't hurt performance that much (but haven't verified).

Quoted 5 lines

Quoted 2 lines

Dumping and verifying which routes get used might actually already be quite complex on its own. Thus my fear.

We even have an API to query which route is used for a tuple. What else would you like to see?

I am not sure here. Some ideas I had were to allow tcpdump (pf_packet) sockets sniff at interfaces and also gather and dump the metadata to user space (this would depend on bpf programs only doing the modifications in metadata and not in the actual packet).

Or maybe just tracing support (without depending on the eBPF program developer to have added debugging in the BPF program).

Quoted 11 lines

Quoted 9 lines

Quoted 5 lines

If it's based on metadata then you need to know the program logic and associate it with the metadata in the dst. It actually doesn't get much easier than to debug one of the samples, they are completely static once compiled and it's very simple to verify if they do what they are supposed to do.

At the same time you can have lots of those programs and you e.g. would also need to verify if they are acting on the same data structures or have the identical code.

This will be addressed with signing AFAIK.

This sounds a bit unrealistic. Signing lots of small programs can be a huge burden to the entity doing the signing (if it is not on the same computer). And as far as I understood the programs should be generated dynamically?

Quoted 5 lines

Quoted 2 lines

It all reminds me a bit on grepping in source code which makes heavy use of function pointers with very generic and short names.

Is this statement related to routing? I don't get the reference to function pointers and generic short names.

No, just an anecdotal side note how I felt when I saw the patchset. ;)

Quoted 16 lines

Quoted 7 lines

Quoted 3 lines

If you like the single program approach, feel free to load the same program for every dst. Perfectly acceptable but I don't see why we should force everybody to use that model.

I am concerned having 100ths of BPF programs, all specialized on a particular route, to debug. Looking at one code file and its associated tables seems still easier to me.

100 programs != 100 source files. A lot more realistic is a single or a handful of programs which get compiled for a particular route with certain pieces enabled/disabled.

Quoted 3 lines

E.g. imaging we have input routes and output routes with different BPF programs. We somehow must make sure all nodes kind of behave accordingly to "sane" network semantics. If you end up with an input route doing bpf

Quoted 6 lines

As soon as we have signing, you can verify your programs in testing, sign the programs and then quickly verify on all your nodes whether you are running the correct programs.

Would it help if we allow to store the original source used for bytecode generation. What would make it clear which program was used.

I would also be fine with just a strong hash of the bytecode, so the program can be identified accurately. Maybe helps with deduplication later on, too. ;)

Quoted 9 lines

Quoted 7 lines

processing and the according output node, which e.g. might be needed to reflect ICMP packets, doesn't behave accordingly you at least have two programs to debug already instead of a switch- or if-condition in one single code location. I would like to "force" this kind of symmetry to developers using eBPF, thus I thought meta-data manipulation and verification inside the kernel would be a better attack at this problem, no?

Are you saying you want a single gigantic program for both input and output?

Even though I read through the patchset I am not absolutely sure which problem it really solves. Especially because lots of things can be done already at the ingress vs. egress interface (I looked at patch 4 but I am not sure how realistic they are).

Quoted 8 lines

That's not possible. The BPF program has different limitations depending on where it runs. On input, any write action on the packet is not allowed, extending the header is only allowed on xmit, and so on.

I also don't see how this could possibly scale if all packets must go through a single BPF program. The overhead will be tremendous if you only want to filter a couple of prefixes.

In case of hash table lookup it should be fast. llvm will probably also generate jump table for a few 100 ip addresses, no? Additionally the routing table lookup could be not done at all.

Thanks,
Hannes

Quoted 29 lines · Hannes Frederic Sowa

Quoted 11 lines · Thomas Graf

Quoted 9 lines · Hannes Frederic Sowa

Quoted 7 lines · Thomas Graf

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

Quoted 7 lines

Quoted 3 lines

I thought more of hooks in the actual output/input functions specific to the protocol type (unfortunately again) protected by jump labels? Those hook get part of the dst_entry mapped so they can act on them.

This has no advantage over installing a BPF program at tc egress and enabling to store/access metadata per dst. The whole point is to execute bpf for a specific route.

The advantage I saw here was that in your proposal the tc egress path would have to be chosen by a route. Otherwise I would already have proposed it. :)

Quoted 5 lines

Quoted 4 lines

Another idea would be to put the eBPF hooks into the fib rules infrastructure. But I fear this wouldn't get you the hooks you were looking for? There they would only end up in the runtime path if actually activated.

Quoted 7 lines

Quoted 2 lines

Use of fib rules kills performance so it's not an option. I'm not even sure that would be any simpler.

It very much depends on the number of rules installed. If there are just several very few rules, it shouldn't hurt performance that much (but haven't verified).

Hannes,

I can say that the primary value we get out of using ILA+LWT is that we can essentially cache a policy decision in connected sockets. That is we are able to create a host route for each destination (thousands of them) that describes how to do the translation for each one. There is no route lookup per packet, and actually no extra lookup otherwise.

The translation code doesn't do much at all, basically just copies in new destination to the packet. We need a route lookup for the rewritten destination, but that is easily cached in the LWT structure. The net result is that the transmit path for ILA is _really_ fast. I'm not sure how we can match this same performance tc egress, it seems like we would want to cache the matching rules in the socket to avoid rule lookups.

On the other hand, I'm not really sure how to implement for this level of performance this in LWT+BPF either. It seems like one way to do that would be to create a program each destination and set it each host. As you point out would create a million different programs which doesn't seem manageable. I don't think the BPF map works either since that implies we need a lookup (?). It seems like what we need is one program but allow it to be parameterized with per destination information saved in the route (LWT structure).

Hi Tom,

Quoted 38 lines · Tom Herbert

Quoted 29 lines · Hannes Frederic Sowa

Quoted 11 lines · Thomas Graf

Quoted 9 lines · Hannes Frederic Sowa

Quoted 7 lines · Thomas Graf

If I understand you correctly then a single BPF program would be loaded which then applies to all dst_output() calls? This has a huge drawback, instead of multiple small BPF programs which do exactly what is required per dst, a large BPF program is needed which matches on metadata. That's way slower and renders one of the biggest advantages of BPF invalid, the ability to generate a a small program tailored to a particular use. See Cilium.

Quoted 7 lines

Quoted 3 lines

I thought more of hooks in the actual output/input functions specific to the protocol type (unfortunately again) protected by jump labels? Those hook get part of the dst_entry mapped so they can act on them.

This has no advantage over installing a BPF program at tc egress and enabling to store/access metadata per dst. The whole point is to execute bpf for a specific route.

The advantage I saw here was that in your proposal the tc egress path would have to be chosen by a route. Otherwise I would already have proposed it. :)

Quoted 5 lines

Quoted 4 lines

Another idea would be to put the eBPF hooks into the fib rules infrastructure. But I fear this wouldn't get you the hooks you were looking for? There they would only end up in the runtime path if actually activated.

Quoted 7 lines

Quoted 2 lines

Use of fib rules kills performance so it's not an option. I'm not even sure that would be any simpler.

It very much depends on the number of rules installed. If there are just several very few rules, it shouldn't hurt performance that much (but haven't verified).

Quoted 7 lines

Hannes,

I can say that the primary value we get out of using ILA+LWT is that we can essentially cache a policy decision in connected sockets. That is we are able to create a host route for each destination (thousands of them) that describes how to do the translation for each one. There is no route lookup per packet, and actually no extra lookup otherwise.

Exactly, that is why I do like LWT and the dst_entry socket caching shows its benefits here. Also the dst_entries communicate enough vital information up the stack so that allocation of sk_buffs is done accordingly to the headers that might need to be inserted later on.

(On the other hand, the looked up BPF program can also be cached. This becomes more difficult if we can't share the socket structs between namespaces though.)

Quoted 7 lines

The translation code doesn't do much at all, basically just copies in new destination to the packet. We need a route lookup for the rewritten destination, but that is easily cached in the LWT structure. The net result is that the transmit path for ILA is _really_ fast. I'm not sure how we can match this same performance tc egress, it seems like we would want to cache the matching rules in the socket to avoid rule lookups.

In case of namespaces, do you allocate the host routes in the parent or child (net-)namespaces? Or don't we talk about namespaces right now at all?

Why do we want to do the packet manipulation in tc egress and not using LWT + interfaces? The dst_entries should be able to express all possible allocation strategies etc. so that we don't need to shift/reallocate packets around when inserting an additional header. We can't express those semantics with tc egress.

Quoted 8 lines

On the other hand, I'm not really sure how to implement for this level of performance this in LWT+BPF either. It seems like one way to do that would be to create a program each destination and set it each host. As you point out would create a million different programs which doesn't seem manageable. I don't think the BPF map works either since that implies we need a lookup (?). It seems like what we need is one program but allow it to be parameterized with per destination information saved in the route (LWT structure).

Yes, that is my proposal. Just using the dst entry as meta-data (which can actually also be an ID for the network namespace the packet is coming from).

My concern with using BPF is that the rest of the kernel doesn't really see the semantics and can't optimize or cache at specific points, because the kernel cannot introspect what the BPF program does (for metadata manipulation, one can e.g. specifiy that the program is "pure", and always provides the same output for some specified given input, thus things can be cached and memorized, but that framework seems very hard to build).

That's why I am in favor of splitting this patchset down and allow the policies that should be expressed by BPF programs being applied to the specific subsystems (I am not totally against a generic BPF hook in input or output of the protocol engines). E.g. can we deal with static rewriting of L2 addresses in the neighbor cache? We already provide a fast header cache for L2 data which might be used here?

I also fear this becomes a kernel by-pass:

It might be very hard e.g. to apply NFT/netfilter to such packets, if e.g. a redirect happens suddenly and packet flow is diverted from the one the user sees currently based on the interfaces and routing tables.

Those are just some thoughts so far, I still have to think more about this. Thanks for the discussion, it is very interesting.

Bye,
Hannes

Quoted 8 lines · Tom Herbert

On the other hand, I'm not really sure how to implement for this level of performance this in LWT+BPF either. It seems like one way to do that would be to create a program each destination and set it each host. As you point out would create a million different programs which doesn't seem manageable. I don't think the BPF map works either since that implies we need a lookup (?). It seems like what we need is one program but allow it to be parameterized with per destination information saved in the route (LWT structure).

Yes, that is my proposal. Just using the dst entry as meta-data (which can actually also be an ID for the network namespace the packet is coming from).

My concern with using BPF is that the rest of the kernel doesn't really see the semantics and can't optimize or cache at specific points, because the kernel cannot introspect what the BPF program does (for metadata manipulation, one can e.g. specifiy that the program is "pure", and always provides the same output for some specified given input, thus things can be cached and memorized, but that framework seems very hard to build).

I also fear this becomes a kernel by-pass:

It might be very hard e.g. to apply NFT/netfilter to such packets, if e.g. a redirect happens suddenly and packet flow is diverted from the one the user sees currently based on the interfaces and routing tables.

That's why I am in favor of splitting this patchset down and allow the policies that should be expressed by BPF programs being applied to the specific subsystems (I am not totally against a generic BPF hook in input or output of the protocol engines). E.g. can we deal with static rewriting of L2 addresses in the neighbor cache? We already provide a fast header cache for L2 data which might be used here?

On the other hand, I'm not really sure how to implement for this level of performance this in LWT+BPF either. It seems like one way to do that would be to create a program each destination and set it each host. As you point out would create a million different programs which doesn't seem manageable. I don't think the BPF map works either since that implies we need a lookup (?). It seems like what we need is one program but allow it to be parameterized with per destination information saved in the route (LWT structure).

Quoted 8 lines · Tom Herbert

On the other hand, I'm not really sure how to implement for this level of performance this in LWT+BPF either. It seems like one way to do that would be to create a program each destination and set it each host. As you point out would create a million different programs which doesn't seem manageable. I don't think the BPF map works either since that implies we need a lookup (?). It seems like what we need is one program but allow it to be parameterized with per destination information saved in the route (LWT structure).

Attaching different BPF programs to millions of unique dsts doesn't make any sense. That will obivously will never scale and it's not supposed to scale. This is meant to be used for prefixes which represent a series of endpoints, f.e. all local containers, all non-internal traffic, all vpn traffic, etc. I'm also not sure why we are talking about ILA here, you have written a native implementation, why would you want to solve it with BPF again?

If you want to run a single program for all dsts, feel free to run the same BPF program for each dst. Nobody is forcing you to attach individual programs.

Quoted 5 lines · Thomas Graf

Quoted 2 lines

Dumping and verifying which routes get used might actually already be quite complex on its own. Thus my fear.

We even have an API to query which route is used for a tuple. What else would you like to see?

I am not sure here. Some ideas I had were to allow tcpdump (pf_packet) sockets sniff at interfaces and also gather and dump the metadata to user space (this would depend on bpf programs only doing the modifications in metadata and not in the actual packet).

Or maybe just tracing support (without depending on the eBPF program developer to have added debugging in the BPF program).

Quoted 1 line

This will be addressed with signing AFAIK.

This sounds a bit unrealistic. Signing lots of small programs can be a huge burden to the entity doing the signing (if it is not on the same computer). And as far as I understood the programs should be generated dynamically?

Quoted 2 lines

Would it help if we allow to store the original source used for bytecode generation. What would make it clear which program was used.

I would also be fine with just a strong hash of the bytecode, so the program can be identified accurately. Maybe helps with deduplication later on, too. ;)

Even though I read through the patchset I am not absolutely sure which problem it really solves. Especially because lots of things can be done already at the ingress vs. egress interface (I looked at patch 4 but I am not sure how realistic they are).

Quoted 3 lines

I also don't see how this could possibly scale if all packets must go through a single BPF program. The overhead will be tremendous if you only want to filter a couple of prefixes.

In case of hash table lookup it should be fast. llvm will probably also generate jump table for a few 100 ip addresses, no? Additionally the routing table lookup could be not done at all.

Quoted 7 lines · Hannes Frederic Sowa

Quoted 5 lines · Thomas Graf

Quoted 2 lines

Dumping and verifying which routes get used might actually already be quite complex on its own. Thus my fear.

We even have an API to query which route is used for a tuple. What else would you like to see?

Quoted 4 lines

I am not sure here. Some ideas I had were to allow tcpdump (pf_packet) sockets sniff at interfaces and also gather and dump the metadata to user space (this would depend on bpf programs only doing the modifications in metadata and not in the actual packet).

Not sure I understand. Why does this depend on BPF?

Quoted 2 lines

Or maybe just tracing support (without depending on the eBPF program developer to have added debugging in the BPF program).

Absolutely in favour of that.

Quoted 6 lines

Quoted 1 line

This will be addressed with signing AFAIK.

This sounds a bit unrealistic. Signing lots of small programs can be a huge burden to the entity doing the signing (if it is not on the same computer). And as far as I understood the programs should be generated dynamically?

Right, for generated programs, a hash is a better fit and still sufficient.

Quoted 6 lines

Quoted 2 lines

Would it help if we allow to store the original source used for bytecode generation. What would make it clear which program was used.

I would also be fine with just a strong hash of the bytecode, so the program can be identified accurately. Maybe helps with deduplication later on, too. ;)

OK, I think we all already agreed on doing this.

Quoted 4 lines

Even though I read through the patchset I am not absolutely sure which problem it really solves. Especially because lots of things can be done already at the ingress vs. egress interface (I looked at patch 4 but I am not sure how realistic they are).

Filtering at egress requires to attach the BPF program to all potential outgoing interface and then pass every single packet through the program whereas with LWT BPF, I'm only taking the cost where actually needed.

Quoted 7 lines

Quoted 3 lines

I also don't see how this could possibly scale if all packets must go through a single BPF program. The overhead will be tremendous if you only want to filter a couple of prefixes.

In case of hash table lookup it should be fast. llvm will probably also generate jump table for a few 100 ip addresses, no? Additionally the routing table lookup could be not done at all.

Why would I want to accept the overhead if I simply avoid it? Just parsing the header and doing the hash lookup will add cost, cost for each packet.

Quoted 3 lines · Thomas Graf

Why would I want to accept the overhead if I simply avoid it? Just parsing the header and doing the hash lookup will add cost, cost for each packet.

That is true, but in case you are outside of the namespace, you still have to calculate the cost of doing the FIB lookup for the BPF program each time, too.

E.g. given the lookup cost in a hash for a netnwork namespace pointer vs. the cost of doing a FIB lookup to get a program that does a specific transformation sounds at least in the big O-notiation to be in a better place. ;)

If you have to do both anyway, probably your patchset will perform better, I agree.

{Open question:
Tom brought up the question on whether it is safe to modify the packet in artbirary ways before dst_output(). This is the equivalent to a raw socket injecting illegal headers. This v2 currently assumes that dst_output() is ready to accept invalid header values. This needs to be verified and if not the case, then raw sockets or dst_output() handlers must be fixed as well. Another option is to mark lwtunnel_output() as read-only for now.}

This series implements BPF program invocation from dst entries via the lightweight tunnels infrastructure. The BPF program can be attached to lwtunnel_input(), lwtunnel_output() or lwtunnel_xmit() and sees an L3 skb as context. input is read-only, output can write, xmit can write, push headers, and redirect.

Motiviation for this work:
- Restricting outgoing routes beyond what the route tuple supports
- Per route accounting byond realms
- Fast attachment of L2 headers where header does not require resolving L2 addresses
- ILA like uses cases where L3 addresses are resolved and then routed in an async manner
- Fast encapsulation + redirect. For now limited to use cases where not setting inner and outer offset/protocol is OK.

A couple of samples on how to use it can be found in patch 04.

v1 -> v2:
- Added new BPF_LWT_REROUTE return code for program to indicate that new route lookup should be performed. Suggested by Tom.
- New sample to illustrate rerouting
- New patch 05: Recursion limit for lwtunnel_output for the case when user creates circular dst redirection. Also resolves the issue for ILA.
- Fix to ensure headroom for potential future L2 header is still guaranteed

Thomas Graf (5):
route: Set orig_output when redirecting to lwt on locally generated
traffic
route: Set lwtstate for local traffic and cached input dsts
bpf: BPF for lightweight tunnel encapsulation
bpf: Add samples for LWT-BPF
lwtunnel: Limit number of recursions on output to 5

 include/linux/filter.h        |   2 +-
 include/uapi/linux/bpf.h      |  37 +++-
 include/uapi/linux/lwtunnel.h |  21 ++
 kernel/bpf/verifier.c         |  16 +-
 net/Kconfig                   |   1 +
 net/core/Makefile             |   2 +-
 net/core/filter.c             | 148 ++++++++++++-
 net/core/lwt_bpf.c            | 504 ++++++++++++++++++++++++++++++++++++++++++
 net/core/lwtunnel.c           |  15 +-
 net/ipv4/route.c              |  37 +++-
 samples/bpf/bpf_helpers.h     |   4 +
 samples/bpf/lwt_bpf.c         | 235 ++++++++++++++++++++
 samples/bpf/test_lwt_bpf.sh   | 370 +++++++++++++++++++++++++++++++
 13 files changed, 1373 insertions(+), 19 deletions(-)
 create mode 100644 net/core/lwt_bpf.c
 create mode 100644 samples/bpf/lwt_bpf.c
 create mode 100755 samples/bpf/test_lwt_bpf.sh

--
2.7.4

Quoted 9 lines · Thomas Graf

{Open question:
Tom brought up the question on whether it is safe to modify the packet in artbirary ways before dst_output(). This is the equivalent to a raw socket injecting illegal headers. This v2 currently assumes that dst_output() is ready to accept invalid header values. This needs to be verified and if not the case, then raw sockets or dst_output() handlers must be fixed as well. Another option is to mark lwtunnel_output() as read-only for now.}

The question might not be so much about illegal headers but whether fields in the skbuff related to the packet contents are kept correct. We have protocol, header offsets, offsets for inner protocols also, encapsulation settings, checksum status, checksum offset, checksum

complete value, vlan information. Any or all of which I believe could be turned into being incorrect if we allow the packet to be arbitrarily modified by BPF. This problem is different than raw sockets because LWT operates in the middle of the stack, the skbuff has already been set up which such things.

Quoted 6 lines

This series implements BPF program invocation from dst entries via the lightweight tunnels infrastructure. The BPF program can be attached to lwtunnel_input(), lwtunnel_output() or lwtunnel_xmit() and sees an L3 skb as context. input is read-only, output can write, xmit can write, push headers, and redirect.

Quoted 10 lines

Motiviation for this work:
- Restricting outgoing routes beyond what the route tuple supports
- Per route accounting byond realms
- Fast attachment of L2 headers where header does not require resolving L2 addresses
- ILA like uses cases where L3 addresses are resolved and then routed in an async manner
- Fast encapsulation + redirect. For now limited to use cases where not setting inner and outer offset/protocol is OK.

Is checksum offload supported? By default, at least for Linux, we offload the outer UDP checksum in VXLAN and the other UDP encapsulations for performance.

Quoted 10 lines · Tom Herbert

Quoted 9 lines · Thomas Graf

{Open question:
Tom brought up the question on whether it is safe to modify the packet in artbirary ways before dst_output(). This is the equivalent to a raw socket injecting illegal headers. This v2 currently assumes that dst_output() is ready to accept invalid header values. This needs to be verified and if not the case, then raw sockets or dst_output() handlers must be fixed as well. Another option is to mark lwtunnel_output() as read-only for now.}

Quoted 4 lines

The question might not be so much about illegal headers but whether fields in the skbuff related to the packet contents are kept correct. We have protocol, header offsets, offsets for inner protocols also, encapsulation settings, checksum status, checksum offset, checksum

The headers cannot be extended or reduced so the offsets always remain correct. What can happen is that the header contains invalid data.

Quoted 5 lines

complete value, vlan information. Any or all of which I believe could be turned into being incorrect if we allow the packet to be arbitrarily modified by BPF. This problem is different than raw sockets because LWT operates in the middle of the stack, the skbuff has already been set up which such things.

You keep saying this "middle in the stack" but the point is exactly the same as a raw socket with IPPROTO_RAW and hdrincl, see rawv6_sendmsg() and rawv6_send_hdrincl(). An IPv6 raw socket can feed arbitrary garbage into dst_output(). IPv4 does some minimal sanity checks.

If this is a concern I'm fine with making the dst_output path read-only for now.

Quoted 16 lines

Quoted 6 lines

This series implements BPF program invocation from dst entries via the lightweight tunnels infrastructure. The BPF program can be attached to lwtunnel_input(), lwtunnel_output() or lwtunnel_xmit() and sees an L3 skb as context. input is read-only, output can write, xmit can write, push headers, and redirect.

Quoted 10 lines

Motiviation for this work:
- Restricting outgoing routes beyond what the route tuple supports
- Per route accounting byond realms
- Fast attachment of L2 headers where header does not require resolving L2 addresses
- ILA like uses cases where L3 addresses are resolved and then routed in an async manner
- Fast encapsulation + redirect. For now limited to use cases where not setting inner and outer offset/protocol is OK.

Quoted 3 lines

Is checksum offload supported? By default, at least for Linux, we offload the outer UDP checksum in VXLAN and the other UDP encapsulations for performance.

No. UDP encap is done by setting a tunnel key through a helper and letting the encapsulation device handle this. I don't currently see a point in replicating all of that logic.

Quoted 3 lines · Thomas Graf

The headers cannot be extended or reduced so the offsets always remain correct. What can happen is that the header contains invalid data.

If we can't add/remove headers then doesn't that really limit the utility of these patches? My assumption was that BPF+LWT is needed to allow users to define and implement their own encapsulations, EH insertion, packet modification, etc.

Quoted 6 lines

You keep saying this "middle in the stack" but the point is exactly the same as a raw socket with IPPROTO_RAW and hdrincl, see rawv6_sendmsg() and rawv6_send_hdrincl(). An IPv6 raw socket can feed arbitrary garbage into dst_output(). IPv4 does some minimal sanity checks.

What I mean is that an admin can create a BPF program that run on any user packets (for instance default route could be set). This would be in the path of TCP, UDP, and other protocols tightly integrated with the stack. Packets being routed may be encapsulated, VLAN, have checksum offload, GORed set etc. They also might be looped back in which case the settings in skbuff become receive parameters.

Quoted 8 lines · Tom Herbert

Quoted 3 lines · Thomas Graf

The headers cannot be extended or reduced so the offsets always remain correct. What can happen is that the header contains invalid data.

If we can't add/remove headers then doesn't that really limit the utility of these patches? My assumption was that BPF+LWT is needed to allow users to define and implement their own encapsulations, EH insertion, packet modification, etc.

I thought you were specifically referring to lwtunnel_output(). You can extend headers at lwtunnel_xmit() but you can't for lwtunnel_output() and lwtunnel_input(). The xmit hook is in ip_finish_output2() where it is fine to do so. We have existing code doing this there.

Quoted 6 lines

Quoted 6 lines

You keep saying this "middle in the stack" but the point is exactly the same as a raw socket with IPPROTO_RAW and hdrincl, see rawv6_sendmsg() and rawv6_send_hdrincl(). An IPv6 raw socket can feed arbitrary garbage into dst_output(). IPv4 does some minimal sanity checks.

Quoted 6 lines

What I mean is that an admin can create a BPF program that run on any user packets (for instance default route could be set). This would be in the path of TCP, UDP, and other protocols tightly integrated with the stack. Packets being routed may be encapsulated, VLAN, have checksum offload, GORed set etc. They also might be looped back in which case the settings in skbuff become receive parameters.

You can do the same with act_pedit or cls_bpf at dev_queue_xmit() before or after you go into the encapsulation device. This is a tool for root, if you install a drop all ssh rule then you won't be able to log into the box anymore. If you modify the packet and render it invalid, the packet will be dropped.
If you attach a VLAN header while VLAN offload is already set up, then the hardware will add another VLAN header, this is what I would expect. I truly hope that we don't have code which crashes if we dev_queue_xmit() garbage into any device. That would be horrible.

Do you have a specific example that could be a problem?

Quoted 10 lines · Thomas Graf

You can do the same with act_pedit or cls_bpf at dev_queue_xmit() before or after you go into the encapsulation device. This is a tool for root, if you install a drop all ssh rule then you won't be able to log into the box anymore. If you modify the packet and render it invalid, the packet will be dropped.
If you attach a VLAN header while VLAN offload is already set up, then the hardware will add another VLAN header, this is what I would expect. I truly hope that we don't have code which crashes if we dev_queue_xmit() garbage into any device. That would be horrible.

Quoted 1 line

Do you have a specific example that could be a problem?

I believe Alexander was dealing with problems where drivers were not properly handling IP extension headers. We regularly get reports about

driver checksum failures on edge conditions. Making a fully functional

and efficient transmit data path is nontrivial, there are many assumptions being made some documented some not. When drivers crash we either fix the driver or the protocol stack that is doing something bad.

Quoted 11 lines · Tom Herbert

Quoted 10 lines · Thomas Graf

You can do the same with act_pedit or cls_bpf at dev_queue_xmit() before or after you go into the encapsulation device. This is a tool for root, if you install a drop all ssh rule then you won't be able to log into the box anymore. If you modify the packet and render it invalid, the packet will be dropped.
If you attach a VLAN header while VLAN offload is already set up, then the hardware will add another VLAN header, this is what I would expect. I truly hope that we don't have code which crashes if we dev_queue_xmit() garbage into any device. That would be horrible.

Quoted 4 lines

Quoted 1 line

Do you have a specific example that could be a problem?

I believe Alexander was dealing with problems where drivers were not properly handling IP extension headers. We regularly get reports about

There are many ways to cause IP extension headers to be inserted. How is this specific to BPF or this series?

Quoted 1 line

driver checksum failures on edge conditions. Making a fully functional

Not sure what an "edge condition" is? Untrusted networks? How is drivers crashing on receive related to this series?

Quoted 4 lines

and efficient transmit data path is nontrivial, there are many assumptions being made some documented some not. When drivers crash we either fix the driver or the protocol stack that is doing something bad.

Tom, we have a dozen ways to modify packet content already and we have multiple ways to take raw packet data from userspace and inject them at dev_queue_xmit() level and some even above. What is different for lwtunnel_xmit()?

This is entirely optional and nobody is forced to use any of this. If you don't trust the BPF program then you better not run in. It's about the same as trusting a random tc filter or iptables ruleset. The important point is that integrity is maintained at all times.I would love to address any specific concern.

You need to show that is integrity is maintained with these patches. Part of this can be done, but part of this needs to be established in testing.

I've already given specifics for at least one potential source of issues in routing issues. I would like to know what happens if someone rewrites an IPv4 packet into IPv6 packet or vice versa. AFAICT we would be send an IPv6 using an IPv4 route, or an IPv4 using an IPv6 route. What is supposed to happen in these circumstances? What actually happens?

Similarly, someone overwrites the whole packet with 0xff. What happens when we try to send that?