* Lai Jiangshan ([email protected]) wrote:
> On 10/28/2011 12:16 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan ([email protected]) 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 <[email protected]>
> >> ---
> >> 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
_______________________________________________
ltt-dev mailing list
[email protected]
http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
