code review 46430043: runtime: concurrent GC sweep

runtime: concurrent GC sweep
Moves sweep phase out of stoptheworld by adding
background sweeper goroutine and lazy on-demand sweeping.

It turned out to be somewhat trickier than I expected,
because there is no point in time when we know size of live heap
nor consistent number of mallocs and frees.
So everything related to next_gc, mprof, memstats, etc becomes trickier.

At the end of GC next_gc is conservatively set to heap_alloc*GOGC,
which is much larger than real value. But after every sweep
next_gc is decremented by freed*GOGC. So when everything is swept
next_gc becomes what it should be.

For mprof I had to introduce 3-generation scheme (allocs, revent_allocs, prev_allocs),
because by the end of GC we know number of frees for the *previous* GC.

Significant caution is required to not cross yet-unknown real value of next_gc.
This is achieved by 2 means:
1. Whenever I allocate a span from MCentral, I sweep a span in that MCentral.
2. Whenever I allocate N pages from MHeap, I sweep until at least N pages are
returned to heap.
This provides quite strong guarantees that heap does not grow when it should now.

http-1
allocated                    7036         7033      -0.04%
allocs                         60           60      +0.00%
cputime                     51050        46700      -8.52%
gc-pause-one             34060569      1777993     -94.78%
gc-pause-total               2554          133     -94.79%
latency-50                 178448       170926      -4.22%
latency-95                 284350       198294     -30.26%
latency-99                 345191       220652     -36.08%
rss                     101564416    101007360      -0.55%
sys-gc                    6606832      6541296      -0.99%
sys-heap                 88801280     87752704      -1.18%
sys-other                 7334208      7405928      +0.98%
sys-stack                  524288       524288      +0.00%
sys-total               103266608    102224216      -1.01%
time                        50339        46533      -7.56%
virtual-mem             292990976    293728256      +0.25%

garbage-1
allocated                 2983818      2990889      +0.24%
allocs                      62880        62902      +0.03%
cputime                  16480000     16190000      -1.76%
gc-pause-one            828462467    487875135     -41.11%
gc-pause-total            4142312      2439375     -41.11%
rss                    1151709184   1153712128      +0.17%
sys-gc                   66068352     66068352      +0.00%
sys-heap               1039728640   1039728640      +0.00%
sys-other                37776064     40770176      +7.93%
sys-stack                 8781824      8781824      +0.00%
sys-total              1152354880   1155348992      +0.26%
time                     16496998     16199876      -1.80%
virtual-mem            1409564672   1402281984      -0.52%

[dvyukov, 2014-01-02 15:49:24]

Hello golang-codereviews@googlegroups.com (cc: cshapiro@golang.org,
khr@golang.org, rsc@golang.org),

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[dvyukov, 2014-01-02 15:52:20]

This turned out to be somewhat trickier than I expected due to various stats
collection (see the description). I am open to ideas on how to
restructure/simplify this.

Also currently there is an episodic deadlock related to finalizers:
add finalizer -> lock finalizer mutex -> reallocate finalizer table -> sweep
span -> queue finalizers -> lock finalizer mutex
It must go away when Keith submits his "specials" refactoring.

[Sameer Ajmani, 2014-01-03 17:19:38]

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.goc
File src/pkg/runtime/malloc.goc (right):

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:196: else while(runtime·atomicload(&s->sweepgen) !=
sg)
is it possible for s->sweepgen to become > sg during the yield?

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:198: }
Out of curiosity, why not this?
	sg = runtime·mheap.sweepgen;
	while(runtime·atomicload(&s->sweepgen) != sg) {
		if(runtime·cas(&s->sweepgen, sg-2, sg-1))
			runtime·MSpan_Sweep(s);
		else
			runtime·osyield();  // unfortunate condition, and we don't have efficient
means to wait
	}

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/mprof.goc
File src/pkg/runtime/mprof.goc (right):

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/mprof.goc...
src/pkg/runtime/mprof.goc:435: MProf_GC();
Is running GC twice here intentional?

[dvyukov, 2014-01-03 17:49:56]

Thanks for looking

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.goc
File src/pkg/runtime/malloc.goc (right):

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:196: else while(runtime·atomicload(&s->sweepgen) !=
sg)
On 2014/01/03 17:19:39, Sameer Ajmani wrote:
> is it possible for s->sweepgen to become > sg during the yield?

No, it's not possible. This function sets m->mallocing, this disables
preemption, which in turn means that stoptheworld/GC can not happen in between.
Only GC bumps sweepgen.

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:198: }
On 2014/01/03 17:19:39, Sameer Ajmani wrote:
> Out of curiosity, why not this?
> 	sg = runtime·mheap.sweepgen;
> 	while(runtime·atomicload(&s->sweepgen) != sg) {
> 		if(runtime·cas(&s->sweepgen, sg-2, sg-1))
> 			runtime·MSpan_Sweep(s);
> 		else
> 			runtime·osyield();  // unfortunate condition, and we don't have efficient
> means to wait
> 	}

This is also possible.
I wanted to be more explicit about what can happen, in what order, and what can
not happen. Your code makes it look like we may need to call MSpan_Sweep several
times (it's in loop), and also that we may still need to loop after MSpan_Sweep.

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/mprof.goc
File src/pkg/runtime/mprof.goc (right):

https://codereview.appspot.com/46430043/diff/230008/src/pkg/runtime/mprof.goc...
src/pkg/runtime/mprof.goc:435: MProf_GC();
On 2014/01/03 17:19:39, Sameer Ajmani wrote:
> Is running GC twice here intentional?

Yes, it is intentional. I need to add a comment.
First call will move stats from "recent" to "prev", the second call will move
stats from "prev" to final stats.

[dvyukov, 2014-01-22 16:29:44]

I've merged with new finalizers/specials, and the deadlock has gone away.
all.bash now passes.

Please take a look.

[dvyukov, 2014-01-22 16:36:35]

On 2014/01/22 16:29:44, dvyukov wrote:
> I've merged with new finalizers/specials, and the deadlock has gone away.
> all.bash now passes.
> 
> Please take a look.

+iant

[rsc, 2014-01-22 19:11:05]

This is pretty complex and there are no comments explaining the big picture.
Could you add some?

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:192: } else
no else after return in the if body.

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:2206: P *p, **pp;
variable declarations at top of function please

[dvyukov, 2014-01-23 18:29:47]

PTAL

I've added comments in mgc0.c and mprof.goc

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:192: } else
On 2014/01/22 19:11:05, rsc wrote:
> no else after return in the if body.

Done.

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/330001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:2206: P *p, **pp;
On 2014/01/22 19:11:05, rsc wrote:
> variable declarations at top of function please

Done.

[iant, 2014-01-28 23:41:11]

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:16: // The sweep phase used to be stop-the-world as well.
At the end of sweep we knew
In this comment don't lead off by saying how things used to work.  That is only
mildly interesting for people tracking history.  Lead off by saying how it works
now.

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:1864: gcstats.nsweepbg++;
Should this field be named nbgsweep, to correspond better to the function name?

[dvyukov, 2014-01-29 13:20:49]

PTAL

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:16: // The sweep phase used to be stop-the-world as well.
At the end of sweep we knew
On 2014/01/28 23:41:12, iant wrote:
> In this comment don't lead off by saying how things used to work.  That is
only
> mildly interesting for people tracking history.  Lead off by saying how it
works
> now.

Done.

https://codereview.appspot.com/46430043/diff/390001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:1864: gcstats.nsweepbg++;
On 2014/01/28 23:41:12, iant wrote:
> Should this field be named nbgsweep, to correspond better to the function
name?

Done.

[jnj, 2014-01-29 17:56:05]

I have some grammar and spelling suggestions, if you like.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:33: // closer to the target value. However, this is not
enough to not over-allocate memory.
s/to not over-allocate/to avoid over-allocating/ ?
"not enough to not" sounds weird to me.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:35: // there is no free swept spans, but there are
small-object unswept spans.
s/there is/there are/

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:36: // If the goroutine would naively allocate a new
span, it can surpass the yet-unknown
If the goroutine naively allocates a new span,

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:45: // into a two-page span).
The parenthesized bit here is confusing to me, maybe it could be reworded? I
don't have a suggestion though.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:50: // the span is sweept (either by sweeping it, or by
waiting for concurrent sweep to finish).
s/sweept/swept/
s/for concurrent/for the concurrent/

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:51: // The finalizer goroutine is kicked off only when
all spans are sweept.
s/sweept/swept/

[dvyukov, 2014-01-30 09:44:40]

Thanks!

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:33: // closer to the target value. However, this is not
enough to not over-allocate memory.
On 2014/01/29 17:56:05, jnj wrote:
> s/to not over-allocate/to avoid over-allocating/ ?
> "not enough to not" sounds weird to me.

Done.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:35: // there is no free swept spans, but there are
small-object unswept spans.
On 2014/01/29 17:56:05, jnj wrote:
> s/there is/there are/

Done.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:36: // If the goroutine would naively allocate a new
span, it can surpass the yet-unknown
On 2014/01/29 17:56:05, jnj wrote:
> If the goroutine naively allocates a new span,

Done.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:45: // into a two-page span).
On 2014/01/29 17:56:05, jnj wrote:
> The parenthesized bit here is confusing to me, maybe it could be reworded? I
> don't have a suggestion though.

I am ready to change it, if you have a proposal.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:50: // the span is sweept (either by sweeping it, or by
waiting for concurrent sweep to finish).
On 2014/01/29 17:56:05, jnj wrote:
> s/sweept/swept/
> s/for concurrent/for the concurrent/

Done.

https://codereview.appspot.com/46430043/diff/410001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:51: // The finalizer goroutine is kicked off only when
all spans are sweept.
On 2014/01/29 17:56:05, jnj wrote:
> s/sweept/swept/

Done.

[dvyukov, 2014-01-30 09:44:43]

Thanks!

[jnj, 2014-01-30 18:03:35]

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:27: // However, at the end of stop-the-world GC phase we
don't know size of alive heap,
However, at the end of the stop-the-world GC phase we don't know the size of the
live heap,

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:29: // At the end of stop-the-world phase next_gc is
conservatively set based on total
s/end of/end of the/

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:45: // into a two-page span).
I'm still not sure I understand it correctly, but it might read more easily like
this:

... a large margin. There is an exception: if a goroutine frees two nonadjacent
one-page spans to the heap, it will allocate a new two-page span, but there can
still be other one-page unswept spans which could be combined into a two-page
span.

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:47: // mark bits in GC bitmap). During GC all mcaches are
flushed into central cache,
s/into central/into the central/

[dvyukov, 2014-02-03 08:10:22]

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:27: // However, at the end of stop-the-world GC phase we
don't know size of alive heap,
On 2014/01/30 18:03:36, jnj wrote:
> However, at the end of the stop-the-world GC phase we don't know the size of
the
> live heap,

Done.

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:29: // At the end of stop-the-world phase next_gc is
conservatively set based on total
On 2014/01/30 18:03:36, jnj wrote:
> s/end of/end of the/

Done.

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:45: // into a two-page span).
On 2014/01/30 18:03:36, jnj wrote:
> I'm still not sure I understand it correctly, but it might read more easily
like
> this:
> 
> ... a large margin. There is an exception: if a goroutine frees two
nonadjacent
> one-page spans to the heap, it will allocate a new two-page span, but there
can
> still be other one-page unswept spans which could be combined into a two-page
> span.

Done.

https://codereview.appspot.com/46430043/diff/430001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:47: // mark bits in GC bitmap). During GC all mcaches are
flushed into central cache,
On 2014/01/30 18:03:36, jnj wrote:
> s/into central/into the central/

Done.

[gobot, 2014-02-10 16:29:06]

R=rsc@golang.org (assigned by dvyukov@google.com)

[rsc, 2014-02-12 17:42:57]

LGTM

Thanks for the comments.

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:56: // the span is being sweept by background
sweeper, skip
s/sweept/swept/

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:77: // the span is being sweept by background
sweeper, skip
s/sweept/swept/

[dvyukov, 2014-02-12 18:10:10]

fingers crossed

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:56: // the span is being sweept by background
sweeper, skip
On 2014/02/12 17:42:58, rsc wrote:
> s/sweept/swept/

Done.

https://codereview.appspot.com/46430043/diff/450001/src/pkg/runtime/mcentral....
src/pkg/runtime/mcentral.c:77: // the span is being sweept by background
sweeper, skip
On 2014/02/12 17:42:58, rsc wrote:
> s/sweept/swept/

Done.

[dvyukov, 2014-02-12 18:17:50]

*** Submitted as https://code.google.com/p/go/source/detail?r=e1d8f233470b ***

runtime: concurrent GC sweep
Moves sweep phase out of stoptheworld by adding
background sweeper goroutine and lazy on-demand sweeping.

It turned out to be somewhat trickier than I expected,
because there is no point in time when we know size of live heap
nor consistent number of mallocs and frees.
So everything related to next_gc, mprof, memstats, etc becomes trickier.

At the end of GC next_gc is conservatively set to heap_alloc*GOGC,
which is much larger than real value. But after every sweep
next_gc is decremented by freed*GOGC. So when everything is swept
next_gc becomes what it should be.

For mprof I had to introduce 3-generation scheme (allocs, revent_allocs,
prev_allocs),
because by the end of GC we know number of frees for the *previous* GC.

Significant caution is required to not cross yet-unknown real value of next_gc.
This is achieved by 2 means:
1. Whenever I allocate a span from MCentral, I sweep a span in that MCentral.
2. Whenever I allocate N pages from MHeap, I sweep until at least N pages are
returned to heap.
This provides quite strong guarantees that heap does not grow when it should
now.

http-1
allocated                    7036         7033      -0.04%
allocs                         60           60      +0.00%
cputime                     51050        46700      -8.52%
gc-pause-one             34060569      1777993     -94.78%
gc-pause-total               2554          133     -94.79%
latency-50                 178448       170926      -4.22%
latency-95                 284350       198294     -30.26%
latency-99                 345191       220652     -36.08%
rss                     101564416    101007360      -0.55%
sys-gc                    6606832      6541296      -0.99%
sys-heap                 88801280     87752704      -1.18%
sys-other                 7334208      7405928      +0.98%
sys-stack                  524288       524288      +0.00%
sys-total               103266608    102224216      -1.01%
time                        50339        46533      -7.56%
virtual-mem             292990976    293728256      +0.25%

garbage-1
allocated                 2983818      2990889      +0.24%
allocs                      62880        62902      +0.03%
cputime                  16480000     16190000      -1.76%
gc-pause-one            828462467    487875135     -41.11%
gc-pause-total            4142312      2439375     -41.11%
rss                    1151709184   1153712128      +0.17%
sys-gc                   66068352     66068352      +0.00%
sys-heap               1039728640   1039728640      +0.00%
sys-other                37776064     40770176      +7.93%
sys-stack                 8781824      8781824      +0.00%
sys-total              1152354880   1155348992      +0.26%
time                     16496998     16199876      -1.80%
virtual-mem            1409564672   1402281984      -0.52%

LGTM=rsc
R=golang-codereviews, sameer, rsc, iant, jeremyjackins, gobot
CC=golang-codereviews, khr
https://codereview.appspot.com/46430043

[gobot, 2014-02-12 23:54:26]

This CL appears to have broken the linux-amd64-race builder.

[gobot, 2014-02-12 23:54:33]

This CL appears to have broken the linux-amd64-race builder.

[gobot, 2014-02-12 23:54:33]

This CL appears to have broken the linux-amd64-race builder.

[minux1, 2014-02-23 05:01:12]

bisect shows this CL is causing random nil pointer faults on dragonfly BSD
amd64.

[dvyukov, 2014-02-23 09:45:38]

On 2014/02/23 05:01:12, minux wrote:
> bisect shows this CL is causing random nil pointer faults on dragonfly BSD
> amd64.

is there an issue?
example crash reports?

there are significant chances that this CL can cause other latent bugs to
activate.

[remyoudompheng, 2014-02-23 20:31:17]

On 2014/02/23 09:45:38, dvyukov wrote:
> On 2014/02/23 05:01:12, minux wrote:
> > bisect shows this CL is causing random nil pointer faults on dragonfly BSD
> > amd64.
> 
> is there an issue?
> example crash reports?
> 
> there are significant chances that this CL can cause other latent bugs to
> activate.

Do you think the linux/race random failures like this one are related ?

http://build.golang.org/log/6ad7b59ef2e93e3c9347eabfb4c4bd66df58fd5a

[minux1, 2014-02-23 21:26:52]

On Sun, Feb 23, 2014 at 4:45 AM, <dvyukov@google.com> wrote:

> On 2014/02/23 05:01:12, minux wrote:
>
>> bisect shows this CL is causing random nil pointer faults on dragonfly
>>
> BSD
>
>> amd64.
>>
>
> is there an issue?
> example crash reports?
>
http://build.golang.org/log/c25c05fcb20465fe6d7deb512cea737b89e740cb

>
> there are significant chances that this CL can cause other latent bugs
> to activate.
>
Very probable.

[dvyukov, 2014-02-24 08:02:13]

On Mon, Feb 24, 2014 at 12:31 AM,  <remyoudompheng@gmail.com> wrote:
> On 2014/02/23 09:45:38, dvyukov wrote:
>>
>> On 2014/02/23 05:01:12, minux wrote:
>> > bisect shows this CL is causing random nil pointer faults on
>
> dragonfly BSD
>>
>> > amd64.
>
>
>> is there an issue?
>> example crash reports?
>
>
>> there are significant chances that this CL can cause other latent bugs
>
> to
>>
>> activate.
>
>
> Do you think the linux/race random failures like this one are related ?
>
> http://build.golang.org/log/6ad7b59ef2e93e3c9347eabfb4c4bd66df58fd5a


Yup, it's related. Here is the fix:
https://codereview.appspot.com/67980043

[aram, 2014-03-11 16:59:36]

This broke Solaris runtime tests:
https://code.google.com/p/go/issues/detail?id=7511