X-Git-Url: https://git.liburcu.org/?a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=c696533db612502c2af74cd3b0d2afb4b13d0670;hb=13f656f996861f47172f34a1ef28e338616ff5e2;hp=25f872f7319a03f3a1c1847aee7e7efcf9d8dcf0;hpb=8ed51e048a8e89b09cca31271d640bbaa521c74a;p=urcu.git

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 25f872f..c696533 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -41,6 +41,8 @@
 #define DEFAULT_MIN_ALLOC_SIZE	1
 #define DEFAULT_RAND_POOL	1000000
 
+#define TEST_HASH_SEED	0x42UL
+
 /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
 #define CACHE_LINE_SIZE 4096
 
@@ -105,6 +107,35 @@ struct test_data {
 	int b;
 };
 
+struct lfht_test_node {
+	struct cds_lfht_node node;
+	void *key;
+	unsigned int key_len;
+	/* cache-cold for iteration */
+	struct rcu_head head;
+};
+
+static inline struct lfht_test_node *
+to_test_node(struct cds_lfht_node *node)
+{
+	return caa_container_of(node, struct lfht_test_node, node);
+}
+
+static inline
+void lfht_test_node_init(struct lfht_test_node *node, void *key,
+			size_t key_len)
+{
+	cds_lfht_node_init(&node->node);
+	node->key = key;
+	node->key_len = key_len;
+}
+
+static inline struct lfht_test_node *
+cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
+{
+	return to_test_node(cds_lfht_iter_get_node(iter));
+}
+
 static volatile int test_go, test_stop;
 
 static unsigned long wdelay;
@@ -116,9 +147,11 @@ static unsigned long rduration;
 
 static unsigned long init_hash_size = DEFAULT_HASH_SIZE;
 static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE;
+static unsigned long max_hash_buckets_size = (1UL << 20);
 static unsigned long init_populate;
 static int opt_auto_resize;
 static int add_only, add_unique, add_replace;
+static const struct cds_lfht_mm_type *memory_backend;
 
 static unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
 static unsigned long init_pool_size = DEFAULT_RAND_POOL,
@@ -353,7 +386,7 @@ void hashword2(
 
 #if (CAA_BITS_PER_LONG == 32)
 static
-unsigned long test_hash(void *_key, size_t length, unsigned long seed)
+unsigned long test_hash(const void *_key, size_t length, unsigned long seed)
 {
 	unsigned int key = (unsigned int) _key;
 
@@ -362,7 +395,7 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed)
 }
 #else
 static
-unsigned long test_hash(void *_key, size_t length, unsigned long seed)
+unsigned long test_hash(const void *_key, size_t length, unsigned long seed)
 {
 	union {
 		uint64_t v64;
@@ -382,8 +415,8 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed)
 #endif
 
 static
-unsigned long test_compare(void *key1, size_t key1_len,
-                           void *key2, size_t key2_len)
+unsigned long test_compare(const void *key1, size_t key1_len,
+                           const void *key2, size_t key2_len)
 {
 	if (caa_unlikely(key1_len != key2_len))
 		return -1;
@@ -394,6 +427,25 @@ unsigned long test_compare(void *key1, size_t key1_len,
 		return 1;
 }
 
+static
+int test_match(struct cds_lfht_node *node, const void *key)
+{
+	struct lfht_test_node *test_node = to_test_node(node);
+
+	return !test_compare(test_node->key, test_node->key_len,
+			key, sizeof(unsigned long));
+}
+
+static inline
+void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
+		struct cds_lfht_iter *iter)
+{
+	assert(key_len == sizeof(unsigned long));
+
+	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
+			test_match, key, iter);
+}
+
 void *thr_count(void *arg)
 {
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -437,7 +489,7 @@ void *thr_count(void *arg)
 void *thr_reader(void *_count)
 {
 	unsigned long long *count = _count;
-	struct cds_lfht_node *node;
+	struct lfht_test_node *node;
 	struct cds_lfht_iter iter;
 
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -454,10 +506,10 @@ void *thr_reader(void *_count)
 
 	for (;;) {
 		rcu_read_lock();
-		cds_lfht_lookup(test_ht,
+		cds_lfht_test_lookup(test_ht,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
 			sizeof(void *), &iter);
-		node = cds_lfht_iter_get_node(&iter);
+		node = cds_lfht_iter_get_test_node(&iter);
 		if (node == NULL) {
 			if (validate_lookup) {
 				printf("[ERROR] Lookup cannot find initial node.\n");
@@ -492,14 +544,15 @@ void *thr_reader(void *_count)
 static
 void free_node_cb(struct rcu_head *head)
 {
-	struct cds_lfht_node *node =
-		caa_container_of(head, struct cds_lfht_node, head);
+	struct lfht_test_node *node =
+		caa_container_of(head, struct lfht_test_node, head);
 	free(node);
 }
 
 void *thr_writer(void *_count)
 {
-	struct cds_lfht_node *node, *ret_node;
+	struct lfht_test_node *node;
+	struct cds_lfht_node *ret_node;
 	struct cds_lfht_iter iter;
 	struct wr_count *count = _count;
 	int ret;
@@ -519,26 +572,33 @@ void *thr_writer(void *_count)
 	for (;;) {
 		if ((addremove == AR_ADD || add_only)
 				|| (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
-			node = malloc(sizeof(struct cds_lfht_node));
-			cds_lfht_node_init(node,
+			node = malloc(sizeof(struct lfht_test_node));
+			lfht_test_node_init(node,
 				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, node);
+				ret_node = cds_lfht_add_unique(test_ht,
+					test_hash(node->key, node->key_len, TEST_HASH_SEED),
+					test_match, node->key, &node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, node);
+					ret_node = cds_lfht_add_replace(test_ht,
+							test_hash(node->key, node->key_len, TEST_HASH_SEED),
+							test_match, node->key, &node->node);
 				else
-					cds_lfht_add(test_ht, node);
+					cds_lfht_add(test_ht,
+						test_hash(node->key, node->key_len, TEST_HASH_SEED),
+						&node->node);
 			}
 			rcu_read_unlock();
-			if (add_unique && ret_node != node) {
+			if (add_unique && ret_node != &node->node) {
 				free(node);
 				nr_addexist++;
 			} else {
 				if (add_replace && ret_node) {
-					call_rcu(&ret_node->head, free_node_cb);
+					call_rcu(&to_test_node(ret_node)->head,
+							free_node_cb);
 					nr_addexist++;
 				} else {
 					nr_add++;
@@ -547,13 +607,13 @@ void *thr_writer(void *_count)
 		} else {
 			/* May delete */
 			rcu_read_lock();
-			cds_lfht_lookup(test_ht,
+			cds_lfht_test_lookup(test_ht,
 				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
 				sizeof(void *), &iter);
 			ret = cds_lfht_del(test_ht, &iter);
 			rcu_read_unlock();
 			if (ret == 0) {
-				node = cds_lfht_iter_get_node(&iter);
+				node = cds_lfht_iter_get_test_node(&iter);
 				call_rcu(&node->head, free_node_cb);
 				nr_del++;
 			} else
@@ -596,7 +656,8 @@ void *thr_writer(void *_count)
 
 static int populate_hash(void)
 {
-	struct cds_lfht_node *node, *ret_node;
+	struct lfht_test_node *node;
+	struct cds_lfht_node *ret_node;
 
 	if (!init_populate)
 		return 0;
@@ -608,26 +669,32 @@ static int populate_hash(void)
 	}
 
 	while (nr_add < init_populate) {
-		node = malloc(sizeof(struct cds_lfht_node));
-		cds_lfht_node_init(node,
+		node = malloc(sizeof(struct lfht_test_node));
+		lfht_test_node_init(node,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % init_pool_size) + init_pool_offset),
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, node);
+			ret_node = cds_lfht_add_unique(test_ht,
+				test_hash(node->key, node->key_len, TEST_HASH_SEED),
+				test_match, node->key, &node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, node);
+				ret_node = cds_lfht_add_replace(test_ht,
+						test_hash(node->key, node->key_len, TEST_HASH_SEED),
+						test_match, node->key, &node->node);
 			else
-				cds_lfht_add(test_ht, node);
+				cds_lfht_add(test_ht,
+					test_hash(node->key, node->key_len, TEST_HASH_SEED),
+					&node->node);
 		}
 		rcu_read_unlock();
-		if (add_unique && ret_node != node) {
+		if (add_unique && ret_node != &node->node) {
 			free(node);
 			nr_addexist++;
 		} else {
 			if (add_replace && ret_node) {
-				call_rcu(&ret_node->head, free_node_cb);
+				call_rcu(&to_test_node(ret_node)->head, free_node_cb);
 				nr_addexist++;
 			} else {
 				nr_add++;
@@ -642,17 +709,15 @@ static
 void test_delete_all_nodes(struct cds_lfht *ht)
 {
 	struct cds_lfht_iter iter;
-	struct cds_lfht_node *node;
+	struct lfht_test_node *node;
 	unsigned long count = 0;
 
-	cds_lfht_first(ht, &iter);
-	while ((node = cds_lfht_iter_get_node(&iter)) != NULL) {
+	cds_lfht_for_each_entry(ht, &iter, node, node) {
 		int ret;
 
 		ret = cds_lfht_del(test_ht, &iter);
 		assert(!ret);
 		call_rcu(&node->head, free_node_cb);
-		cds_lfht_next(ht, &iter);
 		count++;
 	}
 	printf("deleted %lu nodes.\n", count);
@@ -668,14 +733,16 @@ void show_usage(int argc, char **argv)
 	printf("        [-c duration] (reader C.S. duration (in loops))\n");
 	printf("        [-v] (verbose output)\n");
 	printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
-	printf("        [-h size] (initial hash table size)\n");
-	printf("        [-m size] (minimum hash alloc size)\n");
+	printf("        [-h size] (initial number of buckets)\n");
+	printf("        [-m size] (minimum number of allocated buckets)\n");
+	printf("        [-n size] (maximum number of buckets)\n");
 	printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
 	printf("        [-u] Uniquify add (no redundant keys).\n");
 	printf("        [-s] Replace (swap) entries.\n");
 	printf("        [-i] Add only (no removal).\n");
 	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
 	printf("        [-A] Automatically resize hash table.\n");
+	printf("        [-B order|chunk|mmap] Specify the memory backend.\n");
 	printf("        [-R offset] Lookup pool offset.\n");
 	printf("        [-S offset] Write pool offset.\n");
 	printf("        [-T offset] Init pool offset.\n");
@@ -778,6 +845,13 @@ int main(int argc, char **argv)
 			}
 			min_hash_alloc_size = atol(argv[++i]);
 			break;
+		case 'n':
+			if (argc < i + 2) {
+				show_usage(argc, argv);
+				return -1;
+			}
+			max_hash_buckets_size = atol(argv[++i]);
+			break;
 		case 'u':
 			if (add_replace) {
 				printf("Please specify at most one of -s or -u.\n");
@@ -801,6 +875,23 @@ int main(int argc, char **argv)
 		case 'A':
 			opt_auto_resize = 1;
 			break;
+		case 'B':
+			if (argc < i + 2) {
+				show_usage(argc, argv);
+				return -1;
+			}
+			i++;
+			if (!strcmp("order", argv[i]))
+				memory_backend = &cds_lfht_mm_order;
+			else if (!strcmp("chunk", argv[i]))
+				memory_backend = &cds_lfht_mm_chunk;
+			else if (!strcmp("mmap", argv[i]))
+				memory_backend = &cds_lfht_mm_mmap;
+                        else {
+				printf("Please specify memory backend with order|chunk|mmap.\n");
+				exit(-1);
+			}
+			break;
 		case 'R':
 			lookup_pool_offset = atol(argv[++i]);
 			break;
@@ -828,17 +919,23 @@ int main(int argc, char **argv)
 
 	/* Check if hash size is power of 2 */
 	if (init_hash_size && init_hash_size & (init_hash_size - 1)) {
-		printf("Error: Hash table size %lu is not a power of 2.\n",
+		printf("Error: Initial number of buckets (%lu) is not a power of 2.\n",
 			init_hash_size);
 		return -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",
+	if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
+		printf("Error: Minimum number of allocated buckets (%lu) is not a power of 2.\n",
 			min_hash_alloc_size);
 		return -1;
 	}
 
+	if (max_hash_buckets_size && max_hash_buckets_size & (max_hash_buckets_size - 1)) {
+		printf("Error: Maximum number of buckets (%lu) is not a power of 2.\n",
+			max_hash_buckets_size);
+		return -1;
+	}
+
 	memset(&act, 0, sizeof(act));
 	ret = sigemptyset(&act.sa_mask);
 	if (ret == -1) {
@@ -880,8 +977,9 @@ int main(int argc, char **argv)
 	printf_verbose("Mode:%s%s.\n",
 		add_only ? " add only" : " add/remove",
 		add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
-	printf_verbose("Initial hash table size: %lu buckets.\n", init_hash_size);
-	printf_verbose("Minimum hash alloc size: %lu buckets.\n", min_hash_alloc_size);
+	printf_verbose("Initial number of buckets: %lu buckets.\n", init_hash_size);
+	printf_verbose("Minimum number of allocated buckets: %lu buckets.\n", min_hash_alloc_size);
+	printf_verbose("Maximum number of buckets: %lu buckets.\n", max_hash_buckets_size);
 	printf_verbose("Init pool size offset %lu size %lu.\n",
 		init_pool_offset, init_pool_size);
 	printf_verbose("Lookup pool size offset %lu size %lu.\n",
@@ -899,15 +997,24 @@ int main(int argc, char **argv)
 	err = create_all_cpu_call_rcu_data(0);
         assert(!err);
 
+	if (memory_backend) {
+		test_ht = _cds_lfht_new(init_hash_size, min_hash_alloc_size,
+				max_hash_buckets_size,
+				(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
+				CDS_LFHT_ACCOUNTING, memory_backend,
+				&rcu_flavor, NULL);
+	} else {
+		test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
+				max_hash_buckets_size,
+				(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
+				CDS_LFHT_ACCOUNTING, NULL);
+	}
+
 	/*
-	 * Hash creation and population needs to be seen as a RCU reader
+	 * Hash Population needs to be seen as a RCU reader
 	 * thread from the point of view of resize.
 	 */
 	rcu_register_thread();
-	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
-			init_hash_size, min_hash_alloc_size,
-			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
-			CDS_LFHT_ACCOUNTING, NULL);
       	ret = populate_hash();
 	assert(!ret);