Speed up restoring huge rulesets
Phil Sutter
reviewercover 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
Phil Sutter
reviewerRFC 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
@@ -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 (¬argets[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, ¬argets[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, ¬argets[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, ¬argets[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
Florian Westphal
maintainerRe: [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.
Phil Sutter
reviewerRe: [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
Phil Sutter
reviewerRFC 2/2 libxtables: Boost rule target checks by announcing chain names
In reply to Phil SutterWhen 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
@@ -645,6 +645,9 @@ const char *xt_xlate_get(struct xt_xlate *xl);#define xt_xlate_rule_get xt_xlate_getconst 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
@@ -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
@@ -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
@@ -322,6 +322,12 @@ static void notargets_hlist_insert(const char *name)hlist_add_head (&cur->node, ¬argets[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
Florian Westphal
maintainerRe: [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.
Phil Sutter
reviewerRe: [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