1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
//go:build scheduler.tasks || scheduler.asyncify
package runtime
// This file implements the TinyGo scheduler. This scheduler is a very simple
// cooperative round robin scheduler, with a runqueue that contains a linked
// list of goroutines (tasks) that should be run next, in order of when they
// were added to the queue (first-in, first-out). It also contains a sleep queue
// with sleeping goroutines in order of when they should be re-activated.
//
// The scheduler is used both for the asyncify based scheduler and for the task
// based scheduler. In both cases, the 'internal/task.Task' type is used to represent one
// goroutine.
import (
"internal/task"
"runtime/interrupt"
)
// On JavaScript, we can't do a blocking sleep. Instead we have to return and
// queue a new scheduler invocation using setTimeout.
const asyncScheduler = GOOS == "js"
// Queues used by the scheduler.
var (
runqueue task.Queue
sleepQueue *task.Task
sleepQueueBaseTime timeUnit
timerQueue *timerNode
)
// deadlock is called when a goroutine cannot proceed any more, but is in theory
// not exited (so deferred calls won't run). This can happen for example in code
// like this, that blocks forever:
//
// select{}
//
//go:noinline
func deadlock() {
// call yield without requesting a wakeup
task.Pause()
panic("unreachable")
}
// Add this task to the end of the run queue.
func scheduleTask(t *task.Task) {
runqueue.Push(t)
}
func Gosched() {
runqueue.Push(task.Current())
task.Pause()
}
// Add this task to the sleep queue, assuming its state is set to sleeping.
func addSleepTask(t *task.Task, duration timeUnit) {
if schedulerDebug {
println(" set sleep:", t, duration)
if t.Next != nil {
panic("runtime: addSleepTask: expected next task to be nil")
}
}
t.Data = uint64(duration)
now := ticks()
if sleepQueue == nil {
scheduleLog(" -> sleep new queue")
// set new base time
sleepQueueBaseTime = now
}
// Add to sleep queue.
q := &sleepQueue
for ; *q != nil; q = &(*q).Next {
if t.Data < (*q).Data {
// this will finish earlier than the next - insert here
break
} else {
// this will finish later - adjust delay
t.Data -= (*q).Data
}
}
if *q != nil {
// cut delay time between this sleep task and the next
(*q).Data -= t.Data
}
t.Next = *q
*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
}
func schedulerRunQueue() *task.Queue {
return &runqueue
}
// Run the scheduler until all tasks have finished.
// There are a few special cases:
// - When returnAtDeadlock is true, it also returns when there are no more
// runnable goroutines.
// - When using the asyncify scheduler, it returns when it has to wait
// (JavaScript uses setTimeout so the scheduler must return to the JS
// environment).
func scheduler(returnAtDeadlock bool) {
// Main scheduler loop.
var now timeUnit
for !mainExited {
scheduleLog("")
scheduleLog(" schedule")
if sleepQueue != nil || timerQueue != nil {
now = ticks()
}
// Add tasks that are done sleeping to the end of the runqueue so they
// will be executed soon.
if sleepQueue != nil && now-sleepQueueBaseTime >= timeUnit(sleepQueue.Data) {
t := sleepQueue
scheduleLogTask(" awake:", t)
sleepQueueBaseTime += timeUnit(t.Data)
sleepQueue = t.Next
t.Next = nil
runqueue.Push(t)
}
// Check for expired timers to trigger.
if timerQueue != nil && now >= timerQueue.whenTicks() {
scheduleLog("--- timer awoke")
delay := ticksToNanoseconds(now - timerQueue.whenTicks())
// Pop timer from queue.
tn := timerQueue
timerQueue = tn.next
tn.next = nil
// Run the callback stored in this timer node.
tn.callback(tn, delay)
}
t := runqueue.Pop()
if t == nil {
if sleepQueue == nil && timerQueue == nil {
if returnAtDeadlock {
return
}
if asyncScheduler {
// JavaScript is treated specially, see below.
return
}
waitForEvents()
continue
}
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())
}
}
if timeLeft > 0 {
sleepTicks(timeLeft)
if asyncScheduler {
// The sleepTicks function above only sets a timeout at
// which point the scheduler will be called again. It does
// not really sleep. So instead of sleeping, we return and
// expect to be called again.
break
}
}
continue
}
// Run the given task.
scheduleLogTask(" run:", t)
t.Resume()
}
}
// Pause the current task for a given time.
//
//go:linkname sleep time.Sleep
func sleep(duration int64) {
if duration <= 0 {
return
}
addSleepTask(task.Current(), nanosecondsToTicks(duration))
task.Pause()
}
// run is called by the program entry point to execute the go program.
// With a scheduler, init and the main function are invoked in a goroutine before starting the scheduler.
func run() {
initHeap()
go func() {
initAll()
callMain()
mainExited = true
}()
scheduler(false)
}
const hasScheduler = true
|