xref: /minix/sys/lib/libunwind/AddressSpace.hpp (revision 00b67f09) 
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     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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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