* [PATCH RFC] lib/rhashtable: allow users to set the minimum shifts of shrinking
@ 2014-08-27 8:57 Ying Xue
2014-08-27 10:34 ` Thomas Graf
0 siblings, 1 reply; 3+ messages in thread
From: Ying Xue @ 2014-08-27 8:57 UTC (permalink / raw
To: tgraf; +Cc: davem, eric.dumazet, netdev
Now the resizeable hash table size is allowed to shrink a too smaller
size - HASH_MIN_SIZE(4) although users initially specify a rather big
size when table is created. Especially when the number of objects
saved in the table keeps a small value in comparison with the initial
setting of table size during a quite long time, lots of actions of
expanding and shrinking are involved with objects being inserted or
removed from table. However, as synchronize_rcu() has to be called
during expanding and shrinking, these unnecessary actions would
seriously hit users' performance.
Therefore, we should permit users to set the minimum table size
through configuring the minimum of number of shifts when table is
created according to users specific requirement.
Signed-off-by: Ying Xue <ying.xue@windriver.com>
---
include/linux/rhashtable.h | 2 ++
lib/rhashtable.c | 16 ++++++++++++----
2 files changed, 14 insertions(+), 4 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 36826c0..fb298e9d 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -44,6 +44,7 @@ struct rhashtable;
* @head_offset: Offset of rhash_head in struct to be hashed
* @hash_rnd: Seed to use while hashing
* @max_shift: Maximum number of shifts while expanding
+ * @min_shift: Minimum number of shifts while shrinking
* @hashfn: Function to hash key
* @obj_hashfn: Function to hash object
* @grow_decision: If defined, may return true if table should expand
@@ -57,6 +58,7 @@ struct rhashtable_params {
size_t head_offset;
u32 hash_rnd;
size_t max_shift;
+ size_t min_shift;
rht_hashfn_t hashfn;
rht_obj_hashfn_t obj_hashfn;
bool (*grow_decision)(const struct rhashtable *ht,
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index a2c7881..1466e2d 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -293,12 +293,15 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
{
struct bucket_table *ntbl, *tbl = rht_dereference(ht->tbl, ht);
+ size_t min_shift = ilog2(HASH_MIN_SIZE);
struct rhash_head __rcu **pprev;
unsigned int i;
ASSERT_RHT_MUTEX(ht);
- if (tbl->size <= HASH_MIN_SIZE)
+ if (ht->p.min_shift)
+ min_shift = max(ht->p.min_shift, min_shift);
+ if (ht->shift <= min_shift)
return 0;
ntbl = bucket_table_alloc(tbl->size / 2, flags);
@@ -506,9 +509,14 @@ void *rhashtable_lookup_compare(const struct rhashtable *ht, u32 hash,
}
EXPORT_SYMBOL_GPL(rhashtable_lookup_compare);
-static size_t rounded_hashtable_size(unsigned int nelem)
+static size_t rounded_hashtable_size(struct rhashtable_params *params)
{
- return max(roundup_pow_of_two(nelem * 4 / 3), HASH_MIN_SIZE);
+ size_t size = HASH_MIN_SIZE;
+
+ if (params->min_shift)
+ size = max((1UL << params->min_shift), HASH_MIN_SIZE);
+
+ return max(roundup_pow_of_two(params->nelem_hint * 4 / 3), size);
}
/**
@@ -567,7 +575,7 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
return -EINVAL;
if (params->nelem_hint)
- size = rounded_hashtable_size(params->nelem_hint);
+ size = rounded_hashtable_size(params);
tbl = bucket_table_alloc(size, GFP_KERNEL);
if (tbl == NULL)
--
1.7.9.5
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH RFC] lib/rhashtable: allow users to set the minimum shifts of shrinking
2014-08-27 8:57 [PATCH RFC] lib/rhashtable: allow users to set the minimum shifts of shrinking Ying Xue
@ 2014-08-27 10:34 ` Thomas Graf
2014-08-28 1:04 ` Ying Xue
0 siblings, 1 reply; 3+ messages in thread
From: Thomas Graf @ 2014-08-27 10:34 UTC (permalink / raw
To: Ying Xue; +Cc: davem, eric.dumazet, netdev
On 08/27/14 at 04:57pm, Ying Xue wrote:
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index a2c7881..1466e2d 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -293,12 +293,15 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
> int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
> {
> struct bucket_table *ntbl, *tbl = rht_dereference(ht->tbl, ht);
> + size_t min_shift = ilog2(HASH_MIN_SIZE);
> struct rhash_head __rcu **pprev;
> unsigned int i;
>
> ASSERT_RHT_MUTEX(ht);
>
> - if (tbl->size <= HASH_MIN_SIZE)
> + if (ht->p.min_shift)
> + min_shift = max(ht->p.min_shift, min_shift);
> + if (ht->shift <= min_shift)
> return 0;
I like it. Can you translate HASH_MIN_SIZE to .minshift in
rhashtable_init()? That way we only have to deal with .min_shift in
rhashtable_shrink().
Note that shrinking can also be disabled by not providing a
.shrink_decision function in rhashtable_params if the shrinking is
too expensive for your case.
> -static size_t rounded_hashtable_size(unsigned int nelem)
> +static size_t rounded_hashtable_size(struct rhashtable_params *params)
> {
> - return max(roundup_pow_of_two(nelem * 4 / 3), HASH_MIN_SIZE);
> + size_t size = HASH_MIN_SIZE;
> +
> + if (params->min_shift)
> + size = max((1UL << params->min_shift), HASH_MIN_SIZE);
> +
> + return max(roundup_pow_of_two(params->nelem_hint * 4 / 3), size);
> }
Same here. If you merge the provided .min_shift with HASH_MIN_SIZE
in rhashtable_init() before calculating the size, the above logic
can be simplified a lot.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH RFC] lib/rhashtable: allow users to set the minimum shifts of shrinking
2014-08-27 10:34 ` Thomas Graf
@ 2014-08-28 1:04 ` Ying Xue
0 siblings, 0 replies; 3+ messages in thread
From: Ying Xue @ 2014-08-28 1:04 UTC (permalink / raw
To: Thomas Graf; +Cc: davem, eric.dumazet, netdev
On 08/27/2014 06:34 PM, Thomas Graf wrote:
> On 08/27/14 at 04:57pm, Ying Xue wrote:
>> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
>> index a2c7881..1466e2d 100644
>> --- a/lib/rhashtable.c
>> +++ b/lib/rhashtable.c
>> @@ -293,12 +293,15 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
>> int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
>> {
>> struct bucket_table *ntbl, *tbl = rht_dereference(ht->tbl, ht);
>> + size_t min_shift = ilog2(HASH_MIN_SIZE);
>> struct rhash_head __rcu **pprev;
>> unsigned int i;
>>
>> ASSERT_RHT_MUTEX(ht);
>>
>> - if (tbl->size <= HASH_MIN_SIZE)
>> + if (ht->p.min_shift)
>> + min_shift = max(ht->p.min_shift, min_shift);
>> + if (ht->shift <= min_shift)
>> return 0;
>
> I like it. Can you translate HASH_MIN_SIZE to .minshift in
> rhashtable_init()? That way we only have to deal with .min_shift in
> rhashtable_shrink().
>
Good suggestion! I will change it in next version.
> Note that shrinking can also be disabled by not providing a
> .shrink_decision function in rhashtable_params if the shrinking is
> too expensive for your case.
>
Yes, I know the rule. But in some case we hope that rhashtable doesn't
take such expensive actions like expanding and shrinking when its size
is small; meanwhile, when its size is rather big, shrinking is able to
de done as usual.
In fact, we already published the max_shift to users, allowing them to
limit the biggest size of rhashtable. So, exporting min_shift should be
reasonable, having users have a chance to specify the smallest size of
rhashtable.
>> -static size_t rounded_hashtable_size(unsigned int nelem)
>> +static size_t rounded_hashtable_size(struct rhashtable_params *params)
>> {
>> - return max(roundup_pow_of_two(nelem * 4 / 3), HASH_MIN_SIZE);
>> + size_t size = HASH_MIN_SIZE;
>> +
>> + if (params->min_shift)
>> + size = max((1UL << params->min_shift), HASH_MIN_SIZE);
>> +
>> + return max(roundup_pow_of_two(params->nelem_hint * 4 / 3), size);
>> }
>
> Same here. If you merge the provided .min_shift with HASH_MIN_SIZE
> in rhashtable_init() before calculating the size, the above logic
> can be simplified a lot.
>
Thanks for your suggestion.
Regards,
Ying
>
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2014-08-28 1:04 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-08-27 8:57 [PATCH RFC] lib/rhashtable: allow users to set the minimum shifts of shrinking Ying Xue
2014-08-27 10:34 ` Thomas Graf
2014-08-28 1:04 ` Ying Xue
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.