#![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};
use super::stager::StagingTable;
pub const LOH_MAGIC: u64 = 0x464C_4C4F_0000_0001;
pub const LOH_SLOT_SIZE: usize = 64;
pub const LOH_ARGS_INLINE_BYTES: usize = 40;
#[repr(C, align(64))]
pub struct LohHeader {
pub magic: u64,
pub capacity: u64,
pub owner_pid: AtomicU64,
pub epoch: AtomicU64,
pub _pad_meta: [u8; 24],
pub tail: AtomicI64,
pub _pad_tail: [u8; 56],
pub head: AtomicI64,
pub _pad_head: [u8; 56],
}
#[repr(C, align(64))]
pub struct LcrqJobSlot {
pub sequence: AtomicI64,
pub closure_id: u32,
pub args_len: u32,
pub latch_offset: u32,
pub reserved_tag: u32,
pub args_inline: [u8; LOH_ARGS_INLINE_BYTES],
}
#[derive(Debug, Clone, Copy)]
pub struct LohLifoEntry {
pub closure_id: u32,
pub args_len: u32,
pub latch_offset: u32,
pub reserved_tag: u32,
pub args_inline: [u8; LOH_ARGS_INLINE_BYTES],
}
impl LohLifoEntry {
pub fn new(closure_id: u32, latch_offset: u32, args: &[u8]) -> Result<Self, PushError> {
if args.len() > LOH_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; LOH_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 loh_file_size(capacity: usize) -> usize {
std::mem::size_of::<LohHeader>() + capacity * LOH_SLOT_SIZE
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PushError {
Full,
PayloadTooLarge,
LifoFull,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Steal {
Success(StealResult),
Empty,
Retry,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct StealResult {
pub closure_id: u32,
pub args_len: u32,
pub latch_offset: u32,
pub reserved_tag: u32,
pub args_inline: [u8; LOH_ARGS_INLINE_BYTES],
}
impl StealResult {
pub fn args(&self) -> &[u8] {
&self.args_inline[..self.args_len as usize]
}
}
pub const DEFAULT_LIFO_CAP: usize = 256;
pub struct LohDeque {
_file: File,
mmap: MmapMut,
capacity: usize,
capacity_mask: i64,
flush_threshold: usize,
lifo_cap: usize,
local_lifo: StagingTable<LohLifoEntry>,
}
unsafe impl Send for LohDeque {}
unsafe impl Sync for LohDeque {}
impl LohDeque {
pub fn create<P: AsRef<Path>>(
path: P,
capacity: usize,
flush_threshold: usize,
) -> io::Result<Self> {
let capacity = capacity.max(2).next_power_of_two();
let size = loh_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 LohHeader;
unsafe {
(*header_ptr).magic = LOH_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).tail = AtomicI64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_tail.as_mut_ptr(), 0, 56);
(*header_ptr).head = AtomicI64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_head.as_mut_ptr(), 0, 56);
}
let slots_start = std::mem::size_of::<LohHeader>();
for i in 0..capacity {
let off = slots_start + i * LOH_SLOT_SIZE;
let slot_ptr = unsafe { mmap.as_mut_ptr().add(off) as *mut LcrqJobSlot };
unsafe {
(*slot_ptr).sequence = AtomicI64::new(i as i64);
(*slot_ptr).closure_id = 0;
(*slot_ptr).args_len = 0;
(*slot_ptr).latch_offset = u32::MAX;
(*slot_ptr).reserved_tag = 0;
std::ptr::write_bytes(
(*slot_ptr).args_inline.as_mut_ptr(),
0,
LOH_ARGS_INLINE_BYTES,
);
}
}
mmap.flush()?;
let flush_threshold = flush_threshold.max(1);
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
flush_threshold,
lifo_cap: DEFAULT_LIFO_CAP,
local_lifo: StagingTable::new(),
})
}
pub fn open<P: AsRef<Path>>(path: P, flush_threshold: usize) -> 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::<LohHeader>() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"loh 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 LohHeader;
let (magic, capacity) = unsafe { ((*header_ptr).magic, (*header_ptr).capacity as usize) };
if magic != LOH_MAGIC {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("loh magic mismatch: got {magic:#x}, want {LOH_MAGIC:#x}"),
));
}
if !capacity.is_power_of_two() || capacity < 2 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("loh capacity {capacity} is not a power of two >= 2"),
));
}
if size < loh_file_size(capacity) {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!(
"loh file size {size} below expected {}",
loh_file_size(capacity)
),
));
}
let flush_threshold = flush_threshold.max(1);
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
flush_threshold,
lifo_cap: DEFAULT_LIFO_CAP,
local_lifo: StagingTable::new(),
})
}
pub fn capacity(&self) -> usize {
self.capacity
}
pub fn flush_threshold(&self) -> usize {
self.flush_threshold
}
pub fn owner_pid(&self) -> u64 {
self.header().owner_pid.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) -> &LohHeader {
unsafe { &*(self.mmap.as_ptr() as *const LohHeader) }
}
fn slot_ptr(&self, idx: i64) -> *mut LcrqJobSlot {
let slot_idx = (idx & self.capacity_mask) as usize;
let off = std::mem::size_of::<LohHeader>() + slot_idx * LOH_SLOT_SIZE;
unsafe { self.mmap.as_ptr().add(off) as *mut LcrqJobSlot }
}
pub fn snapshot_size(&self) -> (i64, i64, i64, usize) {
let h = self.header();
let head = h.head.load(Ordering::Acquire);
let tail = h.tail.load(Ordering::Acquire);
(head, tail, tail - head, self.local_lifo.staged_total())
}
pub fn push(&self, entry: LohLifoEntry) -> Result<(), PushError> {
self.local_lifo.with_mine(|lifo| {
if lifo.len() >= self.lifo_cap {
return Err(PushError::LifoFull);
}
lifo.push(entry);
if lifo.len() >= self.flush_threshold {
if let Err(e) = self.flush_staged(lifo) {
lifo.pop();
return Err(e);
}
}
Ok(())
})
}
pub fn flush(&self) -> Result<usize, PushError> {
self.local_lifo.with_mine(|lifo| self.flush_staged(lifo))
}
fn flush_staged(&self, lifo: &mut Vec<LohLifoEntry>) -> Result<usize, PushError> {
let n = lifo.len();
if n == 0 {
return Ok(0);
}
let h = self.header();
let head_snapshot = h.head.load(Ordering::Acquire);
let tail_snapshot = h.tail.load(Ordering::Relaxed);
if (tail_snapshot - head_snapshot + n as i64) > self.capacity as i64 {
return Err(PushError::Full);
}
let base = h.tail.fetch_add(n as i64, Ordering::AcqRel);
for (i, entry) in lifo.drain(..).enumerate() {
let idx = base + i as i64;
let slot = self.slot_ptr(idx);
unsafe {
loop {
let seq = (*slot).sequence.load(Ordering::Acquire);
let diff = seq - idx;
if diff == 0 {
break;
}
if diff < 0 {
std::hint::spin_loop();
continue;
}
panic!(
"LOH producer protocol violation: slot[{}] seq={} ahead of idx={}",
idx & self.capacity_mask,
seq,
idx
);
}
(*slot).closure_id = entry.closure_id;
(*slot).args_len = entry.args_len;
(*slot).latch_offset = entry.latch_offset;
(*slot).reserved_tag = entry.reserved_tag;
std::ptr::write_bytes(
(*slot).args_inline.as_mut_ptr(),
0,
LOH_ARGS_INLINE_BYTES,
);
std::ptr::copy_nonoverlapping(
entry.args_inline.as_ptr(),
(*slot).args_inline.as_mut_ptr(),
entry.args_len as usize,
);
(*slot).sequence.store(idx + 1, Ordering::Release);
}
}
Ok(n)
}
pub fn pop_local(&self) -> Option<LohLifoEntry> {
self.local_lifo.with_mine(|lifo| lifo.pop())
}
pub fn steal(&self) -> Steal {
let h = self.header();
let head = h.head.load(Ordering::Acquire);
fence(Ordering::SeqCst);
let tail = h.tail.load(Ordering::Acquire);
if head >= tail {
return Steal::Empty;
}
let slot = self.slot_ptr(head);
let seq = unsafe { (*slot).sequence.load(Ordering::Acquire) };
if seq != head + 1 {
return Steal::Retry;
}
let won = h
.head
.compare_exchange(head, head + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
if !won {
return Steal::Retry;
}
let result = unsafe {
StealResult {
closure_id: (*slot).closure_id,
args_len: (*slot).args_len,
latch_offset: (*slot).latch_offset,
reserved_tag: (*slot).reserved_tag,
args_inline: (*slot).args_inline,
}
};
unsafe {
(*slot)
.sequence
.store(head + self.capacity as i64, Ordering::Release);
}
Steal::Success(result)
}
pub fn flush_to_disk(&self) -> io::Result<()> {
self.mmap.flush()
}
}
#[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_loh_{pid}_{nonce}_{name}.bin"));
p
}
fn entry(id: u32, args_len: u8) -> LohLifoEntry {
let args: Vec<u8> = (0..args_len).collect();
LohLifoEntry::new(id, u32::MAX, &args).expect("build entry")
}
#[test]
fn create_then_open_round_trips_header() {
let path = temp_path("create_open");
let _d = LohDeque::create(&path, 8, 4).expect("create");
let o = LohDeque::open(&path, 4).expect("open");
assert_eq!(o.capacity(), 8);
assert_eq!(o.owner_pid(), std::process::id() as u64);
std::fs::remove_file(&path).ok();
}
#[test]
fn open_rejects_bad_magic() {
let path = temp_path("bad_magic");
std::fs::write(&path, vec![0xCDu8; 8192]).expect("seed");
let r = LohDeque::open(&path, 4);
assert!(r.is_err());
std::fs::remove_file(&path).ok();
}
#[test]
fn push_and_explicit_flush_migrates() {
let path = temp_path("flush");
let d = LohDeque::create(&path, 8, usize::MAX).expect("create");
for i in 0..3u32 {
d.push(entry(i, 1)).expect("push");
}
let (head, tail, sz, lifo_len) = d.snapshot_size();
assert_eq!(head, 0);
assert_eq!(tail, 0);
assert_eq!(sz, 0);
assert_eq!(lifo_len, 3);
let n = d.flush().expect("flush");
assert_eq!(n, 3);
let (_, tail, sz, lifo_len) = d.snapshot_size();
assert_eq!(tail, 3);
assert_eq!(sz, 3);
assert_eq!(lifo_len, 0);
std::fs::remove_file(&path).ok();
}
#[test]
fn push_auto_flushes_at_threshold() {
let path = temp_path("autoflush");
let d = LohDeque::create(&path, 8, 4).expect("create");
for i in 0..4u32 {
d.push(entry(i, 0)).expect("push");
}
let (_, tail, sz, lifo_len) = d.snapshot_size();
assert_eq!(tail, 4);
assert_eq!(sz, 4);
assert_eq!(lifo_len, 0);
std::fs::remove_file(&path).ok();
}
#[test]
fn steal_drains_in_fifo_order_after_flush() {
let path = temp_path("fifo");
let d = LohDeque::create(&path, 8, usize::MAX).expect("create");
for i in 1..=3u32 {
d.push(entry(i, 0)).expect("push");
}
d.flush().expect("flush");
for expected in 1..=3u32 {
loop {
match d.steal() {
Steal::Success(slot) => {
assert_eq!(slot.closure_id, expected);
break;
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
}
assert!(matches!(d.steal(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn pop_local_drains_lifo_in_lifo_order() {
let path = temp_path("pop_local_lifo");
let d = LohDeque::create(&path, 4, usize::MAX).expect("create");
for i in 1..=3u32 {
d.push(entry(i, 0)).expect("push");
}
for expected in (1..=3u32).rev() {
let e = d.pop_local().expect("pop_local");
assert_eq!(e.closure_id, expected);
}
assert!(d.pop_local().is_none());
std::fs::remove_file(&path).ok();
}
#[test]
fn ring_full_at_capacity() {
let path = temp_path("full");
let d = LohDeque::create(&path, 2, usize::MAX).expect("create");
d.push(entry(1, 0)).expect("push");
d.push(entry(2, 0)).expect("push");
let n = d.flush().expect("flush");
assert_eq!(n, 2);
d.push(entry(3, 0)).expect("push to lifo");
let err = d.flush().expect_err("flush past capacity");
assert_eq!(err, PushError::Full);
std::fs::remove_file(&path).ok();
}
#[test]
fn oversize_args_rejected() {
let big = vec![0u8; LOH_ARGS_INLINE_BYTES + 1];
let err = LohLifoEntry::new(0, 0, &big).expect_err("oversize");
assert_eq!(err, PushError::PayloadTooLarge);
}
#[test]
fn close_owner_zeros_pid_and_advances_epoch() {
let path = temp_path("close");
let d = LohDeque::create(&path, 2, 1).expect("create");
assert_eq!(d.owner_pid(), std::process::id() as u64);
let h = d.header();
let before = h.epoch.load(O::Acquire);
d.close_owner();
assert_eq!(d.owner_pid(), 0);
assert_eq!(h.epoch.load(O::Acquire), before + 1);
std::fs::remove_file(&path).ok();
}
#[test]
fn concurrent_thieves_no_double_take() {
let path = temp_path("stress");
let d = Arc::new(LohDeque::create(&path, 128, 8).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(entry(i as u32, 0)) {
Ok(()) => break,
Err(PushError::LifoFull) | Err(PushError::Full) => {
std::thread::yield_now();
d.flush().ok();
}
Err(other) => panic!("push: {other:?}"),
}
}
}
while d.flush().is_err() {
std::thread::yield_now();
}
for h in thieves {
h.join().expect("thief");
}
let expected: usize = (0..n).sum();
assert_eq!(sum.load(O::Relaxed), expected, "every slot consumed once");
std::fs::remove_file(&path).ok();
}
}