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