All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH nft 1/4] cache: rename chain_htable to cache_chain_ht
@ 2021-04-01 20:29 Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 2/4,v2] src: split chain list in table Pablo Neira Ayuso
                   ` (2 more replies)
  0 siblings, 3 replies; 4+ messages in thread
From: Pablo Neira Ayuso @ 2021-04-01 20:29 UTC (permalink / raw)
  To: netfilter-devel

Rename the hashtable chain that is used for fast cache lookups.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/rule.h | 4 ++--
 src/cache.c    | 6 +++---
 src/rule.c     | 6 +++---
 3 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/include/rule.h b/include/rule.h
index 4ef24eb4ec63..f8e615121113 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -155,7 +155,7 @@ struct table {
 	struct handle		handle;
 	struct location		location;
 	struct scope		scope;
-	struct list_head	*chain_htable;
+	struct list_head	*cache_chain_ht;
 	struct list_head	chains;
 	struct list_head	sets;
 	struct list_head	objs;
@@ -230,7 +230,7 @@ struct hook_spec {
  */
 struct chain {
 	struct list_head	list;
-	struct list_head	hlist;
+	struct list_head	cache_hlist;
 	struct handle		handle;
 	struct location		location;
 	unsigned int		refcnt;
diff --git a/src/cache.c b/src/cache.c
index 63971e865622..400128906b03 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -195,7 +195,7 @@ static int chain_cache_cb(struct nftnl_chain *nlc, void *arg)
 	if (chain->flags & CHAIN_F_BINDING) {
 		list_add_tail(&chain->list, &ctx->table->chain_bindings);
 	} else {
-		list_add_tail(&chain->hlist, &ctx->table->chain_htable[hash]);
+		list_add_tail(&chain->cache_hlist, &ctx->table->cache_chain_ht[hash]);
 		list_add_tail(&chain->list, &ctx->table->chains);
 	}
 
@@ -239,7 +239,7 @@ void chain_cache_add(struct chain *chain, struct table *table)
 	uint32_t hash;
 
 	hash = djb_hash(chain->handle.chain.name) % NFT_CACHE_HSIZE;
-	list_add_tail(&chain->hlist, &table->chain_htable[hash]);
+	list_add_tail(&chain->cache_hlist, &table->cache_chain_ht[hash]);
 	list_add_tail(&chain->list, &table->chains);
 }
 
@@ -250,7 +250,7 @@ struct chain *chain_cache_find(const struct table *table,
 	uint32_t hash;
 
 	hash = djb_hash(handle->chain.name) % NFT_CACHE_HSIZE;
-	list_for_each_entry(chain, &table->chain_htable[hash], hlist) {
+	list_for_each_entry(chain, &table->cache_chain_ht[hash], cache_hlist) {
 		if (!strcmp(chain->handle.chain.name, handle->chain.name))
 			return chain;
 	}
diff --git a/src/rule.c b/src/rule.c
index 969318008933..79706ab7b60a 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1140,10 +1140,10 @@ struct table *table_alloc(void)
 	init_list_head(&table->scope.symbols);
 	table->refcnt = 1;
 
-	table->chain_htable =
+	table->cache_chain_ht =
 		xmalloc(sizeof(struct list_head) * NFT_CACHE_HSIZE);
 	for (i = 0; i < NFT_CACHE_HSIZE; i++)
-		init_list_head(&table->chain_htable[i]);
+		init_list_head(&table->cache_chain_ht[i]);
 
 	return table;
 }
@@ -1171,7 +1171,7 @@ void table_free(struct table *table)
 		obj_free(obj);
 	handle_free(&table->handle);
 	scope_release(&table->scope);
-	xfree(table->chain_htable);
+	xfree(table->cache_chain_ht);
 	xfree(table);
 }
 
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 4+ messages in thread
* [PATCH nft 2/4,v2] src: split chain list in table
  2021-04-01 20:29 [PATCH nft 1/4] cache: rename chain_htable to cache_chain_ht Pablo Neira Ayuso
@ 2021-04-01 20:29 ` Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 3/4] evaluate: use chain hashtable for lookups Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 4/4] cache: statify chain_cache_dump() Pablo Neira Ayuso
  2 siblings, 0 replies; 4+ messages in thread
From: Pablo Neira Ayuso @ 2021-04-01 20:29 UTC (permalink / raw)
  To: netfilter-devel

This patch splits table->lists in two:

- Chains that reside in the cache are stored in the new
  tables->cache_chain and tables->cache_chain_ht. The hashtable chain
  cache allows for fast chain lookups.

- Chains that defined via command line / ruleset file reside in
  tables->chains.

Note that chains in the cache (already in the kernel) are not placed in
the table->chains.

By keeping separated lists, chains defined via command line / ruleset
file can be added to cache.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: instead of cloning the chain, reuse the existing chain coming
    from the command/ruleset and add it to the cache.

 include/rule.h |  2 ++
 src/cache.c    |  6 +++---
 src/json.c     |  6 +++---
 src/rule.c     | 18 +++++++++++-------
 4 files changed, 19 insertions(+), 13 deletions(-)

diff --git a/include/rule.h b/include/rule.h
index f8e615121113..6c6ada6b5537 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -156,6 +156,7 @@ struct table {
 	struct location		location;
 	struct scope		scope;
 	struct list_head	*cache_chain_ht;
+	struct list_head	cache_chain;
 	struct list_head	chains;
 	struct list_head	sets;
 	struct list_head	objs;
@@ -231,6 +232,7 @@ struct hook_spec {
 struct chain {
 	struct list_head	list;
 	struct list_head	cache_hlist;
+	struct list_head	cache_list;
 	struct handle		handle;
 	struct location		location;
 	unsigned int		refcnt;
diff --git a/src/cache.c b/src/cache.c
index 400128906b03..c9e1f22a3291 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -193,10 +193,10 @@ static int chain_cache_cb(struct nftnl_chain *nlc, void *arg)
 	chain = netlink_delinearize_chain(ctx->nlctx, nlc);
 
 	if (chain->flags & CHAIN_F_BINDING) {
-		list_add_tail(&chain->list, &ctx->table->chain_bindings);
+		list_add_tail(&chain->cache_list, &ctx->table->chain_bindings);
 	} else {
 		list_add_tail(&chain->cache_hlist, &ctx->table->cache_chain_ht[hash]);
-		list_add_tail(&chain->list, &ctx->table->chains);
+		list_add_tail(&chain->cache_list, &ctx->table->cache_chain);
 	}
 
 	nftnl_chain_list_del(nlc);
@@ -240,7 +240,7 @@ void chain_cache_add(struct chain *chain, struct table *table)
 
 	hash = djb_hash(chain->handle.chain.name) % NFT_CACHE_HSIZE;
 	list_add_tail(&chain->cache_hlist, &table->cache_chain_ht[hash]);
-	list_add_tail(&chain->list, &table->chains);
+	list_add_tail(&chain->cache_list, &table->cache_chain);
 }
 
 struct chain *chain_cache_find(const struct table *table,
diff --git a/src/json.c b/src/json.c
index defbc8fb44df..14e403fe1130 100644
--- a/src/json.c
+++ b/src/json.c
@@ -1584,7 +1584,7 @@ static json_t *table_print_json_full(struct netlink_ctx *ctx,
 		tmp = flowtable_print_json(flowtable);
 		json_array_append_new(root, tmp);
 	}
-	list_for_each_entry(chain, &table->chains, list) {
+	list_for_each_entry(chain, &table->cache_chain, cache_list) {
 		tmp = chain_print_json(chain);
 		json_array_append_new(root, tmp);
 
@@ -1646,7 +1646,7 @@ static json_t *do_list_chain_json(struct netlink_ctx *ctx,
 	struct chain *chain;
 	struct rule *rule;
 
-	list_for_each_entry(chain, &table->chains, list) {
+	list_for_each_entry(chain, &table->cache_chain, cache_list) {
 		if (chain->handle.family != cmd->handle.family ||
 		    strcmp(cmd->handle.chain.name, chain->handle.chain.name))
 			continue;
@@ -1674,7 +1674,7 @@ static json_t *do_list_chains_json(struct netlink_ctx *ctx, struct cmd *cmd)
 		    cmd->handle.family != table->handle.family)
 			continue;
 
-		list_for_each_entry(chain, &table->chains, list) {
+		list_for_each_entry(chain, &table->cache_chain, cache_list) {
 			json_t *tmp = chain_print_json(chain);
 
 			json_array_append_new(root, tmp);
diff --git a/src/rule.c b/src/rule.c
index 79706ab7b60a..5be9c0c82444 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -765,7 +765,7 @@ struct chain *chain_lookup(const struct table *table, const struct handle *h)
 {
 	struct chain *chain;
 
-	list_for_each_entry(chain, &table->chains, list) {
+	list_for_each_entry(chain, &table->cache_chain, cache_list) {
 		if (!strcmp(chain->handle.chain.name, h->chain.name))
 			return chain;
 	}
@@ -777,7 +777,7 @@ struct chain *chain_binding_lookup(const struct table *table,
 {
 	struct chain *chain;
 
-	list_for_each_entry(chain, &table->chain_bindings, list) {
+	list_for_each_entry(chain, &table->chain_bindings, cache_list) {
 		if (!strcmp(chain->handle.chain.name, chain_name))
 			return chain;
 	}
@@ -795,7 +795,7 @@ struct chain *chain_lookup_fuzzy(const struct handle *h,
 	string_misspell_init(&st);
 
 	list_for_each_entry(table, &cache->list, list) {
-		list_for_each_entry(chain, &table->chains, list) {
+		list_for_each_entry(chain, &table->cache_chain, cache_list) {
 			if (!strcmp(chain->handle.chain.name, h->chain.name)) {
 				*t = table;
 				return chain;
@@ -1133,6 +1133,7 @@ struct table *table_alloc(void)
 
 	table = xzalloc(sizeof(*table));
 	init_list_head(&table->chains);
+	init_list_head(&table->cache_chain);
 	init_list_head(&table->sets);
 	init_list_head(&table->objs);
 	init_list_head(&table->flowtables);
@@ -1161,7 +1162,10 @@ void table_free(struct table *table)
 		xfree(table->comment);
 	list_for_each_entry_safe(chain, next, &table->chains, list)
 		chain_free(chain);
-	list_for_each_entry_safe(chain, next, &table->chain_bindings, list)
+	list_for_each_entry_safe(chain, next, &table->chain_bindings, cache_list)
+		chain_free(chain);
+	/* this is implicitly releasing chains in the hashtable cache */
+	list_for_each_entry_safe(chain, next, &table->cache_chain, cache_list)
 		chain_free(chain);
 	list_for_each_entry_safe(set, nset, &table->sets, list)
 		set_free(set);
@@ -1294,7 +1298,7 @@ static void table_print(const struct table *table, struct output_ctx *octx)
 		flowtable_print(flowtable, octx);
 		delim = "\n";
 	}
-	list_for_each_entry(chain, &table->chains, list) {
+	list_for_each_entry(chain, &table->cache_chain, cache_list) {
 		nft_print(octx, "%s", delim);
 		chain_print(chain, octx);
 		delim = "\n";
@@ -2388,7 +2392,7 @@ static int do_list_chain(struct netlink_ctx *ctx, struct cmd *cmd,
 
 	table_print_declaration(table, &ctx->nft->output);
 
-	list_for_each_entry(chain, &table->chains, list) {
+	list_for_each_entry(chain, &table->cache_chain, cache_list) {
 		if (chain->handle.family != cmd->handle.family ||
 		    strcmp(cmd->handle.chain.name, chain->handle.chain.name) != 0)
 			continue;
@@ -2413,7 +2417,7 @@ static int do_list_chains(struct netlink_ctx *ctx, struct cmd *cmd)
 
 		table_print_declaration(table, &ctx->nft->output);
 
-		list_for_each_entry(chain, &table->chains, list) {
+		list_for_each_entry(chain, &table->cache_chain, cache_list) {
 			chain_print_declaration(chain, &ctx->nft->output);
 			nft_print(&ctx->nft->output, "\t}\n");
 		}
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 4+ messages in thread
* [PATCH nft 3/4] evaluate: use chain hashtable for lookups
  2021-04-01 20:29 [PATCH nft 1/4] cache: rename chain_htable to cache_chain_ht Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 2/4,v2] src: split chain list in table Pablo Neira Ayuso
@ 2021-04-01 20:29 ` Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 4/4] cache: statify chain_cache_dump() Pablo Neira Ayuso
  2 siblings, 0 replies; 4+ messages in thread
From: Pablo Neira Ayuso @ 2021-04-01 20:29 UTC (permalink / raw)
  To: netfilter-devel

Instead of the linear list lookup.

Before this patch:

real    0m21,735s
user    0m20,329s
sys     0m1,384s

After:

real    0m10,910s
user    0m9,448s
sys     0m1,434s

chain_lookup() is removed since linear list lookups are only used by the
fuzzy chain name matching for error reporting.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/rule.h |  2 --
 src/evaluate.c |  8 ++++----
 src/netlink.c  |  2 +-
 src/rule.c     | 13 +------------
 4 files changed, 6 insertions(+), 19 deletions(-)

diff --git a/include/rule.h b/include/rule.h
index 6c6ada6b5537..ad9cca90570d 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -259,8 +259,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 struct chain *chain_lookup(const struct table *table,
-				  const struct handle *h);
 extern struct chain *chain_lookup_fuzzy(const struct handle *h,
 					const struct nft_cache *cache,
 					const struct table **table);
diff --git a/src/evaluate.c b/src/evaluate.c
index cebf7cb8ef2c..691920b04093 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -4106,14 +4106,14 @@ static int chain_evaluate(struct eval_ctx *ctx, struct chain *chain)
 		return table_not_found(ctx);
 
 	if (chain == NULL) {
-		if (chain_lookup(table, &ctx->cmd->handle) == NULL) {
+		if (chain_cache_find(table, &ctx->cmd->handle) == NULL) {
 			chain = chain_alloc(NULL);
 			handle_merge(&chain->handle, &ctx->cmd->handle);
 			chain_cache_add(chain, table);
 		}
 		return 0;
 	} else if (!(chain->flags & CHAIN_F_BINDING)) {
-		if (chain_lookup(table, &chain->handle) == NULL)
+		if (chain_cache_find(table, &chain->handle) == NULL)
 			chain_cache_add(chain_get(chain), table);
 	}
 
@@ -4440,7 +4440,7 @@ static int cmd_evaluate_list(struct eval_ctx *ctx, struct cmd *cmd)
 		if (table == NULL)
 			return table_not_found(ctx);
 
-		if (chain_lookup(table, &cmd->handle) == NULL)
+		if (chain_cache_find(table, &cmd->handle) == NULL)
 			return chain_not_found(ctx);
 
 		return 0;
@@ -4600,7 +4600,7 @@ static int cmd_evaluate_rename(struct eval_ctx *ctx, struct cmd *cmd)
 		if (table == NULL)
 			return table_not_found(ctx);
 
-		if (chain_lookup(table, &ctx->cmd->handle) == NULL)
+		if (chain_cache_find(table, &ctx->cmd->handle) == NULL)
 			return chain_not_found(ctx);
 
 		break;
diff --git a/src/netlink.c b/src/netlink.c
index 103fdbd10690..50318f95e690 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -1746,7 +1746,7 @@ static struct rule *trace_lookup_rule(const struct nftnl_trace *nlt,
 	if (!table)
 		return NULL;
 
-	chain = chain_lookup(table, &h);
+	chain = chain_cache_find(table, &h);
 	if (!chain)
 		return NULL;
 
diff --git a/src/rule.c b/src/rule.c
index 5be9c0c82444..9c9fd7fdac6d 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -761,17 +761,6 @@ void chain_free(struct chain *chain)
 	xfree(chain);
 }
 
-struct chain *chain_lookup(const struct table *table, const struct handle *h)
-{
-	struct chain *chain;
-
-	list_for_each_entry(chain, &table->cache_chain, cache_list) {
-		if (!strcmp(chain->handle.chain.name, h->chain.name))
-			return chain;
-	}
-	return NULL;
-}
-
 struct chain *chain_binding_lookup(const struct table *table,
 				   const char *chain_name)
 {
@@ -2625,7 +2614,7 @@ static int do_command_rename(struct netlink_ctx *ctx, struct cmd *cmd)
 
 	switch (cmd->obj) {
 	case CMD_OBJ_CHAIN:
-		chain = chain_lookup(table, &cmd->handle);
+		chain = chain_cache_find(table, &cmd->handle);
 
 		return mnl_nft_chain_rename(ctx, cmd, chain);
 	default:
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 4+ messages in thread
* [PATCH nft 4/4] cache: statify chain_cache_dump()
  2021-04-01 20:29 [PATCH nft 1/4] cache: rename chain_htable to cache_chain_ht Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 2/4,v2] src: split chain list in table Pablo Neira Ayuso
  2021-04-01 20:29 ` [PATCH nft 3/4] evaluate: use chain hashtable for lookups Pablo Neira Ayuso
@ 2021-04-01 20:29 ` Pablo Neira Ayuso
  2 siblings, 0 replies; 4+ messages in thread
From: Pablo Neira Ayuso @ 2021-04-01 20:29 UTC (permalink / raw)
  To: netfilter-devel

Only used internally in cache.c

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/cache.h | 1 -
 src/cache.c     | 3 ++-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/cache.h b/include/cache.h
index a892b7fcdcb9..087f9ba96848 100644
--- a/include/cache.h
+++ b/include/cache.h
@@ -56,7 +56,6 @@ int cache_init(struct netlink_ctx *ctx, unsigned int flags);
 int cache_update(struct nft_ctx *nft, unsigned int flags, struct list_head *msgs);
 void cache_release(struct nft_cache *cache);
 
-struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx, int *err);
 void chain_cache_add(struct chain *chain, struct table *table);
 struct chain *chain_cache_find(const struct table *table,
 			       const struct handle *handle);
diff --git a/src/cache.c b/src/cache.c
index c9e1f22a3291..f7187ee7237f 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -217,7 +217,8 @@ static int chain_cache_init(struct netlink_ctx *ctx, struct table *table,
 	return 0;
 }
 
-struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx, int *err)
+static struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx,
+						 int *err)
 {
 	struct nftnl_chain_list *chain_list;
 
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 4+ messages in thread
end of thread, other threads:[~2021-04-01 20:29 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-01 20:29 [PATCH nft 1/4] cache: rename chain_htable to cache_chain_ht Pablo Neira Ayuso
2021-04-01 20:29 ` [PATCH nft 2/4,v2] src: split chain list in table Pablo Neira Ayuso
2021-04-01 20:29 ` [PATCH nft 3/4] evaluate: use chain hashtable for lookups Pablo Neira Ayuso
2021-04-01 20:29 ` [PATCH nft 4/4] cache: statify chain_cache_dump() Pablo Neira Ayuso

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.