sys/lib/libunwind/AddressSpace.hpp

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