//! 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::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(m: &Mutex) -> MutexGuard<'_, T> { m.lock().unwrap_or_else(PoisonError::into_inner) } fn varint(out: &mut Vec, 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 { 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, } 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 + 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, 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 { out: W, version: Version, at: u64, /// The bytes past which a block is ended. size: usize, block: Vec, last: Vec, /// The block written last, while the index has no entry for it: its /// last key, its offset and its length. ended: Option<(Vec, u64, u64)>, index: Vec, bloom: Bloom, count: u64, } impl TableWriter { /// A table written to `out`, its bloom filter sized for about `entries` entries. pub fn new(out: W, entries: u64) -> TableWriter { 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 { 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 { 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>, } 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 { 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
{ 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 { 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> { 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> { 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> { 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>> { 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>> { 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>, /// 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, /// The first key, or the key the entries are before. bound: Vec, back: bool, failed: bool, } impl Iter<'_> { fn fail(&mut self) -> Option, Vec)>> { self.failed = true; Some(Err(bad(&self.t.path, "a block that does not parse"))) } } impl Iterator for Iter<'_> { type Item = io::Result<(Vec, Vec)>; fn next(&mut self) -> Option { 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>>, } /// A table's file while it is open, among those of a cache. struct Slot { file: Mutex>>, /// The tick of its last read. last: AtomicU64, files: Arc, } impl Slot { /// Its file, if it is open, read now. fn held(&self) -> Option> { 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, file: Arc) -> Arc { 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, } /// 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); #[derive(Default)] struct Lru { items: BTreeMap, /// 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, 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> { 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 { 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 { 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 = 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> { 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, Vec)> { (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(mut w: TableWriter, es: &[(Vec, Vec)]) -> (W, u64) { for (k, v) in es { w.add(k, v).unwrap(); } w.finish().unwrap() } fn write_blocks(path: &Path, es: &[(Vec, Vec)], 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, Vec)]) -> u64 { write_blocks(path, es, BLOCK) } /// A table of `version`, whole: its blocks ended past `block` bytes. fn written(es: &[(Vec, Vec)], block: usize, version: Version) -> Vec { 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, Vec)], 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, Vec)], size: usize, whole: bool) -> Vec { 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)> = 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, Vec)]) -> 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, Vec)> = (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]| 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> = 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> = 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, Vec)> = 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 + '_ { (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::() }) .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 = 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 = (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::>()); // 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()); } }