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