1 /* CFI program execution.
2 Copyright (C) 2009-2010, 2014, 2015 Red Hat, Inc.
3 This file is part of elfutils.
4
5 This file is free software; you can redistribute it and/or modify
6 it under the terms of either
7
8 * the GNU Lesser General Public License as published by the Free
9 Software Foundation; either version 3 of the License, or (at
10 your option) any later version
11
12 or
13
14 * the GNU General Public License as published by the Free
15 Software Foundation; either version 2 of the License, or (at
16 your option) any later version
17
18 or both in parallel, as here.
19
20 elfutils is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 General Public License for more details.
24
25 You should have received copies of the GNU General Public License and
26 the GNU Lesser General Public License along with this program. If
27 not, see <http://www.gnu.org/licenses/>. */
28
29 #ifdef HAVE_CONFIG_H
30 # include <config.h>
31 #endif
32
33 #include <dwarf.h>
34 #include "../libebl/libebl.h"
35 #include "cfi.h"
36 #include "memory-access.h"
37 #include "encoded-value.h"
38 #include "system.h"
39 #include <assert.h>
40 #include <stdlib.h>
41 #include <string.h>
42
43 #define CFI_PRIMARY_MAX 0x3f
44
45 static Dwarf_Frame *
duplicate_frame_state(const Dwarf_Frame * original,Dwarf_Frame * prev)46 duplicate_frame_state (const Dwarf_Frame *original,
47 Dwarf_Frame *prev)
48 {
49 size_t size = offsetof (Dwarf_Frame, regs[original->nregs]);
50 Dwarf_Frame *copy = malloc (size);
51 if (likely (copy != NULL))
52 {
53 memcpy (copy, original, size);
54 copy->prev = prev;
55 }
56 return copy;
57 }
58
59 static inline bool
enough_registers(Dwarf_Word reg,Dwarf_Frame ** pfs,int * result)60 enough_registers (Dwarf_Word reg, Dwarf_Frame **pfs, int *result)
61 {
62 /* Don't allow insanely large register numbers. 268435456 registers
63 should be enough for anybody. And very large values might overflow
64 the array size and offsetof calculations below. */
65 if (unlikely (reg >= INT32_MAX / sizeof ((*pfs)->regs[0])))
66 {
67 *result = DWARF_E_INVALID_CFI;
68 return false;
69 }
70
71 if ((*pfs)->nregs <= reg)
72 {
73 size_t size = offsetof (Dwarf_Frame, regs[reg + 1]);
74 Dwarf_Frame *bigger = realloc (*pfs, size);
75 if (unlikely (bigger == NULL))
76 {
77 *result = DWARF_E_NOMEM;
78 return false;
79 }
80 else
81 {
82 eu_static_assert (reg_unspecified == 0);
83 memset (bigger->regs + bigger->nregs, 0,
84 (reg + 1 - bigger->nregs) * sizeof bigger->regs[0]);
85 bigger->nregs = reg + 1;
86 *pfs = bigger;
87 }
88 }
89 return true;
90 }
91
92 static inline void
require_cfa_offset(Dwarf_Frame * fs)93 require_cfa_offset (Dwarf_Frame *fs)
94 {
95 if (unlikely (fs->cfa_rule != cfa_offset))
96 fs->cfa_rule = cfa_invalid;
97 }
98
99 /* Returns a DWARF_E_* error code, usually NOERROR or INVALID_CFI.
100 Frees *STATE on failure. */
101 static int
execute_cfi(Dwarf_CFI * cache,const struct dwarf_cie * cie,Dwarf_Frame ** state,const uint8_t * program,const uint8_t * const end,bool abi_cfi,Dwarf_Addr loc,Dwarf_Addr find_pc)102 execute_cfi (Dwarf_CFI *cache,
103 const struct dwarf_cie *cie,
104 Dwarf_Frame **state,
105 const uint8_t *program, const uint8_t *const end, bool abi_cfi,
106 Dwarf_Addr loc, Dwarf_Addr find_pc)
107 {
108 /* The caller should not give us anything out of range. */
109 assert (loc <= find_pc);
110
111 int result = DWARF_E_NOERROR;
112
113 #define cfi_assert(ok) do { \
114 if (likely (ok)) break; \
115 result = DWARF_E_INVALID_CFI; \
116 goto out; \
117 } while (0)
118
119 Dwarf_Frame *fs = *state;
120
121 #define register_rule(regno, r_rule, r_value) do { \
122 if (unlikely (! enough_registers (regno, &fs, &result))) \
123 goto out; \
124 fs->regs[regno].rule = reg_##r_rule; \
125 fs->regs[regno].value = (r_value); \
126 } while (0)
127
128 while (program < end)
129 {
130 uint8_t opcode = *program++;
131 Dwarf_Word regno;
132 Dwarf_Word offset;
133 Dwarf_Word sf_offset;
134 Dwarf_Word operand = opcode & CFI_PRIMARY_MAX;
135 switch (opcode)
136 {
137 /* These cases move LOC, i.e. "create a new table row". */
138
139 case DW_CFA_advance_loc1:
140 operand = *program++;
141 FALLTHROUGH;
142 case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX:
143 advance_loc:
144 loc += operand * cie->code_alignment_factor;
145 break;
146
147 case DW_CFA_advance_loc2:
148 cfi_assert (program + 2 <= end);
149 operand = read_2ubyte_unaligned_inc (cache, program);
150 goto advance_loc;
151 case DW_CFA_advance_loc4:
152 cfi_assert (program + 4 <= end);
153 operand = read_4ubyte_unaligned_inc (cache, program);
154 goto advance_loc;
155 case DW_CFA_MIPS_advance_loc8:
156 cfi_assert (program + 8 <= end);
157 operand = read_8ubyte_unaligned_inc (cache, program);
158 goto advance_loc;
159
160 case DW_CFA_set_loc:
161 if (likely (!read_encoded_value (cache, cie->fde_encoding,
162 &program, &loc)))
163 break;
164 result = INTUSE(dwarf_errno) ();
165 goto out;
166
167 /* Now all following cases affect this row, but do not touch LOC.
168 These cases end with 'continue'. We only get out of the
169 switch block for the row-copying (LOC-moving) cases above. */
170
171 case DW_CFA_def_cfa:
172 get_uleb128 (operand, program, end);
173 cfi_assert (program < end);
174 get_uleb128 (offset, program, end);
175 def_cfa:
176 fs->cfa_rule = cfa_offset;
177 fs->cfa_val_reg = operand;
178 fs->cfa_val_offset = offset;
179 /* Prime the rest of the Dwarf_Op so dwarf_frame_cfa can use it. */
180 fs->cfa_data.offset.atom = DW_OP_bregx;
181 fs->cfa_data.offset.offset = 0;
182 continue;
183
184 case DW_CFA_def_cfa_register:
185 get_uleb128 (regno, program, end);
186 require_cfa_offset (fs);
187 fs->cfa_val_reg = regno;
188 continue;
189
190 case DW_CFA_def_cfa_sf:
191 get_uleb128 (operand, program, end);
192 cfi_assert (program < end);
193 get_sleb128 (sf_offset, program, end);
194 offset = sf_offset * cie->data_alignment_factor;
195 goto def_cfa;
196
197 case DW_CFA_def_cfa_offset:
198 get_uleb128 (offset, program, end);
199 def_cfa_offset:
200 require_cfa_offset (fs);
201 fs->cfa_val_offset = offset;
202 continue;
203
204 case DW_CFA_def_cfa_offset_sf:
205 get_sleb128 (sf_offset, program, end);
206 offset = sf_offset * cie->data_alignment_factor;
207 goto def_cfa_offset;
208
209 case DW_CFA_def_cfa_expression:
210 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
211 get_uleb128 (operand, program, end);
212 cfi_assert (operand <= (Dwarf_Word) (end - program));
213 fs->cfa_rule = cfa_expr;
214 fs->cfa_data.expr.data = (unsigned char *) program;
215 fs->cfa_data.expr.length = operand;
216 program += operand;
217 continue;
218
219 case DW_CFA_undefined:
220 get_uleb128 (regno, program, end);
221 register_rule (regno, undefined, 0);
222 continue;
223
224 case DW_CFA_same_value:
225 get_uleb128 (regno, program, end);
226 register_rule (regno, same_value, 0);
227 continue;
228
229 case DW_CFA_offset_extended:
230 get_uleb128 (operand, program, end);
231 cfi_assert (program < end);
232 FALLTHROUGH;
233 case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
234 get_uleb128 (offset, program, end);
235 offset *= cie->data_alignment_factor;
236 offset_extended:
237 register_rule (operand, offset, offset);
238 continue;
239
240 case DW_CFA_offset_extended_sf:
241 get_uleb128 (operand, program, end);
242 get_sleb128 (sf_offset, program, end);
243 offset_extended_sf:
244 offset = sf_offset * cie->data_alignment_factor;
245 goto offset_extended;
246
247 case DW_CFA_GNU_negative_offset_extended:
248 /* GNU extension obsoleted by DW_CFA_offset_extended_sf. */
249 get_uleb128 (operand, program, end);
250 cfi_assert (program < end);
251 get_uleb128 (offset, program, end);
252 sf_offset = -offset;
253 goto offset_extended_sf;
254
255 case DW_CFA_val_offset:
256 get_uleb128 (operand, program, end);
257 cfi_assert (program < end);
258 get_uleb128 (offset, program, end);
259 offset *= cie->data_alignment_factor;
260 val_offset:
261 register_rule (operand, val_offset, offset);
262 continue;
263
264 case DW_CFA_val_offset_sf:
265 get_uleb128 (operand, program, end);
266 cfi_assert (program < end);
267 get_sleb128 (sf_offset, program, end);
268 offset = sf_offset * cie->data_alignment_factor;
269 goto val_offset;
270
271 case DW_CFA_register:
272 get_uleb128 (regno, program, end);
273 cfi_assert (program < end);
274 get_uleb128 (operand, program, end);
275 register_rule (regno, register, operand);
276 continue;
277
278 case DW_CFA_expression:
279 /* Expression rule relies on section data, abi_cfi cannot use it. */
280 assert (! abi_cfi);
281 get_uleb128 (regno, program, end);
282 offset = program - (const uint8_t *) cache->data->d.d_buf;
283 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
284 cfi_assert (program < end);
285 get_uleb128 (operand, program, end);
286 cfi_assert (operand <= (Dwarf_Word) (end - program));
287 program += operand;
288 register_rule (regno, expression, offset);
289 continue;
290
291 case DW_CFA_val_expression:
292 /* Expression rule relies on section data, abi_cfi cannot use it. */
293 assert (! abi_cfi);
294 get_uleb128 (regno, program, end);
295 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
296 offset = program - (const uint8_t *) cache->data->d.d_buf;
297 get_uleb128 (operand, program, end);
298 cfi_assert (operand <= (Dwarf_Word) (end - program));
299 program += operand;
300 register_rule (regno, val_expression, offset);
301 continue;
302
303 case DW_CFA_restore_extended:
304 get_uleb128 (operand, program, end);
305 FALLTHROUGH;
306 case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
307
308 if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
309 {
310 /* Special case hack to give backend abi_cfi a shorthand. */
311 cache->default_same_value = true;
312 continue;
313 }
314
315 /* This can't be used in the CIE's own initial instructions. */
316 cfi_assert (cie->initial_state != NULL);
317
318 /* Restore the CIE's initial rule for this register. */
319 if (unlikely (! enough_registers (operand, &fs, &result)))
320 goto out;
321 if (cie->initial_state->nregs > operand)
322 fs->regs[operand] = cie->initial_state->regs[operand];
323 else
324 fs->regs[operand].rule = reg_unspecified;
325 continue;
326
327 case DW_CFA_remember_state:
328 {
329 /* Duplicate the state and chain the copy on. */
330 Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
331 if (unlikely (copy == NULL))
332 {
333 result = DWARF_E_NOMEM;
334 goto out;
335 }
336 fs = copy;
337 continue;
338 }
339
340 case DW_CFA_restore_state:
341 {
342 /* Pop the current state off and use the old one instead. */
343 Dwarf_Frame *prev = fs->prev;
344 cfi_assert (prev != NULL);
345 free (fs);
346 fs = prev;
347 continue;
348 }
349
350 case DW_CFA_nop:
351 continue;
352
353 case DW_CFA_GNU_window_save: /* DW_CFA_AARCH64_negate_ra_state */
354 if (cache->e_machine == EM_AARCH64)
355 {
356 /* Toggles the return address state, indicating whether
357 the return address is encrypted or not on
358 aarch64. XXX not handled yet. */
359 }
360 else
361 {
362 /* This is magic shorthand used only by SPARC. It's
363 equivalent to a bunch of DW_CFA_register and
364 DW_CFA_offset operations. */
365 if (unlikely (! enough_registers (31, &fs, &result)))
366 goto out;
367 for (regno = 8; regno < 16; ++regno)
368 {
369 /* Find each %oN in %iN. */
370 fs->regs[regno].rule = reg_register;
371 fs->regs[regno].value = regno + 16;
372 }
373 unsigned int address_size;
374 address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
375 ? 4 : 8);
376 for (; regno < 32; ++regno)
377 {
378 /* Find %l0..%l7 and %i0..%i7 in a block at the CFA. */
379 fs->regs[regno].rule = reg_offset;
380 fs->regs[regno].value = (regno - 16) * address_size;
381 }
382 }
383 continue;
384
385 case DW_CFA_GNU_args_size:
386 /* XXX is this useful for anything? */
387 get_uleb128 (operand, program, end);
388 continue;
389
390 default:
391 cfi_assert (false);
392 continue;
393 }
394
395 /* We get here only for the cases that have just moved LOC. */
396 cfi_assert (cie->initial_state != NULL);
397 if (find_pc >= loc)
398 /* This advance has not yet reached FIND_PC. */
399 fs->start = loc;
400 else
401 {
402 /* We have just advanced past the address we're looking for.
403 The state currently described is what we want to see. */
404 fs->end = loc;
405 break;
406 }
407 }
408
409 /* "The end of the instruction stream can be thought of as a
410 DW_CFA_set_loc (initial_location + address_range) instruction."
411 (DWARF 3.0 Section 6.4.3)
412
413 When we fall off the end of the program without an advance_loc/set_loc
414 that put us past FIND_PC, the final state left by the FDE program
415 applies to this address (the caller ensured it was inside the FDE).
416 This address (FDE->end) is already in FS->end as set by the caller. */
417
418 #undef register_rule
419 #undef cfi_assert
420
421 out:
422
423 /* Pop any remembered states left on the stack. */
424 while (fs->prev != NULL)
425 {
426 Dwarf_Frame *prev = fs->prev;
427 fs->prev = prev->prev;
428 free (prev);
429 }
430
431 if (likely (result == DWARF_E_NOERROR))
432 *state = fs;
433 else
434 free (fs);
435
436 return result;
437 }
438
439 static int
cie_cache_initial_state(Dwarf_CFI * cache,struct dwarf_cie * cie)440 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
441 {
442 int result = DWARF_E_NOERROR;
443
444 if (likely (cie->initial_state != NULL))
445 return result;
446
447 /* This CIE has not been used before. Play out its initial
448 instructions and cache the initial state that results.
449 First we'll let the backend fill in the default initial
450 state for this machine's ABI. */
451
452 Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
453
454 /* Make sure we have a backend handle cached. */
455 if (unlikely (cache->ebl == NULL))
456 {
457 cache->ebl = ebl_openbackend (cache->data->s->elf);
458 if (unlikely (cache->ebl == NULL))
459 cache->ebl = (void *) -1l;
460 }
461
462 /* Fetch the ABI's default CFI program. */
463 if (likely (cache->ebl != (void *) -1l)
464 && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
465 return DWARF_E_UNKNOWN_ERROR;
466
467 Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
468 if (unlikely (cie_fs == NULL))
469 return DWARF_E_NOMEM;
470
471 /* If the default state of any register is not "undefined"
472 (i.e. call-clobbered), then the backend supplies instructions
473 for the standard initial state. */
474 if (abi_info.initial_instructions_end > abi_info.initial_instructions)
475 {
476 /* Dummy CIE for backend's instructions. */
477 struct dwarf_cie abi_cie =
478 {
479 .code_alignment_factor = abi_info.code_alignment_factor,
480 .data_alignment_factor = abi_info.data_alignment_factor,
481 };
482 result = execute_cfi (cache, &abi_cie, &cie_fs,
483 abi_info.initial_instructions,
484 abi_info.initial_instructions_end, true,
485 0, (Dwarf_Addr) -1l);
486 }
487
488 /* Now run the CIE's initial instructions. */
489 if (cie->initial_instructions_end > cie->initial_instructions
490 && likely (result == DWARF_E_NOERROR))
491 result = execute_cfi (cache, cie, &cie_fs,
492 cie->initial_instructions,
493 cie->initial_instructions_end, false,
494 0, (Dwarf_Addr) -1l);
495
496 if (likely (result == DWARF_E_NOERROR))
497 {
498 /* Now we have the initial state of things that all
499 FDEs using this CIE will start from. */
500 cie_fs->cache = cache;
501 cie->initial_state = cie_fs;
502 }
503
504 return result;
505 }
506
507 int
508 internal_function
__libdw_frame_at_address(Dwarf_CFI * cache,struct dwarf_fde * fde,Dwarf_Addr address,Dwarf_Frame ** frame)509 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
510 Dwarf_Addr address, Dwarf_Frame **frame)
511 {
512 int result = cie_cache_initial_state (cache, fde->cie);
513 if (likely (result == DWARF_E_NOERROR))
514 {
515 Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
516 if (unlikely (fs == NULL))
517 return DWARF_E_NOMEM;
518
519 fs->fde = fde;
520 fs->start = fde->start;
521 fs->end = fde->end;
522
523 result = execute_cfi (cache, fde->cie, &fs,
524 fde->instructions, fde->instructions_end, false,
525 fde->start, address);
526 if (likely (result == DWARF_E_NOERROR))
527 *frame = fs;
528 }
529 return result;
530 }
531