summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cli/disasm.c3
-rw-r--r--src/cli/record.zig13
-rw-r--r--src/trace/Debugger.zig171
-rw-r--r--src/trace/debugger_test.zig281
-rw-r--r--src/trace/event.zig7
-rw-r--r--src/trace/telescope.zig114
6 files changed, 580 insertions, 9 deletions
diff --git a/src/cli/disasm.c b/src/cli/disasm.c
index 9b15e0c..6f2ffa4 100644
--- a/src/cli/disasm.c
+++ b/src/cli/disasm.c
@@ -21,6 +21,8 @@ struct zt_branch {
// A conditional jump whose condition does not hold is not taken.
uint8_t taken;
uint8_t indirect;
+ // A jump on a condition.
+ uint8_t conditional;
};
// Whether the flags (and rcx) make a conditional jump go.
@@ -96,6 +98,7 @@ size_t zt_disasm(const uint8_t *code, size_t len, uint64_t addr, char *text, siz
branch->taken = regs ? holds(insn->id, regs[18], regs[11]) : 1;
branch->indirect = 0;
branch->target = 0;
+ branch->conditional = branch->kind == 2 && insn->id != X86_INS_JMP && insn->id != X86_INS_LJMP;
if (branch->kind == 1 || branch->kind == 2) {
const cs_x86_op *op = &x->operands[0];
if (x->op_count < 1) branch->kind = 0;
diff --git a/src/cli/record.zig b/src/cli/record.zig
index 6743ec4..5d3726c 100644
--- a/src/cli/record.zig
+++ b/src/cli/record.zig
@@ -10,7 +10,7 @@ pub const usage =
\\usage: ztrace record [-o FILE] [--by insn|line|syscall|break] [-b WHERE]... [-w WHAT[,LEN]]...
\\ [--from WHERE] [--stack BYTES] [-s BYTES] [--telescope DEPTH]
\\ [--around BYTES] [--disasm ROWS] [--steps N]
- \\ [--max-size BYTES] [--strace] [--heap]
+ \\ [--max-size BYTES] [--strace] [--heap] [--asan]
\\ [--ring] [--preload LIB] [--alloc] -- PROGRAM [ARGS]
\\
\\Runs PROGRAM under ptrace into a recording (default out.ztrace). --by
@@ -44,6 +44,10 @@ pub const usage =
\\tcache, and the links of every chunk on a list; at most 4096 chunks and
\\256 entries a list. glibc 2.40 and 2.44 only, linked dynamically or
\\statically; the main arena's heap, the stopped thread's tcache.
+ \\--asan also records AddressSanitizer's shadow of all memory recorded (a
+ \\byte for 8: 00 addressable, f1 f2 f3 a stack frame's redzones, fa a
+ \\heap's, fd freed), where the runtime puts it; for a program built with
+ \\-fsanitize=address only.
\\--steps ends the recording after N moments (N stops from the --from
\\place, when there is one), and --max-size when the
\\file is that large (default 1G). Sizes take a suffix: 64K, 4G.
@@ -74,6 +78,7 @@ pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
var max_bytes: ?u64 = null;
var strace = false;
var heap = false;
+ var asan = false;
var from: ?[]const u8 = null;
var breaks: std.ArrayList([]const u8) = .empty;
var watches: std.ArrayList([]const u8) = .empty;
@@ -94,6 +99,8 @@ pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
strace = true;
} else if (std.mem.eql(u8, arg, "--heap")) {
heap = true;
+ } else if (std.mem.eql(u8, arg, "--asan")) {
+ asan = true;
} else if (producer.take(args, &i)) {
// Its own argument, when it has one, is taken.
} else if (value == null) {
@@ -157,6 +164,9 @@ pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
d.syscalls = if (by == .syscall) .stop else .record;
d.stack_watch = stack_bytes;
if (heap) d.heap = .{};
+ // Built with ASan, the program has its runtime or calls it (`__asan_init`, from a constructor).
+ if (asan and d.symbol("__asan_init") == null and !d.syms.imported.contains("__asan_init")) fail("--asan: {s} has no ASan runtime: build it with -fsanitize=address\n", .{args[i]});
+ d.asan = asan;
if (capture) |n| d.capture = n;
for (breaks.items) |where| {
if (std.mem.startsWith(u8, where, "usdt:")) {
@@ -234,6 +244,7 @@ pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
.no_layout => std.debug.print("heap: not recorded: no layout known for glibc {d}.{d} (known: 2.40, 2.44)\n", .{ h.version[0], h.version[1] }),
.no_arena => std.debug.print("heap: not recorded: more than one place in glibc looks like the main arena\n", .{}),
};
+ if (asan) if (d.asan_shadow) |offset| std.debug.print("asan: shadow at {x}\n", .{offset}) else std.debug.print("asan: not recorded: the runtime never set its shadow\n", .{});
std.debug.print("{s}: {d} moments, {d} events, {d} bytes ({d} bytes/moment), {d:.1} ms, {d:.0} moments/s, exit {d}\n", .{
out, moments,
events, size,
diff --git a/src/trace/Debugger.zig b/src/trace/Debugger.zig
index 971b50b..d312dec 100644
--- a/src/trace/Debugger.zig
+++ b/src/trace/Debugger.zig
@@ -66,6 +66,11 @@ allocations: std.ArrayList(Watch) = .empty,
/// The most read of them at a stop, in bytes: a stop's cost must not grow
/// with the target's heap.
allocation_watch: usize = 256 << 10,
+/// ASan's shadow memory, recorded beside every region recorded (`--asan`):
+/// its byte for each 8 bytes, at `(addr >> 3) + asan_shadow`. The offset
+/// is the runtime's, found at the first stop after it set it.
+asan: bool = false,
+asan_shadow: ?u64 = null,
/// glibc's heap, recorded at every stop as `heap.zig` reads it (`--heap`): null for not at all.
heap: ?@import("heap.zig").Watch = null,
breakpoints: std.ArrayList(Breakpoint) = .empty,
@@ -87,6 +92,9 @@ written: [2]Touch = undefined,
written_count: usize = 0,
/// The instructions above and below the pc whose text a stop records.
disasm_around: usize = 8,
+/// The most instructions of a function recorded whole with its blocks
+/// (`emitBlocks`): a larger one's blocks are recorded without their text.
+function_text: usize = 2048,
/// Each function met, as where its instructions begin (`instructions`).
functions: std.AutoHashMapUnmanaged(u64, []const u32) = .empty,
/// How far a stop follows pointers, from each register and from each of
@@ -146,8 +154,9 @@ pub const Breakpoint = struct { id: u32, addr: u64, saved: u8, hook: ?Hook };
pub const Insn = struct { len: u8, text: []const u8, touches: []const Touch = &.{}, branch: Branch = .{} };
/// Where a call, a jump or a return goes. `kind`: 0 not one, 1 call, 2
/// jump, 3 return. With `indirect` the target is read from the
-/// instruction's memory operand; a return's is on the stack.
-pub const Branch = extern struct { target: u64 = 0, kind: u8 = 0, taken: u8 = 1, indirect: u8 = 0 };
+/// instruction's memory operand; a return's is on the stack. `conditional`:
+/// a jump on a condition.
+pub const Branch = extern struct { target: u64 = 0, kind: u8 = 0, taken: u8 = 1, indirect: u8 = 0, conditional: u8 = 0 };
/// Memory an instruction touches: `how` is 1 for a read, 2 a write, 3 both.
pub const Touch = extern struct { addr: u64, size: u8, how: u8 };
pub const Watch = struct { addr: u64, len: usize };
@@ -506,6 +515,7 @@ fn report(d: *Debugger, stop: Stop) !Stop {
if (d.sink == null) return stop;
if (!d.done) {
try d.emitLine();
+ if (d.asan and d.asan_shadow == null) try d.findShadow();
// With the 128 bytes under the stack pointer: the red zone, a leaf's locals.
if (d.stack_watch > 0) try d.snapshot(d.regs.rsp -| 128, d.stack_watch + 128);
for (d.watches.items) |w| try d.snapshot(w.addr, w.len);
@@ -564,11 +574,13 @@ fn emitCode(d: *Debugger) !void {
}
}
// The instructions round the pc, in address order. Inside a function
- // they are known both ways, the function decoded once from its start;
- // elsewhere (no symbol: stripped code, a JIT's) only from the pc on.
+ // they are known both ways, the function decoded once from its start,
+ // and its blocks are recorded; elsewhere (no bounds: a JIT's code) only
+ // from the pc on.
const around = d.disasm_around;
- if (d.syms.symbolAt(d.regs.rip)) |sym| if (sym.size > 0 and sym.size <= 1 << 16) {
+ if (d.bounds(d.regs.rip)) |sym| if (sym.size > 0 and sym.size <= 1 << 20) {
const starts = try d.instructions(sym, insnAt);
+ try d.emitBlocks(insnAt, sym, starts);
const here: u32 = @intCast(d.regs.rip - sym.addr);
const at = std.sort.binarySearch(u32, starts, here, struct {
fn order(want: u32, have: u32) std.math.Order {
@@ -642,6 +654,124 @@ fn instructions(d: *Debugger, sym: Symbols.Symbol, insnAt: @typeInfo(@TypeOf(d.d
return entry.value_ptr.*;
}
+/// Where the function that holds `addr` begins and how long it is: by its
+/// symbol, else by its call frame information (a stripped library's).
+fn bounds(d: *Debugger, addr: u64) ?Symbols.Symbol {
+ if (d.syms.symbolAt(addr)) |sym| if (sym.size > 0) return sym;
+ const f = d.syms.functionAt(addr) orelse return null;
+ return .{ .name = "", .addr = f.start, .size = f.len };
+}
+
+/// How a basic block ends.
+pub const End = enum(u8) {
+ /// Into the block after it, which something jumps to.
+ fall,
+ /// An unconditional jump in the function, to `to`.
+ jump,
+ /// A conditional jump: to `to` when taken, else into the block after it.
+ branch,
+ ret,
+ /// A jump through a register or memory, to where is not known.
+ indirect,
+ /// A jump out of the function, to `to`: a tail call.
+ tail,
+ /// A call that does not return, to `to` (`no_target`: through a
+ /// register or memory): the function's last instruction, or a call of
+ /// one that never returns (`noreturn_names`).
+ noreturn,
+};
+
+/// A basic block as `emitBlocks` records it: `offset` bytes into its
+/// function, `len` long, how it ends, and where to (`to`, from the
+/// function's start).
+pub const Block = extern struct { offset: u32, len: u32, to: i32 = 0, end: End, pad: [3]u8 = @splat(0) };
+pub const no_target = std.math.minInt(i32);
+
+/// Functions that never return: a call of one ends its block.
+const noreturn_names = [_][]const u8{ "abort", "exit", "_exit", "_Exit", "__stack_chk_fail", "__assert_fail", "__fortify_fail", "__chk_fail", "longjmp", "siglongjmp", "__longjmp_chk", "pthread_exit", "__cxa_throw", "__cxa_rethrow", "_Unwind_Resume" };
+
+/// A function's basic blocks, recorded once as a string (`event.blocksId`
+/// of where it begins): its length (4 bytes), a byte that is 1 when every
+/// instruction of it is recorded too (`function_text` of them at most:
+/// strings by `event.codeId`, as `emitInstruction` writes them; and the
+/// names of where its calls and jumps out of it go), then its
+/// blocks (`Block`). Decoded from its instructions: a block begins at the
+/// function's start, at each jump's target in it, and after each jump,
+/// return and call that does not return; a call that returns ends none.
+fn emitBlocks(d: *Debugger, insnAt: @typeInfo(@TypeOf(d.disasm)).optional.child, sym: Symbols.Symbol, starts: []const u32) !void {
+ if ((try d.described.getOrPut(d.gpa, event.blocksId(sym.addr))).found_existing) return;
+ const code = try d.gpa.alloc(u8, sym.size);
+ defer d.gpa.free(code);
+ const n = d.read(sym.addr, code);
+ const branches = try d.gpa.alloc(Branch, starts.len);
+ defer d.gpa.free(branches);
+ // By instruction: the ones a block begins at, and the calls that do not return.
+ var leaders = try std.DynamicBitSetUnmanaged.initEmpty(d.gpa, starts.len + 1);
+ defer leaders.deinit(d.gpa);
+ var stops = try std.DynamicBitSetUnmanaged.initEmpty(d.gpa, starts.len);
+ defer stops.deinit(d.gpa);
+ leaders.set(0);
+ var text: [192]u8 = undefined;
+ for (starts, branches, 0..) |off, *b, k| {
+ b.* = if (off < n) if (insnAt(code[off..n], sym.addr + off, &text, null, &.{})) |insn| insn.branch else .{} else .{};
+ if (b.kind == 1 and noReturn(d, b.*, k + 1 == starts.len)) stops.set(k);
+ if (b.kind == 2 or b.kind == 3 or stops.isSet(k)) leaders.set(k + 1);
+ if (b.kind == 2 and b.indirect == 0 and b.target -% sym.addr < sym.size) {
+ if (std.sort.binarySearch(u32, starts, @as(u32, @intCast(b.target - sym.addr)), struct {
+ fn order(want: u32, have: u32) std.math.Order {
+ return std.math.order(want, have);
+ }
+ }.order)) |target| leaders.set(target);
+ }
+ }
+ var out: std.Io.Writer.Allocating = .init(d.gpa);
+ defer out.deinit();
+ const w = &out.writer;
+ try w.writeInt(u32, @intCast(sym.size), .little);
+ try w.writeByte(@intFromBool(starts.len <= d.function_text));
+ var first: usize = 0;
+ for (branches, 0..) |b, k| {
+ if (!leaders.isSet(k + 1) and k + 1 < starts.len) continue;
+ const end: u32 = if (k + 1 < starts.len) starts[k + 1] else @intCast(sym.size);
+ var block: Block = .{ .offset = starts[first], .len = end - starts[first], .end = .fall };
+ const to = std.math.cast(i32, @as(i64, @bitCast(b.target -% sym.addr)));
+ switch (b.kind) {
+ 2 => if (b.indirect != 0 or b.target == 0 or to == null) {
+ block.end = .indirect;
+ } else {
+ block.to = to.?;
+ block.end = if (b.conditional != 0) .branch else if (b.target -% sym.addr < sym.size) .jump else .tail;
+ },
+ 3 => block.end = .ret,
+ 1 => if (stops.isSet(k)) {
+ block.end = .noreturn;
+ block.to = if (b.indirect != 0 or b.target == 0) no_target else to orelse no_target;
+ },
+ else => {},
+ }
+ try w.writeAll(std.mem.asBytes(&block));
+ first = k + 1;
+ }
+ // The text of each instruction, when there are few enough, and the
+ // name of each place its calls and its jumps out of it go.
+ if (starts.len <= d.function_text) for (starts, branches, 0..) |off, b, k| {
+ _ = try d.emitInstruction(insnAt, sym.addr + off, if (k > 0) @intCast(starts[k] - starts[k - 1]) else 0);
+ if ((b.kind == 1 or b.kind == 2) and b.indirect == 0 and b.target != 0 and b.target -% sym.addr >= sym.size) try d.nameAddress(b.target);
+ };
+ try d.emit(.{ .kind = .string, .a = .{ event.blocksId(sym.addr), 0, 0, 0, 0, 0 } }, out.written());
+}
+
+/// Whether a call never returns: it is its function's last instruction,
+/// or its callee is one of `noreturn_names` (through its PLT stub too).
+fn noReturn(d: *Debugger, b: Branch, last: bool) bool {
+ if (last) return true;
+ if (b.indirect != 0 or b.target == 0) return false;
+ const callee = (d.syms.symbolAt(b.target) orelse return false).name;
+ const name = if (std.mem.endsWith(u8, callee, "@plt")) callee[0 .. callee.len - "@plt".len] else callee;
+ for (noreturn_names) |known| if (std.mem.eql(u8, known, name)) return true;
+ return false;
+}
+
/// What a viewer follows from the registers and the top of the stack, as
/// pwndbg's telescope does: recorded here, while the memory is there to read.
fn emitTelescope(d: *Debugger) !void {
@@ -670,8 +800,7 @@ fn emitTelescope(d: *Debugger) !void {
fn emitCall(d: *Debugger, ret: u64) !void {
const insnAt = d.disasm orelse return;
if ((try d.described.getOrPut(d.gpa, event.codeId(ret))).found_existing) return;
- // Where its function begins: its symbol's, else its call frame information's (a stripped library's).
- const sym = d.syms.symbolAt(ret) orelse if (d.syms.functionAt(ret -% 1)) |f| Symbols.Symbol{ .name = "", .addr = f.start, .size = f.len } else return;
+ const sym = d.bounds(ret -% 1) orelse return;
if (sym.size == 0 or sym.size > 1 << 16 or ret == sym.addr) return;
const starts = try d.instructions(sym, insnAt);
const k = std.sort.binarySearch(u32, starts, @as(u32, @intCast(ret - sym.addr)), struct {
@@ -838,9 +967,35 @@ pub fn snapshot(d: *Debugger, addr: u64, len: usize) !void {
_ = try d.snap(addr, len);
}
+/// Where ASan's shadow is (`--asan`), recorded once as the string
+/// `asan_id`: a byte of shadow for 2^`scale` bytes of memory, at
+/// `(addr >> scale) + offset`.
+pub const Asan = extern struct { offset: u64, scale: u64 };
+pub const asan_id = event.stringId("asan shadow");
+
+/// ASan's shadow offset, as its runtime has it: the value it exports in
+/// `__asan_shadow_memory_dynamic_address`, set at its start (0x7fff8000 on
+/// x86-64 Linux), and a mapping there (its low shadow). Its scale is 3 on
+/// x86-64 (the runtime keeps it in no variable).
+fn findShadow(d: *Debugger) !void {
+ const sym = d.syms.find("__asan_shadow_memory_dynamic_address") orelse return;
+ var word: [8]u8 = undefined;
+ if (d.read(sym.addr, &word) != 8) return;
+ const offset = std.mem.readInt(u64, &word, .little);
+ if (offset == 0 or d.syms.mappingAt(offset) == null) return;
+ d.asan_shadow = offset;
+ try d.emit(.{ .kind = .string, .a = .{ asan_id, 0, 0, 0, 0, 0 } }, std.mem.asBytes(&Asan{ .offset = offset, .scale = 3 }));
+}
+
/// `snapshot`, returning what was read: from `addr` rounded down to a word,
-/// valid until the next read.
+/// valid until the next read. With ASan's shadow, its bytes for the region
+/// are sent first.
fn snap(d: *Debugger, addr: u64, len: usize) ![]const u8 {
+ if (d.asan_shadow) |offset| _ = try d.snapOnly((addr >> 3) + offset, ((addr + len + 7) >> 3) - (addr >> 3));
+ return d.snapOnly(addr, len);
+}
+
+fn snapOnly(d: *Debugger, addr: u64, len: usize) ![]const u8 {
const start = addr & ~@as(u64, 7);
try d.scratch.resize(d.gpa, std.mem.alignForward(usize, len + (addr - start), 8));
const bytes = d.scratch.items[0 .. d.read(start, d.scratch.items) & ~@as(usize, 7)];
diff --git a/src/trace/debugger_test.zig b/src/trace/debugger_test.zig
index 15ecc71..bd35560 100644
--- a/src/trace/debugger_test.zig
+++ b/src/trace/debugger_test.zig
@@ -323,6 +323,287 @@ test "a call followed down by instruction: through the PLT, the loader's resolve
try std.testing.expect(resolver > 300);
}
+/// Every jump and return a recording by instruction made, tied to its
+/// block's edge: the `branch` event at a stop is the instruction at its
+/// pc, the last of its block; the next stop is at the edge it took.
+/// Returns how many were tied, and how many were in code with no bounds,
+/// recorded as no blocks.
+fn tieBranches(trace: *const zt.Trace) ![2]usize {
+ var tied: usize = 0;
+ var loose: usize = 0;
+ var out: [512]zt.telescope.Block = undefined;
+ var text: [256]u8 = undefined;
+ for (0..trace.len - 1) |i| {
+ const m = try trace.moment(i);
+ var events = try m.events(gpa);
+ defer events.deinit(gpa);
+ const branch = while (events.next()) |item| {
+ if (item.ev.kind == .branch and (item.ev.aux == 2 or item.ev.aux == 3)) break item.ev;
+ } else continue;
+ const pc = branch.a[2];
+ const g = zt.telescope.blocks(m, pc, &out) orelse {
+ // Code with no bounds: no symbol with a size, no unwind information (the C runtime's start).
+ try std.testing.expect(zt.telescope.function(m, pc) == null);
+ loose += 1;
+ continue;
+ };
+ const block = g.blocks[g.here.?];
+ try std.testing.expectEqual(block.start + block.len, pc + (try zt.telescope.instruction(m, pc, &text)).?.len);
+ // The next stop of the same thread: the next moment by instruction, or the one after a syscall's.
+ const next = next: for (i + 1..trace.len) |j| {
+ const later = try trace.moment(j);
+ var after = try later.events(gpa);
+ defer after.deinit(gpa);
+ while (after.next()) |item| if (item.ev.kind == .step and item.ev.tid == branch.tid) break :next item.ev.a[0];
+ } else unreachable;
+ switch (block.end) {
+ .ret => try std.testing.expectEqual(@as(u16, 3), branch.aux),
+ .jump, .tail => try std.testing.expectEqual(block.to.?, next),
+ .branch => try std.testing.expectEqual(if (branch.a[1] != 0) block.to.? else block.falls.?, next),
+ // A jump through memory goes where the event says.
+ .indirect => try std.testing.expectEqual(branch.a[0], next),
+ else => return error.NotABranch,
+ }
+ tied += 1;
+ }
+ return .{ tied, loose };
+}
+
+test "a function's basic blocks from a recording, and the edges a run took: two loops" {
+ var trace = try zt.Trace.open(gpa, io, targets.list_recording);
+ defer trace.close();
+ var out: [16]zt.telescope.Block = undefined;
+ // Their blocks, by `objdump -d` of zig-out/targets/list (-O1):
+ //
+ // reverse: +0 test rdi, rdi list_done: +0 test rdi, rdi
+ // +3 je +25 +3 je +1e
+ // +5 push rbp +5 push rbp
+ // +6 mov rbp, rsp +6 mov rbp, rsp
+ // +9 xor eax, eax +9 xor eax, eax
+ // +b nop +b nop
+ // +10 mov rcx, rax +10 add rax, [rdi]
+ // +13 mov rax, rdi +13 mov rdi, [rdi + 8]
+ // +16 mov rdi, [rdi + 8] +17 test rdi, rdi
+ // +1a mov [rax + 8], rcx +1a jne +10
+ // +1e test rdi, rdi +1c pop rbp
+ // +21 jne +10 +1d ret
+ // +23 pop rbp +1e xor eax, eax
+ // +24 ret +20 ret
+ // +25 xor eax, eax
+ // +27 ret
+ //
+ // The empty list's test, the frame falling into the loop, the loop
+ // back to itself, and two returns.
+ const Want = struct { u64, u64, zt.Debugger.End, ?u64, ?u64 };
+ for ([_][]const u8{ "reverse", "list_done" }, [_][5]Want{
+ .{ .{ 0, 5, .branch, 0x25, 5 }, .{ 5, 0xb, .fall, null, 0x10 }, .{ 0x10, 0x13, .branch, 0x10, 0x23 }, .{ 0x23, 2, .ret, null, null }, .{ 0x25, 3, .ret, null, null } },
+ .{ .{ 0, 5, .branch, 0x1e, 5 }, .{ 5, 0xb, .fall, null, 0x10 }, .{ 0x10, 0xc, .branch, 0x10, 0x1c }, .{ 0x1c, 2, .ret, null, null }, .{ 0x1e, 3, .ret, null, null } },
+ }) |name, want| {
+ // The first stop in the function.
+ const m, const pc = find: for (0..trace.len) |i| {
+ const m = try trace.moment(i);
+ const tids = try m.threads(gpa);
+ defer gpa.free(tids);
+ const regs = (try m.regs(tids[0])) orelse continue;
+ if (std.mem.startsWith(u8, m.trace.strings.get(regs.rip) orelse "", name)) break :find .{ m, regs.rip };
+ } else return error.NotReached;
+ const g = zt.telescope.blocks(m, pc, &out).?;
+ try std.testing.expect(g.text);
+ try std.testing.expectEqual(want.len, g.count);
+ const here: []const u8 = m.trace.strings.get(pc).?;
+ try std.testing.expectEqual(g.start, pc - try std.fmt.parseInt(u64, here[name.len + 1 ..], 10));
+ for (want, g.blocks) |w, b| {
+ try std.testing.expectEqual(g.start + w[0], b.start);
+ try std.testing.expectEqual(w[1], b.len);
+ try std.testing.expectEqual(w[2], b.end);
+ try std.testing.expectEqual(if (w[3]) |to| g.start + to else null, b.to);
+ try std.testing.expectEqual(if (w[4]) |falls| g.start + falls else null, b.falls);
+ }
+ }
+ const tied, const loose = try tieBranches(&trace);
+ try std.testing.expect(tied > 10 and loose == 0);
+}
+
+test "a libc function's basic blocks, from its unwind bounds, at its system call" {
+ var trace = try zt.Trace.open(gpa, io, targets.hello_recording);
+ defer trace.close();
+ var out: [64]zt.telescope.Block = undefined;
+ var text: [256]u8 = undefined;
+ var checked: usize = 0;
+ for (0..trace.len) |i| {
+ const m = try trace.moment(i);
+ const tids = try m.threads(gpa);
+ defer gpa.free(tids);
+ const regs = (try m.regs(tids[0])) orelse continue;
+ const insn = (try zt.telescope.instruction(m, regs.rip, &text)) orelse continue;
+ if (!std.mem.eql(u8, insn.text, "syscall") or !std.mem.startsWith(u8, m.trace.strings.get(regs.rip) orelse "", "libc.so.6!open+")) continue;
+ const g = zt.telescope.blocks(m, regs.rip, &out).?;
+ // open's, whole: from its first instruction, every instruction's text there.
+ try std.testing.expectEqualStrings("libc.so.6!open+0", m.trace.strings.get(g.start).?);
+ try std.testing.expect(g.text and g.count <= out.len);
+ const here = g.blocks[g.here.?];
+ try std.testing.expect(here.start <= regs.rip and regs.rip < here.start + here.len);
+ // The blocks run end to end, each a run of instructions, every edge in the function to a block's start.
+ var at = g.start;
+ for (g.blocks) |b| {
+ try std.testing.expectEqual(at, b.start);
+ at += b.len;
+ var pc = b.start;
+ while (pc < b.start + b.len) pc += (try zt.telescope.instruction(m, pc, &text)).?.len;
+ try std.testing.expectEqual(b.start + b.len, pc);
+ for ([_]?u64{ b.to, b.falls }) |edge| if (edge) |to| if (to -% g.start < g.len) {
+ for (g.blocks) |c| {
+ if (c.start == to) break;
+ } else return error.EdgeIntoABlock;
+ };
+ }
+ try std.testing.expectEqual(g.start + g.len, at);
+ // Its return, and a call that does not return: __stack_chk_fail.
+ var ends: [2]bool = @splat(false);
+ for (g.blocks) |b| {
+ if (b.end == .ret) ends[0] = true;
+ if (b.end == .noreturn) if (b.to) |callee| if (std.mem.indexOf(u8, m.trace.strings.get(callee) orelse "", "__stack_chk_fail") != null) {
+ ends[1] = true;
+ };
+ }
+ try std.testing.expectEqual([2]bool{ true, true }, ends);
+ checked += 1;
+ }
+ try std.testing.expectEqual(@as(usize, 1), checked);
+ // Every jump and return of main, the PLT, the resolver and libc, tied to its edge.
+ const tied, const loose = try tieBranches(&trace);
+ try std.testing.expect(tied > 300 and loose < 10);
+}
+
+/// Runs a command, its output kept, with the environment ASan wants under a
+/// tracer: no leak check (LeakSanitizer cannot work under ptrace).
+fn runQuiet(argv: []const []const u8) !std.process.RunResult {
+ var env = std.process.Environ.Map.init(gpa);
+ defer env.deinit();
+ try env.put("ASAN_OPTIONS", "detect_leaks=0");
+ return std.process.run(gpa, io, .{ .argv = argv, .environ_map = &env });
+}
+
+fn exited(result: std.process.RunResult) ?u8 {
+ defer gpa.free(result.stdout);
+ defer gpa.free(result.stderr);
+ return switch (result.term) {
+ .exited => |code| code,
+ else => null,
+ };
+}
+
+/// The last moment's events of a kind, from a recording: the stops and exits that end a run.
+fn lastOf(trace: *const zt.Trace, kind: zt.Kind) !?zt.Event {
+ var found: ?zt.Event = null;
+ for (0..trace.len) |i| {
+ var events = try (try trace.moment(i)).events(gpa);
+ defer events.deinit(gpa);
+ while (events.next()) |item| if (item.ev.kind == kind) {
+ found = item.ev;
+ };
+ }
+ return found;
+}
+
+test "a stack overflow built plain: past the buffer, its own counter smashed, it writes to the stack's end and faults there" {
+ var tmp = std.testing.tmpDir(.{});
+ defer tmp.cleanup();
+ var dir_buf: [std.Io.Dir.max_path_bytes]u8 = undefined;
+ const dir = dir_buf[0..try tmp.dir.realPath(io, &dir_buf)];
+ const path = try std.fs.path.join(gpa, &.{ dir, "plain.ztrace" });
+ defer gpa.free(path);
+ try std.testing.expectEqual(@as(?u8, 0), exited(try runQuiet(&.{ targets.ztrace, "record", "--by", "syscall", "--from", "fill", "-o", path, "--", targets.overflow, "x" })));
+ var trace = try zt.Trace.open(gpa, io, path);
+ defer trace.close();
+ // SIGSEGV at a store of the loop in fill, its address just past the stack's top.
+ const signal = (try lastOf(&trace, .signal)).?;
+ try std.testing.expectEqual(@as(u16, @backingInt(linux.SIG.SEGV)), signal.aux);
+ const m = try trace.moment(trace.len - 1);
+ try std.testing.expect(std.mem.startsWith(u8, m.trace.strings.get(signal.a[1]) orelse "", "fill+"));
+ var name: []const u8 = "";
+ var buf: [64]u8 = undefined;
+ try std.testing.expect(try m.mapping(signal.a[0], null, &buf) == null);
+ _ = (try m.mapping(signal.a[0] - 1, &name, &buf)).?;
+ try std.testing.expectEqualStrings("[stack]", name);
+ try std.testing.expectEqual(@as(u64, 128 + @backingInt(linux.SIG.SEGV)), (try lastOf(&trace, .exit)).?.a[0]);
+}
+
+test "the same overflow built with ASan, by gcc and by clang: its shadow round the buffer, the branch into its report, the report's text and the exit" {
+ var tmp = std.testing.tmpDir(.{});
+ defer tmp.cleanup();
+ var dir_buf: [std.Io.Dir.max_path_bytes]u8 = undefined;
+ const dir = dir_buf[0..try tmp.dir.realPath(io, &dir_buf)];
+ var built: usize = 0;
+ for ([_][]const u8{ "gcc", "clang" }) |cc| {
+ const exe = try std.fs.path.join(gpa, &.{ dir, cc });
+ defer gpa.free(exe);
+ // A compiler that is not here, or has no ASan runtime, is passed over.
+ const compiled = exited(runQuiet(&.{ cc, "-fsanitize=address", "-O0", "-g", targets.overflow_source, "-o", exe }) catch continue);
+ if (compiled != 0) continue;
+ built += 1;
+
+ // By instruction from fill into the report: the stop at its first instruction.
+ const steps = try std.fs.path.join(gpa, &.{ dir, "steps.ztrace" });
+ defer gpa.free(steps);
+ try std.testing.expectEqual(@as(?u8, 0), exited(try runQuiet(&.{ targets.ztrace, "record", "--by", "insn", "--from", "fill", "--asan", "--stack", "512", "--steps", "3000", "-o", steps, "--", exe, "x" })));
+ var trace = try zt.Trace.open(gpa, io, steps);
+ defer trace.close();
+ const at = for (1..trace.len) |i| {
+ const m = try trace.moment(i);
+ const tids = try m.threads(gpa);
+ defer gpa.free(tids);
+ const regs = (try m.regs(tids[0])) orelse continue;
+ if (std.mem.indexOf(u8, m.trace.strings.get(regs.rip) orelse "", "__asan_report_store1+0") != null) break i;
+ } else return error.NoReport;
+ const m = try trace.moment(at);
+ const tids = try m.threads(gpa);
+ defer gpa.free(tids);
+ const regs = (try m.regs(tids[0])).?;
+ // Its argument is the first byte past buf: buf's 16 bytes addressable
+ // (00 00), the left redzone before them (f1), the right one from there (f3).
+ for ([_]i64{ -48, -40, -32, -24, -16, -8, 0, 8 }, [_]u8{ 0xf1, 0xf1, 0xf1, 0xf1, 0, 0, 0xf3, 0xf3 }) |off, want| {
+ const s = (try zt.telescope.shadow(m, regs.rdi +% @as(u64, @bitCast(off)))).?;
+ try std.testing.expectEqual(@as(?u8, want), s.value);
+ }
+ // Reached by a branch taken (gcc's through its PLT stub), and walked back to main.
+ var events = try (try trace.moment(at - 1)).events(gpa);
+ defer events.deinit(gpa);
+ const into = while (events.next()) |item| {
+ if (item.ev.kind == .branch) break item.ev;
+ } else return error.NoBranch;
+ try std.testing.expectEqual(regs.rip, into.a[0]);
+ try std.testing.expectEqual(@as(u64, 1), into.a[1]);
+ var chain_buf: [16]u64 = undefined;
+ const chain = try zt.telescope.backtrace(m, &regs, &chain_buf);
+ try std.testing.expect(std.mem.startsWith(u8, m.trace.strings.get(chain[1]).?, "fill+"));
+ try std.testing.expect(std.mem.startsWith(u8, m.trace.strings.get(chain[2]).?, "main+"));
+ // The runtime's calls in fill are named: its fake stack's allocation too.
+ var names = trace.strings.valueIterator();
+ while (names.next()) |text| {
+ if (std.mem.indexOf(u8, text.*, "__asan_stack_malloc_") != null) break;
+ } else return error.NoStackMalloc;
+
+ // By syscall to the end: the report as it was written, and the exit.
+ const end = try std.fs.path.join(gpa, &.{ dir, "end.ztrace" });
+ defer gpa.free(end);
+ try std.testing.expectEqual(@as(?u8, 0), exited(try runQuiet(&.{ targets.ztrace, "record", "--by", "syscall", "--from", "fill", "--asan", "-s", "4096", "-o", end, "--", exe, "x" })));
+ var whole = try zt.Trace.open(gpa, io, end);
+ defer whole.close();
+ var reported = false;
+ for (0..whole.len) |i| {
+ var all = try (try whole.moment(i)).events(gpa);
+ defer all.deinit(gpa);
+ while (all.next()) |item| if (item.ev.kind == .syscall_enter and item.ev.aux == @backingInt(linux.SYS.write) and item.ev.a[0] == 2) {
+ if (std.mem.indexOf(u8, item.payload, "ERROR: AddressSanitizer: stack-buffer-overflow") != null) reported = true;
+ };
+ }
+ try std.testing.expect(reported);
+ try std.testing.expectEqual(@as(u64, 1), (try lastOf(&whole, .exit)).?.a[0]);
+ }
+ if (built == 0) return error.SkipZigTest;
+}
+
test "step walks the source lines, in and out of calls, as gdb does" {
var d = try spawn(targets.list, "2", null);
defer d.deinit();
diff --git a/src/trace/event.zig b/src/trace/event.zig
index 02deb51..24caff4 100644
--- a/src/trace/event.zig
+++ b/src/trace/event.zig
@@ -198,6 +198,13 @@ pub fn frameId(addr: u64) u64 {
return addr | 1 << 61;
}
+/// The id of the string that holds the basic blocks of the function that
+/// begins at `addr` (`Debugger.emitBlocks`), found as a frame's is: the
+/// greatest at or below the pc's. Bits 61 and 62 both.
+pub fn blocksId(addr: u64) u64 {
+ return addr | 3 << 61;
+}
+
pub fn now() u64 {
var ts: std.os.linux.timespec = undefined;
_ = std.os.linux.clock_gettime(.MONOTONIC, &ts);
diff --git a/src/trace/telescope.zig b/src/trace/telescope.zig
index 6ab2929..006bb22 100644
--- a/src/trace/telescope.zig
+++ b/src/trace/telescope.zig
@@ -293,6 +293,72 @@ pub fn function(m: Moment, pc: u64) ?Function {
return .{ .start = start, .len = len, .base = t[4], .rows = t[7..][0..rows], .locals = t[7 + rows ..] };
}
+/// A basic block of a function: where it is, how it ends
+/// (`Debugger.End`), and its edges.
+pub const Block = struct {
+ start: u64,
+ len: u64,
+ end: Debugger.End,
+ /// Where it goes: a jump's target, a conditional jump's when taken, a
+ /// tail call's or a call's that does not return; null for none, or
+ /// where it is not known (`indirect`).
+ to: ?u64,
+ /// The block it falls into, after it: `fall`'s, and a conditional
+ /// jump's when not taken; null otherwise.
+ falls: ?u64,
+};
+
+/// A function as its blocks, from the recording (`Debugger.emitBlocks`):
+/// its bounds, its blocks in address order (`blocks`, as many as `out`
+/// holds of `count`), the one that holds the pc, and whether every
+/// instruction's text is recorded (`instruction`; false past
+/// `Debugger.function_text`, the blocks recorded without it).
+pub const Graph = struct { start: u64, len: u64, blocks: []Block, count: usize, here: ?usize, text: bool };
+
+/// The blocks of the function that holds `pc`; null where the recording
+/// has none (no stop was ever in it).
+pub fn blocks(m: Moment, pc: u64, out: []Block) ?Graph {
+ const found = m.trace.stringBelow(event.blocksId(pc)) orelse return null;
+ if (found.id < event.blocksId(0)) return null;
+ const start = found.id - event.blocksId(0);
+ const t = found.text;
+ if (t.len < 5) return null;
+ const len = std.mem.readInt(u32, t[0..4], .little);
+ if (pc - start >= len) return null;
+ const size = @sizeOf(Debugger.Block);
+ const count = (t.len - 5) / size;
+ var g: Graph = .{ .start = start, .len = len, .blocks = out[0..@min(out.len, count)], .count = count, .here = null, .text = t[4] != 0 };
+ for (0..count) |i| {
+ const b = std.mem.bytesToValue(Debugger.Block, t[5 + i * size ..][0..size]);
+ const at = start + b.offset;
+ if (pc -% at < b.len) g.here = i;
+ if (i >= out.len) continue;
+ const to: ?u64 = switch (b.end) {
+ .jump, .branch, .tail, .noreturn => if (b.to == Debugger.no_target) null else start +% @as(u64, @bitCast(@as(i64, b.to))),
+ else => null,
+ };
+ out[i] = .{ .start = at, .len = b.len, .end = b.end, .to = to, .falls = if (b.end == .fall or b.end == .branch) at + b.len else null };
+ }
+ return g;
+}
+
+/// ASan's shadow byte of `addr` at a moment (`ztrace record --asan`): where
+/// it is, and what it holds where the recording has it: 0 all of its 8
+/// bytes addressable, 1 to 7 that many first ones, else why none is (f1 a
+/// stack frame's left redzone, f2 between its variables, f3 its right, f5
+/// a frame returned from, f8 a scope left, fa a heap block's redzone, fd
+/// freed). Null for a recording without the shadow.
+pub fn shadow(m: Moment, addr: u64) !?struct { addr: u64, value: ?u8 } {
+ const text = m.trace.strings.get(Debugger.asan_id) orelse return null;
+ if (text.len != @sizeOf(Debugger.Asan)) return null;
+ const asan = std.mem.bytesToValue(Debugger.Asan, text[0..@sizeOf(Debugger.Asan)]);
+ const at = (addr >> @intCast(asan.scale)) + asan.offset;
+ var byte: [1]u8 = undefined;
+ var known: [1]bool = undefined;
+ try m.read(at, &byte, &known);
+ return .{ .addr = at, .value = if (known[0]) byte[0] else null };
+}
+
/// A GOT slot at a moment: what it holds, and whether that is still the way
/// back into the PLT (`lazy`: the next call through it runs the loader's
/// resolver, which binds it) rather than the function. Null where the
@@ -533,3 +599,51 @@ test "frames walked by their call frame information; each stack word's role" {
var two: [2]u64 = undefined;
try std.testing.expectEqual(@as(u64, 0x400050), (try backtrace(m, &entry, &two))[1]);
}
+
+test "a function's blocks: their edges, the one that holds the pc, and whether their text is recorded" {
+ const gpa = std.testing.allocator;
+ var tmp = std.testing.tmpDir(.{});
+ defer tmp.cleanup();
+ var dir_buf: [std.Io.Dir.max_path_bytes]u8 = undefined;
+ const dir = dir_buf[0..try tmp.dir.realPath(std.testing.io, &dir_buf)];
+ const path = try std.fs.path.join(gpa, &.{ dir, "t.ztrace" });
+ defer gpa.free(path);
+
+ var rec = try store.Recorder.create(gpa, std.testing.io, path);
+ // A function at 400000, 0x40 long, past the text budget (its byte 0): a
+ // test that branches over a loop, the loop, a call through a register
+ // that never returns, and a tail call.
+ const B = Debugger.Block;
+ const blocks_ = [_]B{
+ .{ .offset = 0, .len = 8, .to = 0x20, .end = .branch },
+ .{ .offset = 8, .len = 0x10, .to = 8, .end = .branch },
+ .{ .offset = 0x18, .len = 8, .to = Debugger.no_target, .end = .noreturn },
+ .{ .offset = 0x20, .len = 0x20, .to = 0x1000, .end = .tail },
+ };
+ try rec.emit(.{ .kind = .string, .a = .{ event.blocksId(0x400000), 0, 0, 0, 0, 0 } }, "\x40\x00\x00\x00\x00" ++ std.mem.asBytes(&blocks_));
+ try rec.emit(.{ .kind = .mark, .tid = 1 }, "");
+ try rec.close();
+
+ var trace = try store.Trace.open(gpa, std.testing.io, path);
+ defer trace.close();
+ const m = try trace.moment(0);
+ var out: [3]Block = undefined;
+ const g = blocks(m, 0x400024, &out).?;
+ try std.testing.expectEqual(@as(u64, 0x400000), g.start);
+ try std.testing.expectEqual(@as(u64, 0x40), g.len);
+ try std.testing.expect(!g.text);
+ // Four blocks, three of them given; the pc in the last.
+ try std.testing.expectEqual(@as(usize, 4), g.count);
+ try std.testing.expectEqual(@as(usize, 3), g.blocks.len);
+ try std.testing.expectEqual(@as(?usize, 3), g.here);
+ try std.testing.expectEqualSlices(Block, &.{
+ .{ .start = 0x400000, .len = 8, .end = .branch, .to = 0x400020, .falls = 0x400008 },
+ .{ .start = 0x400008, .len = 0x10, .end = .branch, .to = 0x400008, .falls = 0x400018 },
+ .{ .start = 0x400018, .len = 8, .end = .noreturn, .to = null, .falls = null },
+ }, g.blocks);
+ var all: [4]Block = undefined;
+ try std.testing.expectEqual(Block{ .start = 0x400020, .len = 0x20, .end = .tail, .to = 0x401000, .falls = null }, blocks(m, 0x400020, &all).?.blocks[3]);
+ // Outside it, nothing.
+ try std.testing.expect(blocks(m, 0x400040, &all) == null);
+ try std.testing.expect(blocks(m, 0x3fffff, &all) == null);
+}