use std::collections::{BTreeMap, HashMap};
use crate::Timestamp;
use crate::fidelity::FidelityReport;
use crate::path::canonical_key;
use crate::source::{
ClassifyError, CompressedFile, Darwin, EntryKind, FileContent, LinkEnd, LinkStep,
MODE_TYPE_MASK, Metadata, PathFault, SourceEntry, classify_paths, follow_hard_link,
};
use crate::xattr::{Xattr, repeated_name, same_xattrs};
use super::bulk;
use super::decmpfs::{self, Layout};
use super::names::{self, NameFault, UnicodeVersion};
use super::ondisk::{
DECMPFS_XATTR, RESOURCE_FORK_XATTR, SYMLINK_XATTR, XattrValue, inode_number, xattr_key_size,
};
pub const MAX_EMBEDDED_XATTR: usize = 3800;
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum CompressedFault {
#[error("the compression header is not one")]
NotAHeader,
#[error("compression type {0} is not one a read of the volume decodes")]
UnknownType(u32),
#[error(
"the compression header gives {declared} bytes of content, where the file holds {held}"
)]
#[non_exhaustive]
LengthDiffers {
declared: u64,
held: u64,
},
#[error("compression type {0} keeps its content in a resource fork, and none is given")]
ForkMissing(u32),
#[error(
"compression type {0} keeps its content after its header, and a resource fork is given"
)]
ForkGiven(u32),
#[error("content kept after its compression header is {0} bytes, past one chunk of 65536")]
InlineTooLarge(u64),
#[error(
"a compression attribute of {0} bytes, past the {max} macOS keeps a compressed file with",
max = decmpfs::MAX_INLINE
)]
AttributeTooLong(u64),
}
fn compressed_fault(form: &CompressedFile, held: u64) -> Option<CompressedFault> {
let Some(header) = decmpfs::Header::read_from(&form.header) else {
return Some(CompressedFault::NotAHeader);
};
let Some((layout, _)) = decmpfs::layout(header.method) else {
return Some(CompressedFault::UnknownType(header.method));
};
if header.size != held {
return Some(CompressedFault::LengthDiffers {
declared: header.size,
held,
});
}
match (layout, &form.fork) {
(Layout::Inline, Some(_)) => Some(CompressedFault::ForkGiven(header.method)),
(Layout::Inline, None) if decmpfs::chunk_count(held) > 1 => {
Some(CompressedFault::InlineTooLarge(held))
}
(Layout::Inline, None) if form.header.len() as u64 > decmpfs::MAX_INLINE => {
Some(CompressedFault::AttributeTooLong(form.header.len() as u64))
}
(Layout::Offsets | Layout::Resource, None) => {
Some(CompressedFault::ForkMissing(header.method))
}
_ => None,
}
}
pub(crate) const MAX_EMBEDDED_HEADER: usize = 128;
pub const MAX_SYMLINK_TARGET: usize = 1023;
pub const MAX_XATTR_VALUE: u64 = (1 << 31) - 1;
pub const MAX_XATTR_NAME: usize = 127;
const _: () = assert!(
xattr_key_size(MAX_XATTR_NAME) + XattrValue::HEADER_SIZE + MAX_EMBEDDED_XATTR
<= bulk::largest_entry(4096)
);
const MAX_DEVICE_MAJOR: u32 = 0xFF;
const MAX_DEVICE_MINOR: u32 = 0x00FF_FFFF;
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ModelError {
#[error(
"{}: its contents are declared by length alone, and this writer reads every file's bytes",
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("entry {} names the root but is not a directory", crate::escape::printable(.path))]
#[non_exhaustive]
RootNotDirectory {
path: 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("{}: the name is not UTF-8", crate::escape::printable(.path))]
#[non_exhaustive]
NameNotUtf8 {
path: Vec<u8>,
},
#[error("{}: the name holds a NUL", crate::escape::printable(.path))]
#[non_exhaustive]
NameHoldsNul {
path: Vec<u8>,
},
#[error(
"{}: the name is {units} UTF-16 code units, and macOS creates none longer than 255",
crate::escape::printable(.path)
)]
#[non_exhaustive]
NameTooLong {
path: Vec<u8>,
units: usize,
},
#[error(
"{}: the name holds U+{code_point:04X}, which macOS refuses in a name under Unicode \
{}.{}",
crate::escape::printable(.path),
.unicode.0,
.unicode.1
)]
#[non_exhaustive]
NameRefused {
path: Vec<u8>,
code_point: u32,
unicode: (u8, u8),
},
#[error(
"{} and {} are one name on this volume",
crate::escape::printable(.first),
crate::escape::printable(.second)
)]
#[non_exhaustive]
NamesCompareEqual {
first: Vec<u8>,
second: 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(
"{}: device {major}:{minor} does not fit an 8-bit major and a 24-bit minor",
crate::escape::printable(.path)
)]
#[non_exhaustive]
DeviceNumberTooLarge {
path: Vec<u8>,
major: u32,
minor: u32,
},
#[error(
"{}: a link target of {bytes} bytes, empty, or holding a NUL; macOS creates targets of 1 \
to {MAX_SYMLINK_TARGET} bytes",
crate::escape::printable(.path)
)]
#[non_exhaustive]
SymlinkTarget {
path: Vec<u8>,
bytes: usize,
},
#[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 name {} is not UTF-8, which macOS neither sets nor passes in a check",
crate::escape::printable(.path),
crate::escape::printable(.name)
)]
#[non_exhaustive]
XattrNameNotUtf8 {
path: Vec<u8>,
name: Vec<u8>,
},
#[error(
"{}: a device node carries attributes, which macOS neither lists, reads nor sets on one",
crate::escape::printable(.path)
)]
#[non_exhaustive]
XattrOnDevice {
path: Vec<u8>,
},
#[error(
"{}: an attribute name of {} bytes, past the {MAX_XATTR_NAME} macOS sets",
crate::escape::printable(.path),
.name.len()
)]
#[non_exhaustive]
XattrNameTooLong {
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(
"{}: the attribute {} is {bytes} bytes, and macOS sets none larger than \
{MAX_XATTR_VALUE}",
crate::escape::printable(.path),
crate::escape::printable(.name)
)]
#[non_exhaustive]
XattrTooLarge {
path: Vec<u8>,
name: Vec<u8>,
bytes: u64,
},
#[error(
"{}: a time of {secs} seconds and {nanos} nanoseconds since 1970 is outside what an \
inode records",
crate::escape::printable(.path)
)]
#[non_exhaustive]
TimeOutOfRange {
path: Vec<u8>,
secs: i64,
nanos: u32,
},
#[error(
"{}: a birth time {secs} seconds before 1970 is one macOS will not read",
crate::escape::printable(.path),
secs = .secs.unsigned_abs()
)]
#[non_exhaustive]
BirthTimeBeforeEpoch {
path: Vec<u8>,
secs: i64,
},
#[error(
"{}: a compressed form on an entry that is not a regular file",
crate::escape::printable(.path)
)]
#[non_exhaustive]
CompressedNotAFile {
path: Vec<u8>,
},
#[error("{}: {fault}", crate::escape::printable(.path))]
#[non_exhaustive]
CompressedForm {
path: Vec<u8>,
fault: CompressedFault,
},
#[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(
"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>,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) enum InodeKind {
Directory(Vec<Child>),
File {
size: u64,
stream: Option<u64>,
},
Symlink(Vec<u8>),
Device {
block: bool,
number: u32,
},
Fifo,
Socket,
}
impl InodeKind {
pub(crate) const fn mode_bits(&self) -> u16 {
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) -> u16 {
match self {
Self::Fifo => 1,
Self::Device { block: false, .. } => 2,
Self::Directory(_) => 4,
Self::Device { block: true, .. } => 6,
Self::File { .. } => 8,
Self::Symlink(_) => 10,
Self::Socket => 12,
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct Child {
pub(crate) name: Vec<u8>,
pub(crate) hash: u32,
pub(crate) inode: u64,
pub(crate) entry_type: u16,
pub(crate) sibling: Option<u64>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct Sibling {
pub(crate) id: u64,
pub(crate) parent: u64,
pub(crate) name: Vec<u8>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) enum ModelXattr {
Embedded {
name: Vec<u8>,
value: Vec<u8>,
flags: u16,
},
Stream {
name: Vec<u8>,
stream: u64,
flags: u16,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct Inode {
pub(crate) id: u64,
pub(crate) parent: u64,
pub(crate) name: Vec<u8>,
pub(crate) kind: InodeKind,
pub(crate) meta: Metadata,
pub(crate) xattrs: Vec<ModelXattr>,
pub(crate) links: u32,
pub(crate) siblings: Vec<Sibling>,
pub(crate) bsd_flags: u32,
pub(crate) compressed: bool,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) enum StreamBytes {
File(FileContent),
Held(Vec<u8>),
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct Stream {
pub(crate) id: u64,
pub(crate) owner: u64,
pub(crate) len: u64,
pub(crate) bytes: StreamBytes,
pub(crate) written: u64,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub(crate) struct Counts {
pub(crate) files: u64,
pub(crate) directories: u64,
pub(crate) symlinks: u64,
pub(crate) other: u64,
}
#[derive(Clone, Debug)]
pub(crate) struct ApfsModel {
pub(crate) root: Inode,
pub(crate) inodes: Vec<Inode>,
pub(crate) streams: Vec<Stream>,
pub(crate) next_object_id: u64,
pub(crate) counts: Counts,
pub(crate) fidelity: FidelityReport,
}
pub(crate) fn build_model(
entries: Vec<SourceEntry>,
fold: bool,
unicode: UnicodeVersion,
root: Metadata,
first: u64,
) -> Result<ApfsModel, ModelError> {
Builder {
fold,
unicode,
next: first,
inodes: Vec::new(),
streams: Vec::new(),
attribute_streams: Vec::new(),
counts: Counts::default(),
}
.build(entries, root)
}
pub(crate) fn nanos_of(time: Timestamp) -> Option<i64> {
if !time.has_proper_fraction() {
return None;
}
time.secs
.checked_mul(i64::from(Timestamp::NANOS_PER_SEC))?
.checked_add(i64::from(time.nanos))
}
#[derive(Clone, PartialEq, Eq, Debug)]
enum Class {
Directory,
Object,
Link(Vec<u8>),
}
struct Planned {
key: Vec<u8>,
name: Vec<u8>,
hash: u32,
form: Vec<u32>,
}
struct Frame {
slot: Slot,
entries: Vec<Planned>,
next: usize,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Slot {
Root,
At(usize),
}
struct Builder {
fold: bool,
unicode: UnicodeVersion,
next: u64,
inodes: Vec<Inode>,
streams: Vec<Stream>,
attribute_streams: Vec<Stream>,
counts: Counts,
}
impl Builder {
fn build(
mut self,
entries: Vec<SourceEntry>,
root_meta: Metadata,
) -> Result<ApfsModel, ModelError> {
let classes = classify_paths(
&entries,
|entry, parts| self.class_of(entry, parts),
|class| *class == Class::Directory,
)
.map_err(|e| match 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 }
}
ClassifyError::Class(e) => e,
})?;
let by_key: HashMap<Vec<u8>, &SourceEntry> = entries
.iter()
.map(|entry| (canonical_key(&entry.path), entry))
.collect();
let mut children: BTreeMap<Vec<u8>, Vec<Planned>> = BTreeMap::new();
for entry in &entries {
let key = canonical_key(&entry.path);
if key.is_empty() {
continue;
}
let (parent, name) = match key.iter().rposition(|&b| b == b'/') {
Some(at) => (key[..at].to_vec(), key[at + 1..].to_vec()),
None => (Vec::new(), key.clone()),
};
if !parent.is_empty() {
match classes.get(&parent) {
None => {
return Err(ModelError::ParentMissing {
path: entry.path.clone(),
});
}
Some(Class::Directory) => {}
Some(_) => {
return Err(ModelError::ParentNotDir {
path: entry.path.clone(),
});
}
}
}
let form = names::key(&name, self.fold).expect("a name was held to UTF-8");
children.entry(parent).or_default().push(Planned {
key: key.clone(),
hash: names::hash(&form),
form,
name,
});
}
for list in children.values_mut() {
list.sort_by(|a, b| a.hash.cmp(&b.hash).then_with(|| a.name.cmp(&b.name)));
let mut seen: HashMap<&[u32], &Planned> = HashMap::with_capacity(list.len());
for b in list.iter() {
if let Some(a) = seen.insert(&b.form, b) {
return Err(ModelError::NamesCompareEqual {
first: by_key[&a.key].path.clone(),
second: by_key[&b.key].path.clone(),
});
}
}
}
let mut object_of: HashMap<Vec<u8>, Vec<u8>> = HashMap::new();
for entry in &entries {
let key = canonical_key(&entry.path);
let Some(Class::Link(target)) = classes.get(&key) else {
continue;
};
let end = follow_hard_link(target, classes.len(), |at| match classes.get(at) {
None => LinkStep::Missing,
Some(Class::Directory) => LinkStep::Directory,
Some(Class::Object) => LinkStep::File(at.to_vec()),
Some(Class::Link(next)) => LinkStep::Link(next.clone()),
});
let object = match end {
LinkEnd::File(object) => object,
LinkEnd::Missing | LinkEnd::Unrepresentable => {
return Err(ModelError::HardlinkTargetMissing {
path: entry.path.clone(),
target: target.clone(),
});
}
LinkEnd::Directory => {
return Err(ModelError::HardlinkTargetIsDirectory {
path: entry.path.clone(),
target: target.clone(),
});
}
LinkEnd::Cycle => {
return Err(ModelError::HardlinkCycle {
path: entry.path.clone(),
});
}
};
if !entry.xattrs.is_empty() && !same_xattrs(&entry.xattrs, &by_key[&object].xattrs) {
return Err(ModelError::LinkCarriesXattrs {
path: entry.path.clone(),
});
}
object_of.insert(key, object);
}
let (root_meta, root_xattrs, root_darwin) = match by_key.get(&Vec::new()) {
Some(entry) => (entry.meta, entry.xattrs.clone(), entry.darwin.clone()),
None => (root_meta, Vec::new(), None),
};
let root_darwin = root_darwin.as_ref();
let mut root = Inode {
id: inode_number::ROOT,
parent: inode_number::ROOT_PARENT,
name: b"root".to_vec(),
kind: InodeKind::Directory(Vec::new()),
meta: root_meta,
xattrs: Vec::new(),
links: 1,
siblings: Vec::new(),
bsd_flags: root_darwin.map_or(0, Darwin::stated_flags),
compressed: false,
};
root.xattrs = self.xattrs(inode_number::ROOT, &root_xattrs, false);
let mut placed: HashMap<Vec<u8>, usize> = HashMap::new();
let mut first_entry: Vec<usize> = Vec::new();
let mut stack = vec![Frame {
slot: Slot::Root,
entries: children.remove(&Vec::new()).unwrap_or_default(),
next: 0,
}];
while let Some(frame) = stack.last_mut() {
let Some(planned) = frame.entries.get(frame.next) else {
stack.pop();
continue;
};
frame.next += 1;
let parent_slot = frame.slot;
let parent_id = match parent_slot {
Slot::Root => inode_number::ROOT,
Slot::At(i) => self.inodes[i].id,
};
let object = object_of.get(&planned.key).unwrap_or(&planned.key).clone();
let name = planned.name.clone();
let hash = planned.hash;
let key = planned.key.clone();
let mut new_inode = None;
let child = if let Some(&at) = placed.get(&object) {
if self.inodes[at].siblings.is_empty() {
let first = self.take();
let (first_parent, first_name) =
(self.inodes[at].parent, self.inodes[at].name.clone());
self.inodes[at].siblings.push(Sibling {
id: first,
parent: first_parent,
name: first_name.clone(),
});
let entry = self
.child_at(&mut root, first_parent, first_entry[at])
.expect("an inode's first name is in its directory");
debug_assert_eq!(entry.name, first_name);
entry.sibling = Some(first);
}
let id = self.take();
self.inodes[at].siblings.push(Sibling {
id,
parent: parent_id,
name: name.clone(),
});
self.inodes[at].links += 1;
Child {
name,
hash,
inode: self.inodes[at].id,
entry_type: self.inodes[at].kind.entry_type(),
sibling: Some(id),
}
} else {
let entry = by_key[&object];
let id = self.take();
let darwin = entry.darwin.as_ref();
let compressed = darwin.and_then(|d| d.compressed.as_ref());
let kind = match &entry.kind {
EntryKind::Directory => {
self.counts.directories += 1;
InodeKind::Directory(Vec::new())
}
EntryKind::File(content) if compressed.is_some() => {
self.counts.files += 1;
InodeKind::File {
size: content.len(),
stream: None,
}
}
EntryKind::File(content) => {
self.counts.files += 1;
let size = content.len();
let stream = (size > 0).then_some(id);
if size > 0 {
self.streams.push(Stream {
id,
owner: id,
len: size,
bytes: StreamBytes::File(content.clone()),
written: size,
});
}
InodeKind::File { size, stream }
}
EntryKind::Symlink(target) => {
self.counts.symlinks += 1;
InodeKind::Symlink(target.clone())
}
EntryKind::CharDevice { major, minor } => {
self.counts.other += 1;
InodeKind::Device {
block: false,
number: (major << 24) | minor,
}
}
EntryKind::BlockDevice { major, minor } => {
self.counts.other += 1;
InodeKind::Device {
block: true,
number: (major << 24) | minor,
}
}
EntryKind::Fifo => {
self.counts.other += 1;
InodeKind::Fifo
}
EntryKind::Socket => {
self.counts.other += 1;
InodeKind::Socket
}
EntryKind::HardLink { .. } => {
unreachable!("a link's chain ends at an object, never at a link")
}
};
let mut given = entry.xattrs.clone();
if let Some(form) = compressed {
given.push(Xattr {
name: DECMPFS_XATTR.to_vec(),
value: form.header.clone(),
});
if let Some(fork) = &form.fork {
given.push(Xattr {
name: RESOURCE_FORK_XATTR.to_vec(),
value: fork.clone(),
});
}
}
let xattrs = self.xattrs(id, &given, compressed.is_some());
let bsd_flags = darwin.map_or(0, Darwin::stated_flags)
| if compressed.is_some() {
Darwin::COMPRESSED
} else {
0
};
let entry_type = kind.entry_type();
let is_directory = matches!(kind, InodeKind::Directory(_));
self.inodes.push(Inode {
id,
parent: parent_id,
name: name.clone(),
kind,
meta: entry.meta,
xattrs,
links: 1,
siblings: Vec::new(),
bsd_flags,
compressed: compressed.is_some(),
});
let at = self.inodes.len() - 1;
placed.insert(object, at);
new_inode = Some(at);
if is_directory {
stack.push(Frame {
slot: Slot::At(at),
entries: children.remove(&key).unwrap_or_default(),
next: 0,
});
}
Child {
name,
hash,
inode: id,
entry_type,
sibling: None,
}
};
let directory = match parent_slot {
Slot::Root => &mut root,
Slot::At(i) => &mut self.inodes[i],
};
let InodeKind::Directory(entries) = &mut directory.kind else {
unreachable!("only a directory is entered");
};
if let Some(at) = new_inode {
if first_entry.len() <= at {
first_entry.resize(at + 1, usize::MAX);
}
first_entry[at] = entries.len();
}
entries.push(child);
}
let mut streams = self.streams;
self.attribute_streams.sort_by_key(|stream| stream.id);
streams.extend(self.attribute_streams);
Ok(ApfsModel {
root,
inodes: self.inodes,
streams,
next_object_id: self.next,
counts: self.counts,
fidelity: FidelityReport::new(),
})
}
fn take(&mut self) -> u64 {
let id = self.next;
self.next += 1;
id
}
fn child_at<'a>(
&'a mut self,
root: &'a mut Inode,
parent: u64,
index: usize,
) -> Option<&'a mut Child> {
let directory = if parent == inode_number::ROOT {
root
} else {
let at = self.inodes.binary_search_by_key(&parent, |i| i.id).ok()?;
&mut self.inodes[at]
};
let InodeKind::Directory(entries) = &mut directory.kind else {
return None;
};
entries.get_mut(index)
}
fn xattrs(&mut self, id: u64, given: &[Xattr], compressed: bool) -> Vec<ModelXattr> {
let mut sorted: Vec<&Xattr> = given.iter().collect();
sorted.sort_by(|a, b| a.name.cmp(&b.name));
sorted
.into_iter()
.map(|xattr| {
let header = compressed && xattr.name == DECMPFS_XATTR;
let fork = xattr.name == RESOURCE_FORK_XATTR || header;
let limit = if header {
MAX_EMBEDDED_HEADER
} else {
MAX_EMBEDDED_XATTR
};
if (header || !fork) && xattr.value.len() <= limit {
return ModelXattr::Embedded {
name: xattr.name.clone(),
value: xattr.value.clone(),
flags: super::ondisk::xattr_flags::EMBEDDED,
};
}
let stream = self.take();
let len = xattr.value.len() as u64;
self.attribute_streams.push(Stream {
id: stream,
owner: id,
len,
bytes: StreamBytes::Held(xattr.value.clone()),
written: if fork { len } else { 0 },
});
ModelXattr::Stream {
name: xattr.name.clone(),
stream,
flags: if fork {
super::ondisk::xattr_flags::STREAM
} else {
super::ondisk::xattr_flags::STREAM
| super::ondisk::xattr_flags::SET_THROUGH_SETXATTR
},
}
})
.collect()
}
fn class_of(&self, entry: &SourceEntry, parts: &[&[u8]]) -> Result<Class, ModelError> {
let path = || entry.path.clone();
if let Some(name) = parts.last() {
if name.contains(&0) {
return Err(ModelError::NameHoldsNul { path: path() });
}
names::check(name, self.unicode).map_err(|fault| match fault {
NameFault::NotUtf8 => ModelError::NameNotUtf8 { path: path() },
NameFault::TooLong(units) => ModelError::NameTooLong {
path: path(),
units,
},
NameFault::Unassigned(code_point) | NameFault::Noncharacter(code_point) => {
ModelError::NameRefused {
path: path(),
code_point,
unicode: self.unicode,
}
}
})?;
}
let times = [entry.meta.atime, entry.meta.ctime, entry.meta.mtime];
for time in times.into_iter().chain(entry.meta.btime) {
if nanos_of(time).is_none() {
return Err(ModelError::TimeOutOfRange {
path: path(),
secs: time.secs,
nanos: time.nanos,
});
}
}
if let Some(btime) = entry.meta.btime
&& btime.secs < 0
{
return Err(ModelError::BirthTimeBeforeEpoch {
path: path(),
secs: btime.secs,
});
}
if entry.meta.mode & MODE_TYPE_MASK != 0 {
return Err(ModelError::ModeCarriesFileType {
path: path(),
mode: entry.meta.mode,
});
}
if !entry.xattrs.is_empty()
&& matches!(
entry.kind,
EntryKind::CharDevice { .. } | EntryKind::BlockDevice { .. }
)
{
return Err(ModelError::XattrOnDevice { path: path() });
}
for xattr in &entry.xattrs {
let name = &xattr.name;
if name.is_empty() || name.contains(&0) || name == SYMLINK_XATTR {
return Err(ModelError::XattrName {
path: path(),
name: name.clone(),
});
}
if std::str::from_utf8(name).is_err() {
return Err(ModelError::XattrNameNotUtf8 {
path: path(),
name: name.clone(),
});
}
if name.len() > MAX_XATTR_NAME {
return Err(ModelError::XattrNameTooLong {
path: path(),
name: name.clone(),
});
}
if xattr.value.len() as u64 > MAX_XATTR_VALUE {
return Err(ModelError::XattrTooLarge {
path: path(),
name: name.clone(),
bytes: xattr.value.len() as u64,
});
}
}
if let Some(name) = repeated_name(&entry.xattrs) {
return Err(ModelError::XattrRepeated {
path: path(),
name: name.to_vec(),
});
}
if let Some(form) = entry.darwin.as_ref().and_then(|d| d.compressed.as_ref()) {
let EntryKind::File(content) = &entry.kind else {
return Err(ModelError::CompressedNotAFile { path: path() });
};
if let Some(fault) = compressed_fault(form, content.len()) {
return Err(ModelError::CompressedForm {
path: path(),
fault,
});
}
for name in [DECMPFS_XATTR, RESOURCE_FORK_XATTR] {
if entry.xattrs.iter().any(|x| x.name == name) {
return Err(ModelError::XattrName {
path: path(),
name: name.to_vec(),
});
}
}
for (name, value) in [
(DECMPFS_XATTR, Some(&form.header)),
(RESOURCE_FORK_XATTR, form.fork.as_ref()),
] {
if let Some(value) = value.filter(|v| v.len() as u64 > MAX_XATTR_VALUE) {
return Err(ModelError::XattrTooLarge {
path: path(),
name: name.to_vec(),
bytes: value.len() as u64,
});
}
}
}
Ok(match &entry.kind {
EntryKind::Directory => Class::Directory,
EntryKind::HardLink { target } => Class::Link(canonical_key(target)),
EntryKind::File(FileContent::Declared { .. }) => {
return Err(ModelError::ContentsNotHeld { path: path() });
}
EntryKind::Symlink(target) => {
if target.is_empty() || target.len() > MAX_SYMLINK_TARGET || target.contains(&0) {
return Err(ModelError::SymlinkTarget {
path: path(),
bytes: target.len(),
});
}
Class::Object
}
EntryKind::CharDevice { major, minor } | EntryKind::BlockDevice { major, minor } => {
if *major > MAX_DEVICE_MAJOR || *minor > MAX_DEVICE_MINOR {
return Err(ModelError::DeviceNumberTooLarge {
path: path(),
major: *major,
minor: *minor,
});
}
Class::Object
}
EntryKind::File(_) | EntryKind::Fifo | EntryKind::Socket => Class::Object,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Source, TreeBuilder};
const FOLDING: bool = true;
const UNICODE: UnicodeVersion = (17, 0);
fn meta(mode: u16) -> Metadata {
Metadata::new(mode, Timestamp::from_secs(1_600_000_000))
}
fn model(source: impl Source, fold: bool) -> Result<ApfsModel, ModelError> {
build_model(
source.into_entries(),
fold,
UNICODE,
meta(0o755),
inode_number::FIRST_USER,
)
}
fn simple() -> Vec<SourceEntry> {
let sizes: [(&str, usize); 12] = [
("top/empty", 0),
("top/one", 1),
("top/hundred", 100),
("top/under", 4095),
("top/block", 4096),
("top/over", 4097),
("top/three", 12288),
("top/sub1/sixtyfour", 65536),
("top/sub1/mega", (1 << 20) + 3),
("top/sub2/deep/a", 10),
("top/sub2/deep/b", 20000),
("top/sub2/\u{E9}cole", 300),
];
let mut tree = TreeBuilder::new();
for dir in [
"top",
"top/sub1",
"top/sub2",
"top/sub2/deep",
"top/sub2/empty-dir",
] {
tree = tree.directory(format!("/{dir}"), meta(0o755));
}
for (path, size) in sizes {
tree = tree.file(format!("/{path}"), vec![7u8; size], meta(0o644));
}
for i in 0..30 {
tree = tree.file(format!("/top/sub1/n{i:02}"), vec![1u8; 50 * i], meta(0o644));
}
let entries = tree
.symlink("/top/link-rel", "block", meta(0o755))
.symlink("/top/link-abs", "/nowhere/at/all", meta(0o755))
.hardlink("/top/sub1/three-again", "/top/three", meta(0o644))
.into_entries();
entries
.into_iter()
.map(|entry| match entry.path.as_slice() {
b"/top/block" => entry.with_xattrs(vec![Xattr {
name: b"user.small".to_vec(),
value: vec![3u8; 16],
}]),
b"/top/over" => entry.with_xattrs(vec![Xattr {
name: b"user.big".to_vec(),
value: vec![4u8; 8000],
}]),
_ => entry,
})
.collect()
}
fn named(model: &ApfsModel) -> BTreeMap<Vec<u8>, (u64, Option<u64>)> {
let mut out = BTreeMap::new();
let mut todo = vec![(Vec::new(), &model.root)];
while let Some((path, dir)) = todo.pop() {
let InodeKind::Directory(children) = &dir.kind else {
continue;
};
for child in children {
let mut name = path.clone();
if !name.is_empty() {
name.push(b'/');
}
name.extend_from_slice(&child.name);
out.insert(name.clone(), (child.inode, child.sibling));
if let Some(inode) = model.inodes.iter().find(|i| i.id == child.inode)
&& (child.sibling.is_none() || inode.name == child.name)
{
todo.push((name, inode));
}
}
}
out
}
#[test]
fn a_tree_is_numbered_as_hdiutil_numbered_it() {
let model = model(simple(), FOLDING).expect("a model");
let expected: &[(&str, u64)] = &[
("top", 16),
("top/hundred", 17),
("top/empty", 18),
("top/link-abs", 19),
("top/link-rel", 20),
("top/sub1", 21),
("top/sub1/n23", 22),
("top/sub1/n24", 23),
("top/sub1/n12", 24),
("top/sub1/n15", 25),
("top/sub1/n14", 26),
("top/sub1/n13", 27),
("top/sub1/n25", 28),
("top/sub1/n22", 29),
("top/sub1/sixtyfour", 30),
("top/sub1/n00", 31),
("top/sub1/n07", 32),
("top/sub1/n09", 33),
("top/sub1/n08", 34),
("top/sub1/n06", 35),
("top/sub1/n01", 36),
("top/sub1/n27", 37),
("top/sub1/n18", 38),
("top/sub1/n20", 39),
("top/sub1/n16", 40),
("top/sub1/n29", 41),
("top/sub1/n11", 42),
("top/sub1/n10", 43),
("top/sub1/n17", 44),
("top/sub1/n28", 45),
("top/sub1/n21", 46),
("top/sub1/n26", 47),
("top/sub1/n19", 48),
("top/sub1/three-again", 49),
("top/sub1/mega", 50),
("top/sub1/n04", 51),
("top/sub1/n03", 52),
("top/sub1/n02", 53),
("top/sub1/n05", 54),
("top/over", 55),
("top/three", 49),
("top/one", 59),
("top/sub2", 60),
("top/sub2/deep", 61),
("top/sub2/deep/a", 62),
("top/sub2/deep/b", 63),
("top/sub2/empty-dir", 64),
("top/sub2/\u{E9}cole", 65),
("top/under", 66),
("top/block", 67),
];
let names = named(&model);
for (path, id) in expected {
assert_eq!(names[path.as_bytes()].0, *id, "{path}");
}
assert_eq!(names.len(), expected.len());
assert_eq!(names[b"top/sub1/three-again".as_slice()].1, Some(57));
assert_eq!(names[b"top/three".as_slice()].1, Some(58));
assert_eq!(model.next_object_id, 68);
let over = model.inodes.iter().find(|i| i.id == 55).unwrap();
assert_eq!(
over.xattrs,
[ModelXattr::Stream {
name: b"user.big".to_vec(),
stream: 56,
flags: 0x11
}]
);
let three = model.inodes.iter().find(|i| i.id == 49).unwrap();
assert_eq!(
(three.parent, three.name.as_slice(), three.links),
(21, &b"three-again"[..], 2)
);
assert_eq!(
model.counts,
Counts {
files: 42,
directories: 5,
symlinks: 2,
other: 0
}
);
}
#[test]
fn two_names_one_directory_compares_as_one_are_refused() {
let folding = TreeBuilder::new().file("/Read Me", "a", meta(0o644)).file(
"/read me",
"b",
meta(0o644),
);
assert!(matches!(
model(folding.clone(), true),
Err(ModelError::NamesCompareEqual { .. })
));
assert!(model(folding, false).is_ok());
let composed = TreeBuilder::new()
.file("/caf\u{E9}", "a", meta(0o644))
.file("/cafe\u{301}", "b", meta(0o644));
assert!(matches!(
model(composed, false),
Err(ModelError::NamesCompareEqual { .. })
));
}
#[test]
fn a_name_macos_refuses_is_refused() {
let refused: [(Vec<u8>, &str); 5] = [
(b"/a\xffb".to_vec(), "NameNotUtf8"),
(b"/a\0b".to_vec(), "NameHoldsNul"),
("/\u{378}".into(), "NameRefused"),
("/\u{FDD0}".into(), "NameRefused"),
(format!("/{}", "\u{20AC}".repeat(256)).into(), "NameTooLong"),
];
for (path, want) in refused {
let err =
model(TreeBuilder::new().file(path, "x", meta(0o644)), true).expect_err("refused");
assert!(format!("{err:?}").starts_with(want), "{err:?}");
}
}
#[test]
fn a_birth_time_before_1970_is_refused() {
let before = Timestamp::from_secs(-1);
for path in ["/f", "/"] {
let entry = SourceEntry::new(
path,
if path == "/" {
EntryKind::Directory
} else {
EntryKind::File(b"x".to_vec().into())
},
meta(0o755).with_birth_time(before),
);
let err = model(vec![entry], true).expect_err("refused");
assert!(
matches!(&err, ModelError::BirthTimeBeforeEpoch { secs: -1, path: p } if p == path.as_bytes()),
"{err:?}"
);
}
let modified = Metadata::new(0o644, before).with_birth_time(Timestamp::from_secs(0));
model(TreeBuilder::new().file("/f", "x", modified), true).expect("held");
}
#[test]
fn an_attribute_is_held_in_its_record_to_3800_bytes_and_a_resource_fork_never_is() {
let entry = SourceEntry::new("/f", EntryKind::File(b"x".to_vec().into()), meta(0o644))
.with_xattrs(vec![
Xattr {
name: b"user.at".to_vec(),
value: vec![1; 3800],
},
Xattr {
name: b"user.past".to_vec(),
value: vec![1; 3801],
},
Xattr {
name: RESOURCE_FORK_XATTR.to_vec(),
value: vec![1; 4],
},
]);
let model = model(vec![entry], true).expect("a model");
let flags: Vec<(&[u8], bool, u16)> = model.inodes[0]
.xattrs
.iter()
.map(|x| match x {
ModelXattr::Embedded { name, flags, .. } => (name.as_slice(), true, *flags),
ModelXattr::Stream { name, flags, .. } => (name.as_slice(), false, *flags),
})
.collect();
assert_eq!(
flags,
[
(RESOURCE_FORK_XATTR, false, 0x1),
(&b"user.at"[..], true, 0x2),
(&b"user.past"[..], false, 0x11),
]
);
let written: Vec<(u64, u64)> = model.streams.iter().map(|s| (s.len, s.written)).collect();
assert_eq!(written, [(1, 1), (4, 4), (3801, 0)]);
}
#[test]
fn a_firmlink_is_held_in_its_record_at_the_longest_target_a_line_may_give() {
use super::super::firmlink::{FIRMLINK_XATTR, Firmlinks, MAX_FIRMLINK_TARGET, mark};
let target = vec![b'a'; MAX_FIRMLINK_TARGET];
let mut list = b"/d\t".to_vec();
list.extend_from_slice(&target);
list.push(b'\n');
let links = Firmlinks::parse(&list).expect("a list");
let mut entries = vec![SourceEntry::new("/d", EntryKind::Directory, meta(0o755))];
assert_eq!(mark(&mut entries, &links, true).expect("marked"), 1);
let model = model(entries, true).expect("a model");
let held: Vec<(&[u8], usize, u16)> = model.inodes[0]
.xattrs
.iter()
.filter_map(|x| match x {
ModelXattr::Embedded { name, value, flags } => {
Some((name.as_slice(), value.len(), *flags))
}
ModelXattr::Stream { .. } => None,
})
.collect();
assert_eq!(held, [(FIRMLINK_XATTR, MAX_FIRMLINK_TARGET + 1, 0x2)]);
}
#[test]
fn what_macos_would_not_keep_of_an_attribute_is_refused() {
let xattr = |name: &[u8]| Xattr {
name: name.to_vec(),
value: b"value".to_vec(),
};
for (path, kind) in [
("/c", EntryKind::CharDevice { major: 1, minor: 3 }),
("/b", EntryKind::BlockDevice { major: 1, minor: 4 }),
] {
let entry =
SourceEntry::new(path, kind, meta(0o644)).with_xattrs(vec![xattr(b"user.a")]);
let err = model(vec![entry], true).expect_err("refused");
assert!(
matches!(&err, ModelError::XattrOnDevice { path: p } if p == path.as_bytes()),
"{err:?}"
);
}
let entry = SourceEntry::new(
"/c",
EntryKind::CharDevice { major: 1, minor: 3 },
meta(0o644),
);
model(vec![entry], true).expect("a device node with no attribute");
let pipe = SourceEntry::new("/p", EntryKind::Fifo, meta(0o644))
.with_xattrs(vec![xattr(b"user.a")]);
model(vec![pipe], true).expect("a named pipe's attribute");
for name in [&b"user.\xff\xfe"[..], b"user.\xe9t\xe9"] {
let entry = SourceEntry::new("/f", EntryKind::File(b"f".to_vec().into()), meta(0o644))
.with_xattrs(vec![xattr(name)]);
let err = model(vec![entry], true).expect_err("refused");
assert!(
matches!(&err, ModelError::XattrNameNotUtf8 { name: n, .. } if n == name),
"{err:?}"
);
}
let entry = SourceEntry::new("/f", EntryKind::File(b"f".to_vec().into()), meta(0o644))
.with_xattrs(vec![xattr("user.caf\u{e9}".as_bytes())]);
model(vec![entry], true).expect("a UTF-8 name");
}
#[test]
fn an_attribute_named_twice_is_refused_whatever_its_values() {
let xattr = |name: &str, value: &str| Xattr {
name: name.into(),
value: value.into(),
};
for path in ["/f", "/"] {
let kind = || {
if path == "/" {
EntryKind::Directory
} else {
EntryKind::File(b"hello".to_vec().into())
}
};
for second in ["first", "second"] {
let entry = SourceEntry::new(path, kind(), meta(0o755)).with_xattrs(vec![
xattr("user.a", "first"),
xattr("user.b", "other"),
xattr("user.a", second),
]);
let err = model(vec![entry], true).expect_err("refused");
assert!(
matches!(&err, ModelError::XattrRepeated { path: p, name }
if p == path.as_bytes() && name == b"user.a"),
"{err:?}"
);
}
let entry = SourceEntry::new(path, kind(), meta(0o755))
.with_xattrs(vec![xattr("user.a", "first"), xattr("user.b", "first")]);
model(vec![entry], true).expect("two names");
}
}
fn header(method: u32, size: u64, tail: &[u8]) -> Vec<u8> {
let mut header = decmpfs::MAGIC.to_vec();
header.extend_from_slice(&method.to_le_bytes());
header.extend_from_slice(&size.to_le_bytes());
header.extend_from_slice(tail);
header
}
#[test]
fn a_compressed_form_contradicting_its_file_is_refused_by_what_it_contradicts() {
let held = 70_000u64;
let fork = Some(vec![0; 16]);
let cases: [(CompressedFile, u64, Option<CompressedFault>); 9] = [
(
CompressedFile::new(header(10, held, &[]), fork.clone()),
held,
None,
),
(
CompressedFile::new(header(9, 3, &[0xCC, 1, 2, 3]), None),
3,
None,
),
(
CompressedFile::new(b"fpmc".to_vec(), None),
3,
Some(CompressedFault::NotAHeader),
),
(
CompressedFile::new(header(9, 3, &[]).into_iter().rev().collect(), None),
3,
Some(CompressedFault::NotAHeader),
),
(
CompressedFile::new(header(5, 3, &[]), None),
3,
Some(CompressedFault::UnknownType(5)),
),
(
CompressedFile::new(header(10, held - 1, &[]), fork.clone()),
held,
Some(CompressedFault::LengthDiffers {
declared: held - 1,
held,
}),
),
(
CompressedFile::new(header(10, held, &[]), None),
held,
Some(CompressedFault::ForkMissing(10)),
),
(
CompressedFile::new(header(9, 3, &[0xCC, 1, 2, 3]), fork),
3,
Some(CompressedFault::ForkGiven(9)),
),
(
CompressedFile::new(header(9, held, &[]), None),
held,
Some(CompressedFault::InlineTooLarge(held)),
),
];
for (form, len, want) in cases {
assert_eq!(compressed_fault(&form, len), want, "{form:?}");
let content = FileContent::from(vec![0u8; len as usize]);
let entry = SourceEntry::new("/f", EntryKind::File(content), meta(0o644))
.with_darwin(Darwin::new(0).compressed(form));
match (model(vec![entry], true), want) {
(Ok(_), None) => {}
(Err(ModelError::CompressedForm { fault, .. }), Some(want)) => {
assert_eq!(fault, want)
}
(other, want) => panic!("{want:?}: {other:?}"),
}
}
let at = (decmpfs::MAX_INLINE - 16) as usize;
let form = |n: usize| CompressedFile::new(header(9, n as u64 - 1, &vec![0xCC; n]), None);
assert_eq!(compressed_fault(&form(at), at as u64 - 1), None);
assert_eq!(
compressed_fault(&form(at + 1), at as u64),
Some(CompressedFault::AttributeTooLong(decmpfs::MAX_INLINE + 1))
);
}
}