Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/cas.rs

29.6 KiB, 162 runs

created by r1870400018:16775, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Content-addressed storage (CAS): fixed-size and content-defined chunking,
2//! with SHA-256 content addressing, for opaque byte payloads.
3//!
4//! This module underpins large, syncable payloads that must not be shipped
5//! whole. A payload is split into chunks; each chunk is addressed by
6//! the SHA-256 of its bytes, and an ordered [`Manifest`] of those addresses
7//! reconstructs it. A store keyed by content address then holds a chunk once
8//! however many manifests reference it, and a consumer fetches only the chunks
9//! it lacks. That is what lets a large corpus be used from a device too small
10//! to hold it whole: the device keeps a working-set cache and pulls the rest on
11//! demand.
12//!
13//! # Why SHA-256, not SHA-3
14//!
15//! The canonical caller is a browser client that computes chunk addresses with
16//! the Web Crypto API and a gateway that re-verifies them before it accepts a
17//! chunk. Web Crypto offers SHA-256 but not SHA-3, so SHA-256 is the one
18//! function both sides compute identically. See
19//! [`oxedyne_fe2o3_hash::sha256`], which exists for exactly this reason. The
20//! distributed-Ozone digest hash (`dist::storage`) has a different job -- peer
21//! divergence detection among Rust nodes -- and is chosen there separately.
22//!
23//! # What this module does not do
24//!
25//! Encryption is the caller's concern. For a *content-blind* store the caller
26//! encrypts each chunk before handing it here, so the address is over
27//! ciphertext and the store never sees plaintext; deduplication is therefore
28//! within one caller's keyspace, never across callers.
29//!
30//! # Two chunkers
31//!
32//! [`Chunker`] cuts at fixed offsets: simple, and enough to break the
33//! whole-payload ceiling, but every boundary is an offset rather than a place in
34//! the content, so inserting one byte near the front shifts every boundary after
35//! it and the whole payload re-uploads.
36//!
37//! [`CdcChunker`] cuts where the content says to. A FastCDC-style gear rolling
38//! hash reads the payload and declares a boundary wherever the hash of the
39//! preceding bytes hits a mask, so an insertion moves only the boundaries around
40//! it: the chunks either side keep their addresses and are never re-sent. That
41//! is the refinement the fixed chunker was a first cut for, and it arrived
42//! without changing [`Manifest`] or [`Cas`] -- both chunkers return the same
43//! manifest shape, and a store cannot tell which produced what it holds.
44//!
45//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
46//! Anthropic Claude
47
48use oxedyne_fe2o3_core::prelude::*;
49use oxedyne_fe2o3_hash::sha256;
50use oxedyne_fe2o3_jdat::prelude::*;
51
52use std::collections::{
53 HashMap,
54 HashSet,
55};
56use std::sync::Mutex;
57
58
59pub const ADDR_LEN: usize = 32; // SHA-256 digest
60
61// Large enough that the per-chunk manifest overhead stays a small fraction of a
62// multi-megabyte payload, small enough that an edit confined to one region
63// re-uploads little.
64pub const DEFAULT_CHUNK_SIZE: usize = 256 * 1024;
65
66// A floor stops a run of unlucky hash hits producing a swarm of tiny chunks,
67// each of which costs an address in every manifest that names it.
68pub const DEFAULT_MIN_CHUNK_SIZE: usize = 64 * 1024;
69
70// A ceiling bounds the damage when the hash finds no boundary at all, which is
71// what happens across a long run of identical bytes.
72pub const DEFAULT_MAX_CHUNK_SIZE: usize = 1024 * 1024;
73
74/// Seed for the gear table's generator.
75///
76/// The table must be identical on every machine and in every release, because a
77/// changed table changes every boundary and so every address, which would make
78/// a store's existing chunks unreachable. Fixing the seed here, and deriving the
79/// table from it rather than shipping a literal, is what pins it. The value is
80/// the golden-ratio constant splitmix64 conventionally uses.
81const GEAR_SEED: u64 = 0x9e37_79b9_7f4a_7c15;
82
83// How many bits the mask tightens below the average chunk size and loosens
84// above it. Plain gear chunking gives an exponential spread of chunk sizes, so
85// short chunks dominate and the tail is long. Cutting less readily before the
86// average and more readily after it pulls the spread in towards the average
87// without forcing boundaries at fixed offsets. Two is the level the FastCDC
88// paper settles on.
89const NORM_LEVEL: u32 = 2;
90
91// One random u64 per byte value, generated at compile time from GEAR_SEED by
92// splitmix64, so there is no dependency to pull in and no table in the source.
93static GEAR: [u64; 256] = gear_table();
94
95
96/// A content address: the SHA-256 digest of a chunk's bytes.
97///
98/// Two byte-identical chunks share one address, which is what makes the store
99/// deduplicating. The address is verifiable: a store re-hashes a submitted
100/// chunk and rejects it unless the bytes produce the claimed address, so a
101/// client cannot mislabel a chunk.
102#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
103pub struct ContentId([u8; ADDR_LEN]);
104
105impl ContentId {
106 pub fn of(bytes: &[u8]) -> Self {
107 Self(sha256::digest(bytes))
108 }
109
110 pub const fn from_bytes(bytes: [u8; ADDR_LEN]) -> Self {
111 Self(bytes)
112 }
113
114 /// The slice must be exactly [`ADDR_LEN`] bytes.
115 pub fn from_slice(bytes: &[u8]) -> Outcome<Self> {
116 if bytes.len() != ADDR_LEN {
117 return Err(err!(
118 "A ContentId requires exactly {} bytes, got {}.",
119 ADDR_LEN, bytes.len();
120 Invalid, Input, Size));
121 }
122 let mut arr = [0u8; ADDR_LEN];
123 arr.copy_from_slice(bytes);
124 Ok(Self(arr))
125 }
126
127 pub fn as_bytes(&self) -> &[u8; ADDR_LEN] {
128 &self.0
129 }
130
131 /// Do these bytes hash to this address? A store uses this to reject a chunk
132 /// whose claimed address does not match its content.
133 pub fn verifies(&self, bytes: &[u8]) -> bool {
134 self.0 == sha256::digest(bytes)
135 }
136
137 /// Lowercase hex, for logs and keys.
138 pub fn to_hex(&self) -> String {
139 let mut s = String::with_capacity(ADDR_LEN * 2);
140 for b in &self.0 {
141 s.push(hex_char(b >> 4));
142 s.push(hex_char(b & 0x0f));
143 }
144 s
145 }
146
147 /// Accepts either case, and exactly `2 * ADDR_LEN` characters.
148 pub fn from_hex(s: &str) -> Outcome<Self> {
149 let bytes = s.as_bytes();
150 if bytes.len() != ADDR_LEN * 2 {
151 return Err(err!(
152 "A hex ContentId requires {} characters, got {}.",
153 ADDR_LEN * 2, bytes.len();
154 Invalid, Input, Size));
155 }
156 let mut arr = [0u8; ADDR_LEN];
157 for i in 0..ADDR_LEN {
158 let hi = res!(nibble(bytes[i * 2]));
159 let lo = res!(nibble(bytes[i * 2 + 1]));
160 arr[i] = (hi << 4) | lo;
161 }
162 Ok(Self(arr))
163 }
164}
165
166impl std::fmt::Display for ContentId {
167 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
168 write!(f, "{}", self.to_hex())
169 }
170}
171
172
173#[derive(Clone, Debug, Eq, PartialEq)]
174pub struct Chunk {
175 pub id: ContentId,
176 pub bytes: Vec<u8>,
177}
178
179impl Chunk {
180 pub fn new(bytes: Vec<u8>) -> Self {
181 let id = ContentId::of(&bytes);
182 Self { id, bytes }
183 }
184}
185
186
187/// A reference to one chunk within a [`Manifest`]: its address and byte length.
188///
189/// The length lets a reader validate a fetched chunk and lets a planner size a
190/// download without fetching, so it costs one small integer per chunk to make
191/// the manifest self-checking.
192#[derive(Clone, Copy, Debug, Eq, PartialEq)]
193pub struct ChunkRef {
194 pub id: ContentId,
195 pub len: usize,
196}
197
198
199/// The ordered list of chunk addresses that reconstruct a payload, with the
200/// payload's total length for validation.
201///
202/// A manifest is small -- one address plus a length per chunk -- and is itself
203/// an opaque value the caller may store or encrypt. It is the only thing a
204/// caller must keep to recover a payload from a content-addressed store.
205#[derive(Clone, Debug, Default, Eq, PartialEq)]
206pub struct Manifest {
207 pub total_len: usize, // sum of the chunk lengths
208 pub chunks: Vec<ChunkRef>, // in payload order
209}
210
211impl Manifest {
212 pub fn is_empty(&self) -> bool {
213 self.chunks.is_empty()
214 }
215
216 pub fn len(&self) -> usize {
217 self.chunks.len()
218 }
219
220 /// Chunk addresses in payload order.
221 pub fn addrs(&self) -> impl Iterator<Item = &ContentId> {
222 self.chunks.iter().map(|c| &c.id)
223 }
224
225 /// Each fetched chunk is checked for the expected length and re-hashed to
226 /// confirm it matches the address the manifest names, so a corrupted or
227 /// substituted chunk is rejected rather than returned. The final length is
228 /// checked against `total_len`.
229 pub fn reassemble<F>(&self, mut fetch: F)
230 -> Outcome<Vec<u8>>
231 where
232 F: FnMut(&ContentId) -> Outcome<Vec<u8>>,
233 {
234 let mut out = Vec::with_capacity(self.total_len);
235 for (i, cref) in self.chunks.iter().enumerate() {
236 let bytes = res!(fetch(&cref.id));
237 if bytes.len() != cref.len {
238 return Err(err!(
239 "Chunk {} ({}) has length {}, manifest expects {}.",
240 i, cref.id, bytes.len(), cref.len;
241 Invalid, Input, Size, Mismatch));
242 }
243 if !cref.id.verifies(&bytes) {
244 return Err(err!(
245 "Chunk {} does not hash to its manifest address {}.",
246 i, cref.id;
247 Invalid, Input, Mismatch));
248 }
249 out.extend_from_slice(&bytes);
250 }
251 if out.len() != self.total_len {
252 return Err(err!(
253 "Reassembled {} bytes, manifest declares {}.",
254 out.len(), self.total_len;
255 Invalid, Input, Size, Mismatch));
256 }
257 Ok(out)
258 }
259
260 /// The serialised shape is `[total_len, [[addr, len], ...]]`.
261 pub fn to_dat(&self) -> Dat {
262 let mut list = Vec::with_capacity(self.chunks.len());
263 for cref in &self.chunks {
264 list.push(Dat::List(vec![
265 Dat::BU8(cref.id.as_bytes().to_vec()),
266 Dat::U64(cref.len as u64),
267 ]));
268 }
269 Dat::List(vec![
270 Dat::U64(self.total_len as u64),
271 Dat::List(list),
272 ])
273 }
274
275 pub fn from_dat(dat: &Dat) -> Outcome<Self> {
276 let top = match dat {
277 Dat::List(v) if v.len() == 2 => v,
278 _ => return Err(err!(
279 "Manifest expects a 2-element Dat::List, got {:?}.", dat;
280 Decode, Input, Mismatch)),
281 };
282 let total_len = match &top[0] {
283 Dat::U64(n) => *n as usize,
284 other => return Err(err!(
285 "Manifest total_len expects Dat::U64, got {:?}.", other;
286 Decode, Input, Mismatch)),
287 };
288 let entries = match &top[1] {
289 Dat::List(v) => v,
290 other => return Err(err!(
291 "Manifest chunks expect Dat::List, got {:?}.", other;
292 Decode, Input, Mismatch)),
293 };
294 let mut chunks = Vec::with_capacity(entries.len());
295 for entry in entries {
296 let pair = match entry {
297 Dat::List(v) if v.len() == 2 => v,
298 _ => return Err(err!(
299 "Manifest chunk entry expects a 2-element list, got {:?}.",
300 entry;
301 Decode, Input, Mismatch)),
302 };
303 let id = match &pair[0] {
304 Dat::BU8(b) => res!(ContentId::from_slice(b)),
305 other => return Err(err!(
306 "Manifest chunk address expects Dat::BU8, got {:?}.", other;
307 Decode, Input, Mismatch)),
308 };
309 let len = match &pair[1] {
310 Dat::U64(n) => *n as usize,
311 other => return Err(err!(
312 "Manifest chunk length expects Dat::U64, got {:?}.", other;
313 Decode, Input, Mismatch)),
314 };
315 chunks.push(ChunkRef { id, len });
316 }
317 Ok(Self { total_len, chunks })
318 }
319}
320
321
322/// Splits a payload into fixed-size, content-addressed chunks.
323#[derive(Clone, Copy, Debug)]
324pub struct Chunker {
325 chunk_size: usize, // the final chunk may be shorter
326}
327
328impl Default for Chunker {
329 fn default() -> Self {
330 Self { chunk_size: DEFAULT_CHUNK_SIZE }
331 }
332}
333
334impl Chunker {
335 /// The chunk size must be non-zero.
336 pub fn new(chunk_size: usize) -> Outcome<Self> {
337 if chunk_size == 0 {
338 return Err(err!(
339 "Chunk size must be non-zero.";
340 Invalid, Input, Range));
341 }
342 Ok(Self { chunk_size })
343 }
344
345 pub fn chunk_size(&self) -> usize {
346 self.chunk_size
347 }
348
349 /// A payload shorter than one chunk yields a single chunk; an empty payload
350 /// yields an empty manifest and no chunks. Byte-identical chunks share an
351 /// address, so the returned `Vec<Chunk>` may contain duplicates that a
352 /// deduplicating store collapses on write.
353 pub fn split(&self, payload: &[u8])
354 -> (Manifest, Vec<Chunk>)
355 {
356 let mut refs = Vec::new();
357 let mut chunks = Vec::new();
358 for part in payload.chunks(self.chunk_size) {
359 let chunk = Chunk::new(part.to_vec());
360 refs.push(ChunkRef { id: chunk.id, len: chunk.bytes.len() });
361 chunks.push(chunk);
362 }
363 (Manifest { total_len: payload.len(), chunks: refs }, chunks)
364 }
365}
366
367
368/// Splits a payload into content-defined, content-addressed chunks, cutting
369/// where a FastCDC-style gear rolling hash says the content changes.
370///
371/// The hash reads the payload one byte at a time, keeping a value that depends
372/// only on the last few dozen bytes. Where that value hits a mask, a boundary is
373/// declared. Because the boundary follows the bytes and not the offset, an
374/// insertion or deletion perturbs only the chunks around it: every chunk beyond
375/// the disturbance re-synchronises on the same content and keeps the address it
376/// had, so a store already holding it needs nothing sent.
377///
378/// Boundaries are constrained to `[min, max]` and steered towards `avg` by
379/// normalised chunking: below the average the mask is a couple of bits
380/// stricter, above it a couple of bits looser. The bytes before `min` are not
381/// hashed at all -- no boundary could be accepted there -- which is the
382/// cut-point skipping that makes the scan cheap.
383#[derive(Clone, Copy, Debug)]
384pub struct CdcChunker {
385 min: usize, // except for a payload shorter than this
386 avg: usize, // where the mask loosens
387 max: usize, // a boundary is forced here
388 mask_s: u64, // applied below avg
389 mask_l: u64, // applied at and above avg
390}
391
392impl Default for CdcChunker {
393 fn default() -> Self {
394 Self::sizes(
395 DEFAULT_MIN_CHUNK_SIZE,
396 DEFAULT_CHUNK_SIZE,
397 DEFAULT_MAX_CHUNK_SIZE,
398 )
399 }
400}
401
402impl CdcChunker {
403 /// The sizes must satisfy `0 < min <= avg <= max`.
404 pub fn new(min: usize, avg: usize, max: usize)
405 -> Outcome<Self>
406 {
407 if min == 0 {
408 return Err(err!(
409 "Minimum chunk size must be non-zero.";
410 Invalid, Input, Range));
411 }
412 if min > avg || avg > max {
413 return Err(err!(
414 "Chunk sizes must satisfy min <= avg <= max, got {}, {}, {}.",
415 min, avg, max;
416 Invalid, Input, Range));
417 }
418 Ok(Self::sizes(min, avg, max))
419 }
420
421 /// The sizes are assumed already valid; derives the two masks.
422 fn sizes(min: usize, avg: usize, max: usize) -> Self {
423 let bits = log2_floor(avg); // Mask width for the average.
424 let strict = (bits + NORM_LEVEL).min(63);
425 let loose = bits.saturating_sub(NORM_LEVEL).max(1);
426 Self {
427 min,
428 avg,
429 max,
430 mask_s: high_mask(strict),
431 mask_l: high_mask(loose),
432 }
433 }
434
435 pub fn min_size(&self) -> usize {
436 self.min
437 }
438
439 pub fn avg_size(&self) -> usize {
440 self.avg
441 }
442
443 pub fn max_size(&self) -> usize {
444 self.max
445 }
446
447 /// The contract matches [`Chunker::split`]: an empty payload yields an empty
448 /// manifest and no chunks, a payload shorter than the minimum chunk size
449 /// yields a single chunk, and byte-identical chunks share an address, so the
450 /// returned `Vec<Chunk>` may contain duplicates that a deduplicating store
451 /// collapses on write.
452 pub fn split(&self, payload: &[u8])
453 -> (Manifest, Vec<Chunk>)
454 {
455 let mut refs = Vec::new();
456 let mut chunks = Vec::new();
457 let mut pos = 0;
458 while pos < payload.len() {
459 let len = self.cut(&payload[pos..]);
460 let chunk = Chunk::new(payload[pos..pos + len].to_vec());
461 refs.push(ChunkRef { id: chunk.id, len: chunk.bytes.len() });
462 chunks.push(chunk);
463 pos += len;
464 }
465 (Manifest { total_len: payload.len(), chunks: refs }, chunks)
466 }
467
468 /// The length of the first chunk of `data`, always at least one byte so that
469 /// [`CdcChunker::split`] terminates.
470 fn cut(&self, data: &[u8]) -> usize {
471 let n = data.len();
472 if n <= self.min {
473 return n; // Too short to cut: the whole remainder is one chunk.
474 }
475 let end = self.max.min(n); // Forced boundary.
476 let mid = self.avg.min(end); // Where the mask loosens.
477 let mut fp = 0u64; // The rolling gear hash.
478 let mut i = self.min; // Skip: no boundary may land below.
479 while i < mid {
480 fp = (fp << 1).wrapping_add(GEAR[data[i] as usize]);
481 if fp & self.mask_s == 0 {
482 return i + 1;
483 }
484 i += 1;
485 }
486 while i < end {
487 fp = (fp << 1).wrapping_add(GEAR[data[i] as usize]);
488 if fp & self.mask_l == 0 {
489 return i + 1;
490 }
491 i += 1;
492 }
493 end
494 }
495}
496
497
498/// A store of chunks keyed by content address.
499///
500/// Implementations must be internally thread-safe. The store is deliberately
501/// dumb: it holds opaque bytes addressed by their hash and enforces only that a
502/// chunk's bytes match its address. Which chunks are live -- reachable from a
503/// current manifest -- is the caller's knowledge, supplied to [`Cas::sweep`]
504/// for garbage collection.
505pub trait Cas {
506 /// Stores a chunk, rejecting it if its bytes do not hash to its address.
507 /// Storing an address already present is a no-op (the bytes are identical
508 /// by definition), so writes are idempotent.
509 fn put(&self, chunk: &Chunk) -> Outcome<()>;
510
511 fn get(&self, id: &ContentId) -> Outcome<Option<Vec<u8>>>;
512
513 fn has(&self, id: &ContentId) -> Outcome<bool>;
514
515 /// The bool reports whether a chunk was present to remove.
516 fn delete(&self, id: &ContentId) -> Outcome<bool>;
517
518 fn ids(&self) -> Outcome<Vec<ContentId>>;
519
520 /// Stores `bytes` whole, as a single chunk.
521 fn put_bytes(&self, bytes: Vec<u8>)
522 -> Outcome<ContentId>
523 {
524 let chunk = Chunk::new(bytes);
525 let id = chunk.id;
526 res!(self.put(&chunk));
527 Ok(id)
528 }
529
530 /// Mark-and-sweep garbage collection: the caller assembles the set
531 /// of addresses reachable from every manifest it still holds and hands it
532 /// in; everything else is unreferenced and freed. Deleting only the
533 /// unreferenced set is what lets a lapse evict overflow without disturbing
534 /// chunks a live manifest still needs.
535 fn sweep(&self, live: &HashSet<ContentId>)
536 -> Outcome<usize>
537 {
538 let mut removed = 0;
539 for id in res!(self.ids()) {
540 if !live.contains(&id) {
541 if res!(self.delete(&id)) {
542 removed += 1;
543 }
544 }
545 }
546 Ok(removed)
547 }
548}
549
550
551/// An in-memory [`Cas`] backed by a `HashMap`, for tests and loopback demos.
552pub struct MemoryCas {
553 inner: Mutex<HashMap<ContentId, Vec<u8>>>,
554}
555
556impl MemoryCas {
557 pub fn new() -> Self {
558 Self { inner: Mutex::new(HashMap::new()) }
559 }
560
561 /// Distinct chunks held, so duplicates count once.
562 pub fn len(&self) -> Outcome<usize> {
563 let guard = lock_mutex!(self.inner);
564 Ok(guard.len())
565 }
566
567 pub fn is_empty(&self) -> Outcome<bool> {
568 Ok(res!(self.len()) == 0)
569 }
570}
571
572impl Default for MemoryCas {
573 fn default() -> Self {
574 Self::new()
575 }
576}
577
578impl Cas for MemoryCas {
579 fn put(&self, chunk: &Chunk) -> Outcome<()> {
580 if !chunk.id.verifies(&chunk.bytes) {
581 return Err(err!(
582 "Refusing chunk whose bytes do not hash to its address {}.",
583 chunk.id;
584 Invalid, Input, Mismatch));
585 }
586 let mut guard = lock_mutex!(self.inner);
587 guard.entry(chunk.id).or_insert_with(|| chunk.bytes.clone());
588 Ok(())
589 }
590
591 fn get(&self, id: &ContentId) -> Outcome<Option<Vec<u8>>> {
592 let guard = lock_mutex!(self.inner);
593 Ok(guard.get(id).cloned())
594 }
595
596 fn has(&self, id: &ContentId) -> Outcome<bool> {
597 let guard = lock_mutex!(self.inner);
598 Ok(guard.contains_key(id))
599 }
600
601 fn delete(&self, id: &ContentId) -> Outcome<bool> {
602 let mut guard = lock_mutex!(self.inner);
603 Ok(guard.remove(id).is_some())
604 }
605
606 fn ids(&self) -> Outcome<Vec<ContentId>> {
607 let guard = lock_mutex!(self.inner);
608 Ok(guard.keys().copied().collect())
609 }
610}
611
612
613/// Splitmix64 is a handful of multiplies and shifts, which is why it can run in
614/// a `const` context and save the crate a dependency and a 2 KiB literal.
615const fn gear_table() -> [u64; 256] {
616 let mut table = [0u64; 256];
617 let mut state = GEAR_SEED;
618 let mut i = 0;
619 while i < 256 {
620 state = state.wrapping_add(GEAR_SEED);
621 let mut z = state;
622 z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
623 z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
624 table[i] = z ^ (z >> 31);
625 i += 1;
626 }
627 table
628}
629
630/// A mask over the top `bits` bits of a `u64`, for `1 <= bits <= 63`.
631///
632/// The top bits are the ones to test. A gear hash shifts left by one per byte,
633/// so bit `k` of the hash depends on the last `k + 1` bytes; testing the high
634/// bits therefore tests a window dozens of bytes wide, while testing the low
635/// bits would decide a boundary on almost nothing.
636const fn high_mask(bits: u32) -> u64 {
637 ((1u64 << bits) - 1) << (64 - bits)
638}
639
640/// The value must be non-zero.
641fn log2_floor(n: usize) -> u32 {
642 (usize::BITS - 1) - n.leading_zeros()
643}
644
645fn hex_char(nib: u8) -> char {
646 match nib {
647 0..=9 => (b'0' + nib) as char,
648 10..=15 => (b'a' + nib - 10) as char,
649 _ => '?', // Unreachable: callers mask to 0..=15.
650 }
651}
652
653fn nibble(b: u8)
654 -> Outcome<u8>
655{
656 match b {
657 b'0'..=b'9' => Ok(b - b'0'),
658 b'a'..=b'f' => Ok(b - b'a' + 10),
659 b'A'..=b'F' => Ok(b - b'A' + 10),
660 _ => Err(err!(
661 "Invalid hex character: 0x{:02x}.", b;
662 Invalid, Input)),
663 }
664}
665
666
667#[cfg(test)]
668mod tests {
669 use super::*;
670
671 #[test]
672 fn content_id_deterministic_and_verifies() -> Outcome<()> {
673 let a = ContentId::of(b"hello");
674 let b = ContentId::of(b"hello");
675 let c = ContentId::of(b"world");
676 assert_eq!(a, b);
677 assert_ne!(a, c);
678 assert!(a.verifies(b"hello"));
679 assert!(!a.verifies(b"world"));
680 Ok(())
681 }
682
683 #[test]
684 fn content_id_hex_round_trip() -> Outcome<()> {
685 let id = ContentId::of(b"some bytes");
686 let hex = id.to_hex();
687 assert_eq!(hex.len(), ADDR_LEN * 2);
688 let back = res!(ContentId::from_hex(&hex));
689 assert_eq!(id, back);
690 Ok(())
691 }
692
693 /// An empty payload, one shorter than a chunk, an exact multiple, and one
694 /// with a remainder.
695 #[test]
696 fn chunk_reassemble_round_trip() -> Outcome<()> {
697 let chunker = res!(Chunker::new(4));
698 let store = MemoryCas::new();
699 for payload in [
700 Vec::new(),
701 b"ab".to_vec(),
702 b"abcdefgh".to_vec(), // Exact multiple of 4.
703 b"abcdefghij".to_vec(), // Remainder of 2.
704 ] {
705 let (manifest, chunks) = chunker.split(&payload);
706 for chunk in &chunks {
707 res!(store.put(chunk));
708 }
709 assert_eq!(manifest.total_len, payload.len());
710 let got = res!(manifest.reassemble(|id| {
711 match res!(store.get(id)) {
712 Some(b) => Ok(b),
713 None => Err(err!("missing chunk {}", id; Test, Missing)),
714 }
715 }));
716 assert_eq!(got, payload);
717 }
718 Ok(())
719 }
720
721 #[test]
722 fn identical_chunks_deduplicate() -> Outcome<()> {
723 let chunker = res!(Chunker::new(4));
724 let store = MemoryCas::new();
725 let payload = b"aaaaaaaa".to_vec(); // Two identical "aaaa" chunks.
726 let (manifest, chunks) = chunker.split(&payload);
727 assert_eq!(manifest.len(), 2);
728 for chunk in &chunks {
729 res!(store.put(chunk));
730 }
731 assert_eq!(res!(store.len()), 1); // Deduplicated.
732 Ok(())
733 }
734
735 #[test]
736 fn manifest_dat_round_trip() -> Outcome<()> {
737 let chunker = res!(Chunker::new(3));
738 let (manifest, _) = chunker.split(b"the quick brown fox");
739 let dat = manifest.to_dat();
740 let back = res!(Manifest::from_dat(&dat));
741 assert_eq!(manifest, back);
742 Ok(())
743 }
744
745 #[test]
746 fn reassemble_rejects_tampered_chunk() -> Outcome<()> {
747 let chunker = res!(Chunker::new(4));
748 let (manifest, _) = chunker.split(b"abcdefgh");
749 // Fetch returns the wrong bytes for whatever is asked.
750 let outcome = manifest.reassemble(|_id| Ok(b"XXXX".to_vec()));
751 assert!(outcome.is_err());
752 Ok(())
753 }
754
755 #[test]
756 fn put_rejects_mislabelled_chunk() -> Outcome<()> {
757 let store = MemoryCas::new();
758 let bad = Chunk {
759 id: ContentId::of(b"claimed"),
760 bytes: b"actual".to_vec(),
761 };
762 assert!(store.put(&bad).is_err());
763 Ok(())
764 }
765
766 #[test]
767 fn memory_cas_put_get_has_delete() -> Outcome<()> {
768 let store = MemoryCas::new();
769 let id = res!(store.put_bytes(b"payload".to_vec()));
770 assert!(res!(store.has(&id)));
771 assert_eq!(res!(store.get(&id)), Some(b"payload".to_vec()));
772 assert!(res!(store.delete(&id)));
773 assert!(!res!(store.has(&id)));
774 assert!(!res!(store.delete(&id))); // Second delete is false.
775 Ok(())
776 }
777
778 #[test]
779 fn sweep_frees_unreferenced_chunks() -> Outcome<()> {
780 let store = MemoryCas::new();
781 let keep = res!(store.put_bytes(b"keep me".to_vec()));
782 let _drop = res!(store.put_bytes(b"drop me".to_vec()));
783 assert_eq!(res!(store.len()), 2);
784 let mut live = HashSet::new();
785 live.insert(keep);
786 let removed = res!(store.sweep(&live));
787 assert_eq!(removed, 1);
788 assert_eq!(res!(store.len()), 1);
789 assert!(res!(store.has(&keep)));
790 Ok(())
791 }
792
793 /// Splitmix64 again, seeded separately from the gear table, so a test needs
794 /// no `rand` crate and produces the same payload on every machine and every
795 /// run -- a shift-resistance figure is only worth quoting if it is stable.
796 fn pseudorandom(len: usize, seed: u64) -> Vec<u8> {
797 let mut out = Vec::with_capacity(len);
798 let mut state = seed;
799 while out.len() < len {
800 state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
801 let mut z = state;
802 z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
803 z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
804 z ^= z >> 31;
805 for b in z.to_le_bytes() {
806 if out.len() == len {
807 break;
808 }
809 out.push(b);
810 }
811 }
812 out
813 }
814
815 /// The fraction of `edited`'s chunks whose addresses also occur in `orig`,
816 /// counting multiplicity: the share of the edited payload a store already
817 /// holds, and so need not be sent.
818 fn shared_fraction(orig: &Manifest, edited: &Manifest) -> f64 {
819 let mut have: HashMap<ContentId, usize> = HashMap::new();
820 for cref in &orig.chunks {
821 *have.entry(cref.id).or_insert(0) += 1;
822 }
823 let mut shared = 0usize;
824 for cref in &edited.chunks {
825 if let Some(n) = have.get_mut(&cref.id) {
826 if *n > 0 {
827 *n -= 1;
828 shared += 1;
829 }
830 }
831 }
832 shared as f64 / edited.chunks.len() as f64
833 }
834
835 /// One inserted byte is the smallest edit that shifts everything after it.
836 fn insert_byte(payload: &[u8], at: usize) -> Vec<u8> {
837 let mut out = payload.to_vec();
838 out.insert(at, 0x5a);
839 out
840 }
841
842 #[test]
843 fn cdc_validates_its_sizes() -> Outcome<()> {
844 assert!(CdcChunker::new(0, 16, 64).is_err()); // Zero minimum.
845 assert!(CdcChunker::new(32, 16, 64).is_err()); // min > avg.
846 assert!(CdcChunker::new(16, 128, 64).is_err()); // avg > max.
847 let cdc = res!(CdcChunker::new(16, 64, 256));
848 assert_eq!(cdc.min_size(), 16);
849 assert_eq!(cdc.avg_size(), 64);
850 assert_eq!(cdc.max_size(), 256);
851 let def = CdcChunker::default();
852 assert_eq!(def.min_size(), DEFAULT_MIN_CHUNK_SIZE);
853 assert_eq!(def.avg_size(), DEFAULT_CHUNK_SIZE);
854 assert_eq!(def.max_size(), DEFAULT_MAX_CHUNK_SIZE);
855 Ok(())
856 }
857
858 /// The degenerate payloads behave as the fixed chunker's do.
859 #[test]
860 fn cdc_split_is_deterministic() -> Outcome<()> {
861 let cdc = res!(CdcChunker::new(64, 256, 1024));
862 let payload = pseudorandom(300_000, 7);
863 let (m1, c1) = cdc.split(&payload);
864 let (m2, c2) = cdc.split(&payload);
865 assert_eq!(m1, m2);
866 assert_eq!(c1, c2);
867 assert!(m1.len() > 1); // It really did cut.
868
869 let (empty, chunks) = cdc.split(&[]); // Empty payload, empty manifest.
870 assert!(empty.is_empty());
871 assert_eq!(empty.total_len, 0);
872 assert!(chunks.is_empty());
873
874 let short = pseudorandom(30, 9); // Below the minimum: one chunk.
875 let (m, chunks) = cdc.split(&short);
876 assert_eq!(m.len(), 1);
877 assert_eq!(m.total_len, 30);
878 assert_eq!(chunks[0].bytes, short);
879 Ok(())
880 }
881
882 /// The fixed-size chunker is measured on the same payload for contrast. It
883 /// cuts at offsets, so one inserted byte shifts every boundary after it and
884 /// almost nothing survives, which is the whole reason for the
885 /// content-defined chunker.
886 #[test]
887 fn cdc_survives_an_insertion_near_the_front() -> Outcome<()> {
888 let payload = pseudorandom(4 * 1024 * 1024, 0x0da7_a5ee_d1);
889 let edited = insert_byte(&payload, 1024);
890
891 let cdc = res!(CdcChunker::new(16 * 1024, 64 * 1024, 256 * 1024));
892 let (before, _) = cdc.split(&payload);
893 let (after, _) = cdc.split(&edited);
894 let kept = shared_fraction(&before, &after);
895 assert!(
896 kept > 0.90,
897 "CDC kept only {:.3} of {} chunks across a front insertion.",
898 kept, after.len(),
899 );
900
901 let fixed = res!(Chunker::new(64 * 1024));
902 let (fbefore, _) = fixed.split(&payload);
903 let (fafter, _) = fixed.split(&edited);
904 let fkept = shared_fraction(&fbefore, &fafter);
905 assert!(
906 fkept < 0.10,
907 "The fixed chunker was expected to lose nearly everything, kept {:.3}.",
908 fkept,
909 );
910 Ok(())
911 }
912
913 #[test]
914 fn cdc_survives_an_insertion_in_the_middle() -> Outcome<()> {
915 let payload = pseudorandom(4 * 1024 * 1024, 0x0da7_a5ee_d2);
916 let edited = insert_byte(&payload, 2 * 1024 * 1024);
917
918 let cdc = res!(CdcChunker::new(16 * 1024, 64 * 1024, 256 * 1024));
919 let (before, _) = cdc.split(&payload);
920 let (after, _) = cdc.split(&edited);
921 let kept = shared_fraction(&before, &after);
922 assert!(
923 kept > 0.90,
924 "CDC kept only {:.3} of {} chunks across a middle insertion.",
925 kept, after.len(),
926 );
927 Ok(())
928 }
929
930 #[test]
931 fn cdc_chunk_sizes_stay_within_bounds() -> Outcome<()> {
932 let cdc = CdcChunker::default();
933 let payload = pseudorandom(4 * 1024 * 1024, 0x51ce_51ce);
934 let (manifest, _) = cdc.split(&payload);
935 assert!(manifest.len() > 4);
936 for (i, cref) in manifest.chunks.iter().enumerate() {
937 assert!(
938 cref.len <= cdc.max_size(),
939 "Chunk {} of {} bytes exceeds the maximum.", i, cref.len,
940 );
941 if i + 1 < manifest.len() {
942 // Only the last chunk may fall below the minimum.
943 assert!(
944 cref.len >= cdc.min_size(),
945 "Chunk {} of {} bytes falls below the minimum.", i, cref.len,
946 );
947 }
948 }
949 let mean = payload.len() as f64 / manifest.len() as f64;
950 let avg = cdc.avg_size() as f64;
951 assert!(
952 mean > avg / 2.0 && mean < avg * 2.0,
953 "Mean chunk size {:.0} strays from the {:.0} requested.", mean, avg,
954 );
955 Ok(())
956 }
957
958 #[test]
959 fn cdc_reassembles_byte_for_byte() -> Outcome<()> {
960 let cdc = res!(CdcChunker::new(1024, 4096, 16384));
961 let store = MemoryCas::new();
962 for payload in [
963 Vec::new(),
964 pseudorandom(1, 1),
965 pseudorandom(999, 2), // Below the minimum.
966 pseudorandom(200_000, 3),
967 vec![0u8; 200_000], // A long identical run.
968 ] {
969 let (manifest, chunks) = cdc.split(&payload);
970 for chunk in &chunks {
971 res!(store.put(chunk));
972 }
973 assert_eq!(manifest.total_len, payload.len());
974 let got = res!(manifest.reassemble(|id| {
975 match res!(store.get(id)) {
976 Some(b) => Ok(b),
977 None => Err(err!("missing chunk {}", id; Test, Missing)),
978 }
979 }));
980 assert_eq!(got, payload);
981 }
982 Ok(())
983 }
984
985 #[test]
986 fn gear_table_is_distinct() -> Outcome<()> {
987 let seen: HashSet<u64> = GEAR.iter().copied().collect();
988 assert_eq!(seen.len(), 256);
989 assert!(!GEAR.iter().any(|g| *g == 0));
990 Ok(())
991 }
992}