contrib/llvm/tools/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugArangeSet.cpp

   1 //===-- DWARFDebugArangeSet.cpp ---------------------------------*- C++ -*-===//
   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
  12 #include "SymbolFileDWARF.h"
  13 #include "lldb/Utility/Stream.h"
  14 #include <assert.h>
  15
  16 using namespace lldb_private;
  17
  18 DWARFDebugArangeSet::DWARFDebugArangeSet()
  19     : m_offset(DW_INVALID_OFFSET), m_header(), m_arange_descriptors() {
  20   m_header.length = 0;
  21   m_header.version = 0;
  22   m_header.cu_offset = 0;
  23   m_header.addr_size = 0;
  24   m_header.seg_size = 0;
  25 }
  26
  27 void DWARFDebugArangeSet::Clear() {
  28   m_offset = DW_INVALID_OFFSET;
  29   m_header.length = 0;
  30   m_header.version = 0;
  31   m_header.cu_offset = 0;
  32   m_header.addr_size = 0;
  33   m_header.seg_size = 0;
  34   m_arange_descriptors.clear();
  35 }
  36
  37 void DWARFDebugArangeSet::SetHeader(uint16_t version, uint32_t cu_offset,
  38                                     uint8_t addr_size, uint8_t seg_size) {
  39   m_header.version = version;
  40   m_header.cu_offset = cu_offset;
  41   m_header.addr_size = addr_size;
  42   m_header.seg_size = seg_size;
  43 }
  44
  45 void DWARFDebugArangeSet::Compact() {
  46   if (m_arange_descriptors.empty())
  47     return;
  48
  49   // Iterate through all arange descriptors and combine any ranges that
  50   // overlap or have matching boundaries. The m_arange_descriptors are assumed
  51   // to be in ascending order after being built by adding descriptors
  52   // using the AddDescriptor method.
  53   uint32_t i = 0;
  54   while (i + 1 < m_arange_descriptors.size()) {
  55     if (m_arange_descriptors[i].end_address() >=
  56         m_arange_descriptors[i + 1].address) {
  57       // The current range ends at or exceeds the start of the next address
  58       // range.
  59       // Compute the max end address between the two and use that to make the
  60       // new
  61       // length.
  62       const dw_addr_t max_end_addr =
  63           std::max(m_arange_descriptors[i].end_address(),
  64                    m_arange_descriptors[i + 1].end_address());
  65       m_arange_descriptors[i].length =
  66           max_end_addr - m_arange_descriptors[i].address;
  67       // Now remove the next entry as it was just combined with the previous
  68       // one.
  69       m_arange_descriptors.erase(m_arange_descriptors.begin() + i + 1);
  70     } else {
  71       // Discontiguous address range, just proceed to the next one.
  72       ++i;
  73     }
  74   }
  75 }
  76 //----------------------------------------------------------------------
  77 // Compare function DWARFDebugArangeSet::Descriptor structures
  78 //----------------------------------------------------------------------
  79 static bool DescriptorLessThan(const DWARFDebugArangeSet::Descriptor &range1,
  80                                const DWARFDebugArangeSet::Descriptor &range2) {
  81   return range1.address < range2.address;
  82 }
  83
  84 //----------------------------------------------------------------------
  85 // Add a range descriptor and keep things sorted so we can easily
  86 // compact the ranges before being saved or used.
  87 //----------------------------------------------------------------------
  88 void DWARFDebugArangeSet::AddDescriptor(
  89     const DWARFDebugArangeSet::Descriptor &range) {
  90   if (m_arange_descriptors.empty()) {
  91     m_arange_descriptors.push_back(range);
  92     return;
  93   }
  94
  95   DescriptorIter end = m_arange_descriptors.end();
  96   DescriptorIter pos =
  97       lower_bound(m_arange_descriptors.begin(), end, range, DescriptorLessThan);
  98   const dw_addr_t range_end_addr = range.end_address();
  99   if (pos != end) {
 100     const dw_addr_t found_end_addr = pos->end_address();
 101     if (range.address < pos->address) {
 102       if (range_end_addr < pos->address) {
 103         // Non-contiguous entries, add this one before the found entry
 104         m_arange_descriptors.insert(pos, range);
 105       } else if (range_end_addr == pos->address) {
 106         // The top end of 'range' is the lower end of the entry
 107         // pointed to by 'pos'. We can combine range with the
 108         // entry we found by setting the starting address and
 109         // increasing the length since they don't overlap.
 110         pos->address = range.address;
 111         pos->length += range.length;
 112       } else {
 113         // We can combine these two and make sure the largest end
 114         // address is used to make end address.
 115         pos->address = range.address;
 116         pos->length = std::max(found_end_addr, range_end_addr) - pos->address;
 117       }
 118     } else if (range.address == pos->address) {
 119       pos->length = std::max(pos->length, range.length);
 120     }
 121   } else {
 122     // NOTE: 'pos' points to entry past the end which is ok for insert,
 123     // don't use otherwise!!!
 124     const dw_addr_t max_addr = m_arange_descriptors.back().end_address();
 125     if (max_addr < range.address) {
 126       // Non-contiguous entries, add this one before the found entry
 127       m_arange_descriptors.insert(pos, range);
 128     } else if (max_addr == range.address) {
 129       m_arange_descriptors.back().length += range.length;
 130     } else {
 131       m_arange_descriptors.back().length = std::max(max_addr, range_end_addr) -
 132                                            m_arange_descriptors.back().address;
 133     }
 134   }
 135 }
 136
 137 bool DWARFDebugArangeSet::Extract(const DWARFDataExtractor &data,
 138                                   lldb::offset_t *offset_ptr) {
 139   if (data.ValidOffset(*offset_ptr)) {
 140     m_arange_descriptors.clear();
 141     m_offset = *offset_ptr;
 142
 143     // 7.20 Address Range Table
 144     //
 145     // Each set of entries in the table of address ranges contained in
 146     // the .debug_aranges section begins with a header consisting of: a
 147     // 4-byte length containing the length of the set of entries for this
 148     // compilation unit, not including the length field itself; a 2-byte
 149     // version identifier containing the value 2 for DWARF Version 2; a
 150     // 4-byte offset into the.debug_infosection; a 1-byte unsigned integer
 151     // containing the size in bytes of an address (or the offset portion of
 152     // an address for segmented addressing) on the target system; and a
 153     // 1-byte unsigned integer containing the size in bytes of a segment
 154     // descriptor on the target system. This header is followed by a series
 155     // of tuples. Each tuple consists of an address and a length, each in
 156     // the size appropriate for an address on the target architecture.
 157     m_header.length = data.GetDWARFInitialLength(offset_ptr);
 158     m_header.version = data.GetU16(offset_ptr);
 159     m_header.cu_offset = data.GetDWARFOffset(offset_ptr);
 160     m_header.addr_size = data.GetU8(offset_ptr);
 161     m_header.seg_size = data.GetU8(offset_ptr);
 162
 163     // Try to avoid reading invalid arange sets by making sure:
 164     // 1 - the version looks good
 165     // 2 - the address byte size looks plausible
 166     // 3 - the length seems to make sense
 167     // size looks plausible
 168     if ((m_header.version >= 2 && m_header.version <= 5) &&
 169         (m_header.addr_size == 4 || m_header.addr_size == 8) &&
 170         (m_header.length > 0)) {
 171       if (data.ValidOffset(m_offset + sizeof(m_header.length) +
 172                            m_header.length - 1)) {
 173         // The first tuple following the header in each set begins at an offset
 174         // that is a multiple of the size of a single tuple (that is, twice the
 175         // size of an address). The header is padded, if necessary, to the
 176         // appropriate boundary.
 177         const uint32_t header_size = *offset_ptr - m_offset;
 178         const uint32_t tuple_size = m_header.addr_size << 1;
 179         uint32_t first_tuple_offset = 0;
 180         while (first_tuple_offset < header_size)
 181           first_tuple_offset += tuple_size;
 182
 183         *offset_ptr = m_offset + first_tuple_offset;
 184
 185         Descriptor arangeDescriptor;
 186
 187         static_assert(
 188             sizeof(arangeDescriptor.address) == sizeof(arangeDescriptor.length),
 189             "DWARFDebugArangeSet::Descriptor.address and "
 190             "DWARFDebugArangeSet::Descriptor.length must have same size");
 191
 192         while (data.ValidOffset(*offset_ptr)) {
 193           arangeDescriptor.address =
 194               data.GetMaxU64(offset_ptr, m_header.addr_size);
 195           arangeDescriptor.length =
 196               data.GetMaxU64(offset_ptr, m_header.addr_size);
 197
 198           // Each set of tuples is terminated by a 0 for the address and 0
 199           // for the length.
 200           if (arangeDescriptor.address || arangeDescriptor.length)
 201             m_arange_descriptors.push_back(arangeDescriptor);
 202           else
 203             break; // We are done if we get a zero address and length
 204         }
 205       }
 206 #if defined(LLDB_CONFIGURATION_DEBUG)
 207       else {
 208         printf("warning: .debug_arange set length is too large arange data at "
 209                "0x%8.8x: length=0x%8.8x, version=0x%4.4x, cu_offset=0x%8.8x, "
 210                "addr_size=%u, seg_size=%u\n",
 211                m_offset, m_header.length, m_header.version, m_header.cu_offset,
 212                m_header.addr_size, m_header.seg_size);
 213       }
 214 #endif
 215     }
 216 #if defined(LLDB_CONFIGURATION_DEBUG)
 217     else {
 218       printf("warning: .debug_arange set has bad header at 0x%8.8x: "
 219              "length=0x%8.8x, version=0x%4.4x, cu_offset=0x%8.8x, "
 220              "addr_size=%u, seg_size=%u\n",
 221              m_offset, m_header.length, m_header.version, m_header.cu_offset,
 222              m_header.addr_size, m_header.seg_size);
 223     }
 224 #endif
 225
 226     return !m_arange_descriptors.empty();
 227   }
 228   return false;
 229 }
 230
 231 dw_offset_t DWARFDebugArangeSet::GetOffsetOfNextEntry() const {
 232   return m_offset + m_header.length + 4;
 233 }
 234
 235 void DWARFDebugArangeSet::Dump(Stream *s) const {
 236   s->Printf("Address Range Header: length = 0x%8.8x, version = 0x%4.4x, "
 237             "cu_offset = 0x%8.8x, addr_size = 0x%2.2x, seg_size = 0x%2.2x\n",
 238             m_header.length, m_header.version, m_header.cu_offset,
 239             m_header.addr_size, m_header.seg_size);
 240
 241   const uint32_t hex_width = m_header.addr_size * 2;
 242   DescriptorConstIter pos;
 243   DescriptorConstIter end = m_arange_descriptors.end();
 244   for (pos = m_arange_descriptors.begin(); pos != end; ++pos)
 245     s->Printf("[0x%*.*" PRIx64 " - 0x%*.*" PRIx64 ")\n", hex_width, hex_width,
 246               pos->address, hex_width, hex_width, pos->end_address());
 247 }
 248
 249 class DescriptorContainsAddress {
 250 public:
 251   DescriptorContainsAddress(dw_addr_t address) : m_address(address) {}
 252   bool operator()(const DWARFDebugArangeSet::Descriptor &desc) const {
 253     return (m_address >= desc.address) &&
 254            (m_address < (desc.address + desc.length));
 255   }
 256
 257 private:
 258   const dw_addr_t m_address;
 259 };
 260
 261 dw_offset_t DWARFDebugArangeSet::FindAddress(dw_addr_t address) const {
 262   DescriptorConstIter end = m_arange_descriptors.end();
 263   DescriptorConstIter pos =
 264       std::find_if(m_arange_descriptors.begin(), end,   // Range
 265                    DescriptorContainsAddress(address)); // Predicate
 266   if (pos != end)
 267     return m_header.cu_offset;
 268
 269   return DW_INVALID_OFFSET;
 270 }