Remove existing file in a separate thread asynchronously.

[ruiu]

Summary

On Linux (and probably on other Unix-like systems), unlink(2) is
noticeably slow. It takes 250 milliseconds to remove a 1 GB file
on ext4 filesystem on my machine, whether the file is on SSD or
on a spinning disk.

To create a new result file, we remove existing file first. So, if
you repeatedly link a 1 GB program in a regular compile-link-debug
cycle, every cycle wastes 250 milliseconds only to remove a file.

Since LLD can link a 1 GB in about 5 seconds, that actually counts.

This patch defines unlinkAsync function. The function spawns a
background thread to call unlink. The calling thread returns
almost immediately.

[ruiu]

• Use createUniqueFile instead of createTemporaryFile to create a temporary file name in the same directory as a result file.

[ruiu]

• Do not create a thread if !Config->Threads.

[silvas]

Why are we unlinking at all? Hopefully we can just resize the file and ideally reuse most of the pages the kernel already has allocated. Doing so loses the atomicity of the replacement, but so does asynchronously unlinking like you do in this patch (although this patch would manifest the non-atomicity in a more benign way).

If we slightly overallocate the file (no problem since ELF doesn't mind having some extra zeros at the end), then most of the time re-links will avoid doing any kind of memory allocation from the kernel whatsoever. (edit-relink cycle may cause more or less bytes due to local code modifications from the edits, but the changes are unlikely to be very large).

I'm not sure if users expect atomic replacement of the destination file as the behavior from the linker. If they do, then there's not much we can do to speed this up unfortunately. Joerg, Ed? Any ideas on whether we need atomic replacement?

[joerg]

The reason for unlinking is to get consistent behavior in the error case as well as consistent access permissions.

That said, I can't reproduce the numbers on my laptop. For Ext4 on my laptop, I see around 0.1s for rm to delete a 1GB test file, tmpfs is half of that.

[ruiu]

What is your kernel and how did you create your file? Removing an 1.6 GB link result always takes about 2.5 seconds for me.

$ /ssd/rel/bin/ld.lld @response -o /ssd/out

$ ls -l /ssd/out
-rwxr-x--- 1 ruiu eng 1624892488 Dec  1 09:25 /ssd/out

$ strace -c rm /ssd/out
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 99.96    0.260674      260674         1           unlinkat
  0.01    0.000022           3         8           mmap
  0.01    0.000015           5         3           open
  0.01    0.000014           4         4           mprotect
  0.00    0.000011           2         6           close
  0.00    0.000011           4         3         3 access
  0.00    0.000010          10         1           execve
  0.00    0.000006           6         1           munmap
  0.00    0.000005           3         2           newfstatat
  0.00    0.000004           4         1         1 lseek
  0.00    0.000003           1         3           fstat
  0.00    0.000003           1         3           brk
  0.00    0.000003           3         1           faccessat
  0.00    0.000002           2         1           read
  0.00    0.000002           2         1           ioctl
  0.00    0.000001           1         1           geteuid
  0.00    0.000001           1         1           arch_prctl
------ ----------- ----------- --------- --------- ----------------
100.00    0.260787                    41         4 total

[ruiu]

As to writing to an existing file as opposed to atomic renaming, I believe the reason why we are doing that is to not leave a corrupted file in case of crash. If you do atomic renaming, you'll get a temporary file in the worst case instead of a broken, partically-written result.

However, that can be resolved by renaming an existing file different temporary name, write to the temporary file, and then rename it back. Maybe we should do that?

[joerg]

dd if=/dev/zero of=testfile bs=1024k count=1024
sync
time rm testfile

[ruiu]

dd, sync and rm are too different from real use cases.

[inglorion]

I like the idea of writing to a temporary file, then renaming that. That way, we keep the original file in place until we have a complete file to replace it with, and the replace operation should be fast and atomic on most reasonable filesystems.

Having said that, there are a few potential downsides to this approach. For one, it requires disk space to be sufficient to hold both the old and the new file. For another, some scripts or tools may depend on the output file being absent if the link did not succeed.

If we do end up implementing this "rename, then remove in a separate thread", I would suggest moving it into LLVM. It is a technique I've often found useful, particularly when deleting directories.

[silvas]

Overall, I do like the idea of doing this and this LGTM (although let others chime in). One thing to think about is that if it takes this long to delete a file (even on tmpfs which Joerg mentioned), then how long does it take to allocate the memory for a new file? (let alone write it to disk)

So there is probably a similar cost hidden somewhere else that we could maybe get rid of if we arranged things right (not in this patch though).

[ruiu]

• Call unlinkAsync just before creating a new output file, instead of at the beginning of writeResult().

I'm going to submit this patch tomorrow if there's no objections.

lld/trunk/ELF/Writer.cpp

 #include "Strings.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/FileOutputBuffer.h"
+#include "llvm/Support/FileSystem.h"
 #include "llvm/Support/raw_ostream.h"
 #include <climits>
+#include <thread>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 
 using namespace lld;
for (Phdr &P : Phdrs)
     *HBuf++ = P.H;
 
   // Write the section header table. Note that the first table entry is null.
   auto *SHdrs = reinterpret_cast<Elf_Shdr *>(Buf + EHdr->e_shoff);
   for (OutputSectionBase *Sec : OutputSections)
     Sec->writeHeaderTo<ELFT>(++SHdrs);
 }
 
+// Removes a given file asynchronously. This is a performance hack,
+// so remove this when operating systems are improved.
+//
+// On Linux (and probably on other Unix-like systems), unlink(2) is a
+// noticeably slow system call. As of 2016, unlink takes 250
+// milliseconds to remove a 1 GB file on ext4 filesystem on my machine.
+//
+// To create a new result file, we first remove existing file. So, if
+// you repeatedly link a 1 GB program in a regular compile-link-debug
+// cycle, every cycle wastes 250 milliseconds only to remove a file.
+// Since LLD can link a 1 GB binary in about 5 seconds, that waste
+// actually counts.
+//
+// This function spawns a background thread to call unlink.
+// The calling thread returns almost immediately.
+static void unlinkAsync(StringRef Path) {
+  if (!Config->Threads || !sys::fs::exists(Config->OutputFile))
+    return;
+
+  // First, rename Path to avoid race condition. We cannot remomve
+  // Path from a different thread because we are now going to create
+  // Path as a new file. If we do that in a different thread, the new
+  // thread can remove the new file.
+  SmallString<128> TempPath;
+  if (auto EC = sys::fs::createUniqueFile(Path + "tmp%%%%%%%%", TempPath))
+    fatal(EC, "createUniqueFile failed");
+  if (auto EC = sys::fs::rename(Path, TempPath))
+    fatal(EC, "rename failed");
+
+  // Remove TempPath in background.
+  std::thread([=] { ::remove(TempPath.str().str().c_str()); }).detach();
+}
+
+// Open a result file.
 template <class ELFT> void Writer<ELFT>::openFile() {
+  unlinkAsync(Config->OutputFile);
   ErrorOr<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
       FileOutputBuffer::create(Config->OutputFile, FileSize,
                                FileOutputBuffer::F_executable);
+
   if (auto EC = BufferOrErr.getError())
     error(EC, "failed to open " + Config->OutputFile);
   else
     Buffer = std::move(*BufferOrErr);
 }
 
 template <class ELFT> void Writer<ELFT>::writeSectionsBinary() {
   uint8_t *Buf = Buffer->getBufferStart();