#![allow(clippy::missing_errors_doc)]
use core::cell::UnsafeCell;
use core::sync::atomic::{AtomicI64, AtomicU64, Ordering};
use std::sync::Arc;
use crate::sched::job::{CompactJobRef, JobRef};
pub const KHL_LINE_ITEMS: usize = 3;
#[repr(C, align(8))]
pub struct KhlBody {
pub n_items: u8,
pub k_outer: u8,
pub numa_hint: u8,
pub variant: u8,
pad: [u8; 4],
items: [CompactJobRef; KHL_LINE_ITEMS],
}
impl KhlBody {
#[inline]
pub fn empty(k_outer: u8, numa_hint: u8, variant: u8) -> Self {
Self {
n_items: 0,
k_outer,
numa_hint,
variant,
pad: [0u8; 4],
items: [
CompactJobRef::null(),
CompactJobRef::null(),
CompactJobRef::null(),
],
}
}
#[inline]
pub(crate) fn items_for_adapter(&self) -> &[CompactJobRef; KHL_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() }
}
}
}
impl core::fmt::Debug for KhlBody {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("KhlBody")
.field("n_items", &self.n_items)
.field("k_outer", &self.k_outer)
.finish_non_exhaustive()
}
}
#[repr(C, align(64))]
struct KhlSlot {
seq: AtomicU64,
body: UnsafeCell<KhlBody>,
}
unsafe impl Send for KhlSlot {}
unsafe impl Sync for KhlSlot {}
#[repr(C, align(64))]
struct KhlHeader {
bottom: AtomicI64,
_pad_bottom: [u8; 56],
head: AtomicI64,
_pad_head: [u8; 56],
capacity: usize,
capacity_mask: i64,
buffer: Box<[KhlSlot]>,
}
unsafe impl Send for KhlHeader {}
unsafe impl Sync for KhlHeader {}
pub struct SchedKhlDeque {
inner: Arc<KhlHeader>,
accumulator: UnsafeCell<KhlBody>,
}
unsafe impl Send for SchedKhlDeque {}
pub struct KhlStealer {
inner: Arc<KhlHeader>,
}
impl Clone for KhlStealer {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
#[derive(Debug)]
pub enum KhlSteal {
Success(KhlBody),
Empty,
Retry,
}
pub fn new_khl(capacity: usize) -> (SchedKhlDeque, KhlStealer) {
let capacity = capacity.max(2).next_power_of_two();
let mut buf = Vec::with_capacity(capacity);
for i in 0..capacity {
buf.push(KhlSlot {
seq: AtomicU64::new(i as u64),
body: UnsafeCell::new(KhlBody::empty(0, 0, 0)),
});
}
let inner = Arc::new(KhlHeader {
bottom: AtomicI64::new(0),
_pad_bottom: [0u8; 56],
head: AtomicI64::new(0),
_pad_head: [0u8; 56],
capacity,
capacity_mask: (capacity as i64) - 1,
buffer: buf.into_boxed_slice(),
});
let owner = SchedKhlDeque {
inner: Arc::clone(&inner),
accumulator: UnsafeCell::new(KhlBody::empty(0, 0, 0)),
};
let stealer = KhlStealer { inner };
(owner, stealer)
}
impl SchedKhlDeque {
#[inline(always)]
pub fn push(&self, job: JobRef) {
let acc = unsafe { &mut *self.accumulator.get() };
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 == KHL_LINE_ITEMS as u8 {
let body = core::mem::replace(acc, KhlBody::empty(0, 0, 0));
self.publish(body);
}
}
#[inline(always)]
pub fn push_one(&self, job: JobRef) {
let acc_n = unsafe { (*self.accumulator.get()).n_items };
if acc_n == 0 {
let body = KhlBody {
n_items: 1,
k_outer: job.k_outer,
numa_hint: job.numa_hint,
variant: job.variant,
pad: [0u8; 4],
items: [job.compact(), CompactJobRef::null(), CompactJobRef::null()],
};
self.publish(body);
} else {
self.push(job);
self.flush();
}
}
#[inline]
pub fn flush(&self) {
let acc = unsafe { &mut *self.accumulator.get() };
if acc.n_items == 0 {
return;
}
let body = core::mem::replace(acc, KhlBody::empty(0, 0, 0));
self.publish(body);
}
#[inline]
pub fn try_push_one(&self, job: JobRef) -> Result<(), JobRef> {
let acc = unsafe { &mut *self.accumulator.get() };
if acc.n_items != 0 {
let pending = core::mem::replace(acc, KhlBody::empty(0, 0, 0));
if let Err(returned) = self.try_publish(pending) {
*acc = returned;
return Err(job);
}
}
let body = KhlBody {
n_items: 1,
k_outer: job.k_outer,
numa_hint: job.numa_hint,
variant: job.variant,
pad: [0u8; 4],
items: [job.compact(), CompactJobRef::null(), CompactJobRef::null()],
};
self.try_publish(body).map_err(|body| {
unsafe { body.items[0].to_jobref(body.k_outer, body.numa_hint, body.variant) }
})
}
#[inline]
fn try_publish(&self, body: KhlBody) -> Result<(), KhlBody> {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Relaxed);
let slot = unsafe { h.buffer.get_unchecked((b & h.capacity_mask) as usize) };
if slot.seq.load(Ordering::Acquire) != b as u64 {
return Err(body);
}
unsafe {
core::ptr::write(slot.body.get(), body);
}
slot.seq.store((b as u64) + 1, Ordering::Release);
h.bottom.store(b + 1, Ordering::Relaxed);
Ok(())
}
#[inline]
fn publish(&self, body: KhlBody) {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Relaxed);
let slot = unsafe { h.buffer.get_unchecked((b & h.capacity_mask) as usize) };
#[cfg(target_arch = "x86_64")]
unsafe {
core::arch::asm!(
"prefetchw [{addr}]",
addr = in(reg) slot.body.get(),
options(nostack, preserves_flags),
);
}
let mut spins: u32 = 0;
while slot.seq.load(Ordering::Acquire) != b as u64 {
spins = spins.wrapping_add(1);
if spins & 63 == 0 {
std::thread::yield_now();
} else {
std::hint::spin_loop();
}
}
unsafe {
core::ptr::write(slot.body.get(), body);
}
slot.seq.store((b as u64) + 1, Ordering::Release);
h.bottom.store(b + 1, Ordering::Relaxed);
}
pub fn pop(&self) -> KhlSteal {
let acc = unsafe { &mut *self.accumulator.get() };
if acc.n_items > 0 {
let body = core::mem::replace(acc, KhlBody::empty(0, 0, 0));
return KhlSteal::Success(body);
}
self.pop_newest()
}
fn pop_newest(&self) -> KhlSteal {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Relaxed) - 1;
if h.head.load(Ordering::Acquire) > b {
return KhlSteal::Empty;
}
h.bottom.store(b, Ordering::SeqCst);
core::sync::atomic::fence(Ordering::SeqCst);
let t = h.head.load(Ordering::SeqCst);
if t > b {
h.bottom.store(b + 1, Ordering::SeqCst);
return KhlSteal::Empty;
}
let slot = unsafe { h.buffer.get_unchecked((b & h.capacity_mask) as usize) };
if t == b {
let won = h
.head
.compare_exchange(t, t + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
h.bottom.store(b + 1, Ordering::SeqCst);
if !won {
return KhlSteal::Retry;
}
let body = unsafe { core::ptr::read(slot.body.get()) };
slot.seq.store((b as u64) + (h.capacity as u64), Ordering::Release);
return KhlSteal::Success(body);
}
let body = unsafe { core::ptr::read(slot.body.get()) };
slot.seq.store(b as u64, Ordering::Release);
KhlSteal::Success(body)
}
#[inline]
pub fn stealer(&self) -> KhlStealer {
KhlStealer {
inner: Arc::clone(&self.inner),
}
}
#[inline]
pub fn is_inner_empty(&self) -> bool {
let h = &*self.inner;
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
t >= b
}
#[inline]
pub fn accumulator_n_items(&self) -> u8 {
unsafe { (*self.accumulator.get()).n_items }
}
}
impl KhlStealer {
#[inline]
pub fn steal(&self) -> KhlSteal {
let h = &*self.inner;
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
if t >= b {
return KhlSteal::Empty;
}
if h.head
.compare_exchange(t, t + 1, Ordering::Acquire, Ordering::Relaxed)
.is_err()
{
return KhlSteal::Retry;
}
let slot = unsafe { h.buffer.get_unchecked((t & h.capacity_mask) as usize) };
let mut spins: u32 = 0;
while slot.seq.load(Ordering::Acquire) != (t as u64) + 1 {
spins = spins.wrapping_add(1);
if spins & 63 == 0 {
std::thread::yield_now();
} else {
std::hint::spin_loop();
}
}
let body = unsafe { core::ptr::read(slot.body.get()) };
slot.seq.store(
(t as u64) + (h.capacity as u64),
Ordering::Release,
);
KhlSteal::Success(body)
}
#[inline]
pub fn len(&self) -> usize {
let h = &*self.inner;
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
b.saturating_sub(t).max(0) as usize
}
#[inline]
pub fn prefetch_for_steal(&self) {
let h = &*self.inner;
let t = h.head.load(Ordering::Relaxed);
let slot = &h.buffer[(t & h.capacity_mask) as usize];
let body_ptr = slot.body.get() as *const u8;
#[cfg(target_arch = "x86_64")]
{
unsafe {
std::arch::x86_64::_mm_prefetch(
body_ptr as *const i8,
std::arch::x86_64::_MM_HINT_T0,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
{
std::hint::black_box(body_ptr);
}
}
#[inline]
pub fn is_empty(&self) -> bool {
let h = &*self.inner;
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
t >= b
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::foundation::Variant;
use crate::sched::job::StackJob;
use crate::sched::latch::CoreLatch;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
#[test]
fn slot_is_exactly_one_cache_line() {
assert_eq!(core::mem::size_of::<KhlSlot>(), 64,
"KhlSlot must be exactly 64 bytes (one cache line)");
assert_eq!(core::mem::align_of::<KhlSlot>(), 64);
}
#[test]
fn body_round_trip_single_batch() {
let (deque, stealer) = new_khl(4);
let j = StackJob::new(|_| 42u32, CoreLatch::new());
let r = unsafe { j.as_job_ref(8, 0, Variant::Faithful) };
deque.push(r);
assert!(matches!(stealer.steal(), KhlSteal::Empty));
deque.flush();
match stealer.steal() {
KhlSteal::Success(b) => {
assert_eq!(b.n_items, 1);
unsafe { b.execute_all_lifo(); }
assert!(j.latch.is_set());
assert_eq!(unsafe { j.into_result() }, 42);
}
other => panic!("expected Success, got {other:?}"),
}
}
#[test]
fn batched_three_then_steal() {
let (deque, stealer) = new_khl(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(4, 0, Variant::Fast) };
let r2 = unsafe { j2.as_job_ref(4, 0, Variant::Fast) };
let r3 = unsafe { j3.as_job_ref(4, 0, Variant::Fast) };
deque.push(r1);
deque.push(r2);
deque.push(r3);
match stealer.steal() {
KhlSteal::Success(b) => {
assert_eq!(b.n_items, 3);
unsafe { b.execute_all_lifo(); }
assert!(j1.latch.is_set() && j2.latch.is_set() && j3.latch.is_set());
}
other => panic!("expected Success, got {other:?}"),
}
}
#[test]
fn pop_newest_takes_newest_and_leaves_oldest_to_thieves() {
let (deque, stealer) = new_khl(4);
let jobs: Vec<_> = (0..4u32)
.map(|i| StackJob::new(move |_| i, CoreLatch::new()))
.collect();
for job in &jobs[..3] {
deque.push_one(unsafe { job.as_job_ref(4, 0, Variant::Fast) });
}
match deque.pop_newest() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(jobs[2].latch.is_set() && !jobs[0].latch.is_set() && !jobs[1].latch.is_set());
deque.push_one(unsafe { jobs[3].as_job_ref(4, 0, Variant::Fast) });
match stealer.steal() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(jobs[0].latch.is_set());
match deque.pop_newest() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(jobs[3].latch.is_set());
match deque.pop_newest() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(jobs[1].latch.is_set());
assert!(matches!(deque.pop_newest(), KhlSteal::Empty));
assert!(matches!(stealer.steal(), KhlSteal::Empty));
}
#[test]
fn pop_newest_with_concurrent_thieves_runs_each_job_once() {
use core::sync::atomic::{AtomicBool, AtomicUsize};
use std::time::{Duration, Instant};
const N: usize = 20_000;
let (deque, stealer) = new_khl(64);
let ran = Arc::new(AtomicUsize::new(0));
let done = Arc::new(AtomicBool::new(false));
let jobs: Vec<_> = (0..N)
.map(|_| {
let ran = Arc::clone(&ran);
StackJob::new(move |_| { ran.fetch_add(1, Ordering::Relaxed); }, CoreLatch::new())
})
.collect();
let thieves: Vec<_> = (0..4)
.map(|_| {
let s = stealer.clone();
let done = Arc::clone(&done);
std::thread::spawn(move || {
while !done.load(Ordering::Acquire) {
if let KhlSteal::Success(b) = s.steal() {
unsafe { b.execute_all_lifo() };
}
}
while let KhlSteal::Success(b) = s.steal() {
unsafe { b.execute_all_lifo() };
}
})
})
.collect();
let deadline = Instant::now() + Duration::from_secs(60);
for (i, job) in jobs.iter().enumerate() {
let mut r = unsafe { job.as_job_ref(4, 0, Variant::Fast) };
while let Err(back) = deque.try_push_one(r) {
r = back;
if let KhlSteal::Success(b) = deque.pop_newest() {
unsafe { b.execute_all_lifo() };
}
assert!(Instant::now() < deadline, "push {i} stalled");
}
if i % 3 == 0
&& let KhlSteal::Success(b) = deque.pop_newest()
{
unsafe { b.execute_all_lifo() };
}
}
loop {
match deque.pop_newest() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
KhlSteal::Retry => continue,
KhlSteal::Empty => break,
}
assert!(Instant::now() < deadline, "owner drain stalled");
}
done.store(true, Ordering::Release);
for t in thieves {
t.join().expect("thief thread");
}
assert_eq!(ran.load(Ordering::Relaxed), N, "every job runs exactly once");
assert!(jobs.iter().all(|j| j.latch.is_set()));
}
#[test]
fn try_push_one_refuses_when_ring_full() {
let (deque, stealer) = new_khl(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(4, 0, Variant::Fast) };
assert!(deque.try_push_one(r).is_ok());
}
let fifth = unsafe { jobs[4].as_job_ref(4, 0, Variant::Fast) };
let refused = match deque.try_push_one(fifth) {
Err(job) => job,
Ok(()) => panic!("fifth push into a 4-slot ring must be refused"),
};
match stealer.steal() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
assert!(jobs[0].latch.is_set());
assert!(deque.try_push_one(refused).is_ok());
for _ in 0..4 {
match stealer.steal() {
KhlSteal::Success(b) => unsafe { b.execute_all_lifo() },
other => panic!("expected Success, got {other:?}"),
}
}
assert!(jobs.iter().all(|j| j.latch.is_set()));
assert!(matches!(stealer.steal(), KhlSteal::Empty));
}
#[test]
fn owner_pop_drains_accumulator() {
let (deque, _stealer) = new_khl(4);
let j1 = StackJob::new(|_| 10u32, CoreLatch::new());
let r1 = unsafe { j1.as_job_ref(4, 0, Variant::Fast) };
deque.push(r1);
match deque.pop() {
KhlSteal::Success(b) => {
assert_eq!(b.n_items, 1);
unsafe { b.execute_all_lifo(); }
assert!(j1.latch.is_set());
}
other => panic!("expected Success, got {other:?}"),
}
assert!(matches!(deque.pop(), KhlSteal::Empty));
}
#[test]
fn empty_steal_returns_empty() {
let (_deque, stealer) = new_khl(4);
assert!(matches!(stealer.steal(), KhlSteal::Empty));
}
#[test]
fn concurrent_owner_publish_and_thieves_no_double_take() {
use std::sync::atomic::AtomicU32;
struct Counter {
counter: Arc<AtomicU32>,
value: u32,
}
unsafe fn exec_counter(p: *const ()) {
let b = unsafe { Box::from_raw(p as *mut Counter) };
b.counter.fetch_add(b.value, O::Relaxed);
}
let n = 600u32; let counter = Arc::new(AtomicU32::new(0));
let (deque, s_proto) = new_khl(64);
let consumed = Arc::new(AtomicUsize::new(0));
let mut thieves = Vec::new();
for _ in 0..4 {
let s = s_proto.clone();
let consumed = Arc::clone(&consumed);
thieves.push(thread::spawn(move || {
while consumed.load(O::Relaxed) < n as usize {
match s.steal() {
KhlSteal::Success(b) => {
let n_items = b.n_items as usize;
unsafe { b.execute_all_lifo(); }
consumed.fetch_add(n_items, O::Relaxed);
}
KhlSteal::Empty | KhlSteal::Retry => std::thread::yield_now(),
}
}
}));
}
let counter_p = Arc::clone(&counter);
let producer = thread::spawn(move || {
for i in 0..n {
let boxed = Box::new(Counter { counter: Arc::clone(&counter_p), value: i });
let p = Box::into_raw(boxed) as *const ();
let jref = unsafe { JobRef::from_raw_parts(p, exec_counter, 0, 0, 0) };
deque.push(jref);
}
deque.flush();
});
producer.join().expect("producer joined");
for h in thieves {
h.join().expect("thief joined");
}
let expected: u32 = (0..n).sum();
assert_eq!(counter.load(O::Relaxed), expected,
"sum invariant: each job's value must be added exactly once");
assert_eq!(consumed.load(O::Relaxed), n as usize);
}
}