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