[lttng-dev] [PATCH lttng-tools] Fix: hash table growth (for small tables) should be limited

[lttng-dev] [PATCH lttng-tools] Fix: hash table growth (for small tables) should be limited

[Mathieu Desnoyers]

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 <mathieu.desnoyers at efficios.com>
---
diff --git a/src/common/hashtable/rculfhash.c b/src/common/hashtable/rculfhash.c
index b430a3d..eeb5c43 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

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

[lttng-dev] [PATCH lttng-tools] Fix: hash table growth (for small tables) should be limited (v2)

[Mathieu Desnoyers]

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 <mathieu.desnoyers at efficios.com>
---
diff --git a/src/common/hashtable/rculfhash.c b/src/common/hashtable/rculfhash.c
index b430a3d..ebdc4ff 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

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

[lttng-dev] [PATCH lttng-tools] Fix: hash table growth (for small tables) should be limited (v2)

[David Goulet]

Merged!

Mathieu Desnoyers:
> 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 <mathieu.desnoyers at efficios.com>
> ---
> diff --git a/src/common/hashtable/rculfhash.c b/src/common/hashtable/rculfhash.c
> index b430a3d..ebdc4ff 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
>