Make hashsize ip_conntrack parameter writable
Subsystems (2)
PATCH 1/1 Make hashsize ip_conntrack parameter writable
Status: Tested on 2.6.14-rc3-git3
It's fairly simple to resize the hash table, but currently you need to remove and reinsert the module. That's bad (we lose connection state). Harald has even offered to write a daemon which sets this based on load.
net/ipv4/netfilter/ip_conntrack_core.c +87 -36
@@ -148,16 +148,19 @@ DEFINE_PER_CPU(struct ip_conntrack_stat,static int ip_conntrack_hash_rnd_initted;static unsigned int ip_conntrack_hash_rnd; -static u_int32_t -hash_conntrack (const struct ip_conntrack_tuple *tuple) +static u32 __hash_conntrack (const struct ip_conntrack_tuple *tuple, +unsigned int size) { -#if 0 -dump_tuple (tuple); -#endif return (jhash_3words (tuple->src.ip, (tuple->dst.ip ^ tuple->dst.protonum), (tuple->src.u.all | (tuple->dst.u.all <<16 )), - ip_conntrack_hash_rnd) % ip_conntrack_htable_size); + ip_conntrack_hash_rnd) % size); +} + +static u_int32_t +hash_conntrack (const struct ip_conntrack_tuple *tuple) +{ +return __hash_conntrack (tuple, ip_conntrack_htable_size); }int
@@ -1338,14 +1341,13 @@ static int kill_all(struct ip_conntrackreturn 1 ; } -static void free_conntrack_hash (void ) +static void free_conntrack_hash (struct list_head *hash,int vmalloced,int size) { -if (ip_conntrack_vmalloc) -vfree (ip_conntrack_hash); +if (vmalloced) +vfree (hash);else -free_pages ((unsigned long )ip_conntrack_hash, -get_order (sizeof (struct list_head ) - * ip_conntrack_htable_size)); +free_pages ((unsigned long )hash, +get_order (sizeof (struct list_head ) * size)); }void ip_conntrack_flush ()
@@ -1375,12 +1377,77 @@ void ip_conntrack_cleanup(void)ip_conntrack_flush ();kmem_cache_destroy (ip_conntrack_cachep);kmem_cache_destroy (ip_conntrack_expect_cachep); -free_conntrack_hash (); +free_conntrack_hash (ip_conntrack_hash, ip_conntrack_vmalloc, + ip_conntrack_htable_size);nf_unregister_sockopt (&so_getorigdst); } -static int hashsize; -module_param (hashsize, int,0400 ); +static struct list_head *alloc_hashtable (int size,int *vmalloced) +{ +struct list_head *hash; +unsigned int i; + + *vmalloced =0 ; + hash = (void *)__get_free_pages (GFP_KERNEL , +get_order (sizeof (struct list_head ) + * size)); +if (!hash) { + *vmalloced =1 ; +printk (KERN_WARNING "ip_conntrack: falling back to vmalloc.\n" ); + hash =vmalloc (sizeof (struct list_head ) * size); + } + +if (hash) +for (i =0 ; i < size; i++) +INIT_LIST_HEAD (&hash[i]); + +return hash; +} + +int set_hashsize (const char *val,struct kernel_param *kp) +{ +int i, bucket, hashsize, vmalloced; +int old_vmalloced, old_size; +struct list_head *hash, *old_hash; +struct ip_conntrack_tuple_hash *h; + +/* On boot, we can set this without any fancy locking. */ +if (!ip_conntrack_htable_size) +return param_set_int (val, kp); + + hashsize =simple_strtol (val,NULL ,0 ); +if (!hashsize) +return -EINVAL ; + + hash =alloc_hashtable (hashsize, &vmalloced); +if (!hash) +return -ENOMEM ; + +write_lock_bh (&ip_conntrack_lock); +for (i =0 ; i < ip_conntrack_htable_size; i++) { +while (!list_empty (&ip_conntrack_hash[i])) { + h =list_entry (ip_conntrack_hash[i].next, + struct ip_conntrack_tuple_hash, list); +list_del (&h->list); + bucket =__hash_conntrack (&h->tuple, hashsize); +list_add_tail (&h->list, &hash[bucket]); + } + } + old_size = ip_conntrack_htable_size; + old_vmalloced = ip_conntrack_vmalloc; + old_hash = ip_conntrack_hash; + + ip_conntrack_htable_size = hashsize; + ip_conntrack_vmalloc = vmalloced; + ip_conntrack_hash = hash; +write_unlock_bh (&ip_conntrack_lock); + +free_conntrack_hash (old_hash, old_vmalloced, old_size); +return 0 ; +} + +module_param_call (hashsize, set_hashsize, param_get_uint, + &ip_conntrack_htable_size,0600 );int __init ip_conntrack_init (void ) {
@@ -1389,9 +1456,7 @@ int __init ip_conntrack_init(void)/* Idea from tcp.c: use 1/16384 of memory. On i386: 32MB * machine has 256 buckets. >= 1GB machines have 8192 buckets. */ -if (hashsize) { - ip_conntrack_htable_size = hashsize; - }else { +if (!ip_conntrack_htable_size) { ip_conntrack_htable_size = (((num_physpages <<PAGE_SHIFT ) /16384 ) /sizeof (struct list_head ));
@@ -1413,20 +1478,8 @@ int __init ip_conntrack_init(void)return ret; } -/* AK: the hash table is twice as big than needed because it -uses list_head. it would be much nicer to caches to use a -single pointer list head here. */ - ip_conntrack_vmalloc =0 ; - ip_conntrack_hash - =(void *)__get_free_pages (GFP_KERNEL , -get_order (sizeof (struct list_head ) - *ip_conntrack_htable_size)); -if (!ip_conntrack_hash) { - ip_conntrack_vmalloc =1 ; -printk (KERN_WARNING "ip_conntrack: falling back to vmalloc.\n" ); - ip_conntrack_hash =vmalloc (sizeof (struct list_head ) - * ip_conntrack_htable_size); - } + ip_conntrack_hash =alloc_hashtable (ip_conntrack_htable_size, + &ip_conntrack_vmalloc);if (!ip_conntrack_hash) {printk (KERN_ERR "Unable to create ip_conntrack_hash\n" ); goto err_unreg_sockopt;
@@ -1458,9 +1511,6 @@ int __init ip_conntrack_init(void) ip_ct_protos[IPPROTO_ICMP ] = &ip_conntrack_protocol_icmp;write_unlock_bh (&ip_conntrack_lock); -for (i =0 ; i < ip_conntrack_htable_size; i++) -INIT_LIST_HEAD (&ip_conntrack_hash[i]); -/* For use by ipt_REJECT */ ip_ct_attach = ip_conntrack_attach;
@@ -1475,7 +1525,8 @@ int __init ip_conntrack_init(void) err_free_conntrack_slab:kmem_cache_destroy (ip_conntrack_cachep); err_free_hash: -free_conntrack_hash (); +free_conntrack_hash (ip_conntrack_hash, ip_conntrack_vmalloc, + ip_conntrack_htable_size); err_unreg_sockopt:nf_unregister_sockopt (&so_getorigdst);
Signature · 1 line
A bad analogy is like a leaky screwdriver -- Richard Braakman
On Thu, Oct 06, 2005 at 04:23:03AM +1000, Rusty Russell wrote:
Hi Rusty and all,
Quoted 7 lines
Status: Tested on 2.6.14-rc3-git3
Signed-off-by Rusty Russell <[email protected]> (authored)It's fairly simple to resize the hash table, but currently you need to remove and reinsert the module. That's bad (we lose connection state). Harald has even offered to write a daemon which sets this based on load.
Hope you're having fun at the workshop. Seems like. :-)
Almost two years ago (3 Nov 2005), during the initial redaction of
http://www.wallfire.org/misc/netfilter_conntrack_perf.txt
I asked :
Is it possible to modify HASHSIZE at runtime when ip_conntrack is not compiled as a module? If not, shouldn't we enable this with /proc, like CONNTRACK_MAX?
And Harald replied:
no. It is non-trivial to change the hash size after we have conntrack entries in the table. It would mean we'd need to re-hash all alrady existing connections.
No one else dared to comment at that time...
Well, it's good to see times have changed. ;-)
Anyway, the resize process implies some rehashing... I guess the resizing of a hash on-place (without allocating/populating another one) is really tricky, if not practically impossible.
So if x if the dimension of the new hash table and y is the size of the memory occupied by all the current connections, you should always dispose of x * sizeof(ptr) + y of extra free memory before the resize. That is good to know, I suppose.
As all netfilter operations are probably freezed during the resize, this leads to the next question: how much time will the resize take?
+ for (i = 0; i < ip_conntrack_htable_size; i++) {
+ while (!list_empty(&ip_conntrack_hash[i])) {
+ h = list_entry(ip_conntrack_hash[i].next, struct ip_conntrack_tuple_hash, list); + list_del(&h->list); + bucket = __hash_conntrack(&h->tuple, hashsize); + list_add_tail(&h->list, &hash[bucket]);
+ }
+ }
How many cycles will an iteration take? (so we can get an estimation of the latency period in function of the processor speed and of the current number of connections)
If this can be really long (seconds?... I have no idea), what would you think about doing the list_del() calls outside (after) of the locking section?
One last (silly) question. As you can specify the size of the hash table with
# modprobe ip_conntrack hashsize=1024 at runtime, I suppose you can also set it at boot time by adding ip_conntrack.hashsize=1024 as a kernel boot parameter (static til now). Am I right? Is the list of all tunable parameters (at least for netfilter) available somewhere?
Herve
Signature · 4 lines
_ (°= Hervé Eychenne //) Homepage: http://www.eychenne.org/ v_/_ WallFire project: http://www.wallfire.org/
Thanks,
Quoted 2 lines · Rusty Russell
Status: Tested on 2.6.14-rc3-git3
Signed-off-by Rusty Russell <[email protected]> (authored)
JFYI, here's an incremental (yet untested) patch that adds support to reinitialize the random seed when reisizing
[NETFILTER] Re-seed the random value when reallocating conntrack hash
---
commit 19426ea52220bc2ebb5500aab4bb2124d1c0b5be
tree 8502b4a7038db9f8158c5ad9c895ff7203778146
parent 46fa7468794cfeeb083ecbc4ad189e887bd55900
author Harald Welte <[email protected]> Fri, 07 Oct 2005 05:40:14 +0200 committer Harald Welte <[email protected]> Fri, 07 Oct 2005 05:40:14 +0200
net/ipv4/netfilter/ip_conntrack_core.c | 19 +++++++++++++------ 1 files changed, 13 insertions(+), 6 deletions(-)
net/ipv4/netfilter/ip_conntrack_core.c +13 -6
@@ -50,7 +50,7 @@#include <linux/netfilter_ipv4/ip_conntrack_core.h> #include <linux/netfilter_ipv4/listhelp.h> -#define IP_CONNTRACK_VERSION "2.3" +#define IP_CONNTRACK_VERSION "2.4"#if 0 #define DEBUGP printk
@@ -148,19 +148,20 @@ DEFINE_PER_CPU(struct ip_conntrack_stat,static int ip_conntrack_hash_rnd_initted;static unsigned int ip_conntrack_hash_rnd; -static u32 __hash_conntrack (const struct ip_conntrack_tuple *tuple, -unsigned int size) +static u_int32_t __hash_conntrack (const struct ip_conntrack_tuple *tuple, +unsigned int size,unsigned int rnd) {return (jhash_3words (tuple->src.ip, (tuple->dst.ip ^ tuple->dst.protonum), (tuple->src.u.all | (tuple->dst.u.all <<16 )), - ip_conntrack_hash_rnd) % size); + rnd) % size); }static u_int32_t hash_conntrack (const struct ip_conntrack_tuple *tuple) { -return __hash_conntrack (tuple, ip_conntrack_htable_size); +return __hash_conntrack (tuple, ip_conntrack_htable_size, + ip_conntrack_hash_rnd); }int
@@ -1408,6 +1409,7 @@ int set_hashsize(const char *val, struct {int i, bucket, hashsize, vmalloced;int old_vmalloced, old_size; +int rnd;struct list_head *hash, *old_hash;struct ip_conntrack_tuple_hash *h;
@@ -1423,13 +1425,17 @@ int set_hashsize(const char *val, structif (!hash)return -ENOMEM ; +/* We have to rehash for the new table anyway, so we also can +* use a new random seed */ +get_random_bytes (&rnd,4 ); +write_lock_bh (&ip_conntrack_lock);for (i =0 ; i < ip_conntrack_htable_size; i++) {while (!list_empty (&ip_conntrack_hash[i])) { h =list_entry (ip_conntrack_hash[i].next, struct ip_conntrack_tuple_hash, list);list_del (&h->list); - bucket =__hash_conntrack (&h->tuple, hashsize); + bucket =__hash_conntrack (&h->tuple, hashsize, rnd);list_add_tail (&h->list, &hash[bucket]); } }
@@ -1440,6 +1446,7 @@ int set_hashsize(const char *val, struct ip_conntrack_htable_size = hashsize; ip_conntrack_vmalloc = vmalloced; ip_conntrack_hash = hash; + ip_conntrack_hash_rnd = rnd;write_unlock_bh (&ip_conntrack_lock);free_conntrack_hash (old_hash, old_vmalloced, old_size);
Signature · 5 lines
- Harald Welte <[email protected]> http://netfilter.org/ ============================================================================ "Fragmentation is like classful addressing -- an interesting early architectural error that shows how much experimentation was going on while IP was being designed." -- Paul Vixie
Quoted 2 lines · Harald Welte
JFYI, here's an incremental (yet untested) patch that adds support to reinitialize the random seed when reisizing
Just for my own education, why is the seed random? Doe this mean that we randonly get a "bad" seed?
It just reminds me of the story at:
http://www.karrels.org/Ed/ACM/ec97/prob_5.html
and random things in the kernel smells like hard to reproduce errors. Of course, possibly we don't actually mean "random" here, hence my desire for er... enlightenment.
Sam
Quoted 5 lines · Amin Azez
Quoted 2 lines · Harald Welte
JFYI, here's an incremental (yet untested) patch that adds support to reinitialize the random seed when reisizing
Just for my own education, why is the seed random?
to prevent any DoS attack on our hash function, by some attacker knowing how to make lots of connections hash to the same bucket.
Quoted 1 line
Doe this mean that we randonly get a "bad" seed?
no, just when we receive the first packet, there can be relatively little entropy in the random number generator. So cryptographically speaking, it makes sense to use a new seed when the system is already running for some time.
Quoted 1 line
and random things in the kernel smells like hard to reproduce errors.
it's fairly common practise to use some random value in a hash function to not expose the hash table to an attack on it. It's what all over the networking code is used for many hash tables.
I don't see how this ever could produce an error. The hash function is still deterministic, since the random value is static as long as the hash table exists.
Signature · 5 lines
- Harald Welte <[email protected]> http://netfilter.org/ ============================================================================ "Fragmentation is like classful addressing -- an interesting early architectural error that shows how much experimentation was going on while IP was being designed." -- Paul Vixie
Quoted 11 lines · Harald Welte
it's fairly common practise to use some random value in a hash function to not expose the hash table to an attack on it. It's what all over the networking code is used for many hash tables.
I don't see how this ever could produce an error. The hash function is still deterministic, since the random value is static as long as the hash table exists.
Yes you are right, this makes sense.
I recall some recent(ish) improvements to the perl hash code to avoid memory explosions on deviously crafted input, perhaps the solution was a random seed, or perhaps it was better re-hashing which is understandably less deterministic and not so suited for networking code.
Thanks for the enlightenment
Sam
From: Rusty Russell <[email protected]>
Date: Thu, 06 Oct 2005 04:23:03 +1000
net/ipv4/netfilter/ip_conntrack_core.c DEFINE_PER_CPU(struct ip_conntrack_stat, · line 164
Quoted 5 lines
net/ipv4/netfilter/ip_conntrack_core.c +4
-0+static u_int32_t +hash_conntrack (const struct ip_conntrack_tuple *tuple) +{ +return __hash_conntrack (tuple, ip_conntrack_htable_size); }
Why don't we use inline ?
-----------------------------------------------------------------
Yasuyuki Kozakai @ USAGI Project <[email protected]>
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 10 lines · Yasuyuki KOZAKAI
From: Rusty Russell <[email protected]>
Date: Thu, 06 Oct 2005 04:23:03 +1000net/ipv4/netfilter/ip_conntrack_core.c DEFINE_PER_CPU(struct ip_conntrack_stat, · line 164
Quoted 5 lines
net/ipv4/netfilter/ip_conntrack_core.c +4
-0+static u_int32_t +hash_conntrack (const struct ip_conntrack_tuple *tuple) +{ +return __hash_conntrack (tuple, ip_conntrack_htable_size); }Why don't we use inline ?
Just checking you were reading. Well done, Yasuyuki!
We should use "u32", too, not those types I made the mistake of using when I was young and foolish.
Rusty.
Signature · 1 line
A bad analogy is like a leaky screwdriver -- Richard Braakman
Quoted 12 lines · Rusty Russell
Quoted 10 lines · Yasuyuki KOZAKAI
From: Rusty Russell <[email protected]>
Date: Thu, 06 Oct 2005 04:23:03 +1000net/ipv4/netfilter/ip_conntrack_core.c DEFINE_PER_CPU(struct ip_conntrack_stat, · line 164
Quoted 5 lines
net/ipv4/netfilter/ip_conntrack_core.c +4
-0+static u_int32_t +hash_conntrack (const struct ip_conntrack_tuple *tuple) +{ +return __hash_conntrack (tuple, ip_conntrack_htable_size); }Why don't we use inline ?
Quoted 1 line
Just checking you were reading. Well done, Yasuyuki!
I also noticed the missing inline when merging your patch, but I thought maybe gcc will do it automatically.
Quoted 2 lines
We should use "u32", too, not those types I made the mistake of using when I was young and foolish.
I'm still young and foolish, so all my code uses the u_intXX_t... and I ask myself why we shouldn't use the posix types? I'm still puzzled...
Signature · 5 lines
- Harald Welte <[email protected]> http://netfilter.org/ ============================================================================ "Fragmentation is like classful addressing -- an interesting early architectural error that shows how much experimentation was going on while IP was being designed." -- Paul Vixie
Quoted 4 lines · Harald Welte
Quoted 1 line
Just checking you were reading. Well done, Yasuyuki!
I also noticed the missing inline when merging your patch, but I thought maybe gcc will do it automatically.
We usually suppress gcc's inline heuristics on kernel builds. Not a good idea these days IMHO, but...
Quoted 5 lines
Quoted 2 lines
We should use "u32", too, not those types I made the mistake of using when I was young and foolish.
I'm still young and foolish, so all my code uses the
u_intXX_t... and I ask myself why we shouldn't use the posix types? I'm still puzzled...
Mainly because they're ugly: in the kernel u32 etc is the standard, and the netfilter code should probably follow that.
Rusty.
Signature · 1 line
A bad analogy is like a leaky screwdriver -- Richard Braakman