Skip to main content

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}