use std::cmp::Ordering;
use std::collections::HashSet;
use std::io::{Read, Seek};
use super::container::{Container, Expect, Object, ReadError, Xid};
use super::ondisk::{
EntryKey, EntrySizes, FileExtent, FreeQueueKey, KeyHeader, MapKey, Node, NodeHeader,
ObjectHeader, ParseError, Storage, TREE_ALLOW_GHOSTS, TREE_EPHEMERAL, TREE_HASHED,
TREE_KV_NONALIGNED, TREE_NO_HEADER, TREE_PHYSICAL, TREE_SEQUENTIAL_INSERT, TreeInfo, Unused,
child_oid, key_u64, kind, node_flags, record_kind, xattr_name,
};
pub const MAX_LEVEL: u16 = 63;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Children {
Physical,
Ephemeral,
Virtual {
map_tree: u64,
map_xid: u64,
xid: u64,
},
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Order {
ObjectMap,
FileSystem,
FreeQueue,
Transaction,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct TreeRoot {
pub oid: u64,
pub children: Children,
pub subtype: u16,
pub order: Order,
pub max_xid: u64,
}
impl TreeRoot {
pub(crate) const fn object_map(oid: u64, max_xid: u64) -> Self {
TreeRoot {
oid,
children: Children::Physical,
subtype: kind::OBJECT_MAP,
order: Order::ObjectMap,
max_xid,
}
}
fn map(&self) -> Option<(TreeRoot, u64)> {
match self.children {
Children::Physical | Children::Ephemeral => None,
Children::Virtual {
map_tree,
map_xid,
xid,
} => Some((TreeRoot::object_map(map_tree, map_xid), xid)),
}
}
}
pub(crate) type Target<'t> = &'t dyn Fn(&[u8]) -> Result<Ordering, ParseError>;
pub(crate) type Record = (Vec<u8>, Vec<u8>);
pub(crate) type Visit<'v> = dyn FnMut(&[u8], &[u8]) -> Result<bool, ReadError> + 'v;
struct Frame {
object: Object,
block: u64,
sizes: EntrySizes,
level: u16,
next: u32,
bound: Option<Vec<u8>>,
unused: Unused,
}
impl Frame {
fn node(&self) -> Result<Node<'_>, ReadError> {
Node::frame(&self.object, self.sizes).map_err(|fault| ReadError::BadNode {
block: self.block,
fault,
})
}
}
fn read_root<R: Read + Seek>(
container: &mut Container<R>,
root: &TreeRoot,
) -> Result<Frame, ReadError> {
let (block, object) = read_node(container, root, root.oid, true, root.max_xid)?;
let header = NodeHeader::read_from(&object)?;
if !header.is_root() {
return Err(ReadError::BadTree {
block,
fault: "a root without its tree information",
});
}
let info = TreeInfo::read_from(&object[object.len() - TreeInfo::SIZE..])?;
check_info(block, &info, container.block_size(), root)?;
if header.level > MAX_LEVEL {
return Err(ReadError::BadTree {
block,
fault: "a root higher than any tree the container could hold",
});
}
let mut frame = Frame {
object,
block,
sizes: EntrySizes {
key: info.key_size,
value: info.value_size,
},
level: header.level,
next: 0,
bound: None,
unused: Unused::default(),
};
frame.unused = check_node(&frame.node()?, block, root.order, true)?;
Ok(frame)
}
const READ_FLAGS: u32 = TREE_SEQUENTIAL_INSERT
| TREE_ALLOW_GHOSTS
| TREE_KV_NONALIGNED
| TREE_PHYSICAL
| TREE_EPHEMERAL;
fn check_info(
block: u64,
info: &TreeInfo,
block_size: u32,
tree: &TreeRoot,
) -> Result<(), ReadError> {
if info.flags & (TREE_HASHED | TREE_NO_HEADER) != 0 {
return Err(ReadError::BadTree {
block,
fault: "a tree whose nodes are hashed or headerless",
});
}
if info.flags & !READ_FLAGS != 0 {
return Err(ReadError::BadTree {
block,
fault: "a tree flagged as keyed by 64-bit integers, as not persisted, or with a bit \
the format does not define",
});
}
if (info.flags & TREE_PHYSICAL != 0) != matches!(tree.children, Children::Physical)
|| (info.flags & TREE_EPHEMERAL != 0) != matches!(tree.children, Children::Ephemeral)
{
return Err(ReadError::BadTree {
block,
fault: "a tree whose root says its children are found otherwise than they are",
});
}
if info.node_size != block_size {
return Err(ReadError::BadTree {
block,
fault: "a tree whose nodes are not one block",
});
}
Ok(())
}
fn read_node<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
oid: u64,
is_root: bool,
max_xid: u64,
) -> Result<(u64, Object), ReadError> {
let kinds: &'static [u16] = if is_root {
&[kind::BTREE_ROOT]
} else {
&[kind::BTREE_NODE]
};
let (address, storage) = match tree.children {
Children::Physical => (oid, Storage::Physical),
Children::Ephemeral => (container.ephemeral_address(oid)?, Storage::Ephemeral),
Children::Virtual { .. } => {
let (map, xid) = tree.map().expect("a virtual tree has a map");
return container.read_virtual(&map, oid, xid, kinds, Some(tree.subtype));
}
};
let object = container.read_object(
address,
&Expect {
kinds,
subtype: Some(tree.subtype),
storage,
oid,
xid: Xid::AtMost(max_xid),
},
)?;
Ok((address, object))
}
fn check_node(
node: &Node<'_>,
block: u64,
order: Order,
is_root: bool,
) -> Result<Unused, ReadError> {
let header = node.header();
if header.flags & !node_flags::UNDERSTOOD != 0 {
return Err(ReadError::BadTree {
block,
fault: "a node carrying flags this crate does not read",
});
}
if header.is_root() != is_root {
return Err(ReadError::BadTree {
block,
fault: "a node whose root flag disagrees with its place",
});
}
if header.is_leaf() != (header.level == 0) {
return Err(ReadError::BadTree {
block,
fault: "a node whose leaf flag disagrees with its level",
});
}
if node.is_empty() && !is_root {
return Err(ReadError::BadTree {
block,
fault: "a node other than the root holding nothing",
});
}
if node.is_empty() && header.level > 0 {
return Err(ReadError::BadTree {
block,
fault: "an index node holding nothing",
});
}
let unused = node
.check_layout()
.map_err(|fault| ReadError::BadNode { block, fault })?;
let mut previous: Option<&[u8]> = None;
for i in 0..node.len() {
let (key, value) = node
.entry(i)
.map_err(|fault| ReadError::BadNode { block, fault })?;
if value.is_none() && !(order == Order::FreeQueue && header.is_leaf()) {
return Err(ReadError::BadTree {
block,
fault: "a key without a value",
});
}
if let Some(previous) = previous
&& !in_order(order, previous, key, block)?
{
return Err(ReadError::BadTree {
block,
fault: "keys out of order",
});
}
if node.len() == 1 {
in_order(order, key, key, block)?;
}
previous = Some(key);
}
Ok(unused)
}
fn in_order(order: Order, a: &[u8], b: &[u8], block: u64) -> Result<bool, ReadError> {
let ordered = match order {
Order::ObjectMap => MapKey::read_from(a).and_then(|a| Ok(a < MapKey::read_from(b)?)),
Order::FileSystem => {
compare_records(a, b).map(|o| matches!(o, Some(Ordering::Less) | None))
}
Order::FreeQueue => {
FreeQueueKey::read_from(a).and_then(|a| Ok(a < FreeQueueKey::read_from(b)?))
}
Order::Transaction => key_u64(a, 0).and_then(|a| Ok(a < key_u64(b, 0)?)),
};
ordered.map_err(|_| ReadError::BadTree {
block,
fault: "a key that does not parse",
})
}
pub(crate) fn compare_records(a: &[u8], b: &[u8]) -> Result<Option<Ordering>, ParseError> {
let (ha, hb) = (KeyHeader::read_from(a)?, KeyHeader::read_from(b)?);
let first = (ha.id, ha.kind).cmp(&(hb.id, hb.kind));
if first != Ordering::Equal {
return Ok(Some(first));
}
let distinct = |a: &[u8], b: &[u8]| (a == b).then_some(Ordering::Equal);
Ok(match ha.kind {
record_kind::FILE_EXTENT => {
Some(FileExtentKey::logical(a)?.cmp(&FileExtentKey::logical(b)?))
}
record_kind::SIBLING_LINK => Some(key_u64(a, 8)?.cmp(&key_u64(b, 8)?)),
record_kind::XATTR => Some(xattr_name(a)?.cmp(xattr_name(b)?)),
record_kind::DIR_ENTRY => {
let (ea, eb) = (EntryKey::read_from(a)?, EntryKey::read_from(b)?);
Some(ea.hash.cmp(&eb.hash).then_with(|| ea.name.cmp(eb.name)))
}
record_kind::INODE
| record_kind::DATA_STREAM_ID
| record_kind::CRYPTO_STATE
| record_kind::DIR_STATS
| record_kind::SIBLING_MAP
| record_kind::SNAPSHOT_META
| record_kind::PHYSICAL_EXTENT => Some(Ordering::Equal),
_ => distinct(&a[8..], &b[8..]),
})
}
struct FileExtentKey;
impl FileExtentKey {
fn logical(key: &[u8]) -> Result<u64, ParseError> {
key_u64(key, 8)
}
}
fn descend<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
parent: &Frame,
index: u32,
seen: &mut HashSet<u64>,
) -> Result<Frame, ReadError> {
let node = parent.node()?;
let (separator, value) = node.entry(index).map_err(|fault| ReadError::BadNode {
block: parent.block,
fault,
})?;
let value = value.ok_or(ReadError::BadTree {
block: parent.block,
fault: "an index entry without a child",
})?;
let child = child_oid(value)?;
let bound = if index + 1 < node.len() {
let (next, _) = node.entry(index + 1).map_err(|fault| ReadError::BadNode {
block: parent.block,
fault,
})?;
Some(next.to_vec())
} else {
parent.bound.clone()
};
let parent_xid = ObjectHeader::read_from(&parent.object)?.xid;
let (block, object) = read_node(container, tree, child, false, parent_xid)?;
if !seen.insert(block) {
return Err(ReadError::BadTree {
block,
fault: "a node reached twice",
});
}
let mut frame = Frame {
object,
block,
sizes: parent.sizes,
level: parent.level - 1,
next: 0,
bound,
unused: Unused::default(),
};
let framed = frame.node()?;
if framed.header().level != frame.level {
return Err(ReadError::BadTree {
block,
fault: "a node not one level below its parent",
});
}
let unused = check_node(&framed, block, tree.order, false)?;
let (first, _) = framed
.entry(0)
.map_err(|fault| ReadError::BadNode { block, fault })?;
if first != separator {
return Err(ReadError::BadTree {
block,
fault: "a node whose first key is not its parent's key for it",
});
}
if let Some(bound) = &frame.bound {
let (last, _) = framed
.entry(framed.len() - 1)
.map_err(|fault| ReadError::BadNode { block, fault })?;
if !in_order(tree.order, last, bound, block)? || last == bound.as_slice() {
return Err(ReadError::BadTree {
block,
fault: "a node whose keys reach past its parent's key for the next node",
});
}
}
frame.unused = unused;
Ok(frame)
}
fn last_not_after(
node: &Node<'_>,
block: u64,
target: Target<'_>,
) -> Result<Option<u32>, ReadError> {
let after = first_where(node, block, &|key| Ok(target(key)? == Ordering::Greater))?;
Ok(after.checked_sub(1))
}
fn first_where(
node: &Node<'_>,
block: u64,
past: &dyn Fn(&[u8]) -> Result<bool, ParseError>,
) -> Result<u32, ReadError> {
let (mut lo, mut hi) = (0u32, node.len());
while lo < hi {
let mid = lo + (hi - lo) / 2;
let (key, _) = node
.entry(mid)
.map_err(|fault| ReadError::BadNode { block, fault })?;
if past(key)? {
hi = mid;
} else {
lo = mid + 1;
}
}
Ok(lo)
}
pub(crate) fn find_at_or_before<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
target: Target<'_>,
) -> Result<Option<Record>, ReadError> {
let mut seen = HashSet::new();
let mut frame = read_root(container, tree)?;
seen.insert(frame.block);
loop {
let index = {
let node = frame.node()?;
let found = last_not_after(&node, frame.block, target)?;
if frame.level > 0 {
found.unwrap_or(0)
} else {
let Some(index) = found else {
return Ok(None);
};
let (key, value) = node.entry(index).map_err(|fault| ReadError::BadNode {
block: frame.block,
fault,
})?;
let answer = (key.to_vec(), value.unwrap_or_default().to_vec());
if index + 1 == node.len() && frame.bound.is_some() {
confirm_last(container, tree, target)?;
}
return Ok(Some(answer));
}
};
frame = descend(container, tree, &frame, index, &mut seen)?;
}
}
fn confirm_last<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
target: Target<'_>,
) -> Result<(), ReadError> {
for_each_from(container, tree, target, usize::MAX, &mut |key, _| {
Ok(target(key)? != Ordering::Greater)
})?;
Ok(())
}
pub(crate) fn check_whole<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
) -> Result<(), ReadError> {
walk(
container,
tree,
&|_| Ok(Ordering::Greater),
usize::MAX,
&mut |_, _| Ok(true),
&mut |_, _| Ok(()),
)?;
Ok(())
}
pub(crate) fn for_each_from<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
target: Target<'_>,
limit: usize,
visit: &mut Visit<'_>,
) -> Result<Option<u64>, ReadError> {
walk(container, tree, target, limit, visit, &mut |_, _| Ok(()))
}
type Reached<'v> = dyn FnMut(&Frame, Unused) -> Result<(), ReadError> + 'v;
fn walk<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
target: Target<'_>,
limit: usize,
visit: &mut Visit<'_>,
reached: &mut Reached<'_>,
) -> Result<Option<u64>, ReadError> {
let mut visited = 0usize;
let mut seen = HashSet::new();
let root = read_root(container, tree)?;
seen.insert(root.block);
reached(&root, root.unused)?;
let mut stack = vec![root];
let mut steering = true;
while let Some(top) = stack.last() {
if top.level == 0 {
let node = top.node()?;
let mut i = top.next;
if steering {
i = first_where(&node, top.block, &|key| Ok(target(key)? != Ordering::Less))?;
steering = false;
}
while i < node.len() {
let (key, value) = node.entry(i).map_err(|fault| ReadError::BadNode {
block: top.block,
fault,
})?;
if !visit(key, value.unwrap_or_default())? {
return Ok(Some(top.block));
}
visited += 1;
if visited > limit {
return Err(ReadError::TooManyEntries { limit });
}
i += 1;
}
stack.pop();
continue;
}
let (index, len) = {
let node = top.node()?;
let index = if steering {
last_not_after(&node, top.block, target)?.unwrap_or(0)
} else {
top.next
};
(index, node.len())
};
if index >= len {
stack.pop();
continue;
}
let child = descend(container, tree, top, index, &mut seen)?;
reached(&child, child.unused)?;
if let Some(top) = stack.last_mut() {
top.next = index + 1;
}
stack.push(child);
}
Ok(None)
}
pub(crate) fn for_each<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
visit: &mut Visit<'_>,
) -> Result<(), ReadError> {
let limit = container.limits().max_walk_entries;
for_each_from(container, tree, &|_| Ok(Ordering::Greater), limit, visit)?;
Ok(())
}
#[derive(Clone, Debug)]
pub(crate) struct Census {
pub(crate) info: TreeInfo,
pub(crate) root: u64,
pub(crate) nodes: u64,
pub(crate) records: u64,
pub(crate) longest: (usize, usize),
pub(crate) free_lists: Vec<(u64, &'static str, u16, usize)>,
}
pub(crate) fn census<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
visit: &mut Visit<'_>,
) -> Result<Census, ReadError> {
census_nodes(container, tree, visit, &mut |_| {})
}
pub(crate) fn census_nodes<R: Read + Seek>(
container: &mut Container<R>,
tree: &TreeRoot,
visit: &mut Visit<'_>,
node: &mut dyn FnMut(u64),
) -> Result<Census, ReadError> {
let limit = container.limits().max_walk_entries;
let mut census = Census {
info: TreeInfo::default(),
root: 0,
nodes: 0,
records: 0,
longest: (0, 0),
free_lists: Vec::new(),
};
let tally = std::cell::RefCell::new(&mut census);
walk(
container,
tree,
&|_| Ok(Ordering::Greater),
limit,
&mut |key, value| {
let mut tally = tally.borrow_mut();
tally.records += 1;
tally.longest.0 = tally.longest.0.max(key.len());
tally.longest.1 = tally.longest.1.max(value.len());
drop(tally);
visit(key, value)
},
&mut |frame, unused| {
node(frame.block);
let node = frame.node()?;
let header = node.header();
let mut tally = tally.borrow_mut();
if let Some(info) = node.tree_info() {
tally.info = info;
tally.root = frame.block;
}
tally.nodes += 1;
for (area, (_, said), held) in [
("key", header.key_free_list, unused.key),
("value", header.value_free_list, unused.value),
] {
if usize::from(said) != held {
tally.free_lists.push((frame.block, area, said, held));
}
}
Ok(())
},
)?;
Ok(census)
}
pub(crate) fn records_of(id: u64, kind: u8) -> impl Fn(&[u8]) -> Result<Ordering, ParseError> {
move |key: &[u8]| {
let header = KeyHeader::read_from(key)?;
Ok(match (header.id, header.kind).cmp(&(id, kind)) {
Ordering::Equal => Ordering::Greater,
other => other,
})
}
}
pub(crate) fn extent_at(
stream: u64,
logical: u64,
) -> impl Fn(&[u8]) -> Result<Ordering, ParseError> {
move |key: &[u8]| {
let header = KeyHeader::read_from(key)?;
let first = (header.id, header.kind).cmp(&(stream, record_kind::FILE_EXTENT));
if first != Ordering::Equal {
return Ok(first);
}
Ok(FileExtentKey::logical(key)?.cmp(&logical))
}
}
pub(crate) fn extent(key: &[u8], value: &[u8]) -> Result<FileExtent, ParseError> {
FileExtent::read_from(key, value)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::bytes::put_u64;
fn key(id: u64, kind: u8, tail: &[u8]) -> Vec<u8> {
let mut k = vec![0u8; 8];
KeyHeader { id, kind }.write_to(&mut k);
k.extend_from_slice(tail);
k
}
fn extent_key(id: u64, logical: u64) -> Vec<u8> {
let mut tail = [0u8; 8];
put_u64(&mut tail, 0, logical);
key(id, record_kind::FILE_EXTENT, &tail)
}
fn entry_key(dir: u64, hash: u32, name: &[u8]) -> Vec<u8> {
let mut tail = ((hash << 10) | (name.len() as u32 + 1))
.to_le_bytes()
.to_vec();
tail.extend_from_slice(name);
tail.push(0);
key(dir, record_kind::DIR_ENTRY, &tail)
}
fn named_key(id: u64, kind: u8, name: &[u8]) -> Vec<u8> {
let mut tail = (name.len() as u16 + 1).to_le_bytes().to_vec();
tail.extend_from_slice(name);
tail.push(0);
key(id, kind, &tail)
}
#[test]
fn records_order_by_identifier_kind_then_offset() {
let a = key(16, record_kind::INODE, &[]);
let b = entry_key(16, 7, b"zzz");
let c = key(17, record_kind::INODE, &[]);
assert_eq!(compare_records(&a, &b), Ok(Some(Ordering::Less)));
assert_eq!(compare_records(&b, &c), Ok(Some(Ordering::Less)));
assert_eq!(
compare_records(&extent_key(5, 8192), &extent_key(5, 4096)),
Ok(Some(Ordering::Greater))
);
}
#[test]
fn every_kind_holds_one_record_per_key_and_its_observed_order() {
let fs = |a: &[u8], b: &[u8]| in_order(Order::FileSystem, a, b, 0).expect("keys parse");
assert!(fs(&entry_key(2, 5, b"zz"), &entry_key(2, 6, b"aa")));
assert!(!fs(&entry_key(2, 6, b"aa"), &entry_key(2, 5, b"zz")));
assert!(fs(&entry_key(2, 5, b"a"), &entry_key(2, 5, b"b")));
assert!(!fs(&entry_key(2, 5, b"b"), &entry_key(2, 5, b"a")));
assert!(fs(&entry_key(2, 5, b"aaahapa"), &entry_key(2, 5, b"z610")));
assert!(fs(&entry_key(2, 5, b"Bpk99"), &entry_key(2, 5, b"aaaav")));
assert!(!fs(&entry_key(2, 5, b"a"), &entry_key(2, 5, b"a")));
let fork = named_key(16, record_kind::XATTR, b"com.apple.ResourceFork");
let header = named_key(16, record_kind::XATTR, b"com.apple.decmpfs");
assert!(fs(&fork, &header));
assert!(!fs(&header, &fork));
assert!(!fs(&header, &header));
let (one, two) = (
named_key(7, record_kind::SNAPSHOT_NAME, b"one"),
named_key(7, record_kind::SNAPSHOT_NAME, b"two"),
);
assert!(fs(&one, &two) && fs(&two, &one) && !fs(&one, &one));
assert!(!fs(&extent_key(5, 4096), &extent_key(5, 4096)));
let sibling = |n: u64| key(16, record_kind::SIBLING_LINK, &n.to_le_bytes());
assert!(fs(&sibling(255), &sibling(256)) && !fs(&sibling(256), &sibling(256)));
for kind in [
record_kind::INODE,
record_kind::DATA_STREAM_ID,
record_kind::DIR_STATS,
record_kind::PHYSICAL_EXTENT,
record_kind::SNAPSHOT_META,
] {
assert!(!fs(&key(16, kind, &[]), &key(16, kind, &[])), "kind {kind}");
}
assert!(fs(&key(16, 14, b"a"), &key(16, 14, b"b")));
assert!(!fs(&key(16, 14, b"a"), &key(16, 14, b"a")));
}
#[test]
fn a_target_for_one_objects_records_sorts_before_all_of_them() {
let target = records_of(16, record_kind::DIR_ENTRY);
assert_eq!(
target(&key(16, record_kind::INODE, &[])),
Ok(Ordering::Less)
);
assert_eq!(
target(&key(16, record_kind::DIR_ENTRY, b"x")),
Ok(Ordering::Greater)
);
assert_eq!(
target(&key(17, record_kind::INODE, &[])),
Ok(Ordering::Greater)
);
}
#[test]
fn an_extent_target_is_equal_to_its_own_offset_only() {
let target = extent_at(9, 4096);
assert_eq!(target(&extent_key(9, 0)), Ok(Ordering::Less));
assert_eq!(target(&extent_key(9, 4096)), Ok(Ordering::Equal));
assert_eq!(target(&extent_key(9, 8192)), Ok(Ordering::Greater));
assert_eq!(target(&extent_key(10, 0)), Ok(Ordering::Greater));
}
}