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.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
View as plain text