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

[Mathieu Desnoyers]

* 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++) {

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.

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

Thanks,

Mathieu

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

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