MachProcess::GetLibrariesInfoForAddresses is quadratic in the number of loaded images

[saagarjha]

When debugging, loading a new image will cause the dyld debugger notifier breakpoint that LLDB sets up to be hit. This gives a chance for the debugger to be informed about the new image that just got loaded. To find out what it is, it calls through a sequence of functions that eventually sends a jGetLoadedDynamicLibrariesInfos packet to debugserver with the solib address that was just added. When debugserver receives this it calls GetAllLoadedBinariesViaDYLDSPI which calls a very slow function in the DYLD private framework to iterate all loaded images. Unfortunately this behavior is quadratic in the number of images loaded: as each new image is brought in, the list is regenerated with the new library. When debugging code that loads many libraries in sequence this can cause debugging sessions to hang for long periods of time as debugserver catches up. There has to be a better/faster way to do this.

[llvmbot]

@llvm/issue-subscribers-lldb

Author: Saagar Jha (saagarjha)

When debugging, loading a new image will cause the dyld debugger notifier breakpoint that LLDB sets up to be hit. This gives a chance for the debugger to be informed about the new image that just got loaded. To find out what it is, it calls through [a](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/source/Plugins/DynamicLoader/MacOSX-DYLD/DynamicLoaderMacOS.cpp#L357 ) [sequence](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/source/Plugins/DynamicLoader/MacOSX-DYLD/DynamicLoaderMacOS.cpp#L419 ) [of](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp#L4094 ) [functions](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp#L4121 ) that eventually sends a [jGetLoadedDynamicLibrariesInfos](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/docs/resources/lldbgdbremote.md?plain=1#L138) packet to debugserver with the solib address that was just added. When debugserver receives this [it calls `GetAllLoadedBinariesViaDYLDSPI`](https://github.com/llvm/llvm-project/blob/cecde430093ae24c0a544929bc5a23cc61d3a5f2/lldb/tools/debugserver/source/MacOSX/MachProcess.mm#L1142C3-L1142C33) which calls a very slow function in the DYLD private framework to iterate all loaded images. Unfortunately this behavior is quadratic in the number of images loaded: as each new image is brought in, the list is regenerated with the new library. When debugging code that loads many libraries in sequence this can cause debugging sessions to hang for long periods of time as debugserver catches up. There has to be a better/faster way to do this.