runtime: implement experiment to replace heap bitmap with alloc headers

[gostls13.git] / src / runtime / map.go

// 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 fastrand & 7 == 0 with probability 1/8.
        if fastrand()&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 = fastrand()
        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 = fastrand()

        // 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 = fastrand()
                        }
                        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
        var r uintptr
        if h.B > 31-bucketCntBits {
                r = uintptr(fastrand64())
        } else {
                r = uintptr(fastrand())
        }
        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 = fastrand()

        // 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
}

const maxZero = 1024 // must match value in reflect/value.go:maxZero cmd/compile/internal/gc/walk.go:zeroValSize
var zeroVal [maxZero]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() {
                        *(*unsafe.Pointer)(dstK) = *(*unsafe.Pointer)(srcK)
                } else {
                        typedmemmove(t.Key, dstK, srcK)
                }
                if t.IndirectElem() {
                        *(*unsafe.Pointer)(dstEle) = *(*unsafe.Pointer)(srcEle)
                } 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 {
                dst.buckets = newobject(t.Bucket)
                dst.count = src.count
                typedmemmove(t.Bucket, dst.buckets, src.buckets)
                return dst
        }

        //src.B != 0
        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
                }

                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(fastrand())
        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(fastrand())
        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)
        }
}