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

[Mathieu Desnoyers]

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

Yes, that's clearer now. I'll continue working my way through the
patchset pulls :)

Thanks!

Mathieu

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

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