[ltt-dev] [PATCH 1/6] rculfhash: Fix ht allocation bug

[ltt-dev] [PATCH 1/6] rculfhash: Fix ht allocation bug

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Fix a bug introduced by Lai Jiangshan <laijs at cn.fujitsu.com>:
> alloc_split_items_count() use a wrong flags.
> 
> ht->flags should be inited earlier.

Merged, thanks!

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index d786a3d..da37e97 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1330,6 +1330,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>  	init_size = max(init_size, min_alloc_size);
>  	ht = calloc(1, sizeof(struct cds_lfht));
>  	assert(ht);
> +	ht->flags = flags;
>  	ht->hash_fct = hash_fct;
>  	ht->compare_fct = compare_fct;
>  	ht->hash_seed = hash_seed;
> @@ -1345,7 +1346,6 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>  	alloc_split_items_count(ht);
>  	/* this mutex should not nest in read-side C.S. */
>  	pthread_mutex_init(&ht->resize_mutex, NULL);
> -	ht->flags = flags;
>  	order = get_count_order_ulong(init_size);
>  	ht->t.resize_target = 1UL << order;
>  	cds_lfht_create_dummy(ht, 1UL << order);
> -- 
> 1.7.4.4
> 

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

[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

[ltt-dev] [PATCH 6/6] rculfhash: add min_alloc_size test parameter

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

Merged, thanks !

Mathieu

> ---
>  tests/test_urcu_hash.c |   19 ++++++++++++++++++-
>  1 files changed, 18 insertions(+), 1 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 9ae1fa0..8f850ac 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -38,6 +38,7 @@
>  #endif
>  
>  #define DEFAULT_HASH_SIZE	32
> +#define DEFAULT_MIN_ALLOC_SIZE	1
>  #define DEFAULT_RAND_POOL	1000000
>  
>  /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
> @@ -114,6 +115,7 @@ static unsigned long duration;
>  static unsigned long rduration;
>  
>  static unsigned long init_hash_size = DEFAULT_HASH_SIZE;
> +static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE;
>  static unsigned long init_populate;
>  static int opt_auto_resize;
>  static int add_only, add_unique, add_replace;
> @@ -667,6 +669,7 @@ void show_usage(int argc, char **argv)
>  	printf("        [-v] (verbose output)\n");
>  	printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
>  	printf("        [-h size] (initial hash table size)\n");
> +	printf("        [-m size] (minimum hash alloc size)\n");
>  	printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
>  	printf("        [-u] Uniquify add (no redundant keys).\n");
>  	printf("        [-s] Replace (swap) entries.\n");
> @@ -768,6 +771,13 @@ int main(int argc, char **argv)
>  			}
>  			init_hash_size = atol(argv[++i]);
>  			break;
> +		case 'm':
> +			if (argc < i + 2) {
> +				show_usage(argc, argv);
> +				return -1;
> +			}
> +			min_hash_alloc_size = atol(argv[++i]);
> +			break;
>  		case 'u':
>  			if (add_replace) {
>  				printf("Please specify at most one of -s or -u.\n");
> @@ -823,6 +833,12 @@ int main(int argc, char **argv)
>  		return -1;
>  	}
>  
> +	if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
> +		printf("Error: Min hash alloc size %lu is not a power of 2.\n",
> +			min_hash_alloc_size);
> +		return -1;
> +	}
> +
>  	memset(&act, 0, sizeof(act));
>  	ret = sigemptyset(&act.sa_mask);
>  	if (ret == -1) {
> @@ -865,6 +881,7 @@ int main(int argc, char **argv)
>  		add_only ? " add only" : " add/remove",
>  		add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
>  	printf_verbose("Initial hash table size: %lu buckets.\n", init_hash_size);
> +	printf_verbose("Minimum hash alloc size: %lu buckets.\n", min_hash_alloc_size);
>  	printf_verbose("Init pool size offset %lu size %lu.\n",
>  		init_pool_offset, init_pool_size);
>  	printf_verbose("Lookup pool size offset %lu size %lu.\n",
> @@ -888,7 +905,7 @@ int main(int argc, char **argv)
>  	 */
>  	rcu_register_thread();
>  	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
> -			init_hash_size, 1,
> +			init_hash_size, min_hash_alloc_size,
>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>  			CDS_LFHT_ACCOUNTING, NULL);
>        	ret = populate_hash();
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 3/6] rculfhash: merge duplicated code of cds_lfht_resize_lazy_*()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

I'll let you refresh and respin this patch due to dependency on patch 2.

Thanks!

Mathieu

> ---
>  rculfhash.c |   35 ++++++++++++++---------------------
>  1 files changed, 14 insertions(+), 21 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index e97d854..c12ee10 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1759,13 +1759,9 @@ void do_resize_cb(struct rcu_head *head)
>  }
>  
>  static
> -void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
> +void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
>  {
>  	struct rcu_resize_work *work;
> -	unsigned long target_size = size << growth;
> -
> -	if (resize_target_grow(ht, target_size) >= target_size)
> -		return;
>  
>  	/* Store resize_target before read resize_initiated */
>  	cmm_smp_mb();
> @@ -1784,26 +1780,23 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
>  }
>  
>  static
> +void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
> +{
> +	unsigned long target_size = size << growth;
> +
> +	if (resize_target_grow(ht, target_size) >= target_size)
> +		return;
> +
> +	__cds_lfht_resize_lazy_launch(ht);
> +}
> +
> +static
>  void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>  				unsigned long count)
>  {
> -	struct rcu_resize_work *work;
> -
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
> +
>  	resize_target_update_count(ht, count);
> -	/* Store resize_target before read resize_initiated */
> -	cmm_smp_mb();
> -	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)) {
> -			uatomic_dec(&ht->in_progress_resize);
> -			return;
> -		}
> -		work = malloc(sizeof(*work));
> -		work->ht = ht;
> -		ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
> -		CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> -	}
> +	__cds_lfht_resize_lazy_launch(ht);
>  }
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 4/6] rculfhash: Change lazy shrink strategy

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> We can aggressively grow a ht,

What allows us to state that agressive grow is OK ?

> but we should conservatively shrink a ht.
> 
> When we try to shrink the ht after a deletion,
> but if a growing is required after it, we should
> stop this shrink.
> 
> But it is more complicated to implement it, so we use more
> conservative strategy to shrink a ht to gain simple code:
> 
> We stop to (lazy) shrink when we found growing is
> in progress.
> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |   29 ++++++++++++++++++++++++++++-
>  1 files changed, 28 insertions(+), 1 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index c12ee10..5ff832d 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1797,6 +1797,33 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
>  
> -	resize_target_update_count(ht, count);
> +	count = max(count, ht->min_alloc_size);
> +	if (count == size)
> +		return;
> +
> +	if (count > size) { /* lazy grow */
> +		if (resize_target_grow(ht, count) >= count)
> +			return;
> +	} else { /* lazy shrink */
> +		for (;;) {
> +			unsigned long s;
> +
> +			s = uatomic_cmpxchg(&ht->t.resize_target, size, count);

you could remove the empty lines in this code segment.

> +
> +			if (s == size)
> +				break;
> +
> +			/* growing is/(was just) in progress */
> +			if (s > size)
> +				return;
> +
> +			/* some other thread do shrink for me*/

missing space above.

> +			if (s <= count)
> +				return;

Keeping the behavior of size check (change to patch 2) will probably
affect this.

Thanks,

Mathieu

> +
> +			size = s;
> +		}
> +	}
> +
>  	__cds_lfht_resize_lazy_launch(ht);
>  }
> -- 
> 1.7.4.4
> 

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

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

[Lai Jiangshan]

On 11/02/2011 01:00 AM, Mathieu Desnoyers wrote:
> * 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.


size is stack local variable, and target_size is (size << growth) or
larger(concurrent calls to cds_lfht_resize_lazy),

so "size < target_size" is always true.

> 
> 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 ?

See above.

Thanks,
Lai

> 
> 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
>>
> 

[ltt-dev] [PATCH 4/6] rculfhash: Change lazy shrink strategy

[Lai Jiangshan]

On 11/02/2011 01:08 AM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> We can aggressively grow a ht,
> 
> What allows us to state that agressive grow is OK ?

I mean, if compare to shrinking, growing can be agressive a little more,
we can to do grow even the launching thread get old information.

But if compare to growing, shrinking must be conservative a little more,
if the launching thread find other thread are trying to grow ht,
it means the launching thread got old information, it should
stop to shrink.

I think I should used "relativistic agressive".

Thanks,
Lai


> 

> 
> missing space above.
> 
>> +			if (s <= count)
>> +				return;
> 
> Keeping the behavior of size check (change to patch 2) will probably
> affect this.

Waiting for your new reply for the patch 2.

> 
>> +
>> +			size = s;
>> +		}
>> +	}
>> +
>>  	__cds_lfht_resize_lazy_launch(ht);
>>  }
>> -- 
>> 1.7.4.4
>>
> 

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

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/02/2011 01:00 AM, Mathieu Desnoyers wrote:
> > * 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.
> 
> 
> size is stack local variable, and target_size is (size << growth) or
> larger(concurrent calls to cds_lfht_resize_lazy),
> 
> so "size < target_size" is always true.

Good point. Will looking into the patch again.

Thanks!

Mathieu

> 
> > 
> > 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 ?
> 
> See above.
> 
> Thanks,
> Lai
> 
> > 
> > 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

[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 we should grow the ht only when we success to increase
> the resize_target.

Merged, 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

[ltt-dev] [PATCH 3/6] rculfhash: merge duplicated code of cds_lfht_resize_lazy_*()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

merged, thanks !

Mathieu

> ---
>  rculfhash.c |   35 ++++++++++++++---------------------
>  1 files changed, 14 insertions(+), 21 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index e97d854..c12ee10 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1759,13 +1759,9 @@ void do_resize_cb(struct rcu_head *head)
>  }
>  
>  static
> -void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
> +void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
>  {
>  	struct rcu_resize_work *work;
> -	unsigned long target_size = size << growth;
> -
> -	if (resize_target_grow(ht, target_size) >= target_size)
> -		return;
>  
>  	/* Store resize_target before read resize_initiated */
>  	cmm_smp_mb();
> @@ -1784,26 +1780,23 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
>  }
>  
>  static
> +void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth)
> +{
> +	unsigned long target_size = size << growth;
> +
> +	if (resize_target_grow(ht, target_size) >= target_size)
> +		return;
> +
> +	__cds_lfht_resize_lazy_launch(ht);
> +}
> +
> +static
>  void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>  				unsigned long count)
>  {
> -	struct rcu_resize_work *work;
> -
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
> +
>  	resize_target_update_count(ht, count);
> -	/* Store resize_target before read resize_initiated */
> -	cmm_smp_mb();
> -	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)) {
> -			uatomic_dec(&ht->in_progress_resize);
> -			return;
> -		}
> -		work = malloc(sizeof(*work));
> -		work->ht = ht;
> -		ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
> -		CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> -	}
> +	__cds_lfht_resize_lazy_launch(ht);
>  }
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 4/6] rculfhash: Change lazy shrink strategy

[Mathieu Desnoyers]

merged as:

commit 89bb121d8cea974a8b6927499d917620236b7fee
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Wed Nov 2 11:31:14 2011 -0400

    rculfhash: Change lazy shrink strategy
    
    We can aggressively grow a ht,
    but we should conservatively shrink a ht.
    
    When we try to shrink the ht after a deletion,
    but if a growing is required after it, we should
    stop this shrink.
    
    But it is more complicated to implement it, so we use more
    conservative strategy to shrink a ht to gain simple code:
    
    We stop to (lazy) shrink when we found growing is
    in progress.
    
    [ Edit by Mathieu Desnoyers: Add documentation, cleanup. ]
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index ce7197a..600feec 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1827,13 +1827,36 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
 	__cds_lfht_resize_lazy_launch(ht);
 }
 
+/*
+ * We favor grow operations over shrink. A shrink operation never occurs
+ * if a grow operation is queued for lazy execution. A grow operation
+ * cancels any pending shrink lazy execution.
+ */
 static
 void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 				unsigned long count)
 {
 	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
 		return;
-
-	resize_target_update_count(ht, count);
+	count = max(count, ht->min_alloc_size);
+	if (count == size)
+		return;		/* Already the right size, no resize needed */
+	if (count > size) {	/* lazy grow */
+		if (resize_target_grow(ht, count) >= count)
+			return;
+	} else {		/* lazy shrink */
+		for (;;) {
+			unsigned long s;
+
+			s = uatomic_cmpxchg(&ht->t.resize_target, size, count);
+			if (s == size)
+				break;	/* no resize needed */
+			if (s > size)
+				return;	/* growing is/(was just) in progress */
+			if (s <= count)
+				return;	/* some other thread do shrink */
+			size = s;
+		}
+	}
 	__cds_lfht_resize_lazy_launch(ht);
 }

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