runtime: convert timers to Go
LGTM=rsc
R=golang-codereviews, ruiu, rsc, daniel.morsing
CC=golang-codereviews, khr
https://golang.org/cl/123700044
diff --git a/src/pkg/runtime/time.go b/src/pkg/runtime/time.go
new file mode 100644
index 0000000..9430414
--- /dev/null
+++ b/src/pkg/runtime/time.go
@@ -0,0 +1,263 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Time-related runtime and pieces of package time.
+
+package runtime
+
+import "unsafe"
+
+// Package time knows the layout of this structure.
+// If this struct changes, adjust ../time/sleep.go:/runtimeTimer and netpoll.goc:/timer.
+// For GOOS=nacl, package syscall knows the layout of this structure.
+// If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer.
+type timer struct {
+ i int // heap index
+
+ // Timer wakes up at when, and then at when+period, ... (period > 0 only)
+ // each time calling f(now, arg) in the timer goroutine, so f must be
+ // a well-behaved function and not block.
+ when int64
+ period int64
+ f func(interface{})
+ arg interface{}
+}
+
+var timers struct {
+ lock lock
+ gp *g
+ created bool
+ sleeping bool
+ rescheduling bool
+ waitnote note
+ t []*timer
+}
+
+// Package time APIs.
+// Godoc uses the comments in package time, not these.
+
+// time.now is implemented in assembly.
+
+// Sleep puts the current goroutine to sleep for at least ns nanoseconds.
+func timeSleep(ns int64) {
+ if ns <= 0 {
+ return
+ }
+
+ t := new(timer)
+ t.when = gonanotime() + ns
+ t.f = goroutineReady
+ t.arg = getg()
+ golock(&timers.lock)
+ addtimerLocked(t)
+ goparkunlock(&timers.lock, "sleep")
+}
+
+// startTimer adds t to the timer heap.
+func startTimer(t *timer) {
+ if raceenabled {
+ racerelease(unsafe.Pointer(t))
+ }
+ addtimer(t)
+}
+
+// stopTimer removes t from the timer heap if it is there.
+// It returns true if t was removed, false if t wasn't even there.
+func stopTimer(t *timer) bool {
+ return deltimer(t)
+}
+
+// Go runtime.
+
+// Ready the goroutine arg.
+func goroutineReady(arg interface{}) {
+ goready(arg.(*g))
+}
+
+func addtimer(t *timer) {
+ golock(&timers.lock)
+ addtimerLocked(t)
+ gounlock(&timers.lock)
+}
+
+// Add a timer to the heap and start or kick the timer proc.
+// If the new timer is earlier than any of the others.
+// Timers are locked.
+func addtimerLocked(t *timer) {
+ // when must never be negative; otherwise timerproc will overflow
+ // during its delta calculation and never expire other runtime·timers.
+ if t.when < 0 {
+ t.when = 1<<63 - 1
+ }
+ t.i = len(timers.t)
+ timers.t = append(timers.t, t)
+ siftupTimer(t.i)
+ if t.i == 0 {
+ // siftup moved to top: new earliest deadline.
+ if timers.sleeping {
+ timers.sleeping = false
+ gonotewakeup(&timers.waitnote)
+ }
+ if timers.rescheduling {
+ timers.rescheduling = false
+ goready(timers.gp)
+ }
+ }
+ if !timers.created {
+ timers.created = true
+ go timerproc()
+ }
+}
+
+// Delete timer t from the heap.
+// Do not need to update the timerproc: if it wakes up early, no big deal.
+func deltimer(t *timer) bool {
+ // Dereference t so that any panic happens before the lock is held.
+ // Discard result, because t might be moving in the heap.
+ _ = t.i
+
+ golock(&timers.lock)
+ // t may not be registered anymore and may have
+ // a bogus i (typically 0, if generated by Go).
+ // Verify it before proceeding.
+ i := t.i
+ last := len(timers.t) - 1
+ if i < 0 || i > last || timers.t[i] != t {
+ gounlock(&timers.lock)
+ return false
+ }
+ if i != last {
+ timers.t[i] = timers.t[last]
+ timers.t[i].i = i
+ }
+ timers.t[last] = nil
+ timers.t = timers.t[:last]
+ if i != last {
+ siftupTimer(i)
+ siftdownTimer(i)
+ }
+ gounlock(&timers.lock)
+ return true
+}
+
+// Timerproc runs the time-driven events.
+// It sleeps until the next event in the timers heap.
+// If addtimer inserts a new earlier event, addtimer1 wakes timerproc early.
+func timerproc() {
+ timers.gp = getg()
+ timers.gp.issystem = 1
+ for {
+ golock(&timers.lock)
+ timers.sleeping = false
+ now := gonanotime()
+ delta := int64(-1)
+ for {
+ if len(timers.t) == 0 {
+ delta = -1
+ break
+ }
+ t := timers.t[0]
+ delta = t.when - now
+ if delta > 0 {
+ break
+ }
+ if t.period > 0 {
+ // leave in heap but adjust next time to fire
+ t.when += t.period * (1 + -delta/t.period)
+ siftdownTimer(0)
+ } else {
+ // remove from heap
+ last := len(timers.t) - 1
+ if last > 0 {
+ timers.t[0] = timers.t[last]
+ timers.t[0].i = 0
+ }
+ timers.t[last] = nil
+ timers.t = timers.t[:last]
+ if last > 0 {
+ siftdownTimer(0)
+ }
+ t.i = -1 // mark as removed
+ }
+ f := t.f
+ arg := t.arg
+ gounlock(&timers.lock)
+ if raceenabled {
+ raceacquire(unsafe.Pointer(t))
+ }
+ f(arg)
+ golock(&timers.lock)
+ }
+ if delta < 0 {
+ // No timers left - put goroutine to sleep.
+ timers.rescheduling = true
+ timers.gp.isbackground = 1
+ goparkunlock(&timers.lock, "timer goroutine (idle)")
+ timers.gp.isbackground = 0
+ continue
+ }
+ // At least one timer pending. Sleep until then.
+ timers.sleeping = true
+ gonoteclear(&timers.waitnote)
+ gounlock(&timers.lock)
+ gonotetsleepg(&timers.waitnote, delta)
+ }
+}
+
+// Heap maintenance algorithms.
+
+func siftupTimer(i int) {
+ t := timers.t
+ when := t[i].when
+ tmp := t[i]
+ for i > 0 {
+ p := (i - 1) / 4 // parent
+ if when >= t[p].when {
+ break
+ }
+ t[i] = t[p]
+ t[i].i = i
+ t[p] = tmp
+ t[p].i = p
+ i = p
+ }
+}
+
+func siftdownTimer(i int) {
+ t := timers.t
+ n := len(t)
+ when := t[i].when
+ tmp := t[i]
+ for {
+ c := i*4 + 1 // left child
+ c3 := c + 2 // mid child
+ if c >= n {
+ break
+ }
+ w := t[c].when
+ if c+1 < n && t[c+1].when < w {
+ w = t[c+1].when
+ c++
+ }
+ if c3 < n {
+ w3 := t[c3].when
+ if c3+1 < n && t[c3+1].when < w3 {
+ w3 = t[c3+1].when
+ c3++
+ }
+ if w3 < w {
+ w = w3
+ c = c3
+ }
+ }
+ if w >= when {
+ break
+ }
+ t[i] = t[c]
+ t[i].i = i
+ t[c] = tmp
+ t[c].i = c
+ i = c
+ }
+}
