#![allow(clippy::missing_errors_doc)]
use std::fs::{File, OpenOptions};
use std::io;
use std::path::Path;
use std::sync::atomic::{AtomicI64, AtomicU64, Ordering, fence};
use memmap2::{MmapMut, MmapOptions};
pub const CHASE_LEV_MAGIC: u64 = 0x464C_434C_0000_0001;
pub const SLOT_SIZE: usize = 64;
pub const ARGS_INLINE_BYTES: usize = SLOT_SIZE - 16;
#[repr(C, align(64))]
pub struct DequeHeader {
pub magic: u64,
pub capacity: u64,
pub owner_pid: AtomicU64,
pub epoch: AtomicU64,
pub _pad_meta: [u8; 24],
pub top: AtomicI64,
pub _pad_top: [u8; 56],
pub bottom: AtomicI64,
pub _pad_bottom: [u8; 56],
}
#[repr(C, align(64))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RemoteJobSlot {
pub closure_id: u32,
pub args_len: u32,
pub latch_offset: u32,
pub reserved_tag: u32,
pub args_inline: [u8; ARGS_INLINE_BYTES],
}
impl RemoteJobSlot {
pub fn new(
closure_id: u32,
latch_offset: u32,
args: &[u8],
) -> Result<Self, PushError> {
if args.len() > ARGS_INLINE_BYTES {
return Err(PushError::PayloadTooLarge);
}
let mut s = Self {
closure_id,
args_len: args.len() as u32,
latch_offset,
reserved_tag: 0,
args_inline: [0u8; ARGS_INLINE_BYTES],
};
s.args_inline[..args.len()].copy_from_slice(args);
Ok(s)
}
pub fn args(&self) -> &[u8] {
&self.args_inline[..self.args_len as usize]
}
}
pub const fn deque_file_size(capacity: usize) -> usize {
std::mem::size_of::<DequeHeader>() + capacity * SLOT_SIZE
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PushError {
Full,
PayloadTooLarge,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Steal {
Success(RemoteJobSlot),
Empty,
Retry,
}
pub struct MmfChaseLevDeque {
_file: File,
mmap: MmapMut,
capacity: usize,
capacity_mask: i64,
}
unsafe impl Send for MmfChaseLevDeque {}
unsafe impl Sync for MmfChaseLevDeque {}
impl MmfChaseLevDeque {
pub fn create<P: AsRef<Path>>(path: P, capacity: usize) -> io::Result<Self> {
let capacity = capacity.max(2).next_power_of_two();
let size = deque_file_size(capacity);
let file = OpenOptions::new()
.read(true)
.write(true)
.create(true)
.truncate(true)
.open(path.as_ref())?;
file.set_len(size as u64)?;
let mut mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
let header_ptr = mmap.as_mut_ptr() as *mut DequeHeader;
unsafe {
(*header_ptr).magic = CHASE_LEV_MAGIC;
(*header_ptr).capacity = capacity as u64;
(*header_ptr).owner_pid = AtomicU64::new(std::process::id() as u64);
(*header_ptr).epoch = AtomicU64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_meta.as_mut_ptr(), 0, 24);
(*header_ptr).top = AtomicI64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_top.as_mut_ptr(), 0, 56);
(*header_ptr).bottom = AtomicI64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_bottom.as_mut_ptr(), 0, 56);
}
let slots_start = std::mem::size_of::<DequeHeader>();
unsafe {
std::ptr::write_bytes(
mmap.as_mut_ptr().add(slots_start),
0,
capacity * SLOT_SIZE,
);
}
mmap.flush()?;
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
})
}
pub fn open<P: AsRef<Path>>(path: P) -> io::Result<Self> {
let file = OpenOptions::new().read(true).write(true).open(path.as_ref())?;
let size = file.metadata()?.len() as usize;
if size < std::mem::size_of::<DequeHeader>() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"deque file too small to contain header",
));
}
let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
let header_ptr = mmap.as_ptr() as *const DequeHeader;
let (magic, capacity) = unsafe {
((*header_ptr).magic, (*header_ptr).capacity as usize)
};
if magic != CHASE_LEV_MAGIC {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("chase-lev magic mismatch: got {magic:#x}, want {CHASE_LEV_MAGIC:#x}"),
));
}
if !capacity.is_power_of_two() || capacity < 2 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("deque capacity {capacity} is not a power of two >= 2"),
));
}
if size < deque_file_size(capacity) {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("deque file size {size} below expected {}", deque_file_size(capacity)),
));
}
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
})
}
pub fn capacity(&self) -> usize {
self.capacity
}
pub fn owner_pid(&self) -> u64 {
self.header().owner_pid.load(Ordering::Acquire)
}
pub fn epoch(&self) -> u64 {
self.header().epoch.load(Ordering::Acquire)
}
pub fn close_owner(&self) {
self.header().owner_pid.store(0, Ordering::Release);
self.header().epoch.fetch_add(1, Ordering::Release);
}
fn header(&self) -> &DequeHeader {
unsafe { &*(self.mmap.as_ptr() as *const DequeHeader) }
}
fn slot_ptr(&self, idx: i64) -> *mut RemoteJobSlot {
let slot_idx = (idx & self.capacity_mask) as usize;
let off = std::mem::size_of::<DequeHeader>() + slot_idx * SLOT_SIZE;
unsafe { self.mmap.as_ptr().add(off) as *mut RemoteJobSlot }
}
pub fn snapshot_size(&self) -> (i64, i64, i64) {
let h = self.header();
let t = h.top.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
(t, b, b - t)
}
pub fn push(&self, slot: RemoteJobSlot) -> Result<(), PushError> {
let h = self.header();
let b = h.bottom.load(Ordering::Relaxed);
let t = h.top.load(Ordering::Acquire);
let size = b - t;
if size >= self.capacity as i64 {
return Err(PushError::Full);
}
unsafe {
std::ptr::write(self.slot_ptr(b), slot);
}
h.bottom.store(b + 1, Ordering::Release);
Ok(())
}
pub fn pop(&self) -> Steal {
let h = self.header();
let b = h.bottom.load(Ordering::Relaxed) - 1;
h.bottom.store(b, Ordering::Relaxed);
fence(Ordering::SeqCst);
let t = h.top.load(Ordering::Relaxed);
if t > b {
h.bottom.store(b + 1, Ordering::Relaxed);
return Steal::Empty;
}
let slot = unsafe { std::ptr::read(self.slot_ptr(b)) };
if t < b {
return Steal::Success(slot);
}
let won = h
.top
.compare_exchange(t, t + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
h.bottom.store(b + 1, Ordering::Relaxed);
if won {
Steal::Success(slot)
} else {
Steal::Empty
}
}
pub fn steal(&self) -> Steal {
let h = self.header();
let t = h.top.load(Ordering::Acquire);
fence(Ordering::SeqCst);
let b = h.bottom.load(Ordering::Acquire);
if t >= b {
return Steal::Empty;
}
let slot = unsafe { std::ptr::read(self.slot_ptr(t)) };
let won = h
.top
.compare_exchange(t, t + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
if won {
Steal::Success(slot)
} else {
Steal::Retry
}
}
pub fn flush(&self) -> io::Result<()> {
self.mmap.flush()
}
#[inline]
pub fn prefetch_for_steal(&self) {
let t = self.header().top.load(Ordering::Relaxed);
let slot = self.slot_ptr(t);
#[cfg(target_arch = "x86_64")]
{
unsafe {
std::arch::x86_64::_mm_prefetch(
slot as *const i8,
std::arch::x86_64::_MM_HINT_T0,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
{
std::hint::black_box(slot);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
fn temp_path(name: &str) -> std::path::PathBuf {
let mut p = std::env::temp_dir();
let pid = std::process::id();
let nonce = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.map(|d| d.as_nanos())
.unwrap_or(0);
p.push(format!("flynnel_chase_lev_{pid}_{nonce}_{name}.bin"));
p
}
fn dummy_slot(id: u32, args_len: u8) -> RemoteJobSlot {
let args: Vec<u8> = (0..args_len).collect();
RemoteJobSlot::new(id, u32::MAX, &args).expect("build slot")
}
#[test]
fn create_then_open_round_trips_header() {
let path = temp_path("create_open");
let _d = MmfChaseLevDeque::create(&path, 8).expect("create");
let opened = MmfChaseLevDeque::open(&path).expect("open");
assert_eq!(opened.capacity(), 8);
assert_eq!(opened.owner_pid(), std::process::id() as u64);
assert_eq!(opened.epoch(), 0);
std::fs::remove_file(&path).ok();
}
#[test]
fn open_rejects_bad_magic() {
let path = temp_path("bad_magic");
std::fs::write(&path, vec![0u8; 16384]).expect("seed");
let r = MmfChaseLevDeque::open(&path);
assert!(r.is_err(), "open must reject bad-magic file");
std::fs::remove_file(&path).ok();
}
#[test]
fn push_then_pop_lifo_owner_side() {
let path = temp_path("push_pop_lifo");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
d.push(dummy_slot(1, 1)).expect("push 1");
d.push(dummy_slot(2, 1)).expect("push 2");
d.push(dummy_slot(3, 1)).expect("push 3");
let s = d.pop();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 3),
"expected closure_id 3, got {s:?}");
let s = d.pop();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 2));
let s = d.pop();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 1));
assert!(matches!(d.pop(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn full_deque_reports_push_error() {
let path = temp_path("full");
let d = MmfChaseLevDeque::create(&path, 2).expect("create");
d.push(dummy_slot(1, 0)).expect("push 1");
d.push(dummy_slot(2, 0)).expect("push 2");
let err = d.push(dummy_slot(3, 0)).expect_err("expected full");
assert_eq!(err, PushError::Full);
std::fs::remove_file(&path).ok();
}
#[test]
fn oversize_args_rejected() {
let big = vec![0u8; ARGS_INLINE_BYTES + 1];
let err = RemoteJobSlot::new(0, u32::MAX, &big).expect_err("expected oversize");
assert_eq!(err, PushError::PayloadTooLarge);
}
#[test]
fn steal_drains_owner_pushed_items_fifo() {
let path = temp_path("steal_fifo");
let d = MmfChaseLevDeque::create(&path, 8).expect("create");
d.push(dummy_slot(1, 0)).expect("push 1");
d.push(dummy_slot(2, 0)).expect("push 2");
d.push(dummy_slot(3, 0)).expect("push 3");
let s = d.steal();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 1),
"expected closure_id 1, got {s:?}");
let s = d.steal();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 2));
let s = d.steal();
assert!(matches!(s, Steal::Success(slot) if slot.closure_id == 3));
assert!(matches!(d.steal(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn args_round_trip_through_slot() {
let path = temp_path("args_round_trip");
let d = MmfChaseLevDeque::create(&path, 2).expect("create");
let payload: Vec<u8> = (0..32u8).collect();
let slot = RemoteJobSlot::new(0xCAFE_F00D, 0x1234_5678, &payload)
.expect("build slot");
d.push(slot).expect("push");
match d.pop() {
Steal::Success(got) => {
assert_eq!(got.closure_id, 0xCAFE_F00D);
assert_eq!(got.latch_offset, 0x1234_5678);
assert_eq!(got.args(), &payload[..]);
}
other => panic!("expected Success, got {other:?}"),
}
std::fs::remove_file(&path).ok();
}
#[test]
fn empty_deque_pop_returns_empty() {
let path = temp_path("empty_pop");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
assert!(matches!(d.pop(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn empty_deque_steal_returns_empty() {
let path = temp_path("empty_steal");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
assert!(matches!(d.steal(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn snapshot_size_tracks_push_pop() {
let path = temp_path("snapshot");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
let (t, b, sz) = d.snapshot_size();
assert_eq!((t, b, sz), (0, 0, 0));
d.push(dummy_slot(1, 0)).expect("push 1");
d.push(dummy_slot(2, 0)).expect("push 2");
let (_, _, sz) = d.snapshot_size();
assert_eq!(sz, 2);
d.pop();
let (_, _, sz) = d.snapshot_size();
assert_eq!(sz, 1);
std::fs::remove_file(&path).ok();
}
#[test]
fn prefetch_for_steal_is_safe_on_empty_deque() {
let path = temp_path("prefetch_empty");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
d.prefetch_for_steal();
d.prefetch_for_steal();
std::fs::remove_file(&path).ok();
}
#[test]
fn prefetch_for_steal_does_not_disturb_state() {
let path = temp_path("prefetch_no_disturb");
let d = MmfChaseLevDeque::create(&path, 8).expect("create");
d.push(dummy_slot(1, 0)).expect("push 1");
d.push(dummy_slot(2, 0)).expect("push 2");
let (t0, b0, sz0) = d.snapshot_size();
for _ in 0..16 {
d.prefetch_for_steal();
}
let (t1, b1, sz1) = d.snapshot_size();
assert_eq!((t0, b0, sz0), (t1, b1, sz1),
"prefetch_for_steal must be observable-state-neutral");
std::fs::remove_file(&path).ok();
}
#[test]
fn prefetch_followed_by_steal_returns_same_slot() {
let path = temp_path("prefetch_then_steal");
let d = MmfChaseLevDeque::create(&path, 4).expect("create");
d.push(dummy_slot(0xAA, 0)).expect("push");
d.prefetch_for_steal();
match d.steal() {
Steal::Success(s) => assert_eq!(s.closure_id, 0xAA),
other => panic!("expected Success, got {other:?}"),
}
std::fs::remove_file(&path).ok();
}
#[test]
fn close_owner_zeros_pid_and_advances_epoch() {
let path = temp_path("close_owner");
let d = MmfChaseLevDeque::create(&path, 2).expect("create");
assert_eq!(d.owner_pid(), std::process::id() as u64);
assert_eq!(d.epoch(), 0);
d.close_owner();
assert_eq!(d.owner_pid(), 0);
assert_eq!(d.epoch(), 1);
std::fs::remove_file(&path).ok();
}
#[test]
fn owner_push_with_concurrent_thieves_no_double_take() {
let path = temp_path("concurrent_no_double_take");
let d = Arc::new(MmfChaseLevDeque::create(&path, 64).expect("create"));
let n = 5_000usize;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let mut thieves = Vec::new();
for _ in 0..2 {
let d = Arc::clone(&d);
let consumed = Arc::clone(&consumed);
let sum = Arc::clone(&sum);
thieves.push(thread::spawn(move || {
while consumed.load(O::Relaxed) < n {
match d.steal() {
Steal::Success(slot) => {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(slot.closure_id as usize, O::Relaxed);
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
}));
}
for i in 0..n {
loop {
match d.push(dummy_slot(i as u32, 0)) {
Ok(()) => break,
Err(PushError::Full) => {
if let Steal::Success(slot) = d.pop() {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(slot.closure_id as usize, O::Relaxed);
}
}
Err(other) => panic!("unexpected: {other:?}"),
}
}
}
while consumed.load(O::Relaxed) < n {
match d.pop() {
Steal::Success(slot) => {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(slot.closure_id as usize, O::Relaxed);
}
Steal::Empty => std::thread::yield_now(),
Steal::Retry => std::thread::yield_now(),
}
}
for h in thieves {
h.join().expect("thief joined");
}
let expected: usize = (0..n).sum();
assert_eq!(sum.load(O::Relaxed), expected,
"sum invariant violated: each slot should be consumed exactly once");
assert_eq!(consumed.load(O::Relaxed), n);
std::fs::remove_file(&path).ok();
}
}