~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
2045 lines · 74.6 KB Raw History
//! 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());
    }
}