From 142698282ceb6811ad3482c218b7292037cb67ff Mon Sep 17 00:00:00 2001 From: Matt Fleming Date: Wed, 27 Jan 2010 20:05:20 +0000 Subject: sh: Correct the offset of the return address in ret_from_exception The address that ret_from_exception and ret_from_irq will return to is found in the stack slot for SPC, not PR. This error was causing the DWARF unwinder to pick up the wrong return address on the stack and then unwind using the unwind tables for the wrong function. While I'm here I might as well add CFI annotations for the other registers since they could be useful when unwinding. Signed-off-by: Matt Fleming Signed-off-by: Paul Mundt --- arch/sh/kernel/entry-common.S | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'arch/sh/kernel') diff --git a/arch/sh/kernel/entry-common.S b/arch/sh/kernel/entry-common.S index f0abd58..2b15ae6 100644 --- a/arch/sh/kernel/entry-common.S +++ b/arch/sh/kernel/entry-common.S @@ -70,8 +70,14 @@ ret_from_exception: CFI_STARTPROC simple CFI_DEF_CFA r14, 0 CFI_REL_OFFSET 17, 64 - CFI_REL_OFFSET 15, 0 + CFI_REL_OFFSET 15, 60 CFI_REL_OFFSET 14, 56 + CFI_REL_OFFSET 13, 52 + CFI_REL_OFFSET 12, 48 + CFI_REL_OFFSET 11, 44 + CFI_REL_OFFSET 10, 40 + CFI_REL_OFFSET 9, 36 + CFI_REL_OFFSET 8, 32 preempt_stop() ENTRY(ret_from_irq) ! -- cgit v1.1 From 1dca56f13899b9e256f56198026019835aaf9a3a Mon Sep 17 00:00:00 2001 From: Matt Fleming Date: Wed, 27 Jan 2010 20:44:59 +0000 Subject: sh: Setup frame pointer in handle_exception path In order to allow the DWARF unwinder to unwind through exceptions we need to setup the frame pointer register (r14). Signed-off-by: Matt Fleming Signed-off-by: Paul Mundt --- arch/sh/kernel/cpu/sh3/entry.S | 2 ++ 1 file changed, 2 insertions(+) (limited to 'arch/sh/kernel') diff --git a/arch/sh/kernel/cpu/sh3/entry.S b/arch/sh/kernel/cpu/sh3/entry.S index 3f7e2a2..29021bc6 100644 --- a/arch/sh/kernel/cpu/sh3/entry.S +++ b/arch/sh/kernel/cpu/sh3/entry.S @@ -365,6 +365,8 @@ handle_exception: mov.l @k2, k2 ! read out vector and keep in k2 handle_exception_special: + setup_frame_reg + ! Setup return address and jump to exception handler mov.l 7f, r9 ! fetch return address stc r2_bank, r0 ! k2 (vector) -- cgit v1.1 From 944a3438615da65f11e2559840404a2cac5f65ea Mon Sep 17 00:00:00 2001 From: Matt Fleming Date: Sat, 30 Jan 2010 17:36:20 +0000 Subject: sh: Don't continue unwinding across interrupts Unfortunately, due to poor DWARF info in current toolchains, unwinding through interrutps cannot be done reliably. The problem is that the DWARF info for function epilogues is wrong. Take this standard epilogue sequence, 80003cc4: e3 6f mov r14,r15 80003cc6: 26 4f lds.l @r15+,pr 80003cc8: f6 6e mov.l @r15+,r14 <---- interrupt here 80003cca: f6 6b mov.l @r15+,r11 80003ccc: f6 6a mov.l @r15+,r10 80003cce: f6 69 mov.l @r15+,r9 80003cd0: 0b 00 rts If we take an interrupt at the highlighted point, the DWARF info will bogusly claim that the return address can be found at some offset from the frame pointer, even though the frame pointer was just restored. The worst part is if the unwinder finds a text address at the bogus stack address - unwinding will continue, for a bit, until it finally comes across an unexpected address on the stack and blows up. The only solution is to stop unwinding once we've calculated the function that was executing when the interrupt occurred. This PC can be easily calculated from pt_regs->pc. Signed-off-by: Matt Fleming Signed-off-by: Paul Mundt --- arch/sh/kernel/dwarf.c | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'arch/sh/kernel') diff --git a/arch/sh/kernel/dwarf.c b/arch/sh/kernel/dwarf.c index 88d28ec..e511680 100644 --- a/arch/sh/kernel/dwarf.c +++ b/arch/sh/kernel/dwarf.c @@ -540,6 +540,8 @@ void dwarf_free_frame(struct dwarf_frame *frame) mempool_free(frame, dwarf_frame_pool); } +extern void ret_from_irq(void); + /** * dwarf_unwind_stack - unwind the stack * @@ -678,6 +680,24 @@ struct dwarf_frame * dwarf_unwind_stack(unsigned long pc, addr = frame->cfa + reg->addr; frame->return_addr = __raw_readl(addr); + /* + * Ah, the joys of unwinding through interrupts. + * + * Interrupts are tricky - the DWARF info needs to be _really_ + * accurate and unfortunately I'm seeing a lot of bogus DWARF + * info. For example, I've seen interrupts occur in epilogues + * just after the frame pointer (r14) had been restored. The + * problem was that the DWARF info claimed that the CFA could be + * reached by using the value of the frame pointer before it was + * restored. + * + * So until the compiler can be trusted to produce reliable + * DWARF info when it really matters, let's stop unwinding once + * we've calculated the function that was interrupted. + */ + if (prev && prev->pc == (unsigned long)ret_from_irq) + frame->return_addr = 0; + return frame; bail: -- cgit v1.1 From 1af0b2fc676009d9b5b71a82ea6a3c2b20b7ea56 Mon Sep 17 00:00:00 2001 From: Matt Fleming Date: Sat, 30 Jan 2010 17:37:25 +0000 Subject: sh: Remove superfluous setup_frame_reg call There's no need to setup the frame pointer again in call_handle_tlbmiss. The frame pointer will already have been setup in handle_interrupt. Signed-off-by: Matt Fleming Signed-off-by: Paul Mundt --- arch/sh/kernel/cpu/sh3/entry.S | 1 - 1 file changed, 1 deletion(-) (limited to 'arch/sh/kernel') diff --git a/arch/sh/kernel/cpu/sh3/entry.S b/arch/sh/kernel/cpu/sh3/entry.S index 29021bc6..f6a389c 100644 --- a/arch/sh/kernel/cpu/sh3/entry.S +++ b/arch/sh/kernel/cpu/sh3/entry.S @@ -132,7 +132,6 @@ ENTRY(tlb_protection_violation_store) mov #1, r5 call_handle_tlbmiss: - setup_frame_reg mov.l 1f, r0 mov r5, r8 mov.l @r0, r6 -- cgit v1.1 From 858918b77b29d0e9ce7f524d1b57d602d85f5d64 Mon Sep 17 00:00:00 2001 From: Matt Fleming Date: Sun, 7 Feb 2010 12:40:36 +0000 Subject: sh: Optimise FDE/CIE lookup by using red-black trees Now that the DWARF unwinder is being used to provide perf callstacks unwinding speed is an issue. It is no longer being used in exceptional circumstances where we don't care about runtime performance, e.g. when panicing, so it makes sense improve performance is possible. With this patch I saw a 42% improvement in unwind time when calling return_address(1). Greater improvements will be seen as the number of levels unwound increases as each unwind is now cheaper. Note that insertion time has doubled but that's just the price we pay for keeping the trees balanced. However, this is a one-time cost for kernel boot/module load and so the improvements in lookup time dominate the extra time we spend keeping the trees balanced. Signed-off-by: Matt Fleming Signed-off-by: Paul Mundt --- arch/sh/kernel/dwarf.c | 174 ++++++++++++++++++++++++++++++++++--------------- 1 file changed, 120 insertions(+), 54 deletions(-) (limited to 'arch/sh/kernel') diff --git a/arch/sh/kernel/dwarf.c b/arch/sh/kernel/dwarf.c index e511680..bd1c497 100644 --- a/arch/sh/kernel/dwarf.c +++ b/arch/sh/kernel/dwarf.c @@ -39,10 +39,10 @@ static mempool_t *dwarf_frame_pool; static struct kmem_cache *dwarf_reg_cachep; static mempool_t *dwarf_reg_pool; -static LIST_HEAD(dwarf_cie_list); +static struct rb_root cie_root; static DEFINE_SPINLOCK(dwarf_cie_lock); -static LIST_HEAD(dwarf_fde_list); +static struct rb_root fde_root; static DEFINE_SPINLOCK(dwarf_fde_lock); static struct dwarf_cie *cached_cie; @@ -301,7 +301,8 @@ static inline int dwarf_entry_len(char *addr, unsigned long *len) */ static struct dwarf_cie *dwarf_lookup_cie(unsigned long cie_ptr) { - struct dwarf_cie *cie; + struct rb_node **rb_node = &cie_root.rb_node; + struct dwarf_cie *cie = NULL; unsigned long flags; spin_lock_irqsave(&dwarf_cie_lock, flags); @@ -315,16 +316,24 @@ static struct dwarf_cie *dwarf_lookup_cie(unsigned long cie_ptr) goto out; } - list_for_each_entry(cie, &dwarf_cie_list, link) { - if (cie->cie_pointer == cie_ptr) { - cached_cie = cie; - break; + while (*rb_node) { + struct dwarf_cie *cie_tmp; + + cie_tmp = rb_entry(*rb_node, struct dwarf_cie, node); + BUG_ON(!cie_tmp); + + if (cie_ptr == cie_tmp->cie_pointer) { + cie = cie_tmp; + cached_cie = cie_tmp; + goto out; + } else { + if (cie_ptr < cie_tmp->cie_pointer) + rb_node = &(*rb_node)->rb_left; + else + rb_node = &(*rb_node)->rb_right; } } - /* Couldn't find the entry in the list. */ - if (&cie->link == &dwarf_cie_list) - cie = NULL; out: spin_unlock_irqrestore(&dwarf_cie_lock, flags); return cie; @@ -336,25 +345,34 @@ out: */ struct dwarf_fde *dwarf_lookup_fde(unsigned long pc) { - struct dwarf_fde *fde; + struct rb_node **rb_node = &fde_root.rb_node; + struct dwarf_fde *fde = NULL; unsigned long flags; spin_lock_irqsave(&dwarf_fde_lock, flags); - list_for_each_entry(fde, &dwarf_fde_list, link) { - unsigned long start, end; + while (*rb_node) { + struct dwarf_fde *fde_tmp; + unsigned long tmp_start, tmp_end; - start = fde->initial_location; - end = fde->initial_location + fde->address_range; + fde_tmp = rb_entry(*rb_node, struct dwarf_fde, node); + BUG_ON(!fde_tmp); - if (pc >= start && pc < end) - break; - } + tmp_start = fde_tmp->initial_location; + tmp_end = fde_tmp->initial_location + fde_tmp->address_range; - /* Couldn't find the entry in the list. */ - if (&fde->link == &dwarf_fde_list) - fde = NULL; + if (pc < tmp_start) { + rb_node = &(*rb_node)->rb_left; + } else { + if (pc < tmp_end) { + fde = fde_tmp; + goto out; + } else + rb_node = &(*rb_node)->rb_right; + } + } +out: spin_unlock_irqrestore(&dwarf_fde_lock, flags); return fde; @@ -552,8 +570,8 @@ extern void ret_from_irq(void); * on the callstack. Each of the lower (older) stack frames are * linked via the "prev" member. */ -struct dwarf_frame * dwarf_unwind_stack(unsigned long pc, - struct dwarf_frame *prev) +struct dwarf_frame *dwarf_unwind_stack(unsigned long pc, + struct dwarf_frame *prev) { struct dwarf_frame *frame; struct dwarf_cie *cie; @@ -708,6 +726,8 @@ bail: static int dwarf_parse_cie(void *entry, void *p, unsigned long len, unsigned char *end, struct module *mod) { + struct rb_node **rb_node = &cie_root.rb_node; + struct rb_node *parent; struct dwarf_cie *cie; unsigned long flags; int count; @@ -802,11 +822,30 @@ static int dwarf_parse_cie(void *entry, void *p, unsigned long len, cie->initial_instructions = p; cie->instructions_end = end; - cie->mod = mod; - /* Add to list */ spin_lock_irqsave(&dwarf_cie_lock, flags); - list_add_tail(&cie->link, &dwarf_cie_list); + + while (*rb_node) { + struct dwarf_cie *cie_tmp; + + cie_tmp = rb_entry(*rb_node, struct dwarf_cie, node); + + parent = *rb_node; + + if (cie->cie_pointer < cie_tmp->cie_pointer) + rb_node = &parent->rb_left; + else if (cie->cie_pointer >= cie_tmp->cie_pointer) + rb_node = &parent->rb_right; + else + WARN_ON(1); + } + + rb_link_node(&cie->node, parent, rb_node); + rb_insert_color(&cie->node, &cie_root); + + if (mod != NULL) + list_add_tail(&cie->link, &mod->arch.cie_list); + spin_unlock_irqrestore(&dwarf_cie_lock, flags); return 0; @@ -816,6 +855,8 @@ static int dwarf_parse_fde(void *entry, u32 entry_type, void *start, unsigned long len, unsigned char *end, struct module *mod) { + struct rb_node **rb_node = &fde_root.rb_node; + struct rb_node *parent; struct dwarf_fde *fde; struct dwarf_cie *cie; unsigned long flags; @@ -863,11 +904,38 @@ static int dwarf_parse_fde(void *entry, u32 entry_type, fde->instructions = p; fde->end = end; - fde->mod = mod; - /* Add to list. */ spin_lock_irqsave(&dwarf_fde_lock, flags); - list_add_tail(&fde->link, &dwarf_fde_list); + + while (*rb_node) { + struct dwarf_fde *fde_tmp; + unsigned long tmp_start, tmp_end; + unsigned long start, end; + + fde_tmp = rb_entry(*rb_node, struct dwarf_fde, node); + + start = fde->initial_location; + end = fde->initial_location + fde->address_range; + + tmp_start = fde_tmp->initial_location; + tmp_end = fde_tmp->initial_location + fde_tmp->address_range; + + parent = *rb_node; + + if (start < tmp_start) + rb_node = &parent->rb_left; + else if (start >= tmp_end) + rb_node = &parent->rb_right; + else + WARN_ON(1); + } + + rb_link_node(&fde->node, parent, rb_node); + rb_insert_color(&fde->node, &fde_root); + + if (mod != NULL) + list_add_tail(&fde->link, &mod->arch.fde_list); + spin_unlock_irqrestore(&dwarf_fde_lock, flags); return 0; @@ -912,19 +980,29 @@ static struct unwinder dwarf_unwinder = { static void dwarf_unwinder_cleanup(void) { - struct dwarf_cie *cie, *cie_tmp; - struct dwarf_fde *fde, *fde_tmp; + struct rb_node **fde_rb_node = &fde_root.rb_node; + struct rb_node **cie_rb_node = &cie_root.rb_node; /* * Deallocate all the memory allocated for the DWARF unwinder. * Traverse all the FDE/CIE lists and remove and free all the * memory associated with those data structures. */ - list_for_each_entry_safe(cie, cie_tmp, &dwarf_cie_list, link) - kfree(cie); + while (*fde_rb_node) { + struct dwarf_fde *fde; - list_for_each_entry_safe(fde, fde_tmp, &dwarf_fde_list, link) + fde = rb_entry(*fde_rb_node, struct dwarf_fde, node); + rb_erase(*fde_rb_node, &fde_root); kfree(fde); + } + + while (*cie_rb_node) { + struct dwarf_cie *cie; + + cie = rb_entry(*cie_rb_node, struct dwarf_cie, node); + rb_erase(*cie_rb_node, &cie_root); + kfree(cie); + } kmem_cache_destroy(dwarf_reg_cachep); kmem_cache_destroy(dwarf_frame_cachep); @@ -1024,6 +1102,8 @@ int module_dwarf_finalize(const Elf_Ehdr *hdr, const Elf_Shdr *sechdrs, /* Did we find the .eh_frame section? */ if (i != hdr->e_shnum) { + INIT_LIST_HEAD(&me->arch.cie_list); + INIT_LIST_HEAD(&me->arch.fde_list); err = dwarf_parse_section((char *)start, (char *)end, me); if (err) { printk(KERN_WARNING "%s: failed to parse DWARF info\n", @@ -1044,38 +1124,26 @@ int module_dwarf_finalize(const Elf_Ehdr *hdr, const Elf_Shdr *sechdrs, */ void module_dwarf_cleanup(struct module *mod) { - struct dwarf_fde *fde; - struct dwarf_cie *cie; + struct dwarf_fde *fde, *ftmp; + struct dwarf_cie *cie, *ctmp; unsigned long flags; spin_lock_irqsave(&dwarf_cie_lock, flags); -again_cie: - list_for_each_entry(cie, &dwarf_cie_list, link) { - if (cie->mod == mod) - break; - } - - if (&cie->link != &dwarf_cie_list) { + list_for_each_entry_safe(cie, ctmp, &mod->arch.cie_list, link) { list_del(&cie->link); + rb_erase(&cie->node, &cie_root); kfree(cie); - goto again_cie; } spin_unlock_irqrestore(&dwarf_cie_lock, flags); spin_lock_irqsave(&dwarf_fde_lock, flags); -again_fde: - list_for_each_entry(fde, &dwarf_fde_list, link) { - if (fde->mod == mod) - break; - } - - if (&fde->link != &dwarf_fde_list) { + list_for_each_entry_safe(fde, ftmp, &mod->arch.fde_list, link) { list_del(&fde->link); + rb_erase(&fde->node, &fde_root); kfree(fde); - goto again_fde; } spin_unlock_irqrestore(&dwarf_fde_lock, flags); @@ -1094,8 +1162,6 @@ again_fde: static int __init dwarf_unwinder_init(void) { int err; - INIT_LIST_HEAD(&dwarf_cie_list); - INIT_LIST_HEAD(&dwarf_fde_list); dwarf_frame_cachep = kmem_cache_create("dwarf_frames", sizeof(struct dwarf_frame), 0, -- cgit v1.1