[deliverable/linux.git] / arch / arm / kernel / unwind.c

/*
 * 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
 */

#ifndef __CHECKER__
#if !defined (__ARM_EABI__)
#warning Your compiler does not have EABI support.
#warning    ARM unwind is known to compile only with EABI compilers.
#warning    Change compiler or disable ARM_UNWIND option.
#elif (__GNUC__ == 4 && __GNUC_MINOR__ <= 2) && !defined(__clang__)
#warning Your compiler is too buggy; it is known to not compile ARM unwind support.
#warning    Change compiler or disable ARM_UNWIND option.
#endif
#endif /* __CHECKER__ */

#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/export.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 */
	const unsigned long *insn;	/* pointer to the current instructions word */
	unsigned long sp_high;		/* highest value of sp allowed */
	/*
	 * 1 : check for stack overflow for each register pop.
	 * 0 : save overhead if there is plenty of stack remaining.
	 */
	int check_each_pop;
	int entries;			/* number of entries left to interpret */
	int byte;			/* current byte number in the instructions word */
};

enum regs {
#ifdef CONFIG_THUMB2_KERNEL
	FP = 7,
#else
	FP = 11,
#endif
	SP = 13,
	LR = 14,
	PC = 15
};

extern const struct unwind_idx __start_unwind_idx[];
static const struct unwind_idx *__origin_unwind_idx;
extern const 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 are
 * guaranteed to be sorted in ascending order by the linker.
 *
 * start = first entry
 * origin = first entry with positive offset (or stop if there is no such entry)
 * stop - 1 = last entry
 */
static const struct unwind_idx *search_index(unsigned long addr,
				       const struct unwind_idx *start,
				       const struct unwind_idx *origin,
				       const struct unwind_idx *stop)
{
	unsigned long addr_prel31;

	pr_debug("%s(%08lx, %p, %p, %p)\n",
			__func__, addr, start, origin, stop);

	/*
	 * only search in the section with the matching sign. This way the
	 * prel31 numbers can be compared as unsigned longs.
	 */
	if (addr < (unsigned long)start)
		/* negative offsets: [start; origin) */
		stop = origin;
	else
		/* positive offsets: [origin; stop) */
		start = origin;

	/* prel31 for address relavive to start */
	addr_prel31 = (addr - (unsigned long)start) & 0x7fffffff;

	while (start < stop - 1) {
		const struct unwind_idx *mid = start + ((stop - start) >> 1);

		/*
		 * As addr_prel31 is relative to start an offset is needed to
		 * make it relative to mid.
		 */
		if (addr_prel31 - ((unsigned long)mid - (unsigned long)start) <
				mid->addr_offset)
			stop = mid;
		else {
			/* keep addr_prel31 relative to start */
			addr_prel31 -= ((unsigned long)mid -
					(unsigned long)start);
			start = mid;
		}
	}

	if (likely(start->addr_offset <= addr_prel31))
		return start;
	else {
		pr_warn("unwind: Unknown symbol address %08lx\n", addr);
		return NULL;
	}
}

static const struct unwind_idx *unwind_find_origin(
		const struct unwind_idx *start, const struct unwind_idx *stop)
{
	pr_debug("%s(%p, %p)\n", __func__, start, stop);
	while (start < stop) {
		const struct unwind_idx *mid = start + ((stop - start) >> 1);

		if (mid->addr_offset >= 0x40000000)
			/* negative offset */
			start = mid + 1;
		else
			/* positive offset */
			stop = mid;
	}
	pr_debug("%s -> %p\n", __func__, stop);
	return stop;
}

static const struct unwind_idx *unwind_find_idx(unsigned long addr)
{
	const struct unwind_idx *idx = NULL;
	unsigned long flags;

	pr_debug("%s(%08lx)\n", __func__, addr);

	if (core_kernel_text(addr)) {
		if (unlikely(!__origin_unwind_idx))
			__origin_unwind_idx =
				unwind_find_origin(__start_unwind_idx,
						__stop_unwind_idx);

		/* main unwind table */
		idx = search_index(addr, __start_unwind_idx,
				   __origin_unwind_idx,
				   __stop_unwind_idx);
	} 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->origin,
						   table->stop);
				/* Move-to-front to exploit common traces */
				list_move(&table->list, &unwind_tables);
				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_warn("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;
}

/* Before poping a register check whether it is feasible or not */
static int unwind_pop_register(struct unwind_ctrl_block *ctrl,
				unsigned long **vsp, unsigned int reg)
{
	if (unlikely(ctrl->check_each_pop))
		if (*vsp >= (unsigned long *)ctrl->sp_high)
			return -URC_FAILURE;

	ctrl->vrs[reg] = *(*vsp)++;
	return URC_OK;
}

/* Helper functions to execute the instructions */
static int unwind_exec_pop_subset_r4_to_r13(struct unwind_ctrl_block *ctrl,
						unsigned long mask)
{
	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
	int load_sp, reg = 4;

	load_sp = mask & (1 << (13 - 4));
	while (mask) {
		if (mask & 1)
			if (unwind_pop_register(ctrl, &vsp, reg))
				return -URC_FAILURE;
		mask >>= 1;
		reg++;
	}
	if (!load_sp)
		ctrl->vrs[SP] = (unsigned long)vsp;

	return URC_OK;
}

static int unwind_exec_pop_r4_to_rN(struct unwind_ctrl_block *ctrl,
					unsigned long insn)
{
	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
	int reg;

	/* pop R4-R[4+bbb] */
	for (reg = 4; reg <= 4 + (insn & 7); reg++)
		if (unwind_pop_register(ctrl, &vsp, reg))
				return -URC_FAILURE;

	if (insn & 0x8)
		if (unwind_pop_register(ctrl, &vsp, 14))
				return -URC_FAILURE;

	ctrl->vrs[SP] = (unsigned long)vsp;

	return URC_OK;
}

static int unwind_exec_pop_subset_r0_to_r3(struct unwind_ctrl_block *ctrl,
						unsigned long mask)
{
	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
	int reg = 0;

	/* pop R0-R3 according to mask */
	while (mask) {
		if (mask & 1)
			if (unwind_pop_register(ctrl, &vsp, reg))
				return -URC_FAILURE;
		mask >>= 1;
		reg++;
	}
	ctrl->vrs[SP] = (unsigned long)vsp;

	return URC_OK;
}

/*
 * Execute the current unwind instruction.
 */
static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
{
	unsigned long insn = unwind_get_byte(ctrl);
	int ret = URC_OK;

	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;

		insn = (insn << 8) | unwind_get_byte(ctrl);
		mask = insn & 0x0fff;
		if (mask == 0) {
			pr_warn("unwind: 'Refuse to unwind' instruction %04lx\n",
				insn);
			return -URC_FAILURE;
		}

		ret = unwind_exec_pop_subset_r4_to_r13(ctrl, mask);
		if (ret)
			goto error;
	} else if ((insn & 0xf0) == 0x90 &&
		   (insn & 0x0d) != 0x0d)
		ctrl->vrs[SP] = ctrl->vrs[insn & 0x0f];
	else if ((insn & 0xf0) == 0xa0) {
		ret = unwind_exec_pop_r4_to_rN(ctrl, insn);
		if (ret)
			goto error;
	} else if (insn == 0xb0) {
		if (ctrl->vrs[PC] == 0)
			ctrl->vrs[PC] = ctrl->vrs[LR];
		/* no further processing */
		ctrl->entries = 0;
	} else if (insn == 0xb1) {
		unsigned long mask = unwind_get_byte(ctrl);

		if (mask == 0 || mask & 0xf0) {
			pr_warn("unwind: Spare encoding %04lx\n",
				(insn << 8) | mask);
			return -URC_FAILURE;
		}

		ret = unwind_exec_pop_subset_r0_to_r3(ctrl, mask);
		if (ret)
			goto error;
	} else if (insn == 0xb2) {
		unsigned long uleb128 = unwind_get_byte(ctrl);

		ctrl->vrs[SP] += 0x204 + (uleb128 << 2);
	} else {
		pr_warn("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]);

error:
	return ret;
}

/*
 * 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 low;
	const struct unwind_idx *idx;
	struct unwind_ctrl_block ctrl;

	/* store the highest address on the stack to avoid crossing it*/
	low = frame->sp;
	ctrl.sp_high = ALIGN(low, 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_warn("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_warn("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_warn("unwind: Unsupported personality routine %08lx at %p\n",
			*ctrl.insn, ctrl.insn);
		return -URC_FAILURE;
	}

	ctrl.check_each_pop = 0;

	while (ctrl.entries > 0) {
		int urc;
		if ((ctrl.sp_high - ctrl.vrs[SP]) < sizeof(ctrl.vrs))
			ctrl.check_each_pop = 1;
		urc = unwind_exec_insn(&ctrl);
		if (urc < 0)
			return urc;
		if (ctrl.vrs[SP] < low || ctrl.vrs[SP] >= ctrl.sp_high)
			return -URC_FAILURE;
	}

	if (ctrl.vrs[PC] == 0)
		ctrl.vrs[PC] = ctrl.vrs[LR];

	/* check for infinite loop */
	if (frame->pc == ctrl.vrs[PC])
		return -URC_FAILURE;

	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;

	pr_debug("%s(regs = %p tsk = %p)\n", __func__, regs, tsk);

	if (!tsk)
		tsk = current;

	if (regs) {
		arm_get_current_stackframe(regs, &frame);
		/* PC might be corrupted, use LR in that case. */
		if (!kernel_text_address(regs->ARM_pc))
			frame.pc = regs->ARM_lr;
	} else if (tsk == current) {
		frame.fp = (unsigned long)__builtin_frame_address(0);
		frame.sp = current_stack_pointer;
		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);
	}

	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_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 = (const struct unwind_idx *)start;
	tab->stop = (const struct unwind_idx *)(start + size);
	tab->origin = unwind_find_origin(tab->start, tab->stop);
	tab->begin_addr = text_addr;
	tab->end_addr = text_addr + text_size;

	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);
}
Commit	Line	Data
bff595c1 CM	1	/*
	2	* arch/arm/kernel/unwind.c
	3	*
	4	* Copyright (C) 2008 ARM Limited
	5	*
	6	* This program is free software; you can redistribute it and/or modify
	7	* it under the terms of the GNU General Public License version 2 as
	8	* published by the Free Software Foundation.
	9	*
	10	* This program is distributed in the hope that it will be useful,
	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	13	* GNU General Public License for more details.
	14	*
	15	* You should have received a copy of the GNU General Public License
	16	* along with this program; if not, write to the Free Software
	17	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	18	*
	19	*
	20	* Stack unwinding support for ARM
	21	*
	22	* An ARM EABI version of gcc is required to generate the unwind
	23	* tables. For information about the structure of the unwind tables,
	24	* see "Exception Handling ABI for the ARM Architecture" at:
	25	*
	26	* http://infocenter.arm.com/help/topic/com.arm.doc.subset.swdev.abi/index.html
	27	*/
	28
830703c7	29	#ifndef __CHECKER__
6603a4fd CS	30	#if !defined (__ARM_EABI__)
	31	#warning Your compiler does not have EABI support.
	32	#warning ARM unwind is known to compile only with EABI compilers.
	33	#warning Change compiler or disable ARM_UNWIND option.
e6b80757	34	#elif (__GNUC__ == 4 && __GNUC_MINOR__ <= 2) && !defined(__clang__)
6603a4fd CS	35	#warning Your compiler is too buggy; it is known to not compile ARM unwind support.
	36	#warning Change compiler or disable ARM_UNWIND option.
	37	#endif
830703c7	38	#endif /* __CHECKER__ */
6603a4fd	39
bff595c1 CM	40	#include <linux/kernel.h>
bff595c1 CM	41	#include <linux/init.h>
ecea4ab6	42	#include <linux/export.h>
bff595c1 CM	43	#include <linux/sched.h>
	44	#include <linux/slab.h>
	45	#include <linux/spinlock.h>
	46	#include <linux/list.h>
	47
	48	#include <asm/stacktrace.h>
	49	#include <asm/traps.h>
	50	#include <asm/unwind.h>
	51
	52	/* Dummy functions to avoid linker complaints */
	53	void __aeabi_unwind_cpp_pr0(void)
	54	{
	55	};
	56	EXPORT_SYMBOL(__aeabi_unwind_cpp_pr0);
	57
	58	void __aeabi_unwind_cpp_pr1(void)
	59	{
	60	};
	61	EXPORT_SYMBOL(__aeabi_unwind_cpp_pr1);
	62
	63	void __aeabi_unwind_cpp_pr2(void)
	64	{
	65	};
	66	EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
	67
	68	struct unwind_ctrl_block {
	69	unsigned long vrs[16]; /* virtual register set */
de66a979	70	const unsigned long insn; / pointer to the current instructions word */
a5134577 AA	71	unsigned long sp_high; /* highest value of sp allowed */
	72	/*
	73	* 1 : check for stack overflow for each register pop.
	74	* 0 : save overhead if there is plenty of stack remaining.
	75	*/
	76	int check_each_pop;
bff595c1 CM	77	int entries; /* number of entries left to interpret */
	78	int byte; /* current byte number in the instructions word */
	79	};
	80
	81	enum regs {
b86040a5 CM	82	#ifdef CONFIG_THUMB2_KERNEL
	83	FP = 7,
	84	#else
bff595c1	85	FP = 11,
b86040a5	86	#endif
bff595c1 CM	87	SP = 13,
	88	LR = 14,
	89	PC = 15
	90	};
	91
de66a979 UKK	92	extern const struct unwind_idx __start_unwind_idx[];
	93	static const struct unwind_idx *__origin_unwind_idx;
	94	extern const struct unwind_idx __stop_unwind_idx[];
bff595c1 CM	95
	96	static DEFINE_SPINLOCK(unwind_lock);
	97	static LIST_HEAD(unwind_tables);
	98
	99	/* Convert a prel31 symbol to an absolute address */
	100	#define prel31_to_addr(ptr) \
	101	({ \
	102	/* sign-extend to 32 bits */ \
	103	long offset = (((long)*(ptr)) << 1) >> 1; \
	104	(unsigned long)(ptr) + offset; \
	105	})
	106
	107	/*
de66a979	108	* Binary search in the unwind index. The entries are
bff595c1	109	* guaranteed to be sorted in ascending order by the linker.
de66a979 UKK	110	*
	111	* start = first entry
	112	* origin = first entry with positive offset (or stop if there is no such entry)
	113	* stop - 1 = last entry
bff595c1	114	*/
de66a979 UKK	115	static const struct unwind_idx *search_index(unsigned long addr,
	116	const struct unwind_idx *start,
	117	const struct unwind_idx *origin,
	118	const struct unwind_idx *stop)
bff595c1	119	{
de66a979 UKK	120	unsigned long addr_prel31;
	121
	122	pr_debug("%s(%08lx, %p, %p, %p)\n",
	123	__func__, addr, start, origin, stop);
	124
	125	/*
	126	* only search in the section with the matching sign. This way the
	127	* prel31 numbers can be compared as unsigned longs.
	128	*/
	129	if (addr < (unsigned long)start)
	130	/* negative offsets: [start; origin) */
	131	stop = origin;
	132	else
	133	/* positive offsets: [origin; stop) */
	134	start = origin;
	135
	136	/* prel31 for address relavive to start */
	137	addr_prel31 = (addr - (unsigned long)start) & 0x7fffffff;
bff595c1	138
de66a979 UKK	139	while (start < stop - 1) {
	140	const struct unwind_idx *mid = start + ((stop - start) >> 1);
	141
	142	/*
	143	* As addr_prel31 is relative to start an offset is needed to
	144	* make it relative to mid.
	145	*/
	146	if (addr_prel31 - ((unsigned long)mid - (unsigned long)start) <
	147	mid->addr_offset)
	148	stop = mid;
	149	else {
	150	/* keep addr_prel31 relative to start */
	151	addr_prel31 -= ((unsigned long)mid -
	152	(unsigned long)start);
	153	start = mid;
	154	}
	155	}
	156
	157	if (likely(start->addr_offset <= addr_prel31))
	158	return start;
	159	else {
8b521cb2	160	pr_warn("unwind: Unknown symbol address %08lx\n", addr);
bff595c1	161	return NULL;
de66a979 UKK	162	}
de66a979 UKK	163	}
bff595c1	164
de66a979 UKK	165	static const struct unwind_idx *unwind_find_origin(
	166	const struct unwind_idx start, const struct unwind_idx stop)
	167	{
	168	pr_debug("%s(%p, %p)\n", __func__, start, stop);
ddf5a25c	169	while (start < stop) {
de66a979	170	const struct unwind_idx *mid = start + ((stop - start) >> 1);
bff595c1	171
de66a979 UKK	172	if (mid->addr_offset >= 0x40000000)
de66a979 UKK	173	/* negative offset */
ddf5a25c	174	start = mid + 1;
bff595c1	175	else
de66a979 UKK	176	/* positive offset */
de66a979 UKK	177	stop = mid;
bff595c1	178	}
de66a979 UKK	179	pr_debug("%s -> %p\n", __func__, stop);
de66a979 UKK	180	return stop;
bff595c1 CM	181	}
bff595c1 CM	182
de66a979	183	static const struct unwind_idx *unwind_find_idx(unsigned long addr)
bff595c1	184	{
de66a979	185	const struct unwind_idx *idx = NULL;
bff595c1 CM	186	unsigned long flags;
	187
	188	pr_debug("%s(%08lx)\n", __func__, addr);
	189
de66a979 UKK	190	if (core_kernel_text(addr)) {
	191	if (unlikely(!__origin_unwind_idx))
	192	__origin_unwind_idx =
	193	unwind_find_origin(__start_unwind_idx,
	194	__stop_unwind_idx);
	195
bff595c1 CM	196	/* main unwind table */
bff595c1 CM	197	idx = search_index(addr, __start_unwind_idx,
de66a979 UKK	198	__origin_unwind_idx,
	199	__stop_unwind_idx);
	200	} else {
bff595c1 CM	201	/* module unwind tables */
	202	struct unwind_table *table;
	203
	204	spin_lock_irqsave(&unwind_lock, flags);
	205	list_for_each_entry(table, &unwind_tables, list) {
	206	if (addr >= table->begin_addr &&
	207	addr < table->end_addr) {
	208	idx = search_index(addr, table->start,
de66a979 UKK	209	table->origin,
de66a979 UKK	210	table->stop);
5333a3de PC	211	/* Move-to-front to exploit common traces */
5333a3de PC	212	list_move(&table->list, &unwind_tables);
bff595c1 CM	213	break;
	214	}
	215	}
	216	spin_unlock_irqrestore(&unwind_lock, flags);
	217	}
	218
	219	pr_debug("%s: idx = %p\n", __func__, idx);
	220	return idx;
	221	}
	222
	223	static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
	224	{
	225	unsigned long ret;
	226
	227	if (ctrl->entries <= 0) {
8b521cb2	228	pr_warn("unwind: Corrupt unwind table\n");
bff595c1 CM	229	return 0;
	230	}
	231
	232	ret = (ctrl->insn >> (ctrl->byte 8)) & 0xff;
	233
	234	if (ctrl->byte == 0) {
	235	ctrl->insn++;
	236	ctrl->entries--;
	237	ctrl->byte = 3;
	238	} else
	239	ctrl->byte--;
	240
	241	return ret;
	242	}
	243
a5134577 AA	244	/* Before poping a register check whether it is feasible or not */
	245	static int unwind_pop_register(struct unwind_ctrl_block *ctrl,
	246	unsigned long **vsp, unsigned int reg)
	247	{
	248	if (unlikely(ctrl->check_each_pop))
	249	if (vsp >= (unsigned long )ctrl->sp_high)
	250	return -URC_FAILURE;
	251
	252	ctrl->vrs[reg] = (vsp)++;
	253	return URC_OK;
	254	}
	255
	256	/* Helper functions to execute the instructions */
	257	static int unwind_exec_pop_subset_r4_to_r13(struct unwind_ctrl_block *ctrl,
	258	unsigned long mask)
	259	{
	260	unsigned long vsp = (unsigned long )ctrl->vrs[SP];
	261	int load_sp, reg = 4;
	262
	263	load_sp = mask & (1 << (13 - 4));
	264	while (mask) {
	265	if (mask & 1)
	266	if (unwind_pop_register(ctrl, &vsp, reg))
	267	return -URC_FAILURE;
	268	mask >>= 1;
	269	reg++;
	270	}
	271	if (!load_sp)
	272	ctrl->vrs[SP] = (unsigned long)vsp;
	273
	274	return URC_OK;
	275	}
	276
	277	static int unwind_exec_pop_r4_to_rN(struct unwind_ctrl_block *ctrl,
	278	unsigned long insn)
	279	{
	280	unsigned long vsp = (unsigned long )ctrl->vrs[SP];
	281	int reg;
	282
	283	/* pop R4-R[4+bbb] */
	284	for (reg = 4; reg <= 4 + (insn & 7); reg++)
	285	if (unwind_pop_register(ctrl, &vsp, reg))
	286	return -URC_FAILURE;
	287
8203d5b6	288	if (insn & 0x8)
a5134577 AA	289	if (unwind_pop_register(ctrl, &vsp, 14))
	290	return -URC_FAILURE;
	291
	292	ctrl->vrs[SP] = (unsigned long)vsp;
	293
	294	return URC_OK;
	295	}
	296
	297	static int unwind_exec_pop_subset_r0_to_r3(struct unwind_ctrl_block *ctrl,
	298	unsigned long mask)
	299	{
	300	unsigned long vsp = (unsigned long )ctrl->vrs[SP];
	301	int reg = 0;
	302
	303	/* pop R0-R3 according to mask */
	304	while (mask) {
	305	if (mask & 1)
	306	if (unwind_pop_register(ctrl, &vsp, reg))
	307	return -URC_FAILURE;
	308	mask >>= 1;
	309	reg++;
	310	}
	311	ctrl->vrs[SP] = (unsigned long)vsp;
	312
	313	return URC_OK;
	314	}
	315
bff595c1 CM	316	/*
	317	* Execute the current unwind instruction.
	318	*/
	319	static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
	320	{
	321	unsigned long insn = unwind_get_byte(ctrl);
a5134577	322	int ret = URC_OK;
bff595c1 CM	323
	324	pr_debug("%s: insn = %08lx\n", __func__, insn);
	325
	326	if ((insn & 0xc0) == 0x00)
	327	ctrl->vrs[SP] += ((insn & 0x3f) << 2) + 4;
	328	else if ((insn & 0xc0) == 0x40)
	329	ctrl->vrs[SP] -= ((insn & 0x3f) << 2) + 4;
	330	else if ((insn & 0xf0) == 0x80) {
	331	unsigned long mask;
bff595c1 CM	332
	333	insn = (insn << 8) \| unwind_get_byte(ctrl);
	334	mask = insn & 0x0fff;
	335	if (mask == 0) {
8b521cb2 JP	336	pr_warn("unwind: 'Refuse to unwind' instruction %04lx\n",
8b521cb2 JP	337	insn);
bff595c1 CM	338	return -URC_FAILURE;
	339	}
	340
a5134577 AA	341	ret = unwind_exec_pop_subset_r4_to_r13(ctrl, mask);
	342	if (ret)
	343	goto error;
bff595c1 CM	344	} else if ((insn & 0xf0) == 0x90 &&
	345	(insn & 0x0d) != 0x0d)
	346	ctrl->vrs[SP] = ctrl->vrs[insn & 0x0f];
	347	else if ((insn & 0xf0) == 0xa0) {
a5134577 AA	348	ret = unwind_exec_pop_r4_to_rN(ctrl, insn);
	349	if (ret)
	350	goto error;
bff595c1	351	} else if (insn == 0xb0) {
c894ed69 CM	352	if (ctrl->vrs[PC] == 0)
c894ed69 CM	353	ctrl->vrs[PC] = ctrl->vrs[LR];
bff595c1 CM	354	/* no further processing */
	355	ctrl->entries = 0;
	356	} else if (insn == 0xb1) {
	357	unsigned long mask = unwind_get_byte(ctrl);
bff595c1 CM	358
bff595c1 CM	359	if (mask == 0 \|\| mask & 0xf0) {
8b521cb2 JP	360	pr_warn("unwind: Spare encoding %04lx\n",
8b521cb2 JP	361	(insn << 8) \| mask);
bff595c1 CM	362	return -URC_FAILURE;
	363	}
	364
a5134577 AA	365	ret = unwind_exec_pop_subset_r0_to_r3(ctrl, mask);
	366	if (ret)
	367	goto error;
bff595c1 CM	368	} else if (insn == 0xb2) {
	369	unsigned long uleb128 = unwind_get_byte(ctrl);
	370
	371	ctrl->vrs[SP] += 0x204 + (uleb128 << 2);
	372	} else {
8b521cb2	373	pr_warn("unwind: Unhandled instruction %02lx\n", insn);
bff595c1 CM	374	return -URC_FAILURE;
	375	}
	376
	377	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
	378	ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
	379
a5134577 AA	380	error:
a5134577 AA	381	return ret;
bff595c1 CM	382	}
	383
	384	/*
	385	* Unwind a single frame starting with sp for the symbol at pc. It
	386	* updates the pc and sp with the new values.
	387	*/
	388	int unwind_frame(struct stackframe *frame)
	389	{
a5134577	390	unsigned long low;
de66a979	391	const struct unwind_idx *idx;
bff595c1 CM	392	struct unwind_ctrl_block ctrl;
bff595c1 CM	393
a5134577	394	/* store the highest address on the stack to avoid crossing it*/
bff595c1	395	low = frame->sp;
a5134577	396	ctrl.sp_high = ALIGN(low, THREAD_SIZE);
bff595c1 CM	397
	398	pr_debug("%s(pc = %08lx lr = %08lx sp = %08lx)\n", __func__,
	399	frame->pc, frame->lr, frame->sp);
	400
	401	if (!kernel_text_address(frame->pc))
	402	return -URC_FAILURE;
	403
	404	idx = unwind_find_idx(frame->pc);
	405	if (!idx) {
8b521cb2	406	pr_warn("unwind: Index not found %08lx\n", frame->pc);
bff595c1 CM	407	return -URC_FAILURE;
	408	}
	409
	410	ctrl.vrs[FP] = frame->fp;
	411	ctrl.vrs[SP] = frame->sp;
	412	ctrl.vrs[LR] = frame->lr;
	413	ctrl.vrs[PC] = 0;
	414
	415	if (idx->insn == 1)
	416	/* can't unwind */
	417	return -URC_FAILURE;
	418	else if ((idx->insn & 0x80000000) == 0)
	419	/* prel31 to the unwind table */
	420	ctrl.insn = (unsigned long *)prel31_to_addr(&idx->insn);
	421	else if ((idx->insn & 0xff000000) == 0x80000000)
	422	/* only personality routine 0 supported in the index */
	423	ctrl.insn = &idx->insn;
	424	else {
8b521cb2 JP	425	pr_warn("unwind: Unsupported personality routine %08lx in the index at %p\n",
8b521cb2 JP	426	idx->insn, idx);
bff595c1 CM	427	return -URC_FAILURE;
	428	}
	429
	430	/* check the personality routine */
	431	if ((*ctrl.insn & 0xff000000) == 0x80000000) {
	432	ctrl.byte = 2;
	433	ctrl.entries = 1;
	434	} else if ((*ctrl.insn & 0xff000000) == 0x81000000) {
	435	ctrl.byte = 1;
	436	ctrl.entries = 1 + ((*ctrl.insn & 0x00ff0000) >> 16);
	437	} else {
8b521cb2 JP	438	pr_warn("unwind: Unsupported personality routine %08lx at %p\n",
8b521cb2 JP	439	*ctrl.insn, ctrl.insn);
bff595c1 CM	440	return -URC_FAILURE;
	441	}
	442
a5134577 AA	443	ctrl.check_each_pop = 0;
a5134577 AA	444
bff595c1	445	while (ctrl.entries > 0) {
a5134577 AA	446	int urc;
	447	if ((ctrl.sp_high - ctrl.vrs[SP]) < sizeof(ctrl.vrs))
	448	ctrl.check_each_pop = 1;
	449	urc = unwind_exec_insn(&ctrl);
bff595c1 CM	450	if (urc < 0)
bff595c1 CM	451	return urc;
a5134577	452	if (ctrl.vrs[SP] < low \|\| ctrl.vrs[SP] >= ctrl.sp_high)
c894ed69	453	return -URC_FAILURE;
bff595c1 CM	454	}
	455
	456	if (ctrl.vrs[PC] == 0)
	457	ctrl.vrs[PC] = ctrl.vrs[LR];
	458
c894ed69 CM	459	/* check for infinite loop */
	460	if (frame->pc == ctrl.vrs[PC])
	461	return -URC_FAILURE;
	462
bff595c1 CM	463	frame->fp = ctrl.vrs[FP];
	464	frame->sp = ctrl.vrs[SP];
	465	frame->lr = ctrl.vrs[LR];
	466	frame->pc = ctrl.vrs[PC];
	467
	468	return URC_OK;
	469	}
	470
	471	void unwind_backtrace(struct pt_regs regs, struct task_struct tsk)
	472	{
	473	struct stackframe frame;
bff595c1 CM	474
	475	pr_debug("%s(regs = %p tsk = %p)\n", __func__, regs, tsk);
	476
	477	if (!tsk)
	478	tsk = current;
	479
	480	if (regs) {
c8bee0ad	481	arm_get_current_stackframe(regs, &frame);
51d47999	482	/* PC might be corrupted, use LR in that case. */
c8bee0ad NB	483	if (!kernel_text_address(regs->ARM_pc))
c8bee0ad NB	484	frame.pc = regs->ARM_lr;
bff595c1 CM	485	} else if (tsk == current) {
bff595c1 CM	486	frame.fp = (unsigned long)__builtin_frame_address(0);
0bf4954f	487	frame.sp = current_stack_pointer;
bff595c1 CM	488	frame.lr = (unsigned long)__builtin_return_address(0);
	489	frame.pc = (unsigned long)unwind_backtrace;
	490	} else {
	491	/* task blocked in __switch_to */
	492	frame.fp = thread_saved_fp(tsk);
	493	frame.sp = thread_saved_sp(tsk);
	494	/*
	495	* The function calling __switch_to cannot be a leaf function
	496	* so LR is recovered from the stack.
	497	*/
	498	frame.lr = 0;
	499	frame.pc = thread_saved_pc(tsk);
	500	}
	501
bff595c1 CM	502	while (1) {
	503	int urc;
	504	unsigned long where = frame.pc;
	505
	506	urc = unwind_frame(&frame);
	507	if (urc < 0)
	508	break;
	509	dump_backtrace_entry(where, frame.pc, frame.sp - 4);
	510	}
	511	}
	512
	513	struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
	514	unsigned long text_addr,
	515	unsigned long text_size)
	516	{
	517	unsigned long flags;
bff595c1 CM	518	struct unwind_table tab = kmalloc(sizeof(tab), GFP_KERNEL);
	519
	520	pr_debug("%s(%08lx, %08lx, %08lx, %08lx)\n", __func__, start, size,
	521	text_addr, text_size);
	522
	523	if (!tab)
	524	return tab;
	525
de66a979 UKK	526	tab->start = (const struct unwind_idx *)start;
	527	tab->stop = (const struct unwind_idx *)(start + size);
	528	tab->origin = unwind_find_origin(tab->start, tab->stop);
bff595c1 CM	529	tab->begin_addr = text_addr;
	530	tab->end_addr = text_addr + text_size;
	531
bff595c1 CM	532	spin_lock_irqsave(&unwind_lock, flags);
	533	list_add_tail(&tab->list, &unwind_tables);
	534	spin_unlock_irqrestore(&unwind_lock, flags);
	535
	536	return tab;
	537	}
	538
	539	void unwind_table_del(struct unwind_table *tab)
	540	{
	541	unsigned long flags;
	542
	543	if (!tab)
	544	return;
	545
	546	spin_lock_irqsave(&unwind_lock, flags);
	547	list_del(&tab->list);
	548	spin_unlock_irqrestore(&unwind_lock, flags);
	549
	550	kfree(tab);
	551	}