[ltt-dev] [PATCH 4/6] rculfhash: Change lazy shrink strategy

[Mathieu Desnoyers]

merged as:

commit 89bb121d8cea974a8b6927499d917620236b7fee
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Wed Nov 2 11:31:14 2011 -0400

    rculfhash: Change lazy shrink strategy
    
    We can aggressively grow a ht,
    but we should conservatively shrink a ht.
    
    When we try to shrink the ht after a deletion,
    but if a growing is required after it, we should
    stop this shrink.
    
    But it is more complicated to implement it, so we use more
    conservative strategy to shrink a ht to gain simple code:
    
    We stop to (lazy) shrink when we found growing is
    in progress.
    
    [ Edit by Mathieu Desnoyers: Add documentation, cleanup. ]
    
    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 ce7197a..600feec 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1827,13 +1827,36 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
 	__cds_lfht_resize_lazy_launch(ht);
 }
 
+/*
+ * We favor grow operations over shrink. A shrink operation never occurs
+ * if a grow operation is queued for lazy execution. A grow operation
+ * cancels any pending shrink lazy execution.
+ */
 static
 void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 				unsigned long count)
 {
 	if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
 		return;
-
-	resize_target_update_count(ht, count);
+	count = max(count, ht->min_alloc_size);
+	if (count == size)
+		return;		/* Already the right size, no resize needed */
+	if (count > size) {	/* lazy grow */
+		if (resize_target_grow(ht, count) >= count)
+			return;
+	} else {		/* lazy shrink */
+		for (;;) {
+			unsigned long s;
+
+			s = uatomic_cmpxchg(&ht->t.resize_target, size, count);
+			if (s == size)
+				break;	/* no resize needed */
+			if (s > size)
+				return;	/* growing is/(was just) in progress */
+			if (s <= count)
+				return;	/* some other thread do shrink */
+			size = s;
+		}
+	}
 	__cds_lfht_resize_lazy_launch(ht);
 }

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