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