ferrosys/btrfs/btree.rs
1//! The B-tree engine: one descent, one iteration, and the bounds that make both terminate on
2//! an image that was crafted rather than formatted.
3//!
4//! Every tree in a btrfs is the same shape — internal nodes of `(key, child address)` pairs
5//! over leaves of `(key, data)` items, sorted by the key tuple — so there is one engine and
6//! every tree is read through it. What an item *means* is decided by whoever asked for it;
7//! this module knows only that items have keys and that keys are ordered.
8//!
9//! # What bounds a walk
10//!
11//! An untrusted image can describe a tree that is not one, and each way of doing so has its
12//! own guard:
13//!
14//! - **A count larger than the block holds.** Checked against the room the block has, in the
15//! units the block's own level says it holds — 25 bytes per item, 33 per child pointer.
16//! - **An item whose data escapes its leaf.** Checked in two directions, because a leaf fills
17//! from both ends: the data must begin past the array describing it and end within the
18//! block. The arithmetic is 64-bit whatever the target's pointer width is, so a crafted
19//! offset and length behave the same on a 32-bit machine as on the one this is developed
20//! on.
21//! - **A leaf whose data is not packed.** Every item's data abuts its neighbour's, so a leaf
22//! whose data has been moved with its offsets moved to match — every item still inside the
23//! block, every item pointing at bytes that are not its own — is refused. Nothing about a
24//! bound sees that one, and what a reader would otherwise hand back is one record's bytes
25//! under another record's key.
26//! - **A child pointer that leads back up.** Every address a descent visits is remembered, and
27//! meeting one twice is a refusal rather than a loop.
28//! - **A child at the wrong height.** A child must be exactly one level below its parent, so a
29//! descent has a decreasing measure independent of the visited set and terminates whatever
30//! the addresses say.
31//! - **A block from another transaction.** A root item and a parent's pointer each record the
32//! transaction that wrote the block they lead to, and a block at any other is refused: one
33//! left over from an earlier transaction at an address since written again verifies in
34//! every other respect.
35//! - **Keys out of order, or out of place.** A tree that is not sorted is not a tree, and a
36//! search over one silently misses items rather than failing. Every block's keys are held
37//! against each other when a descent reaches it, a node's as well as a leaf's, and against
38//! the keys its parent records: its first key is the parent's key for it, and its last is
39//! below the parent's key for the block after it. A node's keys are what a search steers
40//! by, so one that does not match the block it leads to hides files a walk of every block
41//! would still meet.
42//! - **A tree larger than the caller will hold.** [`Limits::max_walk_entries`](crate::Limits::max_walk_entries) caps the items
43//! one walk visits.
44//!
45//! This module does I/O, through the volume it borrows.
46
47use std::collections::BTreeSet;
48use std::io::{Read, Seek};
49
50use super::ondisk::DiskKey;
51use super::volume::{ReadError, TreeBlock, TreeRoot, Volume};
52
53/// One item, taken out of the tree that held it.
54#[derive(Clone, PartialEq, Eq, Debug)]
55pub struct Located {
56 /// The key it was found under.
57 pub key: DiskKey,
58 /// Its bytes, which are as long as the item said and no longer.
59 pub data: Vec<u8>,
60}
61
62/// How many blocks stand above `leaves`, level by level, in a tree of this fan-out.
63///
64/// The first entry is the level directly above the leaves and the last is always one — the
65/// root. A tree whose leaves are one block has nothing above them, and the answer is empty:
66/// that leaf *is* the root.
67///
68/// The arithmetic is the same whether it is being asked in advance as a bound
69/// ([`geometry`](super::geometry)) or exactly of records already packed
70/// ([`materialize`](super::materialize)), so it is asked in one place. `fan_out` is floored at
71/// two, because a level whose blocks hold one child each never narrows and the stack would not
72/// end — a floor rather than an error, since the only caller that could reach it derives the
73/// fan-out from a node size the format has already accepted.
74pub(super) fn levels_above(leaves: u64, fan_out: u64) -> Vec<u64> {
75 let fan_out = fan_out.max(2);
76 let mut levels = Vec::new();
77 let mut width = leaves;
78 while width > 1 {
79 width = width.div_ceil(fan_out);
80 levels.push(width);
81 }
82 levels
83}
84
85/// A handle on one tree of a volume, for searching or iterating it.
86///
87/// Borrowed from the [`Volume`] rather than owning anything, so a caller moves between trees
88/// without reopening the filesystem — and so that every block either reads goes through the
89/// one chunk map and the one checksum check.
90pub struct Tree<'a, R> {
91 volume: &'a mut Volume<R>,
92 root: TreeRoot,
93}
94
95impl<'a, R: Read + Seek> Tree<'a, R> {
96 /// A handle on the tree `root` names.
97 pub(super) fn new(volume: &'a mut Volume<R>, root: TreeRoot) -> Self {
98 Self { volume, root }
99 }
100
101 /// Which tree this is, and where it begins.
102 #[must_use]
103 pub fn root(&self) -> TreeRoot {
104 self.root
105 }
106
107 /// Visit every item, in key order.
108 ///
109 /// The closure answers whether to keep going, so a caller looking for one thing stops
110 /// where it finds it rather than reading the rest of the tree.
111 ///
112 /// # Errors
113 ///
114 /// Whatever reading a block does, and the tree-shape refusals this module's documentation
115 /// lists.
116 pub fn for_each_item<F>(&mut self, mut visit: F) -> Result<(), ReadError>
117 where
118 F: FnMut(&DiskKey, &[u8]) -> bool,
119 {
120 self.drive(DiskKey::MIN, &mut |_| true, &mut visit)
121 }
122
123 /// Visit every item at or after `from`, in key order.
124 ///
125 /// The descent goes straight to the first item at or after the key rather than walking the
126 /// tree from its start, which is what makes "the entries of this directory" one descent
127 /// instead of a scan.
128 ///
129 /// # Errors
130 ///
131 /// As [`for_each_item`](Self::for_each_item).
132 pub fn for_each_item_from<F>(&mut self, from: DiskKey, mut visit: F) -> Result<(), ReadError>
133 where
134 F: FnMut(&DiskKey, &[u8]) -> bool,
135 {
136 self.drive(from, &mut |_| true, &mut visit)
137 }
138
139 /// Visit every block of the tree, in the order a depth-first descent meets them.
140 ///
141 /// Every block is fetched through the chunk map and its checksum verified before the
142 /// closure sees it, so a walk that completes is a statement that every block of the tree
143 /// verified. The items are bounds-checked on the way past whether or not the closure looks
144 /// at them, which is what makes this a verification pass rather than a header read.
145 ///
146 /// # Errors
147 ///
148 /// As [`for_each_item`](Self::for_each_item).
149 pub fn for_each_block<F>(&mut self, mut visit: F) -> Result<(), ReadError>
150 where
151 F: FnMut(&TreeBlock) -> bool,
152 {
153 self.drive(DiskKey::MIN, &mut visit, &mut |_, _| true)
154 }
155
156 /// The first item at or after `key`, or [`None`] where the tree holds none.
157 ///
158 /// # Errors
159 ///
160 /// As [`for_each_item`](Self::for_each_item).
161 pub fn find_first(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
162 let mut found = None;
163 self.for_each_item_from(key, |key, data| {
164 found = Some(Located {
165 key: *key,
166 data: data.to_vec(),
167 });
168 false
169 })?;
170 Ok(found)
171 }
172
173 /// The item stored under exactly `key`, or [`None`] where there is none.
174 ///
175 /// # Errors
176 ///
177 /// As [`for_each_item`](Self::for_each_item).
178 pub fn find_exact(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
179 Ok(self.find_first(key)?.filter(|found| found.key == key))
180 }
181
182 /// The last item at or before `key`, or [`None`] where every item in the tree is above it.
183 ///
184 /// The search a *range* needs, where [`find_first`](Self::find_first) is the one a *point*
185 /// needs. A record keyed by where a run begins covers everything up to the next one, so the
186 /// record covering a position is the last one at or before it — and asking for the first at
187 /// or after would find the record covering the *next* position and skip the one wanted.
188 /// That is how a file's extents are keyed, and reading from an offset in the middle of one
189 /// is the case that makes the difference visible.
190 ///
191 /// One descent, so it costs the height of the tree rather than a scan.
192 ///
193 /// # Errors
194 ///
195 /// As [`for_each_item`](Self::for_each_item).
196 pub fn find_at_or_before(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
197 let mut visited = BTreeSet::new();
198 visited.insert(self.root.bytenr);
199 let mut block = self.read_root()?;
200 let mut below = None;
201 loop {
202 if block.header().is_leaf() {
203 let at = partition(&block, &key, true)?;
204 let Some(index) = at.checked_sub(1) else {
205 return Ok(None);
206 };
207 let found = Located {
208 key: block.item(index)?.key,
209 data: block.item_data(index)?.to_vec(),
210 };
211 if index + 1 == block.count()? && below.is_some() {
212 self.confirm_last(&found.key, &key)?;
213 }
214 return Ok(Some(found));
215 }
216 let index = start_index(&block, &key)?;
217 (block, below) = self.child_of(&block, below, index, &mut visited)?;
218 }
219 }
220
221 /// Hold an answer that is the last item of its leaf, where the tree goes on past that leaf,
222 /// to the item after it.
223 ///
224 /// A descent steers by the keys a node records for its children and checks only the
225 /// children it enters. A key for the block after the one entered that sits above that
226 /// block's own first item steers a search for a key between the two into the block before,
227 /// and the answer is that block's last item — a real item, verified, and not the last at
228 /// or before the key. Stepping on to the next item enters the block after through every
229 /// guard a descent applies, which is what holds its first key to the key its parent
230 /// records for it. Only an answer that is the last item of its leaf can have been steered
231 /// that way, so only that answer pays for the step.
232 fn confirm_last(&mut self, answer: &DiskKey, key: &DiskKey) -> Result<(), ReadError> {
233 let mut next = None;
234 self.for_each_item_from(*answer, |item, _| {
235 if item == answer {
236 return true;
237 }
238 next = Some(*item);
239 false
240 })?;
241 if next.is_some_and(|next| next <= *key) {
242 return Err(ReadError::BadTreeBlock {
243 logical: self.root.bytenr,
244 fault: "a search for a key passed over an item at or before it",
245 });
246 }
247 Ok(())
248 }
249
250 /// The child at `index` of `parent`, with every guard a descent applies to one, and the
251 /// bound the child's own children sit below.
252 ///
253 /// Five of them, and each catches something the others cannot: an address already visited
254 /// is a tree that is not one, a block from another transaction than the pointer records is
255 /// not the committed one, a child that is not exactly one level below its parent is a
256 /// descent with no decreasing measure, a leaf whose items are not packed hands back one
257 /// record's bytes under another record's key, and keys out of order or out of the place
258 /// the parent's keys give them steer a search past what the tree holds. Every descent in
259 /// this module goes through here so that none of the five can be forgotten in one of them.
260 ///
261 /// `below` is the bound `parent` itself sits under — the key its own parent records for
262 /// the block after it, or none at the right edge of the tree.
263 fn child_of(
264 &mut self,
265 parent: &TreeBlock,
266 below: Option<DiskKey>,
267 index: usize,
268 visited: &mut BTreeSet<u64>,
269 ) -> Result<(TreeBlock, Option<DiskKey>), ReadError> {
270 let level = parent.header().level;
271 let pointer = parent.key_ptr(index)?;
272 let child_at = pointer.blockptr;
273 if !visited.insert(child_at) {
274 return Err(ReadError::TreeCycle { logical: child_at });
275 }
276 // The child's upper bound is the parent's key for the block after it, or, for the
277 // last child, the parent's own.
278 let child_below = if index + 1 < parent.count()? {
279 Some(parent.key_ptr(index + 1)?.key)
280 } else {
281 below
282 };
283 let child = self.volume.read_tree_block(child_at, pointer.generation)?;
284 // A child exactly one level below its parent is what makes a descent terminate
285 // whatever the addresses say, and it is a separate guard from the visited set rather
286 // than a cheaper version of it: a crafted tree can point at a fresh block at every step
287 // and still never reach a leaf.
288 if u16::from(child.header().level) + 1 != u16::from(level) {
289 return Err(ReadError::BadTreeLevel {
290 logical: child_at,
291 level: child.header().level,
292 parent: level,
293 });
294 }
295 child.check_leaf_packing()?;
296 child.check_keys(Some(pointer.key), child_below)?;
297 Ok((child, child_below))
298 }
299
300 /// How many items the tree holds, having read and verified every block on the way.
301 ///
302 /// # Errors
303 ///
304 /// As [`for_each_item`](Self::for_each_item).
305 pub fn count_items(&mut self) -> Result<u64, ReadError> {
306 let mut items = 0u64;
307 self.for_each_item(|_, _| {
308 items += 1;
309 true
310 })?;
311 Ok(items)
312 }
313
314 /// The tree's top block, checked against what the root item said it would be, and checked
315 /// as every block below it is.
316 ///
317 /// The level and the transaction are each recorded in two places — the root item and the
318 /// block's own header — and holding them against each other is what catches a root item
319 /// pointing at a block that is not the one it describes.
320 fn read_root(&mut self) -> Result<TreeBlock, ReadError> {
321 let block = self
322 .volume
323 .read_tree_block(self.root.bytenr, self.root.generation)?;
324 if block.header().level != self.root.level {
325 return Err(ReadError::BadTreeLevel {
326 logical: self.root.bytenr,
327 level: block.header().level,
328 parent: self.root.level,
329 });
330 }
331 block.check_leaf_packing()?;
332 block.check_keys(None, None)?;
333 Ok(block)
334 }
335
336 /// The one descent, which every public form above is a wrapper over.
337 ///
338 /// A depth-first walk with an explicit stack: each frame is a block and how far through it
339 /// the walk has got. A block enters the stack at the entry `from` selects, so a walk from
340 /// a key descends straight to it and a walk from [`DiskKey::MIN`] starts every block at
341 /// zero.
342 fn drive(
343 &mut self,
344 from: DiskKey,
345 on_block: &mut dyn FnMut(&TreeBlock) -> bool,
346 on_item: &mut dyn FnMut(&DiskKey, &[u8]) -> bool,
347 ) -> Result<(), ReadError> {
348 let limit = self.volume.walk_limit();
349 let mut visited = BTreeSet::new();
350 visited.insert(self.root.bytenr);
351
352 let root = self.read_root()?;
353 if !on_block(&root) {
354 return Ok(());
355 }
356 let start = start_index(&root, &from)?;
357 // Each frame is a block, how far through it the walk has got, and the bound its keys
358 // sit below. Every key a walk passes was held against its neighbours and against that
359 // bound when its block was read, so the order the items come out in is the tree's.
360 let mut stack = vec![(root, start, None)];
361 let mut visits = 0usize;
362
363 while let Some(top) = stack.len().checked_sub(1) {
364 let count = stack[top].0.count()?;
365 let index = stack[top].1;
366 if index >= count {
367 stack.pop();
368 continue;
369 }
370 stack[top].1 += 1;
371
372 if stack[top].0.header().is_leaf() {
373 let key = stack[top].0.item(index)?.key;
374 let data = stack[top].0.item_data(index)?;
375 if !on_item(&key, data) {
376 return Ok(());
377 }
378 // Counted once taken: the item that ends a range — the first record past a
379 // directory, to a listing of it — is read to find the end and is not one the
380 // range holds, so a range of exactly the cap is inside it.
381 visits += 1;
382 if visits > limit {
383 return Err(ReadError::TooManyEntries {
384 objectid: self.root.objectid,
385 limit,
386 });
387 }
388 continue;
389 }
390
391 let (child, below) = {
392 let (parent, _, below) = &stack[top];
393 self.child_of(parent, *below, index, &mut visited)?
394 };
395 if !on_block(&child) {
396 return Ok(());
397 }
398 let start = start_index(&child, &from)?;
399 stack.push((child, start, below));
400 }
401 Ok(())
402 }
403}
404
405/// Where in `block` a walk from `from` begins.
406///
407/// For a **leaf** it is the first item at or after the key, so items below it are skipped. For
408/// a **node** it is the last child whose key is at or below it, since that child's subtree is
409/// where the key would be — and a node whose every key is above `from` starts at its first
410/// child.
411///
412/// Computed for every block rather than only for the leftmost path, which is the same answer
413/// and one fewer piece of state: a block entirely above `from` has no key at or below it, so
414/// the binary search lands on zero on its own.
415///
416/// The search is bounded whatever the block holds, so a block whose keys are not sorted
417/// answers with a wrong index and never with one outside the block. That a block is sorted is
418/// checked when a descent reaches it, before any search over it.
419fn start_index(block: &TreeBlock, from: &DiskKey) -> Result<usize, ReadError> {
420 if *from == DiskKey::MIN {
421 return Ok(0);
422 }
423 // A leaf counts the entries strictly below the key, since that is the first one to visit.
424 // A node counts those at or below it and steps back one, to the child whose subtree is
425 // where the key would be — and a node whose every key is above `from` steps back from
426 // zero, which is its first child.
427 let leaf = block.header().is_leaf();
428 let at = partition(block, from, !leaf)?;
429 Ok(if leaf { at } else { at.saturating_sub(1) })
430}
431
432/// How many of `block`'s entries sort below `from`, counting one equal to it where `inclusive`.
433///
434/// The one binary search over a block, in the two readings a descent needs of it. It is bounded
435/// whatever the block holds, so a block whose keys are not sorted answers with a wrong index
436/// and never with one outside the block. That a block is sorted is checked when a descent
437/// reaches it, before any search over it.
438fn partition(block: &TreeBlock, from: &DiskKey, inclusive: bool) -> Result<usize, ReadError> {
439 let leaf = block.header().is_leaf();
440 let (mut lo, mut hi) = (0usize, block.count()?);
441 while lo < hi {
442 let mid = lo + (hi - lo) / 2;
443 let key = if leaf {
444 block.item(mid)?.key
445 } else {
446 block.key_ptr(mid)?.key
447 };
448 let below = if inclusive { key <= *from } else { key < *from };
449 if below { lo = mid + 1 } else { hi = mid }
450 }
451 Ok(lo)
452}
453
454#[cfg(test)]
455mod tests {
456 use super::*;
457 use crate::btrfs::forge::{
458 CHUNK_LENGTH, CHUNK_LOGICAL, FIRST_FREE_AT, Forge, NODE_SIZE, ROOT_TREE_AT, leaf, node,
459 seal,
460 };
461 use crate::btrfs::ondisk::{Header, Item, ItemType, objectid};
462 use crate::{Limits, OpenOptions};
463
464 /// A key in the root tree's own namespace, so a forged tree sorts the way a real one does.
465 fn key(n: u64) -> DiskKey {
466 DiskKey::new(n, ItemType::ROOT_ITEM, 0)
467 }
468
469 /// A leaf of `n` items, each carrying its own number as a byte.
470 fn items(range: std::ops::Range<u64>) -> Vec<(DiskKey, Vec<u8>)> {
471 range.map(|n| (key(n), vec![n as u8; 8])).collect()
472 }
473
474 /// Every key a walk of `forge`'s root tree visits.
475 fn walk(forge: &Forge) -> Result<Vec<DiskKey>, ReadError> {
476 let mut volume = Volume::open(forge.source())?;
477 let root = volume.root_tree();
478 let mut keys = Vec::new();
479 volume.tree(root).for_each_item(|k, _| {
480 keys.push(*k);
481 true
482 })?;
483 Ok(keys)
484 }
485
486 #[test]
487 fn a_walk_visits_every_item_of_a_tree_in_key_order() {
488 let mut forge = Forge::new();
489 forge.root_leaf(&items(1..40));
490 assert_eq!(
491 walk(&forge).expect("a well-formed tree"),
492 items(1..40).iter().map(|(k, _)| *k).collect::<Vec<_>>()
493 );
494 }
495
496 #[test]
497 fn a_walk_descends_through_a_node_and_reaches_every_leaf_below_it() {
498 // Two leaves under one node, which is the smallest tree that exercises a descent at
499 // all — a one-leaf tree never reads a child pointer.
500 let mut forge = Forge::new();
501 let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
502 forge
503 .block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
504 .block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
505 .root_node(1, &[(key(1), left), (key(10), right)]);
506 assert_eq!(walk(&forge).expect("a well-formed tree").len(), 19);
507 }
508
509 #[test]
510 fn a_seek_lands_where_a_walk_of_the_whole_tree_would_have_reached() {
511 // The property the descent's start index exists for, over a tree deep enough that the
512 // choice of child matters. Every key present is probed, and so is one below and one
513 // above each — the three places an off-by-one in the binary search would show.
514 let mut forge = Forge::new();
515 let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
516 forge
517 .block(left, &leaf(left, objectid::ROOT_TREE, &items(10..20)))
518 .block(right, &leaf(right, objectid::ROOT_TREE, &items(20..30)))
519 .root_node(1, &[(key(10), left), (key(20), right)]);
520
521 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
522 let root = volume.root_tree();
523 let all: Vec<DiskKey> = (10..30).map(key).collect();
524 for probe in (5..35).map(key) {
525 let expected: Vec<DiskKey> = all.iter().copied().filter(|k| *k >= probe).collect();
526 let mut got = Vec::new();
527 volume
528 .tree(root)
529 .for_each_item_from(probe, |k, _| {
530 got.push(*k);
531 true
532 })
533 .expect("a well-formed tree");
534 assert_eq!(got, expected, "seeking to {probe:?}");
535 assert_eq!(
536 volume
537 .tree(root)
538 .find_first(probe)
539 .expect("search")
540 .map(|f| f.key),
541 expected.first().copied()
542 );
543 }
544 // And the exact form answers only where the key is genuinely there.
545 assert!(
546 volume
547 .tree(root)
548 .find_exact(key(15))
549 .expect("search")
550 .is_some()
551 );
552 assert!(
553 volume
554 .tree(root)
555 .find_exact(key(35))
556 .expect("search")
557 .is_none()
558 );
559 }
560
561 #[test]
562 fn a_block_reached_twice_is_a_tree_that_is_not_one() {
563 // Two child pointers naming one leaf. Not a cycle in the strict sense and the same
564 // defect: a walk would visit its items twice, and the key-order check would then fire
565 // for a reason that says nothing about what is wrong.
566 let mut forge = Forge::new();
567 let leaf_at = FIRST_FREE_AT;
568 forge
569 .block(leaf_at, &leaf(leaf_at, objectid::ROOT_TREE, &items(1..10)))
570 .root_node(1, &[(key(1), leaf_at), (key(10), leaf_at)]);
571 assert!(matches!(
572 walk(&forge),
573 Err(ReadError::TreeCycle { logical }) if logical == leaf_at
574 ));
575
576 // And a node naming itself, which the same guard catches before the block is read at
577 // all — the root's own address is in the visited set from the start.
578 let mut forge = Forge::new();
579 forge.root_node(1, &[(key(1), ROOT_TREE_AT)]);
580 assert!(matches!(
581 walk(&forge),
582 Err(ReadError::TreeCycle { logical }) if logical == ROOT_TREE_AT
583 ));
584 }
585
586 #[test]
587 fn a_child_that_is_not_one_level_below_its_parent_is_refused() {
588 // The guard that makes a descent terminate whatever the addresses say: a crafted tree
589 // can name a fresh block at every step, so the visited set alone is not a bound.
590 for child_level in [0u8, 2, 3] {
591 if child_level == 1 {
592 continue;
593 }
594 let mut forge = Forge::new();
595 let child = FIRST_FREE_AT;
596 let block = if child_level == 0 {
597 leaf(child, objectid::ROOT_TREE, &items(1..4))
598 } else {
599 node(
600 child,
601 objectid::ROOT_TREE,
602 child_level,
603 &[(key(1), FIRST_FREE_AT + NODE_SIZE as u64)],
604 )
605 };
606 forge.block(child, &block).root_node(2, &[(key(1), child)]);
607 match walk(&forge) {
608 Err(ReadError::BadTreeLevel { level, parent, .. }) => {
609 assert_eq!((level, parent), (child_level, 2));
610 }
611 other => panic!("a level-{child_level} child under a level-2 node: {other:?}"),
612 }
613 }
614 }
615
616 #[test]
617 fn a_root_block_that_is_not_the_height_its_root_item_claimed_is_refused() {
618 // The level is recorded twice — in the root item and in the block's own header — and
619 // holding them against each other is what catches a root item pointing at a block
620 // that is not the one it describes.
621 let mut forge = Forge::new();
622 forge.root_leaf(&items(1..4));
623 forge.amend_superblock(0, |sb| sb.root_level = 1);
624 assert!(matches!(
625 walk(&forge),
626 Err(ReadError::BadTreeLevel {
627 level: 0,
628 parent: 1,
629 ..
630 })
631 ));
632 }
633
634 #[test]
635 fn a_header_that_does_not_describe_the_block_it_sits_in_is_refused() {
636 // Three claims a header makes about its own block, each checked against something
637 // outside the header. None is a fault a checksum can catch: every one of these fields
638 // is inside what the checksum covers, so a block written correctly somewhere else, or
639 // for another filesystem, verifies perfectly.
640 //
641 // They are one gate because the damage differs and nothing else does — the crafted
642 // block, the walk, and the shape of the refusal are the same three lines in each.
643 /// What a row damages about a header, and the word its refusal must carry.
644 type Fault = (&'static str, Box<dyn Fn(&mut Header)>);
645
646 let faults: [Fault; 3] = [
647 (
648 "room",
649 Box::new(|header: &mut Header| {
650 header.nritems = (NODE_SIZE / Item::SIZE + 1) as u32;
651 }),
652 ),
653 (
654 "logical address",
655 Box::new(|header: &mut Header| header.bytenr = CHUNK_LOGICAL),
656 ),
657 (
658 "another filesystem",
659 Box::new(|header: &mut Header| header.fsid = [0x99; 16]),
660 ),
661 ];
662 for (expected, damage) in faults {
663 let mut forge = Forge::new();
664 forge.root_leaf(&items(1..4));
665 forge.amend(ROOT_TREE_AT, |block| {
666 let mut header = Header::read_from(block).expect("a header");
667 damage(&mut header);
668 header.write_to(block);
669 });
670 match walk(&forge) {
671 Err(ReadError::BadTreeBlock { fault, .. }) => {
672 assert!(fault.contains(expected), "{fault}");
673 }
674 other => panic!("a header claiming the wrong {expected}: {other:?}"),
675 }
676 }
677 }
678
679 #[test]
680 fn an_item_whose_data_escapes_its_leaf_is_refused_in_both_directions() {
681 // Asked of the block directly rather than through a walk, and deliberately: a walk
682 // checks the leaf's packing before it reads an item, and packing already implies an
683 // item cannot end past the block. What it does not imply is that the data stays out
684 // of the array describing it — and a caller holding a block from `read_block` has had
685 // neither check made for it, which is the path these two guards are on.
686 /// What a row damages about an item, and the word its refusal must carry.
687 type Escape = (&'static str, Box<dyn Fn(&mut Item)>);
688
689 let cases: [Escape; 3] = [
690 ("array", Box::new(|item: &mut Item| item.offset = 0)),
691 (
692 "block",
693 Box::new(|item: &mut Item| item.size = NODE_SIZE as u32),
694 ),
695 (
696 "block",
697 Box::new(|item: &mut Item| {
698 item.offset = u32::MAX;
699 item.size = u32::MAX;
700 }),
701 ),
702 ];
703 for (expected, damage) in cases {
704 let mut forge = Forge::new();
705 forge.root_leaf(&items(1..4));
706 forge.amend(ROOT_TREE_AT, |block| {
707 let mut item = Item::read_from(&block[Header::SIZE..]).expect("an item");
708 damage(&mut item);
709 item.write_to(&mut block[Header::SIZE..]);
710 });
711 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
712 let block = volume.read_block(ROOT_TREE_AT).expect("the block verifies");
713 match block.item_data(0) {
714 Err(ReadError::BadItem {
715 fault, index: 0, ..
716 }) => {
717 assert!(fault.contains(expected), "{fault}");
718 }
719 other => panic!("an item escaping its leaf toward the {expected}: {other:?}"),
720 }
721 }
722 }
723
724 #[test]
725 fn a_leaf_whose_data_has_been_moved_with_its_offsets_is_refused() {
726 // Every item stays inside the block and every item points at bytes that are not its
727 // own, so no bound notices — what does is the format's own packing rule, that one
728 // item's data ends where the next one's begins. The baseline's corruptor has a switch
729 // for exactly this shape, and it is what found the check missing.
730 let mut forge = Forge::new();
731 forge.root_leaf(&items(1..6));
732 forge.amend(ROOT_TREE_AT, |block| {
733 let at = Header::SIZE + 2 * Item::SIZE;
734 let mut third = Item::read_from(&block[at..]).expect("an item");
735 third.offset -= 16;
736 third.write_to(&mut block[at..]);
737 });
738 assert!(matches!(
739 walk(&forge),
740 Err(ReadError::BadItem { fault, index: 2, .. })
741 if fault.contains("does not end where the item before it begins")
742 ));
743
744 // And the first item is bounded by the end of the block rather than by a neighbour,
745 // which is the case a rule written only about neighbours would miss.
746 let mut forge = Forge::new();
747 forge.root_leaf(&items(1..6));
748 forge.amend(ROOT_TREE_AT, |block| {
749 let mut first = Item::read_from(&block[Header::SIZE..]).expect("an item");
750 first.size -= 1;
751 first.write_to(&mut block[Header::SIZE..]);
752 });
753 assert!(matches!(
754 walk(&forge),
755 Err(ReadError::BadItem { index: 0, .. })
756 ));
757 }
758
759 #[test]
760 fn a_block_from_another_transaction_than_its_pointer_records_is_refused() {
761 use crate::btrfs::forge::GENERATION;
762 use crate::btrfs::ondisk::KeyPtr;
763
764 // The root block of a tree records another transaction than the root item does. Its
765 // checksum, its address and its filesystem all verify, which is exactly what a block
766 // left at an address since written again looks like.
767 let mut forge = Forge::new();
768 forge.root_leaf(&items(1..6));
769 forge.amend(ROOT_TREE_AT, |block| {
770 let mut header = Header::read_from(block).expect("a header");
771 header.generation = 9999;
772 header.write_to(block);
773 });
774 assert!(matches!(
775 walk(&forge),
776 Err(ReadError::WrongGeneration { logical, generation: 9999, expected })
777 if logical == ROOT_TREE_AT && expected == GENERATION
778 ));
779
780 // A parent's pointer records another transaction than the child carries. The walk and
781 // both forms of lookup reach the child through that pointer, and each refuses it.
782 let mut forge = Forge::new();
783 let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
784 forge
785 .block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
786 .block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
787 .root_node(1, &[(key(1), left), (key(10), right)]);
788 forge.amend(ROOT_TREE_AT, |block| {
789 let at = Header::SIZE + KeyPtr::SIZE;
790 let mut pointer = KeyPtr::read_from(&block[at..]).expect("a pointer");
791 pointer.generation = 9999;
792 pointer.write_to(&mut block[at..]);
793 });
794 let stale = |r: Result<_, ReadError>| {
795 matches!(
796 r,
797 Err(ReadError::WrongGeneration { logical, generation, expected: 9999 })
798 if logical == right && generation == GENERATION
799 )
800 };
801 assert!(stale(walk(&forge).map(|_| ())));
802 let mut volume = Volume::open(forge.source()).expect("the filesystem opens");
803 let root = volume.root_tree();
804 assert!(stale(volume.tree(root).find_first(key(15)).map(|_| ())));
805 assert!(stale(
806 volume.tree(root).find_at_or_before(key(15)).map(|_| ())
807 ));
808 // The left child's pointer is sound, and what sits under it still reads.
809 assert!(
810 volume
811 .tree(root)
812 .find_exact(key(5))
813 .expect("search")
814 .is_some()
815 );
816 }
817
818 #[test]
819 fn a_node_key_that_does_not_match_the_block_it_leads_to_is_refused_on_every_path() {
820 // A node's keys are what a search steers by, and a checksum covers a wrong one as
821 // faithfully as a right one. A walk of every block in order meets every item whatever
822 // the node's keys say, so a check made only where a walk passes each item certifies a
823 // tree whose lookups miss what it holds. Each shape here is refused by the walk and by
824 // both forms of lookup alike.
825 let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
826 // Each shape, and a key whose lookup reaches the block at fault.
827 type Shape = (&'static str, std::ops::Range<u64>, [DiskKey; 2], DiskKey);
828 let shapes: [Shape; 4] = [
829 (
830 "the node's keys are out of order",
831 1..10,
832 [key(10), DiskKey::MIN],
833 key(15),
834 ),
835 (
836 "the key for the right child is below its first key",
837 1..10,
838 [key(1), key(9)],
839 key(15),
840 ),
841 (
842 "the key for the right child is above its first key",
843 1..10,
844 [key(1), key(11)],
845 key(15),
846 ),
847 (
848 "the left child reaches the key the node records for the right one",
849 1..12,
850 [key(1), key(10)],
851 key(5),
852 ),
853 ];
854 for (what, left_items, [first, second], reaches) in shapes {
855 let held: Vec<u64> = left_items.clone().chain(10..20).collect();
856 let mut forge = Forge::new();
857 forge
858 .block(left, &leaf(left, objectid::ROOT_TREE, &items(left_items)))
859 .block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
860 .root_node(1, &[(first, left), (second, right)]);
861 let refused =
862 |r: Result<(), ReadError>| matches!(r, Err(ReadError::BadTreeBlock { .. }));
863 assert!(refused(walk(&forge).map(|_| ())), "{what}: the walk");
864 let mut volume = Volume::open(forge.source()).expect("the filesystem opens");
865 let root = volume.root_tree();
866 for probe in [5, 10, 15] {
867 // A lookup that steers clear of the faulty child is a lookup the fault does
868 // not affect, and answers what the tree holds; one that reaches it must refuse
869 // it, never answer from it. An answer is held to the items the blocks hold, so
870 // a lookup the wrong key steers past an item answers wrongly and fails here.
871 let truths = [
872 (
873 "find_first",
874 held.iter().copied().filter(|n| *n >= probe).min(),
875 ),
876 (
877 "find_at_or_before",
878 held.iter().copied().filter(|n| *n <= probe).max(),
879 ),
880 ];
881 for (form, truth) in truths {
882 let answer = if form == "find_first" {
883 volume.tree(root).find_first(key(probe))
884 } else {
885 volume.tree(root).find_at_or_before(key(probe))
886 };
887 match answer {
888 Ok(found) => assert_eq!(
889 found.map(|located| located.key),
890 truth.map(key),
891 "{what}: {form} {probe} answered other than the tree holds"
892 ),
893 Err(e) => assert!(
894 refused(Err(e)),
895 "{what}: {form} {probe} failed some other way"
896 ),
897 }
898 }
899 }
900 assert!(
901 refused(volume.tree(root).find_first(reaches).map(|_| ())),
902 "{what}: a lookup that reaches the block at fault"
903 );
904 }
905
906 // The control: the same tree with the node's keys each the first key of the block it
907 // leads to, read whole and searched, agrees with itself.
908 let mut forge = Forge::new();
909 forge
910 .block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
911 .block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
912 .root_node(1, &[(key(1), left), (key(10), right)]);
913 assert_eq!(walk(&forge).expect("a well-formed tree").len(), 19);
914 }
915
916 #[test]
917 fn a_tree_whose_keys_are_not_in_order_is_refused_rather_than_searched_wrongly() {
918 // A binary search over unsorted keys silently misses items instead of failing, so a
919 // block whose keys are not sorted is refused when a descent reaches it, before any
920 // search over it.
921 let mut forge = Forge::new();
922 forge.root_leaf(&items(1..6));
923 forge.amend(ROOT_TREE_AT, |block| {
924 let mut second = Item::read_from(&block[Header::SIZE + Item::SIZE..]).expect("an item");
925 second.key = key(0);
926 second.write_to(&mut block[Header::SIZE + Item::SIZE..]);
927 });
928 assert!(matches!(
929 walk(&forge),
930 Err(ReadError::BadTreeBlock { fault, .. }) if fault.contains("above the one before")
931 ));
932
933 // Two items under one key is the same defect at its boundary: a tree's keys are
934 // unique, and a search that found one of them would never see the other.
935 let mut forge = Forge::new();
936 forge.root_leaf(&[(key(1), vec![1; 8]), (key(1), vec![2; 8])]);
937 assert!(matches!(walk(&forge), Err(ReadError::BadTreeBlock { .. })));
938 }
939
940 #[test]
941 fn a_block_whose_checksum_no_longer_covers_it_is_refused_wherever_it_sits() {
942 for at in [ROOT_TREE_AT, CHUNK_LOGICAL] {
943 let mut forge = Forge::new();
944 forge.root_leaf(&items(1..4));
945 forge.break_checksum(at);
946 let opened = Volume::open(forge.source()).and_then(|mut v| {
947 let root = v.root_tree();
948 v.tree(root).count_items()
949 });
950 assert!(
951 matches!(
952 &opened,
953 Err(ReadError::BadChecksum {
954 object: "tree block",
955 ..
956 })
957 ),
958 "a damaged block at {at}: {opened:?}"
959 );
960 }
961 }
962
963 #[test]
964 fn a_block_at_an_address_no_chunk_maps_is_refused_rather_than_read_from_nowhere() {
965 let mut forge = Forge::new();
966 forge.root_leaf(&items(1..4));
967 // Past the end of the one chunk, which is the address space this filesystem has.
968 forge.amend_superblock(0, |sb| sb.root = CHUNK_LOGICAL + CHUNK_LENGTH);
969 assert!(matches!(
970 walk(&forge),
971 Err(ReadError::UnmappedLogical { .. })
972 ));
973 }
974
975 #[test]
976 fn a_walk_stops_at_the_cap_the_caller_set_rather_than_gathering_past_it() {
977 let mut forge = Forge::new();
978 forge.root_leaf(&items(1..40));
979 let options = OpenOptions::new().limits(Limits::new().max_walk_entries(10));
980 let mut volume =
981 Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
982 let root = volume.root_tree();
983 assert!(matches!(
984 volume.tree(root).count_items(),
985 Err(ReadError::TooManyEntries { limit: 10, .. })
986 ));
987 // Exactly at the cap is inside it: a bound that refused the last entry it allowed
988 // would be off by one in the direction that refuses healthy filesystems.
989 let options = OpenOptions::new().limits(Limits::new().max_walk_entries(39));
990 let mut volume =
991 Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
992 let root = volume.root_tree();
993 assert_eq!(volume.tree(root).count_items().expect("within the cap"), 39);
994 // The item that ends a range is not one the range takes: a visit that takes exactly
995 // the cap's worth and declines the next — a directory listing meeting the first record
996 // past the directory — is inside the cap, and one that takes the next is past it.
997 let options = OpenOptions::new().limits(Limits::new().max_walk_entries(10));
998 let mut volume =
999 Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
1000 let root = volume.root_tree();
1001 let mut taken = 0;
1002 volume
1003 .tree(root)
1004 .for_each_item(|_, _| {
1005 if taken == 10 {
1006 return false;
1007 }
1008 taken += 1;
1009 true
1010 })
1011 .expect("ten taken, and the eleventh declined");
1012 assert_eq!(taken, 10);
1013 let mut taken = 0;
1014 assert!(matches!(
1015 volume.tree(root).for_each_item(|_, _| {
1016 taken += 1;
1017 taken <= 11
1018 }),
1019 Err(ReadError::TooManyEntries { limit: 10, .. })
1020 ));
1021 }
1022
1023 #[test]
1024 fn a_visit_that_says_to_stop_stops_where_it_said() {
1025 let mut forge = Forge::new();
1026 forge.root_leaf(&items(1..40));
1027 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
1028 let root = volume.root_tree();
1029 let mut seen = 0;
1030 volume
1031 .tree(root)
1032 .for_each_item(|_, _| {
1033 seen += 1;
1034 seen < 3
1035 })
1036 .expect("a well-formed tree");
1037 assert_eq!(seen, 3);
1038 }
1039
1040 #[test]
1041 fn every_block_of_a_tree_is_offered_to_a_block_walk_including_its_nodes() {
1042 let mut forge = Forge::new();
1043 let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
1044 forge
1045 .block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
1046 .block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
1047 .root_node(1, &[(key(1), left), (key(10), right)]);
1048 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
1049 let root = volume.root_tree();
1050 let mut blocks = Vec::new();
1051 volume
1052 .tree(root)
1053 .for_each_block(|block| {
1054 blocks.push((block.header().bytenr, block.header().level));
1055 true
1056 })
1057 .expect("a well-formed tree");
1058 assert_eq!(blocks, vec![(ROOT_TREE_AT, 1), (left, 0), (right, 0)]);
1059 }
1060
1061 #[test]
1062 fn a_forged_filesystem_is_one_the_reader_accepts_before_it_is_damaged() {
1063 // What makes every gate above a negative control rather than a test of a broken
1064 // fixture: the same filesystem, undamaged, opens and reads.
1065 let mut forge = Forge::new();
1066 forge.root_leaf(&items(1..40));
1067 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
1068 assert_eq!(volume.superblock().nodesize as usize, NODE_SIZE);
1069 assert_eq!(volume.chunk_map().len(), 1);
1070 let root = volume.root_tree();
1071 assert_eq!(
1072 volume.tree(root).count_items().expect("a well-formed tree"),
1073 39
1074 );
1075 // And the seal the forge applies is the format's own recipe, not a second spelling of
1076 // it: a block resealed by hand verifies exactly as one the forge wrote does.
1077 let mut block = leaf(FIRST_FREE_AT, objectid::ROOT_TREE, &items(1..4));
1078 block[Header::SIZE] ^= 0xff;
1079 seal(&mut block);
1080 forge.block(FIRST_FREE_AT, &block);
1081 let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
1082 assert!(volume.read_block(FIRST_FREE_AT).is_ok());
1083 }
1084}