diff options
| -rw-r--r-- | 9proc/README.md | 9 | ||||
| -rw-r--r-- | 9proc/docs/LIBRARY.md | 85 | ||||
| -rw-r--r-- | 9proc/src/core.zig | 1181 | ||||
| -rw-r--r-- | 9proc/src/linux/probe.zig | 2 | ||||
| -rw-r--r-- | 9proc/src/scratch.zig | 30 | ||||
| -rwxr-xr-x | 9proc/test/adv_9proc_hostile.py | 125 | ||||
| -rwxr-xr-x | 9proc/test/adv_core_hostile.py | 158 | ||||
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | docs/design.md | 30 | ||||
| -rw-r--r-- | src/fs.zig | 1126 |
10 files changed, 1845 insertions, 904 deletions
diff --git a/9proc/README.md b/9proc/README.md index 0fd3ddb..15177d7 100644 --- a/9proc/README.md +++ b/9proc/README.md @@ -9,7 +9,12 @@ panics. The core (`core`, `vars`) is freestanding: no allocator, no OS, no threads, caller-owned static `Storage`, fixed-capacity tables sized at comptime. It -compiles for `riscv32-freestanding-none`. `scratch` (an in-memory read/write +compiles for `riscv32-freestanding-none`. The tree is a backend of +`cloud9.fs.Server`, the file-server engine every 9P server built on cloud9 +shares: the engine owns fids, walks, permissions and directory cursors; +the core answers its requests from static nodes, exposed variables and +providers, and a provider may answer a read later (`error.Again` parks it +until a later step). `scratch` (an in-memory read/write tree) takes an allocator; `linux` is the platform layer (listeners, a poll loop on one background thread, threads/stacks/registers, memory, breakpoints and panics via `std.debug`). [docs/LIBRARY.md](docs/LIBRARY.md) has the full @@ -19,7 +24,7 @@ contract. 9proc/ build.zig fragment imported by cloud9's root build.zig (steps below) src/root.zig pub const core, vars, scratch, linux; Config, Server(cfg), Provider - src/core.zig Tree/Server engine on cloud9.Server: fids, walks, dir reads, providers + src/core.zig the tree (static nodes, vars, providers) as a backend of cloud9.fs.Server src/vars.zig comptime value renderers (@typeInfo) for /vars src/scratch.zig in-memory read/write tree provider (takes an Allocator) src/freestanding_check.zig root for the riscv32-freestanding-none compile check diff --git a/9proc/docs/LIBRARY.md b/9proc/docs/LIBRARY.md index eef7dad..e0152e0 100644 --- a/9proc/docs/LIBRARY.md +++ b/9proc/docs/LIBRARY.md @@ -24,7 +24,7 @@ Design rules (non-negotiable, they mirror cloud9): ``` 9proc/src/root.zig pub const core, vars, scratch, linux (linux only), Server(cfg) - 9proc/src/core.zig Tree/Server engine on cloud9.Server: fids, walks, dir reads, providers + 9proc/src/core.zig the tree (static nodes, vars, providers) as a backend of cloud9.fs.Server 9proc/src/vars.zig comptime value renderers (@typeInfo) for /vars 9proc/src/scratch.zig in-memory read/write tree provider (takes an Allocator) 9proc/src/linux/probe.zig background thread + poll loop + unix/tcp/fd listeners @@ -51,34 +51,51 @@ pub const Config = struct { /// slots so that reads at arbitrary offsets are consistent. snapshot_slots: u8 = 8, snapshot_bytes: u32 = 16 * 1024, + max_parked: u8 = 8, // reads a provider has parked with error.Again, per connection }; pub fn Server(comptime cfg: Config) type { return struct { pub const Storage = struct { // caller places this in static memory - in: [msize]u8, out: [msize]u8, snapshots: [cfg.snapshot_slots][cfg.snapshot_bytes]u8, + in: [msize]u8, out: [msize]u8, data: [msize]u8, snapshots: [cfg.snapshot_slots][cfg.snapshot_bytes]u8, }; pub const Shared = struct { // state common to all connections (providers, vars) pub fn init(name_ctx: *anyopaque) Shared; pub fn addProvider(s: *Shared, p: Provider) error{Full}!void; pub fn expose(s: *Shared, name: []const u8, ptr: anytype) error{Full}!void; // typed value → /vars/<name> }; - pub const Conn = struct { // one 9P connection, push/step/output like cloud9 + pub const Backend = struct { ... }; // what cloud9.fs.Server knows of the tree: Req, Reply, features + pub const Engine = cloud9.fs.Server(Backend, .{ .fid_capacity = cfg.max_fids, .slot_capacity = cfg.max_parked, ... }); + pub const Conn = struct { // one 9P connection: an Engine plus the tree's per-connection state pub fn init(shared: *Shared, storage: *Storage, msize: u32) Conn; pub fn push(c: *Conn, bytes: []const u8) usize; // feed transport bytes - pub fn step(c: *Conn) error{Protocol}!bool; // handle ≤ 1 request; false = nothing to do + pub fn step(c: *Conn) error{Protocol}!bool; // serve ≤ 1 engine request; false = nothing to do pub fn output(c: *const Conn) []const u8; // bytes to send pub fn wrote(c: *Conn, n: usize) void; pub fn hangup(c: *Conn) void; // drop fids, tell providers + pub fn fidCount(c: *const Conn) usize; }; }; } ``` -`step` drives `cloud9.Server.receive/reply/negotiate` and the backend: the -static tree (comptime-generated from `cfg`: `/README`, `/build/*` via a -`build_options`-like struct passed in `cfg.build`, `/comptime/types/*`, -`/comptime/decls`, `/runtime/fn/*`, `/ctl`, `/vars/*`) plus **providers**. +The core is a **backend of `cloud9.fs.Server`**, the library's file-server +engine (cloud9's `docs/design.md`, "File server engine"): one engine for +every 9P server built on cloud9. The engine owns the fid table (indexed, +`Options.fid_index`, so thousands of fids cost O(1) per lookup), walks, +permission checks, directory cursors, Tflush, and the releases a dropped +connection owes; `Conn` wraps one engine instance and answers its +requests (`lookup`, `getattr`, `setattr`, `open`, `read`, `write`, +`release`, `readdir`) from the tree: the static part (comptime-generated +from `cfg`: `/README`, `/build/*` via a `build_options`-like struct passed +in `cfg.build`, `/comptime/types/*`, `/comptime/decls`, `/runtime/fn/*`, +`/ctl`, `/vars/*`) is served directly, **providers** through their vtable. +The backend declares every optional engine feature (`fs.Features`: +create, remove, wstat, references), which is how Tcreate/Tremove/Twstat +and the one-clunk-per-handle contract below reach providers. `step` +answers the engine's `retry()` and `next()` requests synchronously, one +`next()` per call; a provider that cannot answer yet parks instead (see +"Answering later"). A provider is a runtime vtable mounted at a top-level name. It owns a subtree with its own naming (dynamic directories such as `/threads/<tid>` or @@ -106,23 +123,53 @@ pub const Provider = struct { }; ``` -Error → Rerror text mapping lives in one place in the core, using the Plan 9 -strings 9ns's bridge already understands (`file does not exist`, -`permission denied`, `file already exists`, `directory not empty`, +Error → Rerror text: what the tree or a provider refuses is answered in +`ename`'s Plan 9 strings, which 9ns's bridge understands (`file does not +exist`, `permission denied`, `file already exists`, `directory not empty`, `not a directory`, `is a directory`, `bad offset`, `no space`, `i/o error`, -`not supported`). +`not supported`, `bad command`, `bad value`, `too many open dynamic +files`); what the engine refuses on its own carries cloud9.fs's strings, +the ones Linux v9fs maps back to errnos (`fid unknown or out of range`, +`fid already in use`, `Too many open files in system`, `bad use of fid` +for I/O on an unopened fid or a walk or clone from an open one, `file +already open for I/O`, `bad offset in directory read`, `permission denied` +for an open the walked mode forbids (a directory for writing, OEXEC, a +static file for writing), `wstat prohibited` for any of the fields the +engine owns (type, dev, qid, atime, the owner names) or a length on a +directory, `illegal name`, `Invalid argument` for an Rstat that cannot fit +the msize or a directory read whose count holds no whole record). The +smallest msize is the engine's `fs.msize_min` (217: one full Rwalk); a +Tversion below it ends the connection. Directory reads follow the 9P rule (offset 0 or previous offset+count, never -split a record). Dynamic file reads: on open the content is generated once -into a snapshot slot (`open` runs the generator; `read` serves the slot; a -read at offset 0 regenerates); no free slot → Rerror `too many open dynamic +split a record); the engine encodes the entries from the tree's records, +with uid/gid/muid the attach uname, the modes `dirent_dir_perm`/ +`dirent_file_perm` and length 0 (a stat of the entry gives the real +ones). Dynamic file reads: on open the content is generated once into a +snapshot slot (`open` runs the generator; `read` serves the slot; a read +at offset 0 regenerates); no free slot → Rerror `too many open dynamic files`. Stats of dynamic files report length 0. Qids: static nodes get comptime paths; provider nodes get -`(provider index << 56) | handle`. +`(provider index << 56) | handle` (or `NodeStat.path` in place of the +handle). The engine's node ids are the same numbers, except that +provider ids are offset by one in the top byte, since the engine reads +node 0 as "the node asked about". + +**Answering later.** `Provider.read` may return `error.Again`: the engine +parks the request (`Config.max_parked` per connection; a further one fails +with EAGAIN), the connection goes on serving, and every later `Conn.step` +asks the provider again with the same handle and offset until it answers, +whether at once or on a later step. The fid stays open; a Tflush of a +parked read answers it with `Interrupted system call` before the Rflush; +hangup and Tversion drop it and close the file as usual. Nothing wakes a +connection by itself: the platform layer steps a connection when its +transport moves, so a provider that becomes ready has to make that happen +(an event stream's job, not the core's). Writes cannot park. Static memory: `Server(cfg).Storage` per connection, `Shared` once. No heap. -The core has unit tests driven through `cloud9.Client` in memory (like today). +The core has unit tests driven through `cloud9.Client` in memory, +including a provider that parks. ## Value renderers (`vars.zig`) @@ -252,8 +299,8 @@ the demo's Storage is a global. ## Verification -* Unit tests: core (in-memory client drives every op incl. providers and - snapshots), vars (render/set for every category), scratch, debug (capture +* Unit tests: core (in-memory client drives every op incl. providers, + snapshots and a parked read), vars (render/set for every category), scratch, debug (capture own thread and a helper thread; breakpoint pause/continue on a helper thread; panic record path without holding). * `zig build 9proc-check-freestanding`: compiles `core.zig` + `vars.zig` diff --git a/9proc/src/core.zig b/9proc/src/core.zig index cead8f3..ce71809 100644 --- a/9proc/src/core.zig +++ b/9proc/src/core.zig @@ -1,12 +1,14 @@ -//! The freestanding 9P2000 introspection engine: a static tree generated at +//! The freestanding 9P2000 introspection tree: a static tree generated at //! comptime from a `Config` (README, /build, /comptime, /runtime/fn, /ctl, -//! /vars) plus runtime `Provider`s mounted at the top level, served over a -//! `cloud9.Server` connection. No allocator, no OS, no threads: every buffer is -//! caller-owned (`Storage`, `Shared`, `Conn`), every table is sized at comptime. -//! See docs/LIBRARY.md. +//! /vars) plus runtime `Provider`s mounted at the top level, served as a +//! backend of `cloud9.fs.Server` (the file-server engine, which owns fids, +//! walks, directory cursors, permissions and Tflush). No allocator, no OS, +//! no threads: every buffer is caller-owned (`Storage`, `Shared`, `Conn`), +//! every table is sized at comptime. See docs/LIBRARY.md. const std = @import("std"); const builtin = @import("builtin"); const cloud9 = @import("cloud9"); +const fs = cloud9.fs; const vars = @import("vars.zig"); const Writer = std.Io.Writer; @@ -50,6 +52,8 @@ pub const Config = struct { /// slots so that reads at arbitrary offsets are consistent. snapshot_slots: u8 = 8, snapshot_bytes: u32 = 16 * 1024, + /// Reads a provider has parked with `error.Again`, per connection. + max_parked: u8 = 8, }; /// Attributes of a provider node, filled by `VTable.stat` and `VTable.list`. @@ -85,6 +89,16 @@ pub const NodeStat = struct { /// `clunk(0)` as a no-op. `walk` must accept "." on any node, file or directory /// (a fresh reference to the same node; the core clones fids with it), and ".." /// on directories (except at the root, which the core resolves itself). +/// +/// Answering later: `read` may return `error.Again` when nothing is there +/// yet. The request then parks in the engine (up to `Config.max_parked` per +/// connection; a further one fails with EAGAIN) and every later `Conn.step` +/// asks the provider again, with the same handle and offset, until it +/// answers; the fid stays open. A Tflush of a parked read answers it with +/// "Interrupted system call"; a hangup or Tversion drops it and closes the +/// file as usual. Nothing wakes a connection by itself: the platform layer +/// steps it when its transport moves, so a provider that becomes ready has +/// to make that happen (out of the core's hands). pub const Provider = struct { name: []const u8, ctx: *anyopaque, @@ -94,7 +108,7 @@ pub const Provider = struct { pub const Handle = u64; pub const root: Handle = 0; - pub const Error = error{ NotFound, Exists, Perm, NotDir, IsDir, NotEmpty, BadOffset, NoSpace, Io, Unsupported, Excl }; + pub const Error = error{ NotFound, Exists, Perm, NotDir, IsDir, NotEmpty, BadOffset, NoSpace, Io, Unsupported, Excl, Again }; pub const VTable = struct { walk: *const fn (ctx: *anyopaque, parent: Handle, name: []const u8) Error!Handle, @@ -102,6 +116,7 @@ pub const Provider = struct { /// The `index`-th entry of `dir`; false when done. list: *const fn (ctx: *anyopaque, dir: Handle, index: usize, out: *NodeStat) Error!bool, open: *const fn (ctx: *anyopaque, h: Handle, mode: u8) Error!void, + /// `error.Again` parks the read; see `Provider`. read: *const fn (ctx: *anyopaque, h: Handle, offset: u64, buf: []u8) Error!usize, write: *const fn (ctx: *anyopaque, h: Handle, offset: u64, data: []const u8) Error!usize, /// Returns the new node, already open with `mode`. @@ -117,7 +132,8 @@ pub const Provider = struct { }; }; -/// The Plan 9 error string for any error the engine or a provider can raise. +/// The Plan 9 error string for any error the tree or a provider can raise +/// (the engine's own refusals carry cloud9.fs's strings). pub fn ename(err: anyerror) []const u8 { return switch (err) { error.NotFound, error.NoFile => "file does not exist", @@ -144,10 +160,28 @@ pub fn ename(err: anyerror) []const u8 { error.WriteFailed => "no space in buffer", error.ReplyTooLarge => "reply too large for msize", error.OutOfMemory => "out of memory", + error.Again => "would block", else => "i/o error", }; } +/// The engine errno closest to an error, beside its `ename`. +fn errno(err: anyerror) u16 { + return switch (err) { + error.NotFound, error.NoFile => fs.E.NOENT, + error.Perm, error.Excl => fs.E.PERM, + error.Exists => fs.E.EXIST, + error.NotEmpty => fs.E.NOTEMPTY, + error.NotDir => fs.E.NOTDIR, + error.IsDir => fs.E.ISDIR, + error.BadOffset, error.Invalid, error.BadValue, error.BadCommand, error.BadName => fs.E.INVAL, + error.NoSpace, error.WriteFailed, error.NoSnapshot => fs.E.NOSPC, + error.Unsupported => fs.E.NOSYS, + error.OutOfMemory => fs.E.NOMEM, + else => fs.E.IO, + }; +} + /// A "don't care" Twstat: every field left as it is. pub const stat_dontcare: cloud9.Stat = .{ .type = 0xFFFF, @@ -380,24 +414,26 @@ pub fn Server(comptime cfg: Config) type { comptime { for (flat) |f| if (f.node.kind == .dynamic and f.node.gen == null) @compileError("dynamic node without generator"); - std.debug.assert(cfg.msize >= cloud9.Server.msize_min); - std.debug.assert(cfg.snapshot_slots > 0 and cfg.max_fids > 0); + std.debug.assert(cfg.msize >= fs.msize_min); + std.debug.assert(cfg.snapshot_slots > 0 and cfg.max_fids > 0 and cfg.max_parked > 0); // Provider index 0xFE/0xFF would collide with the var/static qid tags. std.debug.assert(cfg.max_providers < 0xFE); } - // -- qid paths ------------------------------------------------------ + // -- node ids and qid paths ------------------------------------------ const static_tag: u64 = 0xFF << 56; const var_tag: u64 = 0xFE << 56; const handle_mask: u64 = (1 << 56) - 1; + /// The engine's root: static node 0. + const root_id: u64 = static_tag; // -- storage -------------------------------------------------------- /// Per-connection buffers; the caller places one in static memory. pub const Storage = struct { in: [cfg.msize]u8, - out: [cfg.msize]u8, + out: [@max(cfg.msize, 2 * fs.msize_min)]u8, /// Staging area for read replies (directory records, provider and raw reads). data: [cfg.msize]u8, snapshots: [cfg.snapshot_slots][cfg.snapshot_bytes]u8, @@ -426,9 +462,9 @@ pub fn Server(comptime cfg: Config) type { /// Length of the current ctl result (in `ctl_bufs[ctl_cur]`). ctl_len: u32 = 0, ctl_version: u32 = 0, - /// Entropy for the per-connection fid hash. The core mixes in a + /// Entropy for the per-connection fid index. The core mixes in a /// connection counter and buffer addresses; a platform layer with a - /// random source may set this once after `init` to make the seed + /// random source may set this once after `init` to make the salt /// unpredictable even where addresses are static. hash_seed: u32 = 0, conn_seq: u32 = 0, @@ -486,47 +522,44 @@ pub fn Server(comptime cfg: Config) type { return null; } - // -- connection ----------------------------------------------------- + // -- the engine and its backend --------------------------------------- + /// What the engine knows of this tree: the contract types and the + /// capabilities it may ask for. The requests themselves are served + /// by `Conn.serve`. + pub const Backend = struct { + pub const Req = fs.Req; + pub const Reply = fs.Reply; + pub const features: fs.Features = .{ .create = true, .remove = true, .wstat = true, .references = true }; + }; + + /// The file-server engine this tree is a backend of: it owns the fid + /// table, permissions, directory cursors, Tflush and the releases a + /// dropped connection owes. Names are not kept per fid (`getattr` + /// answers them), so a fid costs the same whatever the name length. + pub const Engine = fs.Server(Backend, .{ + .fid_capacity = cfg.max_fids, + .slot_capacity = cfg.max_parked, + .park_data_max = 0, + .name_capacity = 0, + .fid_index = true, + }); + + /// A reference to a node of the tree: the engine's node id decoded. const NodeRef = union(enum) { static: u32, prov: struct { idx: u8, h: Provider.Handle }, @"var": struct { idx: u8, node: u32 }, }; - const Fid = struct { - id: u32 = 0, - used: bool = false, - node: NodeRef = .{ .static = 0 }, - is_dir: bool = true, - open: bool = false, - mode: u8 = 0, - rclose: bool = false, - dir_offset: u64 = 0, - dir_index: usize = 0, - /// Snapshot slot of an open dynamic file. - snap: ?u8 = null, - /// Free-list link, meaningful while `!used`. - next_free: u16 = no_slot, - }; - - const no_slot: u16 = std.math.maxInt(u16); - /// The fid index is an open-addressing (linear probing) table from fid - /// number to a slot of `Conn.fids`, sized to stay at most half full so - /// that lookups are O(1) with any number of fids. - const index_len: usize = std.math.ceilPowerOfTwoAssert(usize, @as(usize, cfg.max_fids) * 2); - const index_mask: usize = index_len - 1; - const index_shift: u5 = @intCast(32 - @as(usize, std.math.log2_int(usize, index_len))); - - /// 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; + fn nodeId(ref: NodeRef) u64 { + return switch (ref) { + .static => |idx| static_tag | idx, + .@"var" => |v| var_tag | (@as(u64, v.idx) << 32) | v.node, + // Provider ids are offset by one: the engine reads node 0 as + // "the node asked about", and provider 0's root would be 0. + .prov => |p| (@as(u64, p.idx + 1) << 56) | (p.h & handle_mask), + }; } /// Everything the engine needs to know about a node for qid/stat. @@ -537,240 +570,166 @@ pub fn Server(comptime cfg: Config) type { atime: u32, mtime: u32, version: u32, + /// The qid path. path: u64, name: []const u8, - fn qid(i: Info) cloud9.Qid { - var t: u8 = if (i.is_dir) cloud9.qtdir else cloud9.qtfile; - if (i.mode & cloud9.dmappend != 0) t |= cloud9.qtappend; - if (i.mode & cloud9.dmexcl != 0) t |= cloud9.qtexcl; - return .{ .type = t, .version = i.version, .path = i.path }; - } - - fn stat(i: Info) cloud9.Stat { + fn attr(i: Info, ref: NodeRef) fs.Attr { + const id = nodeId(ref); return .{ - .type = 0, - .dev = 0, - .qid = i.qid(), - .mode = i.mode, - .atime = i.atime, - .mtime = i.mtime, - .length = i.length, .name = i.name, - .uid = cfg.name, - .gid = cfg.name, - .muid = cfg.name, + .node = id, + .dir = i.is_dir, + .size = i.length, + .mode = @truncate(i.mode), + .mtime = i.mtime, + .atime = i.atime, + .version = i.version, + .path = if (i.path != id) i.path else null, + .append = i.mode & cloud9.dmappend != 0, + .excl = i.mode & cloud9.dmexcl != 0, }; } }; - /// One 9P connection: a cloud9.Server plus a fid table and snapshot slots. + /// A directory entry as the engine's readdir record wants it. + const Entry = struct { path: u64, dir: bool, name: []const u8 }; + + /// The engine's handle of an open file that holds no snapshot slot. + const no_snapshot: u32 = std.math.maxInt(u32); + + /// One 9P connection: the engine plus this tree's per-connection + /// state (snapshot slots). pub const Conn = struct { shared: *Shared, storage: *Storage, - server: cloud9.Server, + engine: Engine, /// Largest msize this connection negotiates. msize_cap: u32, - fids: [cfg.max_fids]Fid = @splat(.{}), - /// XORed into every fid number before hashing so that a client - /// cannot precompute fid numbers that collide (which would turn the - /// index back into a linear scan). - hash_seed: u32, - /// fid number -> slot of `fids` (`no_slot` = empty bucket). - index: [index_len]u16 = @splat(no_slot), - /// 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, - nfids: u16 = 0, slot_used: [cfg.snapshot_slots]bool = @splat(false), slot_len: [cfg.snapshot_slots]u32 = @splat(0), - name_buf: [max_name]u8 = undefined, pub fn init(shared: *Shared, storage: *Storage, msize: u32) Conn { shared.conn_seq +%= 1; const addr = @intFromPtr(storage) ^ (@intFromPtr(shared) << 7); - const seed = fmix32(shared.hash_seed ^ (shared.conn_seq *% 0x9E37_79B1) ^ @as(u32, @truncate(addr)) ^ @as(u32, @truncate(addr >> 16))); + const seed = shared.hash_seed ^ (shared.conn_seq *% 0x9E37_79B1) ^ @as(u32, @truncate(addr)) ^ @as(u32, @truncate(addr >> 16)); + const cap = @max(@min(msize, cfg.msize), fs.msize_min); return .{ .shared = shared, .storage = storage, - .server = .init(.{ .in = &storage.in, .out = &storage.out }), - .msize_cap = @max(@min(msize, cfg.msize), cloud9.Server.msize_min), - .hash_seed = seed, + .engine = .init(.{ .in = storage.in[0..cap], .out = &storage.out, .root = root_id, .seed = seed }), + .msize_cap = cap, }; } - /// Fibonacci hashing of the (seeded) fid number into `index_len` buckets. - fn fidHome(c: *const Conn, id: u32) usize { - return @intCast(((id ^ c.hash_seed) *% 0x9E37_79B1) >> index_shift); - } - /// Feeds transport bytes; returns how many were taken. pub fn push(c: *Conn, bytes: []const u8) usize { - return c.server.push(bytes); + return c.engine.push(bytes); } /// Bytes to send to the client. pub fn output(c: *const Conn) []const u8 { - return c.server.output(); + return c.engine.output(); } pub fn wrote(c: *Conn, n: usize) void { - c.server.wrote(n); + c.engine.wrote(n); + } + + /// Free space in the input buffer (one msize-sized frame at most). + pub fn inputRoom(c: *const Conn) usize { + return c.engine.protocol.in.len - c.engine.protocol.in_len; } /// Drops every fid (telling providers) and kills the session. pub fn hangup(c: *Conn) void { - c.resetFids(); - c.server.hangup(); + c.engine.hangup(); + while (c.engine.next()) |req| c.serve(req); } - /// Handles at most one request. Returns false when more input (or - /// output drainage) is needed. `error.Protocol` is terminal. + /// Serves at most one request of the engine (a 9P request is one + /// or more of them), after re-asking providers about every parked + /// read. Returns false when more input (or output drainage) is + /// needed. `error.Protocol` is terminal. pub fn step(c: *Conn) error{Protocol}!bool { - const req = (c.server.receive() catch return error.Protocol) orelse return false; - defer c.server.release(); - switch (req.msg) { - .tversion => |m| { - c.resetFids(); - c.server.negotiate(@min(m.msize, c.msize_cap), m.version) catch return error.Protocol; - }, - else => { - const reply = c.dispatch(req.msg) catch |e| cloud9.Msg{ .rerror = .{ .ename = ename(e) } }; - c.server.reply(req.tag, reply) catch |e| switch (e) { - // The reply does not fit the negotiated msize (Rstat or a long - // Rwalk at a tiny msize). receive() guarantees room for one - // msize-sized message, so this is never backpressure: answer with - // an Rerror (truncated to fit by cloud9). Rwalk, the only - // variable-size reply that follows a state change, is size-checked - // in walk() before anything is mutated. - error.TooLarge => c.server.reply(req.tag, .{ .rerror = .{ .ename = ename(error.ReplyTooLarge) } }) catch return error.Protocol, - else => return error.Protocol, - }; - }, - } + if (c.engine.protocol.dead) return error.Protocol; + while (c.engine.retry()) |req| c.serve(req); + const req = c.engine.next() orelse { + if (c.engine.protocol.dead) return error.Protocol; + return false; + }; + c.serve(req); + if (c.engine.protocol.dead) return error.Protocol; return true; } /// Number of fids currently held. pub fn fidCount(c: *const Conn) usize { - return c.nfids; + return c.engine.fidCount(); } - fn dispatch(c: *Conn, msg: cloud9.Msg) anyerror!cloud9.Msg { - return switch (msg) { - .tauth => error.AuthNotRequired, - .tattach => |m| c.attach(m), - .tflush => .rflush, - .twalk => |m| c.walk(m), - .topen => |m| c.open(m), - .tcreate => |m| c.create(m), - .tread => |m| c.read(m), - .twrite => |m| c.write(m), - .tclunk => |m| c.clunk(m), - .tremove => |m| c.remove(m), - .tstat => |m| c.stat(m), - .twstat => |m| c.wstat(m), - else => error.Protocol, - }; - } - - // -- fid table -- - - /// The index bucket holding `id`, if any. - fn findBucket(c: *const Conn, id: u32) ?usize { - var pos = c.fidHome(id); - while (true) : (pos = (pos + 1) & index_mask) { - const slot = c.index[pos]; - if (slot == no_slot) return null; - if (c.fids[slot].id == id) return pos; + /// The provider handle a fid holds, if it holds a provider node. + pub fn providerHandle(c: *const Conn, fid: u32) ?Provider.Handle { + for (c.engine.fids) |f| { + if (!f.used or f.orphan or f.fid != fid) continue; + return switch (c.refOf(f.node) orelse return null) { + .prov => |p| p.h, + else => null, + }; } + return null; } - fn findFid(c: *Conn, id: u32) ?*Fid { - const pos = c.findBucket(id) orelse return null; - return &c.fids[c.index[pos]]; - } - - fn allocFid(c: *Conn, id: u32) !*Fid { - if (c.findBucket(id) != null) return error.FidInUse; - if (c.nfids >= cfg.max_fids) return error.TooManyFids; - const slot: u16 = if (c.free_head != no_slot) blk: { - const slot = c.free_head; - c.free_head = c.fids[slot].next_free; - break :blk slot; - } else blk: { - const slot = c.high_water; - c.high_water += 1; - break :blk slot; - }; - c.fids[slot] = .{ .id = id, .used = true }; - var pos = c.fidHome(id); - while (c.index[pos] != no_slot) pos = (pos + 1) & index_mask; - c.index[pos] = slot; - c.nfids += 1; - return &c.fids[slot]; - } - - /// Removes `id` from the index (backward-shift deletion: no tombstones). - fn unlinkFid(c: *Conn, id: u32) void { - var i = c.findBucket(id).?; - var j = i; - while (true) { - j = (j + 1) & index_mask; - const slot = c.index[j]; - if (slot == no_slot) break; - const k = c.fidHome(c.fids[slot].id); - // The entry at j may move into the hole at i unless its home - // lies in the cyclic interval (i, j]. - const stays = if (i <= j) (k > i and k <= j) else (k > i or k <= j); - if (!stays) { - c.index[i] = slot; - i = j; - } - } - c.index[i] = no_slot; - } + // -- serving the engine -- - /// Releases everything a fid holds; the slot stays allocated. - fn dropContents(c: *Conn, f: *Fid) void { - if (f.snap) |s| c.slot_used[s] = false; - f.snap = null; - if (f.node == .prov) { - const p = c.shared.providers[f.node.prov.idx]; - if (f.open) if (p.vtable.close) |close| close(p.ctx, f.node.prov.h); - if (f.rclose and f.open) if (p.vtable.remove) |rm| rm(p.ctx, f.node.prov.h) catch {}; - p.vtable.clunk(p.ctx, f.node.prov.h); - } - f.open = false; - f.rclose = false; + fn serve(c: *Conn, req: fs.Req) void { + var bytes: []const u8 = ""; + const reply = c.dispatch(req, &bytes) catch |e| failing(req.tag, e); + c.engine.reply(&reply, bytes); } - fn freeFid(c: *Conn, f: *Fid) void { - c.dropContents(f); - c.unlinkFid(f.id); - const slot: u16 = @intCast((@intFromPtr(f) - @intFromPtr(&c.fids)) / @sizeOf(Fid)); - f.* = .{ .next_free = c.free_head }; - c.free_head = slot; - c.nfids -= 1; + fn failing(tag: u64, e: anyerror) fs.Reply { + if (e == error.Again) return .{ .tag = tag, .status = .again }; + return .{ .tag = tag, .status = .err, .errno = errno(e), .ename = ename(e) }; } - fn resetFids(c: *Conn) void { - for (c.fids[0..c.high_water]) |*f| { - if (f.used) c.dropContents(f); - f.* = .{}; + fn dispatch(c: *Conn, req: fs.Req, bytes: *[]const u8) anyerror!fs.Reply { + const ref = c.refOf(req.node) orelse return error.NotFound; + switch (req.op) { + .lookup => { + const l = try c.lookup(ref, req.data); + return .{ .tag = req.tag, .attr = l.info.attr(l.ref) }; + }, + .getattr => return .{ .tag = req.tag, .attr = (try c.info(ref)).attr(ref) }, + .setattr => return c.setattr(req, ref), + .open => return if (req.create) c.create(req, ref) else c.open(req, ref), + .read => return c.read(req, ref, bytes), + .readdir => return c.readDir(req, ref, bytes), + .write => return c.write(req, ref), + .release => return c.release(req, ref), } - @memset(&c.index, no_slot); - c.free_head = no_slot; - c.high_water = 0; - c.nfids = 0; } - /// Releases a provider handle that is not held by any fid. - fn releaseRef(c: *Conn, ref: NodeRef) void { - if (ref == .prov) { - const p = c.shared.providers[ref.prov.idx]; - p.vtable.clunk(p.ctx, ref.prov.h); + /// Decodes an engine node id; null for one this tree never issued. + fn refOf(c: *const Conn, id: u64) ?NodeRef { + const top: u8 = @intCast(id >> 56); + switch (top) { + 0xFF => { + const idx = id & handle_mask; + if (idx >= flat_len) return null; + return .{ .static = @intCast(idx) }; + }, + 0xFE => { + const vidx: u8 = @truncate(id >> 32); + const node: u32 = @truncate(id); + if ((id >> 40) & 0xFFFF != 0 or vidx >= c.shared.nvars) return null; + if (node >= c.shared.vars[vidx].vt.nodes.len) return null; + return .{ .@"var" = .{ .idx = vidx, .node = node } }; + }, + else => { + if (top == 0 or top - 1 >= c.shared.nprov) return null; + return .{ .prov = .{ .idx = top - 1, .h = id & handle_mask } }; + }, } } @@ -835,6 +794,10 @@ pub fn Server(comptime cfg: Config) type { } } + fn provPath(idx: u8, h: Provider.Handle, st: NodeStat) u64 { + return (@as(u64, idx) << 56) | ((if (st.path != 0) st.path else h) & handle_mask); + } + fn provInfo(pr: Provider, idx: u8, h: Provider.Handle, st: NodeStat) Info { return .{ .is_dir = st.isDir(), @@ -843,24 +806,23 @@ pub fn Server(comptime cfg: Config) type { .atime = st.atime, .mtime = st.mtime, .version = st.version, - .path = (@as(u64, idx) << 56) | ((if (st.path != 0) st.path else h) & handle_mask), + .path = provPath(idx, h, st), .name = if (h == Provider.root) pr.name else st.name, }; } - /// Copies `st.name` into the connection so the reply cannot dangle. - fn pinName(c: *Conn, st: cloud9.Stat) cloud9.Stat { - var out = st; - const n = @min(st.name.len, c.name_buf.len); - @memcpy(c.name_buf[0..n], st.name[0..n]); - out.name = c.name_buf[0..n]; - return out; + /// Releases a provider handle that no fid holds. + fn releaseRef(c: *Conn, ref: NodeRef) void { + if (ref == .prov) { + const p = c.shared.providers[ref.prov.idx]; + p.vtable.clunk(p.ctx, ref.prov.h); + } } const Looked = struct { ref: NodeRef, info: Info }; /// Resolves `name` in the directory `ref`. A returned provider ref - /// is a fresh handle the caller must release or retain. + /// is a fresh handle the engine will release exactly once. fn lookup(c: *Conn, ref: NodeRef, name: []const u8) !Looked { switch (ref) { .static => |idx| { @@ -909,34 +871,39 @@ pub fn Server(comptime cfg: Config) type { } } - /// The i-th entry of directory `ref` as a Stat, or null past the end. - /// The name borrows either static memory or the provider's NodeStat. - fn entryStat(c: *Conn, ref: NodeRef, i: usize) !?cloud9.Stat { + /// The i-th entry of directory `ref`, or null past the end. The + /// name borrows static memory or the provider's NodeStat. + fn entry(c: *Conn, ref: NodeRef, i: usize) !?Entry { switch (ref) { .static => |idx| { const f = flat[idx]; if (f.node.kind == .vars) { if (i >= c.shared.nvars) return null; - return (try c.info(.{ .@"var" = .{ .idx = @intCast(i), .node = 0 } })).stat(); + return .{ .path = var_tag | (@as(u64, i) << 32), .dir = true, .name = c.shared.vars[i].name }; + } + if (i < f.count) { + const ci = f.first + @as(u32, @intCast(i)); + return .{ .path = static_tag | ci, .dir = flat[ci].node.isDir(), .name = flat[ci].node.name }; } - if (i < f.count) return (try c.info(.{ .static = f.first + @as(u32, @intCast(i)) })).stat(); if (idx == 0) { const pi = i - f.count; if (pi >= c.shared.nprov) return null; - return (try c.info(.{ .prov = .{ .idx = @intCast(pi), .h = Provider.root } })).stat(); + return .{ .path = @as(u64, pi) << 56, .dir = true, .name = c.shared.providers[pi].name }; } return null; }, .@"var" => |v| { - const n = c.shared.vars[v.idx].vt.nodes[v.node]; + const vt = c.shared.vars[v.idx].vt; + const n = vt.nodes[v.node]; if (i >= n.count) return null; - return (try c.info(.{ .@"var" = .{ .idx = v.idx, .node = n.first + @as(u32, @intCast(i)) } })).stat(); + const ci = n.first + @as(u32, @intCast(i)); + return .{ .path = var_tag | (@as(u64, v.idx) << 32) | ci, .dir = vt.nodes[ci].isDir(), .name = vt.nodes[ci].name }; }, .prov => |p| { const pr = c.provider(p.idx); var st: NodeStat = .{ .mode = 0 }; if (!try pr.vtable.list(pr.ctx, p.h, i, &st)) return null; - return provInfo(pr, p.idx, st.handle, st).stat(); + return .{ .path = provPath(p.idx, st.handle, st), .dir = st.isDir(), .name = st.name }; }, } } @@ -951,12 +918,11 @@ pub fn Server(comptime cfg: Config) type { return error.NoSnapshot; } - /// (Re)generates the content of a dynamic file into its slot. - fn generate(c: *Conn, f: *Fid) !void { - const s = f.snap.?; + /// (Re)generates the content of a dynamic file into slot `s`. + fn generate(c: *Conn, ref: NodeRef, s: u8) !void { var w: Writer = .fixed(&c.storage.snapshots[s]); c.slot_len[s] = 0; - switch (f.node) { + switch (ref) { .static => |idx| try flat[idx].node.gen.?(c.shared.ctx, &w), .@"var" => |v| { const n = c.shared.vars[v.idx].vt.nodes[v.node]; @@ -983,162 +949,85 @@ pub fn Server(comptime cfg: Config) type { }; } - // -- request handlers -- - - fn attach(c: *Conn, m: anytype) !cloud9.Msg { - const f = try c.allocFid(m.fid); - f.node = .{ .static = 0 }; - f.is_dir = true; - return .{ .rattach = .{ .qid = (try c.info(f.node)).qid() } }; + fn snapshot(c: *Conn, handle: u32) []const u8 { + return c.storage.snapshots[handle][0..c.slot_len[handle]]; } - fn walk(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - if (m.newfid != m.fid and c.findFid(m.newfid) != null) return error.FidInUse; - if (m.newfid != m.fid and c.nfids >= cfg.max_fids) return error.TooManyFids; - if (m.nwname > 0 and f.open) return error.AlreadyOpen; - // Cloning a fid onto itself changes nothing; in particular it must not - // close an open fid or discard generated content. - if (m.nwname == 0 and m.newfid == m.fid) return .{ .rwalk = .{ .nwqid = 0 } }; - // A full Rwalk must fit the negotiated msize; check before binding anything. - if (cloud9.header_len + 2 + cloud9.qid_len * @as(usize, m.nwname) > c.server.msize) return error.ReplyTooLarge; - var cur = f.node; - var cur_is_dir = f.is_dir; - var held = false; // cur is a provider handle obtained here, not the fid's - var reply: cloud9.Msg = .{ .rwalk = .{ .nwqid = 0 } }; - const names = m.wname[0..m.nwname]; - for (names, 0..) |name, i| { - if (!cur_is_dir) { - if (i == 0) return error.NotDir; - break; - } - const next = c.lookup(cur, name) catch |e| { - if (i == 0) return e; - break; - }; - if (held) c.releaseRef(cur); - cur = next.ref; - cur_is_dir = next.info.is_dir; - held = cur == .prov; - reply.rwalk.wqid[i] = next.info.qid(); - reply.rwalk.nwqid += 1; - } - if (reply.rwalk.nwqid != names.len) { - if (held) c.releaseRef(cur); - return reply; - } - if (names.len == 0 and cur == .prov) { - // A clone of a provider handle needs its own reference. - const dup = try c.lookup(cur, "."); - cur = dup.ref; - cur_is_dir = dup.info.is_dir; - held = true; - } - const target = if (m.newfid == m.fid) f else c.allocFid(m.newfid) catch |e| { - if (held) c.releaseRef(cur); - return e; - }; - if (target == f) c.dropContents(f); - target.node = cur; - target.is_dir = cur_is_dir; - return reply; - } + // -- request handlers -- - fn open(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - if (f.open) return error.AlreadyOpen; - const acc = m.mode & 3; + fn open(c: *Conn, req: fs.Req, ref: NodeRef) !fs.Reply { + const mode = req.omode; + const acc = mode & 3; const want_write = acc == cloud9.owrite or acc == cloud9.ordwr; - const trunc = m.mode & cloud9.otrunc != 0; - if (f.is_dir and (want_write or trunc)) return error.IsDir; - switch (f.node) { + const trunc = mode & cloud9.otrunc != 0; + switch (ref) { .static => |idx| switch (flat[idx].node.kind) { .dir, .vars, .ctl => {}, .static, .dynamic => if (want_write or trunc) return error.Perm, }, .@"var" => |v| { const n = c.shared.vars[v.idx].vt.nodes[v.node]; - if ((want_write or trunc) and !n.writable()) return error.Perm; + if (n.isDir()) { + if (want_write or trunc) return error.IsDir; + } else if ((want_write or trunc) and !n.writable()) return error.Perm; }, .prov => |p| { const pr = c.provider(p.idx); - try pr.vtable.open(pr.ctx, p.h, m.mode); + try pr.vtable.open(pr.ctx, p.h, mode); }, } - const qid = (c.info(f.node) catch |e| { + const i = c.info(ref) catch |e| { // The provider's open succeeded but its stat did not: undo the open. - if (f.node == .prov) { - const pr = c.provider(f.node.prov.idx); - if (pr.vtable.close) |close| close(pr.ctx, f.node.prov.h); + if (ref == .prov) { + const pr = c.provider(ref.prov.idx); + if (pr.vtable.close) |close| close(pr.ctx, ref.prov.h); } return e; - }).qid(); - if (c.isDynamic(f.node)) { - f.snap = try c.takeSlot(); - c.generate(f) catch |e| { - c.slot_used[f.snap.?] = false; - f.snap = null; - if (f.node == .prov) unreachable; + }; + var handle: u32 = no_snapshot; + if (c.isDynamic(ref)) { + const s = try c.takeSlot(); + c.generate(ref, s) catch |e| { + c.slot_used[s] = false; return e; }; + handle = s; } - f.open = true; - f.mode = m.mode; - f.rclose = m.mode & cloud9.orclose != 0; - f.dir_offset = 0; - f.dir_index = 0; - return .{ .ropen = .{ .qid = qid, .iounit = 0 } }; + return .{ .tag = req.tag, .attr = i.attr(ref), .handle = handle }; } - fn create(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - if (f.open) return error.AlreadyOpen; - const p = switch (f.node) { + fn create(c: *Conn, req: fs.Req, ref: NodeRef) !fs.Reply { + const p = switch (ref) { .prov => |p| p, else => return error.Perm, }; - if (!f.is_dir) return error.NotDir; const pr = c.provider(p.idx); const create_fn = pr.vtable.create orelse return error.Perm; - try validName(m.name); - const is_dir = m.perm & cloud9.dmdir != 0; - const acc = m.mode & 3; - if (is_dir and (acc != cloud9.oread or m.mode & cloud9.otrunc != 0)) return error.IsDir; - const h = try create_fn(pr.ctx, p.h, m.name, m.perm, m.mode); + try validName(req.data); + const h = try create_fn(pr.ctx, p.h, req.data, req.perm, req.omode); const node: NodeRef = .{ .prov = .{ .idx = p.idx, .h = h } }; - const qid = (c.info(node) catch |e| { + const i = c.info(node) catch |e| { if (pr.vtable.close) |close| close(pr.ctx, h); pr.vtable.clunk(pr.ctx, h); return e; - }).qid(); - c.dropContents(f); - f.node = node; - f.is_dir = is_dir; - f.open = true; - f.mode = m.mode; - f.rclose = m.mode & cloud9.orclose != 0; - f.dir_offset = 0; - f.dir_index = 0; - return .{ .rcreate = .{ .qid = qid, .iounit = 0 } }; + }; + return .{ .tag = req.tag, .attr = i.attr(node), .handle = no_snapshot }; } - fn read(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - if (!f.open or (f.mode & 3) == cloud9.owrite) return error.NotOpen; - const count: usize = @min(m.count, c.server.msize -| cloud9.iohdrsz, c.storage.data.len); - if (f.is_dir) return c.readDir(f, m.offset, count); + fn read(c: *Conn, req: fs.Req, ref: NodeRef, bytes: *[]const u8) !fs.Reply { const data = &c.storage.data; - const src: []const u8 = switch (f.node) { + const count: usize = @min(req.size, data.len); + const src: []const u8 = switch (ref) { .static => |idx| blk: { const n = flat[idx].node; switch (n.kind) { .static => break :blk n.content, .ctl => break :blk c.shared.ctlResult(), .dynamic => { - if (m.offset == 0) try c.generate(f); - break :blk c.storage.snapshots[f.snap.?][0..c.slot_len[f.snap.?]]; + if (req.off == 0) try c.generate(ref, @intCast(req.handle)); + break :blk c.snapshot(req.handle); }, - .dir, .vars => unreachable, + .dir, .vars => return error.IsDir, } }, .@"var" => |v| blk: { @@ -1146,72 +1035,75 @@ pub fn Server(comptime cfg: Config) type { switch (n.kind) { .type_name, .size => break :blk n.content, .value, .addr => { - if (m.offset == 0) try c.generate(f); - break :blk c.storage.snapshots[f.snap.?][0..c.slot_len[f.snap.?]]; + if (req.off == 0) try c.generate(ref, @intCast(req.handle)); + break :blk c.snapshot(req.handle); }, .raw => break :blk c.varBase(v.idx, v.node)[0..n.size], - .dir, .fields => unreachable, + .dir, .fields => return error.IsDir, } }, .prov => |p| { const pr = c.provider(p.idx); - const n = try pr.vtable.read(pr.ctx, p.h, m.offset, data[0..count]); - return .{ .rread = .{ .data = data[0..@min(n, count)] } }; + const n = try pr.vtable.read(pr.ctx, p.h, req.off, data[0..count]); + bytes.* = data[0..@min(n, count)]; + return .{ .tag = req.tag }; }, }; - if (m.offset >= src.len) return .{ .rread = .{ .data = "" } }; - const off: usize = @intCast(m.offset); + if (req.off >= src.len) return .{ .tag = req.tag }; + const off: usize = @intCast(req.off); const n = @min(count, src.len - off); - if (f.node == .@"var" and c.shared.vars[f.node.@"var".idx].vt.nodes[f.node.@"var".node].kind == .raw) { + if (ref == .@"var" and c.shared.vars[ref.@"var".idx].vt.nodes[ref.@"var".node].kind == .raw) { // Copy out of the variable so the reply does not read live memory twice. @memcpy(data[0..n], src[off..][0..n]); - return .{ .rread = .{ .data = data[0..n] } }; + bytes.* = data[0..n]; + } else { + bytes.* = src[off..][0..n]; } - return .{ .rread = .{ .data = src[off..][0..n] } }; + return .{ .tag = req.tag }; } - fn readDir(c: *Conn, f: *Fid, offset: u64, count: usize) !cloud9.Msg { - if (offset == 0) { - f.dir_offset = 0; - f.dir_index = 0; - } else if (offset != f.dir_offset) return error.BadOffset; + /// Stages `node:u64le dir:u8 len:u8 name` records from entry + /// `req.off` on, about as many as the engine can fit in `req.size`. + fn readDir(c: *Conn, req: fs.Req, ref: NodeRef, bytes: *[]const u8) !fs.Reply { const data = &c.storage.data; - var used: usize = 0; - var i = f.dir_index; - while (try c.entryStat(f.node, i)) |st| : (i += 1) { - const rec = st.encode(data[used..count]) catch |e| switch (e) { - error.NoSpace => break, - else => return error.Io, - }; - used += rec.len; + const who = c.engine.uname_len; + var n: usize = 0; + var est: usize = 0; + var i: usize = @intCast(req.off); + while (est < req.size) : (i += 1) { + const e = (try c.entry(ref, i)) orelse break; + if (e.name.len > 255 or n + 10 + e.name.len > data.len) break; + std.mem.writeInt(u64, data[n..][0..8], e.path, .little); + data[n + 8] = @intFromBool(e.dir); + data[n + 9] = @intCast(e.name.len); + @memcpy(data[n + 10 ..][0..e.name.len], e.name); + n += 10 + e.name.len; + est += cloud9.stat_fixed + 2 + e.name.len + 3 * who; } - f.dir_offset += used; - f.dir_index = i; - return .{ .rread = .{ .data = data[0..used] } }; + bytes.* = data[0..n]; + return .{ .tag = req.tag }; } - fn write(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - const acc = f.mode & 3; - if (!f.open or (acc != cloud9.owrite and acc != cloud9.ordwr)) return error.NotOpen; - if (f.is_dir) return error.IsDir; - switch (f.node) { + fn write(c: *Conn, req: fs.Req, ref: NodeRef) !fs.Reply { + switch (ref) { .static => |idx| switch (flat[idx].node.kind) { - .ctl => try c.ctlCommand(m.data), + .ctl => try c.ctlCommand(req.data), + .dir, .vars => return error.IsDir, else => return error.Perm, }, .@"var" => |v| { const n = c.shared.vars[v.idx].vt.nodes[v.node]; + if (n.isDir()) return error.IsDir; const set = n.set orelse return error.Perm; - try set(c.varBase(v.idx, v.node), m.data); + try set(c.varBase(v.idx, v.node), req.data); }, .prov => |p| { const pr = c.provider(p.idx); - const n = try pr.vtable.write(pr.ctx, p.h, m.offset, m.data); - return .{ .rwrite = .{ .count = @intCast(@min(n, m.data.len)) } }; + const n = try pr.vtable.write(pr.ctx, p.h, req.off, req.data); + return .{ .tag = req.tag, .written = @intCast(@min(n, req.data.len)) }; }, } - return .{ .rwrite = .{ .count = @intCast(m.data.len) } }; + return .{ .tag = req.tag, .written = @intCast(req.data.len) }; } /// Runs `cfg.ctl`; on success its output becomes the ctl result. @@ -1227,60 +1119,45 @@ pub fn Server(comptime cfg: Config) type { s.ctl_version +%= 1; } - fn clunk(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - c.freeFid(f); - return .rclunk; - } - - fn remove(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - defer c.freeFid(f); // Tremove always clunks - f.rclose = false; - switch (f.node) { - .prov => |p| { - const pr = c.provider(p.idx); - const rm = pr.vtable.remove orelse return error.Perm; - try rm(pr.ctx, p.h); - }, - else => return error.Perm, - } - return .rremove; - } - - fn stat(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - return .{ .rstat = .{ .stat = c.pinName((try c.info(f.node)).stat()) } }; - } - - fn wstat(c: *Conn, m: anytype) !cloud9.Msg { - const f = c.findFid(m.fid) orelse return error.UnknownFid; - const p = switch (f.node) { + /// A wstat, or the truncation hint of an OTRUNC open (which the + /// provider's `open` performs itself; nothing to do here). + fn setattr(c: *Conn, req: fs.Req, ref: NodeRef) !fs.Reply { + if (!req.set.any()) return .{ .tag = req.tag }; + const p = switch (ref) { .prov => |p| p, else => return error.Perm, }; const pr = c.provider(p.idx); const ws = pr.vtable.wstat orelse return error.Perm; - const cur = try c.info(f.node); - const st = m.stat; - const q = cur.qid(); - // Fields we cannot change must be "don't care" or unchanged. - if (st.type != 0xFFFF and st.type != 0) return error.Perm; - if (st.dev != 0xFFFF_FFFF and st.dev != 0) return error.Perm; - if (st.qid.type != 0xFF and st.qid.type != q.type) return error.Perm; - if (st.qid.version != 0xFFFF_FFFF and st.qid.version != q.version) return error.Perm; - if (st.qid.path != 0xFFFF_FFFF_FFFF_FFFF and st.qid.path != q.path) return error.Perm; - if (st.uid.len != 0 and !std.mem.eql(u8, st.uid, cfg.name)) return error.Perm; - if (st.gid.len != 0 and !std.mem.eql(u8, st.gid, cfg.name)) return error.Perm; - if (st.muid.len != 0 and !std.mem.eql(u8, st.muid, cfg.name)) return error.Perm; - if (st.name.len != 0 and !std.mem.eql(u8, st.name, cur.name)) { - if (p.h == Provider.root) return error.Perm; - try validName(st.name); - } - if (st.length != 0xFFFF_FFFF_FFFF_FFFF and st.length != cur.length and cur.is_dir) return error.IsDir; - if (st.mode != 0xFFFF_FFFF and (st.mode & cloud9.dmdir) != (cur.mode & cloud9.dmdir)) return error.Perm; + if (req.set.name and p.h == Provider.root) return error.Perm; + var st = stat_dontcare; + if (req.set.name) st.name = req.data; + if (req.set.mode) st.mode = req.perm; + if (req.set.mtime) st.mtime = req.mtime; + if (req.set.length) st.length = req.length; try ws(pr.ctx, p.h, &st); - return .rwstat; + return .{ .tag = req.tag, .attr = (try c.info(ref)).attr(ref) }; + } + + /// The engine lets go of a reference: closes the open handle it + /// came with, removes the node on Tremove or ORCLOSE, and clunks + /// the provider handle exactly once. + fn release(c: *Conn, req: fs.Req, ref: NodeRef) !fs.Reply { + if (req.opened and req.handle != no_snapshot) c.slot_used[req.handle] = false; + switch (ref) { + .prov => |p| { + const pr = c.provider(p.idx); + if (req.opened) if (pr.vtable.close) |close| close(pr.ctx, p.h); + var result: anyerror!void = {}; + if (req.remove) { + if (pr.vtable.remove) |rm| result = rm(pr.ctx, p.h) else result = error.Perm; + } + pr.vtable.clunk(pr.ctx, p.h); + try result; + }, + else => if (req.remove) return error.Perm, + } + return .{ .tag = req.tag }; } }; @@ -1321,29 +1198,35 @@ pub fn Server(comptime cfg: Config) type { try testing.expectEqualStrings("9P2000", v.version.version); } - /// One round trip; the result borrows the client input buffer until the next call. - pub fn rpc(h: *Harness, req: cloud9.Client.Request) !cloud9.Client.Result { - _ = try h.client.submit(req); + /// Moves bytes both ways and steps the connection until nothing + /// moves; true when anything did. + pub fn pump(h: *Harness) !bool { + var moved = false; while (true) { - var moved = false; + var again = false; while (h.client.output().len > 0) { const k = h.conn.push(h.client.output()); - h.client.wrote(k); - moved = moved or k > 0; - while (try h.conn.step()) {} - while (h.conn.output().len > 0) { - const n = h.client.push(h.conn.output()); - h.conn.wrote(n); - moved = moved or n > 0; - } if (k == 0) break; + h.client.wrote(k); + again = true; } - while (try h.conn.step()) {} + while (try h.conn.step()) again = true; while (h.conn.output().len > 0) { const n = h.client.push(h.conn.output()); + if (n == 0) break; h.conn.wrote(n); - moved = moved or n > 0; + again = true; } + if (!again) return moved; + moved = true; + } + } + + /// One round trip; the result borrows the client input buffer until the next call. + pub fn rpc(h: *Harness, req: cloud9.Client.Request) !cloud9.Client.Result { + _ = try h.client.submit(req); + while (true) { + const moved = try h.pump(); if (h.client.take()) |done| return done.result; if (!moved) return error.Stuck; } @@ -1449,6 +1332,21 @@ pub fn Server(comptime cfg: Config) type { const testing = std.testing; +// The engine's own Rerror strings, for the conditions it decides itself. +const e_unknown_fid = fs.e_unknown_fid; +const e_fid_in_use = fs.e_fid_in_use; +const e_too_many_fids = fs.e_too_many_fids; +const e_bad_use = fs.e_bad_use; +const e_already_open = fs.e_already_open; +const e_bad_offset = fs.e_bad_offset; +const e_perm = fs.e_perm; +const e_not_dir = fs.e_not_dir; +const e_wstat = fs.e_wstat; +const e_illegal_name = fs.e_illegal_name; +const e_small_msize = fs.e_small_msize; +const e_count_small = fs.e_count_small; +const e_interrupted = fs.e_interrupted; + const TestBuild = struct { pub const zig_version: []const u8 = builtin.zig_version_string; pub const target: []const u8 = "test-target"; @@ -1537,12 +1435,20 @@ const test_cfg: Config = .{ .max_vars = 4, .snapshot_slots = 2, .snapshot_bytes = 512, + .max_parked = 2, }; const TS = Server(test_cfg); +/// Whether `fid` is open, read from the engine's table. +fn isOpen(c: *const TS.Conn, fid: u32) bool { + for (c.engine.fids) |f| if (f.used and !f.orphan and f.fid == fid) return f.open; + return false; +} + /// A small in-memory provider: /prov/{hello,dir/{inner}} with create/remove/wstat, -/// counting every handle reference so tests can check clunk discipline. +/// counting every handle reference so tests can check clunk discipline. A +/// read of `hello` parks (error.Again) while `park` is set. const TestProv = struct { const max_nodes = 16; const Entry = struct { @@ -1565,8 +1471,10 @@ const TestProv = struct { nodes: [max_nodes]Entry = @splat(.{}), total_refs: u32 = 0, clunks: u32 = 0, + reads: u32 = 0, fail_io: bool = false, fail_stat: bool = false, + park: bool = false, fn init() TestProv { var p: TestProv = .{}; @@ -1664,6 +1572,8 @@ const TestProv = struct { fn read(ctx: *anyopaque, h: Provider.Handle, offset: u64, buf: []u8) Provider.Error!usize { const p = self(ctx); const e = try p.node(h); + p.reads += 1; + if (p.park and h == 1) return error.Again; if (offset >= e.len) return 0; const n = @min(buf.len, e.len - @as(usize, @intCast(offset))); @memcpy(buf[0..n], e.data[@intCast(offset)..][0..n]); @@ -1799,16 +1709,21 @@ test "README, /build and the static tree read as expected" { try testing.expectEqual(@as(usize, 7), names.len); // static files are read-only; the static tree admits no creates or removes try x.h.walkTo(1, &.{ "build", "target" }); - try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.owrite } }, "permission denied"); + try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.owrite } }, e_perm); try x.h.expectFail(.{ .remove = .{ .fid = 1 } }, "permission denied"); try x.h.walkTo(2, &.{"build"}); - try x.h.expectFail(.{ .create = .{ .fid = 2, .name = "nope", .perm = 0o644, .mode = cloud9.owrite } }, "permission denied"); - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = stat_dontcare } }, "permission denied"); + try x.h.expectFail(.{ .create = .{ .fid = 2, .name = "nope", .perm = 0o644, .mode = cloud9.owrite } }, e_perm); + // a wstat that changes nothing is answered by the engine without asking + _ = try x.h.ok(.{ .wstat = .{ .fid = 2, .stat = stat_dontcare } }); + var ws = stat_dontcare; + ws.mtime = 5; + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, "permission denied"); const st = try x.h.ok(.{ .stat = .{ .fid = 2 } }); try testing.expectEqualStrings("build", st.stat.name); try testing.expectEqualStrings("tester", st.stat.uid); try testing.expect(st.stat.qid.type & cloud9.qtdir != 0); try testing.expectEqual(TS.build_secs, st.stat.mtime); + try testing.expectEqual(TS.build_secs, st.stat.atime); try testing.expectEqual(@as(u32, 0), parseIso8601("1970-01-01T00:00:00Z").?); try testing.expectEqual(@as(?u32, null), parseIso8601("unknown")); } @@ -1873,7 +1788,7 @@ test "runtime/fn calls the function at open and at each read from offset 0" { try x.h.walkTo(4, &.{ "runtime", "fn", "fib30" }); _ = try x.h.ok(.{ .open = .{ .fid = 4, .mode = cloud9.oread } }); _ = try x.h.ok(.{ .clunk = .{ .fid = 1 } }); - _ = try x.h.ok(.{ .walk = .{ .fid = 4, .newfid = 5, .names = &.{} } }); + try x.h.walkTo(5, &.{ "runtime", "fn", "fib30" }); _ = try x.h.ok(.{ .open = .{ .fid = 5, .mode = cloud9.oread } }); } @@ -1895,14 +1810,13 @@ test "snapshot slot exhaustion is an Rerror and clunk frees the slot" { _ = try x.h.ok(.{ .open = .{ .fid = 3, .mode = cloud9.oread } }); const r = try x.h.ok(.{ .read = .{ .fid = 3, .offset = 0, .count = 100 } }); try testing.expectEqualStrings("7", r.read); - // cloning an open fid onto itself keeps it open and its content - const w = try x.h.ok(.{ .walk = .{ .fid = 3, .newfid = 3, .names = &.{} } }); - try testing.expectEqual(@as(u16, 0), w.walk.nwqid); + // an open fid cannot be walked from, not even cloned, and stays open + try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 3, .names = &.{} } }, e_bad_use); + try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{} } }, e_bad_use); + try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{".."} } }, e_bad_use); const r2 = try x.h.ok(.{ .read = .{ .fid = 3, .offset = 0, .count = 100 } }); try testing.expectEqualStrings("7", r2.read); - try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{".."} } }, "file already open"); - _ = try x.h.ok(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{} } }); - try x.h.expectFail(.{ .read = .{ .fid = 4, .offset = 0, .count = 100 } }, "file not open"); + try x.h.expectFail(.{ .read = .{ .fid = 4, .offset = 0, .count = 100 } }, e_unknown_fid); } test "ctl round trip" { @@ -1946,7 +1860,7 @@ test "ctl round trip" { try testing.expectEqual(@as(u64, 0), (try x.h.ok(.{ .stat = .{ .fid = 1 } })).stat.length); // Tversion resets the ctl fid like any other try x.h.version(4096); - try x.h.expectFail(.{ .clunk = .{ .fid = 1 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 1 } }, e_unknown_fid); } test "auth is not required and flush is answered" { @@ -1956,7 +1870,7 @@ test "auth is not required and flush is answered" { try x.h.expectFail(.{ .auth = .{ .afid = 5, .uname = "tester" } }, "authentication not required"); const f = try x.h.ok(.{ .flush = .{ .oldtag = 1 } }); try testing.expect(f == .flush); - try x.h.expectFail(.{ .attach = .{ .fid = 0, .uname = "tester" } }, "fid in use"); + try x.h.expectFail(.{ .attach = .{ .fid = 0, .uname = "tester" } }, e_fid_in_use); } test "vars: value/type/size/addr/raw, fields and writes" { @@ -2027,24 +1941,24 @@ test "vars: value/type/size/addr/raw, fields and writes" { try testing.expectEqualStrings("value", a_st.stat.name); // non-scalar values, type/size/addr/raw and directories are read-only try x.h.walkTo(3, &.{ "vars", "state", "value" }); - try x.h.expectFail(.{ .open = .{ .fid = 3, .mode = cloud9.owrite } }, "permission denied"); + try x.h.expectFail(.{ .open = .{ .fid = 3, .mode = cloud9.owrite } }, e_perm); _ = try x.h.ok(.{ .clunk = .{ .fid = 3 } }); try x.h.walkTo(4, &.{ "vars", "state", "f", "name", "value" }); - try x.h.expectFail(.{ .open = .{ .fid = 4, .mode = cloud9.owrite } }, "permission denied"); + try x.h.expectFail(.{ .open = .{ .fid = 4, .mode = cloud9.owrite } }, e_perm); _ = try x.h.ok(.{ .clunk = .{ .fid = 4 } }); try x.h.walkTo(5, &.{ "vars", "state" }); - try x.h.expectFail(.{ .open = .{ .fid = 5, .mode = cloud9.owrite } }, "is a directory"); - try x.h.expectFail(.{ .create = .{ .fid = 5, .name = "z", .perm = 0o644, .mode = cloud9.owrite } }, "permission denied"); + try x.h.expectFail(.{ .open = .{ .fid = 5, .mode = cloud9.owrite } }, e_perm); + try x.h.expectFail(.{ .create = .{ .fid = 5, .name = "z", .perm = 0o644, .mode = cloud9.owrite } }, e_perm); // .. climbs back out of the var tree; unknown names fail const up = try x.h.ok(.{ .walk = .{ .fid = 5, .newfid = 6, .names = &.{ "f", "inner", "..", "..", "..", "..", "README" } } }); try testing.expectEqual(@as(u16, 7), up.walk.nwqid); _ = try x.h.ok(.{ .clunk = .{ .fid = 6 } }); try x.h.walkTo(7, &.{"vars"}); try x.h.expectFail(.{ .walk = .{ .fid = 7, .newfid = 8, .names = &.{"nope"} } }, "file does not exist"); - try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = 8, .names = &.{"x"} } }, "file already open"); + try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = 8, .names = &.{"x"} } }, e_bad_use); _ = try x.h.ok(.{ .clunk = .{ .fid = 2 } }); try x.h.walkTo(2, &.{ "vars", "state", "f", "a", "value" }); - try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = 8, .names = &.{"x"} } }, "not a directory"); + try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = 8, .names = &.{"x"} } }, e_not_dir); } test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and error mapping" { @@ -2083,13 +1997,13 @@ test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and err _ = try x.h.ok(.{ .clunk = .{ .fid = 1 } }); try testing.expectEqual(@as(u32, 0), x.prov.nodes[3].opens); try testing.expectEqual(@as(u32, 0), x.prov.nodes[3].refs); - // permission and kind errors come from the provider + // permission and kind errors: the engine's from the walked mode, the provider's as its own strings try x.h.walkTo(3, &.{ "prov", "locked" }); - try x.h.expectFail(.{ .open = .{ .fid = 3, .mode = cloud9.oread } }, "permission denied"); + try x.h.expectFail(.{ .open = .{ .fid = 3, .mode = cloud9.oread } }, e_perm); try x.h.walkTo(4, &.{ "prov", "hello" }); - try x.h.expectFail(.{ .walk = .{ .fid = 4, .newfid = 5, .names = &.{"x"} } }, "not a directory"); + try x.h.expectFail(.{ .walk = .{ .fid = 4, .newfid = 5, .names = &.{"x"} } }, e_not_dir); try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = 5, .names = &.{"missing"} } }, "file does not exist"); - try x.h.expectFail(.{ .open = .{ .fid = 2, .mode = cloud9.owrite } }, "is a directory"); + try x.h.expectFail(.{ .open = .{ .fid = 2, .mode = cloud9.owrite } }, e_perm); // create in a provider directory: the fid becomes the new open file const cr = try x.h.ok(.{ .create = .{ .fid = 2, .name = "new", .perm = 0o644, .mode = cloud9.ordwr } }); try testing.expectEqual(cloud9.qtfile, cr.create.qid.type); @@ -2099,11 +2013,11 @@ test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and err try x.h.walkTo(6, &.{"prov"}); try x.h.expectFail(.{ .create = .{ .fid = 6, .name = "new", .perm = 0o644, .mode = cloud9.oread } }, "file already exists"); const long_name = [_]u8{'n'} ** (max_name + 1); - try x.h.expectFail(.{ .create = .{ .fid = 6, .name = &long_name, .perm = 0o644, .mode = cloud9.oread } }, "bad file name"); - try x.h.expectFail(.{ .create = .{ .fid = 6, .name = "d", .perm = cloud9.dmdir | 0o755, .mode = cloud9.owrite } }, "is a directory"); + try x.h.expectFail(.{ .create = .{ .fid = 6, .name = &long_name, .perm = 0o644, .mode = cloud9.oread } }, e_illegal_name); + try x.h.expectFail(.{ .create = .{ .fid = 6, .name = "d", .perm = cloud9.dmdir | 0o755, .mode = cloud9.owrite } }, e_perm); const dr = try x.h.ok(.{ .create = .{ .fid = 6, .name = "d", .perm = cloud9.dmdir | 0o755, .mode = cloud9.oread } }); try testing.expectEqual(cloud9.qtdir, dr.create.qid.type); - // wstat: rename, truncate, mode, mtime; immutable fields are refused + // wstat: rename, truncate, mode, mtime; immutable fields are refused by the engine var ws = stat_dontcare; ws.name = "renamed"; ws.length = 2; @@ -2117,19 +2031,19 @@ test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and err try testing.expectEqual(@as(u32, 99), st2.stat.mtime); ws = stat_dontcare; ws.uid = "someone-else"; - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, "permission denied"); + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, e_wstat); ws = stat_dontcare; ws.mode = cloud9.dmdir | 0o755; - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, "permission denied"); + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, e_wstat); ws = stat_dontcare; ws.name = "bad/name"; - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, "bad file name"); + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, e_illegal_name); ws.name = ".."; - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, "bad file name"); + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = ws } }, e_illegal_name); ws = stat_dontcare; ws.length = 5; try x.h.walkTo(7, &.{ "prov", "d" }); - try x.h.expectFail(.{ .wstat = .{ .fid = 7, .stat = ws } }, "is a directory"); + try x.h.expectFail(.{ .wstat = .{ .fid = 7, .stat = ws } }, e_wstat); ws = stat_dontcare; ws.name = "root2"; // the provider root cannot be renamed try x.h.walkTo(14, &.{"prov"}); @@ -2139,7 +2053,7 @@ test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and err _ = try x.h.ok(.{ .clunk = .{ .fid = 6 } }); try x.h.walkTo(8, &.{ "prov", "dir" }); try x.h.expectFail(.{ .remove = .{ .fid = 8 } }, "directory not empty"); - try x.h.expectFail(.{ .clunk = .{ .fid = 8 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 8 } }, e_unknown_fid); _ = try x.h.ok(.{ .remove = .{ .fid = 2 } }); try x.h.walkTo(9, &.{"prov"}); try x.h.expectFail(.{ .walk = .{ .fid = 9, .newfid = 15, .names = &.{"renamed"} } }, "file does not exist"); @@ -2168,10 +2082,10 @@ test "provider: walk/list/stat/open/read/write/create/remove/wstat/clunk and err // a partial walk releases the handles it obtained const part = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 13, .names = &.{ "prov", "dir", "nope" } } }); try testing.expectEqual(@as(u16, 2), part.walk.nwqid); - try x.h.expectFail(.{ .clunk = .{ .fid = 13 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 13 } }, e_unknown_fid); _ = try x.h.ok(.{ .clunk = .{ .fid = 12 } }); - for (x.h.conn.fids) |f| { - if (f.used) _ = try x.h.ok(.{ .clunk = .{ .fid = f.id } }); + for (x.h.conn.engine.fids) |f| { + if (f.used and !f.orphan) _ = try x.h.ok(.{ .clunk = .{ .fid = f.fid } }); } try testing.expectEqual(@as(u32, 0), x.prov.total_refs); } @@ -2184,7 +2098,7 @@ test "directory reads across offsets, bad offset, and records never split" { _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); const first = try x.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = 4096 } }); try testing.expect(first.read.len > 0); - try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 5, .count = 4096 } }, "bad offset"); + try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 5, .count = 4096 } }, e_bad_offset); // offset 0 restarts; the same bytes come back const again = try x.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = 4096 } }); try testing.expectEqual(first.read.len, again.read.len); @@ -2192,9 +2106,8 @@ test "directory reads across offsets, bad offset, and records never split" { const names = try x.h.listDir(1, 80); defer TS.Harness.freeNames(names); try testing.expectEqual(@as(usize, 7), names.len); - // a count too small for even one record returns nothing rather than splitting it - const tiny = try x.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }); - try testing.expectEqual(@as(usize, 0), tiny.read.len); + // a count too small for even one record is refused rather than splitting it + try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }, e_count_small); // the same for provider and var directories const pn = try x.h.listPath(&.{ "prov", "dir" }); defer TS.Harness.freeNames(pn); @@ -2204,7 +2117,7 @@ test "directory reads across offsets, bad offset, and records never split" { const vn = try x.h.listDir(2, 100); defer TS.Harness.freeNames(vn); try testing.expectEqual(@as(usize, 4), vn.len); - try x.h.expectFail(.{ .read = .{ .fid = 2, .offset = 1, .count = 100 } }, "bad offset"); + try x.h.expectFail(.{ .read = .{ .fid = 2, .offset = 1, .count = 100 } }, e_bad_offset); } test "Tversion mid-session resets fids and clunks every provider handle" { @@ -2226,7 +2139,7 @@ test "Tversion mid-session resets fids and clunks every provider handle" { try testing.expectEqual(@as(u32, 0), x.prov.nodes[3].opens); try testing.expectEqual(before + 2, x.prov.clunks); try testing.expect(!x.h.conn.slot_used[0] and !x.h.conn.slot_used[1]); - try x.h.expectFail(.{ .clunk = .{ .fid = 1 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 1 } }, e_unknown_fid); _ = try x.h.ok(.{ .attach = .{ .fid = 0, .uname = "tester" } }); try x.h.walkTo(1, &.{ "prov", "hello" }); // hangup does the same @@ -2235,24 +2148,34 @@ test "Tversion mid-session resets fids and clunks every provider handle" { try testing.expectEqual(@as(usize, 0), x.h.conn.fidCount()); } -test "a reply that does not fit msize is an Rerror, not a dead connection" { +test "msize: below the engine's floor the connection dies; at the floor everything that fits is served" { var x: Fixture = .{}; try x.init(); defer x.deinit(); - try x.h.version(64); - _ = try x.h.ok(.{ .attach = .{ .fid = 0, .uname = "t" } }); - // Rstat of the root is ~70 bytes. - try x.h.expectFail(.{ .stat = .{ .fid = 0 } }, "reply too large for msize"); - // Rwalk with 5 qids is 74 bytes; the walk must not bind newfid. - try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{ ".", ".", ".", ".", "." } } }, "reply too large for msize"); - try x.h.expectFail(.{ .clunk = .{ .fid = 1 } }, "unknown fid"); - try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 0, .names = &.{ ".", ".", ".", ".", "." } } }, "reply too large for msize"); - const r = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{"README"} } }); - try testing.expectEqual(@as(u16, 1), r.walk.nwqid); - _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); - const rd = try x.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = 40 } }); - try testing.expect(rd.read.len > 0 and rd.read.len <= 64 - cloud9.iohdrsz); - _ = try x.h.ok(.{ .clunk = .{ .fid = 1 } }); + try testing.expectError(error.Protocol, x.h.version(64)); + + var y: Fixture = .{}; + try y.init(); + defer y.deinit(); + try y.h.version(fs.msize_min); + _ = try y.h.ok(.{ .attach = .{ .fid = 0, .uname = "t" } }); + const st = try y.h.ok(.{ .stat = .{ .fid = 0 } }); + try testing.expectEqualStrings("/", st.stat.name); + // A full 16-element Rwalk is exactly msize_min. + const w = try y.h.ok(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &([_][]const u8{"."} ** 16) } }); + try testing.expectEqual(@as(u16, 16), w.walk.nwqid); + _ = try y.h.ok(.{ .clunk = .{ .fid = 1 } }); + // An Rstat that cannot fit is an Rerror, not a dead connection. + try y.h.walkTo(2, &.{"prov"}); + const long_name = [_]u8{'n'} ** 180; // Tcreate fits; the Rstat (61 + 180 bytes) does not + _ = try y.h.ok(.{ .create = .{ .fid = 2, .name = &long_name, .perm = 0o644, .mode = cloud9.oread } }); + try y.h.expectFail(.{ .stat = .{ .fid = 2 } }, e_small_msize); + _ = try y.h.ok(.{ .remove = .{ .fid = 2 } }); + try y.h.walkTo(1, &.{"README"}); + _ = try y.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); + const rd = try y.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = fs.msize_min - cloud9.iohdrsz } }); + try testing.expect(rd.read.len > 0 and rd.read.len <= fs.msize_min - cloud9.iohdrsz); + _ = try y.h.ok(.{ .clunk = .{ .fid = 1 } }); } test "fid table is bounded per connection" { @@ -2263,18 +2186,18 @@ test "fid table is bounded per connection" { while (x.h.conn.fidCount() < test_cfg.max_fids) : (i += 1) { _ = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = i, .names = &.{} } }); } - try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = i, .names = &.{} } }, "too many fids"); - try x.h.expectFail(.{ .attach = .{ .fid = i, .uname = "tester" } }, "too many fids"); + try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = i, .names = &.{} } }, e_too_many_fids); + try x.h.expectFail(.{ .attach = .{ .fid = i, .uname = "tester" } }, e_too_many_fids); // self-walks and clunks still work at the limit _ = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 0, .names = &.{"build"} } }); _ = try x.h.ok(.{ .clunk = .{ .fid = 1 } }); _ = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = i, .names = &.{} } }); - try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 2, .names = &.{"README"} } }, "fid in use"); - try x.h.expectFail(.{ .walk = .{ .fid = 1234, .newfid = 2, .names = &.{} } }, "unknown fid"); + try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 2, .names = &.{"README"} } }, e_fid_in_use); + try x.h.expectFail(.{ .walk = .{ .fid = 1234, .newfid = 2, .names = &.{} } }, e_unknown_fid); // a walk into a provider at the limit must not leak the handle _ = try x.h.ok(.{ .clunk = .{ .fid = 2 } }); _ = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 2, .names = &.{ "..", "prov", "hello" } } }); - try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = i + 1, .names = &.{} } }, "too many fids"); + try x.h.expectFail(.{ .walk = .{ .fid = 2, .newfid = i + 1, .names = &.{} } }, e_too_many_fids); try testing.expectEqual(@as(u32, 1), x.prov.total_refs); } @@ -2295,7 +2218,7 @@ test "Shared refuses more providers or vars than configured" { try testing.expectError(error.Full, shared.expose("v4", &v[4])); } -/// A server with a large fid table for the index tests. +/// A server with a large fid table for the churn test. const big_cfg: Config = .{ .name = "big", .msize = 8192, @@ -2307,8 +2230,8 @@ const big_cfg: Config = .{ }; const BigS = Server(big_cfg); -/// 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). +/// Fid numbers chosen to stress the engine's 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, @@ -2317,34 +2240,15 @@ fn adversarialId(i: u32) u32 { }; } -/// Every index bucket points at a used fid that finds itself, and every used -/// fid is found: the invariant the hostile fid tests check after each phase. -fn checkFidIndex(c: *BigS.Conn) !void { - var indexed: usize = 0; - for (c.index) |slot| { - if (slot == BigS.no_slot) continue; - indexed += 1; - try testing.expect(c.fids[slot].used); - try testing.expectEqual(&c.fids[slot], c.findFid(c.fids[slot].id).?); - } - var used: usize = 0; - for (c.fids[0..c.high_water]) |*f| if (f.used) { - used += 1; - try testing.expectEqual(f, c.findFid(f.id).?); - }; - for (c.fids[c.high_water..]) |*f| try testing.expect(!f.used); - try testing.expectEqual(indexed, used); - try testing.expectEqual(used, c.nfids); -} - -test "fid index: thousands of fids, clunk in hostile orders, reuse, Tversion" { +test "fid table: thousands of fids, clunk in hostile orders, reuse, Tversion" { var ctx: TestCtx = .{}; var shared: BigS.Shared = .init(&ctx); var prov = TestProv.init(); try shared.addProvider(prov.provider()); const storage = try testing.allocator.create(BigS.Storage); defer testing.allocator.destroy(storage); - var h: BigS.Harness = undefined; + const h = try testing.allocator.create(BigS.Harness); + defer testing.allocator.destroy(h); try h.init(&shared, storage); defer h.deinit(); const n: u32 = big_cfg.max_fids - 1; // fid 0 is the attach @@ -2354,34 +2258,30 @@ test "fid index: thousands of fids, clunk in hostile orders, reuse, Tversion" { } try testing.expectEqual(@as(usize, n + 1), h.conn.fidCount()); try testing.expectEqual(n, prov.total_refs); - try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 0x7FFF_FFFF, .names = &.{} } }, "too many fids"); - try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = adversarialId(5), .names = &.{} } }, "fid in use"); - try h.expectFail(.{ .attach = .{ .fid = adversarialId(7), .uname = "t" } }, "fid in use"); - try testing.expect(h.conn.findFid(0x7FFF_FFFF) == null); - try testing.expect(h.conn.findFid(adversarialId(n)) == null); - try checkFidIndex(&h.conn); - // clunk every third fid, then the rest from the top: backward-shift deletion under churn + try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 0x7FFF_FFFF, .names = &.{} } }, e_too_many_fids); + try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = adversarialId(5), .names = &.{} } }, e_fid_in_use); + try h.expectFail(.{ .attach = .{ .fid = adversarialId(7), .uname = "t" } }, e_fid_in_use); + try h.expectFail(.{ .clunk = .{ .fid = 0x7FFF_FFFF } }, e_unknown_fid); + try h.expectFail(.{ .clunk = .{ .fid = adversarialId(n) } }, e_unknown_fid); + // clunk every third fid, then the rest from the top i = 0; while (i < n) : (i += 3) _ = try h.ok(.{ .clunk = .{ .fid = adversarialId(i) } }); - try checkFidIndex(&h.conn); i = n; while (i > 0) { i -= 1; if (i % 3 == 0) { - try h.expectFail(.{ .clunk = .{ .fid = adversarialId(i) } }, "unknown fid"); + try h.expectFail(.{ .clunk = .{ .fid = adversarialId(i) } }, e_unknown_fid); } else { _ = try h.ok(.{ .clunk = .{ .fid = adversarialId(i) } }); } } try testing.expectEqual(@as(usize, 1), h.conn.fidCount()); try testing.expectEqual(@as(u32, 0), prov.total_refs); - try checkFidIndex(&h.conn); - // the whole table is reusable after the churn, through the free list + // the whole table is reusable after the churn i = 0; while (i < n) : (i += 1) _ = try h.ok(.{ .walk = .{ .fid = 0, .newfid = n - i, .names = &.{} } }); - try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = n + 1, .names = &.{} } }, "too many fids"); - try checkFidIndex(&h.conn); - // pseudo-random alloc/free storm with verification + try h.expectFail(.{ .walk = .{ .fid = 0, .newfid = n + 1, .names = &.{} } }, e_too_many_fids); + // pseudo-random alloc/free storm var prng = std.Random.DefaultPrng.init(0x9a11); const rnd = prng.random(); var live: [n + 1]bool = @splat(true); @@ -2395,18 +2295,17 @@ test "fid index: thousands of fids, clunk in hostile orders, reuse, Tversion" { _ = try h.ok(.{ .walk = .{ .fid = 0, .newfid = id, .names = &.{"prov"} } }); } live[id] = !live[id]; - if (round % 997 == 0) try checkFidIndex(&h.conn); } - try checkFidIndex(&h.conn); + var expected: usize = 1; + for (live) |l| expected += @intFromBool(l); + try testing.expectEqual(expected, h.conn.fidCount()); // Tversion drops everything and the table starts over, provider refs balanced try h.version(big_cfg.msize); try testing.expectEqual(@as(usize, 0), h.conn.fidCount()); try testing.expectEqual(@as(u32, 0), prov.total_refs); - try testing.expectEqual(@as(u16, 0), h.conn.high_water); - try checkFidIndex(&h.conn); _ = try h.ok(.{ .attach = .{ .fid = 0xFFFF_FFFE, .uname = "t" } }); _ = try h.ok(.{ .walk = .{ .fid = 0xFFFF_FFFE, .newfid = 0, .names = &.{} } }); - try checkFidIndex(&h.conn); + try testing.expectEqual(@as(usize, 2), h.conn.fidCount()); } test "open: a provider stat failure after a successful open closes the file again" { @@ -2418,7 +2317,7 @@ test "open: a provider stat failure after a successful open closes the file agai try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }, "i/o error"); x.prov.fail_stat = false; try testing.expectEqual(@as(u32, 0), x.prov.nodes[1].opens); - try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }, "file not open"); + try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }, e_bad_use); _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); try testing.expectEqual(@as(u32, 1), x.prov.nodes[1].opens); // the same for create: a stat failure after the provider created the node releases it @@ -2430,7 +2329,7 @@ test "open: a provider stat failure after a successful open closes the file agai try testing.expectEqual(@as(u32, 0), e.opens); try testing.expectEqual(@as(u32, 0), e.refs); }; - try testing.expect(!x.h.conn.findFid(2).?.open); + try testing.expect(!isOpen(&x.h.conn, 2)); try testing.expectEqual(@as(u32, 1), x.prov.total_refs); // fid 1 only } @@ -2440,11 +2339,12 @@ test "fid state machine: open twice, walk from open, remove/clunk of open provid defer x.deinit(); try x.h.walkTo(1, &.{ "prov", "dir", "inner" }); _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.ordwr } }); - try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }, "file already open"); - try x.h.expectFail(.{ .walk = .{ .fid = 1, .newfid = 2, .names = &.{"."} } }, "file already open"); - try x.h.expectFail(.{ .create = .{ .fid = 1, .name = "z", .perm = 0o644, .mode = cloud9.oread } }, "file already open"); - // a clone of an open fid is a fresh, unopened reference - _ = try x.h.ok(.{ .walk = .{ .fid = 1, .newfid = 2, .names = &.{} } }); + try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }, e_already_open); + try x.h.expectFail(.{ .walk = .{ .fid = 1, .newfid = 2, .names = &.{"."} } }, e_bad_use); + try x.h.expectFail(.{ .walk = .{ .fid = 1, .newfid = 2, .names = &.{} } }, e_bad_use); + try x.h.expectFail(.{ .create = .{ .fid = 1, .name = "z", .perm = 0o644, .mode = cloud9.oread } }, e_already_open); + // a second, unopened reference to the same node + try x.h.walkTo(2, &.{ "prov", "dir", "inner" }); try testing.expectEqual(@as(u32, 2), x.prov.nodes[3].refs); try testing.expectEqual(@as(u32, 1), x.prov.nodes[3].opens); // walking newfid == fid with names on an unopened provider fid swaps the handle, refs balanced @@ -2459,24 +2359,24 @@ test "fid state machine: open twice, walk from open, remove/clunk of open provid _ = try x.h.ok(.{ .remove = .{ .fid = 1 } }); try testing.expectEqual(@as(u32, 0), x.prov.nodes[3].opens); try testing.expectEqual(@as(u32, 1), x.prov.nodes[3].refs); - try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }, "unknown fid"); + try x.h.expectFail(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }, e_unknown_fid); _ = try x.h.ok(.{ .clunk = .{ .fid = 2 } }); try testing.expectEqual(@as(u32, 0), x.prov.total_refs); // walking "." on a file fid is "not a directory" at the protocol level, without a provider walk try x.h.walkTo(3, &.{ "prov", "hello" }); const before = x.prov.clunks; - try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{"."} } }, "not a directory"); + try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 4, .names = &.{"."} } }, e_not_dir); try testing.expectEqual(before, x.prov.clunks); try testing.expectEqual(@as(u32, 1), x.prov.total_refs); // a partial walk through a file releases the handles it took const part = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 5, .names = &.{ "prov", "hello", "x", "y" } } }); try testing.expectEqual(@as(u16, 2), part.walk.nwqid); try testing.expectEqual(@as(u32, 1), x.prov.total_refs); - try x.h.expectFail(.{ .clunk = .{ .fid = 5 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 5 } }, e_unknown_fid); // Tremove is always a clunk, even of a static node or when the provider refuses try x.h.walkTo(6, &.{"README"}); try x.h.expectFail(.{ .remove = .{ .fid = 6 } }, "permission denied"); - try x.h.expectFail(.{ .clunk = .{ .fid = 6 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 6 } }, e_unknown_fid); _ = try x.h.ok(.{ .clunk = .{ .fid = 3 } }); try testing.expectEqual(@as(u32, 0), x.prov.total_refs); } @@ -2491,7 +2391,7 @@ test "snapshot slots: exhaust, hold, Tversion frees; reads past the end and at h _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); _ = try x.h.ok(.{ .open = .{ .fid = 2, .mode = cloud9.oread } }); try x.h.expectFail(.{ .open = .{ .fid = 3, .mode = cloud9.oread } }, "too many open dynamic files"); - try testing.expect(!x.h.conn.findFid(3).?.open); + try testing.expect(!isOpen(&x.h.conn, 3)); // reads at offsets near 2^64 never trap (counts above msize are a raw-9P // case: the cloud9 client refuses to send them; test/adv_core_hostile.py covers it) const max_count = test_cfg.msize - cloud9.iohdrsz; @@ -2522,23 +2422,26 @@ test "static and var nodes refuse create, remove and wstat; directories refuse w var x: Fixture = .{}; try x.init(); defer x.deinit(); + var ws = stat_dontcare; + ws.mtime = 1; const dirs = [_][]const []const u8{ &.{}, &.{"build"}, &.{"comptime"}, &.{ "comptime", "types" }, &.{ "comptime", "types", "Layout" }, &.{"runtime"}, &.{ "runtime", "fn" }, &.{"vars"}, &.{ "vars", "state" }, &.{ "vars", "state", "f" }, &.{ "vars", "state", "f", "inner" } }; for (dirs, 0..) |d, k| { const fid: u32 = @intCast(10 + k); try x.h.walkTo(fid, d); - try x.h.expectFail(.{ .create = .{ .fid = fid, .name = "x", .perm = 0o644, .mode = cloud9.owrite } }, "permission denied"); - try x.h.expectFail(.{ .wstat = .{ .fid = fid, .stat = stat_dontcare } }, "permission denied"); - try x.h.expectFail(.{ .open = .{ .fid = fid, .mode = cloud9.owrite } }, "is a directory"); - try x.h.expectFail(.{ .open = .{ .fid = fid, .mode = cloud9.oread | cloud9.otrunc } }, "is a directory"); + try x.h.expectFail(.{ .create = .{ .fid = fid, .name = "x", .perm = 0o644, .mode = cloud9.owrite } }, e_perm); + try x.h.expectFail(.{ .wstat = .{ .fid = fid, .stat = ws } }, "permission denied"); + _ = try x.h.ok(.{ .wstat = .{ .fid = fid, .stat = stat_dontcare } }); + try x.h.expectFail(.{ .open = .{ .fid = fid, .mode = cloud9.owrite } }, e_perm); + try x.h.expectFail(.{ .open = .{ .fid = fid, .mode = cloud9.oread | cloud9.otrunc } }, e_perm); try x.h.expectFail(.{ .remove = .{ .fid = fid } }, "permission denied"); - try x.h.expectFail(.{ .clunk = .{ .fid = fid } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = fid } }, e_unknown_fid); } const files = [_][]const []const u8{ &.{"README"}, &.{ "build", "time" }, &.{ "comptime", "decls" }, &.{ "runtime", "pid" }, &.{ "runtime", "fn", "fib30" }, &.{"ctl"}, &.{ "vars", "state", "value" }, &.{ "vars", "state", "raw" }, &.{ "vars", "state", "f", "a", "value" }, &.{ "vars", "counter", "type" } }; for (files, 0..) |f, k| { const fid: u32 = @intCast(30 + k); try x.h.walkTo(fid, f); - try x.h.expectFail(.{ .wstat = .{ .fid = fid, .stat = stat_dontcare } }, "permission denied"); - try x.h.expectFail(.{ .walk = .{ .fid = fid, .newfid = 99, .names = &.{".."} } }, "not a directory"); + try x.h.expectFail(.{ .wstat = .{ .fid = fid, .stat = ws } }, "permission denied"); + try x.h.expectFail(.{ .walk = .{ .fid = fid, .newfid = 99, .names = &.{".."} } }, e_not_dir); try x.h.expectFail(.{ .remove = .{ .fid = fid } }, "permission denied"); } // writes to a var value at a non-zero offset and with an empty payload @@ -2551,35 +2454,62 @@ test "static and var nodes refuse create, remove and wstat; directories refuse w try testing.expectEqual(@as(u32, 1), x.exposed.a); _ = try x.h.ok(.{ .write = .{ .fid = 1, .offset = std.math.maxInt(u64), .data = "77\n" } }); try testing.expectEqual(@as(u32, 77), x.exposed.a); - // reads of a write-only fid are refused; OEXEC reads like OREAD - try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }, "file not open"); + // reads of a write-only fid are refused; the engine refuses OEXEC + try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 10 } }, e_bad_use); try x.h.walkTo(2, &.{"README"}); - _ = try x.h.ok(.{ .open = .{ .fid = 2, .mode = cloud9.oexec } }); + try x.h.expectFail(.{ .open = .{ .fid = 2, .mode = cloud9.oexec } }, e_perm); + _ = try x.h.ok(.{ .open = .{ .fid = 2, .mode = cloud9.oread } }); try testing.expect((try x.h.ok(.{ .read = .{ .fid = 2, .offset = 0, .count = 10 } })).read.len == 10); } -test "msize 24: every request that fits is answered, every reply that cannot fit is an Rerror" { +test "a provider read that is not ready parks and is answered on a later step" { var x: Fixture = .{}; try x.init(); defer x.deinit(); - try x.h.version(24); - _ = try x.h.ok(.{ .attach = .{ .fid = 0, .uname = "u" } }); // Tattach 20, Rattach 20 - try x.h.expectFail(.{ .stat = .{ .fid = 0 } }, "reply too large"); // Rerror truncated to fit 24 bytes - const w = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 1, .names = &.{"ctl"} } }); // Rwalk 22 - try testing.expectEqual(@as(u16, 1), w.walk.nwqid); - try x.h.expectFail(.{ .walk = .{ .fid = 0, .newfid = 2, .names = &.{ ".", "." } } }, "reply too large"); - try x.h.expectFail(.{ .clunk = .{ .fid = 2 } }, "unknown fid"); - _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.ordwr } }); // Ropen 24 - try x.h.expectFail(.{ .write = .{ .fid = 1, .offset = 0, .data = "e" } }, "bad command"); // Twrite 24 - // the largest read the client may ask for is msize - iohdrsz = 0 bytes - const r = try x.h.ok(.{ .read = .{ .fid = 1, .offset = 0, .count = 0 } }); - try testing.expectEqual(@as(usize, 0), r.read.len); - _ = try x.h.ok(.{ .clunk = .{ .fid = 1 } }); - try x.h.walkTo(3, &.{"build"}); - _ = try x.h.ok(.{ .open = .{ .fid = 3, .mode = cloud9.oread } }); - const d = try x.h.ok(.{ .read = .{ .fid = 3, .offset = 0, .count = 0 } }); - try testing.expectEqual(@as(usize, 0), d.read.len); // no record fits in 0 bytes, nothing is split - try x.h.expectFail(.{ .read = .{ .fid = 3, .offset = 1, .count = 0 } }, "bad offset"); + try x.h.walkTo(1, &.{ "prov", "hello" }); + _ = try x.h.ok(.{ .open = .{ .fid = 1, .mode = cloud9.oread } }); + x.prov.park = true; + const reads = x.prov.reads; + const tag = try x.h.client.submit(.{ .read = .{ .fid = 1, .offset = 0, .count = 100 } }); + _ = try x.h.pump(); + try testing.expectEqual(@as(?cloud9.Client.Done, null), x.h.client.take()); + try testing.expect(x.prov.reads > reads); + // the connection keeps serving, and every step asks the provider again + const asked = x.prov.reads; + const st = try x.h.ok(.{ .stat = .{ .fid = 1 } }); + try testing.expectEqualStrings("hello", st.stat.name); + try testing.expect(x.prov.reads > asked); + try testing.expectEqual(@as(?cloud9.Client.Done, null), x.h.client.take()); + // a second parked read fills the slots; a third is refused at once + _ = try x.h.client.submit(.{ .read = .{ .fid = 1, .offset = 0, .count = 100 } }); + _ = try x.h.pump(); + try testing.expectEqual(@as(?cloud9.Client.Done, null), x.h.client.take()); + try x.h.expectFail(.{ .read = .{ .fid = 1, .offset = 0, .count = 100 } }, fs.e_again); + // ready: the next step answers both, oldest first, with the original tags + x.prov.park = false; + _ = try x.h.pump(); + const first = x.h.client.take() orelse return error.NoReply; + try testing.expectEqual(tag, first.tag); + try testing.expectEqualStrings("hello", first.result.read); + const second = x.h.client.take() orelse return error.NoReply; + try testing.expectEqualStrings("hello", second.result.read); + try testing.expectEqual(@as(?cloud9.Client.Done, null), x.h.client.take()); + // a flushed parked read is interrupted; a hangup with one parked pays the provider + x.prov.park = true; + const parked = try x.h.client.submit(.{ .read = .{ .fid = 1, .offset = 0, .count = 100 } }); + _ = try x.h.pump(); + _ = try x.h.client.submit(.{ .flush = .{ .oldtag = parked } }); + _ = try x.h.pump(); + const interrupted = x.h.client.take() orelse return error.NoReply; + try testing.expectEqual(parked, interrupted.tag); + try testing.expectEqualStrings(e_interrupted, interrupted.result.fail); + try testing.expect((x.h.client.take() orelse return error.NoReply).result == .flush); + _ = try x.h.client.submit(.{ .read = .{ .fid = 1, .offset = 0, .count = 100 } }); + _ = try x.h.pump(); + try testing.expectEqual(@as(u32, 1), x.prov.nodes[1].opens); + x.h.conn.hangup(); + try testing.expectEqual(@as(u32, 0), x.prov.nodes[1].opens); + try testing.expectEqual(@as(u32, 0), x.prov.total_refs); } test "Conn.init clamps the msize cap to [msize_min, cfg.msize]" { @@ -2587,11 +2517,13 @@ test "Conn.init clamps the msize cap to [msize_min, cfg.msize]" { var shared: TS.Shared = .init(&ctx); var storage: TS.Storage = undefined; const lo: TS.Conn = .init(&shared, &storage, 0); - try testing.expectEqual(cloud9.Server.msize_min, lo.msize_cap); + try testing.expectEqual(fs.msize_min, lo.msize_cap); const hi: TS.Conn = .init(&shared, &storage, std.math.maxInt(u32)); try testing.expectEqual(test_cfg.msize, hi.msize_cap); const mid: TS.Conn = .init(&shared, &storage, 4096); try testing.expectEqual(@as(u32, 4096), mid.msize_cap); + // two connections on the same Shared never share a fid-index salt + try testing.expect(lo.engine.hash_seed != hi.engine.hash_seed); } test "parseIso8601 rejects malformed stamps and never traps" { @@ -2611,46 +2543,3 @@ test "parseIso8601 rejects malformed stamps and never traps" { try testing.expectEqual(@as(u32, std.math.maxInt(u32)), parseIso8601("2106-02-07T06:28:15Z").?); try testing.expectEqual(@as(?u32, null), parseIso8601("2106-02-07T06:28:16Z")); } - -/// 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 "fid index: fid numbers crafted to collide under the public hash do not cluster a seeded connection" { - var ctx: TestCtx = .{}; - var shared: BigS.Shared = .init(&ctx); - const storage = try testing.allocator.create(BigS.Storage); - defer testing.allocator.destroy(storage); - var h: BigS.Harness = undefined; - try h.init(&shared, storage); - defer h.deinit(); - // two connections on the same Shared never share a seed - const other: BigS.Conn = .init(&shared, storage, big_cfg.msize); - try testing.expect(other.hash_seed != h.conn.hash_seed); - // ids whose products with the golden ratio share their top bits: all one bucket when unseeded - const inv = inverseMod32(0x9E37_79B1); - try testing.expectEqual(@as(u32, 1), inv *% 0x9E37_79B1); - const n: u32 = big_cfg.max_fids - 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 >> BigS.index_shift), @as(usize, @intCast((id *% 0x9E37_79B1) >> BigS.index_shift))); - _ = try h.ok(.{ .walk = .{ .fid = 0, .newfid = id, .names = &.{} } }); - } - try checkFidIndex(&h.conn); - // the longest probe sequence in the seeded table is short; unseeded it would be ~n - var worst: usize = 0; - i = 0; - while (i < n) : (i += 1) { - const id = (base + i) *% inv; - var pos = h.conn.fidHome(id); - var steps: usize = 0; - while (h.conn.fids[h.conn.index[pos]].id != id) : (pos = (pos + 1) & BigS.index_mask) steps += 1; - worst = @max(worst, steps); - } - try testing.expect(worst < 64); -} diff --git a/9proc/src/linux/probe.zig b/9proc/src/linux/probe.zig index 559d981..4db277d 100644 --- a/9proc/src/linux/probe.zig +++ b/9proc/src/linux/probe.zig @@ -427,7 +427,7 @@ pub fn Probe(comptime Srv: type) type { /// Free space in the connection's input buffer (cloud9 keeps one /// msize-sized frame; `push` copies at most this much). fn inputRoom(conn: *const Srv.Conn) usize { - return conn.server.in.len - conn.server.in_len; + return conn.inputRoom(); } fn readClient(p: *Self, i: usize, hup: bool) void { diff --git a/9proc/src/scratch.zig b/9proc/src/scratch.zig index 2163a28..f666afb 100644 --- a/9proc/src/scratch.zig +++ b/9proc/src/scratch.zig @@ -7,6 +7,7 @@ //! the root is handle 0. Not internally synchronized (like `Shared`). const std = @import("std"); const cloud9 = @import("cloud9"); +const fs = cloud9.fs; const core = @import("core.zig"); const Allocator = std.mem.Allocator; const Provider = core.Provider; @@ -374,8 +375,7 @@ const Fixture = struct { } fn nodeOf(x: *Fixture, fid: u32) *Node { - for (x.h.conn.fids) |f| if (f.used and f.id == fid) return x.scratch.node(f.node.prov.h); - unreachable; + return x.scratch.node(x.h.conn.providerHandle(fid).?); } }; @@ -429,7 +429,7 @@ test "scratch create/write/read/rename/truncate/remove" { _ = try x.h.ok(.{ .clunk = .{ .fid = 5 } }); try x.h.walkTo(6, &.{ "scratch", "d" }); try x.h.expectFail(.{ .remove = .{ .fid = 6 } }, "directory not empty"); - try x.h.expectFail(.{ .clunk = .{ .fid = 6 } }, "unknown fid"); // remove always clunks + try x.h.expectFail(.{ .clunk = .{ .fid = 6 } }, fs.e_unknown_fid); // remove always clunks try x.h.walkTo(7, &.{ "scratch", "d", "inner" }); _ = try x.h.ok(.{ .remove = .{ .fid = 7 } }); try x.h.walkTo(8, &.{ "scratch", "d" }); @@ -469,7 +469,7 @@ test "walk of a missing name and walking a file" { // a walk that fails past the first element is a partial Rwalk that leaves newfid unused const r = try x.h.ok(.{ .walk = .{ .fid = 0, .newfid = 4, .names = &.{ "scratch", "nope", "x" } } }); try testing.expectEqual(@as(u16, 1), r.walk.nwqid); - try x.h.expectFail(.{ .clunk = .{ .fid = 4 } }, "unknown fid"); + try x.h.expectFail(.{ .clunk = .{ .fid = 4 } }, fs.e_unknown_fid); // .. from a file is not a directory; .. from the scratch root reaches the server root try x.h.expectFail(.{ .walk = .{ .fid = 3, .newfid = 5, .names = &.{".."} } }, "not a directory"); try x.h.walkTo(5, &.{"scratch"}); @@ -504,10 +504,9 @@ test "directory read across consecutive offsets returns every record exactly onc seen[idx] = true; } for (seen) |s| try testing.expect(s); - try x.h.expectFail(.{ .read = .{ .fid = 2, .offset = 7, .count = 200 } }, "bad offset"); - // a read that cannot fit even one record returns nothing rather than splitting it - const tiny = try x.h.ok(.{ .read = .{ .fid = 2, .offset = 0, .count = 30 } }); - try testing.expectEqual(@as(usize, 0), tiny.read.len); + try x.h.expectFail(.{ .read = .{ .fid = 2, .offset = 7, .count = 200 } }, fs.e_bad_offset); + // a read that cannot fit even one record is refused rather than splitting it + try x.h.expectFail(.{ .read = .{ .fid = 2, .offset = 0, .count = 30 } }, fs.e_count_small); _ = try x.h.ok(.{ .clunk = .{ .fid = 2 } }); // Tversion resets every fid and every reference try x.h.version(8192); @@ -592,13 +591,16 @@ test "wstat with every field equal to the current stat changes nothing" { try x.h.walkTo(1, &.{"scratch"}); _ = try x.h.ok(.{ .create = .{ .fid = 1, .name = "same", .perm = 0o640, .mode = cloud9.oread } }); const before = (try x.h.ok(.{ .stat = .{ .fid = 1 } })).stat; - var copy = before; + // The engine owns type, dev, qid, atime and the owner names: those must + // be "don't care"; name, mode, mtime and length equal to the current + // stat reach the provider and change nothing. + var copy = dontcare; var name_buf: [core.max_name]u8 = undefined; @memcpy(name_buf[0..before.name.len], before.name); copy.name = name_buf[0..before.name.len]; - copy.uid = "tester"; - copy.gid = "tester"; - copy.muid = "tester"; + copy.mode = before.mode; + copy.mtime = before.mtime; + copy.length = before.length; _ = try x.h.ok(.{ .wstat = .{ .fid = 1, .stat = copy } }); const after = (try x.h.ok(.{ .stat = .{ .fid = 1 } })).stat; try testing.expectEqual(before.qid, after.qid); @@ -619,7 +621,7 @@ test "wstat with every field equal to the current stat changes nothing" { // the mode's directory bit is immutable, mtime is settable st = dontcare; st.mode = cloud9.dmdir | 0o640; - try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = st } }, "permission denied"); + try x.h.expectFail(.{ .wstat = .{ .fid = 2, .stat = st } }, fs.e_wstat); st = dontcare; st.mtime = 12345; _ = try x.h.ok(.{ .wstat = .{ .fid = 2, .stat = st } }); @@ -651,7 +653,7 @@ test "ORCLOSE removes on clunk and removed files stay readable through open fids _ = try x.h.ok(.{ .clunk = .{ .fid = 3 } }); try x.h.walkTo(6, &.{"scratch"}); try x.h.expectFail(.{ .walk = .{ .fid = 6, .newfid = 7, .names = &.{"d"} } }, "file does not exist"); - try x.h.expectFail(.{ .create = .{ .fid = 5, .name = "x", .perm = 0o644, .mode = cloud9.oread } }, "unknown fid"); // remove clunked it + try x.h.expectFail(.{ .create = .{ .fid = 5, .name = "x", .perm = 0o644, .mode = cloud9.oread } }, fs.e_unknown_fid); // remove clunked it } test "qid paths are stable identities, not addresses: remove + recreate differ" { diff --git a/9proc/test/adv_9proc_hostile.py b/9proc/test/adv_9proc_hostile.py index 934e757..dfa0d20 100755 --- a/9proc/test/adv_9proc_hostile.py +++ b/9proc/test/adv_9proc_hostile.py @@ -21,6 +21,22 @@ import time NOTAG = 0xFFFF NOFID = 0xFFFFFFFF + +# The Rerror strings of the conditions cloud9.fs (the file-server engine the +# core is a backend of) decides itself; the tree's own refusals keep the +# Plan 9 strings ("file does not exist", "bad command", ...). +MSIZE_MIN = 217 # one full Rwalk must fit +E_UNKNOWN_FID = "fid unknown or out of range" +E_FID_IN_USE = "fid already in use" +E_TOO_MANY_FIDS = "Too many open files in system" +E_BAD_USE = "bad use of fid" # I/O on an unopened fid; a walk or clone from an open one +E_ALREADY_OPEN = "file already open for I/O" # open or create on an open fid +E_BAD_OFFSET = "bad offset in directory read" +E_PERM = "permission denied" # the engine's own refusals: dirs for write, OEXEC, static trees +E_WSTAT = "wstat prohibited" # engine-owned stat fields, or a length on a directory +E_ILLEGAL_NAME = "illegal name" # names of creates and renames +E_INVAL = "Invalid argument" # a reply that cannot fit msize; a dir read count below one record +E_INTERRUPTED = "Interrupted system call" Tversion, Rversion, Tauth, Rauth, Tattach, Rattach, Rerror = 100, 101, 102, 103, 104, 105, 107 Tflush, Rflush, Twalk, Rwalk, Topen, Ropen, Tcreate, Rcreate = 108, 109, 110, 111, 112, 113, 114, 115 Tread, Rread, Twrite, Rwrite, Tclunk, Rclunk, Tremove, Rremove = 116, 117, 118, 119, 120, 121, 122, 123 @@ -303,37 +319,31 @@ def attack_framing(path): c.raw(frame(Tversion, 5, struct.pack("<I", 8192) + s16(b"9P2000"))) ok("Tversion with tag 5: closed", expect_dead(c)) c.close() - # Tversion msize below the resource floor - for ms in (0, 1, 23): + # Tversion msize below the engine's floor (one full Rwalk must fit): no Rversion + for ms in (0, 1, 23, 24, 64, MSIZE_MIN - 1): c = Nine(path) rt, _, _ = c.version(ms) ok(f"Tversion msize {ms}: no Rversion (closed or Rerror)", rt in (None, Rerror) or expect_dead(c)) c.close() - # tiny msize 24 is negotiable (Rversion fits); Tattach cannot fit, so use msize 64 for the rest - c = Nine(path) - rt, ms, ver = c.version(24) - ok("Tversion msize 24 accepted", rt == Rversion and ms == 24 and ver == b"9P2000", f"{rt} {ms} {ver}") - c.close() + # the floor itself is negotiable, and everything that fits is served at it c = Nine(path) - rt, ms, ver = c.version(64) - ok("Tversion msize 64 accepted", rt == Rversion and ms == 64, f"{rt} {ms} {ver}") + rt, ms, ver = c.version(MSIZE_MIN) + ok(f"Tversion msize {MSIZE_MIN} accepted", rt == Rversion and ms == MSIZE_MIN and ver == b"9P2000", f"{rt} {ms} {ver}") rt, _, _ = c.attach(uname=b"u") - ok("attach at msize 64", rt == Rattach, rt) - # Rstat of the root is ~70 bytes and cannot fit: must be an Rerror, not a dead socket + ok("attach at the floor", rt == Rattach, rt) rt, rb = c.stat(0) - ok("stat at msize 64 answers Rerror (reply does not fit), socket stays open", rt == Rerror, f"{rt} {rb!r}") - # Twalk with 5 names is 37 bytes (fits); Rwalk with 5 qids is 74 bytes (does not) - rt, _, rb = c.walk(0, 1, [b".", b".", b".", b".", b"."]) - ok("5-element walk at msize 64 answers Rerror, socket stays open", rt == Rerror, f"{rt} {rb!r}") - ok("newfid not bound by the failed walk", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("stat of the root at the floor fits", rt == Rstat, f"{rt} {rb!r}") + rt, _, rb = c.walk(0, 1, [b"."] * 16) + ok("16-element walk at the floor fits exactly", rt == Rwalk, f"{rt} {rb!r}") + c.clunk(1) rt, _, _ = c.walk(0, 1, [b"README"]) - ok("1-element walk at msize 64", rt == Rwalk, rt) + ok("1-element walk at the floor", rt == Rwalk, rt) rt, _, _ = c.open(1, OREAD) - ok("open at msize 64", rt == Ropen, rt) + ok("open at the floor", rt == Ropen, rt) rt, d = c.read(1, 0, 4096) - ok("read at msize 64 returns <= 40 bytes", rt == Rread and 0 < len(d) <= 40, f"{rt} {d!r}") + ok(f"read at the floor returns <= {MSIZE_MIN - 11} bytes", rt == Rread and 0 < len(d) <= MSIZE_MIN - 11, f"{rt} {d!r}") rt, _, _ = c.clunk(1) - ok("clunk at msize 64 still works", rt == Rclunk, rt) + ok("clunk at the floor still works", rt == Rclunk, rt) c.close() # huge msize is clamped to the server's max (1 MiB) c = Nine(path) @@ -413,11 +423,11 @@ def attack_walk(path): # partial walk: newfid not bound n = c.walk_ok(0, 1, [b"build", b"nope", b"x"]) ok("partial walk returns 1 qid", n == 1, n) - ok("partial walk does not bind newfid", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("partial walk does not bind newfid", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) # walk through a file n = c.walk_ok(0, 1, [b"build", b"target", b"x"]) ok("walk through a file is partial (2)", n == 2, n) - ok("newfid unbound after partial walk through file", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("newfid unbound after partial walk through file", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) # walk from a file with nwname>0 ok("walk to file", c.walk_ok(0, 1, [b"build", b"target"]) == 2) ok("walk from file fails 'not a directory'", c.err(Twalk, struct.pack("<IIH", 1, 2, 1) + s16(b"x")) == "not a directory") @@ -431,10 +441,10 @@ def attack_walk(path): c.clunk(1) # newfid in use c.walk_ok(0, 1, []) - ok("walk to a fid in use", c.err(Twalk, struct.pack("<IIH", 0, 1, 0)) == "fid in use") - ok("walk from unknown fid", c.err(Twalk, struct.pack("<IIH", 999, 2, 0)) == "unknown fid") + ok("walk to a fid in use", c.err(Twalk, struct.pack("<IIH", 0, 1, 0)) == E_FID_IN_USE) + ok("walk from unknown fid", c.err(Twalk, struct.pack("<IIH", 999, 2, 0)) == E_UNKNOWN_FID) # attach twice - ok("attach twice same fid", c.err(Tattach, struct.pack("<II", 0, NOFID) + s16(b"u") + s16(b"")) == "fid in use") + ok("attach twice same fid", c.err(Tattach, struct.pack("<II", 0, NOFID) + s16(b"u") + s16(b"")) == E_FID_IN_USE) ok("auth is refused", c.err(Tauth, struct.pack("<I", 5) + s16(b"u") + s16(b"")) is not None) c.close() ok("server healthy after walk attacks", healthy(path)) @@ -458,20 +468,20 @@ def attack_io(path): c.clunk(1) # read on unopened fid c.walk_ok(0, 2, [b"README"]) - ok("read on unopened fid", c.err(Tread, struct.pack("<IQI", 2, 0, 10)) == "file not open") - ok("write on unopened fid", c.err(Twrite, struct.pack("<IQI", 2, 0, 1) + b"x") == "file not open") - ok("read unknown fid", c.err(Tread, struct.pack("<IQI", 555, 0, 10)) == "unknown fid") + ok("read on unopened fid", c.err(Tread, struct.pack("<IQI", 2, 0, 10)) == E_BAD_USE) + ok("write on unopened fid", c.err(Twrite, struct.pack("<IQI", 2, 0, 1) + b"x") == E_BAD_USE) + ok("read unknown fid", c.err(Tread, struct.pack("<IQI", 555, 0, 10)) == E_UNKNOWN_FID) c.clunk(2) # directory: write/trunc/write on a dir c.walk_ok(0, 3, [b"build"]) - ok("open dir for write is 'is a directory'", c.err(Topen, struct.pack("<IB", 3, OWRITE)) == "is a directory") + ok("open dir for write is refused by the engine", c.err(Topen, struct.pack("<IB", 3, OWRITE)) == E_PERM) ok("open dir with OTRUNC is refused", c.err(Topen, struct.pack("<IB", 3, OREAD | OTRUNC)) is not None) rt, _, _ = c.open(3, OREAD) ok("write on open dir", c.err(Twrite, struct.pack("<IQI", 3, 0, 1) + b"x") is not None) rt, d = c.read(3, 0, 8192) ok("read dir", rt == Rread and len(d) > 0) - ok("read dir at bad offset", c.err(Tread, struct.pack("<IQI", 3, 3, 8192)) == "bad offset") - ok("read dir at 2^64-1 is bad offset", c.err(Tread, struct.pack("<IQI", 3, (1 << 64) - 1, 8192)) == "bad offset") + ok("read dir at bad offset", c.err(Tread, struct.pack("<IQI", 3, 3, 8192)) == E_BAD_OFFSET) + ok("read dir at 2^64-1 is bad offset", c.err(Tread, struct.pack("<IQI", 3, (1 << 64) - 1, 8192)) == E_BAD_OFFSET) rt, d2 = c.read(3, len(d), 8192) ok("read dir at end returns empty", rt == Rread and d2 == b"") # read of an open write-only file @@ -527,12 +537,12 @@ def attack_scratch(path): return c.walk_ok(0, fid, S + list(extra)) fresh(1) - ok("create name with '/'", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a/b") + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") - ok("create '.'", c.err(Tcreate, struct.pack("<I", 1) + s16(b".") + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") - ok("create '..'", c.err(Tcreate, struct.pack("<I", 1) + s16(b"..") + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") - ok("create empty name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"") + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") - ok("create NUL name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a\x00b") + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") - ok("create 256-byte name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a" * 256) + struct.pack("<IB", 0o644, OWRITE)) == "bad file name") + ok("create name with '/'", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a/b") + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) + ok("create '.'", c.err(Tcreate, struct.pack("<I", 1) + s16(b".") + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) + ok("create '..'", c.err(Tcreate, struct.pack("<I", 1) + s16(b"..") + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) + ok("create empty name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"") + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) + ok("create NUL name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a\x00b") + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) + ok("create 256-byte name", c.err(Tcreate, struct.pack("<I", 1) + s16(b"a" * 256) + struct.pack("<IB", 0o644, OWRITE)) == E_ILLEGAL_NAME) rt, _, _ = c.create(1, b"b" * 255, 0o644, OWRITE) ok("create 255-byte name ok", rt == Rcreate, rt) rt, st = c.stat(1) @@ -566,25 +576,28 @@ def attack_scratch(path): ok("wstat length 64MiB+1 is no space", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(length=(64 << 20) + 1))) == "no space left on device") ok("wstat length 2^64-2 is no space", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(length=(1 << 64) - 2))) == "no space left on device") # read on a write-only fid - ok("read on OWRITE fid", c.err(Tread, struct.pack("<IQI", 1, 0, 10)) == "file not open") + ok("read on OWRITE fid", c.err(Tread, struct.pack("<IQI", 1, 0, 10)) == E_BAD_USE) c.clunk(1) - # wstat with everything set to the current values: no-op + # wstat with name, mode, mtime and length equal to the current values: no-op fresh(1, [b"f"]) rt, st = c.stat(1) + same = mkstat(name=st["name"], mode=st["mode"], mtime=st["mtime"], length=st["length"]) + rt, _, _ = c.wstat(1, same) + ok("wstat with name/mode/mtime/length equal to current is ok", rt == Rwstat, rt) + rt, st2 = c.stat(1) + ok("stat/wstat round trip fidelity", st2 == st, f"{st}\n{st2}") + # the engine owns type, dev, qid, atime and the owner names: naming them at all is refused, even unchanged full = mkstat(name=st["name"], uid=st["uid"], gid=st["gid"], muid=st["muid"], typ=st["type"], dev=st["dev"], qtype=st["qid"][0], qvers=st["qid"][1], qpath=st["qid"][2], mode=st["mode"], atime=st["atime"], mtime=st["mtime"], length=st["length"]) - rt, _, _ = c.wstat(1, full) - ok("wstat with everything equal to current is ok", rt == Rwstat, rt) - rt, st2 = c.stat(1) - ok("stat/wstat round trip fidelity", st2 == st, f"{st}\n{st2}") + ok("wstat naming the engine-owned fields is 'wstat prohibited' even when equal", c.err(Twstat, struct.pack("<I", 1) + s16(full)) == E_WSTAT) # wstat changing immutable fields - ok("wstat changing qid.path", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(qpath=12345))) == "permission denied") - ok("wstat changing uid", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(uid=b"root"))) == "permission denied") - ok("wstat DMDIR on a file", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(mode=DMDIR | 0o755))) == "permission denied") - ok("wstat rename to '.'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"."))) == "bad file name") - ok("wstat rename to '..'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b".."))) == "bad file name") - ok("wstat rename to 'a/b'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"a/b"))) == "bad file name") + ok("wstat changing qid.path", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(qpath=12345))) == E_WSTAT) + ok("wstat changing uid", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(uid=b"root"))) == E_WSTAT) + ok("wstat DMDIR on a file", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(mode=DMDIR | 0o755))) == E_WSTAT) + ok("wstat rename to '.'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"."))) == E_ILLEGAL_NAME) + ok("wstat rename to '..'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b".."))) == E_ILLEGAL_NAME) + ok("wstat rename to 'a/b'", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"a/b"))) == E_ILLEGAL_NAME) ok("wstat rename to existing", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"b" * 255))) == "file already exists") rt, _, _ = c.wstat(1, mkstat(name=b"F")) rt2, st = c.stat(1) @@ -595,18 +608,18 @@ def attack_scratch(path): c.clunk(1) # remove of root / scratch root / static ok("remove of attach root", c.err(Tremove, struct.pack("<I", 0)) == "permission denied") - ok("fid clunked by failed remove", c.err(Tstat, struct.pack("<I", 0)) == "unknown fid") + ok("fid clunked by failed remove", c.err(Tstat, struct.pack("<I", 0)) == E_UNKNOWN_FID) c.attach() c.walk_ok(0, 1, [b"scratch"]) ok("remove of /scratch", c.err(Tremove, struct.pack("<I", 1)) == "permission denied") - ok("fid clunked by failed remove of /scratch", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("fid clunked by failed remove of /scratch", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) c.walk_ok(0, 1, [b"build", b"target"]) ok("remove of static file", c.err(Tremove, struct.pack("<I", 1)) == "permission denied") - ok("clunk unknown fid", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("clunk unknown fid", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) # remove non-empty dir; fid clunked fresh(1) ok("remove non-empty dir", c.err(Tremove, struct.pack("<I", 1)) == "directory not empty") - ok("fid clunked after failed remove", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok("fid clunked after failed remove", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) # a fid on a removed file: everything but stat/clunk fails cleanly fresh(1, [b"F"]) fresh(2, [b"F"]) @@ -667,7 +680,9 @@ def attack_scratch(path): # directory read across offsets while the directory changes fresh(1) c.open(1, OREAD) - rt, d = c.read(1, 0, 120) # one or two records + rt, d = c.read(1, 0, 8192) + first = struct.unpack_from("<H", d)[0] + 2 + rt, d = c.read(1, 0, first) # exactly one record (the engine never splits one) fresh(2, [b"weird", b"inner"]) c.remove(2) fresh(2, [b"weird"]) @@ -700,7 +715,7 @@ def attack_scratch(path): rt, ms, _ = c.version(65536) ok("mid-session Tversion", rt == Rversion) ok("fids gone after Tversion", c.err(Tstat, struct.pack("<I", 1)) is not None) - ok("fids gone after Tversion (0)", c.err(Tstat, struct.pack("<I", 0)) == "unknown fid") + ok("fids gone after Tversion (0)", c.err(Tstat, struct.pack("<I", 0)) == E_UNKNOWN_FID) c.attach() # cleanup: remove everything under root c.walk_ok(0, 1, S) diff --git a/9proc/test/adv_core_hostile.py b/9proc/test/adv_core_hostile.py index 464876f..febda0d 100755 --- a/9proc/test/adv_core_hostile.py +++ b/9proc/test/adv_core_hostile.py @@ -4,7 +4,7 @@ Complements adv_9proc_hostile.py in this directory (framing, tags, scratch, floods) with attacks on the freestanding engine's own paths: the /vars tree and its comptime renderers, snapshot slots, the static tree, the fid table at its -configured maximum, directory-read offsets, msize 24, the ctl staging rule, +configured maximum, directory-read offsets, the msize floor, the ctl staging rule, and the demo's debug providers driven as black boxes. Usage: @@ -30,6 +30,8 @@ from adv_9proc_hostile import ( # noqa: E402 Tread, Rread, Twrite, Rwrite, Tclunk, Rclunk, Tremove, Rremove, Tstat, Rstat, Twstat, Rwstat, Rerror, OREAD, OWRITE, ORDWR, OEXEC, OTRUNC, ORCLOSE, DMDIR, Nine, frame, s16, mkstat, parse_stat, ok, healthy, expect_dead, + MSIZE_MIN, E_UNKNOWN_FID, E_FID_IN_USE, E_TOO_MANY_FIDS, E_BAD_USE, E_ALREADY_OPEN, E_BAD_OFFSET, + E_PERM, E_WSTAT, E_INVAL, ) MAX_FIDS = 32768 # demo/main.zig cfg.max_fids @@ -88,7 +90,7 @@ def attack_vars(path): for nm in (b"0", b"-1", b"0x", b"0x0", b"state\x00", b"State", b" state", b"state ", b"a" * 255, b"a" * 65535, b"\xff\xfe", b"..\x00", b"f", b"value"): n = c.walk_ok(0, 1, [b"vars", nm]) ok(f"walk /vars/{nm[:12]!r}{'...' if len(nm) > 12 else ''} is a partial walk (1)", n == 1, n) - ok(" and newfid stays unbound", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok(" and newfid stays unbound", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) for nm in (b"0", b"F", b"f\x00", b"ticks", b"value ", b"raw\x00"): n = c.walk_ok(0, 1, [b"vars", b"state", nm]) ok(f"walk /vars/state/{nm!r} is a partial walk (2)", n == 2, n) @@ -151,7 +153,7 @@ def attack_vars(path): for bad in (b"abc", b"99999999999999999999999", b"-1", b"1e3", b"", b" ", b"4\x002", b"1.5", b"0x", b"+", b"\xd9\xa1\xd9\xa2", b"12 34", b"0b102"): e = c.err(Twrite, struct.pack("<IQI", 1, 0, len(bad)) + bad) ok(f"write {bad!r} to u64 value is 'bad value'", e == "bad value", e) - ok("read on the write-only value fid is 'file not open'", c.err(Tread, struct.pack("<IQI", 1, 0, 10)) == "file not open") + ok("read on the write-only value fid is 'file not open'", c.err(Tread, struct.pack("<IQI", 1, 0, 10)) == E_BAD_USE) for good, want in ((b" 4200 \n", 4200), (b"0x10", 16), (b"+7", 7), (b"0b1010", 10), (b"0o17", 15), (b"1_000", 1000), (b"18446744073709551615", (1 << 64) - 1)): rt, _, rb = c.write(1, (1 << 64) - 1, good) # offset is ignored for values got = c.path_read([b"vars", b"state", b"f", b"ticks", b"value"]) @@ -200,9 +202,9 @@ def attack_vars(path): p = b"/".join(names).decode() ok(f"create in {p} is denied", c.err(base.Tcreate, struct.pack("<I", 1) + s16(b"x") + struct.pack("<IB", 0o644, OWRITE)) == "permission denied") ok(f"wstat of {p} is denied", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(name=b"y"))) == "permission denied") - ok(f"open {p} for write is 'is a directory'", c.err(Topen, struct.pack("<IB", 1, OWRITE)) == "is a directory") + ok(f"open {p} for write is refused by the engine", c.err(Topen, struct.pack("<IB", 1, OWRITE)) == E_PERM) ok(f"remove {p} is denied", c.err(Tremove, struct.pack("<I", 1)) == "permission denied") - ok(f" and the fid was clunked", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok(f" and the fid was clunked", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) for names in ([b"vars", b"state", b"value"], [b"vars", b"state", b"f", b"last_job", b"value"], [b"vars", b"state", b"type"]): c.walk_ok(0, 1, names) p = b"/".join(names).decode() @@ -249,7 +251,7 @@ def attack_snapshots(path): break ok(f"exactly {SNAPSHOT_SLOTS} dynamic files open per connection", opened == SNAPSHOT_SLOTS, opened) ok("the next open is 'too many open dynamic files'", err == "too many open dynamic files", err) - ok("the refused fid is still unopened (read is 'file not open')", c.err(Tread, struct.pack("<IQI", 100 + opened, 0, 10)) == "file not open") + ok("the refused fid is still unopened (read is 'file not open')", c.err(Tread, struct.pack("<IQI", 100 + opened, 0, 10)) == E_BAD_USE) # every held snapshot is still readable and consistent at offset 1 for i in range(opened): rt, d = c.read(100 + i, 0, 8192) @@ -278,11 +280,11 @@ def attack_snapshots(path): c.walk_ok(0, 60, dyn[0]) rt, _, _ = c.open(60, OREAD) ok("the failed-remove fid's slot was released", rt == Ropen, rt) - # a clone of an open dynamic fid takes no slot and is unopened - rt, _, _ = c.walk(60, 61, []) - ok("clone of an open dynamic fid is allowed", rt == Rwalk, rt) - ok("the clone is not open", c.err(Tread, struct.pack("<IQI", 61, 0, 10)) == "file not open") - ok("the clone cannot open (slots exhausted again)", c.err(Topen, struct.pack("<IB", 61, OREAD)) == "too many open dynamic files") + # an open fid cannot be cloned; a fresh walk to the same file takes no slot and is unopened + ok("clone of an open dynamic fid is refused", c.err(Twalk, struct.pack("<IIH", 60, 61, 0)) == E_BAD_USE) + c.walk_ok(0, 61, dyn[0]) + ok("the fresh fid is not open", c.err(Tread, struct.pack("<IQI", 61, 0, 10)) == E_BAD_USE) + ok("the fresh fid cannot open (slots exhausted again)", c.err(Topen, struct.pack("<IB", 61, OREAD)) == "too many open dynamic files") # Tversion releases everything: 8 opens succeed again rt, ms, _ = c.version(65536) ok("mid-session Tversion", rt == base.Rversion) @@ -310,12 +312,13 @@ def attack_static(path): ok(f"create in {p} is denied", c.err(base.Tcreate, struct.pack("<I", 1) + s16(b"x") + struct.pack("<IB", 0o644, OWRITE)) == "permission denied") ok(f"mkdir in {p} is denied", c.err(base.Tcreate, struct.pack("<I", 1) + s16(b"d") + struct.pack("<IB", DMDIR | 0o755, OREAD)) == "permission denied") ok(f"wstat of {p} is denied", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(mtime=1))) == "permission denied") - ok(f"wstat of {p} with all don't-care is denied too", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat())) == "permission denied") - ok(f"open {p} ORDWR is 'is a directory'", c.err(Topen, struct.pack("<IB", 1, ORDWR)) == "is a directory") - ok(f"open {p} OEXEC works like OREAD", c.open(1, OEXEC)[0] == Ropen) + ok(f"wstat of {p} with all don't-care is a no-op the engine answers itself", c.wstat(1, mkstat())[0] == Rwstat) + ok(f"open {p} ORDWR is refused by the engine", c.err(Topen, struct.pack("<IB", 1, ORDWR)) == E_PERM) + ok(f"open {p} OEXEC is refused by the engine", c.err(Topen, struct.pack("<IB", 1, OEXEC)) == E_PERM) + ok(f"open {p} OREAD", c.open(1, OREAD)[0] == Ropen) ok(f"write to open {p} is 'is a directory'", c.err(Twrite, struct.pack("<IQI", 1, 0, 1) + b"x") is not None) ok(f"remove {p} is denied", c.err(Tremove, struct.pack("<I", 1)) == "permission denied") - ok(f" and clunked", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok(f" and clunked", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) files = [[b"README"], [b"build", b"time"], [b"comptime", b"decls"], [b"comptime", b"types", b"Qid", b"fields"], [b"runtime", b"pid"], [b"runtime", b"fn", b"fib30"], [b"runtime", b"ctl"]] for names in files: p = "/" + b"/".join(names).decode() @@ -324,7 +327,7 @@ def attack_static(path): ok(f"'..' from {p} is 'not a directory'", c.err(Twalk, struct.pack("<IIH", 1, 2, 1) + s16(b"..")) == "not a directory") ok(f"wstat of {p} is denied", c.err(Twstat, struct.pack("<I", 1) + s16(mkstat(length=0))) == "permission denied") ok(f"remove {p} is denied", c.err(Tremove, struct.pack("<I", 1)) == "permission denied") - ok(f" and clunked", c.err(Tclunk, struct.pack("<I", 1)) == "unknown fid") + ok(f" and clunked", c.err(Tclunk, struct.pack("<I", 1)) == E_UNKNOWN_FID) if names[-1] != b"ctl": c.walk_ok(0, 1, names) ok(f"open {p} OWRITE is denied", c.err(Topen, struct.pack("<IB", 1, OWRITE)) == "permission denied") @@ -563,11 +566,11 @@ def attack_fid_table(path): good, bad, dt, dead = flood(c, ids, [b"scratch"]) ok(f"{n} walks with adversarial fid numbers all succeed", good == n and bad == 0 and not dead, (good, bad, dead)) print(f" {n} clones (provider handles) in {dt:.2f}s") - ok("the next fid is 'too many fids'", c.err(Twalk, struct.pack("<IIH", 0, 7, 0)) == "too many fids") - ok("attach at the limit is 'too many fids'", c.err(base.Tattach, struct.pack("<II", 7, base.NOFID) + s16(b"u") + s16(b"")) == "too many fids") - ok("an existing id is 'fid in use'", c.err(Twalk, struct.pack("<IIH", 0, ids[12345], 0)) == "fid in use") + ok("the next fid is 'too many fids'", c.err(Twalk, struct.pack("<IIH", 0, 7, 0)) == E_TOO_MANY_FIDS) + ok("attach at the limit is 'too many fids'", c.err(base.Tattach, struct.pack("<II", 7, base.NOFID) + s16(b"u") + s16(b"")) == E_TOO_MANY_FIDS) + ok("an existing id is 'fid in use'", c.err(Twalk, struct.pack("<IIH", 0, ids[12345], 0)) == E_FID_IN_USE) ok("a self-walk at the limit works", c.walk_ok(ids[5], ids[5], [b".."]) == 1) - ok("an unknown fid at the limit is 'unknown fid'", c.err(Tstat, struct.pack("<I", 7)) == "unknown fid") + ok("an unknown fid at the limit is 'unknown fid'", c.err(Tstat, struct.pack("<I", 7)) == E_UNKNOWN_FID) # clunk all, pipelined, in a hostile order (every third first, then the rest reversed) order = ids[::3] + ids[1::3][::-1] + ids[2::3][::-1] got = [0] @@ -588,12 +591,12 @@ def attack_fid_table(path): t.join(120) ok(f"{n} clunks all answered", got[0] == n and not dead[0] and not t.is_alive(), (got[0], dead[0])) print(f" {n} clunks in {time.time() - t0:.2f}s") - ok("clunk of a clunked fid is 'unknown fid'", c.err(Tclunk, struct.pack("<I", ids[100])) == "unknown fid") + ok("clunk of a clunked fid is 'unknown fid'", c.err(Tclunk, struct.pack("<I", ids[100])) == E_UNKNOWN_FID) # reuse: the whole table is available again with dense ids good, bad, dt, dead = flood(c, list(range(1, n + 1)), []) ok(f"{n} clones with dense ids after the churn all succeed", good == n and bad == 0 and not dead, (good, bad, dead)) print(f" {n} clones (reuse) in {dt:.2f}s") - ok("still 'too many fids' at the limit", c.err(Twalk, struct.pack("<IIH", 0, n + 1, 0)) == "too many fids") + ok("still 'too many fids' at the limit", c.err(Twalk, struct.pack("<IIH", 0, n + 1, 0)) == E_TOO_MANY_FIDS) rt, _, _ = c.version(65536) ok("Tversion after the fid churn", rt == base.Rversion) c.attach() @@ -635,63 +638,66 @@ def attack_flush(path): ok("server healthy after the flush storm", healthy(path)) -# --------------------------------------------------------------------------- msize 24 +# --------------------------------------------------------------------------- msize floor -def attack_msize24(path): - print("# msize 24: everything that fits is served, everything else is an Rerror that fits") +def attack_msize_floor(path): + print(f"# msize floor: below {MSIZE_MIN} the connection dies; at {MSIZE_MIN} everything that fits is served") + for ms in (24, 64, MSIZE_MIN - 1): + c = Nine(path) + rt, _, _ = c.version(ms) + ok(f"Tversion msize {ms}: closed", rt is None or expect_dead(c), rt) + c.close() c = Nine(path) - rt, ms, ver = c.version(24) - ok("Tversion 24", rt == base.Rversion and ms == 24, (rt, ms)) - rt, _, _ = c.attach(uname=b"u") # 20 bytes; Rattach is 20 - ok("Tattach at msize 24", rt == base.Rattach, rt) - e = c.err(Tstat, struct.pack("<I", 0)) - ok("Tstat: Rerror truncated to 15 bytes ('reply too large')", e == "reply too large", e) - rt, _, rb = c.walk(0, 1, [b"build"]) # Twalk 24, Rwalk 22 - ok("Twalk of one 5-byte name", rt == Rwalk, rt) - e = c.err(Twalk, struct.pack("<IIH", 0, 2, 2) + s16(b".") + s16(b".")) # 23 bytes; Rwalk would be 35 - ok("Twalk of two names cannot be answered: 'reply too large'", e == "reply too large", e) - ok("newfid unbound after the refused walk", c.err(Tclunk, struct.pack("<I", 2)) == "unknown fid") - rt, _, _ = c.open(1, OREAD) # Ropen 24 - ok("Topen at msize 24", rt == Ropen, rt) - rt, d = c.read(1, 0, 4096) # count clamped to msize - iohdrsz = 0 - ok("Tread of a directory at msize 24 answers an empty Rread (no split record)", rt == Rread and d == b"", (rt, d)) - e = c.err(Tread, struct.pack("<IQI", 1, 1, 4096)) - ok("dir read at offset 1 is 'bad offset'", e == "bad offset", e) - rt, _, _ = c.clunk(1) - ok("Tclunk at msize 24", rt == Rclunk, rt) - rt, _, _ = c.walk(0, 1, [b"vars"]) # Twalk 23 - rt, _, _ = c.walk(1, 1, [b"state"]) # 23 - rt, _, _ = c.walk(1, 1, [b"value"]) # 23 - ok("walk to /vars/state/value in 3 self-walks", rt == Rwalk, rt) + rt, ms, ver = c.version(MSIZE_MIN) + ok(f"Tversion {MSIZE_MIN}", rt == base.Rversion and ms == MSIZE_MIN, (rt, ms)) + rt, _, _ = c.attach(uname=b"u") + ok("Tattach at the floor", rt == base.Rattach, rt) + rt, st = c.stat(0) + ok("Tstat of the root fits", rt == Rstat and st["name"] == b"/", (rt, st)) + rt, _, rb = c.walk(0, 1, [b"."] * 16) + ok("a full 16-element Rwalk is exactly the floor", rt == Rwalk and struct.unpack_from("<H", rb)[0] == 16, rt) + c.clunk(1) + # an Rstat that cannot fit is an Rerror, not a dead connection: a long name in /scratch + long_name = b"m" * 180 # Tcreate (18 + 180 bytes) fits; the Rstat (61 + 180) does not + c.walk_ok(0, 1, [b"scratch"]) + rt, _, _ = c.create(1, long_name, 0o644, OREAD) + ok("create a long name at the floor", rt == Rcreate, rt) + e = c.err(Tstat, struct.pack("<I", 1)) + ok("Tstat that does not fit is 'Invalid argument'", e == E_INVAL, e) + ok("remove it", c.remove(1)[0] == Rremove) + rt, _, _ = c.walk(0, 1, [b"build"]) rt, _, _ = c.open(1, OREAD) - ok("open a dynamic file at msize 24", rt == Ropen, rt) - rt, d = c.read(1, 0, 4096) - ok("read of a dynamic file at msize 24 is an empty Rread", rt == Rread and d == b"", (rt, d)) + ok("Topen at the floor", rt == Ropen, rt) + rt, d = c.read(1, 0, 4096) # count clamped to msize - 11 + ok("a directory read at the floor yields whole records", rt == Rread and 0 < len(d) <= MSIZE_MIN - 11 and records(d), (rt, len(d) if d else d)) + e = c.err(Tread, struct.pack("<IQI", 1, 1, 4096)) + ok("dir read at offset 1 is a bad offset", e == E_BAD_OFFSET, e) rt, _, _ = c.clunk(1) - for nm in (b"vars", b"state", b"f", b"ticks", b"value"): # each Twalk <= 24 bytes + ok("Tclunk at the floor", rt == Rclunk, rt) + for nm in (b"vars", b"state", b"f", b"ticks", b"value"): rt, _, _ = c.walk(0 if nm == b"vars" else 1, 1, [nm]) ok("walk to /vars/state/f/ticks/value in 5 self-walks", rt == Rwalk, rt) rt, _, _ = c.open(1, OWRITE) - ok("open a writable value at msize 24", rt == Ropen, rt) - rt, _, _ = c.write(1, 0, b"5") # Twrite 24, Rwrite 11 - ok("Twrite of one byte at msize 24", rt == Rwrite, rt) + ok("open a writable value at the floor", rt == Ropen, rt) + rt, _, _ = c.write(1, 0, b"5") + ok("Twrite of one byte at the floor", rt == Rwrite, rt) e = c.err(Twrite, struct.pack("<IQI", 1, 0, 0) + b"") - ok("empty write to a value at msize 24 is 'bad value'", e == "bad value", e) + ok("empty write to a value at the floor is 'bad value'", e == "bad value", e) rt, _, _ = c.clunk(1) - ok("clunk at msize 24", rt == Rclunk, rt) + ok("clunk at the floor", rt == Rclunk, rt) rt, ms, _ = c.version(65536) ok("renegotiate a big msize on the same connection", rt == base.Rversion and ms == 65536, (rt, ms)) c.attach() ok("normal service resumes", c.path_read([b"build", b"zig_version"]) not in (None, b"")) c.close() - # frames larger than 24 after negotiating 24 kill the connection + # frames larger than the negotiated msize kill the connection c = Nine(path) - c.version(24) - c.raw(frame(base.Tattach, 1, struct.pack("<II", 0, base.NOFID) + s16(b"longer-name") + s16(b""))) - ok("a 30-byte Tattach at msize 24: connection closed", expect_dead(c)) + c.version(MSIZE_MIN) + c.raw(frame(base.Tattach, 1, struct.pack("<II", 0, base.NOFID) + s16(b"u" * 210) + s16(b""))) + ok("an over-long Tattach at the floor: connection closed", expect_dead(c)) c.close() - ok("server healthy after msize-24 attacks", healthy(path)) + ok("server healthy after msize-floor attacks", healthy(path)) # --------------------------------------------------------------------------- directory offsets @@ -727,15 +733,15 @@ def attack_dir_offsets(path): rt, d1 = c.read(1, r0, r1) ok(f"{p}: read at the record boundary returns the next record", rt == Rread and d1 == recs[1][1], (rt, len(d1) if d1 else d1)) e = c.err(Tread, struct.pack("<IQI", 1, r0 + r1 + 1, 65000)) - ok(f"{p}: offset boundary+1 is 'bad offset'", e == "bad offset", e) + ok(f"{p}: offset boundary+1 is 'bad offset'", e == E_BAD_OFFSET, e) e = c.err(Tread, struct.pack("<IQI", 1, r0 + r1 - 1, 65000)) - ok(f"{p}: offset boundary-1 is 'bad offset'", e == "bad offset", e) + ok(f"{p}: offset boundary-1 is 'bad offset'", e == E_BAD_OFFSET, e) e = c.err(Tread, struct.pack("<IQI", 1, r0, 65000)) - ok(f"{p}: re-reading an earlier boundary is 'bad offset'", e == "bad offset", e) + ok(f"{p}: re-reading an earlier boundary is 'bad offset'", e == E_BAD_OFFSET, e) rt, rest = c.read(1, r0 + r1, 65000) ok(f"{p}: after a bad offset the good boundary still continues", rt == Rread and rest == d[r0 + r1:], rt) - rt, dd = c.read(1, 0, r0 - 1) - ok(f"{p}: count one short of a record returns nothing (no split)", rt == Rread and dd == b"", (rt, dd)) + e = c.err(Tread, struct.pack("<IQI", 1, 0, r0 - 1)) + ok(f"{p}: count one short of a record is refused (no split)", e == E_INVAL, e) rt, dd = c.read(1, 0, 65000) ok(f"{p}: offset 0 restarts and yields the same bytes", rt == Rread and dd == d) rt, dd = c.read(1, len(d), 65000) @@ -817,17 +823,17 @@ def attack_fid_states(path): c.walk_ok(0, 1, S) rt, _, _ = c.create(1, b"f", 0o644, ORDWR) ok("create f", rt == Rcreate) - ok("open of an open fid is 'file already open'", c.err(Topen, struct.pack("<IB", 1, OREAD)) == "file already open") - ok("walk with names from an open fid is 'file already open'", c.err(Twalk, struct.pack("<IIH", 1, 2, 1) + s16(b".")) == "file already open") - ok("create on an open fid is 'file already open'", c.err(base.Tcreate, struct.pack("<I", 1) + s16(b"g") + struct.pack("<IB", 0o644, OWRITE)) == "file already open") - rt, _, _ = c.walk(1, 2, []) - ok("clone of an open fid is allowed", rt == Rwalk) - ok("the clone is not open", c.err(Tread, struct.pack("<IQI", 2, 0, 10)) == "file not open") + ok("open of an open fid is 'file already open for I/O'", c.err(Topen, struct.pack("<IB", 1, OREAD)) == E_ALREADY_OPEN) + ok("walk with names from an open fid is 'bad use of fid'", c.err(Twalk, struct.pack("<IIH", 1, 2, 1) + s16(b".")) == E_BAD_USE) + ok("create on an open fid is 'file already open for I/O'", c.err(base.Tcreate, struct.pack("<I", 1) + s16(b"g") + struct.pack("<IB", 0o644, OWRITE)) == E_ALREADY_OPEN) + ok("clone of an open fid is refused", c.err(Twalk, struct.pack("<IIH", 1, 2, 0)) == E_BAD_USE) + ok("a fresh walk reaches the open file", c.walk_ok(0, 2, S + [b"f"]) == 3) + ok("the fresh fid is not open", c.err(Tread, struct.pack("<IQI", 2, 0, 10)) == E_BAD_USE) rt, _, _ = c.open(2, OREAD) - ok("the clone opens independently", rt == Ropen) + ok("the fresh fid opens independently", rt == Ropen) c.write(1, 0, b"data") rt, d = c.read(2, 0, 10) - ok("the clone sees the write", rt == Rread and d == b"data", d) + ok("the second fid sees the write", rt == Rread and d == b"data", d) rt, _, _ = c.wstat(2, mkstat(name=b"renamed")) ok("wstat through an open fid works", rt == Rwstat) rt, _, _ = c.remove(1) @@ -982,7 +988,7 @@ def main(): attack_dir_offsets(path) attack_ctl(path) attack_fid_states(path) - attack_msize24(path) + attack_msize_floor(path) attack_flush(path) attack_fid_table(path) if not args.fast: @@ -98,7 +98,8 @@ lists the steps). New related programs follow the same layout. `web/static/`). Always built; steps `serve`, `web`, `http-test`, `e2e`. * [`9proc/`](9proc/README.md) — a 9P debug/introspection server as a library (module `9proc`, exported next to `cloud9`; freestanding - core, Linux debug layer) and its demo binary `9proc-demo`. + core that is a backend of `fs.Server`, Linux debug layer) and its demo + binary `9proc-demo`. `-D9proc=[bool]`; steps `9proc`, `9proc-test`, `9proc-check-freestanding`, `9proc-debug-test`, `9proc-debug-itest`, `9proc-adv`. diff --git a/docs/design.md b/docs/design.md index dda10a6..8387a4d 100644 --- a/docs/design.md +++ b/docs/design.md @@ -104,13 +104,31 @@ negotiating. Every table is sized at comptime by `fs.Options`: `fid_capacity` (256), `slot_capacity` (32), `park_data_max` (128), `name_capacity` (28, at most -255) and `username_capacity` (28); the defaults are the editor's, except the -name capacity, which is the board's. `msize_min` (217) is the smallest -negotiable msize, one full Rwalk. Create, remove, auth, attaching a named -tree and any wstat other than a zero-length truncation are refused. Rerror -strings are the ones Linux v9fs maps back to errnos (`fs.errString`). The +255; zero keeps no names, a stat's name is then the one its getattr +answers and the backend judges name lengths), `username_capacity` (28) and +`fid_index` (off: an open-addressing index from fid number to slot, two +bytes per bucket, for tables of thousands of fids; `InitOptions.seed` +salts it); the defaults are the editor's, except the name capacity, which +is the board's. `msize_min` (217) is the smallest negotiable msize, one +full Rwalk. Auth and attaching a named tree are refused, and so are +create, remove and any wstat other than a zero-length truncation unless +the backend declares the feature: a backend may carry `pub const features: +fs.Features` naming `create` (Tcreate becomes an `open` with `create`, +`data` the name, `perm` and `omode`, answered with the new node's `attr` +and handle), `remove` (Tremove, and ORCLOSE on clunk or hangup, become a +`release` with `remove`; its error is the Rremove's), `wstat` (a Twstat +becomes a `setattr` whose `set` names the changed fields: `data` the new +name, `perm`, `mtime`, `length`; the fields the engine owns must be "don't +care") and `references` (every lookup result, "." and a fid clone +included, is a reference the backend gets exactly one `release` for, with +`opened` telling whether an open handle goes with it). An `Attr` may add +a qid `version`, `atime`, a qid `path` distinct from the node, and the +append-only and exclusive-use bits; a reply's `ename` replaces +`errString(errno)` as the Rerror text. Rerror strings the engine emits on +its own are the ones Linux v9fs maps back to errnos (`fs.errString`). The engine allocates nothing and makes no OS calls; a session is `push()`, -`retry()`, `next()`, `reply()`, `output()`, `wrote()`. +`retry()`, `next()`, `reply()`, `output()`, `wrote()`; `fidCount()` counts +the fids held. # Related programs @@ -28,7 +28,11 @@ 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 ---- @@ -62,12 +66,56 @@ pub const Attr = struct { 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 name or a write's bytes and is borrowed until the -/// reply, unless the write parks, in which case the engine keeps a copy. +/// `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, @@ -77,6 +125,21 @@ pub const Req = struct { 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 @@ -92,6 +155,9 @@ pub fn ReplyWith(comptime Payload: type) 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; @@ -115,11 +181,14 @@ pub const E = struct { 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. @@ -151,11 +220,14 @@ pub fn errString(errno: u16) []const u8 { 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", }; } @@ -177,9 +249,15 @@ pub const Options = struct { /// 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 { @@ -192,29 +270,58 @@ comptime { assert(c9.otrunc | c9.ocexec | c9.orclose == 112); } -fn qidOf(node: u64, dir: bool) Qid { - return .{ .type = if (dir) qtdir else qtfile, .version = 0, .path = node }; +/// 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`). 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. +/// `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 == 0 or opts.name_capacity > 255) @compileError("9P backend name capacity must fit a directory entry"); + 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" }) |field| { + 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(); @@ -228,10 +335,24 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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, read, readdir, write, clunk, remove, stat, wstat }; + const Kind = enum { none, attach, walk, open, create, read, readdir, write, clunk, remove, stat, wstat }; pub const Fid = struct { used: bool = false, @@ -241,14 +362,23 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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, @@ -277,25 +407,44 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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, + /// 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 }; + 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 { @@ -305,20 +454,38 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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) |*f| { - if (!f.used) continue; - if (f.open) f.orphan = true else f.* = .{}; + 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); } @@ -342,8 +509,11 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { } fn fail(s: *Self, tag: u16, ename: []const u8) void { - assert(ename.len <= errmax); - s.emit(tag, .{ .rerror = .{ .ename = ename } }); + 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 { @@ -351,18 +521,109 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { return s.seq; } - fn findFid(s: *Self, fid: u32) ?usize { + // ---- 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 freeFid(s: *Self) ?usize { + 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.fids[i] = .{}; + if (s.findFid(fid)) |i| s.releaseSlot(i); } fn findSlot(s: *Self, req_tag: u64) ?usize { @@ -386,6 +647,12 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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 { @@ -414,7 +681,8 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { if (s.job.kind != .none) { if (s.job.req_tag != 0) return null; if (s.stepJob()) |req| return req; - assert(s.job.kind == .none); + // 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; @@ -431,16 +699,20 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { } fn orphan(s: *Self) ?Backend.Req { - for (&s.fids) |*f| { + if (s.norphans == 0) return null; + for (&s.fids, 0..) |*f, i| { if (!f.used or !f.orphan) continue; - assert(f.open); + 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, }; - f.* = .{}; + s.releaseSlot(i); return req; } return null; @@ -462,7 +734,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { switch (got.msg) { .tversion => |m| s.version(got.tag, m.msize, m.version), .tauth => s.fail(got.tag, e_no_auth), - .tcreate => s.fail(got.tag, e_perm), + .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)), @@ -472,7 +744,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { .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.tag, m.fid, m.stat), + .twstat => |m| s.wstat(got, m.fid, m.stat), else => s.fail(got.tag, e_botch), } } @@ -494,7 +766,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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.freeFid() == null) return s.fail(tag, e_too_many_fids); + 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 }; } @@ -506,29 +778,32 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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.freeFid() == null) return s.fail(tag, e_too_many_fids); + if (!s.hasFreeFid()) return s.fail(tag, e_too_many_fids); } - if (nwname == 0) { + if (nwname == 0 and (newfid == fid or !refs)) { if (newfid != fid) { - const j = s.freeFid().?; + 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 (!s.fids[i].dir) return s.fail(tag, e_not_dir); + 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, @@ -539,7 +814,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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) return s.fail(tag, e_perm); + 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); @@ -550,6 +825,21 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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]; @@ -585,11 +875,11 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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) { + if (s.fids[i].open or refs or (kind == .remove and features.remove)) { s.job = .{ .kind = kind, .tag = tag, .fid = fid }; return; } - s.fids[i] = .{}; + s.releaseSlot(i); if (kind == .remove) s.fail(tag, e_perm) else s.emit(tag, .rclunk); } @@ -598,24 +888,58 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { s.job = .{ .kind = .stat, .tag = tag, .fid = fid }; } - fn wstat(s: *Self, tag: u16, fid: u32, st: Stat) void { - if (s.findFid(fid) == null) return s.fail(tag, e_unknown_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.mode != std.math.maxInt(u32) or - st.atime != 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 or st.uid.len != 0 or st.gid.len != 0 or st.muid.len != 0) + 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 (st.length == std.math.maxInt(u64)) { + 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; } - if (st.length != 0) return s.fail(tag, e_trunc_only); - s.job = .{ .kind = .wstat, .tag = tag, .fid = fid }; + 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 { @@ -646,6 +970,16 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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 }), @@ -658,7 +992,19 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { .node = f.node, .truncate = true, }); - return s.ask(.{ .tag = s.tick(), .op = .open, .node = f.node }); + 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; @@ -701,6 +1047,8 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { .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 => { @@ -709,38 +1057,54 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { }, .wstat => { const f = s.jobFid() orelse return null; - return s.ask(.{ .tag = s.tick(), .op = .setattr, .node = f.node, .truncate = true }); + 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.len > name_capacity) { + if (name_capacity != 0 and name.len > name_capacity) { s.stopWalk(e_illegal_name); return null; } - if (std.mem.eql(u8, name, ".")) { - j.wqid[j.nwqid] = qidOf(j.node, j.dir); + if (!refs and std.mem.eql(u8, name, ".")) { + j.wqid[j.nwqid] = j.qid; j.nwqid += 1; j.step += 1; continue; } - @memcpy(j.name[0..name.len], name); - j.name_len = @intCast(name.len); + 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) break :pick s.findFid(j.fid) orelse { - s.fail(j.tag, e_unknown_fid); - s.finishJob(); - return null; - }; - break :pick s.freeFid() orelse { - s.fail(j.tag, e_too_many_fids); - s.finishJob(); + 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; }; }; @@ -750,20 +1114,35 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { .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(); } @@ -778,17 +1157,27 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { assert(j.req_tag == r.tag); j.req_tag = 0; + if (j.forgetting) { + j.forgetting = false; + return; + } if (j.kind == .clunk or j.kind == .remove) { s.dropFid(j.fid); - if (j.kind == .remove) s.fail(j.tag, e_perm) else s.emit(j.tag, .rclunk); + 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 == .again) return s.parkJob(); if (r.status == .err) { - const ename = errString(r.errno); - if (j.kind == .walk) return s.stopWalk(ename); - s.fail(j.tag, ename); + 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; } @@ -796,7 +1185,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { switch (j.kind) { .none, .clunk, .remove => unreachable, .attach => { - const i = s.freeFid() orelse { + const i = s.takeFid() orelse { s.fail(j.tag, e_too_many_fids); s.finishJob(); return; @@ -808,22 +1197,25 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { .node = node, .dir = r.attr.dir, .perm = r.attr.mode, + .qid = qidFrom(node, r.attr), }; - s.fids[i].name[0] = '/'; - s.fids[i].name_len = 1; - s.emit(j.tag, .{ .rattach = .{ .qid = qidOf(node, r.attr.dir) } }); + 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) { - j.name_len = @intCast(@min(r.attr.name.len, j.name.len)); - @memcpy(j.name[0..j.name_len], r.attr.name[0..j.name_len]); - } + 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.wqid[j.nwqid] = qidOf(j.node, j.dir); - j.nwqid += 1; + 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 => { @@ -832,18 +1224,52 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { return; } const f = s.jobFid() orelse return; - if (r.attr.node != 0) f.node = r.attr.node; + 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 = qidOf(f.node, f.dir), + .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(); @@ -860,6 +1286,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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) @@ -868,6 +1295,13 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { 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(); }, @@ -921,7 +1355,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { return; } if (r.status == .err) { - s.fail(sl.tag, errString(r.errno)); + s.failReply(sl.tag, r); sl.* = .{}; return; } @@ -951,7 +1385,7 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { const rec: Stat = .{ .type = 0, .dev = 0, - .qid = qidOf(std.mem.readInt(u64, staging[i..][0..8], .little), dir), + .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, @@ -983,12 +1417,12 @@ pub fn Server(comptime Backend: type, comptime opts: Options) type { return .{ .type = 0, .dev = 0, - .qid = qidOf(if (a.node != 0) a.node else f.node, a.dir), - .mode = (if (a.dir) dmdir else 0) | @as(u32, a.mode), - .atime = 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 = f.name[0..f.name_len], + .name = if (name_capacity == 0) a.name else f.name[0..f.name_len], .uid = who, .gid = who, .muid = who, @@ -2332,3 +2766,527 @@ test "fs client: hangup and a dead connection refuse everything after" { 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); +} |