use super::page_index::PageIndex;
use crate::error::{DbError, DbResult};
use crate::sync::{self, Condvar, Mutex};
use std::sync::{Arc, OnceLock};
use std::time::Instant;
pub(crate) fn now_ms() -> u64 {
static ANCHOR: OnceLock<Instant> = OnceLock::new();
let anchor = *ANCHOR.get_or_init(Instant::now);
u64::try_from(anchor.elapsed().as_millis()).unwrap_or(u64::MAX)
}
pub(crate) enum BuildError {
Io {
errno: Option<i32>,
kind: std::io::ErrorKind,
message: String,
},
Corrupt {
segment_id: u64,
block: Option<u32>,
path: std::path::PathBuf,
reason: String,
},
Internal(&'static str),
FormatMismatch(String),
Other(String),
}
impl BuildError {
fn from_error(e: &DbError) -> Self {
match e {
DbError::Io(e) => Self::Io {
errno: e.raw_os_error(),
kind: e.kind(),
message: e.to_string(),
},
DbError::SegmentCorrupt {
segment_id,
block,
path,
reason,
} => Self::Corrupt {
segment_id: *segment_id,
block: *block,
path: path.clone(),
reason: reason.clone(),
},
DbError::Internal(message) => Self::Internal(message),
DbError::FormatMismatch(message) => Self::FormatMismatch(message.clone()),
other => Self::Other(other.to_string()),
}
}
fn replay(&self) -> DbError {
match self {
Self::Io {
errno,
kind,
message,
} => DbError::Io(match errno {
Some(errno) => std::io::Error::from_raw_os_error(*errno),
None => std::io::Error::new(*kind, message.clone()),
}),
Self::Corrupt {
segment_id,
block,
path,
reason,
} => DbError::SegmentCorrupt {
segment_id: *segment_id,
block: *block,
path: path.clone(),
reason: reason.clone(),
},
Self::Internal(message) => DbError::Internal(message),
Self::FormatMismatch(message) => DbError::FormatMismatch(message.clone()),
Self::Other(message) => DbError::Io(std::io::Error::other(message.clone())),
}
}
}
pub(crate) enum SkeletonState {
Ready(Arc<PageIndex>),
Pending,
Building(Arc<BuildAttempt>),
Failed {
retry_at_ms: u64,
failures: u32,
error: Arc<BuildError>,
},
}
type BuildOutcome = Result<Arc<PageIndex>, Arc<BuildError>>;
pub(crate) struct BuildAttempt {
outcome: Mutex<Option<BuildOutcome>>,
cv: Condvar,
}
impl BuildAttempt {
fn new() -> Self {
Self {
outcome: Mutex::new(None),
cv: Condvar::new(),
}
}
fn complete(&self, outcome: BuildOutcome) {
*sync::lock(&self.outcome) = Some(outcome);
self.cv.notify_all();
}
fn wait(&self, #[cfg(test)] cell: &SkeletonCell) -> DbResult<Arc<PageIndex>> {
let mut outcome = sync::lock(&self.outcome);
while outcome.is_none() {
outcome = sync::cv_wait(&self.cv, outcome);
}
#[cfg(test)]
{
drop(outcome);
if let Some((paused, resume)) = sync::lock(&cell.waiter_pause).take() {
paused.send(()).unwrap();
resume
.recv_timeout(std::time::Duration::from_secs(5))
.unwrap();
}
outcome = sync::lock(&self.outcome);
}
match outcome
.as_ref()
.expect("completed skeleton attempt has an outcome")
{
Ok(index) => Ok(index.clone()),
Err(error) => Err(error.replay()),
}
}
}
#[cfg(test)]
type WaiterPause = (std::sync::mpsc::Sender<()>, std::sync::mpsc::Receiver<()>);
pub(crate) struct SkeletonCell {
state: Mutex<SkeletonState>,
#[cfg(test)]
waiters: std::sync::atomic::AtomicUsize,
#[cfg(test)]
waiter_pause: Mutex<Option<WaiterPause>>,
}
impl SkeletonCell {
fn new(state: SkeletonState) -> Self {
Self {
state: Mutex::new(state),
#[cfg(test)]
waiters: std::sync::atomic::AtomicUsize::new(0),
#[cfg(test)]
waiter_pause: Mutex::new(None),
}
}
pub(crate) fn ready(index: Arc<PageIndex>) -> Self {
Self::new(SkeletonState::Ready(index))
}
pub(crate) fn pending() -> Self {
Self::new(SkeletonState::Pending)
}
pub(crate) fn get(&self) -> Option<Arc<PageIndex>> {
match &*sync::lock(&self.state) {
SkeletonState::Ready(p) => Some(p.clone()),
_ => None,
}
}
pub(crate) fn is_not_ready(&self) -> bool {
!matches!(*sync::lock(&self.state), SkeletonState::Ready(_))
}
pub(crate) fn is_pending(&self, now_ms: u64) -> bool {
match &*sync::lock(&self.state) {
SkeletonState::Pending => true,
SkeletonState::Failed { retry_at_ms, .. } => *retry_at_ms <= now_ms,
_ => false,
}
}
pub(crate) fn get_or_build(
&self,
slots: &BuildSlots,
now_ms: u64,
build: impl FnOnce() -> DbResult<PageIndex>,
) -> DbResult<Arc<PageIndex>> {
let started = Instant::now();
let mut state = sync::lock(&self.state);
let failures = match &*state {
SkeletonState::Ready(p) => return Ok(p.clone()),
SkeletonState::Building(attempt) => {
let attempt = attempt.clone();
#[cfg(test)]
self.waiters
.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
drop(state);
#[cfg(not(test))]
let result = attempt.wait();
#[cfg(test)]
let result = attempt.wait(self);
#[cfg(test)]
self.waiters
.fetch_sub(1, std::sync::atomic::Ordering::SeqCst);
return result;
}
SkeletonState::Failed {
retry_at_ms, error, ..
} if *retry_at_ms > now_ms => {
return Err(error.replay());
}
SkeletonState::Failed { failures, .. } => *failures,
SkeletonState::Pending => 0,
};
let attempt = Arc::new(BuildAttempt::new());
*state = SkeletonState::Building(attempt.clone());
drop(state);
let slot = slots.acquire();
let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(build));
drop(slot);
let failures = failures.saturating_add(1);
let delay = 1000u64
.saturating_mul(1u64 << failures.saturating_sub(1).min(6))
.min(60_000);
let failed = |error| SkeletonState::Failed {
retry_at_ms: now_ms
.saturating_add(u64::try_from(started.elapsed().as_millis()).unwrap_or(u64::MAX))
.saturating_add(delay),
failures,
error,
};
let publish = |state, outcome| {
*sync::lock(&self.state) = state;
attempt.complete(outcome);
};
match result {
Ok(Ok(p)) => {
let p = Arc::new(p);
publish(SkeletonState::Ready(p.clone()), Ok(p.clone()));
Ok(p)
}
Ok(Err(e)) => {
let error = Arc::new(BuildError::from_error(&e));
publish(failed(error.clone()), Err(error));
Err(e)
}
Err(panic) => {
let error = Arc::new(BuildError::Internal("segment skeleton builder panicked"));
publish(failed(error.clone()), Err(error));
std::panic::resume_unwind(panic);
}
}
}
}
pub(crate) struct BuildSlots {
busy: Mutex<usize>,
cv: Condvar,
max: usize,
#[cfg(test)]
waiters: std::sync::atomic::AtomicUsize,
}
struct BuildSlot<'a>(&'a BuildSlots);
impl Drop for BuildSlot<'_> {
fn drop(&mut self) {
*sync::lock(&self.0.busy) -= 1;
self.0.cv.notify_one();
}
}
impl BuildSlots {
pub(crate) fn new(max: usize) -> Self {
assert!(max > 0);
Self {
busy: Mutex::new(0),
cv: Condvar::new(),
max,
#[cfg(test)]
waiters: std::sync::atomic::AtomicUsize::new(0),
}
}
fn acquire(&self) -> BuildSlot<'_> {
let mut busy = sync::lock(&self.busy);
while *busy >= self.max {
#[cfg(test)]
self.waiters
.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
busy = sync::cv_wait(&self.cv, busy);
#[cfg(test)]
self.waiters
.fetch_sub(1, std::sync::atomic::Ordering::SeqCst);
}
*busy += 1;
BuildSlot(self)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::DbError;
use crate::seg::{core::SegShared, fs::real, segment::Segment, testkit};
use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
use std::time::{Duration, Instant};
fn sample() -> PageIndex {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_segment(real(), dir.path(), 1, &testkit::entries(20, 1));
(*Segment::open(
real(),
dir.path(),
&rec,
testkit::KEY_LEN as u16,
testkit::SEED,
&Arc::new(SegShared::new()),
)
.unwrap()
.skeleton()
.unwrap())
.clone()
}
fn until(f: impl Fn() -> bool) {
let deadline = Instant::now() + Duration::from_secs(5);
while !f() {
assert!(Instant::now() < deadline, "scheduling barrier timed out");
std::thread::yield_now();
}
}
#[test]
fn a_second_reader_waits_for_the_first_build() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
let builds = AtomicUsize::new(0);
let page = sample();
let (started, recv) = std::sync::mpsc::channel();
let (release, gate) = std::sync::mpsc::channel();
std::thread::scope(|s| {
let (cell, slots, builds) = (&cell, &slots, &builds);
let first = s.spawn(move || {
cell.get_or_build(slots, 0, || {
builds.fetch_add(1, SeqCst);
started.send(()).unwrap();
gate.recv_timeout(Duration::from_secs(5)).unwrap();
Ok(page)
})
});
recv.recv_timeout(Duration::from_secs(5)).unwrap();
let second = s.spawn(move || cell.get_or_build(slots, 0, || panic!("duplicate build")));
until(|| cell.waiters.load(SeqCst) == 1);
assert!(cell.get().is_none());
assert!(cell.is_not_ready());
release.send(()).unwrap();
assert!(Arc::ptr_eq(
&first.join().unwrap().unwrap(),
&second.join().unwrap().unwrap()
));
});
assert_eq!(builds.load(SeqCst), 1);
}
fn retry_deadline(cell: &SkeletonCell) -> u64 {
match &*crate::sync::lock(&cell.state) {
SkeletonState::Failed { retry_at_ms, .. } => *retry_at_ms,
_ => panic!("expected failed attempt"),
}
}
#[test]
fn a_failed_build_backs_off_and_retries_with_typed_errors() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
assert!(matches!(cell.get_or_build(&slots, 1000, || Err(DbError::Io(
std::io::Error::from_raw_os_error(13)))), Err(DbError::Io(e)) if e.raw_os_error() == Some(13)));
let first_deadline = retry_deadline(&cell);
assert!(first_deadline >= 2000);
assert!(!cell.is_pending(1000));
assert!(cell.is_not_ready());
assert!(
matches!(cell.get_or_build(&slots, first_deadline - 1, || panic!("not due")),
Err(DbError::Io(e)) if e.raw_os_error() == Some(13))
);
assert!(cell.is_pending(first_deadline));
assert!(
cell.get_or_build(&slots, first_deadline, || Err(DbError::Internal("second")))
.is_err()
);
let second_deadline = retry_deadline(&cell);
assert!(second_deadline >= first_deadline + 2000);
assert!(!cell.is_pending(second_deadline - 1));
assert!(cell.is_pending(second_deadline));
assert!(
cell.get_or_build(&slots, second_deadline, || Ok(sample()))
.is_ok()
);
assert!(!cell.is_not_ready());
}
#[test]
fn backoff_deadlines_follow_a_monotonic_clock() {
let wall = u64::try_from(
std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap()
.as_millis(),
)
.unwrap();
let first = now_ms();
assert!(first < wall / 2, "{first} looks like wall-clock time");
std::thread::sleep(Duration::from_millis(5));
assert!(now_ms() >= first + 5);
}
#[test]
fn a_replayed_build_error_keeps_its_format_mismatch_type() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
let unsupported = || Err(DbError::FormatMismatch("filter kind 9".into()));
assert!(matches!(
cell.get_or_build(&slots, 0, unsupported),
Err(DbError::FormatMismatch(m)) if m == "filter kind 9"
));
assert!(matches!(
cell.get_or_build(&slots, 1, || panic!("in backoff")),
Err(DbError::FormatMismatch(m)) if m == "filter kind 9"
));
}
#[test]
fn backoff_caps_at_sixty_seconds_and_panic_releases_the_slot() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
let mut now = 0;
for delay in [1000, 2000, 4000, 8000, 16000, 32000, 60000, 60000] {
assert!(
cell.get_or_build(&slots, now, || Err(DbError::Internal("failure")))
.is_err()
);
let deadline = retry_deadline(&cell);
assert!(deadline >= now + delay);
assert!(!cell.is_pending(deadline - 1));
assert!(cell.is_pending(deadline));
now = deadline;
}
let cell = SkeletonCell::pending();
assert!(
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
let _ = cell.get_or_build(&slots, 0, || panic!("builder panic"));
}))
.is_err()
);
assert_eq!(*crate::sync::lock(&slots.busy), 0);
assert!(matches!(
cell.get_or_build(&slots, 0, || panic!("backoff")),
Err(DbError::Internal("segment skeleton builder panicked"))
));
let deadline = retry_deadline(&cell);
assert!(cell.get_or_build(&slots, deadline, || Ok(sample())).is_ok());
}
#[test]
fn waiting_readers_share_the_original_typed_error() {
for io in [false, true] {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
let (started, recv) = std::sync::mpsc::channel();
let (release, gate) = std::sync::mpsc::channel();
std::thread::scope(|s| {
let (cell, slots) = (&cell, &slots);
let first = s.spawn(move || {
cell.get_or_build(slots, 1000, || {
started.send(()).unwrap();
gate.recv_timeout(Duration::from_secs(5)).unwrap();
Err(if io {
DbError::Io(std::io::Error::from_raw_os_error(13))
} else {
DbError::SegmentCorrupt {
segment_id: 7,
block: Some(3),
path: "original.sidx".into(),
reason: "checksum mismatch".into(),
}
})
})
});
recv.recv_timeout(Duration::from_secs(5)).unwrap();
let second =
s.spawn(move || cell.get_or_build(slots, 100_000, || panic!("duplicate")));
until(|| cell.waiters.load(SeqCst) == 1);
release.send(()).unwrap();
for result in [
first.join().unwrap(),
second.join().unwrap(),
cell.get_or_build(slots, 1000, || panic!("backoff")),
] {
if io {
assert!(
matches!(result, Err(DbError::Io(e)) if e.raw_os_error() == Some(13))
);
} else {
assert!(
matches!(result, Err(DbError::SegmentCorrupt { segment_id: 7,
block: Some(3), path, reason }) if path == std::path::Path::new("original.sidx")
&& reason == "checksum mismatch")
);
}
}
});
}
}
#[test]
fn a_panicking_builder_completes_its_waiting_reader_and_releases_the_slot() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(1);
let (started, started_rx) = std::sync::mpsc::channel();
let (release, release_rx) = std::sync::mpsc::channel();
std::thread::scope(|scope| {
let (cell, slots) = (&cell, &slots);
let builder = scope.spawn(move || {
cell.get_or_build(slots, 0, || {
started.send(()).unwrap();
release_rx.recv_timeout(Duration::from_secs(5)).unwrap();
panic!("builder panic with waiting reader");
})
});
started_rx.recv_timeout(Duration::from_secs(5)).unwrap();
let waiter =
scope.spawn(move || cell.get_or_build(slots, 100_000, || panic!("duplicate")));
until(|| cell.waiters.load(SeqCst) == 1);
release.send(()).unwrap();
assert!(builder.join().is_err());
assert!(matches!(
waiter.join().unwrap(),
Err(DbError::Internal("segment skeleton builder panicked"))
));
});
assert_eq!(*sync::lock(&slots.busy), 0);
assert!(cell.get_or_build(&slots, 100_000, || Ok(sample())).is_ok());
}
#[test]
fn failed_retry_deadline_saturates_without_wrapping() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(1);
assert!(
cell.get_or_build(&slots, u64::MAX - 500, || Err(DbError::Internal("failure")))
.is_err()
);
assert!(!cell.is_pending(u64::MAX - 1));
assert!(cell.is_pending(u64::MAX));
}
#[test]
fn a_competing_retry_cannot_replace_a_waiters_original_typed_failure() {
for io in [false, true] {
for retry_succeeds in [false, true] {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(2);
let page = sample();
let (started, started_rx) = std::sync::mpsc::channel();
let (finish, finish_rx) = std::sync::mpsc::channel();
let (paused, paused_rx) = std::sync::mpsc::channel();
let (resume, resume_rx) = std::sync::mpsc::channel();
*sync::lock(&cell.waiter_pause) = Some((paused, resume_rx));
std::thread::scope(|scope| {
let (cell, slots) = (&cell, &slots);
let builder = scope.spawn(move || {
cell.get_or_build(slots, 1000, || {
started.send(()).unwrap();
finish_rx.recv_timeout(Duration::from_secs(5)).unwrap();
Err(if io {
DbError::Io(std::io::Error::from_raw_os_error(13))
} else {
DbError::SegmentCorrupt {
segment_id: 7,
block: Some(3),
path: "original.sidx".into(),
reason: "checksum mismatch".into(),
}
})
})
});
started_rx.recv_timeout(Duration::from_secs(5)).unwrap();
let waiter = scope.spawn(move || {
cell.get_or_build(slots, 100_000, || panic!("waiter rebuilt"))
});
until(|| cell.waiters.load(SeqCst) == 1);
finish.send(()).unwrap();
assert!(builder.join().unwrap().is_err());
paused_rx.recv_timeout(Duration::from_secs(5)).unwrap();
let retry = cell.get_or_build(slots, 100_000, || {
if retry_succeeds {
Ok(page)
} else {
Err(DbError::Internal("different attempt"))
}
});
assert_eq!(retry.is_ok(), retry_succeeds);
resume.send(()).unwrap();
let original = waiter.join().unwrap();
if io {
assert!(
matches!(original, Err(DbError::Io(e)) if e.raw_os_error() == Some(13)),
"waiter lost original Io"
);
} else {
assert!(
matches!(original, Err(DbError::SegmentCorrupt {segment_id: 7, block: Some(3), path, reason})
if path == std::path::Path::new("original.sidx") && reason == "checksum mismatch"),
"waiter lost original corruption"
);
}
});
}
}
}
#[test]
fn failed_build_backoff_includes_time_waiting_for_a_slot() {
let cell = SkeletonCell::pending();
let slots = BuildSlots::new(1);
let occupied = slots.acquire();
std::thread::scope(|scope| {
let build = scope.spawn(|| {
cell.get_or_build(&slots, 1000, || Err(DbError::Internal("slow failure")))
});
until(|| slots.waiters.load(SeqCst) == 1);
let start = Instant::now();
while start.elapsed() < Duration::from_millis(20) {
std::thread::yield_now();
}
drop(occupied);
assert!(build.join().unwrap().is_err());
});
assert!(
!cell.is_pending(2010),
"slot wait consumed the retry backoff"
);
assert!(cell.is_pending(100_000));
}
#[test]
fn at_most_two_foreground_builds_run_at_once() {
let slots = BuildSlots::new(2);
let cells = [
SkeletonCell::pending(),
SkeletonCell::pending(),
SkeletonCell::pending(),
];
let active = AtomicUsize::new(0);
let high = AtomicUsize::new(0);
let page = sample();
let gate = std::sync::Barrier::new(3);
std::thread::scope(|s| {
for cell in &cells[..2] {
let page = page.clone();
let (slots, active, high, gate) = (&slots, &active, &high, &gate);
s.spawn(move || {
cell.get_or_build(slots, 0, || {
let n = active.fetch_add(1, SeqCst) + 1;
high.fetch_max(n, SeqCst);
gate.wait();
active.fetch_sub(1, SeqCst);
Ok(page)
})
.unwrap()
});
}
until(|| active.load(SeqCst) == 2);
let third = s.spawn(|| {
cells[2]
.get_or_build(&slots, 0, || {
let n = active.fetch_add(1, SeqCst) + 1;
high.fetch_max(n, SeqCst);
active.fetch_sub(1, SeqCst);
Ok(page.clone())
})
.unwrap()
});
until(|| slots.waiters.load(SeqCst) == 1);
assert_eq!(active.load(SeqCst), 2);
gate.wait();
third.join().unwrap();
});
assert_eq!(high.load(SeqCst), 2);
assert_eq!(*crate::sync::lock(&slots.busy), 0);
}
}