diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-10 11:46:18 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-10 11:47:26 -0300 |
| commit | 5f1f95098611b077bd7e0ca27283fa0e02d1adbc (patch) | |
| tree | 59385d79fa57e94bbaa489fbef0b8c5abc88c500 /src | |
| parent | 233d9cf30b178501e3194297434791b6de35eff2 (diff) | |
| download | computeranim-5f1f95098611b077bd7e0ca27283fa0e02d1adbc.tar.gz computeranim-5f1f95098611b077bd7e0ca27283fa0e02d1adbc.zip | |
recorder: a moment is its events, state is at keyframes
Folding every event into persistent state at every moment cost 750 bytes a
step and 2 KB a scattered 8-byte write: the tree's path copied each time.
Now a moment stores its events alone, in a compact code (a flags byte,
varints, time as a difference, registers as the ones that changed), and the
state (threads, memory, heap, variables, mappings, strings) is written at a
keyframe a batch, sharing with the one before. A reader replays at most a
batch over a keyframe, and keeps four positions replayed, so playing
forward reads one moment a step.
Of a memory write the recorder keeps the spans that differ from what it
holds, so a region read again costs what changed in it. It stops at
max_bytes (1 GiB).
A step with registers: 749 bytes to 57. fib(12) by instruction, 142 000
moments: 111 MB to 8 MB, 197 000 moments/s. bench-store measures the rest.
Diffstat (limited to 'src')
| -rw-r--r-- | src/trace/store.zig | 1021 |
1 files changed, 720 insertions, 301 deletions
diff --git a/src/trace/store.zig b/src/trace/store.zig index e38ef03..8d01570 100644 --- a/src/trace/store.zig +++ b/src/trace/store.zig @@ -1,14 +1,16 @@ -//! 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. +//! 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 moment } -//! moment = map { -//! delta the events of this moment: (u32 payload length, Event, payload)* -//! count events up to and including this moment +//! root = map { +//! moments list of bytes: a moment's events, encoded (`Codec`) +//! keys list of keyframe, one a batch of moments +//! } +//! 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 a thread's registers, source line, open calls +//! 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 @@ -16,9 +18,14 @@ //! strings map id -> text //! } //! -//! The `Recorder` is a `Sink`: it takes events from any backend, folds them -//! 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. +//! 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"); @@ -29,24 +36,32 @@ const Kind = event.Kind; const WriteDB = xitdb.Database(.buffered_file, u64); const ReadDB = xitdb.Database(.file, u64); -const Key = enum(u64) { moments = 1, delta, count, threads, mem, heap, vars, maps, strings }; +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 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 }; +/// 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(value: u64) [8]u8 { +fn be(v: u64) [8]u8 { var out: [8]u8 = undefined; - std.mem.writeInt(u64, &out, value, .big); + 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. @@ -78,8 +93,240 @@ pub const Variable = extern struct { }; 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 }; +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, @@ -92,21 +339,24 @@ 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. + /// Moments a keyframe, at most: what a reader replays to reach one. A + /// crash loses the batch being gathered. batch: usize = 256, + /// 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, - 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, - /// 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 }; + /// 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 { @@ -118,22 +368,16 @@ pub const Recorder = struct { 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 }; + 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.ops.deinit(r.gpa); - r.mem.deinit(r.gpa); - r.mem_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.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); @@ -152,190 +396,152 @@ 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 { + 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(); } - pub fn emit(r: *Recorder, ev: Event, payload: []const u8) !void { - try r.delta.appendSlice(r.gpa, std.mem.asBytes(&@as(u32, @intCast(payload.len)))); - try r.delta.appendSlice(r.gpa, std.mem.asBytes(&ev)); - try r.delta.appendSlice(r.gpa, payload); + 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; - - 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(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(); } - 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 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.* = .{}; - 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, {}); + /// 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; } - at += n; - rest = rest[n..]; + 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 { - for (r.mem_dirty.keys()) |index| try r.op(.chunk, .{index}, std.mem.asBytes(r.mem.getPtr(index).?)); - r.mem_dirty.clearRetainingCapacity(); - try r.op(.delta, .{r.count}, r.delta.items); + try r.blobs.appendSlice(r.gpa, r.delta.items); + try r.ends.append(r.gpa, r.blobs.items.len); 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(); + if (r.ends.items.len >= r.batch or r.blobs.items.len >= 1 << 20) try r.flush(); } - /// Writes the moments ended so far: one transaction. + /// 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.pending == 0) return; - try r.db.runContext(Batch{ .ops = r.ops.items }); - r.ops.clearRetainingCapacity(); - r.pending = 0; + 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 { - 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); + r: *Recorder, - 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]; - } + const Map = WriteDB.HashMap(.read_write); + const Sorted = WriteDB.SortedMap(.read_write); + const List = WriteDB.ArrayList(.read_write); - pub fn run(ctx: Batch, cursor: *DB.Cursor(.read_write)) !void { - var b = ctx; + 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))); - 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() }), - }; + 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. +/// A recording, read. Any moment, in any order; cheapest in order. pub const Trace = struct { gpa: std.mem.Allocator, io: std.Io, @@ -343,36 +549,72 @@ pub const Trace = struct { 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 }; - if (try t.list()) |moments| t.len = try moments.count(); + + 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); } - 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 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) }; + if (index >= t.len) return error.NoSuchMoment; + return .{ .index = index, .trace = t }; } /// The moment that holds event number `n` (from 1): the first whose @@ -382,153 +624,265 @@ pub const Trace = struct { 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; + 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, - map: Trace.Map, + trace: *const Trace, - 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(); + fn state(m: Moment) !*State { + return &(try m.trace.at(m.index)).state; } - fn value(comptime T: type, cursor: ReadDB.Cursor(.read_only)) !T { - var out: T = undefined; - _ = try cursor.readBytes(std.mem.asBytes(&out)); - return out; + /// 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 { - 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); + return gpa.dupe(u32, (try m.state()).threads.keys()); } pub fn regs(m: Moment, tid: u32) !?Regs { - return try value(Regs, (try m.map.getCursor(threadKey(tid, .regs))) orelse return null); + return if ((try m.state()).threads.get(tid)) |t| t.regs else null; } pub fn line(m: Moment, tid: u32) !?Line { - return try value(Line, (try m.map.getCursor(threadKey(tid, .line))) orelse return null); + 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 { - 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); + 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 { - @memset(buf, 0); - if (known) |k| @memset(k, false); - const mem = try Sorted.init((try m.map.getCursor(key(.mem))) orelse return); + 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); - 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; - }; - } + 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(m: Moment, comptime T: type, gpa: std.mem.Allocator, which: Key) ![]T { + 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 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)); + 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 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 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 { - return m.sorted(Allocation, gpa, .heap); + 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 a = (try m.floor(Allocation, .heap, addr)) orelse return null; + 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 { - return m.sorted(Variable, gpa, .vars); + 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 { - return m.sorted(Mapping, gpa, .maps); + 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). + /// when anonymous), copied into `buf`. 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; + 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, bytes.len - @sizeOf(Mapping)); - @memcpy(buf[0..n], bytes[@sizeOf(Mapping)..][0..n]); + const n = @min(buf.len, found.path.len); + @memcpy(buf[0..n], found.path[0..n]); p.* = buf[0..n]; } - return found; + return found.mapping; } pub fn string(m: Moment, id: u64, buf: []u8) !?[]const u8 { - 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); + 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 { - const cursor = (try m.map.getCursor(key(.delta))).?; - return .{ .bytes = try cursor.readBytesAlloc(gpa, null) }; + return .{ .bytes = try gpa.dupe(u8, (try m.trace.at(m.index)).events.items) }; } }; @@ -570,15 +924,17 @@ test "registers, memory and strings are read back moment by moment" { defer gpa.free(path); var rec = try Recorder.create(gpa, std.testing.io, path); - // Batches of two, so moments straddle transactions. + // 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 }; - try rec.emit(testEvent(.step, 7, .{ regs.rip, 0, 0, 0, 0, 0 }), std.mem.asBytes(®s)); + 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(); @@ -586,20 +942,14 @@ test "registers, memory and strings are read back moment by moment" { 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); + // 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 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.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)).?); @@ -607,12 +957,26 @@ test "registers, memory and strings are read back moment by moment" { defer gpa.free(tids); try std.testing.expectEqualSlices(u32, &.{7}, tids); - var events = try last.events(gpa); + 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); - try std.testing.expectEqual(Kind.mem_write, events.next().?.ev.kind); + 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, 0x1002), step.ev.a[0]); - try std.testing.expectEqual(@sizeOf(Regs), step.payload.len); + 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)); @@ -626,7 +990,8 @@ test "the heap, the call stack, variables, lines and mappings follow their event defer gpa.free(path); var rec = try Recorder.create(gpa, std.testing.io, path); - rec.batch = 3; + // 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"); @@ -640,8 +1005,11 @@ test "the heap, the call stack, variables, lines and mappings follow their event 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. + // 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, ""); @@ -649,7 +1017,7 @@ test "the heap, the call stack, variables, lines and mappings follow their event var trace = try Trace.open(gpa, std.testing.io, path); defer trace.close(); - try std.testing.expectEqual(@as(u64, 3), trace.len); + try std.testing.expectEqual(@as(u64, 4), trace.len); const m0 = try trace.moment(0); const heap0 = try m0.heap(gpa); @@ -681,18 +1049,69 @@ test "the heap, the call stack, variables, lines and mappings follow their event 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. + // 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, 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); + 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); +} |
