[ltt-dev] [PATCH 8/9] add duplicated node test

[Lai Jiangshan]

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
>>
>