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