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
83 changes: 83 additions & 0 deletions .github/workflows/crash-kill.yml
Original file line number Diff line number Diff line change
@@ -0,0 +1,83 @@
name: SIGKILL crash-safety fuzz (nightly)

# #308: an abrupt kill landing mid-checkpoint had a ~26% chance of leaving
# the header on disk with a bumped page_count but a stale checksum --
# permanent corruption with no recovery path. The bug was in the ordering
# of our own synchronous write calls, not any OS-specific durability
# boundary, so it affected every platform equally; this runs the full
# matrix rather than Linux only. tests/crash_kill_test.rs runs a small
# smoke count in the per-PR suite (rust.yml, already cross-platform); this
# workflow runs a much larger round count nightly for statistical
# confidence on each OS.

on:
schedule:
- cron: "17 3 * * *"
workflow_dispatch:

permissions:
contents: read
issues: write

jobs:
crash-kill:
name: SIGKILL fuzz suite
strategy:
fail-fast: false
matrix:
os: [ubuntu-latest, windows-latest, macos-latest]
runs-on: ${{ matrix.os }}
timeout-minutes: 30

steps:
- uses: actions/checkout@v4

- name: Install Rust stable
uses: dtolnay/rust-toolchain@stable

- name: Run the SIGKILL crash-safety fuzz suite
shell: bash
env:
MINIGRAF_CRASH_KILL_ROUNDS: "100"
RUST_BACKTRACE: 1
run: |
set -o pipefail
cargo test --test crash_kill_test -- --nocapture 2>&1 | tee crash-kill-output.txt

- name: Record SIGKILL crash-safety failure
if: ${{ failure() }}
shell: bash
env:
GH_TOKEN: ${{ github.token }}
ISSUE_TITLE: "Nightly SIGKILL crash-safety failure (${{ matrix.os }})"
run: |
report_file="crash-kill-failure.md"
{
echo "The nightly SIGKILL crash-safety fuzz suite failed on ${{ matrix.os }}."
echo
echo "- Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID"
echo "- Commit: $GITHUB_SHA"
echo "- Reproduce: cargo test --test crash_kill_test -- --nocapture"
echo " (set MINIGRAF_CRASH_KILL_ROUNDS to raise the round count)"
echo
echo "## Test output"
echo
echo '```text'
tail -n 1000 crash-kill-output.txt
echo '```'
} > "$report_file"

existing_issue="$(gh issue list \
--repo "$GITHUB_REPOSITORY" \
--state open \
--search "$ISSUE_TITLE in:title" \
--json number,title \
--limit 100 \
--jq ".[] | select(.title == \"$ISSUE_TITLE\") | .number" \
| head -n 1)"

if [ -n "$existing_issue" ]; then
gh issue comment "$existing_issue" --repo "$GITHUB_REPOSITORY" --body-file "$report_file"
else
gh issue create --repo "$GITHUB_REPOSITORY" --title "$ISSUE_TITLE" --body-file "$report_file"
fi
51 changes: 50 additions & 1 deletion src/storage/backend/file.rs
Original file line number Diff line number Diff line change
Expand Up @@ -377,10 +377,22 @@ impl StorageBackend for FileBackend {
// Page 0 is the header itself, parse it to update our cached copy
self.header = FileHeader::from_bytes(data)?;
} else if page_id >= self.header.page_count {
// Update page count if this is a new page (but not page 0)
// Bump and persist the page count so a plain reopen (no
// deliberate commit in between) still sees pages written this
// session -- callers like `test_file_backend_persistence`
// depend on that. #308: the bug here was writing the bumped
// page_count with a *stale* header_checksum left over from the
// last real commit, so a crash before that commit finished left
// a permanently checksum-invalid header with no recovery path.
// The fix is to recompute the checksum over the whole header
// every time, so the on-disk header is self-consistent at
// every single-page write, not just at the deliberate commits
// in `PersistentFactStorage::save`.
self.header.page_count = page_id
.checked_add(1)
.ok_or_else(|| anyhow::anyhow!("page_count overflow for page_id {}", page_id))?;
self.header.header_checksum =
crate::storage::persistent_facts::compute_header_checksum(&self.header);
Self::write_header(&mut self.file, &self.header)?;
}

Expand Down Expand Up @@ -460,6 +472,43 @@ mod tests {
FileBackend::open(&temp_path).unwrap();
}

/// #308: whenever `write_page` bumps `page_count` for a newly appended
/// page (exactly what `save()`/`checkpoint()` do for every fact and
/// index page, ahead of the deliberate final header commit), the header
/// it persists to disk must have a `header_checksum` matching its own
/// content. Before this fix, the page_count byte moved but the checksum
/// was left stale from the last real commit -- a `SIGKILL` landing in
/// that window (which fires on nearly every appended page) left a
/// permanently checksum-invalid header with no recovery path.
#[test]
fn test_write_page_keeps_disk_header_checksum_consistent_on_page_count_bump() {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("test_header_atomicity.graph");
let mut backend = FileBackend::open(&path).unwrap();

// Append a page well beyond the current page_count (1) -- exactly
// the pattern save()/checkpoint() use when writing fact and index
// pages ahead of the final atomic header commit.
let page_data = vec![0xABu8; PAGE_SIZE];
backend.write_page(5, &page_data).unwrap();

// Read back through the same handle rather than opening the path
// independently: `backend` still holds the file lock, and Windows
// (unlike Unix) refuses a second, unrelated open of a locked file
// even from the same process.
let raw = backend.read_page(0).unwrap();
let on_disk = FileHeader::from_bytes(&raw).unwrap();
let computed = crate::storage::persistent_facts::compute_header_checksum(&on_disk);
assert_eq!(
on_disk.header_checksum, computed,
"on-disk header checksum must match its own content after a page-count bump"
);
assert_eq!(on_disk.page_count, 6);

// In-memory bookkeeping must agree with what's now on disk.
assert_eq!(backend.page_count().unwrap(), 6);
}

/// The child half of [`test_cross_process_lock_retries_then_fails_within_budget`]:
/// opens `db_path`, holds the lock for `MINIGRAF_HOLD_MILLIS`, signalling
/// readiness by creating `MINIGRAF_HOLD_READY_MARKER` right after
Expand Down
103 changes: 101 additions & 2 deletions src/wal.rs
Original file line number Diff line number Diff line change
Expand Up @@ -62,6 +62,33 @@ fn validate_wal_header(file: &mut File) -> Result<()> {
Ok(())
}

/// Whether an existing WAL file's header is intact, or too short to
/// contain one at all.
enum WalHeaderState {
/// At least `WAL_HEADER_SIZE` bytes present; validated by
/// `validate_wal_header` (magic/version checked separately).
Present,
/// Fewer than `WAL_HEADER_SIZE` bytes on disk. This can only happen
/// from a crash between `create_new` and `write_wal_header` completing
/// in `WalWriter::open_or_create` -- before any `WalWriter` existed to
/// append an entry with. Safe to treat as an empty WAL (#308-class
/// fix: the same "kill mid multi-step file write" window that
/// corrupted the main `.graph` header applies here to the WAL sidecar).
Absent,
}

/// Distinguishes a too-short WAL file from one long enough to validate.
/// Does not itself validate magic/version -- callers still run
/// `validate_wal_header` on the `Present` case.
fn check_wal_header_length(file: &mut File) -> Result<WalHeaderState> {
let len = file.metadata()?.len();
if len < WAL_HEADER_SIZE as u64 {
Ok(WalHeaderState::Absent)
} else {
Ok(WalHeaderState::Present)
}
}

// ─── Entry serialization ────────────────────────────────────────────────────

fn serialize_entry(tx_count: u64, facts: &[Fact]) -> Result<Vec<u8>> {
Expand Down Expand Up @@ -141,7 +168,13 @@ impl WalWriter {

// File exists — validate its header and seek to end for appending
let mut file = OpenOptions::new().read(true).write(true).open(path)?;
validate_wal_header(&mut file)?;
match check_wal_header_length(&mut file)? {
WalHeaderState::Present => validate_wal_header(&mut file)?,
// A previous crash landed between this file's creation and its
// header write completing; no entry could have been appended
// yet, so re-initialize it as a fresh, empty WAL.
WalHeaderState::Absent => write_wal_header(&mut file)?,
}
file.seek(SeekFrom::End(0))?;
Ok(WalWriter { file })
}
Expand Down Expand Up @@ -197,7 +230,16 @@ impl WalReader {
/// Open the WAL at `path` for reading.
pub fn open(path: &Path) -> Result<Self> {
let mut file = File::open(path)?;
validate_wal_header(&mut file)?;
match check_wal_header_length(&mut file)? {
WalHeaderState::Present => validate_wal_header(&mut file)?,
// Too short to contain a header, which can only mean a crash
// landed before any entry was ever appended (see
// `WalHeaderState::Absent`). `read_entries` already treats
// hitting EOF while reading an entry as "no more entries", so
// leaving the file as-is and letting that seek-past-end happen
// naturally is correct -- there is nothing here to replay.
WalHeaderState::Absent => {}
}
Ok(WalReader { file })
}

Expand Down Expand Up @@ -464,6 +506,63 @@ mod tests {
assert!(result.is_err(), "bad magic should be rejected");
}

/// #308-class fix: a crash between `create_new` and the header write
/// finishing in `open_or_create` leaves a WAL file shorter than
/// `WAL_HEADER_SIZE`. No entry could ever have been appended at that
/// point (that requires a fully-open `WalWriter`), so this must be
/// treated as an empty WAL rather than a hard read error.
#[test]
fn test_wal_reader_tolerates_header_shorter_than_wal_header_size() {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("short.wal");

// Simulates a kill mid-write_wal_header: only the magic made it out.
std::fs::write(&path, b"MWAL").unwrap();

let mut reader = WalReader::open(&path).unwrap();
let entries = reader.read_entries().unwrap();
assert!(
entries.is_empty(),
"a too-short WAL header must read back as empty, not error"
);
}

/// As above, but for the writer side: re-opening a WAL left too short
/// by a prior crash must re-initialize it with a fresh header instead
/// of failing `open_or_create`, and the WAL must be fully usable
/// afterward.
#[test]
fn test_wal_writer_reinitializes_header_shorter_than_wal_header_size() {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("short.wal");

std::fs::write(&path, b"MW").unwrap();

let mut writer = WalWriter::open_or_create(&path).unwrap();
let alice = Uuid::new_v4();
let fact = make_fact(alice, ":name", Value::String("Alice".to_string()), 1);
writer.append_entry(1, std::slice::from_ref(&fact)).unwrap();
drop(writer);

let mut reader = WalReader::open(&path).unwrap();
let entries = reader.read_entries().unwrap();
assert_eq!(entries.len(), 1, "re-initialized WAL must accept entries");
}

/// A completely empty (0-byte) WAL file -- the earliest possible point
/// in the crash window, right after `create_new` -- must be tolerated
/// the same way.
#[test]
fn test_wal_reader_tolerates_zero_byte_file() {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("empty.wal");
std::fs::write(&path, []).unwrap();

let mut reader = WalReader::open(&path).unwrap();
let entries = reader.read_entries().unwrap();
assert!(entries.is_empty(), "a 0-byte WAL must read back as empty");
}

#[test]
fn test_wal_truncated_entry_stops_replay() {
let dir = tempfile::tempdir().unwrap();
Expand Down
111 changes: 111 additions & 0 deletions tests/crash_kill_test.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,111 @@
//! #308 regression: a `SIGKILL` during an active `transact`/`checkpoint`
//! must never permanently corrupt the database (header checksum mismatch,
//! no recovery path).
//!
//! Two fixes landed together, both closing the same class of bug -- a
//! multi-step on-disk state transition that a kill could land in the
//! middle of:
//! - `src/storage/backend/file.rs`: `FileBackend::write_page` now
//! recomputes `header_checksum` every time it persists a `page_count`
//! bump, so the on-disk header is self-consistent at every single-page
//! write, not just at the deliberate commits in
//! `PersistentFactStorage::save`.
//! - `src/wal.rs`: a WAL sidecar file shorter than its own header (a crash
//! between `create_new` and `write_wal_header` completing) is now
//! treated as an empty WAL instead of a hard read error, since no entry
//! could ever have been appended at that point.
//!
//! This test reproduces the original report directly: spawn a child that
//! loops `transact` + `checkpoint()` on a fresh `.graph` file, kill it with
//! a real `SIGKILL` at a random point mid-loop, and confirm a fresh process
//! can still open the file afterward.
//!
//! Round count is controlled by `MINIGRAF_CRASH_KILL_ROUNDS` (default: a
//! small smoke count so this runs unconditionally, cheaply, in the per-PR
//! suite). `.github/workflows/crash-kill.yml` runs a much larger nightly
//! count for statistical confidence, matching the ~26% per-round corruption
//! rate observed in the original report before the fix.
#![cfg(not(target_arch = "wasm32"))]

use minigraf::db::Minigraf;
use std::process::Command;
use std::time::{Duration, Instant};

/// Per-PR default: cheap enough to run on every CI build, but with a ~1 -
/// 0.74^5 ≈ 78% chance of catching a reintroduced bug at the original 26%
/// per-round corruption rate.
const DEFAULT_ROUNDS: usize = 5;

fn rounds() -> usize {
std::env::var("MINIGRAF_CRASH_KILL_ROUNDS")
.ok()
.and_then(|s| s.parse().ok())
.unwrap_or(DEFAULT_ROUNDS)
}

/// Cheap, dependency-free jitter for the kill delay. No cryptographic
/// requirement here -- just enough spread across the checkpoint loop's
/// write window to land the kill at varying points mid-`save()`.
fn jitter_millis(seed: u64, max: u64) -> u64 {
let mut x = seed ^ 0x9E37_79B9_7F4A_7C15;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x % max.max(1)
}

#[test]
fn sigkill_during_checkpoint_never_permanently_corrupts_file() {
let exe = std::env::current_exe().expect("test binary path");

for round in 0..rounds() {
let dir = tempfile::tempdir().unwrap();
let db_path = dir.path().join("kill.graph");

let mut child = Command::new(&exe)
.args(["crash_kill_child_entrypoint", "--exact", "--nocapture"])
.env("MINIGRAF_KILL_DB", &db_path)
.spawn()
.expect("spawn crash-kill child");

let seed = Instant::now().elapsed().as_nanos() as u64
^ (round as u64).wrapping_mul(0x2545_F491_4F6C_DD1D);
let delay = Duration::from_millis(5 + jitter_millis(seed, 150));
std::thread::sleep(delay);

child.kill().expect("SIGKILL crash-kill child");
let status = child.wait().expect("reap crash-kill child");
assert!(
!status.success(),
"round {round}: child must not exit cleanly before being killed"
);

// A fresh handle in a fresh process must always be able to open the
// file after the kill -- this is the exact guarantee #308 broke.
let db = match Minigraf::open(&db_path) {
Ok(db) => db,
Err(e) => panic!("round {round}: reopen after SIGKILL must not fail: {e}"),
};
db.execute("(query [:find ?e :where [?e :k ?v]])")
.unwrap_or_else(|e| panic!("round {round}: query after reopen must not fail: {e}"));
}
}

/// Child half of the SIGKILL fuzz loop above: opens `MINIGRAF_KILL_DB` and
/// loops transact + checkpoint until killed. A no-op when the marker
/// environment variable is absent -- same convention as
/// `tests/common::crash_child_entrypoint`.
#[test]
fn crash_kill_child_entrypoint() {
let Ok(db_path) = std::env::var("MINIGRAF_KILL_DB") else {
return;
};
let db = Minigraf::open(&db_path).expect("child opens db");
let mut i: u64 = 0;
loop {
db.execute(&format!("(transact [[:e{i} :k {i}]])"))
.expect("child transact");
db.checkpoint().expect("child checkpoint");
i += 1;
}
}
Loading