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