use crate::disk::{Found, Held, Refused};
use crate::fastcdc::{chunks_of, FASTCDC_MAX_SIZE};
use crate::format::{
check_name, ChunkRef, Chunking, Entry, ExtraData, FileList, FolderList, Kind, Record, Target,
MAX_FOLDER_DEPTH, TIMESTAMP_KEY,
};
use crate::hash::Root;
use crate::intake::Intake;
use crate::store::{Store, Stored};
use crate::threads::{cores, with_helpers};
use crate::{io_error, Error, Result};
use std::collections::VecDeque;
use std::fs::{self, File};
use std::io::{self, ErrorKind, Read};
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::{Arc, Condvar, Mutex, MutexGuard};
use std::time::{SystemTime, UNIX_EPOCH};
pub(crate) fn read_some(reader: &mut dyn Read, buffer: &mut [u8]) -> io::Result<usize> {
loop {
match reader.read(buffer) {
Err(error) if error.kind() == ErrorKind::Interrupted => {}
other => return other,
}
}
}
const ROOM_ALONE: usize = 2 * FASTCDC_MAX_SIZE;
const ROOM_WITH_HELP: usize = 8 * FASTCDC_MAX_SIZE;
const LOOKED_THROUGH_BY_EACH: usize = 4 << 20;
const KEPT_BY_EACH: usize = 1 << 20;
const FIXED_CHUNKS_IN_A_WINDOW: usize = 1024;
const WINDOWS_BEHIND_TO_GROW: usize = 3;
const WINDOW_START: usize = 64 * 1024;
pub(crate) struct Helpers {
free: AtomicUsize,
}
impl Helpers {
fn new(free: usize) -> Arc<Self> {
Arc::new(Self {
free: AtomicUsize::new(free),
})
}
fn for_threads(threads: usize) -> Arc<Self> {
let threads = match threads {
0 => cores(),
threads => threads,
};
Self::new(threads - 1)
}
fn free(&self) -> usize {
self.free.load(Ordering::Relaxed)
}
fn any(&self) -> bool {
self.free() > 0
}
fn take(&self, most: usize) -> usize {
let mut free = self.free.load(Ordering::Relaxed);
loop {
let taken = free.min(most);
if taken == 0 {
return 0;
}
match self.free.compare_exchange_weak(
free,
free - taken,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return taken,
Err(now) => free = now,
}
}
}
fn give(&self, count: usize) {
self.free.fetch_add(count, Ordering::Relaxed);
}
}
pub struct Builder<'s> {
store: &'s dyn Store,
chunking: Chunking,
windows: Windows,
helpers: Arc<Helpers>,
}
impl<'s> Builder<'s> {
pub fn new(store: &'s dyn Store, chunking: Chunking) -> Self {
Self::sharing(store, chunking, Helpers::for_threads(0))
}
fn sharing(store: &'s dyn Store, chunking: Chunking, helpers: Arc<Helpers>) -> Self {
Self {
store,
chunking,
windows: Windows::default(),
helpers,
}
}
pub fn threads(mut self, threads: usize) -> Self {
self.helpers = Helpers::for_threads(threads);
self
}
pub fn chunking(&self) -> Chunking {
self.chunking
}
pub fn file(&mut self, reader: &mut dyn Read) -> Result<Target> {
self.file_from(|buffer| {
read_some(reader, buffer).map_err(|source| Error::Stream {
operation: "read a file's bytes",
source,
})
})
}
pub fn file_from_bytes(&mut self, bytes: &[u8]) -> Result<Target> {
let chunks = settled(self.chunking, &self.helpers, bytes, true);
let mut items = Vec::with_capacity(chunks.len());
keep_chunks(self.store, &self.helpers, &chunks, &mut items)?;
self.keep_list(items)
}
pub fn file_at(&mut self, path: &Path) -> Result<Target> {
let mut file = File::open(path).map_err(|error| io_error("open", path, error))?;
self.file_from(|buffer| {
read_some(&mut file, buffer).map_err(|error| io_error("read", path, error))
})
}
fn file_from(&mut self, mut read: impl FnMut(&mut [u8]) -> Result<usize>) -> Result<Target> {
let store = self.store;
let chunking = self.chunking;
let helpers = &*self.helpers;
let mut room = window_room(chunking, helpers.any());
let mut behind_in_a_row = 0;
let Windows { current, next } = &mut self.windows;
let mut items = Vec::new();
let (mut filled, mut ended) = fill(current, 0, room, &mut read)?;
while filled > 0 {
let chunks = settled(chunking, helpers, ¤t[..filled], ended);
if chunks.is_empty() {
return Err(Error::Invariant {
detail: "a full window settled no chunk",
});
}
let settled_to: usize = chunks.iter().map(|chunk| chunk.len()).sum();
let tail = ¤t[settled_to..filled];
let most = if ended {
chunks.len() / 2
} else {
settled_to.div_ceil(KEPT_BY_EACH).min(chunks.len())
};
let (kept, refilled) =
keep_chunks_while(store, helpers, most, &chunks, &mut items, |behind| {
carry(tail, next, room)?;
if ended {
return Ok((tail.len(), true));
}
let refilled = fill(next, tail.len(), room, &mut read);
if behind() && helpers.free() >= most {
behind_in_a_row += 1;
if behind_in_a_row >= WINDOWS_BEHIND_TO_GROW {
room = window_room(chunking, true);
}
} else {
behind_in_a_row = 0;
}
refilled
});
kept?;
(filled, ended) = refilled?;
std::mem::swap(current, next);
}
self.keep_list(items)
}
fn keep_list(&self, items: Vec<ChunkRef>) -> Result<Target> {
let list = FileList::new(items)?;
if !self.store.has(Stored::FileList, list.hash())? {
self.store
.put(Stored::FileList, list.hash(), &list.encode())?;
}
Ok(list.target())
}
pub fn folder(&mut self, mut entries: Vec<Entry>) -> Result<Target> {
entries.sort_by(|left, right| left.name().as_bytes().cmp(right.name().as_bytes()));
let list = FolderList::new(entries)?;
if !self.store.has(Stored::FolderList, list.hash())? {
self.store
.put(Stored::FolderList, list.hash(), &list.encode())?;
}
Ok(list.target())
}
pub fn finish(self, top: Target, extra: ExtraData) -> Result<Root> {
let helping = self.helpers.take(usize::MAX);
let totals = Intake::measure(self.store, top, self.chunking, helping + 1);
self.helpers.give(helping);
let record = Record::new(top, totals?, self.chunking, extra)?;
let bytes = record.encode();
let root = Root::of_record(&bytes);
self.store.put(Stored::Record, root.as_hash(), &bytes)?;
Ok(root)
}
}
fn keep_chunk(store: &dyn Store, chunk: &[u8]) -> Result<ChunkRef> {
let item = ChunkRef::of(chunk)?;
if !store.has(Stored::Chunk, &item.hash)? {
store.put(Stored::Chunk, &item.hash, chunk)?;
}
Ok(item)
}
fn keep_chunks(
store: &dyn Store,
helpers: &Helpers,
chunks: &[&[u8]],
items: &mut Vec<ChunkRef>,
) -> Result<()> {
keep_chunks_while(store, helpers, chunks.len() / 2, chunks, items, |_| ()).0
}
fn keep_chunks_while<T>(
store: &dyn Store,
helpers: &Helpers,
most: usize,
chunks: &[&[u8]],
items: &mut Vec<ChunkRef>,
meanwhile: impl FnOnce(&dyn Fn() -> bool) -> T,
) -> (Result<()>, T) {
let helping = helpers.take(most);
let next = AtomicUsize::new(0);
let finished = AtomicUsize::new(0);
let work = || {
let mut kept = Vec::new();
loop {
let index = next.fetch_add(1, Ordering::Relaxed);
let Some(chunk) = chunks.get(index) else {
return kept;
};
let item = keep_chunk(store, chunk);
if item.is_err() {
next.store(chunks.len(), Ordering::Relaxed);
}
kept.push((index, item));
finished.fetch_add(1, Ordering::Relaxed);
}
};
let behind = || helping > 0 && finished.load(Ordering::Relaxed) < chunks.len();
let (kept, done) = with_helpers(helping, &work, || meanwhile(&behind));
let kept: Vec<_> = kept.into_iter().flatten().collect();
helpers.give(helping);
(in_order(kept, chunks.len(), items), done)
}
fn in_order(
kept: Vec<(usize, Result<ChunkRef>)>,
count: usize,
items: &mut Vec<ChunkRef>,
) -> Result<()> {
let mut found: Vec<Option<ChunkRef>> = vec![None; count];
for (index, item) in kept {
found[index] = Some(item?);
}
for item in found {
items.push(item.ok_or(Error::Invariant {
detail: "a chunk was left out of a file",
})?);
}
Ok(())
}
#[derive(Default)]
struct Windows {
current: Vec<u8>,
next: Vec<u8>,
}
fn window_room(chunking: Chunking, help: bool) -> usize {
let room = if help { ROOM_WITH_HELP } else { ROOM_ALONE };
match chunking {
Chunking::FastCdcV1 => (room / 2).max(FASTCDC_MAX_SIZE),
Chunking::Fixed(size) => {
let size = size.get() as usize;
let most = size.saturating_mul(FIXED_CHUNKS_IN_A_WINDOW);
(room / 2).min(most).max(size)
}
}
}
fn settled<'d>(
chunking: Chunking,
helpers: &Helpers,
data: &'d [u8],
ended: bool,
) -> Vec<&'d [u8]> {
match chunking {
Chunking::FastCdcV1 => {
let wanted = (data.len() / LOOKED_THROUGH_BY_EACH).saturating_sub(1);
let helping = helpers.take(wanted);
let chunks = chunks_of(data, ended, helping + 1);
helpers.give(helping);
chunks
}
Chunking::Fixed(size) => {
let size = size.get() as usize;
let mut chunks: Vec<&[u8]> = data.chunks(size).collect();
if !ended && chunks.last().is_some_and(|last| last.len() < size) {
chunks.pop();
}
chunks
}
}
}
fn grow(window: &mut Vec<u8>, least: usize, room: usize) -> Result<()> {
let length = (window.len() * 2).max(WINDOW_START).min(room).max(least);
let more = length.saturating_sub(window.len());
window
.try_reserve_exact(more)
.map_err(|_| Error::AllocationFailed {
resource: "the chunking window",
requested: length as u64,
})?;
window.resize(length, 0);
Ok(())
}
fn fill(
window: &mut Vec<u8>,
mut filled: usize,
room: usize,
read: &mut dyn FnMut(&mut [u8]) -> Result<usize>,
) -> Result<(usize, bool)> {
while filled < room {
if filled == window.len() {
grow(window, filled + 1, room)?;
}
let end = window.len().min(room);
let count = read(&mut window[filled..end])?;
if count > end - filled {
return Err(Error::Invariant {
detail: "a reader gave more bytes than it was asked for",
});
}
if count == 0 {
return Ok((filled, true));
}
filled += count;
}
Ok((filled, false))
}
fn carry(tail: &[u8], window: &mut Vec<u8>, room: usize) -> Result<()> {
if window.len() < tail.len() {
grow(window, tail.len(), room)?;
}
window[..tail.len()].copy_from_slice(tail);
Ok(())
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub enum Links {
#[default]
Refuse,
Skip,
}
#[derive(Clone, Debug, Default)]
pub struct BuildOptions {
chunking: Option<Chunking>,
extra: ExtraData,
timestamp: bool,
workers: usize,
links: Links,
}
impl BuildOptions {
pub fn new() -> Self {
Self::default()
}
pub fn chunking(mut self, chunking: Chunking) -> Self {
self.chunking = Some(chunking);
self
}
pub fn extra(mut self, extra: ExtraData) -> Self {
self.extra = extra;
self
}
pub fn timestamp(mut self, on: bool) -> Self {
self.timestamp = on;
self
}
pub fn workers(mut self, workers: usize) -> Self {
self.workers = workers;
self
}
pub fn links(mut self, links: Links) -> Self {
self.links = links;
self
}
}
pub type EntryExtra<'a> = dyn Fn(&Path, &str, Kind) -> Result<ExtraData> + Sync + 'a;
pub fn build(store: &dyn Store, path: impl AsRef<Path>, options: &BuildOptions) -> Result<Root> {
build_tree(store, path.as_ref(), options, None)
}
pub fn build_with(
store: &dyn Store,
path: impl AsRef<Path>,
options: &BuildOptions,
entry_extra: &EntryExtra<'_>,
) -> Result<Root> {
build_tree(store, path.as_ref(), options, Some(entry_extra))
}
fn build_tree(
store: &dyn Store,
path: &Path,
options: &BuildOptions,
entry_extra: Option<&EntryExtra<'_>>,
) -> Result<Root> {
let chunking = options.chunking.unwrap_or(Chunking::FastCdcV1);
let mut extra = options.extra.clone();
if options.timestamp {
extra.insert(TIMESTAMP_KEY, timestamp(SystemTime::now())?)?;
}
let metadata = fs::metadata(path).map_err(|error| io_error("look at", path, error))?;
let mut builder = Builder::new(store, chunking).threads(options.workers);
if !metadata.is_dir() {
let top = builder.file_at(path)?;
return builder.finish(top, extra);
}
let top = Held::open(path).map_err(|error| io_error("open", path, error))?;
let (folders, file_targets) =
walk_and_chunk(store, chunking, &top, options.links, options.workers)?;
let mut folder_targets: Vec<Option<Target>> = vec![None; folders.len()];
for index in (0..folders.len()).rev() {
let mut entries = Vec::with_capacity(folders[index].children.len());
for child in &folders[index].children {
let target = match child.kind {
Kind::File => *file_targets.get(child.index).ok_or(Error::Invariant {
detail: "a file was left out of the build",
})?,
Kind::Folder => folder_targets[child.index].ok_or(Error::Invariant {
detail: "a folder was made before a folder inside it",
})?,
};
let extra = match entry_extra {
Some(entry_extra) => match child.kind {
Kind::File => entry_extra(
&folders[index].path.join(&child.name),
&child.name,
child.kind,
)?,
Kind::Folder => {
entry_extra(&folders[child.index].path, &child.name, child.kind)?
}
},
None => ExtraData::new(),
};
entries.push(Entry::new(child.name.as_str(), target, extra)?);
}
folder_targets[index] = Some(builder.folder(entries)?);
}
let top = folder_targets[0].ok_or(Error::Invariant {
detail: "the top folder was not made",
})?;
builder.finish(top, extra)
}
struct Folder {
path: PathBuf,
children: Vec<Child>,
}
struct Child {
name: String,
kind: Kind,
index: usize,
}
type OnTheWay = (Arc<Held>, Vec<(String, usize)>);
const FOLDERS_AHEAD: usize = 16;
struct Batch {
folder: Arc<Held>,
files: Vec<(usize, String)>,
taken: AtomicUsize,
}
impl Batch {
fn take(&self) -> Option<&(usize, String)> {
self.files.get(self.taken.fetch_add(1, Ordering::Relaxed))
}
fn all_taken(&self) -> bool {
self.taken.load(Ordering::Relaxed) >= self.files.len()
}
}
fn changed(path: &Path, refused: Refused) -> Error {
let what = match refused {
Refused::Io(error) => return io_error("open", path, error),
Refused::Link => "a link now, where a file or a folder was when the build began",
Refused::Other => "something else now than it was when the build began",
};
Error::UnsupportedEntry {
path: path.to_path_buf(),
what,
}
}
fn chunk_file_in(
builder: &mut Builder<'_>,
folder: &Held,
name: &str,
stop: Option<&AtomicBool>,
) -> Result<Target> {
let path = || folder.path().join(name);
let mut file = folder
.open_file(name)
.map_err(|refused| changed(&path(), refused))?;
builder.file_from(|buffer| {
if stop.is_some_and(|stop| stop.load(Ordering::Relaxed)) {
return Err(STOPPED);
}
read_some(&mut file, buffer).map_err(|error| io_error("read", &path(), error))
})
}
struct Walk<'a> {
links: Links,
folders: Vec<Folder>,
files: usize,
on_files: &'a mut dyn FnMut(Batch) -> Result<()>,
}
impl Walk<'_> {
fn read(
&mut self,
held: &Arc<Held>,
index: usize,
depth: usize,
) -> Result<Vec<(String, usize)>> {
let folder_path = held.path().to_path_buf();
let listed = held
.list()
.map_err(|error| io_error("list", &folder_path, error))?;
let mut children = Vec::with_capacity(listed.len());
let mut inside = Vec::new();
let mut files = Vec::new();
for (name, found) in listed {
let name = name.into_string().map_err(|name| Error::NonUtf8FileName {
path: folder_path.join(name),
})?;
check_name(&name)?;
match found {
Found::Folder => {
if depth >= MAX_FOLDER_DEPTH {
return Err(Error::TooDeep {
limit: MAX_FOLDER_DEPTH,
});
}
let below = self.folders.len();
children.push(Child {
name: name.clone(),
kind: Kind::Folder,
index: below,
});
self.folders.push(Folder {
path: folder_path.join(&name),
children: Vec::new(),
});
inside.push((name, below));
}
Found::File => {
children.push(Child {
name: name.clone(),
kind: Kind::File,
index: self.files,
});
files.push((self.files, name));
self.files += 1;
}
Found::Link | Found::Other => {
if self.links == Links::Refuse {
return Err(Error::UnsupportedEntry {
path: folder_path.join(&name),
what: if found == Found::Link {
"a link"
} else {
"a special file"
},
});
}
}
}
}
children.sort_by(|left, right| left.name.as_bytes().cmp(right.name.as_bytes()));
self.folders[index].children = children;
if !files.is_empty() {
(self.on_files)(Batch {
folder: Arc::clone(held),
files,
taken: AtomicUsize::new(0),
})?;
}
Ok(inside)
}
}
fn walk(
top: &Arc<Held>,
links: Links,
on_files: &mut dyn FnMut(Batch) -> Result<()>,
) -> Result<(Vec<Folder>, usize)> {
let mut walk = Walk {
links,
folders: vec![Folder {
path: top.path().to_path_buf(),
children: Vec::new(),
}],
files: 0,
on_files,
};
let mut way: Vec<OnTheWay> = Vec::new();
let mut next = Some((Arc::clone(top), 0_usize));
loop {
if let Some((held, index)) = next.take() {
let inside = walk.read(&held, index, way.len() + 1)?;
way.push((held, inside));
}
let Some((held, inside)) = way.last_mut() else {
break;
};
match inside.pop() {
Some((name, index)) => {
let below = held
.open_folder(&name)
.map_err(|refused| changed(&walk.folders[index].path, refused))?;
next = Some((below, index));
}
None => {
way.pop();
}
}
}
Ok((walk.folders, walk.files))
}
const STOPPED_DETAIL: &str = "the build was stopped";
const STOPPED: Error = Error::Invariant {
detail: STOPPED_DETAIL,
};
fn is_stopped(error: &Error) -> bool {
matches!(error, Error::Invariant { detail } if *detail == STOPPED_DETAIL)
}
fn lock<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
mutex
.lock()
.unwrap_or_else(|poisoned| poisoned.into_inner())
}
fn wait<'a, T>(told: &Condvar, guard: MutexGuard<'a, T>) -> MutexGuard<'a, T> {
told.wait(guard)
.unwrap_or_else(|poisoned| poisoned.into_inner())
}
struct Waiting {
state: Mutex<WaitingState>,
more: Condvar,
room: Condvar,
failed: AtomicBool,
}
struct WaitingState {
batches: VecDeque<Arc<Batch>>,
over: bool,
}
impl Waiting {
fn new() -> Self {
Self {
state: Mutex::new(WaitingState {
batches: VecDeque::new(),
over: false,
}),
more: Condvar::new(),
room: Condvar::new(),
failed: AtomicBool::new(false),
}
}
fn has_failed(&self) -> bool {
self.failed.load(Ordering::Relaxed)
}
fn add(&self, batch: Batch) -> Result<()> {
let one_file = batch.files.len() == 1;
let mut state = lock(&self.state);
loop {
if self.has_failed() {
return Err(STOPPED);
}
if state.batches.len() < FOLDERS_AHEAD {
break;
}
state = wait(&self.room, state);
}
state.batches.push_back(Arc::new(batch));
drop(state);
if one_file {
self.more.notify_one();
} else {
self.more.notify_all();
}
Ok(())
}
fn next(&self) -> Option<Arc<Batch>> {
let mut state = lock(&self.state);
loop {
if self.has_failed() {
return None;
}
while state.batches.front().is_some_and(|batch| batch.all_taken()) {
state.batches.pop_front();
self.room.notify_one();
}
if let Some(batch) = state.batches.front() {
return Some(Arc::clone(batch));
}
if state.over {
return None;
}
state = wait(&self.more, state);
}
}
fn fail(&self) {
let state = lock(&self.state);
self.failed.store(true, Ordering::Relaxed);
drop(state);
self.more.notify_all();
self.room.notify_all();
}
fn end(&self) {
lock(&self.state).over = true;
self.more.notify_all();
}
}
struct Working<'a>(&'a Waiting);
impl Drop for Working<'_> {
fn drop(&mut self) {
if std::thread::panicking() {
self.0.fail();
}
}
}
fn walk_and_chunk(
store: &dyn Store,
chunking: Chunking,
top: &Arc<Held>,
links: Links,
threads: usize,
) -> Result<(Vec<Folder>, Vec<Target>)> {
let threads = match threads {
0 => cores(),
threads => threads,
};
let helpers = Helpers::new(0);
if threads == 1 {
let mut builder = Builder::sharing(store, chunking, helpers);
let mut targets = Vec::new();
let (folders, _) = walk(top, links, &mut |batch| {
for (index, name) in &batch.files {
if *index != targets.len() {
return Err(Error::Invariant {
detail: "a file was chunked out of its turn",
});
}
targets.push(chunk_file_in(&mut builder, &batch.folder, name, None)?);
}
Ok(())
})?;
return Ok((folders, targets));
}
let waiting = Waiting::new();
let work = || -> Result<Vec<(usize, Target)>> {
let _working = Working(&waiting);
let mut builder = Builder::sharing(store, chunking, Arc::clone(&helpers));
let mut done = Vec::new();
let mut first_error = None;
while let Some(batch) = waiting.next() {
while let Some((index, name)) = batch.take() {
if waiting.has_failed() {
break;
}
let stop = Some(&waiting.failed);
match chunk_file_in(&mut builder, &batch.folder, name, stop) {
Ok(target) => done.push((*index, target)),
Err(error) => {
first_error.get_or_insert(error);
waiting.fail();
}
}
}
}
helpers.give(1);
match first_error {
Some(error) => Err(error),
None => Ok(done),
}
};
let (walked, chunked) = std::thread::scope(|scope| {
let _working = Working(&waiting);
let handles: Vec<_> = (0..threads).map(|_| scope.spawn(work)).collect();
let walked = walk(top, links, &mut |batch| waiting.add(batch));
if walked.is_err() {
waiting.fail();
}
waiting.end();
let chunked: Vec<Result<Vec<(usize, Target)>>> = handles
.into_iter()
.map(|handle| match handle.join() {
Ok(result) => result,
Err(payload) => std::panic::resume_unwind(payload),
})
.collect();
(walked, chunked)
});
let mut done = Vec::new();
let mut stopped = false;
for result in chunked {
match result {
Ok(part) => done.extend(part),
Err(error) if is_stopped(&error) => stopped = true,
Err(error) => return Err(error),
}
}
let (folders, files) = walked?;
if stopped {
return Err(STOPPED);
}
let mut targets: Vec<Option<Target>> = vec![None; files];
for (index, target) in done {
targets[index] = Some(target);
}
let targets = targets
.into_iter()
.map(|target| {
target.ok_or(Error::Invariant {
detail: "a file was left out of the build",
})
})
.collect::<Result<Vec<Target>>>()?;
Ok((folders, targets))
}
fn timestamp(time: SystemTime) -> Result<String> {
let elapsed = time
.duration_since(UNIX_EPOCH)
.map_err(|_| Error::SystemTimeBeforeUnixEpoch)?;
let seconds =
i64::try_from(elapsed.as_secs()).map_err(|_| Error::SizeOverflow { field: "timestamp" })?;
Ok(format_epoch_seconds(seconds))
}
fn format_epoch_seconds(seconds: i64) -> String {
let days = seconds.div_euclid(86_400);
let seconds_of_day = seconds.rem_euclid(86_400);
let shifted_days = days + 719_468;
let era = shifted_days.div_euclid(146_097);
let day_of_era = shifted_days - era * 146_097;
let year_of_era =
(day_of_era - day_of_era / 1_460 + day_of_era / 36_524 - day_of_era / 146_096) / 365;
let mut year = year_of_era + era * 400;
let day_of_year = day_of_era - (365 * year_of_era + year_of_era / 4 - year_of_era / 100);
let month_prime = (5 * day_of_year + 2) / 153;
let day = day_of_year - (153 * month_prime + 2) / 5 + 1;
let month = month_prime + if month_prime < 10 { 3 } else { -9 };
if month <= 2 {
year += 1;
}
let hour = seconds_of_day / 3_600;
let minute = seconds_of_day % 3_600 / 60;
let second = seconds_of_day % 60;
format!("{year:04}-{month:02}-{day:02}T{hour:02}:{minute:02}:{second:02}Z")
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Hash, MemoryStore};
use std::time::{Duration, Instant};
const CHUNK: usize = 4 << 20;
const ALONE: usize = ROOM_ALONE / 2;
struct Slow(MemoryStore);
impl Store for Slow {
fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
std::thread::sleep(Duration::from_millis(100));
self.0.put(kind, hash, bytes)
}
fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
self.0.get(kind, hash)
}
fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
self.0.remove(kind, hash)
}
}
struct Counted {
inner: MemoryStore,
chunks: AtomicUsize,
}
impl Store for Counted {
fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
self.inner.put(kind, hash, bytes)?;
if kind == Stored::Chunk {
self.chunks.fetch_add(1, Ordering::SeqCst);
}
Ok(())
}
fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
self.inner.get(kind, hash)
}
fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
self.inner.remove(kind, hash)
}
}
struct Taking {
inner: MemoryStore,
helpers: Arc<Helpers>,
}
impl Store for Taking {
fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
self.helpers.take(usize::MAX);
self.inner.put(kind, hash, bytes)
}
fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
self.inner.get(kind, hash)
}
fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
self.inner.remove(kind, hash)
}
}
fn read_through(
store: &dyn Store,
helpers: Arc<Helpers>,
chunks: usize,
mut asked: impl FnMut(usize, usize),
) {
let chunking = Chunking::fixed(CHUNK as u32).unwrap();
let mut builder = Builder::sharing(store, chunking, helpers);
let longest = window_room(chunking, true);
builder.windows.current.resize(longest, 0);
builder.windows.next.resize(longest, 0);
let length = chunks * CHUNK;
let mut at = 0;
builder
.file_from(|buffer| {
asked(at, buffer.len());
let count = buffer.len().min(length - at);
let mut done = 0;
while done < count {
let chunk = (at + done) / CHUNK;
let end = ((chunk + 1) * CHUNK - at).min(count);
buffer[done..end].fill(chunk as u8);
done = end;
}
at += count;
Ok(count)
})
.unwrap();
}
#[test]
fn a_file_whose_chunks_are_kept_slowly_is_read_in_longer_windows_once_helpers_are_free() {
let store = Slow(MemoryStore::new());
let helpers = Helpers::new(0);
let free = Arc::clone(&helpers);
let mut longest = 0;
read_through(&store, helpers, 12, |at, length| {
if at == 0 {
free.give(6);
}
longest = longest.max(length);
});
assert!(
longest > ALONE,
"the longest read asked for {longest} bytes"
);
}
#[test]
fn a_file_whose_chunks_are_kept_as_fast_as_it_is_read_keeps_its_short_windows() {
let store = Counted {
inner: MemoryStore::new(),
chunks: AtomicUsize::new(0),
};
let helpers = Helpers::new(0);
let free = Arc::clone(&helpers);
let mut longest = 0;
read_through(&store, helpers, 12, |at, length| {
if at == 0 {
free.give(6);
}
let waited = Instant::now();
while store.chunks.load(Ordering::SeqCst) < at / CHUNK
&& waited.elapsed() < Duration::from_secs(10)
{
std::thread::sleep(Duration::from_millis(1));
}
std::thread::sleep(Duration::from_millis(20));
longest = longest.max(length);
});
assert!(longest <= ALONE, "a read asked for {longest} bytes");
}
#[test]
fn helpers_that_are_free_for_a_moment_do_not_grow_a_window() {
let store = Slow(MemoryStore::new());
let helpers = Helpers::new(0);
let free = Arc::clone(&helpers);
let mut held = 0;
let mut longest_early = 0;
let mut longest = 0;
let early = (2 * WINDOWS_BEHIND_TO_GROW + 1) * ALONE;
read_through(&store, helpers, 20, |at, length| {
let window = at / ALONE;
if at == 0 {
free.give(6);
} else if window == WINDOWS_BEHIND_TO_GROW {
held += free.take(usize::MAX);
} else if window == WINDOWS_BEHIND_TO_GROW + 1 {
free.give(std::mem::take(&mut held));
}
if at < early {
longest_early = longest_early.max(length);
}
longest = longest.max(length);
});
assert!(
longest_early <= ALONE,
"a read before byte {early} asked for {longest_early} bytes"
);
assert!(longest > ALONE, "the windows never grew");
}
#[test]
fn a_window_that_too_few_helpers_could_share_keeps_its_length() {
let store = Slow(MemoryStore::new());
let helpers = Helpers::new(0);
let free = Arc::clone(&helpers);
let mut longest = 0;
read_through(&store, helpers, 12, |at, length| {
if at == 0 {
free.give(3);
}
longest = longest.max(length);
});
assert!(longest <= ALONE, "a read asked for {longest} bytes");
}
#[test]
fn chunks_that_no_helper_keeps_do_not_count_as_behind() {
let helpers = Helpers::new(0);
let store = Taking {
inner: MemoryStore::new(),
helpers: Arc::clone(&helpers),
};
let free = Arc::clone(&helpers);
let mut longest = 0;
read_through(&store, helpers, 12, |at, length| {
if at > 0 {
free.give(6);
}
longest = longest.max(length);
});
assert!(longest <= ALONE, "a read asked for {longest} bytes");
}
#[test]
fn the_time_is_written_in_utc_to_the_second() {
assert_eq!(format_epoch_seconds(0), "1970-01-01T00:00:00Z");
assert_eq!(format_epoch_seconds(951_782_400), "2000-02-29T00:00:00Z");
assert_eq!(format_epoch_seconds(1_794_472_200), "2026-11-12T08:30:00Z");
assert_eq!(format_epoch_seconds(4_102_444_799), "2099-12-31T23:59:59Z");
assert_eq!(format_epoch_seconds(-1), "1969-12-31T23:59:59Z");
}
}