[ARM] 5383/2: unwind: Add core support for ARM stack unwinding

This patch adds the main functionality for parsing the stack unwinding
information generated by the ARM EABI toolchains. The unwinding
information consists of an index with a pair of words per function and a
table with unwinding instructions. For more information, see "Exception
Handling ABI for the ARM Architecture" at:

http://infocenter.arm.com/help/topic/com.arm.doc.subset.swdev.abi/index.html

Signed-off-by: Catalin Marinas <catalin.marinas@arm.com>
Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>

6 files changed, 540 insertions, 0 deletions

diff --git a/arch/arm/boot/compressed/vmlinux.lds.in b/arch/arm/boot/compressed/vmlinux.lds.in
index 153a07e7222..a5924b9b88b 100644
--- a/arch/arm/boot/compressed/vmlinux.lds.in
+++ b/arch/arm/boot/compressed/vmlinux.lds.in
@@ -11,6 +11,11 @@ OUTPUT_ARCH(arm)
 ENTRY(_start)
 SECTIONS
 {
+  /DISCARD/ : {
+    *(.ARM.exidx*)
+    *(.ARM.extab*)
+  }
+
   . = TEXT_START;
   _text = .;
 
diff --git a/arch/arm/include/asm/unwind.h b/arch/arm/include/asm/unwind.h
new file mode 100644
index 00000000000..a5edf421005
--- /dev/null
+++ b/arch/arm/include/asm/unwind.h
@@ -0,0 +1,69 @@
+/*
+ * arch/arm/include/asm/unwind.h
+ *
+ * Copyright (C) 2008 ARM Limited
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef __ASM_UNWIND_H
+#define __ASM_UNWIND_H
+
+#ifndef __ASSEMBLY__
+
+/* Unwind reason code according the the ARM EABI documents */
+enum unwind_reason_code {
+	URC_OK = 0,			/* operation completed successfully */
+	URC_CONTINUE_UNWIND = 8,
+	URC_FAILURE = 9			/* unspecified failure of some kind */
+};
+
+struct unwind_idx {
+	unsigned long addr;
+	unsigned long insn;
+};
+
+struct unwind_table {
+	struct list_head list;
+	struct unwind_idx *start;
+	struct unwind_idx *stop;
+	unsigned long begin_addr;
+	unsigned long end_addr;
+};
+
+extern struct unwind_table *unwind_table_add(unsigned long start,
+					     unsigned long size,
+					     unsigned long text_addr,
+					     unsigned long text_size);
+extern void unwind_table_del(struct unwind_table *tab);
+extern void unwind_backtrace(struct pt_regs *regs, struct task_struct *tsk);
+
+#ifdef CONFIG_ARM_UNWIND
+extern int __init unwind_init(void);
+#else
+static inline int __init unwind_init(void)
+{
+	return 0;
+}
+#endif
+
+#endif	/* !__ASSEMBLY__ */
+
+#ifdef CONFIG_ARM_UNWIND
+#define UNWIND(code...)		code
+#else
+#define UNWIND(code...)
+#endif
+
+#endif	/* __ASM_UNWIND_H */
diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
index 645ec743668..8d21427bb67 100644
--- a/arch/arm/kernel/setup.c
+++ b/arch/arm/kernel/setup.c
@@ -40,6 +40,7 @@
 #include <asm/mach/irq.h>
 #include <asm/mach/time.h>
 #include <asm/traps.h>
+#include <asm/unwind.h>
 
 #include "compat.h"
 #include "atags.h"
@@ -684,6 +685,8 @@ void __init setup_arch(char **cmdline_p)
 	struct machine_desc *mdesc;
 	char *from = default_command_line;
 
+	unwind_init();
+
 	setup_processor();
 	mdesc = setup_machine(machine_arch_type);
 	machine_name = mdesc->name;
diff --git a/arch/arm/kernel/traps.c b/arch/arm/kernel/traps.c
index f68ca0fb0ed..57eb0f6f600 100644
--- a/arch/arm/kernel/traps.c
+++ b/arch/arm/kernel/traps.c
@@ -27,6 +27,7 @@
 #include <asm/system.h>
 #include <asm/unistd.h>
 #include <asm/traps.h>
+#include <asm/unwind.h>
 
 #include "ptrace.h"
 #include "signal.h"
@@ -61,6 +62,7 @@ void dump_backtrace_entry(unsigned long where, unsigned long from, unsigned long
 		dump_mem("Exception stack", frame + 4, frame + 4 + sizeof(struct pt_regs));
 }
 
+#ifndef CONFIG_ARM_UNWIND
 /*
  * Stack pointers should always be within the kernels view of
  * physical memory.  If it is not there, then we can't dump
@@ -74,6 +76,7 @@ static int verify_stack(unsigned long sp)
 
 	return 0;
 }
+#endif
 
 /*
  * Dump out the contents of some memory nicely...
@@ -150,6 +153,12 @@ static void dump_instr(struct pt_regs *regs)
 	set_fs(fs);
 }
 
+#ifdef CONFIG_ARM_UNWIND
+static inline void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
+{
+	unwind_backtrace(regs, tsk);
+}
+#else
 static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 {
 	unsigned int fp, mode;
@@ -184,6 +193,7 @@ static void dump_backtrace(struct pt_regs *regs, struct task_struct *tsk)
 	if (ok)
 		c_backtrace(fp, mode);
 }
+#endif
 
 void dump_stack(void)
 {
diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
new file mode 100644
index 00000000000..1dedc2c7ff4
--- /dev/null
+++ b/arch/arm/kernel/unwind.c
@@ -0,0 +1,434 @@
+/*
+ * arch/arm/kernel/unwind.c
+ *
+ * Copyright (C) 2008 ARM Limited
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ *
+ * Stack unwinding support for ARM
+ *
+ * An ARM EABI version of gcc is required to generate the unwind
+ * tables. For information about the structure of the unwind tables,
+ * see "Exception Handling ABI for the ARM Architecture" at:
+ *
+ * http://infocenter.arm.com/help/topic/com.arm.doc.subset.swdev.abi/index.html
+ */
+
+#include <linux/kernel.h>
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/sched.h>
+#include <linux/slab.h>
+#include <linux/spinlock.h>
+#include <linux/list.h>
+
+#include <asm/stacktrace.h>
+#include <asm/traps.h>
+#include <asm/unwind.h>
+
+/* Dummy functions to avoid linker complaints */
+void __aeabi_unwind_cpp_pr0(void)
+{
+};
+EXPORT_SYMBOL(__aeabi_unwind_cpp_pr0);
+
+void __aeabi_unwind_cpp_pr1(void)
+{
+};
+EXPORT_SYMBOL(__aeabi_unwind_cpp_pr1);
+
+void __aeabi_unwind_cpp_pr2(void)
+{
+};
+EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
+
+struct unwind_ctrl_block {
+	unsigned long vrs[16];		/* virtual register set */
+	unsigned long *insn;		/* pointer to the current instructions word */
+	int entries;			/* number of entries left to interpret */
+	int byte;			/* current byte number in the instructions word */
+};
+
+enum regs {
+	FP = 11,
+	SP = 13,
+	LR = 14,
+	PC = 15
+};
+
+extern struct unwind_idx __start_unwind_idx[];
+extern struct unwind_idx __stop_unwind_idx[];
+
+static DEFINE_SPINLOCK(unwind_lock);
+static LIST_HEAD(unwind_tables);
+
+/* Convert a prel31 symbol to an absolute address */
+#define prel31_to_addr(ptr)				\
+({							\
+	/* sign-extend to 32 bits */			\
+	long offset = (((long)*(ptr)) << 1) >> 1;	\
+	(unsigned long)(ptr) + offset;			\
+})
+
+/*
+ * Binary search in the unwind index. The entries entries are
+ * guaranteed to be sorted in ascending order by the linker.
+ */
+static struct unwind_idx *search_index(unsigned long addr,
+				       struct unwind_idx *first,
+				       struct unwind_idx *last)
+{
+	pr_debug("%s(%08lx, %p, %p)\n", __func__, addr, first, last);
+
+	if (addr < first->addr) {
+		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
+		return NULL;
+	} else if (addr >= last->addr)
+		return last;
+
+	while (first < last - 1) {
+		struct unwind_idx *mid = first + ((last - first + 1) >> 1);
+
+		if (addr < mid->addr)
+			last = mid;
+		else
+			first = mid;
+	}
+
+	return first;
+}
+
+static struct unwind_idx *unwind_find_idx(unsigned long addr)
+{
+	struct unwind_idx *idx = NULL;
+	unsigned long flags;
+
+	pr_debug("%s(%08lx)\n", __func__, addr);
+
+	if (core_kernel_text(addr))
+		/* main unwind table */
+		idx = search_index(addr, __start_unwind_idx,
+				   __stop_unwind_idx - 1);
+	else {
+		/* module unwind tables */
+		struct unwind_table *table;
+
+		spin_lock_irqsave(&unwind_lock, flags);
+		list_for_each_entry(table, &unwind_tables, list) {
+			if (addr >= table->begin_addr &&
+			    addr < table->end_addr) {
+				idx = search_index(addr, table->start,
+						   table->stop - 1);
+				break;
+			}
+		}
+		spin_unlock_irqrestore(&unwind_lock, flags);
+	}
+
+	pr_debug("%s: idx = %p\n", __func__, idx);
+	return idx;
+}
+
+static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
+{
+	unsigned long ret;
+
+	if (ctrl->entries <= 0) {
+		pr_warning("unwind: Corrupt unwind table\n");
+		return 0;
+	}
+
+	ret = (*ctrl->insn >> (ctrl->byte * 8)) & 0xff;
+
+	if (ctrl->byte == 0) {
+		ctrl->insn++;
+		ctrl->entries--;
+		ctrl->byte = 3;
+	} else
+		ctrl->byte--;
+
+	return ret;
+}
+
+/*
+ * Execute the current unwind instruction.
+ */
+static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
+{
+	unsigned long insn = unwind_get_byte(ctrl);
+
+	pr_debug("%s: insn = %08lx\n", __func__, insn);
+
+	if ((insn & 0xc0) == 0x00)
+		ctrl->vrs[SP] += ((insn & 0x3f) << 2) + 4;
+	else if ((insn & 0xc0) == 0x40)
+		ctrl->vrs[SP] -= ((insn & 0x3f) << 2) + 4;
+	else if ((insn & 0xf0) == 0x80) {
+		unsigned long mask;
+		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+		int load_sp, reg = 4;
+
+		insn = (insn << 8) | unwind_get_byte(ctrl);
+		mask = insn & 0x0fff;
+		if (mask == 0) {
+			pr_warning("unwind: 'Refuse to unwind' instruction %04lx\n",
+				   insn);
+			return -URC_FAILURE;
+		}
+
+		/* pop R4-R15 according to mask */
+		load_sp = mask & (1 << (13 - 4));
+		while (mask) {
+			if (mask & 1)
+				ctrl->vrs[reg] = *vsp++;
+			mask >>= 1;
+			reg++;
+		}
+		if (!load_sp)
+			ctrl->vrs[SP] = (unsigned long)vsp;
+	} else if ((insn & 0xf0) == 0x90 &&
+		   (insn & 0x0d) != 0x0d)
+		ctrl->vrs[SP] = ctrl->vrs[insn & 0x0f];
+	else if ((insn & 0xf0) == 0xa0) {
+		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+		int reg;
+
+		/* pop R4-R[4+bbb] */
+		for (reg = 4; reg <= 4 + (insn & 7); reg++)
+			ctrl->vrs[reg] = *vsp++;
+		if (insn & 0x80)
+			ctrl->vrs[14] = *vsp++;
+		ctrl->vrs[SP] = (unsigned long)vsp;
+	} else if (insn == 0xb0) {
+		ctrl->vrs[PC] = ctrl->vrs[LR];
+		/* no further processing */
+		ctrl->entries = 0;
+	} else if (insn == 0xb1) {
+		unsigned long mask = unwind_get_byte(ctrl);
+		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+		int reg = 0;
+
+		if (mask == 0 || mask & 0xf0) {
+			pr_warning("unwind: Spare encoding %04lx\n",
+			       (insn << 8) | mask);
+			return -URC_FAILURE;
+		}
+
+		/* pop R0-R3 according to mask */
+		while (mask) {
+			if (mask & 1)
+				ctrl->vrs[reg] = *vsp++;
+			mask >>= 1;
+			reg++;
+		}
+		ctrl->vrs[SP] = (unsigned long)vsp;
+	} else if (insn == 0xb2) {
+		unsigned long uleb128 = unwind_get_byte(ctrl);
+
+		ctrl->vrs[SP] += 0x204 + (uleb128 << 2);
+	} else {
+		pr_warning("unwind: Unhandled instruction %02lx\n", insn);
+		return -URC_FAILURE;
+	}
+
+	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
+		 ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
+
+	return URC_OK;
+}
+
+/*
+ * Unwind a single frame starting with *sp for the symbol at *pc. It
+ * updates the *pc and *sp with the new values.
+ */
+int unwind_frame(struct stackframe *frame)
+{
+	unsigned long high, low;
+	struct unwind_idx *idx;
+	struct unwind_ctrl_block ctrl;
+
+	/* only go to a higher address on the stack */
+	low = frame->sp;
+	high = ALIGN(low, THREAD_SIZE) + THREAD_SIZE;
+
+	pr_debug("%s(pc = %08lx lr = %08lx sp = %08lx)\n", __func__,
+		 frame->pc, frame->lr, frame->sp);
+
+	if (!kernel_text_address(frame->pc))
+		return -URC_FAILURE;
+
+	idx = unwind_find_idx(frame->pc);
+	if (!idx) {
+		pr_warning("unwind: Index not found %08lx\n", frame->pc);
+		return -URC_FAILURE;
+	}
+
+	ctrl.vrs[FP] = frame->fp;
+	ctrl.vrs[SP] = frame->sp;
+	ctrl.vrs[LR] = frame->lr;
+	ctrl.vrs[PC] = 0;
+
+	if (idx->insn == 1)
+		/* can't unwind */
+		return -URC_FAILURE;
+	else if ((idx->insn & 0x80000000) == 0)
+		/* prel31 to the unwind table */
+		ctrl.insn = (unsigned long *)prel31_to_addr(&idx->insn);
+	else if ((idx->insn & 0xff000000) == 0x80000000)
+		/* only personality routine 0 supported in the index */
+		ctrl.insn = &idx->insn;
+	else {
+		pr_warning("unwind: Unsupported personality routine %08lx in the index at %p\n",
+			   idx->insn, idx);
+		return -URC_FAILURE;
+	}
+
+	/* check the personality routine */
+	if ((*ctrl.insn & 0xff000000) == 0x80000000) {
+		ctrl.byte = 2;
+		ctrl.entries = 1;
+	} else if ((*ctrl.insn & 0xff000000) == 0x81000000) {
+		ctrl.byte = 1;
+		ctrl.entries = 1 + ((*ctrl.insn & 0x00ff0000) >> 16);
+	} else {
+		pr_warning("unwind: Unsupported personality routine %08lx at %p\n",
+			   *ctrl.insn, ctrl.insn);
+		return -URC_FAILURE;
+	}
+
+	while (ctrl.entries > 0) {
+		int urc;
+
+		if (ctrl.vrs[SP] < low || ctrl.vrs[SP] >= high)
+			return -URC_FAILURE;
+		urc = unwind_exec_insn(&ctrl);
+		if (urc < 0)
+			return urc;
+	}
+
+	if (ctrl.vrs[PC] == 0)
+		ctrl.vrs[PC] = ctrl.vrs[LR];
+
+	frame->fp = ctrl.vrs[FP];
+	frame->sp = ctrl.vrs[SP];
+	frame->lr = ctrl.vrs[LR];
+	frame->pc = ctrl.vrs[PC];
+
+	return URC_OK;
+}
+
+void unwind_backtrace(struct pt_regs *regs, struct task_struct *tsk)
+{
+	struct stackframe frame;
+	unsigned long high, low;
+	register unsigned long current_sp asm ("sp");
+
+	pr_debug("%s(regs = %p tsk = %p)\n", __func__, regs, tsk);
+
+	if (!tsk)
+		tsk = current;
+
+	if (regs) {
+		frame.fp = regs->ARM_fp;
+		frame.sp = regs->ARM_sp;
+		frame.lr = regs->ARM_lr;
+		frame.pc = regs->ARM_pc;
+	} else if (tsk == current) {
+		frame.fp = (unsigned long)__builtin_frame_address(0);
+		frame.sp = current_sp;
+		frame.lr = (unsigned long)__builtin_return_address(0);
+		frame.pc = (unsigned long)unwind_backtrace;
+	} else {
+		/* task blocked in __switch_to */
+		frame.fp = thread_saved_fp(tsk);
+		frame.sp = thread_saved_sp(tsk);
+		/*
+		 * The function calling __switch_to cannot be a leaf function
+		 * so LR is recovered from the stack.
+		 */
+		frame.lr = 0;
+		frame.pc = thread_saved_pc(tsk);
+	}
+
+	low = frame.sp & ~(THREAD_SIZE - 1);
+	high = low + THREAD_SIZE;
+
+	while (1) {
+		int urc;
+		unsigned long where = frame.pc;
+
+		urc = unwind_frame(&frame);
+		if (urc < 0)
+			break;
+		dump_backtrace_entry(where, frame.pc, frame.sp - 4);
+	}
+}
+
+struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
+				      unsigned long text_addr,
+				      unsigned long text_size)
+{
+	unsigned long flags;
+	struct unwind_idx *idx;
+	struct unwind_table *tab = kmalloc(sizeof(*tab), GFP_KERNEL);
+
+	pr_debug("%s(%08lx, %08lx, %08lx, %08lx)\n", __func__, start, size,
+		 text_addr, text_size);
+
+	if (!tab)
+		return tab;
+
+	tab->start = (struct unwind_idx *)start;
+	tab->stop = (struct unwind_idx *)(start + size);
+	tab->begin_addr = text_addr;
+	tab->end_addr = text_addr + text_size;
+
+	/* Convert the symbol addresses to absolute values */
+	for (idx = tab->start; idx < tab->stop; idx++)
+		idx->addr = prel31_to_addr(&idx->addr);
+
+	spin_lock_irqsave(&unwind_lock, flags);
+	list_add_tail(&tab->list, &unwind_tables);
+	spin_unlock_irqrestore(&unwind_lock, flags);
+
+	return tab;
+}
+
+void unwind_table_del(struct unwind_table *tab)
+{
+	unsigned long flags;
+
+	if (!tab)
+		return;
+
+	spin_lock_irqsave(&unwind_lock, flags);
+	list_del(&tab->list);
+	spin_unlock_irqrestore(&unwind_lock, flags);
+
+	kfree(tab);
+}
+
+int __init unwind_init(void)
+{
+	struct unwind_idx *idx;
+
+	/* Convert the symbol addresses to absolute values */
+	for (idx = __start_unwind_idx; idx < __stop_unwind_idx; idx++)
+		idx->addr = prel31_to_addr(&idx->addr);
+
+	pr_debug("unwind: ARM stack unwinding initialised\n");
+
+	return 0;
+}
diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
index 00216071eaf..5f664599c94 100644
--- a/arch/arm/kernel/vmlinux.lds.S
+++ b/arch/arm/kernel/vmlinux.lds.S
@@ -80,6 +80,8 @@ SECTIONS
 		EXIT_TEXT
 		EXIT_DATA
 		*(.exitcall.exit)
+		*(.ARM.exidx.exit.text)
+		*(.ARM.extab.exit.text)
 #ifndef CONFIG_MMU
 		*(.fixup)
 		*(__ex_table)
@@ -110,6 +112,23 @@ SECTIONS
 
 	_etext = .;			/* End of text and rodata section */
 
+#ifdef CONFIG_ARM_UNWIND
+	/*
+	 * Stack unwinding tables
+	 */
+	. = ALIGN(8);
+	.ARM.unwind_idx : {
+		__start_unwind_idx = .;
+		*(.ARM.exidx*)
+		__stop_unwind_idx = .;
+	}
+	.ARM.unwind_tab : {
+		__start_unwind_tab = .;
+		*(.ARM.extab*)
+		__stop_unwind_tab = .;
+	}
+#endif
+
 #ifdef CONFIG_XIP_KERNEL
 	__data_loc = ALIGN(4);		/* location in binary */
 	. = PAGE_OFFSET + TEXT_OFFSET;