Skip to contentSkip to conversation

rhashtable: Warn if min_size or max_size are not a power of two

PATCH Superseded Thomas Graf 4 participants 11 messages Mar 19, 2015 – Mar 20, 2015

Subsystems (4)
Networking Network drivers Library code Rhashtable
lore
Share & tools
lore

Thomas Graf

author maintainer
#0 lore raw

PATCH 1/1 rhashtable: Warn if min_size or max_size are not a power of two

The current code correctly limits table size to the next power of two. This check is solely to catch programming errors.

Signed-off-by Thomas Graf <[email protected]>
---
 lib/rhashtable.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/rhashtable.c +5 -0
index 5f8fe3e..ad218d6 100644
@@ -933,6 +933,11 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
 		return -EINVAL;
 
+	WARN_ON(params->min_size &&
+		roundup_pow_of_two(params->min_size) != params->min_size);
+	WARN_ON(params->max_size &&
+		roundup_pow_of_two(params->max_size) != params->max_size);
+
 	params->min_size = max(params->min_size, HASH_MIN_SIZE);
 
 	if (params->nelem_hint)
Signature · 1 line
1.9.3
maintainer
#1 lore raw

From: Thomas Graf <[email protected]>
Date: Thu, 19 Mar 2015 17:34:39 +0100

Quoted 4 lines

The current code correctly limits table size to the next power of two. This check is solely to catch programming errors.

Signed-off-by Thomas Graf <[email protected]>

...

lib/rhashtable.c int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params) · line 937

Quoted 1 line
lib/rhashtable.c +1 -0
+		roundup_pow_of_two(params->min_size) != params->min_size);

Please use "!is_power_of_two()", thanks.

author maintainer
#2 lore raw

PATCH v2 1/1 rhashtable: Warn if min_size or max_size are not a power of two

The current code correctly limits table size to the next power of two. This check is solely to catch programming errors.

Signed-off-by Thomas Graf <[email protected]>

---
v2: use is_power_of_2() instead of roundup_pow_of_two()

 lib/rhashtable.c | 3 +++
 1 file changed, 3 insertions(+)
lib/rhashtable.c +3 -0
index 5f8fe3e..5474507 100644
@@ -933,6 +933,9 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
 		return -EINVAL;
 
+	WARN_ON(params->min_size && !is_power_of_2(params->min_size));
+	WARN_ON(params->max_size && !is_power_of_2(params->max_size));
+
 	params->min_size = max(params->min_size, HASH_MIN_SIZE);
 
 	if (params->nelem_hint)
Signature · 1 line
1.9.3
maintainer
#3 lore raw
Quoted 4 lines · Thomas Graf

The current code correctly limits table size to the next power of two. This check is solely to catch programming errors.

Signed-off-by Thomas Graf <[email protected]>

I don't see the point of this. A maximum size of 3 says that the table size should never exceed 3 which makes perfect sense. And our current code will respect that.

So why force it to be a power of 2 just because our table sizes happen to be powers of 2?

Cheers,

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
author maintainer
#4 lore raw
Quoted 4 lines · Herbert Xu
Quoted 3 lines · Thomas Graf

The current code correctly limits table size to the next power of two. This check is solely to catch programming errors.

Quoted 8 lines
Quoted 1 line
Signed-off-by Thomas Graf <[email protected]>

I don't see the point of this. A maximum size of 3 says that the table size should never exceed 3 which makes perfect sense. And our current code will respect that.

So why force it to be a power of 2 just because our table sizes happen to be powers of 2?

rht_grow_above_75() checks the old table size:

(!ht->p.max_size || tbl->size < ht->p.max_size);

If you specify max_size = 3, it grows the table to tbl->size = 4. This can be avoided if max_size is a power of two.

maintainer
#5 lore raw
Quoted 7 lines · Thomas Graf

rht_grow_above_75() checks the old table size:

(!ht->p.max_size || tbl->size < ht->p.max_size);

If you specify max_size = 3, it grows the table to tbl->size = 4. This can be avoided if max_size is a power of two.

OK let's fix the test then. The easiest way would be to round max_size up to the next power of 2.

Cheers,

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
#6 lore raw
Quoted 3 lines · Herbert Xu

OK let's fix the test then. The easiest way would be to round max_size up to the next power of 2.

s/up/down/

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
author maintainer
#7 lore raw

PATCH 1/1 rhashtable: Round up/down min/max_size to ensure we respect limit

Round up min_size respectively round down max_size to the next power of two to make sure we always respect the limit specified by the user. This is required because we compare the table size against the limit before we expand or shrink.

Also fixes a minor bug where we modified min_size in the params provided instead of the copy stored in struct rhashtable.

Signed-off-by Thomas Graf <[email protected]>

---
Herbert: I'm fine with either approach. I figured you expected the user to take care of this, hence the added warning. This is perfectly fine with me me as well.

 lib/rhashtable.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)
lib/rhashtable.c +8 -2
index 5f8fe3e..e75c48d 100644
@@ -933,8 +933,6 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (params->nulls_base && params->nulls_base < (1U << RHT_BASE_SHIFT))
 		return -EINVAL;
 
-	params->min_size = max(params->min_size, HASH_MIN_SIZE);
-
 	if (params->nelem_hint)
 		size = rounded_hashtable_size(params);
 

@@ -942,6 +940,14 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	mutex_init(&ht->mutex);
 	memcpy(&ht->p, params, sizeof(*params));
 
+	if (params->min_size)
+		ht->p.min_size = roundup_pow_of_two(params->min_size);
+
+	if (params->max_size)
+		ht->p.max_size = rounddown_pow_of_two(params->max_size);
+
+	ht->p.min_size = max(params->min_size, HASH_MIN_SIZE);
+
 	if (params->locks_mul)
 		ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);
 	else
Signature · 1 line
1.9.3
maintainer Acked-by on v1 1/1
#8 lore raw

Re: [PATCH net-next] rhashtable: Round up/down min/max_size to ensure we respect limit

Quoted 9 lines · Thomas Graf

Round up min_size respectively round down max_size to the next power of two to make sure we always respect the limit specified by the user. This is required because we compare the table size against the limit before we expand or shrink.

Also fixes a minor bug where we modified min_size in the params provided instead of the copy stored in struct rhashtable.

Signed-off-by Thomas Graf <[email protected]>
Acked-by Herbert Xu <[email protected]>
Quoted 4 lines

---
Herbert: I'm fine with either approach. I figured you expected the user to take care of this, hence the added warning. This is perfectly fine with me me as well.

Thanks for fixing this.

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 Applied
#9 lore raw

Re: [PATCH net-next] rhashtable: Round up/down min/max_size to ensure we respect limit

In reply to Thomas Graf

From: Thomas Graf <[email protected]>
Date: Thu, 19 Mar 2015 22:31:13 +0000

Quoted 5 lines

Round up min_size respectively round down max_size to the next power of two to make sure we always respect the limit specified by the user. This is required because we compare the table size against the limit before we expand or shrink.

Quoted 8 lines

Also fixes a minor bug where we modified min_size in the params provided instead of the copy stored in struct rhashtable.

Signed-off-by Thomas Graf <[email protected]>

---
Herbert: I'm fine with either approach. I figured you expected the user to take care of this, hence the added warning. This is perfectly fine with me me as well.

Applied, thanks a lot.

#10 lore raw
In reply to Herbert Xu

From: Herbert Xu

Quoted 5 lines

Sent: 19 March 2015 21:50

Quoted 3 lines · Thomas Graf

rht_grow_above_75() checks the old table size:

Quoted 7 lines
Quoted 4 lines

(!ht->p.max_size || tbl->size < ht->p.max_size);

If you specify max_size = 3, it grows the table to tbl->size = 4. This can be avoided if max_size is a power of two.

OK let's fix the test then. The easiest way would be to round max_size up to the next power of 2.

Isn't that round-up implicit in the test above, no reason to change the user-supplied limit.

To round down just test tbl->size * 2 <= ht->p.max_size.

Maybe just document the fact that it will grow if the current size is less than the requested maximum.

David