pub(crate) struct IndexGroup {
pub(crate) group: usize,
pub(crate) first_block: usize,
pub(crate) offsets: Vec<u64>,
pub(crate) keys: GroupKeys,
}
pub(crate) enum GroupKeys {
Hash(Vec<u64>),
Key {
sep_offsets: Vec<u32>,
bytes: Vec<u8>,
},
}
impl IndexGroup {
pub(crate) fn contains(&self, block: usize) -> bool {
block >= self.first_block && block - self.first_block < self.offsets.len() - 1
}
pub(crate) fn range(&self, block: usize) -> (u64, usize) {
assert!(self.contains(block), "block outside index group");
let i = block - self.first_block;
(
self.offsets[i],
(self.offsets[i + 1] - self.offsets[i]) as usize,
)
}
pub(crate) fn first_h(&self, block: usize) -> u64 {
assert!(self.contains(block), "block outside index group");
let GroupKeys::Hash(keys) = &self.keys else {
unreachable!("ByHash")
};
keys[block - self.first_block]
}
pub(crate) fn separator(&self, block: usize) -> &[u8] {
assert!(self.contains(block), "block outside index group");
let GroupKeys::Key { sep_offsets, bytes } = &self.keys else {
unreachable!("ByKey")
};
let i = block - self.first_block;
&bytes[sep_offsets[i] as usize..sep_offsets[i + 1] as usize]
}
pub(crate) fn locate_hash(&self, h: u64) -> Option<usize> {
let GroupKeys::Hash(keys) = &self.keys else {
unreachable!("ByHash")
};
keys.partition_point(|&first| first <= h)
.checked_sub(1)
.map(|i| self.first_block + i)
}
pub(crate) fn locate_key(&self, key: &[u8]) -> usize {
let GroupKeys::Key { sep_offsets, .. } = &self.keys else {
unreachable!("ByKey")
};
let mut lo = 0;
let mut hi = sep_offsets.len() - 1;
while lo < hi {
let mid = lo + (hi - lo) / 2;
if self.separator(self.first_block + mid) <= key {
lo = mid + 1;
} else {
hi = mid;
}
}
self.first_block + lo.saturating_sub(1)
}
#[allow(dead_code)]
pub(crate) fn resident_bytes(&self) -> usize {
self.offsets.capacity() * 8
+ match &self.keys {
GroupKeys::Hash(keys) => keys.capacity() * 8,
GroupKeys::Key { sep_offsets, bytes } => {
sep_offsets.capacity() * 4 + bytes.capacity()
}
}
}
}
impl IndexSkeleton {
pub(crate) fn group_of_hash(&self, h: u64) -> Option<usize> {
let GroupSamples::Hash(samples) = &self.samples else {
unreachable!("ByHash")
};
samples.partition_point(|&first| first <= h).checked_sub(1)
}
pub(crate) fn group_of_key(&self, key: &[u8]) -> usize {
let GroupSamples::Key { separators, .. } = &self.samples else {
unreachable!("ByKey")
};
separators
.partition_point(|s| s.as_slice() <= key)
.saturating_sub(1)
}
pub(crate) fn group_of_block(&self, block: usize) -> usize {
block / GROUP_BLOCKS
}
pub(crate) fn group_blocks(&self, g: usize) -> std::ops::Range<usize> {
g * GROUP_BLOCKS..((g + 1) * GROUP_BLOCKS).min(self.blocks)
}
}
pub(crate) const PAGE: u64 = 4096;
pub(crate) const GROUP_BLOCKS: usize = 128;
pub(crate) const PROBE_WINDOW: u64 = 32 * 1024;
pub(crate) fn chunk_count(offset: u64, len: u64) -> usize {
if len == 0 {
return 0;
}
((offset % PAGE) as u128 + len as u128).div_ceil(PAGE as u128) as usize
}
pub(crate) fn chunk_range(offset: u64, len: u64, i: usize) -> (u64, u64) {
let page = offset / PAGE + i as u64;
(
(page * PAGE).max(offset),
page.saturating_add(1)
.saturating_mul(PAGE)
.min(offset.saturating_add(len)),
)
}
pub(crate) fn chunk_crcs(offset: u64, body: &[u8]) -> Vec<u32> {
let len = body.len() as u64;
(0..chunk_count(offset, len))
.map(|i| {
let (s, e) = chunk_range(offset, len, i);
crc32fast::hash(&body[(s - offset) as usize..(e - offset) as usize])
})
.collect()
}
impl PagedSection {
pub(crate) fn chunk_range(&self, i: usize) -> (u64, u64) {
chunk_range(self.offset, self.len, i)
}
pub(crate) fn chunks_covering(&self, from: u64, to: u64) -> std::ops::Range<usize> {
debug_assert!(from < to && to <= self.len);
let first = self.offset / PAGE;
((self.offset + from) / PAGE - first) as usize
..((self.offset + to - 1) / PAGE - first + 1) as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(crate) struct SectionId {
pub kind: u32,
pub prefix_len: u16,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct PagedSection {
pub id: SectionId,
pub offset: u64,
pub len: u64,
pub crcs: Vec<u32>,
}
use super::{FormatFault, filter::FilterTable, key_index::SeparatorIndex, sidecar::*};
#[cfg(any(test, feature = "test-faults"))]
use crate::DbError;
use crate::DbResult;
use std::{
collections::HashSet,
fs::File,
os::unix::fs::FileExt,
sync::{
Arc,
atomic::{AtomicU64, Ordering::Relaxed},
},
};
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum GroupSamples {
Hash(Vec<u64>),
Key {
starts: Vec<u32>,
separators: Vec<Vec<u8>>,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct IndexSkeleton {
pub section: PagedSection,
pub blocks: usize,
pub end_offset: u64,
pub samples: GroupSamples,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct FilterSkeleton {
pub section: PagedSection,
pub filter_at: u64,
pub table: Arc<FilterTable>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct PageIndex {
pub filter: FilterSkeleton,
pub prefix_filters: Vec<(u16, FilterSkeleton)>,
pub index: IndexSkeleton,
}
fn bad() -> FormatFault {
FormatFault::corrupt("invalid page index")
}
struct Cursor<'a>(&'a [u8]);
impl<'a> Cursor<'a> {
fn take(&mut self, n: usize) -> Result<&'a [u8], FormatFault> {
let b = self.0.get(..n).ok_or_else(bad)?;
self.0 = &self.0[n..];
Ok(b)
}
fn u16(&mut self) -> Result<u16, FormatFault> {
Ok(u16::from_le_bytes(
self.take(2)?.try_into().expect("2 bytes"),
))
}
fn u32(&mut self) -> Result<u32, FormatFault> {
Ok(u32::from_le_bytes(
self.take(4)?.try_into().expect("4 bytes"),
))
}
fn u64(&mut self) -> Result<u64, FormatFault> {
Ok(u64::from_le_bytes(
self.take(8)?.try_into().expect("8 bytes"),
))
}
}
pub(crate) fn pageable(kind: u32, order: OrderKind) -> bool {
match kind {
SECTION_FILTER | SECTION_BLOCK_INDEX | SECTION_SEPARATOR_INDEX => true,
SECTION_PREFIX_FILTER => order == OrderKind::ByKey,
_ => false,
}
}
impl PagedSection {
fn encode_into(&self, payload: &[u8], out: &mut Vec<u8>) {
out.extend_from_slice(&self.id.kind.to_le_bytes());
out.extend_from_slice(&self.id.prefix_len.to_le_bytes());
out.extend_from_slice(&[0; 2]);
out.extend_from_slice(&self.offset.to_le_bytes());
out.extend_from_slice(&self.len.to_le_bytes());
out.extend_from_slice(&(self.crcs.len() as u32).to_le_bytes());
out.extend_from_slice(&(payload.len() as u32).to_le_bytes());
for crc in &self.crcs {
out.extend_from_slice(&crc.to_le_bytes());
}
out.extend_from_slice(payload);
}
}
impl FilterSkeleton {
fn encode_into(&self, out: &mut Vec<u8>) {
self.section.encode_into(&self.table.encode_head(), out);
}
}
impl IndexSkeleton {
fn encode_into(&self, out: &mut Vec<u8>) {
let mut payload = Vec::new();
payload.extend_from_slice(&(self.blocks as u32).to_le_bytes());
payload.extend_from_slice(&self.end_offset.to_le_bytes());
match &self.samples {
GroupSamples::Hash(samples) => {
for sample in samples {
payload.extend_from_slice(&sample.to_le_bytes());
}
}
GroupSamples::Key { starts, separators } => {
for (start, separator) in starts.iter().zip(separators) {
payload.extend_from_slice(&start.to_le_bytes());
payload.extend_from_slice(&(separator.len() as u16).to_le_bytes());
payload.extend_from_slice(separator);
}
}
}
self.section.encode_into(&payload, out);
}
}
impl PageIndex {
pub(crate) fn encode(&self) -> Vec<u8> {
let mut out = vec![1, 0, 0, 0];
out.extend_from_slice(&(PAGE as u32).to_le_bytes());
out.extend_from_slice(&(GROUP_BLOCKS as u32).to_le_bytes());
out.extend_from_slice(&((2 + self.prefix_filters.len()) as u32).to_le_bytes());
self.filter.encode_into(&mut out);
for (_, filter) in &self.prefix_filters {
filter.encode_into(&mut out);
}
self.index.encode_into(&mut out);
out
}
pub(crate) fn decode_known(
body: &[u8],
table: &[SectionRecord],
header: &SegHeader,
) -> Result<Option<Self>, FormatFault> {
match body.first() {
Some(1) => Self::decode(body, table, header).map(Some),
Some(_) => Ok(None),
None => Err(bad()),
}
}
pub(crate) fn decode(
body: &[u8],
table: &[SectionRecord],
header: &SegHeader,
) -> Result<Self, FormatFault> {
let mut cursor = Cursor(body);
if cursor.take(4)? != [1, 0, 0, 0]
|| cursor.u32()? != PAGE as u32
|| cursor.u32()? != GROUP_BLOCKS as u32
{
return Err(FormatFault::unsupported("page index version or layout"));
}
let described = cursor.u32()? as usize;
if described
!= table
.iter()
.filter(|r| pageable(r.kind, header.order))
.count()
{
return Err(bad());
}
let prefix_records: Vec<_> = table
.iter()
.filter(|r| r.kind == SECTION_PREFIX_FILTER && pageable(r.kind, header.order))
.collect();
let mut prefix_at = 0;
let mut seen = HashSet::new();
let mut filter = None;
let mut index = None;
let mut prefix_filters = Vec::new();
for _ in 0..described {
let id = SectionId {
kind: cursor.u32()?,
prefix_len: cursor.u16()?,
};
if cursor.u16()? != 0 {
return Err(FormatFault::unsupported(
"page index descriptor reserved bytes",
));
}
if !pageable(id.kind, header.order)
|| !seen.insert(id)
|| (id.kind != SECTION_PREFIX_FILTER && id.prefix_len != 0)
|| (id.kind == SECTION_PREFIX_FILTER
&& (id.prefix_len == 0 || id.prefix_len >= header.key_len))
{
return Err(bad());
}
let offset = cursor.u64()?;
let len = cursor.u64()?;
let chunks = cursor.u32()? as usize;
let payload_len = cursor.u32()? as usize;
let record = if id.kind == SECTION_PREFIX_FILTER {
let r = prefix_records.get(prefix_at).copied().ok_or_else(bad)?;
prefix_at += 1;
r
} else {
let mut matching = table.iter().filter(|r| r.kind == id.kind);
let r = matching.next().ok_or_else(bad)?;
if matching.next().is_some() {
return Err(bad());
}
r
};
if record.offset != offset
|| record.len != len
|| offset.checked_add(len).is_none()
|| chunks != chunk_count(offset, len)
{
return Err(bad());
}
let crc_bytes = cursor.take(chunks.checked_mul(4).ok_or_else(bad)?)?;
let crcs = crc_bytes
.as_chunks::<4>()
.0
.iter()
.map(|b| u32::from_le_bytes(*b))
.collect();
let section = PagedSection {
id,
offset,
len,
crcs,
};
let payload = cursor.take(payload_len)?;
if matches!(id.kind, SECTION_FILTER | SECTION_PREFIX_FILTER) {
let filter_at = if id.kind == SECTION_PREFIX_FILTER {
8
} else {
0
};
let filter_len = usize::try_from(len.checked_sub(filter_at).ok_or_else(bad)?)
.map_err(|_| bad())?;
let parsed = FilterTable::parse(payload, filter_len)?;
if payload.len() != FilterTable::head_len(parsed.bits) {
return Err(bad());
}
let skeleton = FilterSkeleton {
section,
filter_at,
table: Arc::new(parsed),
};
if id.kind == SECTION_FILTER {
if filter.replace(skeleton).is_some() {
return Err(bad());
}
} else {
prefix_filters.push((id.prefix_len, skeleton));
}
} else {
let expected_kind = match header.order {
OrderKind::ByHash => SECTION_BLOCK_INDEX,
OrderKind::ByKey => SECTION_SEPARATOR_INDEX,
};
if id.kind != expected_kind || index.is_some() {
return Err(bad());
}
let mut p = Cursor(payload);
let blocks = p.u32()? as usize;
let end_offset = p.u64()?;
if blocks == 0 || end_offset <= FILE_HEADER_LEN as u64 {
return Err(bad());
}
let groups = blocks.div_ceil(GROUP_BLOCKS);
let samples = if id.kind == SECTION_BLOCK_INDEX {
let record_bytes = len.checked_sub(8).ok_or_else(bad)?;
if record_bytes % 24 != 0
|| record_bytes / 24 != blocks as u64
|| p.0.len() != groups.checked_mul(8).ok_or_else(bad)?
{
return Err(bad());
}
let mut samples = Vec::with_capacity(groups);
for _ in 0..groups {
samples.push(p.u64()?);
}
if samples.windows(2).any(|w| w[0] >= w[1]) {
return Err(bad());
}
GroupSamples::Hash(samples)
} else {
let bytes_at = (blocks as u64)
.checked_mul(16)
.and_then(|n| n.checked_add(20))
.ok_or_else(bad)?;
let column_len = len.checked_sub(bytes_at).ok_or_else(bad)?;
if column_len > u64::from(u32::MAX) || groups > p.0.len() / 6 {
return Err(bad());
}
let mut starts = Vec::with_capacity(groups);
let mut separators = Vec::with_capacity(groups);
for g in 0..groups {
let start = p.u32()?;
let size = p.u16()? as usize;
let separator = p.take(size)?.to_vec();
if size > header.key_len as usize
|| u64::from(start) + size as u64 > column_len
|| (g == 0 && (start != 0 || size != 0))
|| starts.last().is_some_and(|&s| s > start)
|| separators.last().is_some_and(|s| s >= &separator)
{
return Err(bad());
}
starts.push(start);
separators.push(separator);
}
for g in 0..groups {
let end = starts.get(g + 1).map_or(column_len, |&s| u64::from(s));
let span = end.checked_sub(u64::from(starts[g])).ok_or_else(bad)?;
let count = (blocks - g * GROUP_BLOCKS).min(GROUP_BLOCKS);
let remaining = (count - 1) as u64;
let sample_len = separators[g].len() as u64;
if span < sample_len + remaining
|| span > sample_len + remaining * u64::from(header.key_len)
{
return Err(bad());
}
}
GroupSamples::Key { starts, separators }
};
if !p.0.is_empty() {
return Err(bad());
}
index = Some(IndexSkeleton {
section,
blocks,
end_offset,
samples,
});
}
}
if !cursor.0.is_empty() || prefix_at != prefix_records.len() {
return Err(bad());
}
Ok(Self {
filter: filter.ok_or_else(bad)?,
prefix_filters,
index: index.ok_or_else(bad)?,
})
}
pub(crate) fn derive(
sidecar: &[u8],
table: &[SectionRecord],
header: &SegHeader,
) -> Result<Self, FormatFault> {
let mut filter = None;
let mut prefix_filters = Vec::new();
let mut index = None;
for record in table.iter().filter(|r| pageable(r.kind, header.order)) {
let end = record.offset.checked_add(record.len).ok_or_else(bad)?;
let from = usize::try_from(record.offset).map_err(|_| bad())?;
let to = usize::try_from(end).map_err(|_| bad())?;
let body = sidecar.get(from..to).ok_or_else(bad)?;
let mut section = PagedSection {
id: SectionId {
kind: record.kind,
prefix_len: 0,
},
offset: record.offset,
len: record.len,
crcs: chunk_crcs(record.offset, body),
};
if matches!(record.kind, SECTION_FILTER | SECTION_PREFIX_FILTER) {
let filter_at = if record.kind == SECTION_PREFIX_FILTER {
8
} else {
0
};
if filter_at != 0 {
let mut wrapper = Cursor(body);
section.id.prefix_len = wrapper.u16()?;
if wrapper.take(6)? != [0; 6] {
return Err(bad());
}
}
let bytes = body.get(filter_at..).ok_or_else(bad)?;
let skeleton = FilterSkeleton {
section,
filter_at: filter_at as u64,
table: Arc::new(FilterTable::parse(bytes, bytes.len())?),
};
if record.kind == SECTION_FILTER {
filter = Some(skeleton);
} else {
prefix_filters.push((skeleton.section.id.prefix_len, skeleton));
}
} else {
let (blocks, end_offset, samples) = if record.kind == SECTION_BLOCK_INDEX {
let (records, end) = parse_index_records(body)?;
(
records.len(),
end,
GroupSamples::Hash(
records
.iter()
.step_by(GROUP_BLOCKS)
.map(|r| r.first_h)
.collect(),
),
)
} else {
let (n, starts_at, bytes_at) =
SeparatorIndex::validate(body, header.key_len as usize)?;
let mut starts = Vec::new();
let mut separators = Vec::new();
for i in (0..n).step_by(GROUP_BLOCKS) {
let mut c = Cursor(&body[starts_at + i * 4..]);
let start = c.u32()?;
let end = c.u32()?;
starts.push(start);
separators.push(
body[bytes_at + start as usize..bytes_at + end as usize].to_vec(),
);
}
let end = Cursor(&body[8 + n * 8..]).u64()?;
(n, end, GroupSamples::Key { starts, separators })
};
index = Some(IndexSkeleton {
section,
blocks,
end_offset,
samples,
});
}
}
let derived = Self {
filter: filter.ok_or_else(bad)?,
prefix_filters,
index: index.ok_or_else(bad)?,
};
Self::decode(&derived.encode(), table, header)
}
pub(crate) fn resident_bytes(&self) -> usize {
let filters =
std::iter::once(&self.filter).chain(self.prefix_filters.iter().map(|(_, f)| f));
let filter_heap: usize = filters
.map(|f| f.section.crcs.capacity() * 4 + f.table.resident_bytes())
.sum();
size_of::<Self>()
+ filter_heap
+ self.prefix_filters.capacity() * size_of::<(u16, FilterSkeleton)>()
+ self.index.section.crcs.capacity() * 4
+ match &self.index.samples {
GroupSamples::Hash(s) => s.capacity() * 8,
GroupSamples::Key { starts, separators } => {
starts.capacity() * 4
+ separators.capacity() * size_of::<Vec<u8>>()
+ separators.iter().map(|s| s.capacity()).sum::<usize>()
}
}
}
}
pub(crate) struct MetaIo {
#[cfg(test)]
ranges: std::sync::Mutex<Vec<(u64, usize)>>,
requests: AtomicU64,
chunks: AtomicU64,
bytes: AtomicU64,
#[cfg(any(test, feature = "test-faults"))]
attempts: AtomicU64,
#[cfg(any(test, feature = "test-faults"))]
fail_at: AtomicU64,
}
impl MetaIo {
#[cfg(test)]
pub(crate) fn ranges(&self) -> Vec<(u64, usize)> {
self.ranges.lock().expect("metadata range trace").clone()
}
pub(crate) fn new() -> Self {
Self {
#[cfg(test)]
ranges: std::sync::Mutex::new(Vec::new()),
requests: AtomicU64::new(0),
chunks: AtomicU64::new(0),
bytes: AtomicU64::new(0),
#[cfg(any(test, feature = "test-faults"))]
attempts: AtomicU64::new(0),
#[cfg(any(test, feature = "test-faults"))]
fail_at: AtomicU64::new(0),
}
}
#[cfg(any(test, feature = "test-faults"))]
pub(crate) fn fail_read_at(&self, n: u64) {
use std::sync::atomic::Ordering::SeqCst;
let at = if n == 0 {
0
} else {
self.attempts.load(SeqCst) + n
};
self.fail_at.store(at, SeqCst);
}
#[cfg(any(test, feature = "test-faults"))]
pub(crate) fn read_attempts(&self) -> u64 {
self.attempts.load(std::sync::atomic::Ordering::SeqCst)
}
pub(crate) fn read(
&self,
file: &File,
offset: u64,
len: usize,
chunks: usize,
) -> DbResult<Vec<u8>> {
#[cfg(any(test, feature = "test-faults"))]
{
use std::sync::atomic::Ordering::SeqCst;
let n = self.attempts.fetch_add(1, SeqCst) + 1;
if self.fail_at.load(SeqCst) == n {
return Err(DbError::Io(std::io::Error::other(
"injected metadata read failure",
)));
}
}
self.requests.fetch_add(1, Relaxed);
self.chunks.fetch_add(chunks as u64, Relaxed);
self.bytes.fetch_add(len as u64, Relaxed);
let mut buf = vec![0; len];
file.read_exact_at(&mut buf, offset)?;
#[cfg(test)]
self.ranges
.lock()
.expect("metadata range trace")
.push((offset, len));
Ok(buf)
}
pub(crate) fn requests(&self) -> u64 {
self.requests.load(Relaxed)
}
#[allow(dead_code)]
pub(crate) fn chunks(&self) -> u64 {
self.chunks.load(Relaxed)
}
pub(crate) fn bytes(&self) -> u64 {
self.bytes.load(Relaxed)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::seg::{manifest::SegRecord, seal::sidx_name, testkit};
#[test]
fn chunks_follow_file_pages() {
assert_eq!(chunk_count(4000, 5000), 3);
assert_eq!(chunk_range(4000, 5000, 0), (4000, 4096));
assert_eq!(chunk_range(4000, 5000, 1), (4096, 8192));
assert_eq!(chunk_range(4000, 5000, 2), (8192, 9000));
assert_eq!(chunk_count(8192, 4096), 1);
assert_eq!(chunk_count(10, 0), 0);
}
#[test]
fn chunk_crcs_cover_every_byte_once() {
let body: Vec<u8> = (0..9000u32).map(|i| i as u8).collect();
let crcs = chunk_crcs(4000, &body);
assert_eq!(crcs.len(), chunk_count(4000, 9000));
assert_eq!(crcs[0], crc32fast::hash(&body[..96]));
assert_eq!(crcs[1], crc32fast::hash(&body[96..96 + 4096]));
}
#[test]
fn covering_chunks_are_section_relative() {
let s = PagedSection {
id: SectionId {
kind: 2,
prefix_len: 0,
},
offset: 4000,
len: 9000,
crcs: vec![0; 4],
};
assert_eq!(s.chunks_covering(0, 96), 0..1);
assert_eq!(s.chunks_covering(95, 97), 0..2);
assert_eq!(s.chunks_covering(4300, 8999), 2..4);
}
fn sidecar_of(
dir: &std::path::Path,
rec: &SegRecord,
) -> (Vec<u8>, SegHeader, Vec<SectionRecord>) {
let bytes = std::fs::read(dir.join(sidx_name(rec.segment_id, rec.version))).unwrap();
let header = SegHeader::decode(&bytes, SIDX_MAGIC).unwrap();
let footer_at = bytes.len() - SIDX_FOOTER_LEN;
let (table_offset, count, crc) =
parse_footer(&bytes[footer_at..], bytes.len() as u64).unwrap();
let table = parse_table(
&bytes[table_offset as usize..footer_at],
count,
crc,
table_offset,
)
.unwrap();
(bytes, header, table)
}
#[test]
fn a_derived_page_index_round_trips_for_a_hash_segment() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_segment(
crate::seg::fs::real(),
dir.path(),
1,
&testkit::entries(50_000, 1),
);
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let derived = PageIndex::derive(&bytes, &table, &header).unwrap();
let decoded = PageIndex::decode(&derived.encode(), &table, &header).unwrap();
assert_eq!(decoded, derived);
assert_eq!(derived.index.blocks, bytes_blocks(&bytes, &table));
let GroupSamples::Hash(samples) = &derived.index.samples else {
panic!()
};
assert_eq!(samples.len(), derived.index.blocks.div_ceil(GROUP_BLOCKS));
}
#[test]
fn a_derived_page_index_round_trips_for_a_key_segment_with_prefix_filters() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_key_segment(dir.path(), &testkit::key_entries());
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let derived = PageIndex::derive(&bytes, &table, &header).unwrap();
assert_eq!(
derived
.prefix_filters
.iter()
.map(|(n, _)| *n)
.collect::<Vec<_>>(),
vec![4, 8]
);
assert!(derived.prefix_filters.iter().all(|(_, f)| f.filter_at == 8));
assert_eq!(
PageIndex::decode(&derived.encode(), &table, &header).unwrap(),
derived
);
}
#[test]
fn two_prefix_descriptors_reject_malformed_pairings_independently() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_key_segment(dir.path(), &testkit::key_entries());
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let encoded = PageIndex::derive(&bytes, &table, &header).unwrap().encode();
let mut at = 16;
let mut prefixes = Vec::new();
while at < encoded.len() {
let kind = u32::from_le_bytes(encoded[at..at + 4].try_into().unwrap());
let chunks = u32::from_le_bytes(encoded[at + 24..at + 28].try_into().unwrap()) as usize;
let payload =
u32::from_le_bytes(encoded[at + 28..at + 32].try_into().unwrap()) as usize;
let end = at + 32 + 4 * chunks + payload;
if kind == SECTION_PREFIX_FILTER {
prefixes.push(at..end);
}
at = end;
}
assert_eq!(prefixes.len(), 2);
let (a, b) = (&prefixes[0], &prefixes[1]);
let mut swapped = encoded.clone();
swapped.splice(
a.start..b.end,
encoded[b.clone()]
.iter()
.chain(encoded[a.clone()].iter())
.copied(),
);
assert!(PageIndex::decode(&swapped, &table, &header).is_err());
let mut duplicate_identity = encoded.clone();
duplicate_identity[b.start + 4..b.start + 6]
.copy_from_slice(&encoded[a.start + 4..a.start + 6]);
assert!(PageIndex::decode(&duplicate_identity, &table, &header).is_err());
let mut missing = encoded.clone();
missing.drain(b.clone());
missing[12..16].copy_from_slice(&3u32.to_le_bytes());
assert!(PageIndex::decode(&missing, &table, &header).is_err());
let mut repeated = encoded.clone();
repeated.splice(b.clone(), encoded[a.clone()].iter().copied());
assert!(PageIndex::decode(&repeated, &table, &header).is_err());
let mut wrong_record = encoded.clone();
wrong_record[b.start + 8..b.start + 24]
.copy_from_slice(&encoded[a.start + 8..a.start + 24]);
assert!(PageIndex::decode(&wrong_record, &table, &header).is_err());
}
#[test]
fn full_key_prefix_is_rejected_by_decode_and_derive() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_key_segment(dir.path(), &testkit::key_entries());
let (mut bytes, header, table) = sidecar_of(dir.path(), &rec);
let mut skeleton = PageIndex::derive(&bytes, &table, &header).unwrap();
skeleton.prefix_filters[0].0 = header.key_len;
skeleton.prefix_filters[0].1.section.id.prefix_len = header.key_len;
let decode_rejected = PageIndex::decode(&skeleton.encode(), &table, &header).is_err();
let prefix = table
.iter()
.find(|r| r.kind == SECTION_PREFIX_FILTER)
.unwrap();
let at = prefix.offset as usize;
bytes[at..at + 2].copy_from_slice(&header.key_len.to_le_bytes());
let derive_rejected = PageIndex::derive(&bytes, &table, &header).is_err();
assert_eq!((decode_rejected, derive_rejected), (true, true));
}
#[test]
fn multigroup_key_index_round_trips_and_rejects_impossible_spans() {
let dir = tempfile::tempdir().unwrap();
let entries: Vec<_> = (0..600)
.map(|n| {
let key = testkit::ordered_key(n);
testkit::TestEntry {
h: super::super::hash::key_hash(&key, testkit::SEED),
key,
value: Some(vec![42; 80]),
gsn: n + 1,
}
})
.collect();
let rec = testkit::write_key_segment(dir.path(), &entries);
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let good = PageIndex::derive(&bytes, &table, &header).unwrap();
let GroupSamples::Key { starts, .. } = &good.index.samples else {
panic!()
};
assert!(starts.len() >= 3);
assert_eq!(
PageIndex::decode(&good.encode(), &table, &header).unwrap(),
good
);
let mut rejected = Vec::new();
for (case, start) in [("empty first group", 0), ("undersized first group", 126)] {
let mut broken = good.clone();
let GroupSamples::Key { starts, .. } = &mut broken.index.samples else {
panic!()
};
starts[1] = start;
rejected.push((
case,
PageIndex::decode(&broken.encode(), &table, &header).is_err(),
));
}
let mut broken = good.clone();
let GroupSamples::Key { starts, separators } = &mut broken.index.samples else {
panic!()
};
starts[2] = starts[1] + separators[1].len() as u32 - 1;
rejected.push((
"overlapping samples",
PageIndex::decode(&broken.encode(), &table, &header).is_err(),
));
let mut broken = good.clone();
broken.index.blocks = 129;
broken.index.samples = GroupSamples::Key {
starts: vec![0, 0],
separators: vec![vec![], vec![1]],
};
broken.index.section.len = 20 + 129 * 16 + 1;
broken.index.section.crcs =
vec![0; chunk_count(broken.index.section.offset, broken.index.section.len)];
let mut small_table = table.clone();
small_table
.iter_mut()
.find(|r| r.kind == SECTION_SEPARATOR_INDEX)
.unwrap()
.len = broken.index.section.len;
rejected.push((
"one-byte column",
PageIndex::decode(&broken.encode(), &small_table, &header).is_err(),
));
let mut broken = good.clone();
broken.index.blocks = 2;
broken.index.samples = GroupSamples::Key {
starts: vec![0],
separators: vec![vec![]],
};
broken.index.section.len = 20 + 2 * 16;
broken.index.section.crcs =
vec![0; chunk_count(broken.index.section.offset, broken.index.section.len)];
small_table
.iter_mut()
.find(|r| r.kind == SECTION_SEPARATOR_INDEX)
.unwrap()
.len = broken.index.section.len;
rejected.push((
"empty final group",
PageIndex::decode(&broken.encode(), &small_table, &header).is_err(),
));
let mut broken = good.clone();
broken.index.blocks = 129;
let next_start = 127 * u32::from(header.key_len) + 1;
broken.index.samples = GroupSamples::Key {
starts: vec![0, next_start],
separators: vec![vec![], vec![1]],
};
broken.index.section.len = 20 + 129 * 16 + u64::from(next_start) + 1;
broken.index.section.crcs =
vec![0; chunk_count(broken.index.section.offset, broken.index.section.len)];
small_table
.iter_mut()
.find(|r| r.kind == SECTION_SEPARATOR_INDEX)
.unwrap()
.len = broken.index.section.len;
rejected.push((
"oversized separators",
PageIndex::decode(&broken.encode(), &small_table, &header).is_err(),
));
assert!(rejected.iter().all(|(_, refused)| *refused), "{rejected:?}");
}
#[test]
fn decode_refuses_an_inconsistent_page_index() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_segment(
crate::seg::fs::real(),
dir.path(),
1,
&testkit::entries(50_000, 1),
);
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let good = PageIndex::derive(&bytes, &table, &header).unwrap();
for broken in [
{
let mut p = good.clone();
p.filter.section.offset += 1;
p
}, {
let mut p = good.clone();
p.filter.section.crcs.pop();
p
}, {
let mut p = good.clone();
p.index.blocks += 1;
p
}, {
let mut p = good.clone();
if let GroupSamples::Hash(s) = &mut p.index.samples {
s.swap(0, 1)
};
p
}, ] {
assert!(PageIndex::decode(&broken.encode(), &table, &header).is_err());
}
let mut twice = good.encode();
twice[12..16].copy_from_slice(&3u32.to_le_bytes());
assert!(PageIndex::decode(&twice, &table, &header).is_err());
}
fn bytes_blocks(_: &[u8], table: &[SectionRecord]) -> usize {
((table
.iter()
.find(|r| r.kind == SECTION_BLOCK_INDEX)
.unwrap()
.len
- 8)
/ 24) as usize
}
#[test]
fn malformed_page_index_is_bounded() {
let dir = tempfile::tempdir().unwrap();
let rec = testkit::write_segment(
crate::seg::fs::real(),
dir.path(),
1,
&testkit::entries(5_000, 1),
);
let (bytes, header, table) = sidecar_of(dir.path(), &rec);
let encoded = PageIndex::derive(&bytes, &table, &header).unwrap().encode();
for end in 0..encoded.len() {
assert!(PageIndex::decode(&encoded[..end], &table, &header).is_err());
}
for at in [12, 40, 44] {
let mut broken = encoded.clone();
broken[at..at + 4].fill(255);
assert!(PageIndex::decode(&broken, &table, &header).is_err());
}
let mut overflow = table.clone();
overflow[0].offset = u64::MAX;
assert!(PageIndex::derive(&bytes, &overflow, &header).is_err());
}
fn golden_page_index() -> PageIndex {
use super::super::filter::{FuseParams, PartMeta};
PageIndex {
filter: FilterSkeleton {
section: PagedSection {
id: SectionId {
kind: SECTION_FILTER,
prefix_len: 0,
},
offset: 64,
len: 40,
crcs: vec![0x11223344],
},
filter_at: 0,
table: Arc::new(FilterTable {
bits: 0,
parts: vec![PartMeta {
offset: 40,
len: 0,
keys: 0,
params: FuseParams {
seed: 0,
segment_length: 0,
segment_count_length: 0,
},
}],
}),
},
prefix_filters: vec![],
index: IndexSkeleton {
section: PagedSection {
id: SectionId {
kind: SECTION_BLOCK_INDEX,
prefix_len: 0,
},
offset: 104,
len: 80,
crcs: vec![0x55667788],
},
blocks: 3,
end_offset: 364,
samples: GroupSamples::Hash(vec![0x10]),
},
}
}
#[test]
fn page_index_golden_bytes() {
let expected = GOLDEN;
assert_eq!(golden_page_index().encode(), expected);
}
#[test]
fn metadata_reads_count_requests_chunks_bytes_and_propagate_errors() {
use std::io::Write;
let mut file = tempfile::tempfile().unwrap();
file.write_all(b"abcdefgh").unwrap();
let io = MetaIo::new();
assert_eq!(io.read(&file, 2, 4, 2).unwrap(), b"cdef");
assert_eq!((io.requests(), io.chunks(), io.bytes()), (1, 2, 4));
assert!(io.read(&file, 7, 2, 1).is_err());
assert_eq!((io.requests(), io.chunks(), io.bytes()), (2, 3, 6));
}
#[test]
fn metadata_read_failure_injection_precedes_io_accounting() {
let file = tempfile::tempfile().unwrap();
let io = MetaIo::new();
io.fail_read_at(1);
assert!(matches!(io.read(&file, 0, 0, 0), Err(DbError::Io(_))));
assert_eq!((io.requests(), io.chunks(), io.bytes()), (0, 0, 0));
assert!(io.read(&file, 0, 0, 0).is_ok(), "the injection is one-shot");
assert_eq!(io.read_attempts(), 2);
}
#[test]
fn metadata_read_failure_injection_is_scoped_to_its_io() {
let file = tempfile::tempfile().unwrap();
let (armed, other) = (MetaIo::new(), MetaIo::new());
assert!(other.read(&file, 0, 0, 0).is_ok());
armed.fail_read_at(2);
assert!(
other.read(&file, 0, 0, 0).is_ok(),
"another collection's reads"
);
assert!(armed.read(&file, 0, 0, 0).is_ok());
assert!(matches!(armed.read(&file, 0, 0, 0), Err(DbError::Io(_))));
armed.fail_read_at(1);
armed.fail_read_at(0);
assert!(armed.read(&file, 0, 0, 0).is_ok(), "zero disarms");
}
const GOLDEN: &[u8] = &[
0x01, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00,
0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x28,
0x00, 0x00, 0x00, 0x44, 0x33, 0x22, 0x11, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x68, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x50, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
0x14, 0x00, 0x00, 0x00, 0x88, 0x77, 0x66, 0x55, 0x03, 0x00, 0x00, 0x00, 0x6c, 0x01, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
];
}