[lld-macho] Cache readFile results

[keith]

Summary

In one of our links lld was reading 760k files, but the unique number of
files was only 1500. This takes that link from 30 seconds to 8.

This seems like a heavy hammer, especially since some things don't need
to be cached, like the filelist arguments and the passed static
archives (the latter is already cached as a one off), but it seems ld64
does something similar here to short circuit these duplicate reads:

https://github.com/keith/ld64/blob/82e429e186488529111b0ef86af33a3b1b9438c7/src/ld/InputFiles.cpp#L644-L665

Of the types of files being read for our iOS app, the biggest problem
was constantly re-reading small tbd files:

% wc -l /tmp/read.txt
761414 /tmp/read.txt
% cat /tmp/read.txt | sort -u | wc -l
1503

% cat /tmp/read.txt | grep "\.a$" | wc -l
43721
% cat /tmp/read.txt | grep "\.tbd$" | wc -l
717656

We could likely hoist this logic up to not cache at this level, but it
would be a more invasive change to make sure all callers that needed it
cached the results.

I could see this being an issue with OOMs, and I'm not a linker expert so
maybe there's another way we should solve this problem? Feedback welcome!

[int3]

I could see this being an issue with OOMs

We are pretty liberal with our memory use at the moment. E.g. we basically don't free anything until process exit, with the view that most of things we allocate live for most of the linker process' short lifetime anyway. I think we can run with this and revisit if it causes any problems in practice.

lld/MachO/InputFiles.cpp

176

Would be nice to have a comment here about how this is primarily for the caching of .tbd / common library files and is a bit of a heavy hammer (as mentioned in the commit message)

[keith]

Add comment

[smeenai]

This one needs to be reset in the cleanupCallback as well (https://github.com/llvm/llvm-project/blob/e7fdff403e849b18d93cd4a5cb760cba66a92c0b/lld/MachO/Driver.cpp#L1098), as do all the other caches you added (if they aren't already). The cache itself would technically be valid, but we free all our memory arenas at the end of a linker run, so the entries would point to freed memory.

Out of curiosity, is the link that takes 8 seconds now the same one that ld64 takes 20 seconds for? If not, I'd be curious to know how the speed for that one compares after all your changes.

Thanks for all the fixes!

[keith]

In D113153#3108083, @smeenai wrote:

This one needs to be reset in the cleanupCallback as well (https://github.com/llvm/llvm-project/blob/e7fdff403e849b18d93cd4a5cb760cba66a92c0b/lld/MachO/Driver.cpp#L1098), as do all the other caches you added (if they aren't already). The cache itself would technically be valid, but we free all our memory arenas at the end of a linker run, so the entries would point to freed memory.

Ah thanks, I wondered but should have asked. https://reviews.llvm.org/D113198

Out of curiosity, is the link that takes 8 seconds now the same one that ld64 takes 20 seconds for? If not, I'd be curious to know how the speed for that one compares after all your changes.

Yes, so for the same link our benchmarks have been:

• lld before my changes: 1 minute 45 seconds
• ld64 20s
• zld (optimized ld64 fork) ~13s
• lld with all my changes ~8s

Unfortunately the produced binary crashes on what appears to be issues with dropped Objective-C categories, I'm working on reducing a repro case, but if there are known issues around this (I couldn't find any on the bug tracker) I would love to know!

Thanks for all the fixes!

Thanks for the reviews!

[smeenai]

In D113153#3109272, @keith wrote:

Unfortunately the produced binary crashes on what appears to be issues with dropped Objective-C categories, I'm working on reducing a repro case, but if there are known issues around this (I couldn't find any on the bug tracker) I would love to know!

We haven't seen any issues like that on our end yet, as far as I'm aware. The repro will be interesting once you've got it :)

[keith]

In D113153#3109794, @smeenai wrote:

In D113153#3109272, @keith wrote:

Unfortunately the produced binary crashes on what appears to be issues with dropped Objective-C categories, I'm working on reducing a repro case, but if there are known issues around this (I couldn't find any on the bug tracker) I would love to know!

We haven't seen any issues like that on our end yet, as far as I'm aware. The repro will be interesting once you've got it :)

Filed https://bugs.llvm.org/show_bug.cgi?id=52480 with a repro!

lld/MachO/InputFiles.cpp

static bool checkCompatibility(const InputFile *input) {
   if (it->minimum > config->platformInfo.minimum)
     warn(toString(input) + " has version " + it->minimum.getAsString() +
          ", which is newer than target minimum of " +
          config->platformInfo.minimum.getAsString());
 
   return true;
 }
 
+// This cache mostly exists to store system libraries (and .tbds) as they're
+// loaded, rather than the input archives, which are already cached at a higher
+// level, and other files like the filelist that are only read once.
+// Theoretically this caching could be more efficient by hoisting it, but that
+// would require altering many callers to track the state.
+static DenseMap<CachedHashStringRef, MemoryBufferRef> resolvedReads;
 // Open a given file path and return it as a memory-mapped file.
 Optional<MemoryBufferRef> macho::readFile(StringRef path) {
+  CachedHashStringRef key(path);
+  auto entry = resolvedReads.find(key);
+  if (entry != resolvedReads.end())
+    return entry->second;
+
   ErrorOr<std::unique_ptr<MemoryBuffer>> mbOrErr = MemoryBuffer::getFile(path);
   if (std::error_code ec = mbOrErr.getError()) {
     error("cannot open " + path + ": " + ec.message());
     return None;
   }
 
   std::unique_ptr<MemoryBuffer> &mb = *mbOrErr;
   MemoryBufferRef mbref = mb->getMemBufferRef();
   make<std::unique_ptr<MemoryBuffer>>(std::move(mb)); // take mb ownership
 
   // If this is a regular non-fat file, return it.
   const char *buf = mbref.getBufferStart();
   const auto *hdr = reinterpret_cast<const fat_header *>(buf);
   if (mbref.getBufferSize() < sizeof(uint32_t) ||
       read32be(&hdr->magic) != FAT_MAGIC) {
     if (tar)
       tar->append(relativeToRoot(path), mbref.getBuffer());
-    return mbref;
+    return resolvedReads[key] = mbref;
   }
 
   // Object files and archive files may be fat files, which contain multiple
   // real files for different CPU ISAs. Here, we search for a file that matches
   // with the current link target and returns it as a MemoryBufferRef.
   const auto *arch = reinterpret_cast<const fat_arch *>(buf + sizeof(*hdr));
 
   for (uint32_t i = 0, n = read32be(&hdr->nfat_arch); i < n; ++i) {
     if (reinterpret_cast<const char *>(arch + i + 1) >
         buf + mbref.getBufferSize()) {
       error(path + ": fat_arch struct extends beyond end of file");
       return None;
     }
 
     if (read32be(&arch[i].cputype) != static_cast<uint32_t>(target->cpuType) ||
         read32be(&arch[i].cpusubtype) != target->cpuSubtype)
       continue;
 
     uint32_t offset = read32be(&arch[i].offset);
     uint32_t size = read32be(&arch[i].size);
     if (offset + size > mbref.getBufferSize())
       error(path + ": slice extends beyond end of file");
     if (tar)
       tar->append(relativeToRoot(path), mbref.getBuffer());
-    return MemoryBufferRef(StringRef(buf + offset, size), path.copy(bAlloc));
+    return resolvedReads[key] = MemoryBufferRef(StringRef(buf + offset, size),
+                                                path.copy(bAlloc));
   }
 
   error("unable to find matching architecture in " + path);
   return None;
 }
 
 InputFile::InputFile(Kind kind, const InterfaceFile &interface)
     : id(idCount++), fileKind(kind), name(saver.save(interface.getPath())) {}