OLD | NEW |
| (Empty) |
1 // Copyright (c) 2011 The Native Client Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #region | |
6 | |
7 using System.Collections.Generic; | |
8 using System.Linq; | |
9 using NaClVsx; | |
10 | |
11 #endregion | |
12 | |
13 namespace Google.NaClVsx.DebugSupport.DWARF { | |
14 public class SymbolDatabase { | |
15 // Tables | |
16 public Dictionary<ulong, DebugInfoAttribute> Attributes { | |
17 get { return attributes_; } | |
18 } | |
19 | |
20 public Dictionary<ulong, CallFrame> CallFrames { | |
21 get { return callFrames_; } | |
22 } | |
23 | |
24 public Dictionary<ulong, DebugInfoEntry> Entries { | |
25 get { return entries_; } | |
26 } | |
27 | |
28 public Dictionary<ulong, SourceFile> Files { | |
29 get { return files_; } | |
30 } | |
31 | |
32 public Dictionary<ulong, SourceLocation> Locations { | |
33 get { return locations_; } | |
34 } | |
35 | |
36 public Dictionary<ulong, List<LocListEntry>> LocLists { | |
37 get { return locLists_; } | |
38 } | |
39 | |
40 /// <summary> | |
41 /// Described from the inside out: | |
42 /// A rangelist is a dictionary mapping lowPC values to the RangeListEntri
es in which they | |
43 /// occur. The "RangeLists" field is another dictionary mapping offsets t
o Rangelists. | |
44 /// </summary> | |
45 public Dictionary<ulong, Dictionary<ulong, RangeListEntry>> RangeLists { | |
46 get { return rangeLists_; } | |
47 } | |
48 | |
49 public Dictionary<ulong, ScopeTransition> ScopeTransitions { | |
50 get { return scopeTransitions_; } | |
51 } | |
52 | |
53 public Dictionary<ulong, List<DebugInfoEntry>> EntriesByParent { | |
54 get { return entriesByParent_; } | |
55 } | |
56 | |
57 public Dictionary<ulong, List<SourceLocation>> LocationsByFile { | |
58 get { return locationsByFile_; } | |
59 } | |
60 | |
61 /// <summary> | |
62 /// For most lookups, range lists have to be matched to a DIE. This mappi
ng exists in order | |
63 /// to make that easier. It is generated by BuildIndices(). | |
64 /// </summary> | |
65 public Dictionary<ulong, Dictionary<ulong, RangeListEntry>> RangeListsByDIE
{ | |
66 get { return rangeListsByDIE_; } | |
67 } | |
68 | |
69 public Dictionary<string, List<SourceFile>> SourceFilesByFilename { | |
70 get { return sourceFilesByFilename_; } | |
71 } | |
72 | |
73 // Query methods | |
74 public SourceLocation GetLocationForAddress(ulong address) { | |
75 return GetRowForAddress(address, locations_, locationAddresses_); | |
76 } | |
77 | |
78 /// <summary> | |
79 /// This function returns a list of code locations that occur in the given | |
80 /// scope, sorted by their line numbers. | |
81 /// </summary> | |
82 /// <param name = "scope"> | |
83 /// The scope for which lines are being required. | |
84 /// </param> | |
85 /// <param name = "address"> | |
86 /// The address within the scope, for which lines are being required. | |
87 /// This is used to disambiguate between range list entries. | |
88 /// </param> | |
89 /// <returns> | |
90 /// A list of source locations. | |
91 /// </returns> | |
92 public IEnumerable<SourceLocation> GetLocationsByLine( | |
93 DebugInfoEntry scope, ulong address) { | |
94 IEnumerable<SourceLocation> locationsByLine = null; | |
95 | |
96 if (scope.HasAttribute(DwarfAttribute.DW_AT_low_pc)) { | |
97 var scopeAddress = scope.GetLowPC(); | |
98 if (scopeToLocationsByLine_.ContainsKey(scopeAddress)) { | |
99 locationsByLine = scopeToLocationsByLine_[scopeAddress]; | |
100 } | |
101 } else if (scope.HasAttribute(DwarfAttribute.DW_AT_ranges)) { | |
102 var range = GetRangeForAddress(address, scope); | |
103 var absoluteRangeAddress = ulong.MaxValue; | |
104 // We need to add either the range's base address or the compilation uni
t's lowPC address. | |
105 if (ulong.MaxValue != range.BaseAddress) { | |
106 absoluteRangeAddress = range.BaseAddress + range.LowPC; | |
107 } else { | |
108 var compilationUnitEntry = | |
109 scope.GetNearestAncestorWithTag(DwarfTag.DW_TAG_compile_unit); | |
110 if (null != compilationUnitEntry && | |
111 compilationUnitEntry.HasAttribute(DwarfAttribute.DW_AT_low_pc)) { | |
112 absoluteRangeAddress = compilationUnitEntry.GetLowPC() + range.LowPC
; | |
113 } | |
114 } | |
115 if (absoluteRangeAddress != ulong.MaxValue) { | |
116 locationsByLine = scopeToLocationsByLine_[absoluteRangeAddress]; | |
117 } | |
118 } | |
119 | |
120 return locationsByLine ?? (new List<SourceLocation>()); | |
121 } | |
122 | |
123 /// <summary> | |
124 /// Returns the rangelist entry that contains the given address, provided
there is one. | |
125 /// Note that this function will always try to return a rangelist entry so
it is up to the | |
126 /// caller to first verify that the address is contained in a rangelist. | |
127 /// </summary> | |
128 /// <param name = "address">An address which is thought to be contained in a
rangelist.</param> | |
129 /// <returns>A RangeListEntry whose LowPC's absolute address is less than |a
ddress|.</returns> | |
130 public RangeListEntry GetRangeForAddress(ulong address, DebugInfoEntry scope
) { | |
131 RangeListEntry range = null; | |
132 if (scope.HasAttribute(DwarfAttribute.DW_AT_ranges)) { | |
133 var rangeListKeys = new List<ulong>(); | |
134 rangeListKeys.AddRange(scope.RangeListsByAddress.Keys); | |
135 rangeListKeys.Sort(); | |
136 range = GetRowForAddress(address, scope.RangeListsByAddress, rangeListKe
ys); | |
137 } | |
138 return range; | |
139 } | |
140 | |
141 /// <summary> | |
142 /// Locates the scope entry which contains a given address and returns the
scope entry | |
143 /// point. | |
144 /// </summary> | |
145 /// <param name = "address">The address for which a scope is needed.</param> | |
146 public ulong GetScopeAddress(ulong address) { | |
147 var row = GetRowForAddress(address, scopeTransitions_, scopeTransitionAddr
esses_); | |
148 return row.Address; | |
149 } | |
150 | |
151 public DebugInfoEntry GetScopeForAddress(ulong address) { | |
152 var row = GetRowForAddress(address, scopeTransitions_, scopeTransitionAddr
esses_); | |
153 return row.Entry; | |
154 } | |
155 | |
156 public CallFrame GetCallFrameForAddress(ulong address) { | |
157 return GetRowForAddress(address, callFrames_, callFrameAddresses_); | |
158 } | |
159 | |
160 public IEnumerable<DebugInfoEntry> GetChildrenForEntry(ulong entryKey) { | |
161 List<DebugInfoEntry> result; | |
162 if (!entriesByParent_.TryGetValue(entryKey, out result)) { | |
163 result = new List<DebugInfoEntry>(); | |
164 } | |
165 return result; | |
166 } | |
167 | |
168 /// <summary> | |
169 /// This function generates all the "secondary" look-up tables that consti
tute the | |
170 /// SymbolDatabase. This is basically a post-processing step for the bina
ry data. The | |
171 /// lookup structures that are generated here are as follows: | |
172 /// - entriesByParent: For finding the children of any given DIE. | |
173 /// - sourceFilesByFilename: For locating source files. | |
174 /// - locationsByFile: For retrieving all of the SourceLocations in any gi
ven file. This | |
175 /// is used for setting breakpoints. | |
176 /// - locationAddresses: The addresses of the SourceLocations, sorted to a
llow quick | |
177 /// inexact lookups at runtime. They are used as keys into locations_. | |
178 /// - scopeTransitionAddresses: The addresses of the scope transitions. U
sed to allow | |
179 /// quick inexact lookups by address into the scopeTransitions table at ru
ntime. | |
180 /// - callFrameAddresses: The addresses of the call frames. Used to allow
quick inexact | |
181 /// lookups by address into the callFrames_ table at runtime. | |
182 /// - scopeToLocationsByLine: A mapping of scope addresses to lists of cod
e locations that | |
183 /// are sorted by line number. This is to quickly find the right line of
code within a | |
184 /// given scope at runtime. | |
185 /// The function also post-processes the RangeLists to add them scope tran
sitions and make | |
186 /// them searchable by the Address of the DIE to which they belong. | |
187 /// </summary> | |
188 public void BuildIndices() { | |
189 BuildIndex(entries_, entriesByParent_, r => r.ParentKey); | |
190 BuildIndex(files_, sourceFilesByFilename_, r => r.Filename); | |
191 BuildIndex(locations_, locationsByFile_, r => r.SourceFileKey); | |
192 | |
193 locationAddresses_.AddRange(locations_.Keys); | |
194 locationAddresses_.Sort(); | |
195 | |
196 scopeTransitionAddresses_.AddRange(scopeTransitions_.Keys); | |
197 scopeTransitionAddresses_.Sort(); | |
198 | |
199 callFrameAddresses_.AddRange(callFrames_.Keys); | |
200 callFrameAddresses_.Sort(); | |
201 | |
202 // This must be called after scopeTransitionAddresses is created. | |
203 BuildRangeListsByDIE(); | |
204 AddRangesToScopeTransitions(); | |
205 | |
206 var scopeToLocations = new Dictionary<ulong, List<SourceLocation>>(); | |
207 foreach (var sourceLocation in locations_) { | |
208 var scopeStart = GetScopeAddress(sourceLocation.Key); | |
209 if (!scopeToLocations.ContainsKey(scopeStart)) { | |
210 scopeToLocations.Add(scopeStart, new List<SourceLocation>()); | |
211 } | |
212 scopeToLocations[scopeStart].Add(sourceLocation.Value); | |
213 } | |
214 | |
215 foreach (var entry in scopeToLocations) { | |
216 if (!scopeToLocationsByLine_.ContainsKey(entry.Key)) { | |
217 scopeToLocationsByLine_.Add(entry.Key, null); | |
218 } | |
219 scopeToLocationsByLine_[entry.Key] = entry.Value.OrderBy(r => r.Line); | |
220 } | |
221 } | |
222 | |
223 #region Private Implementation | |
224 | |
225 private readonly Dictionary<ulong, DebugInfoAttribute> attributes_ = | |
226 new Dictionary<ulong, DebugInfoAttribute>(); | |
227 | |
228 private readonly List<ulong> callFrameAddresses_ = new List<ulong>(); | |
229 | |
230 private readonly Dictionary<ulong, CallFrame> callFrames_ = | |
231 new Dictionary<ulong, CallFrame>(); | |
232 | |
233 // Indices | |
234 private readonly Dictionary<ulong, List<DebugInfoEntry>> entriesByParent_ = | |
235 new Dictionary<ulong, List<DebugInfoEntry>>(); | |
236 | |
237 private readonly Dictionary<ulong, DebugInfoEntry> entries_ = | |
238 new Dictionary<ulong, DebugInfoEntry>(); | |
239 | |
240 private readonly Dictionary<ulong, SourceFile> files_ = | |
241 new Dictionary<ulong, SourceFile>(); | |
242 | |
243 private readonly Dictionary<ulong, List<LocListEntry>> locLists_ = | |
244 new Dictionary<ulong, List<LocListEntry>>(); | |
245 | |
246 private readonly List<ulong> locationAddresses_ = new List<ulong>(); | |
247 | |
248 private readonly Dictionary<ulong, List<SourceLocation>> locationsByFile_ = | |
249 new Dictionary<ulong, List<SourceLocation>>(); | |
250 | |
251 private readonly Dictionary<ulong, SourceLocation> locations_ = | |
252 new Dictionary<ulong, SourceLocation>(); | |
253 | |
254 private readonly Dictionary<ulong, Dictionary<ulong, RangeListEntry>> rangeL
istsByDIE_ = | |
255 new Dictionary<ulong, Dictionary<ulong, RangeListEntry>>(); | |
256 | |
257 private readonly Dictionary<ulong, Dictionary<ulong, RangeListEntry>> rangeL
ists_ = | |
258 new Dictionary<ulong, Dictionary<ulong, RangeListEntry>>(); | |
259 | |
260 private readonly Dictionary<ulong, IEnumerable<SourceLocation>> | |
261 scopeToLocationsByLine_ = | |
262 new Dictionary<ulong, IEnumerable<SourceLocation>>(); | |
263 | |
264 // Sorted address lists | |
265 private readonly List<ulong> scopeTransitionAddresses_ = new List<ulong>(); | |
266 | |
267 private readonly Dictionary<ulong, ScopeTransition> scopeTransitions_ = | |
268 new Dictionary<ulong, ScopeTransition>(); | |
269 | |
270 private readonly Dictionary<string, List<SourceFile>> sourceFilesByFilename_ | |
271 = new Dictionary<string, List<SourceFile>>(); | |
272 | |
273 #endregion | |
274 | |
275 #region Private Implementation | |
276 | |
277 private static void BuildIndex<TRow, TColumn>( | |
278 IEnumerable<KeyValuePair<ulong, TRow>> table, | |
279 IDictionary<TColumn, List<TRow>> index, | |
280 FieldAccessor<TRow, TColumn> accessor) { | |
281 // Clear out the index so we can rebuild it | |
282 index.Clear(); | |
283 | |
284 // Iterate over each row in the table and insert it | |
285 // into the appropriate entry in the index. | |
286 foreach (var pair in table) { | |
287 List<TRow> indexList; | |
288 var columnValue = accessor(pair.Value); | |
289 | |
290 // If the index doesn't yet have a list for this value, | |
291 // add one. | |
292 if (!index.TryGetValue(columnValue, out indexList)) { | |
293 indexList = new List<TRow>(); | |
294 index.Add(columnValue, indexList); | |
295 } | |
296 indexList.Add(pair.Value); | |
297 } | |
298 } | |
299 | |
300 /// <summary> | |
301 /// Retrieves a row in a table for a given address. | |
302 /// TODO(mlinck): This does not recognize when a value is out of bounds. | |
303 /// </summary> | |
304 /// <typeparam name = "T">The type of the lookup table to use.</typeparam> | |
305 /// <param name = "address">The address to use as key.</param> | |
306 /// <param name = "table">The lookup table to use.</param> | |
307 /// <param name = "index">The index to allow for quicker lookup.</param> | |
308 /// <returns>An entry in the table that frames the address or the last | |
309 /// value in the table if the address is out of bounds.</returns> | |
310 private static T GetRowForAddress<T>(ulong address, | |
311 IDictionary<ulong, T> table, | |
312 List<ulong> index) where T : class { | |
313 T result = null; | |
314 | |
315 var pos = index.BinarySearch(address); | |
316 if (pos < 0) { | |
317 // a negative value means there was no exact match. The | |
318 // value is the two's complement of the next largest match | |
319 // (which is not what we want; we want the next smaller match) | |
320 pos = (~pos) - 1; | |
321 } | |
322 if (pos >= 0) { | |
323 var closestAddress = index[pos]; | |
324 result = table[closestAddress]; | |
325 } | |
326 return result; | |
327 } | |
328 | |
329 /// <summary> | |
330 /// This function goes through each DIE that has a RangeList and adds | |
331 /// scope entries for each range in the list. BuildRangeListsByDIE has to | |
332 /// be run in order for this to succeed. | |
333 /// </summary> | |
334 private void AddRangesToScopeTransitions() { | |
335 foreach (var dieToRangeList in RangeListsByDIE) { | |
336 var rangeList = dieToRangeList.Value; | |
337 foreach (var range in rangeList.Values) { | |
338 var scopeAddress = range.LowPC; | |
339 var scopeEndAddress = range.HighPC; | |
340 var die = Entries[dieToRangeList.Key]; | |
341 if (range.BaseAddress != ulong.MaxValue) { | |
342 scopeAddress += range.BaseAddress; | |
343 scopeEndAddress += range.BaseAddress; | |
344 } else { | |
345 var compileUnit = | |
346 die.GetNearestAncestorWithTag(DwarfTag.DW_TAG_compile_unit); | |
347 if (compileUnit != null && | |
348 compileUnit.HasAttribute(DwarfAttribute.DW_AT_low_pc) && | |
349 compileUnit.GetLowPC() != 0) { | |
350 scopeAddress += compileUnit.GetLowPC(); | |
351 scopeEndAddress += compileUnit.GetLowPC(); | |
352 } | |
353 } | |
354 die.AddRangeListEntryByAddress(scopeAddress, range); | |
355 var scopeTransition = new ScopeTransition { | |
356 Address = scopeAddress, | |
357 Entry = die | |
358 }; | |
359 if (ScopeTransitions.ContainsKey(scopeAddress)) { | |
360 // If the DIE that has this Key is a child of this DIE, don't add | |
361 // our own entry. Otherwise, overwrite it since the current DIE | |
362 // is a more specific scope. | |
363 var collidingTransition = ScopeTransitions[scopeAddress]; | |
364 if (die.HasAsAncestor(collidingTransition.Entry.Key)) { | |
365 InsertRangeScopeTransition(scopeTransition, scopeEndAddress, false
); | |
366 } | |
367 } else { | |
368 InsertRangeScopeTransition(scopeTransition, scopeEndAddress, true); | |
369 } | |
370 } | |
371 } | |
372 } | |
373 | |
374 /// <summary> | |
375 /// This mapping is useful because it allows us to skip the step where we | |
376 /// always have to search DIEs for the correct range list offset. | |
377 /// </summary> | |
378 private void BuildRangeListsByDIE() { | |
379 var entriesWithRanges = | |
380 from entry in Entries | |
381 where entry.Value.HasAttribute(DwarfAttribute.DW_AT_ranges) | |
382 select entry.Value; | |
383 foreach (var entry in entriesWithRanges) { | |
384 var rangesKey = entry.GetRangesOffset(); | |
385 var rangeList = RangeLists[rangesKey]; | |
386 RangeListsByDIE.Add(entry.Key, rangeList); | |
387 } | |
388 } | |
389 | |
390 /// <summary> | |
391 /// This function assumes that the decision to add the scope transition | |
392 /// has been finalized. It will only make sure that the transition is | |
393 /// added in the correct order and that, if appropriate, a transition back | |
394 /// to the parent scope is added as well. | |
395 /// </summary> | |
396 private void InsertRangeScopeTransition(ScopeTransition scopeTransition, | |
397 ulong highPC, | |
398 bool isNewEntry) { | |
399 var previousScopeAddress = GetScopeAddress(scopeTransition.Address); | |
400 var nextScopeIndex = | |
401 scopeTransitionAddresses_.IndexOf(previousScopeAddress) + 1; | |
402 var nextScopeAddress = scopeTransitionAddresses_[nextScopeIndex]; | |
403 | |
404 // If the range and its parent entry end on the same address, we need to | |
405 // add a transition back to the parent. | |
406 var needsReturnScope = (nextScopeAddress >= highPC); | |
407 ScopeTransitions[scopeTransition.Address] = scopeTransition; | |
408 if (isNewEntry) { | |
409 // Since we needed this sorted in order to proceed, we keep it sorted | |
410 // to save time. | |
411 scopeTransitionAddresses_.Insert( | |
412 nextScopeIndex++, scopeTransition.Address); | |
413 } | |
414 if (needsReturnScope) { | |
415 var parentDIE = ScopeTransitions[previousScopeAddress].Entry; | |
416 var parentScopeTransition = new ScopeTransition { | |
417 Address = highPC, | |
418 Entry = parentDIE | |
419 }; | |
420 ScopeTransitions[highPC] = parentScopeTransition; | |
421 scopeTransitionAddresses_.Insert( | |
422 nextScopeIndex, parentScopeTransition.Address); | |
423 } | |
424 } | |
425 | |
426 #endregion | |
427 | |
428 #region Private Implementation | |
429 | |
430 private delegate TColumn FieldAccessor<TRow, TColumn>(TRow row); | |
431 | |
432 #endregion | |
433 | |
434 #region Nested type: CallFrame | |
435 | |
436 public class CallFrame { | |
437 public ulong Address; //use as key | |
438 | |
439 public List<Rule> Rules = new List<Rule>(); | |
440 | |
441 #region Nested type: Rule | |
442 | |
443 public class Rule { | |
444 public ulong Address; | |
445 public int RegisterId; | |
446 | |
447 public IDwarfReader.CfiRuleType RuleType; | |
448 public int BaseRegister; | |
449 public int Offset; | |
450 public byte[] Expression; | |
451 } | |
452 | |
453 #endregion | |
454 } | |
455 | |
456 #endregion | |
457 | |
458 #region Nested type: DebugInfoAttribute | |
459 | |
460 public class DebugInfoAttribute { | |
461 // Offset from beginning of dwarf section. | |
462 public ulong Key; | |
463 // Key of the DebugInfoEntry that this attribute helps describe. | |
464 public ulong ParentKey; | |
465 public DwarfAttribute Tag; | |
466 public object Value; | |
467 } | |
468 | |
469 #endregion | |
470 | |
471 #region Nested type: LocListEntry | |
472 | |
473 public class LocListEntry { | |
474 public ulong StartAddress; | |
475 public ulong EndAddress; | |
476 public byte[] Data; | |
477 } | |
478 | |
479 #endregion | |
480 | |
481 #region Nested type: ScopeTransition | |
482 | |
483 public class ScopeTransition { | |
484 public ulong Address; | |
485 public DebugInfoEntry Entry; | |
486 } | |
487 | |
488 #endregion | |
489 | |
490 #region Nested type: SourceFile | |
491 | |
492 public class SourceFile { | |
493 public ulong Key; | |
494 public string Filename; | |
495 public string RelativePath; | |
496 public string CurrentAbsolutePath; | |
497 } | |
498 | |
499 #endregion | |
500 | |
501 #region Nested type: SourceLocation | |
502 | |
503 public class SourceLocation { | |
504 public ulong StartAddress; // Use as key, since it is unique | |
505 public ulong Length; | |
506 | |
507 public ulong SourceFileKey; | |
508 public uint Line; | |
509 public uint Column; | |
510 } | |
511 | |
512 #endregion | |
513 } | |
514 } | |
OLD | NEW |