summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/trace/store.zig1021
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, &regs);
+ 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(&regs));
+ 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(&regs));
}
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);
+}