//! An account's checkpoint, `repo.checkpoint`: a sorted table //! (`pds_store::table`) of the state its log's frames before a generation //! leave, read as it is needed, never whole; and what a store holds of the //! log after it (`Memtable`), where each entry is, not what it holds. //! //! **The table's entries**, by key, each section's in order: //! //! - `B` and a block's CID: each block of the current tree, MST node or //! record: `[refs u32 LE][rev length u8][rev][bytes]`, the count of paths //! holding a record (`1` for a node) and the rev of the commit that put it //! in the tree; //! - `C`, a space's URI, a zero byte, a blob's CID as a string, a zero //! byte and a record's path: a record of the account's repo in that //! space that references the blob: the rev of the commit or import that //! last wrote the record; //! - `D` and a seq, 8 bytes big-endian: an event in the backfill window, //! when it was made, milliseconds since the epoch, 8 bytes big-endian; //! - `E` and a seq: that event's frame; //! - `H`: the table's generation, the last `seq`, and the greatest seq of //! an event let go, each 8 bytes big-endian: what is read of a table //! without the rest of its state; //! - `O`, a space's URI, a zero byte, a commit's rev and an operation's //! index in that commit, 4 bytes big-endian: an operation of that space //! repo's log: the CID after it and the CID before it, each after its //! length, `0` for none, then the record's path; //! - `P` and a record's path: `[CID length u8][CID][rev]`, the rev of the //! commit that last wrote it; //! - `R`, a space's URI, a zero byte and a record's path: a record of that //! space repo: its CID, the rev of the commit or import that last wrote //! it, and the CIDs of the blobs it references, each after its length; //! - `S`: the rest, one DAG-CBOR map (`Small`): the version, the account's //! DID, the latest commit's block, the counts of records and blocks of //! its tree, the last TID, the handle and a change in flight, the blobs //! held with their takedowns, the records' blob refs and how many //! records of its space repos reference each blob, with blobs in a //! bucket the objects it may keep of blobs not held (`blobstore`), the //! records taken down, each space repo's rev and `data`, the lanes of //! its LtHash and the counts of its records and operations, the spaces //! it is the authority of (as `exportSpaceMeta`'s archives), its write //! notifications, and while the log after it is unmarked, the blob //! references of the space records it let go (`unmarked`); //! - `V`, keyed as `R`: that record's bytes. //! //! **The log after it** is replayed as the store loads, one frame at a time, //! into a `Memtable`: each block, path and event the log changed, and of //! the space repos, each record, commit and blob reference (`spaces`), and //! where in the log its bytes are. A commit's entry names what it changed //! of the tree: the nodes it made, with their bytes, those it took out, //! each record whose count of paths changed, and each record put, with its //! CID. Bytes are read from the log's frames, or the table, as they are //! asked for, through the block cache all the stores share (`BlockCache`), //! which keeps the files of the tables read last open, at most a share of //! them (`Config::share`). What reads a store's tree after its //! lock is let go (`Snapshot`) holds the table's file itself, and so reads //! the table it began with to the end, though a compaction replaces it or //! the account is deleted meanwhile. //! //! **Compacting** (`AccountFold`) merges the table and the sealed logs, in //! order of key, into the next table, as it reads them: blocks taken out, //! paths deleted, events out of the window, and what a `clearRecords`, an //! import or a drop voided of a space repo left out. It holds the state, //! where each entry of the sealed logs is, and of what it reads, only what //! it reads again: the places of the frames' items and the blocks records //! are looked up in, not the table's blocks it passes over once. Once the //! new table is in place, under the account's lock, the store reads it, and //! what of the memtable it holds is let go. //! //! A log of a server before the tree was changed in place has commits that //! name only their records: the first load folds it, read whole in memory //! (`pds_repo::full`), into a table, once. A table of the version before //! has no `H` (`before`): the first load folds it, with the log after it, //! into a table of this version, once. //! //! **Spaces state is this version's alone** (`unmarked`): what a log holds //! of spaces before its mark, or a table of the format `before` reads, is //! let go, but for what its space records reference of blobs until the //! mark; a table written meanwhile says so, in its `S`, with what it //! counted. use crate::blobs::{Blobs, Held}; use crate::cache::unrecoverable; use crate::identity::Pending; use crate::space_authority::Authority; use crate::space_notify::{self, Kept, Schedule}; use crate::space_repo::{self, Restore, Spaces}; use crate::{Account, Store}; use axum::body::Bytes; use k256::ecdsa::SigningKey; use pds_repo::data::{V, cid_of, cid_string, decode, encode}; use pds_repo::{Change, Record, Repo, Source, Tids, put_block}; use pds_store::table::{BlockCache, Key, Table, TableWriter, file_number}; use pds_store::{Fold, Layout, Pos}; use serde_json::Value as Json; use serde_json::value::RawValue; use spaces::{Old, SpaceMem, View}; use std::collections::{BTreeMap, HashMap, HashSet}; use std::fs::File; use std::io::{self, Write}; use std::os::unix::fs::FileExt; use std::path::{Path, PathBuf}; use std::sync::{Arc, Mutex, PoisonError, Weak}; use unmarked::Unmarked; mod before; pub(crate) mod spaces; mod unmarked; pub(crate) use unmarked::mark; #[cfg(test)] pub(crate) use before::tests::downgrade; /// The format's version: of a table with the space repos' sections, the /// only one this server writes. One of the version before is read once, /// to be folded into one of this (`before`). const VERSION: i64 = 3; // ---- Keys and values ----------------------------------------------------------- fn key(section: u8, k: &[u8]) -> Vec { let mut out = Vec::with_capacity(1 + k.len()); out.push(section); out.extend_from_slice(k); out } fn block_value(refs: u32, rev: &str, bytes: &[u8]) -> Vec { let mut out = Vec::with_capacity(5 + rev.len() + bytes.len()); out.extend_from_slice(&refs.to_le_bytes()); out.push(rev.len() as u8); out.extend_from_slice(rev.as_bytes()); out.extend_from_slice(bytes); out } /// A `B` value: the count of paths, the rev, and where the bytes begin. fn read_block_value(v: &[u8]) -> Option<(u32, &str, usize)> { let refs = u32::from_le_bytes(v.get(..4)?.try_into().ok()?); let n = *v.get(4)? as usize; let rev = std::str::from_utf8(v.get(5..5 + n)?).ok()?; Some((refs, rev, 5 + n)) } fn path_value(cid: &[u8], rev: &str) -> Vec { let mut out = vec![cid.len() as u8]; out.extend_from_slice(cid); out.extend_from_slice(rev.as_bytes()); out } fn read_path_value(v: &[u8]) -> Option<(Vec, String)> { let n = *v.first()? as usize; Some(( v.get(1..1 + n)?.to_vec(), String::from_utf8(v.get(1 + n..)?.to_vec()).ok()?, )) } fn hex_of(x: &Json) -> Result, String> { x.as_str() .and_then(|h| hex::decode(h).ok()) .ok_or_else(|| format!("{x} for hex")) } /// The `H` value: the table's generation, the last `seq`, and the greatest /// seq of an event let go, each 8 bytes big-endian. fn header_value(generation: u64, last_seq: u64, let_go: u64) -> Vec { [generation, last_seq, let_go] .iter() .flat_map(|n| n.to_be_bytes()) .collect() } fn read_header(v: &[u8]) -> Option<(u64, u64, u64)> { let n = |i: usize| { Some(u64::from_be_bytes( v.get(i * 8..i * 8 + 8)?.try_into().ok()?, )) }; (v.len() == 24).then_some(())?; Some((n(0)?, n(1)?, n(2)?)) } // ---- The rest of the state ------------------------------------------------------- /// What a checkpoint keeps besides the tree, the events and the space /// repos' records and operations, in its `S` and its `H`, and what the /// log's other entries change. pub(crate) struct Small { /// The generation of the table it was read from. pub generation: u64, /// The latest commit's block; empty before the first. pub head: Vec, pub counts: (u64, u64), pub tids: Tids, pub blobs: Blobs, /// Its records taken down, by path, each with its takedown's reference. pub takedowns: BTreeMap, /// Each space repo's commit, hash and counts. pub spaces: Spaces, pub authority: Authority, pub notify: Kept, /// The handle its last landed change gave it. pub handle: Option, /// A handle change recorded and not settled. pub pending: Option, /// The `seq` of its latest event, `0` if it never had one. pub last_seq: u64, /// The greatest `seq` of an event of its let go as out of the backfill /// window when its log was compacted, `0` if none was: the firehose /// tells a subscriber that missed it so, though nothing else holds it. pub let_go: u64, /// Until its spaces state is this version's, at its mark: the blob /// references of the space records it let go (`unmarked`). pub unmarked: Option, } impl Small { /// The state before any of a log with no table: unmarked. pub(crate) fn new() -> Small { Small { generation: 0, head: Vec::new(), counts: (0, 0), tids: Tids::new(), blobs: Blobs::default(), takedowns: BTreeMap::new(), spaces: Spaces::default(), authority: Authority::default(), notify: Kept::default(), handle: None, pending: None, last_seq: 0, let_go: 0, unmarked: Some(Unmarked::default()), } } /// Its spaces state this version's from here on: the blob references /// of the space records it let go go too, as a drop's do, and a blob /// only they held is no longer held (`unmarked`). pub(crate) fn mark(&mut self) { if self.unmarked.take().is_some() { let delta = self .blobs .space_ref_list() .into_iter() .map(|(cid, n)| (cid.to_string(), -i64::from(n))) .collect(); self.blobs.space_counted(delta); } } fn has_commit(&self) -> bool { !self.head.is_empty() } /// Replay one entry of the log but a commit's or an event's, or a space /// repo's while its spaces state is this version's. fn replay(&mut self, e: &Json, holds: impl Fn(&str) -> bool) -> Result<(), String> { let text = |k: &str| { e[k].as_str() .map(str::to_string) .ok_or_else(|| format!("a log entry with no {k}: {e}")) }; match e["t"].as_str() { Some("handle") => { if self.pending.is_some() || !self.has_commit() { return Err(format!("a handle change while none could be made: {e}")); } self.pending = Some(Pending { handle: text("handle")?, cid: text("cid")?, }); } Some("handled") => { let (Some(p), Some(landed)) = (self.pending.take(), e["landed"].as_bool()) else { return Err(format!("a handle change settled that was not made: {e}")); }; if e["cid"] != p.cid { return Err(format!( "a handle change settled that was not the one made: {e}" )); } if landed { self.handle = Some(p.handle); } } Some(t) if crate::blobs::ENTRIES.contains(&t) => self.blobs.replay(e)?, Some(crate::lifecycle::RECORD_TAKEDOWN) => { let p = text("path")?; match &e["ref"] { Json::String(r) if holds(&p) => self.takedowns.insert(p, r.clone()), Json::Null => self.takedowns.remove(&p), _ => { return Err(format!( "a takedown of a record not held, or with a ref not a string: {e}" )); } }; } Some(unmarked::MARK) => { if e["v"] != unmarked::MARK_VERSION { return Err(format!("a mark of spaces of no known version: {e}")); } self.mark(); } Some(t) if unmarked::of_spaces(t) && self.unmarked.is_some() => { if let Some(u) = &mut self.unmarked { u.replay(e, &mut self.blobs, &mut self.tids); } } Some(t) if crate::space_authority::ENTRIES.contains(&t) => self.authority.replay(e)?, Some(t) if space_notify::ENTRIES.contains(&t) => self.notify.replay(e)?, t => return Err(format!("a log entry of no known type: {t:?}")), } Ok(()) } /// The `S` value of a table: write notifications past their horizon at /// `now_ms` left out. fn encode(&self, did: &str, now_ms: u64) -> Vec { let spaces = self.spaces.saved().map(|r| { map([ ("space", text(r.space)), ("rev", text(r.rev)), ("data", V::Bytes(r.data.to_vec())), ("hash", V::Bytes(r.hash)), ("records", int(r.records)), ("ops", int(r.ops)), ]) }); let n = &self.notify; let queue = n .queue .iter() .filter(|(_, p)| p.at.until >= now_ms) .map(|(space, p)| { map([ ("space", text(space)), ("rev", text(&p.rev)), ("data", V::Bytes(p.data.clone())), ("n", int(p.at.n.into())), ("due", int(p.at.due)), ("until", int(p.at.until)), ]) }); // Every registration, lapsed ones too: one ends only when dropped. let registrations = n.registered.iter().flat_map(|(space, pairs)| { pairs.iter().map(move |((endpoint, token), r)| { map([ ("space", text(space)), ("endpoint", text(endpoint)), ("token", text(token)), ("expires", int(r.expires)), ("noticed", V::Bool(r.noticed)), ]) }) }); let notices = n.notices.iter().map(|((space, (endpoint, token)), x)| { let (update, space_rev, lapse) = match &x.owed { space_notify::Owed::Deleted => ("deleted", V::Null, V::Null), space_notify::Owed::Expired { space_rev, lapse } => { ("expired", text(space_rev), int(*lapse)) } }; map([ ("space", text(space)), ("endpoint", text(endpoint)), ("token", text(token)), ("update", text(update)), ("spaceRev", space_rev), ("lapse", lapse), ("n", int(x.at.n.into())), ("due", int(x.at.due)), ("until", int(x.at.until)), ]) }); let mut state = map([ ("version", V::Int(VERSION)), ("did", text(did)), ( "commit", if self.head.is_empty() { V::Null } else { V::Bytes(self.head.clone()) }, ), ( "counts", V::Arr(vec![int(self.counts.0), int(self.counts.1)]), ), ("tid", V::Str(self.tids.last())), ("handle", or_null(self.handle.as_deref(), text)), ( "pending", or_null(self.pending.as_ref(), |p| { map([("handle", text(&p.handle)), ("cid", text(&p.cid))]) }), ), ( "blobs", V::Arr( self.blobs .held_list() .map(|(cid, h, takedown)| { map([ ("cid", text(cid)), ("mimeType", text(&h.mime)), ("size", int(h.size)), ("at", int(h.at)), ("takedown", or_null(takedown, text)), ]) }) .collect(), ), ), ( "blobRecords", V::Arr( self.blobs .record_list() .into_iter() .map(|(p, rev, cids)| { V::Arr(vec![ text(p), text(rev), V::Arr(cids.iter().map(|c| text(c)).collect()), ]) }) .collect(), ), ), ( "spaceRefs", V::Arr( self.blobs .space_ref_list() .into_iter() .map(|(cid, n)| V::Arr(vec![text(cid), int(n.into())])) .collect(), ), ), ( "takedowns", V::Arr( self.takedowns .iter() .map(|(path, r)| map([("path", text(path)), ("ref", text(r))])) .collect(), ), ), ("spaces", V::Arr(spaces.collect())), ( "authority", V::Arr( self.authority .saved() .map(|(space, archive)| { map([ ("space", text(space)), ("archive", or_null(archive, V::Bytes)), ]) }) .collect(), ), ), ( "notify", map([ ("queue", V::Arr(queue.collect())), ("registrations", V::Arr(registrations.collect())), ("notices", V::Arr(notices.collect())), ]), ), ]); if let V::Map(m) = &mut state { // With blobs in a bucket, the objects it may keep of blobs not held. if let Some(objects) = self.blobs.objects_list() { m.push(( "objects".into(), V::Arr(objects.into_iter().map(text).collect()), )); } // Unmarked: the blob references of the space records let go. if let Some(u) = &self.unmarked { let records = u.saved().map(|(space, path, cids)| { V::Arr(vec![ text(space), text(path), V::Arr(cids.iter().map(|c| text(c)).collect()), ]) }); m.push(("unmarked".into(), V::Arr(records.collect()))); } } encode(&state) } /// Read an `S` value and its table's `H`: everything checked, as /// `encode` and `header_value` write them, and that it is of the /// account `did`. fn decode(bytes: &[u8], header: &[u8], did: &str) -> Result { let state = decode(bytes).map_err(|e| format!("the state: {e}"))?; let header = read_header(header).ok_or("a header that does not parse")?; Small::of(state, header, did) } /// The state an `S` value holds, decoded, with what its table's `H` /// holds: the table's generation, the last `seq`, and the greatest seq /// let go. fn of( mut state: V, (generation, last_seq, let_go): (u64, u64, u64), did: &str, ) -> Result { let mut optional = |k: &str| match &mut state { V::Map(m) => m .iter() .position(|(n, _)| n == k) .map(|i| m.swap_remove(i).1), _ => None, }; let (objects, unmarked) = (optional("objects"), optional("unmarked")); let objects = or_none(objects.unwrap_or(V::Null), |v| { as_list(v, "objects")? .into_iter() .map(|c| as_text(c, "an object")) .collect::, _>>() })?; let unmarked = or_none(unmarked.unwrap_or(V::Null), |v| { let mut u = Unmarked::default(); for x in as_list(v, "unmarked")? { let [space, path, cids] = as_list(x, "an unmarked record")? .try_into() .map_err(|_| "an unmarked record not three")?; let cids = as_list(cids, "an unmarked record's blob refs")? .into_iter() .map(|c| as_text(c, "a blob ref")) .collect::, _>>()?; u.restore( as_text(space, "an unmarked record's space")?, as_text(path, "an unmarked record's path")?, cids, )?; } Ok(u) })?; let [ version, state_did, commit, counts, tid, handle, pending, blobs, blob_records, space_refs, takedowns, spaces, authority, notify, ] = fields( state, [ "version", "did", "commit", "counts", "tid", "handle", "pending", "blobs", "blobRecords", "spaceRefs", "takedowns", "spaces", "authority", "notify", ], "the state", )?; if version != V::Int(VERSION) { return Err(format!( "a checkpoint of version {version:?}, which this server does not know" )); } if as_text(state_did, "did")? != did { return Err("a checkpoint of another account".into()); } let mut s = Small::new(); (s.generation, s.last_seq, s.let_go) = (generation, last_seq, let_go); s.head = or_none(commit, |v| as_bytes(v, "commit"))?.unwrap_or_default(); let (records, blocks) = as_pair(counts, "counts")?; s.counts = (as_uint(records, "a count")?, as_uint(blocks, "a count")?); s.tids.after(&as_text(tid, "tid")?); s.handle = or_none(handle, |v| as_text(v, "handle"))?; s.pending = or_none(pending, |v| { let [handle, cid] = fields(v, ["handle", "cid"], "pending")?; Ok(Pending { handle: as_text(handle, "pending's handle")?, cid: as_text(cid, "pending's cid")?, }) })?; let mut held = Vec::new(); for x in as_list(blobs, "blobs")? { let [cid, mime, size, at, takedown] = fields(x, ["cid", "mimeType", "size", "at", "takedown"], "a blob")?; let h = Held { mime: as_text(mime, "a blob's mimeType")?, size: as_uint(size, "a blob's size")?, at: as_uint(at, "a blob's at")?, }; held.push(( as_text(cid, "a blob's cid")?, h, or_none(takedown, |v| as_text(v, "a blob's takedown"))?, )); } if !ascending(held.iter().map(|(cid, _, _)| cid.as_str())) { return Err("blobs out of order".into()); } let mut records = Vec::new(); for x in as_list(blob_records, "blobRecords")? { let [path, rev, cids] = as_list(x, "a record's blob refs")? .try_into() .map_err(|_| "a record's blob refs not three")?; let cids = as_list(cids, "a record's blob refs")? .into_iter() .map(|c| as_text(c, "a blob ref")) .collect::, _>>()?; records.push(( as_text(path, "a record's path")?, as_text(rev, "a record's rev")?, cids, )); } if !ascending(records.iter().map(|(p, _, _)| p.as_str())) { return Err("blob refs out of order".into()); } let mut counted = Vec::new(); for x in as_list(space_refs, "spaceRefs")? { let (cid, n) = as_pair(x, "a space blob ref")?; let n = u32::try_from(as_uint(n, "a space blob ref's count")?) .ok() .filter(|n| *n > 0) .ok_or("a space blob ref's count out of range")?; counted.push((as_text(cid, "a space blob ref's cid")?, n)); } if !ascending(counted.iter().map(|(cid, _)| cid.as_str())) { return Err("space blob refs out of order".into()); } s.blobs = Blobs::restore(records, held, objects, counted)?; let mut last: Option = None; for x in as_list(takedowns, "takedowns")? { let [path, r] = fields(x, ["path", "ref"], "a takedown")?; let path = as_text(path, "a takedown's path")?; if last.as_ref().is_some_and(|l| *l >= path) { return Err("takedowns out of order".into()); } last = Some(path.clone()); s.takedowns.insert(path, as_text(r, "a takedown's ref")?); } let mut last: Option = None; for x in as_list(spaces, "spaces")? { let [space, rev, data, hash, records, ops] = fields( x, ["space", "rev", "data", "hash", "records", "ops"], "a space", )?; let space = as_text(space, "a space's space")?; if last.as_ref().is_some_and(|l| *l >= space) { return Err("spaces out of order".into()); } last = Some(space.clone()); let data: [u8; 32] = as_bytes(data, "a space's data")? .try_into() .map_err(|_| format!("space {space}'s data, not 32 bytes"))?; let restore = Restore { rev: as_text(rev, "a space's rev")?, data, hash: as_bytes(hash, "a space's hash")?, records: as_uint(records, "a space's records")?, ops: as_uint(ops, "a space's ops")?, space, }; s.spaces.restore(restore, &mut s.tids)?; } let mut spaces_held = Vec::new(); for x in as_list(authority, "authority")? { let [space, archive] = fields(x, ["space", "archive"], "an authority's space")?; spaces_held.push(( as_text(space, "an authority's space")?, or_none(archive, |v| as_bytes(v, "an archive"))?, )); } if !ascending(spaces_held.iter().map(|(s, _)| s.as_str())) { return Err("authority out of order".into()); } for (space, archive) in spaces_held { s.authority.restore(did, &space, archive.as_deref())?; } s.notify = read_notify(notify)?; s.unmarked = unmarked; Ok(s) } } fn int(n: u64) -> V { V::Int(i64::try_from(n).unwrap_or(i64::MAX)) } fn text(s: &str) -> V { V::Str(s.to_string()) } fn or_null(x: Option, f: impl FnOnce(T) -> V) -> V { x.map_or(V::Null, f) } fn map(fields: [(&str, V); N]) -> V { V::Map( fields .into_iter() .map(|(k, v)| (k.to_string(), v)) .collect(), ) } /// A map's values of exactly these keys, in their order. fn fields(v: V, names: [&str; N], what: &str) -> Result<[V; N], String> { let V::Map(mut m) = v else { return Err(format!("{what} is not a map")); }; let got = names.map(|k| { m.iter() .position(|(n, _)| n == k) .map(|i| m.swap_remove(i).1) }); if !m.is_empty() || got.iter().any(Option::is_none) { return Err(format!( "{what} is not a map of exactly {}", names.join(", ") )); } Ok(got.map(|x| x.unwrap_or(V::Null))) } fn as_text(v: V, what: &str) -> Result { if let V::Str(s) = v { Ok(s) } else { Err(format!("{what} is not a string")) } } fn as_uint(v: V, what: &str) -> Result { match v { V::Int(n) if n >= 0 => Ok(n as u64), _ => Err(format!("{what} is not a number of 0 or more")), } } fn as_bytes(v: V, what: &str) -> Result, String> { if let V::Bytes(b) = v { Ok(b) } else { Err(format!("{what} is not bytes")) } } fn as_list(v: V, what: &str) -> Result, String> { if let V::Arr(a) = v { Ok(a) } else { Err(format!("{what} is not a list")) } } fn as_pair(v: V, what: &str) -> Result<(V, V), String> { match as_list(v, what)?.try_into() { Ok::<[V; 2], _>([a, b]) => Ok((a, b)), Err(_) => Err(format!("{what} is not a pair")), } } fn or_none(v: V, f: impl FnOnce(V) -> Result) -> Result, String> { if v == V::Null { Ok(None) } else { f(v).map(Some) } } /// Whether keys are in strictly ascending order. fn ascending(keys: impl IntoIterator) -> bool { let mut last: Option = None; for k in keys { if last.as_ref().is_some_and(|l| *l >= k) { return false; } last = Some(k); } true } /// The notifications' state (`space_notify::Kept`), as `Small::encode` /// writes it. fn read_notify(v: V) -> Result { let [queue, registrations, notices] = fields(v, ["queue", "registrations", "notices"], "notify")?; let schedule = |n: V, due: V, until: V, what: &str| -> Result { let n = u32::try_from(as_uint(n, what)?).map_err(|_| format!("{what}: an attempt too many"))?; Ok(Schedule { n, due: as_uint(due, what)?, until: as_uint(until, what)?, }) }; let mut kept = Kept::default(); for x in as_list(queue, "notify's queue")? { let [space, rev, data, n, due, until] = fields( x, ["space", "rev", "data", "n", "due", "until"], "a queue entry", )?; let space = as_text(space, "a queue entry's space")?; if kept .queue .last_key_value() .is_some_and(|(l, _)| *l >= space) { return Err("notify's queue out of order".into()); } let at = schedule(n, due, until, "a queue entry")?; let p = space_notify::Pending { rev: as_text(rev, "a queue entry's rev")?, data: as_bytes(data, "a queue entry's data")?, at, }; kept.queue.insert(space, p); } let mut last: Option<(String, String, String)> = None; for x in as_list(registrations, "notify's registrations")? { let [space, endpoint, token, expires, noticed] = fields( x, ["space", "endpoint", "token", "expires", "noticed"], "a registration", )?; let key = ( as_text(space, "a registration's space")?, as_text(endpoint, "a registration's endpoint")?, as_text(token, "a registration's token")?, ); if last.as_ref().is_some_and(|l| *l >= key) { return Err("notify's registrations out of order".into()); } last = Some(key.clone()); let V::Bool(noticed) = noticed else { return Err("a registration's noticed is not a boolean".into()); }; let r = space_notify::Registration { expires: as_uint(expires, "a registration's expiry")?, noticed, }; kept.register(key.0, (key.1, key.2), r); } for x in as_list(notices, "notify's notices")? { let [ space, endpoint, token, update, space_rev, lapse, n, due, until, ] = fields( x, [ "space", "endpoint", "token", "update", "spaceRev", "lapse", "n", "due", "until", ], "a notice", )?; let key = ( as_text(space, "a notice's space")?, ( as_text(endpoint, "a notice's endpoint")?, as_text(token, "a notice's token")?, ), ); if kept .notices .last_key_value() .is_some_and(|(l, _)| *l >= key) { return Err("notify's notices out of order".into()); } let owed = match as_text(update, "a notice's update")?.as_str() { "deleted" => space_notify::Owed::Deleted, "expired" => space_notify::Owed::Expired { space_rev: as_text(space_rev, "a notice's spaceRev")?, lapse: as_uint(lapse, "a notice's lapse")?, }, u => return Err(format!("a notice of no known kind {u}")), }; let at = schedule(n, due, until, "a notice")?; kept.notices.insert(key, space_notify::Notice { owed, at }); } Ok(kept) } // ---- The log after the table ------------------------------------------------------- /// Where a block's bytes are: in the table, or in a frame of the log. #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub(crate) enum At { Table, Log(Pos), } /// A block the log changed: the rev that put it in the tree, its count of /// paths, where its bytes are, `None` once it left the tree, and the /// generation of the log that last changed it. #[derive(Clone, Debug)] pub(crate) struct MemBlock { pub rev: Arc, pub refs: u32, pub at: Option, pub generation: u64, } /// A record as a path has it: its CID and the rev that wrote it. pub(crate) type Written = (Vec, Arc); /// The rows of a table or what stands for them, in order of key, each read /// as it is reached. type Rows<'a, E> = Box, Vec), E>> + 'a>; /// What `events_on_disk` answers: each event's seq and when it was made, the /// greatest seq any event has had, and the greatest of those let go. pub(crate) type EventsOnDisk = (Vec<(u64, u64)>, u64, u64); /// What the log after the table changed, and where in it: of the tree's /// blocks and paths, of the events, and of the space repos. #[derive(Default)] pub(crate) struct Memtable { pub blocks: HashMap, MemBlock>, /// Each path: its record's CID and the rev that wrote it, or none once /// deleted, and the generation that last changed it. pub paths: BTreeMap, u64)>, /// Each event: when it was made, and its frame's place. pub events: BTreeMap, /// What it changed of the space repos' records, operations and blob /// references. pub spaces: SpaceMem, /// Whether the log holds a commit of the kind before the tree was /// changed in place, which names only its records. pub legacy: bool, /// The bytes its blocks and paths are counted as in the cache. keys: u64, } /// A commit entry's parts the memtable keeps. struct Commit<'a> { rev: &'a str, puts: Vec<(String, Vec)>, dels: Vec, tree: Vec>, gone: Vec>, refs: Vec<(Vec, u32, String)>, } impl Memtable { /// The bytes it is counted as in the cache. pub fn cost(&self) -> u64 { self.keys + self.events.len() as u64 * 64 + self.spaces.cost() } fn block(&mut self, cid: Vec, b: MemBlock) { let cost = cid.len() as u64 + 120; if self.blocks.insert(cid, b).is_none() { self.keys += cost; } } fn path(&mut self, path: String, written: Option, generation: u64) { let cost = path.len() as u64 * 2 + 120; if self.paths.insert(path, (written, generation)).is_none() { self.keys += cost; } } fn put_commit(&mut self, pos: Pos, c: Commit) { let g = pos.generation; let rev: Arc = Arc::from(c.rev); let gone = |rev: &Arc| MemBlock { rev: rev.clone(), refs: 0, at: None, generation: g, }; for cid in c.tree { let b = MemBlock { rev: rev.clone(), refs: 1, at: Some(At::Log(pos)), generation: g, }; self.block(cid, b); } for cid in c.gone { self.block(cid, gone(&rev)); } // An import puts every record in one commit: each looked up, not // searched for among the others. let put: HashSet<&[u8]> = c.puts.iter().map(|(_, p)| p.as_slice()).collect(); for (cid, n, added) in c.refs { if n == 0 { self.block(cid, gone(&rev)); continue; } let here = put.contains(cid.as_slice()); let at = match self.blocks.get(&cid) { _ if here => At::Log(pos), Some(MemBlock { at: Some(at), .. }) => *at, _ => At::Table, }; let b = MemBlock { rev: Arc::from(added.as_str()), refs: n, at: Some(at), generation: g, }; self.block(cid, b); } for (path, cid) in c.puts { self.path(path, Some((cid, rev.clone())), g); } for path in c.dels { self.path(path, None, g); } } /// A commit made and logged in the frame at `pos`. pub fn commit(&mut self, pos: Pos, c: &Change) { let puts = c .puts .iter() .map(|(p, _)| p.clone()) .zip(c.put_cids.iter().cloned()) .collect(); let refs = c.refs.clone(); self.put_commit( pos, Commit { rev: &c.rev, puts, dels: c.dels.clone(), tree: c.tree.iter().map(|(cid, _)| cid.clone()).collect(), gone: c.gone.clone(), refs, }, ); } /// An event logged in the frame at `pos`, made at `time`. pub fn event(&mut self, seq: u64, time: u64, pos: Pos) { self.events.insert(seq, (time, pos)); } /// Let go of what the log's generations before `generation` changed, /// which a table of that generation holds; a block a later log changed /// but whose bytes are in one of those is read from the table now. fn folded(&mut self, generation: u64) { self.blocks.retain(|_, b| b.generation >= generation); for b in self.blocks.values_mut() { if matches!(b.at, Some(At::Log(p)) if p.generation < generation) { b.at = Some(At::Table); } } self.paths.retain(|_, p| p.1 >= generation); self.events.retain(|_, e| e.1.generation >= generation); let blocks: usize = self.blocks.keys().map(|k| k.len() + 120).sum(); let paths: usize = self.paths.keys().map(|k| k.len() * 2 + 120).sum(); self.keys = (blocks + paths) as u64; self.spaces.folded(generation); } /// Replay an entry of the frame at `pos`: a commit's, an event's, a /// space repo's, or one of `small`'s; `holds` says whether a path holds /// a record, and `old` is the table's entries of the space repos. fn apply( &mut self, small: &mut Small, pos: Pos, e: &Json, holds: &dyn Fn(&Memtable, &str) -> bool, old: Old<'_>, cache: &BlockCache, ) -> Result<(), String> { let text = |k: &str| { e[k].as_str() .ok_or_else(|| format!("a log entry with no {k}: {e}")) }; let list = |k: &str| { e[k].as_array() .ok_or_else(|| format!("a commit with no {k}")) }; match e["t"].as_str() { Some("event") => { let Some(seq) = e["seq"].as_u64() else { return Err(format!("an event with no seq: {e}")); }; if self .events .last_key_value() .is_some_and(|(last, _)| *last >= seq) || seq <= small.last_seq || !small.has_commit() { return Err(format!("event {seq} out of order")); } let time = match e["time"].as_u64() { Some(t) => t, None => crate::events::event_time(&hex_of(&e["frame"])?).unwrap_or(0), }; self.events.insert(seq, (time, pos)); small.last_seq = seq; } Some("commit") => { let rev = text("rev")?; let head = hex_of(&e["head"])?; let path = |p: &Json| { p.as_str() .map(str::to_string) .ok_or_else(|| format!("a commit with {p} for a path")) }; let dels: Vec = list("dels")?.iter().map(path).collect::>()?; let mut puts: Vec<(String, Json)> = Vec::new(); let mut put_cids = Vec::new(); for p in list("puts")? { puts.push((path(&p[0])?, p[1].clone())); if !p[2].is_null() { put_cids.push(hex_of(&p[2])?); } } let change = Change { rev: rev.to_string(), puts, dels: dels.clone(), ..Default::default() }; small.blobs.committed(&change); small.blobs.take_doomed(); for p in &dels { small.takedowns.remove(p); } small.tids.after(rev); small.head = head; if e.get("tree").is_none() { self.legacy = true; return Ok(()); } if put_cids.len() != change.puts.len() { return Err(format!("a commit whose puts name no CID: {rev}")); } // What the log holds is what its commits signed. for ((p, value), cid) in change.puts.iter().zip(&put_cids) { let bytes = put_block(value).map_err(|why| format!("record {p}: {why}"))?; if cid_of(0x71, &bytes) != *cid { return Err(format!("record {p}, which the commit {rev} does not sign")); } } let counts = list("counts")?; small.counts = ( counts .first() .and_then(Json::as_u64) .ok_or("a commit with no counts")?, counts .get(1) .and_then(Json::as_u64) .ok_or("a commit with no counts")?, ); let mut tree = Vec::new(); for x in list("tree")? { let cid = hex_of(&x[0])?; if cid_of(0x71, &hex_of(&x[1])?) != cid { return Err(format!( "a tree node {}, which the commit {rev} does not sign", cid_string(&cid) )); } tree.push(cid); } let gone = list("gone")? .iter() .map(hex_of) .collect::, _>>()?; let mut refs = Vec::new(); for r in list("refs")? { let n = r[1] .as_u64() .and_then(|n| u32::try_from(n).ok()) .ok_or_else(|| format!("a commit with a bad count: {r}"))?; refs.push(( hex_of(&r[0])?, n, r[2].as_str().ok_or("a count with no rev")?.to_string(), )); } let puts = change .puts .into_iter() .map(|(p, _)| p) .zip(put_cids) .collect(); self.put_commit( pos, Commit { rev, puts, dels, tree, gone, refs, }, ); } Some(space_repo::ENTRY | space_repo::IMPORT | space_repo::DROP) if small.unmarked.is_none() => { small.spaces.replay( e, pos, &mut self.spaces, old, cache, &mut small.tids, &mut small.blobs, )? } _ => small.replay(e, |p| holds(self, p))?, } Ok(()) } } /// An item of a frame, as its payload has it: unparsed, borrowed from it. enum Raw<'a> { /// A tree node: its CID in hex, and its bytes. Node(&'a str, Data<'a>), /// A record put: its CID in hex, and its value as JSON. Record(&'a str, &'a RawValue), /// An event: its seq, and its frame. Event(u64, Data<'a>), /// A space record put, or a space commit's operations: its class in an /// index, its name there (`spaces::record_name`, `spaces::ops_name`), /// how it is written, and its text. Space(u8, [u8; 32], u8, &'a str), } /// A tree node's or an event's bytes, as a frame's payload has them: in /// hex in its JSON text, or in a hole of it, as they are (`pds_store`). #[derive(Clone, Copy)] enum Data<'a> { Hex(&'a str), Bytes(&'a [u8]), } impl<'a> Data<'a> { /// How an index says it is written, and where it is in the payload. fn written(self) -> (u8, &'a [u8]) { match self { Data::Hex(h) => (HEX, h.as_bytes()), Data::Bytes(b) => (BYTES, b), } } fn decode(self) -> Result, String> { match self { Data::Hex(h) => unhex(h), Data::Bytes(b) => Ok(b.to_vec()), } } } /// Give `f` each item of a frame's payload, of either kind, skimming the /// rest, until it says to stop: a frame of one large commit is not held /// parsed whole, nor any item of it but the one wanted. Of a payload with /// holes, its JSON text is skimmed as it is, and a node's or an event's /// bytes that are an empty string at a hole are that hole's. fn skim<'a>( payload: &'a [u8], mut f: impl FnMut(Raw<'a>) -> Result, ) -> Result<(), String> { fn parse<'a, T: serde::Deserialize<'a>>(s: &'a str) -> Result { serde_json::from_str(s).map_err(|e| format!("a log entry: {e}")) } let read = pds_store::text(payload)?; let text = std::str::from_utf8(read.json()).map_err(|e| format!("a frame: {e}"))?; let data = |s: &'a str| { let at = s.as_ptr() as usize - text.as_ptr() as usize; if s.is_empty() && let Some(b) = read.hole(at) { Data::Bytes(b) } else { Data::Hex(s) } }; for e in parse::>(text)? { let fields: HashMap<&str, &RawValue> = parse(e.get())?; let field = |k: &str| fields.get(k).map(|r| r.get()); match field("t").map(parse::<&str>).transpose()? { Some("commit") => { if let Some(tree) = field("tree") { for (cid, bytes) in parse::>(tree)? { if !f(Raw::Node(cid, data(bytes)))? { return Ok(()); } } } for p in parse::>>(field("puts").unwrap_or("[]"))? { let (Some(value), Some(cid)) = (p.get(1), p.get(2)) else { continue; }; let Some(cid) = parse::>(cid.get())? else { continue; }; if !f(Raw::Record(cid, value))? { return Ok(()); } } } Some("event") => { let (Some(seq), Some(frame)) = (field("seq"), field("frame")) else { continue; }; if !f(Raw::Event(parse(seq)?, data(parse(frame)?)))? { return Ok(()); } } Some(t @ (space_repo::ENTRY | space_repo::IMPORT)) => { let (Some(space), Some(rev)) = (field("space"), field("rev")) else { continue; }; // One not of this version's, before its log's mark // (`unmarked`), is passed over where it does not read. let (Ok(space), Ok(rev)) = (parse::(space), parse::(rev)) else { continue; }; if let Some(ops) = field("ops") && !f(Raw::Space( SPACE_OPS, spaces::ops_name(&space, &rev), RAW, ops, ))? { return Ok(()); } let records = if t == space_repo::ENTRY { "puts" } else { "records" }; let records = field(records).unwrap_or("[]"); let Ok(records) = parse::>(records) else { continue; }; for (path, value) in records { let name = spaces::record_name(&space, &rev, &path); if !f(Raw::Space(SPACE_RECORD, name, RECORD, value.get()))? { return Ok(()); } } } _ => {} } } Ok(()) } /// A record's block, from its value as a put has it (`put_value`). fn record_block(value: &str) -> Result, String> { let json: Json = serde_json::from_str(value).map_err(|e| format!("a record: {e}"))?; put_block(&json).map_err(|why| format!("a record: {why}")) } fn unhex(h: &str) -> Result, String> { hex::decode(h).map_err(|_| format!("{h} for hex")) } /// How an item of a frame is written: a tree node or an event, in hex, a /// record, as JSON, a space commit's operations, as they are, or a tree /// node or an event in a hole of a payload with holes, as they are. const HEX: u8 = 0; const RECORD: u8 = 1; const RAW: u8 = 2; const BYTES: u8 = 3; /// The classes of an index's items: a block, an event, a space record, and /// a space commit's operations. const BLOCK: u8 = 0; const EVENT: u8 = 1; const SPACE_RECORD: u8 = 2; const SPACE_OPS: u8 = 3; /// The longest name an index holds: a CID's bytes, an event's seq, or a /// space item's name. const NAME: usize = 40; /// An index entry: its item's class, its name's length and its name, /// padded; how it is written, and where it is in the payload, its start /// and length. const ENTRY: usize = 2 + NAME + 1 + 8; const SORT: usize = 2 + NAME; /// The item a reader wants of a frame: a block by CID, an event by seq, a /// space record by its name, checked to be of a CID, or a space commit's /// operations by their name. #[derive(Clone, Copy)] enum Want<'a> { Block(&'a [u8]), Event(u64), SpaceRecord(&'a [u8; 32], &'a [u8]), SpaceOps(&'a [u8; 32]), } /// An item's place in an index's order, if a name that long fits one. fn sort_key(class: u8, name: &[u8]) -> Option<[u8; SORT]> { if name.len() > NAME { return None; } let mut k = [0u8; SORT]; k[0] = class; k[1] = name.len() as u8; k[2..2 + name.len()].copy_from_slice(name); Some(k) } impl Want<'_> { /// Its class in an index, and its name there. fn name(&self) -> (u8, Vec) { match self { Want::Block(cid) => (BLOCK, cid.to_vec()), Want::Event(seq) => (EVENT, seq.to_be_bytes().to_vec()), Want::SpaceRecord(name, _) => (SPACE_RECORD, name.to_vec()), Want::SpaceOps(name) => (SPACE_OPS, name.to_vec()), } } /// Its place in an index's order, if a name that long fits one. fn sort_key(&self) -> Option<[u8; SORT]> { let (class, name) = self.name(); sort_key(class, &name) } } /// Where each item of a frame's payload is in it, sorted, so that one is /// read alone, not the frame: none if a name is too long for it. fn index(payload: &[u8]) -> Result>, String> { let base = payload.as_ptr() as usize; let mut entries: Vec<[u8; ENTRY]> = Vec::new(); let mut fits = true; skim(payload, |item| { let (class, name, (how, text)) = match item { Raw::Node(cid, data) => (BLOCK, unhex(cid)?, data.written()), Raw::Record(cid, value) => (BLOCK, unhex(cid)?, (RECORD, value.get().as_bytes())), Raw::Event(seq, data) => (EVENT, seq.to_be_bytes().to_vec(), data.written()), Raw::Space(class, name, how, text) => (class, name.to_vec(), (how, text.as_bytes())), }; let Some(k) = sort_key(class, &name) else { fits = false; return Ok(false); }; let mut e = [0u8; ENTRY]; e[..SORT].copy_from_slice(&k); e[SORT] = how; e[SORT + 1..SORT + 5] .copy_from_slice(&((text.as_ptr() as usize - base) as u32).to_le_bytes()); e[SORT + 5..].copy_from_slice(&(text.len() as u32).to_le_bytes()); entries.push(e); Ok(true) })?; if !fits { return Ok(None); } entries.sort_by(|a, b| a[..SORT].cmp(&b[..SORT])); entries.dedup_by(|a, b| a[..SORT] == b[..SORT]); Ok(Some(entries.concat())) } /// Where `want` is in the frame `index` is of: how it is written, its /// start and its length. fn find(index: &[u8], want: Want) -> Option<(u8, usize, usize)> { let k = want.sort_key()?; let entry = |i: usize| &index[i * ENTRY..(i + 1) * ENTRY]; let (mut lo, mut hi) = (0, index.len() / ENTRY); while lo < hi { let mid = (lo + hi) / 2; match entry(mid)[..SORT].cmp(&k[..]) { std::cmp::Ordering::Less => lo = mid + 1, std::cmp::Ordering::Greater => hi = mid, std::cmp::Ordering::Equal => { let e = entry(mid); let n = |at: usize| { u32::from_le_bytes(e[at..at + 4].try_into().expect("four bytes")) as usize }; return Some((e[SORT], n(SORT + 1), n(SORT + 5))); } } } None } /// An item, as its frame writes it. fn decode_item(how: u8, text: &[u8]) -> Result, String> { if how == BYTES { return Ok(text.to_vec()); } let text = std::str::from_utf8(text).map_err(|e| format!("an item: {e}"))?; match how { RECORD => record_block(text), RAW => Ok(text.as_bytes().to_vec()), _ => unhex(text), } } /// One item of a frame's payload, found by skimming it. fn item(payload: &[u8], want: Want) -> Result>, String> { let cid = match want { Want::Block(c) => Some(hex::encode(c)), _ => None, }; let mut found = None; skim(payload, |item| { found = match (item, want) { (Raw::Node(c, data), _) if cid.as_deref() == Some(c) => Some(data.decode()?), (Raw::Record(c, value), _) if cid.as_deref() == Some(c) => { Some(record_block(value.get())?) } (Raw::Event(s, data), Want::Event(seq)) if s == seq => Some(data.decode()?), (Raw::Space(SPACE_RECORD, n, how, text), Want::SpaceRecord(name, _)) | (Raw::Space(SPACE_OPS, n, how, text), Want::SpaceOps(name)) if n == *name => { Some(decode_item(how, text.as_bytes())?) } _ => return Ok(true), }; Ok(false) })?; Ok(found) } /// The key a frame's index is kept by in the block cache: its file's /// number and its offset, and no name, which no item has. fn index_key(number: u64, pos: Pos) -> Key { Key::Item(number, pos.offset, Box::default()) } /// An item of the frame at `pos` of the log numbered `number` in `cache`, /// whose bytes `read` reads, by offset and length. Its index, kept in the /// cache, says where it is, so that only it is read; the frame is read /// whole, and checked, only to make the index. A block, and a space /// record, is checked to be what its CID says. fn frame_item( cache: &BlockCache, number: u64, pos: Pos, read: &dyn Fn(u64, usize) -> io::Result>, want: Want, ) -> Result>, String> { let key = index_key(number, pos); let found = match cache.get(&key) { Some(ix) => indexed_item(&ix, pos, read, want)?, None => { let (ix, found) = whole_frame_item(pos, read, want)?; if let Some(ix) = ix { cache.put(key, ix.into()); } found } }; checked(want, found) } /// An item of the frame at `pos`, by the frame's index `ix`: its bytes /// alone, which `read` reads. fn indexed_item( ix: &[u8], pos: Pos, read: &dyn Fn(u64, usize) -> io::Result>, want: Want, ) -> Result>, String> { let Some((how, start, len)) = find(ix, want) else { return Ok(None); }; let text = read(pos.offset + (pds_store::HEADER + start) as u64, len).map_err(|e| e.to_string())?; decode_item(how, &text).map(Some) } /// A frame's index, if a name fits one (`index`), and an item found in it. type Indexed = (Option>, Option>); /// An item of the frame at `pos`, read whole by `read`, and the frame's /// index, made of it. fn whole_frame_item( pos: Pos, read: &dyn Fn(u64, usize) -> io::Result>, want: Want, ) -> Result { let payload = pds_store::payload(read(pos.offset, pos.len as usize).map_err(|e| e.to_string())?) .ok_or_else(|| format!("no whole frame at {}", pos.offset))?; let Some(ix) = index(&payload)? else { return Ok((None, item(&payload, want)?)); }; let found = match find(&ix, want) { None => None, Some((how, start, len)) => Some(decode_item( how, payload .get(start..start + len) .ok_or("an index past its frame")?, )?), }; Ok((Some(ix), found)) } /// An item found, checked: a block, and a space record, is what its CID /// says it is. fn checked(want: Want, found: Option>) -> Result>, String> { if let (Want::Block(c) | Want::SpaceRecord(_, c), Some(b)) = (want, &found) && cid_of(0x71, b) != c { return Err(format!( "block {} is not what its frame holds", cid_string(c) )); } Ok(found) } /// The indexes of the frames a fold reads the items of, by each frame's /// generation and offset, and their bytes. Each is made once, when an item /// of its frame is first read, and kept until the fold ends, whatever its /// size: the block cache keeps no entry larger than an eighth of it, and /// one commit of a whole repository, as an import is, has an index larger /// than the fold's cache would keep, which would otherwise be made again, /// the whole frame read, for each of its items. #[derive(Default)] struct Indexes { of: HashMap<(u64, u64), Vec>, bytes: u64, } impl Indexes { /// An item of the frame at `pos`, whose bytes `read` reads, as /// `frame_item` reads one. fn item( &mut self, pos: Pos, read: &dyn Fn(u64, usize) -> io::Result>, want: Want, ) -> Result>, String> { let found = match self.of.get(&(pos.generation, pos.offset)) { Some(ix) => indexed_item(ix, pos, read, want)?, None => { let (ix, found) = whole_frame_item(pos, read, want)?; if let Some(ix) = ix { self.bytes += ix.len() as u64; self.of.insert((pos.generation, pos.offset), ix); } found } }; checked(want, found) } } /// Read `len` bytes of `file` at `offset`. fn read_at(file: &File, offset: u64, len: usize) -> io::Result> { let mut buf = vec![0u8; len]; file.read_exact_at(&mut buf, offset)?; Ok(buf) } // ---- A store's files --------------------------------------------------------------- /// What a store reads its tree, its events and its space repos from: its /// table, if it has one, and its log, by the memtable. pub(crate) struct Disk { pub layout: Layout, pub table: Option>, pub mem: Memtable, /// The greatest seq of an event of its let go when its log was /// compacted, as its table's `H` has it: `0` with no table. pub let_go: u64, /// The bytes its table's index and bloom filter are counted as in the /// cache: `0` with no table. table_cost: u64, /// The number each log's generation is held by in the block cache. numbers: Mutex>, } /// What a store's blocks and paths are read through: its files and the cache. pub(crate) struct Src<'a> { disk: &'a Disk, cache: &'a BlockCache, } impl Source for Src<'_> { fn block(&self, cid: &[u8]) -> Option> { self.disk.block(self.cache, cid) } fn path(&self, path: &str) -> Option<(Vec, String)> { self.disk.path(self.cache, path) } fn refs(&self, cid: &[u8]) -> Option<(u32, String)> { self.disk.refs(self.cache, cid) } } impl Disk { fn new(layout: Layout, table: Option>) -> Disk { Disk { layout, table_cost: table.as_ref().map_or(0, |t| t.cost()), table, mem: Memtable::default(), let_go: 0, numbers: Mutex::default(), } } /// A new account's: no table, its log empty. pub fn empty(layout: Layout) -> Disk { Disk::new(layout, None) } pub fn source<'a>(&'a self, cache: &'a BlockCache) -> Src<'a> { Src { disk: self, cache } } /// The bytes it is counted as in the cache: its table's index, and /// what the memtable keeps, each a total kept as it changes. pub fn cost(&self) -> u64 { self.table_cost + self.mem.cost() } /// What it holds cannot be read: the server stops (`unrecoverable`). pub(crate) fn fail(&self, why: impl std::fmt::Display) -> ! { unrecoverable(&self.layout.dir, &why.to_string()) } fn number(&self, generation: u64) -> u64 { *self .numbers .lock() .unwrap_or_else(PoisonError::into_inner) .entry(generation) .or_insert_with(file_number) } /// Keep in `cache` the index of the frame just appended at `pos`, its /// payload `payload`: its items are read alone from then on. pub fn indexed(&self, cache: &BlockCache, pos: Pos, payload: &[u8]) { if let Ok(Some(ix)) = index(payload) { cache.put(index_key(self.number(pos.generation), pos), ix.into()); } } /// An item of the frame at `pos`, read and kept in the cache. fn log_item(&self, cache: &BlockCache, pos: Pos, want: Want) -> Option> { let number = self.number(pos.generation); let (class, name) = want.name(); let name = [&[class][..], &name].concat(); let key = Key::Item(number, pos.offset, name.into_boxed_slice()); if let Some(b) = cache.get(&key) { return Some(b); } let path = self.layout.log(pos.generation); let read = |offset: u64, len: usize| read_at(&File::open(&path)?, offset, len); let found: Arc<[u8]> = frame_item(cache, number, pos, &read, want) .unwrap_or_else(|e| self.fail(format!("{}: {e}", path.display())))? .into(); cache.put(key, found.clone()); Some(found) } fn table_get(&self, cache: &BlockCache, k: &[u8]) -> Option> { let t = self.table.as_ref()?; t.get(k, cache).unwrap_or_else(|e| self.fail(e)) } /// A block of the current tree. pub fn block(&self, cache: &BlockCache, cid: &[u8]) -> Option> { match self.mem.blocks.get(cid) { Some(MemBlock { at: None, .. }) => None, Some(MemBlock { at: Some(At::Log(pos)), .. }) => Some( self.log_item(cache, *pos, Want::Block(cid)) .unwrap_or_else(|| { self.fail(format!("block {} missing from its frame", cid_string(cid))) }), ), _ => { let v = self.table_get(cache, &key(b'B', cid))?; let (_, _, at) = read_block_value(&v) .unwrap_or_else(|| self.fail("a block's entry that does not parse")); Some(v[at..].into()) } } } pub fn path(&self, cache: &BlockCache, path: &str) -> Option<(Vec, String)> { match self.mem.paths.get(path) { Some((p, _)) => p.as_ref().map(|(c, r)| (c.clone(), r.to_string())), None => { let v = self.table_get(cache, &key(b'P', path.as_bytes()))?; Some( read_path_value(&v) .unwrap_or_else(|| self.fail("a path's entry that does not parse")), ) } } } pub fn refs(&self, cache: &BlockCache, cid: &[u8]) -> Option<(u32, String)> { match self.mem.blocks.get(cid) { Some(b) => (b.refs > 0).then(|| (b.refs, b.rev.to_string())), None => { let v = self.table_get(cache, &key(b'B', cid))?; let (refs, rev, _) = read_block_value(&v) .unwrap_or_else(|| self.fail("a block's entry that does not parse")); Some((refs, rev.to_string())) } } } /// The records' paths and CIDs from `from` (or, `reverse`, before /// `from`, the last first) while they begin with `prefix`, at most `limit`. pub fn records( &self, cache: &BlockCache, prefix: &str, from: &str, reverse: bool, limit: usize, ) -> Vec<(String, Vec)> { let mut out: Vec<(String, Vec)> = Vec::new(); let in_range = |p: &str| p.starts_with(prefix); // The memtable's, in order. use std::ops::Bound::{Excluded, Included, Unbounded}; let mem: Vec<(&String, &Option)> = if reverse { self.mem .paths .range::((Unbounded, Excluded(from))) .rev() .take_while(|(p, _)| in_range(p)) .map(|(p, v)| (p, &v.0)) .collect() } else { self.mem .paths .range::((Included(from), Unbounded)) .take_while(|(p, _)| in_range(p)) .map(|(p, v)| (p, &v.0)) .collect() }; let mut mi = mem.into_iter().peekable(); let table: Box)>> = match &self.table { None => Box::new(std::iter::empty()), Some(t) => { let start = key(b'P', from.as_bytes()); let it = if reverse { t.iter_back(&start, None, cache) } else { t.iter(&start, None, cache) }; Box::new( it.map(|r| r.unwrap_or_else(|e| self.fail(e))) .take_while(|(k, _)| k.first() == Some(&b'P')) .map(|(k, v)| (String::from_utf8_lossy(&k[1..]).into_owned(), v)) .take_while(|(p, _)| in_range(p)), ) } }; let mut ti = table.peekable(); let before = |a: &str, b: &str| if reverse { a > b } else { a < b }; while out.len() < limit { let next = match (mi.peek(), ti.peek()) { (None, None) => break, (Some(_), None) => 0, (None, Some(_)) => 1, (Some((m, _)), Some((t, _))) if *m == t => 2, (Some((m, _)), Some((t, _))) => { if before(m, t) { 0 } else { 1 } } }; match next { 1 => { let (p, v) = ti.next().expect("peeked"); let (cid, _) = read_path_value(&v) .unwrap_or_else(|| self.fail("a path's entry that does not parse")); out.push((p, cid)); } _ => { if next == 2 { ti.next(); } let (p, v) = mi.next().expect("peeked"); if let Some((cid, _)) = v { out.push((p.clone(), cid.clone())); } } } } out } /// Give `f` every record's path, CID and the rev that last wrote it, in /// order of path, read as it goes. pub fn each_path(&self, cache: &BlockCache, mut f: impl FnMut(&str, &[u8], &str)) { let mut mi = self.mem.paths.iter().peekable(); let table: Box, Vec)>> = match &self.table { None => Box::new(std::iter::empty()), Some(t) => Box::new( t.iter(b"P", None, cache) .map(|r| r.unwrap_or_else(|e| self.fail(e))) .take_while(|(k, _)| k.first() == Some(&b'P')), ), }; let mut ti = table.peekable(); loop { let take_mem = match (mi.peek(), ti.peek()) { (None, None) => return, (Some(_), None) => true, (None, Some(_)) => false, (Some((p, _)), Some((k, _))) => p.as_bytes() <= &k[1..], }; if take_mem { let (p, (x, _)) = mi.next().expect("peeked"); if ti.peek().is_some_and(|(k, _)| k[1..] == *p.as_bytes()) { ti.next(); } if let Some((cid, rev)) = x { f(p, cid, rev); } } else { let (k, v) = ti.next().expect("peeked"); let (cid, rev) = read_path_value(&v) .unwrap_or_else(|| self.fail("a path's entry that does not parse")); f(&String::from_utf8_lossy(&k[1..]), &cid, &rev); } } } /// Every event it holds: its seq and when it was made, in order of seq. pub fn event_seqs(&self, cache: &BlockCache) -> Vec<(u64, u64)> { let mut out: BTreeMap = BTreeMap::new(); if let Some(t) = &self.table { table_events(t, cache, &mut out).unwrap_or_else(|e| self.fail(e)); } out.extend(self.mem.events.iter().map(|(seq, (time, _))| (*seq, *time))); out.into_iter().collect() } /// An event's frame, if it holds it. pub fn event_frame(&self, cache: &BlockCache, seq: u64) -> Option { if let Some((_, pos)) = self.mem.events.get(&seq) { return self .log_item(cache, *pos, Want::Event(seq)) .map(|b| Bytes::copy_from_slice(&b)); } self.table_get(cache, &key(b'E', &seq.to_be_bytes())) .map(Bytes::from) } /// What reads its tree's blocks while it changes: its files open, and /// the memtable's blocks as they are now. pub fn snapshot(&self, head: (Vec, Vec)) -> io::Result { let table = match &self.table { Some(t) => Some((t.clone(), t.file()?)), None => None, }; let mut blocks: Vec<(Vec, MemBlock)> = self .mem .blocks .iter() .map(|(c, b)| (c.clone(), b.clone())) .collect(); blocks.sort_by(|a, b| a.0.cmp(&b.0)); let mut logs = HashMap::new(); for (_, b) in &blocks { if let Some(At::Log(p)) = b.at && let std::collections::hash_map::Entry::Vacant(v) = logs.entry(p.generation) { v.insert(( File::open(self.layout.log(p.generation))?, self.number(p.generation), )); } } Ok(Snapshot { head, table, blocks, logs, }) } } /// A store's tree as it was when taken, read as it is sent. pub(crate) struct Snapshot { head: (Vec, Vec), table: Option<(Arc, Arc)>, blocks: Vec<(Vec, MemBlock)>, /// Each log it reads, by generation, and the number the cache holds it by. logs: HashMap, } impl Snapshot { /// Give `emit` the commit, then each block of the tree that a commit /// after rev `since` put in it (every one with none), in order of CID, /// each read as it is reached; stop when `emit` says to. pub fn run( self, cache: &BlockCache, since: Option<&str>, mut emit: impl FnMut(&[u8], &[u8]) -> bool, ) -> io::Result<()> { let after = |rev: &str| since.is_none_or(|s| rev > s); let commit_rev = match pds_repo::data::decode(&self.head.1) { Ok(V::Map(m)) => m .into_iter() .find(|(k, _)| k == "rev") .and_then(|(_, v)| if let V::Str(s) = v { Some(s) } else { None }) .unwrap_or_default(), _ => String::new(), }; if after(&commit_rev) && !emit(&self.head.0, &self.head.1) { return Ok(()); } let from_log = |pos: Pos, cid: &[u8]| -> io::Result> { let (file, number) = self .logs .get(&pos.generation) .ok_or_else(|| io::Error::other("a log not open"))?; let read = |offset: u64, len: usize| read_at(file, offset, len); frame_item(cache, *number, pos, &read, Want::Block(cid)) .map_err(|e| io::Error::new(io::ErrorKind::InvalidData, e))? .ok_or_else(|| { io::Error::new(io::ErrorKind::InvalidData, "a block missing from its frame") }) }; let mut mem = self.blocks.into_iter().peekable(); let mut table: Rows<'_, io::Error> = match &self.table { None => Box::new(std::iter::empty()), Some((t, f)) => Box::new( t.iter(b"B", Some(&**f), cache) .take_while(|r| r.as_ref().map_or(true, |(k, _)| k.first() == Some(&b'B'))), ), }; let mut next_table = table.next().transpose()?; loop { let take_mem = match (mem.peek(), &next_table) { (None, None) => return Ok(()), (Some(_), None) => true, (None, Some(_)) => false, (Some((c, _)), Some((k, _))) => c.as_slice() <= &k[1..], }; if take_mem { let (cid, b) = mem.next().expect("peeked"); let same = next_table.as_ref().is_some_and(|(k, _)| k[1..] == cid[..]); let table_value = if same { next_table.take() } else { None }; if same { next_table = table.next().transpose()?; } let Some(at) = b.at else { continue }; if !after(&b.rev) { continue; } let bytes = match at { At::Log(pos) => from_log(pos, &cid)?, At::Table => { let (_, v) = table_value.ok_or_else(|| { io::Error::new( io::ErrorKind::InvalidData, "a block the table should hold", ) })?; let (_, _, at) = read_block_value(&v).ok_or_else(|| { io::Error::new(io::ErrorKind::InvalidData, "a block's entry") })?; v[at..].to_vec() } }; if !emit(&cid, &bytes) { return Ok(()); } } else { let (k, v) = next_table.take().expect("peeked"); next_table = table.next().transpose()?; let (_, rev, at) = read_block_value(&v) .ok_or_else(|| io::Error::new(io::ErrorKind::InvalidData, "a block's entry"))?; if after(rev) && !emit(&k[1..], &v[at..]) { return Ok(()); } } } } } /// The events a table holds, each one's seq and when it was made, into `out`. fn table_events(t: &Table, cache: &BlockCache, out: &mut BTreeMap) -> Result<(), String> { for r in t.iter(b"D", None, cache) { let (k, v) = r.map_err(|e| e.to_string())?; if k.first() != Some(&b'D') { break; } let (Ok(seq), Ok(time)) = (<[u8; 8]>::try_from(&k[1..]), <[u8; 8]>::try_from(&v[..])) else { return Err("an event's entry that does not parse".into()); }; out.insert(u64::from_be_bytes(seq), u64::from_be_bytes(time)); } Ok(()) } /// Every event an account's files hold, its seq and when it was made, in /// order of seq, the greatest seq any event of its has had, and the /// greatest of those its log's compaction let go: what its store would /// answer once loaded (`Disk::event_seqs`, `Store::last_seq`, `let_go`), /// read without loading it. Its table's header and events and its /// log's entries of them are read, as a load replays the log, and nothing /// else of it is checked; nothing is deleted, cut back or made durable, no /// log is left open and nothing is kept in memory. For the firehose, which /// makes its index of every account's files where a data directory has /// none, and looks into an account's events for void ones. The caller /// sees that the store is not loaded meanwhile (`cache::Slot::events`, or /// of an account not loaded, `events::Firehose::adopt`). pub(crate) fn events_on_disk(ctx: &crate::cache::Ctx, did: &str) -> Result { let layout = crate::store::account_layout(&ctx.dir, did); let mut out: BTreeMap = BTreeMap::new(); let (generation, mut last, let_go) = match Table::open(&layout.checkpoint(), &ctx.blocks) { Ok(t) => { let read = (|| { // A table of the version before has none: a load folds it. let header = t .get(b"H", &ctx.blocks) .map_err(|e| e.to_string())? .ok_or("a checkpoint of the version before")?; table_events(&t, &ctx.blocks, &mut out)?; read_header(&header).ok_or_else(|| "a header that does not parse".to_string()) })(); ctx.blocks.forget(t.id()); read? } Err(e) if e.kind() == io::ErrorKind::NotFound => (0, 0, 0), Err(e) => return Err(e.to_string()), }; pds_store::read_log(&layout, generation, &mut |_, entries| { for e in entries.iter().filter(|e| e["t"] == "event") { let seq = e["seq"] .as_u64() .ok_or_else(|| "an event with no seq".to_string())?; let time = match e["time"].as_u64() { Some(t) => t, None => crate::events::event_time(&hex_of(&e["frame"])?).unwrap_or(0), }; out.insert(seq, time); last = last.max(seq); } Ok(()) }) .map_err(|e| e.to_string())?; Ok((out.into_iter().collect(), last, let_go)) } // ---- Loading ------------------------------------------------------------------------ /// A store read from its files: its repository, log, files and the rest. pub(crate) struct Loaded { pub repo: Repo, pub wal: pds_store::Wal, pub disk: Disk, pub small: Small, } /// Read an account's store: its table, if it has one, then its log after, /// replayed into the memtable one frame at a time. A log of commits of the /// kind before the tree was changed in place, and a table of the version /// before with the log after it, are folded into a table first. /// /// `durable` says that every frame the log's files hold is on disk /// (`cache::Slot::durable`): the log is then opened with no sync, unless /// there is something of it to mend (`pds_store::Wal::open_log_with`). A /// fold writes, and syncs what it writes: the log read again after one is /// durable whatever it was. pub(crate) fn load( ctx: &crate::cache::Ctx, did: &str, signing: &SigningKey, mut durable: bool, ) -> Result { for _ in 0..2 { // Said of the first try alone: one tried again for want of a file // descriptor may have mended what it then no longer finds. let mut told = durable; let layout = crate::store::account_layout(&ctx.dir, did); let at = |why: String| format!("{}: {why}", layout.dir.display()); let named = |why: String| format!("{}: {why}", layout.checkpoint().display()); let table = match Table::open(&layout.checkpoint(), &ctx.blocks) { Ok(t) => Some(Arc::new(t)), Err(e) if e.kind() == io::ErrorKind::NotFound => None, Err(e) => return Err(at(e.to_string())), }; // Fold a log into a table of this version, once. let fold = |wal: pds_store::Wal| { wal.set_fold(Arc::new(AccountFold { did: did.to_string(), key: signing.clone(), window: ctx.window, blocks: ctx.cache.fold_blocks(), account: Weak::new(), })); wal.compact() }; let mut small = match &table { Some(t) => { let s = t .get(b"S", &ctx.blocks) .map_err(|e| at(e.to_string()))? .ok_or_else(|| at("a checkpoint with no state".into()))?; match t.get(b"H", &ctx.blocks).map_err(|e| at(e.to_string()))? { Some(h) => Small::decode(&s, &h, did).map_err(named)?, None => { // A table of the version before: folded, with the // log after it, into one of this version; then // read again. let generation = before::generation(&s).map_err(named)?; drop(s); let wal = crate::log::retrying(|| { pds_store::Wal::open_log_with( &layout, generation, t.size(), Some(ctx.files.clone()), ctx.policy, std::mem::take(&mut told), &mut |_, _| Ok(()), ) }) .map_err(|e| at(e.to_string()))?; ctx.blocks.forget(t.id()); fold(wal).map_err(at)?; durable = true; continue; } } } None => Small::new(), }; let mut disk = Disk::new(layout.clone(), table); disk.let_go = small.let_go; let size = disk.table.as_ref().map_or(0, |t| t.size()); let generation = small.generation; let old = match &disk.table { Some(t) => Old::Table(t, None), None => Old::None, }; let holds = |m: &Memtable, p: &str| match m.paths.get(p) { Some((x, _)) => x.is_some(), None => disk.table.as_ref().is_some_and(|t| { t.get(&key(b'P', p.as_bytes()), &ctx.blocks) .ok() .flatten() .is_some() }), }; let mut mem = Memtable::default(); let wal = crate::log::retrying(|| { mem = Memtable::default(); pds_store::Wal::open_log_with( &layout, generation, size, Some(ctx.files.clone()), ctx.policy, std::mem::take(&mut told), &mut |pos, entries| { for e in &entries { mem.apply(&mut small, pos, e, &holds, old, &ctx.blocks)?; } Ok(()) }, ) }) .map_err(|e| at(e.to_string()))?; if mem.legacy { if disk.table.is_some() { return Err(at( "a commit of the kind before the tree was changed in place, after a checkpoint" .into(), )); } // Folded into a table, once; then read again. fold(wal).map_err(at)?; durable = true; continue; } disk.mem = mem; let mut repo = Repo::new(did.to_string(), signing.clone()); if small.has_commit() { repo.restore(small.head.clone(), small.counts, &small.tids.last()) .map_err(at)?; // The tree the latest commit names is the store's. if disk.block(&ctx.blocks, &repo.root).is_none() { return Err(at(format!( "the tree {}, which the latest commit signs, is not held", cid_string(&repo.root) ))); } } repo.tids.after(&small.tids.last()); return Ok(Loaded { repo, wal, disk, small, }); } Err(format!( "{did}: its log folded is still of the kind or the version before" )) } // ---- Compacting --------------------------------------------------------------------- /// An account's log's fold: the table of a generation, merged from the one /// before and the sealed logs after it; put in place under the account's /// lock, if its store is held, which reads it from then on. pub(crate) struct AccountFold { pub did: String, pub key: SigningKey, /// The backfill window, in milliseconds. pub window: u64, /// The bytes it may keep of what it reads to read it again /// (`cache::Cache::fold_blocks`). pub blocks: u64, /// The account, whose store reads the table once it is in place. pub account: Weak, } /// What a fold holds in memory while it merges, counted with its account's /// store until it ends (`cache::Slot::folding`): what it holds from the /// start, and the frames' indexes it makes as it goes (`Indexes`). struct Holding { account: Option>, bytes: std::cell::Cell, } impl Holding { fn new(account: &Weak, bytes: u64) -> Holding { let account = account.upgrade(); if let Some(a) = &account { a.store.folding(bytes); } Holding { account, bytes: bytes.into(), } } /// Count `bytes` more. fn more(&self, bytes: u64) { let n = self.bytes.get() + bytes; self.bytes.set(n); if let Some(a) = &self.account { a.store.folding(n); } } } impl Drop for Holding { fn drop(&mut self) { if let Some(a) = &self.account { a.store.folding(0); } } } /// Reads the items of the sealed logs' frames as the merge reaches them, /// each alone, through its frame's index (`Indexes`), whose bytes count /// with what the fold holds, if anything counts it. struct Frames<'a> { layout: &'a Layout, files: HashMap, indexes: Indexes, holding: Option<&'a Holding>, } impl Frames<'_> { fn item(&mut self, pos: Pos, want: Want) -> Result>, String> { let file = match self.files.entry(pos.generation) { std::collections::hash_map::Entry::Occupied(f) => f.into_mut(), std::collections::hash_map::Entry::Vacant(v) => { v.insert(File::open(self.layout.log(pos.generation)).map_err(|e| e.to_string())?) } }; let read = |offset: u64, len: usize| read_at(file, offset, len); let before = self.indexes.bytes; let found = self.indexes.item(pos, &read, want); if let Some(h) = self.holding && self.indexes.bytes > before { h.more(self.indexes.bytes - before); } found } } impl Fold for AccountFold { fn fold_files( &self, checkpoint: Option<&Path>, logs: &[PathBuf], generation: u64, out: &mut dyn Write, ) -> Result<(), String> { // What is read again is kept: the table's blocks records are looked // up in as the logs are replayed, and the places of the frames' // items (`Frames`). What the merge reads once, in order, is not. let cache = BlockCache::new(self.blocks); let passing = BlockCache::new(0); let table = match checkpoint { Some(p) => Some(Table::open(p, &cache).map_err(|e| e.to_string())?), None => None, }; let mut small = match &table { Some(t) => { let state = t .get(b"S", &cache) .map_err(|e| e.to_string())? .ok_or("a checkpoint with no state")?; match t.get(b"H", &cache).map_err(|e| e.to_string())? { Some(h) => Small::decode(&state, &h, &self.did)?, None => before::read(&state, &self.did)?, } } None => Small::new(), }; let spaces_old = match &table { Some(t) => Old::Table(t, None), None => Old::None, }; let layout = Layout::new( logs.first() .and_then(|p| p.parent()) .map_or_else(PathBuf::new, Path::to_path_buf), "repo", ); let first = generation - logs.len() as u64; let mut mem = Memtable::default(); let holds = |m: &Memtable, p: &str| match m.paths.get(p) { Some((x, _)) => x.is_some(), None => table.as_ref().is_some_and(|t| { t.get(&key(b'P', p.as_bytes()), &cache) .ok() .flatten() .is_some() }), }; for (i, p) in logs.iter().enumerate() { let g = first + i as u64; pds_store::read_sealed(p, |offset, len, entries| { for e in &entries { mem.apply( &mut small, Pos { generation: g, offset, len, }, e, &holds, spaces_old, &cache, )?; } Ok(()) })?; } if !small.has_commit() { return Err("an account with no commit yet".into()); } let now = crate::events::now_ms(); if mem.legacy { return legacy_fold( &self.did, &self.key, logs, generation, self.window, now, out, ); } let mut w = TableWriter::new( io::BufWriter::new(out), table.as_ref().map_or(0, |t| t.len()) + (mem.blocks.len() + mem.paths.len() + mem.events.len() * 2) as u64 + spaces::entries(&mem.spaces) + 2, ); // What it holds from here on: the state, where each entry of the // sealed logs is, and the blocks it keeps; and the frames' indexes, // as it makes them. let held = small.blobs.cost() + small.spaces.cost() + small.authority.cost() + small.notify.cost() + mem.cost() + self.blocks; let holding = Holding::new(&self.account, held); let view = View { mem: &mem.spaces, old: spaces_old, cache: &passing, }; let mut frames = Frames { layout: &layout, files: HashMap::new(), indexes: Indexes::default(), holding: Some(&holding), }; let werr = |e: io::Error| e.to_string(); let old = |prefix: u8| -> Rows<'_, String> { match &table { None => Box::new(std::iter::empty()), Some(t) => Box::new( t.iter(&[prefix], None, &passing) .map(|r| r.map_err(|e| e.to_string())) .take_while(move |r| { r.as_ref().map_or(true, |(k, _)| k.first() == Some(&prefix)) }), ), } }; // The tree's blocks. let mut mine: Vec<(&Vec, &MemBlock)> = mem.blocks.iter().collect(); mine.sort_by(|a, b| a.0.cmp(b.0)); let mut mi = mine.into_iter().peekable(); let mut ti = old(b'B').peekable(); loop { let take_mem = match (mi.peek(), ti.peek()) { (None, None) => break, (Some(_), None) => true, (None, Some(_)) => false, (Some((c, _)), Some(Ok((k, _)))) => c.as_slice() <= &k[1..], (_, Some(Err(e))) => return Err(e.clone()), }; if take_mem { let (cid, b) = mi.next().expect("peeked"); let same = matches!(ti.peek(), Some(Ok((k, _))) if k[1..] == cid[..]); let table_value = if same { ti.next().transpose()? } else { None }; let Some(at) = b.at else { continue }; let bytes = match at { At::Log(pos) => frames.item(pos, Want::Block(cid))?.ok_or_else(|| { format!("block {} missing from its frame", cid_string(cid)) })?, At::Table => { let (_, v) = table_value .ok_or_else(|| format!("block {} not in the table", cid_string(cid)))?; let (_, _, at) = read_block_value(&v).ok_or("a block's entry that does not parse")?; v[at..].to_vec() } }; w.add(&key(b'B', cid), &block_value(b.refs, &b.rev, &bytes)) .map_err(werr)?; } else { let (k, v) = ti.next().expect("peeked")?; w.add(&k, &v).map_err(werr)?; } } // The space repos' blob references. spaces::fold( spaces::REFS, view, &mut |pos, want| frames.item(pos, want), &mut |k, v| w.add(k, v).map_err(werr), )?; // The events in the window: when each was made, then its frame. // Of those let go, the greatest seq is kept (`Small::let_go`). let keep = |time: u64| time + 1000 + self.window >= now; let mut kept: BTreeMap)> = BTreeMap::new(); for r in old(b'D') { let (k, v) = r?; let (Ok(seq), Ok(time)) = (<[u8; 8]>::try_from(&k[1..]), <[u8; 8]>::try_from(&v[..])) else { return Err("an event's entry that does not parse".into()); }; let (seq, time) = (u64::from_be_bytes(seq), u64::from_be_bytes(time)); if keep(time) { kept.insert(seq, (time, None)); } else { small.let_go = small.let_go.max(seq); } } for (seq, (time, pos)) in &mem.events { if keep(*time) { kept.insert(*seq, (*time, Some(*pos))); } else { small.let_go = small.let_go.max(*seq); } } for (seq, (time, _)) in &kept { w.add(&key(b'D', &seq.to_be_bytes()), &time.to_be_bytes()) .map_err(werr)?; } let mut ei = old(b'E').peekable(); for (seq, (_, pos)) in &kept { let k = key(b'E', &seq.to_be_bytes()); let frame = match pos { Some(pos) => frames .item(*pos, Want::Event(*seq))? .ok_or_else(|| format!("event {seq} missing from its frame"))?, None => loop { match ei.next() { Some(Ok((tk, v))) if tk == k => break v, Some(Ok((tk, _))) if tk < k => continue, Some(Err(e)) => return Err(e), _ => return Err(format!("event {seq} not in the table")), } }, }; w.add(&k, &frame).map_err(werr)?; } w.add( b"H", &header_value(generation, small.last_seq, small.let_go), ) .map_err(werr)?; // The space repos' operations. spaces::fold( spaces::OPS, view, &mut |pos, want| frames.item(pos, want), &mut |k, v| w.add(k, v).map_err(werr), )?; // The paths. let mut mi = mem.paths.iter().peekable(); let mut ti = old(b'P').peekable(); loop { let take_mem = match (mi.peek(), ti.peek()) { (None, None) => break, (Some(_), None) => true, (None, Some(_)) => false, (Some((p, _)), Some(Ok((k, _)))) => p.as_bytes() <= &k[1..], (_, Some(Err(e))) => return Err(e.clone()), }; if take_mem { let (p, (x, _)) = mi.next().expect("peeked"); if matches!(ti.peek(), Some(Ok((k, _))) if k[1..] == *p.as_bytes()) { ti.next(); } if let Some((cid, rev)) = x { w.add(&key(b'P', p.as_bytes()), &path_value(cid, rev)) .map_err(werr)?; } } else { let (k, v) = ti.next().expect("peeked")?; w.add(&k, &v).map_err(werr)?; } } // The space repos' records, the rest of the state, and the records' bytes. spaces::fold( spaces::RECORDS, view, &mut |pos, want| frames.item(pos, want), &mut |k, v| w.add(k, v).map_err(werr), )?; w.add(b"S", &small.encode(&self.did, now)).map_err(werr)?; spaces::fold( spaces::VALUES, view, &mut |pos, want| frames.item(pos, want), &mut |k, v| w.add(k, v).map_err(werr), )?; let (mut out, _) = w.finish().map_err(werr)?; out.flush().map_err(werr) } fn install( &self, generation: u64, rename: &mut dyn FnMut() -> Result<(), String>, ) -> Result<(), String> { let Some(a) = self.account.upgrade() else { return rename(); }; a.store.installing(|st| { rename()?; let Some(st) = st else { return Ok(()) }; let table = Table::open(&st.disk.layout.checkpoint(), &st.ctx.blocks) .map_err(|e| e.to_string())?; let (_, _, let_go) = table .get(b"H", &st.ctx.blocks) .map_err(|e| e.to_string())? .and_then(|h| read_header(&h)) .ok_or("a checkpoint with no header")?; (st.disk.let_go, st.disk.table_cost) = (let_go, table.cost()); if let Some(old) = st.disk.table.replace(Arc::new(table)) { st.ctx.blocks.forget(old.id()); } st.disk.mem.folded(generation); let numbers: Vec = { let mut n = st .disk .numbers .lock() .unwrap_or_else(PoisonError::into_inner); let gone: Vec = n.keys().filter(|g| **g < generation).copied().collect(); gone.into_iter().filter_map(|g| n.remove(&g)).collect() }; for n in numbers { st.ctx.blocks.forget(n); } Ok(()) }) } } /// The table of a log of the kind before the tree was changed in place: /// replayed whole in memory, as servers then did, its tree rebuilt. fn legacy_fold( did: &str, signing: &SigningKey, logs: &[PathBuf], generation: u64, window: u64, now: u64, out: &mut dyn Write, ) -> Result<(), String> { let mut small = Small::new(); let mut repo = pds_repo::full::Repo::new(did.to_string(), signing.clone()); let mut events: BTreeMap)> = BTreeMap::new(); let cache = BlockCache::new(4 << 20); let layout = Layout::new( logs.first() .and_then(|p| p.parent()) .map_or_else(PathBuf::new, Path::to_path_buf), "repo", ); let first = generation - logs.len() as u64; let mut space_mem = SpaceMem::default(); for (i, p) in logs.iter().enumerate() { pds_store::read_sealed(p, |offset, len, entries| { for e in &entries { match e["t"].as_str() { Some("event") => { let seq = e["seq"] .as_u64() .ok_or_else(|| format!("an event with no seq: {e}"))?; let frame = hex_of(&e["frame"])?; let time = crate::events::event_time(&frame).unwrap_or(0); if events.last_key_value().is_some_and(|(l, _)| *l >= seq) || repo.rev.is_empty() { return Err(format!("event {seq} out of order")); } small.last_seq = seq; events.insert(seq, (time, frame)); } Some("commit") => { let path = |p: &Json| { p.as_str() .map(str::to_string) .ok_or_else(|| format!("a commit with {p} for a path")) }; let list = |k: &str| { e[k].as_array() .ok_or_else(|| format!("a commit with no {k}")) }; let c = Change { rev: e["rev"].as_str().ok_or("a commit with no rev")?.to_string(), head_bytes: hex_of(&e["head"])?, puts: list("puts")? .iter() .map(|p| Ok((path(&p[0])?, p[1].clone()))) .collect::>()?, dels: list("dels")?.iter().map(path).collect::>()?, added: match e.get("added") { Some(a) => a .as_array() .ok_or("a commit whose added is not a list")? .iter() .map(hex_of) .collect::>()?, None => vec![], }, ..Default::default() }; repo.load(&c)?; small.blobs.committed(&c); small.blobs.take_doomed(); for p in &c.dels { small.takedowns.remove(p); } small.tids.after(&c.rev); small.head = c.head_bytes.clone(); } Some(space_repo::ENTRY | space_repo::IMPORT | space_repo::DROP) if small.unmarked.is_none() => { let pos = Pos { generation: first + i as u64, offset, len, }; small.spaces.replay( e, pos, &mut space_mem, Old::None, &cache, &mut small.tids, &mut small.blobs, )?; } _ => { let records = &repo.records; small.replay(e, |p| records.contains_key(p))?; } } } Ok(()) })?; } if repo.rev.is_empty() { return Err("an account with no commit yet".into()); } repo.finish_load()?; let revs: HashMap<&[u8], &str> = repo.block_revs().collect(); let mut entries: BTreeMap, Vec> = BTreeMap::new(); for (cid, bytes) in repo.tree_nodes() { entries.insert( key(b'B', cid), block_value(1, revs.get(cid).copied().unwrap_or_default(), bytes), ); } let mut refs: HashMap<&[u8], u32> = HashMap::new(); for r in repo.records.values() { *refs.entry(r.cid.as_slice()).or_default() += 1; } for (path, r) in &repo.records { entries.insert( key(b'B', &r.cid), block_value( refs[r.cid.as_slice()], revs.get(r.cid.as_slice()).copied().unwrap_or_default(), &r.bytes, ), ); entries.insert( key(b'P', path.as_bytes()), path_value(&r.cid, &repo.written[path]), ); } for (seq, (time, frame)) in events.iter().filter(|(_, (t, _))| t + 1000 + window >= now) { entries.insert(key(b'D', &seq.to_be_bytes()), time.to_be_bytes().to_vec()); entries.insert(key(b'E', &seq.to_be_bytes()), frame.clone()); } small.counts = (repo.records.len() as u64, repo.block_count() as u64 - 1); small.tids.after(&repo.tids.last()); small.let_go = events .iter() .filter(|(_, (t, _))| t + 1000 + window < now) .map(|(seq, _)| *seq) .max() .unwrap_or(0); entries.insert( b"H".to_vec(), header_value(generation, small.last_seq, small.let_go), ); entries.insert(b"S".to_vec(), small.encode(did, now)); let mut frames = Frames { layout: &layout, files: HashMap::new(), indexes: Indexes::default(), holding: None, }; let view = View { mem: &space_mem, old: Old::None, cache: &cache, }; for section in [spaces::REFS, spaces::OPS, spaces::RECORDS, spaces::VALUES] { spaces::fold( section, view, &mut |pos, want| frames.item(pos, want), &mut |k, v| { entries.insert(k.to_vec(), v.to_vec()); Ok(()) }, )?; } let mut w = TableWriter::new(io::BufWriter::new(out), entries.len() as u64); for (k, v) in &entries { w.add(k, v).map_err(|e| e.to_string())?; } let (mut out, _) = w.finish().map_err(|e| e.to_string())?; out.flush().map_err(|e| e.to_string()) } // ---- The store's reads ---------------------------------------------------------------- impl Store { /// What its repository's blocks are read through. pub(crate) fn source(&self) -> Src<'_> { self.disk.source(&self.ctx.blocks) } /// The record at `path`. pub(crate) fn record(&self, path: &str) -> Option { self.repo.get(&self.source(), path) } /// Whether a record is at `path`. pub(crate) fn holds(&self, path: &str) -> bool { self.disk.path(&self.ctx.blocks, path).is_some() } /// The records of a collection from `from`, or before it if `reverse`, /// the last first, at most `limit`: each one's path and record. pub(crate) fn records( &self, collection: &str, from: &str, reverse: bool, limit: usize, ) -> Vec<(String, Record)> { let prefix = format!("{collection}/"); let list = self .disk .records(&self.ctx.blocks, &prefix, from, reverse, limit); list.into_iter() .map(|(p, cid)| { let bytes = self .disk .block(&self.ctx.blocks, &cid) .unwrap_or_else(|| self.disk.fail(format!("record {p} missing"))); let value = decode(&bytes).unwrap_or_else(|e| self.disk.fail(format!("record {p}: {e}"))); ( p, Record { cid, bytes: bytes.to_vec(), value, }, ) }) .collect() } /// The collections it holds records of, in order. pub(crate) fn collections(&self) -> Vec { let mut out: Vec = Vec::new(); let mut from = String::new(); while let Some((p, _)) = self .disk .records(&self.ctx.blocks, "", &from, false, 1) .into_iter() .next() { let c = p.split('/').next().unwrap_or_default().to_string(); // Past every path of the collection: `/` is followed by nothing before `0`. from = format!("{c}0"); out.push(c); } out } /// Give `f` every record's path, CID and the rev that last wrote it, in order of path. pub(crate) fn each_path(&self, f: impl FnMut(&str, &[u8], &str)) { self.disk.each_path(&self.ctx.blocks, f); } /// The greatest seq of an event of its let go when its log was compacted. pub(crate) fn let_go(&self) -> u64 { self.disk.let_go } /// Its events: each one's seq and when it was made. pub(crate) fn event_seqs(&self) -> Vec<(u64, u64)> { self.disk.event_seqs(&self.ctx.blocks) } /// An event's frame, if it holds it. pub(crate) fn event_frame(&self, seq: u64) -> Option { self.disk.event_frame(&self.ctx.blocks, seq) } /// Its tree as it is now, to read as it is sent. pub(crate) fn snapshot(&self) -> io::Result { self.disk .snapshot((self.repo.head.clone(), self.repo.head_bytes().to_vec())) } } #[cfg(test)] mod tests { use crate::testing::*; use pds_repo::data::{cid_string, decode, to_json}; use serde_json::{Value as Json, json}; use std::collections::BTreeMap; fn params(p: &[(&str, &str)]) -> Vec<(String, String)> { p.iter() .map(|(k, v)| (k.to_string(), v.to_string())) .collect() } /// Every record listRecords pages through, newest first or not, `limit` at a time. async fn listed(s: &crate::Shared, did: &str, reverse: bool) -> Vec<(String, Json)> { let mut out = Vec::new(); let mut cursor: Option = None; loop { let mut p = params(&[ ("repo", did), ("collection", "a.b.c"), ("limit", "7"), ("reverse", if reverse { "true" } else { "false" }), ]); if let Some(c) = &cursor { p.push(("cursor".into(), c.clone())); } let got = call_with(s, "com.atproto.repo.listRecords", None, &p, Json::Null) .await .unwrap(); let page = got["records"].as_array().unwrap().clone(); out.extend(page.iter().map(|r| { ( r["uri"] .as_str() .unwrap() .rsplit('/') .next() .unwrap() .to_string(), r["value"].clone(), ) })); match got["cursor"].as_str() { Some(c) if !page.is_empty() => cursor = Some(c.to_string()), _ => return out, } } } /// What the server answers of `did`'s records, as `want` says it holds /// them: by listRecords both ways, getRecord, and getRepo whole. async fn check(s: &crate::Shared, did: &str, want: &BTreeMap) { let asc: Vec<(String, Json)> = want.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); assert_eq!(listed(s, did, true).await, asc); let mut desc = asc.clone(); desc.reverse(); assert_eq!(listed(s, did, false).await, desc); for (k, v) in want { let got = call_with( s, "com.atproto.repo.getRecord", None, ¶ms(&[("repo", did), ("collection", "a.b.c"), ("rkey", k)]), Json::Null, ) .await .unwrap(); assert_eq!(&got["value"], v); } let car = store_of(s, did, |st| { crate::sync::CarStream::of(st, None) .unwrap() .bytes() .unwrap() }); let (roots, blocks) = pds_repo::read_car(&car).unwrap(); assert_eq!(roots, vec![repo_of(s, did, |r| r.head.clone())]); let mut records: Vec = blocks .iter() .filter_map(|(_, b)| decode(b).ok()) .map(|v| to_json(&v)) .filter(|v| v["$type"] == "a.b.c") .collect(); records.sort_by_key(|v| v.to_string()); let mut wanted: Vec = want.values().cloned().collect(); wanted.sort_by_key(|v| v.to_string()); wanted.dedup(); assert_eq!(records, wanted); // Every block is held, and none twice. let cids: Vec = blocks.iter().map(|(c, _)| cid_string(c)).collect(); let mut unique = cids.clone(); unique.sort(); unique.dedup(); assert_eq!(unique.len(), cids.len()); assert_eq!(cids.len() as u64, repo_of(s, did, |r| r.block_count())); } /// Writes, rewrites and deletes across many compactions, the account's /// store let go and loaded again between them, and the server started /// again: every read answers what the writes left, from the table, the /// log after it, or both. #[tokio::test] async fn reads_across_compactions() { let plc = plc().await; let dir = scratch("ckpt-reads"); let opened = |dir: &std::path::Path| { open_with(dir, &plc, |c| { c.load_all = false; c.log_floor = 2048; }) }; let mut s = opened(&dir); let (did, token) = create(&s, "alice").await; let mut want: BTreeMap = BTreeMap::new(); let mut n = 0; for round in 0..6 { for i in 0..25 { n += 1; let k = format!("k{:02}", (i * 7 + round * 3) % 40); if i % 5 == 4 && want.contains_key(&k) { call( &s, "com.atproto.repo.deleteRecord", Some(&token), json!({ "repo": did, "collection": "a.b.c", "rkey": k }), ) .await .unwrap(); want.remove(&k); continue; } // Some records the same as another's, so that a block is held by two paths. let value = json!({ "$type": "a.b.c", "n": if i % 6 == 0 { 0 } else { n } }); call( &s, "com.atproto.repo.putRecord", Some(&token), json!({ "repo": did, "collection": "a.b.c", "rkey": k, "record": value }), ) .await .unwrap(); want.insert(k, value); } let wal = store_of(&s, &did, |st| st.wal.clone()); wal.wait_compacted(); assert!(wal.checkpoint_generation() > 0, "never compacted"); drop(wal); check(&s, &did, &want).await; if round % 2 == 0 { let a = s.account(&did).unwrap(); assert!(a.store.evict()); check(&s, &did, &want).await; } else { drop(s); s = opened(&dir); check(&s, &did, &want).await; } } let _ = std::fs::remove_dir_all(&dir); } async fn put(s: &crate::Shared, did: &str, token: &str, k: &str, value: &Json) { call( s, "com.atproto.repo.putRecord", Some(token), json!({ "repo": did, "collection": "a.b.c", "rkey": k, "record": value }), ) .await .unwrap(); } /// The generation of `did`'s table, once no compaction of its log runs. fn compacted(s: &crate::Shared, did: &str) -> u64 { let wal = store_of(s, did, |st| st.wal.clone()); wal.wait_compacted(); wal.checkpoint_generation() } /// A repository being sent is read whole from the table it began with, /// though a compaction replaces that table meanwhile, and the table's /// file is closed once it is sent. Of more accounts' tables than may be /// open at once, no more files are open than that, each account read /// from its file all the same; and a store let go closes its table's. #[tokio::test] async fn tables_replaced_and_held_open() { let plc = plc().await; let dir = scratch("ckpt-open"); let s = open_with(&dir, &plc, |c| { c.load_all = false; c.log_floor = 2048; }); let open = || s.ctx.blocks.open_files(); let (did, token) = create(&s, "alice").await; let mut want: Vec = Vec::new(); for i in 0..30 { let value = json!({ "$type": "a.b.c", "n": i, "t": "x".repeat(200) }); put(&s, &did, &token, &format!("k{i:02}"), &value).await; want.push(value); } let first = compacted(&s, &did); assert!(first > 0, "never compacted"); assert_eq!(open(), 1); let (head, stream) = store_of(&s, &did, |st| { ( st.repo.head.clone(), crate::sync::CarStream::of(st, None).unwrap(), ) }); // Every record written again, until another table is in its place. let mut n = 0; while compacted(&s, &did) == first { let value = json!({ "$type": "a.b.c", "n": 1000 + n }); put(&s, &did, &token, &format!("k{:02}", n % 30), &value).await; n += 1; assert!(n < 1000, "never compacted again"); } assert_eq!(open(), 2); let (roots, blocks) = pds_repo::read_car(&stream.bytes().unwrap()).unwrap(); assert_eq!(roots, vec![head]); let mut records: Vec = blocks .iter() .filter_map(|(_, b)| decode(b).ok()) .map(|v| to_json(&v)) .filter(|v| v["$type"] == "a.b.c") .collect(); records.sort_by_key(|v| v["n"].as_u64()); assert_eq!(records, want); assert_eq!(open(), 1); let mut dids = vec![did]; let share = s.config.share; for i in 0..share + 5 { let (did, token) = create(&s, &format!("user{i}")).await; let value = json!({ "$type": "a.b.c", "t": "x".repeat(3000) }); put(&s, &did, &token, "k00", &value).await; assert!(compacted(&s, &did) > 0, "never compacted"); assert!(open() <= share); dids.push(did); } assert_eq!(open(), share); for did in &dids { // Nothing of its table in memory: the record is read from its file. store_of(&s, did, |st| { st.ctx.blocks.forget(st.disk.table.as_ref().unwrap().id()) }); let got = call_with( &s, "com.atproto.repo.getRecord", None, ¶ms(&[("repo", did), ("collection", "a.b.c"), ("rkey", "k00")]), Json::Null, ) .await .unwrap(); assert_eq!(got["value"]["$type"], "a.b.c"); assert_eq!(open(), share); } for (i, did) in dids.iter().enumerate() { assert!(s.account(did).unwrap().store.evict()); assert!(open() < dids.len() - i); } assert_eq!(open(), 0); let _ = std::fs::remove_dir_all(&dir); } /// A commit's frame is JSON with holes, and each of its tree's nodes and /// its event is read alone, by the frame's index, as the bytes the hole /// holds: only those bytes are read, as they are, nothing decoded. With /// no index yet, the whole frame is read once and indexed. #[tokio::test] async fn an_item_of_a_frame_with_holes_is_its_bytes_alone() { use super::{BYTES, Want, find, frame_item, index, read_at}; use pds_store::table::BlockCache; let plc = plc().await; let dir = scratch("ckpt-holes"); let s = open(&dir, &plc); let (did, token) = create(&s, "alice").await; for i in 0..40 { call( &s, "com.atproto.repo.createRecord", Some(&token), json!({ "repo": did, "collection": "a.b.c", "record": record(i) }), ) .await .unwrap(); } let layout = crate::store::account_layout(&dir, &did); let generation = store_of(&s, &did, |st| st.wal.generation()); let path = layout.log(generation); // The last frame of the log: the last commit's. let mut last = None; pds_store::scan_file(&path, |offset, len, entries| { last = Some((offset, len, entries)); Ok(()) }) .unwrap() .unwrap(); let (offset, len, entries) = last.unwrap(); let pos = pds_store::Pos { generation, offset, len, }; let file = std::fs::File::open(&path).unwrap(); let frame = read_at(&file, offset, len as usize).unwrap(); assert_eq!(frame[pds_store::HEADER], pds_store::HOLES); let commit = entries.iter().find(|e| e["t"] == "commit").unwrap(); let event = entries.iter().find(|e| e["t"] == "event").unwrap(); let unhex = |v: &Json| hex::decode(v.as_str().unwrap()).unwrap(); let nodes: Vec<(Vec, Vec)> = commit["tree"] .as_array() .unwrap() .iter() .map(|n| (unhex(&n[0]), unhex(&n[1]))) .collect(); assert!(!nodes.is_empty()); let (seq, event_frame) = (event["seq"].as_u64().unwrap(), unhex(&event["frame"])); let reads = std::cell::RefCell::new(Vec::new()); let read = |at: u64, n: usize| { reads.borrow_mut().push((at, n)); read_at(&file, at, n) }; let cache = BlockCache::new(1 << 20); let got = frame_item(&cache, 1, pos, &read, Want::Event(seq)).unwrap(); assert_eq!(got, Some(event_frame.clone())); assert_eq!( reads.take(), [(offset, len as usize)], "the frame, to index it" ); let ix = index(&frame[pds_store::HEADER..]).unwrap().unwrap(); let mut wants: Vec<(Want, Vec)> = nodes .iter() .map(|(cid, node)| (Want::Block(cid), node.clone())) .collect(); wants.push((Want::Event(seq), event_frame)); for (want, bytes) in wants { let (how, start, n) = find(&ix, want).unwrap(); assert_eq!((how, n), (BYTES, bytes.len())); let got = frame_item(&cache, 1, pos, &read, want).unwrap(); assert_eq!(got, Some(bytes.clone())); let at = offset + (pds_store::HEADER + start) as u64; assert_eq!(reads.take(), [(at, bytes.len())], "its bytes alone"); assert_eq!(&frame[(at - offset) as usize..][..bytes.len()], &bytes[..]); } let _ = std::fs::remove_dir_all(&dir); } /// A fold reads each frame of its logs whole once, to index it, and /// then each item alone, however large the frame's index. An import's /// frame, one commit of a whole repository, has an index larger than the /// fold's block cache keeps any entry (an eighth of it, 4 MiB at most), /// which was made again, the whole frame read, for each of its items: /// so the import's log is compacted at once, as a write's is. #[tokio::test] async fn a_fold_indexes_each_frame_once() { use super::{ENTRY, Indexes, Want, read_at}; use axum::http::{HeaderMap, HeaderValue, Method, header}; const RECORDS: usize = 12_000; let plc = plc().await; let dir = scratch("ckpt-fold-index"); // Compacted only when the test says. let s = open_with(&dir, &plc, |c| c.log_floor = 1 << 30); let (did, token) = create(&s, "alice").await; // A repository of its records, imported whole: one frame. let key = k256::ecdsa::SigningKey::from_slice(&[5u8; 32]).unwrap(); let mut repo = pds_repo::full::Repo::new(did.clone(), key); repo.init(); for batch in (0..RECORDS).collect::>().chunks(200) { let ops = batch .iter() .map(|i| pds_repo::Op::Create { collection: "a.b.c".into(), rkey: Some(format!("k{i:05}")), value: pds_repo::data::from_json(&record(*i as i64)).unwrap(), }) .collect(); repo.apply(ops, None).unwrap(); } let car = repo.car(); let mut headers = HeaderMap::new(); headers.insert( header::CONTENT_TYPE, HeaderValue::from_static("application/vnd.ipld.car"), ); headers.insert( header::AUTHORIZATION, HeaderValue::from_str(&format!("Bearer {token}")).unwrap(), ); let authorization = crate::authorization(&headers); let call = crate::Call { nsid: "com.atproto.repo.importRepo", method: &Method::POST, params: &[], body: &car, bearer: crate::sessions::Bearer::of(authorization.as_deref()), headers: &headers, client: "127.0.0.1".into(), charged: std::sync::OnceLock::new(), http: None, }; assert!(matches!( crate::answer(&s, &call).await, Ok(crate::Resp::Nothing) )); // The import's frame, and its items: its records and tree nodes. let layout = crate::store::account_layout(&dir, &did); let generation = store_of(&s, &did, |st| st.wal.generation()); let path = layout.log(generation); let mut found = None; pds_store::scan_file(&path, |offset, len, entries| { if let Some(c) = entries .iter() .find(|e| e["t"] == "commit" && e["puts"].as_array().unwrap().len() == RECORDS) { found = Some((offset, len, c.clone())); } Ok(()) }) .unwrap() .unwrap(); let (offset, len, commit) = found.unwrap(); let unhex = |v: &Json| hex::decode(v.as_str().unwrap()).unwrap(); let mut cids: Vec> = commit["puts"] .as_array() .unwrap() .iter() .map(|p| unhex(&p[2])) .collect(); cids.extend( commit["tree"] .as_array() .unwrap() .iter() .map(|n| unhex(&n[0])), ); assert!( cids.len() * ENTRY > (4 << 20) / 8, "an index the fold's cache would keep" ); // Read as the fold reads them: the frame whole once, then each item alone. let pos = pds_store::Pos { generation, offset, len, }; let file = std::fs::File::open(&path).unwrap(); let whole = std::cell::Cell::new(0); let read = |at: u64, n: usize| { if (at, n) == (offset, len as usize) { whole.set(whole.get() + 1); } read_at(&file, at, n) }; let mut indexes = Indexes::default(); for cid in &cids { let block = indexes.item(pos, &read, Want::Block(cid)).unwrap(); assert!(block.is_some(), "{} missing", cid_string(cid)); } assert_eq!(whole.get(), 1, "the frame read whole for each of its items"); // And so the log is compacted in a moment, not in the time it takes // to read the frame once for each item. let wal = store_of(&s, &did, |st| st.wal.clone()); let started = std::time::Instant::now(); wal.compact().unwrap(); let took = started.elapsed(); assert!( took < std::time::Duration::from_secs(30), "compacted in {took:?}" ); store_of(&s, &did, |st| { st.ctx.blocks.forget(st.disk.table.as_ref().unwrap().id()) }); assert_eq!(records_of(&s, &did).len(), RECORDS); let _ = std::fs::remove_dir_all(&dir); } /// The notifications' part of a table: written and read back whole, /// lapsed registrations and kept notices too. #[test] fn notify_state_round_trips() { use super::{Small, read_notify}; use crate::space_notify::{Kept, Notice, Owed, Registration, Schedule}; use pds_repo::data::V; let m = "at://did:plc:alicealicealicealicealic/space/com.example.forum/m".to_string(); let q = "at://did:plc:elsewhereelsewhereelsewhe/space/com.example.forum/q"; let at = Schedule { n: 1, due: 10, until: 20, }; let mut k = Kept::default(); k.queue.insert( q.to_string(), crate::space_notify::Pending { rev: "3jzfcijpj2z2a".into(), data: vec![1; 32], at, }, ); let pair = |e: &str, t: &str| (e.to_string(), t.to_string()); k.register( m.clone(), pair("https://a.example", "a"), Registration { expires: 5, noticed: true, }, ); k.register( m.clone(), pair("https://b.example/", ""), Registration { expires: 9, noticed: false, }, ); k.notices.insert( (m.clone(), pair("https://a.example", "a")), Notice { owed: Owed::Expired { space_rev: "3jzfcijpj2z2b".into(), lapse: 5, }, at, }, ); k.notices.insert( (m.clone(), pair("https://c.example", "c")), Notice { owed: Owed::Deleted, at, }, ); let mut small = Small::new(); small.notify = k.clone(); let state = pds_repo::data::decode(&small.encode("did:plc:alicealicealicealicealic", 0)).unwrap(); let V::Map(fields) = state else { panic!("a state that is no map") }; let notify = fields.into_iter().find(|(k, _)| k == "notify").unwrap().1; assert_eq!(read_notify(notify).unwrap(), k); } }