#![allow(clippy::missing_errors_doc)]
use core::cell::UnsafeCell;
use core::mem::MaybeUninit;
use crate::sched::chase_lev_local::{self, new_chase_lev};
use crate::sched::job::{CompactJobRef, JobRef};
pub const FCL_LINE_ITEMS: usize = 3;
#[repr(C, align(64))]
pub(crate) struct FatSlot {
pub(crate) n_items: u8,
pub(crate) k_outer: u8,
pub(crate) numa_hint: u8,
pub(crate) variant: u8,
pub(crate) _pad: [u8; 12],
pub(crate) items: [CompactJobRef; FCL_LINE_ITEMS],
}
impl FatSlot {
#[inline]
pub(crate) fn empty(k_outer: u8, numa_hint: u8, variant: u8) -> Self {
Self {
n_items: 0,
k_outer,
numa_hint,
variant,
_pad: [0u8; 12],
items: [
CompactJobRef::null(),
CompactJobRef::null(),
CompactJobRef::null(),
],
}
}
}
pub struct PoppedSlot {
pub n_items: u8,
pub k_outer: u8,
pub numa_hint: u8,
pub variant: u8,
pub(crate) items: [CompactJobRef; FCL_LINE_ITEMS],
}
impl core::fmt::Debug for PoppedSlot {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("PoppedSlot")
.field("n_items", &self.n_items)
.field("k_outer", &self.k_outer)
.field("numa_hint", &self.numa_hint)
.field("variant", &self.variant)
.finish_non_exhaustive()
}
}
impl PoppedSlot {
#[inline]
fn from_slot(s: FatSlot) -> Self {
Self {
n_items: s.n_items,
k_outer: s.k_outer,
numa_hint: s.numa_hint,
variant: s.variant,
items: s.items,
}
}
#[inline]
pub(crate) fn compact_items_for_adapter(&self) -> &[CompactJobRef; FCL_LINE_ITEMS] {
&self.items
}
#[inline]
pub unsafe fn execute_all_lifo(self) {
for i in (0..self.n_items as usize).rev() {
unsafe { self.items[i].execute() }
}
}
}
pub struct SchedFclDeque {
inner: chase_lev_local::Worker<FatSlot>,
accumulator: UnsafeCell<MaybeUninit<FatSlot>>,
}
unsafe impl Send for SchedFclDeque {}
pub struct FclStealer {
inner: chase_lev_local::Stealer<FatSlot>,
}
impl Clone for FclStealer {
fn clone(&self) -> Self {
Self {
inner: self.inner.clone(),
}
}
}
pub fn new_fcl(capacity: usize) -> (SchedFclDeque, FclStealer) {
let (w, s) = new_chase_lev::<FatSlot>(capacity);
let acc = UnsafeCell::new(MaybeUninit::new(FatSlot::empty(0, 0, 0)));
(
SchedFclDeque {
inner: w,
accumulator: acc,
},
FclStealer { inner: s },
)
}
impl SchedFclDeque {
#[inline(always)]
pub fn push(&self, job: JobRef) {
let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
if acc.n_items == 0 {
acc.k_outer = job.k_outer;
acc.numa_hint = job.numa_hint;
acc.variant = job.variant;
}
let idx = acc.n_items as usize;
unsafe { *acc.items.get_unchecked_mut(idx) = job.compact(); }
acc.n_items += 1;
if acc.n_items == FCL_LINE_ITEMS as u8 {
let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
self.flush_slot(slot);
}
}
#[cold]
#[inline(never)]
fn flush_slot(&self, slot: FatSlot) {
let mut s = slot;
loop {
match self.inner.push(s) {
Ok(()) => return,
Err(retry) => {
s = retry;
std::hint::spin_loop();
}
}
}
}
#[inline]
pub fn try_push_one(&self, job: JobRef) -> Result<(), JobRef> {
let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
if acc.n_items != 0 {
let pending = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
if let Err(returned) = self.inner.push(pending) {
*acc = returned;
return Err(job);
}
}
let mut slot = FatSlot::empty(job.k_outer, job.numa_hint, job.variant);
slot.items[0] = job.compact();
slot.n_items = 1;
self.inner.push(slot).map_err(|slot| {
unsafe { slot.items[0].to_jobref(slot.k_outer, slot.numa_hint, slot.variant) }
})
}
#[inline]
pub fn flush(&self) {
let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
if acc.n_items == 0 {
return;
}
let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
self.flush_slot(slot);
}
pub fn pop(&self) -> Option<PoppedSlot> {
let acc = unsafe { (*self.accumulator.get()).assume_init_mut() };
if acc.n_items > 0 {
let slot = core::mem::replace(acc, FatSlot::empty(0, 0, 0));
return Some(PoppedSlot::from_slot(slot));
}
match self.inner.pop() {
chase_lev_local::Steal::Success(s) => Some(PoppedSlot::from_slot(s)),
chase_lev_local::Steal::Empty | chase_lev_local::Steal::Retry => None,
}
}
#[inline]
pub fn stealer(&self) -> FclStealer {
FclStealer {
inner: self.inner.stealer(),
}
}
}
impl Drop for SchedFclDeque {
fn drop(&mut self) {
unsafe {
(*self.accumulator.get()).assume_init_drop();
}
}
}
impl FclStealer {
#[inline]
pub fn steal(&self) -> chase_lev_local::Steal<PoppedSlot> {
match self.inner.steal() {
chase_lev_local::Steal::Success(s) => {
chase_lev_local::Steal::Success(PoppedSlot::from_slot(s))
}
chase_lev_local::Steal::Empty => chase_lev_local::Steal::Empty,
chase_lev_local::Steal::Retry => chase_lev_local::Steal::Retry,
}
}
#[inline]
pub fn prefetch_for_steal(&self) {
self.inner.prefetch_for_steal();
}
#[inline]
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn slot_is_exactly_one_cache_line() {
assert_eq!(core::mem::size_of::<FatSlot>(), 64,
"FatSlot must be exactly 64 bytes (one cache line)");
assert_eq!(core::mem::align_of::<FatSlot>(), 64,
"FatSlot must be 64-byte aligned");
}
#[test]
fn compact_jobref_is_two_words() {
assert_eq!(core::mem::size_of::<CompactJobRef>(), 16,
"CompactJobRef must be 16 bytes");
}
use crate::sched::job::StackJob;
use crate::sched::latch::CoreLatch;
use crate::foundation::Variant;
#[test]
fn try_push_one_refuses_when_inner_full() {
let (deque, stealer) = new_fcl(4);
let jobs: Vec<_> = (0..5u32)
.map(|i| StackJob::new(move |_| i, CoreLatch::new()))
.collect();
for job in &jobs[..4] {
let r = unsafe { job.as_job_ref(8, 0, Variant::Faithful) };
assert!(deque.try_push_one(r).is_ok());
}
let fifth = unsafe { jobs[4].as_job_ref(8, 0, Variant::Faithful) };
let refused = match deque.try_push_one(fifth) {
Err(job) => job,
Ok(()) => panic!("fifth push into a 4-slot deque must be refused"),
};
match stealer.steal() {
chase_lev_local::Steal::Success(s) => unsafe { s.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(deque.try_push_one(refused).is_ok());
for _ in 0..4 {
match stealer.steal() {
chase_lev_local::Steal::Success(s) => unsafe { s.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
}
assert!(jobs.iter().all(|j| j.latch.is_set()));
assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
}
#[test]
fn push_single_then_flush_then_steal() {
let (deque, stealer) = new_fcl(4);
let job = StackJob::new(|_stolen| 7u32, CoreLatch::new());
let r = unsafe { job.as_job_ref(8, 0, Variant::Faithful) };
deque.push(r);
assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
deque.flush();
match stealer.steal() {
chase_lev_local::Steal::Success(s) => {
assert_eq!(s.n_items, 1);
unsafe { s.execute_all_lifo(); }
assert!(job.latch.is_set());
let result = unsafe { job.into_result() };
assert_eq!(result, 7);
}
other => panic!("expected Success, got {other:?}"),
}
}
#[test]
fn buffer_fills_to_3_then_auto_flushes() {
let (deque, stealer) = new_fcl(4);
let j1 = StackJob::new(|_| 1u32, CoreLatch::new());
let j2 = StackJob::new(|_| 2u32, CoreLatch::new());
let j3 = StackJob::new(|_| 3u32, CoreLatch::new());
let r1 = unsafe { j1.as_job_ref(8, 0, Variant::Faithful) };
let r2 = unsafe { j2.as_job_ref(8, 0, Variant::Faithful) };
let r3 = unsafe { j3.as_job_ref(8, 0, Variant::Faithful) };
deque.push(r1);
deque.push(r2);
assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
deque.push(r3);
match stealer.steal() {
chase_lev_local::Steal::Success(s) => {
assert_eq!(s.n_items, 3);
unsafe { s.execute_all_lifo(); }
assert!(j1.latch.is_set());
assert!(j2.latch.is_set());
assert!(j3.latch.is_set());
assert_eq!(unsafe { j1.into_result() }, 1);
assert_eq!(unsafe { j2.into_result() }, 2);
assert_eq!(unsafe { j3.into_result() }, 3);
}
other => panic!("expected Success, got {other:?}"),
}
}
#[test]
fn owner_pop_drains_accumulator_first_lifo() {
let (deque, _stealer) = new_fcl(4);
let j1 = StackJob::new(|_| 10u32, CoreLatch::new());
let j2 = StackJob::new(|_| 20u32, CoreLatch::new());
let r1 = unsafe { j1.as_job_ref(4, 0, Variant::Fast) };
let r2 = unsafe { j2.as_job_ref(4, 0, Variant::Fast) };
deque.push(r1);
deque.push(r2);
match deque.pop() {
Some(slot) => {
assert_eq!(slot.n_items, 2);
unsafe { slot.execute_all_lifo(); }
assert!(j1.latch.is_set());
assert!(j2.latch.is_set());
}
None => panic!("expected Some(slot)"),
}
assert!(deque.pop().is_none());
}
#[test]
#[allow(clippy::type_complexity)]
fn batched_push_then_steal_round_trip() {
let (deque, stealer) = new_fcl(8);
let jobs: Vec<StackJob<CoreLatch, fn(bool) -> u32, u32>> =
(0..9).map(|_| StackJob::new(default_job_fn as fn(bool) -> u32, CoreLatch::new())).collect();
for j in &jobs {
let r = unsafe { j.as_job_ref(4, 0, Variant::Fast) };
deque.push(r);
}
let mut executed = 0;
for _ in 0..3 {
match stealer.steal() {
chase_lev_local::Steal::Success(s) => {
assert_eq!(s.n_items, 3);
executed += s.n_items as usize;
unsafe { s.execute_all_lifo(); }
}
other => panic!("expected Success, got {other:?}"),
}
}
assert_eq!(executed, 9);
assert!(matches!(stealer.steal(), chase_lev_local::Steal::Empty));
}
fn default_job_fn(_stolen: bool) -> u32 { 0 }
}