hash/maphash: Hash always escapes

[nussjustin]

What version of Go are you using (go version)?

$ go version
go version devel +c20b71eb37 Sat Nov 16 02:06:39 2019 +0000 linux/amd64

Does this issue reproduce with the latest release?

n/a

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GO111MODULE="auto"
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/justinn/.cache/go-build"
GOENV="/home/justinn/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/justinn/.gopath"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/opt/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/justinn/Workspace/go/scache/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build754196892=/tmp/go-build -gno-record-gcc-switches"
GOROOT/bin/go version: go version devel +c20b71eb37 Sat Nov 16 02:06:39 2019 +0000 linux/amd64
GOROOT/bin/go tool compile -V: compile version devel +c20b71eb37 Sat Nov 16 02:06:39 2019 +0000
uname -sr: Linux 5.3.11-arch1-1
/usr/lib/libc.so.6: GNU C Library (GNU libc) stable release version 2.30.
gdb --version: GNU gdb (GDB) 8.3.1

What did you do?

// +build go1.14

package sharding

import "hash/maphash"

type Hasher struct {
    seed maphash.Seed
}

func NewHasher() Hasher {
    return Hasher{
        seed: maphash.MakeSeed(),
    }   
}

func (h Hasher) Hash(s string) uint64 {
    var sh maphash.Hash
    sh.SetSeed(h.seed)
    sh.WriteString(s)
    return sh.Sum64()
}

What did you expect to see?

No allocations for hashing.

What did you see instead?

The variable sh in Hasher.Hash escapes to the heap, causing an allocation.

# github.com/nussjustin/scache/internal/sharding
./hash_go114.go:11:6: can inline NewHasher as: func() Hasher { return Hasher literal }
./hash_go114.go:17:6: cannot inline Hasher.Hash: function too complex: cost 154 exceeds budget 80
./hash_go114.go:19:12: inlining call to maphash.(*Hash).SetSeed method(*maphash.Hash) func(maphash.Seed) { if maphash.seed.s == uint64(0) { panic(string("maphash: use of uninitialized Seed")) }; maphash.h.seed = maphash.seed; maphash.h.state = maphash.seed; maphash.h.n = int(0) }
./hash_go114.go:18:6: sh escapes to heap:
./hash_go114.go:18:6:   flow: {heap} = &sh:
./hash_go114.go:18:6:     from sh (address-of) at ./hash_go114.go:20:4
./hash_go114.go:18:6:     from sh.WriteString(s) (call parameter) at ./hash_go114.go:20:16
./hash_go114.go:18:6: sh escapes to heap:
./hash_go114.go:18:6:   flow: {heap} = &sh:
./hash_go114.go:18:6:     from sh (address-of) at ./hash_go114.go:21:11
./hash_go114.go:18:6:     from sh.Sum64() (call parameter) at ./hash_go114.go:21:17
./hash_go114.go:17:22: s does not escape
./hash_go114.go:18:6: moved to heap: sh
<autogenerated>:1: .this does not escape
./hash_go114.go:17:22: s does not escape

The WriteString causes *maphash.Hash to escape because it calls flush internally:

./maphash.go:100:7: parameter h leaks to {heap} with derefs=0:
./maphash.go:100:7:   flow: {heap} = h:
./maphash.go:100:7:     from h.flush() (call parameter) at ./maphash.go:106:10
./maphash.go:100:7: leaking param: h
./maphash.go:100:28: s does not escape

flush itself calls rthash which calls runtime_memhash (imported from runtime.memhash) which causes the array h.buf and thus the *maphash.Hash to escape:

./maphash.go:141:7: parameter h leaks to {heap} with derefs=0:
./maphash.go:141:7:   flow: b = h:
./maphash.go:141:7:     from h.buf (dot of pointer) at ./maphash.go:146:22
./maphash.go:141:7:     from h.buf (address-of) at ./maphash.go:146:26
./maphash.go:141:7:     from h.buf[:] (slice) at ./maphash.go:146:26
./maphash.go:141:7:     from b, seed = <N> (assign-pair) at ./maphash.go:146:20
./maphash.go:141:7:   flow: {heap} = b:
./maphash.go:141:7:     from b[0] (dot of pointer) at ./maphash.go:146:20
./maphash.go:141:7:     from &b[0] (address-of) at ./maphash.go:146:20
./maphash.go:141:7:     from runtime_memhash(unsafe.Pointer(&b[0]), uintptr(seed), uintptr(len(b))) (call parameter) at ./maphash.go:146:20
./maphash.go:141:7: leaking param: h

Sum64 also calls rthash which causes the *maphash.Hash to escape:

./maphash.go:157:7: parameter h leaks to {heap} with derefs=0:
./maphash.go:157:7:   flow: b = h:
./maphash.go:157:7:     from h.buf (dot of pointer) at ./maphash.go:159:17
./maphash.go:157:7:     from h.buf (address-of) at ./maphash.go:159:21
./maphash.go:157:7:     from h.buf[:h.n] (slice) at ./maphash.go:159:21
./maphash.go:157:7:     from b, seed = <N> (assign-pair) at ./maphash.go:159:15
./maphash.go:157:7:   flow: {heap} = b:
./maphash.go:157:7:     from b[0] (dot of pointer) at ./maphash.go:159:15
./maphash.go:157:7:     from &b[0] (address-of) at ./maphash.go:159:15
./maphash.go:157:7:     from runtime_memhash(unsafe.Pointer(&b[0]), uintptr(seed), uintptr(len(b))) (call parameter) at ./maphash.go:159:15
./maphash.go:157:7: leaking param: h

Adding //go:noescape to the declaration of runtime_memhash in hash/maphash/maphash.go:196 makes the *maphash.Hash not escape and removes the allocation.

Based on my understanding of runtime.memhash and escape analysis this should be safe, but I'm not 100% sure.

[nussjustin]

/cc @rsc @randall77

[randall77]

Thanks for finding this. That's the correct fix. CL is coming.

[gopherbot]

Change https://golang.org/cl/207444 mentions this issue: hash/maphash: mark call into runtime hash function as not escaping