summaryrefslogtreecommitdiff
path: root/src/replica.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/replica.zig')
-rw-r--r--src/replica.zig883
1 files changed, 862 insertions, 21 deletions
diff --git a/src/replica.zig b/src/replica.zig
index 032e50af..5c965b2b 100644
--- a/src/replica.zig
+++ b/src/replica.zig
@@ -44,11 +44,34 @@ fn header(buf: []u8, who: u16, seq: u32) void {
std.mem.writeInt(u32, buf[2..6], seq, .little);
}
-pub const Unit = struct { origin: u16, seq: u32, tape: []const u8 };
+/// A unit's head: its origin and seq, then the authority's clocks when it
+/// was made (realtime and monotonic, ns), which a replica's guesses of the
+/// session's clock start from.
+const unit_head = head_len + 16;
+
+pub const Unit = struct { origin: u16, seq: u32, real_ns: i64 = 0, mono_ns: i64 = 0, tape: []const u8 };
pub fn parseUnit(msg: []const u8) ?Unit {
- if (msg.len < head_len) return null;
- return .{ .origin = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .tape = msg[head_len..] };
+ if (msg.len < unit_head) return null;
+ return .{
+ .origin = std.mem.readInt(u16, msg[0..2], .little),
+ .seq = std.mem.readInt(u32, msg[2..6], .little),
+ .real_ns = std.mem.readInt(i64, msg[6..14], .little),
+ .mono_ns = std.mem.readInt(i64, msg[14..22], .little),
+ .tape = msg[unit_head..],
+ };
+}
+
+fn clockNs(id: std.c.clockid_t) i64 {
+ var ts: std.c.timespec = undefined;
+ if (std.c.clock_gettime(id, &ts) != 0) return 0;
+ return @as(i64, ts.sec) * std.time.ns_per_s + ts.nsec;
+}
+
+fn unitHeader(buf: []u8, origin: u16, seq: u32) void {
+ header(buf, origin, seq);
+ std.mem.writeInt(i64, buf[6..14], clockNs(.REALTIME), .little);
+ std.mem.writeInt(i64, buf[14..22], clockNs(.MONOTONIC), .little);
}
pub const Input = struct { client: u16, seq: u32, event: pardes.Event };
@@ -87,6 +110,13 @@ fn nowNs() u64 {
return pardes.FrameStats.nowNs();
}
+/// The `p`th percentile of `samples` (sorted here); 100 is the worst.
+fn pctOf(samples: []u64, p: usize) u64 {
+ if (samples.len == 0) return 0;
+ std.mem.sort(u64, samples, {}, std.sort.asc(u64));
+ return samples[@min(samples.len - 1, samples.len * p / 100)];
+}
+
// ---- the authority ----
pub const Authority = struct {
@@ -142,8 +172,8 @@ pub const Authority = struct {
/// done straight on the core).
pub fn unit(a: *Authority, origin: u16, seq: u32) ![]const u8 {
a.out.clearRetainingCapacity();
- try a.out.appendNTimes(a.gpa, 0, head_len);
- header(a.out.items, origin, seq);
+ try a.out.appendNTimes(a.gpa, 0, unit_head);
+ unitHeader(a.out.items, origin, seq);
try a.out.appendSlice(a.gpa, tape.taken(&a.t));
tape.clearTaken(&a.t);
return a.out.items;
@@ -212,7 +242,7 @@ pub const Authority = struct {
const was = Stepping.begin(&a.t, null);
a.core.toView(a.view_of[in.client]);
a.core.update(in.event);
- a.core.pump(a.host) catch {};
+ a.core.step();
was.end();
return a.unit(in.client, in.seq);
}
@@ -437,7 +467,7 @@ pub const Stats = struct {
}
};
-const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null };
+const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0 };
pub const Replica = struct {
gpa: Allocator,
@@ -464,6 +494,26 @@ pub const Replica = struct {
out: std.ArrayListUnmanaged(u8) = .empty,
/// Nanoseconds of the rollback being made, until its reapply.
recovering: ?u64 = null,
+ /// The digest the last confirmed unit ended on (its last record's
+ /// bytes): a unit of another's that ends on it again (the session's
+ /// pump that took this replica's input in, and moved nothing) leaves
+ /// the speculation on top as it was.
+ last_digest: std.ArrayListUnmanaged(u8) = .empty,
+ /// Units of another's taken so, no rollback made.
+ neutral: u32 = 0,
+ /// What it shows changed since the host last drew it: a unit replayed
+ /// on it, a rollback (a unit that confirmed what it applied, or moved
+ /// nothing, changes nothing to draw).
+ moved: bool = false,
+ /// A client of a session elsewhere (`initDump`): the session's clock is
+ /// guessed, never read here -- its last unit's reading, plus the time
+ /// since it came, plus a round trip (the input reaches the session that
+ /// much later). In process, both read one clock.
+ guess: bool = false,
+ stamp: struct { real_ns: i64 = 0, mono_ns: i64 = 0, at_ns: u64 = 0 } = .{},
+ rtt_ns: u64 = 0,
+ gmtoff: i32 = 0,
+
/// Its terminals' screen state, as the authority's deltas made it.
screens: [pardes.MAX_PANES]?ScreenOf = @splat(null),
screen_out: std.ArrayListUnmanaged(u8) = .empty,
@@ -497,6 +547,43 @@ pub const Replica = struct {
return r;
}
+ /// A replica of a session elsewhere, as its walker dump (src/dump.zig)
+ /// is: what a client of a socket joins with. `opts` are this process's
+ /// (a replica's own allocators and names); its core's allocator is the
+ /// rollback epoch's, but for images and PDFs, whose workers allocate on
+ /// threads of their own. ponytail: a picture's pixels freed while a copy
+ /// is held are not put off; a rollback over one shows an image a frame
+ /// late at worst... or reads freed pixels, which no test session has.
+ pub fn initDump(gpa: Allocator, id: u16, view: u8, bytes: []const u8, opts: pardes.Options) !*Replica {
+ const r = try gpa.create(Replica);
+ r.* = .{ .gpa = gpa, .id = id, .view = view, .t = tape.memory(gpa), .guess = true };
+ r.t.headless = true;
+ errdefer {
+ tape.release(&r.t);
+ r.epoch.deinit();
+ gpa.destroy(r);
+ }
+ const epoch = r.epoch.allocator();
+ r.t.core_gpa = epoch;
+ var o = opts;
+ o.frame_allocator = epoch;
+ o.tree_sitter_allocator = epoch;
+ o.image_allocator = o.image_allocator orelse std.heap.c_allocator;
+ o.pdf_allocator = o.pdf_allocator orelse std.heap.c_allocator;
+ // The session's store and Recent are the authority's.
+ o.store_path = null;
+ const c = try pardes.dump.load(epoch, o, bytes, null);
+ // What loading queued (a watch, a theme asked for) is the
+ // authority's errand, done there already: the session was dumped
+ // between steps, with nothing queued.
+ c.effects_len = 0;
+ c.effects_head = 0;
+ c.in_len = 0;
+ c.in_head = 0;
+ tape.adoptCore(&r.t, c);
+ return r;
+ }
+
pub fn deinit(r: *Replica) void {
for (&r.screens) |*slot| if (slot.*) |*sc| sc.rep.deinit(terminal.emulator_gpa);
if (r.t.core) |c| {
@@ -512,6 +599,7 @@ pub const Replica = struct {
r.since.deinit(r.gpa);
r.out.deinit(r.gpa);
r.screen_out.deinit(r.gpa);
+ r.last_digest.deinit(r.gpa);
r.stats.deinit(r.gpa);
tape.release(&r.t);
if (r.diverged) |why| r.gpa.free(why);
@@ -539,7 +627,7 @@ pub const Replica = struct {
const n = (try wire.encodeClient(room[head_len..], .{ .event = ev })).len;
header(room, r.id, seq);
const msg = try r.gpa.dupe(u8, room[0 .. head_len + n]);
- try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg });
+ try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg, .sent_ns = nowNs() });
r.dirty = true;
r.settle();
if (r.t.screen_state and r.diverged == null) r.echo.typed(r.core(), r.view, ev, seq, r.applied == r.pending.items.len);
@@ -554,6 +642,21 @@ pub const Replica = struct {
const u = parseUnit(msg) orelse return r.fail("a unit too short to read");
r.stats.units += 1;
if (u.origin == r.id) if (r.t.core) |c| r.echo.confirmed(c, u.seq);
+ // A copy taken ahead (`ready`), nothing on top: the unit moves the
+ // state it was of.
+ if (r.applied == 0 and r.copy.held) {
+ r.copy.release();
+ rollback.Epoch.select(null);
+ r.clearSince();
+ }
+ if (r.guess) {
+ r.stamp = .{ .real_ns = u.real_ns, .mono_ns = u.mono_ns, .at_ns = nowNs() };
+ if (u.origin == r.id) for (r.pending.items) |p| if (p.seq == u.seq) {
+ // Sent to confirmed: what reaching the session takes, and back.
+ if (p.sent_ns != 0) r.rtt_ns = nowNs() -| p.sent_ns;
+ break;
+ };
+ }
const was = Stepping.begin(&r.t, &r.epoch);
defer was.end();
if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and
@@ -579,6 +682,25 @@ pub const Replica = struct {
}
return;
}
+ const ends = lastDigest(u.tape);
+ defer if (ends) |d| {
+ r.last_digest.clearRetainingCapacity();
+ r.last_digest.appendSlice(r.gpa, d) catch {};
+ };
+ if (r.applied > 0 and u.origin != r.id and ends != null and std.mem.eql(u8, ends.?, r.last_digest.items)) {
+ // Nothing a digest covers moved: what was applied on top is
+ // what the session will apply on top of it. Replayed when the
+ // copy is next put back.
+ r.neutral += 1;
+ const kept = r.gpa.dupe(u8, u.tape) catch return r.fail("out of memory");
+ r.since.append(r.gpa, kept) catch return r.fail("out of memory");
+ if (r.since.items.len >= rebase_after) {
+ r.stats.rebases += 1;
+ r.toConfirmed();
+ r.dirty = true;
+ }
+ return;
+ }
if (r.applied > 0) {
if (u.origin == r.id) r.stats.mispredicted += 1 else r.stats.foreign += 1;
if (u.origin == r.id and std.c.getenv("PARDES_REPLICA_TRACE") != null) {
@@ -593,6 +715,7 @@ pub const Replica = struct {
r.recovering = nowNs();
r.toConfirmed();
}
+ r.moved = true;
if (tape.replayUnit(&r.t, u.tape)) |why| {
if (std.c.getenv("PARDES_REPLICA_TRACE") != null) {
var w: std.Io.Writer.Allocating = .init(r.gpa);
@@ -657,17 +780,10 @@ pub const Replica = struct {
/// pending[applied] applied on top: whether it was.
fn speculate(r: *Replica) bool {
const p = &r.pending.items[r.applied];
+ // Every kind, a view's own (a resize, the pointer) too: each client
+ // has its own view, and what reaches the authority's (a pty's size,
+ // the pointer over a sliding pane) stops it as any host call does.
const in = parseInput(p.msg) orelse return false;
- switch (in.event) {
- .key, .paste, .command => {},
- else => {
- // The view's (a resize, the pointer): the authority's for
- // now, phase 4's views to come.
- r.stats.unspeculated += 1;
- r.blocked = p.seq;
- return false;
- },
- }
const c = r.core();
if (!r.copy.held) {
const t0 = nowNs();
@@ -683,6 +799,10 @@ pub const Replica = struct {
if (checked) terminalDigests(c, &terminals);
const t0 = nowNs();
tape.beginSpeculation(&r.t);
+ r.t.guess = if (r.guess) guess: {
+ const since: i64 = @intCast(nowNs() -| r.stamp.at_ns + r.rtt_ns);
+ break :guess .{ .real_ns = r.stamp.real_ns + since, .mono_ns = r.stamp.mono_ns + since, .gmtoff = r.gmtoff };
+ } else null;
c.toView(r.view);
// Input into a terminal is the authority's: its step reads the
// emulator (rows, cursor, modes), which here is the last delta's and
@@ -690,7 +810,7 @@ pub const Replica = struct {
// echo.
if (r.t.screen_state) if (c.panes[c.active]) |pane| if (pane.isTerminal()) tape.poison();
c.update(in.event);
- c.pump(c.host) catch {};
+ c.step();
const clean = tape.endSpeculation(&r.t);
const dt = nowNs() - t0;
// Where a blob was written, should one be: the input that did.
@@ -699,6 +819,7 @@ pub const Replica = struct {
// Undone, and the earlier ones applied again on the confirmed
// position: this one waits for the authority.
r.stats.stopped += 1;
+ if (std.c.getenv("PARDES_REPLICA_TRACE") != null) std.debug.print("replica {d}: its input {d} ({t}) stopped at a host call: it waits\n", .{ r.id, p.seq, in.event });
r.blocked = p.seq;
const upto = r.applied;
r.toConfirmed();
@@ -732,9 +853,41 @@ pub const Replica = struct {
}
/// Nothing pending and nothing applied: the replica is the authority's
- /// confirmed state, which `digest` says.
+ /// confirmed state, which `digest` says (a copy taken ahead, `ready`,
+ /// has nothing on top of it).
pub fn quiet(r: *const Replica) bool {
- return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held;
+ return r.pending.items.len == 0 and r.applied == 0;
+ }
+
+ /// The copy taken now, while nothing is pending (the host is idle, its
+ /// frame drawn), so that the next input of its own is applied at once
+ /// without taking it: a copy is a megabyte saved. Let go when a unit
+ /// comes first.
+ pub fn ready(r: *Replica) void {
+ if (r.copy.held or r.pending.items.len > 0 or r.diverged != null) return;
+ const c = r.core();
+ const t0 = nowNs();
+ rollback.Epoch.select(&r.epoch);
+ defer rollback.Epoch.select(null);
+ r.copy.take(&r.epoch, c) catch return;
+ r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {};
+ r.stats.copy_bytes += r.copy.savedBytes();
+ r.stats.copies += 1;
+ }
+
+ /// Whether its core loaded from the dump is the session as it was
+ /// dumped, by the welcome's `digest`.
+ pub fn loaded(r: *Replica, want: u64) bool {
+ return tape.digestOf(r.core()) == want;
+ }
+
+ /// Its own view drawn and presented through `present`, between steps
+ /// (views.drawOne): nothing the digest covers moves. The epoch's trees
+ /// held while a copy is (a render can make or drop a syntax tree).
+ pub fn draw(r: *Replica, present: pardes.views.Present) void {
+ rollback.Epoch.select(&r.epoch);
+ defer rollback.Epoch.select(null);
+ pardes.views.drawOne(r.core(), r.view, present) catch {};
}
/// One of the authority's terminal messages (`Screens.flush`, or an
@@ -827,6 +980,20 @@ pub const Replica = struct {
}
};
+/// The bytes of a unit's last digest record: the state it ended on; null
+/// for one that says what the host wrote or which host it is (a replica's
+/// core takes those only by replaying the unit).
+fn lastDigest(bytes: []const u8) ?[]const u8 {
+ var r: walk.Reader = .{ .bytes = bytes };
+ var last: ?[]const u8 = null;
+ while (true) {
+ const head = r.take(5) catch return last;
+ const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return last;
+ if (head[0] == tape.digest_kind) last = payload;
+ if (head[0] == tape.set_kind) return null;
+ }
+}
+
fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void {
for (p.panes, out) |slot, *d| {
d.* = 0;
@@ -838,6 +1005,647 @@ fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void {
}
}
+// ---- over a socket (docs/next-daemon.md, "Phase 5 part B notes") ----
+//
+// The session's half: each client handed over by the daemon (daemon.zig) is
+// a Peer, with a view of its own, a thread reading its inputs and one
+// writing what it is sent. The recorder is on while any is. At each step
+// boundary of the session's loop (`Peers.boundary`, after a pump):
+// - the pump's unit goes to every client;
+// - a client that came is joined: its view opened, the session dumped
+// (src/dump.zig) and sent ahead of every unit after;
+// - each input that came is a unit of its own: its view, the input, a
+// `step` (what the client's own core applied at once);
+// - a client gone takes its view with it.
+// A client's link only ever holds bytes queued for it: the session's step
+// never waits on one. One that lets `lag_max` pile up is cut off.
+
+const libc = std.c;
+const log = std.log.scoped(.replica);
+const nosignal: u32 = if (builtin.os.tag == .linux) libc.MSG.NOSIGNAL else 0;
+/// What a client may leave unread, past its join's dump, before it is cut
+/// off: minutes of typing, a screenful of a flood's deltas many times over.
+/// PARDES_REPLICA_LAG_KB says another (a test's).
+var lag_max: usize = 64 << 20;
+const dump_piece = 1 << 20;
+
+const Tm = extern struct { sec: c_int, min: c_int, hour: c_int, mday: c_int, mon: c_int, year: c_int, wday: c_int, yday: c_int, isdst: c_int, gmtoff: c_long, zone: ?[*:0]const u8 };
+extern "c" fn localtime_r(t: *const libc.time_t, tm: *Tm) ?*Tm;
+
+/// This zone's offset from UTC now, seconds.
+fn gmtoff() i32 {
+ var ts: libc.timespec = undefined;
+ _ = libc.clock_gettime(.REALTIME, &ts);
+ const secs: libc.time_t = ts.sec;
+ var tm: Tm = undefined;
+ return if (localtime_r(&secs, &tm) != null) @intCast(tm.gmtoff) else 0;
+}
+
+fn writeAll(fd: c_int, bytes: []const u8) bool {
+ var at: usize = 0;
+ while (at < bytes.len) {
+ const n = libc.send(fd, bytes[at..].ptr, bytes.len - at, nosignal);
+ if (n < 0 and libc.errno(n) == .INTR) continue;
+ if (n <= 0) return false;
+ at += @intCast(n);
+ }
+ return true;
+}
+
+fn readSome(fd: c_int, buf: []u8) usize {
+ while (true) {
+ const n = libc.read(fd, buf.ptr, buf.len);
+ if (n < 0 and libc.errno(n) == .INTR) continue;
+ return if (n <= 0) 0 else @intCast(n);
+ }
+}
+
+/// What a stream's reader holds of it, read and not yet taken: a dump's
+/// reader leaves the units read with its last piece to the stream's.
+pub const Framer = struct {
+ buf: std.ArrayListUnmanaged(u8) = .empty,
+ len: usize = 0,
+
+ pub fn deinit(f: *Framer, gpa: Allocator) void {
+ f.buf.deinit(gpa);
+ }
+
+ /// Framed messages off `fd` (detached/wire.zig) handed to `take` until
+ /// the stream ends, `take` says stop, or a message is malformed.
+ fn run(fr: *Framer, gpa: Allocator, fd: c_int, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void {
+ while (true) {
+ var at: usize = 0;
+ var stop = false;
+ while (!stop) {
+ const f = (wire.framed(fr.buf.items[at..fr.len]) catch break) orelse break;
+ at += f.total;
+ stop = !take(ctx, f.tag, f.payload);
+ }
+ if (at > 0) {
+ std.mem.copyForwards(u8, fr.buf.items[0 .. fr.len - at], fr.buf.items[at..fr.len]);
+ fr.len -= at;
+ }
+ if (stop) return;
+ if (wire.framed(fr.buf.items[0..fr.len])) |_| {} else |_| return;
+ // Room for what the head says is coming, or 64 KiB more.
+ const want = if (fr.len >= wire.header_len) wire.header_len + @as(usize, std.mem.readInt(u32, fr.buf.items[1..5], .little)) else 0;
+ const room = @max(want, fr.len + (64 << 10));
+ if (fr.buf.items.len < room) fr.buf.resize(gpa, room) catch return;
+ const n = readSome(fd, fr.buf.items[fr.len..]);
+ if (n == 0) return;
+ fr.len += n;
+ }
+ }
+};
+
+fn readFramed(gpa: Allocator, fd: c_int, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void {
+ var fr: Framer = .{};
+ defer fr.deinit(gpa);
+ fr.run(gpa, fd, ctx, take);
+}
+
+pub const Peer = struct {
+ peers: *Peers,
+ fd: c_int,
+ id: u16,
+ view: u8,
+ /// Inputs read (each one's seq, as the client numbered them).
+ seq: u32 = 0,
+ reader: ?std.Thread = null,
+ writer: ?std.Thread = null,
+ lock: std.Io.Mutex = .init,
+ cond: std.Io.Condition = .init,
+ /// What it is sent, not written yet, and what the writer writes now.
+ out: std.ArrayListUnmanaged(u8) = .empty,
+ sending: std.ArrayListUnmanaged(u8) = .empty,
+ limit: usize = 64 << 20,
+ closing: bool = false,
+ cut: bool = false,
+
+ /// `parts` queued for it, in order; never waits. A client whose queue
+ /// passes its limit is cut off: its link is shut down, and its reader
+ /// says it is gone.
+ fn send(peer: *Peer, parts: []const []const u8) void {
+ const io = peer.peers.io;
+ peer.lock.lockUncancelable(io);
+ defer peer.lock.unlock(io);
+ if (peer.cut or peer.closing) return;
+ var n: usize = peer.out.items.len;
+ for (parts) |p| n += p.len;
+ if (n > peer.limit) {
+ log.info("client {d} is {d} MB behind: cut off", .{ peer.id, n >> 20 });
+ peer.peers.cut += 1;
+ peer.cut = true;
+ _ = libc.shutdown(peer.fd, 2);
+ peer.cond.signal(io);
+ return;
+ }
+ for (parts) |p| peer.out.appendSlice(peer.peers.gpa, p) catch {
+ peer.cut = true;
+ _ = libc.shutdown(peer.fd, 2);
+ break;
+ };
+ peer.cond.signal(io);
+ }
+
+ fn writeLoop(peer: *Peer) void {
+ const io = peer.peers.io;
+ while (true) {
+ peer.lock.lockUncancelable(io);
+ while (peer.out.items.len == 0 and !peer.closing and !peer.cut) peer.cond.waitUncancelable(io, &peer.lock);
+ if (peer.out.items.len == 0 or peer.cut) {
+ peer.lock.unlock(io);
+ return;
+ }
+ std.mem.swap(std.ArrayListUnmanaged(u8), &peer.out, &peer.sending);
+ // The limit was for the dump and what is queued behind it.
+ peer.limit = lag_max;
+ peer.lock.unlock(io);
+ const ok = writeAll(peer.fd, peer.sending.items);
+ peer.sending.clearRetainingCapacity();
+ if (!ok) {
+ _ = libc.shutdown(peer.fd, 2);
+ return;
+ }
+ }
+ }
+
+ fn take(peer: *Peer, tag: u8, payload: []const u8) bool {
+ const t = std.enums.fromInt(wire.ClientTag, tag) orelse return false;
+ switch (t) {
+ .hello, .bye => return false,
+ .ping => {
+ var out: [16]u8 = undefined;
+ const v = (wire.decodeClient(tag, payload) catch return false).ping;
+ const pong = wire.encodeServer(&out, .{ .pong = v }) catch return false;
+ peer.send(&.{pong});
+ return true;
+ },
+ // ponytail: rterm's acks (src/screen_state.zig) go to its
+ // session state once terminals cross as screens.
+ .screen_ack => return true,
+ .check => {
+ peer.peers.post(.{ .check = peer });
+ return true;
+ },
+ else => {},
+ }
+ peer.seq += 1;
+ const msg = peer.peers.gpa.alloc(u8, head_len + wire.header_len + payload.len) catch return false;
+ header(msg, peer.id, peer.seq);
+ msg[head_len] = tag;
+ std.mem.writeInt(u32, msg[head_len + 1 ..][0..4], @intCast(payload.len), .little);
+ @memcpy(msg[head_len + wire.header_len ..], payload);
+ if (parseInput(msg) == null) {
+ peer.peers.gpa.free(msg);
+ return false;
+ }
+ peer.peers.post(.{ .input = .{ .peer = peer, .msg = msg } });
+ return true;
+ }
+
+ fn readLoop(peer: *Peer) void {
+ readFramed(peer.peers.gpa, peer.fd, peer, take);
+ peer.peers.post(.{ .gone = peer });
+ }
+};
+
+pub const Peers = struct {
+ gpa: Allocator = std.heap.c_allocator,
+ io: std.Io = undefined,
+ /// This session's name and pid, for a welcome.
+ name: []const u8 = "",
+ t: tape.Tape = undefined,
+ recording: bool = false,
+ list: [pardes.views.max]?*Peer = @splat(null),
+ next_id: u16 = 1,
+ seq: u32 = 0,
+ lock: std.Io.Mutex = .init,
+ inbox: std.ArrayListUnmanaged(Note) = .empty,
+ taken: std.ArrayListUnmanaged(Note) = .empty,
+ /// A reader posted: the loop's one test a step while nothing is attached.
+ mail: std.atomic.Value(bool) = .init(false),
+ /// Wakes the session's loop (its wait for input) from a reader.
+ wake_ctx: ?*anyopaque = null,
+ wake: ?*const fn (?*anyopaque) void = null,
+ /// What the session would be with no client: unattended without a
+ /// terminal of its own (the host says).
+ alone_unattended: bool = false,
+ /// The worst a join cost the session's step, and the last one's dump.
+ join_ns: u64 = 0,
+ dump_bytes: usize = 0,
+ /// What each client input cost the session (its step, its unit sent),
+ /// and each boundary (its pump's unit sent, what came taken in), ns:
+ /// PARDES_REPLICA_STATS writes them at the session's end.
+ input_ns: std.ArrayListUnmanaged(u64) = .empty,
+ boundary_ns: std.ArrayListUnmanaged(u64) = .empty,
+ cut: u32 = 0,
+ head: [unit_head]u8 = undefined,
+
+ pub const Note = union(enum) { join: c_int, input: struct { peer: *Peer, msg: []u8 }, gone: *Peer, check: *Peer };
+
+ pub fn count(ps: *const Peers) usize {
+ var n: usize = 0;
+ for (ps.list) |slot| n += @intFromBool(slot != null);
+ return n;
+ }
+
+ fn post(ps: *Peers, note: Note) void {
+ ps.lock.lockUncancelable(ps.io);
+ ps.inbox.append(ps.gpa, note) catch {
+ ps.lock.unlock(ps.io);
+ switch (note) {
+ .join => |fd| _ = libc.close(fd),
+ .input => |in| ps.gpa.free(in.msg),
+ .gone, .check => {},
+ }
+ return;
+ };
+ ps.mail.store(true, .release);
+ ps.lock.unlock(ps.io);
+ if (ps.wake) |w| w(ps.wake_ctx);
+ }
+
+ /// A replica's connection the daemon handed over (its hello taken
+ /// there): joined at the next step boundary. Any thread.
+ pub fn handed(ps: *Peers, fd: c_int) void {
+ ps.post(.{ .join = fd });
+ }
+
+ /// What was recorded since the last unit, to every client as one, its
+ /// digest at its end.
+ fn unit(ps: *Peers, origin: u16, seq: u32) void {
+ if (tape.taken(&ps.t).len == 0) return;
+ tape.recordDigest(&ps.t);
+ const bytes = tape.taken(&ps.t);
+ unitHeader(&ps.head, origin, seq);
+ if (std.c.getenv("PARDES_REPLICA_TRACE") != null) {
+ var w: std.Io.Writer.Allocating = .init(ps.gpa);
+ defer w.deinit();
+ w.writer.print("session: unit {d}/{d}, {d} bytes, to {d} clients:\n", .{ origin, seq, bytes.len, ps.count() }) catch {};
+ tape.describe(bytes, &w.writer);
+ std.debug.print("{s}", .{w.written()});
+ }
+ const head = wire.header(@backingInt(wire.ServerTag.unit), unit_head + bytes.len);
+ for (ps.list) |slot| if (slot) |peer| peer.send(&.{ &head, &ps.head, bytes });
+ tape.clearTaken(&ps.t);
+ }
+
+ /// After each of the session's pumps: its unit sent, the clients that
+ /// came joined, their inputs taken in, the ones gone let go.
+ pub fn boundary(ps: *Peers, core: *Pardes) void {
+ if (!ps.recording and !ps.mail.load(.acquire)) return;
+ const t0 = nowNs();
+ defer if (ps.recording) ps.boundary_ns.append(ps.gpa, nowNs() - t0) catch {};
+ if (ps.recording) {
+ ps.seq += 1;
+ ps.unit(0, ps.seq);
+ }
+ if (!ps.mail.load(.acquire)) return;
+ ps.lock.lockUncancelable(ps.io);
+ std.mem.swap(std.ArrayListUnmanaged(Note), &ps.inbox, &ps.taken);
+ ps.mail.store(false, .release);
+ ps.lock.unlock(ps.io);
+ for (ps.taken.items) |note| switch (note) {
+ .join => |fd| ps.join(core, fd),
+ .input => |in| {
+ ps.input(core, in.peer, in.msg);
+ ps.gpa.free(in.msg);
+ },
+ .gone => |peer| ps.leave(core, peer),
+ .check => |peer| {
+ var out: [16]u8 = undefined;
+ peer.send(&.{wire.encodeServer(&out, .{ .check = tape.digestOf(core) }) catch unreachable});
+ },
+ };
+ ps.taken.clearRetainingCapacity();
+ }
+
+ fn input(ps: *Peers, core: *Pardes, peer: *Peer, msg: []const u8) void {
+ const in = parseInput(msg) orelse return;
+ const t0 = nowNs();
+ defer ps.input_ns.append(ps.gpa, nowNs() - t0) catch {};
+ core.toView(peer.view);
+ core.update(in.event);
+ core.step();
+ ps.unit(peer.id, in.seq);
+ }
+
+ fn refuse(fd: c_int, why: []const u8) void {
+ var out: [600]u8 = undefined;
+ if (wire.encodeServer(&out, .{ .refused = why })) |bytes| _ = writeAll(fd, bytes) else |_| {}
+ _ = libc.close(fd);
+ }
+
+ fn join(ps: *Peers, core: *Pardes, fd: c_int) void {
+ const t0 = nowNs();
+ defer ps.join_ns = @max(ps.join_ns, nowNs() - t0);
+ const slot = for (&ps.list) |*s| {
+ if (s.* == null) break s;
+ } else return refuse(fd, "that session has as many clients as it takes");
+ if (!ps.recording) {
+ // A session recording to a file (PARDES_RECORD) has its tape.
+ if (tape.on != null) return refuse(fd, "that session records a tape of its own (PARDES_RECORD)");
+ ps.t = tape.memory(ps.gpa);
+ ps.t.unit_digests = true;
+ tape.on = &ps.t;
+ ps.recording = true;
+ }
+ // Someone looks at it now: its messages go by keys, not the clock.
+ core.unattended = false;
+ const k = core.openView() orelse {
+ core.unattended = ps.count() == 0 and ps.alone_unattended;
+ if (ps.count() == 0) ps.stop(core);
+ return refuse(fd, "that session has as many views as it takes");
+ };
+ // Its own process draws it.
+ core.undrawn |= @as(u8, 1) << @intCast(k);
+ ps.seq += 1;
+ ps.unit(0, ps.seq);
+ const bytes = pardes.dump.dumpBytes(core) catch |err| {
+ core.undrawn &= ~(@as(u8, 1) << @intCast(k));
+ core.closeView(k);
+ ps.unit(0, ps.seq);
+ if (ps.count() == 0) ps.stop(core);
+ var why: [96]u8 = undefined;
+ return refuse(fd, std.fmt.bufPrint(&why, "that session could not be dumped: {t}", .{err}) catch "that session could not be dumped");
+ };
+ // The core's, as a Dump's is.
+ defer core.gpa.free(bytes);
+ ps.dump_bytes = bytes.len;
+ // The joiner's core is the dump's: the host this tape wraps, and
+ // what the host wrote in the core, are said again at the next input.
+ tape.resync(&ps.t);
+ const peer = ps.gpa.create(Peer) catch return refuse(fd, "out of memory");
+ if (std.c.getenv("PARDES_REPLICA_LAG_KB")) |kb| lag_max = (std.fmt.parseInt(usize, std.mem.span(kb), 10) catch 64 << 10) << 10;
+ peer.* = .{ .peers = ps, .fd = fd, .id = ps.next_id, .view = k, .limit = bytes.len + lag_max };
+ ps.next_id +%= 1;
+ if (ps.next_id == 0) ps.next_id = 1;
+ var out: [wire.hello_max + 64]u8 = undefined;
+ // The session's digest as dumped, for the joiner to check its load by.
+ const digest = tape.digestOf(core);
+ const welcome = wire.encodeServer(&out, .{ .welcome = .{ .pid = @intCast(libc.getpid()), .session = ps.name[0..@min(ps.name.len, wire.max_name)], .client = peer.id, .view = k, .dump_len = bytes.len, .gmtoff = gmtoff(), .digest = digest } }) catch unreachable;
+ peer.send(&.{welcome});
+ var at: usize = 0;
+ while (at < bytes.len) : (at += dump_piece) {
+ const piece = bytes[at..@min(bytes.len, at + dump_piece)];
+ const head = wire.header(@backingInt(wire.ServerTag.dump), piece.len);
+ peer.send(&.{ &head, piece });
+ }
+ peer.writer = std.Thread.spawn(.{}, Peer.writeLoop, .{peer}) catch null;
+ peer.reader = std.Thread.spawn(.{}, Peer.readLoop, .{peer}) catch null;
+ if (peer.writer == null or peer.reader == null) {
+ ps.letGo(peer);
+ core.undrawn &= ~(@as(u8, 1) << @intCast(k));
+ core.closeView(k);
+ ps.unit(0, ps.seq);
+ return;
+ }
+ slot.* = peer;
+ log.info("client {d} joined '{s}' as view {d}: a {d} KB dump in {d} us", .{ peer.id, ps.name, k, bytes.len >> 10, (nowNs() - t0) / 1000 });
+ if (std.c.getenv("PARDES_REPLICA_TRACE") != null) std.debug.print("session: client {d} joined after unit {d}\n", .{ peer.id, ps.seq });
+ }
+
+ fn leave(ps: *Peers, core: *Pardes, peer: *Peer) void {
+ for (&ps.list) |*slot| if (slot.* == peer) {
+ slot.* = null;
+ };
+ log.info("client {d} left '{s}'", .{ peer.id, ps.name });
+ core.undrawn &= ~(@as(u8, 1) << @intCast(peer.view));
+ core.closeView(peer.view);
+ if (ps.count() == 0) core.unattended = ps.alone_unattended;
+ ps.seq += 1;
+ ps.unit(0, ps.seq);
+ ps.letGo(peer);
+ if (ps.count() == 0) ps.stop(core);
+ }
+
+ /// Its threads ended and joined, its link closed.
+ fn letGo(ps: *Peers, peer: *Peer) void {
+ const io = ps.io;
+ peer.lock.lockUncancelable(io);
+ peer.closing = true;
+ peer.cond.signal(io);
+ peer.lock.unlock(io);
+ _ = libc.shutdown(peer.fd, 2);
+ if (peer.writer) |w| w.join();
+ if (peer.reader) |r| r.join();
+ _ = libc.close(peer.fd);
+ peer.out.deinit(ps.gpa);
+ peer.sending.deinit(ps.gpa);
+ // What its reader posted after it was let go (its end) is nobody's.
+ ps.lock.lockUncancelable(io);
+ var i: usize = 0;
+ while (i < ps.inbox.items.len) {
+ const mine = switch (ps.inbox.items[i]) {
+ .input => |in| in.peer == peer,
+ .gone, .check => |p| p == peer,
+ .join => false,
+ };
+ if (!mine) {
+ i += 1;
+ continue;
+ }
+ if (ps.inbox.items[i] == .input) ps.gpa.free(ps.inbox.items[i].input.msg);
+ _ = ps.inbox.orderedRemove(i);
+ }
+ ps.lock.unlock(io);
+ ps.gpa.destroy(peer);
+ }
+
+ /// Detach typed in client view `k`'s: its link ends (its reader says
+ /// it is gone, and the next boundary lets it go).
+ pub fn detach(ps: *Peers, k: u8) bool {
+ for (ps.list) |slot| if (slot) |peer| if (peer.view == k) {
+ _ = libc.shutdown(peer.fd, 2);
+ return true;
+ };
+ return false;
+ }
+
+ fn stop(ps: *Peers, core: *Pardes) void {
+ if (!ps.recording) return;
+ if (core.host.vtable == &ps.t.vtable) core.host = ps.t.real;
+ tape.on = null;
+ tape.release(&ps.t);
+ ps.recording = false;
+ }
+
+ /// Every client let go (the session's end, a Restore): each sees its
+ /// link end.
+ pub fn dropAll(ps: *Peers, core: *Pardes) void {
+ for (&ps.list) |*slot| if (slot.*) |peer| {
+ slot.* = null;
+ core.undrawn &= ~(@as(u8, 1) << @intCast(peer.view));
+ core.closeView(peer.view);
+ ps.letGo(peer);
+ };
+ ps.stop(core);
+ ps.lock.lockUncancelable(ps.io);
+ for (ps.inbox.items) |note| switch (note) {
+ .join => |fd| _ = libc.close(fd),
+ .input => |in| ps.gpa.free(in.msg),
+ .gone, .check => {},
+ };
+ ps.inbox.clearRetainingCapacity();
+ ps.lock.unlock(ps.io);
+ core.unattended = ps.alone_unattended;
+ }
+
+ pub fn deinit(ps: *Peers) void {
+ if (std.c.getenv("PARDES_REPLICA_STATS")) |path| if (ps.input_ns.items.len > 0) ps.writeStats(std.mem.span(path));
+ ps.inbox.deinit(ps.gpa);
+ ps.taken.deinit(ps.gpa);
+ ps.input_ns.deinit(ps.gpa);
+ ps.boundary_ns.deinit(ps.gpa);
+ }
+
+ fn writeStats(ps: *Peers, path: []const u8) void {
+ var buf: [400]u8 = undefined;
+ const line = std.fmt.bufPrint(&buf, "session inputs {d} input_us {d}/{d}/{d} boundaries {d} boundary_us {d}/{d}/{d} join_us {d} dump_kb {d} cut {d}\n", .{
+ ps.input_ns.items.len, pctOf(ps.input_ns.items, 50) / 1000, pctOf(ps.input_ns.items, 99) / 1000, pctOf(ps.input_ns.items, 100) / 1000,
+ ps.boundary_ns.items.len, pctOf(ps.boundary_ns.items, 50) / 1000, pctOf(ps.boundary_ns.items, 99) / 1000, pctOf(ps.boundary_ns.items, 100) / 1000,
+ ps.join_ns / 1000, ps.dump_bytes >> 10, ps.cut,
+ }) catch return;
+ var z: [4096]u8 = undefined;
+ const pz = std.fmt.bufPrintSentinel(&z, "{s}", .{path}, 0) catch return;
+ const fd = libc.open(pz, .{ .ACCMODE = .WRONLY, .CREAT = true, .APPEND = true, .CLOEXEC = true }, @as(libc.mode_t, 0o644));
+ if (fd < 0) return;
+ _ = libc.write(fd, line.ptr, line.len);
+ _ = libc.close(fd);
+ }
+};
+
+// ---- the client's half ----
+
+pub const Joined = struct {
+ fd: c_int,
+ pid: u32,
+ client: u16,
+ view: u8,
+ gmtoff: i32,
+ dump: []u8,
+ /// The session's digest as dumped (`Replica.loaded`).
+ digest: u64 = 0,
+ /// What was read past the dump: the stream's (`readStream`).
+ rest: Framer = .{},
+};
+
+/// Connected to the replica socket at `path`, its hello said for
+/// `session`, welcomed, and the dump read whole: what a client joins with.
+/// Errors are said in `why`.
+pub fn dial(gpa: Allocator, path: []const u8, session: []const u8, why: []u8) ?Joined {
+ const fd = libc.socket(libc.AF.UNIX, libc.SOCK.STREAM | libc.SOCK.CLOEXEC, 0);
+ if (fd < 0) return said(why, "no socket", .{});
+ var addr: libc.sockaddr.un = .{ .path = @splat(0) };
+ if (path.len >= addr.path.len) {
+ _ = libc.close(fd);
+ return said(why, "the socket's path is too long: {s}", .{path});
+ }
+ @memcpy(addr.path[0..path.len], path);
+ if (libc.connect(fd, @ptrCast(&addr), @sizeOf(libc.sockaddr.un)) != 0) {
+ _ = libc.close(fd);
+ return said(why, "nothing answers at {s}", .{path});
+ }
+ var out: [wire.hello_max]u8 = undefined;
+ const hello = wire.encodeClient(&out, .{ .hello = .{ .session = session } }) catch {
+ _ = libc.close(fd);
+ return said(why, "that session's name is too long", .{});
+ };
+ var j: Joined = .{ .fd = fd, .pid = 0, .client = 0, .view = 0, .gmtoff = 0, .dump = &.{} };
+ const Read = struct {
+ j: *Joined,
+ gpa: Allocator,
+ why: []u8,
+ got: usize = 0,
+ failed: ?[]const u8 = null,
+ welcomed: bool = false,
+ fn take(r: *@This(), tag: u8, payload: []const u8) bool {
+ const msg = wire.decodeServer(tag, payload) catch {
+ r.failed = "the session's answer was not understood";
+ return false;
+ };
+ switch (msg) {
+ .welcome => |w| {
+ r.j.pid = w.pid;
+ r.j.client = w.client;
+ r.j.view = w.view;
+ r.j.gmtoff = w.gmtoff;
+ r.j.digest = w.digest;
+ r.j.dump = r.gpa.alloc(u8, @intCast(w.dump_len)) catch {
+ r.failed = "out of memory for the session's dump";
+ return false;
+ };
+ r.welcomed = true;
+ return w.dump_len > 0;
+ },
+ .refused => |words| {
+ r.failed = std.fmt.bufPrint(r.why, "{s}\x00", .{words}) catch "refused";
+ return false;
+ },
+ .dump => |piece| {
+ if (!r.welcomed or r.got + piece.len > r.j.dump.len) {
+ r.failed = "the session sent more dump than it said";
+ return false;
+ }
+ @memcpy(r.j.dump[r.got..][0..piece.len], piece);
+ r.got += piece.len;
+ return r.got < r.j.dump.len;
+ },
+ else => {
+ r.failed = "the session sent a unit before its dump";
+ return false;
+ },
+ }
+ }
+ };
+ if (!writeAll(fd, hello)) {
+ _ = libc.close(fd);
+ return said(why, "the session hung up", .{});
+ }
+ var r: Read = .{ .j = &j, .gpa = gpa, .why = why };
+ j.rest.run(gpa, fd, &r, Read.take);
+ if (r.failed != null or !r.welcomed or r.got < j.dump.len) {
+ j.rest.deinit(gpa);
+ if (j.dump.len > 0) gpa.free(j.dump);
+ _ = libc.close(fd);
+ const text = r.failed orelse "the session hung up before the dump was whole";
+ if (text.ptr == why.ptr) return null;
+ return said(why, "{s}", .{text});
+ }
+ return j;
+}
+
+fn said(why: []u8, comptime fmt: []const u8, args: anytype) ?Joined {
+ _ = std.fmt.bufPrint(why, fmt ++ "\x00", args) catch {};
+ return null;
+}
+
+/// A message `Replica.input` made, to the session: the event's frame (its
+/// client and seq are the connection's).
+pub fn sendInput(fd: c_int, msg: []const u8) bool {
+ return writeAll(fd, msg[head_len..]);
+}
+
+/// Asks the session's digest, answered in stream order.
+pub fn askCheck(fd: c_int) bool {
+ var out: [16]u8 = undefined;
+ return writeAll(fd, wire.encodeClient(&out, .check) catch unreachable);
+}
+
+/// The client's last word.
+pub fn bye(fd: c_int) void {
+ var out: [16]u8 = undefined;
+ if (wire.encodeClient(&out, .bye)) |b| _ = writeAll(fd, b) else |_| {}
+}
+
+/// What follows the dump on the client's connection, each message handed
+/// to `take` (a unit, a terminal's delta) until the link ends; `rest` is
+/// what the dump's reader read past it.
+pub fn readStream(gpa: Allocator, fd: c_int, rest: *Framer, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void {
+ rest.run(gpa, fd, ctx, take);
+}
+
pub fn digestOf(a: *Authority) u64 {
const was = Stepping.begin(&a.t, null);
defer was.end();
@@ -1078,3 +1886,36 @@ test "the authority's units with a big file open: its blobs hashed once (PARDES_
std.debug.print("{d} MB file, blobs {s}: a unit p50 {d} us p99 {d} us; a digest p50 {d} us p99 {d} us\n", .{ mb, if (on) "hashed once" else "hashed whole", us[0] / 1000, us[1] / 1000, ds[0] / 1000, ds[1] / 1000 });
}
}
+
+test "a replica joined from the session's dump replays the units after it" {
+ const gpa = std.testing.allocator;
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false);
+ defer a.deinit();
+ _ = try a.local(.{ .key = .{ .cp = 'j', .text = "j" } });
+ const was = Stepping.begin(&a.t, null);
+ const bytes = try pardes.dump.dumpBytes(a.core);
+ tape.resync(&a.t);
+ was.end();
+ defer a.core.gpa.free(bytes);
+ const r = try Replica.initDump(gpa, 1, 0, bytes, .{ .cols = 80, .rows = 24 });
+ defer r.deinit();
+ try std.testing.expectEqual(digestOf(a), r.digest());
+ r.confirm(try a.local(.{ .key = .{ .cp = 'j', .text = "j" } }));
+ if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why});
+ try std.testing.expect(r.diverged == null);
+ var sent: std.ArrayListUnmanaged([]u8) = .empty;
+ defer {
+ for (sent.items) |m| gpa.free(m);
+ sent.deinit(gpa);
+ }
+ for ("oab") |k| try key(r, k, &sent);
+ try key(r, pardes.Key.escape, &sent);
+ for (sent.items) |m| {
+ r.confirm(try a.take(m));
+ r.settle();
+ }
+ if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why});
+ try std.testing.expect(r.diverged == null);
+ try std.testing.expect(r.quiet());
+ try std.testing.expectEqual(digestOf(a), r.digest());
+}