[ltt-dev] [PATCH 5/9] rculfhash: avoid unneed garbage collect

[Mathieu Desnoyers]

* 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