use std::collections::BTreeSet;
use std::io::{Read, Seek};
use super::ondisk::DiskKey;
use super::volume::{ReadError, TreeBlock, TreeRoot, Volume};
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Located {
pub key: DiskKey,
pub data: Vec<u8>,
}
pub(super) fn levels_above(leaves: u64, fan_out: u64) -> Vec<u64> {
let fan_out = fan_out.max(2);
let mut levels = Vec::new();
let mut width = leaves;
while width > 1 {
width = width.div_ceil(fan_out);
levels.push(width);
}
levels
}
pub struct Tree<'a, R> {
volume: &'a mut Volume<R>,
root: TreeRoot,
}
impl<'a, R: Read + Seek> Tree<'a, R> {
pub(super) fn new(volume: &'a mut Volume<R>, root: TreeRoot) -> Self {
Self { volume, root }
}
#[must_use]
pub fn root(&self) -> TreeRoot {
self.root
}
pub fn for_each_item<F>(&mut self, mut visit: F) -> Result<(), ReadError>
where
F: FnMut(&DiskKey, &[u8]) -> bool,
{
self.drive(DiskKey::MIN, &mut |_| true, &mut visit)
}
pub fn for_each_item_from<F>(&mut self, from: DiskKey, mut visit: F) -> Result<(), ReadError>
where
F: FnMut(&DiskKey, &[u8]) -> bool,
{
self.drive(from, &mut |_| true, &mut visit)
}
pub fn for_each_block<F>(&mut self, mut visit: F) -> Result<(), ReadError>
where
F: FnMut(&TreeBlock) -> bool,
{
self.drive(DiskKey::MIN, &mut visit, &mut |_, _| true)
}
pub fn find_first(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
let mut found = None;
self.for_each_item_from(key, |key, data| {
found = Some(Located {
key: *key,
data: data.to_vec(),
});
false
})?;
Ok(found)
}
pub fn find_exact(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
Ok(self.find_first(key)?.filter(|found| found.key == key))
}
pub fn find_at_or_before(&mut self, key: DiskKey) -> Result<Option<Located>, ReadError> {
let mut visited = BTreeSet::new();
visited.insert(self.root.bytenr);
let mut block = self.read_root()?;
let mut below = None;
loop {
if block.header().is_leaf() {
let at = partition(&block, &key, true)?;
let Some(index) = at.checked_sub(1) else {
return Ok(None);
};
let found = Located {
key: block.item(index)?.key,
data: block.item_data(index)?.to_vec(),
};
if index + 1 == block.count()? && below.is_some() {
self.confirm_last(&found.key, &key)?;
}
return Ok(Some(found));
}
let index = start_index(&block, &key)?;
(block, below) = self.child_of(&block, below, index, &mut visited)?;
}
}
fn confirm_last(&mut self, answer: &DiskKey, key: &DiskKey) -> Result<(), ReadError> {
let mut next = None;
self.for_each_item_from(*answer, |item, _| {
if item == answer {
return true;
}
next = Some(*item);
false
})?;
if next.is_some_and(|next| next <= *key) {
return Err(ReadError::BadTreeBlock {
logical: self.root.bytenr,
fault: "a search for a key passed over an item at or before it",
});
}
Ok(())
}
fn child_of(
&mut self,
parent: &TreeBlock,
below: Option<DiskKey>,
index: usize,
visited: &mut BTreeSet<u64>,
) -> Result<(TreeBlock, Option<DiskKey>), ReadError> {
let level = parent.header().level;
let pointer = parent.key_ptr(index)?;
let child_at = pointer.blockptr;
if !visited.insert(child_at) {
return Err(ReadError::TreeCycle { logical: child_at });
}
let child_below = if index + 1 < parent.count()? {
Some(parent.key_ptr(index + 1)?.key)
} else {
below
};
let child = self.volume.read_tree_block(child_at, pointer.generation)?;
if u16::from(child.header().level) + 1 != u16::from(level) {
return Err(ReadError::BadTreeLevel {
logical: child_at,
level: child.header().level,
parent: level,
});
}
child.check_leaf_packing()?;
child.check_keys(Some(pointer.key), child_below)?;
Ok((child, child_below))
}
pub fn count_items(&mut self) -> Result<u64, ReadError> {
let mut items = 0u64;
self.for_each_item(|_, _| {
items += 1;
true
})?;
Ok(items)
}
fn read_root(&mut self) -> Result<TreeBlock, ReadError> {
let block = self
.volume
.read_tree_block(self.root.bytenr, self.root.generation)?;
if block.header().level != self.root.level {
return Err(ReadError::BadTreeLevel {
logical: self.root.bytenr,
level: block.header().level,
parent: self.root.level,
});
}
block.check_leaf_packing()?;
block.check_keys(None, None)?;
Ok(block)
}
fn drive(
&mut self,
from: DiskKey,
on_block: &mut dyn FnMut(&TreeBlock) -> bool,
on_item: &mut dyn FnMut(&DiskKey, &[u8]) -> bool,
) -> Result<(), ReadError> {
let limit = self.volume.walk_limit();
let mut visited = BTreeSet::new();
visited.insert(self.root.bytenr);
let root = self.read_root()?;
if !on_block(&root) {
return Ok(());
}
let start = start_index(&root, &from)?;
let mut stack = vec![(root, start, None)];
let mut visits = 0usize;
while let Some(top) = stack.len().checked_sub(1) {
let count = stack[top].0.count()?;
let index = stack[top].1;
if index >= count {
stack.pop();
continue;
}
stack[top].1 += 1;
if stack[top].0.header().is_leaf() {
let key = stack[top].0.item(index)?.key;
let data = stack[top].0.item_data(index)?;
if !on_item(&key, data) {
return Ok(());
}
visits += 1;
if visits > limit {
return Err(ReadError::TooManyEntries {
objectid: self.root.objectid,
limit,
});
}
continue;
}
let (child, below) = {
let (parent, _, below) = &stack[top];
self.child_of(parent, *below, index, &mut visited)?
};
if !on_block(&child) {
return Ok(());
}
let start = start_index(&child, &from)?;
stack.push((child, start, below));
}
Ok(())
}
}
fn start_index(block: &TreeBlock, from: &DiskKey) -> Result<usize, ReadError> {
if *from == DiskKey::MIN {
return Ok(0);
}
let leaf = block.header().is_leaf();
let at = partition(block, from, !leaf)?;
Ok(if leaf { at } else { at.saturating_sub(1) })
}
fn partition(block: &TreeBlock, from: &DiskKey, inclusive: bool) -> Result<usize, ReadError> {
let leaf = block.header().is_leaf();
let (mut lo, mut hi) = (0usize, block.count()?);
while lo < hi {
let mid = lo + (hi - lo) / 2;
let key = if leaf {
block.item(mid)?.key
} else {
block.key_ptr(mid)?.key
};
let below = if inclusive { key <= *from } else { key < *from };
if below { lo = mid + 1 } else { hi = mid }
}
Ok(lo)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::btrfs::forge::{
CHUNK_LENGTH, CHUNK_LOGICAL, FIRST_FREE_AT, Forge, NODE_SIZE, ROOT_TREE_AT, leaf, node,
seal,
};
use crate::btrfs::ondisk::{Header, Item, ItemType, objectid};
use crate::{Limits, OpenOptions};
fn key(n: u64) -> DiskKey {
DiskKey::new(n, ItemType::ROOT_ITEM, 0)
}
fn items(range: std::ops::Range<u64>) -> Vec<(DiskKey, Vec<u8>)> {
range.map(|n| (key(n), vec![n as u8; 8])).collect()
}
fn walk(forge: &Forge) -> Result<Vec<DiskKey>, ReadError> {
let mut volume = Volume::open(forge.source())?;
let root = volume.root_tree();
let mut keys = Vec::new();
volume.tree(root).for_each_item(|k, _| {
keys.push(*k);
true
})?;
Ok(keys)
}
#[test]
fn a_walk_visits_every_item_of_a_tree_in_key_order() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..40));
assert_eq!(
walk(&forge).expect("a well-formed tree"),
items(1..40).iter().map(|(k, _)| *k).collect::<Vec<_>>()
);
}
#[test]
fn a_walk_descends_through_a_node_and_reaches_every_leaf_below_it() {
let mut forge = Forge::new();
let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
.root_node(1, &[(key(1), left), (key(10), right)]);
assert_eq!(walk(&forge).expect("a well-formed tree").len(), 19);
}
#[test]
fn a_seek_lands_where_a_walk_of_the_whole_tree_would_have_reached() {
let mut forge = Forge::new();
let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(10..20)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(20..30)))
.root_node(1, &[(key(10), left), (key(20), right)]);
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
let root = volume.root_tree();
let all: Vec<DiskKey> = (10..30).map(key).collect();
for probe in (5..35).map(key) {
let expected: Vec<DiskKey> = all.iter().copied().filter(|k| *k >= probe).collect();
let mut got = Vec::new();
volume
.tree(root)
.for_each_item_from(probe, |k, _| {
got.push(*k);
true
})
.expect("a well-formed tree");
assert_eq!(got, expected, "seeking to {probe:?}");
assert_eq!(
volume
.tree(root)
.find_first(probe)
.expect("search")
.map(|f| f.key),
expected.first().copied()
);
}
assert!(
volume
.tree(root)
.find_exact(key(15))
.expect("search")
.is_some()
);
assert!(
volume
.tree(root)
.find_exact(key(35))
.expect("search")
.is_none()
);
}
#[test]
fn a_block_reached_twice_is_a_tree_that_is_not_one() {
let mut forge = Forge::new();
let leaf_at = FIRST_FREE_AT;
forge
.block(leaf_at, &leaf(leaf_at, objectid::ROOT_TREE, &items(1..10)))
.root_node(1, &[(key(1), leaf_at), (key(10), leaf_at)]);
assert!(matches!(
walk(&forge),
Err(ReadError::TreeCycle { logical }) if logical == leaf_at
));
let mut forge = Forge::new();
forge.root_node(1, &[(key(1), ROOT_TREE_AT)]);
assert!(matches!(
walk(&forge),
Err(ReadError::TreeCycle { logical }) if logical == ROOT_TREE_AT
));
}
#[test]
fn a_child_that_is_not_one_level_below_its_parent_is_refused() {
for child_level in [0u8, 2, 3] {
if child_level == 1 {
continue;
}
let mut forge = Forge::new();
let child = FIRST_FREE_AT;
let block = if child_level == 0 {
leaf(child, objectid::ROOT_TREE, &items(1..4))
} else {
node(
child,
objectid::ROOT_TREE,
child_level,
&[(key(1), FIRST_FREE_AT + NODE_SIZE as u64)],
)
};
forge.block(child, &block).root_node(2, &[(key(1), child)]);
match walk(&forge) {
Err(ReadError::BadTreeLevel { level, parent, .. }) => {
assert_eq!((level, parent), (child_level, 2));
}
other => panic!("a level-{child_level} child under a level-2 node: {other:?}"),
}
}
}
#[test]
fn a_root_block_that_is_not_the_height_its_root_item_claimed_is_refused() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..4));
forge.amend_superblock(0, |sb| sb.root_level = 1);
assert!(matches!(
walk(&forge),
Err(ReadError::BadTreeLevel {
level: 0,
parent: 1,
..
})
));
}
#[test]
fn a_header_that_does_not_describe_the_block_it_sits_in_is_refused() {
type Fault = (&'static str, Box<dyn Fn(&mut Header)>);
let faults: [Fault; 3] = [
(
"room",
Box::new(|header: &mut Header| {
header.nritems = (NODE_SIZE / Item::SIZE + 1) as u32;
}),
),
(
"logical address",
Box::new(|header: &mut Header| header.bytenr = CHUNK_LOGICAL),
),
(
"another filesystem",
Box::new(|header: &mut Header| header.fsid = [0x99; 16]),
),
];
for (expected, damage) in faults {
let mut forge = Forge::new();
forge.root_leaf(&items(1..4));
forge.amend(ROOT_TREE_AT, |block| {
let mut header = Header::read_from(block).expect("a header");
damage(&mut header);
header.write_to(block);
});
match walk(&forge) {
Err(ReadError::BadTreeBlock { fault, .. }) => {
assert!(fault.contains(expected), "{fault}");
}
other => panic!("a header claiming the wrong {expected}: {other:?}"),
}
}
}
#[test]
fn an_item_whose_data_escapes_its_leaf_is_refused_in_both_directions() {
type Escape = (&'static str, Box<dyn Fn(&mut Item)>);
let cases: [Escape; 3] = [
("array", Box::new(|item: &mut Item| item.offset = 0)),
(
"block",
Box::new(|item: &mut Item| item.size = NODE_SIZE as u32),
),
(
"block",
Box::new(|item: &mut Item| {
item.offset = u32::MAX;
item.size = u32::MAX;
}),
),
];
for (expected, damage) in cases {
let mut forge = Forge::new();
forge.root_leaf(&items(1..4));
forge.amend(ROOT_TREE_AT, |block| {
let mut item = Item::read_from(&block[Header::SIZE..]).expect("an item");
damage(&mut item);
item.write_to(&mut block[Header::SIZE..]);
});
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
let block = volume.read_block(ROOT_TREE_AT).expect("the block verifies");
match block.item_data(0) {
Err(ReadError::BadItem {
fault, index: 0, ..
}) => {
assert!(fault.contains(expected), "{fault}");
}
other => panic!("an item escaping its leaf toward the {expected}: {other:?}"),
}
}
}
#[test]
fn a_leaf_whose_data_has_been_moved_with_its_offsets_is_refused() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..6));
forge.amend(ROOT_TREE_AT, |block| {
let at = Header::SIZE + 2 * Item::SIZE;
let mut third = Item::read_from(&block[at..]).expect("an item");
third.offset -= 16;
third.write_to(&mut block[at..]);
});
assert!(matches!(
walk(&forge),
Err(ReadError::BadItem { fault, index: 2, .. })
if fault.contains("does not end where the item before it begins")
));
let mut forge = Forge::new();
forge.root_leaf(&items(1..6));
forge.amend(ROOT_TREE_AT, |block| {
let mut first = Item::read_from(&block[Header::SIZE..]).expect("an item");
first.size -= 1;
first.write_to(&mut block[Header::SIZE..]);
});
assert!(matches!(
walk(&forge),
Err(ReadError::BadItem { index: 0, .. })
));
}
#[test]
fn a_block_from_another_transaction_than_its_pointer_records_is_refused() {
use crate::btrfs::forge::GENERATION;
use crate::btrfs::ondisk::KeyPtr;
let mut forge = Forge::new();
forge.root_leaf(&items(1..6));
forge.amend(ROOT_TREE_AT, |block| {
let mut header = Header::read_from(block).expect("a header");
header.generation = 9999;
header.write_to(block);
});
assert!(matches!(
walk(&forge),
Err(ReadError::WrongGeneration { logical, generation: 9999, expected })
if logical == ROOT_TREE_AT && expected == GENERATION
));
let mut forge = Forge::new();
let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
.root_node(1, &[(key(1), left), (key(10), right)]);
forge.amend(ROOT_TREE_AT, |block| {
let at = Header::SIZE + KeyPtr::SIZE;
let mut pointer = KeyPtr::read_from(&block[at..]).expect("a pointer");
pointer.generation = 9999;
pointer.write_to(&mut block[at..]);
});
let stale = |r: Result<_, ReadError>| {
matches!(
r,
Err(ReadError::WrongGeneration { logical, generation, expected: 9999 })
if logical == right && generation == GENERATION
)
};
assert!(stale(walk(&forge).map(|_| ())));
let mut volume = Volume::open(forge.source()).expect("the filesystem opens");
let root = volume.root_tree();
assert!(stale(volume.tree(root).find_first(key(15)).map(|_| ())));
assert!(stale(
volume.tree(root).find_at_or_before(key(15)).map(|_| ())
));
assert!(
volume
.tree(root)
.find_exact(key(5))
.expect("search")
.is_some()
);
}
#[test]
fn a_node_key_that_does_not_match_the_block_it_leads_to_is_refused_on_every_path() {
let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
type Shape = (&'static str, std::ops::Range<u64>, [DiskKey; 2], DiskKey);
let shapes: [Shape; 4] = [
(
"the node's keys are out of order",
1..10,
[key(10), DiskKey::MIN],
key(15),
),
(
"the key for the right child is below its first key",
1..10,
[key(1), key(9)],
key(15),
),
(
"the key for the right child is above its first key",
1..10,
[key(1), key(11)],
key(15),
),
(
"the left child reaches the key the node records for the right one",
1..12,
[key(1), key(10)],
key(5),
),
];
for (what, left_items, [first, second], reaches) in shapes {
let held: Vec<u64> = left_items.clone().chain(10..20).collect();
let mut forge = Forge::new();
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(left_items)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
.root_node(1, &[(first, left), (second, right)]);
let refused =
|r: Result<(), ReadError>| matches!(r, Err(ReadError::BadTreeBlock { .. }));
assert!(refused(walk(&forge).map(|_| ())), "{what}: the walk");
let mut volume = Volume::open(forge.source()).expect("the filesystem opens");
let root = volume.root_tree();
for probe in [5, 10, 15] {
let truths = [
(
"find_first",
held.iter().copied().filter(|n| *n >= probe).min(),
),
(
"find_at_or_before",
held.iter().copied().filter(|n| *n <= probe).max(),
),
];
for (form, truth) in truths {
let answer = if form == "find_first" {
volume.tree(root).find_first(key(probe))
} else {
volume.tree(root).find_at_or_before(key(probe))
};
match answer {
Ok(found) => assert_eq!(
found.map(|located| located.key),
truth.map(key),
"{what}: {form} {probe} answered other than the tree holds"
),
Err(e) => assert!(
refused(Err(e)),
"{what}: {form} {probe} failed some other way"
),
}
}
}
assert!(
refused(volume.tree(root).find_first(reaches).map(|_| ())),
"{what}: a lookup that reaches the block at fault"
);
}
let mut forge = Forge::new();
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
.root_node(1, &[(key(1), left), (key(10), right)]);
assert_eq!(walk(&forge).expect("a well-formed tree").len(), 19);
}
#[test]
fn a_tree_whose_keys_are_not_in_order_is_refused_rather_than_searched_wrongly() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..6));
forge.amend(ROOT_TREE_AT, |block| {
let mut second = Item::read_from(&block[Header::SIZE + Item::SIZE..]).expect("an item");
second.key = key(0);
second.write_to(&mut block[Header::SIZE + Item::SIZE..]);
});
assert!(matches!(
walk(&forge),
Err(ReadError::BadTreeBlock { fault, .. }) if fault.contains("above the one before")
));
let mut forge = Forge::new();
forge.root_leaf(&[(key(1), vec![1; 8]), (key(1), vec![2; 8])]);
assert!(matches!(walk(&forge), Err(ReadError::BadTreeBlock { .. })));
}
#[test]
fn a_block_whose_checksum_no_longer_covers_it_is_refused_wherever_it_sits() {
for at in [ROOT_TREE_AT, CHUNK_LOGICAL] {
let mut forge = Forge::new();
forge.root_leaf(&items(1..4));
forge.break_checksum(at);
let opened = Volume::open(forge.source()).and_then(|mut v| {
let root = v.root_tree();
v.tree(root).count_items()
});
assert!(
matches!(
&opened,
Err(ReadError::BadChecksum {
object: "tree block",
..
})
),
"a damaged block at {at}: {opened:?}"
);
}
}
#[test]
fn a_block_at_an_address_no_chunk_maps_is_refused_rather_than_read_from_nowhere() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..4));
forge.amend_superblock(0, |sb| sb.root = CHUNK_LOGICAL + CHUNK_LENGTH);
assert!(matches!(
walk(&forge),
Err(ReadError::UnmappedLogical { .. })
));
}
#[test]
fn a_walk_stops_at_the_cap_the_caller_set_rather_than_gathering_past_it() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..40));
let options = OpenOptions::new().limits(Limits::new().max_walk_entries(10));
let mut volume =
Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
let root = volume.root_tree();
assert!(matches!(
volume.tree(root).count_items(),
Err(ReadError::TooManyEntries { limit: 10, .. })
));
let options = OpenOptions::new().limits(Limits::new().max_walk_entries(39));
let mut volume =
Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
let root = volume.root_tree();
assert_eq!(volume.tree(root).count_items().expect("within the cap"), 39);
let options = OpenOptions::new().limits(Limits::new().max_walk_entries(10));
let mut volume =
Volume::open_with(forge.source(), options).expect("a well-formed filesystem");
let root = volume.root_tree();
let mut taken = 0;
volume
.tree(root)
.for_each_item(|_, _| {
if taken == 10 {
return false;
}
taken += 1;
true
})
.expect("ten taken, and the eleventh declined");
assert_eq!(taken, 10);
let mut taken = 0;
assert!(matches!(
volume.tree(root).for_each_item(|_, _| {
taken += 1;
taken <= 11
}),
Err(ReadError::TooManyEntries { limit: 10, .. })
));
}
#[test]
fn a_visit_that_says_to_stop_stops_where_it_said() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..40));
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
let root = volume.root_tree();
let mut seen = 0;
volume
.tree(root)
.for_each_item(|_, _| {
seen += 1;
seen < 3
})
.expect("a well-formed tree");
assert_eq!(seen, 3);
}
#[test]
fn every_block_of_a_tree_is_offered_to_a_block_walk_including_its_nodes() {
let mut forge = Forge::new();
let (left, right) = (FIRST_FREE_AT, FIRST_FREE_AT + NODE_SIZE as u64);
forge
.block(left, &leaf(left, objectid::ROOT_TREE, &items(1..10)))
.block(right, &leaf(right, objectid::ROOT_TREE, &items(10..20)))
.root_node(1, &[(key(1), left), (key(10), right)]);
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
let root = volume.root_tree();
let mut blocks = Vec::new();
volume
.tree(root)
.for_each_block(|block| {
blocks.push((block.header().bytenr, block.header().level));
true
})
.expect("a well-formed tree");
assert_eq!(blocks, vec![(ROOT_TREE_AT, 1), (left, 0), (right, 0)]);
}
#[test]
fn a_forged_filesystem_is_one_the_reader_accepts_before_it_is_damaged() {
let mut forge = Forge::new();
forge.root_leaf(&items(1..40));
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
assert_eq!(volume.superblock().nodesize as usize, NODE_SIZE);
assert_eq!(volume.chunk_map().len(), 1);
let root = volume.root_tree();
assert_eq!(
volume.tree(root).count_items().expect("a well-formed tree"),
39
);
let mut block = leaf(FIRST_FREE_AT, objectid::ROOT_TREE, &items(1..4));
block[Header::SIZE] ^= 0xff;
seal(&mut block);
forge.block(FIRST_FREE_AT, &block);
let mut volume = Volume::open(forge.source()).expect("a well-formed filesystem");
assert!(volume.read_block(FIRST_FREE_AT).is_ok());
}
}