Thoughts on Whatnot
Randomness in the Go Playground
July 07, 2021

The Go Playground is a really nice service. Whenever I want to test something really quickly, I can just open it up in a tab and do so without any need to clutter up my filesystem with temporary files, or to even have installed Go on whatever machine I happen to be on at the time. It’s got its quirks, but for the most part it does its job pretty well.

One of the aforementioned quirks, however, can be a problem for testing certain types of things: The playground exists in a timeless sandbox. No matter when or how often you call time.Now(), the playground always reports its time to be 2009-11-10 23:00:00 +0000 UTC m=+0.000000001. For many things this is good, as it means that code is very reproducible, but what if you want randomness? The math/rand package defaults to a seed of 1, meaning that calling the various rand.* functions will always yield the same sequence of results. The usual way to avoid this if that behavior is undesirable is to call rand.Seed(time.Now().UnixNano()) before generating any random numbers, or some equivalent, but this doesn’t work in the sandbox because the time is frozen. No matter how many times the above is called, it will always yield the same result.

However, as convenient and quick as seeding the random number generator using the current time is, it is not the only source of pseudo-randomness available in Go. Three other sources of randomness exist, allowing them to be used to, at the very least, generate a pseudo-random seed from which other random numbers can be generated.

crypto/rand

The simplest by far is crypto/rand, the cryptographically-secure pseudo-random number generator. Unlike math/rand, this generator seeds itself with entropy from the entire system, and the playground’s sandbox doesn’t extend to freezing it. Usage of it to get a seed is pretty simple:

func randomSeedFromCrypto() (s int64, err error) {
	err = binary.Read(rand.Reader, binary.LittleEndian, &s)
	return
}

The choice of binary.LittleEndian is arbitrary.

Now, while this solution works, it has a number of issues. For one thing, it introduces a dependency on crypto/rand, which results in, in all likelihood, there being two imported package rands, which is kind of annoying. Also, unlike the other methods that I’ll detail below, it can fail with an error. Both of these are pretty small problems, but still worth mentioning briefly.

runtime

Maps in Go have an undefined ordering. In order to help enforce a lack of reliance on the internal ordering, Go 1.0 implemented an internal fast randomizer that randomizes the iteration order of maps when they are used with range. This randomizer is still active in the playground, meaning that it can be exploited to generate a pseudo-random number. There are two ways to do this, one of which is nice and fast, but unclean, and one of which that is cleaner, but somewhat awkward due its use of features in ways that they weren’t intended.

The simpler of the two is to use the go:linkname compiler directive. This allows binding of local symbols to symbols in other packages in a way that completely gets around the usual exported/unexported system.

// unsafe must be imported to use go:linkname.
import "unsafe"

// Use unsafe for something so that importing it is O.K.
var _ = unsafe.Sizeof(struct{}{})

//go:linkname randomSeedFromRuntime runtime.fastrand
func randomSeedFromRuntime() uint64

And that’s it. As long as both the go:linkname directive and the randomSeedFromRuntime() definition exist, you can call randomSeedFromRuntime() to get a pseudo-random uint64 pulled straight from the runtime.

This has, again, problems. In particular, it depends on an unexported API, meaning that there is no guarantee whatsoever that it will still work in any future versions of Go. It is, however, quite a bit faster than most of the other methods in this blog post.

map

In a similar vein to the last approach, the map randomizer can be exploited directly via maps themselves. This can be done by extracting random elements from a map via a for loop:

var randmap = map[int64]struct{}{
	0: struct{}{},
	1: struct{}{},
}

func randomSeedFromMap() (s int64) {
	for i := 0; i < 64; i++ {
		for r := range randmap {
			s |= r << i
			break
		}
	}
	return s
}

Because of the randomizer, each loop over randmap via range will yield either 0 or 1 first. By breaking on the first loop, the function can randomly choose which one to use to build s. Obviously this isn’t the most efficient method for creating a random seed, but it doesn’t produce any errors and it doesn’t rely on unexported runtime API. It can also be made more efficient by expanding the number of map elements and the number of bits per map key, but I’ve kept it simpler here just to show the basic idea.

select

The last source of randomness is related to the previous in that the runtime produces purposefully random results that can then be exploited. To summarize, whenever a select is presented with multiple possible cases, it will pseudo-randomly pick one of the available ones. This can be used similarly to the randomized looping of maps above:

func randomSeedFromSelect() (s int64) {
	done := make(chan struct{})
	defer close(done)

	c := make(chan int64)
	go func() {
		for {
			select {
			case <-done:
				return
			case c <- 0:
			case c <- 1:
			}
		}
	}()

	for i := 0; i < 64; i++ {
		s |= <-c << i
	}
	return s
}

This is, quite frankly, the worst of the approaches presented here. The use of channels means that a fair bit of locking is involved, which will slow this down immensely, far more than necessary, even if the generator loop is moved outside of the function and left running for multiple calls. Despite this, this is my personal favorite just for the sheer absurdity of it.

Conclusion

So, what did we learn today?

Nothing useful, that’s for sure.

If you’d like to try the code for yourself, here is, not surprisingly, a playground link that has all of the methods described above defined in it.