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