aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorDamian Gryski <[email protected]>2022-04-09 18:59:44 -0700
committerRon Evans <[email protected]>2022-04-28 09:14:45 +0200
commit1abe1203a3aea06754bcbe9a31673dc76792ccf0 (patch)
treed3d22c21ce42c77147a191bc10f722d77ac21684
parent8b360ec911d283bed3bd816f0d360bbf67b10588 (diff)
downloadtinygo-1abe1203a3aea06754bcbe9a31673dc76792ccf0.tar.gz
tinygo-1abe1203a3aea06754bcbe9a31673dc76792ccf0.zip
src/runtime: make hashmap calculations more uintptr-size independent
-rw-r--r--src/runtime/hashmap.go33
1 files changed, 14 insertions, 19 deletions
diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go
index 5dab4ae56..5c9daa47a 100644
--- a/src/runtime/hashmap.go
+++ b/src/runtime/hashmap.go
@@ -109,27 +109,22 @@ func hashmapKeyHashAlg(alg hashmapAlgorithm) func(key unsafe.Pointer, n uintptr)
}
func hashmapShouldGrow(m *hashmap) bool {
- // with 29 bucket bits, we have potentially 8*(1 << 29) == 2^32 elements
- if m.bucketBits <= 29 {
- // "maximum" number of elements is 0.75 * buckets * elements per bucket
- // to avoid overflow, this is calculated as
- // max = 3 * (1/4 * buckets * elements per bucket)
- // = 3 * (buckets * (elements per bucket)/4)
- // = 3 * (buckets * (8/4)
- // = 3 * (buckets * 2)
- // = 6 * buckets
- max := (uintptr(6) << m.bucketBits)
- return m.count > max
- }
-
- if m.bucketBits == 30 && m.count > uintptr(0xe0000000) {
- return true
+ if m.bucketBits > uint8((unsafe.Sizeof(uintptr(0))*8)-3) {
+ // Over this limit, we're likely to overflow uintptrs during calculations
+ // or numbers of hash elements. Don't allow any more growth.
+ // With 29 bits, this is 2^32 elements anyway.
+ return false
}
- // bucketBits == 32 will cause overflow problems on 32-bit platforms, so we limit it to 31.
- // We're also likely to overflow the `int`-sized map length, causing other issues.
-
- return false
+ // "maximum" number of elements is 0.75 * buckets * elements per bucket
+ // to avoid overflow, this is calculated as
+ // max = 3 * (1/4 * buckets * elements per bucket)
+ // = 3 * (buckets * (elements per bucket)/4)
+ // = 3 * (buckets * (8/4)
+ // = 3 * (buckets * 2)
+ // = 6 * buckets
+ max := (uintptr(6) << m.bucketBits)
+ return m.count > max
}
// Return the number of entries in this hashmap, called from the len builtin.