summaryrefslogtreecommitdiff
path: root/src/agent/check.zig
blob: 865766540d625368e67764bbd311fba9a04a66d5 (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
//! The agent's tests: what a recording made through it has to contain.
//! `zig build test-agent` records real targets under `ztrace run` and runs
//! this on each recording: `check SCENARIO FILE [ARGUMENT]`.
const std = @import("std");
const zt = @import("ztrace");
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;
const expectEqualStrings = std.testing.expectEqualStrings;

const Item = struct { moment: u64, ev: zt.Event, payload: []const u8 };

const Recording = struct {
    arena: std.mem.Allocator,
    trace: *zt.Trace,
    items: []const Item,

    fn count(r: Recording, kind: zt.Kind) usize {
        var n: usize = 0;
        for (r.items) |item| n += @intFromBool(item.ev.kind == kind);
        return n;
    }

    /// The address ranges of the file whose path ends in `name`.
    fn mapped(r: Recording, name: []const u8) ![]const [2]u64 {
        var ranges: std.ArrayList([2]u64) = .empty;
        for (r.items) |item| {
            if (item.ev.kind == .map and std.mem.endsWith(u8, item.payload, name)) try ranges.append(r.arena, .{ item.ev.a[0], item.ev.a[0] + item.ev.a[1] });
        }
        return ranges.items;
    }

    /// The `variable` event of the variable called `name`.
    fn variable(r: Recording, name: []const u8) !Item {
        var id: ?u64 = null;
        for (r.items) |item| {
            if (item.ev.kind == .string and std.mem.eql(u8, item.payload, name)) id = item.ev.a[0];
            if (item.ev.kind == .variable and item.ev.a[2] == id) return item;
        }
        return error.NoSuchVariable;
    }

    /// The 16 numbers the sorting targets sort, as recorded at `moment`.
    fn numbers(r: Recording, moment: u64, addr: u64) ![16]i32 {
        var out: [16]i32 = undefined;
        var known: [64]bool = undefined;
        try (try r.trace.moment(moment)).read(addr, std.mem.asBytes(&out), &known);
        try expect(std.mem.allEqual(bool, &known, true));
        return out;
    }
};

fn within(ranges: []const [2]u64, addr: u64) bool {
    for (ranges) |range| {
        if (addr >= range[0] and addr < range[1]) return true;
    }
    return false;
}

fn fib(n: u64) u64 {
    return if (n < 2) n else fib(n - 1) + fib(n - 2);
}

pub fn main(init: std.process.Init) !void {
    const arena = init.arena.allocator();
    const args = try init.minimal.args.toSlice(arena);
    if (args.len < 3) return error.Usage;
    var trace = try zt.Trace.open(init.gpa, init.io, args[2]);
    defer trace.close();
    var items: std.ArrayList(Item) = .empty;
    for (0..trace.len) |index| {
        var events = try (try trace.moment(index)).events(arena);
        while (events.next()) |item| try items.append(arena, .{ .moment = index, .ev = item.ev, .payload = item.payload });
    }
    const r: Recording = .{ .arena = arena, .trace = &trace, .items = items.items };
    const argument: []const u8 = if (args.len > 3) args[3] else "";

    // Whatever was asked for, the agent says where things are and who runs.
    try expect(r.count(.map) >= 3);
    try expect(r.count(.thread_start) >= 1);

    const scenario = args[1];
    if (std.mem.eql(u8, scenario, "list")) {
        try list(r, try std.fmt.parseInt(usize, argument, 10));
    } else if (std.mem.eql(u8, scenario, "fib")) {
        try calls(r, try std.fmt.parseInt(u64, argument, 10));
    } else if (std.mem.eql(u8, scenario, "sort")) {
        try sorted(r, argument);
    } else if (std.mem.eql(u8, scenario, "api")) {
        try annotated(r);
    } else if (std.mem.eql(u8, scenario, "syscalls")) {
        try syscalls(r);
    } else return error.NoSuchScenario;
}

/// agent_list N: N nodes allocated and freed, and nothing the program
/// allocated left alive.
fn list(r: Recording, n: usize) !void {
    const program = try r.mapped("agent_list");
    try expect(program.len > 0);
    const Block = struct { size: u64, pc: u64 };
    var live: std.AutoHashMapUnmanaged(u64, Block) = .empty;
    var nodes: usize = 0;
    var own: usize = 0;
    var resized: usize = 0;
    for (r.items) |item| switch (item.ev.kind) {
        .alloc => {
            const ptr = item.ev.a[0];
            const pc = item.ev.a[2];
            const how: zt.event.Alloc = @enumFromInt(item.ev.aux);
            // Only a realloc in place may name a pointer that is alive.
            if (live.contains(ptr)) {
                try expectEqual(zt.event.Alloc.realloc, how);
                resized += 1;
            }
            try live.put(r.arena, ptr, .{ .size = item.ev.a[1], .pc = pc });
            if (!within(program, pc)) continue;
            own += 1;
            if (how == .malloc and item.ev.a[1] == 16) nodes += 1;
        },
        .free => {
            // What was allocated before the agent attached is not ours to know.
            const block = live.fetchRemove(item.ev.a[0]) orelse continue;
            if (within(program, block.value.pc)) try expect(within(program, item.ev.a[1]));
        },
        else => {},
    };
    try expectEqual(n, nodes);
    // The nodes, the vector, the two aligned blocks, and the vector again each time it grew.
    try expect(own >= n + 3 + resized);
    var left = live.valueIterator();
    while (left.next()) |block| try expect(!within(program, block.pc));
}

/// agent_fib N hooked at fib: every call with its argument, every return
/// with fib of that argument, each a moment.
fn calls(r: Recording, n: u64) !void {
    var stack: std.ArrayList(u64) = .empty;
    var seen: u64 = 0;
    var last_moment: ?u64 = null;
    for (r.items) |item| switch (item.ev.kind) {
        .call => {
            const regs = std.mem.bytesToValue(zt.Regs, item.payload);
            try expectEqual(item.ev.a[0], regs.rip);
            try expectEqual(item.ev.a[2], regs.rsp);
            if (stack.items.len == 0) try expectEqual(n, regs.rdi) else try expect(regs.rdi + 1 == stack.getLast() or regs.rdi + 2 == stack.getLast());
            try stack.append(r.arena, regs.rdi);
            seen += 1;
            try expect(last_moment == null or item.moment > last_moment.?);
            last_moment = item.moment;
            // The recorder folded the registers into the moment the call ends.
            try expectEqual(regs.rdi, (try (try r.trace.moment(item.moment)).regs(item.ev.tid)).?.rdi);
        },
        .ret => {
            try expectEqual(fib(stack.pop().?), item.ev.a[1]);
            try expect(item.moment > last_moment.?);
            last_moment = item.moment;
        },
        else => {},
    };
    try expectEqual(@as(usize, 0), stack.items.len);
    try expectEqual(2 * fib(n + 1) - 1, seen);
}

/// A sorting target: the variable `name` is a permutation of 0..15 at every
/// moment, changes along the way, and ends sorted.
fn sorted(r: Recording, name: []const u8) !void {
    const variable = try r.variable(name);
    try expectEqual(@as(u64, 64), variable.ev.a[1]);
    var before = try r.numbers(variable.moment, variable.ev.a[0]);
    var states: usize = 1;
    for (variable.moment..r.trace.len) |moment| {
        const now = try r.numbers(moment, variable.ev.a[0]);
        var present: u16 = 0;
        for (now) |v| present |= @as(u16, 1) << @intCast(v);
        try expectEqual(@as(u16, 0xffff), present);
        states += @intFromBool(!std.mem.eql(i32, &now, &before));
        before = now;
    }
    try expect(states >= 8);
    try expect(std.sort.isSorted(i32, &before, {}, std.sort.asc(i32)));
}

/// agent_api: a mark after each insertion, by when the prefix up to it is
/// sorted in the recording; the snapshot of the checksum; the array sorted
/// at the end.
fn annotated(r: Recording) !void {
    const variable = try r.variable("numbers");
    var next: u64 = 1;
    var checksum: ?u64 = null;
    for (r.items) |item| switch (item.ev.kind) {
        .mark => if (std.mem.eql(u8, item.payload, "inserted")) {
            try expectEqual(next, item.ev.a[0]);
            const now = try r.numbers(item.moment, variable.ev.a[0]);
            try expect(std.sort.isSorted(i32, now[0 .. next + 1], {}, std.sort.asc(i32)));
            next += 1;
        } else {
            try expectEqualStrings("done", item.payload);
            try expectEqual(checksum.?, item.ev.a[0]);
        },
        // The snapshot: 8 bytes that are not in the array.
        .mem_write => if (item.ev.a[1] == 8 and item.ev.a[0] -% variable.ev.a[0] >= 64) {
            checksum = std.mem.readInt(u64, item.payload[0..8], .little);
        },
        else => {},
    };
    try expectEqual(@as(u64, 16), next);
    try sorted(r, "numbers");
}

/// agent_sys: what it wrote, from which thread, and every syscall entered
/// is left, innermost first.
fn syscalls(r: Recording) !void {
    const main_tid = for (r.items) |item| {
        if (item.ev.kind == .thread_start) break item.ev.tid;
    } else unreachable;
    var open: std.AutoHashMapUnmanaged(u32, std.ArrayList(Item)) = .empty;
    var written: std.AutoArrayHashMapUnmanaged(u32, std.ArrayList(u8)) = .empty;
    var fd: ?u64 = null;
    for (r.items) |item| switch (item.ev.kind) {
        .thread_start => try expectEqual(@as(u64, item.ev.tid), item.ev.a[0]),
        .syscall_enter => {
            const stack = try open.getOrPutValue(r.arena, item.ev.tid, .empty);
            try stack.value_ptr.append(r.arena, item);
        },
        .syscall_exit => {
            const result = item.ev.a[0];
            const enter = (if (open.getPtr(item.ev.tid)) |stack| stack.pop() else null) orelse {
                // A forked child's first syscall event is its side of the parent's clone.
                try expectEqual(@intFromEnum(std.os.linux.SYS.clone), item.ev.aux);
                try expectEqual(@as(u64, 0), result);
                continue;
            };
            try expectEqual(enter.ev.aux, item.ev.aux);
            switch (@as(std.os.linux.SYS, @enumFromInt(item.ev.aux))) {
                .openat => if (std.mem.eql(u8, enter.payload, "/dev/null")) {
                    fd = result;
                },
                .write => if (enter.ev.a[0] == fd) {
                    try expectEqual(enter.ev.a[2], result);
                    try expectEqual(result, enter.payload.len);
                    const text = try written.getOrPutValue(r.arena, item.ev.tid, .empty);
                    try text.value_ptr.appendSlice(r.arena, enter.payload);
                },
                .getpid => try expectEqual(@as(u64, main_tid), result),
                else => {},
            }
        },
        else => {},
    };
    // Only a thread's last syscall has no exit.
    var stacks = open.valueIterator();
    while (stacks.next()) |stack| {
        if (stack.items.len == 0) continue;
        try expectEqual(@as(usize, 1), stack.items.len);
        const last: std.os.linux.SYS = @enumFromInt(stack.items[0].ev.aux);
        try expect(last == .exit or last == .exit_group);
    }
    try expectEqual(@as(usize, 3), r.count(.thread_start));
    try expectEqual(@as(usize, 3), written.count());
    try expectEqualStrings("hello from main\nmasked\nsignal\nchild exited 3\n", written.get(main_tid).?.items);
    try expectEqualStrings("thread\n", written.values()[1].items);
    try expectEqualStrings("child\n", written.values()[2].items);
}