[iptables PATCH 0/3] Speed up restoring huge rulesets

[iptables PATCH 0/3] Speed up restoring huge rulesets

[Phil Sutter]

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

-- 
2.34.1

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

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

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 iptables/xshared.c         | 4 ++--
 iptables/xshared.h         | 2 +-
 iptables/xtables-restore.c | 5 +----
 3 files changed, 4 insertions(+), 7 deletions(-)

diff --git a/iptables/xshared.c b/iptables/xshared.c
index 43321d3b5358c..00828c8ae87d9 100644
--- a/iptables/xshared.c
+++ b/iptables/xshared.c
@@ -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;
diff --git a/iptables/xshared.h b/iptables/xshared.h
index 0de0e12e5a922..ca761ee7246ad 100644
--- a/iptables/xshared.h
+++ b/iptables/xshared.h
@@ -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);
diff --git a/iptables/xtables-restore.c b/iptables/xtables-restore.c
index 81b25a43c9a04..c94770a0175eb 100644
--- a/iptables/xtables-restore.c
+++ b/iptables/xtables-restore.c
@@ -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);
-- 
2.34.1

[iptables PATCH 2/3] 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.

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

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 094cbd87ec1ed..49790046a79d8 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,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;
 }
-- 
2.34.1

[iptables PATCH 3/3] 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 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.

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 c94770a0175eb..8ee0bb91f7d44 100644
--- a/iptables/xtables-restore.c
+++ b/iptables/xtables-restore.c
@@ -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");
diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 49790046a79d8..60e7c6e90b448 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -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. */
-- 
2.34.1

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

[Florian Westphal]

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

Reviewed-by: Florian Westphal <fw@strlen.de>

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

[Florian Westphal]

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

Acked-by: Florian Westphal <fw@strlen.de>

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

[Florian Westphal]

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

Acked-by: Florian Westphal <fw@strlen.de>