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