2 * Copyright (C) 2002-2006 Novell, Inc.
3 * Jan Beulich <jbeulich@novell.com>
4 * This code is released under version 2 of the GNU GPL.
6 * A simple API for unwinding kernel stacks. This is used for
7 * debugging and error reporting purposes. The kernel doesn't need
8 * full-blown stack unwinding with all the bells and whistles, so there
9 * is not much point in implementing the full Dwarf2 unwind API.
12 #include <linux/unwind.h>
13 #include <linux/module.h>
14 #include <linux/delay.h>
15 #include <linux/stop_machine.h>
16 #include <asm/sections.h>
17 #include <asm/uaccess.h>
18 #include <asm/unaligned.h>
20 extern char __start_unwind[], __end_unwind[];
22 #define MAX_STACK_DEPTH 8
24 #define EXTRA_INFO(f) { \
25 BUILD_BUG_ON_ZERO(offsetof(struct unwind_frame_info, f) \
26 % FIELD_SIZEOF(struct unwind_frame_info, f)) \
27 + offsetof(struct unwind_frame_info, f) \
28 / FIELD_SIZEOF(struct unwind_frame_info, f), \
29 FIELD_SIZEOF(struct unwind_frame_info, f) \
31 #define PTREGS_INFO(f) EXTRA_INFO(regs.f)
34 unsigned offs:BITS_PER_LONG / 2;
35 unsigned width:BITS_PER_LONG / 2;
44 #define REG_INVALID(r) (reg_info[r].width == 0)
47 #define DW_CFA_nop 0x00
48 #define DW_CFA_set_loc 0x01
49 #define DW_CFA_advance_loc1 0x02
50 #define DW_CFA_advance_loc2 0x03
51 #define DW_CFA_advance_loc4 0x04
52 #define DW_CFA_offset_extended 0x05
53 #define DW_CFA_restore_extended 0x06
54 #define DW_CFA_undefined 0x07
55 #define DW_CFA_same_value 0x08
56 #define DW_CFA_register 0x09
57 #define DW_CFA_remember_state 0x0a
58 #define DW_CFA_restore_state 0x0b
59 #define DW_CFA_def_cfa 0x0c
60 #define DW_CFA_def_cfa_register 0x0d
61 #define DW_CFA_def_cfa_offset 0x0e
62 #define DW_CFA_def_cfa_expression 0x0f
63 #define DW_CFA_expression 0x10
64 #define DW_CFA_offset_extended_sf 0x11
65 #define DW_CFA_def_cfa_sf 0x12
66 #define DW_CFA_def_cfa_offset_sf 0x13
67 #define DW_CFA_val_offset 0x14
68 #define DW_CFA_val_offset_sf 0x15
69 #define DW_CFA_val_expression 0x16
70 #define DW_CFA_lo_user 0x1c
71 #define DW_CFA_GNU_window_save 0x2d
72 #define DW_CFA_GNU_args_size 0x2e
73 #define DW_CFA_GNU_negative_offset_extended 0x2f
74 #define DW_CFA_hi_user 0x3f
76 #define DW_EH_PE_FORM 0x07
77 #define DW_EH_PE_native 0x00
78 #define DW_EH_PE_leb128 0x01
79 #define DW_EH_PE_data2 0x02
80 #define DW_EH_PE_data4 0x03
81 #define DW_EH_PE_data8 0x04
82 #define DW_EH_PE_signed 0x08
83 #define DW_EH_PE_ADJUST 0x70
84 #define DW_EH_PE_abs 0x00
85 #define DW_EH_PE_pcrel 0x10
86 #define DW_EH_PE_textrel 0x20
87 #define DW_EH_PE_datarel 0x30
88 #define DW_EH_PE_funcrel 0x40
89 #define DW_EH_PE_aligned 0x50
90 #define DW_EH_PE_indirect 0x80
91 #define DW_EH_PE_omit 0xff
93 typedef unsigned long uleb128_t;
94 typedef signed long sleb128_t;
96 static struct unwind_table {
103 struct unwind_table *link;
105 } root_table, *last_table;
117 struct unwind_state {
119 const u8 *cieStart, *cieEnd;
125 struct unwind_item regs[ARRAY_SIZE(reg_info)];
126 unsigned stackDepth:8;
129 const u8 *stack[MAX_STACK_DEPTH];
132 static const struct cfa badCFA = { ARRAY_SIZE(reg_info), 1 };
134 static struct unwind_table *find_table(unsigned long pc)
136 struct unwind_table *table;
138 for (table = &root_table; table; table = table->link)
139 if ((pc >= table->core.pc
140 && pc < table->core.pc + table->core.range)
141 || (pc >= table->init.pc
142 && pc < table->init.pc + table->init.range))
148 static void init_unwind_table(struct unwind_table *table,
150 const void *core_start,
151 unsigned long core_size,
152 const void *init_start,
153 unsigned long init_size,
154 const void *table_start,
155 unsigned long table_size)
157 table->core.pc = (unsigned long)core_start;
158 table->core.range = core_size;
159 table->init.pc = (unsigned long)init_start;
160 table->init.range = init_size;
161 table->address = table_start;
162 table->size = table_size;
167 void __init unwind_init(void)
169 init_unwind_table(&root_table, "kernel",
172 __start_unwind, __end_unwind - __start_unwind);
175 #ifdef CONFIG_MODULES
177 /* Must be called with module_mutex held. */
178 void *unwind_add_table(struct module *module,
179 const void *table_start,
180 unsigned long table_size)
182 struct unwind_table *table;
187 table = kmalloc(sizeof(*table), GFP_KERNEL);
191 init_unwind_table(table, module->name,
192 module->module_core, module->core_size,
193 module->module_init, module->init_size,
194 table_start, table_size);
197 last_table->link = table;
199 root_table.link = table;
205 struct unlink_table_info
207 struct unwind_table *table;
211 static int unlink_table(void *arg)
213 struct unlink_table_info *info = arg;
214 struct unwind_table *table = info->table, *prev;
216 for (prev = &root_table; prev->link && prev->link != table; prev = prev->link)
220 if (info->init_only) {
222 table->init.range = 0;
225 prev->link = table->link;
235 /* Must be called with module_mutex held. */
236 void unwind_remove_table(void *handle, int init_only)
238 struct unwind_table *table = handle;
239 struct unlink_table_info info;
241 if (!table || table == &root_table)
244 if (init_only && table == last_table) {
246 table->init.range = 0;
251 info.init_only = init_only;
252 stop_machine_run(unlink_table, &info, NR_CPUS);
258 #endif /* CONFIG_MODULES */
260 static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
262 const u8 *cur = *pcur;
266 for (shift = 0, value = 0; cur < end; shift += 7) {
267 if (shift + 7 > 8 * sizeof(value)
268 && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
272 value |= (uleb128_t)(*cur & 0x7f) << shift;
273 if (!(*cur++ & 0x80))
281 static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
283 const u8 *cur = *pcur;
287 for (shift = 0, value = 0; cur < end; shift += 7) {
288 if (shift + 7 > 8 * sizeof(value)
289 && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
293 value |= (sleb128_t)(*cur & 0x7f) << shift;
294 if (!(*cur & 0x80)) {
295 value |= -(*cur++ & 0x40) << shift;
304 static unsigned long read_pointer(const u8 **pLoc,
308 unsigned long value = 0;
315 const unsigned long *pul;
318 if (ptrType < 0 || ptrType == DW_EH_PE_omit)
321 switch(ptrType & DW_EH_PE_FORM) {
323 if (end < (const void *)(ptr.p16u + 1))
325 if(ptrType & DW_EH_PE_signed)
326 value = get_unaligned(ptr.p16s++);
328 value = get_unaligned(ptr.p16u++);
332 if (end < (const void *)(ptr.p32u + 1))
334 if(ptrType & DW_EH_PE_signed)
335 value = get_unaligned(ptr.p32s++);
337 value = get_unaligned(ptr.p32u++);
340 BUILD_BUG_ON(sizeof(u64) != sizeof(value));
342 BUILD_BUG_ON(sizeof(u32) != sizeof(value));
344 case DW_EH_PE_native:
345 if (end < (const void *)(ptr.pul + 1))
347 value = get_unaligned(ptr.pul++);
349 case DW_EH_PE_leb128:
350 BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
351 value = ptrType & DW_EH_PE_signed
352 ? get_sleb128(&ptr.p8, end)
353 : get_uleb128(&ptr.p8, end);
354 if ((const void *)ptr.p8 > end)
360 switch(ptrType & DW_EH_PE_ADJUST) {
364 value += (unsigned long)*pLoc;
369 if ((ptrType & DW_EH_PE_indirect)
370 && __get_user(value, (unsigned long *)value))
377 static signed fde_pointer_type(const u32 *cie)
379 const u8 *ptr = (const u8 *)(cie + 2);
380 unsigned version = *ptr;
383 return -1; /* unsupported */
386 const u8 *end = (const u8 *)(cie + 1) + *cie;
389 /* check if augmentation size is first (and thus present) */
392 /* check if augmentation string is nul-terminated */
393 if ((ptr = memchr(aug = (const void *)ptr, 0, end - ptr)) == NULL)
395 ++ptr; /* skip terminator */
396 get_uleb128(&ptr, end); /* skip code alignment */
397 get_sleb128(&ptr, end); /* skip data alignment */
398 /* skip return address column */
399 version <= 1 ? (void)++ptr : (void)get_uleb128(&ptr, end);
400 len = get_uleb128(&ptr, end); /* augmentation length */
401 if (ptr + len < ptr || ptr + len > end)
412 signed ptrType = *ptr++;
414 if (!read_pointer(&ptr, end, ptrType) || ptr > end)
425 return DW_EH_PE_native|DW_EH_PE_abs;
428 static int advance_loc(unsigned long delta, struct unwind_state *state)
430 state->loc += delta * state->codeAlign;
435 static void set_rule(uleb128_t reg,
436 enum item_location where,
438 struct unwind_state *state)
440 if (reg < ARRAY_SIZE(state->regs)) {
441 state->regs[reg].where = where;
442 state->regs[reg].value = value;
446 static int processCFI(const u8 *start,
448 unsigned long targetLoc,
450 struct unwind_state *state)
459 if (start != state->cieStart) {
460 state->loc = state->org;
461 result = processCFI(state->cieStart, state->cieEnd, 0, ptrType, state);
462 if (targetLoc == 0 && state->label == NULL)
465 for (ptr.p8 = start; result && ptr.p8 < end; ) {
466 switch(*ptr.p8 >> 6) {
474 if ((state->loc = read_pointer(&ptr.p8, end, ptrType)) == 0)
477 case DW_CFA_advance_loc1:
478 result = ptr.p8 < end && advance_loc(*ptr.p8++, state);
480 case DW_CFA_advance_loc2:
481 result = ptr.p8 <= end + 2
482 && advance_loc(*ptr.p16++, state);
484 case DW_CFA_advance_loc4:
485 result = ptr.p8 <= end + 4
486 && advance_loc(*ptr.p32++, state);
488 case DW_CFA_offset_extended:
489 value = get_uleb128(&ptr.p8, end);
490 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
492 case DW_CFA_val_offset:
493 value = get_uleb128(&ptr.p8, end);
494 set_rule(value, Value, get_uleb128(&ptr.p8, end), state);
496 case DW_CFA_offset_extended_sf:
497 value = get_uleb128(&ptr.p8, end);
498 set_rule(value, Memory, get_sleb128(&ptr.p8, end), state);
500 case DW_CFA_val_offset_sf:
501 value = get_uleb128(&ptr.p8, end);
502 set_rule(value, Value, get_sleb128(&ptr.p8, end), state);
504 case DW_CFA_restore_extended:
505 case DW_CFA_undefined:
506 case DW_CFA_same_value:
507 set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0, state);
509 case DW_CFA_register:
510 value = get_uleb128(&ptr.p8, end);
513 get_uleb128(&ptr.p8, end), state);
515 case DW_CFA_remember_state:
516 if (ptr.p8 == state->label) {
520 if (state->stackDepth >= MAX_STACK_DEPTH)
522 state->stack[state->stackDepth++] = ptr.p8;
524 case DW_CFA_restore_state:
525 if (state->stackDepth) {
526 const uleb128_t loc = state->loc;
527 const u8 *label = state->label;
529 state->label = state->stack[state->stackDepth - 1];
530 memcpy(&state->cfa, &badCFA, sizeof(state->cfa));
531 memset(state->regs, 0, sizeof(state->regs));
532 state->stackDepth = 0;
533 result = processCFI(start, end, 0, ptrType, state);
535 state->label = label;
540 state->cfa.reg = get_uleb128(&ptr.p8, end);
542 case DW_CFA_def_cfa_offset:
543 state->cfa.offs = get_uleb128(&ptr.p8, end);
545 case DW_CFA_def_cfa_sf:
546 state->cfa.reg = get_uleb128(&ptr.p8, end);
548 case DW_CFA_def_cfa_offset_sf:
549 state->cfa.offs = get_sleb128(&ptr.p8, end)
552 case DW_CFA_def_cfa_register:
553 state->cfa.reg = get_uleb128(&ptr.p8, end);
555 /*todo case DW_CFA_def_cfa_expression: */
556 /*todo case DW_CFA_expression: */
557 /*todo case DW_CFA_val_expression: */
558 case DW_CFA_GNU_args_size:
559 get_uleb128(&ptr.p8, end);
561 case DW_CFA_GNU_negative_offset_extended:
562 value = get_uleb128(&ptr.p8, end);
565 (uleb128_t)0 - get_uleb128(&ptr.p8, end), state);
567 case DW_CFA_GNU_window_save:
574 result = advance_loc(*ptr.p8++ & 0x3f, state);
577 value = *ptr.p8++ & 0x3f;
578 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
581 set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
586 if (result && targetLoc != 0 && targetLoc < state->loc)
593 || (/*todo While in theory this should apply, gcc in practice omits
594 everything past the function prolog, and hence the location
595 never reaches the end of the function.
596 targetLoc < state->loc &&*/ state->label == NULL));
599 /* Unwind to previous to frame. Returns 0 if successful, negative
600 * number in case of an error. */
601 int unwind(struct unwind_frame_info *frame)
603 #define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
604 const u32 *fde = NULL, *cie = NULL;
605 const u8 *ptr = NULL, *end = NULL;
606 unsigned long startLoc = 0, endLoc = 0, cfa;
609 uleb128_t retAddrReg = 0;
610 struct unwind_table *table;
611 struct unwind_state state;
613 if (UNW_PC(frame) == 0)
615 if ((table = find_table(UNW_PC(frame))) != NULL
616 && !(table->size & (sizeof(*fde) - 1))) {
617 unsigned long tableSize = table->size;
619 for (fde = table->address;
620 tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
621 tableSize -= sizeof(*fde) + *fde,
622 fde += 1 + *fde / sizeof(*fde)) {
623 if (!*fde || (*fde & (sizeof(*fde) - 1)))
626 continue; /* this is a CIE */
627 if ((fde[1] & (sizeof(*fde) - 1))
628 || fde[1] > (unsigned long)(fde + 1)
629 - (unsigned long)table->address)
630 continue; /* this is not a valid FDE */
631 cie = fde + 1 - fde[1] / sizeof(*fde);
632 if (*cie <= sizeof(*cie) + 4
633 || *cie >= fde[1] - sizeof(*fde)
634 || (*cie & (sizeof(*cie) - 1))
636 || (ptrType = fde_pointer_type(cie)) < 0) {
637 cie = NULL; /* this is not a (valid) CIE */
640 ptr = (const u8 *)(fde + 2);
641 startLoc = read_pointer(&ptr,
642 (const u8 *)(fde + 1) + *fde,
646 (const u8 *)(fde + 1) + *fde,
647 ptrType & DW_EH_PE_indirect
649 : ptrType & (DW_EH_PE_FORM|DW_EH_PE_signed));
650 if (UNW_PC(frame) >= startLoc && UNW_PC(frame) < endLoc)
656 memset(&state, 0, sizeof(state));
657 state.cieEnd = ptr; /* keep here temporarily */
658 ptr = (const u8 *)(cie + 2);
659 end = (const u8 *)(cie + 1) + *cie;
660 if ((state.version = *ptr) != 1)
661 cie = NULL; /* unsupported version */
663 /* check if augmentation size is first (and thus present) */
665 /* check for ignorable (or already handled)
666 * nul-terminated augmentation string */
667 while (++ptr < end && *ptr)
668 if (strchr("LPR", *ptr) == NULL)
671 if (ptr >= end || *ptr)
677 /* get code aligment factor */
678 state.codeAlign = get_uleb128(&ptr, end);
679 /* get data aligment factor */
680 state.dataAlign = get_sleb128(&ptr, end);
681 if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
684 retAddrReg = state.version <= 1 ? *ptr++ : get_uleb128(&ptr, end);
685 /* skip augmentation */
686 if (((const char *)(cie + 2))[1] == 'z')
687 ptr += get_uleb128(&ptr, end);
689 || retAddrReg >= ARRAY_SIZE(reg_info)
690 || REG_INVALID(retAddrReg)
691 || reg_info[retAddrReg].width != sizeof(unsigned long))
696 state.cieStart = ptr;
699 end = (const u8 *)(fde + 1) + *fde;
700 /* skip augmentation */
701 if (((const char *)(cie + 2))[1] == 'z') {
702 uleb128_t augSize = get_uleb128(&ptr, end);
704 if ((ptr += augSize) > end)
708 if (cie == NULL || fde == NULL) {
709 #ifdef CONFIG_FRAME_POINTER
710 unsigned long top, bottom;
713 #ifdef CONFIG_FRAME_POINTER
714 top = STACK_TOP(frame->task);
715 bottom = STACK_BOTTOM(frame->task);
716 # if FRAME_RETADDR_OFFSET < 0
717 if (UNW_SP(frame) < top
718 && UNW_FP(frame) <= UNW_SP(frame)
719 && bottom < UNW_FP(frame)
721 if (UNW_SP(frame) > top
722 && UNW_FP(frame) >= UNW_SP(frame)
723 && bottom > UNW_FP(frame)
725 && !((UNW_SP(frame) | UNW_FP(frame))
726 & (sizeof(unsigned long) - 1))) {
729 if (!__get_user(link,
730 (unsigned long *)(UNW_FP(frame)
731 + FRAME_LINK_OFFSET))
732 # if FRAME_RETADDR_OFFSET < 0
733 && link > bottom && link < UNW_FP(frame)
735 && link > UNW_FP(frame) && link < bottom
737 && !(link & (sizeof(link) - 1))
738 && !__get_user(UNW_PC(frame),
739 (unsigned long *)(UNW_FP(frame)
740 + FRAME_RETADDR_OFFSET))) {
741 UNW_SP(frame) = UNW_FP(frame) + FRAME_RETADDR_OFFSET
742 # if FRAME_RETADDR_OFFSET < 0
747 sizeof(UNW_PC(frame));
748 UNW_FP(frame) = link;
755 state.org = startLoc;
756 memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
757 /* process instructions */
758 if (!processCFI(ptr, end, UNW_PC(frame), ptrType, &state)
759 || state.loc > endLoc
760 || state.regs[retAddrReg].where == Nowhere
761 || state.cfa.reg >= ARRAY_SIZE(reg_info)
762 || reg_info[state.cfa.reg].width != sizeof(unsigned long)
763 || state.cfa.offs % sizeof(unsigned long))
766 cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
767 startLoc = min((unsigned long)UNW_SP(frame), cfa);
768 endLoc = max((unsigned long)UNW_SP(frame), cfa);
769 if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
770 startLoc = min(STACK_LIMIT(cfa), cfa);
771 endLoc = max(STACK_LIMIT(cfa), cfa);
774 # define CASES CASE(8); CASE(16); CASE(32)
776 # define CASES CASE(8); CASE(16); CASE(32); CASE(64)
778 for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
779 if (REG_INVALID(i)) {
780 if (state.regs[i].where == Nowhere)
784 switch(state.regs[i].where) {
788 if (state.regs[i].value >= ARRAY_SIZE(reg_info)
789 || REG_INVALID(state.regs[i].value)
790 || reg_info[i].width > reg_info[state.regs[i].value].width)
792 switch(reg_info[state.regs[i].value].width) {
795 state.regs[i].value = FRAME_REG(state.regs[i].value, \
806 for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
809 switch(state.regs[i].where) {
811 if (reg_info[i].width != sizeof(UNW_SP(frame))
812 || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
818 switch(reg_info[i].width) {
819 #define CASE(n) case sizeof(u##n): \
820 FRAME_REG(i, u##n) = state.regs[i].value; \
829 if (reg_info[i].width != sizeof(unsigned long))
831 FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
835 unsigned long addr = cfa + state.regs[i].value
838 if ((state.regs[i].value * state.dataAlign)
839 % sizeof(unsigned long)
841 || addr + sizeof(unsigned long) < addr
842 || addr + sizeof(unsigned long) > endLoc)
844 switch(reg_info[i].width) {
845 #define CASE(n) case sizeof(u##n): \
846 __get_user(FRAME_REG(i, u##n), (u##n *)addr); \
862 EXPORT_SYMBOL(unwind);
864 int unwind_init_frame_info(struct unwind_frame_info *info,
865 struct task_struct *tsk,
866 /*const*/ struct pt_regs *regs)
869 arch_unw_init_frame_info(info, regs);
873 EXPORT_SYMBOL(unwind_init_frame_info);
876 * Prepare to unwind a blocked task.
878 int unwind_init_blocked(struct unwind_frame_info *info,
879 struct task_struct *tsk)
882 arch_unw_init_blocked(info);
886 EXPORT_SYMBOL(unwind_init_blocked);
889 * Prepare to unwind the currently running thread.
891 int unwind_init_running(struct unwind_frame_info *info,
892 asmlinkage int (*callback)(struct unwind_frame_info *,
896 info->task = current;
898 return arch_unwind_init_running(info, callback, arg);
900 EXPORT_SYMBOL(unwind_init_running);
903 * Unwind until the return pointer is in user-land (or until an error
904 * occurs). Returns 0 if successful, negative number in case of
907 int unwind_to_user(struct unwind_frame_info *info)
909 while (!arch_unw_user_mode(info)) {
910 int err = unwind(info);
918 EXPORT_SYMBOL(unwind_to_user);