runtime_fast32.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/goexperiment"
    10  	"internal/race"
    11  	"internal/runtime/sys"
    12  	"unsafe"
    13  )
    14  
    15  //go:linkname runtime_mapaccess1_fast32 runtime.mapaccess1_fast32
    16  func runtime_mapaccess1_fast32(typ *abi.MapType, m *Map, key uint32) unsafe.Pointer {
    17  	p, _ := runtime_mapaccess2_fast32(typ, m, key)
    18  	return p
    19  }
    20  
    21  //go:linkname runtime_mapaccess2_fast32 runtime.mapaccess2_fast32
    22  func runtime_mapaccess2_fast32(typ *abi.MapType, m *Map, key uint32) (unsafe.Pointer, bool) {
    23  	if race.Enabled && m != nil {
    24  		callerpc := sys.GetCallerPC()
    25  		pc := abi.FuncPCABIInternal(runtime_mapaccess2_fast32)
    26  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
    27  	}
    28  
    29  	if m == nil || m.Used() == 0 {
    30  		return unsafe.Pointer(&zeroVal[0]), false
    31  	}
    32  
    33  	if m.writing != 0 {
    34  		fatal("concurrent map read and map write")
    35  		return nil, false
    36  	}
    37  
    38  	if m.dirLen == 0 {
    39  		g := groupReference{
    40  			data: m.dirPtr,
    41  		}
    42  		full := g.ctrls().matchFull()
    43  		slotKey := g.key(typ, 0)
    44  		var keyStride uintptr
    45  		if goexperiment.MapSplitGroup {
    46  			keyStride = 4 // keys are contiguous in split layout
    47  		} else {
    48  			keyStride = typ.KeyStride // == SlotSize in interleaved layout
    49  		}
    50  		var i uintptr
    51  		for full != 0 {
    52  			if key == *(*uint32)(slotKey) && full.lowestSet() {
    53  				if goexperiment.MapSplitGroup {
    54  					return g.elem(typ, i), true
    55  				} else {
    56  					return unsafe.Pointer(uintptr(slotKey) + typ.ElemOff), true
    57  				}
    58  			}
    59  			slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
    60  			full = full.shiftOutLowest()
    61  			i++
    62  		}
    63  		return unsafe.Pointer(&zeroVal[0]), false
    64  	}
    65  
    66  	var hash uintptr
    67  	// Explicitly inline MemHash32.
    68  	// MemHash32 cost is higher than the threshold for inlining.
    69  	// But when we are using intrinsic implementation we want it to be inlined,
    70  	// since it improves performance.
    71  	//
    72  	// Note: memHashAESImplemented is compile time constant. We use it to remove runtime UseAeshash check
    73  	// for architectures where we don't have AES hashing implementations.
    74  	if memHashAESImplemented && UseAeshash {
    75  		hash = memHash32AES(key, m.seed)
    76  	} else {
    77  		hash = memHash32Fallback(key, m.seed)
    78  	}
    79  
    80  	// Select table.
    81  	idx := m.directoryIndex(hash)
    82  	t := m.directoryAt(idx)
    83  
    84  	// Probe table.
    85  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    86  	h2Hash := h2(hash)
    87  	for ; ; seq = seq.next() {
    88  		g := t.groups.group(typ, seq.offset)
    89  
    90  		match := g.ctrls().matchH2(h2Hash)
    91  
    92  		for match != 0 {
    93  			i := match.first()
    94  
    95  			slotKey := g.key(typ, i)
    96  			if key == *(*uint32)(slotKey) {
    97  				if goexperiment.MapSplitGroup {
    98  					return g.elem(typ, i), true
    99  				} else {
   100  					return unsafe.Pointer(uintptr(slotKey) + typ.ElemOff), true
   101  				}
   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]), false
   111  		}
   112  	}
   113  }
   114  
   115  func (m *Map) putSlotSmallFast32(typ *abi.MapType, hash uintptr, key uint32) unsafe.Pointer {
   116  	g := groupReference{
   117  		data: m.dirPtr,
   118  	}
   119  
   120  	match := g.ctrls().matchH2(h2(hash))
   121  
   122  	// Look for an existing slot containing this key.
   123  	for match != 0 {
   124  		i := match.first()
   125  
   126  		slotKey := g.key(typ, i)
   127  		if key == *(*uint32)(slotKey) {
   128  			slotElem := g.elem(typ, i)
   129  			return slotElem
   130  		}
   131  		match = match.removeFirst()
   132  	}
   133  
   134  	// There can't be deleted slots, small maps can't have them
   135  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   136  	// more efficient than matchEmpty.
   137  	match = g.ctrls().matchEmptyOrDeleted()
   138  	if match == 0 {
   139  		// No empty slot found. Need to grow the map.
   140  		return nil
   141  	}
   142  
   143  	i := match.first()
   144  
   145  	slotKey := g.key(typ, i)
   146  	*(*uint32)(slotKey) = key
   147  
   148  	slotElem := g.elem(typ, i)
   149  
   150  	g.ctrls().set(i, ctrl(h2(hash)))
   151  	m.used++
   152  
   153  	return slotElem
   154  }
   155  
   156  func (t *table) uncheckedPutSlotForAssignFast32(typ *abi.MapType, hash uintptr, key uint32) unsafe.Pointer {
   157  	if t.growthLeft == 0 {
   158  		panic("invariant failed: growthLeft is unexpectedly 0")
   159  	}
   160  
   161  	// Given key and its hash hash(key), to insert it, we construct a
   162  	// probeSeq, and use it to find the first group with an unoccupied (empty
   163  	// or deleted) slot. We place the key/value into the first such slot in
   164  	// the group and mark it as full with key's H2.
   165  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   166  	for ; ; seq = seq.next() {
   167  		g := t.groups.group(typ, seq.offset)
   168  
   169  		match := g.ctrls().matchEmptyOrDeleted()
   170  		if match != 0 {
   171  			i := match.first()
   172  
   173  			slotKey := g.key(typ, i)
   174  			*(*uint32)(slotKey) = key
   175  
   176  			slotElem := g.elem(typ, i)
   177  
   178  			t.growthLeft--
   179  			t.used++
   180  			g.ctrls().set(i, ctrl(h2(hash)))
   181  			return slotElem
   182  		}
   183  	}
   184  }
   185  
   186  //go:linkname runtime_mapassign_fast32 runtime.mapassign_fast32
   187  func runtime_mapassign_fast32(typ *abi.MapType, m *Map, key uint32) unsafe.Pointer {
   188  	if m == nil {
   189  		panic(errNilAssign)
   190  	}
   191  	if race.Enabled {
   192  		callerpc := sys.GetCallerPC()
   193  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast32)
   194  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   195  	}
   196  	if m.writing != 0 {
   197  		fatal("concurrent map writes")
   198  	}
   199  
   200  	var hash uintptr
   201  	// See the related comment in runtime_mapaccess2_fast32
   202  	if memHashAESImplemented && UseAeshash {
   203  		hash = memHash32AES(key, m.seed)
   204  	} else {
   205  		hash = memHash32Fallback(key, m.seed)
   206  	}
   207  
   208  	// Set writing after calling Hasher, since Hasher may panic, in which
   209  	// case we have not actually done a write.
   210  	m.writing ^= 1 // toggle, see comment on writing
   211  
   212  	if m.dirPtr == nil {
   213  		m.growToSmall(typ)
   214  	}
   215  
   216  	if m.dirLen == 0 {
   217  		elem := m.putSlotSmallFast32(typ, hash, key)
   218  		if elem == nil {
   219  			// Can't fit another entry, grow to full size map.
   220  			tab := m.growToTable(typ)
   221  
   222  			elem = tab.uncheckedPutSlotForAssignFast32(typ, hash, key)
   223  			m.used++
   224  
   225  			tab.checkInvariants(typ, m)
   226  		}
   227  
   228  		if m.writing == 0 {
   229  			fatal("concurrent map writes")
   230  		}
   231  		m.writing ^= 1
   232  
   233  		return elem
   234  	}
   235  
   236  	var slotElem unsafe.Pointer
   237  outer:
   238  	for {
   239  		// Select table.
   240  		idx := m.directoryIndex(hash)
   241  		t := m.directoryAt(idx)
   242  
   243  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   244  
   245  		// As we look for a match, keep track of the first deleted slot
   246  		// we find, which we'll use to insert the new entry if
   247  		// necessary.
   248  		var firstDeletedGroup groupReference
   249  		var firstDeletedSlot uintptr
   250  
   251  		h2Hash := h2(hash)
   252  		for ; ; seq = seq.next() {
   253  			g := t.groups.group(typ, seq.offset)
   254  			match := g.ctrls().matchH2(h2Hash)
   255  
   256  			// Look for an existing slot containing this key.
   257  			for match != 0 {
   258  				i := match.first()
   259  
   260  				slotKey := g.key(typ, i)
   261  				if key == *(*uint32)(slotKey) {
   262  					slotElem = g.elem(typ, i)
   263  
   264  					t.checkInvariants(typ, m)
   265  					break outer
   266  				}
   267  				match = match.removeFirst()
   268  			}
   269  
   270  			// No existing slot for this key in this group. Is this the end
   271  			// of the probe sequence?
   272  			match = g.ctrls().matchEmptyOrDeleted()
   273  			if match == 0 {
   274  				continue // nothing but filled slots. Keep probing.
   275  			}
   276  			i := match.first()
   277  			if g.ctrls().get(i) == ctrlDeleted {
   278  				// There are some deleted slots. Remember
   279  				// the first one, and keep probing.
   280  				if firstDeletedGroup.data == nil {
   281  					firstDeletedGroup = g
   282  					firstDeletedSlot = i
   283  				}
   284  				continue
   285  			}
   286  			// We've found an empty slot, which means we've reached the end of
   287  			// the probe sequence.
   288  
   289  			// If we found a deleted slot along the way, we can
   290  			// replace it without consuming growthLeft.
   291  			if firstDeletedGroup.data != nil {
   292  				g = firstDeletedGroup
   293  				i = firstDeletedSlot
   294  				t.growthLeft++ // will be decremented below to become a no-op.
   295  			}
   296  
   297  			// If we have no space left, first try to remove some tombstones.
   298  			if t.growthLeft == 0 {
   299  				t.pruneTombstones(typ, m)
   300  			}
   301  
   302  			// If there is room left to grow, just insert the new entry.
   303  			if t.growthLeft > 0 {
   304  				slotKey := g.key(typ, i)
   305  				*(*uint32)(slotKey) = key
   306  
   307  				slotElem = g.elem(typ, i)
   308  
   309  				g.ctrls().set(i, ctrl(h2Hash))
   310  				t.growthLeft--
   311  				t.used++
   312  				m.used++
   313  
   314  				t.checkInvariants(typ, m)
   315  				break outer
   316  			}
   317  
   318  			t.rehash(typ, m)
   319  			continue outer
   320  		}
   321  	}
   322  
   323  	if m.writing == 0 {
   324  		fatal("concurrent map writes")
   325  	}
   326  	m.writing ^= 1
   327  
   328  	return slotElem
   329  }
   330  
   331  // Key is a 32-bit pointer (only called on 32-bit GOARCH). This source is identical to fast64ptr.
   332  //
   333  // TODO(prattmic): With some compiler refactoring we could avoid duplication of this function.
   334  //
   335  //go:linkname runtime_mapassign_fast32ptr runtime.mapassign_fast32ptr
   336  func runtime_mapassign_fast32ptr(typ *abi.MapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
   337  	if m == nil {
   338  		panic(errNilAssign)
   339  	}
   340  	if race.Enabled {
   341  		callerpc := sys.GetCallerPC()
   342  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast32ptr)
   343  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   344  	}
   345  	if m.writing != 0 {
   346  		fatal("concurrent map writes")
   347  	}
   348  
   349  	var hash uintptr
   350  	// See the related comment in runtime_mapaccess2_fast32
   351  	if memHashAESImplemented && UseAeshash {
   352  		hash = memHash32AES(uint32((uintptr)(key)), m.seed)
   353  	} else {
   354  		hash = memHash32Fallback(uint32((uintptr)(key)), m.seed)
   355  	}
   356  
   357  	// Set writing after calling Hasher, since Hasher may panic, in which
   358  	// case we have not actually done a write.
   359  	m.writing ^= 1 // toggle, see comment on writing
   360  
   361  	if m.dirPtr == nil {
   362  		m.growToSmall(typ)
   363  	}
   364  
   365  	if m.dirLen == 0 {
   366  		elem := m.putSlotSmallFastPtr(typ, hash, key)
   367  		if elem == nil {
   368  			// Can't fit another entry, grow to full size map.
   369  			tab := m.growToTable(typ)
   370  
   371  			elem = tab.uncheckedPutSlotForAssignFastPtr(typ, hash, key)
   372  			m.used++
   373  
   374  			tab.checkInvariants(typ, m)
   375  		}
   376  
   377  		if m.writing == 0 {
   378  			fatal("concurrent map writes")
   379  		}
   380  		m.writing ^= 1
   381  
   382  		return elem
   383  	}
   384  
   385  	var slotElem unsafe.Pointer
   386  outer:
   387  	for {
   388  		// Select table.
   389  		idx := m.directoryIndex(hash)
   390  		t := m.directoryAt(idx)
   391  
   392  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   393  
   394  		// As we look for a match, keep track of the first deleted slot we
   395  		// find, which we'll use to insert the new entry if necessary.
   396  		var firstDeletedGroup groupReference
   397  		var firstDeletedSlot uintptr
   398  
   399  		h2Hash := h2(hash)
   400  		for ; ; seq = seq.next() {
   401  			g := t.groups.group(typ, seq.offset)
   402  			match := g.ctrls().matchH2(h2Hash)
   403  
   404  			// Look for an existing slot containing this key.
   405  			for match != 0 {
   406  				i := match.first()
   407  
   408  				slotKey := g.key(typ, i)
   409  				if key == *(*unsafe.Pointer)(slotKey) {
   410  					slotElem = g.elem(typ, i)
   411  
   412  					t.checkInvariants(typ, m)
   413  					break outer
   414  				}
   415  				match = match.removeFirst()
   416  			}
   417  
   418  			// No existing slot for this key in this group. Is this the end
   419  			// of the probe sequence?
   420  			match = g.ctrls().matchEmptyOrDeleted()
   421  			if match == 0 {
   422  				continue // nothing but filled slots. Keep probing.
   423  			}
   424  			i := match.first()
   425  			if g.ctrls().get(i) == ctrlDeleted {
   426  				// There are some deleted slots. Remember
   427  				// the first one, and keep probing.
   428  				if firstDeletedGroup.data == nil {
   429  					firstDeletedGroup = g
   430  					firstDeletedSlot = i
   431  				}
   432  				continue
   433  			}
   434  			// We've found an empty slot, which means we've reached the end of
   435  			// the probe sequence.
   436  
   437  			// If we found a deleted slot along the way, we can
   438  			// replace it without consuming growthLeft.
   439  			if firstDeletedGroup.data != nil {
   440  				g = firstDeletedGroup
   441  				i = firstDeletedSlot
   442  				t.growthLeft++ // will be decremented below to become a no-op.
   443  			}
   444  
   445  			if t.growthLeft == 0 {
   446  				t.pruneTombstones(typ, m)
   447  			}
   448  
   449  			// If there is room left to grow, just insert the new entry.
   450  			if t.growthLeft > 0 {
   451  				slotKey := g.key(typ, i)
   452  				*(*unsafe.Pointer)(slotKey) = key
   453  
   454  				slotElem = g.elem(typ, i)
   455  
   456  				g.ctrls().set(i, ctrl(h2Hash))
   457  				t.growthLeft--
   458  				t.used++
   459  				m.used++
   460  
   461  				t.checkInvariants(typ, m)
   462  				break outer
   463  			}
   464  
   465  			t.rehash(typ, m)
   466  			continue outer
   467  		}
   468  	}
   469  
   470  	if m.writing == 0 {
   471  		fatal("concurrent map writes")
   472  	}
   473  	m.writing ^= 1
   474  
   475  	return slotElem
   476  }
   477  
   478  //go:linkname runtime_mapdelete_fast32 runtime.mapdelete_fast32
   479  func runtime_mapdelete_fast32(typ *abi.MapType, m *Map, key uint32) {
   480  	if race.Enabled {
   481  		callerpc := sys.GetCallerPC()
   482  		pc := abi.FuncPCABIInternal(runtime_mapdelete_fast32)
   483  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   484  	}
   485  
   486  	if m == nil || m.Used() == 0 {
   487  		return
   488  	}
   489  
   490  	m.Delete(typ, abi.NoEscape(unsafe.Pointer(&key)))
   491  }
   492
View as plain text