x/tools/go/ssa: commit 75ff53bc introduced a race condition

[aykevl]

Go version

go version go1.22.2 linux/arm64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/home/ayke/.cache/go-build'
GOENV='/home/ayke/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/ayke/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/ayke'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/usr/local/go1.22.2'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/go1.22.2/pkg/tool/linux_arm64'
GOVCS=''
GOVERSION='go1.22.2'
GCCGO='gccgo'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/ayke/src/tinygo/tinygo/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 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build553721638=/tmp/go-build -gno-record-gcc-switches'

What did you do?

I upgraded the x/tools package to v0.17.0.

What did you see happen?

Lots of infrequent crashes starting from golang/tools@75ff53b (see tinygo-org/tinygo#4206).
The symptoms are all kinds of weird crashes, but in particular what I'm seeing often is functions that appear to be unfinished (no terminator in a basic block).

Interestingly, once I build the program using -race the race condition goes away. This makes it particularly difficult to pinpoint where exactly the bug is located.

I've also tried the master branch (golang/tools@0b45163) but sadly it still shows the same crashes.

I can try to work on a standalone reproducer, but with the nature of this crash it's difficult to find one. Still, if it's difficult to find the culprit just from the bisected commit I can try to work on a reproducer.

What did you expect to see?

No race condition.

[adonovan]

Hi, maintainer of go/ssa and author of https://go.dev/cl/538358 here. I don't have a good hypothesis yet: that CL looks sound w.r.t. concurrency, as does the same code at master. Interestingly, tinygo does not appear to use Program.RuntimeTypes or ssautil.AllFunctions (which is good: these functions should be deprecated!), which were the primary focus of that CL. The tinygo logic to construct go/ssa code looks generally sound too.

Can you share the test case you used for bisecting to this CL? Even if it takes hundreds of runs to reliably fail, that would make it much easier to investigate.

[timothy-king]

@aykevl It looks like ssa.Package.Build is called with some synchronization between packages? I don't fully understand the synchronization though.

https://github.com/tinygo-org/tinygo/blob/release/builder/build.go#L350
https://github.com/tinygo-org/tinygo/blob/release/builder/jobs.go#L123

A lack of synchronization could be a source of races once generics are involved. (ssa.Program.Build solves this.) I don't know why https://go.dev/cl/538358 would be involved.

A test case would really help.

[adonovan]

@aykevl It looks like ssa.Package.Build is called with some synchronization between packages? I don't fully understand the synchronization though.

https://github.com/tinygo-org/tinygo/blob/release/builder/build.go#L350
https://github.com/tinygo-org/tinygo/blob/release/builder/jobs.go#L123

A lack of synchronization could be a source of races once generics are involved. (ssa.Program.Build solves this.) I don't know why https://go.dev/cl/538358 would be involved.

It's quite safe to go/ssa-Build all Packages in parallel--that's exactly what Program.Build does--so that doesn't explain it.

tinygo seems to use concurrency for building and compiling each SSA package in parallel while respecting topological order, which seems sound. (There's more available parallelism of course, in reading, parsing, type-checking, etc.) The only synchronization within each compile job (package) is a cross-process lock on the output file, presumably to prevent concurrent writes from different tinygo processes. There's no fine-grained concurrency, so the lack of Mutex.Lock operations isn't obviously a problem.

I wonder about the fact that some functions in low-level packages of intrinsics (runtime et al) are used from all other packages (e.g. when compiling ssa.Go); if the intrinsics package is not fully llvm-built before the other packages this could lead to a race.

A test case would really help.

Agreed.

[timothy-king]

It's quite safe to go/ssa-Build all Packages in parallel--that's exactly what Program.Build does--so that doesn't explain it.

ssa is very careful to only read from specific fixed fields on functions from other packages or created functions while building. Reading from generic instantiations before they are done can race. Waiting for every package to finish building is good enough, which is what ssa.Program does. Annoyingly diamonds can cause the same instantiation to be created so package topology is not enough. This definitely used to be the case, and I don't remember fixing this. (My memory might be off though.)

[deadprogram]

if the intrinsics package is not fully llvm-built before the other packages this could lead to a race.

That sounds very much like the behavior I have observed anecdotally. However, I do not have a reproducible test case.