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