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, Write};
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        fs::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        fs::create_dir_all(dir)?;
181        // Atomic publish: write a sibling tmp file, fsync, rename over the target.
182        let tmp = dir.join(format!(".{}.tmp-{}", id.to_hex(), std::process::id()));
183        {
184            let mut f = fs::File::create(&tmp)?;
185            f.write_all(canonical)?;
186            f.sync_all()?;
187        }
188        fs::rename(&tmp, &path)?;
189        Ok(id)
190    }
191
192    fn get_node(&self, id: &NodeId) -> Result<Vec<u8>> {
193        let path = self.node_path(id);
194        let bytes = fs::read(&path).map_err(|e| {
195            if e.kind() == std::io::ErrorKind::NotFound {
196                Error::missing_external_object(format!("seed node {id} is not present"))
197            } else {
198                Error::io(format!("reading seed node {id}: {e}"))
199            }
200        })?;
201        let actual = NodeId::of_node(&bytes);
202        if actual != *id {
203            return Err(Error::integrity_mismatch(format!(
204                "seed node {id} content hashes to {actual}"
205            )));
206        }
207        self.io.add_seed(bytes.len() as u64);
208        Ok(bytes)
209    }
210
211    fn get_node_range(&self, id: &NodeId, offset: u64, len: u64) -> Result<Vec<u8>> {
212        let path = self.node_path(id);
213        let mut f = fs::File::open(&path).map_err(|e| {
214            if e.kind() == std::io::ErrorKind::NotFound {
215                Error::missing_external_object(format!("seed node {id} is not present"))
216            } else {
217                Error::io(format!("opening seed node {id}: {e}"))
218            }
219        })?;
220        let file_len = f.metadata()?.len();
221        if offset.checked_add(len).is_none_or(|end| end > file_len) {
222            return Err(Error::integrity_mismatch(format!(
223                "seed node {id} range [{offset}, {}) exceeds stored length {file_len}",
224                offset.saturating_add(len)
225            )));
226        }
227        f.seek(SeekFrom::Start(offset))?;
228        let mut out = vec![0u8; usize::try_from(len).unwrap_or(usize::MAX)];
229        f.read_exact(&mut out)?;
230        self.io.add_seed(out.len() as u64);
231        Ok(out)
232    }
233
234    fn contains_node(&self, id: &NodeId) -> Result<bool> {
235        Ok(self.node_path(id).exists())
236    }
237
238    fn list_nodes(&self) -> Result<Vec<(NodeId, u64)>> {
239        let seed = self.root.join("seed");
240        let mut out: Vec<(NodeId, u64)> = Vec::new();
241        let mut stack = vec![seed];
242        while let Some(dir) = stack.pop() {
243            let entries = match fs::read_dir(&dir) {
244                Ok(e) => e,
245                Err(_) => continue,
246            };
247            for entry in entries.flatten() {
248                let path = entry.path();
249                if path.is_dir() {
250                    stack.push(path);
251                    continue;
252                }
253                let Some(name) = path.file_name().and_then(|n| n.to_str()) else {
254                    continue;
255                };
256                if name.len() != 64 {
257                    continue;
258                }
259                let Ok(id) = NodeId::from_hex(name) else {
260                    continue;
261                };
262                let len = entry.metadata().map(|m| m.len()).unwrap_or(0);
263                out.push((id, len));
264            }
265        }
266        out.sort_unstable();
267        Ok(out)
268    }
269}
270
271/// Collect the transitive closure of `roots` in a seed store, verifying that no
272/// dependency is missing. `deps_of` maps a node's canonical bytes to its
273/// dependency ids; it must be deterministic.
274///
275/// Returns the reachable id set in ascending order. A missing dependency is a
276/// live `MissingExternalObject` (never a silent partial closure).
277pub fn closure(
278    store: &dyn SeedStore,
279    roots: &[NodeId],
280    deps_of: impl Fn(&[u8]) -> Result<Vec<NodeId>>,
281) -> Result<BTreeSet<NodeId>> {
282    let mut seen: BTreeSet<NodeId> = BTreeSet::new();
283    let mut stack: Vec<NodeId> = roots.to_vec();
284    while let Some(id) = stack.pop() {
285        if !seen.insert(id) {
286            continue;
287        }
288        let bytes = store.get_node(&id).map_err(|_| {
289            Error::missing_external_object(format!("seed closure missing node {id}"))
290        })?;
291        for dep in deps_of(&bytes)? {
292            if !seen.contains(&dep) {
293                stack.push(dep);
294            }
295        }
296    }
297    Ok(seen)
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    fn temp_root(label: &str) -> PathBuf {
305        let mut p = std::env::temp_dir();
306        p.push(format!(
307            "vole-seed-{label}-{}-{}",
308            std::process::id(),
309            std::time::SystemTime::now()
310                .duration_since(std::time::UNIX_EPOCH)
311                .unwrap()
312                .as_nanos()
313        ));
314        fs::create_dir_all(&p).unwrap();
315        p
316    }
317
318    #[test]
319    fn put_get_roundtrip_and_idempotence() {
320        let root = temp_root("rt");
321        let mut store = FsSeedStore::open(&root).unwrap();
322        let bytes = b"canonical node bytes";
323        let id1 = store.put_node(bytes).unwrap();
324        let id2 = store.put_node(bytes).unwrap();
325        assert_eq!(id1, id2);
326        assert_eq!(store.get_node(&id1).unwrap(), bytes);
327        assert!(store.contains_node(&id1).unwrap());
328        assert_eq!(store.list_nodes().unwrap(), vec![(id1, bytes.len() as u64)]);
329        fs::remove_dir_all(&root).ok();
330    }
331
332    #[test]
333    fn range_reads_are_strict() {
334        let root = temp_root("range");
335        let mut store = FsSeedStore::open(&root).unwrap();
336        let bytes = b"0123456789";
337        let id = store.put_node(bytes).unwrap();
338        assert_eq!(store.get_node_range(&id, 2, 3).unwrap(), b"234");
339        let e = store.get_node_range(&id, 8, 5).unwrap_err();
340        assert_eq!(e.class(), crate::ErrorClass::IntegrityMismatch);
341        fs::remove_dir_all(&root).ok();
342    }
343
344    #[test]
345    fn node_ids_are_domain_separated_from_object_ids() {
346        let bytes = b"same bytes";
347        assert_ne!(
348            *NodeId::of_node(bytes).as_bytes(),
349            *crate::store::Id::of(bytes).as_bytes()
350        );
351    }
352}
vole_document/store/seed.rs

vole_document/store/
seed.rs
