X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=rculfhash.c;h=807191593c6e7d7671b7ca6f236657771a7d3f32;hb=d0d8f9aa03e9df3ca61b8c823678e5c3a9640a4d;hp=5ad75833a37d77ba4f347d68834d0127e8bc574d;hpb=9d72a73f9c1fbbdd686a2e39a96f1917d5bb4f96;p=urcu.git

diff --git a/rculfhash.c b/rculfhash.c
index 5ad7583..8071915 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -187,7 +187,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
@@ -756,6 +757,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)
 {
@@ -1112,7 +1143,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 = size + start; j < size + start + len; j++) {
 		struct cds_lfht_node *new_node = bucket_at(ht, j);
@@ -1148,7 +1179,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;
 
@@ -1159,8 +1190,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
@@ -1211,7 +1241,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);
@@ -1244,11 +1274,11 @@ 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);
-	assert(first_order > ht->min_alloc_order);
+	assert(first_order > MIN_TABLE_ORDER);
 	for (i = last_order; i >= first_order; i--) {
 		unsigned long len;
 
@@ -1269,8 +1299,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.
@@ -1280,16 +1310,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);
 	}
 }
 
@@ -1299,8 +1329,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);
@@ -1309,12 +1338,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++) {
 			/*
@@ -1367,7 +1391,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;
@@ -1590,23 +1614,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;
 }
 
@@ -1704,7 +1721,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",
@@ -1752,7 +1769,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);
 }
 
@@ -1827,7 +1844,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 */