master
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 = .{ .reg_off = .{
251 .register = cfa.register,
252 .offset = @intCast(cfa.offset),
253 } },
254 .def_cfa_sf => |cfa| vm.current_row.cfa = .{ .reg_off = .{
255 .register = cfa.register,
256 .offset = cfa.offset_sf * cie.data_alignment_factor,
257 } },
258 .def_cfa_reg => |register| switch (vm.current_row.cfa) {
259 .none => {
260 // According to the DWARF specification, this is not valid, because this
261 // instruction can only be used to replace the register if the rule is already a
262 // `.reg_off`. However, this is emitted in practice by GNU toolchains for some
263 // targets, and so by convention is interpreted as equivalent to `.def_cfa` with
264 // an offset of 0.
265 vm.current_row.cfa = .{ .reg_off = .{
266 .register = register,
267 .offset = 0,
268 } };
269 },
270 .expression => return error.InvalidOperation,
271 .reg_off => |*ro| ro.register = register,
272 },
273 .def_cfa_offset => |offset| switch (vm.current_row.cfa) {
274 .none, .expression => return error.InvalidOperation,
275 .reg_off => |*ro| ro.offset = @intCast(offset),
276 },
277 .def_cfa_offset_sf => |offset_sf| switch (vm.current_row.cfa) {
278 .none, .expression => return error.InvalidOperation,
279 .reg_off => |*ro| ro.offset = offset_sf * cie.data_alignment_factor,
280 },
281 .def_cfa_expr => |len| {
282 vm.current_row.cfa = .{ .expression = try takeExprBlock(&fr, len) };
283 },
284 }
285 }
286}
287
288fn takeExprBlock(r: *std.Io.Reader, len: usize) error{ ReadFailed, InvalidOperand }![]const u8 {
289 return r.take(len) catch |err| switch (err) {
290 error.ReadFailed => |e| return e,
291 error.EndOfStream => return error.InvalidOperand,
292 };
293}
294
295const OpcodeByte = packed struct(u8) {
296 low: packed union {
297 operand: u6,
298 extended: enum(u6) {
299 nop = 0,
300 set_loc = 1,
301 advance_loc1 = 2,
302 advance_loc2 = 3,
303 advance_loc4 = 4,
304 offset_extended = 5,
305 restore_extended = 6,
306 undefined = 7,
307 same_value = 8,
308 register = 9,
309 remember_state = 10,
310 restore_state = 11,
311 def_cfa = 12,
312 def_cfa_register = 13,
313 def_cfa_offset = 14,
314 def_cfa_expression = 15,
315 expression = 16,
316 offset_extended_sf = 17,
317 def_cfa_sf = 18,
318 def_cfa_offset_sf = 19,
319 val_offset = 20,
320 val_offset_sf = 21,
321 val_expression = 22,
322 _,
323 },
324 },
325 opcode: enum(u2) {
326 extended = 0,
327 advance_loc = 1,
328 offset = 2,
329 restore = 3,
330 },
331};
332
333pub const Instruction = union(enum) {
334 nop,
335 remember_state,
336 restore_state,
337 advance_loc: u32,
338 set_loc: u64,
339
340 register: struct {
341 index: u8,
342 rule: union(enum) {
343 restore, // restore from cie
344 undefined,
345 same_value,
346 offset_uf: u64,
347 offset_sf: i64,
348 val_offset_uf: u64,
349 val_offset_sf: i64,
350 register: u8,
351 /// Value is the number of bytes in the DWARF expression, which the caller must read.
352 expr: usize,
353 /// Value is the number of bytes in the DWARF expression, which the caller must read.
354 val_expr: usize,
355 },
356 },
357
358 def_cfa: struct {
359 register: u8,
360 offset: u64,
361 },
362 def_cfa_sf: struct {
363 register: u8,
364 offset_sf: i64,
365 },
366 def_cfa_reg: u8,
367 def_cfa_offset: u64,
368 def_cfa_offset_sf: i64,
369 /// Value is the number of bytes in the DWARF expression, which the caller must read.
370 def_cfa_expr: usize,
371
372 pub fn read(
373 reader: *std.Io.Reader,
374 addr_size_bytes: u8,
375 endian: std.builtin.Endian,
376 ) !Instruction {
377 const inst: OpcodeByte = @bitCast(try reader.takeByte());
378 return switch (inst.opcode) {
379 .advance_loc => .{ .advance_loc = inst.low.operand },
380 .offset => .{ .register = .{
381 .index = inst.low.operand,
382 .rule = .{ .offset_uf = try reader.takeLeb128(u64) },
383 } },
384 .restore => .{ .register = .{
385 .index = inst.low.operand,
386 .rule = .restore,
387 } },
388 .extended => switch (inst.low.extended) {
389 .nop => .nop,
390 .remember_state => .remember_state,
391 .restore_state => .restore_state,
392 .advance_loc1 => .{ .advance_loc = try reader.takeByte() },
393 .advance_loc2 => .{ .advance_loc = try reader.takeInt(u16, endian) },
394 .advance_loc4 => .{ .advance_loc = try reader.takeInt(u32, endian) },
395 .set_loc => .{ .set_loc = switch (addr_size_bytes) {
396 2 => try reader.takeInt(u16, endian),
397 4 => try reader.takeInt(u32, endian),
398 8 => try reader.takeInt(u64, endian),
399 else => return error.UnsupportedAddrSize,
400 } },
401
402 .offset_extended => .{ .register = .{
403 .index = try reader.takeLeb128(u8),
404 .rule = .{ .offset_uf = try reader.takeLeb128(u64) },
405 } },
406 .offset_extended_sf => .{ .register = .{
407 .index = try reader.takeLeb128(u8),
408 .rule = .{ .offset_sf = try reader.takeLeb128(i64) },
409 } },
410 .restore_extended => .{ .register = .{
411 .index = try reader.takeLeb128(u8),
412 .rule = .restore,
413 } },
414 .undefined => .{ .register = .{
415 .index = try reader.takeLeb128(u8),
416 .rule = .undefined,
417 } },
418 .same_value => .{ .register = .{
419 .index = try reader.takeLeb128(u8),
420 .rule = .same_value,
421 } },
422 .register => .{ .register = .{
423 .index = try reader.takeLeb128(u8),
424 .rule = .{ .register = try reader.takeLeb128(u8) },
425 } },
426 .val_offset => .{ .register = .{
427 .index = try reader.takeLeb128(u8),
428 .rule = .{ .val_offset_uf = try reader.takeLeb128(u64) },
429 } },
430 .val_offset_sf => .{ .register = .{
431 .index = try reader.takeLeb128(u8),
432 .rule = .{ .val_offset_sf = try reader.takeLeb128(i64) },
433 } },
434 .expression => .{ .register = .{
435 .index = try reader.takeLeb128(u8),
436 .rule = .{ .expr = try reader.takeLeb128(usize) },
437 } },
438 .val_expression => .{ .register = .{
439 .index = try reader.takeLeb128(u8),
440 .rule = .{ .val_expr = try reader.takeLeb128(usize) },
441 } },
442
443 .def_cfa => .{ .def_cfa = .{
444 .register = try reader.takeLeb128(u8),
445 .offset = try reader.takeLeb128(u64),
446 } },
447 .def_cfa_sf => .{ .def_cfa_sf = .{
448 .register = try reader.takeLeb128(u8),
449 .offset_sf = try reader.takeLeb128(i64),
450 } },
451 .def_cfa_register => .{ .def_cfa_reg = try reader.takeLeb128(u8) },
452 .def_cfa_offset => .{ .def_cfa_offset = try reader.takeLeb128(u64) },
453 .def_cfa_offset_sf => .{ .def_cfa_offset_sf = try reader.takeLeb128(i64) },
454 .def_cfa_expression => .{ .def_cfa_expr = try reader.takeLeb128(usize) },
455
456 _ => switch (@intFromEnum(inst.low.extended)) {
457 0x1C...0x3F => return error.UnimplementedUserOpcode,
458 else => return error.InvalidOpcode,
459 },
460 },
461 };
462 }
463};
464
465const std = @import("../../../std.zig");
466const assert = std.debug.assert;
467const Allocator = std.mem.Allocator;
468const Unwind = std.debug.Dwarf.Unwind;
469
470const VirtualMachine = @This();