diff options
Diffstat (limited to 'src/runtime/map.go')
| -rw-r--r-- | src/runtime/map.go | 1732 |
1 files changed, 1732 insertions, 0 deletions
diff --git a/src/runtime/map.go b/src/runtime/map.go new file mode 100644 index 0000000..cd3f838 --- /dev/null +++ b/src/runtime/map.go @@ -0,0 +1,1732 @@ +// 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. + +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" + "runtime/internal/atomic" + "runtime/internal/math" + "unsafe" +) + +const ( + // Maximum number of key/elem pairs a bucket can hold. + bucketCntBits = abi.MapBucketCountBits + bucketCnt = abi.MapBucketCount + + // 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 * bucketCnt * 13 / 16 + + // Maximum key or elem size to keep inline (instead of mallocing per element). + // Must fit in a uint8. + // Fast versions cannot handle big elems - the cutoff size for + // fast versions in cmd/compile/internal/gc/walk.go must be at most this elem. + maxKeySize = abi.MapMaxKeyBytes + maxElemSize = abi.MapMaxElemBytes + + // 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) + + 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 [bucketCnt]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 +} + +// 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.PtrBytes == 0 { + 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. +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. +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.PtrBytes == 0) + 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.PtrBytes != 0 { + 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 := 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 := mapKeyError(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 < bucketCnt; 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+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + if t.IndirectElem() { + e = *((*unsafe.Pointer)(e)) + } + return e + } + } + } + return unsafe.Pointer(&zeroVal[0]) +} + +func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { + if raceenabled && h != nil { + callerpc := 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 := mapKeyError(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 < bucketCnt; 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+bucketCnt*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 < bucketCnt; 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+bucketCnt*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. +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 := 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 < bucketCnt; 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+bucketCnt*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+bucketCnt*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, bucketCnt*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 +} + +func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { + if raceenabled && h != nil { + callerpc := 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 := mapKeyError(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 < bucketCnt; 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.PtrBytes != 0 { + memclrHasPointers(k, t.Key.Size_) + } + e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + if t.IndirectElem() { + *(*unsafe.Pointer)(e) = nil + } else if t.Elem.PtrBytes != 0 { + 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 == bucketCnt-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 = bucketCnt - 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. +func mapiterinit(t *maptype, h *hmap, it *hiter) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiterinit)) + } + + it.t = t + if h == nil || h.count == 0 { + return + } + + if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 { + throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go + } + it.h = h + + // grab snapshot of bucket state + it.B = h.B + it.buckets = h.buckets + if t.Bucket.PtrBytes == 0 { + // 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 & (bucketCnt - 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) +} + +func mapiternext(it *hiter) { + h := it.h + if raceenabled { + callerpc := 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 < bucketCnt; i++ { + offi := (i + it.offset) & (bucketCnt - 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+bucketCnt*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 (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. +func mapclear(t *maptype, h *hmap) { + if raceenabled && h != nil { + callerpc := 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 + + // Mark buckets empty, so existing iterators can be terminated, see issue #59411. + markBucketsEmpty := func(bucket unsafe.Pointer, mask uintptr) { + for i := uintptr(0); i <= mask; i++ { + b := (*bmap)(add(bucket, i*uintptr(t.BucketSize))) + for ; b != nil; b = b.overflow(t) { + for i := uintptr(0); i < bucketCnt; i++ { + b.tophash[i] = emptyRest + } + } + } + } + markBucketsEmpty(h.buckets, bucketMask(h.B)) + if oldBuckets := h.oldbuckets; oldBuckets != nil { + markBucketsEmpty(oldBuckets, h.oldbucketmask()) + } + + h.flags &^= sameSizeGrow + h.oldbuckets = nil + h.nevacuate = 0 + h.noverflow = 0 + h.count = 0 + + // 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 > bucketCnt && 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 +} + +// 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, bucketCnt*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, bucketCnt*uintptr(t.KeySize)) + } + + for ; b != nil; b = b.overflow(t) { + k := add(unsafe.Pointer(b), dataOffset) + e := add(k, bucketCnt*uintptr(t.KeySize)) + for i := 0; i < bucketCnt; 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 == bucketCnt { + dst.b = h.newoverflow(t, dst.b) + dst.i = 0 + dst.k = add(unsafe.Pointer(dst.b), dataOffset) + dst.e = add(dst.k, bucketCnt*uintptr(t.KeySize)) + } + dst.b.tophash[dst.i&(bucketCnt-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.PtrBytes != 0 { + 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 + +//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_ > maxKeySize && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || + t.Key.Size_ <= maxKeySize && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { + throw("key size wrong") + } + if t.Elem.Size_ > maxElemSize && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || + t.Elem.Size_ <= maxElemSize && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { + throw("elem size wrong") + } + if t.Key.Align_ > bucketCnt { + throw("key align too big") + } + if t.Elem.Align_ > bucketCnt { + 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 bucketCnt < 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) +} + +//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 +} + +//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) +} + +//go:linkname reflect_mapiterinit reflect.mapiterinit +func reflect_mapiterinit(t *maptype, h *hmap, it *hiter) { + mapiterinit(t, h, it) +} + +//go:linkname reflect_mapiternext reflect.mapiternext +func reflect_mapiternext(it *hiter) { + mapiternext(it) +} + +//go:linkname reflect_mapiterkey reflect.mapiterkey +func reflect_mapiterkey(it *hiter) unsafe.Pointer { + return it.key +} + +//go:linkname reflect_mapiterelem reflect.mapiterelem +func reflect_mapiterelem(it *hiter) unsafe.Pointer { + return it.elem +} + +//go:linkname reflect_maplen reflect.maplen +func reflect_maplen(h *hmap) int { + if h == nil { + return 0 + } + if raceenabled { + callerpc := 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 := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(reflect_maplen)) + } + return h.count +} + +var zeroVal [abi.ZeroValSize]byte + +// 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 < bucketCnt; i++ { + if isEmpty(src.tophash[i]) { + continue + } + + for ; pos < bucketCnt; pos++ { + if isEmpty(dst.tophash[pos]) { + break + } + } + + if pos == bucketCnt { + dst = h.newoverflow(t, dst) + pos = 0 + } + + srcK := add(unsafe.Pointer(src), dataOffset+uintptr(i)*uintptr(t.KeySize)) + srcEle := add(unsafe.Pointer(src), dataOffset+bucketCnt*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+bucketCnt*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 { + dst := makemap(t, src.count, 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 < bucketCnt; 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+bucketCnt*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 & (bucketCnt - 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 < bucketCnt; i++ { + offi := (i + uintptr(offset)) & (bucketCnt - 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 & (bucketCnt - 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 < bucketCnt; i++ { + offi := (i + uintptr(offset)) & (bucketCnt - 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+bucketCnt*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) + } +} |