use crossbeam_utils::CachePadded;
use crate::runtime::sync::cell::UnsafeCell;
use crate::runtime::sync::sync::atomic::{AtomicPtr, AtomicU64, AtomicU8, AtomicUsize, Ordering};
use crate::runtime::sync::sync::{Arc, Mutex};
pub(crate) const DEFAULT_SEG_SIZE: usize = 16;
const SLOT_EMPTY: u8 = 0;
const SLOT_FILLED: u8 = 1;
struct SlotState(AtomicU8);
impl SlotState {
fn new() -> Self {
Self(AtomicU8::new(SLOT_EMPTY))
}
fn publish_filled(&self) {
self.0.store(SLOT_FILLED, Ordering::Release);
}
fn is_filled(&self) -> bool {
self.0.load(Ordering::Acquire) == SLOT_FILLED
}
fn set_empty(&self) {
self.0.store(SLOT_EMPTY, Ordering::Release);
}
}
pub(crate) struct Slot<T> {
state: SlotState,
data: UnsafeCell<Option<T>>,
}
impl<T> Slot<T> {
fn new() -> Self {
Self {
state: SlotState::new(),
data: UnsafeCell::new(None),
}
}
pub(crate) fn get(&self) -> Option<&T> {
if !self.state.is_filled() {
return None;
}
self.data.with(|p| unsafe { (*p).as_ref() })
}
}
struct Segment<T> {
base: u64,
slots: Box<[Slot<T>]>,
next: AtomicPtr<Segment<T>>,
filled_count: CachePadded<AtomicUsize>,
claim_cursor: AtomicUsize,
drained_count: AtomicUsize,
}
impl<T> Segment<T> {
fn new(base: u64, seg_size: usize) -> Self {
let slots = (0..seg_size)
.map(|_| Slot::new())
.collect::<Vec<_>>()
.into_boxed_slice();
Self {
base,
slots,
next: AtomicPtr::new(std::ptr::null_mut()),
filled_count: CachePadded::new(AtomicUsize::new(0)),
claim_cursor: AtomicUsize::new(0),
drained_count: AtomicUsize::new(0),
}
}
fn len(&self) -> u64 {
self.slots.len() as u64
}
}
struct Locked<T> {
segments: std::collections::VecDeque<Arc<Segment<T>>>,
issued: u64,
}
struct Inner<T> {
locked: Mutex<Locked<T>>,
consumed: CachePadded<AtomicU64>,
seg_size: usize,
drain_batch: AtomicUsize,
}
#[derive(Clone)]
pub(crate) struct PagedRecvBuffer<T> {
inner: Arc<Inner<T>>,
}
pub(crate) struct RecvBufferConsumer<T> {
inner: Arc<Inner<T>>,
current: Arc<Segment<T>>,
cursor: u64,
}
#[must_use = "a claimed slot must be filled, or in-order delivery blocks at its sequence"]
pub(crate) struct SlotHandle<T> {
seq: u64,
seg: Arc<Segment<T>>,
idx: usize,
}
impl<T> SlotHandle<T> {
pub(crate) fn seq(&self) -> u64 {
self.seq
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum FillOutcome {
Stored,
DrainReady,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum DrainMode {
Batched,
Eager,
}
#[must_use = "a claimed run must be completed (or dropped) to free its payloads and unblock reclaim"]
pub(crate) struct SegmentWrite<T> {
seg: Arc<Segment<T>>,
inner: Arc<Inner<T>>,
start: usize,
len: usize,
drained: bool,
}
impl<T> SegmentWrite<T> {
#[cfg(test)]
pub(crate) fn base_seq(&self) -> u64 {
self.seg.base + self.start as u64
}
pub(crate) fn payloads(&self) -> &[Slot<T>] {
&self.seg.slots[self.start..self.start + self.len]
}
fn drain(&mut self) -> u64 {
if std::mem::replace(&mut self.drained, true) {
return 0;
}
let mut freed = 0u64;
for slot in self.payloads() {
slot.data.with_mut(|p| unsafe {
if (*p).take().is_some() {
freed += 1;
}
});
}
self.seg.drained_count.fetch_add(self.len, Ordering::AcqRel);
reclaim_front(&self.inner);
freed
}
pub(crate) fn complete(mut self) -> u64 {
self.drain()
}
}
impl<T> Drop for SegmentWrite<T> {
fn drop(&mut self) {
let _ = self.drain();
}
}
fn reclaim_locked<T>(guard: &mut Locked<T>, consumed: u64) {
while guard.segments.len() > 1 {
let front = guard.segments.front().unwrap();
let fully_consumed = front.base + front.len() <= consumed;
let drained = front.drained_count.load(Ordering::Acquire) == front.slots.len();
if fully_consumed || drained {
guard.segments.pop_front();
} else {
break;
}
}
}
fn reclaim_front<T>(inner: &Inner<T>) {
let mut guard = inner.locked.lock();
let consumed = inner.consumed.load(Ordering::Acquire);
reclaim_locked(&mut guard, consumed);
}
unsafe impl<T: Send> Send for PagedRecvBuffer<T> {}
unsafe impl<T: Send> Sync for PagedRecvBuffer<T> {}
unsafe impl<T: Send> Send for RecvBufferConsumer<T> {}
unsafe impl<T: Send> Sync for RecvBufferConsumer<T> {}
unsafe impl<T: Send> Send for SlotHandle<T> {}
unsafe impl<T: Send> Send for SegmentWrite<T> {}
unsafe impl<T: Send + Sync> Sync for SegmentWrite<T> {}
impl<T> PagedRecvBuffer<T> {
#[cfg(test)]
pub(crate) fn new() -> (Self, RecvBufferConsumer<T>) {
Self::new_with_segment_size(DEFAULT_SEG_SIZE)
}
pub(crate) fn new_with_segment_size(seg_size: usize) -> (Self, RecvBufferConsumer<T>) {
assert!(seg_size > 0, "segment size must be non-zero");
let seg0 = Arc::new(Segment::new(0, seg_size));
let mut segments = std::collections::VecDeque::new();
segments.push_back(seg0.clone());
let inner = Arc::new(Inner {
locked: Mutex::new(Locked {
segments,
issued: 0,
}),
consumed: CachePadded::new(AtomicU64::new(0)),
seg_size,
drain_batch: AtomicUsize::new(seg_size),
});
let consumer = RecvBufferConsumer {
inner: inner.clone(),
current: seg0,
cursor: 0,
};
(PagedRecvBuffer { inner }, consumer)
}
pub(crate) fn claim(&self) -> SlotHandle<T> {
let mut guard = self.inner.locked.lock();
let consumed = self.inner.consumed.load(Ordering::Acquire);
reclaim_locked(&mut guard, consumed);
let seq = guard.issued;
guard.issued += 1;
let tail = guard.segments.back().unwrap().clone();
debug_assert!(
tail.base.checked_add(tail.len()).is_some(),
"sequence space exhausted"
);
let seg = if seq >= tail.base + tail.len() {
let new = Arc::new(Segment::new(tail.base + tail.len(), self.inner.seg_size));
tail.next
.store(Arc::as_ptr(&new) as *mut _, Ordering::Release);
guard.segments.push_back(new.clone());
debug_assert!(seq < new.base + new.len());
new
} else {
tail
};
let idx = (seq - seg.base) as usize;
SlotHandle { seq, seg, idx }
}
pub(crate) fn fill(&self, handle: SlotHandle<T>, value: T) -> FillOutcome {
let SlotHandle { seg, idx, .. } = handle;
seg.slots[idx].data.with_mut(|p| unsafe {
*p = Some(value);
});
seg.slots[idx].state.publish_filled();
let filled = seg.filled_count.fetch_add(1, Ordering::AcqRel) + 1;
let claimed = seg.claim_cursor.load(Ordering::Acquire);
let batch = self.inner.drain_batch.load(Ordering::Relaxed);
if filled == seg.slots.len() || filled.saturating_sub(claimed) >= batch {
FillOutcome::DrainReady
} else {
FillOutcome::Stored
}
}
pub(crate) fn set_drain_batch(&self, batch: usize) {
self.inner
.drain_batch
.store(batch.max(1), Ordering::Relaxed);
}
pub(crate) fn take_drain_run(&self, mode: DrainMode) -> Option<SegmentWrite<T>> {
let guard = self.inner.locked.lock();
let batch = self.inner.drain_batch.load(Ordering::Relaxed);
for seg in guard.segments.iter() {
let start = seg.claim_cursor.load(Ordering::Relaxed);
let mut end = start;
while end < seg.slots.len() && seg.slots[end].state.is_filled() {
end += 1;
}
let avail = end - start;
let at_segment_end = end == seg.slots.len();
let take = if matches!(mode, DrainMode::Eager)
|| avail >= batch
|| (avail > 0 && at_segment_end)
{
avail
} else {
0
};
if take > 0 {
seg.claim_cursor.store(start + take, Ordering::Relaxed);
return Some(SegmentWrite {
seg: seg.clone(),
inner: self.inner.clone(),
start,
len: take,
drained: false,
});
}
}
None
}
pub(crate) fn has_drainable_prefix(&self) -> bool {
let guard = self.inner.locked.lock();
guard.segments.iter().any(|seg| {
let start = seg.claim_cursor.load(Ordering::Relaxed);
start < seg.slots.len() && seg.slots[start].state.is_filled()
})
}
pub(crate) fn has_undrained_fills(&self) -> bool {
let guard = self.inner.locked.lock();
guard.segments.iter().any(|seg| {
seg.filled_count.load(Ordering::Acquire) > seg.drained_count.load(Ordering::Acquire)
})
}
#[cfg(test)]
pub(crate) fn consumed(&self) -> u64 {
self.inner.consumed.load(Ordering::Acquire)
}
#[cfg(test)]
pub(crate) fn snapshot(&self) -> RecvBufferSnapshot {
let guard = self.inner.locked.lock();
let cursor = self.inner.consumed.load(Ordering::Acquire);
let frontier = guard.issued;
let mut arrived = Vec::new();
let mut run_start: Option<u64> = None;
for seq in cursor..frontier {
let seg = guard
.segments
.iter()
.find(|s| seq >= s.base && seq < s.base + s.len());
let filled = match seg {
Some(s) => {
let idx = (seq - s.base) as usize;
s.slots[idx].state.is_filled()
}
None => false,
};
if filled {
if run_start.is_none() {
run_start = Some(seq);
}
} else if let Some(start) = run_start.take() {
arrived.push(start..seq);
}
}
if let Some(start) = run_start {
arrived.push(start..frontier);
}
RecvBufferSnapshot {
cursor,
frontier,
arrived,
}
}
}
impl<T> RecvBufferConsumer<T> {
pub(crate) fn poll_next(&mut self) -> Option<T> {
if self.cursor == self.current.base + self.current.len() {
let raw = self.current.next.load(Ordering::Acquire);
if raw.is_null() {
return None;
}
let next = unsafe {
Arc::increment_strong_count(raw);
Arc::from_raw(raw)
};
self.current = next;
}
let idx = (self.cursor - self.current.base) as usize;
if !self.current.slots[idx].state.is_filled() {
return None;
}
let value = self.current.slots[idx]
.data
.with_mut(|p| unsafe { (*p).take() })
.unwrap();
self.current.slots[idx].state.set_empty();
self.cursor += 1;
self.inner.consumed.store(self.cursor, Ordering::Release);
Some(value)
}
}
#[cfg(test)]
pub(crate) struct RecvBufferSnapshot {
pub(crate) cursor: u64,
pub(crate) frontier: u64,
arrived: Vec<std::ops::Range<u64>>,
}
#[cfg(test)]
impl RecvBufferSnapshot {
pub(crate) fn outstanding(&self) -> u64 {
self.frontier - self.cursor
}
pub(crate) fn head_of_line(&self) -> Option<u64> {
match self.arrived.first() {
Some(first) if first.start == self.cursor => {
if first.end < self.frontier {
Some(first.end)
} else {
None
}
}
_ if self.cursor < self.frontier => Some(self.cursor),
_ => None,
}
}
pub(crate) fn pending(&self) -> Vec<std::ops::Range<u64>> {
let mut gaps = Vec::new();
let mut at = self.cursor;
for run in &self.arrived {
if at < run.start {
gaps.push(at..run.start);
}
at = run.end;
}
if at < self.frontier {
gaps.push(at..self.frontier);
}
gaps
}
pub(crate) fn arrived(&self) -> &[std::ops::Range<u64>] {
&self.arrived
}
}
#[cfg(test)]
impl<T> PagedRecvBuffer<T> {
fn segment_count(&self) -> usize {
self.inner.locked.lock().segments.len()
}
fn front_base(&self) -> u64 {
self.inner.locked.lock().segments.front().unwrap().base
}
}
#[cfg(test)]
impl<T> PagedRecvBuffer<T> {
fn fill_at(&self, handles: &[SlotHandle<T>], slot: usize, value: T) {
let h = &handles[slot];
let seg = h.seg.clone();
let idx = h.idx;
seg.slots[idx].data.with_mut(|p| unsafe {
*p = Some(value);
});
seg.slots[idx].state.publish_filled();
seg.filled_count.fetch_add(1, Ordering::AcqRel);
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::cell::Cell;
#[test]
fn recv_buffer_send_sync_bounds() {
fn assert_send<T: Send>() {}
fn assert_send_sync<T: Send + Sync>() {}
assert_send_sync::<PagedRecvBuffer<u8>>();
assert_send_sync::<SegmentWrite<u8>>();
assert_send_sync::<RecvBufferConsumer<u8>>();
assert_send::<SlotHandle<u8>>();
assert_send::<SegmentWrite<Cell<u8>>>();
static_assertions::assert_not_impl_all!(SegmentWrite<Cell<u8>>: Sync);
assert_send_sync::<PagedRecvBuffer<Cell<u8>>>();
}
fn permutations(n: usize) -> Vec<Vec<usize>> {
let mut items: Vec<usize> = (0..n).collect();
let mut out = Vec::new();
let mut c = vec![0usize; n];
out.push(items.clone());
let mut i = 0;
while i < n {
if c[i] < i {
if i % 2 == 0 {
items.swap(0, i);
} else {
items.swap(c[i], i);
}
out.push(items.clone());
c[i] += 1;
i = 0;
} else {
c[i] = 0;
i += 1;
}
}
out
}
#[test]
fn new_then_poll_returns_none() {
let (_ring, mut consumer) = PagedRecvBuffer::<u64>::new();
assert_eq!(consumer.poll_next(), None);
}
#[test]
fn single_item_round_trip() {
let (ring, mut consumer) = PagedRecvBuffer::new();
let handle = ring.claim();
assert_eq!(handle.seq(), 0);
ring.fill(handle, 42u64);
assert_eq!(consumer.poll_next(), Some(42));
assert_eq!(consumer.poll_next(), None);
}
#[test]
fn out_of_order_fill_within_segment() {
let (ring, mut consumer) = PagedRecvBuffer::new();
let h0 = ring.claim();
let h1 = ring.claim();
let h2 = ring.claim();
ring.fill(h2, 200u64);
assert_eq!(consumer.poll_next(), None);
ring.fill(h0, 0u64);
assert_eq!(consumer.poll_next(), Some(0));
assert_eq!(consumer.poll_next(), None);
ring.fill(h1, 100u64);
assert_eq!(consumer.poll_next(), Some(100));
assert_eq!(consumer.poll_next(), Some(200));
assert_eq!(consumer.poll_next(), None);
}
#[test]
fn cross_segment_delivery() {
let seg_size = 4;
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let n = seg_size * 3 + 2;
let handles: Vec<_> = (0..n).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
for i in 0..n {
assert_eq!(consumer.poll_next(), Some(i as u64), "mismatch at seq {i}");
}
assert_eq!(consumer.poll_next(), None);
}
#[test]
fn fill_outcome_drain_ready_on_last_fill() {
let seg_size = 8;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
let outcome = ring.fill(h, i as u64);
if i < seg_size - 1 {
assert_eq!(outcome, FillOutcome::Stored, "expected Stored at fill {i}");
} else {
assert_eq!(
outcome,
FillOutcome::DrainReady,
"expected DrainReady on the segment-completing fill"
);
}
}
}
#[test]
fn block_path_take_and_complete() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
let sw = ring
.take_drain_run(DrainMode::Batched)
.expect("should have a full segment");
assert_eq!(sw.base_seq(), 0);
assert_eq!(sw.payloads().len(), seg_size);
assert!(ring.take_drain_run(DrainMode::Batched).is_none());
sw.complete();
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, (seg_size + i) as u64);
}
let sw2 = ring
.take_drain_run(DrainMode::Batched)
.expect("second full segment should be takeable");
assert_eq!(sw2.base_seq(), seg_size as u64);
sw2.complete();
}
#[test]
fn take_returns_none_when_below_batch() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size - 1).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
assert!(ring.take_drain_run(DrainMode::Batched).is_none());
}
#[test]
fn drain_runs_partition_segment_at_small_batch() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
ring.set_drain_batch(2);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
ring.fill_at(&handles, 0, 0);
ring.fill_at(&handles, 1, 10);
let r0 = ring.take_drain_run(DrainMode::Batched).expect("first run");
assert_eq!(r0.base_seq(), 0);
let seen0: Vec<u64> = r0.payloads().iter().map(|s| *s.get().unwrap()).collect();
assert_eq!(seen0, vec![0, 10]);
assert!(ring.take_drain_run(DrainMode::Batched).is_none());
ring.fill_at(&handles, 2, 20);
ring.fill_at(&handles, 3, 30);
let r1 = ring.take_drain_run(DrainMode::Batched).expect("second run");
assert_eq!(r1.base_seq(), 2);
let seen1: Vec<u64> = r1.payloads().iter().map(|s| *s.get().unwrap()).collect();
assert_eq!(seen1, vec![20, 30]);
assert!(
ring.take_drain_run(DrainMode::Batched).is_none(),
"segment exhausted"
);
r0.complete();
r1.complete();
}
#[test]
fn drain_run_stops_at_gap() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
ring.set_drain_batch(2);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
ring.fill_at(&handles, 0, 0);
ring.fill_at(&handles, 1, 10);
ring.fill_at(&handles, 3, 30);
let r0 = ring
.take_drain_run(DrainMode::Batched)
.expect("prefix before the gap");
assert_eq!(r0.base_seq(), 0);
assert_eq!(r0.payloads().len(), 2);
assert!(ring.take_drain_run(DrainMode::Batched).is_none());
ring.fill_at(&handles, 2, 20);
let r1 = ring
.take_drain_run(DrainMode::Batched)
.expect("run after the gap fills");
assert_eq!(r1.base_seq(), 2);
let seen: Vec<u64> = r1.payloads().iter().map(|s| *s.get().unwrap()).collect();
assert_eq!(seen, vec![20, 30]);
r0.complete();
r1.complete();
}
#[test]
fn has_drainable_prefix_tracks_the_cursor_slot() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
assert!(!ring.has_drainable_prefix(), "empty buffer has no prefix");
ring.fill_at(&handles, 1, 10);
assert!(
!ring.has_drainable_prefix(),
"a filled slot behind an unfilled cursor slot is not a drainable prefix"
);
ring.fill_at(&handles, 0, 0);
assert!(
ring.has_drainable_prefix(),
"a FILLED slot at the cursor is a drainable prefix"
);
let sw = ring
.take_drain_run(DrainMode::Eager)
.expect("prefix [0,2) is claimable");
assert_eq!(sw.payloads().len(), 2);
assert!(
!ring.has_drainable_prefix(),
"after claiming the prefix the cursor slot is unfilled again"
);
sw.complete();
}
#[test]
fn terminal_drains_partial_below_batch() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..2).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, (i * 10) as u64);
}
assert!(ring.take_drain_run(DrainMode::Batched).is_none());
let sw = ring
.take_drain_run(DrainMode::Eager)
.expect("partial tail run");
assert_eq!(sw.base_seq(), 0);
let seen: Vec<u64> = sw.payloads().iter().map(|s| *s.get().unwrap()).collect();
assert_eq!(seen, vec![0, 10]);
sw.complete();
assert!(ring.take_drain_run(DrainMode::Eager).is_none());
}
#[test]
fn reclaim_waits_for_all_runs_of_a_segment() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
ring.set_drain_batch(2);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
ring.fill_at(&handles, 0, 0);
ring.fill_at(&handles, 1, 1);
let r0 = ring.take_drain_run(DrainMode::Batched).expect("run [0,2)");
ring.fill_at(&handles, 2, 2);
ring.fill_at(&handles, 3, 3);
let r1 = ring.take_drain_run(DrainMode::Batched).expect("run [2,4)");
r0.complete();
let h = ring.claim(); ring.fill(h, 4);
assert_eq!(
ring.segment_count(),
2,
"seg0 has an outstanding run; must not reclaim yet"
);
r1.complete();
assert_eq!(
ring.segment_count(),
1,
"seg0 reclaims once every claimed run completed"
);
}
#[test]
fn non_dividing_batch_drains_segment_tail_residue() {
let seg_size = 4;
let batch = 3; let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
ring.set_drain_batch(batch);
let mut outcomes = Vec::new();
for i in 0..batch {
let h = ring.claim();
outcomes.push(ring.fill(h, (i * 10) as u64));
}
assert_eq!(
outcomes,
vec![
FillOutcome::Stored,
FillOutcome::Stored,
FillOutcome::DrainReady
],
"the fill that reaches the batch raises DrainReady"
);
let r0 = ring
.take_drain_run(DrainMode::Batched)
.expect("batch-sized prefix run");
assert_eq!(r0.base_seq(), 0);
assert_eq!(
r0.payloads().len(),
batch,
"prefix run is exactly the batch"
);
r0.complete();
assert!(
ring.take_drain_run(DrainMode::Batched).is_none(),
"sub-batch residue is not drainable while the segment is incomplete"
);
let h = ring.claim();
assert_eq!(
ring.fill(h, 30),
FillOutcome::DrainReady,
"the fill that completes the segment raises the edge for the tail residue"
);
let r1 = ring
.take_drain_run(DrainMode::Batched)
.expect("segment-end residue run");
assert_eq!(r1.base_seq(), batch as u64);
assert_eq!(
r1.payloads().len(),
seg_size - batch,
"residue is the sub-batch tail"
);
let freed = r1.complete();
assert_eq!(
freed,
(seg_size - batch) as u64,
"residue run frees its tail"
);
}
#[test]
fn block_drain_reports_freed_not_consumed() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
ring.set_drain_batch(2);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
assert_eq!(ring.consumed(), 0);
ring.fill_at(&handles, 0, 0);
ring.fill_at(&handles, 1, 10);
let freed = ring
.take_drain_run(DrainMode::Batched)
.expect("run [0,2)")
.complete();
assert_eq!(freed, 2, "a block drain frees the run length");
assert_eq!(
ring.consumed(),
0,
"the block surface never advances the stream cursor"
);
ring.fill_at(&handles, 2, 20);
ring.fill_at(&handles, 3, 30);
let freed = ring
.take_drain_run(DrainMode::Batched)
.expect("run [2,4)")
.complete();
assert_eq!(freed, 2, "the second run frees its own length");
assert_eq!(ring.consumed(), 0, "consumed stays put on the block path");
}
#[test]
fn consumed_tracks_delivery_cursor() {
let seg_size = 2;
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
assert_eq!(ring.consumed(), 0);
let handles: Vec<_> = (0..3).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
assert_eq!(ring.consumed(), 0, "filling does not advance the cursor");
consumer.poll_next().unwrap();
consumer.poll_next().unwrap();
assert_eq!(ring.consumed(), 2, "two deliveries advance the cursor to 2");
}
#[test]
fn block_path_reads_payloads_in_place() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, (i * 10) as u64);
}
let sw = ring
.take_drain_run(DrainMode::Batched)
.expect("full segment");
let seen: Vec<u64> = sw.payloads().iter().map(|s| *s.get().unwrap()).collect();
assert_eq!(seen, vec![0, 10, 20, 30]);
sw.complete();
}
#[test]
fn slot_get_returns_filled_payload() {
let seg_size = 4;
let (ring, _consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, (i * 7) as u64);
}
let sw = ring
.take_drain_run(DrainMode::Batched)
.expect("full segment");
for (i, slot) in sw.payloads().iter().enumerate() {
assert_eq!(*slot.get().expect("filled"), (i * 7) as u64);
}
sw.complete();
}
#[test]
fn drop_without_complete_reclaims() {
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::sync::Arc as StdArc;
struct DropCounter(#[allow(dead_code)] StdArc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, O::SeqCst);
}
}
let drops = StdArc::new(AtomicUsize::new(0));
let seg_size = 2;
let (ring, _consumer) = PagedRecvBuffer::<DropCounter>::new_with_segment_size(seg_size);
for _ in 0..seg_size {
let h = ring.claim();
ring.fill(h, DropCounter(drops.clone()));
}
let sw = ring.take_drain_run(DrainMode::Batched).expect("seg0 full");
assert_eq!(sw.base_seq(), 0);
assert_eq!(
drops.load(O::SeqCst),
0,
"nothing freed until the run drains"
);
drop(sw);
assert_eq!(
drops.load(O::SeqCst),
seg_size,
"drop-without-complete must free every payload in the run"
);
for _ in 0..2 {
let h = ring.claim();
ring.fill(h, DropCounter(drops.clone()));
}
assert_eq!(
ring.segment_count(),
1,
"dropped-without-complete run must drain and reclaim, not wedge"
);
assert_eq!(
ring.front_base(),
seg_size as u64,
"seg0 (base 0) is the segment reclaimed after its run drained"
);
}
#[test]
fn complete_then_drop_frees_exactly_once() {
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::sync::Arc as StdArc;
struct DropCounter(StdArc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, O::SeqCst);
}
}
let drops = StdArc::new(AtomicUsize::new(0));
let seg_size = 2;
let (ring, _consumer) = PagedRecvBuffer::<DropCounter>::new_with_segment_size(seg_size);
for _ in 0..seg_size {
let h = ring.claim();
ring.fill(h, DropCounter(drops.clone()));
}
let sw = ring.take_drain_run(DrainMode::Batched).expect("full");
sw.complete();
assert_eq!(
drops.load(O::SeqCst),
seg_size,
"complete frees every payload once"
);
assert_eq!(
drops.load(O::SeqCst),
seg_size,
"Drop after complete is a no-op; no double free"
);
}
#[test]
fn out_of_order_complete_frees_eagerly() {
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::sync::Arc as StdArc;
struct DropCounter(StdArc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, O::SeqCst);
}
}
let drops = StdArc::new(AtomicUsize::new(0));
let seg_size = 2;
let (ring, _consumer) = PagedRecvBuffer::<DropCounter>::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size * 2).map(|_| ring.claim()).collect();
let mut it = handles.into_iter();
let h0 = it.next().unwrap(); let h1 = it.next().unwrap(); let h2 = it.next().unwrap();
let h3 = it.next().unwrap();
ring.fill(h2, DropCounter(drops.clone()));
ring.fill(h3, DropCounter(drops.clone()));
let sw = ring
.take_drain_run(DrainMode::Batched)
.expect("seg1 is full");
assert_eq!(
sw.base_seq(),
seg_size as u64,
"frontmost drainable run is in seg1"
);
sw.complete();
assert_eq!(
drops.load(O::SeqCst),
seg_size,
"out-of-order completed segment frees its budget eagerly"
);
ring.fill(h0, DropCounter(drops.clone()));
ring.fill(h1, DropCounter(drops.clone()));
}
#[test]
fn snapshot_cursor_after_drain() {
let seg_size = 2;
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..5).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
for _ in 0..3 {
consumer.poll_next().unwrap();
}
let snap = ring.snapshot();
assert_eq!(
snap.cursor, 3,
"snapshot cursor reflects the consumer's position"
);
assert_eq!(snap.frontier, 5);
assert_eq!(snap.outstanding(), 2);
assert_eq!(snap.arrived(), std::slice::from_ref(&(3..5)));
assert_eq!(
snap.head_of_line(),
None,
"remaining outstanding have all arrived"
);
}
#[test]
fn exhaustive_fill_order_within_segment() {
let seg_size = 4;
for perm in permutations(seg_size) {
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
let mut filled = vec![false; seg_size];
let mut delivered = Vec::new();
for &slot in &perm {
ring.fill_at(&handles, slot, (slot * 10) as u64);
filled[slot] = true;
let mut deliverable = 0;
while deliverable < seg_size && filled[deliverable] {
deliverable += 1;
}
while let Some(v) = consumer.poll_next() {
delivered.push(v);
}
let expect: Vec<u64> = (0..deliverable as u64).map(|i| i * 10).collect();
assert_eq!(
delivered, expect,
"perm {perm:?}: wrong prefix after filling {slot}"
);
}
assert_eq!(consumer.poll_next(), None, "perm {perm:?}: residue");
}
}
#[test]
fn exhaustive_fill_order_across_segments() {
let seg_size = 2;
let segments = if cfg!(miri) { 2 } else { 3 };
let n = seg_size * segments;
for perm in permutations(n) {
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let handles: Vec<_> = (0..n).map(|_| ring.claim()).collect();
let mut delivered = Vec::new();
for &slot in &perm {
ring.fill_at(&handles, slot, (slot * 10) as u64);
while let Some(v) = consumer.poll_next() {
delivered.push(v);
}
}
let expect: Vec<u64> = (0..n as u64).map(|i| i * 10).collect();
assert_eq!(delivered, expect, "perm {perm:?}: out-of-order or lost");
assert_eq!(consumer.poll_next(), None);
}
}
#[test]
fn snapshot_non_contiguous() {
let (ring, _consumer) = PagedRecvBuffer::new();
let mut handles = Vec::new();
for _ in 0..6 {
handles.push(ring.claim());
}
ring.fill(handles.remove(0), 100u64); ring.fill(handles.remove(0), 101u64); let h2 = handles.remove(0); ring.fill(handles.remove(0), 103u64); let h4 = handles.remove(0); ring.fill(handles.remove(0), 105u64);
let snap = ring.snapshot();
assert_eq!(snap.cursor, 0);
assert_eq!(snap.frontier, 6);
assert_eq!(snap.arrived(), &[0..2, 3..4, 5..6]);
assert_eq!(snap.outstanding(), 6);
assert_eq!(snap.head_of_line(), Some(2));
assert_eq!(snap.pending(), vec![2..3, 4..5]);
ring.fill(h2, 102u64);
ring.fill(h4, 104u64);
}
#[test]
fn snapshot_head_of_line_at_cursor() {
let (ring, _consumer) = PagedRecvBuffer::new();
let h0 = ring.claim();
let h1 = ring.claim();
ring.fill(h1, 11u64);
let snap = ring.snapshot();
assert_eq!(snap.cursor, 0);
assert_eq!(snap.frontier, 2);
assert_eq!(snap.head_of_line(), Some(0));
assert_eq!(snap.pending(), vec![0..1]);
assert_eq!(snap.arrived(), std::slice::from_ref(&(1..2)));
ring.fill(h0, 10u64);
}
#[test]
fn snapshot_fully_arrived_no_blocker() {
let (ring, _consumer) = PagedRecvBuffer::new();
let h0 = ring.claim();
let h1 = ring.claim();
ring.fill(h0, 10u64);
ring.fill(h1, 11u64);
let snap = ring.snapshot();
assert_eq!(snap.outstanding(), 2);
assert_eq!(snap.head_of_line(), None);
assert!(snap.pending().is_empty());
assert_eq!(snap.arrived(), std::slice::from_ref(&(0..2)));
}
#[test]
fn reclaim_via_stream_and_claim() {
let seg_size = 4;
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let n = seg_size * 2;
let handles: Vec<_> = (0..n).map(|_| ring.claim()).collect();
for (i, h) in handles.into_iter().enumerate() {
ring.fill(h, i as u64);
}
assert_eq!(ring.segment_count(), 2);
assert_eq!(ring.front_base(), 0);
for _ in 0..seg_size + 1 {
consumer.poll_next().unwrap();
}
let h = ring.claim();
ring.fill(h, 999u64);
assert_eq!(ring.segment_count(), 2, "seg0 reclaimed, seg2 grew");
assert_eq!(
ring.front_base(),
seg_size as u64,
"the fully-consumed front segment (base 0) is the one reclaimed"
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn fill_probe_does_not_underflow_under_concurrent_drain() {
use std::sync::atomic::{AtomicU64, Ordering as O};
for _ in 0..200 {
let seg_size = 16;
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(seg_size);
ring.set_drain_batch(1);
let handles: Vec<_> = (0..seg_size).map(|_| ring.claim()).collect();
let ring = Arc::new(ring);
let freed_total = Arc::new(AtomicU64::new(0));
std::thread::scope(|s| {
for h in handles {
let ring = ring.clone();
let freed_total = freed_total.clone();
s.spawn(move || {
if ring.fill(h, 0) == FillOutcome::DrainReady {
while let Some(sw) = ring.take_drain_run(DrainMode::Batched) {
freed_total.fetch_add(sw.complete(), O::Relaxed);
}
}
});
}
});
while let Some(sw) = ring.take_drain_run(DrainMode::Eager) {
freed_total.fetch_add(sw.complete(), O::Relaxed);
}
assert_eq!(
freed_total.load(O::Relaxed),
seg_size as u64,
"every slot must drain exactly once under concurrent fill+drain"
);
}
}
#[test]
fn concurrent_producer_consumer() {
let seg_size = 4;
let (ring, mut consumer) = PagedRecvBuffer::new_with_segment_size(seg_size);
let n = seg_size * 4;
let ring_clone = ring.clone();
std::thread::scope(|s| {
s.spawn(move || {
for i in 0..n {
let h = ring_clone.claim();
ring_clone.fill(h, i as u64);
}
});
let mut received = Vec::with_capacity(n);
while received.len() < n {
if let Some(v) = consumer.poll_next() {
received.push(v);
}
}
let expected: Vec<u64> = (0..n as u64).collect();
assert_eq!(received, expected);
});
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::*;
use crate::runtime::sync::thread;
#[test]
fn fill_poll_handoff() {
loom::model(|| {
let (ring, mut consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
let handle = ring.claim();
let producer = thread::spawn(move || {
ring.fill(handle, 42);
});
if let Some(v) = consumer.poll_next() {
assert_eq!(v, 42, "observed filled slot must carry the published value");
}
producer.join().unwrap();
let tail = consumer.poll_next();
assert!(tail.is_none() || tail == Some(42));
});
}
#[test]
fn segment_hop() {
loom::model(|| {
let (ring, mut consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
let producer = thread::spawn(move || {
for i in 0..3u64 {
let h = ring.claim();
ring.fill(h, i);
}
});
let mut got = Vec::new();
for _ in 0..6 {
match consumer.poll_next() {
Some(v) => got.push(v),
None => {
if got.len() == 3 {
break;
}
}
}
}
producer.join().unwrap();
for (i, v) in got.iter().enumerate() {
assert_eq!(*v, i as u64, "delivery must be in order across the hop");
}
while let Some(v) = consumer.poll_next() {
got.push(v);
}
assert_eq!(got, vec![0, 1, 2]);
});
}
#[test]
fn reclaim_vs_outstanding_write() {
loom::model(|| {
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
for i in 0..2 {
let h = ring.claim();
ring.fill(h, i as u64);
}
let ring2 = ring.clone();
let taker = thread::spawn(move || {
let sw = ring2
.take_drain_run(DrainMode::Batched)
.expect("seg0 is full and drainable");
assert_eq!(sw.base_seq(), 0);
sw.complete(); });
let h = ring.claim(); ring.fill(h, 99);
taker.join().unwrap();
let h = ring.claim();
ring.fill(h, 100);
assert_eq!(
ring.front_base(),
2,
"drained seg0 (base 0) reclaimed exactly once"
);
});
}
#[test]
fn two_producers_out_of_order() {
loom::model(|| {
let (ring, mut consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
let h0 = ring.claim(); let h1 = ring.claim();
let ring_a = ring.clone();
let a = thread::spawn(move || {
ring_a.fill(h1, 1); });
let b = thread::spawn(move || {
ring.fill(h0, 0);
});
let mut got = Vec::new();
for _ in 0..4 {
if let Some(v) = consumer.poll_next() {
got.push(v);
}
if got.len() == 2 {
break;
}
}
a.join().unwrap();
b.join().unwrap();
while let Some(v) = consumer.poll_next() {
got.push(v);
}
assert_eq!(got, vec![0, 1]);
});
}
#[test]
fn two_takers_race_one_segment() {
loom::model(|| {
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
for i in 0..2 {
let h = ring.claim();
ring.fill(h, i as u64);
}
let ring2 = ring.clone();
let t1 = thread::spawn(move || {
ring2
.take_drain_run(DrainMode::Batched)
.map(|sw| sw.base_seq())
});
let t2 = thread::spawn(move || {
ring.take_drain_run(DrainMode::Batched)
.map(|sw| sw.base_seq())
});
let r1 = t1.join().unwrap();
let r2 = t2.join().unwrap();
let winners: Vec<u64> = [r1, r2].into_iter().flatten().collect();
assert_eq!(
winners,
vec![0],
"exactly one drainer claims the full-segment run"
);
});
}
#[test]
fn drop_without_complete_vs_reclaim() {
loom::model(|| {
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
for i in 0..2 {
let h = ring.claim();
ring.fill(h, i as u64);
}
let ring2 = ring.clone();
let taker = thread::spawn(move || {
let sw = ring2
.take_drain_run(DrainMode::Batched)
.expect("seg0 is full and drainable");
assert_eq!(sw.base_seq(), 0);
drop(sw);
});
let h = ring.claim(); ring.fill(h, 99);
taker.join().unwrap();
let h = ring.claim();
ring.fill(h, 100);
assert_eq!(
ring.front_base(),
2,
"drop-drained seg0 (base 0) reclaimed exactly once"
);
});
}
#[test]
fn out_of_order_fill_across_segment_hop() {
loom::model(|| {
let (ring, mut consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
let handles: Vec<_> = (0..4).map(|_| ring.claim()).collect();
let ring_a = ring.clone();
let a = thread::spawn(move || {
ring_a.fill_at(&handles, 3, 3);
ring_a.fill_at(&handles, 2, 2);
ring_a.fill_at(&handles, 1, 1);
ring_a.fill_at(&handles, 0, 0);
});
let mut got = Vec::new();
for _ in 0..8 {
if let Some(v) = consumer.poll_next() {
got.push(v);
}
if got.len() == 4 {
break;
}
}
a.join().unwrap();
while let Some(v) = consumer.poll_next() {
got.push(v);
}
assert_eq!(
got,
vec![0, 1, 2, 3],
"in-order, exactly once, across the hop"
);
});
}
#[test]
fn reclaim_races_consumer_hop() {
loom::model(|| {
let (ring, mut consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
let h0 = ring.claim();
let h1 = ring.claim();
ring.fill(h0, 0);
ring.fill(h1, 1);
assert_eq!(consumer.poll_next(), Some(0));
assert_eq!(consumer.poll_next(), Some(1));
let ring2 = ring.clone();
let issuer = thread::spawn(move || {
let h2 = ring2.claim(); ring2.fill(h2, 2);
let h3 = ring2.claim(); ring2.fill(h3, 3);
});
let mut got = Vec::new();
for _ in 0..6 {
if let Some(v) = consumer.poll_next() {
got.push(v);
}
if got.len() == 2 {
break;
}
}
issuer.join().unwrap();
while let Some(v) = consumer.poll_next() {
got.push(v);
}
assert_eq!(got, vec![2, 3], "post-hop delivery in order, exactly once");
});
}
#[test]
fn two_takers_distinct_segments() {
loom::model(|| {
let (ring, _consumer) = PagedRecvBuffer::<u64>::new_with_segment_size(2);
for i in 0..4u64 {
let h = ring.claim();
ring.fill(h, i);
}
let ring2 = ring.clone();
let t1 = thread::spawn(move || {
ring2
.take_drain_run(DrainMode::Batched)
.map(|sw| sw.base_seq())
});
let t2 = thread::spawn(move || {
ring.take_drain_run(DrainMode::Batched)
.map(|sw| sw.base_seq())
});
let r1 = t1.join().unwrap();
let r2 = t2.join().unwrap();
let mut bases: Vec<u64> = [r1, r2].into_iter().flatten().collect();
bases.sort_unstable();
assert_eq!(
bases,
vec![0, 2],
"both full segments handed out exactly once across racing drainers"
);
});
}
#[test]
fn two_drainers_partition_one_segment() {
loom::model(|| {
#[derive(Clone)]
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::SeqCst);
}
}
let drops = Arc::new(AtomicUsize::new(0));
let (ring, _consumer) = PagedRecvBuffer::<DropCounter>::new_with_segment_size(2);
ring.set_drain_batch(1);
let h0 = ring.claim();
let h1 = ring.claim();
let ring_a = ring.clone();
let da = drops.clone();
let a = thread::spawn(move || {
ring_a.fill(h0, DropCounter(da));
if let Some(sw) = ring_a.take_drain_run(DrainMode::Batched) {
sw.complete();
}
});
let ring_b = ring.clone();
let db = drops.clone();
let b = thread::spawn(move || {
ring_b.fill(h1, DropCounter(db));
if let Some(sw) = ring_b.take_drain_run(DrainMode::Batched) {
sw.complete();
}
});
a.join().unwrap();
b.join().unwrap();
while let Some(sw) = ring.take_drain_run(DrainMode::Eager) {
sw.complete();
}
assert_eq!(
drops.load(Ordering::SeqCst),
2,
"each slot's payload freed exactly once across partitioned runs"
);
});
}
#[test]
fn two_eager_drainers_partition_one_segment() {
loom::model(|| {
#[derive(Clone)]
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::SeqCst);
}
}
let drops = Arc::new(AtomicUsize::new(0));
let (ring, _consumer) = PagedRecvBuffer::<DropCounter>::new_with_segment_size(2);
let h0 = ring.claim();
let h1 = ring.claim();
let ring_a = ring.clone();
let da = drops.clone();
let a = thread::spawn(move || {
ring_a.fill(h0, DropCounter(da));
if let Some(sw) = ring_a.take_drain_run(DrainMode::Eager) {
sw.complete();
}
});
let ring_b = ring.clone();
let db = drops.clone();
let b = thread::spawn(move || {
ring_b.fill(h1, DropCounter(db));
if let Some(sw) = ring_b.take_drain_run(DrainMode::Eager) {
sw.complete();
}
});
a.join().unwrap();
b.join().unwrap();
while let Some(sw) = ring.take_drain_run(DrainMode::Eager) {
sw.complete();
}
assert_eq!(
drops.load(Ordering::SeqCst),
2,
"each slot's payload freed exactly once across partitioned Eager runs"
);
});
}
}