Skip to contentSkip to conversation

src: add expression handler hashtable

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

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 1/2 src: add expression handler hashtable

netlink_parsers is actually small, but update this code to use a hashtable instead since more expressions may come in the future.

---
 include/cache.h           | 10 +++++++++
 include/netlink.h         |  3 +++
 include/rule.h            |  1 +
 src/libnftables.c         |  2 ++
 src/netlink_delinearize.c | 46 ++++++++++++++++++++++++++++++---------
 5 files changed, 52 insertions(+), 10 deletions(-)
include/cache.h +10 -0
index 213a6eaf9104..b9db1a8f7650 100644
@@ -35,4 +35,14 @@ enum cache_level_flags {
 	NFT_CACHE_FLUSHED	= (1 << 31),
 };
 
+static inline uint32_t djb_hash(const char *key)
+{
+	uint32_t i, hash = 5381;
+
+	for (i = 0; i < strlen(key); i++)
+		hash = ((hash << 5) + hash) + key[i];
+
+	return hash;
+}
+
 #endif /* _NFT_CACHE_H_ */
include/netlink.h +3 -0
index 1077096ea0b1..ad2247e9dd57 100644
@@ -213,4 +213,7 @@ int netlink_events_trace_cb(const struct nlmsghdr *nlh, int type,
 
 enum nft_data_types dtype_map_to_kernel(const struct datatype *dtype);
 
+void expr_handler_init(void);
+void expr_handler_exit(void);
+
 #endif /* NFTABLES_NETLINK_H */
include/rule.h +1 -0
index caca63d0f648..f2f82cc0ca4b 100644
@@ -7,6 +7,7 @@
 #include <netinet/in.h>
 #include <libnftnl/object.h>	/* For NFTNL_CTTIMEOUT_ARRAY_MAX. */
 #include <linux/netfilter/nf_tables.h>
+#include <string.h>
 
 /**
  * struct handle_spec - handle ID
src/libnftables.c +2 -0
index 668e3fc43031..fce52ad4003b 100644
@@ -88,10 +88,12 @@ static void nft_init(struct nft_ctx *ctx)
 	realm_table_rt_init(ctx);
 	devgroup_table_init(ctx);
 	ct_label_table_init(ctx);
+	expr_handler_init();
 }
 
 static void nft_exit(struct nft_ctx *ctx)
 {
+	expr_handler_exit();
 	ct_label_table_exit(ctx);
 	realm_table_rt_exit(ctx);
 	devgroup_table_exit(ctx);
src/netlink_delinearize.c +36 -10

79 lines not on this page · raw message

Signature · 1 line
2.20.1
author maintainer
#1 lore raw

PATCH 2/2 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.

---
 include/cache.h   | 12 ++++++++
 include/netlink.h |  1 -
 include/rule.h    |  4 ++-
 src/cache.c       | 76 +++++++++++++++++++++++++++++++++++++++++++++++
 src/evaluate.c    |  6 ++--
 src/netlink.c     | 46 ----------------------------
 src/rule.c        | 21 ++++++-------
 7 files changed, 103 insertions(+), 63 deletions(-)
include/cache.h +12 -0
index b9db1a8f7650..4786e5217b08 100644
@@ -45,4 +45,16 @@ 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;
+
+int chain_cache_dump(struct netlink_ctx *ctx, struct table *table);
+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 +76 -0

85 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 +9 -12
index 2b5685c23e54..f41018332753 100644
@@ -174,13 +174,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_dump(ctx, table);
 			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 +194,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);
@@ -256,7 +252,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 +921,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 +1285,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 +1296,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 +1325,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