Memory regions

§ Background

The arena experiment adds a package consisting of a single type to the standard library: Arena. This type allows one to allocate data structures into it directly, and allows early release of the arena memory in bulk. In other words, it offers a form of region-based memory management to Go. The implementation is memory-safe insofar as use-after-frees will never result in memory corruption, only a potential crash.

In practice, this package has improved real application performance by 10-15%, achieved almost entirely due to earlier memory reuse and staving off GC execution.

The proposal to add arenas to the standard library is on indefinite hold due to concerns about API pollution. Specifically, for the API to be useful in a wide range of circumstances, APIs have to accept an additional arena parameter. A good example of this problem is the standard library: many functions in the standard library allocate heap memory, and could allocate memory into an arena upon request instead. But this would require changing so many APIs that it becomes infeasible, and is not worth a 10-15% cost reduction.

Furthermore, arenas do not compose well with the existing language. One example is stack allocation. The Go compiler employs an escape analysis pass to stack-allocate memory when possible. This decouples that memory's lifecycle from the garbage collector entirely, and is even more effective than arenas when it is possible. Unfortunately, when one chooses to allocate into an arena, that forces that allocation to come from an arena.

This document proposes a composable replacement for arenas in the form of user-defined goroutine-local memory regions.

§ Goals

First and foremost, our main goal is to reduce resource costs associated with the GC. If we can't achieve that, then this proposal is pointless.

The second most important goal is composability. Specifically:

• No requirement to change APIs to take advantage of arenas.
• Composability with standard library features, like sync.Pool and unique.Handle.
• Composability with existing optimizations, like stack allocation via escape analysis.

Finally, whatever we implement must be relatively easy to use and intuitive to intermediate-to-advanced Go developers. We must offer tools for discovering where regions might be worth it, and where they aren't working out.

§ Design

The core of this design revolves around a pair of functions that behave like annotations of function calls.

The annotations indicate whether the user expects most or all the memory allocated by some function call (and its callees) to stay local to that function (and its callees), and to be unreachable by the time that function returns. If these expectations hold, then that memory is eagerly reclaimed when the function returns.

package region

// Do creates a new scope called a region, and calls f in
// that scope. The scope is destroyed when Do returns.
//
// At the implementation's discretion, memory allocated by f
// and its callees may be implicitly bound to the region.
//
// Memory is automatically unbound from the region when it
// becomes reachable from another region, another goroutine,
// the caller of Do, its caller, or from any other memory not
// bound to this region.
//
// Any memory still bound to the region when it is destroyed is
// eagerly reclaimed by the runtime.
//
// This function exists to reduce resource costs by more
// effectively reusing memory, reducing pressure on the garbage
// collector.
// However, when used incorrectly, it may instead increase
// resource costs, as there is a cost to unbinding memory from
// the region.
// Always experiment and benchmark before committing to
// using a region.
//
// If Do is called within an active region, it creates a new one,
// and the old one is reinstated once f returns.
// However, memory cannot be rebound between regions.
// If memory created by an inner region is referenced by an outer
// region, it is not rebound to the outer region, but rather unbound
// completely.
// Memory created by an outer regions referenced by an inner region
// does not unbind anything, because the outer region always out-lives
// the inner region.
//
// Regions are local to the goroutines that create them,
// and do not propagate to newly created goroutines.
//
// Panics and calls to [runtime.Goexit] will destroy region
// scopes the same as if f returned, if they unwind past the
// call to Do.
func Do(f func())

// Ignore causes g and its callees to ignore the current
// region on the goroutine.
//
// Calling Ignore when not in an active region has no effect.
//
// The primary use-case for Ignore is to exclude memory that
// is known to out-live a region, to more effectively make use
// of regions. Using Ignore is less expensive than the unbinding
// process described in the documentation for [region.Do].
func Ignore(g func())

Comparison with arenas

Where an arena might be used like:

func myFunc(buf []byte) error {
	a := arena.New()
	defer a.Free()

	data := new(MyBigComplexProto)
	if err := proto.UnmarshalOptions{Arena: a}.Unmarshal(buf, data); err != nil {
		return err
	}
	// Do stuff with data. ...
}

Regions would be used like:

func myFunc(buf []byte) error {
	var topLevelErr error
	region.Do(func() {
		data := new(MyBigComplexProto)
		if err := proto.Unmarshal(buf, data); err != nil {
			topLevelErr = err
			return
		}
		// Do stuff with data. ...
	})
	return topLevelErr
}

You can think of a region as an implicit goroutine-local arena that lives for the duration of some function call. That goroutine-local arena is then used for allocating all the memory needed by that function call and its callees (including maps, slices, structs, etc.). And then thanks to some compiler and runtime magic, if any of that memory would cause a use-after-free issue, it is automatically removed from the arena and handed off to the garbage collector instead.

In practice, all uses of an arena within Google tightly limit the arena's lifetime to that of a particular function, usually the one they are created in, like the example above. This fact suggests that regions will most likely be usable in most or all of the same circumstances as arenas.

Annotated examples

Below are some specific examples of different behaviors described in the API.

Basic

This example demonstrates that all major builtins are intended to work with this functionality, and that leaking a pointer out of the region causes the memory it points to to be unbound from the region.

var keep *int
region.Do(func() {
	w := new(int)
	x := new(MyStruct)
	y := make([]int, 10)
	z := make(map[string]string)
	*w = use(x, y, z)
	keep = w // w is unbound from the region.
}) // x, y, and z's memory is eagerly cleaned up, w is not.

Nested regions

This example demonstrates how nested regions interact.

region.Do(func() {
	z := new(MyStruct)
	var y *MyStruct
	region.Do(func() {
		x := new(MyStruct)
		use(x, z) // z may be freely used within this inner region.
		y = x // x is unbound from any region.
	})
	use(y)
})

§ Implementation

Overview

First, region.Do sets a field in the current g indicating the stack offset at which the region begins.

If this stack offset field is != 0, runtime.mallocgc uses a special allocation path. The non-zero stack offset field also implicitly enables a new kind of write barrier for the goroutine (and only for that goroutine).

Then, region.Do calls the function that was passed to it.

The special allocation path allocates all memory in a special part of the heap. Memory allocated this way is referred to as "blue" (Bounded-Lifetime Unshared memory, Eagerly reclaimed, for fellow lovers of tortured acronyms). (Subtlety: "blueness" is relative to the goroutine that allocated the memory.)

In the g, we keep track of every span that was created as part of the blue allocation path. These spans are associated with the last call to region.Do.

The new write barrier catches writes of blue memory pointers to non-blue memory (including regular heap memory, globals, other goroutine stacks, any part of the stack above the latest region.Do, and cross-region writes (for nested regions, since all cross-goroutine writes must pass through already-faded memory)) and transitively "fades" the object graph rooted at the pointer being written. Faded memory is managed by the GC in the traditional tri-color mark scheme (hence "fading" to grayscale).

Once the function passed to region.Do returns, region.Do immediately sweeps all the spans associated with it, releasing any blue memory and places the spans back on a free list.

We go into more detail in the following sections.

New g flag

Let's first define the behavior and invariants of a new field on the g, region. This value is not inherited when new goroutines are created, and it is not inherited by g0. This flag is only ever mutated and accessed by a goroutine, for itself.

Blue memory management

If runtime.mallocgc sees that the current goroutine's region value is non-zero, it goes down a special allocation path for blue memory. This special allocation path allocates all memory in a part of the address space that is separate (that may, but ideally won't, interleave with) the general heap.

Address space

Region memory is allocated from dedicated heapArenas (not to be confused with arenas, these are 64 MiB aligned reservations on most 64-bit platforms, or 4 MiB on 32-bit platforms and Windows). When these are created, we provide hints to mmap and the like to be contiguous and in a distinct part of the address space from the heap, though it's OK if these special region heapArenas interleave with regular heapArenas.

These special heapArenas are distinguished by a compact bitmap (mheap_.isRegionArena) covering the whole address space, with each bit representing one heapArena. This bitmap is incredibly compact: a 48-bit address space divided into 64 MiB chunks results in a 512 KiB bitmap. We can reserve the full 512 KiB up-front and map in parts as-needed. 64 bytes of this bitmap (or one cache line on most systems) is sufficient to cover a contiguous 32 GiB of region memory.

Memory layout

All blue memory is managed in fixed-size blocks with size 8 KiB. If any allocation exceeds 2 KiB in size, it is not allocated blue, and is instead redirected to the general heap. These blocks are just special kinds of spans, and are backed with an mspan that is managed like all other spans today.

The layout of each block follows the Immix design. That is, each block is divided into 128-byte lines and groups of contiguous lines are bump-allocated into. Every allocation made into one of these regions has an 8-byte object header, including objects without pointers and small objects (<=8 bytes in size). (Insight: if objects are short-lived and we're going to reuse their memory quickly, then per-object overheads don't matter as much.)

Implementation note: we can adjust the block size up to accommodate larger objects. We can also potentially allow much larger objects to participate in regions by creating an additional pageAlloc structure for region-allocated memory. This document assumes the greatest impact will be from smaller objects (<2 KiB), which account for most of the allocation volume in most programs. However, should that assumption fail, we can generalize at the cost of some additional complexity.

Allocation

Just like Immix, objects are bump-pointer-allocated into contiguous free lines. Also like Immix, each goroutine carries two local blocks to allocate from. One block may be non-empty (that is, have some non-free lines) and the other will always start out completely empty. The main block is always attempted first, but medium-sized objects that fail to allocate into the main block will be allocated into the secondary block.

Blocks are usually allocated from a P-local free list, and failing that, a global free list. If a full GC has run recently, each goroutine will first try to sweep its own already-active blocks.

Garbage collection

Each blue block reserves the first two lines for a pair of bit-per-word 128-byte bitmaps. One indicates the start of each object, while the other indicates which words of the block have faded (tracked by the write barrier). The bit corresponding to an object's allocation header is set upon allocation. Lines also each get mark and alloc bits, but since they're small (64 bits each) they'll go right in the mspan for the block.

Each object's allocation header reserves the two least significant bits (which will always be zero otherwise) for mark bits. Each GC cycle, the two bits swap purposes. In GC cycle N, the Nth bit mod 2 is the bit for that cycle. When an object is marked, the (N+1 mod 2)'th bit is simultaneously cleared.

The GC will scan blocks using the object start bitmap to find the start of the object, and thus the object header. It marks and scans all reachable objects in blocks, even those objects that are still blue. It also marks any lines containing marked objects. When the GC marks an object whose fade bits are not set, it leaves the fade bits alone.

Sweeping

There are two ways in which objects in region blocks may have their memory made available for reuse. The first is based on the mark bits, which we'll call "full sweeping" since it's very close in semantics to the existing sweeper. The second is based on the fade bits, which we'll call "eager sweeping."

Full sweeping of all blocks is performed each GC cycle. Lines that have not been marked are made available for allocation by installing the line mark bits as the line allocation bits. Note that freeing both blue and non-blue objects is completely fine here: the mark bits prove whether or not the object is reachable. This first kind of sweeping is the one referenced in the allocation path.

Eager sweeping of region blocks is performed when the function passed to region.Do returns. Lines that do not overlap with any faded words, as indicated by the bitmap, are made available for allocation. Note that we may free blue objects that were marked. This is mostly fine: if the object never faded, we can be certain that the object is dead when f returns. The only hazard is if the GC queues a pointer to blue memory that is later freed. If the GC goes to inspect the object later, it might be gone. Even worse, there might not be an object starting at the same address anymore!

There are many ways to deal with this problem, but here are two.

1. Delay eager sweeping until after the mark phase completes. This is unfortunate, but easy to implement and safe.
2. Keep a generation counter on each blue block. If the GC enqueues a blue pointer, it also queues the generation counter from the block it lives in. Later, it checks the generation counter when looking up the block for the object again and if it doesn't match, it skips doing any additional work. This complicates scanning, but would allow for eager reclamation during the mark phase.

New write barrier

A new write barrier tracks when pointers to objects are written outside the call tree rooted at f and the blocks associated with f's region. In other words, it tracks writes of blue pointers to non-blue memory. This write barrier is enabled only if the region field on the g is non-zero. The write barrier executes on each pointer write that is not to the current stack frame (same as the existing write barrier).

If the write barrier discovers a blue pointer being written to non-blue memory, the fade bits for the words corresponding to the object's memory are set. Then, the object's referents are transitively marked as faded. Below is a sketch of the write barrier's fast path.

func regionWriteBarrier(ptr, dst unsafe.Pointer) {
	region := getg().region
	if region == 0 {
		return
	}
	if ptr == nil {
		return
	}
	if dst >= getg().stack.lo && dst < getg().stack.lo+region {
		// The pointer is being written into the stack within the region.
		return
	}
	ptrBlock := findRegionBlock(ptr)
	if ptrBlock == nil {
		// Pointer doesn't belong to a region.
		return
	}
	dstBlock := findRegionBlock(dst)
	// If they belong to different regions and ptr's region doesn't
	// does not out-live dst's, we must fade ptr.
	if dstBlock != nil && ptrBlock.region > dstBlock.region {
		// Otherwise, for within-region writes, only fade on writes of blue
		// to faded memory.
		if !ptrBlock.isBlue(ptr) || dstBlock.isBlue(dst) {
			return
		}
	}
	fade(ptr)
}

func findRegionBlock(ptr unsafe.Pointer) *regionBlock {
	// Check if the pointer lies inside of a region arena.
	arenaIdx := uintptr(ptr)/heapArenaBytes
	if mheap_.isRegionArena[arenaIdx/8]&(uint8(1)<<(arenaIdx%8)) == 0 {
		return nil
	}
	// Find the base of the block, where the fade bitmap, among other things, lives.
	base := uintptr(ptr) &^ (8192-1)
	return (*regionBlock)(unsafe.Pointer(base)))
}

type regionBlock struct {
	faded    [128]byte
	objStart [128]byte
	region   uintptr
	lineFade uint64
}

func (b *regionBlock) isBlue(ptr unsafe.Pointer) bool {
	// Find the word index that ptr corresponds to in the block.
	word := (uintptr(ptr)-uintptr(unsafe.Pointer(b)))/8

	// Load, mask, and check the bit corresponding to the word.
	return b.faded[word/8] & (1<<(word%8)) == 0
}

fade performs the transitive fade bitmap marking. Note that objects must be immediately transitively faded (that is, we cannot defer the operation), because then it would be possible to hide pointers to those objects in another goroutine's stack, which is not protected by a write barrier (and shouldn't be; it's too expensive).

Comparison with the arenas

Implicit allocation instead of explicit allocation

Arenas require explicitly choosing what gets allocated into an arena. On the one hand, this offers fine-grained control over memory, but on the other hand, does not compose well with the language. For example, it requires updating APIs to make the best use of the arena. Standard library APIs that do not accept an arena would need to have a new version to allocate memory into the arena.

One could imagine making arenas implicit and goroutine-bound. But the issue with implicitly allocating memory into an arena is that it's far less clear when it's safe to free the arena since some values may have been allocated into the arena that code authors don't expect.

In contrast, the regions design implicitly allocates all eligible heap memory into a kind of memory region, but avoids the issue of not knowing when to free memory. In essence, the new write barrier effectively pins memory that is not safe to free, meaning the rest can be freed once the region ends. The regions design also offers an opt-out mechanism (region.Ignore), restoring fine-grained control over memory allocation where needed.

Furthermore, explicit allocation introduces some complications with existing optimizations. For example, the compiler's escape analysis may be able to deduce that some value may be stack allocated, but this analysis immediately fails if the value is allocated into an arena. Special compiler support could make arena-allocated values candidates for stack allocation, but that's likely to be complex.

Finer granularity of memory reuse

One property of the arena experiment is that arena chunks are very large (8 MiB) to amortize the cost of syscalls to force faults on the memory. This means that, naively, making good use of arenas would require sharing them across multiple logical operations (for example, multiple HTTP requests in a server). In practice, the arena experiment works around this by only reusing partially-filled arena chunks, filling them up further. However, these partially-filled c