Speed up restoring huge rulesets
Phil Sutter
reviewercover 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
Phil Sutter
reviewerPATCH 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
@@ -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
@@ -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
@@ -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
Re: [iptables PATCH 1/3] nft: Reject standard targets as chain names when restoring
Quoted 7 lines · Phil Sutter
Reuse
parse_chain()called fromdo_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.
Phil Sutter
reviewerPATCH 2/3 libxtables: Implement notargets hash table
In reply to Phil SutterTarget 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
@@ -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 (¬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 ); +strcpy (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 +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
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.
Phil Sutter
reviewerPATCH 3/3 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 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
@@ -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
@@ -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
@@ -321,6 +321,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
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.