use crate::geometry::{BlockRange, Layout};
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum AllocError {
#[error("out of space: requested {requested} blocks, {available} free")]
#[non_exhaustive]
OutOfSpace {
requested: u64,
available: u64,
},
}
#[derive(Clone, Debug)]
pub struct Allocator {
bits: Vec<u8>,
total_blocks: u64,
blocks_per_group: u32,
bytes_per_group: usize,
first_data_block: u64,
cursor: u64,
}
impl Allocator {
#[must_use]
pub fn new(layout: &Layout) -> Self {
let bytes_per_group = (layout.blocks_per_group / 8) as usize;
let capacity_bits = u64::from(layout.group_count) * u64::from(layout.blocks_per_group);
let mut alloc = Self {
bits: vec![0u8; (capacity_bits / 8) as usize],
total_blocks: layout.total_blocks,
blocks_per_group: layout.blocks_per_group,
bytes_per_group,
first_data_block: u64::from(layout.first_data_block),
cursor: u64::from(layout.first_data_block),
};
let last_described = u64::from(layout.first_data_block) + capacity_bits;
for b in layout.total_blocks..last_described {
alloc.set(b);
}
for r in layout.metadata_regions() {
alloc.mark_used(r);
}
alloc
}
pub fn mark_used(&mut self, range: BlockRange) {
for b in range.start..range.end() {
self.set(b);
}
}
#[must_use]
pub fn is_used(&self, b: u64) -> bool {
self.bit(b)
.is_none_or(|i| self.bits[(i / 8) as usize] & (1 << (i % 8)) != 0)
}
pub fn allocate(&mut self, count: u64) -> Result<Vec<BlockRange>, AllocError> {
if count == 0 {
return Ok(Vec::new());
}
let mut ranges = Vec::new();
let mut remaining = count;
let mut i = self.cursor;
let cap = self.total_blocks;
while remaining > 0 {
while i < cap && self.is_used(i) {
i += 1;
}
if i >= cap {
return Err(AllocError::OutOfSpace {
requested: count,
available: count - remaining,
});
}
let start = i;
while i < cap && !self.is_used(i) && (i - start) < remaining {
i += 1;
}
let len = i - start;
ranges.push(BlockRange { start, len });
remaining -= len;
}
for r in &ranges {
self.mark_used(*r);
}
self.cursor = i;
Ok(ranges)
}
#[must_use]
pub fn allocate_contiguous(&mut self, count: u64) -> Option<BlockRange> {
if count == 0 {
return Some(BlockRange {
start: self.first_data_block,
len: 0,
});
}
let cap = self.total_blocks;
let mut i = self.first_data_block;
while i < cap {
while i < cap && self.is_used(i) {
i += 1;
}
let start = i;
while i < cap && !self.is_used(i) {
i += 1;
}
if i - start >= count {
let range = BlockRange { start, len: count };
self.mark_used(range);
return Some(range);
}
}
None
}
pub fn allocate_one(&mut self) -> Result<u64, AllocError> {
Ok(self.allocate(1)?[0].start)
}
#[must_use]
pub fn group_bitmap(&self, index: u32) -> Option<&[u8]> {
let start = index as usize * self.bytes_per_group;
self.bits.get(start..start + self.bytes_per_group)
}
#[must_use]
pub fn free_count(&self) -> u64 {
let positions = self.total_blocks - self.first_data_block;
positions - used_in_prefix(&self.bits, positions)
}
#[must_use]
pub fn group_free_count(&self, index: u32) -> u32 {
let start = self.first_data_block + u64::from(index) * u64::from(self.blocks_per_group);
let end = (start + u64::from(self.blocks_per_group)).min(self.total_blocks);
let positions = end.saturating_sub(start);
let Some(bytes) = self.group_bitmap(index) else {
return 0;
};
(positions - used_in_prefix(bytes, positions)) as u32
}
fn bit(&self, b: u64) -> Option<u64> {
let i = b.checked_sub(self.first_data_block)?;
((i / 8) < self.bits.len() as u64).then_some(i)
}
fn set(&mut self, b: u64) {
if let Some(i) = self.bit(b) {
self.bits[(i / 8) as usize] |= 1 << (i % 8);
}
}
#[cfg(test)]
fn clear(&mut self, b: u64) {
if let Some(i) = self.bit(b) {
self.bits[(i / 8) as usize] &= !(1 << (i % 8));
}
}
}
fn used_in_prefix(bits: &[u8], n: u64) -> u64 {
let whole = (n / 8) as usize;
let mut used: u64 = bits[..whole]
.iter()
.map(|b| u64::from(b.count_ones()))
.sum();
let rem = (n % 8) as u32;
if rem != 0 {
let mask = (1u8 << rem) - 1;
used += u64::from((bits[whole] & mask).count_ones());
}
used
}
#[cfg(test)]
mod tests {
use super::*;
use crate::feature::FeatureSet;
use crate::geometry::{GrowReservation, PlanRequest, plan_layout};
const MIB: u64 = 1024 * 1024;
const GROW_32G: u64 = 32 * 1024 * MIB;
fn layout(mib: u64) -> Layout {
plan_layout(
&PlanRequest::new(mib * MIB, FeatureSet::default())
.grow(GrowReservation::UpTo(GROW_32G)),
)
.unwrap()
}
#[test]
fn the_bitmap_is_indexed_from_the_first_data_block() {
let fs = FeatureSet {
block_size: 1024,
..FeatureSet::default()
};
let l = plan_layout(&PlanRequest::new(64 * MIB, fs).grow(GrowReservation::UpTo(GROW_32G)))
.expect("plan");
assert_eq!(l.first_data_block, 1);
let alloc = Allocator::new(&l);
assert!(alloc.is_used(1), "the superblock is block 1");
assert_eq!(
alloc.group_bitmap(0).expect("group 0")[0] & 1,
1,
"and it is bit 0 of group 0"
);
let g1 = l.groups[1].start_block;
assert!(l.groups[1].has_super);
assert!(alloc.is_used(g1));
assert_eq!(alloc.group_bitmap(1).expect("group 1")[0] & 1, 1);
}
#[test]
fn metadata_is_marked_used_from_the_layout() {
let l = layout(64);
let a = Allocator::new(&l);
for b in 0..=4 {
assert!(a.is_used(b), "block {b} (super/gdt/rgdt) should be used");
}
assert!(a.is_used(5));
assert!(a.is_used(21));
assert!(a.is_used(37));
assert!(a.is_used(1060));
assert!(!a.is_used(1061));
assert!(!a.is_used(6), "unused block-bitmap slot is free");
assert!(!a.is_used(20), "unused inode-bitmap slot is free");
assert!(!a.is_used(36));
}
#[test]
fn allocate_returns_contiguous_run_when_possible() {
let l = layout(64);
let mut a = Allocator::new(&l);
let ranges = a.allocate(4).unwrap();
assert_eq!(ranges.len(), 1, "free space is contiguous here");
assert_eq!(ranges[0].len, 4);
for b in ranges[0].start..ranges[0].end() {
assert!(a.is_used(b));
}
}
#[test]
fn allocate_spans_multiple_ranges_across_a_reserved_window() {
let l = layout(64);
let mut a = Allocator::new(&l);
for b in 0..l.total_blocks {
a.set(b);
}
for b in [100u64, 101, 103, 104] {
a.clear(b);
}
a.cursor = 100;
let ranges = a.allocate(4).unwrap();
assert_eq!(
ranges,
vec![
BlockRange { start: 100, len: 2 },
BlockRange { start: 103, len: 2 },
]
);
}
#[test]
fn allocate_contiguous_takes_one_run_and_skips_short_gaps() {
let l = layout(64);
let mut a = Allocator::new(&l);
for b in 0..l.total_blocks {
a.set(b);
}
for b in [50u64, 51] {
a.clear(b);
}
for b in 200..400 {
a.clear(b);
}
let range = a.allocate_contiguous(100).expect("a 100-block run is free");
assert_eq!(
range,
BlockRange {
start: 200,
len: 100
}
);
for b in range.start..range.end() {
assert!(a.is_used(b));
}
assert!(!a.is_used(50));
}
#[test]
fn allocate_contiguous_returns_none_when_no_run_is_long_enough() {
let l = layout(64);
let mut a = Allocator::new(&l);
for b in 0..l.total_blocks {
a.set(b);
}
for b in [10u64, 11, 20, 21, 22] {
a.clear(b);
}
assert_eq!(a.allocate_contiguous(4), None);
}
#[test]
fn out_of_space_leaves_the_bitmap_untouched() {
let l = layout(64);
let mut a = Allocator::new(&l);
let free_before = a.free_count();
let err = a.allocate(free_before + 1).unwrap_err();
assert!(matches!(err, AllocError::OutOfSpace { .. }));
assert_eq!(a.free_count(), free_before, "no partial allocation");
}
#[test]
fn group_bitmap_slices_align_to_groups() {
let l = layout(512);
let a = Allocator::new(&l);
let g0 = a.group_bitmap(0).expect("group 0");
assert_eq!(g0.len(), (l.blocks_per_group / 8) as usize);
assert_eq!(g0[0], 0b1111_1111);
}
#[test]
fn padding_tail_of_final_group_is_marked_used() {
let l = layout(200);
let a = Allocator::new(&l);
let last_start = u64::from(l.blocks_per_group);
assert!(a.is_used(last_start + 18432), "first padding block");
assert!(a.is_used(last_start + 32767), "last padding block");
assert!(a.free_count() < l.total_blocks);
}
#[test]
fn free_counts_are_consistent_between_whole_and_per_group() {
let l = layout(512);
let a = Allocator::new(&l);
let per_group: u64 = (0..l.group_count)
.map(|g| u64::from(a.group_free_count(g)))
.sum();
assert_eq!(per_group, a.free_count());
}
#[test]
fn popcount_free_count_matches_a_block_by_block_scan() {
for mib in [64u64, 512] {
let l = layout(mib);
let mut a = Allocator::new(&l);
a.allocate(1000).expect("room for a scattered run");
let scan = |lo: u64, hi: u64| (lo..hi).filter(|&b| !a.is_used(b)).count() as u64;
let fdb = u64::from(l.first_data_block);
assert_eq!(
a.free_count(),
scan(fdb, l.total_blocks),
"{mib} MiB whole-fs"
);
for g in 0..l.group_count {
let start = fdb + u64::from(g) * u64::from(l.blocks_per_group);
let end = (start + u64::from(l.blocks_per_group)).min(l.total_blocks);
assert_eq!(
u64::from(a.group_free_count(g)),
scan(start, end),
"{mib} MiB group {g}"
);
}
}
}
}