use alloc::vec::Vec;
use core::{alloc::Allocator, convert::Infallible};
use sha2::{Digest, Sha256};
use super::{Error, Map};
const MAGIC: &[u8; 8] = b"NKEYMAP1";
const HEADER: usize = 24;
const DIGEST: usize = 32;
#[derive(Debug, PartialEq, Eq)]
pub enum ExportError<E> {
Map(Error),
Sink(E),
}
#[derive(Debug, PartialEq, Eq)]
pub enum ImportError<E> {
Map(Error),
Source(E),
}
pub fn export_records<E>(
count: usize,
epoch: u64,
records: impl IntoIterator<Item = (u64, u64)>,
mut sink: impl FnMut(&[u8]) -> Result<(), E>,
) -> Result<(), ExportError<E>> {
encoded_length(count).map_err(ExportError::Map)?;
let mut digest = Sha256::new();
let mut write = |bytes: &[u8]| {
digest.update(bytes);
sink(bytes).map_err(ExportError::Sink)
};
write(MAGIC)?;
write(&epoch.to_le_bytes())?;
write(&(count as u64).to_le_bytes())?;
let mut seen = 0;
for (key, value) in records {
if seen == count {
return Err(ExportError::Map(Error::Checkpoint));
}
let mut record = [0; 16];
record[..8].copy_from_slice(&key.to_le_bytes());
record[8..].copy_from_slice(&value.to_le_bytes());
write(&record)?;
seen += 1;
}
if seen != count {
return Err(ExportError::Map(Error::Checkpoint));
}
sink(&digest.finalize()).map_err(ExportError::Sink)
}
impl Map {
pub fn records_from_checkpoint(
bytes: &[u8],
epoch: u64,
limit: usize,
) -> Result<Vec<(u64, u64)>, Error> {
let payload = checked_payload(bytes, epoch, limit)?;
let mut records = Vec::new();
records
.try_reserve_exact(payload.len() / 16)
.map_err(|_| Error::Allocation)?;
for record in payload.as_chunks::<16>().0 {
records.push((word(&record[..8]), word(&record[8..])));
}
records.sort_unstable_by_key(|record| record.0);
if records.windows(2).any(|pair| pair[0].0 == pair[1].0) {
return Err(Error::Checkpoint);
}
Ok(records)
}
pub fn from_checkpoint(bytes: &[u8], epoch: u64, limit: usize) -> Result<Self, Error> {
Self::from_checkpoint_in(bytes, epoch, limit, alloc::alloc::Global)
}
pub fn from_reader<E>(
length: usize,
epoch: u64,
limit: usize,
read_exact: impl FnMut(&mut [u8]) -> Result<(), E>,
) -> Result<Self, ImportError<E>> {
Self::from_reader_in(length, epoch, limit, alloc::alloc::Global, read_exact)
}
}
impl<A: Allocator + Clone> Map<A> {
pub fn export<E>(
&self,
epoch: u64,
sink: impl FnMut(&[u8]) -> Result<(), E>,
) -> Result<(), ExportError<E>> {
self.healthy().map_err(ExportError::Map)?;
export_records(
self.len,
epoch,
self.slots
.iter()
.filter(|slot| slot.occupied == 1)
.map(|slot| (slot.key, slot.value)),
sink,
)
}
pub fn checkpoint(&self, epoch: u64) -> Result<Vec<u8>, Error> {
self.healthy()?;
let length = encoded_length(self.len)?;
let mut bytes = Vec::new();
bytes
.try_reserve_exact(length)
.map_err(|_| Error::Allocation)?;
let result = self.export(epoch, |part| {
bytes.extend_from_slice(part);
Ok::<_, Infallible>(())
});
match result {
Ok(()) => Ok(bytes),
Err(ExportError::Map(error)) => Err(error),
Err(ExportError::Sink(never)) => match never {},
}
}
pub fn from_checkpoint_in(
bytes: &[u8],
epoch: u64,
limit: usize,
allocator: A,
) -> Result<Self, Error> {
let payload = checked_payload(bytes, epoch, limit)?;
let mut candidate = Self::new_in(limit, allocator);
candidate.reserve(payload.len() / 16)?;
insert_records(&mut candidate, payload)?;
Ok(candidate)
}
pub fn from_reader_in<E>(
length: usize,
epoch: u64,
limit: usize,
allocator: A,
mut read_exact: impl FnMut(&mut [u8]) -> Result<(), E>,
) -> Result<Self, ImportError<E>> {
if length < HEADER + DIGEST {
return Err(ImportError::Map(Error::Checkpoint));
}
let mut header = [0; HEADER];
read_exact(&mut header).map_err(ImportError::Source)?;
let count = header_count(&header, length, epoch, limit).map_err(ImportError::Map)?;
let mut digest = Sha256::new();
digest.update(header);
let mut candidate = Self::new_in(limit, allocator);
candidate.reserve(count).map_err(ImportError::Map)?;
let mut buffer = [0; 4096];
let mut remaining = count;
while remaining != 0 {
let records = remaining.min(buffer.len() / 16);
let chunk = &mut buffer[..records * 16];
read_exact(chunk).map_err(ImportError::Source)?;
digest.update(&*chunk);
insert_records(&mut candidate, chunk).map_err(ImportError::Map)?;
remaining -= records;
}
let mut expected = [0; DIGEST];
read_exact(&mut expected).map_err(ImportError::Source)?;
if digest.finalize().as_slice() != expected {
return Err(ImportError::Map(Error::Integrity));
}
Ok(candidate)
}
pub fn recover(&mut self, bytes: &[u8], epoch: u64) -> Result<(), Error> {
let candidate =
Self::from_checkpoint_in(bytes, epoch, self.limit, self.slots.allocator().clone())?;
*self = candidate;
Ok(())
}
}
fn checked_payload(bytes: &[u8], epoch: u64, limit: usize) -> Result<&[u8], Error> {
if bytes.len() < HEADER + DIGEST {
return Err(Error::Checkpoint);
}
header_count(&bytes[..HEADER], bytes.len(), epoch, limit)?;
let end = bytes.len() - DIGEST;
if Sha256::digest(&bytes[..end]).as_slice() != &bytes[end..] {
return Err(Error::Integrity);
}
Ok(&bytes[HEADER..end])
}
fn header_count(header: &[u8], length: usize, epoch: u64, limit: usize) -> Result<usize, Error> {
if &header[..8] != MAGIC {
return Err(Error::Checkpoint);
}
if word(&header[8..16]) != epoch {
return Err(Error::Epoch);
}
let count = usize::try_from(word(&header[16..24])).map_err(|_| Error::Limit)?;
if count > limit {
return Err(Error::Limit);
}
if encoded_length(count)? != length {
return Err(Error::Checkpoint);
}
Ok(count)
}
fn insert_records<A: Allocator + Clone>(map: &mut Map<A>, bytes: &[u8]) -> Result<(), Error> {
map.with(|mut view| {
for record in bytes.as_chunks::<16>().0 {
if view
.insert(word(&record[..8]), word(&record[8..]))?
.is_some()
{
return Err(Error::Checkpoint);
}
}
Ok(())
})?
}
fn encoded_length(count: usize) -> Result<usize, Error> {
count
.checked_mul(16)
.and_then(|bytes| bytes.checked_add(HEADER + DIGEST))
.ok_or(Error::Limit)
}
fn word(bytes: &[u8]) -> u64 {
let mut word = [0; 8];
word.copy_from_slice(bytes);
u64::from_le_bytes(word)
}