Friday, June 27, 2014

Ice Cream Makers and Data Races Part II

Introduction
Dave Cheney published a post called Ice Cream Makers and Data Races. The post showed an example of an interesting data race that can occur when using an interface typed variable to make a method call. If you have not read the post yet please do. Once you read the post you will discover that the problem lies with the fact that an interface value is implemented internally using a two word header and that the Go memory model states only writes to a single word are atomic.

The program in the post shows a race condition that allows two goroutines to perform a read and write operation at the same time against an interface value. Not synchronizing this read and write allows the read to observe a partial write to the interface value. This allows the method implementation for the Ben type to operate against a value of the Jerry type and visa versa.

In Dave's example, the layout of the Ben and Jerry structs were identical in memory, so they were in some sense compatible. Dave suggested the chaos that would occur if they had different memory representations. This is because each implementation of the Hello method assumes the code is operating against values of the receiver type. When this bug surfaces, this is no longer the case. To give you a visual view of this suggested chaos, I am going to change the declaration of the Jerry type in two different ways. Both changes will give you some better insight into the interworking of interface types and memory.

First Code Change
Let's review the code and see the first set of changes. My changes to the original code are in bold:

01 package main
02
03 import "fmt"
04
05 type IceCreamMaker interface {
06    // Great a customer.
07    Hello()
08 }
09
10 type Ben struct {
11    name string
12 }
13
14 func (b *Ben) Hello() {
15    if b.name != "Ben" {
16        fmt.Printf("Ben says, \"Hello my name is %s\"\n", b.name)
17    }
18 }
19
20 type Jerry struct {
21    field1 *[5]byte
22    field2 int
23 }
24
25 func (j *Jerry) Hello() {
26    name := string((*j.field1)[:])
27    if name != "Jerry" {
28        fmt.Printf("Jerry says, \"Hello my name is %s\"\n", name)
29    }
30 }
31
32 func main() {
33    var ben = &Ben{"Ben"}
34    var jerry = &Jerry{&[5]byte{'J', 'e', 'r', 'r', 'y'}, 5}
35    var maker IceCreamMaker = ben
36
37    var loop0, loop1 func()
38
39    loop0 = func() {
40    maker = ben
41    go loop1()
42    }
43
44    loop1 = func() {
45        maker = jerry
46        go loop0()
47    }
48
49    go loop0()
50
51    for {
52        maker.Hello()
53    }
54 }

In the implementation of the Hello method for the Ben type on lines 14 through 18, I changed the code to only display the message when the name is not Ben. This is a simple change so we don't have to go through the results looking for when the bug surfaces.

Then on lines 20 through 23, I completely changed out the declaration of the Jerry type. The declaration is now a manual representation of a string. A string in Go consists of a header with two words. The first word is a pointer to an array of bytes and the second word is the length of the string. This is similar to a slice but without the third word in the header for the capacity. The declarations of the Ben and Jerry structs represent the same memory layout though declared very differently.

The idea of changing the Jerry type in this fashion is to show how serious this data race condition Dave created is. When the implementation of Hello method for the Ben type is called, the Printf function is going to print the characters for the name field. When the Hello implementation for type Ben is called using a value of type Jerry, the memory associated with the name field could be anything. In this case we are guaranteeing that there is a string representation so the code does not stack trace, but doing this by unusual means.

One lines 25 through 30, I changed the implementation of the Hello method for the Jerry type. I convert the byte array to a string and use the new name variable to check and display the value. Since the declaration of the name field in the Ben type is equivalent to the declaration of the two fields declared in the Jerry type, everything will print out appropriately.

Finally on line 34, I create and initialize the variable of type Jerry, setting the bytes and length. Then the rest of the code remains as is.

Running The Program
When we run this new version of the program the output does not change at all:

Jerry says, "Hello my name is Ben"
Ben says, "Hello my name is Jerry"
Ben says, "Hello my name is Jerry"
Jerry says, "Hello my name is Ben"
Ben says, "Hello my name is Jerry"

Even though the declaration of the Ben and Jerry types are different, the memory layouts are the same and the program runs as designed:

type Ben struct {
   name string
}

type Jerry struct {
   field1 *[5]byte
   field2 int
}

fmt.Printf("Ben says, \"Hello my name is %s\"\n", b.name)

name := string((*j.field1)[:])
fmt.Printf("Jerry says, \"Hello my name is %s\"\n", name)

In the case of the Printf function call for the Ben type implementation of the Hello method, the code thinks the b pointer is pointing to a value of type Ben when it is not. However, since the memory layout is the same between the Ben and Jerry types, the call to the Printf function still works. The same is true for the implementation of the Hello method for the Jerry type. The values of field1 and field2 are equivalent to declaring a string field so everything works.

Crashing The Program
Let's change the code one more time. This time we will make the Jerry type incompatible with the Ben type:

01 package main
02
03 import "fmt"
04
05 type IceCreamMaker interface {
06    // Great a customer.
07    Hello()
08 }
09
10 type Ben struct {
11    name string
12 }
13
14 func (b *Ben) Hello() {
15    if b.name != "Ben" {
16        fmt.Printf("Ben says, \"Hello my name is %s\"\n", b.name)
17    }
18 }
19
20 type Jerry struct {
21    field2 int
22    field1 *[5]byte
23 }
24
25 func (j *Jerry) Hello() {
26    name := string((*j.field1)[:])
27    if name != "Jerry" {
28        fmt.Printf("Jerry says, \"Hello my name is %s\"\n", name)
29    }
30 }
31
32 func main() {
33    var ben = &Ben{"Ben"}
34    var jerry = &Jerry{5, &[5]byte{'J', 'e', 'r', 'r', 'y'}}
35    var maker IceCreamMaker = ben
36
37    var loop0, loop1 func()
38
39    loop0 = func() {
40    maker = ben
41    go loop1()
42    }
43
44    loop1 = func() {
45        maker = jerry
46        go loop0()
47    }
48
49    fmt.Printf("Ben: %p Jerry: %p\n", ben, jerry)
50
51    go loop0()
52
53    for {
54        maker.Hello()
55    }
56 }

Now the declaration of the Jerry type between lines 20 through 23 switches the order of the two field members. The integer value now comes before the byte array pointer. When we run this version of the program we get a stack trace:

Ben: 0x20817a170 Jerry: 0x20817a180

01 panic: runtime error: invalid memory address or nil pointer dereference
02 [signal 0xb code=0x1 addr=0x5 pc=0x294f6]
03
04 goroutine 16 [running]:
05 runtime.panic(0xb90e0, 0x144144)
06    /Users/bill/go/src/pkg/runtime/panic.c:279 +0xf5
07 fmt.(*fmt).padString(0x2081b42d0, 0x5, 0x20817a190)
08    /Users/bill/go/src/pkg/fmt/format.go:130 +0x390
09 fmt.(*fmt).fmt_s(0x2081b42d0, 0x5, 0x20817a190)
10    /Users/bill/go/src/pkg/fmt/format.go:285 +0x67
11 fmt.(*pp).fmtString(0x2081b4270, 0x5, 0x20817a190, 0x73)
12    /Users/bill/go/src/pkg/fmt/print.go:511 +0xe0
13 fmt.(*pp).printArg(0x2081b4270, 0x97760, 0x20817a210, 0x73, 0x0, 0x0)
14    /Users/bill/go/src/pkg/fmt/print.go:780 +0xbb8
15 fmt.(*pp).doPrintf(0x2081b4270, 0xddfd0, 0x20, 0x220832de40, 0x1, 0x1)
16    /Users/bill/go/src/pkg/fmt/print.go:1159 +0x1ecc
17 fmt.Fprintf(0x220818c340, 0x2081c2008, 0xddfd0, 0x20, 0x220832de40, 0x1, 0x1, 0x10, 0x0, 0x0)
18     /Users/bill/go/src/pkg/fmt/print.go:188 +0x7f
19 fmt.Printf(0xddfd0, 0x20, 0x220832de40, 0x1, 0x1, 0x5, 0x0, 0x0)
20    /Users/bill/go/src/pkg/fmt/print.go:197 +0xa2
21 main.(*Ben).Hello(0x20817a180)
22    /Users/bill/Spaces/Go/Projects/src/github.com/goinaction/code/temp/main.go:16 +0x118
23 main.main()
24    /Users/bill/Spaces/Go/Projects/src/github.com/goinaction/code/temp/main.go:54 +0x2c3

If we look at line 21 of the stack trace we will see how the method call to Hello is using the implementation for type Ben but being passed the address of the value for type Jerry. Just before the stack trace I display the addresses of each value to make this clear. If we look at the declaration of the Ben and Jerry types one more time we can see how they are no longer compatible:

type Ben struct {
   name string
}

type Jerry struct {
   field2 int
   field1 *[5]byte
}

Since this new declaration for type Jerry now starts with an integer value, it is not compatible with a string type. This time when the code tries to print the value of b.name on line 16, the program stack traces.

Conclusion
In the end, a running program manipulates memory without any safeguards from the compiler. Memory is just memory and the CPU will interpret that memory as it is told. In the crash example, thanks to the data race bug, the code asked the CPU to interpret an integer value as a string and the program crashed. So I agree with Dave, there is no such thing as a safe data race. Your program either has no data races, or its operation is undefined.

Cherry On Top
After reading both posts you might be disappointed that no ice cream was actually used in the writing of these posts. If you're bummed out now and wished you had some coupons, I found a link to signup for the Ben and Jerry's newsletter. You can also find a store near you.