// 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<> (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< 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<= 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< bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } // tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1< 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) } }