refs_core/container.rs
1//! ReFS v3 container table — the virtual → physical block map.
2//!
3//! # The problem this solves
4//!
5//! In ReFS v3.x the object table names each object's tree-root as a **virtual
6//! block number**, not a physical location. P2 hit this wall: object `0x600`
7//! (the root directory) resolved to a virtual block whose physical page could
8//! not be reached. This module builds the container table and translates.
9//!
10//! # Layout (reverse-engineered — libyal `libfsrefs` §8 "Container tree" + a
11//! real v3.14 volume, byte-verified 2026-07-15; see tests/data/README.md)
12//!
13//! A ReFS **container (band)** is a fixed run of clusters. Its size in clusters
14//! is `band_size / cluster_size` — on the v3.14 oracle
15//! `67_108_864 / 4096 = 16_384` clusters (the boot sector's "Container (or
16//! band) size" at offset 64). A **virtual block number** decomposes as:
17//!
18//! ```text
19//! container_index = vblock / band_clusters
20//! offset_in_container = vblock % band_clusters
21//! ```
22//!
23//! The **container tree** is a Minstore B+-tree ([`crate::MinstorePage`]) of
24//! **160-byte container records**:
25//!
26//! ```text
27//! key +0 8 band identifier (u64)
28//! value +0 8 band (container) identifier
29//! +144 8 cluster block number (the physical LCN — the band's base)
30//! +152 8 cluster count (= band_clusters, the band size)
31//! ```
32//!
33//! Resolving a virtual block:
34//!
35//! ```text
36//! physical_cluster = container_base[container_index] + offset_in_container
37//! physical_offset = physical_cluster * cluster_size
38//! ```
39//!
40//! # The base map (bootstrap, evidence-based — not hardcoded)
41//!
42//! `container_base` maps a *virtual* container index to its *physical* base
43//! cluster. On the real volume the container tree's `band_id` is the *physical*
44//! band, and the virtual-container-index→band mapping is many-to-one (two
45//! virtual indices can share one physical band), so it needs the container
46//! *index* tree — a further table not always resident. This crate therefore
47//! bootstraps the base map from **physically resident metadata**: every
48//! resident Minstore page carries its own (self) block number at header offset
49//! `0x20`, and its physical cluster is where it sits, so
50//! `base[self / band_clusters] = phys_cluster - (self % band_clusters)`. This is
51//! ground truth (verified: `self % band_clusters == phys_cluster - LCN` holds on
52//! every resident page), needs no undocumented indirection, and resolves the
53//! real `0x600` root-directory block. A virtual block whose container index was
54//! never witnessed in the resident metadata is **unresolved** and fails loud
55//! (never a wrong physical offset) — the bootstrap-failure-≠-empty standard.
56//!
57//! # Robustness
58//!
59//! The container tree is parsed through the bounds-checked [`crate::MinstorePage`]
60//! layer (a lying record count/offset yields only in-bounds rows). Every field
61//! read uses the saturating LE helpers; an out-of-range container-record field
62//! yields `0`/`None`, never a panic. The base map is capped by the image's own
63//! cluster count.
64
65use crate::bytes::le_u64;
66use crate::error::RefsError;
67use crate::metablock::REFS_METADATA_PAGE_SIZE;
68use crate::minstore::MinstorePage;
69
70/// ReFS cluster size in bytes (4 KiB — verified on the v3.14 oracle). Four
71/// clusters make one 16 KiB metadata page.
72const CLUSTER_SIZE: u64 = 4096;
73
74/// Offset of the physical cluster block number (LCN) within a 160-byte
75/// container record value (`libfsrefs` §8.1.2).
76const CONTAINER_LCN_OFFSET: usize = 144;
77
78/// Offset of the cluster count (band size in clusters) within a container
79/// record value.
80const CONTAINER_CLUSTER_COUNT_OFFSET: usize = 152;
81
82/// Minimum length of a container record value (`libfsrefs` §8.1.2: 160 bytes).
83const CONTAINER_RECORD_VALUE_LEN: usize = 160;
84
85/// Decompose a ReFS virtual block number into `(container_index,
86/// offset_in_container)` given the band size in clusters.
87///
88/// `container_index = vblock / band_clusters`,
89/// `offset_in_container = vblock % band_clusters`. A `band_clusters` of `0`
90/// (a malformed boot sector) yields `(vblock, 0)` rather than dividing by zero
91/// (the Paranoid Gatekeeper standard — no panic on hostile input).
92#[must_use]
93pub fn decompose_virtual_block(vblock: u64, band_clusters: u64) -> (u64, u64) {
94 if band_clusters == 0 {
95 return (vblock, 0);
96 }
97 (vblock / band_clusters, vblock % band_clusters)
98}
99
100/// One parsed container record: a band's identifier and its physical placement.
101#[derive(Debug, Clone, PartialEq, Eq)]
102#[non_exhaustive]
103pub struct ContainerRecord {
104 /// The band (container) identifier — the container-tree key.
105 pub band_id: u64,
106 /// The physical base cluster of this band (its cluster block number / LCN).
107 pub physical_lcn: u64,
108 /// The band size in clusters (the record's cluster count).
109 pub cluster_count: u64,
110}
111
112/// The ReFS container tree: a Minstore B+-tree of 160-byte container records
113/// mapping each band to its physical cluster block number (`libfsrefs` §8).
114#[derive(Debug)]
115#[non_exhaustive]
116pub struct ContainerTable<'a> {
117 node: MinstorePage<'a>,
118}
119
120impl<'a> ContainerTable<'a> {
121 /// Parse a container-tree page (a Minstore B+-tree node).
122 ///
123 /// # Errors
124 ///
125 /// Any error from [`MinstorePage::parse`] (a page too short to hold the
126 /// node header).
127 pub fn parse(data: &'a [u8], offset: u64) -> Result<Self, RefsError> {
128 Ok(Self {
129 node: MinstorePage::parse(data, offset)?,
130 })
131 }
132
133 /// Iterate the parsed container records (skipping any row whose value is
134 /// shorter than the 160-byte container record — never over-reads).
135 pub fn records(&self) -> impl Iterator<Item = ContainerRecord> + '_ {
136 self.node.rows().filter_map(|row| {
137 // A container record value is 160 bytes; a shorter value is not a
138 // container record (the container tree shares the page format with
139 // other Minstore trees), so skip it rather than read past it.
140 if row.value.len() < CONTAINER_RECORD_VALUE_LEN {
141 return None;
142 }
143 let band_id = le_u64(row.value, 0);
144 let physical_lcn = le_u64(row.value, CONTAINER_LCN_OFFSET);
145 let cluster_count = le_u64(row.value, CONTAINER_CLUSTER_COUNT_OFFSET);
146 Some(ContainerRecord {
147 band_id,
148 physical_lcn,
149 cluster_count,
150 })
151 })
152 }
153
154 /// The physical base cluster (LCN) of `band_id`, or `None` if the band is
155 /// absent from this leaf.
156 #[must_use]
157 pub fn physical_base(&self, band_id: u64) -> Option<u64> {
158 self.records()
159 .find(|r| r.band_id == band_id)
160 .map(|r| r.physical_lcn)
161 }
162
163 /// The cluster count (band size) of `band_id`, or `None` if absent.
164 #[must_use]
165 pub fn cluster_count(&self, band_id: u64) -> Option<u64> {
166 self.records()
167 .find(|r| r.band_id == band_id)
168 .map(|r| r.cluster_count)
169 }
170}
171
172/// A virtual → physical block resolver built from the physically resident
173/// metadata of a ReFS image.
174///
175/// Each resident Minstore page's self-block-number (header offset `0x20`) is
176/// ground truth for its container's physical base; scanning them yields a
177/// `container_index → physical_base_cluster` map. Resolving a virtual block then
178/// decomposes it and applies the base. See the module docs for why this
179/// evidence-based bootstrap is used rather than the (many-to-one, index-tree
180/// dependent) container-tree band enumeration.
181#[derive(Debug, Clone)]
182#[non_exhaustive]
183pub struct ContainerResolver {
184 /// Band size in clusters (`band_size / cluster_size`).
185 band_clusters: u64,
186 /// `container_index → physical_base_cluster`, derived from resident pages.
187 base: Vec<(u64, u64)>,
188}
189
190/// The ReFS metadata-block signature every resident metadata page starts with
191/// (superblock/checkpoint use their own; Minstore pages use `MSB+`). The
192/// resident base map is bootstrapped from `MSB+` pages, whose self-block-number
193/// at header offset `0x20` is the virtual block the page answers to.
194const MSB_SIGNATURE: &[u8; 4] = b"MSB+";
195
196/// Header offset of a metadata page's self (first) block number.
197const SELF_BLOCK_OFFSET: usize = 0x20;
198
199impl ContainerResolver {
200 /// Build a resolver by scanning `image` for physically resident Minstore
201 /// pages and recording each container's physical base from the pages'
202 /// self-block-numbers.
203 ///
204 /// `band_clusters` is the band size in clusters
205 /// (`boot.container_size / cluster_size`; `16_384` on the v3.14 oracle).
206 #[must_use]
207 pub fn from_resident_image(image: &[u8], band_clusters: u64) -> Self {
208 let mut base: Vec<(u64, u64)> = Vec::new();
209 if band_clusters == 0 {
210 return Self {
211 band_clusters,
212 base,
213 };
214 }
215 let cluster = CLUSTER_SIZE as usize;
216 // Metadata pages sit on cluster boundaries; step by cluster and inspect
217 // any page carrying the Minstore signature.
218 let clusters = image.len() / cluster;
219 for c in 0..clusters {
220 let off = c * cluster;
221 // Need the full page in bounds to trust its self-block-number.
222 if off + REFS_METADATA_PAGE_SIZE > image.len() {
223 break;
224 }
225 if &image[off..off + 4] != MSB_SIGNATURE {
226 continue;
227 }
228 let self_block = le_u64(image, off + SELF_BLOCK_OFFSET);
229 let (idx, off_in_band) = decompose_virtual_block(self_block, band_clusters);
230 // The physical base cluster this virtual container maps to.
231 let phys_cluster = c as u64;
232 // A (hostile) page whose offset-in-band exceeds its physical
233 // cluster is inconsistent — skip it rather than record a wrong base
234 // (a wrong base would mis-resolve every block in that container).
235 let Some(band_base) = phys_cluster.checked_sub(off_in_band) else {
236 continue;
237 };
238 if !base.iter().any(|&(i, _)| i == idx) {
239 base.push((idx, band_base));
240 }
241 }
242 Self {
243 band_clusters,
244 base,
245 }
246 }
247
248 /// The physical base cluster mapped to virtual container `index`, or `None`.
249 #[must_use]
250 fn base_of(&self, index: u64) -> Option<u64> {
251 self.base
252 .iter()
253 .find(|&&(i, _)| i == index)
254 .map(|&(_, b)| b)
255 }
256
257 /// Resolve a virtual block number to a physical byte offset, or `None` if
258 /// its container index was never witnessed in the resident metadata (an
259 /// unresolved virtual address — the caller must treat this as a hard wall,
260 /// not an empty result).
261 #[must_use]
262 pub fn resolve_virtual(&self, vblock: u64) -> Option<u64> {
263 let (idx, off) = decompose_virtual_block(vblock, self.band_clusters);
264 let base = self.base_of(idx)?;
265 let cluster = base.checked_add(off)?;
266 cluster.checked_mul(CLUSTER_SIZE)
267 }
268
269 /// Resolve a virtual block number, failing loud with the offending block
270 /// number when it cannot be mapped (rather than a silent `None`).
271 ///
272 /// # Errors
273 ///
274 /// [`RefsError::UnresolvedVirtualBlock`] naming `vblock` when its container
275 /// index has no resident base mapping (or the computed offset overflows).
276 pub fn resolve_virtual_checked(&self, vblock: u64) -> Result<u64, RefsError> {
277 self.resolve_virtual(vblock)
278 .ok_or(RefsError::UnresolvedVirtualBlock { block: vblock })
279 }
280}
281
282#[cfg(test)]
283mod tests {
284 use super::*;
285
286 #[test]
287 fn decompose_zero_band_clusters_never_divides_by_zero() {
288 // A malformed boot sector reporting a zero band size must not panic; the
289 // virtual block passes through as `(vblock, 0)` (no division).
290 assert_eq!(decompose_virtual_block(80_384, 0), (80_384, 0));
291 }
292
293 #[test]
294 fn resolver_zero_band_clusters_is_empty_and_resolves_nothing() {
295 // A zero band size yields an empty resolver (no base entries), and every
296 // resolution then fails loud rather than dividing by zero.
297 let image = vec![0u8; 64 * 4096];
298 let resolver = ContainerResolver::from_resident_image(&image, 0);
299 assert!(resolver.resolve_virtual(80_384).is_none());
300 assert!(matches!(
301 resolver.resolve_virtual_checked(80_384),
302 Err(RefsError::UnresolvedVirtualBlock { block: 80_384 })
303 ));
304 }
305
306 #[test]
307 fn container_records_skip_short_values() {
308 // A Minstore page whose rows carry values shorter than a 160-byte
309 // container record must yield NO container records (the container tree
310 // shares the page format with other trees) — never an over-read.
311 //
312 // Build a minimal valid Minstore page with one 16-byte-value row.
313 let page = build_short_value_page();
314 let ct = ContainerTable::parse(&page, 0).expect("parses");
315 assert_eq!(
316 ct.records().count(),
317 0,
318 "short-value rows are not container records"
319 );
320 assert_eq!(ct.physical_base(1), None);
321 assert_eq!(ct.cluster_count(1), None);
322 }
323
324 #[test]
325 fn resolver_skips_inconsistent_page_whose_offset_exceeds_its_cluster() {
326 // A hostile page carrying the MSB+ signature at cluster 0 but a
327 // self-block-number with a nonzero offset-in-band (offset 5 > cluster 0)
328 // is inconsistent — it must be SKIPPED, never used to record a wrong
329 // base. Here the only such page sits at cluster 0, so no base is learned
330 // and every resolution then fails loud (rather than a wrong offset).
331 const CLUSTER: usize = 4096;
332 let band_clusters = 16_384u64;
333 let mut image = vec![0u8; 64 * CLUSTER];
334 // Page at cluster 0: MSB+ with self-block 5 → container 0, offset 5,
335 // but phys cluster 0 < 5 → checked_sub underflows → skip.
336 image[0..4].copy_from_slice(b"MSB+");
337 image[0x20..0x28].copy_from_slice(&5u64.to_le_bytes());
338 let resolver = ContainerResolver::from_resident_image(&image, band_clusters);
339 // Container 0 was NOT learned (the inconsistent page was skipped).
340 assert!(
341 resolver.resolve_virtual(5).is_none(),
342 "an inconsistent page must not seed a base map entry"
343 );
344 }
345
346 /// A minimal Minstore leaf page with a single row whose value is 16 bytes
347 /// (shorter than a 160-byte container record), mirroring the verified P1
348 /// page layout.
349 fn build_short_value_page() -> Vec<u8> {
350 const PAGE: usize = REFS_METADATA_PAGE_SIZE;
351 let mut page = vec![0u8; PAGE];
352 page[0..4].copy_from_slice(b"MSB+");
353 let node_hdr = 0x100usize;
354 let nho_field = 0x50usize;
355 page[nho_field..nho_field + 4]
356 .copy_from_slice(&((node_hdr - nho_field) as u32).to_le_bytes());
357 let rec = node_hdr + 32;
358 let key = vec![0u8; 8];
359 let value = vec![0u8; 16];
360 let key_off = 16u16;
361 let val_off = key_off + key.len() as u16;
362 let rec_size = (val_off as usize + value.len()) as u32;
363 page[rec..rec + 4].copy_from_slice(&rec_size.to_le_bytes());
364 page[rec + 4..rec + 6].copy_from_slice(&key_off.to_le_bytes());
365 page[rec + 6..rec + 8].copy_from_slice(&(key.len() as u16).to_le_bytes());
366 page[rec + 8..rec + 10].copy_from_slice(&0u16.to_le_bytes());
367 page[rec + 10..rec + 12].copy_from_slice(&val_off.to_le_bytes());
368 page[rec + 12..rec + 14].copy_from_slice(&(value.len() as u16).to_le_bytes());
369 page[rec + key_off as usize..rec + key_off as usize + key.len()].copy_from_slice(&key);
370 page[rec + val_off as usize..rec + val_off as usize + value.len()].copy_from_slice(&value);
371 let roff_start_abs = node_hdr + 0x2000;
372 page[roff_start_abs..roff_start_abs + 4]
373 .copy_from_slice(&(0xffff_0000u32 | ((rec - node_hdr) as u32 & 0xffff)).to_le_bytes());
374 let nh = node_hdr;
375 page[nh + 16..nh + 20].copy_from_slice(&((roff_start_abs - node_hdr) as u32).to_le_bytes());
376 page[nh + 20..nh + 24].copy_from_slice(&1u32.to_le_bytes());
377 page
378 }
379}