[ltt-dev] [PATCH 04/11] create dummy nodes directly when create lfht

[Lai Jiangshan]

On 10/17/2011 10:54 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> make cds_lfht_new() can be called earlier(before rcu is initialized ..etc)
>> If caller want to *parallelly* init the dummy nodes with large init_size,
>> he can use cds_lfht_new()+cds_lfht_resize() combination.
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c |   50 +++++++++++++++++++++++++++++++++++++++++++-------
>>  1 files changed, 43 insertions(+), 7 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index f412c6f..5dcae1f 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -1240,6 +1240,45 @@ void fini_table(struct cds_lfht *ht,
>>  	}
>>  }
>>  
>> +static
>> +void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
>> +{
>> +	struct _cds_lfht_node *prev, *node;
>> +	unsigned long order, len, i, j;
>> +
>> +	ht->t.tbl[0] = calloc(1, sizeof(struct _cds_lfht_node));
>> +	assert(ht->t.tbl[0]);
>> +
>> +	dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0);
>> +	ht->t.tbl[0]->nodes[0].next = flag_dummy(get_end());
>> +	ht->t.tbl[0]->nodes[0].reverse_hash = 0;
>> +
>> +	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {

		/* create the last table for the order */

> 
> see other comment below about the semantic of order changing. Maybe
> "index" or "order_idx" would be more appropriate here, because there is
> a + 1 offset compared to the actual order, to deal with the 0
> special-case.


order	ht_size	last_table_size	number_of_tables
0	1	1		1
1	2	1		2
2	4	2		3
3	8	4		4
4	16	8		5
5	32	16		6

The @order equals the actual order in the loop.
the name and semantic are correct here.

Or I miss your meaning?


> 
>> +		len = 1UL << (order - 1);
>> +		ht->t.tbl[order] = calloc(1, len * sizeof(struct _cds_lfht_node));
>> +		assert(ht->t.tbl[order]);
>> +
>> +		i = 0;
>> +		prev = ht->t.tbl[i]->nodes;
>> +		for (j = 0; j < len; j++) {
>> +			if (j & (j - 1)) {
>> +				prev++;
>> +			} else if (j) {
>> +				i++;
>> +				prev = ht->t.tbl[i]->nodes;
>> +			}
>> +
>> +			node = &ht->t.tbl[order]->nodes[j];
>> +			dbg_printf("create dummy: order %lu index %lu hash %lu\n",
>> +				   order, j, j + len);
>> +			node->next = prev->next;
>> +			assert(is_dummy(node->next));
>> +			node->reverse_hash = bit_reverse_ulong(j + len);
>> +			prev->next = flag_dummy((struct cds_lfht_node *)node);
>> +		}
>> +	}
>> +}
>> +
>>  struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>>  			cds_lfht_compare_fct compare_fct,
>>  			unsigned long hash_seed,
>> @@ -1279,14 +1318,11 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>>  	ht->percpu_count = alloc_per_cpu_items_count();
>>  	/* this mutex should not nest in read-side C.S. */
>>  	pthread_mutex_init(&ht->resize_mutex, NULL);
>> -	order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE)) + 1;
> 

The old "order" is incorrect for me, it is actually "number of tables"

> The line above,
> 
>>  	ht->flags = flags;
>> -	ht->cds_lfht_rcu_thread_offline();
>> -	pthread_mutex_lock(&ht->resize_mutex);
>> -	ht->t.resize_target = 1UL << (order - 1);
>> -	init_table(ht, 0, order);
>> -	pthread_mutex_unlock(&ht->resize_mutex);
>> -	ht->cds_lfht_rcu_thread_online();
>> +	order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE));
> 
> and this line:
> 
> notice that the semantic of "order" is changing, and I think this is
> good: The order really becomes the power of 2 order of the size, rather
> than the "index" in the "order array" which is offset by + 1 compared to
> the actual order value to deal with the 0 special-case.
> 
> We should also make sure that this semantic change does not affect the
> rest of the code. Given that we communicate the target size and size
> with "resize_target" and "size", I think we should be fine for this.
> 


Any problem of the code?
How about the next patches?

> 
>> +	ht->t.resize_target = 1UL << order;
>> +	cds_lfht_create_dummy(ht, 1UL << order);
>> +	ht->t.size = 1UL << order;
>>  	return ht;
>>  }
>>  
>> -- 
>> 1.7.4.4
>>
>