+ "runtime"

+ if runtime.Compiler == "gccgo" {

+ t.Log("does not work on gccgo without better escape analysis")

+ } else {

+ t.Errorf("expected no allocations, got %f", allocs)

+ }

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd plan9 solaris

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package x509

+

+// Possible certificate files; stop after finding one.

+var certFiles []string

+// +build aix dragonfly freebsd linux nacl netbsd openbsd solaris

+ "/var/ssl/certs", // AIX

+const goosList = "aix android darwin dragonfly freebsd linux nacl netbsd openbsd plan9 solaris windows zos "

+ if x == 0 {

+ return x

+ }

+ if x == 0 {

+ return x

+ }

+ if x == 0 {

+ return x

+ }

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// Copyright 2011 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// +build cgo,!netgo

+

+package net

+

+import (

+ "syscall"

+)

+

+const cgoAddrInfoFlags = syscall.AI_CANONNAME

+// +build aix darwin linux,!android netbsd solaris

+// +build aix darwin dragonfly freebsd netbsd openbsd

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd windows solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix nacl

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris nacl

+// +build aix darwin nacl netbsd openbsd

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix nacl solaris

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package net

+

+import (

+ "os"

+ "syscall"

+)

+

+// This was copied from sockopt_linux.go

+

+func setDefaultSockopts(s, family, sotype int, ipv6only bool) error {

+ if family == syscall.AF_INET6 && sotype != syscall.SOCK_RAW {

+ // Allow both IP versions even if the OS default

+ // is otherwise. Note that some operating systems

+ // never admit this option.

+ syscall.SetsockoptInt(s, syscall.IPPROTO_IPV6, syscall.IPV6_V6ONLY, boolint(ipv6only))

+ }

+ // Allow broadcast.

+ return os.NewSyscallError("setsockopt", syscall.SetsockoptInt(s, syscall.SOL_SOCKET, syscall.SO_BROADCAST, 1))

+}

+

+func setDefaultListenerSockopts(s int) error {

+ // Allow reuse of recently-used addresses.

+ return os.NewSyscallError("setsockopt", syscall.SetsockoptInt(s, syscall.SOL_SOCKET, syscall.SO_REUSEADDR, 1))

+}

+

+func setDefaultMulticastSockopts(s int) error {

+ // Allow multicast UDP and raw IP datagram sockets to listen

+ // concurrently across multiple listeners.

+ return os.NewSyscallError("setsockopt", syscall.SetsockoptInt(s, syscall.SOL_SOCKET, syscall.SO_REUSEADDR, 1))

+}

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris windows

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package net

+

+import "syscall"

+

+func setIPv4MulticastInterface(fd *netFD, ifi *Interface) error {

+ return syscall.ENOPROTOOPT

+}

+

+func setIPv4MulticastLoopback(fd *netFD, v bool) error {

+ return syscall.ENOPROTOOPT

+}

+// +build aix darwin dragonfly freebsd linux netbsd openbsd windows

+// +build aix darwin dragonfly nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris windows

+// +build aix freebsd linux netbsd

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+ "runtime"

+ // On AIX when readdir_r hits EOF it sets dirent to nil and returns 9.

+ // https://www.ibm.com/support/knowledgecenter/ssw_aix_71/com.ibm.aix.basetrf2/readdir_r.htm

+ if runtime.GOOS == "aix" && i == 9 && dirent == nil {

+ break

+ }

+// +build aix linux solaris,386 solaris,sparc

+// +build !aix

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// +build aix

+

+package os

+

+// We query the working directory at init, to use it later to search for the

+// executable file

+// errWd will be checked later, if we need to use initWd

+var initWd, errWd = Getwd()

+

+func executable() (string, error) {

+ var err error

+ var exePath string

+ if len(Args) == 0 || Args[0] == "" {

+ return "", ErrNotExist

+ }

+ // Args[0] is an absolute path : this is the executable

+ if IsPathSeparator(Args[0][0]) {

+ exePath = Args[0]

+ } else {

+ for i := 1; i < len(Args[0]); i++ {

+ // Args[0] is a relative path : append current directory

+ if IsPathSeparator(Args[0][i]) {

+ if errWd != nil {

+ return "", errWd

+ }

+ exePath = initWd + string(PathSeparator) + Args[0]

+ break

+ }

+ }

+ }

+ if exePath != "" {

+ err = isExecutable(exePath)

+ if err == nil {

+ return exePath, nil

+ }

+ // File does not exist or is not executable,

+ // this is an unexpected situation !

+ return "", err

+ }

+ // Search for executable in $PATH

+ for _, dir := range splitPathList(Getenv("PATH")) {

+ if len(dir) == 0 {

+ continue

+ }

+ if !IsPathSeparator(dir[0]) {

+ if errWd != nil {

+ return "", errWd

+ }

+ dir = initWd + string(PathSeparator) + dir

+ }

+ exePath = dir + string(PathSeparator) + Args[0]

+ err = isExecutable(exePath)

+ if err == nil {

+ return exePath, nil

+ }

+ if err == ErrPermission {

+ return "", err

+ }

+ }

+ return "", ErrNotExist

+}

+

+// isExecutable returns an error if a given file is not an executable.

+func isExecutable(path string) error {

+ stat, err := Stat(path)

+ if err != nil {

+ return err

+ }

+ mode := stat.Mode()

+ if !mode.IsRegular() {

+ return ErrPermission

+ }

+ if (mode & 0111) != 0 {

+ return nil

+ }

+ return ErrPermission

+}

+

+// splitPathList splits a path list.

+// This is based on genSplit from strings/strings.go

+func splitPathList(pathList string) []string {

+ n := 1

+ for i := 0; i < len(pathList); i++ {

+ if pathList[i] == PathListSeparator {

+ n++

+ }

+ }

+ start := 0

+ a := make([]string, n)

+ na := 0

+ for i := 0; i+1 <= len(pathList) && na+1 < n; i++ {

+ if pathList[i] == PathListSeparator {

+ a[na] = pathList[start:i]

+ na++

+ start = i + 1

+ }

+ }

+ a[na] = pathList[start:]

+ return a[:na+1]

+}

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+ // buffer too small

+ if e == syscall.ERANGE {

+ continue

+ }

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+// +build !aix

+// +build aix linux openbsd solaristag

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+// +build aix solaris irix rtems

+// +build aix dragonfly linux netbsd openbsd solaris

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package user

+

+import "syscall"

+

+// Declarations for the libc functions on AIX.

+

+//extern _posix_getpwnam_r

+func libc_getpwnam_r(name *byte, pwd *syscall.Passwd, buf *byte, buflen syscall.Size_t, result **syscall.Passwd) int

+

+//extern _posix_getpwuid_r

+func libc_getpwuid_r(uid syscall.Uid_t, pwd *syscall.Passwd, buf *byte, buflen syscall.Size_t, result **syscall.Passwd) int

+

+//extern _posix_getgrnam_r

+func libc_getgrnam_r(name *byte, grp *syscall.Group, buf *byte, buflen syscall.Size_t, result **syscall.Group) int

+

+//extern _posix_getgrgid_r

+func libc_getgrgid_r(gid syscall.Gid_t, grp *syscall.Group, buf *byte, buflen syscall.Size_t, result **syscall.Group) int

+

+//extern getgrset

+func libc_getgrset(user *byte) *byte

+// Copyright 2017 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package user

+

+import "fmt"

+

+func listGroups(u *User) ([]string, error) {

+ return nil, fmt.Errorf("user: list groups for %s: not supported on AIX", u.Username)

+}

+// +build aix darwin dragonfly freebsd !android,linux netbsd openbsd solaris

+// +build aix dragonfly nacl netbsd openbsd solaris

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris

+ ptrdata uintptr // size of memory prefix holding all pointers

+ hash uint32 // hash of type; avoids computation in hash tables

+ kind uint8 // enumeration for C

+ align int8 // alignment of variable with this type

+ fieldAlign uint8 // alignment of struct field with this type

+ _ uint8 // unused/padding

+ gcdata *byte // garbage collection data

+ string *string // string form; unnecessary but undeniably useful

+ *uncommonType // (relatively) uncommon fields

+ ptrToThis *rtype // type for pointer to this type, if used in binary or has methods

+ var gcdata *byte

+ var ptrdata uintptr

+ } else if maxAlign < ptrSize {

+ size = align(size, ptrSize)

+ maxAlign = ptrSize

+ nptr := size / ptrSize

+ mask := make([]byte, (nptr+7)/8)

+ psize := bucketSize

+ psize = align(psize, uintptr(ktyp.fieldAlign))

+ base := psize / ptrSize

+

+ if ktyp.kind&kindGCProg != 0 {

+ panic("reflect: unexpected GC program in MapOf")

+ }

+ kmask := (*[16]byte)(unsafe.Pointer(ktyp.gcdata))

+ for i := uintptr(0); i < ktyp.size/ptrSize; i++ {

+ if (kmask[i/8]>>(i%8))&1 != 0 {

+ for j := uintptr(0); j < bucketSize; j++ {

+ word := base + j*ktyp.size/ptrSize + i

+ mask[word/8] |= 1 << (word % 8)

+ }

+ }

+ }

+ psize += bucketSize * ktyp.size

+ psize = align(psize, uintptr(etyp.fieldAlign))

+ base = psize / ptrSize

+

+ if etyp.kind&kindGCProg != 0 {

+ panic("reflect: unexpected GC program in MapOf")

+ }

+ emask := (*[16]byte)(unsafe.Pointer(etyp.gcdata))

+ for i := uintptr(0); i < etyp.size/ptrSize; i++ {

+ if (emask[i/8]>>(i%8))&1 != 0 {

+ for j := uintptr(0); j < bucketSize; j++ {

+ word := base + j*etyp.size/ptrSize + i

+ mask[word/8] |= 1 << (word % 8)

+ }

+ }

+ }

+ }

+

+ word := ovoff / ptrSize

+ mask[word/8] |= 1 << (word % 8)

+ gcdata = &mask[0]

+ ptrdata = (word + 1) * ptrSize

+

+ // overflow word must be last

+ if ptrdata != size {

+ panic("reflect: bad layout computation in MapOf")

+ ptrdata: ptrdata,

+ gcdata: gcdata,

+ hash = uint32(0)

+ size uintptr

+ typalign int8

+ comparable = true

+ hashable = true

+ hasPtr = false // records whether at least one struct-field is a pointer

+ hasGCProg = false // records whether a struct-field type has a GCProg

+ if ft.kind&kindGCProg != 0 {

+ hasGCProg = true

+ }

+ comparable = comparable && (ft.equalfn != nil)

+ hashable = hashable && (ft.hashfn != nil)

+

+ }

+

+ if hasGCProg {

+ lastPtrField := 0

+ for i, ft := range fs {

+ if ft.typ.pointers() {

+ lastPtrField = i

+ }

+ }

+ prog := []byte{0, 0, 0, 0} // will be length of prog

+ for i, ft := range fs {

+ if i > lastPtrField {

+ // gcprog should not include anything for any field after

+ // the last field that contains pointer data

+ break

+ }

+ // FIXME(sbinet) handle padding, fields smaller than a word

+ elemGC := (*[1 << 30]byte)(unsafe.Pointer(ft.typ.gcdata))[:]

+ elemPtrs := ft.typ.ptrdata / ptrSize

+ switch {

+ case ft.typ.kind&kindGCProg == 0 && ft.typ.ptrdata != 0:

+ // Element is small with pointer mask; use as literal bits.

+ mask := elemGC

+ // Emit 120-bit chunks of full bytes (max is 127 but we avoid using partial bytes).

+ var n uintptr

+ for n := elemPtrs; n > 120; n -= 120 {

+ prog = append(prog, 120)

+ prog = append(prog, mask[:15]...)

+ mask = mask[15:]

+ }

+ prog = append(prog, byte(n))

+ prog = append(prog, mask[:(n+7)/8]...)

+ case ft.typ.kind&kindGCProg != 0:

+ // Element has GC program; emit one element.

+ elemProg := elemGC[4 : 4+*(*uint32)(unsafe.Pointer(&elemGC[0]))-1]

+ prog = append(prog, elemProg...)

+ }

+ // Pad from ptrdata to size.

+ elemWords := ft.typ.size / ptrSize

+ if elemPtrs < elemWords {

+ // Emit literal 0 bit, then repeat as needed.

+ prog = append(prog, 0x01, 0x00)

+ if elemPtrs+1 < elemWords {

+ prog = append(prog, 0x81)

+ prog = appendVarint(prog, elemWords-elemPtrs-1)

+ }

+ }

+ }

+ *(*uint32)(unsafe.Pointer(&prog[0])) = uint32(len(prog) - 4)

+ typ.kind |= kindGCProg

+ typ.gcdata = &prog[0]

+ } else {

+ typ.kind &^= kindGCProg

+ bv := new(bitVector)

+ addTypeBits(bv, 0, typ.common())

+ if len(bv.data) > 0 {

+ typ.gcdata = &bv.data[0]

+ typ.ptrdata = typeptrdata(typ.common())

+ if hashable {

+ typ.hashfn = func(p unsafe.Pointer, seed uintptr) uintptr {

+ o := seed

+ for _, ft := range typ.fields {

+ pi := unsafe.Pointer(uintptr(p) + ft.offset)

+ o = ft.typ.hashfn(pi, o)

+ }

+ return o

+ } else {

+ typ.hashfn = nil

+ if comparable {

+ typ.equalfn = func(p, q unsafe.Pointer) bool {

+ for _, ft := range typ.fields {

+ pi := unsafe.Pointer(uintptr(p) + ft.offset)

+ qi := unsafe.Pointer(uintptr(q) + ft.offset)

+ if !ft.typ.equalfn(pi, qi) {

+ return false

+ }

+ return true

+ } else {

+ typ.equalfn = nil

+// typeptrdata returns the length in bytes of the prefix of t

+// containing pointer data. Anything after this offset is scalar data.

+// keep in sync with ../cmd/compile/internal/gc/reflect.go

+func typeptrdata(t *rtype) uintptr {

+ if !t.pointers() {

+ return 0

+ }

+ switch t.Kind() {

+ case Struct:

+ st := (*structType)(unsafe.Pointer(t))

+ // find the last field that has pointers.

+ field := 0

+ for i := range st.fields {

+ ft := st.fields[i].typ

+ if ft.pointers() {

+ field = i

+ }

+ }

+ f := st.fields[field]

+ return f.offset + f.typ.ptrdata

+

+ default:

+ panic("reflect.typeptrdata: unexpected type, " + t.String())

+ }

+}

+

+// See cmd/compile/internal/gc/reflect.go for derivation of constant.

+const maxPtrmaskBytes = 2048

+

+ if count > 0 && typ.ptrdata != 0 {

+ array.ptrdata = typ.size*uintptr(count-1) + typ.ptrdata

+ }

+ array.gcdata = nil

+ array.ptrdata = 0

+ array.gcdata = typ.gcdata

+ array.ptrdata = typ.ptrdata

+

+ case typ.kind&kindGCProg == 0 && array.size <= maxPtrmaskBytes*8*ptrSize:

+ // Element is small with pointer mask; array is still small.

+ // Create direct pointer mask by turning each 1 bit in elem

+ // into count 1 bits in larger mask.

+ mask := make([]byte, (array.ptrdata/ptrSize+7)/8)

+ elemMask := (*[1 << 30]byte)(unsafe.Pointer(typ.gcdata))[:]

+ elemWords := typ.size / ptrSize

+ for j := uintptr(0); j < typ.ptrdata/ptrSize; j++ {

+ if (elemMask[j/8]>>(j%8))&1 != 0 {

+ for i := uintptr(0); i < array.len; i++ {

+ k := i*elemWords + j

+ mask[k/8] |= 1 << (k % 8)

+ }

+ }

+ }

+ array.gcdata = &mask[0]

+ // Create program that emits one element

+ // and then repeats to make the array.

+ prog := []byte{0, 0, 0, 0} // will be length of prog

+ elemGC := (*[1 << 30]byte)(unsafe.Pointer(typ.gcdata))[:]

+ elemPtrs := typ.ptrdata / ptrSize

+ if typ.kind&kindGCProg == 0 {

+ // Element is small with pointer mask; use as literal bits.

+ mask := elemGC

+ // Emit 120-bit chunks of full bytes (max is 127 but we avoid using partial bytes).

+ var n uintptr

+ for n = elemPtrs; n > 120; n -= 120 {

+ prog = append(prog, 120)

+ prog = append(prog, mask[:15]...)

+ mask = mask[15:]

+ }

+ prog = append(prog, byte(n))

+ prog = append(prog, mask[:(n+7)/8]...)

+ } else {

+ // Element has GC program; emit one element.

+ elemProg := elemGC[4 : 4+*(*uint32)(unsafe.Pointer(&elemGC[0]))-1]

+ prog = append(prog, elemProg...)

+ }

+ // Pad from ptrdata to size.

+ elemWords := typ.size / ptrSize

+ if elemPtrs < elemWords {

+ // Emit literal 0 bit, then repeat as needed.

+ prog = append(prog, 0x01, 0x00)

+ if elemPtrs+1 < elemWords {

+ prog = append(prog, 0x81)

+ prog = appendVarint(prog, elemWords-elemPtrs-1)

+ }

+ }

+ // Repeat count-1 times.

+ if elemWords < 0x80 {

+ prog = append(prog, byte(elemWords|0x80))

+ } else {

+ prog = append(prog, 0x80)

+ prog = appendVarint(prog, elemWords)

+ }

+ prog = appendVarint(prog, uintptr(count)-1)

+ prog = append(prog, 0)

+ *(*uint32)(unsafe.Pointer(&prog[0])) = uint32(len(prog) - 4)

+ array.kind |= kindGCProg

+ array.gcdata = &prog[0]

+ array.ptrdata = array.size // overestimate but ok; must match program

+ esize := typ.size

+

+ if typ.equalfn == nil {

+ array.equalfn = nil

+ } else {

+ eequal := typ.equalfn

+ array.equalfn = func(p, q unsafe.Pointer) bool {

+ for i := 0; i < count; i++ {

+ pi := arrayAt(p, i, esize)

+ qi := arrayAt(q, i, esize)

+ if !eequal(pi, qi) {

+ return false

+ }

+ }

+ return true

+ if typ.hashfn == nil {

+ array.hashfn = nil

+ } else {

+ ehash := typ.hashfn

+ array.hashfn = func(ptr unsafe.Pointer, seed uintptr) uintptr {

+ o := seed

+ for i := 0; i < count; i++ {

+ o = ehash(arrayAt(ptr, i, esize), o)

+ return o

+func interhash(p unsafe.Pointer, h uintptr) uintptr {

+func interequal(p, q unsafe.Pointer) bool {

+func nilinterequal(p, q unsafe.Pointer) bool {

+// Testing adapters for hash quality tests (see hash_test.go)

+func stringHash(s string, seed uintptr) uintptr {

+ return strhash(noescape(unsafe.Pointer(&s)), seed)

+}

+

+func bytesHash(b []byte, seed uintptr) uintptr {

+ s := (*slice)(unsafe.Pointer(&b))

+ return memhash(s.array, seed, uintptr(s.len))

+}

+

+func int32Hash(i uint32, seed uintptr) uintptr {

+ return memhash32(noescape(unsafe.Pointer(&i)), seed)

+}

+

+func int64Hash(i uint64, seed uintptr) uintptr {

+ return memhash64(noescape(unsafe.Pointer(&i)), seed)

+}

+

+func efaceHash(i interface{}, seed uintptr) uintptr {

+ return nilinterhash(noescape(unsafe.Pointer(&i)), seed)

+}

+

+func ifaceHash(i interface {

+ F()

+}, seed uintptr) uintptr {

+ return interhash(noescape(unsafe.Pointer(&i)), seed)

+}

+

+// Copyright 2009 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// Cgo call and callback support.

+

+package runtime

+

+import (

+ "runtime/internal/sys"

+ "unsafe"

+)

+

+// Pointer checking for cgo code.

+

+// We want to detect all cases where a program that does not use

+// unsafe makes a cgo call passing a Go pointer to memory that

+// contains a Go pointer. Here a Go pointer is defined as a pointer

+// to memory allocated by the Go runtime. Programs that use unsafe

+// can evade this restriction easily, so we don't try to catch them.

+// The cgo program will rewrite all possibly bad pointer arguments to

+// call cgoCheckPointer, where we can catch cases of a Go pointer

+// pointing to a Go pointer.

+

+// Complicating matters, taking the address of a slice or array

+// element permits the C program to access all elements of the slice

+// or array. In that case we will see a pointer to a single element,

+// but we need to check the entire data structure.

+

+// The cgoCheckPointer call takes additional arguments indicating that

+// it was called on an address expression. An additional argument of

+// true means that it only needs to check a single element. An

+// additional argument of a slice or array means that it needs to

+// check the entire slice/array, but nothing else. Otherwise, the

+// pointer could be anything, and we check the entire heap object,

+// which is conservative but safe.

+

+// When and if we implement a moving garbage collector,

+// cgoCheckPointer will pin the pointer for the duration of the cgo

+// call. (This is necessary but not sufficient; the cgo program will

+// also have to change to pin Go pointers that cannot point to Go

+// pointers.)

+

+// cgoCheckPointer checks if the argument contains a Go pointer that

+// points to a Go pointer, and panics if it does.

+func cgoCheckPointer(ptr interface{}, args ...interface{}) {

+ if debug.cgocheck == 0 {

+ return

+ }

+

+ ep := (*eface)(unsafe.Pointer(&ptr))

+ t := ep._type

+

+ top := true

+ if len(args) > 0 && (t.kind&kindMask == kindPtr || t.kind&kindMask == kindUnsafePointer) {

+ p := ep.data

+ if t.kind&kindDirectIface == 0 {

+ p = *(*unsafe.Pointer)(p)

+ }

+ if !cgoIsGoPointer(p) {

+ return

+ }

+ aep := (*eface)(unsafe.Pointer(&args[0]))

+ switch aep._type.kind & kindMask {

+ case kindBool:

+ if t.kind&kindMask == kindUnsafePointer {

+ // We don't know the type of the element.

+ break

+ }

+ pt := (*ptrtype)(unsafe.Pointer(t))

+ cgoCheckArg(pt.elem, p, true, false, cgoCheckPointerFail)

+ return

+ case kindSlice:

+ // Check the slice rather than the pointer.

+ ep = aep

+ t = ep._type

+ case kindArray:

+ // Check the array rather than the pointer.

+ // Pass top as false since we have a pointer

+ // to the array.

+ ep = aep

+ t = ep._type

+ top = false

+ default:

+ throw("can't happen")

+ }

+ }

+

+ cgoCheckArg(t, ep.data, t.kind&kindDirectIface == 0, top, cgoCheckPointerFail)

+}

+

+const cgoCheckPointerFail = "cgo argument has Go pointer to Go pointer"

+const cgoResultFail = "cgo result has Go pointer"

+

+// cgoCheckArg is the real work of cgoCheckPointer. The argument p

+// is either a pointer to the value (of type t), or the value itself,

+// depending on indir. The top parameter is whether we are at the top

+// level, where Go pointers are allowed.

+func cgoCheckArg(t *_type, p unsafe.Pointer, indir, top bool, msg string) {

+ if t.kind&kindNoPointers != 0 {

+ // If the type has no pointers there is nothing to do.

+ return

+ }

+

+ switch t.kind & kindMask {

+ default:

+ throw("can't happen")

+ case kindArray:

+ at := (*arraytype)(unsafe.Pointer(t))

+ if !indir {

+ if at.len != 1 {

+ throw("can't happen")

+ }

+ cgoCheckArg(at.elem, p, at.elem.kind&kindDirectIface == 0, top, msg)

+ return

+ }

+ for i := uintptr(0); i < at.len; i++ {

+ cgoCheckArg(at.elem, p, true, top, msg)

+ p = add(p, at.elem.size)

+ }

+ case kindChan, kindMap:

+ // These types contain internal pointers that will

+ // always be allocated in the Go heap. It's never OK

+ // to pass them to C.

+ panic(errorString(msg))

+ case kindFunc:

+ if indir {

+ p = *(*unsafe.Pointer)(p)

+ }

+ if !cgoIsGoPointer(p) {

+ return

+ }

+ panic(errorString(msg))

+ case kindInterface:

+ it := *(**_type)(p)

+ if it == nil {

+ return

+ }

+ // A type known at compile time is OK since it's

+ // constant. A type not known at compile time will be

+ // in the heap and will not be OK.

+ if inheap(uintptr(unsafe.Pointer(it))) {

+ panic(errorString(msg))

+ }

+ p = *(*unsafe.Pointer)(add(p, sys.PtrSize))

+ if !cgoIsGoPointer(p) {

+ return

+ }

+ if !top {

+ panic(errorString(msg))

+ }

+ cgoCheckArg(it, p, it.kind&kindDirectIface == 0, false, msg)

+ case kindSlice:

+ st := (*slicetype)(unsafe.Pointer(t))

+ s := (*slice)(p)

+ p = s.array

+ if !cgoIsGoPointer(p) {

+ return

+ }

+ if !top {

+ panic(errorString(msg))

+ }

+ if st.elem.kind&kindNoPointers != 0 {

+ return

+ }

+ for i := 0; i < s.cap; i++ {

+ cgoCheckArg(st.elem, p, true, false, msg)

+ p = add(p, st.elem.size)

+ }

+ case kindString:

+ ss := (*stringStruct)(p)

+ if !cgoIsGoPointer(ss.str) {

+ return

+ }

+ if !top {

+ panic(errorString(msg))

+ }

+ case kindStruct:

+ st := (*structtype)(unsafe.Pointer(t))

+ if !indir {

+ if len(st.fields) != 1 {

+ throw("can't happen")

+ }

+ cgoCheckArg(st.fields[0].typ, p, st.fields[0].typ.kind&kindDirectIface == 0, top, msg)

+ return

+ }

+ for _, f := range st.fields {

+ cgoCheckArg(f.typ, add(p, f.offset), true, top, msg)

+ }

+ case kindPtr, kindUnsafePointer:

+ if indir {

+ p = *(*unsafe.Pointer)(p)

+ }

+

+ if !cgoIsGoPointer(p) {

+ return

+ }

+ if !top {

+ panic(errorString(msg))

+ }

+

+ cgoCheckUnknownPointer(p, msg)

+ }

+}

+

+// cgoCheckUnknownPointer is called for an arbitrary pointer into Go

+// memory. It checks whether that Go memory contains any other

+// pointer into Go memory. If it does, we panic.

+// The return values are unused but useful to see in panic tracebacks.

+func cgoCheckUnknownPointer(p unsafe.Pointer, msg string) (base, i uintptr) {

+ if cgoInRange(p, mheap_.arena_start, mheap_.arena_used) {

+ if !inheap(uintptr(p)) {

+ // On 32-bit systems it is possible for C's allocated memory

+ // to have addresses between arena_start and arena_used.

+ // Either this pointer is a stack or an unused span or it's

+ // a C allocation. Escape analysis should prevent the first,

+ // garbage collection should prevent the second,

+ // and the third is completely OK.

+ return

+ }

+

+ b, hbits, span, _ := heapBitsForObject(uintptr(p), 0, 0, false)

+ base = b

+ if base == 0 {

+ return

+ }

+ n := span.elemsize

+ for i = uintptr(0); i < n; i += sys.PtrSize {

+ if i != 1*sys.PtrSize && !hbits.morePointers() {

+ // No more possible pointers.

+ break

+ }

+ if hbits.isPointer() {

+ if cgoIsGoPointer(*(*unsafe.Pointer)(unsafe.Pointer(base + i))) {

+ panic(errorString(msg))

+ }

+ }

+ hbits = hbits.next()

+ }

+

+ return

+ }

+

+ roots := gcRoots

+ for roots != nil {

+ for j := 0; j < roots.count; j++ {

+ pr := roots.roots[j]

+ addr := uintptr(pr.decl)

+ if cgoInRange(p, addr, addr+pr.size) {

+ cgoCheckBits(pr.decl, pr.gcdata, 0, pr.ptrdata)

+ return

+ }

+ }

+ roots = roots.next

+ }

+

+ return

+}

+

+// cgoIsGoPointer returns whether the pointer is a Go pointer--a

+// pointer to Go memory. We only care about Go memory that might

+// contain pointers.

+//go:nosplit

+//go:nowritebarrierrec

+func cgoIsGoPointer(p unsafe.Pointer) bool {

+ if p == nil {

+ return false

+ }

+

+ if inHeapOrStack(uintptr(p)) {

+ return true

+ }

+

+ roots := gcRoots

+ for roots != nil {

+ for i := 0; i < roots.count; i++ {

+ pr := roots.roots[i]

+ addr := uintptr(pr.decl)

+ if cgoInRange(p, addr, addr+pr.size) {

+ return true

+ }

+ }

+ roots = roots.next

+ }

+

+ return false

+}

+

+// cgoInRange returns whether p is between start and end.

+//go:nosplit

+//go:nowritebarrierrec

+func cgoInRange(p unsafe.Pointer, start, end uintptr) bool {

+ return start <= uintptr(p) && uintptr(p) < end

+}

+

+// cgoCheckResult is called to check the result parameter of an

+// exported Go function. It panics if the result is or contains a Go

+// pointer.

+func cgoCheckResult(val interface{}) {

+ if debug.cgocheck == 0 {

+ return

+ }

+

+ ep := (*eface)(unsafe.Pointer(&val))

+ t := ep._type

+ cgoCheckArg(t, ep.data, t.kind&kindDirectIface == 0, false, cgoResultFail)

+}

+ roots := gcRoots

+ for roots != nil {

+ for i := 0; i < roots.count; i++ {

+ pr := roots.roots[i]

+ addr := uintptr(pr.decl)

+ if cgoInRange(src, addr, addr+pr.size) {

+ doff := uintptr(src) - addr

+ cgoCheckBits(add(src, -doff), pr.gcdata, off+doff, size)

+ return

+ }

+ roots = roots.next

+// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

+func NumCPU() int {

+ return int(ncpu)

+}

+// +build aix darwin dragonfly freebsd linux nacl netbsd openbsd solaris windows

+var Xadduintptr = atomic.Xadduintptr

+var FuncPC = funcPC

+var Fastlog2 = fastlog2

+var StringHash = stringHash

+var BytesHash = bytesHash

+var Int32Hash = int32Hash

+var Int64Hash = int64Hash

+var EfaceHash = efaceHash

+var IfaceHash = ifaceHash

+// Copyright 2013 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+package runtime_test

+

+import (

+ "fmt"

+ "math"

+ "math/rand"

+ . "runtime"

+ "strings"

+ "testing"

+ "unsafe"

+)

+

+// Smhasher is a torture test for hash functions.

+// https://code.google.com/p/smhasher/

+// This code is a port of some of the Smhasher tests to Go.

+//

+// The current AES hash function passes Smhasher. Our fallback

+// hash functions don't, so we only enable the difficult tests when

+// we know the AES implementation is available.

+

+// Sanity checks.

+// hash should not depend on values outside key.

+// hash should not depend on alignment.

+func TestSmhasherSanity(t *testing.T) {

+ r := rand.New(rand.NewSource(1234))

+ const REP = 10

+ const KEYMAX = 128

+ const PAD = 16

+ const OFFMAX = 16

+ for k := 0; k < REP; k++ {

+ for n := 0; n < KEYMAX; n++ {

+ for i := 0; i < OFFMAX; i++ {

+ var b [KEYMAX + OFFMAX + 2*PAD]byte

+ var c [KEYMAX + OFFMAX + 2*PAD]byte

+ randBytes(r, b[:])

+ randBytes(r, c[:])

+ copy(c[PAD+i:PAD+i+n], b[PAD:PAD+n])

+ if BytesHash(b[PAD:PAD+n], 0) != BytesHash(c[PAD+i:PAD+i+n], 0) {

+ t.Errorf("hash depends on bytes outside key")

+ }

+ }

+ }

+ }

+}

+

+type HashSet struct {

+ m map[uintptr]struct{} // set of hashes added

+ n int // number of hashes added

+}

+

+func newHashSet() *HashSet {

+ return &HashSet{make(map[uintptr]struct{}), 0}

+}

+func (s *HashSet) add(h uintptr) {

+ s.m[h] = struct{}{}

+ s.n++

+}

+func (s *HashSet) addS(x string) {

+ s.add(StringHash(x, 0))

+}

+func (s *HashSet) addB(x []byte) {

+ s.add(BytesHash(x, 0))

+}

+func (s *HashSet) addS_seed(x string, seed uintptr) {

+ s.add(StringHash(x, seed))

+}

+func (s *HashSet) check(t *testing.T) {

+ const SLOP = 10.0

+ collisions := s.n - len(s.m)

+ //fmt.Printf("%d/%d\n", len(s.m), s.n)

+ pairs := int64(s.n) * int64(s.n-1) / 2

+ expected := float64(pairs) / math.Pow(2.0, float64(hashSize))

+ stddev := math.Sqrt(expected)

+ if float64(collisions) > expected+SLOP*(3*stddev+1) {

+ t.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f", collisions, expected, stddev)

+ }

+}

+

+// a string plus adding zeros must make distinct hashes

+func TestSmhasherAppendedZeros(t *testing.T) {

+ s := "hello" + strings.Repeat("\x00", 256)

+ h := newHashSet()

+ for i := 0; i <= len(s); i++ {

+ h.addS(s[:i])

+ }

+ h.check(t)

+}

+

+// All 0-3 byte strings have distinct hashes.

+func TestSmhasherSmallKeys(t *testing.T) {

+ h := newHashSet()

+ var b [3]byte

+ for i := 0; i < 256; i++ {

+ b[0] = byte(i)

+ h.addB(b[:1])

+ for j := 0; j < 256; j++ {

+ b[1] = byte(j)

+ h.addB(b[:2])

+ if !testing.Short() {

+ for k := 0; k < 256; k++ {

+ b[2] = byte(k)

+ h.addB(b[:3])

+ }

+ }

+ }

+ }

+ h.check(t)

+}

+

+// Different length strings of all zeros have distinct hashes.

+func TestSmhasherZeros(t *testing.T) {

+ N := 256 * 1024

+ if testing.Short() {

+ N = 1024

+ }

+ h := newHashSet()

+ b := make([]byte, N)

+ for i := 0; i <= N; i++ {

+ h.addB(b[:i])

+ }

+ h.check(t)

+}

+

+// Strings with up to two nonzero bytes all have distinct hashes.

+func TestSmhasherTwoNonzero(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ h := newHashSet()

+ for n := 2; n <= 16; n++ {

+ twoNonZero(h, n)

+ }

+ h.check(t)

+}

+func twoNonZero(h *HashSet, n int) {

+ b := make([]byte, n)

+

+ // all zero

+ h.addB(b[:])

+

+ // one non-zero byte

+ for i := 0; i < n; i++ {

+ for x := 1; x < 256; x++ {

+ b[i] = byte(x)

+ h.addB(b[:])

+ b[i] = 0

+ }

+ }

+

+ // two non-zero bytes

+ for i := 0; i < n; i++ {

+ for x := 1; x < 256; x++ {

+ b[i] = byte(x)

+ for j := i + 1; j < n; j++ {

+ for y := 1; y < 256; y++ {

+ b[j] = byte(y)

+ h.addB(b[:])

+ b[j] = 0

+ }

+ }

+ b[i] = 0

+ }

+ }

+}

+

+// Test strings with repeats, like "abcdabcdabcdabcd..."

+func TestSmhasherCyclic(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ r := rand.New(rand.NewSource(1234))

+ const REPEAT = 8

+ const N = 1000000

+ for n := 4; n <= 12; n++ {

+ h := newHashSet()

+ b := make([]byte, REPEAT*n)

+ for i := 0; i < N; i++ {

+ b[0] = byte(i * 79 % 97)

+ b[1] = byte(i * 43 % 137)

+ b[2] = byte(i * 151 % 197)

+ b[3] = byte(i * 199 % 251)

+ randBytes(r, b[4:n])

+ for j := n; j < n*REPEAT; j++ {

+ b[j] = b[j-n]

+ }

+ h.addB(b)

+ }

+ h.check(t)

+ }

+}

+

+// Test strings with only a few bits set

+func TestSmhasherSparse(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ sparse(t, 32, 6)

+ sparse(t, 40, 6)

+ sparse(t, 48, 5)

+ sparse(t, 56, 5)

+ sparse(t, 64, 5)

+ sparse(t, 96, 4)

+ sparse(t, 256, 3)

+ sparse(t, 2048, 2)

+}

+func sparse(t *testing.T, n int, k int) {

+ b := make([]byte, n/8)

+ h := newHashSet()

+ setbits(h, b, 0, k)

+ h.check(t)

+}

+

+// set up to k bits at index i and greater

+func setbits(h *HashSet, b []byte, i int, k int) {

+ h.addB(b)

+ if k == 0 {

+ return

+ }

+ for j := i; j < len(b)*8; j++ {

+ b[j/8] |= byte(1 << uint(j&7))

+ setbits(h, b, j+1, k-1)

+ b[j/8] &= byte(^(1 << uint(j&7)))

+ }

+}

+

+// Test all possible combinations of n blocks from the set s.

+// "permutation" is a bad name here, but it is what Smhasher uses.

+func TestSmhasherPermutation(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ permutation(t, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)

+ permutation(t, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)

+ permutation(t, []uint32{0, 1}, 20)

+ permutation(t, []uint32{0, 1 << 31}, 20)

+ permutation(t, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)

+}

+func permutation(t *testing.T, s []uint32, n int) {

+ b := make([]byte, n*4)

+ h := newHashSet()

+ genPerm(h, b, s, 0)

+ h.check(t)

+}

+func genPerm(h *HashSet, b []byte, s []uint32, n int) {

+ h.addB(b[:n])

+ if n == len(b) {

+ return

+ }

+ for _, v := range s {

+ b[n] = byte(v)

+ b[n+1] = byte(v >> 8)

+ b[n+2] = byte(v >> 16)

+ b[n+3] = byte(v >> 24)

+ genPerm(h, b, s, n+4)

+ }

+}

+

+type Key interface {

+ clear() // set bits all to 0

+ random(r *rand.Rand) // set key to something random

+ bits() int // how many bits key has

+ flipBit(i int) // flip bit i of the key

+ hash() uintptr // hash the key

+ name() string // for error reporting

+}

+

+type BytesKey struct {

+ b []byte

+}

+

+func (k *BytesKey) clear() {

+ for i := range k.b {

+ k.b[i] = 0

+ }

+}

+func (k *BytesKey) random(r *rand.Rand) {

+ randBytes(r, k.b)

+}

+func (k *BytesKey) bits() int {

+ return len(k.b) * 8

+}

+func (k *BytesKey) flipBit(i int) {

+ k.b[i>>3] ^= byte(1 << uint(i&7))

+}

+func (k *BytesKey) hash() uintptr {

+ return BytesHash(k.b, 0)

+}

+func (k *BytesKey) name() string {

+ return fmt.Sprintf("bytes%d", len(k.b))

+}

+

+type Int32Key struct {

+ i uint32

+}

+

+func (k *Int32Key) clear() {

+ k.i = 0

+}

+func (k *Int32Key) random(r *rand.Rand) {

+ k.i = r.Uint32()

+}

+func (k *Int32Key) bits() int {

+ return 32

+}

+func (k *Int32Key) flipBit(i int) {

+ k.i ^= 1 << uint(i)

+}

+func (k *Int32Key) hash() uintptr {

+ return Int32Hash(k.i, 0)

+}

+func (k *Int32Key) name() string {

+ return "int32"

+}

+

+type Int64Key struct {

+ i uint64

+}

+

+func (k *Int64Key) clear() {

+ k.i = 0

+}

+func (k *Int64Key) random(r *rand.Rand) {

+ k.i = uint64(r.Uint32()) + uint64(r.Uint32())<<32

+}

+func (k *Int64Key) bits() int {

+ return 64

+}

+func (k *Int64Key) flipBit(i int) {

+ k.i ^= 1 << uint(i)

+}

+func (k *Int64Key) hash() uintptr {

+ return Int64Hash(k.i, 0)

+}

+func (k *Int64Key) name() string {

+ return "int64"

+}

+

+type EfaceKey struct {

+ i interface{}

+}

+

+func (k *EfaceKey) clear() {

+ k.i = nil

+}

+func (k *EfaceKey) random(r *rand.Rand) {

+ k.i = uint64(r.Int63())

+}

+func (k *EfaceKey) bits() int {

+ // use 64 bits. This tests inlined interfaces

+ // on 64-bit targets and indirect interfaces on

+ // 32-bit targets.

+ return 64

+}

+func (k *EfaceKey) flipBit(i int) {

+ k.i = k.i.(uint64) ^ uint64(1)<<uint(i)

+}

+func (k *EfaceKey) hash() uintptr {

+ return EfaceHash(k.i, 0)

+}

+func (k *EfaceKey) name() string {

+ return "Eface"

+}

+

+type IfaceKey struct {

+ i interface {

+ F()

+ }

+}

+type fInter uint64

+

+func (x fInter) F() {

+}

+

+func (k *IfaceKey) clear() {

+ k.i = nil

+}

+func (k *IfaceKey) random(r *rand.Rand) {

+ k.i = fInter(r.Int63())

+}

+func (k *IfaceKey) bits() int {

+ // use 64 bits. This tests inlined interfaces

+ // on 64-bit targets and indirect interfaces on

+ // 32-bit targets.

+ return 64

+}

+func (k *IfaceKey) flipBit(i int) {

+ k.i = k.i.(fInter) ^ fInter(1)<<uint(i)

+}

+func (k *IfaceKey) hash() uintptr {

+ return IfaceHash(k.i, 0)

+}

+func (k *IfaceKey) name() string {

+ return "Iface"

+}

+

+// Flipping a single bit of a key should flip each output bit with 50% probability.

+func TestSmhasherAvalanche(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ avalancheTest1(t, &BytesKey{make([]byte, 2)})

+ avalancheTest1(t, &BytesKey{make([]byte, 4)})

+ avalancheTest1(t, &BytesKey{make([]byte, 8)})

+ avalancheTest1(t, &BytesKey{make([]byte, 16)})

+ avalancheTest1(t, &BytesKey{make([]byte, 32)})

+ avalancheTest1(t, &BytesKey{make([]byte, 200)})

+ avalancheTest1(t, &Int32Key{})

+ avalancheTest1(t, &Int64Key{})

+ avalancheTest1(t, &EfaceKey{})

+ avalancheTest1(t, &IfaceKey{})

+}

+func avalancheTest1(t *testing.T, k Key) {

+ const REP = 100000

+ r := rand.New(rand.NewSource(1234))

+ n := k.bits()

+

+ // grid[i][j] is a count of whether flipping

+ // input bit i affects output bit j.

+ grid := make([][hashSize]int, n)

+

+ for z := 0; z < REP; z++ {

+ // pick a random key, hash it

+ k.random(r)

+ h := k.hash()

+

+ // flip each bit, hash & compare the results

+ for i := 0; i < n; i++ {

+ k.flipBit(i)

+ d := h ^ k.hash()

+ k.flipBit(i)

+

+ // record the effects of that bit flip

+ g := &grid[i]

+ for j := 0; j < hashSize; j++ {

+ g[j] += int(d & 1)

+ d >>= 1

+ }

+ }

+ }

+

+ // Each entry in the grid should be about REP/2.

+ // More precisely, we did N = k.bits() * hashSize experiments where

+ // each is the sum of REP coin flips. We want to find bounds on the

+ // sum of coin flips such that a truly random experiment would have

+ // all sums inside those bounds with 99% probability.

+ N := n * hashSize

+ var c float64

+ // find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999

+ for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 {

+ }

+ c *= 4.0 // allowed slack - we don't need to be perfectly random

+ mean := .5 * REP

+ stddev := .5 * math.Sqrt(REP)

+ low := int(mean - c*stddev)

+ high := int(mean + c*stddev)

+ for i := 0; i < n; i++ {

+ for j := 0; j < hashSize; j++ {

+ x := grid[i][j]

+ if x < low || x > high {

+ t.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k.name(), i, j, x, REP)

+ }

+ }

+ }

+}

+

+// All bit rotations of a set of distinct keys

+func TestSmhasherWindowed(t *testing.T) {

+ windowed(t, &Int32Key{})

+ windowed(t, &Int64Key{})

+ windowed(t, &BytesKey{make([]byte, 128)})

+}

+func windowed(t *testing.T, k Key) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ const BITS = 16

+

+ for r := 0; r < k.bits(); r++ {

+ h := newHashSet()

+ for i := 0; i < 1<<BITS; i++ {

+ k.clear()

+ for j := 0; j < BITS; j++ {

+ if i>>uint(j)&1 != 0 {

+ k.flipBit((j + r) % k.bits())

+ }

+ }

+ h.add(k.hash())

+ }

+ h.check(t)

+ }

+}

+

+// All keys of the form prefix + [A-Za-z0-9]*N + suffix.

+func TestSmhasherText(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ text(t, "Foo", "Bar")

+ text(t, "FooBar", "")

+ text(t, "", "FooBar")

+}

+func text(t *testing.T, prefix, suffix string) {

+ const N = 4

+ const S = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst0123456789"

+ const L = len(S)

+ b := make([]byte, len(prefix)+N+len(suffix))

+ copy(b, prefix)

+ copy(b[len(prefix)+N:], suffix)

+ h := newHashSet()

+ c := b[len(prefix):]

+ for i := 0; i < L; i++ {

+ c[0] = S[i]

+ for j := 0; j < L; j++ {

+ c[1] = S[j]

+ for k := 0; k < L; k++ {

+ c[2] = S[k]

+ for x := 0; x < L; x++ {

+ c[3] = S[x]

+ h.addB(b)

+ }

+ }

+ }

+ }

+ h.check(t)

+}

+

+// Make sure different seed values generate different hashes.

+func TestSmhasherSeed(t *testing.T) {

+ h := newHashSet()

+ const N = 100000

+ s := "hello"

+ for i := 0; i < N; i++ {

+ h.addS_seed(s, uintptr(i))

+ }

+ h.check(t)

+}

+

+// size of the hash output (32 or 64 bits)

+const hashSize = 32 + int(^uintptr(0)>>63<<5)

+

+func randBytes(r *rand.Rand, b []byte) {

+ for i := range b {

+ b[i] = byte(r.Uint32())

+ }

+}

+

+func benchmarkHash(b *testing.B, n int) {

+ s := strings.Repeat("A", n)

+

+ for i := 0; i < b.N; i++ {

+ StringHash(s, 0)

+ }

+ b.SetBytes(int64(n))

+}

+

+func BenchmarkHash5(b *testing.B) { benchmarkHash(b, 5) }

+func BenchmarkHash16(b *testing.B) { benchmarkHash(b, 16) }

+func BenchmarkHash64(b *testing.B) { benchmarkHash(b, 64) }

+func BenchmarkHash1024(b *testing.B) { benchmarkHash(b, 1024) }

+func BenchmarkHash65536(b *testing.B) { benchmarkHash(b, 65536) }

+

+func TestArrayHash(t *testing.T) {

+ if Compiler == "gccgo" {

+ t.Skip("does not work on gccgo without better escape analysis")

+ }

+

+ // Make sure that "" in arrays hash correctly. The hash

+ // should at least scramble the input seed so that, e.g.,

+ // {"","foo"} and {"foo",""} have different hashes.

+

+ // If the hash is bad, then all (8 choose 4) = 70 keys

+ // have the same hash. If so, we allocate 70/8 = 8

+ // overflow buckets. If the hash is good we don't

+ // normally allocate any overflow buckets, and the

+ // probability of even one or two overflows goes down rapidly.

+ // (There is always 1 allocation of the bucket array. The map

+ // header is allocated on the stack.)

+ f := func() {

+ // Make the key type at most 128 bytes. Otherwise,

+ // we get an allocation per key.

+ type key [8]string

+ m := make(map[key]bool, 70)

+

+ // fill m with keys that have 4 "foo"s and 4 ""s.

+ for i := 0; i < 256; i++ {

+ var k key

+ cnt := 0

+ for j := uint(0); j < 8; j++ {

+ if i>>j&1 != 0 {

+ k[j] = "foo"

+ cnt++

+ }

+ }

+ if cnt == 4 {

+ m[k] = true

+ }

+ }

+ if len(m) != 70 {

+ t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))

+ }

+ }

+ if n := testing.AllocsPerRun(10, f); n > 6 {

+ t.Errorf("too many allocs %f - hash not balanced", n)

+ }

+}

+func TestStructHash(t *testing.T) {

+ // See the comment in TestArrayHash.

+ f := func() {

+ type key struct {

+ a, b, c, d, e, f, g, h string

+ }

+ m := make(map[key]bool, 70)

+

+ // fill m with keys that have 4 "foo"s and 4 ""s.

+ for i := 0; i < 256; i++ {

+ var k key

+ cnt := 0

+ if i&1 != 0 {

+ k.a = "foo"

+ cnt++

+ }

+ if i&2 != 0 {

+ k.b = "foo"

+ cnt++

+ }

+ if i&4 != 0 {

+ k.c = "foo"

+ cnt++

+ }

+ if i&8 != 0 {

+ k.d = "foo"

+ cnt++

+ }

+ if i&16 != 0 {

+ k.e = "foo"

+ cnt++

+ }

+ if i&32 != 0 {

+ k.f = "foo"

+ cnt++

+ }

+ if i&64 != 0 {

+ k.g = "foo"

+ cnt++

+ }

+ if i&128 != 0 {

+ k.h = "foo"

+ cnt++

+ }

+ if cnt == 4 {

+ m[k] = true

+ }

+ }

+ if len(m) != 70 {

+ t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))

+ }

+ }

+ if n := testing.AllocsPerRun(10, f); n > 6 {

+ t.Errorf("too many allocs %f - hash not balanced", n)

+ }

+}

+

+var sink uint64

+

+func BenchmarkAlignedLoad(b *testing.B) {

+ var buf [16]byte

+ p := unsafe.Pointer(&buf[0])

+ var s uint64

+ for i := 0; i < b.N; i++ {

+ s += ReadUnaligned64(p)

+ }

+ sink = s

+}

+

+func BenchmarkUnalignedLoad(b *testing.B) {

+ var buf [16]byte

+ p := unsafe.Pointer(&buf[1])

+ var s uint64

+ for i := 0; i < b.N; i++ {

+ s += ReadUnaligned64(p)

+ }

+ sink = s

+}

+

+func TestCollisions(t *testing.T) {

+ if testing.Short() {

+ t.Skip("Skipping in short mode")

+ }

+ for i := 0; i < 16; i++ {

+ for j := 0; j < 16; j++ {

+ if j == i {

+ continue

+ }

+ var a [16]byte

+ m := make(map[uint16]struct{}, 1<<16)

+ for n := 0; n < 1<<16; n++ {

+ a[i] = byte(n)

+ a[j] = byte(n >> 8)

+ m[uint16(BytesHash(a[:], 0))] = struct{}{}

+ }

+ if len(m) <= 1<<15 {

+ t.Errorf("too many collisions i=%d j=%d outputs=%d out of 65536\n", i, j, len(m))

+ }

+ }

+ }

+}

+// Copyright 2014 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// Implementation of runtime/debug.WriteHeapDump. Writes all

+// objects in the heap plus additional info (roots, threads,

+// finalizers, etc.) to a file.

+

+// The format of the dumped file is described at

+// https://golang.org/s/go15heapdump.

+

+package runtime

+

+import (

+ "runtime/internal/sys"

+ "unsafe"

+)

+

+//go:linkname runtime_debug_WriteHeapDump runtime_debug.WriteHeapDump

+func runtime_debug_WriteHeapDump(fd uintptr) {

+ stopTheWorld("write heap dump")

+

+ systemstack(func() {

+ writeheapdump_m(fd)

+ })

+

+ startTheWorld()

+}

+

+const (

+ fieldKindEol = 0

+ fieldKindPtr = 1

+ fieldKindIface = 2

+ fieldKindEface = 3

+ tagEOF = 0

+ tagObject = 1

+ tagOtherRoot = 2

+ tagType = 3

+ tagGoroutine = 4

+ tagStackFrame = 5

+ tagParams = 6

+ tagFinalizer = 7

+ tagItab = 8

+ tagOSThread = 9

+ tagMemStats = 10

+ tagQueuedFinalizer = 11

+ tagData = 12

+ tagBSS = 13

+ tagDefer = 14

+ tagPanic = 15

+ tagMemProf = 16

+ tagAllocSample = 17

+)

+

+var dumpfd uintptr // fd to write the dump to.

+var tmpbuf []byte

+

+// buffer of pending write data

+const (

+ bufSize = 4096

+)

+

+var buf [bufSize]byte

+var nbuf uintptr

+

+func dwrite(data unsafe.Pointer, len uintptr) {

+ if len == 0 {

+ return

+ }

+ if nbuf+len <= bufSize {

+ copy(buf[nbuf:], (*[bufSize]byte)(data)[:len])

+ nbuf += len

+ return

+ }

+

+ write(dumpfd, unsafe.Pointer(&buf), int32(nbuf))

+ if len >= bufSize {

+ write(dumpfd, data, int32(len))

+ nbuf = 0

+ } else {

+ copy(buf[:], (*[bufSize]byte)(data)[:len])

+ nbuf = len

+ }

+}

+

+func dwritebyte(b byte) {

+ dwrite(unsafe.Pointer(&b), 1)

+}

+

+func flush() {

+ write(dumpfd, unsafe.Pointer(&buf), int32(nbuf))

+ nbuf = 0

+}

+

+// Cache of types that have been serialized already.

+// We use a type's hash field to pick a bucket.

+// Inside a bucket, we keep a list of types that

+// have been serialized so far, most recently used first.

+// Note: when a bucket overflows we may end up

+// serializing a type more than once. That's ok.

+const (

+ typeCacheBuckets = 256

+ typeCacheAssoc = 4

+)

+

+type typeCacheBucket struct {

+ t [typeCacheAssoc]*_type

+}

+

+var typecache [typeCacheBuckets]typeCacheBucket

+

+// dump a uint64 in a varint format parseable by encoding/binary

+func dumpint(v uint64) {

+ var buf [10]byte

+ var n int

+ for v >= 0x80 {

+ buf[n] = byte(v | 0x80)

+ n++

+ v >>= 7

+ }

+ buf[n] = byte(v)

+ n++

+ dwrite(unsafe.Pointer(&buf), uintptr(n))

+}

+

+func dumpbool(b bool) {

+ if b {

+ dumpint(1)

+ } else {

+ dumpint(0)

+ }

+}

+

+// dump varint uint64 length followed by memory contents

+func dumpmemrange(data unsafe.Pointer, len uintptr) {

+ dumpint(uint64(len))

+ dwrite(data, len)

+}

+

+func dumpslice(b []byte) {

+ dumpint(uint64(len(b)))

+ if len(b) > 0 {

+ dwrite(unsafe.Pointer(&b[0]), uintptr(len(b)))

+ }

+}

+

+func dumpstr(s string) {

+ sp := stringStructOf(&s)

+ dumpmemrange(sp.str, uintptr(sp.len))

+}

+

+// dump information for a type

+func dumptype(t *_type) {

+ if t == nil {

+ return

+ }

+

+ // If we've definitely serialized the type before,

+ // no need to do it again.

+ b := &typecache[t.hash&(typeCacheBuckets-1)]

+ if t == b.t[0] {

+ return

+ }

+ for i := 1; i < typeCacheAssoc; i++ {

+ if t == b.t[i] {

+ // Move-to-front

+ for j := i; j > 0; j-- {

+ b.t[j] = b.t[j-1]

+ }

+ b.t[0] = t

+ return

+ }

+ }

+

+ // Might not have been dumped yet. Dump it and

+ // remember we did so.

+ for j := typeCacheAssoc - 1; j > 0; j-- {

+ b.t[j] = b.t[j-1]

+ }

+ b.t[0] = t

+

+ // dump the type

+ dumpint(tagType)

+ dumpint(uint64(uintptr(unsafe.Pointer(t))))

+ dumpint(uint64(t.size))

+ if x := t.uncommontype; x == nil || t.pkgPath == nil || *t.pkgPath == "" {

+ dumpstr(*t.string)

+ } else {

+ pkgpathstr := *t.pkgPath

+ pkgpath := stringStructOf(&pkgpathstr)

+ namestr := *t.name

+ name := stringStructOf(&namestr)

+ dumpint(uint64(uintptr(pkgpath.len) + 1 + uintptr(name.len)))

+ dwrite(pkgpath.str, uintptr(pkgpath.len))

+ dwritebyte('.')

+ dwrite(name.str, uintptr(name.len))

+ }

+ dumpbool(t.kind&kindDirectIface == 0 || t.kind&kindNoPointers == 0)

+}

+

+// dump an object

+func dumpobj(obj unsafe.Pointer, size uintptr, bv bitvector) {

+ dumpbvtypes(&bv, obj)

+ dumpint(tagObject)

+ dumpint(uint64(uintptr(obj)))

+ dumpmemrange(obj, size)

+ dumpfields(bv)

+}

+

+func dumpotherroot(description string, to unsafe.Pointer) {

+ dumpint(tagOtherRoot)

+ dumpstr(description)

+ dumpint(uint64(uintptr(to)))

+}

+

+func dumpfinalizer(obj unsafe.Pointer, fn *funcval, ft *functype, ot *ptrtype) {

+ dumpint(tagFinalizer)

+ dumpint(uint64(uintptr(obj)))

+ dumpint(uint64(uintptr(unsafe.Pointer(fn))))

+ dumpint(uint64(uintptr(unsafe.Pointer(fn.fn))))

+ dumpint(uint64(uintptr(unsafe.Pointer(ft))))

+ dumpint(uint64(uintptr(unsafe.Pointer(ot))))

+}

+

+type childInfo struct {

+ // Information passed up from the callee frame about

+ // the layout of the outargs region.

+ argoff uintptr // where the arguments start in the frame

+ arglen uintptr // size of args region

+ args bitvector // if args.n >= 0, pointer map of args region

+ sp *uint8 // callee sp

+ depth uintptr // depth in call stack (0 == most recent)

+}

+

+// dump kinds & offsets of interesting fields in bv

+func dumpbv(cbv *bitvector, offset uintptr) {

+ bv := gobv(*cbv)

+ for i := uintptr(0); i < bv.n; i++ {

+ if bv.bytedata[i/8]>>(i%8)&1 == 1 {

+ dumpint(fieldKindPtr)

+ dumpint(uint64(offset + i*sys.PtrSize))

+ }

+ }

+}

+

+func dumpgoroutine(gp *g) {

+ sp := gp.syscallsp

+

+ dumpint(tagGoroutine)

+ dumpint(uint64(uintptr(unsafe.Pointer(gp))))

+ dumpint(uint64(sp))

+ dumpint(uint64(gp.goid))

+ dumpint(uint64(gp.gopc))

+ dumpint(uint64(readgstatus(gp)))

+ dumpbool(isSystemGoroutine(gp))

+ dumpbool(false) // isbackground

+ dumpint(uint64(gp.waitsince))

+ dumpstr(gp.waitreason)

+ dumpint(0)

+ dumpint(uint64(uintptr(unsafe.Pointer(gp.m))))

+ dumpint(uint64(uintptr(unsafe.Pointer(gp._defer))))

+ dumpint(uint64(uintptr(unsafe.Pointer(gp._panic))))

+

+ // dump defer & panic records

+ for d := gp._defer; d != nil; d = d.link {

+ dumpint(tagDefer)

+ dumpint(uint64(uintptr(unsafe.Pointer(d))))

+ dumpint(uint64(uintptr(unsafe.Pointer(gp))))

+ dumpint(0)

+ dumpint(0)

+ dumpint(uint64(uintptr(unsafe.Pointer(d.pfn))))

+ dumpint(0)

+ dumpint(uint64(uintptr(unsafe.Pointer(d.link))))

+ }

+ for p := gp._panic; p != nil; p = p.link {

+ dumpint(tagPanic)

+ dumpint(uint64(uintptr(unsafe.Pointer(p))))

+ dumpint(uint64(uintptr(unsafe.Pointer(gp))))

+ eface := efaceOf(&p.arg)

+ dumpint(uint64(uintptr(unsafe.Pointer(eface._type))))

+ dumpint(uint64(uintptr(unsafe.Pointer(eface.data))))

+ dumpint(0) // was p->defer, no longer recorded

+ dumpint(uint64(uintptr(unsafe.Pointer(p.link))))

+ }

+}

+

+func dumpgs() {

+ // goroutines & stacks

+ for i := 0; uintptr(i) < allglen; i++ {

+ gp := allgs[i]

+ status := readgstatus(gp) // The world is stopped so gp will not be in a scan state.

+ switch status {

+ default:

+ print("runtime: unexpected G.status ", hex(status), "\n")

+ throw("dumpgs in STW - bad status")

+ case _Gdead:

+ // ok

+ case _Grunnable,

+ _Gsyscall,

+ _Gwaiting:

+ dumpgoroutine(gp)

+ }

+ }

+}

+

+func finq_callback(fn *funcval, obj unsafe.Pointer, ft *functype, ot *ptrtype) {

+ dumpint(tagQueuedFinalizer)

+ dumpint(uint64(uintptr(obj)))

+ dumpint(uint64(uintptr(unsafe.Pointer(fn))))

+ dumpint(uint64(uintptr(unsafe.Pointer(fn.fn))))

+ dumpint(uint64(uintptr(unsafe.Pointer(ft))))

+ dumpint(uint64(uintptr(unsafe.Pointer(ot))))

+}

+

+func dumproots() {

+ // MSpan.types

+ for _, s := range mheap_.allspans {

+ if s.state == _MSpanInUse {

+ // Finalizers

+ for sp := s.specials; sp != nil; sp = sp.next {

+ if sp.kind != _KindSpecialFinalizer {

+ continue

+ }

+ spf := (*specialfinalizer)(unsafe.Pointer(sp))

+ p := unsafe.Pointer(s.base() + uintptr(spf.special.offset))

+ dumpfinalizer(p, spf.fn, spf.ft, spf.ot)

+ }

+ }

+ }

+

+ // Finalizer queue

+ iterate_finq(finq_callback)

+}

+

+// Bit vector of free marks.

+// Needs to be as big as the largest number of objects per span.

+var freemark [_PageSize / 8]bool

+

+func dumpobjs() {

+ for _, s := range mheap_.allspans {

+ if s.state != _MSpanInUse {

+ continue

+ }

+ p := s.base()

+ size := s.elemsize

+ n := (s.npages << _PageShift) / size

+ if n > uintptr(len(freemark)) {

+ throw("freemark array doesn't have enough entries")

+ }

+

+ for freeIndex := uintptr(0); freeIndex < s.nelems; freeIndex++ {

+ if s.isFree(freeIndex) {

+ freemark[freeIndex] = true

+ }

+ }

+

+ for j := uintptr(0); j < n; j, p = j+1, p+size {

+ if freemark[j] {

+ freemark[j] = false

+ continue

+ }

+ dumpobj(unsafe.Pointer(p), size, makeheapobjbv(p, size))

+ }

+ }

+}

+

+func dumpparams() {

+ dumpint(tagParams)

+ x := uintptr(1)

+ if *(*byte)(unsafe.Pointer(&x)) == 1 {

+ dumpbool(false) // little-endian ptrs

+ } else {

+ dumpbool(true) // big-endian ptrs

+ }

+ dumpint(sys.PtrSize)

+ dumpint(uint64(mheap_.arena_start))

+ dumpint(uint64(mheap_.arena_used))

+ dumpstr(sys.GOARCH)

+ dumpstr(sys.Goexperiment)

+ dumpint(uint64(ncpu))

+}

+

+func dumpms() {

+ for mp := allm; mp != nil; mp = mp.alllink {

+ dumpint(tagOSThread)

+ dumpint(uint64(uintptr(unsafe.Pointer(mp))))

+ dumpint(uint64(mp.id))

+ dumpint(mp.procid)

+ }

+}

+

+func dumpmemstats() {

+ dumpint(tagMemStats)

+ dumpint(memstats.alloc)

+ dumpint(memstats.total_alloc)

+ dumpint(memstats.sys)

+ dumpint(memstats.nlookup)

+ dumpint(memstats.nmalloc)

+ dumpint(memstats.nfree)

+ dumpint(memstats.heap_alloc)

+ dumpint(memstats.heap_sys)

+ dumpint(memstats.heap_idle)

+ dumpint(memstats.heap_inuse)

+ dumpint(memstats.heap_released)

+ dumpint(memstats.heap_objects)

+ dumpint(memstats.stacks_inuse)

+ dumpint(memstats.stacks_sys)

+ dumpint(memstats.mspan_inuse)

+ dumpint(memstats.mspan_sys)

+ dumpint(memstats.mcache_inuse)

+ dumpint(memstats.mcache_sys)

+ dumpint(memstats.buckhash_sys)

+ dumpint(memstats.gc_sys)

+ dumpint(memstats.other_sys)

+ dumpint(memstats.next_gc)

+ dumpint(memstats.last_gc)

+ dumpint(memstats.pause_total_ns)

+ for i := 0; i < 256; i++ {

+ dumpint(memstats.pause_ns[i])

+ }

+ dumpint(uint64(memstats.numgc))

+}

+

+func dumpmemprof_callback(b *bucket, nstk uintptr, pstk *location, size, allocs, frees uintptr) {

+ stk := (*[100000]location)(unsafe.Pointer(pstk))

+ dumpint(tagMemProf)

+ dumpint(uint64(uintptr(unsafe.Pointer(b))))

+ dumpint(uint64(size))

+ dumpint(uint64(nstk))

+ for i := uintptr(0); i < nstk; i++ {

+ pc := stk[i].pc

+ fn := stk[i].function

+ file := stk[i].filename

+ line := stk[i].lineno

+ if fn == "" {

+ var buf [64]byte

+ n := len(buf)

+ n--

+ buf[n] = ')'

+ if pc == 0 {

+ n--

+ buf[n] = '0'

+ } else {

+ for pc > 0 {

+ n--

+ buf[n] = "0123456789abcdef"[pc&15]

+ pc >>= 4

+ }

+ }

+ n--

+ buf[n] = 'x'

+ n--

+ buf[n] = '0'

+ n--

+ buf[n] = '('

+ dumpslice(buf[n:])

+ dumpstr("?")

+ dumpint(0)

+ } else {

+ dumpstr(fn)

+ dumpstr(file)

+ dumpint(uint64(line))

+ }

+ }

+ dumpint(uint64(allocs))

+ dumpint(uint64(frees))

+}

+

+func dumpmemprof() {

+ iterate_memprof(dumpmemprof_callback)

+ for _, s := range mheap_.allspans {

+ if s.state != _MSpanInUse {

+ continue

+ }

+ for sp := s.specials; sp != nil; sp = sp.next {

+ if sp.kind != _KindSpecialProfile {

+ continue

+ }

+ spp := (*specialprofile)(unsafe.Pointer(sp))

+ p := s.base() + uintptr(spp.special.offset)

+ dumpint(tagAllocSample)

+ dumpint(uint64(p))

+ dumpint(uint64(uintptr(unsafe.Pointer(spp.b))))

+ }

+ }

+}

+

+var dumphdr = []byte("go1.7 heap dump\n")

+

+func mdump() {

+ // make sure we're done sweeping

+ for _, s := range mheap_.allspans {

+ if s.state == _MSpanInUse {

+ s.ensureSwept()

+ }

+ }

+ memclrNoHeapPointers(unsafe.Pointer(&typecache), unsafe.Sizeof(typecache))

+ dwrite(unsafe.Pointer(&dumphdr[0]), uintptr(len(dumphdr)))

+ dumpparams()

+ dumpobjs()

+ dumpgs()

+ dumpms()

+ dumproots()

+ dumpmemstats()

+ dumpmemprof()

+ dumpint(tagEOF)

+ flush()

+}

+

+func writeheapdump_m(fd uintptr) {

+ _g_ := getg()

+ casgstatus(_g_.m.curg, _Grunning, _Gwaiting)

+ _g_.waitreason = "dumping heap"

+

+ // Update stats so we can dump them.

+ // As a side effect, flushes all the MCaches so the MSpan.freelist

+ // lists contain all the free objects.

+ updatememstats(nil)

+

+ // Set dump file.

+ dumpfd = fd

+

+ // Call dump routine.

+ mdump()

+

+ // Reset dump file.

+ dumpfd = 0

+ if tmpbuf != nil {

+ sysFree(unsafe.Pointer(&tmpbuf[0]), uintptr(len(tmpbuf)), &memstats.other_sys)

+ tmpbuf = nil

+ }

+

+ casgstatus(_g_.m.curg, _Gwaiting, _Grunning)

+}

+

+// dumpint() the kind & offset of each field in an object.

+func dumpfields(bv bitvector) {

+ dumpbv(&bv, 0)

+ dumpint(fieldKindEol)

+}

+

+// The heap dump reader needs to be able to disambiguate

+// Eface entries. So it needs to know every type that might

+// appear in such an entry. The following routine accomplishes that.

+// TODO(rsc, khr): Delete - no longer possible.

+

+// Dump all the types that appear in the type field of

+// any Eface described by this bit vector.

+func dumpbvtypes(bv *bitvector, base unsafe.Pointer) {

+}

+

+func makeheapobjbv(p uintptr, size uintptr) bitvector {

+ // Extend the temp buffer if necessary.

+ nptr := size / sys.PtrSize

+ if uintptr(len(tmpbuf)) < nptr/8+1 {

+ if tmpbuf != nil {

+ sysFree(unsafe.Pointer(&tmpbuf[0]), uintptr(len(tmpbuf)), &memstats.other_sys)

+ }

+ n := nptr/8 + 1

+ p := sysAlloc(n, &memstats.other_sys)

+ if p == nil {

+ throw("heapdump: out of memory")

+ }

+ tmpbuf = (*[1 << 30]byte)(p)[:n]

+ }

+ // Convert heap bitmap to pointer bitmap.

+ for i := uintptr(0); i < nptr/8+1; i++ {

+ tmpbuf[i] = 0

+ }

+ i := uintptr(0)

+ hbits := heapBitsForAddr(p)

+ for ; i < nptr; i++ {

+ if i != 1 && !hbits.morePointers() {

+ break // end of object

+ }

+ if hbits.isPointer() {

+ tmpbuf[i/8] |= 1 << (i % 8)

+ }

+ hbits = hbits.next()

+ }

+ return bitvector{int32(i), &tmpbuf[0]}

+}

+

+type gobitvector struct {

+ n uintptr

+ bytedata []uint8

+}

+

+func gobv(bv bitvector) gobitvector {

+ return gobitvector{

+ uintptr(bv.n),

+ (*[1 << 30]byte)(unsafe.Pointer(bv.bytedata))[:(bv.n+7)/8],

+ }

+}

+ if runtime.Compiler == "gccgo" {

+ t.Skip("does not work on gccgo without better escape analysis")

+ }

+

+ if runtime.Compiler == "gccgo" {

+ t.Skip("does not work on gccgo without better escape analysis")

+ }

+

+ gp := getg()

+ if gp != gp.m.g0 && gp.m.preemptoff != "" {

+ throw("notetsleep not on g0")

+ }

+// +build aix darwin nacl netbsd openbsd plan9 solaris windows

+ if gp != gp.m.g0 && gp.m.preemptoff != "" {

+ throw("notetsleep not on g0")

+ }

+// Copyright 2014 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// Memory allocator.

+//

+// This was originally based on tcmalloc, but has diverged quite a bit.

+// http://goog-perftools.sourceforge.net/doc/tcmalloc.html

+

+// The main allocator works in runs of pages.

+// Small allocation sizes (up to and including 32 kB) are

+// rounded to one of about 70 size classes, each of which

+// has its own free set of objects of exactly that size.

+// Any free page of memory can be split into a set of objects

+// of one size class, which are then managed using a free bitmap.

+//

+// The allocator's data structures are:

+//

+// fixalloc: a free-list allocator for fixed-size off-heap objects,

+// used to manage storage used by the allocator.

+// mheap: the malloc heap, managed at page (8192-byte) granularity.

+// mspan: a run of pages managed by the mheap.

+// mcentral: collects all spans of a given size class.

+// mcache: a per-P cache of mspans with free space.

+// mstats: allocation statistics.

+//

+// Allocating a small object proceeds up a hierarchy of caches:

+//

+// 1. Round the size up to one of the small size classes

+// and look in the corresponding mspan in this P's mcache.

+// Scan the mspan's free bitmap to find a free slot.

+// If there is a free slot, allocate it.

+// This can all be done without acquiring a lock.

+//

+// 2. If the mspan has no free slots, obtain a new mspan

+// from the mcentral's list of mspans of the required size

+// class that have free space.

+// Obtaining a whole span amortizes the cost of locking

+// the mcentral.

+//

+// 3. If the mcentral's mspan list is empty, obtain a run

+// of pages from the mheap to use for the mspan.

+//

+// 4. If the mheap is empty or has no page runs large enough,

+// allocate a new group of pages (at least 1MB) from the

+// operating system. Allocating a large run of pages

+// amortizes the cost of talking to the operating system.

+//

+// Sweeping an mspan and freeing objects on it proceeds up a similar

+// hierarchy:

+//

+// 1. If the mspan is being swept in response to allocation, it

+// is returned to the mcache to satisfy the allocation.

+//

+// 2. Otherwise, if the mspan still has allocated objects in it,

+// it is placed on the mcentral free list for the mspan's size

+// class.

+//

+// 3. Otherwise, if all objects in the mspan are free, the mspan

+// is now "idle", so it is returned to the mheap and no longer

+// has a size class.

+// This may coalesce it with adjacent idle mspans.

+//

+// 4. If an mspan remains idle for long enough, return its pages

+// to the operating system.

+//

+// Allocating and freeing a large object uses the mheap

+// directly, bypassing the mcache and mcentral.

+//

+// Free object slots in an mspan are zeroed only if mspan.needzero is

+// false. If needzero is true, objects are zeroed as they are

+// allocated. There are various benefits to delaying zeroing this way:

+//

+// 1. Stack frame allocation can avoid zeroing altogether.

+//

+// 2. It exhibits better temporal locality, since the program is

+// probably about to write to the memory.

+//

+// 3. We don't zero pages that never get reused.

+

+package runtime

+

+import (

+ "runtime/internal/sys"

+ "unsafe"

+)

+

+// C function to get the end of the program's memory.

+func getEnd() uintptr

+

+// For gccgo, use go:linkname to rename compiler-called functions to

+// themselves, so that the compiler will export them.

+//

+//go:linkname newobject runtime.newobject

+

+// Functions called by C code.

+//go:linkname mallocgc runtime.mallocgc

+

+const (

+ debugMalloc = false

+

+ maxTinySize = _TinySize

+ tinySizeClass = _TinySizeClass

+ maxSmallSize = _MaxSmallSize

+

+ pageShift = _PageShift

+ pageSize = _PageSize

+ pageMask = _PageMask

+ // By construction, single page spans of the smallest object class

+ // have the most objects per span.

+ maxObjsPerSpan = pageSize / 8

+

+ mSpanInUse = _MSpanInUse

+

+ concurrentSweep = _ConcurrentSweep

+

+ _PageSize = 1 << _PageShift

+ _PageMask = _PageSize - 1

+

+ // _64bit = 1 on 64-bit systems, 0 on 32-bit systems

+ _64bit = 1 << (^uintptr(0) >> 63) / 2

+

+ // Tiny allocator parameters, see "Tiny allocator" comment in malloc.go.

+ _TinySize = 16

+ _TinySizeClass = 2

+

+ _FixAllocChunk = 16 << 10 // Chunk size for FixAlloc

+ _MaxMHeapList = 1 << (20 - _PageShift) // Maximum page length for fixed-size list in MHeap.

+ _HeapAllocChunk = 1 << 20 // Chunk size for heap growth

+

+ // Per-P, per order stack segment cache size.

+ _StackCacheSize = 32 * 1024

+

+ // Number of orders that get caching. Order 0 is FixedStack

+ // and each successive order is twice as large.

+ // We want to cache 2KB, 4KB, 8KB, and 16KB stacks. Larger stacks

+ // will be allocated directly.

+ // Since FixedStack is different on different systems, we

+ // must vary NumStackOrders to keep the same maximum cached size.

+ // OS | FixedStack | NumStackOrders

+ // -----------------+------------+---------------

+ // linux/darwin/bsd | 2KB | 4

+ // windows/32 | 4KB | 3

+ // windows/64 | 8KB | 2

+ // plan9 | 4KB | 3

+ _NumStackOrders = 4 - sys.PtrSize/4*sys.GoosWindows - 1*sys.GoosPlan9

+

+ // Number of bits in page to span calculations (4k pages).

+ // On Windows 64-bit we limit the arena to 32GB or 35 bits.

+ // Windows counts memory used by page table into committed memory

+ // of the process, so we can't reserve too much memory.

+ // See https://golang.org/issue/5402 and https://golang.org/issue/5236.

+ // On other 64-bit platforms, we limit the arena to 512GB, or 39 bits.

+ // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address.

+ // The only exception is mips32 which only has access to low 2GB of virtual memory.

+ // On Darwin/arm64, we cannot reserve more than ~5GB of virtual memory,

+ // but as most devices have less than 4GB of physical memory anyway, we

+ // try to be conservative here, and only ask for a 2GB heap.

+ _MHeapMap_TotalBits = (_64bit*sys.GoosWindows)*35 + (_64bit*(1-sys.GoosWindows)*(1-sys.GoosDarwin*sys.GoarchArm64))*39 + sys.GoosDarwin*sys.GoarchArm64*31 + (1-_64bit)*(32-(sys.GoarchMips+sys.GoarchMipsle))

+ _MHeapMap_Bits = _MHeapMap_TotalBits - _PageShift

+

+ _MaxMem = uintptr(1<<_MHeapMap_TotalBits - 1)

+

+ // Max number of threads to run garbage collection.

+ // 2, 3, and 4 are all plausible maximums depending

+ // on the hardware details of the machine. The garbage

+ // collector scales well to 32 cpus.

+ _MaxGcproc = 32

+

+ _MaxArena32 = 1<<32 - 1

+

+ // minLegalPointer is the smallest possible legal pointer.

+ // This is the smallest possible architectural page size,

+ // since we assume that the first page is never mapped.

+ //

+ // This should agree with minZeroPage in the compiler.

+ minLegalPointer uintptr = 4096

+)

+

+// physPageSize is the size in bytes of the OS's physical pages.

+// Mapping and unmapping operations must be done at multiples of

+// physPageSize.

+//

+// This must be set by the OS init code (typically in osinit) before

+// mallocinit.

+var physPageSize uintptr

+

+// OS-defined helpers:

+//

+// sysAlloc obtains a large chunk of zeroed memory from the

+// operating system, typically on the order of a hundred kilobytes

+// or a megabyte.

+// NOTE: sysAlloc returns OS-aligned memory, but the heap allocator

+// may use larger alignment, so the caller must be careful to realign the

+// memory obtained by sysAlloc.

+//

+// SysUnused notifies the operating system that the contents

+// of the memory region are no longer needed and can be reused

+// for other purposes.

+// SysUsed notifies the operating system that the contents

+// of the memory region are needed again.

+//

+// SysFree returns it unconditionally; this is only used if

+// an out-of-memory error has been detected midway through

+// an allocation. It is okay if SysFree is a no-op.

+//

+// SysReserve reserves address space without allocating memory.

+// If the pointer passed to it is non-nil, the caller wants the

+// reservation there, but SysReserve can still choose another

+// location if that one is unavailable. On some systems and in some

+// cases SysReserve will simply check that the address space is

+// available and not actually reserve it. If SysReserve returns

+// non-nil, it sets *reserved to true if the address space is

+// reserved, false if it has merely been checked.

+// NOTE: SysReserve returns OS-aligned memory, but the heap allocator

+// may use larger alignment, so the caller must be careful to realign the

+// memory obtained by sysAlloc.

+//

+// SysMap maps previously reserved address space for use.

+// The reserved argument is true if the address space was really

+// reserved, not merely checked.

+//

+// SysFault marks a (already sysAlloc'd) region to fault

+// if accessed. Used only for debugging the runtime.

+

+func mallocinit() {

+ if class_to_size[_TinySizeClass] != _TinySize {

+ throw("bad TinySizeClass")

+ }

+

+ // Not used for gccgo.

+ // testdefersizes()

+

+ // Copy class sizes out for statistics table.

+ for i := range class_to_size {

+ memstats.by_size[i].size = uint32(class_to_size[i])

+ }

+

+ // Check physPageSize.

+ if physPageSize == 0 {

+ // The OS init code failed to fetch the physical page size.

+ throw("failed to get system page size")

+ }

+ if physPageSize < minPhysPageSize {

+ print("system page size (", physPageSize, ") is smaller than minimum page size (", minPhysPageSize, ")\n")

+ throw("bad system page size")

+ }

+ if physPageSize&(physPageSize-1) != 0 {

+ print("system page size (", physPageSize, ") must be a power of 2\n")

+ throw("bad system page size")

+ }

+

+ var p, bitmapSize, spansSize, pSize, limit uintptr

+ var reserved bool

+

+ // limit = runtime.memlimit();

+ // See https://golang.org/issue/5049

+ // TODO(rsc): Fix after 1.1.

+ limit = 0

+

+ // Set up the allocation arena, a contiguous area of memory where

+ // allocated data will be found. The arena begins with a bitmap large

+ // enough to hold 2 bits per allocated word.

+ if sys.PtrSize == 8 && (limit == 0 || limit > 1<<30) {

+ // On a 64-bit machine, allocate from a single contiguous reservation.

+ // 512 GB (MaxMem) should be big enough for now.

+ //

+ // The code will work with the reservation at any address, but ask

+ // SysReserve to use 0x0000XXc000000000 if possible (XX=00...7f).

+ // Allocating a 512 GB region takes away 39 bits, and the amd64

+ // doesn't let us choose the top 17 bits, so that leaves the 9 bits

+ // in the middle of 0x00c0 for us to choose. Choosing 0x00c0 means

+ // that the valid memory addresses will begin 0x00c0, 0x00c1, ..., 0x00df.

+ // In little-endian, that's c0 00, c1 00, ..., df 00. None of those are valid

+ // UTF-8 sequences, and they are otherwise as far away from

+ // ff (likely a common byte) as possible. If that fails, we try other 0xXXc0

+ // addresses. An earlier attempt to use 0x11f8 caused out of memory errors

+ // on OS X during thread allocations. 0x00c0 causes conflicts with

+ // AddressSanitizer which reserves all memory up to 0x0100.

+ // These choices are both for debuggability and to reduce the

+ // odds of a conservative garbage collector (as is still used in gccgo)

+ // not collecting memory because some non-pointer block of memory

+ // had a bit pattern that matched a memory address.

+ //

+ // Actually we reserve 544 GB (because the bitmap ends up being 32 GB)

+ // but it hardly matters: e0 00 is not valid UTF-8 either.

+ //

+ // If this fails we fall back to the 32 bit memory mechanism

+ //

+ // However, on arm64, we ignore all this advice above and slam the

+ // allocation at 0x40 << 32 because when using 4k pages with 3-level

+ // translation buffers, the user address space is limited to 39 bits

+ // On darwin/arm64, the address space is even smaller.

+ arenaSize := round(_MaxMem, _PageSize)

+ bitmapSize = arenaSize / (sys.PtrSize * 8 / 2)

+ spansSize = arenaSize / _PageSize * sys.PtrSize

+ spansSize = round(spansSize, _PageSize)

+ for i := 0; i <= 0x7f; i++ {

+ switch {

+ case GOARCH == "arm64" && GOOS == "darwin":

+ p = uintptr(i)<<40 | uintptrMask&(0x0013<<28)

+ case GOARCH == "arm64":

+ p = uintptr(i)<<40 | uintptrMask&(0x0040<<32)

+ default:

+ p = uintptr(i)<<40 | uintptrMask&(0x00c0<<32)

+ }

+ pSize = bitmapSize + spansSize + arenaSize + _PageSize

+ p = uintptr(sysReserve(unsafe.Pointer(p), pSize, &reserved))

+ if p != 0 {

+ break

+ }

+ }

+ }

+

+ if p == 0 {

+ // On a 32-bit machine, we can't typically get away

+ // with a giant virtual address space reservation.

+ // Instead we map the memory information bitmap

+ // immediately after the data segment, large enough

+ // to handle the entire 4GB address space (256 MB),

+ // along with a reservation for an initial arena.

+ // When that gets used up, we'll start asking the kernel

+ // for any memory anywhere.

+

+ // If we fail to allocate, try again with a smaller arena.

+ // This is necessary on Android L where we share a process

+ // with ART, which reserves virtual memory aggressively.

+ // In the worst case, fall back to a 0-sized initial arena,

+ // in the hope that subsequent reservations will succeed.

+ arenaSizes := [...]uintptr{

+ 512 << 20,

+ 256 << 20,

+ 128 << 20,

+ 0,

+ }

+

+ for _, arenaSize := range &arenaSizes {

+ bitmapSize = (_MaxArena32 + 1) / (sys.PtrSize * 8 / 2)

+ spansSize = (_MaxArena32 + 1) / _PageSize * sys.PtrSize

+ if limit > 0 && arenaSize+bitmapSize+spansSize > limit {

+ bitmapSize = (limit / 9) &^ ((1 << _PageShift) - 1)

+ arenaSize = bitmapSize * 8

+ spansSize = arenaSize / _PageSize * sys.PtrSize

+ }

+ spansSize = round(spansSize, _PageSize)

+

+ // SysReserve treats the address we ask for, end, as a hint,

+ // not as an absolute requirement. If we ask for the end

+ // of the data segment but the operating system requires

+ // a little more space before we can start allocating, it will

+ // give out a slightly higher pointer. Except QEMU, which

+ // is buggy, as usual: it won't adjust the pointer upward.

+ // So adjust it upward a little bit ourselves: 1/4 MB to get

+ // away from the running binary image and then round up

+ // to a MB boundary.

+ p = round(getEnd()+(1<<18), 1<<20)

+ pSize = bitmapSize + spansSize + arenaSize + _PageSize

+ p = uintptr(sysReserve(unsafe.Pointer(p), pSize, &reserved))

+ if p != 0 {

+ break

+ }

+ }

+ if p == 0 {

+ throw("runtime: cannot reserve arena virtual address space")

+ }

+ }

+

+ // PageSize can be larger than OS definition of page size,

+ // so SysReserve can give us a PageSize-unaligned pointer.

+ // To overcome this we ask for PageSize more and round up the pointer.

+ p1 := round(p, _PageSize)

+

+ spansStart := p1

+ mheap_.bitmap = p1 + spansSize + bitmapSize

+ if sys.PtrSize == 4 {

+ // Set arena_start such that we can accept memory

+ // reservations located anywhere in the 4GB virtual space.

+ mheap_.arena_start = 0

+ } else {

+ mheap_.arena_start = p1 + (spansSize + bitmapSize)

+ }

+ mheap_.arena_end = p + pSize

+ mheap_.arena_used = p1 + (spansSize + bitmapSize)

+ mheap_.arena_reserved = reserved

+

+ if mheap_.arena_start&(_PageSize-1) != 0 {

+ println("bad pagesize", hex(p), hex(p1), hex(spansSize), hex(bitmapSize), hex(_PageSize), "start", hex(mheap_.arena_start))

+ throw("misrounded allocation in mallocinit")

+ }

+

+ // Initialize the rest of the allocator.

+ mheap_.init(spansStart, spansSize)

+ _g_ := getg()

+ _g_.m.mcache = allocmcache()

+}

+

+// sysAlloc allocates the next n bytes from the heap arena. The

+// returned pointer is always _PageSize aligned and between

+// h.arena_start and h.arena_end. sysAlloc returns nil on failure.

+// There is no corresponding free function.

+func (h *mheap) sysAlloc(n uintptr) unsafe.Pointer {

+ if n > h.arena_end-h.arena_used {

+ // We are in 32-bit mode, maybe we didn't use all possible address space yet.

+ // Reserve some more space.

+ p_size := round(n+_PageSize, 256<<20)

+ new_end := h.arena_end + p_size // Careful: can overflow

+ if h.arena_end <= new_end && new_end-h.arena_start-1 <= _MaxArena32 {

+ // TODO: It would be bad if part of the arena

+ // is reserved and part is not.

+ var reserved bool

+ p := uintptr(sysReserve(unsafe.Pointer(h.arena_end), p_size, &reserved))

+ if p == 0 {

+ return nil

+ }

+ if p == h.arena_end {

+ h.arena_end = new_end

+ h.arena_reserved = reserved

+ } else if h.arena_start <= p && p+p_size-h.arena_start-1 <= _MaxArena32 {

+ // Keep everything page-aligned.

+ // Our pages are bigger than hardware pages.

+ h.arena_end = p + p_size

+ used := p + (-p & (_PageSize - 1))

+ h.mapBits(used)

+ h.mapSpans(used)

+ h.arena_used = used

+ h.arena_reserved = reserved

+ } else {

+ // We haven't added this allocation to

+ // the stats, so subtract it from a

+ // fake stat (but avoid underflow).

+ stat := uint64(p_size)

+ sysFree(unsafe.Pointer(p), p_size, &stat)

+ }

+ }

+ }

+

+ if n <= h.arena_end-h.arena_used {

+ // Keep taking from our reservation.

+ p := h.arena_used

+ sysMap(unsafe.Pointer(p), n, h.arena_reserved, &memstats.heap_sys)

+ h.mapBits(p + n)

+ h.mapSpans(p + n)

+ h.arena_used = p + n

+ if raceenabled {

+ racemapshadow(unsafe.Pointer(p), n)

+ }

+

+ if p&(_PageSize-1) != 0 {

+ throw("misrounded allocation in MHeap_SysAlloc")

+ }

+ return unsafe.Pointer(p)

+ }

+

+ // If using 64-bit, our reservation is all we have.

+ if h.arena_end-h.arena_start > _MaxArena32 {

+ return nil

+ }

+

+ // On 32-bit, once the reservation is gone we can

+ // try to get memory at a location chosen by the OS.

+ p_size := round(n, _PageSize) + _PageSize

+ p := uintptr(sysAlloc(p_size, &memstats.heap_sys))

+ if p == 0 {

+ return nil

+ }

+

+ if p < h.arena_start || p+p_size-h.arena_start > _MaxArena32 {

+ top := ^uintptr(0)

+ if top-h.arena_start-1 > _MaxArena32 {

+ top = h.arena_start + _MaxArena32 + 1

+ }

+ print("runtime: memory allocated by OS (", hex(p), ") not in usable range [", hex(h.arena_start), ",", hex(top), ")\n")

+ sysFree(unsafe.Pointer(p), p_size, &memstats.heap_sys)

+ return nil

+ }

+

+ p_end := p + p_size

+ p += -p & (_PageSize - 1)

+ if p+n > h.arena_used {

+ h.mapBits(p + n)

+ h.mapSpans(p + n)

+ h.arena_used = p + n

+ if p_end > h.arena_end {

+ h.arena_end = p_end

+ }

+ if raceenabled {

+ racemapshadow(unsafe.Pointer(p), n)

+ }

+ }

+

+ if p&(_PageSize-1) != 0 {

+ throw("misrounded allocation in MHeap_SysAlloc")

+ }

+ return unsafe.Pointer(p)

+}

+

+// base address for all 0-byte allocations

+var zerobase uintptr

+

+// nextFreeFast returns the next free object if one is quickly available.

+// Otherwise it returns 0.

+func nextFreeFast(s *mspan) gclinkptr {

+ theBit := sys.Ctz64(s.allocCache) // Is there a free object in the allocCache?

+ if theBit < 64 {

+ result := s.freeindex + uintptr(theBit)

+ if result < s.nelems {

+ freeidx := result + 1

+ if freeidx%64 == 0 && freeidx != s.nelems {

+ return 0

+ }

+ s.allocCache >>= (theBit + 1)

+ s.freeindex = freeidx

+ v := gclinkptr(result*s.elemsize + s.base())

+ s.allocCount++

+ return v

+ }

+ }

+ return 0

+}

+

+// nextFree returns the next free object from the cached span if one is available.

+// Otherwise it refills the cache with a span with an available object and

+// returns that object along with a flag indicating that this was a heavy

+// weight allocation. If it is a heavy weight allocation the caller must

+// determine whether a new GC cycle needs to be started or if the GC is active

+// whether this goroutine needs to assist the GC.

+func (c *mcache) nextFree(sizeclass uint8) (v gclinkptr, s *mspan, shouldhelpgc bool) {

+ s = c.alloc[sizeclass]

+ shouldhelpgc = false

+ freeIndex := s.nextFreeIndex()

+ if freeIndex == s.nelems {

+ // The span is full.

+ if uintptr(s.allocCount) != s.nelems {

+ println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems)

+ throw("s.allocCount != s.nelems && freeIndex == s.nelems")

+ }

+ systemstack(func() {

+ c.refill(int32(sizeclass))

+ })

+ shouldhelpgc = true

+ s = c.alloc[sizeclass]

+

+ freeIndex = s.nextFreeIndex()

+ }

+

+ if freeIndex >= s.nelems {

+ throw("freeIndex is not valid")

+ }

+

+ v = gclinkptr(freeIndex*s.elemsize + s.base())

+ s.allocCount++

+ if uintptr(s.allocCount) > s.nelems {

+ println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems)

+ throw("s.allocCount > s.nelems")

+ }

+ return

+}

+

+// Allocate an object of size bytes.

+// Small objects are allocated from the per-P cache's free lists.

+// Large objects (> 32 kB) are allocated straight from the heap.

+func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {

+ if gcphase == _GCmarktermination {

+ throw("mallocgc called with gcphase == _GCmarktermination")

+ }

+

+ if size == 0 {

+ return unsafe.Pointer(&zerobase)

+ }

+

+ if debug.sbrk != 0 {

+ align := uintptr(16)

+ if typ != nil {

+ align = uintptr(typ.align)

+ }

+ return persistentalloc(size, align, &memstats.other_sys)

+ }

+

+ // When using gccgo, when a cgo or SWIG function has an

+ // interface return type and the function returns a

+ // non-pointer, memory allocation occurs after syscall.Cgocall

+ // but before syscall.CgocallDone. Treat this allocation as a

+ // callback.

+ incallback := false

+ if gomcache() == nil && getg().m.ncgo > 0 {

+ exitsyscall(0)

+ incallback = true

+ }

+

+ // assistG is the G to charge for this allocation, or nil if

+ // GC is not currently active.

+ var assistG *g

+ if gcBlackenEnabled != 0 {

+ // Charge the current user G for this allocation.

+ assistG = getg()

+ if assistG.m.curg != nil {

+ assistG = assistG.m.curg

+ }

+ // Charge the allocation against the G. We'll account

+ // for internal fragmentation at the end of mallocgc.

+ assistG.gcAssistBytes -= int64(size)

+

+ if assistG.gcAssistBytes < 0 {

+ // This G is in debt. Assist the GC to correct

+ // this before allocating. This must happen

+ // before disabling preemption.

+ gcAssistAlloc(assistG)

+ }

+ }

+

+ // Set mp.mallocing to keep from being preempted by GC.

+ mp := acquirem()

+ if mp.mallocing != 0 {

+ throw("malloc deadlock")

+ }

+ if mp.gsignal == getg() {

+ throw("malloc during signal")

+ }

+ mp.mallocing = 1

+

+ shouldhelpgc := false

+ dataSize := size

+ c := gomcache()

+ var x unsafe.Pointer

+ noscan := typ == nil || typ.kind&kindNoPointers != 0

+ if size <= maxSmallSize {

+ if noscan && size < maxTinySize {

+ // Tiny allocator.

+ //

+ // Tiny allocator combines several tiny allocation requests

+ // into a single memory block. The resulting memory block

+ // is freed when all subobjects are unreachable. The subobjects

+ // must be noscan (don't have pointers), this ensures that

+ // the amount of potentially wasted memory is bounded.

+ //

+ // Size of the memory block used for combining (maxTinySize) is tunable.

+ // Current setting is 16 bytes, which relates to 2x worst case memory

+ // wastage (when all but one subobjects are unreachable).

+ // 8 bytes would result in no wastage at all, but provides less

+ // opportunities for combining.

+ // 32 bytes provides more opportunities for combining,

+ // but can lead to 4x worst case wastage.

+ // The best case winning is 8x regardless of block size.

+ //

+ // Objects obtained from tiny allocator must not be freed explicitly.

+ // So when an object will be freed explicitly, we ensure that

+ // its size >= maxTinySize.

+ //

+ // SetFinalizer has a special case for objects potentially coming

+ // from tiny allocator, it such case it allows to set finalizers

+ // for an inner byte of a memory block.

+ //

+ // The main targets of tiny allocator are small strings and

+ // standalone escaping variables. On a json benchmark

+ // the allocator reduces number of allocations by ~12% and

+ // reduces heap size by ~20%.

+ off := c.tinyoffset

+ // Align tiny pointer for required (conservative) alignment.

+ if size&7 == 0 {

+ off = round(off, 8)

+ } else if size&3 == 0 {

+ off = round(off, 4)

+ } else if size&1 == 0 {

+ off = round(off, 2)

+ }

+ if off+size <= maxTinySize && c.tiny != 0 {

+ // The object fits into existing tiny block.

+ x = unsafe.Pointer(c.tiny + off)

+ c.tinyoffset = off + size

+ c.local_tinyallocs++

+ mp.mallocing = 0

+ releasem(mp)

+ if incallback {

+ entersyscall(0)

+ }

+ return x

+ }

+ // Allocate a new maxTinySize block.

+ span := c.alloc[tinySizeClass]

+ v := nextFreeFast(span)

+ if v == 0 {

+ v, _, shouldhelpgc = c.nextFree(tinySizeClass)

+ }

+ x = unsafe.Pointer(v)

+ (*[2]uint64)(x)[0] = 0

+ (*[2]uint64)(x)[1] = 0

+ // See if we need to replace the existing tiny block with the new one

+ // based on amount of remaining free space.

+ if size < c.tinyoffset || c.tiny == 0 {

+ c.tiny = uintptr(x)

+ c.tinyoffset = size

+ }

+ size = maxTinySize

+ } else {

+ var sizeclass uint8

+ if size <= smallSizeMax-8 {

+ sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]

+ } else {

+ sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]

+ }

+ size = uintptr(class_to_size[sizeclass])

+ span := c.alloc[sizeclass]

+ v := nextFreeFast(span)

+ if v == 0 {

+ v, span, shouldhelpgc = c.nextFree(sizeclass)

+ }

+ x = unsafe.Pointer(v)

+ if needzero && span.needzero != 0 {

+ memclrNoHeapPointers(unsafe.Pointer(v), size)

+ }

+ }

+ } else {

+ var s *mspan

+ shouldhelpgc = true

+ systemstack(func() {

+ s = largeAlloc(size, needzero)

+ })

+ s.freeindex = 1

+ s.allocCount = 1

+ x = unsafe.Pointer(s.base())

+ size = s.elemsize

+ }

+

+ var scanSize uintptr

+ if noscan {

+ heapBitsSetTypeNoScan(uintptr(x))

+ } else {

+ heapBitsSetType(uintptr(x), size, dataSize, typ)

+ if dataSize > typ.size {

+ // Array allocation. If there are any

+ // pointers, GC has to scan to the last

+ // element.

+ if typ.ptrdata != 0 {

+ scanSize = dataSize - typ.size + typ.ptrdata

+ }

+ } else {

+ scanSize = typ.ptrdata

+ }

+ c.local_scan += scanSize

+ }

+

+ // Ensure that the stores above that initialize x to

+ // type-safe memory and set the heap bits occur before

+ // the caller can make x observable to the garbage

+ // collector. Otherwise, on weakly ordered machines,

+ // the garbage collector could follow a pointer to x,

+ // but see uninitialized memory or stale heap bits.

+ publicationBarrier()

+

+ // Allocate black during GC.

+ // All slots hold nil so no scanning is needed.

+ // This may be racing with GC so do it atomically if there can be

+ // a race marking the bit.

+ if gcphase != _GCoff {

+ gcmarknewobject(uintptr(x), size, scanSize)

+ }

+

+ if raceenabled {

+ racemalloc(x, size)

+ }

+

+ if msanenabled {

+ msanmalloc(x, size)

+ }

+

+ mp.mallocing = 0

+ releasem(mp)

+

+ if debug.allocfreetrace != 0 {

+ tracealloc(x, size, typ)

+ }

+

+ if rate := MemProfileRate; rate > 0 {

+ if size < uintptr(rate) && int32(size) < c.next_sample {

+ c.next_sample -= int32(size)

+ } else {

+ mp := acquirem()

+ profilealloc(mp, x, size)

+ releasem(mp)

+ }

+ }

+

+ if assistG != nil {

+ // Account for internal fragmentation in the assist

+ // debt now that we know it.

+ assistG.gcAssistBytes -= int64(size - dataSize)

+ }

+

+ if shouldhelpgc && gcShouldStart(false) {

+ gcStart(gcBackgroundMode, false)

+ }

+

+ if getg().preempt {

+ checkPreempt()

+ }

+

+ if incallback {

+ entersyscall(0)

+ }

+

+ return x

+}

+

+func largeAlloc(size uintptr, needzero bool) *mspan {

+ // print("largeAlloc size=", size, "\n")

+

+ if size+_PageSize < size {

+ throw("out of memory")

+ }

+ npages := size >> _PageShift

+ if size&_PageMask != 0 {

+ npages++

+ }

+

+ // Deduct credit for this span allocation and sweep if

+ // necessary. mHeap_Alloc will also sweep npages, so this only

+ // pays the debt down to npage pages.

+ deductSweepCredit(npages*_PageSize, npages)

+

+ s := mheap_.alloc(npages, 0, true, needzero)

+ if s == nil {

+ throw("out of memory")

+ }

+ s.limit = s.base() + size

+ heapBitsForSpan(s.base()).initSpan(s)

+ return s

+}

+

+// implementation of new builtin

+// compiler (both frontend and SSA backend) knows the signature

+// of this function

+func newobject(typ *_type) unsafe.Pointer {

+ return mallocgc(typ.size, typ, true)

+}

+

+//go:linkname reflect_unsafe_New reflect.unsafe_New

+func reflect_unsafe_New(typ *_type) unsafe.Pointer {

+ return newobject(typ)

+}

+

+// newarray allocates an array of n elements of type typ.

+func newarray(typ *_type, n int) unsafe.Pointer {

+ if n < 0 || uintptr(n) > maxSliceCap(typ.size) {

+ panic(plainError("runtime: allocation size out of range"))

+ }

+ return mallocgc(typ.size*uintptr(n), typ, true)

+}

+

+//go:linkname reflect_unsafe_NewArray reflect.unsafe_NewArray

+func reflect_unsafe_NewArray(typ *_type, n int) unsafe.Pointer {

+ return newarray(typ, n)

+}

+

+func profilealloc(mp *m, x unsafe.Pointer, size uintptr) {

+ mp.mcache.next_sample = nextSample()

+ mProf_Malloc(x, size)

+}

+

+// nextSample returns the next sampling point for heap profiling.

+// It produces a random variable with a geometric distribution and

+// mean MemProfileRate. This is done by generating a uniformly

+// distributed random number and applying the cumulative distribution

+// function for an exponential.

+func nextSample() int32 {

+ if GOOS == "plan9" {

+ // Plan 9 doesn't support floating point in note handler.

+ if g := getg(); g == g.m.gsignal {

+ return nextSampleNoFP()

+ }

+ }

+

+ period := MemProfileRate

+

+ // make nextSample not overflow. Maximum possible step is

+ // -ln(1/(1<<kRandomBitCount)) * period, approximately 20 * period.

+ switch {

+ case period > 0x7000000:

+ period = 0x7000000

+ case period == 0:

+ return 0

+ }

+

+ // Let m be the sample rate,

+ // the probability distribution function is m*exp(-mx), so the CDF is

+ // p = 1 - exp(-mx), so

+ // q = 1 - p == exp(-mx)

+ // log_e(q) = -mx

+ // -log_e(q)/m = x

+ // x = -log_e(q) * period

+ // x = log_2(q) * (-log_e(2)) * period ; Using log_2 for efficiency

+ const randomBitCount = 26

+ q := fastrand()%(1<<randomBitCount) + 1

+ qlog := fastlog2(float64(q)) - randomBitCount

+ if qlog > 0 {

+ qlog = 0

+ }

+ const minusLog2 = -0.6931471805599453 // -ln(2)

+ return int32(qlog*(minusLog2*float64(period))) + 1

+}

+

+// nextSampleNoFP is similar to nextSample, but uses older,

+// simpler code to avoid floating point.

+func nextSampleNoFP() int32 {

+ // Set first allocation sample size.

+ rate := MemProfileRate

+ if rate > 0x3fffffff { // make 2*rate not overflow

+ rate = 0x3fffffff

+ }

+ if rate != 0 {

+ return int32(int(fastrand()) % (2 * rate))

+ }

+ return 0

+}

+

+type persistentAlloc struct {

+ base unsafe.Pointer

+ off uintptr

+}

+

+var globalAlloc struct {

+ mutex

+ persistentAlloc

+}

+

+// Wrapper around sysAlloc that can allocate small chunks.

+// There is no associated free operation.

+// Intended for things like function/type/debug-related persistent data.

+// If align is 0, uses default align (currently 8).

+// The returned memory will be zeroed.

+//

+// Consider marking persistentalloc'd types go:notinheap.

+func persistentalloc(size, align uintptr, sysStat *uint64) unsafe.Pointer {

+ var p unsafe.Pointer

+ systemstack(func() {

+ p = persistentalloc1(size, align, sysStat)

+ })

+ return p

+}

+

+// Must run on system stack because stack growth can (re)invoke it.

+// See issue 9174.

+//go:systemstack

+func persistentalloc1(size, align uintptr, sysStat *uint64) unsafe.Pointer {

+ const (

+ chunk = 256 << 10

+ maxBlock = 64 << 10 // VM reservation granularity is 64K on windows

+ )

+

+ if size == 0 {

+ throw("persistentalloc: size == 0")

+ }

+ if align != 0 {

+ if align&(align-1) != 0 {

+ throw("persistentalloc: align is not a power of 2")

+ }

+ if align > _PageSize {

+ throw("persistentalloc: align is too large")

+ }

+ } else {

+ align = 8

+ }

+

+ if size >= maxBlock {

+ return sysAlloc(size, sysStat)

+ }

+

+ mp := acquirem()

+ var persistent *persistentAlloc

+ if mp != nil && mp.p != 0 {

+ persistent = &mp.p.ptr().palloc

+ } else {

+ lock(&globalAlloc.mutex)

+ persistent = &globalAlloc.persistentAlloc

+ }

+ persistent.off = round(persistent.off, align)

+ if persistent.off+size > chunk || persistent.base == nil {

+ persistent.base = sysAlloc(chunk, &memstats.other_sys)

+ if persistent.base == nil {

+ if persistent == &globalAlloc.persistentAlloc {

+ unlock(&globalAlloc.mutex)

+ }

+ throw("runtime: cannot allocate memory")

+ }

+ persistent.off = 0

+ }

+ p := add(persistent.base, persistent.off)

+ persistent.off += size

+ releasem(mp)

+ if persistent == &globalAlloc.persistentAlloc {

+ unlock(&globalAlloc.mutex)

+ }

+

+ if sysStat != &memstats.other_sys {

+ mSysStatInc(sysStat, size)

+ mSysStatDec(&memstats.other_sys, size)

+ }

+ return p

+}

+// Copyright 2015 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// Garbage collector: write barriers.

+//

+// For the concurrent garbage collector, the Go compiler implements

+// updates to pointer-valued fields that may be in heap objects by

+// emitting calls to write barriers. This file contains the actual write barrier

+// implementation, gcmarkwb_m, and the various wrappers called by the

+// compiler to implement pointer assignment, slice assignment,

+// typed memmove, and so on.

+

+package runtime

+

+import (

+ "runtime/internal/sys"

+ "unsafe"

+)

+

+// For gccgo, use go:linkname to rename compiler-called functions to

+// themselves, so that the compiler will export them.

+//

+//go:linkname writebarrierptr runtime.writebarrierptr

+//go:linkname typedmemmove runtime.typedmemmove

+//go:linkname typedslicecopy runtime.typedslicecopy

+

+// gcmarkwb_m is the mark-phase write barrier, the only barrier we have.

+// The rest of this file exists only to make calls to this function.

+//

+// This is a hybrid barrier that combines a Yuasa-style deletion

+// barrier—which shades the object whose reference is being

+// overwritten—with Dijkstra insertion barrier—which shades the object

+// whose reference is being written. The insertion part of the barrier

+// is necessary while the calling goroutine's stack is grey. In

+// pseudocode, the barrier is:

+//

+// writePointer(slot, ptr):

+// shade(*slot)

+// if current stack is grey:

+// shade(ptr)

+// *slot = ptr

+//

+// slot is the destination in Go code.

+// ptr is the value that goes into the slot in Go code.

+//

+// Shade indicates that it has seen a white pointer by adding the referent

+// to wbuf as well as marking it.

+//

+// The two shades and the condition work together to prevent a mutator

+// from hiding an object from the garbage collector:

+//

+// 1. shade(*slot) prevents a mutator from hiding an object by moving

+// the sole pointer to it from the heap to its stack. If it attempts

+// to unlink an object from the heap, this will shade it.

+//

+// 2. shade(ptr) prevents a mutator from hiding an object by moving

+// the sole pointer to it from its stack into a black object in the

+// heap. If it attempts to install the pointer into a black object,

+// this will shade it.

+//

+// 3. Once a goroutine's stack is black, the shade(ptr) becomes

+// unnecessary. shade(ptr) prevents hiding an object by moving it from

+// the stack to the heap, but this requires first having a pointer

+// hidden on the stack. Immediately after a stack is scanned, it only

+// points to shaded objects, so it's not hiding anything, and the

+// shade(*slot) prevents it from hiding any other pointers on its

+// stack.

+//

+// For a detailed description of this barrier and proof of

+// correctness, see https://github.com/golang/proposal/blob/master/design/17503-eliminate-rescan.md

+//

+//

+//

+// Dealing with memory ordering:

+//

+// Both the Yuasa and Dijkstra barriers can be made conditional on the

+// color of the object containing the slot. We chose not to make these

+// conditional because the cost of ensuring that the object holding

+// the slot doesn't concurrently change color without the mutator

+// noticing seems prohibitive.

+//

+// Consider the following example where the mutator writes into

+// a slot and then loads the slot's mark bit while the GC thread

+// writes to the slot's mark bit and then as part of scanning reads

+// the slot.

+//

+// Initially both [slot] and [slotmark] are 0 (nil)

+// Mutator thread GC thread

+// st [slot], ptr st [slotmark], 1

+//

+// ld r1, [slotmark] ld r2, [slot]

+//

+// Without an expensive memory barrier between the st and the ld, the final

+// result on most HW (including 386/amd64) can be r1==r2==0. This is a classic

+// example of what can happen when loads are allowed to be reordered with older

+// stores (avoiding such reorderings lies at the heart of the classic

+// Peterson/Dekker algorithms for mutual exclusion). Rather than require memory

+// barriers, which will slow down both the mutator and the GC, we always grey

+// the ptr object regardless of the slot's color.

+//

+// Another place where we intentionally omit memory barriers is when

+// accessing mheap_.arena_used to check if a pointer points into the

+// heap. On relaxed memory machines, it's possible for a mutator to

+// extend the size of the heap by updating arena_used, allocate an

+// object from this new region, and publish a pointer to that object,

+// but for tracing running on another processor to observe the pointer

+// but use the old value of arena_used. In this case, tracing will not

+// mark the object, even though it's reachable. However, the mutator

+// is guaranteed to execute a write barrier when it publishes the

+// pointer, so it will take care of marking the object. A general

+// consequence of this is that the garbage collector may cache the

+// value of mheap_.arena_used. (See issue #9984.)

+//

+//

+// Stack writes:

+//

+// The compiler omits write barriers for writes to the current frame,

+// but if a stack pointer has been passed down the call stack, the

+// compiler will generate a write barrier for writes through that

+// pointer (because it doesn't know it's not a heap pointer).

+//

+// One might be tempted to ignore the write barrier if slot points

+// into to the stack. Don't do it! Mark termination only re-scans

+// frames that have potentially been active since the concurrent scan,

+// so it depends on write barriers to track changes to pointers in

+// stack frames that have not been active.

+//

+//

+// Global writes:

+//

+// The Go garbage collector requires write barriers when heap pointers

+// are stored in globals. Many garbage collectors ignore writes to

+// globals and instead pick up global -> heap pointers during

+// termination. This increases pause time, so we instead rely on write

+// barriers for writes to globals so that we don't have to rescan

+// global during mark termination.

+//

+//

+// Publication ordering:

+//

+// The write barrier is *pre-publication*, meaning that the write

+// barrier happens prior to the *slot = ptr write that may make ptr

+// reachable by some goroutine that currently cannot reach it.

+//

+//

+//go:nowritebarrierrec

+//go:systemstack

+func gcmarkwb_m(slot *uintptr, ptr uintptr) {

+ if writeBarrier.needed {

+ // Note: This turns bad pointer writes into bad

+ // pointer reads, which could be confusing. We avoid

+ // reading from obviously bad pointers, which should

+ // take care of the vast majority of these. We could

+ // patch this up in the signal handler, or use XCHG to

+ // combine the read and the write. Checking inheap is

+ // insufficient since we need to track changes to

+ // roots outside the heap.

+ if slot1 := uintptr(unsafe.Pointer(slot)); slot1 >= minPhysPageSize {

+ if optr := *slot; optr != 0 {

+ shade(optr)

+ }

+ }

+ // TODO: Make this conditional on the caller's stack color.

+ if ptr != 0 && inheap(ptr) {

+ shade(ptr)

+ }

+ }

+}

+

+// writebarrierptr_prewrite1 invokes a write barrier for *dst = src

+// prior to the write happening.

+//

+// Write barrier calls must not happen during critical GC and scheduler

+// related operations. In particular there are times when the GC assumes

+// that the world is stopped but scheduler related code is still being

+// executed, dealing with syscalls, dealing with putting gs on runnable

+// queues and so forth. This code cannot execute write barriers because

+// the GC might drop them on the floor. Stopping the world involves removing

+// the p associated with an m. We use the fact that m.p == nil to indicate

+// that we are in one these critical section and throw if the write is of

+// a pointer to a heap object.

+//go:nosplit

+func writebarrierptr_prewrite1(dst *uintptr, src uintptr) {

+ mp := acquirem()

+ if mp.inwb || mp.dying > 0 {

+ releasem(mp)

+ return

+ }

+ systemstack(func() {

+ if mp.p == 0 && memstats.enablegc && !mp.inwb && inheap(src) {

+ throw("writebarrierptr_prewrite1 called with mp.p == nil")

+ }

+ mp.inwb = true

+ gcmarkwb_m(dst, src)

+ })

+ mp.inwb = false

+ releasem(mp)

+}

+

+// NOTE: Really dst *unsafe.Pointer, src unsafe.Pointer,

+// but if we do that, Go inserts a write barrier on *dst = src.

+//go:nosplit

+func writebarrierptr(dst *uintptr, src uintptr) {

+ if writeBarrier.cgo {

+ cgoCheckWriteBarrier(dst, src)

+ }

+ if !writeBarrier.needed {

+ *dst = src

+ return

+ }

+ if src != 0 && src < minPhysPageSize {

+ systemstack(func() {

+ print("runtime: writebarrierptr *", dst, " = ", hex(src), "\n")

+ throw("bad pointer in write barrier")

+ })

+ }

+ writebarrierptr_prewrite1(dst, src)

+ *dst = src

+}

+

+// writebarrierptr_prewrite is like writebarrierptr, but the store

+// will be performed by the caller after this call. The caller must

+// not allow preemption between this call and the write.

+//

+//go:nosplit

+func writebarrierptr_prewrite(dst *uintptr, src uintptr) {

+ if writeBarrier.cgo {

+ cgoCheckWriteBarrier(dst, src)

+ }

+ if !writeBarrier.needed {

+ return

+ }

+ if src != 0 && src < minPhysPageSize {

+ systemstack(func() { throw("bad pointer in write barrier") })

+ }

+ writebarrierptr_prewrite1(dst, src)

+}

+

+// typedmemmove copies a value of type t to dst from src.

+//go:nosplit

+func typedmemmove(typ *_type, dst, src unsafe.Pointer) {

+ if typ.kind&kindNoPointers == 0 {

+ bulkBarrierPreWrite(uintptr(dst), uintptr(src), typ.size)

+ }

+ // There's a race here: if some other goroutine can write to

+ // src, it may change some pointer in src after we've

+ // performed the write barrier but before we perform the

+ // memory copy. This safe because the write performed by that

+ // other goroutine must also be accompanied by a write

+ // barrier, so at worst we've unnecessarily greyed the old

+ // pointer that was in src.

+ memmove(dst, src, typ.size)

+ if writeBarrier.cgo {

+ cgoCheckMemmove(typ, dst, src, 0, typ.size)

+ }

+}

+

+//go:linkname reflect_typedmemmove reflect.typedmemmove

+func reflect_typedmemmove(typ *_type, dst, src unsafe.Pointer) {

+ if raceenabled {

+ raceWriteObjectPC(typ, dst, getcallerpc(unsafe.Pointer(&typ)), funcPC(reflect_typedmemmove))

+ raceReadObjectPC(typ, src, getcallerpc(unsafe.Pointer(&typ)), funcPC(reflect_typedmemmove))

+ }

+ if msanenabled {

+ msanwrite(dst, typ.size)

+ msanread(src, typ.size)

+ }

+ typedmemmove(typ, dst, src)

+}

+

+// typedmemmovepartial is like typedmemmove but assumes that

+// dst and src point off bytes into the value and only copies size bytes.

+//go:linkname reflect_typedmemmovepartial reflect.typedmemmovepartial

+func reflect_typedmemmovepartial(typ *_type, dst, src unsafe.Pointer, off, size uintptr) {

+ if writeBarrier.needed && typ.kind&kindNoPointers == 0 && size >= sys.PtrSize {

+ // Pointer-align start address for bulk barrier.

+ adst, asrc, asize := dst, src, size

+ if frag := -off & (sys.PtrSize - 1); frag != 0 {

+ adst = add(dst, frag)

+ asrc = add(src, frag)

+ asize -= frag

+ }

+ bulkBarrierPreWrite(uintptr(adst), uintptr(asrc), asize&^(sys.PtrSize-1))

+ }

+

+ memmove(dst, src, size)

+ if writeBarrier.cgo {

+ cgoCheckMemmove(typ, dst, src, off, size)

+ }

+}

+

+//go:nosplit

+func typedslicecopy(typ *_type, dst, src slice) int {

+ // TODO(rsc): If typedslicecopy becomes faster than calling

+ // typedmemmove repeatedly, consider using during func growslice.

+ n := dst.len

+ if n > src.len {

+ n = src.len

+ }

+ if n == 0 {

+ return 0

+ }

+ dstp := dst.array

+ srcp := src.array

+

+ if raceenabled {

+ callerpc := getcallerpc(unsafe.Pointer(&typ))

+ pc := funcPC(slicecopy)

+ racewriterangepc(dstp, uintptr(n)*typ.size, callerpc, pc)

+ racereadrangepc(srcp, uintptr(n)*typ.size, callerpc, pc)

+ }

+ if msanenabled {

+ msanwrite(dstp, uintptr(n)*typ.size)

+ msanread(srcp, uintptr(n)*typ.size)

+ }

+

+ if writeBarrier.cgo {

+ cgoCheckSliceCopy(typ, dst, src, n)

+ }

+

+ // Note: No point in checking typ.kind&kindNoPointers here:

+ // compiler only emits calls to typedslicecopy for types with pointers,

+ // and growslice and reflect_typedslicecopy check for pointers

+ // before calling typedslicecopy.

+ if !writeBarrier.needed {

+ memmove(dstp, srcp, uintptr(n)*typ.size)

+ return n

+ }

+

+ systemstack(func() {

+ if uintptr(srcp) < uintptr(dstp) && uintptr(srcp)+uintptr(n)*typ.size > uintptr(dstp) {

+ // Overlap with src before dst.

+ // Copy backward, being careful not to move dstp/srcp

+ // out of the array they point into.

+ dstp = add(dstp, uintptr(n-1)*typ.size)

+ srcp = add(srcp, uintptr(n-1)*typ.size)

+ i := 0

+ for {

+ typedmemmove(typ, dstp, srcp)

+ if i++; i >= n {

+ break

+ }

+ dstp = add(dstp, -typ.size)

+ srcp = add(srcp, -typ.size)

+ }

+ } else {

+ // Copy forward, being careful not to move dstp/srcp

+ // out of the array they point into.

+ i := 0

+ for {

+ typedmemmove(typ, dstp, srcp)

+ if i++; i >= n {

+ break

+ }

+ dstp = add(dstp, typ.size)

+ srcp = add(srcp, typ.size)

+ }

+ }

+ })

+ return n

+}

+

+//go:linkname reflect_typedslicecopy reflect.typedslicecopy

+func reflect_typedslicecopy(elemType *_type, dst, src slice) int {

+ if elemType.kind&kindNoPointers != 0 {

+ n := dst.len

+ if n > src.len {

+ n = src.len

+ }

+ if n == 0 {

+ return 0

+ }

+

+ size := uintptr(n) * elemType.size

+ if raceenabled {

+ callerpc := getcallerpc(unsafe.Pointer(&elemType))

+ pc := funcPC(reflect_typedslicecopy)

+ racewriterangepc(dst.array, size, callerpc, pc)

+ racereadrangepc(src.array, size, callerpc, pc)

+ }

+ if msanenabled {

+ msanwrite(dst.array, size)

+ msanread(src.array, size)

+ }

+

+ memmove(dst.array, src.array, size)

+ return n

+ }

+ return typedslicecopy(elemType, dst, src)

+}

+

+// typedmemclr clears the typed memory at ptr with type typ. The

+// memory at ptr must already be initialized (and hence in type-safe

+// state). If the memory is being initialized for the first time, see

+// memclrNoHeapPointers.

+//

+// If the caller knows that typ has pointers, it can alternatively

+// call memclrHasPointers.

+//

+//go:nosplit

+func typedmemclr(typ *_type, ptr unsafe.Pointer) {

+ if typ.kind&kindNoPointers == 0 {

+ bulkBarrierPreWrite(uintptr(ptr), 0, typ.size)

+ }

+ memclrNoHeapPointers(ptr, typ.size)

+}

+

+// memclrHasPointers clears n bytes of typed memory starting at ptr.

+// The caller must ensure that the type of the object at ptr has

+// pointers, usually by checking typ.kind&kindNoPointers. However, ptr

+// does not have to point to the start of the allocation.

+//

+//go:nosplit

+func memclrHasPointers(ptr unsafe.Pointer, n uintptr) {

+ bulkBarrierPreWrite(uintptr(ptr), 0, n)

+ memclrNoHeapPointers(ptr, n)

+}

+// Copyright 2009 The Go Authors. All rights reserved.

+// Use of this source code is governed by a BSD-style

+// license that can be found in the LICENSE file.

+

+// Garbage collector: type and heap bitmaps.

+//

+// Stack, data, and bss bitmaps

+//

+// Stack frames and global variables in the data and bss sections are described

+// by 1-bit bitmaps in which 0 means uninteresting and 1 means live pointer

+// to be visited during GC. The bits in each byte are consumed starting with

+// the low bit: 1<<0, 1<<1, and so on.

+//

+// Heap bitmap

+//

+// The allocated heap comes from a subset of the memory in the range [start, used),

+// where start == mheap_.arena_start and used == mheap_.arena_used.

+// The heap bitmap comprises 2 bits for each pointer-sized word in that range,

+// stored in bytes indexed backward in memory from start.

+// That is, the byte at address start-1 holds the 2-bit entries for the four words

+// start through start+3*ptrSize, the byte at start-2 holds the entries for

+// start+4*ptrSize through start+7*ptrSize, and so on.

+//

+// In each 2-bit entry, the lower bit holds the same information as in the 1-bit

+// bitmaps: 0 means uninteresting and 1 means live pointer to be visited during GC.

+// The meaning of the high bit depends on the position of the word being described

+// in its allocated object. In all words *except* the second word, the

+// high bit indicates that the object is still being described. In

+// these words, if a bit pair with a high bit 0 is encountered, the

+// low bit can also be assumed to be 0, and the object description is

+// over. This 00 is called the ``dead'' encoding: it signals that the

+// rest of the words in the object are uninteresting to the garbage

+// collector.

+//

+// In the second word, the high bit is the GC ``checkmarked'' bit (see below).

+//

+// The 2-bit entries are split when written into the byte, so that the top half

+// of the byte contains 4 high bits and the bottom half contains 4 low (pointer)

+// bits.

+// This form allows a copy from the 1-bit to the 4-bit form to keep the

+// pointer bits contiguous, instead of having to space them out.

+//

+// The code makes use of the fact that the zero value for a heap bitmap

+// has no live pointer bit set and is (depending on position), not used,

+// not checkmarked, and is the dead encoding.

+// These properties must be preserved when modifying the encoding.

+//

+// Checkmarks

+//

+// In a concurrent garbage collector, one worries about failing to mark

+// a live object due to mutations without write barriers or bugs in the

+// collector implementation. As a sanity check, the GC has a 'checkmark'

+// mode that retraverses the object graph with the world stopped, to make

+// sure that everything that should be marked is marked.

+// In checkmark mode, in the heap bitmap, the high bit of the 2-bit entry

+// for the second word of the object holds the checkmark bit.

+// When not in checkmark mode, this bit is set to 1.

+//

+// The smallest possible allocation is 8 bytes. On a 32-bit machine, that

+// means every allocated object has two words, so there is room for the

+// checkmark bit. On a 64-bit machine, however, the 8-byte allocation is

+// just one word, so the second bit pair is not available for encoding the

+// checkmark. However, because non-pointer allocations are combined

+// into larger 16-byte (maxTinySize) allocations, a plain 8-byte allocation

+// must be a pointer, so the type bit in the first word is not actually needed.

+// It is still used in general, except in checkmark the type bit is repurposed

+// as the checkmark bit and then reinitialized (to 1) as the type bit when

+// finished.

+//

+

+package runtime

+

+import (

+ "runtime/internal/atomic"

+ "runtime/internal/sys"

+ "unsafe"

+)

+

+const (

+ bitPointer = 1 << 0

+ bitScan = 1 << 4

+

+ heapBitsShift = 1 // shift offset between successive bitPointer or bitScan entries

+ heapBitmapScale = sys.PtrSize * (8 / 2) // number of data bytes described by one heap bitmap byte

+

+ // all scan/pointer bits in a byte

+ bitScanAll = bitScan | bitScan<<heapBitsShift | bitScan<<(2*heapBitsShift) | bitScan<<(3*heapBitsShift)

+ bitPointerAll = bitPointer | bitPointer<<heapBitsShift | bitPointer<<(2*heapBitsShift) | bitPointer<<(3*heapBitsShift)

+)

+

+// addb returns the byte pointer p+n.

+//go:nowritebarrier

+//go:nosplit

+func addb(p *byte, n uintptr) *byte {

+ // Note: wrote out full expression instead of calling add(p, n)

+ // to reduce the number of temporaries generated by the

+ // compiler for this trivial expression during inlining.

+ return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + n))

+}

+

+// subtractb returns the byte pointer p-n.

+// subtractb is typically used when traversing the pointer tables referred to by hbits

+// which are arranged in reverse order.

+//go:nowritebarrier

+//go:nosplit

+func subtractb(p *byte, n uintptr) *byte {

+ // Note: wrote out full expression instead of calling add(p, -n)

+ // to reduce the number of temporaries generated by the

+ // compiler for this trivial expression during inlining.

+ return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - n))

+}

+

+// add1 returns the byte pointer p+1.

+//go:nowritebarrier

+//go:nosplit

+func add1(p *byte) *byte {

+ // Note: wrote out full expression instead of calling addb(p, 1)

+ // to reduce the number of temporaries generated by the

+ // compiler for this trivial expression during inlining.

+ return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + 1))

+}

+

+// subtract1 returns the byte pointer p-1.

+// subtract1 is typically used when traversing the pointer tables referred to by hbits

+// which are arranged in reverse order.

+//go:nowritebarrier

+//

+// nosplit because it is used during write barriers and must not be preempted.

+//go:nosplit

+func subtract1(p *byte) *byte {

+ // Note: wrote out full expression instead of calling subtractb(p, 1)

+ // to reduce the number of temporaries generated by the

+ // compiler for this trivial expression during inlining.

+ return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - 1))

+}

+

+// mHeap_MapBits is called each time arena_used is extended.

+// It maps any additional bitmap memory needed for the new arena memory.

+// It must be called with the expected new value of arena_used,

+// *before* h.arena_used has been updated.

+// Waiting to update arena_used until after the memory has been mapped

+// avoids faults when other threads try access the bitmap immediately

+// after observing the change to arena_used.

+//

+//go:nowritebarrier

+func (h *mheap) mapBits(arena_used uintptr) {

+ // Caller has added extra mappings to the arena.

+ // Add extra mappings of bitmap words as needed.

+ // We allocate extra bitmap pieces in chunks of bitmapChunk.

+ const bitmapChunk = 8192

+

+ n := (arena_used - mheap_.arena_start) / heapBitmapScale

+ n = round(n, bitmapChunk)

+ n = round(n, physPageSize)

+ if h.bitmap_mapped >= n {

+ return

+ }

+

+ sysMap(unsafe.Pointer(h.bitmap-n), n-h.bitmap_mapped, h.arena_reserved, &memstats.gc_sys)

+ h.bitmap_mapped = n

+}

+

+// heapBits provides access to the bitmap bits for a single heap word.

+// The methods on heapBits take value receivers so that the compiler

+// can more easily inline calls to those methods and registerize the

+// struct fields independently.

+type heapBits struct {

+ bitp *uint8

+ shift uint32

+}

+

+// markBits provides access to the mark bit for an object in the heap.

+// bytep points to the byte holding the mark bit.

+// mask is a byte with a single bit set that can be &ed with *bytep

+// to see if the bit has been set.

+// *m.byte&m.mask != 0 indicates the mark bit is set.

+// index can be used along with span information to generate

+// the address of the object in the heap.

+// We maintain one set of mark bits for allocation and one for

+// marking purposes.

+type markBits struct {

+ bytep *uint8

+ mask uint8

+ index uintptr

+}

+

+//go:nosplit

+func (s *mspan) allocBitsForIndex(allocBitIndex uintptr) markBits {

+ whichByte := allocBitIndex / 8

+ whichBit := allocBitIndex % 8

+ bytePtr := addb(s.allocBits, whichByte)

+ return markBits{bytePtr, uint8(1 << whichBit), allocBitIndex}

+}

+

+// refillaCache takes 8 bytes s.allocBits starting at whichByte

+// and negates them so that ctz (count trailing zeros) instructions

+// can be used. It then places these 8 bytes into the cached 64 bit

+// s.allocCache.

+func (s *mspan) refillAllocCache(whichByte uintptr) {

+ bytes := (*[8]uint8)(unsafe.Pointer(addb(s.allocBits, whichByte)))

+ aCache := uint64(0)

+ aCache |= uint64(bytes[0])

+ aCache |= uint64(bytes[1]) << (1 * 8)

+ aCache |= uint64(bytes[2]) << (2 * 8)

+ aCache |= uint64(bytes[3]) << (3 * 8)

+ aCache |= uint64(bytes[4]) << (4 * 8)

+ aCache |= uint64(bytes[5]) << (5 * 8)

+ aCache |= uint64(bytes[6]) << (6 * 8)

+ aCache |= uint64(bytes[7]) << (7 * 8)

+ s.allocCache = ^aCache

+}

+

+// nextFreeIndex returns the index of the next free object in s at

+// or after s.freeindex.

+// There are hardware instructions that can be used to make this

+// faster if profiling warrants it.

+func (s *mspan) nextFreeIndex() uintptr {

+ sfreeindex := s.freeindex

+ snelems := s.nelems

+ if sfreeindex == snelems {

+ return sfreeindex

+ }

+ if sfreeindex > snelems {

+ throw("s.freeindex > s.nelems")

+ }

+

+ aCache := s.allocCache

+

+ bitIndex := sys.Ctz64(aCache)

+ for bitIndex == 64 {

+ // Move index to start of next cached bits.

+ sfreeindex = (sfreeindex + 64) &^ (64 - 1)

+ if sfreeindex >= snelems {

+ s.freeindex = snelems

+ return snelems

+ }

+ whichByte := sfreeindex / 8

+ // Refill s.allocCache with the next 64 alloc bits.

+ s.refillAllocCache(whichByte)

+ aCache = s.allocCache

+ bitIndex = sys.Ctz64(aCache)

+ // nothing available in cached bits

+ // grab the next 8 bytes and try again.

+ }

+ result := sfreeindex + uintptr(bitIndex)

+ if result >= snelems {

+ s.freeindex = snelems

+ return snelems

+ }

+

+ s.allocCache >>= (bitIndex + 1)

+ sfreeindex = result + 1

+

+ if sfreeindex%64 == 0 && sfreeindex != snelems {

+ // We just incremented s.freeindex so it isn't 0.

+ // As each 1 in s.allocCache was encountered and used for allocation

+ // it was shifted away. At this point s.allocCache contains all 0s.

+ // Refill s.allocCache so that it corresponds

+ // to the bits at s.allocBits starting at s.freeindex.

+ whichByte := sfreeindex / 8

+ s.refillAllocCache(whichByte)

+ }

+ s.freeindex = sfreeindex

+ return result

+}

+

+// isFree returns whether the index'th object in s is unallocated.

+func (s *mspan) isFree(index uintptr) bool {

+ if index < s.freeindex {

+ return false

+ }

+ whichByte := index / 8

+ whichBit := index % 8

+ byteVal := *addb(s.allocBits, whichByte)

+ return byteVal&uint8(1<<whichBit) == 0

+}

+

+func (s *mspan) objIndex(p uintptr) uintptr {

+ byteOffset := p - s.base()

+ if byteOffset == 0 {

+ return 0

+ }

+ if s.baseMask != 0 {

+ // s.baseMask is 0, elemsize is a power of two, so shift by s.divShift

+ return byteOffset >> s.divShift

+ }

+ return uintptr(((uint64(byteOffset) >> s.divShift) * uint64(s.divMul)) >> s.divShift2)

+}

+

+func markBitsForAddr(p uintptr) markBits {

+ s := spanOf(p)

+ objIndex := s.objIndex(p)

+ return s.markBitsForIndex(objIndex)

+}

+

+func (s *mspan) markBitsForIndex(objIndex uintptr) markBits {

+ whichByte := objIndex / 8

+ bitMask := uint8(1 << (objIndex % 8)) // low 3 bits hold the bit index

+ bytePtr := addb(s.gcmarkBits, whichByte)

+ return markBits{bytePtr, bitMask, objIndex}

+}

+

+func (s *mspan) markBitsForBase() markBits {

+ return markBits{s.gcmarkBits, uint8(1), 0}

+}

+

+// isMarked reports whether mark bit m is set.

+func (m markBits) isMarked() bool {

+ return *m.bytep&m.mask != 0

+}

+

+// setMarked sets the marked bit in the markbits, atomically. Some compilers

+// are not able to inline atomic.Or8 function so if it appears as a hot spot consider

+// inlining it manually.

+func (m markBits) setMarked() {

+ // Might be racing with other updates, so use atomic update always.

+ // We used to be clever here and use a non-atomic update in certain

+ // cases, but it's not worth the risk.

+ atomic.Or8(m.bytep, m.mask)

+}

+

+// setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.

+func (m markBits) setMarkedNonAtomic() {

+ *m.bytep |= m.mask

+}

+

+// clearMarked clears the marked bit in the markbits, atomically.

+func (m markBits) clearMarked() {

+ // Might be racing with other updates, so use atomic update always.

+ // We used to be clever here and use a non-atomic update in certain

+ // cases, but it's not worth the risk.

+ atomic.And8(m.bytep, ^m.mask)

+}

+

+// clearMarkedNonAtomic clears the marked bit non-atomically.

+func (m markBits) clearMarkedNonAtomic() {

+ *m.bytep ^= m.mask

+}

+

+// markBitsForSpan returns the markBits for the span base address base.

+func markBitsForSpan(base uintptr) (mbits markBits) {

+ if base < mheap_.arena_start || base >= mheap_.arena_used {

+ throw("markBitsForSpan: base out of range")

+ }

+ mbits = markBitsForAddr(base)

+ if mbits.mask != 1 {

+ throw("markBitsForSpan: unaligned start")

+ }

+ return mbits

+}

+

+// advance advances the markBits to the next object in the span.

+func (m *markBits) advance() {

+ if m.mask == 1<<7 {

+ m.bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(m.bytep)) + 1))

+ m.mask = 1

+ } else {

+ m.mask = m.mask << 1

+ }

+ m.index++

+}

+

+// heapBitsForAddr returns the heapBits for the address addr.

+// The caller must have already checked that addr is in the range [mheap_.arena_start, mheap_.arena_used).

+//

+// nosplit because it is used during write barriers and must not be preempted.

+//go:nosplit

+func heapBitsForAddr(addr uintptr) heapBits {

+ // 2 bits per work, 4 pairs per byte, and a mask is hard coded.

+ off := (addr - mheap_.arena_start) / sys.PtrSize

+ return heapBits{(*uint8)(unsafe.Pointer(mheap_.bitmap - off/4 - 1)), uint32(off & 3)}

+}

+

+// heapBitsForSpan returns the heapBits for the span base address base.

+func heapBitsForSpan(base uintptr) (hbits heapBits) {

+ if base < mheap_.arena_start || base >= mheap_.arena_used {

+ throw("heapBitsForSpan: base out of range")

+ }

+ return heapBitsForAddr(base)

+}

+

+// heapBitsForObject returns the base address for the heap object

+// containing the address p, the heapBits for base,

+// the object's span, and of the index of the object in s.

+// If p does not point into a heap object,

+// return base == 0

+// otherwise return the base of the object.

+//

+// For gccgo, the forStack parameter is true if the value came from the stack.

+// The stack is collected conservatively and may contain invalid pointers.

+//

+// refBase and refOff optionally give the base address of the object

+// in which the pointer p was found and the byte offset at which it

+// was found. These are used for error reporting.

+func heapBitsForObject(p, refBase, refOff uintptr, forStack bool) (base uintptr, hbits heapBits, s *mspan, objIndex uintptr) {

+ arenaStart := mheap_.arena_start

+ if p < arenaStart || p >= mheap_.arena_used {

+ return

+ }

+ off := p - arenaStart

+ idx := off >> _PageShift

+ // p points into the heap, but possibly to the middle of an object.

+ // Consult the span table to find the block beginning.

+ s = mheap_.spans[idx]

+ if s == nil || p < s.base() || p >= s.limit || s.state != mSpanInUse {

+ if s == nil || s.state == _MSpanStack || forStack {

+ // If s is nil, the virtual address has never been part of the heap.

+ // This pointer may be to some mmap'd region, so we allow it.

+ // Pointers into stacks are also ok, the runtime manages these explicitly.

+ return

+ }

+

+ // The following ensures that we are rigorous about what data

+ // structures hold valid pointers.

+ if debug.invalidptr != 0 {

+ // Typically this indicates an incorrect use

+ // of unsafe or cgo to store a bad pointer in

+ // the Go heap. It may also indicate a runtime

+ // bug.

+ //

+ // TODO(austin): We could be more aggressive

+ // and detect pointers to unallocated objects

+ // in allocated spans.

+ printlock()

+ print("runtime: pointer ", hex(p))

+ if s.state != mSpanInUse {

+ print(" to unallocated span")

+ } else {

+ print(" to unused region of span")

+ }

+ print(" idx=", hex(idx), " span.base()=", hex(s.base()), " span.limit=", hex(s.limit), " span.state=", s.state, "\n")

+ if refBase != 0 {

+ print("runtime: found in object at *(", hex(refBase), "+", hex(refOff), ")\n")

+ gcDumpObject("object", refBase, refOff)

+ }

+ throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")

+ }

+ return

+ }

+

+ if forStack {

+ // A span can be entered in mheap_.spans, and be set

+ // to mSpanInUse, before it is fully initialized.

+ // All we need in practice is allocBits and gcmarkBits,

+ // so make sure they are set.

+ if s.allocBits == nil || s.gcmarkBits == nil {

+ return

+ }