code review 5334051: runtime: add timer support, use for package time

runtime: add timer support, use for package time

This looks like it is just moving some code from
time to runtime (and translating it to C), but the
runtime can do a better job managing the goroutines,
and it needs this functionality for its own maintenance
(for example, for the garbage collector to hand back
unused memory to the OS on a time delay).
Might as well have just one copy of the timer logic,
and runtime can't depend on time, so vice versa.

It also unifies Sleep, NewTicker, and NewTimer behind
one mechanism, so that there are no claims that one
is more efficient than another.  (For example, today
people recommend using time.After instead of time.Sleep
to avoid blocking an OS thread.)

Fixes issue 1644.
Fixes issue 1731.
Fixes issue 2190.

[rsc, 2011-11-04 19:52:03]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg

[bradfitz, 2011-11-04 19:54:07]

Nice.

"Fixes Issue nnn"?  I feel like there is at least one.


On Fri, Nov 4, 2011 at 12:52 PM, <rsc@golang.org> wrote:

> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://go.googlecode.com/hg
>
>
> Description:
> runtime: add timer support, use for package time
>
> This looks like it is just moving some code from
> time to runtime (and translating it to C), but the
> runtime can do a better job managing the goroutines,
> and it needs this functionality for its own maintenance
> (for example, for the garbage collector to hand back
> unused memory to the OS on a time delay).
> Might as well have just one copy of the timer logic,
> and runtime can't depend on time, so vice versa.
>
> It also unifies Sleep, NewTicker, and NewTimer behind
> one mechanism, so that there are no claims that one
> is more efficient than another.  (For example, today
> people recommend using time.After instead of time.Sleep
> to avoid blocking an OS thread.)
>
> Please review this at
http://codereview.appspot.com/**5334051/<http://codereview.appspot.com/5334051/>
>
> Affected files:
>  M src/pkg/runtime/darwin/os.h
>  M src/pkg/runtime/darwin/thread.**c
>  M src/pkg/runtime/freebsd/**thread.c
>  M src/pkg/runtime/linux/thread.c
>  M src/pkg/runtime/lock_futex.c
>  M src/pkg/runtime/lock_sema.c
>  M src/pkg/runtime/openbsd/**thread.c
>  M src/pkg/runtime/plan9/thread.c
>  M src/pkg/runtime/proc.c
>  M src/pkg/runtime/runtime.h
>  M src/pkg/runtime/time.goc
>  M src/pkg/runtime/windows/**thread.c
>  M src/pkg/time/sleep.go
>  M src/pkg/time/sys.go
>  M src/pkg/time/tick.go
>
>
>

[rsc, 2011-11-04 19:54:36]

On Fri, Nov 4, 2011 at 15:54, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> "Fixes Issue nnn"?  I feel like there is at least one.

just added 3

[r, 2011-11-04 21:00:14]

LGTM but some comments wouldn't hurt. this is mysterious to most

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/freebsd/thread.c
File src/pkg/runtime/freebsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:17: uintptr sec;
why are these uintptr? uintptr might be only 32 bits, too. maybe that's not a
problem for nsec since 1b fits in 31.

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:41: static void timerproc(void);
does goc have no comment convention? how about some function comments?

[hector, 2011-11-04 21:13:44]

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/windows/thread.c
File src/pkg/runtime/windows/thread.c (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/windows/threa...
src/pkg/runtime/windows/thread.c:154: // Is it right on 64-bit machines, or is
it 0xFFFFFFFF there too?
I found this in winbase.h:
#define INFINITE	0xFFFFFFFF
MSDN for WaitForSingleObject says it's a DWORD as well.

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/windows/threa...
src/pkg/runtime/windows/thread.c:161: 
Zap the tab :) I also noticed this on the nanotime CL after it was submitted.

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/windows/threa...
src/pkg/runtime/windows/thread.c:164: else if(ns/1000 > 0x7fffffffll)
uppercase LL?

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/windows/threa...
src/pkg/runtime/windows/thread.c:167: ms = ns/1000;
WaitForSingleObject wants milliseconds, but I think this is microseconds.

[iant, 2011-11-04 21:31:53]

FYI

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/freebsd/thread.c
File src/pkg/runtime/freebsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:17: uintptr sec;
On 2011/11/04 21:00:14, r wrote:
> why are these uintptr? uintptr might be only 32 bits, too. maybe that's not a
> problem for nsec since 1b fits in 31.

This does match what godefs pulls out.  In the FreeBSD sources the sec field is
time_t and the nsec field is long.

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:30: sec = ns / 1000000000LL;
I assume you mean "ts.sec =" and "ts.usec =" here.  The code as written won't
even compile.

[iant, 2011-11-04 22:13:57]

FYI

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/darwin/thread.c
File src/pkg/runtime/darwin/thread.c (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/darwin/thread...
src/pkg/runtime/darwin/thread.c:347: int32
This interface is a bit confusing.  If the ns parameter is < 0, always return 0.
 If ns >= 0, return -1 on timed out or interrupted, or 0 if completed.  The
behaviour seems inconsistent if the wait is interrupted (ns < 0, ignore
interrupts, ns >= 0, return -1 on interrupt), and it's not clear why.

It appears that the callers ignore the return value anyhow, and indeed I'm not
sure what they would do with it.  Can we just get rid of it?

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:70: if(t.i != -1) {
I found this a little mysterious at first reading.  What guarantees that the
timer is complete when gosched returns?  The thing that guarantees it is that
the only caller of tsleep has set g->status = Gwaiting.  I think it would be
clearer to move the setting of g->status and g->waitreason down to before the
call to gosched, rather than in the only caller.

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:71: // Woke up before alarm.  Turn it off.
Actually, I don't understand how the case of t.i != -1 is even possible here. 
What could mark this goroutine as ready other than the timer firing?  If the
timer fires, how could t.i != -1?

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:72: runtime·lock(&timers);
Why not just call deltimer?

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:96: n = timers.cap * 3/2;
The formatting here is not the order in which the operations will be performed. 
Suggest "timers.cap*3 / 2".

http://codereview.appspot.com/5334051/diff/8002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:171: t->when += t->period * (1 + -delta/t->period);
This adjustment is not particularly good if, say, delta is 1/2 t->period.  The
resulting wait will be t->period again when it ought to be more like t->period /
2.  Perhaps a bit of scaled arithmetic would be appropriate here, e.g.,
  (t->period * (100 + -delta * 100 / t->period)) / 100

[rsc, 2011-11-04 22:19:20]

On Fri, Nov 4, 2011 at 18:13,  <iant@golang.org> wrote:
> This adjustment is not particularly good if, say, delta is 1/2
> t->period.  The resulting wait will be t->period again when it ought to
> be more like t->period / 2.  Perhaps a bit of scaled arithmetic would be
> appropriate here, e.g.,
>  (t->period * (100 + -delta * 100 / t->period)) / 100

I am not sure this comment applies.  t->when != now.
If delta is 1/2 t->period, then the event is already
1/2 t->period old, and the next one will happen
1/2 t->period from now.  Those two will be a little
close, but we are behind and it will help keep us
on a regular schedule.

Russ

[iant2, 2011-11-04 22:27:43]

Russ Cox <rsc@golang.org> writes:

> On Fri, Nov 4, 2011 at 18:13,  <iant@golang.org> wrote:
>> This adjustment is not particularly good if, say, delta is 1/2
>> t->period.  The resulting wait will be t->period again when it ought to
>> be more like t->period / 2.  Perhaps a bit of scaled arithmetic would be
>> appropriate here, e.g.,
>>  (t->period * (100 + -delta * 100 / t->period)) / 100
>
> I am not sure this comment applies.  t->when != now.
> If delta is 1/2 t->period, then the event is already
> 1/2 t->period old, and the next one will happen
> 1/2 t->period from now.  Those two will be a little
> close, but we are behind and it will help keep us
> on a regular schedule.

Oh yeah.  Never mind.

Ian

[jsing, 2011-11-05 06:30:03]

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/openbsd/thread.c
File src/pkg/runtime/openbsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/openbsd/threa...
src/pkg/runtime/openbsd/thread.c:77: runtime·thrsleep(&m->waitsemacount, ms, 0,
&m->waitsemalock);
This will not work as intended - the second argument is a clock identifier and
the third argument is an optional pointer to a timespec. This basically needs to
match the FreeBSD implementation, however with the clock identifier being
CLOCK_REALTIME. I'll send a change that fixes the thrsleep() definition and
provides enums for the clock identifiers.

[jsing, 2011-11-06 14:50:50]

With this change I'm seeing the following on linux amd64:

TEST FAIL crypto/blowfish
make[1]: Entering directory `/src/go/src/pkg/crypto/blowfish'
gotest -test.short -test.timeout=120
rm -f _test/crypto/blowfish.a
6g   -p crypto/blowfish -o _gotest_.6 block.go cipher.go const.go 
blowfish_test.go
rm -f _test/crypto/blowfish.a
gopack grc _test/crypto/blowfish.a _gotest_.6 
panic: invalid memory address or nil pointer dereference
throw: panic during gc
[signal 0xb code=0x1 addr=0x0 pc=0x408915]

goroutine 1 [running]:
testing.RunTests(0x400c00, 0x50b340, 0x300000003, 0x1, 0x4b353c, ...)
	/src/go/src/pkg/testing/testing.go:210 +0x114
testing.Main(0x400c00, 0x50b340, 0x300000003, 0x517610, 0x0, ...)
	/src/go/src/pkg/testing/testing.go:182 +0x68
main.main()
	/src/go/src/pkg/crypto/blowfish/_testmain.go:31 +0x91
gotest: "./6.out -test.short=true -test.timeout=120" failed: exit status 2

This is relatively random and does not always occur doing the same test -
pc=0x408915 appears to be a mov (%rdx),%rdx within the ReleaseN() function.

[jsing, 2011-11-06 14:56:29]

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/freebsd/thread.c
File src/pkg/runtime/freebsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:15: typedef struct Timespec Timespec;
Any reason not to add this to defs.[ch]?

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:30: sec = ns / 1000000000LL;
s/sec/ts.sec/

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/freebsd/threa...
src/pkg/runtime/freebsd/thread.c:31: usec = ns % 1000000000LL;
s/usec/ts.nsec/

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/linux/thread.c
File src/pkg/runtime/linux/thread.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/linux/thread....
src/pkg/runtime/linux/thread.c:41: Timespec tv, *tvp;
Would it be better to use ts and tsp since this is a timespec?

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/openbsd/thread.c
File src/pkg/runtime/openbsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/openbsd/threa...
src/pkg/runtime/openbsd/thread.c:59: void
s/void/int32/, plus we presumably want to store and return the result from the
thrsleep() call.

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/openbsd/threa...
src/pkg/runtime/openbsd/thread.c:78: goto retry;
Hrmmm... I think we've got an interesting problem here - if we return after a
timeout we will goto retry, waitsemacount is likely to still be 0 (unless
something called wakeup) and we will then sleep again. This will likely need
redesigning in order to sleep with a timeout.

[brainman, 2011-11-07 01:44:57]

Applied your change to 87b7bdc68d7f+. But this program (simplified
http://code.google.com/p/go/issues/detail?id=2190):

package main

import (
	"time"
)

const N = 10000

func main() {
	for i := 0; i < N; i++ {
		go func() {
			time.Sleep(1e9)
		}()
	}
	<-make(chan bool)
}

still crashes on windows:

runtime: failed to create new OS thread (have 1181 already; errno=8)
throw: runtime.newosproc

goroutine 1181 [sleep]:
time.Sleep(0x3b9aca00, 0x0)
	/root/hg/go/src/pkg/runtime/time.c:26 +0x50
main._func_001()
	/root/t2/test.go:12 +0x2d
created by main.main
	/root/t2/test.go:13 +0x34

goroutine 1 [chan receive]:
main.main()
	/root/t2/test.go:15 +0x78

goroutine 2 [sleep]:
time.Sleep(0x3b9aca00, 0x0)
	/root/hg/go/src/pkg/runtime/time.c:26 +0x50
main._func_001()
	/root/t2/test.go:12 +0x2d
created by main.main
	/root/t2/test.go:13 +0x34

goroutine 3 [sleep]:
time.Sleep(0x3b9aca00, 0x0)
	/root/hg/go/src/pkg/runtime/time.c:26 +0x50
main._func_001()
	/root/t2/test.go:12 +0x2d
created by main.main
	/root/t2/test.go:13 +0x34

...

Alex

[dvyukov, 2011-11-07 09:55:44]

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:122: runtime·newm(timerproc);
timers.started = 1;

[dvyukov, 2011-11-07 10:35:02]

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/proc.c#newcod...
src/pkg/runtime/proc.c:725: m->procfn();
I think as of now it will throw if fall through to schedule(). Isn't it better
to put explicit return?

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/proc.c#newcod...
src/pkg/runtime/proc.c:774: m->procfn = procfn;
It is quite fragile. See newm comment in time.goc.

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:122: runtime·newm(timerproc);
One needs to increment mcpu and grunning before starting new M. Otherwise it
won't play nicely with stop the world GC.

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:170: timerproc(void)
I think the thread does not play nicely with garbage collection. It must not
allocate/free any memory and more importantly not touch any GC memory (it seems
to shuffle timer pointers).
it must support the stop the world protocol.

[dvyukov, 2011-11-07 10:54:15]

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/lock_futex.c
File src/pkg/runtime/lock_futex.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/lock_futex.c#...
src/pkg/runtime/lock_futex.c:106: runtime·notesleep(Note *n)
notetsleep(n, -1)?

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/lock_sema.c
File src/pkg/runtime/lock_sema.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/lock_sema.c#n...
src/pkg/runtime/lock_sema.c:115: runtime·notesleep(Note *n)
notetsleep(n, -1)?

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/proc.c#newcod...
src/pkg/runtime/proc.c:586: if(runtime·sched.grunning == 0 &&
!runtime·havetimers())
Need to re-check the condition in time.goc when havetimers() becomes false.

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:29: g->status = Gwaiting;
It's better to set the status in tsleep(). tsleep() is completely senseless w/o
the Gwaiting status.

http://codereview.appspot.com/5334051/diff/5002/src/pkg/runtime/time.goc#newc...
src/pkg/runtime/time.goc:78: if(t.i != -1) {
How can this happen?

[dvyukov, 2011-11-07 11:26:10]

Now it would be nice if we rewrite
  case now <-time.After(timeout):
into
  runtime.selecttimeout(timeout, &now):
Because then we just need to choose a minimal timeout and use timed sleep inside
of select. No need to allocate/collect channel, send/receive values, etc. But it
won't pass the review, right?

[rsc, 2011-11-07 17:38:47]

On Mon, Nov 7, 2011 at 06:26,  <dvyukov@google.com> wrote:
> Now it would be nice if we rewrite
>  case now <-time.After(timeout):
> into
>  runtime.selecttimeout(timeout, &now):
> Because then we just need to choose a minimal timeout and use timed
> sleep inside of select. No need to allocate/collect channel,
> send/receive values, etc. But it won't pass the review, right?

This is a possible direction to go, but it is far
from clear that it is a direction we should go.
Let's not worry about it in this CL.

Russ

[rsc, 2011-11-07 20:40:18]

On Sun, Nov 6, 2011 at 09:56,  <jsing@google.com> wrote:
> src/pkg/runtime/freebsd/thread.c:15: typedef struct Timespec Timespec;
> Any reason not to add this to defs.[ch]?

Only that I cannot regenerate those files easily.
If anyone has access to the necessary FreeBSD machines
and would like to send a CL, that would be great.

Thanks.
Russ

[rsc, 2011-11-07 21:50:05]

PTAL

Thanks for the great feedback, everyone.

I added comments to time.goc and the top of lock_futex.c and lock_sema.c
that should give more context.

Dmitriy and Ian pointed out that the test for t.i == -1 in tsleep was strange.
I had intended tsleep to be like gosched, in that a goroutine could queue
waiting for some event and call tsleep instead of gosched to do a timed
wait.  That part hasn't happened yet and it's not clear if it will be necessary,
so I removed that part of the API and code.

Dmitriy pointed out that the new proc does not play well with the garbage
collector.  In my first draft of this, the Timer structs were all allocated on
C stacks and didn't need to be collected, so it was okay for the proc to run
independently of the GC.  Now that package time can create Timer structs
too, that is clearly not okay anymore.  I changed the code so that the
timerproc is a normal goroutine, which makes it interact correctly with
the garbage collector and also avoids the need for the racy runtime.havetimers.
The procfn hack is gone too.

Ian and Joel pointed out that the semantics of semasleep were fuzzy at best.
The new comment atop lock_sema.c should help.  Another part of the problem
was that I realized that semasleep needed to tell the caller whether the
semaphore had been acquired in order to avoid confusion about the state
of the semaphore, but then I forgot to make the callers use this information.
I have done that now.

Alex pointed out that Windows was storing usec into a variable named ms.
Fixed.

Dmitriy, Ian, and Joel, PTAL in particular at lock_sema.c, openbsd/thread.c,
and lock_futex.c.  All your comments should be addressed.  Dealing with
semaphores is so much harder than dealing with futexes.

Alex, please try this CL on Windows again: the many-thread crash should
be fixed.  This time for sure!  (OT: The other day someone commented
on my App Engine Go shirt thinking that it was Rocky the Flying Squirrel.)

Russ

[hector, 2011-11-07 22:21:14]

On 7 November 2011 21:50, Russ Cox <rsc@golang.org> wrote:
> Alex pointed out that Windows was storing usec into a variable named ms.
> Fixed.

That was me :)

[rsc, 2011-11-07 22:45:16]

On Mon, Nov 7, 2011 at 17:20, Hector Chu <hectorchu@gmail.com> wrote:
> That was me :)

Apologies.  My editor lost the first draft of that message
and I reconstructed it quickly from memory instead of
looking at the review messages.  Oops.

Russ

[hector, 2011-11-07 23:00:25]

Ah I see, thanks for the explanation.  I once lost a long message on a
web form too while typing a reply into codereview.  I felt the pain -
and then I installed Lazarus Form Recovery.

Oh, and Windows changes LGTM.

On 7 November 2011 22:45, Russ Cox <rsc@golang.org> wrote:
> On Mon, Nov 7, 2011 at 17:20, Hector Chu <hectorchu@gmail.com> wrote:
>> That was me :)
>
> Apologies.  My editor lost the first draft of that message
> and I reconstructed it quickly from memory instead of
> looking at the review messages.  Oops.
>
> Russ
>

[brainman, 2011-11-08 00:40:11]

On 2011/11/07 21:50:05, rsc wrote:
> PTAL
> 

Now tests fail:

$ cd $GOROOT/src/pkg/time
$ gotest
rm -f _test/time.a
rm -f _test/time.a
gopack grc _test/time.a _gotest_.8
--- FAIL: time_test.TestAfterTick (1.80 seconds)
        10 ticks of 1e+08 ns took 1.796852e+09 ns, expected 1e+09
--- FAIL: time_test.TestAfterQueuing (0.78 seconds)
        attempt 0 failed: after queue slot 1 arrived at 1.874976e+08, expected [
7.5e+07,1.25e+08]
        attempt 1 failed: after queue slot 2 arrived at 2.656216e+08, expected [
1.75e+08,2.25e+08]
        attempt 2 failed: after queue slot 3 arrived at 3.281208e+08, expected [
2.75e+08,3.25e+08]
        after queue slot 3 arrived at 3.281208e+08, expected [2.75e+08,3.25e+08]

FAIL
gotest: "./8.out.exe" failed: exit status 1

Alex

[brainman, 2011-11-08 02:14:32]

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c
File src/pkg/runtime/lock_sema.c (right):

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:184: // Deadline hasn't arrived.  Keep sleeping.
I think you're missing

ns = deadline - now;

here.

[dvyukov, 2011-11-08 08:24:24]

On 2011/11/07 17:38:47, rsc wrote:
> On Mon, Nov 7, 2011 at 06:26,  <mailto:dvyukov@google.com> wrote:
> > Now it would be nice if we rewrite
> > &nbsp;case now <-time.After(timeout):
> > into
> > &nbsp;runtime.selecttimeout(timeout, &now):
> > Because then we just need to choose a minimal timeout and use timed
> > sleep inside of select. No need to allocate/collect channel,
> > send/receive values, etc. But it won't pass the review, right?
> 
> This is a possible direction to go, but it is far
> from clear that it is a direction we should go.
> Let's not worry about it in this CL.

Oh, I did not mean this CL. That's just some thoughts aloud.
I suspect that one the common use cases is 2-case select where a first case
(non-timeout) is frequently ready. It's a pity that we need to allocate/collect
channels, send/receive values when it can be rewritten along the lines of just
runtime.chansend(c, elem, timeout). I do not see how it can be done outside of
the compiler, however making a language compiler aware of "time"."After" does
not look like the right thing as well.

[dvyukov, 2011-11-08 09:46:45]

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c
File src/pkg/runtime/lock_sema.c (right):

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:120: m->waitsema = runtime·semacreate();
I am not sure a waiting goroutine always calls noteclear before notewait. For
example, getprofile() seems to not do that.

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:200: if(runtime·semasleep(0) < 0)
It is not clear as to whether semasleep() can be interrupted (EINTR) or return
some other error (few lines above you write "Interrupted or timed out"). If yes,
then this check is incorrect, because notewake() updates n->waitm first and
after that releases the semaphore non-atomically, so it can happen that
n->waitm==LOCKED but the semaphore is not yet signaled, so semasleep can
legitimately return "EINTR".

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/runtime.h#ne...
src/pkg/runtime/runtime.h:330: Timer	**pin;
remove

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc
File src/pkg/runtime/time.goc (right):

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
src/pkg/runtime/time.goc:137: siftup(i);
please surround siftup/siftdown with if(i!=timers.len)

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
src/pkg/runtime/time.goc:177: t->f(now, t->arg);
It's suspicious that we use t outside of the lock, looks like a recipe for
problems. I've failed to compromise it, but may we cache t->f and t->arg in
local vars before unlocking the mutex? Just to make it bullet-proof and to not
spent any more time trying to prove its correctness or compromise it. For
example, if we ever implement your "runtime·tsleep as gosched" idea it will do
cause subtle problems.

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
src/pkg/runtime/time.goc:184: g->waitreason = "no pending timers";
IMVHO the description can confuse a user. Perhaps something like "timer
goroutine (idle)" would be more understandable.

[dvyukov, 2011-11-08 10:09:16]

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c
File src/pkg/runtime/lock_sema.c (right):

http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:190: // try to grant us the semaphore when we don't
expect it.
I do not see any correctness issues here, but it looks overly complex. Do we
ever want to use a single note for both timed and non-timed waits? They look
like a completely different use cases. Can't we just assert the usage along the
lines of:

notetwait(n) {
  n->timed = true;
  ...
}

notewait(n) {
  if(n->timed)
    runtime.throw(...);
  ...
}

and then completely remove that rollback part of notetsleep?

[rsc, 2011-11-08 13:47:22]

On Mon, Nov 7, 2011 at 21:14,  <alex.brainman@gmail.com> wrote:
> ns = deadline - now;

Fixed, thanks.  Does that happen to fix your time test?

Russ

[rsc, 2011-11-08 13:55:28]

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
> src/pkg/runtime/lock_sema.c:120: m->waitsema = runtime·semacreate();
> I am not sure a waiting goroutine always calls noteclear before
> notewait. For example, getprofile() seems to not do that.

You're right, fixed.  I thought there was a race setting the waitsema
between sleep and wakeup, but it's okay because sleep doesn't
queue for the wakeup until it has established the semaphore.

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/lock_sema.c#...
> src/pkg/runtime/lock_sema.c:200: if(runtime·semasleep(0) < 0)
> It is not clear as to whether semasleep() can be interrupted (EINTR) or
> return some other error (few lines above you write "Interrupted or timed
> out"). If yes, then this check is incorrect, because notewake() updates
> n->waitm first and after that releases the semaphore non-atomically, so
> it can happen that n->waitm==LOCKED but the semaphore is not yet
> signaled, so semasleep can legitimately return "EINTR".

Thanks.  I have changed this to semasleep(-1).
We know the semaphore is on its way.

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
> src/pkg/runtime/time.goc:137: siftup(i);
> please surround siftup/siftdown with if(i!=timers.len)

Why?  They are correct in that case.

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
> src/pkg/runtime/time.goc:177: t->f(now, t->arg);
> It's suspicious that we use t outside of the lock, looks like a recipe
> for problems. I've failed to compromise it, but may we cache t->f and
> t->arg in local vars before unlocking the mutex? Just to make it
> bullet-proof and to not spent any more time trying to prove its
> correctness or compromise it. For example, if we ever implement your
> "runtime·tsleep as gosched" idea it will do cause subtle problems.

The release of the lock was a dreg from trying to make
timerproc friendly with the gc.  Now that it's a goroutine
we can go back to calling t->f while holding the lock.

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
> src/pkg/runtime/time.goc:184: g->waitreason = "no pending timers";
> IMVHO the description can confuse a user. Perhaps something like "timer
> goroutine (idle)" would be more understandable.

Done.

> src/pkg/runtime/lock_sema.c:190: // try to grant us the semaphore when
> we don't expect it.
> I do not see any correctness issues here, but it looks overly complex.
> Do we ever want to use a single note for both timed and non-timed waits?
> They look like a completely different use cases. Can't we just assert
> the usage along the lines of:
> ...
> and then completely remove that rollback part of notetsleep?

The timer goroutine calls notetsleep(&timers.waitnote, delta)
to wait for either delta ns to pass or for an explicit wakeup by
addtimer.  The rollback is trying to handle that situation.

Russ

[dvyukov, 2011-11-08 14:14:14]

On 2011/11/08 13:55:28, rsc wrote:

>
http://codereview.appspot.com/5334051/diff/18003/src/pkg/runtime/time.goc#new...
> > src/pkg/runtime/time.goc:137: siftup(i);
> > please surround siftup/siftdown with if(i!=timers.len)
> 
> Why?  They are correct in that case.

Well, yes, you're right.

[jsing, 2011-11-08 16:25:51]

With these changes all of the tests pass on OpenBSD/amd64 - I can review the
change more closely tomorrow, unless you wish to commit before then.

http://codereview.appspot.com/5334051/diff/28004/src/pkg/runtime/openbsd/thre...
File src/pkg/runtime/openbsd/thread.c (right):

http://codereview.appspot.com/5334051/diff/28004/src/pkg/runtime/openbsd/thre...
src/pkg/runtime/openbsd/thread.c:68: int32 ms;
Unused.

http://codereview.appspot.com/5334051/diff/28004/src/pkg/runtime/openbsd/thre...
src/pkg/runtime/openbsd/thread.c:84: ts.tv_usec = ns%1000000000LL;
s/usec/nsec/

[dvyukov, 2011-11-08 16:57:08]

LGTM

[brainman, 2011-11-08 22:34:07]

On 2011/11/08 13:47:22, rsc wrote:
> 
> ...  Does that happen to fix your time test?
> 

It does indeed.

LGTM.

Alex

[iant, 2011-11-08 22:48:14]

LGTM

http://codereview.appspot.com/5334051/diff/27004/src/pkg/runtime/lock_sema.c
File src/pkg/runtime/lock_sema.c (right):

http://codereview.appspot.com/5334051/diff/27004/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:15: //		Sleep trying to acquire m->waitsema for at
most ns nanoseconds.
This comment isn't quite what the code does.  How about:

If ns < 0, acquire m->waitsema and return 0.  If ns >= 0, sleep trying to
acquire m->waitsema for at most ns seconds; return 0 if the semaphore was
acquired, -1 if interrupted or timed out.

http://codereview.appspot.com/5334051/diff/27004/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:150: return;
For safety's sake, could we add
    if(n->waitm != LOCKED)
        runtime_throw("aieeeeee");
This code is probably fine but does not fail safe if somebody makes a mistake. 
I think that testing n->waitm non-atomically should be fine here if all is well.

http://codereview.appspot.com/5334051/diff/27004/src/pkg/runtime/lock_sema.c#...
src/pkg/runtime/lock_sema.c:171: return;
Could again double check that n->waitm == LOCKED .

[rsc, 2011-11-09 20:17:11]

*** Submitted as http://code.google.com/p/go/source/detail?r=784b29af787e ***

runtime: add timer support, use for package time

This looks like it is just moving some code from
time to runtime (and translating it to C), but the
runtime can do a better job managing the goroutines,
and it needs this functionality for its own maintenance
(for example, for the garbage collector to hand back
unused memory to the OS on a time delay).
Might as well have just one copy of the timer logic,
and runtime can't depend on time, so vice versa.

It also unifies Sleep, NewTicker, and NewTimer behind
one mechanism, so that there are no claims that one
is more efficient than another.  (For example, today
people recommend using time.After instead of time.Sleep
to avoid blocking an OS thread.)

Fixes issue 1644.
Fixes issue 1731.
Fixes issue 2190.

R=golang-dev, r, hectorchu, iant, iant, jsing, alex.brainman, dvyukov
CC=golang-dev
http://codereview.appspot.com/5334051