Skip to main content

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}