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@cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index ce7197aa822b53510ca9fe58822e47563f11ccdf..600feecfa8f4f8230eede1683cf79cff14a0333f 100644 (file)
--- 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);
 }