[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability

[laijs@cn.fujitsu.com (Lai Jiangshan)]

On 11/22/2011 05:58 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Fast path is not changed.
>> It will slow down very little for slow path.
> 
> it cleans up the code, so it's generally fine with me. There is just one
> part that I don't understand, see below,
> 
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c |  100 +++++++++++++++++++++++++++-------------------------------
>>  1 files changed, 47 insertions(+), 53 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index bda3bd6..b0c7de5 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -755,18 +755,14 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
>>  	return old2;
>>  }
>>  
>> -static
>> -struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
>> -		unsigned long hash)
>> +static inline
>> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>>  {
>> -	unsigned long index, order;
>> -
>> -	assert(size > 0);
>> -	index = hash & (size - 1);
>> +	unsigned long order;
>>  
>> -	if (index < ht->min_alloc_size) {
>> -		dbg_printf("lookup hash %lu index %lu order 0 aridx 0\n",
>> -			   hash, index);
>> +	if ((__builtin_constant_p(index) && index == 0)
>> +			|| index < ht->min_alloc_size) {
>> +		dbg_printf("bucket index %lu order 0 aridx 0\n", index);
>>  		return &ht->t.tbl[0]->nodes[index];
>>  	}
>>  	/*
>> @@ -775,11 +771,19 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
>>  	 * get_count_order_ulong.
>>  	 */
>>  	order = fls_ulong(index);
>> -	dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
>> -		   hash, index, order, index & ((1UL << (order - 1)) - 1));
>> +	dbg_printf("bucket index %lu order %lu aridx %lu\n",
>> +		   index, order, index & ((1UL << (order - 1)) - 1));
>>  	return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)];
>>  }
>>  
>> +static inline
>> +struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
>> +		unsigned long hash)
>> +{
>> +	assert(size > 0);
>> +	return bucket_at(ht, hash & (size - 1));
>> +}
>> +
>>  /*
>>   * Remove all logically deleted nodes from a bucket up to a certain node key.
>>   */
>> @@ -1105,19 +1109,18 @@ static
>>  void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
>>  				   unsigned long start, unsigned long len)
>>  {
>> -	unsigned long j;
>> +	unsigned long j, size = 1UL << (i - 1);
>>  
>>  	assert(i > ht->min_alloc_order);
>>  	ht->cds_lfht_rcu_read_lock();
>> -	for (j = start; j < start + len; j++) {
>> -		struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
>> -
>> -		dbg_printf("init populate: i %lu j %lu hash %lu\n",
>> -			   i, j, (1UL << (i - 1)) + j);
>> -		new_node->reverse_hash =
>> -				bit_reverse_ulong((1UL << (i - 1)) + j);
>> -		_cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1),
>> -				new_node, NULL, 1);
>> +	for (j = start + size; j < size + start + len; j++) {
> 
> Please use "j = size + start; j < size + start + len;"
> 
>> +		struct cds_lfht_node *new_node = bucket_at(ht, j);
>> +
>> +		assert(j >= size && j < (size << 1));
>> +		dbg_printf("init populate: order %lu index %lu hash %lu\n",
>> +			   i, j, j);
>> +		new_node->reverse_hash = bit_reverse_ulong(j);
>> +		_cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
>>  	}
>>  	ht->cds_lfht_rcu_read_unlock();
>>  }
>> @@ -1205,18 +1208,18 @@ static
>>  void remove_table_partition(struct cds_lfht *ht, unsigned long i,
>>  			    unsigned long start, unsigned long len)
>>  {
>> -	unsigned long j;
>> +	unsigned long j, size = 1UL << (i - 1);
>>  
>>  	assert(i > ht->min_alloc_order);
>>  	ht->cds_lfht_rcu_read_lock();
>> -	for (j = start; j < start + len; j++) {
>> -		struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
>> -
>> -		dbg_printf("remove entry: i %lu j %lu hash %lu\n",
>> -			   i, j, (1UL << (i - 1)) + j);
>> -		fini_node->reverse_hash =
>> -			bit_reverse_ulong((1UL << (i - 1)) + j);
>> -		(void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
>> +	for (j = size + start; j < size + start + len; j++) {
>> +		struct cds_lfht_node *fini_node = bucket_at(ht, j);
>> +
>> +		assert(j >= size && j < (size << 1));
>> +		dbg_printf("remove entry: order %lu index %lu hash %lu\n",
>> +			   i, j, j);
>> +		fini_node->reverse_hash = bit_reverse_ulong(j);
>> +		(void) _cds_lfht_del(ht, size, fini_node, 1);
>>  	}
>>  	ht->cds_lfht_rcu_read_unlock();
>>  }
>> @@ -1293,14 +1296,15 @@ static
>>  void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>>  {
>>  	struct cds_lfht_node *prev, *node;
>> -	unsigned long order, len, i, j;
>> +	unsigned long order, len, i;
>>  
>>  	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
>>  	assert(ht->t.tbl[0]);
>>  
>> -	dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0);
>> -	ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end());
>> -	ht->t.tbl[0]->nodes[0].reverse_hash = 0;
>> +	dbg_printf("create bucket: order 0 index 0 hash 0\n");
>> +	node = bucket_at(ht, 0);
>> +	node->next = flag_bucket(get_end());
>> +	node->reverse_hash = 0;
>>  
>>  	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
>>  		len = 1UL << (order - 1);
>> @@ -1311,22 +1315,15 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>>  			assert(ht->t.tbl[order]);
>>  		}
>>  
> 
> below is the change I fail to understand. I think I'd need to be walked
> through this change with an explanation, which could be added as a
> comment telling what this function is doing.

The "if else if" code simulates the code of "set prev as the bucket with index=i".
it is "bucket_at(ht, i)".

Now, we are trying to init the node with the hash=(i+len) (which is also
a bucket with index=(i+len)) to the hash table, so this node has to be inserted
after the bucket with index=i. And because there is no other non-bucket node
nor bucket node with larger index inserted, so the bucket node with index=(i+len)
should be inserted directly linked after the bucket node with index=i.


> 
>> -		i = 0;
>> -		prev = ht->t.tbl[i]->nodes;
>> -		for (j = 0; j < len; j++) {
>> -			if (j & (j - 1)) {	/* Between power of 2 */
>> -				prev++;
>> -			} else if (j) {		/* At each power of 2 */
>> -				i++;
>> -				prev = ht->t.tbl[i]->nodes;
>> -			}
>> +		for (i = 0; i < len; i++) {
>> +			prev = bucket_at(ht, i);
>> +			node = bucket_at(ht, i + len);
> 
>