Skip to main content

scionic_merkletree/
intake.rs

1//! Taking a tree in, and checking a tree that is held.
2//!
3//! There is one set of checks, and it is here. A tree that arrives from a
4//! peer, a tree read from a bundle and a tree that already sits in a store
5//! all go through an [`Intake`]:
6//!
7//! * the record must hash to the root that was asked for;
8//! * a list is taken only when a list that is already checked names it, and
9//!   only when it has the hash, the size and the chunk lengths it has to;
10//! * a chunk is taken only when a file's list that is already checked names
11//!   it, and only with the bytes and the length that list gives it;
12//! * at the end nothing may be missing, folders may not sit too deep, and
13//!   the record's totals must be those of the tree.
14//!
15//! So parents come first, and nothing is kept before it is tied to the root.
16//! A frame never says which hash it belongs under. Its hash is worked out
17//! from its bytes.
18
19use crate::fastcdc::StreamChunker;
20use crate::format::{
21    ChunkRef, Chunking, FileList, FolderList, Kind, Record, Target, Totals, LIST_ITEM_BYTES,
22    MAX_CHUNK_BYTES, MAX_FOLDER_DEPTH, MAX_RECORD_BYTES,
23};
24use crate::hash::{Hash, Root};
25use crate::store::{lent, load_record, missing, Store, Stored};
26use crate::threads::{cores, on_threads};
27use crate::wire::{
28    read_next_onto, Next, Request, FRAME_CHUNK, FRAME_FILE_LIST, FRAME_FOLDER_LIST, FRAME_RECORD,
29};
30use crate::{Error, Result};
31use std::collections::{BTreeMap, HashMap};
32use std::io::Read;
33use std::sync::atomic::{AtomicUsize, Ordering};
34use std::sync::{Arc, Mutex, MutexGuard};
35
36/// The most chunks one request asks for.
37const CHUNKS_PER_REQUEST: u32 = 64;
38
39/// How many chunks one thread looks for in a store before another thread
40/// helps. A store on disk looks at a file for each, which takes tens of
41/// microseconds, and handing work to another thread takes about one.
42const LOOKS_BY_EACH: usize = 64;
43
44fn invalid(detail: &str) -> Error {
45    Error::InvalidData {
46        detail: detail.to_owned(),
47    }
48}
49
50/// What a frame turned out to be, once its hash was worked out.
51#[derive(Clone, Copy, Debug, Eq, PartialEq)]
52pub enum Arrived {
53    Record,
54    FolderList(Hash),
55    FileList(Hash),
56    Chunk(Hash),
57}
58
59/// What became of a frame that an intake accepted.
60#[derive(Clone, Copy, Debug, Eq, PartialEq)]
61pub struct Accepted {
62    pub what: Arrived,
63    /// Whether it was kept now. It is not when it was held already.
64    pub kept: bool,
65}
66
67/// A tree that is whole and checked.
68#[derive(Clone, Debug, Eq, PartialEq)]
69pub struct Summary {
70    pub record: Record,
71    /// How many different folders the tree has.
72    pub folders: u64,
73    /// How many different files the tree has.
74    pub files: u64,
75}
76
77/// How a held tree is checked, beyond what is always checked.
78#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
79pub struct VerifyOptions {
80    rechunk: bool,
81    discard: bool,
82    workers: usize,
83}
84
85impl VerifyOptions {
86    pub fn new() -> Self {
87        Self::default()
88    }
89
90    /// Also chunks every file's bytes again, and refuses a file whose list is
91    /// not the one the chunker gives. With this, the same bytes always have
92    /// the same file hash. It costs one more pass over the bytes.
93    pub fn rechunk(mut self, on: bool) -> Self {
94        self.rechunk = on;
95        self
96    }
97
98    /// Removes from the store what is damaged there: a chunk, a list or a
99    /// record whose bytes are not what its hash says. The check then ends
100    /// with one of them as missing, and a fetch of the tree brings them all
101    /// again. Without this the check stops at a damaged thing and names it,
102    /// and the store is left as it is.
103    pub fn discard_damaged(mut self, on: bool) -> Self {
104        self.discard = on;
105        self
106    }
107
108    /// How many threads check the tree at once: they hash its chunks, and look
109    /// in the store for the chunks of a long list. Zero is one for each core.
110    pub fn workers(mut self, workers: usize) -> Self {
111        self.workers = workers;
112        self
113    }
114}
115
116#[derive(Clone, Copy, Default)]
117struct Mode {
118    /// Chunk again the files that are held whole.
119    rechunk: bool,
120    /// Remove from the store what is damaged there, and want it again.
121    discard: bool,
122    /// How many threads look in the store at once for the chunks of a list.
123    /// Zero is one for each core.
124    threads: usize,
125}
126
127struct FolderSlot {
128    size: u64,
129    order: u64,
130    held: bool,
131    /// The folders directly inside this one.
132    inside: Vec<Hash>,
133}
134
135struct FileSlot {
136    size: u64,
137    order: u64,
138    held: bool,
139}
140
141struct ChunkSlot {
142    length: u32,
143    /// Where the chunk was first listed, while it is not held: the file,
144    /// by the order it was named in, and the chunk's number there.
145    wanted_at: Option<(u64, u64)>,
146}
147
148/// Takes one tree into a store, checking every part as it arrives.
149///
150/// An intake is given frames in any order that puts parents first. What the
151/// store holds already is found when it is named, and is not asked for.
152///
153/// A frame that is refused at the door leaves the intake as it was: one that
154/// nothing names, one that is malformed, one that was not asked for. A list
155/// that is named and then fails a check shows that the tree itself is wrong.
156/// The list is not kept, and the intake is done: every later call gives
157/// [`Error::IntakeFailed`]. A new intake picks up from what the store holds.
158///
159/// What the store holds under a hash and is not what the hash says is
160/// damaged. An intake removes it from the store and wants it again, so a tree
161/// that was harmed where it is kept is made whole by fetching it once more.
162/// Nothing a peer sends can make an intake remove what is sound.
163pub struct Intake<'s> {
164    store: &'s dyn Store,
165    root: Root,
166    mode: Mode,
167    record: Option<Record>,
168    /// How the files are chunked, for a tree that has no record yet.
169    measuring: Option<Chunking>,
170    folders: HashMap<Hash, FolderSlot>,
171    files: HashMap<Hash, FileSlot>,
172    chunks: HashMap<Hash, ChunkSlot>,
173    /// Lists that are named and not held, in the order they were named.
174    wanted_lists: BTreeMap<u64, Target>,
175    /// Chunks that are named and not held, by where they were first listed.
176    wanted_chunks: BTreeMap<(u64, u64), Hash>,
177    file_by_order: HashMap<u64, Hash>,
178    next_order: u64,
179    counted: Totals,
180    pending: Vec<Target>,
181    /// The files to chunk again, once their chunks are hashed.
182    to_rechunk: Vec<Hash>,
183    chunker: Option<StreamChunker>,
184    /// A step that changes what the intake knows failed half way.
185    failed: bool,
186}
187
188impl<'s> Intake<'s> {
189    /// Starts taking in the tree with this root. If the store holds the
190    /// tree's record, everything else it holds of the tree is found now.
191    pub fn new(store: &'s dyn Store, root: Root) -> Result<Self> {
192        let mode = Mode {
193            discard: true,
194            ..Mode::default()
195        };
196        Self::with_mode(store, root, mode)
197    }
198
199    fn bare(store: &'s dyn Store, root: Root, mode: Mode) -> Self {
200        Self {
201            store,
202            root,
203            mode,
204            record: None,
205            measuring: None,
206            folders: HashMap::new(),
207            files: HashMap::new(),
208            chunks: HashMap::new(),
209            wanted_lists: BTreeMap::new(),
210            wanted_chunks: BTreeMap::new(),
211            file_by_order: HashMap::new(),
212            next_order: 0,
213            counted: Totals::default(),
214            pending: Vec::new(),
215            to_rechunk: Vec::new(),
216            chunker: None,
217            failed: false,
218        }
219    }
220
221    fn with_mode(store: &'s dyn Store, root: Root, mode: Mode) -> Result<Self> {
222        let mut intake = Self::bare(store, root, mode);
223        match load_record(store, &root) {
224            Ok(Some(record)) => intake.begin(record)?,
225            Ok(None) => {}
226            // A record that is damaged where it is kept is fetched again.
227            Err(Error::Corrupt { .. }) if mode.discard => {
228                store.remove(Stored::Record, root.as_hash())?;
229            }
230            Err(error) => return Err(error),
231        }
232        Ok(intake)
233    }
234
235    /// Checks every list under `top` as an intake checks it, for a tree that
236    /// has no record yet, and counts what its record has to say: each
237    /// different chunk and each different list, once. The store must hold
238    /// every list. This is how a builder comes by a record's totals, so a
239    /// tree that is built has passed the checks of a tree that is taken in.
240    /// Up to `threads` threads look in the store at once.
241    pub(crate) fn measure(
242        store: &'s dyn Store,
243        top: Target,
244        chunking: Chunking,
245        threads: usize,
246    ) -> Result<Totals> {
247        let mode = Mode {
248            threads,
249            ..Mode::default()
250        };
251        let mut intake = Self::bare(store, Root::from_hash(Hash::ZERO), mode);
252        intake.measuring = Some(chunking);
253        intake.refer(top)?;
254        intake.drain()?;
255        intake.lists_held()?;
256        intake.check_depth(&top)?;
257        Ok(intake.counted)
258    }
259
260    pub fn root(&self) -> &Root {
261        &self.root
262    }
263
264    /// The tree's record, once it is in. Its totals say how much the tree
265    /// will take before any of it is taken, and an intake stops as soon as a
266    /// tree turns out to hold more than its record says.
267    pub fn record(&self) -> Option<&Record> {
268        self.record.as_ref()
269    }
270
271    /// How many lists and chunks are named and not held yet. The record
272    /// counts as one while it is not in.
273    pub fn outstanding(&self) -> usize {
274        usize::from(self.record.is_none()) + self.wanted_lists.len() + self.wanted_chunks.len()
275    }
276
277    /// How many bytes of lists the record still leaves room for.
278    fn lists_left(&self) -> usize {
279        let Some(record) = &self.record else {
280            return 0;
281        };
282        let left = record
283            .totals()
284            .list_bytes
285            .saturating_sub(self.counted.list_bytes);
286        usize::try_from(left).unwrap_or(usize::MAX)
287    }
288
289    /// The longest chunk the tree's way of chunking allows.
290    fn longest_chunk(&self) -> usize {
291        match self.record.as_ref().map(Record::chunking) {
292            Some(Chunking::Fixed(length)) => length.get() as usize,
293            _ => MAX_CHUNK_BYTES,
294        }
295    }
296
297    /// The longest frame that a stream of this tree can hold, whatever comes
298    /// next: for a reader of a stream that was not asked frame by frame, as
299    /// a bundle is. Before the record it is the longest record. After it,
300    /// it is the longest of a record, a chunk, and all the bytes of lists
301    /// that the record gives the tree. What the store holds already may
302    /// come too, and is passed over, so this does not shrink as lists come.
303    pub fn frame_limit(&self) -> usize {
304        let Some(record) = &self.record else {
305            return MAX_RECORD_BYTES;
306        };
307        usize::try_from(record.totals().list_bytes)
308            .unwrap_or(usize::MAX)
309            .max(self.longest_chunk())
310            .saturating_add(1)
311            .max(MAX_RECORD_BYTES)
312    }
313
314    /// The longest frame that can answer one of this intake's requests. A
315    /// peer that sends a longer one is not answering what was asked, and its
316    /// frame need not be read: a file's list is no longer than the file's
317    /// size allows, no list is longer than the record leaves room for, and a
318    /// chunk is no longer than the tree's way of chunking allows.
319    pub fn answer_limit(&self, request: &Request) -> usize {
320        let limit = match request {
321            Request::Record(_) => MAX_RECORD_BYTES,
322            Request::Folder(_) => self.lists_left().saturating_add(1),
323            Request::File(file) => {
324                let most = match (&self.record, self.files.get(file)) {
325                    (Some(record), Some(slot)) => record.chunking().count_bounds(slot.size).1,
326                    _ => 0,
327                };
328                usize::try_from(most)
329                    .unwrap_or(usize::MAX)
330                    .saturating_mul(LIST_ITEM_BYTES)
331                    .min(self.lists_left())
332                    .saturating_add(1)
333            }
334            Request::Chunks { .. } | Request::Chunk(_) => self.longest_chunk() + 1,
335            _ => 0,
336        };
337        // A refusal takes two bytes, and is always let through.
338        limit.max(2)
339    }
340
341    fn begin(&mut self, record: Record) -> Result<()> {
342        let top = record.top();
343        self.record = Some(record);
344        self.refer(top)?;
345        self.drain()
346    }
347
348    fn recorded(&self) -> Result<&Record> {
349        self.record.as_ref().ok_or(Error::NotWanted {
350            what: "a frame that comes before the record",
351        })
352    }
353
354    /// How the tree's files are chunked.
355    fn chunking(&self) -> Result<Chunking> {
356        match self.measuring {
357            Some(chunking) => Ok(chunking),
358            None => Ok(self.recorded()?.chunking()),
359        }
360    }
361
362    /// Every list that is named has to be held.
363    fn lists_held(&self) -> Result<()> {
364        match self.wanted_lists.values().next() {
365            Some(target) => Err(missing(
366                match target.kind {
367                    Kind::Folder => "the list of the folder",
368                    Kind::File => "the list of the file",
369                },
370                &target.hash,
371            )),
372            None => Ok(()),
373        }
374    }
375
376    /// The store holds, under `hash`, bytes that are not what the hash says.
377    /// They are removed when this intake may do that, so that they are
378    /// wanted again. Otherwise they are an error that names them.
379    fn damaged(&self, kind: Stored, hash: &Hash, what: &'static str) -> Result<()> {
380        if self.mode.discard {
381            self.store.remove(kind, hash)
382        } else {
383            Err(Error::Corrupt { what, hash: *hash })
384        }
385    }
386
387    /// Whether the store holds the chunk of each of `items`, in their order:
388    /// asked on several threads at once where there are enough of them to
389    /// share.
390    fn held_of(&self, items: &[(u64, &ChunkRef)]) -> Vec<Result<bool>> {
391        let threads = match self.mode.threads {
392            0 => cores(),
393            threads => threads,
394        };
395        let workers = (items.len() / LOOKS_BY_EACH).clamp(1, threads);
396        if workers == 1 {
397            return items.iter().map(|(_, item)| self.holds(item)).collect();
398        }
399        let next = AtomicUsize::new(0);
400        let work = || {
401            let mut found = Vec::new();
402            loop {
403                let index = next.fetch_add(1, Ordering::Relaxed);
404                let Some((_, item)) = items.get(index) else {
405                    return found;
406                };
407                found.push((index, self.holds(item)));
408            }
409        };
410        let mut found: Vec<(usize, Result<bool>)> =
411            on_threads(workers, &work).into_iter().flatten().collect();
412        found.sort_unstable_by_key(|(index, _)| *index);
413        found.into_iter().map(|(_, held)| held).collect()
414    }
415
416    /// Whether the store holds the chunk that `item` names. The chunk's
417    /// bytes are counted here, not hashed.
418    fn holds(&self, item: &ChunkRef) -> Result<bool> {
419        let size = match self.store.size(Stored::Chunk, &item.hash)? {
420            None => return Ok(false),
421            Some(size) if size == u64::from(item.length) => return Ok(true),
422            Some(size) => size,
423        };
424        // Either the store's bytes are damaged, or the list gives the chunk
425        // a length it does not have. Only damaged bytes are ever removed: a
426        // list that names a sound chunk wrongly must not cost the store it.
427        match self.store.get(Stored::Chunk, &item.hash)? {
428            None => Ok(false),
429            Some(bytes) if Hash::of(&bytes) == item.hash => Err(Error::SizeMismatch {
430                what: "a held chunk",
431                expected: u64::from(item.length),
432                actual: size,
433            }),
434            Some(_) => {
435                self.damaged(Stored::Chunk, &item.hash, "a stored chunk")?;
436                Ok(false)
437            }
438        }
439    }
440
441    /// Notes that a checked parent names `target`.
442    fn refer(&mut self, target: Target) -> Result<()> {
443        let known = match target.kind {
444            Kind::Folder => self.folders.get(&target.hash).map(|slot| slot.size),
445            Kind::File => self.files.get(&target.hash).map(|slot| slot.size),
446        };
447        if let Some(size) = known {
448            return if size == target.size {
449                Ok(())
450            } else {
451                Err(Error::SizeMismatch {
452                    what: "a file or folder that is named twice",
453                    expected: size,
454                    actual: target.size,
455                })
456            };
457        }
458        let order = self.next_order;
459        self.next_order += 1;
460        match target.kind {
461            Kind::Folder => {
462                self.folders.insert(
463                    target.hash,
464                    FolderSlot {
465                        size: target.size,
466                        order,
467                        held: false,
468                        inside: Vec::new(),
469                    },
470                );
471            }
472            Kind::File => {
473                self.files.insert(
474                    target.hash,
475                    FileSlot {
476                        size: target.size,
477                        order,
478                        held: false,
479                    },
480                );
481                self.file_by_order.insert(order, target.hash);
482            }
483        }
484        self.pending.push(target);
485        Ok(())
486    }
487
488    /// Looks in the store for every list that was newly named. A list that
489    /// is there is checked like one that arrives, and the lists it names are
490    /// looked for in turn. A list that is not there is wanted, and so is one
491    /// that is damaged there.
492    fn drain(&mut self) -> Result<()> {
493        while let Some(target) = self.pending.pop() {
494            match target.kind {
495                Kind::Folder => {
496                    let held = self.store.get(Stored::FolderList, &target.hash)?;
497                    let list = held.as_deref().map(|bytes| {
498                        FolderList::decode(bytes)
499                            .ok()
500                            .filter(|list| *list.hash() == target.hash)
501                    });
502                    match list {
503                        Some(Some(list)) => self.admit_folder(&list)?,
504                        Some(None) => {
505                            let what = "a stored folder's list";
506                            self.damaged(Stored::FolderList, &target.hash, what)?;
507                            self.want(target);
508                        }
509                        None => self.want(target),
510                    }
511                }
512                Kind::File => {
513                    let held = self.store.get(Stored::FileList, &target.hash)?;
514                    let list = held.as_deref().map(|bytes| {
515                        FileList::decode(bytes)
516                            .ok()
517                            .filter(|list| *list.hash() == target.hash)
518                    });
519                    match list {
520                        Some(Some(list)) => self.admit_file(&list)?,
521                        Some(None) => {
522                            let what = "a stored file's list";
523                            self.damaged(Stored::FileList, &target.hash, what)?;
524                            self.want(target);
525                        }
526                        None => self.want(target),
527                    }
528                }
529            }
530        }
531        Ok(())
532    }
533
534    fn want(&mut self, target: Target) {
535        let order = match target.kind {
536            Kind::Folder => self.folders.get(&target.hash).map(|slot| slot.order),
537            Kind::File => self.files.get(&target.hash).map(|slot| slot.order),
538        };
539        if let Some(order) = order {
540            self.wanted_lists.insert(order, target);
541        }
542    }
543
544    fn count_list_bytes(&mut self, bytes: u64) -> Result<()> {
545        self.counted.list_bytes =
546            self.counted
547                .list_bytes
548                .checked_add(bytes)
549                .ok_or(Error::SizeOverflow {
550                    field: "list bytes",
551                })?;
552        // A tree that is being measured has no record to be held to yet.
553        let Some(record) = &self.record else {
554            return Ok(());
555        };
556        let recorded = record.totals().list_bytes;
557        if self.counted.list_bytes > recorded {
558            return Err(Error::TotalsMismatch {
559                field: "list bytes",
560                recorded,
561                counted: self.counted.list_bytes,
562            });
563        }
564        Ok(())
565    }
566
567    fn count_chunk(&mut self, length: u32) -> Result<()> {
568        self.counted.chunks = self
569            .counted
570            .chunks
571            .checked_add(1)
572            .ok_or(Error::SizeOverflow { field: "chunks" })?;
573        self.counted.chunk_bytes = self
574            .counted
575            .chunk_bytes
576            .checked_add(u64::from(length))
577            .ok_or(Error::SizeOverflow {
578                field: "chunk bytes",
579            })?;
580        let Some(record) = &self.record else {
581            return Ok(());
582        };
583        let recorded = record.totals();
584        if self.counted.chunks > recorded.chunks {
585            return Err(Error::TotalsMismatch {
586                field: "chunks",
587                recorded: recorded.chunks,
588                counted: self.counted.chunks,
589            });
590        }
591        if self.counted.chunk_bytes > recorded.chunk_bytes {
592            return Err(Error::TotalsMismatch {
593                field: "chunk bytes",
594                recorded: recorded.chunk_bytes,
595                counted: self.counted.chunk_bytes,
596            });
597        }
598        Ok(())
599    }
600
601    /// Takes a folder's list that is named, and notes what it names.
602    fn admit_folder(&mut self, list: &FolderList) -> Result<()> {
603        let slot = self.folders.get_mut(list.hash()).ok_or(Error::Invariant {
604            detail: "a folder is admitted before it is named",
605        })?;
606        if slot.size != list.size() {
607            return Err(Error::SizeMismatch {
608                what: "a folder",
609                expected: slot.size,
610                actual: list.size(),
611            });
612        }
613        slot.held = true;
614        slot.inside = list
615            .entries()
616            .iter()
617            .filter(|entry| entry.kind() == Kind::Folder)
618            .map(|entry| *entry.hash())
619            .collect();
620        slot.inside.sort_unstable();
621        slot.inside.dedup();
622        let order = slot.order;
623        self.wanted_lists.remove(&order);
624        self.count_list_bytes(list.encoded_len())?;
625        for entry in list.entries() {
626            self.refer(entry.target())?;
627        }
628        Ok(())
629    }
630
631    /// Takes a file's list that is named, and notes the chunks it names.
632    fn admit_file(&mut self, list: &FileList) -> Result<()> {
633        let chunking = self.chunking()?;
634        list.check_chunking(chunking)?;
635        let slot = self.files.get_mut(list.hash()).ok_or(Error::Invariant {
636            detail: "a file is admitted before it is named",
637        })?;
638        if slot.size != list.size() {
639            return Err(Error::SizeMismatch {
640                what: "a file",
641                expected: slot.size,
642                actual: list.size(),
643            });
644        }
645        slot.held = true;
646        let order = slot.order;
647        self.wanted_lists.remove(&order);
648        self.count_list_bytes(list.encoded_len())?;
649        // The chunks that this list names for the first time are counted in
650        // their order, up to the first that is wrong.
651        let mut first: HashMap<Hash, u32> = HashMap::new();
652        let mut fresh: Vec<(u64, &ChunkRef)> = Vec::new();
653        let mut wrong = None;
654        for (number, item) in (0_u64..).zip(list.items()) {
655            let known = self
656                .chunks
657                .get(&item.hash)
658                .map(|slot| slot.length)
659                .or_else(|| first.get(&item.hash).copied());
660            if let Some(length) = known {
661                if length != item.length {
662                    wrong = Some(Error::SizeMismatch {
663                        what: "a chunk that is listed with two lengths",
664                        expected: u64::from(length),
665                        actual: u64::from(item.length),
666                    });
667                    break;
668                }
669                continue;
670            }
671            if let Err(error) = self.count_chunk(item.length) {
672                wrong = Some(error);
673                break;
674            }
675            first.insert(item.hash, item.length);
676            fresh.push((number, item));
677        }
678        // Whether the store holds each of them is asked on several threads
679        // at once: a store on disk looks at a file for each, and a list can
680        // name a great many. Only the chunks before the first that is wrong
681        // are asked about, and the answers are taken in their order, so the
682        // error is that of the first chunk that is wrong, as it would be if
683        // each were asked about in turn.
684        let held = self.held_of(&fresh);
685        for ((number, item), held) in fresh.into_iter().zip(held) {
686            let held = held?;
687            let wanted_at = (!held).then_some((order, number));
688            if let Some(at) = wanted_at {
689                self.wanted_chunks.insert(at, item.hash);
690            }
691            self.chunks.insert(
692                item.hash,
693                ChunkSlot {
694                    length: item.length,
695                    wanted_at,
696                },
697            );
698        }
699        if let Some(error) = wrong {
700            return Err(error);
701        }
702        if self.mode.rechunk && chunking == Chunking::FastCdcV1 {
703            self.to_rechunk.push(*list.hash());
704        }
705        Ok(())
706    }
707
708    /// Hashes again every chunk of this tree that the store holds, several
709    /// at once. A chunk whose bytes are not what its hash says is damaged.
710    fn rehash_held(&mut self, workers: usize) -> Result<()> {
711        let mut held: Vec<ChunkRef> = self
712            .chunks
713            .iter()
714            .filter(|(_, slot)| slot.wanted_at.is_none())
715            .map(|(hash, slot)| ChunkRef {
716                hash: *hash,
717                length: slot.length,
718            })
719            .collect();
720        held.sort_unstable_by_key(|item| item.hash);
721        let store = self.store;
722        let next = AtomicUsize::new(0);
723        // Gives the places, in `held`, of the chunks that are damaged.
724        let work = || -> Result<Vec<usize>> {
725            let mut spoiled = Vec::new();
726            loop {
727                let index = next.fetch_add(1, Ordering::Relaxed);
728                let Some(item) = held.get(index) else {
729                    return Ok(spoiled);
730                };
731                let mut sound = false;
732                let found = lent(store, Stored::Chunk, &item.hash, &mut |bytes| {
733                    sound = item.matches(bytes);
734                    Ok(())
735                })
736                .and_then(|held| {
737                    if held {
738                        Ok(())
739                    } else {
740                        Err(missing("the chunk", &item.hash))
741                    }
742                });
743                match found {
744                    Ok(()) if sound => {}
745                    Ok(()) => spoiled.push(index),
746                    Err(error) => {
747                        next.store(held.len(), Ordering::Relaxed);
748                        return Err(error);
749                    }
750                }
751            }
752        };
753        let workers = match workers {
754            0 => std::thread::available_parallelism().map_or(1, usize::from),
755            workers => workers,
756        }
757        .min(held.len());
758        let results: Vec<Result<Vec<usize>>> = on_threads(workers, &work);
759        let mut spoiled = Vec::new();
760        for result in results {
761            spoiled.extend(result?);
762        }
763        spoiled.sort_unstable();
764        for &index in &spoiled {
765            self.damaged(Stored::Chunk, &held[index].hash, "a stored chunk")?;
766        }
767        match spoiled.first() {
768            Some(&index) => Err(missing("the chunk", &held[index].hash)),
769            None => Ok(()),
770        }
771    }
772
773    /// Chunks again every file that is held whole, and holds the result
774    /// against the file's list. The chunks were hashed before this.
775    fn rechunk_held(&mut self) -> Result<()> {
776        for file in std::mem::take(&mut self.to_rechunk) {
777            let Some(bytes) = self.store.get(Stored::FileList, &file)? else {
778                continue;
779            };
780            let list = FileList::decode(&bytes)?;
781            let whole = list.items().iter().all(|item| {
782                self.chunks
783                    .get(&item.hash)
784                    .is_some_and(|slot| slot.wanted_at.is_none())
785            });
786            if whole {
787                self.rechunk(&list)?;
788            }
789        }
790        Ok(())
791    }
792
793    /// Chunks a file's bytes again, and holds the result against its list.
794    fn rechunk(&mut self, list: &FileList) -> Result<()> {
795        let store = self.store;
796        let chunker = self.chunker.get_or_insert_with(StreamChunker::new);
797        let mut unread = list.items().iter();
798        let mut current: Option<(Arc<[u8]>, usize)> = None;
799        let mut unchunked = list.items().iter();
800        let mischunked = || invalid("the chunks of a file do not end where its bytes say they end");
801        chunker.cut(
802            Chunking::FastCdcV1,
803            2 * MAX_CHUNK_BYTES,
804            |buffer| loop {
805                if let Some((bytes, at)) = &mut current {
806                    if *at < bytes.len() {
807                        let count = buffer.len().min(bytes.len() - *at);
808                        buffer[..count].copy_from_slice(&bytes[*at..*at + count]);
809                        *at += count;
810                        return Ok(count);
811                    }
812                }
813                match unread.next() {
814                    Some(item) => {
815                        let bytes = store
816                            .get(Stored::Chunk, &item.hash)?
817                            .filter(|bytes| bytes.len() == item.length as usize)
818                            .ok_or_else(|| missing("the chunk", &item.hash))?;
819                        current = Some((bytes, 0));
820                    }
821                    None => return Ok(0),
822                }
823            },
824            |chunks| {
825                for chunk in chunks {
826                    match unchunked.next() {
827                        Some(item) if item.length as usize == chunk.len() => {}
828                        _ => return Err(mischunked()),
829                    }
830                }
831                Ok(())
832            },
833        )?;
834        if unchunked.next().is_some() {
835            return Err(mischunked());
836        }
837        Ok(())
838    }
839
840    /// Takes one frame: a record, a whole list, or a chunk.
841    ///
842    /// A frame is accepted when it is what a checked parent names. A frame
843    /// that is named and held already is accepted and not kept again. Any
844    /// other frame is an error: one that nothing names, one that is
845    /// malformed, and one that does not have the size it was given.
846    pub fn accept(&mut self, frame: &[u8]) -> Result<Accepted> {
847        self.accept_inner(frame, None)
848    }
849
850    /// Takes one frame, which has to be exactly `expected`: the answer to
851    /// what was asked. Anything else is refused, and nothing of it is kept.
852    pub fn accept_expected(&mut self, frame: &[u8], expected: Arrived) -> Result<Accepted> {
853        self.accept_inner(frame, Some(expected))
854    }
855
856    /// Takes chunk frames that come one after another, each as
857    /// [`Intake::accept`] takes it, or as [`Intake::accept_expected`] does
858    /// where it comes with what it has to be, with up to `workers` threads
859    /// hashing and keeping them at once. The error is that of the first frame,
860    /// in their order, that is refused or cannot be kept. A frame after it
861    /// may have been kept, as it would have been had it come first.
862    fn accept_chunks(&mut self, frames: &[(&[u8], Option<Arrived>)], workers: usize) -> Result<()> {
863        if self.failed {
864            return Err(Error::IntakeFailed);
865        }
866        if frames.is_empty() {
867            return Ok(());
868        }
869        self.recorded()?;
870        // As for one chunk: a store that falls over leaves the intake done.
871        self.failed = true;
872        let store = self.store;
873        let slots = Mutex::new(&mut self.chunks);
874        let next = AtomicUsize::new(0);
875        let work = || {
876            let mut settled = Vec::new();
877            loop {
878                let index = next.fetch_add(1, Ordering::Relaxed);
879                let Some(&(frame, expected)) = frames.get(index) else {
880                    return settled;
881                };
882                settled.push((index, take_chunk(store, &slots, frame, expected)));
883            }
884        };
885        let workers = workers.clamp(1, frames.len());
886        let settled: Vec<_> = on_threads(workers, &work).into_iter().flatten().collect();
887        self.failed = false;
888        let mut first: Option<(usize, Error)> = None;
889        for (index, taken) in settled {
890            match taken {
891                Ok((_, Some(at))) => {
892                    self.wanted_chunks.remove(&at);
893                }
894                Ok((_, None)) => {}
895                Err(error) => {
896                    if first.as_ref().is_none_or(|(before, _)| index < *before) {
897                        first = Some((index, error));
898                    }
899                }
900            }
901        }
902        first.map_or(Ok(()), |(_, error)| Err(error))
903    }
904
905    /// Runs a step that changes what the intake knows of its tree. If the
906    /// step fails, the intake knows half of something, and is done.
907    fn taking(&mut self, step: impl FnOnce(&mut Self) -> Result<()>) -> Result<()> {
908        let done = step(self);
909        self.failed |= done.is_err();
910        done
911    }
912
913    fn accept_inner(&mut self, frame: &[u8], expected: Option<Arrived>) -> Result<Accepted> {
914        if self.failed {
915            return Err(Error::IntakeFailed);
916        }
917        let (&tag, body) = frame
918            .split_first()
919            .ok_or_else(|| invalid("a frame is empty"))?;
920        let as_asked = |arrived: Arrived, what: &'static str| match expected {
921            Some(expected) if expected != arrived => Err(Error::NotWanted { what }),
922            _ => Ok(()),
923        };
924        match tag {
925            FRAME_RECORD => {
926                let what = Arrived::Record;
927                as_asked(what, "a record")?;
928                if Root::of_record(frame) != self.root {
929                    return Err(Error::HashMismatch { what: "a record" });
930                }
931                if self.record.is_some() {
932                    return Ok(Accepted { what, kept: false });
933                }
934                let record = Record::decode(frame)?;
935                self.store.put(Stored::Record, self.root.as_hash(), frame)?;
936                self.taking(|intake| intake.begin(record))?;
937                Ok(Accepted { what, kept: true })
938            }
939            FRAME_FOLDER_LIST => {
940                self.recorded()?;
941                let list = FolderList::decode(body)?;
942                let what = Arrived::FolderList(*list.hash());
943                as_asked(what, "a folder's list")?;
944                match self.folders.get(list.hash()) {
945                    None => Err(Error::NotWanted {
946                        what: "a folder's list",
947                    }),
948                    Some(slot) if slot.held => Ok(Accepted { what, kept: false }),
949                    Some(slot) if slot.size != list.size() => Err(Error::SizeMismatch {
950                        what: "a folder",
951                        expected: slot.size,
952                        actual: list.size(),
953                    }),
954                    Some(_) => {
955                        // The list is kept only once all it says has passed.
956                        self.taking(|intake| {
957                            intake.admit_folder(&list)?;
958                            intake.store.put(Stored::FolderList, list.hash(), body)?;
959                            intake.drain()
960                        })?;
961                        Ok(Accepted { what, kept: true })
962                    }
963                }
964            }
965            FRAME_FILE_LIST => {
966                self.recorded()?;
967                let list = FileList::decode(body)?;
968                let what = Arrived::FileList(*list.hash());
969                as_asked(what, "a file's list")?;
970                match self.files.get(list.hash()) {
971                    None => Err(Error::NotWanted {
972                        what: "a file's list",
973                    }),
974                    Some(slot) if slot.held => Ok(Accepted { what, kept: false }),
975                    Some(slot) if slot.size != list.size() => Err(Error::SizeMismatch {
976                        what: "a file",
977                        expected: slot.size,
978                        actual: list.size(),
979                    }),
980                    Some(_) => {
981                        // The list is kept only once all it says has passed.
982                        self.taking(|intake| {
983                            intake.admit_file(&list)?;
984                            intake.store.put(Stored::FileList, list.hash(), body)
985                        })?;
986                        Ok(Accepted { what, kept: true })
987                    }
988                }
989            }
990            FRAME_CHUNK => {
991                self.recorded()?;
992                // Until the chunk is settled the intake counts as failed: a
993                // store that falls over while it keeps the chunk leaves the
994                // intake done, never holding a chunk as kept that is not.
995                self.failed = true;
996                let taken = take_chunk(self.store, &Mutex::new(&mut self.chunks), frame, expected);
997                self.failed = false;
998                let (hash, kept) = taken?;
999                if let Some(at) = kept {
1000                    self.wanted_chunks.remove(&at);
1001                }
1002                Ok(Accepted {
1003                    what: Arrived::Chunk(hash),
1004                    kept: kept.is_some(),
1005                })
1006            }
1007            _ => Err(invalid("a frame that no tree is taken in by")),
1008        }
1009    }
1010
1011    /// What to ask a peer for next: at most `limit` requests. The record
1012    /// comes first, then lists, then chunks by their file and their numbers.
1013    /// Nothing is asked for twice while it is still wanted, so the caller
1014    /// asks again only after the answers have come, or have failed to.
1015    pub fn requests(&self, limit: usize) -> Vec<Request> {
1016        if self.failed {
1017            return Vec::new();
1018        }
1019        if self.record.is_none() {
1020            return vec![Request::Record(self.root)];
1021        }
1022        let mut requests: Vec<Request> = self
1023            .wanted_lists
1024            .values()
1025            .take(limit)
1026            .map(|target| match target.kind {
1027                Kind::Folder => Request::Folder(target.hash),
1028                Kind::File => Request::File(target.hash),
1029            })
1030            .collect();
1031        let mut span: Option<(u64, u64, u32)> = None;
1032        for &(order, number) in self.wanted_chunks.keys() {
1033            if let Some((span_order, start, count)) = &mut span {
1034                if *span_order == order
1035                    && *start + u64::from(*count) == number
1036                    && *count < CHUNKS_PER_REQUEST
1037                {
1038                    *count += 1;
1039                    continue;
1040                }
1041            }
1042            if let Some(done) = span.take() {
1043                self.push_chunks(&mut requests, done);
1044            }
1045            if requests.len() >= limit {
1046                break;
1047            }
1048            span = Some((order, number, 1));
1049        }
1050        if let Some(done) = span {
1051            if requests.len() < limit {
1052                self.push_chunks(&mut requests, done);
1053            }
1054        }
1055        requests
1056    }
1057
1058    fn push_chunks(&self, requests: &mut Vec<Request>, (order, start, count): (u64, u64, u32)) {
1059        if let Some(file) = self.file_by_order.get(&order) {
1060            requests.push(Request::Chunks {
1061                file: *file,
1062                start,
1063                count,
1064            });
1065        }
1066    }
1067
1068    /// What the answer to one of this intake's requests has to be: the
1069    /// frames, in order. A peer may send fewer chunks than were asked for,
1070    /// and never anything else.
1071    pub fn expected(&self, request: &Request) -> Vec<Arrived> {
1072        match request {
1073            Request::Record(_) => vec![Arrived::Record],
1074            Request::Folder(folder) => vec![Arrived::FolderList(*folder)],
1075            Request::File(file) => vec![Arrived::FileList(*file)],
1076            Request::Chunks { file, start, count } => {
1077                let Some(order) = self.files.get(file).map(|slot| slot.order) else {
1078                    return Vec::new();
1079                };
1080                (*start..start.saturating_add(u64::from(*count)))
1081                    .map_while(|number| self.wanted_chunks.get(&(order, number)))
1082                    .map(|hash| Arrived::Chunk(*hash))
1083                    .collect()
1084            }
1085            _ => Vec::new(),
1086        }
1087    }
1088
1089    /// No path from the top may pass through more folders than the format
1090    /// allows. A folder that sits at several places is measured once.
1091    fn check_depth(&self, top: &Target) -> Result<()> {
1092        if top.kind != Kind::Folder {
1093            return Ok(());
1094        }
1095        let too_deep = || Error::TooDeep {
1096            limit: MAX_FOLDER_DEPTH,
1097        };
1098        // How many folders the longest path down from a folder passes
1099        // through, that folder counted.
1100        let mut heights: HashMap<Hash, usize> = HashMap::new();
1101        let mut path: Vec<(Hash, usize)> = vec![(top.hash, 0)];
1102        while let Some(&(folder, next)) = path.last() {
1103            let inside = self
1104                .folders
1105                .get(&folder)
1106                .map_or(&[][..], |slot| slot.inside.as_slice());
1107            if let Some(child) = inside.get(next) {
1108                if let Some(last) = path.last_mut() {
1109                    last.1 += 1;
1110                }
1111                match heights.get(child) {
1112                    Some(height) if path.len() + height > MAX_FOLDER_DEPTH => {
1113                        return Err(too_deep());
1114                    }
1115                    Some(_) => {}
1116                    None if path.len() >= MAX_FOLDER_DEPTH => return Err(too_deep()),
1117                    None => path.push((*child, 0)),
1118                }
1119            } else {
1120                let height = 1 + inside
1121                    .iter()
1122                    .filter_map(|child| heights.get(child))
1123                    .max()
1124                    .copied()
1125                    .unwrap_or(0);
1126                heights.insert(folder, height);
1127                path.pop();
1128            }
1129        }
1130        Ok(())
1131    }
1132
1133    /// Ends the intake. The tree must be whole: the record in, every list
1134    /// and every chunk held, no folder too deep, and the record's totals
1135    /// right.
1136    pub fn finish(self) -> Result<Summary> {
1137        if self.failed {
1138            return Err(Error::IntakeFailed);
1139        }
1140        if let Some(hash) = self.wanted_chunks.values().next() {
1141            if self.record.is_some() && self.wanted_lists.is_empty() {
1142                return Err(missing("the chunk", hash));
1143            }
1144        }
1145        self.finish_lists()
1146    }
1147
1148    /// Ends the intake as [`Intake::finish`] does, without asking that the
1149    /// chunks are held: every list must be there and right, and the totals
1150    /// are counted from the lists.
1151    pub(crate) fn finish_lists(self) -> Result<Summary> {
1152        if self.failed {
1153            return Err(Error::IntakeFailed);
1154        }
1155        let Some(record) = &self.record else {
1156            return Err(missing("the record of", self.root.as_hash()));
1157        };
1158        self.lists_held()?;
1159        self.check_depth(&record.top())?;
1160        let recorded = record.totals();
1161        for (field, recorded, counted) in [
1162            ("chunks", recorded.chunks, self.counted.chunks),
1163            (
1164                "chunk bytes",
1165                recorded.chunk_bytes,
1166                self.counted.chunk_bytes,
1167            ),
1168            ("list bytes", recorded.list_bytes, self.counted.list_bytes),
1169        ] {
1170            if recorded != counted {
1171                return Err(Error::TotalsMismatch {
1172                    field,
1173                    recorded,
1174                    counted,
1175                });
1176            }
1177        }
1178        Ok(Summary {
1179            folders: self.folders.len() as u64,
1180            files: self.files.len() as u64,
1181            record: record.clone(),
1182        })
1183    }
1184}
1185
1186fn lock<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
1187    mutex
1188        .lock()
1189        .unwrap_or_else(|poisoned| poisoned.into_inner())
1190}
1191
1192/// Takes one chunk frame in, on whichever thread: hashes it, finds the slot
1193/// of the chunk in `slots`, and keeps the chunk, with the checks of
1194/// [`Intake::accept`], in its order. Gives the chunk's hash, and where it
1195/// was wanted if it is kept now. A chunk that a slot names is claimed under
1196/// the lock before it is kept, so that two frames of one chunk keep it once.
1197fn take_chunk(
1198    store: &dyn Store,
1199    slots: &Mutex<&mut HashMap<Hash, ChunkSlot>>,
1200    frame: &[u8],
1201    expected: Option<Arrived>,
1202) -> Result<(Hash, Option<(u64, u64)>)> {
1203    let body = match frame.split_first() {
1204        Some((&FRAME_CHUNK, body)) => body,
1205        _ => {
1206            return Err(Error::Invariant {
1207                detail: "a frame taken in as a chunk is not a chunk",
1208            })
1209        }
1210    };
1211    if body.is_empty() || body.len() > MAX_CHUNK_BYTES {
1212        return Err(invalid("a chunk does not hold 1 byte to 8 MiB"));
1213    }
1214    let hash = Hash::of(body);
1215    if expected.is_some_and(|expected| expected != Arrived::Chunk(hash)) {
1216        return Err(Error::NotWanted { what: "a chunk" });
1217    }
1218    let at = {
1219        let mut slots = lock(slots);
1220        let slot = slots
1221            .get_mut(&hash)
1222            .ok_or(Error::NotWanted { what: "a chunk" })?;
1223        let Some(at) = slot.wanted_at else {
1224            return Ok((hash, None));
1225        };
1226        if slot.length as usize != body.len() {
1227            return Err(Error::SizeMismatch {
1228                what: "a chunk",
1229                expected: u64::from(slot.length),
1230                actual: body.len() as u64,
1231            });
1232        }
1233        slot.wanted_at = None;
1234        at
1235    };
1236    match store.put(Stored::Chunk, &hash, body) {
1237        Ok(()) => Ok((hash, Some(at))),
1238        Err(error) => {
1239            // Not kept, so it is wanted still.
1240            if let Some(slot) = lock(slots).get_mut(&hash) {
1241                slot.wanted_at = Some(at);
1242            }
1243            Err(error)
1244        }
1245    }
1246}
1247
1248/// The most bytes of chunk frames that wait to be taken in together. One
1249/// batch is taken in while the next comes. Batches of 16 MiB, about eight
1250/// chunks of the default chunking, are taken in sooner after they come than
1251/// larger ones, and both stay in a processor's cache more often; smaller
1252/// ones leave too few chunks to share among threads.
1253const CHUNK_FRAMES_BYTES: usize = 16 << 20;
1254
1255/// The most chunk frames that wait to be taken in together, however short.
1256const CHUNK_FRAMES_COUNT: usize = 1024;
1257
1258/// The least bytes of chunk frames that are worth a thread of their own.
1259const CHUNK_BYTES_BY_EACH: usize = 1 << 20;
1260
1261/// Chunk frames that come one after another, held to be taken in together,
1262/// so that several threads hash and keep them at once. They are held one
1263/// after another in one stretch of memory, which serves one batch after
1264/// another: memory that is used again costs much less than fresh memory,
1265/// which a system has to find and clear first. It holds room for one batch
1266/// and the frame that ends it, and no more, whatever the lengths of the
1267/// frames of the batches before.
1268pub(crate) struct ChunkFrames {
1269    /// The frames that are held, and after them the frame that was read
1270    /// last, until it is held or taken out.
1271    memory: Vec<u8>,
1272    /// Where each frame that is held ends in `memory`.
1273    ends: Vec<usize>,
1274    expected: Vec<Option<Arrived>>,
1275    cores: usize,
1276}
1277
1278impl ChunkFrames {
1279    pub(crate) fn new() -> Self {
1280        Self {
1281            memory: Vec::new(),
1282            ends: Vec::new(),
1283            expected: Vec::new(),
1284            cores: std::thread::available_parallelism().map_or(1, usize::from),
1285        }
1286    }
1287
1288    /// How many bytes the frames that are held take.
1289    fn held_bytes(&self) -> usize {
1290        self.ends.last().copied().unwrap_or(0)
1291    }
1292
1293    /// Takes room for a whole batch and the frame that ends it, once: memory
1294    /// that grew a step at a time would be moved, and fresh memory taken,
1295    /// at every step. Room that is not used is not touched.
1296    fn make_room(&mut self) {
1297        let batch = CHUNK_FRAMES_BYTES + MAX_CHUNK_BYTES + 1;
1298        if self.memory.capacity() < batch {
1299            self.memory.reserve_exact(batch - self.memory.len());
1300        }
1301    }
1302
1303    /// Reads what comes next on `input`, as `wire::read_next` does: a frame is
1304    /// read after the frames that are held, and is held only once
1305    /// [`ChunkFrames::hold`] is called.
1306    pub(crate) fn read_next(&mut self, input: &mut dyn Read, limit: usize) -> Result<Next> {
1307        self.make_room();
1308        self.memory.truncate(self.held_bytes());
1309        read_next_onto(input, limit, &mut self.memory)
1310    }
1311
1312    /// Whether the frame that was read last is a chunk's.
1313    pub(crate) fn next_is_chunk(&self) -> bool {
1314        self.memory.get(self.held_bytes()) == Some(&FRAME_CHUNK)
1315    }
1316
1317    /// Moves the frame that was read last into `frame`, which is emptied
1318    /// first.
1319    pub(crate) fn take_next(&mut self, frame: &mut Vec<u8>) {
1320        let held = self.held_bytes();
1321        frame.clear();
1322        frame.extend_from_slice(&self.memory[held..]);
1323        self.memory.truncate(held);
1324    }
1325
1326    /// Holds the frame that was read last. It has to be `expected`, when
1327    /// that is given.
1328    pub(crate) fn hold(&mut self, expected: Option<Arrived>) {
1329        self.ends.push(self.memory.len());
1330        self.expected.push(expected);
1331    }
1332
1333    /// Holds a copy of `frame`, which is lent for the call only.
1334    pub(crate) fn hold_copy(&mut self, frame: &[u8], expected: Option<Arrived>) {
1335        self.make_room();
1336        self.memory.truncate(self.held_bytes());
1337        self.memory.extend_from_slice(frame);
1338        self.hold(expected);
1339    }
1340
1341    /// Whether enough frames are held to take them in now.
1342    pub(crate) fn full(&self) -> bool {
1343        self.held_bytes() >= CHUNK_FRAMES_BYTES || self.ends.len() >= CHUNK_FRAMES_COUNT
1344    }
1345
1346    /// Takes the frames that are held into `intake`, and holds none after.
1347    /// With none held, the intake is not asked anything: an intake that
1348    /// failed has given its failure already.
1349    pub(crate) fn take_in(&mut self, intake: &mut Intake<'_>) -> Result<()> {
1350        if self.ends.is_empty() {
1351            return Ok(());
1352        }
1353        let mut start = 0;
1354        let frames: Vec<(&[u8], Option<Arrived>)> = self
1355            .ends
1356            .iter()
1357            .zip(&self.expected)
1358            .map(|(&end, &expected)| {
1359                let frame = &self.memory[start..end];
1360                start = end;
1361                (frame, expected)
1362            })
1363            .collect();
1364        let workers = self.cores.min(self.held_bytes() / CHUNK_BYTES_BY_EACH + 1);
1365        let taken = intake.accept_chunks(&frames, workers);
1366        self.memory.clear();
1367        self.ends.clear();
1368        self.expected.clear();
1369        taken
1370    }
1371
1372    /// How many bytes of memory this holds for frames.
1373    #[cfg(test)]
1374    fn memory_held(&self) -> usize {
1375        self.memory.capacity()
1376    }
1377}
1378
1379/// What a batch of chunk frames that other threads took in gives back.
1380type TakenIn<'a, 's> = (&'a mut Intake<'s>, &'a mut ChunkFrames, Result<()>);
1381
1382/// Where an intake is while chunk frames are taken in.
1383enum Away<'scope, 'a, 's> {
1384    /// Here, with the frames that the next batch will be held in after this
1385    /// one.
1386    Here(&'a mut Intake<'s>, &'a mut ChunkFrames),
1387    /// With other threads, which take in a batch of chunk frames.
1388    Taking(std::thread::ScopedJoinHandle<'scope, TakenIn<'a, 's>>),
1389}
1390
1391/// Chunk frames that are taken in by other threads while more come: one
1392/// batch is held while the one before it is taken in. Anything else that is
1393/// done with the intake waits until every frame before it is in, so the
1394/// frames are taken in in their order, and the error is that of the first
1395/// frame that is refused or cannot be kept.
1396pub(crate) struct TakingIn<'scope, 'env, 'a, 's> {
1397    scope: &'scope std::thread::Scope<'scope, 'env>,
1398    held: &'a mut ChunkFrames,
1399    /// None once a batch has failed: its failure is what was given.
1400    away: Option<Away<'scope, 'a, 's>>,
1401}
1402
1403impl<'scope, 'env, 'a: 'scope, 's: 'scope> TakingIn<'scope, 'env, 'a, 's> {
1404    pub(crate) fn new(
1405        scope: &'scope std::thread::Scope<'scope, 'env>,
1406        intake: &'a mut Intake<'s>,
1407        frames: &'a mut [ChunkFrames; 2],
1408    ) -> Self {
1409        let [held, spare] = frames;
1410        Self {
1411            scope,
1412            held,
1413            away: Some(Away::Here(intake, spare)),
1414        }
1415    }
1416
1417    /// Reads what comes next on `input`, as [`ChunkFrames::read_next`]
1418    /// does.
1419    pub(crate) fn read_next(&mut self, input: &mut dyn Read, limit: usize) -> Result<Next> {
1420        self.held.read_next(input, limit)
1421    }
1422
1423    /// Moves the frame that was read last into `frame`, as
1424    /// [`ChunkFrames::take_next`] does.
1425    pub(crate) fn take_next(&mut self, frame: &mut Vec<u8>) {
1426        self.held.take_next(frame);
1427    }
1428
1429    /// Whether the frame that was read last is a chunk's.
1430    pub(crate) fn next_is_chunk(&self) -> bool {
1431        self.held.next_is_chunk()
1432    }
1433
1434    /// Holds the frame that was read last, as [`ChunkFrames::hold`] does.
1435    pub(crate) fn hold(&mut self, expected: Option<Arrived>) -> Result<()> {
1436        self.held.hold(expected);
1437        self.hand_over_when_full()
1438    }
1439
1440    /// Holds a copy of `frame`, which is lent for the call only.
1441    pub(crate) fn hold_copy(&mut self, frame: &[u8], expected: Option<Arrived>) -> Result<()> {
1442        self.held.hold_copy(frame, expected);
1443        self.hand_over_when_full()
1444    }
1445
1446    /// Once enough frames are held, hands them to other threads to take in,
1447    /// as soon as the batch before them is in.
1448    fn hand_over_when_full(&mut self) -> Result<()> {
1449        if !self.held.full() {
1450            return Ok(());
1451        }
1452        let (intake, spare) = self.back()?;
1453        let full = std::mem::replace(&mut self.held, spare);
1454        let handle = self.scope.spawn(move || {
1455            let taken = full.take_in(intake);
1456            (intake, full, taken)
1457        });
1458        self.away = Some(Away::Taking(handle));
1459        Ok(())
1460    }
1461
1462    /// Waits until the batch that other threads take in is in, and gives the
1463    /// intake and the frames that the next batch is to be held in.
1464    fn back(&mut self) -> Result<(&'a mut Intake<'s>, &'a mut ChunkFrames)> {
1465        match self.away.take() {
1466            Some(Away::Here(intake, spare)) => Ok((intake, spare)),
1467            Some(Away::Taking(handle)) => match handle.join() {
1468                Ok((intake, spare, Ok(()))) => Ok((intake, spare)),
1469                Ok((_, _, Err(error))) => Err(error),
1470                Err(payload) => std::panic::resume_unwind(payload),
1471            },
1472            None => Err(Error::IntakeFailed),
1473        }
1474    }
1475
1476    /// The intake, once every frame held is in.
1477    pub(crate) fn intake(&mut self) -> Result<&mut Intake<'s>> {
1478        let (intake, spare) = self.back()?;
1479        let taken = self.held.take_in(intake);
1480        let away = self.away.insert(Away::Here(intake, spare));
1481        taken?;
1482        match away {
1483            Away::Here(intake, _) => Ok(&mut **intake),
1484            Away::Taking(_) => Err(Error::Invariant {
1485                detail: "an intake that was here is away",
1486            }),
1487        }
1488    }
1489
1490    /// Takes in every frame that is held, and gives the failure of the first
1491    /// that is refused or cannot be kept. A failure that was given already
1492    /// is not given again.
1493    pub(crate) fn finish(mut self) -> Result<()> {
1494        if self.away.is_none() {
1495            return Ok(());
1496        }
1497        self.intake().map(|_| ())
1498    }
1499}
1500
1501/// Checks a whole tree that a store holds: every list, every chunk's bytes,
1502/// the depth of its folders and the totals in its record. It is the same
1503/// set of checks that a tree goes through when it is taken in.
1504pub fn verify(store: &dyn Store, root: &Root) -> Result<Summary> {
1505    verify_with(store, root, VerifyOptions::default())
1506}
1507
1508/// Checks a whole tree that a store holds, with more checks switched on.
1509///
1510/// The lists are checked first. Then every chunk is hashed again, several at
1511/// once, and last, when that is asked for, every file is chunked again.
1512pub fn verify_with(store: &dyn Store, root: &Root, options: VerifyOptions) -> Result<Summary> {
1513    let mode = Mode {
1514        rechunk: options.rechunk,
1515        discard: options.discard,
1516        threads: options.workers,
1517    };
1518    let mut intake = Intake::with_mode(store, *root, mode)?;
1519    intake.rehash_held(options.workers)?;
1520    intake.rechunk_held()?;
1521    intake.finish()
1522}
1523
1524#[cfg(test)]
1525mod tests {
1526    use super::*;
1527    use crate::store::MemoryStore;
1528
1529    #[test]
1530    fn chunk_frames_take_no_more_memory_than_one_batch_needs() {
1531        // In each batch a long frame comes after short ones, at another place
1532        // each time. Memory that each place kept for the longest frame it
1533        // held would come to all of them: 128 MiB.
1534        let store = MemoryStore::new();
1535        let mut intake = Intake::new(&store, Root::of_record(b"no such tree")).unwrap();
1536        let long = vec![FRAME_CHUNK; (1 << 20) + 1];
1537        let short = [FRAME_CHUNK, 1];
1538        let places = 128;
1539        // Room for a batch and the frame that ends it.
1540        let most = CHUNK_FRAMES_BYTES + MAX_CHUNK_BYTES + 1;
1541        assert!(places * (1 << 20) > most);
1542        // Held as a fetch holds them.
1543        let mut frames = ChunkFrames::new();
1544        for place in 0..places {
1545            for _ in 0..place {
1546                frames.hold_copy(&short, None);
1547            }
1548            frames.hold_copy(&long, None);
1549            // The intake has no record and takes no chunk, and the batch is
1550            // let go all the same.
1551            assert!(frames.take_in(&mut intake).is_err());
1552        }
1553        assert!(
1554            frames.memory_held() <= most,
1555            "{} bytes",
1556            frames.memory_held()
1557        );
1558        // Read as an import reads them.
1559        let mut frames = ChunkFrames::new();
1560        for place in 0..places {
1561            let mut stream = Vec::new();
1562            for frame in std::iter::repeat_n(&short[..], place).chain([&long[..]]) {
1563                stream.extend_from_slice(&(frame.len() as u32).to_be_bytes());
1564                stream.extend_from_slice(frame);
1565            }
1566            let mut input = stream.as_slice();
1567            while let Next::Frame = frames.read_next(&mut input, long.len()).unwrap() {
1568                assert!(frames.next_is_chunk());
1569                frames.hold(None);
1570            }
1571            assert_eq!(frames.ends.len(), place + 1);
1572            assert!(frames.take_in(&mut intake).is_err());
1573        }
1574        assert!(
1575            frames.memory_held() <= most,
1576            "{} bytes",
1577            frames.memory_held()
1578        );
1579    }
1580}