[PATCH net-next] rhashtable: Warn if min_size or max_size are not a power of two

[PATCH net-next] rhashtable: Warn if min_size or max_size are not a power of two

[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 <tgraf@suug.ch>
---
 lib/rhashtable.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 5f8fe3e..ad218d6 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -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)
-- 
1.9.3

Re: [PATCH net-next] rhashtable: Warn if min_size or max_size are not a power of two

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Thu, 19 Mar 2015 17:34:39 +0100

> 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 <tgraf@suug.ch>
 ...
> +		roundup_pow_of_two(params->min_size) != params->min_size);

Please use "!is_power_of_two()", thanks.

[PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[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 <tgraf@suug.ch>
---
v2: use is_power_of_2() instead of roundup_pow_of_two()

 lib/rhashtable.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 5f8fe3e..5474507 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -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)
-- 
1.9.3

Re: [PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[Herbert Xu]

On Thu, Mar 19, 2015 at 07:46:08PM +0000, Thomas Graf wrote:
> 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 <tgraf@suug.ch>

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,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[Thomas Graf]

On 03/20/15 at 08:02am, Herbert Xu wrote:
> On Thu, Mar 19, 2015 at 07:46:08PM +0000, Thomas Graf wrote:
> > 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 <tgraf@suug.ch>
> 
> 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.

Re: [PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[Herbert Xu]

On Thu, Mar 19, 2015 at 09:15:46PM +0000, Thomas Graf wrote:
>
> 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,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[Herbert Xu]

On Fri, Mar 20, 2015 at 08:49:33AM +1100, Herbert Xu wrote:
>
> 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/
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

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

[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 <tgraf@suug.ch>
---
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(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 5f8fe3e..e75c48d 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -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
-- 
1.9.3

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

[Herbert Xu]

On Thu, Mar 19, 2015 at 10:31:13PM +0000, Thomas Graf wrote:
> 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 <tgraf@suug.ch>

Acked-by: Herbert Xu <herbert@gondor.apana.org.au>

> ---
> 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.
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

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

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Thu, 19 Mar 2015 22:31:13 +0000

> 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 <tgraf@suug.ch>
> ---
> 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.

RE: [PATCH net-next v2] rhashtable: Warn if min_size or max_size are not a power of two

[David Laight]

From: Herbert Xu
> Sent: 19 March 2015 21:50
> On Thu, Mar 19, 2015 at 09:15:46PM +0000, Thomas Graf wrote:
> >
> > 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.

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