//! What the program's pointers reach: the structs found by following typed //! pointers through recorded memory, from the live variables (`ztrace cc` //! describes every variable's type, and each struct's fields). The //! node-link view draws them; the memory grid names their rows after them. const std = @import("std"); const Recording = @import("Recording.zig"); const types = Recording.types; pub const Object = struct { addr: u64, /// A struct or union: `record.fields`, `record.size`. type: types.Type, /// Its place among the objects of its kind, for good: the order its /// allocation was made in. Null for one that is not on the heap. slot: ?usize, /// Its allocation is gone: something still points at freed memory. freed: bool, pub fn holds(o: Object, addr: u64) bool { return addr >= o.addr and addr - o.addr < o.type.record.size; } /// The first field that is a plain number: what a node shows as its value. pub fn valueField(o: Object) ?types.Field { for (o.type.record.fields) |f| if (f.type == .scalar) return f; return null; } }; /// A pointer field of a struct, or a pointer variable: where it is and what /// it holds (null: bytes never recorded). pub const Link = struct { from: u64, to: ?u64 }; /// Every struct reachable at `m` from the live pointer variables (from the /// one called `root`, when given), nearest first, in `scratch`. /// shortcut: 64 objects at most; a bigger structure wants a view of part of it. pub fn reach(scratch: std.mem.Allocator, rec: *const Recording, m: Recording.Moment, root: ?[]const u8) []Object { var found: std.ArrayList(Object) = .empty; const variables = m.variables(scratch) catch return &.{}; for (variables) |v| { if (root) |name| if (!std.mem.eql(u8, rec.name(v.name), name)) continue; // A local its call has yet to assign points wherever that stretch of stack did before. if (!rec.assigned(v, m.index)) continue; const t = rec.typeOf(scratch, v.type) orelse continue; if (t == .pointer) follow(scratch, rec, m, &found, v.addr, t.pointer.*); } // Then what they point at, and so on: `found` grows as it is read. var i: usize = 0; while (i < found.items.len) : (i += 1) { const o = found.items[i]; for (o.type.record.fields) |f| if (f.type == .pointer) follow(scratch, rec, m, &found, o.addr + f.offset, f.type.pointer.*); } return found.items; } /// Adds the struct the pointer at `at` points to, if it is one and is new. fn follow(scratch: std.mem.Allocator, rec: *const Recording, m: Recording.Moment, found: *std.ArrayList(Object), at: u64, pointee: types.Type) void { if (found.items.len >= 64) return; const t = rec.resolve(scratch, pointee) orelse return; if (t != .record) return; const addr = (Recording.word(m, at, 8) catch return) orelse return; if (addr == 0) return; for (found.items) |o| if (o.addr == addr) return; const live = (m.allocation(addr) catch null) != null; found.append(scratch, .{ .addr = addr, .type = t, .slot = slotOf(rec, addr, m), .freed = !live and wasAllocated(rec, addr, m.index) }) catch {}; } /// The place of the allocation at `addr` among every allocation of its /// size ever made, in the order they were made: it never changes, so a /// node drawn there stays there as the structure grows and shrinks. /// shortcut: other things of the same size allocated between nodes leave gaps. pub fn slotOf(rec: *const Recording, addr: u64, m: Recording.Moment) ?usize { const born = latest(rec, addr, m.index) orelse return null; var slot: usize = 0; for (rec.allocations[0..born]) |a| slot += @intFromBool(a.size == rec.allocations[born].size); return slot; } fn wasAllocated(rec: *const Recording, addr: u64, moment: u64) bool { return latest(rec, addr, moment) != null; } /// The newest allocation at `addr` made by `moment`. fn latest(rec: *const Recording, addr: u64, moment: u64) ?usize { var i = rec.allocations.len; while (i > 0) { i -= 1; const a = rec.allocations[i]; if (a.moment <= moment and a.ptr == addr) return i; } return null; } /// A type as C spells it (the programs recorded are C): `int`, `node *`. pub fn spell(scratch: std.mem.Allocator, t: types.Type) []const u8 { return switch (t) { .void => "void", .scalar => |s| switch (s.kind) { .int => switch (s.bits) { 8 => "signed char", 16 => "short", 32 => "int", else => "long", }, .uint => switch (s.bits) { 8 => "unsigned char", 16 => "unsigned short", 32 => "unsigned", else => "unsigned long", }, .float => if (s.bits == 32) "float" else "double", .char => "char", .bool => "bool", .@"opaque" => "?", }, .pointer => |to| std.fmt.allocPrint(scratch, "{s} *", .{spell(scratch, to.*)}) catch "?", .array => |a| std.fmt.allocPrint(scratch, "{s} [{d}]", .{ spell(scratch, a.elem.*), a.len }) catch "?", .named => |name| name, .record => "struct", .@"enum" => "enum", .function => "function", }; } /// A variable as C declares it: `int a[8]`, `node *prev`, `long n`. pub fn declare(scratch: std.mem.Allocator, rec: *const Recording, v: Recording.Variable) []const u8 { const name = rec.name(v.name); const t = types.parse(scratch, rec.strings.get(v.type) orelse return name) catch return name; return switch (t) { .array => |a| std.fmt.allocPrint(scratch, "{s} {s}[{d}]", .{ spell(scratch, a.elem.*), name, a.len }) catch name, .pointer => std.fmt.allocPrint(scratch, "{s}{s}", .{ spell(scratch, t), name }) catch name, else => std.fmt.allocPrint(scratch, "{s} {s}", .{ spell(scratch, t), name }) catch name, }; } /// The live variables that hold `addr`: the names a node goes by. Not one /// its call has yet to assign: what its stretch of stack held before is /// not its value. pub fn pointing(scratch: std.mem.Allocator, rec: *const Recording, m: Recording.Moment, addr: u64) []Recording.Variable { var out: std.ArrayList(Recording.Variable) = .empty; const variables = m.variables(scratch) catch return &.{}; for (variables) |v| { if (v.size != 8 or rec.name(v.name).len == 0 or !rec.assigned(v, m.index)) continue; if ((Recording.word(m, v.addr, 8) catch null) == addr) out.append(scratch, v) catch break; } return out.items; } /// Which of `tracked` (variable names, each with a pigment by its place) /// holds `addr`: the first, null when none does. pub fn pigment(scratch: std.mem.Allocator, rec: *const Recording, m: Recording.Moment, tracked: []const []const u8, addr: u64) ?usize { for (tracked, 0..) |name, i| { const v = rec.variable(scratch, m, name) orelse continue; if (rec.assigned(v, m.index) and (Recording.word(m, v.addr, 8) catch null) == addr) return i; } return null; } test "types are spelled as C spells them" { var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); defer arena.deinit(); const int: types.Type = .{ .scalar = .{ .kind = .int, .bits = 32 } }; try std.testing.expectEqualStrings("int", spell(arena.allocator(), int)); try std.testing.expectEqualStrings("node *", spell(arena.allocator(), .{ .pointer = &.{ .named = "node" } })); try std.testing.expectEqualStrings("int [8]", spell(arena.allocator(), .{ .array = .{ .len = 8, .elem = &int } })); }