net: filter: Just In Time compiler for x86-64

In order to speedup packet filtering, here is an implementation of a
JIT compiler for x86_64

It is disabled by default, and must be enabled by the admin.

echo 1 >/proc/sys/net/core/bpf_jit_enable

It uses module_alloc() and module_free() to get memory in the 2GB text
kernel range since we call helpers functions from the generated code.

EAX : BPF A accumulator
EBX : BPF X accumulator
RDI : pointer to skb   (first argument given to JIT function)
RBP : frame pointer (even if CONFIG_FRAME_POINTER=n)
r9d : skb->len - skb->data_len (headlen)
r8  : skb->data

To get a trace of generated code, use :

echo 2 >/proc/sys/net/core/bpf_jit_enable

Example of generated code :

# tcpdump -p -n -s 0 -i eth1 host 192.168.20.0/24

flen=18 proglen=147 pass=3 image=ffffffffa00b5000
JIT code: ffffffffa00b5000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 60
JIT code: ffffffffa00b5010: 44 2b 4f 64 4c 8b 87 b8 00 00 00 be 0c 00 00 00
JIT code: ffffffffa00b5020: e8 24 7b f7 e0 3d 00 08 00 00 75 28 be 1a 00 00
JIT code: ffffffffa00b5030: 00 e8 fe 7a f7 e0 24 00 3d 00 14 a8 c0 74 49 be
JIT code: ffffffffa00b5040: 1e 00 00 00 e8 eb 7a f7 e0 24 00 3d 00 14 a8 c0
JIT code: ffffffffa00b5050: 74 36 eb 3b 3d 06 08 00 00 74 07 3d 35 80 00 00
JIT code: ffffffffa00b5060: 75 2d be 1c 00 00 00 e8 c8 7a f7 e0 24 00 3d 00
JIT code: ffffffffa00b5070: 14 a8 c0 74 13 be 26 00 00 00 e8 b5 7a f7 e0 24
JIT code: ffffffffa00b5080: 00 3d 00 14 a8 c0 75 07 b8 ff ff 00 00 eb 02 31
JIT code: ffffffffa00b5090: c0 c9 c3

BPF program is 144 bytes long, so native program is almost same size ;)

(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 8
(002) ld       [26]
(003) and      #0xffffff00
(004) jeq      #0xc0a81400      jt 16   jf 5
(005) ld       [30]
(006) and      #0xffffff00
(007) jeq      #0xc0a81400      jt 16   jf 17
(008) jeq      #0x806           jt 10   jf 9
(009) jeq      #0x8035          jt 10   jf 17
(010) ld       [28]
(011) and      #0xffffff00
(012) jeq      #0xc0a81400      jt 16   jf 13
(013) ld       [38]
(014) and      #0xffffff00
(015) jeq      #0xc0a81400      jt 16   jf 17
(016) ret      #65535
(017) ret      #0

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Ben Hutchings <bhutchings@solarflare.com>
Cc: Hagen Paul Pfeifer <hagen@jauu.net>
Signed-off-by: David S. Miller <davem@davemloft.net>

3 files changed, 78 insertions, 1 deletions

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 45266b75409..4609b85e559 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -135,6 +135,8 @@ struct sk_filter
 {
         atomic_t                refcnt;
         unsigned int            len;    /* Number of filter blocks */
+        unsigned int            (*bpf_func)(const struct sk_buff *skb,
+                                            const struct sock_filter *filter);
         struct rcu_head         rcu;
         struct sock_filter      insns[0];
 };
@@ -153,6 +155,80 @@ extern unsigned int sk_run_filter(const struct sk_buff *skb,
 extern int sk_attach_filter(struct sock_fprog *fprog, struct sock *sk);
 extern int sk_detach_filter(struct sock *sk);
 extern int sk_chk_filter(struct sock_filter *filter, int flen);
+
+#ifdef CONFIG_BPF_JIT
+extern void bpf_jit_compile(struct sk_filter *fp);
+extern void bpf_jit_free(struct sk_filter *fp);
+#define SK_RUN_FILTER(FILTER, SKB) (*FILTER->bpf_func)(SKB, FILTER->insns)
+#else
+static inline void bpf_jit_compile(struct sk_filter *fp)
+{
+}
+static inline void bpf_jit_free(struct sk_filter *fp)
+{
+}
+#define SK_RUN_FILTER(FILTER, SKB) sk_run_filter(SKB, FILTER->insns)
+#endif
+
+enum {
+        BPF_S_RET_K = 1,
+        BPF_S_RET_A,
+        BPF_S_ALU_ADD_K,
+        BPF_S_ALU_ADD_X,
+        BPF_S_ALU_SUB_K,
+        BPF_S_ALU_SUB_X,
+        BPF_S_ALU_MUL_K,
+        BPF_S_ALU_MUL_X,
+        BPF_S_ALU_DIV_X,
+        BPF_S_ALU_AND_K,
+        BPF_S_ALU_AND_X,
+        BPF_S_ALU_OR_K,
+        BPF_S_ALU_OR_X,
+        BPF_S_ALU_LSH_K,
+        BPF_S_ALU_LSH_X,
+        BPF_S_ALU_RSH_K,
+        BPF_S_ALU_RSH_X,
+        BPF_S_ALU_NEG,
+        BPF_S_LD_W_ABS,
+        BPF_S_LD_H_ABS,
+        BPF_S_LD_B_ABS,
+        BPF_S_LD_W_LEN,
+        BPF_S_LD_W_IND,
+        BPF_S_LD_H_IND,
+        BPF_S_LD_B_IND,
+        BPF_S_LD_IMM,
+        BPF_S_LDX_W_LEN,
+        BPF_S_LDX_B_MSH,
+        BPF_S_LDX_IMM,
+        BPF_S_MISC_TAX,
+        BPF_S_MISC_TXA,
+        BPF_S_ALU_DIV_K,
+        BPF_S_LD_MEM,
+        BPF_S_LDX_MEM,
+        BPF_S_ST,
+        BPF_S_STX,
+        BPF_S_JMP_JA,
+        BPF_S_JMP_JEQ_K,
+        BPF_S_JMP_JEQ_X,
+        BPF_S_JMP_JGE_K,
+        BPF_S_JMP_JGE_X,
+        BPF_S_JMP_JGT_K,
+        BPF_S_JMP_JGT_X,
+        BPF_S_JMP_JSET_K,
+        BPF_S_JMP_JSET_X,
+        /* Ancillary data */
+        BPF_S_ANC_PROTOCOL,
+        BPF_S_ANC_PKTTYPE,
+        BPF_S_ANC_IFINDEX,
+        BPF_S_ANC_NLATTR,
+        BPF_S_ANC_NLATTR_NEST,
+        BPF_S_ANC_MARK,
+        BPF_S_ANC_QUEUE,
+        BPF_S_ANC_HATYPE,
+        BPF_S_ANC_RXHASH,
+        BPF_S_ANC_CPU,
+};
+
 #endif /* __KERNEL__ */
 
 #endif /* __LINUX_FILTER_H__ */
diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index cb8178ab3c5..364bcf212f7 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -2514,6 +2514,7 @@ extern struct rtnl_link_stats64 *dev_get_stats(struct net_device *dev,
 extern int              netdev_max_backlog;
 extern int              netdev_tstamp_prequeue;
 extern int              weight_p;
+extern int              bpf_jit_enable;
 extern int              netdev_set_master(struct net_device *dev, struct net_device *master);
 extern int netdev_set_bond_master(struct net_device *dev,
                                   struct net_device *master);
diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index d0ae90af0b4..79aafbbf430 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
@@ -391,8 +391,8 @@ struct sk_buff {
 
         __u32                   rxhash;
 
+        __u16                   queue_mapping;
         kmemcheck_bitfield_begin(flags2);
-        __u16                   queue_mapping:16;
 #ifdef CONFIG_IPV6_NDISC_NODETYPE
         __u8                    ndisc_nodetype:2;
 #endif