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
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
|
//! A recording, open for a scene: the trace, the thread the components
//! show, and an index made once by reading every moment in order (calls as
//! a tree, syscalls, marks, allocations, the source line after each moment,
//! which registers and bytes each moment changed, every string). Components
//! read the program's state through `moment`; scenes find where to go with
//! `next` and the functions after it.
const std = @import("std");
const zt = @import("ztrace");
const pardes = @import("pardes-syntax");
pub const types = @import("ztrace-types");
const store = zt.store;
const Recording = @This();
pub const Moment = store.Moment;
pub const Variable = store.Variable;
/// One call, from the `call` event to its `ret`.
pub const Call = struct {
/// A string id: `name(function)`.
function: u64,
parent: ?u32,
/// Calls it is inside of.
depth: u32,
/// The stack pointer as it was entered.
sp: u64,
/// The moments that hold its `call` and its `ret` (null: never returned).
enter: u64,
exit: ?u64 = null,
/// Its first argument, as far as the recording tells: the first
/// variable declared in it (`parameter`: where, how many bytes), else
/// `rdi` as it was called.
arg: ?u64 = null,
parameter: ?Span = null,
/// That variable's name, a string id; null when the recording names none.
parameter_name: ?u64 = null,
result: u64 = 0,
/// On the stack at moment `i`.
pub fn active(c: Call, i: u64) bool {
return c.enter <= i and (c.exit == null or c.exit.? > i);
}
};
pub const Syscall = struct {
nr: u16,
args: [6]u64,
/// The string or buffer its first pointer argument points at, when the
/// recorder captured it (a path, the bytes written).
text: []const u8 = "",
/// The moment that holds its entry, and its exit (null: it never came back).
enter: u64,
exit: ?u64 = null,
result: u64 = 0,
};
pub const Mark = struct { moment: u64, text: []const u8 };
/// An allocation ever made: its place in this list is its identity, the
/// same in every view.
pub const Born = struct { ptr: u64, size: u64, moment: u64, event: u64 };
/// A run of bytes a moment changed, or read.
pub const Span = struct { addr: u64, len: u64 };
/// What the instruction at a moment's pc is about to do to memory (the
/// debugger's `touch`): `how` 1 reads there, 2 writes there, 3 both.
pub const Touch = struct { addr: u64, len: u64, how: u8 };
/// Where the instruction at a moment's pc goes, if it is a call, a jump
/// or a return (the debugger's `branch`), and whether it will.
pub const Branch = struct { to: u64, taken: bool, kind: enum(u8) { none, call, jump, ret } };
/// The source line an instruction was compiled from, as the recording saw
/// the program stopped there.
pub const CodeLine = struct { addr: u64, line: u32 };
/// A variable on the stack, declared at a moment.
pub const Declared = struct { moment: u64, addr: u64 };
/// Where a cursor's step may end.
pub const Stop = enum {
/// The next moment, whatever the recorder made one: an instruction, a line.
moment,
/// The next moment on another line of the program's source.
line,
/// The same, not counting lines inside calls made on the way: step over.
over,
/// The next call or return.
call,
/// The next syscall.
syscall,
};
trace: zt.Trace,
/// What `open` was given: the recording's bytes, to know it again.
key: [*]const u8,
/// The source file the recording's lines are in, and its text.
file: []const u8,
source: []const u8,
/// Its functions, as pardes outlines them, and how many lines it has.
functions: []const Function = &.{},
line_count: u32 = 0,
/// The thread shown: the first to make an event.
tid: u32 = 0,
/// The source line `tid` is on after each moment (line 0: none yet), in
/// whatever file; and the last line of `file` it was on, which is where
/// the program's own source stands while a library runs.
lines: []store.Line = &.{},
own: []u32 = &.{},
/// Whether each moment reached a line of `file`: a `line` event of its own.
reached: []bool = &.{},
/// How many calls deep `tid` is after each moment.
depths: []u32 = &.{},
calls: []Call = &.{},
syscalls: []Syscall = &.{},
marks: []Mark = &.{},
allocations: []Born = &.{},
/// The registers of `tid` after each moment (the last known, before any).
registers: []zt.Regs = &.{},
write_spans: Spans = .{},
/// What instructions stored, changed or not (a recording by instruction).
store_spans: Spans = .{},
read_spans: Spans = .{},
/// For each moment, what the instruction at its pc touches and where it branches.
insn_touches: [][2]?Touch = &.{},
insn_branches: []?Branch = &.{},
/// Every instruction address the program stopped at in its own source,
/// with that line, in address order.
code_lines: []CodeLine = &.{},
/// Each local variable's declaration, in the order they came: in a
/// recording that tells no calls, what says when a local began.
locals: []Declared = &.{},
/// The variables declared outside the stack (globals): bytes a lens draws.
globals: []Span = &.{},
strings: std.AutoHashMapUnmanaged(u64, []const u8) = .empty,
arena: std.heap.ArenaAllocator,
const gpa = std.heap.smp_allocator;
/// Recordings opened so far. They live as long as the process: a scene's
/// `frame` runs every frame and asks again.
var opened: std.ArrayList(*Recording) = .empty;
/// A recording as the build embeds it in `recordings`: a `.ztrace` file's
/// bytes (`trace`), the source it ran (`source`) and its name (`file`).
/// Opened and indexed the first time.
pub fn open(program: anytype) *Recording {
for (opened.items) |r| if (r.key == program.trace.ptr) return r;
const r = load(program.trace, program.file, program.source) catch |err| std.debug.panic("canim: cannot open the recording of {s}: {t}", .{ program.file, err });
opened.append(gpa, r) catch @panic("canim: out of memory");
return r;
}
fn load(bytes: []const u8, file: []const u8, source: []const u8) !*Recording {
// The trace reads a file: give it one in memory.
const linux = std.os.linux;
const rc = linux.memfd_create("canim", linux.MFD.CLOEXEC);
if (linux.errno(rc) != .SUCCESS) return error.NoMemfd;
const fd: linux.fd_t = @intCast(rc);
defer _ = linux.close(fd);
var done: usize = 0;
while (done < bytes.len) {
const n = linux.write(fd, bytes[done..].ptr, bytes.len - done);
if (linux.errno(n) != .SUCCESS) return error.WriteFailed;
done += n;
}
var path_buf: [64]u8 = undefined;
const path = try std.fmt.bufPrint(&path_buf, "/proc/self/fd/{d}", .{fd});
const r = try gpa.create(Recording);
errdefer gpa.destroy(r);
r.* = .{ .trace = try .open(gpa, std.Io.Threaded.global_single_threaded.io(), path), .key = bytes.ptr, .file = file, .source = source, .arena = .init(gpa) };
if (r.trace.len == 0) return error.EmptyRecording;
r.functions = try outline(r.arena.allocator(), source, file);
r.line_count = @intCast(std.mem.count(u8, source, "\n") + @intFromBool(source.len > 0 and source[source.len - 1] != '\n'));
try r.index();
return r;
}
/// The instruction at `addr` as the debugger disassembled it at moment
/// `i` (`text` is Intel syntax, in `buf`: give it 212 bytes or more); null
/// where it recorded none. `back` is how long the instruction before it in
/// its function is (0: not known); `line`, the line of the program's own
/// source it was compiled from (null: another file's, or not known);
/// `params`, a direct call's callee's parameter count.
pub fn instruction(r: *const Recording, i: u64, addr: u64, buf: []u8) ?struct { len: u8, back: u8, text: []const u8, line: ?u32, params: ?u8 } {
const found = (zt.telescope.instruction(r.moment(i), addr, buf) catch return null) orelse return null;
var line: ?u32 = null;
if (found.line) |l| if (std.mem.eql(u8, std.fs.path.basename(r.name(l.file)), r.file)) {
line = l.line;
};
return .{ .len = found.len, .back = found.back, .text = found.text, .line = line orelse r.lineOf(addr), .params = found.params };
}
/// The source line the instruction at `addr` was compiled from, for a
/// recording whose instructions do not carry it (`instruction` gives it
/// where they do): where the program stopped there, the line it was on;
/// else the line of the nearest instruction before it that it stopped at,
/// close by. Null where nothing is known.
pub fn lineOf(r: *const Recording, addr: u64) ?u32 {
var lo: usize = 0;
var hi: usize = r.code_lines.len;
while (lo < hi) {
const mid = (lo + hi) / 2;
if (r.code_lines[mid].addr <= addr) lo = mid + 1 else hi = mid;
}
if (lo == 0) return null;
const near = r.code_lines[lo - 1];
return if (addr - near.addr <= 96) near.line else null;
}
/// The line of the program's own source moment `i` is on; null where it is
/// elsewhere (a library's code, a stop with no line).
pub fn ownLine(r: *const Recording, i: u64) ?u32 {
const l = r.lines[@min(i, r.end())];
if (l.line == 0 or !std.mem.eql(u8, std.fs.path.basename(r.name(l.file)), r.file)) return null;
return l.line;
}
/// The first line a source panel of `fit` lines shows when the program is
/// on `line`: the whole file when it fits; else a window that has the line
/// in its middle third, and is the same window for every line of that
/// third, so that the text moves only when the program has moved on.
pub fn viewFirst(r: *const Recording, fit: u32, line: u32) u32 {
if (r.line_count <= fit or fit < 3) return 1;
const third = fit / 3;
const band = (@max(line, 1) - 1) / third;
return std.math.clamp(@as(u32, @intCast(@max(@as(i64, band) - 1, 0))) * third + 1, 1, r.line_count - fit + 1);
}
/// Runs of bytes, a list for each moment.
const Spans = struct {
all: []Span = &.{},
/// Where each moment's end in `all`.
ends: []u32 = &.{},
/// Those of the moments after `from`, up to `to`.
fn of(s: Spans, from: u64, to: u64) []const Span {
if (to >= s.ends.len or from >= to) return &.{};
return s.all[s.ends[from]..s.ends[to]];
}
};
/// shortcut: reads the whole recording at open (about 5 us a moment) and
/// follows one thread; a recording of millions of moments wants this stored
/// in the file by the recorder.
fn index(r: *Recording) !void {
const arena = r.arena.allocator();
var lines: std.ArrayList(store.Line) = .empty;
var own: std.ArrayList(u32) = .empty;
var reached: std.ArrayList(bool) = .empty;
var depths: std.ArrayList(u32) = .empty;
var calls: std.ArrayList(Call) = .empty;
var syscalls: std.ArrayList(Syscall) = .empty;
var marks: std.ArrayList(Mark) = .empty;
var allocations: std.ArrayList(Born) = .empty;
var registers: std.ArrayList(zt.Regs) = .empty;
var writes: std.ArrayList(Span) = .empty;
var write_ends: std.ArrayList(u32) = .empty;
var stores: std.ArrayList(Span) = .empty;
var store_ends: std.ArrayList(u32) = .empty;
var reads: std.ArrayList(Span) = .empty;
var read_ends: std.ArrayList(u32) = .empty;
var touch_list: std.ArrayList([2]?Touch) = .empty;
var locals: std.ArrayList(Declared) = .empty;
var globals: std.ArrayList(Span) = .empty;
// What the instruction at a stop is about to read is read by the step after it.
var pending: [2]?Touch = .{ null, null };
var branch_list: std.ArrayList(?Branch) = .empty;
var code_lines: std.AutoHashMapUnmanaged(u64, u32) = .empty;
defer code_lines.deinit(gpa);
var open_calls: std.ArrayList(u32) = .empty;
defer open_calls.deinit(gpa);
// A recording of instructions tells no calls: they are read off the
// open_calls pointer, until its first `call` event says otherwise.
var derived: std.ArrayList(u64) = .empty;
defer derived.deinit(gpa);
var told = false;
var before: ?zt.Regs = null;
var count: u64 = 0;
// Which bytes any moment so far has recorded, 64 to a word of bits.
var seen: std.AutoHashMapUnmanaged(u64, u64) = .empty;
defer seen.deinit(gpa);
// For each write of the moment in hand: whether the debugger saw it (a
// snapshot of memory at a stop) and no store of the program's told it.
var snapshots: std.ArrayList(bool) = .empty;
defer snapshots.deinit(gpa);
for (0..r.trace.len) |i| {
const m = try r.trace.moment(i);
var events = try m.events(gpa);
defer events.deinit(gpa);
const first_call = calls.items.len;
const first_write = writes.items.len;
var line_at: ?u64 = null;
var line_file: ?u64 = null;
var stepped = false;
var broke = false;
var takes_nothing = false;
// An instrumented program's own events are drained before the
// debugger reports its stop: what follows its line is the debugger's.
var debugger_spoke = false;
var touched: [2]?Touch = .{ null, null };
var branched: ?Branch = null;
snapshots.clearRetainingCapacity();
for (pending) |p| if (p) |read_by| if (read_by.how & 1 != 0) try reads.append(arena, .{ .addr = read_by.addr, .len = read_by.len });
while (events.next()) |item| {
const ev = item.ev;
count += 1;
if (ev.kind == .string) try r.strings.put(arena, ev.a[0], try arena.dupe(u8, item.payload));
if (ev.tid == 0) continue;
if (r.tid == 0) r.tid = ev.tid;
if (ev.tid != r.tid) continue;
switch (ev.kind) {
.call => {
told = true;
try calls.append(arena, .{ .function = ev.a[0], .parent = open_calls.getLastOrNull(), .depth = @intCast(open_calls.items.len), .sp = ev.a[2], .enter = i });
try open_calls.append(gpa, @intCast(calls.items.len - 1));
},
.ret => if (open_calls.pop()) |c| {
calls.items[c].exit = i;
calls.items[c].result = ev.a[1];
},
.syscall_enter => try syscalls.append(arena, .{ .nr = ev.aux, .args = ev.a, .enter = i, .text = if (item.payload.len != @sizeOf(zt.Regs)) try arena.dupe(u8, item.payload) else "" }),
.syscall_exit => if (syscalls.items.len > 0) {
const last = &syscalls.items[syscalls.items.len - 1];
if (last.exit == null) {
last.exit = i;
last.result = ev.a[0];
}
},
.mark => try marks.append(arena, .{ .moment = i, .text = try arena.dupe(u8, item.payload) }),
.alloc => try allocations.append(arena, .{ .ptr = ev.a[0], .size = ev.a[1], .moment = i, .event = count }),
// A store that left the bytes as they were is told too, with no payload: it is still a write.
.mem_write => if (ev.a[1] > 0) {
try writes.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] });
try snapshots.append(gpa, !told or debugger_spoke);
},
.mem_read => if (ev.a[1] > 0) try reads.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] }),
.variable => {
if ((zt.telescope.region(m, ev.a[0]) catch .none) == .stack) try locals.append(arena, .{ .moment = i, .addr = ev.a[0] }) else try globals.append(arena, .{ .addr = ev.a[0], .len = ev.a[1] });
// The first variable of a function that takes something is what it was given.
if (open_calls.getLastOrNull()) |c| {
const takes = for (r.functions) |f| {
if (std.mem.eql(u8, f.name, r.name(calls.items[c].function))) break f.takes;
} else true;
if (takes and calls.items[c].parameter == null and ev.a[1] <= 8) {
calls.items[c].parameter = .{ .addr = ev.a[0], .len = ev.a[1] };
calls.items[c].parameter_name = ev.a[2];
}
}
},
.line => {
line_at = ev.a[3];
line_file = ev.a[0];
// The pass counts its strings from 1; the debugger's ids are hashes with the top bit set.
if (ev.a[0] >> 63 != 0) debugger_spoke = true;
},
.step => stepped = true,
.breakpoint => {
stepped = true;
broke = true;
},
.touch => {
const slot: usize = if (touched[0] == null) 0 else 1;
if (touched[slot] == null) touched[slot] = .{ .addr = ev.a[0], .len = ev.a[1], .how = @intCast(ev.aux & 3) };
},
.branch => branched = .{ .to = ev.a[0], .taken = ev.a[1] != 0, .kind = switch (ev.aux) {
1 => .call,
2 => .jump,
3 => .ret,
else => .none,
} },
else => {},
}
}
const regs = try m.regs(r.tid);
// A debugger records the stack it can see, not what the program
// stores: bytes seen for the first time were not written by this
// step, unless it pushed them (the stack pointer went down a word).
var kept = first_write;
var changed_by_store = false;
for (writes.items[first_write..], snapshots.items) |span, snapshot| {
var fresh = true;
for (0..span.len) |b| {
const gop = try seen.getOrPut(gpa, (span.addr + b) / 64);
if (!gop.found_existing) gop.value_ptr.* = 0;
const bit = @as(u64, 1) << @intCast((span.addr + b) % 64);
if (gop.value_ptr.* & bit != 0) fresh = false;
gop.value_ptr.* |= bit;
}
var keep: ?Span = span;
if (stepped and fresh and snapshot) {
const pushed = regs != null and before != null and regs.?.rsp + 8 == before.?.rsp and span.addr <= regs.?.rsp and span.addr + span.len >= regs.?.rsp + 8;
keep = if (pushed) .{ .addr = regs.?.rsp, .len = 8 } else null;
}
// The store the instruction made says it to the element: below.
if (!told and stepped and stored(pending, span)) {
keep = null;
changed_by_store = true;
}
if (keep) |span_kept| {
writes.items[kept] = span_kept;
kept += 1;
}
}
writes.shrinkRetainingCapacity(kept);
// What the instruction at the stop before said it would store, it
// stored, the bytes it named: a write where the value changed (a
// debugger sees words change, the instruction says which element);
// a store all the same, even of the value that was there.
if (!told and stepped) for (pending) |p| if (p) |w| if (w.how & 2 != 0) {
try stores.append(arena, .{ .addr = w.addr, .len = w.len });
if (changed_by_store) try writes.append(arena, .{ .addr = w.addr, .len = w.len });
};
try write_ends.append(arena, @intCast(writes.items.len));
try store_ends.append(arena, @intCast(stores.items.len));
try read_ends.append(arena, @intCast(reads.items.len));
const line = (try m.line(r.tid)) orelse store.Line{};
try lines.append(arena, line);
const ours = line.line != 0 and std.mem.eql(u8, std.fs.path.basename(r.name(line.file)), r.file);
try own.append(arena, if (ours) line.line else if (own.items.len > 0) own.items[own.items.len - 1] else 0);
try reached.append(arena, ours and line_file != null);
try touch_list.append(arena, touched);
pending = touched;
try branch_list.append(arena, branched);
if (ours and regs != null) try code_lines.put(gpa, regs.?.rip, line.line);
try registers.append(arena, regs orelse before orelse .{});
if (!told and stepped and regs != null and before != null) {
const now = regs.?;
const was = before.?;
// Back where the newest call was made from, its frame gone.
if (derived.getLastOrNull()) |back| {
const top = &calls.items[open_calls.getLast()];
if (now.rip == back and now.rsp == top.sp + 8) {
_ = derived.pop();
_ = open_calls.pop();
top.exit = i;
top.result = now.rax;
}
}
// A call pushes the address after itself and lands on a line of ours.
if (now.rsp + 8 == was.rsp and line_at == now.rip and ours) {
if (try word(m, now.rsp, 8)) |back| if (back > was.rip and back - was.rip <= 15) {
const function = r.functionAt(line.line);
takes_nothing = function != null and !function.?.takes;
try calls.append(arena, .{ .function = try r.intern(if (function) |fun| fun.name else "?"), .parent = open_calls.getLastOrNull(), .depth = @intCast(open_calls.items.len), .sp = now.rsp, .enter = i });
try open_calls.append(gpa, @intCast(calls.items.len - 1));
try derived.append(gpa, back);
};
}
}
// A recording that begins inside a call (`record --from`): the call
// it first stops in was made before it, and is open.
if (!told and broke and ours and calls.items.len == 0) if (regs) |now| {
var found: [2]zt.Debugger.Frame = undefined;
const frames = zt.telescope.frames(m, &now, &found) catch found[0..0];
if (frames.len == 2 and frames[0].high > frames[0].low) {
const function = r.functionAt(line.line);
takes_nothing = function != null and !function.?.takes;
try calls.append(arena, .{ .function = try r.intern(if (function) |fun| fun.name else "?"), .parent = null, .depth = 0, .sp = frames[0].high - 8, .enter = i });
try open_calls.append(gpa, 0);
try derived.append(gpa, frames[1].pc);
}
};
if (regs) |g| before = g;
try depths.append(arena, @intCast(open_calls.items.len));
// What each open call was given, once the recording has it: the
// value of its first variable, or for one read off the registers, rdi.
for (calls.items[first_call..]) |*c| {
if (!told and regs != null and !takes_nothing) c.arg = regs.?.rdi;
}
// (Once it is stored: until then that stretch of stack holds what was there before.)
for (open_calls.items) |c| {
const call_made = &calls.items[c];
if (call_made.arg != null) continue;
if (call_made.parameter) |p| if (touches(writes.items[first_write..], p.addr, p.len)) {
call_made.arg = try word(m, p.addr, @intCast(p.len));
};
}
}
// An instrumented program under the debugger says "call" a few stops
// after the debugger has stopped on the callee's first line: the call
// began at that stop.
if (told) for (calls.items) |*c| {
var at = c.enter;
var back: usize = 0;
while (at > 0 and back < 64 and !reached.items[at]) : (back += 1) at -= 1;
if (!reached.items[at] or at == c.enter) continue;
for (depths.items[at..c.enter]) |*depth| depth.* += 1;
c.enter = at;
};
r.lines = lines.items;
r.own = own.items;
r.reached = reached.items;
r.depths = depths.items;
r.calls = calls.items;
r.syscalls = syscalls.items;
r.marks = marks.items;
r.allocations = allocations.items;
r.registers = registers.items;
r.write_spans = .{ .all = writes.items, .ends = write_ends.items };
r.store_spans = .{ .all = stores.items, .ends = store_ends.items };
r.insn_touches = touch_list.items;
r.insn_branches = branch_list.items;
r.code_lines = try arena.alloc(CodeLine, code_lines.count());
var it = code_lines.iterator();
var n: usize = 0;
while (it.next()) |e| : (n += 1) r.code_lines[n] = .{ .addr = e.key_ptr.*, .line = e.value_ptr.* };
std.mem.sort(CodeLine, r.code_lines, {}, struct {
fn less(_: void, a: CodeLine, b: CodeLine) bool {
return a.addr < b.addr;
}
}.less);
r.read_spans = .{ .all = reads.items, .ends = read_ends.items };
r.locals = locals.items;
r.globals = globals.items;
}
/// A string id for `text`, for names the recording did not define itself.
fn intern(r: *Recording, text: []const u8) !u64 {
const id = std.hash.Wyhash.hash(0, text) | 1 << 63;
if (!r.strings.contains(id)) try r.strings.put(r.arena.allocator(), id, try r.arena.allocator().dupe(u8, text));
return id;
}
pub const Function = struct {
name: []const u8,
/// Whether it has parameters: `main(void)` has none; and how many.
takes: bool,
params: usize = 0,
/// Its first parameter's name ("" when it takes none).
param: []const u8 = "",
/// Its declaration's first line (from 1) and last.
first: u32,
last: u32,
};
/// The functions of `source`, as pardes outlines them: a name is the word
/// before the first parenthesis of a declaration's header.
pub fn outline(arena: std.mem.Allocator, source: []const u8, file: []const u8) ![]Function {
var analysis = pardes.analyzeSource(gpa, file, source, true, false) catch return &.{};
defer analysis.deinit(gpa);
var found: std.ArrayList(Function) = .empty;
for (analysis.declarations) |d| {
const header = source[d.start_byte..d.header_end_byte];
const paren = std.mem.indexOfScalar(u8, header, '(') orelse continue;
var from = paren;
while (from > 0 and (std.ascii.isAlphanumeric(header[from - 1]) or header[from - 1] == '_')) from -= 1;
if (from == paren) continue;
const close = std.mem.indexOfScalarPos(u8, header, paren, ')') orelse header.len;
const params = std.mem.trim(u8, header[paren + 1 .. close], " ");
const first_param = std.mem.trim(u8, params[0 .. std.mem.indexOfScalar(u8, params, ',') orelse params.len], " ");
var name_from = first_param.len;
while (name_from > 0 and (std.ascii.isAlphanumeric(first_param[name_from - 1]) or first_param[name_from - 1] == '_')) name_from -= 1;
try found.append(arena, .{ .name = header[from..paren], .takes = params.len > 0 and !std.mem.eql(u8, params, "void"), .params = if (params.len > 0 and !std.mem.eql(u8, params, "void")) std.mem.count(u8, params, ",") + 1 else 0, .param = first_param[name_from..], .first = @intCast(d.start_line + 1), .last = @intCast(d.end_line + 1) });
}
return found.items;
}
/// The function whose declaration holds `line` (from 1): the innermost.
pub fn functionAt(r: *const Recording, line: u32) ?Function {
var found: ?Function = null;
for (r.functions) |f| if (line >= f.first and line <= f.last) {
found = f;
};
return found;
}
/// `size` bytes at `addr` as a little-endian number; null where a byte of
/// it was never recorded.
pub fn word(m: Moment, addr: u64, size: usize) !?u64 {
var bytes: [8]u8 = @splat(0);
var known: [8]bool = undefined;
try m.read(addr, bytes[0..size], known[0..size]);
for (known[0..size]) |k| if (!k) return null;
return std.mem.readInt(u64, &bytes, .little);
}
pub fn len(r: *const Recording) u64 {
return r.trace.len;
}
/// The last moment.
pub fn end(r: *const Recording) u64 {
return r.trace.len - 1;
}
/// The program's state at moment `i` (the last one, past the end).
pub fn moment(r: *const Recording, i: u64) Moment {
return r.trace.moment(@min(i, r.end())) catch unreachable;
}
/// Register `reg` of the thread shown at moment `i`; 0 when the recording
/// has no registers there.
pub fn register(r: *const Recording, i: u64, reg: []const u8) u64 {
return r.registers[@min(i, r.end())].named(reg) orelse 0;
}
/// A string id's text; "?" for one the recording never defined.
pub fn name(r: *const Recording, id: u64) []const u8 {
return r.strings.get(id) orelse "?";
}
/// The live variable called `text`: the innermost of that name.
pub fn variable(r: *const Recording, scratch: std.mem.Allocator, m: Moment, text: []const u8) ?Variable {
const all = m.variables(scratch) catch return null;
var found: ?Variable = null;
for (all) |v| {
if (std.mem.eql(u8, r.name(v.name), text) and (found == null or v.depth > found.?.depth)) found = v;
}
return found;
}
/// A variable's type, as the compiler pass described it, with a named type
/// (`struct node`, a typedef) followed to what it is. Null when the
/// recording has no description (it was not made by `ztrace cc`).
pub fn typeOf(r: *const Recording, scratch: std.mem.Allocator, id: u64) ?types.Type {
return r.resolve(scratch, types.parse(scratch, r.strings.get(id) orelse return null) catch return null);
}
/// `t`, or what its name stands for.
pub fn resolve(r: *const Recording, scratch: std.mem.Allocator, t: types.Type) ?types.Type {
var at = t;
// A typedef of a typedef of a struct, and no further.
for (0..8) |_| {
if (at != .named) return at;
at = types.parse(scratch, r.strings.get(types.defId(at.named)) orelse return null) catch return null;
}
return null;
}
/// Whether variable `v` has been stored to since the call it lives in
/// began: until then its bytes are whatever that stretch of stack held
/// before, and a picture should not show them as its value.
pub fn assigned(r: *const Recording, v: Variable, i: u64) bool {
if (v.depth == 0) {
// A recording that tells no calls: a local is its value once
// written after it was declared; a global always is.
var k = r.locals.len;
while (k > 0) {
k -= 1;
const d = r.locals[k];
if (d.moment <= i and d.addr == v.addr) return touches(r.written(d.moment, i), v.addr, v.size) or touches(r.store_spans.of(d.moment, i), v.addr, v.size);
}
return true;
}
var enter: u64 = 0;
for (r.calls) |c| {
if (c.enter > i) break;
if (c.active(i) and c.depth + 1 == v.depth) enter = c.enter;
}
return touches(r.written(enter -| 1, i), v.addr, v.size);
}
/// Which allocation ever made holds `addr` at moment `m`: the same number
/// for the same object in every view, null outside the heap.
pub fn identity(r: *const Recording, m: Moment, addr: u64) ?usize {
const a = (m.allocation(addr) catch return null) orelse return null;
for (r.allocations, 0..) |b, i| if (b.event == a.born) return i;
return null;
}
/// What file descriptor `fd` is open on at moment `i`, as the `value`
/// class `fd` says it: the path the call that returned it was given,
/// quoted; the three a program starts with by name; "" when not known.
pub fn openOn(r: *const Recording, scratch: std.mem.Allocator, fd: u64, i: u64) []const u8 {
var on: []const u8 = switch (fd) {
0 => "stdin",
1 => "stdout",
2 => "stderr",
else => "",
};
const SYS = std.os.linux.SYS;
for (r.syscalls) |s| {
if (s.enter >= i) break;
switch (std.enums.fromInt(SYS, s.nr) orelse continue) {
.open, .openat, .creat => if (s.exit != null and s.exit.? <= i and s.result == fd) {
on = if (s.text.len > 0) std.fmt.allocPrint(scratch, "\"{s}\"", .{std.fs.path.basename(s.text)}) catch "" else "";
},
.close => if (s.args[0] == fd) {
on = "";
},
else => {},
}
}
return on;
}
/// The calls open at moment `i`, outermost first, in `scratch`.
/// shortcut: looks at every call made by then; a recording of a million calls wants each call's stack kept as a chain of parents.
pub fn stack(r: *const Recording, scratch: std.mem.Allocator, i: u64) []const Call {
var out: std.ArrayList(Call) = .empty;
for (r.calls) |c| {
if (c.enter > i) break;
if (c.active(i)) out.append(scratch, c) catch break;
}
return out.items;
}
// ---------------------------------------------------------------------------
// Finding moments. Each returns the last moment when there is none: a
// cursor sent there plays to the end.
/// The first moment after `from` that is a stop of kind `by`.
pub fn next(r: *const Recording, by: Stop, from: u64) u64 {
if (from >= r.end()) return r.end();
switch (by) {
.moment => return from + 1,
.line, .over => {
const depth = r.depths[from];
for (from + 1..r.len()) |i| {
// A line of the program's own, newly reached: another line,
// or the same one in another call (fib's, a level down).
if (!r.reached[i] or (r.own[i] == r.own[from] and r.depths[i] == depth)) continue;
if (by == .line or r.depths[i] <= depth) return i;
}
},
.call => {
var best = r.end();
for (r.calls) |c| {
if (c.enter > from) best = @min(best, c.enter);
if (c.exit) |e| if (e > from) {
best = @min(best, e);
};
}
return best;
},
.syscall => for (r.syscalls) |s| if (s.enter > from) return s.enter,
}
return r.end();
}
/// The first moment at or after `from` on line `line` of the program's source.
pub fn lineMoment(r: *const Recording, line: u32, from: u64) u64 {
for (r.own[@min(from, r.len())..], from..) |l, i| if (l == line) return i;
return r.end();
}
/// The first moment after `from` that changes a byte in `addr .. addr + size`.
pub fn nextWrite(r: *const Recording, addr: u64, size: u64, from: u64) u64 {
var i = from + 1;
while (i < r.len()) : (i += 1) if (touches(r.written(i - 1, i), addr, size)) return i;
return r.end();
}
/// The moment of the mark `text`. A scene asking for a mark the program
/// never made is a mistake in the scene.
pub fn mark(r: *const Recording, text: []const u8) u64 {
for (r.marks) |m| if (std.mem.eql(u8, m.text, text)) return m.moment;
std.debug.panic("canim: the recording has no mark \"{s}\"", .{text});
}
/// The `nth` call (from 0) of the function called `function`.
pub fn call(r: *const Recording, function: []const u8, nth: usize) Call {
var seen: usize = 0;
for (r.calls) |c| if (std.mem.eql(u8, r.name(c.function), function)) {
if (seen == nth) return c;
seen += 1;
};
std.debug.panic("canim: the recording has no call {d} of \"{s}\"", .{ nth, function });
}
// ---------------------------------------------------------------------------
// What changed.
/// The bytes the moments after `from`, up to `to`, changed.
pub fn written(r: *const Recording, from: u64, to: u64) []const Span {
return r.write_spans.of(from, to);
}
/// The bytes they stored with the value already there (a local
/// assigned what its slot held before): no change, but an assignment.
pub fn storedSame(r: *const Recording, from: u64, to: u64) []const Span {
return r.store_spans.of(from, to);
}
/// The bytes they read.
pub fn read(r: *const Recording, from: u64, to: u64) []const Span {
return r.read_spans.of(from, to);
}
/// A bit for each register of `Regs.names` that is not what it was:
/// a register a step changed and put back (a call's rsp) is not changed.
pub fn registersChanged(r: *const Recording, from: u64, to: u64) u32 {
if (to >= r.registers.len or from >= to) return 0;
return changedRegisters(r.registers[from], r.registers[to]);
}
/// Whether bytes `span` are drawn somewhere for the step from `from` to
/// `to`: in the stack's frame round either stop's rsp and rbp, in an
/// allocation, or in a global (an array's cells). Elsewhere (the library's
/// own memory) a step's memory level has nothing to show.
pub fn drawn(r: *const Recording, span: Span, from: u64, to: u64) bool {
for ([_]u64{ from, to }) |i| {
const regs = r.registers[@min(i, r.end())];
const low = regs.rsp -| 8;
const high = @max(regs.rbp, regs.rsp) + 16 + 8 * 8;
if (span.addr < high and span.addr + span.len > low) return true;
}
for (r.allocations) |a| if (span.addr < a.ptr + a.size and span.addr + span.len > a.ptr -| 16) return true;
return touches(r.globals, span.addr, span.len);
}
pub fn touches(list: []const Span, addr: u64, size: u64) bool {
for (list) |s| if (s.addr < addr + size and s.addr + s.len > addr) return true;
return false;
}
/// Whether one of `by` (an instruction's touches) stores into `span`.
fn stored(by: [2]?Touch, span: Span) bool {
for (by) |p| if (p) |w| if (w.how & 2 != 0 and w.addr < span.addr + span.len and w.addr + w.len > span.addr) return true;
return false;
}
/// A bit for each register of `Regs.names` that differs between `a` and `b`.
pub fn changedRegisters(a: zt.Regs, b: zt.Regs) u32 {
var mask: u32 = 0;
inline for (zt.Regs.names, 0..) |reg, i| {
if (@field(a, reg) != @field(b, reg)) mask |= 1 << i;
}
return mask;
}
test "registers that differ are told by their place in Regs.names" {
const a: zt.Regs = .{ .rax = 1, .rip = 0x1000, .rsp = 8 };
var b = a;
b.rax = 2;
b.rip = 0x1004;
try std.testing.expectEqualStrings("rax", zt.Regs.names[0]);
const mask = changedRegisters(a, b);
try std.testing.expect(mask & 1 != 0);
try std.testing.expectEqual(@as(u32, 2), @popCount(mask));
try std.testing.expectEqual(@as(u32, 0), changedRegisters(a, a));
}
test "spans touch the ranges they overlap" {
const list = [_]Span{ .{ .addr = 0x100, .len = 4 }, .{ .addr = 0x200, .len = 1 } };
try std.testing.expect(touches(&list, 0x100, 8));
try std.testing.expect(touches(&list, 0x0fc, 5));
try std.testing.expect(!touches(&list, 0x0fc, 4));
try std.testing.expect(!touches(&list, 0x104, 8));
try std.testing.expect(touches(&list, 0x1f9, 8));
}
test "a function is named by the declaration that holds the line" {
const source =
\\#include <stdio.h>
\\
\\long fib(long n) {
\\ if (n < 2)
\\ return n;
\\ return fib(n - 1) + fib(n - 2);
\\}
\\
\\int main(void) {
\\ printf("%ld\\n", fib(5));
\\ return 0;
\\}
;
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const r: Recording = .{ .trace = undefined, .key = undefined, .file = "fib.c", .source = source, .arena = undefined, .functions = try outline(arena.allocator(), source, "fib.c") };
try std.testing.expectEqualStrings("fib", r.functionAt(3).?.name);
try std.testing.expect(r.functionAt(6).?.takes);
try std.testing.expectEqualStrings("main", r.functionAt(10).?.name);
try std.testing.expect(!r.functionAt(10).?.takes);
try std.testing.expect(r.functionAt(8) == null);
try std.testing.expectEqual(@as(u32, 7), r.functionAt(5).?.last);
}
|