//! Authenticated journal implementation. //! //! An authenticated journal maintains a contiguous journal of items alongside a Merkle-family //! structure. The item at index i in the journal corresponds to the leaf at Location i in the //! Merkle structure. This structure enables efficient proofs that an item is included in the //! journal at a specific location. //! //! # Persistence //! //! Only the operations and the frontier are durable. The frontier is one metadata record holding //! the pruning boundary and the digests pinned there. Startup replays the retained operations to //! rebuild the Merkle digests kept in memory. //! //! ```text //! pins resident nodes, at or above the resident height //! memory: P P R R R R R R //! / \ / \ / \ / \ / \ / \ //! lower nodes, rebuilt from their region when needed //! disk: pruned | o o o o o o o o o o o o o o o o o o o o o o o o | //! ^ boundary ^ end //! frontier: the boundary and the pins P //! ``` //! //! Items before the Merkle structure's start are not readable, even when a backing blob still //! holds them. //! //! Nodes at or above [`Config::resident_height`] stay in memory. A lower node is rebuilt when //! needed from the operations in its aligned region of leaves. //! //! A prune commits the operations, writes the frontier at the new boundary, then deletes //! operation blobs. A state sync writes its boundary only after its root is verified, then deletes //! the operation blobs before it. Startup finishes a deletion that a crash interrupted. //! //! # Ownership //! //! Mutating methods take the journal by value and return it on success. If a mutating //! method returns an error, or its future is dropped before it finishes, the journal is //! gone: state that was not yet durable is discarded, but everything already on disk stays //! recoverable. use crate::{ Context, journal::{ Error as JournalError, contiguous::{Batch, Contiguous, Many, Mutable}, }, merkle::{ self, Bagging, Family, Location, Position, Proof, Readable, batch, hasher::Standard as StandardHasher, mem::Mem, }, }; use alloc::{ sync::{Arc, Weak}, vec::Vec, }; use commonware_codec::{Encode, EncodeShared}; use commonware_cryptography::{Digest, Hasher}; use commonware_macros::boxed; use commonware_parallel::Strategy; use commonware_runtime::{Handle, ReadOptions, Spawner}; use commonware_utils::{NZU64, channel::mpsc}; use core::{ num::{NonZeroU64, NonZeroUsize}, ops::Range, }; use futures::Stream; use thiserror::Error; use tracing::{debug, warn}; mod config; mod frontier; mod metrics; mod tree; #[cfg(test)] pub(crate) use config::tests::low_resident_height; pub use config::{Config, ResidentHeight}; pub(crate) use frontier::Frontier; pub(crate) use tree::{Chunk, ChunkHasher}; use tree::{ChunkPlan, Tree}; /// Errors that can occur when interacting with an authenticated journal. #[derive(Error, Debug)] pub enum Error { #[error("merkle error: {0}")] Merkle(#[from] merkle::Error), #[error("journal error: {0}")] Journal(#[from] super::Error), } /// Strong ref to an ancestor [`MerkleizedBatch`] in the journal-batch chain. type MerkleizedParent = Arc::Digest, Item, S>>; /// A speculative batch whose root digest has not yet been computed, /// in contrast to [`MerkleizedBatch`]. pub struct UnmerkleizedBatch { // The inner batch of Merkle leaf digests. inner: batch::UnmerkleizedBatch, // The hasher to use for hashing the items. hasher: StandardHasher, // The items to append from this batch. items: Vec, // This batch's parent, or None if the parent is the journal itself. parent: Option>, } type MerkleizedBatchArc = Arc::Digest, Item, S>>; impl UnmerkleizedBatch { /// Add an item to the batch. #[allow(clippy::should_implement_trait)] pub fn add(mut self, item: Item) -> Self { let encoded = item.encode(); self.inner = self.inner.add(&self.hasher, &encoded); self.items.push(item); self } /// Collect the items of `parent` and the ancestors still reachable through its parent chain, /// in root-to-tip order. Skips ancestors without items. fn collect_ancestor_items(parent: &MerkleizedParent) -> Vec>> { let mut items = Vec::new(); if !parent.items.is_empty() { items.push(Arc::clone(&parent.items)); } let mut current = parent.parent.as_ref().and_then(Weak::upgrade); while let Some(batch) = current { if !batch.items.is_empty() { items.push(Arc::clone(&batch.items)); } current = batch.parent.as_ref().and_then(Weak::upgrade); } items.reverse(); items } /// Merkleize the batch. /// `base` provides committed node data as fallback during hash computation. pub fn merkleize(self, base: &Mem) -> MerkleizedBatchArc { let Self { inner, hasher, items, parent, } = self; let ancestor_items = parent .as_ref() .map_or_else(Vec::new, Self::collect_ancestor_items); let items = Arc::new(items); let merkle = inner.merkleize(base, &hasher); Arc::new(MerkleizedBatch { inner: merkle, bagging: hasher.root_bagging(), items, parent: parent.as_ref().map(Arc::downgrade), ancestor_items, }) } /// Add caller-supplied items to the batch. /// /// # Panics /// /// Panics if items were previously added via [`add`](Self::add). pub(crate) fn add_many(mut self, items: Vec) -> Self { assert!( self.items.is_empty(), "add_many expects no items added via add" ); self.inner = self.inner.add_many(&self.hasher, &items); self.items = items; self } } /// A speculative batch whose root digest has been computed, in contrast to [`UnmerkleizedBatch`]. #[derive(Clone, Debug)] pub struct MerkleizedBatch { /// The inner batch of Merkle leaf digests. pub(crate) inner: Arc>, /// The peak bagging policy inherited from the parent journal or batch. bagging: Bagging, /// The items to append from this batch. items: Arc>, /// This batch's parent, or None if the parent is the journal itself. parent: Option>, /// Ancestor item batches collected at merkleize time (root-to-tip order). pub(crate) ancestor_items: Vec>>, } impl MerkleizedBatch { /// The number of items visible through this batch, including ancestors. pub(crate) fn size(&self) -> u64 { *self.inner.leaves() } /// Compute the root digest after this batch is applied using `inactive_peaks` and the bagging /// carried by `hasher`. pub fn root( &self, hasher: &impl merkle::hasher::Hasher, inactive_peaks: usize, ) -> Result> { self.inner.root(hasher, inactive_peaks) } /// Inclusion proof for the element at `loc`. pub fn proof( &self, base: &Mem, hasher: &impl merkle::hasher::Hasher, loc: Location, inactive_peaks: usize, ) -> Result, merkle::Error> { self.inner.proof(base, hasher, loc, inactive_peaks) } /// Inclusion proof for all elements in `range`. pub fn range_proof( &self, base: &Mem, hasher: &impl merkle::hasher::Hasher, range: core::ops::Range>, inactive_peaks: usize, ) -> Result, merkle::Error> { self.inner.range_proof(base, hasher, range, inactive_peaks) } /// The items added in this batch. pub(crate) const fn items(&self) -> &Arc> { &self.items } /// Create a new speculative batch of operations with this batch as its parent. /// /// The child must be merkleized before unapplied ancestor batches are dropped. Applying a /// sibling fork to the base invalidates it. pub fn new_batch>(self: &Arc) -> UnmerkleizedBatch where Item: Encode, { UnmerkleizedBatch { inner: self.inner.new_batch(), hasher: StandardHasher::new(self.bagging), items: Vec::new(), parent: Some(Arc::clone(self)), } } } impl Readable for MerkleizedBatch { type Family = F; type Digest = D; fn size(&self) -> Position { self.inner.size() } fn get_node(&self, pos: Position) -> Option { self.inner.get_node(pos) } } /// An append-only data structure that maintains a sequential journal of items alongside a /// Merkle-family structure. The item at index i in the journal corresponds to the leaf at Location /// i in the Merkle structure. This structure enables efficient proofs that an item is included in /// the journal at a specific location. pub struct Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { /// Merkle structure where each leaf is an item digest. /// Invariant: leaf i corresponds to item i in the journal. pub(crate) merkle: Tree, /// Durable pruning boundary and the digests pinned there. pub(crate) frontier: Frontier, /// Whether the frontier records the Merkle structure's start. It does not from /// [Self::from_components] until [Self::persist_boundary], and nothing is pruned meanwhile. pub(crate) boundary_recorded: bool, /// Journal of items. /// Invariant: item i corresponds to leaf i in the Merkle structure. pub(crate) journal: C, /// Hasher and peak-bagging mode for the Merkle structure's digests and roots. pub(crate) hasher: StandardHasher, } impl core::fmt::Debug for Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { f.debug_struct("Journal") .field("size", &self.size()) .finish_non_exhaustive() } } impl Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { /// Returns the Location of the next item appended to the journal. pub fn size(&self) -> Location { Location::new(self.journal.bounds().end) } /// Compute the root of the Merkle structure using `inactive_peaks` and the bagging carried by /// the journal's hasher. pub fn root(&self, inactive_peaks: usize) -> Result> { self.merkle .root(&self.hasher, inactive_peaks) .map_err(Into::into) } /// Return a reference to the merkleization strategy. pub const fn strategy(&self) -> &S { self.merkle.strategy() } /// Create a speculative batch atop this journal. pub fn new_batch(&self) -> UnmerkleizedBatch { let root = self.merkle.to_batch(); UnmerkleizedBatch { inner: root.new_batch(), hasher: StandardHasher::new(self.hasher.root_bagging()), items: Vec::new(), parent: None, } } /// Add `items` to `batch`, merkleize, and compute the post-apply root, all as one CPU-bound job /// submitted through [`Strategy::spawn`]. /// /// The job hashes against an immutable snapshot of the committed Merkle state, so a parallel /// strategy can host the batch's dominant CPU phase on its own pool instead of occupying the /// calling task. If the job's caller is cancelled, the job still runs to completion /// against its snapshot and the result is discarded. pub(crate) async fn merkleize( &self, batch: UnmerkleizedBatch, items: Vec, inactive_peaks: usize, ) -> Result<(MerkleizedBatchArc, H::Digest), merkle::Error> where C::Item: 'static, { let ancestors = batch.inner.retain_ancestors(); let mem = self.merkle.snapshot(); let hasher = self.hasher.clone(); let strategy = self.strategy().clone(); strategy .spawn(items.len(), move |_| { let merkleized = batch.add_many(items).merkleize(&mem); let root = merkleized.root(&hasher, inactive_peaks)?; drop(ancestors); Ok((merkleized, root)) }) .await } /// Create an owned [`MerkleizedBatch`] representing the current committed state. /// /// The batch has no items (the committed items are on disk, not in memory). /// This is the starting point for building owned batch chains. pub(crate) fn to_merkleized_batch(&self) -> Arc> { Arc::new(MerkleizedBatch { inner: self.merkle.to_batch(), bagging: self.hasher.root_bagging(), items: Arc::new(Vec::new()), parent: None, ancestor_items: Vec::new(), }) } /// Generate a proof of inclusion for items starting at `start_loc`. /// /// Returns a proof and the items corresponding to the leaves in the range `start_loc..end_loc`, /// where `end_loc` is the minimum of the current item count and `start_loc + max_ops`. /// /// # Errors /// /// - Returns [Error::Merkle] with [merkle::Error::RangeOutOfBounds] if `start_loc` >= current /// item count. /// - Returns [Error::Journal] with [crate::journal::Error::ItemPruned] or [Error::Merkle] with /// [merkle::Error::ElementPruned] if a required item or Merkle node has been pruned. pub async fn proof( &self, start_loc: Location, max_ops: NonZeroU64, inactive_peaks: usize, ) -> Result<(Proof, Vec), Error> { self.historical_proof(self.size(), start_loc, max_ops, inactive_peaks) .await } /// Inclusion proof for the items `batch` appends, anchored at the batch's speculative tip. /// /// Nodes below the batch chain are read from this journal's /// [Merkle store][crate::merkle::mem::Mem], which retains them at least until /// the batch's changes are flushed. pub fn speculative_proof( &self, batch: &MerkleizedBatch, inactive_peaks: usize, ) -> Result, Error> { let end = batch.size(); let start = Location::new(end - batch.items().len() as u64); batch .range_proof( self.merkle.mem(), &self.hasher, start..Location::new(end), inactive_peaks, ) .map_err(Error::Merkle) } /// Merkle frontier at the first item `batch` appends ([`Family::nodes_to_pin`]). /// /// Nodes below the batch chain are read from this journal's /// [Merkle store][crate::merkle::mem::Mem], which retains them at least until /// the batch's changes are flushed. pub fn speculative_pinned_nodes( &self, batch: &MerkleizedBatch, ) -> Result, Error> { let start = Location::new(batch.size() - batch.items().len() as u64); let mem = self.merkle.mem(); F::nodes_to_pin(start) .map(|pos| { batch .get_node(pos) .or_else(|| mem.get_node(pos)) .ok_or(merkle::Error::ElementPruned(pos)) }) .collect::, _>>() .map_err(Error::Merkle) } /// Generate a historical proof with respect to the state of the Merkle structure when it had /// `historical_leaves` leaves. /// /// Returns a proof and the items corresponding to the leaves in the range `start_loc..end_loc`, /// where `end_loc` is the minimum of `historical_leaves` and `start_loc + max_ops`. /// /// # Errors /// /// - Returns [Error::Merkle] with [merkle::Error::RangeOutOfBounds] if `start_loc` >= /// `historical_leaves` or `historical_leaves` > number of items in the journal. /// - Returns [Error::Journal] with [crate::journal::Error::ItemPruned] or [Error::Merkle] with /// [merkle::Error::ElementPruned] if a required item or Merkle node has been pruned. pub async fn historical_proof( &self, historical_leaves: Location, start_loc: Location, max_ops: NonZeroU64, inactive_peaks: usize, ) -> Result<(Proof, Vec), Error> { let bounds = self.bounds(); if *start_loc < bounds.start { return Err(JournalError::ItemPruned(*start_loc).into()); } if *historical_leaves > bounds.end { return Err(merkle::Error::RangeOutOfBounds(Location::new(bounds.end)).into()); } if start_loc >= historical_leaves { return Err(merkle::Error::RangeOutOfBounds(start_loc).into()); } let end_loc = std::cmp::min(historical_leaves, start_loc.saturating_add(max_ops.get())); let hasher = self.hasher.clone(); let proof = merkle::verification::historical_range_proof( &hasher, self, historical_leaves, start_loc..end_loc, inactive_peaks, ) .await?; let positions: Vec = (*start_loc..*end_loc).collect(); let ops = self.journal.read_many(&positions).await?; Ok((proof, ops)) } /// Return the digests [`Family::nodes_to_pin`] lists for `location`, in that order. /// /// Returns [`merkle::Error::ElementPruned`] if a node was pruned, /// [`merkle::Error::LocationOverflow`] if `location` exceeds the family limit, or /// [`merkle::Error::RangeOutOfBounds`] if a valid `location` is past the journal's end. pub async fn pinned_nodes_at( &self, location: Location, ) -> Result, merkle::Error> { if !location.is_valid() { return Err(merkle::Error::LocationOverflow(location)); } if location > self.size() { return Err(merkle::Error::RangeOutOfBounds(location)); } self.merkle .pinned_nodes_at(&self.journal, &self.hasher, location) .await } /// Like [`Contiguous::read_many`], but returns the items partitioned into the shards the /// probe ran with. Concatenating the shards yields the items in `positions` order. /// /// Large batches shard the page-cache probe across the strategy pool. Each shard /// assembles its own hits while they are still cache-hot on the probing worker, so bulk /// callers that can consume partitioned results (e.g. the floor raise, which classifies /// candidates in chunks) skip the serial reassembly a flat result would require. pub(crate) async fn read_many_sharded( &self, positions: &[u64], ) -> Result>, JournalError> { if positions.is_empty() { return Ok(Vec::new()); } // Probe page-cache hits synchronously and complete the misses with one batched read. // The strategy policy decides per batch size whether the probe runs on the calling // thread or sharded across the pool (one scratch buffer per shard and one cache-lock // acquisition per blob a shard touches). The sortedness assert keeps contract // violations deterministic: past it, a non-increasing batch would only trip per-shard // validation when an inversion lands inside a single shard. assert!( positions.is_sorted_by(|a, b| a < b), "positions must be strictly increasing" ); if positions[0] < self.bounds().start { return Err(JournalError::ItemPruned(positions[0])); } let strategy = self.strategy(); let journal = &self.journal; // Each shard yields its hits densely plus the shard-local indices it declined. let probe = |positions: &[u64]| -> (Vec, Vec) { let probed = journal.try_read_many_sync(positions); let mut hits = Vec::with_capacity(probed.len()); let mut missed = Vec::new(); for (idx, item) in probed.into_iter().enumerate() { match item { Some(item) => hits.push(item), None => missed.push(idx), } } (hits, missed) }; let shards: Vec<(Vec, Vec)> = strategy.run_batches(positions.len(), NonZeroUsize::MIN, 1, |batches| { batches.map_collect_vec(|ranges| ranges, |range| probe(&positions[range])) }); // The declined positions are a strictly increasing subsequence of `positions`, so one // batched read serves them all. Each shard covers the slice of `positions` starting // at the previous shards' total item count, whatever geometry the probe ran with. let mut misses: Vec = Vec::new(); let mut offset = 0; for (hits, missed) in &shards { misses.extend(missed.iter().map(|idx| positions[offset + idx])); offset += hits.len() + missed.len(); } if misses.is_empty() { return Ok(shards.into_iter().map(|(hits, _)| hits).collect()); } let mut fetched = journal.read_many(&misses).await?.into_iter(); // Weave the fetched items back into each shard that declined positions. let mut result = Vec::with_capacity(shards.len()); for (hits, missed) in shards { if missed.is_empty() { result.push(hits); continue; } let total = hits.len() + missed.len(); let mut woven = Vec::with_capacity(total); let mut hits = hits.into_iter(); let mut missed = missed.into_iter().peekable(); for idx in 0..total { if missed.next_if_eq(&idx).is_some() { woven.push(fetched.next().expect("one fetched item per miss")); } else { woven.push(hits.next().expect("one probed item per hit")); } } result.push(woven); } Ok(result) } } impl Journal where F: Family, E: Context, C: Mutable, H: Hasher, S: Strategy, { /// Begin durably persisting the journal. /// /// Awaiting the returned [Handle] provides the same durability guarantee as [Self::commit]. /// Also tries to advance the recovery watermark to bound startup recovery. Use /// [Self::sync] to guarantee the backing journal needs none. pub async fn start_sync(mut self) -> Result<(Self, Handle<()>), Error> { let handle; (self.journal, handle) = self.journal.start_sync().await?; self.merkle.flush(); Ok((self, handle)) } /// Durably persist the journal. Unlike [Self::sync], it may leave recovery work for startup /// after a crash. pub async fn commit(mut self) -> Result> { self.journal = self.journal.commit().await?; self.merkle.flush(); Ok(self) } /// Build a journal from synced operations starting at `start`, whose pinned digests are `pins`, /// using the frontier opened under `context`. Nothing is written until /// [Self::persist_boundary], so the frontier and the operations before `start` stay as they /// were until the caller has verified the root. The operations must be durable. /// /// Returns [Error::Merkle] with [`merkle::Error::RangeOutOfBounds`] if `start` lies outside /// the retained operation range. Its end is a valid start for a fully pruned journal. #[boxed] pub async fn from_components( context: E, config: &Config, journal: C, hasher: StandardHasher, start: Location, pins: Vec, apply_batch_size: NonZeroU64, ) -> Result> { let merkle = Tree::new(start, pins, config, &context)?; let bounds = journal.bounds(); if *start < bounds.start || *start > bounds.end { return Err(merkle::Error::RangeOutOfBounds(start).into()); } let frontier = Frontier::open(context.child("frontier"), config.partition.clone()).await?; let merkle = Self::align(merkle, &journal, &hasher, apply_batch_size).await?; Ok(Self { merkle, frontier, boundary_recorded: false, journal, hasher, }) } /// Record the boundary of a journal built by [Self::from_components] before pruning older operations. pub async fn persist_boundary(mut self) -> Result> { let boundary = self.merkle.bounds().start; let pins = self.pinned_nodes_at(boundary).await?; self.frontier = self.frontier.set(boundary, pins).await?; self.boundary_recorded = true; (self.journal, _) = self.journal.prune(*boundary).await?; Ok(self) } /// Align the Merkle structure with the journal. /// /// The Merkle structure must not extend past the journal end. Missing leaves are read and /// added in batches of `apply_batch_size` to bound peak memory use. Each batch's items are /// buffered in memory so their leaves can be hashed across the strategy. async fn align( merkle: Tree, journal: &C, hasher: &StandardHasher, apply_batch_size: NonZeroU64, ) -> Result, Error> { let end = Location::new(journal.bounds().end); merkle.replay(journal, hasher, end, apply_batch_size).await } /// Append an item to the journal and update the Merkle structure. pub async fn append(mut self, item: &C::Item) -> Result<(Self, Location), Error> { let encoded_item = item.encode(); // Append item to the journal, then update the Merkle structure state. let loc; (self.journal, loc) = self.journal.append(item).await?; let unmerkleized_batch = self.merkle.new_batch().add(&self.hasher, &encoded_item); let batch = unmerkleized_batch.merkleize(self.merkle.mem(), &self.hasher); self.merkle = self.merkle.apply_batch(&batch)?; Ok((self, Location::new(loc))) } /// Apply a batch to the journal. /// /// A batch is valid if the journal has not been modified since the batch /// chain was created, or if only ancestors of this batch have been applied. /// Already-committed ancestors are skipped automatically. /// Applying a batch from a different fork returns an error. pub async fn apply_batch( mut self, batch: &MerkleizedBatch, ) -> Result> { // Validate before appending any item, so a rejected batch writes nothing. let start = self.merkle.mem().validate_batch(&batch.inner)?; // Items are collected over the journal batch chain and Merkle records over the inner // chain. A journal batch can be dropped while its Merkle batch stays alive, so the item // list can be shorter, but both lists end at this batch's parent, so the ancestors still // to replay are the newest `remaining` entries of each. Reject the batch before appending // anything if their items are gone. let remaining = batch.inner.ancestor_count() - start; let first = batch.ancestor_items.len().checked_sub(remaining).ok_or( merkle::Error::AncestorDropped { expected: batch.inner.size(), actual: self.merkle.size(), }, )?; // Append the remaining ancestor items in root-to-tip order, then this batch's items, in // one append_many call so the journal's write lock is taken once. let mut batches: Vec<&[C::Item]> = Vec::with_capacity(remaining + 1); batches.extend( batch.ancestor_items[first..] .iter() .map(|items| items.as_slice()), ); if !batch.items.is_empty() { batches.push(&batch.items); } if !batches.is_empty() { (self.journal, _) = self.journal.append_many(Many::Nested(&batches)).await?; } self.merkle = self.merkle.apply_batch(&batch.inner)?; assert_eq!(*self.merkle.leaves(), self.journal.bounds().end); Ok(self) } /// Prune items before `prune_loc`, rounded down to the backing journal's pruning granularity. /// /// # Returns /// The earliest readable item. It may be less than `prune_loc` due to blob alignment, but /// never precedes the journal's existing frontier, including one installed by state sync. /// A journal built by [Self::from_components] prunes nothing until [Self::persist_boundary] /// records its boundary. #[boxed] pub async fn prune(mut self, prune_loc: Location) -> Result<(Self, Location), Error> { // The boundary of synced operations is written only once their root is verified. if !self.boundary_recorded { let start = Location::new(self.bounds().start); return Ok((self, start)); } let old = self.merkle.bounds().start; let boundary = Location::new(self.prune_target(*prune_loc)); if boundary > old { // The frontier must never get ahead of durable operations, and the new boundary may be // justified by a buffered append (e.g. a commit operation), so commit first. let pins = self.pinned_nodes_at(boundary).await?; self.journal = self.journal.commit().await?; self.frontier = self.frontier.set(boundary, pins.clone()).await?; self.merkle.prune(boundary, pins); debug!(size = ?self.journal.bounds().end, ?prune_loc, ?boundary, "pruned inactive ops"); } (self.journal, _) = self.journal.prune(*boundary).await?; let start = Location::new(self.bounds().start); Ok((self, start)) } /// The retained start that pruning to `min_position` would leave. fn prune_target(&self, min_position: u64) -> u64 { // A journal whose synced boundary is not recorded yet prunes nothing. if !self.boundary_recorded { return self.bounds().start; } self.journal .prune_target(min_position) .max(*self.merkle.bounds().start) } /// Destroy the authenticated journal, removing all data from disk. #[boxed] pub async fn destroy(self) -> Result<(), Error> { // Destructure before the first await boundary to avoid stack growth from retaining the // entire `self` in the future. let Self { journal, frontier, .. } = self; // The journal is the source of truth, so it goes first. Reopening an empty journal // discards whatever frontier remains beside it. journal.destroy().await?; frontier.destroy().await?; Ok(()) } /// Durably persist the journal, ensuring the backing journal needs no recovery on startup. /// Startup still replays the retained operations to rebuild the Merkle digests. pub async fn sync(mut self) -> Result> { self.journal = self.journal.sync().await?; self.merkle.flush(); Ok(self) } } /// A journal whose operations [Journal::prepare] has selected but not yet published. pub(crate) struct Recovery where F: Family, E: Context, C: Backing, H: Hasher, S: Strategy, { /// Context of the tasks that replay the selected operations or append their digests. context: E, /// Operation journal awaiting finalization at `selected_end`. journal: C::Recovery, /// Durable frontier. frontier: Frontier, /// Digests at the pruning boundary, before the selected operations are replayed. merkle: Tree, /// Hasher and peak-bagging mode retained for Merkle alignment and the published journal. hasher: StandardHasher, /// Exclusive operation end chosen for publication. selected_end: u64, } impl Recovery where F: Family, E: Context, C: Backing, H: Hasher, S: Strategy, { /// Range selected for publication. pub(crate) fn bounds(&self) -> Range { *self.merkle.bounds().start..self.selected_end } /// Whether storage was empty before commit selection. pub(crate) fn is_fresh(&self) -> bool { self.journal.bounds() == (0..0) } /// Read an operation to validate its recovery requirements. pub(crate) async fn read(&self, pos: u64) -> Result { if pos < self.bounds().start { return Err(JournalError::ItemPruned(pos)); } self.journal.read(pos).await } /// Persist the selected operations and rebuild their Merkle digests. pub(crate) async fn finish(self) -> Result, Error> { let journal = Self::persist(self.journal, self.selected_end).await?; let merkle = Journal::::align(self.merkle, &journal, &self.hasher, APPLY_BATCH_SIZE) .await?; Self::assemble(journal, merkle, self.frontier, self.hasher).await } /// Like [Self::finish], but runs `read` over the selected operations on this task, so they are /// read twice. The journal replays them on `tasks` tasks of its own while `read` runs, or after /// it on this task when `tasks` is 1. `read` must drop every clone of the journal before it /// completes. pub(crate) async fn finish_with( self, tasks: NonZeroUsize, read: impl FnOnce(Arc) -> Fut, ) -> Result<(Journal, T), X> where E: Spawner, C: 'static, Fut: Future>, X: From>, { let journal = Arc::new(Self::persist(self.journal, self.selected_end).await?); if tasks.get() == 1 { let value = read(journal.clone()).await?; let journal = Arc::into_inner(journal).expect("read must drop every journal clone"); let merkle = Journal::::align( self.merkle, &journal, &self.hasher, APPLY_BATCH_SIZE, ) .await?; return Ok(( Self::assemble(journal, merkle, self.frontier, self.hasher).await?, value, )); } // Dedicated, so the replay progresses while `read` keeps this task busy, even on a runtime // with one pool worker. The replay's subtree tasks each hold a clone of `released` until // they drop the journal, so `released_rx` closing means none of them holds it. let (released, mut released_rx) = mpsc::channel::<()>(1); let replay = { let (journal, merkle, hasher) = (journal.clone(), self.merkle, self.hasher.clone()); self.context .dedicated() .spawn(move |context| async move { let end = Location::new(journal.bounds().end); let merkle = merkle .replay_subtrees( context, &journal, &hasher, end, SUBTREE_HEIGHT, tasks, released, ) .await; drop(journal); merkle }) .abort_on_drop() }; let value = match read(journal.clone()).await { Ok(value) => value, Err(error) => { // Release every replay clone of the journal, its subtree tasks' included, before // returning. replay.abort().await; while released_rx.recv().await.is_some() {} return Err(error); } }; let merkle = replay.join().await.map_err(JournalError::from); let merkle = match merkle.map_err(Error::from).and_then(|merkle| merkle) { Ok(merkle) => merkle, Err(error) => { while released_rx.recv().await.is_some() {} return Err(error.into()); } }; let journal = Arc::into_inner(journal).expect("read must drop every journal clone"); Ok(( Self::assemble(journal, merkle, self.frontier, self.hasher).await?, value, )) } /// Like [Self::finish], but the journal does not replay the operations. Instead `read` must /// hash every chunk of the [LeafSink] it receives while it scans them, and send them in order. /// A task of its own appends them to the Merkle structure, so they are read once. pub(crate) async fn finish_hashing( self, read: impl FnOnce(Arc, LeafSink>) -> Fut, ) -> Result<(Journal, T), X> where E: Spawner, C: 'static, Fut: Future>, X: From>, { let journal = Arc::new(Self::persist(self.journal, self.selected_end).await?); let end = Location::new(journal.bounds().end); self.merkle .check_replay_end(journal.as_ref(), end) .map_err(Error::from)?; let (tx, mut rx) = mpsc::channel(BUFFERED_CHUNKS); let sink = LeafSink { plan: self.merkle.chunk_plan(end, SUBTREE_HEIGHT), hasher: self.hasher.clone(), tx, }; // Append each chunk in order as the reader sends it. let append = { let (merkle, hasher) = (self.merkle, self.hasher.clone()); self.context .dedicated() .spawn(move |_| async move { let mut merkle = merkle; while let Some(chunk) = rx.recv().await { merkle = merkle.apply_chunk(&hasher, chunk).await?; } if merkle.leaves() != end { return Err(merkle::Error::DataCorrupted( "chunks ended before the journal", ) .into()); } Ok::<_, Error>(merkle) }) .abort_on_drop() }; let value = match read(journal.clone(), sink).await { Ok(value) => value, Err(error) => { append.abort().await; return Err(error); } }; let merkle = append.join().await.map_err(JournalError::from); let merkle = merkle.map_err(Error::from)??; let journal = Arc::into_inner(journal).expect("read must drop every journal clone"); Ok(( Self::assemble(journal, merkle, self.frontier, self.hasher).await?, value, )) } /// Persist the selected operations. async fn persist(journal: C::Recovery, selected_end: u64) -> Result> { let bounds = journal.bounds(); if selected_end < bounds.end { warn!( journal_size = bounds.end, rewound_items = bounds.end - selected_end, "rewinding journal items" ); } let journal = journal.finish(selected_end).await?; Ok(journal.sync().await?) } /// Delete operations below the boundary, left by a crash during pruning or by a sync, and /// publish the journal. async fn assemble( journal: C, merkle: Tree, frontier: Frontier, hasher: StandardHasher, ) -> Result, Error> { let (journal, _) = journal.prune(*merkle.bounds().start).await?; // Record genesis over a frontier that [Journal::prepare] discarded. let frontier = if *merkle.bounds().start == 0 { frontier.reset().await? } else { frontier }; Ok(Journal { journal, merkle, frontier, boundary_recorded: true, hasher, }) } } /// The number of items to apply to the Merkle structure in a single batch. const APPLY_BATCH_SIZE: NonZeroU64 = NZU64!(1 << 16); /// The height of the aligned subtrees a replay at initialization hashes whole, apart from the /// tree it appends them to. Small in tests, so ordinary logs span many subtrees. #[cfg(not(test))] const SUBTREE_HEIGHT: u32 = 17; #[cfg(test)] const SUBTREE_HEIGHT: u32 = 4; /// Chunks a [LeafSink] buffers ahead of the Merkle structure appending them. const BUFFERED_CHUNKS: usize = 8; /// Where a reader that scans a recovering journal's operations sends them hashed, chunk by chunk, /// so the journal rebuilds its Merkle structure without reading them again. pub(crate) struct LeafSink> { plan: ChunkPlan, hasher: H, tx: mpsc::Sender>, } impl> LeafSink { /// The chunks to scan, hash and send, in position order. Together they cover every operation /// from the journal's pruning boundary to its end. pub(crate) fn chunks(&self) -> impl Iterator> + Send + 'static { self.plan.chunks() } /// A hasher for `chunk`, one of [Self::chunks]. pub(crate) fn chunk_hasher(&self, chunk: Range) -> ChunkHasher { self.plan.hasher(chunk, self.hasher.clone()) } /// Send the next chunk's digests. Returns false if the journal no longer wants them. pub(crate) async fn send(&self, chunk: Chunk) -> bool { self.tx.send(chunk).await.is_ok() } } impl Journal where F: Family, E: Context, C: Backing, H: Hasher, S: Strategy, { /// Create an authenticated journal ending at its last matching item. /// /// An empty retained range preserves its append position. #[boxed] pub async fn new( context: E, merkle_cfg: Config, journal_cfg: C::Config, predicate: fn(&C::Item) -> bool, bagging: merkle::Bagging, ) -> Result> { Self::prepare(context, merkle_cfg, journal_cfg, None, predicate, bagging) .await? .finish() .await } /// Recover a journal whose last matching item ends at or below `max_size`. /// /// Initialization durably discards the suffix before returning. When the journal retains /// its first item and no item matches at or below `max_size`, it is emptied and its frontier /// discarded, whatever that frontier recorded. If that emptying is interrupted, repeat this /// call with the same `max_size` before any other open. Until then [Self::new] can fail or find /// the journal fully pruned at the old frontier. A cap below retained history, or pruned /// history with no matching retained item, returns a pruning error. #[boxed] pub async fn init_at_most( context: E, merkle_cfg: Config, journal_cfg: C::Config, max_size: u64, predicate: fn(&C::Item) -> bool, bagging: merkle::Bagging, ) -> Result> { Self::prepare( context, merkle_cfg, journal_cfg, Some(max_size), predicate, bagging, ) .await? .finish() .await } /// Select and validate component availability before deliberately discarding history. pub(crate) async fn prepare( context: E, merkle_cfg: Config, journal_cfg: C::Config, max_size: Option, predicate: fn(&C::Item) -> bool, bagging: merkle::Bagging, ) -> Result, Error> { let frontier = Frontier::open(context.child("frontier"), merkle_cfg.partition.clone()).await?; let journal = C::recover(context.child("journal"), journal_cfg, max_size).await?; let bounds = journal.bounds(); // An unbounded reopen preserves a fully pruned journal's append position. Other // selections need a retained matching item, except for empty genesis. let (boundary, pins) = frontier.boundary(); let fully_pruned = max_size.is_none() && *boundary == bounds.end; let selected_end = if fully_pruned { bounds.end } else { journal .last_matching(max_size.unwrap_or(u64::MAX), predicate) .await? }; // A selection that is empty at position zero leaves nothing to authenticate, so the // frontier beside it is discarded, whatever it recorded. [Recovery::assemble] records // genesis once the emptied journal is durable. let (boundary, pins) = if bounds.start == 0 && selected_end == 0 { (Location::new(0), Vec::new()) } else { if *boundary < bounds.start || (*boundary > bounds.end && max_size.is_none_or(|max| max >= *boundary)) { return Err( merkle::Error::DataCorrupted("frontier outside operation journal").into(), ); } if !fully_pruned && *boundary != 0 && selected_end <= *boundary { return Err(JournalError::ItemPruned(*boundary).into()); } (boundary, pins) }; let merkle_context = context.child("merkle"); let merkle = Tree::new(boundary, pins, &merkle_cfg, &merkle_context)?; Ok(Recovery { context: context.child("replay"), journal, frontier, merkle, hasher: StandardHasher::::new(bagging), selected_end, }) } } impl Contiguous for Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { type Item = C::Item; fn bounds(&self) -> Range { let mut bounds = self.journal.bounds(); bounds.start = bounds.start.max(*self.merkle.bounds().start); bounds } async fn read(&self, position: u64) -> Result { if position < self.bounds().start { return Err(JournalError::ItemPruned(position)); } self.journal.read(position).await } async fn read_many(&self, positions: &[u64]) -> Result, JournalError> { let mut shards = self.read_many_sharded(positions).await?; if shards.len() == 1 { return Ok(shards.pop().expect("length checked")); } let mut items = Vec::with_capacity(positions.len()); for shard in shards { items.extend(shard); } Ok(items) } fn try_read_sync(&self, position: u64) -> Option { if position < self.bounds().start { return None; } self.journal.try_read_sync(position) } fn try_read_many_sync(&self, positions: &[u64]) -> Vec> { let mut items = self.journal.try_read_many_sync(positions); let start = self.bounds().start; for (position, item) in positions.iter().zip(&mut items) { if *position >= start { break; } *item = None; } items } async fn replay( &self, range: Range, buffer: NonZeroUsize, read_options: ReadOptions, ) -> Result, JournalError>> + Send, JournalError> { if range.start < self.bounds().start { return Err(JournalError::ItemPruned(range.start)); } self.journal.replay(range, buffer, read_options).await } } impl merkle::storage::Storage for Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { type Digest = H::Digest; fn size(&self) -> Position { self.merkle.size() } async fn get_node(&self, position: Position) -> Result, merkle::Error> { self.merkle .get_node(&self.journal, &self.hasher, position) .await } async fn get_nodes( &self, positions: &[Position], ) -> Result, merkle::Error> { self.merkle .get_nodes(&self.journal, &self.hasher, positions) .await } } /// The nodes held in memory, resident or pinned, which include every peak. A node rebuilt from /// operations reads as absent. impl Readable for Journal where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { type Family = F; type Digest = H::Digest; fn size(&self) -> Position { Readable::size(&self.merkle) } fn get_node(&self, pos: Position) -> Option { Readable::get_node(&self.merkle, pos) } } /// A journal under initialization, with read access before its retained end is finalized. /// /// Finishing consumes this owner. A live journal cannot regain recovery access. Opening may /// repair torn storage, but selecting a prefix does not itself discard journal history. pub trait BackingRecovery: Send + Sync + Sized { /// The live journal produced after recovery finishes. type Journal: Mutable; /// Available item positions, including the retained pruning boundary. fn bounds(&self) -> Range; /// Read a retained item for initialization validation. fn read( &self, position: u64, ) -> impl Future::Item, JournalError>> + Send; /// Discard stored items and establish an empty journal at `size` during initialization. fn reset(self, size: u64) -> impl Future> + Send; /// Durably retain the items in `bounds().start..min(size, bounds().end)` and publish the live /// journal. Returns [JournalError::ItemPruned] if `size` lies below the retained start. fn finish(self, size: u64) -> impl Future> + Send; /// Select the latest retained item satisfying `predicate` below an exclusive ceiling. fn last_matching

( &self, ceiling: u64, mut predicate: P, ) -> impl Future> + Send where P: FnMut(&::Item) -> bool + Send, { async move { let bounds = self.bounds(); // A ceiling below retained history cannot select a supported prefix. if ceiling < bounds.start { return Err(JournalError::ItemPruned(ceiling)); } // Search backward and return the exclusive end immediately after the latest match. let mut end = bounds.end.min(ceiling); while end > bounds.start { if predicate(&self.read(end - 1).await?) { return Ok(end); } end -= 1; } // Only an unpruned journal can establish genesis when no retained item matches. if bounds.start != 0 { return Err(JournalError::ItemPruned(bounds.start)); } Ok(0) } } } /// A [Mutable] journal that can back an authenticated [Journal]. pub trait Backing: Mutable { /// The configuration needed to initialize this journal. type Config: Clone + Send + Sync; /// Initialization-owned storage used to select and validate the retained prefix. type Recovery: BackingRecovery; /// Open recovery storage for an optional exclusive item end. Implementations may inspect /// later storage to validate recovery boundaries. Returns [JournalError::ItemPruned] when /// `max_size` lies below the retained start. fn recover( context: E, cfg: Self::Config, max_size: Option, ) -> impl Future> + Send; /// Open recovery storage reset to an empty journal at `size`, discarding stored items /// without reading them. Returns [JournalError::SizeOverflow] for `u64::MAX`. fn clear( context: E, cfg: Self::Config, size: u64, ) -> impl Future> + Send; /// Positions stored items may occupy, determined without reading them. /// /// The start is the retained start and the end bounds every stored item. A pending reset /// yields an empty span at its target. fn span( context: E, cfg: &Self::Config, ) -> impl Future, JournalError>> + Send; } /// Whether `span` contains `position` or is empty exactly at it. fn covers(span: &Range, position: u64) -> bool { position == span.start || span.contains(&position) } /// A [Backing] journal's storage, as [Stored::open] leaves it. pub(crate) enum Stored> { /// Recovery opened bounded at the requested end. Opened(J::Recovery), /// Storage whose span cannot hold the requested position, left unopened. Unopened { context: E, cfg: J::Config }, } impl> Stored { /// Open recovery bounded at `max_size` when [Backing::span] contains `position` or is empty /// exactly at it. Otherwise return the storage unopened. pub(crate) async fn open( context: E, cfg: J::Config, position: u64, max_size: u64, ) -> Result { if !covers(&J::span(context.child("span"), &cfg).await?, position) { return Ok(Self::Unopened { context, cfg }); } let recovery = J::recover(context, cfg, Some(max_size)).await?; Ok(Self::Opened(recovery)) } } /// Durably reset the frontier under `config` to genesis before a state sync appends operations /// in place of every operation the journal held. pub(crate) async fn discard_frontier( context: E, config: &Config, ) -> Result<(), Error> where F: Family, E: Context, H: Hasher, S: Strategy, { Frontier::::open(context, config.partition.clone()) .await? .reset() .await?; Ok(()) } /// The digests pinned at `location`, computed from the local frontier if its rebuilt root matches /// `expected_root`. Returns `None` if the frontier cannot cover `location` or its root differs. pub(crate) async fn pinned_nodes_from_frontier( context: E, config: &Config, journal: &C, hasher: &StandardHasher, location: Location, expected_root: H::Digest, inactive_peaks: usize, ) -> Result>, Error> where F: Family, E: Context, C: Contiguous, H: Hasher, S: Strategy, { let frontier = Frontier::::open(context.child("frontier"), config.partition.clone()) .await?; let (boundary, pins) = frontier.boundary(); let bounds = journal.bounds(); if boundary > location || bounds.start > *boundary || bounds.end < *location { return Ok(None); } let tree = Tree::new(boundary, pins, config, &context)? .replay(journal, hasher, Location::new(bounds.end), APPLY_BATCH_SIZE) .await?; if tree.root(hasher, inactive_peaks)? != expected_root { return Ok(None); } Ok(Some(tree.pinned_nodes_at(journal, hasher, location).await?)) } /// Recover the portion useful for state sync, or reset an unusable local range. pub(crate) async fn init_sync>( context: E, cfg: J::Config, range: Range, ) -> Result { assert!(!range.is_empty(), "range must not be empty"); // Storage whose span cannot hold the sync start is cleared without reading stored items. // The span end reflects blob capacity, which can overstate the recovered end when the tail // is short or has a gap, so an opened prefix that does not cover the sync start is reset. let pending = match Stored::::open(context, cfg, range.start, range.end).await? { Stored::Opened(pending) if covers(&pending.bounds(), range.start) => pending, Stored::Opened(pending) => pending.reset(range.start).await?, Stored::Unopened { context, cfg } => J::clear(context, cfg, range.start).await?, }; // Operations before the sync start stay until the synced journal records its boundary, since // local pins for the target may be rebuilt from them. pending.finish(range.end).await } #[cfg(test)] mod tests { use super::{Config as MerkleConfig, *}; use crate::{ journal::contiguous::{ fixed::{Config as JConfig, Journal as ContiguousJournal}, tests::replay_items, variable::{Config as VConfig, Journal as VariableJournal}, }, merkle::{ Bagging::{BackwardFold, ForwardFold}, mmb, mmr, }, qmdb::{ any::operation::{Unordered as Op, update::Unordered as Update}, operation::Committable, value::FixedEncoding, }, utils::{ detached::{DropMonitor, block_strategy}, task_metrics::{self, RUNNING}, }, }; use commonware_codec::{Encode, FixedSize}; use commonware_cryptography::{Sha256, sha256::Digest}; use commonware_macros::{test_collect_traces, test_traced}; use commonware_parallel::{Rayon, Sequential, mocks::Explorer, rayon::ThreadPoolBuilder}; use commonware_runtime::{ Error as RuntimeError, Metrics as _, Runner as _, Storage as _, Strategizer as _, Supervisor as _, buffer::paged::CacheRef, deterministic::{self, Context}, mocks::{ DelayedSyncContext, MutationFaultContext, MutationFaults, PendingSyncs, ReadGateContext, RecordingContext, drive_pending_syncs, }, reschedule, telemetry::traces::collector::TraceStorage, }; use commonware_utils::{NZU16, NZU64, NZUsize, probability}; use futures::{FutureExt as _, StreamExt as _}; use std::{ future::Future, num::{NonZeroU16, NonZeroU64, NonZeroUsize}, time::Duration, }; const PAGE_SIZE: NonZeroU16 = NZU16!(101); const PAGE_CACHE_SIZE: NonZeroUsize = NZUsize!(11); /// Generic operation type for testing, parameterized by Merkle family. type TestOp = Op>; /// Generic authenticated journal type for testing, parameterized by Merkle family. type TestJournal = Journal< F, deterministic::Context, ContiguousJournal>, Sha256, Sequential, >; type RecordingTestJournal = Journal< F, RecordingContext, ContiguousJournal, TestOp>, Sha256, Sequential, >; fn journal_root(journal: &TestJournal) -> Digest { journal.root(0).unwrap() } fn batch_root( journal: &TestJournal, batch: &MerkleizedBatch, Sequential>, ) -> Digest { batch.root(&journal.hasher, 0).unwrap() } fn merkleize_with( batch: UnmerkleizedBatch, Sequential>, base: &Mem, items: Vec>, ) -> MerkleizedBatchArc, Sequential> { batch.add_many(items).merkleize(base) } /// Create Merkle configuration for tests with the given strategy. fn merkle_config_with(suffix: &str, strategy: S) -> MerkleConfig { MerkleConfig { partition: format!("mmr-metadata-{suffix}"), replay_buffer: NZUsize!(1024), strategy, resident_height: Default::default(), } } /// Create Merkle configuration for tests. fn merkle_config(suffix: &str) -> MerkleConfig { merkle_config_with(suffix, Sequential) } /// Create journal configuration for tests. fn journal_config(suffix: &str) -> JConfig { JConfig { partition: format!("journal-{suffix}"), items_per_blob: NZU64!(7), write_buffer: NZUsize!(1024), replay_buffer: NZUsize!(1024), page_cache: CacheRef::new(PAGE_SIZE, PAGE_CACHE_SIZE), } } /// Create a new empty authenticated journal. async fn create_empty_journal( context: Context, suffix: &str, ) -> TestJournal { let merkle_cfg = merkle_config(suffix); let journal_cfg = journal_config(suffix); TestJournal::::new( context, merkle_cfg, journal_cfg, |op: &TestOp| op.is_commit(), ForwardFold, ) .await .unwrap() } #[test] fn test_batches_inherit_journal_bagging() { deterministic::Runner::default().start(|context| async move { let merkle_cfg = merkle_config("batch-bagging"); let journal_cfg = journal_config("batch-bagging"); let journal = TestJournal::::new( context, merkle_cfg, journal_cfg, |op: &TestOp| op.is_commit(), BackwardFold, ) .await .unwrap(); let batch = journal.new_batch(); assert_eq!(batch.hasher.root_bagging(), BackwardFold); let merkleized = batch.merkleize(journal.merkle.mem()); let child: UnmerkleizedBatch, Sequential> = merkleized.new_batch(); assert_eq!(child.hasher.root_bagging(), BackwardFold); }); } /// Large batched reads shard across the strategy pool and match per-position reads. #[test] fn test_read_many_shards_across_strategy_pool() { deterministic::Runner::default().start(|context| async move { // The most parallel shape of a parallelism-2 strategy splits the probe into two // shards. The tiny test page cache pushes most positions through the batched miss // fallback while the write buffer serves the tail synchronously. let strategy = Explorer::parallel(&context.strategy(NZUsize!(2))); let merkle_cfg = merkle_config_with("shard", strategy); let journal_cfg = journal_config("shard"); type ShardedJournal = Journal< mmr::Family, Context, ContiguousJournal>, Sha256, Explorer, >; let mut journal = ShardedJournal::new( context, merkle_cfg, journal_cfg, |op: &TestOp| op.is_commit(), ForwardFold, ) .await .unwrap(); let count = 4200u64; for i in 0..count { let op = create_operation::((i % 251) as u8); (journal, _) = journal.append(&op).await.unwrap(); } let journal = journal.sync().await.unwrap(); let positions: Vec = (0..count).collect(); let shards = journal.read_many_sharded(&positions).await.unwrap(); assert_eq!(shards.len(), 2, "the probe must run in two shards"); let batch = Contiguous::read_many(&journal, &positions).await.unwrap(); assert_eq!(batch.len(), positions.len()); for &pos in &positions { let single = Contiguous::read(&journal, pos).await.unwrap(); assert_eq!(batch[pos as usize], single); } // An empty batch is a no-op, even with a multi-threaded strategy. assert!( Contiguous::read_many(&journal, &[]) .await .unwrap() .is_empty() ); }); } /// A non-increasing batch panics deterministically, even when fully cached. #[test] #[should_panic(expected = "positions must be strictly increasing")] fn test_read_many_rejects_unsorted_positions() { deterministic::Runner::default().start(|context| async move { let mut journal = create_empty_journal::(context, "unsorted").await; for i in 0..2u8 { let op = create_operation::(i); (journal, _) = journal.append(&op).await.unwrap(); } let journal = journal.sync().await.unwrap(); let _ = Contiguous::read_many(&journal, &[1, 0]).await; }); } /// Create a test operation with predictable values based on index. fn create_operation(index: u8) -> TestOp { TestOp::::Update(Update( Sha256::fill(index), Sha256::fill(index.wrapping_add(1)), )) } /// Create an authenticated journal with N committed operations. /// /// Operations are added and then synced to ensure they are committed. async fn create_journal_with_ops( context: Context, suffix: &str, count: usize, ) -> TestJournal { let mut journal = create_empty_journal::(context, suffix).await; for i in 0..count { let op = create_operation::(i as u8); let loc; (journal, loc) = journal.append(&op).await.unwrap(); assert_eq!(loc, Location::::new(i as u64)); } journal = journal.sync().await.unwrap(); journal } /// Create separate Merkle and journal components for testing alignment. /// /// These components are created independently and can be manipulated separately to test /// scenarios where the Merkle structure and journal are out of sync (e.g., one ahead of the /// other). async fn create_components( context: Context, suffix: &str, ) -> ( Tree, ContiguousJournal>, StandardHasher, ) { let hasher = StandardHasher::new(ForwardFold); let merkle = Tree::new( Location::new(0), Vec::new(), &merkle_config(suffix), &context, ) .unwrap(); let journal = ContiguousJournal::init(context.child("journal"), journal_config(suffix)) .await .unwrap(); (merkle, journal, hasher) } /// Verify that a proof correctly proves the given operations are included in the Merkle /// structure. fn verify_proof( proof: &Proof::Digest>, hasher: &StandardHasher, start_loc: Location, operations: &[TestOp], root: &::Digest, ) -> bool { let encoded_ops: Vec<_> = operations.iter().map(|op| op.encode()).collect(); proof.verify_range_inclusion(hasher, start_loc, &encoded_ops, root) } /// Verify that new() creates an empty authenticated journal. async fn test_new_creates_empty_journal_inner(context: Context) { let journal = create_empty_journal::(context, "new-empty").await; let bounds = journal.bounds(); assert_eq!(bounds.end, 0); assert_eq!(bounds.start, 0); assert!(bounds.is_empty()); } #[test_traced("INFO")] fn test_new_creates_empty_journal_mmr() { let executor = deterministic::Runner::default(); executor.start(test_new_creates_empty_journal_inner::); } #[test_traced("INFO")] fn test_new_creates_empty_journal_mmb() { let executor = deterministic::Runner::default(); executor.start(test_new_creates_empty_journal_inner::); } /// Verify that align() correctly handles empty Merkle and journal components. async fn test_align_with_empty_mmr_and_journal_inner(context: Context) { let (merkle, journal, hasher) = create_components::(context, "align-empty").await; let merkle = TestJournal::::align(merkle, &journal, &hasher, APPLY_BATCH_SIZE) .await .unwrap(); assert_eq!(merkle.leaves(), Location::::new(0)); assert_eq!(journal.size(), 0); } #[test_traced("INFO")] fn test_align_with_empty_mmr_and_journal_mmr() { let executor = deterministic::Runner::default(); executor.start(test_align_with_empty_mmr_and_journal_inner::); } #[test_traced("INFO")] fn test_align_with_empty_mmr_and_journal_mmb() { let executor = deterministic::Runner::default(); executor.start(test_align_with_empty_mmr_and_journal_inner::); } /// Verify that align() replays journal operations when journal is ahead of Merkle. async fn test_align_when_journal_ahead_inner(context: Context) { let (merkle, mut journal, hasher) = create_components::(context, "journal-ahead").await; // Add 20 operations to journal only for i in 0..20 { let op = create_operation::(i as u8); (journal, _) = journal.append(&op).await.unwrap(); } // Add commit let commit_op = TestOp::::Commit(None, Location::::new(0)); let (journal, _) = journal.append(&commit_op).await.unwrap(); let journal = journal.sync().await.unwrap(); // Journal has 21 operations, Merkle has 0 leaves let merkle = TestJournal::::align(merkle, &journal, &hasher, APPLY_BATCH_SIZE) .await .unwrap(); // Merkle should have been replayed to match journal assert_eq!(merkle.leaves(), Location::::new(21)); assert_eq!(journal.size(), 21); } #[test_traced("WARN")] fn test_align_when_journal_ahead_mmr() { let executor = deterministic::Runner::default(); executor.start(test_align_when_journal_ahead_inner::); } #[test_traced("WARN")] fn test_align_when_journal_ahead_mmb() { let executor = deterministic::Runner::default(); executor.start(test_align_when_journal_ahead_inner::); } /// Builds a journal that is ahead of its Merkle structure, replays it on `strategy`, and /// returns the resulting Merkle state. async fn test_align_replay_parallel_matches_serial_inner( context: Context, strategy: S, ) -> (Location, Digest) { type ReplayJournal = Journal< F, deterministic::Context, ContiguousJournal>, Sha256, S, >; // Build a journal that is ahead of the Merkle structure. let mut journal = ContiguousJournal::init( context.child("journal"), journal_config("replay-strategies"), ) .await .unwrap(); for i in 0..20 { (journal, _) = journal .append(&create_operation::(i as u8)) .await .unwrap(); } let commit_op = TestOp::::Commit(None, Location::::new(0)); let (journal, _) = journal.append(&commit_op).await.unwrap(); let journal = journal.sync().await.unwrap(); // Replay in batches of seven, so the 21 leaves take three batches and the strategy picks // the shape that hashes each one. let hasher = StandardHasher::::new(ForwardFold); let merkle = Tree::new( Location::new(0), Vec::new(), &merkle_config_with("replay", strategy), &context, ) .unwrap(); let merkle = ReplayJournal::::align(merkle, &journal, &hasher, NZU64!(7)) .await .unwrap(); assert_eq!(merkle.leaves(), Location::::new(21)); (merkle.leaves(), merkle.root(&hasher, 0).unwrap()) } /// Replays on the runtime's pool in its most parallel shape and in seeded shapes, each of /// which must match a serial replay. The pool must be the runtime's, since the replay awaits /// jobs it hands off. fn align_replay_shapes() { let serial = deterministic::Runner::default().start(|context| { test_align_replay_parallel_matches_serial_inner::(context, Sequential) }); for seed in [None, Some(0), Some(1), Some(2), Some(3)] { let replayed = deterministic::Runner::default().start(|context| async move { let pool = context.strategy(NZUsize!(2)); let strategy = seed.map_or_else( || Explorer::parallel(&pool), |seed| Explorer::seeded(&pool, seed), ); test_align_replay_parallel_matches_serial_inner::(context, strategy).await }); assert_eq!(replayed, serial, "seed {seed:?}"); } } #[test_traced("WARN")] fn test_align_replay_parallel_matches_serial_mmr() { align_replay_shapes::(); } #[test_traced("WARN")] fn test_align_replay_parallel_matches_serial_mmb() { align_replay_shapes::(); } /// Initialization discards a persisted suffix that contains no complete commit. async fn test_align_with_mismatched_committed_ops_inner( context: Context, ) { let mut journal = create_empty_journal::(context.child("first"), "mismatched").await; // Add 20 uncommitted operations for i in 0..20 { let loc; (journal, loc) = journal .append(&create_operation::(i as u8)) .await .unwrap(); assert_eq!(loc, Location::::new(i as u64)); } let size_before = journal.size(); assert_eq!(size_before, 20); // A persisted suffix without a commit must be discarded on restart. journal.sync().await.unwrap(); let journal = create_empty_journal::(context.child("second"), "mismatched").await; // Uncommitted operations should be gone assert_eq!(journal.size(), 0); } #[test_collect_traces("INFO")] fn test_align_with_mismatched_committed_ops_mmr(traces: TraceStorage) { let executor = deterministic::Runner::default(); executor.start(|context| { test_align_with_mismatched_committed_ops_inner::(context) }); traces .get_by_level(tracing::Level::WARN) .expect_event(|event| { let metadata = &event.metadata; metadata.content == "rewinding journal items" && metadata.expect_field_exact("journal_size", "20").is_ok() && metadata.expect_field_exact("rewound_items", "20").is_ok() }) .unwrap(); } #[test_traced("INFO")] fn test_align_with_mismatched_committed_ops_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_align_with_mismatched_committed_ops_inner::(context) }); } async fn test_initialization_selection_inner(context: Context) { // Select the latest complete commit at or below each cap, both before and after pruning. for start in [0, 7] { for cap in [0, 1, 2, 3, 4, 7, 8, 11, 12, 14, 15, 100] { let suffix = format!("select-{start}-{cap}"); let cfg = journal_config(&suffix); let mut journal = ContiguousJournal::init(context.child("create"), cfg.clone()) .await .unwrap(); for i in 0..15 { let op = if [1, 3, 10, 13].contains(&i) { TestOp::::Commit(None, Location::new(0)) } else { create_operation::(i) }; (journal, _) = journal.append(&op).await.unwrap(); } journal = journal.sync().await.unwrap(); if start > 0 { (journal, _) = journal.prune(start).await.unwrap(); } drop(journal); let pending = > as Backing<_>>::recover( context.child("select"), cfg.clone(), Some(cap), ) .await; // Derive the expected exclusive end from the retained commit candidates. let expected = [2, 4, 11, 14] .into_iter() .filter(|end| *end <= cap && *end > start) .max(); if cap < start { assert!(matches!(pending, Err(JournalError::ItemPruned(_)))); continue; } let pending = pending.unwrap(); let selected = pending.last_matching(cap, |op| op.is_commit()).await; if expected.is_none() && start > 0 { assert!(matches!(selected, Err(JournalError::ItemPruned(_)))); continue; } let size = selected.unwrap(); assert_eq!(size, expected.unwrap_or(0)); // Publication makes the selected end authoritative on reopen. drop(pending.finish(size).await.unwrap()); let journal = ContiguousJournal::<_, TestOp>::init(context.child("restart"), cfg) .await .unwrap(); assert_eq!(journal.size(), size); } } // Bound both authenticated components to every prefix around the durable tip. for cap in [0, 1, 2, 3, 4, 5, 6, 7, 8, 100] { let suffix = format!("authenticated-cap-{cap}"); let mc = merkle_config(&suffix); let jc = journal_config(&suffix); let mut journal = TestJournal::::new( context.child("create_auth"), mc.clone(), jc.clone(), |_| true, ForwardFold, ) .await .unwrap(); let mut roots = vec![journal_root(&journal)]; for i in 0..8 { (journal, _) = journal.append(&create_operation::(i)).await.unwrap(); roots.push(journal_root(&journal)); } _ = journal.sync().await.unwrap(); let journal = TestJournal::::init_at_most( context.child("cap_auth"), mc.clone(), jc.clone(), cap, |_| true, ForwardFold, ) .await .unwrap(); let size = cap.min(8); assert_eq!(*journal.size(), size); assert_eq!(journal_root(&journal), roots[size as usize]); drop(journal); let journal = TestJournal::::new(context.child("restart_auth"), mc, jc, |_| true, ForwardFold) .await .unwrap(); assert_eq!(*journal.size(), size); assert_eq!(journal_root(&journal), roots[size as usize]); } } #[test_traced("INFO")] fn test_initialization_selection_mmr() { let executor = deterministic::Runner::default(); executor.start(test_initialization_selection_inner::); } #[test_traced("INFO")] fn test_initialization_selection_mmb() { let executor = deterministic::Runner::default(); executor.start(test_initialization_selection_inner::); } /// Commit A then B, reopen at A, append an equal-length branch without syncing, then crash /// with the appends retained and any unsynced resize lost. Recovery must yield A or a prefix /// of the new branch, never B's operations. fn init_at_most_equal_length_branch_crash_inner() { const A: u64 = 4; fn is_commit(op: &TestOp) -> bool { op.is_commit() } // One operation per page makes the reopen bound page aligned in the operation journal. // The two-page write buffer floor flushes the branch in whole-buffer bursts. fn journal_cfg(suffix: &str) -> JConfig { let page = NonZeroU16::new( as FixedSize>::SIZE as u16).unwrap(); JConfig { partition: format!("journal-{suffix}"), items_per_blob: NZU64!(1000), write_buffer: NZUsize!(1), replay_buffer: NZUsize!(1024), page_cache: CacheRef::new(page, PAGE_CACHE_SIZE), } } // End each branch at a commit so initialization can select it as a complete state. fn branch(first: u8, len: u64) -> Vec> { let mut ops: Vec> = (0..len - 1) .map(|i| create_operation::(first + i as u8)) .collect(); ops.push(TestOp::::Commit(None, Location::new(0))); ops } // A three-operation branch is flushed whole and a five-operation branch only in part, // so recovery sees the new commit in the first case and only A's commit in the second. for len in [3u64, 5] { let suffix = format!("equal-length-branch-{len}"); let crash_suffix = suffix.clone(); let (roots, checkpoint) = deterministic::Runner::default().start_and_recover(move |context| async move { let mc = merkle_config(&crash_suffix); let jc = journal_cfg::(&crash_suffix); let mut journal = TestJournal::::new( context.child("create"), mc.clone(), jc.clone(), is_commit::, ForwardFold, ) .await .unwrap(); for op in branch::(0, A) { (journal, _) = journal.append(&op).await.unwrap(); } let mut journal = journal.sync().await.unwrap(); let root_a = journal_root(&journal); for op in branch::(50, len) { (journal, _) = journal.append(&op).await.unwrap(); } let journal = journal.sync().await.unwrap(); assert_eq!(*journal.size(), A + len); drop(journal); // Keep unsynced writes and drop unsynced resizes at the crash. *context.storage_fault_config().write() = deterministic::FaultConfig { write_rate: Some(deterministic::WriteConfig { failure_rate: probability!(0.0), retention_rate: probability!(1.0), mode: deterministic::PartialWriteMode::Prefix, }), resize_rate: Some(deterministic::ResizeConfig { failure_rate: probability!(0.0), partial_rate: probability!(0.0), }), ..Default::default() }; let mut journal = TestJournal::::init_at_most( context.child("cap"), mc, jc, A, is_commit::, ForwardFold, ) .await .unwrap(); assert_eq!(*journal.size(), A); assert_eq!(journal_root(&journal), root_a); let mut roots = vec![root_a]; for op in branch::(100, len) { (journal, _) = journal.append(&op).await.unwrap(); roots.push(journal_root(&journal)); } drop(journal); roots }); // Recover the selected base commit or a prefix of its replacement branch, with no // operations from the discarded branch. deterministic::Runner::from(checkpoint).start(move |context| async move { *context.storage_fault_config().write() = deterministic::FaultConfig::default(); let journal = TestJournal::::new( context.child("reopen"), merkle_config(&suffix), journal_cfg::(&suffix), is_commit::, ForwardFold, ) .await .unwrap(); let size = *journal.size(); assert!( (A..=A + len).contains(&size), "recovered size {size} is not a prefix of the new branch" ); let expected = branch::(100, len); for pos in A..size { assert_eq!( journal.read(pos).await.unwrap(), expected[(pos - A) as usize], "operation at retained position {pos} was never written there" ); } // The recovered root and proof must authenticate that same operation history. let root = journal_root(&journal); assert_eq!( root, roots[(size - A) as usize], "root does not match the recovered operations" ); let (proof, ops) = journal .proof(Location::new(0), NonZeroU64::new(size).unwrap(), 0) .await .unwrap(); assert_eq!(ops.len() as u64, size); assert!(verify_proof( &proof, &StandardHasher::new(ForwardFold), Location::new(0), &ops, &root )); journal.destroy().await.unwrap(); }); } } #[test_traced("INFO")] fn test_init_at_most_equal_length_branch_crash_mmr() { init_at_most_equal_length_branch_crash_inner::(); } #[test_traced("INFO")] fn test_init_at_most_equal_length_branch_crash_mmb() { init_at_most_equal_length_branch_crash_inner::(); } /// Verify that append() increments the operation count, returns correct locations, and /// operations can be read back correctly. async fn test_apply_op_and_read_operations_inner(context: Context) { let mut journal = create_empty_journal::(context, "apply_op").await; assert_eq!(journal.size(), 0); // Add 50 operations let expected_ops: Vec<_> = (0..50).map(|i| create_operation::(i as u8)).collect(); for (i, op) in expected_ops.iter().enumerate() { let loc; (journal, loc) = journal.append(op).await.unwrap(); assert_eq!(loc, Location::::new(i as u64)); assert_eq!(journal.size(), (i + 1) as u64); } assert_eq!(journal.size(), 50); // Verify all operations can be read back correctly journal = journal.sync().await.unwrap(); for (i, expected_op) in expected_ops.iter().enumerate() { let read_op = journal.read(*Location::::new(i as u64)).await.unwrap(); assert_eq!(read_op, *expected_op); } } #[test_traced("INFO")] fn test_apply_op_and_read_operations_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_op_and_read_operations_inner::); } #[test_traced("INFO")] fn test_apply_op_and_read_operations_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_op_and_read_operations_inner::); } /// Verify that read() returns correct operations at various positions. async fn test_read_operations_at_various_positions_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "read", 50).await; // Verify reading first operation let first_op = journal.read(*Location::::new(0)).await.unwrap(); assert_eq!(first_op, create_operation::(0)); // Verify reading middle operation let middle_op = journal.read(*Location::::new(25)).await.unwrap(); assert_eq!(middle_op, create_operation::(25)); // Verify reading last operation let last_op = journal.read(*Location::::new(49)).await.unwrap(); assert_eq!(last_op, create_operation::(49)); // Verify all operations match expected values for i in 0..50 { let op = journal.read(*Location::::new(i)).await.unwrap(); assert_eq!(op, create_operation::(i as u8)); } } #[test_traced("INFO")] fn test_read_operations_at_various_positions_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_read_operations_at_various_positions_inner::(context) }); } #[test_traced("INFO")] fn test_read_operations_at_various_positions_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_read_operations_at_various_positions_inner::(context) }); } /// Verify that read() returns an error for pruned operations. async fn test_read_pruned_operation_returns_error_inner( context: Context, ) { let mut journal = create_journal_with_ops::(context, "read_pruned", 100).await; // Add commit and prune (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let pruned_boundary; (journal, pruned_boundary) = journal.prune(Location::::new(50)).await.unwrap(); // Try to read an operation before the pruned boundary let read_loc = Location::::new(0); if read_loc < pruned_boundary { let result = journal.read(*read_loc).await; assert!(matches!(result, Err(crate::journal::Error::ItemPruned(_)))); } } #[test_traced("INFO")] fn test_read_pruned_operation_returns_error_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_read_pruned_operation_returns_error_inner::(context) }); } #[test_traced("INFO")] fn test_read_pruned_operation_returns_error_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_read_pruned_operation_returns_error_inner::(context) }); } /// Verify that read() returns an error for out-of-range locations. async fn test_read_out_of_range_returns_error_inner(context: Context) { let journal = create_journal_with_ops::(context, "read_oob", 3).await; // Try to read beyond the end let result = journal.read(*Location::::new(10)).await; assert!(matches!( result, Err(crate::journal::Error::ItemOutOfRange(_)) )); } #[test_traced("INFO")] fn test_read_out_of_range_returns_error_mmr() { let executor = deterministic::Runner::default(); executor.start(test_read_out_of_range_returns_error_inner::); } #[test_traced("INFO")] fn test_read_out_of_range_returns_error_mmb() { let executor = deterministic::Runner::default(); executor.start(test_read_out_of_range_returns_error_inner::); } /// Verify that we can read all operations back correctly. async fn test_read_all_operations_back_correctly_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "read_all", 50).await; assert_eq!(journal.size(), 50); // Verify all operations can be read back and match expected values for i in 0..50 { let op = journal.read(*Location::::new(i)).await.unwrap(); assert_eq!(op, create_operation::(i as u8)); } } #[test_traced("INFO")] fn test_read_all_operations_back_correctly_mmr() { let executor = deterministic::Runner::default(); executor.start(test_read_all_operations_back_correctly_inner::); } #[test_traced("INFO")] fn test_read_all_operations_back_correctly_mmb() { let executor = deterministic::Runner::default(); executor.start(test_read_all_operations_back_correctly_inner::); } /// Verify that sync() persists operations. async fn test_sync_inner(context: Context) { let mut journal = create_empty_journal::(context.child("first"), "close_pending").await; // Add 20 operations let expected_ops: Vec<_> = (0..20).map(|i| create_operation::(i as u8)).collect(); for (i, op) in expected_ops.iter().enumerate() { let loc; (journal, loc) = journal.append(op).await.unwrap(); assert_eq!(loc, Location::::new(i as u64),); } // Add commit operation to commit the operations let commit_loc; (journal, commit_loc) = journal .append(&TestOp::::Commit(None, Location::::new(0))) .await .unwrap(); assert_eq!( commit_loc, Location::::new(20), "commit should be at location 20" ); journal.sync().await.unwrap(); // Reopen and verify the operations persisted let journal = create_empty_journal::(context.child("second"), "close_pending").await; assert_eq!(journal.size(), 21); // Verify all operations can be read back for (i, expected_op) in expected_ops.iter().enumerate() { let read_op = journal.read(*Location::::new(i as u64)).await.unwrap(); assert_eq!(read_op, *expected_op); } } #[test_traced("INFO")] fn test_sync_mmr() { let executor = deterministic::Runner::default(); executor.start(test_sync_inner::); } #[test_traced("INFO")] fn test_sync_mmb() { let executor = deterministic::Runner::default(); executor.start(test_sync_inner::); } /// Awaiting a start_sync handle provides commit-level durability: committed operations /// survive a reopen, with recovery re-aligning the Merkle structure. async fn test_start_sync_durability_inner(context: Context) { let mut journal = create_empty_journal::(context.child("first"), "start_sync").await; let expected_ops: Vec<_> = (0..5).map(|i| create_operation::(i as u8)).collect(); for op in expected_ops.iter() { (journal, _) = journal.append(op).await.unwrap(); } (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(0))) .await .unwrap(); let handle; (journal, handle) = journal.start_sync().await.unwrap(); handle.await.unwrap(); let root = journal_root(&journal); drop(journal); let journal = create_empty_journal::(context.child("second"), "start_sync").await; assert_eq!(journal.size(), 6); assert_eq!(journal_root(&journal), root); for (i, expected_op) in expected_ops.iter().enumerate() { let read_op = journal.read(*Location::::new(i as u64)).await.unwrap(); assert_eq!(read_op, *expected_op); } } #[test_traced("INFO")] fn test_start_sync_durability_mmr() { let executor = deterministic::Runner::default(); executor.start(test_start_sync_durability_inner::); } #[test_traced("INFO")] fn test_start_sync_durability_mmb() { let executor = deterministic::Runner::default(); executor.start(test_start_sync_durability_inner::); } /// Delayed-sync context for exercising in-flight sync handles. type DelayedCtx = DelayedSyncContext; /// Authenticated journal over a delayed-sync storage backend. type DelayedTestJournal = Journal>, Sha256, Sequential>; /// Open an authenticated journal whose blob syncs park on `pending`. /// /// `new` durably persists the recovered journal, so while syncs park the returned future /// must be driven with [drive_pending_syncs] (or the mock unblocked first). fn open_delayed_journal( context: &Context, label: &'static str, suffix: &str, pending: &PendingSyncs, ) -> impl Future, Error>> { DelayedTestJournal::::new( DelayedCtx { inner: context.child(label), pending: pending.clone(), }, merkle_config(suffix), journal_config(suffix), |op: &TestOp| op.is_commit(), ForwardFold, ) } /// A sync handle must not block journal use while the backend sync is pending. #[test_traced("INFO")] fn test_start_sync_overlaps_work() { let executor = deterministic::Runner::default(); executor.start(|context| async move { let pending = PendingSyncs::default(); let open = open_delayed_journal(&context, "first", "start_sync_overlap", &pending); let mut journal = drive_pending_syncs(&pending, open).await.unwrap(); for i in 0..4 { (journal, _) = journal .append(&create_operation::(i)) .await .unwrap(); } let starts_before = pending.starts(); let entered_before = pending.entered(); let completions_before = pending.completions(); let handle; (journal, handle) = journal.start_sync().await.unwrap(); assert!(pending.starts() > starts_before); assert_eq!(pending.completions(), completions_before); // Observe the sync while the journal keeps working. let waiter = context .child("await_sync") .spawn(|_| async move { handle.await.unwrap() }); while pending.entered() == entered_before { reschedule().await; } // Appends and reads complete before the sync does. (journal, _) = journal .append(&create_operation::(4)) .await .unwrap(); let read_op = journal.read(0).await.unwrap(); assert_eq!(read_op, create_operation::(0)); assert_eq!( pending.completions(), completions_before, "the journal made progress while the sync was still in flight" ); pending.unblock(); waiter.await.unwrap(); // The mid-sync append is durable after the next sync. (journal, _) = journal .append(&TestOp::::Commit(None, Location::new(0))) .await .unwrap(); let handle; (journal, handle) = journal.start_sync().await.unwrap(); handle.await.unwrap(); let root = journal.root(0).unwrap(); drop(journal); let journal = open_delayed_journal(&context, "second", "start_sync_overlap", &pending) .await .unwrap(); assert_eq!(journal.size(), 6); assert_eq!(journal.root(0).unwrap(), root); }); } /// A sync begun by `start_sync` that fails in flight surfaces the error through both the /// returned handle and the next durability operation. #[test_traced("INFO")] fn test_start_sync_failure_propagates() { let executor = deterministic::Runner::default(); executor.start(|context| async move { // Pass syncs through so opening the journal doesn't park. let pending = PendingSyncs::default(); pending.unblock(); let mut journal = open_delayed_journal(&context, "first", "start_sync_fail", &pending) .await .unwrap(); for i in 0..4 { (journal, _) = journal .append(&create_operation::(i)) .await .unwrap(); } // Arm all future syncs to resolve to an injected error. pending.arm_fail(); let handle; (journal, handle) = journal.start_sync().await.unwrap(); assert!( handle.await.is_err(), "the sync handle surfaces the failure" ); let starts_before = pending.starts(); // A failed mutable method consumes the journal per the failures-are-fatal contract. assert!( matches!( journal.commit().await, Err(Error::Journal(JournalError::Runtime(_))) ), "the next durability op surfaces the failed in-flight sync" ); assert_eq!( pending.starts(), starts_before, "the surfaced error is the retained failure, not a fresh sync's" ); }); } /// A prune that crosses a blob waits for the in-flight sync before persisting its frontier. #[test_traced("INFO")] fn test_start_sync_prune_waits() { let executor = deterministic::Runner::default(); executor.start(|context| async move { let pending = PendingSyncs::default(); let open = open_delayed_journal(&context, "first", "start_sync_prune", &pending); let mut journal = drive_pending_syncs(&pending, open).await.unwrap(); for i in 0..20 { let op = create_operation::(i); (journal, _) = drive_pending_syncs(&pending, journal.append(&op)) .await .unwrap(); } let handle; (journal, handle) = journal.start_sync().await.unwrap(); let in_flight = pending.lock().len(); assert!(in_flight > 0); // While the operation sync is parked, the prune starts no durability work. Its // frontier write must follow the operations that justify it. pending.arm(); let mut prune = std::pin::pin!(journal.prune(Location::new(14))); assert!( prune.as_mut().now_or_never().is_none(), "prune finished while the in-flight sync was pending" ); assert_eq!( pending.calls(), 0, "prune synced while the in-flight sync was pending" ); pending.unblock(); let (journal, boundary) = prune.await.unwrap(); assert_eq!(boundary, Location::new(14)); assert_eq!(journal.journal.bounds().start, 14); handle.await.unwrap(); drop(journal); let frontier = Frontier::::open( context.child("after"), merkle_config("start_sync_prune").partition, ) .await .unwrap(); assert_eq!(frontier.boundary().0, Location::new(14)); }); } /// A prune whose commit fails leaves the frontier and the operations where they were. #[test] fn test_failed_prune_keeps_frontier() { deterministic::Runner::default().start(|context| async move { let pending = PendingSyncs::default(); pending.unblock(); let mut journal = open_delayed_journal(&context, "initial", "prune-failure", &pending) .await .unwrap(); for i in 0..50 { (journal, _) = journal.append(&create_operation(i)).await.unwrap(); } (journal, _) = journal .append(&TestOp::Commit(None, Location::new(0))) .await .unwrap(); pending.arm_fail(); assert!(matches!( journal.prune(Location::new(21)).await, Err(Error::Journal(JournalError::Runtime(_))) )); let frontier = Frontier::::Digest>::open( context.child("reopen"), merkle_config("prune-failure").partition, ) .await .unwrap(); assert_eq!(frontier.boundary().0, Location::new(0)); let raw = ContiguousJournal::<_, TestOp>::init( context.child("raw"), journal_config("prune-failure"), ) .await .unwrap(); assert_eq!(raw.bounds().start, 0); }); } /// A frontier written ahead of its operations' deletion opens at that boundary and finishes the /// deletion, and a frontier outside the retained operations is corrupt. async fn frontier_before_deletion(context: Context) { // Establish durable operations and the pins needed to prune partway through a blob. let mut journal = create_journal_with_ops::(context.child("initial"), "ahead", 100).await; let root = journal.root(0).unwrap(); let boundary = Location::new(45); let pins = journal.pinned_nodes_at(boundary).await.unwrap(); // Persist the frontier while leaving all operation blobs in place. journal.frontier = journal.frontier.set(boundary, pins).await.unwrap(); drop(journal); // Use the same stored state for capped selection and complete recovery. let prepare = |label: &'static str, max_size| { TestJournal::::prepare( context.child(label), merkle_config("ahead"), journal_config("ahead"), max_size, |_| true, ForwardFold, ) }; let open = |label: &'static str| { TestJournal::::new( context.child(label), merkle_config("ahead"), journal_config("ahead"), |_| true, ForwardFold, ) }; // A capped selection needs a retained item at or above the frontier. assert!(matches!( prepare("below", Some(44)).await, Err(Error::Journal(JournalError::ItemPruned(45))) )); assert!(matches!( prepare("at", Some(45)).await, Err(Error::Journal(JournalError::ItemPruned(45))) )); // Recovery keeps the blob padding below the authenticated range. let journal = open("recovered").await.unwrap(); assert_eq!(journal.merkle.bounds().start, boundary); assert_eq!(journal.journal.bounds(), 42..100); assert_eq!(journal.bounds(), 45..100); assert_eq!(journal.root(0).unwrap(), root); let (proof, ops) = journal.proof(boundary, NZU64!(10), 0).await.unwrap(); assert!(verify_proof(&proof, &journal.hasher, boundary, &ops, &root)); // A same-blob prune preserves the frontier, while crossing a blob advances it. let (journal, start) = journal.prune(Location::new(46)).await.unwrap(); assert_eq!((start, journal.merkle.bounds().start), (boundary, boundary)); let (journal, start) = journal.prune(Location::new(60)).await.unwrap(); assert_eq!(start, Location::new(56)); assert_eq!(journal.root(0).unwrap(), root); drop(journal); // The later pruning boundary and root survive another reopen. let mut journal = open("again").await.unwrap(); assert_eq!(journal.bounds(), 56..100); assert_eq!(journal.root(0).unwrap(), root); // A frontier below the retained operations cannot be rebuilt. journal.frontier = journal .frontier .set(Location::new(0), Vec::new()) .await .unwrap(); drop(journal); assert!(matches!( open("corrupt").await, Err(Error::Merkle(merkle::Error::DataCorrupted(_))) )); // A frontier past the operations is corrupt, whatever the cap. let past = Location::new(110); let pins = F::nodes_to_pin(past).map(|_| Sha256::fill(0)).collect(); let frontier = Frontier::::open(context.child("past"), merkle_config("ahead").partition) .await .unwrap(); drop(frontier.set(past, pins).await.unwrap()); assert!(matches!( prepare("past", Some(120)).await, Err(Error::Merkle(merkle::Error::DataCorrupted(_))) )); } #[test] fn test_frontier_before_deletion_mmr() { deterministic::Runner::default().start(frontier_before_deletion::); } #[test] fn test_frontier_before_deletion_mmb() { deterministic::Runner::default().start(frontier_before_deletion::); } /// Pins at a location whose digests are pruned are [`merkle::Error::ElementPruned`], and pins /// past the end are [`merkle::Error::RangeOutOfBounds`]. async fn pinned_nodes_at_errors(context: Context) { let journal = create_journal_with_ops::(context.child("initial"), "pins", 100).await; let (journal, boundary) = journal.prune(Location::new(45)).await.unwrap(); assert!(*boundary > 1); journal.pinned_nodes_at(boundary).await.unwrap(); assert!(matches!( journal.pinned_nodes_at(Location::new(1)).await, Err(merkle::Error::ElementPruned(_)) )); assert!(matches!( journal.pinned_nodes_at(Location::new(101)).await, Err(merkle::Error::RangeOutOfBounds(_)) )); } #[test] fn test_pinned_nodes_at_errors_mmr() { deterministic::Runner::default().start(pinned_nodes_at_errors::); } #[test] fn test_pinned_nodes_at_errors_mmb() { deterministic::Runner::default().start(pinned_nodes_at_errors::); } /// A frontier beside retained operations whose pins don't match its boundary, or whose boundary /// is not a valid location, fails the open instead of panicking. An invalid location fails to /// decode. #[test] fn test_malformed_frontier_fails_open() { deterministic::Runner::default().start(|context| async move { type F = mmr::Family; let records = [ (Location::new(8), Vec::new()), (Location::new(8), vec![Sha256::fill(1); 2]), (Location::new(u64::MAX), Vec::new()), ]; for (index, (boundary, pins)) in records.into_iter().enumerate() { let suffix = format!("malformed-frontier-{index}"); let journal = create_journal_with_ops::(context.child("ops"), &suffix, 10); drop(journal.await); let frontier = Frontier::::open( context.child("write"), merkle_config(&suffix).partition, ) .await .unwrap(); drop(frontier.set(boundary, pins).await.unwrap()); let result = TestJournal::::new( context.child("open"), merkle_config(&suffix), journal_config(&suffix), |_| true, ForwardFold, ) .await; assert!(matches!( result, Err(Error::Merkle(merkle::Error::InvalidPinnedNodes)) | Err(Error::Journal(JournalError::Metadata( crate::metadata::Error::Corruption(_) ))) )); } }); } /// A read that fails while the replay's subtree tasks hold the journal returns only once they /// have released it, so the journal reopens at once. #[test_traced] fn test_finish_with_failed_read_releases_journal() { // An authenticated journal over a context whose reads can be parked. type Gated = ReadGateContext; type GatedJournal = Journal< mmr::Family, Gated, ContiguousJournal>, Sha256, Sequential, >; // The executor's poll order decides whether an aborted subtree task still holds the journal // once `finish_with` resumes, so cover several seeds. for seed in 0..8u64 { deterministic::Runner::seeded(seed).start(|context| async move { // Write the operations the recovery replays. let (merkle_cfg, journal_cfg) = (merkle_config("failed-read"), journal_config("failed-read")); let initial = context.child("initial"); drop(create_journal_with_ops::(initial, "failed-read", 200).await); // Open the recovery over storage whose reads of the operations can be parked. let (gated, gate) = ReadGateContext::new( context.child("failed"), format!("{}-blobs", journal_cfg.partition), ); let recovery = GatedJournal::prepare( gated, merkle_cfg.clone(), journal_cfg.clone(), None, |_| true, ForwardFold, ) .await .unwrap(); // Fail once every subtree task is parked in a read, holding the journal. let tasks = NZUsize!(2); let subtrees = tasks.get(); let observer = context.child("observer"); let result: Result<(_, ()), Error> = recovery .finish_with(tasks, |journal| async move { drop(journal); gate.arm(); let parked: Vec<_> = (0..subtrees).map(|_| gate.parked()).collect(); for parked in parked { parked.await.unwrap(); } assert_eq!( task_metrics::tasks(&observer.encode(), RUNNING, "replay_chunk"), subtrees as u64, "the replay must run exactly {subtrees} tasks at once" ); Err(Error::Merkle(merkle::Error::DataCorrupted("read"))) }) .await; assert!(matches!( result, Err(Error::Merkle(merkle::Error::DataCorrupted(_))) )); // The journal reopens at once, so no subtree task still holds it. TestJournal::::new( context.child("reopened"), merkle_cfg, journal_cfg, |_| true, ForwardFold, ) .await .unwrap(); }); } } /// A journal built from synced operations records the synced boundary, and reopens there with /// the same root. async fn from_components_records_boundary(context: Context) { // Cover empty history, the full range, a retained suffix, and a fully pruned journal. for (start, count) in [(0, 0), (0, 50), (20, 50), (50, 50)] { // Keep the durable operations and the pins for this import boundary. let suffix = format!("import-{start}-{count}"); let journal = create_journal_with_ops::(context.child("source"), &suffix, count).await; let root = journal.root(0).unwrap(); let start = Location::new(start); let pins = journal.pinned_nodes_at(start).await.unwrap(); let Journal { journal: ops, frontier, hasher, .. } = journal; drop(frontier); // Importing the components keeps the root and writes nothing until the boundary is // persisted. let journal = TestJournal::::from_components( context.child("import"), &merkle_config(&suffix), ops, hasher, start, pins.clone(), NZU64!(7), ) .await .unwrap(); assert_eq!(journal.root(0).unwrap(), root); assert_eq!(journal.frontier.boundary(), Default::default()); let journal = journal.persist_boundary().await.unwrap(); assert_eq!(journal.frontier.boundary(), (start, pins)); drop(journal); // Recovery must rebuild the same root from the persisted boundary. let journal = TestJournal::::new( context.child("reopen"), merkle_config(&suffix), journal_config(&suffix), |_| true, ForwardFold, ) .await .unwrap(); assert_eq!(journal.merkle.bounds().start, start); assert_eq!(journal.root(0).unwrap(), root); } } #[test] fn test_from_components_records_boundary_mmr() { // Imported boundaries and roots must survive recovery across the valid range. deterministic::Runner::default().start(from_components_records_boundary::); } #[test] fn test_from_components_records_boundary_mmb() { // Imported boundaries and roots must survive recovery across the valid range. deterministic::Runner::default().start(from_components_records_boundary::); } /// A journal built from synced operations prunes nothing until its boundary is persisted, so a /// sync whose root is not yet verified never moves the frontier or deletes operations. async fn import_prunes_nothing_before_persist(context: Context) { let suffix = "import-prune"; let journal = create_journal_with_ops::(context.child("source"), suffix, 50).await; let start = Location::new(20); let pins = journal.pinned_nodes_at(start).await.unwrap(); let Journal { journal: ops, frontier, hasher, .. } = journal; drop(frontier); let journal = TestJournal::::from_components( context.child("import"), &merkle_config(suffix), ops, hasher, start, pins.clone(), NZU64!(7), ) .await .unwrap(); let retained = journal.journal.bounds(); assert_eq!(journal.prune_target(40), 20); let (journal, pruned) = journal.prune(Location::new(40)).await.unwrap(); assert_eq!(pruned, Location::new(20)); assert_eq!(journal.frontier.boundary(), Default::default()); assert_eq!(journal.journal.bounds(), retained); let journal = journal.persist_boundary().await.unwrap(); assert_eq!(journal.frontier.boundary(), (start, pins)); // The boundary sits mid-blob, so a prune before it leaves the start there. assert_eq!(journal.prune_target(15), 20); assert_eq!(journal.prune_target(40), 35); let (journal, pruned) = journal.prune(Location::new(40)).await.unwrap(); assert_eq!(pruned, Location::new(35)); assert_eq!(journal.frontier.boundary().0, Location::new(35)); journal.destroy().await.unwrap(); } #[test] fn test_import_prunes_nothing_before_persist_mmr() { deterministic::Runner::default().start(import_prunes_nothing_before_persist::); } #[test] fn test_import_prunes_nothing_before_persist_mmb() { deterministic::Runner::default().start(import_prunes_nothing_before_persist::); } /// An import outside the durable operation range leaves the existing frontier recoverable. async fn from_components_rejects_outside_bounds( context: Context, below: bool, ) { // Supply valid pins so rejection depends on operation availability. let start = Location::new(if below { 15 } else { 21 }); let source = create_journal_with_ops::(context.child("pins"), "pins", 21).await; let pins = source.pinned_nodes_at(start).await.unwrap(); drop(source); // The import falls below a pruned prefix or above the durable end. let config = merkle_config("invalid-components"); let mut raw_config = journal_config("invalid-components"); raw_config.items_per_blob = if below { NZU64!(8) } else { NZU64!(32) }; let mut journal = TestJournal::::new( context.child("initial"), config.clone(), raw_config.clone(), |_| true, ForwardFold, ) .await .unwrap(); for i in 0..20 { (journal, _) = journal.append(&create_operation::(i)).await.unwrap(); } journal = journal.sync().await.unwrap(); // Remove the blob containing the proposed start in the lower-bound case. if below { (journal, _) = journal.prune(Location::new(16)).await.unwrap(); } // Keep the existing state to verify that rejection does not replace its frontier. let root = journal.root(0).unwrap(); let bounds = journal.bounds(); let Journal { journal: ops, frontier, hasher, .. } = journal; drop(frontier); // Reject the import before writing the supplied frontier. assert!(matches!( TestJournal::::from_components( context.child("invalid"), &config, ops, hasher, start, pins, NZU64!(7), ) .await, Err(Error::Merkle(merkle::Error::RangeOutOfBounds(_))) )); // The original operation range and root must remain recoverable. let reopened = TestJournal::::new( context.child("reopen"), config, raw_config, |_| true, ForwardFold, ) .await .unwrap(); assert_eq!(reopened.bounds(), bounds); assert_eq!(reopened.root(0).unwrap(), root); } #[test] fn test_from_components_rejects_below_bounds_mmr() { // An import below the durable range must leave the existing state recoverable. deterministic::Runner::default() .start(|context| from_components_rejects_outside_bounds::(context, true)); } #[test] fn test_from_components_rejects_below_bounds_mmb() { // An import below the durable range must leave the existing state recoverable. deterministic::Runner::default() .start(|context| from_components_rejects_outside_bounds::(context, true)); } #[test] fn test_from_components_rejects_above_bounds_mmr() { // An import above the durable range must leave the existing state recoverable. deterministic::Runner::default() .start(|context| from_components_rejects_outside_bounds::(context, false)); } #[test] fn test_from_components_rejects_above_bounds_mmb() { // An import above the durable range must leave the existing state recoverable. deterministic::Runner::default() .start(|context| from_components_rejects_outside_bounds::(context, false)); } /// A prune that stays within the oldest blob writes no frontier. #[test_traced("INFO")] fn test_same_blob_prune_does_not_write_frontier() { deterministic::Runner::default().start(|context| async move { let (recording, writes) = RecordingContext::new(context); let cfg = merkle_config("commit-frontier"); let raw_cfg = journal_config("commit-frontier"); let mut journal = RecordingTestJournal::::new( recording, cfg, raw_cfg, |_| true, ForwardFold, ) .await .unwrap(); for i in 0..6 { (journal, _) = journal.append(&create_operation(i)).await.unwrap(); } journal = journal.commit().await.unwrap(); writes.clear(); let (journal, start) = journal.prune(Location::new(5)).await.unwrap(); assert_eq!(start, Location::new(0)); assert!( writes.snapshot().writes.is_empty(), "same-blob pruning must not write frontier metadata" ); drop(journal); }); } /// Verify that pruning an empty journal returns the boundary. async fn test_prune_empty_journal_inner(context: Context) { let journal = create_empty_journal::(context, "prune_empty").await; let (_, boundary) = journal.prune(Location::::new(0)).await.unwrap(); assert_eq!(boundary, Location::::new(0)); } #[test_traced("INFO")] fn test_prune_empty_journal_mmr() { let executor = deterministic::Runner::default(); executor.start(test_prune_empty_journal_inner::); } #[test_traced("INFO")] fn test_prune_empty_journal_mmb() { let executor = deterministic::Runner::default(); executor.start(test_prune_empty_journal_inner::); } /// Verify that pruning to a specific location works correctly. async fn test_prune_to_location_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "prune_to", 100).await; // Add commit at position 50 (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let (_, boundary) = journal.prune(Location::::new(50)).await.unwrap(); // Boundary should be <= requested location (may align to section boundary) assert!(boundary <= Location::::new(50)); } #[test_traced("INFO")] fn test_prune_to_location_mmr() { let executor = deterministic::Runner::default(); executor.start(test_prune_to_location_inner::); } #[test_traced("INFO")] fn test_prune_to_location_mmb() { let executor = deterministic::Runner::default(); executor.start(test_prune_to_location_inner::); } /// Verify that prune() returns the actual boundary (which may differ from requested). async fn test_prune_returns_actual_boundary_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "prune_boundary", 100).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let requested = Location::::new(50); let (journal, actual) = journal.prune(requested).await.unwrap(); // Actual boundary should match bounds.start let bounds = journal.bounds(); assert!(!bounds.is_empty()); assert_eq!(actual, bounds.start); // Actual may be <= requested due to section alignment assert!(actual <= requested); } #[test_traced("INFO")] fn test_prune_returns_actual_boundary_mmr() { let executor = deterministic::Runner::default(); executor.start(test_prune_returns_actual_boundary_inner::); } #[test_traced("INFO")] fn test_prune_returns_actual_boundary_mmb() { let executor = deterministic::Runner::default(); executor.start(test_prune_returns_actual_boundary_inner::); } /// Verify that pruning doesn't change the operation count. async fn test_prune_preserves_operation_count_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "prune_count", 100).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let count_before = journal.size(); let (journal, _) = journal.prune(Location::::new(50)).await.unwrap(); let count_after = journal.size(); assert_eq!(count_before, count_after); } #[test_traced("INFO")] fn test_prune_preserves_operation_count_mmr() { let executor = deterministic::Runner::default(); executor.start(test_prune_preserves_operation_count_inner::); } #[test_traced("INFO")] fn test_prune_preserves_operation_count_mmb() { let executor = deterministic::Runner::default(); executor.start(test_prune_preserves_operation_count_inner::); } /// Verify bounds() for empty journal, no pruning, and after pruning. async fn test_bounds_empty_and_pruned_inner(context: Context) { // Test empty journal let journal = create_empty_journal::(context.child("empty"), "oldest").await; assert!(journal.bounds().is_empty()); journal.destroy().await.unwrap(); // Test no pruning let journal = create_journal_with_ops::(context.child("no_prune"), "oldest", 100).await; let bounds = journal.bounds(); assert!(!bounds.is_empty()); assert_eq!(bounds.start, 0); journal.destroy().await.unwrap(); // Test after pruning let mut journal = create_journal_with_ops::(context.child("pruned"), "oldest", 100).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let (journal, pruned_boundary) = journal.prune(Location::::new(50)).await.unwrap(); // Should match the pruned boundary (may be <= 50 due to section alignment) let bounds = journal.bounds(); assert!(!bounds.is_empty()); assert_eq!(bounds.start, pruned_boundary); // Should be <= requested location (50) assert!(pruned_boundary <= 50); journal.destroy().await.unwrap(); } #[test_traced("INFO")] fn test_bounds_empty_and_pruned_mmr() { let executor = deterministic::Runner::default(); executor.start(test_bounds_empty_and_pruned_inner::); } #[test_traced("INFO")] fn test_bounds_empty_and_pruned_mmb() { let executor = deterministic::Runner::default(); executor.start(test_bounds_empty_and_pruned_inner::); } /// Verify bounds().start for empty journal, no pruning, and after pruning. async fn test_bounds_start_after_prune_inner(context: Context) { // Test empty journal let journal = create_empty_journal::(context.child("empty"), "boundary").await; assert_eq!(journal.bounds().start, 0); // Test no pruning drop(journal); let journal = create_journal_with_ops::(context.child("no_prune"), "boundary", 100).await; assert_eq!(journal.bounds().start, 0); // Test after pruning drop(journal); let mut journal = create_journal_with_ops::(context.child("pruned"), "boundary", 100).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(50))) .await .unwrap(); journal = journal.sync().await.unwrap(); let (journal, pruned_boundary) = journal.prune(Location::::new(50)).await.unwrap(); assert_eq!(journal.bounds().start, pruned_boundary); } #[test_traced("INFO")] fn test_bounds_start_after_prune_mmr() { let executor = deterministic::Runner::default(); executor.start(test_bounds_start_after_prune_inner::); } #[test_traced("INFO")] fn test_bounds_start_after_prune_mmb() { let executor = deterministic::Runner::default(); executor.start(test_bounds_start_after_prune_inner::); } /// Verify that Merkle prunes to the journal's actual boundary, not the requested location. async fn test_mmr_prunes_to_journal_boundary_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "mmr_boundary", 50).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(25))) .await .unwrap(); journal = journal.sync().await.unwrap(); let (journal, pruned_boundary) = journal.prune(Location::::new(25)).await.unwrap(); // Verify Merkle and journal remain in sync let bounds = journal.bounds(); assert!(!bounds.is_empty()); assert_eq!(pruned_boundary, bounds.start); // Verify boundary is at or before requested (due to section alignment) assert!(pruned_boundary <= Location::::new(25)); // Verify operation count is unchanged assert_eq!(journal.size(), 51); } #[test_traced("INFO")] fn test_mmr_prunes_to_journal_boundary_mmr() { let executor = deterministic::Runner::default(); executor.start(test_mmr_prunes_to_journal_boundary_inner::); } #[test_traced("INFO")] fn test_mmr_prunes_to_journal_boundary_mmb() { let executor = deterministic::Runner::default(); executor.start(test_mmr_prunes_to_journal_boundary_inner::); } /// Verify proof() for multiple operations. async fn test_proof_multiple_operations_inner(context: Context) { let journal = create_journal_with_ops::(context, "proof_multi", 50).await; let (proof, ops) = journal .proof(Location::::new(0), NZU64!(50), 0) .await .unwrap(); assert_eq!(ops.len(), 50); for (i, op) in ops.iter().enumerate() { assert_eq!(*op, create_operation::(i as u8)); } // Verify the proof is valid let hasher = StandardHasher::new(ForwardFold); let root = journal_root(&journal); assert!(verify_proof( &proof, &hasher, Location::::new(0), &ops, &root )); } #[test_traced("INFO")] fn test_proof_multiple_operations_mmr() { let executor = deterministic::Runner::default(); executor.start(test_proof_multiple_operations_inner::); } #[test_traced("INFO")] fn test_proof_multiple_operations_mmb() { let executor = deterministic::Runner::default(); executor.start(test_proof_multiple_operations_inner::); } /// Verify that historical_proof() respects the max_ops limit. async fn test_historical_proof_limited_by_max_ops_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "proof_limit", 50).await; let size = journal.size(); let (proof, ops) = journal .historical_proof(size, Location::::new(0), NZU64!(20), 0) .await .unwrap(); // Should return only 20 operations despite 50 being available assert_eq!(ops.len(), 20); for (i, op) in ops.iter().enumerate() { assert_eq!(*op, create_operation::(i as u8)); } // Verify the proof is valid let hasher = StandardHasher::new(ForwardFold); let root = journal_root(&journal); assert!(verify_proof( &proof, &hasher, Location::::new(0), &ops, &root )); } #[test_traced("INFO")] fn test_historical_proof_limited_by_max_ops_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_limited_by_max_ops_inner::(context) }); } #[test_traced("INFO")] fn test_historical_proof_limited_by_max_ops_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_limited_by_max_ops_inner::(context) }); } /// Verify historical_proof() at the end of the journal. async fn test_historical_proof_at_end_of_journal_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "proof_end", 50).await; let size = journal.size(); // Request proof starting near the end let (proof, ops) = journal .historical_proof(size, Location::::new(40), NZU64!(20), 0) .await .unwrap(); // Should return only 10 operations (positions 40-49) assert_eq!(ops.len(), 10); for (i, op) in ops.iter().enumerate() { assert_eq!(*op, create_operation::((40 + i) as u8)); } // Verify the proof is valid let hasher = StandardHasher::new(ForwardFold); let root = journal_root(&journal); assert!(verify_proof( &proof, &hasher, Location::::new(40), &ops, &root )); } #[test_traced("INFO")] fn test_historical_proof_at_end_of_journal_mmr() { let executor = deterministic::Runner::default(); executor.start(test_historical_proof_at_end_of_journal_inner::); } #[test_traced("INFO")] fn test_historical_proof_at_end_of_journal_mmb() { let executor = deterministic::Runner::default(); executor.start(test_historical_proof_at_end_of_journal_inner::); } /// Verify that historical_proof() returns an error for invalid size. async fn test_historical_proof_out_of_range_returns_error_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "proof_oob", 5).await; // Request proof with size > actual journal size let result = journal .historical_proof(Location::::new(10), Location::::new(0), NZU64!(1), 0) .await; assert!(matches!( result, Err(Error::Merkle(merkle::Error::RangeOutOfBounds(_))) )); } #[test_traced("INFO")] fn test_historical_proof_out_of_range_returns_error_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_out_of_range_returns_error_inner::(context) }); } #[test_traced("INFO")] fn test_historical_proof_out_of_range_returns_error_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_out_of_range_returns_error_inner::(context) }); } /// Verify that historical_proof() returns an error when start_loc >= size. async fn test_historical_proof_start_too_large_returns_error_inner( context: Context, ) { let journal = create_journal_with_ops::(context, "proof_start_oob", 5).await; let size = journal.size(); // Request proof starting at size (should fail) let result = journal.historical_proof(size, size, NZU64!(1), 0).await; assert!(matches!( result, Err(Error::Merkle(merkle::Error::RangeOutOfBounds(_))) )); } #[test_traced("INFO")] fn test_historical_proof_start_too_large_returns_error_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_start_too_large_returns_error_inner::(context) }); } #[test_traced("INFO")] fn test_historical_proof_start_too_large_returns_error_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_start_too_large_returns_error_inner::(context) }); } /// Verify historical_proof() for a truly historical state (before more operations added). async fn test_historical_proof_truly_historical_inner(context: Context) { // Create journal with initial operations let mut journal = create_journal_with_ops::(context, "proof_historical", 50).await; // Capture root at historical state let hasher = StandardHasher::new(ForwardFold); let historical_root = journal_root(&journal); let historical_size = journal.size(); // Add more operations after the historical state for i in 50..100 { (journal, _) = journal .append(&create_operation::(i as u8)) .await .unwrap(); } let journal = journal.sync().await.unwrap(); // Generate proof for the historical state let (proof, ops) = journal .historical_proof(historical_size, Location::::new(0), NZU64!(50), 0) .await .unwrap(); // Verify operations match expected historical operations assert_eq!(ops.len(), 50); for (i, op) in ops.iter().enumerate() { assert_eq!(*op, create_operation::(i as u8)); } // Verify the proof is valid against the historical root assert!(verify_proof( &proof, &hasher, Location::::new(0), &ops, &historical_root )); } #[test_traced("INFO")] fn test_historical_proof_truly_historical_mmr() { let executor = deterministic::Runner::default(); executor.start(test_historical_proof_truly_historical_inner::); } #[test_traced("INFO")] fn test_historical_proof_truly_historical_mmb() { let executor = deterministic::Runner::default(); executor.start(test_historical_proof_truly_historical_inner::); } /// Verify that historical_proof() returns an error when start_loc is pruned. async fn test_historical_proof_pruned_location_returns_error_inner( context: Context, ) { let mut journal = create_journal_with_ops::(context, "proof_pruned", 50).await; (journal, _) = journal .append(&TestOp::::Commit(None, Location::::new(25))) .await .unwrap(); journal = journal.sync().await.unwrap(); let pruned_boundary; (journal, pruned_boundary) = journal.prune(Location::::new(25)).await.unwrap(); // Try to get proof starting at a location before the pruned boundary let size = journal.size(); let start_loc = Location::::new(0); if start_loc < pruned_boundary { let result = journal .historical_proof(size, start_loc, NZU64!(1), 0) .await; // Should fail when trying to read pruned operations assert!(result.is_err()); } } #[test_traced("INFO")] fn test_historical_proof_pruned_location_returns_error_mmr() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_pruned_location_returns_error_inner::(context) }); } #[test_traced("INFO")] fn test_historical_proof_pruned_location_returns_error_mmb() { let executor = deterministic::Runner::default(); executor.start(|context| { test_historical_proof_pruned_location_returns_error_inner::(context) }); } /// Verify replay() with empty journal and multiple operations. async fn test_replay_operations_inner(context: Context) { // Test empty journal { let journal = create_empty_journal::(context.child("empty"), "replay").await; let stream = replay_items( &journal, 0..journal.bounds().end, NZUsize!(10), ReadOptions::default(), ) .await .unwrap(); futures::pin_mut!(stream); assert!(stream.next().await.is_none()); } // Test replaying all operations let journal = create_journal_with_ops::(context.child("with_ops"), "replay", 50).await; let stream = replay_items( &journal, 0..journal.bounds().end, NZUsize!(100), ReadOptions::default(), ) .await .unwrap(); futures::pin_mut!(stream); for i in 0..50 { let (pos, op) = stream.next().await.unwrap().unwrap(); assert_eq!(pos, i); assert_eq!(op, create_operation::(i as u8)); } assert!(stream.next().await.is_none()); } #[test_traced("INFO")] fn test_replay_operations_mmr() { let executor = deterministic::Runner::default(); executor.start(test_replay_operations_inner::); } #[test_traced("INFO")] fn test_replay_operations_mmb() { let executor = deterministic::Runner::default(); executor.start(test_replay_operations_inner::); } #[test_traced("INFO")] fn test_replay_propagates_read_options_to_backing_journal() { let executor = deterministic::Runner::default(); executor.start(|context| async move { let (context, recordings) = RecordingContext::new(context); let merkle_cfg = merkle_config("replay-options"); let journal_cfg = journal_config("replay-options"); let page_cache = journal_cfg.page_cache.clone(); let mut journal = RecordingTestJournal::::new( context, merkle_cfg, journal_cfg, |op| op.is_commit(), ForwardFold, ) .await .unwrap(); for i in 0..8 { let operation = create_operation::(i); (journal, _) = journal.append(&operation).await.unwrap(); } journal = journal.sync().await.unwrap(); // Evict cached pages so the first replay item requires a backing read through the // authenticated wrapper. page_cache.clear(); let stream = replay_items( &journal, 0..journal.bounds().end, NZUsize!(100), ReadOptions::DONT_CACHE, ) .await .unwrap(); recordings.clear(); futures::pin_mut!(stream); let (position, operation) = stream.next().await.unwrap().unwrap(); assert_eq!(position, 0); assert_eq!(operation, create_operation::(0)); // The authenticated wrapper forwards DONT_CACHE unchanged to the backing journal. let reads = recordings.snapshot().reads; assert!(!reads.is_empty()); assert!( reads .iter() .all(|options| *options == ReadOptions::DONT_CACHE) ); }); } /// Verify replay() starting from a middle location. async fn test_replay_from_middle_inner(context: Context) { let journal = create_journal_with_ops::(context, "replay_middle", 50).await; let stream = replay_items( &journal, 25..journal.bounds().end, NZUsize!(100), ReadOptions::default(), ) .await .unwrap(); futures::pin_mut!(stream); let mut count = 0; while let Some(result) = stream.next().await { let (pos, op) = result.unwrap(); assert_eq!(pos, 25 + count); assert_eq!(op, create_operation::((25 + count) as u8)); count += 1; } // Should have replayed positions 25-49 (25 operations) assert_eq!(count, 25); } #[test_traced("INFO")] fn test_replay_from_middle_mmr() { let executor = deterministic::Runner::default(); executor.start(test_replay_from_middle_inner::); } #[test_traced("INFO")] fn test_replay_from_middle_mmb() { let executor = deterministic::Runner::default(); executor.start(test_replay_from_middle_inner::); } /// Verify the speculative batch API: fork two batches, verify independent roots, apply one. async fn test_speculative_batch_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "speculative_batch", 10).await; let original_root = journal_root(&journal); // Fork two independent speculative batches. let b1 = journal.new_batch(); let b2 = journal.new_batch(); // Add different items to each batch. let op_a = create_operation::(100); let op_b = create_operation::(200); let b1 = b1.add(op_a.clone()); let b2 = b2.add(op_b); // Merkleize and verify independent roots. let m1 = b1.merkleize(journal.merkle.mem()); let m2 = b2.merkleize(journal.merkle.mem()); assert_ne!(batch_root(&journal, &m1), batch_root(&journal, &m2)); assert_ne!(batch_root(&journal, &m1), original_root); assert_ne!(batch_root(&journal, &m2), original_root); // Journal root should be unchanged (batches are speculative). assert_eq!(journal_root(&journal), original_root); // Apply batch 1. let expected_root = batch_root(&journal, &m1); journal = journal.apply_batch(&m1).await.unwrap(); // Journal should now match the applied batch's root. assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 11); } #[test_traced("INFO")] fn test_speculative_batch_mmr() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_inner::); } #[test_traced("INFO")] fn test_speculative_batch_mmb() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_inner::); } /// Verify stacking: create batch A, merkleize, create batch B from merkleized A, /// merkleize, and apply. Verify root and items. async fn test_speculative_batch_stacking_inner(context: Context) { // Seed the journal with history shared by both batches. let mut journal = create_journal_with_ops::(context, "batch_stacking", 10).await; let op_a = create_operation::(100); let op_b = create_operation::(200); // Build a child batch whose root includes its parent operation. let (merkleized_a, merkleized_b) = { let batch_a = journal.new_batch().add(op_a.clone()); let merkleized_a = batch_a.merkleize(journal.merkle.mem()); let batch_b = merkleized_a.new_batch::().add(op_b.clone()); let merkleized_b = batch_b.merkleize(journal.merkle.mem()); (merkleized_a, merkleized_b) }; // Applying the child must leave its parent proof valid at the parent root. let expected_root = batch_root(&journal, &merkleized_b); journal = journal.apply_batch(&merkleized_b).await.unwrap(); let proof = journal.speculative_proof(&merkleized_a, 0).unwrap(); assert!(verify_proof( &proof, &journal.hasher, Location::new(10), core::slice::from_ref(&op_a), &batch_root(&journal, &merkleized_a), )); drop(merkleized_a); // The child retains its proof and pins after the separate parent handle is dropped. let proof = journal.speculative_proof(&merkleized_b, 0).unwrap(); assert!(verify_proof( &proof, &journal.hasher, Location::new(11), core::slice::from_ref(&op_b), &expected_root, )); assert_eq!( journal.speculative_pinned_nodes(&merkleized_b).unwrap(), journal.pinned_nodes_at(Location::new(11)).await.unwrap(), ); // The applied chain must publish both operations under the child root. assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 12); // Verify both items were appended correctly. let read_a = journal.read(*Location::::new(10)).await.unwrap(); assert_eq!(read_a, op_a); let read_b = journal.read(*Location::::new(11)).await.unwrap(); assert_eq!(read_b, op_b); } #[test_traced("INFO")] fn test_speculative_batch_stacking_mmr() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_stacking_inner::); } #[test_traced("INFO")] fn test_speculative_batch_stacking_mmb() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_stacking_inner::); } /// Verify sequential batch application: apply batch A, then build and apply batch B /// from the committed state. Verify root and items. async fn test_speculative_batch_sequential_inner(context: Context) { // Seed the common history for two successive batch applications. let mut journal = create_journal_with_ops::(context, "batch_sequential", 10).await; let op_a = create_operation::(100); let op_b = create_operation::(200); // Publish the first batch before constructing the next one. let batch_a = journal.new_batch().add(op_a.clone()); let merkleized_a = batch_a.merkleize(journal.merkle.mem()); journal = journal.apply_batch(&merkleized_a).await.unwrap(); assert_eq!(*journal.size(), 11); // Build the second batch from the journal containing the first batch. let batch_b = journal.new_batch().add(op_b.clone()); let merkleized_b = batch_b.merkleize(journal.merkle.mem()); let expected_root = batch_root(&journal, &merkleized_b); journal = journal.apply_batch(&merkleized_b).await.unwrap(); assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 12); // The first batch proof must still verify at its own root after the second is applied. let proof = journal.speculative_proof(&merkleized_a, 0).unwrap(); assert!(verify_proof( &proof, &journal.hasher, Location::new(10), core::slice::from_ref(&op_a), &batch_root(&journal, &merkleized_a), )); // Verify both items were appended correctly. let read_a = journal.read(*Location::::new(10)).await.unwrap(); assert_eq!(read_a, op_a); let read_b = journal.read(*Location::::new(11)).await.unwrap(); assert_eq!(read_b, op_b); } #[test_traced("INFO")] fn test_speculative_batch_sequential_mmr() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_sequential_inner::); } #[test_traced("INFO")] fn test_speculative_batch_sequential_mmb() { let executor = deterministic::Runner::default(); executor.start(test_speculative_batch_sequential_inner::); } async fn test_stale_batch_sibling_inner(context: Context) { let mut journal = create_empty_journal::(context.child("open"), "stale-sibling").await; let op_a = create_operation::(1); let op_b = create_operation::(2); // Create two batches from the same base. let batch_a = journal.new_batch().add(op_a.clone()); let merkleized_a = batch_a.merkleize(journal.merkle.mem()); let batch_b = journal.new_batch().add(op_b); let merkleized_b = batch_b.merkleize(journal.merkle.mem()); // Apply A, then commit and sync so the recovered state below includes it (reopen // selects the last commit operation during initialization). journal = journal.apply_batch(&merkleized_a).await.unwrap(); let commit_op = TestOp::::Commit(None, Location::::new(0)); (journal, _) = journal.append(&commit_op).await.unwrap(); journal = journal.sync().await.unwrap(); let root_a = journal_root(&journal); let size_a = journal.size(); let (_, ops) = journal .proof(Location::::new(0), NZU64!(1), 0) .await .unwrap(); assert_eq!(ops, vec![op_a.clone()]); // Applying B must fail (stale). let result = journal.apply_batch(&merkleized_b).await; assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::StaleBatch { .. })) ), "expected StaleBatch, got {result:?}" ); // The eager reject mutated nothing: reopening recovers exactly A's state. let journal = create_empty_journal::(context.child("reopen"), "stale-sibling").await; assert_eq!(journal_root(&journal), root_a); assert_eq!(journal.size(), size_a); let (_, ops) = journal .proof(Location::::new(0), NZU64!(1), 0) .await .unwrap(); assert_eq!(ops, vec![op_a]); journal.destroy().await.unwrap(); } #[test_traced("INFO")] fn test_stale_batch_sibling_mmr() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_sibling_inner::); } #[test_traced("INFO")] fn test_stale_batch_sibling_mmb() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_sibling_inner::); } async fn test_stale_batch_chained_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "stale-chained", 5).await; // Parent batch, then fork two children. let parent_batch = journal.new_batch().add(create_operation::(10)); let parent = parent_batch.merkleize(journal.merkle.mem()); let batch_a = parent.new_batch::().add(create_operation::(20)); let child_a = batch_a.merkleize(journal.merkle.mem()); let batch_b = parent.new_batch::().add(create_operation::(30)); let child_b = batch_b.merkleize(journal.merkle.mem()); // Apply child_a, then child_b should be stale. journal = journal.apply_batch(&child_a).await.unwrap(); let result = journal.apply_batch(&child_b).await; drop(parent); assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::StaleBatch { .. })) ), "expected StaleBatch for sibling, got {result:?}" ); } #[test_traced("INFO")] fn test_stale_batch_chained_mmr() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_chained_inner::); } #[test_traced("INFO")] fn test_stale_batch_chained_mmb() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_chained_inner::); } async fn test_stale_batch_parent_before_child_inner(context: Context) { let mut journal = create_empty_journal::(context, "stale-parent-first").await; // Create parent, then child. let parent_batch = journal.new_batch().add(create_operation::(1)); let parent = parent_batch.merkleize(journal.merkle.mem()); let child_batch = parent.new_batch::().add(create_operation::(2)); let child = child_batch.merkleize(journal.merkle.mem()); let expected_root = batch_root(&journal, &child); // Apply parent, then child (sequential commit). journal = journal.apply_batch(&parent).await.unwrap(); journal = journal.apply_batch(&child).await.unwrap(); assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 2); } /// A retained child of one fork must be rejected without writing to storage once a sibling of /// its parent has been applied, and reopening must recover the sibling's state. async fn test_stale_batch_interior_fork_inner(context: Context) { // Record storage writes so the test can show that a rejected batch wrote nothing. let (storage, recordings) = RecordingContext::new(context.child("open")); let merkle_cfg = merkle_config("stale-interior"); let journal_cfg = journal_config("stale-interior"); let mut journal = RecordingTestJournal::::new( storage, merkle_cfg, journal_cfg, |op| op.is_commit(), ForwardFold, ) .await .unwrap(); for i in 0..4 { (journal, _) = journal.append(&create_operation::(i)).await.unwrap(); } let commit_op = TestOp::::Commit(None, Location::::new(0)); // Retain the chain A -> B, then apply a sibling of A with the same length. let batch_a = journal .new_batch() .add(create_operation::(10)) .add(commit_op.clone()); let a = batch_a.merkleize(journal.merkle.mem()); let batch_b = a.new_batch::().add(create_operation::(20)); let b = batch_b.merkleize(journal.merkle.mem()); let op_sibling = create_operation::(30); let batch_sibling = journal.new_batch().add(op_sibling.clone()).add(commit_op); let sibling = batch_sibling.merkleize(journal.merkle.mem()); journal = journal.apply_batch(&sibling).await.unwrap(); journal = journal.sync().await.unwrap(); let root = journal.root(0).unwrap(); let size = journal.size(); recordings.clear(); // The journal's size lies inside B's chain, but the sibling, not A, produced that state. // Applying B must fail before writing anything, so items and root stay in sync. let result = journal.apply_batch(&b).await; assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::StaleBatch { .. })) ), "applying B must fail with StaleBatch, got {result:?}" ); assert!( recordings.snapshot().writes.is_empty(), "a rejected batch must not write to storage" ); // Reopening recovers exactly the sibling's state. let journal = create_empty_journal::(context.child("reopen"), "stale-interior").await; assert_eq!(journal_root(&journal), root); assert_eq!(journal.size(), size); let (_, ops) = journal .proof(Location::::new(4), NZU64!(1), 0) .await .unwrap(); assert_eq!(ops, vec![op_sibling]); journal.destroy().await.unwrap(); } /// Applying an empty child after its parent must succeed and leave the journal unchanged. async fn test_apply_batch_empty_child_after_parent_inner( context: Context, ) { let mut journal = create_journal_with_ops::(context, "empty-child", 4).await; let parent = journal .new_batch() .add(create_operation::(10)) .merkleize(journal.merkle.mem()); let child = parent.new_batch::().merkleize(journal.merkle.mem()); journal = journal.apply_batch(&parent).await.unwrap(); let root = journal_root(&journal); let size = journal.size(); // The journal is already at the empty child's tip, so applying it changes nothing. journal = journal.apply_batch(&child).await.unwrap(); assert_eq!(journal_root(&journal), root); assert_eq!(journal.size(), size); journal.destroy().await.unwrap(); } #[test_traced("INFO")] fn test_apply_batch_empty_child_after_parent_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_empty_child_after_parent_inner::); } #[test_traced("INFO")] fn test_apply_batch_empty_child_after_parent_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_empty_child_after_parent_inner::); } /// A descendant must be rejected with `AncestorDropped` when an ancestor's journal batch was /// dropped before the descendant was merkleized, even though its Merkle batch was retained. async fn test_apply_batch_rejects_dropped_journal_ancestor_inner( context: Context, ) { let mut journal = create_journal_with_ops::(context.child("open"), "dropped-items", 4).await; let commit_op = TestOp::::Commit(None, Location::::new(0)); let seed = journal .new_batch() .add(create_operation::(5)) .add(commit_op.clone()) .merkleize(journal.merkle.mem()); journal = journal.apply_batch(&seed).await.unwrap(); journal = journal.sync().await.unwrap(); let root = journal_root(&journal); let size = journal.size(); // In the chain A -> B -> C, A's Merkle batch outlives its journal batch, so C retains // A's Merkle data but not A's items. let a = journal .new_batch() .add(create_operation::(10)) .merkleize(journal.merkle.mem()); let b = a .new_batch::() .add(create_operation::(20)) .merkleize(journal.merkle.mem()); let a_merkle = Arc::clone(&a.inner); drop(a); let c = b .new_batch::() .add(create_operation::(30)) .add(commit_op) .merkleize(journal.merkle.mem()); // The Merkle structure is at C's fork point, but the journal lacks A's items and must // reject C before appending anything. let result = journal.apply_batch(&c).await; assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::AncestorDropped { .. })) ), "applying C must fail with AncestorDropped, got {result:?}" ); drop(a_merkle); // Reopening recovers the state from before the rejected batch. let journal = create_empty_journal::(context.child("reopen"), "dropped-items").await; assert_eq!(journal_root(&journal), root); assert_eq!(journal.size(), size); journal.destroy().await.unwrap(); } #[test_traced("INFO")] fn test_apply_batch_rejects_dropped_journal_ancestor_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_rejects_dropped_journal_ancestor_inner::); } #[test_traced("INFO")] fn test_apply_batch_rejects_dropped_journal_ancestor_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_rejects_dropped_journal_ancestor_inner::); } #[test_traced("INFO")] fn test_stale_batch_interior_fork_mmr() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_interior_fork_inner::); } #[test_traced("INFO")] fn test_stale_batch_interior_fork_mmb() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_interior_fork_inner::); } #[test_traced("INFO")] fn test_stale_batch_parent_before_child_mmr() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_parent_before_child_inner::); } #[test_traced("INFO")] fn test_stale_batch_parent_before_child_mmb() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_parent_before_child_inner::); } async fn test_stale_batch_child_before_parent_inner(context: Context) { let mut journal = create_empty_journal::(context, "stale-child-first").await; // Create parent, then child. let parent_batch = journal.new_batch().add(create_operation::(1)); let parent = parent_batch.merkleize(journal.merkle.mem()); let child_batch = parent.new_batch::().add(create_operation::(2)); let child = child_batch.merkleize(journal.merkle.mem()); // Applying the child first (full chain) makes the parent stale. journal = journal.apply_batch(&child).await.unwrap(); let result = journal.apply_batch(&parent).await; assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::StaleBatch { .. })) ), "expected StaleBatch for parent after child applied, got {result:?}" ); } #[test_traced("INFO")] fn test_stale_batch_child_before_parent_mmr() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_child_before_parent_inner::); } #[test_traced("INFO")] fn test_stale_batch_child_before_parent_mmb() { let executor = deterministic::Runner::default(); executor.start(test_stale_batch_child_before_parent_inner::); } /// Apply parent then child: child skips already-committed ancestor items. async fn test_apply_batch_skip_ancestor_items_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "rp-skip", 3).await; // Parent: 2 items. let parent_batch = journal .new_batch() .add(create_operation::(10)) .add(create_operation::(11)); let parent = parent_batch.merkleize(journal.merkle.mem()); // Child: 3 more items. let child_batch = parent .new_batch::() .add(create_operation::(20)) .add(create_operation::(21)) .add(create_operation::(22)); let child = child_batch.merkleize(journal.merkle.mem()); // Apply parent. journal = journal.apply_batch(&parent).await.unwrap(); // Apply child (ancestor items already committed, skipped automatically). journal = journal.apply_batch(&child).await.unwrap(); // Verify all items are present. let (_, ops) = journal .proof(Location::::new(3), NZU64!(5), 0) .await .unwrap(); assert_eq!(ops.len(), 5); } #[test_traced("INFO")] fn test_apply_batch_skip_ancestor_items_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_skip_ancestor_items_inner::); } #[test_traced("INFO")] fn test_apply_batch_skip_ancestor_items_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_skip_ancestor_items_inner::); } /// `apply_batch` works correctly across a 3-level chain. async fn test_apply_batch_cross_batch_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "rp-cross", 2).await; // Grandparent: 3 items. let grandparent_batch = journal .new_batch() .add(create_operation::(3)) .add(create_operation::(4)) .add(create_operation::(5)); let grandparent = grandparent_batch.merkleize(journal.merkle.mem()); // Parent: 2 items. let parent_batch = grandparent .new_batch::() .add(create_operation::(6)) .add(create_operation::(7)); let parent = parent_batch.merkleize(journal.merkle.mem()); // Child: 1 item. let child_batch = parent.new_batch::().add(create_operation::(8)); let child = child_batch.merkleize(journal.merkle.mem()); // Apply grandparent, then parent, then child sequentially. journal = journal.apply_batch(&grandparent).await.unwrap(); // Apply parent (ancestor items already committed, skipped automatically). journal = journal.apply_batch(&parent).await.unwrap(); // Apply child (ancestor items already committed, skipped automatically). journal = journal.apply_batch(&child).await.unwrap(); // All 8 items (2 base + 3 + 2 + 1) should be present. assert_eq!(*journal.size(), 8); // Verify the actual items at each location. let (_, ops) = journal .proof(Location::::new(2), NZU64!(6), 0) .await .unwrap(); for (i, op) in ops.iter().enumerate() { assert_eq!(*op, create_operation::((i + 3) as u8)); } } #[test_traced("INFO")] fn test_apply_batch_cross_batch_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_cross_batch_inner::); } #[test_traced("INFO")] fn test_apply_batch_cross_batch_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_cross_batch_inner::); } /// merkleize_with produces the same root as add + merkleize. async fn test_merkleize_with_matches_add_inner(context: Context) { let journal = create_journal_with_ops::(context, "mw-matches", 5).await; let ops = vec![ create_operation::(10), create_operation::(11), create_operation::(12), ]; // add + merkleize let mut batch = journal.new_batch(); for op in &ops { batch = batch.add(op.clone()); } let expected = batch.merkleize(journal.merkle.mem()); // merkleize_with let batch = journal.new_batch(); let actual = merkleize_with(batch, journal.merkle.mem(), ops); assert_eq!( batch_root(&journal, &actual), batch_root(&journal, &expected) ); } #[test_traced("INFO")] fn test_merkleize_with_matches_add_mmr() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_with_matches_add_inner::); } #[test_traced("INFO")] fn test_merkleize_with_matches_add_mmb() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_with_matches_add_inner::); } /// merkleize_with items are readable after apply. async fn test_merkleize_with_apply_inner(context: Context) { let mut journal = create_journal_with_ops::(context, "mw-apply", 5).await; let ops = vec![create_operation::(10), create_operation::(11)]; let batch = journal.new_batch(); let merkleized = merkleize_with(batch, journal.merkle.mem(), ops.clone()); let expected_root = batch_root(&journal, &merkleized); journal = journal.apply_batch(&merkleized).await.unwrap(); assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 7); assert_eq!(journal.read(5).await.unwrap(), ops[0]); assert_eq!(journal.read(6).await.unwrap(), ops[1]); } #[test_traced("INFO")] fn test_merkleize_with_apply_mmr() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_with_apply_inner::); } #[test_traced("INFO")] fn test_merkleize_with_apply_mmb() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_with_apply_inner::); } /// Apply C (grandchild of A) after only A is committed. B's journal items /// must still be applied, so skip only A's items. async fn test_apply_batch_skips_only_committed_ancestor_items_inner( context: Context, ) { let mut journal = create_empty_journal::(context.child("storage"), "skip-partial").await; // Build chain: A -> B -> C let a_batch = journal.new_batch().add(create_operation::(1)); let a = a_batch.merkleize(journal.merkle.mem()); let b_batch = a.new_batch::().add(create_operation::(2)); let b = b_batch.merkleize(journal.merkle.mem()); let c_batch = b.new_batch::().add(create_operation::(3)); let c = c_batch.merkleize(journal.merkle.mem()); // Apply A, then apply C directly (skipping B's apply_batch). journal = journal.apply_batch(&a).await.unwrap(); journal = journal.apply_batch(&c).await.unwrap(); // All 3 items should be in the journal. assert_eq!(*journal.size(), 3); // Build a reference that applies all three sequentially. let mut reference = create_empty_journal::(context.child("ref"), "skip-partial-ref").await; for i in 1..=3u8 { (reference, _) = reference.append(&create_operation::(i)).await.unwrap(); } assert_eq!(journal_root(&journal), journal_root(&reference)); } #[test_traced("INFO")] fn test_apply_batch_skips_only_committed_ancestor_items_mmr() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_skips_only_committed_ancestor_items_inner::); } #[test_traced("INFO")] fn test_apply_batch_skips_only_committed_ancestor_items_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_skips_only_committed_ancestor_items_inner::); } /// A descendant whose uncommitted ancestor was dropped must fail before /// appending any of its retained journal items. async fn test_apply_batch_detects_dropped_uncommitted_ancestor_inner( context: Context, ) { let journal = create_empty_journal::(context.child("storage"), "dropped-uncommitted").await; let a_batch = journal.new_batch().add(create_operation::(1)); let a = a_batch.merkleize(journal.merkle.mem()); let b_batch = a.new_batch::().add(create_operation::(2)); let b = b_batch.merkleize(journal.merkle.mem()); drop(a); let c_batch = b.new_batch::().add(create_operation::(3)); let c = c_batch.merkleize(journal.merkle.mem()); drop(b); assert_eq!(c.ancestor_items.len(), 1); let result = journal.apply_batch(&c).await; assert!( matches!( result, Err(super::Error::Merkle(merkle::Error::AncestorDropped { expected, .. })) if expected == c.inner.size() ), "expected AncestorDropped, got {result:?}" ); } #[test_traced("INFO")] fn test_apply_batch_detects_dropped_uncommitted_ancestor_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_detects_dropped_uncommitted_ancestor_inner::); } /// A dropped committed prefix must not shift the remaining uncommitted /// ancestor items back to the original fork point. async fn test_apply_batch_after_committed_ancestor_dropped_inner( context: Context, ) { let mut journal = create_empty_journal::(context.child("storage"), "dropped-committed").await; let mut a_batch = journal.new_batch(); for i in 0..8u8 { a_batch = a_batch.add(create_operation::(i)); } let a = a_batch.merkleize(journal.merkle.mem()); let b_batch = a.new_batch::().add(create_operation::(8)); let b = b_batch.merkleize(journal.merkle.mem()); journal = journal.apply_batch(&a).await.unwrap(); drop(a); let c_batch = b.new_batch::().add(create_operation::(9)); let c = c_batch.merkleize(journal.merkle.mem()); // Only B remains in the retained ancestor suffix. assert_eq!(c.ancestor_items.len(), 1); assert_eq!(journal.merkle.mem().validate_batch(&c.inner).unwrap(), 0); drop(b); journal = journal.apply_batch(&c).await.unwrap(); assert_eq!(*journal.size(), 10); let mut reference = create_empty_journal::(context.child("reference"), "dropped-committed-ref").await; for i in 0..10u8 { (reference, _) = reference.append(&create_operation::(i)).await.unwrap(); } assert_eq!(journal_root(&journal), journal_root(&reference)); } #[test_traced("INFO")] fn test_apply_batch_after_committed_ancestor_dropped_mmb() { let executor = deterministic::Runner::default(); executor.start(test_apply_batch_after_committed_ancestor_dropped_inner::); } /// Merkleization retains a speculative suffix after its committed prefix is released. async fn test_merkleize_after_committed_prefix_dropped_inner( context: Context, ) { let mut journal = create_empty_journal::(context.child("storage"), "committed-prefix").await; // Build a speculative suffix over a prefix that will be committed independently. let prefix_items = (0..8u8).map(create_operation::).collect(); let (prefix, _) = journal .merkleize(journal.new_batch(), prefix_items, 0) .await .unwrap(); let pending_items = (8..10u8).map(create_operation::).collect(); let (pending, _) = journal .merkleize(prefix.new_batch::(), pending_items, 0) .await .unwrap(); // Commit and release the prefix. Its Merkle nodes now resolve through the snapshot. journal = journal.apply_batch(&prefix).await.unwrap(); drop(prefix); // The child batch is the pending suffix's only remaining owner. Merkleization must retain // that suffix through root computation. let child_batch = pending.new_batch::(); drop(pending); let (child, expected_root) = journal .merkleize(child_batch, vec![create_operation::(10)], 0) .await .unwrap(); journal = journal.apply_batch(&child).await.unwrap(); assert_eq!(journal_root(&journal), expected_root); assert_eq!(*journal.size(), 11); } #[test_traced("INFO")] fn test_merkleize_after_committed_prefix_dropped_mmr() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_after_committed_prefix_dropped_inner::); } #[test_traced("INFO")] fn test_merkleize_after_committed_prefix_dropped_mmb() { let executor = deterministic::Runner::default(); executor.start(test_merkleize_after_committed_prefix_dropped_inner::); } /// A detached merkleization job owns the full ancestor chain after its waiter is dropped. #[test_traced("INFO")] fn test_merkleize_retains_ancestors_after_cancellation() { deterministic::Runner::default().start(|context| async move { let pool = Rayon::new(ThreadPoolBuilder::new(NZUsize!(2))).unwrap(); let strategy = Explorer::parallel(&pool); let merkle_cfg = merkle_config_with("cancelled-merkleize", strategy); let journal_cfg = journal_config("cancelled-merkleize"); type ParallelJournal = Journal< mmr::Family, Context, ContiguousJournal>>, Sha256, Explorer, >; let journal = ParallelJournal::new( context, merkle_cfg, journal_cfg, |_: &DropMonitor>| false, ForwardFold, ) .await .unwrap(); let a_items = (0..8u8) .map(create_operation::) .map(DropMonitor::untracked) .collect(); let a_batch = journal.new_batch().add_many(a_items); let a = a_batch.merkleize(journal.merkle.mem()); let b_items = (8..10u8) .map(create_operation::) .map(DropMonitor::untracked) .collect(); let b_batch = a.new_batch::().add_many(b_items); let b = b_batch.merkleize(journal.merkle.mem()); let ancestor = Arc::downgrade(&a.inner); let c_batch = b.new_batch::(); drop(b); let release = block_strategy(&pool, 2); let (item, clean_drop) = DropMonitor::tracked(create_operation::(10)); let mut merkleize = Box::pin(journal.merkleize(c_batch, vec![item], 0)); assert!(futures::poll!(merkleize.as_mut()).is_pending()); drop(merkleize); drop(a); assert!(ancestor.upgrade().is_some()); drop(release); assert!( clean_drop .recv_timeout(Duration::from_secs(10)) .expect("detached merkleization did not finish"), "detached merkleization panicked" ); assert!(ancestor.upgrade().is_none()); }); } /// A fully pruned authenticated journal preserves its append position and root across reopen. async fn fully_pruned_authenticated_reopens(context: Context) { // Fill exactly one operation blob, then prune the complete durable prefix. let merkle_cfg = merkle_config("fully-pruned-reopen"); let journal_cfg = journal_config("fully-pruned-reopen"); assert_eq!(journal_cfg.items_per_blob.get(), 7); let mut journal = TestJournal::::new( context.child("seed"), merkle_cfg.clone(), journal_cfg.clone(), |_| true, ForwardFold, ) .await .unwrap(); for i in 0u8..7 { let (next, pos) = journal.append(&create_operation::(i)).await.unwrap(); journal = next; assert_eq!(*pos, u64::from(i)); } let journal = journal.sync().await.unwrap(); let root = journal.root(0).unwrap(); let (journal, boundary) = journal.prune(Location::new(7)).await.unwrap(); assert_eq!(*boundary, 7); assert_eq!(journal.bounds(), 7..7); assert_eq!(journal.root(0).unwrap(), root); drop(journal); // Reopen at the retained boundary and append at that position. let journal = TestJournal::::new( context.child("reopen"), merkle_cfg, journal_cfg, |_| true, ForwardFold, ) .await .unwrap(); assert_eq!(journal.bounds(), 7..7); assert_eq!(journal.root(0).unwrap(), root); let (journal, pos) = journal.append(&create_operation::(7)).await.unwrap(); assert_eq!(*pos, 7); assert_eq!(journal.bounds(), 7..8); journal.destroy().await.unwrap(); } #[test] fn test_fully_pruned_authenticated_reopens_mmr() { deterministic::Runner::default().start(fully_pruned_authenticated_reopens::); } #[test] fn test_fully_pruned_authenticated_reopens_mmb() { deterministic::Runner::default().start(fully_pruned_authenticated_reopens::); } /// Regression test for https://github.com/commonwarexyz/monorepo/issues/5668. /// /// A destroy dropped while the operation journal's clear is still being staged has removed /// nothing, so the pruned journal reopens at its last commit. #[test_traced("INFO")] fn issue_5668_regression_destroy_stages_journal_clear_before_removal() { let executor = deterministic::Runner::default(); executor.start(|context| async move { // Commit and prune, so the retained operations depend on the frontier's pins. let pending = PendingSyncs::default(); let setup = async { let mut journal = open_delayed_journal(&context, "first", "destroy_staged", &pending) .await .unwrap(); for i in 0..30 { (journal, _) = journal .append(&create_operation::(i)) .await .unwrap(); } (journal, _) = journal .append(&TestOp::::Commit(None, Location::new(0))) .await .unwrap(); journal = journal.sync().await.unwrap(); (journal, _) = journal.prune(Location::new(20)).await.unwrap(); journal.sync().await.unwrap() }; let journal = drive_pending_syncs(&pending, setup).await; let bounds = journal.bounds(); let root = journal.root(0).unwrap(); assert!(bounds.start > 0); // Park the first durability operation of destroy and drop the destroy there. pending.arm(); { let destroy = journal.destroy(); futures::pin_mut!(destroy); assert!(futures::poll!(destroy.as_mut()).is_pending()); } // The unfinished clear is not durable, so the last commit must reopen. let journal = TestJournal::::new( context.child("second"), merkle_config("destroy_staged"), journal_config("destroy_staged"), |op: &TestOp| op.is_commit(), ForwardFold, ) .await .expect("a destroy that staged nothing must reopen"); assert_eq!(journal.bounds(), bounds); assert_eq!(journal.root(0).unwrap(), root); journal.destroy().await.unwrap(); }); } /// Create variable journal configuration for tests. fn variable_journal_config(suffix: &str) -> VConfig<()> { VConfig { partition: format!("journal-{suffix}"), items_per_section: NZU64!(7), compression: None, codec_config: (), page_cache: CacheRef::new(PAGE_SIZE, PAGE_CACHE_SIZE), write_buffer: NZUsize!(1024), replay_buffer: NZUsize!(1024), } } /// Where an interrupted destroy stopped, in the order destroy reaches each outcome. #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] enum Interrupted { /// Destroy stopped before the operation journal's clear was staged, and the journal /// reopens at its last commit. Unchanged, /// Destroy stopped while removing the operation journal, and the journal reopens empty. InJournal, /// Destroy stopped after removing the operation journal, while removing the frontier, /// and the journal reopens empty. InFrontier, /// Destroy completed. Completed, } /// The context a journal under an interrupted destroy runs on. It can stop the destroy /// before any mutation. type FaultedContext = MutationFaultContext; /// Returns whether `partition` exists in `context`'s storage. async fn partition_exists(context: &FaultedContext, partition: &str) -> bool { match context.scan(partition).await { Ok(_) => true, Err(RuntimeError::PartitionMissing(_)) => false, Err(err) => panic!("scan of {partition} must succeed: {err}"), } } /// Stop the destroy of a twice-committed, pruned journal before its first mutation, then its /// second, and so on until one destroy completes. Reopen the journal after each and require /// that destroy stopped at each of its outcomes, in order. /// /// `journal_partitions` names every partition of the operation journal configured by /// `journal_cfg`. Destroy removes them before the frontier. fn interrupted_destroy_reopens(journal_cfg: C::Config, journal_partitions: &[String]) where F: Family + PartialEq, C: Backing>, { let mut outcomes = Vec::new(); let mut interrupted = 0; loop { let journal_cfg = journal_cfg.clone(); let outcome = deterministic::Runner::default().start(|context| async move { // Record the digest of empty storage. A completed destroy must restore it. let empty = context.storage_audit(); let faults = MutationFaults::default(); let context = MutationFaultContext { inner: context, faults: faults.clone(), }; let merkle_cfg = merkle_config("interrupted-destroy"); let open = |context| { Journal::::new( context, merkle_cfg.clone(), journal_cfg.clone(), |op: &TestOp| op.is_commit(), ForwardFold, ) }; // Commit twice around a prune, so the frontier holds a boundary and pins that // the retained operations cannot rebuild. let ops: Vec> = (0..102u8) .map(|i| match i { 50 => TestOp::::Commit(None, Location::new(0)), 101 => TestOp::::Commit(None, Location::new(40)), _ => create_operation::(i), }) .collect(); let mut journal = open(context.child("first")).await.unwrap(); let fresh_root = journal.root(0).unwrap(); for op in &ops[..51] { (journal, _) = journal.append(op).await.unwrap(); } journal = journal.sync().await.unwrap(); (journal, _) = journal.prune(Location::new(40)).await.unwrap(); for op in &ops[51..] { (journal, _) = journal.append(op).await.unwrap(); } let journal = journal.sync().await.unwrap(); let bounds = journal.bounds(); let root = journal.root(0).unwrap(); assert!(bounds.start > 0 && bounds.end == 102); // Destroy fails exactly when one of its mutations was refused. faults.allow(interrupted); let destroyed = journal.destroy().await.is_ok(); let stopped = faults.failed(); faults.disarm(); let scenario = format!("stopped after {interrupted} mutations"); assert_eq!(destroyed, !stopped, "{scenario}"); if destroyed { assert_eq!(context.inner.storage_audit(), empty, "{scenario}"); return Interrupted::Completed; } // Removing its last partition is the last step of the operation journal's // removal, so destroy finished it exactly when all its partitions are gone. let mut journal_removed = true; for partition in journal_partitions { journal_removed &= !partition_exists(&context, partition).await; } // The reopened journal is exactly the last commit or empty. let mut journal = open(context.child("second")) .await .unwrap_or_else(|err| panic!("{scenario}: must reopen: {err}")); let outcome = if journal.bounds() == bounds { assert!( !journal_removed, "{scenario}: reopened at its last commit without its operation journal" ); assert_eq!(journal.root(0).unwrap(), root, "{scenario}"); for pos in bounds { let index = usize::try_from(pos).expect("position must fit in usize"); assert_eq!(journal.read(pos).await.unwrap(), ops[index], "{scenario}"); } Interrupted::Unchanged } else { assert_eq!(journal.bounds(), 0..0, "{scenario}"); assert_eq!(journal.root(0).unwrap(), fresh_root, "{scenario}"); // An emptied journal keeps nothing of its past, so other operations // committed to it reopen under their own root. for i in 150..190u8 { (journal, _) = journal.append(&create_operation::(i)).await.unwrap(); } (journal, _) = journal .append(&TestOp::::Commit(None, Location::new(0))) .await .unwrap(); journal = journal.sync().await.unwrap(); let reused = journal.root(0).unwrap(); drop(journal); journal = open(context.child("third")).await.unwrap(); assert_eq!(journal.bounds(), 0..41, "{scenario}"); assert_eq!(journal.root(0).unwrap(), reused, "{scenario}"); if journal_removed { Interrupted::InFrontier } else { Interrupted::InJournal } }; // A retried destroy completes and leaves no blob behind. journal.destroy().await.unwrap(); assert_eq!(context.inner.storage_audit(), empty, "{scenario}"); outcome }); outcomes.push(outcome); if outcome == Interrupted::Completed { break; } interrupted += 1; } // Nothing changes before the first mutation, and a later stop never leaves destroy at // an earlier outcome. assert_eq!(outcomes[0], Interrupted::Unchanged); assert!(outcomes.is_sorted(), "{outcomes:?}"); // A stage no stop point interrupts is a stage whose recovery this does not exercise. for outcome in [ Interrupted::Unchanged, Interrupted::InJournal, Interrupted::InFrontier, Interrupted::Completed, ] { assert!( outcomes.contains(&outcome), "a stop point must reach {outcome:?}: {outcomes:?}" ); } // Destroy stages the operation journal's clear and removes each of its partitions, then // removes the frontier, so it can stop at least once before each. assert!( interrupted >= journal_partitions.len() as u64 + 2, "{interrupted}" ); } /// A fixed operation journal that keeps few blobs once pruned, and its partitions. fn fixed_destroy_config() -> (JConfig, Vec) { let mut cfg = journal_config("interrupted-destroy"); cfg.items_per_blob = NZU64!(32); let partition = &cfg.partition; let partitions = vec![ format!("{partition}-blobs"), format!("{partition}-metadata"), ]; (cfg, partitions) } /// A variable operation journal that keeps few blobs once pruned, and its partitions. fn variable_destroy_config() -> (VConfig<()>, Vec) { let mut cfg = variable_journal_config("interrupted-destroy"); cfg.items_per_section = NZU64!(32); let partition = &cfg.partition; let partitions = vec![ format!("{partition}_data"), format!("{partition}_offsets-blobs"), format!("{partition}_offsets-metadata"), ]; (cfg, partitions) } /// Regression test for https://github.com/commonwarexyz/monorepo/issues/5668. /// /// A destroy interrupted at any point leaves a journal over a fixed operation journal that /// reopens at its last commit or empty, and that a retried destroy removes. #[test] fn issue_5668_regression_interrupted_destroy_reopens_fixed_mmr() { let (cfg, partitions) = fixed_destroy_config(); interrupted_destroy_reopens::< mmr::Family, ContiguousJournal>, >(cfg, &partitions); } /// Regression test for https://github.com/commonwarexyz/monorepo/issues/5668. /// /// A destroy interrupted at any point leaves a journal over a fixed operation journal that /// reopens at its last commit or empty, and that a retried destroy removes. #[test] fn issue_5668_regression_interrupted_destroy_reopens_fixed_mmb() { let (cfg, partitions) = fixed_destroy_config(); interrupted_destroy_reopens::< mmb::Family, ContiguousJournal>, >(cfg, &partitions); } /// Regression test for https://github.com/commonwarexyz/monorepo/issues/5668. /// /// A destroy interrupted at any point leaves a journal over a variable operation journal that /// reopens at its last commit or empty, and that a retried destroy removes. #[test] fn issue_5668_regression_interrupted_destroy_reopens_variable_mmr() { let (cfg, partitions) = variable_destroy_config(); interrupted_destroy_reopens::< mmr::Family, VariableJournal>, >(cfg, &partitions); } /// Regression test for https://github.com/commonwarexyz/monorepo/issues/5668. /// /// A destroy interrupted at any point leaves a journal over a variable operation journal that /// reopens at its last commit or empty, and that a retried destroy removes. #[test] fn issue_5668_regression_interrupted_destroy_reopens_variable_mmb() { let (cfg, partitions) = variable_destroy_config(); interrupted_destroy_reopens::< mmb::Family, VariableJournal>, >(cfg, &partitions); } /// A bounded open that selects no item empties the journal and discards a frontier recorded /// above the journal's start. A cap that selects a commit below the frontier's boundary still /// fails and changes nothing. #[test_traced] fn test_init_at_most_without_match_empties_journal_beside_frontier() { let executor = deterministic::Runner::default(); executor.start(|context| async move { let fresh = create_empty_journal::(context.child("fresh"), "no-match-fresh").await; let fresh_root = fresh.root(0).unwrap(); fresh.destroy().await.unwrap(); let open_at_most = |context: Context, suffix: &'static str, max_size: u64| { TestJournal::::init_at_most( context, merkle_config(suffix), journal_config(suffix), max_size, |op: &TestOp| op.is_commit(), ForwardFold, ) }; for (suffix, max_size) in [("no-match-one", 1), ("no-match-zero", 0)] { // Commit twice to a log that starts at zero, then record a frontier above the // log's start, as pruning does before it deletes operations. let mut journal = create_empty_journal::(context.child("first"), suffix).await; for i in 0..10u8 { let op = match i { 1 | 9 => TestOp::::Commit(None, Location::new(0)), _ => create_operation::(i), }; (journal, _) = journal.append(&op).await.unwrap(); } journal = journal.sync().await.unwrap(); let boundary = Location::new(8); let pins = journal.pinned_nodes_at(boundary).await.unwrap(); journal.frontier = journal.frontier.set(boundary, pins).await.unwrap(); drop(journal); // The first commit ends at two, below the frontier's boundary, and the frontier // keeps it. assert!(matches!( open_at_most(context.child("below_boundary"), suffix, 3).await, Err(Error::Journal(JournalError::ItemPruned(8))) )); let recovery = TestJournal::::prepare( context.child("unchanged"), merkle_config(suffix), journal_config(suffix), None, |op: &TestOp| op.is_commit(), ForwardFold, ) .await .unwrap(); assert_eq!(recovery.bounds(), 8..10); drop(recovery); // No commit ends at or below the cap, so the journal is emptied and the frontier // discarded. let journal = open_at_most(context.child("no_match"), suffix, max_size) .await .expect("a bounded open that selects no item must succeed"); assert_eq!(journal.bounds(), 0..0); assert_eq!(journal.root(0).unwrap(), fresh_root); drop(journal); let journal = create_empty_journal::(context.child("reopened"), suffix).await; assert_eq!(journal.bounds(), 0..0); assert_eq!(journal.root(0).unwrap(), fresh_root); journal.destroy().await.unwrap(); } }); } }