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;
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 static struct unwind_table *last_table;
179 /* Must be called with module_mutex held. */
180 void *unwind_add_table(struct module *module,
181 const void *table_start,
182 unsigned long table_size)
184 struct unwind_table *table;
189 table = kmalloc(sizeof(*table), GFP_KERNEL);
193 init_unwind_table(table, module->name,
194 module->module_core, module->core_size,
195 module->module_init, module->init_size,
196 table_start, table_size);
199 last_table->link = table;
201 root_table.link = table;
207 struct unlink_table_info
209 struct unwind_table *table;
213 static int unlink_table(void *arg)
215 struct unlink_table_info *info = arg;
216 struct unwind_table *table = info->table, *prev;
218 for (prev = &root_table; prev->link && prev->link != table; prev = prev->link)
222 if (info->init_only) {
224 table->init.range = 0;
227 prev->link = table->link;
237 /* Must be called with module_mutex held. */
238 void unwind_remove_table(void *handle, int init_only)
240 struct unwind_table *table = handle;
241 struct unlink_table_info info;
243 if (!table || table == &root_table)
246 if (init_only && table == last_table) {
248 table->init.range = 0;
253 info.init_only = init_only;
254 stop_machine_run(unlink_table, &info, NR_CPUS);
260 #endif /* CONFIG_MODULES */
262 static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
264 const u8 *cur = *pcur;
268 for (shift = 0, value = 0; cur < end; shift += 7) {
269 if (shift + 7 > 8 * sizeof(value)
270 && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
274 value |= (uleb128_t)(*cur & 0x7f) << shift;
275 if (!(*cur++ & 0x80))
283 static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
285 const u8 *cur = *pcur;
289 for (shift = 0, value = 0; cur < end; shift += 7) {
290 if (shift + 7 > 8 * sizeof(value)
291 && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
295 value |= (sleb128_t)(*cur & 0x7f) << shift;
296 if (!(*cur & 0x80)) {
297 value |= -(*cur++ & 0x40) << shift;
306 static unsigned long read_pointer(const u8 **pLoc,
310 unsigned long value = 0;
317 const unsigned long *pul;
320 if (ptrType < 0 || ptrType == DW_EH_PE_omit)
323 switch(ptrType & DW_EH_PE_FORM) {
325 if (end < (const void *)(ptr.p16u + 1))
327 if(ptrType & DW_EH_PE_signed)
328 value = get_unaligned(ptr.p16s++);
330 value = get_unaligned(ptr.p16u++);
334 if (end < (const void *)(ptr.p32u + 1))
336 if(ptrType & DW_EH_PE_signed)
337 value = get_unaligned(ptr.p32s++);
339 value = get_unaligned(ptr.p32u++);
342 BUILD_BUG_ON(sizeof(u64) != sizeof(value));
344 BUILD_BUG_ON(sizeof(u32) != sizeof(value));
346 case DW_EH_PE_native:
347 if (end < (const void *)(ptr.pul + 1))
349 value = get_unaligned(ptr.pul++);
351 case DW_EH_PE_leb128:
352 BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
353 value = ptrType & DW_EH_PE_signed
354 ? get_sleb128(&ptr.p8, end)
355 : get_uleb128(&ptr.p8, end);
356 if ((const void *)ptr.p8 > end)
362 switch(ptrType & DW_EH_PE_ADJUST) {
366 value += (unsigned long)*pLoc;
371 if ((ptrType & DW_EH_PE_indirect)
372 && __get_user(value, (unsigned long *)value))
379 static signed fde_pointer_type(const u32 *cie)
381 const u8 *ptr = (const u8 *)(cie + 2);
382 unsigned version = *ptr;
385 return -1; /* unsupported */
388 const u8 *end = (const u8 *)(cie + 1) + *cie;
391 /* check if augmentation size is first (and thus present) */
394 /* check if augmentation string is nul-terminated */
395 if ((ptr = memchr(aug = (const void *)ptr, 0, end - ptr)) == NULL)
397 ++ptr; /* skip terminator */
398 get_uleb128(&ptr, end); /* skip code alignment */
399 get_sleb128(&ptr, end); /* skip data alignment */
400 /* skip return address column */
401 version <= 1 ? (void)++ptr : (void)get_uleb128(&ptr, end);
402 len = get_uleb128(&ptr, end); /* augmentation length */
403 if (ptr + len < ptr || ptr + len > end)
414 signed ptrType = *ptr++;
416 if (!read_pointer(&ptr, end, ptrType) || ptr > end)
427 return DW_EH_PE_native|DW_EH_PE_abs;
430 static int advance_loc(unsigned long delta, struct unwind_state *state)
432 state->loc += delta * state->codeAlign;
437 static void set_rule(uleb128_t reg,
438 enum item_location where,
440 struct unwind_state *state)
442 if (reg < ARRAY_SIZE(state->regs)) {
443 state->regs[reg].where = where;
444 state->regs[reg].value = value;
448 static int processCFI(const u8 *start,
450 unsigned long targetLoc,
452 struct unwind_state *state)
461 if (start != state->cieStart) {
462 state->loc = state->org;
463 result = processCFI(state->cieStart, state->cieEnd, 0, ptrType, state);
464 if (targetLoc == 0 && state->label == NULL)
467 for (ptr.p8 = start; result && ptr.p8 < end; ) {
468 switch(*ptr.p8 >> 6) {
476 if ((state->loc = read_pointer(&ptr.p8, end, ptrType)) == 0)
479 case DW_CFA_advance_loc1:
480 result = ptr.p8 < end && advance_loc(*ptr.p8++, state);
482 case DW_CFA_advance_loc2:
483 result = ptr.p8 <= end + 2
484 && advance_loc(*ptr.p16++, state);
486 case DW_CFA_advance_loc4:
487 result = ptr.p8 <= end + 4
488 && advance_loc(*ptr.p32++, state);
490 case DW_CFA_offset_extended:
491 value = get_uleb128(&ptr.p8, end);
492 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
494 case DW_CFA_val_offset:
495 value = get_uleb128(&ptr.p8, end);
496 set_rule(value, Value, get_uleb128(&ptr.p8, end), state);
498 case DW_CFA_offset_extended_sf:
499 value = get_uleb128(&ptr.p8, end);
500 set_rule(value, Memory, get_sleb128(&ptr.p8, end), state);
502 case DW_CFA_val_offset_sf:
503 value = get_uleb128(&ptr.p8, end);
504 set_rule(value, Value, get_sleb128(&ptr.p8, end), state);
506 case DW_CFA_restore_extended:
507 case DW_CFA_undefined:
508 case DW_CFA_same_value:
509 set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0, state);
511 case DW_CFA_register:
512 value = get_uleb128(&ptr.p8, end);
515 get_uleb128(&ptr.p8, end), state);
517 case DW_CFA_remember_state:
518 if (ptr.p8 == state->label) {
522 if (state->stackDepth >= MAX_STACK_DEPTH)
524 state->stack[state->stackDepth++] = ptr.p8;
526 case DW_CFA_restore_state:
527 if (state->stackDepth) {
528 const uleb128_t loc = state->loc;
529 const u8 *label = state->label;
531 state->label = state->stack[state->stackDepth - 1];
532 memcpy(&state->cfa, &badCFA, sizeof(state->cfa));
533 memset(state->regs, 0, sizeof(state->regs));
534 state->stackDepth = 0;
535 result = processCFI(start, end, 0, ptrType, state);
537 state->label = label;
542 state->cfa.reg = get_uleb128(&ptr.p8, end);
544 case DW_CFA_def_cfa_offset:
545 state->cfa.offs = get_uleb128(&ptr.p8, end);
547 case DW_CFA_def_cfa_sf:
548 state->cfa.reg = get_uleb128(&ptr.p8, end);
550 case DW_CFA_def_cfa_offset_sf:
551 state->cfa.offs = get_sleb128(&ptr.p8, end)
554 case DW_CFA_def_cfa_register:
555 state->cfa.reg = get_uleb128(&ptr.p8, end);
557 /*todo case DW_CFA_def_cfa_expression: */
558 /*todo case DW_CFA_expression: */
559 /*todo case DW_CFA_val_expression: */
560 case DW_CFA_GNU_args_size:
561 get_uleb128(&ptr.p8, end);
563 case DW_CFA_GNU_negative_offset_extended:
564 value = get_uleb128(&ptr.p8, end);
567 (uleb128_t)0 - get_uleb128(&ptr.p8, end), state);
569 case DW_CFA_GNU_window_save:
576 result = advance_loc(*ptr.p8++ & 0x3f, state);
579 value = *ptr.p8++ & 0x3f;
580 set_rule(value, Memory, get_uleb128(&ptr.p8, end), state);
583 set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
588 if (result && targetLoc != 0 && targetLoc < state->loc)
595 || (/*todo While in theory this should apply, gcc in practice omits
596 everything past the function prolog, and hence the location
597 never reaches the end of the function.
598 targetLoc < state->loc &&*/ state->label == NULL));
601 /* Unwind to previous to frame. Returns 0 if successful, negative
602 * number in case of an error. */
603 int unwind(struct unwind_frame_info *frame)
605 #define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
606 const u32 *fde = NULL, *cie = NULL;
607 const u8 *ptr = NULL, *end = NULL;
608 unsigned long pc = UNW_PC(frame) - frame->call_frame;
609 unsigned long startLoc = 0, endLoc = 0, cfa;
612 uleb128_t retAddrReg = 0;
613 struct unwind_table *table;
614 struct unwind_state state;
616 if (UNW_PC(frame) == 0)
618 if ((table = find_table(pc)) != NULL
619 && !(table->size & (sizeof(*fde) - 1))) {
620 unsigned long tableSize = table->size;
622 for (fde = table->address;
623 tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
624 tableSize -= sizeof(*fde) + *fde,
625 fde += 1 + *fde / sizeof(*fde)) {
626 if (!*fde || (*fde & (sizeof(*fde) - 1)))
629 continue; /* this is a CIE */
630 if ((fde[1] & (sizeof(*fde) - 1))
631 || fde[1] > (unsigned long)(fde + 1)
632 - (unsigned long)table->address)
633 continue; /* this is not a valid FDE */
634 cie = fde + 1 - fde[1] / sizeof(*fde);
635 if (*cie <= sizeof(*cie) + 4
636 || *cie >= fde[1] - sizeof(*fde)
637 || (*cie & (sizeof(*cie) - 1))
639 || (ptrType = fde_pointer_type(cie)) < 0) {
640 cie = NULL; /* this is not a (valid) CIE */
643 ptr = (const u8 *)(fde + 2);
644 startLoc = read_pointer(&ptr,
645 (const u8 *)(fde + 1) + *fde,
649 (const u8 *)(fde + 1) + *fde,
650 ptrType & DW_EH_PE_indirect
652 : ptrType & (DW_EH_PE_FORM|DW_EH_PE_signed));
653 if (pc >= startLoc && pc < endLoc)
659 memset(&state, 0, sizeof(state));
660 state.cieEnd = ptr; /* keep here temporarily */
661 ptr = (const u8 *)(cie + 2);
662 end = (const u8 *)(cie + 1) + *cie;
663 frame->call_frame = 1;
664 if ((state.version = *ptr) != 1)
665 cie = NULL; /* unsupported version */
667 /* check if augmentation size is first (and thus present) */
669 while (++ptr < end && *ptr) {
671 /* check for ignorable (or already handled)
672 * nul-terminated augmentation string */
678 frame->call_frame = 0;
686 if (ptr >= end || *ptr)
692 /* get code aligment factor */
693 state.codeAlign = get_uleb128(&ptr, end);
694 /* get data aligment factor */
695 state.dataAlign = get_sleb128(&ptr, end);
696 if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
699 retAddrReg = state.version <= 1 ? *ptr++ : get_uleb128(&ptr, end);
700 /* skip augmentation */
701 if (((const char *)(cie + 2))[1] == 'z')
702 ptr += get_uleb128(&ptr, end);
704 || retAddrReg >= ARRAY_SIZE(reg_info)
705 || REG_INVALID(retAddrReg)
706 || reg_info[retAddrReg].width != sizeof(unsigned long))
711 state.cieStart = ptr;
714 end = (const u8 *)(fde + 1) + *fde;
715 /* skip augmentation */
716 if (((const char *)(cie + 2))[1] == 'z') {
717 uleb128_t augSize = get_uleb128(&ptr, end);
719 if ((ptr += augSize) > end)
723 if (cie == NULL || fde == NULL) {
724 #ifdef CONFIG_FRAME_POINTER
725 unsigned long top, bottom;
728 #ifdef CONFIG_FRAME_POINTER
729 top = STACK_TOP(frame->task);
730 bottom = STACK_BOTTOM(frame->task);
731 # if FRAME_RETADDR_OFFSET < 0
732 if (UNW_SP(frame) < top
733 && UNW_FP(frame) <= UNW_SP(frame)
734 && bottom < UNW_FP(frame)
736 if (UNW_SP(frame) > top
737 && UNW_FP(frame) >= UNW_SP(frame)
738 && bottom > UNW_FP(frame)
740 && !((UNW_SP(frame) | UNW_FP(frame))
741 & (sizeof(unsigned long) - 1))) {
744 if (!__get_user(link,
745 (unsigned long *)(UNW_FP(frame)
746 + FRAME_LINK_OFFSET))
747 # if FRAME_RETADDR_OFFSET < 0
748 && link > bottom && link < UNW_FP(frame)
750 && link > UNW_FP(frame) && link < bottom
752 && !(link & (sizeof(link) - 1))
753 && !__get_user(UNW_PC(frame),
754 (unsigned long *)(UNW_FP(frame)
755 + FRAME_RETADDR_OFFSET))) {
756 UNW_SP(frame) = UNW_FP(frame) + FRAME_RETADDR_OFFSET
757 # if FRAME_RETADDR_OFFSET < 0
762 sizeof(UNW_PC(frame));
763 UNW_FP(frame) = link;
770 state.org = startLoc;
771 memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
772 /* process instructions */
773 if (!processCFI(ptr, end, pc, ptrType, &state)
774 || state.loc > endLoc
775 || state.regs[retAddrReg].where == Nowhere
776 || state.cfa.reg >= ARRAY_SIZE(reg_info)
777 || reg_info[state.cfa.reg].width != sizeof(unsigned long)
778 || state.cfa.offs % sizeof(unsigned long))
781 #ifndef CONFIG_AS_CFI_SIGNAL_FRAME
783 && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
784 frame->call_frame = 0;
786 cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
787 startLoc = min((unsigned long)UNW_SP(frame), cfa);
788 endLoc = max((unsigned long)UNW_SP(frame), cfa);
789 if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
790 startLoc = min(STACK_LIMIT(cfa), cfa);
791 endLoc = max(STACK_LIMIT(cfa), cfa);
794 # define CASES CASE(8); CASE(16); CASE(32)
796 # define CASES CASE(8); CASE(16); CASE(32); CASE(64)
798 for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
799 if (REG_INVALID(i)) {
800 if (state.regs[i].where == Nowhere)
804 switch(state.regs[i].where) {
808 if (state.regs[i].value >= ARRAY_SIZE(reg_info)
809 || REG_INVALID(state.regs[i].value)
810 || reg_info[i].width > reg_info[state.regs[i].value].width)
812 switch(reg_info[state.regs[i].value].width) {
815 state.regs[i].value = FRAME_REG(state.regs[i].value, \
826 for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
829 switch(state.regs[i].where) {
831 if (reg_info[i].width != sizeof(UNW_SP(frame))
832 || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
838 switch(reg_info[i].width) {
839 #define CASE(n) case sizeof(u##n): \
840 FRAME_REG(i, u##n) = state.regs[i].value; \
849 if (reg_info[i].width != sizeof(unsigned long))
851 FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
855 unsigned long addr = cfa + state.regs[i].value
858 if ((state.regs[i].value * state.dataAlign)
859 % sizeof(unsigned long)
861 || addr + sizeof(unsigned long) < addr
862 || addr + sizeof(unsigned long) > endLoc)
864 switch(reg_info[i].width) {
865 #define CASE(n) case sizeof(u##n): \
866 __get_user(FRAME_REG(i, u##n), (u##n *)addr); \
882 EXPORT_SYMBOL(unwind);
884 int unwind_init_frame_info(struct unwind_frame_info *info,
885 struct task_struct *tsk,
886 /*const*/ struct pt_regs *regs)
889 info->call_frame = 0;
890 arch_unw_init_frame_info(info, regs);
894 EXPORT_SYMBOL(unwind_init_frame_info);
897 * Prepare to unwind a blocked task.
899 int unwind_init_blocked(struct unwind_frame_info *info,
900 struct task_struct *tsk)
903 info->call_frame = 0;
904 arch_unw_init_blocked(info);
908 EXPORT_SYMBOL(unwind_init_blocked);
911 * Prepare to unwind the currently running thread.
913 int unwind_init_running(struct unwind_frame_info *info,
914 asmlinkage int (*callback)(struct unwind_frame_info *,
918 info->task = current;
919 info->call_frame = 0;
921 return arch_unwind_init_running(info, callback, arg);
923 EXPORT_SYMBOL(unwind_init_running);
926 * Unwind until the return pointer is in user-land (or until an error
927 * occurs). Returns 0 if successful, negative number in case of
930 int unwind_to_user(struct unwind_frame_info *info)
932 while (!arch_unw_user_mode(info)) {
933 int err = unwind(info);
941 EXPORT_SYMBOL(unwind_to_user);