runtime: redesign GC synchronization

[aclements]

The barrier mechanism for transitioning from concurrent mark to mark termination has grown to be incredibly complex and fragile. It evolved incrementally from the getfull barrier used by the 1.4 STW GC, but while this barrier was acceptable for STW GC (and for STW mark termination in concurrent GC), its use during concurrent marking has well exceeded its original design criteria.

There are several difficulties:

1. The barrier needs to exit when there's no more work to be found, but unlike in STW GC, in concurrent GC this is a transient condition since write barriers can produce more work at any time during concurrent execution. As a result, one worker can think that GC is done, signal completion, and exit; then more work is created by write barriers; then another worker can wake up from sleep and continue working. This draws out transitions between phases.
2. Unlike in STW GC, participants come and go. There are a fixed number of dedicated mark workers, but fractional and idle mark workers and mutator assists are transient and may or may not be present when we run out of work. This, combined with 1 and the current timed polling loop in getfull make mark completion susceptible to live-lock: it's possible for the program to be in some transient worker each time one of the dedicated workers wakes up to check if it can exit the getfull barrier. It also complicates reasoning about the system because dedicated workers participate directly in the getfull barrier, but transient workers must instead use trygetfull instead because they have exit conditions that aren't captured by getfull (e.g., fractional workers exit when preempted). The complexity of implementing these exit conditions contributed to runtime: concurrent GC leads to 5x memory consumption #11677.
3. The GC needs to know when it's almost out of work during concurrent marking so it can enable more aggressive (but expensive) marking, rescan roots, and flush all work caches. Currently we define "almost out of work" as "out of work in the global queues, but there may per-P cached work". Determining this and synchronizing the workers forced us to layer other synchronization mechanisms on top of the getfull barrier (work.bgMark1 and work.bgMark2) that complicate the coordinator and the worker scheduler (e.g., issue runtime: sporadic huge GC pause #11694).
4. As a result of the additional barriers introduced to solve 3, there is a sleep/wakeup race in the coordinator that is difficult to solve cleanly. When transitioning from mark 1 to mark 2, we're producing new work via scanning while simultaneously consuming work in mutator assists. This means that when we actually enter mark 2, the workers may already have consumed all of the new work that was just created; no new workers will be started unless more work is created by write barriers (which usually happens, but won't necessarily) so there will be nothing to signal completion. We fix this by checking for this condition when we consider scheduling a worker, but this can cause a delay up to the scheduler quantum.
5. There are timed polling loops in multiple places. The loop in getfull delays completion of the mark phase and, while the sleep in this loop doesn't consume CPU, it also doesn't let the mutator make use of the CPU while it's waiting. This delay also contributed to runtime: concurrent GC leads to 5x memory consumption #11677. Likewise, there's a loop in assists that can delay execution of a single mutator.
6. The background mark worker goroutines are effectively higher priority than the coordinator goroutine. If a worker is the first to signal completion, it will put the coordinator on the worker's P's run queue, but if the scheduler decides it needs to continue scheduling the worker (which is possible because of 1), it will delay execution of the coordinator.
7. When transitioning from mark 1 to mark 2, the strict barrier means the coordinator has to do a non-trivial amount of work during which background workers can do very little and assists may simply spin. It would be much better if this were handled by a global state machine that could distribute this work just like we distribute the mark work.

For all of these reasons, I think we need to redesign the GC barrier for 1.6.

This isn't a concrete proposal, but there are some properties I think the synchronization should have:

1. Replace polling loops with sleep and wakeup. Ideally, find a way to unify the various wakeup conditions different parts of the system have. Dedicated workers need to block until there's a work buffer available or the phase terminates. Fractional and idle workers need to block until there's a work buffer available, the preemption flag is set, or the phase terminates. Assists need to block until there's a work buffer available, credit to be stolen, or the phase terminates. Also, ideally, the coordinator itself would symmetrically participate in the barrier and block until the phase terminates (if there is a coordinator; see runtime: replace GC coordinator with state machine #11970).
2. Rather than focusing on the number of goroutines doing work, focus on how many work buffers are "checked out". GC cannot enter mark termination if there is any work on the global queues or any work buffers checked out. Implementation-wise, this may be very similar to what we do with nproc/nwait right now, except that write barriers don't interact with nproc/nwait because they're not "doing work".
3. Make completion monotonic: when a phase is completed, all workers should stop, even if more work shows up.
4. Distribute work currently done on the coordinator, such as rescanning, to the workers and assists.

Most likely the solution to this is deeply tied to the solution to #11970.

@RLH @rsc

[gopherbot]

CL https://golang.org/cl/15890 mentions this issue.

[gopherbot]

CL https://golang.org/cl/16297 mentions this issue.

[rsc]

Is this done?

[RLH]

I believe so, Austin did the work, I just reviewed it.

On Tue, Nov 24, 2015 at 11:42 AM, Russ Cox [email protected] wrote:

Is this done?

—
Reply to this email directly or view it on GitHub
#12041 (comment).

[aclements]

There is still a timed polling loop in getfull (point 5), but it only happens during STW mark termination and doesn't seem to be causing problems at this point (it may extend mark termination time, but I don't have concrete evidence for that). I believe every other point is resolved, so I'll close this issue.