• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 	case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX:
142 	advance_loc:
143 	  loc += operand * cie->code_alignment_factor;
144 	  break;
145 
146 	case DW_CFA_advance_loc2:
147 	  cfi_assert (program + 2 <= end);
148 	  operand = read_2ubyte_unaligned_inc (cache, program);
149 	  goto advance_loc;
150 	case DW_CFA_advance_loc4:
151 	  cfi_assert (program + 4 <= end);
152 	  operand = read_4ubyte_unaligned_inc (cache, program);
153 	  goto advance_loc;
154 	case DW_CFA_MIPS_advance_loc8:
155 	  cfi_assert (program + 8 <= end);
156 	  operand = read_8ubyte_unaligned_inc (cache, program);
157 	  goto advance_loc;
158 
159 	case DW_CFA_set_loc:
160 	  if (likely (!read_encoded_value (cache, cie->fde_encoding,
161 					   &program, &loc)))
162 	    break;
163 	  result = INTUSE(dwarf_errno) ();
164 	  goto out;
165 
166 	  /* Now all following cases affect this row, but do not touch LOC.
167 	     These cases end with 'continue'.  We only get out of the
168 	     switch block for the row-copying (LOC-moving) cases above.  */
169 
170 	case DW_CFA_def_cfa:
171 	  get_uleb128 (operand, program, end);
172 	  cfi_assert (program < end);
173 	  get_uleb128 (offset, program, end);
174 	def_cfa:
175 	  fs->cfa_rule = cfa_offset;
176 	  fs->cfa_val_reg = operand;
177 	  fs->cfa_val_offset = offset;
178 	  /* Prime the rest of the Dwarf_Op so dwarf_frame_cfa can use it.  */
179 	  fs->cfa_data.offset.atom = DW_OP_bregx;
180 	  fs->cfa_data.offset.offset = 0;
181 	  continue;
182 
183 	case DW_CFA_def_cfa_register:
184 	  get_uleb128 (regno, program, end);
185 	  require_cfa_offset (fs);
186 	  fs->cfa_val_reg = regno;
187 	  continue;
188 
189 	case DW_CFA_def_cfa_sf:
190 	  get_uleb128 (operand, program, end);
191 	  cfi_assert (program < end);
192 	  get_sleb128 (sf_offset, program, end);
193 	  offset = sf_offset * cie->data_alignment_factor;
194 	  goto def_cfa;
195 
196 	case DW_CFA_def_cfa_offset:
197 	  get_uleb128 (offset, program, end);
198 	def_cfa_offset:
199 	  require_cfa_offset (fs);
200 	  fs->cfa_val_offset = offset;
201 	  continue;
202 
203 	case DW_CFA_def_cfa_offset_sf:
204 	  get_sleb128 (sf_offset, program, end);
205 	  offset = sf_offset * cie->data_alignment_factor;
206 	  goto def_cfa_offset;
207 
208 	case DW_CFA_def_cfa_expression:
209 	  /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
210 	  get_uleb128 (operand, program, end);
211 	  cfi_assert (operand <= (Dwarf_Word) (end - program));
212 	  fs->cfa_rule = cfa_expr;
213 	  fs->cfa_data.expr.data = (unsigned char *) program;
214 	  fs->cfa_data.expr.length = operand;
215 	  program += operand;
216 	  continue;
217 
218 	case DW_CFA_undefined:
219 	  get_uleb128 (regno, program, end);
220 	  register_rule (regno, undefined, 0);
221 	  continue;
222 
223 	case DW_CFA_same_value:
224 	  get_uleb128 (regno, program, end);
225 	  register_rule (regno, same_value, 0);
226 	  continue;
227 
228 	case DW_CFA_offset_extended:
229 	  get_uleb128 (operand, program, end);
230 	  cfi_assert (program < end);
231 	case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
232 	  get_uleb128 (offset, program, end);
233 	  offset *= cie->data_alignment_factor;
234 	offset_extended:
235 	  register_rule (operand, offset, offset);
236 	  continue;
237 
238 	case DW_CFA_offset_extended_sf:
239 	  get_uleb128 (operand, program, end);
240 	  get_sleb128 (sf_offset, program, end);
241 	offset_extended_sf:
242 	  offset = sf_offset * cie->data_alignment_factor;
243 	  goto offset_extended;
244 
245 	case DW_CFA_GNU_negative_offset_extended:
246 	  /* GNU extension obsoleted by DW_CFA_offset_extended_sf.  */
247 	  get_uleb128 (operand, program, end);
248 	  cfi_assert (program < end);
249 	  get_uleb128 (offset, program, end);
250 	  sf_offset = -offset;
251 	  goto offset_extended_sf;
252 
253 	case DW_CFA_val_offset:
254 	  get_uleb128 (operand, program, end);
255 	  cfi_assert (program < end);
256 	  get_uleb128 (offset, program, end);
257 	  offset *= cie->data_alignment_factor;
258 	val_offset:
259 	  register_rule (operand, val_offset, offset);
260 	  continue;
261 
262 	case DW_CFA_val_offset_sf:
263 	  get_uleb128 (operand, program, end);
264 	  cfi_assert (program < end);
265 	  get_sleb128 (sf_offset, program, end);
266 	  offset = sf_offset * cie->data_alignment_factor;
267 	  goto val_offset;
268 
269 	case DW_CFA_register:
270 	  get_uleb128 (regno, program, end);
271 	  cfi_assert (program < end);
272 	  get_uleb128 (operand, program, end);
273 	  register_rule (regno, register, operand);
274 	  continue;
275 
276 	case DW_CFA_expression:
277 	  /* Expression rule relies on section data, abi_cfi cannot use it.  */
278 	  assert (! abi_cfi);
279 	  get_uleb128 (regno, program, end);
280 	  offset = program - (const uint8_t *) cache->data->d.d_buf;
281 	  /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
282 	  cfi_assert (program < end);
283 	  get_uleb128 (operand, program, end);
284 	  cfi_assert (operand <= (Dwarf_Word) (end - program));
285 	  program += operand;
286 	  register_rule (regno, expression, offset);
287 	  continue;
288 
289 	case DW_CFA_val_expression:
290 	  /* Expression rule relies on section data, abi_cfi cannot use it.  */
291 	  assert (! abi_cfi);
292 	  get_uleb128 (regno, program, end);
293 	  /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
294 	  offset = program - (const uint8_t *) cache->data->d.d_buf;
295 	  get_uleb128 (operand, program, end);
296 	  cfi_assert (operand <= (Dwarf_Word) (end - program));
297 	  program += operand;
298 	  register_rule (regno, val_expression, offset);
299 	  continue;
300 
301 	case DW_CFA_restore_extended:
302 	  get_uleb128 (operand, program, end);
303 	case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
304 
305 	  if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
306 	    {
307 	      /* Special case hack to give backend abi_cfi a shorthand.  */
308 	      cache->default_same_value = true;
309 	      continue;
310 	    }
311 
312 	  /* This can't be used in the CIE's own initial instructions.  */
313 	  cfi_assert (cie->initial_state != NULL);
314 
315 	  /* Restore the CIE's initial rule for this register.  */
316 	  if (unlikely (! enough_registers (operand, &fs, &result)))
317 	    goto out;
318 	  if (cie->initial_state->nregs > operand)
319 	    fs->regs[operand] = cie->initial_state->regs[operand];
320 	  else
321 	    fs->regs[operand].rule = reg_unspecified;
322 	  continue;
323 
324 	case DW_CFA_remember_state:
325 	  {
326 	    /* Duplicate the state and chain the copy on.  */
327 	    Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
328 	    if (unlikely (copy == NULL))
329 	      {
330 		result = DWARF_E_NOMEM;
331 		goto out;
332 	      }
333 	    fs = copy;
334 	    continue;
335 	  }
336 
337 	case DW_CFA_restore_state:
338 	  {
339 	    /* Pop the current state off and use the old one instead.  */
340 	    Dwarf_Frame *prev = fs->prev;
341 	    cfi_assert (prev != NULL);
342 	    free (fs);
343 	    fs = prev;
344 	    continue;
345 	  }
346 
347 	case DW_CFA_nop:
348 	  continue;
349 
350 	case DW_CFA_GNU_window_save:
351 	  /* This is magic shorthand used only by SPARC.  It's equivalent
352 	     to a bunch of DW_CFA_register and DW_CFA_offset operations.  */
353 	  if (unlikely (! enough_registers (31, &fs, &result)))
354 	    goto out;
355 	  for (regno = 8; regno < 16; ++regno)
356 	    {
357 	      /* Find each %oN in %iN.  */
358 	      fs->regs[regno].rule = reg_register;
359 	      fs->regs[regno].value = regno + 16;
360 	    }
361 	  unsigned int address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
362 				       ? 4 : 8);
363 	  for (; regno < 32; ++regno)
364 	    {
365 	      /* Find %l0..%l7 and %i0..%i7 in a block at the CFA.  */
366 	      fs->regs[regno].rule = reg_offset;
367 	      fs->regs[regno].value = (regno - 16) * address_size;
368 	    }
369 	  continue;
370 
371 	case DW_CFA_GNU_args_size:
372 	  /* XXX is this useful for anything? */
373 	  get_uleb128 (operand, program, end);
374 	  continue;
375 
376 	default:
377 	  cfi_assert (false);
378 	  continue;
379 	}
380 
381       /* We get here only for the cases that have just moved LOC.  */
382       cfi_assert (cie->initial_state != NULL);
383       if (find_pc >= loc)
384 	/* This advance has not yet reached FIND_PC.  */
385 	fs->start = loc;
386       else
387 	{
388 	  /* We have just advanced past the address we're looking for.
389 	     The state currently described is what we want to see.  */
390 	  fs->end = loc;
391 	  break;
392 	}
393     }
394 
395   /* "The end of the instruction stream can be thought of as a
396      DW_CFA_set_loc (initial_location + address_range) instruction."
397      (DWARF 3.0 Section 6.4.3)
398 
399      When we fall off the end of the program without an advance_loc/set_loc
400      that put us past FIND_PC, the final state left by the FDE program
401      applies to this address (the caller ensured it was inside the FDE).
402      This address (FDE->end) is already in FS->end as set by the caller.  */
403 
404 #undef register_rule
405 #undef cfi_assert
406 
407  out:
408 
409   /* Pop any remembered states left on the stack.  */
410   while (fs->prev != NULL)
411     {
412       Dwarf_Frame *prev = fs->prev;
413       fs->prev = prev->prev;
414       free (prev);
415     }
416 
417   if (likely (result == DWARF_E_NOERROR))
418     *state = fs;
419   else
420     free (fs);
421 
422   return result;
423 }
424 
425 static int
cie_cache_initial_state(Dwarf_CFI * cache,struct dwarf_cie * cie)426 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
427 {
428   int result = DWARF_E_NOERROR;
429 
430   if (likely (cie->initial_state != NULL))
431     return result;
432 
433   /* This CIE has not been used before.  Play out its initial
434      instructions and cache the initial state that results.
435      First we'll let the backend fill in the default initial
436      state for this machine's ABI.  */
437 
438   Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
439 
440   /* Make sure we have a backend handle cached.  */
441   if (unlikely (cache->ebl == NULL))
442     {
443       cache->ebl = ebl_openbackend (cache->data->s->elf);
444       if (unlikely (cache->ebl == NULL))
445 	cache->ebl = (void *) -1l;
446     }
447 
448   /* Fetch the ABI's default CFI program.  */
449   if (likely (cache->ebl != (void *) -1l)
450       && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
451     return DWARF_E_UNKNOWN_ERROR;
452 
453   Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
454   if (unlikely (cie_fs == NULL))
455     return DWARF_E_NOMEM;
456 
457   /* If the default state of any register is not "undefined"
458      (i.e. call-clobbered), then the backend supplies instructions
459      for the standard initial state.  */
460   if (abi_info.initial_instructions_end > abi_info.initial_instructions)
461     {
462       /* Dummy CIE for backend's instructions.  */
463       struct dwarf_cie abi_cie =
464 	{
465 	  .code_alignment_factor = abi_info.code_alignment_factor,
466 	  .data_alignment_factor = abi_info.data_alignment_factor,
467 	};
468       result = execute_cfi (cache, &abi_cie, &cie_fs,
469 			    abi_info.initial_instructions,
470 			    abi_info.initial_instructions_end, true,
471 			    0, (Dwarf_Addr) -1l);
472     }
473 
474   /* Now run the CIE's initial instructions.  */
475   if (cie->initial_instructions_end > cie->initial_instructions
476       && likely (result == DWARF_E_NOERROR))
477     result = execute_cfi (cache, cie, &cie_fs,
478 			  cie->initial_instructions,
479 			  cie->initial_instructions_end, false,
480 			  0, (Dwarf_Addr) -1l);
481 
482   if (likely (result == DWARF_E_NOERROR))
483     {
484       /* Now we have the initial state of things that all
485 	 FDEs using this CIE will start from.  */
486       cie_fs->cache = cache;
487       cie->initial_state = cie_fs;
488     }
489 
490   return result;
491 }
492 
493 int
494 internal_function
__libdw_frame_at_address(Dwarf_CFI * cache,struct dwarf_fde * fde,Dwarf_Addr address,Dwarf_Frame ** frame)495 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
496 			  Dwarf_Addr address, Dwarf_Frame **frame)
497 {
498   int result = cie_cache_initial_state (cache, fde->cie);
499   if (likely (result == DWARF_E_NOERROR))
500     {
501       Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
502       if (unlikely (fs == NULL))
503 	return DWARF_E_NOMEM;
504 
505       fs->fde = fde;
506       fs->start = fde->start;
507       fs->end = fde->end;
508 
509       result = execute_cfi (cache, fde->cie, &fs,
510 			    fde->instructions, fde->instructions_end, false,
511 			    fde->start, address);
512       if (likely (result == DWARF_E_NOERROR))
513 	*frame = fs;
514     }
515   return result;
516 }
517