Go 1.3.1: The Bad Character

Go 1.3.1 shipped on 13 August 2014, eight weeks after Go 1.3.¹ Sixteen commits sit between the tags, and every one of the fifteen cherry-picks carries Andrew Gerrand's name, thirteen of them landed on 12 and 13 August. There is no blog post and the whole release note is one paragraph in the release history, complete with a doubled word: "bug fixes to the compiler and the the runtime, net, and crypto/rsa packages."¹

It is a point release in the classic mold: one miscompile, three panics, a spurious connect, and a compile-time fix worth ten times its weight.

The bad character#

The lead bug came from a service upgrade. After moving to Go 1.3, psnim2000's program started emitting garbage from a generator constrained to [A-Z0-9]: lowercase letters and punctuation where none should be possible, bytes the reporter was not even sure were valid UTF-8.²

Rémy Oudompheng reduced it to a byte modulo. His test, committed verbatim as test/fixedbugs/issue8325.go, indexes into an alphanumeric string with b % byte(len(alphanum)) and panics on anything outside [0-9A-Z].² The culprit was the byte-sized magic multiply in 6g and 8g: division by a constant gets compiled into a multiplication by a magic number, and the byte-sized version of that optimization got it wrong. Russ Cox's fix of 11 August corrects the code generation and adds the test.²

The test needs no adaptation. On the old toolchain it finds the bad character; on the new one it prints nothing:³

$ go run issue8325.go     # go1.3
found a bad character
panic: BUG
$ go run issue8325.go     # go1.3.1
$

The same byte-modulo expression, printing its result so there is something to see. Hit Run.

package main

import "fmt"

const alphanum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

func main() {
	bytes := []byte{95, 96, 83, 102, 88, 100}
	for i, b := range bytes {
		bytes[i] = alphanum[b%byte(len(alphanum))]
	}
	fmt.Printf("%q\n", bytes)
}

"NOBUGS"

Liveness, ten times faster#

Go 1.3's precise stacks were computed by a brand-new liveness analysis, and the analysis was slow. Brad Fitzpatrick filed the numbers: compiling a slice of interface literals took 0.003 seconds at 100 elements, 4 seconds at 5,000, and 29 seconds at 14,000, growing worse than linearly.⁴ A second report, table-driven test code taking forever to build, gave Russ Cox's fix its headline case: x.go compiling in 9.48 seconds before and 0.84 after.⁵

The fix, landed 6 August, has three parts: an O(n) variable lookup becomes O(1), an O(n²) check that exists purely for debugging now runs only under the debugging flags, and sparse bitmaps are iterated word by word.⁵ The commit message carries the full table, x100.go through x10000.go, topping out at 13.78 seconds against 2.09.

The shape reproduces exactly. Generating the issue's interface slices at 3,000 and 6,000 elements:³

$ time go build -o x3-13 x3000.go     # go1.3
real  0m0.731s
$ time go build -o x3-131 x3000.go    # go1.3.1
real  0m0.254s
$ time go build -o x6-13 x6000.go     # go1.3
real  0m2.626s
$ time go build -o x6-131 x6000.go    # go1.3.1
real  0m0.562s

Doubling the input nearly quadruples the old compiler's time (0.73 to 2.63 seconds) while the new one a bit more than doubles (0.25 to 0.56): 2.9x faster at 3,000 elements, 4.7x at 6,000.

Eight characters#

Jakob Borg reported that Go crashed parsing his resolv.conf: an off-by-one between a length check and a slice index meant any unrecognized eight-character option on an options line panicked the resolver.⁶ His example was options attempts 1, "attempts" being exactly eight letters.

The bug is one line in dnsconfig_unix.go: the guard reads len(s) >= 8 while the slice reads s[0:9], so an eight-byte field passes the check and explodes on the index.⁶ Borg's July fix corrects the bound and adds a test embedding his exact configuration, nameservers 10.60.60.151 and all.⁶

Replaying it needs the pure Go resolver, so both binaries below are built with CGO_ENABLED=0; otherwise libc parses the file and the bug never triggers. With his configuration in place:³

$ ./resolv2-13     # go1.3
panic: runtime error: slice bounds out of range
net.dnsReadConfig(...)
$ ./resolv2-131    # go1.3.1
addrs: [] err: read udp 127.0.0.1:53: connection refused

A panic becomes an ordinary lookup error. (The nameserver here points at localhost so the fixed binary answers at once instead of waiting out timeouts to Borg's original addresses.)

The short session key#

The crypto fix has no issue number. Cedric Staub noticed that decrypting a short message into a longer session-key buffer walked out of bounds: the constant-time copy loops over the length of the destination, so a 1-byte message copied into a 32-byte key reads 31 bytes past the message.⁷ Constant-time code cannot branch away from the overrun; that is the point of it being constant-time.

Adam Langley's July fix restructures the decryption to return the full padded block plus an index, so the copy always reads from a correctly-sized tail, and hardens ConstantTimeCopy itself to panic loudly on mismatched lengths instead of overrunning them.⁷ The added TestShortSessionKey is exactly the program below, which encrypts one byte and decrypts it into 32. Hit Run.

package main

import (
	"crypto/rand"
	"crypto/rsa"
	"fmt"
)

func main() {
	priv, err := rsa.GenerateKey(rand.Reader, 2048)
	if err != nil {
		panic(err)
	}
	ciphertext, err := rsa.EncryptPKCS1v15(rand.Reader, &priv.PublicKey, []byte{1})
	if err != nil {
		panic(err)
	}
	var key [32]byte
	err = rsa.DecryptPKCS1v15SessionKey(nil, priv, ciphertext, key[:])
	fmt.Println("err:", err)
	modified := false
	for _, v := range key {
		if v != 0 {
			modified = true
		}
	}
	fmt.Println("key modified:", modified)
}

err: <nil>
key modified: false

Against the old toolchain, the same file panics:³

$ go run rsashort.go     # go1.3
panic: runtime error: index out of range
$ go run rsashort.go     # go1.3.1
err: <nil>
key modified: false

The spurious connect#

The networking fix has the widest blast radius, and the best paper trail. coocood ran a sentinel: it dialed other applications to detect failures, reading a nil error as proof of life. After the move to Go 1.3, dead hosts started reporting alive. He compared the source against 1.2 and fingered the rewritten connect in net/fd_unix.go.⁸

Jason Eggleston diagnosed it down to the syscall order. Go registered the socket with epoll before connecting: fd.dial called fd.init, which flowed through runtime_pollOpen to epoll_ctl(ADD), and only then issued connect. A second thread blocked in epoll_wait could wake with an EPOLLOUT|EPOLLHUP event for a socket that connect had not even been called on yet; Go took the descriptor for ready, getsockopt found no error pending (EINPROGRESS is not one), and the dial returned success. Polling a file descriptor before connecting it is undefined behavior, and he brought the cross-project receipts: nginx also adds before connecting, but runs one thread per epoll instance, so nothing witnesses the window; libuv, under node and Rust, calls connect first and registers the fd after, on every platform.⁸

Reproducing it takes garton's loop, dialing a down host on repeat and counting the nil errors:³

$ go run epollock.go     # go1.3
attempts=300 nil-errors=95 first-write-err=write tcp 10.255.255.1:12345: i/o timeout
$ go run epollock.go     # go1.3.1
attempts=300 nil-errors=0 first-write-err=<nil>

Ninety-five dials out of three hundred report success against an address that answers nothing, and the phantom connections are good for nothing: the first write hangs until its deadline. On the fixed toolchain every dial waits out its hundred milliseconds and times out. (The repro needs a true black hole: a host answering RST, or a network returning ICMP unreachable, settles the connect and the window never opens. 10.255.255.1 goes unanswered in this container.)

The fix reorders the two calls: fd.init moves to after connect returns EINPROGRESS, with care for a connect that succeeds immediately against localhost, which registers the fd and returns without entering the wait loop. The deadline travels into connect with the move.⁸

Even the merge has texture. Russ Cox balked: a big change whose description said it "could be" the fix, for a point release. Then he approved it, with a warning that has outlived the bug: "This code needs to stop changing. It seems to get rewritten on every release... If the rewrites can't stop on their own, we will have to introduce an explicit freeze for large parts of package net." Mikio Hara's reply owned the history: the bug dated to Go 1.1, and he had missed the new poller's spurious-readiness warning when reworking the code for DragonFly's async connects in 1.3. "so pls blame me, ugh."⁸

The recursive typedef#

Two cgo reports, one root cause. Jonathan Plona's build crashed inside cmd/cgo itself, a nil pointer dereference in typeConv.Type on a recursive use of typedefs. jvshahid got the stranger symptom: an intermittent compilation error, cannot use o.a (type *C.inner) as type *C.struct___0, that printed a few times and then went away if you kept re-running the build. His complaint reads like a motto for deterministic builds: the compiler should either always fail or always succeed.⁹

Both bugs lived in cgo's DWARF type translation. Translating a typedef recursed into the underlying type first and patched up the Go mapping after, but the recursion could loop back through a struct naming the same typedef again, pocketing the not-yet-patched mapping on the way. Which half-finished mapping each pointer ended up with varied run to run: sometimes a crash, sometimes a type error, sometimes clean. Matthew Dempsky's debugging is visible in the issue: he first blamed GCC, attaching object files and readelf diffs to prove the DWARF differed run to run, then turned on -debug-gcc and watched cgo hand GCC the types in a different order each time. cgo was randomizing its own input.⁹

The thread also holds the series' best exchange about tricky code. Ian Lance Taylor: "This bit of code in cgo is really bothering me now. We've had to change it several times, and it's not getting any simpler or easier to understand. Can you think of any way to make this simpler so that we can believe that it is correct?" Dempsky, who had already uploaded a fix: "it took me a long time to understand what was even going on here :(" Then came the insight behind the final patch: pointers are the only way a type can recurse, so translating pointer targets through a completion queue instead of recursion breaks every cycle at once. Russ approved it the way he approved the epoll fix, reluctantly and on the strength of the test: "it fixes intermittent crashes that have no workaround (other than try again)."⁹

The regression test is two mutually recursive structs with the comment "No runtime test; just make sure it compiles." Fifteen runs of go tool cgo on the adapted file, dots for clean runs:³

$ for i in $(seq 1 15); do rm -rf _obj; go tool cgo typedef.go >/dev/null 2>&1 && echo -n . || echo -n X; done; echo     # go1.3
XXX.X.XXX.XXX.X
$ for i in $(seq 1 15); do rm -rf _obj; go tool cgo typedef.go >/dev/null 2>&1 && echo -n . || echo -n X; done; echo     # go1.3.1
...............

Eleven crashes out of fifteen on the old toolchain, each the same nil-pointer panic; fifteen clean runs on the new one. (This drives cmd/cgo directly, which is where the bug lives; the full go build path needs a cgo-enabled toolchain build.)

Roundup#

The rest in brief: ParseMultipartForm gets documentation for its Go 1.3 behavior of requiring a multipart Content-Type.¹⁰ Windows stops crashing when foreign threads raise exceptions inside the Go handler, fixed by Shenghou Ma.¹¹ ARM stops printing a harmless "unexpected return pc" when a profiling signal lands at the wrong moment, an event the reporter measured at about one in fifteen minutes.¹² The 8g toolchain builds again after an undefined D_R15B broke it.¹³ NaCl/amd64p32 loses its leftover traceback panics; the cause, that newproc takes two extra pointers rather than two extra registers and the two differ on amd64p32, was diagnosed before the 1.3 tree froze but missed the cut.¹⁴ The build learns _DEFAULT_SOURCE for glibc 2.20, which started deprecating _BSD_SOURCE.¹⁵ And two documentation-only picks round out the sixteen: a note that gzip/zlib Close flushes, and HTTPS scheme cleanup across the docs.¹⁶

Go 1.3.2 followed on 25 September with security fixes to crypto/tls and further cgo fixes.¹⁷