DWARFDebugArangeSet.cpp revision 321369
1145519Sdarrenr//===-- DWARFDebugArangeSet.cpp ---------------------------------*- C++ -*-===// 2145510Sdarrenr// 3170268Sdarrenr// The LLVM Compiler Infrastructure 4255332Scy// 5255332Scy// This file is distributed under the University of Illinois Open Source 6255332Scy// License. See LICENSE.TXT for details. 7255332Scy// 8255332Scy//===----------------------------------------------------------------------===// 9255332Scy 10170268Sdarrenr#include "DWARFDebugArangeSet.h" 11145510Sdarrenr 12145510Sdarrenr#include "SymbolFileDWARF.h" 13145510Sdarrenr#include "lldb/Utility/Stream.h" 14145510Sdarrenr#include <assert.h> 15255332Scy 16255332Scyusing namespace lldb_private; 17145510Sdarrenr 18145510SdarrenrDWARFDebugArangeSet::DWARFDebugArangeSet() 19145510Sdarrenr : m_offset(DW_INVALID_OFFSET), m_header(), m_arange_descriptors() { 20145510Sdarrenr m_header.length = 0; 21145510Sdarrenr m_header.version = 0; 22145510Sdarrenr m_header.cu_offset = 0; 23145510Sdarrenr m_header.addr_size = 0; 24145510Sdarrenr m_header.seg_size = 0; 25145510Sdarrenr} 26145510Sdarrenr 27145510Sdarrenrvoid DWARFDebugArangeSet::Clear() { 28145510Sdarrenr m_offset = DW_INVALID_OFFSET; 29145510Sdarrenr m_header.length = 0; 30145510Sdarrenr m_header.version = 0; 31145510Sdarrenr m_header.cu_offset = 0; 32145510Sdarrenr m_header.addr_size = 0; 33145510Sdarrenr m_header.seg_size = 0; 34145510Sdarrenr m_arange_descriptors.clear(); 35145510Sdarrenr} 36145510Sdarrenr 37145510Sdarrenrvoid DWARFDebugArangeSet::SetHeader(uint16_t version, uint32_t cu_offset, 38145510Sdarrenr uint8_t addr_size, uint8_t seg_size) { 39145510Sdarrenr m_header.version = version; 40145510Sdarrenr m_header.cu_offset = cu_offset; 41 m_header.addr_size = addr_size; 42 m_header.seg_size = seg_size; 43} 44 45void 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//---------------------------------------------------------------------- 79static 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//---------------------------------------------------------------------- 88void 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 137bool 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 231dw_offset_t DWARFDebugArangeSet::GetOffsetOfNextEntry() const { 232 return m_offset + m_header.length + 4; 233} 234 235void 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 249class DescriptorContainsAddress { 250public: 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 257private: 258 const dw_addr_t m_address; 259}; 260 261dw_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} 271