Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(235)

Side by Side Diff: experimental/visual_studio_plugin/src/NaClVsx.Package/DebugSupport/DWARF/SymbolDatabase.cs

Issue 10928195: First round of dead file removal (Closed) Base URL: https://github.com/samclegg/nativeclient-sdk.git@master
Patch Set: Created 8 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698