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