//! A recording on disk, in xitdb, kept small: what a moment stores is its //! events alone, and the state of the program is stored only now and then. //! //! root = map { //! moments list of bytes: a moment's events, encoded (`Codec`) //! keys list of keyframe, one a batch of moments (4096) //! } //! keyframe = map { //! moment the last moment it holds //! count events up to and including that moment //! threads the set of tids seen //! tid, regs / line / stack / declared a thread's registers, source //! line, open calls and the variables declared in them //! 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 //! } //! //! A keyframe shares what did not change with the one before, so its cost //! is what changed since, once, however often it changed. The state at any //! moment is the keyframe before it with the moments since replayed over //! it: a batch at most. Time travel is still an index. //! //! The `Recorder` is a `Sink`: it takes events from any backend, ends a //! moment at the kinds in `cut`, and stores of a memory write only the //! bytes that differ from what it already holds. 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) { moments = 1, keys, moment, count, threads, mem, heap, vars, maps, strings }; fn key(k: Key) u64 { return @intFromEnum(k); } /// A thread's fields sit in the keyframe's own map, under the tid and a low /// nibble no `Key` has. const Field = enum(u64) { regs = 11, line, stack, declared }; fn threadKey(tid: u64, f: Field) u64 { return tid << 4 | @intFromEnum(f); } fn be(v: u64) [8]u8 { var out: [8]u8 = undefined; std.mem.writeInt(u64, &out, v, .big); return out; } /// The registers as the 27 words they are. fn words(regs: anytype) switch (@TypeOf(regs)) { *Regs => *[27]u64, else => *const [27]u64, } { return @ptrCast(regs); } 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), }; /// 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 }; const max_path = std.Io.Dir.max_path_bytes; const MapEntry = struct { mapping: Mapping, path: []const u8 }; /// A frame as stored: with where its variables begin in the thread's `declared`. const StoredFrame = extern struct { frame: Frame, declared: u64 }; const Thread = struct { regs: ?Regs = null, line: ?Line = null, stack: std.ArrayList(StoredFrame) = .empty, /// The addresses of the variables declared in open calls. declared: std.ArrayList(u64) = .empty, /// Changed since the last keyframe. dirty: bool = true, }; /// Entries changed since the keyframe underneath: null for one removed. fn Over(comptime T: type) type { return std.AutoArrayHashMapUnmanaged(u64, ?T); } /// The program's state, as the events since a keyframe made it. The /// recorder's holds all of memory and the threads; a reader's is laid over /// the keyframe it started from (`base`). const State = struct { /// Owns paths and strings, until the next keyframe (recorder) or seek (reader). arena: std.heap.ArenaAllocator, base: ?Trace.Map = null, threads: std.AutoArrayHashMapUnmanaged(u32, Thread) = .empty, mem: std.AutoHashMapUnmanaged(u64, Chunk) = .empty, /// The recorder's: chunks to write at the next keyframe. mem_dirty: ?std.AutoArrayHashMapUnmanaged(u64, void) = null, heap: Over(Allocation) = .empty, vars: Over(Variable) = .empty, maps: Over(MapEntry) = .empty, strings: std.AutoArrayHashMapUnmanaged(u64, []const u8) = .empty, count: u64 = 0, /// What the codec measures the next event against. ts: u64 = 0, tid: u32 = 0, fn deinit(s: *State, gpa: std.mem.Allocator) void { s.clear(gpa); s.threads.deinit(gpa); s.mem.deinit(gpa); if (s.mem_dirty) |*d| d.deinit(gpa); s.heap.deinit(gpa); s.vars.deinit(gpa); s.maps.deinit(gpa); s.strings.deinit(gpa); s.arena.deinit(); } /// Back to nothing known, keeping the memory it holds. fn clear(s: *State, gpa: std.mem.Allocator) void { for (s.threads.values()) |*t| { t.stack.deinit(gpa); t.declared.deinit(gpa); } s.threads.clearRetainingCapacity(); s.mem.clearRetainingCapacity(); s.heap.clearRetainingCapacity(); s.vars.clearRetainingCapacity(); s.maps.clearRetainingCapacity(); s.strings.clearRetainingCapacity(); _ = s.arena.reset(.retain_capacity); s.count = 0; s.ts = 0; s.tid = 0; } fn thread(s: *State, gpa: std.mem.Allocator, tid: u32) !*Thread { const gop = try s.threads.getOrPut(gpa, tid); if (!gop.found_existing) gop.value_ptr.* = .{}; return gop.value_ptr; } /// A chunk to change: as the keyframe underneath has it, when it does. fn chunk(s: *State, gpa: std.mem.Allocator, index: u64) !*Chunk { const gop = try s.mem.getOrPut(gpa, index); if (!gop.found_existing) gop.value_ptr.* = (try baseChunk(s.base, index)) orelse .{}; return gop.value_ptr; } fn baseChunk(base: ?Trace.Map, index: u64) !?Chunk { const map = base orelse return null; const mem = try Trace.Sorted.init((try map.getCursor(key(.mem))) orelse return null); return try value(Chunk, (try mem.getCursor(&be(index))) orelse return null); } fn write(s: *State, gpa: std.mem.Allocator, 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 c = try s.chunk(gpa, index); @memcpy(c.bytes[off..][0..n], rest[0..n]); c.known |= (if (n == 64) ~@as(u64, 0) else (@as(u64, 1) << @intCast(n)) - 1) << @intCast(off); if (s.mem_dirty) |*dirty| try dirty.put(gpa, index, {}); at += n; rest = rest[n..]; } } /// One event's effect on the state. fn apply(s: *State, gpa: std.mem.Allocator, ev: Event, payload: []const u8) !void { s.count += 1; const a = ev.a; // Tid 0 is no thread: a string defined before any ran. const t: ?*Thread = if (ev.tid != 0) try s.thread(gpa, ev.tid) else null; switch (ev.kind) { .mem_write => return s.write(gpa, a[0], payload), .string => return s.strings.put(gpa, a[0], try s.arena.allocator().dupe(u8, payload)), .alloc => try s.heap.put(gpa, a[0], .{ .ptr = a[0], .size = a[1], .pc = a[2], .born = s.count }), // Freeing what was never seen allocated removes nothing. .free => try s.heap.put(gpa, a[0], null), .map => try s.maps.put(gpa, a[0], .{ .mapping = .{ .addr = a[0], .len = a[1], .prot = a[2], .offset = a[3] }, .path = try s.arena.allocator().dupe(u8, payload[0..@min(payload.len, max_path)]), }), .unmap => try s.maps.put(gpa, a[0], null), else => {}, } const th = t orelse return; switch (ev.kind) { .line => th.line = .{ .file = a[0], .line = @truncate(a[1]), .column = @truncate(a[2]) }, .call => try th.stack.append(gpa, .{ .frame = .{ .function = a[0], .site = a[1], .sp = a[2] }, .declared = th.declared.items.len }), // A return with no call recorded (tracing began inside it) pops nothing. .ret => if (th.stack.pop()) |frame| { for (th.declared.items[@intCast(frame.declared)..]) |addr| try s.vars.put(gpa, addr, null); th.declared.shrinkRetainingCapacity(@intCast(frame.declared)); }, .variable => { if (th.stack.items.len > 0) try th.declared.append(gpa, a[0]); try s.vars.put(gpa, a[0], .{ .addr = a[0], .size = a[1], .name = a[2], .type = a[3], .tid = ev.tid, .depth = @intCast(th.stack.items.len) }); }, else => {}, } // Any event may carry its thread's registers. if (Codec.isRegs(ev, payload)) th.regs = std.mem.bytesToValue(Regs, payload); th.dirty = true; } }; fn value(comptime T: type, cursor: ReadDB.Cursor(.read_only)) !T { // A mapping's value has its path after it: read what the type takes. var buf: [@sizeOf(Mapping) + max_path]u8 = undefined; const bytes = try cursor.readBytes(buf[0..if (T == Mapping) buf.len else @sizeOf(T)]); return std.mem.bytesToValue(T, bytes[0..@sizeOf(T)]); } /// Events as a moment stores them: a kind, a byte saying which fields are /// there, the time since the event before, and what is not zero, each a /// varint; registers as the ones that differ from the thread's last. const Codec = struct { fn put(list: *std.ArrayList(u8), gpa: std.mem.Allocator, v: u64) !void { var x = v; while (x >= 0x80) : (x >>= 7) try list.append(gpa, @as(u8, @truncate(x)) | 0x80); try list.append(gpa, @truncate(x)); } fn take(bytes: []const u8, at: *usize) u64 { var v: u64 = 0; var shift: u6 = 0; while (true) { const b = bytes[at.*]; at.* += 1; v |= @as(u64, b & 0x7f) << shift; if (b < 0x80) return v; shift +%= 7; } } fn isRegs(ev: Event, payload: []const u8) bool { return payload.len == @sizeOf(Regs) and ev.kind != .mem_write and ev.kind != .string; } fn encode(list: *std.ArrayList(u8), gpa: std.mem.Allocator, s: *State, ev: Event, payload: []const u8) !void { var flags: u8 = 0; for (ev.a, 0..) |v, i| flags |= @as(u8, @intFromBool(v != 0)) << @intCast(i); if (ev.aux != 0) flags |= 0x40; if (ev.tid != s.tid) flags |= 0x80; try list.appendSlice(gpa, &.{ @intCast(@intFromEnum(ev.kind)), flags }); const dt: i64 = @bitCast(ev.ts -% s.ts); try put(list, gpa, @bitCast((dt << 1) ^ (dt >> 63))); s.ts = ev.ts; if (ev.tid != s.tid) try put(list, gpa, ev.tid); s.tid = ev.tid; if (ev.aux != 0) try put(list, gpa, ev.aux); for (ev.a) |v| if (v != 0) try put(list, gpa, v); if (!isRegs(ev, payload)) { try put(list, gpa, payload.len << 1); return list.appendSlice(gpa, payload); } const now = std.mem.bytesToValue(Regs, payload); const before: Regs = if (s.threads.get(ev.tid)) |t| t.regs orelse .{} else .{}; var mask: u64 = 0; for (words(&now), words(&before), 0..) |n, b, i| mask |= @as(u64, @intFromBool(n != b)) << @intCast(i); try put(list, gpa, mask << 1 | 1); for (words(&now), 0..) |n, i| { if (mask >> @intCast(i) & 1 != 0) try list.appendSlice(gpa, std.mem.asBytes(&n)); } } /// The next event of `bytes`; its payload is in `bytes` or in `regs`. fn decode(bytes: []const u8, at: *usize, s: *State, regs: *Regs) struct { Event, []const u8 } { const kind: Kind = @enumFromInt(bytes[at.*]); const flags = bytes[at.* + 1]; at.* += 2; const zz = take(bytes, at); s.ts +%= (zz >> 1) ^ (0 -% (zz & 1)); if (flags & 0x80 != 0) s.tid = @intCast(take(bytes, at)); var ev: Event = .{ .ts = s.ts, .tid = s.tid, .kind = kind }; if (flags & 0x40 != 0) ev.aux = @intCast(take(bytes, at)); for (&ev.a, 0..) |*v, i| { if (flags >> @intCast(i) & 1 != 0) v.* = take(bytes, at); } const tag = take(bytes, at); if (tag & 1 == 0) { const len: usize = @intCast(tag >> 1); defer at.* += len; return .{ ev, bytes[at.*..][0..len] }; } regs.* = if (s.threads.get(ev.tid)) |t| t.regs orelse .{} else .{}; for (words(regs), 0..) |*n, i| { if (tag >> @intCast(i + 1) & 1 == 0) continue; n.* = std.mem.readInt(u64, bytes[at.*..][0..8], .little); at.* += 8; } return .{ ev, std.mem.asBytes(regs) }; } }; 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, /// Moments a keyframe, at most: what a reader replays to reach one (a /// millisecond, measured), and what a crash loses. Fewer would be seeked /// to faster and cost more: at 256 the keyframes were half of a /// recording of Lua. batch: usize = 4096, /// The file may grow this large; past it `emit` is `error.RecordingFull`. /// A recording is meant to be megabytes: reaching this means too much is /// being recorded (every instruction of a long run, whole buffers). max_bytes: u64 = 1 << 30, /// The moment being gathered, encoded. delta: std.ArrayList(u8) = .empty, /// Events taken. count: u64 = 0, /// Moments ended, written or not. moments: u64 = 0, /// The moments ended and not yet written, end to end, and where each ends. blobs: std.ArrayList(u8) = .empty, ends: std.ArrayList(usize) = .empty, state: State, full: bool = false, /// 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, .state = .{ .arena = .init(gpa), .mem_dirty = .empty } }; } /// 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.blobs.deinit(r.gpa); r.ends.deinit(r.gpa); r.state.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(); } 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 { if (r.full) return error.RecordingFull; if (ev.kind == .mem_write and payload.len > 0) try r.memWrite(ev, payload) else try r.one(ev, payload); if (r.cut & ev.kind.bit() != 0 or r.delta.items.len >= r.max_delta) try r.commit(); } fn one(r: *Recorder, ev: Event, payload: []const u8) !void { try Codec.encode(&r.delta, r.gpa, &r.state, ev, payload); try r.state.apply(r.gpa, ev, payload); r.count += 1; } /// A memory write, as the spans of it that differ from what is already /// recorded there: a region read again costs what changed in it. With /// nothing changed the event stays, without bytes. fn memWrite(r: *Recorder, ev: Event, payload: []const u8) !void { // Spans closer than this are one: an event's own bytes cost about as much. const gap = 24; var from: ?usize = null; var to: usize = 0; var any = false; for (payload, 0..) |byte, i| { const at = ev.a[0] + i; const off: u6 = @intCast(at % chunk_bytes); if (r.state.mem.getPtr(at / chunk_bytes)) |c| { if (c.known >> off & 1 != 0 and c.bytes[off] == byte) continue; } if (from != null and i - to > gap) { try r.span(ev, payload, from.?, to); from = null; } if (from == null) from = i; to = i + 1; any = true; } if (from) |f| try r.span(ev, payload, f, to); if (!any) try r.one(ev, ""); } fn span(r: *Recorder, ev: Event, payload: []const u8, from: usize, to: usize) !void { var part = ev; part.a[0] += from; part.a[1] = to - from; try r.one(part, payload[from..to]); } /// Ends the moment. It reaches the file with its batch. pub fn commit(r: *Recorder) !void { try r.blobs.appendSlice(r.gpa, r.delta.items); try r.ends.append(r.gpa, r.blobs.items.len); r.delta.clearRetainingCapacity(); r.moments += 1; if (r.ends.items.len >= r.batch or r.blobs.items.len >= 1 << 20) try r.flush(); } /// Writes the moments ended so far and a keyframe after them: one /// transaction. Call it before reading the file while still recording. pub fn flush(r: *Recorder) !void { if (r.ends.items.len == 0) return; try r.db.runContext(Batch{ .r = r }); r.blobs.clearRetainingCapacity(); r.ends.clearRetainingCapacity(); const s = &r.state; for (s.threads.values()) |*t| t.dirty = false; s.mem_dirty.?.clearRetainingCapacity(); s.heap.clearRetainingCapacity(); s.vars.clearRetainingCapacity(); s.maps.clearRetainingCapacity(); s.strings.clearRetainingCapacity(); _ = s.arena.reset(.retain_capacity); // The codec starts over where a reader starts replaying. s.ts = 0; s.tid = 0; if (try r.db.core.length() >= r.max_bytes) r.full = true; } const Batch = struct { r: *Recorder, const Map = WriteDB.HashMap(.read_write); const Sorted = WriteDB.SortedMap(.read_write); const List = WriteDB.ArrayList(.read_write); pub fn run(ctx: Batch, cursor: *WriteDB.Cursor(.read_write)) !void { const r = ctx.r; const s = &r.state; const root = try Map.init(cursor.*); const moments = try List.init(try root.putCursor(key(.moments))); var from: usize = 0; for (r.ends.items) |end| { try moments.append(.{ .bytes = r.blobs.items[from..end] }); from = end; } // The keyframe starts as the last one, which is immutable from // here: what changed since it copies, the rest it shares. const keys = try List.init(try root.putCursor(key(.keys))); try keys.append(.{ .slot = try keys.getSlot(-1) }); var at = try keys.putCursor(-1); try at.freeze(); const k = try Map.init(at); try k.put(key(.moment), .{ .uint = r.moments - 1 }); try k.put(key(.count), .{ .uint = r.count }); for (s.threads.keys(), s.threads.values()) |tid, *t| { if (!t.dirty) continue; try (try Map.init(try k.putCursor(key(.threads)))).put(tid, .{ .uint = 1 }); if (t.regs) |*regs| try k.put(threadKey(tid, .regs), .{ .bytes = std.mem.asBytes(regs) }); if (t.line) |*line| try k.put(threadKey(tid, .line), .{ .bytes = std.mem.asBytes(line) }); try k.put(threadKey(tid, .stack), .{ .bytes = std.mem.sliceAsBytes(t.stack.items) }); try k.put(threadKey(tid, .declared), .{ .bytes = std.mem.sliceAsBytes(t.declared.items) }); } if (s.mem_dirty.?.count() > 0) { const mem = try Sorted.init(try k.putCursor(key(.mem))); for (s.mem_dirty.?.keys()) |index| try mem.put(&be(index), .{ .bytes = std.mem.asBytes(s.mem.getPtr(index).?) }); } inline for (.{ .{ &s.heap, Key.heap }, .{ &s.vars, Key.vars } }) |pair| { if (pair[0].count() > 0) { const map = try Sorted.init(try k.putCursor(key(pair[1]))); for (pair[0].keys(), pair[0].values()) |addr, *entry| { if (entry.*) |*live| try map.put(&be(addr), .{ .bytes = std.mem.asBytes(live) }) else _ = try map.remove(&be(addr)); } } } if (s.maps.count() > 0) { const map = try Sorted.init(try k.putCursor(key(.maps))); for (s.maps.keys(), s.maps.values()) |addr, entry| { const live = entry orelse { _ = try map.remove(&be(addr)); continue; }; var buf: [@sizeOf(Mapping) + max_path]u8 = undefined; @memcpy(buf[0..@sizeOf(Mapping)], std.mem.asBytes(&live.mapping)); @memcpy(buf[@sizeOf(Mapping)..][0..live.path.len], live.path); try map.put(&be(addr), .{ .bytes = buf[0 .. @sizeOf(Mapping) + live.path.len] }); } } if (s.strings.count() > 0) { const strings = try Map.init(try k.putCursor(key(.strings))); for (s.strings.keys(), s.strings.values()) |id, text| try strings.put(id, .{ .bytes = text }); } } }; }; /// A recording, read. Any moment, in any order; cheapest in order. pub const Trace = struct { gpa: std.mem.Allocator, io: std.Io, file: std.Io.File, db: *ReadDB, /// The number of moments. len: u64, /// The last moment of each keyframe. key_moments: []u64, cache: *Cache, const Map = ReadDB.HashMap(.read_only); const Sorted = ReadDB.SortedMap(.read_only); const List = ReadDB.ArrayList(.read_only); /// A few positions in the recording kept replayed: the moment an /// animation shows, the one before it, somewhere a viewer jumped from. const Cache = struct { slots: [4]Slot, tick: u64 = 0, }; const Slot = struct { state: State, /// The moment the state is at, once it is at one. index: ?u64 = null, /// The keyframe under the state, null for the recording's start. base: ?usize = null, /// The next moment to replay. next: u64 = 0, /// The events of the moment at `index`, as `Events` reads them. events: std.ArrayList(u8) = .empty, used: u64 = 0, }; 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 }); var t: Trace = .{ .gpa = gpa, .io = io, .file = file, .db = db, .len = 0, .key_moments = &.{}, .cache = undefined }; const root = try Map.init(db.rootCursor().readOnly()); if (try root.getCursor(key(.moments))) |cursor| t.len = try (try List.init(cursor)).count(); var key_moments: std.ArrayList(u64) = .empty; errdefer key_moments.deinit(gpa); if (try root.getCursor(key(.keys))) |cursor| { var it = try (try List.init(cursor)).iterator(); while (try it.next()) |k| try key_moments.append(gpa, try (try (try Map.init(k)).getCursor(key(.moment))).?.readUint()); } t.key_moments = try key_moments.toOwnedSlice(gpa); errdefer gpa.free(t.key_moments); t.cache = try gpa.create(Cache); t.cache.* = .{ .slots = undefined }; for (&t.cache.slots) |*slot| slot.* = .{ .state = .{ .arena = .init(gpa) } }; return t; } pub fn close(t: *Trace) void { for (&t.cache.slots) |*slot| { slot.state.deinit(t.gpa); slot.events.deinit(t.gpa); } t.gpa.destroy(t.cache); t.gpa.free(t.key_moments); t.file.close(t.io); t.gpa.destroy(t.db); } pub fn moment(t: *const Trace, index: u64) !Moment { if (index >= t.len) return error.NoSuchMoment; return .{ .index = index, .trace = t }; } /// 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 t.at(mid)).state.count < n) lo = mid + 1 else hi = mid; } return if (lo < t.len) lo else null; } fn list(t: *const Trace, which: Key) !List { const root = try Map.init(t.db.rootCursor().readOnly()); return List.init((try root.getCursor(key(which))).?); } /// The state at a moment: a slot already there, or the nearest one /// behind it on the same keyframe replayed forward, or a keyframe /// replayed from. fn at(t: *const Trace, index: u64) !*Slot { const c = t.cache; c.tick += 1; for (&c.slots) |*slot| if (slot.index == index) { slot.used = c.tick; return slot; }; // The keyframe under this moment: the last that ends before it. const after = std.sort.lowerBound(u64, t.key_moments, index, struct { fn order(want: u64, have: u64) std.math.Order { return std.math.order(want, have); } }.order); const base: ?usize = if (after == 0) null else after - 1; var pick: ?*Slot = null; for (&c.slots) |*slot| { const have = slot.index orelse continue; if (slot.base == base and have < index and (pick == null or have > pick.?.index.?)) pick = slot; } const slot = pick orelse blk: { var oldest = &c.slots[0]; for (&c.slots) |*each| if (each.used < oldest.used) { oldest = each; }; try t.reset(oldest, base); break :blk oldest; }; slot.index = null; var moments = try (try t.list(.moments)).iteratorFrom(@intCast(slot.next)); while (slot.next <= index) : (slot.next += 1) { const bytes = try (try moments.next()).?.readBytesAlloc(t.gpa, null); defer t.gpa.free(bytes); slot.events.clearRetainingCapacity(); var pos: usize = 0; while (pos < bytes.len) { var regs: Regs = undefined; const ev, const payload = Codec.decode(bytes, &pos, &slot.state, ®s); try slot.events.appendSlice(t.gpa, std.mem.asBytes(&@as(u32, @intCast(payload.len)))); try slot.events.appendSlice(t.gpa, std.mem.asBytes(&ev)); try slot.events.appendSlice(t.gpa, payload); try slot.state.apply(t.gpa, ev, payload); } } slot.index = index; slot.used = c.tick; return slot; } /// A slot's state as keyframe `base` has it: the threads loaded, the /// rest read through to the keyframe when asked for. fn reset(t: *const Trace, slot: *Slot, base: ?usize) !void { const s = &slot.state; s.clear(t.gpa); slot.index = null; slot.base = base; slot.next = 0; s.base = null; const j = base orelse return; const k = try Map.init((try (try t.list(.keys)).getCursor(@intCast(j))).?); s.base = k; s.count = try (try k.getCursor(key(.count))).?.readUint(); slot.next = t.key_moments[j] + 1; const threads = (try k.getCursor(key(.threads))) orelse return; var it = try threads.iterator(); while (try it.next()) |entry| { const tid: u32 = @intCast((try entry.readKeyValuePair()).hash); const th = try s.thread(t.gpa, tid); if (try k.getCursor(threadKey(tid, .regs))) |cursor| th.regs = try value(Regs, cursor); if (try k.getCursor(threadKey(tid, .line))) |cursor| th.line = try value(Line, cursor); inline for (.{ .{ &th.stack, StoredFrame, Field.stack }, .{ &th.declared, u64, Field.declared } }) |part| { const bytes = try (try k.getCursor(threadKey(tid, part[2]))).?.readBytesAlloc(t.gpa, null); defer t.gpa.free(bytes); try part[0].resize(t.gpa, bytes.len / @sizeOf(part[1])); @memcpy(std.mem.sliceAsBytes(part[0].items), bytes); } } } }; /// The state of the program at one moment of a recording. pub const Moment = struct { index: u64, trace: *const Trace, const Sorted = Trace.Sorted; fn state(m: Moment) !*State { return &(try m.trace.at(m.index)).state; } /// Events up to and including this moment. pub fn count(m: Moment) !u64 { return (try m.state()).count; } /// The threads seen so far, in no order. pub fn threads(m: Moment, gpa: std.mem.Allocator) ![]u32 { return gpa.dupe(u32, (try m.state()).threads.keys()); } pub fn regs(m: Moment, tid: u32) !?Regs { return if ((try m.state()).threads.get(tid)) |t| t.regs else null; } pub fn line(m: Moment, tid: u32) !?Line { return if ((try m.state()).threads.get(tid)) |t| t.line else null; } /// The calls a thread is inside, outermost first. pub fn stack(m: Moment, gpa: std.mem.Allocator, tid: u32) ![]Frame { const t = (try m.state()).threads.get(tid) orelse return &.{}; const out = try gpa.alloc(Frame, t.stack.items.len); for (out, t.stack.items) |*frame, stored| frame.* = stored.frame; 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 { const s = try m.state(); 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); const chunk: Chunk = s.mem.get(at / chunk_bytes) orelse (try State.baseChunk(s.base, at / chunk_bytes)) orelse .{}; @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; } } fn sorted(s: *const State, which: Key) !?Sorted { const base = s.base orelse return null; return try Sorted.init((try base.getCursor(key(which))) orelse return null); } fn addrOf(entry: anytype) u64 { return if (@TypeOf(entry) == MapEntry) entry.mapping.addr else std.mem.bytesToValue(u64, std.mem.asBytes(&entry)[0..8]); } /// A keyframe's entries with the changes since laid over them, by address. fn merged(comptime T: type, gpa: std.mem.Allocator, s: *const State, which: Key, over: anytype) ![]T { var out: std.ArrayList(T) = .empty; errdefer out.deinit(gpa); if (try sorted(s, which)) |base| { var it = try base.iterator(); while (try it.next()) |entry| { const have = try value(T, (try entry.readKeyValuePair()).value_cursor); if (!over.contains(addrOf(have))) try out.append(gpa, have); } } for (over.values()) |entry| { if (entry) |live| try out.append(gpa, if (@TypeOf(live) == MapEntry) live.mapping else live); } std.mem.sort(T, out.items, {}, struct { fn less(_: void, a: T, b: T) bool { return addrOf(a) < addrOf(b); } }.less); return out.toOwnedSlice(gpa); } /// The entry at the greatest address not above `addr`: of the changes, /// or of the keyframe where no change hides it. fn floor(comptime T: type, s: *State, which: Key, over: anytype, addr: u64) !?T { var best: ?T = null; for (over.keys(), over.values()) |at, entry| { const live = entry orelse continue; if (at <= addr and (best == null or at > addrOf(best.?))) best = live; } const base = (try sorted(s, which)) orelse return best; var below = try base.rank(&be(addr +| 1)); while (below > 0) { below -= 1; const cursor = (try base.getIndexKeyValuePair(@intCast(below))).?.value_cursor; const found = try value(if (T == MapEntry) Mapping else T, cursor); if (over.contains(addrOf(found))) continue; if (best != null and addrOf(best.?) > addrOf(found)) break; if (T != MapEntry) return found; var raw: [@sizeOf(Mapping) + max_path]u8 = undefined; const bytes = try cursor.readBytes(&raw); // Lent from the slot's arena: it lives until the slot moves on. return .{ .mapping = found, .path = try s.arena.allocator().dupe(u8, bytes[@sizeOf(Mapping)..]) }; } return best; } /// The live allocations, by address. pub fn heap(m: Moment, gpa: std.mem.Allocator) ![]Allocation { const s = try m.state(); return merged(Allocation, gpa, s, .heap, &s.heap); } /// The live allocation that holds `addr`. pub fn allocation(m: Moment, addr: u64) !?Allocation { const s = try m.state(); const a = (try floor(Allocation, s, .heap, &s.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 { const s = try m.state(); return merged(Variable, gpa, s, .vars, &s.vars); } /// The mapped regions, by address. pub fn mappings(m: Moment, gpa: std.mem.Allocator) ![]Mapping { const s = try m.state(); return merged(Mapping, gpa, s, .maps, &s.maps); } /// The region that holds `addr`, and the file it maps into `path` (empty /// when anonymous), copied into `buf`. pub fn mapping(m: Moment, addr: u64, path: ?*[]const u8, buf: []u8) !?Mapping { const s = try m.state(); const found = (try floor(MapEntry, s, .maps, &s.maps, addr)) orelse return null; if (addr - found.mapping.addr >= found.mapping.len) return null; if (path) |p| { const n = @min(buf.len, found.path.len); @memcpy(buf[0..n], found.path[0..n]); p.* = buf[0..n]; } return found.mapping; } pub fn string(m: Moment, id: u64, buf: []u8) !?[]const u8 { const s = try m.state(); if (s.strings.get(id)) |text| { const n = @min(buf.len, text.len); @memcpy(buf[0..n], text[0..n]); return buf[0..n]; } const base = s.base orelse return null; const all = try Trace.Map.init((try base.getCursor(key(.strings))) orelse return null); return try ((try all.getCursor(id)) orelse return null).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 { return .{ .bytes = try gpa.dupe(u8, (try m.trace.at(m.index)).events.items) }; } }; 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] }; } }; 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; 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); // Keyframes of two, so moments are read at one, after one and before any. 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(testEvent(.mem_write, 7, .{ 62 + i, 4, 0, 0, 0, 0 }), &bytes); const regs: Regs = .{ .rip = 0x1000 + i, .rax = i, .rsp = 0x7ffd_0000_0000 }; var step = testEvent(.step, 7, .{ regs.rip, 0, 0, 0, 0, 0 }); step.ts = 1000 - i; try rec.emit(step, std.mem.asBytes(®s)); } 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); // The last moment first, then back: nothing later leaks into the first. const last = try trace.moment(2); var buf: [8]u8 = undefined; var known: [8]bool = undefined; 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.expectEqual(@as(u64, 0x7ffd_0000_0000), (try last.regs(7)).?.rsp); 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); const first = try trace.moment(0); 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()); // The events come back whole: registers in full, times as given, and of // the second write only the bytes the first had not put there. var events = try (try trace.moment(1)).events(gpa); defer events.deinit(gpa); const write = events.next().?; try std.testing.expectEqual(Kind.mem_write, write.ev.kind); try std.testing.expectEqual(@as(u64, 63), write.ev.a[0]); try std.testing.expectEqualSlices(u8, &.{ 2, 2, 2, 2 }, write.payload); const step = events.next().?; try std.testing.expectEqual(@as(u64, 0x1001), step.ev.a[0]); try std.testing.expectEqual(@as(u64, 999), step.ev.ts); try std.testing.expectEqual(@as(u32, 7), step.ev.tid); try std.testing.expectEqual(Regs{ .rip = 0x1001, .rax = 1, .rsp = 0x7ffd_0000_0000 }, std.mem.bytesToValue(Regs, step.payload)); 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); // A keyframe after moments 1 and 3: each moment is read from another footing. rec.batch = 2; 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: the inner call returns, a third allocation. try rec.emit(testEvent(.ret, 1, .{ 0x400600, 0, 0, 0, 0, 0 }), ""); try rec.emit(testEvent(.alloc, 1, .{ 0x3000, 8, 0x400789, 0, 0, 0 }), ""); try rec.emit(mark, ""); // Moment 3: the outer call returns, the mapping goes. 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, 4), 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); // Moment 2 is read over the keyframe after moment 1: the free and the // mapping come from it, the new allocation and the return from the replay. const m2 = try trace.moment(2); const heap2 = try m2.heap(gpa); defer gpa.free(heap2); try std.testing.expectEqual(@as(usize, 2), heap2.len); try std.testing.expectEqual(@as(u64, 0x2000), heap2[0].ptr); try std.testing.expectEqual(@as(u64, 0x3000), heap2[1].ptr); try std.testing.expectEqual(@as(u64, 0x2000), (try m2.allocation(0x2010)).?.ptr); try std.testing.expectEqual(@as(u64, 12), (try m2.allocation(0x3007)).?.born); const stack2 = try m2.stack(gpa, 1); defer gpa.free(stack2); try std.testing.expectEqual(@as(usize, 1), stack2.len); _ = try m2.mapping(0x400000, &mapped, &path_buf); try std.testing.expectEqualStrings("/bin/prog", mapped); try std.testing.expectEqual(Line{ .file = 9, .line = 12, .column = 5 }, (try m2.line(1)).?); // Returning took the local with its frame; the global stays. const m3 = try trace.moment(3); const stack3 = try m3.stack(gpa, 1); defer gpa.free(stack3); try std.testing.expectEqual(@as(usize, 0), stack3.len); const vars3 = try m3.variables(gpa); defer gpa.free(vars3); try std.testing.expectEqual(@as(usize, 1), vars3.len); try std.testing.expectEqual(@as(u64, 0x601000), vars3[0].addr); try std.testing.expect((try m3.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); } test "a region written again costs what changed in it" { 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); var page: [4096]u8 = undefined; for (&page, 0..) |*byte, i| byte.* = @truncate(i * 7); try rec.emit(testEvent(.mem_write, 1, .{ 0x10000, page.len, 0, 0, 0, 0 }), &page); try rec.emit(testEvent(.mark, 1, @splat(0)), ""); // The same page a thousand times, one byte of it different each time. for (0..1000) |i| { page[i * 4] +%= 1; try rec.emit(testEvent(.mem_write, 1, .{ 0x10000, page.len, 0, 0, 0, 0 }), &page); try rec.emit(testEvent(.mark, 1, @splat(0)), ""); } try rec.close(); const size = (try std.Io.Dir.cwd().statFile(std.testing.io, path, .{})).size; try std.testing.expect(size < 1000 * 200); var trace = try Trace.open(gpa, std.testing.io, path); defer trace.close(); var events = try (try trace.moment(500)).events(gpa); defer events.deinit(gpa); const write = events.next().?; try std.testing.expectEqual(@as(u64, 0x10000 + 499 * 4), write.ev.a[0]); try std.testing.expectEqual(@as(usize, 1), write.payload.len); var back: [4096]u8 = undefined; try (try trace.moment(1000)).read(0x10000, &back, null); try std.testing.expectEqualSlices(u8, &page, &back); }