1/*
2 * Copyright (C) 2007-2010, 2011-2012 Synopsys, Inc. (www.synopsys.com)
3 * Copyright (C) 2002-2006 Novell, Inc.
4 *	Jan Beulich <jbeulich@novell.com>
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 * A simple API for unwinding kernel stacks.  This is used for
11 * debugging and error reporting purposes.  The kernel doesn't need
12 * full-blown stack unwinding with all the bells and whistles, so there
13 * is not much point in implementing the full Dwarf2 unwind API.
14 */
15
16#include <linux/sched.h>
17#include <linux/module.h>
18#include <linux/bootmem.h>
19#include <linux/sort.h>
20#include <linux/slab.h>
21#include <linux/stop_machine.h>
22#include <linux/uaccess.h>
23#include <linux/ptrace.h>
24#include <asm/sections.h>
25#include <asm/unaligned.h>
26#include <asm/unwind.h>
27
28extern char __start_unwind[], __end_unwind[];
29/* extern const u8 __start_unwind_hdr[], __end_unwind_hdr[];*/
30
31/* #define UNWIND_DEBUG */
32
33#ifdef UNWIND_DEBUG
34int dbg_unw;
35#define unw_debug(fmt, ...)			\
36do {						\
37	if (dbg_unw)				\
38		pr_info(fmt, ##__VA_ARGS__);	\
39} while (0);
40#else
41#define unw_debug(fmt, ...)
42#endif
43
44#define MAX_STACK_DEPTH 8
45
46#define EXTRA_INFO(f) { \
47		BUILD_BUG_ON_ZERO(offsetof(struct unwind_frame_info, f) \
48				% FIELD_SIZEOF(struct unwind_frame_info, f)) \
49				+ offsetof(struct unwind_frame_info, f) \
50				/ FIELD_SIZEOF(struct unwind_frame_info, f), \
51				FIELD_SIZEOF(struct unwind_frame_info, f) \
52	}
53#define PTREGS_INFO(f) EXTRA_INFO(regs.f)
54
55static const struct {
56	unsigned offs:BITS_PER_LONG / 2;
57	unsigned width:BITS_PER_LONG / 2;
58} reg_info[] = {
59UNW_REGISTER_INFO};
60
61#undef PTREGS_INFO
62#undef EXTRA_INFO
63
64#ifndef REG_INVALID
65#define REG_INVALID(r) (reg_info[r].width == 0)
66#endif
67
68#define DW_CFA_nop                          0x00
69#define DW_CFA_set_loc                      0x01
70#define DW_CFA_advance_loc1                 0x02
71#define DW_CFA_advance_loc2                 0x03
72#define DW_CFA_advance_loc4                 0x04
73#define DW_CFA_offset_extended              0x05
74#define DW_CFA_restore_extended             0x06
75#define DW_CFA_undefined                    0x07
76#define DW_CFA_same_value                   0x08
77#define DW_CFA_register                     0x09
78#define DW_CFA_remember_state               0x0a
79#define DW_CFA_restore_state                0x0b
80#define DW_CFA_def_cfa                      0x0c
81#define DW_CFA_def_cfa_register             0x0d
82#define DW_CFA_def_cfa_offset               0x0e
83#define DW_CFA_def_cfa_expression           0x0f
84#define DW_CFA_expression                   0x10
85#define DW_CFA_offset_extended_sf           0x11
86#define DW_CFA_def_cfa_sf                   0x12
87#define DW_CFA_def_cfa_offset_sf            0x13
88#define DW_CFA_val_offset                   0x14
89#define DW_CFA_val_offset_sf                0x15
90#define DW_CFA_val_expression               0x16
91#define DW_CFA_lo_user                      0x1c
92#define DW_CFA_GNU_window_save              0x2d
93#define DW_CFA_GNU_args_size                0x2e
94#define DW_CFA_GNU_negative_offset_extended 0x2f
95#define DW_CFA_hi_user                      0x3f
96
97#define DW_EH_PE_FORM     0x07
98#define DW_EH_PE_native   0x00
99#define DW_EH_PE_leb128   0x01
100#define DW_EH_PE_data2    0x02
101#define DW_EH_PE_data4    0x03
102#define DW_EH_PE_data8    0x04
103#define DW_EH_PE_signed   0x08
104#define DW_EH_PE_ADJUST   0x70
105#define DW_EH_PE_abs      0x00
106#define DW_EH_PE_pcrel    0x10
107#define DW_EH_PE_textrel  0x20
108#define DW_EH_PE_datarel  0x30
109#define DW_EH_PE_funcrel  0x40
110#define DW_EH_PE_aligned  0x50
111#define DW_EH_PE_indirect 0x80
112#define DW_EH_PE_omit     0xff
113
114typedef unsigned long uleb128_t;
115typedef signed long sleb128_t;
116
117static struct unwind_table {
118	struct {
119		unsigned long pc;
120		unsigned long range;
121	} core, init;
122	const void *address;
123	unsigned long size;
124	const unsigned char *header;
125	unsigned long hdrsz;
126	struct unwind_table *link;
127	const char *name;
128} root_table;
129
130struct unwind_item {
131	enum item_location {
132		Nowhere,
133		Memory,
134		Register,
135		Value
136	} where;
137	uleb128_t value;
138};
139
140struct unwind_state {
141	uleb128_t loc, org;
142	const u8 *cieStart, *cieEnd;
143	uleb128_t codeAlign;
144	sleb128_t dataAlign;
145	struct cfa {
146		uleb128_t reg, offs;
147	} cfa;
148	struct unwind_item regs[ARRAY_SIZE(reg_info)];
149	unsigned stackDepth:8;
150	unsigned version:8;
151	const u8 *label;
152	const u8 *stack[MAX_STACK_DEPTH];
153};
154
155static const struct cfa badCFA = { ARRAY_SIZE(reg_info), 1 };
156
157static struct unwind_table *find_table(unsigned long pc)
158{
159	struct unwind_table *table;
160
161	for (table = &root_table; table; table = table->link)
162		if ((pc >= table->core.pc
163		     && pc < table->core.pc + table->core.range)
164		    || (pc >= table->init.pc
165			&& pc < table->init.pc + table->init.range))
166			break;
167
168	return table;
169}
170
171static unsigned long read_pointer(const u8 **pLoc,
172				  const void *end, signed ptrType);
173
174static void init_unwind_table(struct unwind_table *table, const char *name,
175			      const void *core_start, unsigned long core_size,
176			      const void *init_start, unsigned long init_size,
177			      const void *table_start, unsigned long table_size,
178			      const u8 *header_start, unsigned long header_size)
179{
180	const u8 *ptr = header_start + 4;
181	const u8 *end = header_start + header_size;
182
183	table->core.pc = (unsigned long)core_start;
184	table->core.range = core_size;
185	table->init.pc = (unsigned long)init_start;
186	table->init.range = init_size;
187	table->address = table_start;
188	table->size = table_size;
189
190	/* See if the linker provided table looks valid. */
191	if (header_size <= 4
192	    || header_start[0] != 1
193	    || (void *)read_pointer(&ptr, end, header_start[1]) != table_start
194	    || header_start[2] == DW_EH_PE_omit
195	    || read_pointer(&ptr, end, header_start[2]) <= 0
196	    || header_start[3] == DW_EH_PE_omit)
197		header_start = NULL;
198
199	table->hdrsz = header_size;
200	smp_wmb();
201	table->header = header_start;
202	table->link = NULL;
203	table->name = name;
204}
205
206void __init arc_unwind_init(void)
207{
208	init_unwind_table(&root_table, "kernel", _text, _end - _text, NULL, 0,
209			  __start_unwind, __end_unwind - __start_unwind,
210			  NULL, 0);
211	  /*__start_unwind_hdr, __end_unwind_hdr - __start_unwind_hdr);*/
212}
213
214static const u32 bad_cie, not_fde;
215static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *);
216static signed fde_pointer_type(const u32 *cie);
217
218struct eh_frame_hdr_table_entry {
219	unsigned long start, fde;
220};
221
222static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
223{
224	const struct eh_frame_hdr_table_entry *e1 = p1;
225	const struct eh_frame_hdr_table_entry *e2 = p2;
226
227	return (e1->start > e2->start) - (e1->start < e2->start);
228}
229
230static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
231{
232	struct eh_frame_hdr_table_entry *e1 = p1;
233	struct eh_frame_hdr_table_entry *e2 = p2;
234	unsigned long v;
235
236	v = e1->start;
237	e1->start = e2->start;
238	e2->start = v;
239	v = e1->fde;
240	e1->fde = e2->fde;
241	e2->fde = v;
242}
243
244static void __init setup_unwind_table(struct unwind_table *table,
245				      void *(*alloc) (unsigned long))
246{
247	const u8 *ptr;
248	unsigned long tableSize = table->size, hdrSize;
249	unsigned n;
250	const u32 *fde;
251	struct {
252		u8 version;
253		u8 eh_frame_ptr_enc;
254		u8 fde_count_enc;
255		u8 table_enc;
256		unsigned long eh_frame_ptr;
257		unsigned int fde_count;
258		struct eh_frame_hdr_table_entry table[];
259	} __attribute__ ((__packed__)) *header;
260
261	if (table->header)
262		return;
263
264	if (table->hdrsz)
265		pr_warn(".eh_frame_hdr for '%s' present but unusable\n",
266			table->name);
267
268	if (tableSize & (sizeof(*fde) - 1))
269		return;
270
271	for (fde = table->address, n = 0;
272	     tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
273	     tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
274		const u32 *cie = cie_for_fde(fde, table);
275		signed ptrType;
276
277		if (cie == &not_fde)
278			continue;
279		if (cie == NULL || cie == &bad_cie)
280			return;
281		ptrType = fde_pointer_type(cie);
282		if (ptrType < 0)
283			return;
284
285		ptr = (const u8 *)(fde + 2);
286		if (!read_pointer(&ptr, (const u8 *)(fde + 1) + *fde,
287								ptrType)) {
288			/* FIXME_Rajesh We have 4 instances of null addresses
289			 * instead of the initial loc addr
290			 * return;
291			 */
292			WARN(1, "unwinder: FDE->initial_location NULL %p\n",
293				(const u8 *)(fde + 1) + *fde);
294		}
295		++n;
296	}
297
298	if (tableSize || !n)
299		return;
300
301	hdrSize = 4 + sizeof(unsigned long) + sizeof(unsigned int)
302	    + 2 * n * sizeof(unsigned long);
303	header = alloc(hdrSize);
304	if (!header)
305		return;
306	header->version = 1;
307	header->eh_frame_ptr_enc = DW_EH_PE_abs | DW_EH_PE_native;
308	header->fde_count_enc = DW_EH_PE_abs | DW_EH_PE_data4;
309	header->table_enc = DW_EH_PE_abs | DW_EH_PE_native;
310	put_unaligned((unsigned long)table->address, &header->eh_frame_ptr);
311	BUILD_BUG_ON(offsetof(typeof(*header), fde_count)
312		     % __alignof(typeof(header->fde_count)));
313	header->fde_count = n;
314
315	BUILD_BUG_ON(offsetof(typeof(*header), table)
316		     % __alignof(typeof(*header->table)));
317	for (fde = table->address, tableSize = table->size, n = 0;
318	     tableSize;
319	     tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
320		/* const u32 *cie = fde + 1 - fde[1] / sizeof(*fde); */
321		const u32 *cie = (const u32 *)(fde[1]);
322
323		if (fde[1] == 0xffffffff)
324			continue;	/* this is a CIE */
325		ptr = (const u8 *)(fde + 2);
326		header->table[n].start = read_pointer(&ptr,
327						      (const u8 *)(fde + 1) +
328						      *fde,
329						      fde_pointer_type(cie));
330		header->table[n].fde = (unsigned long)fde;
331		++n;
332	}
333	WARN_ON(n != header->fde_count);
334
335	sort(header->table,
336	     n,
337	     sizeof(*header->table),
338	     cmp_eh_frame_hdr_table_entries, swap_eh_frame_hdr_table_entries);
339
340	table->hdrsz = hdrSize;
341	smp_wmb();
342	table->header = (const void *)header;
343}
344
345static void *__init balloc(unsigned long sz)
346{
347	return __alloc_bootmem_nopanic(sz,
348				       sizeof(unsigned int),
349				       __pa(MAX_DMA_ADDRESS));
350}
351
352void __init arc_unwind_setup(void)
353{
354	setup_unwind_table(&root_table, balloc);
355}
356
357#ifdef CONFIG_MODULES
358
359static struct unwind_table *last_table;
360
361/* Must be called with module_mutex held. */
362void *unwind_add_table(struct module *module, const void *table_start,
363		       unsigned long table_size)
364{
365	struct unwind_table *table;
366
367	if (table_size <= 0)
368		return NULL;
369
370	table = kmalloc(sizeof(*table), GFP_KERNEL);
371	if (!table)
372		return NULL;
373
374	init_unwind_table(table, module->name,
375			  module->module_core, module->core_size,
376			  module->module_init, module->init_size,
377			  table_start, table_size,
378			  NULL, 0);
379
380#ifdef UNWIND_DEBUG
381	unw_debug("Table added for [%s] %lx %lx\n",
382		module->name, table->core.pc, table->core.range);
383#endif
384	if (last_table)
385		last_table->link = table;
386	else
387		root_table.link = table;
388	last_table = table;
389
390	return table;
391}
392
393struct unlink_table_info {
394	struct unwind_table *table;
395	int init_only;
396};
397
398static int unlink_table(void *arg)
399{
400	struct unlink_table_info *info = arg;
401	struct unwind_table *table = info->table, *prev;
402
403	for (prev = &root_table; prev->link && prev->link != table;
404	     prev = prev->link)
405		;
406
407	if (prev->link) {
408		if (info->init_only) {
409			table->init.pc = 0;
410			table->init.range = 0;
411			info->table = NULL;
412		} else {
413			prev->link = table->link;
414			if (!prev->link)
415				last_table = prev;
416		}
417	} else
418		info->table = NULL;
419
420	return 0;
421}
422
423/* Must be called with module_mutex held. */
424void unwind_remove_table(void *handle, int init_only)
425{
426	struct unwind_table *table = handle;
427	struct unlink_table_info info;
428
429	if (!table || table == &root_table)
430		return;
431
432	if (init_only && table == last_table) {
433		table->init.pc = 0;
434		table->init.range = 0;
435		return;
436	}
437
438	info.table = table;
439	info.init_only = init_only;
440
441	unlink_table(&info); /* XXX: SMP */
442	kfree(table);
443}
444
445#endif /* CONFIG_MODULES */
446
447static uleb128_t get_uleb128(const u8 **pcur, const u8 *end)
448{
449	const u8 *cur = *pcur;
450	uleb128_t value;
451	unsigned shift;
452
453	for (shift = 0, value = 0; cur < end; shift += 7) {
454		if (shift + 7 > 8 * sizeof(value)
455		    && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
456			cur = end + 1;
457			break;
458		}
459		value |= (uleb128_t) (*cur & 0x7f) << shift;
460		if (!(*cur++ & 0x80))
461			break;
462	}
463	*pcur = cur;
464
465	return value;
466}
467
468static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
469{
470	const u8 *cur = *pcur;
471	sleb128_t value;
472	unsigned shift;
473
474	for (shift = 0, value = 0; cur < end; shift += 7) {
475		if (shift + 7 > 8 * sizeof(value)
476		    && (*cur & 0x7fU) >= (1U << (8 * sizeof(value) - shift))) {
477			cur = end + 1;
478			break;
479		}
480		value |= (sleb128_t) (*cur & 0x7f) << shift;
481		if (!(*cur & 0x80)) {
482			value |= -(*cur++ & 0x40) << shift;
483			break;
484		}
485	}
486	*pcur = cur;
487
488	return value;
489}
490
491static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *table)
492{
493	const u32 *cie;
494
495	if (!*fde || (*fde & (sizeof(*fde) - 1)))
496		return &bad_cie;
497
498	if (fde[1] == 0xffffffff)
499		return &not_fde;	/* this is a CIE */
500
501	if ((fde[1] & (sizeof(*fde) - 1)))
502/* || fde[1] > (unsigned long)(fde + 1) - (unsigned long)table->address) */
503		return NULL;	/* this is not a valid FDE */
504
505	/* cie = fde + 1 - fde[1] / sizeof(*fde); */
506	cie = (u32 *) fde[1];
507
508	if (*cie <= sizeof(*cie) + 4 || *cie >= fde[1] - sizeof(*fde)
509	    || (*cie & (sizeof(*cie) - 1))
510	    || (cie[1] != 0xffffffff))
511		return NULL;	/* this is not a (valid) CIE */
512	return cie;
513}
514
515static unsigned long read_pointer(const u8 **pLoc, const void *end,
516				  signed ptrType)
517{
518	unsigned long value = 0;
519	union {
520		const u8 *p8;
521		const u16 *p16u;
522		const s16 *p16s;
523		const u32 *p32u;
524		const s32 *p32s;
525		const unsigned long *pul;
526	} ptr;
527
528	if (ptrType < 0 || ptrType == DW_EH_PE_omit)
529		return 0;
530	ptr.p8 = *pLoc;
531	switch (ptrType & DW_EH_PE_FORM) {
532	case DW_EH_PE_data2:
533		if (end < (const void *)(ptr.p16u + 1))
534			return 0;
535		if (ptrType & DW_EH_PE_signed)
536			value = get_unaligned((u16 *) ptr.p16s++);
537		else
538			value = get_unaligned((u16 *) ptr.p16u++);
539		break;
540	case DW_EH_PE_data4:
541#ifdef CONFIG_64BIT
542		if (end < (const void *)(ptr.p32u + 1))
543			return 0;
544		if (ptrType & DW_EH_PE_signed)
545			value = get_unaligned(ptr.p32s++);
546		else
547			value = get_unaligned(ptr.p32u++);
548		break;
549	case DW_EH_PE_data8:
550		BUILD_BUG_ON(sizeof(u64) != sizeof(value));
551#else
552		BUILD_BUG_ON(sizeof(u32) != sizeof(value));
553#endif
554	case DW_EH_PE_native:
555		if (end < (const void *)(ptr.pul + 1))
556			return 0;
557		value = get_unaligned((unsigned long *)ptr.pul++);
558		break;
559	case DW_EH_PE_leb128:
560		BUILD_BUG_ON(sizeof(uleb128_t) > sizeof(value));
561		value = ptrType & DW_EH_PE_signed ? get_sleb128(&ptr.p8, end)
562		    : get_uleb128(&ptr.p8, end);
563		if ((const void *)ptr.p8 > end)
564			return 0;
565		break;
566	default:
567		return 0;
568	}
569	switch (ptrType & DW_EH_PE_ADJUST) {
570	case DW_EH_PE_abs:
571		break;
572	case DW_EH_PE_pcrel:
573		value += (unsigned long)*pLoc;
574		break;
575	default:
576		return 0;
577	}
578	if ((ptrType & DW_EH_PE_indirect)
579	    && __get_user(value, (unsigned long __user *)value))
580		return 0;
581	*pLoc = ptr.p8;
582
583	return value;
584}
585
586static signed fde_pointer_type(const u32 *cie)
587{
588	const u8 *ptr = (const u8 *)(cie + 2);
589	unsigned version = *ptr;
590
591	if (version != 1)
592		return -1;	/* unsupported */
593
594	if (*++ptr) {
595		const char *aug;
596		const u8 *end = (const u8 *)(cie + 1) + *cie;
597		uleb128_t len;
598
599		/* check if augmentation size is first (and thus present) */
600		if (*ptr != 'z')
601			return -1;
602
603		/* check if augmentation string is nul-terminated */
604		aug = (const void *)ptr;
605		ptr = memchr(aug, 0, end - ptr);
606		if (ptr == NULL)
607			return -1;
608
609		++ptr;		/* skip terminator */
610		get_uleb128(&ptr, end);	/* skip code alignment */
611		get_sleb128(&ptr, end);	/* skip data alignment */
612		/* skip return address column */
613		version <= 1 ? (void) ++ptr : (void)get_uleb128(&ptr, end);
614		len = get_uleb128(&ptr, end);	/* augmentation length */
615
616		if (ptr + len < ptr || ptr + len > end)
617			return -1;
618
619		end = ptr + len;
620		while (*++aug) {
621			if (ptr >= end)
622				return -1;
623			switch (*aug) {
624			case 'L':
625				++ptr;
626				break;
627			case 'P':{
628					signed ptrType = *ptr++;
629
630					if (!read_pointer(&ptr, end, ptrType)
631					    || ptr > end)
632						return -1;
633				}
634				break;
635			case 'R':
636				return *ptr;
637			default:
638				return -1;
639			}
640		}
641	}
642	return DW_EH_PE_native | DW_EH_PE_abs;
643}
644
645static int advance_loc(unsigned long delta, struct unwind_state *state)
646{
647	state->loc += delta * state->codeAlign;
648
649	/* FIXME_Rajesh: Probably we are defining for the initial range as well;
650	   return delta > 0;
651	 */
652	unw_debug("delta %3lu => loc 0x%lx: ", delta, state->loc);
653	return 1;
654}
655
656static void set_rule(uleb128_t reg, enum item_location where, uleb128_t value,
657		     struct unwind_state *state)
658{
659	if (reg < ARRAY_SIZE(state->regs)) {
660		state->regs[reg].where = where;
661		state->regs[reg].value = value;
662
663#ifdef UNWIND_DEBUG
664		unw_debug("r%lu: ", reg);
665		switch (where) {
666		case Nowhere:
667			unw_debug("s ");
668			break;
669		case Memory:
670			unw_debug("c(%lu) ", value);
671			break;
672		case Register:
673			unw_debug("r(%lu) ", value);
674			break;
675		case Value:
676			unw_debug("v(%lu) ", value);
677			break;
678		default:
679			break;
680		}
681#endif
682	}
683}
684
685static int processCFI(const u8 *start, const u8 *end, unsigned long targetLoc,
686		      signed ptrType, struct unwind_state *state)
687{
688	union {
689		const u8 *p8;
690		const u16 *p16;
691		const u32 *p32;
692	} ptr;
693	int result = 1;
694	u8 opcode;
695
696	if (start != state->cieStart) {
697		state->loc = state->org;
698		result =
699		    processCFI(state->cieStart, state->cieEnd, 0, ptrType,
700			       state);
701		if (targetLoc == 0 && state->label == NULL)
702			return result;
703	}
704	for (ptr.p8 = start; result && ptr.p8 < end;) {
705		switch (*ptr.p8 >> 6) {
706			uleb128_t value;
707
708		case 0:
709			opcode = *ptr.p8++;
710
711			switch (opcode) {
712			case DW_CFA_nop:
713				unw_debug("cfa nop ");
714				break;
715			case DW_CFA_set_loc:
716				state->loc = read_pointer(&ptr.p8, end,
717							  ptrType);
718				if (state->loc == 0)
719					result = 0;
720				unw_debug("cfa_set_loc: 0x%lx ", state->loc);
721				break;
722			case DW_CFA_advance_loc1:
723				unw_debug("\ncfa advance loc1:");
724				result = ptr.p8 < end
725				    && advance_loc(*ptr.p8++, state);
726				break;
727			case DW_CFA_advance_loc2:
728				value = *ptr.p8++;
729				value += *ptr.p8++ << 8;
730				unw_debug("\ncfa advance loc2:");
731				result = ptr.p8 <= end + 2
732				    /* && advance_loc(*ptr.p16++, state); */
733				    && advance_loc(value, state);
734				break;
735			case DW_CFA_advance_loc4:
736				unw_debug("\ncfa advance loc4:");
737				result = ptr.p8 <= end + 4
738				    && advance_loc(*ptr.p32++, state);
739				break;
740			case DW_CFA_offset_extended:
741				value = get_uleb128(&ptr.p8, end);
742				unw_debug("cfa_offset_extended: ");
743				set_rule(value, Memory,
744					 get_uleb128(&ptr.p8, end), state);
745				break;
746			case DW_CFA_val_offset:
747				value = get_uleb128(&ptr.p8, end);
748				set_rule(value, Value,
749					 get_uleb128(&ptr.p8, end), state);
750				break;
751			case DW_CFA_offset_extended_sf:
752				value = get_uleb128(&ptr.p8, end);
753				set_rule(value, Memory,
754					 get_sleb128(&ptr.p8, end), state);
755				break;
756			case DW_CFA_val_offset_sf:
757				value = get_uleb128(&ptr.p8, end);
758				set_rule(value, Value,
759					 get_sleb128(&ptr.p8, end), state);
760				break;
761			case DW_CFA_restore_extended:
762				unw_debug("cfa_restore_extended: ");
763			case DW_CFA_undefined:
764				unw_debug("cfa_undefined: ");
765			case DW_CFA_same_value:
766				unw_debug("cfa_same_value: ");
767				set_rule(get_uleb128(&ptr.p8, end), Nowhere, 0,
768					 state);
769				break;
770			case DW_CFA_register:
771				unw_debug("cfa_register: ");
772				value = get_uleb128(&ptr.p8, end);
773				set_rule(value,
774					 Register,
775					 get_uleb128(&ptr.p8, end), state);
776				break;
777			case DW_CFA_remember_state:
778				unw_debug("cfa_remember_state: ");
779				if (ptr.p8 == state->label) {
780					state->label = NULL;
781					return 1;
782				}
783				if (state->stackDepth >= MAX_STACK_DEPTH)
784					return 0;
785				state->stack[state->stackDepth++] = ptr.p8;
786				break;
787			case DW_CFA_restore_state:
788				unw_debug("cfa_restore_state: ");
789				if (state->stackDepth) {
790					const uleb128_t loc = state->loc;
791					const u8 *label = state->label;
792
793					state->label =
794					    state->stack[state->stackDepth - 1];
795					memcpy(&state->cfa, &badCFA,
796					       sizeof(state->cfa));
797					memset(state->regs, 0,
798					       sizeof(state->regs));
799					state->stackDepth = 0;
800					result =
801					    processCFI(start, end, 0, ptrType,
802						       state);
803					state->loc = loc;
804					state->label = label;
805				} else
806					return 0;
807				break;
808			case DW_CFA_def_cfa:
809				state->cfa.reg = get_uleb128(&ptr.p8, end);
810				unw_debug("cfa_def_cfa: r%lu ", state->cfa.reg);
811				/*nobreak*/
812			case DW_CFA_def_cfa_offset:
813				state->cfa.offs = get_uleb128(&ptr.p8, end);
814				unw_debug("cfa_def_cfa_offset: 0x%lx ",
815					  state->cfa.offs);
816				break;
817			case DW_CFA_def_cfa_sf:
818				state->cfa.reg = get_uleb128(&ptr.p8, end);
819				/*nobreak */
820			case DW_CFA_def_cfa_offset_sf:
821				state->cfa.offs = get_sleb128(&ptr.p8, end)
822				    * state->dataAlign;
823				break;
824			case DW_CFA_def_cfa_register:
825				unw_debug("cfa_def_cfa_regsiter: ");
826				state->cfa.reg = get_uleb128(&ptr.p8, end);
827				break;
828				/*todo case DW_CFA_def_cfa_expression: */
829				/*todo case DW_CFA_expression: */
830				/*todo case DW_CFA_val_expression: */
831			case DW_CFA_GNU_args_size:
832				get_uleb128(&ptr.p8, end);
833				break;
834			case DW_CFA_GNU_negative_offset_extended:
835				value = get_uleb128(&ptr.p8, end);
836				set_rule(value,
837					 Memory,
838					 (uleb128_t) 0 - get_uleb128(&ptr.p8,
839								     end),
840					 state);
841				break;
842			case DW_CFA_GNU_window_save:
843			default:
844				unw_debug("UNKNOWN OPCODE 0x%x\n", opcode);
845				result = 0;
846				break;
847			}
848			break;
849		case 1:
850			unw_debug("\ncfa_adv_loc: ");
851			result = advance_loc(*ptr.p8++ & 0x3f, state);
852			break;
853		case 2:
854			unw_debug("cfa_offset: ");
855			value = *ptr.p8++ & 0x3f;
856			set_rule(value, Memory, get_uleb128(&ptr.p8, end),
857				 state);
858			break;
859		case 3:
860			unw_debug("cfa_restore: ");
861			set_rule(*ptr.p8++ & 0x3f, Nowhere, 0, state);
862			break;
863		}
864
865		if (ptr.p8 > end)
866			result = 0;
867		if (result && targetLoc != 0 && targetLoc < state->loc)
868			return 1;
869	}
870
871	return result && ptr.p8 == end && (targetLoc == 0 || (
872		/*todo While in theory this should apply, gcc in practice omits
873		  everything past the function prolog, and hence the location
874		  never reaches the end of the function.
875		targetLoc < state->loc && */  state->label == NULL));
876}
877
878/* Unwind to previous to frame.  Returns 0 if successful, negative
879 * number in case of an error. */
880int arc_unwind(struct unwind_frame_info *frame)
881{
882#define FRAME_REG(r, t) (((t *)frame)[reg_info[r].offs])
883	const u32 *fde = NULL, *cie = NULL;
884	const u8 *ptr = NULL, *end = NULL;
885	unsigned long pc = UNW_PC(frame) - frame->call_frame;
886	unsigned long startLoc = 0, endLoc = 0, cfa;
887	unsigned i;
888	signed ptrType = -1;
889	uleb128_t retAddrReg = 0;
890	const struct unwind_table *table;
891	struct unwind_state state;
892	unsigned long *fptr;
893	unsigned long addr;
894
895	unw_debug("\n\nUNWIND FRAME:\n");
896	unw_debug("PC: 0x%lx BLINK: 0x%lx, SP: 0x%lx, FP: 0x%x\n",
897		  UNW_PC(frame), UNW_BLINK(frame), UNW_SP(frame),
898		  UNW_FP(frame));
899
900	if (UNW_PC(frame) == 0)
901		return -EINVAL;
902
903#ifdef UNWIND_DEBUG
904	{
905		unsigned long *sptr = (unsigned long *)UNW_SP(frame);
906		unw_debug("\nStack Dump:\n");
907		for (i = 0; i < 20; i++, sptr++)
908			unw_debug("0x%p:  0x%lx\n", sptr, *sptr);
909		unw_debug("\n");
910	}
911#endif
912
913	table = find_table(pc);
914	if (table != NULL
915	    && !(table->size & (sizeof(*fde) - 1))) {
916		const u8 *hdr = table->header;
917		unsigned long tableSize;
918
919		smp_rmb();
920		if (hdr && hdr[0] == 1) {
921			switch (hdr[3] & DW_EH_PE_FORM) {
922			case DW_EH_PE_native:
923				tableSize = sizeof(unsigned long);
924				break;
925			case DW_EH_PE_data2:
926				tableSize = 2;
927				break;
928			case DW_EH_PE_data4:
929				tableSize = 4;
930				break;
931			case DW_EH_PE_data8:
932				tableSize = 8;
933				break;
934			default:
935				tableSize = 0;
936				break;
937			}
938			ptr = hdr + 4;
939			end = hdr + table->hdrsz;
940			if (tableSize && read_pointer(&ptr, end, hdr[1])
941			    == (unsigned long)table->address
942			    && (i = read_pointer(&ptr, end, hdr[2])) > 0
943			    && i == (end - ptr) / (2 * tableSize)
944			    && !((end - ptr) % (2 * tableSize))) {
945				do {
946					const u8 *cur =
947					    ptr + (i / 2) * (2 * tableSize);
948
949					startLoc = read_pointer(&cur,
950								cur + tableSize,
951								hdr[3]);
952					if (pc < startLoc)
953						i /= 2;
954					else {
955						ptr = cur - tableSize;
956						i = (i + 1) / 2;
957					}
958				} while (startLoc && i > 1);
959				if (i == 1
960				    && (startLoc = read_pointer(&ptr,
961								ptr + tableSize,
962								hdr[3])) != 0
963				    && pc >= startLoc)
964					fde = (void *)read_pointer(&ptr,
965								   ptr +
966								   tableSize,
967								   hdr[3]);
968			}
969		}
970
971		if (fde != NULL) {
972			cie = cie_for_fde(fde, table);
973			ptr = (const u8 *)(fde + 2);
974			if (cie != NULL
975			    && cie != &bad_cie
976			    && cie != &not_fde
977			    && (ptrType = fde_pointer_type(cie)) >= 0
978			    && read_pointer(&ptr,
979					    (const u8 *)(fde + 1) + *fde,
980					    ptrType) == startLoc) {
981				if (!(ptrType & DW_EH_PE_indirect))
982					ptrType &=
983					    DW_EH_PE_FORM | DW_EH_PE_signed;
984				endLoc =
985				    startLoc + read_pointer(&ptr,
986							    (const u8 *)(fde +
987									 1) +
988							    *fde, ptrType);
989				if (pc >= endLoc)
990					fde = NULL;
991			} else
992				fde = NULL;
993		}
994		if (fde == NULL) {
995			for (fde = table->address, tableSize = table->size;
996			     cie = NULL, tableSize > sizeof(*fde)
997			     && tableSize - sizeof(*fde) >= *fde;
998			     tableSize -= sizeof(*fde) + *fde,
999			     fde += 1 + *fde / sizeof(*fde)) {
1000				cie = cie_for_fde(fde, table);
1001				if (cie == &bad_cie) {
1002					cie = NULL;
1003					break;
1004				}
1005				if (cie == NULL
1006				    || cie == &not_fde
1007				    || (ptrType = fde_pointer_type(cie)) < 0)
1008					continue;
1009				ptr = (const u8 *)(fde + 2);
1010				startLoc = read_pointer(&ptr,
1011							(const u8 *)(fde + 1) +
1012							*fde, ptrType);
1013				if (!startLoc)
1014					continue;
1015				if (!(ptrType & DW_EH_PE_indirect))
1016					ptrType &=
1017					    DW_EH_PE_FORM | DW_EH_PE_signed;
1018				endLoc =
1019				    startLoc + read_pointer(&ptr,
1020							    (const u8 *)(fde +
1021									 1) +
1022							    *fde, ptrType);
1023				if (pc >= startLoc && pc < endLoc)
1024					break;
1025			}
1026		}
1027	}
1028	if (cie != NULL) {
1029		memset(&state, 0, sizeof(state));
1030		state.cieEnd = ptr;	/* keep here temporarily */
1031		ptr = (const u8 *)(cie + 2);
1032		end = (const u8 *)(cie + 1) + *cie;
1033		frame->call_frame = 1;
1034		if ((state.version = *ptr) != 1)
1035			cie = NULL;	/* unsupported version */
1036		else if (*++ptr) {
1037			/* check if augmentation size is first (thus present) */
1038			if (*ptr == 'z') {
1039				while (++ptr < end && *ptr) {
1040					switch (*ptr) {
1041					/* chk for ignorable or already handled
1042					 * nul-terminated augmentation string */
1043					case 'L':
1044					case 'P':
1045					case 'R':
1046						continue;
1047					case 'S':
1048						frame->call_frame = 0;
1049						continue;
1050					default:
1051						break;
1052					}
1053					break;
1054				}
1055			}
1056			if (ptr >= end || *ptr)
1057				cie = NULL;
1058		}
1059		++ptr;
1060	}
1061	if (cie != NULL) {
1062		/* get code aligment factor */
1063		state.codeAlign = get_uleb128(&ptr, end);
1064		/* get data aligment factor */
1065		state.dataAlign = get_sleb128(&ptr, end);
1066		if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
1067			cie = NULL;
1068		else {
1069			retAddrReg =
1070			    state.version <= 1 ? *ptr++ : get_uleb128(&ptr,
1071								      end);
1072			unw_debug("CIE Frame Info:\n");
1073			unw_debug("return Address register 0x%lx\n",
1074				  retAddrReg);
1075			unw_debug("data Align: %ld\n", state.dataAlign);
1076			unw_debug("code Align: %lu\n", state.codeAlign);
1077			/* skip augmentation */
1078			if (((const char *)(cie + 2))[1] == 'z') {
1079				uleb128_t augSize = get_uleb128(&ptr, end);
1080
1081				ptr += augSize;
1082			}
1083			if (ptr > end || retAddrReg >= ARRAY_SIZE(reg_info)
1084			    || REG_INVALID(retAddrReg)
1085			    || reg_info[retAddrReg].width !=
1086			    sizeof(unsigned long))
1087				cie = NULL;
1088		}
1089	}
1090	if (cie != NULL) {
1091		state.cieStart = ptr;
1092		ptr = state.cieEnd;
1093		state.cieEnd = end;
1094		end = (const u8 *)(fde + 1) + *fde;
1095		/* skip augmentation */
1096		if (((const char *)(cie + 2))[1] == 'z') {
1097			uleb128_t augSize = get_uleb128(&ptr, end);
1098
1099			if ((ptr += augSize) > end)
1100				fde = NULL;
1101		}
1102	}
1103	if (cie == NULL || fde == NULL) {
1104#ifdef CONFIG_FRAME_POINTER
1105		unsigned long top, bottom;
1106
1107		top = STACK_TOP_UNW(frame->task);
1108		bottom = STACK_BOTTOM_UNW(frame->task);
1109#if FRAME_RETADDR_OFFSET < 0
1110		if (UNW_SP(frame) < top && UNW_FP(frame) <= UNW_SP(frame)
1111		    && bottom < UNW_FP(frame)
1112#else
1113		if (UNW_SP(frame) > top && UNW_FP(frame) >= UNW_SP(frame)
1114		    && bottom > UNW_FP(frame)
1115#endif
1116		    && !((UNW_SP(frame) | UNW_FP(frame))
1117			 & (sizeof(unsigned long) - 1))) {
1118			unsigned long link;
1119
1120			if (!__get_user(link, (unsigned long *)
1121					(UNW_FP(frame) + FRAME_LINK_OFFSET))
1122#if FRAME_RETADDR_OFFSET < 0
1123			    && link > bottom && link < UNW_FP(frame)
1124#else
1125			    && link > UNW_FP(frame) && link < bottom
1126#endif
1127			    && !(link & (sizeof(link) - 1))
1128			    && !__get_user(UNW_PC(frame),
1129					   (unsigned long *)(UNW_FP(frame)
1130						+ FRAME_RETADDR_OFFSET)))
1131			{
1132				UNW_SP(frame) =
1133				    UNW_FP(frame) + FRAME_RETADDR_OFFSET
1134#if FRAME_RETADDR_OFFSET < 0
1135				    -
1136#else
1137				    +
1138#endif
1139				    sizeof(UNW_PC(frame));
1140				UNW_FP(frame) = link;
1141				return 0;
1142			}
1143		}
1144#endif
1145		return -ENXIO;
1146	}
1147	state.org = startLoc;
1148	memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
1149
1150	unw_debug("\nProcess instructions\n");
1151
1152	/* process instructions
1153	 * For ARC, we optimize by having blink(retAddrReg) with
1154	 * the sameValue in the leaf function, so we should not check
1155	 * state.regs[retAddrReg].where == Nowhere
1156	 */
1157	if (!processCFI(ptr, end, pc, ptrType, &state)
1158	    || state.loc > endLoc
1159/*	   || state.regs[retAddrReg].where == Nowhere */
1160	    || state.cfa.reg >= ARRAY_SIZE(reg_info)
1161	    || reg_info[state.cfa.reg].width != sizeof(unsigned long)
1162	    || state.cfa.offs % sizeof(unsigned long))
1163		return -EIO;
1164
1165#ifdef UNWIND_DEBUG
1166	unw_debug("\n");
1167
1168	unw_debug("\nRegister State Based on the rules parsed from FDE:\n");
1169	for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1170
1171		if (REG_INVALID(i))
1172			continue;
1173
1174		switch (state.regs[i].where) {
1175		case Nowhere:
1176			break;
1177		case Memory:
1178			unw_debug(" r%d: c(%lu),", i, state.regs[i].value);
1179			break;
1180		case Register:
1181			unw_debug(" r%d: r(%lu),", i, state.regs[i].value);
1182			break;
1183		case Value:
1184			unw_debug(" r%d: v(%lu),", i, state.regs[i].value);
1185			break;
1186		}
1187	}
1188
1189	unw_debug("\n");
1190#endif
1191
1192	/* update frame */
1193#ifndef CONFIG_AS_CFI_SIGNAL_FRAME
1194	if (frame->call_frame
1195	    && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
1196		frame->call_frame = 0;
1197#endif
1198	cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
1199	startLoc = min_t(unsigned long, UNW_SP(frame), cfa);
1200	endLoc = max_t(unsigned long, UNW_SP(frame), cfa);
1201	if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
1202		startLoc = min(STACK_LIMIT(cfa), cfa);
1203		endLoc = max(STACK_LIMIT(cfa), cfa);
1204	}
1205
1206	unw_debug("\nCFA reg: 0x%lx, offset: 0x%lx =>  0x%lx\n",
1207		  state.cfa.reg, state.cfa.offs, cfa);
1208
1209	for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1210		if (REG_INVALID(i)) {
1211			if (state.regs[i].where == Nowhere)
1212				continue;
1213			return -EIO;
1214		}
1215		switch (state.regs[i].where) {
1216		default:
1217			break;
1218		case Register:
1219			if (state.regs[i].value >= ARRAY_SIZE(reg_info)
1220			    || REG_INVALID(state.regs[i].value)
1221			    || reg_info[i].width >
1222			    reg_info[state.regs[i].value].width)
1223				return -EIO;
1224			switch (reg_info[state.regs[i].value].width) {
1225			case sizeof(u8):
1226				state.regs[i].value =
1227				FRAME_REG(state.regs[i].value, const u8);
1228				break;
1229			case sizeof(u16):
1230				state.regs[i].value =
1231				FRAME_REG(state.regs[i].value, const u16);
1232				break;
1233			case sizeof(u32):
1234				state.regs[i].value =
1235				FRAME_REG(state.regs[i].value, const u32);
1236				break;
1237#ifdef CONFIG_64BIT
1238			case sizeof(u64):
1239				state.regs[i].value =
1240				FRAME_REG(state.regs[i].value, const u64);
1241				break;
1242#endif
1243			default:
1244				return -EIO;
1245			}
1246			break;
1247		}
1248	}
1249
1250	unw_debug("\nRegister state after evaluation with realtime Stack:\n");
1251	fptr = (unsigned long *)(&frame->regs);
1252	for (i = 0; i < ARRAY_SIZE(state.regs); ++i, fptr++) {
1253
1254		if (REG_INVALID(i))
1255			continue;
1256		switch (state.regs[i].where) {
1257		case Nowhere:
1258			if (reg_info[i].width != sizeof(UNW_SP(frame))
1259			    || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
1260			    != &UNW_SP(frame))
1261				continue;
1262			UNW_SP(frame) = cfa;
1263			break;
1264		case Register:
1265			switch (reg_info[i].width) {
1266			case sizeof(u8):
1267				FRAME_REG(i, u8) = state.regs[i].value;
1268				break;
1269			case sizeof(u16):
1270				FRAME_REG(i, u16) = state.regs[i].value;
1271				break;
1272			case sizeof(u32):
1273				FRAME_REG(i, u32) = state.regs[i].value;
1274				break;
1275#ifdef CONFIG_64BIT
1276			case sizeof(u64):
1277				FRAME_REG(i, u64) = state.regs[i].value;
1278				break;
1279#endif
1280			default:
1281				return -EIO;
1282			}
1283			break;
1284		case Value:
1285			if (reg_info[i].width != sizeof(unsigned long))
1286				return -EIO;
1287			FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
1288			    * state.dataAlign;
1289			break;
1290		case Memory:
1291			addr = cfa + state.regs[i].value * state.dataAlign;
1292
1293			if ((state.regs[i].value * state.dataAlign)
1294			    % sizeof(unsigned long)
1295			    || addr < startLoc
1296			    || addr + sizeof(unsigned long) < addr
1297			    || addr + sizeof(unsigned long) > endLoc)
1298					return -EIO;
1299
1300			switch (reg_info[i].width) {
1301			case sizeof(u8):
1302				__get_user(FRAME_REG(i, u8),
1303					   (u8 __user *)addr);
1304				break;
1305			case sizeof(u16):
1306				__get_user(FRAME_REG(i, u16),
1307					   (u16 __user *)addr);
1308				break;
1309			case sizeof(u32):
1310				__get_user(FRAME_REG(i, u32),
1311					   (u32 __user *)addr);
1312				break;
1313#ifdef CONFIG_64BIT
1314			case sizeof(u64):
1315				__get_user(FRAME_REG(i, u64),
1316					   (u64 __user *)addr);
1317				break;
1318#endif
1319			default:
1320				return -EIO;
1321			}
1322
1323			break;
1324		}
1325		unw_debug("r%d: 0x%lx ", i, *fptr);
1326	}
1327
1328	return 0;
1329#undef FRAME_REG
1330}
1331EXPORT_SYMBOL(arc_unwind);
1332