diff options
Diffstat (limited to 'src/replica.zig')
| -rw-r--r-- | src/replica.zig | 116 |
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); |
