#![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 KHPD_MAGIC: u64 = 0x464B_4850_0000_0001;
pub const KHPD_LINE_SIZE: usize = 64;
pub const LINE_ITEMS: usize = 3;
pub const KHPD_ARGS_INLINE_BYTES: usize = 8;
const STATE_EMPTY: u64 = 0;
const CLAIM_BIT: u64 = 1;
#[repr(C, align(64))]
pub struct KhpdHeader {
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(8))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct LineItem {
pub closure_id: u32,
pub latch_offset: u32,
pub args_inline: [u8; KHPD_ARGS_INLINE_BYTES],
}
impl LineItem {
pub fn new(closure_id: u32, latch_offset: u32, args: &[u8]) -> Result<Self, PushError> {
if args.len() > KHPD_ARGS_INLINE_BYTES {
return Err(PushError::PayloadTooLarge);
}
let mut item = Self {
closure_id,
latch_offset,
args_inline: [0u8; KHPD_ARGS_INLINE_BYTES],
};
item.args_inline[..args.len()].copy_from_slice(args);
Ok(item)
}
pub fn args(&self) -> &[u8] {
&self.args_inline
}
}
#[repr(C, align(64))]
pub struct PublicationLine {
pub state: AtomicU64,
pub items: [LineItem; LINE_ITEMS],
pub _pad: [u8; 8],
}
pub const fn khpd_file_size(capacity: usize) -> usize {
std::mem::size_of::<KhpdHeader>() + capacity * KHPD_LINE_SIZE
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PushError {
Full,
TooManyItems,
PayloadTooLarge,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Steal {
Success(StealResult),
Empty,
Retry,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct StealResult {
pub n_items: usize,
pub items: [LineItem; LINE_ITEMS],
}
pub struct KhpdDeque {
_file: File,
mmap: MmapMut,
capacity: usize,
capacity_mask: i64,
pending: StagingTable<LineItem>,
}
unsafe impl Send for KhpdDeque {}
unsafe impl Sync for KhpdDeque {}
impl KhpdDeque {
pub fn create<P: AsRef<Path>>(path: P, capacity: usize) -> io::Result<Self> {
let capacity = capacity.max(2).next_power_of_two();
let size = khpd_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 KhpdHeader;
unsafe {
(*header_ptr).magic = KHPD_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 lines_start = std::mem::size_of::<KhpdHeader>();
unsafe {
std::ptr::write_bytes(
mmap.as_mut_ptr().add(lines_start),
0,
capacity * KHPD_LINE_SIZE,
);
}
mmap.flush()?;
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
pending: StagingTable::new(),
})
}
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::<KhpdHeader>() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"khpd file too small",
));
}
let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
let header_ptr = mmap.as_ptr() as *const KhpdHeader;
let (magic, capacity) =
unsafe { ((*header_ptr).magic, (*header_ptr).capacity as usize) };
if magic != KHPD_MAGIC {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("khpd magic mismatch {magic:#x}"),
));
}
if !capacity.is_power_of_two() || capacity < 2 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("khpd capacity {capacity} not pow2 >= 2"),
));
}
if size < khpd_file_size(capacity) {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!(
"khpd file size {size} below expected {}",
khpd_file_size(capacity)
),
));
}
Ok(Self {
_file: file,
mmap,
capacity,
capacity_mask: (capacity as i64) - 1,
pending: StagingTable::new(),
})
}
pub fn capacity(&self) -> usize {
self.capacity
}
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) -> &KhpdHeader {
unsafe { &*(self.mmap.as_ptr() as *const KhpdHeader) }
}
fn line_ptr(&self, idx: i64) -> *mut PublicationLine {
let line_idx = (idx & self.capacity_mask) as usize;
let off = std::mem::size_of::<KhpdHeader>() + line_idx * KHPD_LINE_SIZE;
unsafe { self.mmap.as_ptr().add(off) as *mut PublicationLine }
}
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.pending.staged_total())
}
pub fn stage(&self, item: LineItem) -> Result<usize, PushError> {
Ok(self.pending.with_mine(|buffer| {
buffer.push(item);
buffer.len()
}))
}
pub fn publish(&self) -> Result<usize, PushError> {
self.pending.with_mine(|buffer| self.publish_staged(buffer))
}
fn publish_staged(&self, p: &mut Vec<LineItem>) -> Result<usize, PushError> {
if p.is_empty() {
return Ok(0);
}
let total = p.len();
let n_lines = total.div_ceil(LINE_ITEMS);
let h = self.header();
let mut tail_snap = h.tail.load(Ordering::Relaxed);
let base = loop {
let head_snap = h.head.load(Ordering::Acquire);
if (tail_snap - head_snap + n_lines as i64) > self.capacity as i64 {
return Err(PushError::Full);
}
match h.tail.compare_exchange_weak(
tail_snap,
tail_snap + n_lines as i64,
Ordering::AcqRel,
Ordering::Relaxed,
) {
Ok(claimed) => break claimed,
Err(current) => tail_snap = current,
}
};
let mut item_iter = p.drain(..);
for line_i in 0..n_lines {
let idx = base + line_i as i64;
let line = self.line_ptr(idx);
unsafe {
loop {
let st = (*line).state.load(Ordering::Acquire);
if st == STATE_EMPTY {
break;
}
std::hint::spin_loop();
}
let mut n_filled = 0usize;
for i in 0..LINE_ITEMS {
match item_iter.next() {
Some(item) => {
(*line).items[i] = item;
n_filled += 1;
}
None => break,
}
}
let new_state =
((idx as u64) << 32) | ((n_filled as u64) << 16) | CLAIM_BIT;
(*line).state.store(new_state, Ordering::Release);
}
}
Ok(n_lines)
}
pub fn steal_line(&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 line = self.line_ptr(head);
let state = unsafe { (*line).state.load(Ordering::Acquire) };
let expected_epoch = (head as u64) << 32;
if state & 0xFFFF_FFFF_0000_0000 != expected_epoch {
return Steal::Retry;
}
if state & CLAIM_BIT == 0 {
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 {
let n_items = ((state >> 16) & 0xFFFF) as usize;
let n_items = n_items.min(LINE_ITEMS);
StealResult {
n_items,
items: (*line).items,
}
};
unsafe {
(*line).state.store(STATE_EMPTY, 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_khpd_{pid}_{nonce}_{name}.bin"));
p
}
fn item(id: u32) -> LineItem {
LineItem::new(id, u32::MAX, &id.to_le_bytes()).expect("item")
}
#[test]
fn create_open_round_trips_header() {
let path = temp_path("create_open");
let _d = KhpdDeque::create(&path, 8).expect("create");
let o = KhpdDeque::open(&path).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("badmagic");
std::fs::write(&path, vec![0u8; 8192]).expect("seed");
assert!(KhpdDeque::open(&path).is_err());
std::fs::remove_file(&path).ok();
}
#[test]
fn stage_then_publish_writes_one_line() {
let path = temp_path("stage_publish");
let d = KhpdDeque::create(&path, 4).expect("create");
d.stage(item(1)).expect("stage 1");
d.stage(item(2)).expect("stage 2");
let lines = d.publish().expect("publish");
assert_eq!(lines, 1);
let (_, tail, sz, pending) = d.snapshot_size();
assert_eq!(tail, 1);
assert_eq!(sz, 1);
assert_eq!(pending, 0);
std::fs::remove_file(&path).ok();
}
#[test]
fn publish_spans_multiple_lines() {
let path = temp_path("multi_line");
let d = KhpdDeque::create(&path, 4).expect("create");
for i in 1..=7u32 {
d.stage(item(i)).expect("stage");
}
let lines = d.publish().expect("publish");
assert_eq!(lines, 3);
let (_, tail, sz, _) = d.snapshot_size();
assert_eq!(tail, 3);
assert_eq!(sz, 3);
std::fs::remove_file(&path).ok();
}
#[test]
fn steal_returns_items_in_publication_order() {
let path = temp_path("fifo");
let d = KhpdDeque::create(&path, 4).expect("create");
for i in 1..=5u32 {
d.stage(item(i)).expect("stage");
}
d.publish().expect("publish");
loop {
match d.steal_line() {
Steal::Success(r) => {
assert_eq!(r.n_items, 3);
assert_eq!(r.items[0].closure_id, 1);
assert_eq!(r.items[1].closure_id, 2);
assert_eq!(r.items[2].closure_id, 3);
break;
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
loop {
match d.steal_line() {
Steal::Success(r) => {
assert_eq!(r.n_items, 2);
assert_eq!(r.items[0].closure_id, 4);
assert_eq!(r.items[1].closure_id, 5);
break;
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
loop {
match d.steal_line() {
Steal::Empty => break,
Steal::Retry => continue,
Steal::Success(_) => panic!("unexpected success after drain"),
}
}
std::fs::remove_file(&path).ok();
}
#[test]
fn oversize_args_rejected() {
let big = vec![0u8; KHPD_ARGS_INLINE_BYTES + 1];
let err = LineItem::new(0, 0, &big).expect_err("oversize");
assert_eq!(err, PushError::PayloadTooLarge);
}
#[test]
fn ring_full_at_capacity_returns_full() {
let path = temp_path("full");
let d = KhpdDeque::create(&path, 2).expect("create");
for i in 1..=6u32 {
d.stage(item(i)).expect("stage");
}
d.publish().expect("publish 2 lines");
d.stage(item(7)).expect("stage 7");
let err = d.publish().expect_err("publish past capacity");
assert_eq!(err, PushError::Full);
std::fs::remove_file(&path).ok();
}
#[test]
fn close_owner_zeros_pid_and_advances_epoch() {
let path = temp_path("close");
let d = KhpdDeque::create(&path, 2).expect("create");
let before = d.header().epoch.load(O::Acquire);
d.close_owner();
assert_eq!(d.owner_pid(), 0);
assert_eq!(d.header().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(KhpdDeque::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_line() {
Steal::Success(r) => {
for i in 0..r.n_items {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(r.items[i].closure_id as usize, O::Relaxed);
}
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
}));
}
let mut pushed = 0usize;
while pushed < n {
let want = LINE_ITEMS.min(n - pushed);
for _ in 0..want {
d.stage(item(pushed as u32)).expect("stage");
pushed += 1;
}
loop {
match d.publish() {
Ok(_) => break,
Err(PushError::Full) => {
std::thread::yield_now();
}
Err(other) => panic!("publish: {other:?}"),
}
}
}
for t in thieves {
t.join().expect("thief");
}
let expected: usize = (0..n).sum();
assert_eq!(
sum.load(O::Relaxed),
expected,
"stress sum mismatch (expected every item consumed exactly once)"
);
std::fs::remove_file(&path).ok();
}
}