[LLD][ELF] Support --[no-]mmap-output-file with F_no_mmap

[terrelln]

Summary

Add a flag F_no_mmap to FileOutputBuffer to support
--[no-]mmap-output-file in ELF LLD. LLD currently explicitly ignores
this flag for compatibility with GNU ld and gold.

We need this flag to speed up link time for large binaries in certain
scenarios. When we link some of our larger binaries we find that LLD
takes 50+ GB of memory, which causes memory pressure. The memory
pressure causes the VM to flush dirty pages of the output file to disk.
This is normally okay, since we should be flushing cold pages. However,
when using BtrFS with compression we need to write 128KB at a time when
we flush a page. If any page in that 128KB block is written again, then
it must be flushed a second time, and so on. Since LLD doesn't write
sequentially this causes write amplification. The same 128KB block will
end up being flushed multiple times, causing the linker to many times
more IO than necessary. We've observed 3-5x faster builds with
-no-mmap-output-file when we hit this scenario.

The bad scenario only applies to compressed filesystems, which group
together multiple pages into a single compressed block. I've tested
BtrFS, but the problem will be present for any compressed filesystem
on Linux, since it is caused by the VM.

Silently ignoring --no-mmap-output-file caused a silent regression when
we switched from gold to lld. We pass --no-mmap-output-file to fix this
edge case, but since lld silently ignored the flag we didn't realize it
wasn't being respected.

Test Plan:

ninja check-llvm
ninja check-lld

Benchmark building a 9 GB binary that exposes this edge case. I linked 3
times with --mmap-output-file and 3 times with --no-mmap-output-file and
took the average. The machine has 24 cores @ 2.4 GHz, 112 GB of RAM,
BtrFS mounted with -compress-force=zstd, and an 80% full disk.

Mode	Time
mmap	894 s
no mmap	126 s

When compression is disabled, BtrFS performs just as well with and
without mmap on this benchmark.

I was unable to reproduce the regression with any binaries in
lld-speed-test.

[MaskRay]

I don't know btrfs well but my current understanding is that there is a trade-off between compression rates and performance.

--no-mmap-output-file is supported though currently ignored, so filling in its functionality seems fine. I've got some suggestions and questions about the description.

Add support for -[no-]mmap-output-file to ELF. LLD currently explicitly ignores this flag for compatibility with the GNU linker.

GNU linker*s*, or more explicitly, GNU ld and gold.

However, when BtrFS compression is enabled, BtrFS writes 128KB blocks. Since LLD doesn't write the output file sequentially, this causes massive write and compression amplification.

Do the flushes of random accessed dirty pages make it slow under memory pressure?

FileOutputBuffer::F_in_memory

FileOutputBuffer does no have this mode. Do you have another patch that has not been sent?

-compress-force=zstd

What is compression is turned off? Have you measured the performance differences with and without --no-mmap-output-file? I think I have asked too much, but if you have access to some ext4/XFS/ZFS machines, the numbers will be useful... CentOS has defaulted to XFS and ext4 is the most widely used fs on Linux.

lld/test/ELF/mmap-output-file.s

4 ↗

(On Diff #225990)

Just check the output is the same.

llvm-mc -filetype=obj -triple=x86-unknown-linux /dev/null -o %t.o
ld.lld %t.o -o %t
ld.lld --no-mmap-output-file %t.o -o %t1
cmp %t %t1
ld.lld --mmap-output-file %t.o -o %t2
cmp %t %t2

[ruiu]

I should have reviewed this one first, sorry. I'm a little sad that BtrFS behaves poorly under a certain condition, and I feel like the filesystem is at fault than the linker, but I'm fine with actually supporting -no-mmap-output-file option as a workaround. That's practical and easy to implement.

lld/ELF/Config.h

203

Sort asciibetically.

lld/ELF/Options.td

414

Map -> Mmap

415

map -> mmap

[terrelln]

I'll update the description to answer questions, and make the requested changes. I've also answered questions inline below.

I'm a little sad that BtrFS behaves poorly under a certain condition, and I feel like the filesystem is at fault than the linker

I'd say it is a combination of the linker and BtrFS causing the problem. With compression enabled, BtrFS has to write 128 KB at a time. When there is memory pressure, because the linker uses ~50 GB of memory, the kernel is forced to flush the page cache, so BtrFS is forced to do a write. I suspect you'd see the same problem on any compressed filesystem when under memory pressure. Reducing the memory footprint of the linker would also alleviate the problem.

It is possible the kernel page eviction algorithm could be improved if it knew the "block size" of the filesystem, and I've asked our BtrFS folks if they see a way this case can be improved.

Do the flushes of random accessed dirty pages make it slow under memory pressure?

Yeah, BtrFS is forced to flush the dirty pages, but it has to write 128 KB at a time. This drastically slows down non-sequential write patterns since the same 128 KB block is written multiple times.

FileOutputBuffer::F_in_memory

Thats the parent diff D69293

What is compression is turned off? Have you measured the performance differences with and without --no-mmap-output-file? I think I have asked too much, but if you have access to some ext4/XFS/ZFS machines, the numbers will be useful... CentOS has defaulted to XFS and ext4 is the most widely used fs on Linux.

When compression is disabled I don't see the same problem, and I don't expect to see it on other filesystems (without compression enabled). The reason is we don't see as much write amplification. When compression is disabled flushing a 4 KB page only writes 4 KB. And, the kernel should only flush colder pages, so the write amplification should be minimized. But, maybe the kernel isn't as smart about flushing a cold 4 KB page in a warm 128 KB range.

[MaskRay]

Can you try posix_fallocate(fd, 0, len) and see how it performs under memory pressure with btrfs+compression?

[terrelln]

Can you try posix_fallocate(fd, 0, len) and see how it performs under memory pressure with btrfs+compression?

I see the same behavior, which is expected, since we'll still see the write amplification.

[terrelln]

• Merge D69293 into this diff.
• Fix all comments.

[ruiu]

LGTM

lld/ELF/Writer.cpp

2598–2600

nit: can you replace this = with |= for consistency?

[MaskRay]

lld/test/ELF/mmap-output-file.s

5 ↗

(On Diff #226369)

Prefer --m in tests. Due to the way the parser works, -m emulation is not considered, but we don't want users to use -mmap-output-file

[terrelln]

Fix comments

[smeenai]

Will you need someone to commit this for you?

[terrelln]

@smeenai yeah I will

[MaskRay]

-[no-]mmap-output-file

Please also change the title to use the double-dashed form.

lld/test/ELF/mmap-output-file.s

3 ↗

(On Diff #226466)

Just use x86_64. This is not Linux specific.

[terrelln]

Use triple x86_64 in tests.

[ruiu]

Feel free to submit.

[smeenai]

I can commit this for you tomorrow if one of your reviewers hasn't gotten to it by then.

[MaskRay]

@smeenai I just tried

curl -L 'https://reviews.llvm.org/D69294?download=true' | patch -p1; git commit -m 'Differential Revision: https://reviews.llvm.org/D69294'; arc amend

:)

The nice thing with git is that %an and %ae (author name and email) will be just correct. The old Patch by Name svn way does not give enough attribution to the author :(

lld/ELF/Config.h

struct Configuration {
   bool hasDynSymTab;
   bool ignoreDataAddressEquality;
   bool ignoreFunctionAddressEquality;
   bool ltoCSProfileGenerate;
   bool ltoDebugPassManager;
   bool ltoNewPassManager;
   bool mergeArmExidx;
   bool mipsN32Abi = false;
+  bool mmapOutputFile;
   bool nmagic;
   bool noinhibitExec;
   bool nostdlib;
   bool oFormatBinary;
   bool omagic;
   bool optRemarksWithHotness;
   bool pacPlt;
   bool picThunk;
struct Configuration {
   bool undefinedVersion;
   bool useAndroidRelrTags = false;
   bool warnBackrefs;
   bool warnCommon;
   bool warnIfuncTextrel;
   bool warnMissingEntry;
   bool warnSymbolOrdering;
   bool writeAddends;
   bool zCombreloc;
   bool zCopyreloc;
   bool zExecstack;
   bool zGlobal;
   bool zHazardplt;
   bool zIfuncNoplt;
   bool zInitfirst;
   bool zInterpose;
   bool zKeepTextSectionPrefix;

lld/ELF/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->ltoo = args::getInteger(args, OPT_lto_O, 2);
   config->ltoObjPath = args.getLastArgValue(OPT_lto_obj_path_eq);
   config->ltoPartitions = args::getInteger(args, OPT_lto_partitions, 1);
   config->ltoSampleProfile = args.getLastArgValue(OPT_lto_sample_profile);
   config->mapFile = args.getLastArgValue(OPT_Map);
   config->mipsGotSize = args::getInteger(args, OPT_mips_got_size, 0xfff0);
   config->mergeArmExidx =
       args.hasFlag(OPT_merge_exidx_entries, OPT_no_merge_exidx_entries, true);
+  config->mmapOutputFile =
+      args.hasFlag(OPT_mmap_output_file, OPT_no_mmap_output_file, true);
   config->nmagic = args.hasFlag(OPT_nmagic, OPT_no_nmagic, false);
   config->noinhibitExec = args.hasArg(OPT_noinhibit_exec);
   config->nostdlib = args.hasArg(OPT_nostdlib);
   config->oFormatBinary = isOutputFormatBinary(args);
   config->omagic = args.hasFlag(OPT_omagic, OPT_no_omagic, false);
   config->optRemarksFilename = args.getLastArgValue(OPT_opt_remarks_filename);
   config->optRemarksPasses = args.getLastArgValue(OPT_opt_remarks_passes);
   config->optRemarksWithHotness = args.hasArg(OPT_opt_remarks_with_hotness);

lld/ELF/Options.td

 def m: JoinedOrSeparate<["-"], "m">, HelpText<"Set target emulation">;
 
 defm Map: Eq<"Map", "Print a link map to the specified file">;
 
 defm merge_exidx_entries: B<"merge-exidx-entries",
     "Enable merging .ARM.exidx entries (default)",
     "Disable merging .ARM.exidx entries">;
 
+defm mmap_output_file: B<"mmap-output-file",
+    "Mmap the output file for writing (default)",
+    "Do not mmap the output file for writing">;
+
 def nmagic: F<"nmagic">, MetaVarName<"<magic>">,
   HelpText<"Do not page align sections, link against static libraries.">;
 
 def nostdlib: F<"nostdlib">,
   HelpText<"Only search directories specified on the command line">;
 
 def no_color_diagnostics: F<"no-color-diagnostics">,
   HelpText<"Do not use colors in diagnostics">;
defm warn_ifunc_textrel: B<"warn-ifunc-textrel",
     "Warn about using ifunc symbols with text relocations",
     "Do not warn about using ifunc symbols with text relocations (default)">;
 
 defm warn_symbol_ordering: B<"warn-symbol-ordering",
     "Warn about problems with the symbol ordering file (default)",
     "Do not warn about problems with the symbol ordering file">;
 
 def warn_unresolved_symbols: F<"warn-unresolved-symbols">,
   HelpText<"Report unresolved symbols as warnings">;
 
 defm whole_archive: B<"whole-archive",
     "Force load of all members in a static library",
     "Do not force load of all members in a static library (default)">;
 
 defm wrap: Eq<"wrap", "Use wrapper functions for symbol">,
   MetaVarName<"<symbol>=<symbol>">;
 
 def z: JoinedOrSeparate<["-"], "z">, MetaVarName<"<option>">,

 // Options listed below are silently ignored for now for compatibility.
 def: F<"detect-odr-violations">;
 def: Flag<["-"], "g">;
 def: F<"long-plt">;
 def: F<"no-add-needed">;
 def: F<"no-copy-dt-needed-entries">;
 def: F<"no-ctors-in-init-array">;
 def: F<"no-keep-memory">;
-def: F<"no-mmap-output-file">;
 def: F<"no-pipeline-knowledge">;
 def: F<"no-warn-mismatch">;
 def: Flag<["-"], "p">;
 def: Separate<["--", "-"], "rpath-link">;
 def: J<"rpath-link=">;
 def: F<"secure-plt">;
 def: F<"sort-common">;
 def: F<"stats">;

lld/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::openFile() {
   if (fileSize != size_t(fileSize) || maxSize < fileSize) {
     error("output file too large: " + Twine(fileSize) + " bytes");
     return;
   }
 
   unlinkAsync(config->outputFile);
   unsigned flags = 0;
   if (!config->relocatable)
-    flags = FileOutputBuffer::F_executable;
+    flags |= FileOutputBuffer::F_executable;
+  if (!config->mmapOutputFile)
+    flags |= FileOutputBuffer::F_no_mmap;
   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
       FileOutputBuffer::create(config->outputFile, fileSize, flags);
 
   if (!bufferOrErr) {
     error("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
     return;
   }

lld/test/ELF/silent-ignore.test

 RUN: ld.lld --version \
 RUN:   -detect-odr-violations \
 RUN:   -g \
 RUN:   -long-plt \
 RUN:   -no-add-needed \
 RUN:   -no-copy-dt-needed-entries \
 RUN:   -no-ctors-in-init-array \
 RUN:   -no-keep-memory \
-RUN:   -no-mmap-output-file \
 RUN:   -no-pipeline-knowledge \
 RUN:   -no-warn-mismatch \
 RUN:   -p \
 RUN:   -rpath-link . \
 RUN:   -secure-plt \
 RUN:   -sort-common \
 RUN:   -stats \
 RUN:   -warn-execstack \
 RUN:   -warn-once \
 RUN:   -warn-shared-textrel \
 RUN:   -EB \
 RUN:   -EL \
 RUN:   -G 0 \
 RUN:   -Qy
 RUN: not ld.lld --version --not-an-ignored-argument

llvm/include/llvm/Support/FileOutputBuffer.h

 /// If the FileOutputBuffer is committed, the target file's content will become
 /// the buffer content at the time of the commit.  If the FileOutputBuffer is
 /// not committed, the file will be deleted in the FileOutputBuffer destructor.
 class FileOutputBuffer {
 public:
   enum {
     /// set the 'x' bit on the resulting file
     F_executable = 1,
+
+    /// Don't use mmap and instead write an in-memory buffer to a file when this
+    /// buffer is closed.
+    F_no_mmap = 2,
   };
 
   /// Factory method to create an OutputBuffer object which manages a read/write
   /// buffer of the specified size. When committed, the buffer will be written
   /// to the file at the specified path.
   ///
   /// When F_modify is specified and \p FilePath refers to an existing on-disk
   /// file \p Size may be set to -1, in which case the entire file is used.

llvm/lib/Support/FileOutputBuffer.cpp

FileOutputBuffer::create(StringRef Path, size_t Size, unsigned Flags) {
   // file.) If that's the case, we create an in-memory buffer, open the
   // destination file and write to it on commit().
   switch (Stat.type()) {
   case fs::file_type::directory_file:
     return errorCodeToError(errc::is_a_directory);
   case fs::file_type::regular_file:
   case fs::file_type::file_not_found:
   case fs::file_type::status_error:
+    if (Flags & F_no_mmap)
+      return createInMemoryBuffer(Path, Size, Mode);
+    else
       return createOnDiskBuffer(Path, Size, Mode);
   default:
     return createInMemoryBuffer(Path, Size, Mode);
   }
 }

llvm/unittests/Support/FileOutputBufferTest.cpp

TEST(FileOutputBuffer, Test) {
   }
   // Verify file exists and is executable.
   fs::file_status Status;
   ASSERT_NO_ERROR(fs::status(Twine(File4), Status));
   bool IsExecutable = (Status.permissions() & fs::owner_exe);
   EXPECT_TRUE(IsExecutable);
   ASSERT_NO_ERROR(fs::remove(File4.str()));
 
+  // TEST 5: In-memory buffer works as expected.
+  SmallString<128> File5(TestDirectory);
+  File5.append("/file5");
+  {
+    Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
+        FileOutputBuffer::create(File5, 8000, FileOutputBuffer::F_no_mmap);
+    ASSERT_NO_ERROR(errorToErrorCode(BufferOrErr.takeError()));
+    std::unique_ptr<FileOutputBuffer> &Buffer = *BufferOrErr;
+    // Start buffer with special header.
+    memcpy(Buffer->getBufferStart(), "AABBCCDDEEFFGGHHIIJJ", 20);
+    ASSERT_NO_ERROR(errorToErrorCode(Buffer->commit()));
+    // Write to end of buffer to verify it is writable.
+    memcpy(Buffer->getBufferEnd() - 20, "AABBCCDDEEFFGGHHIIJJ", 20);
+    // Commit buffer.
+    ASSERT_NO_ERROR(errorToErrorCode(Buffer->commit()));
+  }
+
+  // Verify file is correct size.
+  uint64_t File5Size;
+  ASSERT_NO_ERROR(fs::file_size(Twine(File5), File5Size));
+  ASSERT_EQ(File5Size, 8000ULL);
+  ASSERT_NO_ERROR(fs::remove(File5.str()));
   // Clean up.
   ASSERT_NO_ERROR(fs::remove(TestDirectory.str()));
 }
 } // anonymous namespace