use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::fmt;
use std::fmt::Display;
use rand::RngExt as _;
use rand::SeedableRng;
use rand::distr::uniform::SampleUniform;
use rand_pcg::Pcg64Mcg;
use crate::config::SchedHeuristic;
use crate::detlog;
use crate::types::DetTid;
pub type Priority = u64;
const EAGER_IO_REPOLL_PRIORITY: Priority = Priority::MIN;
pub const FIRST_PRIORITY: Priority = EAGER_IO_REPOLL_PRIORITY + 1;
pub const LAST_PRIORITY: Priority = 10000;
pub const REPLAY_FOREGROUND_PRIORITY: Priority = FIRST_PRIORITY;
pub const REPLAY_DEFERRED_PRIORITY: Priority = LAST_PRIORITY - 1;
pub const DEFAULT_PRIORITY: Priority = 1000;
pub fn is_ordinary_priority(prio: Priority) -> bool {
(FIRST_PRIORITY..=LAST_PRIORITY).contains(&prio)
}
pub fn entropy_to_priority(entropy: u64) -> Priority {
let range = LAST_PRIORITY - FIRST_PRIORITY + 1;
let offset = entropy % range;
FIRST_PRIORITY + offset
}
pub const PLAIN_YIELDS_BEFORE_EPOCH: u32 = 1;
type RoundRobinTurn = i64;
#[derive(Debug, Copy, Clone)]
pub struct PrioritizedOrder {
priority: Priority,
turn: RoundRobinTurn,
}
impl Ord for PrioritizedOrder {
fn cmp(&self, other: &Self) -> Ordering {
self.priority
.cmp(&other.priority)
.then(self.turn.cmp(&other.turn))
}
}
impl PartialOrd for PrioritizedOrder {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for PrioritizedOrder {
fn eq(&self, other: &Self) -> bool {
self.cmp(other).is_eq()
}
}
impl Eq for PrioritizedOrder {}
impl fmt::Display for PrioritizedOrder {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "(p: {}, t: {})", self.priority, self.turn)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PollerRestore {
Restored,
NotBackedOff,
NotQueued,
}
const POLLING_UPGRADE_INTERVAL: u64 = 200;
#[derive(Debug, Copy, Clone)]
struct QueueValue {
tid: DetTid,
poll_upgrade: Option<Priority>,
deadline_restored: bool,
}
impl QueueValue {
fn counts_as_poller(&self, priority: Priority) -> bool {
self.is_fully_backed_off_poller(priority) || self.deadline_restored
}
fn is_fully_backed_off_poller(&self, priority: Priority) -> bool {
self.poll_upgrade.is_some() && priority >= LAST_PRIORITY
}
}
#[derive(Debug, Clone)]
pub(super) struct SuspendedRunQueueEntry {
key: PrioritizedOrder,
value: QueueValue,
persistent_priority: Priority,
}
#[derive(Debug, Clone)]
pub struct RunQueue {
queue: BTreeMap<PrioritizedOrder, QueueValue>,
last_back_turn: RoundRobinTurn,
last_front_turn: RoundRobinTurn,
tentative_selection: Option<DetTid>,
tentative_selection_is_exact: bool,
yielded_skip: Option<DetTid>,
yield_epoch: Option<BTreeSet<DetTid>>,
yield_streaks: BTreeMap<DetTid, u32>,
queued_by_yield: BTreeSet<DetTid>,
sched_strategy: SchedHeuristic,
prng: Pcg64Mcg,
sticky_random_param: f64,
sticky_random_selection: Option<DetTid>,
}
impl fmt::Display for RunQueue {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(
f,
"Run queue, size={}, last_back_turn={}, last_front_turn={}:",
self.queue.len(),
self.last_back_turn,
self.last_front_turn,
)?;
for x in self.queue.iter() {
writeln!(f, " {:.500?}", x)?;
}
Ok(())
}
}
impl RunQueue {
pub fn new(ss: SchedHeuristic, seed: u64, srp: f64) -> Self {
detlog!("SCHEDRAND: seeding scheduler runqueue with seed {}", seed);
Self {
queue: BTreeMap::new(),
last_back_turn: 0,
last_front_turn: 0,
sched_strategy: ss,
tentative_selection: None,
tentative_selection_is_exact: false,
yielded_skip: None,
yield_epoch: None,
yield_streaks: BTreeMap::new(),
queued_by_yield: BTreeSet::new(),
prng: Pcg64Mcg::seed_from_u64(seed),
sticky_random_param: srp,
sticky_random_selection: None,
}
}
fn push_safety_check(&self, tid: DetTid) {
if cfg!(debug_assertions) {
for qv in self.queue.values() {
if qv.tid == tid {
panic!(
"Invariant violation! Tried to add {} to runqueue, but it's already present:\n {:?}",
tid, self
);
}
}
}
}
pub fn has_runnable_besides(&self, exclude: DetTid) -> bool {
self.queue
.iter()
.any(|(k, v)| v.tid != exclude && !v.counts_as_poller(k.priority))
}
pub fn only_pollers(&self) -> bool {
self.queue
.iter()
.all(|(k, v)| v.counts_as_poller(k.priority))
}
pub fn only_pollers_or_yielders(&self) -> bool {
self.queue
.iter()
.all(|(k, v)| v.counts_as_poller(k.priority) || self.queued_by_yield.contains(&v.tid))
}
pub fn tentative_pop_in_progress(&self) -> bool {
self.tentative_selection.is_some()
}
pub fn push_back(&mut self, tid: DetTid, priority: Priority) -> PrioritizedOrder {
assert!(self.tentative_selection.is_none());
self.push_safety_check(tid);
if !is_ordinary_priority(priority) {
panic!("This is not an acceptable priority value: {}", priority);
}
self.push_back_inner(tid, priority, None)
}
pub fn push_yielded(&mut self, tid: DetTid, priority: Priority) -> PrioritizedOrder {
assert!(self.yielded_skip.is_none());
self.yielded_skip = Some(tid);
self.queued_by_yield.insert(tid);
self.push_back(tid, priority)
}
pub fn push_yielded_into_epoch(&mut self, tid: DetTid, priority: Priority) -> PrioritizedOrder {
let skipped_someone = self.queue.values().any(|value| value.tid != tid);
if skipped_someone {
let streak = self.yield_streaks.entry(tid).or_insert(0);
*streak += 1;
if *streak > PLAIN_YIELDS_BEFORE_EPOCH {
self.yield_epoch
.get_or_insert_with(BTreeSet::new)
.insert(tid);
}
}
self.queued_by_yield.insert(tid);
self.push_back(tid, priority)
}
pub fn push_poller(
&mut self,
tid: DetTid,
normal_priority: Priority,
poll_attempt: u32,
) -> PrioritizedOrder {
assert!(self.tentative_selection.is_none());
self.push_safety_check(tid);
let priority = 1u64
.checked_shl(poll_attempt)
.and_then(|f| f.checked_mul(normal_priority))
.unwrap_or(Priority::MAX)
.min(LAST_PRIORITY);
self.push_back_inner(tid, priority, Some(normal_priority))
}
fn push_back_inner(
&mut self,
tid: DetTid,
priority: Priority,
poll_upgrade: Option<Priority>,
) -> PrioritizedOrder {
self.last_back_turn += 1;
let turn = self.last_back_turn;
let prio = PrioritizedOrder { priority, turn };
self.push_inner(tid, prio, poll_upgrade)
}
pub fn push_front(&mut self, tid: DetTid, priority: Priority) -> PrioritizedOrder {
assert!(self.tentative_selection.is_none());
self.push_safety_check(tid);
assert!(is_ordinary_priority(priority));
self.push_front_inner(tid, priority, None)
}
pub fn push_eager_io_repoll(&mut self, tid: DetTid) -> PrioritizedOrder {
assert!(self.tentative_selection.is_none());
self.push_safety_check(tid);
let priority = EAGER_IO_REPOLL_PRIORITY;
self.push_front_inner(tid, priority, None)
}
fn push_front_inner(
&mut self,
tid: DetTid,
priority: Priority,
poll_upgrade: Option<Priority>,
) -> PrioritizedOrder {
self.last_front_turn -= 1;
let turn = self.last_front_turn;
let prio = PrioritizedOrder { priority, turn };
self.push_inner(tid, prio, poll_upgrade)
}
fn push_inner(
&mut self,
tid: DetTid,
prio: PrioritizedOrder,
poll_upgrade: Option<Priority>,
) -> PrioritizedOrder {
let qval = QueueValue {
tid,
poll_upgrade,
deadline_restored: false,
};
let old = self.queue.insert(prio, qval);
assert!(old.is_none()); self.check_poll_upgrade();
prio
}
pub fn is_empty(&self) -> bool {
self.queue.is_empty()
}
pub fn len(&self) -> usize {
self.queue.len()
}
pub fn tids(&self) -> impl Iterator<Item = &DetTid> {
self.queue.values().map(|v| &v.tid)
}
pub fn contains_tid(&self, tid: DetTid) -> bool {
self.tids().any(|t| t == &tid)
}
pub fn contains_non_polling_tid(&self, tid: DetTid) -> bool {
self.queue
.iter()
.any(|(_, v)| v.tid == tid && v.poll_upgrade.is_none() && !v.deadline_restored)
}
pub(super) fn suspend(
&mut self,
tid: DetTid,
persistent_priority: Priority,
) -> Option<SuspendedRunQueueEntry> {
assert!(self.tentative_selection.is_none());
let key = *self.queue.iter().find(|(_, v)| v.tid == tid)?.0;
let value = self.queue.remove(&key).expect("located queue entry");
Some(SuspendedRunQueueEntry {
key,
value,
persistent_priority,
})
}
pub(super) fn restore(
&mut self,
mut entry: SuspendedRunQueueEntry,
current_priority: Priority,
) {
assert!(self.tentative_selection.is_none());
assert!(!self.contains_tid(entry.value.tid));
if entry.persistent_priority != current_priority {
entry.key.priority = current_priority;
if entry.value.poll_upgrade.is_some() {
entry.value.poll_upgrade = Some(current_priority);
}
}
assert!(self.queue.insert(entry.key, entry.value).is_none());
}
pub fn remove_tid(&mut self, tid: DetTid) -> bool {
assert!(self.tentative_selection.is_none());
let mut kept_all = true;
self.queue.retain(|_k, v| {
let ret = v.tid != tid;
kept_all = kept_all && ret;
ret
});
if self.yielded_skip == Some(tid) {
self.yielded_skip = None;
}
if let Some(epoch) = &mut self.yield_epoch {
epoch.remove(&tid);
}
self.yield_streaks.remove(&tid);
self.queued_by_yield.remove(&tid);
if self.sticky_random_selection == Some(tid) {
self.sticky_random_selection = None;
}
!kept_all
}
fn random_range<T>(&mut self, start: T, end: T) -> T
where
T: SampleUniform + Display + PartialOrd + Copy,
{
let r = self.prng.random_range(start..end);
detlog!("SCHEDRAND: [{},{}) => {}", start, end, r);
r
}
pub fn tentative_pop_next(&mut self) -> Option<DetTid> {
assert!(!self.tentative_selection_is_exact);
let skip = self
.yielded_skip
.filter(|tid| self.queue.len() > 1 && self.contains_tid(*tid));
if self.yield_epoch.as_ref().is_some_and(|epoch| {
self.queue.iter().all(|(key, value)| {
epoch.contains(&value.tid) || value.is_fully_backed_off_poller(key.priority)
})
}) {
self.end_yield_epoch();
}
let mut excluded: BTreeSet<DetTid> = skip.into_iter().collect();
if let Some(epoch) = &self.yield_epoch {
let with_epoch: BTreeSet<DetTid> = excluded.union(epoch).copied().collect();
if self
.queue
.values()
.any(|value| !with_epoch.contains(&value.tid))
{
excluded = with_epoch;
}
}
let excluded_count = self
.queue
.values()
.filter(|value| excluded.contains(&value.tid))
.count();
self.tentative_selection = match self.sched_strategy {
SchedHeuristic::None | SchedHeuristic::ConnectBind => self
.queue
.values()
.find(|value| !excluded.contains(&value.tid))
.map(|value| value.tid),
SchedHeuristic::Random => {
if self.queue.is_empty() {
return None;
}
if self.tentative_selection.is_none() {
let eligible = self.queue.len() - excluded_count;
let random_idx = self.random_range(0, eligible);
self.tentative_selection = self
.queue
.values()
.filter(|value| !excluded.contains(&value.tid))
.nth(random_idx)
.map(|value| value.tid);
};
self.tentative_selection
}
SchedHeuristic::StickyRandom => {
if self.queue.is_empty() {
return None;
}
if self
.sticky_random_selection
.is_some_and(|tid| excluded.contains(&tid))
{
self.sticky_random_selection = None;
}
if self.sticky_random_selection.is_none()
|| !self.contains_tid(self.sticky_random_selection.unwrap())
{
let eligible = self.queue.len() - excluded_count;
let random_idx = self.random_range(0, eligible);
self.sticky_random_selection = self
.queue
.values()
.filter(|value| !excluded.contains(&value.tid))
.nth(random_idx)
.map(|value| value.tid);
}
self.sticky_random_selection
}
};
self.tentative_selection
}
pub fn tentative_pop_tid(&mut self, tid: DetTid) -> Option<DetTid> {
assert!(self.tentative_selection.is_none());
if self.contains_tid(tid) {
self.tentative_selection = Some(tid);
self.tentative_selection_is_exact = true;
}
self.tentative_selection
}
pub fn commit_tentative_pop(&mut self) -> DetTid {
self.commit_selection()
}
pub fn end_yield_epoch(&mut self) {
self.yield_epoch = None;
self.yield_streaks.clear();
}
pub fn commit_tentative_pop_yield(&mut self) -> DetTid {
let tid = self.commit_selection();
self.consume_yield_exclusion();
tid
}
fn commit_selection(&mut self) -> DetTid {
let tentative_selection = self
.tentative_selection
.take()
.expect("tentative_pop to already returned a `Some`");
let exact = std::mem::take(&mut self.tentative_selection_is_exact);
let ret = if exact {
let key = *self
.queue
.iter()
.find(|(_key, value)| value.tid == tentative_selection)
.map(|(key, _value)| key)
.unwrap();
self.queue.remove(&key).map(|value| value.tid)
} else {
match self.sched_strategy {
SchedHeuristic::None | SchedHeuristic::ConnectBind | SchedHeuristic::Random => {
let key = *self
.queue
.iter()
.find(|(_k, v)| v.tid == tentative_selection)
.map(|(k, _v)| k)
.unwrap();
self.queue.remove(&key).map(|v| v.tid)
}
SchedHeuristic::StickyRandom => {
let tid = self.sticky_random_selection.unwrap();
if self.random_range(0f64, 1f64) <= 1.0 - self.sticky_random_param {
self.sticky_random_selection = None;
}
let key = *self
.queue
.iter()
.find(|(_k, v)| v.tid == tid)
.map(|(k, _v)| k)
.unwrap();
self.queue.remove(&key).map(|v| v.tid)
}
}
}
.expect("to always return a DetTid");
debug_assert!(ret == tentative_selection);
self.queued_by_yield.remove(&ret);
ret
}
pub fn commit_tentative_pop_completed_turn(&mut self) -> DetTid {
let tid = self.commit_tentative_pop();
self.consume_yield_exclusion();
self.end_yield_epoch();
tid
}
pub fn consume_yield_exclusion(&mut self) {
self.yielded_skip = None;
}
pub fn undo_tentative_pop(&mut self) {
assert!(self.tentative_selection.is_some());
self.tentative_selection = None;
self.tentative_selection_is_exact = false;
}
fn turn_counter(&self) -> u64 {
debug_assert!(self.last_back_turn >= 0);
debug_assert!(self.last_front_turn <= 0);
self.last_back_turn as u64 + self.last_front_turn.unsigned_abs()
}
fn check_poll_upgrade(&mut self) {
if self.turn_counter().is_multiple_of(POLLING_UPGRADE_INTERVAL) {
self.do_poll_upgrade()
}
}
pub fn is_priority_ordered(&self) -> bool {
self.sched_strategy.is_priority_ordered()
}
#[cfg(test)]
pub fn queued_priority(&self, tid: DetTid) -> Option<Priority> {
self.queue
.iter()
.find(|(_, value)| value.tid == tid)
.map(|(key, _)| key.priority)
}
pub fn restore_poller_priority(&mut self, tid: DetTid) -> PollerRestore {
assert!(self.tentative_selection.is_none());
let Some((&key, value)) = self.queue.iter().find(|(_, value)| value.tid == tid) else {
return PollerRestore::NotQueued;
};
let Some(normal_priority) = value.poll_upgrade else {
return PollerRestore::NotBackedOff;
};
let mut value = self.queue.remove(&key).expect("located queue entry");
value.poll_upgrade = None;
value.deadline_restored = key.priority >= LAST_PRIORITY;
self.last_back_turn += 1;
let restored = PrioritizedOrder {
priority: normal_priority,
turn: self.last_back_turn,
};
assert!(self.queue.insert(restored, value).is_none());
self.check_poll_upgrade();
PollerRestore::Restored
}
#[cold]
fn do_poll_upgrade(&mut self) {
let upgrades = self
.queue
.iter()
.filter_map(|(k, v)| v.poll_upgrade.map(|upgd| (*k, upgd)))
.collect::<Vec<(PrioritizedOrder, Priority)>>();
for (key, upgrade_prio) in upgrades {
if upgrade_prio >= LAST_PRIORITY {
continue;
}
let mut new_key = key;
new_key.priority = upgrade_prio;
let mut qval = self.queue.remove(&key).unwrap();
qval.poll_upgrade = None; let old = self.queue.insert(new_key, qval);
assert!(old.is_none()); }
for (key, value) in self.queue.iter_mut() {
if key.priority < LAST_PRIORITY {
value.deadline_restored = false;
}
}
}
}
impl Default for RunQueue {
fn default() -> Self {
Self::new(SchedHeuristic::None, 0, 0.0)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn restore_poller_priority_moves_one_poller_to_the_back_of_its_level() {
let poller = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
let spinner = DetTid::from_raw(3);
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_poller(poller, DEFAULT_PRIORITY, 3);
queue.push_poller(other, DEFAULT_PRIORITY, 3);
queue.push_back(spinner, DEFAULT_PRIORITY);
let pushes = queue.turn_counter();
assert_eq!(queue.tentative_pop_next(), Some(spinner));
queue.undo_tentative_pop();
assert_eq!(
queue.restore_poller_priority(poller),
PollerRestore::Restored
);
assert_eq!(queue.turn_counter(), pushes + 1, "a restore is one push");
assert_eq!(queue.queued_priority(poller), Some(DEFAULT_PRIORITY));
assert_eq!(queue.tentative_pop_next(), Some(spinner), "queued first");
assert_eq!(queue.commit_tentative_pop(), spinner);
queue.push_back(spinner, DEFAULT_PRIORITY);
assert_eq!(
queue.tentative_pop_next(),
Some(poller),
"ahead of the requeue"
);
queue.undo_tentative_pop();
let (other_key, other_value) = queue
.queue
.iter()
.find(|(_, value)| value.tid == other)
.unwrap();
assert_eq!(other_key.priority, 8 * DEFAULT_PRIORITY);
assert_eq!(other_value.poll_upgrade, Some(DEFAULT_PRIORITY));
assert_eq!(
queue.restore_poller_priority(poller),
PollerRestore::NotBackedOff
);
assert_eq!(
queue.restore_poller_priority(spinner),
PollerRestore::NotBackedOff
);
assert_eq!(
queue.restore_poller_priority(DetTid::from_raw(9)),
PollerRestore::NotQueued
);
}
#[test]
fn an_ordinary_thread_in_the_last_band_is_not_a_poller() {
let worker = DetTid::from_raw(1);
let poller = DetTid::from_raw(2);
let other = DetTid::from_raw(3);
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_back(worker, LAST_PRIORITY);
assert!(!queue.only_pollers());
assert!(!queue.only_pollers_or_yielders());
assert!(queue.has_runnable_besides(other));
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_poller(poller, DEFAULT_PRIORITY, u32::MAX);
assert!(
queue.only_pollers(),
"a fully backed-off poller is a poller"
);
assert!(!queue.has_runnable_besides(other));
queue.push_back(worker, LAST_PRIORITY);
assert!(
!queue.only_pollers(),
"the ordinary thread beside it is work"
);
assert!(queue.has_runnable_besides(poller));
}
#[test]
fn a_deadline_restored_poller_counts_as_a_poller_until_it_runs() {
let poller = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_poller(poller, DEFAULT_PRIORITY, 30);
assert!(queue.only_pollers());
assert_eq!(
queue.restore_poller_priority(poller),
PollerRestore::Restored
);
assert!(queue.only_pollers(), "restored, but it has not run");
assert!(!queue.has_runnable_besides(other));
assert_eq!(queue.tentative_pop_next(), Some(poller));
assert_eq!(queue.commit_tentative_pop(), poller);
queue.push_back(poller, DEFAULT_PRIORITY);
assert!(!queue.only_pollers(), "after its turn it is ordinary work");
assert!(queue.has_runnable_besides(other));
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_poller(poller, DEFAULT_PRIORITY, 1);
assert!(
!queue.only_pollers(),
"at 2000 it is ordinary work, as on main"
);
assert_eq!(
queue.restore_poller_priority(poller),
PollerRestore::Restored
);
assert!(!queue.only_pollers(), "and stays so after the restore");
assert!(queue.has_runnable_besides(other));
}
#[test]
fn a_poll_upgrade_ends_a_restored_pollers_poller_status() {
let poller = DetTid::from_raw(1);
let mut queue = RunQueue::new(SchedHeuristic::None, 0, 0.0);
queue.push_poller(poller, DEFAULT_PRIORITY, 30);
assert_eq!(
queue.restore_poller_priority(poller),
PollerRestore::Restored
);
assert!(queue.only_pollers());
queue.do_poll_upgrade();
assert!(
!queue.only_pollers(),
"upgraded like every backed-off poller"
);
}
#[test]
fn a_last_band_pollers_upgrade_keeps_it_a_poller() {
let poller = DetTid::from_raw(1);
let mut queue = RunQueue::default();
queue.push_poller(poller, LAST_PRIORITY, 0);
assert!(queue.only_pollers());
queue.do_poll_upgrade();
assert!(
queue.only_pollers(),
"an upgrade to the same band is a no-op"
);
assert_eq!(queue.queued_priority(poller), Some(LAST_PRIORITY));
let restored = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_poller(restored, LAST_PRIORITY, 3);
assert_eq!(
queue.restore_poller_priority(restored),
PollerRestore::Restored
);
queue.do_poll_upgrade();
assert!(
queue.only_pollers(),
"so is one its deadline restored there"
);
let count = POLLING_UPGRADE_INTERVAL as i32;
let mut queue = RunQueue::default();
for raw in 1..=count {
queue.push_poller(DetTid::from_raw(raw), LAST_PRIORITY, 0);
}
for cycle in 0..20 * count {
assert!(queue.only_pollers(), "cycle {cycle}");
let tid = queue.tentative_pop_next().expect("a queued poller");
assert_eq!(queue.commit_tentative_pop(), tid);
queue.push_poller(tid, LAST_PRIORITY, 1);
}
assert!(queue.only_pollers());
}
#[test]
fn a_chaos_yield_marks_its_thread_as_a_yielder() {
let yielder = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, LAST_PRIORITY);
yield_turn(&mut queue, yielder, LAST_PRIORITY);
assert!(!queue.only_pollers(), "a yielder is not a poller");
assert!(queue.only_pollers_or_yielders());
queue.push_back(other, DEFAULT_PRIORITY);
assert!(!queue.only_pollers_or_yielders());
assert!(queue.remove_tid(other));
assert_eq!(take_turn(&mut queue), yielder);
queue.push_back(yielder, LAST_PRIORITY);
assert!(!queue.only_pollers_or_yielders(), "it ran without yielding");
}
#[test]
fn only_first_entry_heuristics_are_priority_ordered() {
for (strategy, ordered) in [
(SchedHeuristic::None, true),
(SchedHeuristic::ConnectBind, true),
(SchedHeuristic::Random, false),
(SchedHeuristic::StickyRandom, false),
] {
assert_eq!(
RunQueue::new(strategy, 0, 0.5).is_priority_ordered(),
ordered,
"{strategy:?}"
);
}
}
#[test]
fn transport_suspend_restore_preserves_all_queue_state() {
for strategy in [
SchedHeuristic::None,
SchedHeuristic::Random,
SchedHeuristic::StickyRandom,
] {
let tid = DetTid::from_raw(1);
let peer = DetTid::from_raw(2);
let mut queue = RunQueue::new(strategy, 391, 0.5);
queue.push_yielded(tid, DEFAULT_PRIORITY);
queue.push_back(peer, DEFAULT_PRIORITY);
let key = *queue
.queue
.iter()
.find(|(_, value)| value.tid == tid)
.unwrap()
.0;
queue.queue.get_mut(&key).unwrap().poll_upgrade = Some(DEFAULT_PRIORITY);
queue.sticky_random_selection = Some(tid);
let before = format!("{queue:?}");
let saved = queue.suspend(tid, DEFAULT_PRIORITY).unwrap();
assert_eq!(queue.yielded_skip, Some(tid));
assert_eq!(queue.sticky_random_selection, Some(tid));
queue.restore(saved, DEFAULT_PRIORITY);
assert_eq!(format!("{queue:?}"), before, "{strategy:?}");
}
}
#[test]
fn observation_restore_keeps_real_selection_progress_and_new_priority() {
for strategy in [
SchedHeuristic::None,
SchedHeuristic::Random,
SchedHeuristic::StickyRandom,
] {
let tid = DetTid::from_raw(1);
let peer = DetTid::from_raw(2);
let mut queue = RunQueue::new(strategy, 391, 0.5);
queue.push_yielded(tid, DEFAULT_PRIORITY);
queue.push_back(peer, DEFAULT_PRIORITY);
let key = *queue
.queue
.iter()
.find(|(_, value)| value.tid == tid)
.unwrap()
.0;
queue.queue.get_mut(&key).unwrap().poll_upgrade = Some(DEFAULT_PRIORITY);
let saved = queue.suspend(tid, DEFAULT_PRIORITY).unwrap();
assert_eq!(queue.tentative_pop_next(), Some(peer));
assert_eq!(queue.commit_tentative_pop_completed_turn(), peer);
assert_eq!(queue.yielded_skip, None);
queue.push_back(peer, DEFAULT_PRIORITY);
let random_after_turn = format!("{:?}", queue.prng);
let sticky_after_turn = queue.sticky_random_selection;
let turns_after_turn = (queue.last_back_turn, queue.last_front_turn);
queue.restore(saved, DEFAULT_PRIORITY + 3);
let (restored, value) = queue
.queue
.iter()
.find(|(_, value)| value.tid == tid)
.unwrap();
assert_eq!(restored.turn, key.turn);
assert_eq!(restored.priority, DEFAULT_PRIORITY + 3);
assert_eq!(value.poll_upgrade, Some(DEFAULT_PRIORITY + 3));
assert_eq!(queue.yielded_skip, None);
assert_eq!(queue.sticky_random_selection, sticky_after_turn);
assert_eq!(
(queue.last_back_turn, queue.last_front_turn),
turns_after_turn
);
assert_eq!(format!("{:?}", queue.prng), random_after_turn);
}
}
#[test]
fn yielded_thread_cedes_exactly_one_turn_under_every_heuristic() {
for strategy in [
SchedHeuristic::None,
SchedHeuristic::ConnectBind,
SchedHeuristic::Random,
SchedHeuristic::StickyRandom,
] {
let yielding = DetTid::from_raw(1);
let peer = DetTid::from_raw(2);
let mut queue = RunQueue::new(strategy, 0, 1.0);
queue.push_back(yielding, DEFAULT_PRIORITY - 1);
assert_eq!(queue.tentative_pop_next(), Some(yielding));
assert_eq!(queue.commit_tentative_pop(), yielding);
queue.push_yielded(yielding, DEFAULT_PRIORITY - 1);
queue.push_back(peer, LAST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(peer), "{strategy:?}");
assert_eq!(
queue.commit_tentative_pop_completed_turn(),
peer,
"{strategy:?}"
);
assert_eq!(queue.yielded_skip, None, "{strategy:?}");
let restored_priority = queue
.queue
.iter()
.find(|(_key, value)| value.tid == yielding)
.map(|(key, _value)| key.priority);
assert_eq!(
restored_priority,
Some(DEFAULT_PRIORITY - 1),
"{strategy:?}"
);
if matches!(strategy, SchedHeuristic::None | SchedHeuristic::ConnectBind) {
queue.push_back(peer, LAST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(yielding), "{strategy:?}");
}
}
}
#[test]
fn exact_selection_bypasses_priority_and_heuristic() {
for strategy in [
SchedHeuristic::None,
SchedHeuristic::ConnectBind,
SchedHeuristic::Random,
SchedHeuristic::StickyRandom,
] {
let higher_priority = DetTid::from_raw(1);
let selected = DetTid::from_raw(2);
let mut queue = RunQueue::new(strategy, 0, 1.0);
queue.push_back(higher_priority, FIRST_PRIORITY);
queue.push_back(selected, LAST_PRIORITY);
assert_eq!(queue.tentative_pop_tid(selected), Some(selected));
assert_eq!(queue.commit_tentative_pop(), selected);
assert!(queue.contains_tid(higher_priority));
assert!(!queue.contains_tid(selected));
}
}
#[test]
fn scheduler_only_commit_does_not_consume_yield_exclusion() {
let yielding = DetTid::from_raw(1);
let peer = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielding, DEFAULT_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(yielding));
assert_eq!(queue.commit_tentative_pop(), yielding);
queue.push_yielded(yielding, DEFAULT_PRIORITY);
queue.push_back(peer, DEFAULT_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(peer));
assert_eq!(queue.commit_tentative_pop(), peer);
queue.push_back(peer, DEFAULT_PRIORITY);
assert_eq!(queue.yielded_skip, Some(yielding));
assert_eq!(queue.tentative_pop_next(), Some(peer));
assert_eq!(queue.commit_tentative_pop_completed_turn(), peer);
assert_eq!(queue.yielded_skip, None);
}
fn take_turn(queue: &mut RunQueue) -> DetTid {
queue.tentative_pop_next().expect("a runnable thread");
queue.commit_tentative_pop_completed_turn()
}
fn yield_turn(queue: &mut RunQueue, tid: DetTid, priority: Priority) {
assert_eq!(queue.tentative_pop_tid(tid), Some(tid));
assert_eq!(queue.commit_tentative_pop_yield(), tid);
queue.push_yielded_into_epoch(tid, priority);
}
fn yield_into_epoch(queue: &mut RunQueue, tid: DetTid, priority: Priority) {
for _ in 0..=PLAIN_YIELDS_BEFORE_EPOCH {
yield_turn(queue, tid, priority);
}
assert!(
queue
.yield_epoch
.as_ref()
.is_some_and(|epoch| epoch.contains(&tid))
);
}
#[test]
fn a_yielder_is_reselected_once_before_it_joins_the_epoch() {
let yielder = DetTid::from_raw(1);
let awaited = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
queue.push_back(awaited, LAST_PRIORITY);
yield_turn(&mut queue, yielder, FIRST_PRIORITY);
assert_eq!(queue.yield_epoch, None);
assert_eq!(queue.tentative_pop_next(), Some(yielder));
queue.undo_tentative_pop();
yield_turn(&mut queue, yielder, FIRST_PRIORITY);
assert_eq!(take_turn(&mut queue), awaited);
assert!(queue.yield_streaks.is_empty());
}
#[test]
fn consecutive_lone_yields_build_no_streak() {
let spinner = DetTid::from_raw(1);
let woken = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(spinner, FIRST_PRIORITY);
for _ in 0..5 {
yield_turn(&mut queue, spinner, FIRST_PRIORITY);
}
assert!(queue.yield_streaks.is_empty());
assert_eq!(queue.yield_epoch, None);
queue.push_back(woken, LAST_PRIORITY);
yield_turn(&mut queue, spinner, FIRST_PRIORITY);
assert_eq!(queue.yield_epoch, None);
assert_eq!(queue.tentative_pop_next(), Some(spinner));
}
#[test]
fn the_last_thread_outside_an_epoch_joins_it_by_yielding() {
let first = DetTid::from_raw(1);
let last = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(first, FIRST_PRIORITY);
queue.push_back(last, LAST_PRIORITY);
yield_into_epoch(&mut queue, first, FIRST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(last));
queue.undo_tentative_pop();
yield_into_epoch(&mut queue, last, LAST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(first));
assert_eq!(queue.yield_epoch, None);
}
#[test]
fn two_yielders_cannot_shut_out_a_thread_in_a_later_band() {
let first = DetTid::from_raw(1);
let second = DetTid::from_raw(2);
let awaited = DetTid::from_raw(3);
let mut queue = RunQueue::default();
queue.push_back(first, FIRST_PRIORITY);
queue.push_back(second, FIRST_PRIORITY + 1);
queue.push_back(awaited, LAST_PRIORITY);
yield_into_epoch(&mut queue, first, FIRST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(second));
queue.undo_tentative_pop();
yield_into_epoch(&mut queue, second, FIRST_PRIORITY + 1);
assert_eq!(take_turn(&mut queue), awaited);
}
#[test]
fn a_turn_by_a_thread_that_did_not_yield_ends_the_yield_epoch() {
let yielder = DetTid::from_raw(1);
let early = DetTid::from_raw(2);
let late = DetTid::from_raw(3);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY + 1);
queue.push_back(early, FIRST_PRIORITY);
queue.push_back(late, LAST_PRIORITY);
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY + 1);
assert_eq!(take_turn(&mut queue), early);
assert_eq!(queue.yield_epoch, None);
queue.push_back(early, FIRST_PRIORITY);
assert_eq!(take_turn(&mut queue), early);
queue.push_back(early, FIRST_PRIORITY);
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY + 1);
queue.tentative_pop_next();
assert_eq!(queue.commit_tentative_pop(), early);
queue.push_back(early, FIRST_PRIORITY);
assert!(
queue
.yield_epoch
.as_ref()
.is_some_and(|epoch| epoch.contains(&yielder))
);
queue.end_yield_epoch();
assert_eq!(queue.yield_epoch, None);
assert!(queue.yield_streaks.is_empty());
assert_eq!(
queue.tids().copied().collect::<Vec<_>>(),
[early, yielder, late]
);
}
#[test]
fn a_yield_epoch_covering_every_queued_thread_ends() {
let first = DetTid::from_raw(1);
let second = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(first, FIRST_PRIORITY);
queue.push_back(second, LAST_PRIORITY);
yield_into_epoch(&mut queue, first, FIRST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(second));
queue.undo_tentative_pop();
yield_into_epoch(&mut queue, second, LAST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(first));
assert_eq!(queue.yield_epoch, None);
queue.undo_tentative_pop();
yield_into_epoch(&mut queue, first, FIRST_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(second));
}
#[test]
fn a_yield_epoch_keeps_the_yielders_band_and_poller_status() {
let yielder = DetTid::from_raw(1);
let awaited = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
queue.push_back(awaited, LAST_PRIORITY);
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY);
assert!(!queue.only_pollers());
assert!(queue.has_runnable_besides(awaited));
assert_eq!(
queue.tids().copied().collect::<Vec<_>>(),
[yielder, awaited]
);
assert_eq!(take_turn(&mut queue), awaited);
}
#[test]
fn leaving_the_queue_leaves_the_yield_epoch() {
let yielder = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
queue.push_back(other, LAST_PRIORITY);
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY);
assert!(queue.remove_tid(yielder));
queue.push_front(yielder, FIRST_PRIORITY);
assert_eq!(take_turn(&mut queue), yielder);
}
#[test]
fn only_a_fully_backed_off_poller_releases_a_yield_epoch() {
let yielder = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
for poller in [false, true] {
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
if poller {
queue.push_poller(other, DEFAULT_PRIORITY, 20);
} else {
queue.push_back(other, LAST_PRIORITY);
}
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY);
let expected = if poller { yielder } else { other };
assert_eq!(
queue.tentative_pop_next(),
Some(expected),
"poller={poller}"
);
}
}
#[test]
fn leaving_the_queue_resets_the_yield_streak() {
let yielder = DetTid::from_raw(1);
let other = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
queue.push_back(other, LAST_PRIORITY);
yield_turn(&mut queue, yielder, FIRST_PRIORITY);
assert!(queue.remove_tid(yielder));
queue.push_front(yielder, FIRST_PRIORITY);
yield_turn(&mut queue, yielder, FIRST_PRIORITY);
assert_eq!(queue.yield_epoch, None);
assert_eq!(queue.tentative_pop_next(), Some(yielder));
}
#[test]
fn a_one_turn_skip_and_a_yield_epoch_never_exclude_everyone() {
let yielder = DetTid::from_raw(1);
let poller = DetTid::from_raw(2);
let mut queue = RunQueue::default();
queue.push_back(yielder, FIRST_PRIORITY);
queue.push_back(poller, DEFAULT_PRIORITY);
yield_into_epoch(&mut queue, yielder, FIRST_PRIORITY);
assert_eq!(queue.tentative_pop_tid(poller), Some(poller));
assert_eq!(queue.commit_tentative_pop_yield(), poller);
queue.push_yielded(poller, DEFAULT_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(yielder));
}
#[test]
fn a_lone_yielder_runs_again() {
let yielder = DetTid::from_raw(1);
let mut queue = RunQueue::default();
queue.push_back(yielder, DEFAULT_PRIORITY);
yield_turn(&mut queue, yielder, DEFAULT_PRIORITY);
assert_eq!(take_turn(&mut queue), yielder);
assert_eq!(queue.yield_epoch, None);
assert!(queue.yield_streaks.is_empty());
}
#[test]
fn a_yield_epoch_holds_under_the_random_heuristics() {
for strategy in [SchedHeuristic::Random, SchedHeuristic::StickyRandom] {
for seed in 0..16 {
let yielders = [DetTid::from_raw(1), DetTid::from_raw(2)];
let awaited = DetTid::from_raw(3);
let mut queue = RunQueue::new(strategy, seed, 1.0);
for tid in [yielders[0], yielders[1], awaited] {
queue.push_back(tid, DEFAULT_PRIORITY);
}
for tid in yielders {
yield_into_epoch(&mut queue, tid, DEFAULT_PRIORITY);
}
assert_eq!(take_turn(&mut queue), awaited, "{strategy:?} seed {seed}");
}
}
}
#[test]
fn threads_queued_by_a_yield_are_not_work_a_background_call_waits_behind() {
let first = DetTid::from_raw(1);
let second = DetTid::from_raw(2);
let worker = DetTid::from_raw(3);
let mut queue = RunQueue::default();
queue.push_back(first, DEFAULT_PRIORITY);
queue.push_back(second, DEFAULT_PRIORITY);
assert!(!queue.only_pollers_or_yielders());
assert_eq!(queue.tentative_pop_next(), Some(first));
assert_eq!(queue.commit_tentative_pop_completed_turn(), first);
queue.push_yielded(first, DEFAULT_PRIORITY);
assert!(
!queue.only_pollers_or_yielders(),
"second has not yielded yet"
);
assert_eq!(queue.tentative_pop_next(), Some(second));
assert_eq!(queue.commit_tentative_pop_completed_turn(), second);
queue.push_yielded(second, DEFAULT_PRIORITY);
assert_eq!(queue.yielded_skip, Some(second));
assert!(!queue.only_pollers());
assert!(queue.only_pollers_or_yielders());
queue.push_back(worker, DEFAULT_PRIORITY);
assert!(!queue.only_pollers_or_yielders());
assert!(queue.remove_tid(worker));
assert!(queue.only_pollers_or_yielders());
assert_eq!(queue.tentative_pop_next(), Some(first));
assert_eq!(queue.commit_tentative_pop_completed_turn(), first);
queue.push_back(first, DEFAULT_PRIORITY);
assert!(!queue.only_pollers_or_yielders());
}
#[test]
fn tentative_pop_in_progress_tracks_the_transaction() {
let a = DetTid::from_raw(1);
let b = DetTid::from_raw(2);
let mut queue = RunQueue::default();
assert!(!queue.tentative_pop_in_progress());
queue.push_back(a, DEFAULT_PRIORITY);
queue.push_back(b, DEFAULT_PRIORITY);
assert!(!queue.tentative_pop_in_progress());
assert_eq!(queue.tentative_pop_next(), Some(a));
assert!(queue.tentative_pop_in_progress());
assert_eq!(queue.commit_tentative_pop(), a);
assert!(!queue.tentative_pop_in_progress());
assert_eq!(queue.tentative_pop_tid(b), Some(b));
assert!(queue.tentative_pop_in_progress());
queue.undo_tentative_pop();
assert!(!queue.tentative_pop_in_progress());
}
#[test]
fn removal_clears_per_incarnation_selection_state_before_tid_reuse() {
let tid = DetTid::from_raw(7);
let mut queue = RunQueue::new(SchedHeuristic::StickyRandom, 0x5107, 1.0);
queue.push_back(tid, DEFAULT_PRIORITY);
assert_eq!(queue.tentative_pop_next(), Some(tid));
queue.undo_tentative_pop();
assert_eq!(queue.sticky_random_selection, Some(tid));
queue.yielded_skip = Some(tid);
assert!(queue.remove_tid(tid));
assert_eq!(queue.sticky_random_selection, None);
assert_eq!(queue.yielded_skip, None);
queue.push_back(tid, DEFAULT_PRIORITY);
assert_eq!(queue.sticky_random_selection, None);
assert_eq!(queue.yielded_skip, None);
}
}