1// Copyright 2018 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
5package runtime
6
7import (
8	"runtime/internal/sys"
9	"unsafe"
10)
11
12func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {
13	if raceenabled && h != nil {
14		callerpc := getcallerpc()
15		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast32))
16	}
17	if h == nil || h.count == 0 {
18		return unsafe.Pointer(&zeroVal[0])
19	}
20	if h.flags&hashWriting != 0 {
21		throw("concurrent map read and map write")
22	}
23	var b *bmap
24	if h.B == 0 {
25		// One-bucket table. No need to hash.
26		b = (*bmap)(h.buckets)
27	} else {
28		hash := t.key.hashfn(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
29		m := bucketMask(h.B)
30		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
31		if c := h.oldbuckets; c != nil {
32			if !h.sameSizeGrow() {
33				// There used to be half as many buckets; mask down one more power of two.
34				m >>= 1
35			}
36			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
37			if !evacuated(oldb) {
38				b = oldb
39			}
40		}
41	}
42	for ; b != nil; b = b.overflow(t) {
43		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
44			if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) {
45				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize))
46			}
47		}
48	}
49	return unsafe.Pointer(&zeroVal[0])
50}
51
52func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) {
53	if raceenabled && h != nil {
54		callerpc := getcallerpc()
55		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast32))
56	}
57	if h == nil || h.count == 0 {
58		return unsafe.Pointer(&zeroVal[0]), false
59	}
60	if h.flags&hashWriting != 0 {
61		throw("concurrent map read and map write")
62	}
63	var b *bmap
64	if h.B == 0 {
65		// One-bucket table. No need to hash.
66		b = (*bmap)(h.buckets)
67	} else {
68		hash := t.key.hashfn(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
69		m := bucketMask(h.B)
70		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
71		if c := h.oldbuckets; c != nil {
72			if !h.sameSizeGrow() {
73				// There used to be half as many buckets; mask down one more power of two.
74				m >>= 1
75			}
76			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
77			if !evacuated(oldb) {
78				b = oldb
79			}
80		}
81	}
82	for ; b != nil; b = b.overflow(t) {
83		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
84			if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) {
85				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true
86			}
87		}
88	}
89	return unsafe.Pointer(&zeroVal[0]), false
90}
91
92func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {
93	if h == nil {
94		panic(plainError("assignment to entry in nil map"))
95	}
96	if raceenabled {
97		callerpc := getcallerpc()
98		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32))
99	}
100	if h.flags&hashWriting != 0 {
101		throw("concurrent map writes")
102	}
103	hash := t.key.hashfn(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
104
105	// Set hashWriting after calling alg.hash for consistency with mapassign.
106	h.flags ^= hashWriting
107
108	if h.buckets == nil {
109		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
110	}
111
112again:
113	bucket := hash & bucketMask(h.B)
114	if h.growing() {
115		growWork_fast32(t, h, bucket)
116	}
117	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
118
119	var insertb *bmap
120	var inserti uintptr
121	var insertk unsafe.Pointer
122
123bucketloop:
124	for {
125		for i := uintptr(0); i < bucketCnt; i++ {
126			if isEmpty(b.tophash[i]) {
127				if insertb == nil {
128					inserti = i
129					insertb = b
130				}
131				if b.tophash[i] == emptyRest {
132					break bucketloop
133				}
134				continue
135			}
136			k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4)))
137			if k != key {
138				continue
139			}
140			inserti = i
141			insertb = b
142			goto done
143		}
144		ovf := b.overflow(t)
145		if ovf == nil {
146			break
147		}
148		b = ovf
149	}
150
151	// Did not find mapping for key. Allocate new cell & add entry.
152
153	// If we hit the max load factor or we have too many overflow buckets,
154	// and we're not already in the middle of growing, start growing.
155	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
156		hashGrow(t, h)
157		goto again // Growing the table invalidates everything, so try again
158	}
159
160	if insertb == nil {
161		// all current buckets are full, allocate a new one.
162		insertb = h.newoverflow(t, b)
163		inserti = 0 // not necessary, but avoids needlessly spilling inserti
164	}
165	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
166
167	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4)
168	// store new key at insert position
169	*(*uint32)(insertk) = key
170
171	h.count++
172
173done:
174	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize))
175	if h.flags&hashWriting == 0 {
176		throw("concurrent map writes")
177	}
178	h.flags &^= hashWriting
179	return val
180}
181
182func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
183	if h == nil {
184		panic(plainError("assignment to entry in nil map"))
185	}
186	if raceenabled {
187		callerpc := getcallerpc()
188		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32))
189	}
190	if h.flags&hashWriting != 0 {
191		throw("concurrent map writes")
192	}
193	hash := t.key.hashfn(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
194
195	// Set hashWriting after calling alg.hash for consistency with mapassign.
196	h.flags ^= hashWriting
197
198	if h.buckets == nil {
199		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
200	}
201
202again:
203	bucket := hash & bucketMask(h.B)
204	if h.growing() {
205		growWork_fast32(t, h, bucket)
206	}
207	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
208
209	var insertb *bmap
210	var inserti uintptr
211	var insertk unsafe.Pointer
212
213bucketloop:
214	for {
215		for i := uintptr(0); i < bucketCnt; i++ {
216			if isEmpty(b.tophash[i]) {
217				if insertb == nil {
218					inserti = i
219					insertb = b
220				}
221				if b.tophash[i] == emptyRest {
222					break bucketloop
223				}
224				continue
225			}
226			k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4)))
227			if k != key {
228				continue
229			}
230			inserti = i
231			insertb = b
232			goto done
233		}
234		ovf := b.overflow(t)
235		if ovf == nil {
236			break
237		}
238		b = ovf
239	}
240
241	// Did not find mapping for key. Allocate new cell & add entry.
242
243	// If we hit the max load factor or we have too many overflow buckets,
244	// and we're not already in the middle of growing, start growing.
245	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
246		hashGrow(t, h)
247		goto again // Growing the table invalidates everything, so try again
248	}
249
250	if insertb == nil {
251		// all current buckets are full, allocate a new one.
252		insertb = h.newoverflow(t, b)
253		inserti = 0 // not necessary, but avoids needlessly spilling inserti
254	}
255	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
256
257	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4)
258	// store new key at insert position
259	*(*unsafe.Pointer)(insertk) = key
260
261	h.count++
262
263done:
264	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize))
265	if h.flags&hashWriting == 0 {
266		throw("concurrent map writes")
267	}
268	h.flags &^= hashWriting
269	return val
270}
271
272func mapdelete_fast32(t *maptype, h *hmap, key uint32) {
273	if raceenabled && h != nil {
274		callerpc := getcallerpc()
275		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast32))
276	}
277	if h == nil || h.count == 0 {
278		return
279	}
280	if h.flags&hashWriting != 0 {
281		throw("concurrent map writes")
282	}
283
284	hash := t.key.hashfn(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
285
286	// Set hashWriting after calling alg.hash for consistency with mapdelete
287	h.flags ^= hashWriting
288
289	bucket := hash & bucketMask(h.B)
290	if h.growing() {
291		growWork_fast32(t, h, bucket)
292	}
293	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
294	bOrig := b
295search:
296	for ; b != nil; b = b.overflow(t) {
297		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
298			if key != *(*uint32)(k) || isEmpty(b.tophash[i]) {
299				continue
300			}
301			// Only clear key if there are pointers in it.
302			if t.key.kind&kindNoPointers == 0 {
303				memclrHasPointers(k, t.key.size)
304			}
305			v := add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize))
306			if t.elem.kind&kindNoPointers == 0 {
307				memclrHasPointers(v, t.elem.size)
308			} else {
309				memclrNoHeapPointers(v, t.elem.size)
310			}
311			b.tophash[i] = emptyOne
312			// If the bucket now ends in a bunch of emptyOne states,
313			// change those to emptyRest states.
314			if i == bucketCnt-1 {
315				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
316					goto notLast
317				}
318			} else {
319				if b.tophash[i+1] != emptyRest {
320					goto notLast
321				}
322			}
323			for {
324				b.tophash[i] = emptyRest
325				if i == 0 {
326					if b == bOrig {
327						break // beginning of initial bucket, we're done.
328					}
329					// Find previous bucket, continue at its last entry.
330					c := b
331					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
332					}
333					i = bucketCnt - 1
334				} else {
335					i--
336				}
337				if b.tophash[i] != emptyOne {
338					break
339				}
340			}
341		notLast:
342			h.count--
343			break search
344		}
345	}
346
347	if h.flags&hashWriting == 0 {
348		throw("concurrent map writes")
349	}
350	h.flags &^= hashWriting
351}
352
353func growWork_fast32(t *maptype, h *hmap, bucket uintptr) {
354	// make sure we evacuate the oldbucket corresponding
355	// to the bucket we're about to use
356	evacuate_fast32(t, h, bucket&h.oldbucketmask())
357
358	// evacuate one more oldbucket to make progress on growing
359	if h.growing() {
360		evacuate_fast32(t, h, h.nevacuate)
361	}
362}
363
364func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) {
365	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
366	newbit := h.noldbuckets()
367	if !evacuated(b) {
368		// TODO: reuse overflow buckets instead of using new ones, if there
369		// is no iterator using the old buckets.  (If !oldIterator.)
370
371		// xy contains the x and y (low and high) evacuation destinations.
372		var xy [2]evacDst
373		x := &xy[0]
374		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
375		x.k = add(unsafe.Pointer(x.b), dataOffset)
376		x.v = add(x.k, bucketCnt*4)
377
378		if !h.sameSizeGrow() {
379			// Only calculate y pointers if we're growing bigger.
380			// Otherwise GC can see bad pointers.
381			y := &xy[1]
382			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
383			y.k = add(unsafe.Pointer(y.b), dataOffset)
384			y.v = add(y.k, bucketCnt*4)
385		}
386
387		for ; b != nil; b = b.overflow(t) {
388			k := add(unsafe.Pointer(b), dataOffset)
389			v := add(k, bucketCnt*4)
390			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 4), add(v, uintptr(t.valuesize)) {
391				top := b.tophash[i]
392				if isEmpty(top) {
393					b.tophash[i] = evacuatedEmpty
394					continue
395				}
396				if top < minTopHash {
397					throw("bad map state")
398				}
399				var useY uint8
400				if !h.sameSizeGrow() {
401					// Compute hash to make our evacuation decision (whether we need
402					// to send this key/value to bucket x or bucket y).
403					hash := t.key.hashfn(k, uintptr(h.hash0))
404					if hash&newbit != 0 {
405						useY = 1
406					}
407				}
408
409				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
410				dst := &xy[useY]                 // evacuation destination
411
412				if dst.i == bucketCnt {
413					dst.b = h.newoverflow(t, dst.b)
414					dst.i = 0
415					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
416					dst.v = add(dst.k, bucketCnt*4)
417				}
418				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
419
420				// Copy key.
421				if sys.PtrSize == 4 && t.key.kind&kindNoPointers == 0 && writeBarrier.enabled {
422					// Write with a write barrier.
423					*(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k)
424				} else {
425					*(*uint32)(dst.k) = *(*uint32)(k)
426				}
427
428				typedmemmove(t.elem, dst.v, v)
429				dst.i++
430				// These updates might push these pointers past the end of the
431				// key or value arrays.  That's ok, as we have the overflow pointer
432				// at the end of the bucket to protect against pointing past the
433				// end of the bucket.
434				dst.k = add(dst.k, 4)
435				dst.v = add(dst.v, uintptr(t.valuesize))
436			}
437		}
438		// Unlink the overflow buckets & clear key/value to help GC.
439		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
440			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
441			// Preserve b.tophash because the evacuation
442			// state is maintained there.
443			ptr := add(b, dataOffset)
444			n := uintptr(t.bucketsize) - dataOffset
445			memclrHasPointers(ptr, n)
446		}
447	}
448
449	if oldbucket == h.nevacuate {
450		advanceEvacuationMark(h, t, newbit)
451	}
452}
453