use crate::geometry::{GrowReservation, Layout, MAX_32BIT_BLOCKS, MAX_EXTENT_BLOCKS};
use crate::materialize::{FormatError, FormatOptions, free_after_placing, plan_geometry};
use crate::model::{Content, FsModel};
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum Slack {
#[default]
None,
Bytes(u64),
Share(u16),
}
impl Slack {
pub const MAX_SHARE: u16 = 9000;
fn share_of(total: u64, hundredths: u16) -> u64 {
(u128::from(total) * u128::from(hundredths) / 10_000) as u64
}
fn required_free(self, total_blocks: u64, block_size: u64) -> u64 {
match self {
Self::None => 0,
Self::Bytes(bytes) => bytes.div_ceil(block_size),
Self::Share(hundredths) => Self::share_of(total_blocks, hundredths),
}
}
fn validate(self) -> Result<(), FormatError> {
match self {
Self::Share(hundredths) if hundredths > Self::MAX_SHARE => {
Err(FormatError::SlackShareTooLarge {
hundredths,
limit: Self::MAX_SHARE,
})
}
_ => Ok(()),
}
}
}
pub(crate) struct Fitted {
pub(crate) layout: Layout,
pub(crate) journal_blocks: Option<u32>,
}
enum Miss {
Failed(FormatError),
TooTight,
}
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 probe(
model: &FsModel,
options: &FormatOptions,
slack: Slack,
blocks: u64,
) -> Result<Fitted, Miss> {
let block_size = u64::from(options.feature.block_size);
let size_bytes = blocks.saturating_mul(block_size);
let (layout, journal_blocks) =
plan_geometry(model, options, size_bytes).map_err(Miss::Failed)?;
let free = free_after_placing(&layout, options, journal_blocks, model).map_err(Miss::Failed)?;
if free < slack.required_free(layout.total_blocks, block_size) {
return Err(Miss::TooTight);
}
Ok(Fitted {
layout,
journal_blocks,
})
}
pub(crate) fn search(
model: &FsModel,
options: &FormatOptions,
slack: Slack,
) -> Result<Fitted, FormatError> {
slack.validate()?;
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 mut lo = 0u64;
let mut candidate = content_floor(model, block_size).clamp(1, ceiling);
let (mut hi, mut fitted) = loop {
let miss = match probe(model, options, slack, candidate) {
Ok(fitted) => break (candidate, fitted),
Err(miss) => miss,
};
lo = candidate;
if candidate == ceiling {
return Err(match miss {
Miss::Failed(e) => e,
Miss::TooTight => FormatError::DoesNotFit { ceiling },
});
}
candidate = candidate.saturating_mul(2).min(ceiling);
};
while hi - lo > 1 {
let mid = lo + (hi - lo) / 2;
match probe(model, options, slack, mid) {
Ok(next) => {
hi = mid;
fitted = next;
}
Err(_) => lo = mid,
}
}
Ok(fitted)
}
#[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, Timestamp};
use crate::read::Reader;
use crate::source::{Metadata, Source, TreeBuilder};
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_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 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);
}
}