1// Copyright 2014 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package runtime 6 7// This file contains the implementation of Go's map type. 8// 9// A map is just a hash table. The data is arranged 10// into an array of buckets. Each bucket contains up to 11// 8 key/elem pairs. The low-order bits of the hash are 12// used to select a bucket. Each bucket contains a few 13// high-order bits of each hash to distinguish the entries 14// within a single bucket. 15// 16// If more than 8 keys hash to a bucket, we chain on 17// extra buckets. 18// 19// When the hashtable grows, we allocate a new array 20// of buckets twice as big. Buckets are incrementally 21// copied from the old bucket array to the new bucket array. 22// 23// Map iterators walk through the array of buckets and 24// return the keys in walk order (bucket #, then overflow 25// chain order, then bucket index). To maintain iteration 26// semantics, we never move keys within their bucket (if 27// we did, keys might be returned 0 or 2 times). When 28// growing the table, iterators remain iterating through the 29// old table and must check the new table if the bucket 30// they are iterating through has been moved ("evacuated") 31// to the new table. 32 33// Picking loadFactor: too large and we have lots of overflow 34// buckets, too small and we waste a lot of space. I wrote 35// a simple program to check some stats for different loads: 36// (64-bit, 8 byte keys and elems) 37// loadFactor %overflow bytes/entry hitprobe missprobe 38// 4.00 2.13 20.77 3.00 4.00 39// 4.50 4.05 17.30 3.25 4.50 40// 5.00 6.85 14.77 3.50 5.00 41// 5.50 10.55 12.94 3.75 5.50 42// 6.00 15.27 11.67 4.00 6.00 43// 6.50 20.90 10.79 4.25 6.50 44// 7.00 27.14 10.15 4.50 7.00 45// 7.50 34.03 9.73 4.75 7.50 46// 8.00 41.10 9.40 5.00 8.00 47// 48// %overflow = percentage of buckets which have an overflow bucket 49// bytes/entry = overhead bytes used per key/elem pair 50// hitprobe = # of entries to check when looking up a present key 51// missprobe = # of entries to check when looking up an absent key 52// 53// Keep in mind this data is for maximally loaded tables, i.e. just 54// before the table grows. Typical tables will be somewhat less loaded. 55 56import ( 57 "runtime/internal/atomic" 58 "runtime/internal/math" 59 "runtime/internal/sys" 60 "unsafe" 61) 62 63const ( 64 // Maximum number of key/elem pairs a bucket can hold. 65 bucketCntBits = 3 66 bucketCnt = 1 << bucketCntBits 67 68 // Maximum average load of a bucket that triggers growth is 6.5. 69 // Represent as loadFactorNum/loadFactDen, to allow integer math. 70 loadFactorNum = 13 71 loadFactorDen = 2 72 73 // Maximum key or elem size to keep inline (instead of mallocing per element). 74 // Must fit in a uint8. 75 // Fast versions cannot handle big elems - the cutoff size for 76 // fast versions in cmd/compile/internal/gc/walk.go must be at most this elem. 77 maxKeySize = 128 78 maxElemSize = 128 79 80 // data offset should be the size of the bmap struct, but needs to be 81 // aligned correctly. For amd64p32 this means 64-bit alignment 82 // even though pointers are 32 bit. 83 dataOffset = unsafe.Offsetof(struct { 84 b bmap 85 v int64 86 }{}.v) 87 88 // Possible tophash values. We reserve a few possibilities for special marks. 89 // Each bucket (including its overflow buckets, if any) will have either all or none of its 90 // entries in the evacuated* states (except during the evacuate() method, which only happens 91 // during map writes and thus no one else can observe the map during that time). 92 emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. 93 emptyOne = 1 // this cell is empty 94 evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table. 95 evacuatedY = 3 // same as above, but evacuated to second half of larger table. 96 evacuatedEmpty = 4 // cell is empty, bucket is evacuated. 97 minTopHash = 5 // minimum tophash for a normal filled cell. 98 99 // flags 100 iterator = 1 // there may be an iterator using buckets 101 oldIterator = 2 // there may be an iterator using oldbuckets 102 hashWriting = 4 // a goroutine is writing to the map 103 sameSizeGrow = 8 // the current map growth is to a new map of the same size 104 105 // sentinel bucket ID for iterator checks 106 noCheck = 1<<(8*sys.PtrSize) - 1 107) 108 109// isEmpty reports whether the given tophash array entry represents an empty bucket entry. 110func isEmpty(x uint8) bool { 111 return x <= emptyOne 112} 113 114// A header for a Go map. 115type hmap struct { 116 // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go. 117 // Make sure this stays in sync with the compiler's definition. 118 count int // # live cells == size of map. Must be first (used by len() builtin) 119 flags uint8 120 B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) 121 noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 122 hash0 uint32 // hash seed 123 124 buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. 125 oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing 126 nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) 127 128 extra *mapextra // optional fields 129} 130 131// mapextra holds fields that are not present on all maps. 132type mapextra struct { 133 // If both key and elem do not contain pointers and are inline, then we mark bucket 134 // type as containing no pointers. This avoids scanning such maps. 135 // However, bmap.overflow is a pointer. In order to keep overflow buckets 136 // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow. 137 // overflow and oldoverflow are only used if key and elem do not contain pointers. 138 // overflow contains overflow buckets for hmap.buckets. 139 // oldoverflow contains overflow buckets for hmap.oldbuckets. 140 // The indirection allows to store a pointer to the slice in hiter. 141 overflow *[]*bmap 142 oldoverflow *[]*bmap 143 144 // nextOverflow holds a pointer to a free overflow bucket. 145 nextOverflow *bmap 146} 147 148// A bucket for a Go map. 149type bmap struct { 150 // tophash generally contains the top byte of the hash value 151 // for each key in this bucket. If tophash[0] < minTopHash, 152 // tophash[0] is a bucket evacuation state instead. 153 tophash [bucketCnt]uint8 154 // Followed by bucketCnt keys and then bucketCnt elems. 155 // NOTE: packing all the keys together and then all the elems together makes the 156 // code a bit more complicated than alternating key/elem/key/elem/... but it allows 157 // us to eliminate padding which would be needed for, e.g., map[int64]int8. 158 // Followed by an overflow pointer. 159} 160 161// A hash iteration structure. 162// If you modify hiter, also change cmd/compile/internal/gc/reflect.go to indicate 163// the layout of this structure. 164type hiter struct { 165 key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/internal/gc/range.go). 166 elem unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go). 167 t *maptype 168 h *hmap 169 buckets unsafe.Pointer // bucket ptr at hash_iter initialization time 170 bptr *bmap // current bucket 171 overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive 172 oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive 173 startBucket uintptr // bucket iteration started at 174 offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) 175 wrapped bool // already wrapped around from end of bucket array to beginning 176 B uint8 177 i uint8 178 bucket uintptr 179 checkBucket uintptr 180} 181 182// bucketShift returns 1<<b, optimized for code generation. 183func bucketShift(b uint8) uintptr { 184 // Masking the shift amount allows overflow checks to be elided. 185 return uintptr(1) << (b & (sys.PtrSize*8 - 1)) 186} 187 188// bucketMask returns 1<<b - 1, optimized for code generation. 189func bucketMask(b uint8) uintptr { 190 return bucketShift(b) - 1 191} 192 193// tophash calculates the tophash value for hash. 194func tophash(hash uintptr) uint8 { 195 top := uint8(hash >> (sys.PtrSize*8 - 8)) 196 if top < minTopHash { 197 top += minTopHash 198 } 199 return top 200} 201 202func evacuated(b *bmap) bool { 203 h := b.tophash[0] 204 return h > emptyOne && h < minTopHash 205} 206 207func (b *bmap) overflow(t *maptype) *bmap { 208 return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) 209} 210 211func (b *bmap) setoverflow(t *maptype, ovf *bmap) { 212 *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf 213} 214 215func (b *bmap) keys() unsafe.Pointer { 216 return add(unsafe.Pointer(b), dataOffset) 217} 218 219// incrnoverflow increments h.noverflow. 220// noverflow counts the number of overflow buckets. 221// This is used to trigger same-size map growth. 222// See also tooManyOverflowBuckets. 223// To keep hmap small, noverflow is a uint16. 224// When there are few buckets, noverflow is an exact count. 225// When there are many buckets, noverflow is an approximate count. 226func (h *hmap) incrnoverflow() { 227 // We trigger same-size map growth if there are 228 // as many overflow buckets as buckets. 229 // We need to be able to count to 1<<h.B. 230 if h.B < 16 { 231 h.noverflow++ 232 return 233 } 234 // Increment with probability 1/(1<<(h.B-15)). 235 // When we reach 1<<15 - 1, we will have approximately 236 // as many overflow buckets as buckets. 237 mask := uint32(1)<<(h.B-15) - 1 238 // Example: if h.B == 18, then mask == 7, 239 // and fastrand & 7 == 0 with probability 1/8. 240 if fastrand()&mask == 0 { 241 h.noverflow++ 242 } 243} 244 245func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap { 246 var ovf *bmap 247 if h.extra != nil && h.extra.nextOverflow != nil { 248 // We have preallocated overflow buckets available. 249 // See makeBucketArray for more details. 250 ovf = h.extra.nextOverflow 251 if ovf.overflow(t) == nil { 252 // We're not at the end of the preallocated overflow buckets. Bump the pointer. 253 h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize))) 254 } else { 255 // This is the last preallocated overflow bucket. 256 // Reset the overflow pointer on this bucket, 257 // which was set to a non-nil sentinel value. 258 ovf.setoverflow(t, nil) 259 h.extra.nextOverflow = nil 260 } 261 } else { 262 ovf = (*bmap)(newobject(t.bucket)) 263 } 264 h.incrnoverflow() 265 if t.bucket.ptrdata == 0 { 266 h.createOverflow() 267 *h.extra.overflow = append(*h.extra.overflow, ovf) 268 } 269 b.setoverflow(t, ovf) 270 return ovf 271} 272 273func (h *hmap) createOverflow() { 274 if h.extra == nil { 275 h.extra = new(mapextra) 276 } 277 if h.extra.overflow == nil { 278 h.extra.overflow = new([]*bmap) 279 } 280} 281 282func makemap64(t *maptype, hint int64, h *hmap) *hmap { 283 if int64(int(hint)) != hint { 284 hint = 0 285 } 286 return makemap(t, int(hint), h) 287} 288 289// makemap_small implements Go map creation for make(map[k]v) and 290// make(map[k]v, hint) when hint is known to be at most bucketCnt 291// at compile time and the map needs to be allocated on the heap. 292func makemap_small() *hmap { 293 h := new(hmap) 294 h.hash0 = fastrand() 295 return h 296} 297 298// makemap implements Go map creation for make(map[k]v, hint). 299// If the compiler has determined that the map or the first bucket 300// can be created on the stack, h and/or bucket may be non-nil. 301// If h != nil, the map can be created directly in h. 302// If h.buckets != nil, bucket pointed to can be used as the first bucket. 303func makemap(t *maptype, hint int, h *hmap) *hmap { 304 mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) 305 if overflow || mem > maxAlloc { 306 hint = 0 307 } 308 309 // initialize Hmap 310 if h == nil { 311 h = new(hmap) 312 } 313 h.hash0 = fastrand() 314 315 // Find the size parameter B which will hold the requested # of elements. 316 // For hint < 0 overLoadFactor returns false since hint < bucketCnt. 317 B := uint8(0) 318 for overLoadFactor(hint, B) { 319 B++ 320 } 321 h.B = B 322 323 // allocate initial hash table 324 // if B == 0, the buckets field is allocated lazily later (in mapassign) 325 // If hint is large zeroing this memory could take a while. 326 if h.B != 0 { 327 var nextOverflow *bmap 328 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) 329 if nextOverflow != nil { 330 h.extra = new(mapextra) 331 h.extra.nextOverflow = nextOverflow 332 } 333 } 334 335 return h 336} 337 338// makeBucketArray initializes a backing array for map buckets. 339// 1<<b is the minimum number of buckets to allocate. 340// dirtyalloc should either be nil or a bucket array previously 341// allocated by makeBucketArray with the same t and b parameters. 342// If dirtyalloc is nil a new backing array will be alloced and 343// otherwise dirtyalloc will be cleared and reused as backing array. 344func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) { 345 base := bucketShift(b) 346 nbuckets := base 347 // For small b, overflow buckets are unlikely. 348 // Avoid the overhead of the calculation. 349 if b >= 4 { 350 // Add on the estimated number of overflow buckets 351 // required to insert the median number of elements 352 // used with this value of b. 353 nbuckets += bucketShift(b - 4) 354 sz := t.bucket.size * nbuckets 355 up := roundupsize(sz) 356 if up != sz { 357 nbuckets = up / t.bucket.size 358 } 359 } 360 361 if dirtyalloc == nil { 362 buckets = newarray(t.bucket, int(nbuckets)) 363 } else { 364 // dirtyalloc was previously generated by 365 // the above newarray(t.bucket, int(nbuckets)) 366 // but may not be empty. 367 buckets = dirtyalloc 368 size := t.bucket.size * nbuckets 369 if t.bucket.ptrdata != 0 { 370 memclrHasPointers(buckets, size) 371 } else { 372 memclrNoHeapPointers(buckets, size) 373 } 374 } 375 376 if base != nbuckets { 377 // We preallocated some overflow buckets. 378 // To keep the overhead of tracking these overflow buckets to a minimum, 379 // we use the convention that if a preallocated overflow bucket's overflow 380 // pointer is nil, then there are more available by bumping the pointer. 381 // We need a safe non-nil pointer for the last overflow bucket; just use buckets. 382 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) 383 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) 384 last.setoverflow(t, (*bmap)(buckets)) 385 } 386 return buckets, nextOverflow 387} 388 389// mapaccess1 returns a pointer to h[key]. Never returns nil, instead 390// it will return a reference to the zero object for the elem type if 391// the key is not in the map. 392// NOTE: The returned pointer may keep the whole map live, so don't 393// hold onto it for very long. 394func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { 395 if raceenabled && h != nil { 396 callerpc := getcallerpc() 397 pc := funcPC(mapaccess1) 398 racereadpc(unsafe.Pointer(h), callerpc, pc) 399 raceReadObjectPC(t.key, key, callerpc, pc) 400 } 401 if msanenabled && h != nil { 402 msanread(key, t.key.size) 403 } 404 if h == nil || h.count == 0 { 405 if t.hashMightPanic() { 406 t.hasher(key, 0) // see issue 23734 407 } 408 return unsafe.Pointer(&zeroVal[0]) 409 } 410 if h.flags&hashWriting != 0 { 411 throw("concurrent map read and map write") 412 } 413 hash := t.hasher(key, uintptr(h.hash0)) 414 m := bucketMask(h.B) 415 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) 416 if c := h.oldbuckets; c != nil { 417 if !h.sameSizeGrow() { 418 // There used to be half as many buckets; mask down one more power of two. 419 m >>= 1 420 } 421 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) 422 if !evacuated(oldb) { 423 b = oldb 424 } 425 } 426 top := tophash(hash) 427bucketloop: 428 for ; b != nil; b = b.overflow(t) { 429 for i := uintptr(0); i < bucketCnt; i++ { 430 if b.tophash[i] != top { 431 if b.tophash[i] == emptyRest { 432 break bucketloop 433 } 434 continue 435 } 436 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 437 if t.indirectkey() { 438 k = *((*unsafe.Pointer)(k)) 439 } 440 if t.key.equal(key, k) { 441 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 442 if t.indirectelem() { 443 e = *((*unsafe.Pointer)(e)) 444 } 445 return e 446 } 447 } 448 } 449 return unsafe.Pointer(&zeroVal[0]) 450} 451 452func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { 453 if raceenabled && h != nil { 454 callerpc := getcallerpc() 455 pc := funcPC(mapaccess2) 456 racereadpc(unsafe.Pointer(h), callerpc, pc) 457 raceReadObjectPC(t.key, key, callerpc, pc) 458 } 459 if msanenabled && h != nil { 460 msanread(key, t.key.size) 461 } 462 if h == nil || h.count == 0 { 463 if t.hashMightPanic() { 464 t.hasher(key, 0) // see issue 23734 465 } 466 return unsafe.Pointer(&zeroVal[0]), false 467 } 468 if h.flags&hashWriting != 0 { 469 throw("concurrent map read and map write") 470 } 471 hash := t.hasher(key, uintptr(h.hash0)) 472 m := bucketMask(h.B) 473 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) 474 if c := h.oldbuckets; c != nil { 475 if !h.sameSizeGrow() { 476 // There used to be half as many buckets; mask down one more power of two. 477 m >>= 1 478 } 479 oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) 480 if !evacuated(oldb) { 481 b = oldb 482 } 483 } 484 top := tophash(hash) 485bucketloop: 486 for ; b != nil; b = b.overflow(t) { 487 for i := uintptr(0); i < bucketCnt; i++ { 488 if b.tophash[i] != top { 489 if b.tophash[i] == emptyRest { 490 break bucketloop 491 } 492 continue 493 } 494 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 495 if t.indirectkey() { 496 k = *((*unsafe.Pointer)(k)) 497 } 498 if t.key.equal(key, k) { 499 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 500 if t.indirectelem() { 501 e = *((*unsafe.Pointer)(e)) 502 } 503 return e, true 504 } 505 } 506 } 507 return unsafe.Pointer(&zeroVal[0]), false 508} 509 510// returns both key and elem. Used by map iterator 511func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) { 512 if h == nil || h.count == 0 { 513 return nil, nil 514 } 515 hash := t.hasher(key, uintptr(h.hash0)) 516 m := bucketMask(h.B) 517 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) 518 if c := h.oldbuckets; c != nil { 519 if !h.sameSizeGrow() { 520 // There used to be half as many buckets; mask down one more power of two. 521 m >>= 1 522 } 523 oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) 524 if !evacuated(oldb) { 525 b = oldb 526 } 527 } 528 top := tophash(hash) 529bucketloop: 530 for ; b != nil; b = b.overflow(t) { 531 for i := uintptr(0); i < bucketCnt; i++ { 532 if b.tophash[i] != top { 533 if b.tophash[i] == emptyRest { 534 break bucketloop 535 } 536 continue 537 } 538 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 539 if t.indirectkey() { 540 k = *((*unsafe.Pointer)(k)) 541 } 542 if t.key.equal(key, k) { 543 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 544 if t.indirectelem() { 545 e = *((*unsafe.Pointer)(e)) 546 } 547 return k, e 548 } 549 } 550 } 551 return nil, nil 552} 553 554func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer { 555 e := mapaccess1(t, h, key) 556 if e == unsafe.Pointer(&zeroVal[0]) { 557 return zero 558 } 559 return e 560} 561 562func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) { 563 e := mapaccess1(t, h, key) 564 if e == unsafe.Pointer(&zeroVal[0]) { 565 return zero, false 566 } 567 return e, true 568} 569 570// Like mapaccess, but allocates a slot for the key if it is not present in the map. 571func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { 572 if h == nil { 573 panic(plainError("assignment to entry in nil map")) 574 } 575 if raceenabled { 576 callerpc := getcallerpc() 577 pc := funcPC(mapassign) 578 racewritepc(unsafe.Pointer(h), callerpc, pc) 579 raceReadObjectPC(t.key, key, callerpc, pc) 580 } 581 if msanenabled { 582 msanread(key, t.key.size) 583 } 584 if h.flags&hashWriting != 0 { 585 throw("concurrent map writes") 586 } 587 hash := t.hasher(key, uintptr(h.hash0)) 588 589 // Set hashWriting after calling t.hasher, since t.hasher may panic, 590 // in which case we have not actually done a write. 591 h.flags ^= hashWriting 592 593 if h.buckets == nil { 594 h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) 595 } 596 597again: 598 bucket := hash & bucketMask(h.B) 599 if h.growing() { 600 growWork(t, h, bucket) 601 } 602 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) 603 top := tophash(hash) 604 605 var inserti *uint8 606 var insertk unsafe.Pointer 607 var elem unsafe.Pointer 608bucketloop: 609 for { 610 for i := uintptr(0); i < bucketCnt; i++ { 611 if b.tophash[i] != top { 612 if isEmpty(b.tophash[i]) && inserti == nil { 613 inserti = &b.tophash[i] 614 insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 615 elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 616 } 617 if b.tophash[i] == emptyRest { 618 break bucketloop 619 } 620 continue 621 } 622 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 623 if t.indirectkey() { 624 k = *((*unsafe.Pointer)(k)) 625 } 626 if !t.key.equal(key, k) { 627 continue 628 } 629 // already have a mapping for key. Update it. 630 if t.needkeyupdate() { 631 typedmemmove(t.key, k, key) 632 } 633 elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 634 goto done 635 } 636 ovf := b.overflow(t) 637 if ovf == nil { 638 break 639 } 640 b = ovf 641 } 642 643 // Did not find mapping for key. Allocate new cell & add entry. 644 645 // If we hit the max load factor or we have too many overflow buckets, 646 // and we're not already in the middle of growing, start growing. 647 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { 648 hashGrow(t, h) 649 goto again // Growing the table invalidates everything, so try again 650 } 651 652 if inserti == nil { 653 // all current buckets are full, allocate a new one. 654 newb := h.newoverflow(t, b) 655 inserti = &newb.tophash[0] 656 insertk = add(unsafe.Pointer(newb), dataOffset) 657 elem = add(insertk, bucketCnt*uintptr(t.keysize)) 658 } 659 660 // store new key/elem at insert position 661 if t.indirectkey() { 662 kmem := newobject(t.key) 663 *(*unsafe.Pointer)(insertk) = kmem 664 insertk = kmem 665 } 666 if t.indirectelem() { 667 vmem := newobject(t.elem) 668 *(*unsafe.Pointer)(elem) = vmem 669 } 670 typedmemmove(t.key, insertk, key) 671 *inserti = top 672 h.count++ 673 674done: 675 if h.flags&hashWriting == 0 { 676 throw("concurrent map writes") 677 } 678 h.flags &^= hashWriting 679 if t.indirectelem() { 680 elem = *((*unsafe.Pointer)(elem)) 681 } 682 return elem 683} 684 685func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { 686 if raceenabled && h != nil { 687 callerpc := getcallerpc() 688 pc := funcPC(mapdelete) 689 racewritepc(unsafe.Pointer(h), callerpc, pc) 690 raceReadObjectPC(t.key, key, callerpc, pc) 691 } 692 if msanenabled && h != nil { 693 msanread(key, t.key.size) 694 } 695 if h == nil || h.count == 0 { 696 if t.hashMightPanic() { 697 t.hasher(key, 0) // see issue 23734 698 } 699 return 700 } 701 if h.flags&hashWriting != 0 { 702 throw("concurrent map writes") 703 } 704 705 hash := t.hasher(key, uintptr(h.hash0)) 706 707 // Set hashWriting after calling t.hasher, since t.hasher may panic, 708 // in which case we have not actually done a write (delete). 709 h.flags ^= hashWriting 710 711 bucket := hash & bucketMask(h.B) 712 if h.growing() { 713 growWork(t, h, bucket) 714 } 715 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) 716 bOrig := b 717 top := tophash(hash) 718search: 719 for ; b != nil; b = b.overflow(t) { 720 for i := uintptr(0); i < bucketCnt; i++ { 721 if b.tophash[i] != top { 722 if b.tophash[i] == emptyRest { 723 break search 724 } 725 continue 726 } 727 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) 728 k2 := k 729 if t.indirectkey() { 730 k2 = *((*unsafe.Pointer)(k2)) 731 } 732 if !t.key.equal(key, k2) { 733 continue 734 } 735 // Only clear key if there are pointers in it. 736 if t.indirectkey() { 737 *(*unsafe.Pointer)(k) = nil 738 } else if t.key.ptrdata != 0 { 739 memclrHasPointers(k, t.key.size) 740 } 741 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) 742 if t.indirectelem() { 743 *(*unsafe.Pointer)(e) = nil 744 } else if t.elem.ptrdata != 0 { 745 memclrHasPointers(e, t.elem.size) 746 } else { 747 memclrNoHeapPointers(e, t.elem.size) 748 } 749 b.tophash[i] = emptyOne 750 // If the bucket now ends in a bunch of emptyOne states, 751 // change those to emptyRest states. 752 // It would be nice to make this a separate function, but 753 // for loops are not currently inlineable. 754 if i == bucketCnt-1 { 755 if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { 756 goto notLast 757 } 758 } else { 759 if b.tophash[i+1] != emptyRest { 760 goto notLast 761 } 762 } 763 for { 764 b.tophash[i] = emptyRest 765 if i == 0 { 766 if b == bOrig { 767 break // beginning of initial bucket, we're done. 768 } 769 // Find previous bucket, continue at its last entry. 770 c := b 771 for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { 772 } 773 i = bucketCnt - 1 774 } else { 775 i-- 776 } 777 if b.tophash[i] != emptyOne { 778 break 779 } 780 } 781 notLast: 782 h.count-- 783 break search 784 } 785 } 786 787 if h.flags&hashWriting == 0 { 788 throw("concurrent map writes") 789 } 790 h.flags &^= hashWriting 791} 792 793// mapiterinit initializes the hiter struct used for ranging over maps. 794// The hiter struct pointed to by 'it' is allocated on the stack 795// by the compilers order pass or on the heap by reflect_mapiterinit. 796// Both need to have zeroed hiter since the struct contains pointers. 797func mapiterinit(t *maptype, h *hmap, it *hiter) { 798 if raceenabled && h != nil { 799 callerpc := getcallerpc() 800 racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit)) 801 } 802 803 if h == nil || h.count == 0 { 804 return 805 } 806 807 if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 { 808 throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go 809 } 810 it.t = t 811 it.h = h 812 813 // grab snapshot of bucket state 814 it.B = h.B 815 it.buckets = h.buckets 816 if t.bucket.ptrdata == 0 { 817 // Allocate the current slice and remember pointers to both current and old. 818 // This preserves all relevant overflow buckets alive even if 819 // the table grows and/or overflow buckets are added to the table 820 // while we are iterating. 821 h.createOverflow() 822 it.overflow = h.extra.overflow 823 it.oldoverflow = h.extra.oldoverflow 824 } 825 826 // decide where to start 827 r := uintptr(fastrand()) 828 if h.B > 31-bucketCntBits { 829 r += uintptr(fastrand()) << 31 830 } 831 it.startBucket = r & bucketMask(h.B) 832 it.offset = uint8(r >> h.B & (bucketCnt - 1)) 833 834 // iterator state 835 it.bucket = it.startBucket 836 837 // Remember we have an iterator. 838 // Can run concurrently with another mapiterinit(). 839 if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator { 840 atomic.Or8(&h.flags, iterator|oldIterator) 841 } 842 843 mapiternext(it) 844} 845 846func mapiternext(it *hiter) { 847 h := it.h 848 if raceenabled { 849 callerpc := getcallerpc() 850 racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext)) 851 } 852 if h.flags&hashWriting != 0 { 853 throw("concurrent map iteration and map write") 854 } 855 t := it.t 856 bucket := it.bucket 857 b := it.bptr 858 i := it.i 859 checkBucket := it.checkBucket 860 861next: 862 if b == nil { 863 if bucket == it.startBucket && it.wrapped { 864 // end of iteration 865 it.key = nil 866 it.elem = nil 867 return 868 } 869 if h.growing() && it.B == h.B { 870 // Iterator was started in the middle of a grow, and the grow isn't done yet. 871 // If the bucket we're looking at hasn't been filled in yet (i.e. the old 872 // bucket hasn't been evacuated) then we need to iterate through the old 873 // bucket and only return the ones that will be migrated to this bucket. 874 oldbucket := bucket & it.h.oldbucketmask() 875 b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) 876 if !evacuated(b) { 877 checkBucket = bucket 878 } else { 879 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) 880 checkBucket = noCheck 881 } 882 } else { 883 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) 884 checkBucket = noCheck 885 } 886 bucket++ 887 if bucket == bucketShift(it.B) { 888 bucket = 0 889 it.wrapped = true 890 } 891 i = 0 892 } 893 for ; i < bucketCnt; i++ { 894 offi := (i + it.offset) & (bucketCnt - 1) 895 if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { 896 // TODO: emptyRest is hard to use here, as we start iterating 897 // in the middle of a bucket. It's feasible, just tricky. 898 continue 899 } 900 k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) 901 if t.indirectkey() { 902 k = *((*unsafe.Pointer)(k)) 903 } 904 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize)) 905 if checkBucket != noCheck && !h.sameSizeGrow() { 906 // Special case: iterator was started during a grow to a larger size 907 // and the grow is not done yet. We're working on a bucket whose 908 // oldbucket has not been evacuated yet. Or at least, it wasn't 909 // evacuated when we started the bucket. So we're iterating 910 // through the oldbucket, skipping any keys that will go 911 // to the other new bucket (each oldbucket expands to two 912 // buckets during a grow). 913 if t.reflexivekey() || t.key.equal(k, k) { 914 // If the item in the oldbucket is not destined for 915 // the current new bucket in the iteration, skip it. 916 hash := t.hasher(k, uintptr(h.hash0)) 917 if hash&bucketMask(it.B) != checkBucket { 918 continue 919 } 920 } else { 921 // Hash isn't repeatable if k != k (NaNs). We need a 922 // repeatable and randomish choice of which direction 923 // to send NaNs during evacuation. We'll use the low 924 // bit of tophash to decide which way NaNs go. 925 // NOTE: this case is why we need two evacuate tophash 926 // values, evacuatedX and evacuatedY, that differ in 927 // their low bit. 928 if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { 929 continue 930 } 931 } 932 } 933 if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || 934 !(t.reflexivekey() || t.key.equal(k, k)) { 935 // This is the golden data, we can return it. 936 // OR 937 // key!=key, so the entry can't be deleted or updated, so we can just return it. 938 // That's lucky for us because when key!=key we can't look it up successfully. 939 it.key = k 940 if t.indirectelem() { 941 e = *((*unsafe.Pointer)(e)) 942 } 943 it.elem = e 944 } else { 945 // The hash table has grown since the iterator was started. 946 // The golden data for this key is now somewhere else. 947 // Check the current hash table for the data. 948 // This code handles the case where the key 949 // has been deleted, updated, or deleted and reinserted. 950 // NOTE: we need to regrab the key as it has potentially been 951 // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). 952 rk, re := mapaccessK(t, h, k) 953 if rk == nil { 954 continue // key has been deleted 955 } 956 it.key = rk 957 it.elem = re 958 } 959 it.bucket = bucket 960 if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 961 it.bptr = b 962 } 963 it.i = i + 1 964 it.checkBucket = checkBucket 965 return 966 } 967 b = b.overflow(t) 968 i = 0 969 goto next 970} 971 972// mapclear deletes all keys from a map. 973func mapclear(t *maptype, h *hmap) { 974 if raceenabled && h != nil { 975 callerpc := getcallerpc() 976 pc := funcPC(mapclear) 977 racewritepc(unsafe.Pointer(h), callerpc, pc) 978 } 979 980 if h == nil || h.count == 0 { 981 return 982 } 983 984 if h.flags&hashWriting != 0 { 985 throw("concurrent map writes") 986 } 987 988 h.flags ^= hashWriting 989 990 h.flags &^= sameSizeGrow 991 h.oldbuckets = nil 992 h.nevacuate = 0 993 h.noverflow = 0 994 h.count = 0 995 996 // Keep the mapextra allocation but clear any extra information. 997 if h.extra != nil { 998 *h.extra = mapextra{} 999 } 1000 1001 // makeBucketArray clears the memory pointed to by h.buckets 1002 // and recovers any overflow buckets by generating them 1003 // as if h.buckets was newly alloced. 1004 _, nextOverflow := makeBucketArray(t, h.B, h.buckets) 1005 if nextOverflow != nil { 1006 // If overflow buckets are created then h.extra 1007 // will have been allocated during initial bucket creation. 1008 h.extra.nextOverflow = nextOverflow 1009 } 1010 1011 if h.flags&hashWriting == 0 { 1012 throw("concurrent map writes") 1013 } 1014 h.flags &^= hashWriting 1015} 1016 1017func hashGrow(t *maptype, h *hmap) { 1018 // If we've hit the load factor, get bigger. 1019 // Otherwise, there are too many overflow buckets, 1020 // so keep the same number of buckets and "grow" laterally. 1021 bigger := uint8(1) 1022 if !overLoadFactor(h.count+1, h.B) { 1023 bigger = 0 1024 h.flags |= sameSizeGrow 1025 } 1026 oldbuckets := h.buckets 1027 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) 1028 1029 flags := h.flags &^ (iterator | oldIterator) 1030 if h.flags&iterator != 0 { 1031 flags |= oldIterator 1032 } 1033 // commit the grow (atomic wrt gc) 1034 h.B += bigger 1035 h.flags = flags 1036 h.oldbuckets = oldbuckets 1037 h.buckets = newbuckets 1038 h.nevacuate = 0 1039 h.noverflow = 0 1040 1041 if h.extra != nil && h.extra.overflow != nil { 1042 // Promote current overflow buckets to the old generation. 1043 if h.extra.oldoverflow != nil { 1044 throw("oldoverflow is not nil") 1045 } 1046 h.extra.oldoverflow = h.extra.overflow 1047 h.extra.overflow = nil 1048 } 1049 if nextOverflow != nil { 1050 if h.extra == nil { 1051 h.extra = new(mapextra) 1052 } 1053 h.extra.nextOverflow = nextOverflow 1054 } 1055 1056 // the actual copying of the hash table data is done incrementally 1057 // by growWork() and evacuate(). 1058} 1059 1060// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor. 1061func overLoadFactor(count int, B uint8) bool { 1062 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) 1063} 1064 1065// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets. 1066// Note that most of these overflow buckets must be in sparse use; 1067// if use was dense, then we'd have already triggered regular map growth. 1068func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { 1069 // If the threshold is too low, we do extraneous work. 1070 // If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory. 1071 // "too many" means (approximately) as many overflow buckets as regular buckets. 1072 // See incrnoverflow for more details. 1073 if B > 15 { 1074 B = 15 1075 } 1076 // The compiler doesn't see here that B < 16; mask B to generate shorter shift code. 1077 return noverflow >= uint16(1)<<(B&15) 1078} 1079 1080// growing reports whether h is growing. The growth may be to the same size or bigger. 1081func (h *hmap) growing() bool { 1082 return h.oldbuckets != nil 1083} 1084 1085// sameSizeGrow reports whether the current growth is to a map of the same size. 1086func (h *hmap) sameSizeGrow() bool { 1087 return h.flags&sameSizeGrow != 0 1088} 1089 1090// noldbuckets calculates the number of buckets prior to the current map growth. 1091func (h *hmap) noldbuckets() uintptr { 1092 oldB := h.B 1093 if !h.sameSizeGrow() { 1094 oldB-- 1095 } 1096 return bucketShift(oldB) 1097} 1098 1099// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets(). 1100func (h *hmap) oldbucketmask() uintptr { 1101 return h.noldbuckets() - 1 1102} 1103 1104func growWork(t *maptype, h *hmap, bucket uintptr) { 1105 // make sure we evacuate the oldbucket corresponding 1106 // to the bucket we're about to use 1107 evacuate(t, h, bucket&h.oldbucketmask()) 1108 1109 // evacuate one more oldbucket to make progress on growing 1110 if h.growing() { 1111 evacuate(t, h, h.nevacuate) 1112 } 1113} 1114 1115func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool { 1116 b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize))) 1117 return evacuated(b) 1118} 1119 1120// evacDst is an evacuation destination. 1121type evacDst struct { 1122 b *bmap // current destination bucket 1123 i int // key/elem index into b 1124 k unsafe.Pointer // pointer to current key storage 1125 e unsafe.Pointer // pointer to current elem storage 1126} 1127 1128func evacuate(t *maptype, h *hmap, oldbucket uintptr) { 1129 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) 1130 newbit := h.noldbuckets() 1131 if !evacuated(b) { 1132 // TODO: reuse overflow buckets instead of using new ones, if there 1133 // is no iterator using the old buckets. (If !oldIterator.) 1134 1135 // xy contains the x and y (low and high) evacuation destinations. 1136 var xy [2]evacDst 1137 x := &xy[0] 1138 x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) 1139 x.k = add(unsafe.Pointer(x.b), dataOffset) 1140 x.e = add(x.k, bucketCnt*uintptr(t.keysize)) 1141 1142 if !h.sameSizeGrow() { 1143 // Only calculate y pointers if we're growing bigger. 1144 // Otherwise GC can see bad pointers. 1145 y := &xy[1] 1146 y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) 1147 y.k = add(unsafe.Pointer(y.b), dataOffset) 1148 y.e = add(y.k, bucketCnt*uintptr(t.keysize)) 1149 } 1150 1151 for ; b != nil; b = b.overflow(t) { 1152 k := add(unsafe.Pointer(b), dataOffset) 1153 e := add(k, bucketCnt*uintptr(t.keysize)) 1154 for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) { 1155 top := b.tophash[i] 1156 if isEmpty(top) { 1157 b.tophash[i] = evacuatedEmpty 1158 continue 1159 } 1160 if top < minTopHash { 1161 throw("bad map state") 1162 } 1163 k2 := k 1164 if t.indirectkey() { 1165 k2 = *((*unsafe.Pointer)(k2)) 1166 } 1167 var useY uint8 1168 if !h.sameSizeGrow() { 1169 // Compute hash to make our evacuation decision (whether we need 1170 // to send this key/elem to bucket x or bucket y). 1171 hash := t.hasher(k2, uintptr(h.hash0)) 1172 if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) { 1173 // If key != key (NaNs), then the hash could be (and probably 1174 // will be) entirely different from the old hash. Moreover, 1175 // it isn't reproducible. Reproducibility is required in the 1176 // presence of iterators, as our evacuation decision must 1177 // match whatever decision the iterator made. 1178 // Fortunately, we have the freedom to send these keys either 1179 // way. Also, tophash is meaningless for these kinds of keys. 1180 // We let the low bit of tophash drive the evacuation decision. 1181 // We recompute a new random tophash for the next level so 1182 // these keys will get evenly distributed across all buckets 1183 // after multiple grows. 1184 useY = top & 1 1185 top = tophash(hash) 1186 } else { 1187 if hash&newbit != 0 { 1188 useY = 1 1189 } 1190 } 1191 } 1192 1193 if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { 1194 throw("bad evacuatedN") 1195 } 1196 1197 b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY 1198 dst := &xy[useY] // evacuation destination 1199 1200 if dst.i == bucketCnt { 1201 dst.b = h.newoverflow(t, dst.b) 1202 dst.i = 0 1203 dst.k = add(unsafe.Pointer(dst.b), dataOffset) 1204 dst.e = add(dst.k, bucketCnt*uintptr(t.keysize)) 1205 } 1206 dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check 1207 if t.indirectkey() { 1208 *(*unsafe.Pointer)(dst.k) = k2 // copy pointer 1209 } else { 1210 typedmemmove(t.key, dst.k, k) // copy elem 1211 } 1212 if t.indirectelem() { 1213 *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e) 1214 } else { 1215 typedmemmove(t.elem, dst.e, e) 1216 } 1217 dst.i++ 1218 // These updates might push these pointers past the end of the 1219 // key or elem arrays. That's ok, as we have the overflow pointer 1220 // at the end of the bucket to protect against pointing past the 1221 // end of the bucket. 1222 dst.k = add(dst.k, uintptr(t.keysize)) 1223 dst.e = add(dst.e, uintptr(t.elemsize)) 1224 } 1225 } 1226 // Unlink the overflow buckets & clear key/elem to help GC. 1227 if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 { 1228 b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) 1229 // Preserve b.tophash because the evacuation 1230 // state is maintained there. 1231 ptr := add(b, dataOffset) 1232 n := uintptr(t.bucketsize) - dataOffset 1233 memclrHasPointers(ptr, n) 1234 } 1235 } 1236 1237 if oldbucket == h.nevacuate { 1238 advanceEvacuationMark(h, t, newbit) 1239 } 1240} 1241 1242func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { 1243 h.nevacuate++ 1244 // Experiments suggest that 1024 is overkill by at least an order of magnitude. 1245 // Put it in there as a safeguard anyway, to ensure O(1) behavior. 1246 stop := h.nevacuate + 1024 1247 if stop > newbit { 1248 stop = newbit 1249 } 1250 for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { 1251 h.nevacuate++ 1252 } 1253 if h.nevacuate == newbit { // newbit == # of oldbuckets 1254 // Growing is all done. Free old main bucket array. 1255 h.oldbuckets = nil 1256 // Can discard old overflow buckets as well. 1257 // If they are still referenced by an iterator, 1258 // then the iterator holds a pointers to the slice. 1259 if h.extra != nil { 1260 h.extra.oldoverflow = nil 1261 } 1262 h.flags &^= sameSizeGrow 1263 } 1264} 1265 1266// Reflect stubs. Called from ../reflect/asm_*.s 1267 1268//go:linkname reflect_makemap reflect.makemap 1269func reflect_makemap(t *maptype, cap int) *hmap { 1270 // Check invariants and reflects math. 1271 if t.key.equal == nil { 1272 throw("runtime.reflect_makemap: unsupported map key type") 1273 } 1274 if t.key.size > maxKeySize && (!t.indirectkey() || t.keysize != uint8(sys.PtrSize)) || 1275 t.key.size <= maxKeySize && (t.indirectkey() || t.keysize != uint8(t.key.size)) { 1276 throw("key size wrong") 1277 } 1278 if t.elem.size > maxElemSize && (!t.indirectelem() || t.elemsize != uint8(sys.PtrSize)) || 1279 t.elem.size <= maxElemSize && (t.indirectelem() || t.elemsize != uint8(t.elem.size)) { 1280 throw("elem size wrong") 1281 } 1282 if t.key.align > bucketCnt { 1283 throw("key align too big") 1284 } 1285 if t.elem.align > bucketCnt { 1286 throw("elem align too big") 1287 } 1288 if t.key.size%uintptr(t.key.align) != 0 { 1289 throw("key size not a multiple of key align") 1290 } 1291 if t.elem.size%uintptr(t.elem.align) != 0 { 1292 throw("elem size not a multiple of elem align") 1293 } 1294 if bucketCnt < 8 { 1295 throw("bucketsize too small for proper alignment") 1296 } 1297 if dataOffset%uintptr(t.key.align) != 0 { 1298 throw("need padding in bucket (key)") 1299 } 1300 if dataOffset%uintptr(t.elem.align) != 0 { 1301 throw("need padding in bucket (elem)") 1302 } 1303 1304 return makemap(t, cap, nil) 1305} 1306 1307//go:linkname reflect_mapaccess reflect.mapaccess 1308func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { 1309 elem, ok := mapaccess2(t, h, key) 1310 if !ok { 1311 // reflect wants nil for a missing element 1312 elem = nil 1313 } 1314 return elem 1315} 1316 1317//go:linkname reflect_mapassign reflect.mapassign 1318func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, elem unsafe.Pointer) { 1319 p := mapassign(t, h, key) 1320 typedmemmove(t.elem, p, elem) 1321} 1322 1323//go:linkname reflect_mapdelete reflect.mapdelete 1324func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { 1325 mapdelete(t, h, key) 1326} 1327 1328//go:linkname reflect_mapiterinit reflect.mapiterinit 1329func reflect_mapiterinit(t *maptype, h *hmap) *hiter { 1330 it := new(hiter) 1331 mapiterinit(t, h, it) 1332 return it 1333} 1334 1335//go:linkname reflect_mapiternext reflect.mapiternext 1336func reflect_mapiternext(it *hiter) { 1337 mapiternext(it) 1338} 1339 1340//go:linkname reflect_mapiterkey reflect.mapiterkey 1341func reflect_mapiterkey(it *hiter) unsafe.Pointer { 1342 return it.key 1343} 1344 1345//go:linkname reflect_mapiterelem reflect.mapiterelem 1346func reflect_mapiterelem(it *hiter) unsafe.Pointer { 1347 return it.elem 1348} 1349 1350//go:linkname reflect_maplen reflect.maplen 1351func reflect_maplen(h *hmap) int { 1352 if h == nil { 1353 return 0 1354 } 1355 if raceenabled { 1356 callerpc := getcallerpc() 1357 racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen)) 1358 } 1359 return h.count 1360} 1361 1362//go:linkname reflectlite_maplen internal/reflectlite.maplen 1363func reflectlite_maplen(h *hmap) int { 1364 if h == nil { 1365 return 0 1366 } 1367 if raceenabled { 1368 callerpc := getcallerpc() 1369 racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen)) 1370 } 1371 return h.count 1372} 1373 1374const maxZero = 1024 // must match value in cmd/compile/internal/gc/walk.go:zeroValSize 1375var zeroVal [maxZero]byte 1376