2 * Copyright (C) 2009 Matt Fleming <matt@console-pimps.org>
4 * This file is subject to the terms and conditions of the GNU General Public
5 * License. See the file "COPYING" in the main directory of this archive
8 * This is an implementation of a DWARF unwinder. Its main purpose is
9 * for generating stacktrace information. Based on the DWARF 3
10 * specification from http://www.dwarfstd.org.
13 * - DWARF64 doesn't work.
17 #include <linux/kernel.h>
19 #include <linux/list.h>
20 #include <linux/mempool.h>
22 #include <asm/dwarf.h>
23 #include <asm/unwinder.h>
24 #include <asm/sections.h>
25 #include <asm/unaligned.h>
26 #include <asm/dwarf.h>
27 #include <asm/stacktrace.h>
29 /* Reserve enough memory for two stack frames */
30 #define DWARF_FRAME_MIN_REQ 2
31 /* ... with 4 registers per frame. */
32 #define DWARF_REG_MIN_REQ (DWARF_FRAME_MIN_REQ * 4)
34 static struct kmem_cache
*dwarf_frame_cachep
;
35 static mempool_t
*dwarf_frame_pool
;
37 static struct kmem_cache
*dwarf_reg_cachep
;
38 static mempool_t
*dwarf_reg_pool
;
40 static LIST_HEAD(dwarf_cie_list
);
41 static DEFINE_SPINLOCK(dwarf_cie_lock
);
43 static LIST_HEAD(dwarf_fde_list
);
44 static DEFINE_SPINLOCK(dwarf_fde_lock
);
46 static struct dwarf_cie
*cached_cie
;
49 * dwarf_frame_alloc_reg - allocate memory for a DWARF register
50 * @frame: the DWARF frame whose list of registers we insert on
51 * @reg_num: the register number
53 * Allocate space for, and initialise, a dwarf reg from
54 * dwarf_reg_pool and insert it onto the (unsorted) linked-list of
55 * dwarf registers for @frame.
57 * Return the initialised DWARF reg.
59 static struct dwarf_reg
*dwarf_frame_alloc_reg(struct dwarf_frame
*frame
,
62 struct dwarf_reg
*reg
;
64 reg
= mempool_alloc(dwarf_reg_pool
, GFP_ATOMIC
);
66 printk(KERN_WARNING
"Unable to allocate a DWARF register\n");
68 * Let's just bomb hard here, we have no way to
74 reg
->number
= reg_num
;
78 list_add(®
->link
, &frame
->reg_list
);
83 static void dwarf_frame_free_regs(struct dwarf_frame
*frame
)
85 struct dwarf_reg
*reg
, *n
;
87 list_for_each_entry_safe(reg
, n
, &frame
->reg_list
, link
) {
89 mempool_free(reg
, dwarf_reg_pool
);
94 * dwarf_frame_reg - return a DWARF register
95 * @frame: the DWARF frame to search in for @reg_num
96 * @reg_num: the register number to search for
98 * Lookup and return the dwarf reg @reg_num for this frame. Return
99 * NULL if @reg_num is an register invalid number.
101 static struct dwarf_reg
*dwarf_frame_reg(struct dwarf_frame
*frame
,
102 unsigned int reg_num
)
104 struct dwarf_reg
*reg
;
106 list_for_each_entry(reg
, &frame
->reg_list
, link
) {
107 if (reg
->number
== reg_num
)
115 * dwarf_read_addr - read dwarf data
116 * @src: source address of data
117 * @dst: destination address to store the data to
119 * Read 'n' bytes from @src, where 'n' is the size of an address on
120 * the native machine. We return the number of bytes read, which
121 * should always be 'n'. We also have to be careful when reading
122 * from @src and writing to @dst, because they can be arbitrarily
123 * aligned. Return 'n' - the number of bytes read.
125 static inline int dwarf_read_addr(unsigned long *src
, unsigned long *dst
)
127 u32 val
= get_unaligned(src
);
128 put_unaligned(val
, dst
);
129 return sizeof(unsigned long *);
133 * dwarf_read_uleb128 - read unsigned LEB128 data
134 * @addr: the address where the ULEB128 data is stored
135 * @ret: address to store the result
137 * Decode an unsigned LEB128 encoded datum. The algorithm is taken
138 * from Appendix C of the DWARF 3 spec. For information on the
139 * encodings refer to section "7.6 - Variable Length Data". Return
140 * the number of bytes read.
142 static inline unsigned long dwarf_read_uleb128(char *addr
, unsigned int *ret
)
153 byte
= __raw_readb(addr
);
157 result
|= (byte
& 0x7f) << shift
;
170 * dwarf_read_leb128 - read signed LEB128 data
171 * @addr: the address of the LEB128 encoded data
172 * @ret: address to store the result
174 * Decode signed LEB128 data. The algorithm is taken from Appendix
175 * C of the DWARF 3 spec. Return the number of bytes read.
177 static inline unsigned long dwarf_read_leb128(char *addr
, int *ret
)
189 byte
= __raw_readb(addr
);
191 result
|= (byte
& 0x7f) << shift
;
199 /* The number of bits in a signed integer. */
200 num_bits
= 8 * sizeof(result
);
202 if ((shift
< num_bits
) && (byte
& 0x40))
203 result
|= (-1 << shift
);
211 * dwarf_read_encoded_value - return the decoded value at @addr
212 * @addr: the address of the encoded value
213 * @val: where to write the decoded value
214 * @encoding: the encoding with which we can decode @addr
216 * GCC emits encoded address in the .eh_frame FDE entries. Decode
217 * the value at @addr using @encoding. The decoded value is written
218 * to @val and the number of bytes read is returned.
220 static int dwarf_read_encoded_value(char *addr
, unsigned long *val
,
223 unsigned long decoded_addr
= 0;
226 switch (encoding
& 0x70) {
227 case DW_EH_PE_absptr
:
230 decoded_addr
= (unsigned long)addr
;
233 pr_debug("encoding=0x%x\n", (encoding
& 0x70));
237 if ((encoding
& 0x07) == 0x00)
238 encoding
|= DW_EH_PE_udata4
;
240 switch (encoding
& 0x0f) {
241 case DW_EH_PE_sdata4
:
242 case DW_EH_PE_udata4
:
244 decoded_addr
+= get_unaligned((u32
*)addr
);
245 __raw_writel(decoded_addr
, val
);
248 pr_debug("encoding=0x%x\n", encoding
);
256 * dwarf_entry_len - return the length of an FDE or CIE
257 * @addr: the address of the entry
258 * @len: the length of the entry
260 * Read the initial_length field of the entry and store the size of
261 * the entry in @len. We return the number of bytes read. Return a
262 * count of 0 on error.
264 static inline int dwarf_entry_len(char *addr
, unsigned long *len
)
269 initial_len
= get_unaligned((u32
*)addr
);
273 * An initial length field value in the range DW_LEN_EXT_LO -
274 * DW_LEN_EXT_HI indicates an extension, and should not be
275 * interpreted as a length. The only extension that we currently
276 * understand is the use of DWARF64 addresses.
278 if (initial_len
>= DW_EXT_LO
&& initial_len
<= DW_EXT_HI
) {
280 * The 64-bit length field immediately follows the
281 * compulsory 32-bit length field.
283 if (initial_len
== DW_EXT_DWARF64
) {
284 *len
= get_unaligned((u64
*)addr
+ 4);
287 printk(KERN_WARNING
"Unknown DWARF extension\n");
297 * dwarf_lookup_cie - locate the cie
298 * @cie_ptr: pointer to help with lookup
300 static struct dwarf_cie
*dwarf_lookup_cie(unsigned long cie_ptr
)
302 struct dwarf_cie
*cie
;
305 spin_lock_irqsave(&dwarf_cie_lock
, flags
);
308 * We've cached the last CIE we looked up because chances are
309 * that the FDE wants this CIE.
311 if (cached_cie
&& cached_cie
->cie_pointer
== cie_ptr
) {
316 list_for_each_entry(cie
, &dwarf_cie_list
, link
) {
317 if (cie
->cie_pointer
== cie_ptr
) {
323 /* Couldn't find the entry in the list. */
324 if (&cie
->link
== &dwarf_cie_list
)
327 spin_unlock_irqrestore(&dwarf_cie_lock
, flags
);
332 * dwarf_lookup_fde - locate the FDE that covers pc
333 * @pc: the program counter
335 struct dwarf_fde
*dwarf_lookup_fde(unsigned long pc
)
337 struct dwarf_fde
*fde
;
340 spin_lock_irqsave(&dwarf_fde_lock
, flags
);
342 list_for_each_entry(fde
, &dwarf_fde_list
, link
) {
343 unsigned long start
, end
;
345 start
= fde
->initial_location
;
346 end
= fde
->initial_location
+ fde
->address_range
;
348 if (pc
>= start
&& pc
< end
)
352 /* Couldn't find the entry in the list. */
353 if (&fde
->link
== &dwarf_fde_list
)
356 spin_unlock_irqrestore(&dwarf_fde_lock
, flags
);
362 * dwarf_cfa_execute_insns - execute instructions to calculate a CFA
363 * @insn_start: address of the first instruction
364 * @insn_end: address of the last instruction
365 * @cie: the CIE for this function
366 * @fde: the FDE for this function
367 * @frame: the instructions calculate the CFA for this frame
368 * @pc: the program counter of the address we're interested in
370 * Execute the Call Frame instruction sequence starting at
371 * @insn_start and ending at @insn_end. The instructions describe
372 * how to calculate the Canonical Frame Address of a stackframe.
373 * Store the results in @frame.
375 static int dwarf_cfa_execute_insns(unsigned char *insn_start
,
376 unsigned char *insn_end
,
377 struct dwarf_cie
*cie
,
378 struct dwarf_fde
*fde
,
379 struct dwarf_frame
*frame
,
383 unsigned char *current_insn
;
384 unsigned int count
, delta
, reg
, expr_len
, offset
;
385 struct dwarf_reg
*regp
;
387 current_insn
= insn_start
;
389 while (current_insn
< insn_end
&& frame
->pc
<= pc
) {
390 insn
= __raw_readb(current_insn
++);
393 * Firstly, handle the opcodes that embed their operands
394 * in the instructions.
396 switch (DW_CFA_opcode(insn
)) {
397 case DW_CFA_advance_loc
:
398 delta
= DW_CFA_operand(insn
);
399 delta
*= cie
->code_alignment_factor
;
404 reg
= DW_CFA_operand(insn
);
405 count
= dwarf_read_uleb128(current_insn
, &offset
);
406 current_insn
+= count
;
407 offset
*= cie
->data_alignment_factor
;
408 regp
= dwarf_frame_alloc_reg(frame
, reg
);
410 regp
->flags
|= DWARF_REG_OFFSET
;
414 reg
= DW_CFA_operand(insn
);
420 * Secondly, handle the opcodes that don't embed their
421 * operands in the instruction.
426 case DW_CFA_advance_loc1
:
427 delta
= *current_insn
++;
428 frame
->pc
+= delta
* cie
->code_alignment_factor
;
430 case DW_CFA_advance_loc2
:
431 delta
= get_unaligned((u16
*)current_insn
);
433 frame
->pc
+= delta
* cie
->code_alignment_factor
;
435 case DW_CFA_advance_loc4
:
436 delta
= get_unaligned((u32
*)current_insn
);
438 frame
->pc
+= delta
* cie
->code_alignment_factor
;
440 case DW_CFA_offset_extended
:
441 count
= dwarf_read_uleb128(current_insn
, ®
);
442 current_insn
+= count
;
443 count
= dwarf_read_uleb128(current_insn
, &offset
);
444 current_insn
+= count
;
445 offset
*= cie
->data_alignment_factor
;
447 case DW_CFA_restore_extended
:
448 count
= dwarf_read_uleb128(current_insn
, ®
);
449 current_insn
+= count
;
451 case DW_CFA_undefined
:
452 count
= dwarf_read_uleb128(current_insn
, ®
);
453 current_insn
+= count
;
456 count
= dwarf_read_uleb128(current_insn
,
457 &frame
->cfa_register
);
458 current_insn
+= count
;
459 count
= dwarf_read_uleb128(current_insn
,
461 current_insn
+= count
;
463 frame
->flags
|= DWARF_FRAME_CFA_REG_OFFSET
;
465 case DW_CFA_def_cfa_register
:
466 count
= dwarf_read_uleb128(current_insn
,
467 &frame
->cfa_register
);
468 current_insn
+= count
;
469 frame
->flags
|= DWARF_FRAME_CFA_REG_OFFSET
;
471 case DW_CFA_def_cfa_offset
:
472 count
= dwarf_read_uleb128(current_insn
, &offset
);
473 current_insn
+= count
;
474 frame
->cfa_offset
= offset
;
476 case DW_CFA_def_cfa_expression
:
477 count
= dwarf_read_uleb128(current_insn
, &expr_len
);
478 current_insn
+= count
;
480 frame
->cfa_expr
= current_insn
;
481 frame
->cfa_expr_len
= expr_len
;
482 current_insn
+= expr_len
;
484 frame
->flags
|= DWARF_FRAME_CFA_REG_EXP
;
486 case DW_CFA_offset_extended_sf
:
487 count
= dwarf_read_uleb128(current_insn
, ®
);
488 current_insn
+= count
;
489 count
= dwarf_read_leb128(current_insn
, &offset
);
490 current_insn
+= count
;
491 offset
*= cie
->data_alignment_factor
;
492 regp
= dwarf_frame_alloc_reg(frame
, reg
);
493 regp
->flags
|= DWARF_REG_OFFSET
;
496 case DW_CFA_val_offset
:
497 count
= dwarf_read_uleb128(current_insn
, ®
);
498 current_insn
+= count
;
499 count
= dwarf_read_leb128(current_insn
, &offset
);
500 offset
*= cie
->data_alignment_factor
;
501 regp
= dwarf_frame_alloc_reg(frame
, reg
);
502 regp
->flags
|= DWARF_REG_OFFSET
;
505 case DW_CFA_GNU_args_size
:
506 count
= dwarf_read_uleb128(current_insn
, &offset
);
507 current_insn
+= count
;
509 case DW_CFA_GNU_negative_offset_extended
:
510 count
= dwarf_read_uleb128(current_insn
, ®
);
511 current_insn
+= count
;
512 count
= dwarf_read_uleb128(current_insn
, &offset
);
513 offset
*= cie
->data_alignment_factor
;
515 regp
= dwarf_frame_alloc_reg(frame
, reg
);
516 regp
->flags
|= DWARF_REG_OFFSET
;
517 regp
->addr
= -offset
;
520 pr_debug("unhandled DWARF instruction 0x%x\n", insn
);
529 * dwarf_unwind_stack - recursively unwind the stack
530 * @pc: address of the function to unwind
531 * @prev: struct dwarf_frame of the previous stackframe on the callstack
533 * Return a struct dwarf_frame representing the most recent frame
534 * on the callstack. Each of the lower (older) stack frames are
535 * linked via the "prev" member.
537 struct dwarf_frame
*dwarf_unwind_stack(unsigned long pc
,
538 struct dwarf_frame
*prev
)
540 struct dwarf_frame
*frame
;
541 struct dwarf_cie
*cie
;
542 struct dwarf_fde
*fde
;
543 struct dwarf_reg
*reg
;
547 * If this is the first invocation of this recursive function we
548 * need get the contents of a physical register to get the CFA
549 * in order to begin the virtual unwinding of the stack.
551 * NOTE: the return address is guaranteed to be setup by the
552 * time this function makes its first function call.
555 pc
= (unsigned long)current_text_addr();
557 frame
= mempool_alloc(dwarf_frame_pool
, GFP_ATOMIC
);
559 printk(KERN_ERR
"Unable to allocate a dwarf frame\n");
563 INIT_LIST_HEAD(&frame
->reg_list
);
566 frame
->return_addr
= 0;
568 fde
= dwarf_lookup_fde(pc
);
571 * This is our normal exit path - the one that stops the
572 * recursion. There's two reasons why we might exit
575 * a) pc has no asscociated DWARF frame info and so
576 * we don't know how to unwind this frame. This is
577 * usually the case when we're trying to unwind a
578 * frame that was called from some assembly code
579 * that has no DWARF info, e.g. syscalls.
581 * b) the DEBUG info for pc is bogus. There's
582 * really no way to distinguish this case from the
583 * case above, which sucks because we could print a
589 cie
= dwarf_lookup_cie(fde
->cie_pointer
);
591 frame
->pc
= fde
->initial_location
;
593 /* CIE initial instructions */
594 dwarf_cfa_execute_insns(cie
->initial_instructions
,
595 cie
->instructions_end
, cie
, fde
,
598 /* FDE instructions */
599 dwarf_cfa_execute_insns(fde
->instructions
, fde
->end
, cie
,
602 /* Calculate the CFA */
603 switch (frame
->flags
) {
604 case DWARF_FRAME_CFA_REG_OFFSET
:
606 reg
= dwarf_frame_reg(prev
, frame
->cfa_register
);
609 addr
= prev
->cfa
+ reg
->addr
;
610 frame
->cfa
= __raw_readl(addr
);
614 * Again, this is the first invocation of this
615 * recurisve function. We need to physically
616 * read the contents of a register in order to
617 * get the Canonical Frame Address for this
620 frame
->cfa
= dwarf_read_arch_reg(frame
->cfa_register
);
623 frame
->cfa
+= frame
->cfa_offset
;
629 /* If we haven't seen the return address reg, we're screwed. */
630 reg
= dwarf_frame_reg(frame
, DWARF_ARCH_RA_REG
);
633 addr
= frame
->cfa
+ reg
->addr
;
634 frame
->return_addr
= __raw_readl(addr
);
639 dwarf_frame_free_regs(frame
);
640 mempool_free(frame
, dwarf_frame_pool
);
644 static int dwarf_parse_cie(void *entry
, void *p
, unsigned long len
,
647 struct dwarf_cie
*cie
;
651 cie
= kzalloc(sizeof(*cie
), GFP_KERNEL
);
658 * Record the offset into the .eh_frame section
659 * for this CIE. It allows this CIE to be
660 * quickly and easily looked up from the
663 cie
->cie_pointer
= (unsigned long)entry
;
665 cie
->version
= *(char *)p
++;
666 BUG_ON(cie
->version
!= 1);
668 cie
->augmentation
= p
;
669 p
+= strlen(cie
->augmentation
) + 1;
671 count
= dwarf_read_uleb128(p
, &cie
->code_alignment_factor
);
674 count
= dwarf_read_leb128(p
, &cie
->data_alignment_factor
);
678 * Which column in the rule table contains the
681 if (cie
->version
== 1) {
682 cie
->return_address_reg
= __raw_readb(p
);
685 count
= dwarf_read_uleb128(p
, &cie
->return_address_reg
);
689 if (cie
->augmentation
[0] == 'z') {
690 unsigned int length
, count
;
691 cie
->flags
|= DWARF_CIE_Z_AUGMENTATION
;
693 count
= dwarf_read_uleb128(p
, &length
);
696 BUG_ON((unsigned char *)p
> end
);
698 cie
->initial_instructions
= p
+ length
;
702 while (*cie
->augmentation
) {
704 * "L" indicates a byte showing how the
705 * LSDA pointer is encoded. Skip it.
707 if (*cie
->augmentation
== 'L') {
710 } else if (*cie
->augmentation
== 'R') {
712 * "R" indicates a byte showing
713 * how FDE addresses are
716 cie
->encoding
= *(char *)p
++;
718 } else if (*cie
->augmentation
== 'P') {
720 * "R" indicates a personality
725 } else if (*cie
->augmentation
== 'S') {
729 * Unknown augmentation. Assume
732 p
= cie
->initial_instructions
;
738 cie
->initial_instructions
= p
;
739 cie
->instructions_end
= end
;
742 spin_lock_irqsave(&dwarf_cie_lock
, flags
);
743 list_add_tail(&cie
->link
, &dwarf_cie_list
);
744 spin_unlock_irqrestore(&dwarf_cie_lock
, flags
);
749 static int dwarf_parse_fde(void *entry
, u32 entry_type
,
750 void *start
, unsigned long len
)
752 struct dwarf_fde
*fde
;
753 struct dwarf_cie
*cie
;
758 fde
= kzalloc(sizeof(*fde
), GFP_KERNEL
);
765 * In a .eh_frame section the CIE pointer is the
766 * delta between the address within the FDE
768 fde
->cie_pointer
= (unsigned long)(p
- entry_type
- 4);
770 cie
= dwarf_lookup_cie(fde
->cie_pointer
);
774 count
= dwarf_read_encoded_value(p
, &fde
->initial_location
,
777 count
= dwarf_read_addr(p
, &fde
->initial_location
);
782 count
= dwarf_read_encoded_value(p
, &fde
->address_range
,
783 cie
->encoding
& 0x0f);
785 count
= dwarf_read_addr(p
, &fde
->address_range
);
789 if (fde
->cie
->flags
& DWARF_CIE_Z_AUGMENTATION
) {
791 count
= dwarf_read_uleb128(p
, &length
);
795 /* Call frame instructions. */
796 fde
->instructions
= p
;
797 fde
->end
= start
+ len
;
800 spin_lock_irqsave(&dwarf_fde_lock
, flags
);
801 list_add_tail(&fde
->link
, &dwarf_fde_list
);
802 spin_unlock_irqrestore(&dwarf_fde_lock
, flags
);
807 static void dwarf_unwinder_dump(struct task_struct
*task
, struct pt_regs
*regs
,
809 const struct stacktrace_ops
*ops
, void *data
)
811 struct dwarf_frame
*frame
, *_frame
;
812 unsigned long return_addr
;
818 frame
= dwarf_unwind_stack(return_addr
, _frame
);
821 dwarf_frame_free_regs(_frame
);
822 mempool_free(_frame
, dwarf_frame_pool
);
827 if (!frame
|| !frame
->return_addr
)
830 return_addr
= frame
->return_addr
;
831 ops
->address(data
, return_addr
, 1);
836 static struct unwinder dwarf_unwinder
= {
837 .name
= "dwarf-unwinder",
838 .dump
= dwarf_unwinder_dump
,
842 static void dwarf_unwinder_cleanup(void)
844 struct dwarf_cie
*cie
;
845 struct dwarf_fde
*fde
;
848 * Deallocate all the memory allocated for the DWARF unwinder.
849 * Traverse all the FDE/CIE lists and remove and free all the
850 * memory associated with those data structures.
852 list_for_each_entry(cie
, &dwarf_cie_list
, link
)
855 list_for_each_entry(fde
, &dwarf_fde_list
, link
)
858 kmem_cache_destroy(dwarf_reg_cachep
);
859 kmem_cache_destroy(dwarf_frame_cachep
);
863 * dwarf_unwinder_init - initialise the dwarf unwinder
865 * Build the data structures describing the .dwarf_frame section to
866 * make it easier to lookup CIE and FDE entries. Because the
867 * .eh_frame section is packed as tightly as possible it is not
868 * easy to lookup the FDE for a given PC, so we build a list of FDE
869 * and CIE entries that make it easier.
871 static int __init
dwarf_unwinder_init(void)
877 unsigned int c_entries
, f_entries
;
879 INIT_LIST_HEAD(&dwarf_cie_list
);
880 INIT_LIST_HEAD(&dwarf_fde_list
);
884 entry
= &__start_eh_frame
;
886 dwarf_frame_cachep
= kmem_cache_create("dwarf_frames",
887 sizeof(struct dwarf_frame
), 0, SLAB_PANIC
, NULL
);
888 dwarf_reg_cachep
= kmem_cache_create("dwarf_regs",
889 sizeof(struct dwarf_reg
), 0, SLAB_PANIC
, NULL
);
891 dwarf_frame_pool
= mempool_create(DWARF_FRAME_MIN_REQ
,
896 dwarf_reg_pool
= mempool_create(DWARF_REG_MIN_REQ
,
901 while ((char *)entry
< __stop_eh_frame
) {
904 count
= dwarf_entry_len(p
, &len
);
907 * We read a bogus length field value. There is
908 * nothing we can do here apart from disabling
909 * the DWARF unwinder. We can't even skip this
910 * entry and move to the next one because 'len'
911 * tells us where our next entry is.
917 /* initial length does not include itself */
920 entry_type
= get_unaligned((u32
*)p
);
923 if (entry_type
== DW_EH_FRAME_CIE
) {
924 err
= dwarf_parse_cie(entry
, p
, len
, end
);
930 err
= dwarf_parse_fde(entry
, entry_type
, p
, len
);
937 entry
= (char *)entry
+ len
+ 4;
940 printk(KERN_INFO
"DWARF unwinder initialised: read %u CIEs, %u FDEs\n",
941 c_entries
, f_entries
);
943 err
= unwinder_register(&dwarf_unwinder
);
950 printk(KERN_ERR
"Failed to initialise DWARF unwinder: %d\n", err
);
951 dwarf_unwinder_cleanup();
954 early_initcall(dwarf_unwinder_init
);