use crate::fastcdc::StreamChunker;
use crate::format::{
ChunkRef, Chunking, FileList, FolderList, Kind, Record, Target, Totals, LIST_ITEM_BYTES,
MAX_CHUNK_BYTES, MAX_FOLDER_DEPTH, MAX_RECORD_BYTES,
};
use crate::hash::{Hash, Root};
use crate::store::{lent, load_record, missing, Store, Stored};
use crate::threads::{cores, on_threads};
use crate::wire::{
read_next_onto, Next, Request, FRAME_CHUNK, FRAME_FILE_LIST, FRAME_FOLDER_LIST, FRAME_RECORD,
};
use crate::{Error, Result};
use std::collections::{BTreeMap, HashMap};
use std::io::Read;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::{Arc, Mutex, MutexGuard};
const CHUNKS_PER_REQUEST: u32 = 64;
const LOOKS_BY_EACH: usize = 64;
fn invalid(detail: &str) -> Error {
Error::InvalidData {
detail: detail.to_owned(),
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Arrived {
Record,
FolderList(Hash),
FileList(Hash),
Chunk(Hash),
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Accepted {
pub what: Arrived,
pub kept: bool,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Summary {
pub record: Record,
pub folders: u64,
pub files: u64,
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct VerifyOptions {
rechunk: bool,
discard: bool,
workers: usize,
}
impl VerifyOptions {
pub fn new() -> Self {
Self::default()
}
pub fn rechunk(mut self, on: bool) -> Self {
self.rechunk = on;
self
}
pub fn discard_damaged(mut self, on: bool) -> Self {
self.discard = on;
self
}
pub fn workers(mut self, workers: usize) -> Self {
self.workers = workers;
self
}
}
#[derive(Clone, Copy, Default)]
struct Mode {
rechunk: bool,
discard: bool,
threads: usize,
}
struct FolderSlot {
size: u64,
order: u64,
held: bool,
inside: Vec<Hash>,
}
struct FileSlot {
size: u64,
order: u64,
held: bool,
}
struct ChunkSlot {
length: u32,
wanted_at: Option<(u64, u64)>,
}
pub struct Intake<'s> {
store: &'s dyn Store,
root: Root,
mode: Mode,
record: Option<Record>,
measuring: Option<Chunking>,
folders: HashMap<Hash, FolderSlot>,
files: HashMap<Hash, FileSlot>,
chunks: HashMap<Hash, ChunkSlot>,
wanted_lists: BTreeMap<u64, Target>,
wanted_chunks: BTreeMap<(u64, u64), Hash>,
file_by_order: HashMap<u64, Hash>,
next_order: u64,
counted: Totals,
pending: Vec<Target>,
to_rechunk: Vec<Hash>,
chunker: Option<StreamChunker>,
failed: bool,
}
impl<'s> Intake<'s> {
pub fn new(store: &'s dyn Store, root: Root) -> Result<Self> {
let mode = Mode {
discard: true,
..Mode::default()
};
Self::with_mode(store, root, mode)
}
fn bare(store: &'s dyn Store, root: Root, mode: Mode) -> Self {
Self {
store,
root,
mode,
record: None,
measuring: None,
folders: HashMap::new(),
files: HashMap::new(),
chunks: HashMap::new(),
wanted_lists: BTreeMap::new(),
wanted_chunks: BTreeMap::new(),
file_by_order: HashMap::new(),
next_order: 0,
counted: Totals::default(),
pending: Vec::new(),
to_rechunk: Vec::new(),
chunker: None,
failed: false,
}
}
fn with_mode(store: &'s dyn Store, root: Root, mode: Mode) -> Result<Self> {
let mut intake = Self::bare(store, root, mode);
match load_record(store, &root) {
Ok(Some(record)) => intake.begin(record)?,
Ok(None) => {}
Err(Error::Corrupt { .. }) if mode.discard => {
store.remove(Stored::Record, root.as_hash())?;
}
Err(error) => return Err(error),
}
Ok(intake)
}
pub(crate) fn measure(
store: &'s dyn Store,
top: Target,
chunking: Chunking,
threads: usize,
) -> Result<Totals> {
let mode = Mode {
threads,
..Mode::default()
};
let mut intake = Self::bare(store, Root::from_hash(Hash::ZERO), mode);
intake.measuring = Some(chunking);
intake.refer(top)?;
intake.drain()?;
intake.lists_held()?;
intake.check_depth(&top)?;
Ok(intake.counted)
}
pub fn root(&self) -> &Root {
&self.root
}
pub fn record(&self) -> Option<&Record> {
self.record.as_ref()
}
pub fn outstanding(&self) -> usize {
usize::from(self.record.is_none()) + self.wanted_lists.len() + self.wanted_chunks.len()
}
fn lists_left(&self) -> usize {
let Some(record) = &self.record else {
return 0;
};
let left = record
.totals()
.list_bytes
.saturating_sub(self.counted.list_bytes);
usize::try_from(left).unwrap_or(usize::MAX)
}
fn longest_chunk(&self) -> usize {
match self.record.as_ref().map(Record::chunking) {
Some(Chunking::Fixed(length)) => length.get() as usize,
_ => MAX_CHUNK_BYTES,
}
}
pub fn frame_limit(&self) -> usize {
let Some(record) = &self.record else {
return MAX_RECORD_BYTES;
};
usize::try_from(record.totals().list_bytes)
.unwrap_or(usize::MAX)
.max(self.longest_chunk())
.saturating_add(1)
.max(MAX_RECORD_BYTES)
}
pub fn answer_limit(&self, request: &Request) -> usize {
let limit = match request {
Request::Record(_) => MAX_RECORD_BYTES,
Request::Folder(_) => self.lists_left().saturating_add(1),
Request::File(file) => {
let most = match (&self.record, self.files.get(file)) {
(Some(record), Some(slot)) => record.chunking().count_bounds(slot.size).1,
_ => 0,
};
usize::try_from(most)
.unwrap_or(usize::MAX)
.saturating_mul(LIST_ITEM_BYTES)
.min(self.lists_left())
.saturating_add(1)
}
Request::Chunks { .. } | Request::Chunk(_) => self.longest_chunk() + 1,
_ => 0,
};
limit.max(2)
}
fn begin(&mut self, record: Record) -> Result<()> {
let top = record.top();
self.record = Some(record);
self.refer(top)?;
self.drain()
}
fn recorded(&self) -> Result<&Record> {
self.record.as_ref().ok_or(Error::NotWanted {
what: "a frame that comes before the record",
})
}
fn chunking(&self) -> Result<Chunking> {
match self.measuring {
Some(chunking) => Ok(chunking),
None => Ok(self.recorded()?.chunking()),
}
}
fn lists_held(&self) -> Result<()> {
match self.wanted_lists.values().next() {
Some(target) => Err(missing(
match target.kind {
Kind::Folder => "the list of the folder",
Kind::File => "the list of the file",
},
&target.hash,
)),
None => Ok(()),
}
}
fn damaged(&self, kind: Stored, hash: &Hash, what: &'static str) -> Result<()> {
if self.mode.discard {
self.store.remove(kind, hash)
} else {
Err(Error::Corrupt { what, hash: *hash })
}
}
fn held_of(&self, items: &[(u64, &ChunkRef)]) -> Vec<Result<bool>> {
let threads = match self.mode.threads {
0 => cores(),
threads => threads,
};
let workers = (items.len() / LOOKS_BY_EACH).clamp(1, threads);
if workers == 1 {
return items.iter().map(|(_, item)| self.holds(item)).collect();
}
let next = AtomicUsize::new(0);
let work = || {
let mut found = Vec::new();
loop {
let index = next.fetch_add(1, Ordering::Relaxed);
let Some((_, item)) = items.get(index) else {
return found;
};
found.push((index, self.holds(item)));
}
};
let mut found: Vec<(usize, Result<bool>)> =
on_threads(workers, &work).into_iter().flatten().collect();
found.sort_unstable_by_key(|(index, _)| *index);
found.into_iter().map(|(_, held)| held).collect()
}
fn holds(&self, item: &ChunkRef) -> Result<bool> {
let size = match self.store.size(Stored::Chunk, &item.hash)? {
None => return Ok(false),
Some(size) if size == u64::from(item.length) => return Ok(true),
Some(size) => size,
};
match self.store.get(Stored::Chunk, &item.hash)? {
None => Ok(false),
Some(bytes) if Hash::of(&bytes) == item.hash => Err(Error::SizeMismatch {
what: "a held chunk",
expected: u64::from(item.length),
actual: size,
}),
Some(_) => {
self.damaged(Stored::Chunk, &item.hash, "a stored chunk")?;
Ok(false)
}
}
}
fn refer(&mut self, target: Target) -> Result<()> {
let known = match target.kind {
Kind::Folder => self.folders.get(&target.hash).map(|slot| slot.size),
Kind::File => self.files.get(&target.hash).map(|slot| slot.size),
};
if let Some(size) = known {
return if size == target.size {
Ok(())
} else {
Err(Error::SizeMismatch {
what: "a file or folder that is named twice",
expected: size,
actual: target.size,
})
};
}
let order = self.next_order;
self.next_order += 1;
match target.kind {
Kind::Folder => {
self.folders.insert(
target.hash,
FolderSlot {
size: target.size,
order,
held: false,
inside: Vec::new(),
},
);
}
Kind::File => {
self.files.insert(
target.hash,
FileSlot {
size: target.size,
order,
held: false,
},
);
self.file_by_order.insert(order, target.hash);
}
}
self.pending.push(target);
Ok(())
}
fn drain(&mut self) -> Result<()> {
while let Some(target) = self.pending.pop() {
match target.kind {
Kind::Folder => {
let held = self.store.get(Stored::FolderList, &target.hash)?;
let list = held.as_deref().map(|bytes| {
FolderList::decode(bytes)
.ok()
.filter(|list| *list.hash() == target.hash)
});
match list {
Some(Some(list)) => self.admit_folder(&list)?,
Some(None) => {
let what = "a stored folder's list";
self.damaged(Stored::FolderList, &target.hash, what)?;
self.want(target);
}
None => self.want(target),
}
}
Kind::File => {
let held = self.store.get(Stored::FileList, &target.hash)?;
let list = held.as_deref().map(|bytes| {
FileList::decode(bytes)
.ok()
.filter(|list| *list.hash() == target.hash)
});
match list {
Some(Some(list)) => self.admit_file(&list)?,
Some(None) => {
let what = "a stored file's list";
self.damaged(Stored::FileList, &target.hash, what)?;
self.want(target);
}
None => self.want(target),
}
}
}
}
Ok(())
}
fn want(&mut self, target: Target) {
let order = match target.kind {
Kind::Folder => self.folders.get(&target.hash).map(|slot| slot.order),
Kind::File => self.files.get(&target.hash).map(|slot| slot.order),
};
if let Some(order) = order {
self.wanted_lists.insert(order, target);
}
}
fn count_list_bytes(&mut self, bytes: u64) -> Result<()> {
self.counted.list_bytes =
self.counted
.list_bytes
.checked_add(bytes)
.ok_or(Error::SizeOverflow {
field: "list bytes",
})?;
let Some(record) = &self.record else {
return Ok(());
};
let recorded = record.totals().list_bytes;
if self.counted.list_bytes > recorded {
return Err(Error::TotalsMismatch {
field: "list bytes",
recorded,
counted: self.counted.list_bytes,
});
}
Ok(())
}
fn count_chunk(&mut self, length: u32) -> Result<()> {
self.counted.chunks = self
.counted
.chunks
.checked_add(1)
.ok_or(Error::SizeOverflow { field: "chunks" })?;
self.counted.chunk_bytes = self
.counted
.chunk_bytes
.checked_add(u64::from(length))
.ok_or(Error::SizeOverflow {
field: "chunk bytes",
})?;
let Some(record) = &self.record else {
return Ok(());
};
let recorded = record.totals();
if self.counted.chunks > recorded.chunks {
return Err(Error::TotalsMismatch {
field: "chunks",
recorded: recorded.chunks,
counted: self.counted.chunks,
});
}
if self.counted.chunk_bytes > recorded.chunk_bytes {
return Err(Error::TotalsMismatch {
field: "chunk bytes",
recorded: recorded.chunk_bytes,
counted: self.counted.chunk_bytes,
});
}
Ok(())
}
fn admit_folder(&mut self, list: &FolderList) -> Result<()> {
let slot = self.folders.get_mut(list.hash()).ok_or(Error::Invariant {
detail: "a folder is admitted before it is named",
})?;
if slot.size != list.size() {
return Err(Error::SizeMismatch {
what: "a folder",
expected: slot.size,
actual: list.size(),
});
}
slot.held = true;
slot.inside = list
.entries()
.iter()
.filter(|entry| entry.kind() == Kind::Folder)
.map(|entry| *entry.hash())
.collect();
slot.inside.sort_unstable();
slot.inside.dedup();
let order = slot.order;
self.wanted_lists.remove(&order);
self.count_list_bytes(list.encoded_len())?;
for entry in list.entries() {
self.refer(entry.target())?;
}
Ok(())
}
fn admit_file(&mut self, list: &FileList) -> Result<()> {
let chunking = self.chunking()?;
list.check_chunking(chunking)?;
let slot = self.files.get_mut(list.hash()).ok_or(Error::Invariant {
detail: "a file is admitted before it is named",
})?;
if slot.size != list.size() {
return Err(Error::SizeMismatch {
what: "a file",
expected: slot.size,
actual: list.size(),
});
}
slot.held = true;
let order = slot.order;
self.wanted_lists.remove(&order);
self.count_list_bytes(list.encoded_len())?;
let mut first: HashMap<Hash, u32> = HashMap::new();
let mut fresh: Vec<(u64, &ChunkRef)> = Vec::new();
let mut wrong = None;
for (number, item) in (0_u64..).zip(list.items()) {
let known = self
.chunks
.get(&item.hash)
.map(|slot| slot.length)
.or_else(|| first.get(&item.hash).copied());
if let Some(length) = known {
if length != item.length {
wrong = Some(Error::SizeMismatch {
what: "a chunk that is listed with two lengths",
expected: u64::from(length),
actual: u64::from(item.length),
});
break;
}
continue;
}
if let Err(error) = self.count_chunk(item.length) {
wrong = Some(error);
break;
}
first.insert(item.hash, item.length);
fresh.push((number, item));
}
let held = self.held_of(&fresh);
for ((number, item), held) in fresh.into_iter().zip(held) {
let held = held?;
let wanted_at = (!held).then_some((order, number));
if let Some(at) = wanted_at {
self.wanted_chunks.insert(at, item.hash);
}
self.chunks.insert(
item.hash,
ChunkSlot {
length: item.length,
wanted_at,
},
);
}
if let Some(error) = wrong {
return Err(error);
}
if self.mode.rechunk && chunking == Chunking::FastCdcV1 {
self.to_rechunk.push(*list.hash());
}
Ok(())
}
fn rehash_held(&mut self, workers: usize) -> Result<()> {
let mut held: Vec<ChunkRef> = self
.chunks
.iter()
.filter(|(_, slot)| slot.wanted_at.is_none())
.map(|(hash, slot)| ChunkRef {
hash: *hash,
length: slot.length,
})
.collect();
held.sort_unstable_by_key(|item| item.hash);
let store = self.store;
let next = AtomicUsize::new(0);
let work = || -> Result<Vec<usize>> {
let mut spoiled = Vec::new();
loop {
let index = next.fetch_add(1, Ordering::Relaxed);
let Some(item) = held.get(index) else {
return Ok(spoiled);
};
let mut sound = false;
let found = lent(store, Stored::Chunk, &item.hash, &mut |bytes| {
sound = item.matches(bytes);
Ok(())
})
.and_then(|held| {
if held {
Ok(())
} else {
Err(missing("the chunk", &item.hash))
}
});
match found {
Ok(()) if sound => {}
Ok(()) => spoiled.push(index),
Err(error) => {
next.store(held.len(), Ordering::Relaxed);
return Err(error);
}
}
}
};
let workers = match workers {
0 => std::thread::available_parallelism().map_or(1, usize::from),
workers => workers,
}
.min(held.len());
let results: Vec<Result<Vec<usize>>> = on_threads(workers, &work);
let mut spoiled = Vec::new();
for result in results {
spoiled.extend(result?);
}
spoiled.sort_unstable();
for &index in &spoiled {
self.damaged(Stored::Chunk, &held[index].hash, "a stored chunk")?;
}
match spoiled.first() {
Some(&index) => Err(missing("the chunk", &held[index].hash)),
None => Ok(()),
}
}
fn rechunk_held(&mut self) -> Result<()> {
for file in std::mem::take(&mut self.to_rechunk) {
let Some(bytes) = self.store.get(Stored::FileList, &file)? else {
continue;
};
let list = FileList::decode(&bytes)?;
let whole = list.items().iter().all(|item| {
self.chunks
.get(&item.hash)
.is_some_and(|slot| slot.wanted_at.is_none())
});
if whole {
self.rechunk(&list)?;
}
}
Ok(())
}
fn rechunk(&mut self, list: &FileList) -> Result<()> {
let store = self.store;
let chunker = self.chunker.get_or_insert_with(StreamChunker::new);
let mut unread = list.items().iter();
let mut current: Option<(Arc<[u8]>, usize)> = None;
let mut unchunked = list.items().iter();
let mischunked = || invalid("the chunks of a file do not end where its bytes say they end");
chunker.cut(
Chunking::FastCdcV1,
2 * MAX_CHUNK_BYTES,
|buffer| loop {
if let Some((bytes, at)) = &mut current {
if *at < bytes.len() {
let count = buffer.len().min(bytes.len() - *at);
buffer[..count].copy_from_slice(&bytes[*at..*at + count]);
*at += count;
return Ok(count);
}
}
match unread.next() {
Some(item) => {
let bytes = store
.get(Stored::Chunk, &item.hash)?
.filter(|bytes| bytes.len() == item.length as usize)
.ok_or_else(|| missing("the chunk", &item.hash))?;
current = Some((bytes, 0));
}
None => return Ok(0),
}
},
|chunks| {
for chunk in chunks {
match unchunked.next() {
Some(item) if item.length as usize == chunk.len() => {}
_ => return Err(mischunked()),
}
}
Ok(())
},
)?;
if unchunked.next().is_some() {
return Err(mischunked());
}
Ok(())
}
pub fn accept(&mut self, frame: &[u8]) -> Result<Accepted> {
self.accept_inner(frame, None)
}
pub fn accept_expected(&mut self, frame: &[u8], expected: Arrived) -> Result<Accepted> {
self.accept_inner(frame, Some(expected))
}
fn accept_chunks(&mut self, frames: &[(&[u8], Option<Arrived>)], workers: usize) -> Result<()> {
if self.failed {
return Err(Error::IntakeFailed);
}
if frames.is_empty() {
return Ok(());
}
self.recorded()?;
self.failed = true;
let store = self.store;
let slots = Mutex::new(&mut self.chunks);
let next = AtomicUsize::new(0);
let work = || {
let mut settled = Vec::new();
loop {
let index = next.fetch_add(1, Ordering::Relaxed);
let Some(&(frame, expected)) = frames.get(index) else {
return settled;
};
settled.push((index, take_chunk(store, &slots, frame, expected)));
}
};
let workers = workers.clamp(1, frames.len());
let settled: Vec<_> = on_threads(workers, &work).into_iter().flatten().collect();
self.failed = false;
let mut first: Option<(usize, Error)> = None;
for (index, taken) in settled {
match taken {
Ok((_, Some(at))) => {
self.wanted_chunks.remove(&at);
}
Ok((_, None)) => {}
Err(error) => {
if first.as_ref().is_none_or(|(before, _)| index < *before) {
first = Some((index, error));
}
}
}
}
first.map_or(Ok(()), |(_, error)| Err(error))
}
fn taking(&mut self, step: impl FnOnce(&mut Self) -> Result<()>) -> Result<()> {
let done = step(self);
self.failed |= done.is_err();
done
}
fn accept_inner(&mut self, frame: &[u8], expected: Option<Arrived>) -> Result<Accepted> {
if self.failed {
return Err(Error::IntakeFailed);
}
let (&tag, body) = frame
.split_first()
.ok_or_else(|| invalid("a frame is empty"))?;
let as_asked = |arrived: Arrived, what: &'static str| match expected {
Some(expected) if expected != arrived => Err(Error::NotWanted { what }),
_ => Ok(()),
};
match tag {
FRAME_RECORD => {
let what = Arrived::Record;
as_asked(what, "a record")?;
if Root::of_record(frame) != self.root {
return Err(Error::HashMismatch { what: "a record" });
}
if self.record.is_some() {
return Ok(Accepted { what, kept: false });
}
let record = Record::decode(frame)?;
self.store.put(Stored::Record, self.root.as_hash(), frame)?;
self.taking(|intake| intake.begin(record))?;
Ok(Accepted { what, kept: true })
}
FRAME_FOLDER_LIST => {
self.recorded()?;
let list = FolderList::decode(body)?;
let what = Arrived::FolderList(*list.hash());
as_asked(what, "a folder's list")?;
match self.folders.get(list.hash()) {
None => Err(Error::NotWanted {
what: "a folder's list",
}),
Some(slot) if slot.held => Ok(Accepted { what, kept: false }),
Some(slot) if slot.size != list.size() => Err(Error::SizeMismatch {
what: "a folder",
expected: slot.size,
actual: list.size(),
}),
Some(_) => {
self.taking(|intake| {
intake.admit_folder(&list)?;
intake.store.put(Stored::FolderList, list.hash(), body)?;
intake.drain()
})?;
Ok(Accepted { what, kept: true })
}
}
}
FRAME_FILE_LIST => {
self.recorded()?;
let list = FileList::decode(body)?;
let what = Arrived::FileList(*list.hash());
as_asked(what, "a file's list")?;
match self.files.get(list.hash()) {
None => Err(Error::NotWanted {
what: "a file's list",
}),
Some(slot) if slot.held => Ok(Accepted { what, kept: false }),
Some(slot) if slot.size != list.size() => Err(Error::SizeMismatch {
what: "a file",
expected: slot.size,
actual: list.size(),
}),
Some(_) => {
self.taking(|intake| {
intake.admit_file(&list)?;
intake.store.put(Stored::FileList, list.hash(), body)
})?;
Ok(Accepted { what, kept: true })
}
}
}
FRAME_CHUNK => {
self.recorded()?;
self.failed = true;
let taken = take_chunk(self.store, &Mutex::new(&mut self.chunks), frame, expected);
self.failed = false;
let (hash, kept) = taken?;
if let Some(at) = kept {
self.wanted_chunks.remove(&at);
}
Ok(Accepted {
what: Arrived::Chunk(hash),
kept: kept.is_some(),
})
}
_ => Err(invalid("a frame that no tree is taken in by")),
}
}
pub fn requests(&self, limit: usize) -> Vec<Request> {
if self.failed {
return Vec::new();
}
if self.record.is_none() {
return vec![Request::Record(self.root)];
}
let mut requests: Vec<Request> = self
.wanted_lists
.values()
.take(limit)
.map(|target| match target.kind {
Kind::Folder => Request::Folder(target.hash),
Kind::File => Request::File(target.hash),
})
.collect();
let mut span: Option<(u64, u64, u32)> = None;
for &(order, number) in self.wanted_chunks.keys() {
if let Some((span_order, start, count)) = &mut span {
if *span_order == order
&& *start + u64::from(*count) == number
&& *count < CHUNKS_PER_REQUEST
{
*count += 1;
continue;
}
}
if let Some(done) = span.take() {
self.push_chunks(&mut requests, done);
}
if requests.len() >= limit {
break;
}
span = Some((order, number, 1));
}
if let Some(done) = span {
if requests.len() < limit {
self.push_chunks(&mut requests, done);
}
}
requests
}
fn push_chunks(&self, requests: &mut Vec<Request>, (order, start, count): (u64, u64, u32)) {
if let Some(file) = self.file_by_order.get(&order) {
requests.push(Request::Chunks {
file: *file,
start,
count,
});
}
}
pub fn expected(&self, request: &Request) -> Vec<Arrived> {
match request {
Request::Record(_) => vec![Arrived::Record],
Request::Folder(folder) => vec![Arrived::FolderList(*folder)],
Request::File(file) => vec![Arrived::FileList(*file)],
Request::Chunks { file, start, count } => {
let Some(order) = self.files.get(file).map(|slot| slot.order) else {
return Vec::new();
};
(*start..start.saturating_add(u64::from(*count)))
.map_while(|number| self.wanted_chunks.get(&(order, number)))
.map(|hash| Arrived::Chunk(*hash))
.collect()
}
_ => Vec::new(),
}
}
fn check_depth(&self, top: &Target) -> Result<()> {
if top.kind != Kind::Folder {
return Ok(());
}
let too_deep = || Error::TooDeep {
limit: MAX_FOLDER_DEPTH,
};
let mut heights: HashMap<Hash, usize> = HashMap::new();
let mut path: Vec<(Hash, usize)> = vec![(top.hash, 0)];
while let Some(&(folder, next)) = path.last() {
let inside = self
.folders
.get(&folder)
.map_or(&[][..], |slot| slot.inside.as_slice());
if let Some(child) = inside.get(next) {
if let Some(last) = path.last_mut() {
last.1 += 1;
}
match heights.get(child) {
Some(height) if path.len() + height > MAX_FOLDER_DEPTH => {
return Err(too_deep());
}
Some(_) => {}
None if path.len() >= MAX_FOLDER_DEPTH => return Err(too_deep()),
None => path.push((*child, 0)),
}
} else {
let height = 1 + inside
.iter()
.filter_map(|child| heights.get(child))
.max()
.copied()
.unwrap_or(0);
heights.insert(folder, height);
path.pop();
}
}
Ok(())
}
pub fn finish(self) -> Result<Summary> {
if self.failed {
return Err(Error::IntakeFailed);
}
if let Some(hash) = self.wanted_chunks.values().next() {
if self.record.is_some() && self.wanted_lists.is_empty() {
return Err(missing("the chunk", hash));
}
}
self.finish_lists()
}
pub(crate) fn finish_lists(self) -> Result<Summary> {
if self.failed {
return Err(Error::IntakeFailed);
}
let Some(record) = &self.record else {
return Err(missing("the record of", self.root.as_hash()));
};
self.lists_held()?;
self.check_depth(&record.top())?;
let recorded = record.totals();
for (field, recorded, counted) in [
("chunks", recorded.chunks, self.counted.chunks),
(
"chunk bytes",
recorded.chunk_bytes,
self.counted.chunk_bytes,
),
("list bytes", recorded.list_bytes, self.counted.list_bytes),
] {
if recorded != counted {
return Err(Error::TotalsMismatch {
field,
recorded,
counted,
});
}
}
Ok(Summary {
folders: self.folders.len() as u64,
files: self.files.len() as u64,
record: record.clone(),
})
}
}
fn lock<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
mutex
.lock()
.unwrap_or_else(|poisoned| poisoned.into_inner())
}
fn take_chunk(
store: &dyn Store,
slots: &Mutex<&mut HashMap<Hash, ChunkSlot>>,
frame: &[u8],
expected: Option<Arrived>,
) -> Result<(Hash, Option<(u64, u64)>)> {
let body = match frame.split_first() {
Some((&FRAME_CHUNK, body)) => body,
_ => {
return Err(Error::Invariant {
detail: "a frame taken in as a chunk is not a chunk",
})
}
};
if body.is_empty() || body.len() > MAX_CHUNK_BYTES {
return Err(invalid("a chunk does not hold 1 byte to 8 MiB"));
}
let hash = Hash::of(body);
if expected.is_some_and(|expected| expected != Arrived::Chunk(hash)) {
return Err(Error::NotWanted { what: "a chunk" });
}
let at = {
let mut slots = lock(slots);
let slot = slots
.get_mut(&hash)
.ok_or(Error::NotWanted { what: "a chunk" })?;
let Some(at) = slot.wanted_at else {
return Ok((hash, None));
};
if slot.length as usize != body.len() {
return Err(Error::SizeMismatch {
what: "a chunk",
expected: u64::from(slot.length),
actual: body.len() as u64,
});
}
slot.wanted_at = None;
at
};
match store.put(Stored::Chunk, &hash, body) {
Ok(()) => Ok((hash, Some(at))),
Err(error) => {
if let Some(slot) = lock(slots).get_mut(&hash) {
slot.wanted_at = Some(at);
}
Err(error)
}
}
}
const CHUNK_FRAMES_BYTES: usize = 16 << 20;
const CHUNK_FRAMES_COUNT: usize = 1024;
const CHUNK_BYTES_BY_EACH: usize = 1 << 20;
pub(crate) struct ChunkFrames {
memory: Vec<u8>,
ends: Vec<usize>,
expected: Vec<Option<Arrived>>,
cores: usize,
}
impl ChunkFrames {
pub(crate) fn new() -> Self {
Self {
memory: Vec::new(),
ends: Vec::new(),
expected: Vec::new(),
cores: std::thread::available_parallelism().map_or(1, usize::from),
}
}
fn held_bytes(&self) -> usize {
self.ends.last().copied().unwrap_or(0)
}
fn make_room(&mut self) {
let batch = CHUNK_FRAMES_BYTES + MAX_CHUNK_BYTES + 1;
if self.memory.capacity() < batch {
self.memory.reserve_exact(batch - self.memory.len());
}
}
pub(crate) fn read_next(&mut self, input: &mut dyn Read, limit: usize) -> Result<Next> {
self.make_room();
self.memory.truncate(self.held_bytes());
read_next_onto(input, limit, &mut self.memory)
}
pub(crate) fn next_is_chunk(&self) -> bool {
self.memory.get(self.held_bytes()) == Some(&FRAME_CHUNK)
}
pub(crate) fn take_next(&mut self, frame: &mut Vec<u8>) {
let held = self.held_bytes();
frame.clear();
frame.extend_from_slice(&self.memory[held..]);
self.memory.truncate(held);
}
pub(crate) fn hold(&mut self, expected: Option<Arrived>) {
self.ends.push(self.memory.len());
self.expected.push(expected);
}
pub(crate) fn hold_copy(&mut self, frame: &[u8], expected: Option<Arrived>) {
self.make_room();
self.memory.truncate(self.held_bytes());
self.memory.extend_from_slice(frame);
self.hold(expected);
}
pub(crate) fn full(&self) -> bool {
self.held_bytes() >= CHUNK_FRAMES_BYTES || self.ends.len() >= CHUNK_FRAMES_COUNT
}
pub(crate) fn take_in(&mut self, intake: &mut Intake<'_>) -> Result<()> {
if self.ends.is_empty() {
return Ok(());
}
let mut start = 0;
let frames: Vec<(&[u8], Option<Arrived>)> = self
.ends
.iter()
.zip(&self.expected)
.map(|(&end, &expected)| {
let frame = &self.memory[start..end];
start = end;
(frame, expected)
})
.collect();
let workers = self.cores.min(self.held_bytes() / CHUNK_BYTES_BY_EACH + 1);
let taken = intake.accept_chunks(&frames, workers);
self.memory.clear();
self.ends.clear();
self.expected.clear();
taken
}
#[cfg(test)]
fn memory_held(&self) -> usize {
self.memory.capacity()
}
}
type TakenIn<'a, 's> = (&'a mut Intake<'s>, &'a mut ChunkFrames, Result<()>);
enum Away<'scope, 'a, 's> {
Here(&'a mut Intake<'s>, &'a mut ChunkFrames),
Taking(std::thread::ScopedJoinHandle<'scope, TakenIn<'a, 's>>),
}
pub(crate) struct TakingIn<'scope, 'env, 'a, 's> {
scope: &'scope std::thread::Scope<'scope, 'env>,
held: &'a mut ChunkFrames,
away: Option<Away<'scope, 'a, 's>>,
}
impl<'scope, 'env, 'a: 'scope, 's: 'scope> TakingIn<'scope, 'env, 'a, 's> {
pub(crate) fn new(
scope: &'scope std::thread::Scope<'scope, 'env>,
intake: &'a mut Intake<'s>,
frames: &'a mut [ChunkFrames; 2],
) -> Self {
let [held, spare] = frames;
Self {
scope,
held,
away: Some(Away::Here(intake, spare)),
}
}
pub(crate) fn read_next(&mut self, input: &mut dyn Read, limit: usize) -> Result<Next> {
self.held.read_next(input, limit)
}
pub(crate) fn take_next(&mut self, frame: &mut Vec<u8>) {
self.held.take_next(frame);
}
pub(crate) fn next_is_chunk(&self) -> bool {
self.held.next_is_chunk()
}
pub(crate) fn hold(&mut self, expected: Option<Arrived>) -> Result<()> {
self.held.hold(expected);
self.hand_over_when_full()
}
pub(crate) fn hold_copy(&mut self, frame: &[u8], expected: Option<Arrived>) -> Result<()> {
self.held.hold_copy(frame, expected);
self.hand_over_when_full()
}
fn hand_over_when_full(&mut self) -> Result<()> {
if !self.held.full() {
return Ok(());
}
let (intake, spare) = self.back()?;
let full = std::mem::replace(&mut self.held, spare);
let handle = self.scope.spawn(move || {
let taken = full.take_in(intake);
(intake, full, taken)
});
self.away = Some(Away::Taking(handle));
Ok(())
}
fn back(&mut self) -> Result<(&'a mut Intake<'s>, &'a mut ChunkFrames)> {
match self.away.take() {
Some(Away::Here(intake, spare)) => Ok((intake, spare)),
Some(Away::Taking(handle)) => match handle.join() {
Ok((intake, spare, Ok(()))) => Ok((intake, spare)),
Ok((_, _, Err(error))) => Err(error),
Err(payload) => std::panic::resume_unwind(payload),
},
None => Err(Error::IntakeFailed),
}
}
pub(crate) fn intake(&mut self) -> Result<&mut Intake<'s>> {
let (intake, spare) = self.back()?;
let taken = self.held.take_in(intake);
let away = self.away.insert(Away::Here(intake, spare));
taken?;
match away {
Away::Here(intake, _) => Ok(&mut **intake),
Away::Taking(_) => Err(Error::Invariant {
detail: "an intake that was here is away",
}),
}
}
pub(crate) fn finish(mut self) -> Result<()> {
if self.away.is_none() {
return Ok(());
}
self.intake().map(|_| ())
}
}
pub fn verify(store: &dyn Store, root: &Root) -> Result<Summary> {
verify_with(store, root, VerifyOptions::default())
}
pub fn verify_with(store: &dyn Store, root: &Root, options: VerifyOptions) -> Result<Summary> {
let mode = Mode {
rechunk: options.rechunk,
discard: options.discard,
threads: options.workers,
};
let mut intake = Intake::with_mode(store, *root, mode)?;
intake.rehash_held(options.workers)?;
intake.rechunk_held()?;
intake.finish()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::store::MemoryStore;
#[test]
fn chunk_frames_take_no_more_memory_than_one_batch_needs() {
let store = MemoryStore::new();
let mut intake = Intake::new(&store, Root::of_record(b"no such tree")).unwrap();
let long = vec![FRAME_CHUNK; (1 << 20) + 1];
let short = [FRAME_CHUNK, 1];
let places = 128;
let most = CHUNK_FRAMES_BYTES + MAX_CHUNK_BYTES + 1;
assert!(places * (1 << 20) > most);
let mut frames = ChunkFrames::new();
for place in 0..places {
for _ in 0..place {
frames.hold_copy(&short, None);
}
frames.hold_copy(&long, None);
assert!(frames.take_in(&mut intake).is_err());
}
assert!(
frames.memory_held() <= most,
"{} bytes",
frames.memory_held()
);
let mut frames = ChunkFrames::new();
for place in 0..places {
let mut stream = Vec::new();
for frame in std::iter::repeat_n(&short[..], place).chain([&long[..]]) {
stream.extend_from_slice(&(frame.len() as u32).to_be_bytes());
stream.extend_from_slice(frame);
}
let mut input = stream.as_slice();
while let Next::Frame = frames.read_next(&mut input, long.len()).unwrap() {
assert!(frames.next_is_chunk());
frames.hold(None);
}
assert_eq!(frames.ends.len(), place + 1);
assert!(frames.take_in(&mut intake).is_err());
}
assert!(
frames.memory_held() <= most,
"{} bytes",
frames.memory_held()
);
}
}