[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> It seems that the testing patches have a strange problem, please wait
> before merge it.

Hi Lai,

I'm still waiting to hear from you before pulling the testing patches.
One thought that occurs to me is that we should probably create a second
hash table test program alongside with the existing one.

The test program currently in the tree can also be used as an example of
how to use the hash table. The modifications you bring are interesting
for testing subtle corner-cases, but these transform the test program in
a synthetic workload that cannot be used as a usage example.

So, what are your thoughts about creating a second hash table test
program ? It can very well be derived from a copy of test_urcu_hash, no
problem there. We could event rename the current test_urcu_hash into
example_urcu_hash.c ?

Thanks,

Mathieu

> 
> Thanks,
> Lai
> 
> On 11/14/2011 12:50 PM, Lai Jiangshan wrote:
> > Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> > ---
> >  rculfhash.c      |   24 +++++++++++++++++++++++-
> >  urcu/rculfhash.h |   14 ++++++++++++++
> >  2 files changed, 37 insertions(+), 1 deletions(-)
> > 
> > diff --git a/rculfhash.c b/rculfhash.c
> > index cbfc79e..70f5863 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -1495,12 +1495,34 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  {
> >  	unsigned long size;
> >  
> > -	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> >  	size = rcu_dereference(ht->t.size);
> >  	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
> >  	ht_count_add(ht, size, hash);
> >  }
> >  
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		unsigned long hash, struct cds_lfht_node *node)
> > +{
> > +	struct cds_lfht_node *new_node;
> > +
> > +	if (caa_unlikely(is_removed(iter->next)))
> > +		return false;
> > +
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> > +	node->next = clear_flag(iter->next);
> > +	if (is_bucket(iter->next))
> > +		new_node = flag_bucket(node);
> > +	else
> > +		new_node = node;
> > +	if (uatomic_cmpxchg(&iter->node->next, iter->next,
> > +			new_node) != iter->next)
> > +		return false;
> > +
> > +	ht_count_add(ht, rcu_dereference(ht->t.size), hash);
> > +	return true;
> > +}
> > +
> >  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> >  				unsigned long hash,
> >  				cds_lfht_match_fct match,
> > diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> > index 7d919d0..0f9bf44 100644
> > --- a/urcu/rculfhash.h
> > +++ b/urcu/rculfhash.h
> > @@ -250,6 +250,20 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  		struct cds_lfht_node *node);
> >  
> >  /*
> > + * cds_lfht_add_at - add a node to the hash table at the specified place.
> > + * @ht: the hash table.
> > + * @iter: the specified place to insert
> > + * @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.
> > + */
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		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.
> >   * @hash: the node's hash.
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com