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 |= (-1LL) << 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 pint_t len = n->hdr_entries; 267 while (len) { 268 pint_t next = first + ((len + 1) / 2) * 8; 269 pint_t nextPC = base + (int32_t)get32(next); 270 if (nextPC == pc) { 271 first = next; 272 break; 273 } 274 if (nextPC < pc) { 275 len -= (len + 1) / 2; 276 first = next; 277 } else if (len == 1) 278 break; 279 else 280 len = (len + 1) / 2; 281 } 282 fdeStart = base + (int32_t)get32(first + 4); 283 data_base = n->data_base; 284 return true; 285 } 286 287 bool addFDE(pint_t pcStart, pint_t pcEnd, pint_t fde) { 288 pthread_rwlock_wrlock(&fdeTreeLock); 289 Range *n = (Range *)malloc(sizeof(*n)); 290 n->hdr_base = fde; 291 n->hdr_start = 0; 292 n->hdr_entries = 0; 293 n->first_pc = pcStart; 294 n->last_pc = pcEnd; 295 n->data_base = 0; 296 n->ehframe_base = 0; 297 if (rb_tree_insert_node(&segmentTree, n) == n) { 298 pthread_rwlock_unlock(&fdeTreeLock); 299 return true; 300 } 301 free(n); 302 pthread_rwlock_unlock(&fdeTreeLock); 303 return false; 304 } 305 306 bool removeFDE(pint_t pcStart, pint_t pcEnd, pint_t fde) { 307 pthread_rwlock_wrlock(&fdeTreeLock); 308 Range *n = (Range *)rb_tree_find_node(&segmentTree, &pcStart); 309 if (n == NULL) { 310 pthread_rwlock_unlock(&fdeTreeLock); 311 return false; 312 } 313 assert(n->first_pc == pcStart); 314 assert(n->last_pc == pcEnd); 315 assert(n->hdr_base == fde); 316 assert(n->hdr_start == 0); 317 assert(n->hdr_entries == 0); 318 assert(n->data_base == 0); 319 assert(n->ehframe_base == 0); 320 rb_tree_remove_node(&segmentTree, n); 321 free(n); 322 pthread_rwlock_unlock(&fdeTreeLock); 323 return true; 324 } 325 326 void removeDSO(pint_t ehFrameBase) { 327 pthread_rwlock_wrlock(&fdeTreeLock); 328 Range *n; 329 n = (Range *)rb_tree_find_node(&dsoTree, &ehFrameBase); 330 if (n == NULL) { 331 pthread_rwlock_unlock(&fdeTreeLock); 332 return; 333 } 334 rb_tree_remove_node(&dsoTree, n); 335 rb_tree_remove_node(&segmentTree, n); 336 free(n); 337 pthread_rwlock_unlock(&fdeTreeLock); 338 } 339 340 void setLazyReload() { 341 pthread_rwlock_wrlock(&fdeTreeLock); 342 needsReload = true; 343 pthread_rwlock_unlock(&fdeTreeLock); 344 } 345 346 private: 347 findPCRange_t findPCRange; 348 bool needsReload; 349 pthread_rwlock_t fdeTreeLock; 350 rb_tree_t segmentTree; 351 rb_tree_t dsoTree; 352 353 friend int phdr_callback(struct dl_phdr_info *, size_t, void *); 354 friend int rangeCmp(void *, const void *, const void *); 355 friend int rangeCmpKey(void *, const void *, const void *); 356 friend int dsoTableCmp(void *, const void *, const void *); 357 friend int dsoTableCmpKey(void *, const void *, const void *); 358 359 void updateRange(); 360 361 struct Range { 362 rb_node_t range_link; 363 rb_node_t dso_link; 364 pint_t hdr_base; // Pointer to FDE if hdr_start == 0 365 pint_t hdr_start; 366 pint_t hdr_entries; 367 pint_t first_pc; 368 pint_t last_pc; 369 pint_t data_base; 370 pint_t ehframe_base; 371 }; 372 373 void lazyReload() { 374 pthread_rwlock_wrlock(&fdeTreeLock); 375 dl_iterate_phdr(phdr_callback, this); 376 needsReload = false; 377 pthread_rwlock_unlock(&fdeTreeLock); 378 } 379 380 void addDSO(pint_t header, pint_t data_base) { 381 if (header == 0) 382 return; 383 if (get8(header) != 1) 384 return; 385 if (get8(header + 3) != (DW_EH_PE_datarel | DW_EH_PE_sdata4)) 386 return; 387 pint_t end = header + 4; 388 pint_t ehframe_base = getEncodedP(end, 0, get8(header + 1), NULL); 389 pint_t entries = getEncodedP(end, 0, get8(header + 2), NULL); 390 pint_t start = (end + 3) & ~pint_t(3); 391 if (entries == 0) 392 return; 393 Range *n = (Range *)malloc(sizeof(*n)); 394 n->hdr_base = header; 395 n->hdr_start = start; 396 n->hdr_entries = entries; 397 n->first_pc = header + (int32_t)get32(n->hdr_start); 398 pint_t tmp; 399 (*findPCRange)( 400 *this, header + (int32_t)get32(n->hdr_start + (entries - 1) * 8 + 4), 401 tmp, n->last_pc); 402 n->data_base = data_base; 403 n->ehframe_base = ehframe_base; 404 405 if (rb_tree_insert_node(&segmentTree, n) != n) { 406 free(n); 407 return; 408 } 409 rb_tree_insert_node(&dsoTree, n); 410 } 411 }; 412 413 static int phdr_callback(struct dl_phdr_info *info, size_t size, void *data_) { 414 LocalAddressSpace *data = (LocalAddressSpace *)data_; 415 size_t eh_frame = 0, data_base = 0; 416 const Elf_Phdr *hdr = info->dlpi_phdr; 417 const Elf_Phdr *last_hdr = hdr + info->dlpi_phnum; 418 const Elf_Dyn *dyn; 419 420 for (; hdr != last_hdr; ++hdr) { 421 switch (hdr->p_type) { 422 case PT_GNU_EH_FRAME: 423 eh_frame = info->dlpi_addr + hdr->p_vaddr; 424 break; 425 case PT_DYNAMIC: 426 dyn = (const Elf_Dyn *)(info->dlpi_addr + hdr->p_vaddr); 427 while (dyn->d_tag != DT_NULL) { 428 if (dyn->d_tag == DT_PLTGOT) { 429 data_base = info->dlpi_addr + dyn->d_un.d_ptr; 430 break; 431 } 432 ++dyn; 433 } 434 } 435 } 436 437 if (eh_frame) 438 data->addDSO(eh_frame, data_base); 439 440 return 0; 441 } 442 443 static int rangeCmp(void *context, const void *n1_, const void *n2_) { 444 const LocalAddressSpace::Range *n1 = (const LocalAddressSpace::Range *)n1_; 445 const LocalAddressSpace::Range *n2 = (const LocalAddressSpace::Range *)n2_; 446 447 if (n1->first_pc < n2->first_pc) 448 return -1; 449 if (n1->first_pc > n2->first_pc) 450 return 1; 451 assert(n1->last_pc == n2->last_pc); 452 return 0; 453 } 454 455 static int rangeCmpKey(void *context, const void *n_, const void *pc_) { 456 const LocalAddressSpace::Range *n = (const LocalAddressSpace::Range *)n_; 457 const LocalAddressSpace::pint_t *pc = (const LocalAddressSpace::pint_t *)pc_; 458 if (n->last_pc < *pc) 459 return -1; 460 if (n->first_pc > *pc) 461 return 1; 462 return 0; 463 } 464 465 static int dsoTableCmp(void *context, const void *n1_, const void *n2_) { 466 const LocalAddressSpace::Range *n1 = (const LocalAddressSpace::Range *)n1_; 467 const LocalAddressSpace::Range *n2 = (const LocalAddressSpace::Range *)n2_; 468 469 if (n1->ehframe_base < n2->ehframe_base) 470 return -1; 471 if (n1->ehframe_base > n2->ehframe_base) 472 return 1; 473 return 0; 474 } 475 476 static int dsoTableCmpKey(void *context, const void *n_, const void *ptr_) { 477 const LocalAddressSpace::Range *n = (const LocalAddressSpace::Range *)n_; 478 const LocalAddressSpace::pint_t *ptr = (const LocalAddressSpace::pint_t *)ptr_; 479 if (n->ehframe_base < *ptr) 480 return -1; 481 if (n->ehframe_base > *ptr) 482 return 1; 483 return 0; 484 } 485 486 } // namespace _Unwind 487 488 #endif // __ADDRESSSPACE_HPP__ 489