Author(s): Austin Clements
Last updated: 2015-10-25
Discussion at https://golang.org/issue/11970.
The Go 1.5 GC is structured as a straight-line coordinator goroutine plus several helper goroutines. All state transitions go through the coordinator. This makes state transitions dependent on the scheduler, which can delay transitions, in turn extending the length of the GC cycle, blocking allocation, and occasionally leading to long delays.
We propose to replace this straight-line coordinator with an explicit state machine where state transitions can be performed by any goroutine.
As of Go 1.5, all GC phase changes are managed through straight-line
code in the runtime.gc function, which runs on a dedicated GC
goroutine. However, much of the real work is done in other goroutines.
These other goroutines generally detect when it is time for a phase
change and must coordinate with the main GC goroutine to effect this
phase change. This coordination delays phase changes and opens windows
where, for example, the mutator can allocate uncontrolled, or nothing
can be accomplished because everything is waiting on the coordinator
to wake up. This has led to bugs like
#11677 and
#11911. We've tried to mitigate this
by handing control directly to the coordinator goroutine when we wake
it up, but the scheduler isn't designed for this sort of explicit
co-routine scheduling, so this doesn't always work and it's more
likely to fall apart under stress than an explicit design.
We will restructure the garbage collector as an explicit state machine where any goroutine can effect a state transition. This is primarily an implementation change, not an algorithm change: for the most part, these states and the transitions between them closely follow the current GC algorithm.
Each state is global and determines the GC-related behavior of all goroutines. Each state also has an exit condition. State transitions are performed immediately by whatever goroutine detects that the current state's exit condition is satisfied. Multiple goroutines may detect an exit condition simultaneously, in which case none of these goroutines may progress until the transition has been performed. For many transitions, this is necessary to prevent runaway heap growth. Each transition has a specific set of steps to prepare for the next state and the system enters the next state as soon as those steps are completed. Furthermore, each transition is designed to make the exit condition that triggers that transition false so that the transition happens once and only once per cycle.
In principle, all of the goroutines that detect an exit condition could assist in performing the transition. However, we take a simpler approach where all transitions are protected by a global transition lock and transitions are designed to perform very little non-STW work. When a goroutine detects the exit condition, it acquires the transition lock, re-checks if the exit condition is still true and, if not, simply releases the lock and continues executing in whatever the new state is. It is necessary to re-check the condition, rather than simply check the current state, in case the goroutine is blocked though an entire GC cycle.
The sequence of states and transitions is as follows:
State: Sweep/Off This is the initial state of the system. No scanning, marking, or assisting is performed. Mutators perform proportional sweeping on allocation and background sweeping performs additional sweeping on idle Ps.
In this state, after allocating, a mutator checks if the heap size
has exceeded the GC trigger size and, if so, it performs concurrent
sweep termination by sweeping any remaining unswept spans (there
shouldn't be any for a heap-triggered transition). Once there are no
unswept spans, it performs the sweep termination transition.
Periodic (sysmon-triggered) GC and runtime.GC perform these same
steps regardless of the heap size.
Transition: Sweep termination and initialization Acquire
worldsema. Start background workers. Stop the world. Perform sweep
termination. Clear sync pools. Initialize GC state and statistics.
Enable write barriers, assists, and background workers. If this is a
concurrent GC, configure root marking, start the world, and enter
concurrent mark. If this is a STW GC (runtime.GC), continue with
the mark termination transition.
State: Concurrent mark 1 In this state, background workers perform concurrent scanning and marking and mutators perform assists.
Background workers initially participate in root marking and then switch to draining heap mark work.
Mutators assist with heap marking work in response to allocation according to the assist ratio established by the GC controller.
In this state, the system keeps an atomic counter of the number of
active jobs, which includes the number of background workers and
assists with checked out work buffers, plus the number of workers in
root marking jobs. If this number drops to zero and
gcBlackenPromptly is unset, the worker or assist that dropped it
to zero transitions to concurrent mark 2. Note that it's important
that this transition not happen until all root mark jobs are done,
which is why the counter includes this.
Note: Assists could participate in root marking jobs just like
background workers do and accumulate assist credit for this scanning
work. This would particularly help at the beginning of the cycle
when there may be little background credit or queued heap scan work.
This would also help with load balancing. In this case, we would
want to update scanblock to track scan credit and modify the scan
work estimate to include roots.
Transition: Disable workbuf caching Disable caching of workbufs
by setting gcBlackenPromptly. Queue root mark jobs for globals.
Note: It may also make sense to queue root mark jobs for stacks. This would require making it possible to re-scan a stack (and extend existing stack barriers).
State: Concurrent mark 2 The goroutine that performed the flush
transition flushes all workbuf caches using forEachP. This counts
as an active job to prevent the next transition from happening
before this is done.
Otherwise, this state is identical to concurrent mark 1, except that workbuf caches are disabled.
Because workbuf caches are disabled, if the active workbuf count
drops to zero, there is no more work. When this happens and
gcBlackenPromptly is set, the worker or assist that dropped it the
count to zero performs the mark termination transition.
Transition: Mark termination Stop the world. Unblock all parked
assists. Perform gcMark, checkmark (optionally), gcSweep, and
re-mark (optionally). Start the world. Release worldsema. Print GC
stats. Free stacks.
Note that gcMark itself runs on all Ps, so this process is
parallel even though it happens during a transition.
There are various alternatives to this approach. The most obvious is to simply continue with what we do now: a central GC coordinator with hacks to deal with delays in various transitions. This is working surprisingly well right now, but only as a result of a good deal of engineering effort (primarily the cascade of fixes on #11677) and its fragility makes it difficult to make further changes to the garbage collector.
Another approach would be make the scheduler treat the GC coordinator as a high priority goroutine and always schedule it immediately when it becomes runnable. This would consolidate several of our current state transition "hacks", which attempt to help out the scheduler. However, in a concurrent setting it's important to not only run the coordinator as soon as possible to perform a state transition, but also to disallow uncontrolled allocation on other threads while this transition is being performed. Scheduler hacks don't address the latter problem.
This change is internal to the Go runtime. It does not change any user-facing Go APIs, and hence it satisfies Go 1 compatibility.
This change will be implemented by Austin Clements, hopefully in the Go 1.6 development cycle. Much of the design has already been prototyped.
Many of the prerequisite changes have already been completed. In particular, we've already moved most of the non-STW work out of the GC coordinator (CL 16059 and CL 16070), made root marking jobs smaller (CL 16043), and improved the synchronization of blocked assists (CL 15890).
The GC coordinator will be converted to a decentralized state machine incrementally, one state/transition at a time where possible. At the end of this, there will be no work left in the GC coordinator and it will be deleted.
There are devils in the details. One known devil in the current garbage collector that will affect this design in different ways is the complex constraints on scheduling within the garbage collector (and the runtime in general). For example, background workers are currently not allowed to block, which means they can't stop the world to perform mark termination. These constraints were designed for the current coordinator-based system and we will need to find ways of resolving them in the decentralized design.