use crate::runtime::sync::sync::atomic::{AtomicU64, AtomicU8, Ordering};
use crate::runtime::sync::sync::Arc;
use tokio::sync::Notify;
use tokio_util::sync::CancellationToken;
use crate::transfer::{BoxTransfer, Transfer, TransferId};
pub(super) mod claim {
use crate::runtime::sync::sync::atomic::{AtomicBool, Ordering};
pub(in crate::scheduler) struct ClaimState {
claimed: AtomicBool,
wake_requested: AtomicBool,
}
impl ClaimState {
pub(in crate::scheduler) fn new() -> Self {
Self {
claimed: AtomicBool::new(false),
wake_requested: AtomicBool::new(false),
}
}
pub(in crate::scheduler) fn try_claim(&self) -> bool {
self.claimed
.compare_exchange(false, true, Ordering::SeqCst, Ordering::SeqCst)
.is_ok()
}
pub(in crate::scheduler) fn release_claim(&self) {
self.claimed.store(false, Ordering::SeqCst);
}
pub(in crate::scheduler) fn mark_wake_requested(&self) {
self.wake_requested.store(true, Ordering::SeqCst);
}
pub(in crate::scheduler) fn take_wake_requested(&self) -> bool {
self.wake_requested.swap(false, Ordering::SeqCst)
}
}
}
use claim::ClaimState;
const DEFAULT_PRIORITY: u8 = 128;
pub(super) const IO_WORK_COST: u64 = 128;
pub(super) const SPAWN_WORK_COST: u64 = IO_WORK_COST / 2;
pub(super) const PRIORITY_SCALE: u64 = 256;
pub(super) fn vruntime_delta_for_priority(priority: u8) -> u64 {
vruntime_delta_for_cost(IO_WORK_COST, priority)
}
pub(super) fn vruntime_delta_for_cost(cost: u64, priority: u8) -> u64 {
(cost * PRIORITY_SCALE) / (priority as u64).max(1)
}
#[derive(Clone)]
pub(crate) struct TransferDescriptor(std::sync::Arc<Inner>);
pub(crate) struct WeakTransferDescriptor(std::sync::Weak<Inner>);
impl WeakTransferDescriptor {
pub(crate) fn upgrade(&self) -> Option<TransferDescriptor> {
self.0.upgrade().map(TransferDescriptor)
}
}
struct Inner {
priority: AtomicU8,
vruntime: AtomicU64,
group_vruntime: Arc<AtomicU64>,
queued_executing: QueuedExecuting,
transfer: BoxTransfer,
idle_notify: Notify,
claim_state: ClaimState,
cancellation_token: CancellationToken,
}
impl std::fmt::Debug for TransferDescriptor {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("TransferDescriptor")
.field("tid", &self.0.transfer.ctx().id)
.field("priority", &self.priority())
.field("vruntime", &self.vruntime())
.finish_non_exhaustive()
}
}
impl TransferDescriptor {
#[cfg(test)]
pub(crate) fn new(transfer: BoxTransfer) -> Self {
Self::new_with_vruntime(transfer, 0, Arc::new(AtomicU64::new(0)))
}
pub(crate) fn new_with_vruntime(
transfer: BoxTransfer,
initial_vruntime: u64,
group_vruntime: Arc<AtomicU64>,
) -> Self {
Self(std::sync::Arc::new(Inner {
priority: AtomicU8::new(DEFAULT_PRIORITY),
vruntime: AtomicU64::new(initial_vruntime),
group_vruntime,
queued_executing: QueuedExecuting::new(),
transfer,
idle_notify: Notify::new(),
claim_state: ClaimState::new(),
cancellation_token: CancellationToken::new(),
}))
}
pub(super) fn try_claim(&self) -> bool {
self.0.claim_state.try_claim()
}
pub(super) fn release_claim(&self) {
self.0.claim_state.release_claim()
}
pub(super) fn record_wake_request(&self) {
self.0.claim_state.mark_wake_requested();
self.transfer().ctx().record_wake();
}
pub(super) fn clear_wake_request(&self) {
self.0.claim_state.take_wake_requested();
}
pub(super) fn reconcile_pending_wake(&self) -> bool {
if !self.0.claim_state.take_wake_requested() {
return false;
}
self.transfer().ctx().record_wake();
true
}
pub(crate) fn downgrade(&self) -> WeakTransferDescriptor {
WeakTransferDescriptor(std::sync::Arc::downgrade(&self.0))
}
pub(crate) fn transfer(&self) -> &dyn Transfer {
self.0.transfer.as_ref()
}
pub(crate) fn cancellation_token(&self) -> &CancellationToken {
&self.0.cancellation_token
}
pub(crate) fn id(&self) -> TransferId {
self.0.transfer.ctx().id
}
pub(crate) fn priority(&self) -> u8 {
self.0.priority.load(Ordering::Acquire)
}
pub(crate) fn set_priority(&self, priority: u8) {
self.0.priority.store(priority, Ordering::Release);
}
pub(super) fn group_vruntime_arc(&self) -> Arc<AtomicU64> {
Arc::clone(&self.0.group_vruntime)
}
pub(crate) fn vruntime(&self) -> u64 {
self.0.vruntime.load(Ordering::Acquire)
}
#[cfg(test)]
pub(crate) fn set_vruntime(&self, vruntime: u64) {
self.0.vruntime.store(vruntime, Ordering::Release);
}
fn add_vruntime(&self, delta: u64) {
self.0.vruntime.fetch_add(delta, Ordering::AcqRel);
self.0.group_vruntime.fetch_add(delta, Ordering::SeqCst);
}
pub(crate) fn work_generated(&self) {
let delta = vruntime_delta_for_priority(self.priority());
self.add_vruntime(delta);
}
pub(crate) fn work_generated_spawn(&self) {
let delta = vruntime_delta_for_cost(SPAWN_WORK_COST, self.priority());
self.add_vruntime(delta);
}
pub(crate) fn work_queued(&self) {
self.0.queued_executing.increment_queued();
}
pub(crate) fn work_started(&self) {
self.0.queued_executing.start_executing();
}
pub(crate) fn work_finished(&self) -> bool {
self.0.queued_executing.finish_executing()
}
pub(crate) fn work_purged(&self, count: usize) {
self.0.queued_executing.decrement_queued(count as u32);
}
pub(crate) fn is_idle(&self) -> bool {
self.0.queued_executing.is_idle()
}
pub(crate) fn notify_idle(&self) {
self.0.idle_notify.notify_waiters();
}
pub(crate) fn is_terminal(&self) -> bool {
!self.0.transfer.ctx().is_active()
}
pub(crate) async fn wait_for_idle(&self) {
loop {
let notified = self.0.idle_notify.notified();
if self.is_idle() {
return;
}
notified.await;
}
}
}
#[derive(Debug, Default)]
struct QueuedExecuting(AtomicU64);
impl QueuedExecuting {
const QUEUED_ONE: u64 = 1 << 32;
const EXECUTING_ONE: u64 = 1;
const QUEUED_TO_EXECUTING: u64 = Self::EXECUTING_ONE.wrapping_sub(Self::QUEUED_ONE);
fn new() -> Self {
Self(AtomicU64::new(0))
}
fn increment_queued(&self) {
let prev = self.0.fetch_add(Self::QUEUED_ONE, Ordering::AcqRel);
debug_assert!((prev >> 32) < u32::MAX as u64, "queued overflow");
}
fn decrement_queued(&self, count: u32) {
let delta = (count as u64) << 32;
let prev = self.0.fetch_sub(delta, Ordering::AcqRel);
debug_assert!((prev >> 32) >= count as u64, "queued underflow");
}
fn start_executing(&self) {
let prev = self
.0
.fetch_add(Self::QUEUED_TO_EXECUTING, Ordering::AcqRel);
debug_assert!((prev >> 32) > 0, "queued underflow in start_executing");
}
fn finish_executing(&self) -> bool {
let prev = self.0.fetch_sub(Self::EXECUTING_ONE, Ordering::AcqRel);
debug_assert!((prev as u32) > 0, "executing underflow");
prev == Self::EXECUTING_ONE
}
fn is_idle(&self) -> bool {
self.0.load(Ordering::Acquire) == 0
}
#[cfg(test)]
fn get(&self) -> (u32, u32) {
let val = self.0.load(Ordering::Acquire);
((val >> 32) as u32, val as u32)
}
#[cfg(test)]
fn outstanding(&self) -> u64 {
let (q, e) = self.get();
q as u64 + e as u64
}
}
pub(super) struct ClaimGuard<'a> {
desc: &'a TransferDescriptor,
released: bool,
}
impl<'a> ClaimGuard<'a> {
pub(super) fn new(desc: &'a TransferDescriptor) -> Self {
Self {
desc,
released: false,
}
}
pub(super) fn release(mut self) {
self.desc.release_claim();
self.released = true;
}
pub(super) fn hold(mut self) {
self.released = true;
}
}
impl Drop for ClaimGuard<'_> {
fn drop(&mut self) {
if !self.released {
self.desc.release_claim();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
mod queued_executing {
use super::*;
#[test]
fn test_new_is_idle() {
let qe = QueuedExecuting::new();
assert!(qe.is_idle());
assert_eq!(qe.get(), (0, 0));
assert_eq!(qe.outstanding(), 0);
}
#[test]
fn test_increment_queued() {
let qe = QueuedExecuting::new();
qe.increment_queued();
assert_eq!(qe.get(), (1, 0));
assert!(!qe.is_idle());
qe.increment_queued();
assert_eq!(qe.get(), (2, 0));
}
#[test]
fn test_start_executing() {
let qe = QueuedExecuting::new();
qe.increment_queued();
qe.increment_queued();
qe.start_executing();
assert_eq!(qe.get(), (1, 1));
}
#[test]
fn test_finish_executing_returns_idle_status() {
let qe = QueuedExecuting::new();
qe.increment_queued();
qe.start_executing();
assert!(qe.finish_executing());
assert!(qe.is_idle());
}
#[test]
fn test_finish_executing_not_idle_when_queued_remains() {
let qe = QueuedExecuting::new();
qe.increment_queued();
qe.increment_queued();
qe.start_executing();
assert!(!qe.finish_executing());
assert_eq!(qe.get(), (1, 0));
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_full_lifecycle() {
let qe = QueuedExecuting::new();
qe.increment_queued();
qe.increment_queued();
qe.increment_queued();
qe.start_executing();
qe.start_executing();
assert!(!qe.finish_executing());
qe.decrement_queued(1);
assert!(qe.finish_executing());
assert!(qe.is_idle());
}
#[cfg_attr(miri, ignore)]
#[test]
#[should_panic(expected = "queued underflow")]
#[cfg(debug_assertions)]
fn test_decrement_queued_underflow_panics() {
QueuedExecuting::new().decrement_queued(1);
}
#[cfg_attr(miri, ignore)]
#[test]
#[should_panic(expected = "executing underflow")]
#[cfg(debug_assertions)]
fn test_finish_executing_underflow_panics() {
QueuedExecuting::new().finish_executing();
}
#[cfg_attr(miri, ignore)]
#[test]
#[should_panic(expected = "queued underflow in start_executing")]
#[cfg(debug_assertions)]
fn test_start_executing_without_queued_panics() {
QueuedExecuting::new().start_executing();
}
}
mod priority_vruntime {
use super::*;
use crate::scheduler::transfer::mock::FixedWorkCount;
use crate::scheduler::MockTransfer;
use std::sync::Arc;
fn test_descriptor(id: u64) -> TransferDescriptor {
let transfer_id = TransferId { id, parent: None };
let sm = Arc::new(FixedWorkCount::new(100));
let transfer = Box::new(MockTransfer::new(transfer_id, sm));
TransferDescriptor::new(transfer)
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_priority_affects_vruntime_accumulation() {
let high = test_descriptor(1);
let low = test_descriptor(2);
high.set_priority(255); low.set_priority(64);
for _ in 0..10 {
high.work_generated();
low.work_generated();
}
let high_vrt = high.vruntime();
let low_vrt = low.vruntime();
assert!(
high_vrt < low_vrt,
"high priority should have lower vruntime: high={}, low={}",
high_vrt,
low_vrt
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_max_priority_still_accumulates_vruntime() {
let desc = test_descriptor(1);
desc.set_priority(255);
desc.work_generated();
assert!(
desc.vruntime() > 0,
"max priority should still accumulate vruntime, got {}",
desc.vruntime()
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_priority_ratio_reflected_in_vruntime() {
let high = test_descriptor(1);
let low = test_descriptor(2);
high.set_priority(200);
low.set_priority(50);
for _ in 0..100 {
high.work_generated();
low.work_generated();
}
let high_vrt = high.vruntime();
let low_vrt = low.vruntime();
let ratio = low_vrt as f64 / high_vrt.max(1) as f64;
assert!(
ratio > 2.0,
"4x priority difference should yield >2x vruntime ratio: high={}, low={}, ratio={}",
high_vrt,
low_vrt,
ratio
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_work_generated_spawn_charges_both_individual_and_group_vruntime() {
let desc = test_descriptor(1);
let group = desc.group_vruntime_arc();
assert_eq!(desc.vruntime(), 0);
assert_eq!(group.load(Ordering::SeqCst), 0);
desc.work_generated_spawn();
let expected = vruntime_delta_for_cost(SPAWN_WORK_COST, desc.priority());
assert_eq!(
desc.vruntime(),
expected,
"spawn must charge individual vruntime by the spawn delta"
);
assert_eq!(
group.load(Ordering::SeqCst),
expected,
"spawn must charge group vruntime by the same spawn delta"
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn test_spawn_charge_is_less_than_io_charge() {
let spawn = test_descriptor(1);
let io = test_descriptor(2);
spawn.work_generated_spawn();
io.work_generated();
assert!(
spawn.vruntime() < io.vruntime(),
"spawn charge ({}) must be less than IO charge ({})",
spawn.vruntime(),
io.vruntime()
);
}
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::claim::ClaimState;
use loom::sync::atomic::{AtomicBool, Ordering};
use loom::sync::Arc;
use loom::thread;
#[test]
fn release_recheck_no_lost_wake() {
loom::model(|| {
let state = Arc::new(ClaimState::new());
assert!(state.try_claim());
let inserted = Arc::new(AtomicBool::new(false));
let s2 = state.clone();
let i2 = inserted.clone();
let a = thread::spawn(move || {
s2.release_claim();
if s2.take_wake_requested() {
if s2.try_claim() {
i2.store(true, Ordering::SeqCst);
}
}
});
let s3 = state.clone();
let i3 = inserted.clone();
let b = thread::spawn(move || {
s3.mark_wake_requested();
if s3.try_claim() {
i3.store(true, Ordering::SeqCst);
}
});
a.join().unwrap();
b.join().unwrap();
assert!(
inserted.load(Ordering::SeqCst),
"lost wake: neither A nor B claimed the descriptor to re-insert it"
);
});
}
#[test]
fn try_claim_is_exclusive() {
loom::model(|| {
let state = Arc::new(ClaimState::new());
let s2 = state.clone();
let a = thread::spawn(move || s2.try_claim());
let s3 = state.clone();
let b = thread::spawn(move || s3.try_claim());
let got_a = a.join().unwrap();
let got_b = b.join().unwrap();
assert!(got_a ^ got_b, "try_claim was not exclusive");
});
}
}