Improve the handling of missing elf symtab and missing symbol sizes

[tberghammer]

Summary

Improve the handling of missing elf symtab and missing symbol sizes

• Generate artificial symbol names from eh_fame during symbol parsing so these symbols are already present when we calculate the size of the symbols where 0 is specified.
• Fix symbol size calculation for the last symbol in the file where it have to last until the end of the parent section

[clayborg]

Make sure we use a consistent naming scheme for symbols that don't have names between all ObjectFile subclasses.

source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp

2929

Use the same naming convention as ObjectFileMachO for these unnamed symbols:

Before starting to parse these symbols:

uint32_t synthetic_function_symbol_idx = 0;

Then when you find en EH frame FDE that doesn't have a symbol, the name is calculated with:

snprintf (synthetic_function_symbol,
          sizeof(synthetic_function_symbol),
          "___lldb_unnamed_function%u$$%s",
          ++synthetic_function_symbol_idx,
          module_sp->GetFileSpec().GetFilename().GetCString());

We could move this into ObjectFile.cpp somehow and then have both ObjectFileELF and ObjectFileMachO use the same function to create the function name. If we do this, we should use a lldb_private::StreamString when making the name.

[tberghammer]

source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp

2929

I moved the symbol name generation logic into ObjectFile and also changed ObjectFileMachO to use that one

[clayborg]

Looks good.

include/lldb/Core/RangeMap.h

#endif
                 // release or reduce the memory once it has been allocated/reserved.
                 m_entries.swap (minimal_ranges);
             }
         }
         
         // Calculate the byte size of ranges with zero byte sizes by finding
         // the next entry with a base address > the current base address
         void
-        CalculateSizesOfZeroByteSizeRanges ()
+        CalculateSizesOfZeroByteSizeRanges (S full_size = 0)
         {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
             assert (IsSorted());
 #endif
             typename Collection::iterator pos;
             typename Collection::iterator end;
             typename Collection::iterator next;
             for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
             {
                 if (pos->GetByteSize() == 0)
                 {
                     // Watch out for multiple entries with same address and make sure
                     // we find an entry that is greater than the current base address
                     // before we use that for the size
                     auto curr_base = pos->GetRangeBase();
                     for (next = pos + 1; next != end; ++next)
                     {
                         auto next_base = next->GetRangeBase();
                         if (next_base > curr_base)
                         {
                             pos->SetByteSize (next_base - curr_base);
                             break;
                         }
                     }
+                    if (next == end && full_size > curr_base)
+                        pos->SetByteSize (full_size - curr_base);
                 }
             }
         }
         
         void
         Clear ()
         {
             m_entries.clear();
#endif
                     --pos;
 
                 if (pos != end && pos->Contains(range))
                     return &(*pos);
             }
             return nullptr;
         }
         
+        const Entry*
+        FindEntryStartsAt (B addr) const
+        {
+#ifdef ASSERT_RANGEMAP_ARE_SORTED
+            assert (IsSorted());
+#endif
+            if (!m_entries.empty())
+            {
+                auto begin = m_entries.begin(), end = m_entries.end();
+                auto pos = std::lower_bound (begin, end, Entry(addr, 1), BaseLessThan);
+                if (pos != end && pos->base == addr)
+                    return &(*pos);
+            }
+            return nullptr;
+        }
+        
         Entry *
         Back()
         {
             return (m_entries.empty() ? nullptr : &m_entries.back());
         }
         
         const Entry *
         Back() const

include/lldb/Symbol/DWARFCallFrameInfo.h

public:
     //
     // @param[out] function_info
     //      A vector provided by the caller is filled out.  May be empty if no FDEs/no eh_frame
     //      is present in this Module.
 
     void
     GetFunctionAddressAndSizeVector (FunctionAddressAndSizeVector &function_info);
 
+    void
+    ForEachFDEEntries(const std::function<bool(lldb::addr_t, uint32_t, dw_offset_t)>& callback);
+
 private:
     enum
     {
         CFI_AUG_MAX_SIZE = 8,
         CFI_HEADER_SIZE = 8
     };
 
     struct CIE

include/lldb/Symbol/Symtab.h

const   Symbol *    GetParent (Symbol *symbol) const;
             uint32_t    AppendSymbolIndexesWithNameAndType (const ConstString& symbol_name, lldb::SymbolType symbol_type, std::vector<uint32_t>& matches);
             uint32_t    AppendSymbolIndexesWithNameAndType (const ConstString& symbol_name, lldb::SymbolType symbol_type, Debug symbol_debug_type, Visibility symbol_visibility, std::vector<uint32_t>& matches);
             uint32_t    AppendSymbolIndexesMatchingRegExAndType (const RegularExpression &regex, lldb::SymbolType symbol_type, std::vector<uint32_t>& indexes);
             uint32_t    AppendSymbolIndexesMatchingRegExAndType (const RegularExpression &regex, lldb::SymbolType symbol_type, Debug symbol_debug_type, Visibility symbol_visibility, std::vector<uint32_t>& indexes);
             size_t      FindAllSymbolsWithNameAndType (const ConstString &name, lldb::SymbolType symbol_type, std::vector<uint32_t>& symbol_indexes);
             size_t      FindAllSymbolsWithNameAndType (const ConstString &name, lldb::SymbolType symbol_type, Debug symbol_debug_type, Visibility symbol_visibility, std::vector<uint32_t>& symbol_indexes);
             size_t      FindAllSymbolsMatchingRexExAndType (const RegularExpression &regex, lldb::SymbolType symbol_type, Debug symbol_debug_type, Visibility symbol_visibility, std::vector<uint32_t>& symbol_indexes);
             Symbol *    FindFirstSymbolWithNameAndType (const ConstString &name, lldb::SymbolType symbol_type, Debug symbol_debug_type, Visibility symbol_visibility);
-            Symbol *    FindSymbolContainingFileAddress (lldb::addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes);
+            Symbol *    FindSymbolAtFileAddress (lldb::addr_t file_addr);
             Symbol *    FindSymbolContainingFileAddress (lldb::addr_t file_addr);
             void        ForEachSymbolContainingFileAddress(lldb::addr_t file_addr, std::function<bool(Symbol *)> const &callback);
             size_t      FindFunctionSymbols (const ConstString &name, uint32_t name_type_mask, SymbolContextList& sc_list);
             void        CalculateSymbolSizes ();
 
             void        SortSymbolIndexesByValue (std::vector<uint32_t>& indexes, bool remove_duplicates) const;
 
     static  void        DumpSymbolHeader (Stream *s);

source/Plugins/ObjectFile/ELF/ObjectFileELF.h

public:
     GetAddressByteSize() const override;
 
     lldb::AddressClass
     GetAddressClass (lldb::addr_t file_addr) override;
 
     lldb_private::Symtab *
     GetSymtab() override;
 
-    lldb_private::Symbol *
-    ResolveSymbolForAddress(const lldb_private::Address& so_addr, bool verify_unique) override;
-
     bool
     IsStripped () override;
 
     void
     CreateSections (lldb_private::SectionList &unified_section_list) override;
 
     void
     Dump(lldb_private::Stream *s) override;
private:
     /// given symbol table for each PLT slot.  Returns the number of symbols
     /// added.
     unsigned
     ParseTrampolineSymbols(lldb_private::Symtab *symbol_table, 
                            lldb::user_id_t start_id,
                            const ELFSectionHeaderInfo *rela_hdr,
                            lldb::user_id_t section_id);
 
+    void
+    ParseUnwindSymbols(lldb_private::Symtab *symbol_table,
+                       lldb_private::DWARFCallFrameInfo* eh_frame);
+
     /// Relocates debug sections
     unsigned
     RelocateDebugSections(const elf::ELFSectionHeader *rel_hdr, lldb::user_id_t rel_id);
 
     unsigned
     RelocateSection(lldb_private::Symtab* symtab, const elf::ELFHeader *hdr, const elf::ELFSectionHeader *rel_hdr,
                     const elf::ELFSectionHeader *symtab_hdr, const elf::ELFSectionHeader *debug_hdr,
                     lldb_private::DataExtractor &rel_data, lldb_private::DataExtractor &symtab_data,

source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp

for (i = 0; i < num_symbols; ++i)
                 mangled.SetMangledName( ConstString((mangled_name + suffix).str()) );
 
             ConstString demangled = mangled.GetDemangledName(lldb::eLanguageTypeUnknown);
             llvm::StringRef demangled_name = demangled.GetStringRef();
             if (!demangled_name.empty())
                 mangled.SetDemangledName( ConstString((demangled_name + suffix).str()) );
         }
 
-        // In ELF all symbol should have a valid size but it is not true for some code symbols
-        // coming from hand written assembly. As none of the code symbol should have 0 size we try
-        // to calculate the size for these symbols in the symtab with saying that their original
+        // In ELF all symbol should have a valid size but it is not true for some function symbols
+        // coming from hand written assembly. As none of the function symbol should have 0 size we
+        // try to calculate the size for these symbols in the symtab with saying that their original
         // size is not valid.
-        bool symbol_size_valid = symbol.st_size != 0 || symbol_type != eSymbolTypeCode;
+        bool symbol_size_valid = symbol.st_size != 0 || symbol.getType() != STT_FUNC;
 
         Symbol dc_symbol(
             i + start_id,       // ID is the original symbol table index.
             mangled,
             symbol_type,        // Type of this symbol
             is_global,          // Is this globally visible?
             false,              // Is this symbol debug info?
             false,              // Is this symbol a trampoline?
if (m_symtab_ap.get() == NULL)
 
                 if (m_symtab_ap == nullptr)
                     m_symtab_ap.reset(new Symtab(reloc_section->GetObjectFile()));
 
                 ParseTrampolineSymbols (m_symtab_ap.get(), symbol_id, reloc_header, reloc_id);
             }
         }
 
+        DWARFCallFrameInfo* eh_frame = GetUnwindTable().GetEHFrameInfo();
+        if (eh_frame)
+        {
+            if (m_symtab_ap == nullptr)
+                m_symtab_ap.reset(new Symtab(this));
+            ParseUnwindSymbols (m_symtab_ap.get(), eh_frame);
+        }
+
         // If we still don't have any symtab then create an empty instance to avoid do the section
         // lookup next time.
         if (m_symtab_ap == nullptr)
             m_symtab_ap.reset(new Symtab(this));
 
         m_symtab_ap->CalculateSymbolSizes();
     }
 
for (SectionHeaderCollIter I = m_section_headers.begin();
                     RelocateDebugSections(&reloc_header, reloc_id);
                 }
             }
         }
     }
     return m_symtab_ap.get();
 }
 
-Symbol *
-ObjectFileELF::ResolveSymbolForAddress(const Address& so_addr, bool verify_unique)
+void
+ObjectFileELF::ParseUnwindSymbols(Symtab *symbol_table, DWARFCallFrameInfo* eh_frame)
 {
-    if (!m_symtab_ap.get())
-        return nullptr; // GetSymtab() should be called first.
-
-    const SectionList *section_list = GetSectionList();
+    SectionList* section_list = GetSectionList();
     if (!section_list)
-        return nullptr;
+        return;
 
-    if (DWARFCallFrameInfo *eh_frame = GetUnwindTable().GetEHFrameInfo())
+    // First we save the new symbols into a separate list and add them to the symbol table after
+    // we colleced all symbols we want to add. This is neccessary because adding a new symbol
+    // invalidates the internal index of the symtab what causing the next lookup to be slow because
+    // it have to recalculate the index first.
+    std::vector<Symbol> new_symbols;
+
+    eh_frame->ForEachFDEEntries(
+        [symbol_table, section_list, &new_symbols](lldb::addr_t file_addr,
+                                                   uint32_t size,
+                                                   dw_offset_t) {
+        Symbol* symbol = symbol_table->FindSymbolAtFileAddress(file_addr);
+        if (symbol)
         {
-        AddressRange range;
-        if (eh_frame->GetAddressRange (so_addr, range))
+            if (!symbol->GetByteSizeIsValid())
             {
-            const addr_t file_addr = range.GetBaseAddress().GetFileAddress();
-            Symbol * symbol = verify_unique ? m_symtab_ap->FindSymbolContainingFileAddress(file_addr) : nullptr;
-            if (symbol)
-                return symbol;
-
-            // Note that a (stripped) symbol won't be found by GetSymtab()...
-            lldb::SectionSP eh_sym_section_sp = section_list->FindSectionContainingFileAddress(file_addr);
-            if (eh_sym_section_sp.get())
-            {
-                addr_t section_base = eh_sym_section_sp->GetFileAddress();
-                addr_t offset = file_addr - section_base;
-                uint64_t symbol_id = m_symtab_ap->GetNumSymbols();
-
+                symbol->SetByteSize(size);
+                symbol->SetSizeIsSynthesized(true);
+            }
+        }
+        else
+        {
+            SectionSP section_sp = section_list->FindSectionContainingFileAddress(file_addr);
+            if (section_sp)
+            {
+                addr_t offset = file_addr - section_sp->GetFileAddress();;
+                uint64_t symbol_id = symbol_table->GetNumSymbols();
                 Symbol eh_symbol(
-                        symbol_id,            // Symbol table index.
-                        "???",                // Symbol name.
-                        false,                // Is the symbol name mangled?
-                        eSymbolTypeCode,      // Type of this symbol.
-                        true,                 // Is this globally visible?
-                        false,                // Is this symbol debug info?
-                        false,                // Is this symbol a trampoline?
-                        true,                 // Is this symbol artificial?
-                        eh_sym_section_sp,    // Section in which this symbol is defined or null.
-                        offset,               // Offset in section or symbol value.
-                        range.GetByteSize(),  // Size in bytes of this symbol.
-                        true,                 // Size is valid.
-                        false,                // Contains linker annotations?
-                        0);                   // Symbol flags.
-                if (symbol_id == m_symtab_ap->AddSymbol(eh_symbol))
-                    return m_symtab_ap->SymbolAtIndex(symbol_id);
-            }
+                        symbol_id,       // Symbol table index.
+                        "???",           // Symbol name.
+                        false,           // Is the symbol name mangled?
+                        eSymbolTypeCode, // Type of this symbol.
+                        true,            // Is this globally visible?
+                        false,           // Is this symbol debug info?
+                        false,           // Is this symbol a trampoline?
+                        true,            // Is this symbol artificial?
+                        section_sp,      // Section in which this symbol is defined or null.
+                        offset,          // Offset in section or symbol value.
+                        0,               // Size:          Don't specify the size as an FDE can
+                        false,           // Size is valid: cover multiple symbols.
+                        false,           // Contains linker annotations?
+                        0);              // Symbol flags.
+                new_symbols.push_back(eh_symbol);
             }
         }
-    return nullptr;
-}
+        return true;
+    });
 
+    for (const Symbol& s : new_symbols)
+        symbol_table->AddSymbol(s);
+}
 
 bool
 ObjectFileELF::IsStripped ()
 {
     // TODO: determine this for ELF
     return false;
 }
 

source/Symbol/DWARFCallFrameInfo.cpp

//#endif
                 reg_location.SetIsDWARFExpression(block_data, block_len);
                 row.SetRegisterInfo (reg_num, reg_location);
                 return true;
             }
         }
     }
     return false;
 }
+
+void
+DWARFCallFrameInfo::ForEachFDEEntries(
+    const std::function<bool(lldb::addr_t, uint32_t, dw_offset_t)>& callback)
+{
+    GetFDEIndex();
+
+    for (size_t i = 0, c = m_fde_index.GetSize(); i < c; ++i)
+    {
+        const FDEEntryMap::Entry& entry = m_fde_index.GetEntryRef(i);
+        if (!callback(entry.base, entry.size, entry.data))
+            break;
+    }
+}

source/Symbol/Symtab.cpp

if (!m_file_addr_to_index_computed && !m_symbols.empty())
             if (pos->ValueIsAddress())
             {
                 entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
                 entry.SetByteSize(pos->GetByteSize());
                 entry.data = std::distance(begin, pos);
                 m_file_addr_to_index.Append(entry);
             }
         }
+
+        lldb::addr_t total_size = 0;
+
         const size_t num_entries = m_file_addr_to_index.GetSize();
         if (num_entries > 0)
         {
             m_file_addr_to_index.Sort();
-            m_file_addr_to_index.CalculateSizesOfZeroByteSizeRanges();
-        
             // Now our last symbols might not have had sizes because there
             // was no subsequent symbol to calculate the size from. If this is
             // the case, then calculate the size by capping it at the end of the
             // section in which the symbol resides
             for (int i = num_entries - 1; i >= 0; --i)
             {
-                const FileRangeToIndexMap::Entry &entry = m_file_addr_to_index.GetEntryRef(i);
-                // As we iterate backwards, as soon as we find a symbol with a valid
-                // byte size, we are done
+                const FileRangeToIndexMap::Entry& entry = m_file_addr_to_index.GetEntryRef(i);
+
+                // As we iterate backwards, as soon as we find a symbol with a valid byte size, we
+                // are done.
                 if (entry.GetByteSize() > 0)
                     break;
 
-                // Cap the size to the end of the section in which the symbol resides
-                SectionSP section_sp (m_objfile->GetSectionList()->FindSectionContainingFileAddress (entry.GetRangeBase()));
-                if (section_sp)
-                {
-                    const lldb::addr_t end_section_file_addr = section_sp->GetFileAddress() + section_sp->GetByteSize();
-                    const lldb::addr_t symbol_file_addr = entry.GetRangeBase();
-                    if (end_section_file_addr > symbol_file_addr)
-                    {
-                        Symbol &symbol = m_symbols[entry.data];
-                        if (!symbol.GetByteSizeIsValid())
-                        {
-                            symbol.SetByteSize(end_section_file_addr - symbol_file_addr);
-                            symbol.SetSizeIsSynthesized(true);
-                        }
-                    }
-                }
-            }
-            // Sort again in case the range size changes the ordering
-            m_file_addr_to_index.Sort();
+                const Address& address = m_symbols[entry.data].GetAddressRef();
+                if (SectionSP section_sp = address.GetSection())
+                    total_size = entry.base + section_sp->GetByteSize() - address.GetOffset();
+
+            m_file_addr_to_index.CalculateSizesOfZeroByteSizeRanges(total_size);
         }
     }
 }
 
 void
 Symtab::CalculateSymbolSizes ()
 {
     Mutex::Locker locker (m_mutex);
if (!m_symbols.empty())
                 symbol.SetByteSize(range_size);
                 symbol.SetSizeIsSynthesized(true);
             }
         }
     }
 }
 
 Symbol *
-Symtab::FindSymbolContainingFileAddress (addr_t file_addr, const uint32_t* indexes, uint32_t num_indexes)
+Symtab::FindSymbolAtFileAddress (addr_t file_addr)
 {
     Mutex::Locker locker (m_mutex);
+    if (!m_file_addr_to_index_computed)
+        InitAddressIndexes();
 
-    
-    SymbolSearchInfo info = { this, file_addr, nullptr, nullptr, 0 };
-
-    ::bsearch (&info, 
-               indexes, 
-               num_indexes, 
-               sizeof(uint32_t), 
-               (ComparisonFunction)SymbolWithClosestFileAddress);
-
-    if (info.match_symbol)
-    {
-        if (info.match_offset == 0)
-        {
-            // We found an exact match!
-            return info.match_symbol;
-        }
-
-        if (!info.match_symbol->GetByteSizeIsValid())
-        {
-            // The matched symbol dosn't have a valid byte size so lets just go with that match...
-            return info.match_symbol;
-        }
-
-        // We were able to figure out a symbol size so lets make sure our 
-        // offset puts "file_addr" in the symbol's address range.
-        if (info.match_offset < info.match_symbol->GetByteSize())
-            return info.match_symbol;
+    const FileRangeToIndexMap::Entry *entry = m_file_addr_to_index.FindEntryStartsAt(file_addr);
+    if (entry)
+        Symbol* symbol = SymbolAtIndex(entry->data);
+        if (symbol->GetFileAddress() == file_addr)
+            return symbol;
     }
     return nullptr;
 }
 
 Symbol *
 Symtab::FindSymbolContainingFileAddress (addr_t file_addr)
 {
     Mutex::Locker locker (m_mutex);
Symtab::ForEachSymbolContainingFileAddress(addr_t file_addr, std::function<bool(Symbol *)> const &callback)
 
     std::vector<uint32_t> all_addr_indexes;
 
     // Get all symbols with file_addr
     const size_t addr_match_count = m_file_addr_to_index.FindEntryIndexesThatContain(file_addr, all_addr_indexes);
 
     for (size_t i = 0; i < addr_match_count; ++i)
     {
-        if (!callback(SymbolAtIndex(all_addr_indexes[i])))
+        Symbol* symbol = SymbolAtIndex(all_addr_indexes[i]);
+        if (symbol->ContainsFileAddress(file_addr))
+        {
+            if (!callback(symbol))
                 break;
         }
     }
+}
 
 void
 Symtab::SymbolIndicesToSymbolContextList (std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list)
 {
     // No need to protect this call using m_mutex all other method calls are
     // already thread safe.
     
     const bool merge_symbol_into_function = true;