1/*
2 * Kernel unwinding support
3 *
4 * (c) 2002-2004 Randolph Chung <tausq@debian.org>
5 *
6 * Derived partially from the IA64 implementation. The PA-RISC
7 * Runtime Architecture Document is also a useful reference to
8 * understand what is happening here
9 */
10
11#include <linux/kernel.h>
12#include <linux/init.h>
13#include <linux/sched.h>
14#include <linux/slab.h>
15#include <linux/kallsyms.h>
16
17#include <asm/uaccess.h>
18#include <asm/assembly.h>
19#include <asm/asm-offsets.h>
20#include <asm/ptrace.h>
21
22#include <asm/unwind.h>
23
24/* #define DEBUG 1 */
25#ifdef DEBUG
26#define dbg(x...) printk(x)
27#else
28#define dbg(x...)
29#endif
30
31#define KERNEL_START (KERNEL_BINARY_TEXT_START - 0x1000)
32
33extern struct unwind_table_entry __start___unwind[];
34extern struct unwind_table_entry __stop___unwind[];
35
36static spinlock_t unwind_lock;
37/*
38 * the kernel unwind block is not dynamically allocated so that
39 * we can call unwind_init as early in the bootup process as
40 * possible (before the slab allocator is initialized)
41 */
42static struct unwind_table kernel_unwind_table __read_mostly;
43static LIST_HEAD(unwind_tables);
44
45static inline const struct unwind_table_entry *
46find_unwind_entry_in_table(const struct unwind_table *table, unsigned long addr)
47{
48	const struct unwind_table_entry *e = NULL;
49	unsigned long lo, hi, mid;
50
51	lo = 0;
52	hi = table->length - 1;
53
54	while (lo <= hi) {
55		mid = (hi - lo) / 2 + lo;
56		e = &table->table[mid];
57		if (addr < e->region_start)
58			hi = mid - 1;
59		else if (addr > e->region_end)
60			lo = mid + 1;
61		else
62			return e;
63	}
64
65	return NULL;
66}
67
68static const struct unwind_table_entry *
69find_unwind_entry(unsigned long addr)
70{
71	struct unwind_table *table;
72	const struct unwind_table_entry *e = NULL;
73
74	if (addr >= kernel_unwind_table.start &&
75	    addr <= kernel_unwind_table.end)
76		e = find_unwind_entry_in_table(&kernel_unwind_table, addr);
77	else
78		list_for_each_entry(table, &unwind_tables, list) {
79			if (addr >= table->start &&
80			    addr <= table->end)
81				e = find_unwind_entry_in_table(table, addr);
82			if (e)
83				break;
84		}
85
86	return e;
87}
88
89static void
90unwind_table_init(struct unwind_table *table, const char *name,
91		  unsigned long base_addr, unsigned long gp,
92		  void *table_start, void *table_end)
93{
94	struct unwind_table_entry *start = table_start;
95	struct unwind_table_entry *end =
96		(struct unwind_table_entry *)table_end - 1;
97
98	table->name = name;
99	table->base_addr = base_addr;
100	table->gp = gp;
101	table->start = base_addr + start->region_start;
102	table->end = base_addr + end->region_end;
103	table->table = (struct unwind_table_entry *)table_start;
104	table->length = end - start + 1;
105	INIT_LIST_HEAD(&table->list);
106
107	for (; start <= end; start++) {
108		if (start < end &&
109		    start->region_end > (start+1)->region_start) {
110			printk("WARNING: Out of order unwind entry! %p and %p\n", start, start+1);
111		}
112
113		start->region_start += base_addr;
114		start->region_end += base_addr;
115	}
116}
117
118static void
119unwind_table_sort(struct unwind_table_entry *start,
120		  struct unwind_table_entry *finish)
121{
122	struct unwind_table_entry el, *p, *q;
123
124	for (p = start + 1; p < finish; ++p) {
125		if (p[0].region_start < p[-1].region_start) {
126			el = *p;
127			q = p;
128			do {
129				q[0] = q[-1];
130				--q;
131			} while (q > start &&
132				 el.region_start < q[-1].region_start);
133			*q = el;
134		}
135	}
136}
137
138struct unwind_table *
139unwind_table_add(const char *name, unsigned long base_addr,
140		 unsigned long gp,
141                 void *start, void *end)
142{
143	struct unwind_table *table;
144	unsigned long flags;
145	struct unwind_table_entry *s = (struct unwind_table_entry *)start;
146	struct unwind_table_entry *e = (struct unwind_table_entry *)end;
147
148	unwind_table_sort(s, e);
149
150	table = kmalloc(sizeof(struct unwind_table), GFP_USER);
151	if (table == NULL)
152		return NULL;
153	unwind_table_init(table, name, base_addr, gp, start, end);
154	spin_lock_irqsave(&unwind_lock, flags);
155	list_add_tail(&table->list, &unwind_tables);
156	spin_unlock_irqrestore(&unwind_lock, flags);
157
158	return table;
159}
160
161void unwind_table_remove(struct unwind_table *table)
162{
163	unsigned long flags;
164
165	spin_lock_irqsave(&unwind_lock, flags);
166	list_del(&table->list);
167	spin_unlock_irqrestore(&unwind_lock, flags);
168
169	kfree(table);
170}
171
172/* Called from setup_arch to import the kernel unwind info */
173static int unwind_init(void)
174{
175	long start, stop;
176	register unsigned long gp __asm__ ("r27");
177
178	start = (long)&__start___unwind[0];
179	stop = (long)&__stop___unwind[0];
180
181	spin_lock_init(&unwind_lock);
182
183	printk("unwind_init: start = 0x%lx, end = 0x%lx, entries = %lu\n",
184	    start, stop,
185	    (stop - start) / sizeof(struct unwind_table_entry));
186
187	unwind_table_init(&kernel_unwind_table, "kernel", KERNEL_START,
188			  gp,
189			  &__start___unwind[0], &__stop___unwind[0]);
190	return 0;
191}
192
193#ifdef CONFIG_64BIT
194#define get_func_addr(fptr) fptr[2]
195#else
196#define get_func_addr(fptr) fptr[0]
197#endif
198
199static int unwind_special(struct unwind_frame_info *info, unsigned long pc, int frame_size)
200{
201	void handle_interruption(int, struct pt_regs *);
202	static unsigned long *hi = (unsigned long)&handle_interruption;
203
204	if (pc == get_func_addr(hi)) {
205		struct pt_regs *regs = (struct pt_regs *)(info->sp - frame_size - PT_SZ_ALGN);
206		dbg("Unwinding through handle_interruption()\n");
207		info->prev_sp = regs->gr[30];
208		info->prev_ip = regs->iaoq[0];
209
210		return 1;
211	}
212
213	return 0;
214}
215
216static void unwind_frame_regs(struct unwind_frame_info *info)
217{
218	const struct unwind_table_entry *e;
219	unsigned long npc;
220	unsigned int insn;
221	long frame_size = 0;
222	int looking_for_rp, rpoffset = 0;
223
224	e = find_unwind_entry(info->ip);
225	if (e == NULL) {
226		unsigned long sp;
227		extern char _stext[], _etext[];
228
229		dbg("Cannot find unwind entry for 0x%lx; forced unwinding\n", info->ip);
230
231#ifdef CONFIG_KALLSYMS
232		/* Handle some frequent special cases.... */
233		{
234			char symname[KSYM_NAME_LEN+1];
235			char *modname;
236
237			kallsyms_lookup(info->ip, NULL, NULL, &modname,
238				symname);
239
240			dbg("info->ip = 0x%lx, name = %s\n", info->ip, symname);
241
242			if (strcmp(symname, "_switch_to_ret") == 0) {
243				info->prev_sp = info->sp - CALLEE_SAVE_FRAME_SIZE;
244				info->prev_ip = *(unsigned long *)(info->prev_sp - RP_OFFSET);
245				dbg("_switch_to_ret @ %lx - setting "
246				    "prev_sp=%lx prev_ip=%lx\n",
247				    info->ip, info->prev_sp,
248				    info->prev_ip);
249				return;
250			} else if (strcmp(symname, "ret_from_kernel_thread") == 0 ||
251				   strcmp(symname, "syscall_exit") == 0) {
252				info->prev_ip = info->prev_sp = 0;
253				return;
254			}
255		}
256#endif
257
258		/* Since we are doing the unwinding blind, we don't know if
259		   we are adjusting the stack correctly or extracting the rp
260		   correctly. The rp is checked to see if it belongs to the
261		   kernel text section, if not we assume we don't have a
262		   correct stack frame and we continue to unwind the stack.
263		   This is not quite correct, and will fail for loadable
264		   modules. */
265		sp = info->sp & ~63;
266		do {
267			unsigned long tmp;
268
269			info->prev_sp = sp - 64;
270			info->prev_ip = 0;
271			if (get_user(tmp, (unsigned long *)(info->prev_sp - RP_OFFSET)))
272				break;
273			info->prev_ip = tmp;
274			sp = info->prev_sp;
275		} while (info->prev_ip < (unsigned long)_stext ||
276			 info->prev_ip > (unsigned long)_etext);
277
278		info->rp = 0;
279
280		dbg("analyzing func @ %lx with no unwind info, setting "
281		    "prev_sp=%lx prev_ip=%lx\n", info->ip,
282		    info->prev_sp, info->prev_ip);
283	} else {
284		dbg("e->start = 0x%x, e->end = 0x%x, Save_SP = %d, "
285		    "Save_RP = %d, Millicode = %d size = %u\n",
286		    e->region_start, e->region_end, e->Save_SP, e->Save_RP,
287		    e->Millicode, e->Total_frame_size);
288
289		looking_for_rp = e->Save_RP;
290
291		for (npc = e->region_start;
292		     (frame_size < (e->Total_frame_size << 3) ||
293		      looking_for_rp) &&
294		     npc < info->ip;
295		     npc += 4) {
296
297			insn = *(unsigned int *)npc;
298
299			if ((insn & 0xffffc000) == 0x37de0000 ||
300			    (insn & 0xffe00000) == 0x6fc00000) {
301				/* ldo X(sp), sp, or stwm X,D(sp) */
302				frame_size += (insn & 0x1 ? -1 << 13 : 0) |
303					((insn & 0x3fff) >> 1);
304				dbg("analyzing func @ %lx, insn=%08x @ "
305				    "%lx, frame_size = %ld\n", info->ip,
306				    insn, npc, frame_size);
307			} else if ((insn & 0xffe00008) == 0x73c00008) {
308				/* std,ma X,D(sp) */
309				frame_size += (insn & 0x1 ? -1 << 13 : 0) |
310					(((insn >> 4) & 0x3ff) << 3);
311				dbg("analyzing func @ %lx, insn=%08x @ "
312				    "%lx, frame_size = %ld\n", info->ip,
313				    insn, npc, frame_size);
314			} else if (insn == 0x6bc23fd9) {
315				/* stw rp,-20(sp) */
316				rpoffset = 20;
317				looking_for_rp = 0;
318				dbg("analyzing func @ %lx, insn=stw rp,"
319				    "-20(sp) @ %lx\n", info->ip, npc);
320			} else if (insn == 0x0fc212c1) {
321				/* std rp,-16(sr0,sp) */
322				rpoffset = 16;
323				looking_for_rp = 0;
324				dbg("analyzing func @ %lx, insn=std rp,"
325				    "-16(sp) @ %lx\n", info->ip, npc);
326			}
327		}
328
329		if (!unwind_special(info, e->region_start, frame_size)) {
330			info->prev_sp = info->sp - frame_size;
331			if (e->Millicode)
332				info->rp = info->r31;
333			else if (rpoffset)
334				info->rp = *(unsigned long *)(info->prev_sp - rpoffset);
335			info->prev_ip = info->rp;
336			info->rp = 0;
337		}
338
339		dbg("analyzing func @ %lx, setting prev_sp=%lx "
340		    "prev_ip=%lx npc=%lx\n", info->ip, info->prev_sp,
341		    info->prev_ip, npc);
342	}
343}
344
345void unwind_frame_init(struct unwind_frame_info *info, struct task_struct *t,
346		       struct pt_regs *regs)
347{
348	memset(info, 0, sizeof(struct unwind_frame_info));
349	info->t = t;
350	info->sp = regs->gr[30];
351	info->ip = regs->iaoq[0];
352	info->rp = regs->gr[2];
353	info->r31 = regs->gr[31];
354
355	dbg("(%d) Start unwind from sp=%08lx ip=%08lx\n",
356	    t ? (int)t->pid : -1, info->sp, info->ip);
357}
358
359void unwind_frame_init_from_blocked_task(struct unwind_frame_info *info, struct task_struct *t)
360{
361	struct pt_regs *r = &t->thread.regs;
362	struct pt_regs *r2;
363
364	r2 = kmalloc(sizeof(struct pt_regs), GFP_KERNEL);
365	if (!r2)
366		return;
367	*r2 = *r;
368	r2->gr[30] = r->ksp;
369	r2->iaoq[0] = r->kpc;
370	unwind_frame_init(info, t, r2);
371	kfree(r2);
372}
373
374void unwind_frame_init_running(struct unwind_frame_info *info, struct pt_regs *regs)
375{
376	unwind_frame_init(info, current, regs);
377}
378
379int unwind_once(struct unwind_frame_info *next_frame)
380{
381	unwind_frame_regs(next_frame);
382
383	if (next_frame->prev_sp == 0 ||
384	    next_frame->prev_ip == 0)
385		return -1;
386
387	next_frame->sp = next_frame->prev_sp;
388	next_frame->ip = next_frame->prev_ip;
389	next_frame->prev_sp = 0;
390	next_frame->prev_ip = 0;
391
392	dbg("(%d) Continue unwind to sp=%08lx ip=%08lx\n",
393	    next_frame->t ? (int)next_frame->t->pid : -1,
394	    next_frame->sp, next_frame->ip);
395
396	return 0;
397}
398
399int unwind_to_user(struct unwind_frame_info *info)
400{
401	int ret;
402
403	do {
404		ret = unwind_once(info);
405	} while (!ret && !(info->ip & 3));
406
407	return ret;
408}
409
410module_init(unwind_init);
411