diff options
| -rw-r--r-- | src/detached/wire.zig | 15 | ||||
| -rw-r--r-- | src/replica.zig | 116 | ||||
| -rw-r--r-- | src/tape.zig | 7 | ||||
| -rw-r--r-- | test/daemon.py | 2 |
4 files changed, 119 insertions, 21 deletions
diff --git a/src/detached/wire.zig b/src/detached/wire.zig index a809bebd..6090dedb 100644 --- a/src/detached/wire.zig +++ b/src/detached/wire.zig @@ -9,6 +9,8 @@ const builtin = @import("builtin"); const pardes = @import("../pardes.zig"); const config = @import("pardes_config"); +/// 18: a replica's input is stamped with its guess of the session's +/// clocks, the time its step reads (phase 6's instant interaction notes); /// 17: a pointer's hit carries the place it was made on (Layer.Place) and /// a tag hit its line, which the step resolves it by, not by its frame; /// 16: a far client says so, the session sends it its blobs' hashes before @@ -20,7 +22,7 @@ const config = @import("pardes_config"); /// part B); 14: the hello names a session and /// carries the semantics hash, and a ping is answered (phase 5's /// groundwork); 13: the frames went (phase 3). -pub const version: u16 = 17; +pub const version: u16 = 18; /// The terminal's build and the window's step alike (`semantics`). const family = switch (config.platform) { @@ -85,6 +87,10 @@ pub const ClientTag = enum(u8) { far = 0x06, /// The join's blobs a far client lacks, a bit each in `blobs` order. want = 0x07, + /// The session's clocks (realtime and monotonic, ns) as the client + /// guessed them for the input that follows: its time, which the step + /// reads (src/replica.zig). + stamp = 0x08, key = 0x10, mouse = 0x11, @@ -269,6 +275,7 @@ pub const ClientMsg = union(enum) { check, far: bool, want: []const u8, + stamp: [2]i64, event: pardes.Event, }; @@ -497,6 +504,7 @@ pub fn encodeClient(out: []u8, msg: ClientMsg) Error![]const u8 { .screen_ack, .want => |bytes| try w.writeAll(bytes), .check => {}, .far => |far| try w.writeByte(@intFromBool(far)), + .stamp => |s| for (s) |v| try w.writeInt(i64, v, .little), .event => |ev| switch (ev) { .key => |k| { try w.writeInt(u32, k.cp, .little); @@ -572,6 +580,7 @@ pub fn decodeClient(tag: u8, payload: []const u8) Error!ClientMsg { .check => .check, .far => .{ .far = try getBool(&r) }, .want => return .{ .want = payload }, + .stamp => .{ .stamp = .{ try r.takeInt(i64, .little), try r.takeInt(i64, .little) } }, .key => blk: { const cp = try r.takeInt(u32, .little); // `Key.cp` is a u21, and the specials live in the private-use @@ -633,7 +642,7 @@ const msg_slack = header_len + 64; pub fn clientBound(msg: ClientMsg) usize { return msg_slack + switch (msg) { .hello => |h| h.session.len, - .bye, .ping, .check, .far => 0, + .bye, .ping, .check, .far, .stamp => 0, .screen_ack, .want => |bytes| bytes.len, .event => |ev| switch (ev) { // Its hits' places (14 bytes each) past the slack. @@ -775,6 +784,8 @@ test "detached wire: a session is never told to do a frontend's remembering" { "hello", "bye", "ping", "screen_ack", "check", // ...and how far it is, and which of the join's blobs it lacks. "far", "want", + // ...and when its next input was, by the session's clocks. + "stamp", // ...and everything a person can do to a window. "key", "mouse", "resize", "paste", "command", "pdf_scroll", "pinch", "touch_scroll", 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); diff --git a/src/tape.zig b/src/tape.zig index 12f7fe3d..4759d598 100644 --- a/src/tape.zig +++ b/src/tape.zig @@ -257,6 +257,11 @@ pub const Tape = struct { /// (src/replica.zig): its clock reads (a message's stamp, a file's /// mtime) answer this instead of the clocks here. guess: ?Guess = null, + /// The same guess, as the client sent it with its input, while the + /// authority steps that input: the step's clock reads are the input's + /// time, so the guess a speculation recorded is what the authority + /// records (a message's millisecond, an edit's second never miss). + stamp: ?Guess = null, fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void { t.scratch.clearRetainingCapacity(); @@ -914,7 +919,7 @@ fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anyt t.poisoned_by = @tagName(s); return poisonOf(R); } - if (comptime s == .clock or s == .mtime) if (t.speculating) if (t.guess) |g| { + if (comptime s == .clock or s == .mtime) if (if (t.speculating) t.guess else t.stamp) |g| { const r = guessed(R, g); t.record(.host, u16, &id); t.record(.ret, R, &r); diff --git a/test/daemon.py b/test/daemon.py index b55c9b24..8633238f 100644 --- a/test/daemon.py +++ b/test/daemon.py @@ -208,7 +208,7 @@ class Replica: """A replica's connection (src/detached/wire.zig): length-prefixed messages, a tag byte and a little-endian u32 length. It is a near client: its first word after the hello says so.""" - WIRE = 17 + WIRE = 18 def __init__(self, path, timeout=10): self.s = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM) |
