runtime_swiss.mx raw
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/asan"
12 "internal/msan"
13 "internal/race"
14 "internal/runtime/sys"
15 "unsafe"
16 )
17
18 // Functions below pushed from runtime.
19
20 // Pushed from runtime in order to use runtime.plainError
21 //
22 //go:linkname errNilAssign
23 var errNilAssign error
24
25 // Pull from runtime. It is important that is this the exact same copy as the
26 // runtime because runtime.mapaccess1_fat compares the returned pointer with
27 // &runtime.zeroVal[0].
28 // TODO: move zeroVal to internal/abi?
29 //
30 //go:linkname zeroVal runtime.zeroVal
31 var zeroVal [abi.ZeroValSize]byte
32
33 // mapaccess1 returns a pointer to h[key]. Never returns nil, instead
34 // it will return a reference to the zero object for the elem type if
35 // the key is not in the map.
36 // NOTE: The returned pointer may keep the whole map live, so don't
37 // hold onto it for very long.
38 //
39 //go:linkname runtime_mapaccess1 runtime.mapaccess1
40 func runtime_mapaccess1(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
41 if race.Enabled && m != nil {
42 callerpc := sys.GetCallerPC()
43 pc := abi.FuncPCABIInternal(runtime_mapaccess1)
44 race.ReadPC(unsafe.Pointer(m), callerpc, pc)
45 race.ReadObjectPC(typ.Key, key, callerpc, pc)
46 }
47 if msan.Enabled && m != nil {
48 msan.Read(key, typ.Key.Size_)
49 }
50 if asan.Enabled && m != nil {
51 asan.Read(key, typ.Key.Size_)
52 }
53
54 if m == nil || m.Used() == 0 {
55 if err := mapKeyError(typ, key); err != nil {
56 panic(err) // see issue 23734
57 }
58 return unsafe.Pointer(&zeroVal[0])
59 }
60
61 if m.writing != 0 {
62 fatal("concurrent map read and map write")
63 }
64
65 hash := typ.Hasher(key, m.seed)
66
67 if m.dirLen <= 0 {
68 _, elem, ok := m.getWithKeySmall(typ, hash, key)
69 if !ok {
70 return unsafe.Pointer(&zeroVal[0])
71 }
72 return elem
73 }
74
75 // Select table.
76 idx := m.directoryIndex(hash)
77 t := m.directoryAt(idx)
78
79 // Probe table.
80 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
81 for ; ; seq = seq.next() {
82 g := t.groups.group(typ, seq.offset)
83
84 match := g.ctrls().matchH2(h2(hash))
85
86 for match != 0 {
87 i := match.first()
88
89 slotKey := g.key(typ, i)
90 slotKeyOrig := slotKey
91 if typ.IndirectKey() {
92 slotKey = *((*unsafe.Pointer)(slotKey))
93 }
94 if typ.Key.Equal(key, slotKey) {
95 slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
96 if typ.IndirectElem() {
97 slotElem = *((*unsafe.Pointer)(slotElem))
98 }
99 return slotElem
100 }
101 match = match.removeFirst()
102 }
103
104 match = g.ctrls().matchEmpty()
105 if match != 0 {
106 // Finding an empty slot means we've reached the end of
107 // the probe sequence.
108 return unsafe.Pointer(&zeroVal[0])
109 }
110 }
111 }
112
113 //go:linkname runtime_mapaccess2 runtime.mapaccess2
114 func runtime_mapaccess2(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
115 if race.Enabled && m != nil {
116 callerpc := sys.GetCallerPC()
117 pc := abi.FuncPCABIInternal(runtime_mapaccess1)
118 race.ReadPC(unsafe.Pointer(m), callerpc, pc)
119 race.ReadObjectPC(typ.Key, key, callerpc, pc)
120 }
121 if msan.Enabled && m != nil {
122 msan.Read(key, typ.Key.Size_)
123 }
124 if asan.Enabled && m != nil {
125 asan.Read(key, typ.Key.Size_)
126 }
127
128 if m == nil || m.Used() == 0 {
129 if err := mapKeyError(typ, key); err != nil {
130 panic(err) // see issue 23734
131 }
132 return unsafe.Pointer(&zeroVal[0]), false
133 }
134
135 if m.writing != 0 {
136 fatal("concurrent map read and map write")
137 }
138
139 hash := typ.Hasher(key, m.seed)
140
141 if m.dirLen == 0 {
142 _, elem, ok := m.getWithKeySmall(typ, hash, key)
143 if !ok {
144 return unsafe.Pointer(&zeroVal[0]), false
145 }
146 return elem, true
147 }
148
149 // Select table.
150 idx := m.directoryIndex(hash)
151 t := m.directoryAt(idx)
152
153 // Probe table.
154 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
155 for ; ; seq = seq.next() {
156 g := t.groups.group(typ, seq.offset)
157
158 match := g.ctrls().matchH2(h2(hash))
159
160 for match != 0 {
161 i := match.first()
162
163 slotKey := g.key(typ, i)
164 slotKeyOrig := slotKey
165 if typ.IndirectKey() {
166 slotKey = *((*unsafe.Pointer)(slotKey))
167 }
168 if typ.Key.Equal(key, slotKey) {
169 slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
170 if typ.IndirectElem() {
171 slotElem = *((*unsafe.Pointer)(slotElem))
172 }
173 return slotElem, true
174 }
175 match = match.removeFirst()
176 }
177
178 match = g.ctrls().matchEmpty()
179 if match != 0 {
180 // Finding an empty slot means we've reached the end of
181 // the probe sequence.
182 return unsafe.Pointer(&zeroVal[0]), false
183 }
184 }
185 }
186
187 //go:linkname runtime_mapassign runtime.mapassign
188 func runtime_mapassign(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
189 if m == nil {
190 panic(errNilAssign)
191 }
192 if race.Enabled {
193 callerpc := sys.GetCallerPC()
194 pc := abi.FuncPCABIInternal(runtime_mapassign)
195 race.WritePC(unsafe.Pointer(m), callerpc, pc)
196 race.ReadObjectPC(typ.Key, key, callerpc, pc)
197 }
198 if msan.Enabled {
199 msan.Read(key, typ.Key.Size_)
200 }
201 if asan.Enabled {
202 asan.Read(key, typ.Key.Size_)
203 }
204 if m.writing != 0 {
205 fatal("concurrent map writes")
206 }
207
208 hash := typ.Hasher(key, m.seed)
209
210 // Set writing after calling Hasher, since Hasher may panic, in which
211 // case we have not actually done a write.
212 m.writing ^= 1 // toggle, see comment on writing
213
214 if m.dirPtr == nil {
215 m.growToSmall(typ)
216 }
217
218 if m.dirLen == 0 {
219 if m.used < abi.SwissMapGroupSlots {
220 elem := m.putSlotSmall(typ, hash, key)
221
222 if m.writing == 0 {
223 fatal("concurrent map writes")
224 }
225 m.writing ^= 1
226
227 return elem
228 }
229
230 // Can't fit another entry, grow to full size map.
231 m.growToTable(typ)
232 }
233
234 var slotElem unsafe.Pointer
235 outer:
236 for {
237 // Select table.
238 idx := m.directoryIndex(hash)
239 t := m.directoryAt(idx)
240
241 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
242
243 // As we look for a match, keep track of the first deleted slot
244 // we find, which we'll use to insert the new entry if
245 // necessary.
246 var firstDeletedGroup groupReference
247 var firstDeletedSlot uintptr
248
249 for ; ; seq = seq.next() {
250 g := t.groups.group(typ, seq.offset)
251 match := g.ctrls().matchH2(h2(hash))
252
253 // Look for an existing slot containing this key.
254 for match != 0 {
255 i := match.first()
256
257 slotKey := g.key(typ, i)
258 slotKeyOrig := slotKey
259 if typ.IndirectKey() {
260 slotKey = *((*unsafe.Pointer)(slotKey))
261 }
262 if typ.Key.Equal(key, slotKey) {
263 if typ.NeedKeyUpdate() {
264 typedmemmove(typ.Key, slotKey, key)
265 }
266
267 slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
268 if typ.IndirectElem() {
269 slotElem = *((*unsafe.Pointer)(slotElem))
270 }
271
272 t.checkInvariants(typ, m)
273 break outer
274 }
275 match = match.removeFirst()
276 }
277
278 // No existing slot for this key in this group. Is this the end
279 // of the probe sequence?
280 match = g.ctrls().matchEmpty()
281 if match != 0 {
282 // Finding an empty slot means we've reached the end of
283 // the probe sequence.
284
285 var i uintptr
286
287 // If we found a deleted slot along the way, we
288 // can 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 } else {
294 // Otherwise, use the empty slot.
295 i = match.first()
296 }
297
298 // If there is room left to grow, just insert the new entry.
299 if t.growthLeft > 0 {
300 slotKey := g.key(typ, i)
301 slotKeyOrig := slotKey
302 if typ.IndirectKey() {
303 kmem := newobject(typ.Key)
304 *(*unsafe.Pointer)(slotKey) = kmem
305 slotKey = kmem
306 }
307 typedmemmove(typ.Key, slotKey, key)
308
309 slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
310 if typ.IndirectElem() {
311 emem := newobject(typ.Elem)
312 *(*unsafe.Pointer)(slotElem) = emem
313 slotElem = emem
314 }
315
316 g.ctrls().set(i, ctrl(h2(hash)))
317 t.growthLeft--
318 t.used++
319 m.used++
320
321 t.checkInvariants(typ, m)
322 break outer
323 }
324
325 t.rehash(typ, m)
326 continue outer
327 }
328
329 // No empty slots in this group. Check for a deleted
330 // slot, which we'll use if we don't find a match later
331 // in the probe sequence.
332 //
333 // We only need to remember a single deleted slot.
334 if firstDeletedGroup.data == nil {
335 // Since we already checked for empty slots
336 // above, matches here must be deleted slots.
337 match = g.ctrls().matchEmptyOrDeleted()
338 if match != 0 {
339 firstDeletedGroup = g
340 firstDeletedSlot = match.first()
341 }
342 }
343 }
344 }
345
346 if m.writing == 0 {
347 fatal("concurrent map writes")
348 }
349 m.writing ^= 1
350
351 return slotElem
352 }
353