use std::collections::BTreeMap;
use std::io::{Read, Seek, SeekFrom};
use std::sync::Arc;
use crate::cache::BlockCache;
use crate::compress::Algorithm;
use crate::io::{Bounded, io_error, offset_of, read_exact_at, read_exact_into};
use crate::{Limits, OpenOptions, ReadPolicy};
use super::ChunkMap;
use super::btree::Tree;
use super::ondisk::{
self, ChecksumType, Chunk, DiskKey, Header, IncompatFlags, ItemType, MAX_BLOCK_SIZE, MAX_LEVEL,
MIN_BLOCK_SIZE, MIRRORS, ParseError, RootItem, SUPER_INFO_SIZE, SuperBlock, holds_mirror,
objectid,
};
pub const SUPPORTED_INCOMPAT: IncompatFlags = IncompatFlags::from_bits(
IncompatFlags::MIXED_BACKREF.bits()
| IncompatFlags::DEFAULT_SUBVOL.bits()
| IncompatFlags::BIG_METADATA.bits()
| IncompatFlags::EXTENDED_IREF.bits()
| IncompatFlags::SKINNY_METADATA.bits()
| IncompatFlags::NO_HOLES.bits()
| IncompatFlags::METADATA_UUID.bits()
| decodable_compression_bits(),
);
const COMPRESSION_BITS: [(IncompatFlags, Algorithm); 2] = [
(IncompatFlags::COMPRESS_LZO, Algorithm::Lzo),
(IncompatFlags::COMPRESS_ZSTD, Algorithm::Zstd),
];
const fn decodable_compression_bits() -> u64 {
let mut bits = 0;
let mut i = 0;
while i < COMPRESSION_BITS.len() {
let (flag, algorithm) = COMPRESSION_BITS[i];
if algorithm.available() {
bits |= flag.bits();
}
i += 1;
}
bits
}
struct DecodersFor(u64);
impl std::fmt::Display for DecodersFor {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for (flag, algorithm) in COMPRESSION_BITS {
if self.0 & flag.bits() != 0 {
write!(f, "{}", crate::compress::CompiledBy(Some(algorithm)))?;
}
}
Ok(())
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum Mirror {
OutsideDevice,
Truncated,
Absent,
Damaged,
Misplaced {
bytenr: u64,
},
Present {
generation: u64,
},
Diverged {
generation: u64,
},
Foreign,
}
impl Mirror {
#[must_use]
pub const fn generation(self) -> Option<u64> {
match self {
Mirror::Present { generation } => Some(generation),
_ => None,
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct TreeRoot {
pub objectid: u64,
pub bytenr: u64,
pub level: u8,
pub generation: u64,
}
pub struct Volume<R> {
src: Bounded<R>,
base: u64,
policy: ReadPolicy,
limits: Limits,
superblock: Box<SuperBlock>,
mirrors: [Mirror; MIRRORS.len()],
chunks: ChunkMap,
cache: BlockCache<TreeBlock>,
read_through: BTreeMap<u64, ReadThrough>,
bootstrap_conflicts: Vec<u64>,
source_bytes: u64,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(super) struct ReadThrough {
pub(super) copy: usize,
pub(super) fault: String,
}
impl<R: Read + Seek> Volume<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 base = options.base;
let mut src = Bounded::new(src, base, options.len);
let mut found = [Mirror::Absent; MIRRORS.len()];
let mut candidates: [Option<SuperBlock>; MIRRORS.len()] = [None, None, None];
let mut records: [Option<Vec<u8>>; MIRRORS.len()] = [None, None, None];
for (index, &at) in MIRRORS.iter().enumerate() {
let Some(offset) = offset_of(base, at, 1) else {
found[index] = Mirror::Truncated;
continue;
};
let bytes = match read_exact_at(&mut src, offset, SUPER_INFO_SIZE) {
Ok(bytes) => bytes,
Err(e) if e.kind() == std::io::ErrorKind::UnexpectedEof => {
found[index] = Mirror::Truncated;
continue;
}
Err(e) => return Err(e.into()),
};
let Ok(superblock) = SuperBlock::read_from(&bytes) else {
found[index] = Mirror::Absent;
continue;
};
if !checksum_holds(&bytes, superblock.csum_type) {
found[index] = Mirror::Damaged;
continue;
}
if superblock.bytenr != at {
found[index] = Mirror::Misplaced {
bytenr: superblock.bytenr,
};
continue;
}
found[index] = Mirror::Present {
generation: superblock.generation,
};
candidates[index] = Some(superblock);
records[index] = Some(bytes);
}
if let Some(primary) = &candidates[0] {
let (fsid, device) = (primary.fsid, primary.dev_item.total_bytes);
for (index, &at) in MIRRORS.iter().enumerate().skip(1) {
let state = match &candidates[index] {
Some(_) if !holds_mirror(device, at) => Mirror::OutsideDevice,
Some(copy) if copy.fsid != fsid => Mirror::Foreign,
_ => continue,
};
found[index] = state;
candidates[index] = None;
records[index] = None;
}
}
let chosen = candidates
.iter()
.enumerate()
.filter_map(|(index, sb)| sb.as_ref().map(|sb| (index, sb)))
.max_by_key(|(index, sb)| (sb.generation, std::cmp::Reverse(*index)))
.map(|(index, _)| index);
let Some(chosen) = chosen else {
return Err(
match found.iter().find(|m| {
!matches!(
m,
Mirror::Absent | Mirror::OutsideDevice | Mirror::Truncated
)
}) {
Some(Mirror::Damaged) => ReadError::BadChecksum {
object: "superblock",
at: MIRRORS[0],
},
Some(&Mirror::Misplaced { bytenr }) => ReadError::MisplacedSuperblock {
expected: MIRRORS[0],
bytenr,
},
_ => ReadError::NotBtrfs,
},
);
};
let superblock = candidates[chosen]
.take()
.expect("the chosen copy was parsed");
check_readable(&superblock)?;
let live = records[chosen].take().expect("the chosen copy was read");
for (index, record) in records.iter().enumerate() {
if let (Some(record), Mirror::Present { generation }) = (record, found[index])
&& generation == superblock.generation
&& !same_record(record, &live)
{
found[index] = Mirror::Diverged { generation };
}
}
let device_bytes = superblock.dev_item.total_bytes;
for (index, &at) in MIRRORS.iter().enumerate() {
if !holds_mirror(device_bytes, at) {
found[index] = Mirror::OutsideDevice;
}
}
if options.policy == ReadPolicy::Strict {
for (index, &state) in found.iter().enumerate() {
let fault = match state {
Mirror::OutsideDevice => continue,
Mirror::Present { generation } if generation == superblock.generation => {
continue;
}
Mirror::Present { .. } => "a copy of the superblock is behind the live one",
Mirror::Truncated => "the source is shorter than the device it describes",
Mirror::Absent => "a copy of the superblock is missing",
Mirror::Damaged => "a copy of the superblock fails its checksum",
Mirror::Misplaced { .. } => {
"a copy of the superblock records another place as its own"
}
Mirror::Diverged { .. } => {
"a copy of the superblock at the live generation is not a copy of the \
live one"
}
Mirror::Foreign => "a copy of the superblock belongs to another filesystem",
};
return Err(ReadError::MirrorDisagreement {
mirror: index,
at: MIRRORS[index],
fault,
});
}
}
let bootstrap = superblock
.sys_chunk_bytes()
.ok_or(ReadError::BadBootstrap {
at: 0,
fault: "the recorded length of the bootstrap array is longer than the array",
})?;
let chunks = ChunkMap::from_bootstrap(bootstrap, superblock.dev_item.devid, device_bytes)?;
let cache = tree_cache(superblock.nodesize);
let source_bytes = src.seek(SeekFrom::End(0))?.saturating_sub(base);
let mut volume = Self {
src,
base,
policy: options.policy,
limits: options.limits,
superblock: Box::new(superblock),
mirrors: found,
chunks,
cache,
read_through: BTreeMap::new(),
bootstrap_conflicts: Vec::new(),
source_bytes,
};
volume.load_chunk_tree()?;
Ok(volume)
}
#[must_use]
pub fn superblock(&self) -> &SuperBlock {
&self.superblock
}
#[must_use]
pub fn mirrors(&self) -> &[Mirror; MIRRORS.len()] {
&self.mirrors
}
#[must_use]
pub fn source_bytes(&self) -> u64 {
self.source_bytes
}
#[must_use]
pub fn chunk_map(&self) -> &ChunkMap {
&self.chunks
}
#[must_use]
pub fn policy(&self) -> ReadPolicy {
self.policy
}
#[must_use]
pub fn limits(&self) -> Limits {
self.limits
}
#[must_use]
pub fn node_size(&self) -> u32 {
self.superblock.nodesize
}
#[must_use]
pub fn root_tree(&self) -> TreeRoot {
TreeRoot {
objectid: objectid::ROOT_TREE,
bytenr: self.superblock.root,
level: self.superblock.root_level,
generation: self.superblock.generation,
}
}
#[must_use]
pub fn chunk_tree(&self) -> TreeRoot {
TreeRoot {
objectid: objectid::CHUNK_TREE,
bytenr: self.superblock.chunk_root,
level: self.superblock.chunk_root_level,
generation: self.superblock.chunk_root_generation,
}
}
pub fn tree_roots(&mut self) -> Result<Vec<TreeRoot>, ReadError> {
let mut roots = vec![self.root_tree(), self.chunk_tree()];
let mut failure = None;
let root_tree = self.root_tree();
self.tree(root_tree).for_each_item(|key, data| {
if key.kind != ItemType::ROOT_ITEM {
return true;
}
match RootItem::read_from(data) {
Ok(item) => {
roots.push(TreeRoot {
objectid: key.objectid,
bytenr: item.bytenr,
level: item.level,
generation: item.generation,
});
true
}
Err(e) => {
failure = Some(ReadError::BadRootItem {
objectid: key.objectid,
source: e,
});
false
}
}
})?;
match failure {
Some(e) => Err(e),
None => Ok(roots),
}
}
pub fn tree(&mut self, root: TreeRoot) -> Tree<'_, R> {
Tree::new(self, root)
}
pub fn read_block(&mut self, logical: u64) -> Result<TreeBlock, ReadError> {
self.fetch(logical, None)
}
pub(super) fn read_tree_block(
&mut self,
logical: u64,
generation: u64,
) -> Result<TreeBlock, ReadError> {
self.fetch(logical, Some(generation))
}
fn fetch(&mut self, logical: u64, generation: Option<u64>) -> Result<TreeBlock, ReadError> {
if let Some(block) = self.cache.get(logical)
&& generation.is_none_or(|expected| block.header.generation == expected)
{
return Ok(block.clone());
}
let len = u64::from(self.superblock.nodesize);
let mut first: Option<ReadError> = None;
for (copy, physical) in self.chunks.copies_of(logical, len)?.into_iter().enumerate() {
match self.read_copy(logical, physical, len, generation) {
Ok(block) => {
if let Some(fault) = first {
self.read_through.insert(
logical,
ReadThrough {
copy,
fault: fault.to_string(),
},
);
}
self.cache.insert(logical, block.clone());
return Ok(block);
}
Err(
fault @ (ReadError::BadChecksum { .. }
| ReadError::BadTreeBlock { .. }
| ReadError::WrongGeneration { .. }),
) if self.policy == ReadPolicy::Lenient => {
first.get_or_insert(fault);
}
Err(fault) => return Err(first.unwrap_or(fault)),
}
}
Err(first.expect("a chunk has at least one copy, and each failed"))
}
fn read_copy(
&mut self,
logical: u64,
physical: u64,
len: u64,
generation: Option<u64>,
) -> Result<TreeBlock, ReadError> {
let offset =
offset_of(self.base, physical, 1).ok_or(ReadError::UnmappedLogical { logical, len })?;
let bytes = read_exact_at(&mut self.src, offset, len as usize)?;
if !checksum_holds(&bytes, self.superblock.csum_type) {
return Err(ReadError::BadChecksum {
object: "tree block",
at: logical,
});
}
let header = Header::read_from(&bytes)?;
if header.bytenr != logical {
return Err(ReadError::BadTreeBlock {
logical,
fault: "the block records another logical address as its own",
});
}
if header.fsid != self.superblock.metadata_id() {
return Err(ReadError::BadTreeBlock {
logical,
fault: "the block belongs to another filesystem",
});
}
if header.level > MAX_LEVEL {
return Err(ReadError::BadTreeBlock {
logical,
fault: "the block is at a height the format does not define",
});
}
if let Some(expected) = generation
&& header.generation != expected
{
return Err(ReadError::WrongGeneration {
logical,
generation: header.generation,
expected,
});
}
Ok(TreeBlock {
header,
bytes: bytes.into(),
})
}
pub(super) fn read_through(&self) -> &BTreeMap<u64, ReadThrough> {
&self.read_through
}
pub(super) fn bootstrap_conflicts(&self) -> &[u64] {
&self.bootstrap_conflicts
}
pub fn read_at(&mut self, logical: u64, buf: &mut [u8]) -> Result<(), ReadError> {
let len = buf.len() as u64;
let physical = self.chunks.translate(logical, len)?;
let offset =
offset_of(self.base, physical, 1).ok_or(ReadError::UnmappedLogical { logical, len })?;
read_exact_into(&mut self.src, offset, buf)?;
Ok(())
}
fn load_chunk_tree(&mut self) -> Result<(), ReadError> {
let devid = self.superblock.dev_item.devid;
let device_bytes = self.superblock.dev_item.total_bytes;
let mut found = Vec::new();
let mut failure = None;
let chunk_tree = self.chunk_tree();
self.tree(chunk_tree).for_each_item(|key, data| {
if key.kind != ItemType::CHUNK_ITEM {
return true;
}
match Chunk::read_from(data) {
Ok(chunk) if data.len() >= chunk.encoded_len() => {
found.push((*key, chunk, data[..chunk.encoded_len()].to_vec()));
true
}
Ok(chunk) => {
failure = Some(ReadError::BadChunk {
logical: key.offset,
fault: "a chunk item declares more stripes than the item holds",
});
let _ = chunk;
false
}
Err(e) => {
failure = Some(e.into());
false
}
}
})?;
if let Some(e) = failure {
return Err(e);
}
for (key, chunk, record) in found {
if let Some(existing) = self.chunks.chunk_at(key.offset)
&& existing.logical == key.offset
{
let repeated = ChunkMap::mapped(&key, &chunk, &record, devid, device_bytes)?;
if repeated == *existing {
continue;
}
if self.policy == ReadPolicy::Strict {
return Err(ReadError::BadChunk {
logical: key.offset,
fault: "the chunk tree maps this chunk differently from the superblock's \
bootstrap array",
});
}
self.bootstrap_conflicts.push(key.offset);
continue;
}
self.chunks
.insert(&key, &chunk, &record, devid, device_bytes)?;
}
Ok(())
}
}
const TREE_CACHE_BYTES: usize = 1 << 20;
fn tree_cache(node_size: u32) -> BlockCache<TreeBlock> {
BlockCache::within(TREE_CACHE_BYTES, node_size as usize, 64)
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TreeBlock {
header: Header,
bytes: Arc<[u8]>,
}
impl TreeBlock {
#[must_use]
pub fn header(&self) -> &Header {
&self.header
}
#[must_use]
pub fn bytes(&self) -> &[u8] {
&self.bytes
}
pub fn count(&self) -> Result<usize, ReadError> {
let each = if self.header.is_leaf() {
ondisk::Item::SIZE
} else {
ondisk::KeyPtr::SIZE
};
let claimed = self.header.nritems as usize;
let room = (self.bytes.len() - Header::SIZE) / each;
if claimed > room {
return Err(ReadError::BadTreeBlock {
logical: self.header.bytenr,
fault: "the block claims more entries than it has room for",
});
}
Ok(claimed)
}
pub fn key_ptr(&self, index: usize) -> Result<ondisk::KeyPtr, ReadError> {
if self.header.is_leaf() {
return Err(ReadError::BadTreeBlock {
logical: self.header.bytenr,
fault: "a leaf holds items rather than child pointers",
});
}
if index >= self.count()? {
return Err(ReadError::BadTreeBlock {
logical: self.header.bytenr,
fault: "a child pointer past the block's own count",
});
}
let at = Header::SIZE + index * ondisk::KeyPtr::SIZE;
Ok(ondisk::KeyPtr::read_from(&self.bytes[at..])?)
}
pub fn item(&self, index: usize) -> Result<ondisk::Item, ReadError> {
if !self.header.is_leaf() {
return Err(ReadError::BadTreeBlock {
logical: self.header.bytenr,
fault: "an internal node holds child pointers rather than items",
});
}
if index >= self.count()? {
return Err(ReadError::BadTreeBlock {
logical: self.header.bytenr,
fault: "an item past the block's own count",
});
}
let at = Header::SIZE + index * ondisk::Item::SIZE;
Ok(ondisk::Item::read_from(&self.bytes[at..])?)
}
pub fn check_leaf_packing(&self) -> Result<(), ReadError> {
if !self.header.is_leaf() {
return Ok(());
}
let count = self.count()?;
let mut abuts = (self.bytes.len() - Header::SIZE) as u64;
for index in 0..count {
let item = self.item(index)?;
let start = u64::from(item.offset);
if start + u64::from(item.size) != abuts {
return Err(ReadError::BadItem {
logical: self.header.bytenr,
index,
fault: "the item's data does not end where the item before it begins",
});
}
abuts = start;
}
Ok(())
}
pub fn key_at(&self, index: usize) -> Result<DiskKey, ReadError> {
if self.header.is_leaf() {
Ok(self.item(index)?.key)
} else {
Ok(self.key_ptr(index)?.key)
}
}
pub fn check_keys(
&self,
first: Option<DiskKey>,
below: Option<DiskKey>,
) -> Result<(), ReadError> {
let logical = self.header.bytenr;
let count = self.count()?;
let mut previous: Option<DiskKey> = None;
for index in 0..count {
let key = self.key_at(index)?;
if previous.is_some_and(|last| key <= last) {
return Err(ReadError::BadTreeBlock {
logical,
fault: "a key is not above the one before it",
});
}
previous = Some(key);
}
if let Some(first) = first
&& (count == 0 || self.key_at(0)? != first)
{
return Err(ReadError::BadTreeBlock {
logical,
fault: "the block's first key is not the key its parent records for it",
});
}
if let (Some(last), Some(below)) = (previous, below)
&& last >= below
{
return Err(ReadError::BadTreeBlock {
logical,
fault: "the block holds a key at or above the key its parent records for the \
block after it",
});
}
Ok(())
}
pub fn item_data(&self, index: usize) -> Result<&[u8], ReadError> {
let count = self.count()?;
let item = self.item(index)?;
let array_end = (Header::SIZE + count * ondisk::Item::SIZE) as u64;
let start = Header::SIZE as u64 + u64::from(item.offset);
let end = start + u64::from(item.size);
if start < array_end {
return Err(ReadError::BadItem {
logical: self.header.bytenr,
index,
fault: "the item's data begins inside the array describing it",
});
}
if end > self.bytes.len() as u64 {
return Err(ReadError::BadItem {
logical: self.header.bytenr,
index,
fault: "the item's data runs past the end of the block",
});
}
Ok(&self.bytes[start as usize..end as usize])
}
}
fn checksum_holds(object: &[u8], csum_type: ChecksumType) -> bool {
csum_type.holds(object)
}
fn same_record(a: &[u8], b: &[u8]) -> bool {
let checksum = ondisk::CSUM_FIELD_LEN;
let location = SuperBlock::BYTENR_OFFSET..SuperBlock::BYTENR_OFFSET + 8;
a.len() == b.len()
&& a[checksum..location.start] == b[checksum..location.start]
&& a[location.end..] == b[location.end..]
}
fn check_readable(sb: &SuperBlock) -> Result<(), ReadError> {
if sb.csum_type.digest_len().is_none() {
return Err(ReadError::UnsupportedChecksum {
csum_type: sb.csum_type.value(),
});
}
let unsupported = sb.incompat_flags.without(SUPPORTED_INCOMPAT);
if !unsupported.is_empty() {
let mut names = String::new();
unsupported.describe(&mut names);
return Err(ReadError::UnsupportedFeatures {
bits: unsupported.bits(),
names,
});
}
if sb.num_devices != 1 {
return Err(ReadError::MultiDevice {
num_devices: sb.num_devices,
});
}
for (field, value) in [("sector size", sb.sectorsize), ("node size", sb.nodesize)] {
if !(MIN_BLOCK_SIZE..=MAX_BLOCK_SIZE).contains(&value) || !value.is_power_of_two() {
return Err(ReadError::BadGeometry {
field,
value: u64::from(value),
});
}
}
if sb.nodesize < sb.sectorsize {
return Err(ReadError::BadGeometry {
field: "node size, which is never smaller than the sector size",
value: u64::from(sb.nodesize),
});
}
if sb.dev_item.fsid != sb.metadata_id() {
return Err(ReadError::BadSuperblock {
fault: "the device it describes belongs to another filesystem",
});
}
if sb.dev_item.total_bytes == 0 {
return Err(ReadError::BadSuperblock {
fault: "the device it describes has no length",
});
}
if sb.root == 0 || sb.chunk_root == 0 {
return Err(ReadError::BadSuperblock {
fault: "a tree this filesystem cannot be read without has no root",
});
}
Ok(())
}
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum ReadError {
#[error("i/o error ({kind:?}): {message}")]
#[non_exhaustive]
Io {
kind: std::io::ErrorKind,
message: String,
},
#[error("no btrfs superblock at any of the three locations the format defines")]
NotBtrfs,
#[error(transparent)]
Parse(#[from] ParseError),
#[error("{object} at {at}: the checksum does not cover it")]
#[non_exhaustive]
BadChecksum {
object: &'static str,
at: u64,
},
#[error("a superblock at {expected} records {bytenr} as its own location")]
#[non_exhaustive]
MisplacedSuperblock {
expected: u64,
bytenr: u64,
},
#[error("superblock copy {mirror} at {at}: {fault}")]
#[non_exhaustive]
MirrorDisagreement {
mirror: usize,
at: u64,
fault: &'static str,
},
#[error("checksum algorithm {csum_type} is not one the format defines")]
#[non_exhaustive]
UnsupportedChecksum {
csum_type: u16,
},
#[error(
"unsupported incompatible features: {names} ({bits:#x}){}",
DecodersFor(*.bits)
)]
#[non_exhaustive]
UnsupportedFeatures {
bits: u64,
names: String,
},
#[error("a filesystem of {num_devices} devices cannot be read from one image")]
#[non_exhaustive]
MultiDevice {
num_devices: u64,
},
#[error(
"the chunk at {logical} has a profile this crate cannot read from one device ({flags:#x})"
)]
#[non_exhaustive]
UnsupportedProfile {
logical: u64,
flags: u64,
},
#[error("{field} is {value}, which the format does not define")]
#[non_exhaustive]
BadGeometry {
field: &'static str,
value: u64,
},
#[error("superblock: {fault}")]
#[non_exhaustive]
BadSuperblock {
fault: &'static str,
},
#[error("the superblock's bootstrap chunk array, at byte {at}: {fault}")]
#[non_exhaustive]
BadBootstrap {
at: usize,
fault: &'static str,
},
#[error("the chunk at {logical}: {fault}")]
#[non_exhaustive]
BadChunk {
logical: u64,
fault: &'static str,
},
#[error("two chunks map the logical address {logical}")]
#[non_exhaustive]
ChunkOverlap {
logical: u64,
},
#[error("no chunk maps {len} bytes at the logical address {logical}")]
#[non_exhaustive]
UnmappedLogical {
logical: u64,
len: u64,
},
#[error(
"the tree block at {logical} was written by transaction {generation}, and what points \
at it records transaction {expected}"
)]
#[non_exhaustive]
WrongGeneration {
logical: u64,
generation: u64,
expected: u64,
},
#[error("the tree block at {logical}: {fault}")]
#[non_exhaustive]
BadTreeBlock {
logical: u64,
fault: &'static str,
},
#[error("item {index} of the leaf at {logical}: {fault}")]
#[non_exhaustive]
BadItem {
logical: u64,
index: usize,
fault: &'static str,
},
#[error("the root item for tree {objectid}: {source}")]
#[non_exhaustive]
BadRootItem {
objectid: u64,
source: ParseError,
},
#[error("the tree block at {logical} is reachable from itself")]
#[non_exhaustive]
TreeCycle {
logical: u64,
},
#[error("the tree block at {logical} is at level {level} below a parent at level {parent}")]
#[non_exhaustive]
BadTreeLevel {
logical: u64,
level: u8,
parent: u8,
},
#[error("a walk of tree {objectid} reached the limit of {limit} entries")]
#[non_exhaustive]
TooManyEntries {
objectid: u64,
limit: usize,
},
#[error("the filesystem has no tree {objectid}")]
#[non_exhaustive]
MissingTree {
objectid: u64,
},
#[error("subvolume {tree} holds no inode {inode}")]
#[non_exhaustive]
MissingInode {
tree: u64,
inode: u64,
},
#[error("not a directory: {}", crate::escape::printable(.path))]
#[non_exhaustive]
NotADirectory {
path: Vec<u8>,
},
#[error("inode {inode} of subvolume {tree} is not a symbolic link")]
#[non_exhaustive]
NotASymlink {
tree: u64,
inode: u64,
},
#[error("no such path: {}", crate::escape::printable(.path))]
#[non_exhaustive]
NotFound {
path: Vec<u8>,
},
#[error("{} is not a name a directory can hold", crate::escape::printable(.name))]
#[non_exhaustive]
HostileName {
name: Vec<u8>,
},
#[error(
"a directory entry names directory inode {inode} of subvolume {tree}, which the tree \
reaches by another name as well"
)]
#[non_exhaustive]
RepeatedDirectory {
tree: u64,
inode: u64,
},
#[error("an entry of inode {inode} in subvolume {tree}: {fault} (item type {kind})")]
#[non_exhaustive]
BadDirEntry {
tree: u64,
inode: u64,
fault: &'static str,
kind: u8,
},
#[error("the extended attributes of inode {inode} in subvolume {tree} do not frame")]
#[non_exhaustive]
BadXattr {
tree: u64,
inode: u64,
},
#[error("the extent at offset {at} of inode {inode} in subvolume {tree}: {fault}")]
#[non_exhaustive]
BadExtent {
tree: u64,
inode: u64,
at: u64,
fault: &'static str,
},
#[error(
"inode {inode} of subvolume {tree} is compressed with {}, which this build does not \
decode{}",
crate::btrfs::ondisk::Compression::from_u8(*.compression)
.name()
.unwrap_or("an algorithm the format has not defined"),
crate::compress::CompiledBy(
crate::btrfs::decode::algorithm(crate::btrfs::ondisk::Compression::from_u8(
*.compression
))
.flatten()
)
)]
#[non_exhaustive]
UnsupportedCompression {
tree: u64,
inode: u64,
compression: u8,
},
#[error(
"the extent at offset {at} of inode {inode} in subvolume {tree} does not decode: {fault}"
)]
#[non_exhaustive]
BadCompressedExtent {
tree: u64,
inode: u64,
at: u64,
fault: String,
},
#[error(
"inode {inode} of subvolume {tree} is encoded ({encryption}, {other}), which this crate \
does not decode"
)]
#[non_exhaustive]
UnsupportedEncoding {
tree: u64,
inode: u64,
encryption: u8,
other: u16,
},
#[error(
"inode {inode} of subvolume {tree} is {size} bytes, more than the {cap}-byte cap this \
read is held to"
)]
#[non_exhaustive]
FileTooLarge {
tree: u64,
inode: u64,
size: u64,
cap: u64,
},
#[error("a walk of this filesystem reached the limit of {limit} names")]
#[non_exhaustive]
WalkTooLarge {
limit: usize,
},
#[error("the data at {logical} does not match the checksum recorded for it")]
#[non_exhaustive]
DataChecksum {
logical: u64,
},
#[error("no checksum is recorded for the data at {logical}")]
#[non_exhaustive]
MissingDataChecksum {
logical: u64,
},
#[error("a path longer than this crate builds: {}", crate::escape::printable(.path))]
#[non_exhaustive]
PathTooLong {
path: Vec<u8>,
},
#[error("too many symbolic links resolving {}", crate::escape::printable(.path))]
#[non_exhaustive]
SymlinkLoop {
path: Vec<u8>,
},
}
io_error!(ReadError);
impl<R: Read + Seek> Volume<R> {
#[cfg(test)]
pub(crate) fn with_cache_capacity(mut self, capacity: usize) -> Self {
self.cache = BlockCache::new(capacity);
self
}
pub(super) fn walk_limit(&self) -> usize {
self.limits.max_walk_entries
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::btrfs::ondisk::{CSUM_FIELD_LEN, CompatFlags, CompatRoFlags, DevItem, SuperFlags};
#[test]
fn a_refused_compression_names_the_feature_that_decodes_it() {
let refused = ReadError::UnsupportedCompression {
tree: 5,
inode: 257,
compression: 3,
};
assert_eq!(
refused.to_string(),
"inode 257 of subvolume 5 is compressed with zstd, which this build does not \
decode; the `zstd` feature compiles its decoder"
);
let undefined = ReadError::UnsupportedCompression {
tree: 5,
inode: 257,
compression: 0x7f,
};
assert_eq!(
undefined.to_string(),
"inode 257 of subvolume 5 is compressed with an algorithm the format has not \
defined, which this build does not decode"
);
}
#[test]
fn a_refused_compression_bit_names_the_feature_that_decodes_it() {
let mut names = String::new();
IncompatFlags::COMPRESS_ZSTD.describe(&mut names);
let refused = ReadError::UnsupportedFeatures {
bits: IncompatFlags::COMPRESS_ZSTD.bits(),
names,
};
assert_eq!(
refused.to_string(),
"unsupported incompatible features: compress-zstd (0x10); the `zstd` feature \
compiles its decoder"
);
let mut names = String::new();
IncompatFlags::RAID56.describe(&mut names);
let raid = ReadError::UnsupportedFeatures {
bits: IncompatFlags::RAID56.bits(),
names: names.clone(),
};
assert_eq!(
raid.to_string(),
format!("unsupported incompatible features: {names} (0x80)")
);
for (flag, algorithm) in COMPRESSION_BITS {
assert_eq!(
SUPPORTED_INCOMPAT.contains(flag),
algorithm.available(),
"{flag:?}"
);
}
}
fn a_superblock() -> SuperBlock {
let mut sb = SuperBlock {
csum: [0; CSUM_FIELD_LEN],
fsid: [0x11; 16],
bytenr: MIRRORS[0],
flags: SuperFlags::NONE,
magic: ondisk::MAGIC,
generation: 8,
root: 30_605_312,
chunk_root: 22_036_480,
log_root: 0,
total_bytes: 1 << 30,
bytes_used: 163_840,
root_dir_objectid: 6,
num_devices: 1,
sectorsize: 4096,
nodesize: 16_384,
stripesize: 4096,
sys_chunk_array_size: 0,
chunk_root_generation: 8,
compat_flags: CompatFlags::NONE,
compat_ro_flags: CompatRoFlags::NONE,
incompat_flags: IncompatFlags::MIXED_BACKREF,
csum_type: ChecksumType::CRC32C,
root_level: 0,
chunk_root_level: 0,
log_root_level: 0,
dev_item: DevItem {
devid: 1,
total_bytes: 1 << 30,
bytes_used: 0,
io_align: 4096,
io_width: 4096,
sector_size: 4096,
ty: 0,
generation: 0,
start_offset: 0,
dev_group: 0,
seek_speed: 0,
bandwidth: 0,
uuid: [0xec; 16],
fsid: [0x11; 16],
},
label: [0; ondisk::LABEL_SIZE],
cache_generation: 0,
uuid_tree_generation: 0,
metadata_uuid: [0; 16],
nr_global_roots: 0,
remap_root: 0,
remap_root_generation: 0,
remap_root_level: 0,
sys_chunk_array: [0; ondisk::SYS_CHUNK_ARRAY_SIZE],
};
sb.sys_chunk_array_size = 0;
sb
}
#[test]
fn a_feature_bit_this_crate_does_not_implement_is_refused_by_name() {
let sb = SuperBlock {
incompat_flags: IncompatFlags::MIXED_BACKREF | IncompatFlags::RAID_STRIPE_TREE,
..a_superblock()
};
let err = check_readable(&sb).expect_err("a stripe tree is not readable here");
let ReadError::UnsupportedFeatures { bits, names } = err else {
panic!("expected an unsupported-feature refusal, got {err:?}");
};
assert_eq!(bits, IncompatFlags::RAID_STRIPE_TREE.bits());
assert_eq!(names, "raid-stripe-tree");
let future = SuperBlock {
incompat_flags: IncompatFlags::from_bits(1 << 40),
..a_superblock()
};
let err = check_readable(&future).expect_err("a bit from the future");
assert!(format!("{err}").contains("bit 40"), "{err}");
}
#[test]
fn the_five_defaults_and_the_two_this_layer_reads_are_supported() {
let sb = SuperBlock {
incompat_flags: IncompatFlags::from_bits(0x361),
..a_superblock()
};
check_readable(&sb).expect("the baseline's default feature set");
assert_eq!(SUPPORTED_INCOMPAT.bits() & 0x361, 0x361);
}
#[test]
fn a_filesystem_that_spans_devices_is_refused_rather_than_read_as_a_part_of_itself() {
let sb = SuperBlock {
num_devices: 2,
..a_superblock()
};
assert!(matches!(
check_readable(&sb),
Err(ReadError::MultiDevice { num_devices: 2 })
));
}
#[test]
fn a_geometry_the_format_does_not_define_is_refused_at_open() {
for (sectorsize, nodesize) in [
(2048, 16_384), (4096, 131_072), (4096, 24_576), (16_384, 4096), ] {
let sb = SuperBlock {
sectorsize,
nodesize,
..a_superblock()
};
assert!(
matches!(check_readable(&sb), Err(ReadError::BadGeometry { .. })),
"sector {sectorsize}, node {nodesize}"
);
}
for size in [4096u32, 8192, 16_384, 32_768, 65_536] {
let sb = SuperBlock {
sectorsize: size,
nodesize: size,
..a_superblock()
};
check_readable(&sb)
.unwrap_or_else(|e| panic!("{size} is a size the format defines: {e}"));
}
}
#[test]
fn every_checksum_algorithm_the_format_defines_is_read_and_another_is_named() {
for value in [0u16, 1, 2, 3] {
let sb = SuperBlock {
csum_type: ChecksumType::from_value(value),
..a_superblock()
};
check_readable(&sb).unwrap_or_else(|e| panic!("checksum type {value}: {e}"));
}
for value in [4u16, 9, u16::MAX] {
let sb = SuperBlock {
csum_type: ChecksumType::from_value(value),
..a_superblock()
};
assert!(matches!(
check_readable(&sb),
Err(ReadError::UnsupportedChecksum { .. })
));
}
}
#[test]
fn a_superblock_describing_another_filesystems_device_is_refused() {
let mut sb = a_superblock();
sb.dev_item.fsid = [0x22; 16];
assert!(matches!(
check_readable(&sb),
Err(ReadError::BadSuperblock { .. })
));
for sb in [
SuperBlock {
root: 0,
..a_superblock()
},
SuperBlock {
chunk_root: 0,
..a_superblock()
},
] {
assert!(matches!(
check_readable(&sb),
Err(ReadError::BadSuperblock { .. })
));
}
}
use crate::btrfs::forge::{CHUNK_LOGICAL, CHUNK_TREE_AT, DEVICE_BYTES, Forge, ROOT_TREE_AT};
const TWO_MIRRORS: u64 = (64 << 20) + (2 << 20);
const THREE_MIRRORS: u64 = (256 << 30) + SUPER_INFO_SIZE as u64;
#[test]
fn a_device_carries_every_copy_of_the_superblock_it_has_room_for_and_no_other() {
for (bytes, expected) in [(DEVICE_BYTES, 1), (TWO_MIRRORS, 2), (THREE_MIRRORS, 3)] {
let volume = Volume::open(Forge::of_size(bytes).source())
.unwrap_or_else(|e| panic!("a {bytes}-byte device: {e}"));
let present = volume
.mirrors()
.iter()
.filter(|m| matches!(m, Mirror::Present { .. }))
.count();
assert_eq!(present, expected, "a device of {bytes} bytes");
assert!(
volume.mirrors()[expected..]
.iter()
.all(|m| *m == Mirror::OutsideDevice),
"every location past the last copy is outside the device"
);
}
}
#[test]
fn a_copy_is_written_only_where_the_device_holds_all_of_it() {
let exact = Volume::open(Forge::of_size(256 << 30).source()).expect("a formatted device");
assert_eq!(exact.mirrors()[2], Mirror::OutsideDevice);
let one_more =
Volume::open(Forge::of_size(THREE_MIRRORS).source()).expect("a formatted device");
assert!(matches!(one_more.mirrors()[2], Mirror::Present { .. }));
}
#[test]
fn the_newest_copy_of_the_superblock_is_the_one_the_filesystem_is_read_through() {
let mut forge = Forge::of_size(TWO_MIRRORS);
forge.amend_superblock(1, |sb| {
sb.generation = 99;
sb.root = CHUNK_LOGICAL;
});
let volume = Volume::open_with(
forge.source(),
OpenOptions::new().policy(ReadPolicy::Lenient),
)
.expect("a filesystem whose copies disagree still opens leniently");
assert_eq!(volume.superblock().generation, 99);
assert_eq!(volume.superblock().root, CHUNK_LOGICAL);
assert_eq!(
volume.mirrors()[0].generation(),
Some(super::super::forge::GENERATION)
);
assert_eq!(volume.mirrors()[1].generation(), Some(99));
}
#[test]
fn a_copy_that_disagrees_with_the_live_one_is_refused_strictly_and_recorded_leniently() {
type Damage = (&'static str, Box<dyn Fn(&mut Forge)>, Mirror);
let damage: [Damage; 5] = [
(
"a checksum that no longer covers it",
Box::new(|f: &mut Forge| {
f.break_superblock(1);
}),
Mirror::Damaged,
),
(
"a copy left behind by an earlier transaction",
Box::new(|f: &mut Forge| {
f.amend_superblock(1, |sb| sb.generation = 1);
}),
Mirror::Present { generation: 1 },
),
(
"a copy written somewhere other than where it says it is",
Box::new(|f: &mut Forge| {
f.copy_superblock(0, 1);
}),
Mirror::Misplaced { bytenr: MIRRORS[0] },
),
(
"a copy naming another filesystem",
Box::new(|f: &mut Forge| {
f.amend_superblock(1, |sb| sb.fsid[0] ^= 1);
}),
Mirror::Foreign,
),
(
"a copy at the live generation recording another label",
Box::new(|f: &mut Forge| {
f.amend_superblock(1, |sb| sb.label[0] ^= 1);
}),
Mirror::Diverged {
generation: super::super::forge::GENERATION,
},
),
];
for (what, apply, expected) in damage {
let mut forge = Forge::of_size(TWO_MIRRORS);
apply(&mut forge);
let strict = Volume::open(forge.source()).err();
assert!(
matches!(
strict,
Some(ReadError::MirrorDisagreement { mirror: 1, .. })
),
"{what}: {strict:?}"
);
let lenient = Volume::open_with(
forge.source(),
OpenOptions::new().policy(ReadPolicy::Lenient),
)
.unwrap_or_else(|e| panic!("{what} opens leniently: {e}"));
assert_eq!(lenient.mirrors()[1], expected, "{what}");
assert_eq!(
lenient.superblock().generation,
super::super::forge::GENERATION
);
}
}
#[test]
fn a_damaged_first_copy_is_read_through_the_second_rather_than_refused_outright() {
let mut forge = Forge::of_size(TWO_MIRRORS);
forge.break_superblock(0);
let volume = Volume::open_with(
forge.source(),
OpenOptions::new().policy(ReadPolicy::Lenient),
)
.expect("the second copy is intact");
assert_eq!(volume.mirrors()[0], Mirror::Damaged);
assert!(matches!(volume.mirrors()[1], Mirror::Present { .. }));
let mut forge = Forge::of_size(TWO_MIRRORS);
forge.break_superblock(0).break_superblock(1);
assert!(matches!(
Volume::open_with(
forge.source(),
OpenOptions::new().policy(ReadPolicy::Lenient)
)
.err(),
Some(ReadError::BadChecksum {
object: "superblock",
..
})
));
}
#[test]
fn a_source_with_no_btrfs_in_it_says_so_rather_than_naming_a_structure() {
let empty = std::io::Cursor::new(vec![0u8; 1 << 20]);
assert!(matches!(
Volume::open(empty).err(),
Some(ReadError::NotBtrfs)
));
let tiny = std::io::Cursor::new(vec![0u8; 1024]);
assert!(matches!(
Volume::open(tiny).err(),
Some(ReadError::NotBtrfs)
));
}
#[test]
fn a_source_shorter_than_the_device_it_describes_is_reported_as_that() {
let forge = Forge::of_size(TWO_MIRRORS);
let short = forge.truncated(2 << 20);
assert!(matches!(
Volume::open(short).err(),
Some(ReadError::MirrorDisagreement { mirror: 1, .. })
));
let short = forge.truncated(2 << 20);
let lenient = Volume::open_with(short, OpenOptions::new().policy(ReadPolicy::Lenient))
.expect("lenient");
assert_eq!(lenient.mirrors()[1], Mirror::Truncated);
}
#[test]
fn a_filesystem_inside_a_partition_is_read_from_where_the_caller_says_it_begins() {
const BASE: u64 = 1 << 20;
let forge = Forge::new();
let mut device = vec![0u8; BASE as usize];
let mut source = forge.source();
std::io::Read::read_to_end(&mut source, &mut device).expect("the forged device");
let mut volume =
Volume::open_with(std::io::Cursor::new(device), OpenOptions::new().base(BASE))
.expect("a filesystem a mebibyte into its source");
assert!(matches!(volume.mirrors()[0], Mirror::Present { .. }));
let root = volume.root_tree();
assert_eq!(root.bytenr, ROOT_TREE_AT);
volume
.tree(root)
.count_items()
.expect("the root tree reads");
}
#[test]
fn the_chunk_tree_is_read_through_the_bootstrap_and_completes_the_map() {
let volume = Volume::open(Forge::new().source()).expect("a forged filesystem");
assert_eq!(volume.chunk_map().len(), 1);
let chunk = &volume.chunk_map().chunks()[0];
assert_eq!(chunk.logical, CHUNK_LOGICAL);
assert_eq!(chunk.copies.len(), 1);
assert_ne!(
chunk.copies[0], chunk.logical,
"the mapping is not the identity"
);
}
#[test]
fn a_chunk_tree_that_moves_a_bootstrap_chunk_is_refused_strictly_and_recorded_leniently() {
let mut forge = Forge::new();
forge.amend(CHUNK_TREE_AT, |block| {
let item = ondisk::Item::read_from(&block[Header::SIZE..]).expect("the one item");
let stripe_offset = Header::SIZE + item.offset as usize + Chunk::SIZE + 8;
let moved = crate::bytes::get_u64(block, stripe_offset) + (64 << 10);
block[stripe_offset..stripe_offset + 8].copy_from_slice(&moved.to_le_bytes());
});
assert!(
matches!(
Volume::open(forge.source()).err(),
Some(ReadError::BadChunk { logical, .. }) if logical == CHUNK_LOGICAL
),
"a strict open refuses two mappings of one chunk"
);
let lenient = Volume::open_with(
forge.source(),
OpenOptions::new().policy(ReadPolicy::Lenient),
)
.expect("a lenient open keeps the bootstrap's mapping");
assert_eq!(lenient.bootstrap_conflicts(), [CHUNK_LOGICAL]);
assert_eq!(lenient.chunk_map().len(), 1);
assert_eq!(
lenient.chunk_map().chunks()[0].copies,
[super::super::forge::CHUNK_PHYSICAL]
);
let clean = Volume::open(Forge::new().source()).expect("the forged filesystem");
assert!(clean.bootstrap_conflicts().is_empty());
}
#[test]
fn a_checksum_is_only_held_to_hold_for_the_algorithm_that_produced_it() {
let mut object = vec![0u8; SUPER_INFO_SIZE];
object[64..72].copy_from_slice(&ondisk::MAGIC);
let digest = ondisk::checksum(&object);
object[..4].copy_from_slice(&digest.to_le_bytes());
assert!(checksum_holds(&object, ChecksumType::CRC32C));
object[100] ^= 0xff;
assert!(!checksum_holds(&object, ChecksumType::CRC32C));
object[100] ^= 0xff;
assert!(checksum_holds(&object, ChecksumType::CRC32C));
object[7] = 1;
assert!(!checksum_holds(&object, ChecksumType::CRC32C));
object[7] = 0;
assert!(!checksum_holds(&object, ChecksumType::SHA256));
}
}