summaryrefslogtreecommitdiff
path: root/src/instr/test.zig
blob: 3b67c626c80904ea7f2d1fa24f9c46ca0300fc88 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
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));
}