1//===-- DWARFDebugArangeSet.cpp -------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "DWARFDebugArangeSet.h"
11#include "llvm/Support/Format.h"
12#include "llvm/Support/raw_ostream.h"
13#include <algorithm>
14#include <cassert>
15using namespace llvm;
16
17void DWARFDebugArangeSet::clear() {
18  Offset = -1U;
19  std::memset(&Header, 0, sizeof(Header));
20  ArangeDescriptors.clear();
21}
22
23void DWARFDebugArangeSet::compact() {
24  if (ArangeDescriptors.empty())
25    return;
26
27  // Iterate through all arange descriptors and combine any ranges that
28  // overlap or have matching boundaries. The ArangeDescriptors are assumed
29  // to be in ascending order.
30  uint32_t i = 0;
31  while (i + 1 < ArangeDescriptors.size()) {
32    if (ArangeDescriptors[i].getEndAddress() >= ArangeDescriptors[i+1].Address){
33      // The current range ends at or exceeds the start of the next address
34      // range. Compute the max end address between the two and use that to
35      // make the new length.
36      const uint64_t max_end_addr =
37        std::max(ArangeDescriptors[i].getEndAddress(),
38                 ArangeDescriptors[i+1].getEndAddress());
39      ArangeDescriptors[i].Length = max_end_addr - ArangeDescriptors[i].Address;
40      // Now remove the next entry as it was just combined with the previous one
41      ArangeDescriptors.erase(ArangeDescriptors.begin()+i+1);
42    } else {
43      // Discontiguous address range, just proceed to the next one.
44      ++i;
45    }
46  }
47}
48
49bool
50DWARFDebugArangeSet::extract(DataExtractor data, uint32_t *offset_ptr) {
51  if (data.isValidOffset(*offset_ptr)) {
52    ArangeDescriptors.clear();
53    Offset = *offset_ptr;
54
55    // 7.20 Address Range Table
56    //
57    // Each set of entries in the table of address ranges contained in
58    // the .debug_aranges section begins with a header consisting of: a
59    // 4-byte length containing the length of the set of entries for this
60    // compilation unit, not including the length field itself; a 2-byte
61    // version identifier containing the value 2 for DWARF Version 2; a
62    // 4-byte offset into the.debug_infosection; a 1-byte unsigned integer
63    // containing the size in bytes of an address (or the offset portion of
64    // an address for segmented addressing) on the target system; and a
65    // 1-byte unsigned integer containing the size in bytes of a segment
66    // descriptor on the target system. This header is followed by a series
67    // of tuples. Each tuple consists of an address and a length, each in
68    // the size appropriate for an address on the target architecture.
69    Header.Length = data.getU32(offset_ptr);
70    Header.Version = data.getU16(offset_ptr);
71    Header.CuOffset = data.getU32(offset_ptr);
72    Header.AddrSize = data.getU8(offset_ptr);
73    Header.SegSize = data.getU8(offset_ptr);
74
75    // Perform basic validation of the header fields.
76    if (!data.isValidOffsetForDataOfSize(Offset, Header.Length) ||
77        (Header.AddrSize != 4 && Header.AddrSize != 8)) {
78      clear();
79      return false;
80    }
81
82    // The first tuple following the header in each set begins at an offset
83    // that is a multiple of the size of a single tuple (that is, twice the
84    // size of an address). The header is padded, if necessary, to the
85    // appropriate boundary.
86    const uint32_t header_size = *offset_ptr - Offset;
87    const uint32_t tuple_size = Header.AddrSize * 2;
88    uint32_t first_tuple_offset = 0;
89    while (first_tuple_offset < header_size)
90      first_tuple_offset += tuple_size;
91
92    *offset_ptr = Offset + first_tuple_offset;
93
94    Descriptor arangeDescriptor;
95
96    assert(sizeof(arangeDescriptor.Address) == sizeof(arangeDescriptor.Length));
97    assert(sizeof(arangeDescriptor.Address) >= Header.AddrSize);
98
99    while (data.isValidOffset(*offset_ptr)) {
100      arangeDescriptor.Address = data.getUnsigned(offset_ptr, Header.AddrSize);
101      arangeDescriptor.Length = data.getUnsigned(offset_ptr, Header.AddrSize);
102
103      // Each set of tuples is terminated by a 0 for the address and 0
104      // for the length.
105      if (arangeDescriptor.Address || arangeDescriptor.Length)
106        ArangeDescriptors.push_back(arangeDescriptor);
107      else
108        break; // We are done if we get a zero address and length
109    }
110
111    return !ArangeDescriptors.empty();
112  }
113  return false;
114}
115
116void DWARFDebugArangeSet::dump(raw_ostream &OS) const {
117  OS << format("Address Range Header: length = 0x%8.8x, version = 0x%4.4x, ",
118               Header.Length, Header.Version)
119     << format("cu_offset = 0x%8.8x, addr_size = 0x%2.2x, seg_size = 0x%2.2x\n",
120               Header.CuOffset, Header.AddrSize, Header.SegSize);
121
122  const uint32_t hex_width = Header.AddrSize * 2;
123  for (DescriptorConstIter pos = ArangeDescriptors.begin(),
124       end = ArangeDescriptors.end(); pos != end; ++pos)
125    OS << format("[0x%*.*" PRIx64 " -", hex_width, hex_width, pos->Address)
126       << format(" 0x%*.*" PRIx64 ")\n",
127                 hex_width, hex_width, pos->getEndAddress());
128}
129
130
131namespace {
132  class DescriptorContainsAddress {
133    const uint64_t Address;
134  public:
135    DescriptorContainsAddress(uint64_t address) : Address(address) {}
136    bool operator()(const DWARFDebugArangeSet::Descriptor &desc) const {
137      return Address >= desc.Address && Address < (desc.Address + desc.Length);
138    }
139  };
140}
141
142uint32_t DWARFDebugArangeSet::findAddress(uint64_t address) const {
143  DescriptorConstIter end = ArangeDescriptors.end();
144  DescriptorConstIter pos =
145    std::find_if(ArangeDescriptors.begin(), end, // Range
146                 DescriptorContainsAddress(address)); // Predicate
147  if (pos != end)
148    return Header.CuOffset;
149
150  return -1U;
151}
152