[ltt-dev] [PATCH 5/9] rculfhash: avoid unneed garbage collect
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Mon Oct 17 12:15:23 EDT 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Your added comments is a bit strange for me.
>
> adding thread has no responsibility to do gc except it is prevented from
> "removed" nodes.
The "add" thread can never link its node after a logically removed node:
it performs gc when it sees that this kind of situation would need to
happen.
> it is totally no responsibility to do gc when it successfully adds the node.
>
> and adding thread does not break any thing which harm to the del-ing thread.
This is true because of the way the insertion thread can never cause the
gargage collection of the deletion thread to fail to find the deleted
node it needs to gargage collect.
So I agree with you that the gc'ing is not needed after addition, but
only because we never insert a node within a bucket without having
previously gc'd the bucket from the bucket start up to to the insert
position.
It is very important that no situation can cause the delete to return
while the logically deleted node is still linked in the linked list.
For instance, if the "add" thread could ever add a node with a reverse
hash higher than the logically removed node in a position prior to the
removed node, this would cause the gargage collection to fail to find
the logically removed node. But the way insertion is performed ensures
this scenario never happens, so we should be good.
Thanks,
Mathieu
>
> Thanks,
> Lai
>
> On 10/17/2011 10:07 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >> rculfhash.c | 8 ++------
> >> 1 files changed, 2 insertions(+), 6 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index 1c859ed..f901ded 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -850,7 +850,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> >> enum add_mode mode, int dummy)
> >> {
> >> struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
> >> - *dummy_node, *return_node;
> >> + *return_node;
> >> struct _cds_lfht_node *lookup;
> >>
> >> assert(!is_dummy(node));
> >> @@ -919,7 +919,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> >> return_node = NULL;
> >> else /* ADD_DEFAULT and ADD_UNIQUE */
> >> return_node = node;
> >> - goto gc_end;
> >> + goto end;
> >> }
> >>
> >> replace:
> >> @@ -941,10 +941,6 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> >> (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
> >> /* retry */
> >> }
> >> -gc_end:
> >> - /* Garbage collect logically removed nodes in the bucket */
> >> - dummy_node = (struct cds_lfht_node *) lookup;
> >> - _cds_lfht_gc_bucket(dummy_node, node);
> >
> > If we have a concurrent removal executing while the add is performed,
> > I just want to ensure we agree that this scenario will be correct:
> >
> > 1) removal succeeds. We have flagged
> > a node as "logically removed", but
> > it is still in the linked list.
> >
> > 2) garbage collection is initiated.
> >
> > 3) add succeeds. We insert a
> > node with reverse hash value
> > higher than the logically
> > removed node. This means the
> > add takes care of garbage
> > collecting the logically
> > removed node prior to adding
> > the new node.
> >
> > 4) garbage collection of logically
> > removed node fails
> > (we ignore the return value of
> > (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);)
> > retry and iterate until we find the reverse
> > hash value higher than the logically
> > remove node.
> >
> > So I think this is OK: given that the add path takes care of garbage
> > collecting any logically removed node located prior to the insert
> > position, we don't need to perform gargage collection after insertion.
> >
> > Merged as:
> >
> >
> > commit 960c9e4ff8e6028f5a0d4b1c1d747b20f08c5177
> > Author: Lai Jiangshan <laijs at cn.fujitsu.com>
> > Date: Mon Oct 17 10:10:27 2011 -0400
> >
> > rculfhash: avoid unneed garbage collect
> >
> > [ Edit by Mathieu Desnoyers:
> >
> > If we have a concurrent removal executing while the add is performed,
> > I just want to ensure we agree that this scenario will be correct:
> >
> > 1) removal succeeds. We have flagged
> > a node as "logically removed", but
> > it is still in the linked list.
> >
> > 2) garbage collection is initiated.
> >
> > 3) add succeeds. We insert a
> > node with reverse hash value
> > higher than the logically
> > removed node. This means the
> > add takes care of garbage
> > collecting the logically
> > removed node prior to adding
> > the new node.
> >
> > 4) garbage collection of logically
> > removed node fails
> > (we ignore the return value of
> > (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);)
> > retry and iterate until we find the reverse
> > hash value higher than the logically
> > remove node.
> >
> > So I think this is OK: given that the add path takes care of garbage
> > collecting any logically removed node located prior to the insert
> > position, we don't need to perform gargage collection after the
> > insertion. ]
> >
> > Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> >
> > diff --git a/rculfhash.c b/rculfhash.c
> > index c7b9ea8..d733d6b 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -855,7 +855,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > enum add_mode mode, int dummy)
> > {
> > struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
> > - *dummy_node, *return_node;
> > + *return_node;
> > struct _cds_lfht_node *lookup;
> >
> > assert(!is_dummy(node));
> > @@ -924,7 +924,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > return_node = NULL;
> > else /* ADD_DEFAULT and ADD_UNIQUE */
> > return_node = node;
> > - goto gc_end;
> > + goto end;
> > }
> >
> > replace:
> > @@ -946,10 +946,6 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
> > /* retry */
> > }
> > -gc_end:
> > - /* Garbage collect logically removed nodes in the bucket */
> > - dummy_node = (struct cds_lfht_node *) lookup;
> > - _cds_lfht_gc_bucket(dummy_node, node);
> > end:
> > return return_node;
> > }
> >
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list