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:linkname 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_mapaccess2 runtime.mapaccess2
    63  func runtime_mapaccess2(typ *abi.MapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
    64  	if race.Enabled && m != nil {
    65  		callerpc := sys.GetCallerPC()
    66  		pc := abi.FuncPCABIInternal(runtime_mapaccess2)
    67  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
    68  		race.ReadObjectPC(typ.Key, key, callerpc, pc)
    69  	}
    70  	if msan.Enabled && m != nil {
    71  		msan.Read(key, typ.Key.Size_)
    72  	}
    73  	if asan.Enabled && m != nil {
    74  		asan.Read(key, typ.Key.Size_)
    75  	}
    76  
    77  	if m == nil || m.Used() == 0 {
    78  		if err := mapKeyError(typ, key); err != nil {
    79  			panic(err) // see issue 23734
    80  		}
    81  		return unsafe.Pointer(&zeroVal[0]), false
    82  	}
    83  
    84  	if m.writing != 0 {
    85  		fatal("concurrent map read and map write")
    86  	}
    87  
    88  	hash := typ.Hasher(key, m.seed)
    89  
    90  	if m.dirLen == 0 {
    91  		_, elem, ok := m.getWithKeySmall(typ, hash, key)
    92  		if !ok {
    93  			return unsafe.Pointer(&zeroVal[0]), false
    94  		}
    95  		return elem, true
    96  	}
    97  
    98  	// Select table.
    99  	idx := m.directoryIndex(hash)
   100  	t := m.directoryAt(idx)
   101  
   102  	// Probe table.
   103  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   104  	h2Hash := h2(hash)
   105  	for ; ; seq = seq.next() {
   106  		g := t.groups.group(typ, seq.offset)
   107  
   108  		match := g.ctrls().matchH2(h2Hash)
   109  
   110  		for match != 0 {
   111  			i := match.first()
   112  
   113  			slotKey := g.key(typ, i)
   114  			slotKeyOrig := slotKey
   115  			if typ.IndirectKey() {
   116  				slotKey = *((*unsafe.Pointer)(slotKey))
   117  			}
   118  			if typ.Key.Equal(key, slotKey) {
   119  				var slotElem unsafe.Pointer
   120  				if goexperiment.MapSplitGroup {
   121  					slotElem = g.elem(typ, i)
   122  				} else {
   123  					slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   124  				}
   125  				if typ.IndirectElem() {
   126  					slotElem = *((*unsafe.Pointer)(slotElem))
   127  				}
   128  				return slotElem, true
   129  			}
   130  			match = match.removeFirst()
   131  		}
   132  
   133  		match = g.ctrls().matchEmpty()
   134  		if match != 0 {
   135  			// Finding an empty slot means we've reached the end of
   136  			// the probe sequence.
   137  			return unsafe.Pointer(&zeroVal[0]), false
   138  		}
   139  	}
   140  }
   141  
   142  //go:linkname runtime_mapassign runtime.mapassign
   143  func runtime_mapassign(typ *abi.MapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
   144  	if m == nil {
   145  		panic(errNilAssign)
   146  	}
   147  	if race.Enabled {
   148  		callerpc := sys.GetCallerPC()
   149  		pc := abi.FuncPCABIInternal(runtime_mapassign)
   150  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   151  		race.ReadObjectPC(typ.Key, key, callerpc, pc)
   152  	}
   153  	if msan.Enabled {
   154  		msan.Read(key, typ.Key.Size_)
   155  	}
   156  	if asan.Enabled {
   157  		asan.Read(key, typ.Key.Size_)
   158  	}
   159  	if m.writing != 0 {
   160  		fatal("concurrent map writes")
   161  	}
   162  
   163  	hash := typ.Hasher(key, m.seed)
   164  
   165  	// Set writing after calling Hasher, since Hasher may panic, in which
   166  	// case we have not actually done a write.
   167  	m.writing ^= 1 // toggle, see comment on writing
   168  
   169  	if m.dirPtr == nil {
   170  		m.growToSmall(typ)
   171  	}
   172  
   173  	if m.dirLen == 0 {
   174  		elem := m.putSlotSmall(typ, hash, key)
   175  		if elem == nil {
   176  			// Can't fit another entry, grow to full size map.
   177  			tab := m.growToTable(typ)
   178  
   179  			elem = tab.uncheckedPutSlotForAssign(typ, hash, key)
   180  			m.used++
   181  
   182  			tab.checkInvariants(typ, m)
   183  		}
   184  
   185  		if m.writing == 0 {
   186  			fatal("concurrent map writes")
   187  		}
   188  		m.writing ^= 1
   189  
   190  		return elem
   191  	}
   192  
   193  	var slotElem unsafe.Pointer
   194  outer:
   195  	for {
   196  		// Select table.
   197  		idx := m.directoryIndex(hash)
   198  		t := m.directoryAt(idx)
   199  
   200  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   201  
   202  		// As we look for a match, keep track of the first deleted slot
   203  		// we find, which we'll use to insert the new entry if
   204  		// necessary.
   205  		var firstDeletedGroup groupReference
   206  		var firstDeletedSlot uintptr
   207  
   208  		h2Hash := h2(hash)
   209  		for ; ; seq = seq.next() {
   210  			g := t.groups.group(typ, seq.offset)
   211  			match := g.ctrls().matchH2(h2Hash)
   212  
   213  			// Look for an existing slot containing this key.
   214  			for match != 0 {
   215  				i := match.first()
   216  
   217  				slotKey := g.key(typ, i)
   218  				slotKeyOrig := slotKey
   219  				if typ.IndirectKey() {
   220  					slotKey = *((*unsafe.Pointer)(slotKey))
   221  				}
   222  				if typ.Key.Equal(key, slotKey) {
   223  					if typ.NeedKeyUpdate() {
   224  						typedmemmove(typ.Key, slotKey, key)
   225  					}
   226  
   227  					if goexperiment.MapSplitGroup {
   228  						slotElem = g.elem(typ, i)
   229  					} else {
   230  						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   231  					}
   232  					if typ.IndirectElem() {
   233  						slotElem = *((*unsafe.Pointer)(slotElem))
   234  					}
   235  
   236  					t.checkInvariants(typ, m)
   237  					break outer
   238  				}
   239  				match = match.removeFirst()
   240  			}
   241  
   242  			// No existing slot for this key in this group. Is this the end
   243  			// of the probe sequence?
   244  			match = g.ctrls().matchEmpty()
   245  			if match != 0 {
   246  				// Finding an empty slot means we've reached the end of
   247  				// the probe sequence.
   248  
   249  				var i uintptr
   250  
   251  				// If we found a deleted slot along the way, we
   252  				// can replace it without consuming growthLeft.
   253  				if firstDeletedGroup.data != nil {
   254  					g = firstDeletedGroup
   255  					i = firstDeletedSlot
   256  					t.growthLeft++ // will be decremented below to become a no-op.
   257  				} else {
   258  					// Otherwise, use the empty slot.
   259  					i = match.first()
   260  				}
   261  
   262  				// If there is room left to grow, just insert the new entry.
   263  				if t.growthLeft > 0 {
   264  					slotKey := g.key(typ, i)
   265  					slotKeyOrig := slotKey
   266  					if typ.IndirectKey() {
   267  						kmem := newobject(typ.Key)
   268  						*(*unsafe.Pointer)(slotKey) = kmem
   269  						slotKey = kmem
   270  					}
   271  					typedmemmove(typ.Key, slotKey, key)
   272  
   273  					if goexperiment.MapSplitGroup {
   274  						slotElem = g.elem(typ, i)
   275  					} else {
   276  						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
   277  					}
   278  					if typ.IndirectElem() {
   279  						emem := newobject(typ.Elem)
   280  						*(*unsafe.Pointer)(slotElem) = emem
   281  						slotElem = emem
   282  					}
   283  
   284  					g.ctrls().set(i, ctrl(h2Hash))
   285  					t.growthLeft--
   286  					t.used++
   287  					m.used++
   288  
   289  					t.checkInvariants(typ, m)
   290  					break outer
   291  				}
   292  
   293  				t.rehash(typ, m)
   294  				continue outer
   295  			}
   296  
   297  			// No empty slots in this group. Check for a deleted
   298  			// slot, which we'll use if we don't find a match later
   299  			// in the probe sequence.
   300  			//
   301  			// We only need to remember a single deleted slot.
   302  			if firstDeletedGroup.data == nil {
   303  				// Since we already checked for empty slots
   304  				// above, matches here must be deleted slots.
   305  				match = g.ctrls().matchEmptyOrDeleted()
   306  				if match != 0 {
   307  					firstDeletedGroup = g
   308  					firstDeletedSlot = match.first()
   309  				}
   310  			}
   311  		}
   312  	}
   313  
   314  	if m.writing == 0 {
   315  		fatal("concurrent map writes")
   316  	}
   317  	m.writing ^= 1
   318  
   319  	return slotElem
   320  }
   321
View as plain text