use super::publication_anchor::{RootRef, REGION_LEN};
use crate::creation_options::FormatMode;
use crate::crypto::{open_with_nonce, seal_with_random_nonce, strong_checksum};
use crate::page_buffer::ZeroizingBytes;
use crate::storage::Storage;
use crate::{Error, LockboxId, Result};
use sha2::Sha256;
use zeroize::Zeroizing;
mod cache;
pub(crate) use cache::PageCache;
mod borrowed;
pub(crate) use borrowed::{EntryRef, VisitRef};
const MAGIC: &[u8; 8] = b"RV4IDX02";
const HEADER: usize = 44;
const MAX_NODE: usize = 65536;
const BODY_HEADER: usize = 11;
const MAX_BODY: usize = MAX_NODE - HEADER - 16;
const MAX_ITEMS: usize = 1024;
const MAX_HEIGHT: u8 = 32;
const MAX_KEY: usize = 4096;
const MAX_VALUE: usize = 49152;
const MAX_ENTRIES: u64 = 1_000_000;
pub(crate) enum Visit {
Page(RootRef),
Entry(Entry),
}
#[derive(Clone)]
pub(crate) struct Entry {
pub namespace: u8,
pub key: Zeroizing<Vec<u8>>,
pub value: Zeroizing<Vec<u8>>,
}
impl Entry {
pub(crate) fn new(namespace: u8, key: &[u8], value: &[u8]) -> Result<Self> {
validate_input(key, value)?;
Ok(Self {
namespace,
key: Zeroizing::new(key.to_vec()),
value: Zeroizing::new(value.to_vec()),
})
}
fn identity(&self) -> (u8, &[u8]) {
(self.namespace, &self.key)
}
fn size(&self) -> usize {
7 + self.key.len() + self.value.len()
}
}
#[derive(Clone)]
struct Key {
namespace: u8,
bytes: Zeroizing<Vec<u8>>,
}
impl Key {
fn new(identity: (u8, &[u8])) -> Self {
Self {
namespace: identity.0,
bytes: Zeroizing::new(identity.1.to_vec()),
}
}
fn identity(&self) -> (u8, &[u8]) {
(self.namespace, &self.bytes)
}
}
#[derive(Clone)]
struct Link {
reference: RootRef,
count: u64,
first: Key,
}
impl Link {
fn size(&self) -> usize {
67 + self.first.bytes.len()
}
}
#[derive(Clone)]
enum Node {
Leaf(Vec<Entry>),
Branch { height: u8, children: Vec<Link> },
}
impl Node {
fn count(&self) -> u64 {
match self {
Self::Leaf(entries) => entries.len() as u64,
Self::Branch { children, .. } => children.iter().map(|c| c.count).sum(),
}
}
fn height(&self) -> u8 {
match self {
Self::Leaf(_) => 0,
Self::Branch { height, .. } => *height,
}
}
fn first(&self) -> Option<(u8, &[u8])> {
match self {
Self::Leaf(entries) => entries.first().map(Entry::identity),
Self::Branch { children, .. } => children.first().map(|c| c.first.identity()),
}
}
fn last(&self) -> Option<(u8, &[u8])> {
match self {
Self::Leaf(entries) => entries.last().map(Entry::identity),
Self::Branch { children, .. } => children.last().map(|c| c.first.identity()),
}
}
fn body_len(&self) -> usize {
BODY_HEADER
+ match self {
Self::Leaf(entries) => entries.iter().map(Entry::size).sum::<usize>(),
Self::Branch { children, .. } => children.iter().map(Link::size).sum(),
}
}
fn item_count(&self) -> usize {
match self {
Self::Leaf(entries) => entries.len(),
Self::Branch { children, .. } => children.len(),
}
}
fn pack(self) -> Vec<Self> {
match self {
Self::Leaf(entries) => pack(entries, Entry::size)
.into_iter()
.map(Self::Leaf)
.collect(),
Self::Branch { height, children } => pack(children, Link::size)
.into_iter()
.map(|children| Self::Branch { height, children })
.collect(),
}
}
fn append(&mut self, other: Self) -> Result<()> {
match (self, other) {
(Self::Leaf(left), Self::Leaf(mut right)) => left.append(&mut right),
(
Self::Branch { height, children },
Self::Branch {
height: other_height,
children: mut other,
},
) if *height == other_height => children.append(&mut other),
_ => return Err(Error::CorruptRecord),
}
Ok(())
}
}
pub(crate) struct Change {
pub root: RootRef,
pub created: Vec<RootRef>,
pub retired: Vec<RootRef>,
}
impl Change {
fn new(root: RootRef) -> Self {
Self {
root,
created: Vec::new(),
retired: Vec::new(),
}
}
}
pub(crate) struct RecoveryReport {
pub recovered: u64,
pub unavailable: u64,
pub damaged_pages: Vec<RootRef>,
}
pub(crate) struct Index {
archive: LockboxId,
mode: FormatMode,
key: Option<Zeroizing<[u8; 32]>>,
}
impl Index {
pub(crate) fn new(archive: LockboxId, mode: FormatMode, key: Option<&[u8]>) -> Result<Self> {
FormatMode::parse(mode.0)?;
if mode.plaintext() != key.is_none() || key.is_some_and(|k| k.len() != 32) {
return Err(Error::InvalidKey);
}
let key = key.map(|key| {
let mut derived = Zeroizing::new([0; 32]);
hkdf::Hkdf::<Sha256>::new(Some(archive.as_bytes()), key)
.expand(b"revault-candidate-packed-index-key-v1\0", &mut *derived)
.expect("fixed SHA-256 key length");
derived
});
Ok(Self { archive, mode, key })
}
pub(crate) fn empty(&self, storage: &mut impl Storage) -> Result<RootRef> {
Ok(self.write(storage, &Node::Leaf(Vec::new()))?.reference)
}
pub(crate) fn get(
&self,
storage: &impl Storage,
root: RootRef,
sealed: u64,
namespace: u8,
key: &[u8],
) -> Result<Option<Entry>> {
validate_input(key, &[])?;
let identity = (namespace, key);
let mut node = self.read(storage, root, sealed)?;
let mut upper: Option<Key> = None;
loop {
match node {
Node::Leaf(entries) => {
return Ok(entries
.binary_search_by(|e| e.identity().cmp(&identity))
.ok()
.map(|i| entries[i].clone()))
}
Node::Branch { height, children } => {
let position = children.partition_point(|c| c.first.identity() <= identity);
if position == 0 {
return Ok(None);
}
let position = position - 1;
if let Some(next) = children.get(position + 1) {
upper = Some(next.first.clone());
}
node =
self.child(storage, &children[position], height, sealed, upper.as_ref())?;
}
}
}
}
pub(crate) fn put(
&self,
storage: &mut impl Storage,
root: RootRef,
sealed: u64,
entry: Entry,
) -> Result<Change> {
validate_input(&entry.key, &entry.value)?;
self.mutate(storage, root, sealed, entry.identity(), Some(&entry))
}
pub(crate) fn remove(
&self,
storage: &mut impl Storage,
root: RootRef,
sealed: u64,
namespace: u8,
key: &[u8],
) -> Result<Change> {
validate_input(key, &[])?;
self.mutate(storage, root, sealed, (namespace, key), None)
}
fn mutate(
&self,
storage: &mut impl Storage,
root: RootRef,
sealed: u64,
identity: (u8, &[u8]),
replacement: Option<&Entry>,
) -> Result<Change> {
let node = self.read(storage, root, sealed)?;
let mut change = Change::new(root);
let Some(mut nodes) = self.edit(
storage,
root,
node,
sealed,
None,
identity,
replacement,
&mut change,
)?
else {
return Ok(change);
};
if nodes.len() > 1 {
let height = nodes[0]
.height()
.checked_add(1)
.ok_or(Error::CorruptRecord)?;
if height > MAX_HEIGHT {
return Err(Error::SecurityLimitExceeded("index height limit".into()));
}
let children = nodes
.iter()
.map(|node| self.write_tracked(storage, node, &mut change))
.collect::<Result<Vec<_>>>()?;
nodes = vec![Node::Branch { height, children }];
}
let node = nodes.pop().unwrap_or(Node::Leaf(Vec::new()));
if let Node::Branch { ref children, .. } = node {
if children.len() == 1 {
let mut link = children[0].clone();
let mut parent_height = node.height();
loop {
let child = self.child(storage, &link, parent_height, storage.len()?, None)?;
if let Node::Branch { height, children } = child {
if children.len() == 1 {
change.retired.push(link.reference);
link = children[0].clone();
parent_height = height;
continue;
}
}
change.root = link.reference;
return Ok(change);
}
}
}
change.root = self.write_tracked(storage, &node, &mut change)?.reference;
Ok(change)
}
#[allow(clippy::too_many_arguments)]
fn edit(
&self,
storage: &mut impl Storage,
old: RootRef,
node: Node,
sealed: u64,
upper: Option<&Key>,
identity: (u8, &[u8]),
replacement: Option<&Entry>,
change: &mut Change,
) -> Result<Option<Vec<Node>>> {
let next = match node {
Node::Leaf(mut entries) => {
match (
entries.binary_search_by(|e| e.identity().cmp(&identity)),
replacement,
) {
(Ok(i), Some(entry)) => {
if entries[i].value == entry.value {
return Ok(None);
}
entries[i] = entry.clone();
}
(Err(i), Some(entry)) => entries.insert(i, entry.clone()),
(Ok(i), None) => {
entries.remove(i);
}
(Err(_), None) => return Ok(None),
}
Node::Leaf(entries)
}
Node::Branch {
height,
mut children,
} => {
let position = children
.partition_point(|c| c.first.identity() <= identity)
.saturating_sub(1);
let bound = children.get(position + 1).map(|c| &c.first).or(upper);
let child = self.child(storage, &children[position], height, sealed, bound)?;
let Some(mut changed) = self.edit(
storage,
children[position].reference,
child,
sealed,
bound,
identity,
replacement,
change,
)?
else {
return Ok(None);
};
let mut start = position;
let mut end = position + 1;
if changed.len() == 1 && changed[0].body_len() < MAX_BODY / 3 && children.len() > 1
{
let sibling = if position > 0 {
position - 1
} else {
position + 1
};
let bound = children.get(sibling + 1).map(|c| &c.first).or(upper);
let neighbor =
self.child(storage, &children[sibling], height, sealed, bound)?;
let combined = if sibling < position {
let mut combined = neighbor;
combined.append(changed.remove(0))?;
combined
} else {
let mut combined = changed.remove(0);
combined.append(neighbor)?;
combined
};
changed = combined.pack();
change.retired.push(children[sibling].reference);
start = start.min(sibling);
end = end.max(sibling + 1);
}
let links = changed
.iter()
.filter(|node| node.count() > 0)
.map(|node| self.write_tracked(storage, node, change))
.collect::<Result<Vec<_>>>()?;
children.splice(start..end, links);
Node::Branch { height, children }
}
};
if next.count() > MAX_ENTRIES {
return Err(Error::SecurityLimitExceeded("index entry limit".into()));
}
change.retired.push(old);
Ok(Some(if next.count() == 0 {
Vec::new()
} else {
next.pack()
}))
}
pub(crate) fn fixed_record_size_bound(
&self,
count: u64,
key_len: usize,
value_len: usize,
) -> Result<u64> {
Ok(self.fixed_record_geometry(count, key_len, value_len)?.0)
}
pub(crate) fn fixed_record_node_bound(
&self,
count: u64,
key_len: usize,
value_len: usize,
) -> Result<u64> {
Ok(self.fixed_record_geometry(count, key_len, value_len)?.1)
}
fn fixed_record_geometry(
&self,
count: u64,
key_len: usize,
value_len: usize,
) -> Result<(u64, u64)> {
if count > MAX_ENTRIES || key_len > MAX_KEY || value_len > MAX_VALUE {
return Err(Error::SecurityLimitExceeded("bulk size bound".into()));
}
let mut item_size = 7 + key_len + value_len;
let mut capacity = ((MAX_BODY - BODY_HEADER) / item_size).min(MAX_ITEMS) as u64;
if capacity == 0 {
return Err(Error::CorruptRecord);
}
let mut items = count;
let mut total = 0;
let mut nodes = 0;
loop {
let pages = items.div_ceil(capacity).max(1);
let bytes = if self.mode.unpadded() {
pages * (HEADER + BODY_HEADER + if self.key.is_some() { 16 } else { 0 }) as u64
+ items * item_size as u64
} else {
pages * MAX_NODE as u64
};
total += 2 * bytes;
nodes += pages;
if pages == 1 {
return Ok((total, nodes));
}
items = pages;
item_size = 67 + key_len;
capacity = ((MAX_BODY - BODY_HEADER) / item_size).min(MAX_ITEMS) as u64;
if capacity < 2 {
return Err(Error::CorruptRecord);
}
}
}
pub(crate) fn build_sorted(
&self,
storage: &mut impl Storage,
entries: impl IntoIterator<Item = Result<Entry>>,
) -> Result<Change> {
let mut change = Change::new(RootRef::default());
let mut leaf = Vec::new();
let mut size = BODY_HEADER;
let mut frontier: Vec<Vec<Link>> = Vec::new();
let mut previous: Option<Key> = None;
let mut count = 0u64;
for entry in entries {
let entry = entry?;
validate_input(&entry.key, &entry.value)?;
if previous
.as_ref()
.is_some_and(|p| p.identity() >= entry.identity())
{
return Err(Error::InvalidInput(
"bulk index input must have strictly increasing identities".into(),
));
}
count += 1;
if count > MAX_ENTRIES {
return Err(Error::SecurityLimitExceeded("index entry limit".into()));
}
previous = Some(Key::new(entry.identity()));
if size + entry.size() > MAX_BODY || leaf.len() == MAX_ITEMS {
let link = self.write_tracked(
storage,
&Node::Leaf(std::mem::take(&mut leaf)),
&mut change,
)?;
self.push_frontier(storage, &mut frontier, 0, link, &mut change)?;
size = BODY_HEADER;
}
size += entry.size();
leaf.push(entry);
}
if leaf.is_empty() && count == 0 {
change.root = self
.write_tracked(storage, &Node::Leaf(leaf), &mut change)?
.reference;
return Ok(change);
}
if !leaf.is_empty() {
let link = self.write_tracked(storage, &Node::Leaf(leaf), &mut change)?;
self.push_frontier(storage, &mut frontier, 0, link, &mut change)?;
}
for level in 0..=MAX_HEIGHT as usize {
if level >= frontier.len() {
return Err(Error::CorruptRecord);
}
let children = std::mem::take(&mut frontier[level]);
if children.is_empty() {
continue;
}
let higher_empty = frontier.iter().skip(level + 1).all(Vec::is_empty);
if children.len() == 1 && higher_empty {
change.root = children[0].reference;
return Ok(change);
}
let height = (level + 1) as u8;
if height > MAX_HEIGHT {
return Err(Error::CorruptRecord);
}
let link =
self.write_tracked(storage, &Node::Branch { height, children }, &mut change)?;
self.push_frontier(storage, &mut frontier, level + 1, link, &mut change)?;
}
Err(Error::CorruptRecord)
}
fn push_frontier(
&self,
storage: &mut impl Storage,
frontier: &mut Vec<Vec<Link>>,
level: usize,
link: Link,
change: &mut Change,
) -> Result<()> {
if level > MAX_HEIGHT as usize {
return Err(Error::SecurityLimitExceeded("index height limit".into()));
}
if frontier.len() <= level {
frontier.resize_with(level + 1, Vec::new);
}
let size = BODY_HEADER + frontier[level].iter().map(Link::size).sum::<usize>();
if size + link.size() > MAX_BODY || frontier[level].len() == MAX_ITEMS {
let children = std::mem::take(&mut frontier[level]);
let parent = self.write_tracked(
storage,
&Node::Branch {
height: (level + 1) as u8,
children,
},
change,
)?;
self.push_frontier(storage, frontier, level + 1, parent, change)?;
}
frontier[level].push(link);
Ok(())
}
pub(crate) fn visit(
&self,
storage: &impl Storage,
root: RootRef,
sealed: u64,
visitor: impl FnMut(Entry) -> Result<()>,
) -> Result<()> {
self.visit_range(storage, root, sealed, None, None, visitor)
}
pub(crate) fn visit_range(
&self,
storage: &impl Storage,
root: RootRef,
sealed: u64,
start: Option<(u8, &[u8])>,
end: Option<(u8, &[u8])>,
mut visitor: impl FnMut(Entry) -> Result<()>,
) -> Result<()> {
if start.zip(end).is_some_and(|(start, end)| start > end) {
return Err(Error::InvalidInput("inverted index range".into()));
}
let node = self.read(storage, root, sealed)?;
self.visit_node(
storage,
node,
sealed,
None,
start,
end,
&mut |event| match event {
Visit::Page(_) => Ok(()),
Visit::Entry(entry) => visitor(entry),
},
)
}
pub(crate) fn visit_owned(
&self,
storage: &impl Storage,
root: RootRef,
sealed: u64,
mut visitor: impl FnMut(Visit) -> Result<()>,
) -> Result<()> {
let node = self.read(storage, root, sealed)?;
visitor(Visit::Page(root))?;
self.visit_node(storage, node, sealed, None, None, None, &mut visitor)
}
#[allow(clippy::too_many_arguments)]
fn visit_node(
&self,
storage: &impl Storage,
node: Node,
sealed: u64,
upper: Option<&Key>,
start: Option<(u8, &[u8])>,
end: Option<(u8, &[u8])>,
visitor: &mut impl FnMut(Visit) -> Result<()>,
) -> Result<()> {
match node {
Node::Leaf(entries) => {
for entry in entries {
if start.is_none_or(|s| entry.identity() >= s)
&& end.is_none_or(|e| entry.identity() < e)
{
visitor(Visit::Entry(entry))?;
}
}
}
Node::Branch { height, children } => {
for (position, link) in children.iter().enumerate() {
let bound = children.get(position + 1).map(|c| &c.first).or(upper);
if end.is_some_and(|e| link.first.identity() >= e)
|| start.is_some_and(|s| bound.is_some_and(|b| b.identity() <= s))
{
continue;
}
let child = self.child(storage, link, height, sealed, bound)?;
visitor(Visit::Page(link.reference))?;
self.visit_node(storage, child, sealed, bound, start, end, visitor)?;
}
}
}
Ok(())
}
pub(crate) fn recover(
&self,
storage: &impl Storage,
root: RootRef,
sealed: u64,
mut visitor: impl FnMut(Entry) -> Result<()>,
) -> Result<RecoveryReport> {
let node = self.read(storage, root, sealed)?;
let expected = node.count();
let mut report = RecoveryReport {
recovered: 0,
unavailable: 0,
damaged_pages: Vec::new(),
};
self.recover_node(storage, node, sealed, None, &mut visitor, &mut report)?;
if report.recovered + report.unavailable != expected {
return Err(Error::CorruptRecord);
}
Ok(report)
}
fn recover_node(
&self,
storage: &impl Storage,
node: Node,
sealed: u64,
upper: Option<&Key>,
visitor: &mut impl FnMut(Entry) -> Result<()>,
report: &mut RecoveryReport,
) -> Result<()> {
match node {
Node::Leaf(entries) => {
for entry in entries {
visitor(entry)?;
report.recovered += 1;
}
}
Node::Branch { height, children } => {
for (position, link) in children.iter().enumerate() {
let bound = children.get(position + 1).map(|c| &c.first).or(upper);
match self.child(storage, link, height, sealed, bound) {
Ok(child) => {
self.recover_node(storage, child, sealed, bound, visitor, report)?
}
Err(Error::CorruptRecord | Error::CorruptHeader | Error::Truncated) => {
report.unavailable += link.count;
report.damaged_pages.push(link.reference);
}
Err(error) => return Err(error),
}
}
}
}
Ok(())
}
fn child(
&self,
storage: &impl Storage,
link: &Link,
height: u8,
sealed: u64,
upper: Option<&Key>,
) -> Result<Node> {
let node = self.read(storage, link.reference, sealed)?;
if node.height() + 1 != height
|| node.count() != link.count
|| node.first() != Some(link.first.identity())
|| node
.last()
.is_some_and(|last| upper.is_some_and(|upper| last >= upper.identity()))
{
return Err(Error::CorruptRecord);
}
Ok(node)
}
fn read(&self, storage: &impl Storage, reference: RootRef, sealed: u64) -> Result<Node> {
validate_ref(reference, sealed)?;
self.decode(
&ZeroizingBytes::new(reference.read_verified(storage)?),
sealed,
)
}
fn encode(&self, node: &Node) -> Result<ZeroizingBytes> {
validate_node(node, u64::MAX)?;
let stored_len = if self.mode.unpadded() {
node.body_len()
} else {
MAX_NODE - HEADER - if self.key.is_some() { 16 } else { 0 }
};
let mut body = ZeroizingBytes::new(Vec::with_capacity(stored_len));
body.push(node.height());
body.extend_from_slice(&node.count().to_le_bytes());
body.extend_from_slice(&(node.item_count() as u16).to_le_bytes());
match node {
Node::Leaf(entries) => {
for entry in entries {
body.push(entry.namespace);
body.extend_from_slice(&(entry.key.len() as u16).to_le_bytes());
body.extend_from_slice(&(entry.value.len() as u32).to_le_bytes());
body.extend_from_slice(&entry.key);
body.extend_from_slice(&entry.value);
}
}
Node::Branch { children, .. } => {
for link in children {
body.push(link.first.namespace);
body.extend_from_slice(&(link.first.bytes.len() as u16).to_le_bytes());
body.extend_from_slice(&link.first.bytes);
body.extend_from_slice(&link.reference.primary.to_le_bytes());
body.extend_from_slice(&link.reference.mirror.to_le_bytes());
body.extend_from_slice(&link.reference.len.to_le_bytes());
body.extend_from_slice(&link.reference.digest);
body.extend_from_slice(&link.count.to_le_bytes());
}
}
}
body.resize(stored_len, 0);
let mut out = ZeroizingBytes::new(Vec::with_capacity(HEADER + body.len() + 16));
out.extend_from_slice(MAGIC);
out.extend_from_slice(&1u16.to_le_bytes());
out.extend_from_slice(&self.mode.0.to_le_bytes());
out.extend_from_slice(self.archive.as_bytes());
if let Some(key) = &self.key {
let (nonce, encrypted) = seal_with_random_nonce(&body, key.as_slice(), &out)?;
out.extend_from_slice(&nonce);
out.extend_from_slice(&(encrypted.len() as u32).to_le_bytes());
out.extend_from_slice(&encrypted);
} else {
out.extend_from_slice(&[0; 12]);
out.extend_from_slice(&(body.len() as u32).to_le_bytes());
out.extend_from_slice(&body);
}
Ok(out)
}
fn write(&self, storage: &mut impl Storage, node: &Node) -> Result<Link> {
let bytes = self.encode(node)?;
if storage.len()? < REGION_LEN as u64 {
return Err(Error::CorruptHeader);
}
let (primary, mirror) = storage.append_pair(&bytes)?;
Ok(Link {
reference: RootRef {
primary,
mirror,
len: bytes.len() as u64,
digest: strong_checksum(&bytes),
},
count: node.count(),
first: Key::new(node.first().unwrap_or((0, &[]))),
})
}
fn write_tracked(
&self,
storage: &mut impl Storage,
node: &Node,
change: &mut Change,
) -> Result<Link> {
let link = self.write(storage, node)?;
change.created.push(link.reference);
Ok(link)
}
}
fn validate_input(key: &[u8], value: &[u8]) -> Result<()> {
if key.len() > MAX_KEY || value.len() > MAX_VALUE {
return Err(Error::SecurityLimitExceeded(
"index key or descriptor exceeds node limit".into(),
));
}
Ok(())
}
fn validate_node(node: &Node, sealed: u64) -> Result<()> {
if node.height() > MAX_HEIGHT
|| node.item_count() > MAX_ITEMS
|| node.body_len() > MAX_BODY
|| node.count() > MAX_ENTRIES
{
return Err(Error::CorruptRecord);
}
match node {
Node::Leaf(entries) => {
for entry in entries {
validate_input(&entry.key, &entry.value)?;
}
if entries
.windows(2)
.any(|w| w[0].identity() >= w[1].identity())
{
return Err(Error::CorruptRecord);
}
}
Node::Branch { height, children } => {
if *height == 0
|| children.is_empty()
|| children
.windows(2)
.any(|w| w[0].first.identity() >= w[1].first.identity())
{
return Err(Error::CorruptRecord);
}
let mut ranges = Vec::with_capacity(2 * children.len());
for child in children {
validate_input(&child.first.bytes, &[])?;
validate_ref(child.reference, sealed)?;
if child.count == 0 || child.count > MAX_ENTRIES {
return Err(Error::CorruptRecord);
}
for offset in [child.reference.primary, child.reference.mirror] {
ranges.push((offset, offset + child.reference.len));
}
}
ranges.sort_unstable();
if ranges.windows(2).any(|w| w[0].1 > w[1].0) {
return Err(Error::CorruptRecord);
}
}
}
Ok(())
}
fn validate_ref(reference: RootRef, sealed: u64) -> Result<()> {
if reference.len < HEADER as u64 || reference.len > MAX_NODE as u64 {
return Err(Error::CorruptRecord);
}
let first = reference.primary.min(reference.mirror);
let last = reference.primary.max(reference.mirror);
if first < REGION_LEN as u64
|| first
.checked_add(reference.len)
.is_none_or(|end| end > last)
|| last
.checked_add(reference.len)
.is_none_or(|end| end > sealed)
{
return Err(Error::CorruptRecord);
}
Ok(())
}
fn pack<T>(items: Vec<T>, size: impl Fn(&T) -> usize) -> Vec<Vec<T>> {
let mut groups = Vec::new();
let mut current = Vec::new();
let mut bytes = BODY_HEADER;
for item in items {
if bytes + size(&item) > MAX_BODY || current.len() == MAX_ITEMS {
groups.push(std::mem::take(&mut current));
bytes = BODY_HEADER;
}
bytes += size(&item);
current.push(item);
}
if !current.is_empty() {
groups.push(current);
}
for i in (1..groups.len()).rev() {
let mut together = std::mem::take(&mut groups[i - 1]);
together.append(&mut groups[i]);
let total = together.iter().map(&size).sum::<usize>();
let mut left = 0;
let mut best = None;
for cut in 1..together.len() {
left += size(&together[cut - 1]);
let right = total - left;
if cut <= MAX_ITEMS
&& together.len() - cut <= MAX_ITEMS
&& left + BODY_HEADER <= MAX_BODY
&& right + BODY_HEADER <= MAX_BODY
{
let score = left.abs_diff(right);
if best.is_none_or(|(_, old_score)| score < old_score) {
best = Some((cut, score));
}
}
}
let (cut, _) = best.expect("original adjacent groups satisfy page bounds");
let right = together.split_off(cut);
groups[i - 1] = together;
groups[i] = right;
}
groups
}
struct Cursor<'a>(&'a [u8]);
impl<'a> Cursor<'a> {
fn take(&mut self, len: usize) -> Result<&'a [u8]> {
if len > self.0.len() {
return Err(Error::CorruptRecord);
}
let (next, rest) = self.0.split_at(len);
self.0 = rest;
Ok(next)
}
fn u16(&mut self) -> Result<u16> {
Ok(u16::from_le_bytes(self.take(2)?.try_into().unwrap()))
}
fn u32(&mut self) -> Result<u32> {
Ok(u32::from_le_bytes(self.take(4)?.try_into().unwrap()))
}
fn u64(&mut self) -> Result<u64> {
Ok(u64::from_le_bytes(self.take(8)?.try_into().unwrap()))
}
fn link(&mut self, sealed: u64) -> Result<Link> {
let namespace = self.take(1)?[0];
let key_len = self.u16()? as usize;
if key_len > MAX_KEY {
return Err(Error::CorruptRecord);
}
let first = Key::new((namespace, self.take(key_len)?));
let reference = RootRef {
primary: self.u64()?,
mirror: self.u64()?,
len: self.u64()?,
digest: self.take(32)?.try_into().unwrap(),
};
validate_ref(reference, sealed)?;
let count = self.u64()?;
if count == 0 || count > MAX_ENTRIES {
return Err(Error::CorruptRecord);
}
Ok(Link {
reference,
count,
first,
})
}
}
#[cfg(test)]
#[path = "authenticated_index_tests.rs"]
mod tests;