postgres.git / summary / log / commit / refs

commit    4873da79da4bbd54f580ca6e5b2f5c46ae6e4bc6
Author:   David Rowley <drowley@postgresql.org>
Date:     Fri Aug 13 04:42:35 2021 +0000
First released in: 15.0, 10.19, 11.14, 12.9, 13.5, 14.0

    Fix incorrect hash table resizing code in simplehash.h
    
    This fixes a bug in simplehash.h which caused an incorrect size mask to be
    used when the hash table grew to SH_MAX_SIZE (2^32).  The code was
    incorrectly setting the size mask to 0 when the hash tables reached the
    maximum possible number of buckets.  This would result always trying to
    use the 0th bucket causing an  infinite loop of trying to grow the hash
    table due to there being too many collisions.
    
    Seemingly it's not that common for simplehash tables to ever grow this big
    as this bug dates back to v10 and nobody seems to have noticed it before.
    However, probably the most likely place that people would notice it would
    be doing a large in-memory Hash Aggregate with something close to at least
    2^31 groups.
    
    After this fix, the code now works correctly with up to within 98% of 2^32
    groups and will fail with the following error when trying to insert any
    more items into the hash table:
    
    ERROR:  hash table size exceeded
    
    However, the work_mem (or hash_mem_multiplier in newer versions) settings
    will generally cause Hash Aggregates to spill to disk long before reaching
    that many groups.  The minimal test case I did took a work_mem setting of
    over 192GB to hit the bug.
    
    simplehash hash tables are used in a few other places such as Bitmap Index
    Scans, however, again the size that the hash table can become there is
    also limited to work_mem and it would take a relation of around 16TB
    (2^31) pages and a very large work_mem setting to hit this.  With smaller
    work_mem values the table would become lossy and never grow large enough
    to hit the problem.
    
    Author: Yura Sokolov
    Reviewed-by: David Rowley, Ranier Vilela
    Discussion: https://postgr.es/m/b1f7f32737c3438136f64b26f4852b96@postgrespro.ru
    Backpatch-through: 10, where simplehash.h was added


 src/include/lib/simplehash.h | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)

diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 90dfa8a695d..3d3273a6bbb 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -156,7 +156,7 @@ SH_SCOPE	SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
 #endif
 SH_SCOPE void SH_DESTROY(SH_TYPE * tb);
 SH_SCOPE void SH_RESET(SH_TYPE * tb);
-SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize);
+SH_SCOPE void SH_GROW(SH_TYPE * tb, uint64 newsize);
 SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);
 SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
 											uint32 hash, bool *found);
@@ -232,7 +232,7 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
  * the hashtable.
  */
 static inline void
-SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
+SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint64 newsize)
 {
 	uint64		size;
 
@@ -252,11 +252,7 @@ SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
 
 	/* now set size */
 	tb->size = size;
-
-	if (tb->size == SH_MAX_SIZE)
-		tb->sizemask = 0;
-	else
-		tb->sizemask = tb->size - 1;
+	tb->sizemask = (uint32) (size - 1);
 
 	/*
 	 * Compute the next threshold at which we need to grow the hash table
@@ -406,7 +402,7 @@ SH_RESET(SH_TYPE * tb)
  * performance-wise, when known at some point.
  */
 SH_SCOPE void
-SH_GROW(SH_TYPE * tb, uint32 newsize)
+SH_GROW(SH_TYPE * tb, uint64 newsize)
 {
 	uint64		oldsize = tb->size;
 	SH_ELEMENT_TYPE *olddata = tb->data;


[parent: 2c6275423535]