From 4f4a855d82a889cebcfca150a7a43909bcb6a346 Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Fri, 18 Jan 2019 19:04:36 +0000 Subject: libgo: update to Go1.12beta2 Reviewed-on: https://go-review.googlesource.com/c/158019 gotools/: * Makefile.am (go_cmd_vet_files): Update for Go1.12beta2 release. (GOTOOLS_TEST_TIMEOUT): Increase to 600. (check-runtime): Export LD_LIBRARY_PATH before computing GOARCH and GOOS. (check-vet): Copy golang.org/x/tools into check-vet-dir. * Makefile.in: Regenerate. gcc/testsuite/: * go.go-torture/execute/names-1.go: Stop using debug/xcoff, which is no longer externally visible. From-SVN: r268084 --- libgo/go/runtime/map.go | 96 +++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 82 insertions(+), 14 deletions(-) (limited to 'libgo/go/runtime/map.go') diff --git a/libgo/go/runtime/map.go b/libgo/go/runtime/map.go index 52462c7e117..5dd5283e1ec 100644 --- a/libgo/go/runtime/map.go +++ b/libgo/go/runtime/map.go @@ -55,6 +55,7 @@ package runtime import ( "runtime/internal/atomic" + "runtime/internal/math" "runtime/internal/sys" "unsafe" ) @@ -103,11 +104,12 @@ const ( // Each bucket (including its overflow buckets, if any) will have either all or none of its // entries in the evacuated* states (except during the evacuate() method, which only happens // during map writes and thus no one else can observe the map during that time). - empty = 0 // cell is empty - evacuatedEmpty = 1 // cell is empty, bucket is evacuated. + emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. + emptyOne = 1 // this cell is empty evacuatedX = 2 // key/value is valid. Entry has been evacuated to first half of larger table. evacuatedY = 3 // same as above, but evacuated to second half of larger table. - minTopHash = 4 // minimum tophash for a normal filled cell. + evacuatedEmpty = 4 // cell is empty, bucket is evacuated. + minTopHash = 5 // minimum tophash for a normal filled cell. // flags iterator = 1 // there may be an iterator using buckets @@ -119,6 +121,11 @@ const ( noCheck = 1<<(8*sys.PtrSize) - 1 ) +// isEmpty reports whether the given tophash array entry represents an empty bucket entry. +func isEmpty(x uint8) bool { + return x <= emptyOne +} + // A header for a Go map. type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go. @@ -211,7 +218,7 @@ func tophash(hash uintptr) uint8 { func evacuated(b *bmap) bool { h := b.tophash[0] - return h > empty && h < minTopHash + return h > emptyOne && h < minTopHash } func (b *bmap) overflow(t *maptype) *bmap { @@ -311,7 +318,8 @@ func makemap_small() *hmap { // If h != nil, the map can be created directly in h. // If h.buckets != nil, bucket pointed to can be used as the first bucket. func makemap(t *maptype, hint int, h *hmap) *hmap { - if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) { + mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) + if overflow || mem > maxAlloc { hint = 0 } @@ -321,7 +329,8 @@ func makemap(t *maptype, hint int, h *hmap) *hmap { } h.hash0 = fastrand() - // find size parameter which will hold the requested # of elements + // Find the size parameter B which will hold the requested # of elements. + // For hint < 0 overLoadFactor returns false since hint < bucketCnt. B := uint8(0) for overLoadFactor(hint, B) { B++ @@ -439,9 +448,13 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { } } top := tophash(hash) +bucketloop: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -500,9 +513,13 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) } } top := tophash(hash) +bucketloop: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -547,9 +564,13 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe } } top := tophash(hash) +bucketloop: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -612,7 +633,7 @@ func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { // Set hashWriting after calling alg.hash, since alg.hash may panic, // in which case we have not actually done a write. - h.flags |= hashWriting + h.flags ^= hashWriting if h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) @@ -629,14 +650,18 @@ again: var inserti *uint8 var insertk unsafe.Pointer var val unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { - if b.tophash[i] == empty && inserti == nil { + if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -728,18 +753,22 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { // Set hashWriting after calling alg.hash, since alg.hash may panic, // in which case we have not actually done a write (delete). - h.flags |= hashWriting + h.flags ^= hashWriting bucket := hash & bucketMask(h.B) if h.growing() { growWork(t, h, bucket) } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) + bOrig := b top := tophash(hash) search: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break search + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -764,7 +793,39 @@ search: } else { memclrNoHeapPointers(v, t.elem.size) } - b.tophash[i] = empty + b.tophash[i] = emptyOne + // If the bucket now ends in a bunch of emptyOne states, + // change those to emptyRest states. + // It would be nice to make this a separate function, but + // for loops are not currently inlineable. + if i == bucketCnt-1 { + if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { + goto notLast + } + } else { + if b.tophash[i+1] != emptyRest { + goto notLast + } + } + for { + b.tophash[i] = emptyRest + if i == 0 { + if b == bOrig { + break // beginning of initial bucket, we're done. + } + // Find previous bucket, continue at its last entry. + c := b + for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { + } + i = bucketCnt - 1 + } else { + i-- + } + if b.tophash[i] != emptyOne { + break + } + } + notLast: h.count-- break search } @@ -899,7 +960,9 @@ next: } for ; i < bucketCnt; i++ { offi := (i + it.offset) & (bucketCnt - 1) - if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty { + if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { + // TODO: emptyRest is hard to use here, as we start iterating + // in the middle of a bucket. It's feasible, just tricky. continue } k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) @@ -990,7 +1053,7 @@ func mapclear(t *maptype, h *hmap) { throw("concurrent map writes") } - h.flags |= hashWriting + h.flags ^= hashWriting h.flags &^= sameSizeGrow h.oldbuckets = nil @@ -1158,7 +1221,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { v := add(k, bucketCnt*uintptr(t.keysize)) for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { top := b.tophash[i] - if top == empty { + if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } @@ -1195,7 +1258,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { } } - if evacuatedX+1 != evacuatedY { + if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { throw("bad evacuatedN") } @@ -1351,6 +1414,11 @@ func reflect_mapiterkey(it *hiter) unsafe.Pointer { return it.key } +//go:linkname reflect_mapitervalue reflect.mapitervalue +func reflect_mapitervalue(it *hiter) unsafe.Pointer { + return it.value +} + //go:linkname reflect_maplen reflect.maplen func reflect_maplen(h *hmap) int { if h == nil { -- cgit v1.2.3