diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/cli/dbg.zig | 7 | ||||
| -rw-r--r-- | src/trace/Debugger.zig | 264 | ||||
| -rw-r--r-- | src/trace/Symbols.zig | 480 | ||||
| -rw-r--r-- | src/trace/debugger_test.zig | 150 | ||||
| -rw-r--r-- | src/trace/event.zig | 11 | ||||
| -rw-r--r-- | src/trace/store.zig | 20 | ||||
| -rw-r--r-- | src/trace/telescope.zig | 263 |
7 files changed, 1125 insertions, 70 deletions
diff --git a/src/cli/dbg.zig b/src/cli/dbg.zig index 5fcf88e..c60bff2 100644 --- a/src/cli/dbg.zig +++ b/src/cli/dbg.zig @@ -24,7 +24,7 @@ pub const usage = \\ watch WHAT [LEN] record a region at every stop: an address or a symbol \\ regs the registers \\ x WHAT [LEN] memory at an address, a symbol or $register (64 bytes) - \\ bt the call chain, by frame pointer + \\ bt the call chain, by the unwind tables or the frame pointer \\ context, ctx everything at once, pwndbg's way: registers followed \\ as pointers, the instructions at the pc, the stack \\ back [N] look N moments back in the recording: regs, x @@ -301,6 +301,11 @@ const Session = struct { mem.s.fetch(mem.m, addr, buf, known[0..buf.len]) catch return 0; return std.mem.indexOfScalar(bool, known[0..buf.len], false) orelse buf.len; } + + /// The program's call frame information, the same now as at any moment. + pub fn cfi(mem: Memory, pc: u64) ?zt.Symbols.Cfi { + return mem.s.d.cfi(pc); + } }; /// The stop the program is at now. diff --git a/src/trace/Debugger.zig b/src/trace/Debugger.zig index da7a73b..5310ad3 100644 --- a/src/trace/Debugger.zig +++ b/src/trace/Debugger.zig @@ -101,6 +101,10 @@ telescope_around: usize = 0, /// with the length of each. described: std.AutoHashMapUnmanaged(u64, void) = .empty, code_len: std.AutoHashMapUnmanaged(u64, u8) = .empty, +/// The call frame information at each pc a recorded walk met, its +/// function's frame recorded (null: none there); forgotten when the +/// mappings change. +unwound: std.AutoHashMapUnmanaged(u64, ?Symbols.Cfi) = .empty, /// The static probes armed (`usdt`): what each one's hook reads. sites: std.ArrayList(*Site) = .empty, /// The threads that have stopped before: a first stop is a thread's birth. @@ -171,6 +175,7 @@ fn begin(gpa: std.mem.Allocator, io: std.Io, proc: ptrace.Process, sink: ?event. try d.threads.put(gpa, proc.pid, {}); d.regs = try d.proc.regs(); try d.refreshMaps(); + try d.emitStart(); // Where the target is now: the first stop. _ = try d.report(.step); return d; @@ -189,6 +194,7 @@ pub fn deinit(d: *Debugger) void { d.sites.deinit(d.gpa); d.described.deinit(d.gpa); d.code_len.deinit(d.gpa); + d.unwound.deinit(d.gpa); var decoded = d.functions.valueIterator(); while (decoded.next()) |starts| d.gpa.free(starts.*); d.functions.deinit(d.gpa); @@ -621,19 +627,16 @@ fn emitTelescope(d: *Debugger) !void { var words: [256]u64 = undefined; const n = d.read(r.rsp, std.mem.sliceAsBytes(words[0..@min(words.len, d.telescope_words)])) / 8; for (words[0..n]) |value| try d.chase(value); - // The call chain: each frame's saved pointer and return address - // recorded, the return addresses named, so a viewer walks it again. - var fp = r.rbp; - for (0..16) |_| { - if (fp == 0 or fp & 7 != 0) break; - const frame = try d.snap(fp, 16); - if (frame.len < 16) break; - const next = std.mem.readInt(u64, frame[0..8], .little); - const ret = std.mem.readInt(u64, frame[8..16], .little); - try d.chase(ret); - try d.emitCall(ret); - if (next <= fp) break; - fp = next; + // The call chain, walked as a reader will walk it again (`Recorded`), + // each return address named. + var rec: Recorded = .{ .d = d }; + var chain: [32]Frame = undefined; + const at_entry = if (d.syms.symbolAt(r.rip)) |sym| sym.addr == r.rip else false; + const found = frames(&rec, r, at_entry, &chain); + if (rec.failed) |err| return err; + for (found[@min(1, found.len)..]) |f| { + try d.chase(f.pc); + try d.emitCall(f.pc); } } @@ -757,6 +760,7 @@ fn emitLine(d: *Debugger) !void { pub fn refreshMaps(d: *Debugger) !void { const old = try d.syms.refresh(d.proc.pid); defer d.syms.free(old); + d.unwound.clearRetainingCapacity(); if (d.sink == null) return; const now = d.syms.maps.list; for (old.list) |o| { @@ -809,6 +813,13 @@ fn snap(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)]; + try d.send(start, bytes); + return bytes; +} + +/// Sends the words of `bytes`, read at `start` (a word's address), that +/// the sink was not sent before or that changed since. +fn send(d: *Debugger, start: u64, bytes: []const u8) !void { var page: *Page = undefined; var page_index: u64 = std.math.maxInt(u64); // Where the run of changed words being gathered began. @@ -839,7 +850,6 @@ fn snap(d: *Debugger, addr: u64, len: usize) ![]const u8 { } } if (run_from) |from| try d.emitWrite(start + from, bytes[from..]); - return bytes; } fn emitWrite(d: *Debugger, addr: u64, bytes: []const u8) !void { @@ -1002,12 +1012,16 @@ fn know(d: *Debugger, addr: u64) void { d.refreshMaps() catch {}; } -/// The call chain by frame pointer: the pc, then each return address -/// outwards. `mem` is what has the stack: anything with -/// `read(addr, buf) usize`, the debugger or a moment of a recording. -/// `at_entry` says the pc is a function's first instruction, where its -/// caller's address is still on top of the stack. -// shortcut: a function that keeps no frame hides its caller (a leaf, or one stopped inside its prologue), upgrade with the unwind tables (`std.debug.Dwarf.Unwind`). +/// The call chain: the pc, then each return address outwards. `mem` is +/// what has the stack: anything with `read(addr, buf) usize`, the debugger +/// or a moment of a recording. Where it also has `cfi(pc) ?Symbols.Cfi` +/// (both do) a frame is walked through by its call frame information, +/// which is right inside a function that keeps no frame and inside a +/// prologue; where there is none for the pc (code without unwind tables, a +/// JIT's, a PLT entry, a signal frame), by the frame pointer. `at_entry` +/// says the pc is a function's first instruction, where its caller's +/// address is still on top of the stack: the frame pointer's walk needs +/// telling. pub fn backtrace(mem: anytype, regs: *const Regs, at_entry: bool, out: []u64) []u64 { return walk(u64, mem, regs, at_entry, out); } @@ -1023,30 +1037,200 @@ pub fn frames(mem: anytype, regs: *const Regs, at_entry: bool, out: []Frame) []F return walk(Frame, mem, regs, at_entry, out); } +/// A frame as the walk found it: where its function begins (0: not known) +/// and the row of call frame information it was walked through by (null: +/// by the frame pointer, its saved rbp at `high - 16`). +pub const Unwound = struct { frame: Frame, function: u64 = 0, row: ?Symbols.Row = null }; + +/// `frames`, each with how it was walked: what tells which of its words +/// are saved registers and its return address. +pub fn unwind(mem: anytype, regs: *const Regs, at_entry: bool, out: []Unwound) []Unwound { + return walk(Unwound, mem, regs, at_entry, out); +} + fn walk(comptime T: type, mem: anytype, regs: *const Regs, at_entry: bool, out: []T) []T { + const Mem = switch (@typeInfo(@TypeOf(mem))) { + .pointer => |p| p.child, + else => @TypeOf(mem), + }; + // The registers known in the frame walked, by DWARF's number: rax rdx + // rcx rbx rsi rdi rbp rsp, r8 to r15, the pc. In a caller only those a + // call keeps are, and of them the ones its callee saved or left alone. + var r: [17]?u64 = .{ regs.rax, regs.rdx, regs.rcx, regs.rbx, regs.rsi, regs.rdi, regs.rbp, regs.rsp, regs.r8, regs.r9, regs.r10, regs.r11, regs.r12, regs.r13, regs.r14, regs.r15, regs.rip }; var n: usize = 0; - var pc = regs.rip; - var fp = regs.rbp; - var low = regs.rsp; - var frame: [16]u8 = undefined; - if (at_entry and out.len > 1 and mem.read(regs.rsp, frame[0..8]) == 8) { - // Its frame is the return address alone. - out[0] = if (T == u64) pc else .{ .pc = pc, .low = low, .high = low + 8 }; - n = 1; - low += 8; - pc = std.mem.readInt(u64, frame[0..8], .little); - } - while (n < out.len) { + while (n < out.len) : (n += 1) { + const pc = r[16] orelse break; + if (pc == 0 and n > 0) break; + const sp = r[7].?; + var next: [17]?u64 = @splat(null); + for ([_]u8{ 3, 6, 12, 13, 14, 15 }) |kept| next[kept] = r[kept]; + // A caller's pc is a return address, which may be past the call's function. + const info: ?Symbols.Cfi = if (@hasDecl(Mem, "cfi")) mem.cfi(if (n == 0) pc else pc -% 1) else null; + by_cfi: { + const c = info orelse break :by_cfi; + const base = (if (c.row.cfa_reg < r.len) r[c.row.cfa_reg] else null) orelse break :by_cfi; + const cfa = base +% @as(u64, @bitCast(@as(i64, c.row.cfa))); + if (cfa <= sp or c.row.saved[6] == Symbols.lost) break :by_cfi; + set(T, &out[n], .{ .frame = .{ .pc = pc, .low = sp, .high = cfa }, .function = c.function, .row = c.row }); + next[7] = cfa; + for (Symbols.saved_registers, c.row.saved) |reg, at| { + if (at != 0) next[reg] = if (at == Symbols.lost) null else wordAt(mem, cfa +% @as(u64, @bitCast(@as(i64, at) * 8))); + } + r = next; + continue; + } + if (n == 0 and at_entry) if (wordAt(mem, sp)) |ret| { + // Its frame is the return address alone. + set(T, &out[n], .{ .frame = .{ .pc = pc, .low = sp, .high = sp + 8 } }); + next[7] = sp + 8; + next[16] = ret; + r = next; + continue; + }; + // By the frame pointer: the caller's rbp and pc are at rbp, and + // where its other registers are is not known. + const fp = r[6] orelse 0; + var frame: [16]u8 = undefined; const known = fp != 0 and mem.read(fp, &frame) == 16; - out[n] = if (T == u64) pc else .{ .pc = pc, .low = low, .high = if (known and fp >= low) fp + 16 else low }; - n += 1; - if (!known) break; - low = @max(low, fp + 16); - const next = std.mem.readInt(u64, frame[0..8], .little); - pc = std.mem.readInt(u64, frame[8..16], .little); + set(T, &out[n], .{ .frame = .{ .pc = pc, .low = sp, .high = if (known and fp >= sp) fp + 16 else sp } }); + if (!known) { + n += 1; + break; + } + const up = std.mem.readInt(u64, frame[0..8], .little); + const ret = std.mem.readInt(u64, frame[8..16], .little); // Frames lie up the stack: one that does not is not a frame. - if (pc == 0 or (next != 0 and next <= fp)) break; - fp = next; + if (ret == 0 or (up != 0 and up <= fp)) { + n += 1; + break; + } + next = @splat(null); + next[6] = up; + next[7] = @max(sp, fp + 16); + next[16] = ret; + r = next; } return out[0..n]; } + +fn set(comptime T: type, slot: *T, found: Unwound) void { + slot.* = switch (T) { + u64 => found.frame.pc, + Frame => found.frame, + else => found, + }; +} + +/// The word at `addr`, where `mem` has it. +fn wordAt(mem: anytype, addr: u64) ?u64 { + var bytes: [8]u8 = undefined; + return if (mem.read(addr, &bytes) == 8) std.mem.readInt(u64, &bytes, .little) else null; +} + +/// The call frame information at `pc`: what makes the debugger a `mem` the +/// call chain is walked through by it. +pub fn cfi(d: *Debugger, pc: u64) ?Symbols.Cfi { + return d.syms.cfi(pc); +} + +/// The target's memory as a walk of the call chain reads it, every word it +/// reads recorded, and the frame of every function it goes through +/// (`emitFunction`): so a reader walks the same chain from the recording. +const Recorded = struct { + d: *Debugger, + failed: ?anyerror = null, + /// The stack as last read, a page at a time: a walk goes up it. + window: [4096]u8 = undefined, + from: u64 = 0, + len: usize = 0, + + pub fn read(rec: *Recorded, addr: u64, buf: []u8) usize { + if (addr < rec.from or addr + buf.len > rec.from + rec.len) { + rec.from = addr & ~@as(u64, 7); + rec.len = rec.d.read(rec.from, &rec.window) & ~@as(usize, 7); + if (addr + buf.len > rec.from + rec.len) return 0; + } + const start = addr & ~@as(u64, 7); + const end = std.mem.alignForward(u64, addr + buf.len, 8); + rec.d.send(start, rec.window[start - rec.from .. end - rec.from]) catch |err| { + rec.failed = err; + return 0; + }; + @memcpy(buf, rec.window[addr - rec.from ..][0..buf.len]); + return buf.len; + } + + pub fn cfi(rec: *Recorded, pc: u64) ?Symbols.Cfi { + const d = rec.d; + if (d.unwound.get(pc)) |known| return known; + const found: ?Symbols.Cfi = if (d.syms.functionAt(pc)) |f| found: { + d.emitFunction(f) catch |err| { + rec.failed = err; + return null; + }; + break :found .{ .function = f.start, .row = f.rowAt(pc) }; + } else null; + d.unwound.put(d.gpa, pc, found) catch |err| { + rec.failed = err; + }; + return found; + } +}; + +/// A function's frame as a reader needs it to walk through it and to name +/// its stack's words, recorded once as a string (`event.frameId` of where +/// it begins): its length (4 bytes), what its locals are from (a byte, +/// `Symbols.Function.base`), how many rows (2 bytes), the rows +/// (`Symbols.Row`), then each local (`Symbols.Local`): its offset from the +/// base, its size, the stretch of the function's code it is in, from and +/// to (4 bytes each), its name and a zero. +fn emitFunction(d: *Debugger, f: Symbols.Function) !void { + if ((try d.described.getOrPut(d.gpa, event.frameId(f.start))).found_existing) return; + var text: std.Io.Writer.Allocating = .init(d.gpa); + defer text.deinit(); + const w = &text.writer; + try w.writeInt(u32, std.math.cast(u32, f.len) orelse 0, .little); + try w.writeByte(f.base); + try w.writeInt(u16, @intCast(@min(f.rows.len, std.math.maxInt(u16))), .little); + try w.writeAll(std.mem.sliceAsBytes(f.rows[0..@min(f.rows.len, std.math.maxInt(u16))])); + for (f.locals) |local| { + try w.writeInt(i32, local.offset, .little); + try w.writeInt(u32, local.size, .little); + try w.writeInt(u32, local.from, .little); + try w.writeInt(u32, local.to, .little); + try w.writeAll(local.name); + try w.writeByte(0); + } + try d.emit(.{ .kind = .string, .a = .{ event.frameId(f.start), 0, 0, 0, 0, 0 } }, text.written()); +} + +/// Where the process's first stack is: the stack pointer at its exec, where +/// argc is, then the `argc` pointers of argv and a zero, the `envc` of envp +/// and a zero, and the `auxc` entries of the auxiliary vector (two words +/// each) and the zero entry that ends it. Recorded as the string +/// `event.frameId(0)`. +pub const Start = extern struct { sp: u64, argc: u64, envc: u64, auxc: u64 }; + +fn emitStart(d: *Debugger) !void { + if (d.sink == null) return; + // The kernel keeps it, also for a process attached to: /proc/pid/stat's + // 28th field, after the name in parentheses. + var path_buf: [32]u8 = undefined; + const path = std.fmt.bufPrint(&path_buf, "/proc/{d}/stat", .{d.proc.pid}) catch unreachable; + const file = std.Io.Dir.cwd().openFile(d.syms.io, path, .{}) catch return; + defer file.close(d.syms.io); + var read_buf: [256]u8 = undefined; + var reader = file.readerStreaming(d.syms.io, &read_buf); + var text: [1024]u8 = undefined; + const n = reader.interface.readSliceShort(&text) catch return; + const name_end = std.mem.lastIndexOfScalar(u8, text[0..n], ')') orelse return; + var fields = std.mem.tokenizeScalar(u8, text[name_end + 1 .. n], ' '); + for (0..25) |_| _ = fields.next(); + const sp = std.fmt.parseInt(u64, fields.next() orelse return, 10) catch return; + var start: Start = .{ .sp = sp, .argc = wordAt(d, sp) orelse return, .envc = 0, .auxc = 0 }; + const envp = sp + 8 * (start.argc + 2); + while (start.envc < 1 << 16 and (wordAt(d, envp + 8 * start.envc) orelse 0) != 0) start.envc += 1; + const auxv = envp + 8 * (start.envc + 1); + while (start.auxc < 256 and (wordAt(d, auxv + 16 * start.auxc) orelse 0) != 0) start.auxc += 1; + try d.emit(.{ .kind = .string, .a = .{ event.frameId(0), 0, 0, 0, 0, 0 } }, std.mem.asBytes(&start)); +} diff --git a/src/trace/Symbols.zig b/src/trace/Symbols.zig index abc0ec1..3ebd418 100644 --- a/src/trace/Symbols.zig +++ b/src/trace/Symbols.zig @@ -57,9 +57,52 @@ pub const Module = struct { /// Functions and objects by address in the file. symbols: []Symbol = &.{}, dwarf_tried: bool = false, - /// How many parameters each function takes, by its first address in - /// the file: read from DWARF on first use. - params: ?std.AutoHashMapUnmanaged(u64, u8) = null, + /// What DWARF says of each function, by its first address in the file: + /// read on first use (`readSubprograms`), its locals in `locals`. + subprograms: ?std.AutoHashMapUnmanaged(u64, Subprogram) = null, + locals: std.ArrayList(Local) = .empty, + /// The call frame information, .debug_frame then .eh_frame, either + /// missing: prepared on first use. + unwinds: [2]Dwarf.Unwind = undefined, + unwinds_len: u8 = 0, + unwinds_tried: bool = false, + /// Each function's rows of it, decoded on first use, by its first + /// address in the file. + cfi: std.AutoHashMapUnmanaged(u64, struct { len: u64, rows: []Row }) = .empty, + + /// The call frame information, prepared on first use. + fn unwindTables(m: *Module, gpa: std.mem.Allocator) []Dwarf.Unwind { + if (m.unwinds_tried) return m.unwinds[0..m.unwinds_len]; + m.unwinds_tried = true; + const file = &(m.file orelse return &.{}); + for ([_]?std.debug.ElfFile.UnwindSection{ file.debug_frame, file.eh_frame }, [_]Dwarf.Unwind.Section{ .debug_frame, .eh_frame }) |section, id| { + const s = section orelse continue; + var u: Dwarf.Unwind = .initSection(id, s.vaddr, s.bytes); + u.prepare(gpa, 8, .little, true, false) catch { + u.deinit(gpa); + continue; + }; + m.unwinds[m.unwinds_len] = u; + m.unwinds_len += 1; + } + return m.unwinds[0..m.unwinds_len]; + } + + /// The function whose call frame information holds `pc`, an address in + /// the file: where it begins (in the file) and its rows. + fn rowsAt(m: *Module, gpa: std.mem.Allocator, pc: u64) ?struct { start: u64, len: u64, rows: []const Row } { + for (m.unwindTables(gpa)) |*u| { + const at = (u.lookupPc(pc, 8, .little) catch null) orelse continue; + const cie, const fde = u.getFde(at, .little) catch continue; + if (pc < fde.pc_begin or pc - fde.pc_begin >= fde.pc_range) continue; + const entry = m.cfi.getOrPut(gpa, fde.pc_begin) catch return null; + // Rows that cannot be read are none: the walk falls back on the frame pointer. + if (!entry.found_existing) entry.value_ptr.* = .{ .len = fde.pc_range, .rows = decodeRows(gpa, cie, &fde) catch &.{} }; + if (entry.value_ptr.rows.len == 0) return null; + return .{ .start = fde.pc_begin, .len = entry.value_ptr.len, .rows = entry.value_ptr.rows }; + } + return null; + } /// The line tables, opened on first use. Null without debug info. fn dwarf(m: *Module, gpa: std.mem.Allocator) ?*Dwarf { @@ -105,7 +148,12 @@ fn line(table: *const Dwarf.CompileUnit.SrcLocCache, entry: Dwarf.CompileUnit.Sr pub fn deinit(s: *Symbols) void { for (s.modules.items) |*m| { if (m.file) |*f| f.deinit(s.gpa); - if (m.params) |*p| p.deinit(s.gpa); + if (m.subprograms) |*p| p.deinit(s.gpa); + m.locals.deinit(s.gpa); + for (m.unwinds[0..m.unwinds_len]) |*u| u.deinit(s.gpa); + var decoded = m.cfi.valueIterator(); + while (decoded.next()) |f| s.gpa.free(f.rows); + m.cfi.deinit(s.gpa); s.gpa.free(m.symbols); s.gpa.free(m.path); } @@ -368,20 +416,253 @@ pub fn lineAddress(s: *Symbols, file: []const u8, wanted: u32) ?u64 { /// where no function it describes begins. pub fn parameters(s: *Symbols, addr: u64) ?u8 { const m = s.moduleAt(addr) orelse return null; - const d = m.dwarf(s.gpa) orelse return null; - if (m.params == null) { - m.params = .empty; - countParameters(s.gpa, d, &m.params.?) catch {}; + const sub = (subprogramsOf(m, s.gpa) orelse return null).get(addr - m.bias) orelse return null; + return sub.params; +} + +// The stack: frames, and what their words are. + +/// A row of a function's call frame information: from `offset` bytes into +/// it up to the next row's, where its caller's stack pointer was before the +/// call (the CFA) and where the registers it saved for its caller are. +pub const Row = extern struct { + offset: u32 = 0, + /// The CFA is `cfa_reg` (DWARF's number: 7 rsp, 6 rbp) plus `cfa`; + /// `cfa_reg` is `no_cfa` where it is anything else (an expression, but + /// a PLT's: a signal frame), which a walk does not follow. + cfa: i32 = 0, + cfa_reg: u8 = no_cfa, + /// Where each of `saved_registers` is saved, in words from the CFA: 0 + /// where it is not (it holds the caller's value still; for the return + /// address: there is no caller), `lost` where it is saved some way a + /// walk does not follow. + saved: [saved_registers.len]i8 = @splat(0), +}; +pub const no_cfa: u8 = 0xff; +pub const lost: i8 = std.math.minInt(i8); +/// The registers a function saves for its caller (rbx, rbp, r12 to r15) and +/// the return address, by DWARF's numbers; `saved_names` names them. +pub const saved_registers = [_]u8{ 3, 6, 12, 13, 14, 15, 16 }; +pub const saved_names = [_][]const u8{ "rbx", "rbp", "r12", "r13", "r14", "r15", "rip" }; + +/// A local variable or parameter that lives on the stack, `offset` bytes +/// from its function's frame base, while the pc is `from` to `to` bytes +/// into its function (its block's; the whole function's for one outside a +/// block). `size` is 0 where its type's is not known. +pub const Local = struct { name: []const u8, offset: i32, size: u32, from: u32 = 0, to: u32 = std.math.maxInt(u32) }; + +/// What locals' offsets are from: the CFA, or (`Function.base`) a register. +pub const base_cfa: u8 = 0xfe; +pub const no_base: u8 = 0xff; + +/// A function's frame: how a walk goes through it, and where its locals are. +pub const Function = struct { + /// Where it begins, a target address, and how long it is. + start: u64, + len: u64, + /// Its call frame information, a row a stretch of its code, in order. + rows: []const Row, + /// What its locals' offsets are from: a register (DWARF's number), the + /// CFA (`base_cfa`), or nothing known (`no_base`). + base: u8 = no_base, + locals: []const Local = &.{}, + + /// The row in force at `addr`. + pub fn rowAt(f: Function, addr: u64) Row { + const after = std.sort.partitionPoint(Row, f.rows, addr - f.start, struct { + fn startsBefore(at: u64, row: Row) bool { + return row.offset <= at; + } + }.startsBefore); + return f.rows[after -| 1]; } - return m.params.?.get(addr - m.bias); +}; + +/// The row of call frame information in force at an address, and where its +/// function begins: what a walk of the call chain asks (`Debugger.walk`). +pub const Cfi = struct { function: u64, row: Row }; + +/// The function whose call frame information holds `addr`, with its locals +/// where DWARF describes it. Null without call frame information there. +pub fn functionAt(s: *Symbols, addr: u64) ?Function { + const m = s.moduleAt(addr) orelse return null; + const found = m.rowsAt(s.gpa, addr - m.bias) orelse return null; + var f: Function = .{ .start = found.start + m.bias, .len = found.len, .rows = found.rows }; + if (subprogramsOf(m, s.gpa)) |subs| if (subs.get(found.start)) |sub| { + f.base = sub.base; + f.locals = m.locals.items[sub.first..][0..sub.count]; + }; + return f; } -/// Each function's parameters, by its first address: the formal parameters -/// among the children of each subprogram with code, in .debug_info. The -/// units and their abbreviations are the ones `std.debug.Dwarf` read. -fn countParameters(gpa: std.mem.Allocator, d: *const Dwarf, out: *std.AutoHashMapUnmanaged(u64, u8)) !void { +pub fn cfi(s: *Symbols, addr: u64) ?Cfi { + const f = s.functionAt(addr) orelse return null; + return .{ .function = f.start, .row = f.rowAt(addr) }; +} + +/// Every row of an FDE: where each begins is where the instructions advance +/// to, and what it says is the machine's state there. +fn decodeRows(gpa: std.mem.Allocator, cie: *const Dwarf.Unwind.CommonInformationEntry, fde: *const Dwarf.Unwind.FrameDescriptionEntry) ![]Row { + const VM = Dwarf.Unwind.VirtualMachine; + var starts: std.ArrayList(u64) = .empty; + defer starts.deinit(gpa); + try starts.append(gpa, 0); + var r: std.Io.Reader = .fixed(fde.instructions); + var loc: u64 = 0; + while (r.seek < r.buffer.len) { + const moved = switch (try VM.Instruction.read(&r, 8, .little)) { + .advance_loc => |delta| moved: { + loc += @as(u64, delta) * cie.code_alignment_factor; + break :moved true; + }, + .set_loc => |to| moved: { + loc = to -% fde.pc_begin; + break :moved true; + }, + // An expression's bytes follow its instruction. + .register => |reg| moved: { + switch (reg.rule) { + .expr, .val_expr => |len| try r.discardAll(len), + else => {}, + } + break :moved false; + }, + .def_cfa_expr => |len| moved: { + try r.discardAll(len); + break :moved false; + }, + else => false, + }; + if (moved and loc < fde.pc_range and loc > starts.getLast()) try starts.append(gpa, loc); + } + var vm: VM = .{}; + defer vm.deinit(gpa); + var rows: std.ArrayList(Row) = .empty; + errdefer rows.deinit(gpa); + for (starts.items, 0..) |offset, n| { + vm.reset(); + const row = try vm.runTo(gpa, fde.pc_begin + offset, cie, fde, 8, .little); + var out: Row = .{ .offset = std.math.cast(u32, offset) orelse return error.InvalidDebugInfo }; + for (vm.rowColumns(&row)) |column| { + const i = std.mem.indexOfScalar(u8, &saved_registers, column.register) orelse continue; + out.saved[i] = switch (column.rule) { + .default, .same_value => 0, + // Undefined: for the return address, no caller; for another, no value. + .undefined => if (column.register == 16) 0 else lost, + .offset => |off| if (@rem(off, 8) == 0) std.math.cast(i8, @divExact(off, 8)) orelse lost else lost, + else => lost, + }; + } + switch (row.cfa) { + .reg_off => |ro| if (std.math.cast(i32, ro.offset)) |off| { + out.cfa_reg = ro.register; + out.cfa = off; + }, + // PLT entries, 16 bytes each: rsp + 8, and rsp + 16 from byte + // `k` on, after the entry's push. As rows, two an entry. + .expression => |expr| if (pltPush(expr)) |k| { + const from = fde.pc_begin + offset; + const to = fde.pc_begin + if (n + 1 < starts.items.len) starts.items[n + 1] else fde.pc_range; + var entry = from & ~@as(u64, 15); + while (entry < to) : (entry += 16) for ([_]u64{ entry, entry + k }, [_]i32{ 8, 16 }) |at, cfa| { + if (at + (if (cfa == 8) k else 16 - k) <= from or at >= to) continue; + out.offset = @intCast(@max(at, from) - fde.pc_begin); + out.cfa_reg = 7; + out.cfa = cfa; + try rows.append(gpa, out); + }; + continue; + }, + else => {}, + } + try rows.append(gpa, out); + } + return rows.toOwnedSlice(gpa); +} + +test "an FDE's rows, a PLT's expression among them as two rows an entry" { + const gpa = std.testing.allocator; + // As GNU ld writes them: the CIE's CFA rsp + 8 and return address at + // CFA - 8; the PLT's first 16 bytes push twice, then three entries. + var cie: Dwarf.Unwind.CommonInformationEntry = .{ + .version = 1, + .format = .@"32", + .addr_size_bytes = 8, + .segment_selector_size = 0, + .code_alignment_factor = 1, + .data_alignment_factor = -8, + .return_address_register = 16, + .fde_pointer_enc = .{ .type = .absptr, .rel = .abs }, + .is_signal_frame = false, + .augmentation_kind = .none, + .initial_instructions = &.{ 0x0c, 7, 8, 0x80 | 16, 1 }, + .last_row = null, + }; + try Dwarf.Unwind.VirtualMachine.populateCieLastRow(gpa, &cie, 8, .little); + defer gpa.free(cie.last_row.?.cols); + const OP = std.dwarf.OP; + const fde: Dwarf.Unwind.FrameDescriptionEntry = .{ .pc_begin = 0x401020, .pc_range = 0x40, .instructions = &.{ + 0x0e, 16, 0x40 | 6, 0x0e, 24, 0x40 | 10, + 0x0f, 11, OP.breg7, 8, OP.breg0 + 16, 0, OP.lit15, OP.@"and", OP.lit11, OP.ge, OP.lit3, OP.shl, OP.plus, + } }; + const rows = try decodeRows(gpa, &cie, &fde); + defer gpa.free(rows); + const want = [_][2]i32{ .{ 0, 16 }, .{ 6, 24 }, .{ 0x10, 8 }, .{ 0x1b, 16 }, .{ 0x20, 8 }, .{ 0x2b, 16 }, .{ 0x30, 8 }, .{ 0x3b, 16 } }; + try std.testing.expectEqual(want.len, rows.len); + for (want, rows) |w, row| { + try std.testing.expectEqual(@as(u32, @intCast(w[0])), row.offset); + try std.testing.expectEqual(w[1], row.cfa); + try std.testing.expectEqual(@as(u8, 7), row.cfa_reg); + try std.testing.expectEqual([7]i8{ 0, 0, 0, 0, 0, 0, -1 }, row.saved); + } +} + +/// The CFA of a PLT as GNU ld describes it: `rsp + 8 + 8 * ((rip & 15) >= +/// k)`. Returns k. +fn pltPush(expr: []const u8) ?u8 { + const OP = std.dwarf.OP; + if (expr.len != 11 or expr[6] < OP.lit0 or expr[6] > OP.lit31) return null; + const pattern = [_]u8{ OP.breg7, 8, OP.breg0 + 16, 0, OP.lit15, OP.@"and", 0, OP.ge, OP.lit3, OP.shl, OP.plus }; + for (expr, pattern, 0..) |have, want, i| if (i != 6 and have != want) return null; + return expr[6] - OP.lit0; +} + +/// What DWARF says of a function with code (`readSubprograms`). +const Subprogram = struct { + params: u8 = 0, + base: u8 = no_base, + /// Its locals, in the module's `locals`. + first: usize = 0, + count: usize = 0, +}; + +fn subprogramsOf(m: *Module, gpa: std.mem.Allocator) ?*const std.AutoHashMapUnmanaged(u64, Subprogram) { + if (m.subprograms == null) { + const d = m.dwarf(gpa) orelse return null; + m.subprograms = .empty; + readSubprograms(gpa, d, &m.subprograms.?, &m.locals) catch {}; + } + return &m.subprograms.?; +} + +/// Each function with code, by its first address, in .debug_info: the +/// formal parameters among its children, its frame base, and its locals at +/// any depth whose place is `DW_OP_fbreg` alone (-O0 and -Og code; a place +/// that is a register or a list of places is left out, not guessed), each +/// sized by its type and kept with its block's range of code: blocks may +/// share a slot. The units and their abbreviations are the ones +/// `std.debug.Dwarf` read. +// shortcut: a block whose code is in pieces (`DW_AT_ranges`) has its locals left out, upgrade by reading .debug_rnglists when an -O2 program needs them. +fn readSubprograms(gpa: std.mem.Allocator, d: *const Dwarf, out: *std.AutoHashMapUnmanaged(u64, Subprogram), locals: *std.ArrayList(Local)) !void { const info = d.section(.debug_info) orelse return; const DW = std.dwarf; + // A unit's types by where they are in .debug_info: a size, or the type + // it is a qualified, renamed or repeated (`count` times) form of. + var types: std.AutoHashMapUnmanaged(u64, struct { size: ?u64 = null, of: u64 = 0, count: u64 = 1 }) = .empty; + defer types.deinit(gpa); + // The type of each local of the unit, to size at its end. + var typed: std.ArrayList(u64) = .empty; + defer typed.deinit(gpa); for (d.compile_unit_list.items) |*cu| { const table = for (d.abbrev_table_list.items) |*t| { if (t.offset == cu.abbrev_offset) break t; @@ -391,10 +672,20 @@ fn countParameters(gpa: std.mem.Allocator, d: *const Dwarf, out: *std.AutoHashMa // Past the unit's header: its length, version, (DWARF 5) unit type, // the abbreviations' offset and the address size. r.seek = @intCast(cu.offset + (if (offset == 8) @as(u64, 12) else 4) + 2 + offset + 1 + @intFromBool(cu.version >= 5)); + types.clearRetainingCapacity(); + typed.clearRetainingCapacity(); + const first = locals.items.len; var depth: usize = 0; - // The function whose parameters are being counted, and how deep it is. + // The function being read, and how deep it is; the array type whose + // dimensions are being read. var function: ?struct { pc: u64, depth: usize } = null; + var array: ?struct { at: u64, depth: usize } = null; + // The blocks the walk is inside, in the function, innermost last: + // the range of its code, from its start; null where it is not one range. + var blocks: std.ArrayList(struct { depth: usize, range: ?[2]u32 }) = .empty; + defer blocks.deinit(gpa); while (r.seek < r.buffer.len) { + const at: u64 = r.seek; const code = try r.takeLeb128(u64); if (code == 0) { depth -|= 1; @@ -405,33 +696,176 @@ fn countParameters(gpa: std.mem.Allocator, d: *const Dwarf, out: *std.AutoHashMa if (a.code == code) break a; } else return error.InvalidDebugInfo; var low_pc: ?u64 = null; + var high_pc: ?u64 = null; + var high_is_size = false; + var ranges = false; + var name: ?[]const u8 = null; + var location: ?[]const u8 = null; + var frame_base: ?[]const u8 = null; + var type_at: ?u64 = null; + var size: ?u64 = null; + var count: ?u64 = null; for (abbrev.attrs) |attr| { - const v = try formValue(&r, attr.form_id, cu); - if (attr.id == DW.AT.low_pc) low_pc = switch (attr.form_id) { - DW.FORM.addr => v, - DW.FORM.addrx, DW.FORM.addrx1, DW.FORM.addrx2, DW.FORM.addrx3, DW.FORM.addrx4, DW.FORM.GNU_addr_index => debugAddr(d, cu, v), - else => null, - }; + const from = r.seek; + const form = attr.form_id; + const v = if (form == DW.FORM.implicit_const) @as(u64, @bitCast(attr.payload)) else try formValue(&r, form, cu); + const raw = r.buffer[from..r.seek]; + switch (attr.id) { + DW.AT.low_pc => low_pc = switch (form) { + DW.FORM.addr => v, + DW.FORM.addrx, DW.FORM.addrx1, DW.FORM.addrx2, DW.FORM.addrx3, DW.FORM.addrx4, DW.FORM.GNU_addr_index => debugAddr(d, cu, v), + else => null, + }, + DW.AT.high_pc => { + high_pc = v; + high_is_size = constant(form); + }, + DW.AT.ranges => ranges = true, + DW.AT.name => name = attrString(d, cu, form, v, raw), + DW.AT.location => location = block(form, raw), + DW.AT.frame_base => frame_base = block(form, raw), + DW.AT.type => type_at = switch (form) { + DW.FORM.ref1, DW.FORM.ref2, DW.FORM.ref4, DW.FORM.ref8, DW.FORM.ref_udata => cu.offset + v, + DW.FORM.ref_addr => v, + else => null, + }, + DW.AT.byte_size, DW.AT.count, DW.AT.upper_bound => if (constant(form)) { + if (attr.id == DW.AT.byte_size) size = v else if (attr.id == DW.AT.count) { + count = v; + } else if (count == null) count = v +% 1; + }, + else => {}, + } } const here = depth; if (abbrev.has_children) depth += 1; if (function) |f| if (here <= f.depth) { function = null; }; + if (array) |a| if (here <= a.depth) { + array = null; + }; + while (blocks.items.len > 0 and here <= blocks.getLast().depth) _ = blocks.pop(); switch (abbrev.tag_id) { DW.TAG.subprogram => if (low_pc) |pc| { - try out.put(gpa, pc, 0); + try out.put(gpa, pc, .{ .base = frameBase(frame_base), .first = locals.items.len }); if (abbrev.has_children) function = .{ .pc = pc, .depth = here }; + blocks.clearRetainingCapacity(); + }, + DW.TAG.lexical_block => if (function) |f| if (abbrev.has_children) { + const range: ?[2]u32 = range: { + const lo = low_pc orelse break :range null; + const hi = if (high_is_size) lo +% (high_pc orelse break :range null) else high_pc orelse break :range null; + if (ranges or lo < f.pc or hi < lo) break :range null; + break :range .{ std.math.cast(u32, lo - f.pc) orelse break :range null, std.math.cast(u32, hi - f.pc) orelse break :range null }; + }; + try blocks.append(gpa, .{ .depth = here, .range = range }); }, - DW.TAG.formal_parameter => if (function) |f| if (here == f.depth + 1) { - out.getPtr(f.pc).?.* +|= 1; + DW.TAG.formal_parameter, DW.TAG.variable => if (function) |f| { + const sub = out.getPtr(f.pc).?; + if (abbrev.tag_id == DW.TAG.formal_parameter and here == f.depth + 1) sub.params +|= 1; + const scope: ?[2]u32 = if (blocks.items.len > 0) blocks.getLast().range else .{ 0, std.math.maxInt(u32) }; + if (name) |n| if (fbreg(location)) |off| if (scope) |range| { + try locals.append(gpa, .{ .name = n, .offset = off, .size = 0, .from = range[0], .to = range[1] }); + try typed.append(gpa, type_at orelse 0); + sub.count += 1; + }; + }, + DW.TAG.base_type, DW.TAG.structure_type, DW.TAG.union_type, DW.TAG.class_type, DW.TAG.enumeration_type => if (size) |n| try types.put(gpa, at, .{ .size = n }), + DW.TAG.pointer_type, DW.TAG.reference_type, DW.TAG.rvalue_reference_type, DW.TAG.ptr_to_member_type => try types.put(gpa, at, .{ .size = size orelse cu.addr_size_bytes }), + DW.TAG.typedef, DW.TAG.const_type, DW.TAG.volatile_type, DW.TAG.restrict_type, DW.TAG.atomic_type => if (type_at) |t| try types.put(gpa, at, .{ .of = t }), + DW.TAG.array_type => { + try types.put(gpa, at, if (size) |n| .{ .size = n } else .{ .of = type_at orelse 0 }); + if (abbrev.has_children and size == null) array = .{ .at = at, .depth = here }; + }, + DW.TAG.subrange_type => if (array) |a| if (here == a.depth + 1) { + types.getPtr(a.at).?.count *%= count orelse 0; }, else => {}, } } + // A type that never reaches a size (void, a declaration) is size 0. + for (locals.items[first..], typed.items) |*local, t| { + var n: u64 = 1; + var next = t; + local.size = for (0..16) |_| { + const ty = types.get(next) orelse break 0; + if (ty.size) |bytes| break std.math.cast(u32, n *% bytes) orelse 0; + n *%= ty.count; + next = ty.of; + } else 0; + } } } +/// The bytes of an attribute that is a block (an expression), from its raw +/// form; null for any other form. +fn block(form: u64, raw: []const u8) ?[]const u8 { + const F = std.dwarf.FORM; + var r: std.Io.Reader = .fixed(raw); + const len: usize = switch (form) { + F.exprloc, F.block => r.takeLeb128(usize) catch return null, + F.block1 => r.takeByte() catch return null, + F.block2 => r.takeInt(u16, .little) catch return null, + F.block4 => r.takeInt(u32, .little) catch return null, + else => return null, + }; + return if (r.seek + len == raw.len) raw[r.seek..] else null; +} + +fn constant(form: u64) bool { + const F = std.dwarf.FORM; + return switch (form) { + F.data1, F.data2, F.data4, F.data8, F.udata, F.sdata, F.implicit_const => true, + else => false, + }; +} + +/// `DW_OP_fbreg N` and nothing else: N. +fn fbreg(location: ?[]const u8) ?i32 { + const expr = location orelse return null; + if (expr.len < 2 or expr[0] != std.dwarf.OP.fbreg) return null; + var r: std.Io.Reader = .fixed(expr[1..]); + const off = r.takeLeb128(i64) catch return null; + return if (r.seek == r.buffer.len) std.math.cast(i32, off) else null; +} + +/// A frame base that is the CFA or a register: `base_cfa` or the register's number. +fn frameBase(expr: ?[]const u8) u8 { + const e = expr orelse return no_base; + if (e.len != 1) return no_base; + if (e[0] == std.dwarf.OP.call_frame_cfa) return base_cfa; + if (e[0] >= std.dwarf.OP.reg0 and e[0] <= std.dwarf.OP.reg0 + 16) return e[0] - std.dwarf.OP.reg0; + return no_base; +} + +/// A string attribute's text: in the entry itself, or in .debug_str or +/// .debug_line_str by offset or (DWARF 5) by index. Null for other forms. +fn attrString(d: *const Dwarf, cu: *const Dwarf.CompileUnit, form: u64, v: u64, raw: []const u8) ?[]const u8 { + const F = std.dwarf.FORM; + const off: u64 = switch (form) { + F.string => return raw[0 .. raw.len - 1], + F.strp => v, + F.line_strp => return stringAt(d.section(.debug_line_str), v), + F.strx, F.strx1, F.strx2, F.strx3, F.strx4, F.GNU_str_index => off: { + const offsets = d.section(.debug_str_offsets) orelse return null; + const wide = cu.format == .@"64"; + const width: u64 = if (wide) 8 else 4; + const at = cu.str_offsets_base + v * width; + if (at + width > offsets.len) return null; + break :off if (wide) std.mem.readInt(u64, offsets[@intCast(at)..][0..8], .little) else std.mem.readInt(u32, offsets[@intCast(at)..][0..4], .little); + }, + else => return null, + }; + return stringAt(d.section(.debug_str), off); +} + +fn stringAt(section: ?[]const u8, off: u64) ?[]const u8 { + const s = section orelse return null; + if (off >= s.len) return null; + return std.mem.sliceTo(s[@intCast(off)..], 0); +} + /// The address at `index` of a unit's part of .debug_addr. fn debugAddr(d: *const Dwarf, cu: *const Dwarf.CompileUnit, index: u64) ?u64 { const table = d.section(.debug_addr) orelse return null; diff --git a/src/trace/debugger_test.zig b/src/trace/debugger_test.zig index 5d43d8c..e20f864 100644 --- a/src/trace/debugger_test.zig +++ b/src/trace/debugger_test.zig @@ -173,6 +173,152 @@ test "step walks the source lines, in and out of calls, as gdb does" { try std.testing.expectEqualStrings("main", d2.syms.symbolAt(chain[1]).?.name); } +/// The target's memory with no call frame information: what the call chain +/// is walked by without it, the frame pointer alone. +const FramePointer = struct { + d: *Debugger, + pub fn read(mem: FramePointer, addr: u64, buf: []u8) usize { + return mem.d.read(addr, buf); + } +}; + +fn named(d: *Debugger, pc: u64) []const u8 { + return if (d.syms.symbolAt(pc)) |sym| sym.name else ""; +} + +test "the call chain by the unwind tables: through a frameless wrapper, at a function's first instruction" { + var d = try spawn(targets.fib, "5", null); + defer d.deinit(); + // A brk from malloc, inside libc: its wrapper keeps no frame, so the + // frame pointer's walk passes over its caller. gdb shows the same chain. + d.syscalls = .stop; + var by_cfi: [32]u64 = undefined; + var by_fp: [32]u64 = undefined; + const cfi, const fp = find: while (true) switch (try d.cont()) { + .syscall_enter => |nr| if (nr == @backingInt(linux.SYS.brk)) { + const chain = Debugger.backtrace(&d, &d.regs, false, &by_cfi); + for (chain) |pc| if (std.mem.eql(u8, named(&d, pc), "main")) break :find .{ chain, Debugger.backtrace(FramePointer{ .d = &d }, &d.regs, false, &by_fp) }; + }, + .exited => return error.NoBrkFromMain, + else => {}, + }; + try std.testing.expect(cfi.len > fp.len); + // Every frame the frame pointer finds is found, in order, and the walks end alike. + var at: usize = 0; + for (fp) |pc| { + at = (std.mem.indexOfScalarPos(u64, cfi, at, pc) orelse return error.FrameLost) + 1; + } + try std.testing.expectEqual(fp[fp.len - 1], cfi[cfi.len - 1]); + d.syscalls = .ignore; + + // At fib's first instruction its caller is main's frame still, which + // the frame pointer's walk, not told so, passes over. + var d2 = try spawn(targets.fib, "5", null); + defer d2.deinit(); + _ = try d2.breakAt(d2.symbol("fib").?.addr, null); + _ = try d2.cont(); + try std.testing.expectEqualStrings("main", named(&d2, Debugger.backtrace(&d2, &d2.regs, false, &by_cfi)[1])); + try std.testing.expect(!std.mem.eql(u8, "main", named(&d2, Debugger.backtrace(FramePointer{ .d = &d2 }, &d2.regs, false, &by_fp)[1]))); +} + +test "a recording tells each stack word's role: saved registers, return addresses, locals, the process's start" { + 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, "roles.ztrace" }); + defer gpa.free(path); + + var rec = try zt.Recorder.create(gpa, io, path); + { + errdefer rec.close() catch {}; + var d = try spawn(targets.list_O0, "2", rec.sink()); + defer d.deinit(); + // DWARF's locals: at -O0 each parameter and variable has a place by the frame base. + const push = d.syms.functionAt(d.symbol("push").?.addr).?; + try std.testing.expectEqual(@as(u8, 6), push.base); + try std.testing.expectEqual(@as(usize, 3), push.locals.len); + for (push.locals, [_][]const u8{ "head", "value", "n" }) |local, name| { + try std.testing.expectEqualStrings(name, local.name); + try std.testing.expectEqual(@as(u32, 8), local.size); + try std.testing.expect(local.offset < 0); + } + // main's i is its loop's, a block within it. + for (d.syms.functionAt(d.symbol("main").?.addr).?.locals) |local| { + if (std.mem.eql(u8, local.name, "i")) try std.testing.expect(local.from > 0 and local.to < 0x1000); + } + d.telescope = 1; + d.stack_watch = 4096; + // In push's body: its frame made, its locals above the stack pointer. + _ = try d.breakAt(try d.resolve("list.c:13"), null); + _ = try d.cont(); + try std.testing.expectEqual(@as(u8, 0), try finish(&d)); + } + try rec.close(); + + var trace = try zt.Trace.open(gpa, io, path); + defer trace.close(); + const m = find: for (0..trace.len) |i| { + const m = try trace.moment(i); + var events = try m.events(gpa); + defer events.deinit(gpa); + while (events.next()) |item| if (item.ev.kind == .breakpoint) break :find m; + } else return error.NoBreakpoint; + const tids = try m.threads(gpa); + defer gpa.free(tids); + const regs = (try m.regs(tids[0])).?; + var found: [8]Debugger.Frame = undefined; + const chain = try zt.telescope.frames(m, ®s, &found); + try std.testing.expect(chain.len >= 3); + const Slot = zt.telescope.Slot; + var buf: [512]Slot = undefined; + const words = try zt.telescope.slots(m, ®s, regs.rsp, &buf); + + // push's frame: its locals, rbp saved under the return address. + var seen: [3]bool = @splat(false); + for (words, 0..) |w, i| { + const addr = regs.rsp + 8 * i; + if (addr >= chain[0].high) break; + try std.testing.expectEqual(@as(?u8, 0), w.frame); + if (w.role == .local) for ([_][]const u8{ "head", "value", "n" }, &seen) |name, *s| { + if (std.mem.eql(u8, w.role.local.name, name)) s.* = true; + }; + } + try std.testing.expectEqual([3]bool{ true, true, true }, seen); + const at = struct { + fn word(all: []const Slot, rsp: u64, addr: u64) Slot { + return all[(addr - rsp) / 8]; + } + }.word; + try std.testing.expectEqual(zt.telescope.Role.return_address, at(words, regs.rsp, chain[0].high - 8).role); + try std.testing.expectEqualStrings("rbp", at(words, regs.rsp, chain[0].high - 16).role.saved); + // main's frame, next: its own locals, and its return address into libc. + try std.testing.expectEqual(@as(?u8, 1), at(words, regs.rsp, chain[1].low).frame); + try std.testing.expectEqual(zt.telescope.Role.return_address, at(words, regs.rsp, chain[1].high - 8).role); + // The call is in the loop: its i is named too. + var in_main: [2]bool = @splat(false); + for (words[(chain[1].low - regs.rsp) / 8 .. (chain[1].high - regs.rsp) / 8]) |w| { + if (w.role == .local) for ([_][]const u8{ "head", "i" }, &in_main) |name, *seen_it| { + if (std.mem.eql(u8, w.role.local.name, name)) seen_it.* = true; + }; + } + try std.testing.expectEqual([2]bool{ true, true }, in_main); + + // The process's first stack: argc 2, ./list-O0 and "2", no environment, then the auxiliary vector. + var start_at: ?usize = null; + for (words, 0..) |w, i| if (w.role == .argc) { + start_at = i; + break; + }; + const s = words[start_at orelse return error.NoArgc ..]; + for ([_]zt.telescope.Role{ .argc, .{ .argv = 0 }, .{ .argv = 1 }, .{ .argv = 2 }, .{ .envp = 0 }, .{ .auxv = 0 }, .{ .auxv = 1 } }, s[0..7]) |want, have| { + try std.testing.expectEqual(want, have.role); + } + var argc: [8]u8 = undefined; + try m.read(regs.rsp + 8 * start_at.?, &argc, null); + try std.testing.expectEqual(@as(u64, 2), std.mem.readInt(u64, &argc, .little)); +} + test "the telescope records the region round what a pointer leads to" { var log: Log = .{}; defer log.deinit(); @@ -307,10 +453,10 @@ test "a watch sends a word when it changes, and each moment keeps the region as } try std.testing.expectEqual(@as(usize, 9), writes); try std.testing.expect(log.count(.step) > 100); - // Lines come from one file here, defined once. + // Lines come from one file here, defined once; the one other string is where the stack began. try std.testing.expect(log.count(.line) > 100); for (log.events.items) |e| { - if (e.ev.kind == .string) try std.testing.expect(std.mem.endsWith(u8, e.payload, ".zig")); + if (e.ev.kind == .string and e.ev.a[0] != zt.event.frameId(0)) try std.testing.expect(std.mem.endsWith(u8, e.payload, ".zig")); } var trace = try zt.Trace.open(gpa, io, path); diff --git a/src/trace/event.zig b/src/trace/event.zig index dcd4aa9..02deb51 100644 --- a/src/trace/event.zig +++ b/src/trace/event.zig @@ -187,6 +187,17 @@ pub fn codeId(addr: u64) u64 { return addr | 1 << 62; } +/// The id of the string that describes the frame of the function that +/// begins at `addr`: how to walk through it to its caller (its call frame +/// information) and where its locals are (`Debugger.emitFunction`). A +/// reader finds the one that holds a pc as the greatest id at or below the +/// pc's (`Trace.stringBelow`). `frameId(0)`, where no function begins, is +/// the process's first stack (`Debugger.Start`). Bit 61 keeps these apart +/// from names, instructions and hashed ids. +pub fn frameId(addr: u64) u64 { + return addr | 1 << 61; +} + pub fn now() u64 { var ts: std.os.linux.timespec = undefined; _ = std.os.linux.clock_gettime(.MONOTONIC, &ts); diff --git a/src/trace/store.zig b/src/trace/store.zig index 0b7e8fe..e4546c2 100644 --- a/src/trace/store.zig +++ b/src/trace/store.zig @@ -566,6 +566,8 @@ pub const Trace = struct { key_moments: []u64, /// Every string the recording defines, by id. strings: std.AutoHashMapUnmanaged(u64, []const u8) = .empty, + /// Their ids, in order: for `stringBelow`. + ids: []u64 = &.{}, strings_arena: std.heap.ArenaAllocator, cache: *Cache, @@ -618,6 +620,10 @@ pub const Trace = struct { } } } + t.ids = try t.strings_arena.allocator().alloc(u64, t.strings.count()); + var ids = t.strings.keyIterator(); + for (t.ids) |*id| id.* = ids.next().?.*; + std.mem.sortUnstable(u64, t.ids, {}, std.sort.asc(u64)); const root = try Map.init(db.rootCursor().readOnly()); if (try root.getCursor(key(.moments))) |cursor| t.len = try (try List.init(cursor)).count(); var key_moments: std.ArrayList(u64) = .empty; @@ -634,6 +640,20 @@ pub const Trace = struct { return t; } + /// The string with the greatest id at or below `id`, and that id: where + /// strings are keyed by where a range of addresses begins + /// (`event.frameId`), the one whose range may hold `id`. + pub fn stringBelow(t: *const Trace, id: u64) ?struct { id: u64, text: []const u8 } { + const after = std.sort.upperBound(u64, t.ids, id, struct { + fn order(want: u64, have: u64) std.math.Order { + return std.math.order(want, have); + } + }.order); + if (after == 0) return null; + const found = t.ids[after - 1]; + return .{ .id = found, .text = t.strings.get(found).? }; + } + fn root0(db: *ReadDB) Map { // An empty file has no root map yet: a map that holds nothing. return Map.init(db.rootCursor().readOnly()) catch unreachable; diff --git a/src/trace/telescope.zig b/src/trace/telescope.zig index 7e3e3e0..61736fd 100644 --- a/src/trace/telescope.zig +++ b/src/trace/telescope.zig @@ -7,6 +7,7 @@ const event = @import("event.zig"); const store = @import("store.zig"); const Moment = store.Moment; const Debugger = @import("Debugger.zig"); +const Symbols = @import("Symbols.zig"); /// The kind of memory an address is in, from its mapping. pub const Region = enum { @@ -108,9 +109,11 @@ pub fn instruction(m: Moment, addr: u64, buf: []u8) !?struct { len: u8, back: u8 return .{ .len = s[0], .back = s[1], .text = text, .line = if (line.line != 0) line else null, .params = if (params != 0) params - 1 else null }; } -/// The call chain of a thread at a moment, by frame pointer, from what the -/// recording holds of its stack: the pc, then each return address outwards. -/// It ends where the frames were not recorded. +/// The call chain of a thread at a moment, from what the recording holds of +/// its stack: the pc, then each return address outwards. Each frame is +/// walked through by its function's call frame information where the +/// debugger recorded it (`Debugger.emitFunction`), else by frame pointer +/// (`Debugger.backtrace`). It ends where the frames were not recorded. pub fn backtrace(m: Moment, regs: *const event.Regs, out: []u64) ![]u64 { return Debugger.backtrace(Memory{ .m = m }, regs, try atEntry(m, regs), out); } @@ -121,7 +124,122 @@ pub fn frames(m: Moment, regs: *const event.Regs, out: []Debugger.Frame) ![]Debu return Debugger.frames(Memory{ .m = m }, regs, try atEntry(m, regs), out); } -/// A moment's memory as the frame walk reads it: all of it recorded, or none. +/// What a word of the stack is, where the recording says. +pub const Role = union(enum) { + none, + /// A register its frame's function saved for its caller: "rbx", + /// "rbp", "r12" to "r15". + saved: []const u8, + /// Where its frame's function returns to. + return_address, + /// A local variable or parameter of its frame's function that the debug + /// info places on the stack: its name (the recording's, good while it + /// is open), its size (0: not known), and where the word is in it: 0 at + /// its first byte, 8 a word on, negative where it begins inside the word. + local: struct { name: []const u8, size: u32, offset: i32 }, + /// The process's first stack (`Debugger.Start`): argc; argv[i], the + /// zero that ends them at i = argc; envp[i] likewise, at i = envc; the + /// auxiliary vector's i-th word, two an entry (its type, its value), + /// the zero entry last. + argc, + argv: u32, + envp: u32, + auxv: u32, +}; + +/// A word of the stack: what it is, and the frame of `frames` it lies in +/// (0 the newest; null in none: under the stack pointer, or above the +/// outermost frame, where the process's first stack is). A leaf's locals +/// under the stack pointer (the red zone, at -O0) are its frame's. +pub const Slot = struct { role: Role = .none, frame: ?u8 = null }; + +/// What each word of a thread's stack from `low` (rounded down to a word) +/// is at this moment: `out[i]` is the word at `low + 8 i`. The frames are +/// `frames`'s; what tells their words is the call frame information (the +/// registers each function saved, where; its return address), or the +/// frame pointer (rbp saved under the return address); the debug info (a +/// local's place at -O0 and -Og, while the frame's pc is in its block: +/// none at all where it is in a register or a list of places, nor in a +/// block whose code is in pieces, nor in a prologue or an epilogue where +/// the frame base is a register the CFA is not yet or no longer kept in); +/// and the process's first stack pointer. +pub fn slots(m: Moment, regs: *const event.Regs, low: u64, out: []Slot) ![]Slot { + @memset(out, .{}); + const base = low & ~@as(u64, 7); + const end = base + 8 * out.len; + const in = struct { + fn at(slots_: []Slot, from: u64, addr: u64) ?*Slot { + if (addr < from or (addr - from) / 8 >= slots_.len) return null; + return &slots_[(addr - from) / 8]; + } + }.at; + var found: [64]Debugger.Unwound = undefined; + for (Debugger.unwind(Memory{ .m = m }, regs, try atEntry(m, regs), &found), 0..) |u, k| { + const f = u.frame; + var a = @max(f.low & ~@as(u64, 7), base); + while (a < @min(f.high, end)) : (a += 8) in(out, base, a).?.frame = @intCast(k); + const row = u.row orelse { + // By frame pointer: rbp saved under the return address; at a + // function's entry, the return address alone. + if (f.high == f.low + 8) if (in(out, base, f.low)) |s| { + s.role = .return_address; + }; + if (f.high >= f.low + 16) { + if (in(out, base, f.high - 16)) |s| s.role = .{ .saved = "rbp" }; + if (in(out, base, f.high - 8)) |s| s.role = .return_address; + } + continue; + }; + const cfa = f.high; + if (function(m, u.function)) |func| { + // The frame base is the CFA, or the register the CFA is from. + const frame_base: ?u64 = if (func.base == Symbols.base_cfa) cfa else if (func.base == row.cfa_reg) cfa -% @as(u64, @bitCast(@as(i64, row.cfa))) else null; + var locals = func.locals; + // Where the frame is in its function: a caller is in its call. + const here = (if (k == 0) f.pc else f.pc -% 1) -% u.function; + if (frame_base) |fb| while (locals.len >= 17) { + const offset = std.mem.readInt(i32, locals[0..4], .little); + const size = std.mem.readInt(u32, locals[4..8], .little); + const from = std.mem.readInt(u32, locals[8..12], .little); + const to = std.mem.readInt(u32, locals[12..16], .little); + const name = std.mem.sliceTo(locals[16..], 0); + locals = locals[@min(locals.len, 16 + name.len + 1)..]; + // Blocks share slots: a local is its slot's in its block only. + if (here < from or here >= to) continue; + const at = fb +% @as(u64, @bitCast(@as(i64, offset))); + var w = @max(at & ~@as(u64, 7), base); + while (w < @min(at +% @max(size, 1), end)) : (w += 8) { + const s = in(out, base, w) orelse continue; + // Two small locals in one word: the first named keeps it. + if (s.role == .none) s.role = .{ .local = .{ .name = name, .size = size, .offset = @intCast(@as(i64, @bitCast(w -% at))) } }; + // A leaf's locals under the stack pointer (the red zone) are its frame's too. + if (s.frame == null) s.frame = @intCast(k); + } + }; + } + for (row.saved, 0..) |at, i| { + if (at == 0 or at == Symbols.lost) continue; + const s = in(out, base, cfa +% @as(u64, @bitCast(@as(i64, at) * 8))) orelse continue; + s.role = if (i == 6) .return_address else .{ .saved = Symbols.saved_names[i] }; + } + } + const text = m.trace.strings.get(event.frameId(0)) orelse return out; + if (text.len != @sizeOf(Debugger.Start)) return out; + const start = std.mem.bytesToValue(Debugger.Start, text[0..@sizeOf(Debugger.Start)]); + for (out, 0..) |*s, i| { + const a = base + 8 * i; + if (a < start.sp) continue; + // In words from argc: argv, its zero, envp, its zero, the auxiliary vector. + const w = (a - start.sp) / 8; + const envp = start.argc + 2; + const auxv = envp + start.envc + 1; + s.role = if (w == 0) .argc else if (w < envp) .{ .argv = @intCast(w - 1) } else if (w < auxv) .{ .envp = @intCast(w - envp) } else if (w < auxv + 2 * (start.auxc + 1)) .{ .auxv = @intCast(w - auxv) } else continue; + } + return out; +} + +/// A moment's memory as the frame walk reads it: all of it recorded, or +/// none; and the call frame information the debugger recorded. const Memory = struct { m: Moment, pub fn read(mem: @This(), addr: u64, buf: []u8) usize { @@ -129,8 +247,47 @@ const Memory = struct { mem.m.read(addr, buf, known[0..buf.len]) catch return 0; return if (std.mem.indexOfScalar(bool, known[0..buf.len], false) == null) buf.len else 0; } + + pub fn cfi(mem: @This(), pc: u64) ?Symbols.Cfi { + const f = function(mem.m, pc) orelse return null; + return .{ .function = f.start, .row = f.rowAt(pc) }; + } +}; + +/// A function's frame as the recording has it (`Debugger.emitFunction`): +/// its rows and its locals, each end to end. +const Function = struct { + start: u64, + base: u8, + rows: []const u8, + locals: []const u8, + + fn rowAt(f: Function, pc: u64) Symbols.Row { + const size = @sizeOf(Symbols.Row); + // The last row that begins at or before the pc. + var lo: usize = 0; + var hi = f.rows.len / size; + while (lo < hi) { + const mid = (lo + hi) / 2; + if (std.mem.readInt(u32, f.rows[mid * size ..][0..4], .little) <= pc - f.start) lo = mid + 1 else hi = mid; + } + return std.mem.bytesToValue(Symbols.Row, f.rows[(lo -| 1) * size ..][0..size]); + } }; +/// The recorded frame of the function that holds `pc`. +fn function(m: Moment, pc: u64) ?Function { + const found = m.trace.stringBelow(event.frameId(pc)) orelse return null; + // Below every function recorded is another kind of string, or the process's start. + if (found.id < event.frameId(1)) return null; + const t = found.text; + if (t.len < 7) return null; + const start = found.id - event.frameId(0); + const rows = @as(usize, std.mem.readInt(u16, t[5..7], .little)) * @sizeOf(Symbols.Row); + if (pc - start >= std.mem.readInt(u32, t[0..4], .little) or rows == 0 or t.len < 7 + rows) return null; + return .{ .start = start, .base = t[4], .rows = t[7..][0..rows], .locals = t[7 + rows ..] }; +} + /// At a function's first instruction its frame is not made yet: the /// return address is on top of the stack. fn atEntry(m: Moment, regs: *const event.Regs) !bool { @@ -257,3 +414,101 @@ test "an instruction's line and its callee's parameters; each frame's extent on .{ .pc = 0x400205, .low = 0x7ff108, .high = 0x7ff130 }, }, (try frames(m, ®s, &out))[0..2]); } + +test "frames walked by their call frame information; each stack word's role" { + 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); + // Two functions as `Debugger.emitFunction` records them. g, at 400100, + // keeps no frame and pushes rbx; f, at 400000, keeps one in rbp and has + // three locals by it: x, and buf and y in two blocks, sharing a slot. + const Row = Symbols.Row; + const record = struct { + fn at(r: *store.Recorder, start: u64, len: u32, base: u8, rows: []const Row, locals: []const u8) !void { + var text: std.Io.Writer.Allocating = .init(std.testing.allocator); + defer text.deinit(); + try text.writer.writeInt(u32, len, .little); + try text.writer.writeByte(base); + try text.writer.writeInt(u16, @intCast(rows.len), .little); + try text.writer.writeAll(std.mem.sliceAsBytes(rows)); + try text.writer.writeAll(locals); + try r.emit(.{ .kind = .string, .a = .{ event.frameId(start), 0, 0, 0, 0, 0 } }, text.written()); + } + }.at; + try record(&rec, 0x400100, 0x20, Symbols.no_base, &.{ + .{ .offset = 0, .cfa = 8, .cfa_reg = 7, .saved = .{ 0, 0, 0, 0, 0, 0, -1 } }, + .{ .offset = 1, .cfa = 16, .cfa_reg = 7, .saved = .{ -2, 0, 0, 0, 0, 0, -1 } }, + }, ""); + try record(&rec, 0x400000, 0x100, 6, &.{ + .{ .offset = 0, .cfa = 8, .cfa_reg = 7, .saved = .{ 0, 0, 0, 0, 0, 0, -1 } }, + .{ .offset = 1, .cfa = 16, .cfa_reg = 7, .saved = .{ 0, -2, 0, 0, 0, 0, -1 } }, + .{ .offset = 4, .cfa = 16, .cfa_reg = 6, .saved = .{ 0, -2, 0, 0, 0, 0, -1 } }, + }, "\xf8\xff\xff\xff\x08\x00\x00\x00" ++ "\x00\x00\x00\x00\xff\xff\xff\xff" ++ "x\x00" ++ + // buf is in a block that holds the pc; y shares its slot, in another block. + "\xe0\xff\xff\xff\x10\x00\x00\x00" ++ "\x40\x00\x00\x00\x60\x00\x00\x00" ++ "buf\x00" ++ + "\xe0\xff\xff\xff\x08\x00\x00\x00" ++ "\x60\x00\x00\x00\x80\x00\x00\x00" ++ "y\x00"); + // The process began with its stack at 7ff158: one argument, one variable, one auxiliary entry. + const start: Debugger.Start = .{ .sp = 0x7ff158, .argc = 1, .envc = 1, .auxc = 1 }; + try rec.emit(.{ .kind = .string, .a = .{ event.frameId(0), 0, 0, 0, 0, 0 } }, std.mem.asBytes(&start)); + // g stopped after its push (rsp 7ff100): rbx, then its return into f; + // f's frame up to 7ff150 (rbp 7ff140), which returns to code with no frame recorded. + var stack: [10]u64 = @splat(0); + stack[0] = 0x1234; + stack[1] = 0x400050; + stack[9] = 0x400999; + try rec.emit(.{ .kind = .mem_write, .tid = 1, .a = .{ 0x7ff100, 80, 0, 0, 0, 0 } }, std.mem.sliceAsBytes(&stack)); + 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); + const regs: event.Regs = .{ .rip = 0x400101, .rsp = 0x7ff100, .rbp = 0x7ff140 }; + var out: [4]Debugger.Frame = undefined; + // By the frame pointer alone g's caller f would be passed over. + try std.testing.expectEqualSlices(Debugger.Frame, &.{ + .{ .pc = 0x400101, .low = 0x7ff100, .high = 0x7ff110 }, + .{ .pc = 0x400050, .low = 0x7ff110, .high = 0x7ff150 }, + .{ .pc = 0x400999, .low = 0x7ff150, .high = 0x7ff150 }, + }, try frames(m, ®s, &out)); + + var words: [16]Slot = undefined; + const got = try slots(m, ®s, 0x7ff100, &words); + const local = struct { + fn of(name: []const u8, size: u32, offset: i32) Role { + return .{ .local = .{ .name = name, .size = size, .offset = offset } }; + } + }.of; + const want = [16]struct { Role, ?u8 }{ + .{ .{ .saved = "rbx" }, 0 }, .{ .return_address, 0 }, .{ .none, 1 }, + .{ .none, 1 }, .{ local("buf", 16, 0), 1 }, .{ local("buf", 16, 8), 1 }, + .{ .none, 1 }, .{ local("x", 8, 0), 1 }, .{ .{ .saved = "rbp" }, 1 }, + .{ .return_address, 1 }, .{ .none, null }, .{ .argc, null }, + .{ .{ .argv = 0 }, null }, .{ .{ .argv = 1 }, null }, .{ .{ .envp = 0 }, null }, + .{ .{ .envp = 1 }, null }, + }; + for (want, got) |w, have| { + try std.testing.expectEqual(w[1], have.frame); + try std.testing.expectEqual(std.meta.activeTag(w[0]), std.meta.activeTag(have.role)); + switch (w[0]) { + .saved => |name| try std.testing.expectEqualStrings(name, have.role.saved), + .local => |l| { + try std.testing.expectEqualStrings(l.name, have.role.local.name); + try std.testing.expectEqual(l.size, have.role.local.size); + try std.testing.expectEqual(l.offset, have.role.local.offset); + }, + .argv, .envp => try std.testing.expectEqual(w[0], have.role), + else => {}, + } + } + // In g's first instruction it has pushed nothing: its return address is on top. + const entry: event.Regs = .{ .rip = 0x400100, .rsp = 0x7ff108, .rbp = 0x7ff140 }; + var two: [2]u64 = undefined; + try std.testing.expectEqual(@as(u64, 0x400050), (try backtrace(m, &entry, &two))[1]); +} |
