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
LocalAddressSpace(findPCRange_t findPCRange_)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
get8(pint_t addr)78 uint8_t get8(pint_t addr) {
79 uint8_t val;
80 memcpy(&val, (void *)addr, sizeof(val));
81 return val;
82 }
83
get16(pint_t addr)84 uint16_t get16(pint_t addr) {
85 uint16_t val;
86 memcpy(&val, (void *)addr, sizeof(val));
87 return val;
88 }
89
get32(pint_t addr)90 uint32_t get32(pint_t addr) {
91 uint32_t val;
92 memcpy(&val, (void *)addr, sizeof(val));
93 return val;
94 }
95
get64(pint_t addr)96 uint64_t get64(pint_t addr) {
97 uint64_t val;
98 memcpy(&val, (void *)addr, sizeof(val));
99 return val;
100 }
101
getP(pint_t addr)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
getULEB128(pint_t & addr,pint_t end)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
getSLEB128(pint_t & addr,pint_t end)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
getEncodedP(pint_t & addr,pint_t end,uint8_t encoding,const unw_proc_info_t * ctx)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
findFDE(pint_t pc,pint_t & fdeStart,pint_t & data_base)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
addFDE(pint_t pcStart,pint_t pcEnd,pint_t fde)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
removeFDE(pint_t pcStart,pint_t pcEnd,pint_t fde)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
removeDSO(pint_t ehFrameBase)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
setLazyReload()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
lazyReload()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
addDSO(pint_t header,pint_t data_base)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
phdr_callback(struct dl_phdr_info * info,size_t size,void * data_)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
rangeCmp(void * context,const void * n1_,const void * n2_)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
rangeCmpKey(void * context,const void * n_,const void * pc_)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
dsoTableCmp(void * context,const void * n1_,const void * n2_)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
dsoTableCmpKey(void * context,const void * n_,const void * ptr_)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__
496