[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Tue Nov 22 04:58:51 EST 2011
* 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 <laijs at cn.fujitsu.com>
> ---
> 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.
> - 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);
Using "len + i" would help us follow the code, as i changes, but not
len. I usually try to put the iterators that change the most (innermost
indexes) at the right.
>
> - node = &ht->t.tbl[order]->nodes[j];
> dbg_printf("create bucket: order %lu index %lu hash %lu\n",
> - order, j, j + len);
> + order, i + len, i + len);
Same here,
> node->next = prev->next;
> assert(is_bucket(node->next));
> - node->reverse_hash = bit_reverse_ulong(j + len);
> + node->reverse_hash = bit_reverse_ulong(i + len);
Same here,
Thanks!
Mathieu
> prev->next = flag_bucket(node);
> }
> }
> @@ -1476,14 +1473,11 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>
> void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
> {
> - struct cds_lfht_node *lookup;
> -
> /*
> * Get next after first bucket node. The first bucket node is the
> * first node of the linked list.
> */
> - lookup = &ht->t.tbl[0]->nodes[0];
> - iter->next = lookup->next;
> + iter->next = bucket_at(ht, 0)->next;
> cds_lfht_next(ht, iter);
> }
>
> @@ -1569,7 +1563,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
> unsigned long order, i, size;
>
> /* Check that the table is empty */
> - node = &ht->t.tbl[0]->nodes[0];
> + node = bucket_at(ht, 0);
> do {
> node = clear_flag(node)->next;
> if (!is_bucket(node))
> @@ -1648,7 +1642,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
> *removed = 0;
>
> /* Count non-bucket nodes in the table */
> - node = &ht->t.tbl[0]->nodes[0];
> + node = bucket_at(ht, 0);
> do {
> next = rcu_dereference(node->next);
> if (is_removed(next)) {
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list