use crate::backend::api::{Backend, KeyRange, Op, ScanRequest, Table};
use crate::codec::MAX_DECODED_BYTES;
use crate::error::{Error, Result};
pub const POINTER_MAGIC: [u8; 4] = *b"CCHK";
pub const POINTER_VERSION: u8 = 1;
pub const POINTER_LEN: usize = 26;
pub const FLAG_POSTCARD: u8 = 0;
pub const FLAG_RAW: u8 = 1;
const META_NEXT_VALUE_ID: &[u8] = b"next_value_id";
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ChunkPointer {
pub value_id: u64,
pub n_chunks: u32,
pub total_len: u64,
pub flags: u8,
}
impl ChunkPointer {
pub fn encode(self) -> Vec<u8> {
let mut out = Vec::with_capacity(POINTER_LEN);
out.extend_from_slice(&POINTER_MAGIC);
out.push(POINTER_VERSION);
out.push(self.flags);
out.extend_from_slice(&self.value_id.to_be_bytes());
out.extend_from_slice(&self.n_chunks.to_be_bytes());
out.extend_from_slice(&self.total_len.to_be_bytes());
out
}
pub fn parse(raw: &[u8]) -> Result<Self> {
if raw.len() != POINTER_LEN || raw[0..4] != POINTER_MAGIC {
return Err(Error::Corrupt("not a chunk pointer".into()));
}
if raw[4] != POINTER_VERSION {
return Err(Error::UnsupportedVersion {
found: raw[4],
supported: POINTER_VERSION,
});
}
let n_chunks = u32::from_be_bytes(raw[14..18].try_into().expect("length checked above"));
let total_len = u64::from_be_bytes(raw[18..26].try_into().expect("length checked above"));
if total_len > MAX_DECODED_BYTES as u64 {
return Err(Error::Corrupt(format!(
"chunk pointer declares {total_len} bytes, over the \
{MAX_DECODED_BYTES} byte limit"
)));
}
if u64::from(n_chunks) > total_len {
return Err(Error::Corrupt(format!(
"chunk pointer declares {n_chunks} chunks for {total_len} bytes; \
a chunk holds at least one byte"
)));
}
Ok(Self {
flags: raw[5],
value_id: u64::from_be_bytes(raw[6..14].try_into().expect("length checked above")),
n_chunks,
total_len,
})
}
}
pub fn is_pointer(raw: &[u8]) -> bool {
raw.len() >= 4 && raw[0..4] == POINTER_MAGIC
}
pub fn chunk_key(value_id: u64, seq: u32) -> Vec<u8> {
let mut k = Vec::with_capacity(12);
k.extend_from_slice(&value_id.to_be_bytes());
k.extend_from_slice(&seq.to_be_bytes());
k
}
pub fn chunk_range(value_id: u64) -> KeyRange {
KeyRange::prefix(&value_id.to_be_bytes())
}
pub fn next_value_id_key() -> &'static [u8] {
META_NEXT_VALUE_ID
}
fn counter_op_for(next: u64) -> Op {
Op::Put {
table: Table::Meta,
key: META_NEXT_VALUE_ID.to_vec(),
value: next.to_be_bytes().to_vec(),
}
}
pub fn parse_counter(raw: Option<&[u8]>) -> Result<u64> {
match raw {
None => Ok(0),
Some(bytes) => <[u8; 8]>::try_from(bytes)
.map(u64::from_be_bytes)
.map_err(|_| Error::Corrupt("next_value_id is not an 8-byte integer".into())),
}
}
#[derive(Debug, Default)]
pub struct ValueIds {
next: std::sync::Mutex<Option<u64>>,
}
impl ValueIds {
fn take(&self) -> Result<Option<u64>> {
let mut guard = self
.next
.lock()
.map_err(|_| Error::backend("value id cursor was poisoned"))?;
match *guard {
None => Ok(None),
Some(id) => {
*guard = Some(advance(id)?);
Ok(Some(id))
}
}
}
fn seed_and_take(&self, stored: u64) -> Result<u64> {
let mut guard = self
.next
.lock()
.map_err(|_| Error::backend("value id cursor was poisoned"))?;
let id = match *guard {
Some(current) => current.max(stored),
None => stored,
};
*guard = Some(advance(id)?);
Ok(id)
}
pub async fn allocate(&self, backend: &dyn Backend) -> Result<u64> {
if let Some(id) = self.take()? {
return Ok(id);
}
let floor = seed_floor(backend).await?;
self.seed_and_take(floor)
}
pub(crate) fn counter_op(&self) -> Result<Option<Op>> {
let guard = self
.next
.lock()
.map_err(|_| Error::backend("value id cursor was poisoned"))?;
Ok(guard.map(counter_op_for))
}
}
async fn seed_floor(backend: &dyn Backend) -> Result<u64> {
let raw = backend.get(Table::Meta, META_NEXT_VALUE_ID).await?;
let stored = parse_counter(raw.as_deref())?;
match highest_stored_id(backend).await? {
Some(id) => Ok(stored.max(advance(id)?)),
None => Ok(stored),
}
}
async fn highest_stored_id(backend: &dyn Backend) -> Result<Option<u64>> {
let page = backend
.scan(ScanRequest {
table: Table::Chunks,
range: KeyRange::all(),
reverse: true,
limit: 1,
want_values: false,
})
.await?;
let Some((key, _)) = page.items.first() else {
return Ok(None);
};
let head: [u8; 8] = key
.get(0..8)
.and_then(|head| head.try_into().ok())
.ok_or_else(|| Error::Corrupt("a chunk key is shorter than a value id".into()))?;
Ok(Some(u64::from_be_bytes(head)))
}
fn advance(id: u64) -> Result<u64> {
id.checked_add(1)
.ok_or_else(|| Error::backend("value id space is exhausted"))
}
pub fn gc_ops(pointer: &ChunkPointer) -> Op {
Op::DeleteRange {
table: Table::Chunks,
range: chunk_range(pointer.value_id),
}
}
#[cfg(test)]
mod tests {
use super::*;
use futures::executor::block_on;
#[test]
fn an_unseeded_cursor_writes_no_counter_op() {
let ids = ValueIds::default();
assert!(ids.counter_op().unwrap().is_none());
let seeded = ValueIds::default();
block_on(seeded.allocate(&crate::backend::MemoryBackend::new())).unwrap();
assert!(
seeded.counter_op().unwrap().is_some(),
"a cursor that has handed an id out must persist its high-water mark"
);
}
#[test]
fn pointer_round_trips() {
let p = ChunkPointer {
value_id: 42,
n_chunks: 3,
total_len: 1000,
flags: FLAG_POSTCARD,
};
let encoded = p.encode();
assert_eq!(encoded.len(), POINTER_LEN);
assert!(is_pointer(&encoded));
assert_eq!(ChunkPointer::parse(&encoded).unwrap(), p);
}
#[test]
fn an_absurd_chunk_count_is_refused() {
let raw = ChunkPointer {
value_id: 42,
n_chunks: u32::MAX,
total_len: 1000,
flags: FLAG_POSTCARD,
}
.encode();
assert!(matches!(ChunkPointer::parse(&raw), Err(Error::Corrupt(_))));
}
#[test]
fn a_length_past_the_envelope_ceiling_is_refused() {
let raw = ChunkPointer {
value_id: 42,
n_chunks: 1,
total_len: MAX_DECODED_BYTES as u64 + 1,
flags: FLAG_POSTCARD,
}
.encode();
assert!(matches!(ChunkPointer::parse(&raw), Err(Error::Corrupt(_))));
}
#[test]
fn an_empty_streamed_value_is_still_a_legal_pointer() {
let p = ChunkPointer {
value_id: 7,
n_chunks: 0,
total_len: 0,
flags: FLAG_RAW,
};
assert_eq!(ChunkPointer::parse(&p.encode()).unwrap(), p);
}
#[test]
fn inline_envelopes_are_not_pointers() {
assert!(!is_pointer(b"CBNK...."));
assert!(!is_pointer(b"short"));
}
}