Missed a file.
[mono.git] / mono / mini / unwind.c
1 /*
2  * unwind.c: Stack Unwinding Interface
3  *
4  * Authors:
5  *   Zoltan Varga (vargaz@gmail.com)
6  *
7  * (C) 2008 Novell, Inc.
8  */
9
10 #include "mini.h"
11 #include "mini-unwind.h"
12
13 #include <mono/utils/mono-counters.h>
14 #include <mono/metadata/threads-types.h>
15
16 typedef enum {
17         LOC_SAME,
18         LOC_OFFSET
19 } LocType;
20
21 typedef struct {
22         LocType loc_type;
23         int offset;
24 } Loc;
25
26 typedef struct {
27         guint32 len;
28         guint8 info [MONO_ZERO_LEN_ARRAY];
29 } MonoUnwindInfo;
30
31 static CRITICAL_SECTION unwind_mutex;
32
33 static MonoUnwindInfo **cached_info;
34 static int cached_info_next, cached_info_size;
35 /* Statistics */
36 static int unwind_info_size;
37
38 #define unwind_lock() EnterCriticalSection (&unwind_mutex)
39 #define unwind_unlock() LeaveCriticalSection (&unwind_mutex)
40
41 #ifdef TARGET_AMD64
42 static int map_hw_reg_to_dwarf_reg [] = { 0, 2, 1, 3, 7, 6, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
43 #define NUM_REGS AMD64_NREG
44 #define DWARF_DATA_ALIGN (-8)
45 #define DWARF_PC_REG (mono_hw_reg_to_dwarf_reg (AMD64_RIP))
46 #elif defined(TARGET_ARM)
47 // http://infocenter.arm.com/help/topic/com.arm.doc.ihi0040a/IHI0040A_aadwarf.pdf
48 static int map_hw_reg_to_dwarf_reg [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
49 #define NUM_REGS 16
50 #define DWARF_DATA_ALIGN (-4)
51 #define DWARF_PC_REG (mono_hw_reg_to_dwarf_reg (ARMREG_LR))
52 #elif defined (TARGET_X86)
53 static int map_hw_reg_to_dwarf_reg [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
54 /* + 1 is for IP */
55 #define NUM_REGS X86_NREG + 1
56 #define DWARF_DATA_ALIGN (-4)
57 #define DWARF_PC_REG (mono_hw_reg_to_dwarf_reg (X86_NREG))
58 #elif defined (TARGET_POWERPC)
59 // http://refspecs.linuxfoundation.org/ELF/ppc64/PPC-elf64abi-1.9.html
60 static int map_hw_reg_to_dwarf_reg [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 
61                                                                                   9, 10, 11, 12, 13, 14, 15, 16,
62                                                                                   17, 18, 19, 20, 21, 22, 23, 24,
63                                                                                   25, 26, 27, 28, 29, 30, 31 };
64 #define NUM_REGS 110
65 #define DWARF_DATA_ALIGN (-(gint32)sizeof (mgreg_t))
66 #define DWARF_PC_REG 108
67 #else
68 static int map_hw_reg_to_dwarf_reg [16];
69 #define NUM_REGS 16
70 #define DWARF_DATA_ALIGN 0
71 #define DWARF_PC_REG -1
72 #endif
73
74 static gboolean dwarf_reg_to_hw_reg_inited;
75
76 static int map_dwarf_reg_to_hw_reg [NUM_REGS];
77
78 /*
79  * mono_hw_reg_to_dwarf_reg:
80  *
81  *   Map the hardware register number REG to the register number used by DWARF.
82  */
83 int
84 mono_hw_reg_to_dwarf_reg (int reg)
85 {
86 #ifdef TARGET_POWERPC
87         if (reg == ppc_lr)
88                 return 108;
89         else
90                 g_assert (reg < NUM_REGS);
91 #endif
92
93         if (NUM_REGS == 0) {
94                 g_assert_not_reached ();
95                 return -1;
96         } else {
97                 return map_hw_reg_to_dwarf_reg [reg];
98         }
99 }
100
101 static void
102 init_reg_map (void)
103 {
104         int i;
105
106         g_assert (NUM_REGS > 0);
107         for (i = 0; i < sizeof (map_hw_reg_to_dwarf_reg) / sizeof (int); ++i) {
108                 map_dwarf_reg_to_hw_reg [mono_hw_reg_to_dwarf_reg (i)] = i;
109         }
110
111 #ifdef TARGET_POWERPC
112         map_dwarf_reg_to_hw_reg [DWARF_PC_REG] = ppc_lr;
113 #endif
114
115         mono_memory_barrier ();
116         dwarf_reg_to_hw_reg_inited = TRUE;
117 }
118
119 static inline int
120 mono_dwarf_reg_to_hw_reg (int reg)
121 {
122         if (!dwarf_reg_to_hw_reg_inited)
123                 init_reg_map ();
124
125         return map_dwarf_reg_to_hw_reg [reg];
126 }
127
128 static G_GNUC_UNUSED void
129 encode_uleb128 (guint32 value, guint8 *buf, guint8 **endbuf)
130 {
131         guint8 *p = buf;
132
133         do {
134                 guint8 b = value & 0x7f;
135                 value >>= 7;
136                 if (value != 0) /* more bytes to come */
137                         b |= 0x80;
138                 *p ++ = b;
139         } while (value);
140
141         *endbuf = p;
142 }
143
144 static G_GNUC_UNUSED void
145 encode_sleb128 (gint32 value, guint8 *buf, guint8 **endbuf)
146 {
147         gboolean more = 1;
148         gboolean negative = (value < 0);
149         guint32 size = 32;
150         guint8 byte;
151         guint8 *p = buf;
152
153         while (more) {
154                 byte = value & 0x7f;
155                 value >>= 7;
156                 /* the following is unnecessary if the
157                  * implementation of >>= uses an arithmetic rather
158                  * than logical shift for a signed left operand
159                  */
160                 if (negative)
161                         /* sign extend */
162                         value |= - (1 <<(size - 7));
163                 /* sign bit of byte is second high order bit (0x40) */
164                 if ((value == 0 && !(byte & 0x40)) ||
165                         (value == -1 && (byte & 0x40)))
166                         more = 0;
167                 else
168                         byte |= 0x80;
169                 *p ++= byte;
170         }
171
172         *endbuf = p;
173 }
174
175 static inline guint32
176 decode_uleb128 (guint8 *buf, guint8 **endbuf)
177 {
178         guint8 *p = buf;
179         guint32 res = 0;
180         int shift = 0;
181
182         while (TRUE) {
183                 guint8 b = *p;
184                 p ++;
185
186                 res = res | (((int)(b & 0x7f)) << shift);
187                 if (!(b & 0x80))
188                         break;
189                 shift += 7;
190         }
191
192         *endbuf = p;
193
194         return res;
195 }
196
197 static inline gint32
198 decode_sleb128 (guint8 *buf, guint8 **endbuf)
199 {
200         guint8 *p = buf;
201         gint32 res = 0;
202         int shift = 0;
203
204         while (TRUE) {
205                 guint8 b = *p;
206                 p ++;
207
208                 res = res | (((int)(b & 0x7f)) << shift);
209                 shift += 7;
210                 if (!(b & 0x80)) {
211                         if (shift < 32 && (b & 0x40))
212                                 res |= - (1 << shift);
213                         break;
214                 }
215         }
216
217         *endbuf = p;
218
219         return res;
220 }
221
222 /*
223  * mono_unwind_ops_encode:
224  *
225  *   Encode the unwind ops in UNWIND_OPS into the compact DWARF encoding.
226  * Return a pointer to malloc'ed memory.
227  */
228 guint8*
229 mono_unwind_ops_encode (GSList *unwind_ops, guint32 *out_len)
230 {
231         GSList *l;
232         MonoUnwindOp *op;
233         int loc;
234         guint8 *buf, *p, *res;
235
236         p = buf = g_malloc0 (4096);
237
238         loc = 0;
239         l = unwind_ops;
240         for (; l; l = l->next) {
241                 int reg;
242
243                 op = l->data;
244
245                 /* Convert the register from the hw encoding to the dwarf encoding */
246                 reg = mono_hw_reg_to_dwarf_reg (op->reg);
247
248                 /* Emit an advance_loc if neccesary */
249                 while (op->when > loc) {
250                         if (op->when - loc < 32) {
251                                 *p ++ = DW_CFA_advance_loc | (op->when - loc);
252                                 loc = op->when;
253                         } else {
254                                 *p ++ = DW_CFA_advance_loc | (30);
255                                 loc += 30;
256                         }
257                 }                       
258
259                 switch (op->op) {
260                 case DW_CFA_def_cfa:
261                         *p ++ = op->op;
262                         encode_uleb128 (reg, p, &p);
263                         encode_uleb128 (op->val, p, &p);
264                         break;
265                 case DW_CFA_def_cfa_offset:
266                         *p ++ = op->op;
267                         encode_uleb128 (op->val, p, &p);
268                         break;
269                 case DW_CFA_def_cfa_register:
270                         *p ++ = op->op;
271                         encode_uleb128 (reg, p, &p);
272                         break;
273                 case DW_CFA_offset:
274                         if (reg > 63) {
275                                 *p ++ = DW_CFA_offset_extended_sf;
276                                 encode_uleb128 (reg, p, &p);
277                                 encode_sleb128 (op->val / DWARF_DATA_ALIGN, p, &p);
278                         } else {
279                                 *p ++ = DW_CFA_offset | reg;
280                                 encode_uleb128 (op->val / DWARF_DATA_ALIGN, p, &p);
281                         }
282                         break;
283                 default:
284                         g_assert_not_reached ();
285                         break;
286                 }
287         }
288         
289         g_assert (p - buf < 4096);
290         *out_len = p - buf;
291         res = g_malloc (p - buf);
292         memcpy (res, buf, p - buf);
293         g_free (buf);
294         return res;
295 }
296
297 #if 0
298 #define UNW_DEBUG(stmt) do { stmt; } while (0)
299 #else
300 #define UNW_DEBUG(stmt) do { } while (0)
301 #endif
302
303 static G_GNUC_UNUSED void
304 print_dwarf_state (int cfa_reg, int cfa_offset, int ip, int nregs, Loc *locations)
305 {
306         int i;
307
308         printf ("\t%x: cfa=r%d+%d ", ip, cfa_reg, cfa_offset);
309
310         for (i = 0; i < nregs; ++i)
311                 if (locations [i].loc_type == LOC_OFFSET)
312                         printf ("r%d@%d(cfa) ", i, locations [i].offset);
313         printf ("\n");
314 }
315
316 /*
317  * Given the state of the current frame as stored in REGS, execute the unwind 
318  * operations in unwind_info until the location counter reaches POS. The result is 
319  * stored back into REGS. OUT_CFA will receive the value of the CFA.
320  * This function is signal safe.
321  */
322 void
323 mono_unwind_frame (guint8 *unwind_info, guint32 unwind_info_len, 
324                                    guint8 *start_ip, guint8 *end_ip, guint8 *ip, mgreg_t *regs, 
325                                    int nregs, guint8 **out_cfa)
326 {
327         Loc locations [NUM_REGS];
328         int i, pos, reg, cfa_reg, cfa_offset;
329         guint8 *p;
330         guint8 *cfa_val;
331
332         for (i = 0; i < NUM_REGS; ++i)
333                 locations [i].loc_type = LOC_SAME;
334
335         p = unwind_info;
336         pos = 0;
337         cfa_reg = -1;
338         cfa_offset = -1;
339         while (pos <= ip - start_ip && p < unwind_info + unwind_info_len) {
340                 int op = *p & 0xc0;
341
342                 switch (op) {
343                 case DW_CFA_advance_loc:
344                         UNW_DEBUG (print_dwarf_state (cfa_reg, cfa_offset, pos, nregs, locations));
345                         pos += *p & 0x3f;
346                         p ++;
347                         break;
348                 case DW_CFA_offset:
349                         reg = *p & 0x3f;
350                         p ++;
351                         locations [reg].loc_type = LOC_OFFSET;
352                         locations [reg].offset = decode_uleb128 (p, &p) * DWARF_DATA_ALIGN;
353                         break;
354                 case 0: {
355                         int ext_op = *p;
356                         p ++;
357                         switch (ext_op) {
358                         case DW_CFA_def_cfa:
359                                 cfa_reg = decode_uleb128 (p, &p);
360                                 cfa_offset = decode_uleb128 (p, &p);
361                                 break;
362                         case DW_CFA_def_cfa_offset:
363                                 cfa_offset = decode_uleb128 (p, &p);
364                                 break;
365                         case DW_CFA_def_cfa_register:
366                                 cfa_reg = decode_uleb128 (p, &p);
367                                 break;
368                         case DW_CFA_offset_extended_sf:
369                                 reg = decode_uleb128 (p, &p);
370                                 locations [reg].loc_type = LOC_OFFSET;
371                                 locations [reg].offset = decode_sleb128 (p, &p) * DWARF_DATA_ALIGN;
372                                 break;
373                         case DW_CFA_advance_loc4:
374                                 pos += *(guint32*)p;
375                                 p += 4;
376                                 break;
377                         default:
378                                 g_assert_not_reached ();
379                         }
380                         break;
381                 }
382                 default:
383                         g_assert_not_reached ();
384                 }
385         }
386
387         cfa_val = (guint8*)regs [mono_dwarf_reg_to_hw_reg (cfa_reg)] + cfa_offset;
388         for (i = 0; i < NUM_REGS; ++i) {
389                 if (locations [i].loc_type == LOC_OFFSET) {
390                         int hreg = mono_dwarf_reg_to_hw_reg (i);
391                         g_assert (hreg < nregs);
392                         regs [hreg] = *(gssize*)(cfa_val + locations [i].offset);
393                 }
394         }
395
396         *out_cfa = cfa_val;
397 }
398
399 void
400 mono_unwind_init (void)
401 {
402         InitializeCriticalSection (&unwind_mutex);
403
404         mono_counters_register ("Unwind info size", MONO_COUNTER_JIT | MONO_COUNTER_INT, &unwind_info_size);
405 }
406
407 void
408 mono_unwind_cleanup (void)
409 {
410         int i;
411
412         DeleteCriticalSection (&unwind_mutex);
413
414         if (!cached_info)
415                 return;
416
417         for (i = 0; i < cached_info_next; ++i) {
418                 MonoUnwindInfo *cached = cached_info [i];
419
420                 g_free (cached);
421         }
422
423         g_free (cached_info);
424 }
425
426 /*
427  * mono_cache_unwind_info
428  *
429  *   Save UNWIND_INFO in the unwind info cache and return an id which can be passed
430  * to mono_get_cached_unwind_info to get a cached copy of the info.
431  * A copy is made of the unwind info.
432  * This function is useful for two reasons:
433  * - many methods have the same unwind info
434  * - MonoJitInfo->used_regs is an int so it can't store the pointer to the unwind info
435  */
436 guint32
437 mono_cache_unwind_info (guint8 *unwind_info, guint32 unwind_info_len)
438 {
439         int i;
440         MonoUnwindInfo *info;
441
442         unwind_lock ();
443
444         if (cached_info == NULL) {
445                 cached_info_size = 16;
446                 cached_info = g_new0 (MonoUnwindInfo*, cached_info_size);
447         }
448
449         for (i = 0; i < cached_info_next; ++i) {
450                 MonoUnwindInfo *cached = cached_info [i];
451
452                 if (cached->len == unwind_info_len && memcmp (cached->info, unwind_info, unwind_info_len) == 0) {
453                         unwind_unlock ();
454                         return i;
455                 }
456         }
457
458         info = g_malloc (sizeof (MonoUnwindInfo) + unwind_info_len);
459         info->len = unwind_info_len;
460         memcpy (&info->info, unwind_info, unwind_info_len);
461
462         i = cached_info_next;
463         
464         if (cached_info_next >= cached_info_size) {
465                 MonoUnwindInfo **old_table, **new_table;
466
467                 /*
468                  * Have to resize the table, while synchronizing with 
469                  * mono_get_cached_unwind_info () using hazard pointers.
470                  */
471
472                 old_table = cached_info;
473                 new_table = g_new0 (MonoUnwindInfo*, cached_info_size * 2);
474
475                 memcpy (new_table, cached_info, cached_info_size * sizeof (MonoUnwindInfo*));
476
477                 mono_memory_barrier ();
478
479                 cached_info = new_table;
480
481                 mono_memory_barrier ();
482
483                 mono_thread_hazardous_free_or_queue (old_table, g_free);
484
485                 cached_info_size *= 2;
486         }
487
488         cached_info [cached_info_next ++] = info;
489
490         unwind_info_size += sizeof (MonoUnwindInfo) + unwind_info_len;
491
492         unwind_unlock ();
493         return i;
494 }
495
496 static gpointer
497 get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
498 {
499         gpointer p;
500
501         for (;;) {
502                 /* Get the pointer */
503                 p = *pp;
504                 /* If we don't have hazard pointers just return the
505                    pointer. */
506                 if (!hp)
507                         return p;
508                 /* Make it hazardous */
509                 mono_hazard_pointer_set (hp, hazard_index, p);
510                 /* Check that it's still the same.  If not, try
511                    again. */
512                 if (*pp != p) {
513                         mono_hazard_pointer_clear (hp, hazard_index);
514                         continue;
515                 }
516                 break;
517         }
518
519         return p;
520 }
521
522 /*
523  * This function is signal safe.
524  */
525 guint8*
526 mono_get_cached_unwind_info (guint32 index, guint32 *unwind_info_len)
527 {
528         MonoUnwindInfo **table;
529         MonoUnwindInfo *info;
530         guint8 *data;
531         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
532
533         table = get_hazardous_pointer ((gpointer volatile*)&cached_info, hp, 0);
534
535         info = table [index];
536
537         *unwind_info_len = info->len;
538         data = info->info;
539
540         mono_hazard_pointer_clear (hp, 0);
541
542         return data;
543 }
544
545 /*
546  * mono_unwind_get_dwarf_data_align:
547  *
548  *   Return the data alignment used by the encoded unwind information.
549  */
550 int
551 mono_unwind_get_dwarf_data_align (void)
552 {
553         return DWARF_DATA_ALIGN;
554 }
555
556 /*
557  * mono_unwind_get_dwarf_pc_reg:
558  *
559  *   Return the dwarf register number of the register holding the ip of the
560  * previous frame.
561  */
562 int
563 mono_unwind_get_dwarf_pc_reg (void)
564 {
565         return DWARF_PC_REG;
566 }
567
568 static void
569 decode_cie_op (guint8 *p, guint8 **endp)
570 {
571         int op = *p & 0xc0;
572
573         switch (op) {
574         case DW_CFA_advance_loc:
575                 p ++;
576                 break;
577         case DW_CFA_offset:
578                 p ++;
579                 decode_uleb128 (p, &p);
580                 break;
581         case 0: {
582                 int ext_op = *p;
583                 p ++;
584                 switch (ext_op) {
585                 case DW_CFA_def_cfa:
586                         decode_uleb128 (p, &p);
587                         decode_uleb128 (p, &p);
588                         break;
589                 case DW_CFA_def_cfa_offset:
590                         decode_uleb128 (p, &p);
591                         break;
592                 case DW_CFA_def_cfa_register:
593                         decode_uleb128 (p, &p);
594                         break;
595                 case DW_CFA_advance_loc4:
596                         p += 4;
597                         break;
598                 default:
599                         g_assert_not_reached ();
600                 }
601                 break;
602         }
603         default:
604                 g_assert_not_reached ();
605         }
606
607         *endp = p;
608 }
609
610 /*
611  * mono_unwind_get_ops_from_fde:
612  *
613  *   Return the unwind opcodes encoded in a DWARF FDE entry.
614  */
615 guint8*
616 mono_unwind_get_ops_from_fde (guint8 *fde, guint32 *out_len, guint32 *code_len)
617 {
618         guint8 *p, *cie, *code, *fde_cfi, *cie_cfi;
619         gint32 fde_len, cie_offset, pc_begin, pc_range, aug_len, fde_data_len;
620         gint32 cie_len, cie_id, cie_version, code_align, data_align, return_reg;
621         gint32 i, cie_aug_len, buf_len;
622         char *cie_aug_str;
623         guint8 *buf;
624
625         /* 
626          * http://refspecs.freestandards.org/LSB_3.0.0/LSB-Core-generic/LSB-Core-generic/ehframechpt.html
627          */
628
629         /* Decode FDE */
630
631         p = fde;
632         // FIXME: Endianess ?
633         fde_len = *(guint32*)p;
634         g_assert (fde_len != 0xffffffff && fde_len != 0);
635         p += 4;
636         cie_offset = *(guint32*)p;
637         cie = p - cie_offset;
638         p += 4;
639         pc_begin = *(gint32*)p;
640         code = p + pc_begin;
641         p += 4;
642         pc_range = *(guint32*)p;
643         p += 4;
644         aug_len = decode_uleb128 (p, &p);
645         g_assert (aug_len == 0);
646         fde_cfi = p;
647         fde_data_len = fde + 4 + fde_len - p;
648
649         if (code_len)
650                 *code_len = pc_range;
651
652         /* Decode CIE */
653         p = cie;
654         cie_len = *(guint32*)p;
655         p += 4;
656         cie_id = *(guint32*)p;
657         g_assert (cie_id == 0);
658         p += 4;
659         cie_version = *p;
660         g_assert (cie_version == 1);
661         p += 1;
662         cie_aug_str = (char*)p;
663         p += strlen (cie_aug_str) + 1;
664         code_align = decode_uleb128 (p, &p);
665         data_align = decode_sleb128 (p, &p);
666         return_reg = decode_uleb128 (p, &p);
667         if (strstr (cie_aug_str, "z")) {
668                 cie_aug_len = decode_uleb128 (p, &p);
669                 p += cie_aug_len;
670         }
671         cie_cfi = p;
672
673         /* Make sure the FDE uses the same constants as we do */
674         g_assert (code_align == 1);
675         g_assert (data_align == DWARF_DATA_ALIGN);
676         g_assert (return_reg == DWARF_PC_REG);
677
678         buf_len = (cie + cie_len + 4 - cie_cfi) + (fde + fde_len + 4 - fde_cfi);
679         buf = g_malloc0 (buf_len);
680
681         i = 0;
682         p = cie_cfi;
683         while (p < cie + cie_len + 4) {
684                 if (*p == DW_CFA_nop)
685                         break;
686                 else
687                         decode_cie_op (p, &p);
688         }
689         memcpy (buf + i, cie_cfi, p - cie_cfi);
690         i += p - cie_cfi;
691
692         p = fde_cfi;
693         while (p < fde + fde_len + 4) {
694                 if (*p == DW_CFA_nop)
695                         break;
696                 else
697                         decode_cie_op (p, &p);
698         }
699         memcpy (buf + i, fde_cfi, p - fde_cfi);
700         i += p - fde_cfi;
701         g_assert (i <= buf_len);
702
703         *out_len = i;
704
705         return g_realloc (buf, i);
706 }