use crate::sched::job::JobRef;
use std::sync::Mutex;
#[derive(Default)]
pub struct PrivateLifoDeque {
inner: Mutex<Vec<JobRef>>,
}
impl PrivateLifoDeque {
pub fn new() -> Self {
Self {
inner: Mutex::new(Vec::new()),
}
}
#[cfg(test)]
#[inline]
pub(crate) fn push(&self, job: JobRef) {
let mut g = self.inner.lock().expect("private deque mutex poisoned");
g.push(job);
}
#[cfg(test)]
#[inline]
pub(crate) fn pop(&self) -> Option<JobRef> {
let mut g = self.inner.lock().expect("private deque mutex poisoned");
g.pop()
}
#[cfg(test)]
#[inline]
pub(crate) fn push_local(&self, job: JobRef) -> Result<(), JobRef> {
match self.inner.try_lock() {
Ok(mut g) => {
g.push(job);
Ok(())
}
Err(_) => Err(job),
}
}
#[cfg(test)]
#[inline]
pub(crate) fn try_pop_local(&self) -> Result<Option<JobRef>, ()> {
match self.inner.try_lock() {
Ok(mut g) => Ok(g.pop()),
Err(_) => Err(()),
}
}
pub fn donate_from(&self, source: &PrivateLifoDeque, max_jobs: usize) -> usize {
if max_jobs == 0 {
return 0;
}
let mut src = match source.inner.try_lock() {
Ok(g) => g,
Err(_) => return 0,
};
let n_avail = src.len();
if n_avail <= 1 {
return 0;
}
let take = max_jobs.min(n_avail / 2);
let mut dst = self.inner.lock().expect("private deque mutex poisoned");
for job in src.drain(0..take) {
dst.push(job);
}
take
}
#[inline]
pub fn is_empty(&self) -> bool {
self.inner
.try_lock()
.map(|g| g.is_empty())
.unwrap_or(false)
}
}
impl std::fmt::Debug for PrivateLifoDeque {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("PrivateLifoDeque")
.field("len", &self.inner.try_lock().map(|g| g.len()).unwrap_or(0))
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicU32, Ordering};
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 = PrivateLifoDeque::new();
assert!(d.is_empty());
assert!(d.pop().is_none());
}
#[test]
fn push_pop_lifo_order() {
let d = PrivateLifoDeque::new();
let counter = Arc::new(AtomicU32::new(0));
let c1 = Arc::clone(&counter);
let c2 = Arc::clone(&counter);
let c3 = Arc::clone(&counter);
let j1 = StackJob::new(
move |_| { c1.fetch_add(1, Ordering::Relaxed); },
CoreLatch::new(),
);
let j2 = StackJob::new(
move |_| { c2.fetch_add(10, Ordering::Relaxed); },
CoreLatch::new(),
);
let j3 = StackJob::new(
move |_| { c3.fetch_add(100, Ordering::Relaxed); },
CoreLatch::new(),
);
unsafe {
d.push(j1.as_job_ref(0, NUMA_HINT_ANY, Variant::Faithful));
d.push(j2.as_job_ref(0, NUMA_HINT_ANY, Variant::Faithful));
d.push(j3.as_job_ref(0, NUMA_HINT_ANY, Variant::Faithful));
}
let popped = d.pop().expect("third push pop");
unsafe { popped.execute(); }
assert_eq!(counter.load(Ordering::Relaxed), 100);
let popped = d.pop().expect("second push pop");
unsafe { popped.execute(); }
assert_eq!(counter.load(Ordering::Relaxed), 110);
let popped = d.pop().expect("first push pop");
unsafe { popped.execute(); }
assert_eq!(counter.load(Ordering::Relaxed), 111);
assert!(d.pop().is_none());
}
#[test]
fn donate_from_leaves_one_in_source() {
let donor = PrivateLifoDeque::new();
let receiver = PrivateLifoDeque::new();
let counter = Arc::new(AtomicU32::new(0));
let mut jobs = Vec::new();
for i in 0..4 {
let c = Arc::clone(&counter);
jobs.push(StackJob::new(
move |_| { c.fetch_add(1u32 << i, Ordering::Relaxed); },
CoreLatch::new(),
));
}
for j in &jobs {
unsafe { donor.push(j.as_job_ref(0, NUMA_HINT_ANY, Variant::Faithful)); }
}
let n = receiver.donate_from(&donor, 8);
assert_eq!(n, 2);
let mut donor_after = 0;
while donor.pop().is_some() { donor_after += 1; }
assert_eq!(donor_after, 2);
let mut recv_after = 0;
while receiver.pop().is_some() { recv_after += 1; }
assert_eq!(recv_after, 2);
}
#[test]
fn try_pop_local_no_blocking() {
let d = PrivateLifoDeque::new();
let counter = Arc::new(AtomicU32::new(0));
let c = Arc::clone(&counter);
let j = StackJob::new(
move |_| { c.fetch_add(7, Ordering::Relaxed); },
CoreLatch::new(),
);
unsafe {
assert!(d.push_local(j.as_job_ref(0, NUMA_HINT_ANY, Variant::Faithful)).is_ok());
}
let popped = d.try_pop_local().expect("uncontested try_pop succeeds");
let popped = popped.expect("had one job");
unsafe { popped.execute(); }
assert_eq!(counter.load(Ordering::Relaxed), 7);
assert!(matches!(d.try_pop_local(), Ok(None)));
}
}