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.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 cfi_assert (program < end);
243 get_sleb128 (sf_offset, program, end);
244 offset_extended_sf:
245 offset = sf_offset * cie->data_alignment_factor;
246 goto offset_extended;
247
248 case DW_CFA_GNU_negative_offset_extended:
249 /* GNU extension obsoleted by DW_CFA_offset_extended_sf. */
250 get_uleb128 (operand, program, end);
251 cfi_assert (program < end);
252 get_uleb128 (offset, program, end);
253 sf_offset = -offset;
254 goto offset_extended_sf;
255
256 case DW_CFA_val_offset:
257 get_uleb128 (operand, program, end);
258 cfi_assert (program < end);
259 get_uleb128 (offset, program, end);
260 offset *= cie->data_alignment_factor;
261 val_offset:
262 register_rule (operand, val_offset, offset);
263 continue;
264
265 case DW_CFA_val_offset_sf:
266 get_uleb128 (operand, program, end);
267 cfi_assert (program < end);
268 get_sleb128 (sf_offset, program, end);
269 offset = sf_offset * cie->data_alignment_factor;
270 goto val_offset;
271
272 case DW_CFA_register:
273 get_uleb128 (regno, program, end);
274 cfi_assert (program < end);
275 get_uleb128 (operand, program, end);
276 register_rule (regno, register, operand);
277 continue;
278
279 case DW_CFA_expression:
280 /* Expression rule relies on section data, abi_cfi cannot use it. */
281 assert (! abi_cfi);
282 get_uleb128 (regno, program, end);
283 offset = program - (const uint8_t *) cache->data->d.d_buf;
284 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
285 cfi_assert (program < end);
286 get_uleb128 (operand, program, end);
287 cfi_assert (operand <= (Dwarf_Word) (end - program));
288 program += operand;
289 register_rule (regno, expression, offset);
290 continue;
291
292 case DW_CFA_val_expression:
293 /* Expression rule relies on section data, abi_cfi cannot use it. */
294 assert (! abi_cfi);
295 get_uleb128 (regno, program, end);
296 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
297 offset = program - (const uint8_t *) cache->data->d.d_buf;
298 cfi_assert (program < end);
299 get_uleb128 (operand, program, end);
300 cfi_assert (operand <= (Dwarf_Word) (end - program));
301 program += operand;
302 register_rule (regno, val_expression, offset);
303 continue;
304
305 case DW_CFA_restore_extended:
306 get_uleb128 (operand, program, end);
307 FALLTHROUGH;
308 case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
309
310 if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
311 {
312 /* Special case hack to give backend abi_cfi a shorthand. */
313 cache->default_same_value = true;
314 continue;
315 }
316
317 /* This can't be used in the CIE's own initial instructions. */
318 cfi_assert (cie->initial_state != NULL);
319
320 /* Restore the CIE's initial rule for this register. */
321 if (unlikely (! enough_registers (operand, &fs, &result)))
322 goto out;
323 if (cie->initial_state->nregs > operand)
324 fs->regs[operand] = cie->initial_state->regs[operand];
325 else
326 fs->regs[operand].rule = reg_unspecified;
327 continue;
328
329 case DW_CFA_remember_state:
330 {
331 /* Duplicate the state and chain the copy on. */
332 Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
333 if (unlikely (copy == NULL))
334 {
335 result = DWARF_E_NOMEM;
336 goto out;
337 }
338 fs = copy;
339 continue;
340 }
341
342 case DW_CFA_restore_state:
343 {
344 /* Pop the current state off and use the old one instead. */
345 Dwarf_Frame *prev = fs->prev;
346 cfi_assert (prev != NULL);
347 free (fs);
348 fs = prev;
349 continue;
350 }
351
352 case DW_CFA_nop:
353 continue;
354
355 case DW_CFA_GNU_window_save: /* DW_CFA_AARCH64_negate_ra_state */
356 if (cache->e_machine == EM_AARCH64)
357 {
358 /* Toggles the return address state, indicating whether
359 the return address is encrypted or not on
360 aarch64. XXX not handled yet. */
361 }
362 else
363 {
364 /* This is magic shorthand used only by SPARC. It's
365 equivalent to a bunch of DW_CFA_register and
366 DW_CFA_offset operations. */
367 if (unlikely (! enough_registers (31, &fs, &result)))
368 goto out;
369 for (regno = 8; regno < 16; ++regno)
370 {
371 /* Find each %oN in %iN. */
372 fs->regs[regno].rule = reg_register;
373 fs->regs[regno].value = regno + 16;
374 }
375 unsigned int address_size;
376 address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
377 ? 4 : 8);
378 for (; regno < 32; ++regno)
379 {
380 /* Find %l0..%l7 and %i0..%i7 in a block at the CFA. */
381 fs->regs[regno].rule = reg_offset;
382 fs->regs[regno].value = (regno - 16) * address_size;
383 }
384 }
385 continue;
386
387 case DW_CFA_GNU_args_size:
388 /* XXX is this useful for anything? */
389 get_uleb128 (operand, program, end);
390 continue;
391
392 default:
393 cfi_assert (false);
394 continue;
395 }
396
397 /* We get here only for the cases that have just moved LOC. */
398 cfi_assert (cie->initial_state != NULL);
399 if (find_pc >= loc)
400 /* This advance has not yet reached FIND_PC. */
401 fs->start = loc;
402 else
403 {
404 /* We have just advanced past the address we're looking for.
405 The state currently described is what we want to see. */
406 fs->end = loc;
407 break;
408 }
409 }
410
411 /* "The end of the instruction stream can be thought of as a
412 DW_CFA_set_loc (initial_location + address_range) instruction."
413 (DWARF 3.0 Section 6.4.3)
414
415 When we fall off the end of the program without an advance_loc/set_loc
416 that put us past FIND_PC, the final state left by the FDE program
417 applies to this address (the caller ensured it was inside the FDE).
418 This address (FDE->end) is already in FS->end as set by the caller. */
419
420 #undef register_rule
421 #undef cfi_assert
422
423 out:
424
425 /* Pop any remembered states left on the stack. */
426 while (fs->prev != NULL)
427 {
428 Dwarf_Frame *prev = fs->prev;
429 fs->prev = prev->prev;
430 free (prev);
431 }
432
433 if (likely (result == DWARF_E_NOERROR))
434 *state = fs;
435 else
436 free (fs);
437
438 return result;
439 }
440
441 static int
cie_cache_initial_state(Dwarf_CFI * cache,struct dwarf_cie * cie)442 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
443 {
444 int result = DWARF_E_NOERROR;
445
446 if (likely (cie->initial_state != NULL))
447 return result;
448
449 /* This CIE has not been used before. Play out its initial
450 instructions and cache the initial state that results.
451 First we'll let the backend fill in the default initial
452 state for this machine's ABI. */
453
454 Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
455
456 /* Make sure we have a backend handle cached. */
457 if (unlikely (cache->ebl == NULL))
458 {
459 cache->ebl = ebl_openbackend (cache->data->s->elf);
460 if (unlikely (cache->ebl == NULL))
461 cache->ebl = (void *) -1l;
462 }
463
464 /* Fetch the ABI's default CFI program. */
465 if (likely (cache->ebl != (void *) -1l)
466 && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
467 return DWARF_E_UNKNOWN_ERROR;
468
469 Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
470 if (unlikely (cie_fs == NULL))
471 return DWARF_E_NOMEM;
472
473 /* If the default state of any register is not "undefined"
474 (i.e. call-clobbered), then the backend supplies instructions
475 for the standard initial state. */
476 if (abi_info.initial_instructions_end > abi_info.initial_instructions)
477 {
478 /* Dummy CIE for backend's instructions. */
479 struct dwarf_cie abi_cie =
480 {
481 .code_alignment_factor = abi_info.code_alignment_factor,
482 .data_alignment_factor = abi_info.data_alignment_factor,
483 };
484 result = execute_cfi (cache, &abi_cie, &cie_fs,
485 abi_info.initial_instructions,
486 abi_info.initial_instructions_end, true,
487 0, (Dwarf_Addr) -1l);
488 }
489
490 /* Now run the CIE's initial instructions. */
491 if (cie->initial_instructions_end > cie->initial_instructions
492 && likely (result == DWARF_E_NOERROR))
493 result = execute_cfi (cache, cie, &cie_fs,
494 cie->initial_instructions,
495 cie->initial_instructions_end, false,
496 0, (Dwarf_Addr) -1l);
497
498 if (likely (result == DWARF_E_NOERROR))
499 {
500 /* Now we have the initial state of things that all
501 FDEs using this CIE will start from. */
502 cie_fs->cache = cache;
503 cie->initial_state = cie_fs;
504 }
505
506 return result;
507 }
508
509 int
510 internal_function
__libdw_frame_at_address(Dwarf_CFI * cache,struct dwarf_fde * fde,Dwarf_Addr address,Dwarf_Frame ** frame)511 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
512 Dwarf_Addr address, Dwarf_Frame **frame)
513 {
514 int result = cie_cache_initial_state (cache, fde->cie);
515 if (likely (result == DWARF_E_NOERROR))
516 {
517 Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
518 if (unlikely (fs == NULL))
519 return DWARF_E_NOMEM;
520
521 fs->fde = fde;
522 fs->start = fde->start;
523 fs->end = fde->end;
524
525 result = execute_cfi (cache, fde->cie, &fs,
526 fde->instructions, fde->instructions_end, false,
527 fde->start, address);
528 if (likely (result == DWARF_E_NOERROR))
529 *frame = fs;
530 }
531 return result;
532 }
533