[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Fri Nov 4 06:08:23 EDT 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> We use hash value to determine the range of the object
> >> and use cds_lfht_lookup_fct to lookup them.
> >>
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >> rculfhash.c | 8 ++++----
> >> tests/test_urcu_hash.c | 25 ++++++++++++++++++++++---
> >> urcu/rculfhash.h | 4 +++-
> >> 3 files changed, 29 insertions(+), 8 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index d1a1766..29054cd 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -1391,14 +1391,14 @@ 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,
> >> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >> + cds_lfht_lookup_fct match, void *arg,
> >
> > arg -> key ?
> >
> > for "match", our approach is to provide this function as parameter to
> > cds_lfht_new rather than pass it as parameter each time a lookup is
> > performed. What is the reason why we should pass it here as a parameter?
> >
>
> Allow the user define it.
> In the test, I pass match = a function always returns true when need,
> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.
This looks like an interesting debug and testing feature, but I don't
really see why we should complicate the API to include this. Is there a
real-life use-case you have in mind besides testing ?
If we only need this for testing, we can use a static variable in the
test program to influence the behavior of cds_lfht_test_lookup.
The other patches look fine, I'm just concerned about this one because
it adds complexity to the API which does not seem useful to end-users.
Thanks!
Mathieu
>
> thanks,
> lai
>
>
> >
> >> 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);
> >> @@ -1421,7 +1421,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, arg))) {
> >> break;
> >> }
> >> node = clear_flag(next);
> >> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> >> index e28c14a..4c45573 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,23 @@ 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_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",
> >> @@ -479,7 +498,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);
> >> @@ -574,7 +593,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);
> >> @@ -932,7 +951,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,
> >> + test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
> >> init_hash_size, min_hash_alloc_size,
> >> (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
> >> CDS_LFHT_ACCOUNTING, NULL);
> >> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> >> index f4f3373..b56fe56 100644
> >> --- a/urcu/rculfhash.h
> >> +++ b/urcu/rculfhash.h
> >> @@ -86,6 +86,7 @@ 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_lookup_fct)(struct cds_lfht_node *node, void *arg);
> >>
> >> /*
> >> * cds_lfht_node_init - initialize a hash table node
> >> @@ -203,7 +204,8 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
> >> * 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,
> >> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >> + cds_lfht_lookup_fct match, void *arg,
> >> struct cds_lfht_iter *iter);
> >>
> >> /*
> >> --
> >> 1.7.4.4
> >>
> >
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list