tiny.memtrace.stack.capture

1const std = @import("std");2const pretty_json = @import("pretty").json;3const sys = @import("sys");45pub const max_frames_limit: usize = 512;6const no_record = std.math.maxInt(u32);7const metadata_tag = "\"meta\":\"memtrace.stack\"";89pub const Attribution = enum {10    return_address,11    stack,12};1314pub const Capture = struct {15    addresses: []const usize,16    truncated: bool,17    unwind_failed: bool,18    missing_return_address: bool,19};2021pub const Definition = struct {22    addresses: []usize,23    truncated: bool,24    unwind_failed: bool,25    missing_return_address: bool,26    collision_next: u32,2728    pub fn complete(self: Definition) bool {29        return !self.truncated and30            !self.unwind_failed and31            !self.missing_return_address;32    }33};3435pub const Interned = struct {36    id: u32,37    is_new: bool,38};3940pub const Interner = struct {41    definitions: std.ArrayListUnmanaged(Definition) = .empty,42    collision_heads: std.AutoHashMapUnmanaged(u64, u32) = .{},4344    pub fn deinit(self: *Interner, allocator: std.mem.Allocator) void {45        for (self.definitions.items) |entry| allocator.free(entry.addresses);46        self.definitions.deinit(allocator);47        self.collision_heads.deinit(allocator);48        self.* = .{};49    }5051    pub fn intern(52        self: *Interner,53        allocator: std.mem.Allocator,54        captured: Capture,55    ) !Interned {56        std.debug.assert(captured.addresses.len > 0);57        std.debug.assert(captured.addresses.len <= max_frames_limit);58        const hash = captureHash(captured);59        const prior = self.collision_heads.get(hash);60        var candidate = prior orelse no_record;61        while (candidate != no_record) {62            const entry = self.definitions.items[candidate];63            if (entry.truncated == captured.truncated and64                entry.unwind_failed == captured.unwind_failed and65                entry.missing_return_address == captured.missing_return_address and66                std.mem.eql(usize, entry.addresses, captured.addresses))67            {68                return .{ .id = candidate + 1, .is_new = false };69            }70            candidate = entry.collision_next;71        }72        if (self.definitions.items.len >= no_record) return error.OutOfMemory;73        const owned = try allocator.dupe(usize, captured.addresses);74        errdefer allocator.free(owned);75        try self.definitions.ensureUnusedCapacity(allocator, 1);76        const head = try self.collision_heads.getOrPut(allocator, hash);77        const index: u32 = @intCast(self.definitions.items.len);78        self.definitions.appendAssumeCapacity(.{79            .addresses = owned,80            .truncated = captured.truncated,81            .unwind_failed = captured.unwind_failed,82            .missing_return_address = captured.missing_return_address,83            .collision_next = prior orelse no_record,84        });85        head.value_ptr.* = index;86        return .{ .id = index + 1, .is_new = true };87    }8889    pub fn recordForId(self: *const Interner, id: u32) *const Definition {90        std.debug.assert(id > 0);91        std.debug.assert(id <= self.definitions.items.len);92        return &self.definitions.items[id - 1];93    }94};9596pub fn supportsCapture() bool {97    return sys.backtrace.supportsCapture();98}99100pub fn isMetadataLine(line: []const u8) bool {101    return std.mem.indexOf(u8, line, metadata_tag) != null;102}103104pub fn writeDefinition(105    writer: *std.Io.Writer,106    id: u32,107    definition: Definition,108) !void {109    std.debug.assert(id > 0);110    var stream = pretty_json.Writer.init(writer, .minified);111    const object = try stream.object();112    try object.field("v", 1);113    try object.field("meta", "memtrace.stack");114    try object.field("stack_id", id);115    try object.field("truncated", definition.truncated);116    try object.field("unwind_failed", definition.unwind_failed);117    try object.field("missing_return_address", definition.missing_return_address);118    const addresses = try object.array("call_addresses");119    for (definition.addresses) |address| try addresses.element(address);120    try addresses.end();121    try object.endLine();122}123124pub fn validateFrameLimit(limit: usize) !void {125    if (limit < 2 or limit > max_frames_limit) return error.InvalidStackFrameLimit;126}127128pub noinline fn capture(129    storage: *[max_frames_limit]usize,130    return_address: usize,131    frame_limit: usize,132) Capture {133    std.debug.assert(frame_limit >= 2);134    std.debug.assert(frame_limit <= storage.len);135    storage[0] = callAddress(return_address);136    const available = frame_limit - 1;137    const raw = @as(138        [*]?*anyopaque,139        @ptrCast(@alignCast(storage[1..].ptr)),140    )[0..available];141    @memset(raw, null);142    const count = sys.backtrace.capture(raw);143    for (storage[1 .. count + 1]) |*address| {144        address.* = callAddress(address.*);145    }146    return .{147        .addresses = storage[0 .. count + 1],148        .truncated = count == available,149        .unwind_failed = count == 0,150        .missing_return_address = return_address == 0,151    };152}153154pub fn callAddress(return_address: usize) usize {155    if (comptime @import("builtin").cpu.arch.isSPARC()) return return_address;156    return return_address -| 1;157}158159fn captureHash(captured: Capture) u64 {160    const flags: u64 =161        @as(u64, @intFromBool(captured.truncated)) |162        (@as(u64, @intFromBool(captured.unwind_failed)) << 1) |163        (@as(u64, @intFromBool(captured.missing_return_address)) << 2);164    return std.hash.Wyhash.hash(165        flags,166        std.mem.sliceAsBytes(captured.addresses),167    );168}169170test "stack interner distinguishes complete colliding definitions" {171    var interner: Interner = .{};172    defer interner.deinit(std.testing.allocator);173    const first_addresses = [_]usize{ 1, 2, 3 };174    const second_addresses = [_]usize{ 1, 2, 4 };175    const first = try interner.intern(std.testing.allocator, .{176        .addresses = &first_addresses,177        .truncated = false,178        .unwind_failed = false,179        .missing_return_address = false,180    });181    const repeated = try interner.intern(std.testing.allocator, .{182        .addresses = &first_addresses,183        .truncated = false,184        .unwind_failed = false,185        .missing_return_address = false,186    });187    const second = try interner.intern(std.testing.allocator, .{188        .addresses = &second_addresses,189        .truncated = false,190        .unwind_failed = false,191        .missing_return_address = false,192    });193    try std.testing.expect(first.is_new);194    try std.testing.expect(!repeated.is_new);195    try std.testing.expect(second.is_new);196    try std.testing.expectEqual(first.id, repeated.id);197    try std.testing.expect(first.id != second.id);198}199200fn checkInternerAllocationFailures(allocator: std.mem.Allocator) !void {201    var interner: Interner = .{};202    defer interner.deinit(allocator);203    const first_addresses = [_]usize{ 1, 2, 3 };204    const second_addresses = [_]usize{ 1, 2, 4 };205    _ = try interner.intern(allocator, .{206        .addresses = &first_addresses,207        .truncated = false,208        .unwind_failed = false,209        .missing_return_address = false,210    });211    _ = try interner.intern(allocator, .{212        .addresses = &second_addresses,213        .truncated = false,214        .unwind_failed = false,215        .missing_return_address = false,216    });217}218219test "stack interner rolls back every allocation failure" {220    try std.testing.checkAllAllocationFailures(221        std.testing.allocator,222        checkInternerAllocationFailures,223        .{},224    );225}

1pub const capture = capture_mod;