Open source our TC classifier
Subsystems (5)
cover Open source our TC classifier
We've been developing an in-house L4 load balancer based on XDP and TC for a while. Following Alexei's call for more up-to-date examples of production BPF in the kernel tree [1], Cloudflare is making this available under dual GPL-2.0 or BSD 3-clause terms.
The code requires at least v5.3 to function correctly.
1: https://lore.kernel.org/bpf/20200326210719.den5isqxntnoqhmv@ast-mbp/
Lorenz Bauer (1):
selftests/bpf: add cls_redirect classifier
.../selftests/bpf/prog_tests/cls_redirect.c | 456 +++++++ .../selftests/bpf/progs/test_cls_redirect.c | 1058 +++++++++++++++++ .../selftests/bpf/progs/test_cls_redirect.h | 54 + tools/testing/selftests/bpf/test_progs.h | 7 + 4 files changed, 1575 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/cls_redirect.c create mode 100644 tools/testing/selftests/bpf/progs/test_cls_redirect.c create mode 100644 tools/testing/selftests/bpf/progs/test_cls_redirect.h
Signature · 1 line
2.20.1
PATCH 1/1 selftests/bpf: add cls_redirect classifier
cls_redirect is a TC clsact based replacement for the glb-redirect iptables module available at [1]. It enables what GitHub calls "second chance" flows [2], similarly proposed by the Beamer paper [3]. In contrast to glb-redirect, it also supports migrating UDP flows as long as connected sockets are used. cls_redirect is in production at Cloudflare, as part of our own L4 load balancer.
We have modified the encapsulation format slightly from glb-redirect:
glbgue_chained_routing.private_data_type has been repurposed to form a version field and several flags. Both have been arranged in a way that a private_data_type value of zero matches the current glb-redirect behaviour. This means that cls_redirect will understand packets in glb-redirect format, but not vice versa.
The test suite only covers basic features. For example, cls_redirect will correctly forward path MTU discovery packets, but this is not exercised. It is also possible to switch the encapsulation format to GRE on the last hop, which is also not tested.
There are two major distinctions from glb-redirect: first, cls_redirect relies on receiving encapsulated packets directly from a router. This is because we don't have access to the neighbour tables from BPF, yet. See forward_to_next_hop for details. Second, cls_redirect performs decapsulation instead of using separate ipip and sit tunnel devices. This avoids issues with the sit tunnel [4] and makes deploying the classifier
easier: decapsulated packets appear on the same interface, so existing firewall rules continue to work as expected.
The code base started it's life on v4.19, so there are most likely still hold overs from old workarounds. In no particular order:
- The function buf_off is required to defeat a clang optimization that leads to the verifier rejecting the program due to pointer arithmetic in the wrong order.
- The function pkt_parse_ipv6 is force inlined, because it would otherwise be rejected due to returning a pointer to stack memory.
- The functions fill_tuple and classify_tcp contain kludges, because we've run out of function arguments.
- The logic in general is rather nested, due to verifier restrictions. I think this is either because the verifier loses track of constants on the stack, or because it can't track enum like variables.
1: https://github.com/github/glb-director/tree/master/src/glb-redirect
2: https://github.com/github/glb-director/blob/master/docs/development/second-chance-design.md
3: https://www.usenix.org/conference/nsdi18/presentation/olteanu
4: https://github.com/github/glb-director/issues/64
--- .../selftests/bpf/prog_tests/cls_redirect.c | 456 +++++++ .../selftests/bpf/progs/test_cls_redirect.c | 1058 +++++++++++++++++ .../selftests/bpf/progs/test_cls_redirect.h | 54 + tools/testing/selftests/bpf/test_progs.h | 7 + 4 files changed, 1575 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/cls_redirect.c create mode 100644 tools/testing/selftests/bpf/progs/test_cls_redirect.c create mode 100644 tools/testing/selftests/bpf/progs/test_cls_redirect.h
tools/testing/selftests/bpf/prog_tests/cls_redirect.c new file +456 -0
@@ -0,0 +1,456 @@ +// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause +// Copyright (c) 2020 Cloudflare + +#define _GNU_SOURCE + +#include <arpa/inet.h> +#include <string.h> + +#include <linux/pkt_cls.h> + +#include <test_progs.h> + +#include "progs/test_cls_redirect.h" +#include "test_cls_redirect.skel.h" + +#define ENCAP_IP INADDR_LOOPBACK +#define ENCAP_PORT (1234) + +struct addr_port { +in_port_t port; +union { +struct in_addr in_addr; +struct in6_addr in6_addr; + }; +}; + +struct tuple { +int family; +struct addr_port src; +struct addr_port dst; +}; + +static int start_server (const struct sockaddr *addr,socklen_t len,int type) +{ +int fd =socket (addr->sa_family, type,0 ); +if (CHECK_FAIL (fd ==-1 )) +return -1 ; +if (CHECK_FAIL (bind (fd, addr, len) ==-1 )) + goto err; +if (type ==SOCK_STREAM &&CHECK_FAIL (listen (fd,128 ) ==-1 )) + goto err; + +return fd; + +err: +close (fd); +return -1 ; +} + +static int connect_to_server (const struct sockaddr *addr,socklen_t len, +int type) +{ +int fd =socket (addr->sa_family, type,0 ); +if (CHECK_FAIL (fd ==-1 )) +return -1 ; +if (CHECK_FAIL (connect (fd, addr, len))) + goto err; + +return fd; + +err: +close (fd); +return -1 ; +} + +static bool fill_addr_port (const struct sockaddr *sa,struct addr_port *ap) +{ +const struct sockaddr_in6 *in6; +const struct sockaddr_in *in; + +switch (sa->sa_family) { +case AF_INET : + in = (const struct sockaddr_in *)sa; + ap->in_addr = in->sin_addr; + ap->port = in->sin_port; +return true; + +case AF_INET6 : + in6 = (const struct sockaddr_in6 *)sa; + ap->in6_addr = in6->sin6_addr; + ap->port = in6->sin6_port; +return true; + +default : +return false; + } +} + +static bool set_up_conn (const struct sockaddr *addr,socklen_t len,int type, +int *server,int *conn,struct tuple *tuple) +{ +struct sockaddr_storage ss; +socklen_t slen =sizeof (ss); +struct sockaddr *sa = (struct sockaddr *)&ss; + + *server =start_server (addr, len, type); +if (*server <0 ) +return false; + +if (CHECK_FAIL (getsockname (*server, sa, &slen))) + goto close_server; + + *conn =connect_to_server (sa, slen, type); +if (*conn <0 ) + goto close_server; + +/* We want to simulate packets arriving at conn, so we have to +* swap src and dst. +*/ + slen =sizeof (ss); +if (CHECK_FAIL (getsockname (*conn, sa, &slen))) + goto close_conn; + +if (CHECK_FAIL (!fill_addr_port (sa, &tuple->dst))) + goto close_conn; + + slen =sizeof (ss); +if (CHECK_FAIL (getpeername (*conn, sa, &slen))) + goto close_conn; + +if (CHECK_FAIL (!fill_addr_port (sa, &tuple->src))) + goto close_conn; + + tuple->family = ss.ss_family; +return true; + +close_conn: +close (*conn); + *conn =-1 ; +close_server: +close (*server); + *server =-1 ; +return false; +} + +static socklen_t prepare_addr (struct sockaddr_storage *addr,int family) +{ +struct sockaddr_in *addr4; +struct sockaddr_in6 *addr6; + +switch (family) { +case AF_INET : + addr4 = (struct sockaddr_in *)addr; +memset (addr4,0 ,sizeof (*addr4)); + addr4->sin_family = family; + addr4->sin_addr.s_addr =htonl (INADDR_LOOPBACK ); +return sizeof (*addr4); +case AF_INET6 : + addr6 = (struct sockaddr_in6 *)addr; +memset (addr6,0 ,sizeof (*addr6)); + addr6->sin6_family = family; + addr6->sin6_addr = in6addr_loopback; +return sizeof (*addr6); +default : +fprintf (stderr,"Invalid family %d" , family); +return 0 ; + } +} + +static bool was_decapsulated (struct bpf_prog_test_run_attr *tattr) +{ +return tattr->data_size_out < tattr->data_size_in; +} + +enum type { +UDP , +TCP , + __NR_KIND, +}; + +enum hops { +NO_HOPS , +ONE_HOP , +}; + +enum flags { +NONE , +SYN , +ACK , +}; + +enum conn { +KNOWN_CONN , +UNKNOWN_CONN , +}; + +enum result { +ACCEPT , +FORWARD , +}; + +struct test_cfg { +enum type type; +enum result result; +enum conn conn; +enum hops hops; +enum flags flags; +}; + +static int test_str (void *buf,size_t len,const struct test_cfg *test, +int family) +{ +const char *family_str, *type, *conn, *hops, *result, *flags; + + family_str ="IPv4" ; +if (family ==AF_INET6 ) + family_str ="IPv6" ; + + type ="TCP" ; +if (test->type ==UDP ) + type ="UDP" ; + + conn ="known" ; +if (test->conn ==UNKNOWN_CONN ) + conn ="unknown" ; + + hops ="no hops" ; +if (test->hops ==ONE_HOP ) + hops ="one hop" ; + + result ="accept" ; +if (test->result ==FORWARD ) + result ="forward" ; + + flags ="none" ; +if (test->flags ==SYN ) + flags ="SYN" ; +else if (test->flags ==ACK ) + flags ="ACK" ; + +return snprintf (buf, len,"%s %s %s %s (%s, flags: %s)" , family_str, + type, result, conn, hops, flags); +} + +static struct test_cfg tests[] = { + {TCP ,ACCEPT ,UNKNOWN_CONN ,NO_HOPS ,SYN }, + {TCP ,ACCEPT ,UNKNOWN_CONN ,NO_HOPS ,ACK }, + {TCP ,FORWARD ,UNKNOWN_CONN ,ONE_HOP ,ACK }, + {TCP ,ACCEPT ,KNOWN_CONN ,ONE_HOP ,ACK }, + {UDP ,ACCEPT ,UNKNOWN_CONN ,NO_HOPS ,NONE }, + {UDP ,FORWARD ,UNKNOWN_CONN ,ONE_HOP ,NONE }, + {UDP ,ACCEPT ,KNOWN_CONN ,ONE_HOP ,NONE }, +}; + +static void encap_init (encap_headers_t *encap,uint8_t hop_count,uint8_t proto) +{ +const uint8_t hlen = + (sizeof (struct guehdr ) /sizeof (uint32_t )) + hop_count; + *encap = (encap_headers_t ){ + .eth = { .h_proto =htons (ETH_P_IP ) }, + .ip = { + .ihl =5 , + .version =4 , + .ttl =IPDEFTTL , + .protocol =IPPROTO_UDP , + .daddr =htonl (ENCAP_IP ) + }, + .udp = { + .dest =htons (ENCAP_PORT ), + }, + .gue = { + .hlen = hlen, + .proto_ctype = proto + }, + .unigue = { + .hop_count = hop_count + }, + }; +} + +static size_t build_input (const struct test_cfg *test,void *const buf, +const struct tuple *tuple) +{ +in_port_t sport = tuple->src.port; +encap_headers_t encap; +struct iphdr ip; +struct ipv6hdr ipv6; +struct tcphdr tcp; +struct udphdr udp; +struct in_addr next_hop; +uint8_t *p = buf; +int proto; + + proto =IPPROTO_IPIP ; +if (tuple->family ==AF_INET6 ) + proto =IPPROTO_IPV6 ; + +encap_init (&encap, test->hops ==ONE_HOP ?1 :0 , proto); + p =mempcpy (p, &encap,sizeof (encap)); + +if (test->hops ==ONE_HOP ) { + next_hop = (struct in_addr ){ .s_addr =htonl (0x7f000002 ) }; + p =mempcpy (p, &next_hop,sizeof (next_hop)); + } + + proto =IPPROTO_TCP ; +if (test->type ==UDP ) + proto =IPPROTO_UDP ; + +switch (tuple->family) { +case AF_INET : + ip = (struct iphdr ){ + .ihl =5 , + .version =4 , + .ttl =IPDEFTTL , + .protocol = proto, + .saddr = tuple->src.in_addr.s_addr, + .daddr = tuple->dst.in_addr.s_addr, + }; + p =mempcpy (p, &ip,sizeof (ip)); +break ; +case AF_INET6 : + ipv6 = (struct ipv6hdr ){ + .version =6 , + .hop_limit =IPDEFTTL , + .nexthdr = proto, + .saddr = tuple->src.in6_addr, + .daddr = tuple->dst.in6_addr, + }; + p =mempcpy (p, &ipv6,sizeof (ipv6)); +break ; +default : +return 0 ; + } + +if (test->conn ==UNKNOWN_CONN ) + sport--; + +switch (test->type) { +case TCP : + tcp = (struct tcphdr ){ + .source = sport, + .dest = tuple->dst.port, + }; +if (test->flags ==SYN ) + tcp.syn = true; +if (test->flags ==ACK ) + tcp.ack = true; + p =mempcpy (p, &tcp,sizeof (tcp)); +break ; +case UDP : + udp = (struct udphdr ){ + .source = sport, + .dest = tuple->dst.port, + }; + p =mempcpy (p, &udp,sizeof (udp)); +break ; +default : +return 0 ; + } + +return (void *)p - buf; +} + +static void close_fds (int *fds,int n) +{ +int i; + +for (i =0 ; i < n; i++) +if (fds[i] >0 ) +close (fds[i]); +} + +void test_cls_redirect (void ) +{ +struct test_cls_redirect *skel =NULL ; +struct bpf_prog_test_run_attr tattr = {}; +int families[] = {AF_INET ,AF_INET6 }; +struct sockaddr_storage ss; +struct sockaddr *addr; +socklen_t slen; +int i, j, err; + +int servers[__NR_KIND][ARRAY_SIZE (families)] = {}; +int conns[__NR_KIND][ARRAY_SIZE (families)] = {}; +struct tuple tuples[__NR_KIND][ARRAY_SIZE (families)]; + + skel =test_cls_redirect__open (); +if (CHECK_FAIL (!skel)) +return ; + + skel->rodata->ENCAPSULATION_IP =htonl (ENCAP_IP ); + skel->rodata->ENCAPSULATION_PORT =htons (ENCAP_PORT ); + +if (CHECK_FAIL (test_cls_redirect__load (skel))) + goto cleanup; + + addr = (struct sockaddr *)&ss; +for (i =0 ; i <ARRAY_SIZE (families); i++) { + slen =prepare_addr (&ss, families[i]); +if (CHECK_FAIL (!slen)) + goto cleanup; + +if (CHECK_FAIL (!set_up_conn (addr, slen,SOCK_DGRAM , + &servers[UDP ][i], &conns[UDP ][i], + &tuples[UDP ][i]))) + goto cleanup; + +if (CHECK_FAIL (!set_up_conn (addr, slen,SOCK_STREAM , + &servers[TCP ][i], &conns[TCP ][i], + &tuples[TCP ][i]))) + goto cleanup; + } + + tattr.prog_fd =bpf_program__fd (skel->progs.cls_redirect); +for (i =0 ; i <ARRAY_SIZE (tests); i++) { +struct test_cfg *test = &tests[i]; + +for (j =0 ; j <ARRAY_SIZE (families); j++) { +struct tuple *tuple = &tuples[test->type][j]; +char input[256 ]; +char tmp[256 ]; + +test_str (tmp,sizeof (tmp), test, tuple->family); +if (!test__start_subtest (tmp)) +continue ; + + tattr.data_out = tmp; + tattr.data_size_out =sizeof (tmp); + + tattr.data_in = input; + tattr.data_size_in =build_input (test, input, tuple); +if (CHECK_FAIL (!tattr.data_size_in)) +continue ; + + err =bpf_prog_test_run_xattr (&tattr); +if (CHECK_FAIL (err)) +continue ; + +if (tattr.retval !=TC_ACT_REDIRECT ) { +PRINT_FAIL ("expected TC_ACT_REDIRECT, got %d\n" , + tattr.retval); +continue ; + } + +switch (test->result) { +case ACCEPT : +if (CHECK_FAIL (!was_decapsulated (&tattr))) +continue ; +break ; +case FORWARD : +if (CHECK_FAIL (was_decapsulated (&tattr))) +continue ; +break ; +default : +PRINT_FAIL ("unknown result %d\n" , test->result); +continue ; + } + } + } + +cleanup: +test_cls_redirect__destroy (skel); +close_fds ((int *)servers,sizeof (servers) /sizeof (servers[0 ][0 ])); +close_fds ((int *)conns,sizeof (conns) /sizeof (conns[0 ][0 ])); +}
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +1058 -0
1,058 lines not on this page · raw message
tools/testing/selftests/bpf/progs/test_cls_redirect.h new file +54 -0
54 lines not on this page · raw message
tools/testing/selftests/bpf/test_progs.h +7 -0
@@ -105,6 +105,13 @@ struct ipv6_packet { } __packed;extern struct ipv6_packet pkt_v6; +#define PRINT_FAIL(format...) \ + ({ \ + test__fail(); \ + fprintf(stdout, "%s:FAIL:%d ", __func__, __LINE__); \ + fprintf(stdout, ##format); \ + }) + #define _CHECK(condition, tag, duration, format...) ({ \ int __ret = !!(condition); \ int __save_errno = errno; \
Signature · 1 line
2.20.1
Re: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 6 lines · Lorenz Bauer
cls_redirectis a TC clsact based replacement for the glb-redirect iptables module available at [1]. It enables what GitHub calls "second chance" flows [2], similarly proposed by the Beamer paper [3]. In contrast to glb-redirect, it also supports migrating UDP flows as long as connected sockets are used.cls_redirectis in production at Cloudflare, as part of our own L4 load balancer.
This is awesome. Thank you for contributing!
Applied.
Quoted 3 lines
There are two major distinctions from glb-redirect: first,
cls_redirectrelies on receiving encapsulated packets directly from a router. This is because we don't have access to the neighbour tables from BPF, yet. See
Let's make it available then :)
Quoted 10 lines
The code base started it's life on v4.19, so there are most likely still hold overs from old workarounds. In no particular order:
- The function
buf_offis required to defeat a clang optimization that leads to the verifier rejecting the program due to pointer arithmetic in the wrong order.- The function
pkt_parse_ipv6is force inlined, because it would otherwise be rejected due to returning a pointer to stack memory.
Quoted 6 lines
- The functions
fill_tupleandclassify_tcpcontain kludges, because we've run out of function arguments.- The logic in general is rather nested, due to verifier restrictions. I think this is either because the verifier loses track of constants on the stack, or because it can't track enum like variables.
Have you tried undoing these workarounds to check the latest verifier? If they're still needed we certainly have to improve the verifier.
Quoted 1 line
+#include "
test_cls_redirect.skel.h"
Do you use skeleton internally as well or was it just for selftests? ;)
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 86
Quoted 5 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +5
-0+_Static_assert ( +sizeof (flow_ports_t) != + offsetofend(struct bpf_sock_tuple, ipv4.dport) - + offsetof(struct bpf_sock_tuple, ipv4.sport) - 1, +"flow_ports_t must match sport and dport in struct bpf_sock_tuple" );
Nice. I didn't realize clang supports it. Of course it should.
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));
Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.
Quoted 19 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +19
-0+ +typedef struct buf { +struct __sk_buff *skb; +net_ptr head; +/* NB: tail musn't have alignment other than 1, otherwise +* LLVM will go and eliminate code, e.g. when checking packet lengths. +*/ +uint8_t *const tail; +}buf_t ; + +static size_t buf_off (const buf_t *buf) +{ +/* Clang seems to optimize constructs like +* a - b + c +* if c is known: +* r? = c +* r? -= b +* r? += a +*
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 146
Quoted 10 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +10
-0+* This is a problem if a and b are packet pointers, +* since the verifier allows subtracting two pointers to +* get a scalar, but not a scalar and a pointer. +* +* Use inline asm to break this optimization. +*/ +size_t off = (size_t )buf->head; + asm("%0 -= %1" :"+r" (off) :"r" (buf->skb->data)); +return off; +}
We need to look into this one.
This part is not gated by allow_ptr_leaks.
if (dst_reg == off_reg) {
/* scalar -= pointer. Creates an unknown scalar */
verbose(env, "R%d tried to subtract pointer from scalar\n",
dst);
return -EACCES;
}Hopefully not too hard to fix.
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +11
-0+ +static bool pkt_skip_ipv6_extension_headers (buf_t *pkt, +const struct ipv6hdr *ipv6, +uint8_t *upper_proto, +bool *is_fragment) +{ +/* We understand five extension headers. +* https://tools.ietf.org/html/rfc8200#section-4.1 states that all +* headers should occur once, except Destination Options, which may +* occur twice. Hence we give up after 6 headers. +*/
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 290
Quoted 10 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +10
-0+struct { +uint8_t next; +uint8_t len; + } exthdr = { + .next = ipv6->nexthdr, + }; + *is_fragment = false; + +#pragma clang loop unroll(full) +for (int i =0 ; i <6 ; i++) {
unroll is still needed even with bounded loop support in the verifier?
Quoted 5 lines
+/* This function has to be inlined, because the verifier otherwise rejects it
+ * due to returning a pointer to the stack. This is technically correct, since
+ * scratch is allocated on the stack. However, this usage should be safe since
+ * it's the callers stack after all.
+ */
Interesting. The verifier can recognize that ptr to stack can be safe in some cases. When I added that check I didn't think that the code can be as tricky as this :)
Quoted 43 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +43
-0+static verdict_t process_ipv4 (buf_t *pkt,metrics_t *metrics) +{ +switch (ipv4->protocol) { +case IPPROTO_ICMP : +return process_icmpv4 (pkt, metrics); + +case IPPROTO_TCP : +return process_tcp (pkt, ipv4,sizeof (*ipv4), metrics); + +case IPPROTO_UDP : +return process_udp (pkt, ipv4,sizeof (*ipv4), metrics); + +default : + metrics->errors_total_unknown_l4_proto++; +return INVALID ; + } +} + +static verdict_t process_ipv6 (buf_t *pkt,metrics_t *metrics) + if (is_fragment) { + metrics->errors_total_fragmented_ip++; +return INVALID ; + } + +switch (l4_proto) { +case IPPROTO_ICMPV6 : +return process_icmpv6 (pkt, metrics); + +case IPPROTO_TCP : +return process_tcp (pkt, ipv6,sizeof (*ipv6), metrics); + +case IPPROTO_UDP : +return process_udp (pkt, ipv6,sizeof (*ipv6), metrics); + +default : + metrics->errors_total_unknown_l4_proto++; +return INVALID ; + } +} + +SEC("classifier/cls_redirect") +int cls_redirect (struct __sk_buff *skb) +{
...
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 1020
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +9
-0+verdict_t verdict; +switch (encap->gue.proto_ctype) { +case IPPROTO_IPIP : + verdict =process_ipv4 (&pkt, metrics); +break ; + +case IPPROTO_IPV6 : + verdict =process_ipv6 (&pkt, metrics); +break ;
The code flow looks pretty clean.
I didn't find the copy-paste of ipv[46] -> tcp/udp you were mentioning.
So that old issue is now gone?
Re: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 9 lines · Alexei Starovoitov
Quoted 6 lines · Lorenz Bauer
cls_redirectis a TC clsact based replacement for the glb-redirect iptables module available at [1]. It enables what GitHub calls "second chance" flows [2], similarly proposed by the Beamer paper [3]. In contrast to glb-redirect, it also supports migrating UDP flows as long as connected sockets are used.cls_redirectis in production at Cloudflare, as part of our own L4 load balancer.
Quoted 8 lines
This is awesome. Thank you for contributing!
Applied.Quoted 3 lines
There are two major distinctions from glb-redirect: first,
cls_redirectrelies on receiving encapsulated packets directly from a router. This is because we don't have access to the neighbour tables from BPF, yet. SeeLet's make it available then :)
Yes, I've been dragging my feet on this. It seems like the fib_lookup does almost what we want, but I need to experiment with it. In the best case, we'd have a helper that does the following:
* Try and find a neighbour
* Return it if one exists
* Otherwise, asynchronously trigger neighbour discovery (if it makes sense)
* And return the default gateway
I should probably start a new thread about this on the list.
Quoted 18 lines
Quoted 11 lines
The code base started it's life on v4.19, so there are most likely still hold overs from old workarounds. In no particular order:
- The function
buf_offis required to defeat a clang optimization that leads to the verifier rejecting the program due to pointer arithmetic in the wrong order.- The function
pkt_parse_ipv6is force inlined, because it would otherwise be rejected due to returning a pointer to stack memory.Quoted 6 lines
- The functions
fill_tupleandclassify_tcpcontain kludges, because we've run out of function arguments.- The logic in general is rather nested, due to verifier restrictions. I think this is either because the verifier loses track of constants on the stack, or because it can't track enum like variables.
Quoted 6 lines
Have you tried undoing these workarounds to check the latest verifier? If they're still needed we certainly have to improve the verifier.
Quoted 1 line
+#include "
test_cls_redirect.skel.h"Do you use skeleton internally as well or was it just for selftests? ;)
Only for selftests :) Our internal tooling is all Go based. skeleton is really nice
though, so I'll make sure to steal some ideas!
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 86
Quoted 6 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +5
-0+_Static_assert ( +sizeof (flow_ports_t) != + offsetofend(struct bpf_sock_tuple, ipv4.dport) - + offsetof(struct bpf_sock_tuple, ipv4.sport) - 1, +"flow_ports_t must match sport and dport in struct bpf_sock_tuple" );Nice. I didn't realize clang supports it. Of course it should.
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.
Yes, I think so.
Quoted 55 lines
Quoted 19 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +19
-0+ +typedef struct buf { +struct __sk_buff *skb; +net_ptr head; +/* NB: tail musn't have alignment other than 1, otherwise +* LLVM will go and eliminate code, e.g. when checking packet lengths. +*/ +uint8_t *const tail; +}buf_t ; + +static size_t buf_off (const buf_t *buf) +{ +/* Clang seems to optimize constructs like +* a - b + c +* if c is known: +* r? = c +* r? -= b +* r? += a +* tools/testing/selftests/bpf/progs/test_cls_redirect.c line 146
Quoted 10 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +10
-0+* This is a problem if a and b are packet pointers, +* since the verifier allows subtracting two pointers to +* get a scalar, but not a scalar and a pointer. +* +* Use inline asm to break this optimization. +*/ +size_t off = (size_t )buf->head; + asm("%0 -= %1" :"+r" (off) :"r" (buf->skb->data)); +return off; +}We need to look into this one.
This part is not gated byallow_ptr_leaks.if (dst_reg == off_reg) { /* scalar -= pointer. Creates an unknown scalar */ verbose(env, "R%d tried to subtract pointer from scalar\n", dst); return -EACCES; }Hopefully not too hard to fix.
Quoted 15 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +15
-0+ +static bool pkt_skip_ipv6_extension_headers (buf_t *pkt, +const struct ipv6hdr *ipv6, +uint8_t *upper_proto, +bool *is_fragment) +{ +/* We understand five extension headers. +* https://tools.ietf.org/html/rfc8200#section-4.1 states that all +* headers should occur once, except Destination Options, which may +* occur twice. Hence we give up after 6 headers. +*/ +struct { +uint8_t next; +uint8_t len; + } exthdr = {
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 290
Quoted 6 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +6
-0+ .next = ipv6->nexthdr, + }; + *is_fragment = false; + +#pragma clang loop unroll(full) +for (int i =0 ; i <6 ; i++) {unroll is still needed even with bounded loop support in the verifier?
I've just tried removing this on bpf-next. pkt_ipv4_checksum works without the pragma,pkt_skip_ipv6_extension_headers fails with the following message:
libbpf: load bpf program failed: Invalid argument
libbpf: -- BEGIN DUMP LOG ---
libbpf:
476: for (int i = 0; i < 6; i++) {
477: switch (exthdr.next) {
back-edge from insn 476 to 477
processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
libbpf: -- END LOG --
libbpf: failed to load program 'classifier/cls_redirect'
libbpf: failed to load object 'test_cls_redirect'
libbpf: failed to load BPF skeleton 'test_cls_redirect': -4007 test_cls_redirect:FAIL:385
#10 cls_redirect:FAIL
Summary: 0/0 PASSED, 0 SKIPPED, 1 FAILED
Quoted 65 lines
Quoted 7 lines
+/* This function has to be inlined, because the verifier otherwise rejects it
+ * due to returning a pointer to the stack. This is technically correct, since
+ * scratch is allocated on the stack. However, this usage should be safe since
+ * it's the callers stack after all.
+ */Interesting. The verifier can recognize that ptr to stack can be safe in some cases. When I added that check I didn't think that the code can be as tricky as this :)
Quoted 43 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +43
-0+static verdict_t process_ipv4 (buf_t *pkt,metrics_t *metrics) +{ +switch (ipv4->protocol) { +case IPPROTO_ICMP : +return process_icmpv4 (pkt, metrics); + +case IPPROTO_TCP : +return process_tcp (pkt, ipv4,sizeof (*ipv4), metrics); + +case IPPROTO_UDP : +return process_udp (pkt, ipv4,sizeof (*ipv4), metrics); + +default : + metrics->errors_total_unknown_l4_proto++; +return INVALID ; + } +} + +static verdict_t process_ipv6 (buf_t *pkt,metrics_t *metrics) + if (is_fragment) { + metrics->errors_total_fragmented_ip++; +return INVALID ; + } + +switch (l4_proto) { +case IPPROTO_ICMPV6 : +return process_icmpv6 (pkt, metrics); + +case IPPROTO_TCP : +return process_tcp (pkt, ipv6,sizeof (*ipv6), metrics); + +case IPPROTO_UDP : +return process_udp (pkt, ipv6,sizeof (*ipv6), metrics); + +default : + metrics->errors_total_unknown_l4_proto++; +return INVALID ; + } +} + +SEC("classifier/cls_redirect") +int cls_redirect (struct __sk_buff *skb) +{...
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 1020
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +9
-0+verdict_t verdict; +switch (encap->gue.proto_ctype) { +case IPPROTO_IPIP : + verdict =process_ipv4 (&pkt, metrics); +break ; + +case IPPROTO_IPV6 : + verdict =process_ipv6 (&pkt, metrics); +break ;
Quoted 4 lines
The code flow looks pretty clean.
I didn't find the copy-paste of ipv[46] -> tcp/udp you were mentioning.
So that old issue is now gone?
The biggest offenders are fill_tuple (which is purely a hack) as well as classify_tcp.
I'd really like to call classify_tcp from cls_redirect(), using saved packet pointers and lengths.
Right now the function is called starting from process_ipv4 and process_ipv6, which
means all of those arguments have to be passed down somehow.
Signature · 4 lines
Lorenz Bauer | Systems Engineer 6th Floor, County Hall/The Riverside Building, SE1 7PB, UK www.cloudflare.com
Daniel Borkmann
maintainerRe: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 2 lines · Lorenz Bauer
On Sun, 26 Apr 2020 at 18:33, Alexei Starovoitov
<[email protected]> wrote:
[...]
Quoted 12 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.
Quoted 1 line
Yes, I think so.
Just for some more context [0]. I think the problem is a bit more complex in general. Generally, _any_ kind of pointer to some data (except for the stack) is currently treated as byte-by-byte copy from __builtin_memcpy() and other similarly available __builtin_*() helpers on BPF backend since the backend cannot make any assumptions about the data's alignment and whether unaligned access from the underlying arch is ok & efficient (the latter the verifier does judge for us however). So it's definitely not just limited to xdp->data. There is also the issue that while access to any non-stack data can be unaligned, access to the stack however cannot. I've discussed a while back with Yonghong about potential solutions. One would be to add a small patch to the BPF backend to enable __builtin_*() helpers to allow for unaligned access which could then be opt-ed in e.g. via -mattr from llc for the case when we know that the compiled program only runs on archs with efficient unaligned access anyway. However, this still potentially breaks with the BPF stack for the case when objects are, for example, larger than size 8 but with a natural alignment smaller than 8 where __builtin_memcpy() would then decide to emit dw-typed load/stores. But for these cases could then be annotated via __aligned(8) on stack. So this is basically what we do right now as a generic workaround in Cilium [0], meaning, our own memcpy/memset with optimal number of instructions and __aligned(8) where needed; most of the time this __aligned(8) is not needed, so it's really just a few places, and we also have a cocci scripts to catch these during development if needed. Anyway, real thing would be to allow the BPF stack for unaligned access as well and then BPF backend could nicely solve this in a native way w/o any workarounds, but that is tbd.
Thanks,
Daniel
[0] https://github.com/cilium/cilium/blob/master/bpf/include/bpf/builtins.h
Re: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 43 lines · Daniel Borkmann
Quoted 2 lines · Lorenz Bauer
On Sun, 26 Apr 2020 at 18:33, Alexei Starovoitov
<[email protected]> wrote:[...]
Quoted 12 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.Quoted 1 line
Yes, I think so.
Just for some more context [0]. I think the problem is a bit more complex in general. Generally, _any_ kind of pointer to some data (except for the stack) is currently treated as byte-by-byte copy from
__builtin_memcpy()and other similarly available __builtin_*() helpers on BPF backend since the backend cannot make any assumptions about the data's alignment and whether unaligned access from the underlying arch is ok & efficient (the latter the verifier does judge for us however). So it's definitely not just limited toxdp->data. There is also the issue that while access to any non-stack data can be unaligned, access to the stack however cannot. I've discussed a while back with Yonghong about potential solutions. One would be to add a small patch to the BPF backend to enable __builtin_*() helpers to allow for unaligned access which could then be opt-ed in e.g. via -mattr from llc for the case when we know that the compiled program only runs on archs with efficient unaligned access anyway. However, this still potentially breaks with the BPF stack for the case when objects are, for example, larger than size 8 but with a natural alignment smaller than 8 where__builtin_memcpy()would then decide to emit dw-typed load/stores. But for these cases could then be annotated via__aligned(8)on stack. So this is basically what we do right now as a generic workaround in Cilium [0], meaning, our own memcpy/memset with optimal number of instructions and__aligned(8)where needed; most of the time this__aligned(8)is not needed, so it's really just a few places, and we also have a cocci scripts to catch these during development if needed. Anyway, real thing would be to allow the BPF stack for unaligned access as well and then BPF backend could nicely solve this in a native way w/o any workarounds, but that is tbd.
Quoted 4 lines
Thanks,
Daniel[0] https://github.com/cilium/cilium/blob/master/bpf/include/bpf/builtins.h
Daniel,
do you mind adding such memcpy to libbpf ?
Daniel Borkmann
maintainerRe: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 44 lines · Alexei Starovoitov
Quoted 43 lines · Daniel Borkmann
Quoted 2 lines · Lorenz Bauer
On Sun, 26 Apr 2020 at 18:33, Alexei Starovoitov
<[email protected]> wrote:[...]
Quoted 12 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.Quoted 1 line
Yes, I think so.
Just for some more context [0]. I think the problem is a bit more complex in general. Generally, _any_ kind of pointer to some data (except for the stack) is currently treated as byte-by-byte copy from
__builtin_memcpy()and other similarly available __builtin_*() helpers on BPF backend since the backend cannot make any assumptions about the data's alignment and whether unaligned access from the underlying arch is ok & efficient (the latter the verifier does judge for us however). So it's definitely not just limited toxdp->data. There is also the issue that while access to any non-stack data can be unaligned, access to the stack however cannot. I've discussed a while back with Yonghong about potential solutions. One would be to add a small patch to the BPF backend to enable __builtin_*() helpers to allow for unaligned access which could then be opt-ed in e.g. via -mattr from llc for the case when we know that the compiled program only runs on archs with efficient unaligned access anyway. However, this still potentially breaks with the BPF stack for the case when objects are, for example, larger than size 8 but with a natural alignment smaller than 8 where__builtin_memcpy()would then decide to emit dw-typed load/stores. But for these cases could then be annotated via__aligned(8)on stack. So this is basically what we do right now as a generic workaround in Cilium [0], meaning, our own memcpy/memset with optimal number of instructions and__aligned(8)where needed; most of the time this__aligned(8)is not needed, so it's really just a few places, and we also have a cocci scripts to catch these during development if needed. Anyway, real thing would be to allow the BPF stack for unaligned access as well and then BPF backend could nicely solve this in a native way w/o any workarounds, but that is tbd.
Quoted 7 lines
Quoted 4 lines
Thanks,
Daniel[0] https://github.com/cilium/cilium/blob/master/bpf/include/bpf/builtins.h
Daniel,
do you mind adding such memcpy to libbpf ?
We could do that, yeah. Is there a way from BPF C code when compiling with clang to get to the actual underlying architecture (x86-64, arm64, ppc, etc) when compiling with -target bpf so that we can always fall back to __builtin_*() for those where verifier would bail out on unaligned access? Keep in mind the __bpf_memcpy() and __bpf_memzero() from [0] are fully compile time resolved and I did the implementation for sizes of 1,2,4,..., 96 where the latter is in two' increments, so no odd buffer sizes as we don't need them in our code. If someone does hit such an odd case, then I'm currently throwing a compilation error via __throw_build_bug(). Latter is a nice way to be able to guarantee that a switch/case or if condition is never hit during compilation time. It resolves to __builtin_trap() which is not implemented in the BPF backend and therefore yells to the developer when built into the code (this has a nice property which wouldn't work with BUILD_BUG_ON() for example). Anyway, what I'm saying is that either we'd need the full thing with all sizes or document that unsupported size would be hit when __builtin_trap() assertion is seen.
Thanks,
Daniel
Re: [PATCH 1/1] selftests/bpf: add cls_redirect classifier
Quoted 54 lines · Daniel Borkmann
Quoted 44 lines · Alexei Starovoitov
Quoted 43 lines · Daniel Borkmann
Quoted 2 lines · Lorenz Bauer
On Sun, 26 Apr 2020 at 18:33, Alexei Starovoitov
<[email protected]> wrote:[...]
Quoted 12 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c line 117
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_cls_redirect.c new file +8
-0+/* Linux packet pointers are either aligned to NET_IP_ALIGN (aka 2 bytes), +* or not aligned if the arch supports efficient unaligned access. +* +* Since the verifier ensures that eBPF packet accesses follow these rules, +* we can tell LLVM to emit code as if we always had a larger alignment. +* It will yell at us if we end up on a platform where this is not valid. +*/ +typedef uint8_t *net_ptr __attribute__((align_value (8 )));Wow. I didn't know about this attribute.
I wonder whether it can help Daniel's memcpy hack.Quoted 1 line
Yes, I think so.
Just for some more context [0]. I think the problem is a bit more complex in general. Generally, _any_ kind of pointer to some data (except for the stack) is currently treated as byte-by-byte copy from
__builtin_memcpy()and other similarly available __builtin_*() helpers on BPF backend since the backend cannot make any assumptions about the data's alignment and whether unaligned access from the underlying arch is ok & efficient (the latter the verifier does judge for us however). So it's definitely not just limited toxdp->data. There is also the issue that while access to any non-stack data can be unaligned, access to the stack however cannot. I've discussed a while back with Yonghong about potential solutions. One would be to add a small patch to the BPF backend to enable __builtin_*() helpers to allow for unaligned access which could then be opt-ed in e.g. via -mattr from llc for the case when we know that the compiled program only runs on archs with efficient unaligned access anyway. However, this still potentially breaks with the BPF stack for the case when objects are, for example, larger than size 8 but with a natural alignment smaller than 8 where__builtin_memcpy()would then decide to emit dw-typed load/stores. But for these cases could then be annotated via__aligned(8)on stack. So this is basically what we do right now as a generic workaround in Cilium [0], meaning, our own memcpy/memset with optimal number of instructions and__aligned(8)where needed; most of the time this__aligned(8)is not needed, so it's really just a few places, and we also have a cocci scripts to catch these during development if needed. Anyway, real thing would be to allow the BPF stack for unaligned access as well and then BPF backend could nicely solve this in a native way w/o any workarounds, but that is tbd.Quoted 7 lines
Quoted 4 lines
Thanks,
Daniel[0] https://github.com/cilium/cilium/blob/master/bpf/include/bpf/builtins.h
Daniel,
do you mind adding such memcpy to libbpf ?
Quoted 14 lines
We could do that, yeah. Is there a way from BPF C code when compiling with clang to get to the actual underlying architecture (x86-64, arm64, ppc, etc) when compiling with
-target bpfso that we can always fall back to __builtin_*() for those where verifier would bail out on unaligned access? Keep in mind the__bpf_memcpy()and__bpf_memzero()from [0] are fully compile time resolved and I did the implementation for sizes of 1,2,4,..., 96 where the latter is in two' increments, so no odd buffer sizes as we don't need them in our code. If someone does hit such an odd case, then I'm currently throwing a compilation error via__throw_build_bug(). Latter is a nice way to be able to guarantee that a switch/case or if condition is never hit during compilation time. It resolves to__builtin_trap()which is not implemented in the BPF backend and therefore yells to the developer when built into the code (this has a nice property which wouldn't work withBUILD_BUG_ON()for example). Anyway, what I'm saying is that either we'd need the full thing with all sizes or document that unsupported size would be hit when__builtin_trap()assertion is seen.
I think it would be fine to simply document it.
Most structures have at least one 'int' and don't have 'packed', so they are multiple of 4 typically. Multiple of 2 limitation should be acceptable for most cases.