1254721Semaste//===-- DWARFDebugArangeSet.cpp ---------------------------------*- C++ -*-===// 2254721Semaste// 3254721Semaste// The LLVM Compiler Infrastructure 4254721Semaste// 5254721Semaste// This file is distributed under the University of Illinois Open Source 6254721Semaste// License. See LICENSE.TXT for details. 7254721Semaste// 8254721Semaste//===----------------------------------------------------------------------===// 9254721Semaste 10254721Semaste#include "DWARFDebugArangeSet.h" 11254721Semaste 12254721Semaste#include <assert.h> 13254721Semaste#include "lldb/Core/Stream.h" 14254721Semaste#include "SymbolFileDWARF.h" 15254721Semaste 16254721Semasteusing namespace lldb_private; 17254721Semaste 18254721SemasteDWARFDebugArangeSet::DWARFDebugArangeSet() : 19254721Semaste m_offset(DW_INVALID_OFFSET), 20254721Semaste m_header(), 21254721Semaste m_arange_descriptors() 22254721Semaste{ 23254721Semaste m_header.length = 0; 24254721Semaste m_header.version = 0; 25254721Semaste m_header.cu_offset = 0; 26254721Semaste m_header.addr_size = 0; 27254721Semaste m_header.seg_size = 0; 28254721Semaste} 29254721Semaste 30254721Semastevoid 31254721SemasteDWARFDebugArangeSet::Clear() 32254721Semaste{ 33254721Semaste m_offset = DW_INVALID_OFFSET; 34254721Semaste m_header.length = 0; 35254721Semaste m_header.version = 0; 36254721Semaste m_header.cu_offset = 0; 37254721Semaste m_header.addr_size = 0; 38254721Semaste m_header.seg_size = 0; 39254721Semaste m_arange_descriptors.clear(); 40254721Semaste} 41254721Semaste 42254721Semastevoid 43254721SemasteDWARFDebugArangeSet::SetHeader 44254721Semaste( 45254721Semaste uint16_t version, 46254721Semaste uint32_t cu_offset, 47254721Semaste uint8_t addr_size, 48254721Semaste uint8_t seg_size 49254721Semaste) 50254721Semaste{ 51254721Semaste m_header.version = version; 52254721Semaste m_header.cu_offset = cu_offset; 53254721Semaste m_header.addr_size = addr_size; 54254721Semaste m_header.seg_size = seg_size; 55254721Semaste} 56254721Semaste 57254721Semastevoid 58254721SemasteDWARFDebugArangeSet::Compact() 59254721Semaste{ 60254721Semaste if (m_arange_descriptors.empty()) 61254721Semaste return; 62254721Semaste 63254721Semaste // Iterate through all arange descriptors and combine any ranges that 64254721Semaste // overlap or have matching boundaries. The m_arange_descriptors are assumed 65254721Semaste // to be in ascending order after being built by adding descriptors 66254721Semaste // using the AddDescriptor method. 67254721Semaste uint32_t i = 0; 68254721Semaste while (i + 1 < m_arange_descriptors.size()) 69254721Semaste { 70254721Semaste if (m_arange_descriptors[i].end_address() >= m_arange_descriptors[i+1].address) 71254721Semaste { 72254721Semaste // The current range ends at or exceeds the start of the next address range. 73254721Semaste // Compute the max end address between the two and use that to make the new 74254721Semaste // length. 75254721Semaste const dw_addr_t max_end_addr = std::max(m_arange_descriptors[i].end_address(), m_arange_descriptors[i+1].end_address()); 76254721Semaste m_arange_descriptors[i].length = max_end_addr - m_arange_descriptors[i].address; 77254721Semaste // Now remove the next entry as it was just combined with the previous one. 78254721Semaste m_arange_descriptors.erase(m_arange_descriptors.begin()+i+1); 79254721Semaste } 80254721Semaste else 81254721Semaste { 82254721Semaste // Discontiguous address range, just proceed to the next one. 83254721Semaste ++i; 84254721Semaste } 85254721Semaste } 86254721Semaste} 87254721Semaste//---------------------------------------------------------------------- 88254721Semaste// Compare function DWARFDebugArangeSet::Descriptor structures 89254721Semaste//---------------------------------------------------------------------- 90254721Semastestatic bool DescriptorLessThan (const DWARFDebugArangeSet::Descriptor& range1, const DWARFDebugArangeSet::Descriptor& range2) 91254721Semaste{ 92254721Semaste return range1.address < range2.address; 93254721Semaste} 94254721Semaste 95254721Semaste//---------------------------------------------------------------------- 96254721Semaste// Add a range descriptor and keep things sorted so we can easily 97254721Semaste// compact the ranges before being saved or used. 98254721Semaste//---------------------------------------------------------------------- 99254721Semastevoid 100254721SemasteDWARFDebugArangeSet::AddDescriptor(const DWARFDebugArangeSet::Descriptor& range) 101254721Semaste{ 102254721Semaste if (m_arange_descriptors.empty()) 103254721Semaste { 104254721Semaste m_arange_descriptors.push_back(range); 105254721Semaste return; 106254721Semaste } 107254721Semaste 108254721Semaste DescriptorIter end = m_arange_descriptors.end(); 109254721Semaste DescriptorIter pos = lower_bound(m_arange_descriptors.begin(), end, range, DescriptorLessThan); 110254721Semaste const dw_addr_t range_end_addr = range.end_address(); 111254721Semaste if (pos != end) 112254721Semaste { 113254721Semaste const dw_addr_t found_end_addr = pos->end_address(); 114254721Semaste if (range.address < pos->address) 115254721Semaste { 116254721Semaste if (range_end_addr < pos->address) 117254721Semaste { 118254721Semaste // Non-contiguous entries, add this one before the found entry 119254721Semaste m_arange_descriptors.insert(pos, range); 120254721Semaste } 121254721Semaste else if (range_end_addr == pos->address) 122254721Semaste { 123254721Semaste // The top end of 'range' is the lower end of the entry 124254721Semaste // pointed to by 'pos'. We can combine range with the 125254721Semaste // entry we found by setting the starting address and 126254721Semaste // increasing the length since they don't overlap. 127254721Semaste pos->address = range.address; 128254721Semaste pos->length += range.length; 129254721Semaste } 130254721Semaste else 131254721Semaste { 132254721Semaste // We can combine these two and make sure the largest end 133254721Semaste // address is used to make end address. 134254721Semaste pos->address = range.address; 135254721Semaste pos->length = std::max(found_end_addr, range_end_addr) - pos->address; 136254721Semaste } 137254721Semaste } 138254721Semaste else if (range.address == pos->address) 139254721Semaste { 140254721Semaste pos->length = std::max(pos->length, range.length); 141254721Semaste } 142254721Semaste } 143254721Semaste else 144254721Semaste { 145254721Semaste // NOTE: 'pos' points to entry past the end which is ok for insert, 146254721Semaste // don't use otherwise!!! 147254721Semaste const dw_addr_t max_addr = m_arange_descriptors.back().end_address(); 148254721Semaste if (max_addr < range.address) 149254721Semaste { 150254721Semaste // Non-contiguous entries, add this one before the found entry 151254721Semaste m_arange_descriptors.insert(pos, range); 152254721Semaste } 153254721Semaste else if (max_addr == range.address) 154254721Semaste { 155254721Semaste m_arange_descriptors.back().length += range.length; 156254721Semaste } 157254721Semaste else 158254721Semaste { 159254721Semaste m_arange_descriptors.back().length = std::max(max_addr, range_end_addr) - m_arange_descriptors.back().address; 160254721Semaste } 161254721Semaste } 162254721Semaste} 163254721Semaste 164254721Semastebool 165263363SemasteDWARFDebugArangeSet::Extract(const DWARFDataExtractor &data, lldb::offset_t *offset_ptr) 166254721Semaste{ 167254721Semaste if (data.ValidOffset(*offset_ptr)) 168254721Semaste { 169254721Semaste m_arange_descriptors.clear(); 170254721Semaste m_offset = *offset_ptr; 171254721Semaste 172254721Semaste // 7.20 Address Range Table 173254721Semaste // 174254721Semaste // Each set of entries in the table of address ranges contained in 175254721Semaste // the .debug_aranges section begins with a header consisting of: a 176254721Semaste // 4-byte length containing the length of the set of entries for this 177254721Semaste // compilation unit, not including the length field itself; a 2-byte 178254721Semaste // version identifier containing the value 2 for DWARF Version 2; a 179254721Semaste // 4-byte offset into the.debug_infosection; a 1-byte unsigned integer 180254721Semaste // containing the size in bytes of an address (or the offset portion of 181254721Semaste // an address for segmented addressing) on the target system; and a 182254721Semaste // 1-byte unsigned integer containing the size in bytes of a segment 183254721Semaste // descriptor on the target system. This header is followed by a series 184254721Semaste // of tuples. Each tuple consists of an address and a length, each in 185254721Semaste // the size appropriate for an address on the target architecture. 186263363Semaste m_header.length = data.GetDWARFInitialLength(offset_ptr); 187254721Semaste m_header.version = data.GetU16(offset_ptr); 188263363Semaste m_header.cu_offset = data.GetDWARFOffset(offset_ptr); 189254721Semaste m_header.addr_size = data.GetU8(offset_ptr); 190254721Semaste m_header.seg_size = data.GetU8(offset_ptr); 191254721Semaste 192254721Semaste 193254721Semaste // The first tuple following the header in each set begins at an offset 194254721Semaste // that is a multiple of the size of a single tuple (that is, twice the 195254721Semaste // size of an address). The header is padded, if necessary, to the 196254721Semaste // appropriate boundary. 197254721Semaste const uint32_t header_size = *offset_ptr - m_offset; 198254721Semaste const uint32_t tuple_size = m_header.addr_size << 1; 199254721Semaste uint32_t first_tuple_offset = 0; 200254721Semaste while (first_tuple_offset < header_size) 201254721Semaste first_tuple_offset += tuple_size; 202254721Semaste 203254721Semaste *offset_ptr = m_offset + first_tuple_offset; 204254721Semaste 205254721Semaste Descriptor arangeDescriptor; 206254721Semaste 207254721Semaste assert(sizeof(arangeDescriptor.address) == sizeof(arangeDescriptor.length)); 208254721Semaste assert(sizeof(arangeDescriptor.address) >= m_header.addr_size); 209254721Semaste 210254721Semaste while (data.ValidOffset(*offset_ptr)) 211254721Semaste { 212254721Semaste arangeDescriptor.address = data.GetMaxU64(offset_ptr, m_header.addr_size); 213254721Semaste arangeDescriptor.length = data.GetMaxU64(offset_ptr, m_header.addr_size); 214254721Semaste 215254721Semaste // Each set of tuples is terminated by a 0 for the address and 0 216254721Semaste // for the length. 217254721Semaste if (arangeDescriptor.address || arangeDescriptor.length) 218254721Semaste m_arange_descriptors.push_back(arangeDescriptor); 219254721Semaste else 220254721Semaste break; // We are done if we get a zero address and length 221254721Semaste } 222254721Semaste 223254721Semaste return !m_arange_descriptors.empty(); 224254721Semaste } 225254721Semaste return false; 226254721Semaste} 227254721Semaste 228254721Semaste 229254721Semastedw_offset_t 230254721SemasteDWARFDebugArangeSet::GetOffsetOfNextEntry() const 231254721Semaste{ 232254721Semaste return m_offset + m_header.length + 4; 233254721Semaste} 234254721Semaste 235254721Semaste 236254721Semastevoid 237254721SemasteDWARFDebugArangeSet::Dump(Stream *s) const 238254721Semaste{ 239254721Semaste 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", 240254721Semaste m_header.length ,m_header.version, m_header.cu_offset, m_header.addr_size, m_header.seg_size); 241254721Semaste 242254721Semaste const uint32_t hex_width = m_header.addr_size * 2; 243254721Semaste DescriptorConstIter pos; 244254721Semaste DescriptorConstIter end = m_arange_descriptors.end(); 245254721Semaste for (pos = m_arange_descriptors.begin(); pos != end; ++pos) 246254721Semaste s->Printf("[0x%*.*" PRIx64 " - 0x%*.*" PRIx64 ")\n", 247254721Semaste hex_width, hex_width, pos->address, 248254721Semaste hex_width, hex_width, pos->end_address()); 249254721Semaste} 250254721Semaste 251254721Semaste 252254721Semasteclass DescriptorContainsAddress 253254721Semaste{ 254254721Semastepublic: 255254721Semaste DescriptorContainsAddress (dw_addr_t address) : m_address(address) {} 256254721Semaste bool operator() (const DWARFDebugArangeSet::Descriptor& desc) const 257254721Semaste { 258254721Semaste return (m_address >= desc.address) && (m_address < (desc.address + desc.length)); 259254721Semaste } 260254721Semaste private: 261254721Semaste const dw_addr_t m_address; 262254721Semaste}; 263254721Semaste 264254721Semastedw_offset_t 265254721SemasteDWARFDebugArangeSet::FindAddress(dw_addr_t address) const 266254721Semaste{ 267254721Semaste DescriptorConstIter end = m_arange_descriptors.end(); 268254721Semaste DescriptorConstIter pos = std::find_if( m_arange_descriptors.begin(), end, // Range 269254721Semaste DescriptorContainsAddress(address));// Predicate 270254721Semaste if (pos != end) 271254721Semaste return m_header.cu_offset; 272254721Semaste 273254721Semaste return DW_INVALID_OFFSET; 274254721Semaste} 275