Improve performance when parsing symbol tables in mach-o files.

[clayborg]

Summary

Some larger projects were loading quite slowly with the current LLDB on macOS and macOS simulator builds. I did some instrument traces and found 3 main culprits:

• a LLDB timer that was put into a function that was called too often
• a std::set that was keeping track of the address of symbols that were already added
• a unnamed function generator in ObjectFile that was going slow due to allocations

In order to see this in action I ran the latest LLDB on a large application with many frameworks using the following method:

(lldb) script import time; start_time = time.perf_counter()
(lldb) file Large.app
(lldb) script print(time.perf_counter() - start_time)

I first range "sudo purge" to clear the system file caches to simulate a cold startup of the debugger, followed by two iterations with warm file caches.

Prior to this fix I was seeing the following timings:

17.68 (cold)
14.56 (warm 1)
14.52 (warm 2)

After this fix I was seeing:

11.32 (cold)
8.43 (warm 1)
8.49 (warm 2)

[shafik]

lldb/source/Symbol/ObjectFile.cpp

623–626

We should avoid potentially hiding side effects inside expressions or function calls, I would suggest moving the ++m_synthetic_symbol_idx before.

[JDevlieghere]

LGTM

lldb/source/Core/Module.cpp

if (index < num_comp_units) {
     if (SymbolFile *symbols = GetSymbolFile())
       cu_sp = symbols->GetCompileUnitAtIndex(index);
   }
   return cu_sp;
 }
 
 bool Module::ResolveFileAddress(lldb::addr_t vm_addr, Address &so_addr) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
-  LLDB_SCOPED_TIMERF("Module::ResolveFileAddress (vm_addr = 0x%" PRIx64 ")",
-                     vm_addr);
   SectionList *section_list = GetSectionList();
   if (section_list)
     return so_addr.ResolveAddressUsingFileSections(vm_addr, section_list);
   return false;
 }
 
 uint32_t Module::ResolveSymbolContextForAddress(
     const Address &so_addr, lldb::SymbolContextItem resolve_scope,

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

 #include "lldb/Utility/RegisterValue.h"
 #include "lldb/Utility/Status.h"
 #include "lldb/Utility/StreamString.h"
 #include "lldb/Utility/Timer.h"
 #include "lldb/Utility/UUID.h"
 
 #include "lldb/Host/SafeMachO.h"
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 #include "ObjectFileMachO.h"
 
 #if defined(__APPLE__)
 #include <TargetConditionals.h>
 // GetLLDBSharedCacheUUID() needs to call dlsym()
if (n_sect < m_section_infos.size()) {
               section_sp->GetByteSize());
         } else {
           std::string filename = "<unknown>";
           SectionSP first_section_sp(m_section_list->GetSectionAtIndex(0));
           if (first_section_sp)
             filename = first_section_sp->GetObjectFile()->GetFileSpec().GetPath();
 
           Host::SystemLog(Host::eSystemLogError,
-                          "error: unable to find section %d for a symbol in %s, corrupt file?\n",
-                          n_sect, 
-                          filename.c_str());
+                          "error: unable to find section %d for a symbol in "
+                          "%s, corrupt file?\n",
+                          n_sect, filename.c_str());
         }
       }
       if (m_section_infos[n_sect].vm_range.Contains(file_addr)) {
         // Symbol is in section.
         return m_section_infos[n_sect].section_sp;
       } else if (m_section_infos[n_sect].vm_range.GetByteSize() == 0 &&
                  m_section_infos[n_sect].vm_range.GetBaseAddress() ==
                      file_addr) {
size_t ObjectFileMachO::ParseSymtab() {
   // The data element of type bool indicates that this entry is thumb
   // code.
   typedef AddressDataArray<lldb::addr_t, bool, 100> FunctionStarts;
 
   // Record the address of every function/data that we add to the symtab.
   // We add symbols to the table in the order of most information (nlist
   // records) to least (function starts), and avoid duplicating symbols
   // via this set.
-  std::set<addr_t> symbols_added;
+  llvm::DenseSet<addr_t> symbols_added;
+
+  // We are using a llvm::DenseSet for "symbols_added" so we must be sure we
+  // do not add the tombstone or empty keys to the set.
+  auto add_symbol_addr = [&symbols_added](lldb::addr_t file_addr) {
+    // Don't add the tombstone or empty keys.
+    if (file_addr == UINT64_MAX || file_addr == UINT64_MAX - 1)
+      return;
+    symbols_added.insert(file_addr);
+  };
   FunctionStarts function_starts;
   lldb::offset_t offset = MachHeaderSizeFromMagic(m_header.magic);
   uint32_t i;
   FileSpecList dylib_files;
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS));
   llvm::StringRef g_objc_v2_prefix_class("_OBJC_CLASS_$_");
   llvm::StringRef g_objc_v2_prefix_metaclass("_OBJC_METACLASS_$_");
   llvm::StringRef g_objc_v2_prefix_ivar("_OBJC_IVAR_$_");
if (dsc_data_sp) {
                                     GSYM_sym_idx;
                                 // Copy the address, because often the N_GSYM
                                 // address has an invalid address of zero
                                 // when the global is a common symbol
                                 sym[GSYM_sym_idx].GetAddressRef().SetSection(
                                     symbol_section);
                                 sym[GSYM_sym_idx].GetAddressRef().SetOffset(
                                     symbol_value);
-                                symbols_added.insert(sym[GSYM_sym_idx]
-                                                         .GetAddress()
-                                                         .GetFileAddress());
+                                add_symbol_addr(sym[GSYM_sym_idx]
                                 // We just need the flags from the linker
                                 // symbol, so put these flags
                                 // into the N_GSYM flags to avoid duplicate
                                 // symbols in the symbol table
                                 sym[GSYM_sym_idx].SetFlags(nlist.n_type << 16 |
                                                            nlist.n_desc);
                                 sym[sym_idx].Clear();
                                 continue;
                               }
                             }
                           }
                         }
                       }
 
                       sym[sym_idx].SetID(nlist_idx);
                       sym[sym_idx].SetType(type);
                       if (set_value) {
                         sym[sym_idx].GetAddressRef().SetSection(symbol_section);
                         sym[sym_idx].GetAddressRef().SetOffset(symbol_value);
-                        symbols_added.insert(
+                        add_symbol_addr(
                             sym[sym_idx].GetAddress().GetFileAddress());
                       }
                       sym[sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
 
                       if (symbol_byte_size > 0)
                         sym[sym_idx].SetByteSize(symbol_byte_size);
 
                       if (demangled_is_synthesized)
auto ParseSymbolLambda = [&](struct nlist_64 &nlist, uint32_t nlist_idx,
                   N_GSYM_name_to_sym_idx.find(gsym_name);
               if (pos != N_GSYM_name_to_sym_idx.end()) {
                 const uint32_t GSYM_sym_idx = pos->second;
                 m_nlist_idx_to_sym_idx[nlist_idx] = GSYM_sym_idx;
                 // Copy the address, because often the N_GSYM address has an
                 // invalid address of zero when the global is a common symbol.
                 sym[GSYM_sym_idx].GetAddressRef().SetSection(symbol_section);
                 sym[GSYM_sym_idx].GetAddressRef().SetOffset(symbol_value);
-                symbols_added.insert(
+                add_symbol_addr(
                     sym[GSYM_sym_idx].GetAddress().GetFileAddress());
                 // We just need the flags from the linker symbol, so put these
                 // flags into the N_GSYM flags to avoid duplicate symbols in
                 // the symbol table.
                 sym[GSYM_sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
                 sym[sym_idx].Clear();
                 return true;
               }
             }
           }
         }
       }
 
       sym[sym_idx].SetID(nlist_idx);
       sym[sym_idx].SetType(type);
       if (set_value) {
         sym[sym_idx].GetAddressRef().SetSection(symbol_section);
         sym[sym_idx].GetAddressRef().SetOffset(symbol_value);
-        symbols_added.insert(sym[sym_idx].GetAddress().GetFileAddress());
+        if (symbol_section)
+          add_symbol_addr(sym[sym_idx].GetAddress().GetFileAddress());
       }
       sym[sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
       if (nlist.n_desc & N_WEAK_REF)
         sym[sym_idx].SetIsWeak(true);
 
       if (symbol_byte_size > 0)
         sym[sym_idx].SetByteSize(symbol_byte_size);
 
if (module_sp->ResolveFileAddress(e.entry.address, symbol_addr)) {
       if (symbol_section) {
         sym[sym_idx].SetID(synthetic_sym_id++);
         sym[sym_idx].GetMangled().SetMangledName(ConstString(symbol_name));
         if (demangled_is_synthesized)
           sym[sym_idx].SetDemangledNameIsSynthesized(true);
         sym[sym_idx].SetIsSynthetic(true);
         sym[sym_idx].SetExternal(true);
         sym[sym_idx].GetAddressRef() = symbol_addr;
-        symbols_added.insert(symbol_addr.GetFileAddress());
+        add_symbol_addr(symbol_addr.GetFileAddress());
         if (e.entry.flags & TRIE_SYMBOL_IS_THUMB)
           sym[sym_idx].SetFlags(MACHO_NLIST_ARM_SYMBOL_IS_THUMB);
         ++sym_idx;
       }
     }
   }
 
   if (function_starts_count > 0) {
if (num_synthetic_function_symbols > 0) {
                 symbol_byte_size = section_end_file_addr - symbol_file_addr;
               }
               sym[sym_idx].SetID(synthetic_sym_id++);
               sym[sym_idx].GetMangled().SetDemangledName(
                   GetNextSyntheticSymbolName());
               sym[sym_idx].SetType(eSymbolTypeCode);
               sym[sym_idx].SetIsSynthetic(true);
               sym[sym_idx].GetAddressRef() = symbol_addr;
-              symbols_added.insert(symbol_addr.GetFileAddress());
+              add_symbol_addr(symbol_addr.GetFileAddress());
               if (symbol_flags)
                 sym[sym_idx].SetFlags(symbol_flags);
               if (symbol_byte_size)
                 sym[sym_idx].SetByteSize(symbol_byte_size);
               ++sym_idx;
             }
           }
         }
if (indirect_symbol_index_data.GetByteSize()) {
                   sym[sym_idx].GetMangled() = stub_symbol_mangled_name;
                   if (resolver_addresses.find(symbol_stub_addr) ==
                       resolver_addresses.end())
                     sym[sym_idx].SetType(eSymbolTypeTrampoline);
                   else
                     sym[sym_idx].SetType(eSymbolTypeResolver);
                   sym[sym_idx].SetIsSynthetic(true);
                   sym[sym_idx].GetAddressRef() = so_addr;
-                  symbols_added.insert(so_addr.GetFileAddress());
+                  add_symbol_addr(so_addr.GetFileAddress());
                   sym[sym_idx].SetByteSize(symbol_stub_byte_size);
                   ++sym_idx;
                 }
               } else {
                 if (log)
                   log->Warning("symbol stub referencing symbol table symbol "
                                "%u that isn't in our minimal symbol table, "
                                "fix this!!!",

lldb/source/Symbol/ObjectFile.cpp

if (name.startswith("_OBJC_")) {
       // ObjC v1
       return lldb::eSymbolTypeObjCClass;
     }
   }
   return symbol_type_hint;
 }
 
 ConstString ObjectFile::GetNextSyntheticSymbolName() {
-  StreamString ss;
+  llvm::SmallString<256> name;
+  llvm::raw_svector_ostream os(name);
   ConstString file_name = GetModule()->GetFileSpec().GetFilename();
-  ss.Printf("___lldb_unnamed_symbol%u$$%s", ++m_synthetic_symbol_idx,
-            file_name.GetCString());
-  return ConstString(ss.GetString());
+  ++m_synthetic_symbol_idx;
+  os << "___lldb_unnamed_symbol" << m_synthetic_symbol_idx << "$$"
+     << file_name.GetStringRef();
+  return ConstString(os.str());
 }
 
 std::vector<ObjectFile::LoadableData>
 ObjectFile::GetLoadableData(Target &target) {
   std::vector<LoadableData> loadables;
   SectionList *section_list = GetSectionList();
   if (!section_list)
     return loadables;