[bpf-next,v1,08/10] bpfilter: Add struct table

diff --git a/net/bpfilter/Makefile b/net/bpfilter/Makefile
index 7ce961162283..e16fee837ca0 100644
--- a/net/bpfilter/Makefile
+++ b/net/bpfilter/Makefile
@@ -4,7 +4,7 @@ 
 #
 
 userprogs := bpfilter_umh
-bpfilter_umh-objs := main.o map-common.o context.o match.o target.o rule.o
+bpfilter_umh-objs := main.o map-common.o context.o match.o target.o rule.o table.o
 bpfilter_umh-objs += xt_udp.o
 userccflags += -I $(srctree)/tools/include/ -I $(srctree)/tools/include/uapi
 
diff --git a/net/bpfilter/context.c b/net/bpfilter/context.c
index 6e186399609e..beb4454d1218 100644
--- a/net/bpfilter/context.c
+++ b/net/bpfilter/context.c
@@ -10,8 +10,12 @@ 
 #include <linux/err.h>
 #include <linux/list.h>
 
+#include <string.h>
+
 #include "map-common.h"
 #include "match.h"
+#include "rule.h"
+#include "table.h"
 #include "target.h"
 
 static int init_match_ops_map(struct context *ctx)
@@ -54,6 +58,88 @@  static int init_target_ops_map(struct context *ctx)
 	return 0;
 }
 
+static void init_standard_entry(struct bpfilter_ipt_standard_entry *ipt_entry)
+{
+	ipt_entry->entry.next_offset = sizeof(*ipt_entry);
+	ipt_entry->entry.target_offset = sizeof(ipt_entry->entry);
+	ipt_entry->target.target.u.user.revision = 0;
+	ipt_entry->target.target.u.user.target_size = sizeof(struct bpfilter_ipt_standard_target);
+	ipt_entry->target.verdict = -BPFILTER_NF_ACCEPT - 1;
+}
+
+static void init_error_entry(struct bpfilter_ipt_error_entry *ipt_entry)
+{
+	ipt_entry->entry.next_offset = sizeof(*ipt_entry);
+	ipt_entry->entry.target_offset = sizeof(ipt_entry->entry);
+	ipt_entry->target.target.u.target_size = sizeof(struct bpfilter_ipt_error_target);
+	ipt_entry->target.target.u.user.revision = 0;
+	snprintf(ipt_entry->target.target.u.user.name, sizeof(ipt_entry->target.target.u.user.name),
+		 "ERROR");
+}
+
+static struct table *create_filter_table(struct context *ctx)
+{
+	struct filter_table_entries {
+		struct bpfilter_ipt_standard_entry local_in;
+		struct bpfilter_ipt_standard_entry forward;
+		struct bpfilter_ipt_standard_entry local_out;
+		struct bpfilter_ipt_error_entry error;
+	};
+
+	struct filter_table {
+		struct bpfilter_ipt_replace replace;
+		struct filter_table_entries entries;
+	} filter_table;
+
+	memset(&filter_table, 0, sizeof(filter_table));
+
+	snprintf(filter_table.replace.name, sizeof(filter_table.replace.name), "filter");
+	filter_table.replace.valid_hooks = 1 << BPFILTER_INET_HOOK_LOCAL_IN |
+					   1 << BPFILTER_INET_HOOK_FORWARD |
+					   1 << BPFILTER_INET_HOOK_LOCAL_OUT;
+	filter_table.replace.num_entries = 4;
+	filter_table.replace.size = sizeof(struct filter_table_entries);
+
+	filter_table.replace.hook_entry[BPFILTER_INET_HOOK_FORWARD] =
+		offsetof(struct filter_table_entries, forward);
+	filter_table.replace.underflow[BPFILTER_INET_HOOK_FORWARD] =
+		offsetof(struct filter_table_entries, forward);
+
+	filter_table.replace.hook_entry[BPFILTER_INET_HOOK_LOCAL_OUT] =
+		offsetof(struct filter_table_entries, local_out);
+	filter_table.replace.underflow[BPFILTER_INET_HOOK_LOCAL_OUT] =
+		offsetof(struct filter_table_entries, local_out);
+
+	init_standard_entry(&filter_table.entries.local_in);
+	init_standard_entry(&filter_table.entries.forward);
+	init_standard_entry(&filter_table.entries.local_out);
+	init_error_entry(&filter_table.entries.error);
+
+	return create_table(ctx, &filter_table.replace);
+}
+
+static int init_table_index(struct context *ctx)
+{
+	struct table *table;
+	int err;
+
+	INIT_LIST_HEAD(&ctx->table_index.list);
+
+	err = create_map(&ctx->table_index.map, 1);
+	if (err)
+		return err;
+
+	table = create_filter_table(ctx);
+	if (IS_ERR(table)) {
+		free_map(&ctx->table_index.map);
+		return PTR_ERR(table);
+	}
+
+	list_add_tail(&table->list, &ctx->table_index.list);
+
+	return map_insert(&ctx->table_index.map, table->name, table);
+}
+
 int create_context(struct context *ctx)
 {
 	int err;
@@ -68,11 +154,28 @@  int create_context(struct context *ctx)
 		return err;
 	}
 
+	err = init_table_index(ctx);
+	if (err) {
+		free_map(&ctx->match_ops_map);
+		free_map(&ctx->target_ops_map);
+		return err;
+	}
+
 	return 0;
 }
 
 void free_context(struct context *ctx)
 {
+	struct list_head *t, *n;
+
+	list_for_each_safe(t, n, &ctx->table_index.list) {
+		struct table *table;
+
+		table = list_entry(t, struct table, list);
+		free_table(table);
+	}
+
+	free_map(&ctx->table_index.map);
 	free_map(&ctx->match_ops_map);
 	free_map(&ctx->target_ops_map);
 }
diff --git a/net/bpfilter/context.h b/net/bpfilter/context.h
index ed268259adcc..740d30af9087 100644
--- a/net/bpfilter/context.h
+++ b/net/bpfilter/context.h
@@ -8,14 +8,17 @@ 
 
 #include <sys/syslog.h>
 
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <search.h>
+
+#include "table.h"
 
 struct context {
 	FILE *log_file;
 	struct hsearch_data match_ops_map;
 	struct hsearch_data target_ops_map;
+	struct table_index table_index;
 };
 
 #define BFLOG_IMPL(ctx, level, fmt, ...)                                                           \
diff --git a/net/bpfilter/table.c b/net/bpfilter/table.c
new file mode 100644
index 000000000000..506ad3c9402f
--- /dev/null
+++ b/net/bpfilter/table.c
@@ -0,0 +1,339 @@ 
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (c) 2021 Telegram FZ-LLC
+ */
+
+#define _GNU_SOURCE
+
+#include "table.h"
+
+#include <linux/err.h>
+#include <linux/list.h>
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "context.h"
+#include "rule.h"
+
+static int rule_offset_comparator(const void *x, const void *y)
+{
+	const struct rule *rule = y;
+
+	return x - (const void *)rule->ipt_entry;
+}
+
+static struct rule *table_find_rule_by_offset(struct table *table, uint32_t offset)
+{
+	const struct bpfilter_ipt_entry *key;
+
+	key = table->entries + offset;
+
+	return bsearch(key, table->rules, table->num_rules, sizeof(table->rules[0]),
+		       rule_offset_comparator);
+}
+
+static int table_init_rules(struct context *ctx, struct table *table,
+			    const struct bpfilter_ipt_replace *ipt_replace)
+{
+	uint32_t offset;
+	int i;
+
+	table->entries = malloc(table->size);
+	if (!table->entries)
+		return -ENOMEM;
+
+	memcpy(table->entries, ipt_replace->entries, table->size);
+
+	table->rules = calloc(table->num_rules, sizeof(table->rules[0]));
+	if (!table->rules)
+		return -ENOMEM;
+
+	offset = 0;
+	for (i = 0; i < table->num_rules; ++i) {
+		const struct bpfilter_ipt_entry *ipt_entry;
+		int err;
+
+		if (table->size < offset)
+			return -EINVAL;
+
+		if (table->size < offset + sizeof(*ipt_entry))
+			return -EINVAL;
+
+		ipt_entry = table->entries + offset;
+
+		if ((uintptr_t)ipt_entry % __alignof__(struct bpfilter_ipt_entry))
+			return -EINVAL;
+
+		if (table->size < offset + ipt_entry->next_offset)
+			return -EINVAL;
+
+		err = init_rule(ctx, ipt_entry, &table->rules[i]);
+		if (err)
+			return err;
+
+		table->rules[i].ipt_entry = ipt_entry;
+		offset += ipt_entry->next_offset;
+	}
+
+	if (offset != ipt_replace->size)
+		return -EINVAL;
+
+	if (table->num_rules != ipt_replace->num_entries)
+		return -EINVAL;
+
+	return 0;
+}
+
+static int table_check_hooks(const struct table *table)
+{
+	uint32_t max_rule_front, max_rule_last;
+	bool check = false;
+	int i;
+
+	for (i = 0; i < BPFILTER_INET_HOOK_MAX; ++i) {
+		if (!(table->valid_hooks & (1 << i)))
+			continue;
+
+		if (check) {
+			if (table->hook_entry[i] <= max_rule_front)
+				return -EINVAL;
+
+			if (table->underflow[i] <= max_rule_last)
+				return -EINVAL;
+		}
+
+		max_rule_front = table->hook_entry[i];
+		max_rule_last = table->underflow[i];
+		check = true;
+	}
+
+	return 0;
+}
+
+static int table_init_hooks(struct table *table, const struct bpfilter_ipt_replace *ipt_replace)
+{
+	int i;
+
+	for (i = 0; i < BPFILTER_INET_HOOK_MAX; ++i) {
+		struct rule *rule_front, *rule_last;
+		int verdict;
+
+		if (!(table->valid_hooks & (1 << i)))
+			continue;
+
+		rule_front = table_find_rule_by_offset(table, ipt_replace->hook_entry[i]);
+		rule_last = table_find_rule_by_offset(table, ipt_replace->underflow[i]);
+
+		if (!rule_front || !rule_last)
+			return -EINVAL;
+
+		if (!is_rule_unconditional(rule_last))
+			return -EINVAL;
+
+		if (!rule_has_standard_target(rule_last))
+			return -EINVAL;
+
+		verdict = standard_target_verdict(rule_last->target.ipt_target);
+		if (verdict >= 0)
+			return -EINVAL;
+
+		verdict = convert_verdict(verdict);
+
+		if (verdict != BPFILTER_NF_DROP && verdict != BPFILTER_NF_ACCEPT)
+			return -EINVAL;
+
+		table->hook_entry[i] = rule_front - table->rules;
+		table->underflow[i] = rule_last - table->rules;
+	}
+
+	return table_check_hooks(table);
+}
+
+static struct rule *next_rule(const struct table *table, struct rule *rule)
+{
+	const uint32_t i = rule - table->rules;
+
+	if (table->num_rules <= i + 1)
+		return ERR_PTR(-EINVAL);
+
+	++rule;
+	rule->came_from = i;
+
+	return rule;
+}
+
+static struct rule *backtrack_rule(const struct table *table, struct rule *rule)
+{
+	uint32_t i = rule - table->rules;
+	int prev_i;
+
+	do {
+		rule->hook_mask ^= (1 << BPFILTER_INET_HOOK_MAX);
+		prev_i = i;
+		i = rule->came_from;
+		rule->came_from = 0;
+
+		if (i == prev_i)
+			return NULL;
+
+		rule = &table->rules[i];
+	} while (prev_i == i + 1);
+
+	return next_rule(table, rule);
+}
+
+static int table_check_chain(struct table *table, uint32_t hook, struct rule *rule)
+{
+	uint32_t i = rule - table->rules;
+
+	rule->came_from = i;
+
+	for (;;) {
+		bool visited;
+		int verdict;
+
+		if (!rule)
+			return 0;
+
+		if (IS_ERR(rule))
+			return PTR_ERR(rule);
+
+		i = rule - table->rules;
+
+		if (table->num_rules <= i)
+			return -EINVAL;
+
+		if (rule->hook_mask & (1 << BPFILTER_INET_HOOK_MAX))
+			return -EINVAL;
+
+		// already visited
+		visited = rule->hook_mask & (1 << hook);
+		rule->hook_mask |= (1 << hook) | (1 << BPFILTER_INET_HOOK_MAX);
+
+		if (visited) {
+			rule = backtrack_rule(table, rule);
+			continue;
+		}
+
+		if (!rule_has_standard_target(rule)) {
+			rule = next_rule(table, rule);
+			continue;
+		}
+
+		verdict = standard_target_verdict(rule->target.ipt_target);
+		if (verdict > 0) {
+			rule = table_find_rule_by_offset(table, verdict);
+			if (!rule)
+				return -EINVAL;
+
+			rule->came_from = i;
+			continue;
+		}
+
+		if (!is_rule_unconditional(rule)) {
+			rule = next_rule(table, rule);
+			continue;
+		}
+
+		rule = backtrack_rule(table, rule);
+	}
+
+	return 0;
+}
+
+static int table_check_chains(struct table *table)
+{
+	int i, err;
+
+	for (i = 0, err = 0; !err && i < BPFILTER_INET_HOOK_MAX; ++i) {
+		if (table->valid_hooks & (1 << i))
+			err = table_check_chain(table, i, &table->rules[table->hook_entry[i]]);
+	}
+
+	return err;
+}
+
+struct table *create_table(struct context *ctx, const struct bpfilter_ipt_replace *ipt_replace)
+{
+	struct table *table;
+	int err;
+
+	table = calloc(1, sizeof(*table));
+	if (!table)
+		return ERR_PTR(-ENOMEM);
+
+	INIT_LIST_HEAD(&table->list);
+	snprintf(table->name, sizeof(table->name), "%s", ipt_replace->name);
+	table->valid_hooks = ipt_replace->valid_hooks;
+	table->num_rules = ipt_replace->num_entries;
+	table->num_counters = ipt_replace->num_counters;
+	table->size = ipt_replace->size;
+
+	err = table_init_rules(ctx, table, ipt_replace);
+	if (err)
+		goto err_free;
+
+	err = table_init_hooks(table, ipt_replace);
+	if (err)
+		goto err_free;
+
+	err = table_check_chains(table);
+	if (err)
+		goto err_free;
+
+	return table;
+
+err_free:
+	free_table(table);
+
+	return ERR_PTR(err);
+}
+
+void table_get_info(const struct table *table, struct bpfilter_ipt_get_info *info)
+{
+	int i;
+
+	snprintf(info->name, sizeof(info->name), "%s", table->name);
+	info->valid_hooks = table->valid_hooks;
+
+	for (i = 0; i < BPFILTER_INET_HOOK_MAX; ++i) {
+		const struct rule *rule_front, *rule_last;
+
+		if (!(table->valid_hooks & (1 << i))) {
+			info->hook_entry[i] = 0;
+			info->underflow[i] = 0;
+			continue;
+		}
+
+		rule_front = &table->rules[table->hook_entry[i]];
+		rule_last = &table->rules[table->underflow[i]];
+		info->hook_entry[i] = (const void *)rule_front->ipt_entry - table->entries;
+		info->underflow[i] = (const void *)rule_last->ipt_entry - table->entries;
+	}
+
+	info->num_entries = table->num_rules;
+	info->size = table->size;
+}
+
+void free_table(struct table *table)
+{
+	int i;
+
+	if (!table)
+		return;
+
+	list_del(&table->list);
+
+	if (table->rules) {
+		for (i = 0; i < table->num_rules; ++i)
+			free_rule(&table->rules[i]);
+		free(table->rules);
+	}
+
+	free(table->entries);
+	free(table);
+}
diff --git a/net/bpfilter/table.h b/net/bpfilter/table.h
new file mode 100644
index 000000000000..0f5d653c4460
--- /dev/null
+++ b/net/bpfilter/table.h
@@ -0,0 +1,39 @@ 
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (c) 2021 Telegram FZ-LLC
+ */
+
+#ifndef NET_BPFILTER_TABLE_H
+#define NET_BPFILTER_TABLE_H
+
+#include "../../include/uapi/linux/bpfilter.h"
+
+#include <search.h>
+#include <stdint.h>
+
+struct context;
+struct rule;
+
+struct table {
+	struct list_head list;
+	char name[BPFILTER_XT_TABLE_MAXNAMELEN];
+	uint32_t valid_hooks;
+	uint32_t num_rules;
+	uint32_t num_counters;
+	uint32_t size;
+	uint32_t hook_entry[BPFILTER_INET_HOOK_MAX];
+	uint32_t underflow[BPFILTER_INET_HOOK_MAX];
+	struct rule *rules;
+	void *entries;
+};
+
+struct table_index {
+	struct hsearch_data map;
+	struct list_head list;
+};
+
+struct table *create_table(struct context *ctx, const struct bpfilter_ipt_replace *ipt_replace);
+void table_get_info(const struct table *table, struct bpfilter_ipt_get_info *info);
+void free_table(struct table *table);
+
+#endif // NET_BPFILTER_TABLE_H
diff --git a/tools/testing/selftests/bpf/bpfilter/Makefile b/tools/testing/selftests/bpf/bpfilter/Makefile
index 27a1ddcb6dc9..267a96a4c8a6 100644
--- a/tools/testing/selftests/bpf/bpfilter/Makefile
+++ b/tools/testing/selftests/bpf/bpfilter/Makefile
@@ -21,7 +21,7 @@  BPFILTER_MATCH_SRCS := $(BPFILTERSRCDIR)/match.c $(BPFILTERSRCDIR)/xt_udp.c
 BPFILTER_TARGET_SRCS := $(BPFILTERSRCDIR)/target.c
 
 BPFILTER_COMMON_SRCS := $(BPFILTERSRCDIR)/map-common.c $(BPFILTERSRCDIR)/context.c \
-	$(BPFILTERSRCDIR)/rule.c
+	$(BPFILTERSRCDIR)/rule.c $(BPFILTERSRCDIR)/table.c
 BPFILTER_COMMON_SRCS += $(BPFILTER_MATCH_SRCS) $(BPFILTER_TARGET_SRCS)
 
 $(OUTPUT)/test_map: test_map.c $(BPFILTERSRCDIR)/map-common.c