runtime_fast64.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_fast64 runtime.mapaccess1_fast64
    16  func runtime_mapaccess1_fast64(typ *abi.MapType, m *Map, key uint64) unsafe.Pointer {
    17  	p, _ := runtime_mapaccess2_fast64(typ, m, key)
    18  	return p
    19  }
    20  
    21  //go:linkname runtime_mapaccess2_fast64 runtime.mapaccess2_fast64
    22  func runtime_mapaccess2_fast64(typ *abi.MapType, m *Map, key uint64) (unsafe.Pointer, bool) {
    23  	if race.Enabled && m != nil {
    24  		callerpc := sys.GetCallerPC()
    25  		pc := abi.FuncPCABIInternal(runtime_mapaccess2_fast64)
    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 = 8 // 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 == *(*uint64)(slotKey) && full.lowestSet() {
    53  				if goexperiment.MapSplitGroup {
    54  					return g.elem(typ, i), true
    55  				} else {
    56  					return unsafe.Pointer(uintptr(slotKey) + 8), 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  	// See the related comment in runtime_mapaccess2_fast32
    68  	if memHashAESImplemented && UseAeshash {
    69  		hash = memHash64AES(key, m.seed)
    70  	} else {
    71  		hash = memHash64Fallback(key, m.seed)
    72  	}
    73  
    74  	// Select table.
    75  	idx := m.directoryIndex(hash)
    76  	t := m.directoryAt(idx)
    77  
    78  	// Probe table.
    79  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    80  
    81  	h2Hash := h2(hash)
    82  	for ; ; seq = seq.next() {
    83  		g := t.groups.group(typ, seq.offset)
    84  
    85  		match := g.ctrls().matchH2(h2Hash)
    86  
    87  		for match != 0 {
    88  			i := match.first()
    89  
    90  			slotKey := g.key(typ, i)
    91  			if key == *(*uint64)(slotKey) {
    92  				if goexperiment.MapSplitGroup {
    93  					return g.elem(typ, i), true
    94  				} else {
    95  					return unsafe.Pointer(uintptr(slotKey) + 8), true
    96  				}
    97  			}
    98  			match = match.removeFirst()
    99  		}
   100  
   101  		match = g.ctrls().matchEmpty()
   102  		if match != 0 {
   103  			// Finding an empty slot means we've reached the end of
   104  			// the probe sequence.
   105  			return unsafe.Pointer(&zeroVal[0]), false
   106  		}
   107  	}
   108  }
   109  
   110  func (m *Map) putSlotSmallFast64(typ *abi.MapType, hash uintptr, key uint64) unsafe.Pointer {
   111  	g := groupReference{
   112  		data: m.dirPtr,
   113  	}
   114  
   115  	match := g.ctrls().matchH2(h2(hash))
   116  
   117  	// Look for an existing slot containing this key.
   118  	for match != 0 {
   119  		i := match.first()
   120  
   121  		slotKey := g.key(typ, i)
   122  		if key == *(*uint64)(slotKey) {
   123  			slotElem := g.elem(typ, i)
   124  			return slotElem
   125  		}
   126  		match = match.removeFirst()
   127  	}
   128  
   129  	// There can't be deleted slots, small maps can't have them
   130  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   131  	// more efficient than matchEmpty.
   132  	match = g.ctrls().matchEmptyOrDeleted()
   133  	if match == 0 {
   134  		// No empty slot found. Need to grow the map.
   135  		return nil
   136  	}
   137  
   138  	i := match.first()
   139  
   140  	slotKey := g.key(typ, i)
   141  	*(*uint64)(slotKey) = key
   142  
   143  	slotElem := g.elem(typ, i)
   144  
   145  	g.ctrls().set(i, ctrl(h2(hash)))
   146  	m.used++
   147  
   148  	return slotElem
   149  }
   150  
   151  func (t *table) uncheckedPutSlotForAssignFast64(typ *abi.MapType, hash uintptr, key uint64) unsafe.Pointer {
   152  	if t.growthLeft == 0 {
   153  		panic("invariant failed: growthLeft is unexpectedly 0")
   154  	}
   155  
   156  	// Given key and its hash hash(key), to insert it, we construct a
   157  	// probeSeq, and use it to find the first group with an unoccupied (empty
   158  	// or deleted) slot. We place the key/value into the first such slot in
   159  	// the group and mark it as full with key's H2.
   160  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   161  	for ; ; seq = seq.next() {
   162  		g := t.groups.group(typ, seq.offset)
   163  
   164  		match := g.ctrls().matchEmptyOrDeleted()
   165  		if match != 0 {
   166  			i := match.first()
   167  
   168  			slotKey := g.key(typ, i)
   169  			*(*uint64)(slotKey) = key
   170  
   171  			slotElem := g.elem(typ, i)
   172  
   173  			t.growthLeft--
   174  			t.used++
   175  			g.ctrls().set(i, ctrl(h2(hash)))
   176  			return slotElem
   177  		}
   178  	}
   179  }
   180  
   181  //go:linkname runtime_mapassign_fast64 runtime.mapassign_fast64
   182  func runtime_mapassign_fast64(typ *abi.MapType, m *Map, key uint64) unsafe.Pointer {
   183  	if m == nil {
   184  		panic(errNilAssign)
   185  	}
   186  	if race.Enabled {
   187  		callerpc := sys.GetCallerPC()
   188  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast64)
   189  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   190  	}
   191  	if m.writing != 0 {
   192  		fatal("concurrent map writes")
   193  	}
   194  
   195  	var hash uintptr
   196  	// See the related comment in runtime_mapaccess2_fast32
   197  	if memHashAESImplemented && UseAeshash {
   198  		hash = memHash64AES(key, m.seed)
   199  	} else {
   200  		hash = memHash64Fallback(key, m.seed)
   201  	}
   202  
   203  	// Set writing after calling Hasher, since Hasher may panic, in which
   204  	// case we have not actually done a write.
   205  	m.writing ^= 1 // toggle, see comment on writing
   206  
   207  	if m.dirPtr == nil {
   208  		m.growToSmall(typ)
   209  	}
   210  
   211  	if m.dirLen == 0 {
   212  		elem := m.putSlotSmallFast64(typ, hash, key)
   213  		if elem == nil {
   214  			// Can't fit another entry, grow to full size map.
   215  			tab := m.growToTable(typ)
   216  
   217  			elem = tab.uncheckedPutSlotForAssignFast64(typ, hash, key)
   218  			m.used++
   219  
   220  			tab.checkInvariants(typ, m)
   221  		}
   222  
   223  		if m.writing == 0 {
   224  			fatal("concurrent map writes")
   225  		}
   226  		m.writing ^= 1
   227  
   228  		return elem
   229  	}
   230  
   231  	var slotElem unsafe.Pointer
   232  outer:
   233  	for {
   234  		// Select table.
   235  		idx := m.directoryIndex(hash)
   236  		t := m.directoryAt(idx)
   237  
   238  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   239  
   240  		// As we look for a match, keep track of the first deleted slot
   241  		// we find, which we'll use to insert the new entry if
   242  		// necessary.
   243  		var firstDeletedGroup groupReference
   244  		var firstDeletedSlot uintptr
   245  
   246  		h2Hash := h2(hash)
   247  		for ; ; seq = seq.next() {
   248  			g := t.groups.group(typ, seq.offset)
   249  			match := g.ctrls().matchH2(h2Hash)
   250  
   251  			// Look for an existing slot containing this key.
   252  			for match != 0 {
   253  				i := match.first()
   254  
   255  				slotKey := g.key(typ, i)
   256  				if key == *(*uint64)(slotKey) {
   257  					slotElem = g.elem(typ, i)
   258  
   259  					t.checkInvariants(typ, m)
   260  					break outer
   261  				}
   262  				match = match.removeFirst()
   263  			}
   264  
   265  			// No existing slot for this key in this group. Is this the end
   266  			// of the probe sequence?
   267  			match = g.ctrls().matchEmptyOrDeleted()
   268  			if match == 0 {
   269  				continue // nothing but filled slots. Keep probing.
   270  			}
   271  			i := match.first()
   272  			if g.ctrls().get(i) == ctrlDeleted {
   273  				// There are some deleted slots. Remember
   274  				// the first one, and keep probing.
   275  				if firstDeletedGroup.data == nil {
   276  					firstDeletedGroup = g
   277  					firstDeletedSlot = i
   278  				}
   279  				continue
   280  			}
   281  			// We've found an empty slot, which means we've reached the end of
   282  			// the probe sequence.
   283  
   284  			// If we found a deleted slot along the way, we can
   285  			// replace it without consuming growthLeft.
   286  			if firstDeletedGroup.data != nil {
   287  				g = firstDeletedGroup
   288  				i = firstDeletedSlot
   289  				t.growthLeft++ // will be decremented below to become a no-op.
   290  			}
   291  
   292  			// If we have no space left, first try to remove some tombstones.
   293  			if t.growthLeft == 0 {
   294  				t.pruneTombstones(typ, m)
   295  			}
   296  
   297  			// If there is room left to grow, just insert the new entry.
   298  			if t.growthLeft > 0 {
   299  				slotKey := g.key(typ, i)
   300  				*(*uint64)(slotKey) = key
   301  
   302  				slotElem = g.elem(typ, i)
   303  
   304  				g.ctrls().set(i, ctrl(h2Hash))
   305  				t.growthLeft--
   306  				t.used++
   307  				m.used++
   308  
   309  				t.checkInvariants(typ, m)
   310  				break outer
   311  			}
   312  
   313  			t.rehash(typ, m)
   314  			continue outer
   315  		}
   316  	}
   317  
   318  	if m.writing == 0 {
   319  		fatal("concurrent map writes")
   320  	}
   321  	m.writing ^= 1
   322  
   323  	return slotElem
   324  }
   325  
   326  func (m *Map) putSlotSmallFastPtr(typ *abi.MapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
   327  	g := groupReference{
   328  		data: m.dirPtr,
   329  	}
   330  
   331  	match := g.ctrls().matchH2(h2(hash))
   332  
   333  	// Look for an existing slot containing this key.
   334  	for match != 0 {
   335  		i := match.first()
   336  
   337  		slotKey := g.key(typ, i)
   338  		if key == *(*unsafe.Pointer)(slotKey) {
   339  			slotElem := g.elem(typ, i)
   340  			return slotElem
   341  		}
   342  		match = match.removeFirst()
   343  	}
   344  
   345  	// There can't be deleted slots, small maps can't have them
   346  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   347  	// more efficient than matchEmpty.
   348  	match = g.ctrls().matchEmptyOrDeleted()
   349  	if match == 0 {
   350  		// No empty slot found. Need to grow the map.
   351  		return nil
   352  	}
   353  
   354  	i := match.first()
   355  
   356  	slotKey := g.key(typ, i)
   357  	*(*unsafe.Pointer)(slotKey) = key
   358  
   359  	slotElem := g.elem(typ, i)
   360  
   361  	g.ctrls().set(i, ctrl(h2(hash)))
   362  	m.used++
   363  
   364  	return slotElem
   365  }
   366  
   367  func (t *table) uncheckedPutSlotForAssignFastPtr(typ *abi.MapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
   368  	if t.growthLeft == 0 {
   369  		panic("invariant failed: growthLeft is unexpectedly 0")
   370  	}
   371  
   372  	// Given key and its hash hash(key), to insert it, we construct a
   373  	// probeSeq, and use it to find the first group with an unoccupied (empty
   374  	// or deleted) slot. We place the key/value into the first such slot in
   375  	// the group and mark it as full with key's H2.
   376  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   377  	for ; ; seq = seq.next() {
   378  		g := t.groups.group(typ, seq.offset)
   379  
   380  		match := g.ctrls().matchEmptyOrDeleted()
   381  		if match != 0 {
   382  			i := match.first()
   383  
   384  			slotKey := g.key(typ, i)
   385  			*(*unsafe.Pointer)(slotKey) = key
   386  
   387  			slotElem := g.elem(typ, i)
   388  
   389  			t.growthLeft--
   390  			t.used++
   391  			g.ctrls().set(i, ctrl(h2(hash)))
   392  			return slotElem
   393  		}
   394  	}
   395  }
   396  
   397  // Key is a 64-bit pointer (only called on 64-bit GOARCH).
   398  //
   399  //go:linkname runtime_mapassign_fast64ptr runtime.mapassign_fast64ptr
   400  func runtime_mapassign_fast64ptr(typ *abi.MapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
   401  	if m == nil {
   402  		panic(errNilAssign)
   403  	}
   404  	if race.Enabled {
   405  		callerpc := sys.GetCallerPC()
   406  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast64ptr)
   407  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   408  	}
   409  	if m.writing != 0 {
   410  		fatal("concurrent map writes")
   411  	}
   412  
   413  	var hash uintptr
   414  	// See the related comment in runtime_mapaccess2_fast32
   415  	if memHashAESImplemented && UseAeshash {
   416  		hash = memHash64AES(uint64((uintptr)(key)), m.seed)
   417  	} else {
   418  		hash = memHash64Fallback(uint64((uintptr)(key)), m.seed)
   419  	}
   420  
   421  	// Set writing after calling Hasher, since Hasher may panic, in which
   422  	// case we have not actually done a write.
   423  	m.writing ^= 1 // toggle, see comment on writing
   424  
   425  	if m.dirPtr == nil {
   426  		m.growToSmall(typ)
   427  	}
   428  
   429  	if m.dirLen == 0 {
   430  		elem := m.putSlotSmallFastPtr(typ, hash, key)
   431  		if elem == nil {
   432  			// Can't fit another entry, grow to full size map.
   433  			tab := m.growToTable(typ)
   434  
   435  			elem = tab.uncheckedPutSlotForAssignFastPtr(typ, hash, key)
   436  			m.used++
   437  
   438  			tab.checkInvariants(typ, m)
   439  		}
   440  
   441  		if m.writing == 0 {
   442  			fatal("concurrent map writes")
   443  		}
   444  		m.writing ^= 1
   445  
   446  		return elem
   447  	}
   448  
   449  	var slotElem unsafe.Pointer
   450  outer:
   451  	for {
   452  		// Select table.
   453  		idx := m.directoryIndex(hash)
   454  		t := m.directoryAt(idx)
   455  
   456  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   457  
   458  		// As we look for a match, keep track of the first deleted slot
   459  		// we find, which we'll use to insert the new entry if
   460  		// necessary.
   461  		var firstDeletedGroup groupReference
   462  		var firstDeletedSlot uintptr
   463  
   464  		h2Hash := h2(hash)
   465  		for ; ; seq = seq.next() {
   466  			g := t.groups.group(typ, seq.offset)
   467  			match := g.ctrls().matchH2(h2Hash)
   468  
   469  			// Look for an existing slot containing this key.
   470  			for match != 0 {
   471  				i := match.first()
   472  
   473  				slotKey := g.key(typ, i)
   474  				if key == *(*unsafe.Pointer)(slotKey) {
   475  					slotElem = g.elem(typ, i)
   476  
   477  					t.checkInvariants(typ, m)
   478  					break outer
   479  				}
   480  				match = match.removeFirst()
   481  			}
   482  
   483  			// No existing slot for this key in this group. Is this the end
   484  			// of the probe sequence?
   485  			match = g.ctrls().matchEmptyOrDeleted()
   486  			if match == 0 {
   487  				continue // nothing but filled slots. Keep probing.
   488  			}
   489  			i := match.first()
   490  			if g.ctrls().get(i) == ctrlDeleted {
   491  				// There are some deleted slots. Remember
   492  				// the first one, and keep probing.
   493  				if firstDeletedGroup.data == nil {
   494  					firstDeletedGroup = g
   495  					firstDeletedSlot = i
   496  				}
   497  				continue
   498  			}
   499  			// We've found an empty slot, which means we've reached the end of
   500  			// the probe sequence.
   501  
   502  			// If we found a deleted slot along the way, we can
   503  			// replace it without consuming growthLeft.
   504  			if firstDeletedGroup.data != nil {
   505  				g = firstDeletedGroup
   506  				i = firstDeletedSlot
   507  				t.growthLeft++ // will be decremented below to become a no-op.
   508  			}
   509  
   510  			if t.growthLeft == 0 {
   511  				t.pruneTombstones(typ, m)
   512  			}
   513  
   514  			// If there is room left to grow, just insert the new entry.
   515  			if t.growthLeft > 0 {
   516  				slotKey := g.key(typ, i)
   517  				*(*unsafe.Pointer)(slotKey) = key
   518  
   519  				slotElem = g.elem(typ, i)
   520  
   521  				g.ctrls().set(i, ctrl(h2Hash))
   522  				t.growthLeft--
   523  				t.used++
   524  				m.used++
   525  
   526  				t.checkInvariants(typ, m)
   527  				break outer
   528  			}
   529  
   530  			t.rehash(typ, m)
   531  			continue outer
   532  		}
   533  	}
   534  
   535  	if m.writing == 0 {
   536  		fatal("concurrent map writes")
   537  	}
   538  	m.writing ^= 1
   539  
   540  	return slotElem
   541  }
   542  
   543  //go:linkname runtime_mapdelete_fast64 runtime.mapdelete_fast64
   544  func runtime_mapdelete_fast64(typ *abi.MapType, m *Map, key uint64) {
   545  	if race.Enabled {
   546  		callerpc := sys.GetCallerPC()
   547  		pc := abi.FuncPCABIInternal(runtime_mapdelete_fast64)
   548  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   549  	}
   550  
   551  	if m == nil || m.Used() == 0 {
   552  		return
   553  	}
   554  
   555  	m.Delete(typ, abi.NoEscape(unsafe.Pointer(&key)))
   556  }
   557
View as plain text