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  func NewMap(mt *abi.MapType, hint uintptr, m *Map) *Map {
   280  	return newMap(mt, hint, m, sys.MaxAlloc)
   281  }
   282  
   283  // newMap is NewMap with an explicit allocation limit, for tests.
   284  func newMap(mt *abi.MapType, hint uintptr, m *Map, maxAlloc uintptr) *Map {
   285  	if m == nil {
   286  		m = new(Map)
   287  	}
   288  
   289  	m.seed = uintptr(rand())
   290  
   291  	if hint <= abi.MapGroupSlots {
   292  		// A small map can fill all 8 slots, so no need to increase
   293  		// target capacity.
   294  		//
   295  		// In fact, since an 8 slot group is what the first assignment
   296  		// to an empty map would allocate anyway, it doesn't matter if
   297  		// we allocate here or on the first assignment.
   298  		//
   299  		// Thus we just return without allocating. (We'll save the
   300  		// allocation completely if no assignment comes.)
   301  
   302  		// Note that the compiler may have initialized m.dirPtr with a
   303  		// pointer to a stack-allocated group, in which case we already
   304  		// have a group. The control word is already initialized.
   305  
   306  		return m
   307  	}
   308  
   309  	// Full size map.
   310  
   311  	dirSize, targetCapacity, ok := mapCapacityFor(mt, hint, maxAlloc)
   312  	if !ok {
   313  		return m // return an empty map.
   314  	}
   315  
   316  	m.globalDepth = uint8(sys.TrailingZeros64(dirSize))
   317  	m.globalShift = depthToShift(m.globalDepth)
   318  
   319  	directory := make([]*table, dirSize)
   320  
   321  	for i := range directory {
   322  		// TODO: Think more about initial table capacity.
   323  		directory[i] = newTable(mt, uint64(targetCapacity)/dirSize, i, m.globalDepth)
   324  	}
   325  
   326  	m.dirPtr = unsafe.Pointer(&directory[0])
   327  	m.dirLen = len(directory)
   328  
   329  	return m
   330  }
   331  
   332  // mapCapacityFor computes the directory size and total target slot
   333  // capacity needed to hold hint entries at the standard load factor.
   334  // Shared sizing logic for NewMap and Map.Grow; callers must have already
   335  // handled hint <= abi.MapGroupSlots. ok is false if hint is too large.
   336  func mapCapacityFor(mt *abi.MapType, hint uintptr, maxAlloc uintptr) (dirSize uint64, targetCapacity uintptr, ok bool) {
   337  	// Set initial capacity to hold hint entries without growing in the
   338  	// average case.
   339  	targetCapacity = (hint * abi.MapGroupSlots) / maxAvgGroupLoad
   340  	if targetCapacity < hint { // overflow
   341  		return 0, 0, false
   342  	}
   343  
   344  	dirSize = (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
   345  	var overflow bool
   346  	dirSize, overflow = alignUpPow2(dirSize)
   347  	if overflow || dirSize > uint64(math.MaxUintptr) {
   348  		return 0, 0, false
   349  	}
   350  
   351  	// Reject hints that are obviously too large.
   352  	groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity)
   353  	if overflow {
   354  		return 0, 0, false
   355  	}
   356  	mem, overflow := math.MulUintptr(groups, mt.GroupSize)
   357  	if overflow || mem > maxAlloc {
   358  		return 0, 0, false
   359  	}
   360  
   361  	return dirSize, targetCapacity, true
   362  }
   363  
   364  func NewEmptyMap() *Map {
   365  	m := new(Map)
   366  	m.seed = uintptr(rand())
   367  	// See comment in NewMap. No need to eager allocate a group.
   368  	return m
   369  }
   370  
   371  // totalCapacity returns m's total slot count, summed across distinct
   372  // tables in the directory. A small map reports abi.MapGroupSlots.
   373  func (m *Map) totalCapacity() uint64 {
   374  	if m.dirLen == 0 {
   375  		return abi.MapGroupSlots
   376  	}
   377  
   378  	var total uint64
   379  	var lastTab *table
   380  	for i := range m.dirLen {
   381  		t := m.directoryAt(uintptr(i))
   382  		if t == lastTab {
   383  			continue
   384  		}
   385  		lastTab = t
   386  		total += uint64(t.capacity)
   387  	}
   388  	return total
   389  }
   390  
   391  // Grow increases m's capacity, if necessary, so that at least n more
   392  // entries can be added without further growth in the typical case, as if
   393  // allocated via NewMap(typ, m.Used()+n, ...). Never shrinks m.
   394  func (m *Map) Grow(typ *abi.MapType, n uintptr) {
   395  	m.grow(typ, n, sys.MaxAlloc)
   396  }
   397  
   398  // grow is Grow with an explicit allocation limit, for tests.
   399  func (m *Map) grow(typ *abi.MapType, n uintptr, maxAlloc uintptr) {
   400  	if m.writing != 0 {
   401  		fatal("concurrent map writes")
   402  	}
   403  
   404  	if n == 0 {
   405  		return
   406  	}
   407  
   408  	used := uintptr(m.Used())
   409  	hint := used + n
   410  	if hint < used { // overflow
   411  		hint = math.MaxUintptr
   412  	}
   413  
   414  	if hint <= abi.MapGroupSlots {
   415  		return // small map already has room; see NewMap.
   416  	}
   417  
   418  	dirSize, targetCapacity, ok := mapCapacityFor(typ, hint, maxAlloc)
   419  	if !ok {
   420  		return
   421  	}
   422  
   423  	if m.totalCapacity() >= uint64(targetCapacity) {
   424  		return // already enough room.
   425  	}
   426  
   427  	// Never shrink the directory: growTo only subdivides existing
   428  	// tables, and merging them could overload a new table's headroom.
   429  	if oldDirLen := uint64(m.dirLen); dirSize < oldDirLen {
   430  		dirSize = oldDirLen
   431  	}
   432  
   433  	m.writing ^= 1 // toggle, see comment on writing
   434  
   435  	m.growTo(typ, dirSize, targetCapacity)
   436  
   437  	if m.writing == 0 {
   438  		fatal("concurrent map writes")
   439  	}
   440  	m.writing ^= 1
   441  }
   442  
   443  // growTo replaces m's storage with a fresh directory of dirSize tables
   444  // totaling targetCapacity slots, and moves every entry into it. Callers
   445  // must size dirSize/targetCapacity via mapCapacityFor.
   446  func (m *Map) growTo(typ *abi.MapType, dirSize uint64, targetCapacity uintptr) {
   447  	newGlobalDepth := uint8(sys.TrailingZeros64(dirSize))
   448  	newGlobalShift := depthToShift(newGlobalDepth)
   449  
   450  	// Splitting into multiple tables may not divide evenly; give each
   451  	// full headroom, like table.split, rather than risk overloading
   452  	// uncheckedPutSlot below.
   453  	tableCapacity := uint64(targetCapacity)
   454  	if dirSize > 1 {
   455  		tableCapacity = maxTableCapacity
   456  	}
   457  
   458  	newDir := make([]*table, dirSize)
   459  	for i := range newDir {
   460  		newDir[i] = newTable(typ, tableCapacity, i, newGlobalDepth)
   461  	}
   462  
   463  	// Keep every entry within its old table's directory range, as
   464  	// table.split does. A regular key lands there anyway, but a NaN gets
   465  	// a new random hash, and iterators rely on it staying on the same
   466  	// side of them: they skip the ranges of tables already visited.
   467  	orders := newGlobalDepth - m.globalDepth
   468  
   469  	putGroup := func(g groupReference, oldIndex int, oldDepth uint8) {
   470  		base := uintptr(oldIndex) << orders
   471  		mask := uintptr(1)<<(newGlobalDepth-oldDepth) - 1
   472  		for j := uintptr(0); j < abi.MapGroupSlots; j++ {
   473  			if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
   474  				// Empty or deleted.
   475  				continue
   476  			}
   477  
   478  			key := g.key(typ, j)
   479  			if typ.IndirectKey() {
   480  				key = *((*unsafe.Pointer)(key))
   481  			}
   482  
   483  			elem := g.elem(typ, j)
   484  			if typ.IndirectElem() {
   485  				elem = *((*unsafe.Pointer)(elem))
   486  			}
   487  
   488  			hash := typ.Hasher(key, m.seed)
   489  			idx := base | hash>>(newGlobalShift&63)&mask
   490  			newDir[idx].uncheckedPutSlot(typ, hash, key, elem)
   491  		}
   492  	}
   493  
   494  	switch {
   495  	case m.dirPtr == nil:
   496  		// Empty small map; nothing to move.
   497  	case m.dirLen == 0:
   498  		// Small map: a single group.
   499  		putGroup(groupReference{data: m.dirPtr}, 0, 0)
   500  	default:
   501  		var lastTab *table
   502  		for i := range m.dirLen {
   503  			t := m.directoryAt(uintptr(i))
   504  			if t == lastTab {
   505  				continue
   506  			}
   507  			lastTab = t
   508  
   509  			for gi := uint64(0); gi <= t.groups.lengthMask; gi++ {
   510  				putGroup(t.groups.group(typ, gi), t.index, t.localDepth)
   511  			}
   512  
   513  			// Mark t stale, like table.grow/split, so a live
   514  			// iterator notices and falls back to key lookups.
   515  			t.index = -1
   516  		}
   517  	}
   518  
   519  	for _, t := range newDir {
   520  		t.checkInvariants(typ, m)
   521  	}
   522  
   523  	m.dirPtr = unsafe.Pointer(&newDir[0])
   524  	m.dirLen = len(newDir)
   525  	m.globalDepth = newGlobalDepth
   526  	m.globalShift = newGlobalShift
   527  	m.tombstonePossible = false // tables were rebuilt fresh, no tombstones
   528  }
   529  
   530  func (m *Map) directoryIndex(hash uintptr) uintptr {
   531  	if m.dirLen == 1 {
   532  		return 0
   533  	}
   534  	return hash >> (m.globalShift & 63)
   535  }
   536  
   537  func (m *Map) directoryAt(i uintptr) *table {
   538  	return *(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i))
   539  }
   540  
   541  func (m *Map) directorySet(i uintptr, nt *table) {
   542  	*(**table)(unsafe.Pointer(uintptr(m.dirPtr) + goarch.PtrSize*i)) = nt
   543  }
   544  
   545  func (m *Map) replaceTable(nt *table) {
   546  	// The number of entries that reference the same table doubles for each
   547  	// time the globalDepth grows without the table splitting.
   548  	entries := 1 << (m.globalDepth - nt.localDepth)
   549  	for i := 0; i < entries; i++ {
   550  		//m.directory[nt.index+i] = nt
   551  		m.directorySet(uintptr(nt.index+i), nt)
   552  	}
   553  }
   554  
   555  func (m *Map) installTableSplit(old, left, right *table) {
   556  	if old.localDepth == m.globalDepth {
   557  		// No room for another level in the directory. Grow the
   558  		// directory.
   559  		newDir := make([]*table, m.dirLen*2)
   560  		for i := range m.dirLen {
   561  			t := m.directoryAt(uintptr(i))
   562  			newDir[2*i] = t
   563  			newDir[2*i+1] = t
   564  			// t may already exist in multiple indices. We should
   565  			// only update t.index once. Since the index must
   566  			// increase, seeing the original index means this must
   567  			// be the first time we've encountered this table.
   568  			if t.index == i {
   569  				t.index = 2 * i
   570  			}
   571  		}
   572  		m.globalDepth++
   573  		m.globalShift--
   574  		//m.directory = newDir
   575  		m.dirPtr = unsafe.Pointer(&newDir[0])
   576  		m.dirLen = len(newDir)
   577  	}
   578  
   579  	// N.B. left and right may still consume multiple indices if the
   580  	// directory has grown multiple times since old was last split.
   581  	left.index = old.index
   582  	m.replaceTable(left)
   583  
   584  	entries := 1 << (m.globalDepth - left.localDepth)
   585  	right.index = left.index + entries
   586  	m.replaceTable(right)
   587  }
   588  
   589  func (m *Map) Used() uint64 {
   590  	return m.used
   591  }
   592  
   593  // Get performs a lookup of the key that key points to. It returns a pointer to
   594  // the element, or false if the key doesn't exist.
   595  func (m *Map) Get(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
   596  	return m.getWithoutKey(typ, key)
   597  }
   598  
   599  func (m *Map) getWithKey(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
   600  	if m.Used() == 0 {
   601  		return nil, nil, false
   602  	}
   603  
   604  	if m.writing != 0 {
   605  		fatal("concurrent map read and map write")
   606  	}
   607  
   608  	hash := typ.Hasher(key, m.seed)
   609  
   610  	if m.dirLen == 0 {
   611  		return m.getWithKeySmall(typ, hash, key)
   612  	}
   613  
   614  	idx := m.directoryIndex(hash)
   615  	return m.directoryAt(idx).getWithKey(typ, hash, key)
   616  }
   617  
   618  func (m *Map) getWithoutKey(typ *abi.MapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
   619  	if m.Used() == 0 {
   620  		return nil, false
   621  	}
   622  
   623  	if m.writing != 0 {
   624  		fatal("concurrent map read and map write")
   625  	}
   626  
   627  	hash := typ.Hasher(key, m.seed)
   628  
   629  	if m.dirLen == 0 {
   630  		_, elem, ok := m.getWithKeySmall(typ, hash, key)
   631  		return elem, ok
   632  	}
   633  
   634  	idx := m.directoryIndex(hash)
   635  	return m.directoryAt(idx).getWithoutKey(typ, hash, key)
   636  }
   637  
   638  func (m *Map) getWithKeySmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
   639  	g := groupReference{
   640  		data: m.dirPtr,
   641  	}
   642  
   643  	match := g.ctrls().matchH2(h2(hash))
   644  
   645  	for match != 0 {
   646  		i := match.first()
   647  
   648  		slotKey := g.key(typ, i)
   649  		if typ.IndirectKey() {
   650  			slotKey = *((*unsafe.Pointer)(slotKey))
   651  		}
   652  
   653  		if typ.Key.Equal(key, slotKey) {
   654  			slotElem := g.elem(typ, i)
   655  			if typ.IndirectElem() {
   656  				slotElem = *((*unsafe.Pointer)(slotElem))
   657  			}
   658  			return slotKey, slotElem, true
   659  		}
   660  
   661  		match = match.removeFirst()
   662  	}
   663  
   664  	// No match here means key is not in the map.
   665  	// (A single group means no need to probe or check for empty).
   666  	return nil, nil, false
   667  }
   668  
   669  func (m *Map) Put(typ *abi.MapType, key, elem unsafe.Pointer) {
   670  	slotElem := m.PutSlot(typ, key)
   671  	typedmemmove(typ.Elem, slotElem, elem)
   672  }
   673  
   674  // PutSlot returns a pointer to the element slot where an inserted element
   675  // should be written.
   676  //
   677  // PutSlot never returns nil.
   678  func (m *Map) PutSlot(typ *abi.MapType, key unsafe.Pointer) unsafe.Pointer {
   679  	if m.writing != 0 {
   680  		fatal("concurrent map writes")
   681  	}
   682  
   683  	hash := typ.Hasher(key, m.seed)
   684  
   685  	// Set writing after calling Hasher, since Hasher may panic, in which
   686  	// case we have not actually done a write.
   687  	m.writing ^= 1 // toggle, see comment on writing
   688  
   689  	if m.dirPtr == nil {
   690  		m.growToSmall(typ)
   691  	}
   692  
   693  	if m.dirLen == 0 {
   694  		elem := m.putSlotSmall(typ, hash, key)
   695  		if elem == nil {
   696  			// Can't fit another entry, grow to full size map.
   697  			tab := m.growToTable(typ)
   698  
   699  			elem = tab.uncheckedPutSlotForAssign(typ, hash, key)
   700  			m.used++
   701  
   702  			tab.checkInvariants(typ, m)
   703  		}
   704  
   705  		if m.writing == 0 {
   706  			fatal("concurrent map writes")
   707  		}
   708  		m.writing ^= 1
   709  
   710  		return elem
   711  	}
   712  
   713  	for {
   714  		idx := m.directoryIndex(hash)
   715  		elem, ok := m.directoryAt(idx).PutSlot(typ, m, hash, key)
   716  		if !ok {
   717  			continue
   718  		}
   719  
   720  		if m.writing == 0 {
   721  			fatal("concurrent map writes")
   722  		}
   723  		m.writing ^= 1
   724  
   725  		return elem
   726  	}
   727  }
   728  
   729  func (m *Map) putSlotSmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
   730  	g := groupReference{
   731  		data: m.dirPtr,
   732  	}
   733  
   734  	match := g.ctrls().matchH2(h2(hash))
   735  
   736  	// Look for an existing slot containing this key.
   737  	for match != 0 {
   738  		i := match.first()
   739  
   740  		slotKey := g.key(typ, i)
   741  		if typ.IndirectKey() {
   742  			slotKey = *((*unsafe.Pointer)(slotKey))
   743  		}
   744  		if typ.Key.Equal(key, slotKey) {
   745  			if typ.NeedKeyUpdate() {
   746  				typedmemmove(typ.Key, slotKey, key)
   747  			}
   748  
   749  			slotElem := g.elem(typ, i)
   750  			if typ.IndirectElem() {
   751  				slotElem = *((*unsafe.Pointer)(slotElem))
   752  			}
   753  
   754  			return slotElem
   755  		}
   756  		match = match.removeFirst()
   757  	}
   758  
   759  	// There can't be deleted slots, small maps can't have them
   760  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   761  	// more efficient than matchEmpty.
   762  	match = g.ctrls().matchEmptyOrDeleted()
   763  	if match == 0 {
   764  		// No empty slot found. Need to grow the map.
   765  		return nil
   766  	}
   767  
   768  	i := match.first()
   769  
   770  	slotKey := g.key(typ, i)
   771  	if typ.IndirectKey() {
   772  		kmem := newobject(typ.Key)
   773  		*(*unsafe.Pointer)(slotKey) = kmem
   774  		slotKey = kmem
   775  	}
   776  	typedmemmove(typ.Key, slotKey, key)
   777  
   778  	slotElem := g.elem(typ, i)
   779  	if typ.IndirectElem() {
   780  		emem := newobject(typ.Elem)
   781  		*(*unsafe.Pointer)(slotElem) = emem
   782  		slotElem = emem
   783  	}
   784  
   785  	g.ctrls().set(i, ctrl(h2(hash)))
   786  	m.used++
   787  
   788  	return slotElem
   789  }
   790  
   791  func (m *Map) growToSmall(typ *abi.MapType) {
   792  	grp := newGroups(typ, 1)
   793  	m.dirPtr = grp.data
   794  
   795  	g := groupReference{
   796  		data: m.dirPtr,
   797  	}
   798  	g.ctrls().setEmpty()
   799  }
   800  
   801  func (m *Map) growToTable(typ *abi.MapType) *table {
   802  	tab := newTable(typ, 2*abi.MapGroupSlots, 0, 0)
   803  
   804  	g := groupReference{
   805  		data: m.dirPtr,
   806  	}
   807  
   808  	for i := uintptr(0); i < abi.MapGroupSlots; i++ {
   809  		if (g.ctrls().get(i) & ctrlEmpty) == ctrlEmpty {
   810  			// Empty
   811  			continue
   812  		}
   813  
   814  		key := g.key(typ, i)
   815  		if typ.IndirectKey() {
   816  			key = *((*unsafe.Pointer)(key))
   817  		}
   818  
   819  		elem := g.elem(typ, i)
   820  		if typ.IndirectElem() {
   821  			elem = *((*unsafe.Pointer)(elem))
   822  		}
   823  
   824  		hash := typ.Hasher(key, m.seed)
   825  
   826  		tab.uncheckedPutSlot(typ, hash, key, elem)
   827  	}
   828  
   829  	directory := make([]*table, 1)
   830  
   831  	directory[0] = tab
   832  
   833  	m.dirPtr = unsafe.Pointer(&directory[0])
   834  	m.dirLen = len(directory)
   835  
   836  	m.globalDepth = 0
   837  	m.globalShift = depthToShift(m.globalDepth)
   838  	return tab
   839  }
   840  
   841  func (m *Map) Delete(typ *abi.MapType, key unsafe.Pointer) {
   842  	if m == nil || m.Used() == 0 {
   843  		if err := mapKeyError(typ, key); err != nil {
   844  			panic(err) // see issue 23734
   845  		}
   846  		return
   847  	}
   848  
   849  	if m.writing != 0 {
   850  		fatal("concurrent map writes")
   851  	}
   852  
   853  	hash := typ.Hasher(key, m.seed)
   854  
   855  	// Set writing after calling Hasher, since Hasher may panic, in which
   856  	// case we have not actually done a write.
   857  	m.writing ^= 1 // toggle, see comment on writing
   858  
   859  	if m.dirLen == 0 {
   860  		m.deleteSmall(typ, hash, key)
   861  	} else {
   862  		idx := m.directoryIndex(hash)
   863  		if m.directoryAt(idx).Delete(typ, m, hash, key) {
   864  			m.tombstonePossible = true
   865  		}
   866  	}
   867  
   868  	if m.used == 0 {
   869  		// Reset the hash seed to make it more difficult for attackers
   870  		// to repeatedly trigger hash collisions. See
   871  		// https://go.dev/issue/25237.
   872  		m.seed = uintptr(rand())
   873  	}
   874  
   875  	if m.writing == 0 {
   876  		fatal("concurrent map writes")
   877  	}
   878  	m.writing ^= 1
   879  }
   880  
   881  func (m *Map) deleteSmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) {
   882  	g := groupReference{
   883  		data: m.dirPtr,
   884  	}
   885  
   886  	match := g.ctrls().matchH2(h2(hash))
   887  
   888  	for match != 0 {
   889  		i := match.first()
   890  		slotKey := g.key(typ, i)
   891  		origSlotKey := slotKey
   892  		if typ.IndirectKey() {
   893  			slotKey = *((*unsafe.Pointer)(slotKey))
   894  		}
   895  		if typ.Key.Equal(key, slotKey) {
   896  			m.used--
   897  
   898  			if typ.IndirectKey() {
   899  				// Clearing the pointer is sufficient.
   900  				*(*unsafe.Pointer)(origSlotKey) = nil
   901  			} else if typ.Key.Pointers() {
   902  				// Only bother clearing if there are pointers.
   903  				typedmemclr(typ.Key, slotKey)
   904  			}
   905  
   906  			slotElem := g.elem(typ, i)
   907  			if typ.IndirectElem() {
   908  				// Clearing the pointer is sufficient.
   909  				*(*unsafe.Pointer)(slotElem) = nil
   910  			} else {
   911  				// Unlike keys, always clear the elem (even if
   912  				// it contains no pointers), as compound
   913  				// assignment operations depend on cleared
   914  				// deleted values. See
   915  				// https://go.dev/issue/25936.
   916  				typedmemclr(typ.Elem, slotElem)
   917  			}
   918  
   919  			// We only have 1 group, so it is OK to immediately
   920  			// reuse deleted slots.
   921  			g.ctrls().set(i, ctrlEmpty)
   922  			return
   923  		}
   924  		match = match.removeFirst()
   925  	}
   926  }
   927  
   928  // Clear deletes all entries from the map resulting in an empty map.
   929  func (m *Map) Clear(typ *abi.MapType) {
   930  	if m == nil || m.Used() == 0 && !m.tombstonePossible {
   931  		return
   932  	}
   933  
   934  	if m.writing != 0 {
   935  		fatal("concurrent map writes")
   936  	}
   937  	m.writing ^= 1 // toggle, see comment on writing
   938  
   939  	if m.dirLen == 0 {
   940  		m.clearSmall(typ)
   941  	} else {
   942  		var lastTab *table
   943  		for i := range m.dirLen {
   944  			t := m.directoryAt(uintptr(i))
   945  			if t == lastTab {
   946  				continue
   947  			}
   948  			t.Clear(typ)
   949  			lastTab = t
   950  		}
   951  		m.used = 0
   952  		m.tombstonePossible = false
   953  		// TODO: shrink directory?
   954  	}
   955  	m.clearSeq++
   956  
   957  	// Reset the hash seed to make it more difficult for attackers to
   958  	// repeatedly trigger hash collisions. See https://go.dev/issue/25237.
   959  	m.seed = uintptr(rand())
   960  
   961  	if m.writing == 0 {
   962  		fatal("concurrent map writes")
   963  	}
   964  	m.writing ^= 1
   965  }
   966  
   967  func (m *Map) clearSmall(typ *abi.MapType) {
   968  	g := groupReference{
   969  		data: m.dirPtr,
   970  	}
   971  
   972  	typedmemclr(typ.Group, g.data)
   973  	g.ctrls().setEmpty()
   974  
   975  	m.used = 0
   976  }
   977  
   978  func (m *Map) Clone(typ *abi.MapType) *Map {
   979  	// Note: this should never be called with a nil map.
   980  	if m.writing != 0 {
   981  		fatal("concurrent map clone and map write")
   982  	}
   983  
   984  	// Shallow copy the Map structure.
   985  	m2 := new(Map)
   986  	*m2 = *m
   987  	m = m2
   988  
   989  	// We need to just deep copy the dirPtr field.
   990  	if m.dirPtr == nil {
   991  		// delayed group allocation, nothing to do.
   992  	} else if m.dirLen == 0 {
   993  		// Clone one group.
   994  		oldGroup := groupReference{data: m.dirPtr}
   995  		newGroup := groupReference{data: newGroups(typ, 1).data}
   996  		cloneGroup(typ, newGroup, oldGroup)
   997  		m.dirPtr = newGroup.data
   998  	} else {
   999  		// Clone each (different) table.
  1000  		oldDir := unsafe.Slice((**table)(m.dirPtr), m.dirLen)
  1001  		newDir := make([]*table, m.dirLen)
  1002  		for i, t := range oldDir {
  1003  			if i > 0 && t == oldDir[i-1] {
  1004  				newDir[i] = newDir[i-1]
  1005  				continue
  1006  			}
  1007  			newDir[i] = t.clone(typ)
  1008  		}
  1009  		m.dirPtr = unsafe.Pointer(&newDir[0])
  1010  	}
  1011  
  1012  	return m
  1013  }
  1014  
  1015  func mapKeyError(t *abi.MapType, p unsafe.Pointer) error {
  1016  	if !t.HashMightPanic() {
  1017  		return nil
  1018  	}
  1019  	return mapKeyError2(t.Key, p)
  1020  }
  1021  
  1022  func mapKeyError2(t *abi.Type, p unsafe.Pointer) error {
  1023  	if t.TFlag&abi.TFlagRegularMemory != 0 {
  1024  		return nil
  1025  	}
  1026  	switch t.Kind() {
  1027  	case abi.Float32, abi.Float64, abi.Complex64, abi.Complex128, abi.String:
  1028  		return nil
  1029  	case abi.Interface:
  1030  		i := (*abi.InterfaceType)(unsafe.Pointer(t))
  1031  		var t *abi.Type
  1032  		var pdata *unsafe.Pointer
  1033  		if len(i.Methods) == 0 {
  1034  			a := (*abi.EmptyInterface)(p)
  1035  			t = a.Type
  1036  			if t == nil {
  1037  				return nil
  1038  			}
  1039  			pdata = &a.Data
  1040  		} else {
  1041  			a := (*abi.NonEmptyInterface)(p)
  1042  			if a.ITab == nil {
  1043  				return nil
  1044  			}
  1045  			t = a.ITab.Type
  1046  			pdata = &a.Data
  1047  		}
  1048  
  1049  		if t.Equal == nil {
  1050  			return unhashableTypeError{t}
  1051  		}
  1052  
  1053  		if t.IsDirectIface() {
  1054  			return mapKeyError2(t, unsafe.Pointer(pdata))
  1055  		} else {
  1056  			return mapKeyError2(t, *pdata)
  1057  		}
  1058  	case abi.Array:
  1059  		a := (*abi.ArrayType)(unsafe.Pointer(t))
  1060  		for i := uintptr(0); i < a.Len; i++ {
  1061  			if err := mapKeyError2(a.Elem, unsafe.Pointer(uintptr(p)+i*a.Elem.Size_)); err != nil {
  1062  				return err
  1063  			}
  1064  		}
  1065  		return nil
  1066  	case abi.Struct:
  1067  		s := (*abi.StructType)(unsafe.Pointer(t))
  1068  		for _, f := range s.Fields {
  1069  			if f.Name.IsBlank() {
  1070  				continue
  1071  			}
  1072  			if err := mapKeyError2(f.Typ, unsafe.Pointer(uintptr(p)+f.Offset)); err != nil {
  1073  				return err
  1074  			}
  1075  		}
  1076  		return nil
  1077  	default:
  1078  		// Should never happen, keep this case for robustness.
  1079  		return unhashableTypeError{t}
  1080  	}
  1081  }
  1082  
  1083  type unhashableTypeError struct{ typ *abi.Type }
  1084  
  1085  func (unhashableTypeError) RuntimeError() {}
  1086  
  1087  func (e unhashableTypeError) Error() string { return "hash of unhashable type: " + typeString(e.typ) }
  1088  
  1089  // Pushed from runtime
  1090  //
  1091  //go:linkname typeString
  1092  func typeString(typ *abi.Type) string
  1093
View as plain text