code review 131580043: runtime: Start and stop individual goroutines at gc saf...

runtime: Start and stop individual goroutines at gc safepoints

Code to bring goroutines to a gc safepoint one at a time,
do some work such as scanning, and restart the
goroutine, and then move on to the next goroutine.
Currently this code does not do much useful work
but this infrastructure will be critical to future
concurrent GC work.

Fixed comments reviewers.

[rlh, 2014-08-28 20:11:49]

Hello golang-codereviews@googlegroups.com (cc: dvyukov@google.com,
rsc@golang.org),

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

[rsc, 2014-08-29 19:33:51]

Partial review. Haven't looked at queiesce (also can't spell it) yet.

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

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:749: if(runtime·readgstatus(gp)&Gscan != Gscan) {
s/!= Gscan/== 0/

same thing but more common idiom. i had to puzzle through what this meant.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:631: // Check to see if you need to do some gcphasework
such as scanning the stack
If oldval==Gsyscall, newval==Grunning||newval==Grunnable is guaranteed.
Thus all this boils down to

// Help garbage collector if needed.
if(gp->preemptscan && !gp->gcworkdone && (oldval == Gsyscall || oldval ==
Grunning)) {
    if(oldval == Gsyscall && gp != g) {
        ...
    }
    gp->preemptscan = false;
    runtime.gcphasework(gp);
}

or maybe the gp != g check applies to Grunning too.

remove line number from print.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:650: // Stop a go routine and either scan or flip its
stack.
What does flip mean?
This needs a longer comment regardless.

// stopg attempts to stop the execution of gp, so that its stack can be scanned.
// If stopg returns true, gp's status has been changed to a scan state: the
caller
// is responsible for scanning the stack and then calling restartg.
// If stopg returns false, either the stack does not need to be scanned
// or another goroutine (either a GC helper or gp itself) will finish scanning
// the stack soon.

And on next line, no space before (.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:652: runtime·stopg (G *gp)
I find it very hard to keep scanrestart and success straight when reading
the code. In particular I find it confusing that you can set 'success=true'
to return false.

These variables are being used for control flow. I think it will be much clearer
to use actual control flow.
Everywhere that says
    scanrestart = X;
    success = true;
becomes
    return X;
And then while(!success) is for(;;).

Various cases can be merged using the Gscan bit.

The scanrestart check at the end of the switch is then no longer necessary:
just look at all the 'return true' to see that they are all placed where
the scan bit is set.

The use of preemptone is a bit odd. We just raced down to the p
and then it's going to race back to the gp, all without holding
any locks. Better to just manipulate gp directly, I think.
And then you can eliminate all the code paths where it returns false.
I didn't quite understand why we cared about the return value at all:
it might return true but have marked some OTHER goroutine for preemption,
so the return value was very nearly worthless.

I believe that if you're not using the nearly worthless preemptone,
then you don't need the preemptscan check at the bottom of the switch.
The gcworkdone check seems to be useful still, but I moved it to the
top, so that even a 'continue' will check it again.

for(;;) {
	// Stop if someone else did the work already.
	if(gp->gcworkdone)
		return false;

	s = runtime·readgstatus(gp);
	switch(s) {
	default:
		dumpgstatus(gp);
		runtime·throw("stopg: unexpected status");

	case Gdead:
		// Not worth our time.
		return false;

	case Gcopystack:
		// Loop until a new stack is in place.
		continue;

	case Grunnable:
	case Gsyscall:
	case Gwaiting:
		// Claim goroutine by setting scan bit.
		if(!runtime·castogscanstatus(gp, s, s|Gscan))
			break;
		runtime·gcphasework(gp);
		return true;

	case Gscanrunnable:
	case Gscanwaiting:
	case Gscansyscall:
		// Goroutine already claimed.
		return false;

	case Grunning:
		// Claim goroutine, so we aren't racing with a status
		// transition away from Grunning.
		if(!runtime·castogscanstatus(gp, Grunning, Gscanrunning))
			break;

		// Mark gp for preemption.
		if(!gp->gcworkdone) {
			gp->preemptscan = true;
			gp->preempt = true;
			gp->stackguard0 = StackPreempt;
		}

		// Unclaim.
		runtime·casfromgscanstatus(gp, Gscanrunning, Grunning);
		return false;
	}
}

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:766: switch ( s ) {
- spacing on this line
- unexpected default goes at top of switch
- merge common cases
- gp->m = nil etc is not quite right
 
switch(s) {
default:
    dumpgstatus(gp);
    runtime.throw("restartg: unexpected status");
case Gdead:
    break;
case Gscanrunnable:
case Gscanwaiting:
case Gscansyscall:
     runtime.casfromgscanstatus(gp, s, s&~Gscan);
     break;
case Gscanenqueue:
    // Scan is completed.
    // Goroutine now needs to be made runnable.
    // We put it on the global run queue; ready blocks on the global scheduler
lock.
    runtime.casfromgscanstatus(gp, Gscanenqueue, Gwaiting);
    if(gp != g->m->curg)
        runtime.throw("processing Gscanenqueue on wrong m");
    dropg();
    runtime.ready(gp);
    break;
}

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:772: // You won't get here until the scan is complete....
// Scan is now complete.
// Put gp on global run queue.
// ready acquires and releases the global scheduler lock.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:795: static uint32 concurrentgclock = 0;
I would like to know why this is not a Mutex, but we can put that off for now.
This is unused: delete.

[dvyukov, 2014-08-30 07:21:40]

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:578: GCoff,      // stop and start             nop
During C->Go conversion I hit lots of cases where C identifiers can't be
directly translated to Go, because C identifiers start with upper-case letter
and such identifiers become exported in Go.

I think it's better to start starting all new C identifiers with lower-case
letters, so that they can be directly translated to Go later. Otherwise we will
end up with GCoff vs gc_off in different files.

So probably gcOff, gcQuiesce, ...

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:704: bool    runtime·stopg (G*);
delete space before (

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:705: void    runtime·restartg (G*);
delete space before (

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:706: void    runtime·gcphasework (G*);
delete space before (

[rsc, 2014-08-30 17:34:51]

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:578: GCoff,      // stop and start             nop
No, do NOT do this. Let C style stay C style.
The constants are being exported now, as _Name. 
There are plenty of things we need to clean up once everything is in Go, but it
needs to be PLANNED.
All the runtime changes are far too ad hoc.
Don't make up new rules on the fly.

[rsc, 2014-09-02 20:33:01]

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:818: uint32 activeglen = runtime·allglen;
uint32 activeglen;
<blank line>
activeglen = runtime.allgen;

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:832: // You can end up doing work here if the page trap
on a Grunning Go routine has
goroutine

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:833: // not be sprung or in some race situations. For
example a runnable goes dead
been

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:843: } else if(status == Grunning) {
no else here - if body stopped control flow
also factor out duplicate elses:

if(status == Grunning && gp->stackguard == ...) {
     ...
} else {
    stopscanstart(gp);
}

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:870: schedule(); // is the normal way to relinquish g0...
it just gives it back to the scheduler
schedule(); // never returns

[rlh, 2014-09-02 21:31:49]

I have addressed all comments.

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

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/mgc0.c#ne...
src/pkg/runtime/mgc0.c:749: if(runtime·readgstatus(gp)&Gscan != Gscan) {
On 2014/08/29 19:33:51, rsc wrote:
> s/!= Gscan/== 0/
> 
> same thing but more common idiom. i had to puzzle through what this meant.

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:631: // Check to see if you need to do some gcphasework
such as scanning the stack
On 2014/08/29 19:33:51, rsc wrote:
> If oldval==Gsyscall, newval==Grunning||newval==Grunnable is guaranteed.
> Thus all this boils down to
> 
> // Help garbage collector if needed.
> if(gp->preemptscan && !gp->gcworkdone && (oldval == Gsyscall || oldval ==
> Grunning)) {
>     if(oldval == Gsyscall && gp != g) {
>         ...
>     }
>     gp->preemptscan = false;
>     runtime.gcphasework(gp);
> }
> 
> or maybe the gp != g check applies to Grunning too.
> 
> remove line number from print.

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:650: // Stop a go routine and either scan or flip its
stack.
Flipping means to repoint references from old objects to new objects. Flipping a
stack
means you flip pointers on the stack. It is not something we will be doing in
1.5.


 
On 2014/08/29 19:33:51, rsc wrote:
> What does flip mean?
> This needs a longer comment regardless.
> 
> // stopg attempts to stop the execution of gp, so that its stack can be
scanned.
> // If stopg returns true, gp's status has been changed to a scan state: the
> caller
> // is responsible for scanning the stack and then calling restartg.
> // If stopg returns false, either the stack does not need to be scanned
> // or another goroutine (either a GC helper or gp itself) will finish scanning
> // the stack soon.
> 
> And on next line, no space before (.
>

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:652: runtime·stopg (G *gp)
Yes reworking it to get rid of success and restart is a win and "Done"

I am also convinced that one can set a trap on the gp and that the trap is
independent 
of p and the use of preemptone. Nice catch.

On 2014/08/29 19:33:51, rsc wrote:
> I find it very hard to keep scanrestart and success straight when reading
> the code. In particular I find it confusing that you can set 'success=true'
> to return false.
> 
> These variables are being used for control flow. I think it will be much
clearer
> to use actual control flow.
> Everywhere that says
>     scanrestart = X;
>     success = true;
> becomes
>     return X;
> And then while(!success) is for(;;).
> 
> Various cases can be merged using the Gscan bit.
> 
> The scanrestart check at the end of the switch is then no longer necessary:
> just look at all the 'return true' to see that they are all placed where
> the scan bit is set.
> 
> The use of preemptone is a bit odd. We just raced down to the p
> and then it's going to race back to the gp, all without holding
> any locks. Better to just manipulate gp directly, I think.
> And then you can eliminate all the code paths where it returns false.
> I didn't quite understand why we cared about the return value at all:
> it might return true but have marked some OTHER goroutine for preemption,
> so the return value was very nearly worthless.
> 
> I believe that if you're not using the nearly worthless preemptone,
> then you don't need the preemptscan check at the bottom of the switch.
> The gcworkdone check seems to be useful still, but I moved it to the
> top, so that even a 'continue' will check it again.
> 
> for(;;) {
> 	// Stop if someone else did the work already.
> 	if(gp->gcworkdone)
> 		return false;
> 
> 	s = runtime·readgstatus(gp);
> 	switch(s) {
> 	default:
> 		dumpgstatus(gp);
> 		runtime·throw("stopg: unexpected status");
> 
> 	case Gdead:
> 		// Not worth our time.
> 		return false;
> 
> 	case Gcopystack:
> 		// Loop until a new stack is in place.
> 		continue;
> 
> 	case Grunnable:
> 	case Gsyscall:
> 	case Gwaiting:
> 		// Claim goroutine by setting scan bit.
> 		if(!runtime·castogscanstatus(gp, s, s|Gscan))
> 			break;
> 		runtime·gcphasework(gp);
> 		return true;
> 
> 	case Gscanrunnable:
> 	case Gscanwaiting:
> 	case Gscansyscall:
> 		// Goroutine already claimed.
> 		return false;
> 
> 	case Grunning:
> 		// Claim goroutine, so we aren't racing with a status
> 		// transition away from Grunning.
> 		if(!runtime·castogscanstatus(gp, Grunning, Gscanrunning))
> 			break;
> 
> 		// Mark gp for preemption.
> 		if(!gp->gcworkdone) {
> 			gp->preemptscan = true;
> 			gp->preempt = true;
> 			gp->stackguard0 = StackPreempt;
> 		}
> 
> 		// Unclaim.
> 		runtime·casfromgscanstatus(gp, Gscanrunning, Grunning);
> 		return false;
> 	}
> }

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:766: switch ( s ) {
On 2014/08/29 19:33:51, rsc wrote:
> - spacing on this line
> - unexpected default goes at top of switch
> - merge common cases
> - gp->m = nil etc is not quite right
>  
> switch(s) {
> default:
>     dumpgstatus(gp);
>     runtime.throw("restartg: unexpected status");
> case Gdead:
>     break;
> case Gscanrunnable:
> case Gscanwaiting:
> case Gscansyscall:
>      runtime.casfromgscanstatus(gp, s, s&~Gscan);
>      break;
> case Gscanenqueue:
>     // Scan is completed.
>     // Goroutine now needs to be made runnable.
>     // We put it on the global run queue; ready blocks on the global scheduler
> lock.
>     runtime.casfromgscanstatus(gp, Gscanenqueue, Gwaiting);
>     if(gp != g->m->curg)
>         runtime.throw("processing Gscanenqueue on wrong m");
>     dropg();
>     runtime.ready(gp);
>     break;
> }

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:772: // You won't get here until the scan is complete....
On 2014/08/29 19:33:51, rsc wrote:
> // Scan is now complete.
> // Put gp on global run queue.
> // ready acquires and releases the global scheduler lock.

Acknowledged.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:795: static uint32 concurrentgclock = 0;
On 2014/08/29 19:33:51, rsc wrote:
> I would like to know why this is not a Mutex, but we can put that off for now.
> This is unused: delete.

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:818: uint32 activeglen = runtime·allglen;
On 2014/09/02 20:33:00, rsc wrote:
> uint32 activeglen;
> <blank line>
> activeglen = runtime.allgen;

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:832: // You can end up doing work here if the page trap
on a Grunning Go routine has
On 2014/09/02 20:33:00, rsc wrote:
> goroutine

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:833: // not be sprung or in some race situations. For
example a runnable goes dead
On 2014/09/02 20:33:01, rsc wrote:
> been

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:843: } else if(status == Grunning) {
Not sure what the rules are on }, I removed as many as I could
if(status == Gdead) {
  ...
} else if(status == Grunning && ... && runtime·notetsleep...) 
	runtime·noteclear(&runtime·sched.stopnote);
else 
	stopscanstart(gp);

On 2014/09/02 20:33:01, rsc wrote:
> no else here - if body stopped control flow
> also factor out duplicate elses:
> 
> if(status == Grunning && gp->stackguard == ...) {
>      ...
> } else {
>     stopscanstart(gp);
> }
> 
>

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:870: schedule(); // is the normal way to relinquish g0...
it just gives it back to the scheduler
On 2014/09/02 20:33:01, rsc wrote:
> schedule(); // never returns

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:578: GCoff,      // stop and start             nop
I followed RSC's comment. I also believe that I was following the
enum naming protocol as closely as possible. I used GCmumble instead of Gcmumble
to disambiguate it from the Gmumble enums.

On 2014/08/30 17:34:50, rsc wrote:
> No, do NOT do this. Let C style stay C style.
> The constants are being exported now, as _Name. 
> There are plenty of things we need to clean up once everything is in Go, but
it
> needs to be PLANNED.
> All the runtime changes are far too ad hoc.
> Don't make up new rules on the fly.
>

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:704: bool    runtime·stopg (G*);
On 2014/08/30 07:21:40, dvyukov wrote:
> delete space before (

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:705: void    runtime·restartg (G*);
On 2014/08/30 07:21:40, dvyukov wrote:
> delete space before (

Done.

https://codereview.appspot.com/131580043/diff/40001/src/pkg/runtime/runtime.h...
src/pkg/runtime/runtime.h:706: void    runtime·gcphasework (G*);
On 2014/08/30 07:21:40, dvyukov wrote:
> delete space before (

Done.

[rlh, 2014-09-02 21:33:08]

Hello golang-codereviews@googlegroups.com, rsc@golang.org, dvyukov@google.com
(cc: golang-codereviews@googlegroups.com),

Please take another look.

[rsc, 2014-09-03 15:43:50]

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:650: runtime·throw("stopg: gp->atomicstatus is not valid.
");
remove '. ' at end of message

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:651: break;
delete - throw does not return

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:694: // Should not be here....
delete.
(if you could get here the compiler would reject the file.)

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:704: switch ( s ) {
switch(s) {

remove next blank line

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:708: runtime·throw("restartg: unexpected status.");
delete . at end of message

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:709: break;
delete

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:736: if(g == gp)
if you are testing for g0, use

if(g != g->m->g0)

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:737: runtime·throw("GC not moved to G0");
s/G0/g0/

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:754: uint32 activeglen = runtime·allglen;
uint32 activeglen;
<blank line>
activeglen = runtime.allglen;

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:779: } else if(status == Grunning) {
not seeing rewrite here

https://codereview.appspot.com/131580043/diff/60001/src/pkg/runtime/proc.c#ne...
src/pkg/runtime/proc.c:806: schedule(); // is the normal way to relinquish g0...
it just gives it back to the scheduler
not seeing rewrite here

[rlh, 2014-09-03 16:06:03]

Hello golang-codereviews@googlegroups.com, rsc@golang.org, dvyukov@google.com
(cc: golang-codereviews@googlegroups.com),

Please take another look.

[rsc, 2014-09-03 16:06:10]

LGTM

[rlh, 2014-09-03 16:06:40]

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

runtime: Start and stop individual goroutines at gc safepoints

Code to bring goroutines to a gc safepoint one at a time,
do some work such as scanning, and restart the
goroutine, and then move on to the next goroutine.
Currently this code does not do much useful work
but this infrastructure will be critical to future
concurrent GC work.

Fixed comments reviewers.

LGTM=rsc
R=golang-codereviews, rsc, dvyukov
CC=golang-codereviews
https://codereview.appspot.com/131580043

[gobot, 2014-09-03 16:32:28]

This CL appears to have broken the windows-amd64-perf builder.
See http://build.golang.org/log/031f251092c09a401a908e4be00b2de8ed248214