Skip to main content

refs_core/
minstore.rs

1//! ReFS Minstore B+-tree page — the generic key→value index page every ReFS
2//! table (object table, directories, allocators, schema) is built from — and
3//! the object table that sits on top of it.
4//!
5//! Layout byte-verified against a real ReFS v3.14 volume and consistent with
6//! libyal `libfsrefs`. After the 80-byte metadata-block header
7//! ([`crate::MetaBlock`]) a Minstore page carries:
8//!
9//! ```text
10//! block+0x50  4   node header offset (relative to THIS field) -> node header
11//!  [optional 36-byte tree header + header data]
12//!  Node header (32 bytes):
13//!    0  4  data area start offset (relative to node header)
14//!    4  4  data area end offset
15//!    8  4  unused data size
16//!    c  1  node level (0 = leaf)
17//!    d  1  node type flags (0x01 branch/inner, 0x02 root, 0x04 stream)
18//!    e  2  unknown
19//!   10  4  record offsets start (relative to node header)
20//!   14  4  number of record offsets
21//!   18  4  record offsets end
22//!  Record offsets: u32 each; the UPPER 16 bits are 0xffff in v3, the LOWER 16
23//!    bits are the record offset relative to the node header.
24//!  Node record (variable):
25//!    0  4  record size (includes these 4 bytes)
26//!    4  2  key data offset (relative to record)
27//!    6  2  key data size
28//!    8  2  flags (0x08 = value holds an embedded Minstore node)
29//!    a  2  value data offset (relative to record)
30//!    c  2  value data size
31//! ```
32//!
33//! # Robustness
34//!
35//! A hostile page can lie about the record count, a record offset, or a
36//! key/value offset/size. Every read is bounds-checked: a record whose offset
37//! or key/value span falls outside the page is skipped, and the record count is
38//! capped so a lying count cannot spin an unbounded loop or over-read (the
39//! Paranoid Gatekeeper standard).
40
41use crate::bytes::{le_u16, le_u32, le_u64};
42use crate::error::RefsError;
43use crate::metablock::REFS_METADATA_PAGE_SIZE;
44
45/// The well-known ReFS root-directory object identifier (`REFS_ROOT_DIRECTORY_ID`
46/// in libyal `libfsrefs`). Later phases resolve this through the object table to
47/// reach the file tree.
48pub const REFS_ROOT_DIRECTORY_ID: u64 = 0x0000_0600;
49
50/// Offset of the node-header-offset field within a Minstore page (immediately
51/// after the 80-byte metadata-block header).
52const NODE_HEADER_OFFSET_FIELD: usize = 0x50;
53
54/// Length of the Minstore node header.
55const NODE_HEADER_LEN: usize = 32;
56
57/// Absolute cap on record-offset entries, independent of the page's claimed
58/// count: a page holds at most one 4-byte offset per possible record slot, so a
59/// count beyond the page's own byte capacity is a lie. This caps allocation and
60/// iteration regardless of the header's `number of record offsets`.
61const MAX_RECORDS: usize = REFS_METADATA_PAGE_SIZE / 4;
62
63/// One `(key, value)` Minstore node record, borrowing from the page buffer.
64#[derive(Debug)]
65#[non_exhaustive]
66pub struct MinstoreRow<'a> {
67    /// The record's key bytes.
68    pub key: &'a [u8],
69    /// The record's value bytes.
70    pub value: &'a [u8],
71    /// The record's flags word (`0x08` = value holds an embedded Minstore node).
72    pub flags: u16,
73}
74
75/// A parsed Minstore B+-tree page (leaf or internal/branch node).
76#[derive(Debug)]
77#[non_exhaustive]
78pub struct MinstorePage<'a> {
79    /// The page bytes (a single 16 KiB metadata page).
80    page: &'a [u8],
81    /// Absolute offset of the node header within `page`.
82    node_header: usize,
83    /// Node level (`0` = leaf).
84    level: u8,
85    /// Node type flags (`0x01` = branch/inner, `0x02` = root, `0x04` = stream).
86    flags: u8,
87    /// Absolute offset of the record-offset array within `page`.
88    record_offsets: usize,
89    /// Number of record offsets, already clamped to what the page can hold.
90    record_count: usize,
91}
92
93impl<'a> MinstorePage<'a> {
94    /// Parse the Minstore node in `data` (a metadata page). `offset` is the
95    /// page's absolute byte position, used only for diagnostics.
96    ///
97    /// # Errors
98    ///
99    /// - [`RefsError::Truncated`] if the page is too short to hold the
100    ///   node-header-offset field or the node header it points at.
101    pub fn parse(data: &'a [u8], offset: u64) -> Result<Self, RefsError> {
102        let _ = offset;
103        if data.len() < NODE_HEADER_OFFSET_FIELD + 4 {
104            return Err(RefsError::Truncated {
105                structure: "Minstore node-header-offset field",
106                need: NODE_HEADER_OFFSET_FIELD + 4,
107                have: data.len(),
108            });
109        }
110        // The node-header-offset value is relative to the start of its own
111        // field. Use a saturating/bounds-checked resolution so a hostile value
112        // can never index out of the page.
113        let rel = le_u32(data, NODE_HEADER_OFFSET_FIELD) as usize;
114        let node_header = NODE_HEADER_OFFSET_FIELD.saturating_add(rel);
115        if node_header
116            .checked_add(NODE_HEADER_LEN)
117            .is_none_or(|end| end > data.len())
118        {
119            return Err(RefsError::Truncated {
120                structure: "Minstore node header",
121                need: node_header.saturating_add(NODE_HEADER_LEN),
122                have: data.len(),
123            });
124        }
125
126        let level = data.get(node_header + 12).copied().unwrap_or(0);
127        let flags = data.get(node_header + 13).copied().unwrap_or(0);
128        let roff_rel = le_u32(data, node_header + 16) as usize;
129        let claimed = le_u32(data, node_header + 20) as usize;
130        let record_offsets = node_header.saturating_add(roff_rel);
131
132        // Clamp the record count to what actually fits between the offset array
133        // start and the end of the page — a lying count then yields only the
134        // offsets the page can physically hold (never an over-read).
135        let capacity = data.len().saturating_sub(record_offsets) / 4;
136        let record_count = claimed.min(capacity).min(MAX_RECORDS);
137
138        Ok(Self {
139            page: data,
140            node_header,
141            level,
142            flags,
143            record_offsets,
144            record_count,
145        })
146    }
147
148    /// The node level (`0` = leaf; higher = internal).
149    #[must_use]
150    pub fn level(&self) -> u8 {
151        self.level
152    }
153
154    /// True for a leaf node (level `0` and not a branch).
155    #[must_use]
156    pub fn is_leaf(&self) -> bool {
157        self.level == 0 && !self.is_branch()
158    }
159
160    /// True for an internal/branch node (node-type flag `0x01`).
161    #[must_use]
162    pub fn is_branch(&self) -> bool {
163        self.flags & 0x01 != 0
164    }
165
166    /// Iterate the node's `(key, value)` records, skipping any record whose
167    /// offset or key/value span lies outside the page (never over-reads).
168    pub fn rows(&self) -> impl Iterator<Item = MinstoreRow<'a>> + '_ {
169        (0..self.record_count).filter_map(move |i| self.row(i))
170    }
171
172    /// Resolve record `i` to a bounds-checked `(key, value)` row, or `None` if
173    /// any offset/length lies outside the page.
174    fn row(&self, i: usize) -> Option<MinstoreRow<'a>> {
175        let off_pos = self.record_offsets.checked_add(i.checked_mul(4)?)?;
176        // Record offset: lower 16 bits (upper 16 are 0xffff in v3), relative to
177        // the node header.
178        let raw = le_u32(self.page, off_pos);
179        let rec = self.node_header.checked_add((raw & 0xffff) as usize)?;
180        // Need the 14-byte record header in bounds.
181        if rec.checked_add(14)? > self.page.len() {
182            return None;
183        }
184        let key_off = le_u16(self.page, rec + 4) as usize;
185        let key_len = le_u16(self.page, rec + 6) as usize;
186        let flags = le_u16(self.page, rec + 8);
187        let val_off = le_u16(self.page, rec + 10) as usize;
188        let val_len = le_u16(self.page, rec + 12) as usize;
189
190        let key_start = rec.checked_add(key_off)?;
191        let key_end = key_start.checked_add(key_len)?;
192        let val_start = rec.checked_add(val_off)?;
193        let val_end = val_start.checked_add(val_len)?;
194        let key = self.page.get(key_start..key_end)?;
195        let value = self.page.get(val_start..val_end)?;
196        Some(MinstoreRow { key, value, flags })
197    }
198}
199
200/// A resolved object-table entry: the metadata block number of an object's tree
201/// root.
202#[derive(Debug, Clone, PartialEq, Eq)]
203#[non_exhaustive]
204pub struct PageRef {
205    /// The object's tree-root metadata block number (a virtual address in v3;
206    /// later phases resolve it through the container table before reading).
207    pub block_number: u64,
208}
209
210/// The ReFS object table: a Minstore B+-tree keyed by object identifier, whose
211/// values point at each object's own Minstore tree root.
212///
213/// The object-record **key** is 16 bytes — `[0..8]` zero, `[8..16]` the object
214/// identifier (little-endian). The **value** carries a v3 metadata block
215/// reference whose first block number sits at value offset `0x20` (32).
216#[derive(Debug)]
217#[non_exhaustive]
218pub struct ObjectTable<'a> {
219    node: MinstorePage<'a>,
220}
221
222impl<'a> ObjectTable<'a> {
223    /// Object-identifier position within the 16-byte object-record key.
224    const KEY_ID_OFFSET: usize = 8;
225    /// Offset of the first block number within the object-record value (the
226    /// embedded v3 metadata block reference starts at value offset `0x20`).
227    const VALUE_BLOCK_REF_OFFSET: usize = 0x20;
228
229    /// Parse an object-table page (a Minstore B+-tree node).
230    ///
231    /// # Errors
232    ///
233    /// Any error from [`MinstorePage::parse`].
234    pub fn parse(data: &'a [u8], offset: u64) -> Result<Self, RefsError> {
235        Ok(Self {
236            node: MinstorePage::parse(data, offset)?,
237        })
238    }
239
240    /// Look up an object identifier, returning the block reference to its tree
241    /// root, or `None` if the id is absent (or a matching record is malformed).
242    #[must_use]
243    pub fn lookup(&self, object_id: u64) -> Option<PageRef> {
244        self.node.rows().find_map(|row| {
245            // Key: 16 bytes, object id at [8..16].
246            let id_bytes = row.key.get(Self::KEY_ID_OFFSET..Self::KEY_ID_OFFSET + 8)?;
247            let id = le_u64(id_bytes, 0);
248            if id != object_id {
249                return None;
250            }
251            // Value: block reference first block number at value+0x20.
252            let block = row
253                .value
254                .get(Self::VALUE_BLOCK_REF_OFFSET..Self::VALUE_BLOCK_REF_OFFSET + 8)
255                .map(|b| le_u64(b, 0))?;
256            Some(PageRef {
257                block_number: block,
258            })
259        })
260    }
261}