//! A recording on disk, in xitdb: a history of immutable moments. Each //! moment is the whole state then (registers per thread, the memory seen so //! far, the strings defined) sharing everything unchanged with the moment //! before, plus the events that led to it. Time travel is an index. //! //! history[i] = map { //! delta the events of this moment: (u32 payload length, Event, payload)* //! count events up to and including this moment //! regs map tid -> Regs bytes //! mem sorted map, big-endian (addr / 64) -> u64 mask of known bytes, 64 bytes //! strings map id -> text //! } //! //! The `Recorder` is a `Sink`: it takes events from any backend, folds them //! into the state, and ends a moment at the kinds in `cut`. const std = @import("std"); const xitdb = @import("xitdb"); const event = @import("event.zig"); const Event = event.Event; const Regs = event.Regs; const Kind = event.Kind; const WriteDB = xitdb.Database(.buffered_file, u64); const ReadDB = xitdb.Database(.file, u64); const Key = enum(u64) { delta = 1, count, regs, mem, strings }; fn key(k: Key) u64 { return @intFromEnum(k); } pub const chunk_bytes = 64; const Chunk = extern struct { /// Bit i set: byte i was recorded. known: u64 = 0, bytes: [chunk_bytes]u8 = @splat(0), }; fn chunkKey(index: u64) [8]u8 { var out: [8]u8 = undefined; std.mem.writeInt(u64, &out, index, .big); return out; } pub const Recorder = struct { gpa: std.mem.Allocator, io: std.Io, file: std.Io.File, /// Its own allocation: the database points at it. buffer: *std.Io.Writer.Allocating, db: WriteDB, /// A moment ends after an event of one of these kinds. cut: u64 = Kind.step.bit() | Kind.breakpoint.bit() | Kind.syscall_exit.bit() | Kind.signal.bit() | Kind.exit.bit() | Kind.line.bit() | Kind.mark.bit(), /// ... or when its events pass this many bytes. max_delta: usize = 1 << 20, delta: std.ArrayList(u8) = .empty, count: u64 = 0, moments: u64 = 0, regs_dirty: std.AutoArrayHashMapUnmanaged(u32, Regs) = .empty, /// Every chunk recorded so far, so a partial write needs no read back. mem: std.AutoHashMapUnmanaged(u64, Chunk) = .empty, mem_dirty: std.AutoArrayHashMapUnmanaged(u64, void) = .empty, /// (id, offset and length into `delta`) of this moment's strings. strings_dirty: std.ArrayList(struct { id: u64, at: usize, len: usize }) = .empty, /// A new recording at `path`, replacing any file there. pub fn create(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Recorder { const file = try std.Io.Dir.cwd().createFile(io, path, .{ .read = true, .truncate = true }); errdefer file.close(io); const buffer = try gpa.create(std.Io.Writer.Allocating); errdefer gpa.destroy(buffer); buffer.* = .init(gpa); errdefer buffer.deinit(); // No fsync: a recording is rewritten by running the program again. const db = try WriteDB.init(io, .{ .file = file, .buffer = buffer, .fsync = false }); return .{ .gpa = gpa, .io = io, .file = file, .buffer = buffer, .db = db }; } /// Ends the last moment and closes the file. pub fn close(r: *Recorder) !void { defer { r.delta.deinit(r.gpa); r.regs_dirty.deinit(r.gpa); r.mem.deinit(r.gpa); r.mem_dirty.deinit(r.gpa); r.strings_dirty.deinit(r.gpa); r.file.close(r.io); r.buffer.deinit(); r.gpa.destroy(r.buffer); } if (r.delta.items.len > 0) try r.commit(); try r.db.core.flush(); } pub fn sink(r: *Recorder) event.Sink { return .{ .ctx = r, .emitFn = sinkEmit }; } fn sinkEmit(ctx: *anyopaque, ev: *const Event, payload: []const u8) anyerror!void { const r: *Recorder = @ptrCast(@alignCast(ctx)); return r.emit(ev.*, payload); } pub fn emit(r: *Recorder, ev: Event, payload: []const u8) !void { var len: [4]u8 = undefined; std.mem.writeInt(u32, &len, @intCast(payload.len), .little); try r.delta.appendSlice(r.gpa, &len); try r.delta.appendSlice(r.gpa, std.mem.asBytes(&ev)); const payload_at = r.delta.items.len; try r.delta.appendSlice(r.gpa, payload); r.count += 1; switch (ev.kind) { .mem_write => try r.write(ev.a[0], payload), .string => try r.strings_dirty.append(r.gpa, .{ .id = ev.a[0], .at = payload_at, .len = payload.len }), // Any event may carry the thread's registers. else => if (payload.len == @sizeOf(Regs)) try r.regs_dirty.put(r.gpa, ev.tid, std.mem.bytesToValue(Regs, payload)), } if (r.cut & ev.kind.bit() != 0 or r.delta.items.len >= r.max_delta) try r.commit(); } fn write(r: *Recorder, addr: u64, bytes: []const u8) !void { var at = addr; var rest = bytes; while (rest.len > 0) { const index = at / chunk_bytes; const off: usize = @intCast(at % chunk_bytes); const n = @min(rest.len, chunk_bytes - off); const gop = try r.mem.getOrPut(r.gpa, index); if (!gop.found_existing) gop.value_ptr.* = .{}; @memcpy(gop.value_ptr.bytes[off..][0..n], rest[0..n]); gop.value_ptr.known |= (if (n == 64) ~@as(u64, 0) else (@as(u64, 1) << @intCast(n)) - 1) << @intCast(off); try r.mem_dirty.put(r.gpa, index, {}); at += n; rest = rest[n..]; } } /// Ends the moment: one transaction. pub fn commit(r: *Recorder) !void { const Ctx = struct { r: *Recorder, pub fn run(ctx: @This(), cursor: *WriteDB.Cursor(.read_write)) !void { const rec = ctx.r; const moment = try WriteDB.HashMap(.read_write).init(cursor.*); try moment.put(key(.delta), .{ .bytes = rec.delta.items }); try moment.put(key(.count), .{ .uint = rec.count }); if (rec.regs_dirty.count() > 0) { const regs = try WriteDB.HashMap(.read_write).init(try moment.putCursor(key(.regs))); for (rec.regs_dirty.keys(), rec.regs_dirty.values()) |tid, *value| try regs.put(tid, .{ .bytes = std.mem.asBytes(value) }); } if (rec.mem_dirty.count() > 0) { const mem = try WriteDB.SortedMap(.read_write).init(try moment.putCursor(key(.mem))); for (rec.mem_dirty.keys()) |index| try mem.put(&chunkKey(index), .{ .bytes = std.mem.asBytes(rec.mem.getPtr(index).?) }); } if (rec.strings_dirty.items.len > 0) { const strings = try WriteDB.HashMap(.read_write).init(try moment.putCursor(key(.strings))); for (rec.strings_dirty.items) |s| try strings.put(s.id, .{ .bytes = rec.delta.items[s.at..][0..s.len] }); } } }; const history = try WriteDB.ArrayList(.read_write).init(r.db.rootCursor()); try history.appendContext(.{ .slot = try history.getSlot(-1) }, Ctx{ .r = r }); r.moments += 1; r.delta.clearRetainingCapacity(); r.regs_dirty.clearRetainingCapacity(); r.mem_dirty.clearRetainingCapacity(); r.strings_dirty.clearRetainingCapacity(); } }; /// A recording, read. Any moment, in any order. pub const Trace = struct { gpa: std.mem.Allocator, io: std.Io, file: std.Io.File, db: *ReadDB, len: u64, pub fn open(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Trace { const file = try std.Io.Dir.cwd().openFile(io, path, .{}); errdefer file.close(io); const db = try gpa.create(ReadDB); errdefer gpa.destroy(db); db.* = try ReadDB.init(io, .{ .file = file, .fsync = false }); const history = try ReadDB.ArrayList(.read_only).init(db.rootCursor().readOnly()); return .{ .gpa = gpa, .io = io, .file = file, .db = db, .len = try history.count() }; } pub fn close(t: *Trace) void { t.file.close(t.io); t.gpa.destroy(t.db); } pub fn moment(t: *const Trace, index: u64) !Moment { const history = try ReadDB.ArrayList(.read_only).init(t.db.rootCursor().readOnly()); const cursor = (try history.getCursor(@intCast(index))) orelse return error.NoSuchMoment; return .{ .index = index, .map = try ReadDB.HashMap(.read_only).init(cursor) }; } }; pub const Moment = struct { index: u64, map: ReadDB.HashMap(.read_only), /// Events up to and including this moment. pub fn count(m: Moment) !u64 { return (try m.map.getCursor(key(.count))).?.readUint(); } pub fn regs(m: Moment, tid: u32) !?Regs { const all = try ReadDB.HashMap(.read_only).init((try m.map.getCursor(key(.regs))) orelse return null); const cursor = (try all.getCursor(tid)) orelse return null; var out: Regs = undefined; _ = try cursor.readBytes(std.mem.asBytes(&out)); return out; } /// The memory at `addr` as of this moment. Bytes never recorded read as /// zero, and false in `known` when it is given. pub fn read(m: Moment, addr: u64, buf: []u8, known: ?[]bool) !void { @memset(buf, 0); if (known) |k| @memset(k, false); const mem = try ReadDB.SortedMap(.read_only).init((try m.map.getCursor(key(.mem))) orelse return); var done: usize = 0; while (done < buf.len) { const at = addr + done; const off: usize = @intCast(at % chunk_bytes); const n = @min(buf.len - done, chunk_bytes - off); if (try mem.getCursor(&chunkKey(at / chunk_bytes))) |cursor| { var chunk: Chunk = undefined; _ = try cursor.readBytes(std.mem.asBytes(&chunk)); @memcpy(buf[done..][0..n], chunk.bytes[off..][0..n]); if (known) |k| for (k[done..][0..n], off..) |*bit, i| { bit.* = chunk.known >> @intCast(i) & 1 != 0; }; } done += n; } } pub fn string(m: Moment, id: u64, buf: []u8) !?[]const u8 { const all = try ReadDB.HashMap(.read_only).init((try m.map.getCursor(key(.strings))) orelse return null); const cursor = (try all.getCursor(id)) orelse return null; return try cursor.readBytes(buf); } /// The events that led from the moment before to this one. Free with /// `Events.deinit`. pub fn events(m: Moment, gpa: std.mem.Allocator) !Events { const cursor = (try m.map.getCursor(key(.delta))).?; return .{ .bytes = try cursor.readBytesAlloc(gpa, null) }; } }; pub const Events = struct { bytes: []const u8, at: usize = 0, pub const Item = struct { ev: Event, payload: []const u8 }; pub fn deinit(e: *Events, gpa: std.mem.Allocator) void { gpa.free(e.bytes); } pub fn next(e: *Events) ?Item { if (e.at >= e.bytes.len) return null; const len = std.mem.readInt(u32, e.bytes[e.at..][0..4], .little); const ev = std.mem.bytesToValue(Event, e.bytes[e.at + 4 ..][0..@sizeOf(Event)]); const start = e.at + 4 + @sizeOf(Event); e.at = start + len; return .{ .ev = ev, .payload = e.bytes[start..][0..len] }; } }; test "a recording is read back moment by moment" { const gpa = std.testing.allocator; const io = std.testing.io; var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var path_buf: [std.Io.Dir.max_path_bytes]u8 = undefined; const dir = path_buf[0..try tmp.dir.realPath(io, &path_buf)]; const path = try std.fs.path.join(gpa, &.{ dir, "t.ztrace" }); defer gpa.free(path); var rec = try Recorder.create(gpa, io, path); try rec.emit(.{ .kind = .string, .a = .{ 9, 0, 0, 0, 0, 0 } }, "fib.c"); for (0..3) |i| { // A write that straddles two chunks, then the step that ends the moment. const bytes: [4]u8 = @splat(@intCast(i + 1)); try rec.emit(.{ .kind = .mem_write, .a = .{ 62 + i, 4, 0, 0, 0, 0 } }, &bytes); const regs: Regs = .{ .rip = 0x1000 + i, .rax = i }; try rec.emit(.{ .kind = .step, .tid = 7, .a = .{ regs.rip, 0, 0, 0, 0, 0 } }, std.mem.asBytes(®s)); } try rec.close(); var trace = try Trace.open(gpa, io, path); defer trace.close(); try std.testing.expectEqual(@as(u64, 3), trace.len); // The first moment still shows the first write only: nothing later leaked back. const first = try trace.moment(0); var buf: [8]u8 = undefined; var known: [8]bool = undefined; try first.read(60, &buf, &known); try std.testing.expectEqualSlices(u8, &.{ 0, 0, 1, 1, 1, 1, 0, 0 }, &buf); try std.testing.expectEqualSlices(bool, &.{ false, false, true, true, true, true, false, false }, &known); try std.testing.expectEqual(@as(u64, 0x1000), (try first.regs(7)).?.rip); try std.testing.expectEqual(@as(u64, 3), try first.count()); const last = try trace.moment(2); try last.read(60, &buf, null); try std.testing.expectEqualSlices(u8, &.{ 0, 0, 1, 2, 3, 3, 3, 3 }, &buf); try std.testing.expectEqual(@as(u64, 2), (try last.regs(7)).?.rax); try std.testing.expect((try last.regs(8)) == null); var name: [16]u8 = undefined; try std.testing.expectEqualStrings("fib.c", (try last.string(9, &name)).?); var events = try last.events(gpa); defer events.deinit(gpa); try std.testing.expectEqual(Kind.mem_write, events.next().?.ev.kind); const step = events.next().?; try std.testing.expectEqual(@as(u64, 0x1002), step.ev.a[0]); try std.testing.expectEqual(@sizeOf(Regs), step.payload.len); try std.testing.expect(events.next() == null); }