Skip to contentSkip to conversation

Speed up restoring huge rulesets

RFC In review Phil Sutter 2 participants 7 messages Mar 4, 2022 – Mar 10, 2022 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

cover Speed up restoring huge rulesets

Spinning further on my OpenShift sample ruleset with 50k chains and 130k rules (of which 90k jump to a chain), I discovered old work in a local branch which surprisingly worked and is contained in patch 1:

Cache target lookup results if they failed. This speeds up the logic to determine whether the rule's target is a chain for consecutive rules jumping to that same chain. The cache does not care about table names, but that's fine: If a given chain name is not an extension, that holds for all chains of the same name in all tables.

Patch 2 goes even further by populating that cache from declared chains in the parsed dump file. This is potentially problematic because it effectively disables the chain name and extension clash check (which didn't exist in nft-variant and was a warning only in legacy), and it does that for all tables. So in theory, one could create a chain named LOG in nat table and expect to still be able to use LOG target in filter table. With patch 2 applied, the restore will fail.

I still find the series feasible despite its problems: The performance improvement is immense (see numbers in patches) and it breaks only corner-cases which are likely unintended anyway.

Phil Sutter (2):
libxtables: Implement notargets hash table
libxtables: Boost rule target checks by announcing chain names

 include/xtables.h           |  3 ++
 iptables/iptables-restore.c |  1 +
 iptables/xtables-restore.c  |  1 +
 libxtables/xtables.c        | 84 +++++++++++++++++++++++++++++++++++++
 4 files changed, 89 insertions(+)
Signature · 1 line
2.34.1
author reviewer
#1 lore raw

RFC 1/2 libxtables: Implement notargets hash table

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.

A sample ruleset involving 50k user-defined chains and 130k rules of which 90k contain a chain jump restores significantly faster on my testing VM:

variant old new
---------------------------
legacy 1m12s 37s
nft 1m35s 53s

---
 libxtables/xtables.c | 78 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)
libxtables/xtables.c +78 -0
index 094cbd87ec1ed..3cb9a87c9406d 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,72 @@ 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);
+	cur->name[0] = '\0';
+	strcat(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 +351,8 @@ void xtables_init(void)
 		return;
 	}
 	xtables_libdir = XTABLES_LIBDIR;
+
+	notargets_hlist_init();
 }
 
 void xtables_fini(void)
@@ -291,6 +360,7 @@ void xtables_fini(void)
 #ifndef NO_SHARED_LIBS
 	dlreg_free();
 #endif
+	notargets_hlist_free();
 }
 
 void xtables_set_nfproto(uint8_t nfproto)
@@ -820,8 +890,14 @@ xtables_find_target(const char *name, enum xtables_tryload tryload)
 	struct xtables_target *prev = NULL;
 	struct xtables_target **dptr;
 	struct xtables_target *ptr;
+	struct notarget *notgt;
 	bool found = false;
 
+	/* known non-target? */
+	notgt = notargets_hlist_lookup(name);
+	if (notgt && tryload != XTF_LOAD_MUST_SUCCEED)
+		return NULL;
+
 	/* Standard target? */
 	if (strcmp(name, "") == 0
 	    || strcmp(name, XTC_LABEL_ACCEPT) == 0
@@ -894,6 +970,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
#2 lore raw

Re: [iptables RFC 1/2] libxtables: Implement notargets hash table

libxtables/xtables.c static void dlreg_free(void) · line 321

Quoted 10 lines · Phil Sutter
libxtables/xtables.c +10 -0
+static void notargets_hlist_insert(const char *name)
+{
+	struct notarget *cur;
+
+	if (!name)
+		return;
+
+	cur = xtables_malloc(sizeof(*cur) + strlen(name) + 1);
+	cur->name[0] = '\0';
+	strcat(cur->name, name);

strcpy seems more readable than strcat here.
Other than that this looks good to me.

author reviewer
#3 lore raw

Re: [iptables RFC 1/2] libxtables: Implement notargets hash table

Quoted 13 lines · Florian Westphal

libxtables/xtables.c static void dlreg_free(void) · line 321

Quoted 10 lines · Phil Sutter
libxtables/xtables.c +10 -0
+static void notargets_hlist_insert(const char *name)
+{
+	struct notarget *cur;
+
+	if (!name)
+		return;
+
+	cur = xtables_malloc(sizeof(*cur) + strlen(name) + 1);
+	cur->name[0] = '\0';
+	strcat(cur->name, name);

strcpy seems more readable than strcat here.

Oh, indeed. Looks like an old attempt at avoiding strncpy() compiler warnings. ;)

Thanks, Phil

author reviewer
#4 lore raw

RFC 2/2 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 extension searches for them when parsing rules jumping to them later.

This is kind of a double-edged blade: the obvious downside is that *tables-restore won't detect user-defined chain name and extension clashes anymore. The upside is a tremendous performance improvement restoring large rulesets. The same crooked ruleset as mentioned in earlier patches (50k chains, 130k rules of which 90k jump to a chain) yields these numbers:

variant unoptimized non-targets cache announced chains
----------------------------------------------------------------
legacy 1m12s 37s 2.5s
nft 1m35s 53s 8s

Note that iptables-legacy-restore allows the clashes already as long as the name does not match a standard target, but with this patch it stops warning about it. iptables-nft-restore does not care at all, even allows adding a chain named 'ACCEPT' (and rules can't reach it because '-j ACCEPT' translates to a native nftables verdict). The latter is a bug by itself.

---
 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 81b25a43c9a04..4f9ffefdfab22 100644
@@ -201,6 +201,7 @@ static void xtables_restore_parse_line(struct nft_handle *h,
 				      policy, chain, line,
 				      strerror(errno));
 		}
+		xtables_announce_chain(chain);
 		ret = 1;
 	} else if (state->in_table) {
 		char *pcnt = NULL;
libxtables/xtables.c +6 -0
index 3cb9a87c9406d..96ba16014af46 100644
@@ -322,6 +322,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
#5 lore raw

Re: [iptables RFC 2/2] libxtables: Boost rule target checks by announcing chain names

Quoted 11 lines · Phil Sutter

This is kind of a double-edged blade: the obvious downside is that *tables-restore won't detect user-defined chain name and extension clashes anymore. The upside is a tremendous performance improvement restoring large rulesets. The same crooked ruleset as mentioned in earlier patches (50k chains, 130k rules of which 90k jump to a chain) yields these numbers:

variant unoptimized non-targets cache announced chains
----------------------------------------------------------------
legacy 1m12s 37s 2.5s
nft 1m35s 53s 8s

I think the benefits outweight the possible issues.

Quoted 3 lines

Note that iptables-legacy-restore allows the clashes already as long as the name does not match a standard target, but with this patch it stops warning about it.

Hmm. That seems fixable by refusing the announce in the clash case?

Quoted 4 lines

iptables-nft-restore does not care at all, even allows adding a chain named 'ACCEPT' (and rules can't reach it because '-j ACCEPT' translates to a native nftables verdict). The latter is a bug by itself.

Agree, thats a bug, it should not allow users to do that.

author reviewer
#6 lore raw

Re: [iptables RFC 2/2] libxtables: Boost rule target checks by announcing chain names

Quoted 13 lines · Florian Westphal
Quoted 11 lines · Phil Sutter

This is kind of a double-edged blade: the obvious downside is that *tables-restore won't detect user-defined chain name and extension clashes anymore. The upside is a tremendous performance improvement restoring large rulesets. The same crooked ruleset as mentioned in earlier patches (50k chains, 130k rules of which 90k jump to a chain) yields these numbers:

variant unoptimized non-targets cache announced chains
----------------------------------------------------------------
legacy 1m12s 37s 2.5s
nft 1m35s 53s 8s

Quoted 7 lines

I think the benefits outweight the possible issues.

Quoted 3 lines

Note that iptables-legacy-restore allows the clashes already as long as the name does not match a standard target, but with this patch it stops warning about it.

Hmm. That seems fixable by refusing the announce in the clash case?

When parsing a chain line, iptables-restore does not know there is a clash because this series effectively disables that check. Due to the non-targets hash, any chain name is looked up (as target) only once anyway, so keeping that check in iptables-restore yields the same performance as without the annotate.

Quoted 6 lines
Quoted 4 lines

iptables-nft-restore does not care at all, even allows adding a chain named 'ACCEPT' (and rules can't reach it because '-j ACCEPT' translates to a native nftables verdict). The latter is a bug by itself.

Agree, thats a bug, it should not allow users to do that.

ACK, I'll find a fix. In legacy, libiptc (TC_CREATE_CHAIN) does it, so an nft-specific one it will be.

Thanks, Phil