CPUs implement very fast access to array data: sequences of values of the same type. It makes sense, then, that higher-level languages provide abstractions for this approach. Go provides a built-in concept of a "slice" to handle sequences of values with the same type.
Slices
How are slices implemented?
A slice is represented by a slice header, something like
type SliceHeader[T any] struct {
Data *T
Len int
Cap int
}
here, Data points to the zeroth element of the slice. It points to a separately-allocated array of items of type T. Len gives the number of elements in the slice, and Cap gives the capacity of the underlying storage; that is, Data + Cap points to the end of the underlying storage allocation. In terms of garbage collection, Data serves to keep the underlying storage alive.
Slices can be created using literal expressions, or with make:
strings := []string{"expedita", "maiores", "quia", "animi"}
fmt.Printf("len=%d, cap=%d\n", len(strings), cap(strings))
// Output: len=4, cap=4
ints := make([]int, 5)
fmt.Printf("len=%d, cap=%d, initial=%d\n", len(ints), cap(ints), ints[0])
// Output: len=5, cap=5, initial=0
Slices can also be created from other slices:
middleInts := ints[1:4]
fmt.Printf("len=%d, cap=%d\n", len(middleInts), cap(middleInts))
// Output: len=3, cap=4
Note that the capacity of this slice is 4, even though the underlying storage has 5 elements. That's because the Data field of the slice header is pointing to the second (index 1) element of ints, after which only 4 elements are valid.
Go provides no way to "expand" a slice. That is, given middleInts, there is no way to read ints[0] or ints[4]. But there is a way to write to ints[4], given only middleInts. This sentence should set off security-vulnerability alarm bells in your head!
Append
The common operation of accumulating items into a slice is supported by the append built-in. In Go1.18 and later, the signature can be written func append[T any]([]T, ...T) []T. It was impossible to write such a function in previous versions of Go -- a curious situation for such a ubiquitous operation.
Anyone familiar with functional programming probably recognizes append's signature: it takes a data structure as an argument, along with some additional data, and returns a new data structure with the combined data. Does it modify the original slice? For a functional language, this would be an emphatic "no". A procedural language would answer "yes", and in fact would modify the slice in-place, and return nothing.
Go's choice? "maybe"! Append sometimes modifies its argument, or more specifically the storage underlying its argument. An experienced software engineer knows that "sometimes" leads to intermittent bugs, and that's exactly what happens with append. What's going on here?
strings := []string{"expedita", "maiores", "quia", "animi"}
firstTwo := strings[:2]
three := append(firstTwo, "uhoh")
fmt.Printf("three=%#v\n", three)
fmt.Printf("strings=%#v\n", strings)
// Output:
// three=[]string{"expedita", "maiores", "uhoh"}
// strings=[]string{"expedita", "maiores", "uhoh", "animi"}
How did that "uhoh" appear in strings? Nothing in the code suggests that strings is ever mutated. The append on the third line sees that there is room in the underlying storage for another element, and simply writes into the storage without re-allocating anything. This write aliases with other slices pointing to the same underlying storage -- in this case, with strings. This can cause unexpected results and data corruption even in single-threaded code, but could even cause race conditions and panics in a concurrent program. And all of those are potential security vulnerabilities.
You can imagine that, in a dynamic application dealing with slices of varying lengths, the same call to append may sometimes reallocate, and sometimes simply write into the existing storage. The race conditions are data-dependent, and may only happen intermittently, perhaps never in tests and only on some users' systems -- a nightmare bug!
To review, a fundamental function of the language runtime has a design that's similar to other languages, but different in subtle ways. And, those subtleties can lead to nondeterministic memory corruption and crashes. The rest of the story writes itself.
Reallocations
When append re-allocates memory, how much does it allocate? Those with a computer-science background might remember the phrase "amortized constant time". When append re-allocates, it allocates twice the size of the existing storage. Sparing you the big-O details, the effect is to balance the cost of repeatedly allocating and copying memory against the possibility of allocating memory that will never be used.
At least, this was the case until Go1.18. Buried deep in the release notes, the reallocation algorithm has been tuned to be "less prone to sudden transitions in allocation behavior". This means that in some situations, it may allocate less underlying storage space, but in others, it may allocate more. In either case, the times at which it reallocates will change, potentially uncovering previously innocuous aliasing issues. The result has been that some applications, when built with Go1.18, use notably more memory to perform the same tasks.
Tuning this algorithm is a good choice, but it highlights the fragility of software built using append -- which is to say, all software written in Go.
Live Data
A subtle detail of slices is that the Data field keeps the entire backing storage alive, in terms of garbage collection.
A common error is to allocate a large slice, then return a much smaller sub-slice. For example:
firstFiveWords := readDictionary()[:5]
This is a []string containing 5 elements, so surely it cannot use but a few hundred bytes! No, in fact, the entire dictionary is kept resident by this single slice, even though it is impossible to access any other words but the first five.
This sort of error is hard to spot, all the more so because memory management is Go is automatic, with no explicit allocation or de-allocation primitives. This can easily lead to explosions in runtime memory usage, causing out-of-memory errors in users systems. As with the append issues above, these problems are usually not visible in unit tests.
Summary
Built-in operations in a language will be used everywhere, and it's critical to get their design right. Where that's not the case, bugs creep in due to subtle misunderstandings and implementation details, and seemingly innocent changes can have dramatic, difficult-to-catch, and difficult-to-debug consequences.
Multiplied by hundreds of thousands of engineers using these built-in operations day-to-day, and millions of people relying on the software they're building, the cost of poor language design is staggering.
Top comments (0)