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 5package runtime 6 7import ( 8 "internal/cpu" 9 "runtime/internal/sys" 10 "unsafe" 11) 12 13// For gccgo, use go:linkname to export compiler-called functions. 14// 15//go:linkname memhash0 16//go:linkname memhash8 17//go:linkname memhash16 18//go:linkname memhash32 19//go:linkname memhash64 20//go:linkname memhash128 21//go:linkname strhash 22//go:linkname f32hash 23//go:linkname f64hash 24//go:linkname c64hash 25//go:linkname c128hash 26//go:linkname interhash 27//go:linkname nilinterhash 28//go:linkname memequal0 29//go:linkname memequal8 30//go:linkname memequal16 31//go:linkname memequal32 32//go:linkname memequal64 33//go:linkname memequal128 34//go:linkname strequal 35//go:linkname f32equal 36//go:linkname f64equal 37//go:linkname c64equal 38//go:linkname c128equal 39//go:linkname interequal 40//go:linkname nilinterequal 41//go:linkname efaceeq 42//go:linkname ifaceeq 43//go:linkname ifacevaleq 44//go:linkname ifaceefaceeq 45//go:linkname efacevaleq 46//go:linkname cmpstring 47// 48// Temporary to be called from C code. 49//go:linkname alginit 50 51const ( 52 c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289) 53 c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503) 54) 55 56func memhash0(p unsafe.Pointer, h uintptr) uintptr { 57 return h 58} 59 60func memhash8(p unsafe.Pointer, h uintptr) uintptr { 61 return memhash(p, h, 1) 62} 63 64func memhash16(p unsafe.Pointer, h uintptr) uintptr { 65 return memhash(p, h, 2) 66} 67 68func memhash128(p unsafe.Pointer, h uintptr) uintptr { 69 return memhash(p, h, 16) 70} 71 72// runtime variable to check if the processor we're running on 73// actually supports the instructions used by the AES-based 74// hash implementation. 75var useAeshash bool 76 77// in C code 78func aeshashbody(p unsafe.Pointer, h, s uintptr, sched []byte) uintptr 79 80func aeshash(p unsafe.Pointer, h, s uintptr) uintptr { 81 return aeshashbody(p, h, s, aeskeysched[:]) 82} 83 84func aeshashstr(p unsafe.Pointer, h uintptr) uintptr { 85 ps := (*stringStruct)(p) 86 return aeshashbody(unsafe.Pointer(ps.str), h, uintptr(ps.len), aeskeysched[:]) 87} 88 89func strhash(a unsafe.Pointer, h uintptr) uintptr { 90 x := (*stringStruct)(a) 91 return memhash(x.str, h, uintptr(x.len)) 92} 93 94// NOTE: Because NaN != NaN, a map can contain any 95// number of (mostly useless) entries keyed with NaNs. 96// To avoid long hash chains, we assign a random number 97// as the hash value for a NaN. 98 99func f32hash(p unsafe.Pointer, h uintptr) uintptr { 100 f := *(*float32)(p) 101 switch { 102 case f == 0: 103 return c1 * (c0 ^ h) // +0, -0 104 case f != f: 105 return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN 106 default: 107 return memhash(p, h, 4) 108 } 109} 110 111func f64hash(p unsafe.Pointer, h uintptr) uintptr { 112 f := *(*float64)(p) 113 switch { 114 case f == 0: 115 return c1 * (c0 ^ h) // +0, -0 116 case f != f: 117 return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN 118 default: 119 return memhash(p, h, 8) 120 } 121} 122 123func c64hash(p unsafe.Pointer, h uintptr) uintptr { 124 x := (*[2]float32)(p) 125 return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h)) 126} 127 128func c128hash(p unsafe.Pointer, h uintptr) uintptr { 129 x := (*[2]float64)(p) 130 return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h)) 131} 132 133func interhash(p unsafe.Pointer, h uintptr) uintptr { 134 a := (*iface)(p) 135 tab := a.tab 136 if tab == nil { 137 return h 138 } 139 t := *(**_type)(tab) 140 if t.equal == nil { 141 // Check hashability here. We could do this check inside 142 // typehash, but we want to report the topmost type in 143 // the error text (e.g. in a struct with a field of slice type 144 // we want to report the struct, not the slice). 145 panic(errorString("hash of unhashable type " + t.string())) 146 } 147 if isDirectIface(t) { 148 return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0) 149 } else { 150 return c1 * typehash(t, a.data, h^c0) 151 } 152} 153 154func nilinterhash(p unsafe.Pointer, h uintptr) uintptr { 155 a := (*eface)(p) 156 t := a._type 157 if t == nil { 158 return h 159 } 160 if t.equal == nil { 161 // See comment in interhash above. 162 panic(errorString("hash of unhashable type " + t.string())) 163 } 164 if isDirectIface(t) { 165 return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0) 166 } else { 167 return c1 * typehash(t, a.data, h^c0) 168 } 169} 170 171// typehash computes the hash of the object of type t at address p. 172// h is the seed. 173// This function is seldom used. Most maps use for hashing either 174// fixed functions (e.g. f32hash) or compiler-generated functions 175// (e.g. for a type like struct { x, y string }). This implementation 176// is slower but more general and is used for hashing interface types 177// (called from interhash or nilinterhash, above) or for hashing in 178// maps generated by reflect.MapOf (reflect_typehash, below). 179// Note: this function must match the compiler generated 180// functions exactly. See issue 37716. 181func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr { 182 if t.tflag&tflagRegularMemory != 0 { 183 // Handle ptr sizes specially, see issue 37086. 184 switch t.size { 185 case 4: 186 return memhash32(p, h) 187 case 8: 188 return memhash64(p, h) 189 default: 190 return memhash(p, h, t.size) 191 } 192 } 193 switch t.kind & kindMask { 194 case kindFloat32: 195 return f32hash(p, h) 196 case kindFloat64: 197 return f64hash(p, h) 198 case kindComplex64: 199 return c64hash(p, h) 200 case kindComplex128: 201 return c128hash(p, h) 202 case kindString: 203 return strhash(p, h) 204 case kindInterface: 205 i := (*interfacetype)(unsafe.Pointer(t)) 206 if len(i.methods) == 0 { 207 return nilinterhash(p, h) 208 } 209 return interhash(p, h) 210 case kindArray: 211 a := (*arraytype)(unsafe.Pointer(t)) 212 for i := uintptr(0); i < a.len; i++ { 213 h = typehash(a.elem, add(p, i*a.elem.size), h) 214 } 215 return h 216 case kindStruct: 217 s := (*structtype)(unsafe.Pointer(t)) 218 for _, f := range s.fields { 219 // TODO: maybe we could hash several contiguous fields all at once. 220 if f.name != nil && *f.name == "_" { 221 continue 222 } 223 h = typehash(f.typ, add(p, f.offset()), h) 224 } 225 return h 226 default: 227 // Should never happen, as typehash should only be called 228 // with comparable types. 229 panic(errorString("hash of unhashable type " + t.string())) 230 } 231} 232 233//go:linkname reflect_typehash reflect.typehash 234func reflect_typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr { 235 return typehash(t, p, h) 236} 237 238func memequal0(p, q unsafe.Pointer) bool { 239 return true 240} 241func memequal8(p, q unsafe.Pointer) bool { 242 return *(*int8)(p) == *(*int8)(q) 243} 244func memequal16(p, q unsafe.Pointer) bool { 245 return *(*int16)(p) == *(*int16)(q) 246} 247func memequal32(p, q unsafe.Pointer) bool { 248 return *(*int32)(p) == *(*int32)(q) 249} 250func memequal64(p, q unsafe.Pointer) bool { 251 return *(*int64)(p) == *(*int64)(q) 252} 253func memequal128(p, q unsafe.Pointer) bool { 254 return *(*[2]int64)(p) == *(*[2]int64)(q) 255} 256func f32equal(p, q unsafe.Pointer) bool { 257 return *(*float32)(p) == *(*float32)(q) 258} 259func f64equal(p, q unsafe.Pointer) bool { 260 return *(*float64)(p) == *(*float64)(q) 261} 262func c64equal(p, q unsafe.Pointer) bool { 263 return *(*complex64)(p) == *(*complex64)(q) 264} 265func c128equal(p, q unsafe.Pointer) bool { 266 return *(*complex128)(p) == *(*complex128)(q) 267} 268func strequal(p, q unsafe.Pointer) bool { 269 return *(*string)(p) == *(*string)(q) 270} 271func interequal(p, q unsafe.Pointer) bool { 272 return ifaceeq(*(*iface)(p), *(*iface)(q)) 273} 274func nilinterequal(p, q unsafe.Pointer) bool { 275 return efaceeq(*(*eface)(p), *(*eface)(q)) 276} 277func efaceeq(x, y eface) bool { 278 t := x._type 279 if t != y._type { 280 return false 281 } 282 if t == nil { 283 return true 284 } 285 eq := t.equal 286 if eq == nil { 287 panic(errorString("comparing uncomparable type " + t.string())) 288 } 289 if isDirectIface(t) { 290 return x.data == y.data 291 } 292 return eq(x.data, y.data) 293} 294 295func ifaceeq(x, y iface) bool { 296 xtab := x.tab 297 if xtab == nil && y.tab == nil { 298 return true 299 } 300 if xtab == nil || y.tab == nil { 301 return false 302 } 303 t := *(**_type)(xtab) 304 if t != *(**_type)(y.tab) { 305 return false 306 } 307 eq := t.equal 308 if eq == nil { 309 panic(errorString("comparing uncomparable type " + t.string())) 310 } 311 if isDirectIface(t) { 312 // Direct interface types are ptr, chan, map, func, and single-element structs/arrays thereof. 313 // Maps and funcs are not comparable, so they can't reach here. 314 // Ptrs, chans, and single-element items can be compared directly using ==. 315 return x.data == y.data 316 } 317 return eq(x.data, y.data) 318} 319 320func ifacevaleq(x iface, t *_type, p unsafe.Pointer) bool { 321 if x.tab == nil { 322 return false 323 } 324 xt := *(**_type)(x.tab) 325 if xt != t { 326 return false 327 } 328 eq := t.equal 329 if eq == nil { 330 panic(errorString("comparing uncomparable type " + t.string())) 331 } 332 if isDirectIface(t) { 333 return x.data == p 334 } 335 return eq(x.data, p) 336} 337 338func ifaceefaceeq(x iface, y eface) bool { 339 if x.tab == nil && y._type == nil { 340 return true 341 } 342 if x.tab == nil || y._type == nil { 343 return false 344 } 345 xt := *(**_type)(x.tab) 346 if xt != y._type { 347 return false 348 } 349 eq := xt.equal 350 if eq == nil { 351 panic(errorString("comparing uncomparable type " + xt.string())) 352 } 353 if isDirectIface(xt) { 354 return x.data == y.data 355 } 356 return eq(x.data, y.data) 357} 358 359func efacevaleq(x eface, t *_type, p unsafe.Pointer) bool { 360 if x._type == nil { 361 return false 362 } 363 if x._type != t { 364 return false 365 } 366 eq := t.equal 367 if eq == nil { 368 panic(errorString("comparing uncomparable type " + t.string())) 369 } 370 if isDirectIface(t) { 371 // See comment in efaceeq. 372 return x.data == p 373 } 374 return eq(x.data, p) 375} 376 377func cmpstring(x, y string) int { 378 a := stringStructOf(&x) 379 b := stringStructOf(&y) 380 l := a.len 381 if l > b.len { 382 l = b.len 383 } 384 i := memcmp(unsafe.Pointer(a.str), unsafe.Pointer(b.str), uintptr(l)) 385 if i != 0 { 386 return int(i) 387 } 388 if a.len < b.len { 389 return -1 390 } else if a.len > b.len { 391 return 1 392 } 393 return 0 394} 395 396// For the unsafe.Pointer type descriptor in libgo/runtime/go-unsafe-pointer.c. 397 398func pointerhash(p unsafe.Pointer, h uintptr) uintptr { 399 return memhash(p, h, unsafe.Sizeof(unsafe.Pointer)) 400} 401 402func pointerequal(p, q unsafe.Pointer) bool { 403 return *(*unsafe.Pointer)(p) == *(*unsafe.Pointer)(q) 404} 405 406// Force the creation of function descriptors for equality and hash 407// functions. These will be referenced directly by the compiler. 408var _ = memhash 409var _ = memhash0 410var _ = memhash8 411var _ = memhash16 412var _ = memhash32 413var _ = memhash64 414var _ = memhash128 415var _ = strhash 416var _ = f32hash 417var _ = f64hash 418var _ = c64hash 419var _ = c128hash 420var _ = interhash 421var _ = nilinterhash 422var _ = memequal0 423var _ = memequal8 424var _ = memequal16 425var _ = memequal32 426var _ = memequal64 427var _ = memequal128 428var _ = f32equal 429var _ = f64equal 430var _ = c64equal 431var _ = c128equal 432var _ = strequal 433var _ = interequal 434var _ = nilinterequal 435var _ = pointerhash 436var _ = pointerequal 437 438// Testing adapters for hash quality tests (see hash_test.go) 439func stringHash(s string, seed uintptr) uintptr { 440 return strhash(noescape(unsafe.Pointer(&s)), seed) 441} 442 443func bytesHash(b []byte, seed uintptr) uintptr { 444 s := (*slice)(unsafe.Pointer(&b)) 445 return memhash(s.array, seed, uintptr(s.len)) 446} 447 448func int32Hash(i uint32, seed uintptr) uintptr { 449 return memhash32(noescape(unsafe.Pointer(&i)), seed) 450} 451 452func int64Hash(i uint64, seed uintptr) uintptr { 453 return memhash64(noescape(unsafe.Pointer(&i)), seed) 454} 455 456func efaceHash(i interface{}, seed uintptr) uintptr { 457 return nilinterhash(noescape(unsafe.Pointer(&i)), seed) 458} 459 460func ifaceHash(i interface { 461 F() 462}, seed uintptr) uintptr { 463 return interhash(noescape(unsafe.Pointer(&i)), seed) 464} 465 466const hashRandomBytes = sys.PtrSize / 4 * 64 467 468// used in asm_{386,amd64,arm64}.s to seed the hash function 469var aeskeysched [hashRandomBytes]byte 470 471// used in hash{32,64}.go to seed the hash function 472var hashkey [4]uintptr 473 474func alginit() { 475 // Install AES hash algorithms if the instructions needed are present. 476 if (GOARCH == "386" || GOARCH == "amd64") && 477 support_aes && 478 cpu.X86.HasAES && // AESENC 479 cpu.X86.HasSSSE3 && // PSHUFB 480 cpu.X86.HasSSE41 { // PINSR{D,Q} 481 initAlgAES() 482 return 483 } 484 if GOARCH == "arm64" && cpu.ARM64.HasAES { 485 initAlgAES() 486 return 487 } 488 getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:]) 489 hashkey[0] |= 1 // make sure these numbers are odd 490 hashkey[1] |= 1 491 hashkey[2] |= 1 492 hashkey[3] |= 1 493} 494 495func initAlgAES() { 496 useAeshash = true 497 // Initialize with random data so hash collisions will be hard to engineer. 498 getRandomData(aeskeysched[:]) 499} 500 501// Note: These routines perform the read with a native endianness. 502func readUnaligned32(p unsafe.Pointer) uint32 { 503 q := (*[4]byte)(p) 504 if sys.BigEndian { 505 return uint32(q[3]) | uint32(q[2])<<8 | uint32(q[1])<<16 | uint32(q[0])<<24 506 } 507 return uint32(q[0]) | uint32(q[1])<<8 | uint32(q[2])<<16 | uint32(q[3])<<24 508} 509 510func readUnaligned64(p unsafe.Pointer) uint64 { 511 q := (*[8]byte)(p) 512 if sys.BigEndian { 513 return uint64(q[7]) | uint64(q[6])<<8 | uint64(q[5])<<16 | uint64(q[4])<<24 | 514 uint64(q[3])<<32 | uint64(q[2])<<40 | uint64(q[1])<<48 | uint64(q[0])<<56 515 } 516 return uint64(q[0]) | uint64(q[1])<<8 | uint64(q[2])<<16 | uint64(q[3])<<24 | uint64(q[4])<<32 | uint64(q[5])<<40 | uint64(q[6])<<48 | uint64(q[7])<<56 517} 518