map_swiss.go

     1  // Copyright 2014 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 runtime
     8  
     9  import (
    10  	"internal/abi"
    11  	"internal/runtime/maps"
    12  	"internal/runtime/sys"
    13  	"unsafe"
    14  )
    15  
    16  const (
    17  	// TODO: remove? These are used by tests but not the actual map
    18  	loadFactorNum = 7
    19  	loadFactorDen = 8
    20  )
    21  
    22  type maptype = abi.SwissMapType
    23  
    24  //go:linkname maps_errNilAssign internal/runtime/maps.errNilAssign
    25  var maps_errNilAssign error = plainError("assignment to entry in nil map")
    26  
    27  //go:linkname maps_mapKeyError internal/runtime/maps.mapKeyError
    28  func maps_mapKeyError(t *abi.SwissMapType, p unsafe.Pointer) error {
    29  	return mapKeyError(t, p)
    30  }
    31  
    32  func makemap64(t *abi.SwissMapType, hint int64, m *maps.Map) *maps.Map {
    33  	if int64(int(hint)) != hint {
    34  		hint = 0
    35  	}
    36  	return makemap(t, int(hint), m)
    37  }
    38  
    39  // makemap_small implements Go map creation for make(map[k]v) and
    40  // make(map[k]v, hint) when hint is known to be at most abi.SwissMapGroupSlots
    41  // at compile time and the map needs to be allocated on the heap.
    42  func makemap_small() *maps.Map {
    43  	return maps.NewEmptyMap()
    44  }
    45  
    46  // makemap implements Go map creation for make(map[k]v, hint).
    47  // If the compiler has determined that the map or the first group
    48  // can be created on the stack, m and optionally m.dirPtr may be non-nil.
    49  // If m != nil, the map can be created directly in m.
    50  // If m.dirPtr != nil, it points to a group usable for a small map.
    51  func makemap(t *abi.SwissMapType, hint int, m *maps.Map) *maps.Map {
    52  	if hint < 0 {
    53  		hint = 0
    54  	}
    55  
    56  	return maps.NewMap(t, uintptr(hint), m, maxAlloc)
    57  }
    58  
    59  // mapaccess1 returns a pointer to h[key].  Never returns nil, instead
    60  // it will return a reference to the zero object for the elem type if
    61  // the key is not in the map.
    62  // NOTE: The returned pointer may keep the whole map live, so don't
    63  // hold onto it for very long.
    64  //
    65  // mapaccess1 is pushed from internal/runtime/maps. We could just call it, but
    66  // we want to avoid one layer of call.
    67  //
    68  //go:linkname mapaccess1
    69  func mapaccess1(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer
    70  
    71  func mapaccess2(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) (unsafe.Pointer, bool)
    72  
    73  func mapaccess1_fat(t *abi.SwissMapType, m *maps.Map, key, zero unsafe.Pointer) unsafe.Pointer {
    74  	e := mapaccess1(t, m, key)
    75  	if e == unsafe.Pointer(&zeroVal[0]) {
    76  		return zero
    77  	}
    78  	return e
    79  }
    80  
    81  func mapaccess2_fat(t *abi.SwissMapType, m *maps.Map, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
    82  	e := mapaccess1(t, m, key)
    83  	if e == unsafe.Pointer(&zeroVal[0]) {
    84  		return zero, false
    85  	}
    86  	return e, true
    87  }
    88  
    89  // mapassign is pushed from internal/runtime/maps. We could just call it, but
    90  // we want to avoid one layer of call.
    91  //
    92  //go:linkname mapassign
    93  func mapassign(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer
    94  
    95  func mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) {
    96  	if raceenabled && m != nil {
    97  		callerpc := sys.GetCallerPC()
    98  		pc := abi.FuncPCABIInternal(mapdelete)
    99  		racewritepc(unsafe.Pointer(m), callerpc, pc)
   100  		raceReadObjectPC(t.Key, key, callerpc, pc)
   101  	}
   102  	if msanenabled && m != nil {
   103  		msanread(key, t.Key.Size_)
   104  	}
   105  	if asanenabled && m != nil {
   106  		asanread(key, t.Key.Size_)
   107  	}
   108  
   109  	m.Delete(t, key)
   110  }
   111  
   112  // mapiterinit initializes the Iter struct used for ranging over maps.
   113  // The Iter struct pointed to by 'it' is allocated on the stack
   114  // by the compilers order pass or on the heap by reflect_mapiterinit.
   115  // Both need to have zeroed hiter since the struct contains pointers.
   116  func mapiterinit(t *abi.SwissMapType, m *maps.Map, it *maps.Iter) {
   117  	if raceenabled && m != nil {
   118  		callerpc := sys.GetCallerPC()
   119  		racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(mapiterinit))
   120  	}
   121  
   122  	it.Init(t, m)
   123  	it.Next()
   124  }
   125  
   126  func mapiternext(it *maps.Iter) {
   127  	if raceenabled {
   128  		callerpc := sys.GetCallerPC()
   129  		racereadpc(unsafe.Pointer(it.Map()), callerpc, abi.FuncPCABIInternal(mapiternext))
   130  	}
   131  
   132  	it.Next()
   133  }
   134  
   135  // mapclear deletes all keys from a map.
   136  func mapclear(t *abi.SwissMapType, m *maps.Map) {
   137  	if raceenabled && m != nil {
   138  		callerpc := sys.GetCallerPC()
   139  		pc := abi.FuncPCABIInternal(mapclear)
   140  		racewritepc(unsafe.Pointer(m), callerpc, pc)
   141  	}
   142  
   143  	m.Clear(t)
   144  }
   145  
   146  // Reflect stubs. Called from ../reflect/asm_*.s
   147  
   148  //go:linkname reflect_makemap reflect.makemap
   149  func reflect_makemap(t *abi.SwissMapType, cap int) *maps.Map {
   150  	// Check invariants and reflects math.
   151  	if t.Key.Equal == nil {
   152  		throw("runtime.reflect_makemap: unsupported map key type")
   153  	}
   154  	// TODO: other checks
   155  
   156  	return makemap(t, cap, nil)
   157  }
   158  
   159  //go:linkname reflect_mapaccess reflect.mapaccess
   160  func reflect_mapaccess(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer {
   161  	elem, ok := mapaccess2(t, m, key)
   162  	if !ok {
   163  		// reflect wants nil for a missing element
   164  		elem = nil
   165  	}
   166  	return elem
   167  }
   168  
   169  //go:linkname reflect_mapaccess_faststr reflect.mapaccess_faststr
   170  func reflect_mapaccess_faststr(t *abi.SwissMapType, m *maps.Map, key string) unsafe.Pointer {
   171  	elem, ok := mapaccess2_faststr(t, m, key)
   172  	if !ok {
   173  		// reflect wants nil for a missing element
   174  		elem = nil
   175  	}
   176  	return elem
   177  }
   178  
   179  //go:linkname reflect_mapassign reflect.mapassign0
   180  func reflect_mapassign(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer, elem unsafe.Pointer) {
   181  	p := mapassign(t, m, key)
   182  	typedmemmove(t.Elem, p, elem)
   183  }
   184  
   185  //go:linkname reflect_mapassign_faststr reflect.mapassign_faststr0
   186  func reflect_mapassign_faststr(t *abi.SwissMapType, m *maps.Map, key string, elem unsafe.Pointer) {
   187  	p := mapassign_faststr(t, m, key)
   188  	typedmemmove(t.Elem, p, elem)
   189  }
   190  
   191  //go:linkname reflect_mapdelete reflect.mapdelete
   192  func reflect_mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) {
   193  	mapdelete(t, m, key)
   194  }
   195  
   196  //go:linkname reflect_mapdelete_faststr reflect.mapdelete_faststr
   197  func reflect_mapdelete_faststr(t *abi.SwissMapType, m *maps.Map, key string) {
   198  	mapdelete_faststr(t, m, key)
   199  }
   200  
   201  //go:linkname reflect_mapiterinit reflect.mapiterinit
   202  func reflect_mapiterinit(t *abi.SwissMapType, m *maps.Map, it *maps.Iter) {
   203  	mapiterinit(t, m, it)
   204  }
   205  
   206  //go:linkname reflect_mapiternext reflect.mapiternext
   207  func reflect_mapiternext(it *maps.Iter) {
   208  	mapiternext(it)
   209  }
   210  
   211  //go:linkname reflect_mapiterkey reflect.mapiterkey
   212  func reflect_mapiterkey(it *maps.Iter) unsafe.Pointer {
   213  	return it.Key()
   214  }
   215  
   216  //go:linkname reflect_mapiterelem reflect.mapiterelem
   217  func reflect_mapiterelem(it *maps.Iter) unsafe.Pointer {
   218  	return it.Elem()
   219  }
   220  
   221  //go:linkname reflect_maplen reflect.maplen
   222  func reflect_maplen(m *maps.Map) int {
   223  	if m == nil {
   224  		return 0
   225  	}
   226  	if raceenabled {
   227  		callerpc := sys.GetCallerPC()
   228  		racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(reflect_maplen))
   229  	}
   230  	return int(m.Used())
   231  }
   232  
   233  //go:linkname reflect_mapclear reflect.mapclear
   234  func reflect_mapclear(t *abi.SwissMapType, m *maps.Map) {
   235  	mapclear(t, m)
   236  }
   237  
   238  //go:linkname reflectlite_maplen internal/reflectlite.maplen
   239  func reflectlite_maplen(m *maps.Map) int {
   240  	if m == nil {
   241  		return 0
   242  	}
   243  	if raceenabled {
   244  		callerpc := sys.GetCallerPC()
   245  		racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(reflect_maplen))
   246  	}
   247  	return int(m.Used())
   248  }
   249  
   250  // mapinitnoop is a no-op function known the Go linker; if a given global
   251  // map (of the right size) is determined to be dead, the linker will
   252  // rewrite the relocation (from the package init func) from the outlined
   253  // map init function to this symbol. Defined in assembly so as to avoid
   254  // complications with instrumentation (coverage, etc).
   255  func mapinitnoop()
   256  
   257  // mapclone for implementing maps.Clone
   258  //
   259  //go:linkname mapclone maps.clone
   260  func mapclone(m any) any {
   261  	e := efaceOf(&m)
   262  	e.data = unsafe.Pointer(mapclone2((*abi.SwissMapType)(unsafe.Pointer(e._type)), (*maps.Map)(e.data)))
   263  	return m
   264  }
   265  
   266  func mapclone2(t *abi.SwissMapType, src *maps.Map) *maps.Map {
   267  	dst := makemap(t, int(src.Used()), nil)
   268  
   269  	var iter maps.Iter
   270  	iter.Init(t, src)
   271  	for iter.Next(); iter.Key() != nil; iter.Next() {
   272  		dst.Put(t, iter.Key(), iter.Elem())
   273  	}
   274  
   275  	return dst
   276  }
   277  
   278  // keys for implementing maps.keys
   279  //
   280  //go:linkname keys maps.keys
   281  func keys(m any, p unsafe.Pointer) {
   282  	// Currently unused in the maps package.
   283  	panic("unimplemented")
   284  }
   285  
   286  // values for implementing maps.values
   287  //
   288  //go:linkname values maps.values
   289  func values(m any, p unsafe.Pointer) {
   290  	// Currently unused in the maps package.
   291  	panic("unimplemented")
   292  }
   293
View as plain text