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

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> 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?
> 

See below,

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

I want to ensure that if you change the meaning of "order" in the code,
this change is performed across the whole file, to keep a single
semantic for "order".

Currently, what we have is:

(I'll call the current use of "order" "order-index", because you will
notice that it does not really keep track of the power of 2 order, due
to the + 1 offset for the 0 special-case):

Following the comment:

 * Order index is the off-by-one compare to the actual power of 2
 * because we use index 0 to deal with the 0 special-case.

"order-index"   array size
0               1
1               1
2               2
3               4
4               8
5               16
6               32
7               64

So a cleanup of this code would be to ensure that we don't refer to the
index within the "order table" as "order", because it is off-by-one
compared to the actual power-of-2 order of the array size for the array
corresponding to the index. Using "order" when we really refer to an
index that is off-by-one compared to the content power-of-2 order is
somewhat misleading.

So I think it is good to make sure this semantic gets clearer, but we
really need to go through the whole file and change the top-of-file
comments as well as the code within each function to ensure consistency.

> How about the next patches?

see following emails,

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