bpf: BPF for lightweight tunnel encapsulation

Registers new BPF program types which correspond to the LWT hooks:
- BPF_PROG_TYPE_LWT_IN => dst_input()
- BPF_PROG_TYPE_LWT_OUT => dst_output()
- BPF_PROG_TYPE_LWT_XMIT => lwtunnel_xmit()

The separate program types are required to differentiate between the capabilities each LWT hook allows:

* Programs attached to dst_input() or dst_output() are restricted and may only read the data of an skb. This prevent modification and possible invalidation of already validated packet headers on receive and the construction of illegal headers while the IP headers are still being assembled.

* Programs attached to lwtunnel_xmit() are allowed to modify packet content as well as prepending an L2 header via a newly introduced helper bpf_skb_push(). This is safe as lwtunnel_xmit() is invoked after the IP header has been assembled completely.

All BPF programs receive an skb with L3 headers attached and may return one of the following error 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 in lwtunnel_xmit() context)

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

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

+#define LWT_BPF_MAX_HEADROOM 128

net/core/lwt_bpf.c new file +17 -0

+static int run_lwt_bpf(struct sk_buff *skb, struct bpf_lwt_prog *lwt,
+		       struct dst_entry *dst, bool can_redirect)
+{
+	int ret;
+
+	/* Preempt disable is needed to protect per-cpu redirect_info between
+	 * BPF prog and skb_do_redirect(). The call_rcu in bpf_prog_put() and
+	 * access to maps strictly require a rcu_read_lock() for protection,
+	 * mixing with BH RCU lock doesn't work.
+	 */
+	preempt_disable();
+	rcu_read_lock();
+	bpf_compute_data_end(skb);
+	ret = BPF_PROG_RUN(lwt->prog, skb);
+	rcu_read_unlock();
+
+	switch (ret) {

Quoted 30 lines · Thomas Graf

Registers new BPF program types which correspond to the LWT hooks:
- BPF_PROG_TYPE_LWT_IN => dst_input()
- BPF_PROG_TYPE_LWT_OUT => dst_output()
- BPF_PROG_TYPE_LWT_XMIT => lwtunnel_xmit()

The separate program types are required to differentiate between the capabilities each LWT hook allows:

* Programs attached to dst_input() or dst_output() are restricted and may only read the data of an skb. This prevent modification and possible invalidation of already validated packet headers on receive and the construction of illegal headers while the IP headers are still being assembled.

* Programs attached to lwtunnel_xmit() are allowed to modify packet content as well as prepending an L2 header via a newly introduced helper bpf_skb_push(). This is safe as lwtunnel_xmit() is invoked after the IP header has been assembled completely.

All BPF programs receive an skb with L3 headers attached and may return one of the following error 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 in lwtunnel_xmit() context)

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

Quoted 1 line

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

...

Quoted 1 line

+#define LWT_BPF_MAX_HEADROOM 128

why 128?
btw I'm thinking for XDP to use 256, so metadata can be stored in there.

Quoted 32 lines · Alexei Starovoitov

Quoted 31 lines · Thomas Graf

Registers new BPF program types which correspond to the LWT hooks:
- BPF_PROG_TYPE_LWT_IN => dst_input()
- BPF_PROG_TYPE_LWT_OUT => dst_output()
- BPF_PROG_TYPE_LWT_XMIT => lwtunnel_xmit()

The separate program types are required to differentiate between the capabilities each LWT hook allows:

* Programs attached to dst_input() or dst_output() are restricted and may only read the data of an skb. This prevent modification and possible invalidation of already validated packet headers on receive and the construction of illegal headers while the IP headers are still being assembled.

* Programs attached to lwtunnel_xmit() are allowed to modify packet content as well as prepending an L2 header via a newly introduced helper bpf_skb_push(). This is safe as lwtunnel_xmit() is invoked after the IP header has been assembled completely.

All BPF programs receive an skb with L3 headers attached and may return one of the following error 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 in lwtunnel_xmit() context)

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

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

Quoted 6 lines

...

Quoted 1 line

+#define LWT_BPF_MAX_HEADROOM 128

why 128?
btw I'm thinking for XDP to use 256, so metadata can be stored in there.

hopefully not too off-topic but for XDP I would like to see this get

passed down with the program. It would be more generic and drivers could configure the headroom on demand and more importantly verify that a program pushing data is not going to fail at runtime.

Quoted 33 lines · John Fastabend

Quoted 32 lines · Alexei Starovoitov

Quoted 31 lines · Thomas Graf

Registers new BPF program types which correspond to the LWT hooks:
- BPF_PROG_TYPE_LWT_IN => dst_input()
- BPF_PROG_TYPE_LWT_OUT => dst_output()
- BPF_PROG_TYPE_LWT_XMIT => lwtunnel_xmit()

The separate program types are required to differentiate between the capabilities each LWT hook allows:

* Programs attached to dst_input() or dst_output() are restricted and may only read the data of an skb. This prevent modification and possible invalidation of already validated packet headers on receive and the construction of illegal headers while the IP headers are still being assembled.

* Programs attached to lwtunnel_xmit() are allowed to modify packet content as well as prepending an L2 header via a newly introduced helper bpf_skb_push(). This is safe as lwtunnel_xmit() is invoked after the IP header has been assembled completely.

All BPF programs receive an skb with L3 headers attached and may return one of the following error 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 in lwtunnel_xmit() context)

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

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

Quoted 8 lines

Quoted 6 lines

...

Quoted 1 line

+#define LWT_BPF_MAX_HEADROOM 128

why 128?
btw I'm thinking for XDP to use 256, so metadata can be stored in there.

hopefully not too off-topic but for XDP I would like to see this get

definitely off-topic. lwt->headroom is existing concept. Too late to do anything about it.

Quoted 3 lines

passed down with the program. It would be more generic and drivers could configure the headroom on demand and more importantly verify that a program pushing data is not going to fail at runtime.

For xdp I think it will be problematic, since we'd have to check for that value at prog array access to make sure tailcalls are not broken. Mix and match won't be possible.
So what does 'configure the headroom on demand' buys us? Isn't it much easier to tell all drivers "always reserve this much" ? We burn the page anyway.
If it's configurable per driver, then we'd need an api
to retrieve it. Yet the program author doesn't care what the value is. If program needs to do udp encap, it will try do it. No matter what. If xdp_adjust_head() helper fails, the program will likely decide

to drop the packet. In some cases it may decide to punt to stack for further processing, but for high performance dataplane code it's highly unlikely.
If it's configurable to something that is not cache line boundary hw dma performance may suffer and so on.
So I see only cons in such 'configurable headroom' and propose to have fixed 256 bytes headroom for XDP
which is enough for any sensible encap and metadata.

On Tue, Nov 29, 2016 at 02:21:22PM +0100, Thomas Graf wrote:
...

Quoted 1 line

+#define LWT_BPF_MAX_HEADROOM 128

why 128?
btw I'm thinking for XDP to use 256, so metadata can be stored in there.

Quoted 25 lines

net/core/lwt_bpf.c new file +25 -0

+static int run_lwt_bpf(struct sk_buff *skb, struct bpf_lwt_prog *lwt,
+		       struct dst_entry *dst, bool can_redirect)
+{
+	int ret;
+
+	/* Preempt disable is needed to protect per-cpu redirect_info between
+	 * BPF prog and skb_do_redirect(). The call_rcu in bpf_prog_put() and
+	 * access to maps strictly require a rcu_read_lock() for protection,
+	 * mixing with BH RCU lock doesn't work.
+	 */
+	preempt_disable();
+	rcu_read_lock();
+	bpf_compute_data_end(skb);
+	ret = BPF_PROG_RUN(lwt->prog, skb);
+	rcu_read_unlock();
+
+	switch (ret) {
+	case BPF_OK:
+		break;
+
+	case BPF_REDIRECT:
+		if (!can_redirect) {
+			WARN_ONCE(1, "Illegal redirect return code in prog %s\n",
+				  lwt->name ? : "<unknown>");
+			ret = BPF_OK;

net/core/lwt_bpf.c line 68

Quoted 2 lines

net/core/lwt_bpf.c new file +2 -0

+		} else {
+			ret = skb_do_redirect(skb);

I think this assumes that program did bpf_skb_push and L2 header is present. Would it make sense to check that mac_header < network_header here to make sure that it actually happened? I think the cost of single 'if' isn't much. Also skb_do_redirect() can redirect to l3 tunnels like ipip ;) so program shouldn't be doing bpf_skb_push in such case...

May be rename bpf_skb_push to bpf_skb_push_l2 ?
since it's doing skb_reset_mac_header(skb); at the end of it? Or it's probably better to use 'flags' argument to tell whether bpf_skb_push() should set mac_header or not ?

Then this bit:

net/core/lwt_bpf.c line 167

Quoted 5 lines

net/core/lwt_bpf.c new file +5 -0

+		case BPF_OK:
+			/* If the L3 header was expanded, headroom might be too
+			 * small for L2 header now, expand as needed.
+			 */
+			ret = xmit_check_hhlen(skb);

will work fine as well...
which probably needs "mac_header wasn't set" check? or it's fine?

Quoted 6 lines · Alexei Starovoitov

On Tue, Nov 29, 2016 at 02:21:22PM +0100, Thomas Graf wrote:
...

Quoted 1 line

+#define LWT_BPF_MAX_HEADROOM 128

why 128?
btw I'm thinking for XDP to use 256, so metadata can be stored in there.

It's an arbitrary limit to catch obvious misconfiguration. I'm absolutely fine with bumping it to 256.

Quoted 25 lines

Quoted 25 lines

net/core/lwt_bpf.c new file +25 -0

+static int run_lwt_bpf(struct sk_buff *skb, struct bpf_lwt_prog *lwt,
+		       struct dst_entry *dst, bool can_redirect)
+{
+	int ret;
+
+	/* Preempt disable is needed to protect per-cpu redirect_info between
+	 * BPF prog and skb_do_redirect(). The call_rcu in bpf_prog_put() and
+	 * access to maps strictly require a rcu_read_lock() for protection,
+	 * mixing with BH RCU lock doesn't work.
+	 */
+	preempt_disable();
+	rcu_read_lock();
+	bpf_compute_data_end(skb);
+	ret = BPF_PROG_RUN(lwt->prog, skb);
+	rcu_read_unlock();
+
+	switch (ret) {
+	case BPF_OK:
+		break;
+
+	case BPF_REDIRECT:
+		if (!can_redirect) {
+			WARN_ONCE(1, "Illegal redirect return code in prog %s\n",
+				  lwt->name ? : "<unknown>");
+			ret = BPF_OK;

Quoted 8 lines

net/core/lwt_bpf.c line 68

Quoted 2 lines

net/core/lwt_bpf.c new file +2 -0

+		} else {
+			ret = skb_do_redirect(skb);

I think this assumes that program did bpf_skb_push and L2 header is present. Would it make sense to check that mac_header < network_header here to make sure that it actually happened? I think the cost of single 'if' isn't much. Also skb_do_redirect() can redirect to l3 tunnels like ipip ;) so program shouldn't be doing bpf_skb_push in such case...

We are currently guaranteeing mac_header <= network_header given that bpf_skb_push() is calling skb_reset_mac_header() unconditionally.

Even if a program were to push an L2 header and then redirect to an l3 tunnel, __bpf_redirect_no_mac will pull it off again and correct the mac_header offset.

Should we check in __bpf_redirect_common() whether mac_header < nework_header then or add it to lwt-bpf conditional on dev_is_mac_header_xmit()?

Quoted 3 lines · Thomas Graf

Should we check in __bpf_redirect_common() whether mac_header < nework_header then or add it to lwt-bpf conditional on dev_is_mac_header_xmit()?

may be only extra 'if' in lwt-bpf is all we need?

I'm still missing what will happen if we 'forget' to do bpf_skb_push() inside the lwt-bpf program, but still do redirect in lwt_xmit stage to l2 netdev...

Adds a series of test to verify the functionality of attaching BPF programs at LWT hooks.

Also adds a sample which collects a histogram of packet sizes which pass through an LWT hook.

$ ./lwt_len_hist.sh
Starting netserver with host 'IN(6)ADDR_ANY' port '12865' and family AF_UNSPEC
MIGRATED TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to 192.168.253.2 () port 0 AF_INET : demo
Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

87380 16384 16384 10.00 39857.69

Quoted 14 lines · Thomas Graf

Adds a series of test to verify the functionality of attaching BPF programs at LWT hooks.

Also adds a sample which collects a histogram of packet sizes which pass through an LWT hook.

$ ./lwt_len_hist.sh
Starting netserver with host 'IN(6)ADDR_ANY' port '12865' and family AF_UNSPEC
MIGRATED TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to 192.168.253.2 () port 0 AF_INET : demo
Recv   Send    Send
Socket Socket  Message  Elapsed
Size   Size    Size     Time     Throughput
bytes  bytes   bytes    secs.    10^6bits/sec

Quoted 1 line

87380 16384 16384 10.00 39857.69

Nice!

samples/bpf/test_lwt_bpf.c line 193

Quoted 5 lines

samples/bpf/test_lwt_bpf.c new file +5 -0

+	ret = bpf_redirect(ifindex, 0);
+	if (ret < 0) {
+		printk("bpf_redirect() failed: %d\n", ret);
+		return BPF_DROP;
+	}

this 'if' looks a bit weird. You're passing 0 as flags, so this helper will always succeed.
Other sample code often does 'return bpf_redirect(...)' due to this reasoning.

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 see an L3 skb as context. Programs attached to input and output are read-only. Programs attached to lwtunnel_xmit() can modify and redirect, push headers and redirect packets.

The facility can be used to:
- Collect statistics and generate sampling data for a subset of traffic based on the dst utilized by the packet thus allowing to extend the existing realms.
- Apply additional per route/dst filters to prohibit certain outgoing or incoming packets based on BPF filters. In particular, this allows to maintain per dst custom state across multiple packets in BPF maps and apply filters based on statistics and behaviour observed over time.
- Attachment of L2 headers at transmit where resolving the L2 address is not required.
- Possibly many more.

Did you look at the cgroup based hooks which were added recently in ip_finish_output for cgroup ebpf support and in general the cgroup bpf subsystem. Does some of this solve the problem for you already? Would be interesting to hear your opinion on that.