lib/memtrace/src/stack/capture.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const pretty_json = @import("pretty").json;
3 const sys = @import("sys");
4
5 pub const max_frames_limit: usize = 512;
6 const no_record = std.math.maxInt(u32);
7 const metadata_tag = "\"meta\":\"memtrace.stack\"";
8
9 pub const Attribution = enum {
10 return_address,
11 stack,
12 };
13
14 pub const Capture = struct {
15 addresses: []const usize,
16 truncated: bool,
17 unwind_failed: bool,
18 missing_return_address: bool,
19 };
20
21 pub const Definition = struct {
22 addresses: []usize,
23 truncated: bool,
24 unwind_failed: bool,
25 missing_return_address: bool,
26 collision_next: u32,
27
28 pub fn complete(self: Definition) bool {
29 return !self.truncated and
30 !self.unwind_failed and
31 !self.missing_return_address;
32 }
33 };
34
35 pub const Interned = struct {
36 id: u32,
37 is_new: bool,
38 };
39
40 pub const Interner = struct {
41 definitions: std.ArrayListUnmanaged(Definition) = .empty,
42 collision_heads: std.AutoHashMapUnmanaged(u64, u32) = .{},
43
44 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 }
50
51 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 and
64 entry.unwind_failed == captured.unwind_failed and
65 entry.missing_return_address == captured.missing_return_address and
66 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 }
88
89 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 };
95
96 pub fn supportsCapture() bool {
97 return sys.backtrace.supportsCapture();
98 }
99
100 pub fn isMetadataLine(line: []const u8) bool {
101 return std.mem.indexOf(u8, line, metadata_tag) != null;
102 }
103
104 pub 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 }
123
124 pub fn validateFrameLimit(limit: usize) !void {
125 if (limit < 2 or limit > max_frames_limit) return error.InvalidStackFrameLimit;
126 }
127
128 pub 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 }
153
154 pub fn callAddress(return_address: usize) usize {
155 if (comptime @import("builtin").cpu.arch.isSPARC()) return return_address;
156 return return_address -| 1;
157 }
158
159 fn 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 }
169
170 test "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 }
199
200 fn 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 }
218
219 test "stack interner rolls back every allocation failure" {
220 try std.testing.checkAllAllocationFailures(
221 std.testing.allocator,
222 checkInternerAllocationFailures,
223 .{},
224 );
225 }