Re: [PATCH] netfilter: Reverse nft_set_lookup_byid list traversal

[Pablo Neira Ayuso <pablo@netfilter.org>]

Hi Jan-Phillip,

On Thu, Jan 07, 2021 at 09:56:42AM +0100, Jan-Philipp Litza wrote:
> When loading a large ruleset with many anonymous sets,
> nft_set_lookup_global is called once for each added set element, which
> in turn calls nft_set_lookup_byid if the set was only added in this
> transaction.
> 
> The longer this transaction's queue of unapplied netlink messages gets,
> the longer it takes to traverse it in search for the set referenced by
> ID that was probably added near the end if it is an anonymous set. This
> patch hence searches the list of unapplied netlink messages in reverse
> order, finding the just-added anonymous set faster.
> 
> On some reallife ruleset of ~6000 statements and ~1000 anonymous sets,
> this patch roughly halves the system time on loading:
> 
> Before: 0,06s user 0,39s system 97% cpu 0,459 total
> After:  0,06s user 0,20s system 97% cpu 0,268 total
> 
> The downside might be that newly added non-anonymous named sets are
> probably added at the beginning of a transaction, and looking for them
> when adding elements later on takes longer. However, I reckon that named
> sets too are more often filled right after their creation. Furthermore,
> for named sets, users can optimize their rule structure to add elements
> right after set creation, whereas it's impossible to first create all
> anonymous sets at the beginning of the transaction to optimize for the
> current approach.

If the .nft file contains lots of (linear syntax):

add rule x y ... { ... }
...
add rule x y ... { ... }

then, this patch is a real gain. In this case, nft currently places
the new anonymous set right before the rule, so your patch makes it
perform nicely.

I hesitate with the nested syntax, ie.

table x {
       chain y {
                ... { ... }
                ...
                ... { ... }
       }
}

In this case, nft adds all the anonymous sets at the beginning of the
netlink message, then rules don't find it right at the end.

Probably it's better to convert this code to use a rhashtable for fast
lookups on the transaction so we don't mind about what userspace does
in the future.

Thanks.

> Signed-off-by: Jan-Philipp Litza <jpl@plutex.de>
> ---
>  net/netfilter/nf_tables_api.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
> index 8d5aa0ac4..c488b6b95 100644
> --- a/net/netfilter/nf_tables_api.c
> +++ b/net/netfilter/nf_tables_api.c
> @@ -3639,7 +3639,7 @@ static struct nft_set *nft_set_lookup_byid(const struct net *net,
>  	struct nft_trans *trans;
>  	u32 id = ntohl(nla_get_be32(nla));
>  
> -	list_for_each_entry(trans, &net->nft.commit_list, list) {
> +	list_for_each_entry_reverse(trans, &net->nft.commit_list, list) {
>  		if (trans->msg_type == NFT_MSG_NEWSET) {
>  			struct nft_set *set = nft_trans_set(trans);
>  
> --
> 2.27.0
>