chadtmiller.com/monolith
An atproto PDS
0
0
//! 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<u8> {
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<u8> {
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<u8> {
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<u8>, 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<Vec<u8>, 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<u8> {
[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<u8>,
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<String, String>,
/// 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<String>,
/// A handle change recorded and not settled.
pub pending: Option<Pending>,
/// 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<Unmarked>,
}
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<u8> {
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<Small, String> {
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<Small, String> {
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::<Result<Vec<_>, _>>()
})?;
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::<Result<Vec<_>, _>>()?;
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::<Result<Vec<_>, _>>()?;
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<String> = 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<String> = 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<T>(x: Option<T>, f: impl FnOnce(T) -> V) -> V {
x.map_or(V::Null, f)
}
fn map<const N: usize>(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<const N: usize>(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<String, String> {
if let V::Str(s) = v {
Ok(s)
} else {
Err(format!("{what} is not a string"))
}
}
fn as_uint(v: V, what: &str) -> Result<u64, String> {
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<Vec<u8>, String> {
if let V::Bytes(b) = v {
Ok(b)
} else {
Err(format!("{what} is not bytes"))
}
}
fn as_list(v: V, what: &str) -> Result<Vec<V>, 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<T>(v: V, f: impl FnOnce(V) -> Result<T, String>) -> Result<Option<T>, String> {
if v == V::Null {
Ok(None)
} else {
f(v).map(Some)
}
}
/// Whether keys are in strictly ascending order.
fn ascending<K: PartialOrd>(keys: impl IntoIterator<Item = K>) -> bool {
let mut last: Option<K> = 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<Kept, String> {
let [queue, registrations, notices] =
fields(v, ["queue", "registrations", "notices"], "notify")?;
let schedule = |n: V, due: V, until: V, what: &str| -> Result<Schedule, String> {
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<str>,
pub refs: u32,
pub at: Option<At>,
pub generation: u64,
}
/// A record as a path has it: its CID and the rev that wrote it.
pub(crate) type Written = (Vec<u8>, Arc<str>);
/// 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<dyn Iterator<Item = Result<(Vec<u8>, Vec<u8>), 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<Vec<u8>, 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<String, (Option<Written>, u64)>,
/// Each event: when it was made, and its frame's place.
pub events: BTreeMap<u64, (u64, Pos)>,
/// 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<u8>)>,
dels: Vec<String>,
tree: Vec<Vec<u8>>,
gone: Vec<Vec<u8>>,
refs: Vec<(Vec<u8>, 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<u8>, 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<Written>, 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<str> = Arc::from(c.rev);
let gone = |rev: &Arc<str>| 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<String> = list("dels")?.iter().map(path).collect::<Result<_, _>>()?;
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::<Result<Vec<_>, _>>()?;
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<Vec<u8>, 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<bool, String>,
) -> Result<(), String> {
fn parse<'a, T: serde::Deserialize<'a>>(s: &'a str) -> Result<T, String> {
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::<Vec<&RawValue>>(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::<Vec<(&str, &str)>>(tree)? {
if !f(Raw::Node(cid, data(bytes)))? {
return Ok(());
}
}
}
for p in parse::<Vec<Vec<&RawValue>>>(field("puts").unwrap_or("[]"))? {
let (Some(value), Some(cid)) = (p.get(1), p.get(2)) else {
continue;
};
let Some(cid) = parse::<Option<&str>>(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::<String>(space), parse::<String>(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::<Vec<(String, &RawValue)>>(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<Vec<u8>, 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<Vec<u8>, 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<u8>) {
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<Option<Vec<u8>>, 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<Vec<u8>, 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<Option<Vec<u8>>, 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<Vec<u8>>,
want: Want,
) -> Result<Option<Vec<u8>>, 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<Vec<u8>>,
want: Want,
) -> Result<Option<Vec<u8>>, 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<Vec<u8>>, Option<Vec<u8>>);
/// 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<Vec<u8>>,
want: Want,
) -> Result<Indexed, String> {
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<Vec<u8>>) -> Result<Option<Vec<u8>>, 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<u8>>,
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<Vec<u8>>,
want: Want,
) -> Result<Option<Vec<u8>>, 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<Vec<u8>> {
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<Arc<Table>>,
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<HashMap<u64, u64>>,
}
/// 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<Arc<[u8]>> {
self.disk.block(self.cache, cid)
}
fn path(&self, path: &str) -> Option<(Vec<u8>, 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<Arc<Table>>) -> 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<Arc<[u8]>> {
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<Vec<u8>> {
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<Arc<[u8]>> {
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<u8>, 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<u8>)> {
let mut out: Vec<(String, Vec<u8>)> = 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<Written>)> = if reverse {
self.mem
.paths
.range::<str, _>((Unbounded, Excluded(from)))
.rev()
.take_while(|(p, _)| in_range(p))
.map(|(p, v)| (p, &v.0))
.collect()
} else {
self.mem
.paths
.range::<str, _>((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<dyn Iterator<Item = (String, Vec<u8>)>> = 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<dyn Iterator<Item = (Vec<u8>, Vec<u8>)>> = 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<u64, u64> = 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<Bytes> {
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<u8>, Vec<u8>)) -> io::Result<Snapshot> {
let table = match &self.table {
Some(t) => Some((t.clone(), t.file()?)),
None => None,
};
let mut blocks: Vec<(Vec<u8>, 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<u8>, Vec<u8>),
table: Option<(Arc<Table>, Arc<File>)>,
blocks: Vec<(Vec<u8>, MemBlock)>,
/// Each log it reads, by generation, and the number the cache holds it by.
logs: HashMap<u64, (File, u64)>,
}
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<Vec<u8>> {
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<u64, u64>) -> 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<EventsOnDisk, String> {
let layout = crate::store::account_layout(&ctx.dir, did);
let mut out: BTreeMap<u64, u64> = 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<Loaded, String> {
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<Account>,
}
/// 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<Arc<Account>>,
bytes: std::cell::Cell<u64>,
}
impl Holding {
fn new(account: &Weak<Account>, 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<u64, File>,
indexes: Indexes,
holding: Option<&'a Holding>,
}
impl Frames<'_> {
fn item(&mut self, pos: Pos, want: Want) -> Result<Option<Vec<u8>>, 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<u8>, &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<u64, (u64, Option<Pos>)> = 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<u64> = {
let mut n = st
.disk
.numbers
.lock()
.unwrap_or_else(PoisonError::into_inner);
let gone: Vec<u64> = 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<u64, (u64, Vec<u8>)> = 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::<Result<_, String>>()?,
dels: list("dels")?.iter().map(path).collect::<Result<_, _>>()?,
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::<Result<_, _>>()?,
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<u8>, Vec<u8>> = 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<Record> {
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<String> {
let mut out: Vec<String> = 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<Bytes> {
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<Snapshot> {
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<String> = 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<String, Json>) {
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<Json> = 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<Json> = 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<String> = 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<String, Json> = 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<Json> = 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<Json> = 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<u8>, Vec<u8>)> = 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<u8>)> = 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::<Vec<_>>().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<Vec<u8>> = 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);
}
}