apfs_core/omap.rs
1//! Object map (`omap_phys_t`, type `OBJECT_TYPE_OMAP 0xb`) and virtual-oid
2//! resolution.
3//!
4//! A *virtual* object's oid is not its block address; it is resolved through an
5//! object map at a given transaction id. The omap header (Apple *APFS
6//! Reference*, `omap_phys_t`) points at a B-tree (`om_tree_oid`) whose keys are
7//! `omap_key_t { ok_oid, ok_xid }` (16 bytes) and whose values are
8//! `omap_val_t { ov_flags, ov_size, ov_paddr }` (16 bytes). Looking up
9//! `(virtual_oid, xid)` yields the physical block address of the object as of
10//! that transaction — the mechanism behind both live access and point-in-time
11//! snapshot views.
12//!
13//! `om_flags` (e.g. `OMAP_MANUALLY_MANAGED 0x1`, `OMAP_ENCRYPTING 0x2`,
14//! `OMAP_KEYROLLING 0x8`) describe snapshot/encryption state.
15//!
16//! Field offsets (Apple `omap_phys_t`, little-endian on disk), after the 32-byte
17//! `obj_phys_t om_o` header:
18//!
19//! | off | size | field |
20//! |-----|------|------------------------|
21//! | 32 | 4 | `om_flags` |
22//! | 36 | 4 | `om_snap_count` |
23//! | 40 | 4 | `om_tree_type` |
24//! | 44 | 4 | `om_snapshot_tree_type`|
25//! | 48 | 8 | `om_tree_oid` |
26//! | 56 | 8 | `om_snapshot_tree_oid` |
27//! | 64 | 8 | `om_most_recent_snap` |
28//! | 72 | 8 | `om_pending_revert_min`|
29//! | 80 | 8 | `om_pending_revert_max`|
30
31use crate::btree::{self, BTreeSubtype};
32use crate::object::{fletcher64_checksum, fletcher64_stored, ObjPhys};
33
34/// Object type code `OBJECT_TYPE_OMAP` (Apple): `o_type & 0xffff == 0xb`.
35const OBJECT_TYPE_OMAP: u16 = 0xb;
36
37// `omap_phys_t` field offsets after the 32-byte `obj_phys_t om_o` header.
38const OFF_OM_FLAGS: usize = 32;
39const OFF_OM_TREE_TYPE: usize = 40;
40const OFF_OM_TREE_OID: usize = 48;
41const OFF_OM_SNAPSHOT_TREE_OID: usize = 56;
42
43/// Minimum readable `omap_phys_t` length: header through `om_tree_oid`.
44const OMAP_PHYS_MIN_LEN: usize = OFF_OM_TREE_OID + 8;
45
46/// A resolved object-map entry (`omap_val_t` for a matched `omap_key_t`).
47#[derive(Debug, Clone, Copy)]
48#[non_exhaustive]
49pub struct OmapEntry {
50 /// Virtual object id (`ok_oid`).
51 pub oid: u64,
52 /// Transaction id of this mapping (`ok_xid`).
53 pub xid: u64,
54 /// Physical block address the virtual oid resolves to (`ov_paddr`).
55 pub paddr: u64,
56 /// `ov_size` (object size in bytes; one block for most objects).
57 pub size: u32,
58 /// `ov_flags`.
59 pub flags: u32,
60}
61
62/// Build the `omap_phys` [`crate::ApfsError::UnexpectedObjectType`] error,
63/// carrying the offending raw `o_type` (`found`) — shared by the short-block and
64/// wrong-type guards so the error shape lives in one place.
65fn unexpected_omap_type(found: u32) -> crate::ApfsError {
66 crate::ApfsError::UnexpectedObjectType {
67 structure: "omap_phys",
68 expected: u32::from(OBJECT_TYPE_OMAP),
69 found,
70 }
71}
72
73/// An object map header (`omap_phys_t`): the entry point into a volume/container
74/// object map's backing B-tree.
75#[derive(Debug, Clone, Copy)]
76#[non_exhaustive]
77pub struct ObjectMap {
78 flags: u32,
79 tree_type: u32,
80 tree_oid: u64,
81 snapshot_tree_oid: u64,
82}
83
84impl ObjectMap {
85 /// Parse and validate an `omap_phys_t` header from a block.
86 ///
87 /// Validates magic-by-type (`o_type & 0xffff == OBJECT_TYPE_OMAP`) and the
88 /// Fletcher-64 checksum before trusting any field (checksum-before-trust).
89 ///
90 /// # Errors
91 /// [`crate::ApfsError::NoValidSuperblock`]-style failures are not used here;
92 /// instead [`crate::ApfsError::UnexpectedObjectType`] is returned for a short
93 /// block or a non-omap object (carrying the offending type), and
94 /// [`crate::ApfsError::ChecksumMismatch`] for a Fletcher-64 failure.
95 pub fn parse(block: &[u8]) -> crate::Result<Self> {
96 if block.len() < OMAP_PHYS_MIN_LEN {
97 return Err(unexpected_omap_type(0));
98 }
99 // Type gate: the block must be an OMAP object.
100 let Some(hdr) = ObjPhys::parse(block) else {
101 // cov:unreachable: len checked >= OMAP_PHYS_MIN_LEN > OBJ_PHYS_LEN, so
102 // ObjPhys::parse (which only returns None on len < OBJ_PHYS_LEN) is Some.
103 return Err(unexpected_omap_type(0)); // cov:unreachable
104 };
105 if hdr.obj_type() != OBJECT_TYPE_OMAP {
106 return Err(unexpected_omap_type(hdr.obj_type_raw));
107 }
108 // Checksum gate before trusting the tree oids.
109 let stored = fletcher64_stored(block);
110 let computed = fletcher64_checksum(block);
111 if stored != computed {
112 return Err(crate::ApfsError::ChecksumMismatch {
113 block: hdr.oid,
114 stored,
115 computed,
116 });
117 }
118
119 Ok(Self {
120 flags: crate::bytes::le_u32(block, OFF_OM_FLAGS),
121 tree_type: crate::bytes::le_u32(block, OFF_OM_TREE_TYPE),
122 tree_oid: crate::bytes::le_u64(block, OFF_OM_TREE_OID),
123 snapshot_tree_oid: crate::bytes::le_u64(block, OFF_OM_SNAPSHOT_TREE_OID),
124 })
125 }
126
127 /// `om_tree_oid` — the oid of the B-tree backing this object map. For a
128 /// container omap the tree is stored *physically* (`om_tree_type` carries the
129 /// physical storage flag), so this oid is also the tree root's block address.
130 #[must_use]
131 pub fn tree_oid(&self) -> u64 {
132 self.tree_oid
133 }
134
135 /// `om_tree_type` (storage flags in the high bits | object type in the low).
136 #[must_use]
137 pub fn tree_type(&self) -> u32 {
138 self.tree_type
139 }
140
141 /// `om_flags` (`OMAP_MANUALLY_MANAGED 0x1`, `OMAP_ENCRYPTING 0x2`, …).
142 #[must_use]
143 pub fn flags(&self) -> u32 {
144 self.flags
145 }
146
147 /// `om_snapshot_tree_oid` — `0` when the omap has no snapshot tree.
148 #[must_use]
149 pub fn snapshot_tree_oid(&self) -> u64 {
150 self.snapshot_tree_oid
151 }
152
153 /// Resolve a virtual `oid` at transaction `xid` to a physical block address
154 /// by walking the omap B-tree, choosing the entry with the **largest
155 /// `ok_xid` ≤ `xid`** for the matching `ok_oid` (the most-recent state at or
156 /// before the requested transaction).
157 ///
158 /// The container omap tree is stored physically, so [`Self::tree_oid`] is the
159 /// root node's block address; the walk reads each node by its physical
160 /// address, verifying its Fletcher-64 checksum and guarding against cyclic
161 /// node links.
162 ///
163 /// # Errors
164 /// [`crate::ApfsError::OmapUnresolved`] if no mapping for `oid` at or before
165 /// `xid` exists; [`crate::ApfsError::ChecksumMismatch`] /
166 /// [`crate::ApfsError::CycleGuard`] / [`crate::ApfsError::Io`] on a
167 /// structurally invalid tree or a read failure.
168 pub fn resolve<R: std::io::Read + std::io::Seek>(
169 &self,
170 reader: &mut R,
171 oid: u64,
172 xid: u64,
173 block_size: usize,
174 ) -> crate::Result<OmapEntry> {
175 let mut best: Option<OmapEntry> = None;
176 // Keyed point descent: read one root→leaf path instead of the whole tree.
177 // The omap is keyed by (ok_oid, ok_xid); the entry we want — the largest
178 // ok_xid ≤ xid for this oid — is the floor of (oid, xid), which lives in
179 // the single leaf this descent lands on, so scanning that leaf suffices.
180 btree::find_leaf(
181 reader,
182 self.tree_oid,
183 block_size,
184 BTreeSubtype::Omap,
185 |key| {
186 // omap_key { ok_oid u64 @0, ok_xid u64 @8 }
187 let k_oid = crate::bytes::le_u64(key, 0);
188 let k_xid = crate::bytes::le_u64(key, 8);
189 (k_oid, k_xid).cmp(&(oid, xid))
190 },
191 &mut |key, value| {
192 let k_oid = crate::bytes::le_u64(key, 0);
193 let k_xid = crate::bytes::le_u64(key, 8);
194 if k_oid != oid || k_xid > xid {
195 return;
196 }
197 // omap_val { ov_flags u32 @0, ov_size u32 @4, ov_paddr u64 @8 }
198 let entry = OmapEntry {
199 oid: k_oid,
200 xid: k_xid,
201 flags: crate::bytes::le_u32(value, 0),
202 size: crate::bytes::le_u32(value, 4),
203 paddr: crate::bytes::le_u64(value, 8),
204 };
205 // Keep the most-recent (largest xid ≤ requested) candidate.
206 if best.is_none_or(|b| k_xid > b.xid) {
207 best = Some(entry);
208 }
209 },
210 )?;
211 best.ok_or(crate::ApfsError::OmapUnresolved { oid, xid })
212 }
213}