Skip to contentSkip to conversation

rhashtable updates

PATCH In review Daniel Borkmann 5 participants 18 messages Feb 19, 2015 – Feb 20, 2015

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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.

Fixes 54c5b7d311c8 ("rhashtable: introduce rhashtable_wakeup_worker helper function")
Cc Ying Xue <[email protected]>
---
 lib/rhashtable.c | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)
lib/rhashtable.c +18 -9
index 9cc4c4a..38f7879 100644
@@ -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
#2 lore raw

RE: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete

From: Daniel Borkmann

Quoted 9 lines

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.

Does it actually make sense to shrink below the initial default size?

David

#3 lore raw

Re: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete

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_shift parameter, shrinks cannot go below that.

#4 lore raw

Re: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete

Quoted 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_shift parameter, 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.

maintainer Acked-by on v1 1/3
#5 lore raw

Re: [PATCH net 1/3] rhashtable: don't test for shrink on insert, expansion on delete

In reply to Daniel Borkmann
Quoted 5 lines · Daniel Borkmann

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.

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")
Cc Ying Xue <[email protected]>
#6 lore raw

PATCH 2/3 rhashtable: better high order allocation attempts

In reply to Daniel Borkmann

When 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.

Fixes 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
---
 lib/rhashtable.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
lib/rhashtable.c +3 -3
index 38f7879..b41a5c0 100644
@@ -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
#7 lore raw

RE: [PATCH net 2/3] rhashtable: better high order allocation attempts

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 for kzalloc() 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

#8 lore raw

Re: [PATCH net 2/3] rhashtable: better high order allocation attempts

On 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?

#9 lore raw

Re: [PATCH net 2/3] rhashtable: better high order allocation attempts

In reply to David Laight
Quoted 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 for kzalloc() 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.

#10 lore raw

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 for kzalloc() 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

#11 lore raw

Re: [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.

#12 lore raw

Re: [PATCH net 2/3] rhashtable: better high order allocation attempts

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.

#13 lore raw

Re: [PATCH net 2/3] rhashtable: better high order allocation attempts

In reply to David Laight
Quoted 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.

maintainer Acked-by on v1 2/3
#14 lore raw

Re: [PATCH net 2/3] rhashtable: better high order allocation attempts

In reply to Daniel Borkmann
Quoted 9 lines · Daniel Borkmann

When 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.

Fixes 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
#15 lore raw

PATCH 3/3 rhashtable: allow to unload test module

In reply to Daniel Borkmann

There'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.

Fixes 9d6dbe1bbaf8 ("rhashtable: Make selftest modular")
---
 lib/test_rhashtable.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/test_rhashtable.c +5 -0
index 1dfeba7..9c5fcce 100644
@@ -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
maintainer Acked-by on v1 3/3
#16 lore raw

Re: [PATCH net 3/3] rhashtable: allow to unload test module

Quoted 10 lines · Daniel Borkmann

There'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.

Fixes 9d6dbe1bbaf8 ("rhashtable: Make selftest modular")
maintainer
#17 lore raw
In reply to Daniel Borkmann

From: 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.