[ltt-dev] [PATCH 2/6] rculfhash: Fix ht lazy grow logic.

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> "size < target_size" in cds_lfht_resize_lazy() which is always true
> confuses me.

I think it can be false sometimes if we have multiple concurrent calls
to cds_lfht_resize_lazy. If the first call succeeds, the resize happens,
and then a second call gets to try the resize again, but the table
already has grown. In this case, the resize work does not need to be
executed.

The resize_initiated flag is just a hint telling if a resize is in
progress (so we don't trigger extra resize work when unnecessary), but
it is not sampled before the RCU reads are performed -- only the "size"
is read with rcu_dereference, which ensures that we can use this size
information to confirm that the chain length that we read _after_ the
rcu_dereference actually apply to a size we really want to update. The
resize_initiated flag does not provide this guarantee.

> 
> I think we should grow the ht only when we success to increase
> the resize_target.

I agree on this second change.

Can you respin this patch leaving the ""size < target_size" in place ?

You can add my comments above as documentation of cds_lfht_resize_lazy()
if you want.

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |   25 +++++++++++++------------
>  1 files changed, 13 insertions(+), 12 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index da37e97..e97d854 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -498,7 +498,7 @@ int get_count_order_ulong(unsigned long x)
>  #endif
>  
>  static
> -void cds_lfht_resize_lazy(struct cds_lfht *ht, unsigned long size, int growth);
> +void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth);
>  
>  static
>  void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
> @@ -659,7 +659,7 @@ void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
>  		dbg_printf("WARNING: large chain length: %u.\n",
>  			   chain_len);
>  	if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
> -		cds_lfht_resize_lazy(ht, size,
> +		cds_lfht_resize_lazy_grow(ht, size,
>  			get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
>  }
>  
> @@ -706,7 +706,8 @@ int is_end(struct cds_lfht_node *node)
>  }
>  
>  static
> -unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
> +unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> +		unsigned long v)
>  {
>  	unsigned long old1, old2;
>  
> @@ -716,7 +717,7 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
>  		if (old2 >= v)
>  			return old2;
>  	} while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
> -	return v;
> +	return old2;
>  }
>  
>  static
> @@ -1716,11 +1717,9 @@ void _do_cds_lfht_resize(struct cds_lfht *ht)
>  }
>  
>  static
> -unsigned long resize_target_update(struct cds_lfht *ht, unsigned long size,
> -				   int growth_order)
> +unsigned long resize_target_grow(struct cds_lfht *ht, unsigned long new_size)
>  {
> -	return _uatomic_max(&ht->t.resize_target,
> -			    size << growth_order);
> +	return _uatomic_xchg_monotonic_increase(&ht->t.resize_target, new_size);
>  }
>  
>  static
> @@ -1760,15 +1759,17 @@ void do_resize_cb(struct rcu_head *head)
>  }
>  
>  static
> -void cds_lfht_resize_lazy(struct cds_lfht *ht, unsigned long size, int growth)
> +void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
>  {
>  	struct rcu_resize_work *work;
> -	unsigned long target_size;
> +	unsigned long target_size = size << growth;
> +
> +	if (resize_target_grow(ht, target_size) >= target_size)
> +		return;
>  
> -	target_size = resize_target_update(ht, size, growth);
>  	/* Store resize_target before read resize_initiated */
>  	cmm_smp_mb();
> -	if (!CMM_LOAD_SHARED(ht->t.resize_initiated) && size < target_size) {
> +	if (!CMM_LOAD_SHARED(ht->t.resize_initiated)) {
>  		uatomic_inc(&ht->in_progress_resize);
>  		cmm_smp_mb();	/* increment resize count before load destroy */
>  		if (CMM_LOAD_SHARED(ht->in_progress_destroy)) {
> -- 
> 1.7.4.4
> 

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