path: root/src/fs.zig

//! An asynchronous 9P2000 file-server engine over `Server` (the session).
//!
//! The engine turns each request into a job of one or more backend
//! operations (`Req`), issued through `next()`/`retry()` and answered by tag
//! through `reply()`; a backend may answer at once or later, and may park a
//! read or write with `Status.again`. The engine owns fids, permissions, the
//! directory-read cursor, Tflush and the releases a dropped connection owes.
//! Like the session it is built on, it is allocation-free, makes no OS
//! calls, and is driven by `push()`/`output()`/`wrote()`. Its tables are
//! sized by comptime `Options`. See docs/design.md, "File server engine".
const std = @import("std");
const assert = std.debug.assert;
const testing = std.testing;
const c9 = @import("root.zig");
const wire = @import("wire.zig");
const Protocol = @import("Server.zig");

const Qid = wire.Qid;
const Stat = wire.Stat;
const Msg = wire.Msg;
const Decoded = wire.Decoded;
const header_len = wire.header_len;
const qid_len = wire.qid_len;
const stat_fixed = wire.stat_fixed;
const max_welem = wire.max_welem;
const iohdrsz = wire.iohdrsz;
const notag = wire.notag;
const nofid = wire.nofid;
const qtdir = wire.qtdir;
const qtfile = wire.qtfile;
const qtappend = wire.qtappend;
const qtexcl = wire.qtexcl;
const dmdir = wire.dmdir;
const dmappend = wire.dmappend;
const dmexcl = wire.dmexcl;

// ---- the backend contract ----

/// What the engine asks of a backend. Every request names a node; open,
/// read, write, readdir and release also carry the handle open returned.
pub const Op = enum(u8) {
    lookup,
    getattr,
    setattr,
    open,
    read,
    write,
    release,
    readdir,
};

/// `again` parks the request until the engine retries it (or, for a read or
/// write, until the backend answers the same tag later). A read, readdir,
/// write, open, clunk, remove or truncating wstat can park; a walk, attach,
/// stat, create or renaming wstat cannot, because their names live in the
/// input frame that parking lets go of, and those answer an error instead.
pub const Status = enum(u8) {
    ok,
    again,
    err,
};

/// Node attributes a lookup, getattr or setattr answers with. `node` zero
/// keeps the node the engine asked about; `mode` is the permission bits.
pub const Attr = struct {
    name: []const u8 = "",
    node: u64 = 0,
    dir: bool = false,
    size: u64 = 0,
    mode: u16 = 0o644,
    mtime: u32 = 0,
    atime: u32 = 0,
    /// The qid's version.
    version: u32 = 0,
    /// The qid's path when it must differ from `node`.
    path: ?u64 = null,
    /// Append-only and exclusive-use files: qid type and mode bits.
    append: bool = false,
    excl: bool = false,
};
const attr_type = Attr;

/// Optional backend capabilities, declared as `pub const features: fs.Features`
/// on the backend type. A backend without the declaration has none and the
/// engine refuses the requests they would produce, as it always did.
pub const Features = struct {
    /// Tcreate becomes an `open` with `create` set: `data` is the name,
    /// `perm` the permissions (dmdir for a directory) and `omode` the mode;
    /// the reply names the new node in `attr` and carries its open handle.
    create: bool = false,
    /// Tremove, and ORCLOSE on clunk or hangup, become a `release` with
    /// `remove` set, whose failure is the Rremove's error (the fid is
    /// dropped either way).
    remove: bool = false,
    /// Twstat beyond a zero-length truncation becomes a `setattr` whose
    /// `set` names the fields to change (`data` the new name, `perm` the
    /// mode, `mtime`, `length`).
    wstat: bool = false,
    /// Every lookup result is a reference the backend hands out: the engine
    /// asks lookups for "." too (cloning a fid included) and answers each
    /// reference with exactly one `release` (`opened` says whether an open
    /// handle goes with it) when the fid, or the walk in progress, lets go.
    references: bool = false,
};

/// Which fields a `setattr` changes (`Features.wstat`).
pub const Set = struct {
    name: bool = false,
    mode: bool = false,
    mtime: bool = false,
    length: bool = false,

    pub fn any(s: Set) bool {
        return s.name or s.mode or s.mtime or s.length;
    }
};

/// One backend operation. `tag` is unique per connection and never zero.
/// `data` is a lookup's or create's name, a write's bytes or a setattr's
/// new name, and is borrowed until the reply, unless the write parks, in
/// which case the engine keeps a copy.
pub const Req = struct {
    tag: u64,
    op: Op,
    node: u64,
    handle: u32 = 0,
    off: u64 = 0,
    size: u32 = 0,
    data: []const u8 = &.{},
    truncate: bool = false,
    /// open: the 9P mode asked for (access bits, OTRUNC, ORCLOSE).
    omode: u8 = 0,
    /// open (`Features.create`): create `data` in the directory `node`
    /// with permissions `perm` and open it with `omode`.
    create: bool = false,
    /// create: the new file's permissions; setattr: the new mode.
    perm: u32 = 0,
    /// release: `handle` is an open handle (else the fid was never opened).
    opened: bool = false,
    /// release (`Features.remove`): remove the node as well.
    remove: bool = false,
    /// setattr (`Features.wstat`): the fields to change.
    set: Set = .{},
    mtime: u32 = 0,
    length: u64 = 0,
};

/// A reply carrying an application-defined `payload`: a locator for the
/// reply's bytes that the engine ignores and the application resolves
/// before calling `reply()`. `Payload` is `void` or a type with a `none`
/// tag, which is the default value.
pub fn ReplyWith(comptime Payload: type) type {
    return struct {
        tag: u64,
        status: Status = .ok,
        errno: u16 = 0,
        attr: attr_type = .{},
        handle: u32 = 0,
        payload: Payload = noPayload(Payload),
        written: u32 = 0,
        /// The Rerror text of an `err` reply, when the backend has a better
        /// one than `errString(errno)`; at most `errmax` bytes are sent.
        ename: []const u8 = "",

        pub const Attr = attr_type;

        pub fn fail(tag: u64, e: u16) @This() {
            return .{ .tag = tag, .status = .err, .errno = e };
        }
    };
}

fn noPayload(comptime Payload: type) Payload {
    return if (Payload == void) {} else .none;
}

/// The backend's answer to one `Req`, matched by tag. The bytes of a read
/// or readdir travel beside it as the `bytes` argument of `reply()`.
pub const Reply = ReplyWith(void);

/// The errno values a backend may answer with; `errString` names each.
pub const E = struct {
    pub const PERM: u16 = 1;
    pub const NOENT: u16 = 2;
    pub const IO: u16 = 5;
    pub const NOMEM: u16 = 12;
    pub const EXIST: u16 = 17;
    pub const NOTDIR: u16 = 20;
    pub const ISDIR: u16 = 21;
    pub const INVAL: u16 = 22;
    pub const NFILE: u16 = 23;
    pub const NOSPC: u16 = 28;
    pub const NOSYS: u16 = 38;
    pub const NOTEMPTY: u16 = 39;
};

/// Longest Rerror string the engine emits.
pub const errmax: usize = 128;

pub const e_unknown_fid = "fid unknown or out of range";
pub const e_fid_in_use = "fid already in use";
pub const e_bad_use = "bad use of fid";
pub const e_bad_offset = "bad offset in directory read";
pub const e_perm = "permission denied";
pub const e_not_dir = "not a directory";
pub const e_already_open = "file already open for I/O";
pub const e_illegal_name = "illegal name";
pub const e_too_many_fids = "Too many open files in system";
pub const e_botch = "protocol botch";
pub const e_interrupted = "Interrupted system call";
pub const e_trunc_only = "only support truncation to zero length";
pub const e_wstat = "wstat prohibited";
pub const e_again = "Resource temporarily unavailable";
pub const e_count_small = "Invalid argument";
pub const e_no_tree = "No such file or directory";
pub const e_no_auth = "authentication not required";
pub const e_small_msize = "Invalid argument";

/// The Rerror string for a backend errno, in the spelling Linux v9fs maps back.
pub fn errString(errno: u16) []const u8 {
    return switch (errno) {
        E.PERM => "Operation not permitted",
        E.NOENT => "No such file or directory",
        E.IO => "Input/output error",
        E.NOMEM => "Cannot allocate memory",
        E.EXIST => "File exists",
        E.NOTDIR => "Not a directory",
        E.ISDIR => "Is a directory",
        E.INVAL => "Invalid argument",
        E.NFILE => "Too many open files in system",
        E.NOSPC => "No space left on device",
        E.NOSYS => "Function not implemented",
        E.NOTEMPTY => "Directory not empty",
        else => "Input/output error",
    };
}

/// The modes directory entries report; a stat of the entry gives the real ones.
pub const dirent_dir_perm: u16 = 0o500;
pub const dirent_file_perm: u16 = 0o600;

/// The smallest msize the engine negotiates: one full Rwalk must fit.
pub const msize_min: u32 = header_len + 2 + max_welem * qid_len;

/// Comptime capacities of one engine instance. The defaults are the
/// editor's, except the name capacity, which is the board's.
pub const Options = struct {
    /// Fids one connection may hold at once.
    fid_capacity: usize = 256,
    /// Parked reads and writes one connection may hold at once.
    slot_capacity: usize = 32,
    /// Longest write payload a parked write keeps a copy of.
    park_data_max: usize = 128,
    /// Longest file name a fid remembers; longer walk elements are illegal.
    /// Zero keeps no names: a stat's name is the one its getattr answers,
    /// and the backend judges name lengths.
    name_capacity: usize = 28,
    /// Longest attach uname kept for the uid, gid and muid of stats.
    username_capacity: usize = 28,
    /// Index the fid table by fid number (open addressing, two bytes per
    /// bucket, twice the fid capacity rounded up to a power of two) so that
    /// lookups stay O(1) with thousands of fids; `InitOptions.seed` salts it.
    fid_index: bool = false,
};

comptime {
    const defaults: Options = .{};
    assert(msize_min == 217);
    assert(header_len + 2 + stat_fixed + defaults.name_capacity + 3 * defaults.username_capacity <= msize_min);
    assert(header_len + 4 + stat_fixed + defaults.name_capacity + 3 * defaults.username_capacity <= msize_min);
    assert(defaults.username_capacity >= 20);
    assert(c9.oread | c9.owrite | c9.ordwr | c9.oexec == 3);
    assert(c9.otrunc | c9.ocexec | c9.orclose == 112);
}

/// The qid of `node` as `a` describes it.
fn qidFrom(node: u64, a: Attr) Qid {
    var t: u8 = if (a.dir) qtdir else qtfile;
    if (a.append) t |= qtappend;
    if (a.excl) t |= qtexcl;
    return .{ .type = t, .version = a.version, .path = a.path orelse node };
}

fn featuresOf(comptime Backend: type) Features {
    return if (@hasDecl(Backend, "features")) Backend.features else .{};
}

/// A name a create or rename may use: not empty, "." or "..", no '/' or NUL.
fn legalName(name: []const u8) bool {
    if (name.len == 0 or name.len > 255) return false;
    if (std.mem.eql(u8, name, ".") or std.mem.eql(u8, name, "..")) return false;
    return std.mem.indexOfAny(u8, name, "/\x00") == null;
}

/// MurmurHash3's 32-bit finalizer: every input bit affects every output bit.
fn fmix32(x: u32) u32 {
    var h = x;
    h ^= h >> 16;
    h *%= 0x85EB_CA6B;
    h ^= h >> 13;
    h *%= 0xC2B2_AE35;
    h ^= h >> 16;
    return h;
}

/// The engine for a `Backend` that declares `Req` (this module's `Req`) and
/// `Reply` (this module's `Reply`, or a `ReplyWith`), and optionally
/// `features` (a `Features`). Drive it like the session: `push()` bytes in,
/// answer every `retry()` then every `next()` request through `reply()`,
/// drain `output()` and report `wrote()`. On `protocol.dead` call
/// `hangup()`, answer the releases `next()` still yields, and `init()` again.
pub fn Server(comptime Backend: type, comptime opts: Options) type {
    if (opts.fid_capacity == 0) @compileError("9P server needs at least one fid");
    if (opts.fid_capacity >= std.math.maxInt(u16)) @compileError("9P server fid capacity must fit a u16 slot number");
    if (opts.slot_capacity == 0) @compileError("9P server needs at least one parking slot");
    if (opts.name_capacity > 255) @compileError("9P backend name capacity must fit a directory entry");
    if (opts.username_capacity == 0) @compileError("9P server needs room for a user name");
    if (Backend.Req != Req) @compileError("9P backend requests must be cloud9.fs.Req");
    inline for (.{ "tag", "status", "errno", "attr", "handle", "written", "ename" }) |field| {
        if (!@hasField(Backend.Reply, field)) @compileError("9P backend replies must be cloud9.fs.Reply or a cloud9.fs.ReplyWith");
    }
    if (@FieldType(Backend.Reply, "attr") != Attr) @compileError("9P backend replies must carry cloud9.fs.Attr");
    const name_capacity = opts.name_capacity;
    const username_capacity = opts.username_capacity;
    const park_data_max = opts.park_data_max;
    const features = featuresOf(Backend);
    const refs = features.references;
    return struct {
        const Self = @This();

        protocol: Protocol,
        root: u64,

        uname: [username_capacity]u8 = @splat(0),
        uname_len: u8 = 0,

        fids: [opts.fid_capacity]Fid = @splat(.{}),
        slots: [opts.slot_capacity]Slot = @splat(.{}),
        job: Job = .{},
        seq: u64 = 0,
        /// Fids held, orphans owed a release included.
        nfids: u32 = 0,
        /// Orphans among them, so that `next()` scans the table only when one waits.
        norphans: u32 = 0,
        /// The fid index (`Options.fid_index`): fid number -> slot of `fids`,
        /// `no_slot` for an empty bucket; salted so that a client cannot
        /// choose fid numbers that collide.
        index: [index_len]u16 = @splat(no_slot),
        hash_seed: u32 = 0,
        /// Head of the free list threaded through `Fid.next_free`.
        free_head: u16 = no_slot,
        /// Slots `high_water..` have never been used (bump allocation).
        high_water: u16 = 0,

        pub const options = opts;
        pub const backend_features = features;

        const Kind = enum { none, attach, walk, open, create, read, readdir, write, clunk, remove, stat, wstat };

        pub const Fid = struct {
            used: bool = false,
            fid: u32 = 0,
            node: u64 = 0,
            dir: bool = false,
            perm: u16 = 0,
            open: bool = false,
            omode: u8 = 0,
            rclose: bool = false,
            handle: u32 = 0,
            diroff: u64 = 0,
            dirindex: u32 = 0,
            orphan: bool = false,
            qid: Qid = .{ .type = 0, .version = 0, .path = 0 },
            /// Free-list link, meaningful while `!used` (`Options.fid_index`).
            next_free: u16 = no_slot,
            name: [name_capacity]u8 = @splat(0),
            name_len: u8 = 0,
        };

        const no_slot: u16 = std.math.maxInt(u16);
        const index_len: usize = if (opts.fid_index) std.math.ceilPowerOfTwoAssert(usize, opts.fid_capacity * 2) else 0;
        const index_mask: usize = if (opts.fid_index) index_len - 1 else 0;
        const index_shift: u5 = if (opts.fid_index) @intCast(32 - @as(usize, std.math.log2_int(usize, index_len))) else 0;

        const Slot = struct {
            used: bool = false,
            parked: bool = false,
            retried: bool = false,
            copied: bool = false,
            seq: u64 = 0,
            tag: u16 = 0,
            kind: Kind = .none,
            fid: u32 = 0,
            count: u32 = 0,
            req: Backend.Req = undefined,
            data: [park_data_max]u8 = undefined,
            /// What a parked open needs to become a job again; a parked
            /// wstat is always a truncation to zero, and a clunk or remove
            /// keeps nothing but its fid.
            omode: u8 = 0,
            step: u8 = 0,

            /// Whether the slot holds a whole job rather than a read or write
            /// the engine answers from the slot itself.
            fn holdsJob(sl: *const Slot) bool {
                return switch (sl.kind) {
                    .open, .wstat, .clunk, .remove => true,
                    else => false,
                };
            }
        };

        const Job = struct {
            kind: Kind = .none,
            tag: u16 = 0,
            req_tag: u64 = 0,
            req: Backend.Req = undefined,
            step: u8 = 0,
            fid: u32 = 0,
            newfid: u32 = 0,
            count: u32 = 0,
            offset: u64 = 0,
            omode: u8 = 0,
            node: u64 = 0,
            dir: bool = false,
            perm: u16 = 0,
            qid: Qid = .{ .type = 0, .version = 0, .path = 0 },
            name: [name_capacity]u8 = @splat(0),
            name_len: u8 = 0,
            nwname: u8 = 0,
            nwqid: u8 = 0,
            wqid: [max_welem]Qid = @splat(.{ .type = 0, .version = 0, .path = 0 }),
            msg: Msg = .rflush,
            /// A walk cloning its fid (`Features.references`: one lookup of ".").
            clone: bool = false,
            /// `node` is a reference this walk obtained, not the fid's.
            held: bool = false,
            /// A reference to release before the job goes on.
            forget: u64 = 0,
            /// The outstanding request is that release.
            forgetting: bool = false,
            /// The reply went out; only releases remain.
            closing: bool = false,
            /// This is a parked job asked again this retry round: parked
            /// once more, it sits the round out like a retried read does.
            retried: bool = false,
            /// A create's permissions, a wstat's changes.
            cperm: u32 = 0,
            set: Set = .{},
            mtime: u32 = 0,
            length: u64 = 0,
        };

        pub const InitOptions = struct {
            in: []u8,
            out: []u8,
            root: u64,
            /// Salt for the fid index; a platform layer with a random source
            /// makes it unpredictable.
            seed: u32 = 0,
        };

        pub fn init(o: InitOptions) Self {
            assert(o.in.len >= msize_min);
            assert(o.out.len >= 2 * msize_min);
            assert(o.root != 0);
            return .{ .protocol = .init(.{ .in = o.in, .out = o.out }), .root = o.root, .hash_seed = fmix32(o.seed) };
        }

        pub fn references(s: *const Self, node: u64) bool {
            for (s.fids) |fid| if (fid.used and fid.node == node) return true;
            if (s.job.kind != .none and s.job.node == node) return true;
            for (s.slots) |slot| if (slot.used and slot.req.node == node) return true;
            return false;
        }

        /// Fids held, the releases a hangup still owes included.
        pub fn fidCount(s: *const Self) usize {
            return s.nfids;
        }

        pub fn hangup(s: *Self) void {
            s.reset();
            s.protocol.hangup();
        }

        fn reset(s: *Self) void {
            for (&s.fids, 0..) |*f, i| {
                if (!f.used or f.orphan) continue;
                if (f.open or refs) s.orphanFid(i) else s.releaseSlot(i);
            }
            if (refs) {
                // A walk in progress holds references no fid owns yet.
                if (s.job.kind == .walk and s.job.held) s.stash(s.job.node);
                if (s.job.forget != 0) s.stash(s.job.forget);
            }
            for (&s.slots) |*sl| sl.* = .{};
            s.job = .{};
        }

        /// Parks `node` as an orphan owed a release (`Features.references`).
        fn stash(s: *Self, node: u64) void {
            const i = s.takeFid() orelse return;
            s.fids[i] = .{ .used = true, .orphan = true, .node = node };
            s.nfids += 1;
            s.norphans += 1;
        }

        pub fn push(s: *Self, bytes: []const u8) usize {
            return s.protocol.push(bytes);
        }

        pub fn output(s: *const Self) []const u8 {
            return s.protocol.output();
        }

        pub fn wrote(s: *Self, n: usize) void {
            s.protocol.wrote(n);
        }

        fn hasRoom(s: *Self) bool {
            return s.protocol.hasRoom();
        }

        fn emit(s: *Self, tag: u16, msg: Msg) void {
            s.protocol.reply(tag, msg) catch {
                s.protocol.dead = true;
            };
        }

        fn fail(s: *Self, tag: u16, ename: []const u8) void {
            s.emit(tag, .{ .rerror = .{ .ename = ename[0..@min(ename.len, errmax)] } });
        }

        fn failReply(s: *Self, tag: u16, r: *const Backend.Reply) void {
            s.fail(tag, if (r.ename.len != 0) r.ename else errString(r.errno));
        }

        fn tick(s: *Self) u64 {
            s.seq += 1;
            return s.seq;
        }

        // ---- the fid table ----

        /// Fibonacci hashing of the salted fid number into `index_len` buckets.
        fn fidHome(s: *const Self, fid: u32) usize {
            return @intCast(((fid ^ s.hash_seed) *% 0x9E37_79B1) >> index_shift);
        }

        /// The index bucket holding `fid`, if any.
        fn findBucket(s: *const Self, fid: u32) ?usize {
            var pos = s.fidHome(fid);
            while (true) : (pos = (pos + 1) & index_mask) {
                const slot = s.index[pos];
                if (slot == no_slot) return null;
                if (s.fids[slot].fid == fid) return pos;
            }
        }

        /// The slot of the live (non-orphan) fid `fid`.
        fn findFid(s: *const Self, fid: u32) ?usize {
            if (opts.fid_index) {
                const pos = s.findBucket(fid) orelse return null;
                return s.index[pos];
            }
            for (&s.fids, 0..) |*f, i| if (f.used and !f.orphan and f.fid == fid) return i;
            return null;
        }

        fn hasFreeFid(s: *const Self) bool {
            if (opts.fid_index) return s.nfids < opts.fid_capacity;
            for (&s.fids) |*f| if (!f.used) return true;
            return false;
        }

        /// A free slot; the caller fills it and, unless it is an orphan,
        /// binds it. Counts toward `nfids` only once bound or stashed.
        fn takeFid(s: *Self) ?usize {
            if (opts.fid_index) {
                if (s.nfids >= opts.fid_capacity) return null;
                if (s.free_head != no_slot) {
                    const slot = s.free_head;
                    s.free_head = s.fids[slot].next_free;
                    return slot;
                }
                assert(s.high_water < opts.fid_capacity);
                const slot = s.high_water;
                s.high_water += 1;
                return slot;
            }
            for (&s.fids, 0..) |*f, i| if (!f.used) return i;
            return null;
        }

        /// Makes the used slot `i` (fid number set) findable.
        fn bindFid(s: *Self, i: usize) void {
            assert(s.fids[i].used and !s.fids[i].orphan);
            s.nfids += 1;
            if (!opts.fid_index) return;
            var pos = s.fidHome(s.fids[i].fid);
            while (s.index[pos] != no_slot) pos = (pos + 1) & index_mask;
            s.index[pos] = @intCast(i);
        }

        /// Removes the live fid at slot `i` from the index (backward-shift
        /// deletion: no tombstones).
        fn unbindFid(s: *Self, i: usize) void {
            if (!opts.fid_index) return;
            var hole = s.findBucket(s.fids[i].fid).?;
            var j = hole;
            while (true) {
                j = (j + 1) & index_mask;
                const slot = s.index[j];
                if (slot == no_slot) break;
                const k = s.fidHome(s.fids[slot].fid);
                // The entry at j may move into the hole unless its home lies
                // in the cyclic interval (hole, j].
                const stays = if (hole <= j) (k > hole and k <= j) else (k > hole or k <= j);
                if (!stays) {
                    s.index[hole] = slot;
                    hole = j;
                }
            }
            s.index[hole] = no_slot;
        }

        /// Frees slot `i`, live or orphan.
        fn releaseSlot(s: *Self, i: usize) void {
            assert(s.fids[i].used);
            if (!s.fids[i].orphan) s.unbindFid(i);
            s.fids[i] = .{ .next_free = s.free_head };
            if (opts.fid_index) s.free_head = @intCast(i);
            s.nfids -= 1;
        }

        /// Takes the live fid at slot `i` out of the table but keeps the
        /// slot until the backend has been paid its release.
        fn orphanFid(s: *Self, i: usize) void {
            s.unbindFid(i);
            s.fids[i].orphan = true;
            s.norphans += 1;
        }

        fn dropFid(s: *Self, fid: u32) void {
            if (s.findFid(fid)) |i| s.releaseSlot(i);
        }

        fn findSlot(s: *Self, req_tag: u64) ?usize {
            for (&s.slots, 0..) |*sl, i| if (sl.used and sl.req.tag == req_tag) return i;
            return null;
        }

        fn freeSlot(s: *Self) ?usize {
            for (&s.slots, 0..) |*sl, i| if (!sl.used) return i;
            return null;
        }

        fn findTag(s: *Self, tag: u16) ?usize {
            for (&s.slots, 0..) |*sl, i| if (sl.used and sl.tag == tag) return i;
            return null;
        }

        fn setUname(s: *Self, uname: []const u8) void {
            const n = @min(uname.len, username_capacity);
            @memcpy(s.uname[0..n], uname[0..n]);
            s.uname_len = @intCast(n);
        }

        fn setName(dst: *[name_capacity]u8, dst_len: *u8, name: []const u8) void {
            const n: u8 = @intCast(@min(name.len, name_capacity));
            @memcpy(dst[0..n], name[0..n]);
            dst_len.* = n;
        }

        /// The oldest parked request not yet retried this round, or null when
        /// every parked request has been retried (which starts a new round).
        pub fn retry(s: *Self) ?Backend.Req {
            var best: ?usize = null;
            for (&s.slots, 0..) |*sl, i| {
                if (!sl.used or !sl.parked or sl.retried) continue;
                // A parked job goes back into the job slot, so it waits its
                // turn for that.
                if (sl.holdsJob() and s.job.kind != .none) continue;
                if (best == null or sl.seq < s.slots[best.?].seq) best = i;
            }
            const i = best orelse {
                for (&s.slots) |*sl| sl.retried = false;
                return null;
            };
            if (!s.hasRoom()) {
                for (&s.slots) |*sl| sl.retried = false;
                return null;
            }
            const sl = &s.slots[i];
            if (sl.holdsJob()) {
                // Its fid may have been clunked while it waited: then there
                // is nobody to answer, and asking the backend would make it
                // do the work -- open a handle, make an object -- for no one.
                if (s.findFid(sl.fid) == null) {
                    s.fail(sl.tag, e_unknown_fid);
                    sl.* = .{};
                    return s.retry();
                }
                return s.resumeJob(i);
            }
            sl.retried = true;
            sl.parked = false;
            return sl.req;
        }

        /// Takes a parked job out of its slot and asks its request again;
        /// the reply then goes through `jobReply` like any other.
        fn resumeJob(s: *Self, i: usize) Backend.Req {
            const sl = &s.slots[i];
            assert(s.job.kind == .none);
            s.job = .{
                .kind = sl.kind,
                .tag = sl.tag,
                .fid = sl.fid,
                .omode = sl.omode,
                .step = sl.step,
                .set = if (sl.kind == .wstat) .{ .length = true } else .{},
                .retried = true,
            };
            const req = sl.req;
            sl.* = .{};
            return s.ask(req);
        }

        /// The next backend operation, or null while one is outstanding, the
        /// output is full, or no whole request has arrived.
        pub fn next(s: *Self) ?Backend.Req {
            while (true) {
                if (s.job.kind != .none) {
                    if (s.job.req_tag != 0) return null;
                    if (s.stepJob()) |req| return req;
                    // Done, or (with references) a release still to issue.
                    assert(s.job.kind == .none or (refs and s.job.closing));
                    continue;
                }
                if (s.orphan()) |req| return req;
                if (!s.hasRoom()) return null;
                if (!s.startFrame()) return null;
            }
        }

        /// Answer a request by tag; `bytes` are a read's or readdir's data.
        /// A tag the engine no longer waits for (flushed, hung up) is ignored.
        pub fn reply(s: *Self, r: *const Backend.Reply, bytes: []const u8) void {
            if (s.job.kind != .none and s.job.req_tag == r.tag) return s.jobReply(r, bytes);
            if (s.findSlot(r.tag)) |i| return s.slotReply(i, r, bytes);
        }

        fn orphan(s: *Self) ?Backend.Req {
            if (s.norphans == 0) return null;
            for (&s.fids, 0..) |*f, i| {
                if (!f.used or !f.orphan) continue;
                assert(f.open or refs);
                s.norphans -= 1;
                const req: Backend.Req = .{
                    .tag = s.tick(),
                    .op = .release,
                    .node = f.node,
                    .handle = f.handle,
                    .opened = f.open,
                    .remove = features.remove and f.open and f.rclose,
                };
                s.releaseSlot(i);
                return req;
            }
            return null;
        }

        fn startFrame(s: *Self) bool {
            assert(s.job.kind == .none);
            const got = (s.protocol.receive() catch return false) orelse return false;
            defer if (s.job.kind == .none) s.dropFrame();
            s.dispatch(got);
            return true;
        }

        fn dropFrame(s: *Self) void {
            s.protocol.release();
        }

        fn dispatch(s: *Self, got: Decoded) void {
            switch (got.msg) {
                .tversion => |m| s.version(got.tag, m.msize, m.version),
                .tauth => s.fail(got.tag, e_no_auth),
                .tcreate => |m| if (features.create) s.create(got, m.fid, m.name, m.perm, m.mode) else s.fail(got.tag, e_perm),
                .tattach => |m| s.attach(got.tag, m.fid, m.uname, m.aname),
                .tflush => |m| s.flush(got.tag, m.oldtag),
                .twalk => |m| s.walk(got, m.fid, m.newfid, @intCast(m.nwname)),
                .topen => |m| s.open(got.tag, m.fid, m.mode),
                .tread => |m| s.read(got.tag, m.fid, m.offset, m.count),
                .twrite => |m| s.write(got, m.fid, m.offset, m.data.len),
                .tclunk => |m| s.clunk(got.tag, m.fid, .clunk),
                .tremove => |m| s.clunk(got.tag, m.fid, .remove),
                .tstat => |m| s.stat(got.tag, m.fid),
                .twstat => |m| s.wstat(got, m.fid, m.stat),
                else => s.fail(got.tag, e_botch),
            }
        }

        fn version(s: *Self, tag: u16, want: u32, ver: []const u8) void {
            assert(tag == notag);
            s.reset();
            // The engine's fixed directory staging requires this capacity.
            if (want < msize_min) {
                s.protocol.dead = true;
                return;
            }
            s.protocol.negotiate(want, ver) catch {
                s.protocol.dead = true;
            };
        }

        fn attach(s: *Self, tag: u16, fid: u32, uname: []const u8, aname: []const u8) void {
            if (aname.len != 0) return s.fail(tag, e_no_tree);
            if (fid == nofid) return s.fail(tag, e_unknown_fid);
            if (s.findFid(fid) != null) return s.fail(tag, e_fid_in_use);
            if (!s.hasFreeFid()) return s.fail(tag, e_too_many_fids);
            s.setUname(uname);
            s.job = .{ .kind = .attach, .tag = tag, .fid = fid, .node = s.root };
        }

        fn walk(s: *Self, got: Decoded, fid: u32, newfid: u32, nwname: u8) void {
            const tag = got.tag;
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            if (s.fids[i].open) return s.fail(tag, e_bad_use);
            if (newfid == nofid) return s.fail(tag, e_unknown_fid);
            if (newfid != fid) {
                if (s.findFid(newfid) != null) return s.fail(tag, e_fid_in_use);
                if (!s.hasFreeFid()) return s.fail(tag, e_too_many_fids);
            }
            if (nwname == 0 and (newfid == fid or !refs)) {
                if (newfid != fid) {
                    const j = s.takeFid().?;
                    s.fids[j] = s.fids[i];
                    s.fids[j].fid = newfid;
                    s.fids[j].diroff = 0;
                    s.fids[j].dirindex = 0;
                    s.bindFid(j);
                }
                s.emit(tag, .{ .rwalk = .{ .nwqid = 0 } });
                return;
            }
            if (nwname != 0 and !s.fids[i].dir) return s.fail(tag, e_not_dir);
            s.job = .{
                .kind = .walk,
                .tag = tag,
                .fid = fid,
                .newfid = newfid,
                .nwname = nwname,
                .clone = nwname == 0,
                .node = s.fids[i].node,
                .dir = s.fids[i].dir,
                .perm = s.fids[i].perm,
                .qid = s.fids[i].qid,
                .name = s.fids[i].name,
                .name_len = s.fids[i].name_len,
                .msg = got.msg,
            };
        }

        fn open(s: *Self, tag: u16, fid: u32, mode: u8) void {
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            const f = &s.fids[i];
            if (f.open) return s.fail(tag, e_already_open);
            if (mode & c9.orclose != 0 and !features.remove) return s.fail(tag, e_perm);
            const rw = mode & 3;
            if (rw == c9.oexec) return s.fail(tag, e_perm);
            if (f.dir and (rw != c9.oread or mode & c9.otrunc != 0)) return s.fail(tag, e_perm);
            var need: u16 = 0;
            if (rw == c9.oread or rw == c9.ordwr) need |= 0o400;
            if (rw == c9.owrite or rw == c9.ordwr or mode & c9.otrunc != 0) need |= 0o200;
            if (f.perm & need != need) return s.fail(tag, e_perm);
            s.job = .{ .kind = .open, .tag = tag, .fid = fid, .omode = mode };
        }

        fn create(s: *Self, got: Decoded, fid: u32, name: []const u8, perm: u32, mode: u8) void {
            const tag = got.tag;
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            const f = &s.fids[i];
            if (f.open) return s.fail(tag, e_already_open);
            if (!f.dir) return s.fail(tag, e_not_dir);
            if (!legalName(name) or (name_capacity != 0 and name.len > name_capacity)) return s.fail(tag, e_illegal_name);
            if (mode & c9.orclose != 0 and !features.remove) return s.fail(tag, e_perm);
            const rw = mode & 3;
            if (rw == c9.oexec) return s.fail(tag, e_perm);
            if (perm & dmdir != 0 and (rw != c9.oread or mode & c9.otrunc != 0)) return s.fail(tag, e_perm);
            if (f.perm & 0o200 == 0) return s.fail(tag, e_perm);
            s.job = .{ .kind = .create, .tag = tag, .fid = fid, .omode = mode, .cperm = perm, .msg = got.msg };
        }

        fn read(s: *Self, tag: u16, fid: u32, offset: u64, count: u32) void {
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            const f = &s.fids[i];
            if (!f.open or (f.omode & 3) == c9.owrite) return s.fail(tag, e_bad_use);
            const want = @min(count, s.protocol.msize - header_len - 4);
            if (!f.dir) {
                s.job = .{ .kind = .read, .tag = tag, .fid = fid, .offset = offset, .count = want };
                return;
            }
            if (offset != f.diroff) {
                if (offset != 0) return s.fail(tag, e_bad_offset);
                f.diroff = 0;
                f.dirindex = 0;
            }
            s.job = .{ .kind = .readdir, .tag = tag, .fid = fid, .offset = offset, .count = want };
        }

        fn write(s: *Self, got: Decoded, fid: u32, offset: u64, len: usize) void {
            const tag = got.tag;
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            const f = &s.fids[i];
            if (!f.open or (f.omode & 3) == c9.oread) return s.fail(tag, e_bad_use);
            s.job = .{
                .kind = .write,
                .tag = tag,
                .fid = fid,
                .offset = offset,
                .count = @intCast(len),
                .msg = got.msg,
            };
        }

        fn clunk(s: *Self, tag: u16, fid: u32, kind: Kind) void {
            assert(kind == .clunk or kind == .remove);
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            if (s.fids[i].open or refs or (kind == .remove and features.remove)) {
                s.job = .{ .kind = kind, .tag = tag, .fid = fid };
                return;
            }
            s.releaseSlot(i);
            if (kind == .remove) s.fail(tag, e_perm) else s.emit(tag, .rclunk);
        }

        fn stat(s: *Self, tag: u16, fid: u32) void {
            if (s.findFid(fid) == null) return s.fail(tag, e_unknown_fid);
            s.job = .{ .kind = .stat, .tag = tag, .fid = fid };
        }

        fn wstat(s: *Self, got: Decoded, fid: u32, st: Stat) void {
            const tag = got.tag;
            const i = s.findFid(fid) orelse return s.fail(tag, e_unknown_fid);
            if (st.type != std.math.maxInt(u16) or st.dev != std.math.maxInt(u32) or
                st.qid.type != std.math.maxInt(u8) or st.qid.version != std.math.maxInt(u32) or
                st.qid.path != std.math.maxInt(u64) or st.atime != std.math.maxInt(u32) or
                st.uid.len != 0 or st.gid.len != 0 or st.muid.len != 0)
                return s.fail(tag, e_wstat);
            if (!features.wstat) {
                if (st.mode != std.math.maxInt(u32) or
                    // Linux v9fs follows O_TRUNC with Twstat(length=0, mtime=now).
                    // Accept that timestamp hint with truncation; a control
                    // filesystem does not persist caller-selected timestamps.
                    (st.mtime != std.math.maxInt(u32) and st.length != 0) or st.name.len != 0)
                    return s.fail(tag, e_wstat);
                if (st.length == std.math.maxInt(u64)) {
                    s.emit(tag, .rwstat);
                    return;
                }
                if (st.length != 0) return s.fail(tag, e_trunc_only);
                s.job = .{ .kind = .wstat, .tag = tag, .fid = fid, .set = .{ .length = true } };
                return;
            }
            const f = &s.fids[i];
            var set: Set = .{};
            if (st.name.len != 0) {
                if (!legalName(st.name) or (name_capacity != 0 and st.name.len > name_capacity)) return s.fail(tag, e_illegal_name);
                set.name = true;
            }
            if (st.mode != std.math.maxInt(u32)) {
                if ((st.mode & dmdir != 0) != f.dir) return s.fail(tag, e_wstat);
                set.mode = true;
            }
            if (st.mtime != std.math.maxInt(u32)) set.mtime = true;
            if (st.length != std.math.maxInt(u64)) {
                if (f.dir) return s.fail(tag, e_wstat);
                set.length = true;
            }
            if (!set.any()) {
                s.emit(tag, .rwstat);
                return;
            }
            s.job = .{
                .kind = .wstat,
                .tag = tag,
                .fid = fid,
                .set = set,
                .cperm = st.mode,
                .mtime = st.mtime,
                .length = st.length,
                .msg = got.msg,
            };
        }

        fn flush(s: *Self, tag: u16, oldtag: u16) void {
            if (s.findTag(oldtag)) |i| {
                s.fail(s.slots[i].tag, e_interrupted);
                s.slots[i] = .{};
            }
            s.emit(tag, .rflush);
        }

        fn ask(s: *Self, req: Backend.Req) Backend.Req {
            assert(req.tag != 0);
            s.job.req = req;
            s.job.req_tag = req.tag;
            return req;
        }

        fn jobFid(s: *Self) ?*Fid {
            const i = s.findFid(s.job.fid) orelse {
                s.fail(s.job.tag, e_unknown_fid);
                s.finishJob();
                return null;
            };
            return &s.fids[i];
        }

        fn stepJob(s: *Self) ?Backend.Req {
            const j = &s.job;
            assert(j.kind != .none);
            assert(j.req_tag == 0);
            if (refs and j.forget != 0) {
                const node = j.forget;
                j.forget = 0;
                j.forgetting = true;
                return s.ask(.{ .tag = s.tick(), .op = .release, .node = node });
            }
            if (j.closing) {
                s.finishJob();
                return null;
            }
            switch (j.kind) {
                .none => unreachable,
                .attach => return s.ask(.{ .tag = s.tick(), .op = .getattr, .node = s.root }),
                .walk => return s.stepWalk(),
                .open => {
                    const f = s.jobFid() orelse return null;
                    if (j.step == 0 and j.omode & c9.otrunc != 0) return s.ask(.{
                        .tag = s.tick(),
                        .op = .setattr,
                        .node = f.node,
                        .truncate = true,
                    });
                    return s.ask(.{ .tag = s.tick(), .op = .open, .node = f.node, .omode = j.omode });
                },
                .create => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .open,
                        .node = f.node,
                        .data = j.msg.tcreate.name,
                        .create = true,
                        .perm = j.cperm,
                        .omode = j.omode,
                    });
                },
                .read => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .read,
                        .node = f.node,
                        .handle = f.handle,
                        .off = j.offset,
                        .size = j.count,
                    });
                },
                .readdir => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .readdir,
                        .node = f.node,
                        .handle = f.handle,
                        .off = f.dirindex,
                        .size = j.count,
                    });
                },
                .write => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .write,
                        .node = f.node,
                        .handle = f.handle,
                        .off = j.offset,
                        .size = j.count,
                        .data = j.msg.twrite.data,
                    });
                },
                .clunk, .remove => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .release,
                        .node = f.node,
                        .handle = f.handle,
                        .opened = f.open,
                        .remove = features.remove and (j.kind == .remove or (f.open and f.rclose)),
                    });
                },
                .stat => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{ .tag = s.tick(), .op = .getattr, .node = f.node });
                },
                .wstat => {
                    const f = s.jobFid() orelse return null;
                    return s.ask(.{
                        .tag = s.tick(),
                        .op = .setattr,
                        .node = f.node,
                        .truncate = j.set.length and j.length == 0,
                        .set = if (features.wstat) j.set else .{},
                        .data = if (j.set.name) j.msg.twstat.stat.name else &.{},
                        .perm = j.cperm,
                        .mtime = j.mtime,
                        .length = j.length,
                    });
                },
            }
        }

        fn stepWalk(s: *Self) ?Backend.Req {
            const j = &s.job;
            if (j.clone) {
                assert(refs);
                if (j.step == 0) return s.ask(.{ .tag = s.tick(), .op = .lookup, .node = j.node, .data = "." });
            }
            while (j.step < j.nwname) {
                const name = j.msg.twalk.wname[j.step];
                if (name_capacity != 0 and name.len > name_capacity) {
                    s.stopWalk(e_illegal_name);
                    return null;
                }
                if (!refs and std.mem.eql(u8, name, ".")) {
                    j.wqid[j.nwqid] = j.qid;
                    j.nwqid += 1;
                    j.step += 1;
                    continue;
                }
                setName(&j.name, &j.name_len, name);
                return s.ask(.{ .tag = s.tick(), .op = .lookup, .node = j.node, .data = name });
            }
            var old: u64 = 0;
            const dst = pick: {
                if (j.newfid == j.fid) {
                    const i = s.findFid(j.fid) orelse {
                        s.stopWalk(e_unknown_fid);
                        return null;
                    };
                    old = s.fids[i].node;
                    break :pick i;
                }
                break :pick s.takeFid() orelse {
                    s.stopWalk(e_too_many_fids);
                    return null;
                };
            };
            s.fids[dst] = .{
                .used = true,
                .fid = j.newfid,
                .node = j.node,
                .dir = j.dir,
                .perm = j.perm,
                .qid = j.qid,
                .name = j.name,
                .name_len = j.name_len,
            };
            if (j.newfid != j.fid) s.bindFid(dst);
            s.emit(j.tag, .{ .rwalk = .{ .nwqid = j.nwqid, .wqid = j.wqid } });
            if (refs and old != 0) {
                j.forget = old;
                j.closing = true;
                return null;
            }
            s.finishJob();
            return null;
        }

        /// Ends a walk with a short Rwalk or, with nothing walked, an Rerror;
        /// a reference the walk still holds is released first.
        fn stopWalk(s: *Self, ename: []const u8) void {
            const j = &s.job;
            if (j.nwqid == 0)
                s.fail(j.tag, ename)
            else
                s.emit(j.tag, .{ .rwalk = .{ .nwqid = j.nwqid, .wqid = j.wqid } });
            if (refs and j.held) {
                j.forget = j.node;
                j.held = false;
                j.closing = true;
                return;
            }
            s.finishJob();
        }

        fn finishJob(s: *Self) void {
            s.job = .{};
            if (s.protocol.frame != 0) s.dropFrame();
        }

        fn jobReply(s: *Self, r: *const Backend.Reply, bytes: []const u8) void {
            const j = &s.job;
            assert(j.kind != .none);
            assert(j.req_tag == r.tag);
            j.req_tag = 0;

            if (j.forgetting) {
                j.forgetting = false;
                return;
            }
            // Before a clunk lets its fid go: a parked release keeps the fid
            // until the release is really paid.
            if (r.status == .again) return s.parkJob();
            if (j.kind == .clunk or j.kind == .remove) {
                s.dropFid(j.fid);
                if (j.kind == .clunk)
                    s.emit(j.tag, .rclunk)
                else if (!features.remove)
                    s.fail(j.tag, e_perm)
                else if (r.status == .err)
                    s.failReply(j.tag, r)
                else
                    s.emit(j.tag, .rremove);
                s.finishJob();
                return;
            }
            if (r.status == .err) {
                if (j.kind == .walk) return s.stopWalk(if (r.ename.len != 0) r.ename else errString(r.errno));
                s.failReply(j.tag, r);
                s.finishJob();
                return;
            }

            switch (j.kind) {
                .none, .clunk, .remove => unreachable,
                .attach => {
                    const i = s.takeFid() orelse {
                        s.fail(j.tag, e_too_many_fids);
                        s.finishJob();
                        return;
                    };
                    const node = if (r.attr.node != 0) r.attr.node else s.root;
                    s.fids[i] = .{
                        .used = true,
                        .fid = j.fid,
                        .node = node,
                        .dir = r.attr.dir,
                        .perm = r.attr.mode,
                        .qid = qidFrom(node, r.attr),
                    };
                    setName(&s.fids[i].name, &s.fids[i].name_len, "/");
                    s.bindFid(i);
                    s.emit(j.tag, .{ .rattach = .{ .qid = s.fids[i].qid } });
                    s.finishJob();
                },
                .walk => {
                    if (refs and j.held) j.forget = j.node;
                    if (r.attr.node != 0) j.node = r.attr.node;
                    if (r.attr.name.len != 0) setName(&j.name, &j.name_len, r.attr.name);
                    j.dir = r.attr.dir;
                    j.perm = r.attr.mode;
                    j.qid = qidFrom(j.node, r.attr);
                    j.held = refs;
                    if (!j.clone) {
                        j.wqid[j.nwqid] = j.qid;
                        j.nwqid += 1;
                    }
                    j.step += 1;
                },
                .open => {
                    if (j.step == 0 and j.omode & c9.otrunc != 0) {
                        j.step = 1;
                        return;
                    }
                    const f = s.jobFid() orelse return;
                    if (r.attr.node != 0) {
                        f.node = r.attr.node;
                        f.qid = qidFrom(f.node, r.attr);
                    }
                    f.open = true;
                    f.omode = j.omode;
                    f.rclose = j.omode & c9.orclose != 0;
                    f.handle = r.handle;
                    f.diroff = 0;
                    f.dirindex = 0;
                    s.emit(j.tag, .{ .ropen = .{
                        .qid = f.qid,
                        .iounit = s.protocol.msize - iohdrsz,
                    } });
                    s.finishJob();
                },
                .create => {
                    const f = s.jobFid() orelse return;
                    if (r.attr.node == 0) {
                        s.fail(j.tag, e_botch);
                        s.finishJob();
                        return;
                    }
                    const old = f.node;
                    f.node = r.attr.node;
                    f.dir = r.attr.dir;
                    f.perm = r.attr.mode;
                    f.qid = qidFrom(f.node, r.attr);
                    setName(&f.name, &f.name_len, j.msg.tcreate.name);
                    f.open = true;
                    f.omode = j.omode;
                    f.rclose = j.omode & c9.orclose != 0;
                    f.handle = r.handle;
                    f.diroff = 0;
                    f.dirindex = 0;
                    s.emit(j.tag, .{ .rcreate = .{
                        .qid = f.qid,
                        .iounit = s.protocol.msize - iohdrsz,
                    } });
                    if (refs) {
                        j.forget = old;
                        j.closing = true;
                        return;
                    }
                    s.finishJob();
                },
                .read => {
                    s.emit(j.tag, .{ .rread = .{ .data = bytes[0..@min(bytes.len, j.count)] } });
                    s.finishJob();
                },
                .readdir => {
                    s.emitDirRead(j.tag, j.fid, bytes, j.count);
                    s.finishJob();
                },
                .write => {
                    s.emit(j.tag, .{ .rwrite = .{ .count = @min(r.written, j.count) } });
                    s.finishJob();
                },
                .stat => {
                    const f = s.jobFid() orelse return;
                    f.perm = r.attr.mode;
                    f.dir = r.attr.dir;
                    f.qid = qidFrom(if (r.attr.node != 0) r.attr.node else f.node, r.attr);
                    const response: Msg = .{ .rstat = .{ .stat = s.statOf(f, r.attr) } };
                    if ((wire.encodedLen(response) catch unreachable) > s.protocol.msize)
                        s.fail(j.tag, e_small_msize)
                    else
                        s.emit(j.tag, response);
                    s.finishJob();
                },
                .wstat => {
                    const f = s.jobFid() orelse return;
                    if (r.attr.node != 0) {
                        f.perm = r.attr.mode;
                        f.dir = r.attr.dir;
                        f.qid = qidFrom(r.attr.node, r.attr);
                    }
                    if (j.set.name) setName(&f.name, &f.name_len, j.msg.twstat.stat.name);
                    s.emit(j.tag, .rwstat);
                    s.finishJob();
                },
            }
        }

        fn parkJob(s: *Self) void {
            const j = &s.job;
            // A wstat parks only as the truncation to zero a Linux client
            // sends for O_TRUNC: a rename's name is in the frame, and a mode
            // or mtime would need keeping.
            const parkable = switch (j.kind) {
                .read, .readdir, .write, .open, .clunk, .remove => true,
                .wstat => j.set.length and j.length == 0 and !j.set.name and !j.set.mode and !j.set.mtime,
                else => false,
            };
            if (!parkable) {
                s.fail(j.tag, e_again);
                s.finishJob();
                return;
            }
            const i = s.freeSlot() orelse {
                s.fail(j.tag, e_again);
                s.finishJob();
                return;
            };
            const sl = &s.slots[i];
            sl.* = .{
                .used = true,
                .parked = true,
                .retried = j.retried,
                .seq = s.tick(),
                .tag = j.tag,
                .kind = j.kind,
                .fid = j.fid,
                .count = j.count,
                .req = j.req,
                .omode = j.omode,
                .step = j.step,
            };
            if (j.req.data.len != 0) {
                if (j.req.data.len > park_data_max) {
                    sl.* = .{};
                    s.fail(j.tag, e_again);
                    s.finishJob();
                    return;
                }
                @memcpy(sl.data[0..j.req.data.len], j.req.data);
                sl.copied = true;
                sl.req.data = sl.data[0..j.req.data.len];
            }
            s.finishJob();
        }

        fn slotReply(s: *Self, i: usize, r: *const Backend.Reply, bytes: []const u8) void {
            const sl = &s.slots[i];
            if (r.status == .again) {
                sl.parked = true;
                return;
            }
            // A parked job is answered as a job. One that cannot become the
            // job right now stays parked; the retry asks it again.
            if (sl.holdsJob()) {
                if (s.job.kind != .none) {
                    sl.parked = true;
                    return;
                }
                _ = s.resumeJob(i);
                return s.jobReply(r, bytes);
            }
            if (r.status == .err) {
                s.failReply(sl.tag, r);
                sl.* = .{};
                return;
            }
            switch (sl.kind) {
                .read => s.emit(sl.tag, .{ .rread = .{ .data = bytes[0..@min(bytes.len, sl.count)] } }),
                .readdir => s.emitDirRead(sl.tag, sl.fid, bytes, sl.count),
                .write => s.emit(sl.tag, .{ .rwrite = .{ .count = @min(r.written, sl.count) } }),
                else => s.fail(sl.tag, e_botch),
            }
            sl.* = .{};
        }

        /// A readdir answers records of `node:u64le dir:u8 len:u8 name`; the
        /// engine encodes whole Stat entries into the output frame directly.
        fn emitDirRead(s: *Self, tag: u16, fid: u32, staging: []const u8, count: u32) void {
            const buf = s.protocol.out[s.protocol.out_len..];
            assert(buf.len > header_len + 4);
            const cap = @min(@as(usize, count), buf.len - header_len - 4);
            const who = s.uname[0..s.uname_len];
            var n: usize = header_len + 4;
            var entries: u32 = 0;
            var i: usize = 0;
            while (i + 10 <= staging.len) {
                const nlen: usize = staging[i + 9];
                if (i + 10 + nlen > staging.len) break;
                const dir = staging[i + 8] != 0;
                const rec: Stat = .{
                    .type = 0,
                    .dev = 0,
                    .qid = qidFrom(std.mem.readInt(u64, staging[i..][0..8], .little), .{ .dir = dir }),
                    .mode = (if (dir) dmdir else 0) | @as(u32, if (dir) dirent_dir_perm else dirent_file_perm),
                    .atime = 0,
                    .mtime = 0,
                    .length = 0,
                    .name = staging[i + 10 ..][0..nlen],
                    .uid = who,
                    .gid = who,
                    .muid = who,
                };
                const size = @as(usize, rec.size() catch break) + 2;
                if (n - header_len - 4 + size > cap) break;
                _ = rec.encode(buf[n..]) catch break;
                n += size;
                entries += 1;
                i += 10 + nlen;
            }
            if (entries == 0 and staging.len != 0) return s.fail(tag, e_count_small);
            const payload: u32 = @intCast(n - header_len - 4);
            comptime assert(header_len == 7);
            s.emit(tag, .{ .rread = .{ .data = buf[header_len + 4 .. n] } });
            if (s.findFid(fid)) |k| {
                s.fids[k].diroff += payload;
                s.fids[k].dirindex += entries;
            }
        }

        fn statOf(s: *const Self, f: *const Fid, a: Attr) Stat {
            const who = s.uname[0..s.uname_len];
            return .{
                .type = 0,
                .dev = 0,
                .qid = qidFrom(if (a.node != 0) a.node else f.node, a),
                .mode = (if (a.dir) dmdir else 0) | (if (a.append) dmappend else 0) | (if (a.excl) dmexcl else 0) | @as(u32, a.mode),
                .atime = a.atime,
                .mtime = a.mtime,
                .length = a.size,
                .name = if (name_capacity == 0) a.name else f.name[0..f.name_len],
                .uid = who,
                .gid = who,
                .muid = who,
            };
        }
    };
}

// ---- tests: a stub backend, the engine, and the client against it ----

const oread = c9.oread;
const owrite = c9.owrite;
const ordwr = c9.ordwr;
const oexec = c9.oexec;
const otrunc = c9.otrunc;
const orclose = c9.orclose;
const encode = wire.encode;
const decode = wire.decode;
const frameLen = wire.frameLen;
const Client = c9.Client;
const max_tags = c9.max_tags;

const req_type = Req;
const reply_type = Reply;

const StubFs = struct {
    pub const Req = req_type;
    pub const Reply = reply_type;

    const Entry = struct { node: u64, parent: u64, name: []const u8, dir: bool, mode: u16 };

    const tree = [_]Entry{
        .{ .node = 1, .parent = 1, .name = "/", .dir = true, .mode = 0o500 },
        .{ .node = 2, .parent = 1, .name = "index", .dir = false, .mode = 0o400 },
        .{ .node = 3, .parent = 1, .name = "cons", .dir = false, .mode = 0o200 },
        .{ .node = 4, .parent = 1, .name = "new", .dir = true, .mode = 0o500 },
        .{ .node = 16, .parent = 1, .name = "1", .dir = true, .mode = 0o500 },
        .{ .node = 32, .parent = 1, .name = "2", .dir = true, .mode = 0o500 },
        .{ .node = 17, .parent = 16, .name = "addr", .dir = false, .mode = 0o600 },
        .{ .node = 18, .parent = 16, .name = "body", .dir = false, .mode = 0o600 },
        .{ .node = 19, .parent = 16, .name = "ctl", .dir = false, .mode = 0o600 },
        .{ .node = 21, .parent = 16, .name = "errors", .dir = false, .mode = 0o200 },
        .{ .node = 22, .parent = 16, .name = "event", .dir = false, .mode = 0o600 },
        .{ .node = 23, .parent = 16, .name = "tag", .dir = false, .mode = 0o600 },
    };

    const body_node = 18;
    const index_node = 2;
    const event_node = 22;

    body: []const u8 = "hello, body\n",
    filler: [1024]u8 = @splat('x'),
    event: ?[]const u8 = null,
    park_writes: bool = false,
    park_opens: bool = false,
    park_setattr: bool = false,
    park_releases: bool = false,
    park_lookups: bool = false,
    releases: u32 = 0,
    calls: u32 = 0,
    writes: [128]u8 = undefined,
    writes_len: usize = 0,
    stage: [1024]u8 = undefined,

    const Answer = struct { reply: reply_type, bytes: []const u8 = "" };

    fn find(node: u64) ?usize {
        for (tree, 0..) |e, i| if (e.node == node) return i;
        return null;
    }

    fn sizeOf(st: *const StubFs, node: u64) u64 {
        return switch (node) {
            body_node => st.body.len,
            index_node => st.filler.len,
            else => 0,
        };
    }

    fn contentOf(st: *const StubFs, node: u64) []const u8 {
        return switch (node) {
            body_node => st.body,
            index_node => &st.filler,
            else => "",
        };
    }

    fn attrOf(st: *const StubFs, e: Entry) Attr {
        return .{ .name = e.name, .node = e.node, .dir = e.dir, .mode = e.mode, .size = st.sizeOf(e.node) };
    }

    fn stageDir(st: *StubFs, node: u64, skip: u64) []const u8 {
        var n: usize = 0;
        var seen: u64 = 0;
        for (tree) |e| {
            if (e.parent != node or e.node == node) continue;
            if (seen < skip) {
                seen += 1;
                continue;
            }
            std.mem.writeInt(u64, st.stage[n..][0..8], e.node, .little);
            st.stage[n + 8] = @intFromBool(e.dir);
            st.stage[n + 9] = @intCast(e.name.len);
            @memcpy(st.stage[n + 10 ..][0..e.name.len], e.name);
            n += 10 + e.name.len;
        }
        return st.stage[0..n];
    }

    fn handle(st: *StubFs, req: req_type) Answer {
        st.calls += 1;
        const fail: Answer = .{ .reply = .{ .tag = req.tag, .status = .err, .errno = E.NOENT } };
        const i = find(req.node) orelse return fail;
        switch (req.op) {
            .lookup => {
                if (st.park_lookups) return .{ .reply = .{ .tag = req.tag, .status = .again } };
                if (std.mem.eql(u8, req.data, ".."))
                    return .{ .reply = .{ .tag = req.tag, .attr = st.attrOf(tree[find(tree[i].parent).?]) } };
                for (tree) |e| {
                    if (e.parent != req.node or e.node == req.node) continue;
                    if (!std.mem.eql(u8, e.name, req.data)) continue;
                    return .{ .reply = .{ .tag = req.tag, .attr = st.attrOf(e) } };
                }
                return fail;
            },
            .getattr => return .{ .reply = .{ .tag = req.tag, .attr = st.attrOf(tree[i]) } },
            .setattr => {
                if (st.park_setattr) return .{ .reply = .{ .tag = req.tag, .status = .again } };
                if (req.truncate and req.node == body_node) st.body = "";
                return .{ .reply = .{ .tag = req.tag, .attr = st.attrOf(tree[i]) } };
            },
            .open => {
                if (st.park_opens) return .{ .reply = .{ .tag = req.tag, .status = .again } };
                return .{ .reply = .{ .tag = req.tag, .handle = 7 } };
            },
            .release => {
                if (st.park_releases) return .{ .reply = .{ .tag = req.tag, .status = .again } };
                st.releases += 1;
                return .{ .reply = .{ .tag = req.tag } };
            },
            .readdir => {
                if (!tree[i].dir) return .{ .reply = .{ .tag = req.tag, .status = .err, .errno = E.NOTDIR } };
                return .{ .reply = .{ .tag = req.tag }, .bytes = st.stageDir(req.node, req.off) };
            },
            .read => {
                if (req.node == event_node) {
                    const rec = st.event orelse return .{ .reply = .{ .tag = req.tag, .status = .again } };
                    st.event = null;
                    return .{ .reply = .{ .tag = req.tag }, .bytes = rec };
                }
                const all = st.contentOf(req.node);
                if (req.off >= all.len) return .{ .reply = .{ .tag = req.tag } };
                const from = all[@intCast(req.off)..];
                return .{ .reply = .{ .tag = req.tag }, .bytes = from[0..@min(from.len, req.size)] };
            },
            .write => {
                if (st.park_writes) return .{ .reply = .{ .tag = req.tag, .status = .again } };
                const n = @min(req.data.len, st.writes.len - st.writes_len);
                @memcpy(st.writes[st.writes_len..][0..n], req.data[0..n]);
                st.writes_len += n;
                return .{ .reply = .{ .tag = req.tag, .written = @intCast(n) } };
            },
        }
    }
};

const Srv = Server(StubFs, .{});

const Harness = struct {
    in: [4096]u8 = undefined,
    out: [8192]u8 = undefined,
    fsys: StubFs = .{},
    srv: Srv = undefined,

    fn start(h: *Harness) void {
        h.srv = Srv.init(.{ .in = &h.in, .out = &h.out, .root = 1 });
    }

    fn answer(h: *Harness, req: Req) void {
        const a = h.fsys.handle(req);
        h.srv.reply(&a.reply, a.bytes);
    }

    fn pump(h: *Harness) void {
        while (h.srv.retry()) |req| h.answer(req);
        while (h.srv.next()) |req| h.answer(req);
    }

    fn send(h: *Harness, tag: u16, msg: Msg) !void {
        var buf: [1024]u8 = undefined;
        const bytes = try encode(msg, tag, &buf);
        try testing.expectEqual(bytes.len, h.srv.push(bytes));
        h.pump();
    }

    fn reap(h: *Harness) !Decoded {
        const out = h.srv.output();
        const len = frameLen(out) orelse return error.NoReply;
        if (len > out.len) return error.ShortReply;
        const got = try decode(out[0..len]);
        h.srv.wrote(len);
        return got;
    }

    fn quiet(h: *Harness) !void {
        try testing.expectEqual(@as(usize, 0), h.srv.output().len);
    }

    fn handshake(h: *Harness, msize: u32) !void {
        h.start();
        try h.send(notag, .{ .tversion = .{ .msize = msize, .version = "9P2000" } });
        const v = try h.reap();
        try testing.expectEqualStrings("9P2000", v.msg.rversion.version);
        try h.send(0, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
        const a = try h.reap();
        try testing.expectEqual(@as(u64, 1), a.msg.rattach.qid.path);
    }

    fn walkTo(h: *Harness, tag: u16, newfid: u32, list: []const []const u8) !Decoded {
        try h.send(tag, .{ .twalk = .{
            .fid = 0,
            .newfid = newfid,
            .nwname = @intCast(list.len),
            .wname = wnames(list),
        } });
        return h.reap();
    }
};

fn wnames(list: []const []const u8) [max_welem][]const u8 {
    var out: [max_welem][]const u8 = @splat("");
    for (list, 0..) |n, i| out[i] = n;
    return out;
}

fn dirNames(data: []const u8, out: [][]const u8) !usize {
    var n: usize = 0;
    var i: usize = 0;
    while (i < data.len) {
        const size = std.mem.readInt(u16, data[i..][0..2], .little);
        const st = try Stat.decode(data[i..][0 .. @as(usize, size) + 2]);
        out[n] = st.name;
        n += 1;
        i += @as(usize, size) + 2;
    }
    return n;
}

test "fs server: the version handshake clamps, falls back, and refuses" {
    var h: Harness = .{};
    h.start();

    try h.send(notag, .{ .tversion = .{ .msize = 1 << 20, .version = "9P2000" } });
    var got = try h.reap();
    try testing.expectEqual(notag, got.tag);
    try testing.expectEqual(@as(u32, 4096), got.msg.rversion.msize);
    try testing.expectEqualStrings("9P2000", got.msg.rversion.version);

    try h.send(notag, .{ .tversion = .{ .msize = 512, .version = "9P2000" } });
    got = try h.reap();
    try testing.expectEqual(@as(u32, 512), got.msg.rversion.msize);

    try h.send(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000.u" } });
    got = try h.reap();
    try testing.expectEqualStrings("9P2000", got.msg.rversion.version);

    try h.send(notag, .{ .tversion = .{ .msize = 4096, .version = "TCP/IP" } });
    got = try h.reap();
    try testing.expectEqualStrings("unknown", got.msg.rversion.version);
    try h.send(1, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
    try testing.expect(h.srv.protocol.dead);
    h.start();
    try h.send(notag, .{ .tversion = .{ .msize = 64, .version = "9P2000" } });
    try testing.expect(h.srv.protocol.dead);
    try testing.expectEqual(@as(u32, 216), msize_min - 1);
}

test "fs server: attach names the root, and the only tree there is" {
    var h: Harness = .{};
    h.start();
    try h.send(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000" } });
    _ = try h.reap();

    try h.send(1, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "work" } });
    var got = try h.reap();
    try testing.expectEqualStrings(e_no_tree, got.msg.rerror.ename);

    try h.send(2, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
    got = try h.reap();
    try testing.expectEqual(@as(u64, 1), got.msg.rattach.qid.path);
    try testing.expectEqual(qtdir, got.msg.rattach.qid.type);
    try testing.expectEqual(@as(u32, 0), got.msg.rattach.qid.version);

    try h.send(3, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
    got = try h.reap();
    try testing.expectEqualStrings(e_fid_in_use, got.msg.rerror.ename);

    try h.send(4, .{ .tauth = .{ .afid = 1, .uname = "goblin", .aname = "" } });
    got = try h.reap();
    try testing.expectEqualStrings(e_no_auth, got.msg.rerror.ename);

    try h.send(5, .{ .tstat = .{ .fid = 0 } });
    got = try h.reap();
    try testing.expectEqualStrings("/", got.msg.rstat.stat.name);
    try testing.expectEqualStrings("goblin", got.msg.rstat.stat.uid);
    try testing.expectEqualStrings("goblin", got.msg.rstat.stat.muid);
    try testing.expect(got.msg.rstat.stat.mode & dmdir != 0);
}

test "fs server: a three-element walk, and `..` with no kernel to resolve it" {
    var h: Harness = .{};
    try h.handshake(4096);

    var got = try h.walkTo(5, 1, &.{ "..", "1", "body" });
    try testing.expectEqual(@as(u16, 3), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u64, 1), got.msg.rwalk.wqid[0].path);
    try testing.expectEqual(@as(u64, 16), got.msg.rwalk.wqid[1].path);
    try testing.expectEqual(@as(u64, 18), got.msg.rwalk.wqid[2].path);
    try testing.expectEqual(qtdir, got.msg.rwalk.wqid[1].type);
    try testing.expectEqual(qtfile, got.msg.rwalk.wqid[2].type);
    for (got.msg.rwalk.wqid[0..3]) |q| try testing.expectEqual(@as(u32, 0), q.version);

    got = try h.walkTo(6, 2, &.{ "..", "1", "..", "1", "body" });
    try testing.expectEqual(@as(u16, 5), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u64, 1), got.msg.rwalk.wqid[2].path);
    try testing.expectEqual(@as(u64, 18), got.msg.rwalk.wqid[4].path);
    try h.send(7, .{ .tstat = .{ .fid = 2 } });
    got = try h.reap();
    try testing.expectEqualStrings("body", got.msg.rstat.stat.name);
    try testing.expectEqual(@as(u64, 12), got.msg.rstat.stat.length);

    got = try h.walkTo(8, 3, &.{ "1", "body", ".." });
    try testing.expectEqual(@as(u16, 3), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u64, 16), got.msg.rwalk.wqid[2].path);
    try testing.expectEqual(qtdir, got.msg.rwalk.wqid[2].type);
    try h.send(9, .{ .tstat = .{ .fid = 3 } });
    got = try h.reap();
    try testing.expectEqualStrings("1", got.msg.rstat.stat.name);

    const before = h.fsys.calls;
    got = try h.walkTo(10, 4, &.{ ".", "." });
    try testing.expectEqual(@as(u16, 2), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u64, 1), got.msg.rwalk.wqid[1].path);
    try testing.expectEqual(before, h.fsys.calls);
}

test "fs server: a walk failing on the first element is Rerror, on the second a short Rwalk" {
    var h: Harness = .{};
    try h.handshake(4096);

    var got = try h.walkTo(5, 1, &.{ "nope", "body" });
    try testing.expectEqualStrings("No such file or directory", got.msg.rerror.ename);

    got = try h.walkTo(6, 1, &.{ "1", "nope" });
    try testing.expectEqual(@as(u16, 1), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u64, 16), got.msg.rwalk.wqid[0].path);

    try h.send(7, .{ .tstat = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);

    try h.send(8, .{ .twalk = .{ .fid = 0, .newfid = 1, .nwname = 0 } });
    got = try h.reap();
    try testing.expectEqual(@as(u16, 0), got.msg.rwalk.nwqid);
    try h.send(9, .{ .tstat = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqualStrings("/", got.msg.rstat.stat.name);

    got = try h.walkTo(10, 2, &.{"index"});
    try testing.expectEqual(@as(u16, 1), got.msg.rwalk.nwqid);
    try h.send(11, .{ .twalk = .{ .fid = 2, .newfid = 3, .nwname = 1, .wname = wnames(&.{"body"}) } });
    got = try h.reap();
    try testing.expectEqualStrings(e_not_dir, got.msg.rerror.ename);

    got = try h.walkTo(12, 4, &.{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"});
    try testing.expectEqualStrings(e_illegal_name, got.msg.rerror.ename);

    try h.send(13, .{ .twalk = .{ .fid = 0, .newfid = 1, .nwname = 1, .wname = wnames(&.{"1"}) } });
    got = try h.reap();
    try testing.expectEqualStrings(e_fid_in_use, got.msg.rerror.ename);
}

test "fs server: backend-sized filenames survive walk and stat within negotiated msize" {
    const Native = Server(StubFs, .{ .fid_capacity = 2, .name_capacity = 255 });
    try testing.expectEqual(@as(usize, 28), @sizeOf(@FieldType(Srv.Fid, "name")));
    try testing.expectEqual(@as(usize, 255), @sizeOf(@FieldType(Native.Fid, "name")));

    const filename: [255]u8 = @splat('f');
    for ([_]struct { length: usize, msize: u32 }{
        .{ .length = 29, .msize = 512 },
        .{ .length = 128, .msize = 512 },
        .{ .length = 255, .msize = 512 },
        .{ .length = 200, .msize = 256 },
    }) |case| {
        var in: [1024]u8 = undefined;
        var out: [2048]u8 = undefined;
        var encoded: [1024]u8 = undefined;
        var server = Native.init(.{ .in = &in, .out = &out, .root = 1 });
        server.protocol.msize = case.msize;
        server.setUname("u" ** Native.options.username_capacity);
        server.fids[0] = .{ .used = true, .fid = 0, .node = 1, .dir = true, .perm = 0o500 };
        const name = filename[0..case.length];
        const walk = try encode(.{ .twalk = .{
            .fid = 0,
            .newfid = 1,
            .nwname = 1,
            .wname = wnames(&.{name}),
        } }, 1, &encoded);
        try testing.expectEqual(walk.len, server.push(walk));
        const lookup = server.next() orelse return error.MissingLookup;
        try testing.expectEqual(.lookup, lookup.op);
        try testing.expectEqualStrings(name, lookup.data);
        server.reply(&.{ .tag = lookup.tag, .attr = .{ .node = 2, .name = name, .size = 12 } }, "");
        try testing.expectEqual(null, server.next());
        var response = try decode(server.output());
        try testing.expectEqual(@as(u16, 1), response.msg.rwalk.nwqid);
        server.wrote(server.output().len);

        const stat = try encode(.{ .tstat = .{ .fid = 1 } }, 2, &encoded);
        try testing.expectEqual(stat.len, server.push(stat));
        const getattr = server.next() orelse return error.MissingGetattr;
        try testing.expectEqual(.getattr, getattr.op);
        server.reply(&.{ .tag = getattr.tag, .attr = .{ .node = 2, .name = name, .size = 12 } }, "");
        try testing.expect(server.output().len <= case.msize);
        response = try decode(server.output());
        if (case.msize == 256) {
            try testing.expectEqualStrings(e_small_msize, response.msg.rerror.ename);
        } else {
            try testing.expectEqualStrings(name, response.msg.rstat.stat.name);
            try testing.expectEqual(@as(u64, 12), response.msg.rstat.stat.length);
        }
        server.wrote(server.output().len);
        const clunk = try encode(.{ .tclunk = .{ .fid = 1 } }, 3, &encoded);
        try testing.expectEqual(clunk.len, server.push(clunk));
        try testing.expectEqual(null, server.next());
        response = try decode(server.output());
        try testing.expect(response.msg == .rclunk);
        try testing.expect(!server.protocol.dead);
    }
}

test "fs server: open then read then clunk, and the release a clunk owes the backend" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(5, 1, &.{ "1", "body" });

    try h.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    var got = try h.reap();
    try testing.expectEqual(@as(u64, 18), got.msg.ropen.qid.path);
    try testing.expectEqual(@as(u32, 4096 - iohdrsz), got.msg.ropen.iounit);

    try h.send(7, .{ .topen = .{ .fid = 1, .mode = oread } });
    got = try h.reap();
    try testing.expectEqualStrings(e_already_open, got.msg.rerror.ename);

    try h.send(8, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    got = try h.reap();
    try testing.expectEqualStrings("hello, body\n", got.msg.rread.data);

    try h.send(9, .{ .tread = .{ .fid = 1, .offset = 7, .count = 4096 } });
    got = try h.reap();
    try testing.expectEqualStrings("body\n", got.msg.rread.data);

    try h.send(10, .{ .tread = .{ .fid = 1, .offset = 99, .count = 16 } });
    got = try h.reap();
    try testing.expectEqual(@as(usize, 0), got.msg.rread.data.len);

    try testing.expectEqual(@as(u32, 0), h.fsys.releases);
    try h.send(11, .{ .tclunk = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expect(got.msg == .rclunk);
    try testing.expectEqual(@as(u32, 1), h.fsys.releases);

    try h.send(12, .{ .tread = .{ .fid = 1, .offset = 0, .count = 16 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);
    try h.send(13, .{ .tclunk = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);

    _ = try h.walkTo(14, 2, &.{"index"});
    try h.send(15, .{ .tclunk = .{ .fid = 2 } });
    got = try h.reap();
    try testing.expect(got.msg == .rclunk);
    try testing.expectEqual(@as(u32, 1), h.fsys.releases);
}

test "fs server: every Rread is clamped to the client's count and to the msize" {
    var h: Harness = .{};
    try h.handshake(512);
    _ = try h.walkTo(5, 1, &.{"index"});
    try h.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    _ = try h.reap();

    try h.send(7, .{ .tread = .{ .fid = 1, .offset = 0, .count = 5 } });
    var got = try h.reap();
    try testing.expectEqual(@as(usize, 5), got.msg.rread.data.len);

    try h.send(8, .{ .tread = .{ .fid = 1, .offset = 0, .count = 1 << 20 } });
    const out = h.srv.output();
    try testing.expectEqual(@as(?u32, 512), frameLen(out));
    got = try h.reap();
    try testing.expectEqual(@as(usize, 512 - header_len - 4), got.msg.rread.data.len);

    try h.send(9, .{ .tread = .{ .fid = 1, .offset = 0, .count = 1 << 20 } });
    got = try h.reap();
    try testing.expectEqual(@as(usize, 501), got.msg.rread.data.len);
}

test "fs server: a directory read is whole stat records at a cursor the client cannot invent" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(4, 1, &.{"index"});
    try h.send(5, .{ .topen = .{ .fid = 0, .mode = oread } });
    _ = try h.reap();

    var found: [8][]const u8 = undefined;

    try h.send(6, .{ .tread = .{ .fid = 0, .offset = 0, .count = 150 } });
    var got = try h.reap();
    const first = got.msg.rread.data.len;
    try testing.expectEqual(@as(usize, 2), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings("index", found[0]);
    try testing.expectEqualStrings("cons", found[1]);
    try testing.expect(first <= 150);

    try h.send(7, .{ .tread = .{ .fid = 0, .offset = first, .count = 150 } });
    got = try h.reap();
    const second = got.msg.rread.data.len;
    try testing.expectEqual(@as(usize, 2), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings("new", found[0]);
    try testing.expectEqualStrings("1", found[1]);

    try h.send(8, .{ .tread = .{ .fid = 0, .offset = first + second + 1, .count = 150 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_bad_offset, got.msg.rerror.ename);
    try h.send(9, .{ .tread = .{ .fid = 0, .offset = 3, .count = 150 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_bad_offset, got.msg.rerror.ename);

    try h.send(10, .{ .tread = .{ .fid = 0, .offset = first + second, .count = 150 } });
    got = try h.reap();
    try testing.expectEqual(@as(usize, 1), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings("2", found[0]);

    try h.send(11, .{ .tread = .{ .fid = 0, .offset = first + second + got.msg.rread.data.len, .count = 150 } });
    got = try h.reap();
    try testing.expectEqual(@as(usize, 0), got.msg.rread.data.len);

    try h.send(12, .{ .tread = .{ .fid = 0, .offset = 0, .count = 150 } });
    got = try h.reap();
    try testing.expectEqual(@as(usize, 2), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings("index", found[0]);

    try h.send(13, .{ .tread = .{ .fid = 0, .offset = 0, .count = 40 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_count_small, got.msg.rerror.ename);

    try h.send(14, .{ .tread = .{ .fid = 0, .offset = 0, .count = 150 } });
    got = try h.reap();
    const one = try Stat.decode(got.msg.rread.data[0 .. std.mem.readInt(u16, got.msg.rread.data[0..2], .little) + 2]);
    try testing.expectEqualStrings("index", one.name);
    try testing.expectEqual(@as(u32, dirent_file_perm), one.mode);
    try testing.expectEqual(@as(u64, 0), one.length);
    try testing.expectEqual(@as(u32, 0), one.qid.version);

    try h.send(16, .{ .tstat = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqual(@as(u32, 0o400), got.msg.rstat.stat.mode);
    try testing.expectEqual(@as(u64, 1024), got.msg.rstat.stat.length);
}

test "fs server: long directory names remain whole across pages" {
    var h: Harness = .{};
    try h.handshake(4096);
    var entries: [10 + 255 + 10 + 4]u8 = @splat(0);
    std.mem.writeInt(u64, entries[0..8], 41, .little);
    entries[9] = 255;
    @memset(entries[10..265], 'f');
    std.mem.writeInt(u64, entries[265..273], 42, .little);
    entries[274] = 4;
    @memcpy(entries[275..], "next");
    var found: [2][]const u8 = undefined;

    {
        var request: [64]u8 = undefined;
        const bytes = try encode(.{ .tread = .{ .fid = 0, .offset = 0, .count = 330 } }, 5, &request);
        _ = h.srv.protocol.push(bytes);
        _ = (try h.srv.protocol.receive()).?;
        h.srv.protocol.release();
    }
    h.srv.emitDirRead(5, 0, &entries, 330);
    var got = try h.reap();
    const first = got.msg.rread.data.len;
    try testing.expectEqual(@as(usize, 1), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings(entries[10..265], found[0]);
    try testing.expectEqual(@as(u64, 1), h.srv.fids[0].dirindex);

    {
        var request: [64]u8 = undefined;
        const bytes = try encode(.{ .tread = .{ .fid = 0, .offset = 0, .count = 330 } }, 6, &request);
        _ = h.srv.protocol.push(bytes);
        _ = (try h.srv.protocol.receive()).?;
        h.srv.protocol.release();
    }
    h.srv.emitDirRead(6, 0, entries[265..], 330);
    got = try h.reap();
    try testing.expectEqual(@as(usize, 1), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings("next", found[0]);
    try testing.expectEqual(@as(u64, 2), h.srv.fids[0].dirindex);
    try testing.expectEqual(first + got.msg.rread.data.len, h.srv.fids[0].diroff);

    {
        var request: [64]u8 = undefined;
        const bytes = try encode(.{ .tread = .{ .fid = 0, .offset = 0, .count = 4096 } }, 7, &request);
        _ = h.srv.protocol.push(bytes);
        _ = (try h.srv.protocol.receive()).?;
        h.srv.protocol.release();
    }
    h.srv.emitDirRead(7, 0, &entries, 4096);
    got = try h.reap();
    try testing.expectEqual(@as(usize, 2), try dirNames(got.msg.rread.data, &found));
    try testing.expectEqualStrings(entries[10..265], found[0]);
    try testing.expectEqualStrings("next", found[1]);
}

test "fs server: a blocked read parks, and the connection keeps working" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(5, 1, &.{ "1", "event" });
    try h.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    _ = try h.reap();

    try h.send(7, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    try h.quiet();

    h.pump();
    h.pump();
    try h.quiet();

    _ = try h.walkTo(8, 2, &.{ "1", "body" });
    try h.send(9, .{ .tstat = .{ .fid = 2 } });
    var got = try h.reap();
    try testing.expectEqualStrings("body", got.msg.rstat.stat.name);

    h.fsys.event = "Kli7 7 0 0 hello\n";
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 7), got.tag);
    try testing.expectEqualStrings("Kli7 7 0 0 hello\n", got.msg.rread.data);
    try h.quiet();

    _ = try h.walkTo(10, 3, &.{ "1", "ctl" });
    try h.send(11, .{ .topen = .{ .fid = 3, .mode = owrite } });
    _ = try h.reap();
    h.fsys.park_writes = true;
    try h.send(12, .{ .twrite = .{ .fid = 3, .offset = 0, .data = "clean\n" } });
    try h.quiet();
    try h.send(13, .{ .tstat = .{ .fid = 2 } });
    _ = try h.reap();
    h.fsys.park_writes = false;
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 12), got.tag);
    try testing.expectEqual(@as(u32, 6), got.msg.rwrite.count);
    try testing.expectEqualStrings("clean\n", h.fsys.writes[0..h.fsys.writes_len]);
    for (0..Srv.options.slot_capacity) |k| {
        try h.send(@intCast(100 + k), .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
        try h.quiet();
    }
    try h.send(200, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_again, got.msg.rerror.ename);
}

test "fs server: a parked open, truncate and clunk complete on retry, and a walk cannot park" {
    var h: Harness = .{};
    try h.handshake(4096);

    // An open the backend is not ready for: parked, and the connection keeps
    // answering everything else meanwhile.
    _ = try h.walkTo(5, 1, &.{ "1", "body" });
    h.fsys.park_opens = true;
    try h.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    try h.quiet();
    _ = try h.walkTo(7, 2, &.{ "1", "tag" });
    try h.send(8, .{ .tstat = .{ .fid = 2 } });
    var got = try h.reap();
    try testing.expectEqualStrings("tag", got.msg.rstat.stat.name);
    try h.quiet();
    h.fsys.park_opens = false;
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 6), got.tag);
    try testing.expect(got.msg == .ropen);
    try h.send(9, .{ .tread = .{ .fid = 1, .offset = 0, .count = 64 } });
    got = try h.reap();
    try testing.expectEqualStrings("hello, body\n", got.msg.rread.data);

    // A truncating open parks at its truncate step and resumes there: the
    // truncate still happens before the open.
    _ = try h.walkTo(10, 3, &.{ "1", "body" });
    h.fsys.park_setattr = true;
    try h.send(11, .{ .topen = .{ .fid = 3, .mode = owrite | c9.otrunc } });
    try h.quiet();
    try testing.expectEqualStrings("hello, body\n", h.fsys.body);
    h.fsys.park_setattr = false;
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 11), got.tag);
    try testing.expect(got.msg == .ropen);
    try testing.expectEqualStrings("", h.fsys.body);

    // A clunk of an open fid parks at its release and pays it on retry.
    const paid = h.fsys.releases;
    h.fsys.park_releases = true;
    try h.send(12, .{ .tclunk = .{ .fid = 1 } });
    try h.quiet();
    try testing.expectEqual(paid, h.fsys.releases);
    h.fsys.park_releases = false;
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 12), got.tag);
    try testing.expect(got.msg == .rclunk);
    try testing.expectEqual(paid + 1, h.fsys.releases);

    // A walk keeps its names in the input frame, which parking would let go
    // of, so it is refused rather than parked.
    h.fsys.park_lookups = true;
    try h.send(13, .{ .twalk = .{ .fid = 0, .newfid = 4, .nwname = 1, .wname = wnames(&.{"index"}) } });
    got = try h.reap();
    try testing.expectEqualStrings(e_again, got.msg.rerror.ename);
    h.fsys.park_lookups = false;

    // A parked open whose fid is clunked meanwhile is answered for the
    // clunk's sake and never asked again: the backend would otherwise open
    // a handle for nobody.
    _ = try h.walkTo(16, 5, &.{ "1", "tag" });
    h.fsys.park_opens = true;
    try h.send(17, .{ .topen = .{ .fid = 5, .mode = oread } });
    try h.quiet();
    try h.send(18, .{ .tclunk = .{ .fid = 5 } });
    got = try h.reap();
    try testing.expect(got.msg == .rclunk);
    h.fsys.park_opens = false;
    const asked = h.fsys.calls;
    h.pump();
    got = try h.reap();
    try testing.expectEqual(@as(u16, 17), got.tag);
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);
    try testing.expectEqual(asked, h.fsys.calls);

    // A flush reaches a parked job the way it reaches a parked read.
    h.fsys.park_opens = true;
    try h.send(14, .{ .topen = .{ .fid = 2, .mode = oread } });
    try h.quiet();
    try h.send(15, .{ .tflush = .{ .oldtag = 14 } });
    got = try h.reap();
    try testing.expectEqual(@as(u16, 14), got.tag);
    try testing.expectEqualStrings(e_interrupted, got.msg.rerror.ename);
    got = try h.reap();
    try testing.expect(got.msg == .rflush);
    h.fsys.park_opens = false;
    h.pump();
    try h.quiet();
}

test "fs server: the reply queue is a FIFO that survives a partial write" {
    var h: Harness = .{};
    try h.handshake(4096);

    try h.send(5, .{ .tstat = .{ .fid = 0 } });
    var saved: [256]u8 = undefined;
    const one = h.srv.output();
    const n = one.len;
    @memcpy(saved[0..n], one);
    h.srv.wrote(3);
    try testing.expectEqual(n - 3, h.srv.output().len);

    try h.send(6, .{ .tstat = .{ .fid = 0 } });
    const rest = h.srv.output();
    try testing.expectEqualSlices(u8, saved[3..n], rest[0 .. n - 3]);
    const tail = rest[n - 3 ..];
    const second = try decode(tail[0..frameLen(tail).?]);
    try testing.expectEqual(@as(u16, 6), second.tag);

    var flood: [8192]u8 = @splat(0);
    try testing.expectEqual(@as(usize, 4096), h.srv.push(&flood));
    h.pump();
    try testing.expect(h.srv.protocol.dead);
    try testing.expectEqual(@as(usize, 0), h.srv.push(&flood));
}

test "fs server: Tflush answers the original first and the Rflush second" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(5, 1, &.{ "1", "event" });
    try h.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    _ = try h.reap();
    try h.send(7, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    try h.quiet();

    try h.send(8, .{ .tflush = .{ .oldtag = 7 } });
    var got = try h.reap();
    try testing.expectEqual(@as(u16, 7), got.tag);
    try testing.expectEqualStrings(e_interrupted, got.msg.rerror.ename);
    got = try h.reap();
    try testing.expectEqual(@as(u16, 8), got.tag);
    try testing.expect(got.msg == .rflush);
    try h.quiet();

    h.fsys.event = "Kli7 7 0 0 hello\n";
    h.pump();
    try h.quiet();

    try h.send(9, .{ .tflush = .{ .oldtag = 99 } });
    got = try h.reap();
    try testing.expectEqual(@as(u16, 9), got.tag);
    try testing.expect(got.msg == .rflush);
    try h.quiet();
}

test "fs server: the fid and permission refusals, each in a string Linux knows" {
    var h: Harness = .{};
    try h.handshake(4096);

    for ([_]Msg{
        .{ .tread = .{ .fid = 99, .offset = 0, .count = 16 } },
        .{ .tstat = .{ .fid = 99 } },
        .{ .tclunk = .{ .fid = 99 } },
        .{ .topen = .{ .fid = 99, .mode = oread } },
        .{ .twalk = .{ .fid = 99, .newfid = 98, .nwname = 0 } },
    }, 20..) |msg, tag| {
        try h.send(@intCast(tag), msg);
        const got = try h.reap();
        try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);
    }

    _ = try h.walkTo(5, 1, &.{ "1", "body" });
    try h.send(6, .{ .tread = .{ .fid = 1, .offset = 0, .count = 16 } });
    var got = try h.reap();
    try testing.expectEqualStrings(e_bad_use, got.msg.rerror.ename);
    try h.send(7, .{ .topen = .{ .fid = 1, .mode = oread } });
    _ = try h.reap();
    try h.send(8, .{ .twrite = .{ .fid = 1, .offset = 0, .data = "x" } });
    got = try h.reap();
    try testing.expectEqualStrings(e_bad_use, got.msg.rerror.ename);

    try h.send(9, .{ .twalk = .{ .fid = 1, .newfid = 2, .nwname = 0 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_bad_use, got.msg.rerror.ename);

    _ = try h.walkTo(10, 3, &.{ "1", "errors" });
    try h.send(11, .{ .topen = .{ .fid = 3, .mode = oread } });
    got = try h.reap();
    try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);
    try h.send(12, .{ .topen = .{ .fid = 3, .mode = owrite } });
    got = try h.reap();
    try testing.expect(got.msg == .ropen);

    try h.send(13, .{ .topen = .{ .fid = 0, .mode = ordwr } });
    got = try h.reap();
    try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);
    _ = try h.walkTo(14, 4, &.{ "1", "tag" });
    for ([_]u8{ orclose, oexec, oread | orclose }, 30..) |mode, tag| {
        try h.send(@intCast(tag), .{ .topen = .{ .fid = 4, .mode = mode } });
        got = try h.reap();
        try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);
    }
}

test "fs server: Twstat with a zero length is the truncate, and so is OTRUNC" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(5, 1, &.{ "1", "body" });

    const sentinel: Stat = .{
        .type = std.math.maxInt(u16),
        .dev = std.math.maxInt(u32),
        .qid = .{ .type = 0xFF, .version = std.math.maxInt(u32), .path = std.math.maxInt(u64) },
        .mode = std.math.maxInt(u32),
        .atime = std.math.maxInt(u32),
        .mtime = std.math.maxInt(u32),
        .length = std.math.maxInt(u64),
        .name = "",
        .uid = "",
        .gid = "",
        .muid = "",
    };

    try h.send(6, .{ .twstat = .{ .fid = 1, .stat = sentinel } });
    var got = try h.reap();
    try testing.expect(got.msg == .rwstat);
    try testing.expectEqualStrings("hello, body\n", h.fsys.body);

    var five = sentinel;
    five.length = 5;
    try h.send(7, .{ .twstat = .{ .fid = 1, .stat = five } });
    got = try h.reap();
    try testing.expectEqualStrings(e_trunc_only, got.msg.rerror.ename);

    var renamed = sentinel;
    renamed.name = "other";
    try h.send(8, .{ .twstat = .{ .fid = 1, .stat = renamed } });
    got = try h.reap();
    try testing.expectEqualStrings(e_wstat, got.msg.rerror.ename);
    try testing.expectEqualStrings("hello, body\n", h.fsys.body);

    var changes: [12]Stat = @splat(sentinel);
    changes[0].type = 0;
    changes[1].dev = 0;
    changes[2].qid.type = 0;
    changes[3].qid.version = 0;
    changes[4].qid.path = 0;
    changes[5].mode = 0o644;
    changes[6].atime = 0;
    changes[7].mtime = 0;
    changes[8].name = "renamed";
    changes[9].uid = "owner";
    changes[10].gid = "group";
    changes[11].muid = "writer";
    for (changes) |change| {
        for ([_]u64{ std.math.maxInt(u64), 0 }) |length| {
            if (change.mtime != std.math.maxInt(u32) and length == 0) continue;
            var attributes = change;
            attributes.length = length;
            const calls = h.fsys.calls;
            try h.send(20, .{ .twstat = .{ .fid = 1, .stat = attributes } });
            got = try h.reap();
            try testing.expect(got.msg == .rerror);
            try testing.expectEqualStrings(e_wstat, got.msg.rerror.ename);
            try testing.expectEqual(calls, h.fsys.calls);
            try testing.expectEqualStrings("hello, body\n", h.fsys.body);
        }
    }

    // Captured Linux v9fs O_TRUNC follow-up: length=0 plus current mtime.
    var linux_truncate = sentinel;
    linux_truncate.length = 0;
    linux_truncate.mtime = 1789432552;
    try h.send(21, .{ .twstat = .{ .fid = 1, .stat = linux_truncate } });
    got = try h.reap();
    try testing.expect(got.msg == .rwstat);
    try testing.expectEqualStrings("", h.fsys.body);
    h.fsys.body = "hello, body\n";

    var zero = sentinel;
    zero.length = 0;
    try h.send(9, .{ .twstat = .{ .fid = 1, .stat = zero } });
    got = try h.reap();
    try testing.expect(got.msg == .rwstat);
    try testing.expectEqualStrings("", h.fsys.body);

    h.fsys.body = "hello, body\n";
    _ = try h.walkTo(10, 2, &.{"index"});
    try h.send(11, .{ .topen = .{ .fid = 2, .mode = oread | otrunc } });
    got = try h.reap();
    try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);
    try h.send(12, .{ .topen = .{ .fid = 1, .mode = owrite | otrunc } });
    got = try h.reap();
    try testing.expectEqual(@as(u64, 18), got.msg.ropen.qid.path);
    try testing.expectEqualStrings("", h.fsys.body);
}

test "fs server: create and remove are refused, and a remove clunks the fid anyway" {
    var h: Harness = .{};
    try h.handshake(4096);

    try h.send(5, .{ .tcreate = .{ .fid = 0, .name = "thing", .perm = 0o600, .mode = owrite } });
    var got = try h.reap();
    try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);

    _ = try h.walkTo(6, 1, &.{ "1", "body" });
    try h.send(7, .{ .topen = .{ .fid = 1, .mode = ordwr } });
    _ = try h.reap();
    try h.send(8, .{ .tremove = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_perm, got.msg.rerror.ename);
    try testing.expectEqual(@as(u32, 1), h.fsys.releases);
    try h.send(9, .{ .tstat = .{ .fid = 1 } });
    got = try h.reap();
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);
}

test "fs server: a message arriving a byte at a time is served when its last byte lands" {
    var h: Harness = .{};
    try h.handshake(4096);

    var buf: [64]u8 = undefined;
    const bytes = try encode(.{ .tstat = .{ .fid = 0 } }, 5, &buf);
    for (bytes[0 .. bytes.len - 1]) |b| {
        try testing.expectEqual(@as(usize, 1), h.srv.push(&.{b}));
        h.pump();
        try h.quiet();
    }
    try testing.expectEqual(@as(usize, 1), h.srv.push(bytes[bytes.len - 1 ..]));
    h.pump();
    const got = try h.reap();
    try testing.expectEqualStrings("/", got.msg.rstat.stat.name);

    var pair: [128]u8 = undefined;
    const a = try encode(.{ .tstat = .{ .fid = 0 } }, 6, &pair);
    const b = try encode(.{ .tstat = .{ .fid = 0 } }, 7, pair[a.len..]);
    try testing.expectEqual(a.len + b.len, h.srv.push(pair[0 .. a.len + b.len]));
    h.pump();
    try testing.expectEqual(@as(u16, 6), (try h.reap()).tag);
    try testing.expectEqual(@as(u16, 7), (try h.reap()).tag);
    try h.quiet();
}

test "fs server: invalid framing and reply types terminate the connection" {
    for ([_]u8{ @intFromEnum(wire.Type.rstat), 8, 0 }) |kind| {
        var h: Harness = .{};
        try h.handshake(4096);
        var buf: [64]u8 = undefined;
        const raw = try encode(.{ .tstat = .{ .fid = 0 } }, 5, &buf);
        if (kind == 0) std.mem.writeInt(u32, raw[0..4], 3, .little) else raw[4] = kind;
        _ = h.srv.push(raw);
        h.pump();
        try h.quiet();
        try testing.expect(h.srv.protocol.dead);
    }
}

test "fs server: a connection that drops still pays the backend its releases" {
    var h: Harness = .{};
    try h.handshake(4096);
    _ = try h.walkTo(5, 1, &.{ "1", "event" });
    _ = try h.walkTo(6, 2, &.{ "1", "body" });
    for ([_]u32{ 1, 2 }, 7..) |fid, tag| {
        try h.send(@intCast(tag), .{ .topen = .{ .fid = fid, .mode = oread } });
        _ = try h.reap();
    }
    try h.send(9, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    try h.quiet();

    h.srv.hangup();
    h.pump();
    try testing.expectEqual(@as(u32, 2), h.fsys.releases);
    try h.quiet();

    var g: Harness = .{};
    try g.handshake(4096);
    _ = try g.walkTo(5, 1, &.{ "1", "event" });
    try g.send(6, .{ .topen = .{ .fid = 1, .mode = oread } });
    _ = try g.reap();
    try g.send(7, .{ .tread = .{ .fid = 1, .offset = 0, .count = 4096 } });
    try g.quiet();
    try g.send(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000" } });
    const v = try g.reap();
    try testing.expectEqualStrings("9P2000", v.msg.rversion.version);
    try testing.expectEqual(@as(u32, 1), g.fsys.releases);
    g.fsys.event = "Kli7 7 0 0 hello\n";
    g.pump();
    try g.quiet();
    try g.send(8, .{ .tstat = .{ .fid = 1 } });
    const got = try g.reap();
    try testing.expectEqualStrings(e_unknown_fid, got.msg.rerror.ename);
}

test "fs server: every errno the backend can answer is a string Linux knows" {
    try testing.expectEqualStrings("Operation not permitted", errString(E.PERM));
    try testing.expectEqualStrings("No such file or directory", errString(E.NOENT));
    try testing.expectEqualStrings("Input/output error", errString(E.IO));
    try testing.expectEqualStrings("Cannot allocate memory", errString(E.NOMEM));
    try testing.expectEqualStrings("Not a directory", errString(E.NOTDIR));
    try testing.expectEqualStrings("Invalid argument", errString(E.INVAL));
    try testing.expectEqualStrings("Too many open files in system", errString(E.NFILE));
    try testing.expectEqualStrings("No space left on device", errString(E.NOSPC));
    try testing.expectEqualStrings("Function not implemented", errString(E.NOSYS));
    try testing.expectEqualStrings("Input/output error", errString(0));
    try testing.expectEqualStrings("Input/output error", errString(999));

    try testing.expectEqualStrings("fid unknown or out of range", e_unknown_fid);
    try testing.expectEqualStrings("fid already in use", e_fid_in_use);
    try testing.expectEqualStrings("bad use of fid", e_bad_use);
    try testing.expectEqualStrings("bad offset in directory read", e_bad_offset);
    try testing.expectEqualStrings("permission denied", e_perm);
    try testing.expectEqualStrings("not a directory", e_not_dir);
    try testing.expectEqualStrings("file already open for I/O", e_already_open);
    try testing.expectEqualStrings("illegal name", e_illegal_name);
    try testing.expectEqualStrings("Too many open files in system", e_too_many_fids);
    try testing.expectEqualStrings("protocol botch", e_botch);
    try testing.expectEqualStrings("Interrupted system call", e_interrupted);
    try testing.expectEqualStrings("only support truncation to zero length", e_trunc_only);
    try testing.expectEqualStrings("wstat prohibited", e_wstat);
    try testing.expectEqualStrings("Resource temporarily unavailable", e_again);
    for ([_][]const u8{
        e_unknown_fid,  e_fid_in_use,    e_bad_use,     e_bad_offset,  e_perm,
        e_not_dir,      e_already_open,  e_botch,       e_interrupted, e_trunc_only,
        e_wstat,        e_again,         e_no_tree,     e_no_auth,     e_count_small,
        e_illegal_name, e_too_many_fids, e_small_msize,
    }) |s| try testing.expect(s.len <= errmax);
}

test "fs server: the fid capacity sizes the actual fid storage, and nothing else" {
    const Small = Server(StubFs, .{ .fid_capacity = 32 });
    const Large = Server(StubFs, .{ .fid_capacity = 256 });
    const SmallFids = @FieldType(Small, "fids");
    const LargeFids = @FieldType(Large, "fids");
    try testing.expectEqual(32, @typeInfo(SmallFids).array.len);
    try testing.expectEqual(256, @typeInfo(LargeFids).array.len);
    try testing.expectEqual(32 * @sizeOf(Small.Fid), @sizeOf(SmallFids));
    try testing.expectEqual(256 * @sizeOf(Large.Fid), @sizeOf(LargeFids));
    try testing.expectEqual(
        @sizeOf(LargeFids) - @sizeOf(SmallFids),
        @sizeOf(Large) - @sizeOf(Small),
    );
    try testing.expect(@sizeOf(SmallFids) <= 3 * 1024);
    try testing.expect(@sizeOf(LargeFids) <= 24 * 1024);
    try testing.expect(@sizeOf(@FieldType(Small, "slots")) <= 8 * 1024);
    try testing.expect(3 * 4096 + @sizeOf(Small) <= 24 * 1024);
}

test "fs server: a reply type with a payload locator is accepted and ignored" {
    const Payload = union(enum) { none, staged: u32 };
    const Located = struct {
        pub const Req = req_type;
        pub const Reply = ReplyWith(Payload);
    };
    const Engine = Server(Located, .{ .fid_capacity = 2 });
    const r: Located.Reply = .{ .tag = 1 };
    try testing.expect(r.payload == .none);
    try testing.expect(Located.Reply.Attr == Attr);
    try testing.expectEqual(E.IO, Located.Reply.fail(1, E.IO).errno);
    var in: [1024]u8 = undefined;
    var out: [2048]u8 = undefined;
    var encoded: [64]u8 = undefined;
    var server = Engine.init(.{ .in = &in, .out = &out, .root = 1 });
    _ = server.push(try encode(.{ .tversion = .{ .msize = 1024, .version = "9P2000" } }, notag, &encoded));
    try testing.expectEqual(null, server.next());
    server.wrote(server.output().len);
    _ = server.push(try encode(.{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "u", .aname = "" } }, 1, &encoded));
    const getattr = server.next() orelse return error.MissingGetattr;
    server.reply(&.{ .tag = getattr.tag, .attr = .{ .dir = true, .mode = 0o500 }, .payload = .{ .staged = 0 } }, "");
    try testing.expectEqual(null, server.next());
    const got = try decode(server.output());
    try testing.expectEqual(@as(u64, 1), got.msg.rattach.qid.path);
}

const Pair = struct {
    srv_in: [4096]u8 = undefined,
    srv_out: [8192]u8 = undefined,
    cli_in: [4096]u8 = undefined,
    cli_out: [4096]u8 = undefined,
    fsys: StubFs = .{},
    srv: Srv = undefined,
    cli: Client = undefined,

    fn start(p: *Pair) void {
        p.srv = Srv.init(.{ .in = &p.srv_in, .out = &p.srv_out, .root = 1 });
        p.cli = Client.init(.{ .in = &p.cli_in, .out = &p.cli_out });
    }

    fn answer(p: *Pair, req: Req) void {
        const a = p.fsys.handle(req);
        p.srv.reply(&a.reply, a.bytes);
    }

    fn wire_(p: *Pair) void {
        var moved = true;
        while (moved) {
            moved = false;
            while (p.cli.output().len != 0) {
                const n = p.srv.push(p.cli.output());
                if (n == 0) break;
                p.cli.wrote(n);
                moved = true;
            }
            while (p.srv.retry()) |req| {
                p.answer(req);
                moved = true;
            }
            while (p.srv.next()) |req| {
                p.answer(req);
                moved = true;
            }
            while (p.srv.output().len != 0) {
                const n = p.cli.push(p.srv.output());
                if (n == 0) break;
                p.srv.wrote(n);
                moved = true;
            }
        }
    }

    fn one(p: *Pair, req: Client.Request) !Client.Done {
        const tag = try p.cli.submit(req);
        p.wire_();
        const done = p.cli.take() orelse return error.NoReply;
        try testing.expectEqual(tag, done.tag);
        try testing.expectEqual(std.meta.activeTag(req), done.op);
        try testing.expectEqual(@as(usize, 0), p.cli.pending());
        return done;
    }

    fn handshake(p: *Pair) !void {
        p.start();
        const v = try p.one(.{ .version = .{} });
        try testing.expectEqualStrings("9P2000", v.result.version.version);
        try testing.expectEqual(@as(u16, notag), v.tag);
        const a = try p.one(.{ .attach = .{ .fid = 0, .uname = "goblin" } });
        try testing.expectEqual(@as(u64, 1), a.result.attach.path);
        try testing.expectEqual(qtdir, a.result.attach.type);
    }
};

test "fs client: a whole session against the engine" {
    var p: Pair = .{};
    try p.handshake();
    try testing.expectEqual(@as(u32, 4096), p.cli.msize);
    try testing.expectEqual(@as(u32, 4096 - 11), p.cli.maxRead());
    try testing.expectEqual(@as(u32, 4096 - 23), p.cli.maxWrite());

    const w = try p.one(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{ "1", "body" } } });
    try testing.expectEqual(@as(u16, 2), w.result.walk.nwqid);
    try testing.expectEqual(@as(u64, 16), w.result.walk.wqid[0].path);
    try testing.expectEqual(@as(u64, 18), w.result.walk.wqid[1].path);
    try testing.expectEqual(qtfile, w.result.walk.wqid[1].type);

    const o = try p.one(.{ .open = .{ .fid = 1, .mode = ordwr } });
    try testing.expectEqual(@as(u64, 18), o.result.open.qid.path);
    try testing.expectEqual(@as(u32, 4096 - iohdrsz), o.result.open.iounit);

    const r = try p.one(.{ .read = .{ .fid = 1, .offset = 0, .count = 64 } });
    try testing.expectEqualStrings("hello, body\n", r.result.read);
    const eof = try p.one(.{ .read = .{ .fid = 1, .offset = 12, .count = 64 } });
    try testing.expectEqual(@as(usize, 0), eof.result.read.len);

    const wr = try p.one(.{ .write = .{ .fid = 1, .offset = 0, .data = "abc" } });
    try testing.expectEqual(@as(u32, 3), wr.result.write);
    try testing.expectEqualStrings("abc", p.fsys.writes[0..p.fsys.writes_len]);

    const st = try p.one(.{ .stat = .{ .fid = 1 } });
    try testing.expectEqualStrings("body", st.result.stat.name);
    try testing.expectEqual(@as(u64, 12), st.result.stat.length);
    try testing.expectEqualStrings("goblin", st.result.stat.uid);

    _ = try p.one(.{ .clunk = .{ .fid = 1 } });
    try testing.expectEqual(@as(u32, 1), p.fsys.releases);
    try testing.expectEqual(@as(usize, 0), p.cli.pending());
    try testing.expectEqual(@as(usize, 0), p.cli.output().len);
    try testing.expect(p.cli.take() == null);
    try testing.expect(!p.cli.dead);
}

fn deliverReversed(p: *Pair) !void {
    var scratch: [4096]u8 = undefined;
    const out = p.srv.output();
    try testing.expect(out.len <= scratch.len);
    @memcpy(scratch[0..out.len], out);
    const total = out.len;
    p.srv.wrote(total);

    var at: [max_tags]usize = undefined;
    var lens: [max_tags]u32 = undefined;
    var count: usize = 0;
    var i: usize = 0;
    while (i < total) {
        const len = frameLen(scratch[i..total]) orelse return error.ShortReply;
        at[count] = i;
        lens[count] = len;
        count += 1;
        i += len;
    }
    try testing.expect(count >= 2);
    var k = count;
    while (k > 0) {
        k -= 1;
        const f = scratch[at[k]..][0..lens[k]];
        try testing.expectEqual(f.len, p.cli.push(f));
    }
}

test "fs client: replies out of order are matched by tag and not by arrival" {
    var p: Pair = .{};
    try p.handshake();
    const w = try p.one(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{"index"} } });
    try testing.expectEqual(@as(u16, 1), w.result.walk.nwqid);

    const root_tag = try p.cli.submit(.{ .stat = .{ .fid = 0 } });
    const index_tag = try p.cli.submit(.{ .stat = .{ .fid = 1 } });
    try testing.expectEqual(@as(u16, 0), root_tag);
    try testing.expectEqual(@as(u16, 1), index_tag);
    try testing.expectEqual(@as(usize, 2), p.cli.pending());

    while (p.cli.output().len != 0) {
        const n = p.srv.push(p.cli.output());
        p.cli.wrote(n);
    }
    while (p.srv.next()) |req| p.answer(req);
    try deliverReversed(&p);

    const first = p.cli.take() orelse return error.NoReply;
    try testing.expectEqual(index_tag, first.tag);
    try testing.expectEqualStrings("index", first.result.stat.name);
    const second = p.cli.take() orelse return error.NoReply;
    try testing.expectEqual(root_tag, second.tag);
    try testing.expectEqualStrings("/", second.result.stat.name);
    try testing.expectEqual(@as(usize, 0), p.cli.pending());
    try testing.expect(!p.cli.dead);
}

test "fs client: an Rerror answers one operation and the session carries on" {
    var p: Pair = .{};
    try p.handshake();

    const bad = try p.one(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{"nope"} } });
    try testing.expectEqual(Client.Op.walk, bad.op);
    try testing.expectEqualStrings(errString(E.NOENT), bad.result.fail);

    try testing.expectEqual(@as(usize, 0), p.cli.pending());
    try testing.expect(!p.cli.dead);
    const st = try p.one(.{ .stat = .{ .fid = 0 } });
    try testing.expectEqualStrings("/", st.result.stat.name);

    const stale = try p.one(.{ .stat = .{ .fid = 9 } });
    try testing.expectEqualStrings(e_unknown_fid, stale.result.fail);
    try testing.expect(!p.cli.dead);
}

test "fs client: a reply arriving a byte at a time is taken when its last byte lands" {
    var p: Pair = .{};
    try p.handshake();
    const tag = try p.cli.submit(.{ .stat = .{ .fid = 0 } });

    while (p.cli.output().len != 0) {
        const n = p.srv.push(p.cli.output());
        p.cli.wrote(n);
    }
    while (p.srv.next()) |req| p.answer(req);
    var scratch: [512]u8 = undefined;
    const out = p.srv.output();
    try testing.expect(out.len > 4 and out.len <= scratch.len);
    @memcpy(scratch[0..out.len], out);
    const reply = scratch[0..out.len];
    p.srv.wrote(reply.len);

    for (reply[0 .. reply.len - 1]) |b| {
        try testing.expectEqual(@as(usize, 1), p.cli.push(&.{b}));
        try testing.expect(p.cli.take() == null);
        try testing.expect(!p.cli.dead);
    }
    try testing.expectEqual(@as(usize, 1), p.cli.push(reply[reply.len - 1 ..]));
    const done = p.cli.take() orelse return error.NoReply;
    try testing.expectEqual(tag, done.tag);
    try testing.expectEqualStrings("/", done.result.stat.name);
}

test "fs client: sixteen tags outstanding against the engine, and the seventeenth is refused" {
    var p: Pair = .{};
    try p.handshake();

    var tags: [max_tags]u16 = undefined;
    for (&tags, 0..) |*t, i| {
        t.* = try p.cli.submit(.{ .stat = .{ .fid = 0 } });
        try testing.expectEqual(@as(u16, @intCast(i)), t.*);
    }
    try testing.expectEqual(max_tags, p.cli.pending());
    try testing.expectError(error.NoTags, p.cli.submit(.{ .stat = .{ .fid = 0 } }));
    const owed = p.cli.output().len;
    try testing.expectError(error.NoTags, p.cli.submit(.{ .clunk = .{ .fid = 0 } }));
    try testing.expectEqual(owed, p.cli.output().len);

    p.wire_();
    var seen: [max_tags]bool = @splat(false);
    for (0..max_tags) |_| {
        const done = p.cli.take() orelse return error.NoReply;
        try testing.expectEqual(Client.Op.stat, done.op);
        try testing.expect(!seen[done.tag]);
        seen[done.tag] = true;
    }
    for (seen) |s| try testing.expect(s);
    try testing.expectEqual(@as(usize, 0), p.cli.pending());
    _ = try p.one(.{ .stat = .{ .fid = 0 } });
}

test "fs client: what a caller may not ask for is refused before a tag is spent" {
    var p: Pair = .{};
    p.start();

    try testing.expectError(error.Handshake, p.cli.submit(.{ .stat = .{ .fid = 0 } }));
    try p.handshake();

    try testing.expectError(error.BadRequest, p.cli.submit(.{ .stat = .{ .fid = nofid } }));
    try testing.expectError(error.BadRequest, p.cli.submit(.{ .clunk = .{ .fid = nofid } }));
    try testing.expectError(error.BadRequest, p.cli.submit(.{ .walk = .{ .fid = 0, .newfid = nofid, .names = &.{} } }));

    try testing.expectError(error.BadRequest, p.cli.submit(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{"1/body"} } }));
    try testing.expectError(error.BadRequest, p.cli.submit(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{""} } }));
    const seventeen: [max_welem + 1][]const u8 = @splat("x");
    try testing.expectError(error.BadRequest, p.cli.submit(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &seventeen } }));

    try testing.expectError(error.TooLarge, p.cli.submit(.{ .read = .{
        .fid = 0,
        .offset = 0,
        .count = p.cli.maxRead() + 1,
    } }));
    var big: [4096]u8 = @splat('x');
    try testing.expectError(error.TooLarge, p.cli.submit(.{ .write = .{
        .fid = 0,
        .offset = 0,
        .data = big[0 .. p.cli.maxWrite() + 1],
    } }));
    p.cli.wrote(p.cli.output().len);
    _ = try p.cli.submit(.{ .read = .{ .fid = 0, .offset = 0, .count = p.cli.maxRead() } });
    p.cli.wrote(p.cli.output().len);
    _ = try p.cli.submit(.{ .write = .{ .fid = 0, .offset = 0, .data = big[0..p.cli.maxWrite()] } });

    try testing.expectError(error.Handshake, p.cli.submit(.{ .version = .{} }));
    try testing.expectError(error.NoSpace, p.cli.submit(.{ .stat = .{ .fid = 0 } }));
}

test "fs client: an Rread longer than the Tread asked for is refused" {
    var p: Pair = .{};
    try p.handshake();
    _ = try p.one(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{ "1", "body" } } });
    _ = try p.one(.{ .open = .{ .fid = 1, .mode = oread } });

    const tag = try p.cli.submit(.{ .read = .{ .fid = 1, .offset = 0, .count = 4 } });
    p.cli.wrote(p.cli.output().len);
    var buf: [64]u8 = undefined;
    _ = p.cli.push(try encode(.{ .rread = .{ .data = "hello, body\n" } }, tag, &buf));
    try testing.expect(p.cli.take() == null);
    try testing.expect(p.cli.dead);

    var q: Pair = .{};
    try q.handshake();
    _ = try q.one(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{ "1", "body" } } });
    _ = try q.one(.{ .open = .{ .fid = 1, .mode = oread } });
    const short = try q.one(.{ .read = .{ .fid = 1, .offset = 0, .count = 4 } });
    try testing.expectEqualStrings("hell", short.result.read);
}

test "fs client: hangup and a dead connection refuse everything after" {
    var p: Pair = .{};
    try p.handshake();
    p.cli.hangup();
    try testing.expectEqual(@as(usize, 0), p.cli.pending());
    try testing.expectEqual(@as(usize, 0), p.cli.output().len);
    try testing.expectEqual(@as(usize, 0), p.cli.push("anything"));
    try testing.expect(p.cli.take() == null);
    try testing.expectError(error.Dead, p.cli.submit(.{ .stat = .{ .fid = 0 } }));
    try testing.expectError(error.Dead, p.cli.submit(.{ .version = .{} }));
}

// ---- tests: a backend declaring every feature, references, and the fid index ----

/// A small mutable tree that counts the references the engine holds on
/// every node (each lookup result is one; each release drops one).
const MutableFs = struct {
    pub const Req = req_type;
    pub const Reply = reply_type;
    pub const features: Features = .{ .create = true, .remove = true, .wstat = true, .references = true };

    const Node = struct {
        used: bool = false,
        removed: bool = false,
        parent: u64 = 1,
        name: [32]u8 = undefined,
        name_len: u8 = 0,
        dir: bool = false,
        mode: u16 = 0o644,
        mtime: u32 = 0,
        data: [64]u8 = undefined,
        len: u32 = 0,
        refs: u32 = 0,
        opens: u32 = 0,

        fn nameOf(n: *const Node) []const u8 {
            return n.name[0..n.name_len];
        }
    };

    nodes: [16]Node = @splat(.{}),
    releases: u32 = 0,
    stage: [1024]u8 = undefined,

    fn init() MutableFs {
        var m: MutableFs = .{};
        m.nodes[1] = .{ .used = true, .dir = true, .mode = 0o755 };
        m.nodes[1].name[0] = '/';
        m.nodes[1].name_len = 1;
        _ = m.add(1, "a", false, 0o644);
        @memcpy(m.nodes[2].data[0..5], "hello");
        m.nodes[2].len = 5;
        _ = m.add(1, "d", true, 0o755);
        _ = m.add(3, "x", false, 0o600);
        return m;
    }

    fn add(m: *MutableFs, parent: u64, name: []const u8, dir: bool, mode: u16) u64 {
        for (&m.nodes, 0..) |*n, i| if (i != 0 and !n.used) {
            n.* = .{ .used = true, .parent = parent, .dir = dir, .mode = mode };
            @memcpy(n.name[0..name.len], name);
            n.name_len = @intCast(name.len);
            return i;
        };
        unreachable;
    }

    fn child(m: *const MutableFs, dir: u64, name: []const u8) ?u64 {
        for (&m.nodes, 0..) |*n, i| {
            if (n.used and !n.removed and i != 1 and n.parent == dir and std.mem.eql(u8, n.nameOf(), name)) return i;
        }
        return null;
    }

    fn attrOf(m: *const MutableFs, id: u64) Attr {
        const n = &m.nodes[id];
        return .{ .name = n.nameOf(), .node = id, .dir = n.dir, .mode = n.mode, .size = n.len, .mtime = n.mtime };
    }

    fn totalRefs(m: *const MutableFs) u32 {
        var t: u32 = 0;
        for (&m.nodes) |*n| t += n.refs;
        return t;
    }

    fn handle(m: *MutableFs, req: req_type) StubFs.Answer {
        const fail = struct {
            fn f(tag: u64, e: u16) StubFs.Answer {
                return .{ .reply = .{ .tag = tag, .status = .err, .errno = e } };
            }
        }.f;
        if (req.node == 0 or req.node >= m.nodes.len or !m.nodes[req.node].used) return fail(req.tag, E.NOENT);
        const n = &m.nodes[req.node];
        switch (req.op) {
            .lookup => {
                const id: u64 = if (std.mem.eql(u8, req.data, "."))
                    req.node
                else if (std.mem.eql(u8, req.data, ".."))
                    n.parent
                else
                    m.child(req.node, req.data) orelse return fail(req.tag, E.NOENT);
                if (id != 1) m.nodes[id].refs += 1; // the root, like a provider root, is not counted
                return .{ .reply = .{ .tag = req.tag, .attr = m.attrOf(id) } };
            },
            .getattr => return .{ .reply = .{ .tag = req.tag, .attr = m.attrOf(req.node) } },
            .setattr => {
                if (req.set.name) {
                    if (m.child(n.parent, req.data) != null) return fail(req.tag, E.EXIST);
                    @memcpy(n.name[0..req.data.len], req.data);
                    n.name_len = @intCast(req.data.len);
                }
                if (req.set.mode) n.mode = @truncate(req.perm);
                if (req.set.mtime) n.mtime = req.mtime;
                if (req.set.length or req.truncate) {
                    const len: u32 = if (req.set.length) @intCast(req.length) else 0;
                    if (len > n.data.len) return fail(req.tag, E.NOSPC);
                    if (len > n.len) @memset(n.data[n.len..len], 0);
                    n.len = len;
                }
                return .{ .reply = .{ .tag = req.tag, .attr = m.attrOf(req.node) } };
            },
            .open => {
                if (req.create) {
                    if (m.child(req.node, req.data) != null) return fail(req.tag, E.EXIST);
                    const id = m.add(req.node, req.data, req.perm & dmdir != 0, @truncate(req.perm));
                    m.nodes[id].refs += 1;
                    m.nodes[id].opens += 1;
                    return .{ .reply = .{ .tag = req.tag, .attr = m.attrOf(id), .handle = 7 } };
                }
                n.opens += 1;
                return .{ .reply = .{ .tag = req.tag, .handle = 7 } };
            },
            .read => {
                if (req.off >= n.len) return .{ .reply = .{ .tag = req.tag } };
                const from = n.data[@intCast(req.off)..n.len];
                return .{ .reply = .{ .tag = req.tag }, .bytes = from[0..@min(from.len, req.size)] };
            },
            .write => {
                const end: u64 = req.off + req.data.len;
                if (end > n.data.len) return fail(req.tag, E.NOSPC);
                @memcpy(n.data[@intCast(req.off)..@intCast(end)], req.data);
                n.len = @max(n.len, @as(u32, @intCast(end)));
                n.mtime += 1;
                return .{ .reply = .{ .tag = req.tag, .written = @intCast(req.data.len) } };
            },
            .readdir => {
                var k: usize = 0;
                var seen: u64 = 0;
                for (&m.nodes, 0..) |*e, i| {
                    if (!e.used or e.removed or i == 1 or e.parent != req.node) continue;
                    if (seen < req.off) {
                        seen += 1;
                        continue;
                    }
                    std.mem.writeInt(u64, m.stage[k..][0..8], i, .little);
                    m.stage[k + 8] = @intFromBool(e.dir);
                    m.stage[k + 9] = e.name_len;
                    @memcpy(m.stage[k + 10 ..][0..e.name_len], e.nameOf());
                    k += 10 + e.name_len;
                }
                return .{ .reply = .{ .tag = req.tag }, .bytes = m.stage[0..k] };
            },
            .release => {
                m.releases += 1;
                var status: Status = .ok;
                var errno: u16 = 0;
                if (req.opened) n.opens -= 1;
                if (req.remove) {
                    if (req.node == 1) {
                        status = .err;
                        errno = E.PERM;
                    } else if (n.dir and m.hasChildren(req.node)) {
                        status = .err;
                        errno = E.NOTEMPTY;
                    } else n.removed = true;
                }
                if (req.node != 1) n.refs -= 1;
                if (n.removed and n.refs == 0) n.used = false;
                return .{ .reply = .{ .tag = req.tag, .status = status, .errno = errno, .ename = if (errno == E.NOTEMPTY) "directory not empty" else "" } };
            },
        }
    }

    fn hasChildren(m: *const MutableFs, dir: u64) bool {
        for (&m.nodes, 0..) |*e, i| if (e.used and !e.removed and i != 1 and e.parent == dir) return true;
        return false;
    }
};

/// A "don't care" Twstat: every field left as it is.
const stat_dontcare: Stat = .{
    .type = 0xFFFF,
    .dev = 0xFFFF_FFFF,
    .qid = .{ .type = 0xFF, .version = 0xFFFF_FFFF, .path = 0xFFFF_FFFF_FFFF_FFFF },
    .mode = 0xFFFF_FFFF,
    .atime = 0xFFFF_FFFF,
    .mtime = 0xFFFF_FFFF,
    .length = 0xFFFF_FFFF_FFFF_FFFF,
    .name = "",
    .uid = "",
    .gid = "",
    .muid = "",
};

/// The harness for any backend with a `handle(req) StubFs.Answer`.
fn Rig(comptime Fs: type, comptime opts: Options) type {
    return struct {
        const R = @This();
        const S = Server(Fs, opts);

        in: [4096]u8 = undefined,
        out: [8192]u8 = undefined,
        fsys: Fs,
        srv: S = undefined,

        fn start(r: *R) void {
            r.srv = S.init(.{ .in = &r.in, .out = &r.out, .root = 1, .seed = 0x4242 });
        }

        fn pump(r: *R) void {
            while (r.srv.retry()) |req| {
                const a = r.fsys.handle(req);
                r.srv.reply(&a.reply, a.bytes);
            }
            while (r.srv.next()) |req| {
                const a = r.fsys.handle(req);
                r.srv.reply(&a.reply, a.bytes);
            }
        }

        fn send(r: *R, tag: u16, msg: Msg) !void {
            var buf: [1024]u8 = undefined;
            const bytes = try encode(msg, tag, &buf);
            try testing.expectEqual(bytes.len, r.srv.push(bytes));
            r.pump();
        }

        fn reap(r: *R) !Decoded {
            const out = r.srv.output();
            const len = frameLen(out) orelse return error.NoReply;
            if (len > out.len) return error.ShortReply;
            const got = try decode(out[0..len]);
            r.srv.wrote(len);
            return got;
        }

        fn call(r: *R, tag: u16, msg: Msg) !Decoded {
            try r.send(tag, msg);
            return r.reap();
        }

        fn handshake(r: *R) !void {
            r.start();
            _ = try r.call(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000" } });
            _ = try r.call(0, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
        }

        fn walkTo(r: *R, fid: u32, newfid: u32, list: []const []const u8) !Decoded {
            return r.call(9, .{ .twalk = .{ .fid = fid, .newfid = newfid, .nwname = @intCast(list.len), .wname = wnames(list) } });
        }

        fn ename(r: *R, tag: u16, msg: Msg) ![]const u8 {
            const got = try r.call(tag, msg);
            return if (got.msg == .rerror) got.msg.rerror.ename else error.NotAnError;
        }
    };
}

const MutRig = Rig(MutableFs, .{ .fid_capacity = 8, .slot_capacity = 2 });

test "fs features: create, write, wstat and remove reach a backend that declares them" {
    var r: MutRig = .{ .fsys = MutableFs.init() };
    try r.handshake();
    _ = try r.walkTo(0, 1, &.{"d"});
    var got = try r.call(2, .{ .tcreate = .{ .fid = 1, .name = "new", .perm = 0o640, .mode = ordwr } });
    try testing.expectEqual(qtfile, got.msg.rcreate.qid.type);
    try testing.expectEqual(@as(u32, 4096 - iohdrsz), got.msg.rcreate.iounit);
    got = try r.call(3, .{ .twrite = .{ .fid = 1, .offset = 0, .data = "fresh" } });
    try testing.expectEqual(@as(u32, 5), got.msg.rwrite.count);
    got = try r.call(4, .{ .tread = .{ .fid = 1, .offset = 0, .count = 100 } });
    try testing.expectEqualStrings("fresh", got.msg.rread.data);
    got = try r.call(5, .{ .tstat = .{ .fid = 1 } });
    try testing.expectEqualStrings("new", got.msg.rstat.stat.name);
    try testing.expectEqual(@as(u32, 0o640), got.msg.rstat.stat.mode);
    // the engine judges names and the directory's write bit; the backend judges existence
    try testing.expectEqualStrings(e_already_open, try r.ename(6, .{ .tcreate = .{ .fid = 1, .name = "z", .perm = 0o644, .mode = oread } }));
    _ = try r.walkTo(0, 2, &.{"d"});
    try testing.expectEqualStrings(e_illegal_name, try r.ename(7, .{ .tcreate = .{ .fid = 2, .name = "a/b", .perm = 0o644, .mode = oread } }));
    try testing.expectEqualStrings(e_illegal_name, try r.ename(7, .{ .tcreate = .{ .fid = 2, .name = "..", .perm = 0o644, .mode = oread } }));
    try testing.expectEqualStrings(e_perm, try r.ename(7, .{ .tcreate = .{ .fid = 2, .name = "e", .perm = dmdir | 0o755, .mode = owrite } }));
    try testing.expectEqualStrings(errString(E.EXIST), try r.ename(7, .{ .tcreate = .{ .fid = 2, .name = "new", .perm = 0o644, .mode = oread } }));
    _ = try r.walkTo(0, 3, &.{ "d", "x" });
    try testing.expectEqualStrings(e_not_dir, try r.ename(7, .{ .tcreate = .{ .fid = 3, .name = "e", .perm = 0o644, .mode = oread } }));
    // wstat: rename, mode, mtime, length; the engine-owned fields must be "don't care"
    var st = stat_dontcare;
    st.name = "renamed";
    st.mode = 0o600;
    st.mtime = 99;
    st.length = 2;
    got = try r.call(8, .{ .twstat = .{ .fid = 1, .stat = st } });
    try testing.expect(got.msg == .rwstat);
    got = try r.call(9, .{ .tstat = .{ .fid = 1 } });
    try testing.expectEqualStrings("renamed", got.msg.rstat.stat.name);
    try testing.expectEqual(@as(u32, 0o600), got.msg.rstat.stat.mode);
    try testing.expectEqual(@as(u32, 99), got.msg.rstat.stat.mtime);
    try testing.expectEqual(@as(u64, 2), got.msg.rstat.stat.length);
    st = stat_dontcare;
    st.uid = "someone";
    try testing.expectEqualStrings(e_wstat, try r.ename(10, .{ .twstat = .{ .fid = 1, .stat = st } }));
    st = stat_dontcare;
    st.mode = dmdir | 0o755;
    try testing.expectEqualStrings(e_wstat, try r.ename(10, .{ .twstat = .{ .fid = 1, .stat = st } }));
    st = stat_dontcare;
    st.name = "x";
    try testing.expectEqualStrings(errString(E.EXIST), try r.ename(10, .{ .twstat = .{ .fid = 1, .stat = st } }));
    st = stat_dontcare;
    st.length = 5;
    try testing.expectEqualStrings(e_wstat, try r.ename(10, .{ .twstat = .{ .fid = 2, .stat = st } }));
    got = try r.call(11, .{ .twstat = .{ .fid = 2, .stat = stat_dontcare } });
    try testing.expect(got.msg == .rwstat);
    // remove: the backend's refusal is the Rerror, and the fid is gone either way
    try testing.expectEqualStrings("directory not empty", try r.ename(12, .{ .tremove = .{ .fid = 2 } }));
    try testing.expectEqualStrings(e_unknown_fid, try r.ename(13, .{ .tclunk = .{ .fid = 2 } }));
    got = try r.call(14, .{ .tremove = .{ .fid = 3 } });
    try testing.expect(got.msg == .rremove);
    got = try r.call(15, .{ .tremove = .{ .fid = 1 } });
    try testing.expect(got.msg == .rremove);
    _ = try r.walkTo(0, 4, &.{"d"});
    got = try r.call(16, .{ .tremove = .{ .fid = 4 } });
    try testing.expect(got.msg == .rremove);
    got = try r.walkTo(0, 5, &.{"d"});
    try testing.expectEqualStrings(errString(E.NOENT), got.msg.rerror.ename);
    // ORCLOSE: the clunk removes
    _ = try r.walkTo(0, 6, &.{"a"});
    got = try r.call(17, .{ .topen = .{ .fid = 6, .mode = oread | orclose } });
    try testing.expect(got.msg == .ropen);
    got = try r.call(18, .{ .tclunk = .{ .fid = 6 } });
    try testing.expect(got.msg == .rclunk);
    got = try r.walkTo(0, 7, &.{"a"});
    try testing.expectEqualStrings(errString(E.NOENT), got.msg.rerror.ename);
    try testing.expectEqual(@as(u32, 0), r.fsys.totalRefs());
}

test "fs features: every reference a lookup hands out is released exactly once" {
    var r: MutRig = .{ .fsys = MutableFs.init() };
    try r.handshake();
    const m = &r.fsys;
    // a walk holds one reference per element while it runs and one at the end
    var got = try r.walkTo(0, 1, &.{ "d", ".", "x", "..", "x" });
    try testing.expectEqual(@as(u16, 5), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u32, 1), m.nodes[4].refs);
    try testing.expectEqual(@as(u32, 0), m.nodes[3].refs);
    // a clone is a lookup of "."
    got = try r.walkTo(1, 2, &.{});
    try testing.expectEqual(@as(u32, 2), m.nodes[4].refs);
    // a partial walk releases what it took, and binds nothing
    got = try r.walkTo(0, 3, &.{ "d", "x", "nope" });
    try testing.expectEqual(@as(u16, 2), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u32, 2), m.nodes[4].refs);
    try testing.expectEqual(@as(u32, 0), m.nodes[3].refs);
    try testing.expectEqualStrings(e_unknown_fid, try r.ename(4, .{ .tclunk = .{ .fid = 3 } }));
    // walking a fid onto itself releases the old node after binding the new
    _ = try r.walkTo(0, 8, &.{"d"});
    try testing.expectEqual(@as(u32, 1), m.nodes[3].refs);
    got = try r.walkTo(8, 8, &.{ "..", "d", "x" });
    try testing.expectEqual(@as(u16, 3), got.msg.rwalk.nwqid);
    try testing.expectEqual(@as(u32, 3), m.nodes[4].refs);
    try testing.expectEqual(@as(u32, 0), m.nodes[3].refs);
    _ = try r.call(4, .{ .tclunk = .{ .fid = 8 } });
    try testing.expectEqual(@as(u32, 2), m.nodes[4].refs);
    // clunk of an unopened fid is a release too; an open one closes as well
    got = try r.call(5, .{ .topen = .{ .fid = 2, .mode = oread } });
    try testing.expectEqual(@as(u32, 1), m.nodes[4].opens);
    got = try r.call(6, .{ .tclunk = .{ .fid = 2 } });
    try testing.expectEqual(@as(u32, 1), m.nodes[4].refs);
    try testing.expectEqual(@as(u32, 0), m.nodes[4].opens);
    // a create replaces the directory reference with the new node's
    _ = try r.walkTo(0, 3, &.{"d"});
    try testing.expectEqual(@as(u32, 1), m.nodes[3].refs);
    got = try r.call(7, .{ .tcreate = .{ .fid = 3, .name = "n", .perm = 0o644, .mode = owrite } });
    try testing.expect(got.msg == .rcreate);
    try testing.expectEqual(@as(u32, 0), m.nodes[3].refs);
    try testing.expectEqual(@as(u32, 1), m.nodes[5].refs);
    // Tversion releases everything, opened or not
    _ = try r.call(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000" } });
    try testing.expectEqual(@as(u32, 0), m.totalRefs());
    try testing.expectEqual(@as(u32, 0), m.nodes[5].opens);
    try testing.expectEqual(@as(usize, 0), r.srv.fidCount());
    // and so does a hangup, through the releases next() still yields
    _ = try r.call(0, .{ .tattach = .{ .fid = 0, .afid = nofid, .uname = "goblin", .aname = "" } });
    _ = try r.walkTo(0, 1, &.{ "d", "x" });
    _ = try r.walkTo(0, 2, &.{"a"});
    _ = try r.call(8, .{ .topen = .{ .fid = 2, .mode = oread } });
    try testing.expectEqual(@as(u32, 2), m.totalRefs());
    r.srv.hangup();
    r.pump();
    try testing.expectEqual(@as(u32, 0), m.totalRefs());
    try testing.expectEqual(@as(u32, 0), m.nodes[2].opens);
    try testing.expectEqual(@as(usize, 0), r.srv.fidCount());
}

const IndexRig = Rig(StubFs, .{ .fid_capacity = 4096, .fid_index = true });

/// Every index bucket points at a live fid that finds itself, and every live
/// fid is found: the invariant the churn test checks after each phase.
fn checkFidIndex(s: *const IndexRig.S) !void {
    var indexed: usize = 0;
    for (s.index) |slot| {
        if (slot == IndexRig.S.no_slot) continue;
        indexed += 1;
        try testing.expect(s.fids[slot].used and !s.fids[slot].orphan);
        try testing.expectEqual(@as(usize, slot), s.findFid(s.fids[slot].fid).?);
    }
    var live: usize = 0;
    var used: usize = 0;
    for (s.fids[0..s.high_water], 0..) |*f, i| {
        if (!f.used) continue;
        used += 1;
        if (f.orphan) continue;
        live += 1;
        try testing.expectEqual(i, s.findFid(f.fid).?);
    }
    for (s.fids[s.high_water..]) |*f| try testing.expect(!f.used);
    try testing.expectEqual(indexed, live);
    try testing.expectEqual(used, s.fidCount());
}

/// Fid numbers chosen to stress the index: dense low ids, ids with only high
/// bits set, and ids counting down from 2^32-1 (all distinct for i < 2^20).
fn adversarialId(i: u32) u32 {
    return switch (i % 3) {
        0 => i * 8192 + 1,
        1 => 0x8000_0000 | i,
        else => 0xFFFF_FFFF - i,
    };
}

test "fs server: the fid index holds thousands of fids through hostile clunk orders, reuse and Tversion" {
    const r = try testing.allocator.create(IndexRig);
    defer testing.allocator.destroy(r);
    r.* = .{ .fsys = .{} };
    try r.handshake();
    const n: u32 = 4096 - 1; // fid 0 is the attach
    var i: u32 = 0;
    while (i < n) : (i += 1) {
        const got = try r.walkTo(0, adversarialId(i), &.{ "1", "body" });
        try testing.expectEqual(@as(u16, 2), got.msg.rwalk.nwqid);
    }
    try testing.expectEqual(@as(usize, n + 1), r.srv.fidCount());
    try testing.expectEqualStrings(e_too_many_fids, try r.ename(1, .{ .twalk = .{ .fid = 0, .newfid = 0x7FFF_FFFF, .nwname = 0 } }));
    try testing.expectEqualStrings(e_fid_in_use, try r.ename(1, .{ .twalk = .{ .fid = 0, .newfid = adversarialId(5), .nwname = 0 } }));
    try testing.expectEqualStrings(e_unknown_fid, try r.ename(1, .{ .tclunk = .{ .fid = 0x7FFF_FFFF } }));
    try checkFidIndex(&r.srv);
    // clunk every third fid, then the rest from the top: backward-shift deletion under churn
    i = 0;
    while (i < n) : (i += 3) _ = try r.call(2, .{ .tclunk = .{ .fid = adversarialId(i) } });
    try checkFidIndex(&r.srv);
    i = n;
    while (i > 0) {
        i -= 1;
        const got = try r.call(2, .{ .tclunk = .{ .fid = adversarialId(i) } });
        try testing.expect((got.msg == .rerror) == (i % 3 == 0));
    }
    try testing.expectEqual(@as(usize, 1), r.srv.fidCount());
    try checkFidIndex(&r.srv);
    // the whole table is reusable after the churn, through the free list
    i = 0;
    while (i < n) : (i += 1) _ = try r.call(3, .{ .twalk = .{ .fid = 0, .newfid = n - i, .nwname = 0 } });
    try testing.expectEqualStrings(e_too_many_fids, try r.ename(3, .{ .twalk = .{ .fid = 0, .newfid = n + 1, .nwname = 0 } }));
    try checkFidIndex(&r.srv);
    // a pseudo-random alloc/free storm with verification
    var prng = std.Random.DefaultPrng.init(0x9a11);
    const rnd = prng.random();
    var live: [n + 1]bool = @splat(true);
    live[0] = false;
    var round: usize = 0;
    while (round < 20_000) : (round += 1) {
        const id = 1 + rnd.uintLessThan(u32, n);
        const got = if (live[id])
            try r.call(4, .{ .tclunk = .{ .fid = id } })
        else
            try r.walkTo(0, id, &.{"1"});
        try testing.expect(got.msg != .rerror);
        live[id] = !live[id];
        if (round % 997 == 0) try checkFidIndex(&r.srv);
    }
    try checkFidIndex(&r.srv);
    // Tversion drops everything and the table starts over
    _ = try r.call(notag, .{ .tversion = .{ .msize = 4096, .version = "9P2000" } });
    try testing.expectEqual(@as(usize, 0), r.srv.fidCount());
    try checkFidIndex(&r.srv);
    _ = try r.call(0, .{ .tattach = .{ .fid = 0xFFFF_FFFE, .afid = nofid, .uname = "goblin", .aname = "" } });
    _ = try r.call(5, .{ .twalk = .{ .fid = 0xFFFF_FFFE, .newfid = 0, .nwname = 0 } });
    try checkFidIndex(&r.srv);
    // the index costs two bytes per bucket and nothing else
    try testing.expectEqual(8192 * 2, @sizeOf(@FieldType(IndexRig.S, "index")));
    try testing.expectEqual(0, @sizeOf(@FieldType(Srv, "index")));
}

/// Multiplicative inverse of an odd 32-bit constant (Newton iteration).
fn inverseMod32(a: u32) u32 {
    var x: u32 = a;
    for (0..5) |_| x *%= 2 -% a *% x;
    return x;
}

test "fs server: fid numbers crafted to collide under the public hash do not cluster a salted index" {
    const r = try testing.allocator.create(IndexRig);
    defer testing.allocator.destroy(r);
    r.* = .{ .fsys = .{} };
    try r.handshake();
    // ids whose products with the golden ratio share their top bits: one bucket when unsalted
    const inv = inverseMod32(0x9E37_79B1);
    try testing.expectEqual(@as(u32, 1), inv *% 0x9E37_79B1);
    const n: u32 = 4096 - 1;
    const base: u32 = 0x4242_0000;
    var i: u32 = 0;
    while (i < n) : (i += 1) {
        const id = (base + i) *% inv;
        try testing.expectEqual(@as(usize, base >> IndexRig.S.index_shift), @as(usize, @intCast((id *% 0x9E37_79B1) >> IndexRig.S.index_shift)));
        _ = try r.call(3, .{ .twalk = .{ .fid = 0, .newfid = id, .nwname = 0 } });
    }
    try checkFidIndex(&r.srv);
    // the longest probe sequence in the salted table is short; unsalted it would be ~n
    var worst: usize = 0;
    i = 0;
    while (i < n) : (i += 1) {
        const id = (base + i) *% inv;
        var pos = r.srv.fidHome(id);
        var steps: usize = 0;
        while (r.srv.fids[r.srv.index[pos]].fid != id) : (pos = (pos + 1) & IndexRig.S.index_mask) steps += 1;
        worst = @max(worst, steps);
    }
    try testing.expect(worst < 64);
}