What’s happening here? And when?

A while ago, I posted to the Go users list about what seemed like a problem in how Go was choosing registers versus global variables. Roger’s answer was “go RTFM“, which was precisely the right thing to do. However, it took reading it twice (I’d read it before) and some hard pondering to connect what I was reading to what I was seeing.

In order to save you, the reader, from the same experience, here’s a more detailed explanation of how “happens before” applies to programs where coroutines are writing to and reading from globals. Disclaimer: You really shouldn’t be doing this. In Go, you “share memory by communicating, not communicate by sharing memory”. Asking questions about “what happens when two coroutines write to a global?” means you are already thinking about communicating by sharing, and you are in for a world of hurt. But in this case, I was exploring the concurrency model in coroutines in the absence of calls into the runtime (i.e. cooperative or not?) and so I wanted to avoid channels.

OK, on to the (broken) code:

package main
import "runtime"

var i int

func f(inc int) {
        for {
                i += inc
        }
}

func main() {
        runtime.GOMAXPROCS(3)
        go f(1)
        go f(-1)
        runtime.Gosched()

        for j := 0; ; j++ {
                if (j % 1e9) == 0 {
                        print(i, "\n")
                }
        }
} 

The idea here is to get two uncooperative goroutines (i.e. grabbing the CPU and never giving it back) onto two cores, and then watch what happens from the third goroutine. “Watch what happens” is secret code for “communicate by sharing memory” and we’ve already established that’s a bad idea. Thus it should be no surprise to the reader at this point that the output of main is all zeros, instead of the occasional -1, -2 or 100 or whatever you might have expected.

Looking at the assembly (using “8g -S”) we can see why main() never sees the results from f()’s work:

--- prog list "f" ---
0000 (hog.go:7) TEXT    f+0(SB),$0-4
0001 (hog.go:7) MOVL    inc+0(FP),CX
0002 (hog.go:7) MOVL    i+0(SB),AX
0003 (hog.go:8) JMP     ,5
0004 (hog.go:8) JMP     ,7
0005 (hog.go:9) ADDL    CX,AX
0006 (hog.go:8) JMP     ,5
0007 (hog.go:11) RET     ,

The problem is that the global i is loaded into AX and incremented there, without ever being written back into the memory location where i came from. So main() can’t see it going up and down, because i exists in three different places, the AX for f(1), the AX for f(-1) and the global that main() is looking at.

Is this a bug in Go’s register allocation? No, it is the result of the “happens before” analysis described in The Go Memory Model. Go read that now, you need to understand that to understand the rest…

The examples in The Go Memory Model do not clearly cover this case, and I found it a bit hard to reason about it until I started unrolling the loops in my head so that the program looks like this:

package main
var i int

func f(inc int) {
  i += inc  // 1
  i += inc  // 2
  i += inc  // 3
  ...
}

func main() {
  go f(1);
  go f(-1);

  // in practice, you'd need this to get them running, but it's
  // not important for this analysis
  //runtime.Gosched()

  println(i)  // 4
  println(i)  // 5
  ...
}

The happens-before relation for line 1 and line 2 is governed by the rule that inside a goroutine, program order determines happens-before. The happens-before relation for 4 and 5 are likewise defined. The problem comes when you consider the happens-before order of lines 1 and 4. It is not defined, because the only definition of happens-before that spans goroutines is that implied by sends and receives on a channel.

In fact, by adding a channel to the program, you can make the register assignment I originally complained about go away because you are fixing the happens-before order to be something that the Go compiler can only guarantee by writing to a global and not to a register:

package main
import "runtime"

var x int
var ch = make(chan bool)

func f(inc int) {
  for {
    x += inc
    ch <- true
    println("f: ", inc)
  }
}

func main() {
  go f(1)
  go f(-1)
  runtime.Gosched()

  for {
    _ = <- ch
    println(x)
  }
}

Looking at f() in assembly now gives the right answer:

--- prog list "f" ---
0000 (hog8.go:8) TEXT    f+0(SB),$24-4
0001 (hog8.go:9) JMP     ,3
0002 (hog8.go:9) JMP     ,23
0003 (hog8.go:10) MOVL    inc+0(FP),BX
0004 (hog8.go:10) ADDL    BX,x+0(SB)
... send on channel is here, not interesting for our needs ...
0022 (hog8.go:9) JMP     ,3
0023 (hog8.go:14) RET     ,

Notice how the compiler realized that, because there is a channel send coming up, that the add must happen out in memory (ADDL BX,x+0(SB)) and not in the register as before.

This program uncovers a new strange behavior, however. With GOMAXPROCS=1, it runs f(1),f(1),f(-1),main in a loop, resulting in i incrementing without bound. With GOMAXPROCS=3, it does the expected thing, where i stays around zero, but sometimes goes up and down. I will try looking into that little mystery another time, stay tuned!