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/// An object map header (`omap_phys_t`): the entry point into a volume/container
63/// object map's backing B-tree.
64#[derive(Debug, Clone, Copy)]
65#[non_exhaustive]
66pub struct ObjectMap {
67 flags: u32,
68 tree_type: u32,
69 tree_oid: u64,
70 snapshot_tree_oid: u64,
71}
72
73impl ObjectMap {
74 /// Parse and validate an `omap_phys_t` header from a block.
75 ///
76 /// Validates magic-by-type (`o_type & 0xffff == OBJECT_TYPE_OMAP`) and the
77 /// Fletcher-64 checksum before trusting any field (checksum-before-trust).
78 ///
79 /// # Errors
80 /// [`crate::ApfsError::NoValidSuperblock`]-style failures are not used here;
81 /// instead [`crate::ApfsError::UnexpectedObjectType`] is returned for a short
82 /// block or a non-omap object (carrying the offending type), and
83 /// [`crate::ApfsError::ChecksumMismatch`] for a Fletcher-64 failure.
84 pub fn parse(block: &[u8]) -> crate::Result<Self> {
85 if block.len() < OMAP_PHYS_MIN_LEN {
86 return Err(crate::ApfsError::UnexpectedObjectType {
87 structure: "omap_phys",
88 expected: u32::from(OBJECT_TYPE_OMAP),
89 found: 0,
90 });
91 }
92 // Type gate: the block must be an OMAP object.
93 let Some(hdr) = ObjPhys::parse(block) else {
94 return Err(crate::ApfsError::UnexpectedObjectType {
95 structure: "omap_phys",
96 expected: u32::from(OBJECT_TYPE_OMAP),
97 found: 0,
98 }); // cov:unreachable: len checked >= OMAP_PHYS_MIN_LEN > OBJ_PHYS_LEN
99 };
100 if hdr.obj_type() != OBJECT_TYPE_OMAP {
101 return Err(crate::ApfsError::UnexpectedObjectType {
102 structure: "omap_phys",
103 expected: u32::from(OBJECT_TYPE_OMAP),
104 found: hdr.obj_type_raw,
105 });
106 }
107 // Checksum gate before trusting the tree oids.
108 let stored = fletcher64_stored(block);
109 let computed = fletcher64_checksum(block);
110 if stored != computed {
111 return Err(crate::ApfsError::ChecksumMismatch {
112 block: hdr.oid,
113 stored,
114 computed,
115 });
116 }
117
118 Ok(Self {
119 flags: crate::bytes::le_u32(block, OFF_OM_FLAGS),
120 tree_type: crate::bytes::le_u32(block, OFF_OM_TREE_TYPE),
121 tree_oid: crate::bytes::le_u64(block, OFF_OM_TREE_OID),
122 snapshot_tree_oid: crate::bytes::le_u64(block, OFF_OM_SNAPSHOT_TREE_OID),
123 })
124 }
125
126 /// `om_tree_oid` — the oid of the B-tree backing this object map. For a
127 /// container omap the tree is stored *physically* (`om_tree_type` carries the
128 /// physical storage flag), so this oid is also the tree root's block address.
129 #[must_use]
130 pub fn tree_oid(&self) -> u64 {
131 self.tree_oid
132 }
133
134 /// `om_tree_type` (storage flags in the high bits | object type in the low).
135 #[must_use]
136 pub fn tree_type(&self) -> u32 {
137 self.tree_type
138 }
139
140 /// `om_flags` (`OMAP_MANUALLY_MANAGED 0x1`, `OMAP_ENCRYPTING 0x2`, …).
141 #[must_use]
142 pub fn flags(&self) -> u32 {
143 self.flags
144 }
145
146 /// `om_snapshot_tree_oid` — `0` when the omap has no snapshot tree.
147 #[must_use]
148 pub fn snapshot_tree_oid(&self) -> u64 {
149 self.snapshot_tree_oid
150 }
151
152 /// Resolve a virtual `oid` at transaction `xid` to a physical block address
153 /// by walking the omap B-tree, choosing the entry with the **largest
154 /// `ok_xid` ≤ `xid`** for the matching `ok_oid` (the most-recent state at or
155 /// before the requested transaction).
156 ///
157 /// The container omap tree is stored physically, so [`Self::tree_oid`] is the
158 /// root node's block address; the walk reads each node by its physical
159 /// address, verifying its Fletcher-64 checksum and guarding against cyclic
160 /// node links.
161 ///
162 /// # Errors
163 /// [`crate::ApfsError::OmapUnresolved`] if no mapping for `oid` at or before
164 /// `xid` exists; [`crate::ApfsError::ChecksumMismatch`] /
165 /// [`crate::ApfsError::CycleGuard`] / [`crate::ApfsError::Io`] on a
166 /// structurally invalid tree or a read failure.
167 pub fn resolve<R: std::io::Read + std::io::Seek>(
168 &self,
169 reader: &mut R,
170 oid: u64,
171 xid: u64,
172 block_size: usize,
173 ) -> crate::Result<OmapEntry> {
174 let mut best: Option<OmapEntry> = None;
175 // Keyed point descent: read one root→leaf path instead of the whole tree.
176 // The omap is keyed by (ok_oid, ok_xid); the entry we want — the largest
177 // ok_xid ≤ xid for this oid — is the floor of (oid, xid), which lives in
178 // the single leaf this descent lands on, so scanning that leaf suffices.
179 btree::find_leaf(
180 reader,
181 self.tree_oid,
182 block_size,
183 BTreeSubtype::Omap,
184 |key| {
185 // omap_key { ok_oid u64 @0, ok_xid u64 @8 }
186 let k_oid = crate::bytes::le_u64(key, 0);
187 let k_xid = crate::bytes::le_u64(key, 8);
188 (k_oid, k_xid).cmp(&(oid, xid))
189 },
190 &mut |key, value| {
191 let k_oid = crate::bytes::le_u64(key, 0);
192 let k_xid = crate::bytes::le_u64(key, 8);
193 if k_oid != oid || k_xid > xid {
194 return;
195 }
196 // omap_val { ov_flags u32 @0, ov_size u32 @4, ov_paddr u64 @8 }
197 let entry = OmapEntry {
198 oid: k_oid,
199 xid: k_xid,
200 flags: crate::bytes::le_u32(value, 0),
201 size: crate::bytes::le_u32(value, 4),
202 paddr: crate::bytes::le_u64(value, 8),
203 };
204 // Keep the most-recent (largest xid ≤ requested) candidate.
205 if best.is_none_or(|b| k_xid > b.xid) {
206 best = Some(entry);
207 }
208 },
209 )?;
210 best.ok_or(crate::ApfsError::OmapUnresolved { oid, xid })
211 }
212}