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
|
//! canim on its real recordings (made by the build, under ztrace's
//! debugger): finding moments, what a step changed, calls, pointers
//! followed, and the cursor's timetable for a step.
const std = @import("std");
const canim = @import("canim");
const anim = @import("anim");
const recordings = @import("recordings");
const Recording = canim.Recording;
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;
test "steps by line stop on lines of the program's own source, and no step stands still" {
inline for (.{ recordings.steps, recordings.hello, recordings.sort, recordings.list }) |program| {
const rec = canim.open(program);
// From the first call it shows: main, or the one a recording begins in.
var at = rec.calls[0].enter;
var stops: usize = 0;
while (at < rec.end() and stops < 400) : (stops += 1) {
const next = rec.next(.line, at);
try expect(next > at);
if (next < rec.end()) try expect(rec.reached[next]);
at = next;
}
try expect(stops > 4);
}
}
test "calls are a tree: fib(5) makes fifteen, each with what it was given and gave back" {
const rec = canim.open(recordings.steps);
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const nodes = try canim.calls.layout(arena.allocator(), rec, "fib");
try expectEqual(@as(usize, 15), nodes.len);
try expectEqual(@as(?u64, 5), rec.call("fib", 0).arg);
try expectEqual(@as(u64, 5), rec.call("fib", 0).result);
try expectEqual(@as(?u64, 1), rec.call("fib", 4).arg);
// A node is where it will always be: a parent over the middle of its children.
for (nodes) |n| if (n.parent) |p| try expect(nodes[p].level + 1 == n.level);
}
test "a program recorded by instruction, its variables told: calls, locals, and what they reach" {
const rec = canim.open(recordings.list);
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const reverse = rec.call("reverse", 0);
try expectEqual(@as(usize, 3), rec.allocations.len);
// The recording begins in it (`--from reverse`): the call is open from the first stop.
try expect(rec.own[reverse.enter] == 17 or rec.own[reverse.enter] == 18);
// A local is not its value until its call has stored to it.
const first = rec.lineMoment(18, reverse.enter);
const cur = rec.variable(arena.allocator(), rec.moment(first), "cur").?;
try expect(!rec.assigned(cur, first));
try expect(rec.assigned(cur, rec.lineMoment(21, reverse.enter)));
// Three nodes are reached from the program's pointers, each in the place its allocation gives it.
const things = canim.objects.reach(arena.allocator(), rec, rec.moment(rec.lineMoment(21, reverse.enter)), null);
try expectEqual(@as(usize, 3), things.len);
for (things) |o| try expect(o.slot.? < 3);
}
test "the program's four system calls are found, with what each was given" {
const rec = canim.open(recordings.hello);
var names: [4][]const u8 = undefined;
var n: usize = 0;
for (rec.syscalls) |call| {
if (call.enter < rec.call("main", 0).enter or n == names.len) continue;
names[n] = @import("ztrace").syscalls.name(call.nr) orelse "?";
n += 1;
}
try expectEqual(@as(usize, 4), n);
// glibc's `open` makes `openat`.
try std.testing.expectEqualStrings("openat", names[0]);
try std.testing.expectEqualStrings("read", names[1]);
try std.testing.expectEqualStrings("close", names[2]);
try std.testing.expectEqualStrings("write", names[3]);
}
test "a walked step is as long as what it changed: fire, a slot a level, the hold, the advance, the rest" {
const rec = canim.open(recordings.steps);
const scene = struct {
var at: canim.Cursor = undefined;
fn frame(s: *anim.Frame) void {
const r = canim.open(recordings.steps);
at = canim.cursor(s, r, r.lineMoment(10, r.call("main", 0).enter));
// The cascade as it was: `whole` (`tied` is the next test's).
at.levels = .{ .idea = .calls, .annotation = .whole };
}
};
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
var frame: anim.Frame = .{ .t = 0, .clock = 0, .in = undefined, .pointer = .{ 0, 0 }, .arena = arena.allocator() };
scene.frame(&frame);
const t = canim.theme.time;
// main's line calls fib(5): its two registers (rdi, rsp) 6 f apart,
// the stack 0.30 s after the second, the call's node when the
// projection from its way back arrives.
const from = rec.lineMoment(10, rec.call("main", 0).enter);
const call = scene.at.reading(from, rec.next(.line, from));
const second: f32 = 6.0 / 60.0;
try std.testing.expectApproxEqAbs(@as(f32, 2 * t.cascade + second), call.at[1], 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 2 * t.cascade + second + t.project.bracket + t.project.far), call.at[2], 1e-4);
try expect(call.total > 2.0 and call.total < 3.5);
// A line that changes nothing shown: fire, advance, rest.
var quiet = scene.at;
quiet.levels = .{ .cpu = false, .memory = false, .annotation = .whole };
const line = quiet.reading(rec.lineMoment(4, from), rec.lineMoment(6, from));
try std.testing.expectApproxEqAbs(t.fire + t.step + t.rest + t.step_per_row, line.total, 1e-3);
}
test "under tied a step goes cause to effect: the touch, the word, rsp's pin, the window" {
const rec = canim.open(recordings.steps);
const scene = struct {
var at: canim.Cursor = undefined;
fn frame(s: *anim.Frame) void {
const r = canim.open(recordings.steps);
at = canim.cursor(s, r, r.call("fib", 1).enter - 1);
}
};
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
var frame: anim.Frame = .{ .t = 0, .clock = 0, .in = undefined, .pointer = .{ 0, 0 }, .arena = arena.allocator() };
scene.frame(&frame);
const f = 1.0 / 60.0;
// fib(5)'s `call fib` (by instruction): the touch to the free word over rsp 18 to 30, the return
// address armed 30 to 42 and struck at 42, rsp's pin 48 to 72 (struck as it lands), the window 78 on.
const call = rec.call("fib", 1).enter - 1;
const pushed = scene.at.reading(call, call + 1);
try std.testing.expectApproxEqAbs(@as(f32, 18 * f), pushed.touch, 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 42 * f), pushed.at[1], 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 48 * f), pushed.pins[0], 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 78 * f), pushed.follow, 1e-4);
try expect(pushed.pins[1] < 0 and pushed.advance > pushed.follow);
// `push rbp`, at the callee's entry: the same order.
const push = scene.at.reading(call + 1, call + 2);
try expect(push.touch < push.at[1] and push.at[1] < push.pins[0] and push.pins[0] < push.follow);
// `mov rbp, rsp`: no word; rbp's pin from 18 f, and no window to follow.
const frame_ptr = scene.at.reading(call + 2, call + 3);
try expect(frame_ptr.touch < 0 and frame_ptr.pins[0] < 0 and frame_ptr.follow < 0);
try std.testing.expectApproxEqAbs(@as(f32, 18 * f), frame_ptr.pins[1], 1e-4);
// A load that fills a register (`mov rax, [rbp - 0x10]`, fib(1)'s `return n`): the word read
// (its touch 18 to 30, framed at 30) before rax strikes (48).
var at = call;
var buf: [256]u8 = undefined;
while (!(std.mem.eql(u8, rec.instruction(at, rec.register(at, "rip"), &buf).?.text, "mov rax, qword ptr [rbp - 0x10]") and rec.registersChanged(at, at + 1) & 1 != 0)) at += 1;
const load = scene.at.reading(at, at + 1);
try std.testing.expectApproxEqAbs(@as(f32, 30 * f), load.read, 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 48 * f), load.at[0], 1e-4);
// With `carry = .arrow` the value's way between: carried 36 to 54, rax struck at 66.
var carrying = scene.at;
carrying.levels.carry = .arrow;
const carried = carrying.reading(at, at + 1);
try std.testing.expectApproxEqAbs(@as(f32, 36 * f), carried.carry, 1e-4);
try std.testing.expectApproxEqAbs(@as(f32, 66 * f), carried.at[0], 1e-4);
// `pop rbp`: the word read (framed at 30), then rbp's pin (it takes the word), then rsp's, then the window.
var pop = at;
while (!std.mem.eql(u8, rec.instruction(pop, rec.register(pop, "rip"), &buf).?.text, "pop rbp")) pop += 1;
const popped = scene.at.reading(pop, pop + 1);
try std.testing.expectApproxEqAbs(@as(f32, 30 * f), popped.read, 1e-4);
try expect(popped.read < popped.pins[1] and popped.pins[1] < popped.pins[0] and popped.pins[0] < popped.follow);
}
/// The first moment whose pc is in the function named `name` (as the recording names it: `libc.so.6!open`).
fn firstIn(rec: *const Recording, name: []const u8) u64 {
for (rec.registers, 0..) |regs, i| {
const at = rec.strings.get(regs.rip) orelse continue;
if (std.mem.startsWith(u8, at, name) and at.len > name.len and at[name.len] == '+') return i;
}
unreachable;
}
/// The `blocks` lens's pane, its body: what the graph is laid out for.
const lens_room = [2]f32{ 880 - 4, 344 - 24 - 2 };
/// The moment the sort scene opens at: the inner loop's test, about to compare 31 with 12.
fn sortStart(rec: *const Recording) u64 {
var start = rec.call("sort", 0).enter;
while (rec.next(.over, rec.next(.over, start)) < rec.call("swap", 0).enter) start = rec.next(.over, start);
return start;
}
/// Whether node `n`'s centre is on ring `r`.
fn onRing(n: canim.graph.Node, r: canim.graph.Ring) bool {
const dx = n.x + n.w / 2 - r.c[0];
const dy = n.y + n.h / 2 - r.c[1];
return @abs(@sqrt(dx * dx + dy * dy) - r.r) < 0.5;
}
test "sort's graph: two rings from the code alone, the inner touching the outer at its header, whole in the lens" {
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const graph = canim.graph;
const rec = canim.open(recordings.sort);
const start = sortStart(rec);
const pc = rec.registers[start].rip;
const g = graph.layout(arena.allocator(), rec, start, pc, .rings, lens_room, start).?;
try expect(g.exact and g.text);
try expectEqual(@as(usize, 11), g.nodes.len);
try expectEqual(@as(usize, 0), g.foldedBlocks());
const at = struct {
fn of(gr: canim.graph.Graph, off: u64) canim.graph.Node {
return gr.nodes[gr.nodeOf(gr.start + off).?];
}
}.of;
// Two rings: the outer loop's (the test at +78), the inner's (its test at +8a).
try expectEqual(@as(usize, 2), g.rings.len);
const outer = if (g.nodes[g.rings[0].header].start == g.start + 0x78) g.rings[0] else g.rings[1];
const inner = if (g.nodes[g.rings[0].header].start == g.start + 0x8a) g.rings[0] else g.rings[1];
try expect(g.nodes[outer.header].start == g.start + 0x78 and g.nodes[inner.header].start == g.start + 0x8a);
for ([_]u64{ 0x78, 0x84, 0x8a, 0xc3, 0xfd, 0xff }) |off| try expect(onRing(at(g, off), outer));
for ([_]u64{ 0x8a, 0x95, 0xbc, 0xc5 }) |off| try expect(onRing(at(g, off), inner));
for ([_]u64{ 0x0, 0x10d }) |off| try expect(!onRing(at(g, off), outer) and !onRing(at(g, off), inner));
// The inner ring outside the outer, touching it at +8a: the outer's 3 o'clock, the inner's 9.
const h = at(g, 0x8a);
try std.testing.expectApproxEqAbs(outer.c[0] + outer.r, h.x + h.w / 2, 0.5);
try std.testing.expectApproxEqAbs(inner.c[0] - inner.r, h.x + h.w / 2, 0.5);
try std.testing.expectApproxEqAbs(outer.c[1], inner.c[1], 0.5);
// The headers at 9 o'clock; +0 left of +78 on its line, +10d under it.
const o = at(g, 0x78);
try std.testing.expectApproxEqAbs(outer.c[0] - outer.r, o.x + o.w / 2, 0.5);
const entry = at(g, 0x0);
try expect(entry.y == o.y and entry.x + entry.w < o.x);
const exit = at(g, 0x10d);
try expect(exit.y > o.y + o.h and exit.x < o.x + o.w and exit.x + exit.w > o.x);
// Any two pills 12 apart.
for (g.nodes, 0..) |a, i| for (g.nodes[i + 1 ..]) |b| {
const dx = @max(b.x - (a.x + a.w), a.x - (b.x + b.w), 0);
const dy = @max(b.y - (a.y + a.h), a.y - (b.y + b.h), 0);
try expect(dx * dx + dy * dy >= 12 * 12 - 0.01);
};
// Whole in the lens's pane, no pan.
try expect(g.w <= lens_room[0] and g.h <= lens_room[1]);
}
test "sort's graph says nothing from after the moment: the same layout at every moment, quiet until reached" {
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const graph = canim.graph;
const rec = canim.open(recordings.sort);
const start = sortStart(rec);
const later = rec.call("swap", 5).enter - 1;
const a = graph.layout(arena.allocator(), rec, start, rec.registers[start].rip, .rings, lens_room, start).?;
const b = graph.layout(arena.allocator(), rec, later, rec.registers[later].rip, .rings, lens_room, start).?;
// Where every block is, and every edge's way: the code's, not the run's.
try expectEqual(a.nodes.len, b.nodes.len);
for (a.nodes, b.nodes) |x, y| try expect(x.x == y.x and x.y == y.y and x.w == y.w);
for (a.edges, b.edges) |x, y| {
try expect(x.n == y.n);
for (x.path(), y.path()) |p, q| try expect(p[0] == q[0] and p[1] == q[1]);
}
// At the opening: every block reached but the swap and the way out; no count, no edge, into either.
for (a.nodes) |n| {
const off = n.start - a.start;
try expectEqual(off == 0xc5 or off == 0x10d, n.visits == 0);
}
for (a.edges) |e| if (a.nodes[e.to].visits == 0) try expectEqual(@as(u32, 0), e.count);
// The inner loop's `jle` not taken so far; its turns none yet.
const jle = a.edgeOf(a.nodeOf(a.start + 0x8a).?, a.nodeOf(a.start + 0xbc).?).?;
try expectEqual(@as(u32, 0), a.edges[jle].count);
const turn = a.edgeOf(a.nodeOf(a.start + 0xc5).?, a.nodeOf(a.start + 0x8a).?).?;
try expect(a.edges[turn].back and a.edges[turn].count == 0 and b.edges[turn].count == 5);
// The trail: taken edges only, the newest into the pc's block.
for (a.trail) |maybe| try expect(a.edges[maybe.?].count > 0);
// Three different edges: the last three taken, round the outer loop and into the inner.
try expect(a.trail[0].? != a.trail[1].? and a.trail[1].? != a.trail[2].? and a.trail[0].? != a.trail[2].?);
try expectEqual(b.here.?, b.edges[b.trail[0].?].to);
}
test "reverse's graph: one ring of two blocks, the way in from the left, the way out down" {
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const graph = canim.graph;
const rec = canim.open(recordings.list);
const at = firstIn(rec, "reverse");
const g = graph.layout(arena.allocator(), rec, at, rec.registers[at].rip, .rings, lens_room, at).?;
try expectEqual(@as(usize, 4), g.nodes.len);
try expectEqual(@as(usize, 1), g.rings.len);
var on: usize = 0;
for (g.nodes) |n| on += @intFromBool(onRing(n, g.rings[0]));
try expectEqual(@as(usize, 2), on);
// The recording begins inside it: its first block was entered once.
try expectEqual(@as(u32, 1), g.nodes[0].visits);
try expect(g.w <= lens_room[0] and g.h <= lens_room[1]);
}
test "libc's open at its syscall: what it has not reached folded, a fold opening as the run gets there" {
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const graph = canim.graph;
const rec = canim.open(recordings.hello);
var at = firstIn(rec, "libc.so.6!open");
var buf: [256]u8 = undefined;
while (!std.mem.eql(u8, rec.instruction(at, rec.registers[at].rip, &buf).?.text, "syscall")) at += 1;
const a = graph.layout(arena.allocator(), rec, at, rec.registers[at].rip, .rings, lens_room, at).?;
// Twenty blocks (two of `nop` padding left out); no loop: layers.
try expectEqual(@as(usize, 20), a.blocks);
try expectEqual(@as(usize, 0), a.rings.len);
for (a.edges) |e| try expect(!e.back);
// Folded: only blocks not reached by the moment, two folds (the cancellable call's, the way back from the kernel).
var folds: usize = 0;
for (a.nodes) |n| if (n.folded > 0) {
folds += 1;
try expectEqual(@as(u32, 0), n.visits);
};
try expectEqual(@as(usize, 2), folds);
try expectEqual(@as(usize, 15), a.foldedBlocks());
// `+5b … · 7`, the cancellable call's; `+be … · 8`, the way back from the kernel; +d0 alone stays a quiet pill.
try expectEqual(@as(u32, 7), a.nodes[a.nodeOf(a.start + 0x5b).?].folded);
try expectEqual(@as(u32, 8), a.nodes[a.nodeOf(a.start + 0xbe).?].folded);
try expectEqual(@as(u32, 0), a.nodes[a.nodeOf(a.start + 0xd0).?].folded);
try expect(a.w <= lens_room[0] and a.h <= lens_room[1]);
// At its syscall: the blocks before entered once, those after not yet.
try expectEqual(a.nodeOf(rec.registers[at].rip).?, a.here.?);
for (a.nodes) |n| if (n.folded == 0 and n.visits > 0) try expectEqual(@as(u32, 1), n.visits);
// On to its block's last stop: the same layout. A step on, into the way back from the kernel: its fold open, the other still folded.
const end = graph.blockEnd(rec, at);
const b = graph.layout(arena.allocator(), rec, end, rec.registers[end].rip, .rings, lens_room, at).?;
for (a.nodes, b.nodes) |x, y| try expect(x.x == y.x and x.y == y.y and x.folded == y.folded);
const c = graph.layout(arena.allocator(), rec, end + 1, rec.registers[end + 1].rip, .rings, lens_room, at).?;
try expect(c.open != a.open);
try expectEqual(@as(u32, 0), c.nodes[c.here.?].folded);
try expectEqual(@as(u32, 1), c.nodes[c.here.?].visits);
var still: usize = 0;
for (c.nodes) |n| still += @intFromBool(n.folded > 0);
try expectEqual(@as(usize, 1), still);
}
test "the source follows the pc into musl's own files and back to main's line" {
// musl is built from Zig's sources with the program: its files are always the build's to give.
const rec = canim.open(recordings.musl);
const main = rec.call("main", 0);
try std.testing.expectEqualStrings("hello.c", rec.sources[rec.shown[main.enter].src].name());
var files: [3]bool = @splat(false);
var back = false;
for (rec.shown[main.enter..], main.enter..) |s, i| {
const name = rec.sources[s.src].name();
for ([_][]const u8{ "open.c", "__syscall_cp.c", "syscall_arch.h" }, &files) |want, *seen| seen.* = seen.* or (s.here and std.mem.eql(u8, name, want));
// Where it is on a line of musl's, the panel shows it: never main's held over.
if (s.here) try expect(rec.sourced(i));
back = back or (files[0] and s.here and std.mem.eql(u8, name, "hello.c") and s.line == 6);
}
for (files) |seen| try expect(seen);
try expect(back);
}
|