summaryrefslogtreecommitdiff
path: root/src/replica.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-30 17:54:43 -0300
committerGabriel Schneider <[email protected]>2026-10-30 20:25:56 -0300
commit494aeadc46212766b3d7869a2ed8b811ac490ffa (patch)
treeb3a00bf03f741415c1dd39a5eb7ba4f070152d14 /src/replica.zig
parent58c230e73ab64e7b015a95462bde554c6b25df79 (diff)
downloadpardes-494aeadc46212766b3d7869a2ed8b811ac490ffa.tar.gz
pardes-494aeadc46212766b3d7869a2ed8b811ac490ffa.zip
replica: an input's time is its client's: it is sent stamped with the client's guess of the session's clocks (wire 18's `stamp`), the guess its speculation records, and the authority's step reads that, not its own clocks (within a second of them, else its own), so a step's clock read never mispredicts: an edit's second across a turn, a message's millisecond (Ctrl-W's, a jump's) were each a rollback (fixer 1: 4 seen in 2 minutes), and every reapply of one now reads the same time
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'src/replica.zig')
-rw-r--r--src/replica.zig116
1 files changed, 99 insertions, 17 deletions
diff --git a/src/replica.zig b/src/replica.zig
index b4c3de8c..e483693a 100644
--- a/src/replica.zig
+++ b/src/replica.zig
@@ -36,6 +36,8 @@ const Pardes = pardes.Pardes;
const checked = builtin.mode == .debug or builtin.mode == .safe;
const head_len = 6; // origin or client: u16le, seq: u32le
+/// A `stamp` frame (wire.zig): its header and the two clocks.
+const stamp_len = wire.header_len + 16;
/// Confirmed units fast-pathed under one copy before it is taken afresh:
/// a rollback replays them all.
const rebase_after = 32;
@@ -75,17 +77,36 @@ fn unitHeader(buf: []u8, origin: u16, seq: u32) void {
std.mem.writeInt(i64, buf[14..22], clockNs(.MONOTONIC), .little);
}
-pub const Input = struct { client: u16, seq: u32, event: pardes.Event };
+pub const Input = struct { client: u16, seq: u32, event: pardes.Event, stamp: ?[2]i64 = null };
-/// A client's input message; its event borrows `msg`.
+/// A client's input message: its head, a `stamp` frame (when its client
+/// guessed the session's clocks), and its event's frame, which the event
+/// borrows.
pub fn parseInput(msg: []const u8) ?Input {
if (msg.len < head_len) return null;
- const f = (wire.framed(msg[head_len..]) catch return null) orelse return null;
+ var rest = msg[head_len..];
+ var f = (wire.framed(rest) catch return null) orelse return null;
+ var stamp: ?[2]i64 = null;
+ if (f.tag == @backingInt(wire.ClientTag.stamp)) {
+ stamp = (wire.decodeClient(f.tag, f.payload) catch return null).stamp;
+ rest = rest[f.total..];
+ f = (wire.framed(rest) catch return null) orelse return null;
+ }
const ev = switch (wire.decodeClient(f.tag, f.payload) catch return null) {
.event => |ev| ev,
else => return null,
};
- return .{ .client = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .event = ev };
+ return .{ .client = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .event = ev, .stamp = stamp };
+}
+
+/// An input's stamp as the authority takes it: the client's guess of its
+/// clocks, so the guess its speculation recorded is the step's own; none
+/// from a client a second or more off (a stall, a bad round trip), whose
+/// step reads the clocks here.
+fn stampOf(in: Input) ?tape.Guess {
+ const s = in.stamp orelse return null;
+ if (@abs(s[0] - clockNs(.REALTIME)) >= std.time.ns_per_s or @abs(s[1] - clockNs(.MONOTONIC)) >= std.time.ns_per_s) return null;
+ return .{ .real_ns = s[0], .mono_ns = s[1], .gmtoff = gmtoff() };
}
/// The core whose tape is `t`, stepped: tape.on is process-wide, and so
@@ -252,8 +273,10 @@ pub const Authority = struct {
const in = parseInput(msg) orelse return error.BadInput;
const was = Stepping.begin(&a.t, null);
a.core.toView(a.view_of[in.client]);
+ a.t.stamp = stampOf(in);
a.core.update(in.event);
a.core.step();
+ a.t.stamp = null;
was.end();
return a.unit(in.client, in.seq);
}
@@ -516,7 +539,7 @@ pub const Stats = struct {
/// `terminal`: its speculation read a terminal or moved one's view (or a
/// terminal had the keyboard), so what it did depends on the emulator, and
/// `digest` is the state it ended on: the same records are not enough.
-const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0, terminal: bool = false, digest: u64 = 0 };
+const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0, terminal: bool = false, digest: u64 = 0, guess: ?tape.Guess = null };
/// A terminal's view as the authority's was once `after` of the units
/// since the copy were taken (`Replica.since`): a delta's comes after the
@@ -688,12 +711,20 @@ pub const Replica = struct {
r.stats.inputs += 1;
const seq = r.next_seq;
r.next_seq += 1;
- const room = try r.gpa.alloc(u8, head_len + wire.clientBound(.{ .event = ev }));
+ // Its time, as the session's clocks will read when it steps it (a
+ // round trip on from the last unit's, the clocks here in process):
+ // the step's clock reads, here and there (`stampOf`).
+ const g: tape.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 .{ .real_ns = clockNs(.REALTIME), .mono_ns = clockNs(.MONOTONIC), .gmtoff = gmtoff() };
+ const room = try r.gpa.alloc(u8, head_len + stamp_len + wire.clientBound(.{ .event = ev }));
defer r.gpa.free(room);
- const n = (try wire.encodeClient(room[head_len..], .{ .event = ev })).len;
+ _ = try wire.encodeClient(room[head_len..][0..stamp_len], .{ .stamp = .{ g.real_ns, g.mono_ns } });
+ const n = (try wire.encodeClient(room[head_len + stamp_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, .sent_ns = nowNs() });
+ const msg = try r.gpa.dupe(u8, room[0 .. head_len + stamp_len + n]);
+ try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg, .sent_ns = nowNs(), .guess = g });
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);
@@ -904,10 +935,8 @@ 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;
+ // The time it was sent with, every time it is applied.
+ r.t.guess = p.guess;
c.toView(r.view);
// Input into a terminal: what reaches its program (a key in tty
// mode, a paste, a mouse report) is a pty write, the authority's,
@@ -1411,6 +1440,9 @@ pub const Peer = struct {
sid: u16 = 0,
/// Inputs read (each one's seq, as the client numbered them).
seq: u32 = 0,
+ /// The `stamp` frame its next input came with (its reader's).
+ stamp: [stamp_len]u8 = undefined,
+ stamped: bool = false,
reader: ?std.Thread = null,
writer: ?std.Thread = null,
lock: std.Io.Mutex = .init,
@@ -1652,14 +1684,25 @@ pub const Peer = struct {
peer.cond.signal(io);
return true;
},
+ // Its next input's time, kept for it (this thread's alone).
+ .stamp => {
+ const s = (wire.decodeClient(tag, payload) catch return false).stamp;
+ _ = wire.encodeClient(&peer.stamp, .{ .stamp = s }) catch return false;
+ peer.stamped = true;
+ return true;
+ },
else => {},
}
peer.seq += 1;
- const msg = peer.peers.gpa.alloc(u8, head_len + wire.header_len + payload.len) catch return false;
+ const stamp: []const u8 = if (peer.stamped) &peer.stamp else &.{};
+ peer.stamped = false;
+ const msg = peer.peers.gpa.alloc(u8, head_len + stamp.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);
+ @memcpy(msg[head_len..][0..stamp.len], stamp);
+ const at = head_len + stamp.len;
+ msg[at] = tag;
+ std.mem.writeInt(u32, msg[at + 1 ..][0..4], @intCast(payload.len), .little);
+ @memcpy(msg[at + wire.header_len ..], payload);
if (parseInput(msg) == null) {
peer.peers.gpa.free(msg);
return false;
@@ -1843,8 +1886,10 @@ pub const Peers = struct {
// it read, its unit (part B terminal notes' order).
ps.screensOut(core, .flush);
core.toView(peer.view);
+ ps.t.stamp = stampOf(in);
core.update(in.event);
core.step();
+ ps.t.stamp = null;
ps.screensOut(core, .fill);
ps.unit(peer.id, in.seq);
}
@@ -3063,6 +3108,43 @@ test "a replica's own keys apply at once, confirm on the fast path, and end at t
try std.testing.expectEqual(digestOf(a), r.digest());
}
+test "an input's time is its client's: an edit's second confirms on the fast path though the authority takes it in the next" {
+ const gpa = std.testing.allocator;
+ const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false);
+ defer a.deinit();
+ const r = try Replica.init(gpa, 1, try a.unit(0, 0), false);
+ defer r.deinit();
+ var sent: std.ArrayListUnmanaged([]u8) = .empty;
+ defer {
+ for (sent.items) |m| gpa.free(m);
+ sent.deinit(gpa);
+ }
+ try key(r, 'o', &sent);
+ for (sent.items) |m| {
+ r.confirm(try a.take(m));
+ r.settle();
+ }
+ // Typed 30 ms before a second's turn, taken 30 ms after it: the edit's
+ // file time is the clock's second, read in the step.
+ while (true) {
+ var ts: std.c.timespec = undefined;
+ _ = std.c.clock_gettime(.REALTIME, &ts);
+ if (ts.nsec >= 970 * std.time.ns_per_ms) break;
+ const rest: std.c.timespec = .{ .sec = 0, .nsec = 970 * std.time.ns_per_ms - ts.nsec };
+ _ = std.c.nanosleep(&rest, null);
+ }
+ try key(r, 'x', &sent);
+ try std.testing.expectEqual(@as(usize, 1), r.applied);
+ const late: std.c.timespec = .{ .sec = 0, .nsec = 60 * std.time.ns_per_ms };
+ _ = std.c.nanosleep(&late, null);
+ r.confirm(try a.take(sent.items[1]));
+ r.settle();
+ try std.testing.expect(r.diverged == null and r.quiet());
+ try std.testing.expectEqual(@as(u32, 2), r.stats.fast);
+ try std.testing.expectEqual(@as(u32, 0), r.stats.mispredicted);
+ try std.testing.expectEqual(digestOf(a), r.digest());
+}
+
test "another client's input first: a replica rolls back, replays it and applies its own again" {
const gpa = std.testing.allocator;
const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false);