use crate::fat::geometry::{
FAT32_AUTO_THRESHOLD_BYTES, FatLayout, FatTypeRequest, GeometryError, PlanRequest, plan_layout,
};
use crate::fat::materialize::{FormatError, FormatOptions};
use crate::fat::model::{ModelError, PlacedTree};
use crate::sizing::{Probe, Slack};
#[derive(Debug)]
pub(crate) struct Fitted {
pub(crate) layout: FatLayout,
pub(crate) used_clusters: u32,
pub(crate) next_free: u32,
}
type Band = (u64, u64);
const MAX_SECTORS: u64 = u32::MAX as u64;
fn bands(request: &PlanRequest, floor: u64) -> Vec<Band> {
let sector = u64::from(request.bytes_per_sector);
let threshold = FAT32_AUTO_THRESHOLD_BYTES.div_ceil(sector);
let whole: Band = (floor, MAX_SECTORS);
match request.fat_type {
FatTypeRequest::Auto if threshold > floor => {
vec![(floor, threshold - 1), (threshold, MAX_SECTORS)]
}
_ => vec![whole],
}
}
fn classify(e: GeometryError) -> Probe<FatLayout, FormatError> {
match e {
GeometryError::ClustersAboveMaximum { .. } | GeometryError::VolumeTooLarge { .. } => {
Probe::Exhausted(FormatError::Geometry(e))
}
GeometryError::SectorSizeUnsupported { .. }
| GeometryError::FatCountUnsupported { .. }
| GeometryError::ClusterSizeUnsupported { .. }
| GeometryError::ClusterTooLarge { .. } => Probe::Impossible(FormatError::Geometry(e)),
_ => Probe::TooSmall(FormatError::Geometry(e)),
}
}
fn probe(
tree: &mut PlacedTree,
options: &FormatOptions,
slack: Slack,
sectors: u64,
) -> Probe<FatLayout, FormatError> {
let sector = u64::from(options.plan.bytes_per_sector);
let mut request = options.plan;
request.volume_bytes = sectors.saturating_mul(sector);
let layout = match plan_layout(&request) {
Ok(layout) => layout,
Err(e) => return classify(e),
};
let (used_clusters, _) = match tree.allocate(&layout, &options.model_config()) {
Ok(counts) => counts,
Err(e @ (ModelError::VolumeFull { .. } | ModelError::RootDirectoryFull { .. })) => {
return Probe::TooSmall(FormatError::Model(e));
}
Err(e) => return Probe::Impossible(FormatError::Model(e)),
};
let free = u64::from(layout.clusters - used_clusters);
if free
< slack.required_free(
u64::from(layout.clusters),
u64::from(layout.bytes_per_cluster()),
)
{
return Probe::Tight;
}
Probe::Fits(layout)
}
pub(crate) fn search(
tree: &mut PlacedTree,
options: &FormatOptions,
slack: Slack,
) -> Result<Fitted, FormatError> {
if let Some(hundredths) = slack.share_over_limit() {
return Err(FormatError::SlackShareTooLarge {
hundredths,
limit: Slack::MAX_SHARE,
});
}
options.plan.validate()?;
let sector = u64::from(options.plan.bytes_per_sector);
let floor = content_floor(tree, options).max(1);
let mut last: Option<FormatError> = None;
for (lo, hi) in bands(&options.plan, floor) {
match crate::sizing::bracket(lo, hi, |sectors| probe(tree, options, slack, sectors)) {
Ok((_, layout)) => return settle(tree, options, layout),
Err(Some(e @ FormatError::Model(ModelError::VolumeFull { .. }))) => last = Some(e),
Err(Some(e @ (FormatError::Geometry(_) | FormatError::Model(_)))) => last = Some(e),
Err(Some(e)) => return Err(e),
Err(None) => {}
}
}
Err(last.unwrap_or(FormatError::DoesNotFit {
ceiling: MAX_SECTORS.saturating_mul(sector),
}))
}
fn settle(
tree: &mut PlacedTree,
options: &FormatOptions,
layout: FatLayout,
) -> Result<Fitted, FormatError> {
let (used_clusters, next_free) = tree.allocate(&layout, &options.model_config())?;
Ok(Fitted {
layout,
used_clusters,
next_free,
})
}
fn content_floor(tree: &PlacedTree, options: &FormatOptions) -> u64 {
let sector = u64::from(options.plan.bytes_per_sector);
tree.content_sectors(sector)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::fat::geometry::{ClusterSize, FatType};
use crate::fat::materialize::FormatPlan;
use crate::fat::model::place_tree;
use crate::source::{Metadata, Source, TreeBuilder};
use crate::time::Timestamp;
const TIME: Timestamp = Timestamp::from_secs(1_426_325_212);
fn opts() -> FormatOptions {
FormatOptions::new(0x1234_5678, TIME).accept_all_loss()
}
fn tree(files: usize, each: usize) -> TreeBuilder {
let mut b = TreeBuilder::new().directory(b"/d".to_vec(), Metadata::new(0o755, TIME));
for i in 0..files {
b = b.file(
format!("/d/f{i:04}").into_bytes(),
vec![0xAB; each],
Metadata::new(0o644, TIME),
);
}
b
}
fn fit(
source: impl Source,
options: FormatOptions,
slack: Slack,
) -> Result<Fitted, FormatError> {
let mut placed = place_tree(source.into_entries(), &options.model_config()).expect("place");
search(&mut placed, &options, slack)
}
#[test]
fn a_fitted_volume_formats_and_one_sector_less_does_not() {
for request in [
FatTypeRequest::Auto,
FatTypeRequest::Exactly(FatType::Fat12),
FatTypeRequest::Exactly(FatType::Fat16),
FatTypeRequest::Exactly(FatType::Fat32),
] {
let options = opts().plan(PlanRequest::new(0).fat_type(request));
let fitted = fit(tree(40, 3_000), options, Slack::None)
.unwrap_or_else(|e| panic!("{request:?} does not fit: {e}"));
let sector = u64::from(fitted.layout.bytes_per_sector);
let bytes = u64::from(fitted.layout.total_sectors) * sector;
FormatPlan::new(tree(40, 3_000), bytes, options)
.unwrap_or_else(|e| panic!("{request:?} at the fitted size: {e}"));
assert!(
FormatPlan::new(tree(40, 3_000), bytes - sector, options).is_err(),
"{request:?}: one sector below the fitted size must not hold the tree"
);
}
}
#[test]
fn the_fitted_volume_is_exactly_the_filesystem() {
for files in [1usize, 7, 40, 200] {
let fitted = fit(tree(files, 5_000), opts(), Slack::None).expect("fits");
let l = &fitted.layout;
assert_eq!(
u64::from(l.total_sectors) - u64::from(l.first_data_sector),
u64::from(l.clusters) * u64::from(l.sectors_per_cluster),
"a fitted volume has no tail past its last cluster ({files} files)"
);
}
}
#[test]
fn a_pinned_cluster_size_with_an_auto_type_finds_the_lower_band() {
let dir = tempfile::tempdir().expect("temp dir");
let path = dir.path().join("bulk");
std::fs::write(&path, b"x").expect("write");
let file = std::sync::Arc::new(std::fs::File::open(&path).expect("open"));
let src = TreeBuilder::new().file(
b"/bulk".to_vec(),
crate::source::FileContent::Range(crate::source::FileRange::new(
file,
&path,
0,
300 << 20,
)),
Metadata::new(0o644, TIME),
);
let options = opts().plan(
PlanRequest::new(0)
.cluster_size(ClusterSize::Sectors(64))
.fat_type(FatTypeRequest::Auto),
);
let fitted = fit(src, options, Slack::None).expect("fits");
let bytes =
u64::from(fitted.layout.total_sectors) * u64::from(fitted.layout.bytes_per_sector);
assert!(
bytes < FAT32_AUTO_THRESHOLD_BYTES,
"the answer is in the lower band rather than the bottom of the upper one: \
{bytes} bytes, {:?}",
fitted.layout.fat_type
);
assert_ne!(fitted.layout.fat_type, FatType::Fat32);
}
#[test]
fn the_tree_ends_the_search_allocated_against_the_layout_the_search_returns() {
let options =
opts().plan(PlanRequest::new(0).fat_type(FatTypeRequest::Exactly(FatType::Fat12)));
let place =
|| place_tree(tree(64, 9_000).into_entries(), &options.model_config()).expect("place");
let mut placed = place();
let fitted = search(&mut placed, &options, Slack::None).expect("fits");
let want = {
let mut other = place();
let f = search(&mut other, &options, Slack::None).expect("fits");
other.finish(f.used_clusters, f.next_free).chain_ends()
};
let bytes =
u64::from(fitted.layout.total_sectors) * u64::from(fitted.layout.bytes_per_sector) * 2;
let request = PlanRequest::new(bytes)
.fat_type(FatTypeRequest::Exactly(FatType::Fat12))
.cluster_size(ClusterSize::Sectors(fitted.layout.sectors_per_cluster * 2));
let other = plan_layout(&request).expect("the doubled cluster plans");
assert_ne!(
other.sectors_per_cluster, fitted.layout.sectors_per_cluster,
"the second geometry has to differ, or it proves nothing"
);
placed
.allocate(&other, &options.model_config())
.expect("allocating against the other geometry");
let repaired = settle(&mut placed, &options, fitted.layout).expect("settle");
assert_eq!(repaired.used_clusters, fitted.used_clusters);
assert_eq!(repaired.next_free, fitted.next_free);
assert_eq!(
placed
.finish(repaired.used_clusters, repaired.next_free)
.chain_ends(),
want,
"the tree is the winner's again"
);
}
#[test]
fn a_fitted_volume_written_out_reads_back_across_a_cluster_size_transition() {
for each in [8_150usize, 8_180, 8_210, 8_240] {
let files = 1_024;
let options =
opts().plan(PlanRequest::new(0).fat_type(FatTypeRequest::Exactly(FatType::Fat12)));
let source = || {
let mut b =
TreeBuilder::new().directory(b"/d".to_vec(), Metadata::new(0o755, TIME));
for i in 0..files {
b = b.file(
format!("/d/f{i:04}").into_bytes(),
vec![(i % 251) as u8; each],
Metadata::new(0o644, TIME),
);
}
b
};
let plan = FormatPlan::fit(source(), options, Slack::None)
.unwrap_or_else(|e| panic!("{each}-byte files do not fit: {e}"));
let mut image = std::io::Cursor::new(vec![0u8; plan.volume_bytes() as usize]);
plan.write_to(&mut image)
.unwrap_or_else(|e| panic!("{each}: write: {e}"));
let mut reader = crate::fat::Reader::open(std::io::Cursor::new(image.into_inner()))
.unwrap_or_else(|e| panic!("{each}: open: {e}"));
for i in [0usize, 1, files / 2, files - 1] {
let path = format!("/d/f{i:04}").into_bytes();
let node = reader
.lookup(&path)
.unwrap_or_else(|e| panic!("{each}: lookup f{i:04}: {e}"));
let data = reader
.read_data(&node)
.unwrap_or_else(|e| panic!("{each}: read f{i:04}: {e}"));
assert_eq!(data.len(), each, "{each}: f{i:04} is the wrong length");
assert!(
data.iter().all(|&b| b == (i % 251) as u8),
"{each}: f{i:04} holds another file's bytes"
);
}
}
}
#[test]
fn slack_is_free_clusters_the_finished_volume_has() {
let want = Slack::Share(2500);
let fitted = fit(tree(30, 4_000), opts(), want).expect("fits");
let free = u64::from(fitted.layout.clusters - fitted.used_clusters);
assert!(
free >= Slack::share_of(u64::from(fitted.layout.clusters), 2500),
"a quarter of the cluster heap is free: {free} of {}",
fitted.layout.clusters
);
let tight = fit(tree(30, 4_000), opts(), Slack::None).expect("fits");
assert!(
tight.layout.clusters < fitted.layout.clusters,
"asking for room produces a larger volume than not asking"
);
}
#[test]
fn a_type_the_tree_outgrows_is_refused_by_name() {
let fat12 =
|| opts().plan(PlanRequest::new(0).fat_type(FatTypeRequest::Exactly(FatType::Fat12)));
let err = fit(tree(500, 400_000), fat12(), Slack::None).expect_err("no FAT12 holds it");
assert!(
matches!(
err,
FormatError::Geometry(GeometryError::ClustersAboveMaximum { .. })
),
"{err}"
);
let fitted = fit(tree(500, 200_000), fat12(), Slack::None)
.expect("a hundred megabytes fits FAT12 at 32 KiB clusters");
assert_eq!(fitted.layout.fat_type, FatType::Fat12);
assert!(
fitted.layout.clusters <= 4084,
"{} clusters is past FAT12",
fitted.layout.clusters
);
}
#[test]
fn a_geometry_that_cannot_be_realized_fails_at_once() {
let options = opts().plan(PlanRequest::new(0).bytes_per_sector(3000));
let err = fit(tree(4, 100), options, Slack::None).expect_err("3000 is not a sector size");
assert!(
matches!(
err,
FormatError::Geometry(GeometryError::SectorSizeUnsupported { .. })
),
"{err}"
);
}
#[test]
fn a_share_past_the_limit_is_refused_before_any_search() {
let err = fit(tree(2, 100), opts(), Slack::Share(9001)).expect_err("past the limit");
assert!(
matches!(err, FormatError::SlackShareTooLarge { .. }),
"{err}"
);
}
#[test]
fn a_probe_sizes_a_file_without_reading_it() {
let dir = tempfile::tempdir().expect("temp dir");
let path = dir.path().join("short");
std::fs::write(&path, b"tiny").expect("write");
let file = std::sync::Arc::new(std::fs::File::open(&path).expect("open"));
let src = TreeBuilder::new().file(
b"/claims-more".to_vec(),
crate::source::FileContent::Range(crate::source::FileRange::new(
file, &path, 0, 400_000,
)),
Metadata::new(0o644, TIME),
);
let fitted = fit(src, opts(), Slack::None).expect("a declared length is enough to size it");
assert!(
u64::from(fitted.layout.clusters) * u64::from(fitted.layout.bytes_per_cluster())
>= 400_000,
"the volume was sized for the length the range declared"
);
}
#[test]
fn a_fitted_plan_writes_the_volume_it_planned() {
let plan = FormatPlan::fit(tree(25, 6_000), opts(), Slack::Bytes(1 << 20)).expect("fit");
assert_eq!(
plan.volume_bytes(),
plan.layout().total_bytes(),
"a fitted volume is exactly its filesystem"
);
let mut out = std::io::Cursor::new(Vec::new());
let written = plan.write_to(&mut out).expect("write");
assert_eq!(out.into_inner().len() as u64, plan.volume_bytes());
assert_eq!(written.clusters, plan.layout().clusters);
}
}