From mboxrd@z Thu Jan 1 00:00:00 1970 From: laijs@cn.fujitsu.com (Lai Jiangshan) Date: Wed, 23 Nov 2011 14:33:57 +0800 Subject: [ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability In-Reply-To: <20111122095851.GB8332@Krystal> References: <1321426105-24303-1-git-send-email-laijs@cn.fujitsu.com> <1321426105-24303-2-git-send-email-laijs@cn.fujitsu.com> <20111122095851.GB8332@Krystal> Message-ID: <4ECC93D5.9040202@cn.fujitsu.com> On 11/22/2011 05:58 PM, Mathieu Desnoyers wrote: > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote: >> Fast path is not changed. >> It will slow down very little for slow path. > > it cleans up the code, so it's generally fine with me. There is just one > part that I don't understand, see below, > >> >> Signed-off-by: Lai Jiangshan >> --- >> rculfhash.c | 100 +++++++++++++++++++++++++++------------------------------- >> 1 files changed, 47 insertions(+), 53 deletions(-) >> >> diff --git a/rculfhash.c b/rculfhash.c >> index bda3bd6..b0c7de5 100644 >> --- a/rculfhash.c >> +++ b/rculfhash.c >> @@ -755,18 +755,14 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr, >> return old2; >> } >> >> -static >> -struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, >> - unsigned long hash) >> +static inline >> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) >> { >> - unsigned long index, order; >> - >> - assert(size > 0); >> - index = hash & (size - 1); >> + unsigned long order; >> >> - if (index < ht->min_alloc_size) { >> - dbg_printf("lookup hash %lu index %lu order 0 aridx 0\n", >> - hash, index); >> + if ((__builtin_constant_p(index) && index == 0) >> + || index < ht->min_alloc_size) { >> + dbg_printf("bucket index %lu order 0 aridx 0\n", index); >> return &ht->t.tbl[0]->nodes[index]; >> } >> /* >> @@ -775,11 +771,19 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, >> * get_count_order_ulong. >> */ >> order = fls_ulong(index); >> - dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", >> - hash, index, order, index & ((1UL << (order - 1)) - 1)); >> + dbg_printf("bucket index %lu order %lu aridx %lu\n", >> + index, order, index & ((1UL << (order - 1)) - 1)); >> return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)]; >> } >> >> +static inline >> +struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, >> + unsigned long hash) >> +{ >> + assert(size > 0); >> + return bucket_at(ht, hash & (size - 1)); >> +} >> + >> /* >> * Remove all logically deleted nodes from a bucket up to a certain node key. >> */ >> @@ -1105,19 +1109,18 @@ static >> void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, >> unsigned long start, unsigned long len) >> { >> - unsigned long j; >> + unsigned long j, size = 1UL << (i - 1); >> >> assert(i > ht->min_alloc_order); >> ht->cds_lfht_rcu_read_lock(); >> - for (j = start; j < start + len; j++) { >> - struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j]; >> - >> - dbg_printf("init populate: i %lu j %lu hash %lu\n", >> - i, j, (1UL << (i - 1)) + j); >> - new_node->reverse_hash = >> - bit_reverse_ulong((1UL << (i - 1)) + j); >> - _cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1), >> - new_node, NULL, 1); >> + for (j = start + size; j < size + start + len; j++) { > > Please use "j = size + start; j < size + start + len;" > >> + struct cds_lfht_node *new_node = bucket_at(ht, j); >> + >> + assert(j >= size && j < (size << 1)); >> + dbg_printf("init populate: order %lu index %lu hash %lu\n", >> + i, j, j); >> + new_node->reverse_hash = bit_reverse_ulong(j); >> + _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1); >> } >> ht->cds_lfht_rcu_read_unlock(); >> } >> @@ -1205,18 +1208,18 @@ static >> void remove_table_partition(struct cds_lfht *ht, unsigned long i, >> unsigned long start, unsigned long len) >> { >> - unsigned long j; >> + unsigned long j, size = 1UL << (i - 1); >> >> assert(i > ht->min_alloc_order); >> ht->cds_lfht_rcu_read_lock(); >> - for (j = start; j < start + len; j++) { >> - struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j]; >> - >> - dbg_printf("remove entry: i %lu j %lu hash %lu\n", >> - i, j, (1UL << (i - 1)) + j); >> - fini_node->reverse_hash = >> - bit_reverse_ulong((1UL << (i - 1)) + j); >> - (void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1); >> + for (j = size + start; j < size + start + len; j++) { >> + struct cds_lfht_node *fini_node = bucket_at(ht, j); >> + >> + assert(j >= size && j < (size << 1)); >> + dbg_printf("remove entry: order %lu index %lu hash %lu\n", >> + i, j, j); >> + fini_node->reverse_hash = bit_reverse_ulong(j); >> + (void) _cds_lfht_del(ht, size, fini_node, 1); >> } >> ht->cds_lfht_rcu_read_unlock(); >> } >> @@ -1293,14 +1296,15 @@ static >> void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size) >> { >> struct cds_lfht_node *prev, *node; >> - unsigned long order, len, i, j; >> + unsigned long order, len, i; >> >> ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node)); >> assert(ht->t.tbl[0]); >> >> - dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0); >> - ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end()); >> - ht->t.tbl[0]->nodes[0].reverse_hash = 0; >> + dbg_printf("create bucket: order 0 index 0 hash 0\n"); >> + node = bucket_at(ht, 0); >> + node->next = flag_bucket(get_end()); >> + node->reverse_hash = 0; >> >> for (order = 1; order < get_count_order_ulong(size) + 1; order++) { >> len = 1UL << (order - 1); >> @@ -1311,22 +1315,15 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size) >> assert(ht->t.tbl[order]); >> } >> > > below is the change I fail to understand. I think I'd need to be walked > through this change with an explanation, which could be added as a > comment telling what this function is doing. The "if else if" code simulates the code of "set prev as the bucket with index=i". it is "bucket_at(ht, i)". Now, we are trying to init the node with the hash=(i+len) (which is also a bucket with index=(i+len)) to the hash table, so this node has to be inserted after the bucket with index=i. And because there is no other non-bucket node nor bucket node with larger index inserted, so the bucket node with index=(i+len) should be inserted directly linked after the bucket node with index=i. > >> - i = 0; >> - prev = ht->t.tbl[i]->nodes; >> - for (j = 0; j < len; j++) { >> - if (j & (j - 1)) { /* Between power of 2 */ >> - prev++; >> - } else if (j) { /* At each power of 2 */ >> - i++; >> - prev = ht->t.tbl[i]->nodes; >> - } >> + for (i = 0; i < len; i++) { >> + prev = bucket_at(ht, i); >> + node = bucket_at(ht, i + len); > >