use std::collections::{BTreeMap, BTreeSet};
use std::io;
const MAX_SEGMENT_VERSION: u32 = 0x0fff_ffff;
const MAX_LARGE_BLOCK_ID: u64 = (1_u64 << 60) - 1;
const MAX_NEXT_SEGMENT_VERSION: u32 = MAX_SEGMENT_VERSION + 1;
const SEGMENT_CAPACITY_BYTES: u64 = 256 * 1024 * 1024;
const SLOT_SIZES: [u64; 15] = [
4 * 1024,
6 * 1024,
8 * 1024,
12 * 1024,
16 * 1024,
24 * 1024,
32 * 1024,
48 * 1024,
64 * 1024,
96 * 1024,
128 * 1024,
192 * 1024,
256 * 1024,
384 * 1024,
512 * 1024,
];
#[derive(Clone, Copy, Eq, PartialEq)]
pub(crate) enum SegmentState {
Active,
Sealed,
}
#[derive(Clone)]
pub(crate) struct SegmentRecord {
pub(crate) level: u8,
pub(crate) state: SegmentState,
pub(crate) version: u32,
pub(crate) frontier: u64,
pub(crate) live_count: u64,
pub(crate) bitmap: Vec<u64>,
}
#[derive(Clone)]
pub(crate) struct State {
pub(crate) device_id: [u8; 16],
pub(crate) next_segment_version: u32,
pub(crate) next_large_block_id: u64,
pub(crate) active_versions: [u32; 15],
pub(crate) segments: BTreeMap<(u8, u32), SegmentRecord>,
pub(crate) large_blocks: BTreeMap<u64, u64>,
pub(crate) roots: BTreeSet<u64>,
pub(crate) bindings: BTreeMap<String, u64>,
}
pub(crate) struct Delta {
pub(crate) next_segment_version: u32,
pub(crate) next_large_block_id: u64,
pub(crate) segment_upserts: Vec<SegmentRecord>,
pub(crate) segment_removes: Vec<(u8, u32)>,
pub(crate) large_adds: Vec<(u64, u64)>,
pub(crate) large_removes: Vec<u64>,
pub(crate) root_adds: Vec<u64>,
pub(crate) root_removes: Vec<u64>,
pub(crate) binding_removes: Vec<String>,
pub(crate) binding_upserts: Vec<(String, u64)>,
}
impl State {
pub(crate) fn initial(device_id: [u8; 16]) -> Self {
let active_versions = std::array::from_fn(|index| index as u32 + 1);
let segments = (0_u8..=14)
.map(|level| {
let version = u32::from(level) + 1;
(
(level, version),
SegmentRecord {
level,
state: SegmentState::Active,
version,
frontier: 0,
live_count: 0,
bitmap: Vec::new(),
},
)
})
.collect();
Self {
device_id,
next_segment_version: 16,
next_large_block_id: 1,
active_versions,
segments,
large_blocks: BTreeMap::new(),
roots: BTreeSet::new(),
bindings: BTreeMap::new(),
}
}
pub(crate) fn apply(&mut self, delta: Delta) -> io::Result<()> {
if delta.next_segment_version < self.next_segment_version
|| delta.next_large_block_id < self.next_large_block_id
{
return Err(invalid_data("allocation high water mark regressed"));
}
let mut next = self.clone();
next.apply_unchecked(delta)?;
next.validate()?;
*self = next;
Ok(())
}
fn apply_unchecked(&mut self, delta: Delta) -> io::Result<()> {
validate_high_water_marks(delta.next_segment_version, delta.next_large_block_id)?;
reject_overlap(
delta.segment_upserts.iter().map(SegmentRecord::key),
delta.segment_removes.iter().copied(),
"segment",
)?;
reject_overlap(
delta.large_adds.iter().map(|entry| entry.0),
delta.large_removes.iter().copied(),
"large block",
)?;
reject_overlap(
delta.root_adds.iter().copied(),
delta.root_removes.iter().copied(),
"root",
)?;
reject_overlap(
delta.binding_upserts.iter().map(|entry| entry.0.as_str()),
delta.binding_removes.iter().map(String::as_str),
"binding",
)?;
for key in delta.segment_removes {
self.segments.remove(&key);
}
for record in delta.segment_upserts {
if record.state == SegmentState::Active {
self.active_versions[usize::from(record.level)] = record.version;
}
self.segments.insert(record.key(), record);
}
for id in delta.large_removes {
self.large_blocks.remove(&id);
}
for (id, logical_len) in delta.large_adds {
self.large_blocks.insert(id, logical_len);
}
for block in delta.root_removes {
self.roots.remove(&block);
}
self.roots.extend(delta.root_adds);
for name in delta.binding_removes {
self.bindings.remove(&name);
}
for (name, target) in delta.binding_upserts {
self.bindings.insert(name, target);
}
self.next_segment_version = delta.next_segment_version;
self.next_large_block_id = delta.next_large_block_id;
Ok(())
}
pub(crate) fn validate(&self) -> io::Result<()> {
validate_high_water_marks(self.next_segment_version, self.next_large_block_id)?;
for (level, version) in self.active_versions.iter().copied().enumerate() {
validate_segment_key(level as u8, version)?;
let record = self
.segments
.get(&(level as u8, version))
.ok_or_else(|| invalid_data("active segment is missing"))?;
if record.state != SegmentState::Active {
return Err(invalid_data("active version references sealed segment"));
}
}
if self
.segments
.values()
.any(|record| record.version >= self.next_segment_version)
{
return Err(invalid_data(
"next segment version does not exceed every entity version",
));
}
for record in self.segments.values() {
record.validate()?;
if record.state == SegmentState::Active
&& self.active_versions[usize::from(record.level)] != record.version
{
return Err(invalid_data("noncanonical active segment"));
}
}
if self
.large_blocks
.keys()
.any(|id| *id >= self.next_large_block_id)
{
return Err(invalid_data(
"next large block id does not exceed every entity id",
));
}
for (&id, &logical_len) in &self.large_blocks {
if id == 0 || id >= MAX_LARGE_BLOCK_ID || logical_len == 0 {
return Err(invalid_data("invalid large block record"));
}
}
for block in &self.roots {
validate_block_id(*block)?;
}
for (name, target) in &self.bindings {
if name.is_empty() || !self.roots.contains(target) {
return Err(invalid_data("invalid named binding"));
}
validate_block_id(*target)?;
}
Ok(())
}
}
impl SegmentRecord {
pub(crate) fn key(&self) -> (u8, u32) {
(self.level, self.version)
}
pub(crate) fn validate(&self) -> io::Result<()> {
validate_segment_key(self.level, self.version)?;
let max_frontier = SEGMENT_CAPACITY_BYTES / SLOT_SIZES[usize::from(self.level)];
if self.frontier > max_frontier {
return Err(invalid_data("segment frontier exceeds capacity"));
}
let expected_words = self.frontier.div_ceil(64);
if usize::try_from(expected_words).ok() != Some(self.bitmap.len()) {
return Err(invalid_data("bitmap word count does not match frontier"));
}
if self
.bitmap
.iter()
.map(|word| u64::from(word.count_ones()))
.sum::<u64>()
!= self.live_count
|| self.live_count > self.frontier
{
return Err(invalid_data("invalid live count"));
}
if let Some(last) = self.bitmap.last() {
let used = self.frontier % 64;
if used != 0 && *last >> used != 0 {
return Err(invalid_data("bitmap has bits beyond frontier"));
}
}
Ok(())
}
}
fn validate_segment_key(level: u8, version: u32) -> io::Result<()> {
if level > 14 || version == 0 || version > MAX_SEGMENT_VERSION {
Err(invalid_data("invalid segment key"))
} else {
Ok(())
}
}
fn validate_high_water_marks(
next_segment_version: u32,
next_large_block_id: u64,
) -> io::Result<()> {
if next_segment_version == 0
|| next_segment_version > MAX_NEXT_SEGMENT_VERSION
|| next_large_block_id == 0
|| next_large_block_id > MAX_LARGE_BLOCK_ID
{
Err(invalid_data("invalid allocation high water marks"))
} else {
Ok(())
}
}
fn validate_block_id(raw: u64) -> io::Result<()> {
if raw == u64::MAX {
return Err(invalid_data("reserved BlockId"));
}
let level = (raw & 0x0f) as u8;
let high = raw >> 4;
if level == 15 {
if high == 0 || high == MAX_LARGE_BLOCK_ID {
return Err(invalid_data("reserved large BlockId"));
}
} else if high & u64::from(MAX_SEGMENT_VERSION) == 0 {
return Err(invalid_data("ordinary BlockId has zero segment version"));
}
Ok(())
}
fn reject_overlap<T: Ord>(
left: impl IntoIterator<Item = T>,
right: impl IntoIterator<Item = T>,
name: &str,
) -> io::Result<()> {
let left: BTreeSet<T> = left.into_iter().collect();
if right.into_iter().any(|key| left.contains(&key)) {
Err(invalid_data(&format!(
"{name} appears in mutually exclusive groups"
)))
} else {
Ok(())
}
}
fn invalid_data(message: &str) -> io::Error {
io::Error::new(io::ErrorKind::InvalidData, message)
}
#[allow(dead_code)]
pub(super) mod v1 {
use super::invalid_data;
use crate::BlockId;
pub(crate) use crate::{LargeBlockId, RecordSeq, SegmentVersion};
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::io;
const MAX_SEGMENT_VERSION: u32 = 0x0fff_ffff;
const MAX_LARGE_BLOCK_ID: u64 = (1_u64 << 60) - 1;
const MAX_VALID_LARGE_BLOCK_ID: u64 = MAX_LARGE_BLOCK_ID - 1;
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct AllocationRun {
pub(crate) allocated_at: RecordSeq,
pub(crate) len: u32,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct SegmentData {
pub(crate) allocation_runs: Vec<AllocationRun>,
pub(crate) released_at: Vec<RecordSeq>,
}
impl SegmentData {
fn validate(&self, state_record_seq: RecordSeq) -> io::Result<()> {
let mut slots = 0_u32;
let mut previous_allocated_at = None;
for run in &self.allocation_runs {
if run.len == 0
|| run.allocated_at.is_null()
|| run.allocated_at > state_record_seq
|| previous_allocated_at.is_some_and(|previous| run.allocated_at <= previous)
{
return Err(invalid_data("invalid allocation run"));
}
previous_allocated_at = Some(run.allocated_at);
slots = slots
.checked_add(run.len)
.ok_or_else(|| invalid_data("allocation run length overflow"))?;
}
if self.released_at.len() != usize::try_from(slots).unwrap_or(usize::MAX) {
return Err(invalid_data(
"released_at length does not match allocation runs",
));
}
let mut offset = 0_usize;
for run in &self.allocation_runs {
for released in
&self.released_at[offset..offset + usize::try_from(run.len).unwrap_or(0)]
{
if !released.is_null()
&& (*released > state_record_seq || released <= &run.allocated_at)
{
return Err(invalid_data("release sequence is not after allocation"));
}
}
offset += usize::try_from(run.len).unwrap_or(0);
}
Ok(())
}
fn allocate(&mut self, record_seq: RecordSeq, len: u32) -> io::Result<()> {
if len == 0 || record_seq.is_null() {
return Err(invalid_data("invalid allocation"));
}
if let Some(last) = self.allocation_runs.last_mut() {
if last.allocated_at == record_seq {
last.len = last
.len
.checked_add(len)
.ok_or_else(|| invalid_data("allocation run length overflow"))?;
self.released_at.extend(std::iter::repeat_n(
RecordSeq::NULL,
usize::try_from(len)
.map_err(|_| invalid_data("allocation length overflow"))?,
));
return Ok(());
}
}
self.allocation_runs.push(AllocationRun {
allocated_at: record_seq,
len,
});
self.released_at.extend(std::iter::repeat_n(
RecordSeq::NULL,
usize::try_from(len).map_err(|_| invalid_data("allocation length overflow"))?,
));
Ok(())
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct LevelVersions {
pub(crate) min_version: SegmentVersion,
pub(crate) versions: VecDeque<Option<SegmentData>>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct LargeBlockData {
pub(in crate::file) allocated_at: RecordSeq,
pub(in crate::file) released_at: RecordSeq,
pub(in crate::file) logical_len: u64,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct LargeBlocks {
pub(in crate::file) next_id: LargeBlockId,
pub(in crate::file) entries: BTreeMap<LargeBlockId, LargeBlockData>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct V1State {
pub(crate) record_seq: RecordSeq,
pub(crate) levels: [LevelVersions; 15],
pub(in crate::file) large_blocks: LargeBlocks,
pub(crate) roots: BTreeMap<u64, RecordSeq>,
pub(in crate::file) bindings: BTreeMap<String, BlockId>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct BlockRange {
pub(crate) start: u32,
pub(crate) len: u32,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) enum V1StateChange {
CreateActiveSegment {
level: u8,
version: SegmentVersion,
},
AllocateSegmentBlocks {
level: u8,
version: SegmentVersion,
len: u32,
},
ReleaseSegmentBlocks {
level: u8,
version: SegmentVersion,
ranges: Vec<BlockRange>,
},
RemoveSegment {
level: u8,
version: SegmentVersion,
},
AllocateLargeBlock {
id: LargeBlockId,
logical_len: u64,
},
ReleaseLargeBlock {
id: LargeBlockId,
},
RemoveLargeBlock {
id: LargeBlockId,
},
AddRoot {
block: BlockId,
},
RemoveRoot {
block: BlockId,
},
AddBinding {
name: String,
block: BlockId,
},
RemoveBinding {
name: String,
},
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct V1DeltaRecord {
pub(crate) changes: Vec<V1StateChange>,
}
impl V1State {
pub(crate) fn initial() -> Self {
let levels = std::array::from_fn(|_| LevelVersions {
min_version: SegmentVersion(1),
versions: VecDeque::from([Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
})]),
});
Self {
record_seq: RecordSeq(1),
levels,
large_blocks: LargeBlocks {
next_id: LargeBlockId(1),
entries: BTreeMap::new(),
},
roots: BTreeMap::new(),
bindings: BTreeMap::new(),
}
}
pub(crate) fn validate(&self) -> io::Result<()> {
if self.record_seq.is_null() || self.record_seq.0 == 0 {
return Err(invalid_data("invalid state record sequence"));
}
for level in &self.levels {
if SegmentVersion::new(level.min_version.get()).is_err()
|| level.versions.is_empty()
{
return Err(invalid_data("invalid level version window"));
}
let last_version = level
.min_version
.0
.checked_add(
u32::try_from(level.versions.len() - 1)
.map_err(|_| invalid_data("segment version window is too large"))?,
)
.ok_or_else(|| invalid_data("segment version window overflows"))?;
if last_version > MAX_SEGMENT_VERSION {
return Err(invalid_data("segment version window exceeds encoding"));
}
if !matches!(level.versions.back(), Some(Some(_))) {
return Err(invalid_data("level window has no active tail"));
}
for (index, segment) in level.versions.iter().enumerate() {
if let Some(segment) = segment {
segment.validate(self.record_seq)?;
if index + 1 != level.versions.len() && segment.allocation_runs.is_empty() {
return Err(invalid_data("empty sealed segment"));
}
}
}
}
if self.large_blocks.next_id.0 == 0 || self.large_blocks.next_id.0 > MAX_LARGE_BLOCK_ID
{
return Err(invalid_data("invalid next large block id"));
}
for (id, block) in &self.large_blocks.entries {
if LargeBlockId::new(id.get()).is_err()
|| id.0 >= self.large_blocks.next_id.0
|| block.logical_len == 0
|| block.allocated_at.is_null()
|| block.allocated_at > self.record_seq
|| (!block.released_at.is_null() && block.released_at <= block.allocated_at)
|| (!block.released_at.is_null() && block.released_at > self.record_seq)
{
return Err(invalid_data("invalid large block data"));
}
}
for raw in self.roots.keys().copied() {
validate_block_id(raw)?;
}
for published_at in self.roots.values().copied() {
if published_at.is_null() || published_at.0 == 0 || published_at > self.record_seq {
return Err(invalid_data("invalid root publication sequence"));
}
}
for (name, block) in &self.bindings {
if name.is_empty() || !self.roots.contains_key(&block.0) {
return Err(invalid_data("invalid named binding"));
}
validate_block_id(block.0)?;
}
Ok(())
}
pub(crate) fn plan_reclamation(
&self,
protected: &BTreeSet<RecordSeq>,
) -> io::Result<V1DeltaRecord> {
self.validate()?;
if protected.iter().any(|record_seq| {
record_seq.0 == 0 || record_seq.is_null() || *record_seq > self.record_seq
}) {
return Err(invalid_data("invalid protected record sequence"));
}
let mut changes = Vec::new();
for (level, level_data) in self.levels.iter().enumerate() {
for (index, segment) in level_data
.versions
.iter()
.enumerate()
.take(level_data.versions.len() - 1)
{
let Some(segment) = segment else {
continue;
};
if segment
.released_at
.iter()
.any(|released| released.is_null())
{
continue;
}
let mut offset = 0_usize;
let is_protected = segment.allocation_runs.iter().any(|run| {
let end = offset + run.len as usize;
let hit = segment.released_at[offset..end].iter().any(|released_at| {
protected
.range(run.allocated_at..*released_at)
.next()
.is_some()
});
offset = end;
hit
});
if !is_protected {
changes.push(V1StateChange::RemoveSegment {
level: level as u8,
version: SegmentVersion(level_data.min_version.0 + index as u32),
});
}
}
let active = level_data
.versions
.back()
.and_then(Option::as_ref)
.ok_or_else(|| invalid_data("level window has no active tail"))?;
if !active.allocation_runs.is_empty()
&& active
.released_at
.iter()
.all(|released| !released.is_null())
{
let mut offset = 0_usize;
let is_protected = active.allocation_runs.iter().any(|run| {
let end = offset + run.len as usize;
let hit = active.released_at[offset..end].iter().any(|released_at| {
protected
.range(run.allocated_at..*released_at)
.next()
.is_some()
});
offset = end;
hit
});
if !is_protected {
let old_active_version =
level_data
.min_version
.0
.checked_add(u32::try_from(level_data.versions.len() - 1).map_err(
|_| invalid_data("segment version window is too large"),
)?)
.ok_or_else(|| invalid_data("segment version exhausted"))?;
let next_version =
level_data
.min_version
.0
.checked_add(u32::try_from(level_data.versions.len()).map_err(
|_| invalid_data("segment version window is too large"),
)?)
.filter(|version| *version <= MAX_SEGMENT_VERSION)
.ok_or_else(|| invalid_data("segment version exhausted"))?;
changes.push(V1StateChange::CreateActiveSegment {
level: level as u8,
version: SegmentVersion(next_version),
});
changes.push(V1StateChange::RemoveSegment {
level: level as u8,
version: SegmentVersion(old_active_version),
});
}
}
}
for (id, block) in &self.large_blocks.entries {
if !block.released_at.is_null()
&& protected
.range(block.allocated_at..block.released_at)
.next()
.is_none()
{
changes.push(V1StateChange::RemoveLargeBlock { id: *id });
}
}
Ok(V1DeltaRecord { changes })
}
pub(crate) fn apply_delta_record(
&mut self,
record_seq: RecordSeq,
delta: &V1DeltaRecord,
) -> io::Result<()> {
self.apply_delta_record_inner(record_seq, delta, false)
}
pub(crate) fn apply_maintenance_delta_record(
&mut self,
record_seq: RecordSeq,
delta: &V1DeltaRecord,
) -> io::Result<()> {
self.apply_delta_record_inner(record_seq, delta, true)
}
fn apply_delta_record_inner(
&mut self,
record_seq: RecordSeq,
delta: &V1DeltaRecord,
maintenance: bool,
) -> io::Result<()> {
if record_seq.is_null() {
return Err(invalid_data("delta has null record sequence"));
}
for change in &delta.changes {
let V1StateChange::RemoveRoot { block } = change else {
continue;
};
if self.roots.contains_key(&block.0)
&& delta.changes.iter().any(
|change| matches!(change, V1StateChange::AddRoot { block: added } if added == block),
)
{
return Err(invalid_data("root is both removed and added"));
}
}
for (index, change) in delta.changes.iter().enumerate() {
let V1StateChange::CreateActiveSegment { level, version } = change else {
continue;
};
let is_allocated = delta.changes[index + 1..].iter().any(|change| {
matches!(
change,
V1StateChange::AllocateSegmentBlocks {
level: allocated_level,
version: allocated_version,
len,
} if allocated_level == level && allocated_version == version && *len > 0
)
});
let replaces_empty_active = maintenance
&& self
.levels
.get(usize::from(*level))
.and_then(|level_data| {
let active_version = level_data.min_version.0.checked_add(
u32::try_from(level_data.versions.len().checked_sub(1)?).ok()?,
)?;
delta.changes[index + 1..].iter().find(|change| {
matches!(
change,
V1StateChange::RemoveSegment {
level: removed_level,
version: removed_version,
} if removed_level == level
&& removed_version.0 == active_version
)
})
})
.is_some();
if !is_allocated && !replaces_empty_active {
return Err(invalid_data("created active segment is not allocated"));
}
}
let mut next = self.clone();
if !next.record_seq.is_null() && record_seq <= next.record_seq {
return Err(invalid_data("record sequence is not increasing"));
}
next.record_seq = record_seq;
let mut released_blocks = BTreeSet::new();
for change in &delta.changes {
if let V1StateChange::AddRoot { block } = change
&& released_blocks.contains(&block.0)
{
return Err(invalid_data("cannot add released block as root"));
}
next.apply_change(record_seq, change)?;
match change {
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges,
} => {
for range in ranges {
for index in range.start..range.start + range.len {
released_blocks.insert(
(u64::from(index) << 32)
| (u64::from(version.0) << 4)
| u64::from(*level),
);
}
}
}
V1StateChange::ReleaseLargeBlock { id } => {
released_blocks.insert((id.0 << 4) | 15);
}
_ => {}
}
}
next.validate()?;
*self = next;
Ok(())
}
fn apply_change(
&mut self,
record_seq: RecordSeq,
change: &V1StateChange,
) -> io::Result<()> {
match change {
V1StateChange::CreateActiveSegment { level, version } => {
let level_data = self
.levels
.get_mut(usize::from(*level))
.ok_or_else(|| invalid_data("invalid level"))?;
let expected_version = level_data
.min_version
.0
.checked_add(
u32::try_from(level_data.versions.len())
.map_err(|_| invalid_data("segment version window is too large"))?,
)
.ok_or_else(|| invalid_data("segment version exhausted"))?;
if expected_version == 0 || expected_version > MAX_SEGMENT_VERSION {
return Err(invalid_data("segment version exhausted"));
}
if version.0 != expected_version {
return Err(invalid_data("unexpected segment version"));
}
level_data.versions.push_back(Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
}));
}
V1StateChange::AllocateSegmentBlocks {
level,
version,
len,
} => {
let segment = segment_mut(&mut self.levels, *level, *version)?;
segment.allocate(record_seq, *len)?;
}
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges,
} => {
let segment = segment_mut(&mut self.levels, *level, *version)?;
let mut previous_end = None;
for range in ranges {
if range.len == 0 || previous_end.is_some_and(|end| range.start <= end) {
return Err(invalid_data("invalid block range"));
}
let end = range
.start
.checked_add(range.len)
.ok_or_else(|| invalid_data("block range overflow"))?;
let end_index = usize::try_from(end)
.map_err(|_| invalid_data("block range overflow"))?;
if end_index > segment.released_at.len() {
return Err(invalid_data("block range exceeds allocation"));
}
for released in &mut segment.released_at
[usize::try_from(range.start).unwrap_or(0)..end_index]
{
if !released.is_null() {
return Err(invalid_data("block already released"));
}
*released = record_seq;
}
previous_end = Some(end);
}
}
V1StateChange::RemoveSegment { level, version } => {
let level_data = self
.levels
.get_mut(usize::from(*level))
.ok_or_else(|| invalid_data("invalid level"))?;
let index = version
.0
.checked_sub(level_data.min_version.0)
.ok_or_else(|| invalid_data("unknown segment"))?
as usize;
if index + 1 == level_data.versions.len()
|| level_data
.versions
.get(index)
.and_then(Option::as_ref)
.is_none()
{
return Err(invalid_data("cannot remove active or missing segment"));
}
let segment = level_data.versions[index]
.as_ref()
.ok_or_else(|| invalid_data("cannot remove missing segment"))?;
if segment
.released_at
.iter()
.any(|released| released.is_null())
{
return Err(invalid_data("cannot remove unreleased segment"));
}
level_data.versions[index] = None;
while level_data.versions.len() > 1
&& matches!(level_data.versions.front(), Some(None))
{
let min_version = level_data
.min_version
.0
.checked_add(1)
.filter(|version| *version <= MAX_SEGMENT_VERSION)
.ok_or_else(|| invalid_data("segment version exhausted"))?;
level_data.versions.pop_front();
level_data.min_version = SegmentVersion(min_version);
}
}
V1StateChange::AllocateLargeBlock { id, logical_len } => {
if self.large_blocks.next_id.0 > MAX_VALID_LARGE_BLOCK_ID
|| id.0 != self.large_blocks.next_id.0
|| *logical_len == 0
{
return Err(invalid_data("unexpected large block allocation"));
}
self.large_blocks.entries.insert(
*id,
LargeBlockData {
allocated_at: record_seq,
released_at: RecordSeq::NULL,
logical_len: *logical_len,
},
);
self.large_blocks.next_id.0 = self
.large_blocks
.next_id
.0
.checked_add(1)
.ok_or_else(|| invalid_data("large block id exhausted"))?;
}
V1StateChange::ReleaseLargeBlock { id } => {
let block = self
.large_blocks
.entries
.get_mut(id)
.ok_or_else(|| invalid_data("unknown large block"))?;
if !block.released_at.is_null() {
return Err(invalid_data("large block already released"));
}
block.released_at = record_seq;
}
V1StateChange::RemoveLargeBlock { id } => {
let block = self
.large_blocks
.entries
.get(id)
.ok_or_else(|| invalid_data("unknown large block"))?;
if block.released_at.is_null() {
return Err(invalid_data("cannot remove unreleased large block"));
}
self.large_blocks.entries.remove(id);
}
V1StateChange::AddRoot { block } => {
if self.block_release_seq(*block) == Some(record_seq) {
return Err(invalid_data("cannot add released block as root"));
}
if self.roots.insert(block.0, record_seq).is_some() {
return Err(invalid_data("root already exists"));
}
}
V1StateChange::RemoveRoot { block } => {
if self.roots.remove(&block.0).is_none() {
return Err(invalid_data("unknown root"));
}
}
V1StateChange::AddBinding { name, block } => {
if self.bindings.insert(name.clone(), *block).is_some() {
return Err(invalid_data("binding already exists"));
}
}
V1StateChange::RemoveBinding { name } => {
if self.bindings.remove(name).is_none() {
return Err(invalid_data("unknown binding"));
}
}
}
Ok(())
}
fn block_release_seq(&self, block: BlockId) -> Option<RecordSeq> {
if let Some(id) = block.large_block_id() {
return self
.large_blocks
.entries
.get(&LargeBlockId(id))
.map(|block| block.released_at);
}
let level = self.levels.get(usize::from(block.level()))?;
let version = block.segment_version()?;
let segment = level
.versions
.get(version.checked_sub(level.min_version.0)? as usize)?
.as_ref()?;
segment
.released_at
.get(usize::try_from(block.block_index()?).ok()?)
.copied()
}
}
fn validate_block_id(raw: u64) -> io::Result<()> {
if raw == u64::MAX {
return Err(invalid_data("reserved BlockId"));
}
let level = (raw & 0x0f) as u8;
let high = raw >> 4;
if level == 15 {
if high == 0 || high == MAX_LARGE_BLOCK_ID {
return Err(invalid_data("reserved large BlockId"));
}
} else if high & u64::from(MAX_SEGMENT_VERSION) == 0 {
return Err(invalid_data("ordinary BlockId has zero segment version"));
}
Ok(())
}
fn segment_mut(
levels: &mut [LevelVersions; 15],
level: u8,
version: SegmentVersion,
) -> io::Result<&mut SegmentData> {
let level_data = levels
.get_mut(usize::from(level))
.ok_or_else(|| invalid_data("invalid level"))?;
let index = version
.0
.checked_sub(level_data.min_version.0)
.ok_or_else(|| invalid_data("unknown segment"))? as usize;
level_data
.versions
.get_mut(index)
.and_then(Option::as_mut)
.ok_or_else(|| invalid_data("unknown segment"))
}
}
#[cfg(test)]
mod v1_tests {
use std::collections::BTreeSet;
use std::io::ErrorKind;
use crate::BlockId;
use super::v1::{
AllocationRun, BlockRange, LargeBlockId, RecordSeq, SegmentData, SegmentVersion,
V1DeltaRecord, V1State, V1StateChange,
};
fn reclamation_state() -> V1State {
let mut state = V1State::initial();
let level = 0;
let first_version = SegmentVersion(1);
let second_version = SegmentVersion(2);
let rooted_block = BlockId::from_raw_unchecked(u64::from(second_version.0) << 4);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid allocation sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: first_version,
len: 1,
}],
},
)
.expect("version one allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid seal sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: second_version,
},
V1StateChange::AllocateSegmentBlocks {
level,
version: second_version,
len: 1,
},
V1StateChange::AddRoot {
block: rooted_block,
},
],
},
)
.expect("version two creation and allocation applies");
state
.apply_delta_record(
RecordSeq::new(4).expect("valid segment release sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version: first_version,
ranges: vec![BlockRange { start: 0, len: 1 }],
}],
},
)
.expect("version one release applies");
state
.apply_delta_record(
RecordSeq::new(5).expect("valid large allocation sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateLargeBlock {
id: LargeBlockId(1),
logical_len: 4096,
}],
},
)
.expect("large block allocation applies");
state
.apply_delta_record(
RecordSeq::new(6).expect("valid large release sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseLargeBlock {
id: LargeBlockId(1),
}],
},
)
.expect("large block release applies");
state
}
fn removes_segment(changes: &[V1StateChange], level: u8, version: SegmentVersion) -> bool {
changes.iter().any(|change| {
matches!(
change,
V1StateChange::RemoveSegment {
level: removed_level,
version: removed_version,
} if *removed_level == level && *removed_version == version
)
})
}
fn removes_large_block(changes: &[V1StateChange], id: LargeBlockId) -> bool {
changes.iter().any(|change| {
matches!(
change,
V1StateChange::RemoveLargeBlock { id: removed_id } if *removed_id == id
)
})
}
fn active_segment_with_one_allocation(release: bool) -> V1State {
let mut state = V1State::initial();
state
.apply_delta_record(
RecordSeq::new(2).expect("valid allocation sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("active allocation applies");
if release {
state
.apply_delta_record(
RecordSeq::new(3).expect("valid release sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
}],
},
)
.expect("active release applies");
}
state
}
#[test]
fn v1_plan_reclamation_leaves_initial_empty_active_segments_unchanged() {
let state = V1State::initial();
let before = state.clone();
let plan = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert!(plan.changes.is_empty());
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_removes_sealed_before_replacing_released_active() {
let mut state = V1State::initial();
state
.apply_delta_record(
RecordSeq::new(2).expect("valid allocation sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(2),
len: 1,
},
],
},
)
.expect("sealed and active allocations apply");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid release sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
},
V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(2),
ranges: vec![BlockRange { start: 0, len: 1 }],
},
],
},
)
.expect("sealed and active releases apply");
let before = state.clone();
let plan = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert_eq!(state, before);
assert_eq!(
plan.changes,
vec![
V1StateChange::RemoveSegment {
level: 0,
version: SegmentVersion(1),
},
V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(3),
},
V1StateChange::RemoveSegment {
level: 0,
version: SegmentVersion(2),
},
]
);
state
.apply_maintenance_delta_record(
RecordSeq::new(4).expect("valid maintenance sequence"),
&plan,
)
.expect("planned sealed removal and active replacement apply");
let level = &state.levels[0];
assert_eq!(state.record_seq, RecordSeq(4));
assert_eq!(level.min_version, SegmentVersion(3));
assert_eq!(
level.versions,
std::collections::VecDeque::from([Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
})])
);
assert!(state.validate().is_ok());
}
#[test]
fn v1_plan_reclamation_replaces_unprotected_fully_released_active_in_order() {
let mut state = active_segment_with_one_allocation(true);
let before = state.clone();
let plan = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert_eq!(state, before);
assert_eq!(
plan.changes,
vec![
V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(2),
},
V1StateChange::RemoveSegment {
level: 0,
version: SegmentVersion(1),
},
]
);
state
.apply_maintenance_delta_record(
RecordSeq::new(4).expect("valid maintenance sequence"),
&plan,
)
.expect("planned active replacement applies as maintenance");
let level = &state.levels[0];
assert_eq!(state.record_seq, RecordSeq(4));
assert_eq!(level.min_version, SegmentVersion(2));
assert_eq!(
level.versions,
std::collections::VecDeque::from([Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
})])
);
assert!(state.validate().is_ok());
}
#[test]
fn v1_plan_reclamation_keeps_fully_released_active_when_allocation_is_protected() {
let state = active_segment_with_one_allocation(true);
let before = state.clone();
let plan = state
.plan_reclamation(&BTreeSet::from([RecordSeq(2)]))
.expect("allocation sequence is valid protection");
assert!(!plan.changes.iter().any(|change| matches!(
change,
V1StateChange::CreateActiveSegment { level: 0, .. }
| V1StateChange::RemoveSegment { level: 0, .. }
)));
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_keeps_active_with_unreleased_slots() {
let state = active_segment_with_one_allocation(false);
let before = state.clone();
let plan = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert!(!plan.changes.iter().any(|change| matches!(
change,
V1StateChange::CreateActiveSegment { level: 0, .. }
| V1StateChange::RemoveSegment { level: 0, .. }
)));
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_uses_half_open_segment_lifetime_endpoints() {
let state = reclamation_state();
let before = state.clone();
let version = SegmentVersion(1);
let allocated_endpoint = state
.plan_reclamation(&BTreeSet::from([RecordSeq(2)]))
.expect("allocated endpoint is valid");
let released_endpoint = state
.plan_reclamation(&BTreeSet::from([RecordSeq(4)]))
.expect("released endpoint is valid");
assert!(!removes_segment(&allocated_endpoint.changes, 0, version));
assert!(removes_segment(&released_endpoint.changes, 0, version));
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_protects_sealed_segment_only_inside_lifetime() {
let state = reclamation_state();
let before = state.clone();
let version = SegmentVersion(1);
let protected = state
.plan_reclamation(&BTreeSet::from([RecordSeq(3)]))
.expect("interior sequence is valid");
let unprotected = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert!(!removes_segment(&protected.changes, 0, version));
assert!(removes_segment(&unprotected.changes, 0, version));
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_uses_half_open_large_block_lifetime_endpoints() {
let state = reclamation_state();
let before = state.clone();
let id = LargeBlockId(1);
let allocated_endpoint = state
.plan_reclamation(&BTreeSet::from([RecordSeq(5)]))
.expect("large allocation endpoint is valid");
let released_endpoint = state
.plan_reclamation(&BTreeSet::from([RecordSeq(6)]))
.expect("large release endpoint is valid");
let unprotected = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert!(!removes_large_block(&allocated_endpoint.changes, id));
assert!(removes_large_block(&released_endpoint.changes, id));
assert!(removes_large_block(&unprotected.changes, id));
assert_eq!(state, before);
}
#[test]
fn v1_plan_reclamation_requires_callers_to_merge_root_sequences() {
let state = reclamation_state();
let before = state.clone();
let version = SegmentVersion(1);
let unprotected = state
.plan_reclamation(&BTreeSet::new())
.expect("empty protected set is valid");
assert!(removes_segment(&unprotected.changes, 0, version));
assert_eq!(state, before);
let protected: BTreeSet<RecordSeq> = state.roots.values().copied().collect();
let protected_plan = state
.plan_reclamation(&protected)
.expect("root publication sequences are valid protection");
assert!(!removes_segment(&protected_plan.changes, 0, version));
assert_eq!(state, before);
}
#[test]
fn v1_initial_has_fifteen_empty_active_levels_at_version_one() {
let state = V1State::initial();
assert_eq!(state.levels.len(), 15);
assert!(state.levels.iter().all(|level| {
level.min_version == SegmentVersion(1)
&& level.versions.len() == 1
&& level.versions.front()
== Some(&Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
}))
}));
assert!(state.validate().is_ok());
}
#[test]
fn v1_allocation_runs_merge_and_keep_release_slots_parallel() {
let mut state = V1State::initial();
let delta = V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 3,
version: SegmentVersion(1),
len: 2,
},
V1StateChange::AllocateSegmentBlocks {
level: 3,
version: SegmentVersion(1),
len: 1,
},
],
};
state
.apply_delta_record(RecordSeq::new(2).expect("valid record sequence"), &delta)
.expect("first allocation delta applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level: 3,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 1, len: 1 }],
}],
},
)
.expect("release delta applies");
let segment = state.levels[3].versions.back().and_then(Option::as_ref);
assert_eq!(
segment.map(|value| (&value.allocation_runs, &value.released_at)),
Some((
&vec![AllocationRun {
allocated_at: RecordSeq(2),
len: 3,
}],
&vec![RecordSeq::NULL, RecordSeq(3), RecordSeq::NULL],
))
);
}
#[test]
fn v1_release_segment_blocks_accepts_one_merged_range() {
let mut state = V1State::initial();
let level = 3;
let version = SegmentVersion(1);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version,
len: 3,
}],
},
)
.expect("ordinary block allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges: vec![BlockRange { start: 0, len: 2 }],
}],
},
)
.expect("merged release range applies");
let segment = state.levels[usize::from(level)].versions[0]
.as_ref()
.expect("allocated segment exists");
assert_eq!(
segment.released_at,
vec![RecordSeq(3), RecordSeq(3), RecordSeq::NULL]
);
}
#[test]
fn v1_release_segment_blocks_rejects_adjacent_ranges_without_mutating_state() {
let mut state = V1State::initial();
let level = 3;
let version = SegmentVersion(1);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version,
len: 3,
}],
},
)
.expect("ordinary block allocation applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges: vec![
BlockRange { start: 0, len: 1 },
BlockRange { start: 1, len: 1 },
],
}],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_create_and_allocate_active_segment_seals_nonempty_previous_active() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(2),
len: 1,
},
],
},
)
.expect("nonempty active replacement applies");
let level_data = &state.levels[usize::from(level)];
assert_eq!(level_data.min_version, SegmentVersion(1));
assert_eq!(level_data.versions.len(), 2);
let sealed = level_data.versions[0]
.as_ref()
.expect("old sealed segment remains present");
assert!(!sealed.allocation_runs.is_empty());
let active = level_data.versions[1]
.as_ref()
.expect("new active segment is present at the tail");
assert_eq!(
active.allocation_runs,
vec![AllocationRun {
allocated_at: RecordSeq(3),
len: 1,
}]
);
assert!(state.validate().is_ok());
}
#[test]
fn v1_business_delta_rejects_empty_active_creation_without_mutating_state() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
}],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_validate_rejects_empty_sealed_segment() {
let mut state = V1State::initial();
state.levels[0].versions.push_back(Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
}));
assert!(state.validate().is_err());
}
#[test]
fn v1_validate_rejects_non_active_tail() {
let mut state = V1State::initial();
state.levels[0].versions[0] = None;
assert!(state.validate().is_err());
}
#[test]
fn v1_validate_rejects_null_record_sequence() {
let mut state = V1State::initial();
state.record_seq = RecordSeq::NULL;
assert!(state.validate().is_err());
}
#[test]
fn v1_validate_rejects_adjacent_allocation_runs_with_same_record_sequence() {
let mut state = V1State::initial();
state.record_seq = RecordSeq(1);
state.levels[0].versions[0] = Some(SegmentData {
allocation_runs: vec![
AllocationRun {
allocated_at: RecordSeq(1),
len: 1,
},
AllocationRun {
allocated_at: RecordSeq(1),
len: 1,
},
],
released_at: vec![RecordSeq::NULL, RecordSeq::NULL],
});
assert_eq!(
state.validate().as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
}
#[test]
fn v1_validate_rejects_allocation_runs_with_descending_record_sequences() {
let mut state = V1State::initial();
state.record_seq = RecordSeq(2);
state.levels[0].versions[0] = Some(SegmentData {
allocation_runs: vec![
AllocationRun {
allocated_at: RecordSeq(2),
len: 1,
},
AllocationRun {
allocated_at: RecordSeq(1),
len: 1,
},
],
released_at: vec![RecordSeq::NULL, RecordSeq::NULL],
});
assert_eq!(
state.validate().as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
}
#[test]
fn v1_validate_rejects_invalid_root_publication_sequence() {
let mut state = V1State::initial();
state.roots.insert(0x10, RecordSeq::NULL);
assert!(state.validate().is_err());
}
#[test]
fn v1_validate_rejects_segment_window_past_encoding_limit() {
let mut state = V1State::initial();
state.levels[0].min_version = SegmentVersion(0x0fff_ffff);
state.levels[0].versions.push_back(None);
assert!(state.validate().is_err());
}
#[test]
fn v1_remove_large_block_rejects_unreleased_block_without_mutating_state() {
let mut state = V1State::initial();
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateLargeBlock {
id: super::v1::LargeBlockId(1),
logical_len: 1,
},
V1StateChange::RemoveLargeBlock {
id: super::v1::LargeBlockId(1),
},
],
},
);
assert!(result.is_err());
assert_eq!(state, before);
}
#[test]
fn v1_remove_segment_rejects_unreleased_segment_without_mutating_state() {
let mut state = V1State::initial();
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(2),
len: 1,
},
V1StateChange::RemoveSegment {
level: 0,
version: SegmentVersion(1),
},
],
},
);
assert!(result.is_err());
assert_eq!(state, before);
}
#[test]
fn v1_remove_root_then_add_root_is_invalid_and_does_not_mutate_state() {
let mut state = V1State::initial();
let block = BlockId::from_raw_unchecked(0x10);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AddRoot { block }],
},
)
.expect("initial root addition applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::RemoveRoot { block },
V1StateChange::AddRoot { block },
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_release_then_add_root_is_invalid_and_does_not_mutate_state() {
let mut state = V1State::initial();
let level = 3;
let version = SegmentVersion(1);
let index = 0_u32;
let block = BlockId::from_raw_unchecked(
(u64::from(index) << 32) | (u64::from(version.0) << 4) | u64::from(level),
);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version,
len: 1,
}],
},
)
.expect("ordinary block allocation applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges: vec![BlockRange {
start: index,
len: 1,
}],
},
V1StateChange::AddRoot { block },
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_release_remove_segment_then_add_root_is_invalid_and_does_not_mutate_state() {
let mut state = V1State::initial();
let level = 3;
let version = SegmentVersion(1);
let index = 0_u32;
let block = BlockId::from_raw_unchecked(
(u64::from(index) << 32) | (u64::from(version.0) << 4) | u64::from(level),
);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level,
version,
len: 1,
},
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(2),
len: 1,
},
],
},
)
.expect("sealed segment setup applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges: vec![BlockRange {
start: index,
len: 1,
}],
},
V1StateChange::RemoveSegment { level, version },
V1StateChange::AddRoot { block },
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_release_remove_large_block_then_add_root_is_invalid_and_does_not_mutate_state() {
let mut state = V1State::initial();
let id = super::v1::LargeBlockId(1);
let block = BlockId::from_raw_unchecked((id.0 << 4) | 15);
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateLargeBlock { id, logical_len: 1 }],
},
)
.expect("large block allocation applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseLargeBlock { id },
V1StateChange::RemoveLargeBlock { id },
V1StateChange::AddRoot { block },
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_remove_released_front_segment_trims_window_and_advances_min_version() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(2),
len: 1,
},
],
},
)
.expect("two-version setup applies");
let mut expected = state.clone();
expected.record_seq = RecordSeq(3);
expected.levels[usize::from(level)].min_version = SegmentVersion(2);
expected.levels[usize::from(level)].versions.pop_front();
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseSegmentBlocks {
level,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
},
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
},
],
},
)
.expect("released front segment removal applies");
let before_error = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(4).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
}],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before_error);
assert_eq!(state, expected);
}
#[test]
fn v1_remove_released_middle_segment_preserves_window_and_hole() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(2),
len: 1,
},
],
},
)
.expect("first sealed-segment setup applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(3),
},
V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(3),
len: 1,
},
],
},
)
.expect("three-version setup applies");
let mut expected = state.clone();
expected.record_seq = RecordSeq(4);
expected.levels[usize::from(level)].versions[1] = None;
state
.apply_delta_record(
RecordSeq::new(4).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::ReleaseSegmentBlocks {
level,
version: SegmentVersion(2),
ranges: vec![BlockRange { start: 0, len: 1 }],
},
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(2),
},
],
},
)
.expect("released middle segment removal applies");
let before_error = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(5).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::RemoveSegment {
level,
version: SegmentVersion(2),
}],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before_error);
assert_eq!(state, expected);
}
#[test]
fn v1_maintenance_replaces_fully_released_active_with_empty_next_version() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
}],
},
)
.expect("initial active release applies");
state
.apply_maintenance_delta_record(
RecordSeq::new(4).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
},
],
},
)
.expect("maintenance replaces fully released active segment");
let level_data = &state.levels[usize::from(level)];
assert_eq!(level_data.min_version, SegmentVersion(2));
assert_eq!(
level_data.versions,
std::collections::VecDeque::from([Some(SegmentData {
allocation_runs: Vec::new(),
released_at: Vec::new(),
})])
);
assert!(state.validate().is_ok());
}
#[test]
fn v1_business_delta_rejects_replacing_released_active_with_empty_next_version() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
}],
},
)
.expect("initial active release applies");
let before = state.clone();
let result = state.apply_delta_record(
RecordSeq::new(4).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
},
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_maintenance_rejects_replacing_active_with_unreleased_slots() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
let before = state.clone();
let result = state.apply_maintenance_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
},
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
#[test]
fn v1_maintenance_rejects_remove_active_before_create_without_mutating_state() {
let mut state = V1State::initial();
let level = 0;
state
.apply_delta_record(
RecordSeq::new(2).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level,
version: SegmentVersion(1),
len: 1,
}],
},
)
.expect("initial active allocation applies");
state
.apply_delta_record(
RecordSeq::new(3).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
}],
},
)
.expect("initial active release applies");
let before = state.clone();
let result = state.apply_maintenance_delta_record(
RecordSeq::new(4).expect("valid record sequence"),
&V1DeltaRecord {
changes: vec![
V1StateChange::RemoveSegment {
level,
version: SegmentVersion(1),
},
V1StateChange::CreateActiveSegment {
level,
version: SegmentVersion(2),
},
],
},
);
assert_eq!(
result.as_ref().err().map(std::io::Error::kind),
Some(ErrorKind::InvalidData)
);
assert_eq!(state, before);
}
}