summaryrefslogtreecommitdiff
path: root/src/trace/store.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-10 11:08:49 -0300
committerGabriel Schneider <[email protected]>2026-11-10 11:08:49 -0300
commit0b29354e1ddf6cf75ac4c426a00dd3435ace5069 (patch)
tree918e6f6810a9b8b5a8ed17e698085e92018333b9 /src/trace/store.zig
downloadcomputeranim-0b29354e1ddf6cf75ac4c426a00dd3435ace5069.tar.gz
computeranim-0b29354e1ddf6cf75ac4c426a00dd3435ace5069.zip
ztrace: the event, the ring, the recording, a ptrace loop
One 64-byte Event for every backend; a shared-memory ring from target to tracer with stop/resume; a Recorder that folds events into xitdb moments (registers, memory in 64-byte chunks with known-byte masks, strings) and a Trace that reads any moment back; a minimal ptrace Process; ztrace record, run and dump. Per-area build files so the areas grow apart.
Diffstat (limited to 'src/trace/store.zig')
-rw-r--r--src/trace/store.zig325
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(&regs));
+ }
+ 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);
+}