net: filter: add insn for loading internal transport header offset

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Signed-off-by Chema Gonzalez <[email protected]>

---
 include/linux/filter.h      |  1 +
 include/uapi/linux/filter.h |  3 ++-
 net/core/filter.c           | 17 +++++++++++++++++
 tools/net/bpf_exp.l         |  1 +
 tools/net/bpf_exp.y         | 11 ++++++++++-
 5 files changed, 31 insertions(+), 2 deletions(-)

include/linux/filter.h +1 -0

index 759abf7..b76ae2b 100644
@@ -224,6 +224,7 @@ enum {
        BPF_S_ANC_VLAN_TAG_PRESENT,
        BPF_S_ANC_PAY_OFFSET,
        BPF_S_ANC_RANDOM,
+       BPF_S_ANC_TRA_OFFSET,
 };
 
 #endif /* __LINUX_FILTER_H__ */

include/uapi/linux/filter.h +2 -1

index 253b4d4..9f1b8f1 100644
@@ -131,7 +131,8 @@ struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
 #define SKF_AD_VLAN_TAG_PRESENT 48
 #define SKF_AD_PAY_OFFSET      52
 #define SKF_AD_RANDOM  56
-#define SKF_AD_MAX     60
+#define SKF_AD_TRA_OFFSET      60
+#define SKF_AD_MAX     64
 #define SKF_NET_OFF   (-0x100000)
 #define SKF_LL_OFF    (-0x200000)
 

net/core/filter.c +0 -0

index 7c4db3d..e31846a 100644

net/core/filter.c +13 -0

+
+       if (!skb_flow_dissect(skb, &keys))
+               return 0;
+
+       return keys.thoff;
+}
+
 static u64 __skb_get_nlattr(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
 {
        struct sk_buff *skb = (struct sk_buff *)(long) ctx;

@@ -788,6 +799,7 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
        case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
        case SKF_AD_OFF + SKF_AD_CPU:
        case SKF_AD_OFF + SKF_AD_RANDOM:
+       case SKF_AD_OFF + SKF_AD_TRA_OFFSET:
                /* arg1 = ctx */
                insn->code = BPF_ALU64 | BPF_MOV | BPF_X;
                insn->a_reg = ARG1_REG;

@@ -824,6 +836,9 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
                case SKF_AD_OFF + SKF_AD_RANDOM:
                        insn->imm = __get_random_u32 - __bpf_call_base;
                        break;
+               case SKF_AD_OFF + SKF_AD_TRA_OFFSET:
+                       insn->imm = __skb_get_tra_offset - __bpf_call_base;
+                       break;
                }
                break;
 

@@ -1375,6 +1390,7 @@ int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
                        ANCILLARY(VLAN_TAG_PRESENT);
                        ANCILLARY(PAY_OFFSET);
                        ANCILLARY(RANDOM);
+                       ANCILLARY(TRA_OFFSET);
                        }
 
                        /* ancillary operation unknown or unsupported */

@@ -1760,6 +1776,7 @@ void sk_decode_filter(struct sock_filter *filt, struct sock_filter *to)
                [BPF_S_ANC_VLAN_TAG_PRESENT] = BPF_LD|BPF_B|BPF_ABS,
                [BPF_S_ANC_PAY_OFFSET]  = BPF_LD|BPF_B|BPF_ABS,
                [BPF_S_ANC_RANDOM]      = BPF_LD|BPF_B|BPF_ABS,
+               [BPF_S_ANC_TRA_OFFSET]  = BPF_LD|BPF_B|BPF_ABS,
                [BPF_S_LD_W_LEN]        = BPF_LD|BPF_W|BPF_LEN,
                [BPF_S_LD_W_IND]        = BPF_LD|BPF_W|BPF_IND,
                [BPF_S_LD_H_IND]        = BPF_LD|BPF_H|BPF_IND,

tools/net/bpf_exp.l +1 -0

index 833a966..4e72934 100644
@@ -93,6 +93,7 @@ extern void yyerror(const char *str);
 "#"?("vlan_tci") { return K_VLANT; }
 "#"?("vlan_pr")        { return K_VLANP; }
 "#"?("rand")   { return K_RAND; }
+"#"?("toff")   { return K_TOFF; }
 
 ":"            { return ':'; }
 ","            { return ','; }

tools/net/bpf_exp.y +10 -2

index e6306c5..ced6949 100644
@@ -56,7 +56,7 @@ static void bpf_set_jmp_label(char *label, enum jmp_type type);
 %token OP_LDXI
 
 %token K_PKT_LEN K_PROTO K_TYPE K_NLATTR K_NLATTR_NEST K_MARK K_QUEUE K_HATYPE
-%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND
+%token K_RXHASH K_CPU K_IFIDX K_VLANT K_VLANP K_POFF K_RAND K_TOFF
 
 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
 

@@ -167,6 +167,9 @@ ldb
        | OP_LDB K_RAND {
                bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
                                   SKF_AD_OFF + SKF_AD_RANDOM); }
+       | OP_LDB K_TOFF {
+               bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
+                                  SKF_AD_OFF + SKF_AD_TRA_OFFSET); }
        ;
 
 ldh

@@ -218,6 +221,9 @@ ldh
        | OP_LDH K_RAND {
                bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
                                   SKF_AD_OFF + SKF_AD_RANDOM); }
+       | OP_LDH K_TOFF {
+               bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
+                                  SKF_AD_OFF + SKF_AD_TRA_OFFSET); }
        ;
 
 ldi

@@ -274,6 +280,9 @@ ld
        | OP_LD K_RAND {
                bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
                                   SKF_AD_OFF + SKF_AD_RANDOM); }
+       | OP_LD K_TOFF {
+               bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
+                                  SKF_AD_OFF + SKF_AD_TRA_OFFSET); }
        | OP_LD 'M' '[' number ']' {
                bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
        | OP_LD '[' 'x' '+' number ']' {
--

1.9.1.423.g4596e3a

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Signed-off-by Chema Gonzalez <[email protected]>

[ Chema, please also keep me in cc if possible. ]

Quoted 5 lines · Chema Gonzalez

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Signed-off-by Chema Gonzalez <[email protected]>

Looks good to me. For casting pointers as Dave noted recently, please use 'unsigned long'. This needs to be fixed in other places as well.

Other than that, you can add my:

Acked-by Daniel Borkmann <[email protected]>

Quoted 1 line

[ Chema, please also keep me in cc if possible. ]

Quoted 2 lines

Looks good to me. For casting pointers as Dave noted recently, please use 'unsigned long'. This needs to be fixed in other places as well.

Ohh, and please in future include net or net-next into your subject line.

net/core/filter.c static u64 __skb_get_pay_offset(u64 ctx, u64 A, u64 X, u64 r4, u64 r5) · line 607

Quoted 4 lines

net/core/filter.c +4 -0

+static u64 __skb_get_tra_offset(u64 ctx, u64 A, u64 X, u64 r4, u64 r5)
+{
+       struct flow_keys keys;
+       struct sk_buff *skb = (struct sk_buff *)(long) ctx;

I think kernel style recommends to swap above two lines, but that's a nit.

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Signed-off-by Chema Gonzalez <[email protected]>

From: Chema Gonzalez <[email protected]>
Date: Thu, 1 May 2014 11:44:40 -0700

Quoted 4 lines

Patch adds an ANC_TRA_OFFSET insn that loads the internal transport header of a packet ("internal" meaning after decapsulation by the flow dissector).

Quoted 1 line

Signed-off-by Chema Gonzalez <[email protected]>

I'm not so convinced of this change.

What are the use cases?

If the use cases are to simply pull the ports out of the transport header for filter matching or hashing, don't just make a half-step like this.

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

Quoted 6 lines

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

Once you get the L3 proto and noff/toff, you get everything. The rationale of adding toff/noff is that it's very similar to poff, which we already have.

Quoted 3 lines

Once you get the L3 proto and noff/toff, you get everything. The rationale of adding toff/noff is that it's very similar to poff, which we already have.

But you're implementation is calling a function to do all of that work already, just to get only the transport header and then throwing away all of the other useful bits that function is calculating, so you'll end up doing it twice which is wasted work.

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

Quoted 6 lines

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

I'm not sure whether I follow this. The goal is to be able to access the inner-most headers inside BPF, not in userland by calling getsockopt().

From: Chema Gonzalez <[email protected]>
Date: Mon, 5 May 2014 11:42:00 -0700

Quoted 10 lines · David Miller

Quoted 6 lines

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

I'm not sure whether I follow this. The goal is to be able to access the inner-most headers inside BPF, not in userland by calling getsockopt().

You're missing my entire point.

You can use AF_PACKET mmap() rings and in those ring entries all of the flow dissection information can be put in the ring entry headers before the packet contents. Ports, header offsets, everything.

Quoted 14 lines · David Miller

From: Chema Gonzalez <[email protected]>
Date: Mon, 5 May 2014 11:42:00 -0700

Quoted 10 lines · David Miller

Quoted 6 lines

We can probably add an extension to AF_PACKET which provides the flow key at the end of the tpacket3_hdr if a certain socket option is set.

That would provide the transport header as well as a side effect, and be much more powerful and efficient than this particular BPF instruction.

I'm not sure whether I follow this. The goal is to be able to access the inner-most headers inside BPF, not in userland by calling getsockopt().

Quoted 5 lines

You're missing my entire point.

You can use AF_PACKET mmap() rings and in those ring entries all of the flow dissection information can be put in the ring entry headers before the packet contents. Ports, header offsets, everything.

I added a flow_keys variable in the packet runner function (__sk_run_filter()) stack, and modified __skb_get_poff() to try to get the results from there instead of calling the flow dissector every time you call it. That will allow the packet filter to only perform a single call to the flow dissector per packet.

I reworked the toff patch to use the same flow dissector output approach (and share it with the poff load), and added a tproto patch.

Patches coming now.

-Chema

We want multiple calls to __skb_get_poff() in the same filter to only cause one invocation to the flow dissector. In order to reuse the result of the flow dissector invocation (skb_flow_dissect()), we add a flow_keys variable in the eBPF runner stack (__sk_run_filter() function), and pass it as an argument to __skb_get_poff(). __skb_get_poff() inits the variable the very first time it is called, and reuses the result in any further invocation.

We also add handy function to init/check for inited flow_keys.

Signed-off-by Chema Gonzalez <[email protected]>

---
 include/linux/skbuff.h    |  4 +++-
 net/core/filter.c         | 14 ++++++++++++--
 net/core/flow_dissector.c | 28 ++++++++++++++++++++++------
 3 files changed, 37 insertions(+), 9 deletions(-)

include/linux/skbuff.h +3 -1

index 7a9beeb..858d7af 100644
@@ -3065,7 +3065,9 @@ bool skb_partial_csum_set(struct sk_buff *skb, u16 start, u16 off);
 
 int skb_checksum_setup(struct sk_buff *skb, bool recalculate);
 
-u32 __skb_get_poff(const struct sk_buff *skb);
+void __flow_keys_reset(struct flow_keys *flow);
+bool __flow_keys_inited(struct flow_keys *flow);
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *flow);
 
 /**
  * skb_head_is_locked - Determine if the skb->head is locked down

net/core/filter.c +5 -0

index c442a0d..b71948b 100644
@@ -66,6 +66,11 @@
 #define CTX    regs[BPF_REG_CTX]
 #define K      insn->imm
 
+struct sk_run_filter_ctx {
+       struct sk_buff *skb;
+       struct flow_keys *flow;
+};
+
 /* No hurry in this branch
  *
  * Exported for the bpf jit load helper.

@@ -252,12 +257,15 @@ unsigned int __sk_run_filter(void *ctx, const struct sock_filter_int *insn)
        };
        void *ptr;
        int off;

net/core/filter.c +3 -1

        /* Register for user BPF programs need to be reset first. */
        regs[BPF_REG_A] = 0;

@@ -602,7 +610,9 @@ static unsigned int pkt_type_offset(void)
 
 static u64 __skb_get_pay_offset(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 {
-       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx);
+       struct sk_run_filter_ctx *context = (struct sk_run_filter_ctx *)
+                       (unsigned long) ctx;
+       return __skb_get_poff(context->skb, context->flow);
 }
 
 static u64 __skb_get_nlattr(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)

net/core/flow_dissector.c +22 -7

index 107ed12..4d431f0 100644
@@ -270,21 +270,37 @@ u16 __skb_tx_hash(const struct net_device *dev, const struct sk_buff *skb,
 }
 EXPORT_SYMBOL(__skb_tx_hash);
 
+/* __flow_keys_reset() zeroes a flow_keys struct */
+void __flow_keys_reset(struct flow_keys *flow)
+{
+       memset(flow, 0, sizeof(struct flow_keys));
+}
+
+/* __flow_keys_inited() checks whether a flow_keys struct is init */
+bool __flow_keys_inited(struct flow_keys *flow)
+{
+       struct flow_keys zero_flow;
+
+       __flow_keys_reset(&zero_flow);
+       return memcmp(flow, &zero_flow, sizeof(struct flow_keys));
+}
+
 /* __skb_get_poff() returns the offset to the payload as far as it could
  * be dissected. The main user is currently BPF, so that we can dynamically
  * truncate packets without needing to push actual payload to the user
  * space and can analyze headers only, instead.
  */
-u32 __skb_get_poff(const struct sk_buff *skb)
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *flow)
 {
-       struct flow_keys keys;
        u32 poff = 0;
 
-       if (!skb_flow_dissect(skb, &keys))
-               return 0;
+       /* check whether the flow dissector has already been run */
+       if (!__flow_keys_inited(flow))
+               if (!skb_flow_dissect(skb, flow))
+                       return 0;
 
-       poff += keys.thoff;
-       switch (keys.ip_proto) {
+       poff += flow->thoff;
+       switch (flow->ip_proto) {
        case IPPROTO_TCP: {
                const struct tcphdr *tcph;
                struct tcphdr _tcph;
--

1.9.1.423.g4596e3a

I have a feeling that you didn't test this. Even basic "tcpdump port 22" will be broken,

let alone BPF testsuite. It also breaks seccomp, new JIT and tracing filter patches I've posted yesterday.

sk_run_filter() is a generic interpreter that should be suitable for sockets, seccomp, tracing, etc. Adding one use case specific data structure to interpreter is not desirable.

Doing memset(&flow,0...) every invocation is not performance friendly either. Majority of filters will suffer.

You can do the same without touching sk_run_filter(). For example, you can tweak sk_convert_filter() to pass R10(frame pointer) as arg4 to helper functions (__skb_get_pay_offset() and others)
then inside those functions cast 'arg4 - appropriate offset' to struct flow_keys and use it.
BPF was extended from 16 spill/fill only slots to generic stack space exactly for this type of use cases.

Key point: you can add pretty much any feature to classic BPF by tweaking converter from classic to internal without changing interpreter and causing trainwreck for non-socket use cases.

The idea itself I think is quite interesting. I'm only disliking its implementation.

Hi,

Quoted 2 lines · Alexei Starovoitov

I have a feeling that you didn't test this. Even basic "tcpdump port 22" will be broken,

Not sure whether you understood the use of this. I'm not trying to change how to compile tcpdump expressions. The only way to access the new features is using Daniel's bpf_asm code.

I did test the code:

Quoted 3 lines

sk_run_filter() is a generic interpreter that should be suitable for sockets, seccomp, tracing, etc. Adding one use case specific data structure to interpreter is not desirable.

That's an interesting point, which you'd agree does apply to "ld poff" right now. There's a tradeoff here between making the BPF VM as generic as possible, and having to reimplement in BPF VM code functions that already exist in the kernel (the flow dissector itself). I think not having 2 flow dissectors in the kernel (one in C, one in BPF VM code) is a win.

Quoted 2 lines

Doing memset(&flow,0...) every invocation is not performance friendly either. Majority of filters will suffer.

Will fix. In retrospect, I should have just added an flow_keys_is_init field instead of mapping {0, 0, {0}, 0, 0} to "not inited."

Quoted 8 lines

You can do the same without touching sk_run_filter(). For example, you can tweak sk_convert_filter() to pass R10(frame pointer) as arg4 to helper functions (__skb_get_pay_offset() and others)
then inside those functions cast 'arg4 - appropriate offset' to struct flow_keys and use it.
BPF was extended from 16 spill/fill only slots to generic stack space exactly for this type of use cases.

I tried several implementations, including the one you propose:

1. add flow_keys to skb CB (packet_skb_cb)
The problem here is that struct flow_keys (15 bytes) does not fit in AF_PACKET's 48-byte skb CB. I also tried to create a small_flow_keys struct that only contains L3 info (nhoff/proto, which is the minimum output you need from the flow dissector to be able to get the rest without having to rewalk the packet), or maybe L3 and L4 (thoff/ip_proto). The problem is that the packet CB is completely full already. packet_skb_cb is 4 (origlen) + 20 (sockaddr_ll) and MAX_ADDR_LEN=32, so the net/packet/af_packet.c:1822 check is 4+20+32-8 = 48, which is already the size of the sk_buff->CB.

2. add flow_keys using the stack in the 3 BPF filter runners (original, eBPF, JIT)
- (-) there are 6x BPF engines (1x non-JIT and 5x JIT)
- (+) we can just do the non-JIT version, and let JITs implement it
when they want)
- (+) very simple

3. add FLOW, BPF_REG_FLOW, map it to a register, and then pass it as R4. This is what you're proposing, IIIC. I found the implementation way more complicated (in fact I gave up trying to make it not crash ;), but I guess this is my own taste. What really convinced me to extend the context is that, if you think about it, both the skb and the flow_keys are part of the context that the bpf_calls use to run. If we pass flow_keys in R4, and we ever want to add more context parameters to a call, that means using R5. And then what?

Quoted 3 lines

Key point: you can add pretty much any feature to classic BPF by tweaking converter from classic to internal without changing interpreter and causing trainwreck for non-socket use cases.

Again, the patch is not breaking the current functionality. We already provide "ld poff" as a recognition that packet processing is a first class citizen of the BPF VM. If you run a seccomp filter containing a "ld poff" right now, you're probably causing issues anyway.

please try 'modprobe test_bpf'… you'll see most ld_proto, ld_vlan, … tests failing..

Quoted 9 lines

Quoted 3 lines

sk_run_filter() is a generic interpreter that should be suitable for sockets, seccomp, tracing, etc. Adding one use case specific data structure to interpreter is not desirable.

That's an interesting point, which you'd agree does apply to "ld poff" right now. There's a tradeoff here between making the BPF VM as generic as possible, and having to reimplement in BPF VM code functions that already exist in the kernel (the flow dissector itself). I think not having 2 flow dissectors in the kernel (one in C, one in BPF VM code) is a win.

You misunderstood. That's not at all what I said. See the diff below.

Quoted 4 lines

Quoted 2 lines

Doing memset(&flow,0...) every invocation is not performance friendly either. Majority of filters will suffer.

Will fix. In retrospect, I should have just added an flow_keys_is_init field instead of mapping {0, 0, {0}, 0, 0} to "not inited."

Quoted 9 lines

Quoted 8 lines

You can do the same without touching sk_run_filter(). For example, you can tweak sk_convert_filter() to pass R10(frame pointer) as arg4 to helper functions (__skb_get_pay_offset() and others)
then inside those functions cast 'arg4 - appropriate offset' to struct flow_keys and use it.
BPF was extended from 16 spill/fill only slots to generic stack space exactly for this type of use cases.

I tried several implementations, including the one you propose:

nope. see the diff of what I'm proposing.

Quoted 28 lines

1. add flow_keys to skb CB (packet_skb_cb)
The problem here is that struct flow_keys (15 bytes) does not fit in AF_PACKET's 48-byte skb CB. I also tried to create a small_flow_keys struct that only contains L3 info (nhoff/proto, which is the minimum output you need from the flow dissector to be able to get the rest without having to rewalk the packet), or maybe L3 and L4 (thoff/ip_proto). The problem is that the packet CB is completely full already. packet_skb_cb is 4 (origlen) + 20 (sockaddr_ll) and MAX_ADDR_LEN=32, so the net/packet/af_packet.c:1822 check is 4+20+32-8 = 48, which is already the size of the sk_buff->CB.

2. add flow_keys using the stack in the 3 BPF filter runners (original, eBPF, JIT)
- (-) there are 6x BPF engines (1x non-JIT and 5x JIT)
- (+) we can just do the non-JIT version, and let JITs implement it
when they want)
- (+) very simple

3. add FLOW, BPF_REG_FLOW, map it to a register, and then pass it as R4. This is what you're proposing, IIIC. I found the implementation way more complicated (in fact I gave up trying to make it not crash ;), but I guess this is my own taste. What really convinced me to extend the context is that, if you think about it, both the skb and the flow_keys are part of the context that the bpf_calls use to run. If we pass flow_keys in R4, and we ever want to add more context parameters to a call, that means using R5. And then what?

Quoted 7 lines

Quoted 3 lines

Key point: you can add pretty much any feature to classic BPF by tweaking converter from classic to internal without changing interpreter and causing trainwreck for non-socket use cases.

Again, the patch is not breaking the current functionality. We already provide "ld poff" as a recognition that packet processing is a first class citizen of the BPF VM. If you run a seccomp filter containing a "ld poff" right now, you're probably causing issues anyway.

'ld poff' is not first class citizen of interpreter. There is no such eBPF insn. It's a classic BPF instruction. It is converted into a sequence of eBPF insns including bpf_call.

Just to reduce the number of back and forth emails here is the diff of what you want to do that doesn't break things:
(sorry for whitespace mangling)

include/linux/skbuff.h +1 -1

index 7a9beeb1c458..10f580e44a33 100644
@@ -3065,7 +3065,7 @@ bool skb_partial_csum_set(struct sk_buff *skb,
 u16 start, u16 off);
 
 int skb_checksum_setup(struct sk_buff *skb, bool recalculate);
 
-u32 __skb_get_poff(const struct sk_buff *skb);
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *keys);
 
 /**

* skb_head_is_locked - Determine if the skb->head is locked down

net/core/filter.c +10 -1

index 32c5b44c537e..1179f2fb4c95 100644
@@ -602,7 +602,12 @@ static unsigned int pkt_type_offset(void)
 
 static u64 __skb_get_pay_offset(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 {
-       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx);
+       /* top BPF_MEMWORDS * 4 bytes are used to represent classic BPF
+        * mem[0-15] slots, use next sizeof(struct flow_keys) bytes
+        * of stack to share flow_dissect-ed data
+        */
+       struct flow_keys *keys = (void *) r4 - BPF_MEMWORDS * 4 - sizeof(*keys);
+       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx, keys);
 }
 
 static u64 __skb_get_nlattr(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)

@@ -783,6 +788,10 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
                *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG3, BPF_REG_X);
                insn++;
 
+               /* arg4 = FP */
+               *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG4, BPF_REG_FP);
+               insn++;
+
                /* Emit call(ctx, arg2=A, arg3=X) */
                insn->code = BPF_JMP | BPF_CALL;
                switch (fp->k) {

net/core/flow_dissector.c +4 -5

index 107ed12a5323..c8d9f16e4872 100644
@@ -275,16 +275,15 @@ EXPORT_SYMBOL(__skb_tx_hash);
  * truncate packets without needing to push actual payload to the user
  * space and can analyze headers only, instead.
  */
-u32 __skb_get_poff(const struct sk_buff *skb)
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *keys)
 {
-       struct flow_keys keys;
        u32 poff = 0;
 
-       if (!skb_flow_dissect(skb, &keys))
+       if (!skb_flow_dissect(skb, keys))
                return 0;
 
-       poff += keys.thoff;
-       switch (keys.ip_proto) {
+       poff += keys->thoff;
+       switch (keys->ip_proto) {
        case IPPROTO_TCP: {
 

now just use the same 'keys' address in your new get_off calls. First word can be used to indicate whether flow_dissector() was called or not.

Above is tested with and without JIT with BPF testsuite.

We want multiple calls to __skb_get_poff() in the same filter to only cause one invocation to the flow dissector. In order to reuse the result of the flow dissector invocation (skb_flow_dissect()), we add a flow_keys variable in the eBPF runner stack (__sk_run_filter() function), and pass it as an argument to __skb_get_poff(). __skb_get_poff() inits the variable the very first time it is called, and reuses the result in any further invocation.

Tested:

$ cat tools/net/ipv4_tcp_poff2.bpf
ldh [12]
jne #0x800, drop
ldb [23]
jneq #6, drop
ld poff
ld poff
ld poff
ld poff
ld toff
ld toff
ld toff
ld tproto
ld tproto
ld tproto
ret #-1
drop: ret #0
$ ./tools/net/bpf_asm tools/net/ipv4_tcp_poff2.bpf
16,40 0 0 12,21 0 13 2048,48 0 0 23,21 0 11 6,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963260,32 0 0 4294963260,32 0 0 4294963260,32 0 0 4294963264,32 0 0 4294963264,32 0 0 4294963264,6 0 0 4294967295,6 0 0 0,

And then, in a VM, I ran:

$ tcpdump -n -i eth0 -f "16,40 0 0 12,21 0 13 2048,48 0 0 23,21 0 11
6,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,32 0 0
4294963252,32 0 0 4294963260,32 0 0 4294963260,32 0 0 4294963260,32 0
0 4294963264,32 0 0 4294963264,32 0 0 4294963264,6 0 0 4294967295,6 0
0 0,"

This tcpdump is github's tcpdump HEAD with
https://github.com/the-tcpdump-group/libpcap/pull/353.

Adding some labels shows how the flow dissector is only called for the first "ld poff":

...

[   14.400269] --------__sk_run_filter(): setting flow: {0, 481192, -30720, 1013, 8} is inited? 0
[   14.401528] --------__skb_get_poff(): checking flow dissector: {0, 481192, -30720, 1013, 8} is inited? 0
[   14.403088] --------__skb_get_poff(): before calling flow dissector: {0, 481192, -30720, 1013, 8}
[   14.404068] --------__skb_get_poff(): after calling flow dissector: {23374016, -26957632, -174123520, 34, 6}
[   14.405154] --------__skb_get_poff(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.406264] --------__skb_get_poff(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.407412] --------__skb_get_poff(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.408520] --------__skb_get_tra_offset(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.409673] --------__skb_get_tra_offset(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.410845] --------__skb_get_tra_offset(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.412008] --------__skb_get_tra_protocol(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1

[   14.413255] --------__skb_get_tra_protocol(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.414437] --------__skb_get_tra_protocol(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1
[   14.415888] --------__sk_run_filter(): setting flow: {-1, 399522456, -30720, 1736, 8} is inited? 0
[   14.415929] --------__sk_run_filter(): setting flow: {0, 1400960, -30720, 56016, 7} is inited? 0
[   14.415932] --------__skb_get_poff(): checking flow dissector: {0, 1400960, -30720, 56016, 7} is inited? 0
[   14.415932] --------__skb_get_poff(): before calling flow dissector: {0, 1400960, -30720, 56016, 7}
[   14.415950] --------__skb_get_poff(): after calling flow dissector: {23374016, -26957632, -174123520, 34, 6}
[   14.415952] --------__skb_get_poff(): checking flow dissector: {23374016, -26957632, -174123520, 34, 6} is inited? 1

$ modprobe test_bpf
[    9.809183] test_bpf: #0 TAX 23 39 39 PASS
[    9.820202] test_bpf: #1 TXA 10 10 11 PASS
[    9.824239] test_bpf: #2 ADD_SUB_MUL_K 13 PASS
[    9.826369] test_bpf: #3 DIV_KX 45 PASS
[    9.831530] test_bpf: #4 AND_OR_LSH_K 15 14 PASS
[    9.835290] test_bpf: #5 LD_IND 11 11 11 PASS
[    9.839567] test_bpf: #6 LD_ABS 10 10 10 PASS
[    9.843381] test_bpf: #7 LD_ABS_LL 18 39 PASS
[    9.849925] test_bpf: #8 LD_IND_LL 18 18 18 PASS
[    9.856191] test_bpf: #9 LD_ABS_NET 15 18 PASS
[    9.860391] test_bpf: #10 LD_IND_NET 15 18 17 PASS
[    9.866310] test_bpf: #11 LD_PKTTYPE 44 47 PASS
[    9.876354] test_bpf: #12 LD_MARK 7 7 PASS
[    9.878626] test_bpf: #13 LD_RXHASH 8 8 PASS
[    9.880990] test_bpf: #14 LD_QUEUE 7 7 PASS
[    9.883251] test_bpf: #15 LD_PROTOCOL 20 20 PASS
[    9.888086] test_bpf: #16 LD_VLAN_TAG 9 9 PASS
[    9.890708] test_bpf: #17 LD_VLAN_TAG_PRESENT 10 11 PASS
[    9.893785] test_bpf: #18 LD_IFINDEX 11 11 PASS
[    9.896924] test_bpf: #19 LD_HATYPE 13 14 PASS
[    9.900458] test_bpf: #20 LD_CPU 43 43 PASS
[    9.909919] test_bpf: #21 LD_NLATTR 18 23 PASS
[    9.914841] test_bpf: #22 LD_NLATTR_NEST 110 155 PASS
[    9.942252] test_bpf: #23 LD_PAYLOAD_OFF 134 93 PASS
[    9.965865] test_bpf: #24 LD_ANC_XOR 9 9 PASS
[    9.968571] test_bpf: #25 SPILL_FILL 26 26 26 PASS
[    9.977303] test_bpf: #26 JEQ 10 10 11 PASS
[    9.981278] test_bpf: #27 JGT 10 11 11 PASS
[    9.985383] test_bpf: #28 JGE 13 18 19 PASS
[    9.991189] test_bpf: #29 JSET 24 29 67 PASS
[   10.004116] test_bpf: #30 tcpdump port 22 9 32 37 PASS
[   10.012935] test_bpf: #31 tcpdump complex 9 28 79 PASS
[   10.025630] test_bpf: #32 RET_A 7 7 PASS
[   10.027799] test_bpf: #33 INT: ADD trivial 12 PASS
[   10.029827] test_bpf: #34 INT: MUL_X 10 PASS
[   10.031588] test_bpf: #35 INT: MUL_X2 12 PASS
[   10.033561] test_bpf: #36 INT: MUL32_X 12 PASS
[   10.035462] test_bpf: #37 INT: ADD 64-bit 583 PASS
[   10.094546] test_bpf: #38 INT: ADD 32-bit 525 PASS
[   10.147935] test_bpf: #39 INT: SUB 386 PASS
[   10.187293] test_bpf: #40 INT: XOR 142 PASS
[   10.202252] test_bpf: #41 INT: MUL 171 PASS
[   10.220148] test_bpf: #42 INT: ALU MIX 33 PASS
[   10.224212] test_bpf: #43 INT: DIV + ABS 24 26 PASS
[   10.230178] test_bpf: #44 INT: DIV by zero 10 7 PASS
[   10.232817] test_bpf: #45 check: missing ret PASS
[   10.233604] test_bpf: #46 check: div_k_0 PASS
[   10.234273] test_bpf: #47 check: unknown insn PASS
[   10.235008] test_bpf: #48 check: out of range spill/fill PASS

Signed-off-by Chema Gonzalez <[email protected]>

---
 include/linux/skbuff.h    |  3 ++-
 net/core/filter.c         | 26 +++++++++++++++++++++++++-
 net/core/flow_dissector.c | 16 ++++++++++------
 3 files changed, 37 insertions(+), 8 deletions(-)

include/linux/skbuff.h +2 -1

index 7a9beeb..5f42eee 100644
@@ -3065,7 +3065,8 @@ bool skb_partial_csum_set(struct sk_buff *skb, u16 start, u16 off);
 
 int skb_checksum_setup(struct sk_buff *skb, bool recalculate);
 
-u32 __skb_get_poff(const struct sk_buff *skb);
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *flow,
+               bool *flow_initted);
 
 /**
  * skb_head_is_locked - Determine if the skb->head is locked down

net/core/filter.c +7 -0

index 32c5b44..fc20588 100644
@@ -66,6 +66,11 @@
 #define CTX    regs[BPF_REG_CTX]
 #define K      insn->imm
 
+struct sk_run_filter_ctx {
+       struct flow_keys flow;
+       bool flow_initted;
+};
+
 /* No hurry in this branch
  *
  * Exported for the bpf jit load helper.

@@ -252,6 +257,7 @@ unsigned int __sk_run_filter(void *ctx, const struct sock_filter_int *insn)
        };
        void *ptr;
        int off;
+       struct sk_run_filter_ctx *context;
 
 #define CONT    ({ insn++; goto select_insn; })
 #define CONT_JMP ({ insn++; goto select_insn; })

@@ -259,6 +265,17 @@ unsigned int __sk_run_filter(void *ctx, const struct sock_filter_int *insn)
        FP = (u64) (unsigned long) &stack[ARRAY_SIZE(stack)];
        ARG1 = (u64) (unsigned long) ctx;
 
+       /* init context.

net/core/filter.c +8 -1

        /* Register for user BPF programs need to be reset first. */
        regs[BPF_REG_A] = 0;
        regs[BPF_REG_X] = 0;

@@ -602,7 +619,10 @@ static unsigned int pkt_type_offset(void)
 
 static u64 __skb_get_pay_offset(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 {
-       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx);
+       struct sk_run_filter_ctx *context = (void *) r4 - BPF_MEMWORDS * 4 -
+                       sizeof(*context);
+       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx,
+                       &context->flow, &context->flow_initted);
 }
 
 static u64 __skb_get_nlattr(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)

@@ -783,6 +803,10 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
                *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG3, BPF_REG_X);
                insn++;
 
+               /* arg4 = FP */
+               *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG4, BPF_REG_FP);
+               insn++;
+
                /* Emit call(ctx, arg2=A, arg3=X) */
                insn->code = BPF_JMP | BPF_CALL;
                switch (fp->k) {

net/core/flow_dissector.c +10 -7

index 107ed12..cefe1d2 100644
@@ -275,16 +275,20 @@ EXPORT_SYMBOL(__skb_tx_hash);
  * truncate packets without needing to push actual payload to the user
  * space and can analyze headers only, instead.
  */
-u32 __skb_get_poff(const struct sk_buff *skb)
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *flow,
+               bool *flow_initted)
 {
-       struct flow_keys keys;
        u32 poff = 0;
 
-       if (!skb_flow_dissect(skb, &keys))
-               return 0;
+       /* check whether the flow dissector has already been run */
+       if (!*flow_initted) {
+               if (!skb_flow_dissect(skb, flow))
+                       return 0;
+               *flow_initted = true;
+       }
 
-       poff += keys.thoff;
-       switch (keys.ip_proto) {
+       poff += flow->thoff;
+       switch (flow->ip_proto) {
        case IPPROTO_TCP: {
                const struct tcphdr *tcph;
                struct tcphdr _tcph;
--

1.9.1.423.g4596e3a

this is way too long for commit log. These details can go after '---' line.

net/core/filter.c unsigned int __sk_run_filter(void *ctx, const struct sock_filter_int *insn) · line 278

Quoted 5 lines

net/core/filter.c +5 -0

+        * such field has been inited)
+        */
+       context = (void *)FP - BPF_MEMWORDS * 4 - sizeof(*context);
+       context->flow_initted = false;
+

Neither this code nor comment belong in interpreter which is striving to be generic. Both have a meaning only for your new instructions in socket filters. They do not apply to seccomp and to tracing. Calling it 'struct sk_run_filter_ctx' is equally misleading. 'struct flow_keys' has nothing to do with seccomp and even with normal tcpdump filters.

We've spent so much time to generalize it and now you want to take it back into socket specific territory. As I said in the previous email it's totally not ok to customize eBPF just for one use case especially when you're not sharing final usage scenario.

Any uapi change must be strongly justified.

Other than design issue there is technical problem too.
You're not updating eBPF JIT and context->flow_initted will have junk, so ld_poff will be returning junk too.
JITs and interpreter must match. That was always the case even in old days of classic BPF. Interpreter initialized A and X to zero, JITs had to do the same. If you add stuff like this to interpreter, JITs would have to follow. Fast forward few years and this is not scalable. You have several JITs around and adding custom stuff to interpreter may not even be possible to do in JITs.

Therefore I'm strongly against adding custom C code to interpreter. It's an interpreter of eBPF instructions. Nothing else.
At the same time adding new eBPF instructions would be completely fine. Like right now we don't have < and <= conditional jumps, which adds unnecessary complexity to tracing filters. So we may still expand interpreter and JITs in the future.

Going back to your use case… assuming that you share how user space will use new anc loads… you can do equivalent initialization of 'flow_initted' by emitting extra eBPF insn while converting classic to internal. Don't do it unconditionally though. tcpdump filters should not suffer. You can scan program for presence of ld_poff, ld_toff, ld_tproto and if they're present, emit single eBPF 'st [fp - off], 0' ST_MEM instruction as a first instruction of converted filter. All eBPF JITs will compile it to native automatically. You'll have good performance and all existing filters will not regress.

Quoted 61 lines

        /* Register for user BPF programs need to be reset first. */
        regs[BPF_REG_A] = 0;
        regs[BPF_REG_X] = 0;

net/core/filter.c +8 -1

@@ -602,7 +619,10 @@ static unsigned int pkt_type_offset(void)
 
 static u64 __skb_get_pay_offset(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 {
-       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx);
+       struct sk_run_filter_ctx *context = (void *) r4 - BPF_MEMWORDS * 4 -
+                       sizeof(*context);
+       return __skb_get_poff((struct sk_buff *)(unsigned long) ctx,
+                       &context->flow, &context->flow_initted);
 }
 
 static u64 __skb_get_nlattr(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)

@@ -783,6 +803,10 @@ static bool convert_bpf_extensions(struct sock_filter *fp,
                *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG3, BPF_REG_X);
                insn++;
 
+               /* arg4 = FP */
+               *insn = BPF_ALU64_REG(BPF_MOV, BPF_REG_ARG4, BPF_REG_FP);
+               insn++;
+
                /* Emit call(ctx, arg2=A, arg3=X) */
                insn->code = BPF_JMP | BPF_CALL;
                switch (fp->k) {

net/core/flow_dissector.c +10 -7

index 107ed12..cefe1d2 100644
@@ -275,16 +275,20 @@ EXPORT_SYMBOL(__skb_tx_hash);
  * truncate packets without needing to push actual payload to the user
  * space and can analyze headers only, instead.
  */
-u32 __skb_get_poff(const struct sk_buff *skb)
+u32 __skb_get_poff(const struct sk_buff *skb, struct flow_keys *flow,
+               bool *flow_initted)
 {
-       struct flow_keys keys;
        u32 poff = 0;
 
-       if (!skb_flow_dissect(skb, &keys))
-               return 0;
+       /* check whether the flow dissector has already been run */
+       if (!*flow_initted) {
+               if (!skb_flow_dissect(skb, flow))
+                       return 0;
+               *flow_initted = true;
+       }
 
-       poff += keys.thoff;
-       switch (keys.ip_proto) {
+       poff += flow->thoff;
+       switch (flow->ip_proto) {
        case IPPROTO_TCP: {
                const struct tcphdr *tcph;
                struct tcphdr _tcph;
--

1.9.1.423.g4596e3a

On Fri, May 16, 2014 at 3:00 PM, Alexei Starovoitov <[email protected]> wrote:

Quoted 9 lines

Other than design issue there is technical problem too.
You're not updating eBPF JIT and context->flow_initted will have junk, so ld_poff will be returning junk too.
JITs and interpreter must match. That was always the case even in old days of classic BPF. Interpreter initialized A and X to zero, JITs had to do the same. If you add stuff like this to interpreter, JITs would have to follow. Fast forward few years and this is not scalable. You have several JITs around and adding custom stuff to interpreter may not even be possible to do in JITs.

This is a fair point. In fact my patch is breaking "ld poff."

I think the previous mechanism where a new insn added to BPF would cause the BPF JIT engine to refuse to run was a more scalable: New stuff always went in the non-jitted runner, and people interested in the jitted version will port when they needed it. We definitely not want to require people adding new features to provide 6 versions of the code.

This patch makes __skb_get_pay_offset() (the function called by the eBPF call generated from "ld #poff") store the output of the flow dissector (a flow_keys structure) in the eBPF stack. This way, multiple invocations of this eBPF call in the same BPF filter will only require one single call to the flow dissector.

Note that other eBPF calls that use the flow dissector can use the same approach, and share the results, so at the end there is only one single call to the flow dissector per packet.

Tested:

$ cat tools/net/ipv4_tcp_poff2.bpf
ldh [12]
jne #0x800, drop
ldb [23]
jneq #6, drop
ld poff
ld poff
ld poff
ld poff
ret #-1
drop: ret #0
$ ./tools/net/bpf_asm tools/net/ipv4_tcp_poff2.bpf
10,40 0 0 12,21 0 7 2048,48 0 0 23,21 0 5 6,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,6 0 0 4294967295,6 0 0 0,

And then, in a VM, we ran:

$ tcpdump -n -i eth0 -f "10,40 0 0 12,21 0 7 2048,48 0 0 23,21 0 5 6,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,32 0 0 4294963252,6 0 0 4294967295,6 0 0 0,"

This tcpdump is github's tcpdump HEAD with pull request #353, which allows using raw filters in tcpdump.

Debugging the kernel, we can see that there only the first "ld poff" call does invoke the flow dissector. The other calls reuse the value in the eBPF stack.

Also tested the test_bpf module.

Signed-off-by Chema Gonzalez <[email protected]>

I actually liked [1] most ... ;)

Just an idea ...

Have you taken into account the following: since thoff is u16 and ip_proto is u8 and you clearly seem to want to have the value of these two in your patch set (or even plus the poff value), why not squashing all these into

one extension e.g. SKF_AD_DISSECT where you call the external skb_flow_dissect()
helper or similar on?

I could imagine that either these offsets are squashed into the return or stored if you really need them from the struct flow_keys into M[] itself. So you would end up with one e.g. 'ld #keys' call that e.g. fills out/overwrites
your M[] with the dissected metadata. Then, you'd only have a reason to call that once and do further processing based on these information. Whether you also need poff could e.g. be determined if the user does e.g. 'ldx #1' or so to indicate to the function it eventually calls, that it would further do the dissect and also give you poff into fixed defined M[] slots back.

Thus if someone really only cares about headers, a use case like 'ld #poff + ret a' is sufficient, but if you need much more and don't want to do this in BPF like in your case, you go with 'ld #keys' and process your BPF program further via M[].

Thanks,

Daniel

[1] http://patchwork.ozlabs.org/patch/344271/

Quoted 1 line · Daniel Borkmann

I actually liked [1] most ... ;)

Quoted 4 lines

one extension e.g. SKF_AD_DISSECT where you call the external skb_flow_dissect()
helper or similar on?

Quoted 9 lines

I could imagine that either these offsets are squashed into the return or stored if you really need them from the struct flow_keys into M[] itself. So you would end up with one e.g. 'ld #keys' call that e.g. fills out/overwrites
your M[] with the dissected metadata. Then, you'd only have a reason to call that once and do further processing based on these information. Whether you also need poff could e.g. be determined if the user does e.g. 'ldx #1' or so to indicate to the function it eventually calls, that it would further do the dissect and also give you poff into fixed defined M[] slots back.

IIUC, you're suggesting to have the classic BPF user writes "ld #keys" to load flow_keys in the stack and then *explicitly* adds "ld mem[<offset>]" to access the field she's interested on. Note that if the "ld mem[]" is implicit, then the user must use "ld #thoff" to let the compiler know she wants "ld #keys" and then "ld mem[<thoff_offset>]" (and not "ld mem[<other_offset>]"), which is equivalent to what we're doing right now*.

The only advantage I can see is that we're only adding one new ancillary load, which is more elegant. I can see some issues with this approach:

- usability. The user has to actually know what's the right offset of the thoff, which is cumbersome and may change with kernels. We'd be effectively exporting the flow_keys struct layout to the users.

- have to take care that the classic BPF filter does not muck with mem[] between the "ld #keys" and all of the the "ld* mem[]" that access to it. Note that we're currently storing the flow_keys struct in the stack outside of the mem[] words, so this is not a problem here. (It is only accessible using ebpf insns.)

*Now, if your comment is ebpf-only, that could be ok. That would mean:

- a. the user writes "ld #thoff"
- b. the BPF->eBPF compiler generates one common BPF_CALL (__skb_get_flow_dissect) plus a "ebpf_ldx stack[right_offset]". This would not include payload_offset (which needs to run its own function to get the poff from flow_keys).

Quoted 5 lines · Chema Gonzalez

Quoted 2 lines · Daniel Borkmann

I actually liked [1] most ... ;)

...

Quoted 19 lines

Quoted 4 lines

one extension e.g. SKF_AD_DISSECT where you call the external skb_flow_dissect()
helper or similar on?

Quoted 13 lines

I could imagine that either these offsets are squashed into the return or stored if you really need them from the struct flow_keys into M[] itself. So
you would end up with one e.g. 'ld #keys' call that e.g. fills out/overwrites
your M[] with the dissected metadata. Then, you'd only have a reason to call
that once and do further processing based on these information. Whether you
also need poff could e.g. be determined if the user does e.g. 'ldx #1' or so
to indicate to the function it eventually calls, that it would further do the dissect and also give you poff into fixed defined M[] slots back.

Quoted 7 lines

IIUC, you're suggesting to have the classic BPF user writes "ld #keys" to load flow_keys in the stack and then *explicitly* adds "ld mem[<offset>]" to access the field she's interested on. Note that if the "ld mem[]" is implicit, then the user must use "ld #thoff" to let the compiler know she wants "ld #keys" and then "ld mem[<thoff_offset>]" (and not "ld mem[<other_offset>]"), which is equivalent to what we're doing right now*.

I think there are many ways to design that, but for something possibly generic, what I mean is something like this:

We would a-priori know per API documentation what slots in M[] are filled with which information, just for example:

M[0] <-- nhoff [network header off]
M[1] <-- nproto [network header proto]
M[2] <-- thoff [transport header off]
M[3] <-- tproto [transport header proto]
M[4] <-- poff [payload off]

Now a user could load the following pseudo bpf_asm style program:

ld #5     <-- indicates to fill the first 5 slots of M[], so M[0] to M[4]
ld #keys  <-- triggers the extension to fill the M[] slots
ld M[0]   <-- loads nhoff from M[0] into accu

<do sth with it>
ld M[3] <-- loads tproto into accu, etc
…

A program like:

ld #2
ld #keys
...

Would then on the other hand only fill the first two slots of M[] as the user does not need all information from the kernel's flow dissector and thus also does not fully need to dissect the skb.

This also permits in future to add new fields by enabling them with ld #6 etc, for example.

I think this would fit much more into the design of BPF (although I don't strictly like referring to the kernel's flow dissector and thus bypassing BPF's actual purpose; but I understand that it can get quite complicated with tunnels, etc).

But this idea would allow you to only add 1 new extension and to have it return dynamically a part or all information you would need in your program, and thus solves the issue of calling the skb flow dissector multiple times just because we have ld #thoff, ld #nhoff, etc, we can avoid making such a stack_layout + filter_prologue hack and thus design it more cleanly into the BPF architecture.

Quoted 7 lines

The only advantage I can see is that we're only adding one new ancillary load, which is more elegant. I can see some issues with this approach:

- usability. The user has to actually know what's the right offset of the thoff, which is cumbersome and may change with kernels. We'd be effectively exporting the flow_keys struct layout to the users.

See above.

Quoted 5 lines

- have to take care that the classic BPF filter does not muck with mem[] between the "ld #keys" and all of the the "ld* mem[]" that access to it. Note that we're currently storing the flow_keys struct in the stack outside of the mem[] words, so this is not a problem here. (It is only accessible using ebpf insns.)

Since it is part of the API/ABI, and a new instruction, it is then known that ld #keys would fill particular slots of M[] to the user. That however, must be carefully designed, so that in future one doesn't need to add ld #keys2. The part of not mucking with M[] fields is then part of the user's task actually, just the same way as a user shouldn't store something to A resp. X while an ld resp. ldx knowingly would overwrite that value stored previously. I don't think it would be any different than that.

Quoted 7 lines

*Now, if your comment is ebpf-only, that could be ok. That would mean:

- a. the user writes "ld #thoff"
- b. the BPF->eBPF compiler generates one common BPF_CALL (__skb_get_flow_dissect) plus a "ebpf_ldx stack[right_offset]". This would not include payload_offset (which needs to run its own function to get the poff from flow_keys).

Since we're not using eBPF in user space right now, the comment is not about eBPF. I think if you would use eBPF from user space, you don't need to add such extensions anymore, but could just write yourself a minimal flow dissector in 'restricted' C to solve that problem.

extending cc-list, since I think this thread is related to bpf split thread.

Quoted 49 lines · Daniel Borkmann

Quoted 5 lines · Chema Gonzalez

Quoted 2 lines · Daniel Borkmann

I actually liked [1] most ... ;)

...

Quoted 19 lines

Quoted 4 lines

one extension e.g. SKF_AD_DISSECT where you call the external skb_flow_dissect()
helper or similar on?

Quoted 13 lines

I could imagine that either these offsets are squashed into the return or stored if you really need them from the struct flow_keys into M[] itself. So
you would end up with one e.g. 'ld #keys' call that e.g. fills out/overwrites
your M[] with the dissected metadata. Then, you'd only have a reason to call
that once and do further processing based on these information. Whether you
also need poff could e.g. be determined if the user does e.g. 'ldx #1' or so
to indicate to the function it eventually calls, that it would further do the dissect and also give you poff into fixed defined M[] slots back.

Quoted 7 lines

IIUC, you're suggesting to have the classic BPF user writes "ld #keys" to load flow_keys in the stack and then *explicitly* adds "ld mem[<offset>]" to access the field she's interested on. Note that if the "ld mem[]" is implicit, then the user must use "ld #thoff" to let the compiler know she wants "ld #keys" and then "ld mem[<thoff_offset>]" (and not "ld mem[<other_offset>]"), which is equivalent to what we're doing right now*.

I think there are many ways to design that, but for something possibly generic, what I mean is something like this:

We would a-priori know per API documentation what slots in M[] are filled with which information, just for example:

M[0] <-- nhoff [network header off]
M[1] <-- nproto [network header proto]
M[2] <-- thoff [transport header off]
M[3] <-- tproto [transport header proto]
M[4] <-- poff [payload off]

Quoted 8 lines

Now a user could load the following pseudo bpf_asm style program:

ld #5     <-- indicates to fill the first 5 slots of M[], so M[0] to M[4]
ld #keys  <-- triggers the extension to fill the M[] slots
ld M[0]   <-- loads nhoff from M[0] into accu

<do sth with it>
ld M[3] <-- loads tproto into accu, etc
…

imo there are pros and cons in Daniel's and Chema's proposals for classic BPF extensions.
I like Chema's a bit more, since his proposal doesn't require to change classic BPF verifier and that's always a delicate area (seccomp also allows to use M[] slots).

Both still look like a stop gap until next classic extension appears on horizon.

I think explicit eBPF program solves this particular task cleaner and it doesn't require changing eBPF.

Quoted 64 lines

A program like:

ld #2
ld #keys
...

Would then on the other hand only fill the first two slots of M[] as the user does not need all information from the kernel's flow dissector and thus also does not fully need to dissect the skb.

This also permits in future to add new fields by enabling them with ld #6 etc, for example.

I think this would fit much more into the design of BPF (although I don't strictly like referring to the kernel's flow dissector and thus bypassing BPF's actual purpose; but I understand that it can get quite complicated with tunnels, etc).

But this idea would allow you to only add 1 new extension and to have it return dynamically a part or all information you would need in your program, and thus solves the issue of calling the skb flow dissector multiple times just because we have ld #thoff, ld #nhoff, etc, we can avoid making such a stack_layout + filter_prologue hack and thus design it more cleanly into the BPF architecture.

Quoted 7 lines

The only advantage I can see is that we're only adding one new ancillary load, which is more elegant. I can see some issues with this approach:

- usability. The user has to actually know what's the right offset of the thoff, which is cumbersome and may change with kernels. We'd be effectively exporting the flow_keys struct layout to the users.

See above.

Quoted 5 lines

- have to take care that the classic BPF filter does not muck with mem[] between the "ld #keys" and all of the the "ld* mem[]" that access to it. Note that we're currently storing the flow_keys struct in the stack outside of the mem[] words, so this is not a problem here. (It is only accessible using ebpf insns.)

Since it is part of the API/ABI, and a new instruction, it is then known that ld #keys would fill particular slots of M[] to the user. That however, must be carefully designed, so that in future one doesn't need to add ld #keys2. The part of not mucking with M[] fields is then part of the user's task actually, just the same way as a user shouldn't store something to A resp. X while an ld resp. ldx knowingly would overwrite that value stored previously. I don't think it would be any different than that.

Quoted 7 lines

*Now, if your comment is ebpf-only, that could be ok. That would mean:

- a. the user writes "ld #thoff"
- b. the BPF->eBPF compiler generates one common BPF_CALL (__skb_get_flow_dissect) plus a "ebpf_ldx stack[right_offset]". This would not include payload_offset (which needs to run its own function to get the poff from flow_keys).

Quoted 4 lines

Since we're not using eBPF in user space right now, the comment is not about eBPF. I think if you would use eBPF from user space, you don't need to add such extensions anymore, but could just write yourself a minimal flow dissector in 'restricted' C to solve that problem.

Exactly.
I think exposing eBPF to user space is not a matter of 'if' but 'when'.

I'm not sure how pressing it is now to add another extension to classic, when the goal of this patch set fits into eBPF model just fine. yes, eBPF verifier is not in tree yet and it will obviously take longer to review than Chema's or Daniel's set.

When eBPF is exposed to user space the inner header access can be done in two ways without changing eBPF instruction set or eBPF verifier.

eBPF approach #1:
-- code packet parser in restricted C
Pros:
skb_flow_dissect() stays hidden in kernel.
No additional uapi headache which exist if we start reusing in-kernel skb_flow_dissect() either via classic or eBPF.
Such eBPF program will be just as fast as in-kernel skb_flow_dissect() (I provided performance numbers before)
Cons:
in-kernel skb_flow_dissect() is not reused, but mostly copy-pasted to userspace.

eBPF approach #2:
-- reuse in-kernel skb_flow_dissect() via bpf_call insn from eBPF program Pros:
eBPF program becomes much shorter and can be done in asm like:
bpf_mov r2, fp
bpf_sub r2, 64
bpf_call bpf_skb_flow_dissect // call in-kernel helper function from eBPF program
bpf_ldx r1, [fp - 64] // access flow_keys data
bpf_ldx r2, [fp - 60]

Cons:
bpf_skb_flow_dissect() (wrapper on top of skb_flow_dissect()) becomes uapi visible helper function

imo both eBPF approaches are cleaner than extending classic.

Quoted 6 lines · Alexei Starovoitov

imo there are pros and cons in Daniel's and Chema's proposals for classic BPF extensions.
I like Chema's a bit more, since his proposal doesn't require to change classic BPF verifier and that's always a delicate area (seccomp also allows to use M[] slots).

What bothers me is that you have to *special case* this extension all over the BPF converter and stack, even you need to introduce a prologue just to walk the whole filter program and to check if the extension is present; next to that instead of one extension you need to add a couple of them to uapi. I understand Chema's proposal

or his need to easily access these data but that's why I proposed the above if he wants to go for that. Btw, seccomp doesn't allow for loading BPF extensions, you said so yourself Alexei.

From user api point of view, your approach is cleaner than Chema's,

Quoted 40 lines

I think exposing eBPF to user space is not a matter of 'if' but 'when'.

I'm not sure how pressing it is now to add another extension to classic, when the goal of this patch set fits into eBPF model just fine. yes, eBPF verifier is not in tree yet and it will obviously take longer to review than Chema's or Daniel's set.

When eBPF is exposed to user space the inner header access can be done in two ways without changing eBPF instruction set or eBPF verifier.

eBPF approach #1:
-- code packet parser in restricted C
Pros:
skb_flow_dissect() stays hidden in kernel.
No additional uapi headache which exist if we start reusing in-kernel skb_flow_dissect() either via classic or eBPF. Such eBPF program will be just as fast as in-kernel skb_flow_dissect() (I provided performance numbers before)
Cons:
in-kernel skb_flow_dissect() is not reused, but mostly copy-pasted to userspace.

eBPF approach #2:
-- reuse in-kernel skb_flow_dissect() via bpf_call insn from eBPF program Pros:
eBPF program becomes much shorter and can be done in asm like:
bpf_mov r2, fp
bpf_sub r2, 64
bpf_call bpf_skb_flow_dissect // call in-kernel helper function from eBPF program
bpf_ldx r1, [fp - 64] // access flow_keys data
bpf_ldx r2, [fp - 60]

Cons:
bpf_skb_flow_dissect() (wrapper on top of skb_flow_dissect()) becomes uapi visible helper function

imo both eBPF approaches are cleaner than extending classic.

Quoted 9 lines · Daniel Borkmann

Quoted 6 lines · Alexei Starovoitov

imo there are pros and cons in Daniel's and Chema's proposals for classic BPF extensions.
I like Chema's a bit more, since his proposal doesn't require to change classic BPF verifier and that's always a delicate area (seccomp also allows to use M[] slots).

Quoted 5 lines

What bothers me is that you have to *special case* this extension all over the BPF converter and stack, even you need to introduce a prologue just to walk the whole filter program and to check if the extension is present; next to that instead of one extension you need to add a couple of them to uapi. I understand Chema's proposal

Agree. The walking part and multiple anc loads are not clean, but in your approach you'd need to hack sk_chk_filter() to recognize very specific anc load and do even fancier things in check_load_and_stores() to make sure that 'ld #5, ld #keys' is safe from M[] usage point of view.

ld #5     <-- indicates to fill the first 5 slots of M[], so M[0] to M[4]
ld #keys  <-- triggers the extension to fill the M[] slots
ld M[0]   <-- loads nhoff from M[0] into accu

ld M[0] <-- loads nhoff from M[0] into accu
<do sth with it>
ld M[3] <-- loads tproto into accu, etc

Quoted 3 lines

or his need to easily access these data but that's why I proposed the above if he wants to go for that. Btw, seccomp doesn't allow for loading BPF extensions, you said so yourself Alexei.

of course, but seccomp does use ld/st M[] which will overlap with your socket extension and since check_load_and_stores() will be hacked, seccomp verification needs to be considered as well. From user api point of view, your approach is cleaner than Chema's, but from implementation Chema's is much safer and smaller.

Anyway as I said before I'm not excited about either.
I don't think we should be adding classic BPF extensions any more. The long term headache of supporting classic BPF extensions outweighs the short term benefits.

Not having to constantly tweak kernel for such cases was the key goal of eBPF. My two eBPF approaches to solve Chema's need are both cleaner, since nothing special is being done in eBPF core to support this new need. Both instruction set and verifier stay generic and cover tracing and this new socket use at once. I do realize that I'm talking here about future eBPF verifier that is not in tree yet and eBPF is not exposed to user space, but I think we should consider longer term perspective.
If I'm forced to pick between yours or Chema's classic extensions, I would pick Chema's because it's lesser evil :)

Quoted 41 lines

Quoted 40 lines

I think exposing eBPF to user space is not a matter of 'if' but 'when'.

I'm not sure how pressing it is now to add another extension to classic, when the goal of this patch set fits into eBPF model just fine. yes, eBPF verifier is not in tree yet and it will obviously take longer to review than Chema's or Daniel's set.

When eBPF is exposed to user space the inner header access can be done in two ways without changing eBPF instruction set or eBPF verifier.

eBPF approach #1:
-- code packet parser in restricted C
Pros:
skb_flow_dissect() stays hidden in kernel.
No additional uapi headache which exist if we start reusing in-kernel skb_flow_dissect() either via classic or eBPF. Such eBPF program will be just as fast as in-kernel skb_flow_dissect() (I provided performance numbers before)
Cons:
in-kernel skb_flow_dissect() is not reused, but mostly copy-pasted to userspace.

eBPF approach #2:
-- reuse in-kernel skb_flow_dissect() via bpf_call insn from eBPF program Pros:
eBPF program becomes much shorter and can be done in asm like:
bpf_mov r2, fp
bpf_sub r2, 64
bpf_call bpf_skb_flow_dissect // call in-kernel helper function from eBPF program
bpf_ldx r1, [fp - 64] // access flow_keys data
bpf_ldx r2, [fp - 60]

Cons:
bpf_skb_flow_dissect() (wrapper on top of skb_flow_dissect()) becomes uapi visible helper function

imo both eBPF approaches are cleaner than extending classic.

Your approach needs it too. Citing from your pseudo-code:

Quoted 3 lines

ld #5     <-- indicates to fill the first 5 slots of M[], so M[0] to M[4]
ld #keys  <-- triggers the extension to fill the M[] slots
ld M[0]   <-- loads nhoff from M[0] into accu

How does the "ld M[0]" know that the actual flow dissector has already been called? What if the insn just before the "ld #5" was "jmp +2" ? In that case, the "ld #keys" would have never been called.

Quoted 4 lines

Anyway as I said before I'm not excited about either.
I don't think we should be adding classic BPF extensions any more. The long term headache of supporting classic BPF extensions outweighs the short term benefits.

I see a couple of issues with (effectively) freezing classic BPF development while waiting for direct eBPF access to happen. The first one is that the kernel has to accept it. I can see many questions about this, especially security and usability (I'll send an email about the "split BPF out of core later"). Now, the main issue is whether/when the tools will support it. IMO, this is useful iff I can quickly write/reuse filters and run tcpdump filters based on them. I'm trying to get upstream libpcap to accept support for raw (classic) BPF filters, and it's taking a long time. I can imagine how they may be less receptive about supporting a Linux-only eBPF mechanism. Tools do matter.

On 06/03/2014 11:12 PM, Chema Gonzalez wrote:
...

Quoted 10 lines

Your approach needs it too. Citing from your pseudo-code:

Quoted 3 lines

ld #5     <-- indicates to fill the first 5 slots of M[], so M[0] to M[4]
ld #keys  <-- triggers the extension to fill the M[] slots
ld M[0]   <-- loads nhoff from M[0] into accu

How does the "ld M[0]" know that the actual flow dissector has already been called? What if the insn just before the "ld #5" was "jmp +2" ? In that case, the "ld #keys" would have never been called.

But that case would be no different from doing something like ...

[...]
jmp foo
ldi #42
st M[0]
foo:
ld M[0]
[...]

... and would then not pass the checker in check_load_and_stores(), which, as others have already stated, would need to be extended, of course. It's one possible approach.

Quoted 4 lines

Quoted 4 lines

Anyway as I said before I'm not excited about either.
I don't think we should be adding classic BPF extensions any more. The long term headache of supporting classic BPF extensions outweighs the short term benefits.

Quoted 11 lines

I see a couple of issues with (effectively) freezing classic BPF development while waiting for direct eBPF access to happen. The first one is that the kernel has to accept it. I can see many questions about this, especially security and usability (I'll send an email about the "split BPF out of core later"). Now, the main issue is whether/when the tools will support it. IMO, this is useful iff I can quickly write/reuse filters and run tcpdump filters based on them. I'm trying to get upstream libpcap to accept support for raw (classic) BPF filters, and it's taking a long time. I can imagine how they may be less receptive about supporting a Linux-only eBPF mechanism. Tools do matter.

Grepping through libpcap code, which tries to be platform independent, it seems after all the years, the only thing where you can see support for in their code is SKF_AD_PKTTYPE and SKF_AD_PROTOCOL. Perhaps they

just don't care, perhaps they do, who knows, but it looks to me a bit that they are reluctant to these improvements, maybe for one reason that other OSes don't support it.
From the comments in the MOD/XOR patch, the latter seem to be the issue.

That was also one of the reasons that
led me to start writing bpf_asm (net/tools/) for having a small DSL for more easily trying out BPF code while having _full_ control over it.

Maybe someone should start a binary-compatible Linux-only version of libpcap, where tcpdump will transparently make use of these low level improvements eventually. </rant> ;)

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

Anyway as I said before I'm not excited about either.
I don't think we should be adding classic BPF extensions any more. The long term headache of supporting classic BPF extensions outweighs the short term benefits.

Quoted 11 lines

Quoted 11 lines

I see a couple of issues with (effectively) freezing classic BPF development while waiting for direct eBPF access to happen. The first one is that the kernel has to accept it. I can see many questions about this, especially security and usability (I'll send an email about the "split BPF out of core later"). Now, the main issue is whether/when the tools will support it. IMO, this is useful iff I can quickly write/reuse filters and run tcpdump filters based on them. I'm trying to get upstream libpcap to accept support for raw (classic) BPF filters, and it's taking a long time. I can imagine how they may be less receptive about supporting a Linux-only eBPF mechanism. Tools do matter.

This is a high-level decision, more than a technical one. Do we want to freeze classic BPF development in linux, even before we have a complete eBPF replacement, and zero eBPF tool (libpcap) support?

Quoted 3 lines

Grepping through libpcap code, which tries to be platform independent, it seems after all the years, the only thing where you can see support for in their code is SKF_AD_PKTTYPE and SKF_AD_PROTOCOL. Perhaps they

Actually they recently added MOD/XOR support. Woo-hoo!

Quoted 3 lines

just don't care, perhaps they do, who knows, but it looks to me a bit that they are reluctant to these improvements, maybe for one reason that other OSes don't support it.

From the comments in the MOD/XOR patch, the latter seem to be the issue.

Quoted 7 lines

That was also one of the reasons that
led me to start writing bpf_asm (net/tools/) for having a small DSL for more easily trying out BPF code while having _full_ control over it.

Maybe someone should start a binary-compatible Linux-only version of libpcap, where tcpdump will transparently make use of these low level improvements eventually. </rant> ;)

There's too much code dependent on libpcap to make a replacement possible.

Quoted 3 lines

This is a high-level decision, more than a technical one. Do we want to freeze classic BPF development in linux, even before we have a complete eBPF replacement, and zero eBPF tool (libpcap) support?

In my opinion, I don't think we strictly have to hard-freeze it. The only concern I see is that conceptually hooking into the flow_dissector to read out all keys for further processing on top of them 1) sort of breaks/bypasses the concept of BPF (as it's actually the task of BPF itself for doing this),

2) effectively freezes any changes to the
flow_dissector as BPF applications making use of it now depend on the provided offsets for doing further processing on top of them, 3) it

can already be resolved by (re-)writing the kernel's flow dissector in C-like syntax in user space iff eBPF can be loaded from there with similar performance. So shouldn't we rather work towards that as a more generic approach/goal in the mid term and w/o having to maintain a very short term intermediate solution that we need to special case along the code and have to carry around forever ...

There's still the problem of whether we want to obsolete classic BPF in the kernel before the tools (libpcap mainly) accept eBPF. This can take a lot.

Finally, what's the user's CLI interface you have in mind? Right now, tcpdump expressions are very handy: I know I can pass "ip[2:2] == 1500" or "(tcp[13] & 0x03)" to any libpcap-based application. This is very handy to log into a machine, and quickly run tcpdump to get the packets I'm interested on. What would be the model for using C-- eBPF filters in the same manner?