use crate::bytes::{get_u16, get_u32, get_u64, put_u16, put_u32, put_u64};
use super::{ObjectHeader, ParseError};
pub const NODE_DATA_START: usize = 56;
pub const TREE_INFO_SIZE: usize = 40;
pub const NO_VALUE: u16 = 0xFFFF;
pub const CHILD_POINTER_SIZE: usize = 8;
pub mod node_flags {
pub const ROOT: u16 = 0x1;
pub const LEAF: u16 = 0x2;
pub const FIXED_SIZE: u16 = 0x4;
pub const HASHED: u16 = 0x8;
pub const NO_HEADER: u16 = 0x10;
pub const UNDERSTOOD: u16 = ROOT | LEAF | FIXED_SIZE;
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct NodeHeader {
pub header: ObjectHeader,
pub flags: u16,
pub level: u16,
pub key_count: u32,
pub table: (u16, u16),
pub free_space: (u16, u16),
pub key_free_list: (u16, u16),
pub value_free_list: (u16, u16),
}
impl NodeHeader {
pub const SIZE: usize = NODE_DATA_START;
pub fn read_from(buf: &[u8]) -> Result<Self, ParseError> {
ParseError::need("node header", Self::SIZE, buf)?;
let loc = |off| (get_u16(buf, off), get_u16(buf, off + 2));
Ok(Self {
header: ObjectHeader::read_from(buf)?,
flags: get_u16(buf, 32),
level: get_u16(buf, 34),
key_count: get_u32(buf, 36),
table: loc(40),
free_space: loc(44),
key_free_list: loc(48),
value_free_list: loc(52),
})
}
pub fn write_to(&self, buf: &mut [u8]) {
assert!(
buf.len() >= Self::SIZE,
"a node header needs {} bytes",
Self::SIZE
);
self.header.write_to(buf);
put_u16(buf, 32, self.flags);
put_u16(buf, 34, self.level);
put_u32(buf, 36, self.key_count);
let mut loc = |off, (a, b): (u16, u16)| {
put_u16(buf, off, a);
put_u16(buf, off + 2, b);
};
loc(40, self.table);
loc(44, self.free_space);
loc(48, self.key_free_list);
loc(52, self.value_free_list);
}
#[must_use]
pub const fn is_root(&self) -> bool {
self.flags & node_flags::ROOT != 0
}
#[must_use]
pub const fn is_leaf(&self) -> bool {
self.flags & node_flags::LEAF != 0
}
#[must_use]
pub const fn is_fixed_size(&self) -> bool {
self.flags & node_flags::FIXED_SIZE != 0
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct TreeInfo {
pub flags: u32,
pub node_size: u32,
pub key_size: u32,
pub value_size: u32,
pub longest_key: u32,
pub longest_value: u32,
pub key_count: u64,
pub node_count: u64,
}
pub const TREE_PHYSICAL: u32 = 0x10;
pub const TREE_SEQUENTIAL_INSERT: u32 = 0x2;
pub const TREE_ALLOW_GHOSTS: u32 = 0x4;
pub const TREE_KV_NONALIGNED: u32 = 0x40;
pub const TREE_HASHED: u32 = 0x80;
pub const TREE_NO_HEADER: u32 = 0x100;
pub const TREE_EPHEMERAL: u32 = 0x8;
impl TreeInfo {
pub const SIZE: usize = TREE_INFO_SIZE;
pub fn read_from(buf: &[u8]) -> Result<Self, ParseError> {
ParseError::need("tree information", Self::SIZE, buf)?;
Ok(Self {
flags: get_u32(buf, 0),
node_size: get_u32(buf, 4),
key_size: get_u32(buf, 8),
value_size: get_u32(buf, 12),
longest_key: get_u32(buf, 16),
longest_value: get_u32(buf, 20),
key_count: get_u64(buf, 24),
node_count: get_u64(buf, 32),
})
}
pub fn write_to(&self, buf: &mut [u8]) {
assert!(buf.len() >= Self::SIZE, "tree information needs 40 bytes");
put_u32(buf, 0, self.flags);
put_u32(buf, 4, self.node_size);
put_u32(buf, 8, self.key_size);
put_u32(buf, 12, self.value_size);
put_u32(buf, 16, self.longest_key);
put_u32(buf, 20, self.longest_value);
put_u64(buf, 24, self.key_count);
put_u64(buf, 32, self.node_count);
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum NodeFault {
#[error("{len} bytes cannot hold a node")]
#[non_exhaustive]
TooShort {
len: usize,
},
#[error("the table of contents ({offset} bytes in, {len} long) leaves the node")]
#[non_exhaustive]
TableOutside {
offset: u16,
len: u16,
},
#[error("{count} entries do not fit a table of contents {len} bytes long")]
#[non_exhaustive]
TableTooSmall {
count: u32,
len: u16,
},
#[error("a fixed-size entry of {key_size}-byte keys and {value_size}-byte values")]
#[non_exhaustive]
BadFixedSize {
key_size: u32,
value_size: u32,
},
#[error("a node of entries of varying size in a tree whose keys take {key_size} bytes")]
#[non_exhaustive]
VaryingInFixedTree {
key_size: u32,
},
#[error("entry {index}'s key ({offset} bytes in, {len} long) leaves the key area")]
#[non_exhaustive]
KeyOutside {
index: u32,
offset: u16,
len: u16,
},
#[error(
"entry {index}'s value ({offset} bytes from the end, {len} long) leaves the value area"
)]
#[non_exhaustive]
ValueOutside {
index: u32,
offset: u16,
len: u16,
},
#[error("the free space ({offset} bytes into the key area, {len} long) leaves the node")]
#[non_exhaustive]
FreeSpaceOutside {
offset: u16,
len: u16,
},
#[error("entry {index} of a node counting {count}")]
#[non_exhaustive]
NoEntry {
index: u32,
count: u32,
},
#[error("entry {index}'s {part} shares bytes with another entry's")]
#[non_exhaustive]
Overlap {
index: u32,
part: &'static str,
},
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct Unused {
pub key: usize,
pub value: usize,
}
#[derive(Clone, Copy, Debug)]
pub struct Node<'a> {
bytes: &'a [u8],
header: NodeHeader,
table_start: usize,
key_area: usize,
free_start: usize,
value_start: usize,
value_end: usize,
fixed: Option<(u16, u16)>,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct EntrySizes {
pub key: u32,
pub value: u32,
}
impl<'a> Node<'a> {
pub fn frame(bytes: &'a [u8], sizes: EntrySizes) -> Result<Self, NodeFault> {
let len = bytes.len();
let header = NodeHeader::read_from(bytes).map_err(|_| NodeFault::TooShort { len })?;
let value_end = if header.is_root() {
len.checked_sub(TREE_INFO_SIZE)
.filter(|end| *end >= NODE_DATA_START)
.ok_or(NodeFault::TooShort { len })?
} else {
len
};
let (offset, table_len) = header.table;
let table_start = NODE_DATA_START + usize::from(offset);
let key_area = table_start + usize::from(table_len);
if key_area > value_end {
return Err(NodeFault::TableOutside {
offset,
len: table_len,
});
}
let (free_offset, free_len) = header.free_space;
let free_start = key_area + usize::from(free_offset);
let value_start = free_start + usize::from(free_len);
if value_start > value_end {
return Err(NodeFault::FreeSpaceOutside {
offset: free_offset,
len: free_len,
});
}
let fixed = if header.is_fixed_size() {
let value = if header.is_leaf() {
sizes.value
} else {
CHILD_POINTER_SIZE as u32
};
let fits = |n: u32| n != 0 && n <= u32::from(u16::MAX);
if !fits(sizes.key) || !fits(value) {
return Err(NodeFault::BadFixedSize {
key_size: sizes.key,
value_size: value,
});
}
Some((sizes.key as u16, value as u16))
} else if sizes.key != 0 {
return Err(NodeFault::VaryingInFixedTree {
key_size: sizes.key,
});
} else {
None
};
let entry_size: u64 = if fixed.is_some() { 4 } else { 8 };
if u64::from(header.key_count) * entry_size > u64::from(table_len) {
return Err(NodeFault::TableTooSmall {
count: header.key_count,
len: table_len,
});
}
Ok(Self {
bytes,
header,
table_start,
key_area,
free_start,
value_start,
value_end,
fixed,
})
}
#[must_use]
pub const fn header(&self) -> &NodeHeader {
&self.header
}
#[must_use]
pub const fn bytes(&self) -> &'a [u8] {
self.bytes
}
#[must_use]
pub const fn len(&self) -> u32 {
self.header.key_count
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.header.key_count == 0
}
#[must_use]
pub fn tree_info(&self) -> Option<TreeInfo> {
if !self.header.is_root() {
return None;
}
TreeInfo::read_from(&self.bytes[self.value_end..]).ok()
}
pub fn entry(&self, index: u32) -> Result<(&'a [u8], Option<&'a [u8]>), NodeFault> {
let (key, value) = self.locate(index)?;
Ok((&self.bytes[key], value.map(|value| &self.bytes[value])))
}
pub fn check_layout(&self) -> Result<Unused, NodeFault> {
let mut taken = vec![0u64; self.bytes.len().div_ceil(64)];
let mut held = Unused::default();
let mut claim = |range: std::ops::Range<usize>, index: u32, part: &'static str| {
for at in range {
let (word, bit) = (at / 64, 1u64 << (at % 64));
if taken[word] & bit != 0 {
return Err(NodeFault::Overlap { index, part });
}
taken[word] |= bit;
}
Ok(())
};
for index in 0..self.header.key_count {
let (key, value) = self.locate(index)?;
held.key += key.len();
claim(key, index, "key")?;
if let Some(value) = value {
held.value += value.len();
claim(value, index, "value")?;
}
}
Ok(Unused {
key: (self.free_start - self.key_area) - held.key,
value: (self.value_end - self.value_start) - held.value,
})
}
fn locate(
&self,
index: u32,
) -> Result<(std::ops::Range<usize>, Option<std::ops::Range<usize>>), NodeFault> {
if index >= self.header.key_count {
return Err(NodeFault::NoEntry {
index,
count: self.header.key_count,
});
}
let i = index as usize;
let (key_off, key_len, value_off, value_len) = match self.fixed {
Some((key_len, value_len)) => {
let at = self.table_start + 4 * i;
(
get_u16(self.bytes, at),
key_len,
get_u16(self.bytes, at + 2),
value_len,
)
}
None => {
let at = self.table_start + 8 * i;
(
get_u16(self.bytes, at),
get_u16(self.bytes, at + 2),
get_u16(self.bytes, at + 4),
get_u16(self.bytes, at + 6),
)
}
};
let key_start = self.key_area + usize::from(key_off);
let key_end = key_start + usize::from(key_len);
if key_end > self.free_start {
return Err(NodeFault::KeyOutside {
index,
offset: key_off,
len: key_len,
});
}
if value_off == NO_VALUE {
return Ok((key_start..key_end, None));
}
let outside = NodeFault::ValueOutside {
index,
offset: value_off,
len: value_len,
};
let value_start = self
.value_end
.checked_sub(usize::from(value_off))
.filter(|start| *start >= self.value_start)
.ok_or(outside)?;
let value_end = value_start + usize::from(value_len);
if value_end > self.value_end {
return Err(outside);
}
Ok((key_start..key_end, Some(value_start..value_end)))
}
}
pub fn child_oid(value: &[u8]) -> Result<u64, ParseError> {
ParseError::need("index value", CHILD_POINTER_SIZE, value)?;
Ok(get_u64(value, 0))
}
#[cfg(test)]
mod tests {
use super::*;
fn leaf_root(entries: &[(&[u8], &[u8])]) -> Vec<u8> {
let mut node = vec![0u8; 4096];
let table_len = (entries.len() * 8) as u16;
NodeHeader {
header: ObjectHeader {
checksum: 0,
oid: 5,
xid: 1,
type_word: 0x4000_0002,
subtype: 0x0B,
},
flags: node_flags::ROOT | node_flags::LEAF,
level: 0,
key_count: entries.len() as u32,
table: (0, table_len),
free_space: (0, 0),
key_free_list: (NO_VALUE, 0),
value_free_list: (NO_VALUE, 0),
}
.write_to(&mut node);
let key_area = NODE_DATA_START + usize::from(table_len);
let value_end = 4096 - TREE_INFO_SIZE;
let (mut k, mut v) = (0usize, 0usize);
for (i, (key, value)) in entries.iter().enumerate() {
node[key_area + k..key_area + k + key.len()].copy_from_slice(key);
v += value.len();
node[value_end - v..value_end - v + value.len()].copy_from_slice(value);
let at = NODE_DATA_START + 8 * i;
put_u16(&mut node, at, k as u16);
put_u16(&mut node, at + 2, key.len() as u16);
put_u16(&mut node, at + 4, v as u16);
put_u16(&mut node, at + 6, value.len() as u16);
k += key.len();
}
put_u16(&mut node, 44, k as u16);
put_u16(&mut node, 46, (value_end - v - key_area - k) as u16);
node
}
#[test]
fn a_header_round_trips() {
let header = NodeHeader {
header: ObjectHeader {
checksum: 0,
oid: 9,
xid: 2,
type_word: 3,
subtype: 0x0E,
},
flags: node_flags::LEAF,
level: 0,
key_count: 3,
table: (0, 24),
free_space: (40, 100),
key_free_list: (NO_VALUE, 0),
value_free_list: (NO_VALUE, 0),
};
let mut buf = [0u8; NodeHeader::SIZE];
header.write_to(&mut buf);
assert_eq!(NodeHeader::read_from(&buf), Ok(header));
}
#[test]
fn entries_are_found_where_the_table_says() {
let node = leaf_root(&[(b"alpha", b"one"), (b"beta", b"two!")]);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert_eq!(framed.len(), 2);
assert_eq!(framed.entry(0), Ok((&b"alpha"[..], Some(&b"one"[..]))));
assert_eq!(framed.entry(1), Ok((&b"beta"[..], Some(&b"two!"[..]))));
assert!(framed.tree_info().is_some());
}
#[test]
fn a_key_with_no_value_is_one_with_none() {
let mut node = leaf_root(&[(b"ghost", b"x")]);
put_u16(&mut node, NODE_DATA_START + 4, NO_VALUE);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert_eq!(framed.entry(0), Ok((&b"ghost"[..], None)));
}
#[test]
fn a_key_running_into_the_values_is_refused() {
let mut node = leaf_root(&[(b"alpha", b"one")]);
put_u16(&mut node, NODE_DATA_START + 2, 5000);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert!(matches!(
framed.entry(0),
Err(NodeFault::KeyOutside { index: 0, .. })
));
}
#[test]
fn a_value_reaching_past_its_area_or_back_into_the_table_is_refused() {
let mut node = leaf_root(&[(b"alpha", b"one")]);
put_u16(&mut node, NODE_DATA_START + 4, 2);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert!(matches!(
framed.entry(0),
Err(NodeFault::ValueOutside { .. })
));
put_u16(&mut node, NODE_DATA_START + 4, 4090);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert!(matches!(
framed.entry(0),
Err(NodeFault::ValueOutside { .. })
));
}
#[test]
fn a_key_reaching_into_the_free_space_or_a_value_starting_in_it_is_refused() {
let node = leaf_root(&[(b"alpha", b"one"), (b"beta", b"two!")]);
let mut longer = node.clone();
put_u16(&mut longer, NODE_DATA_START + 8 + 2, 5);
let framed = Node::frame(&longer, EntrySizes::default()).expect("frames");
assert!(matches!(
framed.entry(1),
Err(NodeFault::KeyOutside { index: 1, .. })
));
let mut earlier = node;
put_u16(&mut earlier, NODE_DATA_START + 8 + 4, 8);
let framed = Node::frame(&earlier, EntrySizes::default()).expect("frames");
assert!(matches!(
framed.entry(1),
Err(NodeFault::ValueOutside { index: 1, .. })
));
}
#[test]
fn two_values_sharing_bytes_are_refused() {
let mut node = leaf_root(&[(b"alpha", b"one"), (b"beta", b"two")]);
put_u16(&mut node, NODE_DATA_START + 8 + 4, 3);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert_eq!(framed.entry(1), Ok((&b"beta"[..], Some(&b"one"[..]))));
assert_eq!(
framed.check_layout(),
Err(NodeFault::Overlap {
index: 1,
part: "value"
})
);
}
#[test]
fn the_bytes_no_entry_holds_are_counted_in_each_area() {
let node = leaf_root(&[(b"alpha", b"one"), (b"beta", b"two!")]);
let framed = Node::frame(&node, EntrySizes::default()).expect("frames");
assert_eq!(framed.check_layout(), Ok(Unused { key: 0, value: 0 }));
let mut shorter = node;
put_u16(&mut shorter, NODE_DATA_START + 2, 4);
let framed = Node::frame(&shorter, EntrySizes::default()).expect("frames");
assert_eq!(framed.check_layout(), Ok(Unused { key: 1, value: 0 }));
}
#[test]
fn free_space_leaving_the_node_is_refused() {
let mut node = leaf_root(&[(b"alpha", b"one")]);
put_u16(&mut node, 46, 4000);
assert!(matches!(
Node::frame(&node, EntrySizes::default()),
Err(NodeFault::FreeSpaceOutside { .. })
));
}
#[test]
fn a_table_claiming_more_entries_than_it_has_room_for_is_refused() {
let mut node = leaf_root(&[(b"alpha", b"one")]);
put_u32(&mut node, 36, 2);
assert!(matches!(
Node::frame(&node, EntrySizes::default()),
Err(NodeFault::TableTooSmall { count: 2, .. })
));
}
#[test]
fn a_table_leaving_the_node_is_refused() {
let mut node = leaf_root(&[(b"alpha", b"one")]);
put_u16(&mut node, 40, 4000);
assert!(matches!(
Node::frame(&node, EntrySizes::default()),
Err(NodeFault::TableOutside { .. })
));
}
#[test]
fn a_fixed_size_node_takes_its_sizes_from_the_tree() {
let mut node = vec![0u8; 4096];
NodeHeader {
header: ObjectHeader {
checksum: 0,
oid: 5,
xid: 1,
type_word: 0x4000_0002,
subtype: 0x0B,
},
flags: node_flags::ROOT | node_flags::LEAF | node_flags::FIXED_SIZE,
level: 0,
key_count: 1,
table: (0, 4),
free_space: (
16,
(4096 - TREE_INFO_SIZE - 16 - (NODE_DATA_START + 4) - 16) as u16,
),
key_free_list: (NO_VALUE, 0),
value_free_list: (NO_VALUE, 0),
}
.write_to(&mut node);
let key_area = NODE_DATA_START + 4;
node[key_area..key_area + 16].copy_from_slice(&[7; 16]);
let value_end = 4096 - TREE_INFO_SIZE;
node[value_end - 16..value_end].copy_from_slice(&[9; 16]);
put_u16(&mut node, NODE_DATA_START, 0);
put_u16(&mut node, NODE_DATA_START + 2, 16);
let sizes = EntrySizes { key: 16, value: 16 };
let framed = Node::frame(&node, sizes).expect("frames");
assert_eq!(framed.entry(0), Ok((&[7u8; 16][..], Some(&[9u8; 16][..]))));
assert!(matches!(
Node::frame(&node, EntrySizes::default()),
Err(NodeFault::BadFixedSize { .. })
));
}
}