From 8d91ecf978b99a79e3ff237cda14daa3d666509f Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 10 Nov 2026 11:19:14 -0300 Subject: recorder: moments in batches, and the heap, the stack, variables, lines and mappings in each MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit A transaction a moment cost 10 µs and 1 KB before the moment's own data: the list's path copied each time. Moments now gather 256 to a transaction, each frozen by its own cursor so the list grows in place, and a thread's fields sit in the moment's map instead of two maps down: a small moment is 284 bytes and 1 µs, an instruction step with registers 780 bytes. A moment also folds alloc/free into the live heap, call/ret into each thread's stack, variable into the live variables (a local leaves with its call), line, and map/unmap, so a viewer reads any of them at any moment without replaying. --- src/trace/event.zig | 4 +- src/trace/store.zig | 541 ++++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 460 insertions(+), 85 deletions(-) (limited to 'src/trace') diff --git a/src/trace/event.zig b/src/trace/event.zig index 91e8c62..c24d7ac 100644 --- a/src/trace/event.zig +++ b/src/trace/event.zig @@ -28,7 +28,8 @@ pub const Kind = enum(u16) { mem_write = 16, /// a0=addr a1=len a2=pc mem_read = 17, - /// a0=ptr a1=size a2=caller pc. aux: `Alloc`. + /// a0=ptr a1=size a2=caller pc. aux: `Alloc`. A realloc that moves is a + /// `free` of the old pointer, then this. alloc = 18, /// a0=ptr a1=caller pc free = 19, @@ -79,6 +80,7 @@ pub const Alloc = enum(u16) { malloc, calloc, realloc, memalign, mmap }; pub const Event = extern struct { /// CLOCK_MONOTONIC nanoseconds. ts: u64 = 0, + /// 0 for an event no thread made (a string defined at startup). tid: u32 = 0, kind: Kind, /// Small kind-specific value (syscall number, signal, operand size). diff --git a/src/trace/store.zig b/src/trace/store.zig index 3eca8b7..e38ef03 100644 --- a/src/trace/store.zig +++ b/src/trace/store.zig @@ -1,18 +1,24 @@ -//! 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. +//! A recording on disk, in xitdb: a list of immutable moments. Each moment +//! is the whole state of the program then, sharing everything unchanged with +//! the moment before, plus the events that led to it. Time travel is an +//! index. //! -//! history[i] = map { +//! root = map { moments: list of moment } +//! moment = 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 +//! threads the set of tids seen +//! tid, regs / line / stack a thread's registers, source line, open calls +//! mem sorted map, big-endian (addr / 64) -> Chunk: the known bytes +//! heap sorted map, big-endian ptr -> Allocation: the live allocations +//! vars sorted map, big-endian addr -> Variable: the live named variables +//! maps sorted map, big-endian addr -> Mapping, path: the mapped regions //! 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`. +//! into that state, and ends a moment at the kinds in `cut`. Moments are +//! written a batch a transaction, each frozen before the next begins. const std = @import("std"); const xitdb = @import("xitdb"); const event = @import("event.zig"); @@ -23,11 +29,24 @@ 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 }; +const Key = enum(u64) { moments = 1, delta, count, threads, mem, heap, vars, maps, strings }; fn key(k: Key) u64 { return @intFromEnum(k); } +/// A thread's fields sit in the moment's own map, under the tid and a low +/// nibble no `Key` has: one block to copy when a register changes, not three. +const Field = enum(u64) { regs = 13, line, stack }; +fn threadKey(tid: u64, f: Field) u64 { + return tid << 4 | @intFromEnum(f); +} + +fn be(value: u64) [8]u8 { + var out: [8]u8 = undefined; + std.mem.writeInt(u64, &out, value, .big); + return out; +} + pub const chunk_bytes = 64; const Chunk = extern struct { /// Bit i set: byte i was recorded. @@ -35,11 +54,32 @@ const Chunk = extern struct { 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; -} +/// Where a thread is in its source. +pub const Line = extern struct { file: u64 = 0, line: u32 = 0, column: u32 = 0 }; +/// A call not yet returned from. +pub const Frame = extern struct { function: u64, site: u64, sp: u64 }; +pub const Allocation = extern struct { + ptr: u64, + size: u64, + /// The caller of malloc. + pc: u64, + /// The number of the `alloc` event, from 1. + born: u64, +}; +pub const Variable = extern struct { + addr: u64, + size: u64, + /// String ids: resolve with `Moment.string`. + name: u64, + type: u64, + tid: u32, + /// Calls deep when it was declared; 0 for a global. + depth: u32, +}; +pub const Mapping = extern struct { addr: u64, len: u64, prot: u64, offset: u64 }; + +/// What a moment changed, kept until its batch is written. +const Op = enum(u8) { delta, thread, regs, line, push, pop, chunk, heap_put, heap_del, var_put, var_del, map_put, map_del, string, end }; pub const Recorder = struct { gpa: std.mem.Allocator, @@ -52,15 +92,21 @@ pub const Recorder = struct { 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, + /// Moments a transaction. A crash loses the batch being gathered. + batch: usize = 256, delta: std.ArrayList(u8) = .empty, count: u64 = 0, + /// Moments ended, written or not. moments: u64 = 0, - regs_dirty: std.AutoArrayHashMapUnmanaged(u32, Regs) = .empty, + ops: std.ArrayList(u8) = .empty, + pending: usize = 0, /// 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, + /// Per thread seen: where each open call's variables begin in `declared`. + calls: std.AutoHashMapUnmanaged(u32, Calls) = .empty, + + const Calls = struct { frames: std.ArrayList(usize) = .empty, declared: std.ArrayList(u64) = .empty }; /// A new recording at `path`, replacing any file there. pub fn create(gpa: std.mem.Allocator, io: std.Io, path: []const u8) !Recorder { @@ -75,19 +121,25 @@ pub const Recorder = struct { return .{ .gpa = gpa, .io = io, .file = file, .buffer = buffer, .db = db }; } - /// Ends the last moment and closes the file. + /// Ends the last moment, writes what is pending and closes the file. pub fn close(r: *Recorder) !void { defer { r.delta.deinit(r.gpa); - r.regs_dirty.deinit(r.gpa); + r.ops.deinit(r.gpa); r.mem.deinit(r.gpa); r.mem_dirty.deinit(r.gpa); - r.strings_dirty.deinit(r.gpa); + var it = r.calls.valueIterator(); + while (it.next()) |c| { + c.frames.deinit(r.gpa); + c.declared.deinit(r.gpa); + } + r.calls.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.flush(); try r.db.core.flush(); } @@ -100,21 +152,59 @@ pub const Recorder = struct { return r.emit(ev.*, payload); } + fn op(r: *Recorder, tag: Op, fields: anytype, bytes: []const u8) !void { + try r.ops.append(r.gpa, @intFromEnum(tag)); + inline for (fields) |f| try r.ops.appendSlice(r.gpa, std.mem.asBytes(&@as(u64, f))); + try r.ops.appendSlice(r.gpa, std.mem.asBytes(&@as(u32, @intCast(bytes.len)))); + try r.ops.appendSlice(r.gpa, bytes); + } + 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(&@as(u32, @intCast(payload.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; + const a = ev.a; + const calls = try r.calls.getOrPut(r.gpa, ev.tid); + if (!calls.found_existing) { + calls.value_ptr.* = .{}; + // Tid 0 is no thread: a string defined before any ran. + if (ev.tid != 0) try r.op(.thread, .{ev.tid}, ""); + } + const c = calls.value_ptr; 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)), + .mem_write => try r.write(a[0], payload), + .string => try r.op(.string, .{a[0]}, payload), + .line => try r.op(.line, .{ev.tid}, std.mem.asBytes(&Line{ .file = a[0], .line = @truncate(a[1]), .column = @truncate(a[2]) })), + .alloc => try r.op(.heap_put, .{a[0]}, std.mem.asBytes(&Allocation{ .ptr = a[0], .size = a[1], .pc = a[2], .born = r.count })), + .free => try r.op(.heap_del, .{a[0]}, ""), + .map => { + try r.op(.map_put, .{a[0]}, std.mem.asBytes(&Mapping{ .addr = a[0], .len = a[1], .prot = a[2], .offset = a[3] })); + try r.ops.appendSlice(r.gpa, std.mem.asBytes(&@as(u32, @intCast(payload.len)))); + try r.ops.appendSlice(r.gpa, payload); + }, + .unmap => try r.op(.map_del, .{a[0]}, ""), + .call => { + try c.frames.append(r.gpa, c.declared.items.len); + try r.op(.push, .{ev.tid}, std.mem.asBytes(&Frame{ .function = a[0], .site = a[1], .sp = a[2] })); + }, + .ret => { + // A return with no call recorded (tracing began inside it): nothing to pop. + if (c.frames.pop()) |from| { + for (c.declared.items[from..]) |addr| try r.op(.var_del, .{addr}, ""); + c.declared.shrinkRetainingCapacity(from); + try r.op(.pop, .{ev.tid}, ""); + } + }, + .variable => { + if (c.frames.items.len > 0) try c.declared.append(r.gpa, a[0]); + try r.op(.var_put, .{a[0]}, std.mem.asBytes(&Variable{ .addr = a[0], .size = a[1], .name = a[2], .type = a[3], .tid = ev.tid, .depth = @intCast(c.frames.items.len) })); + }, + else => {}, } + // Any event may carry its thread's registers. + if (payload.len == @sizeOf(Regs) and ev.kind != .mem_write and ev.kind != .string) try r.op(.regs, .{ev.tid}, payload); if (r.cut & ev.kind.bit() != 0 or r.delta.items.len >= r.max_delta) try r.commit(); } @@ -125,47 +215,124 @@ pub const Recorder = struct { const index = at / chunk_bytes; const off: usize = @intCast(at % chunk_bytes); const n = @min(rest.len, chunk_bytes - off); + const mask = (if (n == 64) ~@as(u64, 0) else (@as(u64, 1) << @intCast(n)) - 1) << @intCast(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, {}); + const chunk = gop.value_ptr; + // A write of what is already there changes nothing worth storing. + if (chunk.known & mask != mask or !std.mem.eql(u8, chunk.bytes[off..][0..n], rest[0..n])) { + @memcpy(chunk.bytes[off..][0..n], rest[0..n]); + chunk.known |= mask; + try r.mem_dirty.put(r.gpa, index, {}); + } at += n; rest = rest[n..]; } } - /// Ends the moment: one transaction. + /// Ends the moment. It reaches the file with its batch. 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(); + for (r.mem_dirty.keys()) |index| try r.op(.chunk, .{index}, std.mem.asBytes(r.mem.getPtr(index).?)); r.mem_dirty.clearRetainingCapacity(); - r.strings_dirty.clearRetainingCapacity(); + try r.op(.delta, .{r.count}, r.delta.items); + r.delta.clearRetainingCapacity(); + try r.ops.append(r.gpa, @intFromEnum(Op.end)); + r.moments += 1; + r.pending += 1; + if (r.pending >= r.batch) try r.flush(); + } + + /// Writes the moments ended so far: one transaction. + pub fn flush(r: *Recorder) !void { + if (r.pending == 0) return; + try r.db.runContext(Batch{ .ops = r.ops.items }); + r.ops.clearRetainingCapacity(); + r.pending = 0; } + + const Batch = struct { + ops: []const u8, + at: usize = 0, + + const DB = WriteDB; + const Map = DB.HashMap(.read_write); + const Sorted = DB.SortedMap(.read_write); + const List = DB.ArrayList(.read_write); + + fn take(b: *Batch, comptime T: type) T { + defer b.at += @sizeOf(T); + return std.mem.bytesToValue(T, b.ops[b.at..][0..@sizeOf(T)]); + } + + fn bytes(b: *Batch) []const u8 { + const len = b.take(u32); + defer b.at += len; + return b.ops[b.at..][0..len]; + } + + pub fn run(ctx: Batch, cursor: *DB.Cursor(.read_write)) !void { + var b = ctx; + const root = try Map.init(cursor.*); + const moments = try List.init(try root.putCursor(key(.moments))); + while (b.at < b.ops.len) { + // The new moment starts as the last one, which is immutable + // from here: what this one changes it copies, the rest it + // shares. The list itself grows in place. + try moments.append(.{ .slot = try moments.getSlot(-1) }); + var at = try moments.putCursor(-1); + try at.freeze(); + const moment = try Map.init(at); + while (true) switch (@as(Op, @enumFromInt(b.take(u8)))) { + .end => break, + .delta => { + try moment.put(key(.count), .{ .uint = b.take(u64) }); + try moment.put(key(.delta), .{ .bytes = b.bytes() }); + }, + .thread => { + try (try Map.init(try moment.putCursor(key(.threads)))).put(b.take(u64), .{ .uint = 1 }); + _ = b.bytes(); + }, + .regs => try moment.put(threadKey(b.take(u64), .regs), .{ .bytes = b.bytes() }), + .line => try moment.put(threadKey(b.take(u64), .line), .{ .bytes = b.bytes() }), + .push => { + const stack = try List.init(try moment.putCursor(threadKey(b.take(u64), .stack))); + try stack.append(.{ .bytes = b.bytes() }); + }, + .pop => { + const stack = try List.init(try moment.putCursor(threadKey(b.take(u64), .stack))); + _ = b.bytes(); + const n = try stack.count(); + if (n > 0) try stack.slice(n - 1); + }, + .chunk => try (try Sorted.init(try moment.putCursor(key(.mem)))).put(&be(b.take(u64)), .{ .bytes = b.bytes() }), + .heap_put => try (try Sorted.init(try moment.putCursor(key(.heap)))).put(&be(b.take(u64)), .{ .bytes = b.bytes() }), + .var_put => try (try Sorted.init(try moment.putCursor(key(.vars)))).put(&be(b.take(u64)), .{ .bytes = b.bytes() }), + .heap_del, .var_del, .map_del => |tag| { + const which: Key = switch (tag) { + .heap_del => .heap, + .var_del => .vars, + else => .maps, + }; + const addr = be(b.take(u64)); + _ = b.bytes(); + // Freeing what was never seen allocated is not an error here. + _ = try (try Sorted.init(try moment.putCursor(key(which)))).remove(&addr); + }, + .map_put => { + const addr = be(b.take(u64)); + const mapping = b.bytes(); + const path = b.bytes(); + var value: [@sizeOf(Mapping) + std.Io.Dir.max_path_bytes]u8 = undefined; + const n = @min(path.len, std.Io.Dir.max_path_bytes); + @memcpy(value[0..mapping.len], mapping); + @memcpy(value[mapping.len..][0..n], path[0..n]); + try (try Sorted.init(try moment.putCursor(key(.maps)))).put(&addr, .{ .bytes = value[0 .. mapping.len + n] }); + }, + .string => try (try Map.init(try moment.putCursor(key(.strings)))).put(b.take(u64), .{ .bytes = b.bytes() }), + }; + } + } + }; }; /// A recording, read. Any moment, in any order. @@ -174,16 +341,22 @@ pub const Trace = struct { io: std.Io, file: std.Io.File, db: *ReadDB, + /// The number of moments. len: u64, + const Map = ReadDB.HashMap(.read_only); + const Sorted = ReadDB.SortedMap(.read_only); + const List = ReadDB.ArrayList(.read_only); + 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() }; + var t: Trace = .{ .gpa = gpa, .io = io, .file = file, .db = db, .len = 0 }; + if (try t.list()) |moments| t.len = try moments.count(); + return t; } pub fn close(t: *Trace) void { @@ -191,44 +364,92 @@ pub const Trace = struct { t.gpa.destroy(t.db); } + fn list(t: *const Trace) !?List { + const root = try Map.init(t.db.rootCursor().readOnly()); + return try List.init((try root.getCursor(key(.moments))) orelse return null); + } + 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) }; + const moments = (try t.list()) orelse return error.NoSuchMoment; + const cursor = (try moments.getCursor(@intCast(index))) orelse return error.NoSuchMoment; + return .{ .index = index, .map = try Map.init(cursor) }; + } + + /// The moment that holds event number `n` (from 1): the first whose + /// count reaches it. + pub fn momentOf(t: *const Trace, n: u64) !?u64 { + var lo: u64 = 0; + var hi = t.len; + while (lo < hi) { + const mid = lo + (hi - lo) / 2; + if (try (try t.moment(mid)).count() < n) lo = mid + 1 else hi = mid; + } + return if (lo < t.len) lo else null; } }; pub const Moment = struct { index: u64, - map: ReadDB.HashMap(.read_only), + map: Trace.Map, + + const Map = Trace.Map; + const Sorted = Trace.Sorted; + const List = Trace.List; /// 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; + fn value(comptime T: type, cursor: ReadDB.Cursor(.read_only)) !T { + var out: T = undefined; _ = try cursor.readBytes(std.mem.asBytes(&out)); return out; } + /// The threads seen so far, in no order. + pub fn threads(m: Moment, gpa: std.mem.Allocator) ![]u32 { + var out: std.ArrayList(u32) = .empty; + errdefer out.deinit(gpa); + if (try m.map.getCursor(key(.threads))) |cursor| { + var it = try cursor.iterator(); + while (try it.next()) |entry| try out.append(gpa, @intCast((try entry.readKeyValuePair()).hash)); + } + return out.toOwnedSlice(gpa); + } + + pub fn regs(m: Moment, tid: u32) !?Regs { + return try value(Regs, (try m.map.getCursor(threadKey(tid, .regs))) orelse return null); + } + + pub fn line(m: Moment, tid: u32) !?Line { + return try value(Line, (try m.map.getCursor(threadKey(tid, .line))) orelse return null); + } + + /// The calls a thread is inside, outermost first. + pub fn stack(m: Moment, gpa: std.mem.Allocator, tid: u32) ![]Frame { + var out: std.ArrayList(Frame) = .empty; + errdefer out.deinit(gpa); + if (try m.map.getCursor(threadKey(tid, .stack))) |cursor| { + var it = try (try List.init(cursor)).iterator(); + while (try it.next()) |frame| try out.append(gpa, try value(Frame, frame)); + } + return out.toOwnedSlice(gpa); + } + /// 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); + const mem = try Sorted.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)); + if (try mem.getCursor(&be(at / chunk_bytes))) |cursor| { + const chunk = try value(Chunk, cursor); @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; @@ -238,8 +459,67 @@ pub const Moment = struct { } } + fn sorted(m: Moment, comptime T: type, gpa: std.mem.Allocator, which: Key) ![]T { + var out: std.ArrayList(T) = .empty; + errdefer out.deinit(gpa); + if (try m.map.getCursor(key(which))) |cursor| { + var it = try (try Sorted.init(cursor)).iterator(); + while (try it.next()) |entry| try out.append(gpa, try value(T, (try entry.readKeyValuePair()).value_cursor)); + } + return out.toOwnedSlice(gpa); + } + + /// The entry of a sorted map at the greatest key not above `addr`. + fn floor(m: Moment, comptime T: type, which: Key, addr: u64) !?T { + const map = try Sorted.init((try m.map.getCursor(key(which))) orelse return null); + const below = try map.rank(&be(addr +| 1)); + if (below == 0) return null; + const pair = (try map.getIndexKeyValuePair(@intCast(below - 1))) orelse return null; + return try value(T, pair.value_cursor); + } + + /// The live allocations, by address. + pub fn heap(m: Moment, gpa: std.mem.Allocator) ![]Allocation { + return m.sorted(Allocation, gpa, .heap); + } + + /// The live allocation that holds `addr`. + pub fn allocation(m: Moment, addr: u64) !?Allocation { + const a = (try m.floor(Allocation, .heap, addr)) orelse return null; + return if (addr - a.ptr < @max(a.size, 1)) a else null; + } + + /// The live named variables, by address. + pub fn variables(m: Moment, gpa: std.mem.Allocator) ![]Variable { + return m.sorted(Variable, gpa, .vars); + } + + /// The mapped regions, by address. + pub fn mappings(m: Moment, gpa: std.mem.Allocator) ![]Mapping { + return m.sorted(Mapping, gpa, .maps); + } + + /// The region that holds `addr`, and the file it maps into `path` (empty + /// when anonymous). + pub fn mapping(m: Moment, addr: u64, path: ?*[]const u8, buf: []u8) !?Mapping { + const map = try Sorted.init((try m.map.getCursor(key(.maps))) orelse return null); + const below = try map.rank(&be(addr +| 1)); + if (below == 0) return null; + const pair = (try map.getIndexKeyValuePair(@intCast(below - 1))) orelse return null; + var raw: [@sizeOf(Mapping) + std.Io.Dir.max_path_bytes]u8 = undefined; + const bytes = try pair.value_cursor.readBytes(&raw); + const found = std.mem.bytesToValue(Mapping, bytes[0..@sizeOf(Mapping)]); + if (addr - found.addr >= found.len) return null; + if (path) |p| { + const n = @min(buf.len, bytes.len - @sizeOf(Mapping)); + @memcpy(buf[0..n], bytes[@sizeOf(Mapping)..][0..n]); + p.* = buf[0..n]; + } + return found; + } + 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 all = try Map.init((try m.map.getCursor(key(.strings))) orelse return null); const cursor = (try all.getCursor(id)) orelse return null; return try cursor.readBytes(buf); } @@ -272,28 +552,37 @@ pub const Events = struct { } }; -test "a recording is read back moment by moment" { +fn testPath(gpa: std.mem.Allocator, tmp: *std.testing.TmpDir) ![]u8 { + var buf: [std.Io.Dir.max_path_bytes]u8 = undefined; + const dir = buf[0..try tmp.dir.realPath(std.testing.io, &buf)]; + return std.fs.path.join(gpa, &.{ dir, "t.ztrace" }); +} + +fn testEvent(kind: Kind, tid: u32, a: [6]u64) Event { + return .{ .kind = kind, .tid = tid, .a = a }; +} + +test "registers, memory and strings are 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" }); + const path = try testPath(gpa, &tmp); 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"); + var rec = try Recorder.create(gpa, std.testing.io, path); + // Batches of two, so moments straddle transactions. + rec.batch = 2; + try rec.emit(testEvent(.string, 0, .{ 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); + try rec.emit(testEvent(.mem_write, 7, .{ 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.emit(testEvent(.step, 7, .{ regs.rip, 0, 0, 0, 0, 0 }), std.mem.asBytes(®s)); } try rec.close(); - var trace = try Trace.open(gpa, io, path); + var trace = try Trace.open(gpa, std.testing.io, path); defer trace.close(); try std.testing.expectEqual(@as(u64, 3), trace.len); @@ -314,6 +603,9 @@ test "a recording is read back moment by moment" { 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)).?); + const tids = try last.threads(gpa); + defer gpa.free(tids); + try std.testing.expectEqualSlices(u32, &.{7}, tids); var events = try last.events(gpa); defer events.deinit(gpa); @@ -322,4 +614,85 @@ test "a recording is read back moment by moment" { 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); + try std.testing.expectEqual(@as(?u64, 1), try trace.momentOf(4)); + try std.testing.expectEqual(@as(?u64, null), try trace.momentOf(8)); +} + +test "the heap, the call stack, variables, lines and mappings follow their events" { + const gpa = std.testing.allocator; + var tmp = std.testing.tmpDir(.{}); + defer tmp.cleanup(); + const path = try testPath(gpa, &tmp); + defer gpa.free(path); + + var rec = try Recorder.create(gpa, std.testing.io, path); + rec.batch = 3; + const mark = testEvent(.mark, 1, @splat(0)); + // Moment 0: a mapping, a global, two allocations, a call with a local. + try rec.emit(testEvent(.map, 1, .{ 0x400000, 0x2000, 5, 0, 0, 0 }), "/bin/prog"); + try rec.emit(testEvent(.variable, 1, .{ 0x601000, 4, 1, 2, 0, 0 }), ""); + try rec.emit(testEvent(.alloc, 1, .{ 0x1000, 16, 0x400123, 0, 0, 0 }), ""); + try rec.emit(testEvent(.alloc, 1, .{ 0x2000, 32, 0x400456, 0, 0, 0 }), ""); + try rec.emit(testEvent(.call, 1, .{ 0x400500, 0x400130, 0x7ffe0000, 0, 0, 0 }), ""); + try rec.emit(testEvent(.variable, 1, .{ 0x7ffdfff8, 8, 3, 4, 0, 0 }), ""); + try rec.emit(testEvent(.line, 1, .{ 9, 12, 5, 0, 0, 0 }), ""); + // Moment 1: a nested call, a free. + try rec.emit(testEvent(.call, 1, .{ 0x400600, 0x400510, 0x7ffdffe0, 0, 0, 0 }), ""); + try rec.emit(testEvent(.free, 1, .{ 0x1000, 0, 0, 0, 0, 0 }), ""); + try rec.emit(mark, ""); + // Moment 2: both calls return, the mapping goes. + try rec.emit(testEvent(.ret, 1, .{ 0x400600, 0, 0, 0, 0, 0 }), ""); + try rec.emit(testEvent(.ret, 1, .{ 0x400500, 0, 0, 0, 0, 0 }), ""); + try rec.emit(testEvent(.unmap, 1, .{ 0x400000, 0x2000, 0, 0, 0, 0 }), ""); + try rec.emit(mark, ""); + try rec.close(); + + var trace = try Trace.open(gpa, std.testing.io, path); + defer trace.close(); + try std.testing.expectEqual(@as(u64, 3), trace.len); + + const m0 = try trace.moment(0); + const heap0 = try m0.heap(gpa); + defer gpa.free(heap0); + try std.testing.expectEqual(@as(usize, 2), heap0.len); + try std.testing.expectEqual(@as(u64, 32), heap0[1].size); + try std.testing.expectEqual(@as(u64, 0x2000), (try m0.allocation(0x201f)).?.ptr); + try std.testing.expect((try m0.allocation(0x2020)) == null); + try std.testing.expect((try m0.allocation(0xfff)) == null); + const stack0 = try m0.stack(gpa, 1); + defer gpa.free(stack0); + try std.testing.expectEqual(@as(usize, 1), stack0.len); + try std.testing.expectEqual(@as(u64, 0x400500), stack0[0].function); + try std.testing.expectEqual(Line{ .file = 9, .line = 12, .column = 5 }, (try m0.line(1)).?); + const vars0 = try m0.variables(gpa); + defer gpa.free(vars0); + try std.testing.expectEqual(@as(usize, 2), vars0.len); + try std.testing.expectEqual(@as(u32, 0), vars0[0].depth); + try std.testing.expectEqual(@as(u32, 1), vars0[1].depth); + var path_buf: [64]u8 = undefined; + var mapped: []const u8 = ""; + try std.testing.expectEqual(@as(u64, 0x400000), (try m0.mapping(0x401fff, &mapped, &path_buf)).?.addr); + try std.testing.expectEqualStrings("/bin/prog", mapped); + try std.testing.expect((try m0.mapping(0x402000, null, &path_buf)) == null); + + const m1 = try trace.moment(1); + const stack1 = try m1.stack(gpa, 1); + defer gpa.free(stack1); + try std.testing.expectEqual(@as(usize, 2), stack1.len); + try std.testing.expect((try m1.allocation(0x1000)) == null); + + // Returning took the local with its frame; the global stays. + const m2 = try trace.moment(2); + const stack2 = try m2.stack(gpa, 1); + defer gpa.free(stack2); + try std.testing.expectEqual(@as(usize, 0), stack2.len); + const vars2 = try m2.variables(gpa); + defer gpa.free(vars2); + try std.testing.expectEqual(@as(usize, 1), vars2.len); + try std.testing.expectEqual(@as(u64, 0x601000), vars2[0].addr); + try std.testing.expect((try m2.mapping(0x400000, null, &path_buf)) == null); + // ... and the first moment is as it was. + const again = try m0.stack(gpa, 1); + defer gpa.free(again); + try std.testing.expectEqual(@as(usize, 1), again.len); } -- cgit v1.3