[ltt-dev] [PATCH 8/9] add duplicated node test
Lai Jiangshan
laijs at cn.fujitsu.com
Wed Nov 16 04:16:22 EST 2011
On 11/15/2011 07:31 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>> tests/test_urcu_hash.c | 12 ++++++++++++
>> 1 files changed, 12 insertions(+), 0 deletions(-)
>>
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index 3730c2b..964a4e1 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -111,6 +111,7 @@ struct test_data {
>> struct lfht_test_node {
>> struct cds_lfht_node node;
>> unsigned long hash;
>> + unsigned long dup;
>> unsigned long orig_hash;
>> /* cache-cold for iteration */
>> struct rcu_head head;
>> @@ -406,6 +407,8 @@ void lfht_test_node_init(struct lfht_test_node *node)
>> cds_lfht_next(test_ht, &iter);
>> if (iter.node)
>> hash = to_test_node(iter.node)->orig_hash;
>> +
>> + node->dup = test_rand_get_bits(2);
>> }
>>
>> node->orig_hash = hash;
>> @@ -427,6 +430,15 @@ void lfht_test_node_init(struct lfht_test_node *node)
>> static
>> int test_match(struct cds_lfht_node *node, void *key)
>> {
>> + struct lfht_test_node *u = to_test_node(node), *v = key;
>> +
>> + if (caa_likely(u->hash != v->hash))
>> + return 0;
>> +
>> + /* 56.25% (100% * 9 / 16) duplicated when hash value are the same */
>> + if (u->dup && u->dup == v->dup)
>> + return 1;
>
> Oh, I see, so you use a flag in the node to specify if it is duplicated.
> This is twisted ;)
>
> Hrm, but cds_lfht_next_duplicate needs to follow next pointers to get
> the duplicates, so I don't see how this approach works with the
> rculfhash code.
this new test_match() has:
any a: test_match(a, a) (*)
any a, b: test_match(a, b) -> test_match(b, a)
any a, b, c: test_match(a, b) && test_match(b, c) -> test_match(a, c)
So it is a correct code.
((*) The last line of test_match() should be "return u == v",
but in the code we don't use test_match(a, a), so we don't handle it)
>
> It might be simpler to just create a physical duplicate and add it to
> the table rather than this flag scheme.
User define the definition of the "node duplicate".
raw fingerprints of a finger are not physical duplicate, but they can "match"
with each other.
> This would end up testing the
> normal use of the table rather than a use-case nobody will use in
> practice.
I try to hide the key for test, it is already a use-case nobody will use in practice.
But I think:
We can just focus on the hash value, not the key:
Easy add types of the nodes.
make test flexible.
avoid test only any selected hash function.
Thanks,
Lai
>
> Thanks,
>
> Mathieu
>
>> +
>> return 0;
>> }
>>
>> --
>> 1.7.4.4
>>
>
More information about the lttng-dev
mailing list