[ltt-dev] [PATCH 4/5] rculfhash: fix check_resize()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> When I force the accounting unavailable but with CDS_LFHT_AUTO_RESIZE,
> the hash table will grow very very large, which is bad.

You should double-check if this is caused by having a badly distributed
hash function, which would cause large clusters of nodes to be populated
into a sub-part of the hash table (within a single chain).

The fallback when no accounting is available is using the chain length
to figure out if the table should be expanded. And yes, this is
sensitive to oddly distributed hash functions.

> I think the logic in check_resize() is not good, size is more proper
> for indicating a hash table small or not.

Hrm. The problem with the change you propose is that the only criterion
able to expand the table size becomes disabled when it reaches 1UL <<
COUNT_COMMIT_ORDER. So clearly, it won't expand further, but it may need
to do so.

The reason why I use "count" here is because:

a) when accounting is available, we can expand the table in a
fine-grained way when there are few nodes (e.g. under nr_cpus * 1024).

b) when accounting is not available, we can expand the table all the
time when we encounter a long hash chain. Note that in this case,
"count" is always 0, because accounting is not available, so we never
disable the chain-length-based expand.

Thoughts ?

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |    5 +----
>  1 files changed, 1 insertions(+), 4 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 5ea133f..c0c452c 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -639,16 +639,13 @@ void ht_count_del(struct cds_lfht *ht, unsigned long size, unsigned long hash)
>  static
>  void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
>  {
> -	unsigned long count;
> -
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
> -	count = uatomic_read(&ht->count);
>  	/*
>  	 * Use bucket-local length for small table expand and for
>  	 * environments lacking per-cpu data support.
>  	 */
> -	if (count >= (1UL << COUNT_COMMIT_ORDER))
> +	if (size >= (1UL << COUNT_COMMIT_ORDER))
>  		return;
>  	if (chain_len > 100)
>  		dbg_printf("WARNING: large chain length: %u.\n",
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com