use std::io::{Read, Seek};
use std::sync::Arc;
use crate::cache::BlockCache;
use crate::io::{Bounded, io_error, offset_of, read_exact_at};
use crate::{Limits, OpenOptions, ReadPolicy};
use super::btree::{self, TreeRoot};
use super::geometry::{ChunkGeometry, QueueNodeLimits};
use super::ondisk::{
CHECKPOINT_AREA_IS_TREE, COUNTERS, CRYPTO_GENERATION, CheckpointMap, CheckpointMapping,
ContainerSuperblock, MAP_CRYPTO_CHANGING, MAX_BLOCK_SIZE, MIN_BLOCK_SIZE, MapKey, MapValue,
NodeFault, ObjectHeader, ObjectMap, ParseError, SpaceManager, Storage, VolumeSuperblock,
container_incompat, kind, verify, volume_incompat,
};
pub const SUPPORTED_CONTAINER_INCOMPAT: u64 = container_incompat::VERSION2;
pub const SUPPORTED_VOLUME_INCOMPAT: u64 = volume_incompat::CASE_INSENSITIVE
| volume_incompat::NORMALIZATION_INSENSITIVE
| volume_incompat::ENCRYPTION_ROLLED;
pub(crate) type Object = Arc<[u8]>;
const OBJECT_CACHE_BYTES: usize = 1 << 20;
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct VolumeEntry {
pub slot: usize,
pub oid: u64,
pub address: u64,
pub superblock: VolumeSuperblock,
}
impl VolumeEntry {
#[must_use]
pub fn name(&self) -> &[u8] {
self.superblock.name_bytes()
}
#[must_use]
pub fn refusal(&self) -> Option<ReadError> {
let sb = &self.superblock;
if !sb.is_unencrypted() {
return Some(ReadError::Encrypted { slot: self.slot });
}
if sb.encryption_rolling_oid != 0 {
return Some(ReadError::EncryptionChanging { slot: self.slot });
}
if sb.revert_to_xid != 0 || sb.revert_to_superblock != 0 {
return Some(ReadError::RevertPending { slot: self.slot });
}
let unknown = sb.incompatible_features & !SUPPORTED_VOLUME_INCOMPAT;
if unknown != 0 {
return Some(ReadError::UnsupportedFeatures {
scope: "volume",
bits: unknown,
names: volume_incompat_names(unknown),
});
}
if sb.incompatible_features
& (volume_incompat::CASE_INSENSITIVE | volume_incompat::NORMALIZATION_INSENSITIVE)
== 0
{
return Some(ReadError::UnhashedNames { slot: self.slot });
}
None
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct UnreadableVolume {
pub slot: usize,
pub oid: u64,
pub error: ReadError,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Expect {
pub(crate) kinds: &'static [u16],
pub(crate) subtype: Option<u16>,
pub(crate) storage: Storage,
pub(crate) oid: u64,
pub(crate) xid: Xid,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Xid {
AtMost(u64),
Exactly(u64),
}
pub struct Container<R> {
src: Bounded<R>,
base: u64,
superblock: Box<ContainerSuperblock>,
checkpoint_address: u64,
object_map: ObjectMap,
volumes: Vec<VolumeEntry>,
unreadable: Vec<UnreadableVolume>,
passed_over: Vec<PassedOver>,
block_zero: BlockZero,
policy: ReadPolicy,
limits: Limits,
cache: BlockCache<Object>,
ephemeral: Option<Arc<[CheckpointMapping]>>,
ephemeral_by_oid: Option<Arc<[(u64, u64)]>>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PassedOver {
pub address: u64,
pub xid: u64,
pub reason: &'static str,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum BlockZero {
Current,
Older {
xid: u64,
},
Differs {
bytes: usize,
offset: usize,
field: &'static str,
},
Newer {
xid: u64,
},
NotLoaded {
xid: u64,
},
Unverified,
}
impl BlockZero {
#[must_use]
pub const fn disagrees(self) -> bool {
matches!(
self,
BlockZero::Differs { .. } | BlockZero::Newer { .. } | BlockZero::Unverified
)
}
}
impl std::fmt::Display for BlockZero {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BlockZero::Current => write!(f, "block zero holds the live superblock"),
BlockZero::Older { xid } => {
write!(f, "block zero holds the superblock of transaction {xid}")
}
BlockZero::Differs {
bytes,
offset,
field,
} => write!(
f,
"block zero holds the live transaction and differs from the live superblock in \
{bytes} byte{}, the first at offset {offset} ({field})",
if *bytes == 1 { "" } else { "s" }
),
BlockZero::Newer { xid } => write!(
f,
"block zero holds transaction {xid}, which no whole checkpoint in the \
descriptor area holds"
),
BlockZero::NotLoaded { xid } => write!(
f,
"block zero holds transaction {xid}, whose checkpoint macOS does not load"
),
BlockZero::Unverified => write!(f, "block zero's checksum does not cover it"),
}
}
}
pub(crate) const SAME_TRANSACTION: &str = "another whole checkpoint records the same transaction";
const UNDEFINED: &str = "which the format does not define";
pub(crate) const FOREIGN: &str = "it belongs to another container than block zero";
pub(crate) const QUEUE_LIMITS: &str =
"its space manager gives a free queue another node limit than a container of its size has";
const MAX_EPHEMERAL_BYTES: u64 = 16 << 20;
pub(crate) const MAX_DESCRIPTOR_BYTES: u64 = 16 << 20;
fn read_block_zero<R: Read + Seek>(
src: &mut R,
base: u64,
) -> Result<(ContainerSuperblock, Vec<u8>), ReadError> {
let short = |e: std::io::Error| {
if e.kind() == std::io::ErrorKind::UnexpectedEof {
ReadError::NotApfs
} else {
ReadError::from(e)
}
};
let head = read_exact_at(src, base, MIN_BLOCK_SIZE as usize).map_err(short)?;
let first = ContainerSuperblock::read_from(&head).map_err(|_| ReadError::NotApfs)?;
let block_size = first.block_size;
if !block_size.is_power_of_two() || !(MIN_BLOCK_SIZE..=MAX_BLOCK_SIZE).contains(&block_size) {
return Err(ReadError::BadGeometry {
field: "block size",
value: u64::from(block_size),
why: UNDEFINED,
});
}
let bytes = if block_size == MIN_BLOCK_SIZE {
head
} else {
read_exact_at(src, base, block_size as usize).map_err(short)?
};
Ok((first, bytes))
}
pub(crate) fn is_container<R: Read + Seek>(mut src: R, base: u64) -> Result<bool, ReadError> {
let (first, block_zero) = match read_block_zero(&mut src, base) {
Ok(found) => found,
Err(ReadError::Io { kind, message }) => return Err(ReadError::Io { kind, message }),
Err(_) => return Ok(false),
};
if verify(&block_zero) {
return Ok(true);
}
let options = OpenOptions::new().policy(ReadPolicy::Lenient);
let mut container = Container::unread(Bounded::new(src, base, None), base, first, &options);
match container.find_checkpoint() {
Ok(_) => Ok(true),
Err(ReadError::Io {
kind: std::io::ErrorKind::UnexpectedEof,
..
}) => Ok(false),
Err(ReadError::Io { kind, message }) => Err(ReadError::Io { kind, message }),
Err(_) => Ok(false),
}
}
const COUNTERS_AT: std::ops::Range<usize> = 984..984 + 8 * COUNTERS;
const SUPERBLOCK_FIELDS: &[(usize, &str)] = &[
(0, "the check words"),
(8, "the object identifier"),
(16, "the transaction"),
(24, "the object type"),
(32, "the signature"),
(36, "the block size"),
(40, "the block count"),
(48, "the compatible features"),
(56, "the read-only compatible features"),
(64, "the incompatible features"),
(72, "the container identifier"),
(88, "the next object identifier"),
(96, "the next transaction"),
(104, "the checkpoint areas"),
(152, "the space manager"),
(160, "the object map"),
(168, "the reaper"),
(176, "the test type"),
(180, "the maximum volume count"),
(184, "the volume list"),
(COUNTERS_AT.start, "the counters"),
(COUNTERS_AT.end, "the blocked-out range"),
(1256, "the eviction mapping tree"),
(1264, "the container flags"),
(1272, "the boot driver"),
(1280, "the Fusion identifier"),
(1296, "the keybag"),
(1312, "the ephemeral information"),
(1344, "the test object"),
(1352, "the Fusion middle tree"),
(1360, "the Fusion cache state"),
(1368, "the Fusion cache"),
(1384, "the newest mounted version"),
(1392, "the media keybag"),
(ContainerSuperblock::SIZE, "the rest of the block"),
];
fn superblock_field(offset: usize) -> &'static str {
SUPERBLOCK_FIELDS
.iter()
.take_while(|(start, _)| *start <= offset)
.last()
.map_or("the check words", |(_, name)| name)
}
fn compare_block_zero(block_zero: &[u8], live: &[u8]) -> BlockZero {
let xid = |b: &[u8]| ObjectHeader::read_from(b).map_or(0, |h| h.xid);
let (zero, current) = (xid(block_zero), xid(live));
if zero < current {
return BlockZero::Older { xid: zero };
}
if zero > current {
return BlockZero::Newer { xid: zero };
}
let mut differing = (8..block_zero.len().min(live.len()))
.filter(|at| !COUNTERS_AT.contains(at) && block_zero[*at] != live[*at]);
let Some(offset) = differing.next() else {
return BlockZero::Current;
};
BlockZero::Differs {
bytes: 1 + differing.count(),
offset,
field: superblock_field(offset),
}
}
impl<R: Read + Seek> Container<R> {
pub fn open(src: R) -> Result<Self, ReadError> {
Self::open_with(src, &OpenOptions::new())
}
pub fn open_with(src: R, options: &OpenOptions) -> Result<Self, ReadError> {
let base = options.base;
let mut src = Bounded::new(src, base, options.len);
let (first, block_zero) = read_block_zero(&mut src, base)?;
if !verify(&block_zero) && options.policy == ReadPolicy::Strict {
return Err(ReadError::BadChecksum {
object: "container superblock",
block: 0,
});
}
let mut container = Self::unread(src, base, first, options);
let live = container.find_checkpoint()?;
container.check_live()?;
if verify(&block_zero) {
container.block_zero = compare_block_zero(&block_zero, &live);
if let BlockZero::Newer { xid } = container.block_zero
&& container
.passed_over
.iter()
.any(|passed| passed.xid == xid && passed.reason == QUEUE_LIMITS)
{
container.block_zero = BlockZero::NotLoaded { xid };
}
}
if container.block_zero.disagrees() && options.policy == ReadPolicy::Strict {
return Err(ReadError::BlockZeroDisagrees {
block_zero: container.block_zero,
live: container.xid(),
});
}
container.read_object_map()?;
container.read_volumes()?;
Ok(container)
}
fn unread(
src: Bounded<R>,
base: u64,
first: ContainerSuperblock,
options: &OpenOptions,
) -> Self {
let block_size = first.block_size as usize;
Self {
src,
base,
superblock: Box::new(first),
checkpoint_address: 0,
object_map: empty_map(),
volumes: Vec::new(),
unreadable: Vec::new(),
passed_over: Vec::new(),
block_zero: BlockZero::Unverified,
policy: options.policy,
limits: options.limits,
cache: BlockCache::within(OBJECT_CACHE_BYTES, block_size, 64),
ephemeral: None,
ephemeral_by_oid: None,
}
}
#[must_use]
pub fn superblock(&self) -> &ContainerSuperblock {
&self.superblock
}
#[must_use]
pub fn checkpoint_address(&self) -> u64 {
self.checkpoint_address
}
#[must_use]
pub fn xid(&self) -> u64 {
self.superblock.header.xid
}
#[must_use]
pub fn block_size(&self) -> u32 {
self.superblock.block_size
}
#[must_use]
pub fn volumes(&self) -> &[VolumeEntry] {
&self.volumes
}
#[must_use]
pub fn unreadable_volumes(&self) -> &[UnreadableVolume] {
&self.unreadable
}
#[must_use]
pub fn passed_over(&self) -> &[PassedOver] {
&self.passed_over
}
#[must_use]
pub fn block_zero(&self) -> BlockZero {
self.block_zero
}
#[must_use]
pub fn policy(&self) -> ReadPolicy {
self.policy
}
pub(crate) fn source_bytes(&mut self) -> Result<u64, ReadError> {
let end = self.src.seek(std::io::SeekFrom::End(0))?;
Ok(end.saturating_sub(self.base))
}
pub(crate) fn set_policy(&mut self, policy: ReadPolicy) {
self.policy = policy;
}
#[must_use]
pub fn limits(&self) -> Limits {
self.limits
}
pub fn read_blocks(&mut self, block: u64, buf: &mut [u8]) -> Result<(), ReadError> {
self.read_within(block, 0, buf)
}
pub(crate) fn read_within(
&mut self,
block: u64,
skip: u64,
buf: &mut [u8],
) -> Result<(), ReadError> {
let bs = u64::from(self.block_size());
let blocks = (skip + buf.len() as u64).div_ceil(bs);
if block
.checked_add(blocks)
.is_none_or(|end| end > self.superblock.block_count)
{
return Err(ReadError::OutOfRange { block });
}
let offset = offset_of(self.base, block, bs)
.and_then(|at| at.checked_add(skip))
.ok_or(ReadError::OutOfRange { block })?;
crate::io::read_exact_into(&mut self.src, offset, buf)?;
Ok(())
}
pub(crate) fn read_object(
&mut self,
address: u64,
expect: &Expect,
) -> Result<Object, ReadError> {
let object = match self.cache.get(address) {
Some(held) => Arc::clone(held),
None => {
let mut bytes = vec![0u8; self.block_size() as usize];
self.read_blocks(address, &mut bytes)?;
if !verify(&bytes) {
return Err(ReadError::BadChecksum {
object: object_name(expect.kinds),
block: address,
});
}
let object: Object = bytes.into();
self.cache.insert(address, Arc::clone(&object));
object
}
};
let header = ObjectHeader::read_from(&object)?;
let fault = if !expect.kinds.contains(&header.kind()) {
Some("an object of another type")
} else if expect
.subtype
.is_some_and(|subtype| header.subtype != u32::from(subtype))
{
Some("an object of another subtype")
} else if header.storage() != expect.storage {
Some("an object stored another way")
} else if header.oid != expect.oid {
Some("an object recording another identifier")
} else if header.xid == 0
|| match expect.xid {
Xid::AtMost(xid) => header.xid > xid,
Xid::Exactly(xid) => header.xid != xid,
}
{
Some("an object from another transaction")
} else if header.other_flags() != 0 {
Some("an object carrying flags this crate does not read")
} else {
None
};
if let Some(fault) = fault {
return Err(ReadError::WrongObject {
block: address,
fault,
});
}
Ok(object)
}
pub(crate) fn resolve(
&mut self,
map: &TreeRoot,
oid: u64,
xid: u64,
) -> Result<(MapKey, MapValue), ReadError> {
let target = MapKey { oid, xid };
let found = btree::find_at_or_before(self, map, &|key: &[u8]| {
MapKey::read_from(key).map(|k| k.cmp(&target))
})?;
let Some((key, value)) = found else {
return Err(ReadError::MissingObject { oid, xid });
};
let key = MapKey::read_from(&key)?;
if key.oid != oid {
return Err(ReadError::MissingObject { oid, xid });
}
let value = MapValue::read_from(&value)?;
if value.flags & !CRYPTO_GENERATION != 0 {
return Err(ReadError::BadMapValue {
oid,
flags: value.flags,
});
}
if value.size != self.block_size() {
return Err(ReadError::BadGeometry {
field: "a mapped object's size",
value: u64::from(value.size),
why: "an object of more than a block, which this crate does not read",
});
}
Ok((key, value))
}
pub(crate) fn read_virtual(
&mut self,
map: &TreeRoot,
oid: u64,
xid: u64,
kinds: &'static [u16],
subtype: Option<u16>,
) -> Result<(u64, Object), ReadError> {
let (key, value) = self.resolve(map, oid, xid)?;
let object = self.read_object(
value.address,
&Expect {
kinds,
subtype,
storage: Storage::Virtual,
oid,
xid: Xid::Exactly(key.xid),
},
)?;
Ok((value.address, object))
}
pub(crate) fn object_map_at(
&mut self,
address: u64,
xid: u64,
) -> Result<(ObjectMap, TreeRoot), ReadError> {
let object = self.read_object(
address,
&Expect {
kinds: &[kind::OBJECT_MAP],
subtype: None,
storage: Storage::Physical,
oid: address,
xid: Xid::AtMost(xid),
},
)?;
let map = ObjectMap::read_from(&object)?;
let tree = TreeRoot::object_map(map.tree_oid, map.header.xid);
Ok((map, tree))
}
pub(crate) fn checkpoint_mappings(&mut self) -> Result<Arc<[CheckpointMapping]>, ReadError> {
if let Some(held) = &self.ephemeral {
return Ok(Arc::clone(held));
}
let mappings: Vec<CheckpointMapping> = self
.checkpoint_maps()?
.into_iter()
.flat_map(|(_, _, mappings)| mappings)
.collect();
let held: Arc<[CheckpointMapping]> = mappings.into();
self.ephemeral = Some(Arc::clone(&held));
Ok(held)
}
pub(crate) fn checkpoint_maps(
&mut self,
) -> Result<Vec<(u64, CheckpointMap, Vec<CheckpointMapping>)>, ReadError> {
let areas = self.superblock.checkpoint;
let ring = u64::from(self.superblock.desc_area_blocks());
let mut maps = Vec::new();
let mut block = vec![0u8; self.block_size() as usize];
for k in 0..u64::from(areas.desc_len.saturating_sub(1)) {
let address = areas.desc_base + (u64::from(areas.desc_index) + k) % ring;
self.read_blocks(address, &mut block)?;
let (map, mappings) = CheckpointMap::read_from(&block)?;
maps.push((address, map, mappings));
}
Ok(maps)
}
pub(crate) fn ephemeral_address(&mut self, oid: u64) -> Result<u64, ReadError> {
let xid = self.xid();
let index = match &self.ephemeral_by_oid {
Some(index) => Arc::clone(index),
None => {
let mut index: Vec<(u64, u64)> = self
.checkpoint_mappings()?
.iter()
.map(|mapping| (mapping.oid, mapping.address))
.collect();
index.sort_unstable();
let index: Arc<[(u64, u64)]> = index.into();
self.ephemeral_by_oid = Some(Arc::clone(&index));
index
}
};
let at = index.partition_point(|&(named, _)| named < oid);
let mut naming = index[at..].iter().take_while(|&&(named, _)| named == oid);
let &(_, first) = naming.next().ok_or(ReadError::MissingObject { oid, xid })?;
if let Some(&(_, second)) = naming.next() {
return Err(ReadError::WrongObject {
block: second,
fault: "an identifier another mapping of the checkpoint names",
});
}
Ok(first)
}
pub(crate) fn space_manager(&mut self) -> Result<SpaceManager, ReadError> {
let xid = self.xid();
let oid = self.superblock.space_manager_oid;
let mappings = self.checkpoint_mappings()?;
let mapping = mappings
.iter()
.find(|mapping| mapping.oid == oid)
.copied()
.ok_or(ReadError::MissingObject { oid, xid })?;
let object = self.read_ephemeral(&mapping, kind::SPACE_MANAGER, xid)?;
Ok(SpaceManager::read_from(&object)?)
}
pub(crate) fn read_ephemeral(
&mut self,
mapping: &CheckpointMapping,
kind: u16,
live: u64,
) -> Result<Vec<u8>, ReadError> {
let bs = u64::from(self.block_size());
let size = u64::from(mapping.size);
if size == 0 || size % bs != 0 || size > MAX_EPHEMERAL_BYTES {
return Err(ReadError::BadGeometry {
field: "an ephemeral object's size",
value: size,
why: "not whole blocks, or more than this crate reads",
});
}
let mut bytes = vec![0u8; bs as usize];
self.read_blocks(mapping.address, &mut bytes)?;
let header = ObjectHeader::read_from(&bytes)?;
if size > bs {
if header.oid != mapping.oid || header.type_word != mapping.type_word {
return Err(ReadError::WrongObject {
block: mapping.address,
fault: "an object of another type or identifier than its mapping says",
});
}
bytes.resize(size as usize, 0);
self.read_blocks(mapping.address + 1, &mut bytes[bs as usize..])?;
}
if !verify(&bytes) {
return Err(ReadError::BadChecksum {
object: "ephemeral object",
block: mapping.address,
});
}
let fault = if header.kind() != kind || header.type_word != mapping.type_word {
Some("an object of another type than its mapping says")
} else if header.storage() != Storage::Ephemeral {
Some("an object stored another way")
} else if header.oid != mapping.oid {
Some("an object recording another identifier")
} else if header.xid == 0 || header.xid > live {
Some("an object from another transaction")
} else {
None
};
match fault {
Some(fault) => Err(ReadError::WrongObject {
block: mapping.address,
fault,
}),
None => Ok(bytes),
}
}
fn space_manager_loads(
&mut self,
sb: &ContainerSuperblock,
managers: &[Vec<CheckpointMapping>],
) -> Result<(), &'static str> {
let ring = managers.len() as u64;
let c = &sb.checkpoint;
let found = (0..u64::from(c.desc_len.saturating_sub(1)))
.flat_map(|k| &managers[((u64::from(c.desc_index) + k) % ring) as usize])
.find(|mapping| mapping.oid == sb.space_manager_oid)
.copied();
let bs = u64::from(sb.block_size);
let size = ChunkGeometry::of(sb.block_count, sb.block_size)
.manager_layout()
.1
.div_ceil(bs)
.saturating_mul(bs);
let Some(mapping) = found.filter(|mapping| u64::from(mapping.size) == size) else {
return Ok(());
};
let Some(sm) = self
.read_ephemeral(&mapping, kind::SPACE_MANAGER, sb.header.xid)
.ok()
.and_then(|object| SpaceManager::read_from(&object).ok())
else {
return Ok(());
};
let given = QueueNodeLimits::of(sb.block_count, sb.block_size);
let recorded = (
sm.free_queues[SpaceManager::INTERNAL_POOL].tree_node_limit,
sm.free_queues[SpaceManager::MAIN_QUEUE].tree_node_limit,
);
if recorded == (given.pool, given.main) {
Ok(())
} else {
Err(QUEUE_LIMITS)
}
}
pub(crate) fn container_map(&self) -> TreeRoot {
TreeRoot::object_map(self.object_map.tree_oid, self.object_map.header.xid)
}
fn find_checkpoint(&mut self) -> Result<Vec<u8>, ReadError> {
let first = self.superblock.as_ref().clone();
let area = &first.checkpoint;
if (area.desc_blocks | area.data_blocks) & CHECKPOINT_AREA_IS_TREE != 0 {
return Err(ReadError::UnsupportedCheckpoint);
}
let ring = u64::from(first.desc_area_blocks());
let why = if ring == 0 {
Some(UNDEFINED)
} else if ring.saturating_mul(u64::from(first.block_size)) > MAX_DESCRIPTOR_BYTES {
Some("more than the 16 MiB of descriptor area this crate reads")
} else if area
.desc_base
.checked_add(ring)
.is_none_or(|end| end > first.block_count)
{
Some("which runs past the container's last block")
} else {
None
};
if let Some(why) = why {
return Err(ReadError::BadGeometry {
field: "the checkpoint descriptor area, in blocks,",
value: ring,
why,
});
}
let bs = self.block_size() as usize;
let mut slots: Vec<Option<Slot>> = Vec::with_capacity(ring as usize);
let mut managers: Vec<Vec<CheckpointMapping>> = Vec::with_capacity(ring as usize);
let mut candidates = Vec::new();
let mut bytes = vec![0u8; bs];
for i in 0..ring {
self.read_blocks(area.desc_base + i, &mut bytes)?;
let header = verify(&bytes)
.then(|| ObjectHeader::read_from(&bytes).ok())
.flatten();
slots.push(header.map(|h| Slot {
kind: h.kind(),
xid: h.xid,
mapping: written_as(&h, Storage::Physical, area.desc_base + i),
}));
managers.push(match header {
Some(h) if h.kind() == kind::CHECKPOINT_MAP => CheckpointMap::read_from(&bytes)
.map(|(_, mappings)| {
mappings
.into_iter()
.filter(|m| m.kind() == kind::SPACE_MANAGER)
.collect()
})
.unwrap_or_default(),
_ => Vec::new(),
});
if header.is_some_and(|h| h.kind() == kind::CONTAINER_SUPERBLOCK)
&& let Ok(sb) = ContainerSuperblock::read_from(&bytes)
{
candidates.push((sb.header.xid, i, sb, bytes.clone()));
}
}
candidates.sort_by_key(|candidate| std::cmp::Reverse(candidate.0));
let mut live: Option<(u64, u64, ContainerSuperblock, Vec<u8>)> = None;
for (xid, index, sb, bytes) in candidates {
if live.as_ref().is_some_and(|found| xid < found.0) {
break;
}
let whole = self
.checkpoint_is_whole(&sb, index, &slots)
.and_then(|()| self.space_manager_loads(&sb, &managers));
match (whole, &live) {
(Ok(()), None) => live = Some((xid, index, sb, bytes)),
(Ok(()), Some(_)) => self.passed_over.push(PassedOver {
address: area.desc_base + index,
xid,
reason: SAME_TRANSACTION,
}),
(Err(reason), None) => self.passed_over.push(PassedOver {
address: area.desc_base + index,
xid,
reason,
}),
(Err(_), Some(_)) => {}
}
}
let (_, index, sb, bytes) = live.ok_or(ReadError::NoCheckpoint)?;
self.checkpoint_address = area.desc_base + index;
*self.superblock = sb;
Ok(bytes)
}
fn checkpoint_is_whole(
&self,
sb: &ContainerSuperblock,
index: u64,
slots: &[Option<Slot>],
) -> Result<(), &'static str> {
let ring = slots.len() as u64;
let c = &sb.checkpoint;
let (start, len) = (u64::from(c.desc_index), u64::from(c.desc_len));
if !written_as(&sb.header, Storage::Ephemeral, OID_NX_SUPERBLOCK) {
return Err("it records another identity than a container superblock's");
}
if sb.uuid != self.superblock.uuid {
return Err(FOREIGN);
}
if sb.block_size != self.superblock.block_size
|| sb.checkpoint.desc_base != self.superblock.checkpoint.desc_base
|| sb.checkpoint.desc_blocks != self.superblock.checkpoint.desc_blocks
{
return Err("it describes another geometry than block zero");
}
if sb.checkpoint.data_blocks & CHECKPOINT_AREA_IS_TREE != 0 {
return Err("its data area is described by a tree, which this crate does not read");
}
if len == 0 || len > ring || start >= ring || (start + len - 1) % ring != index {
return Err("it is not the last block of the checkpoint it describes");
}
for k in 0..len - 1 {
match slots[((start + k) % ring) as usize] {
None => return Err("a checkpoint-mapping block of it does not verify"),
Some(slot) if slot.kind != kind::CHECKPOINT_MAP || slot.xid != sb.header.xid => {
return Err("a checkpoint-mapping block of it is from another transaction");
}
Some(slot) if !slot.mapping => {
return Err(
"a checkpoint-mapping block of it records another identity than its own",
);
}
Some(_) => {}
}
}
Ok(())
}
fn check_live(&self) -> Result<(), ReadError> {
let sb = &self.superblock;
let unknown = sb.incompatible_features & !SUPPORTED_CONTAINER_INCOMPAT;
if unknown != 0 {
return Err(ReadError::UnsupportedFeatures {
scope: "container",
bits: unknown,
names: container_incompat_names(unknown),
});
}
if sb.block_count == 0 {
return Err(ReadError::BadGeometry {
field: "block count",
value: 0,
why: UNDEFINED,
});
}
if sb.incompatible_features & container_incompat::VERSION2 == 0
&& self.policy == ReadPolicy::Strict
{
return Err(ReadError::BadGeometry {
field: "the container's format version",
value: 0,
why: UNDEFINED,
});
}
Ok(())
}
fn read_object_map(&mut self) -> Result<(), ReadError> {
let (map, tree) = self.object_map_at(self.superblock.object_map_oid, self.xid())?;
self.object_map = map;
self.check_map(&tree)
}
pub(crate) fn check_map(&mut self, tree: &TreeRoot) -> Result<(), ReadError> {
if self.policy == ReadPolicy::Strict {
btree::check_whole(self, tree)?;
}
Ok(())
}
fn read_volumes(&mut self) -> Result<(), ReadError> {
let slots: Vec<(usize, u64)> = self.superblock.volumes().collect();
for (slot, oid) in slots {
match self.read_volume(slot, oid) {
Ok(entry) => self.volumes.push(entry),
Err(ReadError::Io { kind, message }) => {
return Err(ReadError::Io { kind, message });
}
Err(error) => self.unreadable.push(UnreadableVolume { slot, oid, error }),
}
}
Ok(())
}
fn read_volume(&mut self, slot: usize, oid: u64) -> Result<VolumeEntry, ReadError> {
let map = self.container_map();
let xid = self.xid();
let (address, object) =
self.read_virtual(&map, oid, xid, &[kind::VOLUME_SUPERBLOCK], None)?;
let superblock = VolumeSuperblock::read_from(&object)?;
if superblock.index as usize != slot {
return Err(ReadError::WrongObject {
block: address,
fault: "a volume superblock recording another slot as its own",
});
}
Ok(VolumeEntry {
slot,
oid,
address,
superblock,
})
}
}
#[derive(Clone, Copy)]
struct Slot {
kind: u16,
xid: u64,
mapping: bool,
}
const OID_NX_SUPERBLOCK: u64 = 1;
fn written_as(header: &ObjectHeader, storage: Storage, oid: u64) -> bool {
header.storage() == storage
&& header.oid == oid
&& header.subtype == 0
&& header.other_flags() == 0
}
const fn empty_map() -> ObjectMap {
ObjectMap {
header: ObjectHeader {
checksum: 0,
oid: 0,
xid: 0,
type_word: 0,
subtype: 0,
},
flags: 0,
snapshot_count: 0,
tree_type: 0,
snapshot_tree_type: 0,
tree_oid: 0,
snapshot_tree_oid: 0,
most_recent_snapshot: 0,
pending_revert_min: 0,
pending_revert_max: 0,
}
}
fn object_name(kinds: &[u16]) -> &'static str {
match kinds.first().copied() {
Some(kind::CONTAINER_SUPERBLOCK) => "container superblock",
Some(kind::BTREE_ROOT | kind::BTREE_NODE) => "tree node",
Some(kind::OBJECT_MAP) => "object map",
Some(kind::VOLUME_SUPERBLOCK) => "volume superblock",
Some(kind::SNAPSHOT_EXTENSION) => "snapshot extension",
_ => "object",
}
}
fn container_incompat_names(bits: u64) -> String {
named_bits(
bits,
&[
(container_incompat::VERSION1, "the first format version"),
(container_incompat::VERSION2, "the second format version"),
(container_incompat::FUSION, "Fusion"),
],
)
}
fn volume_incompat_names(bits: u64) -> String {
named_bits(
bits,
&[
(volume_incompat::CASE_INSENSITIVE, "case-insensitive names"),
(volume_incompat::DATALESS_SNAPSHOTS, "dataless snapshots"),
(volume_incompat::ENCRYPTION_ROLLED, "rolled encryption keys"),
(
volume_incompat::NORMALIZATION_INSENSITIVE,
"normalization-insensitive names",
),
(volume_incompat::INCOMPLETE_RESTORE, "an incomplete restore"),
(volume_incompat::SEALED, "a sealed volume"),
],
)
}
fn named_bits(bits: u64, table: &[(u64, &str)]) -> String {
let mut out = Vec::new();
let mut rest = bits;
for (bit, name) in table {
if bits & bit != 0 {
out.push((*name).to_string());
rest &= !bit;
}
}
let mut bit = 1u64;
while rest != 0 {
if rest & bit != 0 {
out.push(format!("{bit:#x}"));
rest &= !bit;
}
bit = bit.wrapping_shl(1);
}
out.join(", ")
}
pub(crate) const fn map_is_changing_encryption(map: &ObjectMap) -> bool {
map.flags & MAP_CRYPTO_CHANGING != 0
}
pub(crate) const fn map_is_reverting(map: &ObjectMap) -> bool {
map.pending_revert_min != 0 || map.pending_revert_max != 0
}
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ReadError {
#[error("i/o error ({kind:?}): {message}")]
#[non_exhaustive]
Io {
kind: std::io::ErrorKind,
message: String,
},
#[error("no APFS container superblock at block zero")]
NotApfs,
#[error(transparent)]
Parse(#[from] ParseError),
#[error("{object} at block {block}: the checksum does not cover it")]
#[non_exhaustive]
BadChecksum {
object: &'static str,
block: u64,
},
#[error("{field} is {value}, {why}")]
#[non_exhaustive]
BadGeometry {
field: &'static str,
value: u64,
why: &'static str,
},
#[error("a checkpoint area described by a tree, which this crate does not read")]
UnsupportedCheckpoint,
#[error("no whole checkpoint in the checkpoint descriptor area")]
NoCheckpoint,
#[error("{block_zero}; the live checkpoint is transaction {live}")]
#[non_exhaustive]
BlockZeroDisagrees {
block_zero: BlockZero,
live: u64,
},
#[error("unsupported {scope} features: {names} ({bits:#x})")]
#[non_exhaustive]
UnsupportedFeatures {
scope: &'static str,
bits: u64,
names: String,
},
#[error("volume {slot} is encrypted")]
#[non_exhaustive]
Encrypted {
slot: usize,
},
#[error("volume {slot}'s encryption is being changed")]
#[non_exhaustive]
EncryptionChanging {
slot: usize,
},
#[error("volume {slot} has a revert pending, which discards the state it holds")]
#[non_exhaustive]
RevertPending {
slot: usize,
},
#[error("volume {slot} keys its directory entries by name without a hash")]
#[non_exhaustive]
UnhashedNames {
slot: usize,
},
#[error("block {block} is outside the container")]
#[non_exhaustive]
OutOfRange {
block: u64,
},
#[error("the object at block {block} is {fault}")]
#[non_exhaustive]
WrongObject {
block: u64,
fault: &'static str,
},
#[error("no version of object {oid} at or before transaction {xid}")]
#[non_exhaustive]
MissingObject {
oid: u64,
xid: u64,
},
#[error("object {oid}'s map record carries flags {flags:#x}")]
#[non_exhaustive]
BadMapValue {
oid: u64,
flags: u32,
},
#[error("the tree node at block {block}: {fault}")]
#[non_exhaustive]
BadNode {
block: u64,
fault: NodeFault,
},
#[error("the tree node at block {block}: {fault}")]
#[non_exhaustive]
BadTree {
block: u64,
fault: &'static str,
},
#[error("a walk reached the limit of {limit} records")]
#[non_exhaustive]
TooManyEntries {
limit: usize,
},
#[error("the container holds no volume {selector}")]
#[non_exhaustive]
NoSuchVolume {
selector: String,
},
#[error(
"the volumes in slots {} are each named {}, so the name names none of them",
.slots.iter().map(ToString::to_string).collect::<Vec<_>>().join(", "),
crate::escape::printable(.name)
)]
#[non_exhaustive]
AmbiguousVolume {
name: Vec<u8>,
slots: Vec<usize>,
},
#[error("the volume holds no snapshot {}", crate::escape::printable(.name))]
#[non_exhaustive]
NoSuchSnapshot {
name: Vec<u8>,
},
#[error("a record of object {id} (kind {kind}): {fault}")]
#[non_exhaustive]
BadRecord {
id: u64,
kind: u8,
fault: String,
},
#[error("the volume holds no inode {inode}")]
#[non_exhaustive]
MissingInode {
inode: u64,
},
#[error("no such path: {}", crate::escape::printable(.path))]
#[non_exhaustive]
NotFound {
path: Vec<u8>,
},
#[error("not a directory: {}", crate::escape::printable(.path))]
#[non_exhaustive]
NotADirectory {
path: Vec<u8>,
},
#[error("inode {inode} is not a symbolic link")]
#[non_exhaustive]
NotASymlink {
inode: u64,
},
#[error("too many symbolic links resolving {}", crate::escape::printable(.path))]
#[non_exhaustive]
SymlinkLoop {
path: Vec<u8>,
},
#[error("{} is not a name a directory can hold", crate::escape::printable(.name))]
#[non_exhaustive]
HostileName {
name: Vec<u8>,
},
#[error(
"a directory entry names directory inode {inode}, which the tree reaches by another \
name as well"
)]
#[non_exhaustive]
RepeatedDirectory {
inode: u64,
},
#[error(
"directory inode {inode} is named in directory inode {named_in} and records inode \
{parent} as its parent"
)]
#[non_exhaustive]
MisplacedDirectory {
inode: u64,
named_in: u64,
parent: u64,
},
#[error(
"inode {inode} is compressed with decmpfs type {method}, which this build does not \
decode{}",
crate::compress::CompiledBy(
crate::apfs::decmpfs::layout(*.method).and_then(|(_, encoding)| encoding.algorithm())
)
)]
#[non_exhaustive]
UnsupportedCompression {
inode: u64,
method: u32,
},
#[error("inode {inode}'s compressed data: {fault}")]
#[non_exhaustive]
BadCompressed {
inode: u64,
fault: String,
},
#[error("the extent at byte {logical} of stream {stream}: {fault}")]
#[non_exhaustive]
BadExtent {
stream: u64,
logical: u64,
block: Option<u64>,
fault: &'static str,
},
#[error("inode {inode} is {size} bytes, more than the {limit}-byte cap this read is held to")]
#[non_exhaustive]
FileTooLarge {
inode: u64,
size: u64,
limit: u64,
},
#[error(
"attribute {} of inode {inode} is {size} bytes, more than the {limit}-byte cap this read \
is held to",
crate::escape::printable(name)
)]
#[non_exhaustive]
AttributeTooLarge {
inode: u64,
name: Vec<u8>,
size: u64,
limit: u64,
},
#[error("a walk of this volume reached the limit of {limit} names")]
#[non_exhaustive]
WalkTooLarge {
limit: usize,
},
#[error("a path longer than this crate builds: {}", crate::escape::printable(.path))]
#[non_exhaustive]
PathTooLong {
path: Vec<u8>,
},
}
io_error!(ReadError);
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_refused_compression_names_the_feature_that_decodes_it() {
let refused = ReadError::UnsupportedCompression {
inode: 18,
method: 11,
};
assert_eq!(
refused.to_string(),
"inode 18 is compressed with decmpfs type 11, which this build does not decode; the \
`lzfse` feature compiles its decoder"
);
let undefined = ReadError::UnsupportedCompression {
inode: 18,
method: 0x7f,
};
assert_eq!(
undefined.to_string(),
"inode 18 is compressed with decmpfs type 127, which this build does not decode"
);
}
#[test]
fn unnamed_bits_are_named_by_their_value() {
assert_eq!(
container_incompat_names(container_incompat::FUSION | 0x40),
"Fusion, 0x40"
);
assert_eq!(
volume_incompat_names(volume_incompat::SEALED),
"a sealed volume"
);
}
#[test]
fn a_source_too_short_for_a_superblock_is_not_a_container() {
let err = Container::open(std::io::Cursor::new(vec![0u8; 100]));
assert!(matches!(err, Err(ReadError::NotApfs)));
}
#[test]
fn zeros_are_not_a_container() {
let err = Container::open(std::io::Cursor::new(vec![0u8; 8192]));
assert!(matches!(err, Err(ReadError::NotApfs)));
}
}