[PATCH RFC PoC 0/3] nftables meets bpf

[PATCH RFC PoC 0/3] nftables meets bpf

[Pablo Neira Ayuso]

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

-- 
2.11.0

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

[Pablo Neira Ayuso]

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.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 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

diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h
index 663b015dace5..8a6406f3811f 100644
--- a/include/net/netfilter/nf_tables.h
+++ b/include/net/netfilter/nf_tables.h
@@ -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;
 };
diff --git a/include/net/netfilter/nf_tables_jit.h b/include/net/netfilter/nf_tables_jit.h
new file mode 100644
index 000000000000..124d3da91b0d
--- /dev/null
+++ b/include/net/netfilter/nf_tables_jit.h
@@ -0,0 +1,84 @@
+#ifndef _NFTABLES_JIT_H_
+#define _NFTABLES_JIT_H_
+
+#include <uapi/linux/netfilter/nf_tables.h>
+
+enum nft_ast_expr_type {
+	NFT_AST_EXPR_UNSPEC	= 0,
+	NFT_AST_EXPR_RELATIONAL,
+	NFT_AST_EXPR_VALUE,
+	NFT_AST_EXPR_META,
+	NFT_AST_EXPR_PAYLOAD,
+};
+
+enum nft_ast_expr_ops {
+	NFT_AST_OP_INVALID,
+	NFT_AST_OP_EQ,
+	NFT_AST_OP_NEQ,
+	NFT_AST_OP_LT,
+	NFT_AST_OP_LTE,
+	NFT_AST_OP_GT,
+	NFT_AST_OP_GTE,
+	NFT_AST_OP_AND,
+	NFT_AST_OP_OR,
+	NFT_AST_OP_XOR,
+};
+
+/**
+ *	struct nft_ast_expr - nf_tables delinearized expression
+ *
+ *	@type: expression type
+ *	@op: type of operation
+ *	@len: length of expression
+ */
+struct nft_ast_expr {
+	enum nft_ast_expr_type		type;
+	enum nft_ast_expr_ops		op;
+	u32				len;
+	union {
+		struct {
+			struct nft_data		data;
+		} value;
+		struct {
+			enum nft_meta_keys	key;
+		} meta;
+		struct {
+			enum nft_payload_bases	base;
+			u32			offset;
+		} payload;
+		struct {
+			struct nft_ast_expr	*left;
+			struct nft_ast_expr	*right;
+		} relational;
+	};
+};
+
+struct nft_ast_expr *nft_ast_expr_alloc(enum nft_ast_expr_type type);
+void nft_ast_expr_destroy(struct nft_ast_expr *expr);
+
+enum nft_ast_stmt_type {
+	NFT_AST_STMT_EXPR		= 0,
+};
+
+/**
+ *	struct nft_ast_stmt - nf_tables delinearized statement
+ *
+ *	@type: statement type
+ */
+struct nft_ast_stmt {
+	struct list_head			list;
+
+	enum nft_ast_stmt_type			type;
+	union {
+		struct nft_ast_expr		*expr;
+	};
+};
+
+struct nft_ast_stmt *nft_ast_stmt_alloc(enum nft_ast_stmt_type type);
+void nft_ast_stmt_list_release(struct list_head *ast_stmt_list);
+
+void nft_ast_stmt_list_print(struct list_head *stmt_list);
+
+int nft_delinearize(struct list_head *ast_stmt_list, struct nft_rule *rule);
+
+#endif
diff --git a/net/netfilter/Makefile b/net/netfilter/Makefile
index 5d9b8b959e58..8b0006e3ae6f 100644
--- a/net/netfilter/Makefile
+++ b/net/netfilter/Makefile
@@ -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
diff --git a/net/netfilter/nf_tables_jit.c b/net/netfilter/nf_tables_jit.c
new file mode 100644
index 000000000000..e971b94bbc69
--- /dev/null
+++ b/net/netfilter/nf_tables_jit.c
@@ -0,0 +1,136 @@
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/netfilter.h>
+#include <net/netfilter/nf_tables.h>
+#include <net/netfilter/nf_tables_jit.h>
+
+struct nft_ast_expr *nft_ast_expr_alloc(enum nft_ast_expr_type type)
+{
+	struct nft_ast_expr *expr;
+
+	expr = kmalloc(sizeof(struct nft_ast_expr), GFP_KERNEL);
+	if (expr == NULL)
+		return NULL;
+
+	expr->type = type;
+	expr->op   = NFT_AST_OP_INVALID;
+
+	return expr;
+}
+EXPORT_SYMBOL_GPL(nft_ast_expr_alloc);
+
+void nft_ast_expr_destroy(struct nft_ast_expr *expr)
+{
+	switch (expr->type) {
+	case NFT_AST_EXPR_VALUE:
+	case NFT_AST_EXPR_META:
+	case NFT_AST_EXPR_PAYLOAD:
+		kfree(expr);
+		break;
+	case NFT_AST_EXPR_RELATIONAL:
+		nft_ast_expr_destroy(expr->relational.left);
+		nft_ast_expr_destroy(expr->relational.right);
+		break;
+	default:
+		WARN_ONCE(1, "Unknown expr %u at destroy\n", expr->type);
+	}
+}
+EXPORT_SYMBOL_GPL(nft_ast_expr_destroy);
+
+struct nft_ast_stmt *nft_ast_stmt_alloc(enum nft_ast_stmt_type type)
+{
+	struct nft_ast_stmt *stmt;
+
+	stmt = kmalloc(sizeof(struct nft_ast_stmt), GFP_KERNEL);
+	if (stmt == NULL)
+		return NULL;
+
+	stmt->type = type;
+	return stmt;
+}
+EXPORT_SYMBOL_GPL(nft_ast_stmt_alloc);
+
+static void nft_ast_stmt_free(struct nft_ast_stmt *stmt)
+{
+	nft_ast_expr_destroy(stmt->expr);
+	kfree(stmt);
+}
+
+void nft_ast_stmt_list_release(struct list_head *ast_stmt_list)
+{
+	struct nft_ast_stmt *stmt, *next;
+
+	list_for_each_entry_safe(stmt, next, ast_stmt_list, list) {
+		list_del(&stmt->list);
+		nft_ast_stmt_free(stmt);
+	}
+}
+EXPORT_SYMBOL_GPL(nft_ast_stmt_list_release);
+
+int nft_delinearize(struct list_head *ast_stmt_list, struct nft_rule *rule)
+{
+	struct nft_ast_expr *regs[NFT_REG32_15 + 1];
+	struct nft_expr *expr;
+	int err;
+
+	expr = nft_expr_first(rule);
+	while (expr->ops && expr != nft_expr_last(rule)) {
+		if (!expr->ops->delinearize)
+			return -EOPNOTSUPP;
+
+		err = expr->ops->delinearize(regs, expr, ast_stmt_list);
+		if (err < 0)
+			return err;
+
+		expr = nft_expr_next(expr);
+	}
+	return 0;
+}
+EXPORT_SYMBOL_GPL(nft_delinearize);
+
+/* TODO use pr_debug() here. */
+static void nft_ast_expr_print(struct nft_ast_expr *expr)
+{
+	pr_info("expr type %u len %u\n", expr->type, expr->len);
+
+	switch (expr->type) {
+	case NFT_AST_EXPR_VALUE:
+		pr_info("value %x %x %x %x\n",
+			expr->value.data.data[0], expr->value.data.data[1],
+			expr->value.data.data[1], expr->value.data.data[2]);
+	        break;
+	case NFT_AST_EXPR_META:
+		pr_info("meta key %u\n", expr->meta.key);
+		break;
+	case NFT_AST_EXPR_PAYLOAD:
+		pr_info("payload base %u offset %u\n",
+			expr->payload.base, expr->payload.offset);
+	break;
+	case NFT_AST_EXPR_RELATIONAL:
+		pr_info("relational\n");
+		pr_info("       left %p\n", expr->relational.left);
+		nft_ast_expr_print(expr->relational.left);
+		pr_info("       right %p\n", expr->relational.right);
+		nft_ast_expr_print(expr->relational.right);
+		break;
+	default:
+		pr_info("UNKNOWN\n");
+		break;
+	}
+}
+
+void nft_ast_stmt_list_print(struct list_head *stmt_list)
+{
+	struct nft_ast_stmt *stmt;
+
+	list_for_each_entry(stmt, stmt_list, list) {
+		pr_info("stmt %u\n", stmt->type);
+
+		switch (stmt->type) {
+		case NFT_AST_STMT_EXPR:
+			nft_ast_expr_print(stmt->expr);
+			break;
+		}
+	}
+}
+EXPORT_SYMBOL_GPL(nft_ast_stmt_list_print);
diff --git a/net/netfilter/nft_cmp.c b/net/netfilter/nft_cmp.c
index fa90a8402845..d994a9e0392e 100644
--- a/net/netfilter/nft_cmp.c
+++ b/net/netfilter/nft_cmp.c
@@ -16,6 +16,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>
 
 struct nft_cmp_expr {
 	struct nft_data		data;
@@ -109,12 +110,78 @@ static int nft_cmp_dump(struct sk_buff *skb, const struct nft_expr *expr)
 	return -1;
 }
 
+static enum nft_ast_expr_ops nft_cmp_to_ops[NFT_CMP_GTE + 1] = {
+	[NFT_CMP_EQ]	= NFT_AST_OP_EQ,
+	[NFT_CMP_NEQ]	= NFT_AST_OP_NEQ,
+	[NFT_CMP_LT]	= NFT_AST_OP_LT,
+	[NFT_CMP_LTE]	= NFT_AST_OP_LTE,
+	[NFT_CMP_GT]	= NFT_AST_OP_GT,
+	[NFT_CMP_GTE]	= NFT_AST_OP_GTE,
+};
+
+static int nft_ast_expr_cmp_op(enum nft_cmp_ops op)
+{
+	BUG_ON(op > NFT_CMP_GTE + 1);
+
+	return nft_cmp_to_ops[op];
+}
+
+static int __nft_cmp_delinearize(struct nft_ast_expr **regs,
+				 const struct nft_cmp_expr *priv,
+				 struct list_head *stmt_list)
+{
+	struct nft_ast_expr *right, *tree;
+	struct nft_ast_stmt *stmt;
+	int err;
+
+	if (regs[priv->sreg] == NULL)
+		return -EINVAL;
+
+	right = nft_ast_expr_alloc(NFT_AST_EXPR_VALUE);
+	if (right == NULL)
+		return -ENOMEM;
+
+	right->value.data = priv->data;
+	right->len = priv->len;
+
+	err = -ENOMEM;
+	tree = nft_ast_expr_alloc(NFT_AST_EXPR_RELATIONAL);
+	if (tree == NULL)
+		goto err1;
+
+	tree->op = nft_ast_expr_cmp_op(priv->op);
+	tree->relational.left = regs[priv->sreg];
+	tree->relational.right = right;
+	tree->len = tree->relational.left->len;
+
+	stmt = nft_ast_stmt_alloc(NFT_AST_STMT_EXPR);
+	if (stmt == NULL)
+		goto err2;
+
+	stmt->expr = tree;
+	list_add_tail(&stmt->list, stmt_list);
+	return 0;
+err2:
+	nft_ast_expr_destroy(tree);
+err1:
+	nft_ast_expr_destroy(right);
+	return err;
+}
+
+static int nft_cmp_delinearize(struct nft_ast_expr **regs,
+			       const struct nft_expr *expr,
+			       struct list_head *stmt_list)
+{
+	return __nft_cmp_delinearize(regs, nft_expr_priv(expr), stmt_list);
+}
+
 static const struct nft_expr_ops nft_cmp_ops = {
 	.type		= &nft_cmp_type,
 	.size		= NFT_EXPR_SIZE(sizeof(struct nft_cmp_expr)),
 	.eval		= nft_cmp_eval,
 	.init		= nft_cmp_init,
 	.dump		= nft_cmp_dump,
+	.delinearize	= nft_cmp_delinearize,
 };
 
 static int nft_cmp_fast_init(const struct nft_ctx *ctx,
@@ -164,12 +231,32 @@ static int nft_cmp_fast_dump(struct sk_buff *skb, const struct nft_expr *expr)
 	return -1;
 }
 
+static int nft_cmp_fast_delinearize(struct nft_ast_expr **regs,
+				    const struct nft_expr *expr,
+				    struct list_head *stmt_list)
+{
+	const struct nft_cmp_fast_expr *priv = nft_expr_priv(expr);
+	struct nft_cmp_expr cmp = {
+		.data   = {
+			.data   = {
+				[0] = priv->data,
+			},
+		},
+		.sreg   = priv->sreg,
+		.len    = priv->len,
+		.op     = NFT_AST_OP_EQ,
+	};
+
+	return __nft_cmp_delinearize(regs, &cmp, stmt_list);
+}
+
 const struct nft_expr_ops nft_cmp_fast_ops = {
 	.type		= &nft_cmp_type,
 	.size		= NFT_EXPR_SIZE(sizeof(struct nft_cmp_fast_expr)),
 	.eval		= NULL,	/* inlined */
 	.init		= nft_cmp_fast_init,
 	.dump		= nft_cmp_fast_dump,
+	.delinearize	= nft_cmp_fast_delinearize,
 };
 
 static const struct nft_expr_ops *
diff --git a/net/netfilter/nft_meta.c b/net/netfilter/nft_meta.c
index 8fb91940e2e7..920434a9470c 100644
--- a/net/netfilter/nft_meta.c
+++ b/net/netfilter/nft_meta.c
@@ -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 = {
diff --git a/net/netfilter/nft_payload.c b/net/netfilter/nft_payload.c
index e110b0ebbf58..0d3b065b701d 100644
--- a/net/netfilter/nft_payload.c
+++ b/net/netfilter/nft_payload.c
@@ -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)
-- 
2.11.0

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

[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);
};

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/net/netfilter/nf_tables_jit.h | 39 +++++++++++++++++++
 net/netfilter/nf_tables_jit.c         | 71 +++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)

diff --git a/include/net/netfilter/nf_tables_jit.h b/include/net/netfilter/nf_tables_jit.h
index 124d3da91b0d..dff3af7ad420 100644
--- a/include/net/netfilter/nf_tables_jit.h
+++ b/include/net/netfilter/nf_tables_jit.h
@@ -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
diff --git a/net/netfilter/nf_tables_jit.c b/net/netfilter/nf_tables_jit.c
index e971b94bbc69..63673ea42be8 100644
--- a/net/netfilter/nf_tables_jit.c
+++ b/net/netfilter/nf_tables_jit.c
@@ -134,3 +134,74 @@ void nft_ast_stmt_list_print(struct list_head *stmt_list)
 	}
 }
 EXPORT_SYMBOL_GPL(nft_ast_stmt_list_print);
+
+struct nft_ast_xfrm_state {
+	const struct nft_ast_xfrm_desc *xfrm_desc;
+	void *data;
+};
+
+static int nft_ast_xfrm_relational(const struct nft_ast_expr *dlexpr,
+				   struct nft_ast_xfrm_state *state)
+{
+	const struct nft_ast_expr *left = dlexpr->relational.left;
+	const struct nft_ast_expr *right = dlexpr->relational.right;
+	const struct nft_ast_xfrm_desc *xfrm_desc = state->xfrm_desc;
+	int err;
+
+	if (right->type != NFT_AST_EXPR_VALUE)
+		return -EOPNOTSUPP;
+
+	switch (left->type) {
+	case NFT_AST_EXPR_META:
+		err = xfrm_desc->meta_desc->xfrm(dlexpr, state, state->data);
+		break;
+	case NFT_AST_EXPR_PAYLOAD:
+		err = xfrm_desc->proto_desc->xfrm(dlexpr, state, state->data);
+		break;
+	default:
+		return -EOPNOTSUPP;
+	}
+
+	return err;
+}
+
+static int nft_ast_xfrm_expr(const struct nft_ast_expr *dlexpr,
+			     struct nft_ast_xfrm_state *state)
+{
+	int err;
+
+	switch (dlexpr->type) {
+	case NFT_AST_EXPR_RELATIONAL:
+		err = nft_ast_xfrm_relational(dlexpr, state);
+		break;
+	default:
+		return -EOPNOTSUPP;
+	}
+
+	return err;
+}
+
+int nft_ast_xfrm(const struct list_head *ast_stmt_list,
+		 const struct nft_ast_xfrm_desc *xfrm_desc, void *data)
+{
+	struct nft_ast_xfrm_state state = {
+		.xfrm_desc	= xfrm_desc,
+		.data		= data,
+	};
+	struct nft_ast_stmt *stmt;
+	int err = 0;
+
+	list_for_each_entry(stmt, ast_stmt_list, list) {
+		switch (stmt->type) {
+		case NFT_AST_STMT_EXPR:
+			err = nft_ast_xfrm_expr(stmt->expr, &state);
+			if (err < 0)
+				return err;
+			break;
+		default:
+			return -EOPNOTSUPP;
+		}
+	}
+	return err;
+}
+EXPORT_SYMBOL_GPL(nft_ast_xfrm);
-- 
2.11.0

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

[Pablo Neira Ayuso]

>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.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 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

diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h
index 8a6406f3811f..09a2faceee91 100644
--- a/include/net/netfilter/nf_tables.h
+++ b/include/net/netfilter/nf_tables.h
@@ -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;
diff --git a/include/net/netfilter/nf_tables_jit.h b/include/net/netfilter/nf_tables_jit.h
index dff3af7ad420..5309a45a6dc2 100644
--- a/include/net/netfilter/nf_tables_jit.h
+++ b/include/net/netfilter/nf_tables_jit.h
@@ -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
diff --git a/net/ipv4/netfilter/nf_tables_ipv4.c b/net/ipv4/netfilter/nf_tables_ipv4.c
index 96f955496d5f..4cb872f3e5a4 100644
--- a/net/ipv4/netfilter/nf_tables_ipv4.c
+++ b/net/ipv4/netfilter/nf_tables_ipv4.c
@@ -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 = {
diff --git a/net/netfilter/Makefile b/net/netfilter/Makefile
index 8b0006e3ae6f..6bd2bcbaa74c 100644
--- a/net/netfilter/Makefile
+++ b/net/netfilter/Makefile
@@ -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
diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
index 8b9fe30de0cd..4746631a5e9d 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -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);
diff --git a/net/netfilter/nf_tables_bpf.c b/net/netfilter/nf_tables_bpf.c
new file mode 100644
index 000000000000..3bc5de5ab763
--- /dev/null
+++ b/net/netfilter/nf_tables_bpf.c
@@ -0,0 +1,92 @@
+#include <linux/types.h>
+#include <linux/filter.h>
+#include <net/netfilter/nf_tables.h>
+#include <net/netfilter/nf_tables_jit.h>
+
+#define NFT_EMIT(jit, __insn)					\
+	jit->insn[jit->len] = (struct sock_filter) __insn;	\
+	jit->len++;						\
+
+static int nft_jit_bpf_payload_xfrm(const struct nft_ast_expr *expr,
+				    struct nft_ast_xfrm_state *state,
+				    void *data)
+{
+	struct nft_ast_expr *right = expr->relational.right;
+	struct nft_ast_expr *left = expr->relational.left;
+	struct nft_rule_jit *jit = data;
+	unsigned int size;
+	unsigned int k;
+
+	pr_info("> match payload at offset %u base %u len %u\n",
+		left->payload.offset, left->payload.base, left->len);
+
+	switch (left->len) {
+	case 1:
+		size = BPF_B;
+		k = right->value.data.data[0];
+		break;
+	case 2:
+		size = BPF_H;
+		k = ntohs(right->value.data.data[0]);
+		break;
+	case 4:
+		size = BPF_W;
+		k = ntohl(right->value.data.data[0]);
+		break;
+	default:
+		return -EOPNOTSUPP;
+	}
+
+	NFT_EMIT(jit, BPF_STMT(BPF_LD | size | BPF_ABS, left->payload.offset));
+	NFT_EMIT(jit, BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, k, 0, 1));
+	NFT_EMIT(jit, BPF_STMT(BPF_RET | BPF_K, NF_DROP));
+	NFT_EMIT(jit, BPF_STMT(BPF_RET | BPF_K, NF_ACCEPT));
+
+	return 0;
+}
+
+static const struct nft_ast_proto_desc nft_jit_bpf_payload_desc = {
+	.xfrm		= nft_jit_bpf_payload_xfrm,
+};
+
+static int nft_jit_bpf_meta_xfrm(const struct nft_ast_expr *expr,
+				 struct nft_ast_xfrm_state *state, void *data)
+{
+	struct nft_ast_expr *right = expr->relational.right;
+	struct nft_ast_expr *left = expr->relational.left;
+	struct nft_rule_jit *jit = data;
+	unsigned int ad;
+
+	pr_info("> generate meta match\n");
+
+	switch (left->meta.key) {
+	case NFT_META_PROTOCOL:
+		pr_info("meta protocol\n");
+		ad = SKF_AD_PROTOCOL;
+		break;
+		break;
+	case NFT_META_IIF:
+		pr_info("meta iif\n");
+		ad = SKF_AD_IFINDEX;
+		break;
+	default:
+		return -EOPNOTSUPP;
+	}
+
+	NFT_EMIT(jit, BPF_STMT(BPF_LD | BPF_W | BPF_ABS, SKF_AD_OFF + ad));
+	NFT_EMIT(jit, BPF_JUMP(BPF_JMP | BPF_JEQ,
+			       right->value.data.data[0], 0, 1));
+	NFT_EMIT(jit, BPF_STMT(BPF_RET | BPF_K, NF_DROP));
+	NFT_EMIT(jit, BPF_STMT(BPF_RET | BPF_K, NF_ACCEPT));
+
+	return 0;
+}
+
+static const struct nft_ast_meta_desc nft_jit_bpf_meta_desc = {
+	.xfrm		= nft_jit_bpf_meta_xfrm,
+};
+
+struct nft_ast_xfrm_desc nft_jit_bpf_xfrm_desc = {
+	.proto_desc	= &nft_jit_bpf_payload_desc,
+	.meta_desc	= &nft_jit_bpf_meta_desc,
+};
diff --git a/net/netfilter/nf_tables_jit.c b/net/netfilter/nf_tables_jit.c
index 63673ea42be8..40d2b380d313 100644
--- a/net/netfilter/nf_tables_jit.c
+++ b/net/netfilter/nf_tables_jit.c
@@ -1,6 +1,7 @@
 #include <linux/init.h>
 #include <linux/module.h>
 #include <linux/netfilter.h>
+#include <linux/filter.h>
 #include <net/netfilter/nf_tables.h>
 #include <net/netfilter/nf_tables_jit.h>
 
@@ -205,3 +206,134 @@ int nft_ast_xfrm(const struct list_head *ast_stmt_list,
 	return err;
 }
 EXPORT_SYMBOL_GPL(nft_ast_xfrm);
+
+int nft_jit_rule(struct nft_rule *rule,
+		 const struct nft_ast_xfrm_desc *xfrm_desc)
+{
+	LIST_HEAD(stmt_list);
+	int err;
+
+	err = nft_delinearize(&stmt_list, rule);
+	if (err < 0)
+		return err;
+
+	err = nft_ast_xfrm(&stmt_list, xfrm_desc, &rule->jit);
+	if (err < 0)
+		return err;
+
+	/* TODO: Remove this, just here to print result of delinearization. */
+	nft_ast_stmt_list_print(&stmt_list);
+
+	nft_ast_stmt_list_release(&stmt_list);
+
+	return err;
+}
+
+void nft_jit_emit_basechain_policy(struct sock_fprog_kern *prog,
+				   unsigned int verdict)
+{
+	struct sock_filter ret = BPF_STMT(BPF_RET | BPF_K, verdict);
+
+	prog->filter[prog->len] = ret;
+	prog->len++;
+}
+
+static void nft_jit_rule_add(struct sock_fprog_kern *prog,
+			     const struct nft_rule_jit *jit)
+{
+	memcpy(&prog->filter[prog->len], jit->insn,
+	       jit->len * sizeof(struct sock_filter));
+	prog->len += jit->len;
+}
+
+int nft_jit_prepare(struct net *net)
+{
+	struct nft_base_chain *basechain;
+	struct sock_fprog_kern prog;
+	struct sock_filter *filter;
+	struct nft_table *table;
+	struct nft_chain *chain;
+	struct nft_rule *rule;
+	unsigned int len = 1;
+	struct bpf_prog *fp;
+
+	list_for_each_entry(table, &net->nft.tables, list) {
+		list_for_each_entry(chain, &table->chains, list) {
+			if (!nft_is_base_chain(chain))
+				continue;
+
+			basechain = nft_base_chain(chain);
+
+			list_for_each_entry(rule, &chain->rules, list) {
+				if (!nft_is_active_next(net, rule))
+					continue;
+
+				len += rule->jit.len;
+			}
+
+			filter = kmalloc(len * sizeof(*filter), GFP_KERNEL);
+			if (!filter)
+				return -ENOMEM;
+
+			prog.filter = filter;
+			prog.len = 0;
+
+			list_for_each_entry(rule, &chain->rules, list) {
+				if (!nft_is_active_next(net, rule))
+					continue;
+
+				nft_jit_rule_add(&prog, &rule->jit);
+			}
+
+			nft_jit_emit_basechain_policy(&prog, basechain->policy);
+
+			if (bpf_prog_create(&fp, &prog)) {
+				kfree(filter);
+				return -ENOMEM;
+			}
+
+			kfree(filter);
+			nft_base_chain(chain)->fp_stash = fp;
+		}
+	}
+
+	return 0;
+}
+
+void nft_jit_commit(struct net *net)
+{
+	struct nft_base_chain *basechain;
+	struct nft_table *table;
+	struct nft_chain *chain;
+	struct bpf_prog *old_fp;
+
+	list_for_each_entry(table, &net->nft.tables, list) {
+		list_for_each_entry(chain, &table->chains, list) {
+			if (!nft_is_base_chain(chain))
+				continue;
+
+			basechain = nft_base_chain(chain);
+			old_fp = basechain->fp;
+			rcu_assign_pointer(basechain->fp, basechain->fp_stash);
+			basechain->fp_stash = old_fp;
+		}
+	}
+}
+
+void nft_jit_release(struct net *net)
+{
+	struct nft_base_chain *basechain;
+	struct nft_table *table;
+	struct nft_chain *chain;
+
+	list_for_each_entry(table, &net->nft.tables, list) {
+		list_for_each_entry(chain, &table->chains, list) {
+			if (!nft_is_base_chain(chain))
+				continue;
+
+			basechain = nft_base_chain(chain);
+			bpf_prog_free(basechain->fp_stash);
+			basechain->fp_stash = NULL;
+		}
+	}
+}
-- 
2.11.0

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

[David Miller]

From: Pablo Neira Ayuso <pablo@netfilter.org>
Date: Mon, 19 Feb 2018 17:37:06 +0100

> 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.
> 
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

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.

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Daniel Borkmann]

On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
[...]
> * 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

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

[Pablo Neira Ayuso]

Hi David,

On Mon, Feb 19, 2018 at 01:53:34PM -0500, David Miller wrote:
> 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!

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Pablo Neira Ayuso]

Hi Daniel,

On Mon, Feb 19, 2018 at 08:57:39PM +0100, Daniel Borkmann wrote:
> On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
> [...]
> > * 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.

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.

> 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.

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Daniel Borkmann]

Hi Pablo,

On 02/20/2018 11:58 AM, Pablo Neira Ayuso wrote:
> On Mon, Feb 19, 2018 at 08:57:39PM +0100, Daniel Borkmann wrote:
>> On 02/19/2018 05:37 PM, Pablo Neira Ayuso wrote:
>> [...]
>>> * 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.
> 
> 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

>> 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

> 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.
> 

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

[Alexei Starovoitov]

On Tue, Feb 20, 2018 at 11:53:55AM +0100, Pablo Neira Ayuso wrote:
> Hi David,
> 
> On Mon, Feb 19, 2018 at 01:53:34PM -0500, David Miller wrote:
> > 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.

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

[Pablo Neira Ayuso]

Hi Alexei,

On Tue, Feb 20, 2018 at 06:01:39PM -0800, Alexei Starovoitov wrote:
> On Tue, Feb 20, 2018 at 11:53:55AM +0100, Pablo Neira Ayuso wrote:
> > 
> > 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!

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Jakub Kicinski]

On Tue, 20 Feb 2018 11:58:22 +0100, Pablo Neira Ayuso wrote:
> 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.

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Florian Fainelli]

On 02/21/2018 03:46 PM, Jakub Kicinski wrote:
> On Tue, 20 Feb 2018 11:58:22 +0100, Pablo Neira Ayuso wrote:
>> 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.
> 

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>
-- 
Florian

Re: [PATCH RFC PoC 0/3] nftables meets bpf

[Jakub Kicinski]

On Wed, 21 Feb 2018 16:30:07 -0800, Florian Fainelli wrote:
> On 02/21/2018 03:46 PM, Jakub Kicinski wrote:
> > On Tue, 20 Feb 2018 11:58:22 +0100, Pablo Neira Ayuso wrote:  
> >> 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.
> 
> 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 :)

> 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...

> - 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!

> - 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.

> - 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.

> </rant>