runtime.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
     6  
     7  import (
     8  	"internal/abi"
     9  	"internal/asan"
    10  	"internal/goexperiment"
    11  	"internal/msan"
    12  	"internal/race"
    13  	"internal/runtime/sys"
    14  	"unsafe"
    15  )
    16  
    17  // Functions below pushed from runtime.
    18  //
    19  //go:linkname fatal
    20  func fatal(s string)
    21  
    22  //go:linknamestd bootstrapRand runtime.bootstrapRand
    23  func bootstrapRand() uint64
    24  
    25  //go:linkname rand
    26  func rand() uint64
    27  
    28  //go:linkname typedmemmove
    29  func typedmemmove(typ *abi.Type, dst, src unsafe.Pointer)
    30  
    31  //go:linkname typedmemclr
    32  func typedmemclr(typ *abi.Type, ptr unsafe.Pointer)
    33  
    34  //go:linkname newarray
    35  func newarray(typ *abi.Type, n int) unsafe.Pointer
    36  
    37  //go:linkname newobject
    38  func newobject(typ *abi.Type) unsafe.Pointer
    39  
    40  // Pushed from runtime in order to use runtime.plainError
    41  //
    42  //go:linkname errNilAssign
    43  var errNilAssign error
    44  
    45  // TODO: move zeroVal to internal/abi?
    46  //
    47  //go:linkname zeroVal runtime.zeroVal
    48  var zeroVal [abi.ZeroValSize]byte
    49  
    50  // mapaccess1 returns a pointer to h[key].  Never returns nil, instead
    51  // it will return a reference to the zero object for the elem type if
    52  // the key is not in the map.
    53  // NOTE: The returned pointer may keep the whole map live, so don't
    54  // hold onto it for very long.
    55  //
    56  //go:linkname runtime_mapaccess1 runtime.mapaccess1
    57  func runtime_mapaccess1(typ *abi.MapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
    58  	p, _ := runtime_mapaccess2(typ, m, key)
    59  	return p
    60  }
    61  
    62  //go:linkname runtime_mapaccess1_fat runtime.mapaccess1_fat
    63  func runtime_mapaccess1_fat(t *abi.MapType, m *Map, key, zero unsafe.Pointer) unsafe.Pointer {
    64  	e, ok := runtime_mapaccess2(t, m, key)
    65  	if !ok {
    66  		return zero
    67  	}
    68  	return e
    69  }
    70  
    71  //go:linkname runtime_mapaccess2_fat runtime.mapaccess2_fat
    72  func runtime_mapaccess2_fat(t *abi.MapType, m *Map, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
    73  	e, ok := runtime_mapaccess2(t, m, key)
    74  	if !ok {
    75  		return zero, false
    76  	}
    77  	return e, true
    78  }
    79  
    80  //go:linkname runtime_mapaccess2 runtime.mapaccess2
    81  func runtime_mapaccess2(typ *abi.MapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
    82  	if race.Enabled && m != nil {
    83  		callerpc := sys.GetCallerPC()
    84  		pc := abi.FuncPCABIInternal(runtime_mapaccess2)
    85  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
    86  		race.ReadObjectPC(typ.Key, key, callerpc, pc)
    87  	}
    88  	if msan.Enabled && m != nil {
    89  		msan.Read(key, typ.Key.Size_)
    90  	}
    91  	if asan.Enabled && m != nil {
    92  		asan.Read(key, typ.Key.Size_)
    93  	}
    94  
    95  	if m == nil || m.Used() == 0 {
    96  		if err := mapKeyError(typ, key); err != nil {
    97  			panic(err) // see issue 23734
    98  		}
    99  		return unsafe.Pointer(&zeroVal[0]), false
   100  	}
   101  
   102  	if m.writing != 0 {
   103  		fatal("concurrent map read and map write")
   104  	}
   105  
   106  	hash := typ.Hasher(key, m.seed)
   107  
   108  	if m.dirLen == 0 {
   109  		_, elem, ok := m.getWithKeySmall(typ, hash, key)
   110  		if !ok {
   111  			return unsafe.Pointer(&zeroVal[0]), false
   112  		}
   113  		return elem, true
   114  	}
   115  
   116  	// Select table.
   117  	idx := m.directoryIndex(hash)
   118  	t := m.directoryAt(idx)
   119  
   120  	// Probe table.
   121  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   122  	h2Hash := h2(hash)
   123  	for ; ; seq = seq.next() {
   124  		g := t.groups.group(typ, seq.offset)
   125  
   126  		match := g.ctrls().matchH2(h2Hash)
   127  
   128  		for match != 0 {
   129  			i := match.first()
   130  
   131  			slotKey := g.key(typ, i)
   132  			slotKeyOrig := slotKey
   133  			if typ.IndirectKey() {
   134  				slotKey = *((*unsafe.Pointer)(slotKey))
   135  			}
   136  			if typ.Key.Equal(key, slotKey) {
   137  				var slotElem unsafe.Pointer
   138  				if goexperiment.MapSplitGroup {
   139  					slotElem = g.elem(typ, i)
   140  				} else {
   141  					slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   142  				}
   143  				if typ.IndirectElem() {
   144  					slotElem = *((*unsafe.Pointer)(slotElem))
   145  				}
   146  				return slotElem, true
   147  			}
   148  			match = match.removeFirst()
   149  		}
   150  
   151  		match = g.ctrls().matchEmpty()
   152  		if match != 0 {
   153  			// Finding an empty slot means we've reached the end of
   154  			// the probe sequence.
   155  			return unsafe.Pointer(&zeroVal[0]), false
   156  		}
   157  	}
   158  }
   159  
   160  //go:linkname runtime_mapassign runtime.mapassign
   161  func runtime_mapassign(typ *abi.MapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
   162  	if m == nil {
   163  		panic(errNilAssign)
   164  	}
   165  	if race.Enabled {
   166  		callerpc := sys.GetCallerPC()
   167  		pc := abi.FuncPCABIInternal(runtime_mapassign)
   168  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   169  		race.ReadObjectPC(typ.Key, key, callerpc, pc)
   170  	}
   171  	if msan.Enabled {
   172  		msan.Read(key, typ.Key.Size_)
   173  	}
   174  	if asan.Enabled {
   175  		asan.Read(key, typ.Key.Size_)
   176  	}
   177  	if m.writing != 0 {
   178  		fatal("concurrent map writes")
   179  	}
   180  
   181  	hash := typ.Hasher(key, m.seed)
   182  
   183  	// Set writing after calling Hasher, since Hasher may panic, in which
   184  	// case we have not actually done a write.
   185  	m.writing ^= 1 // toggle, see comment on writing
   186  
   187  	if m.dirPtr == nil {
   188  		m.growToSmall(typ)
   189  	}
   190  
   191  	if m.dirLen == 0 {
   192  		elem := m.putSlotSmall(typ, hash, key)
   193  		if elem == nil {
   194  			// Can't fit another entry, grow to full size map.
   195  			tab := m.growToTable(typ)
   196  
   197  			elem = tab.uncheckedPutSlotForAssign(typ, hash, key)
   198  			m.used++
   199  
   200  			tab.checkInvariants(typ, m)
   201  		}
   202  
   203  		if m.writing == 0 {
   204  			fatal("concurrent map writes")
   205  		}
   206  		m.writing ^= 1
   207  
   208  		return elem
   209  	}
   210  
   211  	var slotElem unsafe.Pointer
   212  outer:
   213  	for {
   214  		// Select table.
   215  		idx := m.directoryIndex(hash)
   216  		t := m.directoryAt(idx)
   217  
   218  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   219  
   220  		// As we look for a match, keep track of the first deleted slot
   221  		// we find, which we'll use to insert the new entry if
   222  		// necessary.
   223  		var firstDeletedGroup groupReference
   224  		var firstDeletedSlot uintptr
   225  
   226  		h2Hash := h2(hash)
   227  		for ; ; seq = seq.next() {
   228  			g := t.groups.group(typ, seq.offset)
   229  			match := g.ctrls().matchH2(h2Hash)
   230  
   231  			// Look for an existing slot containing this key.
   232  			for match != 0 {
   233  				i := match.first()
   234  
   235  				slotKey := g.key(typ, i)
   236  				slotKeyOrig := slotKey
   237  				if typ.IndirectKey() {
   238  					slotKey = *((*unsafe.Pointer)(slotKey))
   239  				}
   240  				if typ.Key.Equal(key, slotKey) {
   241  					if typ.NeedKeyUpdate() {
   242  						typedmemmove(typ.Key, slotKey, key)
   243  					}
   244  
   245  					if goexperiment.MapSplitGroup {
   246  						slotElem = g.elem(typ, i)
   247  					} else {
   248  						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   249  					}
   250  					if typ.IndirectElem() {
   251  						slotElem = *((*unsafe.Pointer)(slotElem))
   252  					}
   253  
   254  					t.checkInvariants(typ, m)
   255  					break outer
   256  				}
   257  				match = match.removeFirst()
   258  			}
   259  
   260  			// No existing slot for this key in this group. Is this the end
   261  			// of the probe sequence?
   262  			match = g.ctrls().matchEmpty()
   263  			if match != 0 {
   264  				// Finding an empty slot means we've reached the end of
   265  				// the probe sequence.
   266  
   267  				var i uintptr
   268  
   269  				// If we found a deleted slot along the way, we
   270  				// can replace it without consuming growthLeft.
   271  				if firstDeletedGroup.data != nil {
   272  					g = firstDeletedGroup
   273  					i = firstDeletedSlot
   274  					t.growthLeft++ // will be decremented below to become a no-op.
   275  				} else {
   276  					// Otherwise, use the empty slot.
   277  					i = match.first()
   278  				}
   279  
   280  				// If there is room left to grow, just insert the new entry.
   281  				if t.growthLeft > 0 {
   282  					slotKey := g.key(typ, i)
   283  					slotKeyOrig := slotKey
   284  					if typ.IndirectKey() {
   285  						kmem := newobject(typ.Key)
   286  						*(*unsafe.Pointer)(slotKey) = kmem
   287  						slotKey = kmem
   288  					}
   289  					typedmemmove(typ.Key, slotKey, key)
   290  
   291  					if goexperiment.MapSplitGroup {
   292  						slotElem = g.elem(typ, i)
   293  					} else {
   294  						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   295  					}
   296  					if typ.IndirectElem() {
   297  						emem := newobject(typ.Elem)
   298  						*(*unsafe.Pointer)(slotElem) = emem
   299  						slotElem = emem
   300  					}
   301  
   302  					g.ctrls().set(i, ctrl(h2Hash))
   303  					t.growthLeft--
   304  					t.used++
   305  					m.used++
   306  
   307  					t.checkInvariants(typ, m)
   308  					break outer
   309  				}
   310  
   311  				t.rehash(typ, m)
   312  				continue outer
   313  			}
   314  
   315  			// No empty slots in this group. Check for a deleted
   316  			// slot, which we'll use if we don't find a match later
   317  			// in the probe sequence.
   318  			//
   319  			// We only need to remember a single deleted slot.
   320  			if firstDeletedGroup.data == nil {
   321  				// Since we already checked for empty slots
   322  				// above, matches here must be deleted slots.
   323  				match = g.ctrls().matchEmptyOrDeleted()
   324  				if match != 0 {
   325  					firstDeletedGroup = g
   326  					firstDeletedSlot = match.first()
   327  				}
   328  			}
   329  		}
   330  	}
   331  
   332  	if m.writing == 0 {
   333  		fatal("concurrent map writes")
   334  	}
   335  	m.writing ^= 1
   336  
   337  	return slotElem
   338  }
   339
View as plain text