16cebd083f27326f72a028979c11a416c89dd604
[platform/upstream/elfutils.git] / libdwfl / frame_unwind.c
1 /* Get previous frame state for an existing frame state.
2    Copyright (C) 2013, 2014 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 "cfi.h"
34 #include <stdlib.h>
35 #include "libdwflP.h"
36 #include "../libdw/dwarf.h"
37 #include <sys/ptrace.h>
38
39 /* Maximum number of DWARF expression stack slots before returning an error.  */
40 #define DWARF_EXPR_STACK_MAX 0x100
41
42 /* Maximum number of DWARF expression executed operations before returning an
43    error.  */
44 #define DWARF_EXPR_STEPS_MAX 0x1000
45
46 #ifndef MAX
47 # define MAX(a, b) ((a) > (b) ? (a) : (b))
48 #endif
49
50 bool
51 internal_function
52 __libdwfl_frame_reg_get (Dwfl_Frame *state, unsigned regno, Dwarf_Addr *val)
53 {
54   Ebl *ebl = state->thread->process->ebl;
55   if (! ebl_dwarf_to_regno (ebl, &regno))
56     return false;
57   if (regno >= ebl_frame_nregs (ebl))
58     return false;
59   if ((state->regs_set[regno / sizeof (*state->regs_set) / 8]
60        & ((uint64_t) 1U << (regno % (sizeof (*state->regs_set) * 8)))) == 0)
61     return false;
62   if (val)
63     *val = state->regs[regno];
64   return true;
65 }
66
67 bool
68 internal_function
69 __libdwfl_frame_reg_set (Dwfl_Frame *state, unsigned regno, Dwarf_Addr val)
70 {
71   Ebl *ebl = state->thread->process->ebl;
72   if (! ebl_dwarf_to_regno (ebl, &regno))
73     return false;
74   if (regno >= ebl_frame_nregs (ebl))
75     return false;
76   /* For example i386 user_regs_struct has signed fields.  */
77   if (ebl_get_elfclass (ebl) == ELFCLASS32)
78     val &= 0xffffffff;
79   state->regs_set[regno / sizeof (*state->regs_set) / 8] |=
80                 ((uint64_t) 1U << (regno % (sizeof (*state->regs_set) * 8)));
81   state->regs[regno] = val;
82   return true;
83 }
84
85 static bool
86 state_get_reg (Dwfl_Frame *state, unsigned regno, Dwarf_Addr *val)
87 {
88   if (! __libdwfl_frame_reg_get (state, regno, val))
89     {
90       __libdwfl_seterrno (DWFL_E_INVALID_REGISTER);
91       return false;
92     }
93   return true;
94 }
95
96 static int
97 bra_compar (const void *key_voidp, const void *elem_voidp)
98 {
99   Dwarf_Word offset = (uintptr_t) key_voidp;
100   const Dwarf_Op *op = elem_voidp;
101   return (offset > op->offset) - (offset < op->offset);
102 }
103
104 /* If FRAME is NULL is are computing CFI frame base.  In such case another
105    DW_OP_call_frame_cfa is no longer permitted.  */
106
107 static bool
108 expr_eval (Dwfl_Frame *state, Dwarf_Frame *frame, const Dwarf_Op *ops,
109            size_t nops, Dwarf_Addr *result, Dwarf_Addr bias)
110 {
111   Dwfl_Process *process = state->thread->process;
112   if (nops == 0)
113     {
114       __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
115       return false;
116     }
117   Dwarf_Addr *stack = NULL;
118   size_t stack_used = 0, stack_allocated = 0;
119
120   bool
121   push (Dwarf_Addr val)
122   {
123     if (stack_used >= DWARF_EXPR_STACK_MAX)
124       {
125         __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
126         return false;
127       }
128     if (stack_used == stack_allocated)
129       {
130         stack_allocated = MAX (stack_allocated * 2, 32);
131         Dwarf_Addr *stack_new = realloc (stack, stack_allocated * sizeof (*stack));
132         if (stack_new == NULL)
133           {
134             __libdwfl_seterrno (DWFL_E_NOMEM);
135             return false;
136           }
137         stack = stack_new;
138       }
139     stack[stack_used++] = val;
140     return true;
141   }
142
143   bool
144   pop (Dwarf_Addr *val)
145   {
146     if (stack_used == 0)
147       {
148         __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
149         return false;
150       }
151     *val = stack[--stack_used];
152     return true;
153   }
154
155   Dwarf_Addr val1, val2;
156   bool is_location = false;
157   size_t steps_count = 0;
158   for (const Dwarf_Op *op = ops; op < ops + nops; op++)
159     {
160       if (++steps_count > DWARF_EXPR_STEPS_MAX)
161         {
162           __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
163           return false;
164         }
165       switch (op->atom)
166       {
167         /* DW_OP_* order matches libgcc/unwind-dw2.c execute_stack_op:  */
168         case DW_OP_lit0 ... DW_OP_lit31:
169           if (! push (op->atom - DW_OP_lit0))
170             {
171               free (stack);
172               return false;
173             }
174           break;
175         case DW_OP_addr:
176           if (! push (op->number + bias))
177             {
178               free (stack);
179               return false;
180             }
181           break;
182         case DW_OP_GNU_encoded_addr:
183           /* Missing support in the rest of elfutils.  */
184           __libdwfl_seterrno (DWFL_E_UNSUPPORTED_DWARF);
185           return false;
186         case DW_OP_const1u:
187         case DW_OP_const1s:
188         case DW_OP_const2u:
189         case DW_OP_const2s:
190         case DW_OP_const4u:
191         case DW_OP_const4s:
192         case DW_OP_const8u:
193         case DW_OP_const8s:
194         case DW_OP_constu:
195         case DW_OP_consts:
196           if (! push (op->number))
197             {
198               free (stack);
199               return false;
200             }
201           break;
202         case DW_OP_reg0 ... DW_OP_reg31:
203           if (! state_get_reg (state, op->atom - DW_OP_reg0, &val1)
204               || ! push (val1))
205             {
206               free (stack);
207               return false;
208             }
209           break;
210         case DW_OP_regx:
211           if (! state_get_reg (state, op->number, &val1) || ! push (val1))
212             {
213               free (stack);
214               return false;
215             }
216           break;
217         case DW_OP_breg0 ... DW_OP_breg31:
218           if (! state_get_reg (state, op->atom - DW_OP_breg0, &val1))
219             {
220               free (stack);
221               return false;
222             }
223           val1 += op->number;
224           if (! push (val1))
225             {
226               free (stack);
227               return false;
228             }
229           break;
230         case DW_OP_bregx:
231           if (! state_get_reg (state, op->number, &val1))
232             {
233               free (stack);
234               return false;
235             }
236           val1 += op->number2;
237           if (! push (val1))
238             {
239               free (stack);
240               return false;
241             }
242           break;
243         case DW_OP_dup:
244           if (! pop (&val1) || ! push (val1) || ! push (val1))
245             {
246               free (stack);
247               return false;
248             }
249           break;
250         case DW_OP_drop:
251           if (! pop (&val1))
252             {
253               free (stack);
254               return false;
255             }
256           break;
257         case DW_OP_pick:
258           if (stack_used <= op->number)
259             {
260               free (stack);
261               __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
262               return false;
263             }
264           if (! push (stack[stack_used - 1 - op->number]))
265             {
266               free (stack);
267               return false;
268             }
269           break;
270         case DW_OP_over:
271           if (! pop (&val1) || ! pop (&val2)
272               || ! push (val2) || ! push (val1) || ! push (val2))
273             {
274               free (stack);
275               return false;
276             }
277           break;
278         case DW_OP_swap:
279           if (! pop (&val1) || ! pop (&val2) || ! push (val1) || ! push (val2))
280             {
281               free (stack);
282               return false;
283             }
284           break;
285         case DW_OP_rot:
286           {
287             Dwarf_Addr val3;
288             if (! pop (&val1) || ! pop (&val2) || ! pop (&val3)
289                 || ! push (val1) || ! push (val3) || ! push (val2))
290               {
291                 free (stack);
292                 return false;
293               }
294           }
295           break;
296         case DW_OP_deref:
297         case DW_OP_deref_size:
298           if (process->callbacks->memory_read == NULL)
299             {
300               free (stack);
301               __libdwfl_seterrno (DWFL_E_INVALID_ARGUMENT);
302               return false;
303             }
304           if (! pop (&val1)
305               || ! process->callbacks->memory_read (process->dwfl, val1, &val1,
306                                                     process->callbacks_arg))
307             {
308               free (stack);
309               return false;
310             }
311           if (op->atom == DW_OP_deref_size)
312             {
313               const int elfclass = frame->cache->e_ident[EI_CLASS];
314               const unsigned addr_bytes = elfclass == ELFCLASS32 ? 4 : 8;
315               if (op->number > addr_bytes)
316                 {
317                   free (stack);
318                   __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
319                   return false;
320                 }
321 #if BYTE_ORDER == BIG_ENDIAN
322               if (op->number == 0)
323                 val1 = 0;
324               else
325                 val1 >>= (addr_bytes - op->number) * 8;
326 #else
327               if (op->number < 8)
328                 val1 &= (1 << (op->number * 8)) - 1;
329 #endif
330             }
331           if (! push (val1))
332             {
333               free (stack);
334               return false;
335             }
336           break;
337 #define UNOP(atom, expr)                                                \
338         case atom:                                                      \
339           if (! pop (&val1) || ! push (expr))                           \
340             {                                                           \
341               free (stack);                                             \
342               return false;                                             \
343             }                                                           \
344           break;
345         UNOP (DW_OP_abs, abs ((int64_t) val1))
346         UNOP (DW_OP_neg, -(int64_t) val1)
347         UNOP (DW_OP_not, ~val1)
348 #undef UNOP
349         case DW_OP_plus_uconst:
350           if (! pop (&val1) || ! push (val1 + op->number))
351             {
352               free (stack);
353               return false;
354             }
355           break;
356 #define BINOP(atom, op)                                                 \
357         case atom:                                                      \
358           if (! pop (&val2) || ! pop (&val1) || ! push (val1 op val2))  \
359             {                                                           \
360               free (stack);                                             \
361               return false;                                             \
362             }                                                           \
363           break;
364 #define BINOP_SIGNED(atom, op)                                          \
365         case atom:                                                      \
366           if (! pop (&val2) || ! pop (&val1)                            \
367               || ! push ((int64_t) val1 op (int64_t) val2))             \
368             {                                                           \
369               free (stack);                                             \
370               return false;                                             \
371             }                                                           \
372           break;
373         BINOP (DW_OP_and, &)
374         case DW_OP_div:
375           if (! pop (&val2) || ! pop (&val1))
376             {
377               free (stack);
378               return false;
379             }
380           if (val2 == 0)
381             {
382               free (stack);
383               __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
384               return false;
385             }
386           if (! push ((int64_t) val1 / (int64_t) val2))
387             {
388               free (stack);
389               return false;
390             }
391           break;
392         BINOP (DW_OP_minus, -)
393         case DW_OP_mod:
394           if (! pop (&val2) || ! pop (&val1))
395             {
396               free (stack);
397               return false;
398             }
399           if (val2 == 0)
400             {
401               free (stack);
402               __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
403               return false;
404             }
405           if (! push (val1 % val2))
406             {
407               free (stack);
408               return false;
409             }
410           break;
411         BINOP (DW_OP_mul, *)
412         BINOP (DW_OP_or, |)
413         BINOP (DW_OP_plus, +)
414         BINOP (DW_OP_shl, <<)
415         BINOP (DW_OP_shr, >>)
416         BINOP_SIGNED (DW_OP_shra, >>)
417         BINOP (DW_OP_xor, ^)
418         BINOP_SIGNED (DW_OP_le, <=)
419         BINOP_SIGNED (DW_OP_ge, >=)
420         BINOP_SIGNED (DW_OP_eq, ==)
421         BINOP_SIGNED (DW_OP_lt, <)
422         BINOP_SIGNED (DW_OP_gt, >)
423         BINOP_SIGNED (DW_OP_ne, !=)
424 #undef BINOP
425 #undef BINOP_SIGNED
426         case DW_OP_bra:
427           if (! pop (&val1))
428             {
429               free (stack);
430               return false;
431             }
432           if (val1 == 0)
433             break;
434           /* FALLTHRU */
435         case DW_OP_skip:;
436           Dwarf_Word offset = op->offset + 1 + 2 + (int16_t) op->number;
437           const Dwarf_Op *found = bsearch ((void *) (uintptr_t) offset, ops, nops,
438                                            sizeof (*ops), bra_compar);
439           if (found == NULL)
440             {
441               free (stack);
442               /* PPC32 vDSO has such invalid operations.  */
443               __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
444               return false;
445             }
446           /* Undo the 'for' statement increment.  */
447           op = found - 1;
448           break;
449         case DW_OP_nop:
450           break;
451         /* DW_OP_* not listed in libgcc/unwind-dw2.c execute_stack_op:  */
452         case DW_OP_call_frame_cfa:;
453           // Not used by CFI itself but it is synthetized by elfutils internation.
454           Dwarf_Op *cfa_ops;
455           size_t cfa_nops;
456           Dwarf_Addr cfa;
457           if (frame == NULL
458               || dwarf_frame_cfa (frame, &cfa_ops, &cfa_nops) != 0
459               || ! expr_eval (state, NULL, cfa_ops, cfa_nops, &cfa, bias)
460               || ! push (cfa))
461             {
462               __libdwfl_seterrno (DWFL_E_LIBDW);
463               free (stack);
464               return false;
465             }
466           is_location = true;
467           break;
468         case DW_OP_stack_value:
469           // Not used by CFI itself but it is synthetized by elfutils internation.
470           is_location = false;
471           break;
472         default:
473           __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
474           return false;
475       }
476     }
477   if (! pop (result))
478     {
479       free (stack);
480       return false;
481     }
482   free (stack);
483   if (is_location)
484     {
485       if (process->callbacks->memory_read == NULL)
486         {
487           __libdwfl_seterrno (DWFL_E_INVALID_ARGUMENT);
488           return false;
489         }
490       if (! process->callbacks->memory_read (process->dwfl, *result, result,
491                                              process->callbacks_arg))
492         return false;
493     }
494   return true;
495 }
496
497 static void
498 new_unwound (Dwfl_Frame *state)
499 {
500   assert (state->unwound == NULL);
501   Dwfl_Thread *thread = state->thread;
502   Dwfl_Process *process = thread->process;
503   Ebl *ebl = process->ebl;
504   size_t nregs = ebl_frame_nregs (ebl);
505   assert (nregs > 0);
506   Dwfl_Frame *unwound;
507   unwound = malloc (sizeof (*unwound) + sizeof (*unwound->regs) * nregs);
508   state->unwound = unwound;
509   unwound->thread = thread;
510   unwound->unwound = NULL;
511   unwound->signal_frame = false;
512   unwound->initial_frame = false;
513   unwound->pc_state = DWFL_FRAME_STATE_ERROR;
514   memset (unwound->regs_set, 0, sizeof (unwound->regs_set));
515 }
516
517 /* The logic is to call __libdwfl_seterrno for any CFI bytecode interpretation
518    error so one can easily catch the problem with a debugger.  Still there are
519    archs with invalid CFI for some registers where the registers are never used
520    later.  Therefore we continue unwinding leaving the registers undefined.  */
521
522 static void
523 handle_cfi (Dwfl_Frame *state, Dwarf_Addr pc, Dwarf_CFI *cfi, Dwarf_Addr bias)
524 {
525   Dwarf_Frame *frame;
526   if (INTUSE(dwarf_cfi_addrframe) (cfi, pc, &frame) != 0)
527     {
528       __libdwfl_seterrno (DWFL_E_LIBDW);
529       return;
530     }
531   new_unwound (state);
532   Dwfl_Frame *unwound = state->unwound;
533   unwound->signal_frame = frame->fde->cie->signal_frame;
534   Dwfl_Thread *thread = state->thread;
535   Dwfl_Process *process = thread->process;
536   Ebl *ebl = process->ebl;
537   size_t nregs = ebl_frame_nregs (ebl);
538   assert (nregs > 0);
539
540   /* The return register is special for setting the unwound->pc_state.  */
541   unsigned ra = frame->fde->cie->return_address_register;
542   bool ra_set = false;
543   ebl_dwarf_to_regno (ebl, &ra);
544
545   for (unsigned regno = 0; regno < nregs; regno++)
546     {
547       Dwarf_Op reg_ops_mem[3], *reg_ops;
548       size_t reg_nops;
549       if (dwarf_frame_register (frame, regno, reg_ops_mem, &reg_ops,
550                                 &reg_nops) != 0)
551         {
552           __libdwfl_seterrno (DWFL_E_LIBDW);
553           continue;
554         }
555       Dwarf_Addr regval;
556       if (reg_nops == 0)
557         {
558           if (reg_ops == reg_ops_mem)
559             {
560               /* REGNO is undefined.  */
561               if (regno == ra)
562                 unwound->pc_state = DWFL_FRAME_STATE_PC_UNDEFINED;
563               continue;
564             }
565           else if (reg_ops == NULL)
566             {
567               /* REGNO is same-value.  */
568               if (! state_get_reg (state, regno, &regval))
569                 continue;
570             }
571           else
572             {
573               __libdwfl_seterrno (DWFL_E_INVALID_DWARF);
574               continue;
575             }
576         }
577       else if (! expr_eval (state, frame, reg_ops, reg_nops, &regval, bias))
578         {
579           /* PPC32 vDSO has various invalid operations, ignore them.  The
580              register will look as unset causing an error later, if used.
581              But PPC32 does not use such registers.  */
582           continue;
583         }
584
585       /* Some architectures encode some extra info in the return address.  */
586       if (regno == frame->fde->cie->return_address_register)
587         regval &= ebl_func_addr_mask (ebl);
588
589       /* This is another strange PPC[64] case.  There are two
590          registers numbers that can represent the same DWARF return
591          register number.  We only want one to actually set the return
592          register value.  But we always want to override the value if
593          the register is the actual CIE return address register.  */
594       if (ra_set && regno != frame->fde->cie->return_address_register)
595         {
596           unsigned r = regno;
597           if (ebl_dwarf_to_regno (ebl, &r) && r == ra)
598             continue;
599         }
600
601       if (! __libdwfl_frame_reg_set (unwound, regno, regval))
602         {
603           __libdwfl_seterrno (DWFL_E_INVALID_REGISTER);
604           continue;
605         }
606       else if (! ra_set)
607         {
608           unsigned r = regno;
609           if (ebl_dwarf_to_regno (ebl, &r) && r == ra)
610             ra_set = true;
611         }
612     }
613   if (unwound->pc_state == DWFL_FRAME_STATE_ERROR
614       && __libdwfl_frame_reg_get (unwound,
615                                   frame->fde->cie->return_address_register,
616                                   &unwound->pc))
617     {
618       /* PPC32 __libc_start_main properly CFI-unwinds PC as zero.  Currently
619          none of the archs supported for unwinding have zero as a valid PC.  */
620       if (unwound->pc == 0)
621         unwound->pc_state = DWFL_FRAME_STATE_PC_UNDEFINED;
622       else
623         unwound->pc_state = DWFL_FRAME_STATE_PC_SET;
624     }
625   free (frame);
626 }
627
628 static bool
629 setfunc (int firstreg, unsigned nregs, const Dwarf_Word *regs, void *arg)
630 {
631   Dwfl_Frame *state = arg;
632   Dwfl_Frame *unwound = state->unwound;
633   if (firstreg < 0)
634     {
635       assert (firstreg == -1);
636       assert (nregs == 1);
637       assert (unwound->pc_state == DWFL_FRAME_STATE_PC_UNDEFINED);
638       unwound->pc = *regs;
639       unwound->pc_state = DWFL_FRAME_STATE_PC_SET;
640       return true;
641     }
642   while (nregs--)
643     if (! __libdwfl_frame_reg_set (unwound, firstreg++, *regs++))
644       return false;
645   return true;
646 }
647
648 static bool
649 getfunc (int firstreg, unsigned nregs, Dwarf_Word *regs, void *arg)
650 {
651   Dwfl_Frame *state = arg;
652   assert (firstreg >= 0);
653   while (nregs--)
654     if (! __libdwfl_frame_reg_get (state, firstreg++, regs++))
655       return false;
656   return true;
657 }
658
659 static bool
660 readfunc (Dwarf_Addr addr, Dwarf_Word *datap, void *arg)
661 {
662   Dwfl_Frame *state = arg;
663   Dwfl_Thread *thread = state->thread;
664   Dwfl_Process *process = thread->process;
665   return process->callbacks->memory_read (process->dwfl, addr, datap,
666                                           process->callbacks_arg);
667 }
668
669 void
670 internal_function
671 __libdwfl_frame_unwind (Dwfl_Frame *state)
672 {
673   if (state->unwound)
674     return;
675   /* Do not ask dwfl_frame_pc for ISACTIVATION, it would try to unwind STATE
676      which would deadlock us.  */
677   Dwarf_Addr pc;
678   bool ok = INTUSE(dwfl_frame_pc) (state, &pc, NULL);
679   assert (ok);
680   /* Check whether this is the initial frame or a signal frame.
681      Then we need to unwind from the original, unadjusted PC.  */
682   if (! state->initial_frame && ! state->signal_frame)
683     pc--;
684   Dwfl_Module *mod = INTUSE(dwfl_addrmodule) (state->thread->process->dwfl, pc);
685   if (mod == NULL)
686     __libdwfl_seterrno (DWFL_E_NO_DWARF);
687   else
688     {
689       Dwarf_Addr bias;
690       Dwarf_CFI *cfi_eh = INTUSE(dwfl_module_eh_cfi) (mod, &bias);
691       if (cfi_eh)
692         {
693           handle_cfi (state, pc - bias, cfi_eh, bias);
694           if (state->unwound)
695             return;
696         }
697       Dwarf_CFI *cfi_dwarf = INTUSE(dwfl_module_dwarf_cfi) (mod, &bias);
698       if (cfi_dwarf)
699         {
700           handle_cfi (state, pc - bias, cfi_dwarf, bias);
701           if (state->unwound)
702             return;
703         }
704     }
705   assert (state->unwound == NULL);
706   Dwfl_Thread *thread = state->thread;
707   Dwfl_Process *process = thread->process;
708   Ebl *ebl = process->ebl;
709   new_unwound (state);
710   state->unwound->pc_state = DWFL_FRAME_STATE_PC_UNDEFINED;
711   // &Dwfl_Frame.signal_frame cannot be passed as it is a bitfield.
712   bool signal_frame = false;
713   if (! ebl_unwind (ebl, pc, setfunc, getfunc, readfunc, state, &signal_frame))
714     {
715       // Discard the unwind attempt.  During next __libdwfl_frame_unwind call
716       // we may have for example the appropriate Dwfl_Module already mapped.
717       assert (state->unwound->unwound == NULL);
718       free (state->unwound);
719       state->unwound = NULL;
720       // __libdwfl_seterrno has been called above.
721       return;
722     }
723   assert (state->unwound->pc_state == DWFL_FRAME_STATE_PC_SET);
724   state->unwound->signal_frame = signal_frame;
725 }