This is an archive of the discontinued LLVM Phabricator instance.

[LLDB][ELF] Load both, .symtab and .dynsym sections
AbandonedPublic

Authored by kwk on Sep 10 2019, 2:38 AM.

Details

Summary

This change ensures that the .dynsym section will be parsed even when there's already is a .symtab.

It is motivated because of minidebuginfo (https://sourceware.org/gdb/current/onlinedocs/gdb/MiniDebugInfo.html#MiniDebugInfo).

There it says:

Keep all the function symbols not already in the dynamic symbol table.

That means the .symtab embedded inside the .gnu_debugdata does NOT contain the symbols from .dynsym. But in order to put a breakpoint on all symbols we need to load both.

To not add symbols that where already added I keep a list of unique ELF symbols on each invocation of ObjectFileELF::GetSymtab.

My other patch D66791 implements support for minidebuginfo, that's why I need this change.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
JDevlieghere added inline comments.
lldb/lit/Modules/ELF/load-from-dynsym-alone.test
24 ↗(On Diff #219502)

Please also add llvm-strip to the list of support tools (toolchain.py:127).

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2656

Can you motivate the need for this change? This comment seems to suggest that reading the symtab table should be sufficient as it should contain all the information from the dynsym. If that is not true, it would be worth updating this comment.

2685

Why did you remove the last part of the original comment? This seemed to be the most useful part... The newly added sentences explain what we are doing (which is relatively clear from the code). I'd rather see a comment explaining "why" something needs to happen.

kwk updated this revision to Diff 219587.Sep 10 2019, 12:45 PM
  • Added llvm-strip to the list of support tools
kwk marked an inline comment as done.EditedSep 10 2019, 12:55 PM

@JDevlieghere I change the support tool. It was @labath who requested (D66791#inline-601050) to outsource this patch.

Let's put this bit into a separate patch. As I said over IRC, I view this bit as functionally independent of the debugdata stuff (it's definitely independent in it's current form, as it will kick in for non-debugdata files too, which I think is fine).

The change is motivated because of minidebuginfo (https://sourceware.org/gdb/current/onlinedocs/gdb/MiniDebugInfo.html#MiniDebugInfo).

There it says:

  1. Keep all the function symbols not already in the dynamic symbol
  2. table.

That means the .symtab embedded inside the .gnu_debugdata does NOT contain the symbols from .dynsym. But in order to put a breakpoint on all symbols we need to load both. I hope this makes sense.

My other patch D66791 implements support for minidebuginfo, that's why I need this change.

kwk updated this revision to Diff 219594.Sep 10 2019, 1:21 PM
kwk marked an inline comment as done.
  • update comment for .symtab section with minidebuginfo
kwk added a comment.Sep 10 2019, 1:22 PM

Fixed the comment as per request.

JDevlieghere accepted this revision.Sep 10 2019, 2:07 PM

Thanks! This LGTM with the comment on line 2660 rephrased and the motivation as part of the summary/commit message.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2685

The symtab section is non-allocable and can be stripped, while the dynsym section which should always be always be there. If both exist we load both to support the minidebuginfo case. Otherwise we just load the dynsym section.

This revision is now accepted and ready to land.Sep 10 2019, 2:07 PM
kwk updated this revision to Diff 219605.Sep 10 2019, 2:15 PM
  • Rephrase comment
kwk edited the summary of this revision. (Show Details)Sep 10 2019, 2:16 PM
labath accepted this revision.Sep 11 2019, 2:32 AM

lgtm. The reason I requested this to be put separately, is because it is implemented in a way that kicks in even without minidebuginfo. I think this is fine, because entries can be removed from the symtab even without the whole minidebuginfo business. While this format will likely be the only real user of these partial symtabs, in theory, there isn't anything stopping someone from removing symtab entries independently of that. While unlikely, I see no harm in supporting that, if it does not incur any extra maintenance costs.

lldb/lit/Modules/ELF/load-from-dynsym-alone.test
14 ↗(On Diff #219605)

s/.dynamic/.dynsym/

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2659–2661

How about we make this less layered, and rephrase the existing comment a bit: "Information in the dynsym section is *usually* also found in the symtab, but this is not required as symtab entries can be removed after linking. The minidebuginfo format makes use of this facility to create smaller symbol tables.

2693–2696

I wouldn't bother with this. You can just unconditionally create a Symtab object before you start parsing any symbol tables.

kwk updated this revision to Diff 219677.Sep 11 2019, 2:55 AM

Updated commit message and squashed commits into one rebased onto master.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptSep 11 2019, 3:01 AM
kwk marked 3 inline comments as done.Sep 11 2019, 3:13 AM

@labath I've addressed your comment rewrites in a fixup commit that I've commited without a review (llvm-svn: 371600): https://reviews.llvm.org/rLLDB371600

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2693–2696

I don't fully agree that it is that simple because further down in the code we do check for if (m_symtab_up == nullptr) and that is a condition I need to respect because of relocation, don't I?

It broke on linux too. You did run the tests before committing, did you?

labath added inline comments.Sep 11 2019, 6:04 AM
lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2693–2696

Well.. I'm pretty sure you could delete those null checks too. But, given that these null checks seem to be the prevailing pattern in this function, changing that might be better left for a separate patch...

kwk added a comment.Sep 11 2019, 10:44 PM

@stella.stamenova I've reverted this patch and thanks for letting me know.

@labath I didn't notice that tests failed, I'm really sorry.

@labath how shall we go about this? We do have the situation that when you lookup a symbol you might find it twice if it is in .dynsym and in .symtab. Shall I adjust the test expectation to that or change my implementation?

kwk reopened this revision.Sep 15 2019, 9:17 PM
This revision is now accepted and ready to land.Sep 15 2019, 9:17 PM
kwk updated this revision to Diff 220273.Sep 15 2019, 9:17 PM
  • [LLDB][ELF] Fixup for comments in D67390
  • Change test expectation to find 2 instead of 1 symbol
In D67390#1667270, @kwk wrote:

@labath how shall we go about this? We do have the situation that when you lookup a symbol you might find it twice if it is in .dynsym and in .symtab. Shall I adjust the test expectation to that or change my implementation?

That's a good question (and another reason why I wanted this to be a separate patch). Since only two tests broke it does not seem like having some symbols twice does much harm. OTOH, having an identical symbol twice does seem like asking for trouble down the line. One possibility would be to restrict this merging to the gnu_debugdata case only. Another option would be to make the merging code smarter and avoid adding the symbol a second time if it has the same name and address. That would have the advantage of having the symbol just once in the common case, while still preserving the full information (in case the symbol tables were munged independently of the gnu_debugdata thingy).

Overall, I guess I would prefer the last solution (inserting only different symbols) unless that turns out to be difficult. In that case, I think just restricting this to gnu_debugdata is fine.

BTW, if you want, I think you can submit the rest of the gnu_debugdata changes without waiting for this, if you just adjust the test expectations to account for the fact that symtab+dynsym merging does not work (yet).

lldb/packages/Python/lldbsuite/test/functionalities/load_unload/TestLoadUnload.py
276 ↗(On Diff #220273)

You can't do that because this will have only two matches on elf platforms. Since we don't really care about the number here. I suggest finding a string that can be grepped for, which does not depend on the number of matches (maybe just a_function).

kwk added a comment.Sep 16 2019, 4:57 AM
In D67390#1667270, @kwk wrote:

@labath how shall we go about this? We do have the situation that when you lookup a symbol you might find it twice if it is in .dynsym and in .symtab. Shall I adjust the test expectation to that or change my implementation?

That's a good question (and another reason why I wanted this to be a separate patch). Since only two tests broke it does not seem like having some symbols twice does much harm. OTOH, having an identical symbol twice does seem like asking for trouble down the line. One possibility would be to restrict this merging to the gnu_debugdata case only. Another option would be to make the merging code smarter and avoid adding the symbol a second time if it has the same name and address. That would have the advantage of having the symbol just once in the common case, while still preserving the full information (in case the symbol tables were munged independently of the gnu_debugdata thingy).

Overall, I guess I would prefer the last solution (inserting only different symbols) unless that turns out to be difficult. In that case, I think just restricting this to gnu_debugdata is fine.

The crucial line is the following line in ObjectFileELF::ParseSymbols():

symtab->AddSymbol(dc_symbol);

If I change that to:

symtab->FindSymbolsByNameAndAddress(dc_symbol.GetName(), dc_symbol.GetAddress(), indexVector)
if (indexVector.empty()) {
  symtab->AddSymbol(dc_symbol);
}

is that the logic you have in mind? FindSymbolsByNameAndAddress I would need to implement.

BTW, if you want, I think you can submit the rest of the gnu_debugdata changes without waiting for this, if you just adjust the test expectations to account for the fact that symtab+dynsym merging does not work (yet).

Let's wait first, okay?

In D67390#1667270, @kwk wrote:

@labath how shall we go about this? We do have the situation that when you lookup a symbol you might find it twice if it is in .dynsym and in .symtab. Shall I adjust the test expectation to that or change my implementation?

That's a good question (and another reason why I wanted this to be a separate patch). Since only two tests broke it does not seem like having some symbols twice does much harm.

You should ensure that there aren't multiple symbols for the same address. Mach-o has this problem with the STAB symbols and the standard symbol table symbols. That plug-in will unique them into one using the STAB symbol table index as the lldb::user_id_t.

OTOH, having an identical symbol twice does seem like asking for trouble down the line. One possibility would be to restrict this merging to the gnu_debugdata case only. Another option would be to make the merging code smarter and avoid adding the symbol a second time if it has the same name and address. That would have the advantage of having the symbol just once in the common case, while still preserving the full information (in case the symbol tables were munged independently of the gnu_debugdata thingy).

We really want to present the simplest and best view of the module to the the user. So please do only create one symbol, no matter how many sources we have.

Overall, I guess I would prefer the last solution (inserting only different symbols) unless that turns out to be difficult. In that case, I think just restricting this to gnu_debugdata is fine.

Code to unique symbols isn't that hard to do during the symbol table parsing. Thought don't keep re-sorting the lldb_private::Symbol objects, just keep a side map that has file address to symbol name. I am guessing it will be easier than mach-o because there the different symbols have different info (STAB vs normal symbol table symbol) where as in ELF they should be the same.

BTW, if you want, I think you can submit the rest of the gnu_debugdata changes without waiting for this, if you just adjust the test expectations to account for the fact that symtab+dynsym merging does not work (yet).

Love to see this fixed prior to checkin in possible

In D67390#1671128, @kwk wrote:
In D67390#1667270, @kwk wrote:

@labath how shall we go about this? We do have the situation that when you lookup a symbol you might find it twice if it is in .dynsym and in .symtab. Shall I adjust the test expectation to that or change my implementation?

That's a good question (and another reason why I wanted this to be a separate patch). Since only two tests broke it does not seem like having some symbols twice does much harm. OTOH, having an identical symbol twice does seem like asking for trouble down the line. One possibility would be to restrict this merging to the gnu_debugdata case only. Another option would be to make the merging code smarter and avoid adding the symbol a second time if it has the same name and address. That would have the advantage of having the symbol just once in the common case, while still preserving the full information (in case the symbol tables were munged independently of the gnu_debugdata thingy).

Overall, I guess I would prefer the last solution (inserting only different symbols) unless that turns out to be difficult. In that case, I think just restricting this to gnu_debugdata is fine.

The crucial line is the following line in ObjectFileELF::ParseSymbols():

symtab->AddSymbol(dc_symbol);

If I change that to:

symtab->FindSymbolsByNameAndAddress(dc_symbol.GetName(), dc_symbol.GetAddress(), indexVector)
if (indexVector.empty()) {
  symtab->AddSymbol(dc_symbol);
}

in mach-o plug-in we keep a std::map or something easier. We don't sort or search the current lldb_private::Symbol objects since they aren't sorted, nor are the name indexes created until we are done with adding all symbols. Can we use a side map that is just something like:

std::map<lldb::addr_t, ContString> SymbolMapType;

is that the logic you have in mind? FindSymbolsByNameAndAddress I would need to implement.

BTW, if you want, I think you can submit the rest of the gnu_debugdata changes without waiting for this, if you just adjust the test expectations to account for the fact that symtab+dynsym merging does not work (yet).

Let's wait first, okay?

kwk added a comment.Sep 16 2019, 9:17 AM

@clayborg what address is it exactly to store here std::map<lldb::addr_t, ContString> SymbolMapType;? As an example dc_symbol.GetAddress().GetFileAddress() is something that would work but as soon as we have minidebuginfo, then we might end having the same symbol coming from two different object files and so their address would still be different. Also do you want me to keep this map in ObjectFileELF?

In D67390#1671463, @kwk wrote:

@clayborg what address is it exactly to store here std::map<lldb::addr_t, ContString> SymbolMapType;? As an example dc_symbol.GetAddress().GetFileAddress() is something that would work but as soon as we have minidebuginfo, then we might end having the same symbol coming from two different object files and so their address would still be different. Also do you want me to keep this map in ObjectFileELF?

We might need a private function on ObjectFileELF that takes an extra parameter. My idea would be something like:

... ObjectFileELF::GetSymtab() {
  std::map<lldb::addr_t, ConstString SymbolMapType;
  SymbolMapType symbol_map;
  ParseSymbolTablePrivate(..., symbol_map); // .symtab
  ParseSymbolTablePrivate(..., symbol_map); // .dynsym
  ParseSymbolTablePrivate(..., symbol_map); // .other?
clayborg added a comment.EditedSep 16 2019, 9:59 AM
In D67390#1671463, @kwk wrote:

@clayborg what address is it exactly to store here std::map<lldb::addr_t, ContString> SymbolMapType;? As an example dc_symbol.GetAddress().GetFileAddress() is something that would work but as soon as we have minidebuginfo, then we might end having the same symbol coming from two different object files and so their address would still be different. Also do you want me to keep this map in ObjectFileELF?

The file address should be sufficient for normal ELF files. When we have a minidebuginfo, we should almost to loading this as part of the ObjectFileELF that points to the minidebuginfo and parsing it as if it were part of that file. SymbolVendor used to exist to allow one view of an executable using multiple individual ObjectFile objects, but that got removed. So now it might be best to load the minidebuginfo file as an ObjectFileELF _just_ to access the data in the ".gnu_debugdata" and decompress it, and use that data to add to the symbol table of the current file? So the code would be:

ObjectFileELF::GetSymtab() {
  std::map<lldb::addr_t, ConstString SymbolMapType;
  SymbolMapType symbol_map;
  ParseSymbolTablePrivate(..., symbol_map); // .symtab from current file
  ParseSymbolTablePrivate(..., symbol_map); // .dynsym from current file
  // Detect ".gnu_debugdata" file and load it
  FileSpec gnu_debugdata_file(...);
  if (gnu_debugdata_file.Exists()) {
    ObjectfileELF gnu_debugdata(gnu_debugdata_file);
    gnu_debugdata_symtab_data = gnu_debugdata.GetSectionData();
    // Decompress above data and parse the symbol table as if it is part of this file?
   ParseSymbolTablePrivate(...); // .gnu_debugdata symtab
  }

This assumes that the .gnu_debugdata file has the same section definitions for things like .text and .data etc.

kwk added a comment.Sep 17 2019, 2:13 AM

@clayborg thank you for this explanation. My patch for minidebuginfo is already done in D66791 . But this one here I was asked to pull out as a separate patch. For good reasons as we see. I wonder how this extra parameter SymbolMapType of yours does help. In the end I have to identify duplicates. But if no symbol with the same name should be added then why do I care about where the symbol is coming from?

Please help me understand of follow my thoughts here:

When I'm in the (lldb) console and type b foo I expect LLDB to set a breakpoint on the function foo, right? The type of the symbol foo is deduced as function. I ask this question because Symtab has no function to just search for a symbol by name; instead you always have to pass an address, a type or an ID:

Symbol *FindSymbolByID(lldb::user_id_t uid) const;
Symbol *FindSymbolWithType(lldb::SymbolType symbol_type,
size_t FindAllSymbolsWithNameAndType(ConstString name,
size_t FindAllSymbolsWithNameAndType(ConstString name,
size_t FindAllSymbolsMatchingRexExAndType(
Symbol *FindFirstSymbolWithNameAndType(ConstString name,
Symbol *FindSymbolAtFileAddress(lldb::addr_t file_addr);
Symbol *FindSymbolContainingFileAddress(lldb::addr_t file_addr);
size_t FindFunctionSymbols(ConstString name, uint32_t name_type_mask,

So my point of this whole question is: What makes a symbol unique in the sense that it shouldn't be added to the symtab if it is already there?

Shouldn't the type of the symbol together with it's name define uniqueness? We shouldn't care about where the symbol is coming from nor if it is located at a different address. Well, if there's an overloaded function foo(int) and foo(char*) then both symbols are of type function and they both share the same name. When you type b foo you DO want 2 breakpoints to be set. Hence, niqueness cannot be defined over the name and the type . But wait, the name is mangled, so it IS unique enough unless I use Symbol::GetNameNoArguments(); there only the name is returned.

Here's my naive approach to test the admittedly very weird thought process from above: https://github.com/kwk/llvm-project/commit/5da4559a00c73ebefd8f8199890bd1991c94fa3f

In D67390#1672210, @kwk wrote:

So my point of this whole question is: What makes a symbol unique in the sense that it shouldn't be added to the symtab if it is already there?

A symbol name is not unique because you can have multiple (static) functions with the same (mangled) name in one module. An address is not unique as well because you can have symbol aliases, which will have the same address (and we want to keep both names to resolve name breakpoints correctly for instance).

The name+address combination (my original suggestion) should be sufficiently unique for the purposes we care about. Theoretically, if you want, you could include some additional items in the uniqueness "key" like symbol type etc. (to rule out the perverse case of somebody setting a "file" symbol to conflict with some other function symbol), but I don't think that is really necessary.

In D67390#1672210, @kwk wrote:

@clayborg thank you for this explanation. My patch for minidebuginfo is already done in D66791 . But this one here I was asked to pull out as a separate patch. For good reasons as we see. I wonder how this extra parameter SymbolMapType of yours does help. In the end I have to identify duplicates. But if no symbol with the same name should be added then why do I care about where the symbol is coming from?

The uniqueness is for symbols with the same name and file address and size. You can have multiple symbols with the same name, and each on could have a different address. We want there to only be one symbol per ObjectFile that has the same name + addr + size. That way when we ask for symbols by name, we don't have to end up getting more than one symbol for something that is the same thing.

Please help me understand of follow my thoughts here:

When I'm in the (lldb) console and type b foo I expect LLDB to set a breakpoint on the function foo, right? The type of the symbol foo is deduced as function.

Breakpoints ask for symbols whose type is lldb::eSymbolTypeCode and that match the name. The name matching is much more complex than you would think though. "b foo" by default turns into 'set a breakpoint on functions whose "basename" matches foo'. This means a C function named 'foo', any C++ method (stand alone function or class method) whose basename is 'foo' (bar::foo(int)", "foo(int)", "foo(float)", "std::a::b::foo()", many more) and any objective C function whose selector is 'foo' ("-[MyClass foo]", "+[AnotherClass foo]", and any other basename from any other language.

If you type "b foo::bar" this will end up looking up all functions whose basename is "bar" and then making sure any found matches contain "foo::bar".

I ask this question because Symtab has no function to just search for a symbol by name; instead you always have to pass an address, a type or an ID:

Symbol *FindSymbolByID(lldb::user_id_t uid) const;
Symbol *FindSymbolWithType(lldb::SymbolType symbol_type,
size_t FindAllSymbolsWithNameAndType(ConstString name,
size_t FindAllSymbolsWithNameAndType(ConstString name,
size_t FindAllSymbolsMatchingRexExAndType(
Symbol *FindFirstSymbolWithNameAndType(ConstString name,
Symbol *FindSymbolAtFileAddress(lldb::addr_t file_addr);
Symbol *FindSymbolContainingFileAddress(lldb::addr_t file_addr);
size_t FindFunctionSymbols(ConstString name, uint32_t name_type_mask,

FindAllSymbolsWithNameAndType() takes a name. The symbol type can be lldb::eSymbolTypeAny, so yes there is way to search. So there is a way to search for a symbol by name. The main issue is we are still parsing the symbol table and we don't want to initialized the name lookup table in the symbol table just yet since we are still adding symbols to the complete list. This is why an extra map that is used only during parsing of the symbol table makes sense.

So my point of this whole question is: What makes a symbol unique in the sense that it shouldn't be added to the symtab if it is already there?

Symbol is unique within one representation of an ObjectFile where the symbol has the same name, address and size and type.

Shouldn't the type of the symbol together with it's name define uniqueness? We shouldn't care about where the symbol is coming from nor if it is located at a different address.

We don't care where the symbol comes from as long as it is representing information for one ObjectFile. I would contend that if you have an "a.out" binary that has a .gnu_debugdata that points to "a.out.gnu_debugdata" that we would have one single ObjectFile that represents "a.out" and give the best description of what "a.out" contains.

We do care if a symbol has a different address. You can have as many static functions called "foo" as you want in a single binary. They are each unique since they have different addresses. So if you have 10 source files where 3 of those sources have a symbol "foo", we want there to be 3 different symbols with the same name, different addresses and possibly different sizes.

Well, if there's an overloaded function foo(int) and foo(char*) then both symbols are of type function and they both share the same name. When you type b foo you DO want 2 breakpoints to be set.

Yes we do! One breakpoint in LLDB has N breakpoint locations. A breakpoint of any kind (source file and line, function name breakpoint, and more) all constantly adding and removing locations as shared libraries get loaded. So if you have "foo(int)" and "foo(char *)" and say "b foo" we would end up with one breakpoint whose name matches "foo" with two locations.

Hence, niqueness cannot be defined over the name and the type . But wait, the name is mangled, so it IS unique enough unless I use Symbol::GetNameNoArguments(); there only the name is returned.

Again, there can be N breakpoints with the same name and different addresses. We are just trying to avoid a symbol table that has 3 symbols all with the name "foo", address of 0x1000 and size of 0x10. Why? Because the information is redundant and is just noise. The map I suggested would track these symbols so we don't end up adding multiple of the same symbols. Again, name address and size must all match. We _can_ have multiple symbols at the same address with different names. How? Linkers often have aliased symbols that point to the same thing. if we have a symbol "foo" at 0x1000 with size 0x10, we can also have a symbol "foo_alias" at 0x1000 and size 0x10. We need both so that we can set breakpoints correctly when setting breakpoints by name.

Here's my naive approach to test the admittedly very weird thought process from above: https://github.com/kwk/llvm-project/commit/5da4559a00c73ebefd8f8199890bd1991c94fa3f

I will take a look.

Let me know if you have any questions about what I said above.

In D67390#1672210, @kwk wrote:

So my point of this whole question is: What makes a symbol unique in the sense that it shouldn't be added to the symtab if it is already there?

A symbol name is not unique because you can have multiple (static) functions with the same (mangled) name in one module. An address is not unique as well because you can have symbol aliases, which will have the same address (and we want to keep both names to resolve name breakpoints correctly for instance).

The name+address combination (my original suggestion) should be sufficiently unique for the purposes we care about. Theoretically, if you want, you could include some additional items in the uniqueness "key" like symbol type etc. (to rule out the perverse case of somebody setting a "file" symbol to conflict with some other function symbol), but I don't think that is really necessary.

We could track any extra data we need in the map if needed as Pavel suggests above. Not sure if it is needed, but we could do it if necessary.

kwk added a comment.Sep 18 2019, 1:35 AM

@clayborg are you on IRC?

kwk added a comment.Sep 24 2019, 10:09 AM

@clayborg @labath I'm still trying to only add symbols when they are unique.

Take this already existing test:

./bin/llvm-lit -avv ~/llvm-project/lldb/lit/SymbolFile/DWARF/debug-types-line-tables.s

The symbols that are being added at the end of ObjectFileELF::ParseSymbols are these:

Symbol:
  i: 1
  start_id: 0
  symbol_bare: ""
  is_mangled: 0
  symbol_type: 0
  is_global: 0
  symbol_section_sp: 0x1915710 (.debug_str)
  symbol_value: 0
  symbol.st_size: 0
  symbol_size_valid: 1
  has_suffix: 0
  flags: 3

Symbol:
  i: 2
  start_id: 0
  symbol_bare: ""
  is_mangled: 0
  symbol_type: 0
  is_global: 0
  symbol_section_sp: 0x19157e0 (.debug_abbrev)
  symbol_value: 0
  symbol.st_size: 0
  symbol_size_valid: 1
  has_suffix: 0
  flags: 3

Symbol:
  i: 3
  start_id: 0
  symbol_bare: ""
  is_mangled: 0
  symbol_type: 0
  is_global: 0
  symbol_section_sp: 0x1915a50 (.debug_line)
  symbol_value: 0
  symbol.st_size: 0
  symbol_size_valid: 1
  has_suffix: 0
  flags: 3

I wonder how to define uniqueness for them. As you can see, the only difference is the symbol section which wasn't part of your definition of uniqueness (yet).

In D67390#1681034, @kwk wrote:

I wonder how to define uniqueness for them. As you can see, the only difference is the symbol section which wasn't part of your definition of uniqueness (yet).

These symbols should be obviously all kept distinct. Yes, you should add to the tuple also ELFSymbol::st_shndx as I have seen in your code: https://people.redhat.com/jkratoch/kwk-branch.diff

kwk updated this revision to Diff 221689.Sep 25 2019, 1:52 AM
  • [LLDB][ELF] Fixup for comments in D67390
  • Change test expectation to find 2 instead of 1 symbol
  • symbol uniqueness by using elf::ELFSymbol
kwk updated this revision to Diff 221690.Sep 25 2019, 1:58 AM
  • Revert "Change test expectation to find 2 instead of 1 symbol"
jankratochvil added inline comments.Sep 25 2019, 2:11 AM
lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
280

It could be in the same order as ELFSymbol fields as otherwise it is difficult to verify all the fields are matched here.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
42

Is it really needed?

2205

What if the symbol is ignored, the function will then incorrectly return a number of added symbols even when they were not added, wouldn't it?

kwk added a comment.Sep 25 2019, 11:55 PM

Please wait before reviewing this patch again. I will let you know when things do work.

kwk updated this revision to Diff 221968.Sep 26 2019, 9:03 AM
  • Adjust other occurrence of AddSymbol where ELF plays a role
  • Working tests
  • Use unordered_set for storing unique elf symbols

So overall approach is good. See inline comments for issue and questions.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

I would almost just manually compare only the things we care about here. Again, what about st_shndx when comparing a symbol from the main symbol table and one from the .gnu_debugdata symbol table. Are those section indexes guaranteed to match? I would think not.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
289

Do we need a ConstString for the st_shndx as well so we can correctly compare a section from one file to a section from another as in the .gnu_debugdata case?

441

An ELF symbol from one symbol table can have the same name as another yet with a different st_name string table offset. Do we even want to be able to hash an ELFSymbol on its own? Maybe remove this enture function and only hash NamedELFSymbol?

444

I know the section index will match between for symbol tables in the same ELF file, but what about a symbol table in an external file like .gnu_debugdata?

454

Don't we need to hash everything we care about except the st_name? Those indexes can differ if they come from a different string table? Shouldn't this be:

std::size_t h1 = std::hash<elf::elf_addr>()(s.st_value);
std::size_t h2 = std::hash<elf::elf_xword>()(s.st_size);
// Skip std::size_t h3 = std::hash<elf::elf_word>()(s.st_name);
std::size_t h4 = std::hash<unsigned char>()(s.st_info);
std::size_t h5 = std::hash<unsigned char>()(s.st_other);
std::size_t h6 = std::hash<elf::elf_half>()(s.st_shndx);
std::size_t h7 = std::hash<const char *>()(s.st_name_string.AsCString());
return llvm::hash_combine(h1, h2, h4, h5, h6, h7);

I left the "h" variables with the same names to show we don't want "h3".

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2201–2205

Do we even need NamedELFSymbol? Can we just make an unordered_set of lldb_private::Symbol values?

kwk updated this revision to Diff 222029.Sep 26 2019, 2:35 PM
  • Cleanup
kwk edited the summary of this revision. (Show Details)Sep 26 2019, 2:38 PM
kwk updated this revision to Diff 222073.Sep 26 2019, 8:38 PM
  • Cleanup
kwk updated this revision to Diff 222075.Sep 26 2019, 9:00 PM
kwk marked 10 inline comments as done.
  • Change order of compare members to match order of member definitions.
kwk added a comment.Sep 26 2019, 9:02 PM

Not all is answered now but please respect: https://reviews.llvm.org/D67390#1683705

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

@clayborg I explicitly only compare what we care about and therefore always set the name index to be the same.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
289

That is a good point.

454

That's why I explicitly set the name to 0 always which effectively ignores it because it has no effect on the hash then. Please see the specialization hash for NamedELFSymbol.

kwk updated this revision to Diff 222076.Sep 26 2019, 9:14 PM
  • make the section name part of NamedELFSymbol
kwk marked 9 inline comments as done.Sep 26 2019, 9:29 PM

I think I've finished the implementation now and should have answered all your comments and concerns. I run tests now. I would appreciate if you (@clayborg , @labath , @jankratochvil ) can take a look at this patch again.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
289

@clayborg in fact I think this could be the reason not to use a set of lldb_private::Symbol objects because there we don't store the section name or symbol name but only addresses or indexes. I did add the st_section_name_string struct member.

444

I did add the section name to NamedELFSymbol and explicitly ignore it when building the hash for the base ELFSymbol.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
42

removed.

2201–2205

@clayborg I find it much easier with NamedELFSymbol because all we have to do is derive from ELFSymbol and add the strings for the symbol name and the section name. If we were to use lldb_private::Symbol I would have to lookup the symbols manually each time I calculate a hash which seems bad. I mean, the symbol and section name already are ConstStrings and should be stored and computed very efficiently. Also I wanted to keep things local to ELF and not mess with everything that uses lldb_private::Symbol. Makes sense?

2205

@jankratochvil we already have places inside this for-loop where we continue. I hope it is okay to ask the same question back that you've asked for those continue-places. Why don't we adjust the returned number (i) in case symbols where skipped?

kwk updated this revision to Diff 222080.Sep 26 2019, 10:02 PM
kwk marked an inline comment as done.
  • Use symbol name including @VERSION suffix.
kwk added a comment.EditedSep 26 2019, 10:04 PM

Interesting. It looks like we had a test that wants a symbol to be added twice:

[ RUN      ] MangledTest.NameIndexes_FindFunctionSymbols
/home/kkleine/llvm/lldb/unittests/Core/MangledTest.cpp:186: Failure
      Expected: 1
To be equal to: Count("puts@GLIBC_2.6", eFunctionNameTypeFull)
      Which is: 0
/home/kkleine/llvm/lldb/unittests/Core/MangledTest.cpp:187: Failure
      Expected: 2
To be equal to: Count("puts", eFunctionNameTypeFull)
      Which is: 1
/home/kkleine/llvm/lldb/unittests/Core/MangledTest.cpp:188: Failure
      Expected: 2
To be equal to: Count("puts", eFunctionNameTypeBase)
      Which is: 1
[  FAILED  ] MangledTest.NameIndexes_FindFunctionSymbols (1 ms)

Before I used the bare symbol name with stripped @VERSION suffix. Now I've changed the implementation of NamedELFSymbol to include the @VERSION suffix and the tests pass.

This looks fairly ok to me, but it could use a more explicit test of the symbol uniqueing code. Right, now I believe the two tests you added check that the symbols are _not_ uniqued. (They're also a bit hard to follow due to the whole
objcopy business). Could you create a test with a yaml file which will contain various edge cases relevant to this code. I'm thinking of stuff like "a dynsym and a symtab symbol at the same address, but a different name", "a dynsym and symtab symbols with identical names, but different addresses", etc. Then just run "image dump symtab" on that file to check what we have parsed?

I am also surprised that you weren't able to just use a Section* (instead of the name) for the uniqueing. I'd expect that all symbols (even those from the separate object file) should be resolved to the sections in the main object. I see that this isn't the case, but I am surprised that this isn't causing any problems. Anyway, as things seem to be working as they are now, we can leave that for another day.

In D67390#1685313, @kwk wrote:

Before I used the bare symbol name with stripped @VERSION suffix. Now I've changed the implementation of NamedELFSymbol to include the @VERSION suffix and the tests pass.

Interesting. I'm pretty sure that the symbol count is irrelevant for that test (it just wants to know if it is there), so we can change that if needed. However, having the uniqueing include the @VERSION sounds right to me, so if that makes the test happy too then, great.

lldb/lit/Modules/ELF/Inputs/load-from-dynsym-alone.c
1 ↗(On Diff #222080)

It looks like you could inline these test inputs into the test files. You'd just need to change all the comments to // and add .c to the list of valid suffixes in lit.local.cfg.

lldb/lit/Modules/ELF/load-from-dynsym-alone.test
16 ↗(On Diff #222080)

s/dynmic/dynamic/

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

I'll echo @clayborg here. This business with copying the ELFSymbol and clearing some fields is confusing. Do you even need the ELFSymbol::operator== for anything? If not I'd just delete that, and have the derived version compare all fields.

Also, it would be nice if the operator== and hash function definitions were next to each other. Can you just forward declare the std::hash stuff in the header, and have the implementation be next to this?

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2202–2204

Move this into the NamedELFSymbol constructor?

2205

something like if (unique_elf_symbols.insert(needle).second) would be more efficient, as you don't need to mess with the map twice.

2648

what's wrong with the old-fashioned UniqueElfSymbolColl unique_elf_symbols; ?

jankratochvil added inline comments.Sep 27 2019, 4:43 AM
lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
457

I find better to rather define std::hash<ConstString> (or provide ConstString::Hasher which I do in my DWZ patchset).

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2205

I would unconditionally add all the symbols to std::vector<NamedElfSymbol> unique_elf_symbols (with unique_elf_symbols.reserve in advance for the sym of .symtab+.dynsym sizes) and then after processing both .symtab and .dynsym and can llvm::sort(unique_elf_symbols) and add to symtab only those which are unique. I believe it will be much faster, one could benchmark it.

labath added inline comments.Sep 27 2019, 4:48 AM
lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2205

sounds like a good idea.

kwk marked 8 inline comments as done.Sep 30 2019, 4:26 AM

This looks fairly ok to me, but it could use a more explicit test of the symbol uniqueing code. Right, now I believe the two tests you added check that the symbols are _not_ uniqued. (They're also a bit hard to follow due to the whole
objcopy business). Could you create a test with a yaml file which will contain various edge cases relevant to this code. I'm thinking of stuff like "a dynsym and a symtab symbol at the same address, but a different name", "a dynsym and symtab symbols with identical names, but different addresses", etc. Then just run "image dump symtab" on that file to check what we have parsed?

I'll give my best to implement this today.

I am also surprised that you weren't able to just use a Section* (instead of the name) for the uniqueing. I'd expect that all symbols (even those from the separate object file) should be resolved to the sections in the main object. I see that this isn't the case, but I am surprised that this isn't causing any problems. Anyway, as things seem to be working as they are now, we can leave that for another day.

Okay.

In D67390#1685313, @kwk wrote:

Before I used the bare symbol name with stripped @VERSION suffix. Now I've changed the implementation of NamedELFSymbol to include the @VERSION suffix and the tests pass.

Interesting. I'm pretty sure that the symbol count is irrelevant for that test (it just wants to know if it is there), so we can change that if needed. However, having the uniqueing include the @VERSION sounds right to me, so if that makes the test happy too then, great.

Yes, I hoped so. Thank you. Please await another revision of this patch with the tests requested.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

I'll echo @clayborg here. This business with copying the ELFSymbol and clearing some fields is confusing.

I've cleared up the documentation now and it is exactly the way I like it. Every entity deals with it's own business (respects its own fields when comparing). I find it pretty dirty to compare fields from the base struct in a derived one. The way I compare fields from the base struct is minimally invasive.

Do you even need the ELFSymbol::operator== for anything?

Yes, when you want to compare ELFSymbols. I know that I don't do that explicitly but I the function only deals with fields from the entity itself and they don't spill into any derived structure (with the exception of explicitly ignoring fields).

If not I'd just delete that, and have the derived version compare all fields.

No because I call it explcitly from the derived NamedELFSymbol.

Also, it would be nice if the operator== and hash function definitions were next to each other. Can you just forward declare the std::hash stuff in the header, and have the implementation be next to this?

I've found a compromise that is even more appealing to me. The ELFSymbol and NamedELFSymbol structs now have a hash function which contains the implementation next to the one of operator==(). This hash is called in the specialization which remains in the same location as before; the reason being that I didn't find a way do define something in the std:: namespace when I'm in the elf:: namespace.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
457

Once your DWZ patchset arrives, please let me know and we can change it.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2205

@jankratochvil @labath yes, this sound like a good idea for *performance* improvement but honestly, I need to get this patch done first in order to make any progress with minidebuginfo. I hope you don't mind when I take this task to another patch, okay?

2648

Apparently nothing now :) . But before I had troubles because of some deleted default constructor. Thanks for spotting this and bringing it back to my attention.

kwk updated this revision to Diff 222387.Sep 30 2019, 4:27 AM
kwk marked an inline comment as done.
  • typo: dynmic -> dynamic
  • Applied changes requested in review
kwk marked 2 inline comments as done.Sep 30 2019, 4:29 AM
kwk added a comment.EditedSep 30 2019, 6:16 AM

@labath I did prepare some YAML file but apparently yaml2obj isn't meant to deal with this properly. Instead I get an Error like this: yaml2obj: error: repeated symbol name: 'main'. It looks like symbols from the Symbols: part of the YAML file are just added by name to a map. Changing yaml2obj for this seems a bit too heavy right now. If you're okay I'll go with a few more c programs if I can pull them off.

Here's the part hat causes the error:

template <class ELFT> void ELFState<ELFT>::buildSymbolIndexes() {
  auto Build = [this](ArrayRef<ELFYAML::Symbol> V, NameToIdxMap &Map) {
    for (size_t I = 0, S = V.size(); I < S; ++I) {
      const ELFYAML::Symbol &Sym = V[I];
      if (!Sym.Name.empty() && !Map.addName(Sym.Name, I + 1))
        reportError("repeated symbol name: '" + Sym.Name + "'");
    }
  };

  Build(Doc.Symbols, SymN2I);
  Build(Doc.DynamicSymbols, DynSymN2I);
}
kwk updated this revision to Diff 222427.Sep 30 2019, 7:33 AM
  • Added YAML test to merge symbols
kwk updated this revision to Diff 222441.Sep 30 2019, 8:28 AM
  • include test code in .c test file
kwk marked an inline comment as done.Sep 30 2019, 8:28 AM
kwk updated this revision to Diff 222479.Sep 30 2019, 12:52 PM
  • Fix comment
labath added inline comments.Sep 30 2019, 11:40 PM
lldb/lit/Modules/ELF/merge-symbols.yaml
52

smymtab

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

Yes, when you want to compare ELFSymbols. I know that I don't do that explicitly but I the function only deals with fields from the entity itself and they don't spill into any derived structure (with the exception of explicitly ignoring fields).

Yes, but to me that exception kind of invalidates the whole idea. In order to know which fields you need to ignore, you need the knowledge of what fields are present in the struct (and as the fields are public, that is not a big deal), at which point you can just avoid the whole copying business, and explicitly compare the fields that you care about. Given that this also saves a nontrivial amount of code, I still think it's a better way to go. (Also, defining equality operators on class hierarchies is usually not a good idea even if they "nest" nicely, since they can still produce strange results due to object slicing.)

I've found a compromise that is even more appealing to me. The ELFSymbol and NamedELFSymbol structs now have a hash function which contains the implementation next to the one of operator==().

That works for me.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2205

I don't think that kind of reasoning really applies here, since it's this patch that is introducing the potential performance problem. However, I don't think that is going to be a big deal, so I think we can leave this out for now.

kwk updated this revision to Diff 222569.Oct 1 2019, 2:38 AM
kwk marked 8 inline comments as done.
  • Remove verbose output in test
  • Fix typo: smymtab -> symtab
  • Move compare and hash logic out of base class into derived class as requested
kwk marked an inline comment as done.Oct 1 2019, 2:40 AM

@labath can you please check this patch one last time (hopefully)?

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
371–373

@labath okay, I've remove the logic from ELFSymbol and coded everything straight away. I guess, that I wanted to be able to extend ELFSymbol with n number of fields and add them to the ELFSymbol::operator==() without touching the NamedELFSymbol::operator==() as long as the added fields shall not be ignored. Makes sense? I guess that you can find arguments for both ways to implement it. Anyway, I've coded it the way you want now, I hope.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2205

Okay, thank you for allowing me to leave it out for now.

kwk updated this revision to Diff 222576.Oct 1 2019, 3:21 AM
  • Correct comment of test
kwk updated this revision to Diff 222577.Oct 1 2019, 3:22 AM
  • Fix comment
kwk updated this revision to Diff 222584.Oct 1 2019, 3:55 AM
  • Simplify NamedELFSymbol::hash()
labath accepted this revision.Oct 1 2019, 5:10 AM

Ok, let's give this one more shot. Thanks for your patience. I do have a couple of additional comments inline, but I don't think we need another round of review for those.

lldb/lit/Modules/ELF/merge-symbols.yaml
23

Please add a CHECK-EMPTY: after this line to ensure there are no additional symbols here.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
253–256

Is this really needed? It looks like the default compiler-generated copy constructor would be sufficient here.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
1918–1919

delete

2636

delete

jankratochvil added inline comments.Oct 1 2019, 6:32 AM
lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
383

llvm::hash_combine already calls std::hash<T> for each of its parameters.

lldb/source/Plugins/ObjectFile/ELF/ELFHeader.h
457

https://people.redhat.com/jkratoch/ConstStringHasher.patch - Although then the whole UniqueElfSymbolColl should be replaced by std::sort+std::unique of std::vector you plan in a future patch so the hashing does not matter much.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
1925

also delete

2666

For the planned rework of the unification of symbols it could be put (I think) to Symtab::InitAddressIndexes which already sorts the Symtab anyway.

kwk updated this revision to Diff 222634.Oct 1 2019, 8:45 AM
kwk marked 10 inline comments as done.
  • Check that no additional symbols follow after the expected ones
  • Use compiler-generated copy-ctor
  • Cleanup from experiment
  • Simplify NamedELFSymbol::hash()
  • Cleanup
lldb/source/Plugins/ObjectFile/ELF/ELFHeader.cpp
383

Good to know. Thank you.

lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
2636

Sorry, I noticed this myself as well. Some of the performance experiment spilled over in this patch.

2666

Honestly, for the rework I think about not to use an std::vector as you proposed but instead create the std::unordered_set using a bucket count that is equal to the number of symbols in .symtab and in .dynsym. Then inserts to that set will be constant as they are for the vector. But let's see how it goes in a followup patch. I have the feeling that if I use the approach you suggested, I need to keep a vector *and* a set around. The vector for collecting all symbols and the set for doing the unification, no? Anyway, let's postpone this.

kwk abandoned this revision.Oct 2 2019, 8:00 AM

Here's the relevant transcript from #lldb@otfc for why this change is abandoned.

[10/02/19 15:22:25] <jankratochvil> labath: Is it acceptable for you?  "BTW given how this unique-ness of symbols turns out to be non-trivial is it really needed?  Because for regular .symtab we can ignore .dynsym (as current LLDB does) and for .gnu_debugdata->.symtab we can just concatenate it with .dynsym and there will be no symbol duplicates anyway."
[10/02/19 15:22:25] <jankratochvil> Otherwise it is either a big code complication or a big performance regression and it is not really needed for anything.
[10/02/19 15:27:42] <labath> yeah, i suppose that would work
[10/02/19 15:28:11] <labath> then you just need to make sure the merging does not kick in for non-gnu_debugdata sections
[10/02/19 15:28:30] <labath> a simple check on the existing of this section might suffice
[10/02/19 15:29:39] <labath> it seems to me that it would be useful to have information from both sources available, but it is true that nobody has really needed that so far
[10/02/19 15:36:11] <jankratochvil> Thanks.
[10/02/19 15:36:22] <jankratochvil> kkleine: ^^^ Let's call it a win-win. :-)
[10/02/19 16:14:27] <kkleine> labath, jankratochvil I wonder if we the merging with .gnu_debugdata needs to be as "clever" as it is today and if it is enough to just add symbols without checking for uniqueness. That would simplify things even more.
[10/02/19 16:16:32] <jankratochvil> I think just add it without checks.
[10/02/19 16:16:53] <labath> works for me