runtime: add support for time.NewTimer and time.NewTicker

This commit adds support for time.NewTimer and time.NewTicker. It also
adds support for the Stop() method on time.Timer, but doesn't (yet) add
support for the Reset() method.

The implementation has been carefully written so that programs that
don't use these timers will normally not see an increase in RAM or
binary size. None of the examples in the drivers repo change as a result
of this commit. This comes at the cost of slightly more complex code and
possibly slower execution of the timers when they are used.

4 files changed, 192 insertions, 3 deletions

diff --git a/src/runtime/scheduler.go b/src/runtime/scheduler.go
index 383051aeb..7367eed35 100644
--- a/src/runtime/scheduler.go
+++ b/src/runtime/scheduler.go
@@ -12,6 +12,7 @@ package runtime
 
 import (
 	"internal/task"
+	"runtime/interrupt"
 )
 
 const schedulerDebug = false
@@ -27,6 +28,7 @@ var (
 	runqueue           task.Queue
 	sleepQueue         *task.Task
 	sleepQueueBaseTime timeUnit
+	timerQueue         *timerNode
 )
 
 // Simple logging, for debugging.
@@ -114,6 +116,46 @@ func addSleepTask(t *task.Task, duration timeUnit) {
 	*q = t
 }
 
+// addTimer adds the given timer node to the timer queue. It must not be in the
+// queue already.
+// This function is very similar to addSleepTask but for timerQueue instead of
+// sleepQueue.
+func addTimer(tim *timerNode) {
+	mask := interrupt.Disable()
+
+	// Add to timer queue.
+	q := &timerQueue
+	for ; *q != nil; q = &(*q).next {
+		if tim.whenTicks() < (*q).whenTicks() {
+			// this will finish earlier than the next - insert here
+			break
+		}
+	}
+	tim.next = *q
+	*q = tim
+	interrupt.Restore(mask)
+}
+
+// removeTimer is the implementation of time.stopTimer. It removes a timer from
+// the timer queue, returning true if the timer is present in the timer queue.
+func removeTimer(tim *timer) bool {
+	removedTimer := false
+	mask := interrupt.Disable()
+	for t := &timerQueue; *t != nil; t = &(*t).next {
+		if (*t).timer == tim {
+			scheduleLog("removed timer")
+			*t = (*t).next
+			removedTimer = true
+			break
+		}
+	}
+	if !removedTimer {
+		scheduleLog("did not remove timer")
+	}
+	interrupt.Restore(mask)
+	return removedTimer
+}
+
 // Run the scheduler until all tasks have finished.
 func scheduler() {
 	// Main scheduler loop.
@@ -121,7 +163,7 @@ func scheduler() {
 	for !schedulerDone {
 		scheduleLog("")
 		scheduleLog("  schedule")
-		if sleepQueue != nil {
+		if sleepQueue != nil || timerQueue != nil {
 			now = ticks()
 		}
 
@@ -136,9 +178,20 @@ func scheduler() {
 			runqueue.Push(t)
 		}
 
+		// Check for expired timers to trigger.
+		if timerQueue != nil && now >= timerQueue.whenTicks() {
+			scheduleLog("--- timer awoke")
+			// Pop timer from queue.
+			tn := timerQueue
+			timerQueue = tn.next
+			tn.next = nil
+			// Run the callback stored in this timer node.
+			tn.callback(tn)
+		}
+
 		t := runqueue.Pop()
 		if t == nil {
-			if sleepQueue == nil {
+			if sleepQueue == nil && timerQueue == nil {
 				if asyncScheduler {
 					// JavaScript is treated specially, see below.
 					return
@@ -146,12 +199,26 @@ func scheduler() {
 				waitForEvents()
 				continue
 			}
-			timeLeft := timeUnit(sleepQueue.Data) - (now - sleepQueueBaseTime)
+
+			var timeLeft timeUnit
+			if sleepQueue != nil {
+				timeLeft = timeUnit(sleepQueue.Data) - (now - sleepQueueBaseTime)
+			}
+			if timerQueue != nil {
+				timeLeftForTimer := timerQueue.whenTicks() - now
+				if sleepQueue == nil || timeLeftForTimer < timeLeft {
+					timeLeft = timeLeftForTimer
+				}
+			}
+
 			if schedulerDebug {
 				println("  sleeping...", sleepQueue, uint(timeLeft))
 				for t := sleepQueue; t != nil; t = t.Next {
 					println("    task sleeping:", t, timeUnit(t.Data))
 				}
+				for tim := timerQueue; tim != nil; tim = tim.next {
+					println("---   timer waiting:", tim, tim.whenTicks())
+				}
 			}
 			sleepTicks(timeLeft)
 			if asyncScheduler {
diff --git a/src/runtime/time.go b/src/runtime/time.go
new file mode 100644
index 000000000..b14eae6a0
--- /dev/null
+++ b/src/runtime/time.go
@@ -0,0 +1,50 @@
+package runtime
+
+// timerNode is an element in a linked list of timers.
+type timerNode struct {
+	next     *timerNode
+	timer    *timer
+	callback func(*timerNode)
+}
+
+// whenTicks returns the (absolute) time when this timer should trigger next.
+func (t *timerNode) whenTicks() timeUnit {
+	return nanosecondsToTicks(t.timer.when)
+}
+
+// Defined in the time package, implemented here in the runtime.
+//go:linkname startTimer time.startTimer
+func startTimer(tim *timer) {
+	addTimer(&timerNode{
+		timer:    tim,
+		callback: timerCallback,
+	})
+	scheduleLog("adding timer")
+}
+
+// timerCallback is called when a timer expires. It makes sure to call the
+// callback in the time package and to re-add the timer to the queue if this is
+// a ticker (repeating timer).
+// This is intentionally used as a callback and not a direct call (even though a
+// direct call would be trivial), because otherwise a circular dependency
+// between scheduler, addTimer and timerQueue would form. Such a circular
+// dependency causes timerQueue not to get optimized away.
+// If timerQueue doesn't get optimized away, small programs (that don't call
+// time.NewTimer etc) would still pay the cost of these timers.
+func timerCallback(tn *timerNode) {
+	// Run timer function (implemented in the time package).
+	// The seq parameter to the f function is not used in the time
+	// package so is left zero.
+	tn.timer.f(tn.timer.arg, 0)
+
+	// If this is a periodic timer (a ticker), re-add it to the queue.
+	if tn.timer.period != 0 {
+		tn.timer.when += tn.timer.period
+		addTimer(tn)
+	}
+}
+
+//go:linkname stopTimer time.stopTimer
+func stopTimer(tim *timer) bool {
+	return removeTimer(tim)
+}
diff --git a/src/runtime/timer_go116.go b/src/runtime/timer_go116.go
new file mode 100644
index 000000000..9ff1625a8
--- /dev/null
+++ b/src/runtime/timer_go116.go
@@ -0,0 +1,36 @@
+//go:build !go1.18
+// +build !go1.18
+
+// Portions 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.
+
+package runtime
+
+type puintptr uintptr
+
+// Package time knows the layout of this structure.
+// If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
+type timer struct {
+	// If this timer is on a heap, which P's heap it is on.
+	// puintptr rather than *p to match uintptr in the versions
+	// of this struct defined in other packages.
+	pp puintptr
+
+	// Timer wakes up at when, and then at when+period, ... (period > 0 only)
+	// each time calling f(arg, now) in the timer goroutine, so f must be
+	// a well-behaved function and not block.
+	//
+	// when must be positive on an active timer.
+	when   int64
+	period int64
+	f      func(interface{}, uintptr)
+	arg    interface{}
+	seq    uintptr
+
+	// What to set the when field to in timerModifiedXX status.
+	nextwhen int64
+
+	// The status field holds one of the values below.
+	status uint32
+}
diff --git a/src/runtime/timer_go118.go b/src/runtime/timer_go118.go
new file mode 100644
index 000000000..894ed8495
--- /dev/null
+++ b/src/runtime/timer_go118.go
@@ -0,0 +1,36 @@
+//go:build go1.18
+// +build go1.18
+
+// Portions 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.
+
+package runtime
+
+type puintptr uintptr
+
+// Package time knows the layout of this structure.
+// If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
+type timer struct {
+	// If this timer is on a heap, which P's heap it is on.
+	// puintptr rather than *p to match uintptr in the versions
+	// of this struct defined in other packages.
+	pp puintptr
+
+	// Timer wakes up at when, and then at when+period, ... (period > 0 only)
+	// each time calling f(arg, now) in the timer goroutine, so f must be
+	// a well-behaved function and not block.
+	//
+	// when must be positive on an active timer.
+	when   int64
+	period int64
+	f      func(any, uintptr)
+	arg    any
+	seq    uintptr
+
+	// What to set the when field to in timerModifiedXX status.
+	nextwhen int64
+
+	// The status field holds one of the values below.
+	status uint32
+}