1 //===-- DWARFDebugAranges.cpp -----------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "DWARFDebugAranges.h"
11 
12 #include <assert.h>
13 #include <stdio.h>
14 
15 #include <algorithm>
16 
17 #include "lldb/Core/Stream.h"
18 #include "lldb/Core/Timer.h"
19 
20 #include "SymbolFileDWARF.h"
21 #include "DWARFDebugInfo.h"
22 #include "DWARFCompileUnit.h"
23 
24 using namespace lldb_private;
25 
26 //----------------------------------------------------------------------
27 // Constructor
28 //----------------------------------------------------------------------
29 DWARFDebugAranges::DWARFDebugAranges() :
30     m_aranges()
31 {
32 }
33 
34 
35 //----------------------------------------------------------------------
36 // Compare function DWARFDebugAranges::Range structures
37 //----------------------------------------------------------------------
38 static bool RangeLessThan (const DWARFDebugAranges::Range& range1, const DWARFDebugAranges::Range& range2)
39 {
40     return range1.lo_pc < range2.lo_pc;
41 }
42 
43 //----------------------------------------------------------------------
44 // CountArangeDescriptors
45 //----------------------------------------------------------------------
46 class CountArangeDescriptors
47 {
48 public:
49     CountArangeDescriptors (uint32_t& count_ref) : count(count_ref)
50     {
51 //      printf("constructor CountArangeDescriptors()\n");
52     }
53     void operator() (const DWARFDebugArangeSet& set)
54     {
55         count += set.NumDescriptors();
56     }
57     uint32_t& count;
58 };
59 
60 //----------------------------------------------------------------------
61 // AddArangeDescriptors
62 //----------------------------------------------------------------------
63 class AddArangeDescriptors
64 {
65 public:
66     AddArangeDescriptors (DWARFDebugAranges::RangeColl& ranges) : range_collection(ranges) {}
67     void operator() (const DWARFDebugArangeSet& set)
68     {
69         const DWARFDebugArangeSet::Descriptor* arange_desc_ptr;
70         DWARFDebugAranges::Range range;
71         range.offset = set.GetCompileUnitDIEOffset();
72 
73         for (uint32_t i=0; (arange_desc_ptr = set.GetDescriptor(i)) != NULL; ++i)
74         {
75             range.lo_pc = arange_desc_ptr->address;
76             range.hi_pc = arange_desc_ptr->address + arange_desc_ptr->length;
77 
78             // Insert each item in increasing address order so binary searching
79             // can later be done!
80             DWARFDebugAranges::RangeColl::iterator insert_pos = lower_bound(range_collection.begin(), range_collection.end(), range, RangeLessThan);
81             range_collection.insert(insert_pos, range);
82         }
83     }
84     DWARFDebugAranges::RangeColl& range_collection;
85 };
86 
87 //----------------------------------------------------------------------
88 // PrintRange
89 //----------------------------------------------------------------------
90 static void PrintRange(const DWARFDebugAranges::Range& range)
91 {
92     // Cast the address values in case the address type is compiled as 32 bit
93     printf("0x%8.8x: [0x%8.8llx - 0x%8.8llx)\n", range.offset, (long long)range.lo_pc, (long long)range.hi_pc);
94 }
95 
96 //----------------------------------------------------------------------
97 // Extract
98 //----------------------------------------------------------------------
99 bool
100 DWARFDebugAranges::Extract(const DataExtractor &debug_aranges_data)
101 {
102     if (debug_aranges_data.ValidOffset(0))
103     {
104         uint32_t offset = 0;
105 
106         typedef std::vector<DWARFDebugArangeSet>    SetCollection;
107         typedef SetCollection::const_iterator       SetCollectionIter;
108         SetCollection sets;
109 
110         DWARFDebugArangeSet set;
111         Range range;
112         while (set.Extract(debug_aranges_data, &offset))
113             sets.push_back(set);
114 
115         uint32_t count = 0;
116 
117         for_each(sets.begin(), sets.end(), CountArangeDescriptors(count));
118 
119         if (count > 0)
120         {
121             m_aranges.reserve(count);
122             AddArangeDescriptors range_adder(m_aranges);
123             for_each(sets.begin(), sets.end(), range_adder);
124         }
125 
126     //  puts("\n\nDWARFDebugAranges list is:\n");
127     //  for_each(m_aranges.begin(), m_aranges.end(), PrintRange);
128     }
129     return false;
130 }
131 
132 //----------------------------------------------------------------------
133 // Generate
134 //----------------------------------------------------------------------
135 bool
136 DWARFDebugAranges::Generate(SymbolFileDWARF* dwarf2Data)
137 {
138     Clear();
139     DWARFDebugInfo* debug_info = dwarf2Data->DebugInfo();
140     if (debug_info)
141     {
142         uint32_t cu_idx = 0;
143         const uint32_t num_compile_units = dwarf2Data->GetNumCompileUnits();
144         for (cu_idx = 0; cu_idx < num_compile_units; ++cu_idx)
145         {
146             DWARFCompileUnit* cu = debug_info->GetCompileUnitAtIndex(cu_idx);
147             if (cu)
148                 cu->DIE()->BuildAddressRangeTable(dwarf2Data, cu, this);
149         }
150     }
151     return !IsEmpty();
152 }
153 
154 
155 void
156 DWARFDebugAranges::Print() const
157 {
158     puts("\n\nDWARFDebugAranges address range list is:\n");
159     for_each(m_aranges.begin(), m_aranges.end(), PrintRange);
160 }
161 
162 
163 void
164 DWARFDebugAranges::Range::Dump(Stream *s) const
165 {
166     s->Printf("{0x%8.8x}: [0x%8.8llx - 0x%8.8llx)\n", offset, lo_pc, hi_pc);
167 }
168 
169 //----------------------------------------------------------------------
170 // Dump
171 //----------------------------------------------------------------------
172 //void
173 //DWARFDebugAranges::Dump(SymbolFileDWARF* dwarf2Data, Stream *s)
174 //{
175 //    const DataExtractor &debug_aranges_data = dwarf2Data->get_debug_aranges_data();
176 //    if (debug_aranges_data.ValidOffset(0))
177 //    {
178 //        uint32_t offset = 0;
179 //
180 //        DWARFDebugArangeSet set;
181 //        while (set.Extract(debug_aranges_data, &offset))
182 //            set.Dump(s);
183 //    }
184 //    else
185 //        s->PutCString("< EMPTY >\n");
186 //}
187 //
188 
189 //----------------------------------------------------------------------
190 // AppendDebugRanges
191 //----------------------------------------------------------------------
192 //void
193 //DWARFDebugAranges::AppendDebugRanges(BinaryStreamBuf& debug_ranges, dw_addr_t cu_base_addr, uint32_t addr_size) const
194 //{
195 //  if (!m_aranges.empty())
196 //  {
197 //      RangeCollIterator end = m_aranges.end();
198 //      RangeCollIterator pos;
199 //      RangeCollIterator lo_pos = end;
200 //      for (pos = m_aranges.begin(); pos != end; ++pos)
201 //      {
202 //          if (lo_pos == end)
203 //              lo_pos = pos;
204 //
205 //          RangeCollIterator next = pos + 1;
206 //          if (next != end)
207 //          {
208 //              // Check to see if we can combine two consecutive ranges?
209 //              if (pos->hi_pc == next->lo_pc)
210 //                  continue;   // We can combine them!
211 //          }
212 //
213 //          if (cu_base_addr == 0 || cu_base_addr == DW_INVALID_ADDRESS)
214 //          {
215 //              debug_ranges.AppendMax64(lo_pos->lo_pc, addr_size);
216 //              debug_ranges.AppendMax64(pos->hi_pc, addr_size);
217 //          }
218 //          else
219 //          {
220 //              assert(lo_pos->lo_pc >= cu_base_addr);
221 //              assert(pos->hi_pc >= cu_base_addr);
222 //              debug_ranges.AppendMax64(lo_pos->lo_pc - cu_base_addr, addr_size);
223 //              debug_ranges.AppendMax64(pos->hi_pc - cu_base_addr, addr_size);
224 //          }
225 //
226 //          // Reset the low part of the next address range
227 //          lo_pos = end;
228 //      }
229 //  }
230 //  // Terminate the .debug_ranges with two zero addresses
231 //  debug_ranges.AppendMax64(0, addr_size);
232 //  debug_ranges.AppendMax64(0, addr_size);
233 //
234 //}
235 //
236 //----------------------------------------------------------------------
237 // ArangeSetContainsAddress
238 //----------------------------------------------------------------------
239 class ArangeSetContainsAddress
240 {
241 public:
242     ArangeSetContainsAddress (dw_addr_t the_address) : address(the_address), offset(DW_INVALID_OFFSET) {}
243     bool operator() (const DWARFDebugArangeSet& set)
244     {
245         offset = set.FindAddress(address);
246         return (offset != DW_INVALID_OFFSET);
247     }
248     const dw_addr_t address;
249     dw_offset_t offset;
250 };
251 
252 
253 //----------------------------------------------------------------------
254 // InsertRange
255 //----------------------------------------------------------------------
256 void
257 DWARFDebugAranges::InsertRange(dw_offset_t offset, dw_addr_t low_pc, dw_addr_t high_pc)
258 {
259     // Insert each item in increasing address order so binary searching
260     // can later be done!
261     DWARFDebugAranges::Range range(low_pc, high_pc, offset);
262     InsertRange(range);
263 }
264 
265 //----------------------------------------------------------------------
266 // InsertRange
267 //----------------------------------------------------------------------
268 void
269 DWARFDebugAranges::InsertRange(const DWARFDebugAranges::Range& range)
270 {
271     // Insert each item in increasing address order so binary searching
272     // can later be done!
273     RangeColl::iterator insert_pos = lower_bound(m_aranges.begin(), m_aranges.end(), range, RangeLessThan);
274     m_aranges.insert(insert_pos, range);
275 }
276 
277 
278 void
279 DWARFDebugAranges::AppendRange (dw_offset_t offset, dw_addr_t low_pc, dw_addr_t high_pc)
280 {
281     if (!m_aranges.empty())
282     {
283         if (m_aranges.back().offset == offset && m_aranges.back().hi_pc == low_pc)
284         {
285             m_aranges.back().hi_pc = high_pc;
286             return;
287         }
288     }
289     m_aranges.push_back (DWARFDebugAranges::Range(low_pc, high_pc, offset));
290 }
291 
292 void
293 DWARFDebugAranges::Sort()
294 {
295     Timer scoped_timer(__PRETTY_FUNCTION__, "%s this = %p",
296                        __PRETTY_FUNCTION__, this);
297 
298     // Sort our address range entries
299     std::stable_sort (m_aranges.begin(), m_aranges.end(), RangeLessThan);
300 
301     // Merge all neighbouring ranges into a single range and remember the
302     // indices of all ranges merged.
303     const size_t old_size = m_aranges.size();
304     std::vector<size_t> merged;
305     for (size_t merge, cursor = 1; cursor < old_size; ++cursor)
306     {
307         merge = cursor - 1;
308         Range &r1 = m_aranges[merge];
309         Range &r2 = m_aranges[cursor];
310 
311         if (r1.hi_pc == r2.lo_pc && r1.offset == r2.offset)
312         {
313             r2.lo_pc = r1.lo_pc;
314             merged.push_back(merge);
315         }
316     }
317 
318     if (merged.empty())
319         return;
320 
321     // Remove the merged ranges by shifting down all the keepers...
322     const size_t new_size = old_size - merged.size();
323     for (size_t i = 0, src = 0, dst = 0; dst < new_size; ++src, ++dst)
324     {
325         while (src == merged[i]) {
326             ++src;
327             ++i;
328         }
329         if (src == dst)
330             continue;
331         m_aranges[dst] = m_aranges[src];
332     }
333 
334     // ...and drop the extra elements.
335     m_aranges.resize(new_size);
336 }
337 
338 //----------------------------------------------------------------------
339 // FindAddress
340 //----------------------------------------------------------------------
341 dw_offset_t
342 DWARFDebugAranges::FindAddress(dw_addr_t address) const
343 {
344     if ( !m_aranges.empty() )
345     {
346         DWARFDebugAranges::Range range(address);
347         DWARFDebugAranges::RangeCollIterator begin = m_aranges.begin();
348         DWARFDebugAranges::RangeCollIterator end = m_aranges.end();
349         DWARFDebugAranges::RangeCollIterator pos = lower_bound(begin, end, range, RangeLessThan);
350 
351         if ((pos != end) && (pos->lo_pc <= address && address < pos->hi_pc))
352         {
353         //  printf("FindAddress(1) found 0x%8.8x in compile unit: 0x%8.8x\n", address, pos->offset);
354             return pos->offset;
355         }
356         else if (pos != begin)
357         {
358             --pos;
359             if ((pos->lo_pc <= address) && (address < pos->hi_pc))
360             {
361             //  printf("FindAddress(2) found 0x%8.8x in compile unit: 0x%8.8x\n", address, pos->offset);
362                 return (*pos).offset;
363             }
364         }
365     }
366     return DW_INVALID_OFFSET;
367 }
368 
369 //----------------------------------------------------------------------
370 // AllRangesAreContiguous
371 //----------------------------------------------------------------------
372 bool
373 DWARFDebugAranges::AllRangesAreContiguous(dw_addr_t& lo_pc, dw_addr_t& hi_pc) const
374 {
375     if (m_aranges.empty())
376         return false;
377 
378     DWARFDebugAranges::RangeCollIterator begin = m_aranges.begin();
379     DWARFDebugAranges::RangeCollIterator end = m_aranges.end();
380     DWARFDebugAranges::RangeCollIterator pos;
381     dw_addr_t next_addr = 0;
382 
383     for (pos = begin; pos != end; ++pos)
384     {
385         if ((pos != begin) && (pos->lo_pc != next_addr))
386             return false;
387         next_addr = pos->hi_pc;
388     }
389     lo_pc = m_aranges.front().lo_pc;    // We checked for empty at the start of function so front() will be valid
390     hi_pc = m_aranges.back().hi_pc;     // We checked for empty at the start of function so back() will be valid
391     return true;
392 }
393 
394 bool
395 DWARFDebugAranges::GetMaxRange(dw_addr_t& lo_pc, dw_addr_t& hi_pc) const
396 {
397     if (m_aranges.empty())
398         return false;
399 
400     lo_pc = m_aranges.front().lo_pc;    // We checked for empty at the start of function so front() will be valid
401     hi_pc = m_aranges.back().hi_pc;     // We checked for empty at the start of function so back() will be valid
402     return true;
403 }
404 
405