use std::borrow::Cow;
use std::collections::BTreeMap;
use std::io::{Seek, Write};
use crate::alloc::{AllocError, Allocator};
use crate::crc32c::crc32c;
use crate::csum as recipe;
use crate::csum::{Checksummer, Crc32c, CsumScheme, NullCsum};
use crate::dir::{DirBlock, DirBlockKind, DirError, DirLayout, HtreeDir, LinearDir};
use crate::escape::hex;
use crate::extent::{
ExtentError, build_leaves, build_tree, node_capacity, plan_tree, tail_offset, write_node,
};
use crate::feature::{FeatureSet, LARGE_FILE_MIN_SIZE, Profile, resize_inode_size};
use crate::geometry::{
BlockRange, GeometryError, GroupLayout, GrowReservation, InodeCount, Layout, PlanRequest,
ReservedRatio, plan_layout,
};
use crate::hash::{HashSignedness, HashVersion};
use crate::io::ByteSink;
use crate::journal::{self, JournalSize};
use crate::model::{
Content, FIRST_USER_INO, FsModel, LOST_FOUND_INO, ModelConfig, ModelError, ModelInode,
build_model,
};
use crate::ondisk::{
BG_BLOCK_UNINIT, BG_INODE_UNINIT, BG_INODE_ZEROED, DIR_TAIL_LEN, DX_ENTRY_LEN, DX_TAIL_LEN,
DirEntry, GroupDescriptor, Inode, InodeFlags, ParseError, SuperBlock, XATTR_CHECKSUM_OFFSET,
encode_block, encode_device, encode_inline, extra_isize_for, get_u16, get_u32,
orphan_entries_len, orphan_tail_bytes, put_u16, put_u32, split_for_storage,
superblock_checksum, write_dir_tail, write_dx_tail,
};
use crate::sizing::Slack;
use crate::source::Source;
use crate::time::Timestamp;
use crate::xattr::Xattr;
const RESIZE_INO: u32 = 7;
fn journal_space(e: impl Into<FormatError>) -> FormatError {
match e.into() {
FormatError::Alloc(AllocError::OutOfSpace {
requested,
available,
}) => FormatError::JournalDoesNotFit {
requested,
available,
},
other => other,
}
}
const JOURNAL_INO: u32 = 8;
const ORPHAN_INO: u32 = FIRST_USER_INO;
fn first_user_inode(feature: &FeatureSet) -> u32 {
if feature.has_orphan_file() {
ORPHAN_INO + 1
} else {
FIRST_USER_INO
}
}
const MAX_SECTORS_WITHOUT_HUGE_FILE: u64 = u32::MAX as u64;
fn orphan_file_blocks(total_blocks: u64) -> u32 {
const RATIO: u64 = 4096;
const MIN: u64 = 32;
const MAX: u64 = 512;
(total_blocks / RATIO).clamp(MIN, MAX) as u32
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum ErrorBehavior {
#[default]
Continue,
RemountReadOnly,
Panic,
}
crate::naming::named_choice!(ErrorBehavior {
ErrorBehavior::Continue => "continue",
ErrorBehavior::RemountReadOnly => "remount-ro",
ErrorBehavior::Panic => "panic",
});
impl ErrorBehavior {
const fn to_s_errors(self) -> u16 {
match self {
Self::Continue => 1,
Self::RemountReadOnly => 2,
Self::Panic => 3,
}
}
}
#[derive(Clone, Copy, Debug)]
#[non_exhaustive]
pub struct FormatOptions {
pub uuid: [u8; 16],
pub time: Timestamp,
pub hash_seed: [u8; 16],
pub hash_version: HashVersion,
pub hash_signedness: HashSignedness,
pub grow: GrowReservation,
pub inodes: InodeCount,
pub reserved: ReservedRatio,
pub volume_name: [u8; 16],
pub feature: FeatureSet,
pub errors: ErrorBehavior,
pub journal: JournalSize,
pub fixed_time: Option<Timestamp>,
}
impl FormatOptions {
fn validate_format_time(&self) -> Result<(), FormatError> {
let secs = self.time.secs;
if secs < 0 || secs > u64::from(u32::MAX) as i64 {
return Err(FormatError::FormatTimeOutOfRange { secs });
}
Ok(())
}
#[must_use]
pub fn new(uuid: [u8; 16], time: Timestamp, hash_seed: [u8; 16]) -> Self {
Self {
uuid,
time,
hash_seed,
hash_version: HashVersion::default(),
hash_signedness: HashSignedness::default(),
grow: GrowReservation::default(),
inodes: InodeCount::default(),
reserved: ReservedRatio::default(),
volume_name: [0; 16],
feature: FeatureSet::default(),
errors: ErrorBehavior::default(),
journal: JournalSize::Auto,
fixed_time: None,
}
}
#[must_use]
pub const fn plan_request(&self, size_bytes: u64) -> PlanRequest {
PlanRequest::new(size_bytes, self.feature)
.grow(self.grow)
.inodes(self.inodes)
.reserved(self.reserved)
}
#[must_use]
pub fn profile(mut self, profile: Profile) -> Self {
self.feature = profile.feature_set();
self
}
}
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum FormatError {
#[error(transparent)]
Io(#[from] std::io::Error),
#[error(transparent)]
Geometry(#[from] GeometryError),
#[error(transparent)]
Model(#[from] ModelError),
#[error(transparent)]
Dir(#[from] DirError),
#[error(transparent)]
Extent(#[from] ExtentError),
#[error(transparent)]
Alloc(#[from] AllocError),
#[error(transparent)]
Parse(#[from] ParseError),
#[error("source needs {needed} inodes but the filesystem has {available}")]
#[non_exhaustive]
TooManyInodes {
needed: u32,
available: u32,
},
#[error("journal of {requested} blocks is below the minimum of {minimum}")]
#[non_exhaustive]
JournalTooSmall {
requested: u32,
minimum: u32,
},
#[error(
"the journal needs {requested} blocks but only {available} are free: build a \
smaller journal, none at all, or a larger filesystem"
)]
#[non_exhaustive]
JournalDoesNotFit {
requested: u64,
available: u64,
},
#[error(
"a filesystem of {blocks} blocks has no room for a journal, which needs at least \
{minimum} blocks: build it without the has_journal feature, or make it larger"
)]
#[non_exhaustive]
FilesystemTooSmallForJournal {
blocks: u64,
minimum: u32,
},
#[error("the {what} is {size} bytes, a large file on a filesystem without large_file")]
#[non_exhaustive]
LargeFileWithoutFeature {
what: &'static str,
size: u64,
},
#[error(
"the {what} is charged {sectors} sectors, past the {limit} an inode records \
without the huge_file feature"
)]
#[non_exhaustive]
BlockCountWithoutHugeFile {
what: &'static str,
sectors: u64,
limit: u64,
},
#[error(
"a file of {blocks} blocks exceeds the {limit} a classic block map reaches at a \
{block_size}-byte block: build it on a feature set with extents, or at a larger \
block size"
)]
#[non_exhaustive]
FileTooLargeForBlockMap {
blocks: u64,
limit: u64,
block_size: u32,
},
#[error("the resize inode's 32-bit block map cannot name block {block}")]
#[non_exhaustive]
ResizeMapNeeds32BitBlocks {
block: u64,
},
#[error("the orphan file's inode {inode} is already held by an entry")]
#[non_exhaustive]
OrphanInodeInUse {
inode: u32,
},
#[error(
"an image of {bytes} bytes cannot be held in memory on this machine; \
stream it with format_to"
)]
#[non_exhaustive]
ImageTooLargeInMemory {
bytes: u64,
},
#[error(
"no filesystem of up to {ceiling} blocks holds the source with the requested room \
to spare"
)]
#[non_exhaustive]
DoesNotFit {
ceiling: u64,
},
#[error("slack share of {hundredths} hundredths of a percent is past the {limit} limit")]
#[non_exhaustive]
SlackShareTooLarge {
hundredths: u16,
limit: u16,
},
#[error("format time of {secs}s is outside the superblock range [0, 2^32) seconds")]
#[non_exhaustive]
FormatTimeOutOfRange {
secs: i64,
},
}
fn map_block(block: u64) -> Result<u32, FormatError> {
u32::try_from(block).map_err(|_| FormatError::ResizeMapNeeds32BitBlocks { block })
}
const DIRECT_BLOCKS: usize = 12;
const INDIRECT_LEVELS: usize = 3;
fn classic_map_reach(block_size: usize) -> u64 {
let ppb = (block_size / 4) as u64;
DIRECT_BLOCKS as u64 + ppb + ppb * ppb + ppb * ppb * ppb
}
pub struct Image {
bytes: Vec<u8>,
layout: Layout,
}
impl Image {
#[must_use]
pub fn as_bytes(&self) -> &[u8] {
&self.bytes
}
#[must_use]
pub fn into_bytes(self) -> Vec<u8> {
self.bytes
}
#[must_use]
pub fn layout(&self) -> &Layout {
&self.layout
}
pub fn write_to(&self, mut w: impl std::io::Write) -> std::io::Result<()> {
w.write_all(&self.bytes)
}
}
pub fn format(
source: impl Source,
size_bytes: u64,
options: FormatOptions,
) -> Result<Image, FormatError> {
let plan = FormatPlan::new(source, size_bytes, options)?;
let image_bytes = plan.layout.total_blocks * u64::from(plan.layout.block_size);
let buffer = crate::io::image_buffer(image_bytes)
.ok_or(FormatError::ImageTooLargeInMemory { bytes: image_bytes })?;
let mut sink = std::io::Cursor::new(buffer);
let layout = plan.write_to(&mut sink)?;
Ok(Image {
bytes: sink.into_inner(),
layout,
})
}
pub fn format_to(
source: impl Source,
size_bytes: u64,
options: FormatOptions,
mut sink: impl Write + Seek,
) -> Result<Layout, FormatError> {
FormatPlan::new(source, size_bytes, options)?.write_to(&mut sink)
}
pub struct FormatPlan {
layout: Layout,
model: FsModel,
options: FormatOptions,
journal_blocks: Option<u32>,
}
impl FormatPlan {
pub fn new(
source: impl Source,
size_bytes: u64,
options: FormatOptions,
) -> Result<Self, FormatError> {
options.validate_format_time()?;
let model = model_of(source, &options)?;
let (layout, journal_blocks) = plan_geometry(&model, &options, size_bytes)?;
free_after_placing(&layout, &options, journal_blocks, &model)?;
Ok(Self {
layout,
model,
options,
journal_blocks,
})
}
pub fn fit(
source: impl Source,
options: FormatOptions,
slack: Slack,
) -> Result<Self, FormatError> {
options.validate_format_time()?;
options.feature.validate().map_err(GeometryError::from)?;
let model = model_of(source, &options)?;
let fitted = crate::fit::search(&model, &options, slack)?;
Ok(Self {
layout: fitted.layout,
model,
options,
journal_blocks: fitted.journal_blocks,
})
}
#[must_use]
pub fn layout(&self) -> &Layout {
&self.layout
}
#[must_use]
pub fn size_bytes(&self) -> u64 {
self.layout.total_blocks * u64::from(self.layout.block_size)
}
#[must_use]
pub fn used_inodes(&self) -> u32 {
self.model.used_inode_count()
}
#[must_use]
pub fn geometry_pin(&self) -> String {
let mut out = String::from("ferrosys-geometry-pin 1\n");
push_layout_pin(&mut out, &self.layout);
out.push_str("journal_blocks ");
match self.journal_blocks {
Some(blocks) => out.push_str(&blocks.to_string()),
None => out.push_str("none"),
}
out.push('\n');
out
}
pub fn write_to(self, mut sink: impl Write + Seek) -> Result<Layout, FormatError> {
let Self {
layout,
model,
options,
journal_blocks,
} = self;
let feature = options.feature;
let bytes = Bytes(ByteSink::new(&mut sink));
let mut writer = Writer::new(&layout, &feature, options, journal_blocks, bytes)?;
writer.materialize(&model)?;
writer.extend_to_full_size()?;
Ok(layout)
}
}
fn model_of(source: impl Source, options: &FormatOptions) -> Result<FsModel, FormatError> {
let feature = options.feature;
let mut config = ModelConfig::new(feature, first_user_inode(&feature), options.time);
config.fixed_time = options.fixed_time;
Ok(build_model(source, config)?)
}
pub(crate) fn plan_geometry(
model: &FsModel,
options: &FormatOptions,
size_bytes: u64,
) -> Result<(Layout, Option<u32>), FormatError> {
let layout = plan_layout(&options.plan_request(size_bytes))?;
if model.used_inode_count() > layout.total_inodes {
return Err(FormatError::TooManyInodes {
needed: model.used_inode_count(),
available: layout.total_inodes,
});
}
let journal_blocks = journal_size(&layout, options)?;
Ok((layout, journal_blocks))
}
pub(crate) fn free_after_placing(
layout: &Layout,
options: &FormatOptions,
journal_blocks: Option<u32>,
model: &FsModel,
) -> Result<u64, FormatError> {
let feature = options.feature;
let mut writer = Writer::new(layout, &feature, *options, journal_blocks, Discard)?;
writer.place(model)?;
Ok(writer.alloc.free_count())
}
fn pin_time(t: Timestamp) -> String {
format!("{}.{}", t.secs, t.nanos)
}
impl FormatOptions {
#[must_use]
pub fn policy_pin(&self) -> String {
let mut policy = String::from("ferrosys-policy-pin 1\n");
let mut identity = String::new();
self.push_pins(&mut policy, &mut identity);
policy
}
#[must_use]
pub fn identity_pin(&self) -> String {
let mut policy = String::new();
let mut identity = String::from("ferrosys-identity-pin 1\n");
self.push_pins(&mut policy, &mut identity);
identity
}
fn push_pins(&self, policy: &mut String, identity: &mut String) {
let Self {
uuid,
time,
hash_seed,
hash_version,
hash_signedness,
grow,
inodes,
reserved,
volume_name,
feature,
errors,
journal,
fixed_time,
} = self;
feature.push_pin_body(policy);
let line = |out: &mut String, key: &str, value: String| {
out.push_str(key);
out.push(' ');
out.push_str(&value);
out.push('\n');
};
line(
policy,
"grow",
match grow {
GrowReservation::None => "none".to_string(),
GrowReservation::Max => "max".to_string(),
GrowReservation::UpTo(bytes) => format!("upto {bytes}"),
},
);
line(
policy,
"inodes",
match inodes {
InodeCount::Auto => "auto".to_string(),
InodeCount::BytesPerInode(n) => format!("bytes_per_inode {n}"),
InodeCount::Count(n) => format!("count {n}"),
},
);
line(
policy,
"reserved",
reserved.hundredths_of_percent().to_string(),
);
line(
policy,
"errors",
match errors {
ErrorBehavior::Continue => "continue".to_string(),
ErrorBehavior::RemountReadOnly => "remount_read_only".to_string(),
ErrorBehavior::Panic => "panic".to_string(),
},
);
line(
policy,
"journal",
match journal {
JournalSize::Auto => "auto".to_string(),
JournalSize::Blocks(n) => format!("blocks {n}"),
},
);
line(
policy,
"hash_version",
match hash_version {
HashVersion::Legacy => "legacy".to_string(),
HashVersion::HalfMd4 => "half_md4".to_string(),
HashVersion::Tea => "tea".to_string(),
},
);
line(
policy,
"hash_signedness",
match hash_signedness {
HashSignedness::Unsigned => "unsigned".to_string(),
HashSignedness::Signed => "signed".to_string(),
},
);
line(
policy,
"timestamp_clamp",
match fixed_time {
None => "none".to_string(),
Some(_) => "fixed".to_string(),
},
);
line(identity, "uuid", hex(uuid));
line(identity, "time", pin_time(*time));
line(identity, "hash_seed", hex(hash_seed));
line(identity, "volume_name", hex(volume_name));
line(
identity,
"fixed_time",
match fixed_time {
None => "none".to_string(),
Some(t) => pin_time(*t),
},
);
}
}
fn push_layout_pin(out: &mut String, layout: &Layout) {
let 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,
} = layout;
for (key, value) in [
("block_size", u64::from(*block_size)),
("total_blocks", *total_blocks),
("blocks_per_group", u64::from(*blocks_per_group)),
("first_data_block", u64::from(*first_data_block)),
("group_count", u64::from(*group_count)),
("inodes_per_group", u64::from(*inodes_per_group)),
("inode_table_blocks", u64::from(*inode_table_blocks)),
("total_inodes", u64::from(*total_inodes)),
("gdt_blocks", u64::from(*gdt_blocks)),
("reserved_gdt_blocks", u64::from(*reserved_gdt_blocks)),
("flex_bg_size", u64::from(*flex_bg_size)),
("max_grow_blocks", *max_grow_blocks),
("reserved_blocks", *reserved_blocks),
] {
out.push_str(key);
out.push(' ');
out.push_str(&value.to_string());
out.push('\n');
}
let digest = groups_digest(groups);
out.push_str(&format!("groups {group_count} crc32c 0x{digest:08x}\n"));
}
fn groups_digest(groups: &[GroupLayout]) -> u32 {
let mut crc = !0u32;
for group in groups {
let GroupLayout {
index,
start_block,
block_count,
has_super,
block_bitmap,
inode_bitmap,
inode_table,
} = group;
crc = crc32c(crc, &u64::from(*index).to_le_bytes());
crc = crc32c(crc, &start_block.to_le_bytes());
crc = crc32c(crc, &u64::from(*block_count).to_le_bytes());
crc = crc32c(crc, &[u8::from(*has_super)]);
crc = crc32c(crc, &block_bitmap.to_le_bytes());
crc = crc32c(crc, &inode_bitmap.to_le_bytes());
crc = crc32c(crc, &inode_table.to_le_bytes());
}
!crc
}
fn journal_size(layout: &Layout, options: &FormatOptions) -> Result<Option<u32>, FormatError> {
if !options.feature.has_journal() {
return Ok(None);
}
let minimum = journal::MIN_JOURNAL_BLOCKS;
let blocks = match options.journal {
JournalSize::Auto => journal::default_journal_blocks(layout.total_blocks).ok_or(
FormatError::FilesystemTooSmallForJournal {
blocks: layout.total_blocks,
minimum,
},
)?,
JournalSize::Blocks(n) if n >= minimum => n,
JournalSize::Blocks(n) => {
return Err(FormatError::JournalTooSmall {
requested: n,
minimum,
});
}
};
let size = u64::from(blocks) * u64::from(options.feature.block_size);
if size >= LARGE_FILE_MIN_SIZE && !options.feature.has_large_file() {
return Err(FormatError::LargeFileWithoutFeature {
what: "journal",
size,
});
}
Ok(Some(blocks))
}
trait Sink {
fn write_at(&mut self, offset: u64, bytes: &[u8]) -> Result<(), FormatError>;
fn keeps_bytes(&self) -> bool;
fn extend_to(&mut self, size: u64) -> Result<(), FormatError>;
}
struct Bytes<W>(ByteSink<W>);
impl<W: Write + Seek> Sink for Bytes<W> {
fn write_at(&mut self, offset: u64, bytes: &[u8]) -> Result<(), FormatError> {
Ok(self.0.write_at(offset, bytes)?)
}
fn keeps_bytes(&self) -> bool {
true
}
fn extend_to(&mut self, size: u64) -> Result<(), FormatError> {
Ok(self.0.extend_to(size)?)
}
}
struct Discard;
impl Sink for Discard {
fn write_at(&mut self, _offset: u64, _bytes: &[u8]) -> Result<(), FormatError> {
Ok(())
}
fn keeps_bytes(&self) -> bool {
false
}
fn extend_to(&mut self, _size: u64) -> Result<(), FormatError> {
Ok(())
}
}
struct Writer<'a, S> {
layout: &'a Layout,
feature: &'a FeatureSet,
options: FormatOptions,
alloc: Allocator,
sink: S,
block_size: usize,
csum: Box<dyn Checksummer>,
dir: Box<dyn DirLayout>,
inodes: BTreeMap<u32, Inode>,
gdt_bytes: Vec<u8>,
journal_backup: Option<[u32; 17]>,
journal_blocks: Option<u32>,
}
impl<'a, S: Sink> Writer<'a, S> {
fn new(
layout: &'a Layout,
feature: &'a FeatureSet,
options: FormatOptions,
journal_blocks: Option<u32>,
sink: S,
) -> Result<Self, FormatError> {
let block_size = layout.block_size as usize;
let csum: Box<dyn Checksummer> = if feature.has_metadata_csum() {
Box::new(Crc32c::new(&options.uuid))
} else {
Box::new(NullCsum)
};
let dir: Box<dyn DirLayout> = if feature.has_dir_index() {
Box::new(HtreeDir {
seed: options.hash_seed,
version: options.hash_version,
signedness: options.hash_signedness,
checksums: feature.has_metadata_csum(),
})
} else {
Box::new(LinearDir {
tail_len: if feature.has_metadata_csum() {
DIR_TAIL_LEN
} else {
0
},
})
};
Ok(Self {
layout,
feature,
options,
alloc: Allocator::new(layout)?,
sink,
block_size,
csum,
dir,
inodes: BTreeMap::new(),
gdt_bytes: Vec::new(),
journal_backup: None,
journal_blocks,
})
}
fn place(&mut self, model: &FsModel) -> Result<(), FormatError> {
for minode in model.inodes.values() {
let inode = self.materialize_inode(minode)?;
self.inodes.insert(minode.number, inode);
}
self.materialize_reserved_inodes()
}
fn materialize(&mut self, model: &FsModel) -> Result<(), FormatError> {
self.place(model)?;
self.write_inode_tables()?;
self.write_bitmaps_and_descriptors(model)?;
self.write_superblocks(model)?;
Ok(())
}
fn write_at(&mut self, offset: u64, bytes: &[u8]) -> Result<(), FormatError> {
self.sink.write_at(offset, bytes)
}
fn extend_to_full_size(&mut self) -> Result<(), FormatError> {
let size = self.layout.total_blocks * u64::from(self.layout.block_size);
self.sink.extend_to(size)
}
fn new_inode(&self) -> Inode {
Inode::empty(self.feature.inode_size)
}
fn stamp_structural_times(&self, inode: &mut Inode) {
let t = self.options.fixed_time.unwrap_or(self.options.time);
inode.atime = t;
inode.ctime = t;
inode.mtime = t;
inode.crtime = t;
}
fn materialize_inode(&mut self, minode: &ModelInode) -> Result<Inode, FormatError> {
let mut inode = self.new_inode();
inode.mode = minode.mode;
inode.uid = minode.uid;
inode.gid = minode.gid;
inode.links_count = minode.links_count;
inode.atime = minode.atime;
inode.ctime = minode.ctime;
inode.mtime = minode.mtime;
inode.crtime = minode.crtime;
match &minode.content {
Content::Directory(children) => {
let entries: Vec<DirEntry> = children
.iter()
.map(|c| DirEntry {
inode: c.inode,
file_type: c.file_type,
name: c.name.clone(),
})
.collect();
let mut blocks = self.dir.build_blocks(&entries, self.block_size)?;
if minode.number == LOST_FOUND_INO {
let min_blocks = (16 * 1024usize).div_ceil(self.block_size);
while blocks.len() < min_blocks {
blocks.push(DirBlock {
bytes: self.empty_dir_block(),
kind: DirBlockKind::Entries,
});
}
}
let indexed = blocks
.iter()
.any(|b| matches!(b.kind, DirBlockKind::Index { .. }));
self.write_dir_checksums(minode.number, &mut blocks);
let bytes: Vec<Vec<u8>> = blocks.into_iter().map(|b| b.bytes).collect();
self.place_blocks(minode.number, &mut inode, bytes.iter())?;
if indexed {
inode.flags |= InodeFlags::INDEX;
}
}
Content::File(content) => {
let count = content.len().div_ceil(self.block_size as u64);
let physical = self.map_data_blocks(minode.number, &mut inode, count, "file")?;
if self.sink.keeps_bytes() {
let block_size = self.block_size;
let mut blocks = physical.blocks();
content.for_each_window(|_, window| {
for (data, phys) in block_chunks(window, block_size).zip(&mut blocks) {
self.write_block(phys, data.as_ref())?;
}
Ok::<(), FormatError>(())
})?;
}
inode.size = content.len();
}
Content::SlowSymlink(target) => {
let block_size = self.block_size;
self.place_blocks(minode.number, &mut inode, block_chunks(target, block_size))?;
inode.size = target.len() as u64;
}
Content::FastSymlink(target) => {
inode.block[..target.len()].copy_from_slice(target);
inode.size = target.len() as u64;
}
Content::Device { major, minor } => {
let (b0, b1) = encode_device(*major, *minor);
put_u32(&mut inode.block, 0, b0);
put_u32(&mut inode.block, 4, b1);
}
Content::Special => {
}
}
self.encode_xattrs(&mut inode, &minode.xattrs)?;
Ok(inode)
}
fn encode_xattrs(&mut self, inode: &mut Inode, xattrs: &[Xattr]) -> Result<(), FormatError> {
if xattrs.is_empty() {
return Ok(());
}
let region_len = inode.inline_xattr_capacity(self.feature.inode_size);
let (inline, spilled) = split_for_storage(xattrs, region_len);
if !inline.is_empty() {
inode.inline_xattr = encode_inline(&inline, region_len)
.expect("the inline side of the split fits the region by construction");
}
if !spilled.is_empty() {
let mut block = encode_block(&spilled, self.block_size);
let phys = self.alloc.allocate_one()?;
if self.csum.scheme().writes_object_checksums() {
let c = recipe::xattr_block(&*self.csum, phys, &block);
put_u32(&mut block, XATTR_CHECKSUM_OFFSET, c);
}
self.write_block(phys, &block)?;
inode.file_acl = phys;
self.charge_sectors(
inode,
inode.blocks + self.sectors_per_block(),
"extended attributes",
)?;
}
Ok(())
}
fn map_data_blocks(
&mut self,
ino: u32,
inode: &mut Inode,
count: u64,
what: &'static str,
) -> Result<BlockRuns, FormatError> {
self.check_sectors(count * self.sectors_per_block(), what)?;
if self.feature.has_extents() {
inode.flags = InodeFlags::EXTENTS;
let ranges = self.alloc.allocate(count)?;
let meta = self.root_extent_tree(ino, inode, &ranges)?;
self.charge_sectors(inode, (count + meta) * self.sectors_per_block(), what)?;
Ok(BlockRuns::from_ranges(ranges))
} else {
self.build_classic_map(inode, count, what)
}
}
fn place_blocks<B: AsRef<[u8]>>(
&mut self,
ino: u32,
inode: &mut Inode,
blocks: impl ExactSizeIterator<Item = B>,
) -> Result<(), FormatError> {
let count = blocks.len();
let physical = self.map_data_blocks(ino, inode, count as u64, "file")?;
for (data, phys) in blocks.zip(physical.blocks()) {
self.write_block(phys, data.as_ref())?;
}
if inode.size == 0 {
inode.size = (count * self.block_size) as u64;
}
Ok(())
}
fn build_classic_map(
&mut self,
inode: &mut Inode,
n: u64,
what: &'static str,
) -> Result<BlockRuns, FormatError> {
self.check_sectors(n * self.sectors_per_block(), what)?;
let reach = classic_map_reach(self.block_size);
if n > reach {
return Err(FormatError::FileTooLargeForBlockMap {
blocks: n,
limit: reach,
block_size: self.block_size as u32,
});
}
inode.flags = InodeFlags::NONE;
let mut physical = BlockRuns::default();
let mut meta = 0u64;
for slot in 0..n.min(DIRECT_BLOCKS as u64) {
let phys = self.alloc.allocate_one()?;
physical.push(phys);
put_u32(&mut inode.block, slot as usize * 4, map_block(phys)?);
}
for level in 1..=INDIRECT_LEVELS {
if physical.len() >= n {
break;
}
let root = self.build_indirect(level as u32, n, &mut physical, &mut meta)?;
put_u32(
&mut inode.block,
(DIRECT_BLOCKS + level - 1) * 4,
map_block(root)?,
);
}
self.charge_sectors(inode, (n + meta) * self.sectors_per_block(), what)?;
Ok(physical)
}
fn build_indirect(
&mut self,
level: u32,
n: u64,
physical: &mut BlockRuns,
meta: &mut u64,
) -> Result<u64, FormatError> {
let ind_block = self.alloc.allocate_one()?;
*meta += 1;
let ppb = self.block_size / 4;
let mut ptrs = vec![0u8; self.block_size];
for slot in 0..ppb {
if physical.len() >= n {
break;
}
let child = if level == 1 {
let phys = self.alloc.allocate_one()?;
physical.push(phys);
phys
} else {
self.build_indirect(level - 1, n, physical, meta)?
};
put_u32(&mut ptrs, slot * 4, map_block(child)?);
}
self.write_block(ind_block, &ptrs)?;
Ok(ind_block)
}
fn root_extent_tree(
&mut self,
ino: u32,
inode: &mut Inode,
ranges: &[BlockRange],
) -> Result<u64, FormatError> {
let inline_capacity = node_capacity(Inode::BLOCK_BYTES);
let node_capacity = node_capacity(self.block_size);
let leaves = build_leaves(ranges)?;
let shape = plan_tree(leaves.len(), inline_capacity, node_capacity)?;
let mut node_blocks = Vec::with_capacity(shape.node_blocks);
for _ in 0..shape.node_blocks {
node_blocks.push(self.alloc.allocate_one()?);
}
let tree = build_tree(&leaves, inline_capacity, node_capacity, &node_blocks)?;
for node in &tree.nodes {
let mut buf = vec![0u8; self.block_size];
write_node(&node.node, node_capacity, &mut buf)?;
self.write_extent_node_checksum(ino, &mut buf);
self.write_block(node.block, &buf)?;
}
write_node(&tree.root, inline_capacity, &mut inode.block)?;
Ok(shape.node_blocks as u64)
}
fn write_extent_node_checksum(&self, ino: u32, buf: &mut [u8]) {
if !self.csum.scheme().writes_object_checksums() {
return;
}
let tail = tail_offset(self.block_size);
let c = self
.csum
.crc32c(recipe::inode_seed(&*self.csum, ino, 0), &buf[..tail]);
put_u32(buf, tail, c);
}
fn empty_dir_block(&self) -> Vec<u8> {
let tail_len = if self.csum.scheme().writes_object_checksums() {
DIR_TAIL_LEN
} else {
0
};
let usable = self.block_size - tail_len;
let mut block = vec![0u8; self.block_size];
put_u32(&mut block, 0, 0); put_u16(&mut block, 4, usable as u16); if tail_len != 0 {
write_dir_tail(&mut block[usable..usable + DIR_TAIL_LEN], 0)
.expect("tail slice is exactly DIR_TAIL_LEN");
}
block
}
fn write_dir_checksums(&self, dir_ino: u32, blocks: &mut [DirBlock]) {
if !self.csum.scheme().writes_object_checksums() {
return;
}
let seed = recipe::inode_seed(&*self.csum, dir_ino, 0);
for block in blocks {
let mut c = seed;
match block.kind {
DirBlockKind::Entries => {
let covered = self.block_size - DIR_TAIL_LEN;
c = self.csum.crc32c(c, &block.bytes[..covered]);
put_u32(&mut block.bytes, self.block_size - 4, c);
}
DirBlockKind::Index {
count_offset,
limit,
} => {
let count = get_u16(&block.bytes, count_offset + 2) as usize;
let covered = count_offset + DX_ENTRY_LEN * count;
c = self.csum.crc32c(c, &block.bytes[..covered]);
c = self.csum.crc32c(c, &[0u8; DX_TAIL_LEN]);
write_dx_tail(&mut block.bytes, count_offset, limit, c)
.expect("the index block reserved its tail");
}
}
}
}
fn materialize_reserved_inodes(&mut self) -> Result<(), FormatError> {
for n in [1u32, 3, 4, 5, 6, 9, 10] {
self.inodes.insert(n, self.new_inode());
}
let resize = if self.feature.has_resize_inode() {
self.materialize_resize_inode()?
} else {
self.new_inode()
};
self.inodes.insert(RESIZE_INO, resize);
let journal = match self.journal_blocks {
Some(blocks) => self.materialize_journal_inode(blocks)?,
None => self.new_inode(),
};
self.inodes.insert(JOURNAL_INO, journal);
if self.feature.has_orphan_file() {
if self.inodes.contains_key(&ORPHAN_INO) {
return Err(FormatError::OrphanInodeInUse { inode: ORPHAN_INO });
}
let orphan = self.materialize_orphan_inode()?;
self.inodes.insert(ORPHAN_INO, orphan);
}
Ok(())
}
fn materialize_orphan_inode(&mut self) -> Result<Inode, FormatError> {
let blocks = orphan_file_blocks(self.layout.total_blocks);
let ranges = match self.alloc.allocate_contiguous(u64::from(blocks)) {
Some(range) => vec![range],
None => self.alloc.allocate(u64::from(blocks))?,
};
let mut inode = self.new_inode();
inode.mode = 0o100600;
inode.links_count = 1;
self.stamp_structural_times(&mut inode);
inode.flags = InodeFlags::EXTENTS;
let meta = self.root_extent_tree(ORPHAN_INO, &mut inode, &ranges)?;
inode.size = u64::from(blocks) * u64::from(self.feature.block_size);
self.charge_sectors(
&mut inode,
(u64::from(blocks) + meta) * self.sectors_per_block(),
"orphan file",
)?;
let entries_len = orphan_entries_len(self.block_size);
let entries = vec![0u8; entries_len];
for block in ranges.iter().flat_map(|r| r.start..r.start + r.len) {
let c =
recipe::orphan_block(&*self.csum, ORPHAN_INO, inode.generation, block, &entries);
let offset = block * u64::from(self.layout.block_size) + entries_len as u64;
self.write_at(offset, &orphan_tail_bytes(c))?;
}
Ok(inode)
}
fn materialize_journal_inode(&mut self, blocks: u32) -> Result<Inode, FormatError> {
let size = u64::from(blocks) * u64::from(self.feature.block_size);
let sb = journal::build_superblock(&journal::JournalParams::new(
self.feature.block_size,
blocks,
self.options.uuid,
));
let mut inode = self.new_inode();
inode.mode = 0o100600;
inode.links_count = 1;
self.stamp_structural_times(&mut inode);
if self.feature.has_extents() {
let ranges = match self.alloc.allocate_contiguous(u64::from(blocks)) {
Some(range) => vec![range],
None => self
.alloc
.allocate(u64::from(blocks))
.map_err(journal_space)?,
};
self.write_block(ranges[0].start, &sb)?;
inode.flags = InodeFlags::EXTENTS;
let meta = self.root_extent_tree(JOURNAL_INO, &mut inode, &ranges)?;
self.charge_sectors(
&mut inode,
(u64::from(blocks) + meta) * self.sectors_per_block(),
"journal",
)?;
} else {
let physical = self
.build_classic_map(&mut inode, u64::from(blocks), "journal")
.map_err(journal_space)?;
let first = physical
.blocks()
.next()
.expect("a journal of at least the minimum length maps a first block");
self.write_block(first, &sb)?;
}
inode.size = size;
let mut backup = [0u32; 17];
for (i, word) in inode.block.as_chunks::<4>().0.iter().enumerate() {
backup[i] = get_u32(word, 0);
}
backup[15] = (inode.size >> 32) as u32;
backup[16] = inode.size as u32;
self.journal_backup = Some(backup);
Ok(inode)
}
fn materialize_resize_inode(&mut self) -> Result<Inode, FormatError> {
let mut inode = self.new_inode();
inode.mode = 0o100600;
inode.links_count = 1;
self.stamp_structural_times(&mut inode);
inode.flags = InodeFlags::NONE;
let reserved = self.layout.reserved_gdt_blocks;
let bs = self.block_size;
let fdb = u64::from(self.layout.first_data_block);
let gdt = u64::from(self.layout.gdt_blocks);
let backups = self.layout.backup_groups();
let slots = u64::from(self.layout.block_size) / 4;
let dind_block = self.alloc.allocate_one()?;
let mut dind = vec![0u8; bs];
for r in 0..u64::from(reserved) {
let primary = fdb + 1 + gdt + r; let slot = (gdt + r) % slots;
put_u32(&mut dind, (slot * 4) as usize, map_block(primary)?);
}
self.write_block(dind_block, &dind)?;
for r in 0..u64::from(reserved) {
let ind_block = fdb + 1 + gdt + r;
let mut ind = vec![0u8; bs];
for (j, &bg) in backups.iter().enumerate() {
let start = fdb + u64::from(bg) * u64::from(self.layout.blocks_per_group);
let backup_resv = start + 1 + gdt + r;
put_u32(&mut ind, j * 4, map_block(backup_resv)?);
}
self.write_block(ind_block, &ind)?;
}
inode.size = resize_inode_size(self.layout.block_size);
let data_blocks = 1 + u64::from(reserved) + u64::from(reserved) * backups.len() as u64;
self.charge_sectors(
&mut inode,
data_blocks * self.sectors_per_block(),
"resize inode",
)?;
put_u32(&mut inode.block, 13 * 4, map_block(dind_block)?);
Ok(inode)
}
fn write_inode_tables(&mut self) -> Result<(), FormatError> {
let ipg = self.layout.inodes_per_group;
let inode_size = self.feature.inode_size;
let isize = inode_size as usize;
let writes_checksums = self.csum.scheme().writes_object_checksums();
let inodes = std::mem::take(&mut self.inodes);
let mut bytes = vec![0u8; isize];
for (&number, inode) in &inodes {
let group = (number - 1) / ipg;
let index = ((number - 1) % ipg) as usize;
let table = self.layout.groups[group as usize].inode_table;
let offset = table * u64::from(self.layout.block_size) + (index * isize) as u64;
if !writes_checksums && inode.mode == 0 && inode.links_count == 0 {
bytes.iter_mut().for_each(|b| *b = 0);
self.write_at(offset, &bytes)?;
continue;
}
inode.write_to(&mut bytes, inode_size)?;
if writes_checksums {
let has_hi = Inode::has_checksum_hi(inode_size, inode.extra_isize);
let c = recipe::inode(&*self.csum, number, inode.generation, &bytes, has_hi);
put_u16(&mut bytes, Inode::CHECKSUM_LO_OFFSET, (c & 0xffff) as u16);
if has_hi {
put_u16(&mut bytes, Inode::CHECKSUM_HI_OFFSET, (c >> 16) as u16);
}
}
self.write_at(offset, &bytes)?;
}
self.inodes = inodes;
Ok(())
}
fn write_bitmaps_and_descriptors(&mut self, model: &FsModel) -> Result<(), FormatError> {
let ipg = self.layout.inodes_per_group;
let desc_size = self.feature.desc_size() as usize;
let mut gdt_bytes = vec![0u8; self.layout.gdt_blocks as usize * self.block_size];
let mut dir_counts = vec![0u32; self.layout.group_count as usize];
for minode in model.inodes.values() {
if minode.is_dir() {
dir_counts[((minode.number - 1) / ipg) as usize] += 1;
}
}
let uninit_bg = self.csum.scheme().uninit_bg_semantics();
let last_group = self.layout.group_count - 1;
let bb_len = recipe::block_bitmap_len(self.layout.blocks_per_group);
let ib_len = recipe::inode_bitmap_len(ipg);
for g in 0..self.layout.group_count {
let gl = &self.layout.groups[g as usize];
let used_inodes = used_inodes_in_group(g, ipg, model.first_free_inode);
let inode_uninit = uninit_bg && used_inodes == 0;
let block_uninit = uninit_bg
&& !self.layout.is_flex_head(g)
&& g != last_group
&& self.group_is_dataless(g);
let bbmp = if block_uninit {
vec![0u8; self.block_size]
} else {
self.alloc
.group_bitmap(g)
.expect("a group of this layout has a bitmap")
.to_vec()
};
let ibmp = if inode_uninit {
vec![0u8; self.block_size]
} else {
self.inode_bitmap(g, model.first_free_inode)
};
let block_bitmap_csum = if block_uninit {
0
} else {
recipe::bitmap(&*self.csum, &bbmp[..bb_len])
};
let inode_bitmap_csum = if inode_uninit {
0
} else {
recipe::bitmap(&*self.csum, &ibmp[..ib_len])
};
let mut flags = if uninit_bg { BG_INODE_ZEROED } else { 0 };
if inode_uninit {
flags |= BG_INODE_UNINIT;
}
if block_uninit {
flags |= BG_BLOCK_UNINIT;
}
let mut desc = GroupDescriptor {
block_bitmap: gl.block_bitmap,
inode_bitmap: gl.inode_bitmap,
inode_table: gl.inode_table,
free_blocks_count: self.alloc.group_free_count(g),
free_inodes_count: ipg - used_inodes,
used_dirs_count: dir_counts[g as usize],
flags,
itable_unused: if uninit_bg { ipg - used_inodes } else { 0 },
checksum: 0,
block_bitmap_csum,
inode_bitmap_csum,
};
desc.checksum = self.group_desc_csum(g, &desc, desc_size);
let off = g as usize * desc_size;
desc.write_to(&mut gdt_bytes[off..off + desc_size], desc_size)
.expect("descriptor buffer is sized to the whole table");
self.write_block(gl.block_bitmap, &bbmp)?;
self.write_block(gl.inode_bitmap, &ibmp)?;
}
let gdt_start =
(u64::from(self.layout.first_data_block) + 1) * u64::from(self.layout.block_size);
self.write_at(gdt_start, &gdt_bytes)?;
self.gdt_bytes = gdt_bytes;
Ok(())
}
fn group_is_dataless(&self, g: u32) -> bool {
let block_count = u64::from(self.layout.groups[g as usize].block_count);
let free = u64::from(self.alloc.group_free_count(g));
let meta = self.layout.super_overhead_region(g).map_or(0, |r| r.len);
block_count - free == meta
}
fn group_desc_csum(&self, group: u32, desc: &GroupDescriptor, desc_size: usize) -> u16 {
match self.csum.scheme() {
CsumScheme::None => return 0,
CsumScheme::Crc32c => {}
}
let mut buf = [0u8; GroupDescriptor::SIZE_64];
desc.write_to(&mut buf[..desc_size], desc_size)
.expect("descriptor buffer holds a full descriptor");
recipe::group_descriptor(&*self.csum, group, &buf[..desc_size])
}
fn inode_bitmap(&self, group: u32, first_free_inode: u32) -> Vec<u8> {
let ipg = self.layout.inodes_per_group;
let mut bmp = vec![0u8; self.block_size];
let base = u64::from(group) * u64::from(ipg);
for i in 0..ipg {
let inode = base + u64::from(i) + 1;
if inode < u64::from(first_free_inode) {
bmp[(i / 8) as usize] |= 1 << (i % 8);
}
}
for i in ipg..(self.block_size as u32 * 8) {
bmp[(i / 8) as usize] |= 1 << (i % 8);
}
bmp
}
fn write_superblocks(&mut self, model: &FsModel) -> Result<(), FormatError> {
let sb = self.build_superblock(model);
let mut primary = sb.to_bytes();
self.finalize_sb_csum(&mut primary);
self.write_at(1024, &primary)?;
let gdt = std::mem::take(&mut self.gdt_bytes);
for g in self.layout.backup_groups() {
let start = (u64::from(self.layout.first_data_block)
+ u64::from(g) * u64::from(self.layout.blocks_per_group))
* u64::from(self.layout.block_size);
let mut backup = sb.clone();
backup.block_group_nr = u16::try_from(g).unwrap_or(u16::MAX);
let mut bytes = backup.to_bytes();
self.finalize_sb_csum(&mut bytes);
self.write_at(start, &bytes)?;
self.write_at(start + u64::from(self.layout.block_size), &gdt)?;
}
Ok(())
}
fn finalize_sb_csum(&self, bytes: &mut [u8; SuperBlock::SIZE]) {
if !self.csum.scheme().writes_object_checksums() {
return;
}
let c = superblock_checksum(bytes);
put_u32(bytes, SuperBlock::CHECKSUM_OFFSET, c);
}
fn build_superblock(&self, model: &FsModel) -> SuperBlock {
let mut sb = SuperBlock::new();
let l = self.layout;
sb.inodes_count = l.total_inodes;
sb.blocks_count = l.total_blocks;
sb.r_blocks_count = l.reserved_blocks;
sb.free_blocks_count = self.alloc.free_count();
sb.free_inodes_count = l.total_inodes - model.used_inode_count();
sb.first_data_block = l.first_data_block;
sb.log_block_size = l.block_size.trailing_zeros() - 10;
sb.log_cluster_size = sb.log_block_size;
sb.blocks_per_group = l.blocks_per_group;
sb.clusters_per_group = l.blocks_per_group;
sb.inodes_per_group = l.inodes_per_group;
sb.wtime = self.options.time.secs as u32;
sb.max_mnt_count = 0xffff;
sb.state = crate::ondisk::STATE_CLEAN;
sb.errors = self.options.errors.to_s_errors();
sb.lastcheck = self.options.time.secs as u32;
sb.rev_level = 1; sb.first_ino = 11;
sb.inode_size = self.feature.inode_size;
sb.feature_compat = self.feature.compat.bits();
sb.feature_incompat = self.feature.incompat.bits();
sb.feature_ro_compat = self.feature.ro_compat.bits();
sb.uuid = self.options.uuid;
sb.volume_name = self.options.volume_name;
if let Some(backup) = self.journal_backup {
sb.journal_inum = JOURNAL_INO;
sb.jnl_backup_type = 1; sb.jnl_blocks = backup;
}
if self.feature.has_orphan_file() {
sb.orphan_file_inum = ORPHAN_INO;
}
if self.feature.has_csum_seed() {
sb.checksum_seed = self.csum.base_seed();
}
sb.reserved_gdt_blocks = l.reserved_gdt_blocks as u16;
sb.hash_seed = self.options.hash_seed;
sb.def_hash_version = self.options.hash_version.to_u8();
sb.flags = self.options.hash_signedness.to_flag();
sb.desc_size = if self.feature.is_64bit() {
self.feature.desc_size()
} else {
0
};
sb.default_mount_opts = 0x0c; sb.mkfs_time = self.options.time.secs as u32;
sb.min_extra_isize = extra_isize_for(self.feature.inode_size);
sb.want_extra_isize = sb.min_extra_isize;
sb.log_groups_per_flex = if self.feature.has_flex_bg() {
l.flex_bg_size.trailing_zeros() as u8
} else {
0
};
sb.checksum_type = match self.csum.scheme() {
CsumScheme::None => 0,
CsumScheme::Crc32c => 1,
};
let journal_blocks = if self.feature.has_journal() {
self.journal_blocks.map_or(0, u64::from)
} else {
0
};
sb.overhead_clusters =
u32::try_from(l.overhead_blocks() + u64::from(l.first_data_block) + journal_blocks)
.unwrap_or(u32::MAX);
sb
}
fn sectors_per_block(&self) -> u64 {
u64::from(self.layout.block_size) / 512
}
fn charge_sectors(
&self,
inode: &mut Inode,
sectors: u64,
what: &'static str,
) -> Result<(), FormatError> {
self.check_sectors(sectors, what)?;
inode.blocks = sectors;
Ok(())
}
fn check_sectors(&self, sectors: u64, what: &'static str) -> Result<(), FormatError> {
if !self.feature.has_huge_file() && sectors > MAX_SECTORS_WITHOUT_HUGE_FILE {
return Err(FormatError::BlockCountWithoutHugeFile {
what,
sectors,
limit: MAX_SECTORS_WITHOUT_HUGE_FILE,
});
}
Ok(())
}
fn write_block(&mut self, block: u64, data: &[u8]) -> Result<(), FormatError> {
self.write_at(block * u64::from(self.layout.block_size), data)
}
}
fn block_chunks(bytes: &[u8], block_size: usize) -> impl ExactSizeIterator<Item = Cow<'_, [u8]>> {
bytes.chunks(block_size).map(move |chunk| {
if chunk.len() == block_size {
Cow::Borrowed(chunk)
} else {
let mut block = vec![0u8; block_size];
block[..chunk.len()].copy_from_slice(chunk);
Cow::Owned(block)
}
})
}
#[derive(Default)]
struct BlockRuns {
runs: Vec<BlockRange>,
count: u64,
}
impl BlockRuns {
fn from_ranges(runs: Vec<BlockRange>) -> Self {
let count = runs.iter().map(|run| run.len).sum();
Self { runs, count }
}
fn push(&mut self, block: u64) {
match self.runs.last_mut() {
Some(run) if run.end() == block => run.len += 1,
_ => self.runs.push(BlockRange {
start: block,
len: 1,
}),
}
self.count += 1;
}
const fn len(&self) -> u64 {
self.count
}
fn blocks(&self) -> impl Iterator<Item = u64> + '_ {
self.runs.iter().flat_map(|run| run.start..run.end())
}
}
fn used_inodes_in_group(group: u32, ipg: u32, first_free_inode: u32) -> u32 {
let base = group * ipg; (first_free_inode - 1).saturating_sub(base).min(ipg)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::read::Reader;
use crate::source::TreeBuilder;
const MIB: u64 = 1024 * 1024;
fn opts() -> FormatOptions {
let mut o = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16]);
o.grow = GrowReservation::UpTo(32 * 1024 * MIB);
o
}
fn pinned_options() -> FormatOptions {
let mut o = FormatOptions::new([0x11; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16]);
o.grow = GrowReservation::Max;
o
}
fn pinned_plan() -> FormatPlan {
FormatPlan::new(TreeBuilder::new(), 64 * MIB, pinned_options()).expect("plan")
}
#[test]
fn block_runs_hold_a_mapping_as_its_runs_and_hand_back_every_block_in_order() {
let mut runs = BlockRuns::default();
let order: Vec<u64> = (100..112).chain(113..1137).chain([2000, 2001]).collect();
for &block in &order {
runs.push(block);
}
assert_eq!(runs.len(), order.len() as u64);
assert_eq!(runs.runs.len(), 3);
assert!(runs.blocks().eq(order.iter().copied()));
let ranges = vec![
BlockRange { start: 7, len: 3 },
BlockRange { start: 40, len: 2 },
];
let runs = BlockRuns::from_ranges(ranges);
assert_eq!(runs.len(), 5);
assert!(runs.blocks().eq([7, 8, 9, 40, 41]));
}
#[test]
fn the_policy_pin_is_the_document_it_documents() {
let expected = "\
ferrosys-policy-pin 1
compat 0x0000103c has_journal ext_attr resize_inode dir_index orphan_file
incompat 0x000022c2 filetype extent 64bit flex_bg metadata_csum_seed
ro_compat 0x0000046b sparse_super large_file huge_file dir_nlink extra_isize metadata_csum
block_size 4096
inode_size 256
grow max
inodes auto
reserved 500
errors continue
journal auto
hash_version half_md4
hash_signedness unsigned
timestamp_clamp none
";
assert_eq!(pinned_options().policy_pin(), expected);
}
#[test]
fn the_identity_pin_is_the_document_it_documents() {
let expected = "\
ferrosys-identity-pin 1
uuid 11111111111111111111111111111111
time 1700000000.0
hash_seed 00000000000000000000000000000000
volume_name 00000000000000000000000000000000
fixed_time none
";
assert_eq!(pinned_options().identity_pin(), expected);
}
#[test]
fn the_geometry_pin_is_the_document_it_documents() {
let expected = "\
ferrosys-geometry-pin 1
block_size 4096
total_blocks 16384
blocks_per_group 32768
first_data_block 0
group_count 1
inodes_per_group 16384
inode_table_blocks 1024
total_inodes 16384
gdt_blocks 1
reserved_gdt_blocks 256
flex_bg_size 16
max_grow_blocks 538968064
reserved_blocks 819
groups 1 crc32c 0x8a137015
journal_blocks 1024
";
assert_eq!(pinned_plan().geometry_pin(), expected);
}
#[test]
fn the_policy_pin_holds_still_while_the_image_varies() {
let base = pinned_options().policy_pin();
for (what, mut options) in [
("uuid", pinned_options()),
("time", pinned_options()),
("hash_seed", pinned_options()),
("volume_name", pinned_options()),
] {
match what {
"uuid" => options.uuid = [0x99; 16],
"time" => options.time = Timestamp::from_secs(1_800_000_123),
"hash_seed" => options.hash_seed = [0x44; 16],
_ => options.volume_name = *b"board-two\0\0\0\0\0\0\0",
}
assert_eq!(base, options.policy_pin(), "{what} reached the policy pin");
assert_ne!(
pinned_options().identity_pin(),
options.identity_pin(),
"{what} did not reach the identity pin"
);
}
let small = FormatPlan::new(TreeBuilder::new(), 64 * MIB, pinned_options()).expect("plan");
let large = FormatPlan::new(TreeBuilder::new(), 512 * MIB, pinned_options()).expect("plan");
assert_eq!(base, pinned_options().policy_pin());
assert_ne!(
small.geometry_pin(),
large.geometry_pin(),
"two sizes pin the same geometry"
);
}
#[test]
fn a_source_too_large_for_the_size_is_refused_by_the_plan() {
let time = Timestamp::from_secs(1_700_000_000);
let src = TreeBuilder::new().file(
b"/big".to_vec(),
vec![0xAB; 32 * MIB as usize],
crate::Metadata::new(0o644, time),
);
let planned = FormatPlan::new(src, 16 * MIB, pinned_options());
assert!(
matches!(
planned,
Err(FormatError::Alloc(AllocError::OutOfSpace { .. }))
),
"{:?}",
planned.err()
);
}
#[test]
fn every_option_that_moves_bytes_moves_one_of_the_two_pins() {
type Case = (&'static str, bool, Box<dyn Fn(&mut FormatOptions)>);
let cases: Vec<Case> = vec![
(
"uuid",
false,
Box::new(|o: &mut FormatOptions| o.uuid = [0x22; 16]),
),
(
"time",
false,
Box::new(|o: &mut FormatOptions| o.time = Timestamp::from_secs(1_700_000_001)),
),
(
"hash_seed",
false,
Box::new(|o: &mut FormatOptions| o.hash_seed = [0x33; 16]),
),
(
"volume_name",
false,
Box::new(|o: &mut FormatOptions| o.volume_name = *b"rootfs\0\0\0\0\0\0\0\0\0\0"),
),
(
"fixed_time",
true,
Box::new(|o: &mut FormatOptions| {
o.fixed_time = Some(Timestamp::from_secs(1_600_000_000));
}),
),
(
"hash_version",
true,
Box::new(|o: &mut FormatOptions| o.hash_version = HashVersion::Tea),
),
(
"hash_signedness",
true,
Box::new(|o: &mut FormatOptions| o.hash_signedness = HashSignedness::Signed),
),
(
"grow",
true,
Box::new(|o: &mut FormatOptions| o.grow = GrowReservation::None),
),
(
"inodes",
true,
Box::new(|o: &mut FormatOptions| o.inodes = InodeCount::Count(2048)),
),
(
"reserved",
true,
Box::new(|o: &mut FormatOptions| {
o.reserved = ReservedRatio::from_hundredths_of_percent(1000).expect("10%");
}),
),
(
"feature",
true,
Box::new(|o: &mut FormatOptions| o.feature = FeatureSet::EXT2),
),
(
"errors",
true,
Box::new(|o: &mut FormatOptions| o.errors = ErrorBehavior::Panic),
),
(
"journal",
true,
Box::new(|o: &mut FormatOptions| o.journal = JournalSize::Blocks(2048)),
),
];
let base_policy = pinned_options().policy_pin();
let base_identity = pinned_options().identity_pin();
for (name, is_policy, change) in cases {
let mut o = pinned_options();
change(&mut o);
let moved = if is_policy {
base_policy != o.policy_pin()
} else {
base_identity != o.identity_pin()
};
let which = if is_policy { "policy" } else { "identity" };
assert!(moved, "changing {name} left the {which} pin unchanged");
}
}
#[test]
fn a_moved_group_placement_moves_the_digest() {
let mut layout = pinned_plan().layout().clone();
let before = groups_digest(&layout.groups);
layout.groups[0].inode_table += 1;
assert_ne!(
before,
groups_digest(&layout.groups),
"a moved inode table changed no digest"
);
}
#[test]
fn the_profile_setter_seeds_the_matching_feature_set() {
let base = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16]);
assert_eq!(base.profile(Profile::Ext2).feature, FeatureSet::EXT2);
assert_eq!(base.profile(Profile::Ext3).feature, FeatureSet::EXT3);
assert_eq!(base.profile(Profile::Ext4).feature, FeatureSet::DEFAULT);
let seeded = base.profile(Profile::Ext3);
assert_eq!(seeded.uuid, base.uuid);
assert_eq!(seeded.grow, base.grow);
assert_eq!(seeded.inodes, base.inodes);
}
#[test]
fn a_volume_label_is_written_into_the_superblock_and_reads_back() {
let mut o = opts();
o.volume_name = *b"rootfs\0\0\0\0\0\0\0\0\0\0";
let image = format(TreeBuilder::new(), 64 * MIB, o).expect("format");
assert_eq!(
&image.as_bytes()[1024 + 0x78..1024 + 0x78 + 16],
b"rootfs\0\0\0\0\0\0\0\0\0\0"
);
let reader = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
assert_eq!(
reader.superblock().volume_name,
*b"rootfs\0\0\0\0\0\0\0\0\0\0"
);
let image = format(TreeBuilder::new(), 64 * MIB, opts()).expect("format");
assert_eq!(image.as_bytes()[1024 + 0x78..1024 + 0x78 + 16], [0u8; 16]);
}
#[test]
fn the_error_behavior_reaches_the_superblock_and_reads_back() {
let read_errors = |image: &Image| {
u16::from_le_bytes(
image.as_bytes()[1024 + 0x3c..1024 + 0x3c + 2]
.try_into()
.expect("two bytes"),
)
};
assert_eq!(
read_errors(&format(TreeBuilder::new(), 64 * MIB, opts()).expect("format")),
1,
"the default continues, matching the kernel"
);
for (policy, expected) in [
(ErrorBehavior::Continue, 1u16),
(ErrorBehavior::RemountReadOnly, 2),
(ErrorBehavior::Panic, 3),
] {
let mut o = opts();
o.errors = policy;
let image = format(TreeBuilder::new(), 64 * MIB, o).expect("format");
assert_eq!(
read_errors(&image),
expected,
"{policy:?} in the raw superblock"
);
let reader = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
assert_eq!(reader.superblock().errors, expected, "{policy:?} read back");
}
}
#[test]
fn the_orphan_file_size_follows_the_block_count_between_its_floor_and_ceiling() {
assert_eq!(orphan_file_blocks(2048), 32, "below the floor");
assert_eq!(orphan_file_blocks(131_072), 32, "exactly at the floor");
assert_eq!(orphan_file_blocks(262_144), 64);
assert_eq!(orphan_file_blocks(524_288), 128);
assert_eq!(orphan_file_blocks(2_097_152), 512, "exactly at the ceiling");
assert_eq!(orphan_file_blocks(67_108_864), 512, "above the ceiling");
}
#[test]
fn an_entry_on_the_orphan_files_inode_is_refused() {
let options = opts();
let feature = options.feature;
assert!(feature.has_orphan_file());
let layout = plan_layout(&options.plan_request(64 * MIB)).expect("layout");
let model = build_model(
TreeBuilder::new().file(
b"/f".to_vec(),
b"x".to_vec(),
crate::source::Metadata::new(0o644, options.time),
),
ModelConfig::new(feature, ORPHAN_INO, options.time),
)
.expect("model");
assert!(model.inodes.contains_key(&ORPHAN_INO), "the entry took it");
let journal = journal_size(&layout, &options).expect("the journal size is realizable");
let mut writer = Writer::new(&layout, &feature, options, journal, Discard)
.expect("an allocator for a layout this size");
let err = writer
.materialize(&model)
.expect_err("the collision is refused");
assert!(
matches!(err, FormatError::OrphanInodeInUse { inode } if inode == ORPHAN_INO),
"expected OrphanInodeInUse, got {err:?}"
);
}
#[test]
fn the_orphan_file_takes_the_inode_below_the_first_entry() {
let with = FeatureSet::default();
assert!(with.has_orphan_file());
assert_eq!(first_user_inode(&with), ORPHAN_INO + 1);
let mut without = FeatureSet::default();
without.compat = crate::feature::Compat::from_bits(
without.compat.bits()
& !(crate::feature::Compat::HAS_JOURNAL.bits()
| crate::feature::Compat::ORPHAN_FILE.bits()),
);
assert_eq!(first_user_inode(&without), FIRST_USER_INO);
}
#[test]
fn the_block_mapped_family_round_trips_direct_and_indirect_files() {
use crate::source::Metadata;
let time = Timestamp::from_secs(1_700_000_000);
let bs = 4096usize;
let direct = vec![0xa1u8; 5 * bs - 17];
let single = vec![0xb2u8; 20 * bs];
let mut double = vec![0u8; 1040 * bs];
for (i, byte) in double.iter_mut().enumerate() {
*byte = (i % 251) as u8;
}
for profile in [Profile::Ext2, Profile::Ext3] {
let src = TreeBuilder::new()
.file(
b"/direct".to_vec(),
direct.clone(),
Metadata::new(0o644, time),
)
.file(
b"/single".to_vec(),
single.clone(),
Metadata::new(0o644, time),
)
.file(
b"/double".to_vec(),
double.clone(),
Metadata::new(0o644, time),
);
let mut o = FormatOptions::new([7u8; 16], time, [0u8; 16]).profile(profile);
o.grow = GrowReservation::UpTo(32 * 1024 * MIB);
let image = format(src, 64 * MIB, o).expect("format block-mapped");
let mut r = Reader::open(std::io::Cursor::new(image.into_bytes())).expect("open");
assert_eq!(
r.profile(),
profile,
"reads back as the family it was written for"
);
for (name, want) in [
(b"/direct".as_slice(), &direct),
(b"/single".as_slice(), &single),
(b"/double".as_slice(), &double),
] {
let (_, inode) = r.lookup(name).expect("lookup");
assert!(
!inode.flags.contains(crate::ondisk::InodeFlags::EXTENTS),
"{profile} {}: block-mapped inode carries no EXTENTS flag",
String::from_utf8_lossy(name)
);
let got = r.read_data(&inode).expect("read");
assert_eq!(got, *want, "{profile} {}", String::from_utf8_lossy(name));
}
}
}
#[test]
fn a_checksum_off_profile_writes_zero_group_flags() {
let mut feature = FeatureSet::default();
feature.ro_compat = crate::feature::RoCompat::from_bits(
feature.ro_compat.bits() & !crate::feature::RoCompat::METADATA_CSUM.bits(),
);
feature.incompat = crate::feature::Incompat::from_bits(
feature.incompat.bits() & !crate::feature::Incompat::CSUM_SEED.bits(),
);
assert!(!feature.has_metadata_csum());
feature.validate().expect("a checksum-off profile is valid");
let mut o = opts();
o.feature = feature;
let image = format(TreeBuilder::new(), 64 * MIB, o).expect("format");
let group_count = image.layout().group_count;
let mut r = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
for g in 0..group_count {
let desc = r.group_descriptor(g).expect("group descriptor");
assert_eq!(
desc.flags, 0,
"group {g}: bg_flags must be zero without metadata_csum"
);
}
}
#[test]
fn the_resize_map_refuses_a_block_past_thirty_two_bits() {
assert_eq!(map_block(0).unwrap(), 0);
assert_eq!(map_block(u64::from(u32::MAX)).unwrap(), u32::MAX);
let err = map_block(u64::from(u32::MAX) + 1).unwrap_err();
assert!(matches!(
err,
FormatError::ResizeMapNeeds32BitBlocks { block } if block == u64::from(u32::MAX) + 1
));
}
#[test]
fn a_format_time_past_the_superblock_range_is_rejected() {
let mut o = opts();
o.time = Timestamp::from_secs(i64::from(u32::MAX) + 1);
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected FormatTimeOutOfRange");
};
assert!(
matches!(err, FormatError::FormatTimeOutOfRange { secs } if secs == i64::from(u32::MAX) + 1),
"expected FormatTimeOutOfRange, got {err:?}"
);
}
#[test]
fn the_default_max_reservation_formats_and_reads_back() {
let plain = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16]);
assert_eq!(plain.grow, GrowReservation::Max);
let image = format(TreeBuilder::new(), 64 * MIB, plain).expect("default format");
assert_eq!(
image.layout().reserved_gdt_blocks,
256,
"Max reserves the share of a 64 MiB filesystem it can spare"
);
let mut r = Reader::open(std::io::Cursor::new(image.as_bytes())).expect("open");
let resize = r.inode(7).expect("resize inode");
let dind = u32::from_le_bytes([
resize.block[52],
resize.block[53],
resize.block[54],
resize.block[55],
]);
assert_ne!(
dind, 0,
"the reservation hangs off the double-indirect slot"
);
}
#[test]
fn streaming_a_format_writes_the_same_bytes_as_collecting_one() {
use crate::source::Metadata;
let time = Timestamp::from_secs(1_700_000_000);
let source = || {
TreeBuilder::new()
.directory(b"/etc".to_vec(), Metadata::new(0o755, time))
.file(
b"/etc/hostname".to_vec(),
b"ferrosys\n".to_vec(),
Metadata::new(0o644, time),
)
.symlink(
b"/etc/mtab".to_vec(),
b"/proc/self/mounts".to_vec(),
Metadata::new(0o777, time),
)
};
let collected = format(source(), 64 * MIB, opts()).expect("format");
let mut streamed = std::io::Cursor::new(Vec::new());
let layout = format_to(source(), 64 * MIB, opts(), &mut streamed).expect("format_to");
let streamed = streamed.into_inner();
assert_eq!(layout, *collected.layout());
assert_eq!(
streamed.len(),
collected.as_bytes().len(),
"a streamed image is extended to the filesystem's full size"
);
assert_eq!(streamed, collected.as_bytes(), "the images differ");
}
#[test]
fn a_streamed_image_leaves_the_blocks_it_never_writes_alone() {
let mut sink = std::io::Cursor::new(Vec::new());
let layout = format_to(TreeBuilder::new(), 64 * MIB, opts(), &mut sink).expect("format_to");
let bytes = sink.into_inner();
assert_eq!(
bytes.len() as u64,
layout.total_blocks * u64::from(layout.block_size)
);
let last = bytes.len() - layout.block_size as usize;
assert!(bytes[last..].iter().all(|&b| b == 0));
}
#[test]
fn explicit_journal_size_is_honored() {
let mut o = opts();
o.journal = JournalSize::Blocks(2048);
let image = format(TreeBuilder::new(), 512 * MIB, o).expect("format");
let mut r = Reader::open(std::io::Cursor::new(image.as_bytes())).unwrap();
let jsb = r.journal_superblock().unwrap().expect("journal");
assert_eq!(jsb.max_len, 2048);
assert_eq!(r.inode(8).unwrap().size, 2048 * 4096);
}
#[test]
fn the_classic_block_map_reaches_what_its_pointer_words_hold() {
assert_eq!(classic_map_reach(1024), 16_843_020); assert_eq!(classic_map_reach(2048), 134_480_396); assert_eq!(classic_map_reach(4096), 1_074_791_436); }
#[test]
fn a_block_count_the_feature_words_cannot_record_is_refused_rather_than_wrapped() {
let mut o = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16])
.profile(Profile::Ext3);
o.grow = GrowReservation::None;
assert!(
!o.feature.has_huge_file(),
"the block-mapped profiles cannot carry huge_file"
);
o.journal = JournalSize::Blocks(536_870_912);
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected BlockCountWithoutHugeFile");
};
assert!(
matches!(
err,
FormatError::BlockCountWithoutHugeFile {
what: "journal",
limit,
..
} if limit == u64::from(u32::MAX)
),
"expected BlockCountWithoutHugeFile, got {err:?}"
);
o.journal = JournalSize::Blocks(536_870_911);
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected the log not to fit in 64 MiB");
};
assert!(
!matches!(err, FormatError::BlockCountWithoutHugeFile { .. }),
"the count one below the field's reach is a count it records: {err:?}"
);
}
#[test]
fn a_file_past_the_classic_block_maps_reach_is_refused_rather_than_mapped_short() {
let mut o = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16])
.profile(Profile::Ext3);
o.feature.block_size = 1024;
o.grow = GrowReservation::None;
o.journal = JournalSize::Blocks(16_843_021);
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected FileTooLargeForBlockMap");
};
assert!(
matches!(
err,
FormatError::FileTooLargeForBlockMap {
blocks: 16_843_021,
limit: 16_843_020,
block_size: 1024,
}
),
"expected FileTooLargeForBlockMap, got {err:?}"
);
o.journal = JournalSize::Blocks(16_843_020);
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected the log not to fit in 64 MiB");
};
assert!(
matches!(err, FormatError::JournalDoesNotFit { .. }),
"expected JournalDoesNotFit, got {err:?}"
);
}
#[test]
fn a_journal_past_the_large_file_bound_is_rejected_without_the_feature() {
let mut o = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16])
.profile(Profile::Ext3);
o.feature.block_size = 1024;
o.feature = o
.feature
.with_feature("large_file", false)
.expect("a known name");
o.grow = GrowReservation::None;
o.journal = JournalSize::Blocks(2 * 1024 * 1024); let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("expected LargeFileWithoutFeature");
};
assert!(
matches!(
err,
FormatError::LargeFileWithoutFeature {
what: "journal",
size
} if size == 2 * 1024 * MIB
),
"expected LargeFileWithoutFeature for the journal, got {err:?}"
);
let mut o = FormatOptions::new([1u8; 16], Timestamp::from_secs(1_700_000_000), [0u8; 16])
.profile(Profile::Ext3);
o.feature.block_size = 1024;
o.grow = GrowReservation::None;
o.journal = JournalSize::Blocks(2 * 1024 * 1024);
assert!(o.feature.has_large_file());
let Err(err) = format(TreeBuilder::new(), 64 * MIB, o) else {
panic!("a 2 GiB log does not fit a 64 MiB image");
};
assert!(
matches!(err, FormatError::JournalDoesNotFit { .. }),
"the feature check must give way to the space the journal needs, got {err:?}"
);
}
#[test]
fn journal_below_the_minimum_is_rejected() {
let mut o = opts();
o.journal = JournalSize::Blocks(512);
assert!(matches!(
format(TreeBuilder::new(), 512 * MIB, o),
Err(FormatError::JournalTooSmall {
requested: 512,
minimum: 1024
})
));
}
#[test]
fn auto_journal_maps_as_a_single_extent() {
let file = tempfile::tempfile().expect("temp file");
format_to(TreeBuilder::new(), 2048 * MIB, opts(), &file).expect("format");
let mut r = Reader::open(file).unwrap();
let inode = r.inode(8).unwrap();
let entries = u16::from_le_bytes([inode.block[2], inode.block[3]]);
assert_eq!(entries, 1, "journal should map as one contiguous extent");
}
}