use std::collections::{BTreeMap, HashMap};
use crate::fidelity::FidelityReport;
use crate::path::canonical_key;
use crate::source::{
ClassifyError, Darwin, EntryKind, FileContent, MODE_TYPE_MASK, Metadata, PathFault,
SourceEntry, classify_paths,
};
use crate::time::Timestamp;
use crate::xattr::Xattr;
use super::geometry::Content;
use super::ondisk::{DirEntryType, DirItem, FileExtentItem, Header, Item, objectid};
pub const MAX_NAME_LEN: usize = 255;
const MAX_XATTR_NAME: usize = 255;
fn device_number(path: &[u8], major: u32, minor: u32) -> Result<(u32, u32), ModelError> {
use super::ondisk::InodeItem;
if major >> (32 - InodeItem::MINOR_BITS) != 0 || minor > InodeItem::MINOR_MASK {
return Err(ModelError::DeviceNumberTooLarge {
path: path.to_vec(),
major,
minor,
});
}
Ok((major, minor))
}
pub const MAX_EXTENT_BYTES: u64 = 1 << 20;
pub(crate) const FIRST_DIR_INDEX: u64 = 2;
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct SubvolumeRequest {
pub path: Vec<u8>,
pub uuid: [u8; 16],
pub read_only: bool,
}
impl SubvolumeRequest {
#[must_use]
pub fn new(path: impl Into<Vec<u8>>, uuid: [u8; 16]) -> Self {
Self {
path: path.into(),
uuid,
read_only: false,
}
}
#[must_use]
pub fn read_only(mut self, read_only: bool) -> Self {
self.read_only = read_only;
self
}
}
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ModelError {
#[error(
"{}: its contents are declared by length alone, and this writer checksums a file's \
bytes in its metadata",
crate::escape::printable(.path)
)]
#[non_exhaustive]
ContentsNotHeld {
path: Vec<u8>,
},
#[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(
"{}: a name of {bytes} bytes is longer than the {MAX_NAME_LEN} this format holds",
crate::escape::printable(.path)
)]
#[non_exhaustive]
NameTooLong {
path: Vec<u8>,
bytes: usize,
},
#[error("{}: the name holds a NUL", crate::escape::printable(.path))]
#[non_exhaustive]
NameHoldsNul {
path: Vec<u8>,
},
#[error(
"{}: a link target of {bytes} bytes, empty, or holding a NUL; this format holds targets \
of 1 to {limit} bytes",
crate::escape::printable(.path)
)]
#[non_exhaustive]
SymlinkTarget {
path: Vec<u8>,
bytes: usize,
limit: usize,
},
#[error(
"{}: device numbers {major}:{minor} are wider than this format holds",
crate::escape::printable(.path)
)]
#[non_exhaustive]
DeviceNumberTooLarge {
path: Vec<u8>,
major: u32,
minor: u32,
},
#[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(
"{}: mode {mode:#o} carries file-type bits, which the entry's kind supplies",
crate::escape::printable(.path)
)]
#[non_exhaustive]
ModeCarriesFileType {
path: Vec<u8>,
mode: u16,
},
#[error(
"{}: BSD flags {flags:#x} are a Darwin filesystem's, and this one holds none",
crate::escape::printable(.path)
)]
#[non_exhaustive]
BsdFlagsNotHeld {
path: Vec<u8>,
flags: u32,
},
#[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(
"{}: the attribute name {} cannot be stored",
crate::escape::printable(.path),
crate::escape::printable(.name)
)]
#[non_exhaustive]
XattrName {
path: Vec<u8>,
name: Vec<u8>,
},
#[error(
"{}: the attribute {} is stated more than once",
crate::escape::printable(.path),
crate::escape::printable(.name)
)]
#[non_exhaustive]
XattrRepeated {
path: Vec<u8>,
name: Vec<u8>,
},
#[error(
"{}: a time of {secs} seconds and {nanos} nanoseconds, a fraction of a second of a \
second or more",
crate::escape::printable(.path)
)]
#[non_exhaustive]
TimeOutOfRange {
path: Vec<u8>,
secs: i64,
nanos: u32,
},
#[error(
"hard link {} states extended attributes other than its target's, and attributes \
belong to the target",
crate::escape::printable(.path)
)]
#[non_exhaustive]
LinkCarriesXattrs {
path: 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(
"hard link {} and its target {} are in different subvolumes, and no hard link spans two",
crate::escape::printable(.path),
crate::escape::printable(.target)
)]
#[non_exhaustive]
HardlinkCrossesSubvolume {
path: Vec<u8>,
target: Vec<u8>,
},
#[error(
"the subvolume {} names no directory this source declares",
crate::escape::printable(.path)
)]
#[non_exhaustive]
SubvolumeNotADirectory {
path: Vec<u8>,
},
#[error("the root is already a subvolume and cannot be asked for as another")]
SubvolumeAtRoot,
#[error(
"a subvolume is asked for twice at {}",
crate::escape::printable(.path)
)]
#[non_exhaustive]
SubvolumeDuplicate {
path: Vec<u8>,
},
#[error(
"subvolumes {} and {} share the identifier {}",
crate::escape::printable(.first),
crate::escape::printable(.second),
crate::escape::hex(.uuid)
)]
#[non_exhaustive]
SubvolumeUuidRepeated {
first: Vec<u8>,
second: Vec<u8>,
uuid: [u8; 16],
},
#[error(
"the default subvolume {} is not the root and is not a subvolume that was asked for",
crate::escape::printable(.path)
)]
#[non_exhaustive]
DefaultSubvolumeUnknown {
path: Vec<u8>,
},
#[error(
"{}: the {what} needs {bytes} bytes and a leaf of this filesystem holds {capacity}",
crate::escape::printable(.path)
)]
#[non_exhaustive]
RecordTooLarge {
path: Vec<u8>,
what: &'static str,
bytes: usize,
capacity: usize,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) enum ObjectKind {
Directory(Vec<DirEntry>),
File {
content: usize,
size: u64,
inline: bool,
},
Symlink(Vec<u8>),
Device {
block: bool,
major: u32,
minor: u32,
},
Fifo,
Socket,
}
impl ObjectKind {
pub(crate) const fn mode_bits(&self) -> u32 {
match self {
Self::Directory(_) => 0o040_000,
Self::File { .. } => 0o100_000,
Self::Symlink(_) => 0o120_000,
Self::Device { block: true, .. } => 0o060_000,
Self::Device { block: false, .. } => 0o020_000,
Self::Fifo => 0o010_000,
Self::Socket => 0o140_000,
}
}
pub(crate) const fn entry_type(&self) -> DirEntryType {
match self {
Self::Directory(_) => DirEntryType::Dir,
Self::File { .. } => DirEntryType::RegFile,
Self::Symlink(_) => DirEntryType::Symlink,
Self::Device { block: true, .. } => DirEntryType::BlockDev,
Self::Device { block: false, .. } => DirEntryType::CharDev,
Self::Fifo => DirEntryType::Fifo,
Self::Socket => DirEntryType::Socket,
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct DirEntry {
pub name: Vec<u8>,
pub index: u64,
pub target: EntryTarget,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum EntryTarget {
Inode {
inode: u64,
kind: DirEntryType,
},
Subvolume {
id: u64,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct ObjectName {
pub parent: u64,
pub index: u64,
pub name: Vec<u8>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct ModelObject {
pub inode: u64,
pub kind: ObjectKind,
pub meta: Metadata,
pub xattrs: Vec<Xattr>,
pub names: Vec<ObjectName>,
}
impl ModelObject {
pub(crate) fn size(&self) -> u64 {
match &self.kind {
ObjectKind::Directory(entries) => entries.iter().map(|e| 2 * e.name.len() as u64).sum(),
ObjectKind::File { size, .. } => *size,
ObjectKind::Symlink(target) => target.len() as u64,
_ => 0,
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct ModelSubvolume {
pub id: u64,
pub uuid: [u8; 16],
pub read_only: bool,
pub link: Option<SubvolumeLink>,
pub objects: Vec<ModelObject>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct SubvolumeLink {
pub parent: u64,
pub dir: u64,
pub index: u64,
pub name: Vec<u8>,
}
#[derive(Debug)]
pub(crate) struct BtrfsModel {
pub subvolumes: Vec<ModelSubvolume>,
pub default_subvolume: u64,
pub contents: Vec<FileContent>,
pub content: Content,
pub fidelity: FidelityReport,
}
pub(crate) fn build_model(
entries: Vec<SourceEntry>,
subvolumes: &[SubvolumeRequest],
default_subvolume: Option<&[u8]>,
subvolume_uuid: [u8; 16],
sector_size: u32,
node_size: u32,
time: Timestamp,
) -> Result<BtrfsModel, ModelError> {
Builder::new(sector_size, node_size, time).build(
entries,
subvolumes,
default_subvolume,
subvolume_uuid,
)
}
#[derive(Clone, PartialEq, Eq, Debug)]
enum Class {
Directory,
Object,
Link(Vec<u8>),
}
struct PendingLink {
parent: Placed,
at: usize,
target: Vec<u8>,
path: Vec<u8>,
name: Vec<u8>,
index: u64,
xattrs: Vec<Xattr>,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Placed {
subvolume: usize,
object: usize,
}
struct Builder {
sector_size: u32,
time: Timestamp,
capacity: usize,
subvolumes: Vec<ModelSubvolume>,
contents: Vec<FileContent>,
classes: BTreeMap<Vec<u8>, Class>,
subvolume_at: HashMap<Vec<u8>, usize>,
placed: HashMap<Vec<u8>, Placed>,
pending: Vec<PendingLink>,
longest_value: u64,
longest_name: u32,
names: u64,
xattrs: u64,
directories: u64,
files: u64,
data_bytes: u64,
data_extents: u64,
}
impl Builder {
fn new(sector_size: u32, node_size: u32, time: Timestamp) -> Self {
Self {
sector_size,
time,
capacity: node_size as usize - Header::SIZE - Item::SIZE,
subvolumes: Vec::new(),
contents: Vec::new(),
classes: BTreeMap::new(),
subvolume_at: HashMap::new(),
placed: HashMap::new(),
pending: Vec::new(),
longest_value: 0,
longest_name: 0,
names: 0,
xattrs: 0,
directories: 0,
files: 0,
data_bytes: 0,
data_extents: 0,
}
}
fn build(
mut self,
mut entries: Vec<SourceEntry>,
requested: &[SubvolumeRequest],
default_subvolume: Option<&[u8]>,
subvolume_uuid: [u8; 16],
) -> Result<BtrfsModel, ModelError> {
entries.sort_by_key(|entry| canonical_key(&entry.path));
self.classify(&entries)?;
let root = self.open_subvolume(objectid::FS_TREE, subvolume_uuid, false, None);
self.placed.insert(
Vec::new(),
Placed {
subvolume: root,
object: 0,
},
);
let mut wanted = self.subvolume_requests(requested, subvolume_uuid)?;
for entry in entries {
self.place(entry, &mut wanted)?;
}
self.resolve_links()?;
let default_subvolume = match default_subvolume {
None => objectid::FS_TREE,
Some(path) => {
let key = canonical_key(path);
if key.is_empty() {
objectid::FS_TREE
} else {
let at = self.subvolume_at.get(&key).copied().ok_or_else(|| {
ModelError::DefaultSubvolumeUnknown {
path: path.to_vec(),
}
})?;
self.subvolumes[at].id
}
}
};
let content = Content {
directories: self.directories,
files: self.files,
names: self.names,
longest_name: self.longest_name,
longest_value: self.longest_value,
xattrs: self.xattrs,
subvolumes: self.subvolumes.len() as u64 - 1,
data_bytes: self.data_bytes,
data_extents: self.data_extents,
};
Ok(BtrfsModel {
subvolumes: self.subvolumes,
default_subvolume,
contents: self.contents,
content,
fidelity: FidelityReport::new(),
})
}
fn classify(&mut self, entries: &[SourceEntry]) -> Result<(), ModelError> {
self.classes = classify_paths(
entries,
|entry, parts| match parts.last() {
Some(name) if name.len() > MAX_NAME_LEN => Err(ModelError::NameTooLong {
path: entry.path.clone(),
bytes: name.len(),
}),
Some(name) if crate::path::is_hostile_entry(name) => {
Err(ModelError::NameHoldsNul {
path: entry.path.clone(),
})
}
_ => Ok(match &entry.kind {
EntryKind::Directory => Class::Directory,
EntryKind::HardLink { target } => Class::Link(canonical_key(target)),
_ => Class::Object,
}),
},
|class| *class == Class::Directory,
)
.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 subvolume_requests<'a>(
&self,
requested: &'a [SubvolumeRequest],
top_level_uuid: [u8; 16],
) -> Result<HashMap<Vec<u8>, &'a SubvolumeRequest>, ModelError> {
let mut wanted: HashMap<Vec<u8>, &SubvolumeRequest> = HashMap::new();
let mut identified: HashMap<[u8; 16], Vec<u8>> = HashMap::new();
if top_level_uuid != [0; 16] {
identified.insert(top_level_uuid, b"/".to_vec());
}
for request in requested {
let key = canonical_key(&request.path);
if key.is_empty() {
return Err(ModelError::SubvolumeAtRoot);
}
if self.classes.get(&key) != Some(&Class::Directory) {
return Err(ModelError::SubvolumeNotADirectory {
path: request.path.clone(),
});
}
if wanted.insert(key, request).is_some() {
return Err(ModelError::SubvolumeDuplicate {
path: request.path.clone(),
});
}
if request.uuid != [0; 16]
&& let Some(first) = identified.insert(request.uuid, request.path.clone())
{
return Err(ModelError::SubvolumeUuidRepeated {
first,
second: request.path.clone(),
uuid: request.uuid,
});
}
}
Ok(wanted)
}
fn place(
&mut self,
entry: SourceEntry,
wanted: &mut HashMap<Vec<u8>, &SubvolumeRequest>,
) -> Result<(), ModelError> {
let SourceEntry {
path,
kind,
meta,
xattrs,
darwin,
} = entry;
if let Some(flags) = darwin
.as_ref()
.map(Darwin::stated_flags)
.filter(|flags| *flags != 0)
{
return Err(ModelError::BsdFlagsNotHeld { path, flags });
}
if meta.mode & MODE_TYPE_MASK != 0 {
return Err(ModelError::ModeCarriesFileType {
path,
mode: meta.mode,
});
}
let times = [meta.atime, meta.ctime, meta.mtime];
if let Some(time) = times
.into_iter()
.chain(meta.btime)
.find(|t| !t.has_proper_fraction())
{
return Err(ModelError::TimeOutOfRange {
path,
secs: time.secs,
nanos: time.nanos,
});
}
if let Some(x) = xattrs
.iter()
.find(|x| x.name.is_empty() || x.name.contains(&0) || x.name.len() > MAX_XATTR_NAME)
{
return Err(ModelError::XattrName {
name: x.name.clone(),
path,
});
}
if let Some(name) = crate::xattr::repeated_name(&xattrs) {
return Err(ModelError::XattrRepeated {
name: name.to_vec(),
path,
});
}
let key = canonical_key(&path);
if key.is_empty() {
let root = &mut self.subvolumes[0].objects[0];
root.meta = meta;
self.account_xattrs(&xattrs, &path)?;
self.subvolumes[0].objects[0].xattrs = xattrs;
self.placed.insert(
key,
Placed {
subvolume: 0,
object: 0,
},
);
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.placed.get(&parent_key) {
Some(placed) => *placed,
None if self.classes.contains_key(&parent_key) => {
return Err(ModelError::ParentNotDir { path });
}
None => return Err(ModelError::ParentMissing { path }),
};
if !matches!(
self.subvolumes[parent.subvolume].objects[parent.object].kind,
ObjectKind::Directory(_)
) {
return Err(ModelError::ParentNotDir { path });
}
self.longest_name = self.longest_name.max(name.len() as u32);
self.names += 1;
if let EntryKind::HardLink { target } = kind {
let index = self.next_index(parent);
let at = self.add_entry(
parent,
name.clone(),
index,
EntryTarget::Inode {
inode: 0,
kind: DirEntryType::Unknown,
},
);
self.pending.push(PendingLink {
parent,
at,
target,
path,
name,
index,
xattrs,
});
return Ok(());
}
self.account_xattrs(&xattrs, &path)?;
if let Some(request) = wanted.remove(&key) {
let index = self.next_index(parent);
let id = self.next_subvolume_id();
let at = self.open_subvolume(
id,
request.uuid,
request.read_only,
Some(SubvolumeLink {
parent: self.subvolumes[parent.subvolume].id,
dir: self.inode_at(parent),
index,
name: name.clone(),
}),
);
self.subvolumes[at].objects[0].meta = meta;
self.subvolumes[at].objects[0].xattrs = xattrs;
self.add_entry(parent, name, index, EntryTarget::Subvolume { id });
self.subvolume_at.insert(key.clone(), at);
self.placed.insert(
key,
Placed {
subvolume: at,
object: 0,
},
);
return Ok(());
}
let object_kind = self.kind_of(kind, &path)?;
match &object_kind {
ObjectKind::Directory(_) => self.directories += 1,
_ => self.files += 1,
}
let index = self.next_index(parent);
let entry_type = object_kind.entry_type();
let subvolume = parent.subvolume;
let inode = self.next_inode(subvolume);
let holder = self.inode_at(parent);
self.subvolumes[subvolume].objects.push(ModelObject {
inode,
kind: object_kind,
meta,
xattrs,
names: vec![ObjectName {
parent: holder,
index,
name: name.clone(),
}],
});
let object = self.subvolumes[subvolume].objects.len() - 1;
self.add_entry(
parent,
name,
index,
EntryTarget::Inode {
inode,
kind: entry_type,
},
);
self.placed.insert(key, Placed { subvolume, object });
Ok(())
}
fn resolve_links(&mut self) -> Result<(), ModelError> {
for link in std::mem::take(&mut self.pending) {
let found = self.follow_link(&link.target, &link.path)?;
if found.subvolume != link.parent.subvolume {
return Err(ModelError::HardlinkCrossesSubvolume {
path: link.path,
target: link.target,
});
}
if !link.xattrs.is_empty()
&& !crate::xattr::same_xattrs(
&link.xattrs,
&self.subvolumes[found.subvolume].objects[found.object].xattrs,
)
{
return Err(ModelError::LinkCarriesXattrs { path: link.path });
}
let inode = self.inode_at(found);
let kind = self.subvolumes[found.subvolume].objects[found.object]
.kind
.entry_type();
let holder = self.inode_at(link.parent);
self.subvolumes[found.subvolume].objects[found.object]
.names
.push(ObjectName {
parent: holder,
index: link.index,
name: link.name,
});
match &mut self.subvolumes[link.parent.subvolume].objects[link.parent.object].kind {
ObjectKind::Directory(entries) => {
entries[link.at].target = EntryTarget::Inode { inode, kind };
}
_ => unreachable!("a name is only ever added to a directory"),
}
}
Ok(())
}
fn kind_of(&mut self, kind: EntryKind, path: &[u8]) -> Result<ObjectKind, ModelError> {
Ok(match kind {
EntryKind::Directory => ObjectKind::Directory(Vec::new()),
EntryKind::File(content) => {
if matches!(content, FileContent::Declared { .. }) {
return Err(ModelError::ContentsNotHeld {
path: path.to_vec(),
});
}
let size = content.len();
let inline = size > 0
&& size < u64::from(self.sector_size)
&& FileExtentItem::INLINE_DATA_START + size as usize <= self.capacity;
if inline {
self.longest_value = self.longest_value.max(size);
} else if size > 0 {
let stored =
size.div_ceil(u64::from(self.sector_size)) * u64::from(self.sector_size);
self.data_bytes += stored;
self.data_extents += stored.div_ceil(MAX_EXTENT_BYTES) * 2;
}
let at = self.contents.len();
self.contents.push(content);
ObjectKind::File {
content: at,
size,
inline,
}
}
EntryKind::Symlink(target) => {
let limit = self.sector_size as usize - 1;
if target.is_empty() || target.len() > limit || target.contains(&0) {
return Err(ModelError::SymlinkTarget {
path: path.to_vec(),
bytes: target.len(),
limit,
});
}
let need = FileExtentItem::INLINE_DATA_START + target.len();
if need > self.capacity {
return Err(ModelError::RecordTooLarge {
path: path.to_vec(),
what: "symbolic link's target",
bytes: need,
capacity: self.capacity,
});
}
self.longest_value = self.longest_value.max(target.len() as u64);
ObjectKind::Symlink(target)
}
EntryKind::CharDevice { major, minor } => {
let (major, minor) = device_number(path, major, minor)?;
ObjectKind::Device {
block: false,
major,
minor,
}
}
EntryKind::BlockDevice { major, minor } => {
let (major, minor) = device_number(path, major, minor)?;
ObjectKind::Device {
block: true,
major,
minor,
}
}
EntryKind::Fifo => ObjectKind::Fifo,
EntryKind::Socket => ObjectKind::Socket,
EntryKind::HardLink { .. } => unreachable!("a hard link is not a kind of object"),
})
}
fn account_xattrs(&mut self, xattrs: &[Xattr], path: &[u8]) -> Result<(), ModelError> {
for xattr in xattrs {
let need = DirItem::SIZE + xattr.name.len() + xattr.value.len();
if need > self.capacity {
return Err(ModelError::RecordTooLarge {
path: path.to_vec(),
what: "extended attribute",
bytes: need,
capacity: self.capacity,
});
}
self.longest_value = self
.longest_value
.max((xattr.name.len() + xattr.value.len()) as u64);
}
self.xattrs += xattrs.len() as u64;
Ok(())
}
fn follow_link(&self, target: &[u8], path: &[u8]) -> Result<Placed, ModelError> {
let mut at = canonical_key(target);
for _ in 0..=self.classes.len() {
match self.classes.get(&at) {
None => {
return Err(ModelError::HardlinkTargetMissing {
path: path.to_vec(),
target: target.to_vec(),
});
}
Some(Class::Directory) => {
return Err(ModelError::HardlinkTargetIsDirectory {
path: path.to_vec(),
target: target.to_vec(),
});
}
Some(Class::Link(next)) => at = next.clone(),
Some(Class::Object) => {
return Ok(*self
.placed
.get(&at)
.expect("every object was placed before any link was resolved"));
}
}
}
Err(ModelError::HardlinkCycle {
path: path.to_vec(),
})
}
fn open_subvolume(
&mut self,
id: u64,
uuid: [u8; 16],
read_only: bool,
link: Option<SubvolumeLink>,
) -> usize {
self.directories += 1;
self.subvolumes.push(ModelSubvolume {
id,
uuid,
read_only,
link,
objects: vec![ModelObject {
inode: objectid::FIRST_FREE,
kind: ObjectKind::Directory(Vec::new()),
meta: root_metadata(self.time),
xattrs: Vec::new(),
names: Vec::new(),
}],
});
self.subvolumes.len() - 1
}
fn next_subvolume_id(&self) -> u64 {
objectid::FIRST_FREE + self.subvolumes.len() as u64 - 1
}
fn next_inode(&self, subvolume: usize) -> u64 {
objectid::FIRST_FREE + self.subvolumes[subvolume].objects.len() as u64
}
fn inode_at(&self, placed: Placed) -> u64 {
self.subvolumes[placed.subvolume].objects[placed.object].inode
}
fn next_index(&self, dir: Placed) -> u64 {
match &self.subvolumes[dir.subvolume].objects[dir.object].kind {
ObjectKind::Directory(entries) => FIRST_DIR_INDEX + entries.len() as u64,
_ => unreachable!("a name is only ever added to a directory"),
}
}
fn add_entry(&mut self, dir: Placed, name: Vec<u8>, index: u64, target: EntryTarget) -> usize {
match &mut self.subvolumes[dir.subvolume].objects[dir.object].kind {
ObjectKind::Directory(entries) => {
entries.push(DirEntry {
name,
index,
target,
});
entries.len() - 1
}
_ => unreachable!("a name is only ever added to a directory"),
}
}
}
fn root_metadata(time: Timestamp) -> Metadata {
Metadata::new(0o755, time)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::source::{Source, TreeBuilder};
const SECTOR: u32 = 4096;
const NODE: u32 = 16384;
const TIME: Timestamp = Timestamp {
secs: 1_700_000_000,
nanos: 0,
};
fn meta() -> Metadata {
Metadata::new(0o644, crate::Timestamp::from_secs(1_700_000_000))
}
fn dir_meta() -> Metadata {
Metadata::new(0o755, crate::Timestamp::from_secs(1_700_000_000))
}
#[test]
fn an_attribute_name_empty_holding_a_nul_or_overlong_is_refused() {
let overlong = [b"user.".as_slice(), &[b'a'; 300]].concat();
for name in [&b""[..], b"user.a\0b", &overlong] {
let err = error_of(
TreeBuilder::new()
.file("/f", b"hello", meta())
.xattr(name.to_vec(), "value"),
);
assert!(
matches!(&err, ModelError::XattrName { path, name: n } if path == b"/f" && n == name),
"{err:?}"
);
}
}
#[test]
fn a_name_holding_a_nul_is_refused() {
let err = error_of(TreeBuilder::new().file("/with\0nul", b"x", meta()));
assert!(matches!(&err, ModelError::NameHoldsNul { .. }), "{err:?}");
}
#[test]
fn a_link_target_the_checker_refuses_is_refused() {
for target in [
Vec::new(),
vec![b'a'; 4096],
vec![b'a'; 10_000],
b"abc\0def".to_vec(),
] {
let err = error_of(TreeBuilder::new().symlink("/l", target.clone(), meta()));
assert!(
matches!(&err, ModelError::SymlinkTarget { bytes, limit: 4095, .. } if *bytes == target.len()),
"{} bytes: {err:?}",
target.len()
);
}
model_of(TreeBuilder::new().symlink("/l", vec![b'a'; 4095], meta()));
}
#[test]
fn device_numbers_wider_than_the_field_are_refused() {
for (major, minor) in [(4096, 1), (1, 1 << 20)] {
let err = error_of(TreeBuilder::new().char_device("/d", major, minor, meta()));
assert!(
matches!(&err, ModelError::DeviceNumberTooLarge { major: a, minor: b, .. } if (*a, *b) == (major, minor)),
"{err:?}"
);
}
model_of(TreeBuilder::new().char_device("/d", 4095, (1 << 20) - 1, meta()));
}
#[test]
fn an_attribute_named_twice_is_refused_whatever_its_values() {
for path in ["/f", "/"] {
for second in ["first", "second"] {
let source = if path == "/" {
TreeBuilder::new().directory(path, dir_meta())
} else {
TreeBuilder::new().file(path, b"hello", meta())
};
let err = error_of(
source
.xattr("user.a", "first")
.xattr("user.b", "other")
.xattr("user.a", second),
);
assert!(
matches!(&err, ModelError::XattrRepeated { path: p, name }
if p == path.as_bytes() && name == b"user.a"),
"{err:?}"
);
}
}
model_of(
TreeBuilder::new()
.file("/f", b"hello", meta())
.xattr("user.a", "first")
.xattr("user.b", "first"),
);
}
#[test]
fn a_time_with_a_fraction_of_a_second_or_more_is_refused() {
let at = |nanos| crate::Timestamp {
secs: 1_700_000_000,
nanos,
};
model_of(TreeBuilder::new().file("/f", b"x", Metadata::new(0o644, at(999_999_999))));
for meta in [
Metadata::new(0o644, at(1_000_000_000)),
meta().with_times(at(1_500_000_000), at(0), at(0)),
meta().with_birth_time(at(u32::MAX)),
] {
let err = error_of(TreeBuilder::new().file("/f", b"x", meta));
assert!(
matches!(&err, ModelError::TimeOutOfRange { path, nanos, .. }
if path == b"/f" && *nanos >= crate::Timestamp::NANOS_PER_SEC),
"{err:?}"
);
}
}
fn model_of(source: impl Source) -> BtrfsModel {
build_model(
source.into_entries(),
&[],
None,
[0; 16],
SECTOR,
NODE,
TIME,
)
.expect("a buildable tree")
}
fn error_of(source: impl Source) -> ModelError {
build_model(
source.into_entries(),
&[],
None,
[0; 16],
SECTOR,
NODE,
TIME,
)
.expect_err("the tree is refused")
}
fn object(model: &BtrfsModel, subvolume: usize, inode: u64) -> &ModelObject {
model.subvolumes[subvolume]
.objects
.iter()
.find(|o| o.inode == inode)
.expect("an object with that number")
}
#[test]
fn an_empty_source_is_one_subvolume_holding_one_empty_directory() {
let model = model_of(TreeBuilder::new());
assert_eq!(model.subvolumes.len(), 1);
assert_eq!(model.subvolumes[0].objects.len(), 1, "the root directory");
assert_eq!(model.subvolumes[0].id, objectid::FS_TREE);
assert_eq!(model.default_subvolume, objectid::FS_TREE);
assert_eq!(model.content.directories, 1);
assert_eq!(model.content.files, 0);
assert!(model.fidelity.is_faithful());
}
#[test]
fn objects_are_numbered_in_sorted_path_order_whatever_order_a_source_yields() {
let forward = model_of(
TreeBuilder::new()
.directory(b"/a".to_vec(), dir_meta())
.file(b"/a/one".to_vec(), b"1", meta())
.file(b"/b".to_vec(), b"2", meta()),
);
let backward = model_of(
TreeBuilder::new()
.file(b"/b".to_vec(), b"2", meta())
.file(b"/a/one".to_vec(), b"1", meta())
.directory(b"/a".to_vec(), dir_meta()),
);
assert_eq!(forward.subvolumes, backward.subvolumes);
let numbers: Vec<u64> = forward.subvolumes[0]
.objects
.iter()
.map(|o| o.inode)
.collect();
assert_eq!(numbers, [256, 257, 258, 259]);
}
#[test]
fn a_directorys_entries_are_numbered_from_two_and_its_size_counts_them_twice() {
let model = model_of(TreeBuilder::new().file(b"/aa".to_vec(), b"x", meta()).file(
b"/bbb".to_vec(),
b"y",
meta(),
));
let root = object(&model, 0, 256);
let ObjectKind::Directory(entries) = &root.kind else {
panic!("the root is a directory")
};
assert_eq!(
entries.iter().map(|e| e.index).collect::<Vec<_>>(),
[FIRST_DIR_INDEX, FIRST_DIR_INDEX + 1]
);
assert_eq!(root.size(), 2 * (2 + 3));
}
#[test]
fn a_hard_link_is_a_second_name_for_one_object() {
let model = model_of(
TreeBuilder::new()
.file(b"/one".to_vec(), b"x", meta())
.hardlink(b"/two".to_vec(), b"/one".to_vec(), meta()),
);
assert_eq!(model.subvolumes[0].objects.len(), 2);
assert_eq!(model.content.files, 1);
assert_eq!(model.content.names, 2);
let file = object(&model, 0, 257);
assert_eq!(
file.names.iter().map(|n| &n.name).collect::<Vec<_>>(),
[b"one".as_slice(), b"two".as_slice()]
);
let ObjectKind::Directory(entries) = &object(&model, 0, 256).kind else {
panic!("the root is a directory")
};
assert_eq!(entries.len(), 2);
assert!(
entries
.iter()
.all(|e| matches!(e.target, EntryTarget::Inode { inode: 257, .. }))
);
}
#[test]
fn a_chain_of_hard_links_ends_at_the_file_and_a_cycle_is_refused() {
let model = model_of(
TreeBuilder::new()
.file(b"/a".to_vec(), b"x", meta())
.hardlink(b"/b".to_vec(), b"/a".to_vec(), meta())
.hardlink(b"/c".to_vec(), b"/b".to_vec(), meta()),
);
assert_eq!(object(&model, 0, 257).names.len(), 3);
let err = error_of(
TreeBuilder::new()
.hardlink(b"/a".to_vec(), b"/b".to_vec(), meta())
.hardlink(b"/b".to_vec(), b"/a".to_vec(), meta()),
);
assert!(matches!(err, ModelError::HardlinkCycle { .. }), "{err:?}");
}
#[test]
fn a_file_below_a_sector_goes_in_the_metadata_and_one_at_a_sector_does_not() {
let model = model_of(
TreeBuilder::new()
.file(b"/small".to_vec(), vec![b'x'; SECTOR as usize - 1], meta())
.file(b"/large".to_vec(), vec![b'x'; SECTOR as usize], meta()),
);
let large = object(&model, 0, 257);
let small = object(&model, 0, 258);
assert!(matches!(large.kind, ObjectKind::File { inline: false, .. }));
assert!(matches!(small.kind, ObjectKind::File { inline: true, .. }));
assert_eq!(model.content.data_bytes, u64::from(SECTOR));
}
#[test]
fn a_file_too_large_for_a_leaf_is_not_stored_in_one_however_small_the_sector() {
let source = TreeBuilder::new().file(b"/f".to_vec(), vec![b'x'; 8000], meta());
let model = build_model(source.into_entries(), &[], None, [0; 16], 16384, 4096, TIME)
.expect("a buildable tree");
assert!(matches!(
object(&model, 0, 257).kind,
ObjectKind::File { inline: false, .. }
));
}
#[test]
fn an_extended_attribute_no_leaf_holds_is_refused_and_names_the_entry() {
let err = error_of(
TreeBuilder::new()
.file(b"/f".to_vec(), b"x", meta())
.xattr(b"user.big".to_vec(), vec![0u8; NODE as usize]),
);
let ModelError::RecordTooLarge { path, what, .. } = &err else {
panic!("{err:?}")
};
assert_eq!(path, b"/f");
assert_eq!(*what, "extended attribute");
}
#[test]
fn a_hard_link_stating_attributes_other_than_its_targets_is_refused() {
let err = error_of(
TreeBuilder::new()
.file(b"/target".to_vec(), b"x", meta())
.hardlink(b"/link".to_vec(), b"/target".to_vec(), meta())
.xattr(b"user.note".to_vec(), b"v".to_vec()),
);
assert!(
matches!(err, ModelError::LinkCarriesXattrs { .. }),
"{err:?}"
);
let m = model_of(
TreeBuilder::new()
.file(b"/target".to_vec(), b"x", meta())
.xattr(b"user.note".to_vec(), b"v".to_vec())
.hardlink(b"/link".to_vec(), b"/target".to_vec(), meta())
.xattr(b"user.note".to_vec(), b"v".to_vec()),
);
let target = m.subvolumes[0]
.objects
.iter()
.find(|object| object.names.len() == 2)
.expect("the target has two names");
assert_eq!(target.xattrs.len(), 1, "the one attribute, held once");
}
#[test]
fn a_mode_carrying_file_type_bits_is_rejected() {
let err = error_of(TreeBuilder::new().file(b"/f".to_vec(), b"x", {
let mut m = meta();
m.mode = 0o100_644;
m
}));
assert!(
matches!(
err,
ModelError::ModeCarriesFileType {
mode: 0o100_644,
..
}
),
"{err:?}"
);
}
#[test]
fn a_subvolume_takes_the_directory_it_names_and_the_tree_beneath_it() {
let source = TreeBuilder::new()
.directory(b"/@home".to_vec(), dir_meta())
.file(b"/@home/user".to_vec(), b"x", meta())
.file(b"/top".to_vec(), b"y", meta());
let model = build_model(
source.into_entries(),
&[SubvolumeRequest::new(b"/@home".to_vec(), [0x55; 16])],
Some(b"/@home"),
[0; 16],
SECTOR,
NODE,
TIME,
)
.expect("a buildable tree");
assert_eq!(model.subvolumes.len(), 2);
let sub = &model.subvolumes[1];
assert_eq!(sub.id, objectid::FIRST_FREE);
assert_eq!(sub.uuid, [0x55; 16]);
assert_eq!(model.default_subvolume, objectid::FIRST_FREE);
assert_eq!(
sub.objects.iter().map(|o| o.inode).collect::<Vec<_>>(),
[256, 257]
);
let link = sub
.link
.as_ref()
.expect("a subvolume other than the top is named");
assert_eq!(link.parent, objectid::FS_TREE);
assert_eq!(link.dir, 256);
assert_eq!(link.name, b"@home");
let ObjectKind::Directory(entries) = &model.subvolumes[0].objects[0].kind else {
panic!("the root is a directory")
};
assert_eq!(entries.len(), 2);
assert_eq!(
entries[0].target,
EntryTarget::Subvolume {
id: objectid::FIRST_FREE
}
);
assert_eq!(model.content.subvolumes, 1);
}
#[test]
fn a_hard_link_across_a_subvolume_boundary_is_refused_rather_than_copied() {
let source = TreeBuilder::new()
.directory(b"/sub".to_vec(), dir_meta())
.file(b"/target".to_vec(), b"x", meta())
.hardlink(b"/sub/link".to_vec(), b"/target".to_vec(), meta());
let err = build_model(
source.into_entries(),
&[SubvolumeRequest::new(b"/sub".to_vec(), [0x55; 16])],
None,
[0; 16],
SECTOR,
NODE,
TIME,
)
.expect_err("the tree is refused");
assert!(
matches!(err, ModelError::HardlinkCrossesSubvolume { .. }),
"{err:?}"
);
}
#[test]
fn a_subvolume_asked_for_where_no_directory_is_declared_is_refused() {
let source = TreeBuilder::new().file(b"/f".to_vec(), b"x", meta());
for (request, default) in [
(Some(b"/f".to_vec()), None),
(Some(b"/nowhere".to_vec()), None),
] {
let requests = request.map(|p| SubvolumeRequest::new(p, [0; 16]));
let err = build_model(
source.clone().into_entries(),
requests.as_slice(),
default,
[0; 16],
SECTOR,
NODE,
TIME,
)
.expect_err("the request is refused");
assert!(
matches!(err, ModelError::SubvolumeNotADirectory { .. }),
"{err:?}"
);
}
}
#[test]
fn every_refusal_a_path_can_earn_names_the_path() {
let cases: Vec<(ModelError, &[u8])> = vec![
(
error_of(TreeBuilder::new().file(b"/../x".to_vec(), b"x", meta())),
b"/../x",
),
(
error_of(TreeBuilder::new().file(b"/x".to_vec(), b"x", meta()).file(
b"//x".to_vec(),
b"y",
meta(),
)),
b"//x",
),
(
error_of(TreeBuilder::new().file(vec![b'n'; MAX_NAME_LEN + 1], b"x", meta())),
&[b'n'; MAX_NAME_LEN + 1],
),
(
error_of(TreeBuilder::new().file(b"/missing/x".to_vec(), b"x", meta())),
b"/missing/x",
),
(
error_of(TreeBuilder::new().file(b"/f".to_vec(), b"x", meta()).file(
b"/f/under".to_vec(),
b"y",
meta(),
)),
b"/f/under",
),
(
error_of(
TreeBuilder::new()
.root(meta())
.file(b"/".to_vec(), b"x", meta()),
),
b"/",
),
];
for (err, path) in cases {
let text = err.to_string();
let printable = crate::escape::printable(path);
assert!(
text.contains(&printable),
"{text} does not name {printable}"
);
}
}
#[test]
fn the_root_is_described_by_a_source_rather_than_created_by_one() {
let model = model_of(
TreeBuilder::new()
.root(Metadata::new(0o700, crate::Timestamp::from_secs(42)).owned_by(1, 2))
.xattr(b"user.on-the-root".to_vec(), b"v".to_vec()),
);
let root = object(&model, 0, 256);
assert_eq!(root.meta.mode, 0o700);
assert_eq!((root.meta.uid, root.meta.gid), (1, 2));
assert_eq!(root.xattrs.len(), 1);
assert_eq!(model.content.directories, 1);
}
}