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
LocalAddressSpace(findPCRange_t findPCRange_)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
get8(pint_t addr)71 uint8_t get8(pint_t addr) {
72 uint8_t val;
73 memcpy(&val, (void *)addr, sizeof(val));
74 return val;
75 }
76
get16(pint_t addr)77 uint16_t get16(pint_t addr) {
78 uint16_t val;
79 memcpy(&val, (void *)addr, sizeof(val));
80 return val;
81 }
82
get32(pint_t addr)83 uint32_t get32(pint_t addr) {
84 uint32_t val;
85 memcpy(&val, (void *)addr, sizeof(val));
86 return val;
87 }
88
get64(pint_t addr)89 uint64_t get64(pint_t addr) {
90 uint64_t val;
91 memcpy(&val, (void *)addr, sizeof(val));
92 return val;
93 }
94
getP(pint_t addr)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
getULEB128(pint_t & addr,pint_t end)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
getSLEB128(pint_t & addr,pint_t end)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
getEncodedP(pint_t & addr,pint_t end,uint8_t encoding,const unw_proc_info_t * ctx)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
findFDE(pint_t pc,pint_t & fdeStart,pint_t & data_base)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
addFDE(pint_t pcStart,pint_t pcEnd,pint_t fde)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
removeFDE(pint_t pcStart,pint_t pcEnd,pint_t fde)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
removeDSO(pint_t ehFrameBase)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
setLazyReload()338 void setLazyReload() {
339 pthread_rwlock_wrlock(&fdeTreeLock);
340 needsReload = true;
341 pthread_rwlock_unlock(&fdeTreeLock);
342 }
343
344 private:
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
lazyReload()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
addDSO(pint_t header,pint_t data_base)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
phdr_callback(struct dl_phdr_info * info,size_t size,void * data_)411 static 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
rangeCmp(void * context,const void * n1_,const void * n2_)441 static 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
rangeCmpKey(void * context,const void * n_,const void * pc_)453 static 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
dsoTableCmp(void * context,const void * n1_,const void * n2_)463 static 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
dsoTableCmpKey(void * context,const void * n_,const void * ptr_)474 static 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