#![allow(clippy::missing_errors_doc)]
use std::fs::{File, OpenOptions};
use std::io;
use std::path::Path;
use std::sync::atomic::{AtomicI64, AtomicU64, Ordering};
use memmap2::{MmapMut, MmapOptions};
use super::khpd::LineItem;
pub const KHL_MMF_MAGIC: u64 = 0x464B_484C_0000_0001;
pub const KHL_MMF_SLOT_SIZE: usize = 64;
pub const KHL_MMF_LINE_ITEMS: usize = 3;
#[repr(C, align(64))]
pub struct KhlMmfHeader {
pub magic: u64,
pub capacity: u64,
pub owner_pid: AtomicU64,
pub epoch: AtomicU64,
pub _pad_meta: [u8; 24],
pub bottom: AtomicI64,
pub _pad_bottom: [u8; 56],
pub head: AtomicI64,
pub _pad_head: [u8; 56],
}
#[repr(C, align(64))]
pub struct KhlMmfSlot {
pub seq: AtomicU64,
pub n_items: u8,
pub _pad: [u8; 7],
pub items: [LineItem; KHL_MMF_LINE_ITEMS],
}
pub const fn khl_mmf_file_size(capacity: usize) -> usize {
std::mem::size_of::<KhlMmfHeader>() + capacity * KHL_MMF_SLOT_SIZE
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PublishError {
TooManyItems,
}
#[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: u8,
pub items: [LineItem; KHL_MMF_LINE_ITEMS],
}
pub struct MmfKhlDeque {
_file: File,
mmap: MmapMut,
capacity: usize,
capacity_mask: i64,
}
unsafe impl Send for MmfKhlDeque {}
unsafe impl Sync for MmfKhlDeque {}
impl MmfKhlDeque {
pub fn create<P: AsRef<Path>>(path: P, capacity: usize) -> io::Result<Self> {
let capacity = capacity.max(2).next_power_of_two();
let size = khl_mmf_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 KhlMmfHeader;
unsafe {
(*header_ptr).magic = KHL_MMF_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).bottom = AtomicI64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_bottom.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::<KhlMmfHeader>();
unsafe {
std::ptr::write_bytes(
mmap.as_mut_ptr().add(slots_start),
0,
capacity * KHL_MMF_SLOT_SIZE,
);
}
for i in 0..capacity {
let slot_off = slots_start + i * KHL_MMF_SLOT_SIZE;
unsafe {
let seq_ptr = mmap.as_mut_ptr().add(slot_off) as *mut AtomicU64;
(*seq_ptr).store(i as u64, Ordering::Relaxed);
}
}
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::<KhlMmfHeader>() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"khl-mmf file too small to contain header",
));
}
let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
let header_ptr = mmap.as_ptr() as *const KhlMmfHeader;
let (magic, capacity) = unsafe {
((*header_ptr).magic, (*header_ptr).capacity as usize)
};
if magic != KHL_MMF_MAGIC {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("khl-mmf magic mismatch: got {magic:#x}, want {KHL_MMF_MAGIC:#x}"),
));
}
if !capacity.is_power_of_two() || capacity < 2 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("khl-mmf capacity {capacity} is not a power of two >= 2"),
));
}
if size < khl_mmf_file_size(capacity) {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("khl-mmf file size {size} below expected {}",
khl_mmf_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) -> &KhlMmfHeader {
unsafe { &*(self.mmap.as_ptr() as *const KhlMmfHeader) }
}
fn slot_ptr(&self, idx: i64) -> *mut KhlMmfSlot {
let slot_idx = (idx & self.capacity_mask) as usize;
let off = std::mem::size_of::<KhlMmfHeader>() + slot_idx * KHL_MMF_SLOT_SIZE;
unsafe { self.mmap.as_ptr().add(off) as *mut KhlMmfSlot }
}
pub fn snapshot_size(&self) -> (i64, i64, i64) {
let h = self.header();
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
(t, b, b - t)
}
pub fn publish(
&self,
n_items: u8,
items: [LineItem; KHL_MMF_LINE_ITEMS],
) -> Result<(), PublishError> {
if n_items as usize > KHL_MMF_LINE_ITEMS {
return Err(PublishError::TooManyItems);
}
let h = self.header();
let b = h.bottom.load(Ordering::Relaxed);
let slot = self.slot_ptr(b);
let slot_ref = unsafe { &*slot };
let mut spins: u32 = 0;
while slot_ref.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 {
(*slot).n_items = n_items;
(*slot).items = items;
}
slot_ref.seq.store((b as u64) + 1, Ordering::Release);
h.bottom.store(b + 1, Ordering::Relaxed);
Ok(())
}
pub fn pop(&self) -> Steal {
self.steal_or_pop()
}
pub fn steal(&self) -> Steal {
self.steal_or_pop()
}
fn steal_or_pop(&self) -> Steal {
let h = self.header();
let t = h.head.load(Ordering::Acquire);
let b = h.bottom.load(Ordering::Acquire);
if t >= b {
return Steal::Empty;
}
if h.head
.compare_exchange(t, t + 1, Ordering::Acquire, Ordering::Relaxed)
.is_err()
{
return Steal::Retry;
}
let slot = self.slot_ptr(t);
let slot_ref = unsafe { &*slot };
let mut spins: u32 = 0;
while slot_ref.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 n_items = unsafe { (*slot).n_items };
let items = unsafe { (*slot).items };
slot_ref.seq.store(
(t as u64) + (self.capacity as u64),
Ordering::Release,
);
Steal::Success(StealResult { n_items, items })
}
pub fn flush(&self) -> io::Result<()> {
self.mmap.flush()
}
#[inline]
pub fn prefetch_for_steal(&self) {
let t = self.header().head.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);
}
}
}
#[inline]
pub fn movdir64b_available() -> bool {
#[cfg(target_arch = "x86_64")]
{
use std::sync::OnceLock;
static CACHE: OnceLock<bool> = OnceLock::new();
*CACHE.get_or_init(|| {
let res = std::arch::x86_64::__cpuid_count(7, 0);
(res.ecx & (1 << 28)) != 0
})
}
#[cfg(not(target_arch = "x86_64"))]
{
false
}
}
#[cfg(target_arch = "x86_64")]
#[inline]
pub unsafe fn movdir64b(dst: *mut u8, src: *const u8) {
unsafe {
core::arch::asm!(
"movdir64b {dst}, [{src}]",
dst = in(reg) dst,
src = in(reg) src,
options(nostack, preserves_flags),
);
}
}
#[cfg(not(target_arch = "x86_64"))]
#[inline]
#[allow(clippy::missing_safety_doc)]
pub unsafe fn movdir64b(_dst: *mut u8, _src: *const u8) {
unreachable!("movdir64b not supported on this target");
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::AtomicUsize;
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_khl_mmf_{pid}_{nonce}_{name}.bin"));
p
}
fn make_item(closure_id: u32, args: &[u8]) -> LineItem {
LineItem::new(closure_id, 0, args).expect("build item")
}
fn batch(items: Vec<LineItem>) -> (u8, [LineItem; KHL_MMF_LINE_ITEMS]) {
let n = items.len();
let mut arr = [LineItem { closure_id: 0, latch_offset: 0, args_inline: [0u8; 8] }; KHL_MMF_LINE_ITEMS];
for (i, item) in items.into_iter().enumerate() {
arr[i] = item;
}
(n as u8, arr)
}
#[test]
fn slot_is_exactly_one_cache_line() {
assert_eq!(core::mem::size_of::<KhlMmfSlot>(), 64,
"KhlMmfSlot must be exactly 64 bytes");
assert_eq!(core::mem::align_of::<KhlMmfSlot>(), 64);
}
#[test]
fn create_then_open_round_trips_header() {
let path = temp_path("create_open");
let _d = MmfKhlDeque::create(&path, 8).expect("create");
let opened = MmfKhlDeque::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 = MmfKhlDeque::open(&path);
assert!(r.is_err(), "open must reject bad-magic file");
std::fs::remove_file(&path).ok();
}
#[test]
fn publish_then_steal_fifo() {
let path = temp_path("publish_steal_fifo");
let d = MmfKhlDeque::create(&path, 4).expect("create");
let (n1, b1) = batch(vec![make_item(1, b"a")]);
d.publish(n1, b1).expect("p1");
let (n2, b2) = batch(vec![make_item(2, b"b"), make_item(3, b"c")]);
d.publish(n2, b2).expect("p2");
match d.steal() {
Steal::Success(r) => {
assert_eq!(r.n_items, 1);
assert_eq!(r.items[0].closure_id, 1);
}
other => panic!("expected Success, got {other:?}"),
}
match d.steal() {
Steal::Success(r) => {
assert_eq!(r.n_items, 2);
assert_eq!(r.items[0].closure_id, 2);
assert_eq!(r.items[1].closure_id, 3);
}
other => panic!("expected Success, got {other:?}"),
}
assert!(matches!(d.steal(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn snapshot_size_tracks_publish_steal() {
let path = temp_path("snapshot");
let d = MmfKhlDeque::create(&path, 4).expect("create");
let (t0, b0, sz0) = d.snapshot_size();
assert_eq!((t0, b0, sz0), (0, 0, 0));
let (n1, b1) = batch(vec![make_item(1, b"")]);
d.publish(n1, b1).expect("p1");
let (n2, b2) = batch(vec![make_item(2, b"")]);
d.publish(n2, b2).expect("p2");
let (_, _, sz) = d.snapshot_size();
assert_eq!(sz, 2);
d.steal();
let (_, _, sz) = d.snapshot_size();
assert_eq!(sz, 1);
std::fs::remove_file(&path).ok();
}
#[test]
fn empty_steal_returns_empty() {
let path = temp_path("empty_steal");
let d = MmfKhlDeque::create(&path, 4).expect("create");
assert!(matches!(d.steal(), Steal::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn prefetch_for_steal_is_safe_on_empty() {
let path = temp_path("prefetch_empty");
let d = MmfKhlDeque::create(&path, 4).expect("create");
d.prefetch_for_steal();
d.prefetch_for_steal();
std::fs::remove_file(&path).ok();
}
#[test]
fn close_owner_zeros_pid_and_advances_epoch() {
let path = temp_path("close_owner");
let d = MmfKhlDeque::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 movdir64b_detection_does_not_fault() {
let available = movdir64b_available();
std::hint::black_box(available);
}
#[test]
fn concurrent_owner_publish_and_thieves_no_double_take() {
let path = temp_path("concurrent_no_double_take");
let d = Arc::new(MmfKhlDeque::create(&path, 64).expect("create"));
let n_batches = 500;
let consumed = Arc::new(AtomicUsize::new(0));
let mut thieves = Vec::new();
for _ in 0..4 {
let d = Arc::clone(&d);
let consumed = Arc::clone(&consumed);
thieves.push(thread::spawn(move || {
let target = n_batches * 3;
while consumed.load(Ordering::Relaxed) < target {
match d.steal() {
Steal::Success(r) => {
consumed.fetch_add(r.n_items as usize, Ordering::Relaxed);
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
}));
}
for i in 0..n_batches as u32 {
let (n, b) = batch(vec![
make_item(i, b""),
make_item(i, b""),
make_item(i, b""),
]);
d.publish(n, b).expect("publish");
}
for h in thieves {
h.join().expect("thief joined");
}
let total = n_batches * 3;
assert_eq!(consumed.load(Ordering::Relaxed), total,
"each item must be consumed exactly once");
std::fs::remove_file(&path).ok();
}
}