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