[ELF][LTO] Call madvise(MADV_DONTNEED) on MemoryBuffer instances

[MaskRay]

Summary

@tejohnson noticed that freeing MemoryBuffer instances right before
lto->compile can save RSS, likely because the memory can be reused by
LTO indexing (e.g. ThinLTO import/export lists).).

For ELFFileBase instances, symbol and section names are backed by MemoryBuffer,
so destroying MemoryBuffer would make some infrequent passes (parseSymbolVersion,
reportBackrefs) crash and make debugging difficult.
For a BitcodeFile, its content is completely unused, but destroying its
MemoryBuffer makes the buffer identifier inaccessible and may introduce
constraints for future changes.
This patch leverages madvise(MADV_DONTNEED) which achieves the major gain
without the latent issues.

Maximum resident set size (kbytes): for a large --thinlto-index-only link:

• current behavior: 10146104KiB
• destroy MemoryBuffer instances: 8555240KiB
• madvise(MADV_DONTNEED) just bitcodeFiles and lazyBitcodeFiles: 8737372KiB
• madvise(MADV_DONTNEED) all MemoryBuffers: 8739796KiB

Depends on D116366

[MaskRay]

This can be used by in-process LTO. I haven't tested it yet.

[tejohnson]

In D116367#3212369, @MaskRay wrote:

This can be used by in-process LTO. I haven't tested it yet.

Would it be better to try unconditionally marking all/only the bitcode file memory buffers as MADV_DONTNEED?

For the large thin link this change is very close to the same peak RSS reduction as with my change to destroy the buffer objects completely:
Head: 10.7G
Destroy: 8.9G
Don'tNeed: 9.1G

However, when I tried my earlier version which unconditionally freed all the memory buffers, I found that the memory buffer name is used when creating the output indices, which I fixed by saving the name in the InputFile object. Would not doing so with this change cause a time degradation because we will need to pull all these pages back in to get the name from the buffers?

lld/ELF/Driver.cpp

2407–2408

Comment from the second sentence onward should be moved back to the early return, as it relates to that part, or otherwise updated accordingly.

[MaskRay]

update comments

[MaskRay]

In D116367#3212805, @tejohnson wrote:

In D116367#3212369, @MaskRay wrote:

This can be used by in-process LTO. I haven't tested it yet.

Would it be better to try unconditionally marking all/only the bitcode file memory buffers as MADV_DONTNEED?

(Uploaded the previous diff before seeing your comment.)

Agree. Bitcode files can be completely MADV_DONTNEED even in non --thinlto-index-only mode.
For ELFFileBase files, their section and symbol names are used in non --thinlto-index-only mode and nearly unused in --thinlto-index-only mode.

For the large thin link this change is very close to the same peak RSS reduction as with my change to destroy the buffer objects completely:
Head: 10.7G
Destroy: 8.9G
Don'tNeed: 9.1G

However, when I tried my earlier version which unconditionally freed all the memory buffers, I found that the memory buffer name is used when creating the output indices, which I fixed by saving the name in the InputFile object. Would not doing so with this change cause a time degradation because we will need to pull all these pages back in to get the name from the buffers?

The MemoryBuffer identifier is stored separated from the buffer content, so technically there should be no issue. In my coarse estimate yesterday, I haven't found any time degradation.

I will benchmark this by running more times.

[MaskRay]

BTW: I have refactored how --start-lib is handled recently. LazyObjFile has been removed.

The --start-lib style parsing for BitcodeFile is now in BitcodeFile::parseLazy.
It still uses saver.save(sym.getName()). There are two further improvements:

• BitcodeFile::parseLazy and BitcodeFile::parse should use the same string (backed by saver) and perhaps share the symbols array as the current non-lazy and lazy ObjFile share.
• In createBitcodeSymbol, if objSym.getName() is a stable string, we can remove saver.save. This will avoid waste for symbol names, but means that a MemoryBuffer backing a BitcodeFile may still be needed in non --thinlto-index-only mode.

That said, re-reading the string table (STRTAB_BLOCK) pages for BitcodeFile instances may unlikely cause a performance difference. This is a --time-trace dump for a large --thinlto-index-only. Most time is spend in lib/LTO. ld.lld's passes take a tiny portion of total time.

164.864697 Total ExecuteLinker
163.609803 Total Link
158.919291 Total LTO
53.818647 Total ThinLink
4.384058 Total Parse input files
2.107437 Total LowerTypeTestsPass
1.245371 Total Load input files
0.304628 Total Process symbol versions
0.001661 Total Read linker script
0.000595 Total Locate library
0.00054 Total OptModule
0.000366 Total Create output files
0.000227 Total IPSCCPPass
0.00016 Total VerifierPass
0.000128 Total CalledValuePropagationPass
6.9e-05 Total WholeProgramDevirtPass
1.4e-05 Total GlobalDCEPass
9e-06 Total ModuleToPostOrderCGSCCPassAdaptor
9e-06 Total CrossDSOCFIPass
6e-06 Total PGOIndirectCallPromotion
3e-06 Total ReversePostOrderFunctionAttrsPass
2e-06 Total ModuleToFunctionPassAdaptor
2e-06 Total ModuleInlinerWrapperPass
2e-06 Total RequireAnalysisPass<llvm::GlobalsAA, llvm::Module>
1e-06 Total GlobalOptPass
1e-06 Total InferFunctionAttrsPass
1e-06 Total Annotation2MetadataPass

[MaskRay]

decrease memory for in-process LTO as well.

[tejohnson]

In D116367#3212867, @MaskRay wrote:

In D116367#3212805, @tejohnson wrote:

In D116367#3212369, @MaskRay wrote:

This can be used by in-process LTO. I haven't tested it yet.

Would it be better to try unconditionally marking all/only the bitcode file memory buffers as MADV_DONTNEED?

(Uploaded the previous diff before seeing your comment.)

Agree. Bitcode files can be completely MADV_DONTNEED even in non --thinlto-index-only mode.
For ELFFileBase files, their section and symbol names are used in non --thinlto-index-only mode and nearly unused in --thinlto-index-only mode.

For the large thin link this change is very close to the same peak RSS reduction as with my change to destroy the buffer objects completely:
Head: 10.7G
Destroy: 8.9G
Don'tNeed: 9.1G

However, when I tried my earlier version which unconditionally freed all the memory buffers, I found that the memory buffer name is used when creating the output indices, which I fixed by saving the name in the InputFile object. Would not doing so with this change cause a time degradation because we will need to pull all these pages back in to get the name from the buffers?

The MemoryBuffer identifier is stored separated from the buffer content, so technically there should be no issue. In my coarse estimate yesterday, I haven't found any time degradation.

I will benchmark this by running more times.

I tried a few times and didn't see a slowdown.

However, with the latest version to only free the bitcode files, I am seeing less memory reduction (9.3G vs 9.1G before), and also a 30-40s slowdown (maybe the DenseSet lookups?). Something could probably be done to avoid the lookups, but do you have any idea why the memory reduction would be less? Hmm, probably there are some other non-bitcode files that are being read for symbol resolution but not being used further in index only mode?

[MaskRay]

Mark lazyBitcodeFiles as well. Mark just bitcodeFiles and lazyBitcodeFiles should achieve the original saving for distributed ThinLTO usage.

While here, try to support other cases:

• When ELF object files are significant
• Or when archives are used instead of --start-lib and many archive members are not extracted

[MaskRay]

In D116367#3212997, @tejohnson wrote:

I tried a few times and didn't see a slowdown.

However, with the latest version to only free the bitcode files, I am seeing less memory reduction (9.3G vs 9.1G before), and also a 30-40s slowdown (maybe the DenseSet lookups?). Something could probably be done to avoid the lookups, but do you have any idea why the memory reduction would be less? Hmm, probably there are some other non-bitcode files that are being read for symbol resolution but not being used further in index only mode?

It was my negligence. --start-lib bitcode files may not be extracted. They reside in the lazyBitcodeFiles list. The latest diff marked them as well.
I think this is sufficient for our use case. The diff tried a bit more to support other use cases.

lld/ELF/Driver.cpp

1993

typo: passes

[tejohnson]

LGTM with a couple of comment suggestions below.

In D116367#3213058, @MaskRay wrote:

In D116367#3212997, @tejohnson wrote:

I tried a few times and didn't see a slowdown.

However, with the latest version to only free the bitcode files, I am seeing less memory reduction (9.3G vs 9.1G before), and also a 30-40s slowdown (maybe the DenseSet lookups?). Something could probably be done to avoid the lookups, but do you have any idea why the memory reduction would be less? Hmm, probably there are some other non-bitcode files that are being read for symbol resolution but not being used further in index only mode?

It was my negligence. --start-lib bitcode files may not be extracted. They reside in the lazyBitcodeFiles list. The latest diff marked them as well.
I think this is sufficient for our use case. The diff tried a bit more to support other use cases.

Confirmed that the memory savings recovered, and the time reduced too, but in my case skipLinkedOutput is true so it is not doing the dense set lookups at all.

lld/ELF/Driver.cpp

2390

Suggest making this something like "Index file creation is performed in compileBitcodeFiles, so we are done afterwards in that case." Or move this sentence below where we take the early return.

2393

"When only certain thinLTO modules are specified for compilation." isn't a complete sentence. Maybe, "This is also true when only ..." ?

lld/ELF/Driver.cpp

bool elf::link(ArrayRef<const char *> args, bool canExitEarly,
   lld::stdoutOS = &stdoutOS;
   lld::stderrOS = &stderrOS;
 
   errorHandler().cleanupCallback = []() {
     freeArena();
 
     inputSections.clear();
     outputSections.clear();
+    memoryBuffers.clear();
     archiveFiles.clear();
     binaryFiles.clear();
     bitcodeFiles.clear();
     lazyBitcodeFiles.clear();
     objectFiles.clear();
     sharedFiles.clear();
     backwardReferences.clear();
     whyExtract.clear();

 
 static Symbol *addUnusedUndefined(StringRef name,
                                   uint8_t binding = STB_GLOBAL) {
   Undefined sym{nullptr, name, binding, STV_DEFAULT, 0};
   sym.isUsedInRegularObj = false;
   return symtab->addSymbol(sym);
 }
 
+// MemoryBuffers backing BitcodeFiles are unused from now on. Mark input files
+// as MADV_DONTNEED so that these pages can be reused by the expensive thin
+// link, saving memory.
+//
+// With --thinlto-index-only, for ELFFileBase files, their MemoryBuffers are
+// nearly unused as well, but the saving is typically small because
+// in LTO links bitcode files typically dominate.
+static void markBuffersAsDontNeed() {
+  DenseSet<const char *> bufs;
+  for (BitcodeFile *file : elf::bitcodeFiles)
+    bufs.insert(file->mb.getBufferStart());
+
+  for (MemoryBuffer &mb : llvm::make_pointee_range(memoryBuffers))
+    if (bufs.count(mb.getBufferStart()))
+      mb.dontNeedIfMmap();
+}
+
 // This function is where all the optimizations of link-time
 // optimization takes place. When LTO is in use, some input files are
 // not in native object file format but in the LLVM bitcode format.
 // This function compiles bitcode files into a few big native files
 // using LLVM functions and replaces bitcode symbols with the results.
 // Because all bitcode files that the program consists of are passed to
 // the compiler at once, it can do a whole-program optimization.
 template <class ELFT> void LinkerDriver::compileBitcodeFiles() {
   llvm::TimeTraceScope timeScope("LTO");
   // Compile bitcode files and replace bitcode symbols.
   lto.reset(new BitcodeCompiler);
   for (BitcodeFile *file : bitcodeFiles)
     lto->add(*file);
 
+  if (!bitcodeFiles.empty())
+    markBuffersAsDontNeed();
+
   for (InputFile *file : lto->compile()) {
     auto *obj = cast<ObjFile<ELFT>>(file);
     obj->parse(/*ignoreComdats=*/true);
 
     // Parse '@' in symbol names for non-relocatable output.
     if (!config->relocatable)
       for (Symbol *sym : obj->getGlobalSymbols())
         if (sym->hasVersionSuffix)
template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   // name "foo@ver1") rather do harm, so we don't call this if -r is given.
   if (!config->relocatable) {
     llvm::TimeTraceScope timeScope("Process symbol versions");
     symtab->scanVersionScript();
   }
 
   // Do link-time optimization if given files are LLVM bitcode files.
   // This compiles bitcode files into real object files.
   //
   // With this the symbol table should be complete. After this, no new names
   // except a few linker-synthesized ones will be added to the symbol table.
   compileBitcodeFiles<ELFT>();
 
   // Symbol resolution finished. Report backward reference problems.
   reportBackrefs();
   if (errorCount())
     return;
 
   // If --thinlto-index-only is given, we should create only "index
   // files" and not object files. Index file creation is already done
   // in compileBitcodeFiles, so we are done if that's the case.
   // Likewise, --plugin-opt=emit-llvm and --plugin-opt=emit-asm are the
   // options to create output files in bitcode or assembly code
   // respectively. No object files are generated.
   // Also bail out here when only certain thinLTO modules are specified for
   // compilation. The intermediate object file are the expected output.
   if (config->thinLTOIndexOnly || config->emitLLVM || config->ltoEmitAsm ||
       !config->thinLTOModulesToCompile.empty())
     return;
 
   // Handle --exclude-libs again because lto.tmp may reference additional
   // libcalls symbols defined in an excluded archive. This may override
   // versionId set by scanVersionScript().
   if (args.hasArg(OPT_exclude_libs))
     excludeLibs(args);

lld/ELF/InputFiles.h

InputFile *createLazyFile(MemoryBufferRef mb, StringRef archiveName,
                           uint64_t offsetInArchive);
 
 inline bool isBitcode(MemoryBufferRef mb) {
   return identify_magic(mb.getBuffer()) == llvm::file_magic::bitcode;
 }
 
 std::string replaceThinLTOSuffix(StringRef path);
 
+extern SmallVector<std::unique_ptr<MemoryBuffer>> memoryBuffers;
 extern SmallVector<ArchiveFile *, 0> archiveFiles;
 extern SmallVector<BinaryFile *, 0> binaryFiles;
 extern SmallVector<BitcodeFile *, 0> bitcodeFiles;
 extern SmallVector<BitcodeFile *, 0> lazyBitcodeFiles;
 extern SmallVector<ELFFileBase *, 0> objectFiles;
 extern SmallVector<SharedFile *, 0> sharedFiles;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/InputFiles.cpp

 using namespace llvm::sys::fs;
 using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::elf;
 
 bool InputFile::isInGroup;
 uint32_t InputFile::nextGroupId;
 
+SmallVector<std::unique_ptr<MemoryBuffer>> elf::memoryBuffers;
 SmallVector<ArchiveFile *, 0> elf::archiveFiles;
 SmallVector<BinaryFile *, 0> elf::binaryFiles;
 SmallVector<BitcodeFile *, 0> elf::bitcodeFiles;
 SmallVector<BitcodeFile *, 0> elf::lazyBitcodeFiles;
 SmallVector<ELFFileBase *, 0> elf::objectFiles;
 SmallVector<SharedFile *, 0> elf::sharedFiles;
 
 std::unique_ptr<TarWriter> elf::tar;
Optional<MemoryBufferRef> elf::readFile(StringRef path) {
 
   auto mbOrErr = MemoryBuffer::getFile(path, /*IsText=*/false,
                                        /*RequiresNullTerminator=*/false);
   if (auto 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
+  MemoryBufferRef mbref = (*mbOrErr)->getMemBufferRef();
+  memoryBuffers.push_back(std::move(*mbOrErr)); // take MB ownership
 
   if (tar)
     tar->append(relativeToRoot(path), mbref.getBuffer());
   return mbref;
 }
 
 // All input object files must be for the same architecture
 // (e.g. it does not make sense to link x86 object files with