Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -39,6 +39,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- A retract that removes several values of one attribute in one call now hides all of them (#371).
- Queries no longer lose or duplicate facts when more than 65,535 facts are waiting for a checkpoint (#445; also fixed in v2.0.3).
- **A file shorter than its meta page count is refused at open with `STG-044`** (#497). Open never compared the meta page's `page_count` with the file's length. A truncated file (an interrupted copy, a partial download) opened, and its queries and checkpoints then failed with `INT-049` after the WAL had accepted writes. A meta with a `page_count` far past the end opened too: its next checkpoint wrote at that page id, leaving a sparse file of up to 4 EiB, and `verify()` scanned to that count and never finished. Open now refuses both, read-write and read-only, without modifying the file. It does not fall back to the other meta page, because a valid newer meta means that checkpoint happened. A checkpoint now fails with `INT-049` instead of writing a meta that counts pages the backend does not hold, and `verify()` reports a `page_count` past the end as `STG-044` and stops its page scan at the end of the file. `BrowserDb` is not checked: it keeps only live pages (#440), so its store has no length to compare. New code `STG-044`.
- **A file shorter than one page is refused at open with `STG-045` unless it is a torn first write** (#506). Open treated any file under 4 KiB as a new database, because it holds no whole page, and a read-write open wrote a new empty database over it. A database cut below one page by an interrupted copy, or an unrelated file at the path, was silently replaced. Now such a file opens as a new database only when its bytes are zeros or a prefix of the first meta page a new database writes (what a crash during creation can leave, the rule a torn full page 0 already followed); anything else is `STG-045`, read-write and read-only, and the file is not modified. A zero-length file is still a new database. New code `STG-045`.
- Reopening next to a WAL whose entries were all already checkpointed no longer rewinds the transaction counter, so later transactions no longer reuse `tx_count` values and `:as-of` history stays correct (#447; also fixed in v2.0.3).

### Internal
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -197,7 +197,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1380 tests** (1371 passing, 9 ignored; unit + integration + doc).
**1381 tests** (1372 passing, 9 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1380 tests
cargo test # run 1381 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
14 changes: 14 additions & 0 deletions docs/ERROR_REFERENCE.md
Original file line number Diff line number Diff line change
Expand Up @@ -156,6 +156,7 @@ with no `CodedError` anywhere in its chain.
| STG-042 | Database file not found (read-only open) | Storage |
| STG-043 | Log writer target already exists | Storage |
| STG-044 | File shorter than its meta page count | Storage |
| STG-045 | File shorter than one page and not a new database | Storage |
| WAL-001 | Invalid WAL magic number | WAL |
| WAL-002 | Unsupported WAL version | WAL |
| WAL-003 | Value size exceeds maximum | WAL |
Expand Down Expand Up @@ -2289,6 +2290,19 @@ let mut out = LogWriter::create("memory.v2.graph", OpenOptions::new())?;

**Scenario**: A `.graph` file is copied to another machine and the copy stops partway.

### STG-045 File shorter than one page and not a new database

**Error text**: `File is {} bytes, shorter than one page, and is not a new Minigraf database`

**Cause**: The file is longer than zero bytes but shorter than one 4 KiB page, and its bytes are not a torn first write of a new database. Creating a database writes its first meta page in one go, so a crash during that write can leave only a prefix of that page (or zeros); such a file is opened as a new, empty database. Any other short file is something else: a different file at the path, a database cut short by an interrupted copy, or a damaged file. Earlier versions opened it as a new database and a read-write open overwrote it. The file is not modified, read-write or read-only.

**Resolution**:
- Check that the path points at the intended `.graph` file.
- Copy the database again from its source, or restore it from backup.
- If the file is not needed, delete it and open the path again to create a new database.

**Scenario**: A copy of a `.graph` file stops after its first kilobyte, and the copy is opened.

---

## WAL — Write-Ahead Log Errors
Expand Down
6 changes: 3 additions & 3 deletions docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

Binary file not shown.
Binary file not shown.
22 changes: 16 additions & 6 deletions fuzz/fuzz_targets/corrupt_file.rs
Original file line number Diff line number Diff line change
Expand Up @@ -15,7 +15,9 @@
//! Each query must fail or return exactly the answer of the last generation or
//! of the one before it (the meta fallback when the active meta page is
//! damaged), and every query that answers must agree on one generation. A
//! mismatch panics. `verify()` runs too and may fail, but must not panic.
//! mismatch panics. A file cut below one page must fail to open or open as a
//! new, empty database (#506). `verify()` runs too and may fail, but must not
//! panic.
#![no_main]
use libfuzzer_sys::fuzz_target;
use minigraf::{Minigraf, OpenOptions, QueryResult};
Expand Down Expand Up @@ -162,11 +164,6 @@ fuzz_target!(|data: &[u8]| {
2 => bytes.truncate(trunc),
_ => {}
}
// An empty file opens as a new, empty database. A file shorter than one
// page does too today (#506); skipped until that is fixed.
if bytes.len() < PAGE_SIZE {
return;
}

let Ok(dir) = tempfile::tempdir() else {
return;
Expand All @@ -180,6 +177,19 @@ fuzz_target!(|data: &[u8]| {
return;
};

// A file shorter than one page opens only as a new, empty database: when
// it is empty, or what is left is a prefix of a first meta write (#506).
if bytes.len() < PAGE_SIZE {
assert_eq!(db.current_tx_count(), 0, "short file opened with data");
for q in QUERIES {
assert!(
rows(&db, q).is_none_or(|r| r.is_empty()),
"short file answered with data"
);
}
return;
}

// The last generation, or the one before it; narrowed by every answer.
let mut candidates: Vec<&Answers> = t.generations[1..].iter().collect();
candidates.retain(|g| g.tx_count == db.current_tx_count());
Expand Down
9 changes: 9 additions & 0 deletions src/error.rs
Original file line number Diff line number Diff line change
Expand Up @@ -188,6 +188,7 @@ pub(crate) enum ErrorCode {
Stg042,
Stg043,
Stg044,
Stg045,
Wal001,
Wal002,
Wal003,
Expand Down Expand Up @@ -1093,6 +1094,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[
"File is shorter than its meta page: the meta counts {} pages but the file holds {} (truncated?)",
ErrorCategory::Storage,
),
(
ErrorCode::Stg045,
"STG-045",
"File is {} bytes, shorter than one page, and is not a new Minigraf database",
ErrorCategory::Storage,
),
(
ErrorCode::Wal001,
"WAL-001",
Expand Down Expand Up @@ -2007,6 +2014,7 @@ mod tests {
| ErrorCode::Stg042
| ErrorCode::Stg043
| ErrorCode::Stg044
| ErrorCode::Stg045
| ErrorCode::Wal001
| ErrorCode::Wal002
| ErrorCode::Wal003
Expand Down Expand Up @@ -2229,6 +2237,7 @@ mod tests {
ErrorCode::Stg042,
ErrorCode::Stg043,
ErrorCode::Stg044,
ErrorCode::Stg045,
ErrorCode::Wal001,
ErrorCode::Wal002,
ErrorCode::Wal003,
Expand Down
4 changes: 4 additions & 0 deletions src/storage/backend/fault_inject.rs
Original file line number Diff line number Diff line change
Expand Up @@ -102,6 +102,10 @@ impl<B: StorageBackend> StorageBackend for FaultInjectingBackend<B> {
self.inner.holds_every_page()
}

fn partial_page(&self) -> Result<Option<Vec<u8>>> {
self.inner.partial_page()
}

fn close(&mut self) -> Result<()> {
let mut cfg = self.config.lock().unwrap();
let limit = cfg.fail_close_after;
Expand Down
23 changes: 23 additions & 0 deletions src/storage/backend/file.rs
Original file line number Diff line number Diff line change
Expand Up @@ -442,6 +442,23 @@ impl StorageBackend for FileBackend {
Ok(self.page_count)
}

fn partial_page(&self) -> Result<Option<Vec<u8>>> {
let start = self
.page_count
.checked_mul(PAGE_SIZE as u64)
.ok_or_else(|| {
err_coded!(
ErrorCode::Int048,
format!("page offset overflow for page_count {}", self.page_count)
)
})?;
let mut file = &self.file;
file.seek(SeekFrom::Start(start))?;
let mut tail = Vec::new();
file.take(PAGE_SIZE as u64).read_to_end(&mut tail)?;
Ok((!tail.is_empty()).then_some(tail))
}

fn close(&mut self) -> Result<()> {
if self.read_only {
return Ok(());
Expand Down Expand Up @@ -494,6 +511,7 @@ mod tests {
{
let mut backend = FileBackend::open(&path).unwrap();
assert_eq!(backend.page_count().unwrap(), 0);
assert_eq!(backend.partial_page().unwrap(), None);
backend.write_page(5, &vec![0xABu8; PAGE_SIZE]).unwrap();
assert_eq!(backend.page_count().unwrap(), 6);
assert!(backend.read_page(6).is_err(), "past the end must fail");
Expand All @@ -511,9 +529,14 @@ mod tests {
let mut backend = FileBackend::open(&path).unwrap();
assert!(backend.page_count().unwrap() > 0);
assert_eq!(backend.page_count().unwrap(), 6, "partial page not counted");
assert_eq!(
backend.partial_page().unwrap(),
Some(vec![0xCDu8; PAGE_SIZE / 2])
);
backend.write_page(6, &vec![0x11u8; PAGE_SIZE]).unwrap();
assert_eq!(backend.read_page(6).unwrap()[PAGE_SIZE - 1], 0x11);
assert_eq!(backend.page_count().unwrap(), 7);
assert_eq!(backend.partial_page().unwrap(), None, "tail overwritten");
}

/// The child half of [`test_cross_process_lock_retries_then_fails_within_budget`]:
Expand Down
7 changes: 7 additions & 0 deletions src/storage/btree.rs
Original file line number Diff line number Diff line change
Expand Up @@ -745,6 +745,13 @@ impl<B: StorageBackend> StorageBackend for MutexStorageBackend<B> {
self.0.lock().map_or(true, |b| b.holds_every_page())
}

fn partial_page(&self) -> Result<Option<Vec<u8>>> {
self.0
.lock()
.map_err(|_| err_coded!(ErrorCode::Int050, "MutexStorageBackend"))?
.partial_page()
}

fn close(&mut self) -> Result<()> {
bail_coded!(ErrorCode::Int049, "MutexStorageBackend is read-only")
}
Expand Down
9 changes: 9 additions & 0 deletions src/storage/mod.rs
Original file line number Diff line number Diff line change
Expand Up @@ -102,6 +102,15 @@ pub trait StorageBackend: Send + Sync {
true
}

/// The bytes past the last whole page, if any: a file whose length is not
/// a multiple of `PAGE_SIZE` ends in a partial page that `page_count`
/// leaves out. Open uses it to tell a torn first write of a new file from
/// a short file that is something else (#506). Backends without a byte
/// length return `None`.
fn partial_page(&self) -> Result<Option<Vec<u8>>> {
Ok(None)
}

/// Close the storage backend.
///
/// Performs final sync and cleanup.
Expand Down
26 changes: 20 additions & 6 deletions src/storage/persistent_facts.rs
Original file line number Diff line number Diff line change
Expand Up @@ -183,6 +183,14 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
let mut backend = self.lock()?;
let page_count = backend.page_count()?;
if page_count == 0 {
// A file shorter than one page is new only if it holds a torn
// first write of `init_empty`; anything else is not ours to
// re-initialise (#506).
if let Some(tail) = backend.partial_page()?
&& !is_initial_meta_prefix(&tail)
{
bail_coded!(ErrorCode::Stg045, tail.len());
}
return Ok(Opened::Fresh);
}
let page0 = backend.read_page(0)?;
Expand Down Expand Up @@ -796,12 +804,7 @@ fn check_single_valid(
/// file: a prefix of its bytes, then zeros, with page 1 (if present) all zero.
/// Such a file never committed anything, so it is safe to initialise again.
fn is_torn_initial_meta(backend: &dyn StorageBackend, page0: &[u8]) -> Result<bool> {
let expected = MetaPage::empty(1).encode();
let written = page0
.iter()
.rposition(|&b| b != 0)
.map_or(0, |i| i.saturating_add(1));
if page0.get(..written) != expected.get(..written) {
if !is_initial_meta_prefix(page0) {
return Ok(false);
}
if backend.page_count()? > 1 && backend.read_page(1)?.iter().any(|&b| b != 0) {
Expand All @@ -810,6 +813,17 @@ fn is_torn_initial_meta(backend: &dyn StorageBackend, page0: &[u8]) -> Result<bo
Ok(true)
}

/// True if `bytes` are a prefix of the empty generation-1 meta, then zeros:
/// what a torn write of `init_empty`'s page 0 can leave.
fn is_initial_meta_prefix(bytes: &[u8]) -> bool {
let expected = MetaPage::empty(1).encode();
let written = bytes
.iter()
.rposition(|&b| b != 0)
.map_or(0, |i| i.saturating_add(1));
bytes.get(..written) == expected.get(..written)
}

/// Encode `facts` for a checkpoint on top of `m`'s dictionary: assign ids,
/// write new long values to fresh value pages, and build every tree's entries.
fn encode(
Expand Down
47 changes: 47 additions & 0 deletions tests/integrity_test.rs
Original file line number Diff line number Diff line change
Expand Up @@ -170,6 +170,53 @@ fn truncated_file_is_refused_at_open() {
}
}

/// A file shorter than one page opens as a new database only when it is a
/// torn first write: zeros, or a prefix of the empty generation-1 meta. Any
/// other short file (here a database cut to under a page, or foreign bytes) is refused with STG-045, read-write and read-only, and is
/// left as it was; it used to be re-initialised (#506).
#[test]
fn sub_page_file_is_refused_unless_a_torn_first_write() {
let dir = tempfile::tempdir().unwrap();
let (path, _) = checkpointed_file(dir.path(), "short.graph");
// A second checkpoint moves page 0 off the empty generation-1 meta. A
// file cut below a page after one checkpoint is indistinguishable from a
// torn first write, and holds nothing to keep: every tree lies past it.
{
let db = Minigraf::open(&path).unwrap();
fill(&db, 200, 210);
db.checkpoint().unwrap();
}
let template = std::fs::read(&path).unwrap();
std::fs::remove_file(&path).unwrap();
let foreign = vec![0x5Au8; 100];
for bytes in [&template[..2222], &template[..20], &foreign[..]] {
std::fs::write(&path, bytes).unwrap();
assert_eq!(open_code(&path, false), "STG-045");
assert_eq!(open_code(&path, true), "STG-045");
assert_eq!(std::fs::read(&path).unwrap(), bytes, "file unchanged");
assert!(
!dir.path().join("short.graph.wal").exists(),
"no WAL created"
);
}

// A torn first write: init_empty's page 0 cut short, or zeros.
let fresh = dir.path().join("fresh.graph");
drop(Minigraf::open(&fresh).unwrap());
let initial = std::fs::read(&fresh).unwrap();
std::fs::remove_file(&fresh).unwrap();
for bytes in [&initial[..8], &initial[..40], &[0u8; 300][..]] {
std::fs::write(&path, bytes).unwrap();
assert_eq!(open_code(&path, true), "opened");
let db = Minigraf::open(&path).unwrap();
db.execute("(transact [[:a :b 1]])").unwrap();
db.checkpoint().unwrap();
drop(db);
assert_eq!(std::fs::metadata(&path).unwrap().len() % PAGE_SIZE, 0);
std::fs::remove_file(&path).unwrap();
}
}

/// A CRC-valid meta whose `page_count` is far past the end of the file is
/// refused at open: it used to open, and its next checkpoint wrote at that
/// page id, leaving a 4 EiB sparse file (#497).
Expand Down
Loading