netfilter: nat: do not use rhltable
Subsystems (2)
Florian Westphal
maintainercover netfilter: nat: do not use rhltable
This reverts the conversion of the nat bysource table to rhlist that I did last year.
It was a bad idea to begin with.
Fast lookup is not essential; in most cases there is no lookup at all because original tuple is not taken and can be used as-is. What needs to be fast is insertion and deletion.
With rhlist, deletion is slow as it requires a list traversal. So, switch back to a statically-sized table for bysource hash.
include/net/netfilter/nf_conntrack.h | 3 include/net/netfilter/nf_nat.h | 1 net/netfilter/nf_nat_core.c | 142 ++++++++++++++++------------------- 3 files changed, 66 insertions(+), 80 deletions(-)
Florian Westphal
maintainerPATCH 1/2 netfilter: nat: Revert "netfilter: nat: convert nat bysrc hash to rhashtable"
This reverts commit 870190a9ec9075205c0fa795a09fa931694a3ff1.
It was not a good idea. The custom hash table was a much better fit for this purpose.
A fast lookup is not essential, in fact for most cases there is no lookup at all because original tuple is not taken and can be used as-is. What needs to be fast is insertion and deletion.
rhlist removal however requires a rhlist walk.
We can have thousands of entries in such a list if source port/addresses are reused for multiple flows, if this happens removal requests are so expensive that deletions of a few thousand flows can take several seconds(!).
The advantages that we got from rhashtable are:
1) table auto-sizing
2) multiple locks
1) would be nice to have, but it is not essential as we have at most one lookup per new flow, so even a million flows in the bysource table are not a problem compared to current deletion cost.
2) is easy to add to custom hash table.
I tried to add hlist_node to rhlist to speed up rhltable_remove but this isn't doable without changing semantics. rhltable_remove_fast will check that the to-be-deleted object is part of the table and that requires a list walk that we want to avoid.
Furthermore, using hlist_node increases size of struct rhlist_head, which in turn increases nf_conn size.
--- include/net/netfilter/nf_conntrack.h | 3 +- include/net/netfilter/nf_nat.h | 1 - net/netfilter/nf_nat_core.c | 130 ++++++++++++++--------------------- 3 files changed, 54 insertions(+), 80 deletions(-)
include/net/netfilter/nf_conntrack.h +1 -2
@@ -17,7 +17,6 @@#include <linux/bitops.h> #include <linux/compiler.h> #include <linux/atomic.h> -#include <linux/rhashtable.h> #include <linux/netfilter/nf_conntrack_tcp.h> #include <linux/netfilter/nf_conntrack_dccp.h>
@@ -83,7 +82,7 @@ struct nf_conn {possible_net_t ct_net;#if IS_ENABLED (CONFIG_NF_NAT ) -struct rhlist_head nat_bysource; +struct hlist_node nat_bysource;#endif /* all members below initialized via memset */ u8 __nfct_init_offset[0 ];
include/net/netfilter/nf_nat.h +0 -1
@@ -1,6 +1,5 @@#ifndef _NF_NAT_H#define _NF_NAT_H -#include <linux/rhashtable.h> #include <linux/netfilter_ipv4.h> #include <linux/netfilter/nf_nat.h> #include <net/netfilter/nf_conntrack_tuple.h>
net/netfilter/nf_nat_core.c +53 -77
206 lines not on this page · raw message
Signature · 1 line
2.13.0
A message that is not in the archive (sent off-list or not yet received): CAFoGUiyjXxgYBU+POj2_x3H9BXPW=FUGr3LS3KNUDdxDL0vbng@mail.gmail.com
Florian Westphal
maintainerRe: [PATCH nf 1/2] netfilter: nat: Revert "netfilter: nat: convert nat bysrc hash to rhashtable"
Quoted 10 lines · Dao Quang Minh
Thanks for the patch !
Quoted 1 line
rhlist removal however requires a rhlist walk.
We can have thousands of entries in such a list if source port/addresses are reused for multiple flows, if this happens removal requests are so expensive that deletions of a few thousand flows can take several seconds(!).
Do you think rhlist can use double linked list instead of single linked so removal doesn't need to walk the whole chain ?
Yes, but:
Quoted 7 lines
Quoted 7 lines
I tried to add
hlist_nodeto rhlist to speed uprhltable_removebut this isn't doable without changing semantics.rhltable_remove_fastwill check that the to-be-deleted object is part of the table and that requires a list walk that we want to avoid.Furthermore, using
hlist_nodeincreases size of structrhlist_head, which in turn increasesnf_connsize.
Florian Westphal
maintainerPATCH 2/2 netfilter: nat: use keyed locks
In reply to Florian Westphalno need to serialize on a single lock, we can partition the table and add/delete in parallel to different slots.
This restores one of the advantages that got lost with the rhlist revert.
--- net/netfilter/nf_nat_core.c | 36 ++++++++++++++++++++++++------------ 1 file changed, 24 insertions(+), 12 deletions(-)
net/netfilter/nf_nat_core.c +24 -12
@@ -30,7 +30,7 @@#include <net/netfilter/nf_conntrack_zones.h> #include <linux/netfilter/nf_nat.h> -static DEFINE_SPINLOCK (nf_nat_lock); +static spinlock_t nf_nat_locks[CONNTRACK_LOCKS ];static DEFINE_MUTEX (nf_nat_proto_mutex);static const struct nf_nat_l3proto __rcu *nf_nat_l3protos[NFPROTO_NUMPROTO ]
@@ -423,13 +423,15 @@ nf_nat_setup_info(struct nf_conn *ct,if (maniptype ==NF_NAT_MANIP_SRC ) {unsigned int srchash; +spinlock_t *lock; srchash =hash_by_src (net, &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple); -spin_lock_bh (&nf_nat_lock); + lock = &nf_nat_locks[srchash %ARRAY_SIZE (nf_nat_locks)]; +spin_lock_bh (lock);hlist_add_head_rcu (&ct->nat_bysource, &nf_nat_bysource[srchash]); -spin_unlock_bh (&nf_nat_lock); +spin_unlock_bh (lock); }/* It's done. */
@@ -523,6 +525,16 @@ static int nf_nat_proto_remove(struct nf_conn *i, void *data)return i->status &IPS_NAT_MASK ?1 :0 ; } +static void __nf_nat_cleanup_conntrack (struct nf_conn *ct) +{ +unsigned int h; + + h =hash_by_src (nf_ct_net (ct), &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple); +spin_lock_bh (&nf_nat_locks[h %ARRAY_SIZE (nf_nat_locks)]); +hlist_del_rcu (&ct->nat_bysource); +spin_unlock_bh (&nf_nat_locks[h %ARRAY_SIZE (nf_nat_locks)]); +} +static int nf_nat_proto_clean (struct nf_conn *ct,void *data) {if (nf_nat_proto_remove (ct, data))
@@ -538,9 +550,7 @@ static int nf_nat_proto_clean(struct nf_conn *ct, void *data)* will delete entry from already-freed table. */ clear_bit (IPS_SRC_NAT_DONE_BIT , &ct->status); -spin_lock_bh (&nf_nat_lock); -hlist_del_rcu (&ct->nat_bysource); -spin_unlock_bh (&nf_nat_lock); +__nf_nat_cleanup_conntrack (ct);/* don't delete conntrack. Although that would make things a lot * simpler, we'd end up flushing all conntracks on nat rmmod.
@@ -668,11 +678,8 @@ EXPORT_SYMBOL_GPL(nf_nat_l3proto_unregister);/* No one using conntrack by the time this called. */ static void nf_nat_cleanup_conntrack (struct nf_conn *ct) { -if (ct->status &IPS_SRC_NAT_DONE ) { -spin_lock_bh (&nf_nat_lock); -hlist_del_rcu (&ct->nat_bysource); -spin_unlock_bh (&nf_nat_lock); - } +if (ct->status &IPS_SRC_NAT_DONE ) +__nf_nat_cleanup_conntrack (ct); }static struct nf_ct_ext_type nat_extend__read_mostly = {
@@ -794,10 +801,12 @@ static struct nf_ct_helper_expectfn follow_master_nat = {static int __init nf_nat_init (void ) { -int ret; +int ret, i;/* Leave them the same for the moment. */ nf_nat_htable_size = nf_conntrack_htable_size; +if (nf_nat_htable_size <ARRAY_SIZE (nf_nat_locks)) + nf_nat_htable_size =ARRAY_SIZE (nf_nat_locks); nf_nat_bysource =nf_ct_alloc_hashtable (&nf_nat_htable_size,0 );if (!nf_nat_bysource)
@@ -810,6 +819,9 @@ static int __init nf_nat_init(void)return ret; } +for (i =0 ; i <ARRAY_SIZE (nf_nat_locks); i++) +spin_lock_init (&nf_nat_locks[i]); +nf_ct_helper_expectfn_register (&follow_master_nat);BUG_ON (nfnetlink_parse_nat_setup_hook !=NULL );
Signature · 1 line
2.13.0
Pablo Neira Ayuso
maintainerQuoted 11 lines · Florian Westphal
This reverts the conversion of the nat bysource table to rhlist that I did last year.
It was a bad idea to begin with.
Fast lookup is not essential; in most cases there is no lookup at all because original tuple is not taken and can be used as-is. What needs to be fast is insertion and deletion.
With rhlist, deletion is slow as it requires a list traversal. So, switch back to a statically-sized table for bysource hash.
Series applied.
Quoted 6 lines · Pablo Neira Ayuso
Quoted 5 lines · Florian Westphal
This reverts the conversion of the nat bysource table to rhlist that I did last year.
It was a bad idea to begin with.
Quoted 9 lines
Quoted 6 lines
Fast lookup is not essential; in most cases there is no lookup at all because original tuple is not taken and can be used as-is. What needs to be fast is insertion and deletion.
With rhlist, deletion is slow as it requires a list traversal. So, switch back to a statically-sized table for bysource hash.
Series applied.
We've hit this issue in production on Linux 4.9. Even though that's just a "performance" fix (as opposed to actual crash), I believe it's worth queuing it up to -stable (without it we've seen several freezes of 20 seconds and more).
Patch #1 needs minor editing before applying to 4.9. Not sure if patch #2 is worth backporting though. What do you think?