I trust Pavel to review this since it is in the Linux native plugins mostly.

Looks like a good starting point. Thanks for the changes.

Zach made some comments via e-mail:

The other option for fixing the problem with showing the wrong variables in the backtraces would be to make up a new frame-format string that is used for uniqued stack frames and use that format when showing uniqued stack frames:

Clicked submit too early with last comments. After seeing how we previously needed to create a temp UniqueStack just to do the lookup, and also how UniqueStack make its thread index ID list mutable, a better solution is to use a std::map as shown in the inlined comments.

Much cleaner. After seeing how we must construct a UniqueStack just so we can search for it, an even cleaner solution would be to make unique_stacks into:

We should probably store the stacks as lldb::addr_t values that are load addresses for quicker comparisons and searches. Inlined code details things more clearly.

No need for the "StructuredDataType::" or "lldb::StructuredDataType::" prefixes. Since we aren't using an enum class (it was before) and since all enumerators start with "eStructuredDataType", it is now clear where this enum comes from without prefixing with the enum type name and/or namespace. I know you were replicating what was there before. There are two ways to fix this:
1 - define the lldb::StructuredDataType and "enum class StructuredDataType" and then shorten the names by removing eStructuredDataType from each enumerator
2 - leave lldb::StructuredDataType defined as enum StructuredDataType" and leave the names long and they can be used on their own.

If all R"( strings are under 80 characters, this is good to go. If not, just fix and submit, no extra review needed.

Looks like we are down to just running clang format on the code so the R"( strings don't go over 80 chars and this is good to go from me.

Very close and overall very nice, just a few implementation details to take care of.

Add a test and fix the minor things as suggested and this will be good to go.

I believe this patch is close enough for an initial checkin. We can iterate on it once it is in? We seem to be down to how to best iterate over ranges in ranges for intersect and for contains. Let me know your thoughts. Or feel free to commandeer this and check it in as you want it...

Close, some minor fixes.

Very nice.

Just a few makefile changes where CFLAGS is being modified and this will be good to go. Much better location for this. Sean, please keep an eye out for this kind of thing in the future, I believe there is a lot of type searching code and function searching code that could have the same thing done in the future.

Sorry I hadn't posted my reply comments, just did that. Will look at your new comments and answer as needed.

• Added an assert to catch if we don't remove overlapping or invalid ranges that catches the issue where the lambda was returning false instead of true and modified DieRangeInfo::insert() to assert as mentioned.
• fixed ::contains and ::intersects to use a more efficient traversal.
• fixed all other issues

• Address all of David's previous issues

• Created a struct named DWARFRange and test it
• Move all contains and intersects logic into DWARFRange and DieRangeInfo
• Create a new DWARFVerify::DIEInfo that contains a DieRangeInfo and a NonOverlappingRanges.
• Simplify verifyDIE as requested to do everything in one place
• Modified DieRangeInfo::contains and DieRangeInfo::intersects to be faster
• Added tests for DieRangeInfo::contains and DieRangeInfo::intersects
• Removed the SortedRanges class and moved it into DieRangeInfo

Yeah, we need to document exactly what this is doing: looking for the best symbol as an expression parser would want it, preferring symbols from the current module in the SymbolContext, and then looking everywhere. Errors if multiple exist in current module, or in any other modules if not in current, bla bla.

The searching code is indeed better and what we now want, but I question of this code should live in ClangExpressionDeclMap::FindGlobalDataSymbol. A better home for this might be in SymbolContext::FindGlobalDataSymbol? Then others can use this functionality. Other clients must want this kind of functionality (other expression parsers). Seems a shame to have it live somewhere where someone would have to copy the code. Thoughts anyone?

ping

So my question is: if we go the jTrace packet route, I would like to not use GDB remote key/value pairs, and just go full JSON. You can make a new JSON dict and pass all of the GDB remote key/value pairs inside and then you can add a "jparams" key whose value is the JSON from the SB layer. JSON packets start with lower case j, not sure why some were upper cased?

Bonus point for implementing a global symbol search that is aware of the above rules and can stop after step 1 if there are matches, and after step 2 if there are matches, etc.

In D33083#751836, @jingham wrote:

Actually, I take that back. Why do you have to call FindGlobalDataSymbol twice? Shouldn't FindGlobalDataSymbol do that work for you. After all you passed in the module. It should itself prefer symbols in the module...

It also seems wrong that we're just picking the first one in the case where we find two symbols at the same level distant from the current module. Shouldn't that be an error?

There is a SymbolContext function sorts types based on the context contained in a SymbolContext. Seems like we should do the same thing here? See SymbolContext::SortTypeList().

Very nice

In D33035#751264, @krytarowski wrote:

Can we please use the generic process plugin code, not the specific Linux one? If the generic code is insufficient - we should adjust it and alter instances of it (Linux and BSD).

So we don't want clients of SBStructuredData to have to text scrape and write manual decoders. See my inlined comments on the minimal modifications we need to make to SBStructureData first. This then removes a ton of code from your patch. The SBStructureData modifications should probably be done in separate patch as well. internally lldb_private::StructuredData has everything (dicts, array, strings, integers, bools, nulls) inherit from lldb_private::StructuredData::Object. Then SBStructuredData owns a StructuredDataImpl which has a lldb_private::StructuredData::Object shared pointer, so a lldb::SBStructureData can be any object (dicts, array, strings, integers, bools, nulls). So we should expose the ability to get data from SBStructuredData. See my inlined SBStructureData additions I proposed. We really don't want anyone doing manual JSON text scraping.

Remove unused DWARFVerifier::verifyNoRangesOverlap() function.

Fixed the core issues David was asking for. Main differences are:

• Now have SortedRanges class that guarantees ranges are sorted instead of relying on DWARFAddressRangesVector being sorted
• SortedRanges can report if there are invalid ranges in a DWARFAddressRangesVector and if there are overlaps during insert
• DieRangeInfo now uses SortedRanges instead of DWARFAddressRangesVector
• DieRangeInfo now reports errors which really cleans up the DWARFVerifier::verifyDie() function
• NonOverlappingRanges now can report errors when DIEs have overlapping address ranges which really cleans up the DWARFVerifier::verifyDie() function

So now we have DIERangeInfo:

struct DieRangeInfo {
  DWARFDie Die;
  DWARFAddressRangesVector Ranges;
};

• Made a new NonOverlappingRanges class.
• Use it to verify address ranges on the fly for
  • functions within all CUs
  • lexical block and inlined functions in DW_TAG_subprogram DIEs

Moved ranges comparisons over into header file so we can unit test. The unit tests will help in case we make AnyDWARFRangesIntersect or DWARFRangesContains changes that assume sorted lists and try to do things more efficiently.

I would suggest adding Pavel and Tamas, or anyone that has contributed to DynamicLoaderPOSIXDYLD as this will affect them.

What are the measured improvements here? We can't slow things down on any platforms. I know MacOS didn't respond well to making demangling run in parallel. I want to see some numbers here. And please don't quote numbers with tcmalloc or any special allocator unless you have a patch in LLDB already to make this a build option.

Fixed else after return.

Fixes:

• addressed Adrian's issues
• added test for invalid DIE ranges where high pc is less than low pc

Would love to get this one in if anyone any time. I have only one more patch after this for .debug_aranges

Fixed address ranges not being contained errors from incorrectly being reported.

David: this approach uses your suggested recursive approach and should make things clearer. It also adds verification of overlapping DW_TAG_lexical_block and DW_TAG_inlined_subroutine that are siblings at any level.

• Make DIE verification recursive
• Remove all Depth based code and just pass info from the parent
• add detection of overalap between DW_TAG_lexical_block or DW_TAG_inlined_subroutine DIEs at the same level
• rename RangeInfoType to DieRangeInfo
• create a new VerifyDieInfo to help with verification

Sorry missed your first note about perf. This has to be able to handle any number of strings efficiently and growing buckets is probably needed. How many buckets are you starting with here? The design probably shouldn't take up gobs of memory if it just has a few strings as well.

Do you have performance numbers here? I am all for it if it improves performance. If this is faster than llvm::StringMap why not just fix it there? Seems like everyone could benefit if you fix it in LLVM?

One thing to clarify:

And lets just get something to start with and optimize when we actually find something is taking too much memory or an algorithm is not efficient?

In D32821#745213, @dblaikie wrote:

I haven't followed some of the design direction Adrian's been pointing this work in - so all of this is subject to discussion, etc:

1. I'd expect not to build an entire representation of all ranges up-front, then verify them (uses more memory, etc) - but rather verify during a traversal of the DIEs instead

Looks fine to me, make sure Jim is happy as well.

This change is simply for the code moving, not the re-org.

-glldb doesn't emit the Apple accelerator tables IIRC. We don't need to change the DWARF, but just add the Apple accelerator tables by modifying clang to emit them. They will be just fine with DWO as each DWO file would have a set of them. The other way to do this to just check out if this works is to modify "llvm-dsymutil --update" to be able to work on ELF files. "llvm-dsymutil --update" regenerates the accelerator tables and puts them into the DWARF using an existing file with debug info. It was made in case we missing something in the accelerator tables that we added later so we could update old DWARF files gotten from build servers.

It is fine to create a DWARFVerifier.cpp, but can we do that in the next patch? Do you really want to review a patch where everything is moved around? And all functionality is moved around? This patch is nice and self contained.

Paul: I will submit a follow up patch for the DW_AT_stmt_list not being found multiple times since this patch is accepted.

So, unless somebody can come up with a solid use-case, I'd say it should be an error for two CUs to have the same DW_AT_stmt_list offset. (Maybe this should be in the .debug_info verification instead of the line-table verification, though.)

Paul: A future patch will add verification of unique DW_AT_stmt_list values and for verifying that all lines entries are in the CU ranges. I need to get another patch in before I do this as this other patch keeps track of all DW_TAG_subprogram address ranges, CU ranges, and verifies all DW_TAG_lexical_block and DW_TAG_inlined_subroutine are contained in their parents. Once I get that in, I can then verify each row address is found in the CU ranges (if available) and also agains the .debug_aranges (if available).

Woops, nice copy and paste error in the title. Sorry about that. Phabricator is getting worse for copy and paste these days...

David: I took care of all your requests from the previous patch in this one.

Lines have changed too much and a previous patch for llvm-dwarfdump --verify changed where verification happens. I will fix all requested items and make a new diff

In D32754#743899, @probinson wrote:

Can you verify that each CU (that has DW_AT_stmt_list) points to a different place in .debug_line?

I know no one is using TaskRunner, but I would rather not remove it just yet. It has the possibility of being useful. Not in this case, but in general. I'd be interested in hearing what Pavel and Tamas think? None of this affects LLDB on Mac because all Darwin (macOS, iOS, tvOS, watchOS) have Apple accelerator tables emitted by default. If you really want to speed things up, at least when compiling with a new clang, we can change the compiler to emit the apple accelerator tables on all systems...

So I don't see where you moved all of the .Append functions. And if you did your timings with them not being in there then your timings are off.

Ping

In D32757#743669, @scott.smith wrote:

In D32757#743657, @clayborg wrote:

In D32757#743567, @scott.smith wrote:

IMO, this is a simpler interface than TaskRunner. Also, after this, there are no users of TaskRunner left. Should I just delete them?

I think you might not have understood TaskRunner's real benefits. It is smart in the way it runs things: it lets you run N things and get each item as soon as it completes. The TaskMap will serialize everything. So if you have 100 items to do and item 0 takes 200 seconds to complete, and items 1 - 99 take 1ms to complete, you will need to wait for task 0 to complete before you can start parsing the data. This will slow down the DWARF parser if you switch over to this. TaskRunner should not be deleted as it has a very specific purpose. Your TaskMap works fine for one case, but not in the other.

That may provide a benefit on machines with a few cores, but doesn't really help when you have 40+ cores. Granted, the average laptop has 4 cores/8 hyperthreads.

And note in the DWARF parser you can't add the expensive code that aggregates all of the data into the SymbolFileDWARF into "parser_fn" because only on thread can be putting stuff into SymbolFileDWARF at a time.

In D32757#743567, @scott.smith wrote:

IMO, this is a simpler interface than TaskRunner. Also, after this, there are no users of TaskRunner left. Should I just delete them?

Marked things as done and commented where things weren't changed.

Updates:

• reflow code around StmtFormValue
• comment that we don't need to create an error where things are already checked in the .debug_info to make things clear
• Use StringRef where needed
• clang-format
• include bad file index in error message and update unit test
• use '\n' instead of "\n"

I also moved the verification code over into a Verifier class to prepare for future extra verification steps where we will need to persist data between two steps.

Fixed llvm-dwarfdump.cpp to use std::all_of.

Don't exit right away in llvm-dwarfdump if we encounter errors, exit with non-zero status after we have iterated across all files.

Marked things done

• clang-format
• fixes for Adrian

I will split this up as requested.

We can iterate on this.