chadtmiller.com/monolith
An atproto PDS
0
0
//! A sorted table: keys and values, in ascending order of key, written once
//! as they come and read by key or in order without reading the whole file.
//!
//! The file is data blocks, then the index, then the bloom filter, then the
//! footer:
//!
//! - a **data block** is entries, each `[varint key length][key][varint value
//! length][value]`, ending where the next block begins, then 8 bytes of
//! check over the entries. A block holds entries until it passes the
//! writer's block size, `BLOCK` unless it is given another: a value larger
//! than that is a block of its own. A reader reads blocks of any size;
//! - the **index** is, for each block in order, `[varint key length][a
//! key][varint offset][varint length]`, the length its check's too, then 8
//! bytes of check over it. The key is the block's last, or one shorter
//! that is after it and before the next block's first: every key of the
//! block is at or before it, and every key of the next after it;
//! - the **bloom filter** is the number of its hash functions, one byte, then
//! its bits, then 8 bytes of check over both. A key's bits are those
//! numbered `a + i * b`, modulo how many bits there are, for each `i`
//! below the number of hash functions: `a` and `b` are two hashes of the
//! key, `b` with its lowest bit set;
//! - the **footer** is its version's magic, then the index's offset, the
//! index's length, the bloom filter's length and the number of entries,
//! each a u64, little-endian: 40 bytes, and in `PDSTAB02` 8 bytes of
//! check over those.
//!
//! The format has two versions (`Version`), told by the magic:
//!
//! - `PDSTAB02`, which a writer writes: a check is XXH3-64 of the bytes,
//! little-endian, and the hashes are the halves of XXH3-128 of the key,
//! the low half `a`. Its footer has a check, so every byte of the file
//! is under one;
//! - `PDSTAB01`, written before and read as it was: a check is the first 8
//! bytes of SHA-256 of the bytes, and the hashes are the first 16 bytes
//! of SHA-256 of the key, 8 each, little-endian. Its footer has no
//! check: where it says the index and the filter are, the file's size
//! and their checks bear out, and its number of entries nothing does.
//!
//! What it reads it checks: a check that does not match, anything that
//! does not parse, or a number of entries the blocks' bytes could not
//! hold, is an error naming the file, and nothing of it is used. The check
//! is against accident: a block cut short, rotted, or not the one written
//! there. It lies beside the bytes it checks, so neither version's holds
//! against whoever can write the file; and XXH3, which is no cryptographic
//! hash, is not for a table taken from anyone but its writer.
//!
//! Blocks read are kept in a `BlockCache` shared by every table, which also
//! keeps the files of the tables opened with it open, at most so many at
//! once: a table whose file was closed to make room opens it again when it
//! next reads a block, and takes it only if it is the file it was opened
//! from. A table replaced or removed is still read whole by whoever holds
//! its file (`Table::file`); its own file is closed when it is dropped.
use sha2::{Digest, Sha256};
use std::collections::BTreeMap;
use std::fs::File;
use std::io::{self, Write};
use std::ops::Bound;
use std::os::unix::fs::{FileExt, MetadataExt};
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex, MutexGuard, PoisonError, Weak};
use xxhash_rust::xxh3::{xxh3_64, xxh3_128};
/// The bytes past which a data block is ended.
pub const BLOCK: usize = 4 << 10;
/// The tables' files a `BlockCache` made for a table or a few keeps open
/// at once (`BlockCache::new`): the least share of the process's file
/// descriptors.
const FEW: usize = crate::files::LEAST;
/// The bytes of a footer's magic and numbers.
const FOOTER: usize = 40;
/// The bytes of a check.
const CHECK: usize = 8;
/// The bytes of a table's end read at once when it is opened: the footer,
/// and of a table of a few hundred records its index and bloom filter too.
const TAIL: u64 = 8 << 10;
/// The blocks whose index keys are held as what follows the bytes each
/// shares with the first of them: keys of one section begin alike.
const GROUP: usize = 16;
/// Bits of the bloom filter for each entry.
const BLOOM_BITS: u64 = 10;
/// A version of the format: what a check is, which two hashes of a key
/// say which bits of the bloom filter are its, and whether the footer has
/// a check.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Version {
/// `PDSTAB01`, written before and read as it was: SHA-256.
Sha256,
/// `PDSTAB02`, which is written: XXH3.
Xxh3,
}
impl Version {
/// The version a writer writes.
pub const WRITTEN: Version = Version::Xxh3;
/// What a table of it begins its footer with.
pub const fn magic(self) -> &'static [u8; 8] {
match self {
Version::Sha256 => b"PDSTAB01",
Version::Xxh3 => b"PDSTAB02",
}
}
/// The bytes of its footer: with its check, if it has one.
pub const fn footer(self) -> usize {
match self {
Version::Sha256 => FOOTER,
Version::Xxh3 => FOOTER + CHECK,
}
}
/// The version of the table that `file`, a file or the end of one,
/// ends as: the one whose magic is where its footer would begin.
pub fn of(file: &[u8]) -> Option<Version> {
[Version::Xxh3, Version::Sha256].into_iter().find(|v| {
let at = file.len().checked_sub(v.footer());
at.is_some_and(|at| file[at..at + 8] == *v.magic())
})
}
fn check(self, bytes: &[u8]) -> [u8; CHECK] {
match self {
Version::Sha256 => {
let d = Sha256::digest(bytes);
let mut out = [0u8; CHECK];
out.copy_from_slice(&d[..CHECK]);
out
}
Version::Xxh3 => xxh3_64(bytes).to_le_bytes(),
}
}
/// The two hashes of `key` the bloom filter's are made of, the second
/// with its lowest bit set.
fn hashes(self, key: &[u8]) -> (u64, u64) {
let (a, b) = match self {
Version::Sha256 => {
let d = Sha256::digest(key);
(
u64::from_le_bytes(d[..8].try_into().expect("8 bytes")),
u64::from_le_bytes(d[8..16].try_into().expect("8 bytes")),
)
}
Version::Xxh3 => {
let h = xxh3_128(key);
(h as u64, (h >> 64) as u64)
}
};
(a, b | 1)
}
}
fn lock<T>(m: &Mutex<T>) -> MutexGuard<'_, T> {
m.lock().unwrap_or_else(PoisonError::into_inner)
}
fn varint(out: &mut Vec<u8>, mut n: u64) {
loop {
let b = (n & 0x7f) as u8;
n >>= 7;
if n == 0 {
out.push(b);
return;
}
out.push(b | 0x80);
}
}
fn read_varint(bytes: &[u8], pos: &mut usize) -> Option<u64> {
let mut n = 0u64;
for shift in (0..64).step_by(7) {
let b = *bytes.get(*pos)?;
*pos += 1;
n |= u64::from(b & 0x7f) << shift;
if b & 0x80 == 0 {
return Some(n);
}
}
None
}
/// A bloom filter over a table's keys, each given as its two hashes
/// (`Version::hashes`).
struct Bloom {
k: u8,
bits: Vec<u8>,
}
impl Bloom {
fn new(entries: u64) -> Bloom {
let n = (entries.max(1) * BLOOM_BITS).div_ceil(8).max(8) as usize;
Bloom {
k: 7,
bits: vec![0; n],
}
}
/// Which bits are those of the key whose hashes are `a` and `b`.
fn positions(&self, (a, b): (u64, u64)) -> impl Iterator<Item = usize> + use<> {
let m = (self.bits.len() * 8) as u64;
(0..u64::from(self.k)).map(move |i| (a.wrapping_add(i.wrapping_mul(b)) % m) as usize)
}
fn add(&mut self, hashes: (u64, u64)) {
for p in self.positions(hashes) {
self.bits[p / 8] |= 1 << (p % 8);
}
}
fn may_hold(&self, hashes: (u64, u64)) -> bool {
self.positions(hashes)
.all(|p| self.bits[p / 8] & (1 << (p % 8)) != 0)
}
}
/// How many bytes `a` and `b` begin with alike.
fn common(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let mut i = 0;
while i + 8 <= n && a[i..i + 8] == b[i..i + 8] {
i += 8;
}
while i < n && a[i] == b[i] {
i += 1;
}
i
}
/// Make `last` a key no longer than it that is at or after it and before
/// `next`, which is after it: the shortest there is that begins as `last`
/// does up to where the two part, or `last` as it is.
fn shorten(last: &mut Vec<u8>, next: &[u8]) {
let same = common(last, next);
// `next` goes on from `last`: nothing shorter is at or after `last`.
if same == last.len() {
return;
}
// Where they part, a byte between the two; or, with none between, the
// first byte after that can be one more.
let at = if last[same] + 1 < next[same] {
Some(same)
} else {
(same + 1..last.len()).find(|&i| last[i] != 0xff)
};
if let Some(at) = at {
last[at] += 1;
last.truncate(at + 1);
}
}
/// A table being written: keys given in strictly ascending order.
pub struct TableWriter<W: Write> {
out: W,
version: Version,
at: u64,
/// The bytes past which a block is ended.
size: usize,
block: Vec<u8>,
last: Vec<u8>,
/// The block written last, while the index has no entry for it: its
/// last key, its offset and its length.
ended: Option<(Vec<u8>, u64, u64)>,
index: Vec<u8>,
bloom: Bloom,
count: u64,
}
impl<W: Write> TableWriter<W> {
/// A table written to `out`, its bloom filter sized for about `entries` entries.
pub fn new(out: W, entries: u64) -> TableWriter<W> {
TableWriter::with_block(out, entries, BLOCK)
}
/// The same, a block ended past `size` bytes.
pub fn with_block(out: W, entries: u64, size: usize) -> TableWriter<W> {
TableWriter::of_version(out, entries, size, Version::WRITTEN)
}
/// The same, of `version`: of the one before, for what checks that a
/// table of it is still read.
pub fn of_version(out: W, entries: u64, size: usize, version: Version) -> TableWriter<W> {
TableWriter {
out,
version,
at: 0,
size,
block: Vec::new(),
last: Vec::new(),
ended: None,
index: Vec::new(),
bloom: Bloom::new(entries),
count: 0,
}
}
/// Add an entry, its key after every key before.
pub fn add(&mut self, key: &[u8], value: &[u8]) -> io::Result<()> {
if self.count > 0 && key <= self.last.as_slice() {
return Err(io::Error::new(
io::ErrorKind::InvalidInput,
"a table's keys out of order",
));
}
if !self.block.is_empty() && self.block.len() + key.len() + value.len() > self.size {
self.end_block()?;
}
self.place(Some(key));
varint(&mut self.block, key.len() as u64);
self.block.extend_from_slice(key);
varint(&mut self.block, value.len() as u64);
self.block.extend_from_slice(value);
self.last.clear();
self.last.extend_from_slice(key);
self.bloom.add(self.version.hashes(key));
self.count += 1;
if self.block.len() >= self.size {
self.end_block()?;
}
Ok(())
}
fn end_block(&mut self) -> io::Result<()> {
if self.block.is_empty() {
return Ok(());
}
let c = self.version.check(&self.block);
self.block.extend_from_slice(&c);
self.out.write_all(&self.block)?;
self.ended = Some((self.last.clone(), self.at, self.block.len() as u64));
self.at += self.block.len() as u64;
self.block.clear();
Ok(())
}
/// Give the index its entry for the block written last, if it has none:
/// `next` is the key the next block begins with, if there is one.
fn place(&mut self, next: Option<&[u8]>) {
let Some((mut key, offset, len)) = self.ended.take() else {
return;
};
if let Some(next) = next {
shorten(&mut key, next);
}
varint(&mut self.index, key.len() as u64);
self.index.extend_from_slice(&key);
varint(&mut self.index, offset);
varint(&mut self.index, len);
}
/// Write the rest: answers the writer and the table's bytes.
pub fn finish(mut self) -> io::Result<(W, u64)> {
self.end_block()?;
self.place(None);
let c = self.version.check(&self.index);
self.index.extend_from_slice(&c);
let mut bloom = vec![self.bloom.k];
bloom.extend_from_slice(&self.bloom.bits);
let c = self.version.check(&bloom);
bloom.extend_from_slice(&c);
let mut footer = self.version.magic().to_vec();
for n in [
self.at,
self.index.len() as u64,
bloom.len() as u64,
self.count,
] {
footer.extend_from_slice(&n.to_le_bytes());
}
// Its check, in a version whose footer has one.
if self.version.footer() > FOOTER {
let c = self.version.check(&footer);
footer.extend_from_slice(&c);
}
self.out.write_all(&self.index)?;
self.out.write_all(&bloom)?;
self.out.write_all(&footer)?;
self.out.flush()?;
let size = self.at + (self.index.len() + bloom.len() + footer.len()) as u64;
Ok((self.out, size))
}
}
/// Which file a table was read from: its device and inode, its size, and
/// when it was last written, in seconds and nanoseconds.
type Which = (u64, u64, u64, i64, i64);
fn which(meta: &std::fs::Metadata) -> Which {
(
meta.dev(),
meta.ino(),
meta.len(),
meta.mtime(),
meta.mtime_nsec(),
)
}
/// A table's file, read: its index and bloom filter held, its blocks read as needed.
pub struct Table {
path: PathBuf,
/// Which table it is, among all those opened, for the block cache.
id: u64,
version: Version,
/// The index's keys, one after another, and where each one ends: the
/// first of each `GROUP` blocks whole, and of each other what follows
/// the `shared` bytes it begins with as that one does.
keys: Box<[u8]>,
ends: Box<[u32]>,
shared: Box<[u16]>,
/// Where each block begins in the file, and where the last ends.
starts: Box<[u64]>,
bloom: Bloom,
count: u64,
size: u64,
which: Which,
/// Its file among those a cache keeps open: none for a table opened of
/// a file its reader holds (`open_file`).
slot: Option<Arc<Slot>>,
}
fn bad(path: &Path, why: &str) -> io::Error {
io::Error::new(
io::ErrorKind::InvalidData,
format!("{}: {why}", path.display()),
)
}
/// Whether `file` ends as a table of a known version does: with its footer.
pub fn is_table(file: &[u8]) -> bool {
Version::of(file).is_some()
}
/// A block's entries: what it holds before its check.
fn entries_of(block: &[u8]) -> &[u8] {
&block[..block.len() - CHECK]
}
impl Table {
/// Read a table's index and bloom filter. Its file stays open, one of
/// those `cache` keeps open, and is closed when the table is dropped.
pub fn open(path: &Path, cache: &BlockCache) -> io::Result<Table> {
let file = File::open(path)?;
let mut t = Table::open_file(path, &file)?;
let slot = Arc::new(Slot {
file: Mutex::new(None),
last: AtomicU64::new(0),
files: cache.files.clone(),
});
slot.hold(Arc::new(file));
t.slot = Some(slot);
Ok(t)
}
/// The same, of a file opened at `path` that its reader holds, and
/// gives each read.
pub fn open_file(path: &Path, file: &File) -> io::Result<Table> {
static IDS: AtomicU64 = AtomicU64::new(1);
let which = which(&file.metadata()?);
let size = which.2;
if size < FOOTER as u64 {
return Err(bad(path, "too short for a table"));
}
let read = size.min(TAIL);
let mut tail = vec![0u8; read as usize];
file.read_exact_at(&mut tail, size - read)?;
let version =
Version::of(&tail).ok_or_else(|| bad(path, "not a table of a known version"))?;
let (before, footer) = tail.split_at(tail.len() - version.footer());
let (footer, c) = footer.split_at(FOOTER);
if !c.is_empty() && version.check(footer) != c {
return Err(bad(path, "its footer fails its check"));
}
let n = |i: usize| {
u64::from_le_bytes(footer[8 + i * 8..16 + i * 8].try_into().expect("8 bytes"))
};
let (index_at, index_len, bloom_len, count) = (n(0), n(1), n(2), n(3));
if index_at
.checked_add(index_len)
.and_then(|x| x.checked_add(bloom_len))
.and_then(|x| x.checked_add(version.footer() as u64))
!= Some(size)
|| index_len < 8
|| bloom_len < 10
{
return Err(bad(path, "a footer that does not fit the file"));
}
// An entry is two bytes at least, its two lengths.
if count > index_at / 2 {
return Err(bad(path, "more entries than its blocks could hold"));
}
let rest_len = (index_len + bloom_len) as usize;
let more;
let rest = if rest_len <= before.len() {
&before[before.len() - rest_len..]
} else {
let mut buf = vec![0u8; rest_len];
file.read_exact_at(&mut buf, index_at)?;
more = buf;
&more[..]
};
let (index, bloom) = rest.split_at(index_len as usize);
let (index, c) = index.split_at(index.len() - CHECK);
if version.check(index) != c {
return Err(bad(path, "its index fails its check"));
}
let (bloom, c) = bloom.split_at(bloom.len() - CHECK);
if version.check(bloom) != c || bloom[0] == 0 {
return Err(bad(path, "its bloom filter fails its check"));
}
// Room for a block for each 16 bytes of the index, about what one
// takes there: more are made room for as they come.
let blocks = index.len() / 16;
let mut keys = Vec::with_capacity(index.len() / 2);
let (mut ends, mut shared) = (Vec::with_capacity(blocks), Vec::with_capacity(blocks));
let mut starts = Vec::with_capacity(blocks + 1);
let mut pos = 0;
let mut end = 0u64;
let mut prev: Option<&[u8]> = None;
let mut first: &[u8] = &[];
while pos < index.len() {
let parsed = (|| {
let k = read_varint(index, &mut pos)? as usize;
let key = index.get(pos..pos.checked_add(k)?)?;
pos += k;
let offset = read_varint(index, &mut pos)?;
let len = u32::try_from(read_varint(index, &mut pos)?).ok()?;
Some((key, offset, len))
})();
let (key, offset, len) =
parsed.ok_or_else(|| bad(path, "an index that does not parse"))?;
if offset != end || (len as usize) < CHECK || prev.is_some_and(|p| p >= key) {
return Err(bad(path, "an index out of order"));
}
prev = Some(key);
let same = if starts.len() % GROUP == 0 {
first = key;
0
} else {
common(first, key).min(usize::from(u16::MAX))
};
shared.push(same as u16);
keys.extend_from_slice(&key[same..]);
ends.push(
u32::try_from(keys.len()).map_err(|_| bad(path, "an index too large to hold"))?,
);
starts.push(offset);
end = offset
.checked_add(u64::from(len))
.ok_or_else(|| bad(path, "an index out of order"))?;
}
if end != index_at {
return Err(bad(path, "an index that does not cover its blocks"));
}
starts.push(end);
let bloom = Bloom {
k: bloom[0],
bits: bloom[1..].to_vec(),
};
Ok(Table {
path: path.to_path_buf(),
id: IDS.fetch_add(1, Ordering::Relaxed),
version,
keys: keys.into_boxed_slice(),
ends: ends.into_boxed_slice(),
shared: shared.into_boxed_slice(),
starts: starts.into_boxed_slice(),
bloom,
count,
size,
which,
slot: None,
})
}
/// Its file.
pub fn path(&self) -> &Path {
&self.path
}
/// The number the block cache holds its blocks by.
pub fn id(&self) -> u64 {
self.id
}
/// The version of the format it is in.
pub fn version(&self) -> Version {
self.version
}
/// How many entries it holds.
pub fn len(&self) -> u64 {
self.count
}
pub fn is_empty(&self) -> bool {
self.count == 0
}
/// Its file's bytes.
pub fn size(&self) -> u64 {
self.size
}
/// How many data blocks it has.
pub fn blocks(&self) -> usize {
self.ends.len()
}
/// The bytes it takes in memory: its index and bloom filter, and what
/// it holds besides.
pub fn cost(&self) -> u64 {
(self.keys.len()
+ self.ends.len() * 6
+ self.starts.len() * 8
+ self.bloom.bits.len()
+ self.path.as_os_str().len()
+ 384) as u64
}
/// Whether it may hold `key`: false only if it does not.
pub fn may_hold(&self, key: &[u8]) -> bool {
self.bloom.may_hold(self.version.hashes(key))
}
/// What the index holds of block `i`'s key.
fn kept(&self, i: usize) -> &[u8] {
let from = if i == 0 { 0 } else { self.ends[i - 1] as usize };
&self.keys[from..self.ends[i] as usize]
}
/// Whether block `i`'s index key is before `key`.
fn before(&self, i: usize, key: &[u8]) -> bool {
let shared = usize::from(self.shared[i]);
let begins = &self.kept(i - i % GROUP)[..shared];
match begins.cmp(&key[..shared.min(key.len())]) {
// They begin alike, so `key` is no shorter than that: the rest decides.
std::cmp::Ordering::Equal => self.kept(i) < &key[shared..],
order => order.is_lt(),
}
}
/// The first block whose index key is `key` or after: the one that
/// holds `key` if any does, or the number of blocks.
fn find(&self, key: &[u8]) -> usize {
let (mut lo, mut hi) = (0, self.blocks());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if self.before(mid, key) {
lo = mid + 1;
} else {
hi = mid;
}
}
lo
}
/// The file at its path, opened: an error if that is no longer the file
/// it was opened from, as when the table was replaced.
fn reopen(&self) -> io::Result<File> {
let file = File::open(&self.path)?;
if which(&file.metadata()?) != self.which {
return Err(io::Error::new(
io::ErrorKind::NotFound,
format!(
"{}: no longer the table that was opened",
self.path.display()
),
));
}
Ok(file)
}
/// Its file, open: the one its cache keeps open, opened again if it was
/// closed to make room. Whoever holds what this answers reads the table
/// through it (`get_in`, `iter`) whatever becomes of its path after.
pub fn file(&self) -> io::Result<Arc<File>> {
let Some(slot) = &self.slot else {
return self.reopen().map(Arc::new);
};
if let Some(f) = slot.held() {
return Ok(f);
}
Ok(slot.hold(Arc::new(self.reopen()?)))
}
/// Block `i`, check and all, from the cache or from `file` (its own if none).
fn block(&self, i: usize, file: Option<&File>, cache: &BlockCache) -> io::Result<Arc<[u8]>> {
let key = Key::Block(self.id, self.starts[i]);
match cache.get(&key) {
Some(b) => Ok(b),
None => self.read(i, key, file, cache),
}
}
/// Block `i` read from `file` (its own if none), checked, and kept in
/// the cache by `key`.
fn read(
&self,
i: usize,
key: Key,
file: Option<&File>,
cache: &BlockCache,
) -> io::Result<Arc<[u8]>> {
let offset = self.starts[i];
let len = (self.starts[i + 1] - offset) as usize;
let mut block: Arc<[u8]> = std::iter::repeat_n(0u8, len).collect();
let buf = Arc::get_mut(&mut block).expect("held by nothing else yet");
match file {
Some(f) => f.read_exact_at(buf, offset)?,
None => self.file()?.read_exact_at(buf, offset)?,
}
cache.read.fetch_add(len as u64, Ordering::Relaxed);
let (entries, c) = buf.split_at(len - CHECK);
if self.version.check(entries) != c {
return Err(bad(
&self.path,
&format!("the block at {offset} fails its check"),
));
}
cache.put(key, block.clone());
Ok(block)
}
/// The value of `key`, if it holds it.
pub fn get(&self, key: &[u8], cache: &BlockCache) -> io::Result<Option<Vec<u8>>> {
self.get_in(key, None, cache)
}
/// The same, read from `file`, this table's file opened.
pub fn get_in(
&self,
key: &[u8],
file: Option<&File>,
cache: &BlockCache,
) -> io::Result<Option<Vec<u8>>> {
let i = self.find(key);
if i == self.blocks() {
return Ok(None);
}
let at = Key::Block(self.id, self.starts[i]);
let block = match cache.get(&at) {
Some(b) => b,
// Not in memory: the bloom filter says whether the file need be read.
None if !self.may_hold(key) => return Ok(None),
None => self.read(i, at, file, cache)?,
};
let entries = entries_of(&block);
let mut pos = 0;
while pos < entries.len() {
let (k, v) = entry(entries, &mut pos)
.ok_or_else(|| bad(&self.path, "a block that does not parse"))?;
if k == key {
return Ok(Some(v.to_vec()));
}
if k > key {
break;
}
}
Ok(None)
}
/// Its entries in order, from the first whose key is `from` or after.
pub fn iter<'a>(
&'a self,
from: &[u8],
file: Option<&'a File>,
cache: &'a BlockCache,
) -> Iter<'a> {
self.iter_from(self.find(from), from, false, file, cache)
}
/// Its entries in descending order, from the last whose key is before `before`.
pub fn iter_back<'a>(
&'a self,
before: &[u8],
file: Option<&'a File>,
cache: &'a BlockCache,
) -> Iter<'a> {
let block = self.find(before).min(self.blocks().saturating_sub(1));
self.iter_from(block, before, true, file, cache)
}
fn iter_from<'a>(
&'a self,
block: usize,
bound: &[u8],
back: bool,
file: Option<&'a File>,
cache: &'a BlockCache,
) -> Iter<'a> {
Iter {
t: self,
file,
cache,
block,
held: None,
pos: 0,
left: Vec::new(),
bound: bound.to_vec(),
back,
failed: false,
}
}
}
/// The entry of a block's `entries` at `pos`, which is moved past it: its
/// key and value, or None if it does not parse.
fn entry<'a>(entries: &'a [u8], pos: &mut usize) -> Option<(&'a [u8], &'a [u8])> {
let k = read_varint(entries, pos)? as usize;
let key = entries.get(*pos..pos.checked_add(k)?)?;
*pos += k;
let v = read_varint(entries, pos)? as usize;
let value = entries.get(*pos..pos.checked_add(v)?)?;
*pos += v;
Some((key, value))
}
/// A table's entries in order, or in descending order, each block read as
/// it is reached and each entry taken from it as it is asked for.
pub struct Iter<'a> {
t: &'a Table,
file: Option<&'a File>,
cache: &'a BlockCache,
/// The next block to read.
block: usize,
/// The block being read.
held: Option<Arc<[u8]>>,
/// In order: where its next entry begins.
pos: usize,
/// In descending order: where each of its entries still to give begins,
/// the next one last.
left: Vec<usize>,
/// The first key, or the key the entries are before.
bound: Vec<u8>,
back: bool,
failed: bool,
}
impl Iter<'_> {
fn fail(&mut self) -> Option<io::Result<(Vec<u8>, Vec<u8>)>> {
self.failed = true;
Some(Err(bad(&self.t.path, "a block that does not parse")))
}
}
impl Iterator for Iter<'_> {
type Item = io::Result<(Vec<u8>, Vec<u8>)>;
fn next(&mut self) -> Option<Self::Item> {
loop {
if self.failed {
return None;
}
if let Some(block) = self.held.as_deref() {
let entries = entries_of(block);
let at = if self.back {
self.left.pop()
} else {
(self.pos < entries.len()).then_some(self.pos)
};
let Some(mut at) = at else {
self.held = None;
continue;
};
let Some((k, v)) = entry(entries, &mut at) else {
return self.fail();
};
if !self.back {
self.pos = at;
if k < self.bound.as_slice() {
continue;
}
}
return Some(Ok((k.to_vec(), v.to_vec())));
}
if self.block >= self.t.blocks() {
return None;
}
let block = match self.t.block(self.block, self.file, self.cache) {
Ok(b) => b,
Err(e) => {
self.failed = true;
return Some(Err(e));
}
};
if self.back {
let entries = entries_of(&block);
let mut pos = 0;
while pos < entries.len() {
let at = pos;
match entry(entries, &mut pos) {
Some((k, _)) if k < self.bound.as_slice() => self.left.push(at),
Some(_) => break,
None => return self.fail(),
}
}
// Past the first block: done after it.
self.block = if self.block == 0 {
self.t.blocks()
} else {
self.block - 1
};
} else {
self.pos = 0;
self.block += 1;
}
self.held = Some(block);
}
}
}
// ---- The files held open ---------------------------------------------------------
/// The files of the tables opened with one cache: at most `max` of them
/// are open at once, the least recently read closed to make room.
struct Files {
max: usize,
/// How many are open.
open: AtomicUsize,
/// A count of the reads through them, for which was read last.
tick: AtomicU64,
/// The slots whose files are open, each by the tick it was opened at
/// or, later, found read at: the first is the least recently read, once
/// one read since is put back where it belongs.
order: Mutex<BTreeMap<u64, Weak<Slot>>>,
}
/// A table's file while it is open, among those of a cache.
struct Slot {
file: Mutex<Option<Arc<File>>>,
/// The tick of its last read.
last: AtomicU64,
files: Arc<Files>,
}
impl Slot {
/// Its file, if it is open, read now.
fn held(&self) -> Option<Arc<File>> {
let f = lock(&self.file).clone()?;
self.last.store(
self.files.tick.fetch_add(1, Ordering::Relaxed),
Ordering::Relaxed,
);
Some(f)
}
/// Keep `file` open as its file, closing the least recently read of the
/// others' past the most there may be: answers the file to read, which
/// is the one already open if another reader opened it meanwhile.
fn hold(self: &Arc<Slot>, file: Arc<File>) -> Arc<File> {
let files = &self.files;
let tick = {
let mut held = lock(&self.file);
if let Some(f) = held.as_ref() {
return f.clone();
}
*held = Some(file.clone());
let tick = files.tick.fetch_add(1, Ordering::Relaxed);
self.last.store(tick, Ordering::Relaxed);
files.open.fetch_add(1, Ordering::Relaxed);
tick
};
// Closed once the lock is let go.
let mut closed = Vec::new();
let mut order = lock(&files.order);
order.insert(tick, Arc::downgrade(self));
// A file read since it was put in order is put back where it
// belongs, as many times in all as there are files in order: past
// that the first is closed, though it was read meanwhile.
let mut put_back = order.len();
while files.open.load(Ordering::Relaxed) > files.max {
let Some((at, slot)) = order.pop_first() else {
break;
};
// A table dropped closed its own.
let Some(s) = slot.upgrade() else { continue };
let last = s.last.load(Ordering::Relaxed);
if last != at && put_back > 0 {
put_back -= 1;
order.insert(last, slot);
continue;
}
if let Some(f) = lock(&s.file).take() {
files.open.fetch_sub(1, Ordering::Relaxed);
closed.push(f);
}
}
// What tables dropped left behind, before it outgrows the rest.
if order.len() > 2 * files.max + 64 {
order.retain(|_, slot| slot.strong_count() > 0);
}
drop(order);
drop(closed);
file
}
}
impl Drop for Slot {
fn drop(&mut self) {
let file = self.file.get_mut().unwrap_or_else(PoisonError::into_inner);
if file.take().is_some() {
self.files.open.fetch_sub(1, Ordering::Relaxed);
}
}
}
// ---- The block cache ------------------------------------------------------------
/// What the block cache holds an item by: a table's block, by the table and
/// its offset; or any other item read from a file, by a number its reader
/// gives the file, an offset and a name.
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
pub enum Key {
Block(u64, u64),
Item(u64, u64, Box<[u8]>),
}
/// A number no file has been given, for `Key::Item`.
pub fn file_number() -> u64 {
static N: AtomicU64 = AtomicU64::new(1 << 62);
N.fetch_add(1, Ordering::Relaxed)
}
/// The parts a cache's items are divided among, each behind a lock of its
/// own: a power of two.
const PARTS: usize = 64;
/// The bytes an item is counted as beyond its own: its key twice, its
/// place in the part's two maps, and its allocation's header.
const HELD: u64 = 192;
fn held(value: &[u8]) -> u64 {
value.len() as u64 + HELD
}
/// Blocks, and items, read from files, held up to a number of bytes in
/// all, and the files of the tables opened with it, held open up to a
/// count. An item is in one of `PARTS` parts, by its file and offset, each
/// with a lock of its own, so that readers of different items seldom wait
/// for one another; the bytes are counted across all of them, and never
/// pass the budget. Room is made by letting go of the least recently used
/// of the part the new item goes in, then of the other parts in turn. It
/// counts the bytes of the tables' blocks read from their files through it
/// (`read_bytes`).
pub struct BlockCache {
budget: u64,
/// The bytes held, and those of items about to be.
bytes: AtomicU64,
/// The bytes of tables' blocks read from their files, since it was made.
read: AtomicU64,
parts: Box<[Part]>,
files: Arc<Files>,
}
/// One part's items, apart from its neighbours' in memory, so that a lock
/// taken on one does not slow the next.
#[derive(Default)]
#[repr(align(128))]
struct Part(Mutex<Lru>);
#[derive(Default)]
struct Lru {
items: BTreeMap<Key, Item>,
/// The items' keys, each by the tick it was put at or, later, found
/// used at: the first is the least recently used, once one used since
/// is put back where it belongs.
order: BTreeMap<u64, Key>,
tick: u64,
}
struct Item {
value: Arc<[u8]>,
/// The tick of its last use, and the one `order` has it by.
used: u64,
at: u64,
}
impl Lru {
fn get(&mut self, key: &Key) -> Option<Arc<[u8]>> {
self.tick += 1;
let item = self.items.get_mut(key)?;
item.used = self.tick;
Some(item.value.clone())
}
/// Hold `value` by `key`: answers the bytes of what it held by it before.
fn put(&mut self, key: Key, value: Arc<[u8]>) -> Option<u64> {
self.tick += 1;
let (used, at) = (self.tick, self.tick);
self.order.insert(at, key.clone());
let old = self.items.insert(key, Item { value, used, at })?;
self.order.remove(&old.at);
Some(held(&old.value))
}
/// Let go of the least recently used item: answers its bytes, or None
/// if it holds nothing.
fn evict(&mut self) -> Option<u64> {
loop {
let (at, key) = self.order.pop_first()?;
let Some(item) = self.items.get_mut(&key) else {
continue;
};
if item.used != at {
item.at = item.used;
self.order.insert(item.used, key);
continue;
}
return self.items.remove(&key).map(|item| held(&item.value));
}
}
/// Let go of every item of `file`: answers their bytes.
fn forget(&mut self, file: u64) -> u64 {
let item = |file| Key::Item(file, 0, Box::default());
let blocks = (
Bound::Included(Key::Block(file, 0)),
Bound::Included(Key::Block(file, u64::MAX)),
);
let items = (
Bound::Included(item(file)),
file.checked_add(1)
.map_or(Bound::Unbounded, |next| Bound::Excluded(item(next))),
);
let gone: Vec<Key> = self
.items
.range(blocks)
.chain(self.items.range(items))
.map(|(k, _)| k.clone())
.collect();
let mut freed = 0;
for k in gone {
if let Some(item) = self.items.remove(&k) {
self.order.remove(&item.at);
freed += held(&item.value);
}
}
freed
}
}
impl BlockCache {
/// A cache of at most `budget` bytes for a table or a few: at most
/// `FEW` tables' files open.
pub fn new(budget: u64) -> BlockCache {
BlockCache::with_open(budget, FEW)
}
/// A cache of at most `budget` bytes, and `open` tables' files open
/// (one at least): for every account's table, a share of the process's
/// file descriptors (`files::share`).
pub fn with_open(budget: u64, open: usize) -> BlockCache {
BlockCache {
budget,
bytes: AtomicU64::new(0),
read: AtomicU64::new(0),
parts: (0..PARTS).map(|_| Part::default()).collect(),
files: Arc::new(Files {
max: open.max(1),
open: AtomicUsize::new(0),
tick: AtomicU64::new(1),
order: Mutex::default(),
}),
}
}
/// The bytes it holds, counting those of items being put.
pub fn bytes(&self) -> u64 {
self.bytes.load(Ordering::Relaxed)
}
/// The bytes of tables' blocks read from their files through it since
/// it was made, checks and all: what reading by key and in order cost,
/// apart from what opening the tables read of their ends.
pub fn read_bytes(&self) -> u64 {
self.read.load(Ordering::Relaxed)
}
/// How many tables' files it holds open.
pub fn open_files(&self) -> usize {
self.files.open.load(Ordering::Relaxed)
}
/// The part `key`'s item is in.
fn part(&self, key: &Key) -> usize {
let (Key::Block(file, offset) | Key::Item(file, offset, _)) = key;
let h =
(file.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ offset).wrapping_mul(0xd6e8_feb8_6659_fd93);
(h >> (64 - PARTS.trailing_zeros())) as usize
}
pub fn get(&self, key: &Key) -> Option<Arc<[u8]>> {
lock(&self.parts[self.part(key)].0).get(key)
}
/// Hold `value`, unless it is more than an eighth of the budget, having
/// let go of the least recently used until it fits.
pub fn put(&self, key: Key, value: Arc<[u8]>) {
let size = held(&value);
if size > self.budget / 8 {
return;
}
let mine = self.part(&key);
// Room is taken from its own part, then from the others in turn.
for i in 0..PARTS {
let mut part = lock(&self.parts[(mine + i) % PARTS].0);
loop {
let bytes = self.bytes.load(Ordering::Relaxed);
if bytes + size > self.budget {
match part.evict() {
Some(freed) => self.bytes.fetch_sub(freed, Ordering::Relaxed),
None => break,
};
continue;
}
// Counted before it is held, so that the count never
// passes the budget.
let counted = self.bytes.compare_exchange_weak(
bytes,
bytes + size,
Ordering::Relaxed,
Ordering::Relaxed,
);
if counted.is_err() {
continue;
}
if i > 0 {
drop(part);
part = lock(&self.parts[mine].0);
}
if let Some(old) = part.put(key, value) {
self.bytes.fetch_sub(old, Ordering::Relaxed);
}
return;
}
}
// Nothing left to let go of: the rest is other items being put.
}
/// Let go of every item of the file numbered `file`, or of the table `file`.
pub fn forget(&self, file: u64) {
for part in &self.parts {
let freed = lock(&part.0).forget(file);
self.bytes.fetch_sub(freed, Ordering::Relaxed);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn scratch(name: &str) -> PathBuf {
let d = std::env::temp_dir().join(format!("pds-store-table-{}-{name}", std::process::id()));
let _ = std::fs::remove_dir_all(&d);
std::fs::create_dir_all(&d).unwrap();
d
}
fn entries(n: usize) -> Vec<(Vec<u8>, Vec<u8>)> {
(0..n)
.map(|i| {
(
format!("k{i:06}").into_bytes(),
vec![(i % 251) as u8; if i % 97 == 0 { 40_000 } else { i % 300 }],
)
})
.collect()
}
fn fill<W: Write>(mut w: TableWriter<W>, es: &[(Vec<u8>, Vec<u8>)]) -> (W, u64) {
for (k, v) in es {
w.add(k, v).unwrap();
}
w.finish().unwrap()
}
fn write_blocks(path: &Path, es: &[(Vec<u8>, Vec<u8>)], block: usize) -> u64 {
let out = io::BufWriter::new(File::create(path).unwrap());
fill(TableWriter::with_block(out, es.len() as u64, block), es).1
}
fn write(path: &Path, es: &[(Vec<u8>, Vec<u8>)]) -> u64 {
write_blocks(path, es, BLOCK)
}
/// A table of `version`, whole: its blocks ended past `block` bytes.
fn written(es: &[(Vec<u8>, Vec<u8>)], block: usize, version: Version) -> Vec<u8> {
let w = TableWriter::of_version(Vec::new(), es.len() as u64, block, version);
fill(w, es).0
}
/// Every key of `es` found in `t`, none other, in order either way from
/// any point.
fn reads_as(t: &Table, es: &[(Vec<u8>, Vec<u8>)], cache: &BlockCache) {
let n = es.len();
assert_eq!(t.len(), n as u64);
for (k, v) in es {
assert_eq!(t.get(k, cache).unwrap().as_ref(), Some(v));
}
assert_eq!(t.get(b"k9", cache).unwrap(), None);
assert_eq!(t.get(b"a", cache).unwrap(), None);
let all: Vec<_> = t.iter(b"", None, cache).map(Result::unwrap).collect();
assert_eq!(all, es);
if n > 0 {
let mid = &es[n / 2].0;
let after: Vec<_> = t.iter(mid, None, cache).map(Result::unwrap).collect();
assert_eq!(after, es[n / 2..]);
let before: Vec<_> = t.iter_back(mid, None, cache).map(Result::unwrap).collect();
let mut want = es[..n / 2].to_vec();
want.reverse();
assert_eq!(before, want);
let every: Vec<_> = t.iter_back(b"z", None, cache).map(Result::unwrap).collect();
want = es.to_vec();
want.reverse();
assert_eq!(every, want);
// Between two keys, and past the last.
let mut between = es[n / 2].0.clone();
between.push(0);
assert_eq!(t.get(&between, cache).unwrap(), None);
let after: Vec<_> = t.iter(&between, None, cache).map(Result::unwrap).collect();
assert_eq!(after, es[n / 2 + 1..]);
let before: Vec<_> = t
.iter_back(&between, None, cache)
.map(Result::unwrap)
.collect();
assert_eq!(before.len(), n / 2 + 1);
}
}
/// Written and read back: every key found, none other, in order either
/// way from any point, with a cache too small to hold much. What is
/// written is of the version written now.
#[test]
fn round_trips() {
let dir = scratch("round");
let cache = BlockCache::new(64 << 10);
for n in [0usize, 1, 7, 2000] {
let es = entries(n);
let path = dir.join(format!("t{n}"));
let size = write(&path, &es);
let file = std::fs::read(&path).unwrap();
assert_eq!(file.len() as u64, size);
assert_eq!(Version::of(&file), Some(Version::Xxh3));
let t = Table::open(&path, &cache).unwrap();
assert_eq!(t.version(), Version::Xxh3);
reads_as(&t, &es, &cache);
}
let _ = std::fs::remove_dir_all(&dir);
}
/// A table of the version before, built byte for byte as its writers
/// wrote it, its SHA-256 computed here: blocks ended past `size` bytes,
/// and in the index each block's last key `whole`, as with blocks of
/// 16 KiB, or shortened, as with blocks of 4 KiB.
fn written_before(es: &[(Vec<u8>, Vec<u8>)], size: usize, whole: bool) -> Vec<u8> {
let check = |bytes: &[u8]| Sha256::digest(bytes)[..8].to_vec();
// Each block's entries, and which of `es` are its first and its last.
let mut blocks: Vec<(usize, usize, Vec<u8>)> = Vec::new();
let (mut block, mut first) = (Vec::new(), 0);
for (i, (k, v)) in es.iter().enumerate() {
if !block.is_empty() && block.len() + k.len() + v.len() > size {
blocks.push((first, i - 1, std::mem::take(&mut block)));
first = i;
}
varint(&mut block, k.len() as u64);
block.extend_from_slice(k);
varint(&mut block, v.len() as u64);
block.extend_from_slice(v);
if block.len() >= size {
blocks.push((first, i, std::mem::take(&mut block)));
first = i + 1;
}
}
if !block.is_empty() {
blocks.push((first, es.len() - 1, block));
}
let (mut out, mut index) = (Vec::new(), Vec::new());
for (n, (_, last, entries)) in blocks.iter().enumerate() {
let mut key = es[*last].0.clone();
if let (false, Some((next, _, _))) = (whole, blocks.get(n + 1)) {
shorten(&mut key, &es[*next].0);
}
varint(&mut index, key.len() as u64);
index.extend_from_slice(&key);
varint(&mut index, out.len() as u64);
varint(&mut index, (entries.len() + 8) as u64);
out.extend_from_slice(entries);
out.extend_from_slice(&check(entries));
}
let c = check(&index);
index.extend_from_slice(&c);
// The filter: 10 bits an entry, 64 at least, and 7 of them a key's.
let mut filter = vec![0u8; 1 + (es.len().max(1) * 10).div_ceil(8).max(8)];
filter[0] = 7;
let m = (filter.len() as u64 - 1) * 8;
for (k, _) in es {
let d = Sha256::digest(k);
let a = u64::from_le_bytes(d[..8].try_into().unwrap());
let b = u64::from_le_bytes(d[8..16].try_into().unwrap()) | 1;
for i in 0..7 {
let p = (a.wrapping_add(b.wrapping_mul(i)) % m) as usize;
filter[1 + p / 8] |= 1 << (p % 8);
}
}
let c = check(&filter);
filter.extend_from_slice(&c);
let lens = [out.len(), index.len(), filter.len(), es.len()];
out.extend_from_slice(&index);
out.extend_from_slice(&filter);
out.extend_from_slice(b"PDSTAB01");
for n in lens {
out.extend_from_slice(&(n as u64).to_le_bytes());
}
out
}
/// Tables of other block sizes read the same: those written before
/// with blocks of 16 KiB, and blocks so small that each holds an entry
/// or two, whose index keys are nearly all shortened.
#[test]
fn blocks_of_any_size_are_read() {
let dir = scratch("sizes");
let cache = BlockCache::new(64 << 10);
let es = entries(2000);
let path = dir.join("before");
std::fs::write(&path, written_before(&es, 16 << 10, true)).unwrap();
let before = Table::open(&path, &cache).unwrap();
reads_as(&before, &es, &cache);
let mut blocks = vec![before.blocks()];
for size in [16 << 10, BLOCK, 512, 1] {
let path = dir.join(format!("t{size}"));
write_blocks(&path, &es, size);
let t = Table::open(&path, &cache).unwrap();
reads_as(&t, &es, &cache);
blocks.push(t.blocks());
}
assert_eq!(blocks[0], blocks[1]);
assert!(blocks.windows(2).all(|w| w[0] <= w[1]), "{blocks:?}");
assert_eq!(blocks[4], es.len());
let _ = std::fs::remove_dir_all(&dir);
}
/// A table of the version before reads as it did, in each layout it
/// was written in: every key found, none other, in order either way.
/// The writer writes that version as it was, byte for byte, and the
/// version it writes now has the same entries in the same blocks under
/// the same index, each with the other check, and its footer's check.
#[test]
fn the_version_before_reads_as_it_did() {
let dir = scratch("before");
let cache = BlockCache::new(64 << 10);
let (path, other) = (dir.join("before"), dir.join("now"));
for n in [0usize, 1, 7, 2000] {
let es = entries(n);
for (size, whole) in [(16 << 10, true), (BLOCK, false)] {
let before = written_before(&es, size, whole);
assert!(is_table(&before));
std::fs::write(&path, &before).unwrap();
let t = Table::open(&path, &cache).unwrap();
assert_eq!(t.version(), Version::Sha256);
reads_as(&t, &es, &cache);
}
let before = std::fs::read(&path).unwrap();
assert!(before == written(&es, BLOCK, Version::Sha256), "{n}");
let now = written(&es, BLOCK, Version::Xxh3);
assert_eq!(now.len(), before.len() + CHECK);
std::fs::write(&other, &now).unwrap();
let (t, u) = (
Table::open(&path, &cache).unwrap(),
Table::open(&other, &cache).unwrap(),
);
assert_eq!(
(&t.keys, &t.ends, &t.shared, &t.starts),
(&u.keys, &u.ends, &u.shared, &u.starts)
);
for block in t.starts.windows(2) {
let entries = block[0] as usize..block[1] as usize - CHECK;
assert!(before[entries.clone()] == now[entries], "{n}");
}
}
let _ = std::fs::remove_dir_all(&dir);
}
/// The file a writer of each version writes of the same entries is the
/// one such a writer wrote, by its SHA-256: the version before's as
/// the writer that wrote no other wrote it.
#[test]
fn each_version_is_written_as_it_was() {
let es = entries(300);
for (version, want) in [
(
Version::Sha256,
"e85996de4ca91ff13a083546092b1c718ff0f804627ff4b70110cfd7bbe1a520",
),
(
Version::Xxh3,
"f26e29b401b7424ade316ca9d7e7699fc0ae70648b3fcf088e4c65ba4754dfc5",
),
] {
let digest: String = Sha256::digest(written(&es, BLOCK, version))
.iter()
.map(|b| format!("{b:02x}"))
.collect();
assert_eq!(digest, want, "{version:?}");
}
}
/// XXH3 is the one published, by its hashes of nothing and of `abc`
/// (`xxhsum -H3`, and `-H2` for the 128 bits): a check is the 64 bits,
/// and a key's two hashes the 128 bits' low half, then their high.
#[test]
fn xxh3_is_the_one_published() {
let v = Version::Xxh3;
assert_eq!(v.check(b""), 0x2d06_8005_38d3_94c2_u64.to_le_bytes());
assert_eq!(v.check(b"abc"), 0x78af_5f94_892f_3950_u64.to_le_bytes());
assert_eq!(
v.hashes(b""),
(0x6001_c324_468d_497f, 0x99aa_06d3_0147_98d9)
);
assert_eq!(
v.hashes(b"abc"),
(0x78af_5f94_892f_3950, 0x06b0_5ab6_733a_6185)
);
}
/// A file whose footer's magic names no version, or the other's, is
/// refused, and the error says so.
#[test]
fn a_version_not_known_is_refused() {
let dir = scratch("version");
let cache = BlockCache::new(64 << 10);
let es = entries(50);
let path = dir.join("t");
for (version, other) in [
(Version::Xxh3, Version::Sha256),
(Version::Sha256, Version::Xxh3),
] {
let good = written(&es, BLOCK, version);
assert_eq!(Version::of(&good), Some(version));
let at = good.len() - version.footer();
for magic in [b"PDSTAB03", b"PDSTAB00", b"pdstab02", other.magic()] {
let mut b = good.clone();
b[at..at + 8].copy_from_slice(magic);
assert_eq!(Version::of(&b), None);
assert!(!is_table(&b));
std::fs::write(&path, &b).unwrap();
let e = Table::open(&path, &cache).err().unwrap().to_string();
assert!(e.ends_with("not a table of a known version"), "{e}");
}
}
let _ = std::fs::remove_dir_all(&dir);
}
/// A table of the version before whose footer gives more entries than
/// its blocks' bytes could hold, two bytes each, is refused, whatever
/// the number: its footer has no check to find another by, and one its
/// blocks could hold opens, with the entries it has. Of the version
/// written, any other number fails the footer's check.
#[test]
fn more_entries_than_could_be_are_refused() {
let dir = scratch("count");
let cache = BlockCache::new(64 << 10);
let es = entries(50);
let path = dir.join("t");
let open = |file: &[u8]| {
std::fs::write(&path, file).unwrap();
Table::open(&path, &cache).map_err(|e| e.to_string())
};
// `file` with the number at `at`, which ends there, made `n`.
let with = |file: &[u8], at: usize, n: u64| {
let mut b = file.to_vec();
b[at - 8..at].copy_from_slice(&n.to_le_bytes());
b
};
let before = written_before(&es, BLOCK, false);
let end = before.len();
let blocks = u64::from_le_bytes(before[end - 32..end - 24].try_into().unwrap());
for n in [blocks / 2 + 1, 1 << 40, u64::MAX] {
let e = open(&with(&before, end, n)).err().unwrap();
assert!(
e.ends_with("more entries than its blocks could hold"),
"{e}"
);
}
let t = open(&with(&before, end, blocks / 2)).unwrap();
assert_eq!(t.len(), blocks / 2);
assert!(gives(t.iter(b"", None, &cache), &es));
let now = written(&es, BLOCK, Version::Xxh3);
for n in [0, 51, blocks / 2 + 1, u64::MAX] {
let e = open(&with(&now, now.len() - CHECK, n)).err().unwrap();
assert!(e.ends_with("its footer fails its check"), "{e}");
}
let _ = std::fs::remove_dir_all(&dir);
}
/// An index key shortened is no longer than the block's last key, at
/// or after it, and before the next block's first.
#[test]
fn index_keys_are_between_their_blocks() {
let pairs: [(&[u8], &[u8]); 9] = [
(b"a", b"b"),
(b"abc", b"abd"),
(b"abc", b"abcd"),
(b"abc", b"b"),
(b"abcdef", b"abx"),
(b"ab\xff\xff", b"ac"),
(b"ab\xff\x01zz", b"ac"),
(b"a\x00", b"a\x00\x00"),
(b"", b"\x00"),
];
for (last, next) in pairs {
let mut key = last.to_vec();
shorten(&mut key, next);
assert!(
key.len() <= last.len() && last <= key.as_slice() && key.as_slice() < next,
"{last:?} {key:?} {next:?}"
);
}
let mut key = b"abcdef".to_vec();
shorten(&mut key, b"abx");
assert_eq!(key, b"abd");
let mut key = b"ab\xff\x01zz".to_vec();
shorten(&mut key, b"ac");
assert_eq!(key, b"ab\xff\x02");
}
/// A byte changed anywhere is found, in a table of either version: the
/// file is refused, or the block read fails its check; nothing wrong is
/// answered. Unchanged, it reads whole.
#[test]
fn corruption_is_refused() {
let dir = scratch("corrupt");
let es = entries(300);
let bad_path = dir.join("bad");
for version in [Version::Xxh3, Version::Sha256] {
let good = written(&es, BLOCK, version);
std::fs::write(&bad_path, &good).unwrap();
let cache = BlockCache::new(1 << 20);
reads_as(&Table::open(&bad_path, &cache).unwrap(), &es, &cache);
let mut failed = 0;
for i in (0..good.len()).step_by(997) {
let mut b = good.clone();
b[i] ^= 0x41;
std::fs::write(&bad_path, &b).unwrap();
let cache = BlockCache::new(1 << 20);
let Ok(t) = Table::open(&bad_path, &cache) else {
failed += 1;
continue;
};
for (k, v) in &es {
match t.get(k, &cache) {
Ok(Some(got)) => assert_eq!(&got, v, "byte {i}"),
Ok(None) => panic!("byte {i}: a key not found"),
Err(_) => failed += 1,
}
}
for r in t.iter(b"", None, &cache) {
match r {
Ok((k, v)) => assert!(es.contains(&(k, v)), "byte {i}"),
Err(_) => failed += 1,
}
}
}
assert!(failed > 0);
let mut short = good.clone();
short.truncate(good.len() - 1);
std::fs::write(&bad_path, &short).unwrap();
assert!(Table::open(&bad_path, &BlockCache::new(1 << 20)).is_err());
}
let _ = std::fs::remove_dir_all(&dir);
}
/// What `iter` gives is `want` from its first on, to its last or to an
/// error: whether to its last.
fn gives(iter: Iter<'_>, want: &[(Vec<u8>, Vec<u8>)]) -> bool {
let mut n = 0;
for r in iter {
let Ok(e) = r else { return false };
assert!(want.get(n) == Some(&e), "entry {n}");
n += 1;
}
assert_eq!(n, want.len());
true
}
/// Every byte of a small table changed in turn, three ways, and the
/// table cut short at every byte, in either version. Cut short, it
/// does not open. With a byte changed it does not open, or every read
/// of the block changed is an error: a key answers its own value or an
/// error, never another value or none, and what is read in order
/// either way is the entries up to an error. In the version written
/// that is every byte of the file. In the version before, the footer's
/// number of entries is under no check: with a byte of it changed the
/// table does not open, or reads whole, every entry as it was.
#[test]
fn every_byte_changed_is_found() {
let dir = scratch("every");
let path = dir.join("t");
let es: Vec<(Vec<u8>, Vec<u8>)> = (0..40usize)
.map(|i| (format!("key{i:02}").into_bytes(), vec![i as u8; i * 7 % 23]))
.collect();
let back: Vec<_> = es.iter().rev().cloned().collect();
// Nothing is kept of the blocks, so that every read is of the file.
let cache = BlockCache::new(0);
for version in [Version::Xxh3, Version::Sha256] {
let good = written(&es, 64, version);
// The bytes under no check: the version before's number of entries.
let unchecked = match version {
Version::Xxh3 => good.len()..good.len(),
Version::Sha256 => good.len() - 8..good.len(),
};
std::fs::write(&path, &good).unwrap();
let t = Table::open(&path, &cache).unwrap();
assert!(t.blocks() > 8);
reads_as(&t, &es, &cache);
for (i, mask) in (0..good.len()).flat_map(|i| [0x01, 0x80, 0xff].map(|m| (i, m))) {
let mut b = good.clone();
b[i] ^= mask;
std::fs::write(&path, &b).unwrap();
let Ok(t) = Table::open(&path, &cache) else {
continue;
};
let mut failed = 0;
for (k, v) in &es {
match t.get(k, &cache) {
Ok(Some(got)) => assert_eq!(&got, v, "byte {i}"),
Ok(None) => panic!("byte {i}: a key not found"),
Err(_) => failed += 1,
}
}
let whole = [
gives(t.iter(b"", None, &cache), &es),
gives(t.iter_back(b"z", None, &cache), &back),
];
let unchecked = unchecked.contains(&i);
assert_eq!(
(failed == 0, whole),
(unchecked, [unchecked; 2]),
"byte {i}"
);
}
for len in 0..good.len() {
std::fs::write(&path, &good[..len]).unwrap();
assert!(Table::open(&path, &cache).is_err(), "cut at {len}");
}
}
let _ = std::fs::remove_dir_all(&dir);
}
/// Keys out of order are refused as they are given.
#[test]
fn keys_in_order() {
let mut w = TableWriter::new(Vec::new(), 2);
w.add(b"b", b"1").unwrap();
assert!(w.add(b"a", b"2").is_err());
assert!(w.add(b"b", b"2").is_err());
}
/// More tables are read than files may be open: no more are open than
/// that at any time, a file closed is closed, each table reads whole
/// with its file opened again, and a table dropped closes its own.
#[test]
fn open_files_are_bounded() {
let dir = scratch("open");
// Nothing is kept of the blocks, so that every read is of a file.
let cache = BlockCache::with_open(0, 4);
let es = entries(40);
let mut tables = Vec::new();
let mut files = Vec::new();
for i in 0..20 {
let path = dir.join(format!("t{i}"));
write(&path, &es);
let t = Table::open(&path, &cache).unwrap();
files.push(Arc::downgrade(&t.file().unwrap()));
tables.push(t);
assert!(cache.open_files() <= 4);
}
assert_eq!(cache.open_files(), 4);
let open = |files: &[Weak<File>]| files.iter().filter(|f| f.strong_count() > 0).count();
assert_eq!(open(&files), 4);
for round in 0..3 {
for (i, t) in tables.iter().enumerate() {
let (k, v) = &es[(i + round * 7) % es.len()];
assert_eq!(t.get(k, &cache).unwrap().as_ref(), Some(v));
assert!(cache.open_files() <= 4);
}
}
// The least recently read are the ones closed: the last four read stay.
let last: Vec<Weak<File>> = tables[16..]
.iter()
.map(|t| Arc::downgrade(&t.file().unwrap()))
.collect();
tables[16].get(&es[0].0, &cache).unwrap();
assert_eq!(open(&last), 4);
// From many threads at once.
std::thread::scope(|s| {
for thread in 0..8 {
let (tables, es, cache) = (&tables, &es, &cache);
s.spawn(move || {
for n in 0..400 {
let t = &tables[(n * 7 + thread * 3) % tables.len()];
let (k, v) = &es[n % es.len()];
assert_eq!(t.get(k, cache).unwrap().as_ref(), Some(v));
}
});
}
});
assert_eq!(cache.open_files(), 4);
for t in &tables {
reads_as(t, &es, &cache);
}
assert_eq!(open(&files), 0);
// Dropped, each closes its own, and the cache keeps nothing of them.
let now: Vec<Weak<File>> = tables
.iter()
.filter_map(|t| {
lock(&t.slot.as_ref().unwrap().file)
.as_ref()
.map(Arc::downgrade)
})
.collect();
assert_eq!(now.len(), 4);
tables.truncate(2);
assert!(cache.open_files() <= 2);
tables.clear();
assert_eq!(cache.open_files(), 0);
assert_eq!(open(&now), 0);
// Tables opened and dropped leave nothing that grows.
for _ in 0..1000 {
Table::open(&dir.join("t0"), &cache).unwrap();
}
assert_eq!(cache.open_files(), 0);
assert!(lock(&cache.files.order).len() <= 2 * 4 + 64 + 1);
let _ = std::fs::remove_dir_all(&dir);
}
/// A table replaced by another at its path, then removed, while it is
/// open: whoever holds its file reads it whole as it was; the table
/// opened after reads the new one; and the old one, its file closed,
/// refuses to read the file now at its path.
#[test]
fn a_table_replaced_while_open() {
let dir = scratch("replaced");
let cache = BlockCache::with_open(0, 1);
let old = entries(300);
// The same keys, in blocks at the same places, with other values.
let new: Vec<(Vec<u8>, Vec<u8>)> = old
.iter()
.map(|(k, v)| (k.clone(), v.iter().map(|b| b ^ 0xff).collect()))
.collect();
let path = dir.join("t");
write(&path, &old);
let t1 = Table::open(&path, &cache).unwrap();
assert_eq!(t1.get(&old[5].0, &cache).unwrap().as_ref(), Some(&old[5].1));
let held = t1.file().unwrap();
let tmp = dir.join("t.tmp");
write(&tmp, &new);
std::fs::rename(&tmp, &path).unwrap();
// Still open, the old table reads its own file.
reads_as(&t1, &old, &cache);
let t2 = Table::open(&path, &cache).unwrap();
reads_as(&t2, &new, &cache);
// Its file closed to make room, the old table does not read the new one's.
assert_eq!(cache.open_files(), 1);
for (k, _) in &old {
let e = t1.get(k, &cache).unwrap_err();
assert_eq!(e.kind(), io::ErrorKind::NotFound, "{e}");
}
assert!(t1.iter(b"", None, &cache).next().unwrap().is_err());
assert!(t1.file().is_err());
// Through the file held, it reads as it was.
for (k, v) in &old {
assert_eq!(
t1.get_in(k, Some(&*held), &cache).unwrap().as_ref(),
Some(v)
);
}
let all: Vec<_> = t1
.iter(b"", Some(&*held), &cache)
.map(Result::unwrap)
.collect();
assert_eq!(all, old);
// Removed, the new one reads while its file is open, and not after.
std::fs::remove_file(&path).unwrap();
reads_as(&t2, &new, &cache);
let held2 = t2.file().unwrap();
let other = dir.join("other");
write(&other, &old);
let t3 = Table::open(&other, &cache).unwrap();
assert_eq!(
t2.get(&new[0].0, &cache).unwrap_err().kind(),
io::ErrorKind::NotFound
);
assert_eq!(
t2.get_in(&new[0].0, Some(&*held2), &cache)
.unwrap()
.as_ref(),
Some(&new[0].1)
);
// Nothing is left open once they are dropped.
let files = [Arc::downgrade(&held), Arc::downgrade(&held2)];
drop((t1, t2, t3, held, held2));
assert_eq!(cache.open_files(), 0);
assert!(files.iter().all(|f| f.strong_count() == 0));
let _ = std::fs::remove_dir_all(&dir);
}
/// Keys of items that are all in the cache's part `part`.
fn keys_in(c: &BlockCache, part: usize) -> impl Iterator<Item = Key> + '_ {
(0u64..)
.map(|i| Key::Block(1, i))
.filter(move |k| c.part(k) == part)
}
/// The bytes of the items a cache holds, counted one by one.
fn counted(c: &BlockCache) -> u64 {
let parts: Vec<_> = c.parts.iter().map(|p| lock(&p.0)).collect();
parts
.iter()
.map(|l| {
assert_eq!(l.items.len(), l.order.len());
l.items.values().map(|i| held(&i.value)).sum::<u64>()
})
.sum()
}
/// The cache holds no more than its budget, the least recently used of
/// a part let go first, and room made in the other parts when its own
/// has none to give.
#[test]
fn the_cache_is_bounded() {
let c = BlockCache::new(10_000);
for i in 0..100u64 {
c.put(Key::Block(1, i), vec![0u8; 500].into());
assert!(c.bytes() <= 10_000);
assert!(c.get(&Key::Block(1, i)).is_some());
}
assert_eq!(c.bytes(), counted(&c));
assert!(c.bytes() > 10_000 - 2 * held(&[0; 500]));
// An item of more than an eighth is not held.
c.put(Key::Block(2, 0), vec![0u8; 1250].into());
assert!(c.get(&Key::Block(2, 0)).is_none());
c.forget(1);
assert_eq!((c.bytes(), counted(&c)), (0, 0));
// In one part: the least recently used go first.
let keys: Vec<Key> = keys_in(&c, 3).take(20).collect();
for k in &keys[..10] {
c.put(k.clone(), vec![0u8; 500].into());
}
assert!(c.get(&keys[0]).is_some());
for k in &keys[10..] {
c.put(k.clone(), vec![0u8; 500].into());
}
let kept: Vec<usize> = (0..20).filter(|i| c.get(&keys[*i]).is_some()).collect();
assert_eq!(kept[0], 0);
assert_eq!(kept[1..], (20 - (kept.len() - 1)..20).collect::<Vec<_>>());
// An item put again is held once.
c.put(keys[19].clone(), vec![1u8; 300].into());
assert_eq!(c.get(&keys[19]).unwrap().len(), 300);
assert_eq!(c.bytes(), counted(&c));
// An item whose own part holds nothing takes room from another.
let others = [40, 41].map(|part| keys_in(&c, part).next().unwrap());
for k in &others {
c.put(k.clone(), vec![0u8; 1000].into());
}
assert!(others.iter().all(|k| c.get(k).is_some()));
assert!(c.bytes() <= 10_000 && c.bytes() == counted(&c));
// Items of a file are forgotten together, blocks and others, and no others.
let c = BlockCache::new(1 << 20);
for file in [7u64, 8, 9] {
for i in 0..50u64 {
c.put(Key::Block(file, i * 4096), vec![0u8; 10].into());
c.put(
Key::Item(file, i, b"name".as_slice().into()),
vec![0u8; 10].into(),
);
}
}
c.forget(8);
for i in 0..50u64 {
for (file, there) in [(7u64, true), (8, false), (9, true)] {
let item = Key::Item(file, i, b"name".as_slice().into());
assert_eq!(c.get(&Key::Block(file, i * 4096)).is_some(), there);
assert_eq!(c.get(&item).is_some(), there);
}
}
assert_eq!(c.bytes(), 200 * held(&[0; 10]));
assert_eq!(c.bytes(), counted(&c));
}
/// Put to and read from many threads at once, the cache never counts
/// more than its budget, and what it counts is what it holds.
#[test]
fn the_budget_holds_under_many_threads() {
const BUDGET: u64 = 256 << 10;
let c = BlockCache::new(BUDGET);
let over = std::sync::atomic::AtomicBool::new(false);
std::thread::scope(|s| {
for thread in 0..16u64 {
let (c, over) = (&c, &over);
s.spawn(move || {
let mut x = thread + 1;
for n in 0..20_000u64 {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
// Some items as large as may be held, most small.
let len = match x % 16 {
0 => (BUDGET / 8 - HELD) as usize - (x % 64) as usize,
_ => (x % 5000) as usize,
};
let key = match x % 3 {
0 => Key::Item(x % 40, n % 64, b"an item".as_slice().into()),
_ => Key::Block(x % 40, (x >> 8) % 512),
};
if let Some(v) = c.get(&key) {
assert!(v.iter().all(|b| *b == v.len() as u8));
}
c.put(key, vec![len as u8; len].into());
if n % 1000 == 999 {
c.forget(x % 40);
}
if c.bytes() > BUDGET {
over.store(true, Ordering::Relaxed);
}
}
});
}
});
assert!(!over.load(Ordering::Relaxed));
assert_eq!(c.bytes(), counted(&c));
assert!(c.bytes() > BUDGET / 2, "{}", c.bytes());
}
}