netfilter: save the hash of the tuple in the original direction for latter use
Subsystems (2)
PATCH 1/1 netfilter: save the hash of the tuple in the original direction for latter use
Since we don't change the tuple in the original direction, we can save it in ct->tuplehash[IP_CT_DIR_REPLY].hnode.pprev for __nf_conntrack_confirm() use.
__hash_conntrack() is split into two steps: ____hash_conntrack() is used to get the raw hash, and __hash_bucket() is used to get the bucket id.
In SYN-flood case, early_drop() doesn't need to recompute the hash again.
--- net/netfilter/nf_conntrack_core.c | 117 ++++++++++++++++++++++++++------------ 1 file changed, 82 insertions(+), 35 deletions(-)
net/netfilter/nf_conntrack_core.c +82 -35
@@ -65,14 +65,23 @@ EXPORT_SYMBOL_GPL(nf_conntrack_max); DEFINE_PER_CPU(struct nf_conn, nf_conntrack_untracked);EXPORT_PER_CPU_SYMBOL (nf_conntrack_untracked); -static int nf_conntrack_hash_rnd_initted; -static unsigned int nf_conntrack_hash_rnd; - -static u_int32_t __hash_conntrack (const struct nf_conntrack_tuple *tuple, -u16 zone,unsigned int size,unsigned int rnd) +static u32 ____hash_conntrack (const struct nf_conntrack_tuple *tuple,u16 zone) {unsigned int n;u_int32_t h; +static int rnd_initted; +static unsigned int rnd; +static DEFINE_SPINLOCK (rnd_lock); + +if (unlikely (!rnd_initted)) { +spin_lock_bh (&rnd_lock); +if (!rnd_initted) { +get_random_bytes (&rnd,sizeof (rnd)); +wmb (); + rnd_initted =1 ; + } +spin_unlock_bh (&rnd_lock); + }/* The direction must be ignored, so we hash everything up to the * destination ports (which is a multiple of 4) and treat the last
@@ -83,14 +92,29 @@ static u_int32_t __hash_conntrack(const struct nf_conntrack_tuple *tuple, zone ^ rnd ^ (((__force __u16 )tuple->dst.u.all <<16 ) | tuple->dst.protonum)); -return ((u64 )h * size) >>32 ; +return h; +} + +static u32 __hash_bucket (u32 __hash,unsigned int size) +{ +return ((u64 )__hash * size) >>32 ; +} + +static u32 hash_bucket (u32 __hash,const struct net *net) +{ +return __hash_bucket (__hash, net->ct.htable_size); +} + +static u_int32_t __hash_conntrack (const struct nf_conntrack_tuple *tuple, +u16 zone,unsigned int size) +{ +return __hash_bucket (____hash_conntrack (tuple, zone), size); }static inline u_int32_t hash_conntrack (const struct net *net,u16 zone,const struct nf_conntrack_tuple *tuple) { -return __hash_conntrack (tuple, zone, net->ct.htable_size, - nf_conntrack_hash_rnd); +return __hash_conntrack (tuple, zone, net->ct.htable_size); }bool
@@ -292,13 +316,13 @@ static void death_by_timeout(unsigned long ul_conntrack)* OR * - Caller must lock nf_conntrack_lock before calling this function */ -struct nf_conntrack_tuple_hash * -__nf_conntrack_find (struct net *net,u16 zone, -const struct nf_conntrack_tuple *tuple) +static struct nf_conntrack_tuple_hash * +____nf_conntrack_find (struct net *net,u16 zone, +const struct nf_conntrack_tuple *tuple,u32 __hash) {struct nf_conntrack_tuple_hash *h;struct hlist_nulls_node *n; -unsigned int hash =hash_conntrack (net, zone, tuple); +unsigned int hash =hash_bucket (__hash, net);/* Disable BHs the entire time since we normally need to disable them * at least once for the stats anyway.
@@ -327,19 +351,27 @@ begin:return NULL ; } + +struct nf_conntrack_tuple_hash * +__nf_conntrack_find (struct net *net,u16 zone, +const struct nf_conntrack_tuple *tuple) +{ +return ____nf_conntrack_find (net, zone, tuple, +____hash_conntrack (tuple, zone)); +}EXPORT_SYMBOL_GPL (__nf_conntrack_find);/* Find a connection corresponding to a tuple. */ -struct nf_conntrack_tuple_hash * -nf_conntrack_find_get (struct net *net,u16 zone, -const struct nf_conntrack_tuple *tuple) +static struct nf_conntrack_tuple_hash * +__nf_conntrack_find_get (struct net *net,u16 zone, +const struct nf_conntrack_tuple *tuple,u32 __hash) {struct nf_conntrack_tuple_hash *h;struct nf_conn *ct;rcu_read_lock (); begin: - h =__nf_conntrack_find (net, zone, tuple); + h =____nf_conntrack_find (net, zone, tuple, __hash);if (h) { ct =nf_ct_tuplehash_to_ctrack (h); if (unlikely(nf_ct_is_dying(ct) ||
@@ -357,6 +389,14 @@ begin:return h; } + +struct nf_conntrack_tuple_hash * +nf_conntrack_find_get (struct net *net,u16 zone, +const struct nf_conntrack_tuple *tuple) +{ +return __nf_conntrack_find_get (net, zone, tuple, +____hash_conntrack (tuple, zone)); +}EXPORT_SYMBOL_GPL (nf_conntrack_find_get); static void __nf_conntrack_hash_insert(struct nf_conn *ct,
@@ -409,7 +449,8 @@ __nf_conntrack_confirm(struct sk_buff *skb)return NF_ACCEPT ; zone =nf_ct_zone (ct); - hash =hash_conntrack (net, zone, &ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple); +/* reuse the __hash saved before */ + hash =hash_bucket (*(unsigned long *)&ct->tuplehash[IP_CT_DIR_REPLY ].hnnode.pprev, net); repl_hash =hash_conntrack (net, zone, &ct->tuplehash[IP_CT_DIR_REPLY ].tuple);/* We're not in hash table, and we refuse to set up related
@@ -567,25 +608,20 @@ static noinline int early_drop(struct net *net, unsigned int hash)return dropped; } -struct nf_conn *nf_conntrack_alloc (struct net *net,u16 zone, -const struct nf_conntrack_tuple *orig, -const struct nf_conntrack_tuple *repl, -gfp_t gfp) +static struct nf_conn * +__nf_conntrack_alloc (struct net *net,u16 zone, +const struct nf_conntrack_tuple *orig, +const struct nf_conntrack_tuple *repl, +gfp_t gfp,u32 __hash) {struct nf_conn *ct; -if (unlikely (!nf_conntrack_hash_rnd_initted)) { -get_random_bytes (&nf_conntrack_hash_rnd, -sizeof (nf_conntrack_hash_rnd)); - nf_conntrack_hash_rnd_initted =1 ; - } -/* We don't want any race condition at early drop stage */ atomic_inc (&net->ct.count);if (nf_conntrack_max &&unlikely (atomic_read (&net->ct.count) > nf_conntrack_max)) { -unsigned int hash =hash_conntrack (net, zone, orig); +unsigned int hash =hash_bucket (__hash, net);if (!early_drop (net, hash)) {atomic_dec (&net->ct.count);if (net_ratelimit ())
@@ -616,7 +652,8 @@ struct nf_conn *nf_conntrack_alloc(struct net *net, u16 zone, ct->tuplehash[IP_CT_DIR_ORIGINAL ].tuple = *orig; ct->tuplehash[IP_CT_DIR_ORIGINAL ].hnnode.pprev =NULL ; ct->tuplehash[IP_CT_DIR_REPLY ].tuple = *repl; - ct->tuplehash[IP_CT_DIR_REPLY ].hnnode.pprev =NULL ; +/* save __hash for reusing when confirming */ + *(unsigned long *)(&ct->tuplehash[IP_CT_DIR_REPLY ].hnnode.pprev) = __hash;/* Don't set timer yet: wait for confirmation */ setup_timer (&ct->timeout, death_by_timeout, (unsigned long )ct);write_pnet (&ct->ct_net, net);
@@ -643,6 +680,14 @@ out_free:return ERR_PTR (-ENOMEM );#endif } + +struct nf_conn *nf_conntrack_alloc (struct net *net,u16 zone, +const struct nf_conntrack_tuple *orig, +const struct nf_conntrack_tuple *repl, +gfp_t gfp) +{ +return __nf_conntrack_alloc (net, zone, orig, repl, gfp,0 ); +}EXPORT_SYMBOL_GPL (nf_conntrack_alloc);void nf_conntrack_free (struct nf_conn *ct)
@@ -664,7 +709,7 @@ init_conntrack(struct net *net, struct nf_conn *tmpl,struct nf_conntrack_l3proto *l3proto, struct nf_conntrack_l4proto *l4proto, struct sk_buff *skb, - unsigned int dataoff) + unsigned int dataoff, u32 __hash) { struct nf_conn *ct;struct nf_conn_help *help;
@@ -678,7 +723,8 @@ init_conntrack(struct net *net, struct nf_conn *tmpl,return NULL ; } - ct =nf_conntrack_alloc (net, zone, tuple, &repl_tuple,GFP_ATOMIC ); + ct =__nf_conntrack_alloc (net, zone, tuple, &repl_tuple,GFP_ATOMIC , + __hash);if (IS_ERR (ct)) {pr_debug ("Can't allocate conntrack.\n" );return (struct nf_conntrack_tuple_hash *)ct;
@@ -755,6 +801,7 @@ resolve_normal_ct(struct net *net, struct nf_conn *tmpl,struct nf_conntrack_tuple_hash *h;struct nf_conn *ct;u16 zone = tmpl ?nf_ct_zone (tmpl) :NF_CT_DEFAULT_ZONE ; +u32 __hash; if (!nf_ct_get_tuple(skb, skb_network_offset(skb), dataoff, l3num, protonum, &tuple, l3proto,
@@ -764,10 +811,11 @@ resolve_normal_ct(struct net *net, struct nf_conn *tmpl, }/* look for tuple match */ - h =nf_conntrack_find_get (net, zone, &tuple); + __hash =____hash_conntrack (&tuple, zone); + h =__nf_conntrack_find_get (net, zone, &tuple, __hash);if (!h) { h =init_conntrack (net, tmpl, &tuple, l3proto, l4proto, - skb, dataoff); + skb, dataoff, __hash);if (!h)return NULL ;if (IS_ERR (h))
@@ -1307,8 +1355,7 @@ int nf_conntrack_set_hashsize(const char *val, struct kernel_param *kp) ct =nf_ct_tuplehash_to_ctrack (h);hlist_nulls_del_rcu (&h->hnnode); bucket =__hash_conntrack (&h->tuple,nf_ct_zone (ct), - hashsize, - nf_conntrack_hash_rnd); + hashsize);hlist_nulls_add_head_rcu (&h->hnnode, &hash[bucket]); } }
Quoted 34 lines · Changli Gao
Since we don't change the tuple in the original direction, we can save it in ct->tuplehash[IP_CT_DIR_REPLY].hnode.pprev for
__nf_conntrack_confirm()use.
__hash_conntrack()is split into two steps:____hash_conntrack()is used to get the raw hash, and__hash_bucket()is used to get the bucket id.In SYN-flood case,
early_drop()doesn't need to recompute the hash again.Signed-off-by Changli Gao <[email protected]>--- net/netfilter/nf_conntrack_core.c | 117 ++++++++++++++++++++++++++------------ 1 file changed, 82 insertions(+), 35 deletions(-)net/netfilter/nf_conntrack_core.c +5
-5@@ -65,14 +65,23 @@ EXPORT_SYMBOL_GPL(nf_conntrack_max); DEFINE_PER_CPU(struct nf_conn, nf_conntrack_untracked);EXPORT_PER_CPU_SYMBOL (nf_conntrack_untracked); -static int nf_conntrack_hash_rnd_initted; -static unsigned int nf_conntrack_hash_rnd; - -static u_int32_t __hash_conntrack (const struct nf_conntrack_tuple *tuple, -u16 zone,unsigned int size,unsigned int rnd) +static u32 ____hash_conntrack (const struct nf_conntrack_tuple *tuple,u16 zone) {unsigned int n;u_int32_t h; +static int rnd_initted; +static unsigned int rnd; +static DEFINE_SPINLOCK (rnd_lock); +
net/netfilter/nf_conntrack_core.c EXPORT_SYMBOL_GPL(nf_conntrack_max); · line 85
Quoted 10 lines
net/netfilter/nf_conntrack_core.c +9
-0+if (unlikely (!rnd_initted)) { +spin_lock_bh (&rnd_lock); +if (!rnd_initted) { +get_random_bytes (&rnd,sizeof (rnd)); +wmb (); + rnd_initted =1 ; + } +spin_unlock_bh (&rnd_lock); + }
Three variables ?
static atomic_t rnd __read_mostly;
if (unlikely(!atomic_read(&rnd))) {
unsigned int val;
get_random_bytes(&val, sizeof(val));
if (!val)
val = 1;
atomic_cmpxchg(&rnd, 0, val);
}--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 5 lines · Eric Dumazet
Three variables ?
static
atomic_trnd__read_mostly;
Quoted 9 lines
if (unlikely(!atomic_read(&rnd))) {
unsigned int val;get_random_bytes(&val, sizeof(val));
if (!val)
val = 1;
atomic_cmpxchg(&rnd, 0, val);
}
Good idea. However, atomic_t is a volatile variable, and it prevent ILP. I think maybe it hurts the likely case. cmpxchg() is an atomic operations, so is the bellow code better?
static unsigned long rnd __read_mostly;
if (unlikely(!rnd)) {
unsigned long val;
get_random_bytes(&val, sizeof(val));
if (!val)
val = 1;
cmpxchg(&rnd, 0, val);}
Thanks.
Signature · 6 lines
Regards, Changli Gao([email protected]) -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 17 lines · Changli Gao
Quoted 5 lines · Eric Dumazet
Three variables ?
static
atomic_trnd__read_mostly;Quoted 9 lines
if (unlikely(!atomic_read(&rnd))) { unsigned int val; get_random_bytes(&val, sizeof(val)); if (!val) val = 1; atomic_cmpxchg(&rnd, 0, val); }
Quoted 4 lines
Good idea. However,
atomic_tis a volatile variable, and it prevent ILP. I think maybe it hurts the likely case.cmpxchg()is an atomic operations, so is the bellow code better?
I am not sure what you mean by ILP.
On x86, reading twice same memory location is faster than reading it and store in temp variable (on stack) reading from stack
Quoted 9 lines
static unsigned long rnd
__read_mostly;if (unlikely(!rnd)) { unsigned long val; get_random_bytes(&val, sizeof(val)); if (!val) val = 1; cmpxchg(&rnd, 0, val);
Quoted 4 lines
}
Thanks.
I am not sure we must use a long (we really need 4 bytes only), and last time I tried to use cmpxchg(), I was being told it was not available on all arches.
But seeing it used in kernel/pid.c, maybe its not true anymore (that is, __HAVE_ARCH_CMPXCHG is always defined to 1)
Since its a recent change (in kernel/pid.c), I would wait a bit and see if an arch maintainer complains ;)
Quoted 18 lines · Eric Dumazet
Quoted 17 lines · Changli Gao
Quoted 14 lines · Eric Dumazet
Three variables ?
static
atomic_trnd__read_mostly;if (unlikely(!atomic_read(&rnd))) {
unsigned int val;get_random_bytes(&val, sizeof(val));
if (!val)
val = 1;
atomic_cmpxchg(&rnd, 0, val);
}
Quoted 6 lines
Quoted 4 lines
Good idea. However,
atomic_tis a volatile variable, and it prevent ILP. I think maybe it hurts the likely case.cmpxchg()is an atomic operations, so is the bellow code better?I am not sure what you mean by ILP.
I mean http://en.wikipedia.org/wiki/Instruction_level_parallelism
and volatile will suppress compiler optimization.
Quoted 4 lines
On x86, reading twice same memory location is faster than reading it and store in temp variable (on stack) reading from stack
Thanks for this info. But compiler may store it in a register. In fact, we can't control the behavior of compiler in C.
Quoted 12 lines
Quoted 12 lines
static unsigned long rnd
__read_mostly;if (unlikely(!rnd)) {
unsigned long val;
get_random_bytes(&val, sizeof(val));
if (!val)
val = 1;
cmpxchg(&rnd, 0, val);
}
Quoted 4 lines
Quoted 2 lines
Thanks.
I am not sure we must use a long (we really need 4 bytes only),
Yea, 4 bytes is enough.
Quoted 10 lines
and last
time I tried to usecmpxchg(), I was being told it was not available on all arches.But seeing it used in
kernel/pid.c, maybe its not true anymore (that is,__HAVE_ARCH_CMPXCHGis always defined to 1)Since its a recent change (in
kernel/pid.c), I would wait a bit and see if an arch maintainer complains ;)
Thanks. I saw it. These are two cmpxchg() in file:
include/asm-generic/cmpxchg.h
include/asm-generic/system.h
static inline unsigned long __cmpxchg(volatile unsigned long *m,
unsigned long old, unsigned long new)
{
unsigned long retval;
unsigned long flags;
local_irq_save(flags);
retval = *m;
if (retval == old)
*m = new;
local_irq_restore(flags);
return retval;
}#define cmpxchg(ptr, o, n) \
((__typeof__(*(ptr))) __cmpxchg((unsigned long *)(ptr), \
(unsigned long)(o), \
(unsigned long)(n)))This one seems buggy when using it to non unsigned long variables. And in kernel/pid.c, the last_pid variable is int.
Signature · 6 lines
Regards, Changli Gao([email protected]) -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 5 lines · Eric Dumazet
I am not sure we must use a long (we really need 4 bytes only), and last time I tried to use
cmpxchg(), I was being told it was not available on all arches.
Quoted 7 lines
But seeing it used in
kernel/pid.c, maybe its not true anymore (that is,__HAVE_ARCH_CMPXCHGis always defined to 1)Since its a recent change (in
kernel/pid.c), I would wait a bit and see if an arch maintainer complains ;)
I searched the code, and found ext4, btrfs, lockdep, perf and trace all use cmpxchg(). And after this patch serial
(http://linux.derkeiler.com/Mailing-Lists/Kernel/2007-08/msg05032.html)
was merged, maybe cmpxchg() is generic. Is there an SMP processor doesn't support cmpxchg()?
Signature · 2 lines
Regards, Changli Gao([email protected])
Quoted 14 lines · * Changli Gao ([email protected]) wrote:
Quoted 5 lines · Eric Dumazet
I am not sure we must use a long (we really need 4 bytes only), and last time I tried to use
cmpxchg(), I was being told it was not available on all arches.Quoted 7 lines
But seeing it used in
kernel/pid.c, maybe its not true anymore (that is,__HAVE_ARCH_CMPXCHGis always defined to 1)Since its a recent change (in
kernel/pid.c), I would wait a bit and see if an arch maintainer complains ;)
Quoted 5 lines
I searched the code, and found ext4, btrfs, lockdep, perf and trace all use
cmpxchg(). And after this patch serial
(http://linux.derkeiler.com/Mailing-Lists/Kernel/2007-08/msg05032.html)
was merged, maybecmpxchg()is generic. Is there an SMP processor doesn't supportcmpxchg()?
I made sure it was available on all architectures with that patchset, with the intended goal to used it (cmpxchg, cmpxchg_local for 32/64-bit and cmpxchg64, cmpxchg64_local for 64-bit) in arch-agnostic tracer code.
I added a cmpxchg emulated with irqs off for uniprocessor-only architectures that did not have CAS support. sparc32 has moved to a hashed locked scheme for its atomic operations long ago, which makes the full 32 bits available.
So, all in all, I'd be surprised if an architecture would lack cmpxchg() today. It might be possible that a new architecture that just came in would not have taken care of deploying cmpxchg, but that should be easily fixable.
Please see Documentation/atomic_ops.txt for details.
Thanks,
Mathieu
Quoted 4 lines
Signature · 3 lines
-- Regards, Changli Gao([email protected])
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 9 lines · Mathieu Desnoyers
I made sure it was available on all architectures with that patchset, with the intended goal to used it (cmpxchg,
cmpxchg_localfor 32/64-bit and cmpxchg64,cmpxchg64_localfor 64-bit) in arch-agnostic tracer code.I added a cmpxchg emulated with irqs off for uniprocessor-only architectures that did not have CAS support. sparc32 has moved to a hashed locked scheme for its atomic operations long ago, which makes the full 32 bits available.
Quoted 4 lines
So, all in all, I'd be surprised if an architecture would lack
cmpxchg()today. It might be possible that a new architecture that just came in would not have taken care of deploying cmpxchg, but that should be easily fixable.
Thats pretty cool, thanks for clarification !