Skip to main content

scionic_merkletree/
store.rs

1//! Where a tree's parts are kept.
2//!
3//! A store keeps four kinds of thing, each found by its hash: chunks, the
4//! lists of files, the lists of folders, and records. Because a thing's hash
5//! covers only what the thing is, a chunk, a file or a folder that occurs in
6//! many trees is kept once.
7//!
8//! A store checks nothing: it keeps what it is given under the hash it is
9//! given. Everything that this library puts into a store is checked first,
10//! and everything it takes out is checked again before it is used.
11
12use crate::format::{ChunkRef, FileList, FolderList, Kind, Record, Target};
13use crate::hash::{Hash, Root};
14use crate::threads::on_threads;
15use crate::wire::FRAME_CHUNK;
16use crate::{Error, Result};
17use std::collections::HashMap;
18use std::sync::atomic::{AtomicUsize, Ordering};
19use std::sync::{Arc, Mutex, RwLock};
20
21/// The kinds of thing a store keeps.
22#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
23pub enum Stored {
24    /// A chunk's bytes, under the SHA-256 of them.
25    Chunk,
26    /// A file's whole list, under the file's hash.
27    FileList,
28    /// A folder's whole list, under the folder's hash.
29    FolderList,
30    /// A tree's record, under the tree's root.
31    Record,
32}
33
34/// A place that keeps bytes under hashes.
35///
36/// A store that can say how long a thing is without reading it should have
37/// its own [`Store::size`]: a store on disk above all. Without it, seeing
38/// whether a chunk is there takes a read of the whole chunk. A store on disk
39/// should have its own [`Store::lend`] and [`Store::read_into`] too.
40pub trait Store: Send + Sync {
41    /// Keeps `bytes` under `hash`. Keeping what is kept already changes
42    /// nothing.
43    fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()>;
44
45    /// What is kept under `hash`, if anything.
46    fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>>;
47
48    /// Lends what is kept under `hash` to `with`, and says whether anything
49    /// is kept: `with` is called once if it is, and not at all if it is not.
50    /// The bytes are lent for that call only, and an error from `with` is
51    /// what this gives back.
52    ///
53    /// The library reads a tree's chunks this way. A store on disk should
54    /// have its own, which reads into memory that it uses again: [`Store::get`]
55    /// gives fresh memory for every chunk, and some systems take longer to
56    /// give that than the reading takes. Unless a store has its own, this
57    /// asks `get`.
58    fn lend(
59        &self,
60        kind: Stored,
61        hash: &Hash,
62        with: &mut dyn FnMut(&[u8]) -> Result<()>,
63    ) -> Result<bool> {
64        match self.get(kind, hash)? {
65            Some(bytes) => with(&bytes).map(|()| true),
66            None => Ok(false),
67        }
68    }
69
70    /// Reads what is kept under `hash` into `into`, when it is as long as
71    /// `into` is, and says how long it is: None when nothing is kept. A
72    /// thing of another length is not read, and `into` is left as it was.
73    ///
74    /// The library reads chunks this way where it holds them a while: to
75    /// send them, or to read several at once. Their lists say how long they
76    /// are, so they are read one after another into memory that serves one
77    /// batch after another. A store on disk should have its own, which looks
78    /// at how long a thing is before it reads any of it, and reads it
79    /// straight into `into`. Unless a store has its own, this asks
80    /// [`Store::lend`] and copies what is lent.
81    fn read_into(&self, kind: Stored, hash: &Hash, into: &mut [u8]) -> Result<Option<u64>> {
82        let mut length = None;
83        let held = self.lend(kind, hash, &mut |bytes| {
84            length = Some(bytes.len() as u64);
85            if bytes.len() == into.len() {
86                into.copy_from_slice(bytes);
87            }
88            Ok(())
89        })?;
90        Ok(length.filter(|_| held))
91    }
92
93    /// Whether anything is kept under `hash`. Unless a store has its own,
94    /// this asks how long the thing is, so a store that can say that without
95    /// reading the bytes is not read.
96    fn has(&self, kind: Stored, hash: &Hash) -> Result<bool> {
97        Ok(self.size(kind, hash)?.is_some())
98    }
99
100    /// How many bytes are kept under `hash`.
101    fn size(&self, kind: Stored, hash: &Hash) -> Result<Option<u64>> {
102        Ok(self.get(kind, hash)?.map(|bytes| bytes.len() as u64))
103    }
104
105    /// Forgets what is kept under `hash`.
106    fn remove(&self, kind: Stored, hash: &Hash) -> Result<()>;
107}
108
109/// What a store in memory keeps: bytes, by their kind and their hash.
110type Things = HashMap<(Stored, Hash), Arc<[u8]>>;
111
112/// A store in memory.
113#[derive(Default)]
114pub struct MemoryStore {
115    things: RwLock<Things>,
116}
117
118impl MemoryStore {
119    pub fn new() -> Self {
120        Self::default()
121    }
122
123    fn read(&self) -> std::sync::RwLockReadGuard<'_, Things> {
124        self.things
125            .read()
126            .unwrap_or_else(|poisoned| poisoned.into_inner())
127    }
128
129    fn write(&self) -> std::sync::RwLockWriteGuard<'_, Things> {
130        self.things
131            .write()
132            .unwrap_or_else(|poisoned| poisoned.into_inner())
133    }
134
135    /// How many things of `kind` are kept.
136    pub fn count(&self, kind: Stored) -> usize {
137        self.read().keys().filter(|key| key.0 == kind).count()
138    }
139
140    /// How many bytes the things of `kind` hold together.
141    pub fn bytes(&self, kind: Stored) -> u64 {
142        self.read()
143            .iter()
144            .filter(|(key, _)| key.0 == kind)
145            .map(|(_, bytes)| bytes.len() as u64)
146            .sum()
147    }
148
149    /// The hashes of the things of `kind`, in order.
150    pub fn hashes(&self, kind: Stored) -> Vec<Hash> {
151        let mut hashes: Vec<Hash> = self
152            .read()
153            .keys()
154            .filter(|key| key.0 == kind)
155            .map(|key| key.1)
156            .collect();
157        hashes.sort_unstable();
158        hashes
159    }
160}
161
162impl Store for MemoryStore {
163    fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
164        if self.read().contains_key(&(kind, *hash)) {
165            return Ok(());
166        }
167        // Copied before the lock is taken, so that many threads put at once.
168        let kept: Arc<[u8]> = Arc::from(bytes);
169        self.write().entry((kind, *hash)).or_insert(kept);
170        Ok(())
171    }
172
173    fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
174        Ok(self.read().get(&(kind, *hash)).cloned())
175    }
176
177    fn has(&self, kind: Stored, hash: &Hash) -> Result<bool> {
178        Ok(self.read().contains_key(&(kind, *hash)))
179    }
180
181    fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
182        self.write().remove(&(kind, *hash));
183        Ok(())
184    }
185}
186
187/// The store holds, under `hash`, bytes that are not what the hash says.
188pub(crate) fn damaged(what: &'static str, hash: &Hash) -> Error {
189    Error::Corrupt { what, hash: *hash }
190}
191
192/// The record of `root`, read from the store and checked against the root.
193pub(crate) fn load_record(store: &dyn Store, root: &Root) -> Result<Option<Record>> {
194    let Some(bytes) = store.get(Stored::Record, root.as_hash())? else {
195        return Ok(None);
196    };
197    if Root::of_record(&bytes) != *root {
198        return Err(damaged("a stored record", root.as_hash()));
199    }
200    Record::decode(&bytes).map(Some)
201}
202
203/// A list read from a store has to hold the bytes its parent gave it.
204fn confirm_size(read: u64, wanted: &Target, what: &'static str) -> Result<()> {
205    if read != wanted.size {
206        return Err(Error::SizeMismatch {
207            what,
208            expected: wanted.size,
209            actual: read,
210        });
211    }
212    Ok(())
213}
214
215/// The list of the folder `folder`, read from the store and checked. Bytes
216/// that are not a list with the folder's hash are damaged.
217pub(crate) fn load_folder(store: &dyn Store, folder: &Target) -> Result<Option<FolderList>> {
218    folder.require(Kind::Folder)?;
219    let Some(bytes) = store.get(Stored::FolderList, &folder.hash)? else {
220        return Ok(None);
221    };
222    let what = "a stored folder's list";
223    let list = FolderList::decode(&bytes)
224        .ok()
225        .filter(|list| *list.hash() == folder.hash)
226        .ok_or_else(|| damaged(what, &folder.hash))?;
227    confirm_size(list.size(), folder, what)?;
228    Ok(Some(list))
229}
230
231/// The list of the file `file`, read from the store and checked. Bytes that
232/// are not a list with the file's hash are damaged.
233pub(crate) fn load_file(store: &dyn Store, file: &Target) -> Result<Option<FileList>> {
234    file.require(Kind::File)?;
235    let Some(bytes) = store.get(Stored::FileList, &file.hash)? else {
236        return Ok(None);
237    };
238    let what = "a stored file's list";
239    let list = FileList::decode(&bytes)
240        .ok()
241        .filter(|list| *list.hash() == file.hash)
242        .ok_or_else(|| damaged(what, &file.hash))?;
243    confirm_size(list.size(), file, what)?;
244    Ok(Some(list))
245}
246
247/// Whether `bytes` are the chunk that `item` names.
248pub(crate) fn check_chunk(item: &ChunkRef, bytes: &[u8], what: &'static str) -> Result<()> {
249    if bytes.len() as u64 != u64::from(item.length) {
250        return Err(Error::SizeMismatch {
251            what,
252            expected: u64::from(item.length),
253            actual: bytes.len() as u64,
254        });
255    }
256    if Hash::of(bytes) != item.hash {
257        return Err(Error::HashMismatch { what });
258    }
259    Ok(())
260}
261
262/// Has `store` lend the thing under `hash` to `with`, and holds the store to
263/// what [`Store::lend`] promises: one call when it says it holds the thing,
264/// and none when it says it does not. An error from `with` is given back
265/// whatever the store does with it, so that no store can pass over a chunk
266/// that was found damaged.
267pub(crate) fn lent(
268    store: &dyn Store,
269    kind: Stored,
270    hash: &Hash,
271    with: &mut dyn FnMut(&[u8]) -> Result<()>,
272) -> Result<bool> {
273    let mut calls = 0_u32;
274    let mut failed = None;
275    let held = store.lend(kind, hash, &mut |bytes| {
276        calls += 1;
277        let done = if calls == 1 {
278            with(bytes)
279        } else {
280            Err(Error::Invariant {
281                detail: "a store lent one thing twice",
282            })
283        };
284        done.map_err(|error| {
285            failed.get_or_insert(error);
286            // What went wrong is kept here. The store is only told to stop.
287            Error::Invariant {
288                detail: "what a store lent was refused",
289            }
290        })
291    });
292    if let Some(error) = failed {
293        return Err(error);
294    }
295    match (held?, calls) {
296        (true, 1) => Ok(true),
297        (false, 0) => Ok(false),
298        (true, _) => Err(Error::Invariant {
299            detail: "a store said it held a thing, and lent nothing",
300        }),
301        (false, _) => Err(Error::Invariant {
302            detail: "a store lent a thing, and said it did not hold it",
303        }),
304    }
305}
306
307/// Lends the chunk that `item` names to `with`, read from the store and
308/// checked first, and says whether the store holds it. Bytes that do not hash
309/// to the chunk's hash are damaged. Bytes that do, and are not as many as the
310/// item says, show that the item is wrong.
311pub(crate) fn lend_chunk(
312    store: &dyn Store,
313    item: &ChunkRef,
314    with: &mut dyn FnMut(&[u8]) -> Result<()>,
315) -> Result<bool> {
316    lent(store, Stored::Chunk, &item.hash, &mut |bytes| {
317        check_stored_chunk(item, bytes)?;
318        with(bytes)
319    })
320}
321
322/// Holds bytes read from a store to the chunk that `item` names. Bytes that
323/// do not hash to the chunk's hash are damaged. Bytes that do, and are not
324/// as many as the item says, show that the item is wrong.
325fn check_stored_chunk(item: &ChunkRef, bytes: &[u8]) -> Result<()> {
326    if Hash::of(bytes) != item.hash {
327        return Err(damaged("a stored chunk", &item.hash));
328    }
329    if bytes.len() as u64 != u64::from(item.length) {
330        return Err(Error::SizeMismatch {
331            what: "a stored chunk",
332            expected: u64::from(item.length),
333            actual: bytes.len() as u64,
334        });
335    }
336    Ok(())
337}
338
339pub(crate) fn missing(what: &'static str, hash: &Hash) -> Error {
340    Error::Missing { what, hash: *hash }
341}
342
343fn lock<T>(mutex: &Mutex<T>) -> std::sync::MutexGuard<'_, T> {
344    mutex
345        .lock()
346        .unwrap_or_else(|poisoned| poisoned.into_inner())
347}
348
349/// The most bytes of chunks that are read ahead of what is done with them.
350const AHEAD_BYTES: u64 = 64 << 20;
351
352/// The most chunks that are read ahead, however short.
353const AHEAD_COUNT: usize = 1024;
354
355/// The least bytes of chunks that are worth a thread of their own.
356const AHEAD_BYTES_BY_EACH: u64 = 1 << 20;
357
358/// How chunks are read ahead.
359#[derive(Clone, Copy)]
360enum Ahead {
361    /// Checked, as [`lend_chunk`] checks them.
362    Checked,
363    /// As frames to send, as the store holds them: whoever takes them
364    /// checks them.
365    Framed,
366}
367
368/// What is given each chunk that is read ahead, with its place: None for
369/// one that the store does not hold.
370type Given<'g> = dyn FnMut(usize, Option<&[u8]>) -> Result<()> + 'g;
371
372/// How many bytes a chunk takes when it is read ahead as `ahead` says.
373fn slot_length(item: &ChunkRef, ahead: Ahead) -> usize {
374    let length = item.length as usize;
375    match ahead {
376        Ahead::Checked => length,
377        Ahead::Framed => length + 1,
378    }
379}
380
381/// Reads the chunk that `item` names into `slot`, which is as long as
382/// [`slot_length`] gives, as `ahead` says, and says whether the store holds
383/// it. A chunk that the store holds with another length than `item` gives
384/// is not read into `slot`. Read to be checked, it is lent and checked
385/// whole instead, which tells whether it is damaged or `item` is wrong. Read
386/// to be sent, it is not held: it cannot be the chunk.
387fn read_slot(store: &dyn Store, item: &ChunkRef, ahead: Ahead, slot: &mut [u8]) -> Result<bool> {
388    let length = u64::from(item.length);
389    match ahead {
390        Ahead::Checked => match store.read_into(Stored::Chunk, &item.hash, slot)? {
391            None => Ok(false),
392            Some(held) if held == length => {
393                check_stored_chunk(item, slot)?;
394                Ok(true)
395            }
396            Some(_) => match lend_chunk(store, item, &mut |_| Ok(()))? {
397                false => Ok(false),
398                true => Err(Error::Invariant {
399                    detail: "a store gave two lengths for one chunk",
400                }),
401            },
402        },
403        Ahead::Framed => {
404            let Some((tag, body)) = slot.split_first_mut() else {
405                return Err(Error::Invariant {
406                    detail: "a chunk's frame has no room for its tag",
407                });
408            };
409            *tag = FRAME_CHUNK;
410            Ok(store.read_into(Stored::Chunk, &item.hash, body)? == Some(length))
411        }
412    }
413}
414
415/// Reads chunks from a store ahead of what is done with them, several at
416/// once. The chunks of a batch are read one after another into one stretch
417/// of memory, each into as many bytes as its list gives it, and that memory
418/// serves one batch after another: memory that is used again costs much
419/// less than fresh memory. It is no longer than the longest batch, whatever
420/// the lengths of the chunks of the batches before.
421pub(crate) struct ChunksAhead {
422    memory: Vec<u8>,
423    threads: usize,
424}
425
426impl ChunksAhead {
427    pub(crate) fn new() -> Self {
428        Self::with_threads(0)
429    }
430
431    /// Reads with up to `threads` threads at once; zero is one for each
432    /// core.
433    pub(crate) fn with_threads(threads: usize) -> Self {
434        let threads = match threads {
435            0 => std::thread::available_parallelism().map_or(1, usize::from),
436            threads => threads,
437        };
438        Self {
439            memory: Vec::new(),
440            threads,
441        }
442    }
443
444    /// Lends the chunks that `items` name to `with`, each with its place
445    /// among them, in their order. Each is read from the store and checked
446    /// first, as [`lend_chunk`] checks it. Where the chunks are long enough
447    /// to be worth it, several are read and checked at once, ahead of `with`;
448    /// otherwise each is lent straight from the store. The first chunk that
449    /// is missing or damaged is the error, and `with` is given neither it nor
450    /// any after it.
451    pub(crate) fn lend(
452        &mut self,
453        store: &dyn Store,
454        items: &[ChunkRef],
455        with: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
456    ) -> Result<()> {
457        self.each(
458            store,
459            items,
460            Ahead::Checked,
461            &mut |place, bytes| match bytes {
462                Some(bytes) => with(place, bytes),
463                None => Err(missing("the chunk", &items[place].hash)),
464            },
465        )
466    }
467
468    /// Gives `with` the frames of the chunks that `items` name, in their
469    /// order, read from the store as it holds them: whoever takes them checks
470    /// them. Where the chunks are long enough to be worth it, several are
471    /// read at once, ahead of `with`. A chunk that the store does not hold,
472    /// or holds with another length than its item gives, is given as None,
473    /// and nothing after it.
474    pub(crate) fn frames(
475        &mut self,
476        store: &dyn Store,
477        items: &[ChunkRef],
478        with: &mut dyn FnMut(Option<&[u8]>) -> Result<()>,
479    ) -> Result<()> {
480        self.each(store, items, Ahead::Framed, &mut |_, frame| with(frame))
481    }
482
483    /// Gives `with` each chunk that `items` name, read as `ahead` says, with
484    /// its place among them, in their order. A chunk that the store does not
485    /// hold is given as None, and nothing after it.
486    fn each(
487        &mut self,
488        store: &dyn Store,
489        items: &[ChunkRef],
490        ahead: Ahead,
491        with: &mut Given<'_>,
492    ) -> Result<()> {
493        let mut first = 0;
494        while first < items.len() {
495            let mut count = 0;
496            let mut bytes = 0_u64;
497            for item in items[first..].iter().take(AHEAD_COUNT) {
498                if count > 0 && bytes + u64::from(item.length) > AHEAD_BYTES {
499                    break;
500                }
501                bytes += u64::from(item.length);
502                count += 1;
503            }
504            let batch = &items[first..first + count];
505            let worth = usize::try_from(bytes / AHEAD_BYTES_BY_EACH).unwrap_or(usize::MAX);
506            let workers = self.threads.min(worth.saturating_add(1)).min(count);
507            let mut with_place = |index: usize, bytes: Option<&[u8]>| with(first + index, bytes);
508            let ended = if workers <= 1 {
509                self.one_at_a_time(store, batch, ahead, &mut with_place)?
510            } else {
511                self.several_at_once(store, batch, ahead, workers, &mut with_place)?
512            };
513            if ended {
514                return Ok(());
515            }
516            first += count;
517        }
518        Ok(())
519    }
520
521    /// Gives `with` the chunks of `batch`, read one at a time: a checked one
522    /// straight from the store. Says whether one was missing.
523    fn one_at_a_time(
524        &mut self,
525        store: &dyn Store,
526        batch: &[ChunkRef],
527        ahead: Ahead,
528        with: &mut Given<'_>,
529    ) -> Result<bool> {
530        for (index, item) in batch.iter().enumerate() {
531            let held = match ahead {
532                Ahead::Checked => lend_chunk(store, item, &mut |bytes| with(index, Some(bytes)))?,
533                Ahead::Framed => {
534                    let frame = self.room(slot_length(item, ahead));
535                    let held = read_slot(store, item, ahead, frame)?;
536                    if held {
537                        with(index, Some(frame))?;
538                    }
539                    held
540                }
541            };
542            if !held {
543                with(index, None)?;
544                return Ok(true);
545            }
546        }
547        Ok(false)
548    }
549
550    /// Reads the chunks of `batch` on `workers` threads, and then gives them
551    /// to `with` in their order. Says whether one was missing.
552    fn several_at_once(
553        &mut self,
554        store: &dyn Store,
555        batch: &[ChunkRef],
556        ahead: Ahead,
557        workers: usize,
558        with: &mut Given<'_>,
559    ) -> Result<bool> {
560        let lengths: Vec<usize> = batch.iter().map(|item| slot_length(item, ahead)).collect();
561        // Each chunk's own part of the memory, which one thread reads it
562        // into.
563        let mut rest = self.room(lengths.iter().sum());
564        let slots: Vec<Mutex<&mut [u8]>> = lengths
565            .iter()
566            .map(|&length| {
567                let (slot, after) = std::mem::take(&mut rest).split_at_mut(length);
568                rest = after;
569                Mutex::new(slot)
570            })
571            .collect();
572        let next = AtomicUsize::new(0);
573        let work = || {
574            let mut done = Vec::new();
575            loop {
576                let index = next.fetch_add(1, Ordering::Relaxed);
577                let Some(item) = batch.get(index) else {
578                    return done;
579                };
580                let held = read_slot(store, item, ahead, &mut lock(&slots[index]));
581                done.push((index, held));
582            }
583        };
584        let mut done: Vec<_> = on_threads(workers, &work).into_iter().flatten().collect();
585        done.sort_unstable_by_key(|(index, _)| *index);
586        for (index, held) in done {
587            if !held? {
588                with(index, None)?;
589                return Ok(true);
590            }
591            with(index, Some(&lock(&slots[index])))?;
592        }
593        Ok(false)
594    }
595
596    /// The first `length` bytes of the memory, which grows to hold them, and
597    /// to no more. What it held is not needed then: fresh memory, which the
598    /// system gives cleared, is neither copied nor cleared here.
599    fn room(&mut self, length: usize) -> &mut [u8] {
600        if self.memory.len() < length {
601            self.memory = vec![0; length];
602        }
603        &mut self.memory[..length]
604    }
605
606    /// How many bytes of memory this holds for chunks.
607    #[cfg(test)]
608    fn memory_held(&self) -> usize {
609        self.memory.capacity()
610    }
611}
612
613#[cfg(test)]
614mod tests {
615    use super::*;
616
617    #[test]
618    fn a_store_keeps_each_kind_apart_and_each_thing_once() {
619        let store = MemoryStore::new();
620        let hash = Hash::of(b"x");
621        store.put(Stored::Chunk, &hash, b"x").unwrap();
622        store.put(Stored::Chunk, &hash, b"x").unwrap();
623        assert_eq!(store.count(Stored::Chunk), 1);
624        assert_eq!(store.bytes(Stored::Chunk), 1);
625        assert!(store.has(Stored::Chunk, &hash).unwrap());
626        assert!(!store.has(Stored::FileList, &hash).unwrap());
627        assert_eq!(store.size(Stored::Chunk, &hash).unwrap(), Some(1));
628        assert_eq!(store.size(Stored::Record, &hash).unwrap(), None);
629        assert_eq!(&*store.get(Stored::Chunk, &hash).unwrap().unwrap(), b"x");
630        assert_eq!(store.hashes(Stored::Chunk), vec![hash]);
631        store.remove(Stored::Chunk, &hash).unwrap();
632        assert!(store.get(Stored::Chunk, &hash).unwrap().is_none());
633    }
634
635    /// A store that says how long a thing is, and counts how often a thing
636    /// is read from it.
637    struct Sized {
638        inner: MemoryStore,
639        read: std::sync::atomic::AtomicUsize,
640    }
641
642    impl Store for Sized {
643        fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
644            self.inner.put(kind, hash, bytes)
645        }
646
647        fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
648            self.read.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
649            self.inner.get(kind, hash)
650        }
651
652        fn size(&self, kind: Stored, hash: &Hash) -> Result<Option<u64>> {
653            self.inner.size(kind, hash)
654        }
655
656        fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
657            self.inner.remove(kind, hash)
658        }
659    }
660
661    #[test]
662    fn a_store_that_says_how_long_a_thing_is_is_not_read_to_see_what_it_holds() {
663        let store = Sized {
664            inner: MemoryStore::new(),
665            read: Default::default(),
666        };
667        let content: Vec<u8> = (0..5000_u32).map(|at| (at % 251) as u8).collect();
668        let mut builder = crate::Builder::new(&store, crate::Chunking::fixed(16).unwrap());
669        let first = builder.file_from_bytes(&content).unwrap();
670        // Built again, every chunk and the list are there already. Seeing
671        // that takes no read: for a store on disk, a read is the whole of a
672        // chunk.
673        let again = builder.file_from_bytes(&content).unwrap();
674        assert_eq!(again, first);
675        assert!(store.inner.count(Stored::Chunk) > 100);
676        assert_eq!(store.read.load(std::sync::atomic::Ordering::Relaxed), 0);
677        // And it is still asked rightly.
678        assert!(!store.has(Stored::Chunk, &Hash::of(b"not there")).unwrap());
679        assert!(store.has(Stored::FileList, &first.hash).unwrap());
680        assert!(!store.has(Stored::FolderList, &first.hash).unwrap());
681    }
682
683    #[test]
684    fn what_is_read_from_a_store_is_checked_before_it_is_used() {
685        let store = MemoryStore::new();
686        let item = ChunkRef::of(b"right").unwrap();
687        // How many times a chunk was handed on.
688        let seen = std::cell::Cell::new(0);
689        let mut count = |_: &[u8]| {
690            seen.set(seen.get() + 1);
691            Ok(())
692        };
693        // A store that holds other bytes under a chunk's hash.
694        store.put(Stored::Chunk, &item.hash, b"wrong").unwrap();
695        assert!(matches!(
696            lend_chunk(&store, &item, &mut count),
697            Err(Error::Corrupt { .. })
698        ));
699        store.remove(Stored::Chunk, &item.hash).unwrap();
700        store.put(Stored::Chunk, &item.hash, b"longer").unwrap();
701        assert!(matches!(
702            lend_chunk(&store, &item, &mut count),
703            Err(Error::Corrupt { .. })
704        ));
705        // The chunk itself, named by an item that gives it another length.
706        store.remove(Stored::Chunk, &item.hash).unwrap();
707        store.put(Stored::Chunk, &item.hash, b"right").unwrap();
708        assert!(matches!(
709            lend_chunk(&store, &ChunkRef { length: 4, ..item }, &mut count),
710            Err(Error::SizeMismatch { .. })
711        ));
712        // Nothing that failed a check was handed on.
713        assert_eq!(seen.get(), 0);
714        assert!(matches!(lend_chunk(&store, &item, &mut count), Ok(true)));
715        assert_eq!(seen.get(), 1);
716
717        // A list kept under another list's hash.
718        let list = FileList::new(vec![item]).unwrap();
719        let other = FileList::new(vec![item, item]).unwrap();
720        store
721            .put(Stored::FileList, list.hash(), &other.encode())
722            .unwrap();
723        assert!(matches!(
724            load_file(&store, &list.target()),
725            Err(Error::Corrupt { .. })
726        ));
727        // The right list, asked for with another size than it has.
728        store
729            .put(Stored::FileList, other.hash(), &other.encode())
730            .unwrap();
731        let resized = Target {
732            size: other.size() + 1,
733            ..other.target()
734        };
735        assert!(matches!(
736            load_file(&store, &resized),
737            Err(Error::SizeMismatch { .. })
738        ));
739        assert!(load_file(&store, &other.target()).unwrap().is_some());
740        // A file's list is not found as a folder's.
741        let as_folder = Target {
742            kind: Kind::Folder,
743            ..other.target()
744        };
745        assert!(load_folder(&store, &as_folder).unwrap().is_none());
746        assert!(load_file(&store, &as_folder).is_err());
747
748        // A record kept under another root.
749        let root = Root::of_record(b"one");
750        store.put(Stored::Record, root.as_hash(), b"two").unwrap();
751        assert!(matches!(
752            load_record(&store, &root),
753            Err(Error::Corrupt { .. })
754        ));
755    }
756
757    /// A store that lends as it is set to, rightly or not.
758    struct Lending {
759        inner: MemoryStore,
760        /// How many times it hands a thing to `with`.
761        calls: usize,
762        /// Whether it says that it holds the thing.
763        says: bool,
764        /// Whether it passes over an error that `with` gives.
765        passes_over: bool,
766    }
767
768    impl Store for Lending {
769        fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
770            self.inner.put(kind, hash, bytes)
771        }
772
773        fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
774            self.inner.get(kind, hash)
775        }
776
777        fn lend(
778            &self,
779            kind: Stored,
780            hash: &Hash,
781            with: &mut dyn FnMut(&[u8]) -> Result<()>,
782        ) -> Result<bool> {
783            let bytes = self
784                .inner
785                .get(kind, hash)?
786                .unwrap_or_else(|| Arc::from(&b""[..]));
787            for _ in 0..self.calls {
788                let done = with(&bytes);
789                if !self.passes_over {
790                    done?;
791                }
792            }
793            Ok(self.says)
794        }
795
796        fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
797            self.inner.remove(kind, hash)
798        }
799    }
800
801    #[test]
802    fn a_store_is_held_to_what_lending_promises() {
803        let item = ChunkRef::of(b"right").unwrap();
804        // What lending a chunk gave, and what was handed on of it.
805        let lend = |calls, says, passes_over, kept: &[u8]| {
806            let store = Lending {
807                inner: MemoryStore::new(),
808                calls,
809                says,
810                passes_over,
811            };
812            store.put(Stored::Chunk, &item.hash, kept).unwrap();
813            let mut seen = Vec::new();
814            let lent = lend_chunk(&store, &item, &mut |bytes| {
815                seen.push(bytes.to_vec());
816                Ok(())
817            });
818            (lent, seen)
819        };
820        // As promised: one call for what is held, and none for what is not.
821        let (lent, seen) = lend(1, true, false, b"right");
822        assert!(matches!(lent, Ok(true)));
823        assert_eq!(seen, vec![b"right".to_vec()]);
824        assert!(matches!(lend(0, false, false, b"right").0, Ok(false)));
825        // A second call is refused, and nothing of it is handed on.
826        let (lent, seen) = lend(2, true, true, b"right");
827        assert!(matches!(lent, Err(Error::Invariant { .. })));
828        assert_eq!(seen.len(), 1);
829        // Said to be held, and nothing lent; lent, and said not to be held.
830        assert!(matches!(
831            lend(0, true, false, b"right").0,
832            Err(Error::Invariant { .. })
833        ));
834        assert!(matches!(
835            lend(1, false, false, b"right").0,
836            Err(Error::Invariant { .. })
837        ));
838        // Damaged bytes stay an error when the store passes over it, and are
839        // never handed on.
840        for passes_over in [false, true] {
841            let (lent, seen) = lend(1, true, passes_over, b"wrong");
842            assert!(matches!(lent, Err(Error::Corrupt { .. })));
843            assert!(seen.is_empty());
844        }
845    }
846
847    #[test]
848    fn chunks_read_ahead_take_no_more_memory_than_the_longest_batch() {
849        // In each batch a long chunk comes after short ones, at another place
850        // each time. Memory that each place kept for the longest chunk it
851        // held would come to all of them.
852        let store = MemoryStore::new();
853        let long_bytes = vec![7_u8; 1 << 20];
854        let long = ChunkRef::of(&long_bytes).unwrap();
855        store.put(Stored::Chunk, &long.hash, &long_bytes).unwrap();
856        let short = ChunkRef::of(b"s").unwrap();
857        store.put(Stored::Chunk, &short.hash, b"s").unwrap();
858        let mut ahead = ChunksAhead::with_threads(4);
859        for place in 0..64 {
860            let mut items = vec![short; place];
861            items.push(long);
862            let mut given = Vec::new();
863            ahead
864                .frames(&store, &items, &mut |frame| {
865                    given.push(frame.map(<[u8]>::len));
866                    Ok(())
867                })
868                .unwrap();
869            let mut lengths: Vec<_> = items
870                .iter()
871                .map(|item| Some(item.length as usize + 1))
872                .collect();
873            assert_eq!(given, lengths);
874            // Checked, every eighth time: each check hashes the long chunk.
875            if place % 8 == 0 {
876                given.clear();
877                ahead
878                    .lend(&store, &items, &mut |_, bytes| {
879                        given.push(Some(bytes.len()));
880                        Ok(())
881                    })
882                    .unwrap();
883                lengths
884                    .iter_mut()
885                    .for_each(|length| *length = length.map(|length| length - 1));
886                assert_eq!(given, lengths);
887            }
888        }
889        let most = long_bytes.len() + 1 + 64 * 2;
890        assert!(ahead.memory_held() <= most, "{} bytes", ahead.memory_held());
891    }
892}