rhashtable updates
Subsystems (4)
cover rhashtable updates
Daniel Borkmann (3):
rhashtable: don't test for shrink on insert, expansion on delete
rhashtable: better high order allocation attempts
rhashtable: allow to unload test module
lib/rhashtable.c | 33 +++++++++++++++++++++------------ lib/test_rhashtable.c | 5 +++++ 2 files changed, 26 insertions(+), 12 deletions(-)
Signature · 1 line
1.9.3
PATCH 1/3 rhashtable: don't test for shrink on insert, expansion on delete
Restore pre 54c5b7d311c8 behaviour and only probe for expansions on inserts and shrinks on deletes. Currently, it will happen that on initial inserts into a sparse hash table, we may i.e. shrink it first simply because it's not fully populated yet, only to later realize that we need to grow again.
This however is counter intuitive, e.g. an initial default size of 64 elements is already small enough, and in case an elements size hint is given to the hash table by a user, we should avoid unnecessary expansion steps, so a shrink is clearly unintended here.
--- lib/rhashtable.c | 27 ++++++++++++++++++--------- 1 file changed, 18 insertions(+), 9 deletions(-)
lib/rhashtable.c +18 -9
@@ -537,16 +537,25 @@ unlock:mutex_unlock (&ht->mutex); } -static void rhashtable_wakeup_worker (struct rhashtable *ht) +static void rhashtable_probe_expand (struct rhashtable *ht) { -struct bucket_table *tbl =rht_dereference_rcu (ht->tbl, ht); -struct bucket_table *new_tbl =rht_dereference_rcu (ht->future_tbl, ht); -size_t size = tbl->size; +const struct bucket_table *new_tbl =rht_dereference_rcu (ht->future_tbl, ht); +const struct bucket_table *tbl =rht_dereference_rcu (ht->tbl, ht);/* Only adjust the table if no resizing is currently in progress. */ -if (tbl == new_tbl && - ((ht->p.grow_decision && ht->p.grow_decision (ht, size)) || - (ht->p.shrink_decision && ht->p.shrink_decision (ht, size)))) +if (tbl == new_tbl && ht->p.grow_decision && + ht->p.grow_decision (ht, tbl->size)) +schedule_work (&ht->run_work); +} + +static void rhashtable_probe_shrink (struct rhashtable *ht) +{ +const struct bucket_table *new_tbl =rht_dereference_rcu (ht->future_tbl, ht); +const struct bucket_table *tbl =rht_dereference_rcu (ht->tbl, ht); + +/* Only adjust the table if no resizing is currently in progress. */ +if (tbl == new_tbl && ht->p.shrink_decision && + ht->p.shrink_decision (ht, tbl->size))schedule_work (&ht->run_work); }
@@ -569,7 +578,7 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,atomic_inc (&ht->nelems); -rhashtable_wakeup_worker (ht); +rhashtable_probe_expand (ht); }/**
@@ -682,7 +691,7 @@ found:if (ret) {atomic_dec (&ht->nelems); -rhashtable_wakeup_worker (ht); +rhashtable_probe_shrink (ht); }rcu_read_unlock ();
Signature · 1 line
1.9.3
PATCH 2/3 rhashtable: better high order allocation attempts
In reply to Daniel BorkmannWhen trying to allocate future tables via bucket_table_alloc(), it seems overkill on large table shifts that we probe for kzalloc() unconditionally first, as it's likely to fail.
Only probe with kzalloc() for more reasonable table sizes and use vzalloc() either as a fallback on failure or directly in case of large table sizes.
--- lib/rhashtable.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
lib/rhashtable.c +3 -3
@@ -217,15 +217,15 @@ static void bucket_table_free(const struct bucket_table *tbl)static struct bucket_table *bucket_table_alloc (struct rhashtable *ht,size_t nbuckets) { -struct bucket_table *tbl; +struct bucket_table *tbl =NULL ;size_t size;int i; size =sizeof (*tbl) + nbuckets *sizeof (tbl->buckets[0 ]); - tbl =kzalloc (size,GFP_KERNEL | __GFP_NOWARN); +if (size <= (PAGE_SIZE <<PAGE_ALLOC_COSTLY_ORDER )) + tbl =kzalloc (size,GFP_KERNEL | __GFP_NOWARN | __GFP_NORETRY);if (tbl ==NULL ) tbl =vzalloc (size); -if (tbl ==NULL )return NULL ;
Signature · 1 line
1.9.3
PATCH 3/3 rhashtable: allow to unload test module
In reply to Daniel BorkmannThere's no good reason why to disallow unloading of the rhashtable test case module.
Commit 9d6dbe1bbaf8 moved the code from a boot test into a stand-alone module, but only converted the subsys_initcall() handler into a module_init() function without a related exit handler, and thus preventing the test module from unloading.
--- lib/test_rhashtable.c | 5 +++++ 1 file changed, 5 insertions(+)
lib/test_rhashtable.c +5 -0
@@ -222,6 +222,11 @@ static int __init test_rht_init(void)return err; } +static void __exit test_rht_exit(void) +{ +} +module_init (test_rht_init); +module_exit (test_rht_exit);MODULE_LICENSE ("GPL v2" );
Signature · 1 line
1.9.3
RE: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete
In reply to Daniel BorkmannFrom: Daniel Borkmann
Quoted 9 lines
Restore pre
54c5b7d311c8behaviour and only probe for expansions on inserts and shrinks on deletes. Currently, it will happen that on initial inserts into a sparse hash table, we may i.e. shrink it first simply because it's not fully populated yet, only to later realize that we need to grow again.This however is counter intuitive, e.g. an initial default size of 64 elements is already small enough, and in case an elements size hint is given to the hash table by a user, we should avoid unnecessary expansion steps, so a shrink is clearly unintended here.
Does it actually make sense to shrink below the initial default size?
David
RE: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to Daniel BorkmannFrom: Daniel Borkmann
Quoted 3 lines
When trying to allocate future tables via
bucket_table_alloc(), it seems overkill on large table shifts that we probe forkzalloc()unconditionally first, as it's likely to fail.
How about a two-level array for large tables?
Then you don't need to allocate more than 1 page at a time?
David
Re: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete
In reply to David LaightOn 02/20/2015 11:08 AM, David Laight wrote:
...
Quoted 1 line
Does it actually make sense to shrink below the initial default size?
rhashtable has a min_shift parameter, shrinks cannot go below that.
Re: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to David LaightOn 02/20/2015 11:11 AM, David Laight wrote:
...
Quoted 2 lines
How about a two-level array for large tables?
Then you don't need to allocate more than 1 page at a time?
Sorry, I currently don't see how this fits into the rhashtable algorithm i.e. with regards to the expansion and shrink logic?
[email protected]
maintainerRe: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete
In reply to Daniel BorkmannQuoted 5 lines · Daniel Borkmann
On 02/20/2015 11:08 AM, David Laight wrote:
...Quoted 1 line
Does it actually make sense to shrink below the initial default size?
rhashtable has a
min_shiftparameter, shrinks cannot go below that.
Right, it's up to the user to set min_shift according to nelems hint or not. I see use cases for both behaviours.
Re: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete
In reply to Daniel BorkmannQuoted 5 lines · Daniel Borkmann
Restore pre
54c5b7d311c8behaviour and only probe for expansions on inserts and shrinks on deletes. Currently, it will happen that on initial inserts into a sparse hash table, we may i.e. shrink it first simply because it's not fully populated yet, only to later realize that we need to grow again.
Quoted 8 lines
This however is counter intuitive, e.g. an initial default size of 64 elements is already small enough, and in case an elements size hint is given to the hash table by a user, we should avoid unnecessary expansion steps, so a shrink is clearly unintended here.
Fixes 54c5b7d311c8 ("rhashtable: introduce rhashtable_wakeup_worker helper function")Signed-off-by Daniel Borkmann <[email protected]>Cc Ying Xue <[email protected]>
Re: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to Daniel BorkmannQuoted 9 lines · Daniel Borkmann
When trying to allocate future tables via
bucket_table_alloc(), it seems overkill on large table shifts that we probe forkzalloc()unconditionally first, as it's likely to fail.Only probe with
kzalloc()for more reasonable table sizes and usevzalloc()either as a fallback on failure or directly in case of large table sizes.Fixes 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")Signed-off-by Daniel Borkmann <[email protected]>
Re: [PATCH net 3/3] rhashtable: allow to unload test module
In reply to Daniel BorkmannQuoted 10 lines · Daniel Borkmann
There's no good reason why to disallow unloading of the rhashtable test case module.
Commit
9d6dbe1bbaf8moved the code from a boot test into a stand-alone module, but only converted thesubsys_initcall()handler into amodule_init()function without a related exit handler, and thus preventing the test module from unloading.Fixes 9d6dbe1bbaf8 ("rhashtable: Make selftest modular")Signed-off-by Daniel Borkmann <[email protected]>
Re: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to David LaightQuoted 7 lines · David Laight
From: Daniel Borkmann
Quoted 3 lines
When trying to allocate future tables via
bucket_table_alloc(), it seems overkill on large table shifts that we probe forkzalloc()unconditionally first, as it's likely to fail.How about a two-level array for large tables?
Then you don't need to allocate more than 1 page at a time?
This is called vmalloc() in linux kernel.
RE: [PATCH net 2/3] rhashtable: better high order allocation attempts
From: Eric Dumazet
Quoted 10 lines · David Laight
Quoted 7 lines
From: Daniel Borkmann
Quoted 3 lines
When trying to allocate future tables via
bucket_table_alloc(), it seems overkill on large table shifts that we probe forkzalloc()unconditionally first, as it's likely to fail.How about a two-level array for large tables?
Then you don't need to allocate more than 1 page at a time?This is called
vmalloc()in linux kernel.
vmalloc() still requires contiguous KVA, just not contiguous physical memory. I also believe that (on some systems at least) the address space for vmalloc() is much smaller than that for kalloc().
IIRC At least one piece of historic documentation says that vmalloc() should only be used for short term allocations.
I presume this code is allocating very large arrays for the base of the hash lists. Since there is no absolute requirement for contiguous KVA (nothing sequentially accesses the entire array) it can be coded differently.
I realize that this would involve an extra data cache line access. So you'd want to avoid it for small tables.
(I expected this to be your objection)
David
[email protected]
maintainerRe: [PATCH net 2/3] rhashtable: better high order allocation attempts
Quoted 7 lines · David Laight
I presume this code is allocating very large arrays for the base of the hash lists. Since there is no absolute requirement for contiguous KVA (nothing sequentially accesses the entire array) it can be coded differently.
I realize that this would involve an extra data cache line access. So you'd want to avoid it for small tables.
(I expected this to be your objection)
We can consider switching over to flex arrays at some point although NUMA considerations seem much more important to me at this point.
Re: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to David LaightQuoted 3 lines · David Laight
I presume this code is allocating very large arrays for the base of the hash lists. Since there is no absolute requirement for contiguous KVA (nothing sequentially accesses the entire array) it can be coded differently.
vmalloc() is the proper allocator for hash table, even very big ones.
So far, no user wants huge rhashtable that would not fit in vmalloc reserved space.
$ grep Vmalloc /proc/meminfo VmallocTotal: 34359738367 kB VmallocUsed: 377492 kB VmallocChunk: 34359350872 kB
It seems we have some room.
Re: [PATCH net 2/3] rhashtable: better high order allocation attempts
In reply to [email protected]Quoted 3 lines · On Fri, 2015-02-20 at 14:31 +0000, [email protected] wrote:
We can consider switching over to flex arrays at some point although NUMA considerations seem much more important to me at this point.
flex arrays add a performance cost, much higher than TLB misses of vmalloc()
I mentioned in the past that vmalloc() could be using hugepages eventually, so even this TLB cost could be lowered if wanted.
David Miller
maintainerFrom: Daniel Borkmann <[email protected]>
Date: Fri, 20 Feb 2015 00:53:36 +0100
Quoted 4 lines
Daniel Borkmann (3):
rhashtable: don't test for shrink on insert, expansion on delete
rhashtable: better high order allocation attempts
rhashtable: allow to unload test module
Series applied, thanks Daniel.