[PATCH bpf-next v3 13/16] bpfilter: add table code generation

[Quentin Deslandes]

Table code generation consists of multiple steps:
  1) Find front and last rules for the supplied table and hook.
  2) Try to generate code for each rule in [front rule; last rule].
  3) Try to generate each remaining subprog by its type.

Co-developed-by: Dmitrii Banshchikov <me@xxxxxxxxxxxxx>
Signed-off-by: Dmitrii Banshchikov <me@xxxxxxxxxxxxx>
Signed-off-by: Quentin Deslandes <qde@xxxxxxxx>
---
 net/bpfilter/codegen.c | 359 +++++++++++++++++++++++++++++++++++++++++
 net/bpfilter/codegen.h |   2 +
 2 files changed, 361 insertions(+)

diff --git a/net/bpfilter/codegen.c b/net/bpfilter/codegen.c
index e7ae7dfa5118..db0a20b378b5 100644
--- a/net/bpfilter/codegen.c
+++ b/net/bpfilter/codegen.c
@@ -4,15 +4,22 @@
  * Copyright (c) 2022 Meta Platforms, Inc. and affiliates.
  */
 
+#define _GNU_SOURCE
+
 #include "codegen.h"
 
 #include "../../include/uapi/linux/bpfilter.h"
 
+#include <linux/if_ether.h>
+#include <linux/ip.h>
 #include <linux/pkt_cls.h>
 
+#include <bpf/bpf_endian.h>
+
 #include <unistd.h>
 #include <sys/syscall.h>
 
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -20,6 +27,8 @@
 #include <bpf/libbpf.h>
 
 #include "logger.h"
+#include "rule.h"
+#include "table.h"
 
 enum fixup_insn_type {
 	FIXUP_INSN_OFF,
@@ -53,6 +62,65 @@ static int subprog_desc_comparator(const void *x, const void *y)
 	return -1;
 }
 
+/**
+ * codegen_inline_memset_zero_64() - Generate eBPF bytecode to initialise a
+ *	contiguous memory area with 0.
+ * @ctx: codegen context.
+ * @addr_reg: register containing the address of the memory area to initialise.
+ *	The caller need to initialise the register properly before calling this
+ *	function.
+ * @size: size of the memory area. As this function initialises 64 bits at a
+ *	time, @size needs to be a multiple of 64 bits. If it doesn't, the
+ *	function return without intialising the memory and an error message is
+ *	printed out.
+ *
+ * Return: 0 on success, negative errno value on error.
+ */
+static int codegen_inline_memset_zero_64(struct codegen *ctx, int reg,
+					 size_t size)
+{
+	if (size % 8) {
+		BFLOG_ERR("codegen_memset_zero_64() called with size %ld, size must be a multiple of 8",
+			  size);
+		return -EINVAL;
+	}
+
+	for (size_t i = 0; i * 8 < size; ++i)
+		EMIT(ctx, BPF_ST_MEM(BPF_DW, reg, i * 8, 0));
+
+	return 0;
+}
+
+static int codegen_push_subprog(struct codegen *codegen,
+				struct codegen_subprog_desc *subprog)
+{
+	// TODO: merge this with codegen_fixup_push.
+
+	if (codegen->subprogs_cur == codegen->subprogs_max) {
+		struct codegen_subprog_desc **subprogs;
+		uint16_t subprogs_max;
+
+		subprogs_max = codegen->subprogs_cur ?
+			       2 * codegen->subprogs_cur : 1;
+		subprogs = reallocarray(codegen->subprogs, subprogs_max,
+					sizeof(codegen->subprogs[0]));
+		if (!subprogs) {
+			BFLOG_ERR("out of memory");
+			return -ENOMEM;
+		}
+
+		codegen->subprogs_max = subprogs_max;
+		codegen->subprogs = subprogs;
+	}
+
+	codegen->subprogs[codegen->subprogs_cur++] = subprog;
+
+	qsort(codegen->subprogs, codegen->subprogs_cur,
+	      sizeof(codegen->subprogs[0]), subprog_desc_comparator);
+
+	return 0;
+}
+
 static const struct codegen_subprog_desc *codegen_find_subprog(struct codegen *codegen,
 							       const struct codegen_subprog_desc **subprog)
 {
@@ -601,6 +669,297 @@ int create_codegen(struct codegen *codegen, enum bpf_prog_type type)
 	return r;
 }
 
+static int try_codegen_rules(struct codegen *codegen, struct rule *rule_front,
+			     struct rule *rule_last)
+{
+	int r;
+
+	for (; rule_front <= rule_last; ++rule_front, ++codegen->rule_index) {
+		rule_front->index = codegen->rule_index;
+		r = gen_inline_rule(codegen, rule_front);
+		if (r) {
+			BFLOG_ERR("failed to generate inline rule: %s",
+				  STRERR(r));
+			return r;
+		}
+
+		r = codegen_fixup(codegen, CODEGEN_FIXUP_NEXT_RULE);
+		if (r) {
+			BFLOG_ERR("failed to generate next rule fixups: %s",
+				  STRERR(r));
+			return r;
+		}
+
+		r = codegen_fixup(codegen, CODEGEN_FIXUP_COUNTERS_INDEX);
+		if (r) {
+			BFLOG_ERR("failed to generate counters fixups: %s",
+				  STRERR(r));
+			return r;
+		}
+	}
+
+	r = codegen_fixup(codegen, CODEGEN_FIXUP_END_OF_CHAIN);
+	if (r) {
+		BFLOG_ERR("failed to generate end of chain fixups: %s",
+			  STRERR(r));
+		return r;
+	}
+
+	return 0;
+}
+
+static struct rule *table_find_last_rule(const struct table *table,
+					 struct rule *rule_front)
+{
+	for (; rule_front; ++rule_front) {
+		if (!rule_is_unconditional(rule_front))
+			continue;
+
+		if (!rule_has_standard_target(rule_front))
+			continue;
+
+		if (standard_target_verdict(rule_front->target.ipt_target) >= 0)
+			continue;
+
+		return rule_front;
+	}
+
+	return rule_front;
+}
+
+static int try_codegen_user_chain_subprog(struct codegen *codegen,
+					  const struct table *table,
+					  struct codegen_subprog_desc *subprog)
+{
+	struct rule *rule_front;
+	struct rule *rule_last;
+	int r;
+
+	rule_front = table_find_rule_by_offset(table, subprog->offset);
+	if (!rule_front) {
+		BFLOG_ERR("failed to get rule at offset %d", subprog->offset);
+		return -EINVAL;
+	}
+
+	rule_last = table_find_last_rule(table, rule_front);
+	if (!rule_last) {
+		BFLOG_ERR("failed to find last rule");
+		return -EINVAL;
+	}
+
+	subprog->insn = codegen->len_cur;
+	codegen->rule_index = rule_front - table->rules;
+	r = try_codegen_rules(codegen, rule_front, rule_last);
+	if (r) {
+		BFLOG_ERR("failed to generate rules");
+		return r;
+	}
+
+	return codegen_push_subprog(codegen, subprog);
+}
+
+static int try_codegen_subprogs(struct codegen *codegen, const struct table *table)
+{
+	while (!list_empty(&codegen->awaiting_subprogs)) {
+		struct codegen_subprog_desc *subprog;
+		int r = -EINVAL;
+
+		subprog = list_entry(codegen->awaiting_subprogs.next,
+				     struct codegen_subprog_desc,
+				     list);
+
+		if (subprog->type == CODEGEN_SUBPROG_USER_CHAIN) {
+			r = try_codegen_user_chain_subprog(codegen, table,
+							   subprog);
+			if (r < 0) {
+				BFLOG_ERR("failed to generate code for user defined chain: %s",
+					  STRERR(r));
+				return r;
+			}
+		} else {
+			BFLOG_ERR("code generation for subprogram of type %d is not supported",
+				  subprog->type);
+			return -EINVAL;
+		}
+
+		list_del(&subprog->list);
+	}
+
+	return 0;
+}
+
+/**
+ * generate_inline_forward_packet_assessment() - Add eBPF bytecode to assess
+ *	whether the current packet is to be forwarded or not.
+ * @ctx: context to add the bytecode to.
+ *
+ * Use bpf_fib_lookup() to find out whether the current packet is to be
+ * forwarded or not. bpf_fib_lookup() requires a struct bpf_fib_lookup to be
+ * filled with data from the packet.
+ * The outcome of the bytecode will depend on the actual iptables hook used:
+ * BPFILTER_INET_HOOK_FORWARD's chain will be processed if the packet is to be
+ * forwarded, or will be skipped otherwise and jump to the next chain. The
+ * opposite behaviour apply if hook is BPFILTER_INET_HOOK_LOCAL_IN.
+ *
+ * Return: 0 on success, negative errno value on error.
+ */
+static int generate_inline_forward_packet_assessment(struct codegen *ctx)
+{
+	// Set ARG2 to contain the address of the struct bpf_fib_lookup.
+	EMIT(ctx, BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_10));
+	EMIT(ctx, BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2,
+				(-(unsigned int)sizeof(struct bpf_fib_lookup)) - sizeof(struct runtime_context)));
+
+	codegen_inline_memset_zero_64(ctx, BPF_REG_ARG2,
+				      sizeof(struct bpf_fib_lookup));
+
+	// Store h_proto for further decision
+	EMIT(ctx, BPF_LDX_MEM(BPF_H, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      -(short int)(ETH_HLEN) + (short int)offsetof(struct ethhdr, h_proto)));
+	EMIT(ctx, BPF_JMP_IMM(BPF_JEQ, CODEGEN_REG_SCRATCH3,
+			      bpf_htons(ETH_P_IP), 2));
+
+	// Not IPv4? Then do no process any FORWARD rule and move to the next chain (program).
+	EMIT(ctx, BPF_MOV64_IMM(CODEGEN_REG_RETVAL, TC_ACT_UNSPEC));
+	EMIT_FIXUP(ctx, CODEGEN_FIXUP_END_OF_CHAIN, BPF_JMP_A(0));
+
+	// bpf_fib_lookup.family field
+	EMIT(ctx, BPF_ST_MEM(BPF_B, BPF_REG_ARG2,
+			     offsetof(struct bpf_fib_lookup, family), AF_INET));
+
+	// bpf_fib_lookup.l4_protocol field
+	EMIT(ctx, BPF_LDX_MEM(BPF_B, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      offsetof(struct iphdr, protocol)));
+	EMIT(ctx, BPF_STX_MEM(BPF_B, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, l4_protocol)));
+
+	// bpf_fib_lookup.tot_len field
+	EMIT(ctx, BPF_LDX_MEM(BPF_H, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      offsetof(struct iphdr, tot_len)));
+	EMIT(ctx, BPF_STX_MEM(BPF_H, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, tot_len)));
+
+	// bpf_fib_lookup.ifindex field
+	EMIT(ctx, BPF_LDX_MEM(BPF_W, CODEGEN_REG_SCRATCH3, CODEGEN_REG_CTX,
+			      offsetof(struct __sk_buff, ingress_ifindex)));
+	EMIT(ctx, BPF_STX_MEM(BPF_W, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, ifindex)));
+
+	// bpf_fib_lookup.tos field
+	EMIT(ctx, BPF_LDX_MEM(BPF_B, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      offsetof(struct iphdr, tos)));
+	EMIT(ctx, BPF_STX_MEM(BPF_B, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, tos)));
+
+	// bpf_fib_lookup.ipv4_src and bpf_fib_lookup.ipv4_dst fields
+	EMIT(ctx, BPF_LDX_MEM(BPF_W, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      offsetof(struct iphdr, saddr)));
+	EMIT(ctx, BPF_STX_MEM(BPF_W, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, ipv4_src)));
+	EMIT(ctx, BPF_LDX_MEM(BPF_W, CODEGEN_REG_SCRATCH3, CODEGEN_REG_L3,
+			      offsetof(struct iphdr, daddr)));
+	EMIT(ctx, BPF_STX_MEM(BPF_W, BPF_REG_ARG2, CODEGEN_REG_SCRATCH3,
+			      offsetof(struct bpf_fib_lookup, ipv4_dst)));
+
+	EMIT(ctx, BPF_MOV64_REG(BPF_REG_ARG1, CODEGEN_REG_CTX));
+	EMIT(ctx, BPF_MOV64_IMM(BPF_REG_ARG3, sizeof(struct bpf_fib_lookup)));
+	EMIT(ctx, BPF_MOV64_IMM(BPF_REG_ARG4, 0));
+
+	EMIT(ctx, BPF_EMIT_CALL(BPF_FUNC_fib_lookup));
+	EMIT(ctx, BPF_MOV64_REG(CODEGEN_REG_SCRATCH3, CODEGEN_REG_RETVAL));
+	EMIT(ctx, BPF_MOV64_IMM(CODEGEN_REG_RETVAL, TC_ACT_UNSPEC));
+	EMIT_FIXUP(ctx, CODEGEN_FIXUP_END_OF_CHAIN,
+		   BPF_JMP_IMM(ctx->iptables_hook == BPFILTER_INET_HOOK_FORWARD ? BPF_JNE : BPF_JEQ,
+			       CODEGEN_REG_SCRATCH3, BPF_FIB_LKUP_RET_SUCCESS, 0));
+
+	return 0;
+}
+
+int try_codegen(struct codegen *codegen, const struct table *table)
+{
+	struct rule *rule_front;
+	struct rule *rule_last;
+	int r;
+
+	r = codegen->codegen_ops->gen_inline_prologue(codegen);
+	if (r) {
+		BFLOG_ERR("failed to generate inline prologue: %s", STRERR(r));
+		return r;
+	}
+
+	r = codegen->codegen_ops->load_packet_data(codegen, CODEGEN_REG_L3);
+	if (r) {
+		BFLOG_ERR("failed to generate code to load packet data: %s",
+			  STRERR(r));
+		return r;
+	}
+
+	r = codegen->codegen_ops->load_packet_data_end(codegen,
+						       CODEGEN_REG_DATA_END);
+	if (r) {
+		BFLOG_ERR("failed to generate code to load packet data end: %s",
+			  STRERR(r));
+		return r;
+	}
+
+	// save packet size once
+	EMIT(codegen, BPF_MOV64_REG(CODEGEN_REG_SCRATCH2, CODEGEN_REG_DATA_END));
+	EMIT(codegen, BPF_ALU64_REG(BPF_SUB, CODEGEN_REG_SCRATCH2, CODEGEN_REG_L3));
+	EMIT(codegen, BPF_STX_MEM(BPF_W, CODEGEN_REG_RUNTIME_CTX, CODEGEN_REG_SCRATCH2,
+				  STACK_RUNTIME_CONTEXT_OFFSET(data_size)));
+
+	EMIT(codegen, BPF_ALU64_IMM(BPF_ADD, CODEGEN_REG_L3, ETH_HLEN));
+	EMIT_FIXUP(codegen, CODEGEN_FIXUP_END_OF_CHAIN,
+		   BPF_JMP_REG(BPF_JGT, CODEGEN_REG_L3, CODEGEN_REG_DATA_END, 0));
+	EMIT(codegen, BPF_MOV64_REG(CODEGEN_REG_SCRATCH1, CODEGEN_REG_L3));
+	EMIT(codegen, BPF_ALU64_IMM(BPF_ADD, CODEGEN_REG_SCRATCH1, sizeof(struct iphdr)));
+	EMIT_FIXUP(codegen, CODEGEN_FIXUP_END_OF_CHAIN,
+		   BPF_JMP_REG(BPF_JGT, CODEGEN_REG_SCRATCH1, CODEGEN_REG_DATA_END, 0));
+
+	if (codegen->iptables_hook == BPFILTER_INET_HOOK_LOCAL_IN ||
+	    codegen->iptables_hook == BPFILTER_INET_HOOK_FORWARD) {
+		/* There is no XDP nor TC forward hook to attach to. So, we
+		 * need to add code to assess whether a incoming packet it
+		 * to be forwarded or not.
+		 */
+		BFLOG_NOTICE("generate forward packet assessment");
+		generate_inline_forward_packet_assessment(codegen);
+	}
+
+	rule_front = &table->rules[table->hook_entry[codegen->iptables_hook]];
+	rule_last = &table->rules[table->underflow[codegen->iptables_hook]];
+
+	codegen->rule_index = rule_front - table->rules;
+	r = try_codegen_rules(codegen, rule_front, rule_last);
+	if (r) {
+		BFLOG_ERR("failed to generate rules: %s", STRERR(r));
+		return r;
+	}
+
+	r = codegen->codegen_ops->gen_inline_epilogue(codegen);
+	if (r) {
+		BFLOG_ERR("failed to generate inline epilogue: %s",
+			  STRERR(r));
+		return r;
+	}
+
+	r = try_codegen_subprogs(codegen, table);
+	if (r) {
+		BFLOG_ERR("failed to generate subprograms: %s", STRERR(r));
+		return r;
+	}
+
+	r = codegen_fixup(codegen, CODEGEN_FIXUP_JUMP_TO_CHAIN);
+	if (r) {
+		BFLOG_ERR("failed to generate fixups: %s", STRERR(r));
+		return r;
+	}
+
+	codegen->shared_codegen->maps[CODEGEN_RELOC_MAP].max_entries = table->num_rules;
+
+	return 0;
+}
+
 int load_img(struct codegen *codegen)
 {
 	union bpf_attr attr = {};
diff --git a/net/bpfilter/codegen.h b/net/bpfilter/codegen.h
index cca45a13c4aa..6cfd8e7a3692 100644
--- a/net/bpfilter/codegen.h
+++ b/net/bpfilter/codegen.h
@@ -18,6 +18,7 @@
 #include <stdint.h>
 
 struct context;
+struct table;
 
 #define CODEGEN_REG_RETVAL	BPF_REG_0
 #define CODEGEN_REG_SCRATCH1	BPF_REG_1
@@ -174,6 +175,7 @@ int codegen_fixup(struct codegen *codegen, enum codegen_fixup_type fixup_type);
 int emit_fixup(struct codegen *codegen, enum codegen_fixup_type fixup_type,
 	       struct bpf_insn insn);
 int emit_add_counter(struct codegen *codegen);
+int try_codegen(struct codegen *codegen, const struct table *table);
 int load_img(struct codegen *codegen);
 void unload_img(struct codegen *codegen);
 void free_codegen(struct codegen *codegen);
-- 
2.38.1