Skip to contentSkip to conversation

rhashtable rehashing fixes

PATCH Superseded Thomas Graf 3 participants 7 messages Apr 21, 2015 – Apr 22, 2015

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Thomas Graf

author maintainer
#0 lore raw

cover rhashtable rehashing fixes

Some rhashtable rehashing bugs found while testing with the next rhashtable self-test queued up for the next devel cycle:

https://github.com/tgraf/net-next/commits/rht

Thomas Graf (2):
rhashtable: Schedule async resize when sync realloc fails
rhashtable: Do not schedule more than one rehash if we can't grow
further

 include/linux/rhashtable.h | 2 ++
 lib/rhashtable.c           | 4 ++--
 2 files changed, 4 insertions(+), 2 deletions(-)
Signature · 1 line
2.3.5
author maintainer
#1 lore raw

PATCH 1/2 rhashtable: Schedule async resize when sync realloc fails

When rhashtable_insert_rehash() fails with ENOMEM, this indicates that we can't allocate the necessary memory in the current context but the limits as set by the user would still allow to grow.

Thus attempt an async resize in the background where we can allocate using GFP_KERNEL which is more likely to succeed. The insertion itself will still fail to indicate pressure.

This fixes a bug where the table would never continue growing once the utilization is above 100%.

Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
---
 include/linux/rhashtable.h | 2 ++
 1 file changed, 2 insertions(+)
include/linux/rhashtable.h +2 -0
index e23d242..7040b5c 100644
@@ -593,6 +593,8 @@ slow_path:
 		spin_unlock_bh(lock);
 		err = rhashtable_insert_rehash(ht);
 		rcu_read_unlock();
+		if (err == -ENOMEM)
+			schedule_work(&ht->run_work);
 		if (err)
 			return err;
 
Signature · 1 line
2.3.5
maintainer
#2 lore raw

Re: [PATCH net 1/2] rhashtable: Schedule async resize when sync realloc fails

Quoted 8 lines · Thomas Graf

When rhashtable_insert_rehash() fails with ENOMEM, this indicates that we can't allocate the necessary memory in the current context but the limits as set by the user would still allow to grow.

Thus attempt an async resize in the background where we can allocate using GFP_KERNEL which is more likely to succeed. The insertion itself will still fail to indicate pressure.

Quoted 5 lines

This fixes a bug where the table would never continue growing once the utilization is above 100%.

Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")

Good catch. But I think this call should happen in rhashtable_insert_rehash since it's on the slow-path.

Thanks,

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
maintainer
#3 lore raw

Re: [PATCH net 1/2] rhashtable: Schedule async resize when sync realloc fails

From: Herbert Xu <[email protected]>
Date: Wed, 22 Apr 2015 08:36:34 +0800

Quoted 9 lines · Thomas Graf
Quoted 8 lines

When rhashtable_insert_rehash() fails with ENOMEM, this indicates that we can't allocate the necessary memory in the current context but the limits as set by the user would still allow to grow.

Thus attempt an async resize in the background where we can allocate using GFP_KERNEL which is more likely to succeed. The insertion itself will still fail to indicate pressure.

Quoted 8 lines
Quoted 5 lines

This fixes a bug where the table would never continue growing once the utilization is above 100%.

Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")

Good catch. But I think this call should happen in rhashtable_insert_rehash since it's on the slow-path.

Ok, then I expect a respin of this series.

author maintainer
#4 lore raw

Re: [PATCH net 1/2] rhashtable: Schedule async resize when sync realloc fails

Quoted 15 lines · David Miller

From: Herbert Xu <[email protected]>
Date: Wed, 22 Apr 2015 08:36:34 +0800

Quoted 12 lines · Thomas Graf
Quoted 11 lines

When rhashtable_insert_rehash() fails with ENOMEM, this indicates that we can't allocate the necessary memory in the current context but the limits as set by the user would still allow to grow.

Thus attempt an async resize in the background where we can allocate using GFP_KERNEL which is more likely to succeed. The insertion itself will still fail to indicate pressure.

This fixes a bug where the table would never continue growing once the utilization is above 100%.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")

Good catch. But I think this call should happen in rhashtable_insert_rehash since it's on the slow-path.

Ok, then I expect a respin of this series.

Agreed, respinning.

author maintainer
#5 lore raw

PATCH 2/2 rhashtable: Do not schedule more than one rehash if we can't grow further

In reply to Thomas Graf

The current code currently only stops inserting rehashes into the chain when no resizes are currently scheduled. As long as resizes are scheduled and while inserting above the utilization watermark, more and more rehashes will be scheduled.

This lead to a perfect DoS storm with thousands of rehashes scheduled which lead to thousands of spinlocks to be taken sequentially.

Instead, only allow either a series of resizes or a single rehash. Drop any further rehashes and return -EBUSY.

Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
---
 lib/rhashtable.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
lib/rhashtable.c +2 -2
index 4898442..cb819ed 100644
@@ -405,8 +405,8 @@ int rhashtable_insert_rehash(struct rhashtable *ht)
 
 	if (rht_grow_above_75(ht, tbl))
 		size *= 2;
-	/* More than two rehashes (not resizes) detected. */
-	else if (WARN_ON(old_tbl != tbl && old_tbl->size == size))
+	/* Do not schedule more than one rehash */
+	else if (old_tbl != tbl)
 		return -EBUSY;
 
 	new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);
Signature · 1 line
2.3.5
maintainer Acked-by on v1 2/2
#6 lore raw

Re: [PATCH net 2/2] rhashtable: Do not schedule more than one rehash if we can't grow further

Quoted 9 lines · Thomas Graf

The current code currently only stops inserting rehashes into the chain when no resizes are currently scheduled. As long as resizes are scheduled and while inserting above the utilization watermark, more and more rehashes will be scheduled.

This lead to a perfect DoS storm with thousands of rehashes scheduled which lead to thousands of spinlocks to be taken sequentially.

Quoted 5 lines

Instead, only allow either a series of resizes or a single rehash. Drop any further rehashes and return -EBUSY.

Fixes ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt