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}