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