use std::sync::OnceLock;
#[cfg(loom)]
use loom::sync::{Condvar, Mutex};
#[cfg(not(loom))]
use std::sync::{Condvar, Mutex};
use store_io_core::error::NotWrittenCause;
use store_io_core::id::{Generation, RegionId, VolumeId};
use crate::sync::{AtomicU64, Ordering};
#[derive(Debug)]
pub struct AppendFrontier {
shift: u32,
limit: AtomicU64,
tail: AtomicU64,
prefix: AtomicU64,
durable: AtomicU64,
synced: AtomicU64,
ring: OnceLock<Box<[AtomicU64]>>,
mask: u64,
waiters: AtomicU64,
wait: Mutex<()>,
wake: Condvar,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Reservation {
pub start: u64,
pub data_end: u64,
pub end: u64,
}
fn slots(n: usize) -> Box<[AtomicU64]> {
(0..n).map(|_| AtomicU64::new(0)).collect()
}
fn pack(start_block: u64, end_block: u64) -> u64 {
(start_block << 32) | (end_block & 0xFFFF_FFFF)
}
fn unpack(v: u64) -> (u64, u64) {
(v >> 32, v & 0xFFFF_FFFF)
}
pub(crate) type ResumeKey = (VolumeId, RegionId, Generation);
static RESUMES: std::sync::Mutex<std::collections::BTreeMap<ResumeKey, Vec<(u64, u64)>>> =
std::sync::Mutex::new(std::collections::BTreeMap::new());
fn resumes()
-> std::sync::MutexGuard<'static, std::collections::BTreeMap<ResumeKey, Vec<(u64, u64)>>> {
RESUMES
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner)
}
type FileKey = (u64, u128);
struct Lineage {
expect: Option<u64>,
fence: u64,
}
struct Opens {
files: std::collections::BTreeMap<u64, (VolumeId, FileKey)>,
lineages: std::collections::BTreeMap<(VolumeId, FileKey), Lineage>,
}
static OPENS: std::sync::Mutex<Opens> = std::sync::Mutex::new(Opens {
files: std::collections::BTreeMap::new(),
lineages: std::collections::BTreeMap::new(),
});
fn opens() -> std::sync::MutexGuard<'static, Opens> {
OPENS
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner)
}
pub(crate) fn note_open(
volume: VolumeId,
file: store_io_platform::FileIdentity,
epoch: u64,
found: Option<u64>,
) {
if !crate::test_hook::seen() {
return;
}
let key = (volume, (file.volume, file.file));
let mut all = opens();
let _was = all.files.insert(epoch, key);
if all.files.len() > MAX_OPENS {
let _forgotten = all.files.pop_first();
}
let lineage = all.lineages.entry(key).or_insert(Lineage {
expect: None,
fence: epoch,
});
if found.is_none() || lineage.expect != found {
lineage.fence = epoch;
}
lineage.expect = None;
}
pub(crate) fn note_close(epoch: u64, left: Option<u64>) {
if !crate::test_hook::seen() {
return;
}
let mut all = opens();
if let Some(key) = all.files.get(&epoch).copied() {
if let Some(lineage) = all.lineages.get_mut(&key) {
lineage.expect = left;
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Earlier {
Same { vouched: bool },
Other,
Unknown,
}
pub(crate) fn earlier_open(now: u64, earlier: u64) -> Earlier {
let all = opens();
match (all.files.get(&now), all.files.get(&earlier)) {
(Some(a), Some(b)) if a != b => Earlier::Other,
(Some(a), Some(_)) => Earlier::Same {
vouched: all.lineages.get(a).is_some_and(|l| earlier >= l.fence),
},
_ => Earlier::Unknown,
}
}
pub(crate) fn record_resume(key: ResumeKey, epoch: u64, at: u64) {
if !crate::test_hook::seen() {
return;
}
let mut all = resumes();
let list = all.entry(key).or_default();
if list.iter().any(|&(e, b)| e >= epoch && b <= at) {
return;
}
list.retain(|&(e, b)| !(e <= epoch && b >= at));
list.push((epoch, at));
if list.len() > MAX_RESUMES {
list.sort_unstable();
let (e2, b1) = (list[1].0, list[0].1.min(list[1].1));
list[1] = (e2, b1);
let _oldest = list.remove(0);
}
}
const MAX_RESUMES: usize = 64;
const MAX_OPENS: usize = 1 << 16;
pub(crate) fn resumed_below(key: ResumeKey, epoch: u64, through: u64) -> bool {
resumes()
.get(&key)
.is_some_and(|list| list.iter().any(|&(e, b)| e > epoch && b < through))
}
const MAX_RING: u64 = 1 << 20;
#[must_use]
pub(crate) fn ring_for(window: u64, limit: u64, shift: u32) -> usize {
let (w, r) = (window >> shift, limit.div_ceil(1 << shift));
let blocks = if r <= w {
r.max(2).next_power_of_two()
} else {
1u64 << (63 - w.max(1).leading_zeros())
};
#[allow(clippy::cast_possible_truncation)]
let slots = blocks.clamp(2, MAX_RING) as usize;
slots
}
#[must_use]
pub(crate) fn ring_reach(capacity: u64, flags: u8) -> u64 {
if flags & store_io_format::meta2::FLAG_CAPPED != 0 {
capacity
} else {
u64::MAX
}
}
impl AppendFrontier {
#[must_use]
pub fn new(resume: u64, limit: u64, shift: u32, ring: usize) -> Self {
let ring = ring.max(2).next_power_of_two();
let cell = OnceLock::new();
#[cfg(loom)]
let _set = cell.set(slots(ring));
Self {
shift,
limit: AtomicU64::new(limit),
tail: AtomicU64::new(resume),
prefix: AtomicU64::new(resume),
durable: AtomicU64::new(resume),
synced: AtomicU64::new(resume),
ring: cell,
mask: ring as u64 - 1,
waiters: AtomicU64::new(0),
wait: Mutex::new(()),
wake: Condvar::new(),
}
}
pub fn reserve(&self, len: u64) -> Result<Reservation, NotWrittenCause> {
if len == 0 {
return Err(NotWrittenCause::Empty);
}
let block = 1u64 << self.shift;
let mut start = self.tail.load(Ordering::SeqCst);
loop {
let data_end = start.checked_add(len).ok_or(NotWrittenCause::RegionFull)?;
let end = data_end
.checked_add(block - 1)
.ok_or(NotWrittenCause::RegionFull)?
& !(block - 1);
if end > self.limit.load(Ordering::Acquire) {
return Err(NotWrittenCause::RegionFull);
}
let prefix = self.prefix.load(Ordering::SeqCst);
if (start >> self.shift).saturating_sub(prefix >> self.shift) > self.mask {
return Err(NotWrittenCause::TooManyInFlight);
}
match self
.tail
.compare_exchange_weak(start, end, Ordering::SeqCst, Ordering::SeqCst)
{
Ok(_) => {
return Ok(Reservation {
start,
data_end,
end,
});
}
Err(current) => start = current,
}
}
}
pub fn reserve_wait(
&self,
len: u64,
give_up: impl Fn() -> bool,
) -> Result<Reservation, NotWrittenCause> {
loop {
if give_up() {
return Err(NotWrittenCause::TooManyInFlight);
}
let p = self.prefix.load(Ordering::SeqCst);
match self.reserve(len) {
Err(NotWrittenCause::TooManyInFlight) => {
if !self.wait_completed(p + 1, &give_up) {
return Err(NotWrittenCause::TooManyInFlight);
}
}
other => return other,
}
}
}
pub fn complete(&self, r: Reservation) {
let sb = r.start >> self.shift;
let eb = r.end >> self.shift;
let ring = self.ring();
let _previous = ring[(sb & self.mask) as usize].swap(pack(sb, eb), Ordering::AcqRel);
if self.advance(ring) {
self.wake_if_waiting();
}
}
pub(crate) fn raise_limit(&self, limit: u64) {
let _was = self.limit.fetch_max(limit, Ordering::Release);
}
fn ring(&self) -> &[AtomicU64] {
self.ring.get_or_init(|| slots(self.mask as usize + 1))
}
#[cfg(all(test, not(loom)))]
pub(crate) fn ring_slots(&self) -> usize {
self.ring.get().map_or(0, |r| r.len())
}
fn advance(&self, ring: &[AtomicU64]) -> bool {
let mut advanced = false;
loop {
let p = self.prefix.load(Ordering::Acquire);
let pb = p >> self.shift;
let slot = &ring[(pb & self.mask) as usize];
let v = slot.fetch_or(0, Ordering::AcqRel);
if v == 0 {
break;
}
let (s, e) = unpack(v);
if s != pb {
break;
}
if slot
.compare_exchange(v, 0, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
self.prefix.store(e << self.shift, Ordering::Release);
advanced = true;
}
}
advanced
}
fn wake_if_waiting(&self) {
if self.waiters.fetch_or(0, Ordering::AcqRel) > 0 {
let _guard = self
.wait
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
self.wake.notify_all();
}
}
pub fn wait_completed(&self, end: u64, give_up: impl Fn() -> bool) -> bool {
if self.prefix.load(Ordering::SeqCst) >= end {
return true;
}
let _registered = self.waiters.fetch_add(1, Ordering::SeqCst);
let mut guard = self
.wait
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
let reached = loop {
if self.prefix.load(Ordering::SeqCst) >= end {
break true;
}
if give_up() {
break false;
}
guard = self
.wake
.wait(guard)
.unwrap_or_else(std::sync::PoisonError::into_inner);
};
drop(guard);
let _unregistered = self.waiters.fetch_sub(1, Ordering::SeqCst);
reached
}
pub fn wake_all(&self) {
let _guard = self
.wait
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
self.wake.notify_all();
}
#[must_use]
pub fn waiting(&self) -> u64 {
self.waiters.load(Ordering::SeqCst)
}
#[must_use]
pub fn completed(&self) -> u64 {
self.prefix.load(Ordering::SeqCst)
}
#[must_use]
pub fn durable(&self) -> u64 {
self.durable.load(Ordering::SeqCst)
}
pub fn publish_durable(&self, through: u64) {
let _previous = self.durable.fetch_max(through, Ordering::SeqCst);
}
#[must_use]
pub fn synced(&self) -> u64 {
self.synced.load(Ordering::SeqCst)
}
pub fn publish_synced(&self, through: u64) {
self.publish_durable(through);
let _previous = self.synced.fetch_max(through, Ordering::SeqCst);
}
#[must_use]
pub fn tail(&self) -> u64 {
self.tail.load(Ordering::SeqCst)
}
pub fn resume_at(&self, offset: u64) -> Result<u64, NotWrittenCause> {
let block = 1u64 << self.shift;
let target = offset
.checked_add(block - 1)
.ok_or(NotWrittenCause::OutOfBounds)?
& !(block - 1);
if target > self.limit.load(Ordering::Acquire) {
return Err(NotWrittenCause::OutOfBounds);
}
let tail = self.tail.load(Ordering::SeqCst);
if self.prefix.load(Ordering::SeqCst) != tail {
return Err(NotWrittenCause::TooManyInFlight);
}
let new = target.max(tail);
if new == tail {
return Ok(tail);
}
if self
.tail
.compare_exchange(tail, new, Ordering::SeqCst, Ordering::SeqCst)
.is_err()
{
return Err(NotWrittenCause::TooManyInFlight);
}
let _moved = self
.prefix
.compare_exchange(tail, new, Ordering::SeqCst, Ordering::SeqCst);
let _moved = self.advance(self.ring());
self.wake_if_waiting();
let _moved = self
.durable
.compare_exchange(tail, new, Ordering::SeqCst, Ordering::SeqCst);
let _moved = self
.synced
.compare_exchange(tail, new, Ordering::SeqCst, Ordering::SeqCst);
Ok(new)
}
}
#[cfg(all(test, not(loom)))]
mod tests {
#![allow(clippy::unwrap_used)]
use super::*;
use std::sync::Arc;
#[test]
fn test_the_ring_is_allocated_at_the_first_completion() {
let ring = ring_for(16 << 20, 64 << 20, 12);
let fr = AppendFrontier::new(0, 64 << 20, 12, ring);
assert_eq!(fr.ring_slots(), 0);
assert_eq!(fr.resume_at(0), Ok(0));
let r = fr.reserve(4096).unwrap();
assert_eq!(fr.ring_slots(), 0);
fr.complete(r);
assert_eq!(fr.ring_slots(), 4096);
assert_eq!(fr.completed(), 4096);
let moved = AppendFrontier::new(0, 64 << 20, 12, ring);
assert_eq!(moved.resume_at(8192), Ok(8192));
assert_eq!(moved.ring_slots(), 4096);
}
#[test]
fn test_raise_limit() {
let fr = AppendFrontier::new(0, 8192, 12, 4);
let r = fr.reserve(8192).unwrap();
fr.complete(r);
assert_eq!(fr.reserve(1), Err(NotWrittenCause::RegionFull));
fr.raise_limit(16384);
fr.raise_limit(4096);
let r = fr.reserve(8192).unwrap();
assert_eq!((r.start, r.end), (8192, 16384));
assert_eq!(fr.reserve(1), Err(NotWrittenCause::RegionFull));
}
#[test]
fn test_first_appends_at_once_share_one_ring() {
let fr = Arc::new(AppendFrontier::new(0, 64 << 20, 12, 64));
let threads: Vec<_> = (0..16)
.map(|_| {
let fr = Arc::clone(&fr);
std::thread::spawn(move || {
for _ in 0..4 {
let r = fr.reserve_wait(4096, || false).unwrap();
fr.complete(r);
}
})
})
.collect();
for t in threads {
t.join().unwrap();
}
assert_eq!(fr.ring_slots(), 64);
assert_eq!(fr.completed(), 64 * 4096);
}
#[test]
fn test_reopened_append_regions_allocate_no_ring_until_used() {
use std::path::Path;
use store_io_sim::{SimConfig, SimPlatform};
use crate::store::{Store, StoreOptions};
let p = SimPlatform::new(SimConfig::volatile(61));
let s = Store::create(p.clone(), Path::new("/db"), StoreOptions::default()).unwrap();
for i in 0..64 {
let _r = s
.provision_append_region(&format!("a{i}"), 1 << 20)
.unwrap();
}
drop(s);
let s = Store::open(p, Path::new("/db"), StoreOptions::default()).unwrap();
let rings = |s: &Store<SimPlatform>| -> Vec<(String, usize)> {
s.regions_snapshot()
.iter()
.map(|r| {
let f = r.frontier.as_ref().unwrap();
(r.name.as_str().to_owned(), f.ring_slots())
})
.collect()
};
assert!(rings(&s).iter().all(|r| r.1 == 0), "{:?}", rings(&s));
let a7 = s.append_region("a7").unwrap();
let _at = a7.resume_at(0).unwrap();
assert!(
rings(&s).iter().all(|r| r.1 == 0),
"resume_at allocated one"
);
let _t = a7.append(b"x").unwrap();
let used: Vec<_> = rings(&s).into_iter().filter(|r| r.1 > 0).collect();
assert_eq!(used.len(), 1, "{used:?}");
assert_eq!(used[0].0, "a7");
}
#[test]
fn test_a_growable_regions_ring_is_the_windows() {
use std::path::Path;
use store_io_sim::{SimConfig, SimPlatform};
use crate::RegionOptions;
use crate::store::{Store, StoreOptions};
let p = SimPlatform::new(SimConfig::volatile(62));
let opts = StoreOptions {
container_format: store_io_format::slot::FORMAT_2,
region_capacity: 64,
append_window: 1 << 20,
..StoreOptions::default()
};
let window = ring_for(1 << 20, u64::MAX, 12);
assert_eq!(window, 256);
let s = Store::create(p.clone(), Path::new("/db"), opts.clone()).unwrap();
let g = s.provision_append_region("g", 64 << 10).unwrap();
let c = s
.provision_append_region_with(
"c",
RegionOptions::default().size(64 << 10).max_size(256 << 10),
)
.unwrap();
let ring = |s: &Store<SimPlatform>, name: &str| {
s.regions_snapshot()
.iter()
.find(|r| r.name.as_str() == name)
.and_then(|r| r.frontier.as_ref().map(AppendFrontier::ring_slots))
.unwrap()
};
let _t = g.append(b"x").unwrap();
let _t = c.append(b"x").unwrap();
assert_eq!((ring(&s, "g"), ring(&s, "c")), (window, 64));
drop((g, c, s));
let s = Store::open(p, Path::new("/db"), opts).unwrap();
let g = s.append_region("g").unwrap();
let c = s.append_region("c").unwrap();
let _p = g.resume_at(0).unwrap();
let _p = c.resume_at(0).unwrap();
let _t = g.append(b"x").unwrap();
let _t = c.append(b"x").unwrap();
assert_eq!((ring(&s, "g"), ring(&s, "c")), (window, 64), "at the open");
let g = g.recycle().unwrap();
let c = c.recycle().unwrap();
let _t = g.append(b"x").unwrap();
let _t = c.append(b"x").unwrap();
assert_eq!(
(ring(&s, "g"), ring(&s, "c")),
(window, 64),
"after a recycle"
);
}
fn f() -> AppendFrontier {
AppendFrontier::new(0, 1 << 20, 12, 64)
}
#[test]
fn test_ring_for_counts_the_window_in_blocks_of_the_region() {
let big = 1 << 40;
assert_eq!(ring_for(16 << 20, big, 12), 4096);
assert_eq!(
ring_for(16 << 20, big, 9),
32_768,
"512 B blocks hold the same bytes"
);
assert_eq!(ring_for(0, big, 12), 2);
assert_eq!(ring_for(4096, big, 12), 2);
assert_eq!(ring_for(u64::MAX, u64::MAX, 9), 1 << 20);
assert_eq!(
ring_for(10 << 20, big, 12),
2048,
"rounded down, never more"
);
assert_eq!(
ring_for(16 << 20, 64 << 10, 12),
16,
"bounded by the region"
);
assert_eq!(
ring_for(16 << 20, 12 << 20, 12),
4096,
"a region below the window never limits itself"
);
assert_eq!(
ring_for(12 << 20, 12 << 20, 12),
4096,
"nor one the window's size"
);
}
#[test]
fn test_the_default_window_holds_eight_mib_in_flight_at_512_byte_blocks() {
let limit = 64 << 20;
let window = crate::StoreOptions::default().append_window;
let fr = AppendFrontier::new(0, limit, 9, ring_for(window, limit, 9));
for i in 0..8 {
let r = fr.reserve(1 << 20);
assert!(r.is_ok(), "append {i} refused: {r:?}");
}
}
#[test]
fn test_reserve_rounds_to_blocks_and_never_overlaps() {
let fr = f();
let a = fr.reserve(100).unwrap_or_else(|e| panic!("{e:?}"));
let b = fr.reserve(5000).unwrap_or_else(|e| panic!("{e:?}"));
assert_eq!(
a,
Reservation {
start: 0,
data_end: 100,
end: 4096
}
);
assert_eq!(
b,
Reservation {
start: 4096,
data_end: 9096,
end: 12288
}
);
assert_eq!(fr.reserve(0), Err(NotWrittenCause::Empty));
assert_eq!(fr.reserve(1 << 20), Err(NotWrittenCause::RegionFull));
}
#[test]
fn test_out_of_order_completion_advances_prefix_only_when_contiguous() {
let fr = f();
let r: Vec<_> = (0..4)
.map(|_| fr.reserve(4096).unwrap_or_else(|e| panic!("{e:?}")))
.collect();
fr.complete(r[2]);
fr.complete(r[1]);
assert_eq!(fr.completed(), 0);
fr.complete(r[0]);
assert_eq!(fr.completed(), 3 * 4096);
fr.complete(r[3]);
assert_eq!(fr.completed(), 4 * 4096);
}
#[test]
fn test_ring_bound_refuses_runaway_reservations() {
let fr = AppendFrontier::new(0, 1 << 30, 12, 4);
for _ in 0..4 {
assert!(fr.reserve(4096).is_ok());
}
assert_eq!(fr.reserve(4096), Err(NotWrittenCause::TooManyInFlight));
}
#[test]
fn test_the_opens_registry_vouches_only_for_an_unbroken_lineage() {
let v = VolumeId::from_bytes([9; 16]);
let f1 = store_io_platform::FileIdentity {
volume: 1,
file: 10,
};
let f2 = store_io_platform::FileIdentity {
volume: 1,
file: 11,
};
let e = 1u64 << 50;
note_open(v, f1, e, None);
note_close(e, Some(7));
note_open(v, f1, e + 1, Some(7));
assert_eq!(earlier_open(e + 1, e), Earlier::Same { vouched: true });
note_close(e + 1, Some(9));
note_open(v, f1, e + 2, Some(12));
assert_eq!(earlier_open(e + 2, e), Earlier::Same { vouched: false });
assert_eq!(earlier_open(e + 2, e + 1), Earlier::Same { vouched: false });
note_close(e + 2, Some(14));
note_open(v, f1, e + 3, Some(14));
assert_eq!(earlier_open(e + 3, e + 2), Earlier::Same { vouched: true });
assert_eq!(earlier_open(e + 3, e + 1), Earlier::Same { vouched: false });
note_close(e + 3, None);
note_open(v, f1, e + 4, Some(16));
assert_eq!(earlier_open(e + 4, e + 3), Earlier::Same { vouched: false });
note_open(v, f2, e + 5, Some(16));
assert_eq!(earlier_open(e + 5, e + 3), Earlier::Other);
assert_eq!(earlier_open(e + 6, e + 3), Earlier::Unknown);
assert_eq!(earlier_open(e + 4, e + 7), Earlier::Unknown);
}
#[test]
fn test_the_resume_registry_answers_for_every_later_open() {
let key = (
VolumeId::from_bytes([7; 16]),
RegionId::from_raw(3),
Generation::from_raw(1).unwrap(),
);
record_resume(key, 5, 8192);
record_resume(key, 5, 16384);
assert!(resumed_below(key, 4, 8193));
assert!(!resumed_below(key, 4, 8192), "at the base is not below it");
assert!(!resumed_below(key, 5, 1 << 20), "only later opens count");
record_resume(key, 6, 4096);
assert!(resumed_below(key, 5, 8192));
assert!(!resumed_below(key, 5, 4096));
record_resume(key, 7, 65536);
assert!(resumed_below(key, 4, 8192));
assert!(resumed_below(key, 6, 65537));
assert!(!resumed_below(key, 7, u64::MAX));
let other = (key.0, RegionId::from_raw(4), key.2);
assert!(!resumed_below(other, 0, u64::MAX));
}
#[test]
fn test_the_resume_registry_is_bounded_and_only_adds_refusals() {
let key = (
VolumeId::from_bytes([8; 16]),
RegionId::from_raw(1),
Generation::from_raw(1).unwrap(),
);
for i in 0..MAX_RESUMES as u64 + 10 {
record_resume(key, 10 + i, 4096 * (i + 1));
}
assert_eq!(resumes().get(&key).map(Vec::len), Some(MAX_RESUMES));
for i in 0..MAX_RESUMES as u64 + 10 {
assert!(resumed_below(key, 9 + i, 4096 * (i + 1) + 1), "{i}");
}
assert!(resumed_below(key, 15, 4097));
}
#[test]
fn test_resume_only_moves_forward_and_only_when_idle() {
let fr = f();
assert_eq!(fr.resume_at(5000), Ok(8192));
assert_eq!(fr.resume_at(100), Ok(8192));
let r = fr.reserve(1).unwrap_or_else(|e| panic!("{e:?}"));
assert_eq!(r.start, 8192);
assert_eq!(fr.resume_at(1 << 19), Err(NotWrittenCause::TooManyInFlight));
fr.complete(r);
assert_eq!(fr.durable(), 8192);
fr.publish_durable(r.end);
fr.publish_durable(0);
assert_eq!(fr.durable(), r.end);
}
#[test]
fn test_concurrent_appenders_reach_a_gapless_prefix() {
let fr = Arc::new(AppendFrontier::new(0, 1 << 30, 12, 1024));
let handles: Vec<_> = (0..8)
.map(|t| {
let fr = Arc::clone(&fr);
std::thread::spawn(move || {
let mut seed = 0x9E37_79B9u64 + t;
for _ in 0..2_000 {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
let len = 1 + seed % 20_000;
loop {
match fr.reserve(len) {
Ok(r) => {
fr.complete(r);
break;
}
Err(NotWrittenCause::TooManyInFlight) => std::hint::spin_loop(),
Err(e) => panic!("{e:?}"),
}
}
}
})
})
.collect();
for h in handles {
assert!(h.join().is_ok());
}
assert_eq!(
fr.completed(),
fr.tail(),
"every reservation completed, so the prefix reaches the tail"
);
}
#[test]
fn test_waiter_wakes_when_prefix_arrives() {
let fr = Arc::new(f());
let a = fr.reserve(4096).unwrap_or_else(|e| panic!("{e:?}"));
let b = fr.reserve(4096).unwrap_or_else(|e| panic!("{e:?}"));
fr.complete(b);
let waiter = {
let fr = Arc::clone(&fr);
std::thread::spawn(move || fr.wait_completed(b.end, || false))
};
std::thread::yield_now();
fr.complete(a);
assert_eq!(waiter.join().ok(), Some(true));
}
#[test]
fn test_reserve_wait_blocks_until_the_ring_drains() {
let fr = Arc::new(AppendFrontier::new(0, 1 << 30, 12, 4));
let held: Vec<_> = (0..4)
.map(|_| fr.reserve(4096).unwrap_or_else(|e| panic!("{e:?}")))
.collect();
assert_eq!(fr.reserve(4096), Err(NotWrittenCause::TooManyInFlight));
let started = Arc::new(std::sync::Barrier::new(2));
let waiter = {
let fr = Arc::clone(&fr);
let started = Arc::clone(&started);
std::thread::spawn(move || {
let _leader = started.wait();
fr.reserve_wait(4096, || false)
})
};
let _leader = started.wait();
for r in held {
fr.complete(r);
}
let got = waiter.join().ok().and_then(Result::ok);
assert_eq!(got.map(|r| r.start), Some(4 * 4096));
}
#[test]
fn test_reserve_wait_refuses_once_told_to_give_up() {
let fr = AppendFrontier::new(0, 1 << 30, 12, 4);
assert_eq!(
fr.reserve_wait(4096, || true),
Err(NotWrittenCause::TooManyInFlight)
);
assert_eq!(fr.tail(), 0, "reserved on a poisoned store");
}
#[test]
fn test_reserve_wait_gives_up_when_told() {
let fr = Arc::new(AppendFrontier::new(0, 1 << 30, 12, 4));
for _ in 0..4 {
assert!(fr.reserve(4096).is_ok());
}
let give_up = Arc::new(std::sync::atomic::AtomicBool::new(false));
let waiter = {
let fr = Arc::clone(&fr);
let give_up = Arc::clone(&give_up);
std::thread::spawn(move || {
fr.reserve_wait(4096, || give_up.load(std::sync::atomic::Ordering::SeqCst))
})
};
give_up.store(true, std::sync::atomic::Ordering::SeqCst);
fr.wake_all();
assert_eq!(
waiter.join().ok(),
Some(Err(NotWrittenCause::TooManyInFlight))
);
}
}
#[cfg(all(test, loom))]
mod loom_tests {
use super::*;
use loom::sync::Arc;
#[test]
fn loom_a_raised_limit_racing_a_reservation() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 4096, 12, 4));
let r = fr.reserve(4096).unwrap();
fr.complete(r);
let raiser = {
let fr = fr.clone();
loom::thread::spawn(move || fr.raise_limit(8192))
};
let got = fr.reserve(4096);
raiser.join().unwrap();
match got {
Ok(r) => assert_eq!((r.start, r.end), (4096, 8192)),
Err(cause) => {
assert_eq!(cause, NotWrittenCause::RegionFull);
assert!(fr.reserve(4096).is_ok(), "the raised limit was lost");
}
}
});
}
#[test]
fn loom_two_appenders_reach_the_tail() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 4));
let h: Vec<_> = (0..2)
.map(|_| {
let fr = fr.clone();
loom::thread::spawn(move || {
if let Ok(r) = fr.reserve(4096) {
fr.complete(r);
}
})
})
.collect();
for t in h {
let _joined = t.join();
}
assert_eq!(fr.completed(), fr.tail());
});
}
#[test]
fn loom_a_waiter_for_room_sees_the_ring_drain() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 2));
let a = fr.reserve(4096).unwrap_or_else(|_| unreachable!());
let b = fr.reserve(4096).unwrap_or_else(|_| unreachable!());
let done = {
let fr = fr.clone();
loom::thread::spawn(move || {
fr.complete(a);
fr.complete(b);
})
};
let waiter = {
let fr = fr.clone();
loom::thread::spawn(move || fr.reserve_wait(4096, || false).is_ok())
};
let _joined = done.join();
assert_eq!(waiter.join().ok(), Some(true));
});
}
#[test]
fn loom_the_last_completion_wakes_its_waiter() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 4));
let a = fr.reserve(4096).unwrap_or_else(|_| unreachable!());
let done = {
let fr = fr.clone();
loom::thread::spawn(move || fr.complete(a))
};
let waiter = {
let fr = fr.clone();
loom::thread::spawn(move || fr.wait_completed(a.end, || false))
};
let _joined = done.join();
assert_eq!(waiter.join().ok(), Some(true));
});
}
#[test]
fn loom_an_append_racing_resume_is_never_stranded() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 4));
let resume = {
let fr = fr.clone();
loom::thread::spawn(move || {
let _r = fr.resume_at(4096);
})
};
let append = {
let fr = fr.clone();
loom::thread::spawn(move || {
if let Ok(r) = fr.reserve(4096) {
fr.complete(r);
}
})
};
let _a = resume.join();
let _b = append.join();
assert_eq!(fr.completed(), fr.tail(), "a completion was stranded");
});
}
#[test]
fn loom_a_waiter_racing_resume_is_woken() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 2));
let resume = {
let fr = fr.clone();
loom::thread::spawn(move || {
let _r = fr.resume_at(4 * 4096);
})
};
let waiter = {
let fr = fr.clone();
loom::thread::spawn(move || fr.reserve_wait(4096, || false).is_ok())
};
let _a = resume.join();
assert_eq!(waiter.join().ok(), Some(true));
});
}
#[test]
fn loom_resume_to_the_tail_never_moves_the_prefix_back() {
loom::model(|| {
let fr = Arc::new(AppendFrontier::new(0, 1 << 20, 12, 4));
let resume = {
let fr = fr.clone();
loom::thread::spawn(move || {
let _r = fr.resume_at(0);
})
};
let append = {
let fr = fr.clone();
loom::thread::spawn(move || {
if let Ok(r) = fr.reserve(4096) {
fr.complete(r);
}
})
};
let _a = resume.join();
let _b = append.join();
assert_eq!(fr.completed(), fr.tail(), "the prefix moved back");
});
}
}