use super::{ParseError, get_u16, get_u32, put_u8, put_u16, put_u32};
pub const DX_ENTRY_LEN: usize = 8;
pub const DX_TAIL_LEN: usize = 8;
pub const DX_CHECKSUM_OFFSET: usize = 4;
pub const DX_ROOT_COUNT_OFFSET: usize = 32;
pub const DX_NODE_COUNT_OFFSET: usize = 8;
pub const DX_HASH_CONTINUED: u32 = 1;
pub const DX_MAX_INDIRECT_LEVELS: u8 = 1;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct DxEntry {
pub hash: u32,
pub block: u32,
}
#[must_use]
pub const fn dx_limit(block_size: usize, count_offset: usize, checksums: bool) -> usize {
let slots = block_size.saturating_sub(count_offset) / DX_ENTRY_LEN;
if checksums {
slots.saturating_sub(1)
} else {
slots
}
}
#[must_use]
pub const fn dx_tail_offset(count_offset: usize, limit: usize) -> usize {
count_offset + DX_ENTRY_LEN * limit
}
pub fn write_dx_root_header(
buf: &mut [u8],
dir_ino: u32,
parent_ino: u32,
hash_version: u8,
indirect_levels: u8,
) -> Result<(), ParseError> {
if buf.len() < DX_ROOT_COUNT_OFFSET {
return Err(ParseError::TooShort {
structure: "DxRoot",
need: DX_ROOT_COUNT_OFFSET,
got: buf.len(),
});
}
let block_size = buf.len();
put_u32(buf, 0, dir_ino);
put_u16(buf, 4, 12);
put_u8(buf, 6, 1);
put_u8(buf, 7, super::FileType::Dir.to_u8());
buf[8] = b'.';
put_u32(buf, 12, parent_ino);
put_u16(buf, 16, (block_size - 12) as u16);
put_u8(buf, 18, 2);
put_u8(buf, 19, super::FileType::Dir.to_u8());
buf[20] = b'.';
buf[21] = b'.';
put_u32(buf, 24, 0); put_u8(buf, 28, hash_version);
put_u8(buf, 29, 8); put_u8(buf, 30, indirect_levels);
put_u8(buf, 31, 0); Ok(())
}
pub fn write_dx_node_header(buf: &mut [u8]) -> Result<(), ParseError> {
if buf.len() < DX_NODE_COUNT_OFFSET {
return Err(ParseError::TooShort {
structure: "DxNode",
need: DX_NODE_COUNT_OFFSET,
got: buf.len(),
});
}
let block_size = buf.len();
put_u32(buf, 0, 0); put_u16(buf, 4, block_size as u16); put_u8(buf, 6, 0); put_u8(buf, 7, 0); Ok(())
}
pub fn write_dx_entries(
buf: &mut [u8],
count_offset: usize,
limit: usize,
entries: &[DxEntry],
) -> Result<(), ParseError> {
if entries.is_empty() || entries.len() > limit {
return Err(ParseError::InvalidField {
structure: "DxEntries",
field: "count",
value: entries.len() as u64,
});
}
if entries[0].hash != 0 {
return Err(ParseError::InvalidField {
structure: "DxEntries",
field: "hash",
value: u64::from(entries[0].hash),
});
}
if buf.len() < dx_tail_offset(count_offset, limit) {
return Err(ParseError::TooShort {
structure: "DxEntries",
need: dx_tail_offset(count_offset, limit),
got: buf.len(),
});
}
put_u16(buf, count_offset, limit as u16);
put_u16(buf, count_offset + 2, entries.len() as u16);
put_u32(buf, count_offset + 4, entries[0].block);
for (i, entry) in entries.iter().enumerate().skip(1) {
let off = count_offset + DX_ENTRY_LEN * i;
put_u32(buf, off, entry.hash);
put_u32(buf, off + 4, entry.block);
}
Ok(())
}
pub fn write_dx_tail(
buf: &mut [u8],
count_offset: usize,
limit: usize,
checksum: u32,
) -> Result<(), ParseError> {
let off = dx_tail_offset(count_offset, limit);
if buf.len() < off + DX_TAIL_LEN {
return Err(ParseError::TooShort {
structure: "DxTail",
need: off + DX_TAIL_LEN,
got: buf.len(),
});
}
put_u32(buf, off, 0); put_u32(buf, off + DX_CHECKSUM_OFFSET, checksum);
Ok(())
}
pub fn read_dx_countlimit(buf: &[u8], count_offset: usize) -> Result<(u16, u16), ParseError> {
if buf.len() < count_offset + 4 {
return Err(ParseError::TooShort {
structure: "DxCountLimit",
need: count_offset + 4,
got: buf.len(),
});
}
let limit = get_u16(buf, count_offset);
let count = get_u16(buf, count_offset + 2);
if count > limit || count == 0 {
return Err(ParseError::InvalidField {
structure: "DxCountLimit",
field: "count",
value: u64::from(count),
});
}
Ok((limit, count))
}
pub fn read_dx_entries(buf: &[u8], count_offset: usize) -> Result<Vec<DxEntry>, ParseError> {
let (_, count) = read_dx_countlimit(buf, count_offset)?;
let need = count_offset + DX_ENTRY_LEN * count as usize;
if buf.len() < need {
return Err(ParseError::TooShort {
structure: "DxEntries",
need,
got: buf.len(),
});
}
let mut out = Vec::with_capacity(count as usize);
out.push(DxEntry {
hash: 0,
block: get_u32(buf, count_offset + 4),
});
for i in 1..count as usize {
let off = count_offset + DX_ENTRY_LEN * i;
out.push(DxEntry {
hash: get_u32(buf, off),
block: get_u32(buf, off + 4),
});
}
Ok(out)
}
pub fn read_dx_root_info(buf: &[u8]) -> Result<(u8, u8), ParseError> {
if buf.len() < DX_ROOT_COUNT_OFFSET {
return Err(ParseError::TooShort {
structure: "DxRootInfo",
need: DX_ROOT_COUNT_OFFSET,
got: buf.len(),
});
}
Ok((buf[28], buf[30]))
}
#[cfg(test)]
mod tests {
use super::*;
const BS: usize = 4096;
#[test]
fn a_root_reserves_five_hundred_and_seven_entries_under_checksums() {
assert_eq!(dx_limit(BS, DX_ROOT_COUNT_OFFSET, false), 508);
assert_eq!(dx_limit(BS, DX_ROOT_COUNT_OFFSET, true), 507);
assert_eq!(dx_tail_offset(DX_ROOT_COUNT_OFFSET, 507), 4088);
assert_eq!(dx_tail_offset(DX_ROOT_COUNT_OFFSET, 507) + DX_TAIL_LEN, BS);
}
#[test]
fn a_node_reserves_five_hundred_and_ten_entries_under_checksums() {
assert_eq!(dx_limit(BS, DX_NODE_COUNT_OFFSET, false), 511);
assert_eq!(dx_limit(BS, DX_NODE_COUNT_OFFSET, true), 510);
assert_eq!(dx_tail_offset(DX_NODE_COUNT_OFFSET, 510), 4088);
}
#[test]
fn a_block_with_no_room_for_an_entry_holds_none() {
assert_eq!(dx_limit(32, 32, false), 0);
assert_eq!(dx_limit(32, 64, false), 0);
assert_eq!(dx_limit(0, DX_ROOT_COUNT_OFFSET, true), 0);
assert_eq!(dx_limit(DX_ENTRY_LEN + 8, 8, false), 1);
assert_eq!(dx_limit(DX_ENTRY_LEN + 8, 8, true), 0);
}
#[test]
fn a_root_block_matches_e2fsprogs_byte_for_byte() {
let entries = [
DxEntry { hash: 0, block: 1 },
DxEntry {
hash: 0x5c92_21be,
block: 2,
},
DxEntry {
hash: 0xac20_57fe,
block: 3,
},
];
let mut buf = vec![0u8; BS];
write_dx_root_header(&mut buf, 12, 2, 1, 0).unwrap();
write_dx_entries(&mut buf, DX_ROOT_COUNT_OFFSET, 507, &entries).unwrap();
write_dx_tail(&mut buf, DX_ROOT_COUNT_OFFSET, 507, 0xa42b_897b).unwrap();
#[rustfmt::skip]
let expect_head: [u8; 56] = [
0x0c, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x01, 0x02, b'.', 0x00, 0x00, 0x00,
0x02, 0x00, 0x00, 0x00, 0xf4, 0x0f, 0x02, 0x02, b'.', b'.', 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x08, 0x00, 0x00,
0xfb, 0x01, 0x03, 0x00, 0x01, 0x00, 0x00, 0x00,
0xbe, 0x21, 0x92, 0x5c, 0x02, 0x00, 0x00, 0x00,
0xfe, 0x57, 0x20, 0xac, 0x03, 0x00, 0x00, 0x00,
];
assert_eq!(&buf[..56], &expect_head[..]);
assert_eq!(&buf[4088..4092], &[0, 0, 0, 0]);
assert_eq!(&buf[4092..], &0xa42b_897bu32.to_le_bytes()[..]);
assert!(buf[56..4088].iter().all(|&b| b == 0));
}
#[test]
fn a_root_block_reads_back_as_a_dot_entry_hiding_the_index() {
use super::super::DirEntry;
let entries = [DxEntry { hash: 0, block: 1 }, DxEntry { hash: 8, block: 2 }];
let mut buf = vec![0u8; BS];
write_dx_root_header(&mut buf, 12, 2, 1, 0).unwrap();
write_dx_entries(&mut buf, DX_ROOT_COUNT_OFFSET, 507, &entries).unwrap();
let (dot, dot_len) = DirEntry::read_from(&buf, 4096).unwrap();
assert_eq!(dot.name, b".");
assert_eq!(dot_len, 12);
let (dotdot, dotdot_len) = DirEntry::read_from(&buf[12..], 4096).unwrap();
assert_eq!(dotdot.name, b"..");
assert_eq!(dotdot.inode, 2);
assert_eq!(12 + dotdot_len, BS, "the index is not walked");
}
#[test]
fn a_node_block_reads_back_as_one_unused_slot() {
use super::super::DirEntry;
let mut buf = vec![0u8; BS];
write_dx_node_header(&mut buf).unwrap();
write_dx_entries(
&mut buf,
DX_NODE_COUNT_OFFSET,
510,
&[DxEntry { hash: 0, block: 5 }],
)
.unwrap();
let (entry, rec_len) = DirEntry::read_from(&buf, 4096).unwrap();
assert_eq!(entry.inode, 0, "an unused slot a linear walk skips");
assert_eq!(rec_len, BS);
}
#[test]
fn entries_round_trip_with_the_first_hash_implied() {
let entries = vec![
DxEntry { hash: 0, block: 1 },
DxEntry {
hash: 0xdead_be00,
block: 7,
},
];
let mut buf = vec![0u8; BS];
write_dx_entries(&mut buf, DX_ROOT_COUNT_OFFSET, 507, &entries).unwrap();
assert_eq!(
read_dx_countlimit(&buf, DX_ROOT_COUNT_OFFSET).unwrap(),
(507, 2)
);
assert_eq!(
read_dx_entries(&buf, DX_ROOT_COUNT_OFFSET).unwrap(),
entries
);
}
#[test]
fn the_root_info_reads_back() {
let mut buf = vec![0u8; BS];
write_dx_root_header(&mut buf, 12, 2, 2, 1).unwrap();
assert_eq!(read_dx_root_info(&buf).unwrap(), (2, 1));
}
#[test]
fn a_stored_hash_on_the_first_entry_is_rejected() {
let mut buf = vec![0u8; BS];
assert!(matches!(
write_dx_entries(
&mut buf,
DX_ROOT_COUNT_OFFSET,
507,
&[DxEntry { hash: 4, block: 1 }]
),
Err(ParseError::InvalidField { field: "hash", .. })
));
}
#[test]
fn more_entries_than_the_limit_are_rejected() {
let mut buf = vec![0u8; BS];
let entries: Vec<DxEntry> = (0..3)
.map(|i| DxEntry {
hash: if i == 0 { 0 } else { i * 8 },
block: i + 1,
})
.collect();
assert!(matches!(
write_dx_entries(&mut buf, DX_ROOT_COUNT_OFFSET, 2, &entries),
Err(ParseError::InvalidField { field: "count", .. })
));
}
}