1use 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
36const CHUNKS_PER_REQUEST: u32 = 64;
38
39const LOOKS_BY_EACH: usize = 64;
43
44fn invalid(detail: &str) -> Error {
45 Error::InvalidData {
46 detail: detail.to_owned(),
47 }
48}
49
50#[derive(Clone, Copy, Debug, Eq, PartialEq)]
52pub enum Arrived {
53 Record,
54 FolderList(Hash),
55 FileList(Hash),
56 Chunk(Hash),
57}
58
59#[derive(Clone, Copy, Debug, Eq, PartialEq)]
61pub struct Accepted {
62 pub what: Arrived,
63 pub kept: bool,
65}
66
67#[derive(Clone, Debug, Eq, PartialEq)]
69pub struct Summary {
70 pub record: Record,
71 pub folders: u64,
73 pub files: u64,
75}
76
77#[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 pub fn rechunk(mut self, on: bool) -> Self {
94 self.rechunk = on;
95 self
96 }
97
98 pub fn discard_damaged(mut self, on: bool) -> Self {
104 self.discard = on;
105 self
106 }
107
108 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 rechunk: bool,
120 discard: bool,
122 threads: usize,
125}
126
127struct FolderSlot {
128 size: u64,
129 order: u64,
130 held: bool,
131 inside: Vec<Hash>,
133}
134
135struct FileSlot {
136 size: u64,
137 order: u64,
138 held: bool,
139}
140
141struct ChunkSlot {
142 length: u32,
143 wanted_at: Option<(u64, u64)>,
146}
147
148pub struct Intake<'s> {
164 store: &'s dyn Store,
165 root: Root,
166 mode: Mode,
167 record: Option<Record>,
168 measuring: Option<Chunking>,
170 folders: HashMap<Hash, FolderSlot>,
171 files: HashMap<Hash, FileSlot>,
172 chunks: HashMap<Hash, ChunkSlot>,
173 wanted_lists: BTreeMap<u64, Target>,
175 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 to_rechunk: Vec<Hash>,
183 chunker: Option<StreamChunker>,
184 failed: bool,
186}
187
188impl<'s> Intake<'s> {
189 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 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 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 pub fn record(&self) -> Option<&Record> {
268 self.record.as_ref()
269 }
270
271 pub fn outstanding(&self) -> usize {
274 usize::from(self.record.is_none()) + self.wanted_lists.len() + self.wanted_chunks.len()
275 }
276
277 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 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 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 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 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 fn chunking(&self) -> Result<Chunking> {
356 match self.measuring {
357 Some(chunking) => Ok(chunking),
358 None => Ok(self.recorded()?.chunking()),
359 }
360 }
361
362 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 pub fn accept(&mut self, frame: &[u8]) -> Result<Accepted> {
847 self.accept_inner(frame, None)
848 }
849
850 pub fn accept_expected(&mut self, frame: &[u8], expected: Arrived) -> Result<Accepted> {
853 self.accept_inner(frame, Some(expected))
854 }
855
856 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 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 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 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 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 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 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 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 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 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 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 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
1192fn 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 if let Some(slot) = lock(slots).get_mut(&hash) {
1241 slot.wanted_at = Some(at);
1242 }
1243 Err(error)
1244 }
1245 }
1246}
1247
1248const CHUNK_FRAMES_BYTES: usize = 16 << 20;
1254
1255const CHUNK_FRAMES_COUNT: usize = 1024;
1257
1258const CHUNK_BYTES_BY_EACH: usize = 1 << 20;
1260
1261pub(crate) struct ChunkFrames {
1269 memory: Vec<u8>,
1272 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 fn held_bytes(&self) -> usize {
1290 self.ends.last().copied().unwrap_or(0)
1291 }
1292
1293 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 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 pub(crate) fn next_is_chunk(&self) -> bool {
1314 self.memory.get(self.held_bytes()) == Some(&FRAME_CHUNK)
1315 }
1316
1317 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 pub(crate) fn hold(&mut self, expected: Option<Arrived>) {
1329 self.ends.push(self.memory.len());
1330 self.expected.push(expected);
1331 }
1332
1333 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 pub(crate) fn full(&self) -> bool {
1343 self.held_bytes() >= CHUNK_FRAMES_BYTES || self.ends.len() >= CHUNK_FRAMES_COUNT
1344 }
1345
1346 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 #[cfg(test)]
1374 fn memory_held(&self) -> usize {
1375 self.memory.capacity()
1376 }
1377}
1378
1379type TakenIn<'a, 's> = (&'a mut Intake<'s>, &'a mut ChunkFrames, Result<()>);
1381
1382enum Away<'scope, 'a, 's> {
1384 Here(&'a mut Intake<'s>, &'a mut ChunkFrames),
1387 Taking(std::thread::ScopedJoinHandle<'scope, TakenIn<'a, 's>>),
1389}
1390
1391pub(crate) struct TakingIn<'scope, 'env, 'a, 's> {
1397 scope: &'scope std::thread::Scope<'scope, 'env>,
1398 held: &'a mut ChunkFrames,
1399 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 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 pub(crate) fn take_next(&mut self, frame: &mut Vec<u8>) {
1426 self.held.take_next(frame);
1427 }
1428
1429 pub(crate) fn next_is_chunk(&self) -> bool {
1431 self.held.next_is_chunk()
1432 }
1433
1434 pub(crate) fn hold(&mut self, expected: Option<Arrived>) -> Result<()> {
1436 self.held.hold(expected);
1437 self.hand_over_when_full()
1438 }
1439
1440 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 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 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 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 pub(crate) fn finish(mut self) -> Result<()> {
1494 if self.away.is_none() {
1495 return Ok(());
1496 }
1497 self.intake().map(|_| ())
1498 }
1499}
1500
1501pub fn verify(store: &dyn Store, root: &Root) -> Result<Summary> {
1505 verify_with(store, root, VerifyOptions::default())
1506}
1507
1508pub 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 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 let most = CHUNK_FRAMES_BYTES + MAX_CHUNK_BYTES + 1;
1541 assert!(places * (1 << 20) > most);
1542 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 assert!(frames.take_in(&mut intake).is_err());
1552 }
1553 assert!(
1554 frames.memory_held() <= most,
1555 "{} bytes",
1556 frames.memory_held()
1557 );
1558 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}