From 9d8ad8e29d1f50e6a33c0e9a644c50b5e90364d2 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 27 Aug 2013 18:11:04 -0400 Subject: [PATCH] Fix: hash table growth (for small tables) should be limited (v2) Buckets with many entries encountered in a hash table could cause it to grow to a large size, beyond the scope for which this mechanism is expected to play a role when node accounting is available. Indeed, when the hash table grows to larger size, split-counter node accounting is expected to deal with resize/shrink rather than relying on an heuristic based on the largest bucket size. This is fixing an issue where we see hash tables sometimes reaching 65k entries index (65536*8 = 524288 bytes) for a workload limited to adding 1000 entries and then removing all of them, done in a loop (random keys). Signed-off-by: Mathieu Desnoyers Signed-off-by: David Goulet --- src/common/hashtable/rculfhash.c | 29 ++++++++++++++++++++++++++--- 1 file changed, 26 insertions(+), 3 deletions(-) diff --git a/src/common/hashtable/rculfhash.c b/src/common/hashtable/rculfhash.c index b430a3dec..ebdc4ffaa 100644 --- a/src/common/hashtable/rculfhash.c +++ b/src/common/hashtable/rculfhash.c @@ -726,9 +726,32 @@ void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len) if (chain_len > 100) dbg_printf("WARNING: large chain length: %u.\n", chain_len); - if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) - cds_lfht_resize_lazy_grow(ht, size, - cds_lfht_get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1))); + if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) { + int growth; + + /* + * Ideal growth calculated based on chain length. + */ + growth = cds_lfht_get_count_order_u32(chain_len + - (CHAIN_LEN_TARGET - 1)); + if ((ht->flags & CDS_LFHT_ACCOUNTING) + && (size << growth) >= (1UL << COUNT_COMMIT_ORDER)) { + /* + * If ideal growth expands the hash table size + * beyond the "small hash table" sizes, use the + * maximum small hash table size to attempt + * expanding the hash table. This only applies + * when node accounting is available, otherwise + * the chain length is used to expand the hash + * table in every case. + */ + growth = COUNT_COMMIT_ORDER - + cds_lfht_get_count_order_u32(size); + if (growth <= 0) + return; + } + cds_lfht_resize_lazy_grow(ht, size, growth); + } } static -- 2.34.1