Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

x/tools/go/ssa: race condition between generic instantiations in separate packages #63247

Open
aykevl opened this issue Sep 26, 2023 · 2 comments
Open

x/tools/go/ssa: race condition between generic instantiations in separate packages #63247

aykevl opened this issue Sep 26, 2023 · 2 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Unreleased

Comments

@aykevl
Copy link

aykevl commented Sep 26, 2023

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

$ go version
go version go1.21.1 linux/arm64

Does this issue reproduce with the latest release?

Yes, this is the latest release.

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

go env Output
$ go env
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.21.1'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/go1.21.1/pkg/tool/linux_arm64'
GOVCS=''
GOVERSION='go1.21.1'
GCCGO='gccgo'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/ayke/src/ayke/sandbox/ssa-generics-race/go.mod'
GOWORK='/home/ayke/src/ayke/go.work'
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 -fmessage-length=0 -ffile-prefix-map=/tmp/go-build428572541=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Check out the code here: https://github.com/aykevl/sandbox/tree/main/ssa-generics-race

Now build this with the race condition checker enabled, and run it a number of times (the race only manifests itself sometimes). In the fish shell, that looks like this:

$ go build -race
$ for i in (seq 1 200); ./ssa-generics-race; end

What did you expect to see?

It should not trigger a race condition.

What did you see instead?

==================
WARNING: DATA RACE
Read at 0x00c0002c4538 by goroutine 27:
  main.main.func3()
      /home/ayke/src/ayke/sandbox/ssa-generics-race/test.go:77 +0x208

Previous write at 0x00c0002c4538 by goroutine 26:
  golang.org/x/tools/go/ssa.(*Function).newBasicBlock()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/func.go:670 +0x468
  golang.org/x/tools/go/ssa.(*Function).startBody()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/func.go:163 +0x4ac
  golang.org/x/tools/go/ssa.(*builder).buildFunctionBody()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/builder.go:2367 +0x29c
  golang.org/x/tools/go/ssa.(*builder).buildFunction()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/builder.go:2304 +0x5c
  golang.org/x/tools/go/ssa.(*builder).buildCreated()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/builder.go:2391 +0x4c
  golang.org/x/tools/go/ssa.(*Package).build()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/builder.go:2584 +0xff4
  golang.org/x/tools/go/ssa.(*Package).build-fm()
      <autogenerated>:1 +0x34
  sync.(*Once).doSlow()
      /usr/local/go1.21.1/src/sync/once.go:74 +0xb0
  sync.(*Once).Do()
      /usr/local/go1.21.1/src/sync/once.go:65 +0x40
  golang.org/x/tools/go/ssa.(*Package).Build()
      /home/ayke/pkg/mod/golang.org/x/tools@v0.13.0/go/ssa/builder.go:2455 +0x58
  main.main.func2()
      /home/ayke/src/ayke/sandbox/ssa-generics-race/test.go:51 +0x38

Goroutine 27 (running) created at:
  main.main()
      /home/ayke/src/ayke/sandbox/ssa-generics-race/test.go:54 +0x464

Goroutine 26 (running) created at:
  main.main()
      /home/ayke/src/ayke/sandbox/ssa-generics-race/test.go:50 +0x3c4
==================

The high-level overview of the code is as follows:

  1. The AST is created for the given packages.
  2. SSA packages are then created from the AST (but not yet built).
  3. The common "value" package is built first.
  4. The packages testa and testb are then built in parallel. After building of testb is complete, it accesses the value.New[int] function that was built as part of testb.
  5. This results in a race condition, apparently because that generic function is still being instantiated in testa.

My guess would be that there is a shared cache of instantiated generic functions, and while the testa package has started building the value.New[int] function and added it to the cache, testb will just use it without waiting for it to be finished building.

It is possible there is some invariant I have violated in my code, but if I have, I'm not sure what that would be. While building dependencies of packages first seems reasonable, I don't see why sibling packages would need to wait until the other is finished before accessing instantiated generic functions.
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Sep 26, 2023
@gopherbot gopherbot added this to the Unreleased milestone Sep 26, 2023
@aykevl aykevl mentioned this issue Sep 26, 2023
Closed
@timothy-king
Copy link
Contributor

While building dependencies of packages first seems reasonable, I don't see why sibling packages would need to wait until the other is finished before accessing instantiated generic functions.

The current implementation builds until you reach a fixed-point of created functions. It awards the job of building an instantiation to the first ssa.Package that caused the creation of the instantiation. The other packages can then refer to the fixed parts of the *ssa.Function that was created and those packages those do not have to wait. The fixed-point was introduced to eliminate dead-locks for that generics+wrappers introduced.

I think an assumption got introduced that one would either do one ssa.Package or all ssa.Packages in an ssa.Program. These are the two main supported modes. So to support this one would need to delay returning from creating the *ssa.Package until all of the potentially referenced generic functions have finished building on other goroutines.

This is clearly a race though. The most likely answer will be to wait until building value.New[int] is done before testb is done. The simplest form will probably be to wait until testa is finished. Maybe? I am not sure when I will get to this.

@thanm thanm added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 27, 2023
@timothy-king
Copy link
Contributor

It is worth keeping in mind that generic instantiations can be cyclic. Example https://go.dev/play/p/AsUmICi4Fev. Coming up with a strategy that cannot stall and always succeeds is tricky. So if you have instantiations, (*ssa.Program).Build() is an easy way to wait enough.

@aykevl Maybe it would be helpful to know what is the interface you are hoping to have?

  • Do you want (*ssa.Package).Build() to wait until all reachable instantiations are done?
  • Do you want a new (*ssa.Function).Done() that waits until a function is done being built?
  • Something else?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
4 participants
@aykevl @timothy-king @gopherbot @thanm