use crate::geometry::BlockRange;
use crate::ondisk::{EXTENT_ENTRY_SIZE, ExtentHeader, ExtentIdx, ExtentLeaf, ParseError};
pub const MAX_EXTENT_LEN: u32 = 32768;
pub const MAX_EXTENT_DEPTH: u16 = 5;
const MAX_LOGICAL_BLOCKS: u64 = 1 << 32;
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ExtentError {
#[error("{entries} extent entries exceed the {capacity} that fit in the node")]
#[non_exhaustive]
TooManyEntries {
entries: usize,
capacity: usize,
},
#[error("extent node buffer of {bytes} bytes cannot hold a header")]
#[non_exhaustive]
NodeTooSmall {
bytes: usize,
},
#[error("extent tree of depth {depth} exceeds the maximum depth {MAX_EXTENT_DEPTH}")]
#[non_exhaustive]
TooDeep {
depth: u16,
},
#[error("file of {blocks} blocks exceeds the {MAX_LOGICAL_BLOCKS} an extent tree addresses")]
#[non_exhaustive]
FileTooLarge {
blocks: u64,
},
#[error("extent tree needs {need} node blocks but {got} were supplied")]
#[non_exhaustive]
NodeBlockCount {
need: usize,
got: usize,
},
#[error(transparent)]
Leaf(#[from] ParseError),
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum ExtentNode {
Leaves(Vec<ExtentLeaf>),
Index {
depth: u16,
entries: Vec<ExtentIdx>,
},
}
impl ExtentNode {
#[must_use]
pub fn depth(&self) -> u16 {
match self {
Self::Leaves(_) => 0,
Self::Index { depth, .. } => *depth,
}
}
#[must_use]
pub fn len(&self) -> usize {
match self {
Self::Leaves(leaves) => leaves.len(),
Self::Index { entries, .. } => entries.len(),
}
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct ExtentNodeBlock {
pub block: u64,
pub node: ExtentNode,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct ExtentTree {
pub root: ExtentNode,
pub nodes: Vec<ExtentNodeBlock>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct TreeShape {
pub depth: u16,
pub level_nodes: Vec<usize>,
pub node_blocks: usize,
}
#[must_use]
pub const fn node_capacity(node_bytes: usize) -> usize {
node_bytes.saturating_sub(EXTENT_ENTRY_SIZE) / EXTENT_ENTRY_SIZE
}
#[must_use]
pub const fn tail_offset(node_bytes: usize) -> usize {
EXTENT_ENTRY_SIZE * (node_capacity(node_bytes) + 1)
}
pub fn build_leaves(ranges: &[BlockRange]) -> Result<Vec<ExtentLeaf>, ExtentError> {
let total: u64 = ranges.iter().map(|r| r.len).sum();
if total > MAX_LOGICAL_BLOCKS {
return Err(ExtentError::FileTooLarge { blocks: total });
}
let mut leaves: Vec<ExtentLeaf> = Vec::new();
let mut logical: u64 = 0;
for range in ranges {
let mut phys = range.start;
let mut left = range.len;
while left > 0 {
let take = left.min(u64::from(MAX_EXTENT_LEN)) as u32;
if let Some(last) = leaves.last_mut()
&& last.initialized
&& u64::from(last.block) + u64::from(last.len) == logical
&& last.start + u64::from(last.len) == phys
&& u32::from(last.len) + take <= MAX_EXTENT_LEN
{
last.len += take as u16;
} else {
leaves.push(ExtentLeaf {
block: logical as u32,
len: take as u16,
start: phys,
initialized: true,
});
}
logical += u64::from(take);
phys += u64::from(take);
left -= u64::from(take);
}
}
Ok(leaves)
}
pub fn plan_tree(
leaves: usize,
inline_capacity: usize,
node_capacity: usize,
) -> Result<TreeShape, ExtentError> {
if leaves <= inline_capacity {
return Ok(TreeShape {
depth: 0,
level_nodes: Vec::new(),
node_blocks: 0,
});
}
if node_capacity < 2 || inline_capacity < 1 {
return Err(ExtentError::TooManyEntries {
entries: leaves,
capacity: inline_capacity,
});
}
let mut level_nodes = Vec::new();
let mut width = leaves.div_ceil(node_capacity);
level_nodes.push(width);
while width > inline_capacity {
width = width.div_ceil(node_capacity);
level_nodes.push(width);
}
let depth = level_nodes.len() as u16;
if depth > MAX_EXTENT_DEPTH {
return Err(ExtentError::TooDeep { depth });
}
Ok(TreeShape {
depth,
node_blocks: level_nodes.iter().sum(),
level_nodes,
})
}
pub fn build_tree(
leaves: &[ExtentLeaf],
inline_capacity: usize,
node_capacity: usize,
node_blocks: &[u64],
) -> Result<ExtentTree, ExtentError> {
let shape = plan_tree(leaves.len(), inline_capacity, node_capacity)?;
if node_blocks.len() != shape.node_blocks {
return Err(ExtentError::NodeBlockCount {
need: shape.node_blocks,
got: node_blocks.len(),
});
}
if shape.depth == 0 {
return Ok(ExtentTree {
root: ExtentNode::Leaves(leaves.to_vec()),
nodes: Vec::new(),
});
}
let mut nodes: Vec<ExtentNodeBlock> = Vec::with_capacity(shape.node_blocks);
let mut taken = 0usize;
let mut children: Vec<ExtentIdx> = Vec::with_capacity(shape.level_nodes[0]);
for chunk in leaves.chunks(node_capacity) {
let block = node_blocks[taken];
taken += 1;
children.push(ExtentIdx {
block: chunk[0].block,
leaf: block,
});
nodes.push(ExtentNodeBlock {
block,
node: ExtentNode::Leaves(chunk.to_vec()),
});
}
for depth in 1..shape.depth {
let mut parents: Vec<ExtentIdx> = Vec::with_capacity(shape.level_nodes[depth as usize]);
for chunk in children.chunks(node_capacity) {
let block = node_blocks[taken];
taken += 1;
parents.push(ExtentIdx {
block: chunk[0].block,
leaf: block,
});
nodes.push(ExtentNodeBlock {
block,
node: ExtentNode::Index {
depth,
entries: chunk.to_vec(),
},
});
}
children = parents;
}
Ok(ExtentTree {
root: ExtentNode::Index {
depth: shape.depth,
entries: children,
},
nodes,
})
}
pub fn write_node(node: &ExtentNode, eh_max: usize, buf: &mut [u8]) -> Result<(), ExtentError> {
if buf.len() < EXTENT_ENTRY_SIZE {
return Err(ExtentError::NodeTooSmall { bytes: buf.len() });
}
let entries = node.len();
if entries > eh_max || EXTENT_ENTRY_SIZE * (eh_max + 1) > buf.len() {
return Err(ExtentError::TooManyEntries {
entries,
capacity: eh_max.min(node_capacity(buf.len())),
});
}
let header = ExtentHeader {
entries: entries as u16,
max: eh_max as u16,
depth: node.depth(),
generation: 0,
};
buf[0..EXTENT_ENTRY_SIZE].copy_from_slice(&header.to_bytes());
let mut put = |i: usize, bytes: [u8; EXTENT_ENTRY_SIZE]| {
let off = EXTENT_ENTRY_SIZE * (i + 1);
buf[off..off + EXTENT_ENTRY_SIZE].copy_from_slice(&bytes);
};
match node {
ExtentNode::Leaves(leaves) => {
for (i, leaf) in leaves.iter().enumerate() {
put(i, leaf.to_bytes()?);
}
}
ExtentNode::Index { entries, .. } => {
for (i, idx) in entries.iter().enumerate() {
put(i, idx.to_bytes());
}
}
}
Ok(())
}
pub fn parse_node(buf: &[u8]) -> Result<ExtentNode, crate::ondisk::ParseError> {
use crate::ondisk::ParseError;
if buf.len() < EXTENT_ENTRY_SIZE {
return Err(ParseError::TooShort {
structure: "ExtentHeader",
need: EXTENT_ENTRY_SIZE,
got: buf.len(),
});
}
let header_bytes: &[u8; EXTENT_ENTRY_SIZE] = buf[0..EXTENT_ENTRY_SIZE]
.try_into()
.expect("header slice is exactly EXTENT_ENTRY_SIZE bytes");
let header = ExtentHeader::from_bytes(header_bytes)?;
let entries = header.entries as usize;
let need = EXTENT_ENTRY_SIZE * (entries + 1);
if buf.len() < need {
return Err(ParseError::TooShort {
structure: "ExtentNode",
need,
got: buf.len(),
});
}
let entry = |i: usize| -> [u8; EXTENT_ENTRY_SIZE] {
let off = EXTENT_ENTRY_SIZE * (i + 1);
buf[off..off + EXTENT_ENTRY_SIZE]
.try_into()
.expect("entry slice is exactly EXTENT_ENTRY_SIZE bytes")
};
if header.depth == 0 {
let leaves = (0..entries)
.map(|i| ExtentLeaf::from_bytes(&entry(i)))
.collect();
Ok(ExtentNode::Leaves(leaves))
} else {
let idxs = (0..entries)
.map(|i| ExtentIdx::from_bytes(&entry(i)))
.collect();
Ok(ExtentNode::Index {
depth: header.depth,
entries: idxs,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::ondisk::Inode;
const INLINE: usize = node_capacity(Inode::BLOCK_BYTES);
const NODE: usize = node_capacity(4096);
fn leaves_of(n: usize) -> Vec<ExtentLeaf> {
(0..n)
.map(|i| ExtentLeaf {
block: i as u32,
len: 1,
start: 100 + (i as u64) * 2,
initialized: true,
})
.collect()
}
#[test]
fn single_contiguous_run_is_one_leaf() {
let leaves = build_leaves(&[BlockRange { start: 7, len: 4 }]).unwrap();
assert_eq!(
leaves,
vec![ExtentLeaf {
block: 0,
len: 4,
start: 7,
initialized: true,
}]
);
}
#[test]
fn separate_ranges_stay_separate_leaves() {
let leaves = build_leaves(&[
BlockRange { start: 100, len: 2 },
BlockRange { start: 200, len: 3 },
])
.unwrap();
assert_eq!(leaves.len(), 2);
assert_eq!(leaves[1].block, 2);
assert_eq!(leaves[1].start, 200);
}
#[test]
fn contiguous_ranges_coalesce() {
let leaves = build_leaves(&[
BlockRange { start: 50, len: 4 },
BlockRange { start: 54, len: 6 },
])
.unwrap();
assert_eq!(
leaves,
vec![ExtentLeaf {
block: 0,
len: 10,
start: 50,
initialized: true
}]
);
}
#[test]
fn runs_longer_than_a_leaf_split() {
let leaves = build_leaves(&[BlockRange {
start: 1000,
len: 40000,
}])
.unwrap();
assert_eq!(leaves.len(), 2);
assert_eq!(leaves[0].len, 32768);
assert_eq!(leaves[1].block, 32768);
assert_eq!(leaves[1].len, 7232);
assert_eq!(leaves[1].start, 1000 + 32768);
}
#[test]
fn a_file_past_the_logical_limit_is_rejected() {
let ok = build_leaves(&[BlockRange {
start: 0,
len: MAX_LOGICAL_BLOCKS,
}]);
assert!(ok.is_ok());
assert_eq!(
build_leaves(&[BlockRange {
start: 0,
len: MAX_LOGICAL_BLOCKS + 1,
}]),
Err(ExtentError::FileTooLarge {
blocks: MAX_LOGICAL_BLOCKS + 1
})
);
}
#[test]
fn the_inline_area_holds_four_entries_and_a_node_holds_three_hundred_and_forty() {
assert_eq!(INLINE, 4);
assert_eq!(NODE, 340);
assert_eq!(tail_offset(4096), 4092);
assert_eq!(tail_offset(4096) + 4, 4096);
}
#[test]
fn a_node_smaller_than_its_header_holds_no_entries() {
assert_eq!(node_capacity(0), 0);
assert_eq!(node_capacity(EXTENT_ENTRY_SIZE - 1), 0);
assert_eq!(node_capacity(EXTENT_ENTRY_SIZE), 0);
assert_eq!(node_capacity(2 * EXTENT_ENTRY_SIZE), 1);
assert_eq!(tail_offset(0), EXTENT_ENTRY_SIZE);
assert!(matches!(
write_node(
&ExtentNode::Leaves(Vec::new()),
node_capacity(4),
&mut [0u8; 4]
),
Err(ExtentError::NodeTooSmall { .. })
));
}
#[test]
fn leaves_that_fit_inline_need_no_tree() {
let shape = plan_tree(INLINE, INLINE, NODE).unwrap();
assert_eq!(shape.depth, 0);
assert_eq!(shape.node_blocks, 0);
let leaves = leaves_of(INLINE);
let tree = build_tree(&leaves, INLINE, NODE, &[]).unwrap();
assert_eq!(tree.root, ExtentNode::Leaves(leaves));
assert!(tree.nodes.is_empty());
}
#[test]
fn a_fifth_leaf_spills_into_one_external_node() {
let shape = plan_tree(INLINE + 1, INLINE, NODE).unwrap();
assert_eq!(shape.depth, 1);
assert_eq!(shape.level_nodes, vec![1]);
assert_eq!(shape.node_blocks, 1);
let leaves = leaves_of(INLINE + 1);
let tree = build_tree(&leaves, INLINE, NODE, &[900]).unwrap();
assert_eq!(
tree.root,
ExtentNode::Index {
depth: 1,
entries: vec![ExtentIdx {
block: 0,
leaf: 900
}],
}
);
assert_eq!(tree.nodes.len(), 1);
assert_eq!(tree.nodes[0].block, 900);
assert_eq!(tree.nodes[0].node, ExtentNode::Leaves(leaves));
}
#[test]
fn a_depth_one_tree_fills_its_leaf_nodes_in_order() {
let leaves = leaves_of(NODE + 1);
let shape = plan_tree(leaves.len(), INLINE, NODE).unwrap();
assert_eq!(shape.depth, 1);
assert_eq!(shape.level_nodes, vec![2]);
let tree = build_tree(&leaves, INLINE, NODE, &[900, 901]).unwrap();
let ExtentNode::Index { entries, depth } = &tree.root else {
panic!("root indexes the leaf nodes");
};
assert_eq!(*depth, 1);
assert_eq!(
entries[0],
ExtentIdx {
block: 0,
leaf: 900
}
);
assert_eq!(
entries[1],
ExtentIdx {
block: NODE as u32,
leaf: 901
}
);
assert_eq!(tree.nodes[0].node.len(), NODE);
assert_eq!(tree.nodes[1].node.len(), 1);
}
#[test]
fn a_tree_grows_to_depth_two_when_the_root_cannot_index_the_leaf_level() {
let leaves = leaves_of(NODE * (INLINE + 1));
let shape = plan_tree(leaves.len(), INLINE, NODE).unwrap();
assert_eq!(shape.depth, 2);
assert_eq!(shape.level_nodes, vec![INLINE + 1, 1]);
assert_eq!(shape.node_blocks, INLINE + 2);
let blocks: Vec<u64> = (900..900 + shape.node_blocks as u64).collect();
let tree = build_tree(&leaves, INLINE, NODE, &blocks).unwrap();
let ExtentNode::Index { entries, depth } = &tree.root else {
panic!("root indexes the interior level");
};
assert_eq!(*depth, 2);
assert_eq!(entries.len(), 1);
assert_eq!(entries[0].leaf, *blocks.last().unwrap());
let interior = &tree.nodes.last().unwrap().node;
assert_eq!(interior.depth(), 1);
assert_eq!(interior.len(), INLINE + 1);
assert!(tree.nodes[..INLINE + 1].iter().all(|n| n.node.depth() == 0));
}
#[test]
fn every_leaf_appears_exactly_once_in_a_deep_tree() {
let leaves = leaves_of(100);
let shape = plan_tree(leaves.len(), INLINE, 8).unwrap();
assert_eq!(shape.depth, 2);
assert_eq!(shape.level_nodes, vec![13, 2]);
let blocks: Vec<u64> = (900..900 + shape.node_blocks as u64).collect();
let tree = build_tree(&leaves, INLINE, 8, &blocks).unwrap();
let mut seen: Vec<ExtentLeaf> = Vec::new();
for node in &tree.nodes {
if let ExtentNode::Leaves(l) = &node.node {
seen.extend(l.iter().copied());
}
}
assert_eq!(seen, leaves, "leaves survive the split in logical order");
let mut pointed: Vec<u64> = Vec::new();
for node in &tree.nodes {
if let ExtentNode::Index { entries, .. } = &node.node {
pointed.extend(entries.iter().map(|e| e.leaf));
}
}
let ExtentNode::Index { entries, .. } = &tree.root else {
panic!("root indexes the interior level");
};
pointed.extend(entries.iter().map(|e| e.leaf));
pointed.sort_unstable();
assert_eq!(pointed, blocks);
}
#[test]
fn a_tree_deeper_than_ext4_defines_is_rejected() {
assert_eq!(plan_tree(4, 2, 2).unwrap().depth, 1);
assert_eq!(plan_tree(64, 2, 2).unwrap().depth, 5);
assert_eq!(plan_tree(128, 2, 2), Err(ExtentError::TooDeep { depth: 6 }));
}
#[test]
fn a_node_that_cannot_narrow_a_level_is_rejected() {
assert!(matches!(
plan_tree(10, 4, 1),
Err(ExtentError::TooManyEntries { .. })
));
}
#[test]
fn build_tree_checks_the_node_blocks_against_the_plan() {
let leaves = leaves_of(INLINE + 1);
assert_eq!(
build_tree(&leaves, INLINE, NODE, &[]),
Err(ExtentError::NodeBlockCount { need: 1, got: 0 })
);
}
#[test]
fn inline_node_round_trips_through_the_inode_block_area() {
let leaves = build_leaves(&[BlockRange { start: 6, len: 1 }]).unwrap();
let mut block = [0u8; Inode::BLOCK_BYTES];
write_node(&ExtentNode::Leaves(leaves.clone()), INLINE, &mut block).unwrap();
match parse_node(&block).unwrap() {
ExtentNode::Leaves(back) => assert_eq!(back, leaves),
other => panic!("expected leaves, got {other:?}"),
}
}
#[test]
fn an_index_node_round_trips_through_a_block() {
let node = ExtentNode::Index {
depth: 1,
entries: vec![
ExtentIdx {
block: 0,
leaf: 900,
},
ExtentIdx {
block: 340,
leaf: 0x1_0000_0001,
},
],
};
let mut buf = vec![0u8; 4096];
write_node(&node, NODE, &mut buf).unwrap();
assert_eq!(u16::from_le_bytes([buf[4], buf[5]]), NODE as u16);
assert_eq!(parse_node(&buf).unwrap(), node);
}
#[test]
fn write_node_rejects_more_entries_than_the_capacity() {
let five = ExtentNode::Leaves(leaves_of(INLINE + 1));
let mut block = [0u8; Inode::BLOCK_BYTES];
assert_eq!(
write_node(&five, INLINE, &mut block),
Err(ExtentError::TooManyEntries {
entries: 5,
capacity: 4
})
);
}
#[test]
fn parse_ignores_trailing_inline_bytes() {
let leaves = build_leaves(&[BlockRange { start: 6, len: 1 }]).unwrap();
let mut block = [0xabu8; Inode::BLOCK_BYTES];
write_node(&ExtentNode::Leaves(leaves), INLINE, &mut block).unwrap();
match parse_node(&block).unwrap() {
ExtentNode::Leaves(back) => assert_eq!(back.len(), 1),
other => panic!("expected one leaf, got {other:?}"),
}
}
}