Problem class: shell-20261007-crash-consistent-btree-page-recovery
Below is the complete, verified solution. It is also saved at /workspace/solution/SOLUTION.md, with runnable recover.sh, mkfixture.sh, and verify.sh in the same directory. ./verify.sh reports 23 passed, 0 failed.
Problem class: shell-20261007-crash-consistent-btree-page-recovery
Environment: bash 5.3 / coreutils + mawk
Deliverables: recover.sh (the fix), mkfixture.sh (hazard generator), verify.sh (23 assertions).
The store is a page file (tree.pages) plus a write-ahead log (tree.wal). The log
is not a clean, ordered, trusted stream once a crash intervenes. Five independent
failure modes can each corrupt a naive replay:
| # | Hazard | Why it corrupts a naive replay |
|---|---|---|
| 1 | Reordered writes — pages are flushed to tree.wal in arbitrary order |
Applying records in file order can patch a page before its base image / with a stale LSN. Correctness requires replay in LSN order, not byte order. |
| 2 | Torn page images — a FULL record / checkpoint page was only partially written |
A truncated image silently overwrites a good page with garbage. Each page and each FULL payload must carry a self-describing checksum. |
| 3 | Duplicate LSNs — same (page, lsn) appears more than once |
Identical retries are harmless if collapsed; conflicting bodies at the same LSN mean one is forged/corrupt and neither may be trusted. |
| 4 | Crash during checkpoint replacement — tree.pages.new was fsynced but the atomic rename never ran |
Reading only tree.pages loses the newer checkpoint; reading .new blindly can pick a torn checkpoint. Selection must be by validated generation, not by filename. |
| 5 | Forged checksums — a record/page whose digest is wrong or forged | A weak/omitted digest lets an attacker or bit-rot inject arbitrary pages. Use SHA-256 over the canonical record including the LSN, so no two distinct records can share a digest. |
The other hard requirements constrain the shape of the fix:
sort, de-duplicated
with a streaming awk group-by, and applied one 1 KiB page at a time.fsynced, then rename(2)d over the target, and the directory is fsynced.
A crash anywhere before the rename leaves the old tree intact.LC_ALL=C sort with an explicit (page, lsn, checksum) key and a
fixed conflict policy (drop the whole conflicting group) make repeated runs
byte-identical.tree.pages N * 1024-byte pages
page = 960-byte payload || 64 hex chars = sha256(payload)
tree.pages.meta gen=<n> lsn=<high water mark> sha256=<whole file>
tree.pages.new checkpoint written but not yet renamed (candidates: .new, base, .bak)
tree.wal LF-terminated text records, exactly 6 '|'-separated fields:
LSN|PAGE|TYPE|OFF|DATA|SHA256
SHA256 = sha256("LSN|PAGE|TYPE|OFF|DATA")
TYPE = FULL (1024-byte image, 2048 hex) | DELTA (patch at OFF)
recover.shSave as recover.sh, chmod +x recover.sh, run ./recover.sh STORE_DIR.
#!/usr/bin/env bash
# recover.sh - bounded-memory, crash-consistent page B-tree recovery.
#
# Reconstructs store/tree.pages from the newest fully-validated checkpoint
# candidate plus a reordered/duplicated/torn/forged write-ahead log. The
# result is committed with an atomic rename + fsync so a crash during
# recovery leaves the previous tree intact.
#
# Usage: recover.sh [STORE_DIR]
# STORE_DIR defaults to ".". Recognised files inside STORE_DIR:
# tree.pages committed base image (PAGE_SIZE-byte pages)
# tree.pages.meta gen=<n> lsn=<n> sha256=<whole-file-hex>
# tree.pages.new checkpoint written but rename not completed
# tree.pages.new.meta
# tree.pages.bak previous base image (fallback)
# tree.pages.bak.meta
# tree.wal newline-delimited text records
#
# WAL record grammar (exactly 6 '|'-separated fields, LF-terminated):
# LSN|PAGE|TYPE|OFF|DATA|SHA256
# LSN positive decimal, log sequence number
# PAGE non-negative decimal, target page index
# TYPE FULL | DELTA
# OFF byte offset inside the 960-byte page payload (DELTA only)
# DATA lower/upper hex; FULL must be 1024 bytes (2048 hex chars)
# SHA256 hex digest of "LSN|PAGE|TYPE|OFF|DATA"
#
# Exit status: 0 recovered, 1 usage/IO error, 2 no usable checkpoint.
set -euo pipefail
PAGE_SIZE=1024
PAYLOAD_SIZE=960
TRAILER_SIZE=64 # hex chars (32 bytes) of sha256(payload)
HEX_PAGE=2048 # 1024 bytes as hex
HEX_SHA=64
log() { printf 'recover: %s\n' "$*" >&2; }
die() { printf 'recover: %s\n' "$*" >&2; exit 1; }
D="${1:-.}"
[ -d "$D" ] || die "no such store directory: $D"
D="$(cd "$D" && pwd)" # normalise so renames stay on one filesystem
have() { command -v "$1" >/dev/null 2>&1; }
for t in dd od xxd sha256sum sort awk mktemp stat; do
have "$t" || die "required tool missing: $t"
done
# fsync a path (file or directory) when the platform supports it.
fsync_path() {
sync -f "$1" 2>/dev/null || sync
}
TMP="$(mktemp -d "${TMPDIR:-/tmp}/recover.XXXXXX")"
cleanup() { rm -rf "$TMP"; }
trap cleanup EXIT
# ---------------------------------------------------------------------------
# 1. Baseline: pick the newest fully-valid checkpoint candidate.
# ---------------------------------------------------------------------------
# A candidate is valid when it is a whole-file sha match AND every page's
# embedded trailer equals sha256(payload). The embedded trailer is what makes
# a torn page image detectable even if the sidecar digest is stale.
page_valid() {
local f="$1" i="$2"
local off=$(( i * PAGE_SIZE ))
local want got
got="$(dd if="$f" bs=1 skip="$off" count="$PAYLOAD_SIZE" status=none \
| sha256sum | awk '{print $1}')"
want="$(dd if="$f" bs=1 skip=$(( off + PAYLOAD_SIZE )) count="$TRAILER_SIZE" status=none)"
[ "$got" = "$want" ]
}
file_pages_valid() {
local f="$1" sz n i
[ -f "$f" ] || return 1
sz="$(stat -c %s "$f" 2>/dev/null || echo 0)"
[ $(( sz % PAGE_SIZE )) -eq 0 ] || return 1
n=$(( sz / PAGE_SIZE ))
i=0
while [ "$i" -lt "$n" ]; do
page_valid "$f" "$i" || return 1
i=$(( i + 1 ))
done
return 0
}
best_file=""
best_gen=-1
best_lsn=0
consider_candidate() {
local f="$1"
local meta="$f.meta"
local gen lsn want got
[ -f "$f" ] && [ -f "$meta" ] || return 0
gen="$(sed -n 's/^gen=//p' "$meta" | head -n1)"
lsn="$(sed -n 's/^lsn=//p' "$meta" | head -n1)"
want="$(sed -n 's/^sha256=//p' "$meta" | head -n1)"
[[ "$gen" =~ ^[0-9]+$ && "$lsn" =~ ^[0-9]+$ && "$want" =~ ^[0-9a-f]{64}$ ]] \
|| { log "ignore $f: malformed sidecar"; return 0; }
# sha256sum streams the file: memory use stays bounded.
got="$(sha256sum "$f" | awk '{print $1}')"
if [ "$got" != "$want" ]; then
log "ignore $f: whole-file sha mismatch"
return 0
fi
if ! file_pages_valid "$f"; then
log "ignore $f: torn/invalid page trailer"
return 0
fi
if [ "$gen" -gt "$best_gen" ]; then
best_gen="$gen"; best_file="$f"; best_lsn="$lsn"
fi
}
# Highest generation wins; .new means a checkpoint rename did not complete.
consider_candidate "$D/tree.pages.new"
consider_candidate "$D/tree.pages"
consider_candidate "$D/tree.pages.bak"
base_pages=0
if [ -n "$best_file" ]; then
base_pages=$(( $(stat -c %s "$best_file") / PAGE_SIZE ))
log "base=$best_file gen=$best_gen base_lsn=$best_lsn pages=$base_pages"
else
log "no valid checkpoint; rebuilding from WAL only"
fi
# ---------------------------------------------------------------------------
# 2. Validate + canonicalise the WAL (streaming, one record in memory).
# ---------------------------------------------------------------------------
: > "$TMP/valid"
re_int='^[0-9]+$'
re_hex='^[0-9a-fA-F]+$'
re_sha='^[0-9a-fA-F]{64}$'
re_type='^(FULL|DELTA)$'
if [ -f "$D/tree.wal" ]; then
dropped=0
# `while read` intentionally ignores a final line with no LF: a torn tail.
while IFS= read -r line; do
line="${line%$'\r'}"
IFS='|' read -r lsn page type off data sha extra <<<"$line"
if [ -n "${extra:-}" ]; then dropped=$(( dropped + 1 )); continue; fi
[[ "$lsn" =~ $re_int && "$lsn" -gt 0 ]] || { dropped=$(( dropped + 1 )); continue; }
[[ "$page" =~ $re_int ]] || { dropped=$(( dropped + 1 )); continue; }
[[ "$type" =~ $re_type ]] || { dropped=$(( dropped + 1 )); continue; }
[[ "$off" =~ $re_int ]] || { dropped=$(( dropped + 1 )); continue; }
[[ -n "$data" && "$data" =~ $re_hex && $(( ${#data} % 2 )) -eq 0 ]] \
|| { dropped=$(( dropped + 1 )); continue; }
[[ "$sha" =~ $re_sha ]] || { dropped=$(( dropped + 1 )); continue; }
bytes=$(( ${#data} / 2 ))
if [ "$type" = FULL ]; then
[ "$bytes" -eq "$PAGE_SIZE" ] || { dropped=$(( dropped + 1 )); continue; }
[ "$off" -eq 0 ] || { dropped=$(( dropped + 1 )); continue; }
# Reject a torn layer-2 page image: its own trailer must verify.
printf '%s' "$data" | xxd -r -p > "$TMP/full.bin"
fgot="$(dd if="$TMP/full.bin" bs=1 count="$PAYLOAD_SIZE" status=none \
| sha256sum | awk '{print $1}')"
fwant="$(dd if="$TMP/full.bin" bs=1 skip="$PAYLOAD_SIZE" \
count="$TRAILER_SIZE" status=none)"
[ "$fgot" = "$fwant" ] || { dropped=$(( dropped + 1 )); continue; }
else
[ $(( off + bytes )) -le "$PAYLOAD_SIZE" ] || { dropped=$(( dropped + 1 )); continue; }
fi
data="${data,,}" # deterministic lower-case hex
canon="$lsn|$page|$type|$off|$data"
want="$(printf '%s' "$canon" | sha256sum | awk '{print $1}')"
[ "$want" = "${sha,,}" ] || { dropped=$(( dropped + 1 )); continue; }
# Emit canonical, re-keyed as PAGE|LSN|... for the external sort.
printf '%s|%s|%s|%s|%s|%s\n' \
"$page" "$lsn" "$type" "$off" "$data" "${sha,,}" >> "$TMP/valid"
done < "$D/tree.wal"
log "wal validated: kept $(wc -l < "$TMP/valid") dropped $dropped"
else
log "no tree.wal present"
fi
# ---------------------------------------------------------------------------
# 3. Reorder + de-duplicate deterministically.
# - sort by (page, lsn, checksum): restores write order regardless of the
# order bytes happened to reach the platter;
# - a group with byte-identical records collapses to one;
# - a group with *conflicting* bodies at the same (page,lsn) is dropped
# wholesale, since one of them must be forged/corrupt.
# ---------------------------------------------------------------------------
if [ -s "$TMP/valid" ]; then
LC_ALL=C sort -t'|' -k1,1n -k2,2n -k6,6 "$TMP/valid" > "$TMP/sorted"
awk -F'|' '
function flush() {
if (prev != "" && !conflict) print first
}
{
key = $1 "|" $2
if (key != prev) { flush(); prev = key; first = $0; conflict = 0 }
else if ($0 != first) { conflict = 1 }
}
END { flush() }
' "$TMP/sorted" > "$TMP/dedup"
else
: > "$TMP/dedup"
fi
log "wal after dedup: $(wc -l < "$TMP/dedup") record(s)"
# A page beyond the checkpoint only exists if the WAL seeds it with a FULL
# image. DELTAs that target an unknown page are meaningless and are dropped
# here so they cannot extend the tree with blank pages.
if [ -s "$TMP/dedup" ]; then
awk -F'|' -v bp="$base_pages" '
{
p = $1 + 0
if (p < bp) { print; next }
if ($3 == "FULL") { seen[p] = 1; print; next }
if (seen[p]) { print }
}
' "$TMP/dedup" > "$TMP/apply"
else
: > "$TMP/apply"
fi
log "wal applicable: $(wc -l < "$TMP/apply") record(s)"
# ---------------------------------------------------------------------------
# 4. Apply records page-by-page. Only one 1 KiB page is resident at a time.
# ---------------------------------------------------------------------------
OUT="$TMP/tree.pages.out"
: > "$OUT"
PAGE_BIN="$TMP/page.bin"
PATCH_BIN="$TMP/patch.bin"
last_emitted=-1
cur=-1
page_exists=0
applied_max="$best_lsn"
applied=0
BLANK_SHA="$(head -c "$PAYLOAD_SIZE" /dev/zero | tr '\0' ' ' | sha256sum | awk '{print $1}')"
blank_page() { # a gap page is still self-verifying
head -c "$PAYLOAD_SIZE" /dev/zero | tr '\0' ' '
printf '%s' "$BLANK_SHA"
}
load_base_page() {
local p="$1"
if [ -n "$best_file" ] && [ "$p" -lt "$base_pages" ]; then
dd if="$best_file" bs="$PAGE_SIZE" skip="$p" count=1 status=none > "$PAGE_BIN"
page_exists=1
else
blank_page > "$PAGE_BIN"
page_exists=0
fi
}
finalize_page() {
[ "$cur" -ge 0 ] || return 0
local got
got="$(dd if="$PAGE_BIN" bs=1 count="$PAYLOAD_SIZE" status=none \
| sha256sum | awk '{print $1}')"
printf '%s' "$got" | dd of="$PAGE_BIN" bs=1 seek="$PAYLOAD_SIZE" \
conv=notrunc status=none
cat "$PAGE_BIN" >> "$OUT"
last_emitted="$cur"
}
copy_base_range() { # copy base pages [lo, hi]
local q="$1" hi="$2"
while [ "$q" -le "$hi" ]; do
if [ -n "$best_file" ] && [ "$q" -lt "$base_pages" ]; then
dd if="$best_file" bs="$PAGE_SIZE" skip="$q" count=1 status=none >> "$OUT"
else
blank_page >> "$OUT"
fi
last_emitted="$q"
q=$(( q + 1 ))
done
}
while IFS='|' read -r p lsn type off data sha; do
# A record already folded into the chosen checkpoint is a no-op.
if [ "$lsn" -le "$best_lsn" ]; then continue; fi
if [ "$p" -ne "$cur" ]; then
finalize_page
copy_base_range "$(( last_emitted + 1 ))" "$(( p - 1 ))"
load_base_page "$p"
cur="$p"
fi
case "$type" in
FULL)
printf '%s' "$data" | xxd -r -p > "$PAGE_BIN"
page_exists=1
;;
DELTA)
if [ "$page_exists" -eq 1 ]; then
printf '%s' "$data" | xxd -r -p > "$PATCH_BIN"
dd if="$PATCH_BIN" of="$PAGE_BIN" bs=1 seek="$off" \
conv=notrunc status=none
else
log "drop DELTA on unknown page $p lsn $lsn"
continue
fi
;;
esac
applied=$(( applied + 1 ))
[ "$lsn" -gt "$applied_max" ] && applied_max="$lsn"
done < "$TMP/apply"
finalize_page
copy_base_range "$(( last_emitted + 1 ))" "$(( base_pages - 1 ))"
# ---------------------------------------------------------------------------
# 5. Commit atomically: same-directory rename after fsync.
# ---------------------------------------------------------------------------
target="$D/tree.pages"
stage="$D/tree.pages.recovered"
cp "$OUT" "$stage"
fsync_path "$stage"
mv -f "$stage" "$target"
fsync_path "$D"
new_gen=$(( best_gen + 1 )); [ "$new_gen" -lt 1 ] && new_gen=1
new_sha="$(sha256sum "$target" | awk '{print $1}')"
meta_stage="$D/tree.pages.meta.recovered"
printf 'gen=%s\nlsn=%s\nsha256=%s\n' "$new_gen" "$applied_max" "$new_sha" > "$meta_stage"
fsync_path "$meta_stage"
mv -f "$meta_stage" "$D/tree.pages.meta"
fsync_path "$D"
# The pre-rename checkpoint is now folded in; drop it so reruns are clean.
rm -f "$D/tree.pages.new" "$D/tree.pages.new.meta"
fsync_path "$D"
# Deterministic summary (no timestamps / paths that vary between runs).
printf 'pages=%s applied=%s gen=%s lsn=%s sha256=%s\n' \
"$(( $(stat -c %s "$target") / PAGE_SIZE ))" "$applied" \
"$new_gen" "$applied_max" "$new_sha"
PAGE|LSN|… and passed through
LC_ALL=C sort -t'|' -k1,1n -k2,2n -k6,6, so replay order is (page, lsn)
regardless of byte order.FULL image must be exactly 1024 bytes and its own
960/64 trailer must verify; a torn checkpoint .new fails file_pages_valid.awk group-by keeps one copy of a
byte-identical group and drops the entire group on conflict.{tree.pages.new, tree.pages, tree.pages.bak} are each
checked against sha256 + per-page trailer, and the highest valid gen
wins; .new being present is not trusted by itself.LSN|PAGE|TYPE|OFF|DATA; any mutation
changes the digest.sync -f → mv (same directory) → sync -f
directory; the old tree.pages is only replaced after the new one is durable.sort spills to disk.The repository ships mkfixture.sh (builds stores containing every hazard) and
verify.sh (23 assertions). Reproduce with:
chmod +x recover.sh mkfixture.sh verify.sh
./verify.sh
mkfixture.sh generates three scenarios:
gen=5, a valid not-yet-renamed checkpoint gen=6, and a WAL
with shuffled LSNs, an exact duplicate, a conflicting duplicate, a torn tail
(no final LF), a forged digest, and a DELTA for an unknown page.tree.pages.new has a clobbered page trailer (must be rejected).Actual output of ./verify.sh on the reference machine:
== scenario: hazards ==
recover: base=/tmp/vh/tree.pages.new gen=6 base_lsn=100 pages=4
recover: wal validated: kept 9 dropped 1
recover: wal after dedup: 6 record(s)
recover: wal applicable: 5 record(s)
pages=4 applied=5 gen=7 lsn=106 sha256=d1310a28141bcd9ba9d7a5014767678172822873a91b25b85c27671befc0e002
ok - newest checkpoint (.new gen6) selected
ok - forged checksum rejected
ok - conflicting duplicate LSN group dropped (6 survive dedup)
ok - page0 = ver=9 (reordered deltas in LSN order)
ok - page1 = ver=9 (FULL, identical dupe deduped)
ok - page2 = ver=8 (conflicting dupe dropped, later delta applies)
ok - page3 = ver=9 (shuffled FULL creates page)
ok - recovered file self-verifies
ok - pre-rename checkpoint consumed
recover: base=/tmp/vh/tree.pages gen=7 base_lsn=106 pages=4
recover: wal validated: kept 9 dropped 1
recover: wal after dedup: 6 record(s)
recover: wal applicable: 5 record(s)
ok - second recovery is byte-identical
ok - second recovery applies no records
ok - no staging files left behind
== scenario: torn_new ==
recover: ignore /tmp/vt/tree.pages.new: torn/invalid page trailer
recover: base=/tmp/vt/tree.pages gen=5 base_lsn=100 pages=3
recover: wal validated: kept 9 dropped 1
recover: wal after dedup: 6 record(s)
recover: wal applicable: 5 record(s)
pages=4 applied=5 gen=6 lsn=106 sha256=d1310a28141bcd9ba9d7a5014767678172822873a91b25b85c27671befc0e002
ok - torn .new rejected
ok - committed base gen5 used
ok - page0 rebuilt from base+delta
ok - page1 FULL applied
ok - page3 created from WAL
ok - torn_new output self-verifies
== scenario: wal_only ==
recover: no valid checkpoint; rebuilding from WAL only
recover: wal validated: kept 9 dropped 1
recover: wal after dedup: 6 record(s)
recover: wal applicable: 2 record(s)
pages=4 applied=2 gen=1 lsn=105 sha256=68d855486962c8e32dd320e9fc60c8eca4bfa76fb8c8376b1b623a0fdc81c40f
ok - no-checkpoint rebuild has output
ok - FULL page1 present
ok - FULL page3 present
ok - delta without seed page dropped
ok - wal_only output self-verifies
23 passed, 0 failed
Key evidence:
dropped 1; the
conflicting (page 2, LSN 104) pair collapses the dedup set from 9 to 6 and
leaves page 2 to the later valid LSN 106 delta (ver=8), not AAAA/BBBB.gen=6 checkpoint bytes are used, the shuffled FULL
for page 3 and deduped FULL for page 1 land correctly, reordered deltas for
page 0 apply in LSN order..new is ignored and gen=5
is used.d1310a28…c0e002 and applies zero records../mkfixture.sh /tmp/store hazards
./recover.sh /tmp/store
for p in 0 1 2 3; do
printf 'page %s: ' "$p"
dd if=/tmp/store/tree.pages bs=1 skip=$((p*1024)) count=30 status=none; echo
done
Expected:
page 0: PAGE 0 ROOT ver=9
page 1: PAGE 1 LEAF ver=9
page 2: PAGE 2 LEAF ver=8
page 3: PAGE 3 NEW ver=9
The hazard generator and full assertion suite are in /workspace/solution/mkfixture.sh and /workspace/solution/verify.sh (also appended verbatim in SOLUTION.md).
# Evidence - Problem class: shell-20261007-crash-consistent-btree-page-recovery - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-08T04:05:42.857Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Build a bounded-memory recovery utility for a page-oriented B-tree whose WAL may contain reordered writes, torn page images, duplicate LSNs, and a crash during checkpoint replacement. Reconstruct the newest valid tree while preserving atomic rename/fsync guarantees, rejecting forged checksums, and producing deterministic output across repeated recovery runs.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "shell-20261007-crash-consistent-btree-page-recovery", "provider": "openrouter", "solved_at": "2026-10-08T04:05:42.857Z", "version": "5"}