summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/detached/wire.zig15
-rw-r--r--src/replica.zig116
-rw-r--r--src/tape.zig7
3 files changed, 118 insertions, 20 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);