DWARFDebugArangeSet.cpp revision 276479
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 16using namespace lldb_private; 17 18DWARFDebugArangeSet::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 30void 31DWARFDebugArangeSet::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 42void 43DWARFDebugArangeSet::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 57void 58DWARFDebugArangeSet::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//---------------------------------------------------------------------- 90static 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//---------------------------------------------------------------------- 99void 100DWARFDebugArangeSet::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 164bool 165DWARFDebugArangeSet::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 265dw_offset_t 266DWARFDebugArangeSet::GetOffsetOfNextEntry() const 267{ 268 return m_offset + m_header.length + 4; 269} 270 271 272void 273DWARFDebugArangeSet::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 288class DescriptorContainsAddress 289{ 290public: 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 300dw_offset_t 301DWARFDebugArangeSet::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} 311