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