[ltt-dev] [PATCH 03/11] Move replace code out from _cds_lfht_add()

[Lai Jiangshan]

On 10/17/2011 10:46 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Make a function only do one thing.
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c |   38 ++++++++++++++------------------------
>>  1 files changed, 14 insertions(+), 24 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index 8433ec4..f412c6f 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -264,7 +264,6 @@ struct partition_resize_work {
>>  enum add_mode {
>>  	ADD_DEFAULT = 0,
>>  	ADD_UNIQUE = 1,
>> -	ADD_REPLACE = 2,
>>  };
>>  
>>  static
>> @@ -883,16 +882,13 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
>>  			next = rcu_dereference(clear_flag(iter)->p.next);
>>  			if (unlikely(is_removed(next)))
>>  				goto gc_node;
>> -			if ((mode == ADD_UNIQUE || mode == ADD_REPLACE)
>> +			if ((mode == ADD_UNIQUE)
>>  			    && !is_dummy(next)
>>  			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash
>>  			    && !ht->compare_fct(node->key, node->key_len,
>>  						clear_flag(iter)->key,
>>  						clear_flag(iter)->key_len)) {
>> -				if (mode == ADD_UNIQUE)
>> -					return clear_flag(iter);
>> -				else /* mode == ADD_REPLACE */
>> -					goto replace;
>> +				return clear_flag(iter);
>>  			}
>>  			/* Only account for identical reverse hash once */
>>  			if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
>> @@ -919,23 +915,10 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
>>  				    new_node) != iter) {
>>  			continue;	/* retry */
>>  		} else {
>> -			if (mode == ADD_REPLACE)
>> -				return_node = NULL;
>> -			else	/* ADD_DEFAULT and ADD_UNIQUE */
>> -				return_node = node;
>> +			return_node = node;
>>  			goto end;
>>  		}
>>  
>> -	replace:
>> -
>> -		if (!_cds_lfht_replace(ht, size, clear_flag(iter), next,
>> -				    node)) {
>> -			return_node = clear_flag(iter);
>> -			goto end;	/* gc already done */
>> -		} else {
>> -			continue;	/* retry */
>> -		}
>> -
>>  	gc_node:
>>  		assert(!is_removed(iter));
>>  		if (is_dummy(iter))
>> @@ -1455,10 +1438,17 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
>>  	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
>>  
>>  	size = rcu_dereference(ht->t.size);
>> -	ret = _cds_lfht_add(ht, size, node, ADD_REPLACE, 0);
>> -	if (ret == NULL)
>> -		ht_count_add(ht, size);
>> -	return ret;
>> +	for (;;) {
>> +		ret = _cds_lfht_add(ht, size, node, ADD_UNIQUE, 0);
>> +		if (ret == node) {
>> +			ht_count_add(ht, size);
>> +			return NULL;
>> +		}
>> +
>> +		if (!_cds_lfht_replace(ht, size, ret,
>> +				rcu_dereference(ret->p.next), node))
> 
> Hrm, if ret->p.next changes between the iteration done in _cds_lfht_add
> and this rcu_dereference, I think we may have an inconsistency. 

The only consistency need to be kept is: 'ret' node is the duplicated node.

If it is deleted: we will find it in _cds_lfht_replace() and then we try to _cds_lfht_add() again.
If it is kept with ret->p.next changed: _cds_lfht_replace() will loop until success or it is deleted

> We
> should return the ret next pointer read from _cds_lfht_add (maybe by
> adding a parameter to _cds_lfht_add), and use the returned pointer here
> instead. This will ensure that the checks done within the _cds_lfht_add
> iteration (is the pointer null, or is it logically removed) are still
> valid. Re-fetching the next value here skips these checks.
> 
> Thanks,
> 
> Mathieu
> 
>> +			return ret;
>> +	}
>>  }
>>  
>>  int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
>> -- 
>> 1.7.4.4
>>
>