ARC: dw2 unwind: Remove falllback linear search thru FDE entries
[cascardo/linux.git] / arch / arc / kernel / unwind.c
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
28 extern 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
34 int dbg_unw;
35 #define unw_debug(fmt, ...)                     \
36 do {                                            \
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
55 static const struct {
56         unsigned offs:BITS_PER_LONG / 2;
57         unsigned width:BITS_PER_LONG / 2;
58 } reg_info[] = {
59 UNW_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
114 typedef unsigned long uleb128_t;
115 typedef signed long sleb128_t;
116
117 static 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
130 struct unwind_item {
131         enum item_location {
132                 Nowhere,
133                 Memory,
134                 Register,
135                 Value
136         } where;
137         uleb128_t value;
138 };
139
140 struct 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
155 static const struct cfa badCFA = { ARRAY_SIZE(reg_info), 1 };
156
157 static 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
171 static unsigned long read_pointer(const u8 **pLoc,
172                                   const void *end, signed ptrType);
173
174 static 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
206 void __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
214 static const u32 bad_cie, not_fde;
215 static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *);
216 static signed fde_pointer_type(const u32 *cie);
217
218 struct eh_frame_hdr_table_entry {
219         unsigned long start, fde;
220 };
221
222 static 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
230 static 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
244 static 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
345 static void *__init balloc(unsigned long sz)
346 {
347         return __alloc_bootmem_nopanic(sz,
348                                        sizeof(unsigned int),
349                                        __pa(MAX_DMA_ADDRESS));
350 }
351
352 void __init arc_unwind_setup(void)
353 {
354         setup_unwind_table(&root_table, balloc);
355 }
356
357 #ifdef CONFIG_MODULES
358
359 static struct unwind_table *last_table;
360
361 /* Must be called with module_mutex held. */
362 void *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
393 struct unlink_table_info {
394         struct unwind_table *table;
395         int init_only;
396 };
397
398 static 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. */
424 void 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
447 static 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
468 static 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
491 static 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
515 static 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
586 static 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
645 static 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
656 static 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
685 static 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. */
880 int 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                                         cie = NULL;
992                                 }
993                         } else {
994                                 fde = NULL;
995                                 cie = NULL;
996                         }
997                 }
998         }
999         if (cie != NULL) {
1000                 memset(&state, 0, sizeof(state));
1001                 state.cieEnd = ptr;     /* keep here temporarily */
1002                 ptr = (const u8 *)(cie + 2);
1003                 end = (const u8 *)(cie + 1) + *cie;
1004                 frame->call_frame = 1;
1005                 if ((state.version = *ptr) != 1)
1006                         cie = NULL;     /* unsupported version */
1007                 else if (*++ptr) {
1008                         /* check if augmentation size is first (thus present) */
1009                         if (*ptr == 'z') {
1010                                 while (++ptr < end && *ptr) {
1011                                         switch (*ptr) {
1012                                         /* chk for ignorable or already handled
1013                                          * nul-terminated augmentation string */
1014                                         case 'L':
1015                                         case 'P':
1016                                         case 'R':
1017                                                 continue;
1018                                         case 'S':
1019                                                 frame->call_frame = 0;
1020                                                 continue;
1021                                         default:
1022                                                 break;
1023                                         }
1024                                         break;
1025                                 }
1026                         }
1027                         if (ptr >= end || *ptr)
1028                                 cie = NULL;
1029                 }
1030                 ++ptr;
1031         }
1032         if (cie != NULL) {
1033                 /* get code aligment factor */
1034                 state.codeAlign = get_uleb128(&ptr, end);
1035                 /* get data aligment factor */
1036                 state.dataAlign = get_sleb128(&ptr, end);
1037                 if (state.codeAlign == 0 || state.dataAlign == 0 || ptr >= end)
1038                         cie = NULL;
1039                 else {
1040                         retAddrReg =
1041                             state.version <= 1 ? *ptr++ : get_uleb128(&ptr,
1042                                                                       end);
1043                         unw_debug("CIE Frame Info:\n");
1044                         unw_debug("return Address register 0x%lx\n",
1045                                   retAddrReg);
1046                         unw_debug("data Align: %ld\n", state.dataAlign);
1047                         unw_debug("code Align: %lu\n", state.codeAlign);
1048                         /* skip augmentation */
1049                         if (((const char *)(cie + 2))[1] == 'z') {
1050                                 uleb128_t augSize = get_uleb128(&ptr, end);
1051
1052                                 ptr += augSize;
1053                         }
1054                         if (ptr > end || retAddrReg >= ARRAY_SIZE(reg_info)
1055                             || REG_INVALID(retAddrReg)
1056                             || reg_info[retAddrReg].width !=
1057                             sizeof(unsigned long))
1058                                 cie = NULL;
1059                 }
1060         }
1061         if (cie != NULL) {
1062                 state.cieStart = ptr;
1063                 ptr = state.cieEnd;
1064                 state.cieEnd = end;
1065                 end = (const u8 *)(fde + 1) + *fde;
1066                 /* skip augmentation */
1067                 if (((const char *)(cie + 2))[1] == 'z') {
1068                         uleb128_t augSize = get_uleb128(&ptr, end);
1069
1070                         if ((ptr += augSize) > end)
1071                                 fde = NULL;
1072                 }
1073         }
1074         if (cie == NULL || fde == NULL) {
1075 #ifdef CONFIG_FRAME_POINTER
1076                 unsigned long top, bottom;
1077
1078                 top = STACK_TOP_UNW(frame->task);
1079                 bottom = STACK_BOTTOM_UNW(frame->task);
1080 #if FRAME_RETADDR_OFFSET < 0
1081                 if (UNW_SP(frame) < top && UNW_FP(frame) <= UNW_SP(frame)
1082                     && bottom < UNW_FP(frame)
1083 #else
1084                 if (UNW_SP(frame) > top && UNW_FP(frame) >= UNW_SP(frame)
1085                     && bottom > UNW_FP(frame)
1086 #endif
1087                     && !((UNW_SP(frame) | UNW_FP(frame))
1088                          & (sizeof(unsigned long) - 1))) {
1089                         unsigned long link;
1090
1091                         if (!__get_user(link, (unsigned long *)
1092                                         (UNW_FP(frame) + FRAME_LINK_OFFSET))
1093 #if FRAME_RETADDR_OFFSET < 0
1094                             && link > bottom && link < UNW_FP(frame)
1095 #else
1096                             && link > UNW_FP(frame) && link < bottom
1097 #endif
1098                             && !(link & (sizeof(link) - 1))
1099                             && !__get_user(UNW_PC(frame),
1100                                            (unsigned long *)(UNW_FP(frame)
1101                                                 + FRAME_RETADDR_OFFSET)))
1102                         {
1103                                 UNW_SP(frame) =
1104                                     UNW_FP(frame) + FRAME_RETADDR_OFFSET
1105 #if FRAME_RETADDR_OFFSET < 0
1106                                     -
1107 #else
1108                                     +
1109 #endif
1110                                     sizeof(UNW_PC(frame));
1111                                 UNW_FP(frame) = link;
1112                                 return 0;
1113                         }
1114                 }
1115 #endif
1116                 return -ENXIO;
1117         }
1118         state.org = startLoc;
1119         memcpy(&state.cfa, &badCFA, sizeof(state.cfa));
1120
1121         unw_debug("\nProcess instructions\n");
1122
1123         /* process instructions
1124          * For ARC, we optimize by having blink(retAddrReg) with
1125          * the sameValue in the leaf function, so we should not check
1126          * state.regs[retAddrReg].where == Nowhere
1127          */
1128         if (!processCFI(ptr, end, pc, ptrType, &state)
1129             || state.loc > endLoc
1130 /*         || state.regs[retAddrReg].where == Nowhere */
1131             || state.cfa.reg >= ARRAY_SIZE(reg_info)
1132             || reg_info[state.cfa.reg].width != sizeof(unsigned long)
1133             || state.cfa.offs % sizeof(unsigned long))
1134                 return -EIO;
1135
1136 #ifdef UNWIND_DEBUG
1137         unw_debug("\n");
1138
1139         unw_debug("\nRegister State Based on the rules parsed from FDE:\n");
1140         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1141
1142                 if (REG_INVALID(i))
1143                         continue;
1144
1145                 switch (state.regs[i].where) {
1146                 case Nowhere:
1147                         break;
1148                 case Memory:
1149                         unw_debug(" r%d: c(%lu),", i, state.regs[i].value);
1150                         break;
1151                 case Register:
1152                         unw_debug(" r%d: r(%lu),", i, state.regs[i].value);
1153                         break;
1154                 case Value:
1155                         unw_debug(" r%d: v(%lu),", i, state.regs[i].value);
1156                         break;
1157                 }
1158         }
1159
1160         unw_debug("\n");
1161 #endif
1162
1163         /* update frame */
1164 #ifndef CONFIG_AS_CFI_SIGNAL_FRAME
1165         if (frame->call_frame
1166             && !UNW_DEFAULT_RA(state.regs[retAddrReg], state.dataAlign))
1167                 frame->call_frame = 0;
1168 #endif
1169         cfa = FRAME_REG(state.cfa.reg, unsigned long) + state.cfa.offs;
1170         startLoc = min_t(unsigned long, UNW_SP(frame), cfa);
1171         endLoc = max_t(unsigned long, UNW_SP(frame), cfa);
1172         if (STACK_LIMIT(startLoc) != STACK_LIMIT(endLoc)) {
1173                 startLoc = min(STACK_LIMIT(cfa), cfa);
1174                 endLoc = max(STACK_LIMIT(cfa), cfa);
1175         }
1176
1177         unw_debug("\nCFA reg: 0x%lx, offset: 0x%lx =>  0x%lx\n",
1178                   state.cfa.reg, state.cfa.offs, cfa);
1179
1180         for (i = 0; i < ARRAY_SIZE(state.regs); ++i) {
1181                 if (REG_INVALID(i)) {
1182                         if (state.regs[i].where == Nowhere)
1183                                 continue;
1184                         return -EIO;
1185                 }
1186                 switch (state.regs[i].where) {
1187                 default:
1188                         break;
1189                 case Register:
1190                         if (state.regs[i].value >= ARRAY_SIZE(reg_info)
1191                             || REG_INVALID(state.regs[i].value)
1192                             || reg_info[i].width >
1193                             reg_info[state.regs[i].value].width)
1194                                 return -EIO;
1195                         switch (reg_info[state.regs[i].value].width) {
1196                         case sizeof(u8):
1197                                 state.regs[i].value =
1198                                 FRAME_REG(state.regs[i].value, const u8);
1199                                 break;
1200                         case sizeof(u16):
1201                                 state.regs[i].value =
1202                                 FRAME_REG(state.regs[i].value, const u16);
1203                                 break;
1204                         case sizeof(u32):
1205                                 state.regs[i].value =
1206                                 FRAME_REG(state.regs[i].value, const u32);
1207                                 break;
1208 #ifdef CONFIG_64BIT
1209                         case sizeof(u64):
1210                                 state.regs[i].value =
1211                                 FRAME_REG(state.regs[i].value, const u64);
1212                                 break;
1213 #endif
1214                         default:
1215                                 return -EIO;
1216                         }
1217                         break;
1218                 }
1219         }
1220
1221         unw_debug("\nRegister state after evaluation with realtime Stack:\n");
1222         fptr = (unsigned long *)(&frame->regs);
1223         for (i = 0; i < ARRAY_SIZE(state.regs); ++i, fptr++) {
1224
1225                 if (REG_INVALID(i))
1226                         continue;
1227                 switch (state.regs[i].where) {
1228                 case Nowhere:
1229                         if (reg_info[i].width != sizeof(UNW_SP(frame))
1230                             || &FRAME_REG(i, __typeof__(UNW_SP(frame)))
1231                             != &UNW_SP(frame))
1232                                 continue;
1233                         UNW_SP(frame) = cfa;
1234                         break;
1235                 case Register:
1236                         switch (reg_info[i].width) {
1237                         case sizeof(u8):
1238                                 FRAME_REG(i, u8) = state.regs[i].value;
1239                                 break;
1240                         case sizeof(u16):
1241                                 FRAME_REG(i, u16) = state.regs[i].value;
1242                                 break;
1243                         case sizeof(u32):
1244                                 FRAME_REG(i, u32) = state.regs[i].value;
1245                                 break;
1246 #ifdef CONFIG_64BIT
1247                         case sizeof(u64):
1248                                 FRAME_REG(i, u64) = state.regs[i].value;
1249                                 break;
1250 #endif
1251                         default:
1252                                 return -EIO;
1253                         }
1254                         break;
1255                 case Value:
1256                         if (reg_info[i].width != sizeof(unsigned long))
1257                                 return -EIO;
1258                         FRAME_REG(i, unsigned long) = cfa + state.regs[i].value
1259                             * state.dataAlign;
1260                         break;
1261                 case Memory:
1262                         addr = cfa + state.regs[i].value * state.dataAlign;
1263
1264                         if ((state.regs[i].value * state.dataAlign)
1265                             % sizeof(unsigned long)
1266                             || addr < startLoc
1267                             || addr + sizeof(unsigned long) < addr
1268                             || addr + sizeof(unsigned long) > endLoc)
1269                                         return -EIO;
1270
1271                         switch (reg_info[i].width) {
1272                         case sizeof(u8):
1273                                 __get_user(FRAME_REG(i, u8),
1274                                            (u8 __user *)addr);
1275                                 break;
1276                         case sizeof(u16):
1277                                 __get_user(FRAME_REG(i, u16),
1278                                            (u16 __user *)addr);
1279                                 break;
1280                         case sizeof(u32):
1281                                 __get_user(FRAME_REG(i, u32),
1282                                            (u32 __user *)addr);
1283                                 break;
1284 #ifdef CONFIG_64BIT
1285                         case sizeof(u64):
1286                                 __get_user(FRAME_REG(i, u64),
1287                                            (u64 __user *)addr);
1288                                 break;
1289 #endif
1290                         default:
1291                                 return -EIO;
1292                         }
1293
1294                         break;
1295                 }
1296                 unw_debug("r%d: 0x%lx ", i, *fptr);
1297         }
1298
1299         return 0;
1300 #undef FRAME_REG
1301 }
1302 EXPORT_SYMBOL(arc_unwind);