Source file src/runtime/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 func makemap64(t *abi.SwissMapType, hint int64, m *maps.Map) *maps.Map { 28 if int64(int(hint)) != hint { 29 hint = 0 30 } 31 return makemap(t, int(hint), m) 32 } 33 34 // makemap_small implements Go map creation for make(map[k]v) and 35 // make(map[k]v, hint) when hint is known to be at most abi.SwissMapGroupSlots 36 // at compile time and the map needs to be allocated on the heap. 37 // 38 // makemap_small should be an internal detail, 39 // but widely used packages access it using linkname. 40 // Notable members of the hall of shame include: 41 // - github.com/bytedance/sonic 42 // 43 // Do not remove or change the type signature. 44 // See go.dev/issue/67401. 45 // 46 //go:linkname makemap_small 47 func makemap_small() *maps.Map { 48 return maps.NewEmptyMap() 49 } 50 51 // makemap implements Go map creation for make(map[k]v, hint). 52 // If the compiler has determined that the map or the first group 53 // can be created on the stack, m and optionally m.dirPtr may be non-nil. 54 // If m != nil, the map can be created directly in m. 55 // If m.dirPtr != nil, it points to a group usable for a small map. 56 // 57 // makemap should be an internal detail, 58 // but widely used packages access it using linkname. 59 // Notable members of the hall of shame include: 60 // - github.com/ugorji/go/codec 61 // 62 // Do not remove or change the type signature. 63 // See go.dev/issue/67401. 64 // 65 //go:linkname makemap 66 func makemap(t *abi.SwissMapType, hint int, m *maps.Map) *maps.Map { 67 if hint < 0 { 68 hint = 0 69 } 70 71 return maps.NewMap(t, uintptr(hint), m, maxAlloc) 72 } 73 74 // mapaccess1 returns a pointer to h[key]. Never returns nil, instead 75 // it will return a reference to the zero object for the elem type if 76 // the key is not in the map. 77 // NOTE: The returned pointer may keep the whole map live, so don't 78 // hold onto it for very long. 79 // 80 // mapaccess1 is pushed from internal/runtime/maps. We could just call it, but 81 // we want to avoid one layer of call. 82 // 83 //go:linkname mapaccess1 84 func mapaccess1(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer 85 86 // mapaccess2 should be an internal detail, 87 // but widely used packages access it using linkname. 88 // Notable members of the hall of shame include: 89 // - github.com/ugorji/go/codec 90 // 91 // Do not remove or change the type signature. 92 // See go.dev/issue/67401. 93 // 94 //go:linkname mapaccess2 95 func mapaccess2(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) (unsafe.Pointer, bool) 96 97 func mapaccess1_fat(t *abi.SwissMapType, m *maps.Map, key, zero unsafe.Pointer) unsafe.Pointer { 98 e := mapaccess1(t, m, key) 99 if e == unsafe.Pointer(&zeroVal[0]) { 100 return zero 101 } 102 return e 103 } 104 105 func mapaccess2_fat(t *abi.SwissMapType, m *maps.Map, key, zero unsafe.Pointer) (unsafe.Pointer, bool) { 106 e := mapaccess1(t, m, key) 107 if e == unsafe.Pointer(&zeroVal[0]) { 108 return zero, false 109 } 110 return e, true 111 } 112 113 // mapassign is pushed from internal/runtime/maps. We could just call it, but 114 // we want to avoid one layer of call. 115 // 116 // mapassign should be an internal detail, 117 // but widely used packages access it using linkname. 118 // Notable members of the hall of shame include: 119 // - github.com/bytedance/sonic 120 // - github.com/RomiChan/protobuf 121 // - github.com/segmentio/encoding 122 // - github.com/ugorji/go/codec 123 // 124 // Do not remove or change the type signature. 125 // See go.dev/issue/67401. 126 // 127 //go:linkname mapassign 128 func mapassign(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer 129 130 // mapdelete should be an internal detail, 131 // but widely used packages access it using linkname. 132 // Notable members of the hall of shame include: 133 // - github.com/ugorji/go/codec 134 // 135 // Do not remove or change the type signature. 136 // See go.dev/issue/67401. 137 // 138 //go:linkname mapdelete 139 func mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) { 140 if raceenabled && m != nil { 141 callerpc := sys.GetCallerPC() 142 pc := abi.FuncPCABIInternal(mapdelete) 143 racewritepc(unsafe.Pointer(m), callerpc, pc) 144 raceReadObjectPC(t.Key, key, callerpc, pc) 145 } 146 if msanenabled && m != nil { 147 msanread(key, t.Key.Size_) 148 } 149 if asanenabled && m != nil { 150 asanread(key, t.Key.Size_) 151 } 152 153 m.Delete(t, key) 154 } 155 156 // mapIterStart initializes the Iter struct used for ranging over maps and 157 // performs the first step of iteration. The Iter struct pointed to by 'it' is 158 // allocated on the stack by the compilers order pass or on the heap by 159 // reflect. Both need to have zeroed it since the struct contains pointers. 160 func mapIterStart(t *abi.SwissMapType, m *maps.Map, it *maps.Iter) { 161 if raceenabled && m != nil { 162 callerpc := sys.GetCallerPC() 163 racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(mapIterStart)) 164 } 165 166 it.Init(t, m) 167 it.Next() 168 } 169 170 // mapIterNext performs the next step of iteration. Afterwards, the next 171 // key/elem are in it.Key()/it.Elem(). 172 func mapIterNext(it *maps.Iter) { 173 if raceenabled { 174 callerpc := sys.GetCallerPC() 175 racereadpc(unsafe.Pointer(it.Map()), callerpc, abi.FuncPCABIInternal(mapIterNext)) 176 } 177 178 it.Next() 179 } 180 181 // mapclear deletes all keys from a map. 182 func mapclear(t *abi.SwissMapType, m *maps.Map) { 183 if raceenabled && m != nil { 184 callerpc := sys.GetCallerPC() 185 pc := abi.FuncPCABIInternal(mapclear) 186 racewritepc(unsafe.Pointer(m), callerpc, pc) 187 } 188 189 m.Clear(t) 190 } 191 192 // Reflect stubs. Called from ../reflect/asm_*.s 193 194 // reflect_makemap is for package reflect, 195 // but widely used packages access it using linkname. 196 // Notable members of the hall of shame include: 197 // - gitee.com/quant1x/gox 198 // - github.com/modern-go/reflect2 199 // - github.com/goccy/go-json 200 // - github.com/RomiChan/protobuf 201 // - github.com/segmentio/encoding 202 // - github.com/v2pro/plz 203 // 204 // Do not remove or change the type signature. 205 // See go.dev/issue/67401. 206 // 207 //go:linkname reflect_makemap reflect.makemap 208 func reflect_makemap(t *abi.SwissMapType, cap int) *maps.Map { 209 // Check invariants and reflects math. 210 if t.Key.Equal == nil { 211 throw("runtime.reflect_makemap: unsupported map key type") 212 } 213 // TODO: other checks 214 215 return makemap(t, cap, nil) 216 } 217 218 // reflect_mapaccess is for package reflect, 219 // but widely used packages access it using linkname. 220 // Notable members of the hall of shame include: 221 // - gitee.com/quant1x/gox 222 // - github.com/modern-go/reflect2 223 // - github.com/v2pro/plz 224 // 225 // Do not remove or change the type signature. 226 // See go.dev/issue/67401. 227 // 228 //go:linkname reflect_mapaccess reflect.mapaccess 229 func reflect_mapaccess(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) unsafe.Pointer { 230 elem, ok := mapaccess2(t, m, key) 231 if !ok { 232 // reflect wants nil for a missing element 233 elem = nil 234 } 235 return elem 236 } 237 238 //go:linkname reflect_mapaccess_faststr reflect.mapaccess_faststr 239 func reflect_mapaccess_faststr(t *abi.SwissMapType, m *maps.Map, key string) unsafe.Pointer { 240 elem, ok := mapaccess2_faststr(t, m, key) 241 if !ok { 242 // reflect wants nil for a missing element 243 elem = nil 244 } 245 return elem 246 } 247 248 // reflect_mapassign is for package reflect, 249 // but widely used packages access it using linkname. 250 // Notable members of the hall of shame include: 251 // - gitee.com/quant1x/gox 252 // - github.com/v2pro/plz 253 // 254 // Do not remove or change the type signature. 255 // 256 //go:linkname reflect_mapassign reflect.mapassign0 257 func reflect_mapassign(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer, elem unsafe.Pointer) { 258 p := mapassign(t, m, key) 259 typedmemmove(t.Elem, p, elem) 260 } 261 262 //go:linkname reflect_mapassign_faststr reflect.mapassign_faststr0 263 func reflect_mapassign_faststr(t *abi.SwissMapType, m *maps.Map, key string, elem unsafe.Pointer) { 264 p := mapassign_faststr(t, m, key) 265 typedmemmove(t.Elem, p, elem) 266 } 267 268 //go:linkname reflect_mapdelete reflect.mapdelete 269 func reflect_mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) { 270 mapdelete(t, m, key) 271 } 272 273 //go:linkname reflect_mapdelete_faststr reflect.mapdelete_faststr 274 func reflect_mapdelete_faststr(t *abi.SwissMapType, m *maps.Map, key string) { 275 mapdelete_faststr(t, m, key) 276 } 277 278 // reflect_maplen is for package reflect, 279 // but widely used packages access it using linkname. 280 // Notable members of the hall of shame include: 281 // - github.com/goccy/go-json 282 // - github.com/wI2L/jettison 283 // 284 // Do not remove or change the type signature. 285 // See go.dev/issue/67401. 286 // 287 //go:linkname reflect_maplen reflect.maplen 288 func reflect_maplen(m *maps.Map) int { 289 if m == nil { 290 return 0 291 } 292 if raceenabled { 293 callerpc := sys.GetCallerPC() 294 racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(reflect_maplen)) 295 } 296 return int(m.Used()) 297 } 298 299 //go:linkname reflect_mapclear reflect.mapclear 300 func reflect_mapclear(t *abi.SwissMapType, m *maps.Map) { 301 mapclear(t, m) 302 } 303 304 //go:linkname reflectlite_maplen internal/reflectlite.maplen 305 func reflectlite_maplen(m *maps.Map) int { 306 if m == nil { 307 return 0 308 } 309 if raceenabled { 310 callerpc := sys.GetCallerPC() 311 racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(reflect_maplen)) 312 } 313 return int(m.Used()) 314 } 315 316 // mapinitnoop is a no-op function known the Go linker; if a given global 317 // map (of the right size) is determined to be dead, the linker will 318 // rewrite the relocation (from the package init func) from the outlined 319 // map init function to this symbol. Defined in assembly so as to avoid 320 // complications with instrumentation (coverage, etc). 321 func mapinitnoop() 322 323 // mapclone for implementing maps.Clone 324 // 325 //go:linkname mapclone maps.clone 326 func mapclone(m any) any { 327 e := efaceOf(&m) 328 typ := (*abi.SwissMapType)(unsafe.Pointer(e._type)) 329 map_ := (*maps.Map)(e.data) 330 map_ = map_.Clone(typ) 331 e.data = (unsafe.Pointer)(map_) 332 return m 333 } 334 335 // keys for implementing maps.keys 336 // 337 //go:linkname keys maps.keys 338 func keys(m any, p unsafe.Pointer) { 339 // Currently unused in the maps package. 340 panic("unimplemented") 341 } 342 343 // values for implementing maps.values 344 // 345 //go:linkname values maps.values 346 func values(m any, p unsafe.Pointer) { 347 // Currently unused in the maps package. 348 panic("unimplemented") 349 } 350