[ltt-dev] [PATCH 2/6 respin] create dummy nodes directly when create lfht

[Lai Jiangshan]

On 10/28/2011 12:16 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 |   48 ++++++++++++++++++++++++++++++++++++++++++------
>>  1 files changed, 42 insertions(+), 6 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index 63a7ee4..ed02e80 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -1264,6 +1264,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++) {
>> +		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;
>> +			}
> 
> I fear I don't understand the intent of the above if / else if tests,
> nor the impact on the initialization. Can you enlighten me ?
> 

If all tables are located continuously, we can use
"prev++;"
only, it is enough. (That is a wonderful ability of the hash table).
but they are not located continuously,
so we have to jump two next tables if we reach the ead of the previous
table.

so "prev++" becomes/(is simulated as):

if (j & (j - 1)) {	/* still in the previous table */
	prev++;
} else {		/* "prev++" jump to next table */
	i++;
	prev = ht->t.tbl[i]->nodes;
}

because prev is inited before the "for" loop, we should
not do any when "j==0".
(we can also init "i = -1;" before the "for" loop to avoid this case.).

Thanks,
Lai.

> Thanks,
> 
> Mathieu
> 
>> +
>> +			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,
>> @@ -1303,14 +1342,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));
>>  	ht->flags = flags;
>> -	ht->cds_lfht_rcu_thread_offline();
>> -	pthread_mutex_lock(&ht->resize_mutex);
>> +	order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE));
>>  	ht->t.resize_target = 1UL << order;
>> -	init_table(ht, 0, order);
>> -	pthread_mutex_unlock(&ht->resize_mutex);
>> -	ht->cds_lfht_rcu_thread_online();
>> +	cds_lfht_create_dummy(ht, 1UL << order);
>> +	ht->t.size = 1UL << order;
>>  	return ht;
>>  }
>>  
>> -- 
>> 1.7.4.4
>>
>