Source file src/internal/runtime/maps/map.go
1 // Copyright 2024 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 5 // Package maps implements Go's builtin map type. 6 package maps 7 8 import ( 9 "internal/abi" 10 "internal/goarch" 11 "internal/runtime/math" 12 "internal/runtime/sys" 13 "unsafe" 14 ) 15 16 // This package contains the implementation of Go's builtin map type. 17 // 18 // The map design is based on Abseil's "Swiss Table" map design 19 // (https://abseil.io/about/design/swisstables), with additional modifications 20 // to cover Go's additional requirements, discussed below. 21 // 22 // Terminology: 23 // - Slot: A storage location of a single key/element pair. 24 // - Group: A group of abi.MapGroupSlots (8) slots, plus a control word. 25 // - Control word: An 8-byte word which denotes whether each slot is empty, 26 // deleted, or used. If a slot is used, its control byte also contains the 27 // lower 7 bits of the hash (H2). 28 // - H1: Upper 57 bits of a hash. 29 // - H2: Lower 7 bits of a hash. 30 // - Table: A complete "Swiss Table" hash table. A table consists of one or 31 // more groups for storage plus metadata to handle operation and determining 32 // when to grow. 33 // - Map: The top-level Map type consists of zero or more tables for storage. 34 // The upper bits of the hash select which table a key belongs to. 35 // - Directory: Array of the tables used by the map. 36 // 37 // At its core, the table design is similar to a traditional open-addressed 38 // hash table. Storage consists of an array of groups, which effectively means 39 // an array of key/elem slots with some control words interspersed. Lookup uses 40 // the hash to determine an initial group to check. If, due to collisions, this 41 // group contains no match, the probe sequence selects the next group to check 42 // (see below for more detail about the probe sequence). 43 // 44 // The key difference occurs within a group. In a standard open-addressed 45 // linear probed hash table, we would check each slot one at a time to find a 46 // match. A swiss table utilizes the extra control word to check all 8 slots in 47 // parallel. 48 // 49 // Each byte in the control word corresponds to one of the slots in the group. 50 // In each byte, 1 bit is used to indicate whether the slot is in use, or if it 51 // is empty/deleted. The other 7 bits contain the lower 7 bits of the hash for 52 // the key in that slot. See [ctrl] for the exact encoding. 53 // 54 // During lookup, we can use some clever bitwise manipulation to compare all 8 55 // 7-bit hashes against the input hash in parallel (see [ctrlGroup.matchH2]). 56 // That is, we effectively perform 8 steps of probing in a single operation. 57 // With SIMD instructions, this could be extended to 16 slots with a 16-byte 58 // control word. 59 // 60 // Since we only use 7 bits of the 64 bit hash, there is a 1 in 128 (~0.7%) 61 // probability of false positive on each slot, but that's fine: we always need 62 // double check each match with a standard key comparison regardless. 63 // 64 // Probing 65 // 66 // Probing is done using the upper 57 bits (H1) of the hash as an index into 67 // the groups array. Probing walks through the groups using quadratic probing 68 // until it finds a group with a match or a group with an empty slot. See 69 // [probeSeq] for specifics about the probe sequence. Note the probe 70 // invariants: the number of groups must be a power of two, and the end of a 71 // probe sequence must be a group with an empty slot (the table can never be 72 // 100% full). 73 // 74 // Deletion 75 // 76 // Probing stops when it finds a group with an empty slot. This affects 77 // deletion: when deleting from a completely full group, we must not mark the 78 // slot as empty, as there could be more slots used later in a probe sequence 79 // and this deletion would cause probing to stop too early. Instead, we mark 80 // such slots as "deleted" with a tombstone. If the group still has an empty 81 // slot, we don't need a tombstone and directly mark the slot empty. Insert 82 // prioritizes reuse of tombstones over filling an empty slots. Otherwise, 83 // tombstones are only completely cleared during grow, as an in-place cleanup 84 // complicates iteration. 85 // 86 // Growth 87 // 88 // The probe sequence depends on the number of groups. Thus, when growing the 89 // group count all slots must be reordered to match the new probe sequence. In 90 // other words, an entire table must be grown at once. 91 // 92 // In order to support incremental growth, the map splits its contents across 93 // multiple tables. Each table is still a full hash table, but an individual 94 // table may only service a subset of the hash space. Growth occurs on 95 // individual tables, so while an entire table must grow at once, each of these 96 // grows is only a small portion of a map. The maximum size of a single grow is 97 // limited by limiting the maximum size of a table before it is split into 98 // multiple tables. 99 // 100 // A map starts with a single table. Up to [maxTableCapacity], growth simply 101 // replaces this table with a replacement with double capacity. Beyond this 102 // limit, growth splits the table into two. 103 // 104 // The map uses "extendible hashing" to select which table to use. In 105 // extendible hashing, we use the upper bits of the hash as an index into an 106 // array of tables (called the "directory"). The number of bits uses increases 107 // as the number of tables increases. For example, when there is only 1 table, 108 // we use 0 bits (no selection necessary). When there are 2 tables, we use 1 109 // bit to select either the 0th or 1st table. [Map.globalDepth] is the number 110 // of bits currently used for table selection, and by extension (1 << 111 // globalDepth), the size of the directory. 112 // 113 // Note that each table has its own load factor and grows independently. If the 114 // 1st bucket grows, it will split. We'll need 2 bits to select tables, though 115 // we'll have 3 tables total rather than 4. We support this by allowing 116 // multiple indices to point to the same table. This example: 117 // 118 // directory (globalDepth=2) 119 // +----+ 120 // | 00 | --\ 121 // +----+ +--> table (localDepth=1) 122 // | 01 | --/ 123 // +----+ 124 // | 10 | ------> table (localDepth=2) 125 // +----+ 126 // | 11 | ------> table (localDepth=2) 127 // +----+ 128 // 129 // Tables track the depth they were created at (localDepth). It is necessary to 130 // grow the directory when splitting a table where globalDepth == localDepth. 131 // 132 // Iteration 133 // 134 // Iteration is the most complex part of the map due to Go's generous iteration 135 // semantics. A summary of semantics from the spec: 136 // 1. Adding and/or deleting entries during iteration MUST NOT cause iteration 137 // to return the same entry more than once. 138 // 2. Entries added during iteration MAY be returned by iteration. 139 // 3. Entries modified during iteration MUST return their latest value. 140 // 4. Entries deleted during iteration MUST NOT be returned by iteration. 141 // 5. Iteration order is unspecified. In the implementation, it is explicitly 142 // randomized. 143 // 144 // If the map never grows, these semantics are straightforward: just iterate 145 // over every table in the directory and every group and slot in each table. 146 // These semantics all land as expected. 147 // 148 // If the map grows during iteration, things complicate significantly. First 149 // and foremost, we need to track which entries we already returned to satisfy 150 // (1). There are three types of grow: 151 // a. A table replaced by a single larger table. 152 // b. A table split into two replacement tables. 153 // c. Growing the directory (occurs as part of (b) if necessary). 154 // 155 // For all of these cases, the replacement table(s) will have a different probe 156 // sequence, so simply tracking the current group and slot indices is not 157 // sufficient. 158 // 159 // For (a) and (b), note that grows of tables other than the one we are 160 // currently iterating over are irrelevant. 161 // 162 // We handle (a) and (b) by having the iterator keep a reference to the table 163 // it is currently iterating over, even after the table is replaced. We keep 164 // iterating over the original table to maintain the iteration order and avoid 165 // violating (1). Any new entries added only to the replacement table(s) will 166 // be skipped (allowed by (2)). To avoid violating (3) or (4), while we use the 167 // original table to select the keys, we must look them up again in the new 168 // table(s) to determine if they have been modified or deleted. There is yet 169 // another layer of complexity if the key does not compare equal itself. See 170 // [Iter.Next] for the gory details. 171 // 172 // Note that for (b) once we finish iterating over the old table we'll need to 173 // skip the next entry in the directory, as that contains the second split of 174 // the old table. We can use the old table's localDepth to determine the next 175 // logical index to use. 176 // 177 // For (b), we must adjust the current directory index when the directory 178 // grows. This is more straightforward, as the directory orders remains the 179 // same after grow, so we just double the index if the directory size doubles. 180 // 181 // Hashing Pointers 182 // 183 // Keys in Go maps can be pointers, or contain pointers. The hash of 184 // a pointer is a somewhat tricky concept, as pointers to stack 185 // objects can change during a stack copy. Because we hash a pointer 186 // by just hashing its uintptr-converted value, the hash of a key can 187 // potentially become stale across any stack copy. 188 // 189 // For keys that are stored into maps, we must avoid this. All key 190 // arguments to map assignments must have their pointer targets marked 191 // as escaping so that the hash of the key in the map is stable. This 192 // is true even when the map itself does not escape and can live on 193 // the stack. 194 // 195 // For keys that are used for lookup (or delete), it turns out that 196 // escaping is not required. If we are looking up a pointer which 197 // points to the stack, the hash value is ~irrelevant, as the key is 198 // guaranteed to not be in the map (due to the previous paragraph). 199 200 // Extracts the H1 portion of a hash: the 57 upper bits. 201 // TODO(prattmic): what about 32-bit systems? 202 func h1(h uintptr) uintptr { 203 return h >> 7 204 } 205 206 // Extracts the H2 portion of a hash: the 7 bits not used for h1. 207 // 208 // These are used as an occupied control byte. 209 func h2(h uintptr) uintptr { 210 return h & 0x7f 211 } 212 213 // Note: changes here must be reflected in cmd/compile/internal/reflectdata/map.go:MapType. 214 type Map struct { 215 // The number of filled slots (i.e. the number of elements in all 216 // tables). Excludes deleted slots. 217 // Must be first (known by the compiler, for len() builtin). 218 used uint64 219 220 // seed is the hash seed, computed as a unique random number per map. 221 seed uintptr 222 223 // The directory of tables. 224 // 225 // Normally dirPtr points to an array of table pointers 226 // 227 // dirPtr *[dirLen]*table 228 // 229 // The length (dirLen) of this array is `1 << globalDepth`. Multiple 230 // entries may point to the same table. See top-level comment for more 231 // details. 232 // 233 // Small map optimization: if the map always contained 234 // abi.MapGroupSlots or fewer entries, it fits entirely in a 235 // single group. In that case dirPtr points directly to a single group. 236 // 237 // dirPtr *group 238 // 239 // In this case, dirLen is 0. used counts the number of used slots in 240 // the group. Note that small maps never have deleted slots (as there 241 // is no probe sequence to maintain). 242 dirPtr unsafe.Pointer 243 dirLen int 244 245 // The number of bits to use in table directory lookups. 246 globalDepth uint8 247 248 // The number of bits to shift out of the hash for directory lookups. 249 // On 64-bit systems, this is 64 - globalDepth. 250 globalShift uint8 251 252 // writing is a flag that is toggled (XOR 1) while the map is being 253 // written. Normally it is set to 1 when writing, but if there are 254 // multiple concurrent writers, then toggling increases the probability 255 // that both sides will detect the race. 256 writing uint8 257 258 // tombstonePossible is false if we know that no table in this map 259 // contains a tombstone. 260 tombstonePossible bool 261 262 // clearSeq is a sequence counter of calls to Clear. It is used to 263 // detect map clears during iteration. 264 clearSeq uint64 265 } 266 267 // Use 64-bit hash on 64-bit systems, except on Wasm, where we use 268 // 32-bit hash (see runtime/hash32.go). 269 const Use64BitHash = goarch.PtrSize == 8 && goarch.IsWasm == 0 270 271 func depthToShift(depth uint8) uint8 { 272 if !Use64BitHash { 273 return 32 - depth 274 } 275 return 64 - depth 276 } 277 278 // If m is non-nil, it should be used rather than allocating. 279 // 280 // maxAlloc should be runtime.maxAlloc. 281 // 282 // TODO(prattmic): Put maxAlloc somewhere accessible. 283 func NewMap(mt *abi.MapType, hint uintptr, m *Map, maxAlloc uintptr) *Map { 284 if m == nil { 285 m = new(Map) 286 } 287 288 m.seed = uintptr(rand()) 289 290 if hint <= abi.MapGroupSlots { 291 // A small map can fill all 8 slots, so no need to increase 292 // target capacity. 293 // 294 // In fact, since an 8 slot group is what the first assignment 295 // to an empty map would allocate anyway, it doesn't matter if 296 // we allocate here or on the first assignment. 297 // 298 // Thus we just return without allocating. (We'll save the 299 // allocation completely if no assignment comes.) 300 301 // Note that the compiler may have initialized m.dirPtr with a 302 // pointer to a stack-allocated group, in which case we already 303 // have a group. The control word is already initialized. 304 305 return m 306 } 307 308 // Full size map. 309 310 // Set initial capacity to hold hint entries without growing in the 311 // average case. 312 targetCapacity := (hint * abi.MapGroupSlots) / maxAvgGroupLoad 313 if targetCapacity < hint { // overflow 314 return m // return an empty map. 315 } 316 317 dirSize := (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity 318 dirSize, overflow := alignUpPow2(dirSize) 319 if overflow || dirSize > uint64(math.MaxUintptr) { 320 return m // return an empty map. 321 } 322 323 // Reject hints that are obviously too large. 324 groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity) 325 if overflow { 326 return m // return an empty map. 327 } else { 328 mem, overflow := math.MulUintptr(groups, mt.GroupSize) 329 if overflow || mem > maxAlloc { 330 return m // return an empty map. 331 } 332 } 333 334 m.globalDepth = uint8(sys.TrailingZeros64(dirSize)) 335 m.globalShift = depthToShift(m.globalDepth) 336 337 directory := make([]*table, dirSize) 338 339 for i := range directory { 340 // TODO: Think more about initial table capacity. 341 directory[i] = newTable(mt, uint64(targetCapacity)/dirSize, i, m.globalDepth) 342 } 343 344 m.dirPtr = unsafe.Pointer(&directory[0]) 345 m.dirLen = len(directory) 346 347 return m 348 } 349 350 func NewEmptyMap() *Map { 351 m := new(Map) 352 m.seed = uintptr(rand()) 353 // See comment in NewMap. No need to eager allocate a group. 354 return m 355 } 356 357 func (m *Map) directoryIndex(hash uintptr) uintptr { 358 if m.dirLen == 1 { 359 return 0 360 } 361 return hash >> (m.globalShift & 63) 362 } 363 364 func (m *Map) directoryAt(i uintptr) *table { 365 return *(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i)) 366 } 367 368 func (m *Map) directorySet(i uintptr, nt *table) { 369 *(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i)) = nt 370 } 371 372 func (m *Map) replaceTable(nt *table) { 373 // The number of entries that reference the same table doubles for each 374 // time the globalDepth grows without the table splitting. 375 entries := 1 << (m.globalDepth - nt.localDepth) 376 for i := 0; i < entries; i++ { 377 //m.directory[nt.index+i] = nt 378 m.directorySet(uintptr(nt.index+i), nt) 379 } 380 } 381 382 func (m *Map) installTableSplit(old, left, right *table) { 383 if old.localDepth == m.globalDepth { 384 // No room for another level in the directory. Grow the 385 // directory. 386 newDir := make([]*table, m.dirLen*2) 387 for i := range m.dirLen { 388 t := m.directoryAt(uintptr(i)) 389 newDir[2*i] = t 390 newDir[2*i+1] = t 391 // t may already exist in multiple indices. We should 392 // only update t.index once. Since the index must 393 // increase, seeing the original index means this must 394 // be the first time we've encountered this table. 395 if t.index == i { 396 t.index = 2 * i 397 } 398 } 399 m.globalDepth++ 400 m.globalShift-- 401 //m.directory = newDir 402 m.dirPtr = unsafe.Pointer(&newDir[0]) 403 m.dirLen = len(newDir) 404 } 405 406 // N.B. left and right may still consume multiple indices if the 407 // directory has grown multiple times since old was last split. 408 left.index = old.index 409 m.replaceTable(left) 410 411 entries := 1 << (m.globalDepth - left.localDepth) 412 right.index = left.index + entries 413 m.replaceTable(right) 414 } 415 416 func (m *Map) Used() uint64 { 417 return m.used 418 } 419 420 // Get performs a lookup of the key that key points to. It returns a pointer to 421 // the element, or false if the key doesn't exist. 422 func (m *Map) Get(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, bool) { 423 return m.getWithoutKey(typ, key) 424 } 425 426 func (m *Map) getWithKey(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) { 427 if m.Used() == 0 { 428 return nil, nil, false 429 } 430 431 if m.writing != 0 { 432 fatal("concurrent map read and map write") 433 } 434 435 hash := typ.Hasher(key, m.seed) 436 437 if m.dirLen == 0 { 438 return m.getWithKeySmall(typ, hash, key) 439 } 440 441 idx := m.directoryIndex(hash) 442 return m.directoryAt(idx).getWithKey(typ, hash, key) 443 } 444 445 func (m *Map) getWithoutKey(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, bool) { 446 if m.Used() == 0 { 447 return nil, false 448 } 449 450 if m.writing != 0 { 451 fatal("concurrent map read and map write") 452 } 453 454 hash := typ.Hasher(key, m.seed) 455 456 if m.dirLen == 0 { 457 _, elem, ok := m.getWithKeySmall(typ, hash, key) 458 return elem, ok 459 } 460 461 idx := m.directoryIndex(hash) 462 return m.directoryAt(idx).getWithoutKey(typ, hash, key) 463 } 464 465 func (m *Map) getWithKeySmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) { 466 g := groupReference{ 467 data: m.dirPtr, 468 } 469 470 match := g.ctrls().matchH2(h2(hash)) 471 472 for match != 0 { 473 i := match.first() 474 475 slotKey := g.key(typ, i) 476 if typ.IndirectKey() { 477 slotKey = *((*unsafe.Pointer)(slotKey)) 478 } 479 480 if typ.Key.Equal(key, slotKey) { 481 slotElem := g.elem(typ, i) 482 if typ.IndirectElem() { 483 slotElem = *((*unsafe.Pointer)(slotElem)) 484 } 485 return slotKey, slotElem, true 486 } 487 488 match = match.removeFirst() 489 } 490 491 // No match here means key is not in the map. 492 // (A single group means no need to probe or check for empty). 493 return nil, nil, false 494 } 495 496 func (m *Map) Put(typ *abi.MapType, key, elem unsafe.Pointer) { 497 slotElem := m.PutSlot(typ, key) 498 typedmemmove(typ.Elem, slotElem, elem) 499 } 500 501 // PutSlot returns a pointer to the element slot where an inserted element 502 // should be written. 503 // 504 // PutSlot never returns nil. 505 func (m *Map) PutSlot(typ *abi.MapType, key unsafe.Pointer) unsafe.Pointer { 506 if m.writing != 0 { 507 fatal("concurrent map writes") 508 } 509 510 hash := typ.Hasher(key, m.seed) 511 512 // Set writing after calling Hasher, since Hasher may panic, in which 513 // case we have not actually done a write. 514 m.writing ^= 1 // toggle, see comment on writing 515 516 if m.dirPtr == nil { 517 m.growToSmall(typ) 518 } 519 520 if m.dirLen == 0 { 521 elem := m.putSlotSmall(typ, hash, key) 522 if elem == nil { 523 // Can't fit another entry, grow to full size map. 524 tab := m.growToTable(typ) 525 526 elem = tab.uncheckedPutSlotForAssign(typ, hash, key) 527 m.used++ 528 529 tab.checkInvariants(typ, m) 530 } 531 532 if m.writing == 0 { 533 fatal("concurrent map writes") 534 } 535 m.writing ^= 1 536 537 return elem 538 } 539 540 for { 541 idx := m.directoryIndex(hash) 542 elem, ok := m.directoryAt(idx).PutSlot(typ, m, hash, key) 543 if !ok { 544 continue 545 } 546 547 if m.writing == 0 { 548 fatal("concurrent map writes") 549 } 550 m.writing ^= 1 551 552 return elem 553 } 554 } 555 556 func (m *Map) putSlotSmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer { 557 g := groupReference{ 558 data: m.dirPtr, 559 } 560 561 match := g.ctrls().matchH2(h2(hash)) 562 563 // Look for an existing slot containing this key. 564 for match != 0 { 565 i := match.first() 566 567 slotKey := g.key(typ, i) 568 if typ.IndirectKey() { 569 slotKey = *((*unsafe.Pointer)(slotKey)) 570 } 571 if typ.Key.Equal(key, slotKey) { 572 if typ.NeedKeyUpdate() { 573 typedmemmove(typ.Key, slotKey, key) 574 } 575 576 slotElem := g.elem(typ, i) 577 if typ.IndirectElem() { 578 slotElem = *((*unsafe.Pointer)(slotElem)) 579 } 580 581 return slotElem 582 } 583 match = match.removeFirst() 584 } 585 586 // There can't be deleted slots, small maps can't have them 587 // (see deleteSmall). Use matchEmptyOrDeleted as it is a bit 588 // more efficient than matchEmpty. 589 match = g.ctrls().matchEmptyOrDeleted() 590 if match == 0 { 591 // No empty slot found. Need to grow the map. 592 return nil 593 } 594 595 i := match.first() 596 597 slotKey := g.key(typ, i) 598 if typ.IndirectKey() { 599 kmem := newobject(typ.Key) 600 *(*unsafe.Pointer)(slotKey) = kmem 601 slotKey = kmem 602 } 603 typedmemmove(typ.Key, slotKey, key) 604 605 slotElem := g.elem(typ, i) 606 if typ.IndirectElem() { 607 emem := newobject(typ.Elem) 608 *(*unsafe.Pointer)(slotElem) = emem 609 slotElem = emem 610 } 611 612 g.ctrls().set(i, ctrl(h2(hash))) 613 m.used++ 614 615 return slotElem 616 } 617 618 func (m *Map) growToSmall(typ *abi.MapType) { 619 grp := newGroups(typ, 1) 620 m.dirPtr = grp.data 621 622 g := groupReference{ 623 data: m.dirPtr, 624 } 625 g.ctrls().setEmpty() 626 } 627 628 func (m *Map) growToTable(typ *abi.MapType) *table { 629 tab := newTable(typ, 2*abi.MapGroupSlots, 0, 0) 630 631 g := groupReference{ 632 data: m.dirPtr, 633 } 634 635 for i := uintptr(0); i < abi.MapGroupSlots; i++ { 636 if (g.ctrls().get(i) & ctrlEmpty) == ctrlEmpty { 637 // Empty 638 continue 639 } 640 641 key := g.key(typ, i) 642 if typ.IndirectKey() { 643 key = *((*unsafe.Pointer)(key)) 644 } 645 646 elem := g.elem(typ, i) 647 if typ.IndirectElem() { 648 elem = *((*unsafe.Pointer)(elem)) 649 } 650 651 hash := typ.Hasher(key, m.seed) 652 653 tab.uncheckedPutSlot(typ, hash, key, elem) 654 } 655 656 directory := make([]*table, 1) 657 658 directory[0] = tab 659 660 m.dirPtr = unsafe.Pointer(&directory[0]) 661 m.dirLen = len(directory) 662 663 m.globalDepth = 0 664 m.globalShift = depthToShift(m.globalDepth) 665 return tab 666 } 667 668 func (m *Map) Delete(typ *abi.MapType, key unsafe.Pointer) { 669 if m == nil || m.Used() == 0 { 670 if err := mapKeyError(typ, key); err != nil { 671 panic(err) // see issue 23734 672 } 673 return 674 } 675 676 if m.writing != 0 { 677 fatal("concurrent map writes") 678 } 679 680 hash := typ.Hasher(key, m.seed) 681 682 // Set writing after calling Hasher, since Hasher may panic, in which 683 // case we have not actually done a write. 684 m.writing ^= 1 // toggle, see comment on writing 685 686 if m.dirLen == 0 { 687 m.deleteSmall(typ, hash, key) 688 } else { 689 idx := m.directoryIndex(hash) 690 if m.directoryAt(idx).Delete(typ, m, hash, key) { 691 m.tombstonePossible = true 692 } 693 } 694 695 if m.used == 0 { 696 // Reset the hash seed to make it more difficult for attackers 697 // to repeatedly trigger hash collisions. See 698 // https://go.dev/issue/25237. 699 m.seed = uintptr(rand()) 700 } 701 702 if m.writing == 0 { 703 fatal("concurrent map writes") 704 } 705 m.writing ^= 1 706 } 707 708 func (m *Map) deleteSmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) { 709 g := groupReference{ 710 data: m.dirPtr, 711 } 712 713 match := g.ctrls().matchH2(h2(hash)) 714 715 for match != 0 { 716 i := match.first() 717 slotKey := g.key(typ, i) 718 origSlotKey := slotKey 719 if typ.IndirectKey() { 720 slotKey = *((*unsafe.Pointer)(slotKey)) 721 } 722 if typ.Key.Equal(key, slotKey) { 723 m.used-- 724 725 if typ.IndirectKey() { 726 // Clearing the pointer is sufficient. 727 *(*unsafe.Pointer)(origSlotKey) = nil 728 } else if typ.Key.Pointers() { 729 // Only bother clearing if there are pointers. 730 typedmemclr(typ.Key, slotKey) 731 } 732 733 slotElem := g.elem(typ, i) 734 if typ.IndirectElem() { 735 // Clearing the pointer is sufficient. 736 *(*unsafe.Pointer)(slotElem) = nil 737 } else { 738 // Unlike keys, always clear the elem (even if 739 // it contains no pointers), as compound 740 // assignment operations depend on cleared 741 // deleted values. See 742 // https://go.dev/issue/25936. 743 typedmemclr(typ.Elem, slotElem) 744 } 745 746 // We only have 1 group, so it is OK to immediately 747 // reuse deleted slots. 748 g.ctrls().set(i, ctrlEmpty) 749 return 750 } 751 match = match.removeFirst() 752 } 753 } 754 755 // Clear deletes all entries from the map resulting in an empty map. 756 func (m *Map) Clear(typ *abi.MapType) { 757 if m == nil || m.Used() == 0 && !m.tombstonePossible { 758 return 759 } 760 761 if m.writing != 0 { 762 fatal("concurrent map writes") 763 } 764 m.writing ^= 1 // toggle, see comment on writing 765 766 if m.dirLen == 0 { 767 m.clearSmall(typ) 768 } else { 769 var lastTab *table 770 for i := range m.dirLen { 771 t := m.directoryAt(uintptr(i)) 772 if t == lastTab { 773 continue 774 } 775 t.Clear(typ) 776 lastTab = t 777 } 778 m.used = 0 779 m.tombstonePossible = false 780 // TODO: shrink directory? 781 } 782 m.clearSeq++ 783 784 // Reset the hash seed to make it more difficult for attackers to 785 // repeatedly trigger hash collisions. See https://go.dev/issue/25237. 786 m.seed = uintptr(rand()) 787 788 if m.writing == 0 { 789 fatal("concurrent map writes") 790 } 791 m.writing ^= 1 792 } 793 794 func (m *Map) clearSmall(typ *abi.MapType) { 795 g := groupReference{ 796 data: m.dirPtr, 797 } 798 799 typedmemclr(typ.Group, g.data) 800 g.ctrls().setEmpty() 801 802 m.used = 0 803 } 804 805 func (m *Map) Clone(typ *abi.MapType) *Map { 806 // Note: this should never be called with a nil map. 807 if m.writing != 0 { 808 fatal("concurrent map clone and map write") 809 } 810 811 // Shallow copy the Map structure. 812 m2 := new(Map) 813 *m2 = *m 814 m = m2 815 816 // We need to just deep copy the dirPtr field. 817 if m.dirPtr == nil { 818 // delayed group allocation, nothing to do. 819 } else if m.dirLen == 0 { 820 // Clone one group. 821 oldGroup := groupReference{data: m.dirPtr} 822 newGroup := groupReference{data: newGroups(typ, 1).data} 823 cloneGroup(typ, newGroup, oldGroup) 824 m.dirPtr = newGroup.data 825 } else { 826 // Clone each (different) table. 827 oldDir := unsafe.Slice((**table)(m.dirPtr), m.dirLen) 828 newDir := make([]*table, m.dirLen) 829 for i, t := range oldDir { 830 if i > 0 && t == oldDir[i-1] { 831 newDir[i] = newDir[i-1] 832 continue 833 } 834 newDir[i] = t.clone(typ) 835 } 836 m.dirPtr = unsafe.Pointer(&newDir[0]) 837 } 838 839 return m 840 } 841 842 func mapKeyError(t *abi.MapType, p unsafe.Pointer) error { 843 if !t.HashMightPanic() { 844 return nil 845 } 846 return mapKeyError2(t.Key, p) 847 } 848 849 func mapKeyError2(t *abi.Type, p unsafe.Pointer) error { 850 if t.TFlag&abi.TFlagRegularMemory != 0 { 851 return nil 852 } 853 switch t.Kind() { 854 case abi.Float32, abi.Float64, abi.Complex64, abi.Complex128, abi.String: 855 return nil 856 case abi.Interface: 857 i := (*abi.InterfaceType)(unsafe.Pointer(t)) 858 var t *abi.Type 859 var pdata *unsafe.Pointer 860 if len(i.Methods) == 0 { 861 a := (*abi.EmptyInterface)(p) 862 t = a.Type 863 if t == nil { 864 return nil 865 } 866 pdata = &a.Data 867 } else { 868 a := (*abi.NonEmptyInterface)(p) 869 if a.ITab == nil { 870 return nil 871 } 872 t = a.ITab.Type 873 pdata = &a.Data 874 } 875 876 if t.Equal == nil { 877 return unhashableTypeError{t} 878 } 879 880 if t.IsDirectIface() { 881 return mapKeyError2(t, unsafe.Pointer(pdata)) 882 } else { 883 return mapKeyError2(t, *pdata) 884 } 885 case abi.Array: 886 a := (*abi.ArrayType)(unsafe.Pointer(t)) 887 for i := uintptr(0); i < a.Len; i++ { 888 if err := mapKeyError2(a.Elem, unsafe.Pointer(uintptr(p)+i*a.Elem.Size_)); err != nil { 889 return err 890 } 891 } 892 return nil 893 case abi.Struct: 894 s := (*abi.StructType)(unsafe.Pointer(t)) 895 for _, f := range s.Fields { 896 if f.Name.IsBlank() { 897 continue 898 } 899 if err := mapKeyError2(f.Typ, unsafe.Pointer(uintptr(p)+f.Offset)); err != nil { 900 return err 901 } 902 } 903 return nil 904 default: 905 // Should never happen, keep this case for robustness. 906 return unhashableTypeError{t} 907 } 908 } 909 910 type unhashableTypeError struct{ typ *abi.Type } 911 912 func (unhashableTypeError) RuntimeError() {} 913 914 func (e unhashableTypeError) Error() string { return "hash of unhashable type: " + typeString(e.typ) } 915 916 // Pushed from runtime 917 // 918 //go:linkname typeString 919 func typeString(typ *abi.Type) string 920