diff options
Diffstat (limited to 'src/trace/store.zig')
| -rw-r--r-- | src/trace/store.zig | 325 |
1 files changed, 325 insertions, 0 deletions
diff --git a/src/trace/store.zig b/src/trace/store.zig new file mode 100644 index 0000000..3eca8b7 --- /dev/null +++ b/src/trace/store.zig @@ -0,0 +1,325 @@ +//! 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); +} |
