//! Write-ahead logs: the server's only durable state. //! //! A log file is a sequence of frames, `[len u32 LE][check u64 LE][payload]`, //! each a request's entries: a request's whole effect on one log is //! therefore one frame, and lands whole or not at all. Frames are written //! one after another in the order they are given, each where the last //! ended, and synced (`File::sync_data`) before the request is answered; //! concurrent requests share one sync. A log given a journal (`journal`, //! `Files::with_journal`) writes each frame to it too, and waits on the //! journal's sync in place of its own file's: what is said here of a //! log's sync is then of the journal's, and the journal makes the log's //! file durable later, by itself. //! //! A frame's payload is of one of two kinds, told by its first byte: //! //! - `[`: a JSON array of entries (`frame`, `frame_of`), its check the //! first 8 bytes of SHA-256 over the length and payload. //! - `0x01` (`HOLES`): JSON with holes (`frame_with_holes`), its check //! XXH3-64 over the length and payload, little-endian: //! //! ```text //! 0x01 //! json_len u32 LE //! holes u32 LE, how many //! holes × { at u32 LE, start u32 LE, len u32 LE } //! json json_len bytes: the array of entries, each hole written "" //! bytes the rest: the holes' bytes, one after another //! ``` //! //! Each `at` is an offset into `json`, the closing quote of an empty //! string that is a value, not a key; the holes are in order of `at`, //! strictly rising; `start` and `len` are a range of `bytes`, the ranges //! in order, touching, covering `bytes` exactly. It stands for the JSON //! text with, at each `at`, the lowercase hex of that hole's bytes put //! between the quotes (`fill`): byte for byte the payload of the first //! kind of the same entries, which is what every reader here parses. //! `json` as it is is JSON too, so a reader after one item of a frame //! reads it (`text`) and takes a hole's bytes as they are. //! //! After its last frame a file may hold **room**: zeros, written to be //! written over. A frame written over room leaves the file's size and its //! blocks as they were, so its sync has the frame's bytes alone to put on //! disk; a frame that grows the file has the sync put its new size and its //! new blocks there too, which on Linux is a commit of the file system's //! journal, and the larger part of the sync's time. Room is zeros written, //! not blocks reserved (`fallocate`): a block reserved and never written //! costs that commit when a frame first lands in it. A log's end is //! therefore the end of its last whole frame, not its file's: `Wal::len`, //! `Wal::log_bytes`, a frame's `Pos`, what compaction goes by, and //! `log_len` of a file not open count frames, never room. //! //! Room is made as a log is written to, and only then, and only by a log //! with no journal: a log given one is never synced by itself as its //! frames are answered, so room would buy it nothing, and it writes its //! frames alone, over room its file holds already. Of a log with no //! journal, a frame that the //! room left does not hold grows the file by itself and by as many zeros //! as there are bytes of frames written to the file since it was made, //! opened, or closed by its pool, that frame's among them: at most //! `AHEAD`, and never past what the log may grow to before it is compacted //! (`generations`). The file grows under that frame's sync whatever is //! done, which makes frame and room durable together as it would the //! frame alone, and the frames after go into the room. So the first frame //! written to a file since it was opened grows it by that frame and as //! much again, and a second no longer than the first lands in room. //! //! The room in a file is therefore never more than the frames written to //! it since it was opened, nor does the file reach past what its frames //! may grow to without room; the zeros written are never more than twice //! the frames written; and of a log written to again and again, the //! frames that grow the file are the first, then one for each doubling of //! what was written, and from `AHEAD` on one for each `AHEAD` of frames. //! Room is given back, the file cut to its frames, when its log is sealed //! (`generations`), when its pool closes its file, when the log is closed //! (`Wal::close`) or let go, and when it is opened. So a file holds room //! only while a `Wal` holds it open; but every log open when its process //! is killed keeps the room it had until it is next opened. The cut that //! gives room back is synced by nothing but a sync that follows it for //! frames: no frame's being on disk rests on it, and zeros a power cut //! brings back are room to the next open, as a kill's are. //! //! Replay stops at the first place that does not hold a whole frame: one //! whose payload is not empty and passes the check its first byte names, //! or, a byte of no kind this version knows, either check. The file is cut //! there, durably, before anything is written to it. Zeros are no frame: a //! header of zeros names a payload of no bytes, and an empty payload is no //! frame whatever its check, so room reads as the log's end. What follows //! that place is not looked at for frames: zeros are room; anything else is //! a torn tail, `Wal::dropped`. A whole frame is never cut: one this version //! cannot read, of another kind (a later version's), with holes not as its //! kind says, or whose entries do not parse, is an error, `InvalidData`, //! and the log is left as it is. A last write cut short, at any byte, is no //! whole frame, and so is cut, never refused. //! //! What a power cut leaves, and why every frame answered survives it. A //! frame is answered once a `sync_data` of its file, begun after the frame //! was written, has returned. That sync puts on disk every byte written to //! the file before it began and, where the file grew, its size: so the frame //! is on disk whole, with every frame before it, which were written before //! it at lower offsets, and the file is as long as the frame's end at least, //! whether the frame went over room or past the file's end. After the last //! frame synced the disk may hold anything of what was written since: of //! each frame all, part or nothing, in whatever order their blocks got //! there, zeros where room was and they did not; and the file may end //! anywhere from the last frame synced on, short of the room it was given //! or of frames written after, their growing it not yet on disk, or past //! them. Replay reads from the file's start, so it reads every frame synced. //! It takes the frames after them that are there whole, each written after //! the one before it; it stops at the first that is not, whether the file //! ends there, zeros lie there or part of a frame does, and takes nothing //! past it, since whatever lies past a frame that did not reach the disk //! was never synced, and never answered. The cut that follows takes those //! bytes off the disk before a frame is written in their place, so that none //! of them is ever read as following a later frame. Nothing else is ever //! cut off a file but zeros after its frames, and what a failed append or a //! seal with no log after it left there (`mend`). The order of the syncs is //! as without room, which is bytes of the current log's file and no more: //! the files `Wal::sync_first` was given, the sealed logs and the //! directory, then the current log (`sync_written`). //! //! An append that fails, as on a full disk, is cut back from the file, its //! room with it, before the next goes on, and nothing ever aborts. Room that //! cannot be written is left out, and the append stands. A log may be one of //! a `Files` pool's, which keeps at most so many open at once: one file //! descriptor each, opened when needed and closed, least recently used //! first, to make room for another. The pool closes no file in use: one //! whose log is being appended to, or that a sync in flight holds. That //! sync holds the file and no lock of the log's, and the file's lock //! stays with it until it returns: closed by the pool meanwhile, the log //! would find its own file locked at its next append. Nor does the pool //! cut such a file's room. A seal or a close may, while a sync of the //! file runs, and takes nothing from the sync: what it covers is frames, //! all of them before the room. //! //! A log has one writer, which alone knows where its frames end. Every log //! file is locked for as long as it is held open to write to (`flock`, //! exclusive, never waited for): the current log from when it is opened //! until its pool closes it, or the log is closed or let go; a sealed log //! until it is durable, and by what syncs it, a commit or its compaction, //! until that sync returns. A file another handle holds is an error naming //! it, when the log is opened or, of a log whose file is not held, at its //! next append, before anything is written to it or cut off it; and so is //! a file found of another size than it was last found with. A log's file //! is not held, and so not locked, once its pool has closed it, and from //! an open that syncs nothing (`generations`) until its first append: //! nothing of it is written meanwhile. The lock is the open file's, //! so two handles in one process exclude each other as two processes do, //! and it goes when the file is closed, however that comes about. What //! only reads a log (`scan_file`, `read_frame`, `read_sealed`, `read_log`, //! `log_len`) takes no lock and needs none. A child process holds a copy //! of every file its parent has open, and so each one's lock, from when it //! is made until it execs: a process that spawns one holds `spawning` //! meanwhile, and no log's file is opened until it is let go, so that a //! log closed and opened again in that time does not find its own lock //! held. //! //! A log closed (`Wal::close`, and `Files::close` for every log of a pool) //! takes no frame from then on, and every frame it took is on disk once //! `Wal::close` answers, its room given back and its files let go: every //! frame its files hold is then durable, until they are next opened and //! written to. Whatever opens them next may say so (`Wal::open_log_with`, //! `durable`), and then syncs nothing but what it mends, which room is //! not: zeros found after a log's frames are cut off with no sync //! (`generations`, "An open that syncs nothing"). A `Wal` dropped lets its //! files go as one closed does, and gives back its room, but syncs //! nothing: what was not waited for is as a kill leaves it. //! //! Every sync of written data made here, a log's, a checkpoint's or a //! directory's, as a log is opened, waited on, compacted or closed, is told //! to what `on_sync` set; and so is each its users make through `sync_file`, //! `sync_dir`, `flush_file` and `sync_filesystem`. //! //! A log opened with `Wal::open_log` has generations, a file each, and a //! checkpoint folding those before one, and is compacted as it grows and ages: //! see `generations`. //! //! Every file and directory made here is its owner's alone: `0600` and //! `0700`, whatever the umask. #![forbid(unsafe_code)] use serde_json::Value as Json; use sha2::{Digest, Sha256}; use std::collections::BTreeMap; use std::fs::{File, OpenOptions, Permissions}; use std::io::{self, Write}; use std::os::unix::fs::{DirBuilderExt, FileExt, OpenOptionsExt, PermissionsExt}; use std::path::{Path, PathBuf}; use std::sync::atomic::{AtomicBool, AtomicU64, Ordering}; use std::sync::{ Arc, Condvar, Mutex, MutexGuard, PoisonError, RwLock, RwLockWriteGuard, TryLockError, Weak, }; use std::time::{Duration, Instant}; pub mod files; #[cfg(test)] mod frame_tests; mod generations; pub mod journal; pub mod table; pub use generations::{FLOOR, Fold, Layout, Policy, is_seal, read_log, read_sealed}; pub use journal::Journal; /// What is told how long each sync of written data took, if anything is. static ON_SYNC: std::sync::OnceLock = std::sync::OnceLock::new(); /// Have `f` told how long each sync of written data to the disk takes: /// every one this crate makes, of a log as it is opened, waited on, sealed /// or closed, of the checkpoint a compaction writes, of the files a frame /// rests on and of a directory; and each its users make with `sync_file` /// and `sync_dir`. The first one set stays. pub fn on_sync(f: fn(std::time::Duration)) { let _ = ON_SYNC.set(f); } /// One sync of written data, its time told to what `on_sync` set. fn timed(sync: impl FnOnce() -> io::Result<()>) -> io::Result<()> { let started = Instant::now(); let r = sync(); if let Some(f) = ON_SYNC.get() { f(started.elapsed()); } r } /// Make a file's bytes, its size and the rest of what the system keeps of /// it durable: one sync (`on_sync`). pub fn sync_file(file: &File) -> io::Result<()> { timed(|| file.sync_all()) } /// Make a file's bytes and its size durable: one sync (`on_sync`). fn sync_data(file: &File) -> io::Result<()> { timed(|| file.sync_data()) } /// Hand a file's bytes, its size and the rest of what the system keeps of /// it, or a directory's entries, to the drive, as `fsync` does: one sync /// (`on_sync`). On most systems that makes them durable, as `sync_file` /// does. On macOS it does not: the drive may hold what it was handed in a /// cache of its own, and writes all of that out, whatever file it is of, /// when a sync that reaches the disk is next asked of it, as `sync_file` /// and `sync_dir` ask (`F_FULLFSYNC`). So many files are made durable by /// this of each, then one `sync_file` or `sync_dir` of anything on the same /// drive, in that order. It needs the file open only to read. pub fn flush_file(file: &File) -> io::Result<()> { timed(|| Ok(rustix::fs::fsync(file)?)) } /// Make durable everything written to the file system `file` is on, of /// every file and directory there, whoever wrote it: one sync (`on_sync`), /// `syncfs`. #[cfg(target_os = "linux")] pub fn sync_filesystem(file: &File) -> io::Result<()> { timed(|| Ok(rustix::fs::syncfs(file)?)) } /// How many syncs this thread has made since this was first asked, on any /// thread: for tests, each of which opens its logs on a thread of its own. #[cfg(test)] pub(crate) fn syncs() -> u64 { use std::cell::Cell; thread_local!(static MADE: Cell = const { Cell::new(0) }); on_sync(|_| MADE.with(|n| n.set(n.get() + 1))); MADE.with(Cell::get) } /// What is told why a compaction in the background failed, if anything is; /// else it is said on standard error. static ON_ERROR: std::sync::OnceLock = std::sync::OnceLock::new(); /// Have `f` told why each compaction in the background failed; the first one set stays. pub fn on_error(f: fn(&str)) { let _ = ON_ERROR.set(f); } /// Say why a compaction in the background failed. pub(crate) fn report(why: &str) { match ON_ERROR.get() { Some(f) => f(why), None => eprintln!("pds: compacting {why}"), } } /// The bytes of a frame's header: its payload's length and check. pub const HEADER: usize = 12; /// The mode of every file the server makes. pub const FILE_MODE: u32 = 0o600; /// The mode of every directory the server makes. pub const DIR_MODE: u32 = 0o700; /// The most room a log's file is given at once: zeros after its frames, for /// the frames after to be written over. pub const AHEAD: u64 = 256 << 10; /// Zeros, to write as room. static ZEROS: [u8; 1 << 16] = [0; 1 << 16]; /// The first byte of a payload of JSON with holes; a JSON array's is `[`. pub const HOLES: u8 = 0x01; /// The bytes of a payload with holes before its table: its kind, its /// text's length and how many holes it has. const HOLED_HEAD: usize = 9; /// A hole's entry in its payload's table: `at`, `start`, `len`. const HOLE: usize = 12; /// The check of a JSON payload: the first 8 bytes of SHA-256 over its /// length and it. fn check(payload: &[u8]) -> [u8; 8] { let mut h = Sha256::new(); h.update((payload.len() as u32).to_le_bytes()); h.update(payload); h.finalize()[..8].try_into().unwrap() } /// The check of a payload with holes: XXH3-64 over its length and it, /// little-endian. fn check_holed(payload: &[u8]) -> [u8; 8] { let mut h = xxhash_rust::xxh3::Xxh3Default::new(); h.update(&(payload.len() as u32).to_le_bytes()); h.update(payload); h.digest().to_le_bytes() } /// Whether a frame, of check `sum` and payload `payload`, is whole: its /// payload is not empty and passes the check its first byte names, or, /// of a kind this version does not know, either. An empty payload, which /// a header of zeros names, is no frame. fn whole(sum: &[u8], payload: &[u8]) -> bool { match payload.first() { None => false, Some(b'[') => sum == check(payload), Some(&HOLES) => sum == check_holed(payload), Some(_) => sum == check(payload) || sum == check_holed(payload), } } /// The entries of a frame, of check `sum` and payload `payload`: `None` if /// it is no whole frame, as a torn tail and room are not; an error if it is /// whole and cannot be read (`text`, `fill`), or its entries do not parse /// as a JSON array. fn entries(sum: &[u8], payload: &[u8]) -> Result>, String> { if !whole(sum, payload) { return Ok(None); } match serde_json::from_slice(&fill(payload)?) { Ok(Json::Array(entries)) => Ok(Some(entries)), Ok(_) => Err("a whole frame whose payload is no JSON array".into()), Err(e) => Err(format!("a whole frame whose entries do not parse: {e}")), } } /// Lowercase hex digits. const DIGITS: &[u8; 16] = b"0123456789abcdef"; /// The JSON text a payload stands for: a JSON payload's is itself; one with /// holes', its text with each hole's bytes put in it in lowercase hex, /// between the quotes of the empty string at its `at`: byte for byte the /// JSON payload of the same entries. An error if the payload is of no kind /// this version reads, or its holes are not as its kind says (`text`). pub fn fill(payload: &[u8]) -> Result, String> { let text = text(payload)?; let json = text.json(); if text.count == 0 { return Ok(json.into()); } let bytes = payload.len() - text.bytes; let mut out = Vec::with_capacity(json.len() + 2 * bytes); let mut from = 0; for (at, b) in text.holes() { out.extend_from_slice(&json[from..at]); for &x in b { out.extend_from_slice(&[DIGITS[usize::from(x >> 4)], DIGITS[usize::from(x & 15)]]); } from = at; } out.extend_from_slice(&json[from..]); Ok(out.into()) } /// A frame's payload, read for its JSON text: of a JSON payload, all of /// it; of one with holes, its text as it is there, each hole an empty /// string, and where each hole's bytes are. pub struct Text<'a> { payload: &'a [u8], /// Where its text is in the payload. json: std::ops::Range, /// Its holes' table, and how many it holds. table: &'a [u8], count: usize, /// Where its holes' bytes start in the payload. bytes: usize, } /// A payload's JSON text and holes, checked to be as its kind says: an /// error if its first byte is of no kind this version reads, or, with /// holes, if its table does not fit it, its holes are not in order of /// `at`, strictly rising, each at the closing quote of an empty string /// that is a value, or their ranges are not in order, touching and /// covering its bytes exactly. pub fn text(payload: &[u8]) -> Result, String> { match payload.first() { Some(b'[') => { return Ok(Text { payload, json: 0..payload.len(), table: &[], count: 0, bytes: payload.len(), }); } Some(&HOLES) => {} Some(&b) => return Err(format!("a frame of a later version: its kind is {b:#04x}")), None => return Err("an empty frame".into()), } let bad = |why: &str| Err(format!("a frame with holes {why}")); let u32_at = |at: usize| u32::from_le_bytes(payload[at..at + 4].try_into().unwrap()) as usize; if payload.len() < HOLED_HEAD { return bad("shorter than its head"); } let (json_len, count) = (u32_at(1), u32_at(5)); let Some(json_at) = count .checked_mul(HOLE) .and_then(|t| t.checked_add(HOLED_HEAD)) .filter(|&at| at <= payload.len()) else { return bad("whose table does not fit it"); }; let Some(bytes) = json_at .checked_add(json_len) .filter(|&end| end <= payload.len()) else { return bad("whose text does not fit it"); }; let text = Text { payload, json: json_at..bytes, table: &payload[HOLED_HEAD..json_at], count, bytes, }; let json = text.json(); let mut empties = Empties { json, i: 0 }; let (mut next, mut last) = (0, None); for i in 0..count { let (at, start, len) = text.entry(i); if last.is_some_and(|l| l >= at) { return bad("out of order"); } last = Some(at); if start != next { return bad("whose ranges do not touch"); } next = match start.checked_add(len) { Some(end) if end <= payload.len() - bytes => end, _ => return bad("past its bytes"), }; if !empties.reach(at) { return bad("not at an empty string"); } } if next != payload.len() - bytes { return bad("whose ranges do not cover its bytes"); } Ok(text) } impl<'a> Text<'a> { /// Its JSON text as the payload holds it: of a payload with holes, each /// hole an empty string. pub fn json(&self) -> &'a [u8] { &self.payload[self.json.clone()] } /// The `i`th entry of its table: `at`, `start`, `len`. fn entry(&self, i: usize) -> (usize, usize, usize) { let e = &self.table[i * HOLE..(i + 1) * HOLE]; let n = |k: usize| u32::from_le_bytes(e[k..k + 4].try_into().unwrap()) as usize; (n(0), n(4), n(8)) } /// Its holes in order: each one's `at`, and its bytes. fn holes(&self) -> impl Iterator + '_ { (0..self.count).map(|i| { let (at, start, len) = self.entry(i); ( at, &self.payload[self.bytes + start..self.bytes + start + len], ) }) } /// The bytes of the hole at `at` of its text, if there is one: borrowed /// from the payload. pub fn hole(&self, at: usize) -> Option<&'a [u8]> { let (mut lo, mut hi) = (0, self.count); while lo < hi { let mid = (lo + hi) / 2; let (a, start, len) = self.entry(mid); match a.cmp(&at) { std::cmp::Ordering::Less => lo = mid + 1, std::cmp::Ordering::Greater => hi = mid, std::cmp::Ordering::Equal => { return Some(&self.payload[self.bytes + start..self.bytes + start + len]); } } } None } } /// The places in a JSON text where a hole may be: the closing quote of /// each empty string that is a value (followed by no `:`), in order. struct Empties<'a> { json: &'a [u8], /// Where to go on from, outside every string. i: usize, } impl Empties<'_> { /// Go on to `at`: whether it is such a place. fn reach(&mut self, at: usize) -> bool { while self.i < self.json.len() && self.i <= at { if self.json[self.i] != b'"' { self.i += 1; continue; } // A string: on to its closing quote, past every escape. let open = self.i; let mut j = open + 1; while j < self.json.len() && self.json[j] != b'"' { j += if self.json[j] == b'\\' { 2 } else { 1 }; } self.i = j + 1; if j == at { let after = self.json[self.i.min(self.json.len())..] .iter() .find(|b| !b.is_ascii_whitespace()); return j == open + 1 && after != Some(&b':'); } } false } } /// A payload with holes being written (`frame_with_holes`): JSON text, /// written to it as to any writer (`io::Write` for `&Holed`), and bytes /// handed to it, each for an empty string just written. pub struct Holed<'a> { out: std::cell::RefCell>, holes: std::cell::RefCell>, } impl<'a> Holed<'a> { /// Have the empty string just written, `""`, a value, stand for /// `bytes`: the frame holds them as they are, after its text. pub fn hole(&self, bytes: &'a [u8]) { let out = self.out.borrow(); assert!( out.ends_with(b"\"\""), "a hole is an empty string just written" ); self.holes.borrow_mut().push((out.len() - 1, bytes)); } } impl Write for &Holed<'_> { fn write(&mut self, buf: &[u8]) -> io::Result { self.out.borrow_mut().extend_from_slice(buf); Ok(buf.len()) } fn flush(&mut self) -> io::Result<()> { Ok(()) } } /// A frame of entries all small JSON: a JSON payload. pub fn frame(entries: &[Json]) -> Vec { frame_of(0, |out| { serde_json::to_writer(out, entries).expect("entries serialize") }) } /// The frame of the JSON payload `write` writes, a JSON array of entries, /// with room for about `capacity` bytes of it made at once: written in /// place, never copied. pub fn frame_of(capacity: usize, write: impl FnOnce(&mut Vec)) -> Vec { let mut out = Vec::with_capacity(HEADER + capacity); out.resize(HEADER, 0); write(&mut out); framed(out, check) } /// The frame of a payload with holes: `write` writes its JSON text, the /// array of entries, to the `Holed` it is given, and hands it bytes /// (`Holed::hole`), with room for about `capacity` bytes of text made at /// once. The text is written in place; the bytes are copied once, after /// it. Its last byte is never zero, as a JSON array's `]` is not /// (`log_len`): while its bytes would end with one, the holes from the /// last with bytes on are written in its text as hex instead, as a JSON /// payload has them. pub fn frame_with_holes<'a>(capacity: usize, write: impl FnOnce(&Holed<'a>)) -> Vec { let start = HEADER + HOLED_HEAD; let mut out = Vec::with_capacity(start + capacity); out.resize(start, 0); let w = Holed { out: out.into(), holes: Vec::new().into(), }; write(&w); let (mut out, mut holes) = (w.out.into_inner(), w.holes.into_inner()); while let Some(i) = holes.iter().rposition(|(_, b)| !b.is_empty()) && holes[i].1.last() == Some(&0) { for (at, b) in holes.drain(i..).rev() { let hex = b .iter() .flat_map(|&x| [DIGITS[usize::from(x >> 4)], DIGITS[usize::from(x & 15)]]); out.splice(at..at, hex); } } let json_len = out.len() - start; let table = holes.len() * HOLE; let bytes: usize = holes.iter().map(|(_, b)| b.len()).sum(); out.reserve_exact(table + bytes); out.resize(out.len() + table, 0); out.copy_within(start..start + json_len, start + table); let mut from = 0; for (i, (at, b)) in holes.iter().enumerate() { let e = start + i * HOLE; for (k, n) in [at - start, from, b.len()].into_iter().enumerate() { out[e + 4 * k..e + 4 * k + 4].copy_from_slice(&(n as u32).to_le_bytes()); } from += b.len(); } for (_, b) in &holes { out.extend_from_slice(b); } out[HEADER] = HOLES; out[HEADER + 1..HEADER + 5].copy_from_slice(&(json_len as u32).to_le_bytes()); out[HEADER + 5..start].copy_from_slice(&(holes.len() as u32).to_le_bytes()); debug_assert!( text(&out[HEADER..]).is_ok(), "a payload with holes as its kind says" ); framed(out, check_holed) } /// `out`, a payload after a header's room, with its header filled in: its /// length and its check, by `check`. fn framed(mut out: Vec, check: fn(&[u8]) -> [u8; 8]) -> Vec { let len = (out.len() - HEADER) as u32; let sum = check(&out[HEADER..]); out[..4].copy_from_slice(&len.to_le_bytes()); out[4..HEADER].copy_from_slice(&sum); out } /// The entries of every whole frame at the start of `data`, and where they /// end; an error if a whole frame there cannot be read (the module's /// "Replay"), which nothing is to cut. pub fn scan(data: &[u8]) -> Result<(Vec>, usize), String> { let mut frames = Vec::new(); let pos = scan_each(data, |_, entries| { frames.push(entries); Ok(()) })?; Ok((frames, pos)) } /// Give `f` each whole frame at the start of `data`, with its offset, one /// at a time, so that no more than one is parsed at once: where they end, /// or the first error `f` answers, or that a whole frame cannot be read. pub fn scan_each( data: &[u8], mut f: impl FnMut(usize, Vec) -> Result<(), String>, ) -> Result { let mut pos = 0; while data.len() - pos >= HEADER { let len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize; let end = pos + HEADER + len; if end > data.len() { break; } let read = entries(&data[pos + 4..pos + HEADER], &data[pos + HEADER..end]); let Some(entries) = read.map_err(|why| format!("the frame at {pos}: {why}"))? else { break; }; f(pos, entries)?; pos = end; } Ok(pos) } /// Where a frame is: its log's generation, its offset in the file, and its /// length, header and all. #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] pub struct Pos { pub generation: u64, pub offset: u64, pub len: u64, } /// What `scan_log` found of a file. pub(crate) struct Scanned { /// The bytes of its whole frames. pub whole: u64, /// Where what it holds ends: `whole`, or past it, with part of a frame. pub held: u64, /// Its size, room and all. pub size: u64, } /// Read the file at `path` frame by frame, giving `f` each whole frame's /// offset, length and entries, one at a time, up to the first place that /// holds no whole frame: answers the bytes of whole frames and where what /// the file holds ends, which is its size less the room at its end, the /// zeros after its last frame; or `f`'s first error, or that a whole frame /// cannot be read (the module's "Replay"), as `Ok(Err(why))`. The two /// differ where part of a frame follows the last whole one. A read that /// fails is the error, not the end of what the file holds. pub fn scan_file( path: &Path, f: impl FnMut(u64, u64, Vec) -> Result<(), String>, ) -> io::Result> { Ok(scan_log(path, f)?.map(|s| (s.whole, s.held))) } // Make a read of a log's bytes at `at` and after fail, on this thread, // for a test of what a replay does then. #[cfg(test)] thread_local!(static READ_FAILS: std::cell::Cell> = const { std::cell::Cell::new(None) }); /// Whether a read at `at` is to fail, as a test has it (`READ_FAILS`). fn read_fails(at: u64) -> io::Result<()> { #[cfg(test)] if READ_FAILS.get().is_some_and(|from| at >= from) { return Err(io::Error::other("a read failed")); } let _ = at; Ok(()) } /// The same, answering the file's size too. pub(crate) fn scan_log( path: &Path, mut f: impl FnMut(u64, u64, Vec) -> Result<(), String>, ) -> io::Result> { use std::io::Read; let file = File::open(path)?; let size = file.metadata()?.len(); let mut r = io::BufReader::with_capacity(1 << 16, &file); let mut pos = 0u64; let mut payload = Vec::new(); loop { let mut head = [0u8; HEADER]; if size - pos < HEADER as u64 { break; } read_fails(pos)?; r.read_exact(&mut head)?; let len = u32::from_le_bytes(head[..4].try_into().unwrap()) as u64; if size - pos - (HEADER as u64) < len { break; } payload.clear(); payload.resize(len as usize, 0); read_fails(pos + HEADER as u64)?; r.read_exact(&mut payload)?; let entries = match entries(&head[4..], &payload) { Ok(Some(entries)) => entries, Ok(None) => break, Err(why) => { return Ok(Err(format!( "{}: the frame at {pos}: {why}", path.display() ))); } }; if let Err(why) = f(pos, HEADER as u64 + len, entries) { return Ok(Err(why)); } pos += HEADER as u64 + len; } Ok(Ok(Scanned { whole: pos, held: held(&file, pos, size)?, size, })) } /// Where what `file`, of `size` bytes, holds ends, at or after `from`: its /// size, less the zeros it ends with. Read from its end, a block at a time. fn held(file: &File, from: u64, size: u64) -> io::Result { let mut block = [0u8; 4096]; let mut end = size; while end > from { let n = (end - from).min(block.len() as u64) as usize; let at = end - n as u64; file.read_exact_at(&mut block[..n], at)?; if let Some(last) = block[..n].iter().rposition(|&b| b != 0) { return Ok(at + last as u64 + 1); } end = at; } Ok(from) } /// The bytes of `rest`, what follows the last whole frame of a log read /// whole, that are not room: all but the zeros it ends with. fn torn(rest: &[u8]) -> usize { rest.iter() .rposition(|&b| b != 0) .map_or(0, |last| last + 1) } /// The bytes the log file at `path` holds: its size, less the room at its /// end. Found from its end, with no frame read: room is zeros, and a frame /// ends with its payload's last byte, never zero: a JSON array's `]`, or of /// a payload with holes, a byte its writer kept from being zero /// (`frame_with_holes`). A file that ends in part of a frame holds that /// part too, until a start cuts it off. pub fn log_len(path: &Path) -> io::Result { let file = File::open(path)?; held(&file, 0, file.metadata()?.len()) } /// Read the frame at `offset` of the file at `path`, `len` bytes long: its /// entries, or an error if it is not there whole, or cannot be read. pub fn read_frame(path: &Path, offset: u64, len: u64) -> io::Result> { let mut buf = vec![0u8; len as usize]; File::open(path)?.read_exact_at(&mut buf, offset)?; let at = |why: &str| { io::Error::new( io::ErrorKind::InvalidData, format!("{}: the frame at {offset}: {why}", path.display()), ) }; one(&buf) .map_err(|why| at(&why))? .ok_or_else(|| at("not whole")) } /// A frame's payload, as it is in the frame, if the frame is whole and of /// a kind this version reads, its holes as its kind says (`text`). pub fn payload(mut bytes: Vec) -> Option> { let payload = sized(&bytes)?; if !whole(&bytes[4..HEADER], payload) || text(payload).is_err() { return None; } bytes.drain(..HEADER); Some(bytes) } /// One frame's entries, if it is whole and can be read. pub fn parse_frame(bytes: &[u8]) -> Option> { one(bytes).ok().flatten() } /// One frame's entries: `None` if it is not whole, an error if it is but /// cannot be read. fn one(bytes: &[u8]) -> Result>, String> { match sized(bytes) { Some(payload) => entries(&bytes[4..HEADER], payload), None => Ok(None), } } /// The payload of `bytes`, if they are one frame's length, header and all. fn sized(bytes: &[u8]) -> Option<&[u8]> { let len = u32::from_le_bytes(bytes.get(..4)?.try_into().unwrap()) as usize; (bytes.len() == HEADER + len).then(|| &bytes[HEADER..]) } /// Make a directory's entries durable: one sync (`on_sync`). pub fn sync_dir(dir: &Path) -> io::Result<()> { timed(|| File::open(dir)?.sync_all()) } /// Make `dir` and every directory above it that is missing, each `0700`; /// answers those it made, outermost first. pub fn make_dirs(dir: &Path) -> io::Result> { let mut made = Vec::new(); let mut d = Some(dir); while let Some(x) = d.filter(|x| !x.as_os_str().is_empty() && !x.exists()) { made.push(x.to_path_buf()); d = x.parent(); } made.reverse(); for x in &made { match std::fs::DirBuilder::new().mode(DIR_MODE).create(x) { Ok(()) => std::fs::set_permissions(x, Permissions::from_mode(DIR_MODE))?, Err(e) if e.kind() == io::ErrorKind::AlreadyExists => {} Err(e) => return Err(e), } } Ok(made) } /// Open a file with `opts`, created `0600` if it is created, and made so /// whatever the umask. pub fn open_private(path: &Path, opts: &mut OpenOptions) -> io::Result { let f = opts.mode(FILE_MODE).open(path)?; f.set_permissions(Permissions::from_mode(FILE_MODE))?; Ok(f) } /// Held, alone, while a child process is spawned (`spawning`), and shared /// by each log's file as it is opened. static SPAWNING: RwLock<()> = RwLock::new(()); /// What a process holds while it spawns a child, from before the child is /// made until it has execed, as when `std::process::Command::spawn` /// returns: no log's file is opened meanwhile. Until it execs the child /// holds a copy of every file its parent has open, and with a log's file /// its lock, though the parent has closed it since: opened again then, the /// log would be found held by another handle. pub fn spawning() -> RwLockWriteGuard<'static, ()> { SPAWNING.write().unwrap_or_else(PoisonError::into_inner) } /// How long a log's file found locked is tried again before it is taken as /// held by another handle. const LOCK_WAIT: Duration = Duration::from_millis(100); /// Open a log's file to write to, `0600`, and lock it: an error naming it /// if another handle holds it so, before anything of it is changed. A file /// found locked is tried again for `LOCK_WAIT` first: a child process on /// its way to exec holds its copy of the file, and the lock with it, until /// the exec closes it, which on Linux may be a moment after its parent's /// spawn has returned and `spawning` is let go. fn open_locked(path: &Path, opts: &mut OpenOptions) -> io::Result { use rustix::fs::{FlockOperation, flock}; let _none_spawning = SPAWNING.read().unwrap_or_else(PoisonError::into_inner); let f = opts.mode(FILE_MODE).open(path)?; let tried = Instant::now(); loop { match flock(&f, FlockOperation::NonBlockingLockExclusive) { Ok(()) => break, Err(rustix::io::Errno::WOULDBLOCK) if tried.elapsed() < LOCK_WAIT => { std::thread::sleep(Duration::from_millis(1)); } Err(rustix::io::Errno::WOULDBLOCK) => return Err(busy(path)), Err(e) => return Err(e.into()), } } f.set_permissions(Permissions::from_mode(FILE_MODE))?; Ok(f) } /// The error of a log file another handle holds open to write to. fn busy(path: &Path) -> io::Error { io::Error::new( io::ErrorKind::ResourceBusy, format!( "{}: another handle holds it open to write to", path.display() ), ) } /// A log file at `path`, empty, `0600`, locked, open to write frames to. fn create_log(path: &Path) -> io::Result { let f = open_locked(path, OpenOptions::new().create(true).write(true).read(true))?; f.set_len(0)?; Ok(f) } fn lock(m: &Mutex) -> MutexGuard<'_, T> { m.lock().unwrap_or_else(PoisonError::into_inner) } /// A pool of logs, of which at most `max` are open at once, and the /// journal they are written to as well, if they are (`journal`). pub struct Files { max: usize, /// The logs open, by when each was last used: a log's key is its /// `used`, and both change only under this lock. open: Mutex>>, tick: AtomicU64, /// Whether its logs take no more frames (`close`). closed: AtomicBool, /// The journal every log of the pool writes its frames to too, and /// waits on in place of a sync of its own file; none to sync each. journal: Option>, } /// The logs `Files::make_room` first tries to close, the least recently /// used: every one after them only if each of these is in use. const OLDEST: usize = 8; impl Files { /// A pool whose logs are each synced by itself. pub fn new(max: usize) -> Arc { Files::with(max, None) } /// A pool whose logs are written to `journal` too, and wait on it. pub fn with_journal(max: usize, journal: Arc) -> Arc { Files::with(max, Some(journal)) } fn with(max: usize, journal: Option>) -> Arc { Arc::new(Files { max: max.max(1), open: Mutex::new(BTreeMap::new()), tick: AtomicU64::new(1), closed: AtomicBool::new(false), journal, }) } /// The journal its logs are written to, if they are. pub fn journal(&self) -> Option<&Arc> { self.journal.as_ref() } /// Close every log of the pool, those opened after this too: an append /// to one, a compaction's start and a rewrite are refused from now on. /// A frame being appended as this is called may still land: `Wal::close` /// of its log then makes it durable. A log is opened as one of the /// pool's all the same, and mends what it finds, which is a write of /// its own: whoever closes a pool to leave its logs' files as they are /// opens none after (`is_closed`). pub fn close(&self) { self.closed.store(true, Ordering::SeqCst); } /// Whether the pool is closed. pub fn is_closed(&self) -> bool { self.closed.load(Ordering::SeqCst) } /// How many of its logs are open. pub fn open_count(&self) -> usize { lock(&self.open) .values() .filter(|w| w.strong_count() > 0) .count() } fn touch(&self, me: &Arc) { let t = self.tick.fetch_add(1, Ordering::Relaxed); let mut open = lock(&self.open); if let Some(w) = open.remove(&me.used.load(Ordering::Relaxed)) { open.insert(t, w); me.used.store(t, Ordering::Relaxed); } } /// Hold a place for `me`, which holds its own lock and has no file open, /// closing the least recently used log not in use to make room; waits /// for one if every log is in use. A log is in use while its lock is /// held, and while anything else holds its file: a sync of it in /// flight (`Shared::sync_written`), which holds no lock of the log's. /// The file's lock is the open file's, and stays with whatever holds /// it open: were the log's own hold dropped then, its next append /// would open the file again and find it locked. fn make_room(&self, me: &Arc) { let mut tried = OLDEST; loop { let victims: Vec> = { let mut open = lock(&self.open); open.remove(&me.used.swap(0, Ordering::Relaxed)); if open.len() < self.max { let t = self.tick.fetch_add(1, Ordering::Relaxed); open.insert(t, Arc::downgrade(me)); me.used.store(t, Ordering::Relaxed); return; } open.values().take(tried).cloned().collect() }; let all = victims.len() < tried; let closed = victims.into_iter().filter_map(|w| w.upgrade()).any(|v| { let mut inner = match v.inner.try_lock() { Ok(g) => g, Err(TryLockError::Poisoned(p)) => p.into_inner(), Err(TryLockError::WouldBlock) => return false, }; // Under its lock nothing else takes hold of its file, and // one held elsewhere is left as it is, room and all. if inner .file .as_ref() .is_some_and(|f| Arc::strong_count(f) > 1) { return false; } // Its place is given up under its own lock, so that it cannot // take another meanwhile; and its room, which a log not in // use has no use for. Its file's lock goes with the file, // which closes here: nothing else holds it. inner.give_back(); inner.found = inner .file .take() .and_then(|f| f.metadata().ok()) .map(|m| m.len()); self.forget(&v); true }); if !closed { if all { std::thread::sleep(std::time::Duration::from_millis(1)); } tried = usize::MAX; } } } fn forget(&self, me: &Shared) { let mut open = lock(&self.open); open.remove(&me.used.swap(0, Ordering::Relaxed)); } } struct Inner { /// The current log's file, while it is open; shared with an fsync in progress. file: Option>, /// The current log's path: that of its generation. path: PathBuf, /// The bytes of whole frames in the file: where the log ends, and the /// next frame goes. len: u64, /// The file's size: `len`, and the room after it. size: u64, /// The bytes of frames written to the file since it was made, opened or /// closed, or its room last given back: as much room is made at once. since: u64, /// Whether an append failed and the file may still hold part of it. torn: bool, /// The file's size as it was last found, when its pool closed it, if it /// could be told, or when the log was opened with no file held /// (`generations`): it is opened again only if it is that still. found: Option, /// Whether the log's files are let go (`Wal::close`, or the `Wal` /// dropped): it opens no file again. shut: bool, /// The current log's generation, and when it began: `began` in this /// process, less `before`, how long it had run already when this /// process opened the log, as its files tell (`generations`). generation: u64, began: Instant, before: Duration, /// The bytes of the sealed logs from the checkpoint's generation on. sealed: u64, /// The checkpoint's generation (`0` with none), and its bytes. checkpoint: u64, checkpoint_bytes: u64, /// Sealed logs not yet made durable with the directory, which holds the /// logs after them: each one's generation and file. unsynced: Vec<(u64, Arc)>, /// What makes the log's checkpoints; no compaction without it. fold: Option>, /// Whether a compaction of the log runs. compacting: bool, /// After a compaction failed, none is made due before this. quiet_until: Option, /// Whether it takes no more frames (`Wal::close`). closed: bool, /// The number of the journal's record of its last frame, if it has a /// journal: a wait waits for the journal to reach it. journaled: u64, /// Whether a cut of the file fails, as a test has it. #[cfg(test)] cut_fails: bool, } impl Inner { fn new(path: PathBuf, len: u64) -> Inner { Inner { file: None, path, len, size: len, since: 0, torn: false, found: None, shut: false, generation: 0, began: Instant::now(), before: Duration::ZERO, sealed: 0, checkpoint: 0, checkpoint_bytes: 0, unsynced: Vec::new(), fold: None, compacting: false, quiet_until: None, closed: false, journaled: 0, #[cfg(test)] cut_fails: false, } } /// Write a frame where the last ended, over room or past the file's /// end; and where that grows the file, give it room after the frame: /// as much as the frames written to it since it was opened, this one /// among them, `AHEAD` at most and `most` at most. fn put(&mut self, file: &File, frame: &[u8], most: u64) -> io::Result<()> { file.write_all_at(frame, self.len)?; self.len += frame.len() as u64; self.since += frame.len() as u64; if self.len > self.size { self.size = self.len + room(file, self.len, self.since.min(AHEAD).min(most)); } Ok(()) } /// Cut the file back to its whole frames, its room with them. fn cut(&mut self, file: &File) -> io::Result<()> { #[cfg(test)] if self.cut_fails { return Err(io::Error::other("a cut failed")); } file.set_len(self.len)?; self.size = self.len; self.since = 0; self.torn = false; Ok(()) } /// Give back the file's room, cutting it to its frames, and count the /// next frame as its first: as the log's file is closed, before its /// seal is written, and when it is asked. Part of a frame an append /// left goes with it, if it can be cut now. Room that cannot be given /// back stays until the log is opened. fn give_back(&mut self) { if let Some(file) = self.file.clone() { if self.torn { let _ = self.cut(&file); } else if self.size > self.len && file.set_len(self.len).is_ok() { self.size = self.len; } } self.since = 0; } } /// The logs of this run whose cut back of a frame an append wrote but did /// not take never succeeded, each with the length to cut it to: the next /// open of one in the run cuts it first, and does not take it as at rest. static UNCUT: Mutex> = Mutex::new(BTreeMap::new()); /// Cut the log at `path` back as an append of this run could not, if one /// could not (`UNCUT`): whether it was. It stays noted until `cut_noted`. fn cut_uncut(path: &Path) -> io::Result { let Some(len) = lock(&UNCUT).get(path).copied() else { return Ok(false); }; open_locked(path, OpenOptions::new().write(true))?.set_len(len)?; Ok(true) } /// Note that the log at `path`, cut back by `cut_uncut`, is durable so. fn cut_noted(path: &Path) { lock(&UNCUT).remove(path); } /// Give `file`, which ends at `end`, `n` bytes of room: zeros written past /// its end. Answers the room it has then: `n`, or none where a write failed, /// with the file cut back to `end` if it can be. Zeros left past `end` all /// the same are written over or cut off as any room is. fn room(file: &File, end: u64, n: u64) -> u64 { let mut done = 0; while done < n { let k = (n - done).min(ZEROS.len() as u64) as usize; if file.write_all_at(&ZEROS[..k], end + done).is_err() { let _ = file.set_len(end); return 0; } done += k as u64; } n } struct Shared { pool: Option>, /// When the log was last used, as its pool counts: its key among the /// pool's open logs, 0 while it has no place there. used: AtomicU64, /// The directory the log's files are in. dir: PathBuf, /// Its files, for a log with generations; `None` for one file (`Wal::open`). layout: Option, policy: Policy, /// The log's lock, held through each append, so that frames go in whole /// and in order. inner: Mutex, /// Signalled, with `inner`, when a compaction ends. compacted: Condvar, /// Frames handed to the operating system. written: AtomicU64, /// The syncs of written frames, one at a time; the lock is let go /// through each, and held only to begin one, to end one and to wait. synced: Mutex, /// Signalled, with `synced`, when a sync ends. sync_ended: Condvar, /// Frames known to be on disk. durable: AtomicU64, /// The bytes recovery cut off when the log was opened: a torn tail, and /// of a log with generations, the logs after one cut short or unsealed. dropped: u64, /// Files outside the log that frames given since rest on, as a blob a /// commit references: each synced, with its directory, before the log /// next is, so that a frame on disk never has one that is not. sync_first: Mutex>, /// The journal its frames are written to too, and its waits wait on in /// place of a sync of its own file: its pool's, or one given it /// (`Wal::use_journal`); none to sync its file by itself. journal: std::sync::OnceLock>, /// The fsyncs of logs and the directory made through the log, in order. #[cfg(test)] trace: Mutex>, /// Called as the files `sync_first` was given are synced: it may hold /// that, or fail it. #[cfg(test)] files_first: Mutex>, } /// The syncs of a log's written frames. #[derive(Default)] struct Syncs { /// Whether one is going on, and how many have begun. going: bool, begun: u64, /// The last that failed. failed: Option, } /// A sync that failed: which it was, the frames it would have covered /// (every one up to this number), and why. struct Failed { sync: u64, covered: u64, kind: io::ErrorKind, why: String, } /// A sync going on, ended when this is dropped: noted if it failed, and /// every waiter woken. struct Ending<'a> { synced: &'a Mutex, ended: &'a Condvar, sync: u64, covered: u64, failed: Option<(io::ErrorKind, String)>, } impl Drop for Ending<'_> { fn drop(&mut self) { let mut syncs = lock(self.synced); syncs.going = false; if let Some((kind, why)) = self.failed.take() { syncs.failed = Some(Failed { sync: self.sync, covered: self.covered, kind, why, }); } drop(syncs); self.ended.notify_all(); } } /// Return once `durable` has reached `seq`, sharing syncs with every /// other waiter on the same `synced`: one of them makes a sync with /// `sync`, which tells `covered` how far it reaches as soon as that is /// known, and each it covers is answered when it ends, as it ended; one it /// does not cover waits for the next, or makes it. A sync that fails is the /// answer to each waiter it would have covered. fn wait_shared( synced: &Mutex, ended: &Condvar, durable: &AtomicU64, seq: u64, sync: impl FnOnce(&mut u64) -> io::Result<()>, ) -> io::Result<()> { let mut syncs = lock(synced); loop { if durable.load(Ordering::SeqCst) >= seq { return Ok(()); } if !syncs.going { break; } let following = syncs.begun; syncs = ended.wait(syncs).unwrap_or_else(PoisonError::into_inner); if let Some(failed) = syncs.failed.as_ref().filter(|f| f.sync == following) && seq <= failed.covered && durable.load(Ordering::SeqCst) < seq { return Err(io::Error::new(failed.kind, failed.why.clone())); } } syncs.going = true; syncs.begun += 1; // Ended, and those waiting on it woken, however this returns. let mut ending = Ending { synced, ended, sync: syncs.begun, covered: 0, failed: None, }; drop(syncs); let synced = sync(&mut ending.covered); if let Err(e) = &synced { ending.failed = Some((e.kind(), e.to_string())); } synced } /// A log dropped gives up its place in the pool. impl Drop for Shared { fn drop(&mut self) { if let Some(p) = &self.pool { p.forget(self); } } } impl Shared { fn new( dir: PathBuf, layout: Option, pool: Option>, policy: Policy, inner: Inner, dropped: u64, ) -> Arc { let journal = std::sync::OnceLock::new(); if let Some(j) = pool.as_ref().and_then(|p| p.journal.clone()) { let _ = journal.set(j); } Arc::new(Shared { pool, used: AtomicU64::new(0), dir, layout, policy, inner: Mutex::new(inner), compacted: Condvar::new(), written: AtomicU64::new(0), synced: Mutex::new(Syncs::default()), sync_ended: Condvar::new(), durable: AtomicU64::new(0), dropped, sync_first: Mutex::new(Vec::new()), journal, #[cfg(test)] trace: Mutex::new(Vec::new()), #[cfg(test)] files_first: Mutex::new(None), }) } /// Whether the log takes no more frames: it was closed, or its pool was. fn closed(&self, inner: &Inner) -> bool { inner.closed || self .pool .as_ref() .is_some_and(|p| p.closed.load(Ordering::SeqCst)) } /// What an append, a compaction's start or a rewrite of a closed log is /// answered. fn refused(&self, inner: &Inner) -> io::Error { io::Error::other(format!("{}: the log is closed", inner.path.display())) } /// The file, opened if it is not, with a place in the pool: locked, and /// an error if it is not the size it was last found. fn file(self: &Arc, inner: &mut Inner) -> io::Result> { if let Some(f) = &inner.file { if let Some(p) = &self.pool { p.touch(self); } return Ok(f.clone()); } if inner.shut { return Err(self.refused(inner)); } let found = inner.found; let file = self.place(inner, |path| { let f = open_locked(path, OpenOptions::new().write(true).read(true))?; if let Some(size) = found && f.metadata()?.len() != size { return Err(io::Error::new( io::ErrorKind::InvalidData, format!( "{}: changed by another handle since this one last read it", path.display() ), )); } Ok(f) })?; inner.found = None; Ok(file) } /// Make the current log, empty, with a place in the pool. fn create(self: &Arc, inner: &mut Inner) -> io::Result> { self.place(inner, create_log) } fn place( self: &Arc, inner: &mut Inner, open: impl FnOnce(&Path) -> io::Result, ) -> io::Result> { if let Some(p) = &self.pool { p.make_room(self); } match open(&inner.path) { Ok(f) => { let f = Arc::new(f); inner.file = Some(f.clone()); Ok(f) } Err(e) => { if let Some(p) = &self.pool { p.forget(self); } Err(e) } } } /// Cut the file back to its whole frames, if an append left part of /// one: its room goes with it. fn mend(self: &Arc, inner: &mut Inner) -> io::Result<()> { if inner.torn { let file = self.file(inner)?; inner.cut(&file)?; } Ok(()) } /// Cut back a frame an append wrote and did not take. A log whose cut /// fails takes no frame from then on, as a closed one, its cut tried /// again as it is let go: else a frame no append took could stay in /// the file, and be read as one of its frames. fn cut_back(self: &Arc, inner: &mut Inner) { inner.torn = true; if self.mend(inner).is_err() { inner.closed = true; } } /// Make sealed logs durable, and the directory, which holds the logs /// after them. fn sync_sealed(&self, logs: &[(u64, Arc)]) -> io::Result<()> { if logs.is_empty() { return Ok(()); } for (g, f) in logs { sync_data(f)?; self.note(|| format!("log {g}")); } sync_dir(&self.dir)?; self.note(|| "dir".into()); Ok(()) } /// Sync the files `Wal::sync_first` was given, then their directories, /// each once; a file gone since (a blob no longer held) needs none. Those /// not synced are kept for the next try. Before any log is synced, sealed /// or current, so that a frame on disk never rests on a file that is not; /// with a journal, before the frame is written (`Wal::append`). fn sync_files_first(&self) -> io::Result<()> { let paths = std::mem::take(&mut *lock(&self.sync_first)); if paths.is_empty() { return Ok(()); } let synced = (|| { #[cfg(test)] { let hook = lock(&self.files_first).clone(); if let Some(hook) = hook { hook()?; } } let mut dirs = std::collections::BTreeSet::new(); for p in &paths { match File::open(p) { Ok(f) => sync_file(&f)?, Err(e) if e.kind() == io::ErrorKind::NotFound => continue, Err(e) => return Err(e), } dirs.insert( p.parent() .filter(|d| !d.as_os_str().is_empty()) .unwrap_or(Path::new(".")) .to_path_buf(), ); } dirs.iter().try_for_each(|d| sync_dir(d)) })(); if synced.is_err() { lock(&self.sync_first).extend(paths); } synced } /// Make every frame written so far durable, with every file they rest /// on: `covered` is told how many frames that is, as soon as it is known. /// With a journal, the journal is made durable up to the record of the /// last of them, in place of a sync of the log's own file. fn sync_written(self: &Arc, covered: &mut u64) -> io::Result<()> { let journal = self.journal.get(); // Every frame up to `target` is in this file, in a sealed log not yet // durable, or in one a rewrite or a sync before made durable; and, // with a journal, in a record of it up to `journaled`. let (file, sealed, generation, journaled) = { let mut inner = lock(&self.inner); *covered = self.written.load(Ordering::SeqCst); let file = match journal { Some(_) => None, None => Some(self.file(&mut inner)?), }; ( file, inner.unsynced.clone(), inner.generation, inner.journaled, ) }; let target = *covered; // Taken after `target`: every file given before a frame up to it. self.sync_files_first()?; // No frame of a generation is durable before the logs before it are, // sealed, and the directory with it in: else a power cut could leave // them unsealed, and it would be dropped at start. self.sync_sealed(&sealed)?; if !sealed.is_empty() { lock(&self.inner) .unsynced .retain(|(g, _)| !sealed.iter().any(|(h, _)| h == g)); } match (journal, file) { (Some(j), _) => { j.wait(journaled)?; self.note(|| format!("journal {journaled}")); } (None, file) => { // Opened under the lock above, where there is no journal. if let Some(file) = file { sync_data(&file)?; } self.note(|| format!("current {generation}")); } } self.durable.fetch_max(target, Ordering::SeqCst); Ok(()) } /// Note an fsync, for tests to check their order. fn note(&self, what: impl FnOnce() -> String) { #[cfg(test)] lock(&self.trace).push(what()); #[cfg(not(test))] let _ = what; } } pub struct Wal(Arc); impl Drop for Wal { /// A log let go gives back its room and holds none of its files open, /// and so none of their locks, though a compaction of it is yet to /// return: that holds a sealed log's file only while it syncs it. fn drop(&mut self) { self.let_go(); } } impl Wal { /// Read the log at `path` (creating it, and the directories it is in, if /// need be), cut off what follows its last whole frame, a torn tail or /// room, and return the intact frames with the log ready for appending. /// Given `pool`, it is one of the pool's. It has no generations, and is /// never compacted. pub fn open(path: &Path, pool: Option>) -> io::Result<(Wal, Vec>)> { let dir = path .parent() .filter(|d| !d.as_os_str().is_empty()) .unwrap_or(Path::new(".")); let made = make_dirs(dir)?; let existed = path.exists(); // A frame an append of this run could not cut back, cut now. let cut = existed && cut_uncut(path)?; let data = if existed { std::fs::read(path)? } else { vec![] }; let (frames, good) = scan(&data).map_err(|why| { io::Error::new( io::ErrorKind::InvalidData, format!("{}: {why}", path.display()), ) })?; let shared = Shared::new( dir.to_path_buf(), None, pool, Policy::default(), Inner::new(path.to_path_buf(), good as u64), torn(&data[good..]) as u64, ); { let mut inner = lock(&shared.inner); let file = if existed { shared.file(&mut inner)? } else { shared.create(&mut inner)? }; if good < data.len() { file.set_len(good as u64)?; } sync_file(&file)?; } if !existed { sync_dir(dir)?; } for x in made.iter() { if let Some(parent) = x.parent().filter(|p| !p.as_os_str().is_empty()) { sync_dir(parent)?; } } if cut { cut_noted(path); } Ok((Wal(shared), frames)) } /// Hand a frame to the operating system; answers its number, to `wait` /// for. A frame that cannot be written whole is cut back from the file, /// and the log goes on as if it had not been given; so is one whose /// record its journal, if it has one, did not take. With a journal, the /// files `sync_first` was given are synced before the frame is written, /// and the append fails if they cannot be: else the journal's next sync, /// any log's, or a checkpoint's flush of the log could put the frame on /// disk before them. A log with a fold set may then start compacting /// (`generations`). pub fn append(&self, entries: &[Json]) -> io::Result { self.append_at(entries).map(|(n, _)| n) } /// The same, answering too where the frame went. pub fn append_at(&self, entries: &[Json]) -> io::Result<(u64, Pos)> { self.append_frame_at(&frame(entries)) } /// The same, of a frame made already (`frame_of`). pub fn append_frame_at(&self, bytes: &[u8]) -> io::Result<(u64, Pos)> { let s = &self.0; let mut inner = lock(&s.inner); if s.closed(&inner) { return Err(s.refused(&inner)); } s.mend(&mut inner)?; if s.journal.get().is_some() { s.sync_files_first()?; } let file = s.file(&mut inner)?; let offset = inner.len; // With a journal no sync of the log's own file answers a frame: // room would buy it nothing. let most = match s.journal.get() { Some(_) => 0, None => s.left(&inner, bytes.len() as u64), }; if let Err(e) = inner.put(&file, bytes, most) { s.cut_back(&mut inner); return Err(e); } if let Some(j) = s.journal.get() { match j.append(&inner.path, offset, bytes) { Ok(n) => inner.journaled = n, Err(e) => { // No frame stays in the file with no record of it. inner.len = offset; s.cut_back(&mut inner); return Err(e); } } } let pos = Pos { generation: inner.generation, offset, len: bytes.len() as u64, }; let n = s.written.fetch_add(1, Ordering::SeqCst) + 1; let failed = s.trigger(&mut inner); drop(inner); if let Some(why) = failed { report(&why); } Ok((n, pos)) } /// Close the log. It takes no more frames: an append, a compaction's /// start and a rewrite are refused from now on. Its room is given /// back, and every frame it took is made durable, with the files they /// rest on, each sealed log and the directory, as a group commit does: /// once this answers, every frame the log's files hold is on disk. /// Then its files are let go, their locks with them, and it makes no /// sync after. A compaction under way makes no `.tmp`, puts no /// checkpoint in place and deletes nothing from then on, each of which /// it does only under the log's lock with the files not let go /// (`generations`): it ends where it was, a `.tmp` it had made left, /// and leaves the files as a kill at one of its steps would, which the /// next to open them mends. /// Answers the sync's error, the files let go all the same. For a /// shutdown, and for what ends a log's writing while something still /// holds it. pub fn close(&self) -> io::Result<()> { let s = &self.0; // Read under the lock an append holds: every frame taken is counted. let written = { let mut inner = lock(&s.inner); inner.closed = true; inner.give_back(); s.written.load(Ordering::SeqCst) }; let synced = self.wait(written); self.let_go(); synced } /// Let the log's files go, their locks with them, its room given back: /// it takes no frame and makes no sync from then on, and a compaction /// of it makes no `.tmp`, puts no checkpoint in place and deletes /// nothing. Nothing is synced: what was not waited for is as a kill /// leaves it. A frame an append wrote and could not cut back is cut /// now, or else by the next open of the log in this run (`UNCUT`). fn let_go(&self) { let mut inner = lock(&self.0.inner); if inner.torn && !inner.shut && self.0.mend(&mut inner).is_err() { lock(&UNCUT).insert(inner.path.clone(), inner.len); } inner.give_back(); inner.closed = true; inner.shut = true; inner.file = None; inner.unsynced.clear(); drop(inner); if let Some(p) = &self.0.pool { p.forget(&self.0); } } /// The bytes of a torn tail cut off its end when it was opened: none /// of them room. pub fn dropped(&self) -> u64 { self.0.dropped } pub fn written(&self) -> u64 { self.0.written.load(Ordering::SeqCst) } /// The bytes of the frames in the current log's file: where it ends, /// whatever room its file has after them. pub fn len(&self) -> u64 { lock(&self.0.inner).len } pub fn is_empty(&self) -> bool { self.len() == 0 } /// Have `paths` synced, each with its directory, before the log next is: /// given before a frame that rests on them is appended, they are on disk /// before it is. Concurrent waiters share their syncs as they share the /// log's. pub fn sync_first(&self, paths: impl IntoIterator) { lock(&self.0.sync_first).extend(paths); } /// Write the log's frames from now on to `journal` too, and wait on it /// in place of a sync of the log's own file, as a log of a pool with a /// journal does: for a log of no pool, given it before its first /// append. A log that has a journal keeps it. pub fn use_journal(&self, journal: Arc) { let _ = self.0.journal.set(journal); } /// Whether frame `seq` is known to be on disk already. pub fn is_durable(&self, seq: u64) -> bool { self.0.durable.load(Ordering::SeqCst) >= seq } /// Return once frame `seq` is on disk, and every file `sync_first` was /// given before it. Waiters at once share a sync: one of them makes it, /// of every frame written by then, and each it covers is answered when /// it ends, as it ended; one it does not cover waits for the next, or /// makes it. A sync that fails is the answer to each waiter it would /// have covered, and leaves the log as it was, for the next to try again. pub fn wait(&self, seq: u64) -> io::Result<()> { let s = &self.0; wait_shared(&s.synced, &s.sync_ended, &s.durable, seq, |covered| { s.sync_written(covered) }) } /// Put in the log's place, durably, the frames `fold` makes of its frames, /// with appends held off meanwhile. If `fold` or a write fails, the log is /// as it was. With a journal, the log's file is first made durable by /// itself, and the journal told to `forget` it, durably, before /// anything is put in its place: a start writes nothing the journal held /// of the file before into the one after. pub fn rewrite( &self, fold: impl FnOnce(Vec>) -> Result>, String>, ) -> Result<(), String> { let s = &self.0; let mut inner = lock(&s.inner); let path = inner.path.clone(); let at = |e: io::Error| format!("{}: {e}", path.display()); if s.closed(&inner) { return Err(s.refused(&inner).to_string()); } s.mend(&mut inner).map_err(at)?; // What the frames rest on is on disk before they are, here too. s.sync_files_first().map_err(at)?; // Every frame given so far is durable once the new file is in place: // those of sealed logs too. s.sync_sealed(&inner.unsynced).map_err(at)?; inner.unsynced.clear(); let data = std::fs::read(&path).map_err(at)?; let (frames, good) = scan(&data).map_err(|why| format!("{}: {why}", path.display()))?; if torn(&data[good..]) > 0 { return Err(format!("{}: a frame that is not whole", path.display())); } let folded = fold(frames)?; if let Some(j) = s.journal.get() { let file = s.file(&mut inner).map_err(at)?; sync_data(&file).map_err(at)?; j.forget(&path).map_err(at)?; } let mut name = path.file_name().unwrap_or_default().to_os_string(); name.push(".rewrite"); let tmp = path.with_file_name(name); let written = (|| { let mut f = open_private( &tmp, OpenOptions::new().create(true).write(true).truncate(true), )?; let mut len = 0u64; let mut out = io::BufWriter::new(&mut f); for entries in &folded { let bytes = frame(entries); out.write_all(&bytes)?; len += bytes.len() as u64; } out.flush()?; drop(out); sync_file(&f)?; std::fs::rename(&tmp, &path)?; sync_dir(&s.dir)?; Ok(len) })(); let len = match written { Ok(len) => len, Err(e) => { let _ = std::fs::remove_file(&tmp); return Err(at(e)); } }; if let Some(p) = &s.pool { p.forget(s); } inner.file = None; inner.len = len; inner.size = len; inner.since = 0; // The new file is on disk whole, with every frame given so far. s.durable .fetch_max(s.written.load(Ordering::SeqCst), Ordering::SeqCst); Ok(()) } } #[cfg(test)] mod tests { use super::*; use serde_json::json; fn scratch(name: &str) -> PathBuf { let d = std::env::temp_dir().join(format!("pds-store-{}-{name}", std::process::id())); let _ = std::fs::remove_dir_all(&d); d } /// Many logs in a pool of two: never more than two open, each appended /// to and synced through whatever is open, each replaying what it was given. #[test] fn a_pool_keeps_few_open() { let dir = scratch("pool"); let pool = Files::new(2); let wals: Vec = (0..6) .map(|i| { Wal::open(&dir.join(format!("{i}/x.log")), Some(pool.clone())) .unwrap() .0 }) .collect(); assert!(pool.open_count() <= 2); for round in 0..3 { for (i, w) in wals.iter().enumerate() { let n = w.append(&[json!({ "i": i, "round": round })]).unwrap(); w.wait(n).unwrap(); assert!(pool.open_count() <= 2); } } drop(wals); for i in 0..6 { let (_, frames) = Wal::open(&dir.join(format!("{i}/x.log")), None).unwrap(); assert_eq!( frames, (0..3) .map(|r| vec![json!({ "i": i, "round": r })]) .collect::>() ); } let _ = std::fs::remove_dir_all(&dir); } /// A log dropped leaves its place in the pool, and a pool of more logs /// than it tries to close first closes the least recently used. #[test] fn a_pool_closes_the_least_recently_used() { let dir = scratch("pool-order"); let pool = Files::new(OLDEST + 4); let open = |i: usize| { Wal::open(&dir.join(format!("{i}/x.log")), Some(pool.clone())) .unwrap() .0 }; let is_open = |w: &Wal| lock(&w.0.inner).file.is_some(); let wals: Vec = (0..OLDEST + 4).map(open).collect(); assert_eq!(pool.open_count(), OLDEST + 4); // The first is used again, so the second is the one closed. let n = wals[0].append(&[json!({ "again": true })]).unwrap(); wals[0].wait(n).unwrap(); let more = open(OLDEST + 4); assert_eq!(pool.open_count(), OLDEST + 4); assert!(is_open(&wals[0]) && !is_open(&wals[1]) && is_open(&wals[2])); // The log closed takes a place again when it is next written. let n = wals[1].append(&[json!({ "again": true })]).unwrap(); wals[1].wait(n).unwrap(); assert!(is_open(&wals[1]) && !is_open(&wals[2])); assert_eq!(pool.open_count(), OLDEST + 4); drop(wals); assert_eq!(pool.open_count(), 1); drop(more); assert!(lock(&pool.open).is_empty()); let _ = std::fs::remove_dir_all(&dir); } /// A log whose file something else holds, as a sync in flight does, is /// not the one its pool closes: the file's lock would live on in that /// holder's hands, and the log's next append find its own file held. #[test] fn a_pool_closes_no_file_held_elsewhere() { let dir = scratch("pool-held"); let pool = Files::new(2); let open = |i: usize| { Wal::open(&dir.join(format!("{i}/x.log")), Some(pool.clone())) .unwrap() .0 }; let is_open = |w: &Wal| lock(&w.0.inner).file.is_some(); let (held, other) = (open(0), open(1)); let n = held.append(&[json!({ "n": 0 })]).unwrap(); held.wait(n).unwrap(); other.append(&[json!({ "n": 0 })]).unwrap(); // As `sync_written` holds it through its sync, with no lock held. let syncing = lock(&held.0.inner).file.clone().unwrap(); let room = syncing.metadata().unwrap().len(); assert!(room > held.len(), "it holds room"); // The least recently used, and passed over: the next is closed. let more = open(2); assert!(is_open(&held) && !is_open(&other) && is_open(&more)); assert_eq!(syncing.metadata().unwrap().len(), room, "its room kept"); let n = held.append(&[json!({ "n": 1 })]).unwrap(); held.wait(n).unwrap(); // Once nothing else holds it, it is closed as any other. drop(syncing); let n = other.append(&[json!({ "n": 1 })]).unwrap(); other.wait(n).unwrap(); let n = more.append(&[json!({ "n": 0 })]).unwrap(); more.wait(n).unwrap(); assert!(!is_open(&held) && is_open(&other) && is_open(&more)); let n = held.append(&[json!({ "n": 2 })]).unwrap(); held.wait(n).unwrap(); drop((held, other, more)); let (_, frames) = Wal::open(&dir.join("0/x.log"), None).unwrap(); assert_eq!( frames, (0..3).map(|n| vec![json!({ "n": n })]).collect::>() ); let _ = std::fs::remove_dir_all(&dir); } /// A rewrite puts its frames in the log's place, and appends go on after them. #[test] fn rewrite_replaces_the_log() { let dir = scratch("rewrite"); let path = dir.join("a.log"); let (wal, _) = Wal::open(&path, None).unwrap(); for i in 0..10 { wal.append(&[json!(i)]).unwrap(); } wal.rewrite(|frames| { Ok(vec![ frames .into_iter() .flatten() .filter(|e| e.as_i64().unwrap() % 2 == 0) .collect(), ]) }) .unwrap(); assert!(wal.is_durable(wal.written())); let n = wal.append(&[json!("after")]).unwrap(); wal.wait(n).unwrap(); assert_eq!(wal.len(), log_len(&path).unwrap()); let frames = scan(&std::fs::read(&path).unwrap()).unwrap().0; assert_eq!( frames, vec![ vec![json!(0), json!(2), json!(4), json!(6), json!(8)], vec![json!("after")] ] ); assert!(wal.rewrite(|_| Err("no".into())).is_err()); drop(wal); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 2); let _ = std::fs::remove_dir_all(&dir); } /// The files and directories a log makes are its owner's alone, whatever the umask. #[test] fn private_files() { let dir = scratch("modes"); let path = dir.join("a/b/c.log"); Wal::open(&path, None) .unwrap() .0 .append(&[json!(1)]) .unwrap(); let mode = |p: &Path| std::fs::metadata(p).unwrap().permissions().mode() & 0o777; assert_eq!(mode(&path), FILE_MODE); assert_eq!(mode(&dir.join("a")), DIR_MODE); assert_eq!(mode(&dir.join("a/b")), DIR_MODE); let _ = std::fs::remove_dir_all(&dir); } /// Writers at once share syncs: every frame waited for is on disk, in /// no more syncs than there are frames, and a frame on disk already /// needs none. #[test] fn waiters_share_syncs() { let dir = scratch("shared"); let (wal, _) = Wal::open(&dir.join("a.log"), None).unwrap(); std::thread::scope(|s| { for t in 0..8 { let wal = &wal; s.spawn(move || { for i in 0..20 { let n = wal.append(&[json!([t, i])]).unwrap(); wal.wait(n).unwrap(); assert!(wal.is_durable(n)); } }); } }); let syncs = lock(&wal.0.trace).len(); assert!((1..=160).contains(&syncs), "{syncs} syncs of 160 frames"); wal.wait(wal.written()).unwrap(); assert_eq!(lock(&wal.0.trace).len(), syncs); drop(wal); let (_, frames) = Wal::open(&dir.join("a.log"), None).unwrap(); assert_eq!(frames.len(), 160); let _ = std::fs::remove_dir_all(&dir); } /// A sync that fails is the answer to every waiter it would have /// covered, whichever of them made it, and leaves the log as it was: /// the next sync is tried, and makes their frames durable once it can. #[test] fn a_failed_sync_fails_its_waiters() { let dir = scratch("failed"); let (wal, _) = Wal::open(&dir.join("a.log"), None).unwrap(); // A file the frames rest on that cannot be opened: one under a file. let blocker = dir.join("blocker"); std::fs::write(&blocker, b"").unwrap(); wal.sync_first([blocker.join("x")]); let waited: Vec<(u64, io::Result<()>)> = std::thread::scope(|s| { let waiters: Vec<_> = (0..8) .map(|i| { let wal = &wal; s.spawn(move || { let n = wal.append(&[json!(i)]).unwrap(); (n, wal.wait(n)) }) }) .collect(); waiters.into_iter().map(|w| w.join().unwrap()).collect() }); for (n, answer) in &waited { assert!(answer.is_err(), "frame {n} answered {answer:?}"); assert!(!wal.is_durable(*n)); } assert!(wal.wait(wal.written()).is_err(), "tried again, and failed"); std::fs::remove_file(&blocker).unwrap(); wal.wait(wal.written()).unwrap(); assert!(waited.iter().all(|(n, _)| wal.is_durable(*n))); let _ = std::fs::remove_dir_all(&dir); } /// A file's size, room and all. fn file_size(path: &Path) -> u64 { std::fs::metadata(path).unwrap().len() } /// A log of two frames with room after them, and then a third written /// over the room: the file as a kill leaves it before the third and /// after it, and where the third begins and ends. fn roomy(dir: &Path) -> (PathBuf, Vec, Vec, usize, usize) { roomy_in(dir, None) } /// The same, the log given `journal` before the third frame: one whose /// file holds room from before it had a journal. fn roomy_in( dir: &Path, journal: Option>, ) -> (PathBuf, Vec, Vec, usize, usize) { let path = dir.join("a.log"); let (wal, _) = Wal::open(&path, None).unwrap(); wal.append(&[json!("a")]).unwrap(); // Longer than the room the first left: it grows the file. wal.append(&[json!("bb")]).unwrap(); let before = std::fs::read(&path).unwrap(); let from = wal.len() as usize; assert_eq!(before.len(), 2 * from, "as much room as frames"); if let Some(j) = journal { wal.use_journal(j); } wal.append(&[json!("c")]).unwrap(); let after = std::fs::read(&path).unwrap(); let to = wal.len() as usize; assert_eq!(after.len(), before.len(), "written over the room"); assert_eq!(&after[to..], &before[to..]); (path, before, after, from, to) } /// Zeros are no frame, however many: a header of zeros names a payload /// of no bytes, whose check is not zero, and which is no JSON array. #[test] fn zeros_are_no_frame() { assert_ne!(check(&[]), [0u8; 8]); for n in [0, 1, HEADER - 1, HEADER, HEADER + 1, 4096, 1 << 16] { let zeros = vec![0u8; n]; assert_eq!(scan(&zeros), Ok((vec![], 0)), "{n} zeros"); assert_eq!(parse_frame(&zeros), None, "{n} zeros"); assert_eq!(payload(zeros), None, "{n} zeros"); } // Nor is a header with the check of no payload: nothing is no array. let mut empty = vec![0u8; HEADER]; empty[4..].copy_from_slice(&check(&[])); assert_eq!(scan(&empty), Ok((vec![], 0))); assert_eq!(parse_frame(&empty), None); let dir = scratch("zeros"); make_dirs(&dir).unwrap(); let path = dir.join("a.log"); std::fs::write(&path, vec![0u8; 5000]).unwrap(); let seen = scan_file(&path, |_, _, _| Err("a frame".into())).unwrap(); assert_eq!(seen, Ok((0, 0))); assert_eq!(log_len(&path).unwrap(), 0); let (wal, frames) = Wal::open(&path, None).unwrap(); assert_eq!((frames.len(), wal.len(), wal.dropped()), (0, 0, 0)); assert_eq!(file_size(&path), 0); let _ = std::fs::remove_dir_all(&dir); } /// Room is made as a log is written to: a frame that grows the file /// gives it as much room as the frames written since it was opened, /// itself among them, at most `AHEAD`. So the first grows it by twice /// its length, and the frames after go over the room. The log's end /// is its frames', whatever the file's. The room goes when the log is /// let go or closed; a kill leaves it, until the next start. #[test] fn room_is_made_as_a_log_is_written_to() { let dir = scratch("room"); let path = dir.join("a.log"); let (wal, _) = Wal::open(&path, None).unwrap(); wal.append(&[json!(0)]).unwrap(); let one = wal.len(); assert_eq!(file_size(&path), 2 * one, "the first, and as much again"); let (_, at) = wal.append_at(&[json!(1)]).unwrap(); assert_eq!((at.offset, at.len), (one, one)); assert_eq!((wal.len(), file_size(&path)), (2 * one, 2 * one)); wal.append(&[json!(2)]).unwrap(); assert_eq!((wal.len(), file_size(&path)), (3 * one, 6 * one)); for i in 3..6 { wal.append(&[json!(i)]).unwrap(); assert_eq!(file_size(&path), 6 * one, "over the room"); } assert_eq!(wal.len(), 6 * one); // A frame larger than the room left takes it and grows the file. let large = json!("x".repeat(100 << 10)); let long = frame(std::slice::from_ref(&large)).len() as u64; wal.append(std::slice::from_ref(&large)).unwrap(); assert_eq!(file_size(&path), 2 * wal.len()); wal.append(std::slice::from_ref(&large)).unwrap(); assert_eq!(file_size(&path) - wal.len(), 6 * one); wal.append(std::slice::from_ref(&large)).unwrap(); assert_eq!(file_size(&path), wal.len() + AHEAD, "never more"); wal.append(std::slice::from_ref(&large)).unwrap(); assert_eq!(file_size(&path) - wal.len(), AHEAD - long); wal.wait(wal.written()).unwrap(); // What reads the file finds its frames, and the end of them. let len = wal.len(); assert_eq!(log_len(&path).unwrap(), len); let (frames, end) = scan(&std::fs::read(&path).unwrap()).unwrap(); assert_eq!((frames.len(), end as u64), (10, len)); assert_eq!(scan_file(&path, |_, _, _| Ok(())).unwrap(), Ok((len, len))); assert_eq!(read_frame(&path, at.offset, at.len).unwrap(), [json!(1)]); let live = std::fs::read(&path).unwrap(); // Let go, it gives its room back. drop(wal); assert_eq!(file_size(&path), len); // Killed, it keeps the room it had until it is opened. std::fs::write(&path, &live).unwrap(); let (wal, frames) = Wal::open(&path, None).unwrap(); assert_eq!((frames.len(), wal.len(), wal.dropped()), (10, len, 0)); assert_eq!(file_size(&path), len); wal.append(&[json!(6)]).unwrap(); assert_eq!(file_size(&path), wal.len() + one, "as at first"); wal.append(&[json!(7)]).unwrap(); assert_eq!(file_size(&path), wal.len()); // Closed, it gives it back, and every frame it took is on disk. let n = wal.append(&[json!(8)]).unwrap(); assert!(file_size(&path) > wal.len() && !wal.is_durable(n)); wal.close().unwrap(); assert!(file_size(&path) == wal.len() && wal.is_durable(n)); drop(wal); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 13); let _ = std::fs::remove_dir_all(&dir); } /// A frame written over room, cut at every byte, with the room after it /// as it was: the log recovers to before the frame or, whole, after it, /// is cut back to its frames, and goes on. #[test] fn a_cut_inside_room_recovers_to_before_or_after() { let dir = scratch("room-cut"); let (path, before, after, from, to) = roomy(&dir); for cut in from..=to { let disk = [&after[..cut], &before[cut..]].concat(); std::fs::write(&path, &disk).unwrap(); let (wal, frames) = Wal::open(&path, None).unwrap(); let whole = (cut == to) as usize; assert_eq!(frames.len(), 2 + whole, "cut at {cut}"); let part = if cut == to { 0 } else { torn(&after[from..cut]) }; assert_eq!(wal.dropped(), part as u64, "cut at {cut}"); assert_eq!(file_size(&path), wal.len(), "cut at {cut}"); assert_eq!(wal.len() as usize, if cut == to { to } else { from }); wal.wait(wal.append(&[json!("d")]).unwrap()).unwrap(); drop(wal); let (_, frames) = Wal::open(&path, None).unwrap(); assert_eq!(frames.len(), 3 + whole, "cut at {cut}"); assert_eq!(frames[2 + whole], [json!("d")], "cut at {cut}"); } let _ = std::fs::remove_dir_all(&dir); } /// A file shorter than its room, the room not on disk whole, or than a /// frame written over it: ending at any byte from its last frame synced /// on, it recovers to the frames that are there whole. #[test] fn a_file_shorter_than_its_room() { let dir = scratch("room-short"); let (path, before, after, from, to) = roomy(&dir); let opened = |disk: &[u8]| { std::fs::write(&path, disk).unwrap(); let (wal, frames) = Wal::open(&path, None).unwrap(); assert_eq!(file_size(&path), wal.len()); (frames.len(), wal.len() as usize, wal.dropped() as usize) }; for end in from..=before.len() { assert_eq!(opened(&before[..end]), (2, from, 0), "ends at {end}"); } for end in from..to { let part = torn(&after[from..end]); assert_eq!(opened(&after[..end]), (2, from, part), "ends at {end}"); } for end in to..=after.len() { assert_eq!(opened(&after[..end]), (3, to, 0), "ends at {end}"); } let _ = std::fs::remove_dir_all(&dir); } /// The same two with a journal, as `PDS_SYNC` `together` writes, given /// the log after the first two frames, which made room: the third /// written over that room, and not answered. The log cut at every byte /// of the third, the room after it as it was or the file ending there, /// and the journal as a power cut leaves it, its record of the third /// whole or cut at every byte: a start redoes the journal, and the log /// holds the first two and the third where either kept it whole, and /// goes on. #[test] fn a_cut_inside_room_with_a_journal() { let dir = scratch("room-journal"); let j = Journal::open_with(&dir, None, false).unwrap(); let (path, before, after, from, to) = roomy_in(&dir, Some(j.clone())); let segment = dir.join(journal::DIR).join("1.log"); let whole = std::fs::read(&segment).unwrap(); j.let_go(); let ends = journal::ends(&whole); assert_eq!(ends.len(), 1); let none = journal::MAGIC.len(); let started = |disk: &[u8], journal: &[u8]| { std::fs::write(&path, disk).unwrap(); std::fs::write(&segment, journal).unwrap(); journal::redo(&dir, journal::Redo::Eager).unwrap(); assert!(!segment.exists()); let (wal, frames) = Wal::open(&path, None).unwrap(); (wal, frames.len()) }; for cut in from..=to { for (disk, kept) in [ ([&after[..cut], &before[cut..]].concat(), 2), (after[..cut].to_vec(), 2), ] { let kept = kept + (cut == to) as usize; assert_eq!(started(&disk, &whole[..none]).1, kept, "cut at {cut}"); let (wal, n) = started(&disk, &whole); assert_eq!(n, 3, "cut at {cut}, the journal whole"); if cut % 7 == 0 || cut == to { wal.wait(wal.append(&[json!("d")]).unwrap()).unwrap(); drop(wal); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 4); } } } for end in none..=ends[0] { let n = started(&before, &whole[..end]).1; assert_eq!(n, 2 + (end == ends[0]) as usize, "the journal cut at {end}"); } let _ = std::fs::remove_dir_all(&dir); } /// A log with a journal makes no room: its file is its frames alone /// after each append. One whose file holds room from before it had a /// journal writes over the room, and holds its frames alone once closed. #[test] fn a_journaled_log_makes_no_room() { let dir = scratch("room-journaled"); let j = Journal::open_with(&dir, None, false).unwrap(); let pool = Files::with_journal(4, j.clone()); let path = dir.join("b.log"); let (wal, _) = Wal::open(&path, Some(pool)).unwrap(); for i in 0..20 { wal.append(&[json!(i)]).unwrap(); assert_eq!(file_size(&path), wal.len(), "room after frame {i}"); } let path = dir.join("a.log"); let (wal, _) = Wal::open(&path, None).unwrap(); wal.append(&[json!("a")]).unwrap(); wal.append(&[json!("bb")]).unwrap(); let roomy = file_size(&path); assert!(roomy > wal.len()); wal.use_journal(j.clone()); wal.append(&[json!("c")]).unwrap(); assert_eq!(file_size(&path), roomy, "written over the room"); wal.close().unwrap(); assert_eq!(file_size(&path), wal.len()); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 3); let _ = std::fs::remove_dir_all(&dir); } /// Nothing after a gap is taken: a frame that follows zeros where one /// did not reach the disk, or part of one that did, is cut off with /// them, and never read after a frame written later in their place. #[test] fn nothing_after_a_gap_is_taken() { let dir = scratch("room-gap"); make_dirs(&dir).unwrap(); let path = dir.join("a.log"); let [a, b, c, e] = ["a", "b", "c", "e"].map(|x| frame(&[json!(x)])); let kept = [a.clone(), b.clone()].concat(); let room = vec![0u8; 64]; let opened = |disk: &[u8]| { std::fs::write(&path, disk).unwrap(); let (wal, frames) = Wal::open(&path, None).unwrap(); assert_eq!(frames, [[json!("a")], [json!("b")]]); assert_eq!(file_size(&path), kept.len() as u64); assert_eq!(std::fs::read(&path).unwrap(), kept); wal }; for gap in [1, HEADER - 1, HEADER, c.len(), 4096] { let disk = [&kept[..], &vec![0u8; gap], &c, &room].concat(); assert_eq!(opened(&disk).dropped(), (gap + c.len()) as u64, "{gap}"); } // A frame the length of the gap, written where it was. let disk = [&kept[..], &vec![0u8; e.len()], &c, &room].concat(); let wal = opened(&disk); wal.wait(wal.append(&[json!("e")]).unwrap()).unwrap(); drop(wal); assert_eq!(std::fs::read(&path).unwrap(), [&kept[..], &e].concat()); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 3); // Zeros, then what is no frame. let disk = [&kept[..], &[0u8; 20], &[0xff; 30], &room[..]].concat(); assert_eq!(opened(&disk).dropped(), 50); // A frame of several blocks, one of which did not reach the disk: // its first, with its header, or one inside it. let large = frame(&[json!("x".repeat(10_000))]); for missing in [0..4096, 4096..8192, large.len() - 1..large.len()] { let mut part = large.clone(); part[missing.clone()].fill(0); let disk = [&kept[..], &part, &c, &room].concat(); let dropped = opened(&disk).dropped(); assert_eq!(dropped, (large.len() + c.len()) as u64, "{missing:?}"); } let _ = std::fs::remove_dir_all(&dir); } /// A pool gives back the room of a log it closes: a log not in use /// holds its frames alone, and is written to next as one just opened. #[test] fn a_pool_gives_back_the_room_of_a_log_it_closes() { let dir = scratch("room-pool"); let pool = Files::new(1); let (pa, pb) = (dir.join("a.log"), dir.join("b.log")); let (a, _) = Wal::open(&pa, Some(pool.clone())).unwrap(); let (b, _) = Wal::open(&pb, Some(pool.clone())).unwrap(); for i in 0..3 { a.append(&[json!(i)]).unwrap(); } assert!(file_size(&pa) > a.len()); b.append(&[json!("b")]).unwrap(); assert_eq!((file_size(&pa), file_size(&pb)), (a.len(), 2 * b.len())); let closed = a.len(); a.append(&[json!(3)]).unwrap(); assert_eq!(file_size(&pb), b.len()); assert_eq!(file_size(&pa) - a.len(), a.len() - closed); a.wait(a.append(&[json!(4)]).unwrap()).unwrap(); assert_eq!(file_size(&pa), a.len(), "over the room"); b.wait(b.append(&[json!("c")]).unwrap()).unwrap(); assert_eq!(file_size(&pa), a.len()); assert!(file_size(&pb) > b.len()); // Let go, a log gives back its room as one its pool closes does. let held = (a.len(), b.len()); drop((a, b)); assert_eq!((file_size(&pa), file_size(&pb)), held); assert_eq!(Wal::open(&pa, None).unwrap().1.len(), 5); assert_eq!(Wal::open(&pb, None).unwrap().1.len(), 2); let _ = std::fs::remove_dir_all(&dir); } /// A log written before room was, its file its frames alone, is read /// and carried on from; and so is one that ends in part of a frame. #[test] fn a_log_with_no_room_is_carried_on() { let dir = scratch("room-none"); make_dirs(&dir).unwrap(); let path = dir.join("a.log"); let frames: Vec = (0..4).flat_map(|i| frame(&[json!(i)])).collect(); let part = &frame(&[json!(4)])[..9]; std::fs::write(&path, [&frames[..], part].concat()).unwrap(); let (wal, read) = Wal::open(&path, None).unwrap(); assert_eq!((read.len(), wal.dropped()), (4, 9)); for i in 4..7 { wal.wait(wal.append(&[json!(i)]).unwrap()).unwrap(); } assert!(file_size(&path) > wal.len()); drop(wal); let (_, read) = Wal::open(&path, None).unwrap(); let want: Vec> = (0..7).map(|i| vec![json!(i)]).collect(); assert_eq!(read, want); let _ = std::fs::remove_dir_all(&dir); } /// A log has one writer. A second handle on its file fails, with an /// error naming the file, and changes nothing of it; once the first is /// let go, another opens it and writes after its frames. A handle whose /// pool closed its file fails its next append, and writes nothing, /// while another holds the file, and once another has written to it. #[test] fn a_log_has_one_writer() { let dir = scratch("one-writer"); let path = dir.join("a.log"); let (a, _) = Wal::open(&path, None).unwrap(); for i in 0..3 { a.wait(a.append(&[json!(["a", i])]).unwrap()).unwrap(); } assert!(file_size(&path) > a.len()); let held = std::fs::read(&path).unwrap(); let refused = Wal::open(&path, None).err().expect("an error"); assert_eq!(refused.kind(), io::ErrorKind::ResourceBusy); let said = refused.to_string(); assert!(said.contains("a.log") && said.contains("another handle")); assert_eq!(std::fs::read(&path).unwrap(), held, "{said}"); drop(a); let (c, frames) = Wal::open(&path, None).unwrap(); assert_eq!(frames.len(), 3); let (n, at) = c.append_at(&[json!(["c", 0])]).unwrap(); assert_eq!(at.offset as usize, torn(&held)); c.wait(n).unwrap(); drop(c); let order = [("a", 0), ("a", 1), ("a", 2), ("c", 0)]; let want: Vec> = order.iter().map(|(w, i)| vec![json!([w, i])]).collect(); assert_eq!(Wal::open(&path, None).unwrap().1, want); // With a pool of one, a log's file is closed as another's is used. let pool = Files::new(1); let other = dir.join("b.log"); let (a, _) = Wal::open(&path, Some(pool.clone())).unwrap(); let (b, _) = Wal::open(&other, Some(pool.clone())).unwrap(); let (taken, _) = Wal::open(&path, None).unwrap(); let held = std::fs::read(&path).unwrap(); let refused = a.append(&[json!(["a", 3])]).unwrap_err(); assert_eq!(refused.kind(), io::ErrorKind::ResourceBusy); assert!(refused.to_string().contains("a.log"), "{refused}"); assert_eq!(std::fs::read(&path).unwrap(), held); taken .wait(taken.append(&[json!(["t", 0])]).unwrap()) .unwrap(); drop(taken); b.append(&[json!("b")]).unwrap(); let held = std::fs::read(&path).unwrap(); let refused = a.append(&[json!(["a", 3])]).unwrap_err(); assert_eq!(refused.kind(), io::ErrorKind::InvalidData); assert!(refused.to_string().contains("a.log"), "{refused}"); assert_eq!(std::fs::read(&path).unwrap(), held); drop((a, b)); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 5); // A log closed takes nothing more, and leaves its file to another. let (shut, _) = Wal::open(&other, None).unwrap(); shut.close().unwrap(); let (next, frames) = Wal::open(&other, None).unwrap(); assert_eq!(frames.len(), 1); let refused = shut.append(&[json!("late")]).unwrap_err(); assert!(refused.to_string().contains("b.log: the log is closed")); next.wait(next.append(&[json!("next")]).unwrap()).unwrap(); drop((shut, next)); assert_eq!(Wal::open(&other, None).unwrap().1.len(), 2); let _ = std::fs::remove_dir_all(&dir); } /// A log whose file is let go a moment after it is opened again is /// opened: its lock is tried for a while before the log is taken as /// held. #[test] fn a_lock_let_go_soon_is_waited_for() { let dir = scratch("soon"); let path = dir.join("a.log"); let (held, _) = Wal::open(&path, None).unwrap(); held.wait(held.append(&[json!("one")]).unwrap()).unwrap(); std::thread::scope(|s| { s.spawn(|| { std::thread::sleep(Duration::from_millis(5)); drop(held); }); assert_eq!(Wal::open(&path, None).unwrap().1.len(), 1); }); let _ = std::fs::remove_dir_all(&dir); } /// A log closed and opened again while child processes are spawned is /// never found held: a child has a copy of its file, and its lock, /// until it execs, and whoever spawns one holds `spawning` till then. #[test] fn a_child_being_spawned_holds_no_log() { use std::process::{Command, Stdio}; use std::sync::atomic::AtomicBool; let dir = scratch("spawning"); let path = dir.join("a.log"); let this = std::env::current_exe().unwrap(); let spawned = AtomicBool::new(false); std::thread::scope(|s| { s.spawn(|| { for _ in 0..100 { let mut child = { let _alone = spawning(); Command::new(&this) .arg("--list") .stdin(Stdio::null()) .stdout(Stdio::null()) .spawn() .unwrap() }; child.wait().unwrap(); } spawned.store(true, Ordering::SeqCst); }); let mut opened = 0; while !spawned.load(Ordering::SeqCst) { drop(Wal::open(&path, None).unwrap()); opened += 1; } assert!(opened > 1, "{opened}"); }); let _ = std::fs::remove_dir_all(&dir); } }