Skip to contentSkip to conversation

Speed up restoring huge rulesets

PATCH In review Phil Sutter 2 participants 7 messages Mar 16, 2022 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

cover Speed up restoring huge rulesets

The largest penalty when restoring a large ruleset is checking for whether a given target name is a chain or extension. Patch 2 adds a cache to libxtables for failed extension lookups so consecutive ones (e.g. multiple rules jumping to the same chain) are fast.

If a ruleset contains many user-defined chains, there is still a significant slow-down due to the single extension lookup which remains. Patch 3 introduces an announcement mechanism, implying that a chain line in a dump file is never a target.

Testing my OCP ruleset (50k chains, 130k rules, 90k chain jumps) again:

variant before after
-------------------------------------
legacy 1m31s 2.6s
nft 1m47s 13s

The performance gain is large enough to justify the lost warning if a chain name clashes with a non-standard target. The only case which was forbidden before, namely a clash with standard target (DROP, ACCEPT, etc.) is still caught due to patch 1 of this series.

Changes since RFC:
- Introduce patch 1 to catch the only real issue
- Slight performance drop with nft due to the kept standard target check
- Update commit messages

Phil Sutter (3):
nft: Reject standard targets as chain names when restoring
libxtables: Implement notargets hash table
libxtables: Boost rule target checks by announcing chain names

 include/xtables.h           |  3 ++
 iptables/iptables-restore.c |  1 +
 iptables/xshared.c          |  4 +-
 iptables/xshared.h          |  2 +-
 iptables/xtables-restore.c  |  6 +--
 libxtables/xtables.c        | 81 +++++++++++++++++++++++++++++++++++++
 6 files changed, 90 insertions(+), 7 deletions(-)
Signature · 1 line
2.34.1
author reviewer
#1 lore raw

PATCH 1/3 nft: Reject standard targets as chain names when restoring

Reuse parse_chain() called from do_parse() for '-N' and rename it for a better description of what it does.

Note that by itself, this patch will likely kill iptables-restore performance for big rulesets due to the extra extension lookup for chain lines. A following patch announcing those chains to libxtables will alleviate that.

---
 iptables/xshared.c         | 4 ++--
 iptables/xshared.h         | 2 +-
 iptables/xtables-restore.c | 5 +----
 3 files changed, 4 insertions(+), 7 deletions(-)
iptables/xshared.c +2 -2
index 43321d3b5358c..00828c8ae87d9 100644
@@ -1031,7 +1031,7 @@ set_option(unsigned int *options, unsigned int option, u_int16_t *invflg,
 	}
 }
 
-void parse_chain(const char *chainname)
+void assert_valid_chain_name(const char *chainname)
 {
 	const char *ptr;
 
@@ -1412,7 +1412,7 @@ void do_parse(int argc, char *argv[],
 			break;
 
 		case 'N':
-			parse_chain(optarg);
+			assert_valid_chain_name(optarg);
 			add_command(&p->command, CMD_NEW_CHAIN, CMD_NONE,
 				    invert);
 			p->chain = optarg;
iptables/xshared.h +1 -1
index 0de0e12e5a922..ca761ee7246ad 100644
@@ -244,7 +244,7 @@ char cmd2char(int option);
 void add_command(unsigned int *cmd, const int newcmd,
 		 const int othercmds, int invert);
 int parse_rulenumber(const char *rule);
-void parse_chain(const char *chainname);
+void assert_valid_chain_name(const char *chainname);
 
 void generic_opt_check(int command, int options);
 char opt2char(int option);
iptables/xtables-restore.c +1 -4
index 81b25a43c9a04..c94770a0175eb 100644
@@ -155,10 +155,7 @@ static void xtables_restore_parse_line(struct nft_handle *h,
 				   "%s: line %u chain name invalid\n",
 				   xt_params->program_name, line);
 
-		if (strlen(chain) >= XT_EXTENSION_MAXNAMELEN)
-			xtables_error(PARAMETER_PROBLEM,
-				   "Invalid chain name `%s' (%u chars max)",
-				   chain, XT_EXTENSION_MAXNAMELEN - 1);
+		assert_valid_chain_name(chain);
 
 		policy = strtok(NULL, " \t\n");
 		DEBUGP("line %u, policy '%s'\n", line, policy);
Signature · 1 line
2.34.1
maintainer Reviewed-by on v1 1/3
#2 lore raw

Re: [iptables PATCH 1/3] nft: Reject standard targets as chain names when restoring

Quoted 7 lines · Phil Sutter

Reuse parse_chain() called from do_parse() for '-N' and rename it for a better description of what it does.

Note that by itself, this patch will likely kill iptables-restore performance for big rulesets due to the extra extension lookup for chain lines. A following patch announcing those chains to libxtables will alleviate that.

author reviewer
#3 lore raw

PATCH 2/3 libxtables: Implement notargets hash table

In reply to Phil Sutter

Target lookup is relatively costly due to the filesystem access. Avoid this overhead in huge rulesets which contain many chain jumps by caching the failed lookups into a hashtable for later.

---
 libxtables/xtables.c | 75 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
libxtables/xtables.c +75 -0
index 094cbd87ec1ed..49790046a79d8 100644
@@ -49,6 +49,7 @@
 #include <linux/netfilter_ipv4/ip_tables.h>
 #include <linux/netfilter_ipv6/ip6_tables.h>
 #include <libiptc/libxtc.h>
+#include <libiptc/linux_list.h>
 
 #ifndef NO_SHARED_LIBS
 #include <dlfcn.h>
@@ -255,6 +256,71 @@ static void dlreg_free(void)
 }
 #endif
 
+struct notarget {
+	struct hlist_node node;
+	char name[];
+};
+
+#define NOTARGET_HSIZE	512
+static struct hlist_head notargets[NOTARGET_HSIZE];
+
+static void notargets_hlist_init(void)
+{
+	int i;
+
+	for (i = 0; i < NOTARGET_HSIZE; i++)
+		INIT_HLIST_HEAD(&notargets[i]);
+}
+
+static void notargets_hlist_free(void)
+{
+	struct hlist_node *pos, *n;
+	struct notarget *cur;
+	int i;
+
+	for (i = 0; i < NOTARGET_HSIZE; i++) {
+		hlist_for_each_entry_safe(cur, pos, n, &notargets[i], node) {
+			hlist_del(&cur->node);
+			free(cur);
+		}
+	}
+}
+
+static 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;
+}
+
+static struct notarget *notargets_hlist_lookup(const char *name)
+{
+	uint32_t key = djb_hash(name) % NOTARGET_HSIZE;
+	struct hlist_node *node;
+	struct notarget *cur;
+
+	hlist_for_each_entry(cur, node, &notargets[key], node) {
+		if (!strcmp(name, cur->name))
+			return cur;
+	}
+	return NULL;
+}
+
+static void notargets_hlist_insert(const char *name)
+{
+	struct notarget *cur;
+
+	if (!name)
+		return;
+
+	cur = xtables_malloc(sizeof(*cur) + strlen(name) + 1);
+	strcpy(cur->name, name);
+	hlist_add_head(&cur->node, &notargets[djb_hash(name) % NOTARGET_HSIZE]);
+}
+
 void xtables_init(void)
 {
 	/* xtables cannot be used with setuid in a safe way. */
@@ -284,6 +350,8 @@ void xtables_init(void)
 		return;
 	}
 	xtables_libdir = XTABLES_LIBDIR;
+
+	notargets_hlist_init();
 }
 
 void xtables_fini(void)
@@ -291,6 +359,7 @@ void xtables_fini(void)
 #ifndef NO_SHARED_LIBS
 	dlreg_free();
 #endif
+	notargets_hlist_free();
 }
 
 void xtables_set_nfproto(uint8_t nfproto)
@@ -829,6 +898,10 @@ xtables_find_target(const char *name, enum xtables_tryload tryload)
 	    || strcmp(name, XTC_LABEL_QUEUE) == 0
 	    || strcmp(name, XTC_LABEL_RETURN) == 0)
 		name = "standard";
+	/* known non-target? */
+	else if (notargets_hlist_lookup(name) &&
+		 tryload != XTF_LOAD_MUST_SUCCEED)
+		return NULL;
 
 	/* Trigger delayed initialization */
 	for (dptr = &xtables_pending_targets; *dptr; ) {
@@ -894,6 +967,8 @@ xtables_find_target(const char *name, enum xtables_tryload tryload)
 
 	if (ptr)
 		ptr->used = 1;
+	else
+		notargets_hlist_insert(name);
 
 	return ptr;
 }
Signature · 1 line
2.34.1
maintainer Acked-by on v1 2/3
#4 lore raw

Re: [iptables PATCH 2/3] libxtables: Implement notargets hash table

Quoted 3 lines · Phil Sutter

Target lookup is relatively costly due to the filesystem access. Avoid this overhead in huge rulesets which contain many chain jumps by caching the failed lookups into a hashtable for later.

author reviewer
#5 lore raw

PATCH 3/3 libxtables: Boost rule target checks by announcing chain names

In reply to Phil Sutter

When restoring a ruleset, feed libxtables with chain names from respective lines to avoid an extension search.

While the user's intention is clear, this effectively disables the sanity check for clashes with target extensions. But:

* The check yielded only a warning and the clashing chain was finally accepted.

* Users crafting iptables dumps for feeding into iptables-restore likely know what they're doing.

---
 include/xtables.h           | 3 +++
 iptables/iptables-restore.c | 1 +
 iptables/xtables-restore.c  | 1 +
 libxtables/xtables.c        | 6 ++++++
 4 files changed, 11 insertions(+)
include/xtables.h +3 -0
index ca674c2663eb4..816a157d5577d 100644
@@ -645,6 +645,9 @@ const char *xt_xlate_get(struct xt_xlate *xl);
 #define xt_xlate_rule_get xt_xlate_get
 const char *xt_xlate_set_get(struct xt_xlate *xl);
 
+/* informed target lookups */
+void xtables_announce_chain(const char *name);
+
 #ifdef XTABLES_INTERNAL
 
 /* Shipped modules rely on this... */
iptables/iptables-restore.c +1 -0
index 1917fb2315665..4cf0d3dadead9 100644
@@ -308,6 +308,7 @@ ip46tables_restore_main(const struct iptables_restore_cb *cb,
 						cb->ops->strerror(errno));
 			}
 
+			xtables_announce_chain(chain);
 			ret = 1;
 
 		} else if (in_table) {
iptables/xtables-restore.c +1 -0
index c94770a0175eb..8ee0bb91f7d44 100644
@@ -155,6 +155,7 @@ static void xtables_restore_parse_line(struct nft_handle *h,
 				   "%s: line %u chain name invalid\n",
 				   xt_params->program_name, line);
 
+		xtables_announce_chain(chain);
 		assert_valid_chain_name(chain);
 
 		policy = strtok(NULL, " \t\n");
libxtables/xtables.c +6 -0
index 49790046a79d8..60e7c6e90b448 100644
@@ -321,6 +321,12 @@ static void notargets_hlist_insert(const char *name)
 	hlist_add_head(&cur->node, &notargets[djb_hash(name) % NOTARGET_HSIZE]);
 }
 
+void xtables_announce_chain(const char *name)
+{
+	if (!notargets_hlist_lookup(name))
+		notargets_hlist_insert(name);
+}
+
 void xtables_init(void)
 {
 	/* xtables cannot be used with setuid in a safe way. */
Signature · 1 line
2.34.1
maintainer Acked-by on v1 3/3
#6 lore raw

Re: [iptables PATCH 3/3] libxtables: Boost rule target checks by announcing chain names

Quoted 11 lines · Phil Sutter

When restoring a ruleset, feed libxtables with chain names from respective lines to avoid an extension search.

While the user's intention is clear, this effectively disables the sanity check for clashes with target extensions. But:

* The check yielded only a warning and the clashing chain was finally accepted.

* Users crafting iptables dumps for feeding into iptables-restore likely know what they're doing.