summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/fs.zig1126
1 files changed, 1042 insertions, 84 deletions
diff --git a/src/fs.zig b/src/fs.zig
index 69cdf9f..1641171 100644
--- a/src/fs.zig
+++ b/src/fs.zig
@@ -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);
+}
generated by cgit v1.3 (git 2.53.0) at 2026-10-02 06:39:00 +0000