From 913979f882d13360cba11fd4402d193d74b0396a Mon Sep 17 00:00:00 2001
From: Pablo Neira Ayuso <pablo@netfilter.org>
Date: Thu, 20 Aug 2020 18:21:37 +0200
Subject: 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.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 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(-)

diff --git a/include/cache.h b/include/cache.h
index 213a6eaf..b9db1a8f 100644
--- a/include/cache.h
+++ b/include/cache.h
@@ -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_ */
diff --git a/include/netlink.h b/include/netlink.h
index 1077096e..ad2247e9 100644
--- a/include/netlink.h
+++ b/include/netlink.h
@@ -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 */
diff --git a/include/rule.h b/include/rule.h
index caca63d0..f2f82cc0 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -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
diff --git a/src/libnftables.c b/src/libnftables.c
index 668e3fc4..fce52ad4 100644
--- a/src/libnftables.c
+++ b/src/libnftables.c
@@ -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);
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 9e3ed53d..43d7ff82 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -27,6 +27,7 @@
 #include <erec.h>
 #include <sys/socket.h>
 #include <libnftnl/udata.h>
+#include <cache.h>
 #include <xt.h>
 
 static int netlink_parse_expr(const struct nftnl_expr *nle,
@@ -1627,12 +1628,14 @@ static void netlink_parse_objref(struct netlink_parse_ctx *ctx,
 	ctx->stmt = stmt;
 }
 
-static const struct {
+struct expr_handler {
 	const char	*name;
 	void		(*parse)(struct netlink_parse_ctx *ctx,
 				 const struct location *loc,
 				 const struct nftnl_expr *nle);
-} netlink_parsers[] = {
+};
+
+static const struct expr_handler netlink_parsers[] = {
 	{ .name = "immediate",	.parse = netlink_parse_immediate },
 	{ .name = "cmp",	.parse = netlink_parse_cmp },
 	{ .name = "lookup",	.parse = netlink_parse_lookup },
@@ -1673,25 +1676,48 @@ static const struct {
 	{ .name = "synproxy",	.parse = netlink_parse_synproxy },
 };
 
+static const struct expr_handler **expr_handle_ht;
+
+#define NFT_EXPR_HSIZE	4096
+
+void expr_handler_init(void)
+{
+	unsigned int i;
+	uint32_t hash;
+
+	expr_handle_ht = calloc(NFT_EXPR_HSIZE, sizeof(expr_handle_ht));
+	if (!expr_handle_ht)
+		memory_allocation_error();
+
+	for (i = 0; i < array_size(netlink_parsers); i++) {
+		hash = djb_hash(netlink_parsers[i].name) % NFT_EXPR_HSIZE;
+		assert(expr_handle_ht[hash] == NULL);
+		expr_handle_ht[hash] = &netlink_parsers[i];
+	}
+}
+
+void expr_handler_exit(void)
+{
+	xfree(expr_handle_ht);
+}
+
 static int netlink_parse_expr(const struct nftnl_expr *nle,
 			      struct netlink_parse_ctx *ctx)
 {
 	const char *type = nftnl_expr_get_str(nle, NFTNL_EXPR_NAME);
 	struct location loc;
-	unsigned int i;
+	uint32_t hash;
 
 	memset(&loc, 0, sizeof(loc));
 	loc.indesc = &indesc_netlink;
 	loc.nle = nle;
 
-	for (i = 0; i < array_size(netlink_parsers); i++) {
-		if (strcmp(type, netlink_parsers[i].name))
-			continue;
-		netlink_parsers[i].parse(ctx, &loc, nle);
-		return 0;
-	}
+	hash = djb_hash(type) % NFT_EXPR_HSIZE;
+	if (expr_handle_ht[hash])
+		expr_handle_ht[hash]->parse(ctx, &loc, nle);
+	else
+		netlink_error(ctx, &loc, "unknown expression type '%s'", type);
 
-	netlink_error(ctx, &loc, "unknown expression type '%s'", type);
 	return 0;
 }
 
-- 
cgit v1.2.3