~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
822 lines · 39.1 KB Raw History
//! What the server keeps on disk, generation by generation, so that the
//! disk it takes and the time it takes to start follow what it holds now,
//! not every write it was ever sent (`spec/STORE.md` says what must hold;
//! how is this server's own, and written here).
//!
//! **Files.** In `PDS_DATA_DIR`: the service log, `accounts.<g>.log`, and its
//! checkpoint `accounts.checkpoint`; for each account, in `repos/<did>/`,
//! its log `repo.<g>.log`, its checkpoint `repo.checkpoint`, and `blobs/`,
//! or with blobs in a bucket, none, and the mark `blobstore` (`blobstore`);
//! `lock`, which the process using the directory holds (`hold`);
//! the firehose's index, `events.<g>.log` and its checkpoint
//! `events.checkpoint`, which events were made and whose, kept as they are
//! made (`events::index`); and `clean-shutdown`, the mark a shutdown
//! leaves, taken away by the start after it (`ops`). While a checkpoint is
//! written, `<checkpoint>.tmp` is beside it.
//! Generations are decimal from 0. A log is frames (`pds_store`), each one
//! write's whole effect, and may end with a **seal**, `[{"t":"seal"}]`: the
//! log is closed, the next generation follows. The file of the log written
//! to may be longer than its frames, by **room**: zeros the next frames are
//! written over, so that their syncs find the file no longer than it was
//! (`pds_store`). A log's bytes, wherever they are counted, are its
//! frames': room is no part of them. A frame that grows its log's file
//! gives it as much room as the frames written to the file since it was
//! opened, itself among them: the first, as much again as itself. Never
//! more than `pds_store::AHEAD`, 256 KiB, nor past what the log may grow
//! to before it is compacted by size. Room is given back when the log is
//! sealed, when its file is closed to keep within the logs' share of the
//! process's file descriptors (`pds_store::files`), when its account's
//! store is let go (`cache`), when the server shuts down (`ops::settle`),
//! and when it is opened. A log's file is locked for as long as it is held
//! open to write to (`pds_store`): a second handle on it, in this process
//! or another, is an error that names the file, never a second writer.
//! What reads a log takes no lock, and a log loaded with no sync (below)
//! holds none until a frame is first appended to it.
//!
//! **The room a data directory holds** is that of the logs open to be
//! written to, and no other's: the service log's and the accounts' logs
//! open at once, a share `n` of the file descriptors at most. Each holds
//! no more than the bytes of the frames written to it since it was opened,
//! and no more than `AHEAD`: so all of them at most `(n + 1) * AHEAD`, 65
//! times 256 KiB or 16.25 MiB with a share of 64, 4097 times 256 KiB or
//! 256 KiB more than 1 GiB with the largest, 4096, and never more than was
//! written to those logs since they were opened. The log of an account
//! that is idle holds its frames alone once its store is let go, and after
//! a shutdown. After a kill it holds the room it had, if it was open then,
//! until its store is next loaded; the service log, until the next start.
//! What `spec/STORE.md` bounds of the directory's size holds with room as
//! without: a log's file reaches no further with room than its frames may
//! without, a log sealed, by size or by age, holds none, and the log after
//! it begins empty.
//!
//! **Checkpoints.** The checkpoint of generation `g` is the state as of the
//! start of log `g`: every log before folded. An account's is a sorted
//! table (`pds_store::table`, laid out in `checkpoint`): the blocks of its
//! current tree by CID, each with its count of paths and the rev that put
//! it there; each record's path with its CID and last rev; the events in
//! the window by seq; each space repo's records, their bytes, its
//! operations and its records' blob references, by the space's URI; a
//! header naming its generation and the last `seq`; and the rest of its
//! state in one entry (the latest commit, the last TID, the handle and a
//! change in flight, the blobs held with their takedowns, the records
//! taken down, each space repo's commit and LtHash, the spaces it is the
//! authority of and its write notifications). It is read as it is needed,
//! through a block cache all accounts share, never whole; what the log
//! after it changed is kept as where in the log it is
//! (`checkpoint::Memtable`). The service log's is a sorted table too, laid
//! out in `compact`: each account's row by DID, hints of which account has
//! each handle, email and password reset token, the accounts' DIDs in the
//! order they were made, the entries that are not one account's, and a
//! summary naming its generation and the last `seq`. It is read through
//! the same block cache, a row as its account is first used; what the log
//! after it holds of an account not yet loaded is kept as where in the log
//! it is (`directory`).
//!
//! **Compacting** a log of generation `g`, when after an append, or as the
//! compaction before ends, its logs pass `max(min(checkpoint,
//! ACCOUNT_CAP), log_floor)` bytes, the service log's `max(min(checkpoint,
//! SERVICE_CAP), log_floor)`, or its generation began more than twice the
//! backfill window ago (`policy`, `service_policy`); and an account's,
//! whatever its size, when what its store holds in memory of the log after
//! its table passes its share of the cache (`cache::Cache::memtable`). So
//! once no compaction runs, a log holds no more than that, though writes
//! came while the last one ran:
//!
//! 1. under the log's lock, log `g`'s room given back, its seal written,
//!    and log `g + 1` made, empty; nothing synced, nothing read, nothing
//!    folded there;
//! 2. outside it, log `g` and the directory synced: no frame of log `g + 1`
//!    is answered before;
//! 3. the checkpoint before and the sealed logs read from disk and folded
//!    (`AccountFold`, `ServiceFold`: each a streaming merge in order of
//!    key) into `<checkpoint>.tmp`, synced;
//! 4. renamed over `<checkpoint>`, under the account's lock if its store is
//!    held, or for the service log with the directory held, which read the
//!    new table from then on; the directory synced;
//! 5. the logs before `g + 1` deleted.
//!
//! Both logs are capped because a start, or an account's first use after
//! one, replays them: what a start reads of the service log does not grow
//! with the accounts, and its table is written whole once for each
//! `SERVICE_CAP` of log; what an account's first use reads of its log does
//! not grow with its table, as a day of events makes it, which is written
//! whole once for each `ACCOUNT_CAP` of log (`spec/STORE.md`, "The first
//! request to a cold account").
//!
//! **Starting**: `<checkpoint>.tmp` deleted, the checkpoint read (generation
//! `c`), logs before `c` deleted, the rest replayed in order and none
//! missing; a log but the last not ended by its seal, or one ending in part
//! of a frame, is cut there and the later ones deleted (none of that was
//! answered); room a kill left in a log is cut off it; then appends go to
//! the last log, or a new one after a seal.
//! So a kill at any point leaves a whole state: before the rename, the old
//! checkpoint and every sealed log; after, the new one, and the logs it
//! covers deleted then if not already. The service log starts so as the
//! server does, an account's as its store is loaded (`cache`), and what a
//! log holds is durable before anything is made of it (below). The
//! firehose learns the events made before a start from its index alone,
//! read after the start (`events::Firehose::find_old`); each event is sent
//! as its store, loaded, reads it. Only where a data directory has no
//! index yet, as the version before this left it, are the accounts' files
//! read for it, without that, once, as the start makes it
//! (`events::Firehose::adopt`, `checkpoint::events_on_disk`). A service
//! checkpoint of the
//! format before a table, a log whose first frame names its generation, is
//! folded alone into a table of the same generation before the service log
//! starts (`compact::convert`). An account's table of the version before,
//! which has no header, is folded with the log after it into a table of
//! this version, of the next generation, as its store is first loaded
//! (`checkpoint::load`).
//!
//! **Spaces are carried from the mark on** (`spec/STORE.md`,
//! "Upgrades"): an account's spaces state is this server's from the mark
//! its log begins with on, and what is found before it, in a log or a
//! table an earlier version wrote, is let go as its store is first loaded,
//! which appends the mark then; nothing else of the account changes but
//! the blobs only those spaces held (`checkpoint::unmarked`).
//!
//! **What a start syncs.** A log's frames are made durable as it starts,
//! before anything is made of them: a process killed may have left frames
//! the system had not written out, and what the server makes of a frame, an
//! answer, an event sent, an entry of another log, a frame after it, must
//! not outlive it. That sync is left out where every frame the log's files
//! hold is known to be on disk and the start finds nothing of them to mend
//! (`pds_store`, "An open that syncs nothing"), which is so in two cases:
//!
//! - **After a shutdown.** A shutdown closes every log, the service log and
//!   each account's, so that none takes another frame, gives back each
//!   one's room, and syncs every frame they took (`ops::settle`, which
//!   says why that is all of them). That is every frame of the logs this
//!   run opened. A log it never opened, of an account nothing asked for,
//!   holds what the run found there, which is durable if the run started
//!   with the word, or once the run has made what it found durable
//!   (below). Only where both are so does the shutdown leave its mark
//!   holding the word that the logs are durable (`ops::mark`); otherwise
//!   the mark is left without it. The word names the directory it was
//!   written in, and is the word there alone ("The word is its
//!   directory's", below). Whatever next opens that directory, a server
//!   or `pds migrate-blobs`, takes the word out of the mark, durably,
//!   before it writes anything (`ops::durable`, first in
//!   `Service::open`), and then opens each log with no sync: the service
//!   log as it starts, and each account's as its store is first loaded,
//!   whenever in the run that is, as nothing writes to an account's log
//!   but its store. So while the word is in the mark of the directory it
//!   names it is true of every log there, and a run that is killed,
//!   whatever it wrote first, leaves a mark without it, or none: the
//!   start after a kill syncs each log as it starts.
//! - **A store let go and loaded again**, in any run. A store is let go
//!   only with every frame its log was given on disk and no compaction of
//!   it running (`cache`), its log's room goes with it, and nothing writes
//!   to its log until it is loaded again. Its slot keeps that, a bit
//!   (`cache::Slot::durable`), and the next load syncs nothing.
//!
//! In both the log's file is its frames alone: its room was given back as
//! it was closed or let go. That cut is not synced, since no frame's being
//! on disk rests on it. A load that all the same finds zeros after a log's
//! frames takes them for room and cuts them off, again with no sync: the
//! log was open when a run before this shutdown's was killed and has not
//! been loaded since, or a power cut undid the cut. Part of a frame there
//! is a torn tail, which is mended. A log loaded with no sync is not
//! written to, and its file is neither opened nor locked, until a frame is
//! first appended: the file is then locked, and is an error if another
//! handle has changed it since; that first frame grows it, by the frame
//! and as much room again, under its own commit's sync.
//!
//! What a start mends is a write of its own, and is synced as ever, the
//! whole log with it: a torn tail cut, logs deleted, a log made, a
//! compaction cut short and finished. So is what the fold of a
//! table of the version before writes. A load of a store mends so
//! whenever in the run it comes, and so none begins once a shutdown has
//! closed the logs (`cache::Slot::load`): each mend there was is synced by
//! the time the mark is left, and a run in which a load failed, which may
//! have mended in part, leaves no word. A shutdown that does not finish
//! leaves no word: the mark is written only once every log is closed and
//! synced, so one that fails to sync a log, or is killed before the mark,
//! leaves the directory as a kill does, its open logs with their room.
//! A mark a version before left
//! holds no word, as that version left its logs open to writes after it
//! had synced them: each log is synced as it starts.
//!
//! **The word is its directory's.** The word is of bytes: those the files
//! of a directory held as its server shut down, which are on disk. A copy
//! of the directory is other bytes, which `cp -a`, `rsync` or an archive
//! unpacked leave in the system's memory for a while, and its mark, copied
//! with it, says the same. So the mark names, after the word, the
//! directory it was written in, by what a copy does not keep
//! (`ops::word`): the id of the file system the data directory is on, the
//! directory's inode, and when it last changed (its `ctime`); the same
//! three of `repos`; and the mark's own inode. And the mark's own time of
//! writing is set to when the data directory last changed, which is when
//! the mark was made. A start takes the word only where each of them is
//! what it finds, and the mark was written when it says
//! (`ops::durable`). Otherwise the mark holds no word, whatever else it
//! holds, a mark of the bare word too, which nothing wrote: the start is
//! as after a kill but that it says nothing of recovering, each log
//! synced as it is opened and what it found made durable in the
//! background (below). What the mark held is taken out of it either way.
//!
//! Why that is enough, case by case:
//!
//! - A copy within the file system has other inodes: the directory's own
//!   are in use while it is made.
//! - A copy to another file system finds another id, where the id is the
//!   file system's own, as on Linux ext4, btrfs and tmpfs make it of their
//!   UUID.
//! - An id is not always that. XFS gives its device's number, and so does
//!   macOS for every file system, as `fstatvfs` reads it: a file system
//!   made anew on the device has the same, and gives its first files the
//!   inodes the one before gave. And a restore into the directory itself,
//!   emptied or written over, keeps the directory's inode and may be given
//!   again the inodes it freed. There the change times decide. A `ctime`
//!   is the system's alone to set, to when the inode last changed: no
//!   copy sets one back. `repos` made anew has changed since the mark, or
//!   with an account's directory put in it or taken out; and so has the
//!   data directory with any file made in it, renamed into it or deleted
//!   from it, which is how `rsync` and an archive put a file in place. A
//!   shutdown makes its mark anew, so that the directory last changed as
//!   its own mark was made (`ops::mark`), and a start that has read the
//!   mark sets the directory's mode, which changes it again: the mark of
//!   a shutdown before, restored once the server has started since, names
//!   a time that is gone. A time is told to the grain the file system
//!   keeps, a tick of the system's clock at the coarsest: less than it
//!   takes to copy a mark away between its shutdown and the next start.
//! - A file system that gives no id, zeros, as NFS and FUSE do, never has
//!   the word. Inodes alone do not tell a copy there, as above, and a file
//!   system that keeps so little may not keep change times of its own
//!   either: each start on one syncs as after a kill.
//! - A `mv` of the directory within its file system moves no byte, and
//!   keeps the ids and the inodes; where the file system counts it a
//!   change of the directory moved, as most do, there is no word, and
//!   nothing is lost by that but one start's syncs. So with a `chown -R`
//!   or `chmod -R` of it, and with anything else that changes either
//!   directory between the shutdown and the start.
//! - A copy put back over the directory it was made of, file by file,
//!   with nothing made, renamed or deleted in either directory and no
//!   start since the shutdown, as a plain `cp -r` over files all there
//!   does: the mark is among the files written, and was then last written
//!   at another time than it says.
//! - A snapshot of the volume taken of a stopped server keeps all of them,
//!   and the word stands: it holds what the disk held, which was every
//!   frame. What puts such an image on another device is to have it there
//!   durably before the file system is used, as the file system itself
//!   needs. A snapshot a file system takes of itself keeps them or not, as
//!   that file system gives a snapshot an id of its own.
//!
//! What the mark does not tell is a file written over in place by what
//! leaves the mark, the data directory and `repos` as they were: one log
//! of one account copied over itself, or the whole directory by a tool
//! told to write in place and to set each file's time back. Nothing that
//! copies a directory away does that; whoever writes into a stopped
//! server's files so is to let them reach the disk (`sync`).
//!
//! **What a start found, made durable.** A run that starts without the
//! word, as after a kill, syncs each log it opens, and no other: the log
//! of an account that no request asks for in that run is opened by
//! nothing, and may hold frames the killed process left in the system's
//! memory. So such a run makes durable all that it found, at once and in
//! the background once it serves (`sync_found`, `ops::sync_found_soon`),
//! and only a run that has done so, or that started with the word or on a
//! directory with no data, leaves the word at its shutdown. The pass may
//! run at any time in the run: a log the run opens is synced by that open,
//! and settled by the shutdown; one it does not open is written to by
//! nothing, so that the pass syncs all the shutdown will find in it. The
//! firehose's index is read first, which its open syncs, and a shutdown
//! closes it last (`ops::sync_found`, `ops::settle`). On
//! Linux it is one `syncfs` of the data directory's file system, and of
//! `repos`' where that is another, which makes durable every file and
//! directory there. Elsewhere there is none, and each account's logs and
//! its table are opened to read and handed to the drive, its directory
//! after them, a few accounts at once, and then one sync that reaches the
//! disk is made, of `repos`: `fsync` returns once the drive has what it
//! was given, where it reaches the disk that is all, and where it does not
//! (macOS) the sync that does has the drive write out everything it was
//! handed before, whatever file it is asked of. Either way the accounts'
//! directories are taken to be on `repos`' file system and drive. The pass
//! loads no account, takes no log's lock, and holds a few files open and
//! nothing in memory but the name it is at. Until it has ended, and for
//! this run's own loads after, everything is as after a kill; if it fails,
//! or the server is shut down or killed before it ends, no word is left,
//! and the next start is as after a kill. A shutdown does not wait for it.
//!
//! **Seqs** are never given twice: each event keeps the seq it was written
//! with, and the next follows the greatest any log, checkpoint or the
//! firehose's index names, of events dropped too, and the greatest
//! reserved (`events::SEQS`). An event out of the window is dropped at its
//! log's next compaction (`in_window`), its entry in the index at the
//! index's.
//!
//! **The layout before generations**, a single `accounts.log` and
//! `repos/<did>/repo.log`, is moved to generation 0 on the first start
//! (`migrate`).

use crate::Config;
use crate::events::event_time;
use pds_store::{Fold, Layout, Policy};
use serde_json::Value as Json;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::io;
use std::path::{Path, PathBuf};

/// The bytes a log may grow to past its checkpoint's, whatever the checkpoint's size.
pub(crate) const FLOOR: u64 = 1 << 20;

/// The most an account's log grows to past its table before it is
/// compacted, whatever the table's size, but `log_floor` if that is more:
/// its first use after a start replays it. `Config::account_cap`'s
/// default, which tests set smaller.
pub(crate) const ACCOUNT_CAP: u64 = 4 << 20;

/// How much more than compacts it by size an account's log may hold while
/// a compaction of it runs, before its writers wait for that compaction
/// (`cache::Slot::write_lock`): so that, however fast the writes come
/// while a large table is written again, its first use after a start
/// replays no more than its cap (`Config::account_cap`) and this, and a
/// write.
pub(crate) const BEHIND: u64 = 2 << 20;

/// The most the service log grows to before it is compacted, whatever its
/// checkpoint's size, but `log_floor` if that is more: a start replays it.
pub(crate) const SERVICE_CAP: u64 = 8 << 20;

/// The service log's files, in the data directory.
pub(crate) fn service_layout(dir: &Path) -> Layout {
    Layout::new(dir, "accounts")
}

/// An account's log's files, in its own directory.
pub(crate) fn account_layout(dir: &Path, did: &str) -> Layout {
    Layout::new(dir.join("repos").join(did), "repo")
}

/// Whether a data directory holds data: a service log of any generation,
/// its checkpoint, or the single log of the layout before generations.
pub(crate) fn holds_data(dir: &Path) -> bool {
    let layout = service_layout(dir);
    layout.generations().is_ok_and(|g| !g.is_empty())
        || layout.checkpoint().exists()
        || dir.join(LEGACY_SERVICE).exists()
}

/// How many accounts' files the pass that makes durable what a start found
/// has open at once, where it syncs them file by file (`flush_found`).
#[cfg(not(target_os = "linux"))]
const WALKERS: usize = 4;

/// Make durable every log and table of every account in the data directory
/// `dir`, as they are now, whoever wrote them and whether or not anything
/// has loaded them since ("What a start found, made durable"): no account
/// is loaded and no log locked. One `syncfs` of the directory's file
/// system, and of `repos`' where that is another.
#[cfg(target_os = "linux")]
pub(crate) fn sync_found(dir: &Path) -> io::Result<()> {
    use std::os::unix::fs::MetadataExt;
    let top = std::fs::File::open(dir)?;
    pds_store::sync_filesystem(&top)?;
    let repos = match std::fs::File::open(dir.join("repos")) {
        Ok(repos) => repos,
        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(()),
        Err(e) => return Err(e),
    };
    if repos.metadata()?.dev() != top.metadata()?.dev() {
        pds_store::sync_filesystem(&repos)?;
    }
    Ok(())
}

/// Make durable every log and table of every account in the data directory
/// `dir`, as they are now, whoever wrote them and whether or not anything
/// has loaded them since ("What a start found, made durable"): no account
/// is loaded and no log locked. File by file, where no one sync makes a
/// file system durable.
#[cfg(not(target_os = "linux"))]
pub(crate) fn sync_found(dir: &Path) -> io::Result<()> {
    flush_found(dir, WALKERS)
}

/// The same, file by file, on `walkers` threads, this one among them: each
/// account's logs and table handed to the drive, its directory after them,
/// and then one sync of `repos` that reaches the disk, which makes durable
/// all that the drive was handed before it (`pds_store::flush_file`). The
/// accounts are read from `repos` as they are reached, never listed whole.
#[cfg(any(test, not(target_os = "linux")))]
pub(crate) fn flush_found(dir: &Path, walkers: usize) -> io::Result<()> {
    use std::sync::{Mutex, PoisonError};
    let repos = dir.join("repos");
    let accounts = match std::fs::read_dir(&repos) {
        Ok(accounts) => Mutex::new(accounts),
        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(()),
        Err(e) => return Err(e),
    };
    let failed: Mutex<Option<io::Error>> = Mutex::new(None);
    let work = || {
        loop {
            let next = accounts
                .lock()
                .unwrap_or_else(PoisonError::into_inner)
                .next();
            let Some(account) = next else { return };
            let flushed = account.and_then(|a| flush_account(&a.path()));
            let mut failed = failed.lock().unwrap_or_else(PoisonError::into_inner);
            if let Err(e) = flushed {
                failed.get_or_insert(e);
            }
            if failed.is_some() {
                return;
            }
        }
    };
    std::thread::scope(|s| {
        for i in 1..walkers {
            let spawned = std::thread::Builder::new()
                .name(format!("pds-sync-{i}"))
                .spawn_scoped(s, work);
            if spawned.is_err() {
                break;
            }
        }
        work();
    });
    match failed.into_inner().unwrap_or_else(PoisonError::into_inner) {
        Some(e) => Err(e),
        None => pds_store::sync_dir(&repos),
    }
}

/// Hand to the drive the logs and the table in an account's directory
/// `dir`, each opened to read, and then the directory. What is gone
/// meanwhile, a log its compaction deleted or an account deleted whole, and
/// what is no account's directory, needs none.
#[cfg(any(test, not(target_os = "linux")))]
fn flush_account(dir: &Path) -> io::Result<()> {
    let gone = |e: &io::Error| {
        matches!(
            e.kind(),
            io::ErrorKind::NotFound | io::ErrorKind::NotADirectory
        )
    };
    let layout = Layout::new(dir, "repo");
    let logs = match layout.generations() {
        Ok(logs) => logs,
        Err(e) if gone(&e) => return Ok(()),
        Err(e) => return Err(e),
    };
    let files = logs
        .into_iter()
        .map(|g| layout.log(g))
        .chain([layout.checkpoint(), dir.to_path_buf()]);
    for path in files {
        match std::fs::File::open(&path) {
            Ok(f) => pds_store::flush_file(&f)?,
            Err(e) if gone(&e) => {}
            Err(e) => return Err(e),
        }
    }
    Ok(())
}

/// The file a process holds a data directory by.
const LOCK: &str = "lock";

/// Hold the data directory `dir`, made if it is missing, for as long as the
/// file answered is open: `pds serve` and `pds migrate-blobs` each hold it
/// while they run (`spec/COMMANDS.md`). Refused if another process holds
/// it; the system lets it go when the process ends, however it ends.
pub(crate) fn hold(dir: &Path) -> Result<std::fs::File, String> {
    pds_store::make_dirs(dir).map_err(|e| format!("{}: {e}", dir.display()))?;
    let lock = dir.join(LOCK);
    let at = |e: io::Error| format!("{}: {e}", lock.display());
    let f = pds_store::open_private(
        &lock,
        std::fs::OpenOptions::new()
            .create(true)
            .truncate(false)
            .write(true),
    )
    .map_err(at)?;
    match rustix::fs::flock(&f, rustix::fs::FlockOperation::NonBlockingLockExclusive) {
        Ok(()) => Ok(f),
        Err(rustix::io::Errno::WOULDBLOCK) => Err(format!(
            "{} is held by another process: a pds serve, or a pds migrate-blobs, runs on it",
            dir.display()
        )),
        Err(e) => Err(at(e.into())),
    }
}

/// When an account's log is compacted: past its checkpoint's size, or
/// `Config::account_cap` (`ACCOUNT_CAP`) if that is less, or `log_floor` if
/// that is more; or once its generation began more than twice the window
/// ago, as its files tell
/// (`pds_store::Policy::max_age`): so the first write after `2 W` of quiet
/// compacts it, though the server was started again, or the store let go
/// and loaded again, meanwhile (`spec/STORE.md`, "Settled").
pub(crate) fn policy(c: &Config) -> Policy {
    Policy {
        floor: c.log_floor,
        cap: Some(c.account_cap),
        max_age: Some(c.backfill * 2),
    }
}

/// When the service log is compacted: as an account's, by age too across a
/// start, but that it grows to no more than `SERVICE_CAP`, however large its
/// checkpoint.
pub(crate) fn service_policy(c: &Config) -> Policy {
    Policy {
        cap: Some(SERVICE_CAP),
        ..policy(c)
    }
}

/// Whether a checkpoint written at `now_ms` keeps an event: made no more than
/// the window before, with a second's slack for events numbered in another
/// order than their times by the accounts' writes side by side.
pub(crate) fn in_window(frame: &[u8], now_ms: u64, window: u64) -> bool {
    event_time(frame).is_none_or(|t| t + 1000 + window >= now_ms)
}

fn now_secs() -> u64 {
    crate::events::now_ms() / 1000
}

/// The service log's fold: its checkpoint, a table (`compact`), put in
/// place with the directory held, which reads it from then on.
pub(crate) struct ServiceFold {
    /// The backfill window, in milliseconds.
    pub window: u64,
    /// The accounts, which read the table once it is in place.
    pub accounts: std::sync::Weak<crate::directory::Accounts>,
}

impl Fold for ServiceFold {
    fn fold_files(
        &self,
        checkpoint: Option<&Path>,
        logs: &[PathBuf],
        generation: u64,
        out: &mut dyn io::Write,
    ) -> Result<(), String> {
        let now = crate::events::now_ms();
        crate::compact::fold_files(
            checkpoint,
            logs,
            generation,
            now_secs(),
            |_, f| in_window(f, now, self.window),
            out,
        )
    }

    fn install(
        &self,
        generation: u64,
        rename: &mut dyn FnMut() -> Result<(), String>,
    ) -> Result<(), String> {
        match self.accounts.upgrade() {
            Some(accounts) => accounts.install(generation, rename),
            None => rename(),
        }
    }
}

/// Remove a file that may not be there.
fn remove_if(path: &Path) -> io::Result<()> {
    match std::fs::remove_file(path) {
        Err(e) if e.kind() != io::ErrorKind::NotFound => Err(e),
        _ => Ok(()),
    }
}

/// The service log's file of the layout before generations.
pub(crate) const LEGACY_SERVICE: &str = "accounts.log";
/// An account's log of the layout before generations.
const LEGACY_REPO: &str = "repo.log";

/// Remove what the layout before generations left once its logs were moved
/// to generation 0: a crash between the two leaves it.
pub(crate) fn remove_legacy(dir: &Path, did: Option<&str>) -> io::Result<()> {
    match did {
        None => {
            remove_if(&dir.join(LEGACY_SERVICE))?;
            remove_if(&dir.join(format!("{LEGACY_SERVICE}.rewrite")))?;
            remove_if(&dir.join(MIGRATING))
        }
        Some(did) => remove_if(&dir.join("repos").join(did).join(LEGACY_REPO)),
    }
}

/// The service log of generation 0 being written by a migration that
/// renumbers its events.
const MIGRATING: &str = "accounts.0.log.migrating";

/// Whether `dir` holds the layout before generations: `accounts.log`, and
/// neither a service checkpoint nor a log of any generation.
fn is_legacy(dir: &Path) -> io::Result<bool> {
    if !dir.join(LEGACY_SERVICE).exists() || service_layout(dir).checkpoint().exists() {
        return Ok(false);
    }
    let Ok(entries) = std::fs::read_dir(dir) else {
        return Ok(true);
    };
    for e in entries {
        let name = e?.file_name();
        let name = name.to_string_lossy();
        if name
            .strip_prefix("accounts.")
            .and_then(|r| r.strip_suffix(".log"))
            .is_some_and(|g| !g.is_empty() && g.bytes().all(|b| b.is_ascii_digit()))
        {
            return Ok(false);
        }
    }
    Ok(true)
}

/// An event entry of a log of the layout before generations: where it is,
/// its `ord`, and the seq it was written with.
struct LegacyEvent {
    /// The account whose log it is in, or none for the service log's.
    log: Option<String>,
    frame: usize,
    entry: usize,
    ord: u64,
    seq: u64,
}

/// Move the layout before generations to generation 0, on the first start
/// with it: `accounts.log` becomes `accounts.0.log`, and each account's
/// `repo.log` its `repo.0.log`, read as they are, but that each event's seq
/// is the one the server before served it with. That server numbered the
/// events again at each start, 1, 2, ... in the order of their `ord`s, a
/// deleted account's places among them; numbers are never given again from
/// now on, so they are fixed here, once: an event whose seq is not that is
/// written with it, in a log of generation 0 written whole beside the old
/// one. Logs whose events need nothing are renamed. The service log moves
/// last, and its move is the migration's commit: until then a start finds
/// the layout before generations and migrates again, from each account's
/// `repo.log`, or its `repo.0.log` where a move before was cut short; after,
/// the old files left are removed.
pub(crate) fn migrate(dir: &Path) -> Result<(), String> {
    let at = |p: &Path, e: io::Error| format!("{}: {e}", p.display());
    if !is_legacy(dir).map_err(|e| at(dir, e))? {
        return Ok(());
    }
    let service_path = dir.join(LEGACY_SERVICE);
    let data = std::fs::read(&service_path).map_err(|e| at(&service_path, e))?;
    let (mut service, _) =
        pds_store::scan(&data).map_err(|why| format!("{}: {why}", service_path.display()))?;
    // The accounts, and the places of the deleted ones' events.
    let mut accounts: Vec<String> = Vec::new();
    let mut gaps: Vec<u64> = Vec::new();
    let mut events: Vec<LegacyEvent> = Vec::new();
    let legacy_event = |log: Option<String>,
                        frame: usize,
                        entry: usize,
                        e: &Json|
     -> Result<Option<LegacyEvent>, String> {
        let (Some(ord), Some(seq)) = (e["ord"].as_u64(), e["seq"].as_u64()) else {
            return Err(format!("an event with no ord or seq: {e}"));
        };
        Ok(Some(LegacyEvent {
            log,
            frame,
            entry,
            ord,
            seq,
        }))
    };
    for (i, f) in service.iter().enumerate() {
        for (j, e) in f.iter().enumerate() {
            match e["t"].as_str() {
                Some("account") => accounts.extend(e["did"].as_str().map(str::to_string)),
                Some("deleted") => {
                    let did = e["did"].as_str().unwrap_or_default();
                    accounts.retain(|a| a != did);
                    events.retain(|x| {
                        x.log.as_deref() != Some(did)
                            && !(x.log.is_none() && service[x.frame][x.entry]["did"] == did)
                    });
                    for g in e["gaps"].as_array().into_iter().flatten() {
                        if let (Some(a), Some(b)) = (g[0].as_u64(), g[1].as_u64()) {
                            gaps.extend(a..=b);
                        }
                    }
                    events.extend(legacy_event(None, i, j, e)?);
                }
                Some("event") => events.extend(legacy_event(None, i, j, e)?),
                _ => {}
            }
        }
    }
    // Each account's log: `repo.log`, or `repo.0.log` if a migration cut short moved it.
    let mut logs: BTreeMap<String, (PathBuf, Vec<Vec<Json>>)> = BTreeMap::new();
    for did in &accounts {
        let d = dir.join("repos").join(did);
        let path = [d.join(LEGACY_REPO), d.join("repo.0.log")]
            .into_iter()
            .find(|p| p.exists());
        let Some(path) = path else { continue };
        let data = std::fs::read(&path).map_err(|e| at(&path, e))?;
        let frames = pds_store::scan(&data)
            .map_err(|why| format!("{}: {why}", path.display()))?
            .0;
        for (i, f) in frames.iter().enumerate() {
            for (j, e) in f.iter().enumerate() {
                if e["t"] == "event" {
                    events.extend(legacy_event(Some(did.clone()), i, j, e)?);
                }
            }
        }
        logs.insert(did.clone(), (path, frames));
    }
    // Number them as the server before did.
    let mut places: Vec<(u64, Option<usize>)> = events
        .iter()
        .enumerate()
        .map(|(i, e)| (e.ord, Some(i)))
        .collect();
    places.extend(gaps.iter().map(|&o| (o, None)));
    places.sort();
    let mut changed: HashSet<Option<String>> = HashSet::new();
    let mut renumber: HashMap<(Option<String>, usize, usize), u64> = HashMap::new();
    for (n, (_, i)) in places.iter().enumerate() {
        let Some(i) = i else { continue };
        let e = &events[*i];
        let seq = n as u64 + 1;
        if e.seq != seq {
            changed.insert(e.log.clone());
            renumber.insert((e.log.clone(), e.frame, e.entry), seq);
        }
    }
    let fix = |log: Option<&str>, frames: &mut [Vec<Json>]| -> Result<(), String> {
        for (i, f) in frames.iter_mut().enumerate() {
            for (j, e) in f.iter_mut().enumerate() {
                if let Some(&seq) = renumber.get(&(log.map(str::to_string), i, j)) {
                    let frame = e["frame"]
                        .as_str()
                        .and_then(|h| hex::decode(h).ok())
                        .ok_or_else(|| format!("an event with no frame: {e}"))?;
                    let frame = crate::events::renumber(&frame, seq)?;
                    e["seq"] = seq.into();
                    e["frame"] = hex::encode(frame).into();
                }
            }
        }
        Ok(())
    };
    let write_whole = |path: &Path, frames: &[Vec<Json>]| -> io::Result<()> {
        use std::io::Write;
        let f = pds_store::open_private(
            path,
            std::fs::OpenOptions::new()
                .create(true)
                .write(true)
                .truncate(true),
        )?;
        let mut out = io::BufWriter::new(&f);
        for entries in frames {
            out.write_all(&pds_store::frame(entries))?;
        }
        out.flush()?;
        drop(out);
        pds_store::sync_file(&f)
    };
    for (did, (path, mut frames)) in logs {
        let d = dir.join("repos").join(&did);
        let gen0 = d.join("repo.0.log");
        if changed.contains(&Some(did.clone())) {
            fix(Some(&did), &mut frames)?;
            write_whole(&gen0, &frames).map_err(|e| at(&gen0, e))?;
        } else if path != gen0 {
            std::fs::rename(&path, &gen0).map_err(|e| at(&path, e))?;
        }
        pds_store::sync_dir(&d).map_err(|e| at(&d, e))?;
    }
    let gen0 = service_layout(dir).log(0);
    if changed.contains(&None) {
        fix(None, &mut service)?;
        let tmp = dir.join(MIGRATING);
        write_whole(&tmp, &service).map_err(|e| at(&tmp, e))?;
        std::fs::rename(&tmp, &gen0).map_err(|e| at(&tmp, e))?;
    } else {
        std::fs::rename(&service_path, &gen0).map_err(|e| at(&service_path, e))?;
    }
    pds_store::sync_dir(dir).map_err(|e| at(dir, e))?;
    remove_legacy(dir, None).map_err(|e| at(dir, e))?;
    Ok(())
}

#[cfg(test)]
mod tests {
    /// A data directory is held by one at a time, until it lets it go.
    #[test]
    fn a_data_directory_is_held_by_one_at_a_time() {
        let dir = crate::testing::scratch("held");
        let held = super::hold(&dir).unwrap();
        let refused = super::hold(&dir).unwrap_err();
        assert!(refused.contains("held by another process"), "{refused}");
        drop(held);
        drop(super::hold(&dir).unwrap());
        let _ = std::fs::remove_dir_all(&dir);
    }
}