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;
