summaryrefslogtreecommitdiff
path: root/src/tape.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/tape.zig')
-rw-r--r--src/tape.zig236
1 files changed, 222 insertions, 14 deletions
diff --git a/src/tape.zig b/src/tape.zig
index ec38deac..70609858 100644
--- a/src/tape.zig
+++ b/src/tape.zig
@@ -127,19 +127,40 @@ pub const Tape = struct {
/// PARDES_RECORD_EVERY: a digest after every input, a nested one's too
/// (to find the step a divergence starts at), not only the host's last.
every: bool = false,
+ /// A replica applying its own input before the authority has ordered it
+ /// (src/replica.zig): recorded as the authority would record it, so the
+ /// two can be compared, but nothing is performed. A host call or a
+ /// syscall stops it (`poisoned`): what the call returns is the
+ /// authority's to say, and the input waits for it. A read of the clock
+ /// or the environment (`value`) is made here, a guess the comparison
+ /// checks.
+ speculating: bool = false,
+ poisoned: bool = false,
+ /// The allocator of the core a replay makes (a replica's rollback epoch,
+ /// src/rollback.zig), when it is not the tape's own.
+ core_gpa: ?std.mem.Allocator = null,
+ /// Where a replay keeps what a core keeps of an input (its options),
+ /// for a tape that is let go; else the tape's allocator, for good.
+ kept_arena: ?std.heap.ArenaAllocator = null,
+ /// No digests recorded (a speculation's: a replica compares what it
+ /// was given and what it asked, from a state the authority shares).
+ no_digest: bool = false,
fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void {
t.scratch.clearRetainingCapacity();
walk.encode(T, v, &t.scratch.writer) catch @panic("tape: out of memory");
const payload = t.scratch.written();
const len: u32 = @intCast(payload.len);
- t.buf.append(t.gpa, @intFromEnum(kind)) catch @panic("tape: out of memory");
+ t.buf.append(t.gpa, @backingInt(kind)) catch @panic("tape: out of memory");
t.buf.appendSlice(t.gpa, std.mem.asBytes(&len)) catch @panic("tape: out of memory");
t.buf.appendSlice(t.gpa, payload) catch @panic("tape: out of memory");
if (t.buf.items.len > 1 << 20) t.flush();
}
fn flush(t: *Tape) void {
+ // A tape in memory (a replica's, an authority's stream) is taken
+ // by whoever holds it.
+ if (t.fd < 0) return;
var at: usize = 0;
while (at < t.buf.items.len) {
const n = libc.write(t.fd, t.buf.items[at..].ptr, t.buf.items.len - at);
@@ -222,7 +243,7 @@ pub const Tape = struct {
t.wrap(core);
};
t.record(.done, void, &{});
- if (t.depth == 0 or t.every) if (t.core) |core| {
+ if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| {
var parts: Parts = undefined;
const d = digestParts(core, &parts);
t.record(.digest, []const u64, &d);
@@ -239,12 +260,12 @@ pub const Tape = struct {
const head = t.in.take(5) catch return null;
const len = std.mem.bytesToValue(u32, head[1..5]);
const payload = t.in.take(len) catch return null;
- return .{ .kind = @enumFromInt(head[0]), .payload = .{ .bytes = payload } };
+ return .{ .kind = @fromBackingInt(@intCast(head[0])), .payload = .{ .bytes = payload } };
}
fn peek(t: *const Tape) ?Kind {
if (t.in.bytes.len - t.in.at < 5) return null;
- return @enumFromInt(t.in.bytes[t.in.at]);
+ return @fromBackingInt(@intCast(t.in.bytes[t.in.at]));
}
fn diverge(t: *Tape, comptime why: []const u8, args: anytype) void {
@@ -374,7 +395,8 @@ pub const Tape = struct {
const tag = std.mem.bytesToValue(Tag, (r.take(@sizeOf(Tag)) catch return t.diverge("a short input", .{})));
r.at -= @sizeOf(Tag);
const kept = tag == .init or tag == .init_from_dump or tag == .restore;
- const input = walk.decode(Input, r, if (kept) t.gpa else t.arena.allocator()) catch return t.diverge("a short input", .{});
+ const keep = if (t.kept_arena) |*k| k.allocator() else t.gpa;
+ const input = walk.decode(Input, r, if (kept) keep else t.arena.allocator()) catch return t.diverge("a short input", .{});
const outer = t.applying;
t.applying = switch (input) {
.update => |ev| @tagName(ev),
@@ -390,13 +412,14 @@ pub const Tape = struct {
.init_from_dump => |d| d.opts,
else => unreachable,
};
- opts.image_allocator = t.gpa;
- opts.pdf_allocator = t.gpa;
- opts.tree_sitter_allocator = t.gpa;
- opts.frame_allocator = t.gpa;
+ const gpa = t.core_gpa orelse t.gpa;
+ opts.image_allocator = gpa;
+ opts.pdf_allocator = gpa;
+ opts.tree_sitter_allocator = gpa;
+ opts.frame_allocator = gpa;
t.core = switch (input) {
- .init => Pardes.init(t.gpa, opts),
- .init_from_dump => |d| pardes.dump.initFromDump(t.gpa, opts, d.bytes),
+ .init => Pardes.init(gpa, opts),
+ .init_from_dump => |d| pardes.dump.initFromDump(gpa, opts, d.bytes),
else => unreachable,
} catch |err| return t.diverge("init failed: {t}", .{err});
t.core.?.host = t.hostOf(t.mask);
@@ -608,8 +631,21 @@ fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype
}
return walk.decode(R, &ret, t.arena.allocator()) catch std.mem.zeroes(R);
}
- const real = @field(t.real.vtable.*, name).?;
const id: u16 = i;
+ if (t.speculating) {
+ // Nobody watches a replica's step: its frames are its own, drawn
+ // outside it (and the authority's host says so too, or the
+ // comparison fails).
+ if (comptime std.mem.eql(u8, name, "watched")) {
+ const r = false;
+ t.record(.host, u16, &id);
+ t.record(.ret, R, &r);
+ return r;
+ }
+ t.poisoned = true;
+ return poisonOf(R);
+ }
+ const real = @field(t.real.vtable.*, name).?;
t.record(.host, u16, &id);
t.seeFields();
const outer = !t.host_side;
@@ -639,7 +675,7 @@ pub fn value(comptime s: Site, comptime f: anytype, args: anytype) @typeInfo(@Ty
fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anytype, comptime yields: bool) @typeInfo(@TypeOf(f)).@"fn".return_type.? {
const R = @typeInfo(@TypeOf(f)).@"fn".return_type.?;
const t = on orelse return if (yields) out(f, args) else @call(.auto, f, args);
- const id: u16 = @as(u16, host_fns.len) + @intFromEnum(s);
+ const id: u16 = @as(u16, host_fns.len) + @backingInt(s);
if (t.replay) {
if (!t.expectHost(id, @tagName(s))) {
std.debug.print("replay: {s}\n", .{t.diverged orelse "?"});
@@ -651,6 +687,12 @@ fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anyt
// The host's own (a shell's spawn asking the shell), or one inside a
// site's syscall: the outer call is the record.
if (t.host_side) return if (yields) out(f, args) else @call(.auto, f, args);
+ // A syscall a speculating replica must not make: its input waits for
+ // the authority's answer.
+ if (yields and t.speculating) {
+ t.poisoned = true;
+ return poisonOf(R);
+ }
t.record(.host, u16, &id);
t.seeFields();
t.host_side = true;
@@ -679,7 +721,173 @@ fn out(comptime f: anytype, args: anytype) @typeInfo(@TypeOf(f)).@"fn".return_ty
/// Asked by `turn.yield`: a syscall a replica must never make.
pub fn replaying() bool {
- return if (on) |t| t.replay else false;
+ return if (on) |t| t.replay or t.speculating else false;
+}
+
+/// A replica speculating (src/replica.zig): state only the authority
+/// changes (a terminal's emulator) is left alone, and the input waits.
+pub fn speculating() bool {
+ return if (on) |t| t.speculating else false;
+}
+
+/// What a speculation reached is the authority's: the input is undone and
+/// waits for the authority's order.
+pub fn poison() void {
+ if (on) |t| if (t.speculating) {
+ t.poisoned = true;
+ };
+}
+
+/// A harmless stand-in for what a host call or a syscall would have
+/// returned to a speculation that is thrown away once it returns: an
+/// error where one can be said, else zeroes.
+fn poisonOf(comptime R: type) R {
+ return switch (@typeInfo(R)) {
+ .error_union => |e| if (@typeInfo(e.error_set).error_set.error_names) |errors|
+ (if (errors.len > 0) @field(e.error_set, errors[0]) else std.mem.zeroes(R))
+ else
+ error.Unexpected,
+ .optional => null,
+ .void => {},
+ .@"union" => |u| inline for (u.field_names, u.field_types) |name, F| {
+ if (comptime zeroable(F)) break @unionInit(R, name, std.mem.zeroes(F));
+ } else @compileError("tape: no harmless value of " ++ @typeName(R)),
+ else => std.mem.zeroes(R),
+ };
+}
+
+fn zeroable(comptime T: type) bool {
+ return switch (@typeInfo(T)) {
+ .int, .float, .bool, .optional, .void => true,
+ .pointer => |p| p.size == .slice,
+ .array => |a| zeroable(a.child),
+ .@"struct" => |s| blk: {
+ for (s.field_types) |F| if (!zeroable(F)) break :blk false;
+ break :blk true;
+ },
+ else => false,
+ };
+}
+
+// ---- a replica's tapes in memory (src/replica.zig) ----
+
+/// A tape recorded in memory: an authority's stream, taken unit by unit.
+pub fn memory(gpa: std.mem.Allocator) Tape {
+ return .{ .gpa = gpa, .replay = false, .scratch = .init(gpa), .arena = .init(gpa), .kept_arena = .init(gpa) };
+}
+
+/// What a tape in memory holds, given back (its core is gone already).
+pub fn release(t: *Tape) void {
+ t.buf.deinit(t.gpa);
+ t.scratch.deinit();
+ t.arena.deinit();
+ if (t.kept_arena) |*k| k.deinit();
+}
+
+/// What was recorded since the last take; the tape's to reuse after.
+pub fn taken(t: *Tape) []const u8 {
+ return t.buf.items;
+}
+
+pub fn clearTaken(t: *Tape) void {
+ t.buf.clearRetainingCapacity();
+}
+
+/// The records of `bytes`, top-level inputs and all, applied to the
+/// tape's core as the authority applied them, each digest checked; why
+/// they diverged, or null.
+pub fn replayUnit(t: *Tape, bytes: []const u8) ?[]const u8 {
+ t.replay = true;
+ t.speculating = false;
+ defer t.replay = false;
+ t.in = .{ .bytes = bytes };
+ while (t.diverged == null) {
+ const kind = t.peek() orelse break;
+ var rec = t.next().?;
+ switch (kind) {
+ .input => {
+ t.apply(&rec.payload);
+ _ = t.arena.reset(.retain_capacity);
+ },
+ .set => t.applySet(&rec.payload),
+ .digest => t.check(&rec.payload),
+ .host, .ret, .done => t.diverge("a {t} record at the top", .{kind}),
+ }
+ }
+ return t.diverged;
+}
+
+/// Starts recording `t`'s core as a speculation: the host's watched
+/// fields as they are now, nothing recorded yet.
+pub fn beginSpeculation(t: *Tape) void {
+ t.replay = false;
+ t.speculating = true;
+ t.poisoned = false;
+ t.no_digest = true;
+ t.buf.clearRetainingCapacity();
+ t.seeFields();
+}
+
+/// Whether it stayed clean (no host call, no syscall, no authority state).
+pub fn endSpeculation(t: *Tape) bool {
+ t.speculating = false;
+ t.no_digest = false;
+ return !t.poisoned;
+}
+
+/// Whether two tapes record the same inputs, host calls and answers,
+/// their digests aside.
+pub fn sameRecords(a: []const u8, b: []const u8) bool {
+ var x: walk.Reader = .{ .bytes = a };
+ var y: walk.Reader = .{ .bytes = b };
+ while (true) {
+ const ra = nextRecord(&x);
+ const rb = nextRecord(&y);
+ if (ra == null or rb == null) return ra == null and rb == null;
+ if (ra.?.kind != rb.?.kind or !std.mem.eql(u8, ra.?.payload, rb.?.payload)) return false;
+ }
+}
+
+fn nextRecord(r: *walk.Reader) ?struct { kind: Kind, payload: []const u8 } {
+ while (true) {
+ const head = r.take(5) catch return null;
+ const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return null;
+ const kind: Kind = @fromBackingInt(@intCast(head[0]));
+ if (kind != .digest) return .{ .kind = kind, .payload = payload };
+ }
+}
+
+/// A tape's records, one a line (kind; an input's or a host call's name),
+/// for a divergence's report.
+pub fn describe(bytes: []const u8, w: *std.Io.Writer) void {
+ var r: walk.Reader = .{ .bytes = bytes };
+ var depth: usize = 0;
+ while (true) {
+ const head = r.take(5) catch return;
+ const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return;
+ const kind: Kind = @fromBackingInt(@intCast(head[0]));
+ if (kind == .done or kind == .ret) depth -|= 1;
+ w.splatByteAll(' ', depth * 2) catch {};
+ switch (kind) {
+ .input => {
+ const tag = std.mem.bytesToValue(std.meta.Tag(Input), payload[0..@sizeOf(std.meta.Tag(Input))]);
+ w.print("input {t}", .{tag}) catch {};
+ if (tag == .update) w.print(" {t}", .{std.mem.bytesToValue(std.meta.Tag(pardes.Event), payload[@sizeOf(std.meta.Tag(Input))..][0..@sizeOf(std.meta.Tag(pardes.Event))])}) catch {};
+ },
+ .host => {
+ const id = std.mem.bytesToValue(u16, payload[0..2]);
+ w.print("host {s}", .{if (id < host_fns.len) host_fns[id] else @tagName(@as(Site, @fromBackingInt(@intCast(id - host_fns.len))))}) catch {};
+ },
+ else => w.print("{t} ({d} bytes)", .{ kind, payload.len }) catch {},
+ }
+ w.writeByte('\n') catch {};
+ if (kind == .input or kind == .host) depth += 1;
+ }
+}
+
+/// The digest a replica and its authority must agree on.
+pub fn digestOf(p: *const Pardes) u64 {
+ return walk.digest(Pardes, p);
}
/// PARDES_RECORD set: the tape is written from the session's first call.