diff options
| -rw-r--r-- | src/internal/task/task.go | 3 | ||||
| -rw-r--r-- | src/internal/task/task_asyncify.go | 5 | ||||
| -rw-r--r-- | src/internal/task/task_stack.go | 5 | ||||
| -rw-r--r-- | src/runtime/arch_tinygoriscv.go | 2 | ||||
| -rw-r--r-- | src/runtime/chan.go | 6 | ||||
| -rw-r--r-- | src/runtime/cond.go | 2 | ||||
| -rw-r--r-- | src/runtime/gc_blocks.go | 5 | ||||
| -rw-r--r-- | src/runtime/scheduler.go | 221 | ||||
| -rw-r--r-- | src/runtime/scheduler_any.go | 31 | ||||
| -rw-r--r-- | src/runtime/scheduler_cooperative.go | 252 | ||||
| -rw-r--r-- | src/runtime/scheduler_none.go | 58 | ||||
| -rw-r--r-- | src/sync/mutex.go | 2 |
12 files changed, 315 insertions, 277 deletions
diff --git a/src/internal/task/task.go b/src/internal/task/task.go index c1ee57dda..bce65b582 100644 --- a/src/internal/task/task.go +++ b/src/internal/task/task.go @@ -33,3 +33,6 @@ func getGoroutineStackSize(fn uintptr) uintptr //go:linkname runtime_alloc runtime.alloc func runtime_alloc(size uintptr, layout unsafe.Pointer) unsafe.Pointer + +//go:linkname scheduleTask runtime.scheduleTask +func scheduleTask(*Task) diff --git a/src/internal/task/task_asyncify.go b/src/internal/task/task_asyncify.go index 55a1044e4..637a6b223 100644 --- a/src/internal/task/task_asyncify.go +++ b/src/internal/task/task_asyncify.go @@ -52,7 +52,7 @@ type stackState struct { func start(fn uintptr, args unsafe.Pointer, stackSize uintptr) { t := &Task{} t.state.initialize(fn, args, stackSize) - runqueuePushBack(t) + scheduleTask(t) } //export tinygo_launch @@ -82,9 +82,6 @@ func (s *state) initialize(fn uintptr, args unsafe.Pointer, stackSize uintptr) { s.csp = unsafe.Add(stack, stackSize) } -//go:linkname runqueuePushBack runtime.runqueuePushBack -func runqueuePushBack(*Task) - // currentTask is the current running task, or nil if currently in the scheduler. var currentTask *Task diff --git a/src/internal/task/task_stack.go b/src/internal/task/task_stack.go index 551612425..88a097068 100644 --- a/src/internal/task/task_stack.go +++ b/src/internal/task/task_stack.go @@ -101,15 +101,12 @@ func swapTask(oldStack uintptr, newStack *uintptr) //go:extern tinygo_startTask var startTask [0]uint8 -//go:linkname runqueuePushBack runtime.runqueuePushBack -func runqueuePushBack(*Task) - // start creates and starts a new goroutine with the given function and arguments. // The new goroutine is scheduled to run later. func start(fn uintptr, args unsafe.Pointer, stackSize uintptr) { t := &Task{} t.state.initialize(fn, args, stackSize) - runqueuePushBack(t) + scheduleTask(t) } // OnSystemStack returns whether the caller is running on the system stack. diff --git a/src/runtime/arch_tinygoriscv.go b/src/runtime/arch_tinygoriscv.go index 0d376c48b..921c775a5 100644 --- a/src/runtime/arch_tinygoriscv.go +++ b/src/runtime/arch_tinygoriscv.go @@ -36,7 +36,7 @@ func procUnpin() { func waitForEvents() { mask := riscv.DisableInterrupts() - if !runqueue.Empty() { + if runqueue := schedulerRunQueue(); runqueue == nil || !runqueue.Empty() { riscv.Asm("wfi") } riscv.EnableInterrupts(mask) diff --git a/src/runtime/chan.go b/src/runtime/chan.go index 269f5a01b..1f0d7ced8 100644 --- a/src/runtime/chan.go +++ b/src/runtime/chan.go @@ -183,8 +183,7 @@ func (ch *channel) resumeRX(ok bool) unsafe.Pointer { b.detach() } - // push task onto runqueue - runqueue.Push(b.t) + scheduleTask(b.t) return dst } @@ -210,8 +209,7 @@ func (ch *channel) resumeTX() unsafe.Pointer { b.detach() } - // push task onto runqueue - runqueue.Push(b.t) + scheduleTask(b.t) return src } diff --git a/src/runtime/cond.go b/src/runtime/cond.go index 00e89932a..b27ab08ab 100644 --- a/src/runtime/cond.go +++ b/src/runtime/cond.go @@ -34,7 +34,7 @@ func (c *Cond) Notify() bool { default: // Unblock the waiting task. if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.t)), unsafe.Pointer(t), nil) { - runqueuePushBack(t) + scheduleTask(t) return true } } diff --git a/src/runtime/gc_blocks.go b/src/runtime/gc_blocks.go index b2d2fed7f..d58bfd92a 100644 --- a/src/runtime/gc_blocks.go +++ b/src/runtime/gc_blocks.go @@ -464,12 +464,13 @@ func runGC() (freeBytes uintptr) { // Therefore we need to scan the runqueue separately. var markedTaskQueue task.Queue runqueueScan: + runqueue := schedulerRunQueue() for !runqueue.Empty() { // Pop the next task off of the runqueue. t := runqueue.Pop() // Mark the task if it has not already been marked. - markRoot(uintptr(unsafe.Pointer(&runqueue)), uintptr(unsafe.Pointer(t))) + markRoot(uintptr(unsafe.Pointer(runqueue)), uintptr(unsafe.Pointer(t))) // Push the task onto our temporary queue. markedTaskQueue.Push(t) @@ -484,7 +485,7 @@ func runGC() (freeBytes uintptr) { interrupt.Restore(i) goto runqueueScan } - runqueue = markedTaskQueue + *runqueue = markedTaskQueue interrupt.Restore(i) } else { finishMark() diff --git a/src/runtime/scheduler.go b/src/runtime/scheduler.go index 8ba461e4d..d84ccf3e0 100644 --- a/src/runtime/scheduler.go +++ b/src/runtime/scheduler.go @@ -1,36 +1,11 @@ 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" -) +import "internal/task" const schedulerDebug = false -// 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" - var mainExited bool -// Queues used by the scheduler. -var ( - runqueue task.Queue - sleepQueue *task.Task - sleepQueueBaseTime timeUnit - timerQueue *timerNode -) - // Simple logging, for debugging. func scheduleLog(msg string) { if schedulerDebug { @@ -52,204 +27,12 @@ func scheduleLogChan(msg string, ch *channel, t *task.Task) { } } -// 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") -} - // Goexit terminates the currently running goroutine. No other goroutines are affected. // // Unlike the main Go implementation, no deferred calls will be run. // //go:inline func Goexit() { - // its really just a deadlock + // TODO: run deferred functions deadlock() } - -// Add this task to the end of the run queue. -func runqueuePushBack(t *task.Task) { - runqueue.Push(t) -} - -// 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 -} - -// 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() - } -} - -func Gosched() { - runqueue.Push(task.Current()) - task.Pause() -} diff --git a/src/runtime/scheduler_any.go b/src/runtime/scheduler_any.go deleted file mode 100644 index 2e7861a15..000000000 --- a/src/runtime/scheduler_any.go +++ /dev/null @@ -1,31 +0,0 @@ -//go:build !scheduler.none - -package runtime - -import "internal/task" - -// 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 diff --git a/src/runtime/scheduler_cooperative.go b/src/runtime/scheduler_cooperative.go new file mode 100644 index 000000000..5c4dfd5bf --- /dev/null +++ b/src/runtime/scheduler_cooperative.go @@ -0,0 +1,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 diff --git a/src/runtime/scheduler_none.go b/src/runtime/scheduler_none.go index 5079a8085..7775b360e 100644 --- a/src/runtime/scheduler_none.go +++ b/src/runtime/scheduler_none.go @@ -2,6 +2,19 @@ package runtime +import "internal/task" + +const hasScheduler = false + +// run is called by the program entry point to execute the go program. +// With the "none" scheduler, init and the main function are invoked directly. +func run() { + initHeap() + initAll() + callMain() + mainExited = true +} + //go:linkname sleep time.Sleep func sleep(duration int64) { if duration <= 0 { @@ -11,18 +24,43 @@ func sleep(duration int64) { sleepTicks(nanosecondsToTicks(duration)) } +func deadlock() { + // The only goroutine available is deadlocked. + runtimePanic("all goroutines are asleep - deadlock!") +} + +func scheduleTask(t *task.Task) { + // Pause() will panic, so this should not be reachable. +} + +func Gosched() { + // There are no other goroutines, so there's nothing to schedule. +} + +func addTimer(tim *timerNode) { + runtimePanic("timers not supported without a scheduler") +} + +func removeTimer(tim *timer) bool { + runtimePanic("timers not supported without a scheduler") + return false +} + +func schedulerRunQueue() *task.Queue { + // This function is not actually used, it is only called when hasScheduler + // is true. + runtimePanic("unreachable: no runqueue without a scheduler") + return nil +} + +func scheduler(returnAtDeadlock bool) { + // The scheduler should never be run when using -scheduler=none. Meaning, + // this code should be unreachable. + runtimePanic("unreachable: scheduler must not be called with the 'none' scheduler") +} + // getSystemStackPointer returns the current stack pointer of the system stack. // This is always the current stack pointer. func getSystemStackPointer() uintptr { return getCurrentStackPointer() } - -// run is called by the program entry point to execute the go program. -// With the "none" scheduler, init and the main function are invoked directly. -func run() { - initHeap() - initAll() - callMain() -} - -const hasScheduler = false diff --git a/src/sync/mutex.go b/src/sync/mutex.go index 3db705af0..b62b9fafd 100644 --- a/src/sync/mutex.go +++ b/src/sync/mutex.go @@ -10,7 +10,7 @@ type Mutex struct { blocked task.Stack } -//go:linkname scheduleTask runtime.runqueuePushBack +//go:linkname scheduleTask runtime.scheduleTask func scheduleTask(*task.Task) func (m *Mutex) Lock() { |