Merge branch 'sh/dwarf-unwinder'
[linux-2.6.git] / arch / sh / kernel / dwarf.c
1 /*
2  * Copyright (C) 2009 Matt Fleming <matt@console-pimps.org>
3  *
4  * This file is subject to the terms and conditions of the GNU General Public
5  * License.  See the file "COPYING" in the main directory of this archive
6  * for more details.
7  *
8  * This is an implementation of a DWARF unwinder. Its main purpose is
9  * for generating stacktrace information. Based on the DWARF 3
10  * specification from http://www.dwarfstd.org.
11  *
12  * TODO:
13  *      - DWARF64 doesn't work.
14  *      - Registers with DWARF_VAL_OFFSET rules aren't handled properly.
15  */
16
17 /* #define DEBUG */
18 #include <linux/kernel.h>
19 #include <linux/io.h>
20 #include <linux/list.h>
21 #include <linux/mempool.h>
22 #include <linux/mm.h>
23 #include <asm/dwarf.h>
24 #include <asm/unwinder.h>
25 #include <asm/sections.h>
26 #include <asm/unaligned.h>
27 #include <asm/stacktrace.h>
28
29 /* Reserve enough memory for two stack frames */
30 #define DWARF_FRAME_MIN_REQ     2
31 /* ... with 4 registers per frame. */
32 #define DWARF_REG_MIN_REQ       (DWARF_FRAME_MIN_REQ * 4)
33
34 static struct kmem_cache *dwarf_frame_cachep;
35 static mempool_t *dwarf_frame_pool;
36
37 static struct kmem_cache *dwarf_reg_cachep;
38 static mempool_t *dwarf_reg_pool;
39
40 static LIST_HEAD(dwarf_cie_list);
41 static DEFINE_SPINLOCK(dwarf_cie_lock);
42
43 static LIST_HEAD(dwarf_fde_list);
44 static DEFINE_SPINLOCK(dwarf_fde_lock);
45
46 static struct dwarf_cie *cached_cie;
47
48 /**
49  *      dwarf_frame_alloc_reg - allocate memory for a DWARF register
50  *      @frame: the DWARF frame whose list of registers we insert on
51  *      @reg_num: the register number
52  *
53  *      Allocate space for, and initialise, a dwarf reg from
54  *      dwarf_reg_pool and insert it onto the (unsorted) linked-list of
55  *      dwarf registers for @frame.
56  *
57  *      Return the initialised DWARF reg.
58  */
59 static struct dwarf_reg *dwarf_frame_alloc_reg(struct dwarf_frame *frame,
60                                                unsigned int reg_num)
61 {
62         struct dwarf_reg *reg;
63
64         reg = mempool_alloc(dwarf_reg_pool, GFP_ATOMIC);
65         if (!reg) {
66                 printk(KERN_WARNING "Unable to allocate a DWARF register\n");
67                 /*
68                  * Let's just bomb hard here, we have no way to
69                  * gracefully recover.
70                  */
71                 UNWINDER_BUG();
72         }
73
74         reg->number = reg_num;
75         reg->addr = 0;
76         reg->flags = 0;
77
78         list_add(&reg->link, &frame->reg_list);
79
80         return reg;
81 }
82
83 static void dwarf_frame_free_regs(struct dwarf_frame *frame)
84 {
85         struct dwarf_reg *reg, *n;
86
87         list_for_each_entry_safe(reg, n, &frame->reg_list, link) {
88                 list_del(&reg->link);
89                 mempool_free(reg, dwarf_reg_pool);
90         }
91 }
92
93 /**
94  *      dwarf_frame_reg - return a DWARF register
95  *      @frame: the DWARF frame to search in for @reg_num
96  *      @reg_num: the register number to search for
97  *
98  *      Lookup and return the dwarf reg @reg_num for this frame. Return
99  *      NULL if @reg_num is an register invalid number.
100  */
101 static struct dwarf_reg *dwarf_frame_reg(struct dwarf_frame *frame,
102                                          unsigned int reg_num)
103 {
104         struct dwarf_reg *reg;
105
106         list_for_each_entry(reg, &frame->reg_list, link) {
107                 if (reg->number == reg_num)
108                         return reg;
109         }
110
111         return NULL;
112 }
113
114 /**
115  *      dwarf_read_addr - read dwarf data
116  *      @src: source address of data
117  *      @dst: destination address to store the data to
118  *
119  *      Read 'n' bytes from @src, where 'n' is the size of an address on
120  *      the native machine. We return the number of bytes read, which
121  *      should always be 'n'. We also have to be careful when reading
122  *      from @src and writing to @dst, because they can be arbitrarily
123  *      aligned. Return 'n' - the number of bytes read.
124  */
125 static inline int dwarf_read_addr(unsigned long *src, unsigned long *dst)
126 {
127         u32 val = get_unaligned(src);
128         put_unaligned(val, dst);
129         return sizeof(unsigned long *);
130 }
131
132 /**
133  *      dwarf_read_uleb128 - read unsigned LEB128 data
134  *      @addr: the address where the ULEB128 data is stored
135  *      @ret: address to store the result
136  *
137  *      Decode an unsigned LEB128 encoded datum. The algorithm is taken
138  *      from Appendix C of the DWARF 3 spec. For information on the
139  *      encodings refer to section "7.6 - Variable Length Data". Return
140  *      the number of bytes read.
141  */
142 static inline unsigned long dwarf_read_uleb128(char *addr, unsigned int *ret)
143 {
144         unsigned int result;
145         unsigned char byte;
146         int shift, count;
147
148         result = 0;
149         shift = 0;
150         count = 0;
151
152         while (1) {
153                 byte = __raw_readb(addr);
154                 addr++;
155                 count++;
156
157                 result |= (byte & 0x7f) << shift;
158                 shift += 7;
159
160                 if (!(byte & 0x80))
161                         break;
162         }
163
164         *ret = result;
165
166         return count;
167 }
168
169 /**
170  *      dwarf_read_leb128 - read signed LEB128 data
171  *      @addr: the address of the LEB128 encoded data
172  *      @ret: address to store the result
173  *
174  *      Decode signed LEB128 data. The algorithm is taken from Appendix
175  *      C of the DWARF 3 spec. Return the number of bytes read.
176  */
177 static inline unsigned long dwarf_read_leb128(char *addr, int *ret)
178 {
179         unsigned char byte;
180         int result, shift;
181         int num_bits;
182         int count;
183
184         result = 0;
185         shift = 0;
186         count = 0;
187
188         while (1) {
189                 byte = __raw_readb(addr);
190                 addr++;
191                 result |= (byte & 0x7f) << shift;
192                 shift += 7;
193                 count++;
194
195                 if (!(byte & 0x80))
196                         break;
197         }
198
199         /* The number of bits in a signed integer. */
200         num_bits = 8 * sizeof(result);
201
202         if ((shift < num_bits) && (byte & 0x40))
203                 result |= (-1 << shift);
204
205         *ret = result;
206
207         return count;
208 }
209
210 /**
211  *      dwarf_read_encoded_value - return the decoded value at @addr
212  *      @addr: the address of the encoded value
213  *      @val: where to write the decoded value
214  *      @encoding: the encoding with which we can decode @addr
215  *
216  *      GCC emits encoded address in the .eh_frame FDE entries. Decode
217  *      the value at @addr using @encoding. The decoded value is written
218  *      to @val and the number of bytes read is returned.
219  */
220 static int dwarf_read_encoded_value(char *addr, unsigned long *val,
221                                     char encoding)
222 {
223         unsigned long decoded_addr = 0;
224         int count = 0;
225
226         switch (encoding & 0x70) {
227         case DW_EH_PE_absptr:
228                 break;
229         case DW_EH_PE_pcrel:
230                 decoded_addr = (unsigned long)addr;
231                 break;
232         default:
233                 pr_debug("encoding=0x%x\n", (encoding & 0x70));
234                 UNWINDER_BUG();
235         }
236
237         if ((encoding & 0x07) == 0x00)
238                 encoding |= DW_EH_PE_udata4;
239
240         switch (encoding & 0x0f) {
241         case DW_EH_PE_sdata4:
242         case DW_EH_PE_udata4:
243                 count += 4;
244                 decoded_addr += get_unaligned((u32 *)addr);
245                 __raw_writel(decoded_addr, val);
246                 break;
247         default:
248                 pr_debug("encoding=0x%x\n", encoding);
249                 UNWINDER_BUG();
250         }
251
252         return count;
253 }
254
255 /**
256  *      dwarf_entry_len - return the length of an FDE or CIE
257  *      @addr: the address of the entry
258  *      @len: the length of the entry
259  *
260  *      Read the initial_length field of the entry and store the size of
261  *      the entry in @len. We return the number of bytes read. Return a
262  *      count of 0 on error.
263  */
264 static inline int dwarf_entry_len(char *addr, unsigned long *len)
265 {
266         u32 initial_len;
267         int count;
268
269         initial_len = get_unaligned((u32 *)addr);
270         count = 4;
271
272         /*
273          * An initial length field value in the range DW_LEN_EXT_LO -
274          * DW_LEN_EXT_HI indicates an extension, and should not be
275          * interpreted as a length. The only extension that we currently
276          * understand is the use of DWARF64 addresses.
277          */
278         if (initial_len >= DW_EXT_LO && initial_len <= DW_EXT_HI) {
279                 /*
280                  * The 64-bit length field immediately follows the
281                  * compulsory 32-bit length field.
282                  */
283                 if (initial_len == DW_EXT_DWARF64) {
284                         *len = get_unaligned((u64 *)addr + 4);
285                         count = 12;
286                 } else {
287                         printk(KERN_WARNING "Unknown DWARF extension\n");
288                         count = 0;
289                 }
290         } else
291                 *len = initial_len;
292
293         return count;
294 }
295
296 /**
297  *      dwarf_lookup_cie - locate the cie
298  *      @cie_ptr: pointer to help with lookup
299  */
300 static struct dwarf_cie *dwarf_lookup_cie(unsigned long cie_ptr)
301 {
302         struct dwarf_cie *cie;
303         unsigned long flags;
304
305         spin_lock_irqsave(&dwarf_cie_lock, flags);
306
307         /*
308          * We've cached the last CIE we looked up because chances are
309          * that the FDE wants this CIE.
310          */
311         if (cached_cie && cached_cie->cie_pointer == cie_ptr) {
312                 cie = cached_cie;
313                 goto out;
314         }
315
316         list_for_each_entry(cie, &dwarf_cie_list, link) {
317                 if (cie->cie_pointer == cie_ptr) {
318                         cached_cie = cie;
319                         break;
320                 }
321         }
322
323         /* Couldn't find the entry in the list. */
324         if (&cie->link == &dwarf_cie_list)
325                 cie = NULL;
326 out:
327         spin_unlock_irqrestore(&dwarf_cie_lock, flags);
328         return cie;
329 }
330
331 /**
332  *      dwarf_lookup_fde - locate the FDE that covers pc
333  *      @pc: the program counter
334  */
335 struct dwarf_fde *dwarf_lookup_fde(unsigned long pc)
336 {
337         struct dwarf_fde *fde;
338         unsigned long flags;
339
340         spin_lock_irqsave(&dwarf_fde_lock, flags);
341
342         list_for_each_entry(fde, &dwarf_fde_list, link) {
343                 unsigned long start, end;
344
345                 start = fde->initial_location;
346                 end = fde->initial_location + fde->address_range;
347
348                 if (pc >= start && pc < end)
349                         break;
350         }
351
352         /* Couldn't find the entry in the list. */
353         if (&fde->link == &dwarf_fde_list)
354                 fde = NULL;
355
356         spin_unlock_irqrestore(&dwarf_fde_lock, flags);
357
358         return fde;
359 }
360
361 /**
362  *      dwarf_cfa_execute_insns - execute instructions to calculate a CFA
363  *      @insn_start: address of the first instruction
364  *      @insn_end: address of the last instruction
365  *      @cie: the CIE for this function
366  *      @fde: the FDE for this function
367  *      @frame: the instructions calculate the CFA for this frame
368  *      @pc: the program counter of the address we're interested in
369  *
370  *      Execute the Call Frame instruction sequence starting at
371  *      @insn_start and ending at @insn_end. The instructions describe
372  *      how to calculate the Canonical Frame Address of a stackframe.
373  *      Store the results in @frame.
374  */
375 static int dwarf_cfa_execute_insns(unsigned char *insn_start,
376                                    unsigned char *insn_end,
377                                    struct dwarf_cie *cie,
378                                    struct dwarf_fde *fde,
379                                    struct dwarf_frame *frame,
380                                    unsigned long pc)
381 {
382         unsigned char insn;
383         unsigned char *current_insn;
384         unsigned int count, delta, reg, expr_len, offset;
385         struct dwarf_reg *regp;
386
387         current_insn = insn_start;
388
389         while (current_insn < insn_end && frame->pc <= pc) {
390                 insn = __raw_readb(current_insn++);
391
392                 /*
393                  * Firstly, handle the opcodes that embed their operands
394                  * in the instructions.
395                  */
396                 switch (DW_CFA_opcode(insn)) {
397                 case DW_CFA_advance_loc:
398                         delta = DW_CFA_operand(insn);
399                         delta *= cie->code_alignment_factor;
400                         frame->pc += delta;
401                         continue;
402                         /* NOTREACHED */
403                 case DW_CFA_offset:
404                         reg = DW_CFA_operand(insn);
405                         count = dwarf_read_uleb128(current_insn, &offset);
406                         current_insn += count;
407                         offset *= cie->data_alignment_factor;
408                         regp = dwarf_frame_alloc_reg(frame, reg);
409                         regp->addr = offset;
410                         regp->flags |= DWARF_REG_OFFSET;
411                         continue;
412                         /* NOTREACHED */
413                 case DW_CFA_restore:
414                         reg = DW_CFA_operand(insn);
415                         continue;
416                         /* NOTREACHED */
417                 }
418
419                 /*
420                  * Secondly, handle the opcodes that don't embed their
421                  * operands in the instruction.
422                  */
423                 switch (insn) {
424                 case DW_CFA_nop:
425                         continue;
426                 case DW_CFA_advance_loc1:
427                         delta = *current_insn++;
428                         frame->pc += delta * cie->code_alignment_factor;
429                         break;
430                 case DW_CFA_advance_loc2:
431                         delta = get_unaligned((u16 *)current_insn);
432                         current_insn += 2;
433                         frame->pc += delta * cie->code_alignment_factor;
434                         break;
435                 case DW_CFA_advance_loc4:
436                         delta = get_unaligned((u32 *)current_insn);
437                         current_insn += 4;
438                         frame->pc += delta * cie->code_alignment_factor;
439                         break;
440                 case DW_CFA_offset_extended:
441                         count = dwarf_read_uleb128(current_insn, &reg);
442                         current_insn += count;
443                         count = dwarf_read_uleb128(current_insn, &offset);
444                         current_insn += count;
445                         offset *= cie->data_alignment_factor;
446                         break;
447                 case DW_CFA_restore_extended:
448                         count = dwarf_read_uleb128(current_insn, &reg);
449                         current_insn += count;
450                         break;
451                 case DW_CFA_undefined:
452                         count = dwarf_read_uleb128(current_insn, &reg);
453                         current_insn += count;
454                         regp = dwarf_frame_alloc_reg(frame, reg);
455                         regp->flags |= DWARF_UNDEFINED;
456                         break;
457                 case DW_CFA_def_cfa:
458                         count = dwarf_read_uleb128(current_insn,
459                                                    &frame->cfa_register);
460                         current_insn += count;
461                         count = dwarf_read_uleb128(current_insn,
462                                                    &frame->cfa_offset);
463                         current_insn += count;
464
465                         frame->flags |= DWARF_FRAME_CFA_REG_OFFSET;
466                         break;
467                 case DW_CFA_def_cfa_register:
468                         count = dwarf_read_uleb128(current_insn,
469                                                    &frame->cfa_register);
470                         current_insn += count;
471                         frame->flags |= DWARF_FRAME_CFA_REG_OFFSET;
472                         break;
473                 case DW_CFA_def_cfa_offset:
474                         count = dwarf_read_uleb128(current_insn, &offset);
475                         current_insn += count;
476                         frame->cfa_offset = offset;
477                         break;
478                 case DW_CFA_def_cfa_expression:
479                         count = dwarf_read_uleb128(current_insn, &expr_len);
480                         current_insn += count;
481
482                         frame->cfa_expr = current_insn;
483                         frame->cfa_expr_len = expr_len;
484                         current_insn += expr_len;
485
486                         frame->flags |= DWARF_FRAME_CFA_REG_EXP;
487                         break;
488                 case DW_CFA_offset_extended_sf:
489                         count = dwarf_read_uleb128(current_insn, &reg);
490                         current_insn += count;
491                         count = dwarf_read_leb128(current_insn, &offset);
492                         current_insn += count;
493                         offset *= cie->data_alignment_factor;
494                         regp = dwarf_frame_alloc_reg(frame, reg);
495                         regp->flags |= DWARF_REG_OFFSET;
496                         regp->addr = offset;
497                         break;
498                 case DW_CFA_val_offset:
499                         count = dwarf_read_uleb128(current_insn, &reg);
500                         current_insn += count;
501                         count = dwarf_read_leb128(current_insn, &offset);
502                         offset *= cie->data_alignment_factor;
503                         regp = dwarf_frame_alloc_reg(frame, reg);
504                         regp->flags |= DWARF_VAL_OFFSET;
505                         regp->addr = offset;
506                         break;
507                 case DW_CFA_GNU_args_size:
508                         count = dwarf_read_uleb128(current_insn, &offset);
509                         current_insn += count;
510                         break;
511                 case DW_CFA_GNU_negative_offset_extended:
512                         count = dwarf_read_uleb128(current_insn, &reg);
513                         current_insn += count;
514                         count = dwarf_read_uleb128(current_insn, &offset);
515                         offset *= cie->data_alignment_factor;
516
517                         regp = dwarf_frame_alloc_reg(frame, reg);
518                         regp->flags |= DWARF_REG_OFFSET;
519                         regp->addr = -offset;
520                         break;
521                 default:
522                         pr_debug("unhandled DWARF instruction 0x%x\n", insn);
523                         UNWINDER_BUG();
524                         break;
525                 }
526         }
527
528         return 0;
529 }
530
531 /**
532  *      dwarf_free_frame - free the memory allocated for @frame
533  *      @frame: the frame to free
534  */
535 void dwarf_free_frame(struct dwarf_frame *frame)
536 {
537         dwarf_frame_free_regs(frame);
538         mempool_free(frame, dwarf_frame_pool);
539 }
540
541 /**
542  *      dwarf_unwind_stack - unwind the stack
543  *
544  *      @pc: address of the function to unwind
545  *      @prev: struct dwarf_frame of the previous stackframe on the callstack
546  *
547  *      Return a struct dwarf_frame representing the most recent frame
548  *      on the callstack. Each of the lower (older) stack frames are
549  *      linked via the "prev" member.
550  */
551 struct dwarf_frame * dwarf_unwind_stack(unsigned long pc,
552                                         struct dwarf_frame *prev)
553 {
554         struct dwarf_frame *frame;
555         struct dwarf_cie *cie;
556         struct dwarf_fde *fde;
557         struct dwarf_reg *reg;
558         unsigned long addr;
559
560         /*
561          * If we're starting at the top of the stack we need get the
562          * contents of a physical register to get the CFA in order to
563          * begin the virtual unwinding of the stack.
564          *
565          * NOTE: the return address is guaranteed to be setup by the
566          * time this function makes its first function call.
567          */
568         if (!pc && !prev)
569                 pc = (unsigned long)current_text_addr();
570
571         frame = mempool_alloc(dwarf_frame_pool, GFP_ATOMIC);
572         if (!frame) {
573                 printk(KERN_ERR "Unable to allocate a dwarf frame\n");
574                 UNWINDER_BUG();
575         }
576
577         INIT_LIST_HEAD(&frame->reg_list);
578         frame->flags = 0;
579         frame->prev = prev;
580         frame->return_addr = 0;
581
582         fde = dwarf_lookup_fde(pc);
583         if (!fde) {
584                 /*
585                  * This is our normal exit path. There are two reasons
586                  * why we might exit here,
587                  *
588                  *      a) pc has no asscociated DWARF frame info and so
589                  *      we don't know how to unwind this frame. This is
590                  *      usually the case when we're trying to unwind a
591                  *      frame that was called from some assembly code
592                  *      that has no DWARF info, e.g. syscalls.
593                  *
594                  *      b) the DEBUG info for pc is bogus. There's
595                  *      really no way to distinguish this case from the
596                  *      case above, which sucks because we could print a
597                  *      warning here.
598                  */
599                 goto bail;
600         }
601
602         cie = dwarf_lookup_cie(fde->cie_pointer);
603
604         frame->pc = fde->initial_location;
605
606         /* CIE initial instructions */
607         dwarf_cfa_execute_insns(cie->initial_instructions,
608                                 cie->instructions_end, cie, fde,
609                                 frame, pc);
610
611         /* FDE instructions */
612         dwarf_cfa_execute_insns(fde->instructions, fde->end, cie,
613                                 fde, frame, pc);
614
615         /* Calculate the CFA */
616         switch (frame->flags) {
617         case DWARF_FRAME_CFA_REG_OFFSET:
618                 if (prev) {
619                         reg = dwarf_frame_reg(prev, frame->cfa_register);
620                         UNWINDER_BUG_ON(!reg);
621                         UNWINDER_BUG_ON(reg->flags != DWARF_REG_OFFSET);
622
623                         addr = prev->cfa + reg->addr;
624                         frame->cfa = __raw_readl(addr);
625
626                 } else {
627                         /*
628                          * Again, we're starting from the top of the
629                          * stack. We need to physically read
630                          * the contents of a register in order to get
631                          * the Canonical Frame Address for this
632                          * function.
633                          */
634                         frame->cfa = dwarf_read_arch_reg(frame->cfa_register);
635                 }
636
637                 frame->cfa += frame->cfa_offset;
638                 break;
639         default:
640                 UNWINDER_BUG();
641         }
642
643         reg = dwarf_frame_reg(frame, DWARF_ARCH_RA_REG);
644
645         /*
646          * If we haven't seen the return address register or the return
647          * address column is undefined then we must assume that this is
648          * the end of the callstack.
649          */
650         if (!reg || reg->flags == DWARF_UNDEFINED)
651                 goto bail;
652
653         UNWINDER_BUG_ON(reg->flags != DWARF_REG_OFFSET);
654
655         addr = frame->cfa + reg->addr;
656         frame->return_addr = __raw_readl(addr);
657
658         return frame;
659
660 bail:
661         dwarf_free_frame(frame);
662         return NULL;
663 }
664
665 static int dwarf_parse_cie(void *entry, void *p, unsigned long len,
666                            unsigned char *end, struct module *mod)
667 {
668         struct dwarf_cie *cie;
669         unsigned long flags;
670         int count;
671
672         cie = kzalloc(sizeof(*cie), GFP_KERNEL);
673         if (!cie)
674                 return -ENOMEM;
675
676         cie->length = len;
677
678         /*
679          * Record the offset into the .eh_frame section
680          * for this CIE. It allows this CIE to be
681          * quickly and easily looked up from the
682          * corresponding FDE.
683          */
684         cie->cie_pointer = (unsigned long)entry;
685
686         cie->version = *(char *)p++;
687         UNWINDER_BUG_ON(cie->version != 1);
688
689         cie->augmentation = p;
690         p += strlen(cie->augmentation) + 1;
691
692         count = dwarf_read_uleb128(p, &cie->code_alignment_factor);
693         p += count;
694
695         count = dwarf_read_leb128(p, &cie->data_alignment_factor);
696         p += count;
697
698         /*
699          * Which column in the rule table contains the
700          * return address?
701          */
702         if (cie->version == 1) {
703                 cie->return_address_reg = __raw_readb(p);
704                 p++;
705         } else {
706                 count = dwarf_read_uleb128(p, &cie->return_address_reg);
707                 p += count;
708         }
709
710         if (cie->augmentation[0] == 'z') {
711                 unsigned int length, count;
712                 cie->flags |= DWARF_CIE_Z_AUGMENTATION;
713
714                 count = dwarf_read_uleb128(p, &length);
715                 p += count;
716
717                 UNWINDER_BUG_ON((unsigned char *)p > end);
718
719                 cie->initial_instructions = p + length;
720                 cie->augmentation++;
721         }
722
723         while (*cie->augmentation) {
724                 /*
725                  * "L" indicates a byte showing how the
726                  * LSDA pointer is encoded. Skip it.
727                  */
728                 if (*cie->augmentation == 'L') {
729                         p++;
730                         cie->augmentation++;
731                 } else if (*cie->augmentation == 'R') {
732                         /*
733                          * "R" indicates a byte showing
734                          * how FDE addresses are
735                          * encoded.
736                          */
737                         cie->encoding = *(char *)p++;
738                         cie->augmentation++;
739                 } else if (*cie->augmentation == 'P') {
740                         /*
741                          * "R" indicates a personality
742                          * routine in the CIE
743                          * augmentation.
744                          */
745                         UNWINDER_BUG();
746                 } else if (*cie->augmentation == 'S') {
747                         UNWINDER_BUG();
748                 } else {
749                         /*
750                          * Unknown augmentation. Assume
751                          * 'z' augmentation.
752                          */
753                         p = cie->initial_instructions;
754                         UNWINDER_BUG_ON(!p);
755                         break;
756                 }
757         }
758
759         cie->initial_instructions = p;
760         cie->instructions_end = end;
761
762         cie->mod = mod;
763
764         /* Add to list */
765         spin_lock_irqsave(&dwarf_cie_lock, flags);
766         list_add_tail(&cie->link, &dwarf_cie_list);
767         spin_unlock_irqrestore(&dwarf_cie_lock, flags);
768
769         return 0;
770 }
771
772 static int dwarf_parse_fde(void *entry, u32 entry_type,
773                            void *start, unsigned long len,
774                            unsigned char *end, struct module *mod)
775 {
776         struct dwarf_fde *fde;
777         struct dwarf_cie *cie;
778         unsigned long flags;
779         int count;
780         void *p = start;
781
782         fde = kzalloc(sizeof(*fde), GFP_KERNEL);
783         if (!fde)
784                 return -ENOMEM;
785
786         fde->length = len;
787
788         /*
789          * In a .eh_frame section the CIE pointer is the
790          * delta between the address within the FDE
791          */
792         fde->cie_pointer = (unsigned long)(p - entry_type - 4);
793
794         cie = dwarf_lookup_cie(fde->cie_pointer);
795         fde->cie = cie;
796
797         if (cie->encoding)
798                 count = dwarf_read_encoded_value(p, &fde->initial_location,
799                                                  cie->encoding);
800         else
801                 count = dwarf_read_addr(p, &fde->initial_location);
802
803         p += count;
804
805         if (cie->encoding)
806                 count = dwarf_read_encoded_value(p, &fde->address_range,
807                                                  cie->encoding & 0x0f);
808         else
809                 count = dwarf_read_addr(p, &fde->address_range);
810
811         p += count;
812
813         if (fde->cie->flags & DWARF_CIE_Z_AUGMENTATION) {
814                 unsigned int length;
815                 count = dwarf_read_uleb128(p, &length);
816                 p += count + length;
817         }
818
819         /* Call frame instructions. */
820         fde->instructions = p;
821         fde->end = end;
822
823         fde->mod = mod;
824
825         /* Add to list. */
826         spin_lock_irqsave(&dwarf_fde_lock, flags);
827         list_add_tail(&fde->link, &dwarf_fde_list);
828         spin_unlock_irqrestore(&dwarf_fde_lock, flags);
829
830         return 0;
831 }
832
833 static void dwarf_unwinder_dump(struct task_struct *task,
834                                 struct pt_regs *regs,
835                                 unsigned long *sp,
836                                 const struct stacktrace_ops *ops,
837                                 void *data)
838 {
839         struct dwarf_frame *frame, *_frame;
840         unsigned long return_addr;
841
842         _frame = NULL;
843         return_addr = 0;
844
845         while (1) {
846                 frame = dwarf_unwind_stack(return_addr, _frame);
847
848                 if (_frame)
849                         dwarf_free_frame(_frame);
850
851                 _frame = frame;
852
853                 if (!frame || !frame->return_addr)
854                         break;
855
856                 return_addr = frame->return_addr;
857                 ops->address(data, return_addr, 1);
858         }
859
860         if (frame)
861                 dwarf_free_frame(frame);
862 }
863
864 static struct unwinder dwarf_unwinder = {
865         .name = "dwarf-unwinder",
866         .dump = dwarf_unwinder_dump,
867         .rating = 150,
868 };
869
870 static void dwarf_unwinder_cleanup(void)
871 {
872         struct dwarf_cie *cie;
873         struct dwarf_fde *fde;
874
875         /*
876          * Deallocate all the memory allocated for the DWARF unwinder.
877          * Traverse all the FDE/CIE lists and remove and free all the
878          * memory associated with those data structures.
879          */
880         list_for_each_entry(cie, &dwarf_cie_list, link)
881                 kfree(cie);
882
883         list_for_each_entry(fde, &dwarf_fde_list, link)
884                 kfree(fde);
885
886         kmem_cache_destroy(dwarf_reg_cachep);
887         kmem_cache_destroy(dwarf_frame_cachep);
888 }
889
890 /**
891  *      dwarf_parse_section - parse DWARF section
892  *      @eh_frame_start: start address of the .eh_frame section
893  *      @eh_frame_end: end address of the .eh_frame section
894  *      @mod: the kernel module containing the .eh_frame section
895  *
896  *      Parse the information in a .eh_frame section.
897  */
898 int dwarf_parse_section(char *eh_frame_start, char *eh_frame_end,
899                         struct module *mod)
900 {
901         u32 entry_type;
902         void *p, *entry;
903         int count, err = 0;
904         unsigned long len;
905         unsigned int c_entries, f_entries;
906         unsigned char *end;
907
908         c_entries = 0;
909         f_entries = 0;
910         entry = eh_frame_start;
911
912         while ((char *)entry < eh_frame_end) {
913                 p = entry;
914
915                 count = dwarf_entry_len(p, &len);
916                 if (count == 0) {
917                         /*
918                          * We read a bogus length field value. There is
919                          * nothing we can do here apart from disabling
920                          * the DWARF unwinder. We can't even skip this
921                          * entry and move to the next one because 'len'
922                          * tells us where our next entry is.
923                          */
924                         err = -EINVAL;
925                         goto out;
926                 } else
927                         p += count;
928
929                 /* initial length does not include itself */
930                 end = p + len;
931
932                 entry_type = get_unaligned((u32 *)p);
933                 p += 4;
934
935                 if (entry_type == DW_EH_FRAME_CIE) {
936                         err = dwarf_parse_cie(entry, p, len, end, mod);
937                         if (err < 0)
938                                 goto out;
939                         else
940                                 c_entries++;
941                 } else {
942                         err = dwarf_parse_fde(entry, entry_type, p, len,
943                                               end, mod);
944                         if (err < 0)
945                                 goto out;
946                         else
947                                 f_entries++;
948                 }
949
950                 entry = (char *)entry + len + 4;
951         }
952
953         printk(KERN_INFO "DWARF unwinder initialised: read %u CIEs, %u FDEs\n",
954                c_entries, f_entries);
955
956         return 0;
957
958 out:
959         return err;
960 }
961
962 /**
963  *      dwarf_module_unload - remove FDE/CIEs associated with @mod
964  *      @mod: the module that is being unloaded
965  *
966  *      Remove any FDEs and CIEs from the global lists that came from
967  *      @mod's .eh_frame section because @mod is being unloaded.
968  */
969 void dwarf_module_unload(struct module *mod)
970 {
971         struct dwarf_fde *fde;
972         struct dwarf_cie *cie;
973         unsigned long flags;
974
975         spin_lock_irqsave(&dwarf_cie_lock, flags);
976
977 again_cie:
978         list_for_each_entry(cie, &dwarf_cie_list, link) {
979                 if (cie->mod == mod)
980                         break;
981         }
982
983         if (&cie->link != &dwarf_cie_list) {
984                 list_del(&cie->link);
985                 kfree(cie);
986                 goto again_cie;
987         }
988
989         spin_unlock_irqrestore(&dwarf_cie_lock, flags);
990
991         spin_lock_irqsave(&dwarf_fde_lock, flags);
992
993 again_fde:
994         list_for_each_entry(fde, &dwarf_fde_list, link) {
995                 if (fde->mod == mod)
996                         break;
997         }
998
999         if (&fde->link != &dwarf_fde_list) {
1000                 list_del(&fde->link);
1001                 kfree(fde);
1002                 goto again_fde;
1003         }
1004
1005         spin_unlock_irqrestore(&dwarf_fde_lock, flags);
1006 }
1007
1008 /**
1009  *      dwarf_unwinder_init - initialise the dwarf unwinder
1010  *
1011  *      Build the data structures describing the .dwarf_frame section to
1012  *      make it easier to lookup CIE and FDE entries. Because the
1013  *      .eh_frame section is packed as tightly as possible it is not
1014  *      easy to lookup the FDE for a given PC, so we build a list of FDE
1015  *      and CIE entries that make it easier.
1016  */
1017 static int __init dwarf_unwinder_init(void)
1018 {
1019         int err;
1020         INIT_LIST_HEAD(&dwarf_cie_list);
1021         INIT_LIST_HEAD(&dwarf_fde_list);
1022
1023         dwarf_frame_cachep = kmem_cache_create("dwarf_frames",
1024                         sizeof(struct dwarf_frame), 0,
1025                         SLAB_PANIC | SLAB_HWCACHE_ALIGN | SLAB_NOTRACK, NULL);
1026
1027         dwarf_reg_cachep = kmem_cache_create("dwarf_regs",
1028                         sizeof(struct dwarf_reg), 0,
1029                         SLAB_PANIC | SLAB_HWCACHE_ALIGN | SLAB_NOTRACK, NULL);
1030
1031         dwarf_frame_pool = mempool_create(DWARF_FRAME_MIN_REQ,
1032                                           mempool_alloc_slab,
1033                                           mempool_free_slab,
1034                                           dwarf_frame_cachep);
1035
1036         dwarf_reg_pool = mempool_create(DWARF_REG_MIN_REQ,
1037                                          mempool_alloc_slab,
1038                                          mempool_free_slab,
1039                                          dwarf_reg_cachep);
1040
1041         err = dwarf_parse_section(__start_eh_frame, __stop_eh_frame, NULL);
1042         if (err)
1043                 goto out;
1044
1045         err = unwinder_register(&dwarf_unwinder);
1046         if (err)
1047                 goto out;
1048
1049         return 0;
1050
1051 out:
1052         printk(KERN_ERR "Failed to initialise DWARF unwinder: %d\n", err);
1053         dwarf_unwinder_cleanup();
1054         return -EINVAL;
1055 }
1056 early_initcall(dwarf_unwinder_init);