Skip to contentSkip to conversation

nftables meets bpf

RFC PATCH In review Pablo Neira Ayuso 6 participants 14 messages Feb 19, 2018 – Feb 22, 2018

Subsystems (3)
lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover nftables meets bpf

Hi!

The following patchset is a PoC to add generic infrastructure to jit nftables to bpf. Rationale is the following:

nft --> netlink --> nf_tables -> intermediate representation --> bpf

The idea is to convert our internal nf_tables structure representation to an abstract syntax tree (our intermediate representation) that represents the ruleset. Then, we walk over this abstract syntax tree to generate bpf code. Finally, we store the bpf bytecode in a buffer in the rule, then when ruleset updates happen.

Patch #1 adds the intermediate representation infrastructure that creates
the syntax tree for the payload and the meta expressions - that allows us to match on payload and sk_buff meta information.

Patch #2 adds the infrastructure to walk over the syntax tree and invoke
the callbacks to generate the target backend representation.

Patch #3 adds the bpf backend jit, this places the struct nft_rule_jit
object in the rule object, that stores the bpf bytecode per rule. Then, from commit phase in nftables, this collects all per-rule bpf chunks and place them in the same program blob.

Benefits are many:

* Netlink-based interface, so we don't need to expose helper functions from the ebpf because of the nf_tables jit support. This allow us to keep all the scary details behind the curtain and let us evolve freely.

* Simplified infrastructure: We don't need the ebpf verifier complexity either given we trust the code we generate from the kernel. We don't need any complex userspace tooling either, just libnftnl and nft userspace binaries.

* Hardware offload: We can use this to offload rulesets to the only smartnic driver that we have in the tree that already implements bpf offload, hence, we can reuse this work already in place.

* Good support for incremental updates, we don't lose stateful information when performing updates on the ruleset. No full table/blob replacement as in iptables, which is a major well-known design limitation.

* Use existing bpf arch jits available in the tree.

Among many others that are also described in the nftables wiki [1].

Moreover, with some incremental work, this infrastructure will allow us to translate software nftables configurations to any backend target, including TCAM based hardware offloads commonly available in switches and nics.

Comments welcome.

Thanks.

[1] https://wiki.nftables.org/

P.S: Only classic bpf for this PoC at this stage, but it's a matter of
doing some knitting to get all the pieces together.

Pablo Neira Ayuso (3):
netfilter: nf_tables: add infrastructure to provide intermediate
representation
netfilter: add ast to target transformation
netfilter: nf_tables: add BPF-based jit infrastructure

 include/net/netfilter/nf_tables.h     |  25 +++
 include/net/netfilter/nf_tables_jit.h | 136 ++++++++++++++
 net/ipv4/netfilter/nf_tables_ipv4.c   |   7 +-
 net/netfilter/Makefile                |   3 +-
 net/netfilter/nf_tables_api.c         |  28 +++
 net/netfilter/nf_tables_bpf.c         |  92 +++++++++
 net/netfilter/nf_tables_jit.c         | 339 ++++++++++++++++++++++++++++++++++
 net/netfilter/nft_cmp.c               |  87 +++++++++
 net/netfilter/nft_meta.c              |  19 ++
 net/netfilter/nft_payload.c           |  22 +++
 10 files changed, 752 insertions(+), 6 deletions(-)
 create mode 100644 include/net/netfilter/nf_tables_jit.h
 create mode 100644 net/netfilter/nf_tables_bpf.c
 create mode 100644 net/netfilter/nf_tables_jit.c
Signature · 1 line
2.11.0
author maintainer
#1 lore raw

RFC PATCH 1/3 netfilter: nf_tables: add infrastructure to provide intermediate representation

This infrastructure allows us to build small abstract syntax trees to represent the rule.

You can use this representation to easily generate another different target internal representation.

This intermediate representation makes the nf_tables codebase independent from layout changes in its binary representation, to avoid hard dependencies between us and the target representation.

---
 include/net/netfilter/nf_tables.h     |   6 ++
 include/net/netfilter/nf_tables_jit.h |  84 +++++++++++++++++++++
 net/netfilter/Makefile                |   3 +-
 net/netfilter/nf_tables_jit.c         | 136 ++++++++++++++++++++++++++++++++++
 net/netfilter/nft_cmp.c               |  87 ++++++++++++++++++++++
 net/netfilter/nft_meta.c              |  19 +++++
 net/netfilter/nft_payload.c           |  22 ++++++
 7 files changed, 356 insertions(+), 1 deletion(-)
 create mode 100644 include/net/netfilter/nf_tables_jit.h
 create mode 100644 net/netfilter/nf_tables_jit.c
include/net/netfilter/nf_tables.h +6 -0
index 663b015dace5..8a6406f3811f 100644
@@ -712,6 +712,8 @@ struct nft_expr_type {
 
 #define NFT_EXPR_STATEFUL		0x1
 
+struct nft_ast_expr;
+
 /**
  *	struct nft_expr_ops - nf_tables expression operations
  *
@@ -722,6 +724,7 @@ struct nft_expr_type {
  *	@dump: function to dump parameters
  *	@type: expression type
  *	@validate: validate expression, called during loop detection
+ *	@delinearize: convert expression to intermediate representation
  *	@data: extra data to attach to this expression operation
  */
 struct nft_expr;
@@ -743,6 +746,9 @@ struct nft_expr_ops {
 	int				(*validate)(const struct nft_ctx *ctx,
 						    const struct nft_expr *expr,
 						    const struct nft_data **data);
+	int				(*delinearize)(struct nft_ast_expr **regs,
+						       const struct nft_expr *expr,
+						       struct list_head *stmt);
 	const struct nft_expr_type	*type;
 	void				*data;
 };
include/net/netfilter/nf_tables_jit.h new file +84 -0

84 lines not on this page · raw message

net/netfilter/Makefile +2 -1
index 5d9b8b959e58..8b0006e3ae6f 100644
@@ -75,7 +75,8 @@ obj-$(CONFIG_NF_DUP_NETDEV)	+= nf_dup_netdev.o
 # nf_tables
 nf_tables-objs := nf_tables_core.o nf_tables_api.o nf_tables_trace.o \
 		  nft_immediate.o nft_cmp.o nft_range.o nft_bitwise.o \
-		  nft_byteorder.o nft_payload.o nft_lookup.o nft_dynset.o
+		  nft_byteorder.o nft_payload.o nft_lookup.o nft_dynset.o \
+		  nf_tables_jit.o
 
 obj-$(CONFIG_NF_TABLES)		+= nf_tables.o
 obj-$(CONFIG_NF_TABLES_INET)	+= nf_tables_inet.o
net/netfilter/nf_tables_jit.c new file +136 -0

136 lines not on this page · raw message

net/netfilter/nft_cmp.c +87 -0

117 lines not on this page · raw message

net/netfilter/nft_meta.c +19 -0
index 8fb91940e2e7..920434a9470c 100644
@@ -24,6 +24,7 @@
 #include <net/tcp_states.h> /* for TCP_TIME_WAIT */
 #include <net/netfilter/nf_tables.h>
 #include <net/netfilter/nf_tables_core.h>
+#include <net/netfilter/nf_tables_jit.h>
 #include <net/netfilter/nft_meta.h>
 
 #include <uapi/linux/netfilter_bridge.h> /* NF_BR_PRE_ROUTING */
@@ -469,6 +470,23 @@ void nft_meta_set_destroy(const struct nft_ctx *ctx,
 }
 EXPORT_SYMBOL_GPL(nft_meta_set_destroy);
 
+static int nft_meta_get_delinearize(struct nft_ast_expr **regs,
+				    const struct nft_expr *expr,
+				    struct list_head *stmt_list)
+{
+	struct nft_meta *priv = nft_expr_priv(expr);
+	struct nft_ast_expr *dlexpr;
+
+	dlexpr = nft_ast_expr_alloc(NFT_AST_EXPR_META);
+	if (dlexpr == NULL)
+		return -ENOMEM;
+
+	dlexpr->meta.key = priv->key;
+
+	regs[priv->dreg] = dlexpr;
+	return 0;
+}
+
 static struct nft_expr_type nft_meta_type;
 static const struct nft_expr_ops nft_meta_get_ops = {
 	.type		= &nft_meta_type,
@@ -477,6 +495,7 @@ static const struct nft_expr_ops nft_meta_get_ops = {
 	.init		= nft_meta_get_init,
 	.dump		= nft_meta_get_dump,
 	.validate	= nft_meta_get_validate,
+	.delinearize	= nft_meta_get_delinearize,
 };
 
 static const struct nft_expr_ops nft_meta_set_ops = {
net/netfilter/nft_payload.c +22 -0
index e110b0ebbf58..0d3b065b701d 100644
@@ -18,6 +18,7 @@
 #include <linux/netfilter/nf_tables.h>
 #include <net/netfilter/nf_tables_core.h>
 #include <net/netfilter/nf_tables.h>
+#include <net/netfilter/nf_tables_jit.h>
 /* For layer 4 checksum field offset. */
 #include <linux/tcp.h>
 #include <linux/udp.h>
@@ -153,12 +154,32 @@ static int nft_payload_dump(struct sk_buff *skb, const struct nft_expr *expr)
 	return -1;
 }
 
+static int nft_payload_delinearize(struct nft_ast_expr **regs,
+				   const struct nft_expr *expr,
+				   struct list_head *stmt_list)
+{
+	struct nft_payload *priv = nft_expr_priv(expr);
+	struct nft_ast_expr *dlexpr;
+
+	dlexpr = nft_ast_expr_alloc(NFT_AST_EXPR_PAYLOAD);
+	if (dlexpr == NULL)
+		return -ENOMEM;
+
+	dlexpr->payload.base	= priv->base;
+	dlexpr->payload.offset	= priv->offset;
+	dlexpr->len		= priv->len;
+
+	regs[priv->dreg] = dlexpr;
+	return 0;
+}
+
 static const struct nft_expr_ops nft_payload_ops = {
 	.type		= &nft_payload_type,
 	.size		= NFT_EXPR_SIZE(sizeof(struct nft_payload)),
 	.eval		= nft_payload_eval,
 	.init		= nft_payload_init,
 	.dump		= nft_payload_dump,
+	.delinearize	= nft_payload_delinearize,
 };
 
 const struct nft_expr_ops nft_payload_fast_ops = {
@@ -167,6 +188,7 @@ const struct nft_expr_ops nft_payload_fast_ops = {
 	.eval		= nft_payload_eval,
 	.init		= nft_payload_init,
 	.dump		= nft_payload_dump,
+	.delinearize	= nft_payload_delinearize,
 };
 
 static inline void nft_csum_replace(__sum16 *sum, __wsum fsum, __wsum tsum)
Signature · 1 line
2.11.0
author maintainer
#2 lore raw

RFC PATCH 2/3 netfilter: add ast to target transformation

In reply to Pablo Neira Ayuso

This patch adds the generic infrastructure is used to describe the transformation from abstract syntax tree to target internal representation.

The target has to define the transformation callbacks:

struct nft_ast_xfrm_desc {
       const struct nft_ast_proto_desc *proto_desc;
       const struct nft_ast_meta_desc  *meta_desc;
};

The protocol and meta description structure provide the callback to transform internal representation to the corresponding target.

struct nft_ast_{proto,meta}_desc {
int (*xfrm)(const struct nft_ast_expr *dlexpr,
struct nft_ast_xfrm_state *state, void *data);
};

---
 include/net/netfilter/nf_tables_jit.h | 39 +++++++++++++++++++
 net/netfilter/nf_tables_jit.c         | 71 +++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)
include/net/netfilter/nf_tables_jit.h +39 -0
index 124d3da91b0d..dff3af7ad420 100644
@@ -81,4 +81,43 @@ void nft_ast_stmt_list_print(struct list_head *stmt_list);
 
 int nft_delinearize(struct list_head *ast_stmt_list, struct nft_rule *rule);
 
+/*
+ * Tree of transformation callback definitions.
+ */
+struct nft_ast_xfrm_state;
+
+/**
+ *	struct nft_ast_proto_desc - nf_tables protocol transformation description
+ *
+ *	@xfrm: transformation callback
+ */
+struct nft_ast_proto_desc {
+	int (*xfrm)(const struct nft_ast_expr *dlexpr,
+		    struct nft_ast_xfrm_state *state, void *data);
+};
+
+/**
+ *	struct nft_ast_meta_desc - nf_tables meta transformation description
+ *
+ *	@xfrm: transformation callback
+ */
+struct nft_ast_meta_desc {
+	int (*xfrm)(const struct nft_ast_expr *dlexpr,
+		    struct nft_ast_xfrm_state *state, void *data);
+};
+
+/**
+ *	struct nft_ast_xfrm_desc - nf_tables generic transformation description
+ *
+ *	@key: meta key
+ *	@xfrm: transformation callback
+ */
+struct nft_ast_xfrm_desc {
+	const struct nft_ast_proto_desc	*proto_desc;
+	const struct nft_ast_meta_desc	*meta_desc;
+};
+
+int nft_ast_xfrm(const struct list_head *ast_stmt_list,
+		 const struct nft_ast_xfrm_desc *base_desc, void *data);
+
 #endif
net/netfilter/nf_tables_jit.c +71 -0

74 lines not on this page · raw message

Signature · 1 line
2.11.0
author maintainer
#3 lore raw

RFC PATCH 3/3 netfilter: nf_tables: add BPF-based jit infrastructure

In reply to Pablo Neira Ayuso
Quoted 1 line

From nf_tables_newrule(), this calls nft_jit_rule() that transforms

our internal expression structure layout to abstract syntax tree, then we walk over this syntax tree to generate the BPF instructions that are placed in the rule jit buffer. From the commit phase, collect all jit buffers, place them in a BPF program that gets attached to the chain.

This should be good enough to test simple payload and meta match. For more sophisticated stuff, we may use internal bpf helpers to call our _eval() functions.

---
 include/net/netfilter/nf_tables.h     |  19 +++++
 include/net/netfilter/nf_tables_jit.h |  13 ++++
 net/ipv4/netfilter/nf_tables_ipv4.c   |   7 +-
 net/netfilter/Makefile                |   2 +-
 net/netfilter/nf_tables_api.c         |  28 ++++++++
 net/netfilter/nf_tables_bpf.c         |  92 ++++++++++++++++++++++++
 net/netfilter/nf_tables_jit.c         | 132 ++++++++++++++++++++++++++++++++++
 7 files changed, 287 insertions(+), 6 deletions(-)
 create mode 100644 net/netfilter/nf_tables_bpf.c
include/net/netfilter/nf_tables.h +19 -0
index 8a6406f3811f..09a2faceee91 100644
@@ -10,6 +10,7 @@
 #include <linux/netfilter/nf_tables.h>
 #include <linux/u64_stats_sync.h>
 #include <net/netfilter/nf_flow_table.h>
+#include <linux/filter.h>
 #include <net/netlink.h>
 
 #define NFT_JUMP_STACK_SIZE	16
@@ -796,10 +797,23 @@ static inline int nft_expr_clone(struct nft_expr *dst, struct nft_expr *src)
 	return 0;
 }
 
+/* Size of buffer to store jit transformation. Instead of having a fixed buffer
+ * size per rule, we can calculate this in runtime when walking over the syntax
+ * tree instead, this is a proof of concept at this stage, so use a fixed size
+ * buffer.
+ */
+#define NFT_RULE_JIT_BUFSIZ	32
+
+struct nft_rule_jit {
+	struct sock_filter	insn[NFT_RULE_JIT_BUFSIZ];
+	unsigned int		len;
+};
+
 /**
  *	struct nft_rule - nf_tables rule
  *
  *	@list: used internally
+ *	@jit: instructions that result from jit transformation
  *	@handle: rule handle
  *	@genmask: generation mask
  *	@dlen: length of expression data
@@ -808,6 +822,7 @@ static inline int nft_expr_clone(struct nft_expr *dst, struct nft_expr *src)
  */
 struct nft_rule {
 	struct list_head		list;
+	struct nft_rule_jit		jit;
 	u64				handle:42,
 					genmask:2,
 					dlen:12,
@@ -915,6 +930,8 @@ struct nft_stats {
  *	struct nft_base_chain - nf_tables base chain
  *
  *	@ops: netfilter hook ops
+ *	@fp: jitted filter program
+ *	@fp_stash: jitted filter program stash (for two-commit phase protocol)
  *	@type: chain type
  *	@policy: default policy
  *	@stats: per-cpu chain stats
@@ -923,6 +940,8 @@ struct nft_stats {
  */
 struct nft_base_chain {
 	struct nf_hook_ops		ops;
+	struct bpf_prog	__rcu		*fp;
+	struct bpf_prog			*fp_stash;
 	const struct nf_chain_type	*type;
 	u8				policy;
 	u8				flags;
include/net/netfilter/nf_tables_jit.h +13 -0
index dff3af7ad420..5309a45a6dc2 100644
@@ -120,4 +120,17 @@ struct nft_ast_xfrm_desc {
 int nft_ast_xfrm(const struct list_head *ast_stmt_list,
 		 const struct nft_ast_xfrm_desc *base_desc, void *data);
 
+struct sock_fprog_kern;
+
+void nft_jit_emit_basechain_policy(struct sock_fprog_kern *prog,
+				   unsigned int verdict);
+int nft_jit_rule(struct nft_rule *rule,
+                 const struct nft_ast_xfrm_desc *xfrm_desc);
+
+extern struct nft_ast_xfrm_desc nft_jit_bpf_xfrm_desc;
+
+int nft_jit_prepare(struct net *net);
+void nft_jit_commit(struct net *net);
+void nft_jit_release(struct net *net);
+
 #endif
net/ipv4/netfilter/nf_tables_ipv4.c +2 -5
index 96f955496d5f..4cb872f3e5a4 100644
@@ -22,12 +22,9 @@ static unsigned int nft_do_chain_ipv4(void *priv,
 				      struct sk_buff *skb,
 				      const struct nf_hook_state *state)
 {
-	struct nft_pktinfo pkt;
+	const struct nft_chain *chain = priv;
 
-	nft_set_pktinfo(&pkt, skb, state);
-	nft_set_pktinfo_ipv4(&pkt, skb);
-
-	return nft_do_chain(&pkt, priv);
+	return BPF_PROG_RUN(nft_base_chain(chain)->fp, skb);
 }
 
 static const struct nf_chain_type filter_ipv4 = {
net/netfilter/Makefile +1 -1
index 8b0006e3ae6f..6bd2bcbaa74c 100644
@@ -76,7 +76,7 @@ obj-$(CONFIG_NF_DUP_NETDEV)	+= nf_dup_netdev.o
 nf_tables-objs := nf_tables_core.o nf_tables_api.o nf_tables_trace.o \
 		  nft_immediate.o nft_cmp.o nft_range.o nft_bitwise.o \
 		  nft_byteorder.o nft_payload.o nft_lookup.o nft_dynset.o \
-		  nf_tables_jit.o
+		  nf_tables_jit.o nf_tables_bpf.o
 
 obj-$(CONFIG_NF_TABLES)		+= nf_tables.o
 obj-$(CONFIG_NF_TABLES_INET)	+= nf_tables_inet.o
net/netfilter/nf_tables_api.c +28 -0
index 8b9fe30de0cd..4746631a5e9d 100644
@@ -15,11 +15,13 @@
 #include <linux/netlink.h>
 #include <linux/vmalloc.h>
 #include <linux/netfilter.h>
+#include <linux/filter.h>
 #include <linux/netfilter/nfnetlink.h>
 #include <linux/netfilter/nf_tables.h>
 #include <net/netfilter/nf_flow_table.h>
 #include <net/netfilter/nf_tables_core.h>
 #include <net/netfilter/nf_tables.h>
+#include <net/netfilter/nf_tables_jit.h>
 #include <net/net_namespace.h>
 #include <net/sock.h>
 
@@ -1324,13 +1326,16 @@ static int nf_tables_addchain(struct nft_ctx *ctx, u8 family, u8 genmask,
 	struct nft_stats __percpu *stats;
 	struct net *net = ctx->net;
 	struct nft_chain *chain;
+	struct bpf_prog *fp;
 	int err;
 
 	if (table->use == UINT_MAX)
 		return -EOVERFLOW;
 
 	if (nla[NFTA_CHAIN_HOOK]) {
+		struct sock_fprog_kern prog;
 		struct nft_chain_hook hook;
+		struct sock_filter filter;
 		struct nf_hook_ops *ops;
 
 		err = nft_chain_parse_hook(net, nla, &hook, family, create);
@@ -1371,6 +1376,18 @@ static int nf_tables_addchain(struct nft_ctx *ctx, u8 family, u8 genmask,
 		if (basechain->type->type == NFT_CHAIN_T_NAT)
 			ops->nat_hook = true;
 
+		prog.filter = &filter;
+		prog.len = 0;
+		nft_jit_emit_basechain_policy(&prog, NF_ACCEPT);
+
+		if (bpf_prog_create(&fp, &prog)) {
+			nft_chain_release_hook(&hook);
+			free_percpu(basechain->stats);
+			kfree(basechain);
+			return -ENOMEM;
+		}
+		RCU_INIT_POINTER(basechain->fp, fp);
+
 		chain->flags |= NFT_BASE_CHAIN;
 		basechain->policy = policy;
 	} else {
@@ -2324,6 +2341,10 @@ static int nf_tables_newrule(struct net *net, struct sock *nlsk,
 			list_add_rcu(&rule->list, &chain->rules);
 	}
 
+	err = nft_jit_rule(rule, &nft_jit_bpf_xfrm_desc);
+	if (err < 0)
+		goto err3;
+
 	if (nft_trans_rule_add(&ctx, NFT_MSG_NEWRULE, rule) == NULL) {
 		err = -ENOMEM;
 		goto err3;
@@ -5702,6 +5723,9 @@ static int nf_tables_commit(struct net *net, struct sk_buff *skb)
 	struct nft_trans *trans, *next;
 	struct nft_trans_elem *te;
 
+	if (nft_jit_prepare(net) < 0)
+		return -1;
+
 	/* Bump generation counter, invalidate any dump in progress */
 	while (++net->nft.base_seq == 0);
 
@@ -5827,8 +5851,12 @@ static int nf_tables_commit(struct net *net, struct sk_buff *skb)
 		}
 	}
 
+	nft_jit_commit(net);
+
 	synchronize_rcu();
 
+	nft_jit_release(net);
+
 	list_for_each_entry_safe(trans, next, &net->nft.commit_list, list) {
 		list_del(&trans->list);
 		nf_tables_commit_release(trans);
net/netfilter/nf_tables_bpf.c new file +92 -0

92 lines not on this page · raw message

net/netfilter/nf_tables_jit.c +132 -0

141 lines not on this page · raw message

Signature · 1 line
2.11.0
maintainer
#4 lore raw

Re: [PATCH RFC 3/3] netfilter: nf_tables: add BPF-based jit infrastructure

From: Pablo Neira Ayuso <[email protected]>
Date: Mon, 19 Feb 2018 17:37:06 +0100

Quoted 11 lines

From nf_tables_newrule(), this calls nft_jit_rule() that transforms our internal expression structure layout to abstract syntax tree, then we walk over this syntax tree to generate the BPF instructions that are placed in the rule jit buffer. From the commit phase, collect all jit buffers, place them in a BPF program that gets attached to the chain.

This should be good enough to test simple payload and meta match. For more sophisticated stuff, we may use internal bpf helpers to call our _eval() functions.

I'm very suprised that this is generating classical BPF filters.

We have native eBPF and that is what anything generating new code should be using, rather than the 20+ year old CBPF.

Furthermore, we should not ever generate and use bpf code snippets to use directly in the kernel.

Instead, all BPF code should be given to the kernel from userspace through the bpf syscall interface, so that the boundry is distinct and the verifier can be run properly on all pieces of eBPF code before the kernel uses it.

author maintainer
#5 lore raw

Re: [PATCH RFC 3/3] netfilter: nf_tables: add BPF-based jit infrastructure

Hi David,

Quoted 4 lines · David Miller

I'm very suprised that this is generating classical BPF filters.

We have native eBPF and that is what anything generating new code should be using, rather than the 20+ year old CBPF.

I'm not the only one that likes 90s interfaces after all ;-)

I'll explore how to generate eBPF code in the next patchset version.

Thanks!

#6 lore raw

Re: [PATCH RFC 3/3] netfilter: nf_tables: add BPF-based jit infrastructure

Quoted 11 lines · Pablo Neira Ayuso

Hi David,

Quoted 4 lines · David Miller

I'm very suprised that this is generating classical BPF filters.

We have native eBPF and that is what anything generating new code should be using, rather than the 20+ year old CBPF.

I'm not the only one that likes 90s interfaces after all ;-)

I'll explore how to generate eBPF code in the next patchset version.

from the user space please...
it was already explained few times in this thread and in other threads (kprobe, seccomp, etc related) over the last years why it's not ok to generate eBPF from the kernel.

author maintainer
#7 lore raw

Re: [PATCH RFC 3/3] netfilter: nf_tables: add BPF-based jit infrastructure

Hi Alexei,

Quoted 5 lines · Alexei Starovoitov
Quoted 2 lines · Pablo Neira Ayuso

I'll explore how to generate eBPF code in the next patchset version.

from the user space please...

OK, let's do that, from user space I see two things we can do to integrate with eBPF:

1) Add a bpf chain type, that we can use to allow to attach eBPF programs, it would look similar to tc cls_bpf. We mentioned this idea in the past, it can open up existing netfilter hooks for custom eBPF programs.

2) Use the usermode helper infrastructure that bpfilter PoC is proposing to transparently pass the nft netlink batch to userspace for eBPF jit. This would allow us to convert the datapath to eBPF.

Regarding the usermode helper, just an idea, not sure your plans but it's probably interesting to explore some sort of messaging-based communication between kernel and the eBPF userspace infrastructure. But that can be done later on, I understand all this is a PoC.

Thanks!

#8 lore raw
In reply to Pablo Neira Ayuso

On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
[...]

Quoted 8 lines

* Simplified infrastructure: We don't need the ebpf verifier complexity either given we trust the code we generate from the kernel. We don't need any complex userspace tooling either, just libnftnl and nft userspace binaries.

* Hardware offload: We can use this to offload rulesets to the only smartnic driver that we have in the tree that already implements bpf offload, hence, we can reuse this work already in place.

In addition Dave's points, regarding the above two, this will also only work behind the verifier since NIC offloading piggy-backs on the verifier's program analysis to prepare and generate a dev specific JITed BPF prog, so it's not the same as normal host JITs (and there, the cBPF -> eBPF in kernel migration adds a lot of headaches already due to different underlying assumptions coming from the two flavors, even if both are eBPF insns in the end), and given this, offloading will also only work for eBPF and not cBPF. There's a lot more the verifier is doing internally, like performing various different program rewrites from the context, for helpers (e.g. inlining), and for internal insn mappings that are not exposed (e.g. in calls), so we definitely need to go through it.

Thanks,
Daniel

author maintainer
#9 lore raw

Hi Daniel,

Quoted 11 lines · Daniel Borkmann

On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
[...]

Quoted 8 lines

* Simplified infrastructure: We don't need the ebpf verifier complexity either given we trust the code we generate from the kernel. We don't need any complex userspace tooling either, just libnftnl and nft userspace binaries.

* Hardware offload: We can use this to offload rulesets to the only smartnic driver that we have in the tree that already implements bpf offload, hence, we can reuse this work already in place.

Quoted 8 lines

In addition Dave's points, regarding the above two, this will also only work behind the verifier since NIC offloading piggy-backs on the verifier's program analysis to prepare and generate a dev specific JITed BPF prog, so it's not the same as normal host JITs (and there, the cBPF -> eBPF in kernel migration adds a lot of headaches already due to different underlying assumptions coming from the two flavors, even if both are eBPF insns in the end), and given this, offloading will also only work for eBPF and not cBPF.

We also have a large range of TCAM based hardware offload outthere that will _not_ work with your BPF HW offload infrastructure. What this bpf infrastructure pushes into the kernel is just a blob expressing things in a very low-level instruction-set: trying to find a mapping of that to typical HW intermediate representations in the TCAM based HW offload world will be simply crazy.

Quoted 4 lines

There's a lot more the verifier is doing internally, like performing various different program rewrites from the context, for helpers (e.g. inlining), and for internal insn mappings that are not exposed (e.g. in calls), so we definitely need to go through it.

If we need to call the verifier from the kernel for the code that we generate there for this initial stage, that should be not an issue.

The BPF interface is lacking many of the features and flexibility we have in netlink these days, and it is only allowing for monolitic ruleset replacement. This approach also loses internal rule stateful information that we're doing in the packet path when updating the ruleset. So it's taking us back to exactly the same mistakes we made in iptables back in the 90s as it's been mentioned already.

So I just wish I can count with your help in this process, we can get the best of the two worlds by providing a subsystem that allows users to configure packet classification through one single interface, no matter if the policy representation ends up being in software or HW offloads, either TCAM or smartnic.

Thanks.

#10 lore raw

Hi Pablo,

Quoted 21 lines · Pablo Neira Ayuso
Quoted 11 lines · Daniel Borkmann

On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
[...]

Quoted 8 lines

* Simplified infrastructure: We don't need the ebpf verifier complexity either given we trust the code we generate from the kernel. We don't need any complex userspace tooling either, just libnftnl and nft userspace binaries.

* Hardware offload: We can use this to offload rulesets to the only smartnic driver that we have in the tree that already implements bpf offload, hence, we can reuse this work already in place.

Quoted 8 lines

In addition Dave's points, regarding the above two, this will also only work behind the verifier since NIC offloading piggy-backs on the verifier's program analysis to prepare and generate a dev specific JITed BPF prog, so it's not the same as normal host JITs (and there, the cBPF -> eBPF in kernel migration adds a lot of headaches already due to different underlying assumptions coming from the two flavors, even if both are eBPF insns in the end), and given this, offloading will also only work for eBPF and not cBPF.

Quoted 6 lines

We also have a large range of TCAM based hardware offload outthere that will _not_ work with your BPF HW offload infrastructure. What this bpf infrastructure pushes into the kernel is just a blob expressing things in a very low-level instruction-set: trying to find a mapping of that to typical HW intermediate representations in the TCAM based HW offload world will be simply crazy.

Sure, and I think that's fine; there have been possible ways proposed in last netdev conference how this can be addressed by adding hints [0] in a programmable way as meta data in front of the packet as one option to accelerate. Other than that for fully pushing into hardware people will get a SmartNIC and there are multiple big vendors in that area working on them. Potentially in few years from now they're more and more becoming a commodity in DCs, lets see. Maybe we'll be programming them similarly as the case with graphics cards today. :-)

[0] https://www.netdevconf.org/2.2/session.html?waskiewicz-xdpacceleration-talk

Quoted 11 lines
Quoted 4 lines

There's a lot more the verifier is doing internally, like performing various different program rewrites from the context, for helpers (e.g. inlining), and for internal insn mappings that are not exposed (e.g. in calls), so we definitely need to go through it.

If we need to call the verifier from the kernel for the code that we generate there for this initial stage, that should be not an issue.

The BPF interface is lacking many of the features and flexibility we have in netlink these days, and it is only allowing for monolitic ruleset replacement. This approach also loses internal rule stateful

That only depends how you partition your program, a partial reconfiguration is definitely possible and done so today, for example as talked about in LB use case where the packet processing is staged e.g. into sampling, DDoS mitigation, and encap + redirect phase, where each of the components can be replaced atomically during runtime. So there is definitely flexibility available.

Thanks,
Daniel

Quoted 12 lines

information that we're doing in the packet path when updating the ruleset. So it's taking us back to exactly the same mistakes we made in iptables back in the 90s as it's been mentioned already.

So I just wish I can count with your help in this process, we can get the best of the two worlds by providing a subsystem that allows users to configure packet classification through one single interface, no matter if the policy representation ends up being in software or HW offloads, either TCAM or smartnic.

Thanks.

#11 lore raw
In reply to Pablo Neira Ayuso
Quoted 6 lines · Pablo Neira Ayuso

We also have a large range of TCAM based hardware offload outthere that will _not_ work with your BPF HW offload infrastructure. What this bpf infrastructure pushes into the kernel is just a blob expressing things in a very low-level instruction-set: trying to find a mapping of that to typical HW intermediate representations in the TCAM based HW offload world will be simply crazy.

I'm not sure where the TCAM talk is coming from. Think much smaller - cellular modems/phone SoCs, 32bit ARM/MIPS router box CPUs. The information the verifier is gathering will be crucial for optimizing those. Please don't discount the value of being able to use heterogeneous processing units by the networking stack.

#12 lore raw
Quoted 8 lines · Jakub Kicinski
Quoted 6 lines · Pablo Neira Ayuso

We also have a large range of TCAM based hardware offload outthere that will _not_ work with your BPF HW offload infrastructure. What this bpf infrastructure pushes into the kernel is just a blob expressing things in a very low-level instruction-set: trying to find a mapping of that to typical HW intermediate representations in the TCAM based HW offload world will be simply crazy.

Quoted 6 lines

I'm not sure where the TCAM talk is coming from. Think much smaller - cellular modems/phone SoCs, 32bit ARM/MIPS router box CPUs. The information the verifier is gathering will be crucial for optimizing those. Please don't discount the value of being able to use heterogeneous processing units by the networking stack.

The only use case that we have a good answer for is when there is no HW offload capability available, because there, we know that eBPF is our best possible solution for a software fast path, in large part because of all the efforts that went into making it both safe and fast.

When there is offloading HW available, there does not appear to be a perfect answer to this problem of, given a standard Linux utility that can express any sort of match + action, be it ethtool::rxnfc, tc/cls_{u32,flower}, nftables, how do I transform that into what makes most sense to my HW? You could:

- have hardware that understands BPF bytecode directly, great, then you don't have to do anything, just pass it up the driver baby, oh wait, it's not that simple, the NFP driver is not small

- transform BPF back into something that your hardware understand, does that belong in the kernel? Maybe, maybe not

- use a completely different intermediate representation like P4, brainfuck, I don't know

Maybe first things first, we have at least 3 different programming interfaces, if not more: ethtool::rxnfc, tc/cls_{u32,flower}, nftables that are all capable of programming TCAMs and hardware capable of match
+ action, how about we start with having some sort of common library code that:

- validates input parameters against HW capabilities
- does the adequate transformation from any of these interfaces into a generic set of input parameters
- define what the appropriate behavior is when programming through all of these 3 interfaces that ultimately access the same shared piece of HW, and therefore need to manage resources allocation?

</rant>

Signature · 1 line
Florian
#13 lore raw
Quoted 15 lines · Florian Fainelli
Quoted 8 lines · Jakub Kicinski
Quoted 6 lines · Pablo Neira Ayuso

We also have a large range of TCAM based hardware offload outthere that will _not_ work with your BPF HW offload infrastructure. What this bpf infrastructure pushes into the kernel is just a blob expressing things in a very low-level instruction-set: trying to find a mapping of that to typical HW intermediate representations in the TCAM based HW offload world will be simply crazy.

Quoted 5 lines

I'm not sure where the TCAM talk is coming from. Think much smaller - cellular modems/phone SoCs, 32bit ARM/MIPS router box CPUs. The information the verifier is gathering will be crucial for optimizing those. Please don't discount the value of being able to use heterogeneous processing units by the networking stack.

Quoted 4 lines

The only use case that we have a good answer for is when there is no HW offload capability available, because there, we know that eBPF is our best possible solution for a software fast path, in large part because of all the efforts that went into making it both safe and fast.

I was trying to point out that JITing eBPF for the host on 32 bit systems is already a pain, Jiong Wang is leading an effort to improve this both from LLVM and verifier angles, IOW running through the verifier may become useful even for host JITs :)

Quoted 9 lines

When there is offloading HW available, there does not appear to be a perfect answer to this problem of, given a standard Linux utility that can express any sort of match + action, be it ethtool::rxnfc, tc/cls_{u32,flower}, nftables, how do I transform that into what makes most sense to my HW? You could:

- have hardware that understands BPF bytecode directly, great, then you don't have to do anything, just pass it up the driver baby, oh wait, it's not that simple, the NFP driver is not small

True, it's not the largest but fair point, IMHO we should be trying to push for sharing as much code between drivers as possible, and on all fronts, but that's a topic for another time...

Quoted 2 lines

- transform BPF back into something that your hardware understand, does that belong in the kernel? Maybe, maybe not

Personally, I think there is non-zero probability of AMP CPUs/systems becoming more common. NFP is very powerful and fast, but less advanced solution may just use an off-the-shelf MIPS/ARM/Andes core. Taking it slightly further from home to the cellular/WiFi wake up problem which was mentioned by Android folks at one of netdevs - if we have MIPS/ARM/Andes *host* JIT in the kernel, and the NIC processor is built on one of those all the driver needs to provide is some glue and we can offload filtering to the MCU on the NIC/modem!

Quoted 10 lines

- use a completely different intermediate representation like P4, brainfuck, I don't know

Maybe first things first, we have at least 3 different programming interfaces, if not more: ethtool::rxnfc, tc/cls_{u32,flower}, nftables that are all capable of programming TCAMs and hardware capable of match
+ action, how about we start with having some sort of common library code that:

- validates input parameters against HW capabilities

This one may be quite hard.

Quoted 5 lines

- does the adequate transformation from any of these interfaces into a generic set of input parameters
- define what the appropriate behavior is when programming through all of these 3 interfaces that ultimately access the same shared piece of HW, and therefore need to manage resources allocation?

That would be great! :) Flower stands out today as the most feature rich and a go-to for TCAM offloads.

Quoted 1 line

</rant>