Skip to contentSkip to conversation

src: add chain hashtable cache

PATCH New Pablo Neira Ayuso 1 participant 1 message Aug 21, 2020 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH v2 1/1 src: add chain hashtable cache

This significantly improves ruleset listing time with large rulesets (~50k rules) with _lots_ of non-base chains.

 # time nft list ruleset &> /dev/null

Before this patch:

real    0m11,172s
user    0m6,810s
sys     0m4,220s

After this patch:

real    0m4,747s
user    0m0,802s
sys     0m3,912s

This patch also removes list_bindings from netlink_ctx since there is no need to keep a temporary list of chains anymore.

---
v2: dump chain netlink cache only once.

 include/cache.h   | 14 ++++++++
 include/netlink.h |  1 -
 include/rule.h    |  4 ++-
 src/cache.c       | 92 +++++++++++++++++++++++++++++++++++++++++++++++
 src/evaluate.c    |  6 ++--
 src/netlink.c     | 46 ------------------------
 src/rule.c        | 34 +++++++++++-------
 7 files changed, 133 insertions(+), 64 deletions(-)
include/cache.h +14 -0
index b9db1a8f7650..baa2bb29f1e7 100644
@@ -45,4 +45,18 @@ static inline uint32_t djb_hash(const char *key)
 	return hash;
 }
 
+#define NFT_CACHE_HSIZE 8192
+
+struct netlink_ctx;
+struct table;
+struct chain;
+struct handle;
+
+struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx, int *err);
+int chain_cache_init(struct netlink_ctx *ctx, struct table *table,
+		     struct nftnl_chain_list *chain_cache);
+void chain_cache_add(struct chain *chain, struct table *table);
+struct chain *chain_cache_find(const struct table *table,
+			       const struct handle *handle);
+
 #endif /* _NFT_CACHE_H_ */
include/netlink.h +0 -1
index ad2247e9dd57..b78277a8ce30 100644
@@ -64,7 +64,6 @@ struct netlink_ctx {
 	struct nft_ctx		*nft;
 	struct list_head	*msgs;
 	struct list_head	list;
-	struct list_head	list_bindings;
 	struct set		*set;
 	const void		*data;
 	uint32_t		seqnum;
include/rule.h +3 -1
index f2f82cc0ca4b..62d25be2106e 100644
@@ -8,6 +8,7 @@
 #include <libnftnl/object.h>	/* For NFTNL_CTTIMEOUT_ARRAY_MAX. */
 #include <linux/netfilter/nf_tables.h>
 #include <string.h>
+#include <cache.h>
 
 /**
  * struct handle_spec - handle ID
@@ -153,6 +154,7 @@ struct table {
 	struct handle		handle;
 	struct location		location;
 	struct scope		scope;
+	struct list_head	*chain_htable;
 	struct list_head	chains;
 	struct list_head	sets;
 	struct list_head	objs;
@@ -217,6 +219,7 @@ struct hook_spec {
  */
 struct chain {
 	struct list_head	list;
+	struct list_head	hlist;
 	struct handle		handle;
 	struct location		location;
 	unsigned int		refcnt;
@@ -242,7 +245,6 @@ extern const char *chain_hookname_lookup(const char *name);
 extern struct chain *chain_alloc(const char *name);
 extern struct chain *chain_get(struct chain *chain);
 extern void chain_free(struct chain *chain);
-extern void chain_add_hash(struct chain *chain, struct table *table);
 extern struct chain *chain_lookup(const struct table *table,
 				  const struct handle *h);
 extern struct chain *chain_lookup_fuzzy(const struct handle *h,
src/cache.c +92 -0

101 lines not on this page · raw message

src/evaluate.c +3 -3
index b64ed3c0c6a4..320a464f9162 100644
@@ -3855,7 +3855,7 @@ static int rule_cache_update(struct eval_ctx *ctx, enum cmd_ops op)
 	if (!table)
 		return table_not_found(ctx);
 
-	chain = chain_lookup(table, &rule->handle);
+	chain = chain_cache_find(table, &rule->handle);
 	if (!chain)
 		return chain_not_found(ctx);
 
@@ -3999,12 +3999,12 @@ static int chain_evaluate(struct eval_ctx *ctx, struct chain *chain)
 		if (chain_lookup(table, &ctx->cmd->handle) == NULL) {
 			chain = chain_alloc(NULL);
 			handle_merge(&chain->handle, &ctx->cmd->handle);
-			chain_add_hash(chain, table);
+			chain_cache_add(chain, table);
 		}
 		return 0;
 	} else if (!(chain->flags & CHAIN_F_BINDING)) {
 		if (chain_lookup(table, &chain->handle) == NULL)
-			chain_add_hash(chain_get(chain), table);
+			chain_cache_add(chain_get(chain), table);
 	}
 
 	if (chain->flags & CHAIN_F_BASECHAIN) {
src/netlink.c +0 -46

52 lines not on this page · raw message

src/rule.c +21 -13
index 2b5685c23e54..a925d8448760 100644
@@ -152,11 +152,18 @@ static int cache_init_tables(struct netlink_ctx *ctx, struct handle *h,
 
 static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags)
 {
+	struct nftnl_chain_list *chain_list = NULL;
 	struct rule *rule, *nrule;
 	struct table *table;
 	struct chain *chain;
 	struct set *set;
-	int ret;
+	int ret = 0;
+
+	if (flags & NFT_CACHE_CHAIN_BIT) {
+		chain_list = chain_cache_dump(ctx, &ret);
+		if (!chain_list)
+			return ret;
+	}
 
 	list_for_each_entry(table, &ctx->nft->cache.list, list) {
 		if (flags & NFT_CACHE_SET_BIT) {
@@ -174,13 +181,9 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags)
 			}
 		}
 		if (flags & NFT_CACHE_CHAIN_BIT) {
-			ret = netlink_list_chains(ctx, &table->handle);
+			ret = chain_cache_init(ctx, table, chain_list);
 			if (ret < 0)
 				return -1;
-
-			list_splice_tail_init(&ctx->list, &table->chains);
-			list_splice_tail_init(&ctx->list_bindings,
-					      &table->chain_bindings);
 		}
 		if (flags & NFT_CACHE_FLOWTABLE_BIT) {
 			ret = netlink_list_flowtables(ctx, &table->handle);
@@ -198,7 +201,7 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags)
 		if (flags & NFT_CACHE_RULE_BIT) {
 			ret = netlink_list_rules(ctx, &table->handle);
 			list_for_each_entry_safe(rule, nrule, &ctx->list, list) {
-				chain = chain_lookup(table, &rule->handle);
+				chain = chain_cache_find(table, &rule->handle);
 				if (!chain)
 					chain = chain_binding_lookup(table,
 							rule->handle.chain.name);
@@ -208,6 +211,10 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags)
 				return -1;
 		}
 	}
+
+	if (flags & NFT_CACHE_CHAIN_BIT)
+		nftnl_chain_list_free(chain_list);
+
 	return 0;
 }
 
@@ -256,7 +263,6 @@ int cache_update(struct nft_ctx *nft, unsigned int flags, struct list_head *msgs
 {
 	struct netlink_ctx ctx = {
 		.list		= LIST_HEAD_INIT(ctx.list),
-		.list_bindings	= LIST_HEAD_INIT(ctx.list_bindings),
 		.nft		= nft,
 		.msgs		= msgs,
 	};
@@ -926,11 +932,6 @@ void chain_free(struct chain *chain)
 	xfree(chain);
 }
 
-void chain_add_hash(struct chain *chain, struct table *table)
-{
-	list_add_tail(&chain->list, &table->chains);
-}
-
 struct chain *chain_lookup(const struct table *table, const struct handle *h)
 {
 	struct chain *chain;
@@ -1295,6 +1296,7 @@ void chain_print_plain(const struct chain *chain, struct output_ctx *octx)
 struct table *table_alloc(void)
 {
 	struct table *table;
+	int i;
 
 	table = xzalloc(sizeof(*table));
 	init_list_head(&table->chains);
@@ -1305,6 +1307,11 @@ struct table *table_alloc(void)
 	init_list_head(&table->scope.symbols);
 	table->refcnt = 1;
 
+	table->chain_htable =
+		xmalloc(sizeof(struct list_head) * NFT_CACHE_HSIZE);
+	for (i = 0; i < NFT_CACHE_HSIZE; i++)
+		init_list_head(&table->chain_htable[i]);
+
 	return table;
 }
 
@@ -1329,6 +1336,7 @@ void table_free(struct table *table)
 		obj_free(obj);
 	handle_free(&table->handle);
 	scope_release(&table->scope);
+	xfree(table->chain_htable);
 	xfree(table);
 }
 
Signature · 1 line
2.20.1