nft hash set expansion problem

nft hash set expansion problem

[Josh Hunt]

Nft hash sets are unable to expand past the initial # of buckets. This 
is b/c nft hash sets don't define the max_shift parameter and so 
rht_grow_above_75():

         return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
                (ht->p.max_shift && atomic_read(&ht->shift) < 
ht->p.max_shift);

can't return true.

It's not clear to me if this is intentional; requiring users of 
rhashtables define a max_shift in order to support expansion, or a bug 
in the grow decision function?

Here's a possible fix if it's the latter. Let me know and I can submit 
something formal if that's the case.

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index e96fc00..2c51617 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -250,7 +250,7 @@ bool rht_grow_above_75(const struct rhashtable *ht, 
size_t new_size)
  {
         /* Expand table when exceeding 75% load */
         return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
-              (ht->p.max_shift && atomic_read(&ht->shift) < 
ht->p.max_shift);
+              (ht->p.max_shift ? atomic_read(&ht->shift) < 
ht->p.max_shift : 1);
  }
  EXPORT_SYMBOL_GPL(rht_grow_above_75);

Thanks
Josh

Re: nft hash set expansion problem

[Daniel Borkmann]

On 02/08/2015 08:38 PM, Josh Hunt wrote:
> Nft hash sets are unable to expand past the initial # of buckets. This is b/c nft hash sets don't define the max_shift parameter and so rht_grow_above_75():
...
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index e96fc00..2c51617 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -250,7 +250,7 @@ bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
>   {
>          /* Expand table when exceeding 75% load */
>          return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
> -              (ht->p.max_shift && atomic_read(&ht->shift) < ht->p.max_shift);
> +              (ht->p.max_shift ? atomic_read(&ht->shift) < ht->p.max_shift : 1);
>   }
>   EXPORT_SYMBOL_GPL(rht_grow_above_75);

This seems not correct as we want to have an upper limit for
rhashtable expansions. It's better to define a max_shift for
nftables, instead.

Re: nft hash set expansion problem

[Josh Hunt]

On 02/08/2015 04:43 PM, Daniel Borkmann wrote:
> On 02/08/2015 08:38 PM, Josh Hunt wrote:
>> Nft hash sets are unable to expand past the initial # of buckets. This
>> is b/c nft hash sets don't define the max_shift parameter and so
>> rht_grow_above_75():
> ...
>> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
>> index e96fc00..2c51617 100644
>> --- a/lib/rhashtable.c
>> +++ b/lib/rhashtable.c
>> @@ -250,7 +250,7 @@ bool rht_grow_above_75(const struct rhashtable
>> *ht, size_t new_size)
>>   {
>>          /* Expand table when exceeding 75% load */
>>          return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
>> -              (ht->p.max_shift && atomic_read(&ht->shift) <
>> ht->p.max_shift);
>> +              (ht->p.max_shift ? atomic_read(&ht->shift) <
>> ht->p.max_shift : 1);
>>   }
>>   EXPORT_SYMBOL_GPL(rht_grow_above_75);
>
> This seems not correct as we want to have an upper limit for
> rhashtable expansions. It's better to define a max_shift for
> nftables, instead.

Thanks Daniel that's what I wanted to know. I'll fix this on the 
nft_hash side.

Josh

Re: nft hash set expansion problem

[Thomas Graf]

On 02/09/15 at 08:44am, Josh Hunt wrote:
> On 02/08/2015 04:43 PM, Daniel Borkmann wrote:
> >This seems not correct as we want to have an upper limit for
> >rhashtable expansions. It's better to define a max_shift for
> >nftables, instead.
> 
> Thanks Daniel that's what I wanted to know. I'll fix this on the nft_hash
> side.

I agree it does not make sense to allow unlimited growth.
Can you enforce a max_shift > 0 in rhashtable_init() while you
are at it? 

Re: nft hash set expansion problem

[Josh Hunt]

On 02/09/2015 09:21 AM, Thomas Graf wrote:
> On 02/09/15 at 08:44am, Josh Hunt wrote:
>> On 02/08/2015 04:43 PM, Daniel Borkmann wrote:
>>> This seems not correct as we want to have an upper limit for
>>> rhashtable expansions. It's better to define a max_shift for
>>> nftables, instead.
>>
>> Thanks Daniel that's what I wanted to know. I'll fix this on the nft_hash
>> side.
>
> I agree it does not make sense to allow unlimited growth.
> Can you enforce a max_shift > 0 in rhashtable_init() while you
> are at it?
>

Yeah I'll do that as well.