Home | History | Annotate | Line # | Download | only in libunwind
      1 //===------------------------- AddressSpace.hpp ---------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is dual licensed under the MIT and the University of Illinois Open
      6 // Source Licenses. See LICENSE.TXT for details.
      7 //
      8 //
      9 // Abstracts accessing local vs remote address spaces.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #ifndef __ADDRESSSPACE_HPP__
     14 #define __ADDRESSSPACE_HPP__
     15 
     16 #include <sys/rbtree.h>
     17 #include <cassert>
     18 #include <cstddef>
     19 #include <cstdint>
     20 #include <cstdlib>
     21 #include <cstring>
     22 #include <dlfcn.h>
     23 #include <elf.h>
     24 #include <link.h>
     25 #include <pthread.h>
     26 
     27 #include "dwarf2.h"
     28 
     29 namespace _Unwind {
     30 
     31 static int rangeCmp(void *, const void *, const void *);
     32 static int rangeCmpKey(void *, const void *, const void *);
     33 static int dsoTableCmp(void *, const void *, const void *);
     34 static int dsoTableCmpKey(void *, const void *, const void *);
     35 static int phdr_callback(struct dl_phdr_info *, size_t, void *);
     36 
     37 struct unw_proc_info_t {
     38   uintptr_t data_base;       // Base address for data-relative relocations
     39   uintptr_t start_ip;        // Start address of function
     40   uintptr_t end_ip;          // First address after end of function
     41   uintptr_t lsda;            // Address of Language Specific Data Area
     42   uintptr_t handler;         // Personality routine
     43   uintptr_t extra_args;      // Extra stack space for frameless routines
     44   uintptr_t unwind_info;     // Address of DWARF unwind info
     45 };
     46 
     47 /// LocalAddressSpace is used as a template parameter to UnwindCursor when
     48 /// unwinding a thread in the same process.  The wrappers compile away,
     49 /// making local unwinds fast.
     50 class LocalAddressSpace {
     51 public:
     52   typedef uintptr_t pint_t;
     53   typedef intptr_t sint_t;
     54 
     55   typedef void (*findPCRange_t)(LocalAddressSpace &, pint_t, pint_t &pcStart,
     56                                 pint_t &pcEnd);
     57 
     58   LocalAddressSpace(findPCRange_t findPCRange_)
     59       : findPCRange(findPCRange_), needsReload(true) {
     60     static const rb_tree_ops_t segmentTreeOps = {
     61       rangeCmp, rangeCmpKey, offsetof(Range, range_link), NULL
     62     };
     63     static const rb_tree_ops_t dsoTreeOps = {
     64       dsoTableCmp, dsoTableCmpKey, offsetof(Range, dso_link), NULL
     65     };
     66     rb_tree_init(&segmentTree, &segmentTreeOps);
     67     rb_tree_init(&dsoTree, &dsoTreeOps);
     68     pthread_rwlock_init(&fdeTreeLock, NULL);
     69   }
     70 
     71   uint8_t get8(pint_t addr) {
     72     uint8_t val;
     73     memcpy(&val, (void *)addr, sizeof(val));
     74     return val;
     75   }
     76 
     77   uint16_t get16(pint_t addr) {
     78     uint16_t val;
     79     memcpy(&val, (void *)addr, sizeof(val));
     80     return val;
     81   }
     82 
     83   uint32_t get32(pint_t addr) {
     84     uint32_t val;
     85     memcpy(&val, (void *)addr, sizeof(val));
     86     return val;
     87   }
     88 
     89   uint64_t get64(pint_t addr) {
     90     uint64_t val;
     91     memcpy(&val, (void *)addr, sizeof(val));
     92     return val;
     93   }
     94 
     95   uintptr_t getP(pint_t addr) {
     96     if (sizeof(uintptr_t) == sizeof(uint32_t))
     97       return get32(addr);
     98     else
     99       return get64(addr);
    100   }
    101 
    102   uint64_t getULEB128(pint_t &addr, pint_t end) {
    103     uint64_t result = 0;
    104     uint8_t byte;
    105     int bit = 0;
    106     do {
    107       uint64_t b;
    108 
    109       assert(addr != end);
    110 
    111       byte = get8(addr++);
    112       b = byte & 0x7f;
    113 
    114       assert(bit < 64);
    115       assert(b << bit >> bit == b);
    116 
    117       result |= b << bit;
    118       bit += 7;
    119     } while (byte >= 0x80);
    120     return result;
    121   }
    122 
    123   int64_t getSLEB128(pint_t &addr, pint_t end) {
    124     uint64_t result = 0;
    125     uint8_t byte;
    126     int bit = 0;
    127     do {
    128       uint64_t b;
    129 
    130       assert(addr != end);
    131 
    132       byte = get8(addr++);
    133       b = byte & 0x7f;
    134 
    135       assert(bit < 64);
    136       assert(b << bit >> bit == b);
    137 
    138       result |= b << bit;
    139       bit += 7;
    140     } while (byte >= 0x80);
    141     // sign extend negative numbers
    142     if ((byte & 0x40) != 0)
    143       result |= (~0ULL) << bit;
    144     return result;
    145   }
    146 
    147   pint_t getEncodedP(pint_t &addr, pint_t end, uint8_t encoding,
    148                      const unw_proc_info_t *ctx) {
    149     pint_t startAddr = addr;
    150     const uint8_t *p = (uint8_t *)addr;
    151     pint_t result;
    152 
    153     if (encoding == DW_EH_PE_omit)
    154       return 0;
    155     if (encoding == DW_EH_PE_aligned) {
    156       addr = (addr + sizeof(pint_t) - 1) & sizeof(pint_t);
    157       return getP(addr);
    158     }
    159 
    160     // first get value
    161     switch (encoding & 0x0F) {
    162     case DW_EH_PE_ptr:
    163       result = getP(addr);
    164       p += sizeof(pint_t);
    165       addr = (pint_t)p;
    166       break;
    167     case DW_EH_PE_uleb128:
    168       result = getULEB128(addr, end);
    169       break;
    170     case DW_EH_PE_udata2:
    171       result = get16(addr);
    172       p += 2;
    173       addr = (pint_t)p;
    174       break;
    175     case DW_EH_PE_udata4:
    176       result = get32(addr);
    177       p += 4;
    178       addr = (pint_t)p;
    179       break;
    180     case DW_EH_PE_udata8:
    181       result = get64(addr);
    182       p += 8;
    183       addr = (pint_t)p;
    184       break;
    185     case DW_EH_PE_sleb128:
    186       result = getSLEB128(addr, end);
    187       break;
    188     case DW_EH_PE_sdata2:
    189       result = (int16_t)get16(addr);
    190       p += 2;
    191       addr = (pint_t)p;
    192       break;
    193     case DW_EH_PE_sdata4:
    194       result = (int32_t)get32(addr);
    195       p += 4;
    196       addr = (pint_t)p;
    197       break;
    198     case DW_EH_PE_sdata8:
    199       result = get64(addr);
    200       p += 8;
    201       addr = (pint_t)p;
    202       break;
    203     case DW_EH_PE_omit:
    204       result = 0;
    205       break;
    206     default:
    207       assert(0 && "unknown pointer encoding");
    208     }
    209 
    210     // then add relative offset
    211     switch (encoding & 0x70) {
    212     case DW_EH_PE_absptr:
    213       // do nothing
    214       break;
    215     case DW_EH_PE_pcrel:
    216       result += startAddr;
    217       break;
    218     case DW_EH_PE_textrel:
    219       assert(0 && "DW_EH_PE_textrel pointer encoding not supported");
    220       break;
    221     case DW_EH_PE_datarel:
    222       assert(ctx != NULL && "DW_EH_PE_datarel without context");
    223       if (ctx)
    224         result += ctx->data_base;
    225       break;
    226     case DW_EH_PE_funcrel:
    227       assert(ctx != NULL && "DW_EH_PE_funcrel without context");
    228       if (ctx)
    229         result += ctx->start_ip;
    230       break;
    231     case DW_EH_PE_aligned:
    232       __builtin_unreachable();
    233     default:
    234       assert(0 && "unknown pointer encoding");
    235       break;
    236     }
    237 
    238     if (encoding & DW_EH_PE_indirect)
    239       result = getP(result);
    240 
    241     return result;
    242   }
    243 
    244   bool findFDE(pint_t pc, pint_t &fdeStart, pint_t &data_base) {
    245     Range *n;
    246     for (;;) {
    247       pthread_rwlock_rdlock(&fdeTreeLock);
    248       n = (Range *)rb_tree_find_node(&segmentTree, &pc);
    249       pthread_rwlock_unlock(&fdeTreeLock);
    250       if (n != NULL)
    251         break;
    252       if (!needsReload)
    253         break;
    254       lazyReload();
    255     }
    256     if (n == NULL)
    257       return false;
    258     if (n->hdr_start == 0) {
    259       fdeStart = n->hdr_base;
    260       data_base = n->data_base;
    261       return true;
    262     }
    263 
    264     pint_t base = n->hdr_base;
    265     pint_t first = n->hdr_start;
    266     for (pint_t len = n->hdr_entries; len > 1; ) {
    267       pint_t next = first + (len / 2) * 8;
    268       pint_t nextPC = base + (int32_t)get32(next);
    269       if (nextPC == pc) {
    270         first = next;
    271         break;
    272       }
    273       if (nextPC < pc) {
    274         first = next;
    275         len -= (len / 2);
    276       } else {
    277         len /= 2;
    278       }
    279     }
    280     fdeStart = base + (int32_t)get32(first + 4);
    281     data_base = n->data_base;
    282     return true;
    283   }
    284 
    285   bool addFDE(pint_t pcStart, pint_t pcEnd, pint_t fde) {
    286     Range *n = (Range *)malloc(sizeof(*n));
    287     n->hdr_base = fde;
    288     n->hdr_start = 0;
    289     n->hdr_entries = 0;
    290     n->first_pc = pcStart;
    291     n->last_pc = pcEnd;
    292     n->data_base = 0;
    293     n->ehframe_base = 0;
    294     pthread_rwlock_wrlock(&fdeTreeLock);
    295     if (static_cast<Range *>(rb_tree_insert_node(&segmentTree, n)) == n) {
    296       pthread_rwlock_unlock(&fdeTreeLock);
    297       return true;
    298     }
    299     free(n);
    300     pthread_rwlock_unlock(&fdeTreeLock);
    301     return false;
    302   }
    303 
    304   bool removeFDE(pint_t pcStart, pint_t pcEnd, pint_t fde) {
    305     pthread_rwlock_wrlock(&fdeTreeLock);
    306     Range *n = static_cast<Range *>(rb_tree_find_node(&segmentTree, &pcStart));
    307     if (n == NULL) {
    308       pthread_rwlock_unlock(&fdeTreeLock);
    309       return false;
    310     }
    311     assert(n->first_pc == pcStart);
    312     assert(n->last_pc == pcEnd);
    313     assert(n->hdr_base == fde);
    314     assert(n->hdr_start == 0);
    315     assert(n->hdr_entries == 0);
    316     assert(n->data_base == 0);
    317     assert(n->ehframe_base == 0);
    318     rb_tree_remove_node(&segmentTree, n);
    319     free(n);
    320     pthread_rwlock_unlock(&fdeTreeLock);
    321     return true;
    322   }
    323 
    324   void removeDSO(pint_t ehFrameBase) {
    325     pthread_rwlock_wrlock(&fdeTreeLock);
    326     Range *n;
    327     n = (Range *)rb_tree_find_node(&dsoTree, &ehFrameBase);
    328     if (n == NULL) {
    329       pthread_rwlock_unlock(&fdeTreeLock);
    330       return;
    331     }
    332     rb_tree_remove_node(&dsoTree, n);
    333     rb_tree_remove_node(&segmentTree, n);
    334     free(n);
    335     pthread_rwlock_unlock(&fdeTreeLock);
    336   }
    337 
    338   void setLazyReload() {
    339     pthread_rwlock_wrlock(&fdeTreeLock);
    340     needsReload = true;
    341     pthread_rwlock_unlock(&fdeTreeLock);
    342   }
    343 
    344 private:
    345   findPCRange_t findPCRange;
    346   bool needsReload;
    347   pthread_rwlock_t fdeTreeLock;
    348   rb_tree_t segmentTree;
    349   rb_tree_t dsoTree;
    350 
    351   friend int phdr_callback(struct dl_phdr_info *, size_t, void *);
    352   friend int rangeCmp(void *, const void *, const void *);
    353   friend int rangeCmpKey(void *, const void *, const void *);
    354   friend int dsoTableCmp(void *, const void *, const void *);
    355   friend int dsoTableCmpKey(void *, const void *, const void *);
    356 
    357   void updateRange();
    358 
    359   struct Range {
    360     rb_node_t range_link;
    361     rb_node_t dso_link;
    362     pint_t hdr_base; // Pointer to FDE if hdr_start == 0
    363     pint_t hdr_start;
    364     pint_t hdr_entries;
    365     pint_t first_pc;
    366     pint_t last_pc;
    367     pint_t data_base;
    368     pint_t ehframe_base;
    369   };
    370 
    371   void lazyReload() {
    372     pthread_rwlock_wrlock(&fdeTreeLock);
    373     dl_iterate_phdr(phdr_callback, this);
    374     needsReload = false;
    375     pthread_rwlock_unlock(&fdeTreeLock);
    376   }
    377 
    378   void addDSO(pint_t header, pint_t data_base) {
    379     if (header == 0)
    380       return;
    381     if (get8(header) != 1)
    382       return;
    383     if (get8(header + 3) != (DW_EH_PE_datarel | DW_EH_PE_sdata4))
    384       return;
    385     pint_t end = header + 4;
    386     pint_t ehframe_base = getEncodedP(end, 0, get8(header + 1), NULL);
    387     pint_t entries = getEncodedP(end, 0, get8(header + 2), NULL);
    388     pint_t start = (end + 3) & ~pint_t(3);
    389     if (entries == 0)
    390       return;
    391     Range *n = (Range *)malloc(sizeof(*n));
    392     n->hdr_base = header;
    393     n->hdr_start = start;
    394     n->hdr_entries = entries;
    395     n->first_pc = header + (int32_t)get32(n->hdr_start);
    396     pint_t tmp;
    397     (*findPCRange)(
    398         *this, header + (int32_t)get32(n->hdr_start + (entries - 1) * 8 + 4),
    399         tmp, n->last_pc);
    400     n->data_base = data_base;
    401     n->ehframe_base = ehframe_base;
    402 
    403     if (static_cast<Range *>(rb_tree_insert_node(&segmentTree, n)) != n) {
    404       free(n);
    405       return;
    406     }
    407     rb_tree_insert_node(&dsoTree, n);
    408   }
    409 };
    410 
    411 static int phdr_callback(struct dl_phdr_info *info, size_t size, void *data_) {
    412   LocalAddressSpace *data = (LocalAddressSpace *)data_;
    413   size_t eh_frame = 0, data_base = 0;
    414   const Elf_Phdr *hdr = info->dlpi_phdr;
    415   const Elf_Phdr *last_hdr = hdr + info->dlpi_phnum;
    416   const Elf_Dyn *dyn;
    417 
    418   for (; hdr != last_hdr; ++hdr) {
    419     switch (hdr->p_type) {
    420     case PT_GNU_EH_FRAME:
    421       eh_frame = info->dlpi_addr + hdr->p_vaddr;
    422       break;
    423     case PT_DYNAMIC:
    424       dyn = (const Elf_Dyn *)(info->dlpi_addr + hdr->p_vaddr);
    425       while (dyn->d_tag != DT_NULL) {
    426         if (dyn->d_tag == DT_PLTGOT) {
    427           data_base = info->dlpi_addr + dyn->d_un.d_ptr;
    428           break;
    429         }
    430         ++dyn;
    431       }
    432     }
    433   }
    434 
    435   if (eh_frame)
    436     data->addDSO(eh_frame, data_base);
    437 
    438   return 0;
    439 }
    440 
    441 static int rangeCmp(void *context, const void *n1_, const void *n2_) {
    442   const LocalAddressSpace::Range *n1 = (const LocalAddressSpace::Range *)n1_;
    443   const LocalAddressSpace::Range *n2 = (const LocalAddressSpace::Range *)n2_;
    444 
    445   if (n1->first_pc < n2->first_pc)
    446     return -1;
    447   if (n1->first_pc > n2->first_pc)
    448     return 1;
    449   assert(n1->last_pc == n2->last_pc);
    450   return 0;
    451 }
    452 
    453 static int rangeCmpKey(void *context, const void *n_, const void *pc_) {
    454   const LocalAddressSpace::Range *n = (const LocalAddressSpace::Range *)n_;
    455   const LocalAddressSpace::pint_t *pc = (const LocalAddressSpace::pint_t *)pc_;
    456   if (n->last_pc < *pc)
    457     return -1;
    458   if (n->first_pc > *pc)
    459     return 1;
    460   return 0;
    461 }
    462 
    463 static int dsoTableCmp(void *context, const void *n1_, const void *n2_) {
    464   const LocalAddressSpace::Range *n1 = (const LocalAddressSpace::Range *)n1_;
    465   const LocalAddressSpace::Range *n2 = (const LocalAddressSpace::Range *)n2_;
    466 
    467   if (n1->ehframe_base < n2->ehframe_base)
    468     return -1;
    469   if (n1->ehframe_base > n2->ehframe_base)
    470     return 1;
    471   return 0;
    472 }
    473 
    474 static int dsoTableCmpKey(void *context, const void *n_, const void *ptr_) {
    475   const LocalAddressSpace::Range *n = (const LocalAddressSpace::Range *)n_;
    476   const LocalAddressSpace::pint_t *ptr = (const LocalAddressSpace::pint_t *)ptr_;
    477   if (n->ehframe_base < *ptr)
    478     return -1;
    479   if (n->ehframe_base > *ptr)
    480     return 1;
    481   return 0;
    482 }
    483 
    484 } // namespace _Unwind
    485 
    486 #endif // __ADDRESSSPACE_HPP__
    487