unique: "run out of hash bits" bug in internal HashTrieMap

[GiedriusS]

Go version

go version devel go1.24-3d33437c45 Sun Sep 15 02:05:37 2024 +0000 linux/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/giedriusstatkevicius/.cache/go-build'
GOENV='/home/giedriusstatkevicius/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/giedriusstatkevicius/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/giedriusstatkevicius/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/giedriusstatkevicius/dev/goroot'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/home/giedriusstatkevicius/dev/goroot/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='devel go1.24-3d33437c45 Sun Sep 15 02:05:37 2024 +0000'
GODEBUG=''
GOTELEMETRY='local'
GOTELEMETRYDIR='/home/giedriusstatkevicius/.config/go/telemetry'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/giedriusstatkevicius/dev/thanos/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build2862491001=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Trying to intern all strings coming through gRPC using the new unique.Make(): new vtprotobuf extension. It seems like it is very easy to break some limits? The machine has 128 cores and 256GiB+ of RAM so resources shouldn't be a problem.

I tried creating a toy program that interns random strings and couldn't reproduce it, unfortunately.

What did you see happen?

I see this after some time:

panic: internal/concurrent.HashMapTrie: ran out of hash bits while inserting                                                
 goroutine 119167 [running]:                                                                                                 
 internal/concurrent.(*HashTrieMap[...]).expand(0x3869440?, 0xc004e117d0, 0xc00c21ed20, 0x7eee22e697634db7, 0x0, 0xc0151414a0
)                                                                                                                                                                                             
       /usr/local/go/src/internal/concurrent/hashtriemap.go:163 +0x1ea                                                       
 internal/concurrent.(*HashTrieMap[...]).LoadOrStore(0x3869440, {0xc00155e107, 0x12}, {0xc000fe1540})
       /usr/local/go/src/internal/concurrent/hashtriemap.go:142 +0x40a
 unique.Make[...]({0xc00155e107, 0x12})
       /usr/local/go/src/unique/handle.go:67 +0x1ea
 github.com/thanos-io/thanos/pkg/store/labelpb.(*Label).UnmarshalVT(0xc001935bd0, {0xc00155e0fe, 0x1b, 0x3f02})
       /home/giedriusstatkevicius/dev/thanos/pkg/store/labelpb/types_vtproto.pb.go:303 +0x4e5

Same happens with 1.23.1.

What did you expect to see?

I expected no panic.

[gabyhelp]

Related Issues and Documentation

• internal/concurrent: hashtriemap uses abi.NoEscape cause incorrect inlining decision #68511 (closed)
• unique: panic for Make(struct{}{}) #69458 (closed)
• x/tools/go/types/typeutil: stack overflow when hashing recursive embedded type interface #26863 (closed)
• x/tools/go/types/typeutil: stack overflow when hashing mutually recursive pointers to type parameters #51314 (closed)
• runtime: unexpected fault address 0x0 in hashmap.go #13062 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[cagedmantis]

cc @mknyszek

[mknyszek]

There's no internal limit, this is just a bug. ("Run out of hash bits" means that the implementation would've expected a hash collision given that it just walked over (what it thinks is) the maximum depth of the tree and ran out of hash bits. Hash collisions are still handled, though.)

Looking into it.

[GiedriusS]

I'll try to add an atomic counter to see how many calls it takes to trigger this panic

[mknyszek]

My suspicion is an off-by-one error in creating new nodes. Like, the hash matches down to the last 4 bits, but the last 4 don't and we give up too early. It occurs to me that this codepath isn't well-tested because actual collisions (which are well-tested) short-circuit to appending onto the overflow list for a node.

I'll try to write a test for this case and see if that's the problem.

[mknyszek]

Yeah, actually, I'm feeling more confident in this diagnosis. If it's the case, I should have a fix and a test shortly.

EDIT: No, that doesn't seem to be it.

[mknyszek]

I took a brief look at planetscale/vtprotobuf#140 and I noticed that you're using unsafe.String to pass a byte slice through to unique.Make. This is fine, but one thing that occurs to me is that on insert, the node we're colliding with is re-hashed. If the byte slice you passed to unique.Make is mutated prior to this commit then it's possible that that produces a different hash.

It already looks like you already tried at tip though, past that commit, and ran into the same issue. Can you confirm that?

[GiedriusS]

I took a brief look at planetscale/vtprotobuf#140 and I noticed that you're using unsafe.String to pass a byte slice through to unique.Make. This is fine, but one thing that occurs to me is that on insert, the node we're colliding with is re-hashed. If the byte slice you passed to unique.Make is mutated prior to this commit then it's possible that that produces a different hash.

It already looks like you already tried at tip though, past that commit, and ran into the same issue. Can you confirm that?

Yeah, that's why I tried the tip version. Without that commit the panic occurs within a few seconds of me triggering that code path. With that commit it's a bit harder and occurs in 30-60 seconds.

[mknyszek]

If you have any instructions to reproduce, or if you're willing to share a core file or something (so that I can inspect the state of the HashTrieMap on crash) that would help me iterate on this faster.

I can also write a small patch to dump the state of the HashMapTrie on crash, if you're willing to run that and provide the output. (EDIT: If it helps, I can remove the actual key/value output, I think I just need the hash anyway.)

[gopherbot]

Change https://go.dev/cl/614475 mentions this issue: unique,internal/concurrent: add some more tests