use std::num::NonZeroU64;
use crate::feature::FeatureSet;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct BlockRange {
pub start: u64,
pub len: u64,
}
impl BlockRange {
#[must_use]
pub const fn end(self) -> u64 {
self.start + self.len
}
#[must_use]
pub const fn is_empty(self) -> bool {
self.len == 0
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum GeometryError {
#[error(
"filesystem of {blocks} blocks is too small: group 0 needs {overhead} for metadata, \
{reserved_gdt_blocks} of them reserved to grow into"
)]
#[non_exhaustive]
TooSmall {
blocks: u64,
overhead: u64,
reserved_gdt_blocks: u64,
},
#[error("grow target {target} blocks is below the initial size {initial} blocks")]
#[non_exhaustive]
GrowTargetTooSmall {
target: u64,
initial: u64,
},
#[error(
"grow target needs {needed} reserved GDT blocks but the resize inode can \
represent at most {limit}; a larger target would require meta_bg"
)]
#[non_exhaustive]
GrowTargetTooLarge {
needed: u64,
limit: u64,
},
#[error(
"a filesystem of {blocks} blocks cannot reserve descriptor blocks: the resize \
inode's block map is 32 bits wide and addresses at most {limit} blocks"
)]
#[non_exhaustive]
ReservationNeeds32BitBlocks {
blocks: u64,
limit: u64,
},
#[error("a grow target needs the resize_inode feature to map the reserved GDT blocks")]
GrowTargetNeedsResizeInode,
#[error("filesystem of {blocks} blocks needs {groups} block groups, past the {limit} limit")]
#[non_exhaustive]
TooManyGroups {
blocks: u64,
groups: u64,
limit: u64,
},
#[error(
"filesystem of {blocks} blocks needs {groups} block groups, whose {overhead}-block \
superblock and descriptor run does not fit a block group of {blocks_per_group} blocks"
)]
#[non_exhaustive]
DescriptorsExceedGroup {
blocks: u64,
groups: u64,
overhead: u64,
blocks_per_group: u64,
},
#[error("filesystem of {blocks} blocks needs {inodes} inodes, past the {limit} limit")]
#[non_exhaustive]
TooManyInodes {
blocks: u64,
inodes: u64,
limit: u64,
},
#[error(
"inode density needs {inodes_per_group} inodes per group but a group's bitmap \
indexes at most {limit}"
)]
#[non_exhaustive]
InodesTooDense {
inodes_per_group: u64,
limit: u64,
},
#[error(
"filesystem of {blocks} blocks needs the 64bit feature: a 32-bit block \
number addresses at most {limit}"
)]
#[non_exhaustive]
BlockCountNeeds64Bit {
blocks: u64,
limit: u64,
},
#[error("filesystem of {blocks} blocks exceeds the {limit} an extent addresses")]
#[non_exhaustive]
BlockCountTooLarge {
blocks: u64,
limit: u64,
},
#[error("final group of {blocks} blocks cannot hold its {overhead} metadata blocks")]
#[non_exhaustive]
FinalGroupTooSmall {
blocks: u64,
overhead: u64,
},
#[error(transparent)]
Feature(#[from] crate::feature::FeatureError),
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct GroupLayout {
pub index: u32,
pub start_block: u64,
pub block_count: u32,
pub has_super: bool,
pub block_bitmap: u64,
pub inode_bitmap: u64,
pub inode_table: u64,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct Layout {
pub feature: FeatureSet,
pub block_size: u32,
pub total_blocks: u64,
pub blocks_per_group: u32,
pub first_data_block: u32,
pub group_count: u32,
pub inodes_per_group: u32,
pub inode_table_blocks: u32,
pub total_inodes: u32,
pub gdt_blocks: u32,
pub reserved_gdt_blocks: u32,
pub flex_bg_size: u32,
pub max_grow_blocks: u64,
pub reserved_blocks: u64,
pub groups: Vec<GroupLayout>,
}
pub const MAX_32BIT_BLOCKS: u64 = u32::MAX as u64;
pub const MAX_EXTENT_BLOCKS: u64 = 1 << 48;
const GROW_MAX_SHARE: u64 = 64;
const MIN_INODES_PER_GROUP: u64 = 8;
#[must_use]
fn super_overhead(gdt_blocks: u32, reserved_gdt_blocks: u32) -> u64 {
1 + u64::from(gdt_blocks) + u64::from(reserved_gdt_blocks)
}
impl Layout {
#[must_use]
pub fn is_flex_head(&self, index: u32) -> bool {
index.is_multiple_of(self.flex_bg_size)
}
#[must_use]
fn flex_members(&self, head: u32) -> u32 {
(self.group_count - head).min(self.flex_bg_size)
}
#[must_use]
fn flex_slots(&self, head: u32) -> u32 {
let members = self.flex_members(head);
if members == 1 {
self.flex_bg_size
} else {
members
}
}
#[must_use]
fn flex_meta_span(&self, head: u32) -> u64 {
let slots = u64::from(self.flex_slots(head));
let members = u64::from(self.flex_members(head));
2 * slots + members * u64::from(self.inode_table_blocks)
}
#[must_use]
pub fn super_overhead_region(&self, index: u32) -> Option<BlockRange> {
let g = self.groups.get(index as usize)?;
if !g.has_super {
return None;
}
Some(BlockRange {
start: g.start_block,
len: super_overhead(self.gdt_blocks, self.reserved_gdt_blocks),
})
}
#[must_use]
pub fn backup_groups(&self) -> Vec<u32> {
self.groups
.iter()
.filter(|g| g.has_super && g.index != 0)
.map(|g| g.index)
.collect()
}
#[must_use]
pub fn metadata_regions(&self) -> Vec<BlockRange> {
let mut runs = Vec::new();
for g in &self.groups {
if let Some(r) = self.super_overhead_region(g.index) {
runs.push(r);
}
runs.push(BlockRange {
start: g.block_bitmap,
len: 1,
});
runs.push(BlockRange {
start: g.inode_bitmap,
len: 1,
});
runs.push(BlockRange {
start: g.inode_table,
len: u64::from(self.inode_table_blocks),
});
}
runs.sort_by_key(|r| r.start);
runs
}
#[must_use]
pub fn overhead_blocks(&self) -> u64 {
self.metadata_regions().iter().map(|r| r.len).sum()
}
}
fn is_power_of(mut g: u32, base: u32) -> bool {
if g == 0 {
return false;
}
while g > 1 {
if !g.is_multiple_of(base) {
return false;
}
g /= base;
}
true
}
#[must_use]
pub(crate) fn sparse_super_has_copy(g: u32) -> bool {
g == 0 || g == 1 || is_power_of(g, 3) || is_power_of(g, 5) || is_power_of(g, 7)
}
const COMPAT_SPARSE_SUPER2: u32 = 0x0200;
#[must_use]
pub(crate) fn carries_superblock(g: u32, sb: &crate::ondisk::SuperBlock) -> bool {
if g == 0 {
return true;
}
if sb.feature_compat & COMPAT_SPARSE_SUPER2 != 0 {
return sb.backup_bgs.contains(&g);
}
sb.feature_ro_compat & crate::feature::RoCompat::SPARSE_SUPER.bits() == 0
|| sparse_super_has_copy(g)
}
fn inode_ratio(total_blocks: u64, block_size: u32) -> u64 {
let meg = u64::from((1024 * 1024) / block_size);
if total_blocks < 3 * meg {
8192 } else if total_blocks < 512 * meg {
4096 } else if total_blocks < 4 * 1024 * 1024 * meg {
16384 } else if total_blocks < 16 * 1024 * 1024 * meg {
32768 } else {
65536 }
}
fn gdt_blocks_for(groups: u64, desc_size: u16, block_size: u32) -> u64 {
let per_block = u64::from(block_size) / u64::from(desc_size);
groups.div_ceil(per_block)
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum GrowReservation {
None,
UpTo(u64),
#[default]
Max,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum InodeCount {
#[default]
Auto,
BytesPerInode(NonZeroU64),
Count(u32),
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct ReservedRatio {
hundredths_of_percent: u16,
}
impl ReservedRatio {
const MAX_HUNDREDTHS: u16 = 5000;
pub const DEFAULT: Self = Self {
hundredths_of_percent: 500,
};
#[must_use]
pub fn from_hundredths_of_percent(hundredths: u16) -> Option<Self> {
(hundredths <= Self::MAX_HUNDREDTHS).then_some(Self {
hundredths_of_percent: hundredths,
})
}
#[must_use]
pub fn hundredths_of_percent(self) -> u16 {
self.hundredths_of_percent
}
#[must_use]
pub fn blocks(self, total_blocks: u64) -> u64 {
let reserved = u128::from(total_blocks) * u128::from(self.hundredths_of_percent) / 10_000;
reserved as u64
}
}
impl Default for ReservedRatio {
fn default() -> Self {
Self::DEFAULT
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PlanRequest {
pub size_bytes: u64,
pub feature: FeatureSet,
pub grow: GrowReservation,
pub inodes: InodeCount,
pub reserved: ReservedRatio,
}
impl PlanRequest {
#[must_use]
pub const fn new(size_bytes: u64, feature: FeatureSet) -> Self {
Self {
size_bytes,
feature,
grow: GrowReservation::Max,
inodes: InodeCount::Auto,
reserved: ReservedRatio::DEFAULT,
}
}
#[must_use]
pub const fn grow(mut self, grow: GrowReservation) -> Self {
self.grow = grow;
self
}
#[must_use]
pub const fn inodes(mut self, inodes: InodeCount) -> Self {
self.inodes = inodes;
self
}
#[must_use]
pub const fn reserved(mut self, reserved: ReservedRatio) -> Self {
self.reserved = reserved;
self
}
}
pub fn plan_layout(request: &PlanRequest) -> Result<Layout, GeometryError> {
let &PlanRequest {
size_bytes,
feature,
grow: reservation,
inodes,
reserved,
} = request;
feature.validate()?;
let block_size = feature.block_size;
let total_blocks = size_bytes / u64::from(block_size);
if let GrowReservation::UpTo(bytes) = reservation {
let target = bytes / u64::from(block_size);
if target < total_blocks {
return Err(GeometryError::GrowTargetTooSmall {
target,
initial: total_blocks,
});
}
}
if !feature.is_64bit() && total_blocks > MAX_32BIT_BLOCKS {
return Err(GeometryError::BlockCountNeeds64Bit {
blocks: total_blocks,
limit: MAX_32BIT_BLOCKS,
});
}
if total_blocks > MAX_EXTENT_BLOCKS {
return Err(GeometryError::BlockCountTooLarge {
blocks: total_blocks,
limit: MAX_EXTENT_BLOCKS,
});
}
let first_data_block = if block_size == 1024 { 1 } else { 0 };
let fdb = u64::from(first_data_block);
let blocks_per_group = 8 * block_size;
let bpg = u64::from(blocks_per_group);
let desc_size = feature.desc_size();
let ipb = u64::from(feature.inodes_per_block());
let inode_cap = u64::from(8 * block_size);
let flex_bg_size: u32 = 16;
let reserved_limit = u64::from(block_size) / 4;
let resize_ceiling = MAX_32BIT_BLOCKS;
let reservation_representable = total_blocks <= resize_ceiling;
let can_reserve = feature.has_resize_inode() && reservation_representable;
let up_to_gdt = if let GrowReservation::UpTo(bytes) = reservation {
let target = bytes / u64::from(block_size);
let groups = target.saturating_sub(fdb).div_ceil(bpg);
Some(gdt_blocks_for(groups, desc_size, block_size))
} else {
None
};
let ceiling_gdt = gdt_blocks_for((resize_ceiling - fdb).div_ceil(bpg), desc_size, block_size);
let inode_count_for = |blocks: u64| -> u64 {
let held = blocks.saturating_sub(fdb);
match inodes {
InodeCount::Auto => held * u64::from(block_size) / inode_ratio(blocks, block_size),
InodeCount::BytesPerInode(bytes) => held * u64::from(block_size) / bytes.get(),
InodeCount::Count(count) => u64::from(count),
}
.max(16)
};
let mut total_blocks = total_blocks;
let (group_count_u64, gdt_blocks, reserved_gdt_blocks, inodes_per_group, inode_table_blocks) = loop {
let addressable = total_blocks.saturating_sub(fdb);
let group_count = addressable.div_ceil(bpg).max(1);
if group_count > u64::from(u32::MAX) {
return Err(GeometryError::TooManyGroups {
blocks: total_blocks,
groups: group_count,
limit: u64::from(u32::MAX),
});
}
let gdt = gdt_blocks_for(group_count, desc_size, block_size);
let reserved = match reservation {
GrowReservation::None => 0,
GrowReservation::UpTo(_) => {
let want = up_to_gdt.unwrap_or(gdt).saturating_sub(gdt);
if want > 0 && !feature.has_resize_inode() {
return Err(GeometryError::GrowTargetNeedsResizeInode);
}
if want > 0 && !reservation_representable {
return Err(GeometryError::ReservationNeeds32BitBlocks {
blocks: total_blocks,
limit: resize_ceiling,
});
}
if want > reserved_limit {
return Err(GeometryError::GrowTargetTooLarge {
needed: want,
limit: reserved_limit,
});
}
want
}
GrowReservation::Max if !can_reserve => 0,
GrowReservation::Max => reserved_limit
.min(ceiling_gdt.saturating_sub(gdt))
.min(total_blocks / GROW_MAX_SHARE)
.min(bpg.saturating_sub(1 + gdt)),
};
if group_count >= 2 && 1 + gdt + reserved > bpg {
return Err(GeometryError::DescriptorsExceedGroup {
blocks: total_blocks,
groups: group_count,
overhead: 1 + gdt + reserved,
blocks_per_group: bpg,
});
}
let num_inodes = inode_count_for(total_blocks);
let mut ipg = num_inodes.div_ceil(group_count);
if ipg > inode_cap {
return Err(GeometryError::InodesTooDense {
inodes_per_group: ipg,
limit: inode_cap,
});
}
ipg = ((ipg.div_ceil(ipb) * ipb) & !7).max(MIN_INODES_PER_GROUP);
let itb = ipg / ipb;
let rem = addressable % bpg;
if group_count >= 2 && rem != 0 {
let last = (group_count - 1) as u32;
let mut required = 0u64;
if !feature.is_sparse_super() || sparse_super_has_copy(last) {
required += 1 + gdt + reserved;
}
if feature.has_flex_bg() {
if last.is_multiple_of(flex_bg_size) {
let members = group_count - u64::from(last);
let slots = if members == 1 {
u64::from(flex_bg_size)
} else {
members
};
required += 2 * slots + members * itb;
}
} else {
required += 2 + itb;
}
if rem < required + 1 {
total_blocks -= rem;
continue;
}
}
break (
group_count,
gdt as u32,
reserved as u32,
ipg as u32,
itb as u32,
);
};
let group_count = group_count_u64 as u32;
let total_inodes_u64 = u64::from(inodes_per_group) * group_count_u64;
if total_inodes_u64 > u64::from(u32::MAX) {
return Err(GeometryError::TooManyInodes {
blocks: total_blocks,
inodes: total_inodes_u64,
limit: u64::from(u32::MAX),
});
}
let total_inodes = total_inodes_u64 as u32;
let max_grow_blocks = match reservation {
GrowReservation::None => total_blocks,
GrowReservation::UpTo(bytes) => bytes / u64::from(block_size),
GrowReservation::Max => {
let per_block = u64::from(block_size) / u64::from(desc_size);
let describable = (u64::from(gdt_blocks) + u64::from(reserved_gdt_blocks)) * per_block;
(describable * bpg + fdb)
.min(resize_ceiling)
.max(total_blocks)
}
};
let group0_tables = if feature.has_flex_bg() {
let g0_members = group_count_u64.min(u64::from(flex_bg_size));
let g0_slots = if g0_members == 1 {
u64::from(flex_bg_size)
} else {
g0_members
};
2 * g0_slots + g0_members * u64::from(inode_table_blocks)
} else {
2 + u64::from(inode_table_blocks)
};
let group0_overhead = super_overhead(gdt_blocks, reserved_gdt_blocks) + group0_tables + 1;
if total_blocks < group0_overhead {
return Err(GeometryError::TooSmall {
blocks: total_blocks,
overhead: group0_overhead,
reserved_gdt_blocks: u64::from(reserved_gdt_blocks),
});
}
let reserved_blocks = reserved.blocks(total_blocks);
let mut layout = Layout {
feature,
block_size,
total_blocks,
blocks_per_group,
first_data_block,
group_count,
inodes_per_group,
inode_table_blocks,
total_inodes,
gdt_blocks,
reserved_gdt_blocks,
flex_bg_size,
max_grow_blocks,
reserved_blocks,
groups: Vec::with_capacity(group_count as usize),
};
for index in 0..group_count {
let start_block = fdb + u64::from(index) * u64::from(blocks_per_group);
let end_block = (start_block + u64::from(blocks_per_group)).min(total_blocks);
let block_count = (end_block - start_block) as u32;
let has_super = if feature.is_sparse_super() {
sparse_super_has_copy(index)
} else {
true
};
layout.groups.push(GroupLayout {
index,
start_block,
block_count,
has_super,
block_bitmap: 0,
inode_bitmap: 0,
inode_table: 0,
});
}
let itb = u64::from(inode_table_blocks);
let mut placed_end = 0u64;
if feature.has_flex_bg() {
let backups: Vec<BlockRange> = (0..group_count)
.filter_map(|g| layout.super_overhead_region(g))
.collect();
let mut head = 0u32;
while head < group_count {
let members = layout.flex_members(head);
let slots = u64::from(layout.flex_slots(head));
let overhead = layout.super_overhead_region(head).map_or(0, |r| r.len);
let mut cursor = (layout.groups[head as usize].start_block + overhead).max(placed_end);
let mut block_bitmaps = Vec::with_capacity(members as usize);
for _ in 0..members {
let b = first_fit(cursor, 1, &backups);
block_bitmaps.push(b);
cursor = b + 1;
}
cursor = cursor.max(block_bitmaps[0] + slots);
let mut inode_bitmaps = Vec::with_capacity(members as usize);
for _ in 0..members {
let b = first_fit(cursor, 1, &backups);
inode_bitmaps.push(b);
cursor = b + 1;
}
cursor = cursor.max(inode_bitmaps[0] + slots);
for m in 0..members {
let table = first_fit(cursor, itb, &backups);
cursor = table + itb;
let g = &mut layout.groups[(head + m) as usize];
g.block_bitmap = block_bitmaps[m as usize];
g.inode_bitmap = inode_bitmaps[m as usize];
g.inode_table = table;
}
placed_end = cursor;
head += layout.flex_bg_size;
}
} else {
for index in 0..group_count {
let overhead = layout.super_overhead_region(index).map_or(0, |r| r.len);
let base = layout.groups[index as usize].start_block + overhead;
let g = &mut layout.groups[index as usize];
g.block_bitmap = base;
g.inode_bitmap = base + 1;
g.inode_table = base + 2;
placed_end = base + 2 + itb;
}
}
let last = group_count - 1;
let last_group = &layout.groups[last as usize];
let mut last_overhead = 0u64;
if let Some(r) = layout.super_overhead_region(last) {
last_overhead += r.len;
}
if feature.has_flex_bg() {
if layout.is_flex_head(last) {
last_overhead += layout.flex_meta_span(last);
}
} else {
last_overhead += 2 + u64::from(inode_table_blocks);
}
if u64::from(last_group.block_count) < last_overhead + 1 || placed_end > layout.total_blocks {
return Err(GeometryError::FinalGroupTooSmall {
blocks: u64::from(last_group.block_count),
overhead: last_overhead,
});
}
Ok(layout)
}
fn first_fit(from: u64, len: u64, windows: &[BlockRange]) -> u64 {
let mut start = from;
'restart: loop {
for w in windows {
if w.start < start + len && start < w.end() {
start = w.end();
continue 'restart;
}
}
return start;
}
}
#[cfg(test)]
mod tests {
use super::*;
const MIB: u64 = 1024 * 1024;
const GROW_32G: u64 = 32 * 1024 * MIB;
fn plan(mib: u64) -> Layout {
plan_layout(
&PlanRequest::new(mib * MIB, FeatureSet::default())
.grow(GrowReservation::UpTo(GROW_32G)),
)
.expect("plan")
}
fn plan_at(block_size: u32, mib: u64) -> Layout {
let fs = FeatureSet {
block_size,
..FeatureSet::default()
};
plan_layout(&PlanRequest::new(mib * MIB, fs).grow(GrowReservation::UpTo(GROW_32G)))
.expect("plan")
}
fn plan_geo(
size_bytes: u64,
reservation: GrowReservation,
feature: FeatureSet,
) -> Result<Layout, GeometryError> {
plan_layout(&PlanRequest::new(size_bytes, feature).grow(reservation))
}
fn plan_inodes(mib: u64, inodes: InodeCount) -> Layout {
plan_layout(
&PlanRequest::new(mib * MIB, FeatureSet::default())
.grow(GrowReservation::None)
.inodes(inodes),
)
.expect("plan")
}
fn plan_bs_inodes(block_size: u32, mib: u64, inodes: InodeCount) -> Layout {
let fs = FeatureSet {
block_size,
..FeatureSet::default()
};
plan_layout(
&PlanRequest::new(mib * MIB, fs)
.grow(GrowReservation::None)
.inodes(inodes),
)
.expect("plan")
}
fn plan_reserved(mib: u64, reserved: ReservedRatio) -> Layout {
plan_layout(
&PlanRequest::new(mib * MIB, FeatureSet::default())
.grow(GrowReservation::None)
.reserved(reserved),
)
.expect("plan")
}
#[test]
fn a_flex_block_groups_tables_step_around_the_backups_they_meet() {
let l = plan_at(1024, 200);
let itb = u64::from(l.inode_table_blocks);
let backups: Vec<BlockRange> = (0..l.group_count)
.filter_map(|g| l.super_overhead_region(g))
.collect();
assert!(backups.len() > 1, "this size has backup superblocks");
for g in &l.groups {
let table = BlockRange {
start: g.inode_table,
len: itb,
};
for w in &backups {
assert!(
table.end() <= w.start || table.start >= w.end(),
"group {}'s inode table {table:?} straddles the backup at {w:?}",
g.index
);
}
}
assert!(
l.groups
.windows(2)
.any(|w| w[1].inode_table > w[0].inode_table + itb),
"no table was displaced, so this size does not exercise the rule"
);
}
fn plan_block_mapped(feature: FeatureSet, block_size: u32, mib: u64) -> Layout {
let fs = FeatureSet {
block_size,
..feature
};
plan_layout(&PlanRequest::new(mib * MIB, fs).grow(GrowReservation::None)).expect("plan")
}
#[test]
fn block_mapped_metadata_stays_within_each_group() {
for feature in [FeatureSet::EXT2, FeatureSet::EXT3] {
for bs in [1024u32, 2048, 4096] {
let l = plan_block_mapped(feature, bs, 600);
assert!(!l.feature.has_flex_bg(), "the family is non-flex (bs={bs})");
assert!(
!l.feature.has_extents(),
"the family is block-mapped (bs={bs})"
);
assert_eq!(
l.feature.desc_size(),
32,
"32-byte descriptors without 64bit"
);
assert!(
l.group_count >= 4,
"need at least four groups for the group-3 backup (bs={bs}, groups={})",
l.group_count
);
assert!(
l.super_overhead_region(1).is_some() && l.super_overhead_region(3).is_some(),
"sparse_super keeps backups in groups 1 and 3 (bs={bs})"
);
let itb = u64::from(l.inode_table_blocks);
for g in &l.groups {
let overhead = l.super_overhead_region(g.index).map_or(0, |r| r.len);
let base = g.start_block + overhead;
assert_eq!(
g.block_bitmap, base,
"group {} block bitmap (bs={bs})",
g.index
);
assert_eq!(
g.inode_bitmap,
base + 1,
"group {} inode bitmap (bs={bs})",
g.index
);
assert_eq!(
g.inode_table,
base + 2,
"group {} inode table (bs={bs})",
g.index
);
let group_end = g.start_block + u64::from(g.block_count);
assert!(
g.block_bitmap >= g.start_block && g.inode_table + itb <= group_end,
"group {}'s metadata {}..{} leaves the group {}..{} (bs={bs})",
g.index,
g.block_bitmap,
g.inode_table + itb,
g.start_block,
group_end
);
}
let runs = l.metadata_regions();
for pair in runs.windows(2) {
assert!(
pair[0].end() <= pair[1].start,
"block-mapped metadata overlaps at bs={bs}: {:?} then {:?}",
pair[0],
pair[1]
);
}
}
}
}
#[test]
fn metadata_never_overlaps_at_any_block_size() {
for bs in [1024u32, 2048, 4096] {
for mib in [16u64, 33, 64, 120, 200, 512] {
let l = plan_at(bs, mib);
let runs = l.metadata_regions();
for pair in runs.windows(2) {
assert!(
pair[0].end() <= pair[1].start,
"{bs}-byte blocks, {mib} MiB: {:?} overlaps {:?}",
pair[0],
pair[1]
);
}
let last = runs.last().expect("a filesystem has metadata");
assert!(last.end() <= l.total_blocks, "metadata runs past the end");
}
}
}
#[test]
fn the_superblock_and_descriptor_run_always_fits_a_block_group() {
for bs in [1024u32, 2048, 4096] {
for shift in 4..=23u32 {
let mib = 1u64 << shift;
let features = FeatureSet {
block_size: bs,
..FeatureSet::default()
};
let planned = plan_geo(mib * MIB, GrowReservation::Max, features);
let Ok(l) = planned else {
plan_geo(mib * MIB, GrowReservation::None, features)
.expect_err("Max failed a size that plans without a reservation");
continue;
};
let run = super_overhead(l.gdt_blocks, l.reserved_gdt_blocks);
assert!(
l.group_count < 2 || run <= u64::from(l.blocks_per_group),
"{bs}-byte blocks, {mib} MiB: a {run}-block run in a \
{}-block group",
l.blocks_per_group
);
}
}
}
#[test]
fn max_plans_every_size_the_geometry_itself_can_express() {
let features = FeatureSet {
block_size: 1024,
..FeatureSet::default()
};
for groups in [126_961u64, 129_000, 131_056] {
let bytes = groups * 8 * 1024 * 1024;
plan_geo(bytes, GrowReservation::None, features)
.expect("the geometry itself is expressible");
let l = plan_geo(bytes, GrowReservation::Max, features)
.unwrap_or_else(|e| panic!("{groups} groups: Max refused what None plans: {e}"));
let run = super_overhead(l.gdt_blocks, l.reserved_gdt_blocks);
assert!(
run <= u64::from(l.blocks_per_group),
"{groups} groups: a {run}-block run in a {}-block group",
l.blocks_per_group
);
}
}
#[test]
fn a_descriptor_table_too_large_for_a_block_group_is_refused() {
for (bs, mib) in [
(1024u32, 1024u64 * 1024),
(1024, 2 * 1024 * 1024),
(2048, 16 * 1024 * 1024),
] {
let err = plan_geo(
mib * MIB,
GrowReservation::None,
FeatureSet {
block_size: bs,
..FeatureSet::default()
},
)
.expect_err("a run longer than a block group is not plannable");
assert!(
matches!(err, GeometryError::DescriptorsExceedGroup { .. }),
"{bs}-byte blocks, {mib} MiB: expected DescriptorsExceedGroup, got {err:?}"
);
}
}
#[test]
fn the_size_below_the_descriptor_threshold_still_plans() {
let l = plan_geo(
990 * 1024 * MIB,
GrowReservation::None,
FeatureSet {
block_size: 1024,
..FeatureSet::default()
},
)
.expect("990 GiB at a 1 KiB block is expressible without meta_bg");
assert!(
super_overhead(l.gdt_blocks, l.reserved_gdt_blocks) <= u64::from(l.blocks_per_group)
);
}
#[test]
fn a_groups_inode_count_ends_on_a_byte_boundary() {
for bs in [1024u32, 2048, 4096] {
for mib in [16u64, 33, 64, 120, 200, 512, 2048] {
let l = plan_at(bs, mib);
assert!(
l.inodes_per_group.is_multiple_of(8),
"{bs}-byte blocks, {mib} MiB: inodes_per_group {} is not a multiple of 8",
l.inodes_per_group
);
assert!(l.inodes_per_group > 0);
}
}
}
#[test]
fn only_a_1024_byte_block_reserves_block_zero() {
assert_eq!(plan_at(1024, 64).first_data_block, 1);
assert_eq!(plan_at(2048, 64).first_data_block, 0);
assert_eq!(plan_at(4096, 64).first_data_block, 0);
}
#[test]
fn a_filesystem_past_thirty_two_bits_needs_the_64bit_feature() {
let bytes = 20_000_000_000_000u64; let no_64bit = FeatureSet {
incompat: crate::feature::Incompat::from_bits(
FeatureSet::default().incompat.bits()
& !crate::feature::Incompat::SIXTY_FOUR_BIT.bits(),
),
..FeatureSet::default()
};
assert!(!no_64bit.is_64bit());
assert!(matches!(
plan_geo(bytes, GrowReservation::UpTo(bytes), no_64bit),
Err(GeometryError::BlockCountNeeds64Bit { .. })
));
let under = MAX_32BIT_BLOCKS * 4096;
assert!(plan_geo(under, GrowReservation::UpTo(under), no_64bit).is_ok());
}
#[test]
fn the_planner_addresses_a_drive_past_thirty_two_bits_exactly() {
for bytes in [
20_000_000_000_000u64, 64 * 1024 * 1024 * MIB,
] {
let l =
plan_geo(bytes, GrowReservation::UpTo(bytes), FeatureSet::default()).expect("plan");
assert_eq!(l.total_blocks, bytes / 4096, "block count is exact");
assert!(
l.total_blocks > MAX_32BIT_BLOCKS,
"this size is past 32 bits"
);
assert_eq!(
u64::from(l.total_inodes),
u64::from(l.inodes_per_group) * u64::from(l.group_count)
);
}
}
#[test]
fn a_filesystem_past_what_an_extent_addresses_is_refused() {
let bytes = (MAX_EXTENT_BLOCKS + 1) * 4096;
assert!(matches!(
plan_geo(bytes, GrowReservation::UpTo(bytes), FeatureSet::default()),
Err(GeometryError::BlockCountTooLarge { .. })
));
}
#[test]
fn a_superblock_copy_is_in_the_groups_the_superblock_names() {
let mut sb = crate::ondisk::SuperBlock::default();
assert!((0..20).all(|g| carries_superblock(g, &sb)));
sb.feature_ro_compat = crate::feature::RoCompat::SPARSE_SUPER.bits();
let with: Vec<u32> = (0..50).filter(|&g| carries_superblock(g, &sb)).collect();
assert_eq!(with, [0, 1, 3, 5, 7, 9, 25, 27, 49]);
sb.feature_compat = COMPAT_SPARSE_SUPER2;
sb.backup_bgs = [1, 64];
let with: Vec<u32> = (0..100).filter(|&g| carries_superblock(g, &sb)).collect();
assert_eq!(with, [0, 1, 64]);
sb.backup_bgs = [0, 0];
let with: Vec<u32> = (0..100).filter(|&g| carries_superblock(g, &sb)).collect();
assert_eq!(with, [0]);
}
#[test]
fn is_power_of_matches_sparse_super_backups() {
for g in [1u32, 3, 5, 7, 9, 25, 27, 49, 81, 125, 243, 343] {
assert!(sparse_super_has_copy(g), "group {g} should carry a copy");
}
for g in [2u32, 4, 6, 8, 10, 11, 15, 16, 24, 26, 48] {
assert!(!sparse_super_has_copy(g), "group {g} should not");
}
assert!(sparse_super_has_copy(0), "primary");
}
#[test]
fn single_group_64mib_matches_ground_truth() {
let l = plan(64);
assert_eq!(l.total_blocks, 16384);
assert_eq!(l.group_count, 1);
assert_eq!(l.inodes_per_group, 16384);
assert_eq!(l.inode_table_blocks, 1024);
assert_eq!(l.total_inodes, 16384);
assert_eq!(l.gdt_blocks, 1);
assert_eq!(l.reserved_gdt_blocks, 3);
assert_eq!(l.reserved_blocks, 819);
let g0 = &l.groups[0];
assert!(g0.has_super);
assert_eq!(g0.block_bitmap, 5);
assert_eq!(g0.inode_bitmap, 21, "single-group flex reserves 16 slots");
assert_eq!(g0.inode_table, 37);
assert!(l.backup_groups().is_empty(), "one group: no backups");
}
#[test]
fn an_absolute_inode_count_rounds_up_to_fill_the_group_tables() {
let l = plan_inodes(64, InodeCount::Count(5000));
assert_eq!(l.group_count, 1);
assert_eq!(l.inodes_per_group, 5008);
assert_eq!(l.total_inodes, 5008);
let l = plan_inodes(256, InodeCount::Count(5000));
assert_eq!(l.group_count, 2);
assert_eq!(l.inodes_per_group, 2512);
assert_eq!(l.total_inodes, 5024);
}
#[test]
fn an_absolute_inode_count_at_1024_byte_blocks_matches_mke2fs() {
for (request, want_ipg) in [
(2040u32, 2040u32),
(2041, 2040),
(2044, 2040), (2046, 2048),
(2048, 2048),
(2049, 2048),
(2050, 2048), (2052, 2048),
(2053, 2056),
] {
let l = plan_bs_inodes(1024, 8, InodeCount::Count(request));
assert_eq!(l.group_count, 1, "8 MiB at 1024-byte blocks is one group");
assert_eq!(
l.inodes_per_group, want_ipg,
"Count({request}) at 1024-byte blocks: inodes_per_group",
);
assert_eq!(
l.total_inodes, want_ipg,
"single group: total equals per-group",
);
}
}
#[test]
fn an_absolute_inode_count_at_2048_byte_blocks_masks_to_eight() {
let fs = FeatureSet {
block_size: 2048,
inode_size: 512,
..FeatureSet::default()
};
for (request, want_ipg) in [(4090u32, 4088u32), (4094, 4096), (4097, 4096)] {
let l = plan_layout(
&PlanRequest::new(16 * MIB, fs)
.grow(GrowReservation::None)
.inodes(InodeCount::Count(request)),
)
.expect("plan");
assert_eq!(l.group_count, 1, "16 MiB at 2048-byte blocks is one group");
assert_eq!(
l.inodes_per_group, want_ipg,
"Count({request}) at 2048-byte blocks: inodes_per_group",
);
}
}
#[test]
fn a_count_spread_below_the_rounding_step_still_leaves_every_group_inodes() {
for (mib, request, want_ipg, want_total) in [
(8u64, 16u32, 16u32, 16u32), (16, 16, 8, 16), (32, 16, 8, 32), (64, 32, 8, 64), (128, 64, 8, 128), ] {
let l = plan_bs_inodes(1024, mib, InodeCount::Count(request));
assert_eq!(
(l.inodes_per_group, l.total_inodes),
(want_ipg, want_total),
"Count({request}) on {mib} MiB at 1024-byte blocks",
);
assert!(
l.inode_table_blocks > 0,
"Count({request}) on {mib} MiB: a group's inode table has no blocks",
);
}
}
#[test]
fn the_size_driven_ratio_matches_mke2fs_at_every_bucket_boundary() {
for (bs, meg) in [(1024u32, 1024u64), (2048, 512), (4096, 256)] {
assert_eq!(
inode_ratio(3 * meg - 1, bs),
8192,
"floppy, {bs}-byte blocks"
);
assert_eq!(inode_ratio(3 * meg, bs), 4096, "small, {bs}-byte blocks");
assert_eq!(
inode_ratio(512 * meg - 1, bs),
4096,
"small, {bs}-byte blocks"
);
assert_eq!(
inode_ratio(512 * meg, bs),
16384,
"default, {bs}-byte blocks"
);
assert_eq!(
inode_ratio(4 * 1024 * 1024 * meg - 1, bs),
16384,
"default, {bs}-byte blocks"
);
assert_eq!(
inode_ratio(4 * 1024 * 1024 * meg, bs),
32768,
"big, {bs}-byte blocks"
);
assert_eq!(
inode_ratio(16 * 1024 * 1024 * meg - 1, bs),
32768,
"big, {bs}-byte blocks"
);
assert_eq!(
inode_ratio(16 * 1024 * 1024 * meg, bs),
65536,
"huge, {bs}-byte blocks"
);
}
assert_eq!(plan_inodes(64, InodeCount::Auto).total_inodes, 16384);
assert_eq!(plan_inodes(512, InodeCount::Auto).total_inodes, 32768);
}
#[test]
fn a_bytes_per_inode_ratio_overrides_the_size_driven_one() {
let bpi = |n: u64| InodeCount::BytesPerInode(NonZeroU64::new(n).unwrap());
assert_eq!(plan_inodes(64, bpi(16384)).total_inodes, 4096);
assert_eq!(plan_inodes(64, bpi(65536)).total_inodes, 1024);
}
#[test]
fn a_density_past_one_groups_bitmap_is_refused() {
let too_many = plan_layout(
&PlanRequest::new(64 * MIB, FeatureSet::default())
.grow(GrowReservation::None)
.inodes(InodeCount::Count(40000)),
)
.unwrap_err();
assert!(matches!(
too_many,
GeometryError::InodesTooDense { limit: 32768, .. }
));
let too_dense = plan_layout(
&PlanRequest::new(64 * MIB, FeatureSet::default())
.grow(GrowReservation::None)
.inodes(InodeCount::BytesPerInode(NonZeroU64::new(1024).unwrap())),
)
.unwrap_err();
assert!(matches!(too_dense, GeometryError::InodesTooDense { .. }));
}
#[test]
fn one_inode_per_block_fills_each_groups_bitmap_at_a_one_kibibyte_block() {
let fs = FeatureSet {
block_size: 1024,
..FeatureSet::default()
};
for kib in [16_385u64, 24_577, 24_600, 32_769] {
let layout = plan_layout(
&PlanRequest::new(kib * 1024, fs)
.grow(GrowReservation::None)
.inodes(InodeCount::BytesPerInode(NonZeroU64::new(1024).unwrap())),
)
.unwrap_or_else(|e| panic!("{kib} KiB: {e}"));
assert!(layout.inodes_per_group <= 8192, "{kib} KiB");
}
}
#[test]
fn auto_density_never_overflows_a_group_at_the_drop_boundary() {
let bpg = 8 * 4096u64;
for extra in [0u64, 1, 2, 7] {
let blocks = bpg + extra;
let l = plan_geo(blocks * 4096, GrowReservation::None, FeatureSet::default())
.unwrap_or_else(|e| panic!("Auto refused {blocks} blocks: {e}"));
assert!(u64::from(l.inodes_per_group) <= bpg);
}
}
#[test]
fn the_reserved_ratio_holds_back_an_exact_share() {
let l = plan_reserved(64, ReservedRatio::DEFAULT);
assert_eq!(l.total_blocks, 16384);
assert_eq!(l.reserved_blocks, 819);
let r = ReservedRatio::from_hundredths_of_percent(150).unwrap();
assert_eq!(plan_reserved(64, r).reserved_blocks, 245);
let none = ReservedRatio::from_hundredths_of_percent(0).unwrap();
assert_eq!(plan_reserved(64, none).reserved_blocks, 0);
let half = ReservedRatio::from_hundredths_of_percent(5000).unwrap();
assert_eq!(plan_reserved(64, half).reserved_blocks, 8192);
assert!(ReservedRatio::from_hundredths_of_percent(5001).is_none());
assert_eq!(half.blocks(u64::MAX), u64::MAX / 2);
assert_eq!(ReservedRatio::DEFAULT.blocks(u64::MAX), u64::MAX / 20);
let past_the_64_bit_product = u64::MAX / 500 + 1;
assert_eq!(
ReservedRatio::DEFAULT.blocks(past_the_64_bit_product),
past_the_64_bit_product / 20
);
}
#[test]
fn four_groups_512mib_matches_ground_truth() {
let l = plan(512);
assert_eq!(l.total_blocks, 131072);
assert_eq!(l.group_count, 4);
assert_eq!(l.inodes_per_group, 8192);
assert_eq!(l.inode_table_blocks, 512);
assert_eq!(l.total_inodes, 32768);
assert_eq!(l.reserved_gdt_blocks, 3);
assert_eq!(l.backup_groups(), vec![1, 3]);
let bmp: Vec<_> = l.groups.iter().map(|g| g.block_bitmap).collect();
assert_eq!(bmp, vec![5, 6, 7, 8]);
let ibmp: Vec<_> = l.groups.iter().map(|g| g.inode_bitmap).collect();
assert_eq!(ibmp, vec![9, 10, 11, 12]);
let itbl: Vec<_> = l.groups.iter().map(|g| g.inode_table).collect();
assert_eq!(itbl, vec![13, 525, 1037, 1549]);
}
#[test]
fn drop_is_flex_aware() {
let l = plan(2049);
assert_eq!(l.group_count, 16);
assert_eq!(l.total_blocks, 524288);
assert_eq!(l.inodes_per_group, 8192);
assert_eq!(l.inode_table_blocks, 512);
let l = plan(129);
assert_eq!(l.group_count, 2);
assert_eq!(l.groups[1].block_count, 256);
assert!(l.groups[1].has_super, "group 1 is a sparse_super backup");
}
#[test]
fn partial_final_group() {
let l = plan(200);
assert_eq!(l.total_blocks, 51200);
assert_eq!(l.group_count, 2);
assert_eq!(l.groups[0].block_count, 32768);
assert_eq!(l.groups[1].block_count, 18432);
}
#[test]
fn seventeen_groups_partial_trailing_flex_reserves_full_slots() {
let l = plan(2176);
assert_eq!(l.group_count, 17);
let g16 = &l.groups[16];
assert_eq!(g16.start_block, 16 * 32768);
assert_eq!(g16.block_bitmap, 16 * 32768);
assert_eq!(g16.inode_bitmap, 16 * 32768 + 16);
assert_eq!(g16.inode_table, 16 * 32768 + 32);
}
#[test]
fn reserved_gdt_is_zero_at_the_grow_target() {
let l = plan_geo(
GROW_32G,
GrowReservation::UpTo(GROW_32G),
FeatureSet::default(),
)
.unwrap();
assert_eq!(l.group_count, 256);
assert_eq!(l.gdt_blocks, 4);
assert_eq!(l.reserved_gdt_blocks, 0);
}
#[test]
fn none_reserves_no_descriptor_headroom() {
let l = plan_geo(64 * MIB, GrowReservation::None, FeatureSet::default()).unwrap();
assert_eq!(l.reserved_gdt_blocks, 0);
assert_eq!(l.max_grow_blocks, l.total_blocks);
}
#[test]
fn max_reserves_the_ceiling_it_can_afford() {
let at =
|mib: u64| plan_geo(mib * MIB, GrowReservation::Max, FeatureSet::default()).unwrap();
let l = at(256);
assert_eq!(l.gdt_blocks, 1);
assert_eq!(l.reserved_gdt_blocks, 1024);
assert_eq!(l.max_grow_blocks, 1025 * 64 * 32768);
assert_eq!(at(1024).reserved_gdt_blocks, 1024);
assert_eq!(at(16 * 1024).reserved_gdt_blocks, 1024);
for (mib, expect) in [(16u64, 64u32), (32, 128), (64, 256), (128, 512)] {
let l = at(mib);
assert_eq!(l.reserved_gdt_blocks, expect, "{mib} MiB");
assert!(
u64::from(l.reserved_gdt_blocks) <= l.total_blocks / 64,
"{mib} MiB spends more than a sixty-fourth on headroom"
);
assert!(
l.max_grow_blocks > 32 * l.total_blocks,
"{mib} MiB grow reach"
);
}
}
#[test]
fn max_never_makes_a_small_filesystem_unplannable() {
for mib in [1u64, 2, 4, 8, 16] {
let l = plan_geo(mib * MIB, GrowReservation::Max, FeatureSet::EXT2)
.unwrap_or_else(|e| panic!("{mib} MiB must plan under Max: {e}"));
assert!(
u64::from(l.reserved_gdt_blocks) <= l.total_blocks / 64,
"{mib} MiB spends more than a sixty-fourth on headroom"
);
assert!(l.max_grow_blocks > l.total_blocks, "{mib} MiB still grows");
}
}
#[test]
fn an_explicit_target_is_not_held_to_the_share() {
let l = plan_geo(
16 * MIB,
GrowReservation::UpTo(8 * 1024 * 1024 * MIB),
FeatureSet::default(),
)
.expect("an explicit target at the format's ceiling is honored");
assert_eq!(l.reserved_gdt_blocks, 1023);
assert!(u64::from(l.reserved_gdt_blocks) > l.total_blocks / 64);
}
#[test]
fn a_reservation_that_cannot_fit_names_its_share_of_the_overhead() {
let err = plan_geo(
4 * MIB,
GrowReservation::UpTo(8 * 1024 * 1024 * MIB),
FeatureSet::default(),
)
.expect_err("a 4 MiB filesystem cannot reserve 1023 descriptor blocks");
let GeometryError::TooSmall {
reserved_gdt_blocks,
overhead,
..
} = err
else {
panic!("expected TooSmall, got {err:?}");
};
assert_eq!(reserved_gdt_blocks, 1023);
assert!(overhead > reserved_gdt_blocks);
let text = err.to_string();
assert!(
text.contains("1023 of them reserved to grow into"),
"{text}"
);
}
#[test]
fn max_never_errors_deep_in_the_tib_range() {
let huge = 4 * 1024 * 1024 * MIB;
let l =
plan_geo(huge, GrowReservation::Max, FeatureSet::default()).expect("Max never errors");
assert!(l.reserved_gdt_blocks <= 1024);
}
#[test]
fn up_to_past_the_resize_ceiling_is_rejected() {
let err = plan_geo(
64 * MIB,
GrowReservation::UpTo(16 * 1024 * 1024 * MIB),
FeatureSet::default(),
)
.unwrap_err();
assert!(matches!(err, GeometryError::GrowTargetTooLarge { .. }));
}
#[test]
fn max_past_thirty_two_bits_reserves_nothing() {
let past = (MAX_32BIT_BLOCKS + 1) * 4096; let l =
plan_geo(past, GrowReservation::Max, FeatureSet::default()).expect("Max never errors");
assert!(
l.total_blocks > MAX_32BIT_BLOCKS,
"this size is past 32 bits"
);
assert_eq!(
l.reserved_gdt_blocks, 0,
"no reserved blocks the 32-bit map could name"
);
}
#[test]
fn up_to_past_thirty_two_bits_is_rejected() {
let past = (MAX_32BIT_BLOCKS + 1) * 4096;
let err =
plan_geo(past, GrowReservation::UpTo(past * 2), FeatureSet::default()).unwrap_err();
assert!(
matches!(err, GeometryError::ReservationNeeds32BitBlocks { .. }),
"expected ReservationNeeds32BitBlocks, got {err:?}"
);
}
#[test]
fn the_default_reservation_is_max() {
assert_eq!(GrowReservation::default(), GrowReservation::Max);
}
#[test]
fn metadata_regions_are_sorted_and_disjoint() {
for mib in [64u64, 200, 512, 2048, 2176] {
let l = plan(mib);
let runs = l.metadata_regions();
for w in runs.windows(2) {
assert!(w[0].end() <= w[1].start, "overlap at {mib} MiB: {w:?}");
}
assert!(l.overhead_blocks() > 0);
assert!(l.overhead_blocks() < l.total_blocks);
}
}
#[test]
fn grow_target_below_size_is_rejected() {
let err = plan_geo(
512 * MIB,
GrowReservation::UpTo(64 * MIB),
FeatureSet::default(),
)
.unwrap_err();
assert!(matches!(err, GeometryError::GrowTargetTooSmall { .. }));
}
#[test]
fn tiny_filesystem_is_rejected() {
let err = plan_geo(
64 * 1024,
GrowReservation::UpTo(64 * MIB),
FeatureSet::default(),
)
.unwrap_err();
assert!(matches!(err, GeometryError::TooSmall { .. }));
}
#[test]
fn invalid_feature_set_propagates() {
let mut fs = FeatureSet::default();
fs.incompat |= crate::feature::Incompat::META_BG;
let err = plan_geo(64 * MIB, GrowReservation::UpTo(GROW_32G), fs).unwrap_err();
assert!(matches!(err, GeometryError::Feature(_)));
}
#[test]
fn overhead_blocks_and_final_group_are_consistent_across_sizes() {
for mib in [64u64, 120, 129, 200, 384, 640, 2048, 2049] {
assert!(
plan_geo(
mib * MIB,
GrowReservation::UpTo(GROW_32G),
FeatureSet::default()
)
.is_ok(),
"sizing {mib} MiB should plan cleanly"
);
}
}
}