lsm_tree/

error.rs

// SPDX-License-Identifier: Apache-2.0
// Copyright (c) 2024-present, fjall-rs
// Copyright (c) 2026-present, Dmitry Prudnikov

use crate::{Checksum, CompressionType, SeqNo};
#[cfg(not(feature = "std"))]
use alloc::string::String;

/// Represents errors that can occur in the LSM-tree
#[derive(Debug)]
#[non_exhaustive]
pub enum Error {
    /// I/O error
    Io(crate::io::Error),

    /// Decompression failed
    Decompress(CompressionType),

    /// Invalid or unparsable data format version
    InvalidVersion(u8),

    /// Some required files could not be recovered from disk
    Unrecoverable,

    /// The operation was aborted on a caller's cooperative cancellation
    /// request ([`RecoveryProgress::request_cancel`]).
    ///
    /// A repair cancelled BEFORE its manifest commit left the directory
    /// untouched (the scan is read-only), so a retry re-derives everything
    /// from the same bytes; a cancel requested after the commit is ignored
    /// rather than reported, since the rebuilt manifest is already durable.
    ///
    /// [`RecoveryProgress::request_cancel`]: crate::RecoveryProgress::request_cancel
    Cancelled,

    /// The read resolved into an extent that was physically EXCISED — a
    /// hole-punched region that reads back as zeros.
    ///
    /// Tight-space reclaim punches consumed extents in place, and manifest
    /// recovery may keep a table whose surviving blocks are intact around
    /// such a hole rather than discard the whole file. Reading one of the
    /// punched blocks is a genuine, permanent loss of exactly those rows, and
    /// it is reported as such instead of being smuggled out as a checksum
    /// mismatch (which reads as "the bytes rotted") or, worse, as "no such
    /// key" — the latter would fall through to a superseded version in a
    /// lower level and silently resurrect it.
    ///
    /// This is the engine's equivalent of a filesystem returning `EIO` for a
    /// bad extent while the rest of the file keeps reading.
    Excised {
        /// Byte offset of the excised block within the file.
        offset: u64,
    },

    /// Checksum mismatch
    ChecksumMismatch {
        /// Checksum of loaded block
        got: Checksum,

        /// Checksum that was saved in block header
        expected: Checksum,
    },

    /// A memtable entry's per-KV digest, computed at insert under
    /// [`KvChecksumComputePoint::AtInsert`](crate::runtime_config::KvChecksumComputePoint::AtInsert),
    /// did not match a recompute over the entry's current bytes at flush.
    ///
    /// This is the memtable-residence RAM-corruption signal: the entry's
    /// logical content (`value_type`, `seqno`, key, or value) changed while it
    /// sat in the memtable, between insert and flush. Distinct from
    /// [`Self::ChecksumMismatch`] (on-disk block bytes) — this catches a flip
    /// that happens entirely in RAM, before any block is written.
    MemtableKvChecksumMismatch {
        /// Sequence number of the entry whose digest diverged (locates it).
        seqno: u64,

        /// Digest recomputed over the entry's current memtable bytes at flush.
        got: u64,

        /// Digest computed and stored when the entry was inserted.
        expected: u64,
    },

    /// A memtable entry carried an insert-time per-KV digest
    /// ([`KvChecksumComputePoint::AtInsert`](crate::runtime_config::KvChecksumComputePoint::AtInsert))
    /// tagged with an algorithm `AtInsert` never stores: a non-4-byte or
    /// unknown algorithm wire tag.
    ///
    /// `AtInsert` only ever writes a 4-byte algorithm tag (`Xxh3Low32` /
    /// `Crc32c`), so a digest-bearing node tagged otherwise means the node's
    /// algorithm metadata was corrupted in RAM during memtable residence.
    /// Distinct from [`Self::MemtableKvChecksumMismatch`] (the digest value
    /// diverged): here the algorithm itself is unusable, so the engine refuses
    /// to "verify" the entry under the wrong algorithm rather than risk a
    /// flipped tag passing the residence check.
    MemtableKvChecksumCorruptAlgorithm {
        /// Sequence number of the entry whose algorithm tag is invalid.
        seqno: u64,

        /// The invalid algorithm wire tag read from the node.
        tag: u8,
    },

    /// A repair COMMITTED its rebuilt manifest, but a later step failed: the
    /// repair's own post-commit cleanup, or the follow-up open inside
    /// [`Config::open_or_repair`](crate::Config::open_or_repair).
    ///
    /// The report travels WITH the error because it exists only in that call:
    /// the retry finds a healthy manifest (its open sweeps any cleanup
    /// leftover itself), runs no repair, and answers `None` — an
    /// external-WAL consumer would otherwise never learn its replay
    /// obligation
    /// ([`RepairReport::wal_replay_scope`](crate::RepairReport::wal_replay_scope))
    /// and could keep stale or resurrected values. Consume the report exactly
    /// as a successful repair's, then retry the open (`cause` is typically
    /// transient).
    #[cfg(feature = "std")]
    RepairedButUnopened {
        /// The completed repair's report — not rederivable on a retry.
        report: alloc::boxed::Box<crate::RepairReport>,

        /// The follow-up open's failure.
        cause: alloc::boxed::Box<Self>,
    },

    /// The on-disk tree's type does not match the type the configuration
    /// requests: a standard open (no `kv_separation_opts`) of a KV-separated
    /// (blob) tree, or the reverse.
    ///
    /// This is a CONFIGURATION error — fix the options and reopen — not
    /// damage, so [`Config::open_or_repair`](crate::Config::open_or_repair)
    /// propagates it instead of repairing: a rebuild under the mismatched
    /// type would commit a manifest of the wrong tree shape (a `Standard`
    /// rebuild of a blob tree strands every blob file behind SSTs full of
    /// indirections, and the orphan sweep then deletes them).
    TreeTypeMismatch {
        /// The type the configuration requested.
        requested: crate::TreeType,

        /// The type the on-disk tree actually has.
        actual: crate::TreeType,
    },

    /// Blob frame header CRC mismatch (V4 format).
    /// Distinct from `ChecksumMismatch` which covers data payload checksums.
    HeaderCrcMismatch {
        /// CRC recomputed from header fields
        recomputed: u32,

        /// CRC stored in the blob frame header
        stored: u32,
    },

    /// Invalid enum tag
    InvalidTag((&'static str, u8)),

    /// Invalid block trailer
    InvalidTrailer,

    /// Invalid block header
    InvalidHeader(&'static str),

    /// Data size (decompressed, on-disk, or requested) is invalid or exceeds a safety limit
    DecompressedSizeTooLarge {
        /// Size associated with the data being processed. This may come from
        /// on-disk/in-memory metadata (e.g., header, block/value handle) or be
        /// derived from caller input (e.g., a requested key or value length),
        /// and may be zero, invalid, or over the configured limit.
        declared: u64,

        /// Maximum allowed size for the data or request being processed
        limit: u64,
    },

    /// UTF-8 error
    Utf8(core::str::Utf8Error),

    /// Merge operator failed.
    ///
    /// No context payload — consistent with other unit variants
    /// (`Unrecoverable`, `InvalidTrailer`). Operators should log
    /// details before returning this error.
    MergeOperator,

    /// Encryption failed
    Encrypt(&'static str),

    /// Decryption failed
    Decrypt(&'static str),

    /// Comparator mismatch on tree reopen.
    ///
    /// The tree was created with a comparator whose [`crate::UserComparator::name`]
    /// differs from the one supplied at reopen time.
    ComparatorMismatch {
        /// Comparator name persisted in the tree metadata.
        stored: String,

        /// Comparator name supplied by the caller.
        supplied: &'static str,
    },

    /// Zstd dictionary required but not provided, or `dict_id` mismatch
    ZstdDictMismatch {
        /// Dictionary ID stored in the block/table metadata
        expected: u32,

        /// Dictionary ID provided by the caller (`None` if no dictionary supplied)
        got: Option<u32>,
    },

    /// Per-record XXH3-64 mismatch inside a framed manifest section
    /// (`tables` / `blob_files`). Distinct from
    /// [`Error::ChecksumMismatch`] — same XXH3 family but a
    /// different output width (XXH3-64 here vs XXH3-128 for
    /// block-level payloads) on a different layer of the on-disk
    /// format, with different recovery semantics (manifest framing
    /// surfaces routed through `ManifestRecoveryMode`; block
    /// checksums surface via `Error::ChecksumMismatch` for the
    /// block I/O paths). Strict manifest recovery modes surface
    /// this so an operator can see the exact 64-bit digests that
    /// disagreed; `SkipAnyCorruptedRecords` and
    /// `PointInTimeRecovery` route around the corruption without
    /// raising it.
    ManifestFrameChecksumMismatch {
        /// SFA section the corrupt record was found in (e.g.
        /// `"tables"`, `"blob_files"`). Static so this can be
        /// compared without parsing message strings.
        section: &'static str,
        /// XXH3-64 digest the framing header claimed for the
        /// record's payload.
        expected: u64,
        /// XXH3-64 digest the reader recomputed over the bytes
        /// actually on disk.
        got: u64,
    },

    /// Range tombstone block decode failure.
    RangeTombstoneDecode {
        /// Which field or validation failed (e.g. `start_len`, `start`, `seqno`, `interval`)
        field: &'static str,

        /// Byte offset within the block to the start of the field whose decoding failed
        /// (captured before reading bytes for that field).
        offset: u64,
    },

    /// A [`WriteBatch`](crate::WriteBatch) contains mixed operation types
    /// (e.g. insert + remove) for the same user key.
    ///
    /// Mixed ops at the same logical version are rejected because the
    /// memtable/skiplist ordering ties on `(user_key, seqno)` and does not
    /// include `value_type` as a tie-breaker. That would otherwise make
    /// equal-key entries with different operation types ambiguous to later
    /// reads and merges, yielding tie-break-dependent "last write wins"
    /// semantics.
    MixedOperationBatch,

    /// Tree was opened with `Config::page_ecc(true)` but this build of
    /// the crate does not have the `page_ecc` cargo feature enabled.
    /// The reader has no way to verify or recover Reed-Solomon parity
    /// without the codec, so opening such a tree would silently
    /// downgrade integrity guarantees — return this error instead.
    PageEccUnsupported,

    /// Block payload failed the XXH3 integrity check and the
    /// attached Reed-Solomon parity trailer could not reconstruct
    /// it (more shards are corrupted than the (4, 2) RS scheme
    /// can recover). Surfaced ONLY by ECC-protected blocks
    /// (the `ECC_PARITY` header flag set); a block written without parity
    /// (`Config::page_ecc(false)`) on a checksum mismatch returns
    /// [`Self::ChecksumMismatch`] instead, because there's no
    /// parity to even attempt recovery from.
    PageEccUnrecoverable {
        /// XXH3 checksum recomputed from the on-disk bytes.
        got: Checksum,
        /// XXH3 checksum stored in the block header.
        expected: Checksum,
    },

    /// Route-compatibility mismatch on reopen.
    ///
    /// Recovery found fewer tables on disk than the manifest expects, and all
    /// missing tables are on levels not covered by any current
    /// [`level_routes`](crate::Config::level_routes).  This typically means a
    /// previously configured route was removed, leaving its directory
    /// unreachable.
    ///
    /// Re-adding the missing route(s) will usually resolve the error.  If
    /// missing tables are on levels that *are* covered by a current route,
    /// recovery returns [`Unrecoverable`](Self::Unrecoverable) instead
    /// (the SST files were genuinely lost).
    RouteMismatch {
        /// Number of tables listed in the manifest.
        expected: usize,

        /// Number of tables actually found across all configured routes.
        found: usize,
    },

    /// Valid configuration / on-disk layout that this build does not
    /// yet know how to process, or constructor input that violates a
    /// documented invariant (e.g. `CompressionType::None` passed to
    /// [`crate::table::block::CompressionContext::new`]). Distinct
    /// from [`Error::Unrecoverable`] (signals corruption) and from
    /// [`Error::Io`] with `ErrorKind::Unsupported` (which can also
    /// surface from platform / backend limits); the `&'static str`
    /// payload names the specific marker that triggered the rejection
    /// (e.g. `"filter_tli"` for a partitioned filter SFA section,
    /// `"compression-context-none"` for the constructor invariant) so
    /// the caller can route the diagnostic without parsing message
    /// strings.
    FeatureUnsupported(&'static str),

    /// The tree directory is already locked by another live instance.
    ///
    /// Returned by [`Config::open`](crate::Config::open) and
    /// [`Config::repair`](crate::Config::repair) when the cross-process
    /// directory lock (a `LOCK` file under the tree directory, held via an
    /// advisory OS file lock) could not be acquired because another process
    /// owns it. Holds the directory path as a display string for diagnostics.
    /// Two processes mutating the same manifest would corrupt it, so the second
    /// acquirer fails fast here. Disable the lock with
    /// [`Config::with_directory_lock`](crate::Config::with_directory_lock) only
    /// when exclusivity is enforced at a higher layer.
    Locked(String),

    /// Manifest footer / TOC / file-level discovery failure.
    ///
    /// Scoped to errors detected at or before the TOC is parsed —
    /// i.e. everything the reader needs *before* it can answer
    /// "where is section X". Section-content failures (a specific
    /// section's Block fails verification) go through
    /// [`ManifestSectionInvalid`](Error::ManifestSectionInvalid)
    /// instead so callers like `Tree::open` can distinguish a
    /// totally unreadable manifest from a per-section problem.
    ///
    /// Typical causes:
    ///
    /// - **Footer-payload structural failure:** unknown layout
    ///   version, oversized section count, empty/oversized section
    ///   name, invalid UTF-8, duplicate section name, footer
    ///   payload exceeds the 4 KiB reservation.
    /// - **Tail / head-mirror double failure:** both the
    ///   tail-footer Block read and the head-mirror fallback
    ///   failed verification (XXH3 mismatch, AEAD decryption,
    ///   parse error). Per-path causes are logged at `error`
    ///   level and collapsed here.
    /// - **TOC entry value corruption:** a TOC entry's
    ///   `block_offset + block_size` overflows `u64` or extends
    ///   past the end of the file. The TOC bytes are footer
    ///   payload, so a malformed TOC entry is a footer-level
    ///   issue even though it surfaces in
    ///   `ManifestArchiveReader::read_section`.
    /// - **Trailing size-hint corruption:** the tail's 4-byte
    ///   footer-size hint is zero or exceeds
    ///   `HEAD_FOOTER_RESERVED_SIZE` (4 KiB), or the implied
    ///   `section_end` lands inside the head reservation. Caught
    ///   in both the reader and `checkpoint::write_current_for_version`.
    /// - **Writer-side invariant breach:** `write_cursor` would
    ///   overflow `u64`, an in-memory section would exceed the
    ///   on-disk Block-size cap, etc.
    /// - **CURRENT pointer points at a missing manifest:** when
    ///   `version::get_current_version` opens the referenced
    ///   `v{N}` file and gets `NotFound`, the error is rewrapped
    ///   here so `Tree::open`'s outer `Io(NotFound) => create_new`
    ///   arm cannot mistake a half-applied recovery / corrupted
    ///   state for a clean first-open.
    ManifestFooterInvalid(&'static str),

    /// Manifest section content failed verification or matched no
    /// TOC entry.
    ///
    /// Surfaced by `ManifestArchiveReader::read_section` (and the
    /// helper that validates the inner Block header before
    /// delegating to `Block::from_reader`). Distinct from
    /// [`ManifestFooterInvalid`](Error::ManifestFooterInvalid)
    /// because the footer / TOC loaded fine — the bad bytes are
    /// localised to one section Block and a caller MAY route
    /// recovery differently (e.g. skip the section vs. refuse
    /// the whole manifest).
    ///
    /// Causes:
    ///
    /// - **Requested section name not in TOC:** the caller asked
    ///   for a section that the manifest doesn't declare.
    /// - **Section Block header doesn't fit its outer buffer:**
    ///   the inner block's derived on-disk size (header + payload +
    ///   parity-if-flagged) exceeds the TOC-declared `block_size`.
    ///   Defence-in-depth against a forged TOC pointing at a too-small
    ///   slot.
    /// - **Block decoded at the TOC offset has the wrong
    ///   `block_type`:** TOC says "section here" but the bytes
    ///   carry a non-`Manifest` Block. Defence-in-depth against
    ///   TOC-redirect attacks; once AAD-binding lands in
    ///   `encryption::block`, `Block::from_reader` will reject
    ///   this internally and the check here becomes belt-and-
    ///   braces.
    ManifestSectionInvalid(&'static str),

    /// The trailing record of the incremental manifest edit log is
    /// incomplete or corrupt, and the active
    /// [`ManifestRecoveryMode`](crate::config::ManifestRecoveryMode) does
    /// not tolerate that defect, so the open aborts rather than silently
    /// rolling the edit back.
    ///
    /// A clean end-of-log is never reported here: a crash exactly at a
    /// record boundary is byte-identical to a pristine close, so that
    /// case is always tolerated. This fires when bytes of a trailing
    /// record are present but the record fails framing — a
    /// power-loss-truncated append (only
    /// [`AbsoluteConsistency`](crate::config::ManifestRecoveryMode::AbsoluteConsistency)
    /// rejects it; other modes roll it back), or a fully-framed record
    /// whose checksum doesn't match (bit-rot) / whose header is forged
    /// (rejected by both `AbsoluteConsistency` and
    /// [`TolerateCorruptedTailRecords`](crate::config::ManifestRecoveryMode::TolerateCorruptedTailRecords),
    /// which salvages writer-incomplete tails only; rolled back under
    /// `PointInTimeRecovery` / `SkipAnyCorruptedRecords`).
    ///
    /// Recover by truncating the torn tail: run
    /// [`Config::repair`](crate::Config::repair), which rebuilds a clean
    /// standalone snapshot (dropping the edit log), or re-open under a
    /// [`ManifestRecoveryMode`](crate::config::ManifestRecoveryMode) that
    /// tolerates the defect to roll the trailing edit back.
    TornManifestEditLog {
        /// The trailing defect detected: `"truncated"` (partial record
        /// from a power-loss-interrupted append), `"checksum-mismatch"`
        /// (fully-framed record whose payload bit-rotted),
        /// `"bad-header"` (implausible framing length), or
        /// `"len-mismatch"` (record length disagrees with the expected
        /// fixed size). Static so callers can branch without parsing
        /// the message string.
        kind: &'static str,
    },

    /// A write was declined by the storage admission gate because accepting it
    /// could push the tree's live footprint past its effective budget.
    ///
    /// Only produced when [`storage_admission_check`](crate::runtime_config::RuntimeConfig::storage_admission_check)
    /// is enabled. The predicate is computed, not latched: raising
    /// [`storage_limit_bytes`](crate::runtime_config::RuntimeConfig::storage_limit_bytes),
    /// freeing disk, or a compaction reclaiming space clears the read-only
    /// state on the next check with no restart. Internal flush / compaction are
    /// never gated (reserved headroom), so the engine can always reclaim space.
    StorageFull {
        /// Live on-disk bytes at the time of the check.
        used: u64,

        /// Effective byte budget that `used` (plus reserved headroom) exceeded.
        limit: u64,
    },

    /// A read asked for a snapshot whose version the history no longer
    /// retains.
    ///
    /// The engine serves a snapshot at seqno `s` from the newest retained
    /// version installed BELOW `s`. Compaction maintenance prunes the history
    /// up to the newest version below the caller's GC watermark
    /// ([`AbstractTree::major_compact`](crate::AbstractTree::major_compact)'s
    /// `seqno_threshold`), and [`AbstractTree::clear`](crate::AbstractTree::clear)
    /// drains it to the new empty version, so afterwards every snapshot at or
    /// below the oldest retained version's seqno has nothing to be served
    /// from. Serving it from the oldest retained version instead would
    /// silently answer with data the snapshot never saw, so the read is
    /// refused. Snapshot `0` is the exception: it sees no entry from any
    /// version and is always served (empty). The boundary is persisted with
    /// the manifest, so the refusal holds across a reopen as well.
    ///
    /// Point reads return it directly; iterators yield it as their first and
    /// only item. [`AbstractTree::oldest_retained_seqno`](crate::AbstractTree::oldest_retained_seqno)
    /// exposes the boundary so a caller can validate a snapshot before
    /// reading: a snapshot is servable iff it is `0` or strictly above that
    /// seqno.
    SnapshotBelowRetention {
        /// The snapshot seqno the read asked for.
        requested: SeqNo,

        /// Seqno of the oldest version the history still retains; reads at
        /// `oldest_retained + 1` and above are servable.
        oldest_retained: SeqNo,
    },
}

impl core::fmt::Display for Error {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "LsmTreeError: {self:?}")
    }
}

impl core::error::Error for Error {
    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
        match self {
            Self::Io(e) => Some(e),
            // The variant is explicitly a causal wrapper: generic error-chain
            // logging and transient-retry classifiers must be able to reach
            // the post-commit step's own failure through the standard chain.
            #[cfg(feature = "std")]
            Self::RepairedButUnopened { cause, .. } => Some(&**cause),
            _ => None,
        }
    }
}

impl From<crate::sfa::Error> for Error {
    fn from(value: crate::sfa::Error) -> Self {
        match value {
            crate::sfa::Error::Io(e) => Self::from(e),
            crate::sfa::Error::ChecksumMismatch { got, expected } => {
                log::error!("Archive ToC checksum mismatch");
                Self::ChecksumMismatch {
                    got: got.into(),
                    expected: expected.into(),
                }
            }
            crate::sfa::Error::InvalidHeader => {
                log::error!("Invalid archive header");
                Self::Unrecoverable
            }
            crate::sfa::Error::InvalidVersion => {
                log::error!("Invalid archive version");
                Self::Unrecoverable
            }
            crate::sfa::Error::UnsupportedChecksumType => {
                log::error!("Invalid archive checksum type");
                Self::Unrecoverable
            }
        }
    }
}

impl Error {
    /// Whether this failure says something about the ENVIRONMENT or the
    /// CALLER's configuration rather than about the bytes on disk — the class
    /// every recovery path must PROPAGATE instead of recording as damage.
    ///
    /// Recording one of these as damage commits a manifest that omits the file
    /// and then removes it, turning a fixable mistake into permanent loss;
    /// propagating lets the operator fix the environment (or supply the right
    /// key / dictionary) and re-run with everything still on disk.
    ///
    /// - [`Self::Io`] of an environmental kind: the interrupted-syscall
    ///   retryables, plus access failures that do not implicate the bytes
    ///   (`PermissionDenied`, `StorageFull`, `QuotaExceeded`,
    ///   `ReadOnlyFilesystem`, `OutOfMemory`).
    /// - [`Self::Decrypt`]: an AEAD failure is exactly what a missing or wrong
    ///   key produces on perfectly healthy ciphertext.
    /// - [`Self::ZstdDictMismatch`]: the persisted descriptor names a
    ///   dictionary the caller did not supply, or supplied a different one.
    ///
    /// A failure that DOES implicate the bytes (a bad sector, a structural
    /// decode failure) is not in this class: a retry cannot fix it, and the
    /// recovery paths grade that file instead of aborting over it.
    #[must_use]
    pub(crate) fn is_environmental(&self) -> bool {
        match self {
            Self::Io(io) => io.kind().is_environmental(),
            Self::Decrypt(_) => true,
            #[cfg(zstd_any)]
            Self::ZstdDictMismatch { .. } => true,
            _ => false,
        }
    }
}

// The `Io` variant carries `crate::io::Error` (the no_std-capable I/O error),
// so this bridge is a direct wrap. Std file-I/O paths surface `std::io::Error`;
// the std-gated bridge below folds those through `crate::io::Error`.
impl From<crate::io::Error> for Error {
    fn from(value: crate::io::Error) -> Self {
        Self::Io(value)
    }
}

#[cfg(feature = "std")]
impl From<std::io::Error> for Error {
    fn from(value: std::io::Error) -> Self {
        Self::Io(value.into())
    }
}

/// Tree result
pub type Result<T> = core::result::Result<T, Error>;