1use crate::disk::{Found, Held, Refused};
4use crate::fastcdc::{chunks_of, FASTCDC_MAX_SIZE};
5use crate::format::{
6 check_name, ChunkRef, Chunking, Entry, ExtraData, FileList, FolderList, Kind, Record, Target,
7 MAX_FOLDER_DEPTH, TIMESTAMP_KEY,
8};
9use crate::hash::Root;
10use crate::intake::Intake;
11use crate::store::{Store, Stored};
12use crate::threads::{cores, with_helpers};
13use crate::{io_error, Error, Result};
14use std::collections::VecDeque;
15use std::fs::{self, File};
16use std::io::{self, ErrorKind, Read};
17use std::path::{Path, PathBuf};
18use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
19use std::sync::{Arc, Condvar, Mutex, MutexGuard};
20use std::time::{SystemTime, UNIX_EPOCH};
21
22pub(crate) fn read_some(reader: &mut dyn Read, buffer: &mut [u8]) -> io::Result<usize> {
24 loop {
25 match reader.read(buffer) {
26 Err(error) if error.kind() == ErrorKind::Interrupted => {}
27 other => return other,
28 }
29 }
30}
31
32const ROOM_ALONE: usize = 2 * FASTCDC_MAX_SIZE;
35
36const ROOM_WITH_HELP: usize = 8 * FASTCDC_MAX_SIZE;
39
40const LOOKED_THROUGH_BY_EACH: usize = 4 << 20;
43
44const KEPT_BY_EACH: usize = 1 << 20;
47
48const FIXED_CHUNKS_IN_A_WINDOW: usize = 1024;
50
51const WINDOWS_BEHIND_TO_GROW: usize = 3;
57
58const WINDOW_START: usize = 64 * 1024;
61
62pub(crate) struct Helpers {
73 free: AtomicUsize,
74}
75
76impl Helpers {
77 fn new(free: usize) -> Arc<Self> {
78 Arc::new(Self {
79 free: AtomicUsize::new(free),
80 })
81 }
82
83 fn for_threads(threads: usize) -> Arc<Self> {
86 let threads = match threads {
87 0 => cores(),
88 threads => threads,
89 };
90 Self::new(threads - 1)
91 }
92
93 fn free(&self) -> usize {
95 self.free.load(Ordering::Relaxed)
96 }
97
98 fn any(&self) -> bool {
99 self.free() > 0
100 }
101
102 fn take(&self, most: usize) -> usize {
104 let mut free = self.free.load(Ordering::Relaxed);
105 loop {
106 let taken = free.min(most);
107 if taken == 0 {
108 return 0;
109 }
110 match self.free.compare_exchange_weak(
111 free,
112 free - taken,
113 Ordering::Relaxed,
114 Ordering::Relaxed,
115 ) {
116 Ok(_) => return taken,
117 Err(now) => free = now,
118 }
119 }
120 }
121
122 fn give(&self, count: usize) {
123 self.free.fetch_add(count, Ordering::Relaxed);
124 }
125}
126
127pub struct Builder<'s> {
133 store: &'s dyn Store,
134 chunking: Chunking,
135 windows: Windows,
136 helpers: Arc<Helpers>,
137}
138
139impl<'s> Builder<'s> {
140 pub fn new(store: &'s dyn Store, chunking: Chunking) -> Self {
142 Self::sharing(store, chunking, Helpers::for_threads(0))
143 }
144
145 fn sharing(store: &'s dyn Store, chunking: Chunking, helpers: Arc<Helpers>) -> Self {
146 Self {
147 store,
148 chunking,
149 windows: Windows::default(),
150 helpers,
151 }
152 }
153
154 pub fn threads(mut self, threads: usize) -> Self {
161 self.helpers = Helpers::for_threads(threads);
162 self
163 }
164
165 pub fn chunking(&self) -> Chunking {
167 self.chunking
168 }
169
170 pub fn file(&mut self, reader: &mut dyn Read) -> Result<Target> {
174 self.file_from(|buffer| {
175 read_some(reader, buffer).map_err(|source| Error::Stream {
176 operation: "read a file's bytes",
177 source,
178 })
179 })
180 }
181
182 pub fn file_from_bytes(&mut self, bytes: &[u8]) -> Result<Target> {
185 let chunks = settled(self.chunking, &self.helpers, bytes, true);
186 let mut items = Vec::with_capacity(chunks.len());
187 keep_chunks(self.store, &self.helpers, &chunks, &mut items)?;
188 self.keep_list(items)
189 }
190
191 pub fn file_at(&mut self, path: &Path) -> Result<Target> {
193 let mut file = File::open(path).map_err(|error| io_error("open", path, error))?;
194 self.file_from(|buffer| {
195 read_some(&mut file, buffer).map_err(|error| io_error("read", path, error))
196 })
197 }
198
199 fn file_from(&mut self, mut read: impl FnMut(&mut [u8]) -> Result<usize>) -> Result<Target> {
210 let store = self.store;
211 let chunking = self.chunking;
212 let helpers = &*self.helpers;
213 let mut room = window_room(chunking, helpers.any());
214 let mut behind_in_a_row = 0;
215 let Windows { current, next } = &mut self.windows;
216 let mut items = Vec::new();
217 let (mut filled, mut ended) = fill(current, 0, room, &mut read)?;
218 while filled > 0 {
219 let chunks = settled(chunking, helpers, ¤t[..filled], ended);
220 if chunks.is_empty() {
221 return Err(Error::Invariant {
222 detail: "a full window settled no chunk",
223 });
224 }
225 let settled_to: usize = chunks.iter().map(|chunk| chunk.len()).sum();
226 let tail = ¤t[settled_to..filled];
227 let most = if ended {
231 chunks.len() / 2
232 } else {
233 settled_to.div_ceil(KEPT_BY_EACH).min(chunks.len())
234 };
235 let (kept, refilled) =
236 keep_chunks_while(store, helpers, most, &chunks, &mut items, |behind| {
237 carry(tail, next, room)?;
238 if ended {
239 return Ok((tail.len(), true));
240 }
241 let refilled = fill(next, tail.len(), room, &mut read);
242 if behind() && helpers.free() >= most {
243 behind_in_a_row += 1;
244 if behind_in_a_row >= WINDOWS_BEHIND_TO_GROW {
245 room = window_room(chunking, true);
246 }
247 } else {
248 behind_in_a_row = 0;
249 }
250 refilled
251 });
252 kept?;
253 (filled, ended) = refilled?;
254 std::mem::swap(current, next);
255 }
256 self.keep_list(items)
257 }
258
259 fn keep_list(&self, items: Vec<ChunkRef>) -> Result<Target> {
262 let list = FileList::new(items)?;
263 if !self.store.has(Stored::FileList, list.hash())? {
264 self.store
265 .put(Stored::FileList, list.hash(), &list.encode())?;
266 }
267 Ok(list.target())
268 }
269
270 pub fn folder(&mut self, mut entries: Vec<Entry>) -> Result<Target> {
273 entries.sort_by(|left, right| left.name().as_bytes().cmp(right.name().as_bytes()));
274 let list = FolderList::new(entries)?;
275 if !self.store.has(Stored::FolderList, list.hash())? {
276 self.store
277 .put(Stored::FolderList, list.hash(), &list.encode())?;
278 }
279 Ok(list.target())
280 }
281
282 pub fn finish(self, top: Target, extra: ExtraData) -> Result<Root> {
290 let helping = self.helpers.take(usize::MAX);
293 let totals = Intake::measure(self.store, top, self.chunking, helping + 1);
294 self.helpers.give(helping);
295 let record = Record::new(top, totals?, self.chunking, extra)?;
296 let bytes = record.encode();
297 let root = Root::of_record(&bytes);
298 self.store.put(Stored::Record, root.as_hash(), &bytes)?;
299 Ok(root)
300 }
301}
302
303fn keep_chunk(store: &dyn Store, chunk: &[u8]) -> Result<ChunkRef> {
306 let item = ChunkRef::of(chunk)?;
307 if !store.has(Stored::Chunk, &item.hash)? {
308 store.put(Stored::Chunk, &item.hash, chunk)?;
309 }
310 Ok(item)
311}
312
313fn keep_chunks(
316 store: &dyn Store,
317 helpers: &Helpers,
318 chunks: &[&[u8]],
319 items: &mut Vec<ChunkRef>,
320) -> Result<()> {
321 keep_chunks_while(store, helpers, chunks.len() / 2, chunks, items, |_| ()).0
323}
324
325fn keep_chunks_while<T>(
330 store: &dyn Store,
331 helpers: &Helpers,
332 most: usize,
333 chunks: &[&[u8]],
334 items: &mut Vec<ChunkRef>,
335 meanwhile: impl FnOnce(&dyn Fn() -> bool) -> T,
336) -> (Result<()>, T) {
337 let helping = helpers.take(most);
338 let next = AtomicUsize::new(0);
339 let finished = AtomicUsize::new(0);
340 let work = || {
341 let mut kept = Vec::new();
342 loop {
343 let index = next.fetch_add(1, Ordering::Relaxed);
344 let Some(chunk) = chunks.get(index) else {
345 return kept;
346 };
347 let item = keep_chunk(store, chunk);
348 if item.is_err() {
349 next.store(chunks.len(), Ordering::Relaxed);
350 }
351 kept.push((index, item));
352 finished.fetch_add(1, Ordering::Relaxed);
353 }
354 };
355 let behind = || helping > 0 && finished.load(Ordering::Relaxed) < chunks.len();
358 let (kept, done) = with_helpers(helping, &work, || meanwhile(&behind));
359 let kept: Vec<_> = kept.into_iter().flatten().collect();
360 helpers.give(helping);
361 (in_order(kept, chunks.len(), items), done)
362}
363
364fn in_order(
367 kept: Vec<(usize, Result<ChunkRef>)>,
368 count: usize,
369 items: &mut Vec<ChunkRef>,
370) -> Result<()> {
371 let mut found: Vec<Option<ChunkRef>> = vec![None; count];
372 for (index, item) in kept {
373 found[index] = Some(item?);
374 }
375 for item in found {
376 items.push(item.ok_or(Error::Invariant {
377 detail: "a chunk was left out of a file",
378 })?);
379 }
380 Ok(())
381}
382
383#[derive(Default)]
386struct Windows {
387 current: Vec<u8>,
388 next: Vec<u8>,
389}
390
391fn window_room(chunking: Chunking, help: bool) -> usize {
394 let room = if help { ROOM_WITH_HELP } else { ROOM_ALONE };
395 match chunking {
396 Chunking::FastCdcV1 => (room / 2).max(FASTCDC_MAX_SIZE),
397 Chunking::Fixed(size) => {
398 let size = size.get() as usize;
399 let most = size.saturating_mul(FIXED_CHUNKS_IN_A_WINDOW);
400 (room / 2).min(most).max(size)
401 }
402 }
403}
404
405fn settled<'d>(
409 chunking: Chunking,
410 helpers: &Helpers,
411 data: &'d [u8],
412 ended: bool,
413) -> Vec<&'d [u8]> {
414 match chunking {
415 Chunking::FastCdcV1 => {
416 let wanted = (data.len() / LOOKED_THROUGH_BY_EACH).saturating_sub(1);
417 let helping = helpers.take(wanted);
418 let chunks = chunks_of(data, ended, helping + 1);
419 helpers.give(helping);
420 chunks
421 }
422 Chunking::Fixed(size) => {
423 let size = size.get() as usize;
424 let mut chunks: Vec<&[u8]> = data.chunks(size).collect();
425 if !ended && chunks.last().is_some_and(|last| last.len() < size) {
426 chunks.pop();
427 }
428 chunks
429 }
430 }
431}
432
433fn grow(window: &mut Vec<u8>, least: usize, room: usize) -> Result<()> {
436 let length = (window.len() * 2).max(WINDOW_START).min(room).max(least);
437 let more = length.saturating_sub(window.len());
438 window
439 .try_reserve_exact(more)
440 .map_err(|_| Error::AllocationFailed {
441 resource: "the chunking window",
442 requested: length as u64,
443 })?;
444 window.resize(length, 0);
445 Ok(())
446}
447
448fn fill(
452 window: &mut Vec<u8>,
453 mut filled: usize,
454 room: usize,
455 read: &mut dyn FnMut(&mut [u8]) -> Result<usize>,
456) -> Result<(usize, bool)> {
457 while filled < room {
458 if filled == window.len() {
459 grow(window, filled + 1, room)?;
460 }
461 let end = window.len().min(room);
462 let count = read(&mut window[filled..end])?;
463 if count > end - filled {
464 return Err(Error::Invariant {
465 detail: "a reader gave more bytes than it was asked for",
466 });
467 }
468 if count == 0 {
469 return Ok((filled, true));
470 }
471 filled += count;
472 }
473 Ok((filled, false))
474}
475
476fn carry(tail: &[u8], window: &mut Vec<u8>, room: usize) -> Result<()> {
478 if window.len() < tail.len() {
479 grow(window, tail.len(), room)?;
480 }
481 window[..tail.len()].copy_from_slice(tail);
482 Ok(())
483}
484
485#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
489pub enum Links {
490 #[default]
492 Refuse,
493 Skip,
495}
496
497#[derive(Clone, Debug, Default)]
499pub struct BuildOptions {
500 chunking: Option<Chunking>,
501 extra: ExtraData,
502 timestamp: bool,
503 workers: usize,
504 links: Links,
505}
506
507impl BuildOptions {
508 pub fn new() -> Self {
509 Self::default()
510 }
511
512 pub fn chunking(mut self, chunking: Chunking) -> Self {
515 self.chunking = Some(chunking);
516 self
517 }
518
519 pub fn extra(mut self, extra: ExtraData) -> Self {
521 self.extra = extra;
522 self
523 }
524
525 pub fn timestamp(mut self, on: bool) -> Self {
528 self.timestamp = on;
529 self
530 }
531
532 pub fn workers(mut self, workers: usize) -> Self {
536 self.workers = workers;
537 self
538 }
539
540 pub fn links(mut self, links: Links) -> Self {
541 self.links = links;
542 self
543 }
544}
545
546pub type EntryExtra<'a> = dyn Fn(&Path, &str, Kind) -> Result<ExtraData> + Sync + 'a;
549
550pub fn build(store: &dyn Store, path: impl AsRef<Path>, options: &BuildOptions) -> Result<Root> {
557 build_tree(store, path.as_ref(), options, None)
558}
559
560pub fn build_with(
563 store: &dyn Store,
564 path: impl AsRef<Path>,
565 options: &BuildOptions,
566 entry_extra: &EntryExtra<'_>,
567) -> Result<Root> {
568 build_tree(store, path.as_ref(), options, Some(entry_extra))
569}
570
571fn build_tree(
572 store: &dyn Store,
573 path: &Path,
574 options: &BuildOptions,
575 entry_extra: Option<&EntryExtra<'_>>,
576) -> Result<Root> {
577 let chunking = options.chunking.unwrap_or(Chunking::FastCdcV1);
578 let mut extra = options.extra.clone();
579 if options.timestamp {
580 extra.insert(TIMESTAMP_KEY, timestamp(SystemTime::now())?)?;
581 }
582 let metadata = fs::metadata(path).map_err(|error| io_error("look at", path, error))?;
583 let mut builder = Builder::new(store, chunking).threads(options.workers);
584 if !metadata.is_dir() {
585 let top = builder.file_at(path)?;
586 return builder.finish(top, extra);
587 }
588
589 let top = Held::open(path).map_err(|error| io_error("open", path, error))?;
592 let (folders, file_targets) =
593 walk_and_chunk(store, chunking, &top, options.links, options.workers)?;
594 let mut folder_targets: Vec<Option<Target>> = vec![None; folders.len()];
597 for index in (0..folders.len()).rev() {
598 let mut entries = Vec::with_capacity(folders[index].children.len());
599 for child in &folders[index].children {
600 let target = match child.kind {
601 Kind::File => *file_targets.get(child.index).ok_or(Error::Invariant {
602 detail: "a file was left out of the build",
603 })?,
604 Kind::Folder => folder_targets[child.index].ok_or(Error::Invariant {
605 detail: "a folder was made before a folder inside it",
606 })?,
607 };
608 let extra = match entry_extra {
609 Some(entry_extra) => match child.kind {
613 Kind::File => entry_extra(
614 &folders[index].path.join(&child.name),
615 &child.name,
616 child.kind,
617 )?,
618 Kind::Folder => {
619 entry_extra(&folders[child.index].path, &child.name, child.kind)?
620 }
621 },
622 None => ExtraData::new(),
623 };
624 entries.push(Entry::new(child.name.as_str(), target, extra)?);
625 }
626 folder_targets[index] = Some(builder.folder(entries)?);
627 }
628 let top = folder_targets[0].ok_or(Error::Invariant {
629 detail: "the top folder was not made",
630 })?;
631 builder.finish(top, extra)
632}
633
634struct Folder {
635 path: PathBuf,
636 children: Vec<Child>,
637}
638
639struct Child {
640 name: String,
641 kind: Kind,
642 index: usize,
644}
645
646type OnTheWay = (Arc<Held>, Vec<(String, usize)>);
650
651const FOLDERS_AHEAD: usize = 16;
655
656struct Batch {
659 folder: Arc<Held>,
660 files: Vec<(usize, String)>,
662 taken: AtomicUsize,
664}
665
666impl Batch {
667 fn take(&self) -> Option<&(usize, String)> {
670 self.files.get(self.taken.fetch_add(1, Ordering::Relaxed))
671 }
672
673 fn all_taken(&self) -> bool {
674 self.taken.load(Ordering::Relaxed) >= self.files.len()
675 }
676}
677
678fn changed(path: &Path, refused: Refused) -> Error {
681 let what = match refused {
682 Refused::Io(error) => return io_error("open", path, error),
683 Refused::Link => "a link now, where a file or a folder was when the build began",
684 Refused::Other => "something else now than it was when the build began",
685 };
686 Error::UnsupportedEntry {
687 path: path.to_path_buf(),
688 what,
689 }
690}
691
692fn chunk_file_in(
696 builder: &mut Builder<'_>,
697 folder: &Held,
698 name: &str,
699 stop: Option<&AtomicBool>,
700) -> Result<Target> {
701 let path = || folder.path().join(name);
703 let mut file = folder
704 .open_file(name)
705 .map_err(|refused| changed(&path(), refused))?;
706 builder.file_from(|buffer| {
707 if stop.is_some_and(|stop| stop.load(Ordering::Relaxed)) {
708 return Err(STOPPED);
709 }
710 read_some(&mut file, buffer).map_err(|error| io_error("read", &path(), error))
711 })
712}
713
714struct Walk<'a> {
716 links: Links,
717 folders: Vec<Folder>,
718 files: usize,
720 on_files: &'a mut dyn FnMut(Batch) -> Result<()>,
722}
723
724impl Walk<'_> {
725 fn read(
729 &mut self,
730 held: &Arc<Held>,
731 index: usize,
732 depth: usize,
733 ) -> Result<Vec<(String, usize)>> {
734 let folder_path = held.path().to_path_buf();
735 let listed = held
736 .list()
737 .map_err(|error| io_error("list", &folder_path, error))?;
738 let mut children = Vec::with_capacity(listed.len());
739 let mut inside = Vec::new();
740 let mut files = Vec::new();
741 for (name, found) in listed {
742 let name = name.into_string().map_err(|name| Error::NonUtf8FileName {
743 path: folder_path.join(name),
744 })?;
745 check_name(&name)?;
746 match found {
747 Found::Folder => {
748 if depth >= MAX_FOLDER_DEPTH {
749 return Err(Error::TooDeep {
750 limit: MAX_FOLDER_DEPTH,
751 });
752 }
753 let below = self.folders.len();
754 children.push(Child {
755 name: name.clone(),
756 kind: Kind::Folder,
757 index: below,
758 });
759 self.folders.push(Folder {
760 path: folder_path.join(&name),
761 children: Vec::new(),
762 });
763 inside.push((name, below));
764 }
765 Found::File => {
766 children.push(Child {
767 name: name.clone(),
768 kind: Kind::File,
769 index: self.files,
770 });
771 files.push((self.files, name));
772 self.files += 1;
773 }
774 Found::Link | Found::Other => {
775 if self.links == Links::Refuse {
776 return Err(Error::UnsupportedEntry {
777 path: folder_path.join(&name),
778 what: if found == Found::Link {
779 "a link"
780 } else {
781 "a special file"
782 },
783 });
784 }
785 }
786 }
787 }
788 children.sort_by(|left, right| left.name.as_bytes().cmp(right.name.as_bytes()));
789 self.folders[index].children = children;
790 if !files.is_empty() {
791 (self.on_files)(Batch {
792 folder: Arc::clone(held),
793 files,
794 taken: AtomicUsize::new(0),
795 })?;
796 }
797 Ok(inside)
798 }
799}
800
801fn walk(
810 top: &Arc<Held>,
811 links: Links,
812 on_files: &mut dyn FnMut(Batch) -> Result<()>,
813) -> Result<(Vec<Folder>, usize)> {
814 let mut walk = Walk {
815 links,
816 folders: vec![Folder {
817 path: top.path().to_path_buf(),
818 children: Vec::new(),
819 }],
820 files: 0,
821 on_files,
822 };
823 let mut way: Vec<OnTheWay> = Vec::new();
826 let mut next = Some((Arc::clone(top), 0_usize));
827 loop {
828 if let Some((held, index)) = next.take() {
829 let inside = walk.read(&held, index, way.len() + 1)?;
830 way.push((held, inside));
831 }
832 let Some((held, inside)) = way.last_mut() else {
833 break;
834 };
835 match inside.pop() {
836 Some((name, index)) => {
837 let below = held
838 .open_folder(&name)
839 .map_err(|refused| changed(&walk.folders[index].path, refused))?;
840 next = Some((below, index));
841 }
842 None => {
843 way.pop();
844 }
845 }
846 }
847 Ok((walk.folders, walk.files))
848}
849
850const STOPPED_DETAIL: &str = "the build was stopped";
853const STOPPED: Error = Error::Invariant {
854 detail: STOPPED_DETAIL,
855};
856
857fn is_stopped(error: &Error) -> bool {
858 matches!(error, Error::Invariant { detail } if *detail == STOPPED_DETAIL)
859}
860
861fn lock<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
862 mutex
863 .lock()
864 .unwrap_or_else(|poisoned| poisoned.into_inner())
865}
866
867fn wait<'a, T>(told: &Condvar, guard: MutexGuard<'a, T>) -> MutexGuard<'a, T> {
868 told.wait(guard)
869 .unwrap_or_else(|poisoned| poisoned.into_inner())
870}
871
872struct Waiting {
879 state: Mutex<WaitingState>,
880 more: Condvar,
882 room: Condvar,
884 failed: AtomicBool,
886}
887
888struct WaitingState {
889 batches: VecDeque<Arc<Batch>>,
890 over: bool,
892}
893
894impl Waiting {
895 fn new() -> Self {
896 Self {
897 state: Mutex::new(WaitingState {
898 batches: VecDeque::new(),
899 over: false,
900 }),
901 more: Condvar::new(),
902 room: Condvar::new(),
903 failed: AtomicBool::new(false),
904 }
905 }
906
907 fn has_failed(&self) -> bool {
908 self.failed.load(Ordering::Relaxed)
909 }
910
911 fn add(&self, batch: Batch) -> Result<()> {
913 let one_file = batch.files.len() == 1;
914 let mut state = lock(&self.state);
915 loop {
916 if self.has_failed() {
917 return Err(STOPPED);
918 }
919 if state.batches.len() < FOLDERS_AHEAD {
920 break;
921 }
922 state = wait(&self.room, state);
923 }
924 state.batches.push_back(Arc::new(batch));
925 drop(state);
926 if one_file {
927 self.more.notify_one();
928 } else {
929 self.more.notify_all();
930 }
931 Ok(())
932 }
933
934 fn next(&self) -> Option<Arc<Batch>> {
938 let mut state = lock(&self.state);
939 loop {
940 if self.has_failed() {
941 return None;
942 }
943 while state.batches.front().is_some_and(|batch| batch.all_taken()) {
944 state.batches.pop_front();
945 self.room.notify_one();
946 }
947 if let Some(batch) = state.batches.front() {
948 return Some(Arc::clone(batch));
949 }
950 if state.over {
951 return None;
952 }
953 state = wait(&self.more, state);
954 }
955 }
956
957 fn fail(&self) {
960 let state = lock(&self.state);
961 self.failed.store(true, Ordering::Relaxed);
962 drop(state);
963 self.more.notify_all();
964 self.room.notify_all();
965 }
966
967 fn end(&self) {
969 lock(&self.state).over = true;
970 self.more.notify_all();
971 }
972}
973
974struct Working<'a>(&'a Waiting);
977
978impl Drop for Working<'_> {
979 fn drop(&mut self) {
980 if std::thread::panicking() {
981 self.0.fail();
982 }
983 }
984}
985
986fn walk_and_chunk(
990 store: &dyn Store,
991 chunking: Chunking,
992 top: &Arc<Held>,
993 links: Links,
994 threads: usize,
995) -> Result<(Vec<Folder>, Vec<Target>)> {
996 let threads = match threads {
997 0 => cores(),
998 threads => threads,
999 };
1000 let helpers = Helpers::new(0);
1003 if threads == 1 {
1004 let mut builder = Builder::sharing(store, chunking, helpers);
1006 let mut targets = Vec::new();
1007 let (folders, _) = walk(top, links, &mut |batch| {
1008 for (index, name) in &batch.files {
1009 if *index != targets.len() {
1010 return Err(Error::Invariant {
1011 detail: "a file was chunked out of its turn",
1012 });
1013 }
1014 targets.push(chunk_file_in(&mut builder, &batch.folder, name, None)?);
1015 }
1016 Ok(())
1017 })?;
1018 return Ok((folders, targets));
1019 }
1020 let waiting = Waiting::new();
1021 let work = || -> Result<Vec<(usize, Target)>> {
1022 let _working = Working(&waiting);
1023 let mut builder = Builder::sharing(store, chunking, Arc::clone(&helpers));
1024 let mut done = Vec::new();
1025 let mut first_error = None;
1026 while let Some(batch) = waiting.next() {
1027 while let Some((index, name)) = batch.take() {
1030 if waiting.has_failed() {
1031 break;
1032 }
1033 let stop = Some(&waiting.failed);
1034 match chunk_file_in(&mut builder, &batch.folder, name, stop) {
1035 Ok(target) => done.push((*index, target)),
1036 Err(error) => {
1037 first_error.get_or_insert(error);
1038 waiting.fail();
1039 }
1040 }
1041 }
1042 }
1043 helpers.give(1);
1044 match first_error {
1045 Some(error) => Err(error),
1046 None => Ok(done),
1047 }
1048 };
1049 let (walked, chunked) = std::thread::scope(|scope| {
1050 let _working = Working(&waiting);
1051 let handles: Vec<_> = (0..threads).map(|_| scope.spawn(work)).collect();
1052 let walked = walk(top, links, &mut |batch| waiting.add(batch));
1053 if walked.is_err() {
1056 waiting.fail();
1057 }
1058 waiting.end();
1060 let chunked: Vec<Result<Vec<(usize, Target)>>> = handles
1061 .into_iter()
1062 .map(|handle| match handle.join() {
1063 Ok(result) => result,
1064 Err(payload) => std::panic::resume_unwind(payload),
1065 })
1066 .collect();
1067 (walked, chunked)
1068 });
1069 let mut done = Vec::new();
1072 let mut stopped = false;
1073 for result in chunked {
1074 match result {
1075 Ok(part) => done.extend(part),
1076 Err(error) if is_stopped(&error) => stopped = true,
1077 Err(error) => return Err(error),
1078 }
1079 }
1080 let (folders, files) = walked?;
1081 if stopped {
1082 return Err(STOPPED);
1083 }
1084 let mut targets: Vec<Option<Target>> = vec![None; files];
1085 for (index, target) in done {
1086 targets[index] = Some(target);
1087 }
1088 let targets = targets
1089 .into_iter()
1090 .map(|target| {
1091 target.ok_or(Error::Invariant {
1092 detail: "a file was left out of the build",
1093 })
1094 })
1095 .collect::<Result<Vec<Target>>>()?;
1096 Ok((folders, targets))
1097}
1098
1099fn timestamp(time: SystemTime) -> Result<String> {
1101 let elapsed = time
1102 .duration_since(UNIX_EPOCH)
1103 .map_err(|_| Error::SystemTimeBeforeUnixEpoch)?;
1104 let seconds =
1105 i64::try_from(elapsed.as_secs()).map_err(|_| Error::SizeOverflow { field: "timestamp" })?;
1106 Ok(format_epoch_seconds(seconds))
1107}
1108
1109fn format_epoch_seconds(seconds: i64) -> String {
1110 let days = seconds.div_euclid(86_400);
1111 let seconds_of_day = seconds.rem_euclid(86_400);
1112 let shifted_days = days + 719_468;
1113 let era = shifted_days.div_euclid(146_097);
1114 let day_of_era = shifted_days - era * 146_097;
1115 let year_of_era =
1116 (day_of_era - day_of_era / 1_460 + day_of_era / 36_524 - day_of_era / 146_096) / 365;
1117 let mut year = year_of_era + era * 400;
1118 let day_of_year = day_of_era - (365 * year_of_era + year_of_era / 4 - year_of_era / 100);
1119 let month_prime = (5 * day_of_year + 2) / 153;
1120 let day = day_of_year - (153 * month_prime + 2) / 5 + 1;
1121 let month = month_prime + if month_prime < 10 { 3 } else { -9 };
1122 if month <= 2 {
1123 year += 1;
1124 }
1125 let hour = seconds_of_day / 3_600;
1126 let minute = seconds_of_day % 3_600 / 60;
1127 let second = seconds_of_day % 60;
1128 format!("{year:04}-{month:02}-{day:02}T{hour:02}:{minute:02}:{second:02}Z")
1129}
1130
1131#[cfg(test)]
1132mod tests {
1133 use super::*;
1134 use crate::{Hash, MemoryStore};
1135 use std::time::{Duration, Instant};
1136
1137 const CHUNK: usize = 4 << 20;
1140
1141 const ALONE: usize = ROOM_ALONE / 2;
1143
1144 struct Slow(MemoryStore);
1147
1148 impl Store for Slow {
1149 fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1150 std::thread::sleep(Duration::from_millis(100));
1151 self.0.put(kind, hash, bytes)
1152 }
1153
1154 fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1155 self.0.get(kind, hash)
1156 }
1157
1158 fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1159 self.0.remove(kind, hash)
1160 }
1161 }
1162
1163 struct Counted {
1165 inner: MemoryStore,
1166 chunks: AtomicUsize,
1167 }
1168
1169 impl Store for Counted {
1170 fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1171 self.inner.put(kind, hash, bytes)?;
1172 if kind == Stored::Chunk {
1173 self.chunks.fetch_add(1, Ordering::SeqCst);
1174 }
1175 Ok(())
1176 }
1177
1178 fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1179 self.inner.get(kind, hash)
1180 }
1181
1182 fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1183 self.inner.remove(kind, hash)
1184 }
1185 }
1186
1187 struct Taking {
1190 inner: MemoryStore,
1191 helpers: Arc<Helpers>,
1192 }
1193
1194 impl Store for Taking {
1195 fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
1196 self.helpers.take(usize::MAX);
1197 self.inner.put(kind, hash, bytes)
1198 }
1199
1200 fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
1201 self.inner.get(kind, hash)
1202 }
1203
1204 fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
1205 self.inner.remove(kind, hash)
1206 }
1207 }
1208
1209 fn read_through(
1213 store: &dyn Store,
1214 helpers: Arc<Helpers>,
1215 chunks: usize,
1216 mut asked: impl FnMut(usize, usize),
1217 ) {
1218 let chunking = Chunking::fixed(CHUNK as u32).unwrap();
1219 let mut builder = Builder::sharing(store, chunking, helpers);
1220 let longest = window_room(chunking, true);
1223 builder.windows.current.resize(longest, 0);
1224 builder.windows.next.resize(longest, 0);
1225 let length = chunks * CHUNK;
1226 let mut at = 0;
1227 builder
1228 .file_from(|buffer| {
1229 asked(at, buffer.len());
1230 let count = buffer.len().min(length - at);
1231 let mut done = 0;
1232 while done < count {
1233 let chunk = (at + done) / CHUNK;
1234 let end = ((chunk + 1) * CHUNK - at).min(count);
1235 buffer[done..end].fill(chunk as u8);
1236 done = end;
1237 }
1238 at += count;
1239 Ok(count)
1240 })
1241 .unwrap();
1242 }
1243
1244 #[test]
1245 fn a_file_whose_chunks_are_kept_slowly_is_read_in_longer_windows_once_helpers_are_free() {
1246 let store = Slow(MemoryStore::new());
1247 let helpers = Helpers::new(0);
1250 let free = Arc::clone(&helpers);
1251 let mut longest = 0;
1252 read_through(&store, helpers, 12, |at, length| {
1253 if at == 0 {
1254 free.give(6);
1255 }
1256 longest = longest.max(length);
1257 });
1258 assert!(
1259 longest > ALONE,
1260 "the longest read asked for {longest} bytes"
1261 );
1262 }
1263
1264 #[test]
1265 fn a_file_whose_chunks_are_kept_as_fast_as_it_is_read_keeps_its_short_windows() {
1266 let store = Counted {
1267 inner: MemoryStore::new(),
1268 chunks: AtomicUsize::new(0),
1269 };
1270 let helpers = Helpers::new(0);
1271 let free = Arc::clone(&helpers);
1272 let mut longest = 0;
1273 read_through(&store, helpers, 12, |at, length| {
1274 if at == 0 {
1275 free.give(6);
1276 }
1277 let waited = Instant::now();
1281 while store.chunks.load(Ordering::SeqCst) < at / CHUNK
1282 && waited.elapsed() < Duration::from_secs(10)
1283 {
1284 std::thread::sleep(Duration::from_millis(1));
1285 }
1286 std::thread::sleep(Duration::from_millis(20));
1287 longest = longest.max(length);
1288 });
1289 assert!(longest <= ALONE, "a read asked for {longest} bytes");
1290 }
1291
1292 #[test]
1293 fn helpers_that_are_free_for_a_moment_do_not_grow_a_window() {
1294 let store = Slow(MemoryStore::new());
1295 let helpers = Helpers::new(0);
1296 let free = Arc::clone(&helpers);
1297 let mut held = 0;
1298 let mut longest_early = 0;
1299 let mut longest = 0;
1300 let early = (2 * WINDOWS_BEHIND_TO_GROW + 1) * ALONE;
1304 read_through(&store, helpers, 20, |at, length| {
1305 let window = at / ALONE;
1306 if at == 0 {
1307 free.give(6);
1308 } else if window == WINDOWS_BEHIND_TO_GROW {
1309 held += free.take(usize::MAX);
1310 } else if window == WINDOWS_BEHIND_TO_GROW + 1 {
1311 free.give(std::mem::take(&mut held));
1312 }
1313 if at < early {
1314 longest_early = longest_early.max(length);
1315 }
1316 longest = longest.max(length);
1317 });
1318 assert!(
1319 longest_early <= ALONE,
1320 "a read before byte {early} asked for {longest_early} bytes"
1321 );
1322 assert!(longest > ALONE, "the windows never grew");
1323 }
1324
1325 #[test]
1326 fn a_window_that_too_few_helpers_could_share_keeps_its_length() {
1327 let store = Slow(MemoryStore::new());
1328 let helpers = Helpers::new(0);
1329 let free = Arc::clone(&helpers);
1330 let mut longest = 0;
1331 read_through(&store, helpers, 12, |at, length| {
1333 if at == 0 {
1334 free.give(3);
1335 }
1336 longest = longest.max(length);
1337 });
1338 assert!(longest <= ALONE, "a read asked for {longest} bytes");
1339 }
1340
1341 #[test]
1342 fn chunks_that_no_helper_keeps_do_not_count_as_behind() {
1343 let helpers = Helpers::new(0);
1344 let store = Taking {
1345 inner: MemoryStore::new(),
1346 helpers: Arc::clone(&helpers),
1347 };
1348 let free = Arc::clone(&helpers);
1349 let mut longest = 0;
1350 read_through(&store, helpers, 12, |at, length| {
1355 if at > 0 {
1356 free.give(6);
1357 }
1358 longest = longest.max(length);
1359 });
1360 assert!(longest <= ALONE, "a read asked for {longest} bytes");
1361 }
1362
1363 #[test]
1364 fn the_time_is_written_in_utc_to_the_second() {
1365 assert_eq!(format_epoch_seconds(0), "1970-01-01T00:00:00Z");
1366 assert_eq!(format_epoch_seconds(951_782_400), "2000-02-29T00:00:00Z");
1367 assert_eq!(format_epoch_seconds(1_794_472_200), "2026-11-12T08:30:00Z");
1368 assert_eq!(format_epoch_seconds(4_102_444_799), "2099-12-31T23:59:59Z");
1369 assert_eq!(format_epoch_seconds(-1), "1969-12-31T23:59:59Z");
1370 }
1371}