//! The pass and the runtime on real programs: each test reads the recording //! of a target the build compiled with `ztrace cc` and ran under `ztrace //! run` (their paths come from build/llvm.zig), as a viewer would: names //! and types from the recording alone. const std = @import("std"); const linux = std.os.linux; const zt = @import("ztrace"); const types = @import("types"); const recordings = @import("recordings"); const gpa = std.testing.allocator; const io = std.testing.io; const expect = std.testing.expect; const expectEqual = std.testing.expectEqual; const expectEqualSlices = std.testing.expectEqualSlices; const expectEqualStrings = std.testing.expectEqualStrings; const Item = struct { moment: u64, ev: zt.Event, payload: []const u8 }; /// A recording, its events in order with the moment each is in, and the id /// the runtime gave each text. const Recording = struct { arena: std.heap.ArenaAllocator, trace: zt.Trace, items: []Item, ids: std.StringHashMapUnmanaged(u64) = .empty, fn open(path: []const u8) !Recording { var r: Recording = .{ .arena = .init(gpa), .trace = try zt.Trace.open(gpa, io, path), .items = &.{} }; errdefer r.close(); const arena = r.arena.allocator(); var items: std.ArrayList(Item) = .empty; for (0..r.trace.len) |m| { var events = try (try r.trace.moment(m)).events(arena); while (events.next()) |item| { try items.append(arena, .{ .moment = m, .ev = item.ev, .payload = item.payload }); if (item.ev.kind == .string) try r.ids.put(arena, item.payload, item.ev.a[0]); } } r.items = items.items; return r; } /// The id of a text; 0, which nothing has, for one the program lacks. fn id(r: *const Recording, text: []const u8) u64 { return r.ids.get(text) orelse 0; } fn close(r: *Recording) void { r.trace.close(); r.arena.deinit(); } fn last(r: *const Recording) !zt.store.Moment { return r.trace.moment(r.trace.len - 1); } fn string(r: *Recording, of: u64) ![]const u8 { const buf = try r.arena.allocator().alloc(u8, 4096); return (try (try r.last()).string(of, buf)) orelse error.NoSuchString; } /// The first `variable` event of that name and type. fn variable(r: *Recording, name: []const u8, type_text: []const u8) !zt.Event { for (r.items) |item| { if (item.ev.kind == .variable and item.ev.a[2] == r.id(name) and item.ev.a[3] == r.id(type_text)) return item.ev; } return error.NoSuchVariable; } fn count(r: *const Recording, kind: zt.Kind, a0: u64) usize { var n: usize = 0; for (r.items) |item| n += @intFromBool(item.ev.kind == kind and item.ev.a[0] == a0); return n; } /// `T` from the memory recorded as of a moment; every byte must be known. fn read(moment: zt.store.Moment, comptime T: type, addr: u64) !T { var out: T = undefined; var known: [@sizeOf(T)]bool = undefined; try moment.read(addr, std.mem.asBytes(&out), &known); try expect(std.mem.allEqual(bool, &known, true)); return out; } }; /// The calls of fib(n) from `at` on must be the tree of the source: each /// declares its parameter and stores n in it (the recorder keeps the bytes /// of a store only where they changed memory: the value is read there), /// calls fib(n-1) then fib(n-2), and returns their sum from the frame it /// entered. Returns the sum. fn fibTree(r: *const Recording, at: *usize, calls: *usize, n: u32) !u32 { const items = r.items; const fib = r.id("fib"); while (!((items[at.*].ev.kind == .call or items[at.*].ev.kind == .ret) and items[at.*].ev.a[0] == fib)) at.* += 1; const call, const param, const store = .{ items[at.*].ev, items[at.* + 1].ev, items[at.* + 2] }; at.* += 3; calls.* += 1; try expectEqual(zt.Kind.call, call.kind); try expectEqual(r.id("fn(u32)u32"), call.a[3]); try expectEqual(zt.Kind.variable, param.kind); try expectEqual(@as(u16, 1), param.aux); try expectEqual(r.id("n"), param.a[2]); try expectEqual(zt.Kind.mem_write, store.ev.kind); try expectEqual(param.a[0], store.ev.a[0]); try expectEqual(n, try Recording.read(try r.trace.moment(store.moment), u32, param.a[0])); const result = if (n < 2) n else try fibTree(r, at, calls, n - 1) + try fibTree(r, at, calls, n - 2); while (items[at.*].ev.kind != .ret) at.* += 1; const ret = items[at.*].ev; at.* += 1; try expectEqual(fib, ret.a[0]); try expectEqual(@as(u64, result), ret.a[1]); try expectEqual(@as(u16, 4), ret.aux); return result; } test "fib: the call tree, arguments and results" { var r = try Recording.open(recordings.fib); defer r.close(); var at: usize = 0; var calls: usize = 0; try expectEqual(@as(u32, 8), try fibTree(&r, &at, &calls, 6)); try expectEqual(@as(usize, 25), calls); try expectEqual(@as(usize, 25), r.count(.call, r.id("fib"))); try expectEqual(@as(usize, 25), r.count(.ret, r.id("fib"))); try expectEqualStrings("fib", try r.string(r.id("fib"))); // Numbered from 1: a name costs a recording a byte or two each time. try expect(r.id("fib") != 0 and r.id("fib") <= r.ids.count()); // The recorder's stack at the first fib(1): main, then fib six deep. var seen: usize = 0; const deepest = for (r.items) |item| { if (item.ev.kind == .call and item.ev.a[0] == r.id("fib")) seen += 1; if (seen == 6) break item; } else unreachable; const stack = try (try r.trace.moment(deepest.moment)).stack(gpa, deepest.ev.tid); defer gpa.free(stack); try expectEqual(@as(usize, 7), stack.len); try expectEqual(r.id("main"), stack[0].function); for (stack[1..], stack[0 .. stack.len - 1]) |frame, outer| { try expectEqual(r.id("fib"), frame.function); try expect(frame.sp < outer.sp); } } test "sort: both arrays end sorted, and the lines run as often as the source says" { try sortChecks(recordings.sort); } test "sort -O2: the optimizer keeps what the pass put in before it" { try sortChecks(recordings.sort_O2); } fn sortChecks(recording: []const u8) !void { var r = try Recording.open(recording); defer r.close(); const unsorted = [8]i32{ 5, 2, 9, 1, 7, 3, 8, 4 }; const sorted = [8]i32{ 1, 2, 3, 4, 5, 7, 8, 9 }; for ([_][]const u8{ "bubbled", "inserted" }) |name| { const v = try r.variable(name, "[8]i32"); try expectEqual(@as(u64, 32), v.a[1]); try expectEqual(sorted, try Recording.read(try r.last(), [8]i32, v.a[0])); } // The constant they are copied from is a global: known from the start. const source = try r.variable("unsorted", "[8]i32"); try expectEqual(unsorted, try Recording.read(try r.trace.moment(0), [8]i32, source.a[0])); // Inside bubble the recorder knows its locals, and the array as it then was. const in_bubble = for (r.items) |item| { if (item.ev.kind == .line and item.ev.tid != 0 and (try (try r.trace.moment(item.moment)).stack(r.arena.allocator(), item.ev.tid)).len == 2) break item; } else unreachable; const then = try r.trace.moment(in_bubble.moment); try expectEqual(unsorted, try Recording.read(then, [8]i32, (try r.variable("bubbled", "[8]i32")).a[0])); var depth_of_a: u32 = 0; for (try then.variables(r.arena.allocator())) |v| { if (v.name == r.id("a")) depth_of_a = v.depth; } try expectEqual(@as(u32, 2), depth_of_a); // After main returned only the global is left. const left = try (try r.last()).variables(r.arena.allocator()); try expectEqual(@as(usize, 1), left.len); try expectEqual(r.id("unsorted"), left[0].name); // Every line event is a line of the one source file, which the recording names. var file: u64 = 0; var hits: [64]u32 = @splat(0); for (r.items) |item| { if (item.ev.kind != .line) continue; if (file == 0) file = item.ev.a[0]; try expectEqual(file, item.ev.a[0]); hits[item.ev.a[1]] += 1; } const path = try r.string(file); try expect(std.mem.endsWith(u8, path, "targets/instr_sort.c")); const text = try std.Io.Dir.cwd().readFileAlloc(io, path, r.arena.allocator(), .limited(1 << 20)); // The array has 13 inversions: bubble sort swaps that often, insertion // sort shifts that often. Bubble sort compares 8*7/2 times. const expected = [_]struct { []const u8, u32 }{ .{ "if (a[j] > a[j + 1]) {", 28 }, .{ "a[j + 1] = t;", 13 }, .{ "a[j + 1] = a[j];", 13 }, .{ "int key = a[i];", 7 }, .{ "bubble(bubbled, N);", 1 }, }; var found: usize = 0; var lines = std.mem.splitScalar(u8, text, '\n'); var number: usize = 1; while (lines.next()) |line| : (number += 1) { const code = std.mem.trim(u8, line, " "); // No event on a line with no code. if (code.len == 0 or std.mem.startsWith(u8, code, "//") or std.mem.startsWith(u8, code, "#")) try expectEqual(@as(u32, 0), hits[number]); for (expected) |e| { if (!std.mem.eql(u8, code, e[0])) continue; try expectEqual(e[1], hits[number]); found += 1; } } try expectEqual(expected.len, found); } /// The values of a list from `head` on, following `next` through the memory /// recorded as of `moment`, by the offsets of the node's description. fn listValues(moment: zt.store.Moment, node: types.Type, head: u64, out: []i32) ![]i32 { var at = head; var n: usize = 0; while (at != 0) : (n += 1) { out[n] = try Recording.read(moment, i32, at + node.field("value").?.offset); at = try Recording.read(moment, u64, at + node.field("next").?.offset); } return out[0..n]; } test "list: the recorded stores are the list, at every push and at the end" { var r = try Recording.open(recordings.list); defer r.close(); const arena = r.arena.allocator(); // From the variable to the shape of a node, through the type descriptions. const list = try r.variable("list", "*`struct node`"); const pointer = try types.parse(arena, try r.string(list.a[3])); const node = try types.parse(arena, try r.string(types.defId(pointer.pointer.named))); try expectEqual(@as(?u64, 16), node.size()); try expectEqualStrings("struct node", node.field("next").?.type.pointer.named); // Each push returns a list one longer: its squares, newest first. var buf: [8]i32 = undefined; var pushes: usize = 0; for (r.items) |item| { if (item.ev.kind != .ret or item.ev.a[0] != r.id("push")) continue; pushes += 1; const values = try listValues(try r.trace.moment(item.moment), node, item.ev.a[1], &buf); try expectEqual(pushes, values.len); for (values, 0..) |v, i| try expectEqual(@as(i32, @intCast((pushes - i) * (pushes - i))), v); } try expectEqual(@as(usize, 5), pushes); // Reversed in place, and left in the global. const end = try r.last(); const head = try Recording.read(end, u64, list.a[0]); try expectEqualSlices(i32, &.{ 1, 4, 9, 16, 25 }, try listValues(end, node, head, &buf)); const globals = try end.variables(arena); try expectEqual(@as(usize, 1), globals.len); try expectEqual(@as(u32, 0), globals[0].depth); } test "bfs: distances and visiting order, the graph known from the start" { var r = try Recording.open(recordings.bfs); defer r.close(); const end = try r.last(); const distance = try r.variable("distance", "[7]i32"); try expectEqual([7]i32{ 0, 1, 1, 2, 3, 4, -1 }, try Recording.read(end, [7]i32, distance.a[0])); const order = try r.variable("order", "[7]i32"); try expectEqual([7]i32{ 0, 1, 2, 3, 4, 5, 0 }, try Recording.read(end, [7]i32, order.a[0])); // The edge list is constant: in the first moment already. The matrix // main builds from it is symmetric and has each edge twice. const edges = try Recording.read(try r.trace.moment(0), [6][2]i32, (try r.variable("edges", "[6][2]i32")).a[0]); const adjacent = try Recording.read(end, [7][7]i32, (try r.variable("adjacent", "[7][7]i32")).a[0]); var ones: usize = 0; for (adjacent) |row| { for (row) |cell| ones += @intCast(cell); } try expectEqual(2 * edges.len, ones); for (edges) |e| try expectEqual(@as(i32, 1), adjacent[@intCast(e[1])][@intCast(e[0])]); // bfs returns how many it reached; its queue lived only during the call. const queue = try r.variable("queue", "[7]i32"); for (r.items) |item| { if (item.ev.kind != .ret or item.ev.a[0] != r.id("bfs")) continue; try expectEqual(@as(u64, 6), item.ev.a[1]); try expectEqual([6]i32{ 0, 1, 2, 3, 4, 5 }, try Recording.read(try r.trace.moment(item.moment), [6]i32, queue.a[0])); } try expectEqual(@as(usize, 1), r.count(.ret, r.id("bfs"))); for (try end.variables(r.arena.allocator())) |v| try expect(v.name != r.id("queue")); } test "only: nothing outside the selection, by function name" { var r = try Recording.open(recordings.sort_only); defer r.close(); // Of three functions and a global, bubble alone: its call, its five locals. var calls: usize = 0; var variables: usize = 0; var writes: usize = 0; for (r.items) |item| switch (item.ev.kind) { .call => { try expectEqual(r.id("bubble"), item.ev.a[0]); calls += 1; }, .variable => variables += 1, .mem_write => writes += 1, .line => try expect(item.ev.a[1] >= 11 and item.ev.a[1] <= 21), else => {}, }; try expectEqual(@as(usize, 1), calls); try expectEqual(@as(usize, 5), variables); try expect(writes > 13); try expect(r.ids.get("bubble") != null and r.ids.get("insertion") == null and r.ids.get("unsorted") == null); } test "mem: lines and calls in the whole file, stores in one function" { var r = try Recording.open(recordings.sort_mem); defer r.close(); var full = try Recording.open(recordings.sort); defer full.close(); // The file's name selects all of it: every line and call of the full recording. for ([_]zt.Kind{ .line, .call, .ret, .variable }) |kind| { var here: usize = 0; var there: usize = 0; for (r.items) |item| here += @intFromBool(item.ev.kind == kind); for (full.items) |item| there += @intFromBool(item.ev.kind == kind); try expectEqual(there, here); } // Stores only while insertion runs; the one before is the global's contents. var inside = false; var writes: usize = 0; for (r.items) |item| switch (item.ev.kind) { .call, .ret => inside = item.ev.kind == .call and item.ev.a[0] == r.id("insertion"), .mem_write => { try expect(inside or item.ev.a[0] == (try r.variable("unsorted", "[8]i32")).a[0]); writes += @intFromBool(inside); }, else => {}, }; try expect(writes > 13); } test "big: a megabyte written is 64 KiB recorded" { var r = try Recording.open(recordings.big); defer r.close(); const end = try r.last(); for ([_][]const u8{ "from", "to" }) |name| { const v = try r.variable(name, "[1048576]c8"); var bytes: [(64 << 10) + 1]u8 = undefined; var known: [bytes.len]bool = undefined; try end.read(v.a[0], &bytes, &known); try expect(std.mem.allEqual(u8, bytes[0 .. 64 << 10], 7)); try expect(std.mem.allEqual(bool, known[0 .. 64 << 10], true)); try expect(!known[64 << 10]); } // Four megabytes of globals and writes: four times 64 KiB, and the keyframe. try expect((try std.Io.Dir.cwd().statFile(io, recordings.big, .{})).size < 1 << 20); // As the runtime emits them, before the recorder: pieces, each saying how // much was written from its address on. const arena = r.arena.allocator(); const path = try arena.dupeSentinel(u8, recordings.big_program, 0); var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{}); defer session.close(); const Pieces = struct { name: u64 = 0, from: u64 = 0, bytes: u64 = 0, first: u64 = 0, last: u64 = 0, fn emit(ctx: *anyopaque, ev: *const zt.Event, payload: []const u8) anyerror!void { const p: *@This() = @ptrCast(@alignCast(ctx)); if (ev.kind == .string and std.mem.eql(u8, payload, "from")) p.name = ev.a[0]; if (ev.kind == .variable and ev.a[2] == p.name) p.from = ev.a[0]; // The memset, not the global's first contents. if (ev.kind != .mem_write or ev.a[0] -% p.from >= 1 << 20 or payload[0] != 7) return; try expect(payload.len <= 2048 and ev.a[1] >= payload.len); if (p.bytes == 0) p.first = ev.a[1]; p.bytes += payload.len; p.last = ev.a[1]; } }; var pieces: Pieces = .{}; while (try session.pump(.{ .ctx = &pieces, .emitFn = Pieces.emit }, std.time.ns_per_ms)) {} try expectEqual(@as(u64, 64 << 10), pieces.bytes); try expectEqual(@as(u64, 1 << 20), pieces.first); try expectEqual(@as(u64, (1 << 20) - (64 << 10) + 2048), pieces.last); } test "own: a program's own memcpy is traced when the program calls it, not when the runtime does" { var r = try Recording.open(recordings.own); defer r.close(); // Every mem_write the runtime emits it copies with this memcpy. try expect(r.count(.mem_write, (try r.variable("to", "[8]c8")).a[0]) > 0); try expectEqual(@as(usize, 1), r.count(.call, r.id("memcpy"))); try expectEqual(@as(usize, 1), r.count(.call, r.id("strlen"))); for (r.items) |item| { if (item.ev.kind == .ret and item.ev.a[0] == r.id("strlen")) try expectEqual(@as(u64, 7), item.ev.a[1]); } try expectEqualStrings("abcdefg", std.mem.sliceTo(&try Recording.read(try r.last(), [8]u8, (try r.variable("to", "[8]c8")).a[0]), 0)); } test "step: the ring holds the target at every line, its memory there to read" { var r = try Recording.open(recordings.sort); defer r.close(); const arena = r.arena.allocator(); var lines: usize = 0; for (r.items) |item| lines += @intFromBool(item.ev.kind == .line); const path = try arena.dupeSentinel(u8, recordings.sort_program, 0); var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{ .stop_mask = zt.Kind.line.bit() }); defer session.close(); const ring = &session.ring; // The array as the events so far say it is, against the target's own. var name: u64 = 0; var addr: u64 = 0; var told: [32]u8 = @splat(0); var compared: usize = 0; var stops: usize = 0; while (true) { const rec = ring.peek() orelse { if (session.exit_code != null) break; var status: u32 = 0; if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) session.exit_code = linux.W.EXITSTATUS(status) else ring.wait(std.time.ns_per_ms); continue; }; const ev = rec.ev.*; if (ev.kind == .string and std.mem.eql(u8, rec.payload, "bubbled")) name = ev.a[0]; if (ev.kind == .variable and ev.a[2] == name) addr = ev.a[0]; if (ev.kind == .mem_write and ev.a[0] >= addr and ev.a[0] + ev.a[1] <= addr + told.len) { @memcpy(told[ev.a[0] - addr ..][0..rec.payload.len], rec.payload); // From the first copy into it on; before, it is whatever the stack held. compared += @intFromBool(compared == 0 and rec.payload.len == told.len); } ring.advance(rec); if (ev.kind != .line) continue; // Held: it emits nothing more until resumed. while (ring.hdr.stopped.load(.acquire) == 0) std.atomic.spinLoopHint(); try expect(ring.peek() == null); var live: [32]u8 = undefined; const local = [_]std.posix.iovec{.{ .base = &live, .len = live.len }}; const remote = [_]std.posix.iovec_const{.{ .base = @ptrFromInt(addr), .len = live.len }}; try expectEqual(live.len, linux.process_vm_readv(session.pid, &local, &remote, 0)); if (compared > 0) { try expectEqualSlices(u8, &told, &live); compared += 1; } stops += 1; ring.resumeAll(); } try expectEqual(lines, stops); try expect(compared > lines - 16); try expectEqual(@as(?u8, 10), session.exit_code); try expectEqualSlices(i32, &.{ 1, 2, 3, 4, 5, 7, 8, 9 }, &std.mem.bytesToValue([8]i32, &told)); }