#![allow(clippy::missing_errors_doc)]
use std::fs::{File, OpenOptions};
use std::io;
use std::path::Path;
use std::sync::atomic::{AtomicU64, Ordering};
use memmap2::{MmapMut, MmapOptions};
use super::khpd::LineItem;
use crate::cpu_info::{has_monitorx, has_waitpkg};
pub const URD_MAGIC: u64 = 0x4655_5244_0000_0001;
pub const URD_MAILBOX_SIZE: usize = 64;
pub const MAILBOX_ITEMS: usize = 3;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum WaitStrategy {
PauseSpin,
Waitpkg,
Monitorx,
}
pub const SPIN_BEFORE_WAIT: u32 = 512;
impl WaitStrategy {
pub fn pick() -> Self {
if has_waitpkg() {
Self::Waitpkg
} else if has_monitorx() {
Self::Monitorx
} else {
Self::PauseSpin
}
}
}
const STATE_EMPTY: u64 = 0;
const CLAIM_READY: u64 = 1;
#[repr(C, align(64))]
pub struct UrdHeader {
pub magic: u64,
pub n_mailboxes: u64,
pub owner_pid: AtomicU64,
pub epoch: AtomicU64,
pub _pad_meta: [u8; 24],
pub rr_cursor: AtomicU64,
pub _pad_rr: [u8; 56],
}
#[repr(C, align(64))]
pub struct Mailbox {
pub state: AtomicU64,
pub items: [LineItem; MAILBOX_ITEMS],
pub _pad: [u8; 8],
}
pub const fn urd_file_size(n_mailboxes: usize) -> usize {
std::mem::size_of::<UrdHeader>() + n_mailboxes * URD_MAILBOX_SIZE
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PublishError {
BadTarget(usize),
TooManyItems,
PayloadTooLarge,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Drain {
Success(DrainResult),
Empty,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DrainResult {
pub n_items: usize,
pub items: [LineItem; MAILBOX_ITEMS],
}
pub struct UrdDeque {
_file: File,
mmap: MmapMut,
n_mailboxes: usize,
wait_strategy: WaitStrategy,
}
unsafe impl Send for UrdDeque {}
unsafe impl Sync for UrdDeque {}
impl UrdDeque {
pub fn create<P: AsRef<Path>>(path: P, n_mailboxes: usize) -> io::Result<Self> {
let n_mailboxes = n_mailboxes.max(1);
let size = urd_file_size(n_mailboxes);
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 UrdHeader;
unsafe {
(*header_ptr).magic = URD_MAGIC;
(*header_ptr).n_mailboxes = n_mailboxes 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).rr_cursor = AtomicU64::new(0);
std::ptr::write_bytes((*header_ptr)._pad_rr.as_mut_ptr(), 0, 56);
}
let mailboxes_start = std::mem::size_of::<UrdHeader>();
unsafe {
std::ptr::write_bytes(
mmap.as_mut_ptr().add(mailboxes_start),
0,
n_mailboxes * URD_MAILBOX_SIZE,
);
}
mmap.flush()?;
let wait_strategy = WaitStrategy::pick();
Ok(Self {
_file: file,
mmap,
n_mailboxes,
wait_strategy,
})
}
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::<UrdHeader>() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"urd file too small",
));
}
let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
let header_ptr = mmap.as_ptr() as *const UrdHeader;
let (magic, n_mailboxes) =
unsafe { ((*header_ptr).magic, (*header_ptr).n_mailboxes as usize) };
if magic != URD_MAGIC {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("urd magic mismatch {magic:#x}"),
));
}
if n_mailboxes == 0 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"urd n_mailboxes must be >= 1",
));
}
if size < urd_file_size(n_mailboxes) {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"urd file size below header expected",
));
}
let wait_strategy = WaitStrategy::pick();
Ok(Self {
_file: file,
mmap,
n_mailboxes,
wait_strategy,
})
}
pub fn n_mailboxes(&self) -> usize {
self.n_mailboxes
}
pub fn wait_strategy(&self) -> WaitStrategy {
self.wait_strategy
}
pub fn set_wait_strategy(&mut self, strategy: WaitStrategy) {
match strategy {
WaitStrategy::Waitpkg => assert!(
has_waitpkg(),
"this host has no WAITPKG, so UMONITOR would be an illegal instruction"
),
WaitStrategy::Monitorx => assert!(
has_monitorx(),
"this host has no MONITORX, so MONITORX would be an illegal instruction"
),
WaitStrategy::PauseSpin => {}
}
self.wait_strategy = strategy;
}
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) -> &UrdHeader {
unsafe { &*(self.mmap.as_ptr() as *const UrdHeader) }
}
fn mailbox_ptr(&self, idx: usize) -> *mut Mailbox {
let off = std::mem::size_of::<UrdHeader>() + idx * URD_MAILBOX_SIZE;
unsafe { self.mmap.as_ptr().add(off) as *mut Mailbox }
}
fn mailbox(&self, idx: usize) -> &Mailbox {
unsafe { &*self.mailbox_ptr(idx) }
}
pub fn publish_to(
&self,
target: usize,
items: &[LineItem],
) -> Result<usize, PublishError> {
if target >= self.n_mailboxes {
return Err(PublishError::BadTarget(target));
}
if items.len() > MAILBOX_ITEMS {
return Err(PublishError::TooManyItems);
}
if items.is_empty() {
return Ok(0);
}
let mb = self.mailbox(target);
loop {
let s = mb.state.load(Ordering::Acquire);
if s == STATE_EMPTY {
break;
}
std::hint::spin_loop();
}
unsafe {
let mb_ptr = self.mailbox_ptr(target);
for (i, item) in items.iter().enumerate() {
(*mb_ptr).items[i] = *item;
}
}
let epoch = self.header().epoch.load(Ordering::Relaxed);
let new_state = (epoch << 32) | ((items.len() as u64) << 16) | CLAIM_READY;
mb.state.store(new_state, Ordering::Release);
Ok(items.len())
}
pub fn publish_round_robin(
&self,
items: &[LineItem],
) -> Result<(usize, usize), PublishError> {
let cursor = self.header().rr_cursor.fetch_add(1, Ordering::Relaxed) as usize;
let target = cursor % self.n_mailboxes;
let n = self.publish_to(target, items)?;
Ok((target, n))
}
pub fn drain_mailbox(&self, mailbox_idx: usize) -> Drain {
if mailbox_idx >= self.n_mailboxes {
return Drain::Empty;
}
let mb = self.mailbox(mailbox_idx);
let s = mb.state.load(Ordering::Acquire);
if s & 0xFFFF != CLAIM_READY {
return Drain::Empty;
}
let n_items = ((s >> 16) & 0xFFFF) as usize;
let n_items = n_items.min(MAILBOX_ITEMS);
let result = unsafe {
DrainResult {
n_items,
items: (*self.mailbox_ptr(mailbox_idx)).items,
}
};
mb.state.store(STATE_EMPTY, Ordering::Release);
Drain::Success(result)
}
pub fn wait_and_drain(&self, mailbox_idx: usize, deadline_tsc: u64) -> Drain {
if mailbox_idx >= self.n_mailboxes {
return Drain::Empty;
}
let mb = self.mailbox(mailbox_idx);
let state_addr = (&raw const mb.state).cast::<u8>();
let mut spins = 0u32;
loop {
let s = mb.state.load(Ordering::Acquire);
if s & 0xFFFF == CLAIM_READY {
break;
}
if spins < SPIN_BEFORE_WAIT {
spins += 1;
std::hint::spin_loop();
continue;
}
match self.wait_strategy {
WaitStrategy::PauseSpin => std::hint::spin_loop(),
WaitStrategy::Waitpkg => {
unsafe { wait_with_waitpkg(state_addr, deadline_tsc) };
}
WaitStrategy::Monitorx => {
unsafe { wait_with_monitorx(state_addr, deadline_tsc) };
}
}
}
self.drain_mailbox(mailbox_idx)
}
pub fn flush_to_disk(&self) -> io::Result<()> {
self.mmap.flush()
}
}
#[cfg(target_arch = "x86_64")]
#[inline(always)]
unsafe fn wait_with_waitpkg(state_addr: *const u8, deadline_tsc: u64) {
use std::arch::asm;
let lo = deadline_tsc as u32;
let hi = (deadline_tsc >> 32) as u32;
unsafe {
asm!(
"umonitor rax",
in("rax") state_addr,
options(nostack, preserves_flags),
);
asm!(
"umwait {hint:e}",
hint = in(reg) 1u32,
in("eax") lo,
in("edx") hi,
options(nostack),
);
}
}
#[cfg(not(target_arch = "x86_64"))]
#[inline(always)]
unsafe fn wait_with_waitpkg(_state_addr: *const u8, _deadline_tsc: u64) {
std::hint::spin_loop();
}
#[cfg(target_arch = "x86_64")]
#[inline(always)]
unsafe fn wait_with_monitorx(state_addr: *const u8, deadline_tsc: u64) {
use std::arch::asm;
let now = unsafe { std::arch::x86_64::_rdtsc() };
let remaining = deadline_tsc.saturating_sub(now).max(1);
let ask = u32::try_from(remaining).unwrap_or(u32::MAX);
unsafe {
asm!(
".byte 0x0f, 0x01, 0xfa",
in("rax") state_addr,
in("ecx") 0u32,
in("edx") 0u32,
options(nostack, preserves_flags),
);
asm!(
"push rbx",
"mov ebx, {ask:e}",
".byte 0x0f, 0x01, 0xfb",
"pop rbx",
ask = in(reg) ask,
inout("eax") 0xF0u32 => _,
inout("ecx") 2u32 => _,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
#[inline(always)]
unsafe fn wait_with_monitorx(_state_addr: *const u8, _deadline_tsc: u64) {
std::hint::spin_loop();
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::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_urd_{pid}_{nonce}_{name}.bin"));
p
}
fn remove_temp(path: &std::path::Path) {
if let Err(e) = std::fs::remove_file(path) {
eprintln!("urd test: could not remove {}: {e}", path.display());
}
}
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 _u = UrdDeque::create(&path, 4).expect("create");
let o = UrdDeque::open(&path).expect("open");
assert_eq!(o.n_mailboxes(), 4);
assert_eq!(o.owner_pid(), std::process::id() as u64);
std::fs::remove_file(&path).ok();
}
#[test]
fn wait_strategy_matches_host() {
let path = temp_path("strategy");
let u = UrdDeque::create(&path, 2).expect("create");
let s = u.wait_strategy();
if has_waitpkg() {
assert_eq!(s, WaitStrategy::Waitpkg);
} else if has_monitorx() {
assert_eq!(s, WaitStrategy::Monitorx);
} else {
assert_eq!(s, WaitStrategy::PauseSpin);
}
remove_temp(&path);
}
#[test]
fn the_second_stage_is_the_best_monitor_wait_the_host_has() {
let want = if has_waitpkg() {
WaitStrategy::Waitpkg
} else if has_monitorx() {
WaitStrategy::Monitorx
} else {
WaitStrategy::PauseSpin
};
assert_eq!(WaitStrategy::pick(), want);
}
#[test]
fn the_spin_floor_is_long_enough_to_be_worth_having() {
const { assert!(SPIN_BEFORE_WAIT >= 64) };
}
#[test]
fn the_thief_never_picks_a_wait_its_host_cannot_execute() {
let path = temp_path("strategy_executable");
let u = UrdDeque::create(&path, 2).expect("create");
match u.wait_strategy() {
WaitStrategy::Waitpkg => assert!(has_waitpkg()),
WaitStrategy::Monitorx => assert!(has_monitorx()),
WaitStrategy::PauseSpin => {}
}
remove_temp(&path);
}
#[test]
fn publish_then_drain_round_trips() {
let path = temp_path("publish_drain");
let u = UrdDeque::create(&path, 2).expect("create");
let items = [item(1), item(2), item(3)];
let n = u.publish_to(0, &items).expect("publish");
assert_eq!(n, 3);
match u.drain_mailbox(0) {
Drain::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);
}
Drain::Empty => panic!("expected ready mailbox"),
}
assert!(matches!(u.drain_mailbox(0), Drain::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn publish_round_robin_cycles_targets() {
let path = temp_path("rr");
let u = UrdDeque::create(&path, 4).expect("create");
let items = [item(1)];
let (t0, _) = u.publish_round_robin(&items).expect("rr 0");
u.drain_mailbox(t0);
let (t1, _) = u.publish_round_robin(&items).expect("rr 1");
u.drain_mailbox(t1);
let (t2, _) = u.publish_round_robin(&items).expect("rr 2");
u.drain_mailbox(t2);
let (t3, _) = u.publish_round_robin(&items).expect("rr 3");
let mut targets = [t0, t1, t2, t3];
targets.sort();
assert_eq!(targets, [0, 1, 2, 3]);
std::fs::remove_file(&path).ok();
}
#[test]
fn too_many_items_rejected() {
let path = temp_path("too_many");
let u = UrdDeque::create(&path, 2).expect("create");
let items: Vec<LineItem> = (0..(MAILBOX_ITEMS + 1) as u32).map(item).collect();
let err = u.publish_to(0, &items).expect_err("too many");
assert_eq!(err, PublishError::TooManyItems);
std::fs::remove_file(&path).ok();
}
#[test]
fn bad_target_rejected() {
let path = temp_path("bad_target");
let u = UrdDeque::create(&path, 2).expect("create");
let err = u.publish_to(99, &[item(1)]).expect_err("bad target");
assert_eq!(err, PublishError::BadTarget(99));
std::fs::remove_file(&path).ok();
}
#[test]
fn empty_publish_is_noop() {
let path = temp_path("empty");
let u = UrdDeque::create(&path, 2).expect("create");
assert_eq!(u.publish_to(0, &[]).expect("publish"), 0);
assert!(matches!(u.drain_mailbox(0), Drain::Empty));
std::fs::remove_file(&path).ok();
}
#[test]
fn close_owner_zeros_pid_and_advances_epoch() {
let path = temp_path("close");
let u = UrdDeque::create(&path, 2).expect("create");
let before = u.header().epoch.load(O::Acquire);
u.close_owner();
assert_eq!(u.owner_pid(), 0);
assert_eq!(u.header().epoch.load(O::Acquire), before + 1);
std::fs::remove_file(&path).ok();
}
#[test]
fn four_thieves_no_double_take() {
use std::sync::atomic::AtomicUsize;
use std::time::{Duration, Instant};
let path = temp_path("stress");
let u = Arc::new(UrdDeque::create(&path, 4).expect("create"));
let n = 400usize;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let mut thieves = Vec::new();
for tid in 0..4 {
let u = Arc::clone(&u);
let consumed = Arc::clone(&consumed);
let sum = Arc::clone(&sum);
thieves.push(thread::spawn(move || {
let deadline = Instant::now() + Duration::from_secs(30);
while consumed.load(O::Relaxed) < n {
assert!(
Instant::now() < deadline,
"URD stress: thief {tid} starved past 30s deadline",
);
match u.drain_mailbox(tid) {
Drain::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,
);
}
}
Drain::Empty => std::thread::yield_now(),
}
}
}));
}
let mut pushed = 0usize;
while pushed < n {
let want = MAILBOX_ITEMS.min(n - pushed);
let mut batch = [item(0); MAILBOX_ITEMS];
for slot in batch.iter_mut().take(want) {
*slot = item(pushed as u32);
pushed += 1;
}
u.publish_round_robin(&batch[..want]).expect("rr publish");
}
for t in thieves {
t.join().expect("thief");
}
let expected: usize = (0..n).sum();
assert_eq!(
sum.load(O::Relaxed),
expected,
"URD stress sum invariant (every item consumed exactly once)"
);
std::fs::remove_file(&path).ok();
}
}