use std::io::{Cursor, Seek, Write};
use crate::Timestamp;
use crate::fidelity::FidelityReport;
use crate::io::ByteSink;
use crate::source::{CONTENT_WINDOW, Source};
use super::MappedChunk;
use super::btree::levels_above;
use super::geometry::{
BtrfsLayout, CSUM_BYTES_PER_SECTOR, GeometryError, MAX_CSUM_RECORD, MIRROR_WINDOW, PlanRequest,
Pool, RESERVED_HEAD, ReservationExceeded, STRIPE_LEN, Slack, block_sizes, mirror_windows,
plan_layout,
};
use super::model::{
BtrfsModel, DirEntry, EntryTarget, MAX_EXTENT_BYTES, ModelError, ModelObject, ModelSubvolume,
ObjectKind, SubvolumeRequest, build_model,
};
use super::ondisk::{
BACKREF_REV_MIXED, BACKREF_REV_SHIFT, BlockGroupFlags, BlockGroupItem, CSUM_FIELD_LEN,
ChecksumType, Chunk, CompatFlags, CompatRoFlags, DevExtent, DevItem, DevStats, DirEntryType,
DirItem, DiskKey, ExtentDataRef, ExtentFlags, ExtentItem, ExtentKind, FileExtentItem,
FreeSpaceInfo, HEADER_FLAG_WRITTEN, Header, IncompatFlags, InlineRef, InodeExtref, InodeFlags,
InodeItem, InodeRef, Item, ItemType, KeyPtr, LABEL_SIZE, MAGIC, MIRRORS, RootBackup, RootFlags,
RootItem, RootRef, SUPER_INFO_SIZE, SYS_CHUNK_ARRAY_SIZE, Stripe, SuperBlock, SuperFlags,
crc32c_over, extref_hash, name_hash, objectid, seal, uuid_key,
};
pub const GENERATION: u64 = 1;
pub const DEVICE_ID: u64 = 1;
const SUBVOLUME_NAME: &[u8] = b"default";
const PARENT_NAME: &[u8] = b"..";
const DIRECTORY_MODE: u32 = 0o040_755;
const NO_FREE_SPACE_CACHE: u64 = u64::MAX;
const LAYOUT_ROUNDS: usize = 8;
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct VolumeLabel([u8; LABEL_SIZE]);
impl VolumeLabel {
pub const MAX_BYTES: usize = LABEL_SIZE - 1;
pub const UNNAMED: Self = Self([0; LABEL_SIZE]);
pub fn new(name: &str) -> Result<Self, LabelError> {
Self::from_bytes(name.as_bytes())
}
pub fn from_bytes(name: &[u8]) -> Result<Self, LabelError> {
if name.len() > Self::MAX_BYTES {
return Err(LabelError::TooLong {
bytes: name.len(),
limit: Self::MAX_BYTES,
});
}
if let Some(at) = name.iter().position(|&byte| byte == 0) {
return Err(LabelError::NulByte { at });
}
let mut field = [0u8; LABEL_SIZE];
field[..name.len()].copy_from_slice(name);
Ok(Self(field))
}
#[must_use]
pub fn as_bytes(&self) -> &[u8] {
let end = self
.0
.iter()
.position(|&byte| byte == 0)
.unwrap_or(LABEL_SIZE);
&self.0[..end]
}
const fn field(&self) -> [u8; LABEL_SIZE] {
self.0
}
}
impl Default for VolumeLabel {
fn default() -> Self {
Self::UNNAMED
}
}
impl core::fmt::Debug for VolumeLabel {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match core::str::from_utf8(self.as_bytes()) {
Ok(text) => write!(f, "VolumeLabel({text:?})"),
Err(_) => write!(f, "VolumeLabel({:?})", self.as_bytes()),
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum LabelError {
#[error("a label of {bytes} bytes exceeds the {limit} the superblock holds")]
#[non_exhaustive]
TooLong {
bytes: usize,
limit: usize,
},
#[error("a label may not contain a NUL byte, and this one does at byte {at}")]
#[non_exhaustive]
NulByte {
at: usize,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct FormatOptions {
pub fsid: [u8; 16],
pub metadata_uuid: Option<[u8; 16]>,
pub chunk_tree_uuid: [u8; 16],
pub device_uuid: [u8; 16],
pub subvolume_uuid: [u8; 16],
pub time: Timestamp,
pub label: VolumeLabel,
pub plan: PlanRequest,
pub subvolumes: Vec<SubvolumeRequest>,
pub default_subvolume: Option<Vec<u8>>,
}
impl FormatOptions {
#[must_use]
pub const fn new(fsid: [u8; 16], time: Timestamp) -> Self {
Self {
fsid,
metadata_uuid: None,
chunk_tree_uuid: [0; 16],
device_uuid: [0; 16],
subvolume_uuid: [0; 16],
time,
label: VolumeLabel::UNNAMED,
plan: PlanRequest::new(0),
subvolumes: Vec::new(),
default_subvolume: None,
}
}
#[must_use]
pub fn label(mut self, label: VolumeLabel) -> Self {
self.label = label;
self
}
#[must_use]
pub fn metadata_uuid(mut self, uuid: Option<[u8; 16]>) -> Self {
self.metadata_uuid = uuid;
self
}
#[must_use]
pub fn chunk_tree_uuid(mut self, uuid: [u8; 16]) -> Self {
self.chunk_tree_uuid = uuid;
self
}
#[must_use]
pub fn device_uuid(mut self, uuid: [u8; 16]) -> Self {
self.device_uuid = uuid;
self
}
#[must_use]
pub fn subvolume_uuid(mut self, uuid: [u8; 16]) -> Self {
self.subvolume_uuid = uuid;
self
}
#[must_use]
pub fn plan(mut self, plan: PlanRequest) -> Self {
self.plan = plan;
self
}
#[must_use]
pub fn subvolume(mut self, request: SubvolumeRequest) -> Self {
self.subvolumes.push(request);
self
}
#[must_use]
pub fn default_subvolume(mut self, path: impl Into<Vec<u8>>) -> Self {
self.default_subvolume = Some(path.into());
self
}
fn metadata_id(&self) -> [u8; 16] {
self.metadata_uuid.unwrap_or(self.fsid)
}
fn distinct_metadata_uuid(&self) -> Option<[u8; 16]> {
self.metadata_uuid.filter(|uuid| *uuid != self.fsid)
}
}
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum FormatError {
#[error(transparent)]
Io(#[from] std::io::Error),
#[error(transparent)]
Geometry(#[from] GeometryError),
#[error(transparent)]
Model(#[from] ModelError),
#[error("slack of {hundredths} hundredths of a percent is past the limit of {limit}")]
#[non_exhaustive]
SlackShareTooLarge {
hundredths: u16,
limit: u16,
},
#[error("no filesystem up to {ceiling} bytes holds the tree with the room asked for")]
#[non_exhaustive]
DoesNotFit {
ceiling: u64,
},
#[error(transparent)]
Reservation(#[from] ReservationExceeded),
#[error("a record of {bytes} bytes does not fit a leaf, which holds {capacity}")]
#[non_exhaustive]
RecordTooLarge {
bytes: usize,
capacity: usize,
},
#[error("the layout did not settle in {LAYOUT_ROUNDS} rounds")]
LayoutUnsettled,
#[error("the data block groups were planned for {planned} bytes and did not hold them")]
#[non_exhaustive]
DataExhausted {
planned: u64,
},
#[error(
"{} seconds and {} nanoseconds since 1970 is not a time the filesystem records",
time.secs,
time.nanos
)]
#[non_exhaustive]
TimeOutOfRange {
time: Timestamp,
},
#[error("an image of {bytes} bytes cannot be held in memory on this machine")]
#[non_exhaustive]
ImageTooLargeInMemory {
bytes: u64,
},
}
pub struct Image {
bytes: Vec<u8>,
layout: BtrfsLayout,
slack: Slack,
fidelity: FidelityReport,
}
impl Image {
#[must_use]
pub fn fidelity(&self) -> &FidelityReport {
&self.fidelity
}
#[must_use]
pub fn as_bytes(&self) -> &[u8] {
&self.bytes
}
#[must_use]
pub fn into_bytes(self) -> Vec<u8> {
self.bytes
}
#[must_use]
pub fn layout(&self) -> &BtrfsLayout {
&self.layout
}
#[must_use]
pub fn slack(&self) -> Slack {
self.slack
}
pub fn write_to(&self, mut w: impl Write) -> std::io::Result<()> {
w.write_all(&self.bytes)
}
}
pub struct FormatPlan {
prepared: Prepared,
volume_bytes: u64,
options: FormatOptions,
}
impl FormatPlan {
pub fn new(
source: impl Source,
volume_bytes: u64,
options: FormatOptions,
) -> Result<Self, FormatError> {
Ok(Self {
prepared: prepare(source, volume_bytes, &options)?,
volume_bytes,
options,
})
}
pub fn fit(
source: impl Source,
options: FormatOptions,
slack: crate::Slack,
) -> Result<Self, FormatError> {
let (request, model) = modelled(source, &options)?;
let layout = crate::btrfs::fit::search(&request, slack)?;
Ok(Self {
volume_bytes: layout.volume_bytes,
prepared: Prepared { model, layout },
options,
})
}
#[cfg(test)]
pub(crate) const fn content(&self) -> super::geometry::Content {
self.prepared.model.content
}
#[must_use]
pub fn layout(&self) -> &BtrfsLayout {
&self.prepared.layout
}
#[must_use]
pub const fn volume_bytes(&self) -> u64 {
self.volume_bytes
}
#[must_use]
pub fn fidelity(&self) -> &FidelityReport {
&self.prepared.model.fidelity
}
pub fn write_to(&self, sink: impl Write + Seek) -> Result<Slack, FormatError> {
write_filesystem(sink, &self.prepared, &self.options, self.volume_bytes)
}
}
pub fn format(
source: impl Source,
volume_bytes: u64,
options: FormatOptions,
) -> Result<Image, FormatError> {
let plan = FormatPlan::new(source, volume_bytes, options)?;
let buffer =
crate::io::image_buffer(volume_bytes).ok_or(FormatError::ImageTooLargeInMemory {
bytes: volume_bytes,
})?;
let mut image = Cursor::new(buffer);
let slack = plan.write_to(&mut image)?;
Ok(Image {
bytes: image.into_inner(),
layout: plan.prepared.layout,
slack,
fidelity: plan.prepared.model.fidelity,
})
}
pub fn format_to<W: Write + Seek>(
sink: W,
source: impl Source,
volume_bytes: u64,
options: FormatOptions,
) -> Result<BtrfsLayout, FormatError> {
let plan = FormatPlan::new(source, volume_bytes, options)?;
plan.write_to(sink)?;
Ok(plan.prepared.layout)
}
struct Prepared {
model: BtrfsModel,
layout: BtrfsLayout,
}
fn prepare(
source: impl Source,
volume_bytes: u64,
options: &FormatOptions,
) -> Result<Prepared, FormatError> {
let (mut request, model) = modelled(source, options)?;
request.volume_bytes = volume_bytes;
let layout = plan_layout(&request)?;
Ok(Prepared { model, layout })
}
fn modelled(
source: impl Source,
options: &FormatOptions,
) -> Result<(PlanRequest, BtrfsModel), FormatError> {
if !options.time.has_proper_fraction() {
return Err(FormatError::TimeOutOfRange { time: options.time });
}
let mut request = options.plan;
let (sector_size, node_size) = block_sizes(&request)?;
let model = build_model(
source.into_entries(),
&options.subvolumes,
options.default_subvolume.as_deref(),
options.subvolume_uuid,
sector_size,
node_size,
options.time,
)?;
request.content = model.content;
joined_records_fit(&model, node_size)?;
Ok((request, model))
}
fn record_capacity(node_size: u32) -> usize {
node_size as usize - Header::SIZE - Item::SIZE
}
fn joined_records_fit(model: &BtrfsModel, node_size: u32) -> Result<(), FormatError> {
let capacity = record_capacity(node_size);
let check = |sizes: &mut dyn Iterator<Item = (u64, usize)>| {
let mut joined: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
for (hash, bytes) in sizes {
let total = joined.entry(hash).or_default();
*total += bytes;
if *total > capacity {
return Err(FormatError::RecordTooLarge {
bytes: *total,
capacity,
});
}
}
Ok(())
};
for object in model.subvolumes.iter().flat_map(|sub| &sub.objects) {
if let ObjectKind::Directory(entries) = &object.kind {
check(
&mut entries
.iter()
.map(|e| (name_hash(&e.name), DirItem::SIZE + e.name.len())),
)?;
}
check(&mut object.xattrs.iter().map(|x| {
(
name_hash(&x.name),
DirItem::SIZE + x.name.len() + x.value.len(),
)
}))?;
}
Ok(())
}
#[derive(Clone, PartialEq, Eq, Debug)]
struct Record {
key: DiskKey,
data: Vec<u8>,
}
impl Record {
fn cost(&self) -> usize {
self.data.len() + Item::SIZE
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
struct Shape {
leaves: Vec<usize>,
upper: Vec<u64>,
}
impl Shape {
fn blocks(&self) -> u64 {
self.upper.iter().sum::<u64>() + self.leaves.len() as u64
}
fn level(&self) -> u8 {
self.upper.len() as u8
}
}
fn shape(records: &[Record], node_size: u32) -> Result<Shape, FormatError> {
let capacity = node_size as usize - Header::SIZE;
let mut leaves = Vec::new();
let mut count = 0usize;
let mut used = 0usize;
for record in records {
let cost = record.cost();
if cost > capacity {
return Err(FormatError::RecordTooLarge {
bytes: record.data.len(),
capacity: capacity - Item::SIZE,
});
}
if used + cost > capacity {
leaves.push(count);
count = 0;
used = 0;
}
count += 1;
used += cost;
}
leaves.push(count);
Ok(Shape {
upper: levels_above(leaves.len() as u64, capacity as u64 / KeyPtr::SIZE as u64),
leaves,
})
}
fn sorted(mut records: Vec<Record>) -> Vec<Record> {
records.sort_by_key(|record| record.key);
records
}
fn encode(len: usize, fill: impl FnOnce(&mut [u8])) -> Vec<u8> {
let mut bytes = vec![0u8; len];
fill(&mut bytes);
bytes
}
#[derive(Clone)]
struct Allocation {
used: Vec<u64>,
reached: Vec<u64>,
windows: Vec<Vec<u64>>,
node_size: u64,
data_cursor: usize,
}
impl Allocation {
fn new(layout: &BtrfsLayout) -> Self {
Self {
used: vec![0; layout.chunks.len()],
reached: vec![0; layout.chunks.len()],
windows: layout
.chunks
.iter()
.map(|chunk| {
mirror_windows(chunk, &layout.superblock_mirrors)
.into_iter()
.map(|logical| logical - chunk.logical)
.collect()
})
.collect(),
node_size: u64::from(layout.node_size),
data_cursor: 0,
}
}
fn window_across(&self, index: usize, offset: u64, len: u64) -> Option<u64> {
self.windows[index]
.iter()
.find(|&&window| window < offset + len && offset < window + MIRROR_WINDOW)
.map(|&window| window + MIRROR_WINDOW)
}
fn take(
&mut self,
layout: &BtrfsLayout,
kind: BlockGroupFlags,
count: u64,
) -> Option<Vec<u64>> {
let mut out = Vec::with_capacity(count as usize);
for (index, chunk) in layout.chunks.iter().enumerate() {
if !chunk.flags.contains(kind) {
continue;
}
while out.len() as u64 != count && self.reached[index] + self.node_size <= chunk.length
{
let at = self.reached[index];
if let Some(past) = self.window_across(index, at, self.node_size) {
self.reached[index] = past;
continue;
}
out.push(chunk.logical + at);
self.reached[index] += self.node_size;
self.used[index] += self.node_size;
}
}
(out.len() as u64 == count).then_some(out)
}
fn take_data(&mut self, layout: &BtrfsLayout, bytes: u64) -> Option<(u64, u64)> {
while self.data_cursor < layout.chunks.len() {
let index = self.data_cursor;
let chunk = &layout.chunks[index];
if !chunk.flags.contains(BlockGroupFlags::DATA) {
self.data_cursor += 1;
continue;
}
let at = self.reached[index];
if let Some(past) = self.window_across(index, at, 1) {
self.reached[index] = past;
continue;
}
let stop = self.windows[index]
.iter()
.copied()
.find(|&window| window > at)
.unwrap_or(chunk.length);
let free = stop - at;
if free == 0 {
self.data_cursor += 1;
continue;
}
let granted = bytes.min(free);
self.reached[index] += granted;
self.used[index] += granted;
return Some((chunk.logical + at, granted));
}
None
}
fn free_runs(&self, index: usize, length: u64) -> Vec<(u64, u64)> {
let reached = self.reached[index];
let passed = self.windows[index]
.iter()
.filter(|&&window| window < reached)
.map(|&window| (window, MIRROR_WINDOW));
let tail = (reached < length).then_some((reached, length - reached));
let mut runs: Vec<(u64, u64)> = Vec::new();
for (start, len) in passed.chain(tail) {
match runs.last_mut() {
Some(last) if last.0 + last.1 == start => last.1 += len,
_ => runs.push((start, len)),
}
}
runs
}
fn blocks_of(&self, layout: &BtrfsLayout, kind: BlockGroupFlags) -> u64 {
self.bytes_of(layout, kind) / self.node_size
}
fn bytes_of(&self, layout: &BtrfsLayout, kind: BlockGroupFlags) -> u64 {
layout
.chunks
.iter()
.enumerate()
.filter(|(_, chunk)| chunk.flags.contains(kind))
.map(|(index, _)| self.used[index])
.sum()
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct DataExtent {
offset: u64,
logical: u64,
length: u64,
root: u64,
inode: u64,
}
impl DataExtent {
const fn logical_end(&self) -> u64 {
self.logical + self.length
}
}
struct DataPlan {
per_object: Vec<Vec<Vec<DataExtent>>>,
}
impl DataPlan {
fn ordered(&self) -> impl Iterator<Item = &DataExtent> {
self.per_object
.iter()
.flat_map(|subvolume| subvolume.iter().flatten())
}
}
fn plan_data(
model: &BtrfsModel,
layout: &BtrfsLayout,
allocation: &mut Allocation,
) -> Result<DataPlan, FormatError> {
let sector = u64::from(layout.sector_size);
let mut per_object = Vec::with_capacity(model.subvolumes.len());
for subvolume in &model.subvolumes {
let mut objects = Vec::with_capacity(subvolume.objects.len());
for object in &subvolume.objects {
let mut extents = Vec::new();
if let ObjectKind::File {
size,
inline: false,
..
} = object.kind
{
let stored = size.div_ceil(sector) * sector;
let mut at = 0;
while at < stored {
let want = (stored - at).min(MAX_EXTENT_BYTES);
let (logical, granted) =
allocation
.take_data(layout, want)
.ok_or(FormatError::DataExhausted {
planned: model.content.data_bytes,
})?;
extents.push(DataExtent {
offset: at,
logical,
length: granted,
root: subvolume.id,
inode: object.inode,
});
at += granted;
}
}
objects.push(extents);
}
per_object.push(objects);
}
Ok(DataPlan { per_object })
}
fn csum_records(data: &DataPlan, sector_size: u32) -> Vec<Record> {
let sector = u64::from(sector_size);
let per_record = MAX_CSUM_RECORD / CSUM_BYTES_PER_SECTOR;
let mut records: Vec<Record> = Vec::new();
let mut covered = 0;
for extent in data.ordered() {
let mut at = extent.logical;
while at < extent.logical_end() {
let room = match records.last() {
Some(last) if at == covered => {
per_record - last.data.len() as u64 / CSUM_BYTES_PER_SECTOR
}
_ => 0,
};
if room == 0 {
records.push(Record {
key: DiskKey::new(objectid::EXTENT_CSUM, ItemType::EXTENT_CSUM, at),
data: Vec::new(),
});
}
let last = records
.last_mut()
.expect("a record was just pushed or found");
let room = per_record - last.data.len() as u64 / CSUM_BYTES_PER_SECTOR;
let sectors = ((extent.logical_end() - at) / sector).min(room);
last.data.resize(
last.data.len() + (sectors * CSUM_BYTES_PER_SECTOR) as usize,
0,
);
at += sectors * sector;
covered = at;
}
}
records
}
struct CsumFill<'a> {
records: &'a mut [Record],
at: usize,
offset: usize,
}
impl<'a> CsumFill<'a> {
fn new(records: &'a mut [Record]) -> Self {
Self {
records,
at: 0,
offset: 0,
}
}
fn push(&mut self, digest: u32) {
while self
.records
.get(self.at)
.is_some_and(|record| self.offset == record.data.len())
{
self.at += 1;
self.offset = 0;
}
let record = &mut self.records[self.at];
crate::bytes::put_u32(&mut record.data, self.offset, digest);
self.offset += CSUM_BYTES_PER_SECTOR as usize;
}
fn finish(self) {
let filled = self.records[..self.at]
.iter()
.map(|record| record.data.len())
.sum::<usize>()
+ self.offset;
let wanted = self
.records
.iter()
.map(|record| record.data.len())
.sum::<usize>();
assert_eq!(
filled, wanted,
"the checksum tree was sized for bytes the data pass did not produce"
);
}
}
fn write_data<W: Write + Seek>(
sink: &mut ByteSink<W>,
model: &BtrfsModel,
layout: &BtrfsLayout,
data: &DataPlan,
csums: &mut CsumFill<'_>,
) -> Result<(), FormatError> {
let sector = layout.sector_size as usize;
let mut buffer = Vec::new();
for (subvolume, objects) in model.subvolumes.iter().zip(&data.per_object) {
for (object, extents) in subvolume.objects.iter().zip(objects) {
if extents.is_empty() {
continue;
}
let ObjectKind::File { content, .. } = object.kind else {
unreachable!("only a regular file is given data extents")
};
let content = &model.contents[content];
for extent in extents {
let mut done = 0u64;
while done < extent.length {
let n = (extent.length - done).min(CONTENT_WINDOW as u64);
let from = extent.offset + done;
let held = content.len().saturating_sub(from).min(n);
buffer.clear();
buffer.resize(n as usize, 0);
content.read_at(from, &mut buffer[..held as usize])?;
for at in (0..buffer.len()).step_by(sector) {
csums.push(crc32c_over(&buffer[at..at + sector]));
}
for offset in copies_of(layout, extent.logical) {
sink.write_at(offset + done, &buffer)?;
}
done += n;
}
}
}
}
Ok(())
}
struct BuiltTree {
objectid: u64,
records: Vec<Record>,
shape: Shape,
levels: Vec<Vec<u64>>,
}
impl BuiltTree {
fn place(
objectid: u64,
records: Vec<Record>,
layout: &BtrfsLayout,
allocation: &mut Allocation,
kind: BlockGroupFlags,
) -> Result<Self, FormatError> {
let shape = shape(&records, layout.node_size)?;
let addresses = allocation
.take(layout, kind, shape.blocks())
.ok_or_else(|| exhausted(layout, allocation, kind))?;
Ok(Self::from_addresses(objectid, records, shape, addresses))
}
fn from_addresses(
objectid: u64,
records: Vec<Record>,
shape: Shape,
addresses: Vec<u64>,
) -> Self {
let mut rest = addresses.as_slice();
let mut levels = Vec::with_capacity(shape.upper.len() + 1);
let (leaves, tail) = rest.split_at(shape.leaves.len());
levels.push(leaves.to_vec());
rest = tail;
for width in &shape.upper {
let (level, tail) = rest.split_at(*width as usize);
levels.push(level.to_vec());
rest = tail;
}
Self {
objectid,
records,
shape,
levels,
}
}
fn root(&self) -> u64 {
self.levels
.last()
.and_then(|level| level.first())
.copied()
.expect("every tree has a root block")
}
fn blocks(&self) -> u64 {
self.shape.blocks()
}
fn extents(&self) -> impl Iterator<Item = (u64, u8)> + '_ {
self.levels
.iter()
.enumerate()
.flat_map(|(level, blocks)| blocks.iter().map(move |address| (*address, level as u8)))
}
}
fn children_range(below: usize, count: usize, within: usize) -> std::ops::Range<usize> {
let fan_out = below.div_ceil(count);
let from = within * fan_out;
from..(from + fan_out).min(below)
}
fn exhausted(layout: &BtrfsLayout, allocation: &Allocation, kind: BlockGroupFlags) -> FormatError {
let system = kind.contains(BlockGroupFlags::SYSTEM);
FormatError::Reservation(ReservationExceeded {
pool: if system { Pool::System } else { Pool::Metadata },
reserved: if system {
layout.reservation.system_blocks
} else {
layout.reservation.metadata_blocks
},
used: allocation.blocks_of(layout, kind) + 1,
})
}
struct Filesystem {
trees: Vec<BuiltTree>,
allocation: Allocation,
}
impl Filesystem {
fn tree(&self, objectid: u64) -> &BuiltTree {
self.trees
.iter()
.find(|tree| tree.objectid == objectid)
.expect("every tree the order names was placed")
}
fn all_extents(&self) -> Vec<(u64, u8, u64)> {
let mut out: Vec<(u64, u8, u64)> = self
.trees
.iter()
.flat_map(|tree| {
tree.extents()
.map(|(address, level)| (address, level, tree.objectid))
})
.collect();
out.sort_unstable();
out
}
}
fn tree_order(compat_ro: CompatRoFlags, model: &BtrfsModel) -> Vec<u64> {
let mut order = Vec::new();
if compat_ro.contains(CompatRoFlags::BLOCK_GROUP_TREE) {
order.push(objectid::BLOCK_GROUP_TREE);
}
order.push(objectid::DEV_TREE);
order.extend(model.subvolumes.iter().map(|subvolume| subvolume.id));
order.push(objectid::UUID_TREE);
order.push(objectid::CSUM_TREE);
order.push(objectid::DATA_RELOC_TREE);
if compat_ro.contains(CompatRoFlags::FREE_SPACE_TREE) {
order.push(objectid::FREE_SPACE_TREE);
}
order.push(objectid::EXTENT_TREE);
order.push(objectid::ROOT_TREE);
order
}
fn root_item_trees(compat_ro: CompatRoFlags, model: &BtrfsModel) -> Vec<u64> {
let mut trees = vec![objectid::EXTENT_TREE, objectid::DEV_TREE];
trees.extend(model.subvolumes.iter().map(|subvolume| subvolume.id));
trees.push(objectid::CSUM_TREE);
trees.push(objectid::UUID_TREE);
if compat_ro.contains(CompatRoFlags::FREE_SPACE_TREE) {
trees.push(objectid::FREE_SPACE_TREE);
}
if compat_ro.contains(CompatRoFlags::BLOCK_GROUP_TREE) {
trees.push(objectid::BLOCK_GROUP_TREE);
}
trees.push(objectid::DATA_RELOC_TREE);
trees
}
struct Round {
filesystem: Filesystem,
reserved: Vec<u64>,
records: Vec<Record>,
shape: Shape,
}
struct Placed {
allocation: Allocation,
data: DataPlan,
subvolume_records: Vec<Vec<Record>>,
}
fn assemble(
model: &BtrfsModel,
layout: &BtrfsLayout,
options: &FormatOptions,
volume_bytes: u64,
) -> Result<(Filesystem, DataPlan), FormatError> {
let mut allocation = Allocation::new(layout);
let data = plan_data(model, layout, &mut allocation)?;
let mut subvolume_records = Vec::with_capacity(model.subvolumes.len());
for (index, subvolume) in model.subvolumes.iter().enumerate() {
subvolume_records.push(fs_tree_records(
subvolume,
&data.per_object[index],
model,
layout,
)?);
}
let placed = Placed {
allocation,
data,
subvolume_records,
};
let mut extent_blocks = 1u64;
for _ in 0..LAYOUT_ROUNDS {
let round = lay_out(model, &placed, layout, options, volume_bytes, extent_blocks)?;
let needed = round.shape.blocks();
if needed == extent_blocks {
let filesystem = settle(round, model, &placed, layout, options)?;
return Ok((filesystem, placed.data));
}
extent_blocks = needed;
}
Err(FormatError::LayoutUnsettled)
}
fn lay_out(
model: &BtrfsModel,
placed: &Placed,
layout: &BtrfsLayout,
options: &FormatOptions,
volume_bytes: u64,
extent_blocks: u64,
) -> Result<Round, FormatError> {
let compat_ro = layout.compat_ro_flags;
let mut allocation = placed.allocation.clone();
let mut trees = Vec::new();
trees.push(BuiltTree::place(
objectid::CHUNK_TREE,
chunk_tree_records(layout, options, volume_bytes),
layout,
&mut allocation,
BlockGroupFlags::SYSTEM,
)?);
let mut reserved = Vec::new();
for objectid in tree_order(compat_ro, model) {
if objectid == objectid::EXTENT_TREE {
reserved = allocation
.take(layout, BlockGroupFlags::METADATA, extent_blocks)
.ok_or_else(|| exhausted(layout, &allocation, BlockGroupFlags::METADATA))?;
continue;
}
let records = match model
.subvolumes
.iter()
.position(|subvolume| subvolume.id == objectid)
{
Some(index) => placed.subvolume_records[index].clone(),
None => match objectid {
objectid::DEV_TREE => dev_tree_records(layout, options),
objectid::DATA_RELOC_TREE => relocation_tree_records(options, layout.node_size),
objectid::UUID_TREE => uuid_tree_records(model),
objectid::CSUM_TREE => csum_records(&placed.data, layout.sector_size),
objectid::BLOCK_GROUP_TREE => block_group_records(layout, &allocation),
objectid::FREE_SPACE_TREE => {
free_space_tree_settled(layout, &allocation, extent_blocks, model, options)?
}
_ => root_tree_records(
&|_| TreePlacement::UNPLACED,
model,
layout,
options,
compat_ro,
),
},
};
trees.push(BuiltTree::place(
objectid,
records,
layout,
&mut allocation,
BlockGroupFlags::METADATA,
)?);
}
let filesystem = Filesystem { trees, allocation };
let mut extents = filesystem.all_extents();
extents.extend(
reserved
.iter()
.map(|&address| (address, 0, objectid::EXTENT_TREE)),
);
extents.sort_unstable();
let records = extent_tree_records(
&extents,
&placed.data,
layout,
&filesystem.allocation,
compat_ro,
);
Ok(Round {
shape: shape(&records, layout.node_size)?,
filesystem,
reserved,
records,
})
}
fn settle(
round: Round,
model: &BtrfsModel,
placed: &Placed,
layout: &BtrfsLayout,
options: &FormatOptions,
) -> Result<Filesystem, FormatError> {
let Round {
mut filesystem,
reserved,
records,
shape: divided,
} = round;
filesystem.trees.push(BuiltTree::from_addresses(
objectid::EXTENT_TREE,
records,
divided,
reserved,
));
let extents = filesystem.all_extents();
let records = extent_tree_records(
&extents,
&placed.data,
layout,
&filesystem.allocation,
layout.compat_ro_flags,
);
let at = filesystem.trees.len() - 1;
assert_eq!(
shape(&records, layout.node_size)?,
filesystem.trees[at].shape,
"the extent tree changed shape once its own blocks had levels, and its blocks were \
addressed against the shape it had"
);
filesystem.trees[at].records = records;
refill(&mut filesystem, model, layout, options)?;
Ok(filesystem)
}
fn refill(
filesystem: &mut Filesystem,
model: &BtrfsModel,
layout: &BtrfsLayout,
options: &FormatOptions,
) -> Result<(), FormatError> {
let compat_ro = layout.compat_ro_flags;
let allocation = filesystem.allocation.clone();
for objectid in [
objectid::BLOCK_GROUP_TREE,
objectid::FREE_SPACE_TREE,
objectid::ROOT_TREE,
] {
let Some(at) = filesystem
.trees
.iter()
.position(|tree| tree.objectid == objectid)
else {
continue;
};
let records = match objectid {
objectid::BLOCK_GROUP_TREE => block_group_records(layout, &allocation),
objectid::FREE_SPACE_TREE => free_space_tree_records(layout, &allocation),
_ => root_tree_records(
&|id| {
let tree = filesystem.tree(id);
TreePlacement {
root: tree.root(),
bytes_used: tree.blocks() * u64::from(layout.node_size),
level: tree.shape.level(),
}
},
model,
layout,
options,
compat_ro,
),
};
let reshaped = shape(&records, layout.node_size)?;
assert_eq!(
reshaped, filesystem.trees[at].shape,
"tree {objectid} changed shape once its records held real values, and its blocks \
were addressed against the shape it had"
);
filesystem.trees[at].records = records;
}
Ok(())
}
fn chunk_tree_records(
layout: &BtrfsLayout,
options: &FormatOptions,
volume_bytes: u64,
) -> Vec<Record> {
let mut records = vec![Record {
key: DiskKey::new(objectid::DEV_ITEMS, ItemType::DEV_ITEM, DEVICE_ID),
data: encode(DevItem::SIZE, |buf| {
device_item(layout, options, volume_bytes).write_to(buf);
}),
}];
for chunk in &layout.chunks {
records.push(Record {
key: DiskKey::new(
objectid::FIRST_CHUNK_TREE,
ItemType::CHUNK_ITEM,
chunk.logical,
),
data: chunk_record(layout, options, chunk),
});
}
records
}
fn device_item(layout: &BtrfsLayout, options: &FormatOptions, volume_bytes: u64) -> DevItem {
DevItem {
devid: DEVICE_ID,
total_bytes: volume_bytes,
bytes_used: layout.device_bytes_used(),
io_align: layout.sector_size,
io_width: layout.sector_size,
sector_size: layout.sector_size,
ty: 0,
generation: 0,
start_offset: 0,
dev_group: 0,
seek_speed: 0,
bandwidth: 0,
uuid: options.device_uuid,
fsid: options.metadata_id(),
}
}
fn chunk_record(layout: &BtrfsLayout, options: &FormatOptions, chunk: &MappedChunk) -> Vec<u8> {
let bootstrap = chunk.logical == RESERVED_HEAD && chunk.flags.contains(BlockGroupFlags::SYSTEM);
let record = Chunk {
length: chunk.length,
owner: objectid::EXTENT_TREE,
stripe_len: STRIPE_LEN,
ty: chunk.flags,
io_align: if bootstrap {
layout.sector_size
} else {
STRIPE_LEN as u32
},
io_width: if bootstrap {
layout.sector_size
} else {
STRIPE_LEN as u32
},
sector_size: layout.sector_size,
num_stripes: chunk.copies.len() as u16,
sub_stripes: u16::from(!bootstrap),
};
encode(record.encoded_len(), |buf| {
record.write_to(buf);
for (index, &offset) in chunk.copies.iter().enumerate() {
Stripe {
devid: DEVICE_ID,
offset,
dev_uuid: options.device_uuid,
}
.write_to(&mut buf[Chunk::SIZE + index * Stripe::SIZE..]);
}
})
}
fn dev_tree_records(layout: &BtrfsLayout, options: &FormatOptions) -> Vec<Record> {
let mut records = vec![Record {
key: DiskKey::new(DevStats::DEV_STATS, ItemType::PERSISTENT_ITEM, DEVICE_ID),
data: encode(DevStats::SIZE, |buf| DevStats::default().write_to(buf)),
}];
for chunk in &layout.chunks {
for &offset in &chunk.copies {
records.push(Record {
key: DiskKey::new(DEVICE_ID, ItemType::DEV_EXTENT, offset),
data: encode(DevExtent::SIZE, |buf| {
DevExtent {
chunk_tree: objectid::CHUNK_TREE,
chunk_objectid: objectid::FIRST_CHUNK_TREE,
chunk_offset: chunk.logical,
length: chunk.length,
chunk_tree_uuid: options.chunk_tree_uuid,
}
.write_to(buf);
}),
});
}
}
sorted(records)
}
fn relocation_tree_records(options: &FormatOptions, node_size: u32) -> Vec<Record> {
let root = objectid::FIRST_FREE;
sorted(vec![
Record {
key: DiskKey::new(root, ItemType::INODE_ITEM, 0),
data: encode(InodeItem::SIZE, |buf| {
InodeItem {
generation: GENERATION,
transid: 0,
size: 0,
nbytes: u64::from(node_size),
block_group: 0,
nlink: 1,
uid: 0,
gid: 0,
mode: DIRECTORY_MODE,
rdev: 0,
flags: InodeFlags::NONE,
sequence: 0,
atime: options.time,
ctime: options.time,
mtime: options.time,
otime: options.time,
}
.write_to(buf);
}),
},
parent_name_record(root),
])
}
fn parent_name_record(root: u64) -> Record {
named_record(
DiskKey::new(root, ItemType::INODE_REF, root),
InodeRef {
index: 0,
name_len: PARENT_NAME.len() as u16,
},
PARENT_NAME,
)
}
fn named_record(key: DiskKey, head: InodeRef, name: &[u8]) -> Record {
let mut data = encode(InodeRef::SIZE, |buf| head.write_to(buf));
data.extend_from_slice(name);
Record { key, data }
}
fn fs_tree_records(
subvolume: &ModelSubvolume,
data: &[Vec<DataExtent>],
model: &BtrfsModel,
layout: &BtrfsLayout,
) -> Result<Vec<Record>, FormatError> {
let mut records = vec![parent_name_record(objectid::FIRST_FREE)];
for (index, object) in subvolume.objects.iter().enumerate() {
let extents = &data[index];
records.push(inode_record(object, extents, index == 0, layout.node_size));
records.extend(name_records(object, layout.node_size));
records.extend(xattr_records(object));
if let ObjectKind::Directory(entries) = &object.kind {
records.extend(directory_records(object.inode, entries));
}
records.extend(extent_records(object, extents, model)?);
}
packed(records, layout.node_size)
}
fn inode_record(
object: &ModelObject,
extents: &[DataExtent],
is_subvolume_root: bool,
node_size: u32,
) -> Record {
let nbytes = match &object.kind {
ObjectKind::Directory(_) if is_subvolume_root => u64::from(node_size),
ObjectKind::Directory(_) => 0,
ObjectKind::File { inline: true, .. } | ObjectKind::Symlink(_) => object.size(),
ObjectKind::File { .. } => extents.iter().map(|extent| extent.length).sum(),
_ => 0,
};
let rdev = match object.kind {
ObjectKind::Device { major, minor, .. } => InodeItem::encode_device(major, minor),
_ => 0,
};
let nlink = match &object.kind {
ObjectKind::Directory(_) => 1,
_ => object.names.len() as u32,
};
Record {
key: DiskKey::new(object.inode, ItemType::INODE_ITEM, 0),
data: encode(InodeItem::SIZE, |buf| {
InodeItem {
generation: GENERATION,
transid: 0,
size: object.size(),
nbytes,
block_group: 0,
nlink,
uid: object.meta.uid,
gid: object.meta.gid,
mode: object.kind.mode_bits() | u32::from(object.meta.mode),
rdev,
flags: InodeFlags::NONE,
sequence: 0,
atime: object.meta.atime,
ctime: object.meta.ctime,
mtime: object.meta.mtime,
otime: object.meta.btime.unwrap_or(object.meta.mtime),
}
.write_to(buf);
}),
}
}
fn name_records(object: &ModelObject, node_size: u32) -> Vec<Record> {
let capacity = node_size as usize - Header::SIZE - Item::SIZE;
let mut records = Vec::new();
let mut parents: Vec<u64> = Vec::new();
for name in &object.names {
if !parents.contains(&name.parent) {
parents.push(name.parent);
}
}
for parent in parents {
let mut data: Vec<u8> = Vec::new();
for name in object.names.iter().filter(|name| name.parent == parent) {
let head = InodeRef {
index: name.index,
name_len: name.name.len() as u16,
};
if !data.is_empty() && data.len() + InodeRef::SIZE + name.name.len() > capacity {
let mut extended = encode(InodeExtref::SIZE, |buf| {
InodeExtref {
parent_objectid: parent,
index: name.index,
name_len: head.name_len,
}
.write_to(buf);
});
extended.extend_from_slice(&name.name);
records.push(Record {
key: DiskKey::new(
object.inode,
ItemType::INODE_EXTREF,
extref_hash(parent, &name.name),
),
data: extended,
});
continue;
}
let at = data.len();
data.resize(at + InodeRef::SIZE, 0);
head.write_to(&mut data[at..]);
data.extend_from_slice(&name.name);
}
if !data.is_empty() {
records.push(Record {
key: DiskKey::new(object.inode, ItemType::INODE_REF, parent),
data,
});
}
}
records
}
fn xattr_records(object: &ModelObject) -> Vec<Record> {
object
.xattrs
.iter()
.map(|xattr| Record {
key: DiskKey::new(object.inode, ItemType::XATTR_ITEM, name_hash(&xattr.name)),
data: dir_item_data(
&DirItem {
location: DiskKey::MIN,
transid: 0,
data_len: xattr.value.len() as u16,
name_len: xattr.name.len() as u16,
kind: DirEntryType::Xattr,
},
&xattr.name,
&xattr.value,
),
})
.collect()
}
fn directory_records(inode: u64, entries: &[DirEntry]) -> Vec<Record> {
let mut records = Vec::with_capacity(entries.len() * 2);
for entry in entries {
let (location, kind) = match entry.target {
EntryTarget::Inode { inode, kind } => {
(DiskKey::new(inode, ItemType::INODE_ITEM, 0), kind)
}
EntryTarget::Subvolume { id } => {
(DiskKey::new(id, ItemType::ROOT_ITEM, 0), DirEntryType::Dir)
}
};
let head = DirItem {
location,
transid: GENERATION,
data_len: 0,
name_len: entry.name.len() as u16,
kind,
};
let data = dir_item_data(&head, &entry.name, &[]);
records.push(Record {
key: DiskKey::new(inode, ItemType::DIR_ITEM, name_hash(&entry.name)),
data: data.clone(),
});
records.push(Record {
key: DiskKey::new(inode, ItemType::DIR_INDEX, entry.index),
data,
});
}
records
}
fn dir_item_data(head: &DirItem, name: &[u8], value: &[u8]) -> Vec<u8> {
let mut data = encode(DirItem::SIZE, |buf| head.write_to(buf));
data.extend_from_slice(name);
data.extend_from_slice(value);
data
}
fn extent_records(
object: &ModelObject,
extents: &[DataExtent],
model: &BtrfsModel,
) -> Result<Vec<Record>, FormatError> {
let inline = |bytes: &[u8]| Record {
key: DiskKey::new(object.inode, ItemType::EXTENT_DATA, 0),
data: {
let mut data = encode(FileExtentItem::INLINE_DATA_START, |buf| {
FileExtentItem {
generation: GENERATION,
ram_bytes: bytes.len() as u64,
compression: super::ondisk::Compression::None,
encryption: 0,
other_encoding: 0,
kind: ExtentKind::Inline,
disk_bytenr: 0,
disk_num_bytes: 0,
offset: 0,
num_bytes: 0,
}
.write_to(buf);
});
data.extend_from_slice(bytes);
data
},
};
Ok(match &object.kind {
ObjectKind::Symlink(target) => vec![inline(target)],
ObjectKind::File { size: 0, .. } => Vec::new(),
ObjectKind::File {
content,
inline: true,
..
} => vec![inline(&model.contents[*content].read()?)],
ObjectKind::File { .. } => extents
.iter()
.map(|extent| Record {
key: DiskKey::new(object.inode, ItemType::EXTENT_DATA, extent.offset),
data: encode(FileExtentItem::SIZE, |buf| {
FileExtentItem {
generation: GENERATION,
ram_bytes: extent.length,
compression: super::ondisk::Compression::None,
encryption: 0,
other_encoding: 0,
kind: ExtentKind::Regular,
disk_bytenr: extent.logical,
disk_num_bytes: extent.length,
offset: 0,
num_bytes: extent.length,
}
.write_to(buf);
}),
})
.collect(),
_ => Vec::new(),
})
}
fn packed(records: Vec<Record>, node_size: u32) -> Result<Vec<Record>, FormatError> {
let capacity = record_capacity(node_size);
let mut out: Vec<Record> = Vec::with_capacity(records.len());
for record in sorted(records) {
match out.last_mut() {
Some(last) if last.key == record.key => {
last.data.extend_from_slice(&record.data);
if last.data.len() > capacity {
return Err(FormatError::RecordTooLarge {
bytes: last.data.len(),
capacity,
});
}
}
_ => out.push(record),
}
}
Ok(out)
}
fn uuid_tree_records(model: &BtrfsModel) -> Vec<Record> {
sorted(
model
.subvolumes
.iter()
.filter(|subvolume| subvolume.uuid != [0; 16])
.map(|subvolume| {
let (objectid_half, offset_half) = uuid_key(subvolume.uuid);
Record {
key: DiskKey::new(objectid_half, ItemType::UUID_SUBVOL, offset_half),
data: subvolume.id.to_le_bytes().to_vec(),
}
})
.collect(),
)
}
fn block_group_records(layout: &BtrfsLayout, allocation: &Allocation) -> Vec<Record> {
layout
.chunks
.iter()
.enumerate()
.map(|(index, chunk)| Record {
key: DiskKey::new(chunk.logical, ItemType::BLOCK_GROUP_ITEM, chunk.length),
data: encode(BlockGroupItem::SIZE, |buf| {
BlockGroupItem {
used: allocation.used[index],
chunk_objectid: objectid::FIRST_CHUNK_TREE,
flags: chunk.flags,
}
.write_to(buf);
}),
})
.collect()
}
fn free_space_tree_records(layout: &BtrfsLayout, allocation: &Allocation) -> Vec<Record> {
let mut records = Vec::new();
for (index, chunk) in layout.chunks.iter().enumerate() {
let runs = allocation.free_runs(index, chunk.length);
records.push(Record {
key: DiskKey::new(chunk.logical, ItemType::FREE_SPACE_INFO, chunk.length),
data: encode(FreeSpaceInfo::SIZE, |buf| {
FreeSpaceInfo {
extent_count: runs.len() as u32,
flags: 0,
}
.write_to(buf);
}),
});
for (start, len) in runs {
records.push(Record {
key: DiskKey::new(chunk.logical + start, ItemType::FREE_SPACE_EXTENT, len),
data: Vec::new(),
});
}
}
sorted(records)
}
fn free_space_tree_settled(
layout: &BtrfsLayout,
allocation: &Allocation,
extent_blocks: u64,
model: &BtrfsModel,
options: &FormatOptions,
) -> Result<Vec<Record>, FormatError> {
let compat_ro = layout.compat_ro_flags;
let root_records = root_tree_records(
&|_| TreePlacement::UNPLACED,
model,
layout,
options,
compat_ro,
);
let root_blocks = shape(&root_records, layout.node_size)?.blocks();
let mut own_blocks = 1u64;
for _ in 0..LAYOUT_ROUNDS {
let mut settled = allocation.clone();
settled
.take(
layout,
BlockGroupFlags::METADATA,
own_blocks + extent_blocks + root_blocks,
)
.ok_or_else(|| exhausted(layout, allocation, BlockGroupFlags::METADATA))?;
let records = free_space_tree_records(layout, &settled);
let needed = shape(&records, layout.node_size)?.blocks();
if needed == own_blocks {
return Ok(records);
}
own_blocks = needed;
}
Err(FormatError::LayoutUnsettled)
}
fn extent_tree_records(
extents: &[(u64, u8, u64)],
data: &DataPlan,
layout: &BtrfsLayout,
allocation: &Allocation,
compat_ro: CompatRoFlags,
) -> Vec<Record> {
let mut records: Vec<Record> = extents
.iter()
.map(|&(address, level, owner)| Record {
key: DiskKey::new(address, ItemType::METADATA_ITEM, u64::from(level)),
data: encode(ExtentItem::SIZE + InlineRef::SIZE, |buf| {
ExtentItem {
refs: 1,
generation: GENERATION,
flags: ExtentFlags::TREE_BLOCK,
}
.write_to(buf);
InlineRef {
kind: ItemType::TREE_BLOCK_REF,
offset: owner,
}
.write_to(&mut buf[ExtentItem::SIZE..]);
}),
})
.collect();
records.extend(data.ordered().map(|extent| Record {
key: DiskKey::new(extent.logical, ItemType::EXTENT_ITEM, extent.length),
data: encode(ExtentItem::SIZE + 1 + ExtentDataRef::SIZE, |buf| {
ExtentItem {
refs: 1,
generation: GENERATION,
flags: ExtentFlags::DATA,
}
.write_to(buf);
buf[ExtentItem::SIZE] = ItemType::EXTENT_DATA_REF.value();
ExtentDataRef {
root: extent.root,
objectid: extent.inode,
offset: extent.offset,
count: 1,
}
.write_to(&mut buf[ExtentItem::SIZE + 1..]);
}),
}));
if !compat_ro.contains(CompatRoFlags::BLOCK_GROUP_TREE) {
records.extend(block_group_records(layout, allocation));
}
sorted(records)
}
#[derive(Clone, Copy)]
struct TreePlacement {
root: u64,
bytes_used: u64,
level: u8,
}
impl TreePlacement {
const UNPLACED: Self = Self {
root: 0,
bytes_used: 0,
level: 0,
};
}
fn root_tree_records(
placement: &dyn Fn(u64) -> TreePlacement,
model: &BtrfsModel,
layout: &BtrfsLayout,
options: &FormatOptions,
compat_ro: CompatRoFlags,
) -> Vec<Record> {
let node_size = u64::from(layout.node_size);
let mut records: Vec<Record> = root_item_trees(compat_ro, model)
.into_iter()
.map(|id| {
let placed = placement(id);
let subvolume = model.subvolumes.iter().find(|sub| sub.id == id);
let has_directory = subvolume.is_some() || id == objectid::DATA_RELOC_TREE;
let zero = Timestamp::from_secs(0);
Record {
key: DiskKey::new(id, ItemType::ROOT_ITEM, 0),
data: encode(RootItem::SIZE, |buf| {
RootItem {
generation: GENERATION,
root_dirid: if has_directory {
objectid::FIRST_FREE
} else {
0
},
bytenr: placed.root,
byte_limit: 0,
bytes_used: placed.bytes_used,
last_snapshot: 0,
flags: match subvolume {
Some(sub) if sub.read_only => RootFlags::SUBVOL_RDONLY,
_ => RootFlags::NONE,
},
refs: 1,
drop_progress: DiskKey::MIN,
drop_level: 0,
level: placed.level,
generation_v2: GENERATION,
uuid: subvolume.map_or([0; 16], |sub| sub.uuid),
parent_uuid: [0; 16],
received_uuid: [0; 16],
ctransid: 0,
otransid: 0,
stransid: 0,
rtransid: 0,
ctime: if subvolume.is_some() {
options.time
} else {
zero
},
otime: if subvolume.is_some() {
options.time
} else {
zero
},
stime: zero,
rtime: zero,
}
.write_to(buf);
}),
}
})
.collect();
for subvolume in &model.subvolumes {
let Some(link) = &subvolume.link else {
continue;
};
let head = RootRef {
dirid: link.dir,
sequence: link.index,
name_len: link.name.len() as u16,
};
for (objectid, kind, offset) in [
(link.parent, ItemType::ROOT_REF, subvolume.id),
(subvolume.id, ItemType::ROOT_BACKREF, link.parent),
] {
let mut data = encode(RootRef::SIZE, |buf| head.write_to(buf));
data.extend_from_slice(&link.name);
records.push(Record {
key: DiskKey::new(objectid, kind, offset),
data,
});
}
}
records.push(named_record(
DiskKey::new(
objectid::FS_TREE,
ItemType::INODE_REF,
objectid::ROOT_TREE_DIR,
),
InodeRef {
index: 0,
name_len: SUBVOLUME_NAME.len() as u16,
},
SUBVOLUME_NAME,
));
records.push(Record {
key: DiskKey::new(objectid::ROOT_TREE_DIR, ItemType::INODE_ITEM, 0),
data: encode(InodeItem::SIZE, |buf| {
InodeItem {
generation: GENERATION,
transid: 0,
size: 0,
nbytes: node_size,
block_group: 0,
nlink: 1,
uid: 0,
gid: 0,
mode: DIRECTORY_MODE,
rdev: 0,
flags: InodeFlags::NONE,
sequence: 0,
atime: options.time,
ctime: options.time,
mtime: options.time,
otime: options.time,
}
.write_to(buf);
}),
});
records.push(named_record(
DiskKey::new(
objectid::ROOT_TREE_DIR,
ItemType::INODE_REF,
objectid::ROOT_TREE_DIR,
),
InodeRef {
index: 0,
name_len: PARENT_NAME.len() as u16,
},
PARENT_NAME,
));
records.push(Record {
key: DiskKey::new(
objectid::ROOT_TREE_DIR,
ItemType::DIR_ITEM,
name_hash(SUBVOLUME_NAME),
),
data: {
let entry = DirItem {
location: DiskKey::new(
model.default_subvolume,
ItemType::ROOT_ITEM,
if model.default_subvolume == objectid::FS_TREE {
u64::MAX
} else {
0
},
),
transid: GENERATION,
data_len: 0,
name_len: SUBVOLUME_NAME.len() as u16,
kind: DirEntryType::Dir,
};
let mut data = encode(DirItem::SIZE, |buf| entry.write_to(buf));
data.extend_from_slice(SUBVOLUME_NAME);
data
},
});
sorted(records)
}
fn write_filesystem<W: Write + Seek>(
sink: W,
prepared: &Prepared,
options: &FormatOptions,
volume_bytes: u64,
) -> Result<Slack, FormatError> {
let Prepared { model, layout } = prepared;
let (mut filesystem, data) = assemble(model, layout, options, layout.volume_bytes)?;
let mut sink = ByteSink::new(sink);
let metadata_id = options.metadata_id();
let csum_at = filesystem
.trees
.iter()
.position(|tree| tree.objectid == objectid::CSUM_TREE)
.expect("every filesystem has a checksum tree");
let mut csum_records = std::mem::take(&mut filesystem.trees[csum_at].records);
let mut fill = CsumFill::new(&mut csum_records);
write_data(&mut sink, model, layout, &data, &mut fill)?;
fill.finish();
filesystem.trees[csum_at].records = csum_records;
let mut block = vec![0u8; layout.node_size as usize];
for tree in &filesystem.trees {
let mut below: Vec<DiskKey> = Vec::new();
for (level, addresses) in tree.levels.iter().enumerate() {
let mut keys = Vec::with_capacity(addresses.len());
for (within, &address) in addresses.iter().enumerate() {
block.fill(0);
let header = Header {
csum: [0; CSUM_FIELD_LEN],
fsid: metadata_id,
bytenr: address,
flags: HEADER_FLAG_WRITTEN
| (u64::from(BACKREF_REV_MIXED) << BACKREF_REV_SHIFT),
chunk_tree_uuid: options.chunk_tree_uuid,
generation: GENERATION,
owner: tree.objectid,
nritems: 0,
level: level as u8,
};
keys.push(if level == 0 {
let from: usize = tree.shape.leaves[..within].iter().sum();
let records = &tree.records[from..from + tree.shape.leaves[within]];
write_leaf(&mut block, &header, records)
} else {
let range = children_range(below.len(), addresses.len(), within);
let children: Vec<(DiskKey, u64)> = range
.clone()
.map(|at| (below[at], tree.levels[level - 1][at]))
.collect();
write_node(&mut block, &header, &children)
});
for offset in copies_of(layout, address) {
sink.write_at(offset, &block)?;
}
}
below = keys;
}
}
let used_metadata = filesystem
.allocation
.blocks_of(layout, BlockGroupFlags::METADATA);
let used_system = filesystem
.allocation
.blocks_of(layout, BlockGroupFlags::SYSTEM);
let slack = layout.reservation.account(used_metadata, used_system)?;
let superblock = superblock(
&filesystem,
model,
layout,
options,
layout.volume_bytes,
slack,
);
let backup = backup_of(&filesystem, &superblock);
let mut bytes = vec![0u8; SUPER_INFO_SIZE];
for &at in &layout.superblock_mirrors {
bytes.fill(0);
let mut copy = superblock.clone();
copy.bytenr = at;
copy.write_to(&mut bytes);
backup.write_to(&mut bytes[RootBackup::offset_of(0).expect("the first of the ring")..]);
seal(&mut bytes);
sink.write_at(at, &bytes)?;
}
sink.extend_to(volume_bytes)?;
Ok(slack)
}
fn copies_of(layout: &BtrfsLayout, logical: u64) -> impl Iterator<Item = u64> + '_ {
let at = layout
.chunks
.partition_point(|chunk| chunk.logical_end() <= logical);
layout
.chunks
.get(at)
.filter(|chunk| (chunk.logical..chunk.logical_end()).contains(&logical))
.into_iter()
.flat_map(move |chunk| {
let within = logical - chunk.logical;
chunk.copies.iter().map(move |copy| copy + within)
})
}
fn write_leaf(block: &mut [u8], header: &Header, records: &[Record]) -> DiskKey {
let mut head = *header;
head.nritems = records.len() as u32;
head.write_to(block);
let mut data_end = block.len();
for (index, record) in records.iter().enumerate() {
data_end -= record.data.len();
block[data_end..data_end + record.data.len()].copy_from_slice(&record.data);
Item {
key: record.key,
offset: (data_end - Header::SIZE) as u32,
size: record.data.len() as u32,
}
.write_to(&mut block[Header::SIZE + index * Item::SIZE..]);
}
assert!(
Header::SIZE + records.len() * Item::SIZE <= data_end,
"a leaf's item array and its data met, which the shaping exists to prevent"
);
seal(block);
records.first().map_or(DiskKey::MIN, |record| record.key)
}
fn write_node(block: &mut [u8], header: &Header, children: &[(DiskKey, u64)]) -> DiskKey {
assert!(
Header::SIZE + children.len() * KeyPtr::SIZE <= block.len(),
"an internal node was given more children than a block holds, which the fan-out the shaping divided by exists to prevent"
);
let mut head = *header;
head.nritems = children.len() as u32;
head.write_to(block);
for (index, &(key, blockptr)) in children.iter().enumerate() {
KeyPtr {
key,
blockptr,
generation: GENERATION,
}
.write_to(&mut block[Header::SIZE + index * KeyPtr::SIZE..]);
}
seal(block);
children.first().map_or(DiskKey::MIN, |&(key, _)| key)
}
fn superblock(
filesystem: &Filesystem,
model: &BtrfsModel,
layout: &BtrfsLayout,
options: &FormatOptions,
volume_bytes: u64,
slack: Slack,
) -> SuperBlock {
let root = filesystem.tree(objectid::ROOT_TREE);
let chunk = filesystem.tree(objectid::CHUNK_TREE);
let spent = layout.reservation.metadata_blocks + layout.reservation.system_blocks
- slack.metadata_blocks
- slack.system_blocks;
let data_bytes = filesystem
.allocation
.bytes_of(layout, BlockGroupFlags::DATA);
let mut array = [0u8; SYS_CHUNK_ARRAY_SIZE];
let mut array_len = 0usize;
for mapped in layout.chunks_of(BlockGroupFlags::SYSTEM) {
let record = chunk_record(layout, options, mapped);
DiskKey::new(
objectid::FIRST_CHUNK_TREE,
ItemType::CHUNK_ITEM,
mapped.logical,
)
.write_to(&mut array[array_len..]);
array_len += DiskKey::SIZE;
array[array_len..array_len + record.len()].copy_from_slice(&record);
array_len += record.len();
}
let mut incompat = layout.incompat_flags;
if options.distinct_metadata_uuid().is_some() {
incompat |= IncompatFlags::METADATA_UUID;
}
if model.default_subvolume != objectid::FS_TREE {
incompat |= IncompatFlags::DEFAULT_SUBVOL;
}
SuperBlock {
csum: [0; CSUM_FIELD_LEN],
fsid: options.fsid,
bytenr: MIRRORS[0],
flags: SuperFlags::from_bits(HEADER_FLAG_WRITTEN),
magic: MAGIC,
generation: GENERATION,
root: root.root(),
chunk_root: chunk.root(),
log_root: 0,
total_bytes: volume_bytes,
bytes_used: spent * u64::from(layout.node_size) + data_bytes,
root_dir_objectid: objectid::ROOT_TREE_DIR,
num_devices: 1,
sectorsize: layout.sector_size,
nodesize: layout.node_size,
stripesize: layout.sector_size,
sys_chunk_array_size: array_len as u32,
chunk_root_generation: GENERATION,
compat_flags: CompatFlags::NONE,
compat_ro_flags: layout.compat_ro_flags,
incompat_flags: incompat,
csum_type: ChecksumType::CRC32C,
root_level: root.shape.level(),
chunk_root_level: chunk.shape.level(),
log_root_level: 0,
dev_item: device_item(layout, options, volume_bytes),
label: options.label.field(),
cache_generation: if layout
.compat_ro_flags
.contains(CompatRoFlags::FREE_SPACE_TREE)
{
0
} else {
NO_FREE_SPACE_CACHE
},
uuid_tree_generation: 0,
metadata_uuid: options.distinct_metadata_uuid().unwrap_or([0; 16]),
nr_global_roots: 0,
remap_root: 0,
remap_root_generation: 0,
remap_root_level: 0,
sys_chunk_array: array,
}
}
fn backup_of(filesystem: &Filesystem, sb: &SuperBlock) -> RootBackup {
let root_of = |id: u64| filesystem.tree(id).root();
let level_of = |id: u64| filesystem.tree(id).shape.level();
RootBackup {
tree_root: sb.root,
tree_root_gen: GENERATION,
chunk_root: sb.chunk_root,
chunk_root_gen: GENERATION,
extent_root: root_of(objectid::EXTENT_TREE),
extent_root_gen: GENERATION,
fs_root: root_of(objectid::FS_TREE),
fs_root_gen: GENERATION,
dev_root: root_of(objectid::DEV_TREE),
dev_root_gen: GENERATION,
csum_root: root_of(objectid::CSUM_TREE),
csum_root_gen: GENERATION,
total_bytes: sb.total_bytes,
bytes_used: sb.bytes_used,
num_devices: sb.num_devices,
tree_root_level: sb.root_level,
chunk_root_level: sb.chunk_root_level,
extent_root_level: level_of(objectid::EXTENT_TREE),
fs_root_level: level_of(objectid::FS_TREE),
dev_root_level: level_of(objectid::DEV_TREE),
csum_root_level: level_of(objectid::CSUM_TREE),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::btrfs::forge::Sparse;
use crate::btrfs::ondisk::{CompatRoFlags, Header, ItemType, SuperBlock};
use crate::btrfs::{
DEFAULT_COMPAT_RO, DEFAULT_INCOMPAT, Mirror, NodeSize, Profile, Reader, SectorSize, Volume,
};
use crate::source::{Metadata, TreeBuilder};
const GIB: u64 = 1 << 30;
const MIB: u64 = 1 << 20;
const TIME: Timestamp = Timestamp {
secs: 1_786_472_859,
nanos: 0,
};
fn options() -> FormatOptions {
FormatOptions::new([0x11; 16], TIME)
.chunk_tree_uuid([0x22; 16])
.device_uuid([0x33; 16])
.subvolume_uuid([0x44; 16])
}
fn model_of(source: impl crate::Source) -> BtrfsModel {
build_model(source.into_entries(), &[], None, [0; 16], 4096, 16384, TIME)
.expect("a buildable tree")
}
fn image_of(bytes: u64, plan: PlanRequest) -> Image {
format(TreeBuilder::new(), bytes, options().plan(plan)).expect("a volume past the minimum")
}
fn opened(image: &Image) -> Volume<Cursor<&[u8]>> {
Volume::open(Cursor::new(image.as_bytes())).expect("this crate reads what it wrote")
}
#[test]
fn every_tree_the_format_defines_is_written_and_reachable() {
let image = image_of(GIB, PlanRequest::new(0));
let mut volume = opened(&image);
let mut found: Vec<u64> = volume
.tree_roots()
.expect("the root tree")
.iter()
.map(|root| root.objectid)
.collect();
found.sort_unstable();
let mut wanted = vec![objectid::ROOT_TREE, objectid::CHUNK_TREE];
wanted.extend(root_item_trees(
image.layout().compat_ro_flags,
&model_of(TreeBuilder::new()),
));
wanted.sort_unstable();
assert_eq!(found, wanted);
for root in volume.tree_roots().expect("the root tree") {
volume
.tree(root)
.count_items()
.unwrap_or_else(|e| panic!("tree {} does not read back: {e}", root.objectid));
}
}
#[test]
fn the_filesystem_reads_back_as_one_empty_directory_owned_by_root() {
let image = image_of(GIB, PlanRequest::new(0));
let mut reader =
Reader::open(Cursor::new(image.as_bytes())).expect("this crate reads what it wrote");
let root = reader.root().expect("a root directory");
assert_eq!(root.item.mode, DIRECTORY_MODE);
assert_eq!((root.item.uid, root.item.gid), (0, 0));
assert_eq!(root.item.mtime, TIME, "the instant the options named");
assert_eq!(root.item.otime, TIME, "including the birth time");
let walked = reader.walk().expect("a walk of an empty tree");
assert_eq!(walked.len(), 1, "{:?}", walked);
assert!(
walked[0].path.is_empty(),
"the root is the path of no components"
);
assert_eq!(reader.subvolumes().len(), 1);
let subvolume = &reader.subvolumes()[0];
assert_eq!(subvolume.id, objectid::FS_TREE);
assert_eq!(subvolume.uuid, [0x44; 16]);
assert_eq!(subvolume.otime, TIME);
assert!(!subvolume.read_only);
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
#[test]
fn two_formats_of_one_parameter_set_are_the_same_bytes() {
let first = image_of(GIB, PlanRequest::new(0));
let second = image_of(GIB, PlanRequest::new(0));
assert_eq!(first.as_bytes(), second.as_bytes());
let other = format(
TreeBuilder::new(),
GIB,
options().subvolume_uuid([0x45; 16]),
)
.expect("formattable");
assert_ne!(first.as_bytes(), other.as_bytes());
}
#[test]
fn a_name_reaches_every_superblock_copy_and_reads_back_as_the_bytes_it_was_given() {
let label = VolumeLabel::from_bytes("système de fichiers".as_bytes()).expect("a label");
let image = format(TreeBuilder::new(), GIB, options().label(label))
.expect("a volume past the minimum");
let copies = &image.layout().superblock_mirrors;
assert_eq!(copies.len(), 2, "one copy proves nothing here");
for &at in copies {
let at = at as usize;
let sb = SuperBlock::read_from(&image.as_bytes()[at..at + SUPER_INFO_SIZE])
.expect("a superblock at every copy");
assert_eq!(sb.label_bytes(), label.as_bytes());
}
let plain = image_of(GIB, PlanRequest::new(0));
assert_eq!(opened(&plain).superblock().label_bytes(), b"");
}
#[test]
fn a_filesystem_with_two_ids_stamps_its_blocks_and_its_device_with_the_second() {
const VISIBLE: [u8; 16] = [0x11; 16];
const METADATA: [u8; 16] = [0x77; 16];
let image = format(
TreeBuilder::new(),
GIB,
options().metadata_uuid(Some(METADATA)),
)
.expect("a volume past the minimum");
let mut volume = opened(&image);
let sb = volume.superblock();
assert_eq!(sb.fsid, VISIBLE);
assert_eq!(sb.metadata_uuid, METADATA);
assert_eq!(
sb.dev_item.fsid, METADATA,
"the device belongs to the metadata"
);
assert!(sb.incompat_flags.contains(IncompatFlags::METADATA_UUID));
for root in volume.tree_roots().expect("the trees") {
let block = volume.read_block(root.bytenr).expect("a tree block");
assert_eq!(
block.header().fsid,
METADATA,
"tree {} is stamped with the visible id",
root.objectid
);
}
let plain = image_of(GIB, PlanRequest::new(0));
let sb = opened(&plain).superblock().clone();
assert_eq!(sb.dev_item.fsid, VISIBLE);
assert_eq!(sb.metadata_uuid, [0; 16]);
assert!(!sb.incompat_flags.contains(IncompatFlags::METADATA_UUID));
let stated = format(
TreeBuilder::new(),
GIB,
options().metadata_uuid(Some(VISIBLE)),
)
.expect("a volume past the minimum");
let sb = opened(&stated).superblock().clone();
assert_eq!(sb.metadata_uuid, [0; 16]);
assert!(!sb.incompat_flags.contains(IncompatFlags::METADATA_UUID));
assert_eq!(stated.as_bytes(), plain.as_bytes(), "the same filesystem");
}
#[test]
fn a_name_the_field_cannot_hold_is_refused_rather_than_cut_short() {
assert!(VolumeLabel::from_bytes(&[b'a'; VolumeLabel::MAX_BYTES]).is_ok());
assert!(matches!(
VolumeLabel::from_bytes(&[b'a'; VolumeLabel::MAX_BYTES + 1]),
Err(LabelError::TooLong { bytes, limit })
if bytes == VolumeLabel::MAX_BYTES + 1 && limit == VolumeLabel::MAX_BYTES
));
assert!(matches!(
VolumeLabel::from_bytes(b"ro\0ot"),
Err(LabelError::NulByte { at: 2 })
));
}
#[test]
fn a_streamed_image_is_the_collected_one_and_touches_only_what_it_writes() {
for source in [TreeBuilder::new(), populated()] {
let collected =
format(source.clone(), GIB, options()).expect("a volume past the minimum");
let mut streamed = Cursor::new(vec![0u8; GIB as usize]);
let layout = format_to(&mut streamed, source, GIB, options()).expect("formattable");
assert_eq!(&streamed.into_inner()[..], collected.as_bytes());
assert_eq!(&layout, collected.layout());
}
}
#[test]
fn every_block_records_the_address_it_was_written_to_and_the_filesystem_it_belongs_to() {
let image = image_of(GIB, PlanRequest::new(0));
let mut volume = opened(&image);
let roots = volume.tree_roots().expect("the root tree");
let node_size = image.layout().node_size as usize;
for root in roots {
let block = volume.read_block(root.bytenr).expect("a tree block");
let header = Header::read_from(block.bytes()).expect("a header");
assert_eq!(header.bytenr, root.bytenr);
assert_eq!(
header.fsid, [0x11; 16],
"the filesystem id, not the chunk's"
);
assert_eq!(header.chunk_tree_uuid, [0x22; 16]);
assert_eq!(header.generation, GENERATION);
assert_eq!(block.bytes().len(), node_size);
}
}
#[test]
fn an_image_no_allocator_holds_is_refused_rather_than_aborting() {
let err = format(TreeBuilder::new(), 1 << 60, options()).err();
assert!(
matches!(err, Some(FormatError::ImageTooLargeInMemory { bytes }) if bytes == 1 << 60),
"{err:?}"
);
}
#[test]
fn a_size_past_a_whole_sector_records_the_whole_sectors() {
let bytes = (1u64 << 30) + 513;
let mut sink = Sparse::new(bytes);
let layout =
format_to(&mut sink, TreeBuilder::new(), bytes, options()).expect("formattable");
assert_eq!(layout.volume_bytes, 1 << 30);
let sb = SuperBlock::read_from(&sink.read_at(MIRRORS[0], SUPER_INFO_SIZE))
.expect("the superblock");
assert_eq!(sb.total_bytes, 1 << 30);
assert_eq!(sb.dev_item.total_bytes, 1 << 30);
}
#[test]
fn every_superblock_copy_the_device_holds_is_written_and_says_where_it_is() {
let bytes = (256 << 30) + SUPER_INFO_SIZE as u64;
let mut sink = Sparse::new(bytes);
let layout =
format_to(&mut sink, TreeBuilder::new(), bytes, options()).expect("formattable");
assert_eq!(layout.superblock_mirrors, MIRRORS);
for &at in &layout.superblock_mirrors {
let sb = SuperBlock::read_from(&sink.read_at(at, SUPER_INFO_SIZE))
.expect("a superblock at every mirror");
assert_eq!(sb.bytenr, at, "a copy records where it lives");
assert_eq!(sb.generation, GENERATION);
assert_eq!(sb.total_bytes, bytes);
}
let volume = Volume::open(sink).expect("readable");
assert!(
volume.mirrors().iter().all(|mirror| matches!(
mirror,
Mirror::Present {
generation: GENERATION
}
)),
"every copy is a superblock at the one transaction: {:?}",
volume.mirrors()
);
}
#[test]
fn a_replicated_block_group_holds_every_copy_of_every_block_it_covers() {
let image = image_of(GIB, PlanRequest::new(0).metadata_profile(Profile::Dup));
let layout = image.layout();
let node_size = layout.node_size as usize;
let metadata = layout
.chunks_of(crate::btrfs::ondisk::BlockGroupFlags::METADATA)
.next()
.expect("a metadata chunk");
assert_eq!(metadata.copies.len(), 2, "the profile asked for two");
let bytes = image.as_bytes();
let first = metadata.copies[0] as usize;
let second = metadata.copies[1] as usize;
assert_eq!(
&bytes[first..first + node_size],
&bytes[second..second + node_size],
"the two copies of the first metadata block are not the same bytes"
);
}
#[test]
fn the_reservation_covers_what_the_writer_spends_and_the_slack_is_reported() {
for node in [4096u32, 16384, 65536] {
let image = image_of(GIB, PlanRequest::new(0).node_size(NodeSize::Bytes(node)));
let slack = image.slack();
let reservation = image.layout().reservation;
assert!(
slack.metadata_blocks < reservation.metadata_blocks,
"node {node}: a filesystem that spent nothing is not a filesystem"
);
assert_eq!(slack.system_blocks, reservation.system_blocks - 1);
}
}
#[test]
fn the_root_tree_grows_a_level_where_a_node_is_too_small_to_hold_it() {
for (node, level) in [(4096u32, 1u8), (16384, 0), (65536, 0)] {
let image = image_of(GIB, PlanRequest::new(0).node_size(NodeSize::Bytes(node)));
let volume = opened(&image);
assert_eq!(
volume.superblock().root_level,
level,
"the root tree at a {node}-byte node"
);
assert_eq!(volume.superblock().nodesize, node);
}
}
#[test]
fn the_extent_tree_records_every_block_of_every_tree_including_its_own() {
for node in [4096u32, 16384] {
let image = image_of(GIB, PlanRequest::new(0).node_size(NodeSize::Bytes(node)));
let mut volume = opened(&image);
let roots = volume.tree_roots().expect("the root tree");
let extent = roots
.iter()
.find(|root| root.objectid == objectid::EXTENT_TREE)
.copied()
.expect("an extent tree");
let mut recorded = Vec::new();
volume
.tree(extent)
.for_each_item(|key, _| {
if key.kind == ItemType::METADATA_ITEM {
recorded.push((key.objectid, key.offset as u8));
}
true
})
.expect("the extent tree reads back");
recorded.sort_unstable();
let mut allocated = Vec::new();
for root in &roots {
volume
.tree(*root)
.for_each_block(|block| {
let header = Header::read_from(block.bytes()).expect("a header");
allocated.push((header.bytenr, header.level));
true
})
.expect("every tree reads back");
}
allocated.sort_unstable();
allocated.dedup();
assert_eq!(recorded, allocated, "at a {node}-byte node");
}
}
#[test]
fn the_free_space_tree_accounts_for_every_byte_of_every_block_group() {
let image = image_of(GIB, PlanRequest::new(0));
let layout = image.layout();
let mut volume = opened(&image);
let roots = volume.tree_roots().expect("the root tree");
let free_space = roots
.iter()
.find(|root| root.objectid == objectid::FREE_SPACE_TREE)
.copied()
.expect("a free-space tree");
let mut runs: Vec<(u64, u64)> = Vec::new();
let mut infos: Vec<(u64, u64, u32)> = Vec::new();
volume
.tree(free_space)
.for_each_item(|key, data| {
if key.kind == ItemType::FREE_SPACE_EXTENT {
runs.push((key.objectid, key.offset));
} else if key.kind == ItemType::FREE_SPACE_INFO {
let info = FreeSpaceInfo::read_from(data).expect("a free-space record");
infos.push((key.objectid, key.offset, info.extent_count));
}
true
})
.expect("the free-space tree reads back");
assert_eq!(
infos.len(),
layout.chunks.len(),
"one record per block group"
);
for (index, chunk) in layout.chunks.iter().enumerate() {
let (start, length, count) = infos[index];
assert_eq!((start, length), (chunk.logical, chunk.length));
assert_eq!(count, 1, "a block group written once has one free run");
let (run_start, run_length) = runs[index];
assert!(run_start >= chunk.logical && run_start < chunk.logical_end());
assert_eq!(
run_start + run_length,
chunk.logical_end(),
"the free run reaches the end of its block group"
);
}
}
#[test]
fn every_combination_of_the_knobs_produces_a_filesystem_this_crate_reads_back() {
let mut formatted = 0usize;
let mut refused = 0usize;
for volume in [45 * MIB, 229 * MIB, GIB, 17 * GIB, 300 * GIB] {
for sector in [4096u32, 16384, 65536] {
for node in [4096u32, 16384, 65536] {
if node < sector {
continue;
}
for metadata in [Profile::Single, Profile::Dup] {
for data in [Profile::Single, Profile::Dup] {
for compat_ro in [
DEFAULT_COMPAT_RO,
DEFAULT_COMPAT_RO.without(CompatRoFlags::BLOCK_GROUP_TREE),
CompatRoFlags::NONE,
] {
let plan = PlanRequest::new(0)
.sector_size(SectorSize::Bytes(sector))
.node_size(NodeSize::Bytes(node))
.metadata_profile(metadata)
.data_profile(data)
.features(DEFAULT_INCOMPAT, compat_ro);
let what = format!(
"{volume} bytes, {sector}-byte sector, {node}-byte node, {metadata:?}/{data:?}, compat_ro {:#x}",
compat_ro.bits()
);
let mut sink = Sparse::new(volume);
match format_to(
&mut sink,
TreeBuilder::new(),
volume,
options().plan(plan),
) {
Err(FormatError::Geometry(_)) => {
refused += 1;
continue;
}
Err(e) => panic!("{what}: {e}"),
Ok(_) => formatted += 1,
}
let mut volume_read = Volume::open(sink.clone())
.unwrap_or_else(|e| panic!("{what}: {e}"));
let roots = volume_read
.tree_roots()
.unwrap_or_else(|e| panic!("{what}: {e}"));
for root in roots {
volume_read.tree(root).count_items().unwrap_or_else(|e| {
panic!(
"{what}: tree {} does not read back: {e}",
root.objectid
)
});
}
let mut reader =
Reader::open(sink).unwrap_or_else(|e| panic!("{what}: {e}"));
let report = reader.scan();
assert!(report.is_clean(), "{what}: {:?}", report.anomalies());
}
}
}
}
}
}
assert!(
formatted > refused,
"only {formatted} of {} combinations produced a filesystem",
formatted + refused
);
}
#[test]
fn a_format_instant_with_a_fraction_of_a_second_or_more_is_refused() {
for nanos in [999_999_999, 1_000_000_000, 1_500_000_000] {
let mut options = options();
options.time = Timestamp {
secs: 1_700_000_000,
nanos,
};
let mut sink = Cursor::new(Vec::new());
match format_to(&mut sink, TreeBuilder::new(), 256 * MIB, options) {
Err(err @ FormatError::TimeOutOfRange { time }) => {
assert!(nanos >= Timestamp::NANOS_PER_SEC, "{nanos}");
assert_eq!(time.nanos, nanos);
assert_eq!(
err.to_string(),
format!(
"1700000000 seconds and {nanos} nanoseconds since 1970 is not a \
time the filesystem records"
)
);
assert!(sink.into_inner().is_empty());
}
Ok(_) => assert!(nanos < Timestamp::NANOS_PER_SEC, "{nanos}"),
Err(e) => panic!("{nanos}: {e}"),
}
}
}
#[test]
fn a_volume_too_small_for_its_profiles_is_refused_before_anything_is_written() {
let mut sink = Cursor::new(Vec::new());
let err = format_to(&mut sink, TreeBuilder::new(), 8 * MIB, options())
.expect_err("far below the minimum");
assert!(matches!(err, FormatError::Geometry(_)), "{err}");
assert!(
sink.into_inner().is_empty(),
"a destination is not touched by a format that could not have succeeded"
);
}
fn colliding(prefix: &[u8], target: u32) -> Vec<u8> {
let table: Vec<u32> = (0..256u32)
.map(|i| {
(0..8).fold(i, |c, _| {
if c & 1 == 0 {
c >> 1
} else {
(c >> 1) ^ 0x82F6_3B78
}
})
})
.collect();
let top = |byte: u32| (0..256).find(|&i| table[i] >> 24 == byte).expect("unique");
let mut indices = [0usize; 4];
let mut state = target;
for k in (0..4).rev() {
indices[k] = top(state >> 24);
state = ((state ^ table[indices[k]]) << 8) | indices[k] as u32;
}
let mut register = crate::crc32c(!1, prefix);
let mut name = prefix.to_vec();
for &index in &indices {
name.push(((register ^ index as u32) & 0xff) as u8);
register = (register >> 8) ^ table[index];
}
assert_eq!(
name_hash(&name),
u64::from(target),
"the forged name hashes to the target"
);
name
}
#[test]
fn names_sharing_a_hash_past_what_a_leaf_holds_are_refused_when_planned() {
let time = Timestamp::from_secs(1_700_000_000);
let mut source = TreeBuilder::new().directory("/d", Metadata::new(0o755, time));
let mut made = 0;
for i in 0u32.. {
let prefix = format!("/d/{i:0>246}");
let path = colliding(prefix.as_bytes(), 0x1234_5678);
if path[3..].iter().any(|&b| b == b'/' || b == 0) {
continue;
}
source = source.file(path, b"x".to_vec(), Metadata::new(0o644, time));
made += 1;
if made == 60 {
break;
}
}
assert!(matches!(
FormatPlan::new(source, 256 * MIB, options()),
Err(FormatError::RecordTooLarge { .. })
));
}
#[test]
fn a_record_larger_than_a_leaf_is_refused_rather_than_split() {
let node = 4096u32;
let records = vec![Record {
key: DiskKey::MIN,
data: vec![0; node as usize],
}];
assert!(matches!(
shape(&records, node),
Err(FormatError::RecordTooLarge { .. })
));
}
#[test]
fn a_tree_with_nothing_in_it_is_one_empty_leaf_rather_than_no_blocks() {
let empty = shape(&[], 16384).expect("shapeable");
assert_eq!(empty.blocks(), 1);
assert_eq!(empty.level(), 0);
assert_eq!(empty.leaves, vec![0]);
}
#[test]
fn leaves_are_packed_full_rather_than_left_half_empty() {
let node = 4096u32;
let records: Vec<Record> = (0..200)
.map(|n| Record {
key: DiskKey::new(n, ItemType::INODE_ITEM, 0),
data: vec![0; 100],
})
.collect();
let shaped = shape(&records, node).expect("shapeable");
let capacity = node as usize - Header::SIZE;
for (index, count) in shaped.leaves.iter().enumerate() {
let used = count * (100 + Item::SIZE);
if index + 1 < shaped.leaves.len() {
assert!(
used + 100 + Item::SIZE > capacity,
"leaf {index} had room for another record"
);
}
assert!(used <= capacity);
}
assert_eq!(shaped.leaves.iter().sum::<usize>(), 200);
}
fn populated() -> TreeBuilder {
let meta = Metadata::new(0o644, TIME).owned_by(1000, 100);
let dir = Metadata::new(0o755, TIME);
TreeBuilder::new()
.directory(b"/dir".to_vec(), dir)
.file(b"/dir/one".to_vec(), b"x", meta)
.hardlink(b"/dir/two".to_vec(), b"/dir/one".to_vec(), meta)
.symlink(b"/dir/link".to_vec(), b"/small.txt".to_vec(), meta)
.symlink(b"/dir/up".to_vec(), b"../small.txt".to_vec(), meta)
.file(b"/small.txt".to_vec(), b"hello\n", meta)
.xattr(b"user.note".to_vec(), b"hi".to_vec())
.file(b"/big.bin".to_vec(), vec![7u8; (1 << 20) + 5000], meta)
.file(b"/empty".to_vec(), Vec::new(), meta)
.char_device(b"/nulldev".to_vec(), 1, 3, meta)
.block_device(b"/disk".to_vec(), 8, 0, meta)
.fifo(b"/pipe".to_vec(), meta)
.socket(b"/sock".to_vec(), meta)
}
fn filled(source: impl crate::Source, bytes: u64) -> Image {
format(source, bytes, options()).expect("a formattable tree")
}
fn read(image: &Image) -> Reader<Cursor<&[u8]>> {
Reader::open(Cursor::new(image.as_bytes())).expect("this crate reads what it wrote")
}
#[test]
fn every_kind_of_entry_a_source_states_reads_back_as_what_it_was() {
let image = filled(populated(), GIB);
let mut reader = read(&image);
let mut paths: Vec<String> = reader
.walk()
.expect("a walk")
.iter()
.map(|entry| String::from_utf8_lossy(&entry.path).into_owned())
.collect();
paths.sort();
assert_eq!(
paths,
[
"",
"/big.bin",
"/dir",
"/dir/link",
"/dir/one",
"/dir/two",
"/dir/up",
"/disk",
"/empty",
"/nulldev",
"/pipe",
"/small.txt",
"/sock"
]
);
let small = reader.lookup(b"/small.txt").expect("the file is there");
assert_eq!(small.item.mode & 0o7777, 0o644);
assert_eq!((small.item.uid, small.item.gid), (1000, 100));
assert_eq!(small.item.mtime, TIME);
assert_eq!(small.item.otime, TIME);
assert_eq!(reader.read_data(&small).expect("bytes"), b"hello\n");
let xattrs = reader.xattrs(&small).expect("attributes");
assert_eq!(xattrs.len(), 1);
assert_eq!(xattrs[0].name, b"user.note");
assert_eq!(xattrs[0].value, b"hi");
let big = reader.lookup(b"/big.bin").expect("the file is there");
let bytes = reader.read_data(&big).expect("bytes");
assert_eq!(bytes.len(), (1 << 20) + 5000);
assert!(bytes.iter().all(|&b| b == 7));
let mut middle = [0u8; 16];
reader
.read_into(&big, (1 << 20) + 8, &mut middle)
.expect("a read past the first extent");
assert_eq!(middle, [7u8; 16]);
let empty = reader.lookup(b"/empty").expect("the file is there");
assert_eq!(empty.item.size, 0);
assert!(reader.read_data(&empty).expect("bytes").is_empty());
let link = reader
.lookup_no_follow(b"/dir/link")
.expect("the link is there");
assert!(link.is_symlink());
assert_eq!(reader.link_target(&link).expect("target"), b"/small.txt");
assert_eq!(
reader.lookup(b"/dir/link").expect("through the link").inode,
reader.lookup(b"/small.txt").expect("the target").inode
);
let up = reader
.lookup_no_follow(b"/dir/up")
.expect("the link is there");
assert_eq!(reader.link_target(&up).expect("target"), b"../small.txt");
let one = reader.lookup(b"/dir/one").expect("the file is there");
let two = reader.lookup(b"/dir/two").expect("the second name");
assert_eq!(one.inode, two.inode);
assert_eq!(one.item.nlink, 2);
assert_eq!(reader.read_data(&two).expect("bytes"), b"x");
let device = reader.lookup(b"/nulldev").expect("the node is there");
assert_eq!(device.item.device(), (1, 3));
assert_eq!(device.item.mode & 0o170_000, 0o020_000);
let disk = reader.lookup(b"/disk").expect("the node is there");
assert_eq!(disk.item.device(), (8, 0));
assert_eq!(disk.item.mode & 0o170_000, 0o060_000);
assert_eq!(
reader.lookup(b"/pipe").expect("the node").item.mode & 0o170_000,
0o010_000
);
assert_eq!(
reader.lookup(b"/sock").expect("the node").item.mode & 0o170_000,
0o140_000
);
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
#[test]
fn every_byte_written_verifies_against_the_checksum_written_beside_it() {
let image = filled(populated(), GIB);
let mut reader = read(&image);
for entry in reader.walk().expect("a walk") {
if entry.node.is_file() {
reader
.verify_data(&entry.node)
.unwrap_or_else(|e| panic!("{}: {e}", String::from_utf8_lossy(&entry.path)));
}
}
let mut bytes = image.into_bytes();
let at = image_data_offset(&bytes);
bytes[at] ^= 0xff;
let mut reader = Reader::open(Cursor::new(&bytes[..])).expect("still readable");
let big = reader.lookup(b"/big.bin").expect("the file is there");
assert!(matches!(
reader.verify_data(&big),
Err(super::super::ReadError::DataChecksum { .. })
));
}
fn image_data_offset(bytes: &[u8]) -> usize {
let volume = Volume::open(Cursor::new(bytes)).expect("readable");
let chunk = volume
.chunk_map()
.chunks()
.iter()
.find(|chunk| chunk.flags.contains(BlockGroupFlags::DATA))
.expect("a data block group");
chunk.copies[0] as usize
}
#[test]
fn a_source_and_its_image_hold_the_same_tree_whatever_order_the_source_gave_it() {
let forward = filled(populated(), GIB);
let mut entries = populated().into_entries();
entries.reverse();
let backward = format(Reversed(entries), GIB, options()).expect("a formattable tree");
assert_eq!(forward.as_bytes(), backward.as_bytes());
}
struct Reversed(Vec<crate::SourceEntry>);
impl crate::Source for Reversed {
fn into_entries(self) -> Vec<crate::SourceEntry> {
self.0
}
}
#[test]
fn nothing_a_source_states_is_lost_on_the_way_in() {
let image = filled(populated(), GIB);
assert!(image.fidelity().is_faithful());
assert!(image.fidelity().records().is_empty());
let precise = Metadata::new(0o600, TIME).with_times(
Timestamp {
secs: 1_700_000_001,
nanos: 123_456_789,
},
Timestamp {
secs: 1_700_000_002,
nanos: 987_654_321,
},
Timestamp {
secs: 1_700_000_003,
nanos: 500_000_000,
},
);
let image = filled(
TreeBuilder::new().file(b"/precise".to_vec(), b"x", precise),
GIB,
);
assert!(image.fidelity().is_faithful());
let mut reader = read(&image);
let node = reader.lookup(b"/precise").expect("the file is there");
assert_eq!(node.item.atime, precise.atime);
assert_eq!(node.item.ctime, precise.ctime, "the change time survives");
assert_eq!(node.item.mtime, precise.mtime);
assert_eq!(node.item.mtime.nanos, 500_000_000, "and its fraction");
}
#[test]
fn a_subvolume_is_a_tree_of_its_own_that_a_walk_crosses_into() {
let meta = Metadata::new(0o644, TIME);
let dir = Metadata::new(0o755, TIME);
let source = TreeBuilder::new()
.directory(b"/@".to_vec(), dir)
.file(b"/@/etc".to_vec(), b"root\n", meta)
.directory(b"/@home".to_vec(), dir)
.file(b"/@home/user".to_vec(), b"home\n", meta)
.file(b"/outside".to_vec(), b"top\n", meta);
let image = format(
source,
GIB,
options()
.subvolume(SubvolumeRequest::new(b"/@".to_vec(), [0x66; 16]))
.subvolume(SubvolumeRequest::new(b"/@home".to_vec(), [0x55; 16]).read_only(true))
.default_subvolume(b"/@".to_vec()),
)
.expect("a formattable tree");
let mut reader = read(&image);
let found: Vec<(u64, [u8; 16], bool, Vec<u8>)> = reader
.subvolumes()
.iter()
.map(|sub| (sub.id, sub.uuid, sub.read_only, sub.name.clone()))
.collect();
assert_eq!(
found,
[
(objectid::FS_TREE, [0x44; 16], false, Vec::new()),
(256, [0x66; 16], false, b"@".to_vec()),
(257, [0x55; 16], true, b"@home".to_vec()),
]
);
assert_eq!(reader.default_subvolume(), 256);
let mut paths: Vec<String> = reader
.walk()
.expect("a walk")
.iter()
.map(|entry| String::from_utf8_lossy(&entry.path).into_owned())
.collect();
paths.sort();
assert_eq!(
paths,
["", "/@", "/@/etc", "/@home", "/@home/user", "/outside"]
);
let inside = reader.lookup(b"/@home/user").expect("the file is there");
assert_eq!(inside.tree, 257);
assert_eq!(reader.read_data(&inside).expect("bytes"), b"home\n");
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
#[test]
fn every_tree_this_writer_emits_holds_its_records_in_key_order() {
let meta = Metadata::new(0o644, TIME);
let source = TreeBuilder::new()
.directory(b"/@".to_vec(), Metadata::new(0o755, TIME))
.file(b"/@/etc".to_vec(), b"root\n", meta)
.directory(b"/@home".to_vec(), Metadata::new(0o755, TIME))
.file(b"/@home/user".to_vec(), vec![7u8; 300_000], meta)
.file(b"/outside".to_vec(), b"top\n", meta);
let image = format(
source,
GIB,
options()
.subvolume(SubvolumeRequest::new(b"/@".to_vec(), [0xee; 16]))
.subvolume(SubvolumeRequest::new(b"/@home".to_vec(), [0x11; 16])),
)
.expect("a formattable tree");
let mut volume = opened(&image);
for root in volume.tree_roots().expect("the trees") {
let mut previous: Option<crate::btrfs::ondisk::DiskKey> = None;
let mut count = 0usize;
volume
.tree(root)
.for_each_item(|key, _| {
if let Some(before) = previous {
assert!(
before < *key,
"tree {} holds {key:?} after {before:?}",
root.objectid
);
}
previous = Some(*key);
count += 1;
true
})
.expect("a walkable tree");
assert!(count > 0, "tree {} is empty", root.objectid);
}
}
#[test]
fn a_root_tree_spanning_more_than_one_leaf_is_shaped_and_refilled_alike() {
for (node_size, count) in [(4096u32, 2u8), (16384, 22)] {
let mut source = TreeBuilder::new();
let mut with =
options().plan(PlanRequest::new(0).node_size(NodeSize::Bytes(node_size)));
for at in 0..count {
let path = vec![b'/', b'a' + at];
source = source.directory(path.clone(), Metadata::new(0o755, TIME));
with = with.subvolume(SubvolumeRequest::new(path, [at + 1; 16]));
}
let image = format(source, GIB, with)
.unwrap_or_else(|e| panic!("{count} subvolumes at a {node_size}-byte node: {e}"));
let mut reader = Reader::open(Cursor::new(image.as_bytes()))
.expect("this crate reads what it wrote");
assert_eq!(reader.subvolumes().len(), usize::from(count) + 1);
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
}
#[test]
fn the_uuid_tree_maps_the_identifier_each_subvolume_records() {
let image = image_of(GIB, PlanRequest::new(0));
let mut volume = opened(&image);
let uuid_tree = |volume: &mut Volume<Cursor<&[u8]>>| {
volume
.tree_roots()
.expect("the trees")
.into_iter()
.find(|root| root.objectid == objectid::UUID_TREE)
.expect("a UUID tree")
};
let root = uuid_tree(&mut volume);
let mut entries = Vec::new();
volume
.tree(root)
.for_each_item(|key, data| {
entries.push((key.objectid, key.kind, key.offset, data.to_vec()));
true
})
.expect("a walkable tree");
let (low, high) = uuid_key([0x44; 16]);
assert_eq!(
entries,
[(
low,
ItemType::UUID_SUBVOL,
high,
objectid::FS_TREE.to_le_bytes().to_vec()
)]
);
let unset = format(TreeBuilder::new(), GIB, options().subvolume_uuid([0; 16]))
.expect("a volume past the minimum");
let mut volume = Volume::open(Cursor::new(unset.as_bytes())).expect("readable");
let root = uuid_tree(&mut volume);
assert_eq!(volume.tree(root).count_items().expect("walkable"), 0);
}
#[test]
fn two_subvolumes_sharing_an_identifier_are_refused_before_anything_is_written() {
let dir = Metadata::new(0o755, TIME);
let source = || {
TreeBuilder::new()
.directory(b"/a".to_vec(), dir)
.directory(b"/b".to_vec(), dir)
};
let repeated = format(
source(),
GIB,
options()
.subvolume(SubvolumeRequest::new(b"/a".to_vec(), [0x77; 16]))
.subvolume(SubvolumeRequest::new(b"/b".to_vec(), [0x77; 16])),
)
.err()
.expect("one identifier for two subvolumes");
assert!(
matches!(
repeated,
FormatError::Model(ModelError::SubvolumeUuidRepeated { .. })
),
"{repeated:?}"
);
let with_top = format(
source(),
GIB,
options().subvolume(SubvolumeRequest::new(b"/a".to_vec(), [0x44; 16])),
)
.err()
.expect("the top-level subvolume holds 0x44 already");
assert!(
matches!(
with_top,
FormatError::Model(ModelError::SubvolumeUuidRepeated { .. })
),
"{with_top:?}"
);
format(
source(),
GIB,
options()
.subvolume_uuid([0; 16])
.subvolume(SubvolumeRequest::new(b"/a".to_vec(), [0; 16]))
.subvolume(SubvolumeRequest::new(b"/b".to_vec(), [0; 16])),
)
.expect("identifiers never set collide with nothing");
}
#[test]
fn a_source_larger_than_the_volume_is_refused_before_anything_is_written() {
let source = TreeBuilder::new().file(
b"/huge".to_vec(),
vec![0u8; 300 << 20],
Metadata::new(0o644, TIME),
);
let err = format(source, 256 << 20, options())
.err()
.expect("more than the volume holds");
assert!(
matches!(
err,
FormatError::Geometry(GeometryError::ContentTooLarge { .. })
),
"{err:?}"
);
}
#[test]
fn a_tree_the_filesystem_cannot_hold_is_refused_and_names_the_entry() {
let err = format(
TreeBuilder::new().hardlink(
b"/a".to_vec(),
b"/nowhere".to_vec(),
Metadata::new(0o644, TIME),
),
GIB,
options(),
)
.err()
.expect("the link names nothing");
assert!(
matches!(
err,
FormatError::Model(ModelError::HardlinkTargetMissing { .. })
),
"{err:?}"
);
assert!(err.to_string().contains("/nowhere"), "{err}");
}
fn densely_linked(count: usize, node: u32) -> Image {
let meta = Metadata::new(0o644, TIME);
let long = "n".repeat(200);
let mut source = TreeBuilder::new().file(b"/target".to_vec(), b"x", meta);
for n in 0..count {
source = source.hardlink(
format!("/{long}{n:04}").into_bytes(),
b"/target".to_vec(),
meta,
);
}
format(
source,
GIB,
options().plan(PlanRequest::new(0).node_size(NodeSize::Bytes(node))),
)
.expect("a formattable tree")
}
#[test]
fn names_past_what_one_record_holds_go_into_the_extended_form_and_read_back() {
let image = densely_linked(40, 4096);
let mut reader = read(&image);
let target = reader.lookup(b"/target").expect("the file is there");
assert_eq!(target.item.nlink, 41, "one name and forty more");
assert_eq!(reader.walk().expect("a walk").len(), 42);
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
let mut volume = opened(&image);
let root = volume
.tree_roots()
.expect("the root tree")
.into_iter()
.find(|root| root.objectid == objectid::FS_TREE)
.expect("the filesystem tree");
let mut kinds = std::collections::BTreeSet::new();
volume
.tree(root)
.for_each_item(|key, _| {
kinds.insert(key.kind);
true
})
.expect("a walk of the filesystem tree");
assert!(kinds.contains(&ItemType::INODE_REF), "{kinds:?}");
assert!(kinds.contains(&ItemType::INODE_EXTREF), "{kinds:?}");
let roomy = densely_linked(40, 65536);
let mut volume = opened(&roomy);
let root = volume
.tree_roots()
.expect("the root tree")
.into_iter()
.find(|root| root.objectid == objectid::FS_TREE)
.expect("the filesystem tree");
let mut kinds = std::collections::BTreeSet::new();
volume
.tree(root)
.for_each_item(|key, _| {
kinds.insert(key.kind);
true
})
.expect("a walk of the filesystem tree");
assert!(!kinds.contains(&ItemType::INODE_EXTREF), "{kinds:?}");
}
#[test]
fn a_tree_of_small_files_with_attributes_stays_inside_its_reservation() {
let meta = Metadata::new(0o644, TIME);
let mut source = TreeBuilder::new();
for n in 0..2000u32 {
source = source
.file(format!("/f{n:05}").into_bytes(), vec![b'x'; 512], meta)
.xattr(b"user.n".to_vec(), vec![b'v'; 64]);
}
let image = filled(source, 2 * GIB);
let mut reader = read(&image);
assert_eq!(reader.walk().expect("a walk").len(), 2001);
let one = reader.lookup(b"/f01234").expect("the file is there");
assert_eq!(reader.read_data(&one).expect("bytes"), vec![b'x'; 512]);
assert_eq!(reader.xattrs(&one).expect("attributes").len(), 1);
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
#[test]
fn a_name_in_every_directory_and_a_file_in_every_leaf_still_reads_back() {
let meta = Metadata::new(0o644, TIME);
let mut source = TreeBuilder::new();
for n in 0..400u32 {
source = source.file(format!("/f{n:04}").into_bytes(), vec![0xab; 8192], meta);
}
let image = filled(source, 2 * GIB);
let mut reader = read(&image);
assert_eq!(reader.walk().expect("a walk").len(), 401);
let one = reader.lookup(b"/f0123").expect("the file is there");
assert_eq!(reader.read_data(&one).expect("bytes"), vec![0xab; 8192]);
reader.verify_data(&one).expect("its checksums");
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
let root = reader
.volume_mut()
.tree_roots()
.expect("the root tree")
.into_iter()
.find(|root| root.objectid == objectid::FS_TREE)
.expect("the filesystem tree");
assert!(root.level > 0, "the filesystem tree is still one leaf");
}
#[test]
fn a_file_larger_than_a_data_chunk_spans_several_and_reads_back_whole() {
let meta = Metadata::new(0o644, TIME);
let content: Vec<u8> = (0..20 * MIB).map(|n| (n % 251) as u8).collect();
let source = TreeBuilder::new().file(b"/span.bin".to_vec(), content.clone(), meta);
let image = filled(source, 2 * GIB);
let volume = opened(&image);
let data_chunks = volume
.chunk_map()
.chunks()
.iter()
.filter(|chunk| chunk.flags.contains(BlockGroupFlags::DATA))
.count();
assert!(
data_chunks > 1,
"{data_chunks} data chunks — the file fit one"
);
let mut reader = read(&image);
let entry = reader.lookup(b"/span.bin").expect("the file is there");
assert_eq!(reader.read_data(&entry).expect("bytes"), content);
reader.verify_data(&entry).expect("its checksums");
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
#[test]
fn tree_blocks_step_over_the_window_a_superblock_copy_takes_and_leave_it_free() {
let layout = plan_layout(&PlanRequest::new(GIB)).expect("a default volume");
let (index, chunk) = layout
.chunks
.iter()
.enumerate()
.find(|(_, chunk)| !mirror_windows(chunk, &layout.superblock_mirrors).is_empty())
.expect("a chunk holds the copy at sixty-four mebibytes");
assert!(chunk.flags.contains(BlockGroupFlags::METADATA));
let window = mirror_windows(chunk, &layout.superblock_mirrors)[0];
let node = u64::from(layout.node_size);
let mut allocation = Allocation::new(&layout);
let past = (window - chunk.logical) / node + 8;
let blocks = allocation
.take(&layout, BlockGroupFlags::METADATA, past)
.expect("the chunk has room past the window");
assert!(
blocks
.iter()
.all(|&at| at + node <= window || at >= window + MIRROR_WINDOW),
"a block was handed out inside the window at {window}"
);
assert_eq!(
blocks.last().copied(),
Some(window + MIRROR_WINDOW + 7 * node),
"allocation resumed right past the window"
);
assert_eq!(
allocation.used[index],
past * node,
"the window is not counted as used"
);
assert_eq!(
allocation.free_runs(index, chunk.length),
[
(window - chunk.logical, MIRROR_WINDOW),
(
allocation.reached[index],
chunk.length - allocation.reached[index]
),
],
"the window is a free run of its own, ahead of the run behind what is held"
);
}
#[test]
fn file_data_steps_over_the_window_a_superblock_copy_takes_and_reads_back_whole() {
let meta = Metadata::new(0o644, TIME);
let mut source = TreeBuilder::new();
let mut contents = Vec::new();
for index in 0..7u8 {
let cycle: Vec<u8> = (0..251u8).map(|n| n ^ index).collect();
let content: Vec<u8> = cycle
.iter()
.copied()
.cycle()
.take((8 * MIB) as usize)
.collect();
source = source.file(format!("/f{index}").into_bytes(), content.clone(), meta);
contents.push(content);
}
let plan = PlanRequest::new(0).metadata_profile(Profile::Single);
let image = format(source, GIB, options().plan(plan)).expect("a formattable tree");
let at = MIRRORS[1] as usize;
let sb = SuperBlock::read_from(&image.as_bytes()[at..at + SUPER_INFO_SIZE])
.expect("a superblock at sixty-four mebibytes");
assert_eq!(sb.bytenr, MIRRORS[1]);
let layout = image.layout();
let windows: Vec<u64> = layout
.chunks_of(BlockGroupFlags::DATA)
.flat_map(|chunk| mirror_windows(chunk, &layout.superblock_mirrors))
.collect();
assert_eq!(windows.len(), 1, "a data chunk holds the copy");
let mut reader = read(&image);
for (index, content) in contents.iter().enumerate() {
let entry = reader
.lookup(format!("/f{index}").as_bytes())
.expect("the file is there");
assert_eq!(&reader.read_data(&entry).expect("bytes"), content);
reader.verify_data(&entry).expect("its checksums");
}
assert!(reader.scan().is_clean(), "{:?}", reader.scan().anomalies());
}
}