vole_document/store/
seed.rs

1//! The procedural seed store (Phase 11).
2//!
3//! Phase 9 externalized *coarse* object-table entries and lost to per-file LZ
4//! and to content-defined chunking: the granularity was wrong and most
5//! representation state stayed embedded. Phase 11 instead persists **fine-
6//! grained procedural seed nodes**, one blob per node, keyed by a
7//! domain-separated content id.
8//!
9//! ## Identity
10//!
11//! A node's id is `BLAKE3-256("VOLE:PSEED:v1" || canonical_node_bytes)`. It is
12//! **domain-separated** from the object table's un-prefixed
13//! [`crate::store::Id`](crate::store::Id), so a seed node can never collide with,
14//! or be mistaken for, a raw object. A node id is a relational/advisory identity:
15//! it never appears in the whole-source `INTEGRITY` manifest and is never a
16//! substitute for the source SHA-256.
17//!
18//! ## Backends
19//!
20//! * [`FsSeedStore`] — the reference substrate: plain files under the store
21//!   root, written atomically (`tmp -> rename`), read with `pread`-style range
22//!   reads. Range reads carry no whole-node hash gate; only [`SeedStore::get`]
23//!   re-hashes.
24//! * An `EntropyFsStore` also implements [`SeedStore`], storing one node per
25//!   blob through the embeddable engine. Nodes are opaque bytes to EntropyFS; we
26//!   never claim EntropyFS natively stores VOLE procedural semantics (ADR-0025).
27
28use core::fmt;
29use std::collections::BTreeSet;
30use std::fs;
31use std::io::{Read, Seek, SeekFrom};
32use std::path::{Path, PathBuf};
33
34use crate::error::{Error, Result};
35
36use super::IoCounters;
37
38/// Domain-separation prefix for a procedural seed node's content id.
39pub const SEED_NODE_DOMAIN: &[u8] = b"VOLE:PSEED:v1";
40
41/// Canonical seed-node format version.
42pub const SEED_FORMAT_VERSION: u8 = 1;
43
44/// `NodeId` is a newtype over the 32 raw bytes of
45/// `BLAKE3-256("VOLE:PSEED:v1" || canonical_node_bytes)`. Hex is lower-case.
46#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
47pub struct NodeId([u8; 32]);
48
49impl NodeId {
50    /// Wrap 32 raw digest bytes.
51    pub const fn from_bytes(b: [u8; 32]) -> Self {
52        NodeId(b)
53    }
54
55    /// The raw digest bytes.
56    pub const fn as_bytes(&self) -> &[u8; 32] {
57        &self.0
58    }
59
60    /// Content id of canonical node bytes: `BLAKE3-256(domain || bytes)`.
61    pub fn of_node(canonical: &[u8]) -> Self {
62        let mut h = blake3::Hasher::new();
63        h.update(SEED_NODE_DOMAIN);
64        h.update(canonical);
65        NodeId(*h.finalize().as_bytes())
66    }
67
68    /// Lower-case hex rendering (64 characters).
69    pub fn to_hex(&self) -> String {
70        crate::integrity::to_hex(&self.0)
71    }
72
73    /// Parse exactly 64 lower- or upper-case hex characters.
74    pub fn from_hex(s: &str) -> Result<Self> {
75        crate::store::Id::from_hex(s).map(|id| NodeId(*id.as_bytes()))
76    }
77}
78
79impl fmt::Display for NodeId {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        f.write_str(&self.to_hex())
82    }
83}
84
85/// Physical accounting of a seed store.
86#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
87pub struct SeedStoreStats {
88    /// Number of stored nodes.
89    pub node_count: u64,
90    /// Sum of canonical node payload lengths.
91    pub total_bytes: u64,
92}
93
94/// A content-addressed store of canonical procedural seed nodes.
95///
96/// `put` takes `&mut self` (ids are content-derived, so retries are idempotent).
97pub trait SeedStore {
98    /// Store the canonical bytes of one node, returning its content id.
99    ///
100    /// Idempotent and at-least-once: identical bytes always return the same id
101    /// and are stored once. A returned id guarantees the bytes are durable under
102    /// [`SeedStore::get_node`].
103    fn put_node(&mut self, canonical: &[u8]) -> Result<NodeId>;
104
105    /// Fetch the exact canonical bytes for `id`.
106    ///
107    /// MUST verify `NodeId::of_node(bytes) == id` before returning.
108    fn get_node(&self, id: &NodeId) -> Result<Vec<u8>>;
109
110    /// Fetch `len` bytes of `id` starting at `offset` (strict; no EOF clip).
111    fn get_node_range(&self, id: &NodeId, offset: u64, len: u64) -> Result<Vec<u8>>;
112
113    /// Whether `id` is present.
114    fn contains_node(&self, id: &NodeId) -> Result<bool>;
115
116    /// Every stored `(id, canonical_len)`, for closure checking and GC.
117    fn list_nodes(&self) -> Result<Vec<(NodeId, u64)>>;
118}
119
120/// The reference seed substrate: one file per node under `root/seed`.
121///
122/// Layout: `root/seed/<aa>/<bb>/<64-hex>` where `aa`/`bb` are the first two
123/// bytes of the id in hex. Writes are atomic (`tmp -> rename`); reads are
124/// hash-verified by [`SeedStore::get_node`] and strict-range by
125/// [`SeedStore::get_node_range`].
126pub struct FsSeedStore {
127    root: PathBuf,
128    io: IoCounters,
129}
130
131impl std::fmt::Debug for FsSeedStore {
132    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133        f.debug_struct("FsSeedStore")
134            .field("root", &self.root)
135            .finish_non_exhaustive()
136    }
137}
138
139impl FsSeedStore {
140    /// Open (creating if needed) a seed store rooted at `root`, with a fresh,
141    /// private I/O counter set.
142    pub fn open(root: impl AsRef<Path>) -> Result<Self> {
143        Self::open_with_io(root, IoCounters::new())
144    }
145
146    /// Open a seed store that accounts every read against `io`. A caller that
147    /// also holds a [`crate::field::FieldStore`] shares its counter handle here,
148    /// so a seed read made through either handle is attributed to one universe.
149    pub fn open_with_io(root: impl AsRef<Path>, io: IoCounters) -> Result<Self> {
150        let root = root.as_ref().to_path_buf();
151        crate::store::durable::create_dir_all(&root.join("seed"))?;
152        Ok(FsSeedStore { root, io })
153    }
154
155    /// The seed-store root directory.
156    pub fn root(&self) -> &Path {
157        &self.root
158    }
159
160    fn node_path(&self, id: &NodeId) -> PathBuf {
161        let hex = id.to_hex();
162        self.root
163            .join("seed")
164            .join(&hex[0..2])
165            .join(&hex[2..4])
166            .join(&hex)
167    }
168}
169
170impl SeedStore for FsSeedStore {
171    fn put_node(&mut self, canonical: &[u8]) -> Result<NodeId> {
172        let id = NodeId::of_node(canonical);
173        let path = self.node_path(&id);
174        if path.exists() {
175            return Ok(id);
176        }
177        let dir = path
178            .parent()
179            .ok_or_else(|| Error::internal_invariant("seed node path has no parent"))?;
180        crate::store::durable::create_dir_all(dir)?;
181        // Atomic publish: write a sibling tmp file, fsync, rename over the target,
182        // then fsync the directory so the rename is durable across a power cut
183        // (Phase 23, GAP 1).
184        let tmp = dir.join(format!(".{}.tmp-{}", id.to_hex(), std::process::id()));
185        {
186            let mut f = crate::store::durable::create_file(&tmp)?;
187            crate::store::durable::write_all(&mut f, &tmp, canonical)?;
188            crate::store::durable::sync_all(&f, &tmp)?;
189        }
190        crate::store::durable::rename(&tmp, &path)?;
191        crate::store::durable::sync_dir(dir)?;
192        Ok(id)
193    }
194
195    fn get_node(&self, id: &NodeId) -> Result<Vec<u8>> {
196        let path = self.node_path(id);
197        let bytes = fs::read(&path).map_err(|e| {
198            if e.kind() == std::io::ErrorKind::NotFound {
199                Error::missing_external_object(format!("seed node {id} is not present"))
200            } else {
201                Error::io(format!("reading seed node {id}: {e}"))
202            }
203        })?;
204        let actual = NodeId::of_node(&bytes);
205        if actual != *id {
206            return Err(Error::integrity_mismatch(format!(
207                "seed node {id} content hashes to {actual}"
208            )));
209        }
210        self.io.add_seed(bytes.len() as u64);
211        Ok(bytes)
212    }
213
214    fn get_node_range(&self, id: &NodeId, offset: u64, len: u64) -> Result<Vec<u8>> {
215        let path = self.node_path(id);
216        let mut f = fs::File::open(&path).map_err(|e| {
217            if e.kind() == std::io::ErrorKind::NotFound {
218                Error::missing_external_object(format!("seed node {id} is not present"))
219            } else {
220                Error::io(format!("opening seed node {id}: {e}"))
221            }
222        })?;
223        let file_len = f.metadata()?.len();
224        if offset.checked_add(len).is_none_or(|end| end > file_len) {
225            return Err(Error::integrity_mismatch(format!(
226                "seed node {id} range [{offset}, {}) exceeds stored length {file_len}",
227                offset.saturating_add(len)
228            )));
229        }
230        f.seek(SeekFrom::Start(offset))?;
231        let mut out = vec![0u8; usize::try_from(len).unwrap_or(usize::MAX)];
232        f.read_exact(&mut out)?;
233        self.io.add_seed(out.len() as u64);
234        Ok(out)
235    }
236
237    fn contains_node(&self, id: &NodeId) -> Result<bool> {
238        Ok(self.node_path(id).exists())
239    }
240
241    fn list_nodes(&self) -> Result<Vec<(NodeId, u64)>> {
242        let seed = self.root.join("seed");
243        let mut out: Vec<(NodeId, u64)> = Vec::new();
244        let mut stack = vec![seed];
245        while let Some(dir) = stack.pop() {
246            let entries = match fs::read_dir(&dir) {
247                Ok(e) => e,
248                Err(_) => continue,
249            };
250            for entry in entries.flatten() {
251                let path = entry.path();
252                if path.is_dir() {
253                    stack.push(path);
254                    continue;
255                }
256                let Some(name) = path.file_name().and_then(|n| n.to_str()) else {
257                    continue;
258                };
259                if name.len() != 64 {
260                    continue;
261                }
262                let Ok(id) = NodeId::from_hex(name) else {
263                    continue;
264                };
265                let len = entry.metadata().map(|m| m.len()).unwrap_or(0);
266                out.push((id, len));
267            }
268        }
269        out.sort_unstable();
270        Ok(out)
271    }
272}
273
274/// Collect the transitive closure of `roots` in a seed store, verifying that no
275/// dependency is missing. `deps_of` maps a node's canonical bytes to its
276/// dependency ids; it must be deterministic.
277///
278/// Returns the reachable id set in ascending order. A missing dependency is a
279/// live `MissingExternalObject` (never a silent partial closure).
280pub fn closure(
281    store: &dyn SeedStore,
282    roots: &[NodeId],
283    deps_of: impl Fn(&[u8]) -> Result<Vec<NodeId>>,
284) -> Result<BTreeSet<NodeId>> {
285    let mut seen: BTreeSet<NodeId> = BTreeSet::new();
286    let mut stack: Vec<NodeId> = roots.to_vec();
287    while let Some(id) = stack.pop() {
288        if !seen.insert(id) {
289            continue;
290        }
291        let bytes = store.get_node(&id).map_err(|_| {
292            Error::missing_external_object(format!("seed closure missing node {id}"))
293        })?;
294        for dep in deps_of(&bytes)? {
295            if !seen.contains(&dep) {
296                stack.push(dep);
297            }
298        }
299    }
300    Ok(seen)
301}
302
303#[cfg(test)]
304mod tests {
305    use super::*;
306
307    fn temp_root(label: &str) -> PathBuf {
308        let mut p = std::env::temp_dir();
309        p.push(format!(
310            "vole-seed-{label}-{}-{}",
311            std::process::id(),
312            std::time::SystemTime::now()
313                .duration_since(std::time::UNIX_EPOCH)
314                .unwrap()
315                .as_nanos()
316        ));
317        fs::create_dir_all(&p).unwrap();
318        p
319    }
320
321    #[test]
322    fn put_get_roundtrip_and_idempotence() {
323        let root = temp_root("rt");
324        let mut store = FsSeedStore::open(&root).unwrap();
325        let bytes = b"canonical node bytes";
326        let id1 = store.put_node(bytes).unwrap();
327        let id2 = store.put_node(bytes).unwrap();
328        assert_eq!(id1, id2);
329        assert_eq!(store.get_node(&id1).unwrap(), bytes);
330        assert!(store.contains_node(&id1).unwrap());
331        assert_eq!(store.list_nodes().unwrap(), vec![(id1, bytes.len() as u64)]);
332        fs::remove_dir_all(&root).ok();
333    }
334
335    #[test]
336    fn range_reads_are_strict() {
337        let root = temp_root("range");
338        let mut store = FsSeedStore::open(&root).unwrap();
339        let bytes = b"0123456789";
340        let id = store.put_node(bytes).unwrap();
341        assert_eq!(store.get_node_range(&id, 2, 3).unwrap(), b"234");
342        let e = store.get_node_range(&id, 8, 5).unwrap_err();
343        assert_eq!(e.class(), crate::ErrorClass::IntegrityMismatch);
344        fs::remove_dir_all(&root).ok();
345    }
346
347    #[test]
348    fn node_ids_are_domain_separated_from_object_ids() {
349        let bytes = b"same bytes";
350        assert_ne!(
351            *NodeId::of_node(bytes).as_bytes(),
352            *crate::store::Id::of(bytes).as_bytes()
353        );
354    }
355}
vole_document/store/seed.rs

vole_document/store/
seed.rs
