use std::ops::{Deref, DerefMut};
use std::sync::{Arc, Condvar, Mutex, MutexGuard, OnceLock, PoisonError, TryLockError};
use store_io_core::observe::{Counter, Observer};
use store_io_core::error::OsError;
use store_io_platform::{Completion, CompletionBuf, IoBuf, IoOp, Queue, RawResult, Rejected};
use crate::optable::Kind;
use crate::queue_core::Core;
use crate::sync::{AtomicBool, AtomicU64, Ordering};
pub(crate) struct QueueSet<Q> {
queues: Box<[Mutex<Lane<Q>>]>,
flush: Box<[Mutex<Lane<Q>>]>,
parallel: OnceLock<Box<[Mutex<Lane<Q>>]>>,
parallel_init: Mutex<()>,
parallel_workers: OnceLock<Option<usize>>,
parallel_off: AtomicBool,
depth: usize,
marks: Box<[Arc<LaneMark>]>,
waiters: AtomicU64,
wake: Mutex<()>,
returned: Condvar,
}
pub(crate) struct Lane<Q> {
core: Core<Q>,
pub(crate) done: CompletionBuf,
}
impl<Q: Queue> Lane<Q> {
pub(crate) fn submit(&mut self, op: IoOp<'_, Q::File>, tag: u64) -> Result<(), Rejected> {
let Some((index, qtag)) = self.core.table.claim() else {
let buf = match op {
IoOp::Write { buf, .. } | IoOp::Read { buf, .. } => Some(buf),
IoOp::FlushData { .. } => None,
};
return Err(Rejected { buf, raw: None });
};
self.core.table.start(index, tag, Kind::Raw, None, false);
self.core
.queue
.submit(op, qtag)
.inspect_err(|_| self.core.table.abort(index))
}
#[allow(clippy::type_complexity)]
pub(crate) fn perform<'a>(
&mut self,
op: IoOp<'a, Q::File>,
) -> Result<Result<(Option<IoBuf>, RawResult<usize>), IoOp<'a, Q::File>>, Rejected> {
if self.core.table.live > 0 || !self.done.is_empty() || !self.core.queue.performs() {
return Ok(Err(op));
}
struct Idle<'t>(&'t crate::optable::Table);
impl Drop for Idle<'_> {
fn drop(&mut self) {
self.0.publish();
}
}
self.core.table.busy();
let _idle = Idle(&self.core.table);
self.core.queue.perform(op)
}
pub(crate) fn wait(&mut self, min: usize) -> Result<usize, OsError> {
let waited = self.core.queue.wait(min, &mut self.core.raw);
let n = self.collect();
waited.map(|_| n)
}
pub(crate) fn in_flight(&self) -> usize {
self.core.table.live
}
fn collect(&mut self) -> usize {
let mut n = 0;
for c in self.core.raw.drain() {
let Some(tag) = self.core.table.take(c.tag) else {
debug_assert!(false, "a lane completion matched no row");
continue;
};
n += 1;
assert!(
self.done.push(Completion { tag, ..c }).is_ok(),
"a lane's completions overflowed"
);
}
n
}
}
#[repr(align(128))]
pub(crate) struct LaneMark(AtomicU64);
impl LaneMark {
pub(crate) fn new() -> Self {
Self(AtomicU64::new(0))
}
#[inline]
pub(crate) fn set(&self, v: u64) {
self.0.store(v, Ordering::Relaxed);
}
pub(crate) fn get(&self) -> u64 {
self.0.load(Ordering::Relaxed)
}
}
pub(crate) struct LaneGuard<'a, Q: Queue> {
guard: MutexGuard<'a, Lane<Q>>,
_notify: Option<Notify<'a, Q>>,
}
pub(crate) struct FlushGuard<'a, Q: Queue> {
guard: MutexGuard<'a, Lane<Q>>,
}
impl<Q: Queue> Deref for FlushGuard<'_, Q> {
type Target = Lane<Q>;
fn deref(&self) -> &Lane<Q> {
&self.guard
}
}
impl<Q: Queue> DerefMut for FlushGuard<'_, Q> {
fn deref_mut(&mut self) -> &mut Lane<Q> {
&mut self.guard
}
}
struct Notify<'a, Q> {
set: &'a QueueSet<Q>,
}
impl<Q> Drop for Notify<'_, Q> {
fn drop(&mut self) {
if self.set.waiters.fetch_add(0, Ordering::AcqRel) > 0 {
let _wake = self.set.wake.lock().unwrap_or_else(PoisonError::into_inner);
self.set.returned.notify_one();
}
}
}
impl<Q: Queue> LaneGuard<'_, Q> {
pub(crate) fn is_shared(&self) -> bool {
self._notify.is_some()
}
}
impl<Q: Queue> Deref for LaneGuard<'_, Q> {
type Target = Lane<Q>;
fn deref(&self) -> &Lane<Q> {
&self.guard
}
}
impl<Q: Queue> DerefMut for LaneGuard<'_, Q> {
fn deref_mut(&mut self) -> &mut Lane<Q> {
&mut self.guard
}
}
impl<Q: Queue> QueueSet<Q> {
pub(crate) fn new(queues: Vec<Q>, depth: usize) -> Self {
Self::build(queues, Vec::new(), depth)
}
pub(crate) fn with_flush_lanes(queues: Vec<Q>, flush: Vec<Q>, depth: usize) -> Self {
Self::build(queues, flush, depth)
}
fn build(queues: Vec<Q>, flush: Vec<Q>, depth: usize) -> Self {
let n = queues.len();
let marks: Box<[Arc<LaneMark>]> = (0..2 * n + flush.len().max(1))
.map(|_| Arc::new(LaneMark(AtomicU64::new(0))))
.collect();
Self {
queues: queues
.into_iter()
.zip(marks.iter())
.map(|(q, m)| lane(q, m, depth))
.collect(),
flush: flush
.into_iter()
.zip(&marks[2 * n..])
.map(|(q, m)| lane(q, m, depth))
.collect(),
parallel: OnceLock::new(),
parallel_init: Mutex::new(()),
parallel_workers: OnceLock::new(),
parallel_off: AtomicBool::new(false),
depth,
marks,
waiters: AtomicU64::new(0),
wake: Mutex::new(()),
returned: Condvar::new(),
}
}
pub(crate) fn flush_lane(&self, slot: usize) -> Option<FlushGuard<'_, Q>> {
self.flush.get(slot).map(|m| {
let guard = m.lock().unwrap_or_else(PoisonError::into_inner);
FlushGuard { guard }
})
}
pub(crate) fn get_parallel(
&self,
hint: usize,
make: impl FnOnce(usize) -> Option<Vec<Q>>,
) -> LaneGuard<'_, Q> {
let n = self.queues.len();
if self.parallel_off.load(Ordering::Relaxed) {
return self.get(hint);
}
let parallel = self.parallel.get().map(|b| &**b);
let Some(lanes) = parallel.or_else(|| self.create_parallel(make)) else {
return self.get(hint);
};
let found = (0..n).find_map(|i| {
let at = (hint % n + i) % n;
match lanes[at].try_lock() {
Ok(g) => Some((at, g)),
Err(TryLockError::Poisoned(p)) => Some((at, p.into_inner())),
Err(TryLockError::WouldBlock) => None,
}
});
let Some((_, guard)) = found else {
return self.get(hint);
};
LaneGuard {
guard,
_notify: None,
}
}
fn create_parallel(
&self,
make: impl FnOnce(usize) -> Option<Vec<Q>>,
) -> Option<&[Mutex<Lane<Q>>]> {
let _one = self
.parallel_init
.lock()
.unwrap_or_else(PoisonError::into_inner);
if let Some(lanes) = self.parallel.get() {
return Some(&**lanes);
}
if self.parallel_off.load(Ordering::Relaxed) {
return None;
}
let n = self.queues.len();
let Some(queues) = make(n).filter(|qs| qs.len() == n && n > 0) else {
self.parallel_off.store(true, Ordering::Relaxed);
return None;
};
let _workers = self
.parallel_workers
.set(queues.first().and_then(Queue::workers));
let lanes: Box<[Mutex<Lane<Q>>]> = queues
.into_iter()
.zip(&self.marks[n..2 * n])
.map(|(q, m)| lane(q, m, self.depth))
.collect();
let _set = self.parallel.set(lanes);
self.parallel.get().map(|b| &**b)
}
#[cfg(test)]
pub(crate) fn has_parallel(&self) -> bool {
self.parallel.get().is_some()
}
pub(crate) fn parallel_workers(&self) -> Option<usize> {
self.parallel_workers.get().copied().flatten()
}
pub(crate) fn flush_lanes(&self) -> usize {
self.flush.len()
}
pub(crate) fn keep_flush_lanes(&mut self, n: usize) {
let mut lanes = core::mem::take(&mut self.flush).into_vec();
lanes.truncate(n.max(1));
self.flush = lanes.into_boxed_slice();
}
pub(crate) fn shared_len(&self) -> usize {
self.queues.len()
}
pub(crate) fn marks(&self) -> impl ExactSizeIterator<Item = u64> + '_ {
self.marks.iter().map(|m| m.0.load(Ordering::Relaxed))
}
fn try_any(&self, hint: usize) -> Option<(usize, MutexGuard<'_, Lane<Q>>)> {
let n = self.queues.len();
(0..n).find_map(|i| {
let at = (hint % n + i) % n;
match self.queues[at].try_lock() {
Ok(g) => Some((at, g)),
Err(TryLockError::Poisoned(p)) => Some((at, p.into_inner())),
Err(TryLockError::WouldBlock) => None,
}
})
}
pub(crate) fn get(&self, hint: usize) -> LaneGuard<'_, Q> {
if let Some((_, guard)) = self.try_any(hint) {
return LaneGuard {
guard,
_notify: Some(Notify { set: self }),
};
}
let _registered = self.waiters.fetch_add(1, Ordering::AcqRel);
let mut wake = self.wake.lock().unwrap_or_else(PoisonError::into_inner);
let (_, guard) = loop {
if let Some(found) = self.try_any(hint) {
break found;
}
wake = self
.returned
.wait(wake)
.unwrap_or_else(PoisonError::into_inner);
};
drop(wake);
let _unregistered = self.waiters.fetch_sub(1, Ordering::AcqRel);
LaneGuard {
guard,
_notify: Some(Notify { set: self }),
}
}
}
pub(crate) fn solo_lane<Q>(queue: Q, depth: usize) -> Lane<Q> {
lane(queue, &Arc::new(LaneMark::new()), depth)
.into_inner()
.unwrap_or_else(PoisonError::into_inner)
}
fn lane<Q>(queue: Q, mark: &Arc<LaneMark>, depth: usize) -> Mutex<Lane<Q>> {
let depth = depth.max(1);
Mutex::new(Lane {
core: Core::new(queue, depth, Arc::clone(mark)),
done: CompletionBuf::with_capacity(depth),
})
}
pub(crate) enum Ran {
Done {
buf: Option<IoBuf>,
result: RawResult<usize>,
},
Abandoned(OsError),
}
pub(crate) fn clear_stale<Q: Queue>(lane: &mut Lane<Q>) -> Result<(), OsError> {
if lane.done.is_empty() && lane.in_flight() == 0 && lane.core.queue.in_flight() == 0 {
return Ok(());
}
lane.done.drain().for_each(drop);
while lane.core.queue.in_flight() > 0 {
let n = lane.core.queue.in_flight();
let _added = lane.wait(n)?;
lane.done.drain().for_each(drop);
}
debug_assert_eq!(lane.in_flight(), 0, "lane rows outlived their operations");
if lane.in_flight() > 0 {
lane.core.table.forget();
}
Ok(())
}
pub(crate) fn run<Q: Queue>(
slot: &mut Lane<Q>,
op: IoOp<'_, Q::File>,
) -> Result<Ran, (Option<IoBuf>, Option<OsError>)> {
const TAG: u64 = 0x5110;
let is_read = matches!(op, IoOp::Read { .. });
if let Err(raw) = clear_stale(slot) {
drop(op);
return Ok(Ran::Abandoned(raw));
}
let op = match slot.perform(op) {
Ok(Ok((buf, result))) => {
debug_assert!(
!is_read || buf.is_some() || result.is_err(),
"a read succeeded without its buffer (platform contract 1)"
);
return Ok(Ran::Done { buf, result });
}
Ok(Err(op)) => op,
Err(r) => return Err((r.buf, r.raw)),
};
slot.submit(op, TAG).map_err(|r| (r.buf, r.raw))?;
loop {
for c in slot.done.drain() {
if c.tag == TAG {
debug_assert!(
!is_read || c.buf.is_some() || c.result.is_err(),
"a read succeeded without its buffer (platform contract 1)"
);
return Ok(Ran::Done {
buf: c.buf,
result: c.result,
});
}
}
if let Err(raw) = slot.wait(1) {
return Ok(Ran::Abandoned(raw));
}
}
}
pub(crate) trait Source {
fn next(&mut self) -> Next;
fn recycle(&mut self, buf: IoBuf);
fn is_split(&self) -> bool {
false
}
}
pub(crate) enum Next {
Write(u64, IoBuf),
Wait,
Done,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Pumped {
All,
Refused(Option<OsError>),
Failed(Option<OsError>),
}
pub(crate) fn pump<Q: Queue>(
lane: &mut Lane<Q>,
file: &Q::File,
dsync: bool,
src: &mut impl Source,
obs: &Observer,
) -> Pumped {
const TAG: u64 = 0x5111;
let mut in_flight = 0usize;
let mut submitted = 0usize;
let mut failure: Option<Option<OsError>> = None;
let mut held: Option<(u64, IoBuf)> = None;
let mut producing = true;
loop {
while failure.is_none() && producing {
let (offset, buf) = match held.take() {
Some(w) => w,
None => match src.next() {
Next::Write(offset, buf) => (offset, buf),
Next::Wait => break,
Next::Done => {
producing = false;
break;
}
},
};
let bytes = buf.len() as u64;
let op = IoOp::Write {
file,
offset,
buf,
dsync,
};
let op = if in_flight == 0 {
match lane.perform(op) {
Ok(Ok((buf, result))) => {
submitted += 1;
obs.add(Counter::Writes, 1);
obs.add(Counter::WriteBytes, bytes);
match (result, buf) {
(Ok(n), Some(buf)) if n == buf.len() => src.recycle(buf),
(result, _) => failure = Some(result.err()),
}
continue;
}
Ok(Err(op)) => op,
Err(r) => {
if submitted == 0 {
return Pumped::Refused(r.raw);
}
failure = Some(r.raw);
break;
}
}
} else {
op
};
match lane.submit(op, TAG) {
Ok(()) => {
in_flight += 1;
submitted += 1;
obs.add(Counter::Writes, 1);
obs.add(Counter::WriteBytes, bytes);
}
Err(r) if r.raw.is_none() && in_flight > 0 => {
match r.buf {
Some(buf) => held = Some((offset, buf)),
None => failure = Some(None),
}
break;
}
Err(r) => {
if submitted == 0 {
return Pumped::Refused(r.raw);
}
failure = Some(r.raw);
}
}
}
if in_flight == 0 {
if producing && failure.is_none() {
if submitted == 0 {
return Pumped::Refused(None);
}
failure = Some(None);
}
break;
}
if let Err(raw) = lane.wait(1) {
return Pumped::Failed(Some(raw));
}
for c in lane.done.drain() {
in_flight = in_flight.saturating_sub(1);
match (c.result, c.buf) {
(Ok(n), Some(buf)) if n == buf.len() => src.recycle(buf),
(result, _) => {
if failure.is_none() {
failure = Some(result.err());
}
}
}
}
}
match failure {
None => Pumped::All,
Some(raw) => Pumped::Failed(raw),
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used)]
use std::path::Path;
use store_io_core::error::ErrorContext;
use store_io_platform::IoOp;
use store_io_sim::{SimConfig, SimPlatform};
use crate::{Store, StoreOptions};
#[test]
fn test_a_stale_completion_is_discarded_with_nothing_in_flight() {
let p = SimPlatform::new(SimConfig::volatile(41));
let s = Store::create(p, Path::new("/db"), StoreOptions::default()).unwrap();
let mut lane = s.inner.queues.get(0);
let stale = store_io_platform::Completion {
tag: 0x5110,
buf: None,
result: Ok(4096),
};
assert!(lane.done.push(stale).is_ok());
assert_eq!(lane.in_flight(), 0);
super::clear_stale(&mut lane).unwrap();
assert!(lane.done.is_empty(), "the stale completion was kept");
}
#[test]
fn test_a_refused_lane_submission_leaves_nothing_in_flight() {
let p = SimPlatform::new(SimConfig::volatile(40));
let s = Store::create(p.clone(), Path::new("/db"), StoreOptions::default()).unwrap();
let mut lane = s.inner.queues.get(0);
for _ in 0..3 {
p.with_world(|w| {
let next = w.write_submits() + 1;
w.faults_mut().fail_submit = Some((next, 5));
});
let buf = s.take(4096, ErrorContext::default()).unwrap();
let op = IoOp::Write {
file: &s.inner.file,
offset: 0,
buf,
dsync: false,
};
let refused = lane.submit(op, 7).unwrap_err();
assert!(refused.buf.is_some() && refused.raw.is_some());
assert_eq!(lane.in_flight(), 0, "the refused row was not given back");
}
}
}