[ltt-dev] [PATCH 00/10 round10] rculfhash memory managements

[ltt-dev] [PATCH 00/10 round10] rculfhash memory managements

[Lai Jiangshan]

Patch 1-5: extract memory managements (internal)APIs and prepare
           for memory managements

Patch 6-8: Add two memory managements and comments.
           You can read or apply patch 8 before patch 6,7

Patch 10 add my name to rculfhash.c and urcu/rculfhash.h


Lai Jiangshan (10):
  introduce bucket_at() and improve readability
  proper wrapper for bucket table alloc and free
  ht->t.size is no required larger than ht->min_table_size now
  remove struct rcu_level
  add max_size arguemnt
  add LFHT_MEMORY_CHUNK low level memory management
  add LFHT_MEMORY_RESERVED low level memory management
  comments for memory management
  fix comments of cds_lfht_new()
  add my name

 rculfhash.c            |  503 +++++++++++++++++++++++++++++++++++++-----------
 tests/test_urcu_hash.c |    4 +-
 urcu/rculfhash.h       |   15 +-
 3 files changed, 405 insertions(+), 117 deletions(-)

-- 
1.7.4.4

[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability

[Lai Jiangshan]

Fast path is not changed.
It will slow down very little for slow path.

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++) {
+		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]);
 		}
 
-		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);
 
-			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);
 			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);
 			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

[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability

[Mathieu Desnoyers]

* 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

[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability

[Lai Jiangshan]

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

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

[ltt-dev] [PATCH 01/10 round10] introduce bucket_at() and improve readability

[Mathieu Desnoyers]

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

Sounds like a very reasonable explanation to me. Please add this as a
comment block above the function.

Thanks!

Mathieu

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

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

[ltt-dev] [PATCH 02/10 round10] proper wrapper for bucket table alloc and free

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |   78 +++++++++++++++++++++++++++++++++++-----------------------
 1 files changed, 47 insertions(+), 31 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index b0c7de5..c7f993f 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -755,6 +755,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
 	return old2;
 }
 
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		ht->t.tbl[0] = calloc(ht->min_alloc_size,
+			sizeof(struct cds_lfht_node));
+		assert(ht->t.tbl[0]);
+	} else if (order > ht->min_alloc_order) {
+		ht->t.tbl[order] = calloc(1UL << (order -1),
+			sizeof(struct cds_lfht_node));
+		assert(ht->t.tbl[order]);
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0)
+		poison_free(ht->t.tbl[0]);
+	else if (order > ht->min_alloc_order)
+		poison_free(ht->t.tbl[order]);
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
 static inline
 struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 {
@@ -1158,8 +1188,7 @@ void init_table(struct cds_lfht *ht,
 		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
 			break;
 
-		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
-		assert(ht->t.tbl[i]);
+		cds_lfht_alloc_bucket_table(ht, i);
 
 		/*
 		 * Set all bucket nodes reverse hash values for a level and
@@ -1243,7 +1272,7 @@ void fini_table(struct cds_lfht *ht,
 		unsigned long first_order, unsigned long last_order)
 {
 	long i;
-	void *free_by_rcu = NULL;
+	unsigned long free_by_rcu_order = 0;
 
 	dbg_printf("fini table: first_order %lu last_order %lu\n",
 		   first_order, last_order);
@@ -1268,8 +1297,8 @@ void fini_table(struct cds_lfht *ht,
 		 * return a logically removed node as insert position.
 		 */
 		ht->cds_lfht_synchronize_rcu();
-		if (free_by_rcu)
-			free(free_by_rcu);
+		if (free_by_rcu_order)
+			cds_lfht_free_bucket_table(ht, free_by_rcu_order);
 
 		/*
 		 * Set "removed" flag in bucket nodes about to be removed.
@@ -1279,16 +1308,16 @@ void fini_table(struct cds_lfht *ht,
 		 */
 		remove_table(ht, i, len);
 
-		free_by_rcu = ht->t.tbl[i];
+		free_by_rcu_order = i;
 
 		dbg_printf("fini new size: %lu\n", 1UL << i);
 		if (CMM_LOAD_SHARED(ht->in_progress_destroy))
 			break;
 	}
 
-	if (free_by_rcu) {
+	if (free_by_rcu_order) {
 		ht->cds_lfht_synchronize_rcu();
-		free(free_by_rcu);
+		cds_lfht_free_bucket_table(ht, free_by_rcu_order);
 	}
 }
 
@@ -1298,8 +1327,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
 	struct cds_lfht_node *prev, *node;
 	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]);
+	cds_lfht_alloc_bucket_table(ht, 0);
 
 	dbg_printf("create bucket: order 0 index 0 hash 0\n");
 	node = bucket_at(ht, 0);
@@ -1308,12 +1336,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
 
 	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
 		len = 1UL << (order - 1);
-		if (order <= ht->min_alloc_order) {
-			ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
-		} else {
-			ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
-			assert(ht->t.tbl[order]);
-		}
+		cds_lfht_alloc_bucket_table(ht, order);
 
 		for (i = 0; i < len; i++) {
 			prev = bucket_at(ht, i);
@@ -1576,23 +1599,16 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
 	 */
 	size = ht->t.size;
 	/* Internal sanity check: all nodes left should be bucket */
-	for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
-		unsigned long len;
+	for (i = 0; i < size; i++) {
+		node = bucket_at(ht, i);
+		dbg_printf("delete bucket: index %lu expected hash %lu hash %lu\n",
+			i, i, bit_reverse_ulong(node->reverse_hash));
+		assert(is_bucket(node->next));
+	}
 
-		len = !order ? 1 : 1UL << (order - 1);
-		for (i = 0; i < len; i++) {
-			dbg_printf("delete order %lu i %lu hash %lu\n",
-				order, i,
-				bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
-			assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
-		}
+	for (order = get_count_order_ulong(size); (long)order >= 0; order--)
+		cds_lfht_free_bucket_table(ht, order);
 
-		if (order == ht->min_alloc_order)
-			poison_free(ht->t.tbl[0]);
-		else if (order > ht->min_alloc_order)
-			poison_free(ht->t.tbl[order]);
-		/* Nothing to delete for order < ht->min_alloc_order */
-	}
 	return 0;
 }
 
-- 
1.7.4.4

[ltt-dev] [PATCH 02/10 round10] proper wrapper for bucket table alloc and free

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |   78 +++++++++++++++++++++++++++++++++++-----------------------
>  1 files changed, 47 insertions(+), 31 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index b0c7de5..c7f993f 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -755,6 +755,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
>  	return old2;
>  }
>  
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0) {
> +		ht->t.tbl[0] = calloc(ht->min_alloc_size,
> +			sizeof(struct cds_lfht_node));
> +		assert(ht->t.tbl[0]);
> +	} else if (order > ht->min_alloc_order) {
> +		ht->t.tbl[order] = calloc(1UL << (order -1),
> +			sizeof(struct cds_lfht_node));
> +		assert(ht->t.tbl[order]);
> +	}
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0)
> +		poison_free(ht->t.tbl[0]);
> +	else if (order > ht->min_alloc_order)
> +		poison_free(ht->t.tbl[order]);
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
>  static inline
>  struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>  {
> @@ -1158,8 +1188,7 @@ void init_table(struct cds_lfht *ht,
>  		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
>  			break;
>  
> -		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
> -		assert(ht->t.tbl[i]);
> +		cds_lfht_alloc_bucket_table(ht, i);
>  
>  		/*
>  		 * Set all bucket nodes reverse hash values for a level and
> @@ -1243,7 +1272,7 @@ void fini_table(struct cds_lfht *ht,
>  		unsigned long first_order, unsigned long last_order)
>  {
>  	long i;
> -	void *free_by_rcu = NULL;
> +	unsigned long free_by_rcu_order = 0;
>  
>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
>  		   first_order, last_order);
> @@ -1268,8 +1297,8 @@ void fini_table(struct cds_lfht *ht,
>  		 * return a logically removed node as insert position.
>  		 */
>  		ht->cds_lfht_synchronize_rcu();
> -		if (free_by_rcu)
> -			free(free_by_rcu);
> +		if (free_by_rcu_order)
> +			cds_lfht_free_bucket_table(ht, free_by_rcu_order);
>  
>  		/*
>  		 * Set "removed" flag in bucket nodes about to be removed.
> @@ -1279,16 +1308,16 @@ void fini_table(struct cds_lfht *ht,
>  		 */
>  		remove_table(ht, i, len);
>  
> -		free_by_rcu = ht->t.tbl[i];
> +		free_by_rcu_order = i;

Hrm, so for i = 0 (order 0), we never call free() ?

Thanks,

Mathieu

>  
>  		dbg_printf("fini new size: %lu\n", 1UL << i);
>  		if (CMM_LOAD_SHARED(ht->in_progress_destroy))
>  			break;
>  	}
>  
> -	if (free_by_rcu) {
> +	if (free_by_rcu_order) {
>  		ht->cds_lfht_synchronize_rcu();
> -		free(free_by_rcu);
> +		cds_lfht_free_bucket_table(ht, free_by_rcu_order);
>  	}
>  }
>  
> @@ -1298,8 +1327,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>  	struct cds_lfht_node *prev, *node;
>  	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]);
> +	cds_lfht_alloc_bucket_table(ht, 0);
>  
>  	dbg_printf("create bucket: order 0 index 0 hash 0\n");
>  	node = bucket_at(ht, 0);
> @@ -1308,12 +1336,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>  
>  	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
>  		len = 1UL << (order - 1);
> -		if (order <= ht->min_alloc_order) {
> -			ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
> -		} else {
> -			ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
> -			assert(ht->t.tbl[order]);
> -		}
> +		cds_lfht_alloc_bucket_table(ht, order);
>  
>  		for (i = 0; i < len; i++) {
>  			prev = bucket_at(ht, i);
> @@ -1576,23 +1599,16 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
>  	 */
>  	size = ht->t.size;
>  	/* Internal sanity check: all nodes left should be bucket */
> -	for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
> -		unsigned long len;
> +	for (i = 0; i < size; i++) {
> +		node = bucket_at(ht, i);
> +		dbg_printf("delete bucket: index %lu expected hash %lu hash %lu\n",
> +			i, i, bit_reverse_ulong(node->reverse_hash));
> +		assert(is_bucket(node->next));
> +	}
>  
> -		len = !order ? 1 : 1UL << (order - 1);
> -		for (i = 0; i < len; i++) {
> -			dbg_printf("delete order %lu i %lu hash %lu\n",
> -				order, i,
> -				bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
> -			assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
> -		}
> +	for (order = get_count_order_ulong(size); (long)order >= 0; order--)
> +		cds_lfht_free_bucket_table(ht, order);
>  
> -		if (order == ht->min_alloc_order)
> -			poison_free(ht->t.tbl[0]);
> -		else if (order > ht->min_alloc_order)
> -			poison_free(ht->t.tbl[order]);
> -		/* Nothing to delete for order < ht->min_alloc_order */
> -	}
>  	return 0;
>  }
>  
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 02/10 round10] proper wrapper for bucket table alloc and free

[Lai Jiangshan]

On 11/22/2011 06:01 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c |   78 +++++++++++++++++++++++++++++++++++-----------------------
>>  1 files changed, 47 insertions(+), 31 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index b0c7de5..c7f993f 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -755,6 +755,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
>>  	return old2;
>>  }
>>  
>> +static
>> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
>> +{
>> +	if (order == 0) {
>> +		ht->t.tbl[0] = calloc(ht->min_alloc_size,
>> +			sizeof(struct cds_lfht_node));
>> +		assert(ht->t.tbl[0]);
>> +	} else if (order > ht->min_alloc_order) {
>> +		ht->t.tbl[order] = calloc(1UL << (order -1),
>> +			sizeof(struct cds_lfht_node));
>> +		assert(ht->t.tbl[order]);
>> +	}
>> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
>> +}
>> +
>> +/*
>> + * cds_lfht_free_bucket_table() should be called with decreasing order.
>> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
>> + * lfht is destroyed.
>> + */
>> +static
>> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
>> +{
>> +	if (order == 0)
>> +		poison_free(ht->t.tbl[0]);
>> +	else if (order > ht->min_alloc_order)
>> +		poison_free(ht->t.tbl[order]);
>> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
>> +}
>> +
>>  static inline
>>  struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>>  {
>> @@ -1158,8 +1188,7 @@ void init_table(struct cds_lfht *ht,
>>  		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
>>  			break;
>>  
>> -		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
>> -		assert(ht->t.tbl[i]);
>> +		cds_lfht_alloc_bucket_table(ht, i);
>>  
>>  		/*
>>  		 * Set all bucket nodes reverse hash values for a level and
>> @@ -1243,7 +1272,7 @@ void fini_table(struct cds_lfht *ht,
>>  		unsigned long first_order, unsigned long last_order)
>>  {
>>  	long i;
>> -	void *free_by_rcu = NULL;
>> +	unsigned long free_by_rcu_order = 0;
>>  
>>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
>>  		   first_order, last_order);
>> @@ -1268,8 +1297,8 @@ void fini_table(struct cds_lfht *ht,
>>  		 * return a logically removed node as insert position.
>>  		 */
>>  		ht->cds_lfht_synchronize_rcu();
>> -		if (free_by_rcu)
>> -			free(free_by_rcu);
>> +		if (free_by_rcu_order)
>> +			cds_lfht_free_bucket_table(ht, free_by_rcu_order);
>>  
>>  		/*
>>  		 * Set "removed" flag in bucket nodes about to be removed.
>> @@ -1279,16 +1308,16 @@ void fini_table(struct cds_lfht *ht,
>>  		 */
>>  		remove_table(ht, i, len);
>>  
>> -		free_by_rcu = ht->t.tbl[i];
>> +		free_by_rcu_order = i;
> 
> Hrm, so for i = 0 (order 0), we never call free() ?
> 

You can find the "assert" before the loop, the i is not possible 0.
when ds_lfht_free_bucket_table(0), it means the whole hash table is
being destroyed, it is not happened now.

Thanks,
Lai

[ltt-dev] [PATCH 02/10 round10] proper wrapper for bucket table alloc and free

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/22/2011 06:01 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >>  rculfhash.c |   78 +++++++++++++++++++++++++++++++++++-----------------------
> >>  1 files changed, 47 insertions(+), 31 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index b0c7de5..c7f993f 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -755,6 +755,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> >>  	return old2;
> >>  }
> >>  
> >> +static
> >> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> >> +{
> >> +	if (order == 0) {
> >> +		ht->t.tbl[0] = calloc(ht->min_alloc_size,
> >> +			sizeof(struct cds_lfht_node));
> >> +		assert(ht->t.tbl[0]);
> >> +	} else if (order > ht->min_alloc_order) {
> >> +		ht->t.tbl[order] = calloc(1UL << (order -1),
> >> +			sizeof(struct cds_lfht_node));
> >> +		assert(ht->t.tbl[order]);
> >> +	}
> >> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> >> +}
> >> +
> >> +/*
> >> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> >> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> >> + * lfht is destroyed.
> >> + */
> >> +static
> >> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> >> +{
> >> +	if (order == 0)
> >> +		poison_free(ht->t.tbl[0]);
> >> +	else if (order > ht->min_alloc_order)
> >> +		poison_free(ht->t.tbl[order]);
> >> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> >> +}
> >> +
> >>  static inline
> >>  struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> >>  {
> >> @@ -1158,8 +1188,7 @@ void init_table(struct cds_lfht *ht,
> >>  		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
> >>  			break;
> >>  
> >> -		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
> >> -		assert(ht->t.tbl[i]);
> >> +		cds_lfht_alloc_bucket_table(ht, i);
> >>  
> >>  		/*
> >>  		 * Set all bucket nodes reverse hash values for a level and
> >> @@ -1243,7 +1272,7 @@ void fini_table(struct cds_lfht *ht,
> >>  		unsigned long first_order, unsigned long last_order)
> >>  {
> >>  	long i;
> >> -	void *free_by_rcu = NULL;
> >> +	unsigned long free_by_rcu_order = 0;
> >>  
> >>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
> >>  		   first_order, last_order);
> >> @@ -1268,8 +1297,8 @@ void fini_table(struct cds_lfht *ht,
> >>  		 * return a logically removed node as insert position.
> >>  		 */
> >>  		ht->cds_lfht_synchronize_rcu();
> >> -		if (free_by_rcu)
> >> -			free(free_by_rcu);
> >> +		if (free_by_rcu_order)
> >> +			cds_lfht_free_bucket_table(ht, free_by_rcu_order);
> >>  
> >>  		/*
> >>  		 * Set "removed" flag in bucket nodes about to be removed.
> >> @@ -1279,16 +1308,16 @@ void fini_table(struct cds_lfht *ht,
> >>  		 */
> >>  		remove_table(ht, i, len);
> >>  
> >> -		free_by_rcu = ht->t.tbl[i];
> >> +		free_by_rcu_order = i;
> > 
> > Hrm, so for i = 0 (order 0), we never call free() ?
> > 
> 
> You can find the "assert" before the loop, the i is not possible 0.
> when ds_lfht_free_bucket_table(0), it means the whole hash table is
> being destroyed, it is not happened now.

I see, sounds good!

Thanks,

Mathieu

> 
> Thanks,
> Lai

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

[ltt-dev] [PATCH 03/10 round10] ht->t.size is no required larger than ht->min_table_size now

[Lai Jiangshan]

Thanks to the wrappers of bucket table alloc/free.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |   19 ++++++++++---------
 tests/test_urcu_hash.c |    2 +-
 2 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index c7f993f..a72e1a5 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -186,7 +186,8 @@
 /*
  * Define the minimum table size.
  */
-#define MIN_TABLE_SIZE			1
+#define MIN_TABLE_ORDER			0
+#define MIN_TABLE_SIZE			(1UL << MIN_TABLE_ORDER)
 
 #if (CAA_BITS_PER_LONG == 32)
 #define MAX_TABLE_ORDER			32
@@ -1141,7 +1142,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
 {
 	unsigned long j, size = 1UL << (i - 1);
 
-	assert(i > ht->min_alloc_order);
+	assert(i > MIN_TABLE_ORDER);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = start + size; j < size + start + len; j++) {
 		struct cds_lfht_node *new_node = bucket_at(ht, j);
@@ -1177,7 +1178,7 @@ void init_table(struct cds_lfht *ht,
 
 	dbg_printf("init table: first_order %lu last_order %lu\n",
 		   first_order, last_order);
-	assert(first_order > ht->min_alloc_order);
+	assert(first_order > MIN_TABLE_ORDER);
 	for (i = first_order; i <= last_order; i++) {
 		unsigned long len;
 
@@ -1239,7 +1240,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
 {
 	unsigned long j, size = 1UL << (i - 1);
 
-	assert(i > ht->min_alloc_order);
+	assert(i > MIN_TABLE_ORDER);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = size + start; j < size + start + len; j++) {
 		struct cds_lfht_node *fini_node = bucket_at(ht, j);
@@ -1276,7 +1277,7 @@ void fini_table(struct cds_lfht *ht,
 
 	dbg_printf("fini table: first_order %lu last_order %lu\n",
 		   first_order, last_order);
-	assert(first_order > ht->min_alloc_order);
+	assert(first_order > MIN_TABLE_ORDER);
 	for (i = last_order; i >= first_order; i--) {
 		unsigned long len;
 
@@ -1376,7 +1377,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	if (!init_size || (init_size & (init_size - 1)))
 		return NULL;
 	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
-	init_size = max(init_size, min_alloc_size);
+	init_size = max(init_size, MIN_TABLE_SIZE);
 	ht = calloc(1, sizeof(struct cds_lfht));
 	assert(ht);
 	ht->flags = flags;
@@ -1706,7 +1707,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
 {
 	unsigned long old_order, new_order;
 
-	new_size = max(new_size, ht->min_alloc_size);
+	new_size = max(new_size, MIN_TABLE_SIZE);
 	old_order = get_count_order_ulong(old_size);
 	new_order = get_count_order_ulong(new_size);
 	dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
@@ -1754,7 +1755,7 @@ static
 void resize_target_update_count(struct cds_lfht *ht,
 				unsigned long count)
 {
-	count = max(count, ht->min_alloc_size);
+	count = max(count, MIN_TABLE_SIZE);
 	uatomic_set(&ht->t.resize_target, count);
 }
 
@@ -1829,7 +1830,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 {
 	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
 		return;
-	count = max(count, ht->min_alloc_size);
+	count = max(count, MIN_TABLE_SIZE);
 	if (count == size)
 		return;		/* Already the right size, no resize needed */
 	if (count > size) {	/* lazy grow */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 509767c..b9e3e81 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -896,7 +896,7 @@ int main(int argc, char **argv)
 		return -1;
 	}
 
-	if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
+	if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
 		printf("Error: Min hash alloc size %lu is not a power of 2.\n",
 			min_hash_alloc_size);
 		return -1;
-- 
1.7.4.4

[ltt-dev] [PATCH 03/10 round10] ht->t.size is no required larger than ht->min_table_size now

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Thanks to the wrappers of bucket table alloc/free.

Sorry, I don't understand this change, and I don't see how the patch
below matches the patch title. This patch does not touch ht->t.size at
all, and seems to use MIN_TABLE_SIZE to replace ht->min_table_size, but
does not explain why this is possible.

More below,

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |   19 ++++++++++---------
>  tests/test_urcu_hash.c |    2 +-
>  2 files changed, 11 insertions(+), 10 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index c7f993f..a72e1a5 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -186,7 +186,8 @@
>  /*
>   * Define the minimum table size.
>   */
> -#define MIN_TABLE_SIZE			1
> +#define MIN_TABLE_ORDER			0
> +#define MIN_TABLE_SIZE			(1UL << MIN_TABLE_ORDER)
>  
>  #if (CAA_BITS_PER_LONG == 32)
>  #define MAX_TABLE_ORDER			32
> @@ -1141,7 +1142,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
>  {
>  	unsigned long j, size = 1UL << (i - 1);
>  
> -	assert(i > ht->min_alloc_order);
> +	assert(i > MIN_TABLE_ORDER);

Here, all this does is change the min_alloc_order

>  	ht->cds_lfht_rcu_read_lock();
>  	for (j = start + size; j < size + start + len; j++) {
>  		struct cds_lfht_node *new_node = bucket_at(ht, j);
> @@ -1177,7 +1178,7 @@ void init_table(struct cds_lfht *ht,
>  
>  	dbg_printf("init table: first_order %lu last_order %lu\n",
>  		   first_order, last_order);
> -	assert(first_order > ht->min_alloc_order);
> +	assert(first_order > MIN_TABLE_ORDER);
>  	for (i = first_order; i <= last_order; i++) {
>  		unsigned long len;
>  
> @@ -1239,7 +1240,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
>  {
>  	unsigned long j, size = 1UL << (i - 1);
>  
> -	assert(i > ht->min_alloc_order);
> +	assert(i > MIN_TABLE_ORDER);
>  	ht->cds_lfht_rcu_read_lock();
>  	for (j = size + start; j < size + start + len; j++) {
>  		struct cds_lfht_node *fini_node = bucket_at(ht, j);
> @@ -1276,7 +1277,7 @@ void fini_table(struct cds_lfht *ht,
>  
>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
>  		   first_order, last_order);
> -	assert(first_order > ht->min_alloc_order);
> +	assert(first_order > MIN_TABLE_ORDER);
>  	for (i = last_order; i >= first_order; i--) {
>  		unsigned long len;
>  
> @@ -1376,7 +1377,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	if (!init_size || (init_size & (init_size - 1)))
>  		return NULL;
>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
> -	init_size = max(init_size, min_alloc_size);
> +	init_size = max(init_size, MIN_TABLE_SIZE);
>  	ht = calloc(1, sizeof(struct cds_lfht));
>  	assert(ht);
>  	ht->flags = flags;
> @@ -1706,7 +1707,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
>  {
>  	unsigned long old_order, new_order;
>  
> -	new_size = max(new_size, ht->min_alloc_size);
> +	new_size = max(new_size, MIN_TABLE_SIZE);
>  	old_order = get_count_order_ulong(old_size);
>  	new_order = get_count_order_ulong(new_size);
>  	dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
> @@ -1754,7 +1755,7 @@ static
>  void resize_target_update_count(struct cds_lfht *ht,
>  				unsigned long count)
>  {
> -	count = max(count, ht->min_alloc_size);
> +	count = max(count, MIN_TABLE_SIZE);
>  	uatomic_set(&ht->t.resize_target, count);
>  }
>  
> @@ -1829,7 +1830,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>  {
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
> -	count = max(count, ht->min_alloc_size);
> +	count = max(count, MIN_TABLE_SIZE);
>  	if (count == size)
>  		return;		/* Already the right size, no resize needed */
>  	if (count > size) {	/* lazy grow */
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 509767c..b9e3e81 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -896,7 +896,7 @@ int main(int argc, char **argv)
>  		return -1;
>  	}
>  
> -	if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
> +	if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {

This seems to fix a bug in the test program, but it's not documented.
Maybe this should go in as a separate patch ?

Thanks,

Mathieu

>  		printf("Error: Min hash alloc size %lu is not a power of 2.\n",
>  			min_hash_alloc_size);
>  		return -1;
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 03/10 round10] ht->t.size is no required larger than ht->min_table_size now

[Lai Jiangshan]

On 11/22/2011 06:06 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Thanks to the wrappers of bucket table alloc/free.
> 
> Sorry, I don't understand this change, and I don't see how the patch
> below matches the patch title. This patch does not touch ht->t.size at
> all, and seems to use MIN_TABLE_SIZE to replace ht->min_table_size, but
> does not explain why this is possible.
> 

Original code always ensure ht->t.size >= ht->min_table_size.
It is not good, ht->min_table_size should be used for allocation,
not for the bucket size in used.

Thanks,
Lai

Add:
Original code don't do special alloc/free when ht->t.size < ht->min_table_size
in init_table()/fini_table(), so we have to force ht->t.size >= ht->min_table_size.

New code use the wrappers, they handle the special cases.



> More below,
> 
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c            |   19 ++++++++++---------
>>  tests/test_urcu_hash.c |    2 +-
>>  2 files changed, 11 insertions(+), 10 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index c7f993f..a72e1a5 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -186,7 +186,8 @@
>>  /*
>>   * Define the minimum table size.
>>   */
>> -#define MIN_TABLE_SIZE			1
>> +#define MIN_TABLE_ORDER			0
>> +#define MIN_TABLE_SIZE			(1UL << MIN_TABLE_ORDER)
>>  
>>  #if (CAA_BITS_PER_LONG == 32)
>>  #define MAX_TABLE_ORDER			32
>> @@ -1141,7 +1142,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
>>  {
>>  	unsigned long j, size = 1UL << (i - 1);
>>  
>> -	assert(i > ht->min_alloc_order);
>> +	assert(i > MIN_TABLE_ORDER);
> 
> Here, all this does is change the min_alloc_order
> 
>>  	ht->cds_lfht_rcu_read_lock();
>>  	for (j = start + size; j < size + start + len; j++) {
>>  		struct cds_lfht_node *new_node = bucket_at(ht, j);
>> @@ -1177,7 +1178,7 @@ void init_table(struct cds_lfht *ht,
>>  
>>  	dbg_printf("init table: first_order %lu last_order %lu\n",
>>  		   first_order, last_order);
>> -	assert(first_order > ht->min_alloc_order);
>> +	assert(first_order > MIN_TABLE_ORDER);
>>  	for (i = first_order; i <= last_order; i++) {
>>  		unsigned long len;
>>  
>> @@ -1239,7 +1240,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
>>  {
>>  	unsigned long j, size = 1UL << (i - 1);
>>  
>> -	assert(i > ht->min_alloc_order);
>> +	assert(i > MIN_TABLE_ORDER);
>>  	ht->cds_lfht_rcu_read_lock();
>>  	for (j = size + start; j < size + start + len; j++) {
>>  		struct cds_lfht_node *fini_node = bucket_at(ht, j);
>> @@ -1276,7 +1277,7 @@ void fini_table(struct cds_lfht *ht,
>>  
>>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
>>  		   first_order, last_order);
>> -	assert(first_order > ht->min_alloc_order);
>> +	assert(first_order > MIN_TABLE_ORDER);
>>  	for (i = last_order; i >= first_order; i--) {
>>  		unsigned long len;
>>  
>> @@ -1376,7 +1377,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  	if (!init_size || (init_size & (init_size - 1)))
>>  		return NULL;
>>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
>> -	init_size = max(init_size, min_alloc_size);
>> +	init_size = max(init_size, MIN_TABLE_SIZE);
>>  	ht = calloc(1, sizeof(struct cds_lfht));
>>  	assert(ht);
>>  	ht->flags = flags;
>> @@ -1706,7 +1707,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
>>  {
>>  	unsigned long old_order, new_order;
>>  
>> -	new_size = max(new_size, ht->min_alloc_size);
>> +	new_size = max(new_size, MIN_TABLE_SIZE);
>>  	old_order = get_count_order_ulong(old_size);
>>  	new_order = get_count_order_ulong(new_size);
>>  	dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
>> @@ -1754,7 +1755,7 @@ static
>>  void resize_target_update_count(struct cds_lfht *ht,
>>  				unsigned long count)
>>  {
>> -	count = max(count, ht->min_alloc_size);
>> +	count = max(count, MIN_TABLE_SIZE);
>>  	uatomic_set(&ht->t.resize_target, count);
>>  }
>>  
>> @@ -1829,7 +1830,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>>  {
>>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>>  		return;
>> -	count = max(count, ht->min_alloc_size);
>> +	count = max(count, MIN_TABLE_SIZE);
>>  	if (count == size)
>>  		return;		/* Already the right size, no resize needed */
>>  	if (count > size) {	/* lazy grow */
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index 509767c..b9e3e81 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -896,7 +896,7 @@ int main(int argc, char **argv)
>>  		return -1;
>>  	}
>>  
>> -	if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
>> +	if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
> 
> This seems to fix a bug in the test program, but it's not documented.
> Maybe this should go in as a separate patch ?
> 
> Thanks,
> 
> Mathieu
> 
>>  		printf("Error: Min hash alloc size %lu is not a power of 2.\n",
>>  			min_hash_alloc_size);
>>  		return -1;
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 03/10 round10] ht->t.size is no required larger than ht->min_table_size now

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/22/2011 06:06 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> Thanks to the wrappers of bucket table alloc/free.
> > 
> > Sorry, I don't understand this change, and I don't see how the patch
> > below matches the patch title. This patch does not touch ht->t.size at
> > all, and seems to use MIN_TABLE_SIZE to replace ht->min_table_size, but
> > does not explain why this is possible.
> > 
> 
> Original code always ensure ht->t.size >= ht->min_table_size.
> It is not good, ht->min_table_size should be used for allocation,
> not for the bucket size in used.
> 
> Thanks,
> Lai
> 
> Add:
> Original code don't do special alloc/free when ht->t.size < ht->min_table_size
> in init_table()/fini_table(), so we have to force ht->t.size >= ht->min_table_size.
> 
> New code use the wrappers, they handle the special cases.

OK. So I think this clearer description of what the patch does is
required for the next round.

Thanks!

Mathieu

> 
> 
> 
> > More below,
> > 
> >>
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >>  rculfhash.c            |   19 ++++++++++---------
> >>  tests/test_urcu_hash.c |    2 +-
> >>  2 files changed, 11 insertions(+), 10 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index c7f993f..a72e1a5 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -186,7 +186,8 @@
> >>  /*
> >>   * Define the minimum table size.
> >>   */
> >> -#define MIN_TABLE_SIZE			1
> >> +#define MIN_TABLE_ORDER			0
> >> +#define MIN_TABLE_SIZE			(1UL << MIN_TABLE_ORDER)
> >>  
> >>  #if (CAA_BITS_PER_LONG == 32)
> >>  #define MAX_TABLE_ORDER			32
> >> @@ -1141,7 +1142,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> >>  {
> >>  	unsigned long j, size = 1UL << (i - 1);
> >>  
> >> -	assert(i > ht->min_alloc_order);
> >> +	assert(i > MIN_TABLE_ORDER);
> > 
> > Here, all this does is change the min_alloc_order
> > 
> >>  	ht->cds_lfht_rcu_read_lock();
> >>  	for (j = start + size; j < size + start + len; j++) {
> >>  		struct cds_lfht_node *new_node = bucket_at(ht, j);
> >> @@ -1177,7 +1178,7 @@ void init_table(struct cds_lfht *ht,
> >>  
> >>  	dbg_printf("init table: first_order %lu last_order %lu\n",
> >>  		   first_order, last_order);
> >> -	assert(first_order > ht->min_alloc_order);
> >> +	assert(first_order > MIN_TABLE_ORDER);
> >>  	for (i = first_order; i <= last_order; i++) {
> >>  		unsigned long len;
> >>  
> >> @@ -1239,7 +1240,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
> >>  {
> >>  	unsigned long j, size = 1UL << (i - 1);
> >>  
> >> -	assert(i > ht->min_alloc_order);
> >> +	assert(i > MIN_TABLE_ORDER);
> >>  	ht->cds_lfht_rcu_read_lock();
> >>  	for (j = size + start; j < size + start + len; j++) {
> >>  		struct cds_lfht_node *fini_node = bucket_at(ht, j);
> >> @@ -1276,7 +1277,7 @@ void fini_table(struct cds_lfht *ht,
> >>  
> >>  	dbg_printf("fini table: first_order %lu last_order %lu\n",
> >>  		   first_order, last_order);
> >> -	assert(first_order > ht->min_alloc_order);
> >> +	assert(first_order > MIN_TABLE_ORDER);
> >>  	for (i = last_order; i >= first_order; i--) {
> >>  		unsigned long len;
> >>  
> >> @@ -1376,7 +1377,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  	if (!init_size || (init_size & (init_size - 1)))
> >>  		return NULL;
> >>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
> >> -	init_size = max(init_size, min_alloc_size);
> >> +	init_size = max(init_size, MIN_TABLE_SIZE);
> >>  	ht = calloc(1, sizeof(struct cds_lfht));
> >>  	assert(ht);
> >>  	ht->flags = flags;
> >> @@ -1706,7 +1707,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
> >>  {
> >>  	unsigned long old_order, new_order;
> >>  
> >> -	new_size = max(new_size, ht->min_alloc_size);
> >> +	new_size = max(new_size, MIN_TABLE_SIZE);
> >>  	old_order = get_count_order_ulong(old_size);
> >>  	new_order = get_count_order_ulong(new_size);
> >>  	dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
> >> @@ -1754,7 +1755,7 @@ static
> >>  void resize_target_update_count(struct cds_lfht *ht,
> >>  				unsigned long count)
> >>  {
> >> -	count = max(count, ht->min_alloc_size);
> >> +	count = max(count, MIN_TABLE_SIZE);
> >>  	uatomic_set(&ht->t.resize_target, count);
> >>  }
> >>  
> >> @@ -1829,7 +1830,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
> >>  {
> >>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
> >>  		return;
> >> -	count = max(count, ht->min_alloc_size);
> >> +	count = max(count, MIN_TABLE_SIZE);
> >>  	if (count == size)
> >>  		return;		/* Already the right size, no resize needed */
> >>  	if (count > size) {	/* lazy grow */
> >> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> >> index 509767c..b9e3e81 100644
> >> --- a/tests/test_urcu_hash.c
> >> +++ b/tests/test_urcu_hash.c
> >> @@ -896,7 +896,7 @@ int main(int argc, char **argv)
> >>  		return -1;
> >>  	}
> >>  
> >> -	if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
> >> +	if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
> > 
> > This seems to fix a bug in the test program, but it's not documented.
> > Maybe this should go in as a separate patch ?
> > 
> > Thanks,
> > 
> > Mathieu
> > 
> >>  		printf("Error: Min hash alloc size %lu is not a power of 2.\n",
> >>  			min_hash_alloc_size);
> >>  		return -1;
> >> -- 
> >> 1.7.4.4
> >>
> > 
> 
> 
> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
> 

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

[ltt-dev] [PATCH 04/10 round10] remove struct rcu_level

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |   28 ++++++++++++----------------
 1 files changed, 12 insertions(+), 16 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index a72e1a5..2df133c 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -238,27 +238,23 @@ struct ht_items_count {
 } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
 
 /*
- * rcu_level: Contains the per order-index-level bucket node table. The
- * size of each bucket node table is half the number of hashes contained
- * in this order (except for order 0). The minimum allocation size
- * parameter allows combining the bucket node arrays of the lowermost
- * levels to improve cache locality for small index orders.
- */
-struct rcu_level {
-	/* Note: manually update allocation length when adding a field */
-	struct cds_lfht_node nodes[0];
-};
-
-/*
  * rcu_table: Contains the size and desired new size if a resize
  * operation is in progress, as well as the statically-sized array of
- * rcu_level pointers.
+ * bucket table pointers.
  */
 struct rcu_table {
 	unsigned long size;	/* always a power of 2, shared (RCU) */
 	unsigned long resize_target;
 	int resize_initiated;
-	struct rcu_level *tbl[MAX_TABLE_ORDER];
+
+	/*
+	 * Contains the per order-index-level bucket node table. The size
+	 * of each bucket node table is half the number of hashes contained
+	 * in this order (except for order 0). The minimum allocation size
+	 * parameter allows combining the bucket node arrays of the lowermost
+	 * levels to improve cache locality for small index orders.
+	 */
+	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
 };
 
 /*
@@ -794,7 +790,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long 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];
+		return &ht->t.tbl[0][index];
 	}
 	/*
 	 * equivalent to get_count_order_ulong(index + 1), but optimizes
@@ -804,7 +800,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 	order = fls_ulong(index);
 	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)];
+	return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
 }
 
 static inline
-- 
1.7.4.4

[ltt-dev] [PATCH 04/10 round10] remove struct rcu_level

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

This change looks fine. Please resubmit along with the other patches, as
they need to be applied before.

Acked-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

> ---
>  rculfhash.c |   28 ++++++++++++----------------
>  1 files changed, 12 insertions(+), 16 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index a72e1a5..2df133c 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -238,27 +238,23 @@ struct ht_items_count {
>  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>  
>  /*
> - * rcu_level: Contains the per order-index-level bucket node table. The
> - * size of each bucket node table is half the number of hashes contained
> - * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the bucket node arrays of the lowermost
> - * levels to improve cache locality for small index orders.
> - */
> -struct rcu_level {
> -	/* Note: manually update allocation length when adding a field */
> -	struct cds_lfht_node nodes[0];
> -};
> -
> -/*
>   * rcu_table: Contains the size and desired new size if a resize
>   * operation is in progress, as well as the statically-sized array of
> - * rcu_level pointers.
> + * bucket table pointers.
>   */
>  struct rcu_table {
>  	unsigned long size;	/* always a power of 2, shared (RCU) */
>  	unsigned long resize_target;
>  	int resize_initiated;
> -	struct rcu_level *tbl[MAX_TABLE_ORDER];
> +
> +	/*
> +	 * Contains the per order-index-level bucket node table. The size
> +	 * of each bucket node table is half the number of hashes contained
> +	 * in this order (except for order 0). The minimum allocation size
> +	 * parameter allows combining the bucket node arrays of the lowermost
> +	 * levels to improve cache locality for small index orders.
> +	 */
> +	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
>  };
>  
>  /*
> @@ -794,7 +790,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long 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];
> +		return &ht->t.tbl[0][index];
>  	}
>  	/*
>  	 * equivalent to get_count_order_ulong(index + 1), but optimizes
> @@ -804,7 +800,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>  	order = fls_ulong(index);
>  	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)];
> +	return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
>  }
>  
>  static inline
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 05/10 round10] add max_size arguemnt

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |   17 +++++++++++++++++
 tests/test_urcu_hash.c |    2 +-
 urcu/rculfhash.h       |    9 ++++++---
 3 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 2df133c..b7be893 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -266,6 +266,7 @@ struct cds_lfht {
 	struct rcu_table t;
 	unsigned long min_alloc_order;
 	unsigned long min_alloc_size;
+	unsigned long max_size;
 	int flags;
 	/*
 	 * We need to put the work threads offline (QSBR) when taking this
@@ -1351,6 +1352,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
 
 struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
+			unsigned long max_size,
 			int flags,
 			void (*cds_lfht_call_rcu)(struct rcu_head *head,
 					void (*func)(struct rcu_head *head)),
@@ -1369,11 +1371,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	/* min_alloc_size must be power of two */
 	if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
 		return NULL;
+
 	/* init_size must be power of two */
 	if (!init_size || (init_size & (init_size - 1)))
 		return NULL;
+
+	if (!max_size)
+		max_size = 1UL << (MAX_TABLE_ORDER - 1);
+
+	/* max_size must be power of two */
+	if (!max_size || (max_size & (max_size - 1)))
+		return NULL;
+
 	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
 	init_size = max(init_size, MIN_TABLE_SIZE);
+	max_size = max(max_size, min_alloc_size);
+	init_size = min(init_size, max_size);
 	ht = calloc(1, sizeof(struct cds_lfht));
 	assert(ht);
 	ht->flags = flags;
@@ -1393,6 +1406,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	ht->t.resize_target = 1UL << order;
 	ht->min_alloc_size = min_alloc_size;
 	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+	ht->max_size = max_size;
 	cds_lfht_create_bucket(ht, 1UL << order);
 	ht->t.size = 1UL << order;
 	return ht;
@@ -1752,6 +1766,7 @@ void resize_target_update_count(struct cds_lfht *ht,
 				unsigned long count)
 {
 	count = max(count, MIN_TABLE_SIZE);
+	count = min(count, ht->max_size);
 	uatomic_set(&ht->t.resize_target, count);
 }
 
@@ -1809,6 +1824,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
 {
 	unsigned long target_size = size << growth;
 
+	target_size = min(target_size, ht->max_size);
 	if (resize_target_grow(ht, target_size) >= target_size)
 		return;
 
@@ -1827,6 +1843,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
 		return;
 	count = max(count, MIN_TABLE_SIZE);
+	count = min(count, ht->max_size);
 	if (count == size)
 		return;		/* Already the right size, no resize needed */
 	if (count > size) {	/* lazy grow */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index b9e3e81..2961177 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -967,7 +967,7 @@ int main(int argc, char **argv)
 	 * thread from the point of view of resize.
 	 */
 	rcu_register_thread();
-	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
+	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
 			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
 			CDS_LFHT_ACCOUNTING, NULL);
       	ret = populate_hash();
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index c13d3df..2eefd2c 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -98,6 +98,7 @@ enum {
  */
 struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
+			unsigned long max_size,
 			int flags,
 			void (*cds_lfht_call_rcu)(struct rcu_head *head,
 				void (*func)(struct rcu_head *head)),
@@ -112,8 +113,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 
 /*
  * cds_lfht_new - allocate a hash table.
- * @init_size: number of nodes to allocate initially. Must be power of two.
- * @min_alloc_size: the smallest allocation size to use. Must be power of two.
+ * @init_size: number of buckets to allocate initially. Must be power of two.
+ * @min_alloc_size: the smallest allocation buckets size to use. Must be power of two.
+ * @max_size: the max size of buckets for future growing. Must be power of two.
  * @flags: hash table creation flags (can be combined with bitwise or: '|').
  *           0: no flags.
  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
@@ -134,10 +136,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 static inline
 struct cds_lfht *cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
+			unsigned long max_size,
 			int flags,
 			pthread_attr_t *attr)
 {
-	return _cds_lfht_new(init_size, min_alloc_size, flags,
+	return _cds_lfht_new(init_size, min_alloc_size, max_size, flags,
 			call_rcu, synchronize_rcu, rcu_read_lock,
 			rcu_read_unlock, rcu_thread_offline,
 			rcu_thread_online, rcu_register_thread,
-- 
1.7.4.4

[ltt-dev] [PATCH 05/10 round10] add max_size arguemnt

[Mathieu Desnoyers]

arguemnt -> argument

I think we need to discuss the semantic of max_size: here, you propose
that max_size is just the number of buckets, but it does not limit the
ability of the table to contain more elements than max_size.

IMHO, it would be nice to have max_size limit the number of elements
that the table can accept, e.g. ensuring that insertion fails if the
number of elements gets over the max_size threshold. It might not need
to be an exact thing though, just giving an approximated upper limit
might be fine (using the split-counters), as long as it is documented.

Thanks,

Mathieu

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |   17 +++++++++++++++++
>  tests/test_urcu_hash.c |    2 +-
>  urcu/rculfhash.h       |    9 ++++++---
>  3 files changed, 24 insertions(+), 4 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 2df133c..b7be893 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -266,6 +266,7 @@ struct cds_lfht {
>  	struct rcu_table t;
>  	unsigned long min_alloc_order;
>  	unsigned long min_alloc_size;
> +	unsigned long max_size;
>  	int flags;
>  	/*
>  	 * We need to put the work threads offline (QSBR) when taking this
> @@ -1351,6 +1352,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>  
>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  			unsigned long min_alloc_size,
> +			unsigned long max_size,
>  			int flags,
>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
>  					void (*func)(struct rcu_head *head)),
> @@ -1369,11 +1371,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	/* min_alloc_size must be power of two */
>  	if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
>  		return NULL;
> +
>  	/* init_size must be power of two */
>  	if (!init_size || (init_size & (init_size - 1)))
>  		return NULL;
> +
> +	if (!max_size)
> +		max_size = 1UL << (MAX_TABLE_ORDER - 1);
> +
> +	/* max_size must be power of two */
> +	if (!max_size || (max_size & (max_size - 1)))
> +		return NULL;
> +
>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
>  	init_size = max(init_size, MIN_TABLE_SIZE);
> +	max_size = max(max_size, min_alloc_size);
> +	init_size = min(init_size, max_size);
>  	ht = calloc(1, sizeof(struct cds_lfht));
>  	assert(ht);
>  	ht->flags = flags;
> @@ -1393,6 +1406,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	ht->t.resize_target = 1UL << order;
>  	ht->min_alloc_size = min_alloc_size;
>  	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> +	ht->max_size = max_size;
>  	cds_lfht_create_bucket(ht, 1UL << order);
>  	ht->t.size = 1UL << order;
>  	return ht;
> @@ -1752,6 +1766,7 @@ void resize_target_update_count(struct cds_lfht *ht,
>  				unsigned long count)
>  {
>  	count = max(count, MIN_TABLE_SIZE);
> +	count = min(count, ht->max_size);
>  	uatomic_set(&ht->t.resize_target, count);
>  }
>  
> @@ -1809,6 +1824,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
>  {
>  	unsigned long target_size = size << growth;
>  
> +	target_size = min(target_size, ht->max_size);
>  	if (resize_target_grow(ht, target_size) >= target_size)
>  		return;
>  
> @@ -1827,6 +1843,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>  		return;
>  	count = max(count, MIN_TABLE_SIZE);
> +	count = min(count, ht->max_size);
>  	if (count == size)
>  		return;		/* Already the right size, no resize needed */
>  	if (count > size) {	/* lazy grow */
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index b9e3e81..2961177 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -967,7 +967,7 @@ int main(int argc, char **argv)
>  	 * thread from the point of view of resize.
>  	 */
>  	rcu_register_thread();
> -	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
> +	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>  			CDS_LFHT_ACCOUNTING, NULL);
>        	ret = populate_hash();
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index c13d3df..2eefd2c 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -98,6 +98,7 @@ enum {
>   */
>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  			unsigned long min_alloc_size,
> +			unsigned long max_size,
>  			int flags,
>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
>  				void (*func)(struct rcu_head *head)),
> @@ -112,8 +113,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  
>  /*
>   * cds_lfht_new - allocate a hash table.
> - * @init_size: number of nodes to allocate initially. Must be power of two.
> - * @min_alloc_size: the smallest allocation size to use. Must be power of two.
> + * @init_size: number of buckets to allocate initially. Must be power of two.
> + * @min_alloc_size: the smallest allocation buckets size to use. Must be power of two.
> + * @max_size: the max size of buckets for future growing. Must be power of two.
>   * @flags: hash table creation flags (can be combined with bitwise or: '|').
>   *           0: no flags.
>   *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
> @@ -134,10 +136,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  static inline
>  struct cds_lfht *cds_lfht_new(unsigned long init_size,
>  			unsigned long min_alloc_size,
> +			unsigned long max_size,
>  			int flags,
>  			pthread_attr_t *attr)
>  {
> -	return _cds_lfht_new(init_size, min_alloc_size, flags,
> +	return _cds_lfht_new(init_size, min_alloc_size, max_size, flags,
>  			call_rcu, synchronize_rcu, rcu_read_lock,
>  			rcu_read_unlock, rcu_thread_offline,
>  			rcu_thread_online, rcu_register_thread,
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 05/10 round10] add max_size arguemnt

[Lai Jiangshan]

On 11/22/2011 06:11 PM, Mathieu Desnoyers wrote:
> arguemnt -> argument
> 
> I think we need to discuss the semantic of max_size: here, you propose
> that max_size is just the number of buckets, but it does not limit the
> ability of the table to contain more elements than max_size.
> 
> IMHO, it would be nice to have max_size limit the number of elements
> that the table can accept, e.g. ensuring that insertion fails if the
> number of elements gets over the max_size threshold. It might not need
> to be an exact thing though, just giving an approximated upper limit
> might be fine (using the split-counters), as long as it is documented.

documented: "max_size: the max size of buckets for future growing"

Is max_bucket_size better?
and min_alloc_size need to be changed to min_alloc_bucket_size?

I'm not planing to add "max_size" for the number of elements in this
round or near future.

Thanks,
Lai

> 
> Thanks,
> 
> Mathieu
> 
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c            |   17 +++++++++++++++++
>>  tests/test_urcu_hash.c |    2 +-
>>  urcu/rculfhash.h       |    9 ++++++---
>>  3 files changed, 24 insertions(+), 4 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index 2df133c..b7be893 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -266,6 +266,7 @@ struct cds_lfht {
>>  	struct rcu_table t;
>>  	unsigned long min_alloc_order;
>>  	unsigned long min_alloc_size;
>> +	unsigned long max_size;
>>  	int flags;
>>  	/*
>>  	 * We need to put the work threads offline (QSBR) when taking this
>> @@ -1351,6 +1352,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>>  
>>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  			unsigned long min_alloc_size,
>> +			unsigned long max_size,
>>  			int flags,
>>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
>>  					void (*func)(struct rcu_head *head)),
>> @@ -1369,11 +1371,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  	/* min_alloc_size must be power of two */
>>  	if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
>>  		return NULL;
>> +
>>  	/* init_size must be power of two */
>>  	if (!init_size || (init_size & (init_size - 1)))
>>  		return NULL;
>> +
>> +	if (!max_size)
>> +		max_size = 1UL << (MAX_TABLE_ORDER - 1);
>> +
>> +	/* max_size must be power of two */
>> +	if (!max_size || (max_size & (max_size - 1)))
>> +		return NULL;
>> +
>>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
>>  	init_size = max(init_size, MIN_TABLE_SIZE);
>> +	max_size = max(max_size, min_alloc_size);
>> +	init_size = min(init_size, max_size);
>>  	ht = calloc(1, sizeof(struct cds_lfht));
>>  	assert(ht);
>>  	ht->flags = flags;
>> @@ -1393,6 +1406,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  	ht->t.resize_target = 1UL << order;
>>  	ht->min_alloc_size = min_alloc_size;
>>  	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
>> +	ht->max_size = max_size;
>>  	cds_lfht_create_bucket(ht, 1UL << order);
>>  	ht->t.size = 1UL << order;
>>  	return ht;
>> @@ -1752,6 +1766,7 @@ void resize_target_update_count(struct cds_lfht *ht,
>>  				unsigned long count)
>>  {
>>  	count = max(count, MIN_TABLE_SIZE);
>> +	count = min(count, ht->max_size);
>>  	uatomic_set(&ht->t.resize_target, count);
>>  }
>>  
>> @@ -1809,6 +1824,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
>>  {
>>  	unsigned long target_size = size << growth;
>>  
>> +	target_size = min(target_size, ht->max_size);
>>  	if (resize_target_grow(ht, target_size) >= target_size)
>>  		return;
>>  
>> @@ -1827,6 +1843,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
>>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
>>  		return;
>>  	count = max(count, MIN_TABLE_SIZE);
>> +	count = min(count, ht->max_size);
>>  	if (count == size)
>>  		return;		/* Already the right size, no resize needed */
>>  	if (count > size) {	/* lazy grow */
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index b9e3e81..2961177 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -967,7 +967,7 @@ int main(int argc, char **argv)
>>  	 * thread from the point of view of resize.
>>  	 */
>>  	rcu_register_thread();
>> -	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
>> +	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
>>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>>  			CDS_LFHT_ACCOUNTING, NULL);
>>        	ret = populate_hash();
>> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
>> index c13d3df..2eefd2c 100644
>> --- a/urcu/rculfhash.h
>> +++ b/urcu/rculfhash.h
>> @@ -98,6 +98,7 @@ enum {
>>   */
>>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  			unsigned long min_alloc_size,
>> +			unsigned long max_size,
>>  			int flags,
>>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
>>  				void (*func)(struct rcu_head *head)),
>> @@ -112,8 +113,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  
>>  /*
>>   * cds_lfht_new - allocate a hash table.
>> - * @init_size: number of nodes to allocate initially. Must be power of two.
>> - * @min_alloc_size: the smallest allocation size to use. Must be power of two.
>> + * @init_size: number of buckets to allocate initially. Must be power of two.
>> + * @min_alloc_size: the smallest allocation buckets size to use. Must be power of two.
>> + * @max_size: the max size of buckets for future growing. Must be power of two.
>>   * @flags: hash table creation flags (can be combined with bitwise or: '|').
>>   *           0: no flags.
>>   *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
>> @@ -134,10 +136,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  static inline
>>  struct cds_lfht *cds_lfht_new(unsigned long init_size,
>>  			unsigned long min_alloc_size,
>> +			unsigned long max_size,
>>  			int flags,
>>  			pthread_attr_t *attr)
>>  {
>> -	return _cds_lfht_new(init_size, min_alloc_size, flags,
>> +	return _cds_lfht_new(init_size, min_alloc_size, max_size, flags,
>>  			call_rcu, synchronize_rcu, rcu_read_lock,
>>  			rcu_read_unlock, rcu_thread_offline,
>>  			rcu_thread_online, rcu_register_thread,
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 05/10 round10] add max_size arguemnt

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/22/2011 06:11 PM, Mathieu Desnoyers wrote:
> > arguemnt -> argument
> > 
> > I think we need to discuss the semantic of max_size: here, you propose
> > that max_size is just the number of buckets, but it does not limit the
> > ability of the table to contain more elements than max_size.
> > 
> > IMHO, it would be nice to have max_size limit the number of elements
> > that the table can accept, e.g. ensuring that insertion fails if the
> > number of elements gets over the max_size threshold. It might not need
> > to be an exact thing though, just giving an approximated upper limit
> > might be fine (using the split-counters), as long as it is documented.
> 
> documented: "max_size: the max size of buckets for future growing"
> 
> Is max_bucket_size better?
> and min_alloc_size need to be changed to min_alloc_bucket_size?
> 
> I'm not planing to add "max_size" for the number of elements in this
> round or near future.

maybe max_nr_buckets then ?

nr_ seems to be more descriptive than "size" in this context, because
"size" could lead to some confusion, leading to think that we would be
specifying the size of a bucket rather than actually specifying the
number of buckets. Seems reasonable ?

Thanks,

Mathieu

> 
> Thanks,
> Lai
> 
> > 
> > Thanks,
> > 
> > Mathieu
> > 
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >>  rculfhash.c            |   17 +++++++++++++++++
> >>  tests/test_urcu_hash.c |    2 +-
> >>  urcu/rculfhash.h       |    9 ++++++---
> >>  3 files changed, 24 insertions(+), 4 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index 2df133c..b7be893 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -266,6 +266,7 @@ struct cds_lfht {
> >>  	struct rcu_table t;
> >>  	unsigned long min_alloc_order;
> >>  	unsigned long min_alloc_size;
> >> +	unsigned long max_size;
> >>  	int flags;
> >>  	/*
> >>  	 * We need to put the work threads offline (QSBR) when taking this
> >> @@ -1351,6 +1352,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
> >>  
> >>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  			unsigned long min_alloc_size,
> >> +			unsigned long max_size,
> >>  			int flags,
> >>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
> >>  					void (*func)(struct rcu_head *head)),
> >> @@ -1369,11 +1371,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  	/* min_alloc_size must be power of two */
> >>  	if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
> >>  		return NULL;
> >> +
> >>  	/* init_size must be power of two */
> >>  	if (!init_size || (init_size & (init_size - 1)))
> >>  		return NULL;
> >> +
> >> +	if (!max_size)
> >> +		max_size = 1UL << (MAX_TABLE_ORDER - 1);
> >> +
> >> +	/* max_size must be power of two */
> >> +	if (!max_size || (max_size & (max_size - 1)))
> >> +		return NULL;
> >> +
> >>  	min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
> >>  	init_size = max(init_size, MIN_TABLE_SIZE);
> >> +	max_size = max(max_size, min_alloc_size);
> >> +	init_size = min(init_size, max_size);
> >>  	ht = calloc(1, sizeof(struct cds_lfht));
> >>  	assert(ht);
> >>  	ht->flags = flags;
> >> @@ -1393,6 +1406,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  	ht->t.resize_target = 1UL << order;
> >>  	ht->min_alloc_size = min_alloc_size;
> >>  	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> >> +	ht->max_size = max_size;
> >>  	cds_lfht_create_bucket(ht, 1UL << order);
> >>  	ht->t.size = 1UL << order;
> >>  	return ht;
> >> @@ -1752,6 +1766,7 @@ void resize_target_update_count(struct cds_lfht *ht,
> >>  				unsigned long count)
> >>  {
> >>  	count = max(count, MIN_TABLE_SIZE);
> >> +	count = min(count, ht->max_size);
> >>  	uatomic_set(&ht->t.resize_target, count);
> >>  }
> >>  
> >> @@ -1809,6 +1824,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
> >>  {
> >>  	unsigned long target_size = size << growth;
> >>  
> >> +	target_size = min(target_size, ht->max_size);
> >>  	if (resize_target_grow(ht, target_size) >= target_size)
> >>  		return;
> >>  
> >> @@ -1827,6 +1843,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
> >>  	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
> >>  		return;
> >>  	count = max(count, MIN_TABLE_SIZE);
> >> +	count = min(count, ht->max_size);
> >>  	if (count == size)
> >>  		return;		/* Already the right size, no resize needed */
> >>  	if (count > size) {	/* lazy grow */
> >> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> >> index b9e3e81..2961177 100644
> >> --- a/tests/test_urcu_hash.c
> >> +++ b/tests/test_urcu_hash.c
> >> @@ -967,7 +967,7 @@ int main(int argc, char **argv)
> >>  	 * thread from the point of view of resize.
> >>  	 */
> >>  	rcu_register_thread();
> >> -	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
> >> +	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
> >>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
> >>  			CDS_LFHT_ACCOUNTING, NULL);
> >>        	ret = populate_hash();
> >> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> >> index c13d3df..2eefd2c 100644
> >> --- a/urcu/rculfhash.h
> >> +++ b/urcu/rculfhash.h
> >> @@ -98,6 +98,7 @@ enum {
> >>   */
> >>  struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  			unsigned long min_alloc_size,
> >> +			unsigned long max_size,
> >>  			int flags,
> >>  			void (*cds_lfht_call_rcu)(struct rcu_head *head,
> >>  				void (*func)(struct rcu_head *head)),
> >> @@ -112,8 +113,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  
> >>  /*
> >>   * cds_lfht_new - allocate a hash table.
> >> - * @init_size: number of nodes to allocate initially. Must be power of two.
> >> - * @min_alloc_size: the smallest allocation size to use. Must be power of two.
> >> + * @init_size: number of buckets to allocate initially. Must be power of two.
> >> + * @min_alloc_size: the smallest allocation buckets size to use. Must be power of two.
> >> + * @max_size: the max size of buckets for future growing. Must be power of two.
> >>   * @flags: hash table creation flags (can be combined with bitwise or: '|').
> >>   *           0: no flags.
> >>   *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
> >> @@ -134,10 +136,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> >>  static inline
> >>  struct cds_lfht *cds_lfht_new(unsigned long init_size,
> >>  			unsigned long min_alloc_size,
> >> +			unsigned long max_size,
> >>  			int flags,
> >>  			pthread_attr_t *attr)
> >>  {
> >> -	return _cds_lfht_new(init_size, min_alloc_size, flags,
> >> +	return _cds_lfht_new(init_size, min_alloc_size, max_size, flags,
> >>  			call_rcu, synchronize_rcu, rcu_read_lock,
> >>  			rcu_read_unlock, rcu_thread_offline,
> >>  			rcu_thread_online, rcu_register_thread,
> >> -- 
> >> 1.7.4.4
> >>
> > 
> 
> 
> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
> 

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

[ltt-dev] [PATCH 06/10 round10] add LFHT_MEMORY_CHUNK low level memory management

[Lai Jiangshan]

The old memory mangement is named as LFHT_MEMORY_ORDER.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |  116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 111 insertions(+), 5 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index b7be893..ae1177f 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -172,6 +172,10 @@
 #define dbg_printf(fmt, args...)
 #endif
 
+#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
+#define LFHT_MEMORY_ORDER
+#endif
+
 /*
  * Split-counters lazily update the global counter each 1024
  * addition/removal. It automatically keeps track of resize required.
@@ -195,6 +199,8 @@
 #define MAX_TABLE_ORDER			64
 #endif
 
+#define MAX_CHUNK_TABLE			(1UL << 10)
+
 /*
  * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
  */
@@ -247,6 +253,7 @@ struct rcu_table {
 	unsigned long resize_target;
 	int resize_initiated;
 
+#ifdef LFHT_MEMORY_ORDER
 	/*
 	 * Contains the per order-index-level bucket node table. The size
 	 * of each bucket node table is half the number of hashes contained
@@ -255,6 +262,7 @@ struct rcu_table {
 	 * levels to improve cache locality for small index orders.
 	 */
 	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
+#endif
 };
 
 /*
@@ -289,6 +297,16 @@ struct cds_lfht {
 	pthread_attr_t *resize_attr;	/* Resize threads attributes */
 	long count;			/* global approximate item count */
 	struct ht_items_count *split_count;	/* split item count */
+
+#ifdef LFHT_MEMORY_CHUNK
+	/*
+	 * Contains the bucket node chunks. The size of each bucket node
+	 * chunk is ->min_alloc_size(avoid to alloc chunks with different
+	 * size). chunks improve cache locality for small index orders
+	 * and improve lookup_bucket() for the archs without hardware fls().
+	 */
+	struct cds_lfht_node *tbl[0];
+#endif
 };
 
 /*
@@ -753,6 +771,93 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
 	return old2;
 }
 
+#ifdef LFHT_MEMORY_CHUNK
+static
+struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
+		unsigned long max_size)
+{
+	struct cds_lfht *ht;
+
+	min_alloc_size = max(min_alloc_size, max_size / MAX_CHUNK_TABLE);
+	ht = calloc(1, sizeof(struct cds_lfht) +
+			sizeof(ht->tbl[0]) * (max_size / min_alloc_size));
+	assert(ht);
+
+	ht->min_alloc_size = min_alloc_size;
+	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+	ht->max_size = max_size;
+
+	return ht;
+}
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		ht->tbl[0] = calloc(ht->min_alloc_size,
+			sizeof(struct cds_lfht_node));
+		assert(ht->tbl[0]);
+	} else if (order > ht->min_alloc_order) {
+		unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_order);
+
+		for (i = len; i < 2 * len; i++) {
+			ht->tbl[i] = calloc(ht->min_alloc_size,
+				sizeof(struct cds_lfht_node));
+			assert(ht->tbl[i]);
+		}
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0)
+		poison_free(ht->tbl[0]);
+	else if (order > ht->min_alloc_order) {
+		unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_order);
+
+		for (i = len; i < 2 * len; i++)
+			poison_free(ht->tbl[i]);
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+static inline
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+	unsigned long chunk, offset;
+
+	if (__builtin_constant_p(index) && index == 0)
+		return &ht->tbl[0][0];
+
+	chunk = index >> ht->min_alloc_order;
+	offset = index & (ht->min_alloc_size - 1);
+	return &ht->tbl[chunk][offset];
+}
+#else
+/* LFHT_MEMORY_ORDER */
+static
+struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
+		unsigned long max_size)
+{
+	struct cds_lfht *ht;
+
+	ht = calloc(1, sizeof(struct cds_lfht));
+	assert(ht);
+
+	ht->min_alloc_size = min_alloc_size;
+	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+	ht->max_size = max_size;
+
+	return ht;
+}
+
 static
 void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
 {
@@ -803,6 +908,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 		   index, order, index & ((1UL << (order - 1)) - 1));
 	return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
 }
+#endif
 
 static inline
 struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
@@ -1376,8 +1482,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	if (!init_size || (init_size & (init_size - 1)))
 		return NULL;
 
+#ifdef LFHT_MEMORY_ORDER
+	/* max_size == 0 for LFHT_MEMORY_ORDER means infinite max_size. */
 	if (!max_size)
 		max_size = 1UL << (MAX_TABLE_ORDER - 1);
+#endif
 
 	/* max_size must be power of two */
 	if (!max_size || (max_size & (max_size - 1)))
@@ -1387,8 +1496,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	init_size = max(init_size, MIN_TABLE_SIZE);
 	max_size = max(max_size, min_alloc_size);
 	init_size = min(init_size, max_size);
-	ht = calloc(1, sizeof(struct cds_lfht));
-	assert(ht);
+
+	ht = _cds_lfht_alloc(min_alloc_size, max_size);
 	ht->flags = flags;
 	ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
 	ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
@@ -1404,9 +1513,6 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	pthread_mutex_init(&ht->resize_mutex, NULL);
 	order = get_count_order_ulong(init_size);
 	ht->t.resize_target = 1UL << order;
-	ht->min_alloc_size = min_alloc_size;
-	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
-	ht->max_size = max_size;
 	cds_lfht_create_bucket(ht, 1UL << order);
 	ht->t.size = 1UL << order;
 	return ht;
-- 
1.7.4.4

[ltt-dev] [PATCH 06/10 round10] add LFHT_MEMORY_CHUNK low level memory management

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> The old memory mangement is named as LFHT_MEMORY_ORDER.
> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |  116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
>  1 files changed, 111 insertions(+), 5 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index b7be893..ae1177f 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -172,6 +172,10 @@
>  #define dbg_printf(fmt, args...)
>  #endif
>  
> +#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
> +#define LFHT_MEMORY_ORDER
> +#endif
> +
>  /*
>   * Split-counters lazily update the global counter each 1024
>   * addition/removal. It automatically keeps track of resize required.
> @@ -195,6 +199,8 @@
>  #define MAX_TABLE_ORDER			64
>  #endif
>  
> +#define MAX_CHUNK_TABLE			(1UL << 10)
> +
>  /*
>   * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
>   */
> @@ -247,6 +253,7 @@ struct rcu_table {
>  	unsigned long resize_target;
>  	int resize_initiated;
>  
> +#ifdef LFHT_MEMORY_ORDER
>  	/*
>  	 * Contains the per order-index-level bucket node table. The size
>  	 * of each bucket node table is half the number of hashes contained
> @@ -255,6 +262,7 @@ struct rcu_table {
>  	 * levels to improve cache locality for small index orders.
>  	 */
>  	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> +#endif
>  };
>  
>  /*
> @@ -289,6 +297,16 @@ struct cds_lfht {
>  	pthread_attr_t *resize_attr;	/* Resize threads attributes */
>  	long count;			/* global approximate item count */
>  	struct ht_items_count *split_count;	/* split item count */
> +
> +#ifdef LFHT_MEMORY_CHUNK
> +	/*
> +	 * Contains the bucket node chunks. The size of each bucket node
> +	 * chunk is ->min_alloc_size(avoid to alloc chunks with different
> +	 * size). chunks improve cache locality for small index orders
> +	 * and improve lookup_bucket() for the archs without hardware fls().
> +	 */
> +	struct cds_lfht_node *tbl[0];
> +#endif
>  };
>  
>  /*
> @@ -753,6 +771,93 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
>  	return old2;
>  }
>  
> +#ifdef LFHT_MEMORY_CHUNK
> +static
> +struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
> +		unsigned long max_size)
> +{
> +	struct cds_lfht *ht;
> +
> +	min_alloc_size = max(min_alloc_size, max_size / MAX_CHUNK_TABLE);
> +	ht = calloc(1, sizeof(struct cds_lfht) +
> +			sizeof(ht->tbl[0]) * (max_size / min_alloc_size));

Hrm, this first level of indirection quickly becomes much larger than
the order-based table. Have you measured gains with this approach ?

Can you detail the use-case for this approach ?

Have you measured the overhead of software fls() compared to the
overhead of increases cache footprint of the larger table for the
chunk-based approach ?

Thanks,

Mathieu

> +	assert(ht);
> +
> +	ht->min_alloc_size = min_alloc_size;
> +	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> +	ht->max_size = max_size;
> +
> +	return ht;
> +}
> +
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0) {
> +		ht->tbl[0] = calloc(ht->min_alloc_size,
> +			sizeof(struct cds_lfht_node));
> +		assert(ht->tbl[0]);
> +	} else if (order > ht->min_alloc_order) {
> +		unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_order);
> +
> +		for (i = len; i < 2 * len; i++) {
> +			ht->tbl[i] = calloc(ht->min_alloc_size,
> +				sizeof(struct cds_lfht_node));
> +			assert(ht->tbl[i]);
> +		}
> +	}
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0)
> +		poison_free(ht->tbl[0]);
> +	else if (order > ht->min_alloc_order) {
> +		unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_order);
> +
> +		for (i = len; i < 2 * len; i++)
> +			poison_free(ht->tbl[i]);
> +	}
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +static inline
> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> +{
> +	unsigned long chunk, offset;
> +
> +	if (__builtin_constant_p(index) && index == 0)
> +		return &ht->tbl[0][0];
> +
> +	chunk = index >> ht->min_alloc_order;
> +	offset = index & (ht->min_alloc_size - 1);
> +	return &ht->tbl[chunk][offset];
> +}
> +#else
> +/* LFHT_MEMORY_ORDER */
> +static
> +struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
> +		unsigned long max_size)
> +{
> +	struct cds_lfht *ht;
> +
> +	ht = calloc(1, sizeof(struct cds_lfht));
> +	assert(ht);
> +
> +	ht->min_alloc_size = min_alloc_size;
> +	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> +	ht->max_size = max_size;
> +
> +	return ht;
> +}
> +
>  static
>  void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
>  {
> @@ -803,6 +908,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>  		   index, order, index & ((1UL << (order - 1)) - 1));
>  	return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
>  }
> +#endif
>  
>  static inline
>  struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
> @@ -1376,8 +1482,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	if (!init_size || (init_size & (init_size - 1)))
>  		return NULL;
>  
> +#ifdef LFHT_MEMORY_ORDER
> +	/* max_size == 0 for LFHT_MEMORY_ORDER means infinite max_size. */
>  	if (!max_size)
>  		max_size = 1UL << (MAX_TABLE_ORDER - 1);
> +#endif
>  
>  	/* max_size must be power of two */
>  	if (!max_size || (max_size & (max_size - 1)))
> @@ -1387,8 +1496,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	init_size = max(init_size, MIN_TABLE_SIZE);
>  	max_size = max(max_size, min_alloc_size);
>  	init_size = min(init_size, max_size);
> -	ht = calloc(1, sizeof(struct cds_lfht));
> -	assert(ht);
> +
> +	ht = _cds_lfht_alloc(min_alloc_size, max_size);
>  	ht->flags = flags;
>  	ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
>  	ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
> @@ -1404,9 +1513,6 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	pthread_mutex_init(&ht->resize_mutex, NULL);
>  	order = get_count_order_ulong(init_size);
>  	ht->t.resize_target = 1UL << order;
> -	ht->min_alloc_size = min_alloc_size;
> -	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> -	ht->max_size = max_size;
>  	cds_lfht_create_bucket(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] [PATCH 06/10 round10] add LFHT_MEMORY_CHUNK low level memory management

[Mathieu Desnoyers]

Hi Lai,

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
 [...]
> Hrm, this first level of indirection quickly becomes much larger than
> the order-based table. Have you measured gains with this approach ?
> 
> Can you detail the use-case for this approach ?
> 
> Have you measured the overhead of software fls() compared to the
> overhead of increases cache footprint of the larger table for the
> chunk-based approach ?

Hrm, I thought about this a little more last night, and my thoughts are
getting clearer in terms of memory management backends: I'm not against
the chunk-based memory allocation strategy per se, what I would like
though is to have these mm strategies added as plugins rather than as
#ifdef in the code of rculfhash.c. I see that we could introduce a
structure of callback pointers for e.g.

struct rculfhash_mm {
        struct cds_lfht *(*alloc)(unsigned long min_alloc_size,
                                unsigned long max_size);
        void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order);
        void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order);
};

We could then provide their implementation in separate files, e.g.

rculfhash-mm-order.c
rculfhash-mm-chunk.c
rculfhash-mm-mmap.c

A pointer to the mm strategy could be passed to cds_lfht_new upon
hash table creation.

We should probably try to unify the #ifdefs inside struct rcu_table to
put all the variants into a union. We should export the data structure
declarations needed by rculfhash-mm-* in a rculfhash-internal.h header,
placed along with the c files.

Now there is just bucket_at() that I would really like to keep inline.
Thoughts about how to do this efficiently and in a manageable way are
welcome. But I guess we should benchmark the performance difference
between inline and non-inline bucket_at(). It might end up that it's not
really worthwhile to try keeping it inline. Benchmarks would tell...

Thanks,

Mathieu

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

[ltt-dev] [PATCH 06/10 round10] add LFHT_MEMORY_CHUNK low level memory management

[Lai Jiangshan]

On 11/22/2011 06:20 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> The old memory mangement is named as LFHT_MEMORY_ORDER.
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c |  116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
>>  1 files changed, 111 insertions(+), 5 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index b7be893..ae1177f 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -172,6 +172,10 @@
>>  #define dbg_printf(fmt, args...)
>>  #endif
>>  
>> +#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
>> +#define LFHT_MEMORY_ORDER
>> +#endif
>> +
>>  /*
>>   * Split-counters lazily update the global counter each 1024
>>   * addition/removal. It automatically keeps track of resize required.
>> @@ -195,6 +199,8 @@
>>  #define MAX_TABLE_ORDER			64
>>  #endif
>>  
>> +#define MAX_CHUNK_TABLE			(1UL << 10)
>> +
>>  /*
>>   * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
>>   */
>> @@ -247,6 +253,7 @@ struct rcu_table {
>>  	unsigned long resize_target;
>>  	int resize_initiated;
>>  
>> +#ifdef LFHT_MEMORY_ORDER
>>  	/*
>>  	 * Contains the per order-index-level bucket node table. The size
>>  	 * of each bucket node table is half the number of hashes contained
>> @@ -255,6 +262,7 @@ struct rcu_table {
>>  	 * levels to improve cache locality for small index orders.
>>  	 */
>>  	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
>> +#endif
>>  };
>>  
>>  /*
>> @@ -289,6 +297,16 @@ struct cds_lfht {
>>  	pthread_attr_t *resize_attr;	/* Resize threads attributes */
>>  	long count;			/* global approximate item count */
>>  	struct ht_items_count *split_count;	/* split item count */
>> +
>> +#ifdef LFHT_MEMORY_CHUNK
>> +	/*
>> +	 * Contains the bucket node chunks. The size of each bucket node
>> +	 * chunk is ->min_alloc_size(avoid to alloc chunks with different
>> +	 * size). chunks improve cache locality for small index orders
>> +	 * and improve lookup_bucket() for the archs without hardware fls().
>> +	 */
>> +	struct cds_lfht_node *tbl[0];
>> +#endif
>>  };
>>  
>>  /*
>> @@ -753,6 +771,93 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
>>  	return old2;
>>  }
>>  
>> +#ifdef LFHT_MEMORY_CHUNK
>> +static
>> +struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
>> +		unsigned long max_size)
>> +{
>> +	struct cds_lfht *ht;
>> +
>> +	min_alloc_size = max(min_alloc_size, max_size / MAX_CHUNK_TABLE);
>> +	ht = calloc(1, sizeof(struct cds_lfht) +
>> +			sizeof(ht->tbl[0]) * (max_size / min_alloc_size));
> 
> Hrm, this first level of indirection quickly becomes much larger than
> the order-based table. Have you measured gains with this approach ?
> 
> Can you detail the use-case for this approach ?

I guess some times max_bucket_size/normal_bucket_size is not very high,
(I also guess it is quit real/often in practice)
so the users can use bigger min_alloc_size(bigger chunk size) and smaller
chunk pointer table.

(see "History" of memory management)

> 
> Have you measured the overhead of software fls() compared to the
> overhead of increases cache footprint of the larger table for the
> chunk-based approach ?

Sorry, I also guessed. So I just said this management is simpler and better
when there is no hardware fls(). not "better performance", let the users
make the decision.

It seems it is very hard to measure.

"History" of memory management:

I was thinking what is not good when this rculfhash is merged into linux kernel.
the bigger order memory allocation will be an obstacle. we can not allocate
big memory in kernel, we have to allocate small pieces(pages), and we have two
choices:
1) (v)map the pages as continuous order memory.
2) use discontinuous pages as chunks.

2) ===========> I got this LFHT_MEMORY_CHUNK.

1) ===========> since we need to do mapping, why not map them all continuous,
		and map them when demanded, I got LFHT_MEMORY_RESERVED.
		(it introduces a new obstacle, we require big memory space,
		 but 64BITS can provide it easier.)

The paper of Ori Shalev and Nir Shavit are actually a special LFHT_MEMORY_RESERVED.

[ltt-dev] [PATCH 06/10 round10] add LFHT_MEMORY_CHUNK low level memory management

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/22/2011 06:20 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> The old memory mangement is named as LFHT_MEMORY_ORDER.
> >>
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >>  rculfhash.c |  116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
> >>  1 files changed, 111 insertions(+), 5 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index b7be893..ae1177f 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -172,6 +172,10 @@
> >>  #define dbg_printf(fmt, args...)
> >>  #endif
> >>  
> >> +#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
> >> +#define LFHT_MEMORY_ORDER
> >> +#endif
> >> +
> >>  /*
> >>   * Split-counters lazily update the global counter each 1024
> >>   * addition/removal. It automatically keeps track of resize required.
> >> @@ -195,6 +199,8 @@
> >>  #define MAX_TABLE_ORDER			64
> >>  #endif
> >>  
> >> +#define MAX_CHUNK_TABLE			(1UL << 10)
> >> +
> >>  /*
> >>   * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
> >>   */
> >> @@ -247,6 +253,7 @@ struct rcu_table {
> >>  	unsigned long resize_target;
> >>  	int resize_initiated;
> >>  
> >> +#ifdef LFHT_MEMORY_ORDER
> >>  	/*
> >>  	 * Contains the per order-index-level bucket node table. The size
> >>  	 * of each bucket node table is half the number of hashes contained
> >> @@ -255,6 +262,7 @@ struct rcu_table {
> >>  	 * levels to improve cache locality for small index orders.
> >>  	 */
> >>  	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> >> +#endif
> >>  };
> >>  
> >>  /*
> >> @@ -289,6 +297,16 @@ struct cds_lfht {
> >>  	pthread_attr_t *resize_attr;	/* Resize threads attributes */
> >>  	long count;			/* global approximate item count */
> >>  	struct ht_items_count *split_count;	/* split item count */
> >> +
> >> +#ifdef LFHT_MEMORY_CHUNK
> >> +	/*
> >> +	 * Contains the bucket node chunks. The size of each bucket node
> >> +	 * chunk is ->min_alloc_size(avoid to alloc chunks with different
> >> +	 * size). chunks improve cache locality for small index orders
> >> +	 * and improve lookup_bucket() for the archs without hardware fls().
> >> +	 */
> >> +	struct cds_lfht_node *tbl[0];
> >> +#endif
> >>  };
> >>  
> >>  /*
> >> @@ -753,6 +771,93 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> >>  	return old2;
> >>  }
> >>  
> >> +#ifdef LFHT_MEMORY_CHUNK
> >> +static
> >> +struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
> >> +		unsigned long max_size)
> >> +{
> >> +	struct cds_lfht *ht;
> >> +
> >> +	min_alloc_size = max(min_alloc_size, max_size / MAX_CHUNK_TABLE);
> >> +	ht = calloc(1, sizeof(struct cds_lfht) +
> >> +			sizeof(ht->tbl[0]) * (max_size / min_alloc_size));
> > 
> > Hrm, this first level of indirection quickly becomes much larger than
> > the order-based table. Have you measured gains with this approach ?
> > 
> > Can you detail the use-case for this approach ?
> 
> I guess some times max_bucket_size/normal_bucket_size is not very high,
> (I also guess it is quit real/often in practice)
> so the users can use bigger min_alloc_size(bigger chunk size) and smaller
> chunk pointer table.
> 
> (see "History" of memory management)
> 
> > 
> > Have you measured the overhead of software fls() compared to the
> > overhead of increases cache footprint of the larger table for the
> > chunk-based approach ?
> 
> Sorry, I also guessed. So I just said this management is simpler and better
> when there is no hardware fls(). not "better performance", let the users
> make the decision.
> 
> It seems it is very hard to measure.
> 
> "History" of memory management:
> 
> I was thinking what is not good when this rculfhash is merged into linux kernel.
> the bigger order memory allocation will be an obstacle. we can not allocate
> big memory in kernel, we have to allocate small pieces(pages), and we have two
> choices:
> 1) (v)map the pages as continuous order memory.
> 2) use discontinuous pages as chunks.
> 
> 2) ===========> I got this LFHT_MEMORY_CHUNK.
> 
> 1) ===========> since we need to do mapping, why not map them all continuous,
> 		and map them when demanded, I got LFHT_MEMORY_RESERVED.
> 		(it introduces a new obstacle, we require big memory space,
> 		 but 64BITS can provide it easier.)

Ah, I see. So chunk on 32-bit (with page allocation), and reserved on
64-bit. Yep, this makes sense. So having these as plugins would be
really interesting.

Thanks,

Mathieu

> 
> The paper of Ori Shalev and Nir Shavit are actually a special LFHT_MEMORY_RESERVED.
> 
> 

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

[ltt-dev] [PATCH 07/10 round10] add LFHT_MEMORY_RESERVED low level memory management

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |  119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 118 insertions(+), 1 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index ae1177f..b764dc1 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -155,6 +155,7 @@
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>
+#include <sys/mman.h>
 
 #include "config.h"
 #include <urcu.h>
@@ -172,7 +173,7 @@
 #define dbg_printf(fmt, args...)
 #endif
 
-#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
+#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK) && !defined(LFHT_MEMORY_RESERVED)
 #define LFHT_MEMORY_ORDER
 #endif
 
@@ -262,6 +263,13 @@ struct rcu_table {
 	 * levels to improve cache locality for small index orders.
 	 */
 	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
+#elif defined(LFHT_MEMORY_RESERVED)
+	/*
+	 * Contains all the room of buckets without memory allocated.
+	 * All the per order-index-level bucket node tables will be allocated
+	 * inside it when used. It achieves extreme simple bucket indexing.
+	 */
+	struct cds_lfht_node *tbl;
 #endif
 };
 
@@ -840,6 +848,115 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 	offset = index & (ht->min_alloc_size - 1);
 	return &ht->tbl[chunk][offset];
 }
+#elif defined(LFHT_MEMORY_RESERVED)
+static
+struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
+		unsigned long max_size)
+{
+	struct cds_lfht *ht;
+	unsigned long page_bucket_size = getpagesize() / sizeof(*ht->t.tbl);
+
+	if (max_size <= page_bucket_size) /* small table */
+		min_alloc_size = max_size;
+	else /* large table */
+		min_alloc_size = max(min_alloc_size, page_bucket_size);
+
+	ht = calloc(1, sizeof(struct cds_lfht));
+	assert(ht);
+
+	ht->min_alloc_size = min_alloc_size;
+	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+	ht->max_size = max_size;
+
+	return ht;
+}
+
+/* reserve inaccessible memory space without allocation any memory */
+static void *memory_reserve(size_t length)
+{
+	void *ret = mmap(NULL, length, PROT_NONE, MAP_ANONYMOUS, -1, 0);
+
+	assert(ret != MAP_FAILED);
+	return ret;
+}
+
+static void memory_dereserve(void *ptr, size_t length)
+{
+	int ret = munmap(ptr, length);
+
+	assert(ret == 0);
+}
+
+static void memory_populate(void *ptr, size_t length)
+{
+	void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
+			MAP_FIXED | MAP_ANONYMOUS, -1, 0);
+
+	assert(ret == ptr);
+}
+
+/*
+ * Discard garbage memory and avoid system save it when try to swap it out.
+ * Make it still reserved, inaccessible.
+ */
+static void memory_discard(void *ptr, size_t length)
+{
+	void *ret = mmap(ptr, length, PROT_NONE,
+			MAP_FIXED | MAP_ANONYMOUS, -1, 0);
+
+	assert(ret == ptr);
+}
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		if (ht->min_alloc_size == ht->max_size) { /* small table */
+			ht->t.tbl = calloc(ht->max_size, sizeof(*ht->t.tbl));
+			assert(ht->t.tbl);
+			return;
+		}
+		/* large table */
+		ht->t.tbl = memory_reserve(ht->max_size * sizeof(*ht->t.tbl));
+		memory_populate(ht->t.tbl, ht->min_alloc_size * sizeof(*ht->t.tbl));
+	} else if (order > ht->min_alloc_order) { /* large table */
+		unsigned long len = 1UL << (order - 1);
+
+		assert(ht->min_alloc_size < ht->max_size);
+		memory_populate(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		if (ht->min_alloc_size == ht->max_size) { /* small table */
+			poison_free(ht->t.tbl);
+			return;
+		}
+		/* large table */
+		memory_dereserve(ht->t.tbl, ht->max_size * sizeof(*ht->t.tbl));
+	} else if (order > ht->min_alloc_order) { /* large table */
+		unsigned long len = 1UL << (order - 1);
+
+		assert(ht->min_alloc_size < ht->max_size);
+		memory_discard(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+static inline
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+	return &ht->t.tbl[index];
+}
 #else
 /* LFHT_MEMORY_ORDER */
 static
-- 
1.7.4.4

[ltt-dev] [PATCH 07/10 round10] add LFHT_MEMORY_RESERVED low level memory management

[Lai Jiangshan]

Sent wrong patch, use this one.
(Emails were generated from my draft branch, but only this patch is different)


From: Lai Jiangshan <laijs@cn.fujitsu.com>

add LFHT_MEMORY_RESERVED low level memory management
    
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
diff --git a/rculfhash.c b/rculfhash.c
index 9e7150f..824e4e5 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -189,6 +189,7 @@
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>
+#include <sys/mman.h>
 
 #include "config.h"
 #include <urcu.h>
@@ -206,7 +207,7 @@
 #define dbg_printf(fmt, args...)
 #endif
 
-#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
+#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK) && !defined(LFHT_MEMORY_RESERVED)
 #define LFHT_MEMORY_ORDER
 #endif
 
@@ -296,6 +297,13 @@ struct rcu_table {
 	 * levels to improve cache locality for small index orders.
 	 */
 	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
+#elif defined(LFHT_MEMORY_RESERVED)
+	/*
+	 * Contains all the room of buckets without memory allocated.
+	 * All the per order-index-level bucket node tables will be allocated
+	 * inside it when used. It achieves extreme simple bucket indexing.
+	 */
+	struct cds_lfht_node *tbl;
 #endif
 };
 
@@ -874,6 +882,116 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 	offset = index & (ht->min_alloc_size - 1);
 	return &ht->tbl[chunk][offset];
 }
+#elif defined(LFHT_MEMORY_RESERVED)
+static
+struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
+		unsigned long max_size)
+{
+	struct cds_lfht *ht;
+	unsigned long page_bucket_size = getpagesize() / sizeof(*ht->t.tbl);
+
+	if (max_size <= page_bucket_size) /* small table */
+		min_alloc_size = max_size;
+	else /* large table */
+		min_alloc_size = max(min_alloc_size, page_bucket_size);
+
+	ht = calloc(1, sizeof(struct cds_lfht));
+	assert(ht);
+
+	ht->min_alloc_size = min_alloc_size;
+	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+	ht->max_size = max_size;
+
+	return ht;
+}
+
+/* reserve inaccessible memory space without allocation any memory */
+static void *memory_reserve(size_t length)
+{
+	void *ret = mmap(NULL, length, PROT_NONE,
+			MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	assert(ret != MAP_FAILED);
+	return ret;
+}
+
+static void memory_dereserve(void *ptr, size_t length)
+{
+	int ret = munmap(ptr, length);
+
+	assert(ret == 0);
+}
+
+static void memory_populate(void *ptr, size_t length)
+{
+	void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
+			MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	assert(ret == ptr);
+}
+
+/*
+ * Discard garbage memory and avoid system save it when try to swap it out.
+ * Make it still reserved, inaccessible.
+ */
+static void memory_discard(void *ptr, size_t length)
+{
+	void *ret = mmap(ptr, length, PROT_NONE,
+			MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	assert(ret == ptr);
+}
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		if (ht->min_alloc_size == ht->max_size) { /* small table */
+			ht->t.tbl = calloc(ht->max_size, sizeof(*ht->t.tbl));
+			assert(ht->t.tbl);
+			return;
+		}
+		/* large table */
+		ht->t.tbl = memory_reserve(ht->max_size * sizeof(*ht->t.tbl));
+		memory_populate(ht->t.tbl, ht->min_alloc_size * sizeof(*ht->t.tbl));
+	} else if (order > ht->min_alloc_order) { /* large table */
+		unsigned long len = 1UL << (order - 1);
+
+		assert(ht->min_alloc_size < ht->max_size);
+		memory_populate(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+	if (order == 0) {
+		if (ht->min_alloc_size == ht->max_size) { /* small table */
+			poison_free(ht->t.tbl);
+			return;
+		}
+		/* large table */
+		memory_dereserve(ht->t.tbl, ht->max_size * sizeof(*ht->t.tbl));
+	} else if (order > ht->min_alloc_order) { /* large table */
+		unsigned long len = 1UL << (order - 1);
+
+		assert(ht->min_alloc_size < ht->max_size);
+		memory_discard(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
+	}
+	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+static inline
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+	return &ht->t.tbl[index];
+}
 #else
 /* LFHT_MEMORY_ORDER */
 static

[ltt-dev] [PATCH 07/10 round10] add LFHT_MEMORY_RESERVED low level memory management

[Mathieu Desnoyers]

I _really_ like this approach. Although I'm doubtful about the merits of
the "chunk" memory allocation scheme, this mmap-based scheme looks
really promising!

Please resubmit with next round,

Comments below,

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |  119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
>  1 files changed, 118 insertions(+), 1 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index ae1177f..b764dc1 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -155,6 +155,7 @@
>  #include <stdio.h>
>  #include <stdint.h>
>  #include <string.h>
> +#include <sys/mman.h>
>  
>  #include "config.h"
>  #include <urcu.h>
> @@ -172,7 +173,7 @@
>  #define dbg_printf(fmt, args...)
>  #endif
>  
> -#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK)
> +#if !defined(LFHT_MEMORY_ORDER) && !defined(LFHT_MEMORY_CHUNK) && !defined(LFHT_MEMORY_RESERVED)
>  #define LFHT_MEMORY_ORDER
>  #endif
>  
> @@ -262,6 +263,13 @@ struct rcu_table {
>  	 * levels to improve cache locality for small index orders.
>  	 */
>  	struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> +#elif defined(LFHT_MEMORY_RESERVED)
> +	/*
> +	 * Contains all the room of buckets without memory allocated.
> +	 * All the per order-index-level bucket node tables will be allocated
> +	 * inside it when used. It achieves extreme simple bucket indexing.
> +	 */
> +	struct cds_lfht_node *tbl;
>  #endif
>  };
>  
> @@ -840,6 +848,115 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
>  	offset = index & (ht->min_alloc_size - 1);
>  	return &ht->tbl[chunk][offset];
>  }
> +#elif defined(LFHT_MEMORY_RESERVED)
> +static
> +struct cds_lfht *_cds_lfht_alloc(unsigned long min_alloc_size,
> +		unsigned long max_size)
> +{
> +	struct cds_lfht *ht;
> +	unsigned long page_bucket_size = getpagesize() / sizeof(*ht->t.tbl);
> +
> +	if (max_size <= page_bucket_size) /* small table */
> +		min_alloc_size = max_size;
> +	else /* large table */
> +		min_alloc_size = max(min_alloc_size, page_bucket_size);
> +
> +	ht = calloc(1, sizeof(struct cds_lfht));
> +	assert(ht);
> +
> +	ht->min_alloc_size = min_alloc_size;
> +	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> +	ht->max_size = max_size;
> +
> +	return ht;
> +}
> +
> +/* reserve inaccessible memory space without allocation any memory */
> +static void *memory_reserve(size_t length)

reserve -> map ?

> +{
> +	void *ret = mmap(NULL, length, PROT_NONE, MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret != MAP_FAILED);
> +	return ret;
> +}
> +
> +static void memory_dereserve(void *ptr, size_t length)

dereserve -> unmap ?

Thanks,

Mathieu

> +{
> +	int ret = munmap(ptr, length);
> +
> +	assert(ret == 0);
> +}
> +
> +static void memory_populate(void *ptr, size_t length)
> +{
> +	void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
> +			MAP_FIXED | MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret == ptr);
> +}
> +
> +/*
> + * Discard garbage memory and avoid system save it when try to swap it out.
> + * Make it still reserved, inaccessible.
> + */
> +static void memory_discard(void *ptr, size_t length)
> +{
> +	void *ret = mmap(ptr, length, PROT_NONE,
> +			MAP_FIXED | MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret == ptr);
> +}
> +
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0) {
> +		if (ht->min_alloc_size == ht->max_size) { /* small table */
> +			ht->t.tbl = calloc(ht->max_size, sizeof(*ht->t.tbl));
> +			assert(ht->t.tbl);
> +			return;
> +		}
> +		/* large table */
> +		ht->t.tbl = memory_reserve(ht->max_size * sizeof(*ht->t.tbl));
> +		memory_populate(ht->t.tbl, ht->min_alloc_size * sizeof(*ht->t.tbl));
> +	} else if (order > ht->min_alloc_order) { /* large table */
> +		unsigned long len = 1UL << (order - 1);
> +
> +		assert(ht->min_alloc_size < ht->max_size);
> +		memory_populate(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
> +	}
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> +	if (order == 0) {
> +		if (ht->min_alloc_size == ht->max_size) { /* small table */
> +			poison_free(ht->t.tbl);
> +			return;
> +		}
> +		/* large table */
> +		memory_dereserve(ht->t.tbl, ht->max_size * sizeof(*ht->t.tbl));
> +	} else if (order > ht->min_alloc_order) { /* large table */
> +		unsigned long len = 1UL << (order - 1);
> +
> +		assert(ht->min_alloc_size < ht->max_size);
> +		memory_discard(ht->t.tbl + len, len * sizeof(*ht->t.tbl));
> +	}
> +	/* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +static inline
> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> +{
> +	return &ht->t.tbl[index];
> +}
>  #else
>  /* LFHT_MEMORY_ORDER */
>  static
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 08/10 round10] comments for memory management

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |   33 +++++++++++++++++++++++++++++++++
 1 files changed, 33 insertions(+), 0 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index b764dc1..3f982cf 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -117,6 +117,39 @@
  * grow hash table from order 5 to 6: init the index=6 bucket node table
  * shrink hash table from order 6 to 5: fini the index=6 bucket node table
  *
+ * Bucket memory management:
+ * - Bucket node order tables are high level or algorithm level view
+ *   of bucket management of the hash table. The management of
+ *   the memory where the bucket node tables locate is low level
+ *   or raw level view of the hash table.
+ * - The bucket management uses cds_lfht_alloc_bucket_table(order) and
+ *   cds_lfht_free_bucket_table(order) of the memory management to
+ *   alloc/free the bucket node tables.
+ * - Memory management attributes: min_alloc_size, max_size
+ *   Memory management configurations: LFHT_MEMORY_ORDER, LFHT_MEMORY_CHUNK,
+ *   				       LFHT_MEMORY_RESERVED
+ * - min_alloc_size: the smallest allocation buckets size to use and the
+ *   small bucket node tables are forced to be allocated in this contiguous
+ *   memory which improve cache locality of small index orders.
+ * - max_size: the max size of buckets for future growing.
+ * - LFHT_MEMORY_ORDER: a block order memory per a bucket node order table.
+ *   (except small bucket node tables, see min_alloc_size).
+ *   + the size of the table can grow infinitely
+ *   + two level bucket indexing which requires hard/soft fls()
+ *   + bad indexing when there is node hardware fls() instruction
+ * - LFHT_MEMORY_CHUNK: use same-size memory chunks. A big bucket node table
+ *   will be constructed by multi/one memory chunk(s). The size of a chunk
+ *   is choson to be min_alloc_size.
+ *   + a chunk ptr table need be be allocted when the hash table is created
+ *   + two level bucket indexing but simpler than LFHT_MEMORY_ORDER
+ * - LFHT_MEMORY_RESERVED: reserve a large memory space for all the max_size
+ *   buckets when hash table is created. All of the bucket node tables
+ *   are/(will be) allocated in this contiguous memory space. The memory
+ *   is allocated only when it is demanded. And when a bucket node table
+ *   is free, the memory can be discard to reduce system memory presure.
+ *   + one level bucket indexing, extremly simple
+ *   + recomended only when the system have enough memory space: 64BITS.
+ *
  * A bit of ascii art explanation:
  * 
  * Order index is the off-by-one compare to the actual power of 2 because 
-- 
1.7.4.4

[ltt-dev] [PATCH 09/10 round10] fix comments of cds_lfht_new()

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 urcu/rculfhash.h |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 2eefd2c..b7d5039 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -119,6 +119,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
  * @flags: hash table creation flags (can be combined with bitwise or: '|').
  *           0: no flags.
  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
+ *           CDS_LFHT_ACCOUNTING: count the number of node addition
+ *                                and removal in the table
  * @attr: optional resize worker thread attributes. NULL for default.
  *
  * Return NULL on error.
@@ -131,7 +133,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
  * this priority level. Having lower priority for call_rcu and resize threads
  * does not pose any correctness issue, but the resize operations could be
  * starved by updates, thus leading to long hash table bucket chains.
- * Threads calling this API need to be registered RCU read-side threads.
+ * Threads calling this API are NOT required to be registered RCU read-side
+ * threads. It can be called very early.(before rcu is initialized ...etc.)
  */
 static inline
 struct cds_lfht *cds_lfht_new(unsigned long init_size,
-- 
1.7.4.4

[ltt-dev] [PATCH 09/10 round10] fix comments of cds_lfht_new()

[Mathieu Desnoyers]

Merged as:

commit 44bbe7fa346773b33bf9024efea88705c2f6f476
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Wed Nov 23 06:44:35 2011 +0100

    Update comments of cds_lfht_new()
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 9208011..5754719 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -117,6 +117,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
  * @flags: hash table creation flags (can be combined with bitwise or: '|').
  *           0: no flags.
  *           CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
+ *           CDS_LFHT_ACCOUNTING: count the number of node addition
+ *                                and removal in the table
  * @attr: optional resize worker thread attributes. NULL for default.
  *
  * Return NULL on error.
@@ -129,7 +131,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
  * this priority level. Having lower priority for call_rcu and resize threads
  * does not pose any correctness issue, but the resize operations could be
  * starved by updates, thus leading to long hash table bucket chains.
- * Threads calling this API need to be registered RCU read-side threads.
+ * Threads calling this API are NOT required to be registered RCU read-side
+ * threads. It can be called very early.(before rcu is initialized ...etc.)
  */
 static inline
 struct cds_lfht *cds_lfht_new(unsigned long init_size,

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

[ltt-dev] [PATCH 10/10 round10] add my name

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c      |    1 +
 urcu/rculfhash.h |    1 +
 2 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 3f982cf..2fe9bdc 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -4,6 +4,7 @@
  * Userspace RCU library - Lock-Free Resizable RCU Hash Table
  *
  * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index b7d5039..8e43d8d 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -7,6 +7,7 @@
  * Userspace RCU library - Lock-Free RCU Hash Table
  *
  * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
-- 
1.7.4.4

[ltt-dev] [PATCH 10/10 round10] add my name

[Mathieu Desnoyers]

Merged, as the following commit. Thanks Lai!

Mathieu

commit 0dcf48471eda28730279e5ead11e5411d23e3af0
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Wed Nov 23 06:45:57 2011 +0100

    Add Lai Jiangshan's copyright to rculfhash
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index c08447b..4f82da4 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -4,6 +4,7 @@
  * Userspace RCU library - Lock-Free Resizable RCU Hash Table
  *
  * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 5754719..d3018b7 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -7,6 +7,7 @@
  * Userspace RCU library - Lock-Free RCU Hash Table
  *
  * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public

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