From 89bb121d8cea974a8b6927499d917620236b7fee Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Wed, 2 Nov 2011 11:31:14 -0400 Subject: [PATCH] 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 Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 27 +++++++++++++++++++++++++-- 1 file changed, 25 insertions(+), 2 deletions(-) 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); } -- 2.34.1