use super::ondisk::{
BlockRange, CheckpointMap, CheckpointMapping, ChunkInfo, ChunkList, FreeQueueKey, MAX_VOLUMES,
NODE_DATA_START, TREE_INFO_SIZE,
};
#[cfg(feature = "serde")]
use serde::Serialize;
pub const MIN_BLOCK_COUNT: u64 = 1024;
pub const MAX_CONTAINER_BYTES: u64 = 16 << 40;
pub const LAST_CONTIGUOUS_BLOCK_COUNT: u64 = 1_572_863;
pub(crate) const SPACE_MANAGER_STRUCT_SIZE: u32 = 2520;
pub(crate) const POOL_BITMAP_SLOTS: u32 = 16;
pub(crate) const FIRST_XID: u64 = 1;
pub(crate) const SECOND_XID: u64 = 2;
const QUEUE_ENTRY_BYTES: u64 = 4 + FreeQueueKey::SIZE as u64 + 8;
const QUEUE_NODE_UNCOUNTED: u64 = 24;
const QUEUE_LIMIT_BYTES: u64 = 2 << 20;
const BYTES_PER_VOLUME_SLOT: u64 = 512 << 20;
const ADDRESS_BYTES: u64 = 8;
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum BlockSize {
#[default]
K4,
K8,
K16,
K32,
K64,
}
impl BlockSize {
pub const ALL: [Self; 5] = [Self::K4, Self::K8, Self::K16, Self::K32, Self::K64];
#[must_use]
pub const fn new(bytes: u32) -> Option<Self> {
let mut at = 0;
while at < Self::ALL.len() {
if Self::ALL[at].bytes() == bytes {
return Some(Self::ALL[at]);
}
at += 1;
}
None
}
#[must_use]
pub const fn bytes(self) -> u32 {
match self {
Self::K4 => 4096,
Self::K8 => 8192,
Self::K16 => 16384,
Self::K32 => 32768,
Self::K64 => 65536,
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PlanRequest {
pub container_bytes: u64,
pub block_size: BlockSize,
pub volumes: u32,
}
impl PlanRequest {
#[must_use]
pub const fn new(container_bytes: u64) -> Self {
Self {
container_bytes,
block_size: BlockSize::K4,
volumes: 1,
}
}
#[must_use]
pub const fn block_size(mut self, size: BlockSize) -> Self {
self.block_size = size;
self
}
#[must_use]
pub const fn volumes(mut self, volumes: u32) -> Self {
self.volumes = volumes;
self
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum GeometryError {
#[error(
"a container of {bytes} bytes holds {block_count} blocks of {block_size} bytes, and \
one needs at least {MIN_BLOCK_COUNT}"
)]
#[non_exhaustive]
ContainerTooSmall {
bytes: u64,
block_size: u32,
block_count: u64,
},
#[error("a container of {bytes} bytes is larger than the {MAX_CONTAINER_BYTES} planned")]
#[non_exhaustive]
ContainerTooLarge {
bytes: u64,
},
#[error("a container is formatted with at least one volume")]
NoVolumes,
#[error("a container of {bytes} bytes holds at most {max_volumes} volumes, not {volumes}")]
#[non_exhaustive]
TooManyVolumes {
bytes: u64,
volumes: u32,
max_volumes: u32,
},
#[error(
"a container of {bytes} bytes has {free} blocks free past its own objects, too few for \
what its volumes hold"
)]
#[non_exhaustive]
ContainerFull {
bytes: u64,
free: u64,
},
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct ChunkGeometry {
pub blocks_per_chunk: u64,
pub chunks_per_cib: u64,
pub cibs_per_cab: u64,
pub chunk_count: u64,
pub cib_count: u64,
pub cab_count: u64,
}
impl ChunkGeometry {
#[must_use]
pub fn of(block_count: u64, block_size: u32) -> Self {
let bs = u64::from(block_size);
assert!(
bs > ChunkList::ENTRIES_AT as u64,
"a {bs}-byte block holds no chunk-info block"
);
let blocks_per_chunk = bs * 8;
let chunks_per_cib = (bs - ChunkList::ENTRIES_AT as u64) / ChunkInfo::SIZE as u64;
let cibs_per_cab = (bs - ChunkList::ENTRIES_AT as u64) / ADDRESS_BYTES;
let chunk_count = block_count.div_ceil(blocks_per_chunk);
let cib_count = chunk_count.div_ceil(chunks_per_cib);
let cab_count = if cib_count > cibs_per_cab {
cib_count.div_ceil(cibs_per_cab)
} else {
0
};
Self {
blocks_per_chunk,
chunks_per_cib,
cibs_per_cab,
chunk_count,
cib_count,
cab_count,
}
}
#[must_use]
pub const fn listed(&self) -> u64 {
if self.cab_count > 0 {
self.cab_count
} else {
self.cib_count
}
}
pub(crate) const fn pool_blocks(&self) -> u64 {
3 * (self.chunk_count + self.cib_count + self.cab_count)
}
pub(crate) const fn pool_bitmaps(&self) -> u64 {
self.pool_blocks().div_ceil(self.blocks_per_chunk)
}
pub(crate) fn manager_layout(&self) -> (ManagerArrays, u64) {
let bitmaps = self.pool_bitmaps();
let arrays = manager_arrays(
u64::from(SPACE_MANAGER_STRUCT_SIZE),
bitmaps,
u64::from(POOL_BITMAP_SLOTS) * bitmaps,
);
(arrays, second_list_offset(arrays.addresses, self.listed()))
}
const fn chunk_of(&self, block: u64) -> u64 {
block / self.blocks_per_chunk
}
}
pub(crate) const fn chunk_span(blocks_per_chunk: u64, block_count: u64, chunk: u64) -> (u64, u64) {
let first = chunk * blocks_per_chunk;
let left = block_count - first;
(
first,
if blocks_per_chunk < left {
blocks_per_chunk
} else {
left
},
)
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) struct ManagerArrays {
pub(crate) xids: u64,
pub(crate) slots: u64,
pub(crate) free_list: u64,
pub(crate) addresses: u64,
}
pub(crate) const fn manager_arrays(struct_size: u64, bitmaps: u64, slots: u64) -> ManagerArrays {
let xids = struct_size;
let slot_array = xids + 8 * bitmaps;
let free_list = slot_array + (2 * bitmaps).div_ceil(8) * 8;
ManagerArrays {
xids,
slots: slot_array,
free_list,
addresses: free_list + (2 * slots).div_ceil(8) * 8,
}
}
pub(crate) const fn second_list_offset(addresses: u64, listed: u64) -> u64 {
addresses + ADDRESS_BYTES * listed
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct SpaceManagerShape {
pub blocks: u32,
pub bitmap_xid_offset: u32,
pub bitmap_slot_offset: u32,
pub bitmap_free_list_offset: u32,
pub address_offset: u32,
pub second_address_offset: u32,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct QueueNodeLimits {
pub pool: u16,
pub main: u16,
}
impl QueueNodeLimits {
pub(crate) fn of(block_count: u64, block_size: u32) -> Self {
let bs = u64::from(block_size);
let per_node = (bs - NODE_DATA_START as u64 - TREE_INFO_SIZE as u64 - QUEUE_NODE_UNCOUNTED)
/ QUEUE_ENTRY_BYTES;
let cap = u64::from(Self::cap(block_size));
let nodes = |entries: u64| -> u16 {
let needed = entries.div_ceil(per_node).max(1);
let needed = if needed == 2 { 3 } else { needed };
narrow(needed.min(cap))
};
let share = match block_count {
n if n < 1 << 18 => 32,
n if n < 1 << 20 => 16,
_ => 8,
};
let pool_blocks = ChunkGeometry::of(block_count, block_size).pool_blocks();
Self {
pool: nodes(pool_blocks.div_ceil(8)),
main: nodes(block_count.div_ceil(share)),
}
}
pub(crate) fn cap(block_size: u32) -> u16 {
narrow(QUEUE_LIMIT_BYTES / u64::from(block_size))
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct MapPlace {
pub object: u64,
pub root: u64,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct VolumePlace {
pub object_map: MapPlace,
pub extent_ref_tree: u64,
pub snapshot_tree: u64,
pub root_tree: u64,
pub superblock: u64,
}
impl VolumePlace {
pub(crate) const fn blocks(&self) -> [u64; 6] {
[
self.object_map.object,
self.object_map.root,
self.extent_ref_tree,
self.snapshot_tree,
self.root_tree,
self.superblock,
]
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct QueueRoots {
pub pool: u64,
pub main: u64,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct ChunkBitmap {
pub chunk: u64,
pub block: u64,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Checkpoint {
pub xid: u64,
pub map: u64,
pub superblock: u64,
pub space_manager: u64,
pub reaper: u64,
pub queues: Option<QueueRoots>,
pub object_map: MapPlace,
pub volumes: Vec<VolumePlace>,
pub cab_blocks: Vec<u64>,
pub cib_blocks: Vec<u64>,
pub bitmaps: Vec<ChunkBitmap>,
pub pool_bitmap_slots: Vec<u32>,
pub freed_pool: Vec<BlockRange>,
pub freed_main: Vec<BlockRange>,
pub content: Vec<BlockRange>,
}
#[derive(Clone, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct ApfsLayout {
pub block_size: u32,
pub block_count: u64,
pub max_volumes: u32,
pub descriptor_area: BlockRange,
pub data_area: BlockRange,
pub chunks: ChunkGeometry,
pub space_manager: SpaceManagerShape,
pub pool_bitmap_area: BlockRange,
pub pool_bitmaps: u32,
pub pool: BlockRange,
pub queue_node_limits: QueueNodeLimits,
pub ephemeral_min_blocks: u32,
pub checkpoints: [Checkpoint; 2],
}
const LARGEST_WRITE_ASK: u64 = 100 + 9 * 8;
const LARGEST_STEP: u64 = 4095;
const MOST_HELD: u64 = 143;
const MEBIBYTE: u64 = 1 << 20;
pub(crate) const fn macos_reserve(blocks: u64, block_size: u64) -> u64 {
const fn held(x: u64, low: u64, high: u64) -> u64 {
if x < low {
low
} else if x > high {
high
} else {
x
}
}
let hundredth = blocks / 100;
LARGEST_WRITE_ASK
+ MEBIBYTE.div_ceil(block_size)
+ held(hundredth, 100, 4000)
+ held(hundredth, 25, 4096)
+ LARGEST_STEP
+ MOST_HELD
}
impl ApfsLayout {
#[must_use]
pub const fn newest(&self) -> &Checkpoint {
&self.checkpoints[1]
}
#[must_use]
pub fn free_blocks(&self) -> u64 {
let [_, newest] = self.in_use();
self.block_count - newest.iter().map(|run| run.count).sum::<u64>()
}
#[must_use]
pub fn writable_blocks(&self) -> u64 {
self.free_blocks()
.saturating_sub(macos_reserve(self.block_count, u64::from(self.block_size)))
}
pub(crate) fn in_use(&self) -> [Vec<BlockRange>; 2] {
let [first, second] = &self.checkpoints;
let pool_end = self.pool.start + self.pool.count;
let mut first_main = vec![
BlockRange {
start: 0,
count: pool_end,
},
BlockRange {
start: first.object_map.object,
count: 2,
},
];
first_main.sort_by_key(|run| run.start);
let mut second_main = first_main.clone();
for volume in &second.volumes {
second_main.extend(
volume
.blocks()
.into_iter()
.map(|start| BlockRange { start, count: 1 }),
);
}
second_main.push(BlockRange {
start: second.object_map.object,
count: 2,
});
second_main.extend(second.content.iter().copied());
[first_main, second_main]
}
}
pub fn plan_layout(request: &PlanRequest) -> Result<ApfsLayout, GeometryError> {
let block_size = request.block_size.bytes();
let block_count = request.container_bytes / u64::from(block_size);
let bytes = block_count * u64::from(block_size);
if block_count < MIN_BLOCK_COUNT {
return Err(GeometryError::ContainerTooSmall {
bytes: request.container_bytes,
block_size,
block_count,
});
}
if bytes > MAX_CONTAINER_BYTES {
return Err(GeometryError::ContainerTooLarge { bytes });
}
if request.volumes == 0 {
return Err(GeometryError::NoVolumes);
}
let sizing = Sizing::of(block_count, block_size);
if request.volumes > sizing.max_volumes {
return Err(GeometryError::TooManyVolumes {
bytes,
volumes: request.volumes,
max_volumes: sizing.max_volumes,
});
}
let places = Places::of(&sizing, request.volumes);
Ok(sizing.layout(&places, &[]))
}
pub(crate) struct ContentPlanner {
sizing: Sizing,
places: Places,
planned: Vec<u64>,
next: u64,
content: Vec<BlockRange>,
}
impl ContentPlanner {
pub(crate) fn new(request: &PlanRequest) -> Result<Self, GeometryError> {
let layout = plan_layout(request)?;
let sizing = Sizing::of(layout.block_count, layout.block_size);
let places = Places::of(&sizing, request.volumes);
let mut planned: Vec<u64> = places
.volumes
.iter()
.flat_map(VolumePlace::blocks)
.chain([places.first_map.object, places.first_map.root])
.chain([places.second_map.object, places.second_map.root])
.collect();
planned.sort_unstable();
Ok(Self {
next: sizing.pool_end(),
sizing,
places,
planned,
content: Vec::new(),
})
}
pub(crate) const fn block_size(&self) -> u32 {
self.sizing.block_size
}
pub(crate) fn volume_place(&self, slot: u64) -> VolumePlace {
self.places.volumes[usize::try_from(slot).expect("a slot fits memory")]
}
pub(crate) fn take(&mut self, blocks: u64) -> Result<Vec<BlockRange>, GeometryError> {
let mut runs: Vec<BlockRange> = Vec::new();
let mut wanted = blocks;
while wanted > 0 {
let at = self.planned.partition_point(|&b| b < self.next);
if self.planned.get(at) == Some(&self.next) {
self.next += 1;
continue;
}
let limit = self
.planned
.get(at)
.copied()
.unwrap_or(self.sizing.block_count);
if self.next >= self.sizing.block_count {
return Err(GeometryError::ContainerFull {
bytes: self.sizing.block_count * u64::from(self.sizing.block_size),
free: self.free(),
});
}
let count = wanted.min(limit - self.next);
match runs.last_mut() {
Some(run) if run.start + run.count == self.next => run.count += count,
_ => runs.push(BlockRange {
start: self.next,
count,
}),
}
self.next += count;
wanted -= count;
}
self.content.extend(runs.iter().copied());
Ok(runs)
}
fn free(&self) -> u64 {
let start = self.sizing.pool_end();
let in_range = self.planned.iter().filter(|&&b| b >= start).count() as u64;
self.sizing.block_count - start - in_range
}
#[cfg(test)]
pub(crate) fn keep_every(&mut self, every: u64) {
self.planned.extend(
(self.next..self.sizing.block_count)
.step_by(to_index(every))
.skip(1),
);
self.planned.sort_unstable();
self.planned.dedup();
}
pub(crate) fn finish(self) -> ApfsLayout {
self.sizing.layout(&self.places, &self.content)
}
}
#[cfg(test)]
pub(crate) fn layout_of(block_count: u64, block_size: u32, volumes: u32) -> ApfsLayout {
let sizing = Sizing::of(block_count, block_size);
sizing.layout(&Places::of(&sizing, volumes), &[])
}
#[derive(Clone, Copy, Debug)]
struct Sizing {
block_size: u32,
block_count: u64,
chunks: ChunkGeometry,
manager: SpaceManagerShape,
pool_bitmaps: u32,
pool_bitmap_area: BlockRange,
pool: BlockRange,
limits: QueueNodeLimits,
max_volumes: u32,
ephemeral_min_blocks: u32,
descriptor_area: BlockRange,
data_area: BlockRange,
}
impl Sizing {
fn of(block_count: u64, block_size: u32) -> Self {
let bs = u64::from(block_size);
let chunks = ChunkGeometry::of(block_count, block_size);
let pool_blocks = chunks.pool_blocks();
let pool_bitmaps = chunks.pool_bitmaps();
let slots = u64::from(POOL_BITMAP_SLOTS) * pool_bitmaps;
let (arrays, list_end) = chunks.manager_layout();
let manager_blocks = list_end.div_ceil(bs);
let limits = QueueNodeLimits::of(block_count, block_size);
let ephemeral_min_blocks = u32::from(limits.main).min(8);
let max_volumes: u32 = narrow(
(block_count * bs)
.div_ceil(BYTES_PER_VOLUME_SLOT)
.min(MAX_VOLUMES as u64),
);
let data_blocks = 4
+ 8 * manager_blocks
+ 32 * u64::from(ephemeral_min_blocks) * u64::from(max_volumes)
+ 4 * (u64::from(limits.pool) + u64::from(limits.main));
let per_map = (bs - CheckpointMap::MAPPINGS_AT as u64) / CheckpointMapping::SIZE as u64;
let map_blocks = data_blocks.div_ceil(per_map);
let descriptor_blocks = 4 * map_blocks.div_ceil(4) + 4;
let descriptor_area = BlockRange {
start: 1,
count: descriptor_blocks,
};
let data_area = BlockRange {
start: descriptor_area.start + descriptor_blocks,
count: data_blocks,
};
let pool_bitmap_area = BlockRange {
start: data_area.start + data_blocks,
count: slots,
};
let pool = BlockRange {
start: pool_bitmap_area.start + slots,
count: pool_blocks,
};
Self {
block_size,
block_count,
chunks,
manager: SpaceManagerShape {
blocks: narrow(manager_blocks),
bitmap_xid_offset: narrow(arrays.xids),
bitmap_slot_offset: narrow(arrays.slots),
bitmap_free_list_offset: narrow(arrays.free_list),
address_offset: narrow(arrays.addresses),
second_address_offset: narrow(list_end),
},
pool_bitmaps: narrow(pool_bitmaps),
pool_bitmap_area,
pool,
limits,
max_volumes,
ephemeral_min_blocks,
descriptor_area,
data_area,
}
}
const fn pool_end(&self) -> u64 {
self.pool.start + self.pool.count
}
fn layout(&self, places: &Places, content: &[BlockRange]) -> ApfsLayout {
let manager_blocks = u64::from(self.manager.blocks);
let desc = self.descriptor_area.start;
let data = self.data_area.start;
let mut pool = PoolCursor {
next: self.pool.start,
};
let cibs = to_index(self.chunks.cib_count);
let per_cab = to_index(self.chunks.cibs_per_cab);
let mut cab_blocks = Vec::with_capacity(to_index(self.chunks.cab_count));
let mut cib_blocks = Vec::with_capacity(cibs);
if self.chunks.cab_count > 0 {
for cab in 0..to_index(self.chunks.cab_count) {
cab_blocks.push(pool.take());
for _ in 0..per_cab.min(cibs - cab * per_cab) {
cib_blocks.push(pool.take());
}
}
} else {
cib_blocks.extend((0..cibs).map(|_| pool.take()));
}
let first_map = places.first_map;
let mut touched: Vec<u64> = (0..=self.chunks.chunk_of(self.pool_end() - 1))
.chain([first_map.object, first_map.root].map(|block| self.chunks.chunk_of(block)))
.collect();
touched.sort_unstable();
touched.dedup();
let first_bitmaps: Vec<ChunkBitmap> = touched
.into_iter()
.map(|chunk| ChunkBitmap {
chunk,
block: pool.take(),
})
.collect();
let first_pool_end = pool.next;
let first = Checkpoint {
xid: FIRST_XID,
map: desc,
superblock: desc + 1,
space_manager: data,
reaper: data + manager_blocks,
queues: None,
object_map: first_map,
volumes: Vec::new(),
cab_blocks: cab_blocks.clone(),
cib_blocks: cib_blocks.clone(),
bitmaps: first_bitmaps.clone(),
pool_bitmap_slots: (0..self.pool_bitmaps).collect(),
freed_pool: Vec::new(),
freed_main: Vec::new(),
content: Vec::new(),
};
let allocated = places
.volumes
.iter()
.flat_map(VolumePlace::blocks)
.chain([places.second_map.object, places.second_map.root])
.map(|start| BlockRange { start, count: 1 })
.chain(content.iter().copied());
let chunk_count = to_index(self.chunks.chunk_count);
let mut seen = vec![false; chunk_count];
let mut dirty: Vec<u64> = Vec::new();
for run in allocated {
let last = self.chunks.chunk_of(run.start + run.count - 1);
for chunk in self.chunks.chunk_of(run.start)..=last {
if !std::mem::replace(&mut seen[to_index(chunk)], true) {
dirty.push(chunk);
}
}
}
let per_cib = self.chunks.chunks_per_cib;
let mut freed = Vec::new();
let mut cab_done = vec![false; to_index(self.chunks.cab_count)];
let mut cib_done = vec![false; cibs];
let mut bitmap_of: Vec<Option<usize>> = vec![None; chunk_count];
let mut bitmaps = first_bitmaps;
for (i, bitmap) in bitmaps.iter().enumerate() {
bitmap_of[to_index(bitmap.chunk)] = Some(i);
}
for chunk in dirty {
let cib = chunk / per_cib;
if self.chunks.cab_count > 0 {
let cab = cib / self.chunks.cibs_per_cab;
let at = to_index(cab);
if !std::mem::replace(&mut cab_done[at], true) {
freed.push(cab_blocks[at]);
cab_blocks[at] = pool.take();
}
}
let at = to_index(cib);
if !std::mem::replace(&mut cib_done[at], true) {
freed.push(cib_blocks[at]);
cib_blocks[at] = pool.take();
}
match bitmap_of[to_index(chunk)] {
Some(i) => {
freed.push(bitmaps[i].block);
bitmaps[i].block = pool.take();
}
None => bitmaps.push(ChunkBitmap {
chunk,
block: pool.take(),
}),
}
}
bitmaps.sort_unstable_by_key(|bitmap| bitmap.chunk);
let per_bitmap = self.chunks.blocks_per_chunk;
let first_bitmap = (first_pool_end - self.pool.start) / per_bitmap;
let last_bitmap = (pool.next - 1 - self.pool.start) / per_bitmap;
let mut slots: Vec<u32> = (0..self.pool_bitmaps).collect();
for (slot, bitmap) in (self.pool_bitmaps..).zip(first_bitmap..=last_bitmap) {
slots[to_index(bitmap)] = slot;
}
let second_manager = data + manager_blocks + 1;
let reaper = second_manager + manager_blocks;
let second = Checkpoint {
xid: SECOND_XID,
map: desc + 2,
superblock: desc + 3,
space_manager: second_manager,
reaper,
queues: Some(QueueRoots {
pool: reaper + 1,
main: reaper + 2,
}),
object_map: places.second_map,
volumes: places.volumes.clone(),
cab_blocks,
cib_blocks,
bitmaps,
pool_bitmap_slots: slots,
freed_pool: freed
.into_iter()
.map(|start| BlockRange { start, count: 1 })
.collect(),
freed_main: vec![BlockRange {
start: first_map.object,
count: 2,
}],
content: content.to_vec(),
};
ApfsLayout {
block_size: self.block_size,
block_count: self.block_count,
max_volumes: self.max_volumes,
descriptor_area: self.descriptor_area,
data_area: self.data_area,
chunks: self.chunks,
space_manager: self.manager,
pool_bitmap_area: self.pool_bitmap_area,
pool_bitmaps: self.pool_bitmaps,
pool: self.pool,
queue_node_limits: self.limits,
ephemeral_min_blocks: self.ephemeral_min_blocks,
checkpoints: [first, second],
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
struct Places {
first_map: MapPlace,
volumes: Vec<VolumePlace>,
second_map: MapPlace,
}
impl Places {
fn of(sizing: &Sizing, volumes: u32) -> Self {
let volumes = u64::from(volumes);
let map = |at: u64| MapPlace {
object: at,
root: at + 1,
};
let volume = |map_at: u64, objects_at: u64| VolumePlace {
object_map: map(map_at),
extent_ref_tree: objects_at,
snapshot_tree: objects_at + 1,
root_tree: objects_at + 2,
superblock: objects_at + 3,
};
let places = if sizing.block_count <= LAST_CONTIGUOUS_BLOCK_COUNT {
let start = sizing.pool_end();
Self {
first_map: map(start),
volumes: (0..volumes)
.map(|i| volume(start + 2 + 6 * i, start + 4 + 6 * i))
.collect(),
second_map: map(start + 2 + 6 * volumes),
}
} else {
let (objects, maps) = far_placement(sizing.block_count, sizing.block_size);
Self {
first_map: map(maps),
volumes: (0..volumes)
.map(|i| volume(maps + 2 + 2 * i, objects + 4 * i))
.collect(),
second_map: map(maps + 2 + 2 * volumes),
}
};
let pool_end = sizing.pool_end();
let blocks = places
.volumes
.iter()
.flat_map(VolumePlace::blocks)
.chain([places.first_map.object, places.first_map.root])
.chain([places.second_map.object, places.second_map.root]);
for block in blocks {
assert!(
(pool_end..sizing.block_count).contains(&block),
"block {block} is outside the main space of a {}-block container",
sizing.block_count
);
}
places
}
}
fn far_placement(block_count: u64, block_size: u32) -> (u64, u64) {
const SCALE: u64 = 1280;
let units = block_count * u64::from(block_size) / 4096;
let span = |from: u64, to: u64| units.min(to).saturating_sub(from);
let piecewise = 65_536 * SCALE
+ span(1 << 22, 1 << 24) * (SCALE / 64)
+ span(1 << 24, 1 << 25) * (SCALE / 80)
+ span(1 << 25, 1 << 26) * (SCALE / 256)
+ units.saturating_sub(1 << 26) * (SCALE / 320);
let eighth = block_count * (SCALE / 8);
let (x, below_whole) = if eighth < piecewise {
(eighth, false)
} else {
(piecewise, units > 1 << 26)
};
let gap = (x / (8 * SCALE)).min((1 << 27) / u64::from(block_size));
if below_whole {
((x - 1) / SCALE, (2 * x - 1) / SCALE - gap)
} else {
(x / SCALE, 2 * x / SCALE - gap)
}
}
struct PoolCursor {
next: u64,
}
impl PoolCursor {
fn take(&mut self) -> u64 {
let block = self.next;
self.next += 1;
block
}
}
pub(crate) fn narrow<T: TryFrom<u64>>(value: u64) -> T {
T::try_from(value)
.unwrap_or_else(|_| panic!("{value} does not fit the field the format records it in"))
}
pub(crate) fn to_index(index: u64) -> usize {
usize::try_from(index).expect("a position in a list held in memory")
}
#[cfg(test)]
mod tests {
use super::*;
const NEWFS: &str = include_str!("fixtures/newfs-placements.txt");
const NEWFS_DIGESTS: &str = include_str!("fixtures/newfs-digests.txt");
const CONTAINERS: u64 = 1168;
const RECORDS: usize = 212;
const DIGEST_CONTAINERS: u64 = 6340;
const DIGESTS: usize = 1582;
fn runs(blocks: impl IntoIterator<Item = u64>) -> String {
let mut out: Vec<(u64, u64)> = Vec::new();
for block in blocks {
match out.last_mut() {
Some((start, count)) if *start + *count == block => *count += 1,
_ => out.push((block, 1)),
}
}
if out.is_empty() {
return "-".to_string();
}
let parts: Vec<String> = out.iter().map(|(s, n)| format!("{s}+{n}")).collect();
parts.join(",")
}
fn freed(xid: u64, frees: &[BlockRange]) -> String {
let mut blocks: Vec<u64> = frees
.iter()
.flat_map(|run| run.start..run.start + run.count)
.collect();
blocks.sort_unstable();
let mut runs: Vec<(u64, u64)> = Vec::new();
for block in blocks {
match runs.last_mut() {
Some((start, count)) if *start + *count == block => *count += 1,
_ => runs.push((block, 1)),
}
}
if runs.is_empty() {
return "-".to_string();
}
let parts: Vec<String> = runs
.iter()
.map(|(start, count)| format!("{xid}:{start}+{count}"))
.collect();
parts.join(",")
}
fn listing(layout: &ApfsLayout) -> Vec<String> {
let c = &layout.chunks;
let m = &layout.space_manager;
let mut out = vec![
format!("blocks {} {}", layout.block_count, layout.block_size),
format!(
"descriptor {} {}",
layout.descriptor_area.start, layout.descriptor_area.count
),
format!("data {} {}", layout.data_area.start, layout.data_area.count),
format!(
"chunks {} {} {} {} {} {}",
c.blocks_per_chunk,
c.chunks_per_cib,
c.cibs_per_cab,
c.chunk_count,
c.cib_count,
c.cab_count
),
format!(
"manager {} {} {} {} {} {}",
m.blocks,
m.address_offset,
m.second_address_offset,
m.bitmap_xid_offset,
m.bitmap_slot_offset,
m.bitmap_free_list_offset
),
format!(
"pool-bitmaps {} {} {}",
layout.pool_bitmaps, layout.pool_bitmap_area.start, layout.pool_bitmap_area.count
),
format!("pool {} {}", layout.pool.start, layout.pool.count),
format!(
"queue-limits {} {}",
layout.queue_node_limits.pool, layout.queue_node_limits.main
),
format!("max-volumes {}", layout.max_volumes),
format!("ephemeral-min {}", layout.ephemeral_min_blocks),
];
for cp in &layout.checkpoints {
out.push(format!("tx {}", cp.xid));
out.push(format!(" descriptor {} {}", cp.map, cp.superblock));
out.push(format!(" manager {}", cp.space_manager));
out.push(format!(" reaper {}", cp.reaper));
if let Some(q) = cp.queues {
out.push(format!(" queues {} {}", q.pool, q.main));
}
out.push(format!(
" object-map {} {}",
cp.object_map.object, cp.object_map.root
));
for (slot, v) in cp.volumes.iter().enumerate() {
out.push(format!(
" volume {slot} {} {} {} {} {} {}",
v.object_map.object,
v.object_map.root,
v.extent_ref_tree,
v.snapshot_tree,
v.root_tree,
v.superblock
));
}
out.push(format!(
" address-blocks {}",
runs(cp.cab_blocks.iter().copied())
));
out.push(format!(
" info-blocks {}",
runs(cp.cib_blocks.iter().copied())
));
let bitmaps: Vec<String> = cp
.bitmaps
.iter()
.map(|b| format!("{}:{}", b.chunk, b.block))
.collect();
out.push(format!(
" bitmaps {}",
if bitmaps.is_empty() {
"-".to_string()
} else {
bitmaps.join(",")
}
));
out.push(format!(
" pool-bitmap-slots {}",
runs(cp.pool_bitmap_slots.iter().map(|&s| u64::from(s)))
));
if cp.queues.is_some() {
out.push(format!(" freed-pool {}", freed(cp.xid, &cp.freed_pool)));
out.push(format!(" freed-main {}", freed(cp.xid, &cp.freed_main)));
}
}
out
}
struct Record<'a> {
hows: Vec<&'a str>,
containers: u64,
lines: Vec<&'a str>,
}
fn records() -> Vec<Record<'static>> {
let mut out: Vec<Record<'static>> = Vec::new();
for line in NEWFS.lines() {
if line.starts_with('#') {
continue;
}
if let Some(head) = line.strip_prefix("@ ") {
let mut words = head.split(' ');
let hows = words
.next()
.expect("a record names how")
.split('+')
.collect();
let containers = words
.next()
.and_then(|n| n.parse().ok())
.expect("a record counts its containers");
out.push(Record {
hows,
containers,
lines: Vec::new(),
});
} else {
out.last_mut()
.expect("a listing follows a record's head")
.lines
.push(line);
}
}
out
}
fn numbers(line: &str, after: &str) -> Vec<u64> {
line.strip_prefix(after)
.unwrap_or_else(|| panic!("{line:?} begins {after:?}"))
.split(' ')
.map(|n| n.parse().expect("a number"))
.collect()
}
fn sizing(record: &Record<'_>) -> Sizing {
let head = numbers(record.lines[0], "blocks ");
Sizing::of(head[0], u32::try_from(head[1]).expect("a block size"))
}
fn measured_places(record: &Record<'_>) -> Places {
let at = |prefix: &str, nth: usize| -> Vec<u64> {
let line = record
.lines
.iter()
.filter(|l| l.starts_with(prefix))
.nth(nth)
.unwrap_or_else(|| panic!("the listing has {prefix:?}"));
numbers(line, prefix)
};
let first = at(" object-map ", 0);
let second = at(" object-map ", 1);
let v = at(" volume 0 ", 0);
Places {
first_map: MapPlace {
object: first[0],
root: first[1],
},
volumes: vec![VolumePlace {
object_map: MapPlace {
object: v[0],
root: v[1],
},
extent_ref_tree: v[2],
snapshot_tree: v[3],
root_tree: v[4],
superblock: v[5],
}],
second_map: MapPlace {
object: second[0],
root: second[1],
},
}
}
fn assert_same(label: &str, planned: &[String], measured: &[&str]) {
for (i, (p, m)) in planned.iter().zip(measured).enumerate() {
assert_eq!(p, m, "{label}: line {i} differs");
}
assert_eq!(planned.len(), measured.len(), "{label}: listing length");
}
#[test]
fn every_object_is_planned_where_newfs_apfs_placed_it() {
let records = records();
assert_eq!(records.len(), RECORDS, "the fixture's records");
assert_eq!(
records.iter().map(|r| r.containers).sum::<u64>(),
CONTAINERS,
"the containers the fixture holds"
);
let mut far_devices = 0;
for record in &records {
let sizing = sizing(record);
let label = format!("{} ({})", record.lines[0], record.hows.join("+"));
let planned = listing(&sizing.layout(&Places::of(&sizing, 1), &[]));
if record.hows.contains(&"file") {
assert_same(&label, &planned, &record.lines);
} else if record.hows == ["container-only"] {
let first = planned
.iter()
.position(|l| l == "tx 2")
.expect("a plan has two transactions");
assert_same(&label, &planned[..first], &record.lines);
} else {
assert_eq!(record.hows, ["device"], "{label}");
assert!(
sizing.block_count > LAST_CONTIGUOUS_BLOCK_COUNT,
"{label}: an attached disk diverges only past the contiguous limit"
);
far_devices += 1;
let second = planned
.iter()
.position(|l| l == "tx 2")
.expect("a plan has two transactions");
assert_same(&label, &planned[..second], &record.lines[..second]);
assert_ne!(
planned[second..],
record.lines[second..],
"{label}: the attached disk's placement is its own"
);
let placed = listing(&sizing.layout(&measured_places(record), &[]));
assert_same(&label, &placed, &record.lines);
}
}
assert_eq!(
far_devices, 12,
"the attached disks past the contiguous limit"
);
}
#[test]
fn every_other_size_measured_is_planned_as_newfs_apfs_laid_it_out() {
let mut digests = 0;
let mut containers = 0;
for line in NEWFS_DIGESTS.lines().filter(|l| !l.starts_with('#')) {
let words: Vec<&str> = line.split(' ').collect();
let number = |i: usize| -> u64 { words[i].parse().expect("a number") };
let sizing = Sizing::of(number(0), u32::try_from(number(1)).expect("a block size"));
let measured = u32::from_str_radix(words[2], 16).expect("a checksum");
let planned = listing(&sizing.layout(&Places::of(&sizing, 1), &[])).join("\n");
assert_eq!(
!crate::crc32c(!0, planned.as_bytes()),
measured,
"{} blocks of {}: the plan's listing is not newfs_apfs's; the plan's is\n{planned}",
words[0],
words[1]
);
digests += 1;
containers += number(3);
}
assert_eq!(digests, DIGESTS, "the fixture's listings");
assert_eq!(
containers, DIGEST_CONTAINERS,
"the containers the fixture holds"
);
}
#[test]
fn a_container_below_the_floor_or_above_the_ceiling_is_refused() {
let below = PlanRequest::new(MIN_BLOCK_COUNT * 4096 - 1);
assert_eq!(
plan_layout(&below),
Err(GeometryError::ContainerTooSmall {
bytes: MIN_BLOCK_COUNT * 4096 - 1,
block_size: 4096,
block_count: MIN_BLOCK_COUNT - 1,
})
);
assert!(plan_layout(&PlanRequest::new(MIN_BLOCK_COUNT * 4096)).is_ok());
let large_blocks = PlanRequest::new(4 << 20).block_size(BlockSize::K64);
assert!(matches!(
plan_layout(&large_blocks),
Err(GeometryError::ContainerTooSmall {
block_count: 64,
..
})
));
assert!(plan_layout(&PlanRequest::new(64 << 20).block_size(BlockSize::K64)).is_ok());
assert!(plan_layout(&PlanRequest::new(MAX_CONTAINER_BYTES)).is_ok());
assert_eq!(
plan_layout(&PlanRequest::new(MAX_CONTAINER_BYTES + 4096)),
Err(GeometryError::ContainerTooLarge {
bytes: MAX_CONTAINER_BYTES + 4096
})
);
assert!(plan_layout(&PlanRequest::new(MAX_CONTAINER_BYTES + 4095)).is_ok());
}
#[test]
fn a_container_diskutil_resized_is_sized_as_one_formatted_at_its_new_size() {
let resized: [(u64, u16, u16, u64, u64); 4] = [
(244_140, 1, 54, 27, 744),
(488_281, 1, 215, 48, 1_900),
(488_282, 1, 215, 48, 1_900),
(16_726_006, 3, 512, 1_548, 27_672),
];
for (block_count, pool, main, pool_blocks, data_blocks) in resized {
let layout = layout_of(block_count, 4096, 1);
assert_eq!(
layout.queue_node_limits,
QueueNodeLimits { pool, main },
"{block_count}"
);
assert_eq!(
(layout.pool.count, layout.data_area.count),
(pool_blocks, data_blocks),
"{block_count}"
);
}
}
#[test]
fn a_container_holds_one_volume_per_512_mib_up_to_100() {
assert_eq!(
plan_layout(&PlanRequest::new(64 << 20).volumes(0)),
Err(GeometryError::NoVolumes)
);
assert_eq!(
plan_layout(&PlanRequest::new(512 << 20).volumes(2)),
Err(GeometryError::TooManyVolumes {
bytes: 512 << 20,
volumes: 2,
max_volumes: 1,
})
);
let two = plan_layout(&PlanRequest::new((512 << 20) + 4096).volumes(2)).expect("two fit");
assert_eq!(two.max_volumes, 2);
assert_eq!(two.newest().volumes.len(), 2);
let full = plan_layout(&PlanRequest::new(1 << 40).volumes(100)).expect("a hundred fit");
assert_eq!(full.max_volumes, 100);
assert!(matches!(
plan_layout(&PlanRequest::new(1 << 40).volumes(101)),
Err(GeometryError::TooManyVolumes {
max_volumes: 100,
..
})
));
}
fn placed_blocks(layout: &ApfsLayout) -> Vec<(u64, &'static str, String)> {
let mut out = Vec::new();
let mut put = |block: u64, area: &'static str, what: String| out.push((block, area, what));
put(0, "zero", "block zero".into());
for cp in &layout.checkpoints {
let x = cp.xid;
put(cp.map, "descriptor", format!("map {x}"));
put(cp.superblock, "descriptor", format!("superblock {x}"));
for i in 0..u64::from(layout.space_manager.blocks) {
put(cp.space_manager + i, "data", format!("space manager {x}"));
}
put(cp.reaper, "data", format!("reaper {x}"));
if let Some(q) = cp.queues {
put(q.pool, "data", format!("pool queue {x}"));
put(q.main, "data", format!("main queue {x}"));
}
put(cp.object_map.object, "main", format!("object map {x}"));
put(cp.object_map.root, "main", format!("object map root {x}"));
for (slot, v) in cp.volumes.iter().enumerate() {
for (i, block) in v.blocks().into_iter().enumerate() {
put(block, "main", format!("volume {slot} object {i} {x}"));
}
}
for (bitmap, slot) in cp.pool_bitmap_slots.iter().enumerate() {
let block = layout.pool_bitmap_area.start + u64::from(*slot);
put(
block,
"pool bitmaps",
format!("pool bitmap {bitmap} in slot {slot}"),
);
}
for (i, &b) in cp.cab_blocks.iter().enumerate() {
put(b, "pool", format!("address block {i} at {b}"));
}
for (i, &b) in cp.cib_blocks.iter().enumerate() {
put(b, "pool", format!("chunk-info block {i} at {b}"));
}
for b in &cp.bitmaps {
put(
b.block,
"pool",
format!("bitmap of chunk {} at {}", b.chunk, b.block),
);
}
}
out
}
#[test]
fn every_plan_keeps_each_object_in_its_area_and_apart_from_every_other() {
let mut sizes: Vec<u64> = Vec::new();
let mut bytes: u64 = 4 << 20;
while bytes <= MAX_CONTAINER_BYTES {
sizes.push(bytes);
sizes.push(bytes / 7 * 5);
bytes = bytes * 3 / 2;
}
sizes.push(MAX_CONTAINER_BYTES);
let mut planned = 0;
for block in [
BlockSize::K4,
BlockSize::K8,
BlockSize::K16,
BlockSize::K32,
BlockSize::K64,
] {
for &size in &sizes {
let Ok(one) = plan_layout(&PlanRequest::new(size).block_size(block)) else {
continue;
};
for volumes in [1, one.max_volumes] {
let layout =
plan_layout(&PlanRequest::new(size).block_size(block).volumes(volumes))
.expect("as many volumes as there are slots");
check_apart(&layout);
planned += 1;
}
}
}
assert!(planned > 600, "{planned} plans checked");
}
fn check_apart(layout: &ApfsLayout) {
let label = format!("{} blocks of {}", layout.block_count, layout.block_size);
let mut seen: std::collections::BTreeMap<u64, String> = std::collections::BTreeMap::new();
for (block, expected, what) in placed_blocks(layout) {
assert!(block < layout.block_count, "{label}: {what} at {block}");
let area = if block == 0 {
"zero"
} else if block < layout.data_area.start {
"descriptor"
} else if block < layout.pool_bitmap_area.start {
"data"
} else if block < layout.pool.start {
"pool bitmaps"
} else if block < layout.pool.start + layout.pool.count {
"pool"
} else {
"main"
};
assert_eq!(area, expected, "{label}: {what} at {block}");
match seen.get(&block) {
Some(before) => assert_eq!(
before, &what,
"{label}: {before} and {what} are both at {block}"
),
None => {
seen.insert(block, what);
}
}
}
}
#[test]
fn a_hundred_volumes_take_the_places_one_does_one_after_another() {
for size in [64u64 << 30, 4 << 40] {
let one = plan_layout(&PlanRequest::new(size)).expect("one volume");
let many = plan_layout(&PlanRequest::new(size).volumes(100)).expect("a hundred");
assert_eq!(one.newest().volumes[0], many.newest().volumes[0]);
assert_eq!(one.checkpoints[0], many.checkpoints[0]);
let volumes = &many.newest().volumes;
for pair in volumes.windows(2) {
assert!(pair[0].object_map.object < pair[1].object_map.object);
assert!(pair[0].superblock < pair[1].extent_ref_tree);
}
assert!(many.newest().object_map.object > volumes[99].object_map.root);
}
}
#[test]
fn the_chunk_geometry_lists_address_blocks_past_what_one_holds() {
let fits = ChunkGeometry::of(507 * 126 * 32768, 4096);
assert_eq!(
(fits.cib_count, fits.cab_count, fits.listed()),
(507, 0, 507)
);
let over = ChunkGeometry::of(507 * 126 * 32768 + 1, 4096);
assert_eq!((over.cib_count, over.cab_count, over.listed()), (508, 2, 2));
let large = ChunkGeometry::of(1 << 20, 65536);
assert_eq!(
(
large.blocks_per_chunk,
large.chunks_per_cib,
large.cibs_per_cab
),
(524_288, 2046, 8187)
);
let huge = ChunkGeometry::of(u64::MAX, 4096);
assert_eq!(huge.chunk_count, u64::MAX.div_ceil(32768));
assert!(huge.cib_count > u64::from(u32::MAX));
}
}