[lldb] Speed up looking for dSYM next to executable

[bulbazord]

Summary

The goal of this patch is to speed up the code that searches for a dSYM
next to an executable.

I generated a project with 10,000 c source files and accompanying header
files using a script that I wrote. I generated objects for each of them
(with debug info in it) but intentionally did not create a dSYM for
anything. I also built a driver, and then linked everything into one
binary. The project itself is very simple, but the number of object files
involved is very large. I then measured lldb's performance debugging
this binary. (NB: I plan on putting this script into lldb's script
directory at some point after some cleanups)

Using the command lldb -x -b -o 'b main' $binary (launch lldb with no
lldbinit, place a breakpoint on main, and then quit), I measured how
long this takes and measured where time was being spent.

On my machine, I used hyperfine to get some statistics about how long
this actually took:

alex@alangford many-objects % hyperfine -w 3 -- "$lldb -x -b -o 'b main' $binary"
Benchmark 1: $lldb -x -b -o 'b main' $binary
  Time (mean ± σ):      4.395 s ±  0.046 s    [User: 3.239 s, System: 1.245 s]
  Range (min … max):    4.343 s …  4.471 s    10 runs

Out of the ~4.4 seconds of work, it looks like ~630ms were being spent
on LocateDSYMInVincinityOfExecutable. After digging in further, we
were spending the majority of our time manipulating paths in FileSpec
with RemoveLastPathComponent and AppendPathComponent. There were a
lot of FileSystem operations as well, so I made an attempt to minimize
the amount of calls to Exists and Resolve as well.

Given how widely used the code in FileSpec is, I opted to improve this
codepath specifically rather than attempt to refactor the internals of
FileSpec. I believe that improving FileSpec is also worth doing, but as
it is a larger change with far reaching implications, I opted to make
this change instead.

With this change, we shave off approximately 600ms:

alex@alangford many-objects % hyperfine -w 3 -- "$lldb -x -b -o 'b main' $binary"
Benchmark 1: $lldb -x -b -o 'b main' $binary
  Time (mean ± σ):      3.822 s ±  0.056 s    [User: 2.749 s, System: 1.167 s]
  Range (min … max):    3.750 s …  3.920 s    10 runs

[bulbazord]

Perhaps the right thing to do would be to try to do the larger FileSpec changes instead? The changes in Symbols::LocateExecutableSymbolFile can probably go in regardless though. We call Resolve on all the file specs in debug_file_search_paths on line 307, so no need to call Resolve twice.

[mib]

lldb/source/Symbol/LocateSymbolFile.cpp

89–91

Why do you need the first call to append ?

102–118

Is this extra dot on purpose ?

105–108

This part is a bit confusing ... may be a comment would help understand what we're trying to achieve here.

178–181

Same here ... this could use a comment to explain what we're doing.

[bulbazord]

lldb/source/Symbol/LocateSymbolFile.cpp

89–91

The code suggestion you've given doesn't work for 2 reasons:

• llvm::sys::path::append only takes 4 Twine arguments, so this won't compile.
• llvm::sys::path::append appends things as if they were paths. So for /bin/ls you'll end up with /bin/ls/.dSYM/Contents/Resources/DWARF instead of /bin/ls.dSYM/Contents/Resources/DWARF.

102–118

I wanted to distinguish between $parent_dir/CF.framework because what is the parent_dir in this case? I used 3 dots to indicate $some_path/CF.framework.

105–108

I'll add more to the comment.

178–181

Will add.

[bulbazord]

Address @mib's comments

[mib]

Thanks! LGTM!

[JDevlieghere]

IMHO this is optimizing the wrong thing. If FileSpec is slow, then we should try to make that faster, instead of updating the different places it's used.

[bulbazord]

I'm going to see how we could potentially improve FileSpec's performance rather than go with this approach.

lldb/source/Symbol/LocateSymbolFile.cpp

 // Given a binary exec_fspec, and a ModuleSpec with an architecture/uuid,
 // return true if there is a matching dSYM bundle next to the exec_fspec,
 // and return that value in dsym_fspec.
 // If there is a .dSYM.yaa compressed archive next to the exec_fspec,
 // call through Symbols::DownloadObjectAndSymbolFile to download the
 // expanded/uncompressed dSYM and return that filepath in dsym_fspec.
 
 static bool LookForDsymNextToExecutablePath(const ModuleSpec &mod_spec,
-                                            const FileSpec &exec_fspec,
+                                            llvm::StringRef executable_path,
+                                            llvm::sys::path::Style path_style,
                                             FileSpec &dsym_fspec) {
-  ConstString filename = exec_fspec.GetFilename();
-  FileSpec dsym_directory = exec_fspec;
-  dsym_directory.RemoveLastPathComponent();
-
-  std::string dsym_filename = filename.AsCString();
-  dsym_filename += ".dSYM";
-  dsym_directory.AppendPathComponent(dsym_filename);
-  dsym_directory.AppendPathComponent("Contents");
-  dsym_directory.AppendPathComponent("Resources");
-  dsym_directory.AppendPathComponent("DWARF");
-
-  if (FileSystem::Instance().Exists(dsym_directory)) {
-
-    // See if the binary name exists in the dSYM DWARF
-    // subdir.
-    dsym_fspec = dsym_directory;
-    dsym_fspec.AppendPathComponent(filename.AsCString());
-    if (FileSystem::Instance().Exists(dsym_fspec) &&
-        FileAtPathContainsArchAndUUID(dsym_fspec, mod_spec.GetArchitecturePtr(),
+  llvm::StringRef filename = llvm::sys::path::filename(executable_path, path_style);
+  llvm::SmallString<64> dsym_file = executable_path;
+
+  dsym_file.append(".dSYM");
+  llvm::sys::path::append(dsym_file, path_style, "Contents", "Resources",
+                          "DWARF", filename);
+
+  // First, see if the binary name exists in the dSYM DWARF subdir
+  if (FileSystem::Instance().Exists(dsym_file)) {
+    dsym_fspec.SetFile(dsym_file, path_style);
+    if (FileAtPathContainsArchAndUUID(dsym_fspec, mod_spec.GetArchitecturePtr(),
                                       mod_spec.GetUUIDPtr())) {
       return true;
     }
+  }
 
-    // See if we have "../CF.framework" - so we'll look for
-    // CF.framework.dSYM/Contents/Resources/DWARF/CF
-    // We need to drop the last suffix after '.' to match
-    // 'CF' in the DWARF subdir.
-    std::string binary_name(filename.AsCString());
-    auto last_dot = binary_name.find_last_of('.');
-    if (last_dot != std::string::npos) {
-      binary_name.erase(last_dot);
-      dsym_fspec = dsym_directory;
-      dsym_fspec.AppendPathComponent(binary_name);
-      if (FileSystem::Instance().Exists(dsym_fspec) &&
-          FileAtPathContainsArchAndUUID(dsym_fspec,
+  // If the "executable path" is actually a framework bundle, e.g.
+  // /CF.framework, the dSYM's DWARF file may not have the `.framework`
+  // suffix (e.g. /CF.framework.dSYM/Contents/Resources/DWARF/CF).
+  // Given that `dsym_file` already will look like
+  // `/CF.framework.dSYM/Contents/Resources/DWARF/CF.framework` we an
+  // just drop the last `.framework` and check again.
+  if (filename.endswith(".framework")) {
+    const auto last_dot = dsym_file.find_last_of('.');
+    if (last_dot != llvm::StringRef::npos) {
+      dsym_file.truncate(last_dot - 1); // last_dot - 1 to include the dot
+      if (FileSystem::Instance().Exists(dsym_file)) {
+        dsym_fspec.SetFile(dsym_file, path_style);
+        if (FileAtPathContainsArchAndUUID(dsym_fspec,
                                           mod_spec.GetArchitecturePtr(),
                                           mod_spec.GetUUIDPtr())) {
           return true;
         }
       }
     }
+  }
 
   // See if we have a .dSYM.yaa next to this executable path.
-  FileSpec dsym_yaa_fspec = exec_fspec;
-  dsym_yaa_fspec.RemoveLastPathComponent();
-  std::string dsym_yaa_filename = filename.AsCString();
-  dsym_yaa_filename += ".dSYM.yaa";
-  dsym_yaa_fspec.AppendPathComponent(dsym_yaa_filename);
-
-  if (FileSystem::Instance().Exists(dsym_yaa_fspec)) {
+  dsym_file = executable_path;
+  dsym_file.append(".dSYM.yaa");
+  if (FileSystem::Instance().Exists(dsym_file)) {
     ModuleSpec mutable_mod_spec = mod_spec;
     Status error;
     if (Symbols::DownloadObjectAndSymbolFile(mutable_mod_spec, error, true) &&
         FileSystem::Instance().Exists(mutable_mod_spec.GetSymbolFileSpec())) {
       dsym_fspec = mutable_mod_spec.GetSymbolFileSpec();
       return true;
     }
   }

 //
 // If there is a .dSYM.yaa compressed archive found next to the binary,
 // we'll call DownloadObjectAndSymbolFile to expand it into a plain .dSYM
 
 static bool LocateDSYMInVincinityOfExecutable(const ModuleSpec &module_spec,
                                               FileSpec &dsym_fspec) {
   Log *log = GetLog(LLDBLog::Host);
   const FileSpec &exec_fspec = module_spec.GetFileSpec();
-  if (exec_fspec) {
-    if (::LookForDsymNextToExecutablePath(module_spec, exec_fspec,
-                                          dsym_fspec)) {
-      if (log) {
-        LLDB_LOGF(log, "dSYM with matching UUID & arch found at %s",
-                  dsym_fspec.GetPath().c_str());
-      }
-      return true;
-    } else {
-      FileSpec parent_dirs = exec_fspec;
-
-      // Remove the binary name from the FileSpec
-      parent_dirs.RemoveLastPathComponent();
+  if (!exec_fspec)
+    return false;
+
+  const llvm::sys::path::Style path_style = exec_fspec.GetPathStyle();
+  llvm::SmallString<64> executable_path;
+  exec_fspec.GetPath(executable_path, /* denormalize = */ false);
+  if (LookForDsymNextToExecutablePath(module_spec, executable_path.str(),
+                                      path_style, dsym_fspec)) {
+  }
 
-      // Add a ".dSYM" name to each directory component of the path,
-      // stripping off components.  e.g. we may have a binary like
-      // /S/L/F/Foundation.framework/Versions/A/Foundation and
-      // /S/L/F/Foundation.framework.dSYM
-      //
-      // so we'll need to start with
-      // /S/L/F/Foundation.framework/Versions/A, add the .dSYM part to the
-      // "A", and if that doesn't exist, strip off the "A" and try it again
-      // with "Versions", etc., until we find a dSYM bundle or we've
-      // stripped off enough path components that there's no need to
-      // continue.
-
-      for (int i = 0; i < 4; i++) {
-        // Does this part of the path have a "." character - could it be a
-        // bundle's top level directory?
-        const char *fn = parent_dirs.GetFilename().AsCString();
-        if (fn == nullptr)
-          break;
-        if (::strchr(fn, '.') != nullptr) {
-          if (::LookForDsymNextToExecutablePath(module_spec, parent_dirs,
-                                                dsym_fspec)) {
-            if (log) {
-              LLDB_LOGF(log, "dSYM with matching UUID & arch found at %s",
-                        dsym_fspec.GetPath().c_str());
-            }
-            return true;
-          }
-        }
-        parent_dirs.RemoveLastPathComponent();
-      }
-    }
-  }
+  // We may be in a framework bundle, in which case we want to look a few
+  // directories up for the dSYM, e.g. we may have a binary like
+  // /S/L/F/Foundation.framework/Versions/A/Foundation and the dSYM may be
+  // /S/L/F/Foundation.framework.dSYM/
+  llvm::StringRef parent_path = executable_path.str();
+  constexpr uint8_t num_parent_paths_to_check = 4;
+  for (uint8_t i = 0; i < num_parent_paths_to_check; i++) {
+    if (!llvm::sys::path::has_parent_path(parent_path, path_style))
+    parent_path = llvm::sys::path::parent_path(parent_path, path_style);
+    llvm::StringRef filename =
+        llvm::sys::path::filename(parent_path, path_style);
+    // If we're in a framework bundle and the filename doesn't have a '.' in it,
+    // we need to continue going up until we find it. We don't want to stop at
+    // `/S/L/F/Foundation.framework/Versions`, the dSYM is probably not there.
+    if (filename.find('.') == llvm::StringRef::npos)
+      continue;
+
+    if (LookForDsymNextToExecutablePath(module_spec, parent_path, path_style,
+
   dsym_fspec.Clear();
   return false;
 }
 
 static FileSpec LocateExecutableSymbolFileDsym(const ModuleSpec &module_spec) {
   const FileSpec *exec_fspec = module_spec.GetFileSpecPtr();
   const ArchSpec *arch = module_spec.GetArchitecturePtr();
   const UUID *uuid = module_spec.GetUUIDPtr();
ModuleSpec Symbols::LocateExecutableObjectFile(const ModuleSpec &module_spec) {
   return result;
 }
 
 // Keep "symbols.enable-external-lookup" description in sync with this function.
 
 FileSpec
 Symbols::LocateExecutableSymbolFile(const ModuleSpec &module_spec,
                                     const FileSpecList &default_search_paths) {
-  FileSpec symbol_file_spec = module_spec.GetSymbolFileSpec();
+  const FileSpec &symbol_file_spec = module_spec.GetSymbolFileSpec();
   if (symbol_file_spec.IsAbsolute() &&
       FileSystem::Instance().Exists(symbol_file_spec))
     return symbol_file_spec;
 
   Progress progress(llvm::formatv(
       "Locating external symbol file for {0}",
       module_spec.GetFileSpec().GetFilename().AsCString("<Unknown>")));
 
   FileSpecList debug_file_search_paths = default_search_paths;
 
-  // Add module directory.
   FileSpec module_file_spec = module_spec.GetFileSpec();
   // We keep the unresolved pathname if it fails.
   FileSystem::Instance().ResolveSymbolicLink(module_file_spec,
                                              module_file_spec);
 
   ConstString file_dir = module_file_spec.GetDirectory();
+  // Add module directory.
   {
     FileSpec file_spec(file_dir.AsCString("."));
-    FileSystem::Instance().Resolve(file_spec);
     debug_file_search_paths.AppendIfUnique(file_spec);
   }
 
   if (ModuleList::GetGlobalModuleListProperties().GetEnableExternalLookup()) {
 
     // Add current working directory.
     {
       FileSpec file_spec(".");
-      FileSystem::Instance().Resolve(file_spec);
       debug_file_search_paths.AppendIfUnique(file_spec);
     }
 
 #ifndef _WIN32
 #if defined(__NetBSD__)
     // Add /usr/libdata/debug directory.
     {
       FileSpec file_spec("/usr/libdata/debug");
-      FileSystem::Instance().Resolve(file_spec);
       debug_file_search_paths.AppendIfUnique(file_spec);
     }
 #else
     // Add /usr/lib/debug directory.
     {
       FileSpec file_spec("/usr/lib/debug");
-      FileSystem::Instance().Resolve(file_spec);
       debug_file_search_paths.AppendIfUnique(file_spec);
     }
 #endif
 #endif // _WIN32
   }
 
   std::string uuid_str;
   const UUID &module_uuid = module_spec.GetUUID();