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