119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-- DWARFDebugArangeSet.cpp -------------------------------------------===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "DWARFDebugArangeSet.h" 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Format.h" 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <algorithm> 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <cassert> 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid DWARFDebugArangeSet::clear() { 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = -1U; 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::memset(&Header, 0, sizeof(Header)); 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors.clear(); 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid DWARFDebugArangeSet::compact() { 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ArangeDescriptors.empty()) 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Iterate through all arange descriptors and combine any ranges that 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // overlap or have matching boundaries. The ArangeDescriptors are assumed 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to be in ascending order. 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint32_t i = 0; 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (i + 1 < ArangeDescriptors.size()) { 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ArangeDescriptors[i].getEndAddress() >= ArangeDescriptors[i+1].Address){ 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The current range ends at or exceeds the start of the next address 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // range. Compute the max end address between the two and use that to 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // make the new length. 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint64_t max_end_addr = 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::max(ArangeDescriptors[i].getEndAddress(), 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors[i+1].getEndAddress()); 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors[i].Length = max_end_addr - ArangeDescriptors[i].Address; 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now remove the next entry as it was just combined with the previous one 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors.erase(ArangeDescriptors.begin()+i+1); 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Discontiguous address range, just proceed to the next one. 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++i; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDWARFDebugArangeSet::extract(DataExtractor data, uint32_t *offset_ptr) { 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (data.isValidOffset(*offset_ptr)) { 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors.clear(); 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset = *offset_ptr; 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 7.20 Address Range Table 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Each set of entries in the table of address ranges contained in 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the .debug_aranges section begins with a header consisting of: a 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 4-byte length containing the length of the set of entries for this 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // compilation unit, not including the length field itself; a 2-byte 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // version identifier containing the value 2 for DWARF Version 2; a 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 4-byte offset into the.debug_infosection; a 1-byte unsigned integer 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // containing the size in bytes of an address (or the offset portion of 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // an address for segmented addressing) on the target system; and a 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 1-byte unsigned integer containing the size in bytes of a segment 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // descriptor on the target system. This header is followed by a series 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // of tuples. Each tuple consists of an address and a length, each in 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the size appropriate for an address on the target architecture. 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.Length = data.getU32(offset_ptr); 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.Version = data.getU16(offset_ptr); 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.CuOffset = data.getU32(offset_ptr); 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.AddrSize = data.getU8(offset_ptr); 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.SegSize = data.getU8(offset_ptr); 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Perform basic validation of the header fields. 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!data.isValidOffsetForDataOfSize(Offset, Header.Length) || 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (Header.AddrSize != 4 && Header.AddrSize != 8)) { 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman clear(); 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The first tuple following the header in each set begins at an offset 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that is a multiple of the size of a single tuple (that is, twice the 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // size of an address). The header is padded, if necessary, to the 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // appropriate boundary. 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint32_t header_size = *offset_ptr - Offset; 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint32_t tuple_size = Header.AddrSize * 2; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman uint32_t first_tuple_offset = 0; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (first_tuple_offset < header_size) 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman first_tuple_offset += tuple_size; 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman *offset_ptr = Offset + first_tuple_offset; 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Descriptor arangeDescriptor; 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(sizeof(arangeDescriptor.Address) == sizeof(arangeDescriptor.Length)); 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(sizeof(arangeDescriptor.Address) >= Header.AddrSize); 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (data.isValidOffset(*offset_ptr)) { 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman arangeDescriptor.Address = data.getUnsigned(offset_ptr, Header.AddrSize); 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman arangeDescriptor.Length = data.getUnsigned(offset_ptr, Header.AddrSize); 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Each set of tuples is terminated by a 0 for the address and 0 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // for the length. 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (arangeDescriptor.Address || arangeDescriptor.Length) 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArangeDescriptors.push_back(arangeDescriptor); 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; // We are done if we get a zero address and length 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !ArangeDescriptors.empty(); 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid DWARFDebugArangeSet::dump(raw_ostream &OS) const { 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << format("Address Range Header: length = 0x%8.8x, version = 0x%4.4x, ", 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.Length, Header.Version) 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << format("cu_offset = 0x%8.8x, addr_size = 0x%2.2x, seg_size = 0x%2.2x\n", 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Header.CuOffset, Header.AddrSize, Header.SegSize); 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint32_t hex_width = Header.AddrSize * 2; 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (DescriptorConstIter pos = ArangeDescriptors.begin(), 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman end = ArangeDescriptors.end(); pos != end; ++pos) 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << format("[0x%*.*llx -", hex_width, hex_width, pos->Address) 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << format(" 0x%*.*llx)\n", hex_width, hex_width, pos->getEndAddress()); 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class DescriptorContainsAddress { 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const uint64_t Address; 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman public: 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DescriptorContainsAddress(uint64_t address) : Address(address) {} 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator()(const DWARFDebugArangeSet::Descriptor &desc) const { 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Address >= desc.Address && Address < (desc.Address + desc.Length); 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanuint32_t DWARFDebugArangeSet::findAddress(uint64_t address) const { 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DescriptorConstIter end = ArangeDescriptors.end(); 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DescriptorConstIter pos = 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::find_if(ArangeDescriptors.begin(), end, // Range 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DescriptorContainsAddress(address)); // Predicate 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (pos != end) 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Header.CuOffset; 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return -1U; 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 151