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.

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

cmd/compile: global variable initialization done in unexpected order #51913

Open
jcp19 opened this issue Mar 24, 2022 · 24 comments
Open

cmd/compile: global variable initialization done in unexpected order #51913

jcp19 opened this issue Mar 24, 2022 · 24 comments
Assignees
Labels
NeedsFix
Milestone

Comments

@jcp19
Copy link

@jcp19 jcp19 commented Mar 24, 2022

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

$ go version
go version go1.16.4 darwin/amd64

Does this issue reproduce with the latest release?

Yes

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

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/joao/Library/Caches/go-build"
GOENV="/Users/joao/Library/Application Support/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/joao/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/joao/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/Cellar/go/1.16.4/libexec"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/Cellar/go/1.16.4/libexec/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.16.4"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/2d/wcw2b3c57jz69cl5tg_s2fx00000gn/T/go-build3928827666=/tmp/go-build -gno-record-gcc-switches -fno-common"
GOROOT/bin/go version: go version go1.16.4 darwin/amd64
GOROOT/bin/go tool compile -V: compile version go1.16.4
uname -v: Darwin Kernel Version 21.3.0: Wed Jan  5 21:37:58 PST 2022; root:xnu-8019.80.24~20/RELEASE_X86_64
ProductName:	macOS
ProductVersion:	12.2.1
BuildVersion:	21D62
lldb --version: lldb-1103.0.22.10
Apple Swift version 5.2.4 (swiftlang-1103.0.32.9 clang-1103.0.32.53)

What did you do?

I have a package consisting of the following two files:

f1.go

package main    
   
var A int = 3    
var B int = A + 1    
var C int = A

f2.go

package main    
   
import "fmt"    
                     
var D = f()      
   
func f() int {    
  A = 1    
  return 1    
}    
   
func main() {    
  fmt.Println(A, B, C)    
}  

What did you expect to see?

According to the Go language specification, "package-level variable initialization proceeds stepwise, with each step selecting the variable earliest in declaration order which has no dependencies on uninitialized variables".

As such, I would expect two possible orders in which the global variables can be initialized:

  1. A < B < C < D - happens when you compile the project by passing f1.go first to the compiler, followed by f2.go . In this case, the output is "1 4 3"
  2. A < D < B < C - happens when f2.go is passed first to the compiler. In this case, the expected output would be "1 2 1".

What did you see instead?

For the second case (when f2.go is passed first), the actual output is "1 2 3". If instead I rewrite file f1.go to the following, I get the expected output for case 2.

Rewritten f2.go

package main    
   
import "fmt"    
   
var A int = initA()    
var B int = initB()    
var C int = initC()    
     
func initA() int {    
  fmt.Println("Init A")    
  return 3    
}    
     
func initB() int {    
  fmt.Println("Init B")    
  return A + 1    
}    
 
func initC() int {    
  fmt.Println("Init C")    
  return A    
} 

Output

Init A
Init B
Init C
1 2 1

Additional Information

This issue was first discussed in the golang-nuts Google Group (link).

@go101
Copy link

@go101 go101 commented Mar 24, 2022

A little clarification: OP means the outputs are different between go run f1.go f2.go and go run f2.go f1.go. And after rewriting f1.go, things changes a bit.

By the specification, the outputs should be always 1 4 3.

@candlerb
Copy link

@candlerb candlerb commented Mar 24, 2022

By the specification, the outputs should be always 1 4 3.

The two scenarios are:

  • f1.go f2.go: declaration order is A B C D
  • f2.go f1.go: declaration order is D A B C

In the first case it's simple:

  • A is set to 3
  • B is set to 4
  • C is set to 3
  • D is set to 1, and A is set to 1 as a side-effect

Expected result: 1 4 3

In the second case, I come to a different conclusion from reading the spec than you:

  • D is not ready because it depends on A
  • A is set to 3
  • D is now "the next package-level variable that is earliest in declaration order and ready for initialization", so it gets set to 1, and A is set to 1 as a side-effect
  • B is set to 2
  • C is set to 1

Expected result: 1 2 1

That is, I read "next" to mean "the next variable to be initialized", not "the next variable following sequentially after the one which was last initialized". Is this an incorrect reading?

@mknyszek mknyszek changed the title package-initialization: global variable initialization done in unexpected order runtime: global variable initialization done in unexpected order Mar 24, 2022
@mknyszek mknyszek added this to the backlog milestone Mar 24, 2022
@mknyszek mknyszek removed this from the backlog milestone Mar 24, 2022
@mknyszek mknyszek added this to the Backlog milestone Mar 24, 2022
@mknyszek mknyszek added the NeedsInvestigation label Mar 24, 2022
@mknyszek
Copy link
Contributor

@mknyszek mknyszek commented Mar 24, 2022

CC @golang/runtime

For additional context, see #31292. Unclear if this is a bug yet, but since it also involves the spec, CC @griesemer who was central to #31292.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Mar 24, 2022

Edited. There appears to be a bug in the compiler. See #51913 (comment).

This is working as intended. Note that the spec also says:

The declaration order of variables declared in multiple files is determined by the order in which the files are presented to the compiler: Variables declared in the first file are declared before any of the variables declared in the second file, and so on.

We don't need multiple files, we can just arrange the variable declarations accordingly. In the first case:

package main

var A int = 3
var B int = A + 1
var C int = A
var D = f()

func f() int {
	A = 1
	return 1
}

func main() {
	println(A, B, C, D)
}

the output is

1 4 3 1

Here's the corresponding trace from the type checker's initialization order computation (this is the trace produced by types2 which is used by the compiler, but note that at the moment the compiler still uses its own init order computation and not the types2 computation - still they match):

Computing initialization order for package main ("main")

Object dependency graph:
        A has no dependencies
        B depends on
                A
        C depends on
                A
        D depends on
                f
        f depends on
                A
        main depends on
                A
                B
                C
                D

Transposed object dependency graph (functions eliminated):
        A depends on 0 nodes
                B is dependent
                C is dependent
                D is dependent
        C depends on 1 nodes
        B depends on 1 nodes
        D depends on 1 nodes

Processing nodes:
        A (src pos 1) depends on 0 nodes now
        B (src pos 2) depends on 0 nodes now
        C (src pos 3) depends on 0 nodes now
        D (src pos 4) depends on 0 nodes now

Initialization order:
        A = 3
        B = A + 1
        C = A
        D = f()

For the 2nd case:

package main

var D = f()

func f() int {
	A = 1
	return 1
}

func main() {
	println(A, B, C, D)
}

var A int = 3
var B int = A + 1
var C int = A

the output is

1 2 3 1

and the corresponding init computation trace is:

Computing initialization order for package main ("main")

Object dependency graph:
        D depends on
                f
        f depends on
                A
        main depends on
                A
                B
                C
                D
        A has no dependencies
        B depends on
                A
        C depends on
                A

Transposed object dependency graph (functions eliminated):
        A depends on 0 nodes
                D is dependent
                B is dependent
                C is dependent
        D depends on 1 nodes
        C depends on 1 nodes
        B depends on 1 nodes

Processing nodes:
        A (src pos 4) depends on 0 nodes now
        D (src pos 1) depends on 0 nodes now
        B (src pos 5) depends on 0 nodes now
        C (src pos 6) depends on 0 nodes now

Initialization order:
        A = 3
        D = f()
        B = A + 1
        C = A

Thus, in this case D gets initialized before B because it's before B in the source. This explains the difference.

Closing.

@aarzilli
Copy link
Contributor

@aarzilli aarzilli commented Mar 24, 2022

In the second case, if f runs before the assignemnt to C shouldn't that see the side effect of the call to f?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Mar 24, 2022

@aarzilli Good catch, I totally glanced over this. Indeed go/types and types2 compute the correct initialization order (currently not used by the compiler), while the compiler still has a bug here, I think. Re-opening.

For the 1st case:

  1. A is set to 3. Variable state is: A = 3, B = 0, C = 0, D = 0.
  2. B is set to A + 1. Variable state is: A = 3, B = 4, C = 0, D = 1.
  3. C is set to A. Variable state is: A = 3, B = 4, C = 3, D = 0.
  4. D is set to 1 (result of f()), and A is set to 1. Variable state is: A = 1, B = 4, C = 3, D = 1.

For the 2nd case:

  1. A is set to 3. Variable state is: A = 3, B = 0, C = 0, D = 0.
  2. D is set to 1 (result of f()), and A is set to 1. Variable state is: A = 1, B = 0, C = 0, D = 1.
  3. B is set to A + 1. Variable state is: A = 1, B = 2, C = 0, D = 1.
  4. C is set to A. Variable state is: A = 1, B = 2, C = 1, D = 1.

@griesemer griesemer reopened this Mar 24, 2022
@griesemer griesemer changed the title runtime: global variable initialization done in unexpected order cmd/compile: global variable initialization done in unexpected order Mar 24, 2022
@griesemer
Copy link
Contributor

@griesemer griesemer commented Mar 24, 2022

Related issue: #49150

@griesemer
Copy link
Contributor

@griesemer griesemer commented Mar 24, 2022

cc: @mdempsky It looks like cmd/compile may still have an issue with initialization order. Maybe it's time to switch to the types2-determined order?

cc: @ianlancetaylor for gccgo results for these two cases.

@griesemer griesemer removed this from the Backlog milestone Mar 24, 2022
@griesemer griesemer added this to the Go1.19 milestone Mar 24, 2022
@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 24, 2022

The compiler issue here is that we optimize var X = 3; var Y = X into var X = 3; var Y = 3, even when there might be user function calls that could modify X's value before the spec says Y is initialized.

Unfortunately, I think this is more complex than just switching to types2's initialization order. I think cmd/compile is already correctly sorting the initialization statements; it's just misapplying an optimization that isn't actually safe. (And it looks like gccgo has a similar issue.)

The easy fix is to just disable that optimization, but that might lead to more dynamic initialization.

The more complex fix would involve actually tracking when user-written calls are sequenced during initialization, and keeping track of which global variables they might clobber, and how that limits subsequent optimization opportunities.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 24, 2022

Here's a minimal repro of the issue, btw:

package main

var _ = func() int {
	a = false
	return 0
}()

var a = true
var b = a

func main() {
	if b {
		panic("FAIL")
	}
}

The Go spec says this program should silently exit with success. But instead it currently panics when compiled with either cmd/compile or gccgo.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 24, 2022

Change https://go.dev/cl/395541 mentions this issue: cmd/compile: disable unsafe staticinit optimization

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Mar 24, 2022

I changed gccgo to match gc's behavior because the runtime package requires it (https://go.dev/cl/245098). I see that CL 395541 keeps the optimizations only for the runtime package, so I guess I'll do the same in gccgo.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 24, 2022

I changed gccgo to match gc's behavior because the runtime package requires it (https://go.dev/cl/245098).

Thanks for the reference. For what it's worth, it looks like replacing var maxSearchAddr = maxOffAddr with func maxSearchAddr() offAddr { return maxOffAddr } and then changing uses of maxSearchAddr to maxSearchAddr() seems to eliminate the need for special casing package runtime in CL 395541.

I don't feel strongly about which way to proceed here. In general, I prefer fewer special cases for package runtime, in hopes that there are fewer surprises for the runtime team when switching between writing Standard Go and Runtime Go. But package initialization is already inherently weird for package runtime, and it seems unlikely the runtime team is going to write any tricky initializers that would interfere with this optimization.

If anyone else leans one way or the other here, let me know.

/cc @aclements @mknyszek @prattmic

@aclements
Copy link
Member

@aclements aclements commented Mar 25, 2022

I would also prefer that we not special-case the runtime here, especially if there's only one problem right now.

Is the issue with maxSearchAddr that we currently statically initialize it, but with CL 395541, it now gets dynamically initialized but the runtime depends on its value before it calls runtime.init? I don't see any dynamic assignments to either maxSearchAddr or maxOffAddr.

(It's too bad we don't have const structs. Then there would be an easy solution for maxSearchAddr. :P)

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Mar 25, 2022

Yes, if maxSearchAddr is initialized dynamically then it is initialized when we run package initialization in the call to doInit in main in proc.go. But long before that the code will use maxSearchAddr in pageAlloc.init called via mallocinit and schedinit. In an ordinary package this problem would be handled, but the runtime package initializes things outside of init functions.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 26, 2022

Change https://go.dev/cl/395994 mentions this issue: compiler: revert for package-scope "a = b; b = x" just set "a = x"``

@go101
Copy link

@go101 go101 commented Mar 26, 2022

About source file order in a package, will it be better to always sort files in a package before compiling, to remove some unspecified behaviors?

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 26, 2022

About source file order in a package, will it be better to always sort files in a package before compiling, to remove some unspecified behaviors?

The Go spec recommends build systems to do that, and cmd/go already does when invoking cmd/compile.

@go101
Copy link

@go101 go101 commented Mar 26, 2022

Why not compulsively?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Mar 26, 2022

That doesn't seem like an aspect that should be determined in a language spec.

In any case no reason to change it now.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 28, 2022

Change https://go.dev/cl/396194 mentions this issue: runtime: change maxSearchAddr into a helper function

gopherbot pushed a commit to golang/gofrontend that referenced this issue Apr 15, 2022
Revert CL 245098.  It caused incorrect initialization ordering.

Adjust the runtime package to work even with the CL reverted.

Original description of CL 245098:

    This avoids requiring an init function to initialize the variable.
    This can only be done if x is a static initializer.

    The go1.15rc1 runtime package relies on this optimization.
    The package has a variable "var maxSearchAddr = maxOffAddr".
    The maxSearchAddr variable is used by code that runs before package
    initialization is complete.

For golang/go#51913

Change-Id: I07a896da3d97c278bd144d95238bdd3f98c9a1ab
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/395994
Reviewed-by: Cherry Mui <cherryyz@google.com>
Reviewed-by: Than McIntosh <thanm@google.com>
xionghul pushed a commit to xionghul/gcc that referenced this issue Apr 15, 2022
Revert CL 245098.  It caused incorrect initialization ordering.

Adjust the runtime package to work even with the CL reverted.

Original description of CL 245098:

    This avoids requiring an init function to initialize the variable.
    This can only be done if x is a static initializer.

    The go1.15rc1 runtime package relies on this optimization.
    The package has a variable "var maxSearchAddr = maxOffAddr".
    The maxSearchAddr variable is used by code that runs before package
    initialization is complete.

For golang/go#51913

Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/395994
gopherbot pushed a commit that referenced this issue May 11, 2022
This avoids a dependency on the compiler statically initializing
maxSearchAddr, which is necessary so we can disable the (overly
aggressive and spec non-conforming) optimizations in cmd/compile and
gccgo.

Updates #51913.

Change-Id: I424e62c81c722bb179ed8d2d8e188274a1aeb7b6
Reviewed-on: https://go-review.googlesource.com/c/go/+/396194
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@gopherbot
Copy link

@gopherbot gopherbot commented May 11, 2022

Change https://go.dev/cl/405549 mentions this issue: runtime: avoid staticinit dependency with sigsetAllExiting

@mdempsky
Copy link
Member

@mdempsky mdempsky commented May 11, 2022

@gopherbot Please backport to Go 1.18. This is a silent miscompilation of valid (albeit unlikely) code.

@gopherbot
Copy link

@gopherbot gopherbot commented May 11, 2022

Backport issue(s) opened: #52857 (for 1.18).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

@prattmic prattmic added NeedsFix and removed NeedsInvestigation labels May 20, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsFix
Projects
Status: In Progress
Development

No branches or pull requests