use crate::hash::{DirHash, HashSignedness, HashVersion, dir_hash};
use crate::ondisk::{
DIR_TAIL_LEN, DX_HASH_CONTINUED, DX_MAX_INDIRECT_LEVELS, DX_NODE_COUNT_OFFSET,
DX_ROOT_COUNT_OFFSET, DirEntry, DxEntry, ParseError, dx_limit, min_rec_len, put_u16,
rec_len_to_disk, write_dir_tail, write_dx_entries, write_dx_node_header, write_dx_root_header,
};
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum DirError {
#[error("directory entry needs {need} bytes, more than a {block_size}-byte block holds")]
#[non_exhaustive]
EntryTooLarge {
need: usize,
block_size: usize,
},
#[error("directory entries must begin with \".\" and \"..\"")]
MissingDotEntries,
#[error("directory index needs {blocks} entry blocks, more than the {capacity} addressable")]
#[non_exhaustive]
IndexTooLarge {
blocks: usize,
capacity: usize,
},
#[error(transparent)]
Encode(#[from] ParseError),
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum DirBlockKind {
Entries,
Index {
count_offset: usize,
limit: usize,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct DirBlock {
pub bytes: Vec<u8>,
pub kind: DirBlockKind,
}
impl DirBlock {
#[must_use]
fn entries(bytes: Vec<u8>) -> Self {
Self {
bytes,
kind: DirBlockKind::Entries,
}
}
}
pub trait DirLayout: crate::sealed::Sealed {
fn build_blocks(
&self,
entries: &[DirEntry],
block_size: usize,
) -> Result<Vec<DirBlock>, DirError>;
}
fn close_block(
block: &mut [u8],
last_off: usize,
usable: usize,
tail_len: usize,
) -> Result<(), DirError> {
put_u16(
block,
last_off + 4,
rec_len_to_disk(usable - last_off, block.len()),
);
if tail_len != 0 {
write_dir_tail(&mut block[usable..usable + tail_len], 0)?;
}
Ok(())
}
fn pack_one_block(
entries: &[&DirEntry],
block_size: usize,
tail_len: usize,
) -> Result<Vec<u8>, DirError> {
let usable = block_size - tail_len;
let mut block = vec![0u8; block_size];
let mut off = 0usize;
let mut last_off = 0usize;
for entry in entries {
let need = min_rec_len(entry.name.len()) as usize;
entry.write_to(&mut block[off..off + need], need, block_size)?;
last_off = off;
off += need;
}
close_block(&mut block, last_off, usable, tail_len)?;
Ok(block)
}
fn record_len(entry: &DirEntry, block_size: usize, tail_len: usize) -> Result<usize, DirError> {
let need = min_rec_len(entry.name.len()) as usize;
if need > block_size - tail_len {
return Err(DirError::EntryTooLarge { need, block_size });
}
Ok(need)
}
fn fits_in_one_block(
entries: &[DirEntry],
block_size: usize,
tail_len: usize,
) -> Result<bool, DirError> {
let mut total = 0usize;
for entry in entries {
total += record_len(entry, block_size, tail_len)?;
}
Ok(total <= block_size - tail_len)
}
#[derive(Clone, Copy, Debug)]
pub struct LinearDir {
pub tail_len: usize,
}
impl crate::sealed::Sealed for LinearDir {}
impl DirLayout for LinearDir {
fn build_blocks(
&self,
entries: &[DirEntry],
block_size: usize,
) -> Result<Vec<DirBlock>, DirError> {
let usable = block_size - self.tail_len;
let mut blocks: Vec<DirBlock> = Vec::new();
let mut cur: Vec<&DirEntry> = Vec::new();
let mut used = 0usize;
for entry in entries {
let need = record_len(entry, block_size, self.tail_len)?;
if used + need > usable && !cur.is_empty() {
blocks.push(DirBlock::entries(pack_one_block(
&cur,
block_size,
self.tail_len,
)?));
cur.clear();
used = 0;
}
used += need;
cur.push(entry);
}
if !cur.is_empty() {
blocks.push(DirBlock::entries(pack_one_block(
&cur,
block_size,
self.tail_len,
)?));
}
Ok(blocks)
}
}
#[derive(Clone, Copy, Debug)]
pub struct HtreeDir {
pub seed: [u8; 16],
pub version: HashVersion,
pub signedness: HashSignedness,
pub checksums: bool,
}
impl HtreeDir {
fn split_dots(entries: &[DirEntry]) -> Result<(&DirEntry, &DirEntry, &[DirEntry]), DirError> {
match entries {
[dot, dotdot, rest @ ..] if dot.name == b"." && dotdot.name == b".." => {
Ok((dot, dotdot, rest))
}
_ => Err(DirError::MissingDotEntries),
}
}
fn sort_by_hash<'a>(&self, entries: &'a [DirEntry]) -> Vec<(DirHash, &'a DirEntry)> {
let mut hashed: Vec<(DirHash, &DirEntry)> = entries
.iter()
.map(|e| {
(
dir_hash(&e.name, self.version, self.signedness, &self.seed),
e,
)
})
.collect();
hashed.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.name.cmp(&b.1.name)));
hashed
}
}
impl crate::sealed::Sealed for HtreeDir {}
impl DirLayout for HtreeDir {
fn build_blocks(
&self,
entries: &[DirEntry],
block_size: usize,
) -> Result<Vec<DirBlock>, DirError> {
let tail_len = if self.checksums { DIR_TAIL_LEN } else { 0 };
if fits_in_one_block(entries, block_size, tail_len)? {
return LinearDir { tail_len }.build_blocks(entries, block_size);
}
let (dot, dotdot, rest) = Self::split_dots(entries)?;
let hashed = self.sort_by_hash(rest);
let usable = block_size - tail_len;
let mut leaves: Vec<Vec<(DirHash, &DirEntry)>> = Vec::new();
let mut cur: Vec<(DirHash, &DirEntry)> = Vec::new();
let mut used = 0usize;
for (hash, entry) in hashed {
let need = record_len(entry, block_size, tail_len)?;
if used + need > usable && !cur.is_empty() {
leaves.push(std::mem::take(&mut cur));
used = 0;
}
used += need;
cur.push((hash, entry));
}
if !cur.is_empty() {
leaves.push(cur);
}
let mut leaf_hash = vec![0u32; leaves.len()];
for k in 1..leaves.len() {
let first = leaves[k][0].0.major;
let prev_last = leaves[k - 1]
.last()
.expect("a block holds an entry")
.0
.major;
leaf_hash[k] = first
| if first == prev_last {
DX_HASH_CONTINUED
} else {
0
};
}
let root_limit = dx_limit(block_size, DX_ROOT_COUNT_OFFSET, self.checksums);
let node_limit = dx_limit(block_size, DX_NODE_COUNT_OFFSET, self.checksums);
let indirect_levels = u8::from(leaves.len() > root_limit);
if indirect_levels > 0 && leaves.len().div_ceil(node_limit) > root_limit {
return Err(DirError::IndexTooLarge {
blocks: leaves.len(),
capacity: root_limit * node_limit,
});
}
debug_assert!(indirect_levels <= DX_MAX_INDIRECT_LEVELS);
let node_count = if indirect_levels == 0 {
0
} else {
leaves.len().div_ceil(node_limit)
};
let first_leaf_block = 1 + node_count;
let mut nodes: Vec<DirBlock> = Vec::with_capacity(node_count);
let root_entries: Vec<DxEntry> = if indirect_levels == 0 {
(0..leaves.len())
.map(|k| DxEntry {
hash: leaf_hash[k],
block: (first_leaf_block + k) as u32,
})
.collect()
} else {
let leaf_indices: Vec<usize> = (0..leaves.len()).collect();
for chunk in leaf_indices.chunks(node_limit) {
let node_entries: Vec<DxEntry> = chunk
.iter()
.enumerate()
.map(|(j, &k)| DxEntry {
hash: if j == 0 { 0 } else { leaf_hash[k] },
block: (first_leaf_block + k) as u32,
})
.collect();
let mut bytes = vec![0u8; block_size];
write_dx_node_header(&mut bytes)?;
write_dx_entries(&mut bytes, DX_NODE_COUNT_OFFSET, node_limit, &node_entries)?;
nodes.push(DirBlock {
bytes,
kind: DirBlockKind::Index {
count_offset: DX_NODE_COUNT_OFFSET,
limit: node_limit,
},
});
}
(0..node_count)
.map(|i| DxEntry {
hash: leaf_hash[i * node_limit],
block: (1 + i) as u32,
})
.collect()
};
let mut root = vec![0u8; block_size];
write_dx_root_header(
&mut root,
dot.inode,
dotdot.inode,
self.version.to_u8(),
indirect_levels,
)?;
write_dx_entries(&mut root, DX_ROOT_COUNT_OFFSET, root_limit, &root_entries)?;
let mut blocks = Vec::with_capacity(1 + node_count + leaves.len());
blocks.push(DirBlock {
bytes: root,
kind: DirBlockKind::Index {
count_offset: DX_ROOT_COUNT_OFFSET,
limit: root_limit,
},
});
blocks.extend(nodes);
for leaf in &leaves {
let refs: Vec<&DirEntry> = leaf.iter().map(|(_, e)| *e).collect();
blocks.push(DirBlock::entries(pack_one_block(
&refs, block_size, tail_len,
)?));
}
Ok(blocks)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::ondisk::{DIR_TAIL_LEN, FileType, read_dx_entries, read_dx_root_info};
const BS: usize = 4096;
const SEED: [u8; 16] = [
0x11, 0x11, 0x11, 0x11, 0x22, 0x22, 0x33, 0x33, 0x44, 0x44, 0x55, 0x55, 0x55, 0x55, 0x55,
0x55,
];
fn htree() -> HtreeDir {
HtreeDir {
seed: SEED,
version: HashVersion::HalfMd4,
signedness: HashSignedness::Unsigned,
checksums: true,
}
}
fn dot_entries(dir_ino: u32, parent_ino: u32) -> Vec<DirEntry> {
vec![
DirEntry {
inode: dir_ino,
file_type: FileType::Dir,
name: b".".to_vec(),
},
DirEntry {
inode: parent_ino,
file_type: FileType::Dir,
name: b"..".to_vec(),
},
]
}
fn many(n: u32) -> Vec<DirEntry> {
let mut entries = dot_entries(12, 2);
for i in 0..n {
entries.push(DirEntry {
inode: 100 + i,
file_type: FileType::RegFile,
name: format!("entry-name-number-{i:06}").into_bytes(),
});
}
entries
}
fn walk(block: &[u8]) -> Vec<(u32, Vec<u8>, usize)> {
let mut out = Vec::new();
let mut off = 0;
while off < block.len() {
let (e, rec_len) = DirEntry::read_from(&block[off..], block.len()).unwrap();
out.push((e.inode, e.name, rec_len));
off += rec_len;
}
out
}
fn names(blocks: &[DirBlock], block_size: usize) -> Vec<Vec<u8>> {
let mut out = Vec::new();
for block in blocks {
let usable = block_size - DIR_TAIL_LEN;
let mut off = 0;
while off < usable {
let (e, rec_len) = DirEntry::read_from(&block.bytes[off..], block_size).unwrap();
if e.inode != 0 && e.name != b"." && e.name != b".." {
out.push(e.name);
}
off += rec_len;
}
}
out.sort();
out
}
#[test]
fn root_directory_tiles_one_block_with_a_reserved_tail() {
let mut entries = dot_entries(2, 2);
entries.push(DirEntry {
inode: 11,
file_type: FileType::Dir,
name: b"lost+found".to_vec(),
});
let blocks = LinearDir {
tail_len: DIR_TAIL_LEN,
}
.build_blocks(&entries, BS)
.unwrap();
assert_eq!(blocks.len(), 1);
assert_eq!(blocks[0].kind, DirBlockKind::Entries);
let walked = walk(&blocks[0].bytes);
assert_eq!(walked[0].1, b".");
assert_eq!(walked[1].1, b"..");
assert_eq!(walked[2].1, b"lost+found");
assert_eq!(walked[3].0, 0, "tail is a zero-inode slot");
let total: usize = walked.iter().map(|(_, _, r)| *r).sum();
assert_eq!(total, BS);
assert_eq!(walked[2].2, BS - DIR_TAIL_LEN - 12 - 12);
assert_eq!(walked[3].2, DIR_TAIL_LEN);
}
#[test]
fn lost_found_is_only_dot_entries() {
let entries = dot_entries(11, 2);
let blocks = LinearDir {
tail_len: DIR_TAIL_LEN,
}
.build_blocks(&entries, BS)
.unwrap();
assert_eq!(blocks.len(), 1);
let walked = walk(&blocks[0].bytes);
assert_eq!(walked[0].2, 12);
assert_eq!(walked[1].2, BS - DIR_TAIL_LEN - 12);
assert_eq!(walked.last().unwrap().0, 0, "tail");
}
#[test]
fn many_entries_spill_into_multiple_linear_blocks() {
let entries = many(500);
let blocks = LinearDir {
tail_len: DIR_TAIL_LEN,
}
.build_blocks(&entries, BS)
.unwrap();
assert!(blocks.len() > 1, "500 entries need several blocks");
let mut seen = 0;
for block in &blocks {
let walked = walk(&block.bytes);
let total: usize = walked.iter().map(|(_, _, r)| *r).sum();
assert_eq!(total, BS, "block tiles exactly");
assert_eq!(walked.last().unwrap().0, 0, "block ends with the tail");
seen += walked.iter().filter(|(ino, _, _)| *ino != 0).count();
}
assert_eq!(seen, entries.len(), "every entry placed exactly once");
}
#[test]
fn a_directory_that_fits_in_one_block_is_not_indexed() {
let entries = many(20);
assert!(fits_in_one_block(&entries, BS, DIR_TAIL_LEN).unwrap());
let blocks = htree().build_blocks(&entries, BS).unwrap();
assert_eq!(blocks.len(), 1);
assert_eq!(blocks[0].kind, DirBlockKind::Entries);
}
#[test]
fn a_directory_that_spills_gets_a_root_and_entry_blocks() {
let entries = many(150);
assert!(!fits_in_one_block(&entries, BS, DIR_TAIL_LEN).unwrap());
let blocks = htree().build_blocks(&entries, BS).unwrap();
assert_eq!(blocks.len(), 3);
assert_eq!(
blocks[0].kind,
DirBlockKind::Index {
count_offset: DX_ROOT_COUNT_OFFSET,
limit: 507
}
);
assert!(blocks[1..].iter().all(|b| b.kind == DirBlockKind::Entries));
assert_eq!(read_dx_root_info(&blocks[0].bytes).unwrap(), (1, 0));
let index = read_dx_entries(&blocks[0].bytes, DX_ROOT_COUNT_OFFSET).unwrap();
assert_eq!(index.len(), 2);
assert_eq!(index[0], DxEntry { hash: 0, block: 1 });
assert_eq!(index[1].block, 2);
assert_eq!(names(&blocks, BS).len(), 150);
let (dot, _) = DirEntry::read_from(&blocks[0].bytes, BS).unwrap();
assert_eq!(dot.name, b".");
}
#[test]
fn entry_blocks_are_ordered_by_hash_and_the_index_agrees() {
let entries = many(400);
let h = htree();
let blocks = h.build_blocks(&entries, BS).unwrap();
let index = read_dx_entries(&blocks[0].bytes, DX_ROOT_COUNT_OFFSET).unwrap();
for (k, entry) in index.iter().enumerate() {
let block = &blocks[entry.block as usize];
let lower = index[k].hash & !DX_HASH_CONTINUED;
let upper = index.get(k + 1).map(|e| e.hash & !DX_HASH_CONTINUED);
let mut off = 0;
while off < BS - DIR_TAIL_LEN {
let (e, rec_len) = DirEntry::read_from(&block.bytes[off..], BS).unwrap();
if e.inode != 0 {
let major = dir_hash(&e.name, h.version, h.signedness, &h.seed).major;
assert!(major >= lower, "{:?} sorts before its block", e.name);
if let Some(upper) = upper {
assert!(major <= upper, "{:?} sorts after its block", e.name);
}
}
off += rec_len;
}
}
assert_eq!(names(&blocks, BS).len(), 400);
}
#[test]
fn the_index_hashes_rise_and_never_carry_a_stray_continued_bit() {
let blocks = htree().build_blocks(&many(2000), BS).unwrap();
let index = read_dx_entries(&blocks[0].bytes, DX_ROOT_COUNT_OFFSET).unwrap();
assert!(index.len() > 2, "2000 entries need several blocks");
for pair in index.windows(2) {
assert!(
pair[0].hash < pair[1].hash,
"index hashes must strictly rise"
);
}
assert!(index[1..].iter().all(|e| e.hash & DX_HASH_CONTINUED == 0));
}
#[test]
fn each_block_records_whether_its_first_hash_continues_the_previous() {
let h = htree();
let blocks = h.build_blocks(&many(1200), BS).unwrap();
let index = read_dx_entries(&blocks[0].bytes, DX_ROOT_COUNT_OFFSET).unwrap();
assert!(index.len() > 2, "1200 entries need several blocks");
for (k, entry) in index.iter().enumerate().skip(1) {
let prev = &blocks[index[k - 1].block as usize];
let last_major = walk(&prev.bytes)
.iter()
.filter(|(ino, _, _)| *ino != 0)
.map(|(_, name, _)| dir_hash(name, h.version, h.signedness, &h.seed).major)
.next_back()
.expect("a block holds an entry");
let first_major = entry.hash & !DX_HASH_CONTINUED;
let continued = entry.hash & DX_HASH_CONTINUED != 0;
assert_eq!(
continued,
first_major == last_major,
"block {k} records the wrong continuation"
);
}
}
#[test]
fn a_directory_too_large_for_the_root_grows_an_interior_level() {
const SMALL: usize = 1024;
assert_eq!(dx_limit(SMALL, DX_ROOT_COUNT_OFFSET, true), 123);
assert_eq!(dx_limit(SMALL, DX_NODE_COUNT_OFFSET, true), 126);
let entries = many(4600);
let blocks = htree().build_blocks(&entries, SMALL).unwrap();
assert_eq!(read_dx_root_info(&blocks[0].bytes).unwrap().1, 1);
let root = read_dx_entries(&blocks[0].bytes, DX_ROOT_COUNT_OFFSET).unwrap();
assert_eq!(root.len(), 2, "149 entry blocks need two interior nodes");
assert_eq!(root[0], DxEntry { hash: 0, block: 1 });
assert_eq!(root[1].block, 2);
assert_eq!(
blocks[1].kind,
DirBlockKind::Index {
count_offset: DX_NODE_COUNT_OFFSET,
limit: 126
}
);
assert_eq!(blocks[2].kind, blocks[1].kind);
assert!(blocks[3..].iter().all(|b| b.kind == DirBlockKind::Entries));
let mut named: Vec<u32> = Vec::new();
for node in &blocks[1..=2] {
named.extend(
read_dx_entries(&node.bytes, DX_NODE_COUNT_OFFSET)
.unwrap()
.iter()
.map(|e| e.block),
);
}
let expect: Vec<u32> = (3..blocks.len() as u32).collect();
assert_eq!(named, expect);
assert_eq!(names(&blocks, SMALL).len(), 4600);
}
#[test]
fn a_directory_without_dot_entries_is_rejected() {
let entries: Vec<DirEntry> = (0..300)
.map(|i| DirEntry {
inode: 100 + i,
file_type: FileType::RegFile,
name: format!("entry-name-number-{i:06}").into_bytes(),
})
.collect();
assert_eq!(
htree().build_blocks(&entries, BS),
Err(DirError::MissingDotEntries)
);
}
#[test]
fn an_entry_larger_than_a_block_is_rejected() {
let mut entries = dot_entries(12, 2);
entries.push(DirEntry {
inode: 100,
file_type: FileType::RegFile,
name: vec![b'a'; 255],
});
assert!(
LinearDir {
tail_len: DIR_TAIL_LEN
}
.build_blocks(&entries, 128)
.is_err()
);
}
#[test]
fn clearing_checksums_gives_an_index_block_one_more_entry() {
let mut h = htree();
h.checksums = false;
let blocks = h.build_blocks(&many(150), BS).unwrap();
assert_eq!(
blocks[0].kind,
DirBlockKind::Index {
count_offset: DX_ROOT_COUNT_OFFSET,
limit: 508
}
);
}
}