use std::collections::{BTreeMap, BTreeSet};
use std::io;
use pi_append_log::{BlockDecoder, BlockEncoder, DefaultBlockCodec};
use super::state::{Delta, SegmentRecord, SegmentState, State};
const MAGIC: [u8; 4] = *b"pibd";
const FORMAT_VERSION: u16 = 1;
const CHECKPOINT_KIND: u8 = 1;
const DELTA_KIND: u8 = 2;
const MAX_COLLECTION_COUNT: u32 = 1_000_000;
const MAX_STRING_LEN: u32 = 1024 * 1024;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(super) struct LengthModel {
pub(super) count: usize,
pub(super) bytes_per_item: usize,
pub(super) variable_bytes: usize,
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(super) struct LogRecordShape {
pub(super) fixed_bytes: usize,
pub(super) segments: LengthModel,
pub(super) segment_bitmap_words: usize,
pub(super) large_blocks: LengthModel,
pub(super) segment_removes: LengthModel,
pub(super) large_removes: LengthModel,
pub(super) roots: LengthModel,
pub(super) root_removes: LengthModel,
pub(super) bindings: LengthModel,
pub(super) binding_removes: LengthModel,
pub(super) root_name_utf8_bytes: usize,
}
pub(super) fn checkpoint_shape_for_test(state: &State) -> LogRecordShape {
let segment_bitmap_words = state
.segments
.values()
.map(|record| record.bitmap.len())
.fold(0_usize, usize::saturating_add);
let root_name_utf8_bytes = state
.bindings
.keys()
.map(String::len)
.fold(0_usize, usize::saturating_add);
LogRecordShape {
fixed_bytes: 8 + 16 + 4 + 8 + (15 * 4) + (4 * 4),
segments: LengthModel {
count: state.segments.len(),
bytes_per_item: 28,
variable_bytes: segment_bitmap_words.saturating_mul(8),
},
segment_bitmap_words,
large_blocks: LengthModel {
count: state.large_blocks.len(),
bytes_per_item: 16,
variable_bytes: 0,
},
roots: LengthModel {
count: state.roots.len(),
bytes_per_item: 8,
variable_bytes: 0,
},
bindings: LengthModel {
count: state.bindings.len(),
bytes_per_item: 4 + 8,
variable_bytes: root_name_utf8_bytes,
},
root_name_utf8_bytes,
..LogRecordShape::default()
}
}
pub(super) fn delta_shape_for_test(delta: &Delta) -> LogRecordShape {
let segment_bitmap_words = delta
.segment_upserts
.iter()
.map(|record| record.bitmap.len())
.fold(0_usize, usize::saturating_add);
let binding_upsert_utf8_bytes = delta
.binding_upserts
.iter()
.map(|(name, _)| name.len())
.fold(0_usize, usize::saturating_add);
let binding_remove_utf8_bytes = delta
.binding_removes
.iter()
.map(String::len)
.fold(0_usize, usize::saturating_add);
LogRecordShape {
fixed_bytes: 8 + 4 + 8 + (8 * 4),
segments: LengthModel {
count: delta.segment_upserts.len(),
bytes_per_item: 28,
variable_bytes: segment_bitmap_words.saturating_mul(8),
},
segment_bitmap_words,
large_blocks: LengthModel {
count: delta.large_adds.len(),
bytes_per_item: 16,
variable_bytes: 0,
},
segment_removes: LengthModel {
count: delta.segment_removes.len(),
bytes_per_item: 1 + 4,
variable_bytes: 0,
},
large_removes: LengthModel {
count: delta.large_removes.len(),
bytes_per_item: 8,
variable_bytes: 0,
},
roots: LengthModel {
count: delta.root_adds.len(),
bytes_per_item: 8,
variable_bytes: 0,
},
root_removes: LengthModel {
count: delta.root_removes.len(),
bytes_per_item: 8,
variable_bytes: 0,
},
bindings: LengthModel {
count: delta.binding_upserts.len(),
bytes_per_item: 4 + 8,
variable_bytes: binding_upsert_utf8_bytes,
},
binding_removes: LengthModel {
count: delta.binding_removes.len(),
bytes_per_item: 4,
variable_bytes: binding_remove_utf8_bytes,
},
root_name_utf8_bytes: binding_upsert_utf8_bytes.saturating_add(binding_remove_utf8_bytes),
}
}
const ENVELOPE_MAX_PAYLOAD_LEN: usize = u32::MAX as usize - 16;
fn checked_model_len(model: LengthModel) -> Result<usize, crate::BlockStoreError> {
model
.count
.checked_mul(model.bytes_per_item)
.and_then(|fixed| fixed.checked_add(model.variable_bytes))
.ok_or(crate::BlockStoreError::RecordTooLarge)
}
fn checked_payload_len(
shape: LogRecordShape,
configured_max: usize,
) -> Result<usize, crate::BlockStoreError> {
let models = [
shape.segments,
shape.large_blocks,
shape.segment_removes,
shape.large_removes,
shape.roots,
shape.root_removes,
shape.bindings,
shape.binding_removes,
];
let mut total = shape.fixed_bytes;
for model in models {
total = total
.checked_add(checked_model_len(model)?)
.ok_or(crate::BlockStoreError::RecordTooLarge)?;
}
if total > configured_max || total > ENVELOPE_MAX_PAYLOAD_LEN {
return Err(crate::BlockStoreError::RecordTooLarge);
}
Ok(total)
}
pub(crate) fn checkpoint_payload_len(state: &State) -> Result<usize, crate::BlockStoreError> {
checkpoint_payload_len_with_limit(state, DefaultBlockCodec::default().max_payload_len())
}
pub(crate) fn checkpoint_payload_len_with_limit(
state: &State,
configured_max: usize,
) -> Result<usize, crate::BlockStoreError> {
checked_payload_len(checkpoint_shape_for_test(state), configured_max)
}
#[allow(dead_code)]
pub(crate) fn delta_payload_len(delta: &Delta) -> Result<usize, crate::BlockStoreError> {
delta_payload_len_with_limit(delta, DefaultBlockCodec::default().max_payload_len())
}
pub(crate) fn delta_payload_len_with_limit(
delta: &Delta,
configured_max: usize,
) -> Result<usize, crate::BlockStoreError> {
checked_payload_len(delta_shape_for_test(delta), configured_max)
}
#[cfg(test)]
#[allow(dead_code)]
pub(super) fn checked_checkpoint_payload_len_for_test(
shape: LogRecordShape,
configured_max: usize,
) -> Result<usize, crate::BlockStoreError> {
checked_payload_len(shape, configured_max)
}
#[cfg(test)]
#[allow(dead_code)]
pub(super) fn checked_delta_payload_len_for_test(
shape: LogRecordShape,
configured_max: usize,
) -> Result<usize, crate::BlockStoreError> {
checked_payload_len(shape, configured_max)
}
pub(crate) enum Record {
Checkpoint {
sequence: u64,
state: State,
},
Delta {
sequence: u64,
delta: Delta,
},
}
pub(crate) enum DecodeError {
Recovery(
io::Error,
),
UnsupportedFormat,
}
impl From<io::Error> for DecodeError {
fn from(error: io::Error) -> Self {
Self::Recovery(error)
}
}
#[allow(dead_code, clippy::large_enum_variant)]
enum V1Record {
Checkpoint {
record_seq: crate::file::state::v1::RecordSeq,
state: crate::file::state::v1::V1State,
},
Delta {
record_seq: crate::file::state::v1::RecordSeq,
delta: crate::file::state::v1::V1DeltaRecord,
},
}
#[allow(dead_code)]
fn encode_v1_checkpoint_block(state: &crate::file::state::v1::V1State) -> io::Result<Vec<u8>> {
DefaultBlockCodec::default().encode(
u64::from(state.record_seq.get()),
0,
&v1_codec::encode_checkpoint_payload(state)?,
)
}
#[allow(dead_code)]
fn encode_v1_delta_block(
record_seq: crate::file::state::v1::RecordSeq,
delta: &crate::file::state::v1::V1DeltaRecord,
) -> io::Result<Vec<u8>> {
let record_seq = crate::file::state::v1::RecordSeq::new(record_seq.get())?;
DefaultBlockCodec::default().encode(
u64::from(record_seq.get()),
0,
&v1_codec::encode_delta_payload(delta)?,
)
}
#[allow(dead_code)]
fn decode_v1_record_block(block: &[u8]) -> io::Result<V1Record> {
let decoded = DefaultBlockCodec::default().decode_forward(block)?;
if decoded.encoded_len() != block.len() || decoded.flags() != 0 {
return Err(invalid_data("invalid V1 log block"));
}
let block_seq = decoded.block_seq();
if block_seq == 0 || block_seq >= u64::from(u32::MAX) {
return Err(invalid_data("invalid V1 record sequence"));
}
let record_seq = crate::file::state::v1::RecordSeq::new(
u32::try_from(block_seq).map_err(|_| invalid_data("invalid V1 record sequence"))?,
)?;
let payload = decoded.payload();
let mut cursor = Cursor::new(payload);
cursor.expect_bytes(&MAGIC)?;
if cursor.u16()? != FORMAT_VERSION {
return Err(invalid_data("invalid V1 record version"));
}
let kind = cursor.u8()?;
if cursor.u8()? != 0 {
return Err(invalid_data("nonzero V1 record reserved byte"));
}
match kind {
CHECKPOINT_KIND => Ok(V1Record::Checkpoint {
record_seq,
state: v1_codec::decode_checkpoint_payload(payload, record_seq)?,
}),
DELTA_KIND => Ok(V1Record::Delta {
record_seq,
delta: v1_codec::decode_delta_payload(payload)?,
}),
_ => Err(invalid_data("unknown V1 record kind")),
}
}
#[allow(dead_code)]
fn recover_v1_record_blocks<'a>(
blocks: impl IntoIterator<Item = &'a [u8]>,
) -> io::Result<crate::file::state::v1::V1State> {
let mut blocks = blocks.into_iter();
let first = blocks
.next()
.ok_or_else(|| invalid_data("empty V1 record chain"))?;
let mut state = match decode_v1_record_block(first)
.map_err(|_| invalid_data("invalid V1 record chain"))?
{
V1Record::Checkpoint { state, .. } => state,
V1Record::Delta { .. } => return Err(invalid_data("V1 record chain starts with delta")),
};
for block in blocks {
match decode_v1_record_block(block).map_err(|_| invalid_data("invalid V1 record chain"))? {
V1Record::Checkpoint { .. } => {
return Err(invalid_data("checkpoint follows initial V1 checkpoint"));
}
V1Record::Delta { record_seq, delta } => {
state
.apply_delta_record(record_seq, &delta)
.map_err(|_| invalid_data("invalid V1 record chain"))?
}
}
}
Ok(state)
}
pub(crate) fn encode_initial_checkpoint(device_id: [u8; 16]) -> Vec<u8> {
encode_checkpoint_payload(&State::initial(device_id))
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn encode_checkpoint(state: &State, sequence: u64) -> io::Result<Vec<u8>> {
DefaultBlockCodec::default().encode(sequence, 0, &encode_checkpoint_payload(state))
}
fn encode_checkpoint_payload(state: &State) -> Vec<u8> {
let mut output = Vec::new();
common_header(&mut output, CHECKPOINT_KIND);
output.extend_from_slice(&state.device_id);
output.extend_from_slice(&state.next_segment_version.to_le_bytes());
output.extend_from_slice(&state.next_large_block_id.to_le_bytes());
for version in state.active_versions {
output.extend_from_slice(&version.to_le_bytes());
}
output.extend_from_slice(&(state.segments.len() as u32).to_le_bytes());
for record in state.segments.values() {
encode_segment(&mut output, record);
}
output.extend_from_slice(&(state.large_blocks.len() as u32).to_le_bytes());
for (&id, &logical_len) in &state.large_blocks {
output.extend_from_slice(&id.to_le_bytes());
output.extend_from_slice(&logical_len.to_le_bytes());
}
output.extend_from_slice(&(state.roots.len() as u32).to_le_bytes());
for block in &state.roots {
output.extend_from_slice(&block.to_le_bytes());
}
output.extend_from_slice(&(state.bindings.len() as u32).to_le_bytes());
for (name, target) in &state.bindings {
encode_string(&mut output, name);
output.extend_from_slice(&target.to_le_bytes());
}
output
}
pub(crate) fn encode_delta(delta: &Delta) -> Vec<u8> {
let mut output = Vec::new();
common_header(&mut output, DELTA_KIND);
output.extend_from_slice(&delta.next_segment_version.to_le_bytes());
output.extend_from_slice(&delta.next_large_block_id.to_le_bytes());
output.extend_from_slice(&(delta.segment_upserts.len() as u32).to_le_bytes());
for record in &delta.segment_upserts {
encode_segment(&mut output, record);
}
output.extend_from_slice(&(delta.segment_removes.len() as u32).to_le_bytes());
for (level, version) in &delta.segment_removes {
output.push(*level);
output.extend_from_slice(&version.to_le_bytes());
}
output.extend_from_slice(&(delta.large_adds.len() as u32).to_le_bytes());
for (id, logical_len) in &delta.large_adds {
output.extend_from_slice(&id.to_le_bytes());
output.extend_from_slice(&logical_len.to_le_bytes());
}
output.extend_from_slice(&(delta.large_removes.len() as u32).to_le_bytes());
for id in &delta.large_removes {
output.extend_from_slice(&id.to_le_bytes());
}
output.extend_from_slice(&(delta.root_adds.len() as u32).to_le_bytes());
for block in &delta.root_adds {
output.extend_from_slice(&block.to_le_bytes());
}
output.extend_from_slice(&(delta.root_removes.len() as u32).to_le_bytes());
for block in &delta.root_removes {
output.extend_from_slice(&block.to_le_bytes());
}
output.extend_from_slice(&(delta.binding_removes.len() as u32).to_le_bytes());
for name in &delta.binding_removes {
encode_string(&mut output, name);
}
output.extend_from_slice(&(delta.binding_upserts.len() as u32).to_le_bytes());
for (name, target) in &delta.binding_upserts {
encode_string(&mut output, name);
output.extend_from_slice(&target.to_le_bytes());
}
output
}
pub(crate) fn decode_record_block(block: &[u8]) -> Result<Record, DecodeError> {
let decoded = DefaultBlockCodec::default().decode_forward(block)?;
if decoded.encoded_len() != block.len() || decoded.flags() != 0 {
return Err(invalid_data("invalid log block").into());
}
let sequence = decoded.block_seq();
let input = decoded.payload();
let mut cursor = Cursor::new(input);
cursor.expect_bytes(&MAGIC)?;
let version = cursor.u16()?;
if version > FORMAT_VERSION {
return Err(DecodeError::UnsupportedFormat);
}
if version != FORMAT_VERSION {
return Err(invalid_data("invalid record version").into());
}
let kind = cursor.u8()?;
if cursor.u8()? != 0 {
return Err(invalid_data("nonzero record reserved byte").into());
}
match kind {
CHECKPOINT_KIND => Ok(Record::Checkpoint {
sequence,
state: decode_checkpoint(&mut cursor)?,
}),
DELTA_KIND => Ok(Record::Delta {
sequence,
delta: decode_delta(&mut cursor)?,
}),
_ => Err(invalid_data("unknown record kind").into()),
}
}
fn decode_checkpoint(cursor: &mut Cursor<'_>) -> Result<State, DecodeError> {
let device_id = cursor.array_16()?;
let next_segment_version = cursor.u32()?;
let next_large_block_id = cursor.u64()?;
let mut active_versions = [0_u32; 15];
for version in &mut active_versions {
*version = cursor.u32()?;
}
let segments = decode_sorted_segments(cursor)?;
let large_blocks = decode_sorted_pairs(cursor, |cursor| Ok((cursor.u64()?, cursor.u64()?)))?;
let roots = decode_sorted_values(cursor, |cursor| cursor.u64())?;
let bindings = decode_sorted_pairs(cursor, |cursor| Ok((cursor.string()?, cursor.u64()?)))?;
cursor.finish()?;
let state = State {
device_id,
next_segment_version,
next_large_block_id,
active_versions,
segments,
large_blocks,
roots,
bindings,
};
state.validate()?;
Ok(state)
}
fn decode_delta(cursor: &mut Cursor<'_>) -> Result<Delta, DecodeError> {
let next_segment_version = cursor.u32()?;
let next_large_block_id = cursor.u64()?;
let segment_upserts = decode_sorted_vec(cursor, decode_segment, SegmentRecord::key)?;
let segment_removes = decode_sorted_vec(
cursor,
|cursor| Ok((cursor.u8()?, cursor.u32()?)),
|key| *key,
)?;
let large_adds = decode_sorted_vec(
cursor,
|cursor| Ok((cursor.u64()?, cursor.u64()?)),
|entry| entry.0,
)?;
let large_removes = decode_sorted_vec(cursor, |cursor| cursor.u64(), |id| *id)?;
let root_adds = decode_sorted_vec(cursor, |cursor| cursor.u64(), |block| *block)?;
let root_removes = decode_sorted_vec(cursor, |cursor| cursor.u64(), |block| *block)?;
let binding_removes = decode_sorted_vec(cursor, |cursor| cursor.string(), String::clone)?;
let binding_upserts = decode_sorted_vec(
cursor,
|cursor| Ok((cursor.string()?, cursor.u64()?)),
|entry| entry.0.clone(),
)?;
cursor.finish()?;
let delta = Delta {
next_segment_version,
next_large_block_id,
segment_upserts,
segment_removes,
large_adds,
large_removes,
root_adds,
root_removes,
binding_removes,
binding_upserts,
};
validate_delta_records(&delta)?;
Ok(delta)
}
fn decode_sorted_segments(
cursor: &mut Cursor<'_>,
) -> io::Result<BTreeMap<(u8, u32), SegmentRecord>> {
let records = decode_sorted_vec(cursor, decode_segment, SegmentRecord::key)?;
Ok(records
.into_iter()
.map(|record| (record.key(), record))
.collect())
}
fn decode_segment(cursor: &mut Cursor<'_>) -> io::Result<SegmentRecord> {
let level = cursor.u8()?;
let state = match cursor.u8()? {
1 => SegmentState::Active,
2 => SegmentState::Sealed,
_ => return Err(invalid_data("invalid segment state")),
};
if cursor.u16()? != 0 {
return Err(invalid_data("nonzero segment reserved field"));
}
let version = cursor.u32()?;
let frontier = cursor.u64()?;
let live_count = cursor.u64()?;
let word_count = cursor.count()?;
let mut bitmap = Vec::with_capacity(word_count);
for _ in 0..word_count {
bitmap.push(cursor.u64()?);
}
let record = SegmentRecord {
level,
state,
version,
frontier,
live_count,
bitmap,
};
record.validate()?;
Ok(record)
}
fn validate_delta_records(delta: &Delta) -> io::Result<()> {
for &(level, version) in &delta.segment_removes {
if level > 14 || version == 0 || version > 0x0fff_ffff {
return Err(invalid_data("invalid removed segment key"));
}
}
for &(id, logical_len) in &delta.large_adds {
if id == 0 || id >= (1_u64 << 60) - 1 || logical_len == 0 {
return Err(invalid_data("invalid large block add"));
}
}
if delta
.large_removes
.iter()
.any(|id| *id == 0 || *id >= (1_u64 << 60) - 1)
{
return Err(invalid_data("invalid large block remove"));
}
Ok(())
}
fn decode_sorted_pairs<K: Ord + Clone, V>(
cursor: &mut Cursor<'_>,
decode: impl FnMut(&mut Cursor<'_>) -> io::Result<(K, V)>,
) -> io::Result<BTreeMap<K, V>> {
Ok(decode_sorted_vec(cursor, decode, |entry| entry.0.clone())?
.into_iter()
.collect())
}
fn decode_sorted_values<T: Ord + Clone>(
cursor: &mut Cursor<'_>,
decode: impl FnMut(&mut Cursor<'_>) -> io::Result<T>,
) -> io::Result<BTreeSet<T>> {
Ok(decode_sorted_vec(cursor, decode, T::clone)?
.into_iter()
.collect())
}
fn decode_sorted_vec<T, K: Ord>(
cursor: &mut Cursor<'_>,
mut decode: impl FnMut(&mut Cursor<'_>) -> io::Result<T>,
key: impl Fn(&T) -> K,
) -> io::Result<Vec<T>> {
let count = cursor.count()?;
let mut output = Vec::with_capacity(count);
for _ in 0..count {
let value = decode(cursor)?;
if output
.last()
.is_some_and(|previous| key(previous) >= key(&value))
{
return Err(invalid_data("collection is not strictly sorted"));
}
output.push(value);
}
Ok(output)
}
fn common_header(output: &mut Vec<u8>, kind: u8) {
output.extend_from_slice(&MAGIC);
output.extend_from_slice(&FORMAT_VERSION.to_le_bytes());
output.push(kind);
output.push(0);
}
fn encode_segment(output: &mut Vec<u8>, record: &SegmentRecord) {
output.push(record.level);
output.push(match record.state {
SegmentState::Active => 1,
SegmentState::Sealed => 2,
});
output.extend_from_slice(&0_u16.to_le_bytes());
output.extend_from_slice(&record.version.to_le_bytes());
output.extend_from_slice(&record.frontier.to_le_bytes());
output.extend_from_slice(&record.live_count.to_le_bytes());
output.extend_from_slice(&(record.bitmap.len() as u32).to_le_bytes());
for word in &record.bitmap {
output.extend_from_slice(&word.to_le_bytes());
}
}
fn encode_string(output: &mut Vec<u8>, value: &str) {
output.extend_from_slice(&(value.len() as u32).to_le_bytes());
output.extend_from_slice(value.as_bytes());
}
struct Cursor<'a> {
input: &'a [u8],
offset: usize,
}
impl<'a> Cursor<'a> {
fn new(input: &'a [u8]) -> Self {
Self { input, offset: 0 }
}
fn take(&mut self, length: usize) -> io::Result<&'a [u8]> {
let end = self
.offset
.checked_add(length)
.ok_or_else(|| invalid_data("record offset overflow"))?;
let bytes = self
.input
.get(self.offset..end)
.ok_or_else(|| invalid_data("truncated record"))?;
self.offset = end;
Ok(bytes)
}
fn expect_bytes(&mut self, expected: &[u8]) -> io::Result<()> {
if self.take(expected.len())? == expected {
Ok(())
} else {
Err(invalid_data("unexpected record bytes"))
}
}
fn u8(&mut self) -> io::Result<u8> {
Ok(self.take(1)?[0])
}
fn u16(&mut self) -> io::Result<u16> {
Ok(u16::from_le_bytes(self.array()?))
}
fn u32(&mut self) -> io::Result<u32> {
Ok(u32::from_le_bytes(self.array()?))
}
fn u64(&mut self) -> io::Result<u64> {
Ok(u64::from_le_bytes(self.array()?))
}
fn array_16(&mut self) -> io::Result<[u8; 16]> {
self.array()
}
fn array<const N: usize>(&mut self) -> io::Result<[u8; N]> {
self.take(N)?
.try_into()
.map_err(|_| invalid_data("truncated fixed-width field"))
}
fn count(&mut self) -> io::Result<usize> {
let count = self.u32()?;
if count > MAX_COLLECTION_COUNT {
return Err(invalid_data("collection count exceeds limit"));
}
usize::try_from(count).map_err(|_| invalid_data("collection count does not fit usize"))
}
fn string(&mut self) -> io::Result<String> {
let length = self.u32()?;
if length > MAX_STRING_LEN {
return Err(invalid_data("string length exceeds limit"));
}
let bytes = self.take(
usize::try_from(length)
.map_err(|_| invalid_data("string length does not fit usize"))?,
)?;
let value = std::str::from_utf8(bytes).map_err(|_| invalid_data("invalid UTF-8 string"))?;
Ok(value.to_owned())
}
fn finish(&self) -> io::Result<()> {
if self.offset == self.input.len() {
Ok(())
} else {
Err(invalid_data("record has trailing bytes"))
}
}
}
fn invalid_data(message: &str) -> io::Error {
io::Error::new(io::ErrorKind::InvalidData, message)
}
#[allow(dead_code)]
mod v1_codec {
use std::collections::{BTreeMap, VecDeque};
use std::io;
use super::{
CHECKPOINT_KIND, Cursor, DELTA_KIND, FORMAT_VERSION, MAGIC, MAX_COLLECTION_COUNT,
MAX_STRING_LEN, common_header, invalid_data,
};
use crate::BlockId;
use crate::file::state::v1::{
AllocationRun, BlockRange, LargeBlockData, LargeBlockId, LargeBlocks, LevelVersions,
RecordSeq, SegmentData, SegmentVersion, V1DeltaRecord, V1State, V1StateChange,
};
const OPTION_NONE: u8 = 0;
const OPTION_SOME: u8 = 1;
const MAX_SEGMENT_VERSION: u32 = 0x0fff_ffff;
const MAX_VALID_LARGE_BLOCK_ID: u64 = (1_u64 << 60) - 2;
pub(super) fn encode_checkpoint_payload(state: &V1State) -> io::Result<Vec<u8>> {
state.validate()?;
let mut output = Vec::new();
common_header(&mut output, CHECKPOINT_KIND);
for level in &state.levels {
output.extend_from_slice(&level.min_version.0.to_le_bytes());
encode_count(&mut output, level.versions.len())?;
for segment in &level.versions {
match segment {
None => output.push(OPTION_NONE),
Some(segment) => {
output.push(OPTION_SOME);
encode_count(&mut output, segment.allocation_runs.len())?;
for run in &segment.allocation_runs {
output.extend_from_slice(&run.allocated_at.get().to_le_bytes());
output.extend_from_slice(&run.len.to_le_bytes());
}
encode_count(&mut output, segment.released_at.len())?;
for released_at in &segment.released_at {
output.extend_from_slice(&released_at.get().to_le_bytes());
}
}
}
}
}
output.extend_from_slice(&state.large_blocks.next_id.0.to_le_bytes());
encode_count(&mut output, state.large_blocks.entries.len())?;
for (id, block) in &state.large_blocks.entries {
output.extend_from_slice(&id.0.to_le_bytes());
output.extend_from_slice(&block.allocated_at.get().to_le_bytes());
output.extend_from_slice(&block.released_at.get().to_le_bytes());
output.extend_from_slice(&block.logical_len.to_le_bytes());
}
encode_count(&mut output, state.roots.len())?;
for (raw, published_at) in &state.roots {
output.extend_from_slice(&raw.to_le_bytes());
output.extend_from_slice(&published_at.get().to_le_bytes());
}
encode_count(&mut output, state.bindings.len())?;
for (name, block) in &state.bindings {
encode_string(&mut output, name)?;
output.extend_from_slice(&u64::from(*block).to_le_bytes());
}
Ok(output)
}
pub(super) fn decode_checkpoint_payload(
payload: &[u8],
envelope_record_seq: RecordSeq,
) -> io::Result<V1State> {
let mut cursor = Cursor::new(payload);
cursor.expect_bytes(&MAGIC)?;
if cursor.u16()? != FORMAT_VERSION || cursor.u8()? != CHECKPOINT_KIND || cursor.u8()? != 0 {
return Err(invalid_data("invalid V1 checkpoint common header"));
}
let record_seq = RecordSeq::new(envelope_record_seq.get())?;
let mut levels = Vec::with_capacity(15);
for _ in 0..15 {
let min_version = SegmentVersion(cursor.u32()?);
let count = cursor.count()?;
let mut versions = VecDeque::with_capacity(count);
for _ in 0..count {
let segment = match cursor.u8()? {
OPTION_NONE => None,
OPTION_SOME => {
let run_count = cursor.count()?;
let mut allocation_runs = Vec::with_capacity(run_count);
for _ in 0..run_count {
allocation_runs.push(AllocationRun {
allocated_at: RecordSeq::new(cursor.u32()?)?,
len: cursor.u32()?,
});
}
let released_count = cursor.count()?;
let mut released_at = Vec::with_capacity(released_count);
for _ in 0..released_count {
released_at.push(decode_nullable_record_seq(&mut cursor)?);
}
Some(SegmentData {
allocation_runs,
released_at,
})
}
_ => return Err(invalid_data("invalid V1 segment option tag")),
};
versions.push_back(segment);
}
levels.push(LevelVersions {
min_version,
versions,
});
}
let levels: [LevelVersions; 15] = levels
.try_into()
.map_err(|_| invalid_data("invalid V1 level count"))?;
let next_id = LargeBlockId(cursor.u64()?);
let entries = decode_sorted_map(&mut cursor, |cursor| {
let id = LargeBlockId(cursor.u64()?);
let block = LargeBlockData {
allocated_at: RecordSeq::new(cursor.u32()?)?,
released_at: decode_nullable_record_seq(cursor)?,
logical_len: cursor.u64()?,
};
Ok((id, block))
})?;
let roots = decode_sorted_map(&mut cursor, |cursor| {
let raw = cursor.u64()?;
let published_at = RecordSeq::new(cursor.u32()?)?;
Ok((raw, published_at))
})?;
let bindings = decode_sorted_map(&mut cursor, |cursor| {
let name = cursor.string()?;
let block = BlockId::from_raw_unchecked(cursor.u64()?);
Ok((name, block))
})?;
cursor.finish()?;
let state = V1State {
record_seq,
levels,
large_blocks: LargeBlocks { next_id, entries },
roots,
bindings,
};
state.validate()?;
Ok(state)
}
pub(super) fn encode_delta_payload(delta: &V1DeltaRecord) -> io::Result<Vec<u8>> {
let mut output = Vec::new();
common_header(&mut output, DELTA_KIND);
encode_count(&mut output, delta.changes.len())?;
for change in &delta.changes {
encode_change(&mut output, change)?;
}
Ok(output)
}
pub(super) fn decode_delta_payload(payload: &[u8]) -> io::Result<V1DeltaRecord> {
let mut cursor = Cursor::new(payload);
cursor.expect_bytes(&MAGIC)?;
if cursor.u16()? != FORMAT_VERSION || cursor.u8()? != DELTA_KIND || cursor.u8()? != 0 {
return Err(invalid_data("invalid V1 delta common header"));
}
let count = cursor.count()?;
let mut changes = Vec::with_capacity(count);
for _ in 0..count {
changes.push(decode_change(&mut cursor)?);
}
cursor.finish()?;
Ok(V1DeltaRecord { changes })
}
fn encode_change(output: &mut Vec<u8>, change: &V1StateChange) -> io::Result<()> {
match change {
V1StateChange::CreateActiveSegment { level, version } => {
output.push(0);
encode_segment(output, *level, *version)?;
}
V1StateChange::AllocateSegmentBlocks {
level,
version,
len,
} => {
output.push(1);
encode_segment(output, *level, *version)?;
output.extend_from_slice(&len.to_le_bytes());
}
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges,
} => {
output.push(2);
encode_segment(output, *level, *version)?;
encode_count(output, ranges.len())?;
for range in ranges {
output.extend_from_slice(&range.start.to_le_bytes());
output.extend_from_slice(&range.len.to_le_bytes());
}
}
V1StateChange::RemoveSegment { level, version } => {
output.push(3);
encode_segment(output, *level, *version)?;
}
V1StateChange::AllocateLargeBlock { id, logical_len } => {
output.push(4);
encode_large_block_id(output, *id)?;
output.extend_from_slice(&logical_len.to_le_bytes());
}
V1StateChange::ReleaseLargeBlock { id } => {
output.push(5);
encode_large_block_id(output, *id)?;
}
V1StateChange::RemoveLargeBlock { id } => {
output.push(6);
encode_large_block_id(output, *id)?;
}
V1StateChange::AddRoot { block } => {
output.push(7);
encode_block_id(output, *block)?;
}
V1StateChange::RemoveRoot { block } => {
output.push(8);
encode_block_id(output, *block)?;
}
V1StateChange::AddBinding { name, block } => {
output.push(9);
encode_binding_name(output, name)?;
encode_block_id(output, *block)?;
}
V1StateChange::RemoveBinding { name } => {
output.push(10);
encode_binding_name(output, name)?;
}
}
Ok(())
}
fn decode_change(cursor: &mut Cursor<'_>) -> io::Result<V1StateChange> {
Ok(match cursor.u8()? {
0 => {
let (level, version) = decode_segment(cursor)?;
V1StateChange::CreateActiveSegment { level, version }
}
1 => {
let (level, version) = decode_segment(cursor)?;
V1StateChange::AllocateSegmentBlocks {
level,
version,
len: cursor.u32()?,
}
}
2 => {
let (level, version) = decode_segment(cursor)?;
let count = cursor.count()?;
let mut ranges = Vec::with_capacity(count);
for _ in 0..count {
ranges.push(BlockRange {
start: cursor.u32()?,
len: cursor.u32()?,
});
}
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges,
}
}
3 => {
let (level, version) = decode_segment(cursor)?;
V1StateChange::RemoveSegment { level, version }
}
4 => V1StateChange::AllocateLargeBlock {
id: decode_large_block_id(cursor)?,
logical_len: cursor.u64()?,
},
5 => V1StateChange::ReleaseLargeBlock {
id: decode_large_block_id(cursor)?,
},
6 => V1StateChange::RemoveLargeBlock {
id: decode_large_block_id(cursor)?,
},
7 => V1StateChange::AddRoot {
block: decode_block_id(cursor)?,
},
8 => V1StateChange::RemoveRoot {
block: decode_block_id(cursor)?,
},
9 => V1StateChange::AddBinding {
name: decode_binding_name(cursor)?,
block: decode_block_id(cursor)?,
},
10 => V1StateChange::RemoveBinding {
name: decode_binding_name(cursor)?,
},
_ => return Err(invalid_data("unknown V1 state change tag")),
})
}
fn encode_segment(output: &mut Vec<u8>, level: u8, version: SegmentVersion) -> io::Result<()> {
validate_segment(level, version)?;
output.push(level);
output.extend_from_slice(&version.0.to_le_bytes());
Ok(())
}
fn decode_segment(cursor: &mut Cursor<'_>) -> io::Result<(u8, SegmentVersion)> {
let level = cursor.u8()?;
let version = SegmentVersion(cursor.u32()?);
validate_segment(level, version)?;
Ok((level, version))
}
fn validate_segment(level: u8, version: SegmentVersion) -> io::Result<()> {
if level >= 15 || version.0 == 0 || version.0 > MAX_SEGMENT_VERSION {
Err(invalid_data("invalid V1 segment identity"))
} else {
Ok(())
}
}
fn encode_large_block_id(output: &mut Vec<u8>, id: LargeBlockId) -> io::Result<()> {
validate_large_block_id(id)?;
output.extend_from_slice(&id.0.to_le_bytes());
Ok(())
}
fn decode_large_block_id(cursor: &mut Cursor<'_>) -> io::Result<LargeBlockId> {
let id = LargeBlockId(cursor.u64()?);
validate_large_block_id(id)?;
Ok(id)
}
fn validate_large_block_id(id: LargeBlockId) -> io::Result<()> {
if id.0 == 0 || id.0 > MAX_VALID_LARGE_BLOCK_ID {
Err(invalid_data("invalid V1 large block id"))
} else {
Ok(())
}
}
fn encode_block_id(output: &mut Vec<u8>, block: BlockId) -> io::Result<()> {
let raw = u64::from(block);
BlockId::try_from(raw).map_err(|_| invalid_data("invalid V1 block id"))?;
output.extend_from_slice(&raw.to_le_bytes());
Ok(())
}
fn decode_block_id(cursor: &mut Cursor<'_>) -> io::Result<BlockId> {
BlockId::try_from(cursor.u64()?).map_err(|_| invalid_data("invalid V1 block id"))
}
fn encode_binding_name(output: &mut Vec<u8>, name: &str) -> io::Result<()> {
if name.is_empty() {
return Err(invalid_data("empty V1 binding name"));
}
encode_string(output, name)
}
fn decode_binding_name(cursor: &mut Cursor<'_>) -> io::Result<String> {
let name = cursor.string()?;
if name.is_empty() {
Err(invalid_data("empty V1 binding name"))
} else {
Ok(name)
}
}
fn encode_count(output: &mut Vec<u8>, count: usize) -> io::Result<()> {
let count = u32::try_from(count).map_err(|_| invalid_data("collection count overflow"))?;
if count > MAX_COLLECTION_COUNT {
return Err(invalid_data("collection count exceeds limit"));
}
output.extend_from_slice(&count.to_le_bytes());
Ok(())
}
fn encode_string(output: &mut Vec<u8>, value: &str) -> io::Result<()> {
let length =
u32::try_from(value.len()).map_err(|_| invalid_data("string length overflow"))?;
if length > MAX_STRING_LEN {
return Err(invalid_data("string length exceeds limit"));
}
output.extend_from_slice(&length.to_le_bytes());
output.extend_from_slice(value.as_bytes());
Ok(())
}
fn decode_nullable_record_seq(cursor: &mut Cursor<'_>) -> io::Result<RecordSeq> {
let value = cursor.u32()?;
if value == RecordSeq::NULL.get() {
Ok(RecordSeq::NULL)
} else {
RecordSeq::new(value)
}
}
fn decode_sorted_map<K: Ord + Clone, V>(
cursor: &mut Cursor<'_>,
mut decode: impl FnMut(&mut Cursor<'_>) -> io::Result<(K, V)>,
) -> io::Result<BTreeMap<K, V>> {
let count = cursor.count()?;
let mut output = BTreeMap::new();
let mut previous = None;
for _ in 0..count {
let (key, value) = decode(cursor)?;
if previous.as_ref().is_some_and(|item| item >= &key) {
return Err(invalid_data("collection is not strictly sorted"));
}
previous = Some(key.clone());
output.insert(key, value);
}
Ok(output)
}
}
#[cfg(test)]
mod v1_codec_tests {
use std::io;
use pi_append_log::{BlockDecoder, BlockEncoder, DefaultBlockCodec};
use crate::BlockId;
use crate::file::state::v1::{
BlockRange, LargeBlockId, RecordSeq, SegmentVersion, V1DeltaRecord, V1State, V1StateChange,
};
use super::v1_codec::{
decode_checkpoint_payload, decode_delta_payload, encode_checkpoint_payload,
encode_delta_payload,
};
use super::{
DELTA_KIND, MAGIC, V1Record, decode_v1_record_block, encode_v1_checkpoint_block,
encode_v1_delta_block, recover_v1_record_blocks,
};
fn first_level_option_tag_offset(payload: &[u8]) -> usize {
let mut offset = 0;
assert_eq!(
payload.get(offset..offset + MAGIC.len()),
Some(MAGIC.as_slice())
);
offset += MAGIC.len();
offset += size_of::<u16>();
offset += size_of::<u8>();
offset += size_of::<u8>();
offset += size_of::<u32>();
let count_end = offset + size_of::<u32>();
let version_count = u32::from_le_bytes(
payload[offset..count_end]
.try_into()
.expect("first V1 level version count should be present"),
);
assert!(
version_count > 0,
"initial V1 level should contain a version"
);
count_end
}
fn assert_invalid_data(result: io::Result<V1State>) {
let error = result.expect_err("malformed V1 checkpoint should be rejected");
assert_eq!(error.kind(), io::ErrorKind::InvalidData);
}
fn assert_invalid_delta_data(result: io::Result<V1DeltaRecord>) {
let error = result.expect_err("malformed V1 delta should be rejected");
assert_eq!(error.kind(), io::ErrorKind::InvalidData);
}
fn assert_invalid_v1_record_data(result: io::Result<V1Record>) {
match result {
Err(error) => assert_eq!(error.kind(), io::ErrorKind::InvalidData),
Ok(_) => panic!("invalid V1 record envelope sequence should be rejected"),
}
}
fn read_u32_at(payload: &[u8], offset: &mut usize) -> u32 {
let end = *offset + size_of::<u32>();
let value = u32::from_le_bytes(
payload[*offset..end]
.try_into()
.expect("encoded V1 delta u32 field should be present"),
);
*offset = end;
value
}
fn single_delta_change_offset(payload: &[u8], expected_tag: u8) -> usize {
let mut offset = 0;
assert_eq!(
payload.get(offset..offset + MAGIC.len()),
Some(MAGIC.as_slice())
);
offset += MAGIC.len();
offset += size_of::<u16>();
offset += size_of::<u8>();
offset += size_of::<u8>();
assert_eq!(read_u32_at(payload, &mut offset), 1);
assert_eq!(payload.get(offset), Some(&expected_tag));
offset + size_of::<u8>()
}
fn add_binding_target_offset(payload: &[u8]) -> usize {
let mut offset = single_delta_change_offset(payload, 9);
let name_len = usize::try_from(read_u32_at(payload, &mut offset))
.expect("encoded binding name length should fit usize");
offset
.checked_add(name_len)
.expect("encoded binding target offset should not overflow")
}
fn replace_raw_block_id(payload: &mut [u8], offset: usize, raw: u64) {
let end = offset + size_of::<u64>();
payload[offset..end].copy_from_slice(&raw.to_le_bytes());
}
fn replace_u32(payload: &mut [u8], offset: usize, value: u32) {
let end = offset + size_of::<u32>();
payload[offset..end].copy_from_slice(&value.to_le_bytes());
}
fn replace_u64(payload: &mut [u8], offset: usize, value: u64) {
let end = offset + size_of::<u64>();
payload[offset..end].copy_from_slice(&value.to_le_bytes());
}
fn envelope_crc32(bytes: &[u8]) -> u32 {
let mut crc = u32::MAX;
for byte in bytes {
crc ^= u32::from(*byte);
for _ in 0..8 {
let mask = 0_u32.wrapping_sub(crc & 1);
crc = (crc >> 1) ^ (0xedb8_8320 & mask);
}
}
!crc
}
fn v1_block_with_raw_envelope_sequence(payload: &[u8], sequence: u64) -> Vec<u8> {
let mut block = DefaultBlockCodec::default()
.encode(1, 0, payload)
.expect("append-log codec should encode a valid sequence fixture");
block[12..20].copy_from_slice(&sequence.to_le_bytes());
let crc_offset = block.len() - size_of::<u32>();
let crc = envelope_crc32(&block[..crc_offset]);
block[crc_offset..].copy_from_slice(&crc.to_le_bytes());
block
}
#[test]
fn v1_delta_codec_roundtrips_empty_changes() {
let delta = V1DeltaRecord {
changes: Vec::new(),
};
let payload = encode_delta_payload(&delta).expect("empty V1 delta should encode");
let decoded = decode_delta_payload(&payload).expect("empty V1 delta should decode");
assert_eq!(decoded, delta);
}
#[test]
fn v1_delta_codec_roundtrips_nonempty_ordered_changes() {
let level = 0;
let version = SegmentVersion(1);
let replacement_root = BlockId::from_raw_unchecked(
(u64::from(2_u32) << 32) | (u64::from(version.0) << 4) | u64::from(level),
);
let removed_root = BlockId::from_raw_unchecked(
(u64::from(3_u32) << 32) | (u64::from(version.0) << 4) | u64::from(level),
);
let mut base = V1State::initial();
base.apply_delta_record(
RecordSeq::new(2).expect("record sequence should be valid"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level,
version,
len: 4,
},
V1StateChange::AddRoot {
block: replacement_root,
},
V1StateChange::AddRoot {
block: removed_root,
},
V1StateChange::AddBinding {
name: "old".to_owned(),
block: removed_root,
},
],
},
)
.expect("nonempty V1 delta fixture should apply");
let delta = V1DeltaRecord {
changes: vec![
V1StateChange::RemoveRoot {
block: removed_root,
},
V1StateChange::ReleaseSegmentBlocks {
level,
version,
ranges: vec![BlockRange { start: 0, len: 2 }],
},
V1StateChange::RemoveBinding {
name: "old".to_owned(),
},
V1StateChange::AddBinding {
name: "current".to_owned(),
block: replacement_root,
},
],
};
let mut applied = base.clone();
applied
.apply_delta_record(
RecordSeq::new(3).expect("record sequence should be valid"),
&delta,
)
.expect("ordered V1 delta fixture should be legal");
let payload = encode_delta_payload(&delta)
.expect("nonempty V1 delta codec seam should encode ordered changes");
let decoded =
decode_delta_payload(&payload).expect("encoded nonempty V1 delta should decode");
assert_eq!(decoded.changes, delta.changes);
}
#[test]
fn v1_delta_codec_roundtrips_all_state_change_variants_in_order() {
let max_version = SegmentVersion(0x0fff_ffff);
let max_large_id = LargeBlockId((1_u64 << 60) - 2);
let ordinary_block = BlockId::from_raw_unchecked(
(u64::from(u32::MAX) << 32) | (u64::from(max_version.0) << 4) | 14,
);
let large_block = BlockId::from_raw_unchecked((max_large_id.0 << 4) | 15);
let delta = V1DeltaRecord {
changes: vec![
V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(1),
},
V1StateChange::AllocateSegmentBlocks {
level: 14,
version: max_version,
len: u32::MAX,
},
V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(1),
ranges: vec![BlockRange {
start: u32::MAX,
len: u32::MAX,
}],
},
V1StateChange::RemoveSegment {
level: 14,
version: max_version,
},
V1StateChange::AllocateLargeBlock {
id: max_large_id,
logical_len: u64::MAX,
},
V1StateChange::ReleaseLargeBlock {
id: LargeBlockId(1),
},
V1StateChange::RemoveLargeBlock { id: max_large_id },
V1StateChange::AddRoot {
block: ordinary_block,
},
V1StateChange::RemoveRoot { block: large_block },
V1StateChange::AddBinding {
name: "边界-根".to_owned(),
block: large_block,
},
V1StateChange::RemoveBinding {
name: "z".to_owned(),
},
],
};
let payload = encode_delta_payload(&delta).expect("all V1 changes should encode");
let decoded = decode_delta_payload(&payload).expect("all V1 changes should decode");
assert_eq!(decoded, delta);
}
#[test]
fn v1_delta_codec_roundtrips_gapped_release_ranges_in_order() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level: 3,
version: SegmentVersion(17),
ranges: vec![
BlockRange { start: 2, len: 3 },
BlockRange { start: 11, len: 5 },
],
}],
};
let payload = encode_delta_payload(&delta).expect("gapped ranges should encode");
let decoded = decode_delta_payload(&payload).expect("gapped ranges should decode");
assert_eq!(decoded.changes, delta.changes);
}
#[test]
fn v1_delta_codec_roundtrips_non_ascii_binding_name() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddBinding {
name: "主存储-🦀".to_owned(),
block: BlockId::from_raw_unchecked(0x10),
}],
};
let payload = encode_delta_payload(&delta).expect("non-ASCII binding should encode");
let decoded = decode_delta_payload(&payload).expect("non-ASCII binding should decode");
assert_eq!(decoded, delta);
}
#[test]
fn v1_delta_codec_rejects_unknown_change_tag() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddRoot {
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload = encode_delta_payload(&delta).expect("valid change should encode");
let fields_offset = single_delta_change_offset(&payload, 7);
payload[fields_offset - 1] = u8::MAX;
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_invalid_utf8_binding_name() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddBinding {
name: "valid".to_owned(),
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload = encode_delta_payload(&delta).expect("valid binding should encode");
let mut name_offset = single_delta_change_offset(&payload, 9);
let name_len = read_u32_at(&payload, &mut name_offset);
assert!(name_len > 0);
payload[name_offset] = 0xff;
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_trailing_payload_byte() {
let mut payload = encode_delta_payload(&V1DeltaRecord {
changes: Vec::new(),
})
.expect("empty delta should encode");
payload.push(0);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_invalid_segment_version_encodings() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::CreateActiveSegment {
level: 0,
version: SegmentVersion(1),
}],
};
let valid_payload = encode_delta_payload(&delta).expect("valid segment should encode");
let segment_offset = single_delta_change_offset(&valid_payload, 0);
let version_offset = segment_offset + size_of::<u8>();
for invalid_version in [0, 0x1000_0000] {
let mut payload = valid_payload.clone();
replace_u32(&mut payload, version_offset, invalid_version);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
}
#[test]
fn v1_delta_codec_rejects_invalid_large_block_id_encodings() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::ReleaseLargeBlock {
id: LargeBlockId(1),
}],
};
let valid_payload = encode_delta_payload(&delta).expect("valid large block should encode");
let id_offset = single_delta_change_offset(&valid_payload, 5);
for invalid_id in [0, (1_u64 << 60) - 1] {
let mut payload = valid_payload.clone();
replace_u64(&mut payload, id_offset, invalid_id);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
}
#[test]
fn v1_delta_codec_rejects_add_root_with_reserved_max_block_id() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddRoot {
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload = encode_delta_payload(&delta).expect("valid AddRoot delta should encode");
let block_offset = single_delta_change_offset(&payload, 7);
replace_raw_block_id(&mut payload, block_offset, u64::MAX);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_add_root_with_zero_segment_version() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddRoot {
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload = encode_delta_payload(&delta).expect("valid AddRoot delta should encode");
let block_offset = single_delta_change_offset(&payload, 7);
let ordinary_block_with_zero_segment_version = u64::from(1_u32) << 32;
replace_raw_block_id(
&mut payload,
block_offset,
ordinary_block_with_zero_segment_version,
);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_add_root_with_zero_large_block_id() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddRoot {
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload = encode_delta_payload(&delta).expect("valid AddRoot delta should encode");
let block_offset = single_delta_change_offset(&payload, 7);
replace_raw_block_id(&mut payload, block_offset, 15);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_delta_codec_rejects_add_binding_with_reserved_target_encoding() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AddBinding {
name: "root".to_owned(),
block: BlockId::from_raw_unchecked(0x10),
}],
};
let mut payload =
encode_delta_payload(&delta).expect("valid AddBinding delta should encode");
let target_offset = add_binding_target_offset(&payload);
replace_raw_block_id(&mut payload, target_offset, u64::MAX);
assert_invalid_delta_data(decode_delta_payload(&payload));
}
#[test]
fn v1_checkpoint_codec_uses_envelope_record_seq_instead_of_payload_field() {
let initial = V1State::initial();
let initial_payload =
encode_checkpoint_payload(&initial).expect("initial V1 state should encode");
let mut same_state_at_later_sequence = initial.clone();
same_state_at_later_sequence.record_seq =
RecordSeq::new(9).expect("record sequence should be valid");
let later_payload = encode_checkpoint_payload(&same_state_at_later_sequence)
.expect("record sequence should not affect checkpoint payload encoding");
assert_eq!(initial_payload, later_payload);
let decoded = decode_checkpoint_payload(
&initial_payload,
RecordSeq::new(9).expect("envelope record sequence should be valid"),
)
.expect("initial V1 checkpoint payload should decode");
let mut expected = V1State::initial();
expected.record_seq = RecordSeq::new(9).expect("record sequence should be valid");
assert_eq!(decoded.record_seq, RecordSeq(9));
assert_eq!(decoded, expected);
}
#[test]
fn v1_checkpoint_block_roundtrips_envelope_record_seq_without_payload_duplication() {
let initial = V1State::initial();
let initial_payload =
encode_checkpoint_payload(&initial).expect("initial V1 checkpoint should encode");
let mut later = initial.clone();
later.record_seq = RecordSeq::new(9).expect("later record sequence should be valid");
let later_payload =
encode_checkpoint_payload(&later).expect("later V1 checkpoint should encode");
assert_eq!(initial_payload, later_payload);
let block = encode_v1_checkpoint_block(&later).expect("V1 checkpoint block should encode");
let decoded = decode_v1_record_block(&block).expect("V1 checkpoint block should decode");
match decoded {
V1Record::Checkpoint { record_seq, state } => {
assert_eq!(record_seq, later.record_seq);
assert_eq!(state.record_seq, record_seq);
assert_eq!(state, later);
}
V1Record::Delta { .. } => panic!("checkpoint block decoded as Delta"),
}
}
#[test]
fn v1_delta_block_roundtrips_envelope_record_seq_and_preserves_change_order() {
let early_seq = RecordSeq::new(2).expect("early record sequence should be valid");
let later_seq = RecordSeq::new(9).expect("later record sequence should be valid");
let root = BlockId::from_raw_unchecked(0x10);
let delta = V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::AddRoot { block: root },
V1StateChange::AddBinding {
name: "primary".to_owned(),
block: root,
},
],
};
let early_block = encode_v1_delta_block(early_seq, &delta)
.expect("early ordered V1 Delta block should encode");
let later_block = encode_v1_delta_block(later_seq, &delta)
.expect("later ordered V1 Delta block should encode");
let codec = DefaultBlockCodec::default();
let early_envelope = codec
.decode_forward(&early_block)
.expect("early V1 Delta envelope should decode");
let later_envelope = codec
.decode_forward(&later_block)
.expect("later V1 Delta envelope should decode");
assert_eq!(early_envelope.block_seq(), u64::from(early_seq.get()));
assert_eq!(later_envelope.block_seq(), u64::from(later_seq.get()));
assert_eq!(early_envelope.payload(), later_envelope.payload());
let decoded =
decode_v1_record_block(&early_block).expect("early V1 Delta block should decode");
match decoded {
V1Record::Delta {
record_seq: decoded_seq,
delta: decoded_delta,
} => {
assert_eq!(decoded_seq, early_seq);
assert_eq!(decoded_delta.changes, delta.changes);
}
V1Record::Checkpoint { .. } => panic!("Delta block decoded as checkpoint"),
}
}
#[test]
fn decoded_v1_delta_envelope_sequences_drive_state_lifecycle_timestamps() {
let checkpoint = encode_v1_checkpoint_block(&V1State::initial())
.expect("initial V1 checkpoint block should encode");
let mut state = match decode_v1_record_block(&checkpoint)
.expect("initial V1 checkpoint block should decode")
{
V1Record::Checkpoint { state, .. } => state,
V1Record::Delta { .. } => panic!("initial checkpoint decoded as Delta"),
};
let ordinary_block = BlockId::from_raw_unchecked(0x10);
let large_id = LargeBlockId(1);
let large_block = BlockId::from_raw_unchecked((large_id.0 << 4) | 15);
let allocate_seq = RecordSeq::new(7).expect("allocation sequence should be valid");
let allocate_delta = V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
},
V1StateChange::AllocateLargeBlock {
id: large_id,
logical_len: 4096,
},
V1StateChange::AddRoot {
block: ordinary_block,
},
V1StateChange::AddRoot { block: large_block },
],
};
let allocate_block = encode_v1_delta_block(allocate_seq, &allocate_delta)
.expect("allocation Delta block should encode");
let (decoded_allocate_seq, decoded_allocate_delta) =
match decode_v1_record_block(&allocate_block)
.expect("allocation Delta block should decode")
{
V1Record::Delta { record_seq, delta } => (record_seq, delta),
V1Record::Checkpoint { .. } => panic!("allocation Delta decoded as checkpoint"),
};
state
.apply_delta_record(decoded_allocate_seq, &decoded_allocate_delta)
.expect("decoded allocation Delta should apply");
let release_seq = RecordSeq::new(11).expect("release sequence should be valid");
let release_delta = V1DeltaRecord {
changes: vec![
V1StateChange::RemoveRoot {
block: ordinary_block,
},
V1StateChange::RemoveRoot { block: large_block },
V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 0, len: 1 }],
},
V1StateChange::ReleaseLargeBlock { id: large_id },
],
};
let release_block = encode_v1_delta_block(release_seq, &release_delta)
.expect("release Delta block should encode");
let (decoded_release_seq, decoded_release_delta) = match decode_v1_record_block(
&release_block,
)
.expect("release Delta block should decode")
{
V1Record::Delta { record_seq, delta } => (record_seq, delta),
V1Record::Checkpoint { .. } => panic!("release Delta decoded as checkpoint"),
};
state
.apply_delta_record(decoded_release_seq, &decoded_release_delta)
.expect("decoded release Delta should apply");
let segment = state.levels[0].versions[0]
.as_ref()
.expect("initial active segment should remain present");
let large = state
.large_blocks
.entries
.get(&large_id)
.expect("released large block should remain until removal");
assert_eq!(state.record_seq, decoded_release_seq);
assert_eq!(
segment.allocation_runs[0].allocated_at,
decoded_allocate_seq
);
assert_eq!(segment.released_at[0], decoded_release_seq);
assert_eq!(large.allocated_at, decoded_allocate_seq);
assert_eq!(large.released_at, decoded_release_seq);
assert_eq!(
state.roots.get(&ordinary_block.0),
None,
"removed root should no longer be published"
);
let publication_state = match decode_v1_record_block(&allocate_block)
.expect("allocation Delta should remain decodable")
{
V1Record::Delta { record_seq, delta } => {
let mut state = V1State::initial();
state
.apply_delta_record(record_seq, &delta)
.expect("decoded allocation Delta should reapply to initial state");
state
}
V1Record::Checkpoint { .. } => panic!("allocation Delta decoded as checkpoint"),
};
assert_eq!(
publication_state.roots.get(&ordinary_block.0),
Some(&decoded_allocate_seq)
);
assert_eq!(
publication_state.roots.get(&large_block.0),
Some(&decoded_allocate_seq)
);
}
#[test]
fn v1_record_block_rejects_out_of_range_envelope_sequences() {
let payload = encode_delta_payload(&V1DeltaRecord {
changes: Vec::new(),
})
.expect("empty V1 Delta payload should encode");
for invalid_seq in [0_u64, u64::from(u32::MAX), u64::from(u32::MAX) + 1] {
let block = v1_block_with_raw_envelope_sequence(&payload, invalid_seq);
assert_invalid_v1_record_data(decode_v1_record_block(&block));
}
assert_eq!(payload[6], DELTA_KIND);
}
#[test]
fn v1_checkpoint_codec_roundtrips_nonempty_state() {
let mut state = V1State::initial();
let ordinary_block = BlockId::from_raw_unchecked(0x10);
let large_block_id = LargeBlockId(1);
let large_block = BlockId::from_raw_unchecked((large_block_id.0 << 4) | 15);
state
.apply_delta_record(
RecordSeq::new(2).expect("record sequence should be valid"),
&V1DeltaRecord {
changes: vec![
V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 2,
},
V1StateChange::AllocateLargeBlock {
id: large_block_id,
logical_len: 4096,
},
V1StateChange::AddRoot {
block: ordinary_block,
},
V1StateChange::AddRoot { block: large_block },
V1StateChange::AddBinding {
name: "primary".to_owned(),
block: large_block,
},
],
},
)
.expect("nonempty V1 state setup should apply");
state
.apply_delta_record(
RecordSeq::new(3).expect("record sequence should be valid"),
&V1DeltaRecord {
changes: vec![V1StateChange::ReleaseSegmentBlocks {
level: 0,
version: SegmentVersion(1),
ranges: vec![BlockRange { start: 1, len: 1 }],
}],
},
)
.expect("ordinary block release should apply");
let payload =
encode_checkpoint_payload(&state).expect("nonempty V1 checkpoint state should encode");
let decoded = decode_checkpoint_payload(&payload, state.record_seq)
.expect("nonempty V1 checkpoint payload should decode");
assert_eq!(decoded, state);
}
#[test]
fn v1_checkpoint_codec_rejects_unknown_first_level_option_tag() {
let mut payload =
encode_checkpoint_payload(&V1State::initial()).expect("initial V1 state should encode");
let option_tag_offset = first_level_option_tag_offset(&payload);
payload[option_tag_offset] = 2;
assert_invalid_data(decode_checkpoint_payload(&payload, RecordSeq(1)));
}
#[test]
fn v1_checkpoint_codec_rejects_trailing_payload_byte() {
let mut payload =
encode_checkpoint_payload(&V1State::initial()).expect("initial V1 state should encode");
payload.push(0);
assert_invalid_data(decode_checkpoint_payload(&payload, RecordSeq(1)));
}
#[test]
fn v1_checkpoint_codec_rejects_null_envelope_record_seq() {
let payload =
encode_checkpoint_payload(&V1State::initial()).expect("initial V1 state should encode");
assert_invalid_data(decode_checkpoint_payload(&payload, RecordSeq::NULL));
}
#[test]
fn v1_recovery_chain_accepts_single_checkpoint() {
let checkpoint = encode_v1_checkpoint_block(&V1State::initial())
.expect("initial V1 checkpoint block should encode");
let recovered = recover_v1_record_blocks([checkpoint.as_slice()])
.expect("single checkpoint chain should recover");
assert_eq!(recovered, V1State::initial());
}
#[test]
fn v1_recovery_chain_applies_delta_after_checkpoint_with_sequence_gap() {
let checkpoint = encode_v1_checkpoint_block(&V1State::initial())
.expect("initial V1 checkpoint block should encode");
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 2,
}],
};
let delta_block = encode_v1_delta_block(
RecordSeq::new(4).expect("gapped Delta sequence should be valid"),
&delta,
)
.expect("gapped V1 Delta block should encode");
let recovered = recover_v1_record_blocks([checkpoint.as_slice(), delta_block.as_slice()])
.expect("strictly increasing sequence gap should recover");
let segment = recovered.levels[0].versions[0]
.as_ref()
.expect("initial active segment should remain present");
assert_eq!(recovered.record_seq, RecordSeq(4));
assert_eq!(segment.allocation_runs.len(), 1);
assert_eq!(segment.allocation_runs[0].allocated_at, RecordSeq(4));
assert_eq!(segment.allocation_runs[0].len, 2);
assert_eq!(segment.released_at, vec![RecordSeq::NULL; 2]);
}
#[test]
fn v1_recovery_chain_rejects_delta_with_same_sequence_as_checkpoint() {
let mut checkpoint_state = V1State::initial();
checkpoint_state.record_seq = RecordSeq(4);
let checkpoint = encode_v1_checkpoint_block(&checkpoint_state)
.expect("sequence-four V1 checkpoint block should encode");
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
};
let delta_block = encode_v1_delta_block(RecordSeq(4), &delta)
.expect("same-sequence V1 Delta block should encode");
let error = recover_v1_record_blocks([checkpoint.as_slice(), delta_block.as_slice()])
.expect_err("same-sequence Delta must not return State");
assert_eq!(error.kind(), io::ErrorKind::InvalidData);
}
#[test]
fn v1_recovery_chain_rejects_delta_with_sequence_before_checkpoint() {
let mut checkpoint_state = V1State::initial();
checkpoint_state.record_seq = RecordSeq(4);
let checkpoint = encode_v1_checkpoint_block(&checkpoint_state)
.expect("sequence-four V1 checkpoint block should encode");
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
};
let delta_block = encode_v1_delta_block(RecordSeq(3), &delta)
.expect("earlier-sequence V1 Delta block should encode");
let error = recover_v1_record_blocks([checkpoint.as_slice(), delta_block.as_slice()])
.expect_err("earlier-sequence Delta must not return State");
assert_eq!(error.kind(), io::ErrorKind::InvalidData);
}
#[test]
fn v1_recovery_chain_accepts_delta_after_later_checkpoint() {
let mut checkpoint_state = V1State::initial();
checkpoint_state.record_seq = RecordSeq(4);
let checkpoint = encode_v1_checkpoint_block(&checkpoint_state)
.expect("sequence-four V1 checkpoint block should encode");
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
};
let delta_block = encode_v1_delta_block(RecordSeq(9), &delta)
.expect("sequence-nine V1 Delta block should encode");
let recovered = recover_v1_record_blocks([checkpoint.as_slice(), delta_block.as_slice()])
.expect("strictly later Delta should recover");
assert_eq!(recovered.record_seq, RecordSeq(9));
}
#[test]
fn v1_recovery_chain_applies_gapped_deltas_in_physical_order() {
let checkpoint = encode_v1_checkpoint_block(&V1State::initial())
.expect("initial V1 checkpoint block should encode");
let first_delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
};
let second_delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 2,
}],
};
let first_delta_block = encode_v1_delta_block(RecordSeq(4), &first_delta)
.expect("sequence-four V1 Delta block should encode");
let second_delta_block = encode_v1_delta_block(RecordSeq(9), &second_delta)
.expect("sequence-nine V1 Delta block should encode");
let recovered = recover_v1_record_blocks([
checkpoint.as_slice(),
first_delta_block.as_slice(),
second_delta_block.as_slice(),
])
.expect("gapped Deltas should recover in physical order");
let segment = recovered.levels[0].versions[0]
.as_ref()
.expect("initial active segment should remain present");
assert_eq!(recovered.record_seq, RecordSeq(9));
assert_eq!(segment.allocation_runs.len(), 2);
assert_eq!(segment.allocation_runs[0].allocated_at, RecordSeq(4));
assert_eq!(segment.allocation_runs[0].len, 1);
assert_eq!(segment.allocation_runs[1].allocated_at, RecordSeq(9));
assert_eq!(segment.allocation_runs[1].len, 2);
}
#[test]
fn v1_recovery_chain_rejects_delta_as_first_record() {
let delta = V1DeltaRecord {
changes: vec![V1StateChange::AllocateSegmentBlocks {
level: 0,
version: SegmentVersion(1),
len: 1,
}],
};
let delta_block = encode_v1_delta_block(RecordSeq(4), &delta)
.expect("first V1 Delta block should encode");
let error = recover_v1_record_blocks([delta_block.as_slice()])
.expect_err("Delta-first chain must not return State");
assert_eq!(error.kind(), io::ErrorKind::InvalidData);
}
}