use crate::sched::chase_lev_local::{Steal, Stealer};
use crate::sched::job::JobRef;
#[cfg(test)]
use crate::sched::chase_lev_local::{Worker, new_chase_lev};
#[cfg(test)]
pub(crate) struct ArenaDeque {
worker: Worker<JobRef>,
stealer: Stealer<JobRef>,
}
#[cfg(test)]
impl ArenaDeque {
pub(crate) fn new_lifo() -> Self {
let (worker, stealer) = new_chase_lev::<JobRef>(64);
Self { worker, stealer }
}
#[inline]
pub(crate) fn push(&self, job: JobRef) {
if self.worker.push(job).is_err() {
panic!("test deque must not overflow");
}
}
#[inline]
pub(crate) fn pop(&self) -> Option<JobRef> {
match self.worker.pop() {
Steal::Success(j) => Some(j),
Steal::Empty | Steal::Retry => None,
}
}
#[inline]
pub(crate) fn stealer(&self) -> Stealer<JobRef> {
self.stealer.clone()
}
#[inline]
pub(crate) fn is_empty(&self) -> bool {
self.worker.is_empty()
}
}
#[allow(dead_code)]
pub(crate) fn steal_retry(stealer: &Stealer<JobRef>) -> Option<JobRef> {
loop {
match stealer.steal() {
Steal::Success(job) => return Some(job),
Steal::Empty => return None,
Steal::Retry => continue,
}
}
}
#[allow(dead_code)]
pub(crate) fn steal_retry_batch(
stealer: &Stealer<JobRef>,
_dest_worker: &crate::sched::chase_lev_local::Worker<JobRef>,
) -> Option<JobRef> {
steal_retry(stealer)
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicU32, Ordering};
use std::thread;
use crate::foundation::Variant;
use crate::sched::job::{NUMA_HINT_ANY, StackJob};
use crate::sched::latch::CoreLatch;
#[test]
fn new_deque_is_empty() {
let d = ArenaDeque::new_lifo();
assert!(d.is_empty());
assert!(d.pop().is_none());
}
#[test]
fn push_then_pop_returns_same_job() {
let d = ArenaDeque::new_lifo();
let job = StackJob::new(|_stolen| 7u32, CoreLatch::new());
let r = unsafe { job.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful) };
let id_k = r.k_outer;
d.push(r);
assert!(!d.is_empty());
let popped = d.pop().expect("pop after push must return job");
assert_eq!(popped.k_outer, id_k);
unsafe { popped.execute() };
assert!(job.latch.is_set());
let value = unsafe { job.into_result() };
assert_eq!(value, 7);
}
#[test]
fn pop_is_lifo_on_owner_end() {
let d = ArenaDeque::new_lifo();
let j1 = StackJob::new(|_| 1u32, CoreLatch::new());
let j2 = StackJob::new(|_| 2u32, CoreLatch::new());
let j3 = StackJob::new(|_| 3u32, CoreLatch::new());
unsafe {
d.push(j1.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
d.push(j2.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
d.push(j3.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
}
let r3 = d.pop().unwrap();
unsafe { r3.execute() };
assert!(j3.latch.is_set());
let r2 = d.pop().unwrap();
unsafe { r2.execute() };
assert!(j2.latch.is_set());
let r1 = d.pop().unwrap();
unsafe { r1.execute() };
assert!(j1.latch.is_set());
assert!(d.pop().is_none());
let v1 = unsafe { j1.into_result() };
let v2 = unsafe { j2.into_result() };
let v3 = unsafe { j3.into_result() };
assert_eq!((v1, v2, v3), (1, 2, 3));
}
#[test]
fn steal_retry_returns_none_on_empty() {
let d = ArenaDeque::new_lifo();
assert!(steal_retry(&d.stealer()).is_none());
}
#[test]
fn cross_thread_push_owner_steal_thief_executes_jobs() {
const N: u32 = 64;
let d = ArenaDeque::new_lifo();
let stealer = d.stealer();
let counter = Arc::new(AtomicU32::new(0));
let counter_thief = Arc::clone(&counter);
let jobs: Vec<_> = (0..N)
.map(|_| {
let c = Arc::clone(&counter);
StackJob::new(
move |_stolen| {
c.fetch_add(1, Ordering::SeqCst);
},
CoreLatch::new(),
)
})
.collect();
let thief = thread::spawn(move || {
let mut seen = 0u32;
while seen < N {
if let Some(job) = steal_retry(&stealer) {
unsafe { job.execute() };
seen += 1;
} else {
thread::yield_now();
}
}
});
for job in &jobs {
let r = unsafe { job.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful) };
d.push(r);
}
thief.join().expect("thief thread must finish");
assert_eq!(counter.load(Ordering::SeqCst), N,
"every pushed job must execute exactly once across threads");
for j in &jobs {
assert!(j.latch.is_set());
}
let _ = counter_thief;
}
}