use super::MappedChunk;
use super::btree::levels_above;
use super::ondisk::{
BlockGroupFlags, ChecksumType, Chunk, CompatRoFlags, DevItem, DirItem, Header, IncompatFlags,
InodeItem, InodeRef, Item, KeyPtr, MAX_BLOCK_SIZE, MIN_BLOCK_SIZE, MIRRORS, RootItem,
SUPER_INFO_SIZE, Stripe, holds_mirror,
};
#[cfg(feature = "serde")]
use serde::Serialize;
pub const RESERVED_HEAD: u64 = 1 << 20;
pub const STRIPE_LEN: u64 = 64 << 10;
pub const BOOTSTRAP_SYSTEM_CHUNK: u64 = 4 << 20;
pub const VOLUME_SHARE: u64 = 10;
pub const LARGE_VOLUME: u64 = 50 << 30;
pub const DEFAULT_NODE_SIZE: u32 = 16 << 10;
pub const DEFAULT_SECTOR_SIZE: u32 = 4096;
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum Profile {
#[default]
Single,
Dup,
}
impl Profile {
#[must_use]
pub const fn copies(self) -> u64 {
match self {
Self::Single => 1,
Self::Dup => 2,
}
}
#[must_use]
pub const fn flag(self) -> BlockGroupFlags {
match self {
Self::Single => BlockGroupFlags::from_bits(0),
Self::Dup => BlockGroupFlags::DUP,
}
}
}
crate::naming::named_choice!(Profile {
Profile::Single => "single",
Profile::Dup => "dup",
});
crate::naming::serialize_as_name!(Profile);
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum SectorSize {
#[default]
Auto,
Bytes(u32),
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum NodeSize {
#[default]
Auto,
Bytes(u32),
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Content {
pub directories: u64,
pub files: u64,
pub names: u64,
pub longest_name: u32,
pub longest_value: u64,
pub xattrs: u64,
pub subvolumes: u64,
pub data_bytes: u64,
pub data_extents: u64,
}
impl Content {
pub const EMPTY: Self = Self {
directories: 1,
files: 0,
names: 0,
longest_name: 0,
longest_value: 0,
xattrs: 0,
subvolumes: 0,
data_bytes: 0,
data_extents: 0,
};
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Reservation {
pub metadata_blocks: u64,
pub system_blocks: u64,
pub node_size: u32,
}
impl Reservation {
#[must_use]
pub const fn metadata_bytes(&self) -> u64 {
self.metadata_blocks.saturating_mul(self.node_size as u64)
}
#[must_use]
pub const fn system_bytes(&self) -> u64 {
self.system_blocks.saturating_mul(self.node_size as u64)
}
pub const fn account(
&self,
metadata_blocks_used: u64,
system_blocks_used: u64,
) -> Result<Slack, ReservationExceeded> {
let Some(metadata_blocks) = self.metadata_blocks.checked_sub(metadata_blocks_used) else {
return Err(ReservationExceeded {
pool: Pool::Metadata,
reserved: self.metadata_blocks,
used: metadata_blocks_used,
});
};
let Some(system_blocks) = self.system_blocks.checked_sub(system_blocks_used) else {
return Err(ReservationExceeded {
pool: Pool::System,
reserved: self.system_blocks,
used: system_blocks_used,
});
};
Ok(Slack {
metadata_blocks,
system_blocks,
})
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum Pool {
Metadata,
System,
}
impl Pool {
#[must_use]
pub const fn as_str(self) -> &'static str {
match self {
Self::Metadata => "metadata",
Self::System => "system",
}
}
}
crate::naming::serialize_as_name!(Pool);
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Slack {
pub metadata_blocks: u64,
pub system_blocks: u64,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[error("the {} reservation of {reserved} blocks was exceeded: {used} were spent", pool.as_str())]
#[non_exhaustive]
pub struct ReservationExceeded {
pub pool: Pool,
pub reserved: u64,
pub used: u64,
}
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum GeometryError {
#[error(
"sector size {bytes} is not a power of two between {MIN_BLOCK_SIZE} and {MAX_BLOCK_SIZE}"
)]
#[non_exhaustive]
SectorSizeUnsupported {
bytes: u32,
},
#[error(
"node size {bytes} is not a power of two between the {sector_size}-byte sector and \
{MAX_BLOCK_SIZE}"
)]
#[non_exhaustive]
NodeSizeUnsupported {
bytes: u32,
sector_size: u32,
},
#[error(
"a volume of {volume_bytes} bytes is too small: {minimum} are needed for the chunks \
these profiles require"
)]
#[non_exhaustive]
VolumeTooSmall {
volume_bytes: u64,
minimum: u64,
},
#[error(
"a volume of {volume_bytes} bytes cannot hold this content: the chunks it needs span \
{needed} bytes"
)]
#[non_exhaustive]
ContentTooLarge {
volume_bytes: u64,
needed: u64,
},
#[error(
"this content needs {chunks} chunks, whose records need {needed_blocks} tree blocks, \
and the system chunk holds {available_blocks}"
)]
#[non_exhaustive]
ChunkMapTooLarge {
chunks: u64,
needed_blocks: u64,
available_blocks: u64,
},
#[error("this crate does not write {names} ({bits:#x})")]
#[non_exhaustive]
FeatureUnsupported {
bits: u64,
names: String,
},
#[error("the {feature} feature also requires {requires}")]
#[non_exhaustive]
FeatureIncoherent {
feature: &'static str,
requires: &'static str,
},
}
pub const WRITABLE_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(),
);
pub const WRITABLE_COMPAT_RO: CompatRoFlags = CompatRoFlags::from_bits(
CompatRoFlags::FREE_SPACE_TREE.bits()
| CompatRoFlags::FREE_SPACE_TREE_VALID.bits()
| CompatRoFlags::BLOCK_GROUP_TREE.bits(),
);
pub const DEFAULT_INCOMPAT: IncompatFlags = IncompatFlags::from_bits(
IncompatFlags::MIXED_BACKREF.bits()
| IncompatFlags::EXTENDED_IREF.bits()
| IncompatFlags::SKINNY_METADATA.bits()
| IncompatFlags::NO_HOLES.bits(),
);
pub const DEFAULT_COMPAT_RO: CompatRoFlags = WRITABLE_COMPAT_RO;
pub const DEFAULT_METADATA_PROFILE: Profile = Profile::Dup;
pub const DEFAULT_DATA_PROFILE: Profile = Profile::Single;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PlanRequest {
pub volume_bytes: u64,
pub sector_size: SectorSize,
pub node_size: NodeSize,
pub metadata_profile: Profile,
pub data_profile: Profile,
pub incompat_flags: IncompatFlags,
pub compat_ro_flags: CompatRoFlags,
pub content: Content,
}
impl PlanRequest {
#[must_use]
pub const fn new(volume_bytes: u64) -> Self {
Self {
volume_bytes,
sector_size: SectorSize::Auto,
node_size: NodeSize::Auto,
metadata_profile: DEFAULT_METADATA_PROFILE,
data_profile: DEFAULT_DATA_PROFILE,
incompat_flags: DEFAULT_INCOMPAT,
compat_ro_flags: DEFAULT_COMPAT_RO,
content: Content::EMPTY,
}
}
#[must_use]
pub const fn sector_size(mut self, size: SectorSize) -> Self {
self.sector_size = size;
self
}
#[must_use]
pub const fn node_size(mut self, size: NodeSize) -> Self {
self.node_size = size;
self
}
#[must_use]
pub const fn metadata_profile(mut self, profile: Profile) -> Self {
self.metadata_profile = profile;
self
}
#[must_use]
pub const fn data_profile(mut self, profile: Profile) -> Self {
self.data_profile = profile;
self
}
#[must_use]
pub const fn features(mut self, incompat: IncompatFlags, compat_ro: CompatRoFlags) -> Self {
self.incompat_flags = incompat;
self.compat_ro_flags = compat_ro;
self
}
#[must_use]
pub const fn content(mut self, content: Content) -> Self {
self.content = content;
self
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct BtrfsLayout {
pub volume_bytes: u64,
pub sector_size: u32,
pub node_size: u32,
pub incompat_flags: IncompatFlags,
pub compat_ro_flags: CompatRoFlags,
pub chunks: Vec<MappedChunk>,
pub superblock_mirrors: Vec<u64>,
pub reservation: Reservation,
}
impl BtrfsLayout {
#[must_use]
pub fn device_bytes_used(&self) -> u64 {
self.chunks
.iter()
.map(|chunk| chunk.length * chunk.copies.len() as u64)
.sum()
}
#[must_use]
pub fn logical_end(&self) -> u64 {
self.chunks
.last()
.map_or(RESERVED_HEAD, MappedChunk::logical_end)
}
pub fn chunks_of(&self, kind: BlockGroupFlags) -> impl Iterator<Item = &MappedChunk> {
self.chunks
.iter()
.filter(move |chunk| chunk.flags.contains(kind))
}
}
pub fn plan_layout(request: &PlanRequest) -> Result<BtrfsLayout, GeometryError> {
let (sector_size, node_size) = block_sizes(request)?;
let asked = request.volume_bytes;
let mut aligned = *request;
aligned.volume_bytes -= asked % u64::from(sector_size);
let request = &aligned;
let incompat = validated_features(request, node_size)?;
let compat_ro = request.compat_ro_flags;
let minimum = minimum_volume_bytes(request.metadata_profile, request.data_profile);
if request.volume_bytes < minimum {
return Err(GeometryError::VolumeTooSmall {
volume_bytes: asked,
minimum,
});
}
let superblock_mirrors = held_mirrors(request.volume_bytes);
let metadata_blocks = reserve_metadata(
request,
sector_size,
node_size,
compat_ro,
superblock_mirrors.len() as u64,
);
let metadata_bytes = metadata_blocks.saturating_mul(u64::from(node_size));
let mut lost = Lost::NONE;
let chunks = loop {
let pending = pending_chunks(request, metadata_bytes, lost)?;
let chunks = place_pending(&pending, request.volume_bytes);
let placed = Lost::of(&chunks, &superblock_mirrors);
if placed.within(lost) {
break chunks;
}
lost = lost.max(placed);
};
let reservation = Reservation {
metadata_blocks,
system_blocks: reserve_system(&chunks, &superblock_mirrors, node_size)?,
node_size,
};
Ok(BtrfsLayout {
volume_bytes: request.volume_bytes,
sector_size,
node_size,
incompat_flags: incompat,
compat_ro_flags: compat_ro,
chunks,
superblock_mirrors,
reservation,
})
}
pub fn block_sizes(request: &PlanRequest) -> Result<(u32, u32), GeometryError> {
let sector_size = match request.sector_size {
SectorSize::Auto => DEFAULT_SECTOR_SIZE,
SectorSize::Bytes(bytes) => bytes,
};
if !is_block_size(sector_size) {
return Err(GeometryError::SectorSizeUnsupported { bytes: sector_size });
}
let node_size = match request.node_size {
NodeSize::Auto => DEFAULT_NODE_SIZE.max(sector_size),
NodeSize::Bytes(bytes) => bytes,
};
if !is_block_size(node_size) || node_size < sector_size {
return Err(GeometryError::NodeSizeUnsupported {
bytes: node_size,
sector_size,
});
}
Ok((sector_size, node_size))
}
const fn is_block_size(bytes: u32) -> bool {
bytes.is_power_of_two() && bytes >= MIN_BLOCK_SIZE && bytes <= MAX_BLOCK_SIZE
}
fn validated_features(
request: &PlanRequest,
node_size: u32,
) -> Result<IncompatFlags, GeometryError> {
let unsupported = request.incompat_flags.without(WRITABLE_INCOMPAT);
if !unsupported.is_empty() {
let mut names = String::new();
unsupported.describe(&mut names);
return Err(GeometryError::FeatureUnsupported {
bits: unsupported.bits(),
names,
});
}
let unsupported_ro = request.compat_ro_flags.without(WRITABLE_COMPAT_RO);
if !unsupported_ro.is_empty() {
let mut names = String::new();
unsupported_ro.describe(&mut names);
return Err(GeometryError::FeatureUnsupported {
bits: unsupported_ro.bits(),
names,
});
}
if request
.compat_ro_flags
.contains(CompatRoFlags::BLOCK_GROUP_TREE)
{
if !request
.compat_ro_flags
.contains(CompatRoFlags::FREE_SPACE_TREE)
{
return Err(GeometryError::FeatureIncoherent {
feature: "block-group-tree",
requires: "free-space-tree",
});
}
if !request.incompat_flags.contains(IncompatFlags::NO_HOLES) {
return Err(GeometryError::FeatureIncoherent {
feature: "block-group-tree",
requires: "no-holes",
});
}
}
let mut incompat = request.incompat_flags;
if node_size > MIN_BLOCK_SIZE {
incompat |= IncompatFlags::BIG_METADATA;
} else if incompat.contains(IncompatFlags::BIG_METADATA) {
return Err(GeometryError::FeatureIncoherent {
feature: "big-metadata",
requires: "a node larger than four kibibytes",
});
}
Ok(incompat)
}
#[must_use]
pub const fn minimum_volume_bytes(metadata: Profile, data: Profile) -> u64 {
const MIB: u64 = 1 << 20;
match (metadata, data) {
(Profile::Single, Profile::Single) => 45 * MIB,
(Profile::Dup, Profile::Single) => 109 * MIB,
(Profile::Single, Profile::Dup) => 165 * MIB,
(Profile::Dup, Profile::Dup) => 229 * MIB,
}
}
#[must_use]
pub const fn chunk_length(kind: BlockGroupFlags, profile: Profile, volume_bytes: u64) -> u64 {
let (preferred, floor) = preference(kind, profile, volume_bytes);
let share = volume_bytes / VOLUME_SHARE;
if preferred <= share {
return preferred;
}
let shared = round_down(share / profile.copies(), STRIPE_LEN);
if shared > floor { shared } else { floor }
}
const fn preference(kind: BlockGroupFlags, profile: Profile, volume_bytes: u64) -> (u64, u64) {
const UNREPLICATED: (u64, u64) = (8 << 20, STRIPE_LEN);
if !matches!(profile, Profile::Dup) {
return UNREPLICATED;
}
if kind.contains(BlockGroupFlags::DATA) {
(1 << 30, 64 << 20)
} else if kind.contains(BlockGroupFlags::METADATA) {
let preferred = if volume_bytes > LARGE_VOLUME {
1 << 30
} else {
256 << 20
};
(preferred, 32 << 20)
} else {
UNREPLICATED
}
}
const fn round_down(value: u64, unit: u64) -> u64 {
value - value % unit
}
struct Pending {
kind: BlockGroupFlags,
profile: Profile,
length: u64,
keep: bool,
}
fn pending_chunks(
request: &PlanRequest,
metadata_bytes: u64,
lost: Lost,
) -> Result<Vec<Pending>, GeometryError> {
let volume = request.volume_bytes;
let metadata = request.metadata_profile;
let data = request.data_profile;
let keeps_bootstrap_metadata = matches!(metadata, Profile::Single);
let keeps_bootstrap_data = matches!(data, Profile::Single);
let system = BlockGroupFlags::SYSTEM;
let meta = BlockGroupFlags::METADATA;
let dat = BlockGroupFlags::DATA;
let mut pending = Vec::new();
pending.push(Pending {
kind: system,
profile: Profile::Single,
length: BOOTSTRAP_SYSTEM_CHUNK,
keep: keeps_bootstrap_metadata,
});
pending.push(Pending {
kind: meta,
profile: Profile::Single,
length: chunk_length(meta, Profile::Single, volume),
keep: keeps_bootstrap_metadata,
});
pending.push(Pending {
kind: dat,
profile: Profile::Single,
length: chunk_length(dat, Profile::Single, volume),
keep: keeps_bootstrap_data,
});
if !keeps_bootstrap_metadata {
pending.push(Pending {
kind: system,
profile: metadata,
length: chunk_length(system, metadata, volume),
keep: true,
});
pending.push(Pending {
kind: meta,
profile: metadata,
length: chunk_length(meta, metadata, volume),
keep: true,
});
}
if !keeps_bootstrap_data {
pending.push(Pending {
kind: dat,
profile: data,
length: chunk_length(dat, data, volume),
keep: true,
});
}
let held = |kind: BlockGroupFlags| -> u64 {
pending
.iter()
.filter(|entry| entry.keep && entry.kind.contains(kind))
.map(|entry| entry.length)
.sum()
};
let metadata_each = chunk_length(meta, metadata, volume);
let extra_metadata = shortfall(
metadata_bytes.saturating_add(lost.metadata),
held(meta),
metadata_each,
);
let data_each = chunk_length(dat, data, volume);
let extra_data = shortfall(
request.content.data_bytes.saturating_add(lost.data),
held(dat),
data_each,
);
let placed: u64 = pending
.iter()
.map(|entry| entry.length * entry.profile.copies())
.sum();
let needed = extra_metadata
.checked_mul(metadata_each * metadata.copies())
.and_then(|bytes| bytes.checked_add(extra_data.checked_mul(data_each * data.copies())?))
.and_then(|bytes| bytes.checked_add(placed + RESERVED_HEAD));
match needed {
Some(needed) if needed <= volume => {}
_ => {
return Err(GeometryError::ContentTooLarge {
volume_bytes: volume,
needed: needed.unwrap_or(u64::MAX),
});
}
}
for (count, kind, profile, length) in [
(extra_metadata, meta, metadata, metadata_each),
(extra_data, dat, data, data_each),
] {
for _ in 0..count {
pending.push(Pending {
kind,
profile,
length,
keep: true,
});
}
}
Ok(pending)
}
fn place_pending(pending: &[Pending], volume: u64) -> Vec<MappedChunk> {
let mut chunks = Vec::with_capacity(pending.len());
let mut logical = RESERVED_HEAD;
let mut physical = RESERVED_HEAD;
for entry in pending {
let copies = entry.profile.copies();
if entry.keep {
chunks.push(MappedChunk {
logical,
length: entry.length,
flags: entry.kind | entry.profile.flag(),
copies: (0..copies).map(|n| physical + n * entry.length).collect(),
});
}
logical += entry.length;
physical += entry.length * copies;
}
debug_assert!(
physical <= volume,
"the span was checked before it was placed"
);
chunks
}
const fn shortfall(needed: u64, held: u64, each: u64) -> u64 {
match needed.checked_sub(held) {
Some(0) | None => 0,
Some(short) => short.div_ceil(each),
}
}
pub(crate) const MIRROR_WINDOW: u64 = STRIPE_LEN;
fn held_mirrors(volume_bytes: u64) -> Vec<u64> {
MIRRORS
.iter()
.copied()
.filter(|&at| holds_mirror(volume_bytes, at))
.collect()
}
pub(crate) fn mirror_windows(chunk: &MappedChunk, mirrors: &[u64]) -> Vec<u64> {
let mut windows = Vec::new();
for © in &chunk.copies {
let copy_end = copy + chunk.length;
for &at in mirrors {
let end = at + SUPER_INFO_SIZE as u64;
if end <= copy || at >= copy_end {
continue;
}
let first = (at.max(copy) - copy) / MIRROR_WINDOW;
let last = (end.min(copy_end) - 1 - copy) / MIRROR_WINDOW;
windows.extend((first..=last).map(|stripe| chunk.logical + stripe * MIRROR_WINDOW));
}
}
windows.sort_unstable();
windows.dedup();
windows
}
fn window_bytes(chunk: &MappedChunk, mirrors: &[u64]) -> u64 {
mirror_windows(chunk, mirrors).len() as u64 * MIRROR_WINDOW
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Lost {
metadata: u64,
data: u64,
}
impl Lost {
const NONE: Self = Self {
metadata: 0,
data: 0,
};
fn of(chunks: &[MappedChunk], mirrors: &[u64]) -> Self {
let lost = |kind: BlockGroupFlags| -> u64 {
chunks
.iter()
.filter(|chunk| chunk.flags.contains(kind))
.map(|chunk| window_bytes(chunk, mirrors))
.sum()
};
Self {
metadata: lost(BlockGroupFlags::METADATA),
data: lost(BlockGroupFlags::DATA),
}
}
const fn within(self, counted: Self) -> bool {
self.metadata <= counted.metadata && self.data <= counted.data
}
fn max(self, other: Self) -> Self {
Self {
metadata: self.metadata.max(other.metadata),
data: self.data.max(other.data),
}
}
}
fn blocks_for(records: u64, record_bytes: u64, node_size: u32) -> u64 {
if records == 0 {
return 1;
}
let capacity = u64::from(node_size) - Header::SIZE as u64;
let per_leaf = (capacity / (Item::SIZE as u64 + record_bytes)).max(1);
let leaves = records.div_ceil(per_leaf);
levels_above(leaves, capacity / KeyPtr::SIZE as u64)
.iter()
.fold(leaves, |blocks, level| blocks.saturating_add(*level))
}
fn reserve_metadata(
request: &PlanRequest,
sector_size: u32,
node_size: u32,
compat_ro: CompatRoFlags,
mirrors: u64,
) -> u64 {
let content = &request.content;
let name_bytes = u64::from(content.longest_name);
let subvolumes = content.subvolumes.saturating_add(1);
let data_extents = content.data_extents.saturating_add(mirrors);
let trees = 6
+ u64::from(compat_ro.contains(CompatRoFlags::FREE_SPACE_TREE))
+ u64::from(compat_ro.contains(CompatRoFlags::BLOCK_GROUP_TREE));
let root_records = trees
.saturating_add(subvolumes.saturating_mul(3))
.saturating_add(4);
let root_tree = blocks_for(root_records, RootItem::SIZE as u64, node_size);
let fs_records = content
.directories
.saturating_add(content.files.saturating_mul(2))
.saturating_add(content.names.saturating_mul(3))
.saturating_add(content.xattrs)
.saturating_add(data_extents);
let fs_trees = blocks_for(
fs_records,
(InodeItem::SIZE as u64)
.max(InodeRef::SIZE as u64 + name_bytes)
.max(DirItem::SIZE as u64 + name_bytes + content.longest_value),
node_size,
)
.saturating_add(subvolumes);
let csum_bytes = content
.data_bytes
.div_ceil(u64::from(sector_size))
.saturating_mul(CSUM_BYTES_PER_SECTOR);
let csum_tree = blocks_for(
csum_bytes.div_ceil(MAX_CSUM_RECORD),
MAX_CSUM_RECORD,
node_size,
);
let small_trees =
(3 * blocks_for(64, 64, node_size)).saturating_add(blocks_for(subvolumes, 32, node_size));
let outside_extent_tree = root_tree
.saturating_add(fs_trees)
.saturating_add(csum_tree)
.saturating_add(small_trees);
let capacity = u64::from(node_size) - Header::SIZE as u64;
let per_leaf = (capacity / (Item::SIZE as u64 + EXTENT_RECORD_BYTES)).max(2);
let outside_records = outside_extent_tree
.saturating_add(data_extents)
.saturating_mul(2);
let extent_tree = blocks_for(
outside_records.saturating_add(outside_records.div_ceil(per_leaf - 1)),
EXTENT_RECORD_BYTES,
node_size,
);
let total = outside_extent_tree.saturating_add(extent_tree);
total.saturating_add(total / 8).saturating_add(8)
}
fn reserve_system(
chunks: &[MappedChunk],
mirrors: &[u64],
node_size: u32,
) -> Result<u64, GeometryError> {
let count = chunks.len() as u64;
let record_bytes = chunks
.iter()
.map(|chunk| Chunk::SIZE as u64 + chunk.copies.len() as u64 * Stripe::SIZE as u64)
.max()
.unwrap_or(Chunk::SIZE as u64)
.max(DevItem::SIZE as u64);
let needed_blocks = blocks_for(count.saturating_add(1), record_bytes, node_size);
let available_blocks = chunks
.iter()
.find(|chunk| chunk.flags.contains(BlockGroupFlags::SYSTEM))
.map_or(0, |chunk| {
(chunk.length - window_bytes(chunk, mirrors)) / u64::from(node_size)
});
if needed_blocks > available_blocks {
return Err(GeometryError::ChunkMapTooLarge {
chunks: count,
needed_blocks,
available_blocks,
});
}
Ok(needed_blocks)
}
pub(crate) const CSUM_BYTES_PER_SECTOR: u64 =
ChecksumType::CRC32C.digest_len().expect("crc32c has one") as u64;
pub(crate) const MAX_CSUM_RECORD: u64 = 2048;
const EXTENT_RECORD_BYTES: u64 = 64;
#[cfg(test)]
mod tests {
use super::*;
const GIB: u64 = 1 << 30;
const MIB: u64 = 1 << 20;
const BASELINE_1G_DEFAULT: &[(u64, u64, &[u64])] = &[
(13_631_488, 8_388_608, &[13_631_488]),
(22_020_096, 8_388_608, &[22_020_096, 30_408_704]),
(30_408_704, 53_673_984, &[38_797_312, 92_471_296]),
];
const BASELINE_1G_SINGLE: &[(u64, u64, &[u64])] = &[
(1_048_576, 4_194_304, &[1_048_576]),
(5_242_880, 8_388_608, &[5_242_880]),
(13_631_488, 8_388_608, &[13_631_488]),
];
fn shape(layout: &BtrfsLayout) -> Vec<(u64, u64, Vec<u64>)> {
layout
.chunks
.iter()
.map(|chunk| (chunk.logical, chunk.length, chunk.copies.clone()))
.collect()
}
fn expected(rows: &[(u64, u64, &[u64])]) -> Vec<(u64, u64, Vec<u64>)> {
rows.iter()
.map(|&(logical, length, copies)| (logical, length, copies.to_vec()))
.collect()
}
#[test]
fn a_default_volume_is_laid_out_the_way_the_baseline_lays_one_out() {
let layout = plan_layout(&PlanRequest::new(GIB)).expect("a gibibyte is formattable");
assert_eq!(shape(&layout), expected(BASELINE_1G_DEFAULT));
assert_eq!(layout.device_bytes_used(), 132_513_792);
}
#[test]
fn nothing_replicated_keeps_the_chunks_the_bootstrap_laid_down() {
let layout = plan_layout(
&PlanRequest::new(GIB)
.metadata_profile(Profile::Single)
.data_profile(Profile::Single),
)
.expect("a gibibyte is formattable");
assert_eq!(shape(&layout), expected(BASELINE_1G_SINGLE));
assert_eq!(layout.device_bytes_used(), 20_971_520);
assert_eq!(layout.chunks[0].logical, RESERVED_HEAD);
}
#[test]
fn replicating_metadata_leaves_the_span_the_replaced_chunks_occupied() {
let layout = plan_layout(&PlanRequest::new(GIB)).expect("a gibibyte is formattable");
let first = layout.chunks[0].logical;
assert_eq!(
first,
RESERVED_HEAD
+ BOOTSTRAP_SYSTEM_CHUNK
+ chunk_length(BlockGroupFlags::METADATA, Profile::Single, GIB,)
);
assert!(first > RESERVED_HEAD);
}
#[test]
fn an_unreplicated_chunk_takes_the_generic_rule_whatever_it_holds() {
let volume = 64 * GIB;
assert_eq!(
chunk_length(BlockGroupFlags::DATA, Profile::Single, volume),
8 * MIB
);
assert_eq!(
chunk_length(BlockGroupFlags::DATA, Profile::Dup, volume),
GIB
);
}
#[test]
fn a_replicated_metadata_chunk_reaches_a_gibibyte_only_past_the_volume_that_earns_it() {
let kind = BlockGroupFlags::METADATA;
assert_eq!(chunk_length(kind, Profile::Dup, LARGE_VOLUME), 256 * MIB);
assert_eq!(chunk_length(kind, Profile::Dup, LARGE_VOLUME + 1), GIB);
assert_eq!(chunk_length(kind, Profile::Dup, 100 * GIB), GIB);
}
#[test]
fn below_every_minimum_a_chunk_is_never_shorter_than_one_stripe() {
for volume in [0, 1, STRIPE_LEN, MIB, 10 * MIB] {
for kind in [BlockGroupFlags::SYSTEM, BlockGroupFlags::METADATA] {
for profile in [Profile::Single, Profile::Dup] {
let length = chunk_length(kind, profile, volume);
assert!(length >= STRIPE_LEN, "{kind:?} {profile:?} on {volume}");
assert_eq!(length % STRIPE_LEN, 0);
}
}
}
assert_eq!(
chunk_length(BlockGroupFlags::SYSTEM, Profile::Single, 0),
STRIPE_LEN
);
}
#[test]
fn no_chunk_takes_more_than_its_share_of_the_volume_once_the_volume_can_afford_a_floor() {
for volume in [GIB, 4 * GIB, 40 * GIB, 400 * GIB, 4000 * GIB] {
for kind in [
BlockGroupFlags::DATA,
BlockGroupFlags::METADATA,
BlockGroupFlags::SYSTEM,
] {
for profile in [Profile::Single, Profile::Dup] {
let length = chunk_length(kind, profile, volume);
assert!(
length <= volume / VOLUME_SHARE,
"{kind:?} {profile:?} on {volume}: {length}"
);
assert_eq!(length % STRIPE_LEN, 0, "{kind:?} {profile:?} on {volume}");
}
}
}
}
#[test]
fn the_two_address_spaces_advance_by_different_amounts_and_neither_overlaps() {
for volume in [110 * MIB, 256 * MIB, GIB, 17 * GIB, 300 * GIB] {
for metadata in [Profile::Single, Profile::Dup] {
for data in [Profile::Single, Profile::Dup] {
if volume < minimum_volume_bytes(metadata, data) {
continue;
}
let layout = plan_layout(
&PlanRequest::new(volume)
.metadata_profile(metadata)
.data_profile(data),
)
.expect("a volume past the minimum");
let mut logical = RESERVED_HEAD;
let mut physical = RESERVED_HEAD;
for chunk in &layout.chunks {
assert!(chunk.logical >= logical, "{volume} {metadata:?} {data:?}");
assert!(chunk.copies[0] >= physical);
for pair in chunk.copies.windows(2) {
assert_eq!(pair[1] - pair[0], chunk.length, "copies are adjacent");
}
logical = chunk.logical_end();
physical = chunk.copies[chunk.copies.len() - 1] + chunk.length;
assert!(physical <= volume, "a copy is placed past the device");
}
}
}
}
}
#[test]
fn a_volume_too_small_for_its_profiles_is_refused_with_the_size_that_would_do() {
for (metadata, data, minimum) in [
(Profile::Single, Profile::Single, 45 * MIB),
(Profile::Dup, Profile::Single, 109 * MIB),
(Profile::Single, Profile::Dup, 165 * MIB),
(Profile::Dup, Profile::Dup, 229 * MIB),
] {
assert_eq!(minimum_volume_bytes(metadata, data), minimum);
let request = PlanRequest::new(minimum - 1)
.metadata_profile(metadata)
.data_profile(data);
assert_eq!(
plan_layout(&request),
Err(GeometryError::VolumeTooSmall {
volume_bytes: minimum - 1,
minimum,
})
);
let request = PlanRequest::new(minimum)
.metadata_profile(metadata)
.data_profile(data);
assert!(plan_layout(&request).is_ok(), "{metadata:?} {data:?}");
}
}
#[test]
fn a_sector_or_node_size_the_format_does_not_define_is_refused() {
for bytes in [0, 1, 512, 2048, 6144, 128 << 10] {
assert_eq!(
plan_layout(&PlanRequest::new(GIB).sector_size(SectorSize::Bytes(bytes))),
Err(GeometryError::SectorSizeUnsupported { bytes })
);
}
for bytes in [512, 2048, 24576, 128 << 10] {
assert_eq!(
plan_layout(&PlanRequest::new(GIB).node_size(NodeSize::Bytes(bytes))),
Err(GeometryError::NodeSizeUnsupported {
bytes,
sector_size: DEFAULT_SECTOR_SIZE,
})
);
}
assert_eq!(
plan_layout(
&PlanRequest::new(GIB)
.sector_size(SectorSize::Bytes(16384))
.node_size(NodeSize::Bytes(4096))
),
Err(GeometryError::NodeSizeUnsupported {
bytes: 4096,
sector_size: 16384,
})
);
}
#[test]
fn a_node_takes_the_sector_size_where_that_is_the_larger_of_the_two() {
for (sector, node) in [
(4096, 16384),
(16384, 16384),
(32768, 32768),
(65536, 65536),
] {
let layout = plan_layout(&PlanRequest::new(GIB).sector_size(SectorSize::Bytes(sector)))
.expect("a gibibyte is formattable");
assert_eq!(layout.node_size, node, "sector {sector}");
}
}
#[test]
fn a_feature_this_crate_does_not_write_is_refused_naming_every_bit_at_once() {
let asked = DEFAULT_INCOMPAT | IncompatFlags::ZONED | IncompatFlags::RAID56;
assert_eq!(
plan_layout(&PlanRequest::new(GIB).features(asked, DEFAULT_COMPAT_RO)),
Err(GeometryError::FeatureUnsupported {
bits: IncompatFlags::ZONED.bits() | IncompatFlags::RAID56.bits(),
names: "raid56, zoned".to_string(),
})
);
}
#[test]
fn a_feature_asked_for_without_what_it_rests_on_is_refused_rather_than_dropped() {
let ro = CompatRoFlags::BLOCK_GROUP_TREE;
assert_eq!(
plan_layout(&PlanRequest::new(GIB).features(DEFAULT_INCOMPAT, ro)),
Err(GeometryError::FeatureIncoherent {
feature: "block-group-tree",
requires: "free-space-tree",
})
);
let ro = CompatRoFlags::BLOCK_GROUP_TREE | CompatRoFlags::FREE_SPACE_TREE;
assert_eq!(
plan_layout(
&PlanRequest::new(GIB)
.features(DEFAULT_INCOMPAT.without(IncompatFlags::NO_HOLES), ro)
),
Err(GeometryError::FeatureIncoherent {
feature: "block-group-tree",
requires: "no-holes",
})
);
}
#[test]
fn asking_for_wide_blocks_at_a_four_kilobyte_node_is_refused_rather_than_cleared() {
let asked = DEFAULT_INCOMPAT | IncompatFlags::BIG_METADATA;
assert_eq!(
plan_layout(
&PlanRequest::new(GIB)
.node_size(NodeSize::Bytes(4096))
.features(asked, DEFAULT_COMPAT_RO)
),
Err(GeometryError::FeatureIncoherent {
feature: "big-metadata",
requires: "a node larger than four kibibytes",
})
);
}
#[test]
fn big_metadata_is_set_exactly_where_a_tree_block_exceeds_four_kibibytes() {
for (sector, node, set) in [
(4096u32, 4096u32, false),
(4096, 16384, true),
(4096, 8192, true),
(65536, 65536, true),
] {
let layout = plan_layout(
&PlanRequest::new(GIB)
.sector_size(SectorSize::Bytes(sector))
.node_size(NodeSize::Bytes(node)),
)
.expect("a gibibyte is formattable");
assert_eq!(
layout.incompat_flags.contains(IncompatFlags::BIG_METADATA),
set,
"sector {sector} node {node}"
);
}
}
#[test]
fn a_volume_is_planned_with_every_superblock_location_it_has_room_for() {
for (volume, expected) in [
((64 << 20) - 1, 1),
(64 << 20, 1),
((64 << 20) + 4096, 2),
(GIB, 2),
(256 << 30, 2),
((256 << 30) + 4096, 3),
] {
let request = PlanRequest::new(volume)
.metadata_profile(Profile::Single)
.data_profile(Profile::Single);
let layout = plan_layout(&request).expect("past the minimum");
assert_eq!(
layout.superblock_mirrors.len(),
expected,
"a volume of {volume} bytes"
);
assert_eq!(layout.superblock_mirrors[0], MIRRORS[0]);
}
}
#[test]
fn an_empty_filesystem_is_reserved_more_metadata_than_one_costs() {
for (node, spent) in [(4096u32, 11u64), (16384, 9), (65536, 9)] {
let layout = plan_layout(&PlanRequest::new(GIB).node_size(NodeSize::Bytes(node)))
.expect("a gibibyte is formattable");
assert!(
layout.reservation.metadata_blocks >= spent,
"node {node}: reserved {}, the baseline spends {spent}",
layout.reservation.metadata_blocks
);
assert_eq!(layout.reservation.node_size, node);
assert!(layout.reservation.system_blocks >= 1);
}
}
#[test]
fn the_reservation_always_fits_the_metadata_chunks_planned_for_it() {
for volume in [110 * MIB, GIB, 17 * GIB, 300 * GIB] {
for content in [
Content::EMPTY,
Content {
directories: 4_000,
files: 40_000,
names: 44_000,
longest_name: 255,
xattrs: 8_000,
subvolumes: 3,
data_bytes: 64 * MIB,
data_extents: 900,
..Content::EMPTY
},
] {
let Ok(layout) = plan_layout(&PlanRequest::new(volume).content(content)) else {
continue;
};
let planned: u64 = layout
.chunks_of(BlockGroupFlags::METADATA)
.map(|chunk| chunk.length - window_bytes(chunk, &layout.superblock_mirrors))
.sum();
assert!(
planned >= layout.reservation.metadata_bytes(),
"a volume of {volume} bytes reserves more metadata than it plans room for"
);
}
}
}
#[test]
fn a_window_is_the_stripe_a_superblock_copy_falls_in_through_either_copy_of_a_chunk() {
let chunk = |logical: u64, length: u64, copies: &[u64]| MappedChunk {
logical,
length,
flags: BlockGroupFlags::METADATA | BlockGroupFlags::DUP,
copies: copies.to_vec(),
};
let first = chunk(30_408_704, 53_673_984, &[38_797_312, 92_471_296]);
assert_eq!(
mirror_windows(&first, &MIRRORS),
[30_408_704 + (64 * MIB - 38_797_312)]
);
let second = chunk(30_408_704, 53_673_984, &[92_471_296, 38_797_312]);
assert_eq!(
mirror_windows(&second, &MIRRORS),
mirror_windows(&first, &MIRRORS)
);
assert!(mirror_windows(&first, &MIRRORS[..1]).is_empty());
let at = chunk(5 * MIB, 8 * MIB, &[64 * MIB]);
assert_eq!(mirror_windows(&at, &MIRRORS), [5 * MIB]);
let before = chunk(5 * MIB, 8 * MIB, &[56 * MIB]);
assert!(mirror_windows(&before, &MIRRORS).is_empty());
let ragged = chunk(5 * MIB, 8 * MIB, &[64 * MIB - 4096]);
assert_eq!(mirror_windows(&ragged, &MIRRORS), [5 * MIB]);
}
#[test]
fn data_block_groups_hold_their_content_once_the_windows_are_taken_out() {
let mut covered = 0;
for data in (40 * MIB..120 * MIB).step_by((STRIPE_LEN / 4) as usize) {
let request = PlanRequest::new(GIB)
.metadata_profile(Profile::Single)
.content(Content {
files: 1,
names: 1,
longest_name: 8,
data_bytes: data,
data_extents: data.div_ceil(MIB) * 2,
..Content::EMPTY
});
let layout = plan_layout(&request).expect("the content fits the volume");
let usable: u64 = layout
.chunks_of(BlockGroupFlags::DATA)
.map(|chunk| chunk.length - window_bytes(chunk, &layout.superblock_mirrors))
.sum();
assert!(
usable >= data,
"{data} bytes of content planned into {usable} bytes of data block groups"
);
covered += layout
.chunks_of(BlockGroupFlags::DATA)
.filter(|chunk| !mirror_windows(chunk, &layout.superblock_mirrors).is_empty())
.count();
}
assert!(covered > 0, "no data chunk ever held a superblock copy");
}
#[test]
fn the_system_reservation_grows_with_the_chunks_the_content_appends() {
let empty = plan_layout(&PlanRequest::new(4 * GIB)).expect("formattable");
assert_eq!(empty.reservation.system_blocks, 1);
let populated = plan_layout(&PlanRequest::new(4 * GIB).content(Content {
files: 1,
names: 1,
longest_name: 16,
data_bytes: 2 * GIB,
data_extents: 2048,
..Content::EMPTY
}))
.expect("two gibibytes of content fit a four-gibibyte volume");
assert!(
populated.reservation.system_blocks >= 3,
"reserved {} system blocks for {} chunks",
populated.reservation.system_blocks,
populated.chunks.len()
);
assert!(populated.chunks.len() > empty.chunks.len());
}
#[test]
fn a_chunk_map_the_system_chunk_cannot_record_is_refused_with_both_numbers() {
let request = PlanRequest::new(1024 * GIB)
.metadata_profile(Profile::Single)
.data_profile(Profile::Single)
.content(Content {
files: 1,
names: 1,
longest_name: 16,
data_bytes: 300 * GIB,
data_extents: 4096,
..Content::EMPTY
});
match plan_layout(&request) {
Err(GeometryError::ChunkMapTooLarge {
chunks,
needed_blocks,
available_blocks,
}) => {
assert!(chunks > 30_000, "{chunks} chunks");
assert!(needed_blocks > available_blocks);
assert_eq!(available_blocks, BOOTSTRAP_SYSTEM_CHUNK / 16384);
}
other => panic!("expected the chunk-map refusal, got {other:?}"),
}
}
#[test]
fn content_larger_than_the_volume_is_refused_rather_than_placed_past_its_end() {
let request = PlanRequest::new(GIB).content(Content {
longest_value: 0,
data_bytes: 8 * GIB,
data_extents: 8192,
files: 1,
..Content::EMPTY
});
assert!(matches!(
plan_layout(&request),
Err(GeometryError::ContentTooLarge { .. })
));
}
#[test]
fn content_no_device_could_hold_is_refused_rather_than_planned_a_chunk_at_a_time() {
for data_bytes in [u64::MAX, u64::MAX / 2, 1 << 60] {
let request = PlanRequest::new(GIB).content(Content {
longest_value: 0,
data_bytes,
data_extents: 1 << 20,
files: 1,
..Content::EMPTY
});
assert!(
matches!(
plan_layout(&request),
Err(GeometryError::ContentTooLarge { .. })
),
"{data_bytes} bytes of data on a gibibyte"
);
}
}
#[test]
fn a_bound_too_large_to_represent_saturates_rather_than_wrapping() {
let request = PlanRequest::new(GIB).content(Content {
longest_value: 0,
directories: u64::MAX,
files: u64::MAX,
names: u64::MAX,
longest_name: 255,
xattrs: u64::MAX,
subvolumes: u64::MAX,
data_bytes: u64::MAX,
data_extents: u64::MAX,
});
assert!(matches!(
plan_layout(&request),
Err(GeometryError::ContentTooLarge { .. })
));
}
#[test]
fn a_name_costs_the_three_records_a_directory_entry_actually_is() {
let base = plan_layout(&PlanRequest::new(17 * GIB).content(Content {
directories: 1_000,
files: 10_000,
names: 0,
longest_name: 255,
..Content::EMPTY
}))
.expect("plannable");
let named = plan_layout(&PlanRequest::new(17 * GIB).content(Content {
directories: 1_000,
files: 10_000,
names: 11_000,
longest_name: 255,
..Content::EMPTY
}))
.expect("plannable");
assert!(named.reservation.metadata_blocks > base.reservation.metadata_blocks);
}
#[test]
fn a_reservation_that_was_exceeded_says_so_rather_than_absorbing_it() {
let reservation = Reservation {
metadata_blocks: 40,
system_blocks: 2,
node_size: 16384,
};
assert_eq!(
reservation.account(24, 1),
Ok(Slack {
metadata_blocks: 16,
system_blocks: 1,
})
);
assert_eq!(
reservation.account(40, 2),
Ok(Slack {
metadata_blocks: 0,
system_blocks: 0,
})
);
assert_eq!(
reservation.account(41, 1),
Err(ReservationExceeded {
pool: Pool::Metadata,
reserved: 40,
used: 41,
})
);
assert_eq!(
reservation.account(1, 3),
Err(ReservationExceeded {
pool: Pool::System,
reserved: 2,
used: 3,
})
);
assert_eq!(
reservation.account(1, 3).unwrap_err().to_string(),
"the system reservation of 2 blocks was exceeded: 3 were spent"
);
assert_eq!(reservation.metadata_bytes(), 40 * 16384);
assert_eq!(reservation.system_bytes(), 2 * 16384);
}
}