use crate::extent::ExtentError;
use crate::geometry::{
GeometryError, GrowReservation, InodeCount, Layout, MAX_32BIT_BLOCKS, MAX_EXTENT_BLOCKS,
};
use crate::materialize::{FormatError, FormatOptions, free_after_placing, plan_geometry};
use crate::model::{Content, FsModel};
use crate::sizing::{Probe, Slack};
pub(crate) struct Fitted {
pub(crate) layout: Layout,
pub(crate) journal_blocks: Option<u32>,
}
fn ceiling_blocks(options: &FormatOptions) -> u64 {
let format = if options.feature.is_64bit() {
MAX_EXTENT_BLOCKS
} else {
MAX_32BIT_BLOCKS
};
match options.grow {
GrowReservation::UpTo(bytes) => format.min(bytes / u64::from(options.feature.block_size)),
GrowReservation::None | GrowReservation::Max => format,
}
}
fn content_floor(model: &FsModel, block_size: u64) -> u64 {
model
.inodes
.values()
.map(|inode| match &inode.content {
Content::Directory(_) => 1,
Content::File(content) => content.len().div_ceil(block_size),
Content::SlowSymlink(target) => (target.len() as u64).div_ceil(block_size),
Content::FastSymlink(_) | Content::Device { .. } | Content::Special => 0,
})
.sum()
}
fn classify(e: GeometryError) -> Probe<Fitted, FormatError> {
match e {
GeometryError::TooManyGroups { .. }
| GeometryError::TooManyInodes { .. }
| GeometryError::DescriptorsExceedGroup { .. }
| GeometryError::BlockCountNeeds64Bit { .. }
| GeometryError::BlockCountTooLarge { .. }
| GeometryError::ReservationNeeds32BitBlocks { .. }
| GeometryError::GrowTargetTooSmall { .. } => Probe::Exhausted(FormatError::Geometry(e)),
GeometryError::Feature(_) => Probe::Impossible(FormatError::Geometry(e)),
_ => Probe::TooSmall(FormatError::Geometry(e)),
}
}
fn probe(
model: &FsModel,
options: &FormatOptions,
slack: Slack,
blocks: u64,
) -> Probe<Fitted, FormatError> {
let block_size = u64::from(options.feature.block_size);
let size_bytes = blocks.saturating_mul(block_size);
let (layout, journal_blocks) = match plan_geometry(model, options, size_bytes) {
Ok(planned) => planned,
Err(FormatError::Geometry(e)) => return classify(e),
Err(e @ FormatError::TooManyInodes { .. })
if matches!(options.inodes, InodeCount::Count(_)) =>
{
return Probe::Impossible(e);
}
Err(e) => return Probe::TooSmall(e),
};
let free = match free_after_placing(&layout, options, journal_blocks, model) {
Ok(free) => free,
Err(e @ (FormatError::Dir(_) | FormatError::Extent(ExtentError::FileTooLarge { .. }))) => {
return Probe::Impossible(e);
}
Err(e) => return Probe::TooSmall(e),
};
if free < slack.required_free(layout.total_blocks, block_size) {
return Probe::Tight;
}
Probe::Fits(Fitted {
layout,
journal_blocks,
})
}
pub(crate) fn search(
model: &FsModel,
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 block_size = u64::from(options.feature.block_size);
let ceiling = ceiling_blocks(options);
if slack.required_free(ceiling, block_size) >= ceiling {
return Err(FormatError::DoesNotFit { ceiling });
}
let floor = content_floor(model, block_size).clamp(1, ceiling);
let probed = crate::sizing::bracket(floor, ceiling, |blocks| {
probe(model, options, slack, blocks)
});
match probed {
Ok((_, fitted)) => Ok(fitted),
Err(Some(e)) => Err(e),
Err(None) => Err(FormatError::DoesNotFit { ceiling }),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::feature::{FeatureSet, Profile};
use crate::materialize::{FormatPlan, format};
use crate::model::{ModelConfig, build_model};
use crate::ondisk::SuperBlock;
use crate::read::Reader;
use crate::source::{Metadata, Source, TreeBuilder};
use crate::time::Timestamp;
const MIB: u64 = 1024 * 1024;
fn time() -> Timestamp {
Timestamp::from_secs(1_700_000_000)
}
fn opts() -> FormatOptions {
FormatOptions::new([0x11; 16], time(), [0u8; 16])
}
fn block_size_of(sb: &SuperBlock) -> u64 {
1024u64 << sb.log_block_size
}
fn tree(count: usize, bytes: usize) -> TreeBuilder {
let mut builder =
TreeBuilder::new().directory(b"/data".to_vec(), Metadata::new(0o755, time()));
for i in 0..count {
builder = builder.file(
format!("/data/f{i}").into_bytes(),
vec![b'x'; bytes],
Metadata::new(0o644, time()),
);
}
builder
}
fn fit_err(source: impl Source, options: FormatOptions, slack: Slack) -> FormatError {
match FormatPlan::fit(source, options, slack) {
Ok(plan) => panic!("expected a failure, fitted {} bytes", plan.size_bytes()),
Err(e) => e,
}
}
fn model_of(source: impl Source, options: &FormatOptions) -> FsModel {
let config = ModelConfig::new(options.feature, 12, options.time);
build_model(source, config).expect("model")
}
#[test]
fn a_fitted_size_formats_and_one_block_less_does_not() {
for (count, bytes) in [(0, 0), (1, 1), (16, 4096), (64, 100_000)] {
let plan = FormatPlan::fit(tree(count, bytes), opts(), Slack::None).expect("fit");
let size = plan.size_bytes();
format(tree(count, bytes), size, opts())
.unwrap_or_else(|e| panic!("{count}x{bytes}: the fitted {size} bytes: {e}"));
let smaller = size - u64::from(opts().feature.block_size);
assert!(
format(tree(count, bytes), smaller, opts()).is_err(),
"{count}x{bytes}: one block below the fitted {size} bytes formatted too"
);
}
}
#[test]
fn a_fitted_image_reads_back_with_its_contents() {
let plan = FormatPlan::fit(tree(8, 5000), opts(), Slack::None).expect("fit");
let size = plan.size_bytes();
let image = format(tree(8, 5000), size, opts()).expect("format at the fitted size");
let mut reader = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
let (_, inode) = reader
.lookup(b"/data/f7")
.expect("the last file is present");
assert_eq!(inode.size, 5000);
assert_eq!(reader.read_data(&inode).expect("read").len(), 5000);
}
#[test]
fn slack_is_free_space_the_finished_filesystem_has() {
let source = || tree(32, 20_000);
for slack in [Slack::Bytes(8 * MIB), Slack::Share(2500)] {
let plan = FormatPlan::fit(source(), opts(), slack).expect("fit");
let size = plan.size_bytes();
let image = format(source(), size, opts()).expect("format");
let reader = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
let sb = reader.superblock();
let want = match slack {
Slack::Bytes(bytes) => bytes.div_ceil(block_size_of(sb)),
Slack::Share(h) => Slack::share_of(sb.blocks_count, h),
Slack::None => 0,
};
assert!(
sb.free_blocks_count >= want,
"{slack:?}: {} free of {} blocks, wanted {want}",
sb.free_blocks_count,
sb.blocks_count
);
let smaller = size - u64::from(opts().feature.block_size);
let short = match format(source(), smaller, opts()) {
Err(_) => true,
Ok(image) => {
let reader =
Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
let sb = reader.superblock();
let want = match slack {
Slack::Bytes(bytes) => bytes.div_ceil(block_size_of(sb)),
Slack::Share(h) => Slack::share_of(sb.blocks_count, h),
Slack::None => 0,
};
sb.free_blocks_count < want
}
};
assert!(short, "{slack:?}: one block below the fit satisfied it too");
}
}
#[test]
fn no_slack_leaves_a_filesystem_with_almost_nothing_in_it() {
let options = opts().profile(Profile::Ext2);
let source = || tree(24, 30_000);
let plan = FormatPlan::fit(source(), options, Slack::None).expect("fit");
let image = format(source(), plan.size_bytes(), options).expect("format");
let reader = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
let sb = reader.superblock();
assert!(
sb.free_blocks_count * 10 < sb.blocks_count,
"{} of {} blocks free is not a fitted filesystem",
sb.free_blocks_count,
sb.blocks_count
);
}
#[test]
fn a_bigger_source_fits_a_bigger_filesystem() {
let small = FormatPlan::fit(tree(4, 4096), opts(), Slack::None).expect("fit");
let large = FormatPlan::fit(tree(4, 4 * MIB as usize), opts(), Slack::None).expect("fit");
assert!(
large.size_bytes() > small.size_bytes(),
"{} is not larger than {}",
large.size_bytes(),
small.size_bytes()
);
}
#[test]
fn every_family_fits() {
for profile in [Profile::Ext2, Profile::Ext3, Profile::Ext4] {
let options = opts().profile(profile);
let plan = FormatPlan::fit(tree(12, 9000), options, Slack::None)
.unwrap_or_else(|e| panic!("{profile:?}: {e}"));
let size = plan.size_bytes();
format(tree(12, 9000), size, options)
.unwrap_or_else(|e| panic!("{profile:?} at {size}: {e}"));
assert!(
format(
tree(12, 9000),
size - u64::from(options.feature.block_size),
options
)
.is_err(),
"{profile:?}: one block less formatted too"
);
}
}
#[test]
fn a_thousand_byte_block_fits_too() {
let feature = FeatureSet {
block_size: 1024,
..FeatureSet::EXT2
};
let mut options = opts();
options.feature = feature;
let plan = FormatPlan::fit(tree(6, 3000), options, Slack::None).expect("fit");
let size = plan.size_bytes();
assert_eq!(size % 1024, 0);
format(tree(6, 3000), size, options).expect("format at the fitted size");
}
#[test]
fn the_fitted_plan_is_the_plan_that_writes() {
let plan = FormatPlan::fit(tree(5, 8000), opts(), Slack::None).expect("fit");
let blocks = plan.layout().total_blocks;
let size = plan.size_bytes();
let mut out = std::io::Cursor::new(vec![0u8; size as usize]);
let layout = plan.write_to(&mut out).expect("write");
assert_eq!(layout.total_blocks, blocks);
Reader::open(std::io::Cursor::new(out.into_inner())).expect("the written image opens");
}
#[test]
fn a_grow_target_bounds_the_search() {
let mut options = opts();
options.grow = GrowReservation::UpTo(8 * MIB);
let err = fit_err(tree(64, 1024 * 1024), options, Slack::None);
assert!(
matches!(
err,
FormatError::Alloc(_) | FormatError::JournalDoesNotFit { .. }
),
"{err}"
);
}
#[test]
fn a_share_past_the_limit_is_refused_before_any_search() {
let err = fit_err(
TreeBuilder::new(),
opts(),
Slack::Share(Slack::MAX_SHARE + 1),
);
assert!(
matches!(err, FormatError::SlackShareTooLarge { limit, .. } if limit == Slack::MAX_SHARE),
"{err}"
);
}
#[test]
fn slack_no_filesystem_could_leave_is_answered_before_any_probing() {
let err = fit_err(TreeBuilder::new(), opts(), Slack::Bytes(u64::MAX));
assert!(matches!(err, FormatError::DoesNotFit { .. }), "{err}");
}
#[test]
fn slack_no_filesystem_can_leave_says_so() {
let mut options = opts().profile(Profile::Ext2);
options.grow = GrowReservation::UpTo(8 * MIB);
let err = fit_err(
tree(1, MIB as usize),
options,
Slack::Share(Slack::MAX_SHARE),
);
assert!(matches!(err, FormatError::DoesNotFit { .. }), "{err}");
}
#[test]
fn a_fixed_inode_count_too_small_for_the_tree_fails_at_once() {
let mut options = opts();
options.inodes = InodeCount::Count(16);
let err = fit_err(tree(100, 1), options, Slack::None);
assert!(matches!(err, FormatError::TooManyInodes { .. }), "{err}");
}
#[test]
fn a_feature_set_that_cannot_be_realized_fails_at_once() {
let mut options = opts();
options.feature = FeatureSet {
block_size: 3000,
..FeatureSet::DEFAULT
};
let err = fit_err(TreeBuilder::new(), options, Slack::None);
assert!(matches!(err, FormatError::Geometry(_)), "{err}");
}
#[test]
fn a_refusal_that_points_upward_ends_the_climb_rather_than_stepping_over_the_answer() {
for e in [
GeometryError::TooManyGroups {
blocks: 0,
groups: 0,
limit: 0,
},
GeometryError::TooManyInodes {
blocks: 0,
inodes: 0,
limit: 0,
},
GeometryError::DescriptorsExceedGroup {
blocks: 0,
groups: 0,
overhead: 0,
blocks_per_group: 0,
},
] {
assert!(
matches!(classify(e), Probe::Exhausted(_)),
"{e:?} points upward"
);
}
assert!(matches!(
classify(GeometryError::TooSmall {
blocks: 0,
overhead: 0,
reserved_gdt_blocks: 0,
}),
Probe::TooSmall(_)
));
}
#[test]
fn a_feature_set_that_cannot_be_realized_is_answered_by_the_first_probe() {
let err = classify(GeometryError::Feature(
crate::feature::FeatureError::FiletypeRequired,
));
assert!(matches!(err, Probe::Impossible(_)));
}
#[test]
fn the_content_floor_counts_what_the_contents_occupy() {
let source = TreeBuilder::new()
.file(
b"/big".to_vec(),
vec![b'x'; 8193],
Metadata::new(0o644, time()),
)
.symlink(
b"/short".to_vec(),
b"/big".to_vec(),
Metadata::new(0o777, time()),
)
.char_device(b"/dev".to_vec(), 1, 3, Metadata::new(0o600, time()));
assert_eq!(content_floor(&model_of(source, &opts()), 4096), 5);
}
}