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