Memory Order Guarantees In Go

About Memory Ordering

Modern compilers (at compile time) and CPU processors (at run time) often make some optimizations by adjusting the instruction orders, so that the instruction execution orders may differ from the orders presented in code.

(Instruction reordering is also often called memory ordering.)

Surely, instruction reorderings are not arbitrary. The basic requirement for a reordering inside a specified goroutine is the reordering must not be detectable by the gorotuine itself if the goroutine doesn't share data with other goroutines. In other words, from the perspective of such a goroutine, it can think its instruction execution order is always the same as the order specified by code, even if there are really some instruction reorderings happening inside it.

However, if some goroutines share some data, instruction reorderings happen inside one of these goroutine may be observed by the others goroutines, and affact the behaviors of all these goroutines. Sharing data between goroutines is common in concurrent programming, if we ignore the results caused by instruction reordering, the behaviors of our concurrent programs might compiler and CPU dependent, and often abnormal.

Here is an unprofessional Go program which doesn't consider instruction reordering. the program is expanded from an example in Go 1 memory model.
package main

import "runtime"

var a string
var done bool

func setup() {
	a = "hello, world"
	done = true
}

func main() {
	go setup()

	for !done {
		runtime.Gosched()
	}
	println(a) // expect to print: hello, world
}
The behavior of this program is very possible as we expect, a hello, world text will be printed. However, the behavior of this program is compiler and CPU dependent. If the program is compiled with a different compiler, or it runs on a different architecture, it may print nothing, or a text different from hello, world. The reason is compilers and CPUs may exchange the execution orders of the two lines in the setup function, so the final effect of the setup function may become to
func setup() {
	done = true
	a = "hello, world"
}

The setup goroutine in the above program will not observe the reordering, however, the main goroutine will.

Besides the reordering problem, there are data races in the program. There are not any synchronizations made in accessing the variable a and done. So, the above program is a showcase full of concurrent programming mistakes. A professional Go programmer should not make these mistakes.

Go Memory Model

Sometimes, we need to ensure that the execution of some code lines in a goroutine must happen before (or after) the execution of some code lines in another goroutine, to keep the correctness of a program. Instruction reorderings may cause some troubles for such circumstances. How should we do to prevent some possible instruction reorderings?

Different CPU architectures provide different fence instructions to prevent different kinds of instruction reorderings. Some programming languages provide corresponding functions to insert these fence instructions in code. However, understanding and correctly using the fence instructions raises the bar of concurrent programming.

The design philosophy of Go is to use as fewer features as possible to support as more use cases as possible, at the same time to ensure a good enough overall code execution efficiency. So Go built-in and standard packages don't provide direct ways to use the CPU fence instructions. In fact, in Go, we can use some kinds of the synchronization methods in Go to ensure expected code execution orders.

Following will list some guaranteed (and non-guaranteed) code execution orders, which are mentioned or not mentioned in Go 1 memory model and other official Go documentations.

In the following descriptions, if we say event A is guaranteed to happen before event B, it means any of the goroutines involved in the two events will observe that any of the statements presented before event A in source code will be executed before any of the statements presented after event B in source code. For other irrelevant goroutines, the observed orders may be different from the just described.

init Functions Related Order Guarantees

Go memory model mentions the two init functions related order guarantees: In fact, there is two other order guarantees:

The Creation Of A Goroutine Happens Before The Execution Of The Goroutine

In the following function, the assignment x, y = 123, 789 will be executed before the call fmt.Println(x), and the call fmt.Println(x) will be executed before the call fmt.Println(y).
var x, y int
func f1() {
	x, y = 123, 789
	go func() {
		fmt.Println(x)
		go func() {
			fmt.Println(y)
		}()
	}()
}
However, the executon orders of the three in the following function are not deterministic. There are data races in this function.
var x, y int
func f2() {
	go func() {
		fmt.Println(x) // might print 0, 123, or some others.
	}()
	go func() {
		fmt.Println(y) // might print 0, 789, or some others.
	}()
	x, y = 123, 789
}

Channel Related Order Guarantees

The following listed guarantees are not mentioned in Go 1 memory model, but I think they are obvious. Go 1 memory model lists the following three channel related order guarantees.
  1. The nth successful send to a channel happens before the nth successful receive from that channel completes, no matter that channel is buffered or unbuffered.
  2. The nth successful receive from a channel with capacity m happens before the (n+m)th send to that channel completes. In particular, if that channel is unbuffered (m == 0), the nth successful receive from that channel happens before the nth successful send on that channel completes.
  3. The closing of a channel happens before a receive completes if the receive returns a zero value because the channel is closed.

Please note, all above order guarantees are made for the involved goroutines. For other irrelevant goroutines, the observed orders may be different from the above described.

Here is an example show some guaranteed code execution orders in using an unbuffered channel.
func f() {
	var a, b int
	var c = make(chan bool)

	go func() {
		a = 1
		c <- true
		if b != 1 { // impossible
			panic("b != 1") // will never happen
		}
	}()

	go func() {
		b = 1
		<-c
		if a != 1  { // impossible
			panic("a != 1") // will never happen
		}
	}()
}
Here, for the two new created goroutines, the following orders are guaranteed: So the two calls to panic in the above example will never get executed. However, the panic calls in the following example may get executed.
func f() {
	var a, b, x, y int
	c := make(chan bool)

	go func() {
		a = 1
		c <- true
		x = 1
	}()

	go func() {
		b = 1
		<-c
		y = 1
	}()

	// Many data races are in this goroutine.
	// Don't write code as such.
	go func() {
		if x == 1 {
			if a != 1 { // possible
				panic("a != 1") // may happen
			}
			if b != 1 { // possible
				panic("b != 1") // may happen
			}
		}

		if y == 1 {
			if a != 1 { // possible
				panic("a != 1") // may happen
			}
			if b != 1 { // possible
				panic("b != 1") // may happen
			}
		}
	}()
}

Here, for the third goroutine, which is irrelevant to the operations on channel c, will not be guaranteed to observe the orders observed by the first two new created goroutines. So, any of the four panic calls may get executed.

In fact, most compiler implementations do guarantee the four panic calls in the above example will never get executed, however, none of the Go official documentations make such guarantees. So the code in the above example is not cross-compiler or cross-compiler-version compatible. We should stick to the Go official documentations to write professional Go code.

Here is an example using an unbuffered channel.
func f() {
	var k, l, m, n, x, y int
	c := make(chan bool, 2)

	go func() {
		k = 1
		c <- true
		l = 1
		c <- true
		m = 1
		c <- true
		n = 1
	}()

	go func() {
		x = 1
		<-c
		y = 1
	}()
}
The following orders are guaranteed:

The execution of x = 1 is not guaranteed to happen before the execution of l = 1 and m = 1, and the execution of l = 1 and m = 1 is not guaranteed to happen before the execution of y = 1.

The following is an example on channel closing. In this example, the execution of k = 1 is guaranteed to happen before the execution of y = 1, but not guaranteed to happen before the execution of x = 1,
func f() {
	var k, x, y int
	c := make(chan bool, 1)

	go func() {
		c <- true
		k = 1
		close(c)
	}()

	go func() {
		<-c
		x = 1
		<-c
		y = 1
	}()
}

Mutex Related Order Guarantees

Followings are the mutex related order guarantees in Go.
  1. For an addressable value l of type Mutex or RWMutex in the sync standard package, the nth successful call of l.Unlock() happens before the (n+1)th successful call of l.Lock() returns.
  2. For an addressable value l of type RWMutex, if a call of l.Lock() has returned successfully, then the next successful call of l.Unlock() will happen before the return of any call of l.RLock() which has not started or returned yet.
  3. For an addressable value l of type RWMutex, if the nth successful call of l.RLock() has returned, then the mth successful call of l.RUnlock(), where m <= n, happens before the return of any call of l.Lock() which has not started or returned yet.
In the following exanmple, the following orders are guaranteed:
func fab() {
	var a, b int
	var l sync.RWMutex

	l.Lock()
	go func() {
		l.Lock()
		b = 1
		l.Unlock()
	}()
	go func() {
		a = 1
		l.Unlock()
	}()
}

func fmn() {
	var m, n int
	var l sync.RWMutex

	l.RLock()
	go func() {
		l.Lock()
		n = 1
		l.Unlock()
	}()
	go func() {
		m = 1
		l.RUnlock()
	}()
}

func fxy() {
	var x, y int
	var l sync.RWMutex

	l.Lock()
	go func() {
		l.RLock()
		y = 1
		l.RUnlock()
	}()
	go func() {
		x = 1
		l.Unlock()
	}()
}

Order Guarantees Made By sync.WaitGroup Values

Assume at a given time, the counter maintained by an addressable sync.WaitGroup value wg is not zero, and after the given time, a wg.Add (or wg.Done) method call and a wg.Wait method call are made. As long as we can confirm that the counter never becomes to zero before the wg.Add (or wg.Done) method call returns (and after the given time), the wg.Add (or wg.Done) method call is guaranteed to happen before any wg.Wait method call made after the given time returns.

Please read the explanations for sync.WaitGroup to get how to use sync.WaitGroup values.

Order Guarantees Made By sync.Once Values

For an addressable sync.Once value o, among all the o.Do calls, only exact one argument function will be invoked. The invoked argument function is guaranteed to return before any o.Do method call returns. In other words, the code in the invoked argument function is guaranteed to be executed before any o.Do method call returns.

Please read the explanations for sync.Once to get how to use sync.Once values.

Order Guarantees Made By sync.Cond Values

It is some hard to make a clear discription for the order guarantees made by an addressable sync.Cond value c. Simply put, if a c.Wait() call is guaranteed to be resumed by a c.Notify (or c.Broadcast) call, then the c.Notify (or c.Broadcast) call is guaranteed to happen before the c.Wait() call returns.

Please read the explanations for sync.Cond to get how to use sync.Cond values.

Atomic Related Order Guarantees

All above mentioned synchronization techniques make some memory order guarantees. These guarantees are well documented in all kinds of Go official documentations. However, none of Go official documentations mentions what memory order guarantees are made by the atomic synchronization technique.

In fact, in the implementation of the standard Go compiler, at least up to Go SDK 1.10, there are exactly some memory order guarantees made by atomic operations. The standard Go runtime relies extensively on the guarantees provided by atomic operations. For example, the following program always prints 1, if it is compiled with the standard Go compiler 1.10.
package main

import "fmt"
import "sync/atomic"
import "runtime"

func main() {
	var a, b int32 = 0, 0

	go func() {
		atomic.StoreInt32(&a, 1)
		atomic.StoreInt32(&b, 1)
	}()

	for {
		if n := atomic.LoadInt32(&b); n == 1 {
			// The following line always prints 1.
			fmt.Println(atomic.LoadInt32(&a))
			break
		}
		runtime.Gosched()
	}
}

Here, the main goroutine will always observe that the modification of a happens before the modification of b.

However, the guarantees made by atomic operations are not written down in the Go specification and other offcial Go documentations. If you want to write cross-compiler and cross-compile-version compatible Go code, the safe advice is, don't rely on atomic to guarantee memory orderings in general Go programming. There is an issue on how these guarantees should be written down. But, up to now (Go 1.10), the decision has not been made.

Please read this article to get how to do atomic operations.

The Go 101 project is hosted on both github and gitlab. Welcome to improve Go 101 articles by submitting corrections for all kinds of mistakes, such as typos, grammar errors, wording inaccuracies, description flaws and code bugs.