From 0422d92c2d658f6093b8209f75808efd2109a110 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sat, 5 Nov 2011 09:01:09 -0400 Subject: [PATCH] rculfhash: extract compare_fct and hash_fct from the hash table Leave the compare_fct and hash_fct to the caller, which can therefore become the only one which needs to know the layout of struct cds_lfht_node (except for the _cds_lfht_node part). This will enable us to remove the cds_lfht_node structure from the hash table (moving it entirely to the caller), replacing it by _cds_lfht_node, which is really the only part the hash table needs to know about. Use-cases that can benefit from this extra flexibility: >> Sometimes the caller don't have the key or the keys which are big >> are saved separated. Example: file server >> Or key comparation is too slow. >> Or caller just need approximate lookup. >> Or caller want to compare keys with different strategies for >> performance. Suggested-by: Lai Jiangshan Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 57 ++++++++++++++++--------------------- tests/test_urcu_hash.c | 51 ++++++++++++++++++++++++++------- urcu/rculfhash.h | 64 +++++++++++++++++++++++++++++------------- 3 files changed, 109 insertions(+), 63 deletions(-) diff --git a/rculfhash.c b/rculfhash.c index 600feec..53ecaac 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -267,8 +267,6 @@ struct rcu_table { */ struct cds_lfht { struct rcu_table t; - cds_lfht_hash_fct hash_fct; - cds_lfht_compare_fct compare_fct; unsigned long min_alloc_order; unsigned long min_alloc_size; unsigned long hash_seed; @@ -320,6 +318,7 @@ struct partition_resize_work { static void _cds_lfht_add(struct cds_lfht *ht, + cds_lfht_match_fct match, unsigned long size, struct cds_lfht_node *node, struct cds_lfht_iter *unique_ret, @@ -892,6 +891,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, */ static void _cds_lfht_add(struct cds_lfht *ht, + cds_lfht_match_fct match, unsigned long size, struct cds_lfht_node *node, struct cds_lfht_iter *unique_ret, @@ -944,7 +944,7 @@ void _cds_lfht_add(struct cds_lfht *ht, * (including observe one node by one node * by forward iterations) */ - cds_lfht_next_duplicate(ht, &d_iter); + cds_lfht_next_duplicate(ht, match, &d_iter); if (!d_iter.node) goto insert; @@ -1120,7 +1120,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, i, j, (1UL << (i - 1)) + j); new_node->p.reverse_hash = bit_reverse_ulong((1UL << (i - 1)) + j); - _cds_lfht_add(ht, 1UL << (i - 1), + _cds_lfht_add(ht, NULL, 1UL << (i - 1), new_node, NULL, 1); } ht->cds_lfht_rcu_read_unlock(); @@ -1337,10 +1337,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size) } } -struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, - cds_lfht_compare_fct compare_fct, - unsigned long hash_seed, - unsigned long init_size, +struct cds_lfht *_cds_lfht_new(unsigned long init_size, unsigned long min_alloc_size, int flags, void (*cds_lfht_call_rcu)(struct rcu_head *head, @@ -1368,9 +1365,6 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, ht = calloc(1, sizeof(struct cds_lfht)); assert(ht); ht->flags = flags; - ht->hash_fct = hash_fct; - ht->compare_fct = compare_fct; - ht->hash_seed = hash_seed; ht->cds_lfht_call_rcu = cds_lfht_call_rcu; ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu; ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock; @@ -1392,14 +1386,13 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, return ht; } -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, - struct cds_lfht_iter *iter) +void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match, + unsigned long hash, void *key, struct cds_lfht_iter *iter) { struct cds_lfht_node *node, *next, *dummy_node; struct _cds_lfht_node *lookup; - unsigned long hash, reverse_hash, size; + unsigned long reverse_hash, size; - hash = ht->hash_fct(key, key_len, ht->hash_seed); reverse_hash = bit_reverse_ulong(hash); size = rcu_dereference(ht->t.size); @@ -1422,7 +1415,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, if (caa_likely(!is_removed(next)) && !is_dummy(next) && node->p.reverse_hash == reverse_hash - && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) { + && caa_likely(match(node, key))) { break; } node = clear_flag(next); @@ -1432,17 +1425,16 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, iter->next = next; } -void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter) +void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match, + struct cds_lfht_iter *iter) { struct cds_lfht_node *node, *next; unsigned long reverse_hash; void *key; - size_t key_len; node = iter->node; reverse_hash = node->p.reverse_hash; key = node->key; - key_len = node->key_len; next = iter->next; node = clear_flag(next); @@ -1458,7 +1450,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter) next = rcu_dereference(node->p.next); if (caa_likely(!is_removed(next)) && !is_dummy(next) - && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) { + && caa_likely(match(node->key, key))) { break; } node = clear_flag(next); @@ -1503,46 +1495,45 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter) cds_lfht_next(ht, iter); } -void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node) +void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, + struct cds_lfht_node *node) { - unsigned long hash, size; + unsigned long size; - hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); - size = rcu_dereference(ht->t.size); - _cds_lfht_add(ht, size, node, NULL, 0); + _cds_lfht_add(ht, NULL, size, node, NULL, 0); ht_count_add(ht, size, hash); } struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, + cds_lfht_match_fct match, + unsigned long hash, struct cds_lfht_node *node) { - unsigned long hash, size; + unsigned long size; struct cds_lfht_iter iter; - hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); - size = rcu_dereference(ht->t.size); - _cds_lfht_add(ht, size, node, &iter, 0); + _cds_lfht_add(ht, match, size, node, &iter, 0); if (iter.node == node) ht_count_add(ht, size, hash); return iter.node; } struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, + cds_lfht_match_fct match, + unsigned long hash, struct cds_lfht_node *node) { - unsigned long hash, size; + unsigned long size; struct cds_lfht_iter iter; - hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); - size = rcu_dereference(ht->t.size); for (;;) { - _cds_lfht_add(ht, size, node, &iter, 0); + _cds_lfht_add(ht, match, size, node, &iter, 0); if (iter.node == node) { ht_count_add(ht, size, hash); return NULL; diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index e28c14a..3111353 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 @@ -419,6 +421,24 @@ unsigned long test_compare(void *key1, size_t key1_len, return 1; } +static +int test_match(struct cds_lfht_node *node, void *arg) +{ + return !test_compare(node->key, node->key_len, + arg, sizeof(unsigned long)); +} + +static +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_match, + test_hash(key, key_len, TEST_HASH_SEED), + key, iter); +} + void *thr_count(void *arg) { printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -479,7 +499,7 @@ 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_test_node(&iter); @@ -551,12 +571,18 @@ void *thr_writer(void *_count) sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, &node->node); + ret_node = cds_lfht_add_unique(test_ht, test_match, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); } else { if (add_replace) - ret_node = cds_lfht_add_replace(test_ht, &node->node); + ret_node = cds_lfht_add_replace(test_ht, test_match, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); else - cds_lfht_add(test_ht, &node->node); + cds_lfht_add(test_ht, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); } rcu_read_unlock(); if (add_unique && ret_node != &node->node) { @@ -574,7 +600,7 @@ 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); @@ -642,12 +668,18 @@ static int populate_hash(void) sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, &node->node); + ret_node = cds_lfht_add_unique(test_ht, test_match, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); } else { if (add_replace) - ret_node = cds_lfht_add_replace(test_ht, &node->node); + ret_node = cds_lfht_add_replace(test_ht, test_match, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); else - cds_lfht_add(test_ht, &node->node); + cds_lfht_add(test_ht, + test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED), + &node->node); } rcu_read_unlock(); if (add_unique && ret_node != &node->node) { @@ -932,8 +964,7 @@ int main(int argc, char **argv) * 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, + test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (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 f4f3373..9dcaf02 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -84,11 +84,13 @@ struct cds_lfht; typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length, unsigned long seed); -typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len, - void *key2, size_t key2_len); +typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, void *key); /* * cds_lfht_node_init - initialize a hash table node + * @node: the node to initialize. + * @key: pointer to the key to use. + * @key_len: the length of the key, in bytes. */ static inline void cds_lfht_node_init(struct cds_lfht_node *node, void *key, @@ -109,10 +111,7 @@ enum { /* * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly. */ -struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, - cds_lfht_compare_fct compare_fct, - unsigned long hash_seed, - unsigned long init_size, +struct cds_lfht *_cds_lfht_new(unsigned long init_size, unsigned long min_alloc_size, int flags, void (*cds_lfht_call_rcu)(struct rcu_head *head, @@ -128,9 +127,6 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, /* * cds_lfht_new - allocate a hash table. - * @hash_fct: the hashing function. - * @compare_fct: the key comparison function. - * @hash_seed: the seed for hash function. * @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. * @flags: hash table creation flags (can be combined with bitwise or: '|'). @@ -151,16 +147,12 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, * Threads calling this API need to be registered RCU read-side threads. */ static inline -struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct, - cds_lfht_compare_fct compare_fct, - unsigned long hash_seed, - unsigned long init_size, +struct cds_lfht *cds_lfht_new(unsigned long init_size, unsigned long min_alloc_size, int flags, pthread_attr_t *attr) { - return _cds_lfht_new(hash_fct, compare_fct, hash_seed, - init_size, min_alloc_size, flags, + return _cds_lfht_new(init_size, min_alloc_size, flags, call_rcu, synchronize_rcu, rcu_read_lock, rcu_read_unlock, rcu_thread_offline, rcu_thread_online, rcu_register_thread, @@ -187,6 +179,7 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr); * @count: Traverse the hash table, count the number of nodes observed. * @removed: Number of logically removed nodes observed during traversal. * @split_count_after: Sample the node count split-counter after traversal. + * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ @@ -198,16 +191,22 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, /* * cds_lfht_lookup - lookup a node by key. + * @ht: the hash table. + * @match: the key match function. + * @hash: the key hash. + * @iter: Node, if found (output). *iter->node set to NULL if not found. * - * Output in "*iter". *iter->node set to NULL if not found. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, - struct cds_lfht_iter *iter); +void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match, + unsigned long hash, void *key, struct cds_lfht_iter *iter); /* * cds_lfht_next_duplicate - get the next item with same key (after a lookup). + * @ht: the hash table. + * @match: the key match function. + * @iter: Node, if found (output). *iter->node set to NULL if not found. * * Uses an iterator initialized by a lookup. * Sets *iter-node to the following node with same key. @@ -218,10 +217,13 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ -void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter); +void cds_lfht_next_duplicate(struct cds_lfht *ht, + cds_lfht_match_fct match, struct cds_lfht_iter *iter); /* * cds_lfht_first - get the first node in the table. + * @ht: the hash table. + * @iter: First node, if exists (output). *iter->node set to NULL if not found. * * Output in "*iter". *iter->node set to NULL if table is empty. * Call with rcu_read_lock held. @@ -231,6 +233,8 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_next - get the next node in the table. + * @ht: the hash table. + * @iter: Next node, if exists (output). *iter->node set to NULL if not found. * * Input/Output in "*iter". *iter->node set to NULL if *iter was * pointing to the last table node. @@ -241,15 +245,22 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_add - add a node to the hash table. + * @ht: the hash table. + * @hash: the key hash. + * @node: the node to add. * * This function supports adding redundant keys into the table. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ -void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node); +void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, + struct cds_lfht_node *node); /* * cds_lfht_add_unique - add a node to hash table, if key is not present. + * @ht: the hash table. + * @match: the key match function. + * @node: the node to try adding. * * Return the node added upon success. * Return the unique node already present upon failure. If @@ -264,10 +275,15 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node); * add_unique and add_replace (see below). */ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, + cds_lfht_match_fct match, + unsigned long hash, struct cds_lfht_node *node); /* * cds_lfht_add_replace - replace or add a node within hash table. + * @ht: the hash table. + * @match: the key match function. + * @node: the node to add. * * Return the node replaced upon success. If no node matching the key * was present, return NULL, which also means the operation succeeded. @@ -288,10 +304,15 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, * will never generate duplicated keys. */ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, + cds_lfht_match_fct match, + unsigned long hash, struct cds_lfht_node *node); /* * cds_lfht_replace - replace a node pointer to by iter within hash table. + * @ht: the hash table. + * @old_iter: the iterator position of the node to replace. + * @now_node: the new node to try using for replacement. * * Return 0 if replacement is successful, negative value otherwise. * Replacing a NULL old node or an already removed node will fail with a @@ -319,6 +340,8 @@ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, /* * cds_lfht_del - remove node pointed to by iterator from hash table. + * @ht: the hash table. + * @iter: the iterator position of the node to delete. * * Return 0 if the node is successfully removed, negative value * otherwise. @@ -337,6 +360,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_resize - Force a hash table resize + * @ht: the hash table. * @new_size: update to this hash table size. * * Threads calling this API need to be registered RCU read-side threads. -- 2.34.1