merged as:
commit 89bb121d8cea974a8b6927499d917620236b7fee
Author: Lai Jiangshan <[email protected]>
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 <[email protected]>
Signed-off-by: Mathieu Desnoyers <[email protected]>
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
_______________________________________________
ltt-dev mailing list
[email protected]
http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
