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