Improve futex_wake behaviour. The current code yields and schedules a new thread if any equal or higher-priority thread has become runnable. The new code decomposes these cases. If a new thread is runnable and should run now, the current thread yields. If a new thread is runnable but is the same priority as the current thread, the scheduler ensures that a timer interrupt is ready but does not yield immediately. This improves the test suite performance by around 2% and a producer-consumer microbenchmark by about 35%.
diff --git a/sdk/core/scheduler/main.cc b/sdk/core/scheduler/main.cc index 0aef309..214bca0 100644 --- a/sdk/core/scheduler/main.cc +++ b/sdk/core/scheduler/main.cc
@@ -14,7 +14,6 @@ #include <futex.h> #include <interrupt.h> #include <locks.hh> -#include <new> #include <priv/riscv.h> #include <riscvreg.h> #include <simulator.h> @@ -122,6 +121,26 @@ */ static constexpr auto UnboundedSleep = std::numeric_limits<uint32_t>::max(); + enum FutexWakeKind + { + /** + * The futex wake did not make any threads runnable that would be + * scheduled preemptively. + */ + NoYield, + /** + * The futex wake made a thread at the current priority level runnable, + * the caller should ensure that there is a timer interrupt scheduled + * to make the current thread yield later. + */ + YieldLater, + /** + * The futex wake made a thread at a higher priority level runnable, + * the caller should yield to allow the other thread to run immediately. + */ + YieldNow, + }; + /** * Helper that wakes a set of up to `count` threads waiting on the futex * whose address is given by the `key` parameter. @@ -134,11 +153,10 @@ * dropped back to the previous priority. * - The number of sleeper that were awoken. */ - std::tuple<bool, bool, int> + std::tuple<bool, int> futex_wake(ptraddr_t key, uint32_t count = std::numeric_limits<uint32_t>::max()) { - bool shouldYield = false; bool shouldRecalculatePriorityBoost = false; // The number of threads that we've woken, this is the return value on // success. @@ -150,7 +168,8 @@ { shouldRecalculatePriorityBoost |= thread->futexPriorityInheriting; - shouldYield = thread->ready(Thread::WakeReason::Futex); + thread->ready(Thread::WakeReason::Futex); + Debug::log("futex_wake woke thread {}", thread->id_get()); count--; woke++; } @@ -163,9 +182,10 @@ MultiWaiterInternal::wake_waiters(key, count); count -= multiwaitersWoken; woke += multiwaitersWoken; - shouldYield |= (multiwaitersWoken > 0); } - return {shouldYield, shouldRecalculatePriorityBoost, woke}; + Debug::log("futex_wake on {} woke {} waiters", key, woke); + + return {shouldRecalculatePriorityBoost, woke}; } } // namespace @@ -297,8 +317,11 @@ word++; // Wake anyone sleeping on this futex. Interrupt futexes // are not priority inheriting. - std::tie(schedNeeded, std::ignore, std::ignore) = + int woke; + Debug::log("Waking waiters on interrupt futex {}", &word); + std::tie(std::ignore, woke) = futex_wake(Capability{&word}.address()); + schedNeeded |= (woke > 0); }); tick = schedNeeded; break; @@ -530,7 +553,24 @@ } ptraddr_t key = Capability{address}.address(); - auto [shouldYield, shouldResetPrioirity, woke] = futex_wake(key, count); + auto [shouldResetPrioirity, woke] = futex_wake(key, count); + + FutexWakeKind shouldYield = NoYield; + + if (woke > 0) + { + auto *thread = Thread::current_get(); + if (!thread->is_highest_priority()) + { + shouldYield = YieldNow; + } + else if (thread->has_priority_peers()) + { + shouldYield = + thread->has_run_for_full_tick() ? YieldNow : YieldLater; + } + Debug::log("futex_wake yielding? {}", shouldYield); + } // If this futex wake is dropping a priority boost, reset the boost. if (shouldResetPrioirity) @@ -551,12 +591,18 @@ priority_boost_for_thread(currentThread->id_get())); // If we have dropped priority below that of another runnable thread, we // should yield now. - shouldYield |= !currentThread->is_highest_priority(); } - if (shouldYield) + switch (shouldYield) { - yield(); + case YieldLater: + Timer::ensure_tick(); + break; + case YieldNow: + yield(); + break; + case NoYield: + break; } return woke;
diff --git a/sdk/core/scheduler/thread.h b/sdk/core/scheduler/thread.h index f937c46..e050e08 100644 --- a/sdk/core/scheduler/thread.h +++ b/sdk/core/scheduler/thread.h
@@ -5,8 +5,10 @@ #include "common.h" #include <cdefs.h> +#include <platform-timer.hh> #include <priv/riscv.h> #include <strings.h> +#include <tick_macros.h> #include <utils.hh> namespace @@ -111,6 +113,15 @@ current->priority, current->OriginalPriority); } + if (current != th) + { + current->expiryTime = TimerCore::time(); + } +#ifdef CLANG_TIDY + // The static analyser thinks that `debug_log_message_write` may + // assign `nullptr` to `current`. + __builtin_assume(current != nullptr); +#endif return current->tStackPtr; } return schedTStack; @@ -203,10 +214,9 @@ * the resource disappearing, do some clean-ups. * @param the reason why this thread is now able to be scheduled */ - bool ready(WakeReason reason) + void ready(WakeReason reason) { int64_t ticksLeft; - bool schedule = false; // We must be suspended. Debug::Assert(state == ThreadState::Suspended, @@ -229,23 +239,14 @@ if (priority > highestPriority) { highestPriority = priority; - schedule = true; } } - // If this is the same priority as the current thread, we may need - // to update the timer. - if (priority >= highestPriority) - { - schedule = true; - } if (reason == WakeReason::Timer || reason == WakeReason::Delete) { multiWaiter = nullptr; } list_insert(&priorityList[priority]); isYielding = false; - - return schedule; } /** @@ -543,6 +544,17 @@ return next != this; } + /** + * Returns true if the thread has run for a complete tick. This must + * be called only on the currently running thread. + */ + bool has_run_for_full_tick() + { + Debug::Assert(this == current, + "Only the current thread is running"); + return TimerCore::time() >= expiryTime + TIMERCYCLES_PER_TICK; + } + ~ThreadImpl() { // We have static definition of threads. We only create threads in @@ -564,8 +576,12 @@ ///@} /// Pointer to the list of the resource this thread is blocked on. ThreadImpl **sleepQueue; - /// If suspended, when will this thread expire. The maximum value is - /// special-cased to mean blocked indefinitely. + /** + * If suspended, when will this thread expire. The maximum value is + * special-cased to mean blocked indefinitely. + * + * When a thread is running, this the time at which it was scheduled. + */ uint64_t expiryTime{static_cast<uint64_t>(-1)}; /// The number of cycles that this thread has been scheduled for.
diff --git a/sdk/core/scheduler/timer.h b/sdk/core/scheduler/timer.h index c74a9d5..5a48924 100644 --- a/sdk/core/scheduler/timer.h +++ b/sdk/core/scheduler/timer.h
@@ -3,6 +3,7 @@ #pragma once +#include "common.h" #include "plic.h" #include "thread.h" #include <platform-timer.hh> @@ -23,6 +24,9 @@ { T::setnext(cycles) }; + { + T::next() + } -> std::same_as<uint64_t>; }; static_assert( @@ -106,6 +110,21 @@ } /** + * Ensure that a timer tick is scheduled for the current thread. + */ + static void ensure_tick() + { + auto *thread = Thread::current_get(); + Debug::Assert(thread != nullptr, + "Ensure tick called with no running thread"); + auto tickTime = thread->expiryTime + TIMERCYCLES_PER_TICK; + if (tickTime < TimerCore::next()) + { + setnext(tickTime); + } + } + + /** * Wake any threads that were sleeping until a timeout before the * current time. This also wakes yielded threads if there are no * runnable threads.
diff --git a/sdk/include/platform/generic-riscv/platform-timer.hh b/sdk/include/platform/generic-riscv/platform-timer.hh index 5f3e226..6fce600 100644 --- a/sdk/include/platform/generic-riscv/platform-timer.hh +++ b/sdk/include/platform/generic-riscv/platform-timer.hh
@@ -80,6 +80,18 @@ *pmtimercmphigh = nextTime >> 32; } + /** + * Returns the time at which the next timer is scheduled. + */ + static uint64_t next() + { + volatile uint32_t *pmtimercmphigh = pmtimercmp + 1; + uint64_t nextTimer = *pmtimercmphigh; + nextTimer <<= 32; + nextTimer |= *pmtimercmp; + return nextTimer; + } + static void clear() { volatile uint32_t *pmtimercmphigh = pmtimercmp + 1;