diff options
Diffstat (limited to 'src/instr/test.zig')
| -rw-r--r-- | src/instr/test.zig | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/src/instr/test.zig b/src/instr/test.zig new file mode 100644 index 0000000..3b67c62 --- /dev/null +++ b/src/instr/test.zig @@ -0,0 +1,464 @@ +//! 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)); +} |
