use std::collections::BTreeMap;
use std::io::{Read, Seek, Write};
use crate::compress::Algorithm;
use crate::fidelity::Synthesis;
use crate::finding::{Family, Severity};
use crate::path::is_hostile_component;
use crate::policy::MAX_PATH;
use crate::source::Metadata;
use crate::time::Timestamp;
use crate::tree::{Attributes, FsTree, NodeKind, TreeEntry, TreeError};
use crate::xattr::Xattr;
use crate::{Limits, OpenOptions, ReadPolicy};
use super::decode;
use super::ondisk::{
DirEntryType, DirItem, DiskKey, ExtentKind, FileExtentItem, InodeItem, ItemType, RootFlags,
RootItem, RootRef, for_each_packed, name_hash, objectid,
};
use super::scan::{
Category, Scan, ScanReport, has_live_log, mirror_anomaly, tree_name, walk_anomaly,
};
use super::volume::{ReadError, TreeRoot, Volume};
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Node {
pub tree: u64,
pub inode: u64,
pub item: InodeItem,
}
impl Node {
#[must_use]
pub const fn is_dir(&self) -> bool {
self.item.mode_type() == MODE_DIR
}
#[must_use]
pub const fn is_file(&self) -> bool {
self.item.mode_type() == MODE_REG
}
#[must_use]
pub const fn is_symlink(&self) -> bool {
self.item.mode_type() == MODE_LNK
}
}
const MODE_DIR: u32 = 0o040_000;
const MODE_REG: u32 = 0o100_000;
const MODE_LNK: u32 = 0o120_000;
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct Entry {
pub name: Vec<u8>,
pub kind: DirEntryType,
pub location: DiskKey,
pub index: u64,
}
impl Entry {
#[must_use]
pub const fn is_subvolume(&self) -> bool {
matches!(self.location.kind, ItemType::ROOT_ITEM)
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct Subvolume {
pub id: u64,
pub root: TreeRoot,
pub root_dir: u64,
pub read_only: bool,
pub uuid: [u8; 16],
pub parent_uuid: [u8; 16],
pub otime: Timestamp,
pub parent: Option<u64>,
pub parent_dir: u64,
pub name: Vec<u8>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct WalkEntry {
pub path: Vec<u8>,
pub node: Node,
}
pub struct Reader<R> {
volume: Volume<R>,
subvolumes: Vec<Subvolume>,
top: Subvolume,
default_subvolume: u64,
}
impl<R: Read + Seek> Reader<R> {
pub fn open(src: R) -> Result<Self, ReadError> {
Self::open_with(src, &OpenOptions::new())
}
pub fn open_with(src: R, options: &OpenOptions) -> Result<Self, ReadError> {
let mut volume = Volume::open_with(src, *options)?;
let subvolumes = read_subvolumes(&mut volume)?;
let top = subvolumes
.iter()
.find(|sub| sub.id == objectid::FS_TREE)
.cloned()
.ok_or(ReadError::MissingTree {
objectid: objectid::FS_TREE,
})?;
let default_subvolume = read_default_subvolume(&mut volume)?.unwrap_or(objectid::FS_TREE);
Ok(Self {
volume,
subvolumes,
top,
default_subvolume,
})
}
#[must_use]
pub fn volume(&self) -> &Volume<R> {
&self.volume
}
pub fn volume_mut(&mut self) -> &mut Volume<R> {
&mut self.volume
}
#[must_use]
pub fn into_volume(self) -> Volume<R> {
self.volume
}
#[must_use]
pub fn policy(&self) -> ReadPolicy {
self.volume.policy()
}
#[must_use]
pub fn limits(&self) -> Limits {
self.volume.limits()
}
#[must_use]
pub fn subvolumes(&self) -> &[Subvolume] {
&self.subvolumes
}
#[must_use]
pub fn top_level(&self) -> &Subvolume {
&self.top
}
#[must_use]
pub fn default_subvolume(&self) -> u64 {
self.default_subvolume
}
pub fn root(&mut self) -> Result<Node, ReadError> {
let top = self.top.clone();
self.inode(top.id, top.root_dir)
}
pub fn inode(&mut self, tree: u64, inode: u64) -> Result<Node, ReadError> {
let root = self.tree_root(tree)?;
let key = DiskKey::new(inode, ItemType::INODE_ITEM, 0);
let found = self
.volume
.tree(root)
.find_exact(key)?
.ok_or(ReadError::MissingInode { tree, inode })?;
Ok(Node {
tree,
inode,
item: InodeItem::read_from(&found.data)?,
})
}
pub fn read_dir(&mut self, node: &Node) -> Result<Vec<Entry>, ReadError> {
if !node.is_dir() {
return Err(ReadError::NotADirectory { path: Vec::new() });
}
let root = self.tree_root(node.tree)?;
let from = DiskKey::first_of(node.inode, ItemType::DIR_INDEX);
let mut entries = Vec::new();
let mut failure = None;
self.volume
.tree(root)
.for_each_item_from(from, |key, data| {
if key.objectid != node.inode || key.kind != ItemType::DIR_INDEX {
return false;
}
let framed = for_each_packed::<DirItem, _>(data, |head, tail| {
let (name, _) = head.split(tail);
entries.push(Entry {
name: name.to_vec(),
kind: head.kind,
location: head.location,
index: key.offset,
});
true
});
match framed {
Ok(()) => true,
Err(e) => {
failure = Some(e.into());
false
}
}
})?;
match failure {
Some(e) => Err(e),
None => Ok(entries),
}
}
pub fn lookup(&mut self, path: &[u8]) -> Result<Node, ReadError> {
self.resolve(path, true)
}
pub fn lookup_no_follow(&mut self, path: &[u8]) -> Result<Node, ReadError> {
self.resolve(path, false)
}
fn resolve(&mut self, path: &[u8], follow_final: bool) -> Result<Node, ReadError> {
crate::resolve::drive(self, path, follow_final)
}
pub fn find_entry(&mut self, dir: &Node, name: &[u8]) -> Result<Option<Entry>, ReadError> {
let root = self.tree_root(dir.tree)?;
let key = DiskKey::new(dir.inode, ItemType::DIR_ITEM, name_hash(name));
let Some(found) = self.volume.tree(root).find_exact(key)? else {
return Ok(None);
};
let mut entry = None;
for_each_packed::<DirItem, _>(&found.data, |head, tail| {
let (stored, _) = head.split(tail);
if stored == name {
entry = Some(Entry {
name: stored.to_vec(),
kind: head.kind,
location: head.location,
index: 0,
});
return false;
}
true
})?;
Ok(entry)
}
pub fn step(&mut self, dir: &Node, entry: &Entry) -> Result<Node, ReadError> {
self.at_location(dir.tree, entry.location)
}
pub fn xattrs(&mut self, node: &Node) -> Result<Vec<Xattr>, ReadError> {
let root = self.tree_root(node.tree)?;
let from = DiskKey::first_of(node.inode, ItemType::XATTR_ITEM);
let mut out = Vec::new();
let mut failure = None;
self.volume
.tree(root)
.for_each_item_from(from, |key, data| {
if key.objectid != node.inode || key.kind != ItemType::XATTR_ITEM {
return false;
}
let framed = for_each_packed::<DirItem, _>(data, |head, tail| {
let (name, value) = head.split(tail);
out.push(Xattr {
name: name.to_vec(),
value: value.to_vec(),
});
true
});
match framed {
Ok(()) => true,
Err(_) => {
failure = Some(ReadError::BadXattr {
tree: node.tree,
inode: node.inode,
});
false
}
}
})?;
match failure {
Some(e) => Err(e),
None => Ok(out),
}
}
pub fn read_into(
&mut self,
node: &Node,
offset: u64,
buf: &mut [u8],
) -> Result<usize, ReadError> {
if !node.is_file() && !node.is_symlink() {
return Ok(0);
}
let size = node.item.size;
if offset >= size || buf.is_empty() {
return Ok(0);
}
let want = buf.len().min((size - offset) as usize);
let out = &mut buf[..want];
out.fill(0);
let end = offset + want as u64;
for (at, item, raw) in self.extent_records(node, offset, end)? {
self.place_extent(node, at, &item, &raw, offset, out)?;
}
Ok(want)
}
pub fn read_data(&mut self, node: &Node) -> Result<Vec<u8>, ReadError> {
let size = node.item.size;
let cap = self.limits().max_file_bytes.min(isize::MAX as u64);
if size > cap {
return Err(ReadError::FileTooLarge {
tree: node.tree,
inode: node.inode,
size,
cap,
});
}
let mut out = vec![0u8; size as usize];
let mut at = 0usize;
while at < out.len() {
let placed = self.read_into(node, at as u64, &mut out[at..])?;
if placed == 0 {
break;
}
at += placed;
}
out.truncate(at);
Ok(out)
}
pub fn read_data_to(&mut self, node: &Node, mut out: impl Write) -> Result<u64, ReadError> {
let mut buf = vec![0u8; STREAM_BUFFER];
let mut at = 0u64;
loop {
let placed = self.read_into(node, at, &mut buf)?;
if placed == 0 {
return Ok(at);
}
out.write_all(&buf[..placed])?;
at += placed as u64;
}
}
pub fn link_target(&mut self, node: &Node) -> Result<Vec<u8>, ReadError> {
if !node.is_symlink() {
return Err(ReadError::NotASymlink {
tree: node.tree,
inode: node.inode,
});
}
self.read_data(node)
}
pub fn walk(&mut self) -> Result<Vec<WalkEntry>, ReadError> {
let mut out = Vec::new();
self.walk_with::<ReadError, _>(|_, entry| {
out.push(entry);
Ok(())
})?;
Ok(out)
}
pub fn walk_with<E, F>(&mut self, mut visit: F) -> Result<(), E>
where
E: From<ReadError>,
F: FnMut(&mut Self, WalkEntry) -> Result<(), E>,
{
let root = self.root().map_err(E::from)?;
visit(
self,
WalkEntry {
path: Vec::new(),
node: root,
},
)?;
crate::walk::drive(self, |reader, entry| visit(reader, entry))
}
#[must_use]
pub fn scan(&mut self) -> ScanReport {
let mut scan = Scan::new(self.limits().max_findings);
let live = self.volume.superblock().generation;
for (index, &state) in self.volume.mirrors().iter().enumerate() {
if let Some((severity, detail)) = mirror_anomaly(state, live) {
scan.at(
Category::Superblock,
severity,
None,
None,
format!("copy {index} of the superblock: {detail}"),
);
}
}
if has_live_log(&self.volume) {
scan.at(
Category::Superblock,
Severity::Cosmetic,
None,
Some(self.volume.superblock().log_root),
"the filesystem was not cleanly unmounted and holds a log tree; what is read \
here is the last committed transaction, without the writes the log holds"
.to_string(),
);
}
let roots = match self.volume.tree_roots() {
Ok(roots) => roots,
Err(e) => {
let (category, severity) = walk_anomaly(&e);
scan.at(
category,
severity,
Some(objectid::ROOT_TREE),
None,
format!("the root tree, which names every other: {e}"),
);
return scan.finish();
}
};
for &root in &roots {
if scan.found.is_full() {
break;
}
let walked = self.volume.tree(root).for_each_item(|key, _| {
scan.met_unknown(key.kind);
!scan.found.is_full()
});
if let Err(e) = walked {
let (category, severity) = walk_anomaly(&e);
scan.at(
category,
severity,
Some(root.objectid),
Some(root.bytenr),
format!("{}: {e}", tree_name(root.objectid)),
);
}
}
self.scan_uuid_mapping(&roots, &mut scan);
scan.finish()
}
fn scan_uuid_mapping(&mut self, roots: &[TreeRoot], scan: &mut Scan) {
let Some(&uuid_root) = roots
.iter()
.find(|root| root.objectid == objectid::UUID_TREE)
else {
return;
};
let recorded: std::collections::HashMap<u64, [u8; 16]> = self
.subvolumes
.iter()
.map(|sub| (sub.id, sub.uuid))
.collect();
let mut satisfied: std::collections::HashSet<u64> = std::collections::HashSet::new();
let walked = self.volume.tree(uuid_root).for_each_item(|key, data| {
if key.kind != ItemType::UUID_SUBVOL {
return true;
}
let mut uuid = [0u8; 16];
uuid[..8].copy_from_slice(&key.objectid.to_le_bytes());
uuid[8..].copy_from_slice(&key.offset.to_le_bytes());
if data.is_empty() || data.len() % 8 != 0 {
scan.at(
Category::Item,
Severity::Structural,
Some(objectid::UUID_TREE),
None,
format!(
"the UUID tree's entry for {} holds {} bytes, which is not a list of \
8-byte subvolume ids",
crate::escape::hex(&uuid),
data.len()
),
);
return !scan.found.is_full();
}
for id in data.as_chunks::<8>().0 {
let id = u64::from_le_bytes(*id);
match recorded.get(&id) {
Some(held) if *held == uuid => {
satisfied.insert(id);
}
Some(_) => scan.at(
Category::Item,
Severity::Structural,
Some(objectid::UUID_TREE),
None,
format!(
"the UUID tree maps identifier {} to subvolume {id}, whose root \
item records a different identifier",
crate::escape::hex(&uuid)
),
),
None => scan.at(
Category::Item,
Severity::Structural,
Some(objectid::UUID_TREE),
None,
format!(
"the UUID tree maps identifier {} to subvolume {id}, which does \
not exist",
crate::escape::hex(&uuid)
),
),
}
}
!scan.found.is_full()
});
if walked.is_err() {
return;
}
for sub in &self.subvolumes {
if scan.found.is_full() {
break;
}
if sub.uuid != [0; 16] && !satisfied.contains(&sub.id) {
scan.at(
Category::Item,
Severity::Structural,
Some(objectid::UUID_TREE),
None,
format!(
"subvolume {} records identifier {} and the UUID tree has no entry \
mapping it back",
sub.id,
crate::escape::hex(&sub.uuid)
),
);
}
}
}
pub fn verify_data(&mut self, node: &Node) -> Result<(), ReadError> {
if !node.is_file() && !node.is_symlink() {
return Ok(());
}
if node
.item
.flags
.contains(super::ondisk::InodeFlags::NODATASUM)
{
return Ok(());
}
let sector = u64::from(self.volume.superblock().sectorsize);
let records = self.extent_records(node, 0, u64::MAX)?;
for (at, item, _) in records {
if item.kind.is_inline() || item.is_hole() || item.kind == ExtentKind::Prealloc {
continue;
}
let mut logical = item.disk_bytenr;
let end = logical
.checked_add(item.disk_num_bytes)
.ok_or(ReadError::BadExtent {
tree: node.tree,
inode: node.inode,
at,
fault: "the extent's address runs past the end of the address space",
})?;
let mut buf = vec![0u8; sector as usize];
while logical < end {
let take = (end - logical).min(sector) as usize;
self.volume.read_at(logical, &mut buf[..take])?;
let recorded = self
.data_checksum(logical)?
.ok_or(ReadError::MissingDataChecksum { logical })?;
if super::ondisk::crc32c_over(&buf[..take]) != recorded {
return Err(ReadError::DataChecksum { logical });
}
logical += take as u64;
}
}
Ok(())
}
fn data_checksum(&mut self, logical: u64) -> Result<Option<u32>, ReadError> {
let sector = u64::from(self.volume.superblock().sectorsize);
let Some(digest) = self.volume.superblock().csum_type.digest_len() else {
return Ok(None);
};
let root = self.tree_root_of(objectid::CSUM_TREE)?;
let wanted = DiskKey::new(objectid::EXTENT_CSUM, ItemType::EXTENT_CSUM, logical);
let Some(found) = self.volume.tree(root).find_at_or_before(wanted)? else {
return Ok(None);
};
if found.key.objectid != objectid::EXTENT_CSUM || found.key.kind != ItemType::EXTENT_CSUM {
return Ok(None);
}
let covered = (found.data.len() / digest) as u64 * sector;
let end = found.key.offset.checked_add(covered);
if end.is_none_or(|end| logical >= end) {
return Ok(None);
}
let index = ((logical - found.key.offset) / sector) as usize * digest;
Ok((index + 4 <= found.data.len()).then(|| crate::bytes::get_u32(&found.data, index)))
}
fn tree_root_of(&mut self, objectid: u64) -> Result<TreeRoot, ReadError> {
let root_tree = self.volume.root_tree();
let key = DiskKey::new(objectid, ItemType::ROOT_ITEM, 0);
let found = self
.volume
.tree(root_tree)
.find_first(key)?
.filter(|found| found.key.objectid == objectid && found.key.kind == ItemType::ROOT_ITEM)
.ok_or(ReadError::MissingTree { objectid })?;
let item = RootItem::read_from(&found.data)
.map_err(|source| ReadError::BadRootItem { objectid, source })?;
Ok(TreeRoot {
objectid,
bytenr: item.bytenr,
level: item.level,
generation: item.generation,
})
}
fn pending_children(
&mut self,
dir: &Node,
path: &[u8],
) -> Result<Vec<(Vec<u8>, u64, DiskKey)>, ReadError> {
let mut out = Vec::new();
for entry in self.read_dir(dir)? {
if is_hostile_component(&entry.name) {
return Err(ReadError::HostileName { name: entry.name });
}
let child = crate::walk::child_path(path, &entry.name).ok_or_else(|| {
let mut too_long = path.to_vec();
too_long.push(b'/');
too_long.extend_from_slice(&entry.name);
ReadError::PathTooLong { path: too_long }
})?;
out.push((child, dir.tree, entry.location));
}
out.reverse();
Ok(out)
}
fn at_location(&mut self, tree: u64, location: DiskKey) -> Result<Node, ReadError> {
match location.kind {
ItemType::INODE_ITEM => self.inode(tree, location.objectid),
ItemType::ROOT_ITEM => {
let id = location.objectid;
let root_dir = self
.subvolumes
.iter()
.find(|sub| sub.id == id)
.ok_or(ReadError::MissingTree { objectid: id })?
.root_dir;
self.inode(id, root_dir)
}
other => Err(ReadError::BadDirEntry {
tree,
inode: location.objectid,
fault: "the entry names neither an inode nor a subvolume",
kind: other.value(),
}),
}
}
fn tree_root(&self, id: u64) -> Result<TreeRoot, ReadError> {
self.subvolumes
.iter()
.find(|sub| sub.id == id)
.map(|sub| sub.root)
.ok_or(ReadError::MissingTree { objectid: id })
}
fn extent_records(
&mut self,
node: &Node,
offset: u64,
end: u64,
) -> Result<Vec<(u64, FileExtentItem, Vec<u8>)>, ReadError> {
let root = self.tree_root(node.tree)?;
let wanted = DiskKey::new(node.inode, ItemType::EXTENT_DATA, offset);
let covering = self.volume.tree(root).find_at_or_before(wanted)?;
let from = match covering {
Some(found)
if found.key.objectid == node.inode && found.key.kind == ItemType::EXTENT_DATA =>
{
found.key
}
_ => DiskKey::first_of(node.inode, ItemType::EXTENT_DATA),
};
let mut out = Vec::new();
let mut failure = None;
self.volume
.tree(root)
.for_each_item_from(from, |key, data| {
if key.objectid != node.inode
|| key.kind != ItemType::EXTENT_DATA
|| key.offset >= end
{
return false;
}
match FileExtentItem::read_from(data) {
Ok(item) => {
out.push((key.offset, item, data.to_vec()));
true
}
Err(e) => {
failure = Some(e.into());
false
}
}
})?;
match failure {
Some(e) => Err(e),
None => Ok(out),
}
}
fn place_extent(
&mut self,
node: &Node,
at: u64,
item: &FileExtentItem,
raw: &[u8],
offset: u64,
out: &mut [u8],
) -> Result<(), ReadError> {
let bad = |fault: &'static str| ReadError::BadExtent {
tree: node.tree,
inode: node.inode,
at,
fault,
};
let encoding = match decode::algorithm(item.compression) {
None => None,
Some(Some(algorithm)) if algorithm.available() => Some(algorithm),
Some(_) => {
return Err(ReadError::UnsupportedCompression {
tree: node.tree,
inode: node.inode,
compression: item.compression.to_u8(),
});
}
};
if item.encryption != 0 || item.other_encoding != 0 {
return Err(ReadError::UnsupportedEncoding {
tree: node.tree,
inode: node.inode,
encryption: item.encryption,
other: item.other_encoding,
});
}
let covers = if item.kind.is_inline() {
item.ram_bytes
} else {
item.num_bytes
};
let record_end = at
.checked_add(covers)
.ok_or_else(|| bad("the record's length runs past the end of the address space"))?;
let start = at.max(offset);
let stop = record_end.min(offset + out.len() as u64);
if stop <= start {
return Ok(());
}
let into = (start - offset) as usize;
let len = (stop - start) as usize;
let within = start - at;
if item.kind.is_inline() {
let stored = item.inline_data(raw)?;
if let Some(algorithm) = encoding {
let whole = self.expand(node, at, item, algorithm, stored)?;
let from = within as usize;
out[into..into + len].copy_from_slice(&whole[from..from + len]);
return Ok(());
}
if (stored.len() as u64) < covers {
return Err(bad("the record claims more bytes than the item holds"));
}
let from = within as usize;
out[into..into + len].copy_from_slice(&stored[from..from + len]);
return Ok(());
}
if item.is_hole() || item.kind == ExtentKind::Prealloc {
return Ok(());
}
if item.kind != ExtentKind::Regular {
return Err(bad("the record is of a shape this reader does not define"));
}
if let Some(algorithm) = encoding {
if item.disk_num_bytes > decode::MAX_COMPRESSED {
return Err(bad(
"the extent stores more than this format compresses into",
));
}
let mut stored = vec![0u8; item.disk_num_bytes as usize];
self.volume.read_at(item.disk_bytenr, &mut stored)?;
let whole = self.expand(node, at, item, algorithm, &stored)?;
let skip = item
.offset
.checked_add(within)
.ok_or_else(|| bad("the record begins past the end of the extent it names"))?;
let last = skip
.checked_add(len as u64)
.ok_or_else(|| bad("the record's run leaves the extent it names"))?;
if last > whole.len() as u64 {
return Err(bad("the record's run leaves the extent it names"));
}
let from = skip as usize;
out[into..into + len].copy_from_slice(&whole[from..from + len]);
return Ok(());
}
let skip = item
.offset
.checked_add(within)
.ok_or_else(|| bad("the record begins past the end of the extent it names"))?;
let last = skip
.checked_add(len as u64)
.ok_or_else(|| bad("the record's run leaves the extent it names"))?;
if last > item.disk_num_bytes {
return Err(bad("the record's run leaves the extent it names"));
}
let logical = item
.disk_bytenr
.checked_add(skip)
.ok_or_else(|| bad("the record's address runs past the end of the address space"))?;
self.volume.read_at(logical, &mut out[into..into + len])
}
fn expand(
&mut self,
node: &Node,
at: u64,
item: &FileExtentItem,
algorithm: Algorithm,
stored: &[u8],
) -> Result<Vec<u8>, ReadError> {
if item.ram_bytes > decode::MAX_UNCOMPRESSED {
return Err(ReadError::BadExtent {
tree: node.tree,
inode: node.inode,
at,
fault: "the record expands to more than this format compresses in",
});
}
let sector_size = self.volume.superblock().sectorsize;
let mut whole = vec![0u8; item.ram_bytes as usize];
let produced = decode::decode(algorithm, stored, &mut whole, sector_size).map_err(|e| {
ReadError::BadCompressedExtent {
tree: node.tree,
inode: node.inode,
at,
fault: e.to_string(),
}
})?;
if produced != whole.len() {
return Err(ReadError::BadCompressedExtent {
tree: node.tree,
inode: node.inode,
at,
fault: format!(
"it expands to {produced} bytes and the record declares {}",
whole.len()
),
});
}
Ok(whole)
}
}
const STREAM_BUFFER: usize = 1 << 20;
fn read_subvolumes<R: Read + Seek>(volume: &mut Volume<R>) -> Result<Vec<Subvolume>, ReadError> {
let root_tree = volume.root_tree();
let mut items: BTreeMap<u64, (RootItem, TreeRoot)> = BTreeMap::new();
let mut links: BTreeMap<u64, (u64, u64, Vec<u8>)> = BTreeMap::new();
let mut failure = None;
volume.tree(root_tree).for_each_item(|key, data| {
if !is_subvolume_id(key.objectid) {
return true;
}
match key.kind {
ItemType::ROOT_ITEM => match RootItem::read_from(data) {
Ok(item) => {
let root = TreeRoot {
objectid: key.objectid,
bytenr: item.bytenr,
level: item.level,
generation: item.generation,
};
items.insert(key.objectid, (item, root));
true
}
Err(e) => {
failure = Some(ReadError::BadRootItem {
objectid: key.objectid,
source: e,
});
false
}
},
ItemType::ROOT_BACKREF => {
let mut link = None;
let framed = for_each_packed::<RootRef, _>(data, |head, name| {
link = Some((key.offset, head.dirid, name.to_vec()));
false
});
match framed {
Ok(()) => {
if let Some(link) = link {
links.insert(key.objectid, link);
}
true
}
Err(e) => {
failure = Some(e.into());
false
}
}
}
_ => true,
}
})?;
if let Some(e) = failure {
return Err(e);
}
let mut out: Vec<Subvolume> = items
.into_iter()
.map(|(id, (item, root))| {
let (parent, parent_dir, name) = links
.remove(&id)
.map_or((None, 0, Vec::new()), |(parent, dir, name)| {
(Some(parent), dir, name)
});
Subvolume {
id,
root,
root_dir: item.root_dirid,
read_only: item.flags.contains(RootFlags::SUBVOL_RDONLY),
uuid: item.uuid,
parent_uuid: item.parent_uuid,
otime: item.otime,
parent,
parent_dir,
name,
}
})
.collect();
out.sort_by_key(|sub| (sub.id != objectid::FS_TREE, sub.id));
Ok(out)
}
fn read_default_subvolume<R: Read + Seek>(
volume: &mut Volume<R>,
) -> Result<Option<u64>, ReadError> {
let root_tree = volume.root_tree();
let key = DiskKey::new(
objectid::ROOT_TREE_DIR,
ItemType::DIR_ITEM,
name_hash(b"default"),
);
let Some(found) = volume.tree(root_tree).find_exact(key)? else {
return Ok(None);
};
let mut id = None;
for_each_packed::<DirItem, _>(&found.data, |head, tail| {
let (name, _) = head.split(tail);
if name == b"default" && head.location.kind == ItemType::ROOT_ITEM {
id = Some(head.location.objectid);
return false;
}
true
})?;
Ok(id)
}
impl<R: Read + Seek> crate::resolve::Resolve for Reader<R> {
type Ancestor = (u64, u64);
type Node = Node;
type Error = ReadError;
fn root_node(&mut self) -> Result<Node, ReadError> {
self.root()
}
fn ancestor_of(&self, node: &Node) -> (u64, u64) {
(node.tree, node.inode)
}
fn node_at(&mut self, (tree, inode): (u64, u64)) -> Result<Node, ReadError> {
self.inode(tree, inode)
}
fn is_directory(&self, node: &Node) -> bool {
node.is_dir()
}
fn find_name(&mut self, dir: &Node, name: &[u8]) -> Result<Option<Node>, ReadError> {
let Some(entry) = self.find_entry(dir, name)? else {
return Ok(None);
};
Ok(Some(self.step(dir, &entry)?))
}
fn read_link(&mut self, node: &Node, path: &[u8]) -> Result<Option<Vec<u8>>, ReadError> {
if !node.is_symlink() {
return Ok(None);
}
if node.item.size > MAX_PATH as u64 {
return Err(self.not_found(path));
}
Ok(Some(self.link_target(node)?))
}
fn not_found(&self, path: &[u8]) -> ReadError {
ReadError::NotFound {
path: path.to_vec(),
}
}
fn not_a_directory(&self, _node: &Node, path: &[u8]) -> ReadError {
ReadError::NotADirectory {
path: path.to_vec(),
}
}
fn too_many_links(&self, path: &[u8]) -> ReadError {
ReadError::SymlinkLoop {
path: path.to_vec(),
}
}
}
impl<R: Read + Seek> crate::walk::Walk for Reader<R> {
type Pending = (Vec<u8>, u64, DiskKey);
type Entry = WalkEntry;
type Key = (u64, u64);
type Error = ReadError;
fn cap(&mut self) -> usize {
self.limits().max_walk_entries
}
fn seed(&mut self) -> Result<crate::walk::Seed<Self>, ReadError> {
let root = self.root()?;
let children = self.pending_children(&root, b"")?;
Ok((children, vec![(root.tree, root.inode)]))
}
fn resolve(&mut self, pending: Self::Pending) -> Result<WalkEntry, ReadError> {
let (path, tree, location) = pending;
let node = self.at_location(tree, location)?;
Ok(WalkEntry { path, node })
}
fn descend_key(&self, entry: &WalkEntry) -> Option<(u64, u64)> {
entry
.node
.is_dir()
.then_some((entry.node.tree, entry.node.inode))
}
fn children(&mut self, entry: &WalkEntry) -> Result<Vec<Self::Pending>, ReadError> {
self.pending_children(&entry.node, &entry.path)
}
fn too_large(limit: usize) -> ReadError {
ReadError::WalkTooLarge { limit }
}
}
type WalkFail<E> = crate::tree::WalkFail<ReadError, E>;
impl<E> From<ReadError> for WalkFail<E> {
fn from(err: ReadError) -> Self {
WalkFail::Read(err)
}
}
impl From<ReadError> for TreeError {
fn from(err: ReadError) -> Self {
match err {
ReadError::Io { kind, message } => TreeError::Io { kind, message },
ReadError::FileTooLarge { .. } | ReadError::TooManyEntries { .. } => {
TreeError::LimitExceeded {
family: Family::Btrfs,
detail: err.to_string(),
}
}
ReadError::UnsupportedFeatures { .. }
| ReadError::UnsupportedChecksum { .. }
| ReadError::UnsupportedProfile { .. }
| ReadError::UnsupportedCompression { .. }
| ReadError::UnsupportedEncoding { .. }
| ReadError::MultiDevice { .. } => TreeError::Unsupported {
family: Family::Btrfs,
detail: err.to_string(),
},
other => TreeError::Malformed {
family: Family::Btrfs,
detail: other.to_string(),
},
}
}
}
impl<R: Read + Seek> FsTree for Reader<R> {
type Node = Node;
fn family(&self) -> Family {
Family::Btrfs
}
fn max_file_bytes(&self) -> u64 {
self.limits().max_file_bytes
}
fn walk_tree<E, F>(&mut self, mut visit: F) -> Result<(), E>
where
E: From<TreeError>,
F: FnMut(&mut Self, TreeEntry<Node>) -> Result<(), E>,
{
let mut shared: BTreeMap<(u64, u64), u64> = BTreeMap::new();
let outcome = self.walk_with::<WalkFail<E>, _>(|reader, entry| {
let node = entry.node;
let kind = match node.item.mode_type() {
MODE_DIR => NodeKind::Directory,
MODE_REG => NodeKind::File {
size: node.item.size,
},
MODE_LNK => NodeKind::Symlink,
MODE_CHR => {
let (major, minor) = node.item.device();
NodeKind::CharDevice { major, minor }
}
MODE_BLK => {
let (major, minor) = node.item.device();
NodeKind::BlockDevice { major, minor }
}
MODE_FIFO => NodeKind::Fifo,
MODE_SOCK => NodeKind::Socket,
other => {
return Err(WalkFail::Tree(TreeError::Malformed {
family: Family::Btrfs,
detail: format!(
"inode {} of subvolume {} records file type {other:#o}, which names \
no file type",
node.inode, node.tree
),
}));
}
};
let mut out = TreeEntry::new(entry.path, kind, node);
if !matches!(kind, NodeKind::Directory) && node.item.nlink > 1 {
let next = shared.len() as u64;
out = out.shared(*shared.entry((node.tree, node.inode)).or_insert(next));
}
visit(reader, out).map_err(WalkFail::Visitor)
});
match outcome {
Ok(()) => Ok(()),
Err(WalkFail::Read(e)) => Err(E::from(TreeError::from(e))),
Err(WalkFail::Tree(e)) => Err(E::from(e)),
Err(WalkFail::Visitor(e)) => Err(e),
}
}
fn stat(&mut self, node: &Node, _synthesis: &Synthesis) -> Result<Attributes, TreeError> {
let meta = Metadata {
mode: node.item.mode as u16,
uid: node.item.uid,
gid: node.item.gid,
atime: node.item.atime,
ctime: node.item.ctime,
mtime: node.item.mtime,
};
Ok(Attributes::read(meta, self.xattrs(node)?))
}
fn read_bytes(&mut self, node: &Node, offset: u64, buf: &mut [u8]) -> Result<usize, TreeError> {
Ok(Reader::read_into(self, node, offset, buf)?)
}
fn link_target(&mut self, node: &Node) -> Result<Vec<u8>, TreeError> {
Ok(Reader::link_target(self, node)?)
}
}
const MODE_CHR: u32 = 0o020_000;
const MODE_BLK: u32 = 0o060_000;
const MODE_FIFO: u32 = 0o010_000;
const MODE_SOCK: u32 = 0o140_000;
const fn is_subvolume_id(objectid: u64) -> bool {
objectid == objectid::FS_TREE
|| (objectid >= objectid::FIRST_FREE && objectid <= objectid::LAST_FREE)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::btrfs::forge::{
DATA_AT, DATA_BYTE, FS_TREE_AT, Forge, NODE_SIZE, ROOT_DIR, TIME, addressed_extent,
compressed_extent, csum_item, entry, fs_tree, inline_extent, inode_item, leaf, root_item,
};
use crate::btrfs::ondisk::{Compression, InodeFlags};
use crate::btrfs::scan::Anomaly;
const SUB_TREE_AT: u64 = FS_TREE_AT + NODE_SIZE as u64;
const SUB_ID: u64 = 257;
fn a_filesystem_holding(items: Vec<(DiskKey, Vec<u8>)>) -> Forge {
let mut all = vec![(
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
)];
all.extend(items);
let mut forge = Forge::new();
forge.block(FS_TREE_AT, &fs_tree(FS_TREE_AT, objectid::FS_TREE, all));
forge.data(DATA_AT, &[DATA_BYTE; 4096]);
forge.root_leaf(&[(
DiskKey::new(objectid::FS_TREE, ItemType::ROOT_ITEM, 0),
root_item(FS_TREE_AT, 0, ROOT_DIR),
)]);
forge
}
fn a_file(name: &[u8], mode: u32, size: u64, record: Vec<u8>) -> Vec<(DiskKey, Vec<u8>)> {
let mut items = vec![
(
DiskKey::new(257, ItemType::INODE_ITEM, 0),
inode_item(mode, size, 1),
),
(DiskKey::new(257, ItemType::EXTENT_DATA, 0), record),
];
items.extend(entry(
ROOT_DIR,
2,
name,
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
items
}
fn a_filesystem_with_a_subvolume() -> Forge {
let mut top = vec![
(
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
),
(
DiskKey::new(257, ItemType::INODE_ITEM, 0),
inode_item(MODE_REG | 0o644, 3, 1),
),
(
DiskKey::new(257, ItemType::EXTENT_DATA, 0),
inline_extent(b"up\n"),
),
];
top.extend(entry(
ROOT_DIR,
2,
b"above",
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
top.extend(entry(
ROOT_DIR,
3,
b"nested",
DiskKey::new(SUB_ID, ItemType::ROOT_ITEM, u64::MAX),
DirEntryType::Dir,
));
let mut sub = vec![
(
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
),
(
DiskKey::new(257, ItemType::INODE_ITEM, 0),
inode_item(MODE_REG | 0o644, 6, 1),
),
(
DiskKey::new(257, ItemType::EXTENT_DATA, 0),
inline_extent(b"inside"),
),
];
sub.extend(entry(
ROOT_DIR,
2,
b"within",
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
let mut forge = Forge::new();
forge.block(FS_TREE_AT, &fs_tree(FS_TREE_AT, objectid::FS_TREE, top));
forge.block(SUB_TREE_AT, &fs_tree(SUB_TREE_AT, SUB_ID, sub));
let mut backref = vec![0u8; 18];
RootRef {
dirid: ROOT_DIR,
sequence: 3,
name_len: 6,
}
.write_to(&mut backref);
backref.extend_from_slice(b"nested");
forge.root_leaf(&[
(
DiskKey::new(objectid::FS_TREE, ItemType::ROOT_ITEM, 0),
root_item(FS_TREE_AT, 0, ROOT_DIR),
),
(
DiskKey::new(SUB_ID, ItemType::ROOT_ITEM, 0),
root_item(SUB_TREE_AT, 0, ROOT_DIR),
),
(
DiskKey::new(SUB_ID, ItemType::ROOT_BACKREF, objectid::FS_TREE),
backref,
),
]);
forge
}
fn open(forge: &Forge) -> Reader<crate::btrfs::forge::Sparse> {
Reader::open(forge.source()).expect("a forged filesystem opens")
}
#[test]
fn a_filesystem_opens_at_the_root_of_its_top_level_subvolume() {
let forge = Forge::populated();
let mut reader = open(&forge);
assert_eq!(reader.subvolumes().len(), 1);
assert_eq!(reader.top_level().id, objectid::FS_TREE);
assert_eq!(reader.default_subvolume(), objectid::FS_TREE);
let root = reader.root().expect("the root directory");
assert_eq!(root.inode, ROOT_DIR);
assert!(root.is_dir());
assert_eq!(root.item.mode & 0o7777, 0o755);
assert_eq!(root.item.mtime, TIME);
assert_eq!(root.item.otime, TIME);
}
#[test]
fn a_directory_lists_its_entries_in_the_order_it_stores_them() {
let forge = Forge::populated();
let mut reader = open(&forge);
let root = reader.root().expect("the root");
let names: Vec<Vec<u8>> = reader
.read_dir(&root)
.expect("the root lists")
.into_iter()
.map(|entry| entry.name)
.collect();
assert_eq!(
names,
vec![
b"hello.txt".to_vec(),
b"big".to_vec(),
b"link".to_vec(),
b"sub".to_vec()
]
);
assert!(!names.iter().any(|name| name == b"." || name == b".."));
}
#[test]
fn a_name_is_found_through_the_hash_it_is_keyed_by() {
let forge = Forge::populated();
let mut reader = open(&forge);
let node = reader.lookup(b"/hello.txt").expect("the file");
assert!(node.is_file());
assert_eq!(node.item.size, 6);
let inner = reader.lookup(b"/sub/inner").expect("the nested file");
assert_eq!(reader.read_data(&inner).expect("its bytes"), b"in\n");
assert!(matches!(
reader.lookup(b"/missing"),
Err(ReadError::NotFound { .. })
));
assert!(matches!(
reader.lookup(b"/hello.txt/deeper"),
Err(ReadError::NotADirectory { .. })
));
}
#[test]
fn a_small_file_is_read_out_of_the_record_that_holds_it() {
let forge = Forge::populated();
let mut reader = open(&forge);
let node = reader.lookup(b"/hello.txt").expect("the file");
assert_eq!(reader.read_data(&node).expect("its bytes"), b"hello\n");
let mut buf = [0u8; 3];
assert_eq!(
reader
.read_into(&node, 2, &mut buf)
.expect("a partial read"),
3
);
assert_eq!(&buf, b"llo");
assert_eq!(
reader.read_into(&node, 6, &mut buf).expect("past the end"),
0
);
}
#[test]
fn a_large_file_is_read_through_the_extent_that_addresses_it() {
let forge = Forge::populated();
let mut reader = open(&forge);
let node = reader.lookup(b"/big").expect("the file");
let bytes = reader.read_data(&node).expect("its bytes");
assert_eq!(bytes.len(), 4096);
assert!(bytes.iter().all(|&b| b == 0xab));
let mut streamed = Vec::new();
assert_eq!(
reader
.read_data_to(&node, &mut streamed)
.expect("streaming it"),
4096
);
assert_eq!(streamed, bytes);
}
#[test]
fn a_symbolic_link_hands_back_the_target_it_records() {
let forge = Forge::populated();
let mut reader = open(&forge);
let link = reader.lookup_no_follow(b"/link").expect("the link");
assert!(link.is_symlink());
assert_eq!(reader.link_target(&link).expect("its target"), b"hello.txt");
let file = reader.lookup_no_follow(b"/hello.txt").expect("the file");
assert_ne!(link.inode, file.inode);
assert!(matches!(
reader.link_target(&file),
Err(ReadError::NotASymlink { .. })
));
}
fn a_link(
dir: u64,
inode: u64,
index: u64,
name: &[u8],
target: &[u8],
) -> Vec<(DiskKey, Vec<u8>)> {
let mut items = vec![
(
DiskKey::new(inode, ItemType::INODE_ITEM, 0),
inode_item(MODE_LNK | 0o777, target.len() as u64, 1),
),
(
DiskKey::new(inode, ItemType::EXTENT_DATA, 0),
inline_extent(target),
),
];
items.extend(entry(
dir,
index,
name,
DiskKey::new(inode, ItemType::INODE_ITEM, 0),
DirEntryType::Symlink,
));
items
}
#[test]
fn a_path_continues_through_a_link_naming_a_directory() {
let mut items = vec![
(
DiskKey::new(260, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
),
(
DiskKey::new(261, ItemType::INODE_ITEM, 0),
inode_item(MODE_REG | 0o644, 3, 1),
),
(
DiskKey::new(261, ItemType::EXTENT_DATA, 0),
inline_extent(b"in\n"),
),
];
items.extend(entry(
ROOT_DIR,
2,
b"sub",
DiskKey::new(260, ItemType::INODE_ITEM, 0),
DirEntryType::Dir,
));
items.extend(entry(
260,
2,
b"inner",
DiskKey::new(261, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
items.extend(a_link(ROOT_DIR, 259, 3, b"to-sub", b"sub"));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
let through = reader
.lookup(b"/to-sub/inner")
.expect("a path continuing through a link to a directory");
let direct = reader
.lookup(b"/sub/inner")
.expect("the same file directly");
assert_eq!((through.tree, through.inode), (direct.tree, direct.inode));
assert_eq!(reader.read_data(&through).expect("its bytes"), b"in\n");
let stopped = reader
.lookup_no_follow(b"/to-sub/inner")
.expect("the same, not following the last component");
assert_eq!((stopped.tree, stopped.inode), (direct.tree, direct.inode));
}
#[test]
fn a_target_beginning_at_the_root_restarts_there() {
let mut items = vec![
(
DiskKey::new(260, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
),
(
DiskKey::new(261, ItemType::INODE_ITEM, 0),
inode_item(MODE_REG | 0o644, 3, 1),
),
(
DiskKey::new(261, ItemType::EXTENT_DATA, 0),
inline_extent(b"at\n"),
),
];
items.extend(entry(
ROOT_DIR,
2,
b"sub",
DiskKey::new(260, ItemType::INODE_ITEM, 0),
DirEntryType::Dir,
));
items.extend(entry(
ROOT_DIR,
3,
b"top.txt",
DiskKey::new(261, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
items.extend(a_link(260, 259, 2, b"up", b"/top.txt"));
items.extend(a_link(260, 262, 3, b"over", b"../top.txt"));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
let found = reader
.lookup(b"/sub/up")
.expect("resolving the absolute target");
assert_eq!(reader.read_data(&found).expect("its bytes"), b"at\n");
let ascended = reader
.lookup(b"/sub/over")
.expect("resolving the ascending relative target");
assert_eq!((ascended.tree, ascended.inode), (found.tree, found.inode));
}
#[test]
fn a_chain_of_links_that_does_not_end_is_refused() {
let mut items = a_link(ROOT_DIR, 259, 2, b"a", b"b");
items.extend(a_link(ROOT_DIR, 260, 3, b"b", b"a"));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
assert!(matches!(
reader.lookup(b"/a"),
Err(ReadError::SymlinkLoop { .. })
));
let stopped = reader.lookup_no_follow(b"/a").expect("the link itself");
assert!(stopped.is_symlink());
}
#[test]
fn a_lookup_follows_a_link_and_a_no_follow_lookup_stops_at_it() {
let forge = Forge::populated();
let mut reader = open(&forge);
let followed = reader.lookup(b"/link").expect("resolving through the link");
let stopped = reader.lookup_no_follow(b"/link").expect("stopping at it");
let target = reader.lookup(b"/hello.txt").expect("the file it names");
assert_eq!((followed.tree, followed.inode), (target.tree, target.inode));
assert!(stopped.is_symlink());
assert_ne!(stopped.inode, followed.inode);
}
#[test]
fn a_nodes_extended_attributes_come_back_in_the_boundary_form() {
let forge = Forge::populated();
let mut reader = open(&forge);
let node = reader.lookup(b"/hello.txt").expect("the file");
assert_eq!(
reader.xattrs(&node).expect("its attributes"),
vec![Xattr {
name: b"user.note".to_vec(),
value: b"a value".to_vec(),
}]
);
let root = reader.root().expect("the root");
assert!(reader.xattrs(&root).expect("no attributes").is_empty());
}
#[test]
fn a_walk_yields_the_root_first_and_then_every_name_below_it() {
let forge = Forge::populated();
let mut reader = open(&forge);
let paths: Vec<Vec<u8>> = reader
.walk()
.expect("a walk")
.into_iter()
.map(|entry| entry.path)
.collect();
assert_eq!(
paths,
vec![
Vec::new(),
b"/hello.txt".to_vec(),
b"/big".to_vec(),
b"/link".to_vec(),
b"/sub".to_vec(),
b"/sub/inner".to_vec(),
],
"a parent comes before its children, in the order its directory stores them"
);
}
#[test]
fn a_subvolume_is_crossed_into_as_though_it_were_a_directory() {
let forge = a_filesystem_with_a_subvolume();
let mut reader = open(&forge);
assert_eq!(reader.subvolumes().len(), 2);
let nested = &reader.subvolumes()[1];
assert_eq!(nested.id, SUB_ID);
assert_eq!(nested.name, b"nested");
assert_eq!(nested.parent, Some(objectid::FS_TREE));
assert_eq!(nested.parent_dir, ROOT_DIR);
let node = reader.lookup(b"/nested/within").expect("the nested file");
assert_eq!(node.tree, SUB_ID, "the node is in the subvolume's own tree");
assert_eq!(reader.read_data(&node).expect("its bytes"), b"inside");
let paths: Vec<Vec<u8>> = reader
.walk()
.expect("a walk")
.into_iter()
.map(|entry| entry.path)
.collect();
assert_eq!(
paths,
vec![
Vec::new(),
b"/above".to_vec(),
b"/nested".to_vec(),
b"/nested/within".to_vec(),
]
);
}
#[test]
fn a_parent_component_ascends_back_out_of_the_subvolume_it_descended_into() {
let forge = a_filesystem_with_a_subvolume();
let mut reader = open(&forge);
let above = reader.lookup(b"/above").expect("the file above the seam");
let within = reader.lookup(b"/nested/within").expect("the nested file");
assert_eq!(within.tree, SUB_ID);
let ascended = reader
.lookup(b"/nested/../above")
.expect("out of the subvolume and back down");
assert_eq!((ascended.tree, ascended.inode), (above.tree, above.inode));
assert_eq!(ascended.tree, objectid::FS_TREE);
let returned = reader
.lookup(b"/nested/../nested/within")
.expect("back into the subvolume");
assert_eq!((returned.tree, returned.inode), (within.tree, within.inode));
let seam = reader
.lookup(b"/nested/..")
.expect("the mount point's parent");
assert_eq!(seam.tree, objectid::FS_TREE);
assert_eq!(seam.inode, ROOT_DIR);
let root = reader.root().expect("the root");
for path in [&b"/.."[..], b"/../..", b"/nested/../../.."] {
let stayed = reader
.lookup(path)
.unwrap_or_else(|e| panic!("{}: {e}", String::from_utf8_lossy(path)));
assert_eq!((stayed.tree, stayed.inode), (root.tree, root.inode));
}
}
#[test]
fn an_inode_number_is_only_an_identity_within_its_own_subvolume() {
let forge = a_filesystem_with_a_subvolume();
let mut reader = open(&forge);
let above = reader.lookup(b"/above").expect("the top-level file");
let within = reader.lookup(b"/nested/within").expect("the nested file");
assert_eq!(above.inode, within.inode);
assert_ne!(above.tree, within.tree);
assert_eq!(reader.read_data(&above).expect("bytes"), b"up\n");
assert_eq!(reader.read_data(&within).expect("bytes"), b"inside");
}
#[test]
fn a_run_of_a_file_that_was_never_written_reads_back_as_zeros() {
let mut items = vec![
(
DiskKey::new(257, ItemType::INODE_ITEM, 0),
inode_item(MODE_REG | 0o644, 12288, 1),
),
(
DiskKey::new(257, ItemType::EXTENT_DATA, 4096),
addressed_extent(ExtentKind::Regular, DATA_AT, 4096, 0, 4096),
),
(
DiskKey::new(257, ItemType::EXTENT_DATA, 8192),
addressed_extent(ExtentKind::Regular, 0, 0, 0, 4096),
),
];
items.extend(entry(
ROOT_DIR,
2,
b"sparse",
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
let node = reader.lookup(b"/sparse").expect("the file");
let bytes = reader.read_data(&node).expect("its bytes");
assert_eq!(bytes.len(), 12288);
assert!(bytes[..4096].iter().all(|&b| b == 0), "the unrecorded gap");
assert!(
bytes[4096..8192].iter().all(|&b| b == DATA_BYTE),
"the extent"
);
assert!(bytes[8192..].iter().all(|&b| b == 0), "the recorded hole");
let mut buf = [0u8; 8];
reader
.read_into(&node, 5000, &mut buf)
.expect("a read from the middle of an extent");
assert!(buf.iter().all(|&b| b == DATA_BYTE));
}
#[test]
fn a_preallocated_extent_reads_back_as_zeros_rather_than_as_what_is_on_the_volume() {
let forge = a_filesystem_holding(a_file(
b"reserved",
MODE_REG | 0o644,
4096,
addressed_extent(ExtentKind::Prealloc, DATA_AT, 4096, 0, 4096),
));
let mut reader = open(&forge);
let node = reader.lookup(b"/reserved").expect("the file");
assert!(
reader
.read_data(&node)
.expect("its bytes")
.iter()
.all(|&b| b == 0)
);
}
#[test]
fn an_extent_whose_run_leaves_the_extent_it_names_is_refused() {
let forge = a_filesystem_holding(a_file(
b"overreaching",
MODE_REG | 0o644,
4096,
addressed_extent(ExtentKind::Regular, DATA_AT, 512, 0, 4096),
));
let mut reader = open(&forge);
let node = reader.lookup(b"/overreaching").expect("the file");
assert!(matches!(
reader.read_data(&node),
Err(ReadError::BadExtent { .. })
));
}
#[test]
fn an_extent_encoded_in_a_way_the_format_has_not_defined_is_refused_by_its_byte() {
let record = compressed_extent(Compression::Unknown(9), b"encoded somehow", 4096);
let forge = a_filesystem_holding(a_file(b"squeezed", MODE_REG | 0o644, 4096, record));
let mut reader = open(&forge);
let node = reader.lookup(b"/squeezed").expect("the file");
let err = reader.read_data(&node).expect_err("an encoded extent");
assert!(matches!(
err,
ReadError::UnsupportedCompression { compression: 9, .. }
));
assert!(
format!("{err}").contains("an algorithm the format has not defined"),
"{err}"
);
}
#[cfg(feature = "zlib")]
const ZLIB_STREAM: &[u8] = &[
0x78, 0xda, 0x4b, 0x4b, 0x2d, 0x2a, 0xca, 0x2f, 0xae, 0x2c, 0x4e, 0x23, 0x93, 0x06, 0x00,
0x88, 0x65, 0x1b, 0xe9,
];
#[cfg(feature = "zlib")]
fn zlib_payload() -> Vec<u8> {
b"ferrosys".repeat(8)
}
#[cfg(feature = "zlib")]
#[test]
fn a_compressed_extent_reads_back_as_the_bytes_it_stands_for() {
let want = zlib_payload();
let record = compressed_extent(Compression::Zlib, ZLIB_STREAM, want.len() as u64);
let forge = a_filesystem_holding(a_file(
b"inline",
MODE_REG | 0o644,
want.len() as u64,
record,
));
let mut reader = open(&forge);
let node = reader.lookup(b"/inline").expect("the file");
assert_eq!(reader.read_data(&node).expect("it decodes"), want);
let mut record = addressed_extent(
ExtentKind::Regular,
DATA_AT,
ZLIB_STREAM.len() as u64,
0,
64,
);
record[16] = Compression::Zlib.to_u8();
record[8..16].copy_from_slice(&(want.len() as u64).to_le_bytes());
let mut forge = a_filesystem_holding(a_file(
b"addressed",
MODE_REG | 0o644,
want.len() as u64,
record,
));
forge.data(DATA_AT, ZLIB_STREAM);
let mut reader = open(&forge);
let node = reader.lookup(b"/addressed").expect("the file");
assert_eq!(reader.read_data(&node).expect("it decodes"), want);
let mut middle = [0u8; 8];
assert_eq!(
reader
.read_into(&node, 20, &mut middle)
.expect("it decodes"),
8
);
assert_eq!(&middle, &want[20..28]);
}
#[cfg(feature = "zlib")]
#[test]
fn a_compressed_extent_that_does_not_decode_is_a_fault_in_the_filesystem() {
let record = compressed_extent(Compression::Zlib, b"not a stream", 64);
let forge = a_filesystem_holding(a_file(b"damaged", MODE_REG | 0o644, 64, record));
let mut reader = open(&forge);
let node = reader.lookup(b"/damaged").expect("the file");
assert!(matches!(
reader.read_data(&node),
Err(ReadError::BadCompressedExtent { .. })
));
}
#[cfg(feature = "zlib")]
#[test]
fn a_record_expanding_to_more_than_the_format_compresses_in_is_refused_before_it_costs_it() {
let mut record = compressed_extent(Compression::Zlib, ZLIB_STREAM, 64);
record[8..16].copy_from_slice(&(1u64 << 30).to_le_bytes());
let forge = a_filesystem_holding(a_file(b"greedy", MODE_REG | 0o644, 1 << 30, record));
let mut reader = open(&forge);
let node = reader.lookup(b"/greedy").expect("the file");
let mut out = [0u8; 64];
assert!(matches!(
reader.read_into(&node, 0, &mut out),
Err(ReadError::BadExtent { .. })
));
}
#[test]
fn a_directory_reachable_from_itself_is_descended_into_once_rather_than_forever() {
let mut items = vec![(
DiskKey::new(257, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
)];
items.extend(entry(
ROOT_DIR,
2,
b"down",
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::Dir,
));
items.extend(entry(
257,
2,
b"up",
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
DirEntryType::Dir,
));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
let paths: Vec<Vec<u8>> = reader
.walk()
.expect("a walk terminates")
.into_iter()
.map(|walked| walked.path)
.collect();
assert_eq!(
paths,
vec![Vec::new(), b"/down".to_vec(), b"/down/up".to_vec()]
);
}
#[test]
fn a_name_no_directory_can_hold_stops_a_walk_rather_than_becoming_a_path() {
let forge = a_filesystem_holding(a_file(
b"../escape",
MODE_REG | 0o644,
0,
inline_extent(b""),
));
let mut reader = open(&forge);
assert!(matches!(reader.walk(), Err(ReadError::HostileName { .. })));
assert!(matches!(
reader.lookup(b"/../escape"),
Err(ReadError::NotFound { .. })
));
}
fn a_filesystem_with_checksums(on_the_volume: &[u8], covering: &[u8]) -> Forge {
let items = a_file(
b"data",
MODE_REG | 0o644,
4096,
addressed_extent(ExtentKind::Regular, DATA_AT, 4096, 0, 4096),
);
let mut forge = Forge::new();
let mut all = vec![(
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
)];
all.extend(items);
forge.block(FS_TREE_AT, &fs_tree(FS_TREE_AT, objectid::FS_TREE, all));
forge.data(DATA_AT, on_the_volume);
forge.block(
SUB_TREE_AT,
&fs_tree(
SUB_TREE_AT,
objectid::CSUM_TREE,
vec![(
DiskKey::new(objectid::EXTENT_CSUM, ItemType::EXTENT_CSUM, DATA_AT),
csum_item(covering, NODE_SIZE),
)],
),
);
forge.root_leaf(&[
(
DiskKey::new(objectid::FS_TREE, ItemType::ROOT_ITEM, 0),
root_item(FS_TREE_AT, 0, ROOT_DIR),
),
(
DiskKey::new(objectid::CSUM_TREE, ItemType::ROOT_ITEM, 0),
root_item(SUB_TREE_AT, 0, 0),
),
]);
forge
}
#[test]
fn a_files_bytes_are_held_against_the_checksums_the_filesystem_recorded_for_them() {
let bytes = [DATA_BYTE; 4096];
let forge = a_filesystem_with_checksums(&bytes, &bytes);
let mut reader = open(&forge);
let node = reader.lookup(b"/data").expect("the file");
reader.verify_data(&node).expect("the bytes are the bytes");
let mut decayed = bytes;
decayed[100] ^= 0xff;
let forge = a_filesystem_with_checksums(&decayed, &bytes);
let mut reader = open(&forge);
let node = reader.lookup(b"/data").expect("the file");
assert_eq!(
reader.read_data(&node).expect("a read still succeeds")[100],
DATA_BYTE ^ 0xff,
"an ordinary read hands back what is there"
);
assert!(matches!(
reader.verify_data(&node),
Err(ReadError::DataChecksum { logical }) if logical == DATA_AT
));
}
#[test]
fn a_file_with_no_checksum_recorded_for_it_is_reported_rather_than_passed() {
let forge = a_filesystem_with_checksums(&[DATA_BYTE; 4096], &[]);
let mut reader = open(&forge);
let node = reader.lookup(b"/data").expect("the file");
assert!(matches!(
reader.verify_data(&node),
Err(ReadError::MissingDataChecksum { .. })
));
}
#[test]
fn a_file_the_filesystem_does_not_checksum_is_not_held_to_one() {
let mut record = inode_item(MODE_REG | 0o644, 4096, 1);
record[64] = InodeFlags::NODATASUM.bits() as u8;
let mut items = vec![
(DiskKey::new(257, ItemType::INODE_ITEM, 0), record),
(
DiskKey::new(257, ItemType::EXTENT_DATA, 0),
addressed_extent(ExtentKind::Regular, DATA_AT, 4096, 0, 4096),
),
];
items.extend(entry(
ROOT_DIR,
2,
b"raw",
DiskKey::new(257, ItemType::INODE_ITEM, 0),
DirEntryType::RegFile,
));
let forge = a_filesystem_holding(items);
let mut reader = open(&forge);
let node = reader.lookup(b"/raw").expect("the file");
assert!(node.item.flags.contains(InodeFlags::NODATASUM));
reader
.verify_data(&node)
.expect("nothing is recorded, so nothing is held against");
let forge = a_filesystem_holding(a_file(
b"reserved",
MODE_REG | 0o644,
4096,
addressed_extent(ExtentKind::Prealloc, DATA_AT, 4096, 0, 4096),
));
let mut reader = open(&forge);
let node = reader.lookup(b"/reserved").expect("the file");
reader.verify_data(&node).expect("nothing has been written");
}
#[test]
fn a_filesystem_nothing_is_wrong_with_scans_clean() {
let forge = Forge::populated();
let mut reader = open(&forge);
let report = reader.scan();
assert!(report.is_clean(), "{:?}", report.anomalies());
assert!(!report.is_truncated());
}
#[test]
fn a_filesystem_that_was_not_cleanly_unmounted_says_what_is_missing() {
let mut forge = Forge::populated();
forge.amend_superblock(0, |sb| sb.log_root = FS_TREE_AT);
let mut reader = open(&forge);
let report = reader.scan();
let logged: Vec<&Anomaly> = report
.anomalies()
.iter()
.filter(|a| a.category == Category::Superblock)
.collect();
assert_eq!(logged.len(), 1);
assert_eq!(logged[0].severity, Severity::Cosmetic);
assert!(logged[0].detail.contains("last committed transaction"));
assert!(logged[0].detail.contains("not cleanly unmounted"));
let node = reader.lookup(b"/hello.txt").expect("the file");
assert_eq!(reader.read_data(&node).expect("its bytes"), b"hello\n");
}
#[test]
fn a_scan_reports_a_block_that_does_not_verify_rather_than_stopping_at_it() {
let mut forge = Forge::populated();
forge.break_checksum(FS_TREE_AT);
let mut reader = Reader::open_with(
forge.source(),
&OpenOptions::new().policy(ReadPolicy::Lenient),
)
.expect("the superblock and the root tree are intact");
let report = reader.scan();
assert!(!report.is_clean());
let damaged: Vec<&Anomaly> = report
.anomalies()
.iter()
.filter(|a| a.severity == Severity::Integrity)
.collect();
assert_eq!(damaged.len(), 1, "{:?}", report.anomalies());
assert_eq!(damaged[0].category, Category::Tree);
assert_eq!(damaged[0].tree, Some(objectid::FS_TREE));
assert!(matches!(
reader.lookup(b"/hello.txt"),
Err(ReadError::BadChecksum { .. })
));
}
#[test]
fn a_scan_reports_a_uuid_tree_that_disagrees_with_the_root_items() {
const UUID_TREE_AT: u64 = FS_TREE_AT + 3 * NODE_SIZE as u64;
let held = [0x44u8; 16];
let mut item = root_item(FS_TREE_AT, 0, ROOT_DIR);
let mut with_uuid = RootItem::read_from(&item).expect("the forge's root item reads back");
with_uuid.uuid = held;
with_uuid.write_to(&mut item);
let mut forge = Forge::new();
forge.block(
FS_TREE_AT,
&fs_tree(
FS_TREE_AT,
objectid::FS_TREE,
vec![(
DiskKey::new(ROOT_DIR, ItemType::INODE_ITEM, 0),
inode_item(MODE_DIR | 0o755, 0, 1),
)],
),
);
forge.block(
UUID_TREE_AT,
&leaf(
UUID_TREE_AT,
objectid::UUID_TREE,
&[(
DiskKey::new(0, ItemType::UUID_SUBVOL, 0),
objectid::FS_TREE.to_le_bytes().to_vec(),
)],
),
);
forge.root_leaf(&[
(
DiskKey::new(objectid::FS_TREE, ItemType::ROOT_ITEM, 0),
item,
),
(
DiskKey::new(objectid::UUID_TREE, ItemType::ROOT_ITEM, 0),
root_item(UUID_TREE_AT, 0, 0),
),
]);
let mut reader = open(&forge);
let report = reader.scan();
let details: Vec<&str> = report
.anomalies()
.iter()
.filter(|a| a.tree == Some(objectid::UUID_TREE))
.map(|a| a.detail.as_str())
.collect();
assert_eq!(details.len(), 2, "{:?}", report.anomalies());
assert!(
details[0].contains("records a different identifier"),
"{details:?}"
);
assert!(
details[1].contains("no entry mapping it back"),
"{details:?}"
);
reader.root().expect("the root directory");
}
#[test]
fn a_filesystem_with_no_top_level_tree_is_refused_at_open() {
let mut forge = Forge::new();
forge.root_leaf(&[]);
assert!(matches!(
Reader::open(forge.source()),
Err(ReadError::MissingTree { objectid: 5 })
));
}
#[test]
fn a_whole_file_read_is_held_to_the_cap_the_caller_set() {
let forge = Forge::populated();
let mut reader = Reader::open_with(
forge.source(),
&OpenOptions::new().limits(Limits::new().max_file_bytes(4)),
)
.expect("a forged filesystem");
let node = reader.lookup(b"/hello.txt").expect("the file");
assert!(matches!(
reader.read_data(&node),
Err(ReadError::FileTooLarge {
size: 6,
cap: 4,
..
})
));
let mut out = Vec::new();
assert_eq!(reader.read_data_to(&node, &mut out).expect("streaming"), 6);
}
}