//! A recording, open for a scene: the trace, the thread the components //! show, and an index made once by reading every moment in order (calls as //! a tree, syscalls, marks, allocations, the source line after each moment, //! which registers and bytes each moment changed, every string). Components //! read the program's state through `moment`; scenes find where to go with //! `next` and the functions after it. const std = @import("std"); const zt = @import("ztrace"); const pardes = @import("pardes-syntax"); pub const types = @import("ztrace-types"); const store = zt.store; const Recording = @This(); pub const Moment = store.Moment; pub const Variable = store.Variable; /// One call, from the `call` event to its `ret`. pub const Call = struct { /// A string id: `name(function)`. function: u64, parent: ?u32, /// Calls it is inside of. depth: u32, /// The stack pointer as it was entered. sp: u64, /// The moments that hold its `call` and its `ret` (null: never returned). enter: u64, exit: ?u64 = null, /// Its first argument, as far as the recording tells: the first /// variable declared in it (`parameter`: where, how many bytes), else /// `rdi` as it was called. arg: ?u64 = null, parameter: ?Span = null, /// That variable's name, a string id; null when the recording names none. parameter_name: ?u64 = null, result: u64 = 0, /// On the stack at moment `i`. pub fn active(c: Call, i: u64) bool { return c.enter <= i and (c.exit == null or c.exit.? > i); } }; pub const Syscall = struct { nr: u16, args: [6]u64, /// The string or buffer its first pointer argument points at, when the /// recorder captured it (a path, the bytes written). text: []const u8 = "", /// The moment that holds its entry, and its exit (null: it never came back). enter: u64, exit: ?u64 = null, result: u64 = 0, }; pub const Mark = struct { moment: u64, text: []const u8 }; /// An allocation ever made: its place in this list is its identity, the /// same in every view. /// An allocation: the agent's (`event` its event), or, in a recording with /// none and glibc's heap at each stop (`--heap`), a chunk in use there, its /// body (`ptr` 16 into the chunk, `size` the chunk's less its 16), from the /// first stop that has it to the first that does not (`gone`). pub const Born = struct { ptr: u64, size: u64, moment: u64, event: u64, gone: u64 = std.math.maxInt(u64) }; /// A run of bytes a moment changed, or read. pub const Span = struct { addr: u64, len: u64 }; /// What the instruction at a moment's pc is about to do to memory (the /// debugger's `touch`): `how` 1 reads there, 2 writes there, 3 both. pub const Touch = struct { addr: u64, len: u64, how: u8 }; /// Where the instruction at a moment's pc goes, if it is a call, a jump /// or a return (the debugger's `branch`), and whether it will. pub const Branch = struct { to: u64, taken: bool, kind: enum(u8) { none, call, jump, ret } }; /// The source line an instruction was compiled from, as the recording saw /// the program stopped there. pub const CodeLine = struct { addr: u64, line: u32 }; /// A variable on the stack, declared at a moment. pub const Declared = struct { moment: u64, addr: u64 }; /// Where a cursor's step may end. pub const Stop = enum { /// The next moment, whatever the recorder made one: an instruction, a line. moment, /// The next moment on another line of the program's source. line, /// The same, not counting lines inside calls made on the way: step over. over, /// The next call or return. call, /// The next syscall. syscall, }; trace: zt.Trace, /// What `open` was given: the recording's bytes, to know it again. key: [*]const u8, /// The source file the recording's lines are in, and its text. file: []const u8, source: []const u8, /// Its functions, as pardes outlines them, and how many lines it has. functions: []const Function = &.{}, line_count: u32 = 0, /// Every file the source panel can show: the program's own first (`file`, /// `source`), then those the build gave it (a library's, by the path its /// debug info names); and the most lines any of them has. sources: []const Source = &.{}, most_lines: u32 = 0, /// Where the source panel stands after each moment: the line the pc is on /// where its file is one of `sources`, else the last such line (the /// deepest frame that has source, a frame up). shown: []Shown = &.{}, /// The thread shown: the first to make an event. tid: u32 = 0, /// The source line `tid` is on after each moment (line 0: none yet), in /// whatever file; and the last line of `file` it was on, which is where /// the program's own source stands while a library runs. lines: []store.Line = &.{}, own: []u32 = &.{}, /// Whether each moment reached a line of `file`: a `line` event of its own. reached: []bool = &.{}, /// How many calls deep `tid` is after each moment. depths: []u32 = &.{}, calls: []Call = &.{}, syscalls: []Syscall = &.{}, marks: []Mark = &.{}, allocations: []Born = &.{}, /// Whether `allocations` were read off the heap (`allocationsFromHeap`). heap_read: bool = false, /// The registers of `tid` after each moment (the last known, before any). registers: []zt.Regs = &.{}, write_spans: Spans = .{}, /// What instructions stored, changed or not (a recording by instruction). store_spans: Spans = .{}, read_spans: Spans = .{}, /// For each moment, what the instruction at its pc touches and where it branches. insn_touches: [][2]?Touch = &.{}, insn_branches: []?Branch = &.{}, /// Every instruction address the program stopped at in its own source, /// with that line, in address order. code_lines: []CodeLine = &.{}, /// Each local variable's declaration, in the order they came: in a /// recording that tells no calls, what says when a local began. locals: []Declared = &.{}, /// The variables declared outside the stack (globals): bytes a lens draws. globals: []Span = &.{}, strings: std.AutoHashMapUnmanaged(u64, []const u8) = .empty, /// What a program built without the pass does not tell of itself (the /// introduction's plain build): its globals' types and its named types, in /// the pass's notation (`types`), by name (`declare`); its locals are the /// debug info's (`zt.telescope.slots`), untyped. declared: std.StringHashMapUnmanaged(u64) = .empty, arena: std.heap.ArenaAllocator, const gpa = std.heap.smp_allocator; /// Recordings opened so far. They live as long as the process: a scene's /// `frame` runs every frame and asks again. var opened: std.ArrayList(*Recording) = .empty; /// A file the source panel can show: its path as the debug info names it /// (the program's own, its bare name), its text and how many lines. pub const Source = struct { path: []const u8, text: []const u8, lines: u32, /// What its tag says: the file's name. pub fn name(s: Source) []const u8 { return std.fs.path.basename(s.path); } }; /// A line of `sources[src]`; `here`: the pc is on it (else a frame up is). pub const Shown = struct { src: u16 = 0, line: u32 = 0, here: bool = false }; /// A recording as the build embeds it in `recordings`: a `.ztrace` file's /// bytes (`trace`), the source it ran (`source`) and its name (`file`), /// and the other sources its lines name that the build found (`sources`: /// path and text). Opened and indexed the first time. pub fn open(program: anytype) *Recording { for (opened.items) |r| if (r.key == program.trace.ptr) return r; const more: []const [2][]const u8 = if (@hasField(@TypeOf(program), "sources")) program.sources else &.{}; const r = load(program.trace, program.file, program.source, more) catch |err| std.debug.panic("canim: cannot open the recording of {s}: {t}", .{ program.file, err }); opened.append(gpa, r) catch @panic("canim: out of memory"); return r; } fn lineCount(text: []const u8) u32 { return @intCast(std.mem.count(u8, text, "\n") + @intFromBool(text.len > 0 and text[text.len - 1] != '\n')); } fn load(bytes: []const u8, file: []const u8, source: []const u8, more: []const [2][]const u8) !*Recording { // The trace reads a file: give it one in memory. const linux = std.os.linux; const rc = linux.memfd_create("canim", linux.MFD.CLOEXEC); if (linux.errno(rc) != .SUCCESS) return error.NoMemfd; const fd: linux.fd_t = @intCast(rc); defer _ = linux.close(fd); var done: usize = 0; while (done < bytes.len) { const n = linux.write(fd, bytes[done..].ptr, bytes.len - done); if (linux.errno(n) != .SUCCESS) return error.WriteFailed; done += n; } var path_buf: [64]u8 = undefined; const path = try std.fmt.bufPrint(&path_buf, "/proc/self/fd/{d}", .{fd}); const r = try gpa.create(Recording); errdefer gpa.destroy(r); r.* = .{ .trace = try .open(gpa, std.Io.Threaded.global_single_threaded.io(), path), .key = bytes.ptr, .file = file, .source = source, .arena = .init(gpa) }; if (r.trace.len == 0) return error.EmptyRecording; r.functions = try outline(r.arena.allocator(), source, file); r.line_count = lineCount(source); const sources = try r.arena.allocator().alloc(Source, 1 + more.len); sources[0] = .{ .path = file, .text = source, .lines = r.line_count }; for (more, sources[1..]) |pair, *s| s.* = .{ .path = pair[0], .text = pair[1], .lines = lineCount(pair[1]) }; r.sources = sources; for (sources) |s| r.most_lines = @max(r.most_lines, s.lines); try r.index(); return r; } /// The instruction at `addr` as the debugger disassembled it at moment /// `i` (`text` is Intel syntax, in `buf`: give it 212 bytes or more); null /// where it recorded none. `back` is how long the instruction before it in /// its function is (0: not known); `line`, the line of the program's own /// source it was compiled from (null: another file's, or not known); /// `params`, a direct call's callee's parameter count. pub fn instruction(r: *const Recording, i: u64, addr: u64, buf: []u8) ?struct { len: u8, back: u8, text: []const u8, line: ?u32, src: u16 = 0, params: ?u8 } { const found = (zt.telescope.instruction(r.moment(i), addr, buf) catch return null) orelse return null; if (found.line) |l| if (r.sourceOf(l.file)) |k| return .{ .len = found.len, .back = found.back, .text = found.text, .line = l.line, .src = k, .params = found.params }; return .{ .len = found.len, .back = found.back, .text = found.text, .line = r.lineOf(addr), .params = found.params }; } /// The source a line's file (a string id) is, of `sources`: null where the recording has none. pub fn sourceOf(r: *const Recording, file: u64) ?u16 { const path = r.name(file); if (std.mem.eql(u8, std.fs.path.basename(path), r.file)) return 0; for (r.sources, 0..) |s, k| if (k > 0 and std.mem.eql(u8, s.path, path)) return @intCast(k); return null; } /// Where the code at `addr` is, as the debug info has it at moment `i`: /// its file's name and line, whatever the file (a library's too, its /// source in hand or not); at moment `i`'s own pc, the moment's line. pub fn where(r: *const Recording, i: u64, addr: u64) ?struct { file: []const u8, line: u32 } { var buf: [256]u8 = undefined; if (addr == r.register(i, "rip")) { const l = r.lines[@min(i, r.end())]; if (l.line != 0) return .{ .file = std.fs.path.basename(r.name(l.file)), .line = l.line }; } const found = (zt.telescope.instruction(r.moment(i), addr, &buf) catch null) orelse return null; if (found.line) |l| return .{ .file = std.fs.path.basename(r.name(l.file)), .line = l.line }; return if (r.lineOf(addr)) |l| .{ .file = r.file, .line = l } else null; } /// The source line the instruction at `addr` was compiled from, for a /// recording whose instructions do not carry it (`instruction` gives it /// where they do): where the program stopped there, the line it was on; /// else the line of the nearest instruction before it that it stopped at, /// close by. Null where nothing is known. pub fn lineOf(r: *const Recording, addr: u64) ?u32 { var lo: usize = 0; var hi: usize = r.code_lines.len; while (lo < hi) { const mid = (lo + hi) / 2; if (r.code_lines[mid].addr <= addr) lo = mid + 1 else hi = mid; } if (lo == 0) return null; const near = r.code_lines[lo - 1]; return if (addr - near.addr <= 96) near.line else null; } /// The line of the program's own source moment `i` is on; null where it is /// elsewhere (a library's code, a stop with no line). pub fn ownLine(r: *const Recording, i: u64) ?u32 { const l = r.lines[@min(i, r.end())]; if (l.line == 0 or !std.mem.eql(u8, std.fs.path.basename(r.name(l.file)), r.file)) return null; return l.line; } /// Whether the pc at moment `i` is on a line the source panel can show (the /// program's own, or a library's whose source the build gave): not in a /// PLT stub, the vDSO, a library without source (where `shown` keeps the last line). pub fn sourced(r: *const Recording, i: u64) bool { var buf: [256]u8 = undefined; const here = r.instruction(i, r.register(i, "rip"), &buf) orelse return r.ownLine(i) != null; return here.line != null; } /// The first line a source panel of `fit` lines shows when the program is /// on `line` of a file of `lines`: the whole file when it fits; else a /// window that has the line in its middle third, and is the same window /// for every line of that third, so that the text moves only when the /// program has moved on. pub fn viewFirst(fit: u32, lines: u32, line: u32) u32 { if (lines <= fit or fit == 0) return 1; // One or two lines (a column's pane): the line itself, first. if (fit < 3) return std.math.clamp(line, 1, lines - fit + 1); const third = fit / 3; const band = (@max(line, 1) - 1) / third; return std.math.clamp(@as(u32, @intCast(@max(@as(i64, band) - 1, 0))) * third + 1, 1, lines - fit + 1); } /// The first line of `shown`'s file a source panel of `fit` lines shows. pub fn shownFirst(r: *const Recording, fit: u32, shown: Shown) u32 { return viewFirst(fit, r.sources[shown.src].lines, shown.line); } /// Runs of bytes, a list for each moment. const Spans = struct { all: []Span = &.{}, /// Where each moment's end in `all`. ends: []u32 = &.{}, /// Those of the moments after `from`, up to `to`. fn of(s: Spans, from: u64, to: u64) []const Span { if (to >= s.ends.len or from >= to) return &.{}; return s.all[s.ends[from]..s.ends[to]]; } }; /// shortcut: reads the whole recording at open (about 5 us a moment) and /// follows one thread; a recording of millions of moments wants this stored /// in the file by the recorder. fn index(r: *Recording) !void { const arena = r.arena.allocator(); var lines: std.ArrayList(store.Line) = .empty; var own: std.ArrayList(u32) = .empty; var shown: std.ArrayList(Shown) = .empty; var reached: std.ArrayList(bool) = .empty; var depths: std.ArrayList(u32) = .empty; var calls: std.ArrayList(Call) = .empty; var syscalls: std.ArrayList(Syscall) = .empty; var marks: std.ArrayList(Mark) = .empty; var allocations: std.ArrayList(Born) = .empty; var registers: std.ArrayList(zt.Regs) = .empty; var writes: std.ArrayList(Span) = .empty; var write_ends: std.ArrayList(u32) = .empty; var stores: std.ArrayList(Span) = .empty; var store_ends: std.ArrayList(u32) = .empty; var reads: std.ArrayList(Span) = .empty; var read_ends: std.ArrayList(u32) = .empty; var touch_list: std.ArrayList([2]?Touch) = .empty; var locals: std.ArrayList(Declared) = .empty; var globals: std.ArrayList(Span) = .empty; // What the instruction at a stop is about to read is read by the step after it. var pending: [2]?Touch = .{ null, null }; var branch_list: std.ArrayList(?Branch) = .empty; var code_lines: std.AutoHashMapUnmanaged(u64, u32) = .empty; defer code_lines.deinit(gpa); var open_calls: std.ArrayList(u32) = .empty; defer open_calls.deinit(gpa); // A recording of instructions tells no calls: they are read off the // open_calls pointer, until its first `call` event says otherwise. var derived: std.ArrayList(u64) = .empty; defer derived.deinit(gpa); var told = false; var before: ?zt.Regs = null; var count: u64 = 0; // Which bytes any moment so far has recorded, 64 to a word of bits. var seen: std.AutoHashMapUnmanaged(u64, u64) = .empty; defer seen.deinit(gpa); // For each write of the moment in hand: whether the debugger saw it (a // snapshot of memory at a stop) and no store of the program's told it. var snapshots: std.ArrayList(bool) = .empty; defer snapshots.deinit(gpa); for (0..r.trace.len) |i| { const m = try r.trace.moment(i); var events = try m.events(gpa); defer events.deinit(gpa); const first_call = calls.items.len; const first_write = writes.items.len; var line_at: ?u64 = null; var line_file: ?u64 = null; var stepped = false; var broke = false; var takes_nothing = false; // An instrumented program's own events are drained before the // debugger reports its stop: what follows its line is the debugger's. var debugger_spoke = false; var touched: [2]?Touch = .{ null, null }; var branched: ?Branch = null; snapshots.clearRetainingCapacity(); for (pending) |p| if (p) |read_by| if (read_by.how & 1 != 0) try reads.append(arena, .{ .addr = read_by.addr, .len = read_by.len }); while (events.next()) |item| { const ev = item.ev; count += 1; if (ev.kind == .string) try r.strings.put(arena, ev.a[0], try arena.dupe(u8, item.payload)); if (ev.tid == 0) continue; if (r.tid == 0) r.tid = ev.tid; if (ev.tid != r.tid) continue; switch (ev.kind) { .call => { told = true; try calls.append(arena, .{ .function = ev.a[0], .parent = open_calls.getLastOrNull(), .depth = @intCast(open_calls.items.len), .sp = ev.a[2], .enter = i }); try open_calls.append(gpa, @intCast(calls.items.len - 1)); }, .ret => if (open_calls.pop()) |c| { calls.items[c].exit = i; calls.items[c].result = ev.a[1]; }, .syscall_enter => try syscalls.append(arena, .{ .nr = ev.aux, .args = ev.a, .enter = i, .text = if (item.payload.len != @sizeOf(zt.Regs)) try arena.dupe(u8, item.payload) else "" }), .syscall_exit => if (syscalls.items.len > 0) { const last = &syscalls.items[syscalls.items.len - 1]; if (last.exit == null) { last.exit = i; last.result = ev.a[0]; } }, .mark => try marks.append(arena, .{ .moment = i, .text = try arena.dupe(u8, item.payload) }), .alloc => try allocations.append(arena, .{ .ptr = ev.a[0], .size = ev.a[1], .moment = i, .event = count }), // A store that left the bytes as they were is told too, with no payload: it is still a write. .mem_write => if (ev.a[1] > 0) { try writes.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] }); try snapshots.append(gpa, !told or debugger_spoke); }, .mem_read => if (ev.a[1] > 0) try reads.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] }), .variable => { if ((zt.telescope.region(m, ev.a[0]) catch .none) == .stack) try locals.append(arena, .{ .moment = i, .addr = ev.a[0] }) else try globals.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] }); // The first variable of a function that takes something is what it was given. if (open_calls.getLastOrNull()) |c| { const takes = for (r.functions) |f| { if (std.mem.eql(u8, f.name, r.name(calls.items[c].function))) break f.takes; } else true; if (takes and calls.items[c].parameter == null and ev.a[1] <= 8) { calls.items[c].parameter = .{ .addr = ev.a[0], .len = ev.a[1] }; calls.items[c].parameter_name = ev.a[2]; } } }, .line => { line_at = ev.a[3]; line_file = ev.a[0]; // The pass counts its strings from 1; the debugger's ids are hashes with the top bit set. if (ev.a[0] >> 63 != 0) debugger_spoke = true; }, .step => stepped = true, .breakpoint => { stepped = true; broke = true; }, .touch => { const slot: usize = if (touched[0] == null) 0 else 1; if (touched[slot] == null) touched[slot] = .{ .addr = ev.a[0], .len = ev.a[1], .how = @intCast(ev.aux & 3) }; }, .branch => branched = .{ .to = ev.a[0], .taken = ev.a[1] != 0, .kind = switch (ev.aux) { 1 => .call, 2 => .jump, 3 => .ret, else => .none, } }, else => {}, } } const regs = try m.regs(r.tid); // A debugger records the stack it can see, not what the program // stores: bytes seen for the first time were not written by this // step, unless it pushed them (the stack pointer went down a word). var kept = first_write; var changed_by_store = false; for (writes.items[first_write..], snapshots.items) |span, snapshot| { var fresh = true; for (0..span.len) |b| { const gop = try seen.getOrPut(gpa, (span.addr + b) / 64); if (!gop.found_existing) gop.value_ptr.* = 0; const bit = @as(u64, 1) << @intCast((span.addr + b) % 64); if (gop.value_ptr.* & bit != 0) fresh = false; gop.value_ptr.* |= bit; } var keep: ?Span = span; if (stepped and fresh and snapshot) { const pushed = regs != null and before != null and regs.?.rsp + 8 == before.?.rsp and span.addr <= regs.?.rsp and span.addr + span.len >= regs.?.rsp + 8; keep = if (pushed) .{ .addr = regs.?.rsp, .len = 8 } else null; } // The store the instruction made says it to the element: below. if (!told and stepped and stored(pending, span)) { keep = null; changed_by_store = true; } if (keep) |span_kept| { writes.items[kept] = span_kept; kept += 1; } } writes.shrinkRetainingCapacity(kept); // What the instruction at the stop before said it would store, it // stored, the bytes it named: a write where the value changed (a // debugger sees words change, the instruction says which element); // a store all the same, even of the value that was there. if (!told and stepped) for (pending) |p| if (p) |w| if (w.how & 2 != 0) { try stores.append(arena, .{ .addr = w.addr, .len = w.len }); if (changed_by_store) try writes.append(arena, .{ .addr = w.addr, .len = w.len }); }; try write_ends.append(arena, @intCast(writes.items.len)); try store_ends.append(arena, @intCast(stores.items.len)); try read_ends.append(arena, @intCast(reads.items.len)); const line = (try m.line(r.tid)) orelse store.Line{}; try lines.append(arena, line); const ours = line.line != 0 and std.mem.eql(u8, std.fs.path.basename(r.name(line.file)), r.file); try own.append(arena, if (ours) line.line else if (own.items.len > 0) own.items[own.items.len - 1] else 0); const src = if (line.line != 0) r.sourceOf(line.file) else null; try shown.append(arena, if (src) |k| .{ .src = k, .line = line.line, .here = true } else if (shown.items.len > 0) .{ .src = shown.items[shown.items.len - 1].src, .line = shown.items[shown.items.len - 1].line } else .{}); try reached.append(arena, ours and line_file != null); try touch_list.append(arena, touched); pending = touched; try branch_list.append(arena, branched); // Not where the instruction says it has no line: a library's code (a // PLT stub, libc) keeps the last line of ours in `lines`, and is not of it. if (ours and regs != null) { var text: [256]u8 = undefined; const here = zt.telescope.instruction(m, regs.?.rip, &text) catch null; if (here == null or here.?.line != null) try code_lines.put(gpa, regs.?.rip, line.line); } try registers.append(arena, regs orelse before orelse .{}); if (!told and stepped and regs != null and before != null) { const now = regs.?; const was = before.?; // Back where the newest call was made from, its frame gone. if (derived.getLastOrNull()) |back| { const top = &calls.items[open_calls.getLast()]; if (now.rip == back and now.rsp == top.sp + 8) { _ = derived.pop(); _ = open_calls.pop(); top.exit = i; top.result = now.rax; } } // A call pushes the address after itself and lands on a line of ours. if (now.rsp + 8 == was.rsp and line_at == now.rip and ours) { if (try word(m, now.rsp, 8)) |back| if (back > was.rip and back - was.rip <= 15) { const function = r.functionAt(line.line); takes_nothing = function != null and !function.?.takes; try calls.append(arena, .{ .function = try r.intern(if (function) |fun| fun.name else "?"), .parent = open_calls.getLastOrNull(), .depth = @intCast(open_calls.items.len), .sp = now.rsp, .enter = i }); try open_calls.append(gpa, @intCast(calls.items.len - 1)); try derived.append(gpa, back); }; } } // A recording that begins inside a call (`record --from`): the call // it first stops in was made before it, and is open. if (!told and broke and ours and calls.items.len == 0) if (regs) |now| { var found: [2]zt.Debugger.Frame = undefined; const frames = zt.telescope.frames(m, &now, &found) catch found[0..0]; if (frames.len == 2 and frames[0].high > frames[0].low) { const function = r.functionAt(line.line); takes_nothing = function != null and !function.?.takes; try calls.append(arena, .{ .function = try r.intern(if (function) |fun| fun.name else "?"), .parent = null, .depth = 0, .sp = frames[0].high - 8, .enter = i }); try open_calls.append(gpa, 0); try derived.append(gpa, frames[1].pc); } }; if (regs) |g| before = g; try depths.append(arena, @intCast(open_calls.items.len)); // What each open call was given, once the recording has it: the // value of its first variable, or for one read off the registers, rdi. for (calls.items[first_call..]) |*c| { if (!told and regs != null and !takes_nothing) c.arg = regs.?.rdi; } // (Once it is stored: until then that stretch of stack holds what was there before.) for (open_calls.items) |c| { const call_made = &calls.items[c]; if (call_made.arg != null) continue; if (call_made.parameter) |p| if (touches(writes.items[first_write..], p.addr, p.len)) { call_made.arg = try word(m, p.addr, @intCast(p.len)); }; } } // An instrumented program under the debugger says "call" a few stops // after the debugger has stopped on the callee's first line: the call // began at that stop. if (told) for (calls.items) |*c| { var at = c.enter; var back: usize = 0; while (at > 0 and back < 64 and !reached.items[at]) : (back += 1) at -= 1; if (!reached.items[at] or at == c.enter) continue; for (depths.items[at..c.enter]) |*depth| depth.* += 1; c.enter = at; }; r.lines = lines.items; r.own = own.items; r.shown = shown.items; r.reached = reached.items; r.depths = depths.items; r.calls = calls.items; r.syscalls = syscalls.items; r.marks = marks.items; r.allocations = allocations.items; r.registers = registers.items; r.write_spans = .{ .all = writes.items, .ends = write_ends.items }; r.store_spans = .{ .all = stores.items, .ends = store_ends.items }; r.insn_touches = touch_list.items; r.insn_branches = branch_list.items; r.code_lines = try arena.alloc(CodeLine, code_lines.count()); var it = code_lines.iterator(); var n: usize = 0; while (it.next()) |e| : (n += 1) r.code_lines[n] = .{ .addr = e.key_ptr.*, .line = e.value_ptr.* }; std.mem.sort(CodeLine, r.code_lines, {}, struct { fn less(_: void, a: CodeLine, b: CodeLine) bool { return a.addr < b.addr; } }.less); r.read_spans = .{ .all = reads.items, .ends = read_ends.items }; r.locals = locals.items; r.globals = globals.items; } /// A scene that draws the program's allocations from glibc's heap /// (`--heap`) where no agent told them (the introduction's list nodes): /// `allocations` read off the heap, once. Not by default: a scene of the /// heap's own (`heap`) times its steps by what it draws, not by these. pub fn allocationsFromHeap(r: *Recording) void { if (r.allocations.len > 0 or r.heap_read) return; r.heap_read = true; r.allocations = heapBorn(r, r.arena.allocator()) catch &.{}; } /// The program's allocations read off glibc's heap at each stop (`--heap`), /// where no agent told them: each chunk in use but the tcache's own, from /// the first stop that has it; `gone` at the first that does not. In the /// order they were first seen, by address within one stop. fn heapBorn(r: *const Recording, arena: std.mem.Allocator) ![]Born { var out: std.ArrayList(Born) = .empty; var scratch: std.heap.ArenaAllocator = .init(gpa); defer scratch.deinit(); var i: u64 = 0; while (i <= r.end()) : (i += 1) { _ = scratch.reset(.retain_capacity); const h = (zt.heap.glibc(scratch.allocator(), r.moment(i), r.tid) catch null) orelse continue; const own: u64 = if (h.tcache) |tc| tc.addr else 0; for (h.chunks) |c| { if (c.free or c.in != .none or c.addr + 16 == own or c.size() < 32) continue; const ptr = c.addr + 16; const known = for (out.items) |b| { if (b.ptr == ptr and b.gone > i) break true; } else false; if (!known) try out.append(arena, .{ .ptr = ptr, .size = c.size() - 16, .moment = i, .event = std.math.maxInt(u64) }); } // What was in use and is not now has gone. for (out.items) |*b| if (b.gone > i and b.moment < i) { const still = for (h.chunks) |c| { if (c.addr + 16 == b.ptr and !c.free and c.in == .none) break true; } else false; if (!still) b.gone = i; }; } return out.items; } /// The allocation live at `m` that holds `addr`: the agent's (`Moment.allocation`) or one read off the heap. pub fn allocated(r: *const Recording, m: Moment, addr: u64) bool { if ((m.allocation(addr) catch null) != null) return true; for (r.allocations) |b| if (b.event == std.math.maxInt(u64) and addr >= b.ptr and addr - b.ptr < @max(b.size, 1) and b.moment <= m.index and m.index < b.gone) return true; return false; } /// A string id for `text`, for names the recording did not define itself. fn intern(r: *Recording, text: []const u8) !u64 { const id = std.hash.Wyhash.hash(0, text) | 1 << 63; if (!r.strings.contains(id)) try r.strings.put(r.arena.allocator(), id, try r.arena.allocator().dupe(u8, text)); return id; } pub const Function = struct { name: []const u8, /// Whether it has parameters: `main(void)` has none; and how many. takes: bool, params: usize = 0, /// Its first parameter's name ("" when it takes none). param: []const u8 = "", /// Its declaration's first line (from 1) and last. first: u32, last: u32, }; /// The functions of `source`, as pardes outlines them: a name is the word /// before the first parenthesis of a declaration's header. pub fn outline(arena: std.mem.Allocator, source: []const u8, file: []const u8) ![]Function { var analysis = pardes.analyzeSource(gpa, file, source, true, false) catch return &.{}; defer analysis.deinit(gpa); var found: std.ArrayList(Function) = .empty; for (analysis.declarations) |d| { const header = source[d.start_byte..d.header_end_byte]; const paren = std.mem.indexOfScalar(u8, header, '(') orelse continue; var from = paren; while (from > 0 and (std.ascii.isAlphanumeric(header[from - 1]) or header[from - 1] == '_')) from -= 1; if (from == paren) continue; const close = std.mem.indexOfScalarPos(u8, header, paren, ')') orelse header.len; const params = std.mem.trim(u8, header[paren + 1 .. close], " "); const first_param = std.mem.trim(u8, params[0 .. std.mem.indexOfScalar(u8, params, ',') orelse params.len], " "); var name_from = first_param.len; while (name_from > 0 and (std.ascii.isAlphanumeric(first_param[name_from - 1]) or first_param[name_from - 1] == '_')) name_from -= 1; try found.append(arena, .{ .name = header[from..paren], .takes = params.len > 0 and !std.mem.eql(u8, params, "void"), .params = if (params.len > 0 and !std.mem.eql(u8, params, "void")) std.mem.count(u8, params, ",") + 1 else 0, .param = first_param[name_from..], .first = @intCast(d.start_line + 1), .last = @intCast(d.end_line + 1) }); } return found.items; } /// The function whose declaration holds `line` (from 1): the innermost. pub fn functionAt(r: *const Recording, line: u32) ?Function { var found: ?Function = null; for (r.functions) |f| if (line >= f.first and line <= f.last) { found = f; }; return found; } /// `size` bytes at `addr` as a little-endian number; null where a byte of /// it was never recorded. pub fn word(m: Moment, addr: u64, size: usize) !?u64 { var bytes: [8]u8 = @splat(0); var known: [8]bool = undefined; try m.read(addr, bytes[0..size], known[0..size]); for (known[0..size]) |k| if (!k) return null; return std.mem.readInt(u64, &bytes, .little); } pub fn len(r: *const Recording) u64 { return r.trace.len; } /// The last moment. pub fn end(r: *const Recording) u64 { return r.trace.len - 1; } /// The program's state at moment `i` (the last one, past the end). pub fn moment(r: *const Recording, i: u64) Moment { return r.trace.moment(@min(i, r.end())) catch unreachable; } /// Register `reg` of the thread shown at moment `i`; 0 when the recording /// has no registers there. pub fn register(r: *const Recording, i: u64, reg: []const u8) u64 { return r.registers[@min(i, r.end())].named(reg) orelse 0; } /// A string id's text; "?" for one the recording never defined. pub fn name(r: *const Recording, id: u64) []const u8 { return r.strings.get(id) orelse "?"; } /// The live variable called `text`: the innermost of that name. pub fn variable(r: *const Recording, scratch: std.mem.Allocator, m: Moment, text: []const u8) ?Variable { const all = m.variables(scratch) catch return null; var found: ?Variable = null; for (all) |v| { if (std.mem.eql(u8, r.name(v.name), text) and (found == null or v.depth > found.?.depth)) found = v; } return found orelse if (r.declared.count() > 0) r.plain(m, text) else null; } /// The live variables: the recording's, or a plain build's declared globals. pub fn variables(r: *const Recording, scratch: std.mem.Allocator, m: Moment) []Variable { const all = m.variables(scratch) catch return &.{}; if (all.len > 0 or r.declared.count() == 0) return all; var out: std.ArrayList(Variable) = .empty; var it = r.declared.keyIterator(); while (it.next()) |key| if (key.*[0] != '`') if (r.plain(m, key.*)) |v| out.append(scratch, v) catch break; return out.items; } /// Declares, for a program built without the pass, global `what`'s type /// (`text`, in the pass's notation), or a named type's description /// (`what` in backticks, as a type names it). Once each. /// shortcut: a scene writes them from the source, as the tracer reads no types from the debug info; upgrade when it does. pub fn declare(r: *Recording, what: []const u8, text: []const u8) void { if (r.declared.contains(what)) return; const a = r.arena.allocator(); const named = what[0] == '`'; const id = if (named) types.defId(what[1 .. what.len - 1]) else r.intern(text) catch return; if (named) r.strings.put(a, id, a.dupe(u8, text) catch return) catch return; r.declared.put(a, a.dupe(u8, what) catch return, id) catch {}; } /// A plain build's variable `text` at `m`: a declared global, at the /// address the recording names `text+0` (a word: what a lens hangs from is /// a pointer); or a local of the newest frame, by the debug info. Its /// `name` is 0: the recording has no id for it. fn plain(r: *const Recording, m: Moment, text: []const u8) ?Variable { if (r.declared.get(text)) |ty| { var it = r.strings.iterator(); while (it.next()) |e| { const s = e.value_ptr.*; if (e.key_ptr.* >> 63 == 0 and s.len == text.len + 2 and std.mem.startsWith(u8, s, text) and std.mem.endsWith(u8, s, "+0")) return .{ .addr = e.key_ptr.*, .size = 8, .name = 0, .type = ty, .tid = r.tid, .depth = 0 }; } return null; } const regs = (m.regs(r.tid) catch null) orelse return null; var buf: [32]zt.telescope.Slot = undefined; const slots = zt.telescope.slots(m, ®s, regs.rsp, &buf) catch return null; for (slots, 0..) |slot, k| if (slot.frame == 0 and slot.role == .local) { const l = slot.role.local; if (l.offset == 0 and std.mem.eql(u8, l.name, text)) return .{ .addr = regs.rsp + 8 * k, .size = l.size, .name = 0, .type = 0, .tid = r.tid, .depth = r.depths[@min(m.index, r.end())] }; }; return null; } /// A variable's type, as the compiler pass described it, with a named type /// (`struct node`, a typedef) followed to what it is. Null when the /// recording has no description (it was not made by `ztrace cc`). pub fn typeOf(r: *const Recording, scratch: std.mem.Allocator, id: u64) ?types.Type { return r.resolve(scratch, types.parse(scratch, r.strings.get(id) orelse return null) catch return null); } /// `t`, or what its name stands for. pub fn resolve(r: *const Recording, scratch: std.mem.Allocator, t: types.Type) ?types.Type { var at = t; // A typedef of a typedef of a struct, and no further. for (0..8) |_| { if (at != .named) return at; at = types.parse(scratch, r.strings.get(types.defId(at.named)) orelse return null) catch return null; } return null; } /// Whether variable `v` has been stored to since the call it lives in /// began: until then its bytes are whatever that stretch of stack held /// before, and a picture should not show them as its value. pub fn assigned(r: *const Recording, v: Variable, i: u64) bool { if (v.depth == 0) { // A recording that tells no calls: a local is its value once // written after it was declared; a global always is. var k = r.locals.len; while (k > 0) { k -= 1; const d = r.locals[k]; if (d.moment <= i and d.addr == v.addr) return touches(r.written(d.moment, i), v.addr, v.size) or touches(r.store_spans.of(d.moment, i), v.addr, v.size); } return true; } var enter: u64 = 0; for (r.calls) |c| { if (c.enter > i) break; if (c.active(i) and c.depth + 1 == v.depth) enter = c.enter; } // A plain build's local (`plain`): a store of the value its stretch of stack held assigns it too. return touches(r.written(enter -| 1, i), v.addr, v.size) or (v.name == 0 and touches(r.store_spans.of(enter -| 1, i), v.addr, v.size)); } /// Which allocation ever made holds `addr` at moment `m`: the same number /// for the same object in every view, null outside the heap. pub fn identity(r: *const Recording, m: Moment, addr: u64) ?usize { const a = (m.allocation(addr) catch return null) orelse return null; for (r.allocations, 0..) |b, i| if (b.event == a.born) return i; return null; } /// What file descriptor `fd` is open on at moment `i`, as the `value` /// class `fd` says it: the path the call that returned it was given, /// quoted; the three a program starts with by name; "" when not known. pub fn openOn(r: *const Recording, scratch: std.mem.Allocator, fd: u64, i: u64) []const u8 { var on: []const u8 = switch (fd) { 0 => "stdin", 1 => "stdout", 2 => "stderr", else => "", }; const SYS = std.os.linux.SYS; for (r.syscalls) |s| { if (s.enter >= i) break; switch (std.enums.fromInt(SYS, s.nr) orelse continue) { .open, .openat, .creat => if (s.exit != null and s.exit.? <= i and s.result == fd) { on = if (s.text.len > 0) std.fmt.allocPrint(scratch, "\"{s}\"", .{std.fs.path.basename(s.text)}) catch "" else ""; }, .close => if (s.args[0] == fd) { on = ""; }, else => {}, } } return on; } /// The calls open at moment `i`, outermost first, in `scratch`. /// shortcut: looks at every call made by then; a recording of a million calls wants each call's stack kept as a chain of parents. pub fn stack(r: *const Recording, scratch: std.mem.Allocator, i: u64) []const Call { var out: std.ArrayList(Call) = .empty; for (r.calls) |c| { if (c.enter > i) break; if (c.active(i)) out.append(scratch, c) catch break; } return out.items; } // --------------------------------------------------------------------------- // Finding moments. Each returns the last moment when there is none: a // cursor sent there plays to the end. /// The first moment after `from` that is a stop of kind `by`. pub fn next(r: *const Recording, by: Stop, from: u64) u64 { if (from >= r.end()) return r.end(); switch (by) { .moment => return from + 1, .line, .over => { const depth = r.depths[from]; for (from + 1..r.len()) |i| { // A line of the program's own, newly reached: another line, // or the same one in another call (fib's, a level down). if (!r.reached[i] or (r.own[i] == r.own[from] and r.depths[i] == depth)) continue; if (by == .line or r.depths[i] <= depth) return i; } }, .call => { var best = r.end(); for (r.calls) |c| { if (c.enter > from) best = @min(best, c.enter); if (c.exit) |e| if (e > from) { best = @min(best, e); }; } return best; }, .syscall => for (r.syscalls) |s| if (s.enter > from) return s.enter, } return r.end(); } /// The first moment at or after `from` on line `line` of the program's source. pub fn lineMoment(r: *const Recording, line: u32, from: u64) u64 { for (r.own[@min(from, r.len())..], from..) |l, i| if (l == line) return i; return r.end(); } /// The first moment after `from` that changes a byte in `addr .. addr + size`. pub fn nextWrite(r: *const Recording, addr: u64, size: u64, from: u64) u64 { var i = from + 1; while (i < r.len()) : (i += 1) if (touches(r.written(i - 1, i), addr, size)) return i; return r.end(); } /// The moment of the mark `text`. A scene asking for a mark the program /// never made is a mistake in the scene. pub fn mark(r: *const Recording, text: []const u8) u64 { for (r.marks) |m| if (std.mem.eql(u8, m.text, text)) return m.moment; std.debug.panic("canim: the recording has no mark \"{s}\"", .{text}); } /// The `nth` call (from 0) of the function called `function`. pub fn call(r: *const Recording, function: []const u8, nth: usize) Call { var seen: usize = 0; for (r.calls) |c| if (std.mem.eql(u8, r.name(c.function), function)) { if (seen == nth) return c; seen += 1; }; std.debug.panic("canim: the recording has no call {d} of \"{s}\"", .{ nth, function }); } // --------------------------------------------------------------------------- // What changed. /// The bytes the moments after `from`, up to `to`, changed. pub fn written(r: *const Recording, from: u64, to: u64) []const Span { return r.write_spans.of(from, to); } /// The bytes they stored with the value already there (a local /// assigned what its slot held before): no change, but an assignment. pub fn storedSame(r: *const Recording, from: u64, to: u64) []const Span { return r.store_spans.of(from, to); } /// The bytes they read. pub fn read(r: *const Recording, from: u64, to: u64) []const Span { return r.read_spans.of(from, to); } /// A bit for each register of `Regs.names` that is not what it was: /// a register a step changed and put back (a call's rsp) is not changed. pub fn registersChanged(r: *const Recording, from: u64, to: u64) u32 { if (to >= r.registers.len or from >= to) return 0; return changedRegisters(r.registers[from], r.registers[to]); } /// Whether bytes `span` are drawn somewhere for the step from `from` to /// `to`: in the stack's frame round either stop's rsp and rbp, in an /// allocation, or in a global (an array's cells). Elsewhere (the library's /// own memory) a step's memory level has nothing to show. pub fn drawn(r: *const Recording, span: Span, from: u64, to: u64) bool { for ([_]u64{ from, to }) |i| { const regs = r.registers[@min(i, r.end())]; const low = regs.rsp -| 8; const high = @max(regs.rbp, regs.rsp) + 16 + 8 * 8; if (span.addr < high and span.addr + span.len > low) return true; } for (r.allocations) |a| if (span.addr < a.ptr + a.size and span.addr + span.len > a.ptr -| 16) return true; return touches(r.globals, span.addr, span.len); } pub fn touches(list: []const Span, addr: u64, size: u64) bool { // Saturating: a register's chain asks about any value, to the top of the address space. for (list) |s| if (s.addr < addr +| size and s.addr + s.len > addr) return true; return false; } /// Whether one of `by` (an instruction's touches) stores into `span`. fn stored(by: [2]?Touch, span: Span) bool { for (by) |p| if (p) |w| if (w.how & 2 != 0 and w.addr < span.addr + span.len and w.addr + w.len > span.addr) return true; return false; } /// A bit for each register of `Regs.names` that differs between `a` and `b`. pub fn changedRegisters(a: zt.Regs, b: zt.Regs) u32 { var mask: u32 = 0; inline for (zt.Regs.names, 0..) |reg, i| { if (@field(a, reg) != @field(b, reg)) mask |= 1 << i; } return mask; } test "registers that differ are told by their place in Regs.names" { const a: zt.Regs = .{ .rax = 1, .rip = 0x1000, .rsp = 8 }; var b = a; b.rax = 2; b.rip = 0x1004; try std.testing.expectEqualStrings("rax", zt.Regs.names[0]); const mask = changedRegisters(a, b); try std.testing.expect(mask & 1 != 0); try std.testing.expectEqual(@as(u32, 2), @popCount(mask)); try std.testing.expectEqual(@as(u32, 0), changedRegisters(a, a)); } test "spans touch the ranges they overlap" { const list = [_]Span{ .{ .addr = 0x100, .len = 4 }, .{ .addr = 0x200, .len = 1 } }; try std.testing.expect(touches(&list, 0x100, 8)); try std.testing.expect(touches(&list, 0x0fc, 5)); try std.testing.expect(!touches(&list, 0x0fc, 4)); try std.testing.expect(!touches(&list, 0x104, 8)); try std.testing.expect(touches(&list, 0x1f9, 8)); } test "a function is named by the declaration that holds the line" { const source = \\#include \\ \\long fib(long n) { \\ if (n < 2) \\ return n; \\ return fib(n - 1) + fib(n - 2); \\} \\ \\int main(void) { \\ printf("%ld\\n", fib(5)); \\ return 0; \\} ; var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); defer arena.deinit(); const r: Recording = .{ .trace = undefined, .key = undefined, .file = "fib.c", .source = source, .arena = undefined, .functions = try outline(arena.allocator(), source, "fib.c") }; try std.testing.expectEqualStrings("fib", r.functionAt(3).?.name); try std.testing.expect(r.functionAt(6).?.takes); try std.testing.expectEqualStrings("main", r.functionAt(10).?.name); try std.testing.expect(!r.functionAt(10).?.takes); try std.testing.expect(r.functionAt(8) == null); try std.testing.expectEqual(@as(u32, 7), r.functionAt(5).?.last); }