use crate::exfat::geometry::{ClusterSize, ExfatLayout, GeometryError, PlanRequest, plan_layout};
use crate::exfat::materialize::{FormatError, FormatOptions};
use crate::exfat::model::{ModelError, PlacedTree};
use crate::sizing::{Probe, Slack};
type Band = (u64, u64);
const CLUSTER_STEPS: [u64; 3] = [7 << 20, (256 << 20) + 1, (32 << 30) + 1];
fn bands(request: &PlanRequest, floor: u64) -> Vec<Band> {
let sector = u64::from(request.bytes_per_sector);
let ceiling = u64::MAX / sector;
if !matches!(request.cluster_size, ClusterSize::Auto) {
return vec![(floor, ceiling)];
}
let mut bands = Vec::new();
let mut low = floor;
for step in CLUSTER_STEPS {
let first = step.div_ceil(sector);
if first > low {
bands.push((low, first - 1));
low = first;
}
}
bands.push((low, ceiling));
bands
}
fn classify(e: GeometryError) -> Probe<ExfatLayout, FormatError> {
match e {
GeometryError::TooManyClusters { .. } => Probe::Exhausted(FormatError::Geometry(e)),
GeometryError::SectorSizeUnsupported { .. }
| GeometryError::ClusterSizeUnsupported { .. }
| GeometryError::ClusterTooLarge { .. }
| GeometryError::BoundaryAlignUnsupported { .. } => {
Probe::Impossible(FormatError::Geometry(e))
}
_ => Probe::TooSmall(FormatError::Geometry(e)),
}
}
fn probe(
tree: &mut PlacedTree,
options: &FormatOptions,
slack: Slack,
sectors: u64,
) -> Probe<ExfatLayout, FormatError> {
let mut request = options.plan;
request.volume_bytes = sectors.saturating_mul(u64::from(request.bytes_per_sector));
let layout = match plan_layout(&request) {
Ok(layout) => layout,
Err(e) => return classify(e),
};
let used = match tree.allocate(&layout) {
Ok(used) => used,
Err(e @ ModelError::VolumeFull { .. }) => return Probe::TooSmall(FormatError::Model(e)),
Err(e) => return Probe::Impossible(FormatError::Model(e)),
};
let free = u64::from(layout.cluster_count - used);
let required = slack.required_free(
u64::from(layout.cluster_count),
u64::from(layout.bytes_per_cluster),
);
if free < required {
Probe::Tight
} else {
Probe::Fits(layout)
}
}
#[derive(Debug)]
pub(crate) struct Fitted {
pub(crate) layout: ExfatLayout,
pub(crate) used_clusters: u32,
}
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,
});
}
let sector = u64::from(options.plan.bytes_per_sector);
let floor = tree.content_sectors(sector).max(1);
let mut refusal = None;
for (low, high) in bands(&options.plan, floor) {
match crate::sizing::bracket(low, high, |sectors| probe(tree, options, slack, sectors)) {
Ok((_, layout)) => {
let used_clusters = tree.allocate(&layout)?;
return Ok(Fitted {
layout,
used_clusters,
});
}
Err(Some(FormatError::Model(e))) if !matches!(e, ModelError::VolumeFull { .. }) => {
return Err(FormatError::Model(e));
}
Err(Some(e)) => refusal = Some(e),
Err(None) => {}
}
}
Err(refusal.unwrap_or(FormatError::DoesNotFit {
ceiling: (u64::MAX / sector).saturating_mul(sector),
}))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::exfat::geometry::conventional_cluster_size;
use crate::exfat::materialize::FormatPlan;
use crate::source::{Metadata, TreeBuilder};
use crate::time::Timestamp;
const TIME: Timestamp = Timestamp::from_secs(1_426_325_212);
fn opts() -> FormatOptions {
FormatOptions::new(0x1234_5678).accepted_loss(crate::AcceptedLoss::ALL)
}
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:05}").into_bytes(),
vec![0xAB; each],
Metadata::new(0o644, TIME),
);
}
b
}
#[test]
fn the_bands_follow_the_conventional_cluster_size() {
let request = PlanRequest::new(0);
let bands = bands(&request, 1);
assert_eq!(bands.len(), 4);
for pair in bands.windows(2) {
assert_eq!(pair[0].1 + 1, pair[1].0, "the bands meet");
let below = conventional_cluster_size(pair[0].1 * 512);
let above = conventional_cluster_size(pair[1].0 * 512);
assert!(above > below, "{pair:?}");
}
for (low, high) in &bands[..3] {
assert_eq!(
conventional_cluster_size(low * 512),
conventional_cluster_size(high * 512)
);
}
let pinned = PlanRequest::new(0).cluster_size(ClusterSize::Bytes(4096));
assert_eq!(super::bands(&pinned, 9).len(), 1);
}
#[test]
fn a_fitted_size_formats_and_one_sector_less_does_not() {
let plan = FormatPlan::fit(tree(40, 3000), opts(), Slack::None).expect("fit");
let bytes = plan.volume_bytes();
assert!(FormatPlan::new(tree(40, 3000), bytes, opts()).is_ok());
let sector = u64::from(plan.layout().bytes_per_sector);
assert!(FormatPlan::new(tree(40, 3000), bytes - sector, opts()).is_err());
let mut out = std::io::Cursor::new(Vec::new());
plan.write_to(&mut out).expect("write");
let mut r = crate::exfat::Reader::open(std::io::Cursor::new(out.into_inner()))
.expect("a strict read of the fitted volume");
assert_eq!(r.walk().expect("walk").len(), 41);
}
#[test]
fn slack_is_free_room_the_volume_has() {
let tight = FormatPlan::fit(tree(10, 5000), opts(), Slack::None).expect("fit");
let roomy = FormatPlan::fit(tree(10, 5000), opts(), Slack::Bytes(4 << 20)).expect("fit");
assert!(roomy.volume_bytes() > tight.volume_bytes());
let free = u64::from(roomy.free_clusters()) * u64::from(roomy.layout().bytes_per_cluster);
assert!(free >= 4 << 20, "{free} bytes free");
}
#[test]
fn a_tree_just_below_a_cluster_step_is_not_fitted_past_it() {
let plan = FormatPlan::fit(tree(60_000, 1), opts(), Slack::None).expect("fit");
assert!(plan.volume_bytes() <= 256 << 20, "{}", plan.volume_bytes());
assert_eq!(plan.layout().bytes_per_cluster, 4096);
}
}