1//! Virtual machine that evaluates DWARF call frame instructions
2
3/// See section 6.4.1 of the DWARF5 specification for details on each
4pub const RegisterRule = union(enum) {
5 /// The spec says that the default rule for each column is the undefined rule.
6 /// However, it also allows ABI / compiler authors to specify alternate defaults, so
7 /// there is a distinction made here.
8 default,
9 undefined,
10 same_value,
11 /// offset(N)
12 offset: i64,
13 /// val_offset(N)
14 val_offset: i64,
15 /// register(R)
16 register: u8,
17 /// expression(E)
18 expression: []const u8,
19 /// val_expression(E)
20 val_expression: []const u8,
21};
22
23pub const CfaRule = union(enum) {
24 none,
25 reg_off: struct {
26 register: u8,
27 offset: i64,
28 },
29 expression: []const u8,
30};
31
32/// Each row contains unwinding rules for a set of registers.
33pub const Row = struct {
34 /// Offset from `FrameDescriptionEntry.pc_begin`
35 offset: u64 = 0,
36 cfa: CfaRule = .none,
37 /// The register fields in these columns define the register the rule applies to.
38 columns: ColumnRange = .{ .start = undefined, .len = 0 },
39};
40
41pub const Column = struct {
42 register: u8,
43 rule: RegisterRule,
44};
45
46const ColumnRange = struct {
47 start: usize,
48 len: u8,
49};
50
51columns: std.ArrayList(Column) = .empty,
52stack: std.ArrayList(struct {
53 cfa: CfaRule,
54 columns: ColumnRange,
55}) = .empty,
56current_row: Row = .{},
57
58/// The result of executing the CIE's initial_instructions
59cie_row: ?Row = null,
60
61pub fn deinit(self: *VirtualMachine, gpa: Allocator) void {
62 self.stack.deinit(gpa);
63 self.columns.deinit(gpa);
64 self.* = undefined;
65}
66
67pub fn reset(self: *VirtualMachine) void {
68 self.stack.clearRetainingCapacity();
69 self.columns.clearRetainingCapacity();
70 self.current_row = .{};
71 self.cie_row = null;
72}
73
74/// Return a slice backed by the row's non-CFA columns
75pub fn rowColumns(self: *const VirtualMachine, row: *const Row) []Column {
76 if (row.columns.len == 0) return &.{};
77 return self.columns.items[row.columns.start..][0..row.columns.len];
78}
79
80/// Either retrieves or adds a column for `register` (non-CFA) in the current row.
81fn getOrAddColumn(self: *VirtualMachine, gpa: Allocator, register: u8) !*Column {
82 for (self.rowColumns(&self.current_row)) |*c| {
83 if (c.register == register) return c;
84 }
85
86 if (self.current_row.columns.len == 0) {
87 self.current_row.columns.start = self.columns.items.len;
88 } else {
89 assert(self.current_row.columns.start + self.current_row.columns.len == self.columns.items.len);
90 }
91 self.current_row.columns.len += 1;
92
93 const column = try self.columns.addOne(gpa);
94 column.* = .{
95 .register = register,
96 .rule = .default,
97 };
98
99 return column;
100}
101
102pub fn populateCieLastRow(
103 gpa: Allocator,
104 cie: *Unwind.CommonInformationEntry,
105 addr_size_bytes: u8,
106 endian: std.builtin.Endian,
107) !void {
108 assert(cie.last_row == null);
109
110 var vm: VirtualMachine = .{};
111 defer vm.deinit(gpa);
112
113 try vm.evalInstructions(
114 gpa,
115 cie,
116 std.math.maxInt(u64),
117 cie.initial_instructions,
118 addr_size_bytes,
119 endian,
120 );
121
122 cie.last_row = .{
123 .offset = vm.current_row.offset,
124 .cfa = vm.current_row.cfa,
125 .cols = try gpa.dupe(Column, vm.rowColumns(&vm.current_row)),
126 };
127}
128
129/// Runs the CIE instructions, then the FDE instructions. Execution halts
130/// once the row that corresponds to `pc` is known, and the row is returned.
131pub fn runTo(
132 vm: *VirtualMachine,
133 gpa: Allocator,
134 pc: u64,
135 cie: *const Unwind.CommonInformationEntry,
136 fde: *const Unwind.FrameDescriptionEntry,
137 addr_size_bytes: u8,
138 endian: std.builtin.Endian,
139) !Row {
140 assert(vm.cie_row == null);
141
142 const target_offset = pc - fde.pc_begin;
143 assert(target_offset < fde.pc_range);
144
145 const instruction_bytes: []const u8 = insts: {
146 if (target_offset < cie.last_row.?.offset) {
147 break :insts cie.initial_instructions;
148 }
149 // This is the more common case: start from the CIE's last row.
150 assert(vm.columns.items.len == 0);
151 vm.current_row = .{
152 .offset = cie.last_row.?.offset,
153 .cfa = cie.last_row.?.cfa,
154 .columns = .{
155 .start = 0,
156 .len = @intCast(cie.last_row.?.cols.len),
157 },
158 };
159 try vm.columns.appendSlice(gpa, cie.last_row.?.cols);
160 vm.cie_row = vm.current_row;
161 break :insts fde.instructions;
162 };
163
164 try vm.evalInstructions(
165 gpa,
166 cie,
167 target_offset,
168 instruction_bytes,
169 addr_size_bytes,
170 endian,
171 );
172 return vm.current_row;
173}
174
175/// Evaluates instructions from `instruction_bytes` until `target_addr` is reached or all
176/// instructions have been evaluated.
177fn evalInstructions(
178 vm: *VirtualMachine,
179 gpa: Allocator,
180 cie: *const Unwind.CommonInformationEntry,
181 target_addr: u64,
182 instruction_bytes: []const u8,
183 addr_size_bytes: u8,
184 endian: std.builtin.Endian,
185) !void {
186 var fr: std.Io.Reader = .fixed(instruction_bytes);
187 while (fr.seek < fr.buffer.len) {
188 switch (try Instruction.read(&fr, addr_size_bytes, endian)) {
189 .nop => {
190 // If there was one nop, there's a good chance we've reached the padding and so
191 // everything left is a nop, which is represented by a 0 byte.
192 if (std.mem.allEqual(u8, fr.buffered(), 0)) return;
193 },
194
195 .remember_state => {
196 try vm.stack.append(gpa, .{
197 .cfa = vm.current_row.cfa,
198 .columns = vm.current_row.columns,
199 });
200 const cols_len = vm.current_row.columns.len;
201 const copy_start = vm.columns.items.len;
202 assert(vm.current_row.columns.start == copy_start - cols_len);
203 try vm.columns.ensureUnusedCapacity(gpa, cols_len); // to prevent aliasing issues
204 vm.columns.appendSliceAssumeCapacity(vm.columns.items[copy_start - cols_len ..]);
205 vm.current_row.columns.start = copy_start;
206 },
207 .restore_state => {
208 const restored = vm.stack.pop() orelse return error.InvalidOperation;
209 vm.columns.shrinkRetainingCapacity(restored.columns.start + restored.columns.len);
210
211 vm.current_row.cfa = restored.cfa;
212 vm.current_row.columns = restored.columns;
213 },
214
215 .advance_loc => |delta| {
216 const new_addr = vm.current_row.offset + delta * cie.code_alignment_factor;
217 if (new_addr > target_addr) return;
218 vm.current_row.offset = new_addr;
219 },
220 .set_loc => |new_addr| {
221 if (new_addr <= vm.current_row.offset) return error.InvalidOperation;
222 if (cie.segment_selector_size != 0) return error.InvalidOperation; // unsupported
223 // TODO: Check cie.segment_selector_size != 0 for DWARFV4
224
225 if (new_addr > target_addr) return;
226 vm.current_row.offset = new_addr;
227 },
228
229 .register => |reg| {
230 const column = try vm.getOrAddColumn(gpa, reg.index);
231 column.rule = switch (reg.rule) {
232 .restore => rule: {
233 const cie_row = &(vm.cie_row orelse return error.InvalidOperation);
234 for (vm.rowColumns(cie_row)) |cie_col| {
235 if (cie_col.register == reg.index) break :rule cie_col.rule;
236 }
237 break :rule .default;
238 },
239 .undefined => .undefined,
240 .same_value => .same_value,
241 .offset_uf => |off| .{ .offset = @as(i64, @intCast(off)) * cie.data_alignment_factor },
242 .offset_sf => |off| .{ .offset = off * cie.data_alignment_factor },
243 .val_offset_uf => |off| .{ .val_offset = @as(i64, @intCast(off)) * cie.data_alignment_factor },
244 .val_offset_sf => |off| .{ .val_offset = off * cie.data_alignment_factor },
245 .register => |callee_reg| .{ .register = callee_reg },
246 .expr => |len| .{ .expression = try takeExprBlock(&fr, len) },
247 .val_expr => |len| .{ .val_expression = try takeExprBlock(&fr, len) },
248 };
249 },
250 .def_cfa => |cfa| vm.current_row.cfa = .{
251 .reg_off = .{
252 .register = cfa.register,
253 // Unfortunately, LLVM emits negative CFI directives as their unsigned variants
254 // rather than the signed variants that DWARF has for exactly that purpose, hence
255 // `@bitCast` instead of `@intCast`.
256 .offset = @bitCast(cfa.offset),
257 },
258 },
259 .def_cfa_sf => |cfa| vm.current_row.cfa = .{ .reg_off = .{
260 .register = cfa.register,
261 .offset = cfa.offset_sf * cie.data_alignment_factor,
262 } },
263 .def_cfa_reg => |register| switch (vm.current_row.cfa) {
264 .none => {
265 // According to the DWARF specification, this is not valid, because this
266 // instruction can only be used to replace the register if the rule is already a
267 // `.reg_off`. However, this is emitted in practice by GNU toolchains for some
268 // targets, and so by convention is interpreted as equivalent to `.def_cfa` with
269 // an offset of 0.
270 vm.current_row.cfa = .{ .reg_off = .{
271 .register = register,
272 .offset = 0,
273 } };
274 },
275 .expression => return error.InvalidOperation,
276 .reg_off => |*ro| ro.register = register,
277 },
278 .def_cfa_offset => |offset| switch (vm.current_row.cfa) {
279 .none, .expression => return error.InvalidOperation,
280 // See the comment for `def_cfa` above.
281 .reg_off => |*ro| ro.offset = @bitCast(offset),
282 },
283 .def_cfa_offset_sf => |offset_sf| switch (vm.current_row.cfa) {
284 .none, .expression => return error.InvalidOperation,
285 .reg_off => |*ro| ro.offset = offset_sf * cie.data_alignment_factor,
286 },
287 .def_cfa_expr => |len| {
288 vm.current_row.cfa = .{ .expression = try takeExprBlock(&fr, len) };
289 },
290 }
291 }
292}
293
294fn takeExprBlock(r: *std.Io.Reader, len: usize) error{ ReadFailed, InvalidOperand }![]const u8 {
295 return r.take(len) catch |err| switch (err) {
296 error.ReadFailed => |e| return e,
297 error.EndOfStream => return error.InvalidOperand,
298 };
299}
300
301const OpcodeByte = packed struct(u8) {
302 low: packed union {
303 operand: u6,
304 extended: enum(u6) {
305 nop = 0,
306 set_loc = 1,
307 advance_loc1 = 2,
308 advance_loc2 = 3,
309 advance_loc4 = 4,
310 offset_extended = 5,
311 restore_extended = 6,
312 undefined = 7,
313 same_value = 8,
314 register = 9,
315 remember_state = 10,
316 restore_state = 11,
317 def_cfa = 12,
318 def_cfa_register = 13,
319 def_cfa_offset = 14,
320 def_cfa_expression = 15,
321 expression = 16,
322 offset_extended_sf = 17,
323 def_cfa_sf = 18,
324 def_cfa_offset_sf = 19,
325 val_offset = 20,
326 val_offset_sf = 21,
327 val_expression = 22,
328 _,
329 },
330 },
331 opcode: enum(u2) {
332 extended = 0,
333 advance_loc = 1,
334 offset = 2,
335 restore = 3,
336 },
337};
338
339pub const Instruction = union(enum) {
340 nop,
341 remember_state,
342 restore_state,
343 advance_loc: u32,
344 set_loc: u64,
345
346 register: struct {
347 index: u8,
348 rule: union(enum) {
349 restore, // restore from cie
350 undefined,
351 same_value,
352 offset_uf: u64,
353 offset_sf: i64,
354 val_offset_uf: u64,
355 val_offset_sf: i64,
356 register: u8,
357 /// Value is the number of bytes in the DWARF expression, which the caller must read.
358 expr: usize,
359 /// Value is the number of bytes in the DWARF expression, which the caller must read.
360 val_expr: usize,
361 },
362 },
363
364 def_cfa: struct {
365 register: u8,
366 offset: u64,
367 },
368 def_cfa_sf: struct {
369 register: u8,
370 offset_sf: i64,
371 },
372 def_cfa_reg: u8,
373 def_cfa_offset: u64,
374 def_cfa_offset_sf: i64,
375 /// Value is the number of bytes in the DWARF expression, which the caller must read.
376 def_cfa_expr: usize,
377
378 pub fn read(
379 reader: *std.Io.Reader,
380 addr_size_bytes: u8,
381 endian: std.builtin.Endian,
382 ) !Instruction {
383 const inst: OpcodeByte = @bitCast(try reader.takeByte());
384 return switch (inst.opcode) {
385 .advance_loc => .{ .advance_loc = inst.low.operand },
386 .offset => .{ .register = .{
387 .index = inst.low.operand,
388 .rule = .{ .offset_uf = try reader.takeLeb128(u64) },
389 } },
390 .restore => .{ .register = .{
391 .index = inst.low.operand,
392 .rule = .restore,
393 } },
394 .extended => switch (inst.low.extended) {
395 .nop => .nop,
396 .remember_state => .remember_state,
397 .restore_state => .restore_state,
398 .advance_loc1 => .{ .advance_loc = try reader.takeByte() },
399 .advance_loc2 => .{ .advance_loc = try reader.takeInt(u16, endian) },
400 .advance_loc4 => .{ .advance_loc = try reader.takeInt(u32, endian) },
401 .set_loc => .{ .set_loc = switch (addr_size_bytes) {
402 2 => try reader.takeInt(u16, endian),
403 4 => try reader.takeInt(u32, endian),
404 8 => try reader.takeInt(u64, endian),
405 else => return error.UnsupportedAddrSize,
406 } },
407
408 .offset_extended => .{ .register = .{
409 .index = try reader.takeLeb128(u8),
410 .rule = .{ .offset_uf = try reader.takeLeb128(u64) },
411 } },
412 .offset_extended_sf => .{ .register = .{
413 .index = try reader.takeLeb128(u8),
414 .rule = .{ .offset_sf = try reader.takeLeb128(i64) },
415 } },
416 .restore_extended => .{ .register = .{
417 .index = try reader.takeLeb128(u8),
418 .rule = .restore,
419 } },
420 .undefined => .{ .register = .{
421 .index = try reader.takeLeb128(u8),
422 .rule = .undefined,
423 } },
424 .same_value => .{ .register = .{
425 .index = try reader.takeLeb128(u8),
426 .rule = .same_value,
427 } },
428 .register => .{ .register = .{
429 .index = try reader.takeLeb128(u8),
430 .rule = .{ .register = try reader.takeLeb128(u8) },
431 } },
432 .val_offset => .{ .register = .{
433 .index = try reader.takeLeb128(u8),
434 .rule = .{ .val_offset_uf = try reader.takeLeb128(u64) },
435 } },
436 .val_offset_sf => .{ .register = .{
437 .index = try reader.takeLeb128(u8),
438 .rule = .{ .val_offset_sf = try reader.takeLeb128(i64) },
439 } },
440 .expression => .{ .register = .{
441 .index = try reader.takeLeb128(u8),
442 .rule = .{ .expr = try reader.takeLeb128(usize) },
443 } },
444 .val_expression => .{ .register = .{
445 .index = try reader.takeLeb128(u8),
446 .rule = .{ .val_expr = try reader.takeLeb128(usize) },
447 } },
448
449 .def_cfa => .{ .def_cfa = .{
450 .register = try reader.takeLeb128(u8),
451 .offset = try reader.takeLeb128(u64),
452 } },
453 .def_cfa_sf => .{ .def_cfa_sf = .{
454 .register = try reader.takeLeb128(u8),
455 .offset_sf = try reader.takeLeb128(i64),
456 } },
457 .def_cfa_register => .{ .def_cfa_reg = try reader.takeLeb128(u8) },
458 .def_cfa_offset => .{ .def_cfa_offset = try reader.takeLeb128(u64) },
459 .def_cfa_offset_sf => .{ .def_cfa_offset_sf = try reader.takeLeb128(i64) },
460 .def_cfa_expression => .{ .def_cfa_expr = try reader.takeLeb128(usize) },
461
462 _ => switch (@backingInt(inst.low.extended)) {
463 // For the moment, we just ignore these so that they don't cause unwinding to
464 // fail; `SelfUnwinder` already unconditionally strips pointer authentication
465 // codes. If this code is ever extended to be useful for remote/offline
466 // unwinding, we will have to actually model the RA sign state properly.
467 0x2C => .nop, // DW_CFA_AARCH64_negate_ra_state_with_pc
468 0x2D => .nop, // DW_CFA_AARCH64_negate_ra_state
469
470 0x1C...0x2B, 0x2E...0x3F => return error.UnimplementedUserOpcode,
471 else => return error.InvalidOpcode,
472 },
473 },
474 };
475 }
476};
477
478const std = @import("../../../std.zig");
479const assert = std.debug.assert;
480const Allocator = std.mem.Allocator;
481const Unwind = std.debug.Dwarf.Unwind;
482
483const VirtualMachine = @This();