[ltt-dev] [PATCH 1/6 respin] cleanup order semantic

[Mathieu Desnoyers]

Merged as:

commit 93d46c395ff595372827983e9e84bd1e49eb6fab
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Fri Oct 28 05:15:46 2011 +0200

    Cleanup order semantic
    
    [ Edit by Mathieu Desnoyers: renamed "end_order" to "last_order", to
      match the "first_order" inclusive semantic. Normally, "end" excludes
      the range limit value, but "last" includes it. We use an inclusive
      range end value here. ]
    
    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 5264a8e..18a3cb8 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -91,12 +91,32 @@
  *   the "dummy node" tables.
  * - There is one dummy node table per hash index order. The size of
  *   each dummy node table is half the number of hashes contained in
- *   this order.
- * - call_rcu is used to garbage-collect the old order table.
+ *   this order (except for order 0).
+ * - synchronzie_rcu is used to garbage-collect the old dummy node table.
  * - The per-order dummy node tables contain a compact version of the
  *   hash table nodes. These tables are invariant after they are
  *   populated into the hash table.
- * 
+ *
+ * Dummy node tables:
+ *
+ * hash table	hash table	the last	all dummy node tables
+ * order	size		dummy node	0   1   2   3   4   5   6(index)
+ * 				table size
+ * 0		1		1		1
+ * 1		2		1		1   1
+ * 2		4		2		1   1   2
+ * 3		8		4		1   1   2   4
+ * 4		16		8		1   1   2   4   8
+ * 5		32		16		1   1   2   4   8  16
+ * 6		64		32		1   1   2   4   8  16  32
+ *
+ * When growing/shrinking, we only focus on the last dummy node table
+ * which size is (!order ? 1 : (1 << (order -1))).
+ *
+ * Example for growing/shrinking:
+ * grow hash table from order 5 to 6: init the index=6 dummy node table
+ * shrink hash table from order 6 to 5: fini the index=6 dummy node table
+ *
  * A bit of ascii art explanation:
  * 
  * Order index is the off-by-one compare to the actual power of 2 because 
@@ -1079,14 +1099,13 @@ void init_table_populate(struct cds_lfht *ht, unsigned long i,
 
 static
 void init_table(struct cds_lfht *ht,
-		unsigned long first_order, unsigned long len_order)
+		unsigned long first_order, unsigned long last_order)
 {
-	unsigned long i, end_order;
+	unsigned long i;
 
-	dbg_printf("init table: first_order %lu end_order %lu\n",
-		   first_order, first_order + len_order);
-	end_order = first_order + len_order;
-	for (i = first_order; i < end_order; i++) {
+	dbg_printf("init table: first_order %lu last_order %lu\n",
+		   first_order, last_order);
+	for (i = first_order; i <= last_order; i++) {
 		unsigned long len;
 
 		len = !i ? 1 : 1UL << (i - 1);
@@ -1179,16 +1198,15 @@ void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
 
 static
 void fini_table(struct cds_lfht *ht,
-		unsigned long first_order, unsigned long len_order)
+		unsigned long first_order, unsigned long last_order)
 {
-	long i, end_order;
+	long i;
 	void *free_by_rcu = NULL;
 
-	dbg_printf("fini table: first_order %lu end_order %lu\n",
-		   first_order, first_order + len_order);
-	end_order = first_order + len_order;
+	dbg_printf("fini table: first_order %lu last_order %lu\n",
+		   first_order, last_order);
 	assert(first_order > 0);
-	for (i = end_order - 1; i >= first_order; i--) {
+	for (i = last_order; i >= first_order; i--) {
 		unsigned long len;
 
 		len = !i ? 1 : 1UL << (i - 1);
@@ -1271,11 +1289,11 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 	ht->percpu_count = alloc_per_cpu_items_count();
 	/* this mutex should not nest in read-side C.S. */
 	pthread_mutex_init(&ht->resize_mutex, NULL);
-	order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE)) + 1;
+	order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE));
 	ht->flags = flags;
 	ht->cds_lfht_rcu_thread_offline();
 	pthread_mutex_lock(&ht->resize_mutex);
-	ht->t.resize_target = 1UL << (order - 1);
+	ht->t.resize_target = 1UL << order;
 	init_table(ht, 0, order);
 	pthread_mutex_unlock(&ht->resize_mutex);
 	ht->cds_lfht_rcu_thread_online();
@@ -1582,12 +1600,12 @@ void _do_cds_lfht_grow(struct cds_lfht *ht,
 {
 	unsigned long old_order, new_order;
 
-	old_order = get_count_order_ulong(old_size) + 1;
-	new_order = get_count_order_ulong(new_size) + 1;
+	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",
 		   old_size, old_order, new_size, new_order);
 	assert(new_size > old_size);
-	init_table(ht, old_order, new_order - old_order);
+	init_table(ht, old_order + 1, new_order);
 }
 
 /* called with resize mutex held */
@@ -1598,14 +1616,14 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
 	unsigned long old_order, new_order;
 
 	new_size = max(new_size, MIN_TABLE_SIZE);
-	old_order = get_count_order_ulong(old_size) + 1;
-	new_order = get_count_order_ulong(new_size) + 1;
+	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",
 		   old_size, old_order, new_size, new_order);
 	assert(new_size < old_size);
 
 	/* Remove and unlink all dummy nodes to remove. */
-	fini_table(ht, new_order, old_order - new_order);
+	fini_table(ht, new_order + 1, old_order);
 }
 
 
-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com