diff options
| author | Michael Pratt <mpratt@google.com> | 2025-07-25 15:35:36 -0400 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2025-07-30 11:47:14 -0700 |
| commit | 2ae059ccaf982c3304fae0b48c1d78ad7192cbdd (patch) | |
| tree | dc3fda38ac232193ff6b3978978dc41e9906bbe0 /src/runtime | |
| parent | cc571dab91e73413cf2ba1546a4ba485038cf2d1 (diff) | |
| download | go-2ae059ccaf982c3304fae0b48c1d78ad7192cbdd.tar.xz | |
all: remove GOEXPERIMENT=swissmap
For #54766.
Change-Id: I6a6a636c40b5fe2e8b0d4a5e23933492bc8bb76e
Reviewed-on: https://go-review.googlesource.com/c/go/+/691595
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Diffstat (limited to 'src/runtime')
| -rw-r--r-- | src/runtime/export_map_noswiss_test.go | 64 | ||||
| -rw-r--r-- | src/runtime/export_map_swiss_test.go | 11 | ||||
| -rw-r--r-- | src/runtime/export_test.go | 3 | ||||
| -rw-r--r-- | src/runtime/linkname_shim.go (renamed from src/runtime/linkname_swiss.go) | 7 | ||||
| -rw-r--r-- | src/runtime/map.go (renamed from src/runtime/map_swiss.go) | 20 | ||||
| -rw-r--r-- | src/runtime/map_fast32.go (renamed from src/runtime/map_fast32_swiss.go) | 2 | ||||
| -rw-r--r-- | src/runtime/map_fast32_noswiss.go | 493 | ||||
| -rw-r--r-- | src/runtime/map_fast64.go (renamed from src/runtime/map_fast64_swiss.go) | 2 | ||||
| -rw-r--r-- | src/runtime/map_fast64_noswiss.go | 502 | ||||
| -rw-r--r-- | src/runtime/map_faststr.go (renamed from src/runtime/map_faststr_swiss.go) | 2 | ||||
| -rw-r--r-- | src/runtime/map_faststr_noswiss.go | 507 | ||||
| -rw-r--r-- | src/runtime/map_noswiss.go | 1891 | ||||
| -rw-r--r-- | src/runtime/map_noswiss_test.go | 214 | ||||
| -rw-r--r-- | src/runtime/map_swiss_test.go | 75 | ||||
| -rw-r--r-- | src/runtime/map_test.go | 126 | ||||
| -rw-r--r-- | src/runtime/runtime-gdb.py | 41 | ||||
| -rw-r--r-- | src/runtime/runtime-gdb_test.go | 41 | ||||
| -rw-r--r-- | src/runtime/type.go | 10 |
18 files changed, 80 insertions, 3931 deletions
diff --git a/src/runtime/export_map_noswiss_test.go b/src/runtime/export_map_noswiss_test.go deleted file mode 100644 index 4638afa6b8..0000000000 --- a/src/runtime/export_map_noswiss_test.go +++ /dev/null @@ -1,64 +0,0 @@ -// Copyright 2024 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime - -import ( - "internal/abi" - "unsafe" -) - -const RuntimeHmapSize = unsafe.Sizeof(hmap{}) - -func OverLoadFactor(count int, B uint8) bool { - return overLoadFactor(count, B) -} - -func MapBucketsCount(m map[int]int) int { - h := *(**hmap)(unsafe.Pointer(&m)) - return 1 << h.B -} - -func MapBucketsPointerIsNil(m map[int]int) bool { - h := *(**hmap)(unsafe.Pointer(&m)) - return h.buckets == nil -} - -func MapTombstoneCheck(m map[int]int) { - // Make sure emptyOne and emptyRest are distributed correctly. - // We should have a series of filled and emptyOne cells, followed by - // a series of emptyRest cells. - h := *(**hmap)(unsafe.Pointer(&m)) - i := any(m) - t := *(**maptype)(unsafe.Pointer(&i)) - - for x := 0; x < 1<<h.B; x++ { - b0 := (*bmap)(add(h.buckets, uintptr(x)*uintptr(t.BucketSize))) - n := 0 - for b := b0; b != nil; b = b.overflow(t) { - for i := 0; i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != emptyRest { - n++ - } - } - } - k := 0 - for b := b0; b != nil; b = b.overflow(t) { - for i := 0; i < abi.OldMapBucketCount; i++ { - if k < n && b.tophash[i] == emptyRest { - panic("early emptyRest") - } - if k >= n && b.tophash[i] != emptyRest { - panic("late non-emptyRest") - } - if k == n-1 && b.tophash[i] == emptyOne { - panic("last non-emptyRest entry is emptyOne") - } - k++ - } - } - } -} diff --git a/src/runtime/export_map_swiss_test.go b/src/runtime/export_map_swiss_test.go deleted file mode 100644 index 55a7d6ff04..0000000000 --- a/src/runtime/export_map_swiss_test.go +++ /dev/null @@ -1,11 +0,0 @@ -// Copyright 2024 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build goexperiment.swissmap - -package runtime - -func MapTombstoneCheck(m map[int]int) { - // TODO -} diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go index 3af1362ee2..fa30efccb1 100644 --- a/src/runtime/export_test.go +++ b/src/runtime/export_test.go @@ -59,9 +59,6 @@ const CrashStackImplemented = crashStackImplemented const TracebackInnerFrames = tracebackInnerFrames const TracebackOuterFrames = tracebackOuterFrames -var MapKeys = keys -var MapValues = values - var LockPartialOrder = lockPartialOrder type TimeTimer = timeTimer diff --git a/src/runtime/linkname_swiss.go b/src/runtime/linkname_shim.go index 1be724477e..0ceff2b16c 100644 --- a/src/runtime/linkname_swiss.go +++ b/src/runtime/linkname_shim.go @@ -2,8 +2,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build goexperiment.swissmap - package runtime import ( @@ -16,8 +14,7 @@ import ( // Legacy //go:linkname compatibility shims // // The functions below are unused by the toolchain, and exist only for -// compatibility with existing //go:linkname use in the ecosystem (and in -// map_noswiss.go for normal use via GOEXPERIMENT=noswissmap). +// compatibility with existing //go:linkname use in the ecosystem. // linknameIter is the it argument to mapiterinit and mapiternext. // @@ -27,7 +24,7 @@ import ( // type hiter struct { // key unsafe.Pointer // elem unsafe.Pointer -// t *maptype +// t *maptype // old map abi.Type // h *hmap // buckets unsafe.Pointer // bptr *bmap diff --git a/src/runtime/map_swiss.go b/src/runtime/map.go index c2cf08fcaa..facf86e494 100644 --- a/src/runtime/map_swiss.go +++ b/src/runtime/map.go @@ -2,8 +2,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build goexperiment.swissmap - package runtime import ( @@ -19,8 +17,6 @@ const ( loadFactorDen = 8 ) -type maptype = abi.SwissMapType - //go:linkname maps_errNilAssign internal/runtime/maps.errNilAssign var maps_errNilAssign error = plainError("assignment to entry in nil map") @@ -331,19 +327,3 @@ func mapclone(m any) any { e.data = (unsafe.Pointer)(map_) return m } - -// keys for implementing maps.keys -// -//go:linkname keys maps.keys -func keys(m any, p unsafe.Pointer) { - // Currently unused in the maps package. - panic("unimplemented") -} - -// values for implementing maps.values -// -//go:linkname values maps.values -func values(m any, p unsafe.Pointer) { - // Currently unused in the maps package. - panic("unimplemented") -} diff --git a/src/runtime/map_fast32_swiss.go b/src/runtime/map_fast32.go index 0a241d3793..8b460edf77 100644 --- a/src/runtime/map_fast32_swiss.go +++ b/src/runtime/map_fast32.go @@ -2,8 +2,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build goexperiment.swissmap - package runtime import ( diff --git a/src/runtime/map_fast32_noswiss.go b/src/runtime/map_fast32_noswiss.go deleted file mode 100644 index 751717b6cd..0000000000 --- a/src/runtime/map_fast32_noswiss.go +++ /dev/null @@ -1,493 +0,0 @@ -// Copyright 2018 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime - -import ( - "internal/abi" - "internal/goarch" - "internal/runtime/sys" - "unsafe" -) - -func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess1_fast32)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - m := bucketMask(h.B) - b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -// mapaccess2_fast32 should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapaccess2_fast32 -func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess2_fast32)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - m := bucketMask(h.B) - b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -// mapassign_fast32 should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign_fast32 -func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapassign_fast32)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapassign. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if isEmpty(b.tophash[i]) { - if insertb == nil { - inserti = i - insertb = b - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4))) - if k != key { - continue - } - inserti = i - insertb = b - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) - // store new key at insert position - *(*uint32)(insertk) = key - - h.count++ - -done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*4+inserti*uintptr(t.ValueSize)) - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - return elem -} - -// mapassign_fast32ptr should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign_fast32ptr -func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapassign_fast32)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapassign. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if isEmpty(b.tophash[i]) { - if insertb == nil { - inserti = i - insertb = b - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4))) - if k != key { - continue - } - inserti = i - insertb = b - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) - // store new key at insert position - *(*unsafe.Pointer)(insertk) = key - - h.count++ - -done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*4+inserti*uintptr(t.ValueSize)) - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - return elem -} - -func mapdelete_fast32(t *maptype, h *hmap, key uint32) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapdelete_fast32)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapdelete - h.flags ^= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - bOrig := b -search: - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { - if key != *(*uint32)(k) || isEmpty(b.tophash[i]) { - continue - } - // Only clear key if there are pointers in it. - // This can only happen if pointers are 32 bit - // wide as 64 bit pointers do not fit into a 32 bit key. - if goarch.PtrSize == 4 && t.Key.Pointers() { - // The key must be a pointer as we checked pointers are - // 32 bits wide and the key is 32 bits wide also. - *(*unsafe.Pointer)(k) = nil - } - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)) - if t.Elem.Pointers() { - memclrHasPointers(e, t.Elem.Size_) - } else { - memclrNoHeapPointers(e, t.Elem.Size_) - } - b.tophash[i] = emptyOne - // If the bucket now ends in a bunch of emptyOne states, - // change those to emptyRest states. - if i == abi.OldMapBucketCount-1 { - if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { - goto notLast - } - } else { - if b.tophash[i+1] != emptyRest { - goto notLast - } - } - for { - b.tophash[i] = emptyRest - if i == 0 { - if b == bOrig { - break // beginning of initial bucket, we're done. - } - // Find previous bucket, continue at its last entry. - c := b - for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { - } - i = abi.OldMapBucketCount - 1 - } else { - i-- - } - if b.tophash[i] != emptyOne { - break - } - } - notLast: - h.count-- - // Reset the hash seed to make it more difficult for attackers to - // repeatedly trigger hash collisions. See issue 25237. - if h.count == 0 { - h.hash0 = uint32(rand()) - } - break search - } - } - - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting -} - -func growWork_fast32(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_fast32(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_fast32(t, h, h.nevacuate) - } -} - -func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.OldMapBucketCount*4) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.OldMapBucketCount*4) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.OldMapBucketCount*4) - for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 4), add(e, uintptr(t.ValueSize)) { - top := b.tophash[i] - if isEmpty(top) { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/elem to bucket x or bucket y). - hash := t.Hasher(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == abi.OldMapBucketCount { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.OldMapBucketCount*4) - } - dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - if goarch.PtrSize == 4 && t.Key.Pointers() && writeBarrier.enabled { - // Write with a write barrier. - *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) - } else { - *(*uint32)(dst.k) = *(*uint32)(k) - } - - typedmemmove(t.Elem, dst.e, e) - dst.i++ - // These updates might push these pointers past the end of the - // key or elem arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 4) - dst.e = add(dst.e, uintptr(t.ValueSize)) - } - } - // Unlink the overflow buckets & clear key/elem to help GC. - if h.flags&oldIterator == 0 && t.Bucket.Pointers() { - b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.BucketSize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} diff --git a/src/runtime/map_fast64_swiss.go b/src/runtime/map_fast64.go index 8b7fcf88e8..5de22a5bea 100644 --- a/src/runtime/map_fast64_swiss.go +++ b/src/runtime/map_fast64.go @@ -2,8 +2,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build goexperiment.swissmap - package runtime import ( diff --git a/src/runtime/map_fast64_noswiss.go b/src/runtime/map_fast64_noswiss.go deleted file mode 100644 index abb272d2b6..0000000000 --- a/src/runtime/map_fast64_noswiss.go +++ /dev/null @@ -1,502 +0,0 @@ -// Copyright 2018 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime - -import ( - "internal/abi" - "internal/goarch" - "internal/runtime/sys" - "unsafe" -) - -func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess1_fast64)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - m := bucketMask(h.B) - b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -// mapaccess2_fast64 should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapaccess2_fast64 -func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess2_fast64)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - m := bucketMask(h.B) - b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -// mapassign_fast64 should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign_fast64 -func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapassign_fast64)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapassign. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if isEmpty(b.tophash[i]) { - if insertb == nil { - insertb = b - inserti = i - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8))) - if k != key { - continue - } - insertb = b - inserti = i - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) - // store new key at insert position - *(*uint64)(insertk) = key - - h.count++ - -done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*8+inserti*uintptr(t.ValueSize)) - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - return elem -} - -// mapassign_fast64ptr should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign_fast64ptr -func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapassign_fast64)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapassign. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if isEmpty(b.tophash[i]) { - if insertb == nil { - insertb = b - inserti = i - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8))) - if k != key { - continue - } - insertb = b - inserti = i - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) - // store new key at insert position - *(*unsafe.Pointer)(insertk) = key - - h.count++ - -done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*8+inserti*uintptr(t.ValueSize)) - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - return elem -} - -func mapdelete_fast64(t *maptype, h *hmap, key uint64) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapdelete_fast64)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - - hash := t.Hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapdelete - h.flags ^= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - bOrig := b -search: - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { - if key != *(*uint64)(k) || isEmpty(b.tophash[i]) { - continue - } - // Only clear key if there are pointers in it. - if t.Key.Pointers() { - if goarch.PtrSize == 8 { - *(*unsafe.Pointer)(k) = nil - } else { - // There are three ways to squeeze at one or more 32 bit pointers into 64 bits. - // Just call memclrHasPointers instead of trying to handle all cases here. - memclrHasPointers(k, 8) - } - } - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)) - if t.Elem.Pointers() { - memclrHasPointers(e, t.Elem.Size_) - } else { - memclrNoHeapPointers(e, t.Elem.Size_) - } - b.tophash[i] = emptyOne - // If the bucket now ends in a bunch of emptyOne states, - // change those to emptyRest states. - if i == abi.OldMapBucketCount-1 { - if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { - goto notLast - } - } else { - if b.tophash[i+1] != emptyRest { - goto notLast - } - } - for { - b.tophash[i] = emptyRest - if i == 0 { - if b == bOrig { - break // beginning of initial bucket, we're done. - } - // Find previous bucket, continue at its last entry. - c := b - for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { - } - i = abi.OldMapBucketCount - 1 - } else { - i-- - } - if b.tophash[i] != emptyOne { - break - } - } - notLast: - h.count-- - // Reset the hash seed to make it more difficult for attackers to - // repeatedly trigger hash collisions. See issue 25237. - if h.count == 0 { - h.hash0 = uint32(rand()) - } - break search - } - } - - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting -} - -func growWork_fast64(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_fast64(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_fast64(t, h, h.nevacuate) - } -} - -func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.OldMapBucketCount*8) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.OldMapBucketCount*8) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.OldMapBucketCount*8) - for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 8), add(e, uintptr(t.ValueSize)) { - top := b.tophash[i] - if isEmpty(top) { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/elem to bucket x or bucket y). - hash := t.Hasher(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == abi.OldMapBucketCount { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.OldMapBucketCount*8) - } - dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - if t.Key.Pointers() && writeBarrier.enabled { - if goarch.PtrSize == 8 { - // Write with a write barrier. - *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) - } else { - // There are three ways to squeeze at least one 32 bit pointer into 64 bits. - // Give up and call typedmemmove. - typedmemmove(t.Key, dst.k, k) - } - } else { - *(*uint64)(dst.k) = *(*uint64)(k) - } - - typedmemmove(t.Elem, dst.e, e) - dst.i++ - // These updates might push these pointers past the end of the - // key or elem arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 8) - dst.e = add(dst.e, uintptr(t.ValueSize)) - } - } - // Unlink the overflow buckets & clear key/elem to help GC. - if h.flags&oldIterator == 0 && t.Bucket.Pointers() { - b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.BucketSize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} diff --git a/src/runtime/map_faststr_swiss.go b/src/runtime/map_faststr.go index 23f6c1e810..ca16a8eab6 100644 --- a/src/runtime/map_faststr_swiss.go +++ b/src/runtime/map_faststr.go @@ -2,8 +2,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -//go:build goexperiment.swissmap - package runtime import ( diff --git a/src/runtime/map_faststr_noswiss.go b/src/runtime/map_faststr_noswiss.go deleted file mode 100644 index e8b6a3f1ae..0000000000 --- a/src/runtime/map_faststr_noswiss.go +++ /dev/null @@ -1,507 +0,0 @@ -// Copyright 2018 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime - -import ( - "internal/abi" - "internal/goarch" - "internal/runtime/sys" - "unsafe" -) - -func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess1_faststr)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - key := stringStructOf(&ky) - if h.B == 0 { - // One-bucket table. - b := (*bmap)(h.buckets) - if key.len < 32 { - // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || isEmpty(b.tophash[i]) { - if b.tophash[i] == emptyRest { - break - } - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) - } - } - return unsafe.Pointer(&zeroVal[0]) - } - // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.OldMapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || isEmpty(b.tophash[i]) { - if b.tophash[i] == emptyRest { - break - } - continue - } - if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) - } - // check first 4 bytes - if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { - continue - } - // check last 4 bytes - if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { - continue - } - if keymaybe != abi.OldMapBucketCount { - // Two keys are potential matches. Use hash to distinguish them. - goto dohash - } - keymaybe = i - } - if keymaybe != abi.OldMapBucketCount { - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) - if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)) - } - } - return unsafe.Pointer(&zeroVal[0]) - } -dohash: - hash := t.Hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -// mapaccess2_faststr should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapaccess2_faststr -func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapaccess2_faststr)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - key := stringStructOf(&ky) - if h.B == 0 { - // One-bucket table. - b := (*bmap)(h.buckets) - if key.len < 32 { - // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || isEmpty(b.tophash[i]) { - if b.tophash[i] == emptyRest { - break - } - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true - } - } - return unsafe.Pointer(&zeroVal[0]), false - } - // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.OldMapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || isEmpty(b.tophash[i]) { - if b.tophash[i] == emptyRest { - break - } - continue - } - if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true - } - // check first 4 bytes - if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { - continue - } - // check last 4 bytes - if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { - continue - } - if keymaybe != abi.OldMapBucketCount { - // Two keys are potential matches. Use hash to distinguish them. - goto dohash - } - keymaybe = i - } - if keymaybe != abi.OldMapBucketCount { - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) - if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)), true - } - } - return unsafe.Pointer(&zeroVal[0]), false - } -dohash: - hash := t.Hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -// mapassign_faststr should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign_faststr -func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapassign_faststr)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - key := stringStructOf(&s) - hash := t.Hasher(noescape(unsafe.Pointer(&s)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapassign. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_faststr(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - top := tophash(hash) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if isEmpty(b.tophash[i]) && insertb == nil { - insertb = b - inserti = i - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*goarch.PtrSize)) - if k.len != key.len { - continue - } - if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { - continue - } - // already have a mapping for key. Update it. - inserti = i - insertb = b - // Overwrite existing key, so it can be garbage collected. - // The size is already guaranteed to be set correctly. - k.str = key.str - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = top // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*goarch.PtrSize) - // store new key at insert position - *((*stringStruct)(insertk)) = *key - h.count++ - -done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+inserti*uintptr(t.ValueSize)) - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - return elem -} - -func mapdelete_faststr(t *maptype, h *hmap, ky string) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racewritepc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapdelete_faststr)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - - key := stringStructOf(&ky) - hash := t.Hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher for consistency with mapdelete - h.flags ^= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_faststr(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - bOrig := b - top := tophash(hash) -search: - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { - continue - } - // Clear key's pointer. - k.str = nil - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) - if t.Elem.Pointers() { - memclrHasPointers(e, t.Elem.Size_) - } else { - memclrNoHeapPointers(e, t.Elem.Size_) - } - b.tophash[i] = emptyOne - // If the bucket now ends in a bunch of emptyOne states, - // change those to emptyRest states. - if i == abi.OldMapBucketCount-1 { - if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { - goto notLast - } - } else { - if b.tophash[i+1] != emptyRest { - goto notLast - } - } - for { - b.tophash[i] = emptyRest - if i == 0 { - if b == bOrig { - break // beginning of initial bucket, we're done. - } - // Find previous bucket, continue at its last entry. - c := b - for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { - } - i = abi.OldMapBucketCount - 1 - } else { - i-- - } - if b.tophash[i] != emptyOne { - break - } - } - notLast: - h.count-- - // Reset the hash seed to make it more difficult for attackers to - // repeatedly trigger hash collisions. See issue 25237. - if h.count == 0 { - h.hash0 = uint32(rand()) - } - break search - } - } - - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting -} - -func growWork_faststr(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_faststr(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_faststr(t, h, h.nevacuate) - } -} - -func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.OldMapBucketCount*2*goarch.PtrSize) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.OldMapBucketCount*2*goarch.PtrSize) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.OldMapBucketCount*2*goarch.PtrSize) - for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 2*goarch.PtrSize), add(e, uintptr(t.ValueSize)) { - top := b.tophash[i] - if isEmpty(top) { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/elem to bucket x or bucket y). - hash := t.Hasher(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == abi.OldMapBucketCount { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.OldMapBucketCount*2*goarch.PtrSize) - } - dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - *(*string)(dst.k) = *(*string)(k) - - typedmemmove(t.Elem, dst.e, e) - dst.i++ - // These updates might push these pointers past the end of the - // key or elem arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 2*goarch.PtrSize) - dst.e = add(dst.e, uintptr(t.ValueSize)) - } - } - // Unlink the overflow buckets & clear key/elem to help GC. - if h.flags&oldIterator == 0 && t.Bucket.Pointers() { - b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.BucketSize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} diff --git a/src/runtime/map_noswiss.go b/src/runtime/map_noswiss.go deleted file mode 100644 index 7b3c98eb88..0000000000 --- a/src/runtime/map_noswiss.go +++ /dev/null @@ -1,1891 +0,0 @@ -// Copyright 2014 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime - -// This file contains the implementation of Go's map type. -// -// A map is just a hash table. The data is arranged -// into an array of buckets. Each bucket contains up to -// 8 key/elem pairs. The low-order bits of the hash are -// used to select a bucket. Each bucket contains a few -// high-order bits of each hash to distinguish the entries -// within a single bucket. -// -// If more than 8 keys hash to a bucket, we chain on -// extra buckets. -// -// When the hashtable grows, we allocate a new array -// of buckets twice as big. Buckets are incrementally -// copied from the old bucket array to the new bucket array. -// -// Map iterators walk through the array of buckets and -// return the keys in walk order (bucket #, then overflow -// chain order, then bucket index). To maintain iteration -// semantics, we never move keys within their bucket (if -// we did, keys might be returned 0 or 2 times). When -// growing the table, iterators remain iterating through the -// old table and must check the new table if the bucket -// they are iterating through has been moved ("evacuated") -// to the new table. - -// Picking loadFactor: too large and we have lots of overflow -// buckets, too small and we waste a lot of space. I wrote -// a simple program to check some stats for different loads: -// (64-bit, 8 byte keys and elems) -// loadFactor %overflow bytes/entry hitprobe missprobe -// 4.00 2.13 20.77 3.00 4.00 -// 4.50 4.05 17.30 3.25 4.50 -// 5.00 6.85 14.77 3.50 5.00 -// 5.50 10.55 12.94 3.75 5.50 -// 6.00 15.27 11.67 4.00 6.00 -// 6.50 20.90 10.79 4.25 6.50 -// 7.00 27.14 10.15 4.50 7.00 -// 7.50 34.03 9.73 4.75 7.50 -// 8.00 41.10 9.40 5.00 8.00 -// -// %overflow = percentage of buckets which have an overflow bucket -// bytes/entry = overhead bytes used per key/elem pair -// hitprobe = # of entries to check when looking up a present key -// missprobe = # of entries to check when looking up an absent key -// -// Keep in mind this data is for maximally loaded tables, i.e. just -// before the table grows. Typical tables will be somewhat less loaded. - -import ( - "internal/abi" - "internal/goarch" - "internal/runtime/atomic" - "internal/runtime/maps" - "internal/runtime/math" - "internal/runtime/sys" - "unsafe" -) - -type maptype = abi.OldMapType - -const ( - // Maximum number of key/elem pairs a bucket can hold. - bucketCntBits = abi.OldMapBucketCountBits - - // Maximum average load of a bucket that triggers growth is bucketCnt*13/16 (about 80% full) - // Because of minimum alignment rules, bucketCnt is known to be at least 8. - // Represent as loadFactorNum/loadFactorDen, to allow integer math. - loadFactorDen = 2 - loadFactorNum = loadFactorDen * abi.OldMapBucketCount * 13 / 16 - - // data offset should be the size of the bmap struct, but needs to be - // aligned correctly. For amd64p32 this means 64-bit alignment - // even though pointers are 32 bit. - dataOffset = unsafe.Offsetof(struct { - b bmap - v int64 - }{}.v) - - // Possible tophash values. We reserve a few possibilities for special marks. - // Each bucket (including its overflow buckets, if any) will have either all or none of its - // entries in the evacuated* states (except during the evacuate() method, which only happens - // during map writes and thus no one else can observe the map during that time). - emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. - emptyOne = 1 // this cell is empty - evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table. - evacuatedY = 3 // same as above, but evacuated to second half of larger table. - evacuatedEmpty = 4 // cell is empty, bucket is evacuated. - minTopHash = 5 // minimum tophash for a normal filled cell. - - // flags - iterator = 1 // there may be an iterator using buckets - oldIterator = 2 // there may be an iterator using oldbuckets - hashWriting = 4 // a goroutine is writing to the map - sameSizeGrow = 8 // the current map growth is to a new map of the same size - - // sentinel bucket ID for iterator checks - noCheck = 1<<(8*goarch.PtrSize) - 1 -) - -// isEmpty reports whether the given tophash array entry represents an empty bucket entry. -func isEmpty(x uint8) bool { - return x <= emptyOne -} - -// A header for a Go map. -type hmap struct { - // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go. - // Make sure this stays in sync with the compiler's definition. - count int // # live cells == size of map. Must be first (used by len() builtin) - flags uint8 - B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) - noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details - hash0 uint32 // hash seed - - buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. - oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing - nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) - clearSeq uint64 - - extra *mapextra // optional fields -} - -// mapextra holds fields that are not present on all maps. -type mapextra struct { - // If both key and elem do not contain pointers and are inline, then we mark bucket - // type as containing no pointers. This avoids scanning such maps. - // However, bmap.overflow is a pointer. In order to keep overflow buckets - // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow. - // overflow and oldoverflow are only used if key and elem do not contain pointers. - // overflow contains overflow buckets for hmap.buckets. - // oldoverflow contains overflow buckets for hmap.oldbuckets. - // The indirection allows to store a pointer to the slice in hiter. - overflow *[]*bmap - oldoverflow *[]*bmap - - // nextOverflow holds a pointer to a free overflow bucket. - nextOverflow *bmap -} - -// A bucket for a Go map. -type bmap struct { - // tophash generally contains the top byte of the hash value - // for each key in this bucket. If tophash[0] < minTopHash, - // tophash[0] is a bucket evacuation state instead. - tophash [abi.OldMapBucketCount]uint8 - // Followed by bucketCnt keys and then bucketCnt elems. - // NOTE: packing all the keys together and then all the elems together makes the - // code a bit more complicated than alternating key/elem/key/elem/... but it allows - // us to eliminate padding which would be needed for, e.g., map[int64]int8. - // Followed by an overflow pointer. -} - -// A hash iteration structure. -// If you modify hiter, also change cmd/compile/internal/reflectdata/reflect.go -// and reflect/value.go to match the layout of this structure. -type hiter struct { - key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go). - elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go). - t *maptype - h *hmap - buckets unsafe.Pointer // bucket ptr at hash_iter initialization time - bptr *bmap // current bucket - overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive - oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive - startBucket uintptr // bucket iteration started at - offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) - wrapped bool // already wrapped around from end of bucket array to beginning - B uint8 - i uint8 - bucket uintptr - checkBucket uintptr - clearSeq uint64 -} - -// bucketShift returns 1<<b, optimized for code generation. -func bucketShift(b uint8) uintptr { - // Masking the shift amount allows overflow checks to be elided. - return uintptr(1) << (b & (goarch.PtrSize*8 - 1)) -} - -// bucketMask returns 1<<b - 1, optimized for code generation. -func bucketMask(b uint8) uintptr { - return bucketShift(b) - 1 -} - -// tophash calculates the tophash value for hash. -func tophash(hash uintptr) uint8 { - top := uint8(hash >> (goarch.PtrSize*8 - 8)) - if top < minTopHash { - top += minTopHash - } - return top -} - -func evacuated(b *bmap) bool { - h := b.tophash[0] - return h > emptyOne && h < minTopHash -} - -func (b *bmap) overflow(t *maptype) *bmap { - return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.BucketSize)-goarch.PtrSize)) -} - -func (b *bmap) setoverflow(t *maptype, ovf *bmap) { - *(**bmap)(add(unsafe.Pointer(b), uintptr(t.BucketSize)-goarch.PtrSize)) = ovf -} - -func (b *bmap) keys() unsafe.Pointer { - return add(unsafe.Pointer(b), dataOffset) -} - -// incrnoverflow increments h.noverflow. -// noverflow counts the number of overflow buckets. -// This is used to trigger same-size map growth. -// See also tooManyOverflowBuckets. -// To keep hmap small, noverflow is a uint16. -// When there are few buckets, noverflow is an exact count. -// When there are many buckets, noverflow is an approximate count. -func (h *hmap) incrnoverflow() { - // We trigger same-size map growth if there are - // as many overflow buckets as buckets. - // We need to be able to count to 1<<h.B. - if h.B < 16 { - h.noverflow++ - return - } - // Increment with probability 1/(1<<(h.B-15)). - // When we reach 1<<15 - 1, we will have approximately - // as many overflow buckets as buckets. - mask := uint32(1)<<(h.B-15) - 1 - // Example: if h.B == 18, then mask == 7, - // and rand() & 7 == 0 with probability 1/8. - if uint32(rand())&mask == 0 { - h.noverflow++ - } -} - -func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap { - var ovf *bmap - if h.extra != nil && h.extra.nextOverflow != nil { - // We have preallocated overflow buckets available. - // See makeBucketArray for more details. - ovf = h.extra.nextOverflow - if ovf.overflow(t) == nil { - // We're not at the end of the preallocated overflow buckets. Bump the pointer. - h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize))) - } else { - // This is the last preallocated overflow bucket. - // Reset the overflow pointer on this bucket, - // which was set to a non-nil sentinel value. - ovf.setoverflow(t, nil) - h.extra.nextOverflow = nil - } - } else { - ovf = (*bmap)(newobject(t.Bucket)) - } - h.incrnoverflow() - if !t.Bucket.Pointers() { - h.createOverflow() - *h.extra.overflow = append(*h.extra.overflow, ovf) - } - b.setoverflow(t, ovf) - return ovf -} - -func (h *hmap) createOverflow() { - if h.extra == nil { - h.extra = new(mapextra) - } - if h.extra.overflow == nil { - h.extra.overflow = new([]*bmap) - } -} - -func makemap64(t *maptype, hint int64, h *hmap) *hmap { - if int64(int(hint)) != hint { - hint = 0 - } - return makemap(t, int(hint), h) -} - -// makemap_small implements Go map creation for make(map[k]v) and -// make(map[k]v, hint) when hint is known to be at most bucketCnt -// at compile time and the map needs to be allocated on the heap. -// -// makemap_small should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname makemap_small -func makemap_small() *hmap { - h := new(hmap) - h.hash0 = uint32(rand()) - return h -} - -// makemap implements Go map creation for make(map[k]v, hint). -// If the compiler has determined that the map or the first bucket -// can be created on the stack, h and/or bucket may be non-nil. -// If h != nil, the map can be created directly in h. -// If h.buckets != nil, bucket pointed to can be used as the first bucket. -// -// makemap should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname makemap -func makemap(t *maptype, hint int, h *hmap) *hmap { - mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_) - if overflow || mem > maxAlloc { - hint = 0 - } - - // initialize Hmap - if h == nil { - h = new(hmap) - } - h.hash0 = uint32(rand()) - - // Find the size parameter B which will hold the requested # of elements. - // For hint < 0 overLoadFactor returns false since hint < bucketCnt. - B := uint8(0) - for overLoadFactor(hint, B) { - B++ - } - h.B = B - - // allocate initial hash table - // if B == 0, the buckets field is allocated lazily later (in mapassign) - // If hint is large zeroing this memory could take a while. - if h.B != 0 { - var nextOverflow *bmap - h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) - if nextOverflow != nil { - h.extra = new(mapextra) - h.extra.nextOverflow = nextOverflow - } - } - - return h -} - -// makeBucketArray initializes a backing array for map buckets. -// 1<<b is the minimum number of buckets to allocate. -// dirtyalloc should either be nil or a bucket array previously -// allocated by makeBucketArray with the same t and b parameters. -// If dirtyalloc is nil a new backing array will be alloced and -// otherwise dirtyalloc will be cleared and reused as backing array. -func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) { - base := bucketShift(b) - nbuckets := base - // For small b, overflow buckets are unlikely. - // Avoid the overhead of the calculation. - if b >= 4 { - // Add on the estimated number of overflow buckets - // required to insert the median number of elements - // used with this value of b. - nbuckets += bucketShift(b - 4) - sz := t.Bucket.Size_ * nbuckets - up := roundupsize(sz, !t.Bucket.Pointers()) - if up != sz { - nbuckets = up / t.Bucket.Size_ - } - } - - if dirtyalloc == nil { - buckets = newarray(t.Bucket, int(nbuckets)) - } else { - // dirtyalloc was previously generated by - // the above newarray(t.Bucket, int(nbuckets)) - // but may not be empty. - buckets = dirtyalloc - size := t.Bucket.Size_ * nbuckets - if t.Bucket.Pointers() { - memclrHasPointers(buckets, size) - } else { - memclrNoHeapPointers(buckets, size) - } - } - - if base != nbuckets { - // We preallocated some overflow buckets. - // To keep the overhead of tracking these overflow buckets to a minimum, - // we use the convention that if a preallocated overflow bucket's overflow - // pointer is nil, then there are more available by bumping the pointer. - // We need a safe non-nil pointer for the last overflow bucket; just use buckets. - nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize))) - last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize))) - last.setoverflow(t, (*bmap)(buckets)) - } - return buckets, nextOverflow -} - -// mapaccess1 returns a pointer to h[key]. Never returns nil, instead -// it will return a reference to the zero object for the elem type if -// the key is not in the map. -// NOTE: The returned pointer may keep the whole map live, so don't -// hold onto it for very long. -func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - pc := abi.FuncPCABIInternal(mapaccess1) - racereadpc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.Key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.Key.Size_) - } - if asanenabled && h != nil { - asanread(key, t.Key.Size_) - } - if h == nil || h.count == 0 { - if err := maps.OldMapKeyError(t, key); err != nil { - panic(err) // see issue 23734 - } - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - hash := t.Hasher(key, uintptr(h.hash0)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) -bucketloop: - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - if t.IndirectElem() { - e = *((*unsafe.Pointer)(e)) - } - return e - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -// mapaccess2 should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapaccess2 -func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - pc := abi.FuncPCABIInternal(mapaccess2) - racereadpc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.Key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.Key.Size_) - } - if asanenabled && h != nil { - asanread(key, t.Key.Size_) - } - if h == nil || h.count == 0 { - if err := maps.OldMapKeyError(t, key); err != nil { - panic(err) // see issue 23734 - } - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - hash := t.Hasher(key, uintptr(h.hash0)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) -bucketloop: - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - if t.IndirectElem() { - e = *((*unsafe.Pointer)(e)) - } - return e, true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -// returns both key and elem. Used by map iterator. -func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) { - if h == nil || h.count == 0 { - return nil, nil - } - hash := t.Hasher(key, uintptr(h.hash0)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) -bucketloop: - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - if t.IndirectElem() { - e = *((*unsafe.Pointer)(e)) - } - return k, e - } - } - } - return nil, nil -} - -func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer { - e := mapaccess1(t, h, key) - if e == unsafe.Pointer(&zeroVal[0]) { - return zero - } - return e -} - -func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) { - e := mapaccess1(t, h, key) - if e == unsafe.Pointer(&zeroVal[0]) { - return zero, false - } - return e, true -} - -// Like mapaccess, but allocates a slot for the key if it is not present in the map. -// -// mapassign should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/RomiChan/protobuf -// - github.com/segmentio/encoding -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapassign -func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := sys.GetCallerPC() - pc := abi.FuncPCABIInternal(mapassign) - racewritepc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.Key, key, callerpc, pc) - } - if msanenabled { - msanread(key, t.Key.Size_) - } - if asanenabled { - asanread(key, t.Key.Size_) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - hash := t.Hasher(key, uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher, since t.hasher may panic, - // in which case we have not actually done a write. - h.flags ^= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - top := tophash(hash) - - var inserti *uint8 - var insertk unsafe.Pointer - var elem unsafe.Pointer -bucketloop: - for { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if isEmpty(b.tophash[i]) && inserti == nil { - inserti = &b.tophash[i] - insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - } - if b.tophash[i] == emptyRest { - break bucketloop - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - if !t.Key.Equal(key, k) { - continue - } - // already have a mapping for key. Update it. - if t.NeedKeyUpdate() { - typedmemmove(t.Key, k, key) - } - elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if inserti == nil { - // The current bucket and all the overflow buckets connected to it are full, allocate a new one. - newb := h.newoverflow(t, b) - inserti = &newb.tophash[0] - insertk = add(unsafe.Pointer(newb), dataOffset) - elem = add(insertk, abi.OldMapBucketCount*uintptr(t.KeySize)) - } - - // store new key/elem at insert position - if t.IndirectKey() { - kmem := newobject(t.Key) - *(*unsafe.Pointer)(insertk) = kmem - insertk = kmem - } - if t.IndirectElem() { - vmem := newobject(t.Elem) - *(*unsafe.Pointer)(elem) = vmem - } - typedmemmove(t.Key, insertk, key) - *inserti = top - h.count++ - -done: - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting - if t.IndirectElem() { - elem = *((*unsafe.Pointer)(elem)) - } - return elem -} - -// mapdelete should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/ugorji/go/codec -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapdelete -func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - pc := abi.FuncPCABIInternal(mapdelete) - racewritepc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.Key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.Key.Size_) - } - if asanenabled && h != nil { - asanread(key, t.Key.Size_) - } - if h == nil || h.count == 0 { - if err := maps.OldMapKeyError(t, key); err != nil { - panic(err) // see issue 23734 - } - return - } - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - - hash := t.Hasher(key, uintptr(h.hash0)) - - // Set hashWriting after calling t.hasher, since t.hasher may panic, - // in which case we have not actually done a write (delete). - h.flags ^= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize))) - bOrig := b - top := tophash(hash) -search: - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if b.tophash[i] != top { - if b.tophash[i] == emptyRest { - break search - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - k2 := k - if t.IndirectKey() { - k2 = *((*unsafe.Pointer)(k2)) - } - if !t.Key.Equal(key, k2) { - continue - } - // Only clear key if there are pointers in it. - if t.IndirectKey() { - *(*unsafe.Pointer)(k) = nil - } else if t.Key.Pointers() { - memclrHasPointers(k, t.Key.Size_) - } - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - if t.IndirectElem() { - *(*unsafe.Pointer)(e) = nil - } else if t.Elem.Pointers() { - memclrHasPointers(e, t.Elem.Size_) - } else { - memclrNoHeapPointers(e, t.Elem.Size_) - } - b.tophash[i] = emptyOne - // If the bucket now ends in a bunch of emptyOne states, - // change those to emptyRest states. - // It would be nice to make this a separate function, but - // for loops are not currently inlineable. - if i == abi.OldMapBucketCount-1 { - if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { - goto notLast - } - } else { - if b.tophash[i+1] != emptyRest { - goto notLast - } - } - for { - b.tophash[i] = emptyRest - if i == 0 { - if b == bOrig { - break // beginning of initial bucket, we're done. - } - // Find previous bucket, continue at its last entry. - c := b - for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { - } - i = abi.OldMapBucketCount - 1 - } else { - i-- - } - if b.tophash[i] != emptyOne { - break - } - } - notLast: - h.count-- - // Reset the hash seed to make it more difficult for attackers to - // repeatedly trigger hash collisions. See issue 25237. - if h.count == 0 { - h.hash0 = uint32(rand()) - } - break search - } - } - - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting -} - -// mapiterinit initializes the hiter struct used for ranging over maps. -// The hiter struct pointed to by 'it' is allocated on the stack -// by the compilers order pass or on the heap by reflect_mapiterinit. -// Both need to have zeroed hiter since the struct contains pointers. -// -// mapiterinit should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/goccy/go-json -// - github.com/RomiChan/protobuf -// - github.com/segmentio/encoding -// - github.com/ugorji/go/codec -// - github.com/wI2L/jettison -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapiterinit -func mapiterinit(t *maptype, h *hmap, it *hiter) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiterinit)) - } - - it.t = t - if h == nil || h.count == 0 { - return - } - - if unsafe.Sizeof(hiter{}) != 8+12*goarch.PtrSize { - throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go - } - it.h = h - it.clearSeq = h.clearSeq - - // grab snapshot of bucket state - it.B = h.B - it.buckets = h.buckets - if !t.Bucket.Pointers() { - // Allocate the current slice and remember pointers to both current and old. - // This preserves all relevant overflow buckets alive even if - // the table grows and/or overflow buckets are added to the table - // while we are iterating. - h.createOverflow() - it.overflow = h.extra.overflow - it.oldoverflow = h.extra.oldoverflow - } - - // decide where to start - r := uintptr(rand()) - it.startBucket = r & bucketMask(h.B) - it.offset = uint8(r >> h.B & (abi.OldMapBucketCount - 1)) - - // iterator state - it.bucket = it.startBucket - - // Remember we have an iterator. - // Can run concurrently with another mapiterinit(). - if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator { - atomic.Or8(&h.flags, iterator|oldIterator) - } - - mapiternext(it) -} - -// mapiternext should be an internal detail, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/bytedance/sonic -// - github.com/RomiChan/protobuf -// - github.com/segmentio/encoding -// - github.com/ugorji/go/codec -// - gonum.org/v1/gonum -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname mapiternext -func mapiternext(it *hiter) { - h := it.h - if raceenabled { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiternext)) - } - if h.flags&hashWriting != 0 { - fatal("concurrent map iteration and map write") - } - t := it.t - bucket := it.bucket - b := it.bptr - i := it.i - checkBucket := it.checkBucket - -next: - if b == nil { - if bucket == it.startBucket && it.wrapped { - // end of iteration - it.key = nil - it.elem = nil - return - } - if h.growing() && it.B == h.B { - // Iterator was started in the middle of a grow, and the grow isn't done yet. - // If the bucket we're looking at hasn't been filled in yet (i.e. the old - // bucket hasn't been evacuated) then we need to iterate through the old - // bucket and only return the ones that will be migrated to this bucket. - oldbucket := bucket & it.h.oldbucketmask() - b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))) - if !evacuated(b) { - checkBucket = bucket - } else { - b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize))) - checkBucket = noCheck - } - } else { - b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize))) - checkBucket = noCheck - } - bucket++ - if bucket == bucketShift(it.B) { - bucket = 0 - it.wrapped = true - } - i = 0 - } - for ; i < abi.OldMapBucketCount; i++ { - offi := (i + it.offset) & (abi.OldMapBucketCount - 1) - if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { - // TODO: emptyRest is hard to use here, as we start iterating - // in the middle of a bucket. It's feasible, just tricky. - continue - } - k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize)) - if checkBucket != noCheck && !h.sameSizeGrow() { - // Special case: iterator was started during a grow to a larger size - // and the grow is not done yet. We're working on a bucket whose - // oldbucket has not been evacuated yet. Or at least, it wasn't - // evacuated when we started the bucket. So we're iterating - // through the oldbucket, skipping any keys that will go - // to the other new bucket (each oldbucket expands to two - // buckets during a grow). - if t.ReflexiveKey() || t.Key.Equal(k, k) { - // If the item in the oldbucket is not destined for - // the current new bucket in the iteration, skip it. - hash := t.Hasher(k, uintptr(h.hash0)) - if hash&bucketMask(it.B) != checkBucket { - continue - } - } else { - // Hash isn't repeatable if k != k (NaNs). We need a - // repeatable and randomish choice of which direction - // to send NaNs during evacuation. We'll use the low - // bit of tophash to decide which way NaNs go. - // NOTE: this case is why we need two evacuate tophash - // values, evacuatedX and evacuatedY, that differ in - // their low bit. - if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { - continue - } - } - } - if it.clearSeq == h.clearSeq && - ((b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || - !(t.ReflexiveKey() || t.Key.Equal(k, k))) { - // This is the golden data, we can return it. - // OR - // key!=key, so the entry can't be deleted or updated, so we can just return it. - // That's lucky for us because when key!=key we can't look it up successfully. - it.key = k - if t.IndirectElem() { - e = *((*unsafe.Pointer)(e)) - } - it.elem = e - } else { - // The hash table has grown since the iterator was started. - // The golden data for this key is now somewhere else. - // Check the current hash table for the data. - // This code handles the case where the key - // has been deleted, updated, or deleted and reinserted. - // NOTE: we need to regrab the key as it has potentially been - // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). - rk, re := mapaccessK(t, h, k) - if rk == nil { - continue // key has been deleted - } - it.key = rk - it.elem = re - } - it.bucket = bucket - if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 - it.bptr = b - } - it.i = i + 1 - it.checkBucket = checkBucket - return - } - b = b.overflow(t) - i = 0 - goto next -} - -// mapclear deletes all keys from a map. -// It is called by the compiler. -func mapclear(t *maptype, h *hmap) { - if raceenabled && h != nil { - callerpc := sys.GetCallerPC() - pc := abi.FuncPCABIInternal(mapclear) - racewritepc(unsafe.Pointer(h), callerpc, pc) - } - - if h == nil || h.count == 0 { - return - } - - if h.flags&hashWriting != 0 { - fatal("concurrent map writes") - } - - h.flags ^= hashWriting - h.flags &^= sameSizeGrow - h.oldbuckets = nil - h.nevacuate = 0 - h.noverflow = 0 - h.count = 0 - h.clearSeq++ - - // Reset the hash seed to make it more difficult for attackers to - // repeatedly trigger hash collisions. See issue 25237. - h.hash0 = uint32(rand()) - - // Keep the mapextra allocation but clear any extra information. - if h.extra != nil { - *h.extra = mapextra{} - } - - // makeBucketArray clears the memory pointed to by h.buckets - // and recovers any overflow buckets by generating them - // as if h.buckets was newly alloced. - _, nextOverflow := makeBucketArray(t, h.B, h.buckets) - if nextOverflow != nil { - // If overflow buckets are created then h.extra - // will have been allocated during initial bucket creation. - h.extra.nextOverflow = nextOverflow - } - - if h.flags&hashWriting == 0 { - fatal("concurrent map writes") - } - h.flags &^= hashWriting -} - -func hashGrow(t *maptype, h *hmap) { - // If we've hit the load factor, get bigger. - // Otherwise, there are too many overflow buckets, - // so keep the same number of buckets and "grow" laterally. - bigger := uint8(1) - if !overLoadFactor(h.count+1, h.B) { - bigger = 0 - h.flags |= sameSizeGrow - } - oldbuckets := h.buckets - newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) - - flags := h.flags &^ (iterator | oldIterator) - if h.flags&iterator != 0 { - flags |= oldIterator - } - // commit the grow (atomic wrt gc) - h.B += bigger - h.flags = flags - h.oldbuckets = oldbuckets - h.buckets = newbuckets - h.nevacuate = 0 - h.noverflow = 0 - - if h.extra != nil && h.extra.overflow != nil { - // Promote current overflow buckets to the old generation. - if h.extra.oldoverflow != nil { - throw("oldoverflow is not nil") - } - h.extra.oldoverflow = h.extra.overflow - h.extra.overflow = nil - } - if nextOverflow != nil { - if h.extra == nil { - h.extra = new(mapextra) - } - h.extra.nextOverflow = nextOverflow - } - - // the actual copying of the hash table data is done incrementally - // by growWork() and evacuate(). -} - -// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor. -func overLoadFactor(count int, B uint8) bool { - return count > abi.OldMapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) -} - -// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets. -// Note that most of these overflow buckets must be in sparse use; -// if use was dense, then we'd have already triggered regular map growth. -func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { - // If the threshold is too low, we do extraneous work. - // If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory. - // "too many" means (approximately) as many overflow buckets as regular buckets. - // See incrnoverflow for more details. - if B > 15 { - B = 15 - } - // The compiler doesn't see here that B < 16; mask B to generate shorter shift code. - return noverflow >= uint16(1)<<(B&15) -} - -// growing reports whether h is growing. The growth may be to the same size or bigger. -func (h *hmap) growing() bool { - return h.oldbuckets != nil -} - -// sameSizeGrow reports whether the current growth is to a map of the same size. -func (h *hmap) sameSizeGrow() bool { - return h.flags&sameSizeGrow != 0 -} - -//go:linkname sameSizeGrowForIssue69110Test -func sameSizeGrowForIssue69110Test(h *hmap) bool { - return h.sameSizeGrow() -} - -// noldbuckets calculates the number of buckets prior to the current map growth. -func (h *hmap) noldbuckets() uintptr { - oldB := h.B - if !h.sameSizeGrow() { - oldB-- - } - return bucketShift(oldB) -} - -// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets(). -func (h *hmap) oldbucketmask() uintptr { - return h.noldbuckets() - 1 -} - -func growWork(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate(t, h, h.nevacuate) - } -} - -func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool { - b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.BucketSize))) - return evacuated(b) -} - -// evacDst is an evacuation destination. -type evacDst struct { - b *bmap // current destination bucket - i int // key/elem index into b - k unsafe.Pointer // pointer to current key storage - e unsafe.Pointer // pointer to current elem storage -} - -func evacuate(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.OldMapBucketCount*uintptr(t.KeySize)) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.OldMapBucketCount*uintptr(t.KeySize)) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.OldMapBucketCount*uintptr(t.KeySize)) - for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) { - top := b.tophash[i] - if isEmpty(top) { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - k2 := k - if t.IndirectKey() { - k2 = *((*unsafe.Pointer)(k2)) - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/elem to bucket x or bucket y). - hash := t.Hasher(k2, uintptr(h.hash0)) - if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) { - // If key != key (NaNs), then the hash could be (and probably - // will be) entirely different from the old hash. Moreover, - // it isn't reproducible. Reproducibility is required in the - // presence of iterators, as our evacuation decision must - // match whatever decision the iterator made. - // Fortunately, we have the freedom to send these keys either - // way. Also, tophash is meaningless for these kinds of keys. - // We let the low bit of tophash drive the evacuation decision. - // We recompute a new random tophash for the next level so - // these keys will get evenly distributed across all buckets - // after multiple grows. - useY = top & 1 - top = tophash(hash) - } else { - if hash&newbit != 0 { - useY = 1 - } - } - } - - if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { - throw("bad evacuatedN") - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY - dst := &xy[useY] // evacuation destination - - if dst.i == abi.OldMapBucketCount { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.OldMapBucketCount*uintptr(t.KeySize)) - } - dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check - if t.IndirectKey() { - *(*unsafe.Pointer)(dst.k) = k2 // copy pointer - } else { - typedmemmove(t.Key, dst.k, k) // copy elem - } - if t.IndirectElem() { - *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e) - } else { - typedmemmove(t.Elem, dst.e, e) - } - dst.i++ - // These updates might push these pointers past the end of the - // key or elem arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, uintptr(t.KeySize)) - dst.e = add(dst.e, uintptr(t.ValueSize)) - } - } - // Unlink the overflow buckets & clear key/elem to help GC. - if h.flags&oldIterator == 0 && t.Bucket.Pointers() { - b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.BucketSize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} - -func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { - h.nevacuate++ - // Experiments suggest that 1024 is overkill by at least an order of magnitude. - // Put it in there as a safeguard anyway, to ensure O(1) behavior. - stop := h.nevacuate + 1024 - if stop > newbit { - stop = newbit - } - for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { - h.nevacuate++ - } - if h.nevacuate == newbit { // newbit == # of oldbuckets - // Growing is all done. Free old main bucket array. - h.oldbuckets = nil - // Can discard old overflow buckets as well. - // If they are still referenced by an iterator, - // then the iterator holds a pointers to the slice. - if h.extra != nil { - h.extra.oldoverflow = nil - } - h.flags &^= sameSizeGrow - } -} - -// Reflect stubs. Called from ../reflect/asm_*.s - -// reflect_makemap is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - gitee.com/quant1x/gox -// - github.com/modern-go/reflect2 -// - github.com/goccy/go-json -// - github.com/RomiChan/protobuf -// - github.com/segmentio/encoding -// - github.com/v2pro/plz -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_makemap reflect.makemap -func reflect_makemap(t *maptype, cap int) *hmap { - // Check invariants and reflects math. - if t.Key.Equal == nil { - throw("runtime.reflect_makemap: unsupported map key type") - } - if t.Key.Size_ > abi.OldMapMaxKeyBytes && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || - t.Key.Size_ <= abi.OldMapMaxKeyBytes && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { - throw("key size wrong") - } - if t.Elem.Size_ > abi.OldMapMaxElemBytes && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || - t.Elem.Size_ <= abi.OldMapMaxElemBytes && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { - throw("elem size wrong") - } - if t.Key.Align_ > abi.OldMapBucketCount { - throw("key align too big") - } - if t.Elem.Align_ > abi.OldMapBucketCount { - throw("elem align too big") - } - if t.Key.Size_%uintptr(t.Key.Align_) != 0 { - throw("key size not a multiple of key align") - } - if t.Elem.Size_%uintptr(t.Elem.Align_) != 0 { - throw("elem size not a multiple of elem align") - } - if abi.OldMapBucketCount < 8 { - throw("bucketsize too small for proper alignment") - } - if dataOffset%uintptr(t.Key.Align_) != 0 { - throw("need padding in bucket (key)") - } - if dataOffset%uintptr(t.Elem.Align_) != 0 { - throw("need padding in bucket (elem)") - } - - return makemap(t, cap, nil) -} - -// reflect_mapaccess is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - gitee.com/quant1x/gox -// - github.com/modern-go/reflect2 -// - github.com/v2pro/plz -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_mapaccess reflect.mapaccess -func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - elem, ok := mapaccess2(t, h, key) - if !ok { - // reflect wants nil for a missing element - elem = nil - } - return elem -} - -//go:linkname reflect_mapaccess_faststr reflect.mapaccess_faststr -func reflect_mapaccess_faststr(t *maptype, h *hmap, key string) unsafe.Pointer { - elem, ok := mapaccess2_faststr(t, h, key) - if !ok { - // reflect wants nil for a missing element - elem = nil - } - return elem -} - -// reflect_mapassign is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - gitee.com/quant1x/gox -// - github.com/v2pro/plz -// -// Do not remove or change the type signature. -// -//go:linkname reflect_mapassign reflect.mapassign0 -func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, elem unsafe.Pointer) { - p := mapassign(t, h, key) - typedmemmove(t.Elem, p, elem) -} - -//go:linkname reflect_mapassign_faststr reflect.mapassign_faststr0 -func reflect_mapassign_faststr(t *maptype, h *hmap, key string, elem unsafe.Pointer) { - p := mapassign_faststr(t, h, key) - typedmemmove(t.Elem, p, elem) -} - -//go:linkname reflect_mapdelete reflect.mapdelete -func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { - mapdelete(t, h, key) -} - -//go:linkname reflect_mapdelete_faststr reflect.mapdelete_faststr -func reflect_mapdelete_faststr(t *maptype, h *hmap, key string) { - mapdelete_faststr(t, h, key) -} - -// reflect_mapiterinit is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/modern-go/reflect2 -// - gitee.com/quant1x/gox -// - github.com/v2pro/plz -// - github.com/wI2L/jettison -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_mapiterinit reflect.mapiterinit -func reflect_mapiterinit(t *maptype, h *hmap, it *hiter) { - mapiterinit(t, h, it) -} - -// reflect_mapiternext is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - gitee.com/quant1x/gox -// - github.com/modern-go/reflect2 -// - github.com/goccy/go-json -// - github.com/v2pro/plz -// - github.com/wI2L/jettison -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_mapiternext reflect.mapiternext -func reflect_mapiternext(it *hiter) { - mapiternext(it) -} - -// reflect_mapiterkey was for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/goccy/go-json -// - gonum.org/v1/gonum -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_mapiterkey reflect.mapiterkey -func reflect_mapiterkey(it *hiter) unsafe.Pointer { - return it.key -} - -// reflect_mapiterelem was for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/goccy/go-json -// - gonum.org/v1/gonum -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_mapiterelem reflect.mapiterelem -func reflect_mapiterelem(it *hiter) unsafe.Pointer { - return it.elem -} - -// reflect_maplen is for package reflect, -// but widely used packages access it using linkname. -// Notable members of the hall of shame include: -// - github.com/goccy/go-json -// - github.com/wI2L/jettison -// -// Do not remove or change the type signature. -// See go.dev/issue/67401. -// -//go:linkname reflect_maplen reflect.maplen -func reflect_maplen(h *hmap) int { - if h == nil { - return 0 - } - if raceenabled { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(reflect_maplen)) - } - return h.count -} - -//go:linkname reflect_mapclear reflect.mapclear -func reflect_mapclear(t *maptype, h *hmap) { - mapclear(t, h) -} - -//go:linkname reflectlite_maplen internal/reflectlite.maplen -func reflectlite_maplen(h *hmap) int { - if h == nil { - return 0 - } - if raceenabled { - callerpc := sys.GetCallerPC() - racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(reflect_maplen)) - } - return h.count -} - -// mapinitnoop is a no-op function known the Go linker; if a given global -// map (of the right size) is determined to be dead, the linker will -// rewrite the relocation (from the package init func) from the outlined -// map init function to this symbol. Defined in assembly so as to avoid -// complications with instrumentation (coverage, etc). -func mapinitnoop() - -// mapclone for implementing maps.Clone -// -//go:linkname mapclone maps.clone -func mapclone(m any) any { - e := efaceOf(&m) - e.data = unsafe.Pointer(mapclone2((*maptype)(unsafe.Pointer(e._type)), (*hmap)(e.data))) - return m -} - -// moveToBmap moves a bucket from src to dst. It returns the destination bucket or new destination bucket if it overflows -// and the pos that the next key/value will be written, if pos == bucketCnt means needs to written in overflow bucket. -func moveToBmap(t *maptype, h *hmap, dst *bmap, pos int, src *bmap) (*bmap, int) { - for i := 0; i < abi.OldMapBucketCount; i++ { - if isEmpty(src.tophash[i]) { - continue - } - - for ; pos < abi.OldMapBucketCount; pos++ { - if isEmpty(dst.tophash[pos]) { - break - } - } - - if pos == abi.OldMapBucketCount { - dst = h.newoverflow(t, dst) - pos = 0 - } - - srcK := add(unsafe.Pointer(src), dataOffset+uintptr(i)*uintptr(t.KeySize)) - srcEle := add(unsafe.Pointer(src), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize)) - dstK := add(unsafe.Pointer(dst), dataOffset+uintptr(pos)*uintptr(t.KeySize)) - dstEle := add(unsafe.Pointer(dst), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize)) - - dst.tophash[pos] = src.tophash[i] - if t.IndirectKey() { - srcK = *(*unsafe.Pointer)(srcK) - if t.NeedKeyUpdate() { - kStore := newobject(t.Key) - typedmemmove(t.Key, kStore, srcK) - srcK = kStore - } - // Note: if NeedKeyUpdate is false, then the memory - // used to store the key is immutable, so we can share - // it between the original map and its clone. - *(*unsafe.Pointer)(dstK) = srcK - } else { - typedmemmove(t.Key, dstK, srcK) - } - if t.IndirectElem() { - srcEle = *(*unsafe.Pointer)(srcEle) - eStore := newobject(t.Elem) - typedmemmove(t.Elem, eStore, srcEle) - *(*unsafe.Pointer)(dstEle) = eStore - } else { - typedmemmove(t.Elem, dstEle, srcEle) - } - pos++ - h.count++ - } - return dst, pos -} - -func mapclone2(t *maptype, src *hmap) *hmap { - hint := src.count - if overLoadFactor(hint, src.B) { - // Note: in rare cases (e.g. during a same-sized grow) the map - // can be overloaded. Make sure we don't allocate a destination - // bucket array larger than the source bucket array. - // This will cause the cloned map to be overloaded also, - // but that's better than crashing. See issue 69110. - hint = int(loadFactorNum * (bucketShift(src.B) / loadFactorDen)) - } - dst := makemap(t, hint, nil) - dst.hash0 = src.hash0 - dst.nevacuate = 0 - // flags do not need to be copied here, just like a new map has no flags. - - if src.count == 0 { - return dst - } - - if src.flags&hashWriting != 0 { - fatal("concurrent map clone and map write") - } - - if src.B == 0 && !(t.IndirectKey() && t.NeedKeyUpdate()) && !t.IndirectElem() { - // Quick copy for small maps. - dst.buckets = newobject(t.Bucket) - dst.count = src.count - typedmemmove(t.Bucket, dst.buckets, src.buckets) - return dst - } - - if dst.B == 0 { - dst.buckets = newobject(t.Bucket) - } - dstArraySize := int(bucketShift(dst.B)) - srcArraySize := int(bucketShift(src.B)) - for i := 0; i < dstArraySize; i++ { - dstBmap := (*bmap)(add(dst.buckets, uintptr(i*int(t.BucketSize)))) - pos := 0 - for j := 0; j < srcArraySize; j += dstArraySize { - srcBmap := (*bmap)(add(src.buckets, uintptr((i+j)*int(t.BucketSize)))) - for srcBmap != nil { - dstBmap, pos = moveToBmap(t, dst, dstBmap, pos, srcBmap) - srcBmap = srcBmap.overflow(t) - } - } - } - - if src.oldbuckets == nil { - return dst - } - - oldB := src.B - srcOldbuckets := src.oldbuckets - if !src.sameSizeGrow() { - oldB-- - } - oldSrcArraySize := int(bucketShift(oldB)) - - for i := 0; i < oldSrcArraySize; i++ { - srcBmap := (*bmap)(add(srcOldbuckets, uintptr(i*int(t.BucketSize)))) - if evacuated(srcBmap) { - continue - } - - if oldB >= dst.B { // main bucket bits in dst is less than oldB bits in src - dstBmap := (*bmap)(add(dst.buckets, (uintptr(i)&bucketMask(dst.B))*uintptr(t.BucketSize))) - for dstBmap.overflow(t) != nil { - dstBmap = dstBmap.overflow(t) - } - pos := 0 - for srcBmap != nil { - dstBmap, pos = moveToBmap(t, dst, dstBmap, pos, srcBmap) - srcBmap = srcBmap.overflow(t) - } - continue - } - - // oldB < dst.B, so a single source bucket may go to multiple destination buckets. - // Process entries one at a time. - for srcBmap != nil { - // move from oldBlucket to new bucket - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - if isEmpty(srcBmap.tophash[i]) { - continue - } - - if src.flags&hashWriting != 0 { - fatal("concurrent map clone and map write") - } - - srcK := add(unsafe.Pointer(srcBmap), dataOffset+i*uintptr(t.KeySize)) - if t.IndirectKey() { - srcK = *((*unsafe.Pointer)(srcK)) - } - - srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) - if t.IndirectElem() { - srcEle = *((*unsafe.Pointer)(srcEle)) - } - dstEle := mapassign(t, dst, srcK) - typedmemmove(t.Elem, dstEle, srcEle) - } - srcBmap = srcBmap.overflow(t) - } - } - return dst -} - -// keys for implementing maps.keys -// -//go:linkname keys maps.keys -func keys(m any, p unsafe.Pointer) { - e := efaceOf(&m) - t := (*maptype)(unsafe.Pointer(e._type)) - h := (*hmap)(e.data) - - if h == nil || h.count == 0 { - return - } - s := (*slice)(p) - r := int(rand()) - offset := uint8(r >> h.B & (abi.OldMapBucketCount - 1)) - if h.B == 0 { - copyKeys(t, h, (*bmap)(h.buckets), s, offset) - return - } - arraySize := int(bucketShift(h.B)) - buckets := h.buckets - for i := 0; i < arraySize; i++ { - bucket := (i + r) & (arraySize - 1) - b := (*bmap)(add(buckets, uintptr(bucket)*uintptr(t.BucketSize))) - copyKeys(t, h, b, s, offset) - } - - if h.growing() { - oldArraySize := int(h.noldbuckets()) - for i := 0; i < oldArraySize; i++ { - bucket := (i + r) & (oldArraySize - 1) - b := (*bmap)(add(h.oldbuckets, uintptr(bucket)*uintptr(t.BucketSize))) - if evacuated(b) { - continue - } - copyKeys(t, h, b, s, offset) - } - } - return -} - -func copyKeys(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { - for b != nil { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.OldMapBucketCount - 1) - if isEmpty(b.tophash[offi]) { - continue - } - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - k := add(unsafe.Pointer(b), dataOffset+offi*uintptr(t.KeySize)) - if t.IndirectKey() { - k = *((*unsafe.Pointer)(k)) - } - if s.len >= s.cap { - fatal("concurrent map read and map write") - } - typedmemmove(t.Key, add(s.array, uintptr(s.len)*uintptr(t.Key.Size())), k) - s.len++ - } - b = b.overflow(t) - } -} - -// values for implementing maps.values -// -//go:linkname values maps.values -func values(m any, p unsafe.Pointer) { - e := efaceOf(&m) - t := (*maptype)(unsafe.Pointer(e._type)) - h := (*hmap)(e.data) - if h == nil || h.count == 0 { - return - } - s := (*slice)(p) - r := int(rand()) - offset := uint8(r >> h.B & (abi.OldMapBucketCount - 1)) - if h.B == 0 { - copyValues(t, h, (*bmap)(h.buckets), s, offset) - return - } - arraySize := int(bucketShift(h.B)) - buckets := h.buckets - for i := 0; i < arraySize; i++ { - bucket := (i + r) & (arraySize - 1) - b := (*bmap)(add(buckets, uintptr(bucket)*uintptr(t.BucketSize))) - copyValues(t, h, b, s, offset) - } - - if h.growing() { - oldArraySize := int(h.noldbuckets()) - for i := 0; i < oldArraySize; i++ { - bucket := (i + r) & (oldArraySize - 1) - b := (*bmap)(add(h.oldbuckets, uintptr(bucket)*uintptr(t.BucketSize))) - if evacuated(b) { - continue - } - copyValues(t, h, b, s, offset) - } - } - return -} - -func copyValues(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { - for b != nil { - for i := uintptr(0); i < abi.OldMapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.OldMapBucketCount - 1) - if isEmpty(b.tophash[offi]) { - continue - } - - if h.flags&hashWriting != 0 { - fatal("concurrent map read and map write") - } - - ele := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+offi*uintptr(t.ValueSize)) - if t.IndirectElem() { - ele = *((*unsafe.Pointer)(ele)) - } - if s.len >= s.cap { - fatal("concurrent map read and map write") - } - typedmemmove(t.Elem, add(s.array, uintptr(s.len)*uintptr(t.Elem.Size())), ele) - s.len++ - } - b = b.overflow(t) - } -} diff --git a/src/runtime/map_noswiss_test.go b/src/runtime/map_noswiss_test.go deleted file mode 100644 index 5af7b7b8c8..0000000000 --- a/src/runtime/map_noswiss_test.go +++ /dev/null @@ -1,214 +0,0 @@ -// Copyright 2024 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package runtime_test - -import ( - "internal/abi" - "internal/goarch" - "runtime" - "slices" - "testing" -) - -func TestHmapSize(t *testing.T) { - // The structure of hmap is defined in runtime/map.go - // and in cmd/compile/internal/reflectdata/map.go and must be in sync. - // The size of hmap should be 56 bytes on 64 bit and 36 bytes on 32 bit platforms. - var hmapSize = uintptr(2*8 + 5*goarch.PtrSize) - if runtime.RuntimeHmapSize != hmapSize { - t.Errorf("sizeof(runtime.hmap{})==%d, want %d", runtime.RuntimeHmapSize, hmapSize) - } -} - -func TestLoadFactor(t *testing.T) { - for b := uint8(0); b < 20; b++ { - count := 13 * (1 << b) / 2 // 6.5 - if b == 0 { - count = 8 - } - if runtime.OverLoadFactor(count, b) { - t.Errorf("OverLoadFactor(%d,%d)=true, want false", count, b) - } - if !runtime.OverLoadFactor(count+1, b) { - t.Errorf("OverLoadFactor(%d,%d)=false, want true", count+1, b) - } - } -} - -func TestMapIterOrder(t *testing.T) { - sizes := []int{3, 7, 9, 15} - if abi.OldMapBucketCountBits >= 5 { - // it gets flaky (often only one iteration order) at size 3 when abi.MapBucketCountBits >=5. - t.Fatalf("This test becomes flaky if abi.MapBucketCountBits(=%d) is 5 or larger", abi.OldMapBucketCountBits) - } - for _, n := range sizes { - for i := 0; i < 1000; i++ { - // Make m be {0: true, 1: true, ..., n-1: true}. - m := make(map[int]bool) - for i := 0; i < n; i++ { - m[i] = true - } - // Check that iterating over the map produces at least two different orderings. - ord := func() []int { - var s []int - for key := range m { - s = append(s, key) - } - return s - } - first := ord() - ok := false - for try := 0; try < 100; try++ { - if !slices.Equal(first, ord()) { - ok = true - break - } - } - if !ok { - t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) - break - } - } - } -} - -const bs = abi.OldMapBucketCount - -// belowOverflow should be a pretty-full pair of buckets; -// atOverflow is 1/8 bs larger = 13/8 buckets or two buckets -// that are 13/16 full each, which is the overflow boundary. -// Adding one to that should ensure overflow to the next higher size. -const ( - belowOverflow = bs * 3 / 2 // 1.5 bs = 2 buckets @ 75% - atOverflow = belowOverflow + bs/8 // 2 buckets at 13/16 fill. -) - -var mapBucketTests = [...]struct { - n int // n is the number of map elements - noescape int // number of expected buckets for non-escaping map - escape int // number of expected buckets for escaping map -}{ - {-(1 << 30), 1, 1}, - {-1, 1, 1}, - {0, 1, 1}, - {1, 1, 1}, - {bs, 1, 1}, - {bs + 1, 2, 2}, - {belowOverflow, 2, 2}, // 1.5 bs = 2 buckets @ 75% - {atOverflow + 1, 4, 4}, // 13/8 bs + 1 == overflow to 4 - - {2 * belowOverflow, 4, 4}, // 3 bs = 4 buckets @75% - {2*atOverflow + 1, 8, 8}, // 13/4 bs + 1 = overflow to 8 - - {4 * belowOverflow, 8, 8}, // 6 bs = 8 buckets @ 75% - {4*atOverflow + 1, 16, 16}, // 13/2 bs + 1 = overflow to 16 -} - -func TestMapBuckets(t *testing.T) { - // Test that maps of different sizes have the right number of buckets. - // Non-escaping maps with small buckets (like map[int]int) never - // have a nil bucket pointer due to starting with preallocated buckets - // on the stack. Escaping maps start with a non-nil bucket pointer if - // hint size is above bucketCnt and thereby have more than one bucket. - // These tests depend on bucketCnt and loadFactor* in map.go. - t.Run("mapliteral", func(t *testing.T) { - for _, tt := range mapBucketTests { - localMap := map[int]int{} - if runtime.MapBucketsPointerIsNil(localMap) { - t.Errorf("no escape: buckets pointer is nil for non-escaping map") - } - for i := 0; i < tt.n; i++ { - localMap[i] = i - } - if got := runtime.MapBucketsCount(localMap); got != tt.noescape { - t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got) - } - escapingMap := runtime.Escape(map[int]int{}) - if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) { - t.Errorf("escape: buckets pointer is nil for n=%d buckets", count) - } - for i := 0; i < tt.n; i++ { - escapingMap[i] = i - } - if got := runtime.MapBucketsCount(escapingMap); got != tt.escape { - t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got) - } - } - }) - t.Run("nohint", func(t *testing.T) { - for _, tt := range mapBucketTests { - localMap := make(map[int]int) - if runtime.MapBucketsPointerIsNil(localMap) { - t.Errorf("no escape: buckets pointer is nil for non-escaping map") - } - for i := 0; i < tt.n; i++ { - localMap[i] = i - } - if got := runtime.MapBucketsCount(localMap); got != tt.noescape { - t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got) - } - escapingMap := runtime.Escape(make(map[int]int)) - if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) { - t.Errorf("escape: buckets pointer is nil for n=%d buckets", count) - } - for i := 0; i < tt.n; i++ { - escapingMap[i] = i - } - if got := runtime.MapBucketsCount(escapingMap); got != tt.escape { - t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got) - } - } - }) - t.Run("makemap", func(t *testing.T) { - for _, tt := range mapBucketTests { - localMap := make(map[int]int, tt.n) - if runtime.MapBucketsPointerIsNil(localMap) { - t.Errorf("no escape: buckets pointer is nil for non-escaping map") - } - for i := 0; i < tt.n; i++ { - localMap[i] = i - } - if got := runtime.MapBucketsCount(localMap); got != tt.noescape { - t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got) - } - escapingMap := runtime.Escape(make(map[int]int, tt.n)) - if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) { - t.Errorf("escape: buckets pointer is nil for n=%d buckets", count) - } - for i := 0; i < tt.n; i++ { - escapingMap[i] = i - } - if got := runtime.MapBucketsCount(escapingMap); got != tt.escape { - t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got) - } - } - }) - t.Run("makemap64", func(t *testing.T) { - for _, tt := range mapBucketTests { - localMap := make(map[int]int, int64(tt.n)) - if runtime.MapBucketsPointerIsNil(localMap) { - t.Errorf("no escape: buckets pointer is nil for non-escaping map") - } - for i := 0; i < tt.n; i++ { - localMap[i] = i - } - if got := runtime.MapBucketsCount(localMap); got != tt.noescape { - t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got) - } - escapingMap := runtime.Escape(make(map[int]int, tt.n)) - if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) { - t.Errorf("escape: buckets pointer is nil for n=%d buckets", count) - } - for i := 0; i < tt.n; i++ { - escapingMap[i] = i - } - if got := runtime.MapBucketsCount(escapingMap); got != tt.escape { - t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got) - } - } - }) -} diff --git a/src/runtime/map_swiss_test.go b/src/runtime/map_swiss_test.go deleted file mode 100644 index d5c9fdbe46..0000000000 --- a/src/runtime/map_swiss_test.go +++ /dev/null @@ -1,75 +0,0 @@ -// Copyright 2024 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build goexperiment.swissmap - -package runtime_test - -import ( - "internal/abi" - "internal/goarch" - "internal/runtime/maps" - "slices" - "testing" - "unsafe" -) - -func TestHmapSize(t *testing.T) { - // The structure of Map is defined in internal/runtime/maps/map.go - // and in cmd/compile/internal/reflectdata/map_swiss.go and must be in sync. - // The size of Map should be 48 bytes on 64 bit and 32 bytes on 32 bit platforms. - wantSize := uintptr(2*8 + 4*goarch.PtrSize) - gotSize := unsafe.Sizeof(maps.Map{}) - if gotSize != wantSize { - t.Errorf("sizeof(maps.Map{})==%d, want %d", gotSize, wantSize) - } -} - -// See also reflect_test.TestGroupSizeZero. -func TestGroupSizeZero(t *testing.T) { - var m map[struct{}]struct{} - mTyp := abi.TypeOf(m) - mt := (*abi.SwissMapType)(unsafe.Pointer(mTyp)) - - // internal/runtime/maps when create pointers to slots, even if slots - // are size 0. The compiler should have reserved an extra word to - // ensure that pointers to the zero-size type at the end of group are - // valid. - if mt.Group.Size() <= 8 { - t.Errorf("Group size got %d want >8", mt.Group.Size()) - } -} - -func TestMapIterOrder(t *testing.T) { - sizes := []int{3, 7, 9, 15} - for _, n := range sizes { - for i := 0; i < 1000; i++ { - // Make m be {0: true, 1: true, ..., n-1: true}. - m := make(map[int]bool) - for i := 0; i < n; i++ { - m[i] = true - } - // Check that iterating over the map produces at least two different orderings. - ord := func() []int { - var s []int - for key := range m { - s = append(s, key) - } - return s - } - first := ord() - ok := false - for try := 0; try < 100; try++ { - if !slices.Equal(first, ord()) { - ok = true - break - } - } - if !ok { - t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) - break - } - } - } -} diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go index b1ff02d851..ff7fbeb230 100644 --- a/src/runtime/map_test.go +++ b/src/runtime/map_test.go @@ -6,7 +6,9 @@ package runtime_test import ( "fmt" - "internal/goexperiment" + "internal/abi" + "internal/goarch" + "internal/runtime/maps" "internal/testenv" "math" "os" @@ -812,31 +814,6 @@ func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) { } } -func TestMapTombstones(t *testing.T) { - m := map[int]int{} - const N = 10000 - // Fill a map. - for i := 0; i < N; i++ { - m[i] = i - } - runtime.MapTombstoneCheck(m) - // Delete half of the entries. - for i := 0; i < N; i += 2 { - delete(m, i) - } - runtime.MapTombstoneCheck(m) - // Add new entries to fill in holes. - for i := N; i < 3*N/2; i++ { - m[i] = i - } - runtime.MapTombstoneCheck(m) - // Delete everything. - for i := 0; i < 3*N/2; i++ { - delete(m, i) - } - runtime.MapTombstoneCheck(m) -} - type canString int func (c canString) String() string { @@ -1060,44 +1037,6 @@ func TestEmptyMapWithInterfaceKey(t *testing.T) { }) } -func TestMapKeys(t *testing.T) { - if goexperiment.SwissMap { - t.Skip("mapkeys not implemented for swissmaps") - } - - type key struct { - s string - pad [128]byte // sizeof(key) > abi.MapMaxKeyBytes - } - m := map[key]int{{s: "a"}: 1, {s: "b"}: 2} - keys := make([]key, 0, len(m)) - runtime.MapKeys(m, unsafe.Pointer(&keys)) - for _, k := range keys { - if len(k.s) != 1 { - t.Errorf("len(k.s) == %d, want 1", len(k.s)) - } - } -} - -func TestMapValues(t *testing.T) { - if goexperiment.SwissMap { - t.Skip("mapvalues not implemented for swissmaps") - } - - type val struct { - s string - pad [128]byte // sizeof(val) > abi.MapMaxElemBytes - } - m := map[int]val{1: {s: "a"}, 2: {s: "b"}} - vals := make([]val, 0, len(m)) - runtime.MapValues(m, unsafe.Pointer(&vals)) - for _, v := range vals { - if len(v.s) != 1 { - t.Errorf("len(v.s) == %d, want 1", len(v.s)) - } - } -} - func computeHash() uintptr { var v struct{} return runtime.MemHash(unsafe.Pointer(&v), 0, unsafe.Sizeof(v)) @@ -1202,3 +1141,62 @@ func TestMapIterDeleteReplace(t *testing.T) { }) } } + +func TestHmapSize(t *testing.T) { + // The structure of Map is defined in internal/runtime/maps/map.go + // and in cmd/compile/internal/reflectdata/map.go and must be in sync. + // The size of Map should be 48 bytes on 64 bit and 32 bytes on 32 bit platforms. + wantSize := uintptr(2*8 + 4*goarch.PtrSize) + gotSize := unsafe.Sizeof(maps.Map{}) + if gotSize != wantSize { + t.Errorf("sizeof(maps.Map{})==%d, want %d", gotSize, wantSize) + } +} + +// See also reflect_test.TestGroupSizeZero. +func TestGroupSizeZero(t *testing.T) { + var m map[struct{}]struct{} + mTyp := abi.TypeOf(m) + mt := (*abi.SwissMapType)(unsafe.Pointer(mTyp)) + + // internal/runtime/maps when create pointers to slots, even if slots + // are size 0. The compiler should have reserved an extra word to + // ensure that pointers to the zero-size type at the end of group are + // valid. + if mt.Group.Size() <= 8 { + t.Errorf("Group size got %d want >8", mt.Group.Size()) + } +} + +func TestMapIterOrder(t *testing.T) { + sizes := []int{3, 7, 9, 15} + for _, n := range sizes { + for i := 0; i < 1000; i++ { + // Make m be {0: true, 1: true, ..., n-1: true}. + m := make(map[int]bool) + for i := 0; i < n; i++ { + m[i] = true + } + // Check that iterating over the map produces at least two different orderings. + ord := func() []int { + var s []int + for key := range m { + s = append(s, key) + } + return s + } + first := ord() + ok := false + for try := 0; try < 100; try++ { + if !slices.Equal(first, ord()) { + ok = true + break + } + } + if !ok { + t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) + break + } + } + } +} diff --git a/src/runtime/runtime-gdb.py b/src/runtime/runtime-gdb.py index 6d99515176..23b1f331c8 100644 --- a/src/runtime/runtime-gdb.py +++ b/src/runtime/runtime-gdb.py @@ -160,13 +160,6 @@ class MapTypePrinter: return str(self.val.type) def children(self): - fields = [f.name for f in self.val.type.strip_typedefs().target().fields()] - if 'buckets' in fields: - yield from self.old_map_children() - else: - yield from self.swiss_map_children() - - def swiss_map_children(self): SwissMapGroupSlots = 8 # see internal/abi:SwissMapGroupSlots cnt = 0 @@ -270,40 +263,6 @@ class MapTypePrinter: yield from group_slots(group) - def old_map_children(self): - MapBucketCount = 8 # see internal/abi:OldMapBucketCount - B = self.val['B'] - buckets = self.val['buckets'] - oldbuckets = self.val['oldbuckets'] - flags = self.val['flags'] - inttype = self.val['hash0'].type - cnt = 0 - for bucket in xrange(2 ** int(B)): - bp = buckets + bucket - if oldbuckets: - oldbucket = bucket & (2 ** (B - 1) - 1) - oldbp = oldbuckets + oldbucket - oldb = oldbp.dereference() - if (oldb['overflow'].cast(inttype) & 1) == 0: # old bucket not evacuated yet - if bucket >= 2 ** (B - 1): - continue # already did old bucket - bp = oldbp - while bp: - b = bp.dereference() - for i in xrange(MapBucketCount): - if b['tophash'][i] != 0: - k = b['keys'][i] - v = b['values'][i] - if flags & 1: - k = k.dereference() - if flags & 2: - v = v.dereference() - yield str(cnt), k - yield str(cnt + 1), v - cnt += 2 - bp = b['overflow'] - - class ChanTypePrinter: """Pretty print chan[T] types. diff --git a/src/runtime/runtime-gdb_test.go b/src/runtime/runtime-gdb_test.go index 47c1fe5851..e81efadeb3 100644 --- a/src/runtime/runtime-gdb_test.go +++ b/src/runtime/runtime-gdb_test.go @@ -8,8 +8,6 @@ import ( "bytes" "flag" "fmt" - "internal/abi" - "internal/goexperiment" "internal/testenv" "os" "os/exec" @@ -155,9 +153,6 @@ func checkPtraceScope(t *testing.T) { } } -// NOTE: the maps below are allocated larger than abi.MapBucketCount -// to ensure that they are not "optimized out". - var helloSource = ` import "fmt" import "runtime" @@ -166,19 +161,21 @@ var gslice []string var smallmapvar map[string]string func main() { smallmapvar = make(map[string]string) - mapvar := make(map[string]string, ` + strconv.FormatInt(abi.OldMapBucketCount+9, 10) + `) - slicemap := make(map[string][]string,` + strconv.FormatInt(abi.OldMapBucketCount+3, 10) + `) - chanint := make(chan int, 10) - chanstr := make(chan string, 10) - chanint <- 99 + // NOTE: the maps below are allocated large to ensure that they are not + // "optimized out". + mapvar := make(map[string]string, 10) + slicemap := make(map[string][]string, 10) + chanint := make(chan int, 10) + chanstr := make(chan string, 10) + chanint <- 99 chanint <- 11 - chanstr <- "spongepants" - chanstr <- "squarebob" + chanstr <- "spongepants" + chanstr <- "squarebob" smallmapvar["abc"] = "def" mapvar["abc"] = "def" mapvar["ghi"] = "jkl" slicemap["a"] = []string{"b","c","d"} - slicemap["e"] = []string{"f","g","h"} + slicemap["e"] = []string{"f","g","h"} strvar := "abc" ptrvar := &strvar slicevar := make([]string, 0, 16) @@ -638,20 +635,10 @@ func TestGdbAutotmpTypes(t *testing.T) { types := []string{ "[]main.astruct", "main.astruct", - } - if goexperiment.SwissMap { - types = append(types, []string{ - "groupReference<string,main.astruct>", - "table<string,main.astruct>", - "map<string,main.astruct>", - "map<string,main.astruct> * map[string]main.astruct", - }...) - } else { - types = append(types, []string{ - "bucket<string,main.astruct>", - "hash<string,main.astruct>", - "hash<string,main.astruct> * map[string]main.astruct", - }...) + "groupReference<string,main.astruct>", + "table<string,main.astruct>", + "map<string,main.astruct>", + "map<string,main.astruct> * map[string]main.astruct", } for _, name := range types { if !strings.Contains(sgot, name) { diff --git a/src/runtime/type.go b/src/runtime/type.go index baaaeafc4a..636ea3a485 100644 --- a/src/runtime/type.go +++ b/src/runtime/type.go @@ -9,7 +9,6 @@ package runtime import ( "internal/abi" "internal/goarch" - "internal/goexperiment" "internal/runtime/atomic" "unsafe" ) @@ -605,13 +604,8 @@ func typesEqual(t, v *_type, seen map[_typePair]struct{}) bool { } return true case abi.Map: - if goexperiment.SwissMap { - mt := (*abi.SwissMapType)(unsafe.Pointer(t)) - mv := (*abi.SwissMapType)(unsafe.Pointer(v)) - return typesEqual(mt.Key, mv.Key, seen) && typesEqual(mt.Elem, mv.Elem, seen) - } - mt := (*abi.OldMapType)(unsafe.Pointer(t)) - mv := (*abi.OldMapType)(unsafe.Pointer(v)) + mt := (*abi.SwissMapType)(unsafe.Pointer(t)) + mv := (*abi.SwissMapType)(unsafe.Pointer(v)) return typesEqual(mt.Key, mv.Key, seen) && typesEqual(mt.Elem, mv.Elem, seen) case abi.Pointer: pt := (*ptrtype)(unsafe.Pointer(t)) |
