netfilter: nat: Revert "netfilter: nat: convert nat bysrc hash to rhashtable" hash to rhashtable"
PATCH v2 1/1 netfilter: nat: Revert "netfilter: nat: convert nat bysrc hash to rhashtable" hash to rhashtable"
commit e1bf1687740ce1a3598a1c5e452b852ff2190682 upstream.
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.
---
Hi Greg,
this is a 4.9.y backport of the same revert that already went into 4.13.y; please consider applying this.
Note: you need to 'git cherry-pick 6e699867f84c0f358fed233fe6162173aca28e04' first, else this won't apply (and cause crash if newly allocated conntrack is dropped right away).
include/net/netfilter/nf_conntrack.h | 3 +- include/net/netfilter/nf_nat.h | 1 - net/netfilter/nf_nat_core.c | 134 +++++++++++++++-------------------- 3 files changed, 57 insertions(+), 81 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>
@@ -101,7 +100,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 +56 -78
217 lines not on this page · raw message
Signature · 1 line
2.13.6
your patch is not clean
patching file net/netfilter/nf_nat_core.c Hunk #7 succeeded at 550 (offset 6 lines). Hunk #8 FAILED at 672.
Hunk #9 succeeded at 819 (offset 10 lines). Hunk #10 succeeded at 852 (offset 10 lines). Hunk #11 succeeded at 872 (offset 10 lines).
nf_nat_cleanup_conntrack is wrong
your patch
@@ -672,9 +645,11 @@ 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)
- rhltable_remove(&nf_nat_bysource_table, &ct->nat_bysource, - nf_nat_bysource_params);
+ 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);
+ }
}
original function
/* No one using conntrack by the time this called. */ static void nf_nat_cleanup_conntrack(struct nf_conn *ct) {
struct nf_conn_nat *nat = nf_ct_ext_find(ct, NF_CT_EXT_NAT);
if (!nat)
return;
rhltable_remove(&nf_nat_bysource_table, &ct->nat_bysource, nf_nat_bysource_params);
}
Am 15.11.2017 um 11:15 schrieb Florian Westphal:
Quoted 317 lines
commit
e1bf1687740ce1a3598a1c5e452b852ff2190682upstream.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 locks1) 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_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.Reported-by Ivan Babrou <[email protected]>Signed-off-by Florian Westphal <[email protected]>Signed-off-by Pablo Neira Ayuso <[email protected]>---
Hi Greg,this is a 4.9.y backport of the same revert that already went into 4.13.y; please consider applying this.
Note: you need to 'git cherry-pick
6e699867f84c0f358fed233fe6162173aca28e04' first, else this won't apply (and cause crash if newly allocated conntrack is dropped right away).include/net/netfilter/nf_conntrack.h | 3 +- include/net/netfilter/nf_nat.h | 1 - net/netfilter/nf_nat_core.c | 134 +++++++++++++++-------------------- 3 files changed, 57 insertions(+), 81 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> @@ -101,7 +100,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 +56
-78@@ -30,19 +30,17 @@#include <net/netfilter/nf_conntrack_zones.h> #include <linux/netfilter/nf_nat.h> +static DEFINE_SPINLOCK (nf_nat_lock); +static DEFINE_MUTEX (nf_nat_proto_mutex);static const struct nf_nat_l3proto __rcu *nf_nat_l3protos[NFPROTO_NUMPROTO ]__read_mostly ;static const struct nf_nat_l4proto __rcu **nf_nat_l4protos[NFPROTO_NUMPROTO ]__read_mostly ; -struct nf_nat_conn_key { -const struct net *net; -const struct nf_conntrack_tuple *tuple; -const struct nf_conntrack_zone *zone; -}; - -static struct rhltable nf_nat_bysource_table; +static struct hlist_head *nf_nat_bysource__read_mostly ; +static unsigned int nf_nat_htable_size__read_mostly ; +static unsigned int nf_nat_hash_rnd__read_mostly ;inline const struct nf_nat_l3proto *__nf_nat_l3proto_find (u8 family)@@ -121,17 +119,19 @@ int nf_xfrm_me_harder(struct net *net, struct sk_buff *skb, unsigned int family)EXPORT_SYMBOL (nf_xfrm_me_harder);#endif /* CONFIG_XFRM */ -static u32 nf_nat_bysource_hash (const void *data,u32 len,u32 seed) +/* We keep an extra hash for each conntrack, for fast searching. */ +static inline unsigned int +hash_by_src (const struct net *n,const struct nf_conntrack_tuple *tuple) { -const struct nf_conntrack_tuple *t; -const struct nf_conn *ct = data; +unsigned int hash; + +get_random_once (&nf_nat_hash_rnd,sizeof (nf_nat_hash_rnd)); - t = &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple;/* Original src, to ensure we map it consistently if poss. */ + hash =jhash2 ((u32 *)&tuple->src,sizeof (tuple->src) /sizeof (u32), + tuple->dst.protonum ^ nf_nat_hash_rnd ^net_hash_mix (n)); - seed ^=net_hash_mix (nf_ct_net (ct)); -return jhash2 ((const u32 *)&t->src,sizeof (t->src) /sizeof (u32), - t->dst.protonum ^ seed); +return reciprocal_scale (hash, nf_nat_htable_size); }/* Is this tuple already taken? (not by us) */ @@ -187,28 +187,6 @@ same_src(const struct nf_conn *ct, t->src.u.all == tuple->src.u.all); } -static int nf_nat_bysource_cmp (struct rhashtable_compare_arg *arg, -const void *obj) -{ -const struct nf_nat_conn_key *key = arg->key; -const struct nf_conn *ct = obj; - -if (!same_src (ct, key->tuple) || - !net_eq (nf_ct_net (ct), key->net) || - !nf_ct_zone_equal (ct, key->zone,IP_CT_DIR_ORIGINAL )) -return 1 ; - -return 0 ; -} - -static struct rhashtable_params nf_nat_bysource_params = { - .head_offset = offsetof(struct nf_conn , nat_bysource), - .obj_hashfn = nf_nat_bysource_hash, - .obj_cmpfn = nf_nat_bysource_cmp, - .nelem_hint =256 , - .min_size =1024 , -}; -/* Only called for SRC manip */ static int find_appropriate_src(struct net *net,@@ -219,26 +197,22 @@ find_appropriate_src(struct net *net,struct nf_conntrack_tuple *result, const struct nf_nat_range *range) { + unsigned int h = hash_by_src(net, tuple);const struct nf_conn *ct; -struct nf_nat_conn_key key = { - .net = net, - .tuple = tuple, - .zone = zone - }; -struct rhlist_head *hl, *h; - - hl =rhltable_lookup (&nf_nat_bysource_table, &key, - nf_nat_bysource_params); -rhl_for_each_entry_rcu (ct, h, hl, nat_bysource) { -nf_ct_invert_tuplepr (result, - &ct->tuplehash[IP_CT_DIR_REPLY ].tuple); - result->dst = tuple->dst; - -if (in_range (l3proto, l4proto, result, range)) -return 1 ; +hlist_for_each_entry_rcu (ct, &nf_nat_bysource[h], nat_bysource) { +if (same_src (ct, tuple) && +net_eq (net,nf_ct_net (ct)) && +nf_ct_zone_equal (ct, zone,IP_CT_DIR_ORIGINAL )) { +/* Copy source part from reply tuple. */ +nf_ct_invert_tuplepr (result, + &ct->tuplehash[IP_CT_DIR_REPLY ].tuple); + result->dst = tuple->dst; + +if (in_range (l3proto, l4proto, result, range)) +return 1 ; + } } -return 0 ; }@@ -411,6 +385,7 @@ nf_nat_setup_info(struct nf_conn *ct,const struct nf_nat_range *range, enum nf_nat_manip_type maniptype) { + struct net *net = nf_ct_net(ct);struct nf_conntrack_tuple curr_tuple, new_tuple;struct nf_conn_nat *nat;@@ -452,19 +427,16 @@ nf_nat_setup_info(struct nf_conn *ct, }if (maniptype ==NF_NAT_MANIP_SRC ) { -struct nf_nat_conn_key key = { - .net =nf_ct_net (ct), - .tuple = &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple, - .zone =nf_ct_zone (ct), - }; -int err; - - err =rhltable_insert_key (&nf_nat_bysource_table, - &key, - &ct->nat_bysource, - nf_nat_bysource_params); -if (err) -return NF_DROP ; +unsigned int srchash; + + srchash =hash_by_src (net, + &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple); +spin_lock_bh (&nf_nat_lock); +/* nf_conntrack_alter_reply might re-allocate extension aera */ + nat =nfct_nat (ct); +hlist_add_head_rcu (&ct->nat_bysource, + &nf_nat_bysource[srchash]); +spin_unlock_bh (&nf_nat_lock); }/* It's done. */ @@ -572,9 +544,10 @@ static int nf_nat_proto_clean(struct nf_conn *ct, void *data)* Else, when the conntrack is destoyed, nf_nat_cleanup_conntrack() * will delete entry from already-freed table. */ +spin_lock_bh (&nf_nat_lock); +hlist_del_rcu (&ct->nat_bysource); ct->status &= ~IPS_NAT_DONE_MASK ; -rhltable_remove (&nf_nat_bysource_table, &ct->nat_bysource, - nf_nat_bysource_params); +spin_unlock_bh (&nf_nat_lock);/* don't delete conntrack. Although that would make things a lot * simpler, we'd end up flushing all conntracks on nat rmmod. @@ -699,9 +672,11 @@ 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 ) -rhltable_remove (&nf_nat_bysource_table, &ct->nat_bysource, - nf_nat_bysource_params); +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); + } }static struct nf_ct_ext_type nat_extend__read_mostly = {@@ -836,13 +811,16 @@ static int __init nf_nat_init(void) {int ret; - ret =rhltable_init (&nf_nat_bysource_table, &nf_nat_bysource_params); -if (ret) -return ret; +/* Leave them the same for the moment. */ + nf_nat_htable_size = nf_conntrack_htable_size; + + nf_nat_bysource =nf_ct_alloc_hashtable (&nf_nat_htable_size,0 ); +if (!nf_nat_bysource) +return -ENOMEM ; ret =nf_ct_extend_register (&nat_extend);if (ret <0 ) { -rhltable_destroy (&nf_nat_bysource_table); +nf_ct_free_hashtable (nf_nat_bysource, nf_nat_htable_size);printk (KERN_ERR "nf_nat_core: Unable to register extension\n" );return ret; }@@ -866,7 +844,7 @@ static int __init nf_nat_init(void)return 0 ; cleanup_extend: -rhltable_destroy (&nf_nat_bysource_table); +nf_ct_free_hashtable (nf_nat_bysource, nf_nat_htable_size);nf_ct_extend_unregister (&nat_extend);return ret; }@@ -886,8 +864,8 @@ static void __exit nf_nat_cleanup(void)for (i =0 ; i <NFPROTO_NUMPROTO ; i++)kfree (nf_nat_l4protos[i]); - -rhltable_destroy (&nf_nat_bysource_table); +synchronize_net (); +nf_ct_free_hashtable (nf_nat_bysource, nf_nat_htable_size); }MODULE_LICENSE ("GPL" );
Signature · 11 lines
Mit freundlichen Grüssen / Regards Sebastian Gottschall / CTO NewMedia-NET GmbH - DD-WRT Firmensitz: Stubenwaldallee 21a, 64625 Bensheim Registergericht: Amtsgericht Darmstadt, HRB 25473 Geschäftsführer: Peter Steinhäuser, Christian Scheele http://www.dd-wrt.com email: [email protected] Tel.: +496251-582650 / Fax: +496251-5826565
Quoted 1 line · Sebastian Gottschall
your patch is not clean
Please stop top-posting.
Quoted 16 lines
patching file
net/netfilter/nf_nat_core.c
Hunk #7 succeeded at 550 (offset 6 lines).
Hunk #8 FAILED at 672.
Hunk #9 succeeded at 819 (offset 10 lines).
Hunk #10 succeeded at 852 (offset 10 lines).
Hunk #11 succeeded at 872 (offset 10 lines).
nf_nat_cleanup_conntrackis wrongyour patch
(quoted diff) +0
-0@@ -672,9 +645,11 @@ 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)
Quoted 8 lines
-ᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵ rhltable_remove(&nf_nat_bysource_table,
&ct->nat_bysource, -ᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵᅵnf_nat_bysource_params); +ᅵᅵᅵᅵᅵᅵ 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);
+ᅵᅵᅵᅵᅵᅵ }
ᅵ}
It assumes
git cherry-pick 6e699867f84c0f358fed233fe6162173aca28e04
to get the IPS_SRC_NAT_DONE test.
Greg KH
maintainerQuoted 33 lines · Florian Westphal
Quoted 1 line · Sebastian Gottschall
your patch is not clean
Please stop top-posting.
Quoted 16 lines
patching file
net/netfilter/nf_nat_core.c
Hunk #7 succeeded at 550 (offset 6 lines).
Hunk #8 FAILED at 672.
Hunk #9 succeeded at 819 (offset 10 lines).
Hunk #10 succeeded at 852 (offset 10 lines).
Hunk #11 succeeded at 872 (offset 10 lines).
nf_nat_cleanup_conntrackis wrongyour patch
(quoted diff) +0
-0@@ -672,9 +645,11 @@ 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)Quoted 8 lines
-�������������� rhltable_remove(&nf_nat_bysource_table,
&ct->nat_bysource, -������������������������������nf_nat_bysource_params); +������ 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);
+������ }
�}It assumes
git cherry-pick6e699867f84c0f358fed233fe6162173aca28e04
Quoted 1 line
to get the
IPS_SRC_NAT_DONEtest.
Can you all submit a "clean" patch series against the next 4.9-stable release I do in an hour?
thanks,
greg k-h