use std::collections::{BTreeMap, BTreeSet};
use fsqlite_error::{FrankenError, Result};
use fsqlite_types::cx::Cx;
use fsqlite_types::ecs::{SYMBOL_RECORD_MAGIC, SYMBOL_RECORD_VERSION, SymbolRecordError};
use fsqlite_types::{
COMMIT_MARKER_RECORD_V1_SIZE, CommitMarker, CommitSeq, ObjectId, Oti, SymbolRecord,
};
use fsqlite_vfs::{SyncKind, VfsFile, VfsWriteCompletion, VfsWriteCompletionState};
const SYMBOL_HEADER_BYTES: usize = 51;
const SYMBOL_TRAILER_BYTES: usize = 25;
#[derive(Debug, Clone, Copy)]
pub struct NativeDurabilityLimits {
pub max_symbol_bytes: usize,
pub max_batch_bytes: usize,
pub max_stream_bytes: u64,
pub max_records: usize,
}
impl Default for NativeDurabilityLimits {
fn default() -> Self {
Self {
max_symbol_bytes: 65_536,
max_batch_bytes: 16 * 1024 * 1024,
max_stream_bytes: 512 * 1024 * 1024,
max_records: 1_000_000,
}
}
}
impl NativeDurabilityLimits {
fn validate(self) -> Result<()> {
if self.max_symbol_bytes == 0
|| self.max_batch_bytes < SYMBOL_HEADER_BYTES + SYMBOL_TRAILER_BYTES
|| self.max_stream_bytes == 0
|| self.max_records == 0
{
return Err(FrankenError::OutOfRange {
what: "native durability limits".to_owned(),
value: format!("{self:?}"),
});
}
Ok(())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct NativeDurabilityReceipt {
pub first_seq: CommitSeq,
pub last_seq: CommitSeq,
pub commits: usize,
pub symbol_stream_bytes: u64,
pub marker_stream_bytes: u64,
}
#[derive(Debug)]
pub struct NativeDurabilityRecovery {
pub markers: Vec<CommitMarker>,
pub symbol_records: usize,
pub erased_symbols: usize,
pub symbol_tail_bytes: u64,
pub marker_tail_bytes: u64,
}
impl NativeDurabilityRecovery {
#[must_use]
pub const fn append_blocked(&self) -> bool {
self.symbol_tail_bytes != 0 || self.marker_tail_bytes != 0
}
}
#[derive(Debug, Clone, Copy)]
struct SymbolLocation {
offset: u64,
len: usize,
}
#[derive(Debug)]
#[allow(clippy::struct_excessive_bools)]
pub struct NativeDurabilityLog<S: VfsFile, M: VfsFile> {
symbols: S,
markers: M,
limits: NativeDurabilityLimits,
index: BTreeMap<ObjectId, Vec<SymbolLocation>>,
record_count: usize,
symbol_end: u64,
marker_end: u64,
published_tip: CommitSeq,
previous_marker: Option<ObjectId>,
last_time_ns: u64,
poisoned: bool,
append_blocked: bool,
last_write: Option<VfsWriteCompletion>,
symbols_closed: bool,
markers_closed: bool,
}
impl<S: VfsFile, M: VfsFile> NativeDurabilityLog<S, M> {
pub fn create(cx: &Cx, symbols: S, markers: M, limits: NativeDurabilityLimits) -> Result<Self> {
limits.validate()?;
checkpoint(cx)?;
ensure_distinct_files(&symbols, &markers)?;
if symbols.file_size(cx)? != 0 || markers.file_size(cx)? != 0 {
return Err(corrupt("create requires empty native streams"));
}
Ok(Self::empty(symbols, markers, limits))
}
fn empty(symbols: S, markers: M, limits: NativeDurabilityLimits) -> Self {
Self {
symbols,
markers,
limits,
index: BTreeMap::new(),
record_count: 0,
symbol_end: 0,
marker_end: 0,
published_tip: CommitSeq::ZERO,
previous_marker: None,
last_time_ns: 0,
poisoned: false,
append_blocked: false,
last_write: None,
symbols_closed: false,
markers_closed: false,
}
}
#[must_use]
pub const fn published_tip(&self) -> CommitSeq {
self.published_tip
}
#[must_use]
pub const fn needs_recovery(&self) -> bool {
self.poisoned || self.append_blocked
}
#[must_use]
pub fn outstanding_write(&self) -> Option<VfsWriteCompletion> {
self.last_write.clone()
}
fn ready(&self) -> Result<()> {
self.readable()?;
if self.append_blocked {
return Err(FrankenError::BusyRecovery);
}
Ok(())
}
fn readable(&self) -> Result<()> {
if self.poisoned || self.symbols_closed || self.markers_closed {
return Err(FrankenError::BusyRecovery);
}
Ok(())
}
pub async fn recover<V, VF>(
cx: &Cx,
symbols: S,
markers: M,
limits: NativeDurabilityLimits,
mut verify_object: V,
) -> Result<(Self, NativeDurabilityRecovery)>
where
V: FnMut(ObjectId, Vec<SymbolRecord>) -> VF,
VF: std::future::Future<Output = Result<()>>,
{
limits.validate()?;
checkpoint(cx)?;
ensure_distinct_files(&symbols, &markers)?;
let symbol_end = symbols.file_size(cx)?;
let marker_end = markers.file_size(cx)?;
let marker_width = u64_len(COMMIT_MARKER_RECORD_V1_SIZE)?;
let marker_count =
usize::try_from(marker_end / marker_width).map_err(|_| FrankenError::TooBig)?;
if symbol_end > limits.max_stream_bytes
|| marker_end > limits.max_stream_bytes
|| marker_count > limits.max_records
{
return Err(FrankenError::TooBig);
}
let mut log = Self::empty(symbols, markers, limits);
log.symbol_end = symbol_end;
log.marker_end = marker_end;
let mut offset = 0_u64;
let mut erased_symbols = 0_usize;
while symbol_end - offset >= u64_len(SYMBOL_HEADER_BYTES)? {
checkpoint(cx)?;
if log.record_count == limits.max_records {
return Err(FrankenError::TooBig);
}
let mut header = [0_u8; SYMBOL_HEADER_BYTES];
read_exact_at(&log.symbols, cx, &mut header, offset).await?;
let len = symbol_wire_len(&header, limits)?;
let end = offset
.checked_add(u64_len(len)?)
.ok_or(FrankenError::TooBig)?;
if end > symbol_end {
break;
}
let mut bytes = zeroed(len)?;
read_exact_at(&log.symbols, cx, &mut bytes, offset).await?;
match SymbolRecord::from_bytes(&bytes) {
Ok(record) => {
log.index
.entry(record.object_id)
.or_default()
.push(SymbolLocation { offset, len });
}
Err(SymbolRecordError::IntegrityFailure { .. }) => erased_symbols += 1,
Err(error) => return Err(corrupt(&error.to_string())),
}
log.record_count += 1;
offset = end;
}
let mut recovered = Vec::new();
recovered
.try_reserve_exact(marker_count)
.map_err(|_| FrankenError::OutOfMemory)?;
let mut tip = CommitSeq::ZERO;
let mut previous = None;
let mut time = 0;
let mut verified = BTreeSet::new();
for ordinal in 0..marker_count {
checkpoint(cx)?;
let mut bytes = [0_u8; COMMIT_MARKER_RECORD_V1_SIZE];
let position = u64_len(ordinal)?
.checked_mul(marker_width)
.ok_or(FrankenError::TooBig)?;
read_exact_at(&log.markers, cx, &mut bytes, position).await?;
let marker = CommitMarker::from_record_bytes(&bytes)
.ok_or_else(|| corrupt("malformed native marker record"))?;
validate_marker(&marker, tip, previous, time)?;
for object_id in [marker.capsule_object_id, marker.proof_object_id] {
if verified.insert(object_id) {
let records = log.read_object(cx, object_id).await?;
verify_object(object_id, records).await?;
}
}
tip = marker.commit_seq;
previous = Some(ObjectId::derive_from_canonical_bytes(&bytes));
time = marker.commit_time_unix_ns;
recovered.push(marker);
}
let report = NativeDurabilityRecovery {
markers: recovered,
symbol_records: log.record_count,
erased_symbols,
symbol_tail_bytes: symbol_end - offset,
marker_tail_bytes: marker_end % marker_width,
};
log.check_lengths(cx)?;
checkpoint(cx)?;
log.poisoned = true;
log.symbols.durable_sync(cx, SyncKind::FullDurable)?;
log.markers.durable_sync(cx, SyncKind::FullDurable)?;
log.published_tip = tip;
log.previous_marker = previous;
log.last_time_ns = time;
log.append_blocked = report.append_blocked();
log.poisoned = false;
Ok((log, report))
}
fn check_lengths(&mut self, cx: &Cx) -> Result<()> {
if self.symbols.file_size(cx)? != self.symbol_end
|| self.markers.file_size(cx)? != self.marker_end
{
self.poisoned = true;
return Err(FrankenError::BusyRecovery);
}
ensure_distinct_files(&self.symbols, &self.markers)
}
pub async fn append_symbols(&mut self, cx: &Cx, records: &[SymbolRecord]) -> Result<()> {
self.ready()?;
checkpoint(cx)?;
self.check_lengths(cx)?;
if records.is_empty() {
return Ok(());
}
let count = self
.record_count
.checked_add(records.len())
.ok_or(FrankenError::TooBig)?;
if count > self.limits.max_records {
return Err(FrankenError::TooBig);
}
let mut bytes = Vec::new();
let mut locations = Vec::new();
locations
.try_reserve_exact(records.len())
.map_err(|_| FrankenError::OutOfMemory)?;
for record in records {
checkpoint(cx)?;
let symbol_len = usize::try_from(record.oti.t).map_err(|_| FrankenError::TooBig)?;
if symbol_len == 0 || symbol_len != record.symbol_data.len() {
return Err(corrupt("symbol payload does not match OTI.T"));
}
if symbol_len > self.limits.max_symbol_bytes {
return Err(FrankenError::TooBig);
}
if record.oti.f == 0 || record.oti.f > u64_len(self.limits.max_batch_bytes)? {
return Err(FrankenError::TooBig);
}
let len = symbol_len
.checked_add(SYMBOL_HEADER_BYTES + SYMBOL_TRAILER_BYTES)
.ok_or(FrankenError::TooBig)?;
let end = bytes.len().checked_add(len).ok_or(FrankenError::TooBig)?;
if end > self.limits.max_batch_bytes {
return Err(FrankenError::TooBig);
}
let wire = record.to_bytes();
SymbolRecord::from_bytes(&wire).map_err(|error| corrupt(&error.to_string()))?;
let offset = self
.symbol_end
.checked_add(u64_len(bytes.len())?)
.ok_or(FrankenError::TooBig)?;
bytes
.try_reserve(len)
.map_err(|_| FrankenError::OutOfMemory)?;
bytes.extend_from_slice(&wire);
locations.push((record.object_id, SymbolLocation { offset, len }));
}
let end = self
.symbol_end
.checked_add(u64_len(bytes.len())?)
.ok_or(FrankenError::TooBig)?;
if end > self.limits.max_stream_bytes {
return Err(FrankenError::TooBig);
}
self.poisoned = true;
let completion = VfsWriteCompletion::new();
self.last_write = Some(completion.clone());
self.symbols
.write_tracked(cx, &bytes, self.symbol_end, completion)
.await?;
for (object_id, location) in locations {
self.index.entry(object_id).or_default().push(location);
}
self.symbol_end = end;
self.record_count = count;
self.poisoned = false;
self.last_write = None;
Ok(())
}
pub async fn read_object(&self, cx: &Cx, object_id: ObjectId) -> Result<Vec<SymbolRecord>> {
self.readable()?;
let locations = self
.index
.get(&object_id)
.ok_or_else(|| corrupt("missing native object"))?;
let total = locations.iter().try_fold(0_usize, |sum, location| {
sum.checked_add(location.len).ok_or(FrankenError::TooBig)
})?;
if total > self.limits.max_batch_bytes {
return Err(FrankenError::TooBig);
}
let mut records = Vec::new();
records
.try_reserve_exact(locations.len())
.map_err(|_| FrankenError::OutOfMemory)?;
for location in locations {
checkpoint(cx)?;
let mut bytes = zeroed(location.len)?;
read_exact_at(&self.symbols, cx, &mut bytes, location.offset).await?;
if symbol_wire_len(&bytes, self.limits)? != location.len {
return Err(corrupt("native object locator length mismatch"));
}
let record = match SymbolRecord::from_bytes(&bytes) {
Ok(record) => record,
Err(SymbolRecordError::IntegrityFailure { .. }) => continue,
Err(error) => return Err(corrupt(&error.to_string())),
};
if record.object_id != object_id {
return Err(corrupt("native object locator identity mismatch"));
}
records.push(record);
}
if records.is_empty() {
return Err(corrupt("no intact symbols for native object"));
}
Ok(records)
}
pub async fn publish<V, VF>(
&mut self,
cx: &Cx,
markers: &[CommitMarker],
mut verify_object: V,
) -> Result<Option<NativeDurabilityReceipt>>
where
V: FnMut(ObjectId, Vec<SymbolRecord>) -> VF,
VF: std::future::Future<Output = Result<()>>,
{
self.ready()?;
checkpoint(cx)?;
self.check_lengths(cx)?;
if markers.is_empty() {
return Ok(None);
}
let len = markers
.len()
.checked_mul(COMMIT_MARKER_RECORD_V1_SIZE)
.ok_or(FrankenError::TooBig)?;
let end = self
.marker_end
.checked_add(u64_len(len)?)
.ok_or(FrankenError::TooBig)?;
if len > self.limits.max_batch_bytes
|| end > self.limits.max_stream_bytes
|| end / u64_len(COMMIT_MARKER_RECORD_V1_SIZE)? > u64_len(self.limits.max_records)?
{
return Err(FrankenError::TooBig);
}
let mut wire = Vec::new();
wire.try_reserve_exact(len)
.map_err(|_| FrankenError::OutOfMemory)?;
let mut tip = self.published_tip;
let mut previous = self.previous_marker;
let mut time = self.last_time_ns;
let mut verified = BTreeSet::new();
for marker in markers {
checkpoint(cx)?;
validate_marker(marker, tip, previous, time)?;
for object_id in [marker.capsule_object_id, marker.proof_object_id] {
if verified.insert(object_id) {
let records = self.read_object(cx, object_id).await?;
verify_object(object_id, records).await?;
}
}
let bytes = marker.to_record_bytes();
wire.extend_from_slice(&bytes);
tip = marker.commit_seq;
previous = Some(ObjectId::derive_from_canonical_bytes(&bytes));
time = marker.commit_time_unix_ns;
}
self.check_lengths(cx)?;
let receipt = NativeDurabilityReceipt {
first_seq: markers[0].commit_seq,
last_seq: tip,
commits: markers.len(),
symbol_stream_bytes: self.symbol_end,
marker_stream_bytes: end,
};
self.poisoned = true;
self.symbols.durable_sync(cx, SyncKind::FullDurable)?; let completion = VfsWriteCompletion::new();
self.last_write = Some(completion.clone());
self.markers
.write_tracked(cx, &wire, self.marker_end, completion)
.await?;
self.markers.durable_sync(cx, SyncKind::FullDurable)?; self.marker_end = end;
self.published_tip = tip;
self.previous_marker = previous;
self.last_time_ns = time;
self.last_write = None;
self.poisoned = false;
Ok(Some(receipt))
}
pub fn close(&mut self, cx: &Cx) -> Result<()> {
if self
.last_write
.as_ref()
.is_some_and(|write| write.state() == VfsWriteCompletionState::Pending)
{
return Err(FrankenError::BusyRecovery);
}
self.poisoned = true;
let symbols_result = if self.symbols_closed {
Ok(())
} else {
self.symbols.close(cx)
};
if symbols_result.is_ok() {
self.symbols_closed = true;
}
let markers_result = if self.markers_closed {
Ok(())
} else {
self.markers.close(cx)
};
if markers_result.is_ok() {
self.markers_closed = true;
}
symbols_result.and(markers_result)
}
}
fn symbol_wire_len(header: &[u8], limits: NativeDurabilityLimits) -> Result<usize> {
if header.len() < SYMBOL_HEADER_BYTES
|| header[..4] != SYMBOL_RECORD_MAGIC
|| header[4] != SYMBOL_RECORD_VERSION
{
return Err(corrupt("malformed native symbol header"));
}
let oti =
Oti::from_bytes(&header[21..43]).ok_or_else(|| corrupt("malformed native symbol OTI"))?;
let size = u32::from_le_bytes(
header[47..51]
.try_into()
.map_err(|_| corrupt("short symbol size"))?,
);
if size == 0 || size != oti.t {
return Err(corrupt("native symbol size does not match OTI.T"));
}
let size = usize::try_from(size).map_err(|_| FrankenError::TooBig)?;
let len = size
.checked_add(SYMBOL_HEADER_BYTES + SYMBOL_TRAILER_BYTES)
.ok_or(FrankenError::TooBig)?;
if size > limits.max_symbol_bytes
|| len > limits.max_batch_bytes
|| oti.f == 0
|| oti.f > u64_len(limits.max_batch_bytes)?
{
return Err(FrankenError::TooBig);
}
Ok(len)
}
fn validate_marker(
marker: &CommitMarker,
tip: CommitSeq,
previous: Option<ObjectId>,
time: u64,
) -> Result<()> {
if !marker.verify_integrity() {
return Err(corrupt("native marker integrity mismatch"));
}
if tip.get().checked_add(1) != Some(marker.commit_seq.get()) {
return Err(corrupt("non-contiguous native marker sequence"));
}
if marker.prev_marker != previous || marker.commit_time_unix_ns < time {
return Err(corrupt("native marker chain or clock mismatch"));
}
Ok(())
}
fn ensure_distinct_files<S: VfsFile, M: VfsFile>(symbols: &S, markers: &M) -> Result<()> {
let symbols_id = symbols
.refresh_file_identity()?
.ok_or(FrankenError::Unsupported)?;
let markers_id = markers
.refresh_file_identity()?
.ok_or(FrankenError::Unsupported)?;
if symbols_id == markers_id {
return Err(corrupt(
"native symbol and marker streams alias the same file",
));
}
Ok(())
}
fn checkpoint(cx: &Cx) -> Result<()> {
cx.checkpoint().map_err(|_| FrankenError::Interrupt)
}
fn corrupt(detail: &str) -> FrankenError {
FrankenError::WalCorrupt {
detail: detail.to_owned(),
}
}
fn u64_len(len: usize) -> Result<u64> {
u64::try_from(len).map_err(|_| FrankenError::TooBig)
}
fn zeroed(len: usize) -> Result<Vec<u8>> {
let mut bytes = Vec::new();
bytes
.try_reserve_exact(len)
.map_err(|_| FrankenError::OutOfMemory)?;
bytes.resize(len, 0);
Ok(bytes)
}
async fn read_exact_at<F: VfsFile>(file: &F, cx: &Cx, bytes: &mut [u8], offset: u64) -> Result<()> {
let mut read = 0;
while read < bytes.len() {
checkpoint(cx)?;
let position = offset
.checked_add(u64_len(read)?)
.ok_or(FrankenError::TooBig)?;
let count = file.read(cx, &mut bytes[read..], position).await?;
if count == 0 || count > bytes.len() - read {
return Err(corrupt("short native stream read"));
}
read += count;
}
Ok(())
}