use super::{AtomicU64, AtomicUsize, Ordering, ParkToken, TaskId, TaskKey, WakeCause, WakeNotice};
pub(super) struct Slot {
next: AtomicUsize,
task: AtomicU64,
wait: AtomicU64,
selection: AtomicU64,
}
#[repr(align(64))]
pub(super) struct Cursor(AtomicUsize);
impl Cursor {
fn new() -> Self {
Self(AtomicUsize::new(0))
}
}
impl Slot {
fn new() -> Self {
Self {
next: AtomicUsize::new(0),
task: AtomicU64::new(0),
wait: AtomicU64::new(0),
selection: AtomicU64::new(0),
}
}
}
pub(crate) struct WakeQueue {
slots: Box<[Slot]>,
pub(super) head: Cursor,
pub(super) consumer: Cursor,
}
impl WakeQueue {
const SLEEPING: usize = 1 << (usize::BITS - 1);
const INDEX_MASK: usize = !Self::SLEEPING;
pub(crate) fn new(capacity: usize) -> Self {
let slot_count = capacity
.checked_mul(2)
.and_then(|count| count.checked_add(2))
.expect("wake queue capacity exhausted");
assert!(slot_count < Self::SLEEPING, "wake queue capacity exhausted");
Self {
slots: (0..slot_count).map(|_| Slot::new()).collect(),
head: Cursor::new(),
consumer: Cursor::new(),
}
}
pub(crate) fn push(
&self,
notice: WakeNotice,
before_publish: impl FnOnce(),
) -> std::result::Result<bool, WakeNotice> {
let index = notice.route.encoded();
let Some(slot) = self.slots.get(index) else {
return Err(notice);
};
if slot.task.load(Ordering::Acquire) != 0 {
return Err(notice);
}
slot.task.store(notice.task.get(), Ordering::Relaxed);
slot.wait.store(notice.token.wait(), Ordering::Relaxed);
slot.selection.store(
encode_selection(notice.token.generation(), notice.cause),
Ordering::Relaxed,
);
before_publish();
let mut head = self.head.0.load(Ordering::Acquire);
loop {
slot.next.store(head & Self::INDEX_MASK, Ordering::Relaxed);
match self.head.0.compare_exchange_weak(
head,
index,
Ordering::Release,
Ordering::Acquire,
) {
Ok(_) => return Ok(head & Self::SLEEPING != 0),
Err(observed) => head = observed,
}
}
}
pub(crate) fn pop(&self) -> Option<WakeNotice> {
let mut index = self.consumer.0.load(Ordering::Relaxed);
if index == 0 {
if self.head.0.load(Ordering::Acquire) & Self::INDEX_MASK == 0 {
return None;
}
index = self.head.0.swap(0, Ordering::Acquire) & Self::INDEX_MASK;
if index == 0 {
return None;
}
if self.slots[index].next.load(Ordering::Relaxed) != 0 {
index = self.reverse(index);
}
}
let slot = &self.slots[index];
self.consumer
.0
.store(slot.next.load(Ordering::Relaxed), Ordering::Relaxed);
let (generation, cause) = decode_selection(slot.selection.load(Ordering::Relaxed));
let notice = WakeNotice {
token: ParkToken::new(slot.wait.load(Ordering::Relaxed), generation),
task: TaskId::new(slot.task.load(Ordering::Relaxed)),
route: TaskKey::from_encoded(index),
cause,
};
slot.task.store(0, Ordering::Release);
Some(notice)
}
pub(crate) fn has_pending(&self) -> bool {
self.consumer.0.load(Ordering::Relaxed) != 0
|| self.head.0.load(Ordering::Acquire) & Self::INDEX_MASK != 0
}
pub(crate) fn pending(&self) -> usize {
self.slots
.iter()
.filter(|slot| slot.task.load(Ordering::Acquire) != 0)
.count()
}
pub(crate) fn arm_wait(&self) -> bool {
if self.consumer.0.load(Ordering::Relaxed) != 0 {
return true;
}
let mut head = self.head.0.load(Ordering::Acquire);
loop {
if head & Self::INDEX_MASK != 0 {
return true;
}
if head & Self::SLEEPING != 0 {
return false;
}
match self.head.0.compare_exchange_weak(
head,
Self::SLEEPING,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return false,
Err(observed) => head = observed,
}
}
}
pub(crate) fn disarm_wait(&self) {
self.head.0.fetch_and(Self::INDEX_MASK, Ordering::Release);
}
fn reverse(&self, mut head: usize) -> usize {
let mut reversed = 0;
while head != 0 {
let slot = &self.slots[head];
let next = slot.next.load(Ordering::Relaxed);
slot.next.store(reversed, Ordering::Relaxed);
reversed = head;
head = next;
}
reversed
}
}
fn encode_selection(generation: u64, cause: WakeCause) -> u64 {
let cause = match cause {
WakeCause::Ready => 1,
WakeCause::TimedOut => 2,
WakeCause::Cancelled => 3,
WakeCause::InheritedCancelled => 4,
WakeCause::Closed => 5,
};
assert!(
generation <= u64::MAX >> 3,
"wake generation exceeds packed representation"
);
(generation << 3) | cause
}
fn decode_selection(selection: u64) -> (u64, WakeCause) {
let cause = match selection & 0x07 {
1 => WakeCause::Ready,
2 => WakeCause::TimedOut,
3 => WakeCause::Cancelled,
4 => WakeCause::InheritedCancelled,
5 => WakeCause::Closed,
_ => unreachable!("invalid queued wake cause"),
};
(selection >> 3, cause)
}
#[cfg(test)]
#[path = "wake_queue_core_test.rs"]
mod wake_queue_core_test;