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.SwissMapGroupSlots (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 indicies 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 // Extracts the H1 portion of a hash: the 57 upper bits.
182 // TODO(prattmic): what about 32-bit systems?
183 func h1(h uintptr) uintptr {
184 return h >> 7
185 }
186 187 // Extracts the H2 portion of a hash: the 7 bits not used for h1.
188 //
189 // These are used as an occupied control byte.
190 func h2(h uintptr) uintptr {
191 return h & 0x7f
192 }
193 194 // Note: changes here must be reflected in cmd/compile/internal/reflectdata/map_swiss.go:SwissMapType.
195 type Map struct {
196 // The number of filled slots (i.e. the number of elements in all
197 // tables). Excludes deleted slots.
198 // Must be first (known by the compiler, for len() builtin).
199 used uint64
200 201 // seed is the hash seed, computed as a unique random number per map.
202 seed uintptr
203 204 // The directory of tables.
205 //
206 // Normally dirPtr points to an array of table pointers
207 //
208 // dirPtr *[dirLen]*table
209 //
210 // The length (dirLen) of this array is `1 << globalDepth`. Multiple
211 // entries may point to the same table. See top-level comment for more
212 // details.
213 //
214 // Small map optimization: if the map always contained
215 // abi.SwissMapGroupSlots or fewer entries, it fits entirely in a
216 // single group. In that case dirPtr points directly to a single group.
217 //
218 // dirPtr *group
219 //
220 // In this case, dirLen is 0. used counts the number of used slots in
221 // the group. Note that small maps never have deleted slots (as there
222 // is no probe sequence to maintain).
223 dirPtr unsafe.Pointer
224 dirLen int
225 226 // The number of bits to use in table directory lookups.
227 globalDepth uint8
228 229 // The number of bits to shift out of the hash for directory lookups.
230 // On 64-bit systems, this is 64 - globalDepth.
231 globalShift uint8
232 233 // writing is a flag that is toggled (XOR 1) while the map is being
234 // written. Normally it is set to 1 when writing, but if there are
235 // multiple concurrent writers, then toggling increases the probability
236 // that both sides will detect the race.
237 writing uint8
238 239 // tombstonePossible is false if we know that no table in this map
240 // contains a tombstone.
241 tombstonePossible bool
242 243 // clearSeq is a sequence counter of calls to Clear. It is used to
244 // detect map clears during iteration.
245 clearSeq uint64
246 }
247 248 func depthToShift(depth uint8) uint8 {
249 if goarch.PtrSize == 4 {
250 return 32 - depth
251 }
252 return 64 - depth
253 }
254 255 // If m is non-nil, it should be used rather than allocating.
256 //
257 // maxAlloc should be runtime.maxAlloc.
258 //
259 // TODO(prattmic): Put maxAlloc somewhere accessible.
260 func NewMap(mt *abi.SwissMapType, hint uintptr, m *Map, maxAlloc uintptr) *Map {
261 if m == nil {
262 m = new(Map)
263 }
264 265 m.seed = uintptr(rand())
266 267 if hint <= abi.SwissMapGroupSlots {
268 // A small map can fill all 8 slots, so no need to increase
269 // target capacity.
270 //
271 // In fact, since an 8 slot group is what the first assignment
272 // to an empty map would allocate anyway, it doesn't matter if
273 // we allocate here or on the first assignment.
274 //
275 // Thus we just return without allocating. (We'll save the
276 // allocation completely if no assignment comes.)
277 278 // Note that the compiler may have initialized m.dirPtr with a
279 // pointer to a stack-allocated group, in which case we already
280 // have a group. The control word is already initialized.
281 282 return m
283 }
284 285 // Full size map.
286 287 // Set initial capacity to hold hint entries without growing in the
288 // average case.
289 targetCapacity := (hint * abi.SwissMapGroupSlots) / maxAvgGroupLoad
290 if targetCapacity < hint { // overflow
291 return m // return an empty map.
292 }
293 294 dirSize := (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
295 dirSize, overflow := alignUpPow2(dirSize)
296 if overflow || dirSize > uint64(math.MaxUintptr) {
297 return m // return an empty map.
298 }
299 300 // Reject hints that are obviously too large.
301 groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity)
302 if overflow {
303 return m // return an empty map.
304 } else {
305 mem, overflow := math.MulUintptr(groups, mt.GroupSize)
306 if overflow || mem > maxAlloc {
307 return m // return an empty map.
308 }
309 }
310 311 m.globalDepth = uint8(sys.TrailingZeros64(dirSize))
312 m.globalShift = depthToShift(m.globalDepth)
313 314 directory := make([]*table, dirSize)
315 316 for i := range directory {
317 // TODO: Think more about initial table capacity.
318 directory[i] = newTable(mt, uint64(targetCapacity)/dirSize, i, m.globalDepth)
319 }
320 321 m.dirPtr = unsafe.Pointer(&directory[0])
322 m.dirLen = len(directory)
323 324 return m
325 }
326 327 func NewEmptyMap() *Map {
328 m := new(Map)
329 m.seed = uintptr(rand())
330 // See comment in NewMap. No need to eager allocate a group.
331 return m
332 }
333 334 func (m *Map) directoryIndex(hash uintptr) uintptr {
335 if m.dirLen == 1 {
336 return 0
337 }
338 return hash >> (m.globalShift & 63)
339 }
340 341 func (m *Map) directoryAt(i uintptr) *table {
342 return *(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i))
343 }
344 345 func (m *Map) directorySet(i uintptr, nt *table) {
346 *(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i)) = nt
347 }
348 349 func (m *Map) replaceTable(nt *table) {
350 // The number of entries that reference the same table doubles for each
351 // time the globalDepth grows without the table splitting.
352 entries := 1 << (m.globalDepth - nt.localDepth)
353 for i := 0; i < entries; i++ {
354 //m.directory[nt.index+i] = nt
355 m.directorySet(uintptr(nt.index+i), nt)
356 }
357 }
358 359 func (m *Map) installTableSplit(old, left, right *table) {
360 if old.localDepth == m.globalDepth {
361 // No room for another level in the directory. Grow the
362 // directory.
363 newDir := make([]*table, m.dirLen*2)
364 for i := range m.dirLen {
365 t := m.directoryAt(uintptr(i))
366 newDir[2*i] = t
367 newDir[2*i+1] = t
368 // t may already exist in multiple indicies. We should
369 // only update t.index once. Since the index must
370 // increase, seeing the original index means this must
371 // be the first time we've encountered this table.
372 if t.index == i {
373 t.index = 2 * i
374 }
375 }
376 m.globalDepth++
377 m.globalShift--
378 //m.directory = newDir
379 m.dirPtr = unsafe.Pointer(&newDir[0])
380 m.dirLen = len(newDir)
381 }
382 383 // N.B. left and right may still consume multiple indicies if the
384 // directory has grown multiple times since old was last split.
385 left.index = old.index
386 m.replaceTable(left)
387 388 entries := 1 << (m.globalDepth - left.localDepth)
389 right.index = left.index + entries
390 m.replaceTable(right)
391 }
392 393 func (m *Map) Used() uint64 {
394 return m.used
395 }
396 397 // Get performs a lookup of the key that key points to. It returns a pointer to
398 // the element, or false if the key doesn't exist.
399 func (m *Map) Get(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
400 return m.getWithoutKey(typ, key)
401 }
402 403 func (m *Map) getWithKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
404 if m.Used() == 0 {
405 return nil, nil, false
406 }
407 408 if m.writing != 0 {
409 fatal("concurrent map read and map write")
410 }
411 412 hash := typ.Hasher(key, m.seed)
413 414 if m.dirLen == 0 {
415 return m.getWithKeySmall(typ, hash, key)
416 }
417 418 idx := m.directoryIndex(hash)
419 return m.directoryAt(idx).getWithKey(typ, hash, key)
420 }
421 422 func (m *Map) getWithoutKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
423 if m.Used() == 0 {
424 return nil, false
425 }
426 427 if m.writing != 0 {
428 fatal("concurrent map read and map write")
429 }
430 431 hash := typ.Hasher(key, m.seed)
432 433 if m.dirLen == 0 {
434 _, elem, ok := m.getWithKeySmall(typ, hash, key)
435 return elem, ok
436 }
437 438 idx := m.directoryIndex(hash)
439 return m.directoryAt(idx).getWithoutKey(typ, hash, key)
440 }
441 442 func (m *Map) getWithKeySmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
443 g := groupReference{
444 data: m.dirPtr,
445 }
446 447 match := g.ctrls().matchH2(h2(hash))
448 449 for match != 0 {
450 i := match.first()
451 452 slotKey := g.key(typ, i)
453 if typ.IndirectKey() {
454 slotKey = *((*unsafe.Pointer)(slotKey))
455 }
456 457 if typ.Key.Equal(key, slotKey) {
458 slotElem := g.elem(typ, i)
459 if typ.IndirectElem() {
460 slotElem = *((*unsafe.Pointer)(slotElem))
461 }
462 return slotKey, slotElem, true
463 }
464 465 match = match.removeFirst()
466 }
467 468 // No match here means key is not in the map.
469 // (A single group means no need to probe or check for empty).
470 return nil, nil, false
471 }
472 473 func (m *Map) Put(typ *abi.SwissMapType, key, elem unsafe.Pointer) {
474 slotElem := m.PutSlot(typ, key)
475 typedmemmove(typ.Elem, slotElem, elem)
476 }
477 478 // PutSlot returns a pointer to the element slot where an inserted element
479 // should be written.
480 //
481 // PutSlot never returns nil.
482 func (m *Map) PutSlot(typ *abi.SwissMapType, key unsafe.Pointer) unsafe.Pointer {
483 if m.writing != 0 {
484 fatal("concurrent map writes")
485 }
486 487 hash := typ.Hasher(key, m.seed)
488 489 // Set writing after calling Hasher, since Hasher may panic, in which
490 // case we have not actually done a write.
491 m.writing ^= 1 // toggle, see comment on writing
492 493 if m.dirPtr == nil {
494 m.growToSmall(typ)
495 }
496 497 if m.dirLen == 0 {
498 if m.used < abi.SwissMapGroupSlots {
499 elem := m.putSlotSmall(typ, hash, key)
500 501 if m.writing == 0 {
502 fatal("concurrent map writes")
503 }
504 m.writing ^= 1
505 506 return elem
507 }
508 509 // Can't fit another entry, grow to full size map.
510 //
511 // TODO(prattmic): If this is an update to an existing key then
512 // we actually don't need to grow.
513 m.growToTable(typ)
514 }
515 516 for {
517 idx := m.directoryIndex(hash)
518 elem, ok := m.directoryAt(idx).PutSlot(typ, m, hash, key)
519 if !ok {
520 continue
521 }
522 523 if m.writing == 0 {
524 fatal("concurrent map writes")
525 }
526 m.writing ^= 1
527 528 return elem
529 }
530 }
531 532 func (m *Map) putSlotSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
533 g := groupReference{
534 data: m.dirPtr,
535 }
536 537 match := g.ctrls().matchH2(h2(hash))
538 539 // Look for an existing slot containing this key.
540 for match != 0 {
541 i := match.first()
542 543 slotKey := g.key(typ, i)
544 if typ.IndirectKey() {
545 slotKey = *((*unsafe.Pointer)(slotKey))
546 }
547 if typ.Key.Equal(key, slotKey) {
548 if typ.NeedKeyUpdate() {
549 typedmemmove(typ.Key, slotKey, key)
550 }
551 552 slotElem := g.elem(typ, i)
553 if typ.IndirectElem() {
554 slotElem = *((*unsafe.Pointer)(slotElem))
555 }
556 557 return slotElem
558 }
559 match = match.removeFirst()
560 }
561 562 // There can't be deleted slots, small maps can't have them
563 // (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
564 // more efficient than matchEmpty.
565 match = g.ctrls().matchEmptyOrDeleted()
566 if match == 0 {
567 fatal("small map with no empty slot (concurrent map writes?)")
568 return nil
569 }
570 571 i := match.first()
572 573 slotKey := g.key(typ, i)
574 if typ.IndirectKey() {
575 kmem := newobject(typ.Key)
576 *(*unsafe.Pointer)(slotKey) = kmem
577 slotKey = kmem
578 }
579 typedmemmove(typ.Key, slotKey, key)
580 581 slotElem := g.elem(typ, i)
582 if typ.IndirectElem() {
583 emem := newobject(typ.Elem)
584 *(*unsafe.Pointer)(slotElem) = emem
585 slotElem = emem
586 }
587 588 g.ctrls().set(i, ctrl(h2(hash)))
589 m.used++
590 591 return slotElem
592 }
593 594 func (m *Map) growToSmall(typ *abi.SwissMapType) {
595 grp := newGroups(typ, 1)
596 m.dirPtr = grp.data
597 598 g := groupReference{
599 data: m.dirPtr,
600 }
601 g.ctrls().setEmpty()
602 }
603 604 func (m *Map) growToTable(typ *abi.SwissMapType) {
605 tab := newTable(typ, 2*abi.SwissMapGroupSlots, 0, 0)
606 607 g := groupReference{
608 data: m.dirPtr,
609 }
610 611 for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
612 if (g.ctrls().get(i) & ctrlEmpty) == ctrlEmpty {
613 // Empty
614 continue
615 }
616 617 key := g.key(typ, i)
618 if typ.IndirectKey() {
619 key = *((*unsafe.Pointer)(key))
620 }
621 622 elem := g.elem(typ, i)
623 if typ.IndirectElem() {
624 elem = *((*unsafe.Pointer)(elem))
625 }
626 627 hash := typ.Hasher(key, m.seed)
628 629 tab.uncheckedPutSlot(typ, hash, key, elem)
630 }
631 632 directory := make([]*table, 1)
633 634 directory[0] = tab
635 636 m.dirPtr = unsafe.Pointer(&directory[0])
637 m.dirLen = len(directory)
638 639 m.globalDepth = 0
640 m.globalShift = depthToShift(m.globalDepth)
641 }
642 643 func (m *Map) Delete(typ *abi.SwissMapType, key unsafe.Pointer) {
644 if m == nil || m.Used() == 0 {
645 if err := mapKeyError(typ, key); err != nil {
646 panic(err) // see issue 23734
647 }
648 return
649 }
650 651 if m.writing != 0 {
652 fatal("concurrent map writes")
653 }
654 655 hash := typ.Hasher(key, m.seed)
656 657 // Set writing after calling Hasher, since Hasher may panic, in which
658 // case we have not actually done a write.
659 m.writing ^= 1 // toggle, see comment on writing
660 661 if m.dirLen == 0 {
662 m.deleteSmall(typ, hash, key)
663 } else {
664 idx := m.directoryIndex(hash)
665 if m.directoryAt(idx).Delete(typ, m, hash, key) {
666 m.tombstonePossible = true
667 }
668 }
669 670 if m.used == 0 {
671 // Reset the hash seed to make it more difficult for attackers
672 // to repeatedly trigger hash collisions. See
673 // https://go.dev/issue/25237.
674 m.seed = uintptr(rand())
675 }
676 677 if m.writing == 0 {
678 fatal("concurrent map writes")
679 }
680 m.writing ^= 1
681 }
682 683 func (m *Map) deleteSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) {
684 g := groupReference{
685 data: m.dirPtr,
686 }
687 688 match := g.ctrls().matchH2(h2(hash))
689 690 for match != 0 {
691 i := match.first()
692 slotKey := g.key(typ, i)
693 origSlotKey := slotKey
694 if typ.IndirectKey() {
695 slotKey = *((*unsafe.Pointer)(slotKey))
696 }
697 if typ.Key.Equal(key, slotKey) {
698 m.used--
699 700 if typ.IndirectKey() {
701 // Clearing the pointer is sufficient.
702 *(*unsafe.Pointer)(origSlotKey) = nil
703 } else if typ.Key.Pointers() {
704 // Only bother clearing if there are pointers.
705 typedmemclr(typ.Key, slotKey)
706 }
707 708 slotElem := g.elem(typ, i)
709 if typ.IndirectElem() {
710 // Clearing the pointer is sufficient.
711 *(*unsafe.Pointer)(slotElem) = nil
712 } else {
713 // Unlike keys, always clear the elem (even if
714 // it contains no pointers), as compound
715 // assignment operations depend on cleared
716 // deleted values. See
717 // https://go.dev/issue/25936.
718 typedmemclr(typ.Elem, slotElem)
719 }
720 721 // We only have 1 group, so it is OK to immediately
722 // reuse deleted slots.
723 g.ctrls().set(i, ctrlEmpty)
724 return
725 }
726 match = match.removeFirst()
727 }
728 }
729 730 // Clear deletes all entries from the map resulting in an empty map.
731 func (m *Map) Clear(typ *abi.SwissMapType) {
732 if m == nil || m.Used() == 0 && !m.tombstonePossible {
733 return
734 }
735 736 if m.writing != 0 {
737 fatal("concurrent map writes")
738 }
739 m.writing ^= 1 // toggle, see comment on writing
740 741 if m.dirLen == 0 {
742 m.clearSmall(typ)
743 } else {
744 var lastTab *table
745 for i := range m.dirLen {
746 t := m.directoryAt(uintptr(i))
747 if t == lastTab {
748 continue
749 }
750 t.Clear(typ)
751 lastTab = t
752 }
753 m.used = 0
754 m.tombstonePossible = false
755 // TODO: shrink directory?
756 }
757 m.clearSeq++
758 759 // Reset the hash seed to make it more difficult for attackers to
760 // repeatedly trigger hash collisions. See https://go.dev/issue/25237.
761 m.seed = uintptr(rand())
762 763 if m.writing == 0 {
764 fatal("concurrent map writes")
765 }
766 m.writing ^= 1
767 }
768 769 func (m *Map) clearSmall(typ *abi.SwissMapType) {
770 g := groupReference{
771 data: m.dirPtr,
772 }
773 774 typedmemclr(typ.Group, g.data)
775 g.ctrls().setEmpty()
776 777 m.used = 0
778 }
779 780 func (m *Map) Clone(typ *abi.SwissMapType) *Map {
781 // Note: this should never be called with a nil map.
782 if m.writing != 0 {
783 fatal("concurrent map clone and map write")
784 }
785 786 // Shallow copy the Map structure.
787 m2 := new(Map)
788 *m2 = *m
789 m = m2
790 791 // We need to just deep copy the dirPtr field.
792 if m.dirPtr == nil {
793 // delayed group allocation, nothing to do.
794 } else if m.dirLen == 0 {
795 // Clone one group.
796 oldGroup := groupReference{data: m.dirPtr}
797 newGroup := groupReference{data: newGroups(typ, 1).data}
798 cloneGroup(typ, newGroup, oldGroup)
799 m.dirPtr = newGroup.data
800 } else {
801 // Clone each (different) table.
802 oldDir := unsafe.Slice((**table)(m.dirPtr), m.dirLen)
803 newDir := make([]*table, m.dirLen)
804 for i, t := range oldDir {
805 if i > 0 && t == oldDir[i-1] {
806 newDir[i] = newDir[i-1]
807 continue
808 }
809 newDir[i] = t.clone(typ)
810 }
811 m.dirPtr = unsafe.Pointer(&newDir[0])
812 }
813 814 return m
815 }
816 817 func OldMapKeyError(t *abi.OldMapType, p unsafe.Pointer) error {
818 if !t.HashMightPanic() {
819 return nil
820 }
821 return mapKeyError2(t.Key, p)
822 }
823 824 func mapKeyError(t *abi.SwissMapType, p unsafe.Pointer) error {
825 if !t.HashMightPanic() {
826 return nil
827 }
828 return mapKeyError2(t.Key, p)
829 }
830 831 func mapKeyError2(t *abi.Type, p unsafe.Pointer) error {
832 if t.TFlag&abi.TFlagRegularMemory != 0 {
833 return nil
834 }
835 switch t.Kind() {
836 case abi.Float32, abi.Float64, abi.Complex64, abi.Complex128, abi.String:
837 return nil
838 case abi.Interface:
839 i := (*abi.InterfaceType)(unsafe.Pointer(t))
840 var t *abi.Type
841 var pdata *unsafe.Pointer
842 if len(i.Methods) == 0 {
843 a := (*abi.EmptyInterface)(p)
844 t = a.Type
845 if t == nil {
846 return nil
847 }
848 pdata = &a.Data
849 } else {
850 a := (*abi.NonEmptyInterface)(p)
851 if a.ITab == nil {
852 return nil
853 }
854 t = a.ITab.Type
855 pdata = &a.Data
856 }
857 858 if t.Equal == nil {
859 return unhashableTypeError{t}
860 }
861 862 if t.Kind_&abi.KindDirectIface != 0 {
863 return mapKeyError2(t, unsafe.Pointer(pdata))
864 } else {
865 return mapKeyError2(t, *pdata)
866 }
867 case abi.Array:
868 a := (*abi.ArrayType)(unsafe.Pointer(t))
869 for i := uintptr(0); i < a.Len; i++ {
870 if err := mapKeyError2(a.Elem, unsafe.Pointer(uintptr(p)+i*a.Elem.Size_)); err != nil {
871 return err
872 }
873 }
874 return nil
875 case abi.Struct:
876 s := (*abi.StructType)(unsafe.Pointer(t))
877 for _, f := range s.Fields {
878 if f.Name.IsBlank() {
879 continue
880 }
881 if err := mapKeyError2(f.Typ, unsafe.Pointer(uintptr(p)+f.Offset)); err != nil {
882 return err
883 }
884 }
885 return nil
886 default:
887 // Should never happen, keep this case for robustness.
888 return unhashableTypeError{t}
889 }
890 }
891 892 type unhashableTypeError struct{ typ *abi.Type }
893 894 func (unhashableTypeError) RuntimeError() {}
895 896 func (e unhashableTypeError) Error() string { return "hash of unhashable type: " + typeString(e.typ) }
897 898 // Pushed from runtime
899 //
900 //go:linkname typeString
901 func typeString(typ *abi.Type) string
902