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