use std::collections::{BTreeMap, HashMap};
use crate::fidelity::{Direction, FidelityReport, LossPolicy, Property, WRITE_BITS};
use crate::path::canonical_key;
use crate::source::{
ClassifyError, Darwin, EntryKind, FileContent, LinkEnd, LinkStep, Metadata, PathFault,
SourceEntry, classify_paths, follow_hard_link,
};
use crate::time::{DosTimestamp, Timestamp};
use super::geometry::FatLayout;
use super::name::{DirNames, NameError, PlacedName, folded};
use super::ondisk::{Attributes, DIR_ENTRY_SIZE};
pub const MAX_FILE_BYTES: u64 = u32::MAX as u64;
pub const MAX_DIRECTORY_BYTES: u64 = MAX_DIRECTORY_ENTRIES * DIR_ENTRY_SIZE as u64;
pub const MAX_DIRECTORY_ENTRIES: u64 = 1 << 16;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum TimeField {
Modification,
Access,
Birth,
}
impl TimeField {
#[must_use]
pub const fn as_str(self) -> &'static str {
match self {
TimeField::Modification => "modification time",
TimeField::Access => "access time",
TimeField::Birth => "birth time",
}
}
}
impl core::fmt::Display for TimeField {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.write_str(self.as_str())
}
}
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ModelError {
#[error(
"{}: its contents are declared by length alone, and this writer reads a file's bytes \
itself",
crate::escape::printable(.path)
)]
#[non_exhaustive]
ContentsNotHeld {
path: Vec<u8>,
},
#[error("{}: {source}", crate::escape::printable(.path))]
#[non_exhaustive]
Name {
path: Vec<u8>,
#[source]
source: NameError,
},
#[error("path {} has a `..` component", crate::escape::printable(.path))]
#[non_exhaustive]
InvalidComponent {
path: Vec<u8>,
},
#[error("path {} is used by more than one entry", crate::escape::printable(.path))]
#[non_exhaustive]
Duplicate {
path: Vec<u8>,
},
#[error(
"{} and {} differ only in case, which no FAT driver distinguishes",
crate::escape::printable(.path),
crate::escape::printable(.other)
)]
#[non_exhaustive]
Indistinguishable {
path: Vec<u8>,
other: Vec<u8>,
},
#[error("path {} has no parent directory", crate::escape::printable(.path))]
#[non_exhaustive]
ParentMissing {
path: Vec<u8>,
},
#[error("path {} has a parent that is not a directory", crate::escape::printable(.path))]
#[non_exhaustive]
ParentNotDir {
path: Vec<u8>,
},
#[error("entry {} names the root but is not a directory", crate::escape::printable(.path))]
#[non_exhaustive]
RootNotDirectory {
path: Vec<u8>,
},
#[error(
"hard link {} targets {}, which does not exist",
crate::escape::printable(.path),
crate::escape::printable(.target)
)]
#[non_exhaustive]
HardlinkTargetMissing {
path: Vec<u8>,
target: Vec<u8>,
},
#[error(
"hard link {} targets the directory {}",
crate::escape::printable(.path),
crate::escape::printable(.target)
)]
#[non_exhaustive]
HardlinkTargetIsDirectory {
path: Vec<u8>,
target: Vec<u8>,
},
#[error(
"hard link {} names a chain of links that returns to itself",
crate::escape::printable(.path)
)]
#[non_exhaustive]
HardlinkCycle {
path: Vec<u8>,
},
#[error(
"{}: a {field} of {secs} seconds past the epoch is outside the {min} to {max} a FAT \
directory entry represents",
crate::escape::printable(.path)
)]
#[non_exhaustive]
TimeOutOfRange {
path: Vec<u8>,
field: TimeField,
secs: i64,
min: i64,
max: i64,
},
#[error(
"{}: a file of {bytes} bytes exceeds the {limit} a directory entry's length field \
records",
crate::escape::printable(.path)
)]
#[non_exhaustive]
FileTooLarge {
path: Vec<u8>,
bytes: u64,
limit: u64,
},
#[error(
"{}: a FAT volume cannot carry the {} of this entry",
crate::escape::printable(.path),
.property.as_str()
)]
#[non_exhaustive]
LossNotAccepted {
path: Vec<u8>,
property: Property,
},
#[error(
"the directory {} needs {needed} bytes of entries and the format holds {limit} in one",
crate::escape::printable(.path)
)]
#[non_exhaustive]
DirectoryTooLarge {
path: Vec<u8>,
needed: u64,
limit: u64,
},
#[error(
"the root directory needs {needed} entries and its region holds {capacity}; FAT12 \
and FAT16 fix that capacity when the volume is planned"
)]
#[non_exhaustive]
RootDirectoryFull {
needed: u32,
capacity: u32,
},
#[error("the tree needs {needed} clusters and the volume has {available}")]
#[non_exhaustive]
VolumeFull {
needed: u64,
available: u32,
},
}
fn file_size(bytes: u64, path: &[u8]) -> Result<u32, ModelError> {
u32::try_from(bytes).map_err(|_| ModelError::FileTooLarge {
path: path.to_vec(),
bytes,
limit: MAX_FILE_BYTES,
})
}
pub(crate) const ROOT_DIR: usize = 0;
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub(crate) struct ClusterRun {
pub first: u32,
pub count: u32,
}
impl ClusterRun {
pub(crate) const fn is_empty(self) -> bool {
self.count == 0
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub(crate) struct EntryTimes {
pub create: DosTimestamp,
pub write: DosTimestamp,
pub access_date: u16,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Node {
Dir(usize),
File {
content: usize,
size: u32,
run: ClusterRun,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct ModelEntry {
pub name: PlacedName,
pub attributes: Attributes,
pub times: EntryTimes,
pub node: Node,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct ModelDir {
pub parent: Option<usize>,
pub entries: Vec<ModelEntry>,
pub times: EntryTimes,
pub run: ClusterRun,
}
impl ModelDir {
fn slots(&self, index: usize, has_label: bool) -> u64 {
let leading = if index == ROOT_DIR {
u64::from(has_label)
} else {
2
};
leading
+ self
.entries
.iter()
.map(|e| e.name.slots() as u64)
.sum::<u64>()
}
}
#[derive(Debug)]
pub(crate) struct FatModel {
pub dirs: Vec<ModelDir>,
pub contents: Vec<FileContent>,
pub fidelity: FidelityReport,
pub used_clusters: u32,
pub next_free: u32,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct ModelConfig {
pub loss: LossPolicy,
pub has_label: bool,
}
pub(crate) fn place_tree(
entries: Vec<SourceEntry>,
config: &ModelConfig,
) -> Result<PlacedTree, ModelError> {
Builder::new(config).place_all(entries)
}
pub(crate) fn build_model(
entries: Vec<SourceEntry>,
layout: &FatLayout,
config: &ModelConfig,
) -> Result<FatModel, ModelError> {
let mut placed = Builder::new(config).place_all(entries)?;
let (used_clusters, next_free) = placed.allocate(layout, config)?;
Ok(placed.finish(used_clusters, next_free))
}
#[derive(Clone, PartialEq, Eq, Debug)]
enum Class {
Dir,
File {
content: usize,
size: u32,
},
Link(Vec<u8>),
Unrepresentable,
}
struct Builder<'a> {
config: &'a ModelConfig,
dirs: Vec<ModelDir>,
contents: Vec<FileContent>,
fidelity: FidelityReport,
classes: BTreeMap<Vec<u8>, Class>,
dir_of: HashMap<Vec<u8>, usize>,
names: Vec<DirNames>,
folded: Vec<HashMap<String, Vec<u8>>>,
}
impl<'a> Builder<'a> {
fn new(config: &'a ModelConfig) -> Self {
let root = ModelDir {
parent: None,
entries: Vec::new(),
times: EntryTimes::default(),
run: ClusterRun::default(),
};
Self {
config,
dirs: vec![root],
contents: Vec::new(),
fidelity: FidelityReport::new(),
classes: BTreeMap::new(),
dir_of: HashMap::from([(Vec::new(), 0usize)]),
names: vec![DirNames::new()],
folded: vec![HashMap::new()],
}
}
fn place_all(mut self, mut entries: Vec<SourceEntry>) -> Result<PlacedTree, ModelError> {
entries.sort_by_key(|entry| canonical_key(&entry.path));
self.classify(&entries)?;
for entry in entries {
self.place(entry)?;
}
self.check_directory_capacity()?;
Ok(PlacedTree {
dirs: self.dirs,
contents: self.contents,
fidelity: self.fidelity,
})
}
fn classify(&mut self, entries: &[SourceEntry]) -> Result<(), ModelError> {
let mut next_content = 0usize;
self.classes = classify_paths(
entries,
|entry, _| {
Ok(match &entry.kind {
EntryKind::Directory => Class::Dir,
EntryKind::File(content) => {
if matches!(content, FileContent::Declared { .. }) {
return Err(ModelError::ContentsNotHeld {
path: entry.path.clone(),
});
}
let size = file_size(content.len(), &entry.path)?;
let content = next_content;
next_content += 1;
Class::File { content, size }
}
EntryKind::HardLink { target } => Class::Link(canonical_key(target)),
_ => Class::Unrepresentable,
})
},
|class| *class == Class::Dir,
)
.map_err(|e| match e {
ClassifyError::Class(e) => e,
ClassifyError::Path(PathFault::Traversal, path) => {
ModelError::InvalidComponent { path }
}
ClassifyError::Path(PathFault::Duplicate, path) => ModelError::Duplicate { path },
ClassifyError::Path(PathFault::RootNotDirectory, path) => {
ModelError::RootNotDirectory { path }
}
})?;
Ok(())
}
fn place(&mut self, entry: SourceEntry) -> Result<(), ModelError> {
let SourceEntry {
path,
kind,
meta,
xattrs,
darwin,
} = entry;
let key = canonical_key(&path);
if key.is_empty() {
return Ok(());
}
let split = key.iter().rposition(|&b| b == b'/');
let (parent_key, name) = match split {
Some(at) => (key[..at].to_vec(), key[at + 1..].to_vec()),
None => (Vec::new(), key.clone()),
};
let parent = match self.dir_of.get(&parent_key) {
Some(&index) => index,
None if self.classes.contains_key(&parent_key) => {
return Err(ModelError::ParentNotDir { path });
}
None => return Err(ModelError::ParentMissing { path }),
};
let Some(node) = self.node_for(kind, &key, &path)? else {
return Ok(());
};
let placed = self.name_in(parent, &name, &path)?;
let times = self.times_for(&meta, &path)?;
let is_dir = matches!(node, Node::Dir(_));
self.record_losses(&meta, &xattrs, darwin.as_ref(), is_dir, &path)?;
let mut attributes = if is_dir {
Attributes::DIRECTORY
} else {
Attributes::ARCHIVE
};
if meta.mode & WRITE_BITS == 0 {
attributes |= Attributes::READ_ONLY;
}
if let Node::Dir(index) = node {
self.dirs[index].times = times;
}
self.dirs[parent].entries.push(ModelEntry {
name: placed,
attributes,
times,
node,
});
Ok(())
}
fn check_directory_capacity(&self) -> Result<(), ModelError> {
for (index, dir) in self.dirs.iter().enumerate() {
let needed = dir.slots(index, self.config.has_label) * DIR_ENTRY_SIZE as u64;
if needed > MAX_DIRECTORY_BYTES {
let key = self
.dir_of
.iter()
.find_map(|(key, &at)| (at == index).then_some(key.as_slice()))
.unwrap_or_default();
let mut path = b"/".to_vec();
path.extend_from_slice(key);
return Err(ModelError::DirectoryTooLarge {
path,
needed,
limit: MAX_DIRECTORY_BYTES,
});
}
}
Ok(())
}
fn node_for(
&mut self,
kind: EntryKind,
key: &[u8],
path: &[u8],
) -> Result<Option<Node>, ModelError> {
match kind {
EntryKind::Directory => {
let index = self.dirs.len();
self.dirs.push(ModelDir {
parent: None,
entries: Vec::new(),
times: EntryTimes::default(),
run: ClusterRun::default(),
});
self.names.push(DirNames::new());
self.folded.push(HashMap::new());
self.dir_of.insert(key.to_vec(), index);
Ok(Some(Node::Dir(index)))
}
EntryKind::File(content) => {
let Some(Class::File { content: at, size }) = self.classes.get(key).cloned() else {
unreachable!("a file was classified as something else")
};
assert_eq!(at, self.contents.len(), "the two passes fell out of step");
self.contents.push(content);
Ok(Some(Node::File {
content: at,
size,
run: ClusterRun::default(),
}))
}
EntryKind::HardLink { target } => match self.resolve_link(&target, path)? {
Some((content, size)) => {
self.lose(Property::Kind, path)?;
Ok(Some(Node::File {
content,
size,
run: ClusterRun::default(),
}))
}
None => {
self.lose(Property::Kind, path)?;
Ok(None)
}
},
_ => {
self.lose(Property::Kind, path)?;
Ok(None)
}
}
}
fn resolve_link(&self, target: &[u8], path: &[u8]) -> Result<Option<(usize, u32)>, ModelError> {
match follow_hard_link(target, self.classes.len(), |key| {
match self.classes.get(key) {
Some(Class::File { content, size }) => LinkStep::File((*content, *size)),
Some(Class::Dir) => LinkStep::Directory,
Some(Class::Unrepresentable) => LinkStep::Unrepresentable,
Some(Class::Link(next)) => LinkStep::Link(next.clone()),
None => LinkStep::Missing,
}
}) {
LinkEnd::File(found) => Ok(Some(found)),
LinkEnd::Unrepresentable => Ok(None),
LinkEnd::Directory => Err(ModelError::HardlinkTargetIsDirectory {
path: path.to_vec(),
target: target.to_vec(),
}),
LinkEnd::Missing => Err(ModelError::HardlinkTargetMissing {
path: path.to_vec(),
target: target.to_vec(),
}),
LinkEnd::Cycle => Err(ModelError::HardlinkCycle {
path: path.to_vec(),
}),
}
}
fn name_in(
&mut self,
parent: usize,
name: &[u8],
path: &[u8],
) -> Result<PlacedName, ModelError> {
if let Some(key) = folded(name) {
if let Some(other) = self.folded[parent].get(&key) {
return Err(ModelError::Indistinguishable {
path: path.to_vec(),
other: other.clone(),
});
}
self.folded[parent].insert(key, path.to_vec());
}
let placed = self.names[parent]
.place(name)
.map_err(|source| ModelError::Name {
path: path.to_vec(),
source,
})?;
let rendered = crate::fat::name::render(&placed.short);
if let Some(key) = folded(rendered.as_bytes())
&& folded(name).as_deref() != Some(key.as_str())
{
if let Some(other) = self.folded[parent].get(&key) {
return Err(ModelError::Indistinguishable {
path: path.to_vec(),
other: other.clone(),
});
}
self.folded[parent].insert(key, path.to_vec());
}
Ok(placed)
}
fn times_for(&mut self, meta: &Metadata, path: &[u8]) -> Result<EntryTimes, ModelError> {
let write = self.encode(meta.mtime, TimeField::Modification, path)?;
let access = self.encode(meta.atime, TimeField::Access, path)?;
let create = match meta.btime {
Some(btime) => self.encode(btime, TimeField::Birth, path)?,
None => write,
};
let birth_precise = meta
.btime
.is_none_or(|btime| btime.nanos.is_multiple_of(10_000_000));
if meta.mtime.secs % 2 != 0 || meta.mtime.nanos != 0 || !birth_precise {
self.fidelity
.record(Direction::Dropped, path, Property::TimePrecision);
}
Ok(EntryTimes {
create,
write,
access_date: access.date,
})
}
fn encode(
&self,
time: Timestamp,
field: TimeField,
path: &[u8],
) -> Result<DosTimestamp, ModelError> {
DosTimestamp::encode(time).ok_or_else(|| ModelError::TimeOutOfRange {
path: path.to_vec(),
field,
secs: time.secs,
min: DosTimestamp::SECS_MIN,
max: DosTimestamp::SECS_MAX,
})
}
fn record_losses(
&mut self,
meta: &Metadata,
xattrs: &[crate::xattr::Xattr],
darwin: Option<&Darwin>,
is_dir: bool,
path: &[u8],
) -> Result<(), ModelError> {
self.config
.loss
.record_losses(&mut self.fidelity, meta, xattrs, darwin, is_dir, path)
.map_err(|property| ModelError::LossNotAccepted {
path: path.to_vec(),
property,
})
}
fn lose(&mut self, property: Property, path: &[u8]) -> Result<(), ModelError> {
if !self.config.loss.accepts(property) {
return Err(ModelError::LossNotAccepted {
path: path.to_vec(),
property,
});
}
self.fidelity.record(Direction::Dropped, path, property);
Ok(())
}
}
#[derive(Debug)]
pub(crate) struct PlacedTree {
dirs: Vec<ModelDir>,
contents: Vec<FileContent>,
fidelity: FidelityReport,
}
impl PlacedTree {
pub(crate) fn allocate(
&mut self,
layout: &FatLayout,
config: &ModelConfig,
) -> Result<(u32, u32), ModelError> {
self.check_root_capacity(layout, config)?;
self.allocate_clusters(layout, config)
}
pub(crate) fn content_sectors(&self, bytes_per_sector: u64) -> u64 {
let mut total = 0u64;
for dir in &self.dirs {
total = total.saturating_add(1);
for entry in &dir.entries {
if let Node::File { size, .. } = entry.node {
total = total.saturating_add(u64::from(size).div_ceil(bytes_per_sector));
}
}
}
total
}
pub(crate) fn finish(self, used_clusters: u32, next_free: u32) -> FatModel {
FatModel {
dirs: self.dirs,
contents: self.contents,
fidelity: self.fidelity,
used_clusters,
next_free,
}
}
fn check_root_capacity(
&self,
layout: &FatLayout,
config: &ModelConfig,
) -> Result<(), ModelError> {
if layout.root_entries == 0 {
return Ok(());
}
let needed = self.dirs[ROOT_DIR].slots(ROOT_DIR, config.has_label);
if needed > u64::from(layout.root_entries) {
return Err(ModelError::RootDirectoryFull {
needed: u32::try_from(needed).unwrap_or(u32::MAX),
capacity: layout.root_entries,
});
}
Ok(())
}
fn allocate_clusters(
&mut self,
layout: &FatLayout,
config: &ModelConfig,
) -> Result<(u32, u32), ModelError> {
let per_cluster = u64::from(layout.bytes_per_cluster());
let available = layout.clusters;
let mut next: u64 = 2;
let mut take = |count: u64| -> Result<ClusterRun, ModelError> {
let first = next;
next += count;
if next > u64::from(available) + 2 {
return Err(ModelError::VolumeFull {
needed: next - 2,
available,
});
}
Ok(ClusterRun {
first: if count == 0 { 0 } else { first as u32 },
count: count as u32,
})
};
for index in 0..self.dirs.len() {
if index != ROOT_DIR || layout.fat32.is_some() {
let slots = self.dirs[index].slots(index, config.has_label);
let bytes = slots * DIR_ENTRY_SIZE as u64;
self.dirs[index].run = take(bytes.div_ceil(per_cluster).max(1))?;
}
for at in 0..self.dirs[index].entries.len() {
if let Node::File { size, .. } = self.dirs[index].entries[at].node {
let run = take(u64::from(size).div_ceil(per_cluster))?;
if let Node::File { run: slot, .. } = &mut self.dirs[index].entries[at].node {
*slot = run;
}
}
}
}
for index in 0..self.dirs.len() {
for at in 0..self.dirs[index].entries.len() {
if let Node::Dir(child) = self.dirs[index].entries[at].node {
self.dirs[child].parent = Some(index);
}
}
}
let used = (next - 2) as u32;
Ok((used, next as u32))
}
}
impl FatModel {
pub fn chain_ends(&self) -> Vec<u32> {
let mut ends = Vec::new();
let mut push = |run: ClusterRun| {
if !run.is_empty() {
ends.push(run.first + run.count - 1);
}
};
for dir in &self.dirs {
push(dir.run);
for entry in &dir.entries {
if let Node::File { run, .. } = entry.node {
push(run);
}
}
}
assert!(
ends.windows(2).all(|w| w[0] < w[1]),
"the chain ends are not ascending, so allocation and this walk disagree"
);
ends
}
pub fn entry_target(&self, node: Node) -> (u32, u32) {
match node {
Node::Dir(index) => (self.dirs[index].run.first, 0),
Node::File { size, run, .. } => (if run.is_empty() { 0 } else { run.first }, size),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::fat::geometry::{FatTypeRequest, PlanRequest, plan_layout};
use crate::fidelity::{AcceptedLoss, Synthesis};
use crate::source::{Source, TreeBuilder};
const TIME: Timestamp = Timestamp::from_secs(1_426_325_212);
fn meta(mode: u16) -> Metadata {
Metadata::new(mode, TIME)
}
fn layout() -> FatLayout {
plan_layout(&PlanRequest::new(64 << 20)).expect("plan")
}
fn config(accepted: AcceptedLoss) -> ModelConfig {
ModelConfig {
loss: LossPolicy {
accepted,
synthesis: Synthesis::new(),
},
has_label: false,
}
}
fn model_of(source: impl Source, accepted: AcceptedLoss) -> Result<FatModel, ModelError> {
build_model(source.into_entries(), &layout(), &config(accepted))
}
fn tree() -> TreeBuilder {
TreeBuilder::new()
.directory(b"/etc".to_vec(), meta(0o755))
.file(
b"/etc/hostname".to_vec(),
b"ferrosys\n".to_vec(),
meta(0o644),
)
.directory(b"/etc/conf.d".to_vec(), meta(0o755))
.file(b"/etc/conf.d/net".to_vec(), vec![b'x'; 9000], meta(0o644))
.file(b"/big".to_vec(), vec![0xAB; 70_000], meta(0o644))
}
#[test]
fn re_allocating_a_placed_tree_at_two_layouts_matches_two_fresh_builds() {
let cfg = config(AcceptedLoss::ALL);
let small = plan_layout(&PlanRequest::new(16 << 20)).expect("plan 16 MiB");
let large = plan_layout(&PlanRequest::new(64 << 20)).expect("plan 64 MiB");
let mut placed = Builder::new(&cfg)
.place_all(tree().into_entries())
.expect("place");
for layout in [&small, &large] {
let (used, next) = placed.allocate(layout, &cfg).expect("allocate");
let fresh = build_model(tree().into_entries(), layout, &cfg).expect("fresh build");
assert_eq!(used, fresh.used_clusters);
assert_eq!(next, fresh.next_free);
assert_eq!(format!("{:?}", placed.dirs), format!("{:?}", fresh.dirs));
}
}
#[test]
fn a_failed_allocation_leaves_the_tree_re_allocatable() {
let cfg = config(AcceptedLoss::ALL);
let mut placed = Builder::new(&cfg)
.place_all(tree().into_entries())
.expect("place");
let tiny = plan_layout(&PlanRequest::new(64 << 10)).expect("plan 64 KiB");
assert!(
matches!(
placed.allocate(&tiny, &cfg),
Err(ModelError::VolumeFull { .. })
),
"the tree does not fit a 64 KiB volume"
);
let large = plan_layout(&PlanRequest::new(64 << 20)).expect("plan 64 MiB");
let (used, next) = placed
.allocate(&large, &cfg)
.expect("the tree allocates after a refusal");
let fresh = build_model(tree().into_entries(), &large, &cfg).expect("fresh build");
assert_eq!((used, next), (fresh.used_clusters, fresh.next_free));
assert_eq!(format!("{:?}", placed.dirs), format!("{:?}", fresh.dirs));
}
fn names(dir: &ModelDir) -> Vec<String> {
dir.entries
.iter()
.map(|e| String::from_utf8_lossy(&e.name.short).into_owned())
.collect()
}
#[test]
fn a_root_owned_tree_with_conventional_modes_is_carried_whole() {
let source = TreeBuilder::new()
.directory(b"/EFI".to_vec(), meta(0o755))
.directory(b"/EFI/BOOT".to_vec(), meta(0o755))
.file(b"/EFI/BOOT/BOOTX64.EFI".to_vec(), b"MZ", meta(0o644));
let model = model_of(source, AcceptedLoss::NONE).expect("a faithful tree");
assert!(model.fidelity.is_faithful());
assert_eq!(model.dirs.len(), 3);
assert_eq!(names(&model.dirs[0]), ["EFI "]);
let source = TreeBuilder::new().file(b"/RO.TXT".to_vec(), b"x", meta(0o444));
let model = model_of(source, AcceptedLoss::NONE).expect("read-only is carried");
assert!(model.fidelity.is_faithful());
assert!(
model.dirs[0].entries[0]
.attributes
.contains(Attributes::READ_ONLY)
);
}
#[test]
fn a_property_the_format_cannot_carry_refuses_until_it_is_accepted() {
let cases: Vec<(&str, Property, TreeBuilder)> = vec![
(
"an owner",
Property::Ownership,
TreeBuilder::new().file(b"/f".to_vec(), b"x", meta(0o644).owned_by(1000, 1000)),
),
(
"an executable bit",
Property::Permissions,
TreeBuilder::new().file(b"/f".to_vec(), b"x", meta(0o755)),
),
(
"a setuid bit",
Property::SpecialBits,
TreeBuilder::new().file(b"/f".to_vec(), b"x", meta(0o4644)),
),
(
"a symbolic link",
Property::Kind,
TreeBuilder::new().symlink(b"/f".to_vec(), b"/t".to_vec(), meta(0o777)),
),
(
"an extended attribute",
Property::ExtendedAttributes,
TreeBuilder::new()
.file(b"/f".to_vec(), b"x", meta(0o644))
.xattr(b"user.note".to_vec(), b"v".to_vec()),
),
(
"a change time",
Property::ChangeTime,
TreeBuilder::new().file(
b"/f".to_vec(),
b"x",
meta(0o644).with_times(TIME, Timestamp::from_secs(TIME.secs + 100), TIME),
),
),
];
for (what, property, source) in cases {
let refused = model_of(source.clone(), AcceptedLoss::NONE);
assert!(
matches!(refused, Err(ModelError::LossNotAccepted { property: p, .. }) if p == property),
"{what} was not refused: {refused:?}"
);
let other = if property == Property::Ownership {
Property::Permissions
} else {
Property::Ownership
};
assert!(
model_of(source.clone(), AcceptedLoss::NONE.and(other)).is_err(),
"{what} was accepted by an unrelated property"
);
let model = model_of(source, AcceptedLoss::NONE.and(property))
.unwrap_or_else(|e| panic!("{what} was still refused: {e}"));
assert_eq!(
model.fidelity.count(Direction::Dropped, property),
1,
"{what}"
);
}
}
#[test]
fn a_rounded_time_is_recorded_and_never_refuses() {
let odd = Timestamp::from_secs(TIME.secs + 1);
let source = TreeBuilder::new().file(b"/f".to_vec(), b"x", Metadata::new(0o644, odd));
let model = model_of(source, AcceptedLoss::NONE).expect("precision never refuses");
assert_eq!(
model
.fidelity
.count(Direction::Dropped, Property::TimePrecision),
1
);
assert!(!model.fidelity.is_faithful(), "the loss is still reported");
let source = TreeBuilder::new().file(
b"/f".to_vec(),
b"x",
meta(0o644).with_times(odd, TIME, TIME),
);
let model = model_of(source, AcceptedLoss::NONE).expect("build");
assert!(model.fidelity.is_faithful());
let times = model.dirs[0].entries[0].times;
assert_eq!(
times.access_date,
DosTimestamp::encode(odd).expect("in range").date
);
assert_eq!(times.write, DosTimestamp::encode(TIME).expect("in range"));
}
#[test]
fn a_hard_link_is_copied_and_a_symbolic_link_is_not_followed() {
let source = TreeBuilder::new()
.file(b"/bin".to_vec(), b"payload", meta(0o644))
.hardlink(b"/also".to_vec(), b"/bin".to_vec(), meta(0o644))
.symlink(b"/link".to_vec(), b"/etc/shadow".to_vec(), meta(0o777));
let model = model_of(source, AcceptedLoss::NONE.and(Property::Kind)).expect("build");
assert_eq!(model.dirs[0].entries.len(), 2);
assert_eq!(names(&model.dirs[0]), ["ALSO ", "BIN "]);
let runs: Vec<(usize, ClusterRun)> = model.dirs[0]
.entries
.iter()
.map(|e| match e.node {
Node::File { content, run, .. } => (content, run),
Node::Dir(_) => panic!("a file was modelled as a directory"),
})
.collect();
assert_eq!(runs[0].0, runs[1].0, "one content, named twice");
assert_ne!(runs[0].1.first, runs[1].1.first, "and two chains");
assert_eq!(model.fidelity.count(Direction::Dropped, Property::Kind), 2);
}
#[test]
fn every_kind_the_format_has_no_field_for_leaves_nothing_behind() {
let source = TreeBuilder::new()
.char_device(b"/null".to_vec(), 1, 3, meta(0o666))
.block_device(b"/sda".to_vec(), 8, 0, meta(0o660))
.fifo(b"/pipe".to_vec(), meta(0o644))
.socket(b"/sock".to_vec(), meta(0o644))
.symlink(b"/link".to_vec(), b"/t".to_vec(), meta(0o777));
let model = model_of(source, AcceptedLoss::ALL).expect("build");
assert!(model.dirs[0].entries.is_empty());
assert_eq!(model.fidelity.count(Direction::Dropped, Property::Kind), 5);
assert_eq!(model.fidelity.summary().len(), 1);
}
#[test]
fn a_hard_link_to_something_that_was_itself_dropped_is_dropped_too() {
let source = TreeBuilder::new()
.symlink(b"/link".to_vec(), b"/t".to_vec(), meta(0o777))
.hardlink(b"/also".to_vec(), b"/link".to_vec(), meta(0o644));
let model = model_of(source, AcceptedLoss::ALL).expect("build");
assert!(model.dirs[0].entries.is_empty());
assert_eq!(model.fidelity.count(Direction::Dropped, Property::Kind), 2);
}
#[test]
fn a_hard_link_the_source_never_declared_is_a_refusal_rather_than_a_loss() {
let source = TreeBuilder::new().hardlink(b"/a".to_vec(), b"/nowhere".to_vec(), meta(0o644));
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::HardlinkTargetMissing { .. })
));
let source = TreeBuilder::new()
.directory(b"/d".to_vec(), meta(0o755))
.hardlink(b"/a".to_vec(), b"/d".to_vec(), meta(0o644));
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::HardlinkTargetIsDirectory { .. })
));
}
#[test]
fn two_names_one_driver_cannot_tell_apart_are_refused() {
let source = TreeBuilder::new()
.file(b"/readme.txt".to_vec(), b"a", meta(0o644))
.file(b"/README.TXT".to_vec(), b"b", meta(0o644));
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::Indistinguishable { .. })
));
let source = TreeBuilder::new()
.directory(b"/d".to_vec(), meta(0o755))
.file(b"/readme.txt".to_vec(), b"a", meta(0o644))
.file(b"/d/README.TXT".to_vec(), b"b", meta(0o644));
assert!(model_of(source, AcceptedLoss::NONE).is_ok());
}
#[test]
fn a_derived_short_name_that_is_another_entrys_name_is_refused() {
let source = TreeBuilder::new()
.file(b"/A Long File Name.txt".to_vec(), b"a", meta(0o644))
.file(b"/ALONGFIL.TXT".to_vec(), b"b", meta(0o644));
assert!(
matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::Indistinguishable { .. })
),
"a name reachable two ways is refused"
);
let source = TreeBuilder::new()
.file(b"/A Long File Name.txt".to_vec(), b"a", meta(0o644))
.file(b"/Another Long Name.txt".to_vec(), b"b", meta(0o644));
assert!(model_of(source, AcceptedLoss::ALL).is_ok());
}
#[test]
fn the_tree_is_placed_in_sorted_order_whatever_order_it_arrives_in() {
let forwards = TreeBuilder::new()
.directory(b"/d".to_vec(), meta(0o755))
.file(b"/d/a".to_vec(), b"a", meta(0o644))
.file(b"/d/b".to_vec(), b"b", meta(0o644))
.file(b"/z".to_vec(), b"z", meta(0o644));
let backwards = TreeBuilder::new()
.file(b"/z".to_vec(), b"z", meta(0o644))
.file(b"/d/b".to_vec(), b"b", meta(0o644))
.file(b"/d/a".to_vec(), b"a", meta(0o644))
.directory(b"/d".to_vec(), meta(0o755));
let one = model_of(forwards, AcceptedLoss::NONE).expect("build");
let two = model_of(backwards, AcceptedLoss::NONE).expect("build");
assert_eq!(one.dirs, two.dirs);
assert_eq!(names(&one.dirs[0]), ["D ", "Z "]);
assert_eq!(names(&one.dirs[1]), ["A ", "B "]);
}
#[test]
fn a_malformed_tree_is_refused_by_shape() {
let cases: Vec<(&str, TreeBuilder)> = vec![
(
"a missing parent",
TreeBuilder::new().file(b"/d/f".to_vec(), b"x", meta(0o644)),
),
(
"a parent that is a file",
TreeBuilder::new()
.file(b"/d".to_vec(), b"x", meta(0o644))
.file(b"/d/f".to_vec(), b"x", meta(0o644)),
),
(
"a duplicate path",
TreeBuilder::new()
.file(b"/f".to_vec(), b"a", meta(0o644))
.file(b"//f".to_vec(), b"b", meta(0o644)),
),
(
"a traversal",
TreeBuilder::new().file(b"/d/../f".to_vec(), b"x", meta(0o644)),
),
];
for (what, source) in cases {
assert!(
model_of(source, AcceptedLoss::ALL).is_err(),
"{what} was accepted"
);
}
}
#[test]
fn the_root_is_a_directory_and_its_metadata_is_not_a_loss() {
let source = TreeBuilder::new()
.root(meta(0o700).owned_by(1000, 1000))
.file(b"/f".to_vec(), b"x", meta(0o644));
let model = model_of(source, AcceptedLoss::NONE).expect("the root is accepted");
assert!(model.fidelity.is_faithful());
assert_eq!(model.dirs[0].entries.len(), 1);
let source = TreeBuilder::new().file(b"/".to_vec(), b"x", meta(0o644));
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::RootNotDirectory { .. })
));
}
#[test]
fn a_birth_time_is_held_to_the_fat_creation_field() {
let born = Timestamp {
secs: TIME.secs + 1,
nanos: 230_000_000,
};
let file = |meta: Metadata| TreeBuilder::new().file(b"/f".to_vec(), b"x", meta);
let model =
model_of(file(meta(0o644).with_birth_time(born)), AcceptedLoss::NONE).expect("held");
assert!(model.fidelity.is_faithful());
let times = model.dirs[0].entries[0].times;
assert_eq!(times.create, DosTimestamp::encode(born).expect("in range"));
assert_eq!(times.write, DosTimestamp::encode(TIME).expect("in range"));
let finer = Timestamp { nanos: 1, ..born };
let model =
model_of(file(meta(0o644).with_birth_time(finer)), AcceptedLoss::NONE).expect("held");
assert_eq!(
model
.fidelity
.count(Direction::Dropped, Property::TimePrecision),
1
);
let before = meta(0o644).with_birth_time(Timestamp::from_secs(0));
assert!(matches!(
model_of(file(before), AcceptedLoss::ALL),
Err(ModelError::TimeOutOfRange {
field: TimeField::Birth,
secs: 0,
..
})
));
}
#[test]
fn a_time_outside_the_format_is_refused_rather_than_wrapped() {
let source = TreeBuilder::new().file(
b"/f".to_vec(),
b"x",
Metadata::new(0o644, Timestamp::from_secs(0)),
);
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::TimeOutOfRange {
field: TimeField::Modification,
secs: 0,
..
})
));
let source = TreeBuilder::new().file(
b"/f".to_vec(),
b"x",
meta(0o644).with_times(Timestamp::from_secs(0), TIME, TIME),
);
assert!(matches!(
model_of(source, AcceptedLoss::ALL),
Err(ModelError::TimeOutOfRange {
field: TimeField::Access,
..
})
));
}
#[test]
fn clusters_are_handed_out_in_one_ascending_pass_and_every_chain_is_contiguous() {
let bytes = layout().bytes_per_cluster() as usize;
let source = TreeBuilder::new()
.file(b"/big".to_vec(), vec![7u8; bytes * 3 + 1], meta(0o644))
.file(b"/empty".to_vec(), Vec::new(), meta(0o644))
.directory(b"/d".to_vec(), meta(0o755));
let model = model_of(source, AcceptedLoss::NONE).expect("build");
assert!(model.dirs[0].run.is_empty());
let entries = &model.dirs[0].entries;
assert_eq!(
names(&model.dirs[0]),
["BIG ", "D ", "EMPTY "]
);
let Node::File { run, .. } = entries[0].node else {
panic!("BIG is a file")
};
assert_eq!(run, ClusterRun { first: 2, count: 4 });
assert_eq!(model.dirs[1].run, ClusterRun { first: 6, count: 1 });
assert_eq!(model.entry_target(entries[2].node), (0, 0));
assert_eq!(model.used_clusters, 5);
assert_eq!(model.next_free, 7);
}
#[test]
fn a_fat32_root_takes_the_cluster_its_layout_names() {
let layout = plan_layout(
&PlanRequest::new(512 << 20)
.fat_type(FatTypeRequest::Exactly(super::super::FatType::Fat32)),
)
.expect("plan");
let source = TreeBuilder::new().file(b"/f".to_vec(), b"x", meta(0o644));
let model = build_model(source.into_entries(), &layout, &config(AcceptedLoss::NONE))
.expect("build");
assert_eq!(
model.dirs[0].run.first,
layout.fat32.expect("fat32").root_cluster
);
assert_eq!(model.dirs[0].run.count, 1);
}
#[test]
fn a_tree_larger_than_the_volume_is_refused_before_anything_is_written() {
let layout = plan_layout(&PlanRequest::new(1 << 20)).expect("plan");
let bytes = layout.bytes_per_cluster() as usize;
let source = TreeBuilder::new().file(
b"/f".to_vec(),
vec![0u8; bytes * (layout.clusters as usize + 1)],
meta(0o644),
);
assert!(matches!(
build_model(source.into_entries(), &layout, &config(AcceptedLoss::NONE)),
Err(ModelError::VolumeFull { .. })
));
}
#[test]
fn a_root_region_the_tree_overflows_is_refused_and_names_the_counts() {
let layout = plan_layout(
&PlanRequest::new(64 << 20).root_entries(super::super::RootEntries::Count(16)),
)
.expect("plan");
let capacity = layout.root_entries;
let mut source = TreeBuilder::new();
for i in 0..capacity {
source = source.file(format!("/file{i}").into_bytes(), b"x", meta(0o644));
}
let err = build_model(source.into_entries(), &layout, &config(AcceptedLoss::NONE))
.expect_err("the region is too small");
assert!(
matches!(err, ModelError::RootDirectoryFull { needed, capacity: c }
if needed == capacity * 2 && c == capacity),
"{err:?}"
);
let mut source = TreeBuilder::new().directory(b"/d".to_vec(), meta(0o755));
for i in 0..capacity {
source = source.file(format!("/d/file{i}").into_bytes(), b"x", meta(0o644));
}
assert!(build_model(source.into_entries(), &layout, &config(AcceptedLoss::NONE)).is_ok());
}
fn directory_of(files: u64, long: bool) -> TreeBuilder {
let mut source = TreeBuilder::new().directory(b"/d".to_vec(), meta(0o755));
for i in 0..files {
let name = if long {
format!("/d/f{i:07}")
} else {
format!("/d/F{i:07}")
};
source = source.file(name.into_bytes(), Vec::new(), meta(0o644));
}
source
}
#[test]
fn a_directory_is_held_to_the_format_s_size_counting_every_entry_it_occupies() {
let config = config(AcceptedLoss::NONE);
let full = MAX_DIRECTORY_ENTRIES - 2;
assert!(place_tree(directory_of(full, false).into_entries(), &config).is_ok());
let err = place_tree(directory_of(full + 1, false).into_entries(), &config)
.expect_err("one entry past the bound");
assert!(
matches!(&err, ModelError::DirectoryTooLarge { path, needed, limit }
if path == b"/d"
&& *needed == MAX_DIRECTORY_BYTES + DIR_ENTRY_SIZE as u64
&& *limit == MAX_DIRECTORY_BYTES),
"{err:?}"
);
assert_eq!(MAX_DIRECTORY_BYTES, 2 << 20);
let half = full / 2;
assert!(place_tree(directory_of(half, true).into_entries(), &config).is_ok());
assert!(matches!(
place_tree(directory_of(half + 1, true).into_entries(), &config),
Err(ModelError::DirectoryTooLarge { .. })
));
}
#[test]
fn a_chained_root_is_held_to_the_bound_with_its_label_counted() {
let root_of = |files: u64| {
let mut source = TreeBuilder::new();
for i in 0..files {
let name = format!("/F{i:07}");
source = source.file(name.into_bytes(), Vec::new(), meta(0o644));
}
source.into_entries()
};
let labelled = ModelConfig {
has_label: true,
..config(AcceptedLoss::NONE)
};
let full = MAX_DIRECTORY_ENTRIES - 1;
assert!(place_tree(root_of(full), &labelled).is_ok());
let err = place_tree(root_of(full + 1), &labelled).expect_err("one entry past the bound");
assert!(
matches!(&err, ModelError::DirectoryTooLarge { path, .. } if path == b"/"),
"{err:?}"
);
assert!(place_tree(root_of(full + 1), &config(AcceptedLoss::NONE)).is_ok());
}
#[test]
fn an_empty_source_models_an_empty_volume() {
let model = model_of(TreeBuilder::new(), AcceptedLoss::NONE).expect("build");
assert_eq!(model.dirs.len(), 1);
assert!(model.dirs[0].entries.is_empty());
assert!(model.fidelity.is_faithful());
assert_eq!(model.used_clusters, 0);
assert_eq!(model.next_free, 2);
assert!(model.chain_ends().is_empty());
}
#[test]
fn the_report_names_every_entry_and_exactly_what_it_lost() {
let other = TIME.secs + 100;
let source = TreeBuilder::new()
.file(b"/plain".to_vec(), b"x", meta(0o644))
.directory(b"/d".to_vec(), meta(0o755))
.file(b"/owned".to_vec(), b"x", meta(0o644).owned_by(1000, 1000))
.file(b"/exec".to_vec(), b"x", meta(0o755))
.file(b"/setuid".to_vec(), b"x", meta(0o4644))
.file(b"/attrs".to_vec(), b"x", meta(0o644))
.xattr(b"user.note".to_vec(), b"v".to_vec())
.file(
b"/changed".to_vec(),
b"x",
meta(0o644).with_times(TIME, Timestamp::from_secs(other), TIME),
)
.file(
b"/odd".to_vec(),
b"x",
Metadata::new(0o644, Timestamp::from_secs(TIME.secs + 1)),
)
.symlink(b"/link".to_vec(), b"/plain".to_vec(), meta(0o777));
let model = model_of(source, AcceptedLoss::ALL).expect("build");
let mut by_path: Vec<(String, Vec<&str>)> = Vec::new();
for record in model.fidelity.records() {
let path = String::from_utf8_lossy(&record.path).into_owned();
match by_path.iter_mut().find(|(p, _)| *p == path) {
Some((_, props)) => props.push(record.property.as_str()),
None => by_path.push((path, vec![record.property.as_str()])),
}
}
by_path.sort();
assert_eq!(
by_path,
vec![
("/attrs".to_string(), vec!["extended attributes"]),
("/changed".to_string(), vec!["change time"]),
("/exec".to_string(), vec!["permissions"]),
("/link".to_string(), vec!["kind"]),
("/odd".to_string(), vec!["time precision"]),
("/owned".to_string(), vec!["ownership"]),
("/setuid".to_string(), vec!["special bits"]),
],
"the report does not name exactly the entries that lost something"
);
assert!(!by_path.iter().any(|(p, _)| p == "/plain" || p == "/d"));
assert!(!model.fidelity.is_truncated());
}
#[test]
fn every_subdirectory_knows_the_directory_that_holds_it() {
let source = TreeBuilder::new()
.directory(b"/a".to_vec(), meta(0o755))
.directory(b"/a/b".to_vec(), meta(0o755))
.directory(b"/a/b/c".to_vec(), meta(0o755));
let model = model_of(source, AcceptedLoss::NONE).expect("build");
assert_eq!(model.dirs[0].parent, None);
assert_eq!(model.dirs[1].parent, Some(0));
assert_eq!(model.dirs[2].parent, Some(1));
assert_eq!(model.dirs[3].parent, Some(2));
}
}