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 29namespace _Unwind { 30 31static int rangeCmp(void *, const void *, const void *); 32static int rangeCmpKey(void *, const void *, const void *); 33static int dsoTableCmp(void *, const void *, const void *); 34static int dsoTableCmpKey(void *, const void *, const void *); 35static int phdr_callback(struct dl_phdr_info *, size_t, void *); 36 37struct 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. 50class LocalAddressSpace { 51public: 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 344private: 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 411static 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 441static 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 453static 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 463static 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 474static 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