diff options
author | Ian Lance Taylor <ian@gcc.gnu.org> | 2019-01-15 20:32:39 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2019-01-15 20:32:39 +0000 |
commit | 6a0c8e77f289a5c2e1b1ad0f2c8a5c5105f599a6 (patch) | |
tree | ed17062ac88ccb7fdf858eb98d80b5880065061a /libgo/go | |
parent | a81a6d58367e63f3c7314eb793002e5feb379428 (diff) |
compiler, runtime: panic on uncomparable map key, even if map is empty
This ports https://golang.org/cl/155918 from the master repo.
runtime: panic on uncomparable map key, even if map is empty
Reorg map flags a bit so we don't need any extra space for the extra flag.
This is a pre-req for updating libgo to the Go 1.12beta2 release.
Reviewed-on: https://go-review.googlesource.com/c/157858
From-SVN: r267950
Diffstat (limited to 'libgo/go')
-rw-r--r-- | libgo/go/reflect/type.go | 58 | ||||
-rw-r--r-- | libgo/go/runtime/map.go | 73 | ||||
-rw-r--r-- | libgo/go/runtime/type.go | 37 |
3 files changed, 109 insertions, 59 deletions
diff --git a/libgo/go/reflect/type.go b/libgo/go/reflect/type.go index da7796f3703..e4a9326d083 100644 --- a/libgo/go/reflect/type.go +++ b/libgo/go/reflect/type.go @@ -347,16 +347,13 @@ type interfaceType struct { // mapType represents a map type. type mapType struct { rtype - key *rtype // map key type - elem *rtype // map element (value) type - bucket *rtype // internal bucket structure - keysize uint8 // size of key slot - indirectkey uint8 // store ptr to key instead of key itself - valuesize uint8 // size of value slot - indirectvalue uint8 // store ptr to value instead of value itself - bucketsize uint16 // size of bucket - reflexivekey bool // true if k==k for all keys - needkeyupdate bool // true if we need to update key on an overwrite + key *rtype // map key type + elem *rtype // map element (value) type + bucket *rtype // internal bucket structure + keysize uint8 // size of key slot + valuesize uint8 // size of value slot + bucketsize uint16 // size of bucket + flags uint32 } // ptrType represents a pointer type. @@ -1506,6 +1503,8 @@ func MapOf(key, elem Type) Type { s := "map[" + *ktyp.string + "]" + *etyp.string // Make a map type. + // Note: flag values must match those used in the TMAP case + // in ../cmd/compile/internal/gc/reflect.go:dtypesym. var imap interface{} = (map[unsafe.Pointer]unsafe.Pointer)(nil) mt := **(**mapType)(unsafe.Pointer(&imap)) mt.string = &s @@ -1520,23 +1519,29 @@ func MapOf(key, elem Type) Type { mt.ptrToThis = nil mt.bucket = bucketOf(ktyp, etyp) + mt.flags = 0 if ktyp.size > maxKeySize { mt.keysize = uint8(ptrSize) - mt.indirectkey = 1 + mt.flags |= 1 // indirect key } else { mt.keysize = uint8(ktyp.size) - mt.indirectkey = 0 } if etyp.size > maxValSize { mt.valuesize = uint8(ptrSize) - mt.indirectvalue = 1 + mt.flags |= 2 // indirect value } else { mt.valuesize = uint8(etyp.size) - mt.indirectvalue = 0 } mt.bucketsize = uint16(mt.bucket.size) - mt.reflexivekey = isReflexive(ktyp) - mt.needkeyupdate = needKeyUpdate(ktyp) + if isReflexive(ktyp) { + mt.flags |= 4 + } + if needKeyUpdate(ktyp) { + mt.flags |= 8 + } + if hashMightPanic(ktyp) { + mt.flags |= 16 + } // Canonicalize before storing in lookupCache ti := toType(&mt.rtype) @@ -1715,6 +1720,27 @@ func needKeyUpdate(t *rtype) bool { } } +// hashMightPanic reports whether the hash of a map key of type t might panic. +func hashMightPanic(t *rtype) bool { + switch t.Kind() { + case Interface: + return true + case Array: + tt := (*arrayType)(unsafe.Pointer(t)) + return hashMightPanic(tt.elem) + case Struct: + tt := (*structType)(unsafe.Pointer(t)) + for _, f := range tt.fields { + if hashMightPanic(f.typ) { + return true + } + } + return false + default: + return false + } +} + // Make sure these routines stay in sync with ../../runtime/map.go! // These types exist only for GC, so we only fill out GC relevant info. // Currently, that's just size and the GC program. We also fill in string diff --git a/libgo/go/runtime/map.go b/libgo/go/runtime/map.go index 8e97bc56930..52462c7e117 100644 --- a/libgo/go/runtime/map.go +++ b/libgo/go/runtime/map.go @@ -414,14 +414,17 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { if msanenabled && h != nil { msanread(key, t.key.size) } + hashfn := t.key.hashfn + equalfn := t.key.equalfn if h == nil || h.count == 0 { + if t.hashMightPanic() { + hashfn(key, 0) // see issue 23734 + } return unsafe.Pointer(&zeroVal[0]) } if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } - hashfn := t.key.hashfn - equalfn := t.key.equalfn hash := hashfn(key, uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) @@ -442,12 +445,12 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { + if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if equalfn(key, k) { v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { + if t.indirectvalue() { v = *((*unsafe.Pointer)(v)) } return v @@ -472,14 +475,17 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) if msanenabled && h != nil { msanread(key, t.key.size) } + hashfn := t.key.hashfn + equalfn := t.key.equalfn if h == nil || h.count == 0 { + if t.hashMightPanic() { + hashfn(key, 0) // see issue 23734 + } return unsafe.Pointer(&zeroVal[0]), false } if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } - hashfn := t.key.hashfn - equalfn := t.key.equalfn hash := hashfn(key, uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) @@ -500,12 +506,12 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { + if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if equalfn(key, k) { v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { + if t.indirectvalue() { v = *((*unsafe.Pointer)(v)) } return v, true @@ -547,12 +553,12 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { + if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if equalfn(key, k) { v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { + if t.indirectvalue() { v = *((*unsafe.Pointer)(v)) } return k, v @@ -634,14 +640,14 @@ again: continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { + if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if !equalfn(key, k) { continue } // already have a mapping for key. Update it. - if t.needkeyupdate { + if t.needkeyupdate() { typedmemmove(t.key, k, key) } val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) @@ -672,12 +678,12 @@ again: } // store new key/value at insert position - if t.indirectkey { + if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } - if t.indirectvalue { + if t.indirectvalue() { vmem := newobject(t.elem) *(*unsafe.Pointer)(val) = vmem } @@ -690,7 +696,7 @@ done: throw("concurrent map writes") } h.flags &^= hashWriting - if t.indirectvalue { + if t.indirectvalue() { val = *((*unsafe.Pointer)(val)) } return val @@ -706,15 +712,18 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { if msanenabled && h != nil { msanread(key, t.key.size) } + hashfn := t.key.hashfn + equalfn := t.key.equalfn if h == nil || h.count == 0 { + if t.hashMightPanic() { + hashfn(key, 0) // see issue 23734 + } return } if h.flags&hashWriting != 0 { throw("concurrent map writes") } - hashfn := t.key.hashfn - equalfn := t.key.equalfn hash := hashfn(key, uintptr(h.hash0)) // Set hashWriting after calling alg.hash, since alg.hash may panic, @@ -735,20 +744,20 @@ search: } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) k2 := k - if t.indirectkey { + if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } if !equalfn(key, k2) { continue } // Only clear key if there are pointers in it. - if t.indirectkey { + if t.indirectkey() { *(*unsafe.Pointer)(k) = nil } else if t.key.kind&kindNoPointers == 0 { memclrHasPointers(k, t.key.size) } v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { + if t.indirectvalue() { *(*unsafe.Pointer)(v) = nil } else if t.elem.kind&kindNoPointers == 0 { memclrHasPointers(v, t.elem.size) @@ -894,7 +903,7 @@ next: continue } k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) - if t.indirectkey { + if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize)) @@ -906,7 +915,7 @@ next: // through the oldbucket, skipping any keys that will go // to the other new bucket (each oldbucket expands to two // buckets during a grow). - if t.reflexivekey || equalfn(k, k) { + if t.reflexivekey() || equalfn(k, k) { // If the item in the oldbucket is not destined for // the current new bucket in the iteration, skip it. hash := hashfn(k, uintptr(h.hash0)) @@ -927,13 +936,13 @@ next: } } if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || - !(t.reflexivekey || equalfn(k, k)) { + !(t.reflexivekey() || equalfn(k, k)) { // This is the golden data, we can return it. // OR // key!=key, so the entry can't be deleted or updated, so we can just return it. // That's lucky for us because when key!=key we can't look it up successfully. it.key = k - if t.indirectvalue { + if t.indirectvalue() { v = *((*unsafe.Pointer)(v)) } it.value = v @@ -1157,7 +1166,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { throw("bad map state") } k2 := k - if t.indirectkey { + if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } var useY uint8 @@ -1165,7 +1174,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { // Compute hash to make our evacuation decision (whether we need // to send this key/value to bucket x or bucket y). hash := t.key.hashfn(k2, uintptr(h.hash0)) - if h.flags&iterator != 0 && !t.reflexivekey && !t.key.equalfn(k2, k2) { + if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equalfn(k2, k2) { // If key != key (NaNs), then the hash could be (and probably // will be) entirely different from the old hash. Moreover, // it isn't reproducible. Reproducibility is required in the @@ -1200,12 +1209,12 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { dst.v = add(dst.k, bucketCnt*uintptr(t.keysize)) } dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check - if t.indirectkey { + if t.indirectkey() { *(*unsafe.Pointer)(dst.k) = k2 // copy pointer } else { typedmemmove(t.key, dst.k, k) // copy value } - if t.indirectvalue { + if t.indirectvalue() { *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) } else { typedmemmove(t.elem, dst.v, v) @@ -1271,12 +1280,12 @@ func reflect_makemap(t *maptype, cap int) *hmap { if !ismapkey(t.key) { throw("runtime.reflect_makemap: unsupported map key type") } - if t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(sys.PtrSize)) || - t.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) { + if t.key.size > maxKeySize && (!t.indirectkey() || t.keysize != uint8(sys.PtrSize)) || + t.key.size <= maxKeySize && (t.indirectkey() || t.keysize != uint8(t.key.size)) { throw("key size wrong") } - if t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(sys.PtrSize)) || - t.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) { + if t.elem.size > maxValueSize && (!t.indirectvalue() || t.valuesize != uint8(sys.PtrSize)) || + t.elem.size <= maxValueSize && (t.indirectvalue() || t.valuesize != uint8(t.elem.size)) { throw("value size wrong") } if t.key.align > bucketCnt { diff --git a/libgo/go/runtime/type.go b/libgo/go/runtime/type.go index 8fd38c3f396..5cafa38e18b 100644 --- a/libgo/go/runtime/type.go +++ b/libgo/go/runtime/type.go @@ -86,17 +86,32 @@ type interfacetype struct { } type maptype struct { - typ _type - key *_type - elem *_type - bucket *_type // internal type representing a hash bucket - keysize uint8 // size of key slot - indirectkey bool // store ptr to key instead of key itself - valuesize uint8 // size of value slot - indirectvalue bool // store ptr to value instead of value itself - bucketsize uint16 // size of bucket - reflexivekey bool // true if k==k for all keys - needkeyupdate bool // true if we need to update key on an overwrite + typ _type + key *_type + elem *_type + bucket *_type // internal type representing a hash bucket + keysize uint8 // size of key slot + valuesize uint8 // size of value slot + bucketsize uint16 // size of bucket + flags uint32 +} + +// Note: flag values must match those used in the TMAP case +// in ../cmd/compile/internal/gc/reflect.go:dtypesym. +func (mt *maptype) indirectkey() bool { // store ptr to key instead of key itself + return mt.flags&1 != 0 +} +func (mt *maptype) indirectvalue() bool { // store ptr to value instead of value itself + return mt.flags&2 != 0 +} +func (mt *maptype) reflexivekey() bool { // true if k==k for all keys + return mt.flags&4 != 0 +} +func (mt *maptype) needkeyupdate() bool { // true if we need to update key on an overwrite + return mt.flags&8 != 0 +} +func (mt *maptype) hashMightPanic() bool { // true if hash function might panic + return mt.flags&16 != 0 } type arraytype struct { |