[iptables RFC 0/2] Speed up restoring huge rulesets

[iptables RFC 0/2] Speed up restoring huge rulesets

[Phil Sutter]

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(+)

-- 
2.34.1

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

[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.

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

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 libxtables/xtables.c | 78 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 094cbd87ec1ed..3cb9a87c9406d 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -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;
 }
-- 
2.34.1

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

[Florian Westphal]

Phil Sutter <phil@nwl.cc> wrote:
> +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.

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

[Phil Sutter]

On Thu, Mar 10, 2022 at 01:17:48PM +0100, Florian Westphal wrote:
> Phil Sutter <phil@nwl.cc> wrote:
> > +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

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

[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.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 include/xtables.h           | 3 +++
 iptables/iptables-restore.c | 1 +
 iptables/xtables-restore.c  | 1 +
 libxtables/xtables.c        | 6 ++++++
 4 files changed, 11 insertions(+)

diff --git a/include/xtables.h b/include/xtables.h
index ca674c2663eb4..816a157d5577d 100644
--- a/include/xtables.h
+++ b/include/xtables.h
@@ -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... */
diff --git a/iptables/iptables-restore.c b/iptables/iptables-restore.c
index 1917fb2315665..4cf0d3dadead9 100644
--- a/iptables/iptables-restore.c
+++ b/iptables/iptables-restore.c
@@ -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) {
diff --git a/iptables/xtables-restore.c b/iptables/xtables-restore.c
index 81b25a43c9a04..4f9ffefdfab22 100644
--- a/iptables/xtables-restore.c
+++ b/iptables/xtables-restore.c
@@ -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;
diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 3cb9a87c9406d..96ba16014af46 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -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. */
-- 
2.34.1

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

[Florian Westphal]

Phil Sutter <phil@nwl.cc> wrote:
> 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.

> 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?

> 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.

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

[Phil Sutter]

On Thu, Mar 10, 2022 at 01:21:57PM +0100, Florian Westphal wrote:
> Phil Sutter <phil@nwl.cc> wrote:
> > 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.
> 
> > 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.

> > 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