Source file src/internal/runtime/maps/runtime_fast64_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/race"
    12  	"internal/runtime/sys"
    13  	"unsafe"
    14  )
    15  
    16  //go:linkname runtime_mapaccess1_fast64 runtime.mapaccess1_fast64
    17  func runtime_mapaccess1_fast64(typ *abi.SwissMapType, m *Map, key uint64) unsafe.Pointer {
    18  	if race.Enabled && m != nil {
    19  		callerpc := sys.GetCallerPC()
    20  		pc := abi.FuncPCABIInternal(runtime_mapaccess1_fast64)
    21  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
    22  	}
    23  
    24  	if m == nil || m.Used() == 0 {
    25  		return unsafe.Pointer(&zeroVal[0])
    26  	}
    27  
    28  	if m.writing != 0 {
    29  		fatal("concurrent map read and map write")
    30  		return nil
    31  	}
    32  
    33  	if m.dirLen == 0 {
    34  		g := groupReference{
    35  			data: m.dirPtr,
    36  		}
    37  		full := g.ctrls().matchFull()
    38  		slotKey := g.key(typ, 0)
    39  		slotSize := typ.SlotSize
    40  		for full != 0 {
    41  			if key == *(*uint64)(slotKey) && full.lowestSet() {
    42  				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
    43  				return slotElem
    44  			}
    45  			slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
    46  			full = full.shiftOutLowest()
    47  		}
    48  		return unsafe.Pointer(&zeroVal[0])
    49  	}
    50  
    51  	k := key
    52  	hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
    53  
    54  	// Select table.
    55  	idx := m.directoryIndex(hash)
    56  	t := m.directoryAt(idx)
    57  
    58  	// Probe table.
    59  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    60  	for ; ; seq = seq.next() {
    61  		g := t.groups.group(typ, seq.offset)
    62  
    63  		match := g.ctrls().matchH2(h2(hash))
    64  
    65  		for match != 0 {
    66  			i := match.first()
    67  
    68  			slotKey := g.key(typ, i)
    69  			if key == *(*uint64)(slotKey) {
    70  				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
    71  				return slotElem
    72  			}
    73  			match = match.removeFirst()
    74  		}
    75  
    76  		match = g.ctrls().matchEmpty()
    77  		if match != 0 {
    78  			// Finding an empty slot means we've reached the end of
    79  			// the probe sequence.
    80  			return unsafe.Pointer(&zeroVal[0])
    81  		}
    82  	}
    83  }
    84  
    85  //go:linkname runtime_mapaccess2_fast64 runtime.mapaccess2_fast64
    86  func runtime_mapaccess2_fast64(typ *abi.SwissMapType, m *Map, key uint64) (unsafe.Pointer, bool) {
    87  	if race.Enabled && m != nil {
    88  		callerpc := sys.GetCallerPC()
    89  		pc := abi.FuncPCABIInternal(runtime_mapaccess2_fast64)
    90  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
    91  	}
    92  
    93  	if m == nil || m.Used() == 0 {
    94  		return unsafe.Pointer(&zeroVal[0]), false
    95  	}
    96  
    97  	if m.writing != 0 {
    98  		fatal("concurrent map read and map write")
    99  		return nil, false
   100  	}
   101  
   102  	if m.dirLen == 0 {
   103  		g := groupReference{
   104  			data: m.dirPtr,
   105  		}
   106  		full := g.ctrls().matchFull()
   107  		slotKey := g.key(typ, 0)
   108  		slotSize := typ.SlotSize
   109  		for full != 0 {
   110  			if key == *(*uint64)(slotKey) && full.lowestSet() {
   111  				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
   112  				return slotElem, true
   113  			}
   114  			slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
   115  			full = full.shiftOutLowest()
   116  		}
   117  		return unsafe.Pointer(&zeroVal[0]), false
   118  	}
   119  
   120  	k := key
   121  	hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
   122  
   123  	// Select table.
   124  	idx := m.directoryIndex(hash)
   125  	t := m.directoryAt(idx)
   126  
   127  	// Probe table.
   128  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   129  	for ; ; seq = seq.next() {
   130  		g := t.groups.group(typ, seq.offset)
   131  
   132  		match := g.ctrls().matchH2(h2(hash))
   133  
   134  		for match != 0 {
   135  			i := match.first()
   136  
   137  			slotKey := g.key(typ, i)
   138  			if key == *(*uint64)(slotKey) {
   139  				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
   140  				return slotElem, true
   141  			}
   142  			match = match.removeFirst()
   143  		}
   144  
   145  		match = g.ctrls().matchEmpty()
   146  		if match != 0 {
   147  			// Finding an empty slot means we've reached the end of
   148  			// the probe sequence.
   149  			return unsafe.Pointer(&zeroVal[0]), false
   150  		}
   151  	}
   152  }
   153  
   154  func (m *Map) putSlotSmallFast64(typ *abi.SwissMapType, hash uintptr, key uint64) unsafe.Pointer {
   155  	g := groupReference{
   156  		data: m.dirPtr,
   157  	}
   158  
   159  	match := g.ctrls().matchH2(h2(hash))
   160  
   161  	// Look for an existing slot containing this key.
   162  	for match != 0 {
   163  		i := match.first()
   164  
   165  		slotKey := g.key(typ, i)
   166  		if key == *(*uint64)(slotKey) {
   167  			slotElem := g.elem(typ, i)
   168  			return slotElem
   169  		}
   170  		match = match.removeFirst()
   171  	}
   172  
   173  	// There can't be deleted slots, small maps can't have them
   174  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   175  	// more efficient than matchEmpty.
   176  	match = g.ctrls().matchEmptyOrDeleted()
   177  	if match == 0 {
   178  		fatal("small map with no empty slot (concurrent map writes?)")
   179  	}
   180  
   181  	i := match.first()
   182  
   183  	slotKey := g.key(typ, i)
   184  	*(*uint64)(slotKey) = key
   185  
   186  	slotElem := g.elem(typ, i)
   187  
   188  	g.ctrls().set(i, ctrl(h2(hash)))
   189  	m.used++
   190  
   191  	return slotElem
   192  }
   193  
   194  //go:linkname runtime_mapassign_fast64 runtime.mapassign_fast64
   195  func runtime_mapassign_fast64(typ *abi.SwissMapType, m *Map, key uint64) unsafe.Pointer {
   196  	if m == nil {
   197  		panic(errNilAssign)
   198  	}
   199  	if race.Enabled {
   200  		callerpc := sys.GetCallerPC()
   201  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast64)
   202  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   203  	}
   204  	if m.writing != 0 {
   205  		fatal("concurrent map writes")
   206  	}
   207  
   208  	k := key
   209  	hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), 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.putSlotSmallFast64(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 key == *(*uint64)(slotKey) {
   260  					slotElem = g.elem(typ, i)
   261  
   262  					t.checkInvariants(typ, m)
   263  					break outer
   264  				}
   265  				match = match.removeFirst()
   266  			}
   267  
   268  			// No existing slot for this key in this group. Is this the end
   269  			// of the probe sequence?
   270  			match = g.ctrls().matchEmptyOrDeleted()
   271  			if match == 0 {
   272  				continue // nothing but filled slots. Keep probing.
   273  			}
   274  			i := match.first()
   275  			if g.ctrls().get(i) == ctrlDeleted {
   276  				// There are some deleted slots. Remember
   277  				// the first one, and keep probing.
   278  				if firstDeletedGroup.data == nil {
   279  					firstDeletedGroup = g
   280  					firstDeletedSlot = i
   281  				}
   282  				continue
   283  			}
   284  			// We've found an empty slot, which means we've reached the end of
   285  			// the probe sequence.
   286  
   287  			// If we found a deleted slot along the way, we can
   288  			// 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  			}
   294  
   295  			// If we have no space left, first try to remove some tombstones.
   296  			if t.growthLeft == 0 {
   297  				t.pruneTombstones(typ, m)
   298  			}
   299  
   300  			// If there is room left to grow, just insert the new entry.
   301  			if t.growthLeft > 0 {
   302  				slotKey := g.key(typ, i)
   303  				*(*uint64)(slotKey) = key
   304  
   305  				slotElem = g.elem(typ, i)
   306  
   307  				g.ctrls().set(i, ctrl(h2(hash)))
   308  				t.growthLeft--
   309  				t.used++
   310  				m.used++
   311  
   312  				t.checkInvariants(typ, m)
   313  				break outer
   314  			}
   315  
   316  			t.rehash(typ, m)
   317  			continue outer
   318  		}
   319  	}
   320  
   321  	if m.writing == 0 {
   322  		fatal("concurrent map writes")
   323  	}
   324  	m.writing ^= 1
   325  
   326  	return slotElem
   327  }
   328  
   329  func (m *Map) putSlotSmallFastPtr(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
   330  	g := groupReference{
   331  		data: m.dirPtr,
   332  	}
   333  
   334  	match := g.ctrls().matchH2(h2(hash))
   335  
   336  	// Look for an existing slot containing this key.
   337  	for match != 0 {
   338  		i := match.first()
   339  
   340  		slotKey := g.key(typ, i)
   341  		if key == *(*unsafe.Pointer)(slotKey) {
   342  			slotElem := g.elem(typ, i)
   343  			return slotElem
   344  		}
   345  		match = match.removeFirst()
   346  	}
   347  
   348  	// There can't be deleted slots, small maps can't have them
   349  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   350  	// more efficient than matchEmpty.
   351  	match = g.ctrls().matchEmptyOrDeleted()
   352  	if match == 0 {
   353  		fatal("small map with no empty slot (concurrent map writes?)")
   354  	}
   355  
   356  	i := match.first()
   357  
   358  	slotKey := g.key(typ, i)
   359  	*(*unsafe.Pointer)(slotKey) = key
   360  
   361  	slotElem := g.elem(typ, i)
   362  
   363  	g.ctrls().set(i, ctrl(h2(hash)))
   364  	m.used++
   365  
   366  	return slotElem
   367  }
   368  
   369  // Key is a 64-bit pointer (only called on 64-bit GOARCH).
   370  //
   371  //go:linkname runtime_mapassign_fast64ptr runtime.mapassign_fast64ptr
   372  func runtime_mapassign_fast64ptr(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
   373  	if m == nil {
   374  		panic(errNilAssign)
   375  	}
   376  	if race.Enabled {
   377  		callerpc := sys.GetCallerPC()
   378  		pc := abi.FuncPCABIInternal(runtime_mapassign_fast64ptr)
   379  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   380  	}
   381  	if m.writing != 0 {
   382  		fatal("concurrent map writes")
   383  	}
   384  
   385  	k := key
   386  	hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
   387  
   388  	// Set writing after calling Hasher, since Hasher may panic, in which
   389  	// case we have not actually done a write.
   390  	m.writing ^= 1 // toggle, see comment on writing
   391  
   392  	if m.dirPtr == nil {
   393  		m.growToSmall(typ)
   394  	}
   395  
   396  	if m.dirLen == 0 {
   397  		if m.used < abi.SwissMapGroupSlots {
   398  			elem := m.putSlotSmallFastPtr(typ, hash, key)
   399  
   400  			if m.writing == 0 {
   401  				fatal("concurrent map writes")
   402  			}
   403  			m.writing ^= 1
   404  
   405  			return elem
   406  		}
   407  
   408  		// Can't fit another entry, grow to full size map.
   409  		m.growToTable(typ)
   410  	}
   411  
   412  	var slotElem unsafe.Pointer
   413  outer:
   414  	for {
   415  		// Select table.
   416  		idx := m.directoryIndex(hash)
   417  		t := m.directoryAt(idx)
   418  
   419  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   420  
   421  		// As we look for a match, keep track of the first deleted slot
   422  		// we find, which we'll use to insert the new entry if
   423  		// necessary.
   424  		var firstDeletedGroup groupReference
   425  		var firstDeletedSlot uintptr
   426  
   427  		for ; ; seq = seq.next() {
   428  			g := t.groups.group(typ, seq.offset)
   429  			match := g.ctrls().matchH2(h2(hash))
   430  
   431  			// Look for an existing slot containing this key.
   432  			for match != 0 {
   433  				i := match.first()
   434  
   435  				slotKey := g.key(typ, i)
   436  				if key == *(*unsafe.Pointer)(slotKey) {
   437  					slotElem = g.elem(typ, i)
   438  
   439  					t.checkInvariants(typ, m)
   440  					break outer
   441  				}
   442  				match = match.removeFirst()
   443  			}
   444  
   445  			// No existing slot for this key in this group. Is this the end
   446  			// of the probe sequence?
   447  			match = g.ctrls().matchEmptyOrDeleted()
   448  			if match == 0 {
   449  				continue // nothing but filled slots. Keep probing.
   450  			}
   451  			i := match.first()
   452  			if g.ctrls().get(i) == ctrlDeleted {
   453  				// There are some deleted slots. Remember
   454  				// the first one, and keep probing.
   455  				if firstDeletedGroup.data == nil {
   456  					firstDeletedGroup = g
   457  					firstDeletedSlot = i
   458  				}
   459  				continue
   460  			}
   461  			// We've found an empty slot, which means we've reached the end of
   462  			// the probe sequence.
   463  
   464  			// If we found a deleted slot along the way, we can
   465  			// replace it without consuming growthLeft.
   466  			if firstDeletedGroup.data != nil {
   467  				g = firstDeletedGroup
   468  				i = firstDeletedSlot
   469  				t.growthLeft++ // will be decremented below to become a no-op.
   470  			}
   471  
   472  			// If there is room left to grow, just insert the new entry.
   473  			if t.growthLeft > 0 {
   474  				slotKey := g.key(typ, i)
   475  				*(*unsafe.Pointer)(slotKey) = key
   476  
   477  				slotElem = g.elem(typ, i)
   478  
   479  				g.ctrls().set(i, ctrl(h2(hash)))
   480  				t.growthLeft--
   481  				t.used++
   482  				m.used++
   483  
   484  				t.checkInvariants(typ, m)
   485  				break outer
   486  			}
   487  
   488  			t.rehash(typ, m)
   489  			continue outer
   490  		}
   491  	}
   492  
   493  	if m.writing == 0 {
   494  		fatal("concurrent map writes")
   495  	}
   496  	m.writing ^= 1
   497  
   498  	return slotElem
   499  }
   500  
   501  //go:linkname runtime_mapdelete_fast64 runtime.mapdelete_fast64
   502  func runtime_mapdelete_fast64(typ *abi.SwissMapType, m *Map, key uint64) {
   503  	if race.Enabled {
   504  		callerpc := sys.GetCallerPC()
   505  		pc := abi.FuncPCABIInternal(runtime_mapdelete_fast64)
   506  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   507  	}
   508  
   509  	if m == nil || m.Used() == 0 {
   510  		return
   511  	}
   512  
   513  	m.Delete(typ, abi.NoEscape(unsafe.Pointer(&key)))
   514  }
   515  

View as plain text