use crate::bytes::{le_u16, le_u32, le_u64};
use crate::container::ContainerResolver;
use crate::error::RefsError;
use crate::metablock::REFS_METADATA_PAGE_SIZE;
use crate::minstore::{MinstorePage, ObjectTable, REFS_ROOT_DIRECTORY_ID};
const RECORD_TYPE_ENTRY: u16 = 0x0030;
const DEFAULT_BAND_CLUSTERS: u64 = 16_384;
const MAX_DESCENT_DEPTH: usize = 64;
const MAX_VISITED_PAGES: usize = 4096;
const ENTRY_TYPE_FILE: u16 = 1;
const ENTRY_TYPE_DIRECTORY: u16 = 2;
const RESIDENT_VIRTUAL_BASE: u64 = 65_536;
const OBJECT_TABLE_CLUSTER: u64 = 56;
const CLUSTER_SIZE: usize = 4096;
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct FileMetadata {
pub size: u64,
pub allocated: u64,
pub created: u64,
pub modified: u64,
pub accessed: u64,
pub changed: u64,
pub attributes: u32,
pub is_directory: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct DirEntry {
pub name: String,
pub is_directory: bool,
pub object_id: Option<u64>,
pub metadata: Option<FileMetadata>,
}
fn decode_utf16le(bytes: &[u8]) -> String {
let units: Vec<u16> = bytes
.chunks_exact(2)
.map(|c| u16::from_le_bytes([c[0], c[1]]))
.collect();
char::decode_utf16(units)
.map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER))
.collect()
}
fn parse_metadata(value: &[u8], is_directory: bool) -> FileMetadata {
if is_directory {
FileMetadata {
size: 0,
allocated: 0,
created: le_u64(value, 16),
modified: le_u64(value, 24),
changed: le_u64(value, 32),
accessed: le_u64(value, 40),
attributes: le_u32(value, 64),
is_directory: true,
}
} else {
FileMetadata {
size: le_u64(value, 64),
allocated: le_u64(value, 72),
created: le_u64(value, 0),
modified: le_u64(value, 8),
changed: le_u64(value, 16),
accessed: le_u64(value, 24),
attributes: le_u32(value, 32),
is_directory: false,
}
}
}
pub fn parse_directory(page: &[u8]) -> Result<Vec<DirEntry>, RefsError> {
let node = MinstorePage::parse(page, 0)?;
let mut out = Vec::new();
collect_entries(&node, &mut out);
Ok(out)
}
fn resident_block_offset(block: u64, image_len: usize) -> Option<usize> {
let candidates = if block >= RESIDENT_VIRTUAL_BASE {
[Some(block - RESIDENT_VIRTUAL_BASE), Some(block)]
} else {
[Some(block), None]
};
for cluster in candidates.into_iter().flatten() {
let off = usize::try_from(cluster).ok()?.checked_mul(CLUSTER_SIZE)?;
if off.checked_add(REFS_METADATA_PAGE_SIZE)? <= image_len {
return Some(off);
}
}
None
}
fn object_table(image: &[u8]) -> Result<ObjectTable<'_>, RefsError> {
let off = usize::try_from(OBJECT_TABLE_CLUSTER)
.ok()
.and_then(|c| c.checked_mul(CLUSTER_SIZE))
.ok_or(RefsError::Truncated {
structure: "object table (offset overflow)",
need: usize::MAX,
have: image.len(),
})?;
let page = image.get(off..).ok_or(RefsError::Truncated {
structure: "object table page",
need: off,
have: image.len(),
})?;
ObjectTable::parse(page, off as u64)
}
const MSB_SIGNATURE: &[u8; 4] = b"MSB+";
const SELF_BLOCK_OFFSET: usize = 0x20;
fn page_answers_block(image: &[u8], off: usize, block: u64) -> bool {
let Some(page) = image.get(off..off + REFS_METADATA_PAGE_SIZE) else {
return false;
};
page.get(0..4) == Some(MSB_SIGNATURE.as_slice()) && le_u64(page, SELF_BLOCK_OFFSET) == block
}
fn resolve_block_offset(image: &[u8], resolver: &ContainerResolver, block: u64) -> Option<usize> {
if let Some(off) = resolver
.resolve_virtual(block)
.and_then(|o| usize::try_from(o).ok())
{
if page_answers_block(image, off, block) {
return Some(off);
}
}
if let Some(off) = resident_block_offset(block, image.len()) {
if page_answers_block(image, off, block) {
return Some(off);
}
}
None
}
fn read_page<'a>(
image: &'a [u8],
resolver: &ContainerResolver,
block: u64,
) -> Result<&'a [u8], RefsError> {
let off = resolve_block_offset(image, resolver, block)
.ok_or(RefsError::UnresolvedVirtualBlock { block })?;
image
.get(off..off + REFS_METADATA_PAGE_SIZE)
.ok_or(RefsError::Truncated {
structure: "directory page",
need: off + REFS_METADATA_PAGE_SIZE,
have: image.len(),
})
}
fn descend(
image: &[u8],
resolver: &ContainerResolver,
block: u64,
depth: usize,
visited: &mut Vec<u64>,
out: &mut Vec<DirEntry>,
) -> Result<(), RefsError> {
if depth >= MAX_DESCENT_DEPTH || visited.len() >= MAX_VISITED_PAGES {
return Ok(());
}
if visited.contains(&block) {
return Ok(());
}
visited.push(block);
let page = read_page(image, resolver, block)?;
let node = MinstorePage::parse(page, 0)?;
if node.is_branch() {
for row in node.rows() {
let Some(child_bytes) = row.value.get(0..8) else {
continue;
};
let child = le_u64(child_bytes, 0);
descend(image, resolver, child, depth + 1, visited, out)?;
}
} else {
collect_entries(&node, out);
}
Ok(())
}
fn collect_entries(node: &MinstorePage<'_>, out: &mut Vec<DirEntry>) {
for row in node.rows() {
if le_u16(row.key, 0) != RECORD_TYPE_ENTRY {
continue;
}
let entry_type = le_u16(row.key, 2);
let name = decode_utf16le(row.key.get(4..).unwrap_or(&[]));
let is_directory = entry_type == ENTRY_TYPE_DIRECTORY;
let (object_id, metadata) = match entry_type {
ENTRY_TYPE_DIRECTORY => (
Some(le_u64(row.value, 0)),
Some(parse_metadata(row.value, true)),
),
ENTRY_TYPE_FILE => (None, Some(parse_metadata(row.value, false))),
_ => (None, None),
};
out.push(DirEntry {
name,
is_directory,
object_id,
metadata,
});
}
}
pub fn list_dir(image: &[u8], dir_object_id: u64) -> Result<Vec<DirEntry>, RefsError> {
let ot = object_table(image)?;
let root_block = ot
.lookup(dir_object_id)
.ok_or(RefsError::ObjectIdNotFound {
object_id: dir_object_id,
})?
.block_number;
walk_directory(image, root_block)
}
pub fn walk_directory(image: &[u8], root_block: u64) -> Result<Vec<DirEntry>, RefsError> {
let resolver = ContainerResolver::from_resident_image(image, DEFAULT_BAND_CLUSTERS);
let mut out = Vec::new();
let mut visited = Vec::new();
descend(image, &resolver, root_block, 0, &mut visited, &mut out)?;
Ok(out)
}
#[must_use]
pub fn find_by_path(image: &[u8], path: &str) -> Option<(u64, FileMetadata)> {
let components: Vec<&str> = path.split('/').filter(|c| !c.is_empty()).collect();
if components.is_empty() {
return None; }
let mut dir_id = REFS_ROOT_DIRECTORY_ID;
for (i, component) in components.iter().enumerate() {
let entries = list_dir(image, dir_id).ok()?;
let entry = entries.into_iter().find(|e| e.name == *component)?;
let is_last = i + 1 == components.len();
if is_last {
return entry.metadata.map(|md| (dir_id, md));
}
dir_id = entry.object_id?;
}
None }
#[cfg(test)]
mod tests {
use super::*;
fn header_only_page(signature: [u8; 4], self_block: u64) -> Vec<u8> {
let mut page = vec![0u8; REFS_METADATA_PAGE_SIZE];
page[0..4].copy_from_slice(&signature);
page[SELF_BLOCK_OFFSET..SELF_BLOCK_OFFSET + 8].copy_from_slice(&self_block.to_le_bytes());
page
}
#[test]
fn page_answers_block_rejects_out_of_bounds_offset() {
let image = vec![0u8; REFS_METADATA_PAGE_SIZE];
assert!(!page_answers_block(&image, REFS_METADATA_PAGE_SIZE, 0));
}
#[test]
fn page_answers_block_rejects_wrong_signature_and_wrong_self_block() {
let not_msb = header_only_page(*b"SUPB", 7);
assert!(!page_answers_block(¬_msb, 0, 7));
let msb = header_only_page(*b"MSB+", 7);
assert!(!page_answers_block(&msb, 0, 8));
assert!(page_answers_block(&msb, 0, 7));
}
#[test]
fn resolve_block_offset_uses_resident_heuristic_when_resolver_cannot_map() {
let mut image = vec![0u8; 64 * CLUSTER_SIZE];
let page = header_only_page(*b"MSB+", 8);
image[8 * CLUSTER_SIZE..8 * CLUSTER_SIZE + REFS_METADATA_PAGE_SIZE].copy_from_slice(&page);
let empty_resolver = ContainerResolver::from_resident_image(&[], 0);
let off = resolve_block_offset(&image, &empty_resolver, 8);
assert_eq!(
off,
Some(8 * CLUSTER_SIZE),
"resident heuristic lands block 8"
);
}
#[test]
fn resolve_block_offset_none_when_no_strategy_answers() {
let image = vec![0u8; 64 * CLUSTER_SIZE];
let empty_resolver = ContainerResolver::from_resident_image(&[], 0);
assert_eq!(resolve_block_offset(&image, &empty_resolver, 8), None);
}
#[test]
fn descend_branch_row_with_short_value_is_skipped_not_panicked() {
let mut page = vec![0u8; REFS_METADATA_PAGE_SIZE];
page[0..4].copy_from_slice(b"MSB+");
page[SELF_BLOCK_OFFSET..SELF_BLOCK_OFFSET + 8].copy_from_slice(&4u64.to_le_bytes());
let node_hdr = 0x100usize;
page[0x50..0x54].copy_from_slice(&((node_hdr - 0x50) as u32).to_le_bytes());
let rec = node_hdr + 32;
let key = [0u8; 4];
let value = [0u8; 4]; let key_off = 16u16;
let val_off = key_off + key.len() as u16;
let rec_size = (val_off as usize + value.len()) as u32;
page[rec..rec + 4].copy_from_slice(&rec_size.to_le_bytes());
page[rec + 4..rec + 6].copy_from_slice(&key_off.to_le_bytes());
page[rec + 6..rec + 8].copy_from_slice(&(key.len() as u16).to_le_bytes());
page[rec + 10..rec + 12].copy_from_slice(&val_off.to_le_bytes());
page[rec + 12..rec + 14].copy_from_slice(&(value.len() as u16).to_le_bytes());
let roff_abs = node_hdr + 0x2000;
page[roff_abs..roff_abs + 4]
.copy_from_slice(&(0xffff_0000u32 | ((rec - node_hdr) as u32 & 0xffff)).to_le_bytes());
page[node_hdr + 13] = 0x01; page[node_hdr + 16..node_hdr + 20].copy_from_slice(&0x2000u32.to_le_bytes());
page[node_hdr + 20..node_hdr + 24].copy_from_slice(&1u32.to_le_bytes());
let mut image = vec![0u8; 16 * CLUSTER_SIZE];
image[4 * CLUSTER_SIZE..4 * CLUSTER_SIZE + REFS_METADATA_PAGE_SIZE].copy_from_slice(&page);
let entries =
walk_directory(&image, 4).expect("walk does not panic on a short branch value");
assert!(entries.is_empty(), "the short-value branch row was skipped");
}
}