[lldb][TypeSystem] ForEach: Don't hold the TypeSystemMap lock across callback

[Michael137]

Summary

The TypeSystemMap::m_mutex guards against concurrent modifications
of members of TypeSystemMap. In particular, m_map.

TypeSystemMap::ForEach iterates through the entire m_map calling
a user-specified callback for each entry. This is all done while
m_mutex is locked. However, there's nothing that guarantees that
the callback itself won't call back into TypeSystemMap APIs on the
same thread. This lead to double-locking m_mutex, which is undefined
behaviour. We've seen this cause a deadlock in the swift plugin with
following backtrace:

int main() {
    std::unique_ptr<int> up = std::make_unique<int>(5);

    volatile int val = *up;
    return val;
}

clang++ -std=c++2a -g -O1 main.cpp

./bin/lldb -o “br se -p return” -o run -o “v *up” -o “expr *up” -b

frame #4: std::lock_guard<std::mutex>::lock_guard
frame #5: lldb_private::TypeSystemMap::GetTypeSystemForLanguage <<<< Lock #2
frame #6: lldb_private::TypeSystemMap::GetTypeSystemForLanguage
frame #7: lldb_private::Target::GetScratchTypeSystemForLanguage
...
frame #26: lldb_private::SwiftASTContext::LoadLibraryUsingPaths
frame #27: lldb_private::SwiftASTContext::LoadModule
frame #30: swift::ModuleDecl::collectLinkLibraries
frame #31: lldb_private::SwiftASTContext::LoadModule
frame #34: lldb_private::SwiftASTContext::GetCompileUnitImportsImpl
frame #35: lldb_private::SwiftASTContext::PerformCompileUnitImports
frame #36: lldb_private::TypeSystemSwiftTypeRefForExpressions::GetSwiftASTContext
frame #37: lldb_private::TypeSystemSwiftTypeRefForExpressions::GetPersistentExpressionState
frame #38: lldb_private::Target::GetPersistentSymbol
frame #41: lldb_private::TypeSystemMap::ForEach                 <<<< Lock #1
frame #42: lldb_private::Target::GetPersistentSymbol
frame #43: lldb_private::IRExecutionUnit::FindInUserDefinedSymbols
frame #44: lldb_private::IRExecutionUnit::FindSymbol
frame #45: lldb_private::IRExecutionUnit::MemoryManager::GetSymbolAddressAndPresence
frame #46: lldb_private::IRExecutionUnit::MemoryManager::findSymbol
frame #47: non-virtual thunk to lldb_private::IRExecutionUnit::MemoryManager::findSymbol
frame #48: llvm::LinkingSymbolResolver::findSymbol
frame #49: llvm::LegacyJITSymbolResolver::lookup
frame #50: llvm::RuntimeDyldImpl::resolveExternalSymbols
frame #51: llvm::RuntimeDyldImpl::resolveRelocations
frame #52: llvm::MCJIT::finalizeLoadedModules
frame #53: llvm::MCJIT::finalizeObject
frame #54: lldb_private::IRExecutionUnit::ReportAllocations
frame #55: lldb_private::IRExecutionUnit::GetRunnableInfo
frame #56: lldb_private::ClangExpressionParser::PrepareForExecution
frame #57: lldb_private::ClangUserExpression::TryParse
frame #58: lldb_private::ClangUserExpression::Parse

Our solution is to simply iterate over a local copy of m_map.

Testing

• Confirmed on manual reproducer (would reproduce 100% of the time before the patch)

[Michael137]

• Add back change dropped in cherry-pick

[aprantl]

Do we have other ForEach methods that contain a similar footgun?

[Michael137]

In D149949#4322221, @aprantl wrote:

Do we have other ForEach methods that contain a similar footgun?

Not that I can tell

[labath]

Just as a drive-by, since we're constructing a copy anyway it would be possible to merge this construction with the "uniqueing" behavior of the visited set. I.e., instead of making a literal copy of the map, just construct a to_be_visited set of /unique/ objects, and then iterate over that.

[Michael137]

In D149949#4341608, @labath wrote:

Just as a drive-by, since we're constructing a copy anyway it would be possible to merge this construction with the "uniqueing" behavior of the visited set. I.e., instead of making a literal copy of the map, just construct a to_be_visited set of /unique/ objects, and then iterate over that.

Agreed that would be a nice cleanup. I considered it initially but thought I'd split it out into a separate patch (but never did)

lldb/source/Symbol/TypeSystem.cpp

map.clear();
     std::lock_guard<std::mutex> guard(m_mutex);
     m_map.clear();
     m_clear_in_progress = false;
   }
 }
 
 void TypeSystemMap::ForEach(
     std::function<bool(lldb::TypeSystemSP)> const &callback) {
+
+  // The callback may call into this function again causing
+  // us to lock m_mutex twice if we held it across the callback.
+  // Since we just care about guarding access to 'm_map', make
+  // a local copy and iterate over that instead.
+  collection map_snapshot;
+  {
       std::lock_guard<std::mutex> guard(m_mutex);
+      map_snapshot = m_map;
+  }
+
   // Use a std::set so we only call the callback once for each unique
   // TypeSystem instance.
   llvm::DenseSet<TypeSystem *> visited;
-  for (auto &pair : m_map) {
+  for (auto &pair : map_snapshot) {
     TypeSystem *type_system = pair.second.get();
     if (!type_system || visited.count(type_system))
       continue;
     visited.insert(type_system);
     assert(type_system);
     if (!callback(pair.second))
       break;
   }