[ELF][WIP] Parallelize writes of different OutputSections

[andrewng]

Summary

Potential alternative to https://reviews.llvm.org/D131247.

[andrewng]

Approach adopted in D131247.

lld/ELF/OutputSections.h

 //===- OutputSections.h -----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_OUTPUT_SECTIONS_H
 #define LLD_ELF_OUTPUT_SECTIONS_H
 
 #include "InputSection.h"
 #include "LinkerScript.h"
 #include "lld/Common/LLVM.h"
+#include "llvm/Support/Parallel.h"
 
 #include <array>
 
 namespace lld::elf {
 
 struct PhdrEntry;
 
 struct CompressedData {
public:
   // that wasn't needed). This is needed for orphan placement.
   bool hasInputSections = false;
 
   // The output section description is specified between DATA_SEGMENT_ALIGN and
   // DATA_RELRO_END.
   bool relro = false;
 
   void finalize();
-  template <class ELFT> void writeTo(uint8_t *buf);
+  template <class ELFT>
+  void writeTo(uint8_t *buf, llvm::parallel::TaskGroup &tg);
   // Check that the addends for dynamic relocations were written correctly.
   void checkDynRelAddends(const uint8_t *bufStart);
   template <class ELFT> void maybeCompress();
 
   void sort(llvm::function_ref<int(InputSectionBase *s)> order);
   void sortInitFini();
   void sortCtorsDtors();
 
 private:
+  SmallVector<InputSection *, 0> storage;
+
   // Used for implementation of --compress-debug-sections option.
   CompressedData compressed;
 
   std::array<uint8_t, 4> getFiller();
 };
 
 struct OutputDesc final : SectionCommand {
   OutputSection osec;

lld/ELF/OutputSections.cpp

#if LLVM_ENABLE_ZLIB
   if (!config->compressDebugSections || (flags & SHF_ALLOC) ||
       !name.startswith(".debug_") || size == 0)
     return;
 
   llvm::TimeTraceScope timeScope("Compress debug sections");
 
   // Write uncompressed data to a temporary zero-initialized buffer.
   auto buf = std::make_unique<uint8_t[]>(size);
-  writeTo<ELFT>(buf.get());
+  {
+    parallel::TaskGroup tg;
+    writeTo<ELFT>(buf.get(), tg);
+  }
   // We chose 1 (Z_BEST_SPEED) as the default compression level because it is
   // the fastest. If -O2 is given, we use level 6 to compress debug info more by
   // ~15%. We found that level 7 to 9 doesn't make much difference (~1% more
   // compression) while they take significant amount of time (~2x), so level 6
   // seems enough.
   const int level = config->optimize >= 2 ? 6 : Z_BEST_SPEED;
 
   // Split input into 1-MiB shards.
static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
   else if (size == 4)
     write32(buf, data);
   else if (size == 8)
     write64(buf, data);
   else
     llvm_unreachable("unsupported Size argument");
 }
 
-template <class ELFT> void OutputSection::writeTo(uint8_t *buf) {
+template <class ELFT>
+void OutputSection::writeTo(uint8_t *buf, parallel::TaskGroup &tg) {
   llvm::TimeTraceScope timeScope("Write sections", name);
   if (type == SHT_NOBITS)
     return;
 
   // If --compress-debug-section is specified and if this is a debug section,
   // we've already compressed section contents. If that's the case,
   // just write it down.
   if (compressed.shards) {
parallelFor(0, compressed.numShards, [&](size_t i) {
              compressed.shards[i].size());
     });
 
     write32be(buf + (size - sizeof(*chdr) - 4), compressed.checksum);
     return;
   }
 
   // Write leading padding.
-  SmallVector<InputSection *, 0> storage;
   ArrayRef<InputSection *> sections = getInputSections(*this, storage);
   std::array<uint8_t, 4> filler = getFiller();
   bool nonZeroFiller = read32(filler.data()) != 0;
   if (nonZeroFiller)
     fill(buf, sections.empty() ? size : sections[0]->outSecOff, filler);
 
-  parallelFor(0, sections.size(), [&](size_t i) {
+  auto fn = [=](size_t begin, size_t end) {
+    size_t numSections = sections.size();
+    for (size_t i = begin; i < end; ++i) {
       InputSection *isec = sections[i];
       if (auto *s = dyn_cast<SyntheticSection>(isec))
         s->writeTo(buf + isec->outSecOff);
       else
         isec->writeTo<ELFT>(buf + isec->outSecOff);
 
       // Fill gaps between sections.
       if (nonZeroFiller) {
         uint8_t *start = buf + isec->outSecOff + isec->getSize();
         uint8_t *end;
-      if (i + 1 == sections.size())
+        if (i + 1 == numSections)
           end = buf + size;
         else
           end = buf + sections[i + 1]->outSecOff;
         if (isec->nopFiller) {
           assert(target->nopInstrs);
           nopInstrFill(start, end - start);
         } else
           fill(start, end - start, filler);
       }
-  });
+    }
+  };
 
-  // Linker scripts may have BYTE()-family commands with which you
-  // can write arbitrary bytes to the output. Process them if any.
+  // If there is any BYTE()-family command (rare), write the section content
+  // first then process BYTE to overwrite the filler content. The write is
+  // serial due to the limitation of llvm/Support/Parallel.h.
+  bool written = false;
+  size_t numSections = sections.size();
   for (SectionCommand *cmd : commands)
-    if (auto *data = dyn_cast<ByteCommand>(cmd))
+    if (auto *data = dyn_cast<ByteCommand>(cmd)) {
+      if (!std::exchange(written, true))
+        fn(0, numSections);
       writeInt(buf + data->offset, data->expression().getValue(), data->size);
     }
+  if (written || !numSections)
+    return;
+
+  // There is no data command. Write content asynchronously to overlap the write
+  // time with other output sections. Note, if a linker script specifies
+  // overlapping output sections (needs --noinhibit-exec or --no-check-sections
+  // to supress the error), the output may be non-deterministic.
+  for (size_t begin = 0, i = 0, taskSize = 0, taskSizeLimit = 4 * 1024 * 1024;
+       ;) {
+    taskSize += sections[i]->getSize();
+    bool done = (++i == numSections);
+    if (done || taskSize >= taskSizeLimit) {
+      parallelAsyncTask(tg, [=] { fn(begin, i); });
+      if (done)
+        break;
+      begin = i;
+      taskSize = 0;
+    }
+  }
+}
 
 static void finalizeShtGroup(OutputSection *os, InputSection *section) {
   // sh_link field for SHT_GROUP sections should contain the section index of
   // the symbol table.
   os->link = in.symTab->getParent()->sectionIndex;
 
   if (!section)
     return;
void OutputSection::checkDynRelAddends(const uint8_t *bufStart) {
   });
 }
 
 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 
-template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);
+template void OutputSection::writeTo<ELF32LE>(uint8_t *,
+                                              llvm::parallel::TaskGroup &);
+template void OutputSection::writeTo<ELF32BE>(uint8_t *,
+                                              llvm::parallel::TaskGroup &);
+template void OutputSection::writeTo<ELF64LE>(uint8_t *,
+                                              llvm::parallel::TaskGroup &);
+template void OutputSection::writeTo<ELF64BE>(uint8_t *,
+                                              llvm::parallel::TaskGroup &);
 
 template void OutputSection::maybeCompress<ELF32LE>();
 template void OutputSection::maybeCompress<ELF32BE>();
 template void OutputSection::maybeCompress<ELF64LE>();
 template void OutputSection::maybeCompress<ELF64BE>();

lld/ELF/Writer.cpp

error("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
     return;
   }
   buffer = std::move(*bufferOrErr);
   Out::bufferStart = buffer->getBufferStart();
 }
 
 template <class ELFT> void Writer<ELFT>::writeSectionsBinary() {
+  parallel::TaskGroup tg;
   for (OutputSection *sec : outputSections)
     if (sec->flags & SHF_ALLOC)
-      sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
+      sec->writeTo<ELFT>(Out::bufferStart + sec->offset, tg);
 }
 
 static void fillTrap(uint8_t *i, uint8_t *end) {
   for (; i + 4 <= end; i += 4)
     memcpy(i, &target->trapInstr, 4);
 }
 
 // Fill the last page of executable segments with trap instructions
if (last && (last->p_flags & PF_X))
           alignToPowerOf2(last->p_filesz, config->maxPageSize);
   }
 }
 
 // Write section contents to a mmap'ed file.
 template <class ELFT> void Writer<ELFT>::writeSections() {
   llvm::TimeTraceScope timeScope("Write sections");
 
+  {
     // In -r or --emit-relocs mode, write the relocation sections first as in
     // ELf_Rel targets we might find out that we need to modify the relocated
     // section while doing it.
+    parallel::TaskGroup tg;
     for (OutputSection *sec : outputSections)
       if (sec->type == SHT_REL || sec->type == SHT_RELA)
-      sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
-
+        sec->writeTo<ELFT>(Out::bufferStart + sec->offset, tg);
+  }
+  {
+    parallel::TaskGroup tg;
     for (OutputSection *sec : outputSections)
       if (sec->type != SHT_REL && sec->type != SHT_RELA)
-      sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
+        sec->writeTo<ELFT>(Out::bufferStart + sec->offset, tg);
+  }
 
   // Finally, check that all dynamic relocation addends were written correctly.
   if (config->checkDynamicRelocs && config->writeAddends) {
     for (OutputSection *sec : outputSections)
       if (sec->type == SHT_REL || sec->type == SHT_RELA)
         sec->checkDynRelAddends(Out::bufferStart);
   }
 }

lld/test/ELF/arm-thumb-interwork-notfunc.s

 // REQUIRES: arm
 // RUN: llvm-mc -g --triple=armv7a-linux-gnueabihf -arm-add-build-attributes -filetype=obj -o %t.o %s
-// RUN: ld.lld %t.o -o %t 2>&1 | FileCheck %s --check-prefix=WARN
+/// Use --threads=1 to keep emitted warnings across sections sequential.
+// RUN: ld.lld %t.o -o %t --threads=1 2>&1 | FileCheck %s --check-prefix=WARN
 // RUN: llvm-objdump --no-show-raw-insn -d %t | FileCheck %s
 
 .syntax unified
 .section .arm_target, "ax", %progbits
 .balign 0x1000
 .arm
 arm_func_with_notype:
 .type arm_func_with_explicit_notype, %notype

lld/test/ELF/hexagon-jump-error.s

 # REQUIRES: hexagon
 # RUN: llvm-mc -filetype=obj -triple=hexagon-unknown-elf %s -o %t.o
-# RUN: not ld.lld %t.o -o /dev/null 2>&1 | FileCheck --implicit-check-not "out of range" %s
+## Use --threads=1 to keep emitted warnings across sections sequential.
+# RUN: not ld.lld %t.o -o /dev/null --threads=1 2>&1 | FileCheck --implicit-check-not "out of range" %s
 
   .globl  _start
   .type _start, @function
 _start:
 
 # CHECK: relocation R_HEX_B9_PCREL out of range: 1028 is not in [-1024, 1023]
 {r0 = #0; jump #1f}
 .space (1<<10)

lld/test/ELF/linkerscript/overlapping-sections.s

 # fatal error by passing --noinhibit-exec, so this behaviour is fine.
 
 # RUN: llvm-objdump -s %t.so | FileCheck %s --check-prefix BROKEN-OUTPUT-FILE
 # BROKEN-OUTPUT-FILE-LABEL: Contents of section .sec1:
 # BROKEN-OUTPUT-FILE-NEXT: 8000 01010101 01010101 01010101 01010101
 # BROKEN-OUTPUT-FILE-NEXT: 8010 01010101 01010101 01010101 01010101
 # BROKEN-OUTPUT-FILE-NEXT: 8020 01010101 01010101 01010101 01010101
 # BROKEN-OUTPUT-FILE-NEXT: 8030 01010101 01010101 01010101 01010101
-# Starting here the contents of .sec2 overwrites .sec1:
-# BROKEN-OUTPUT-FILE-NEXT: 8040 02020202 02020202 02020202 02020202
+## Starting here the content may be from either .sec1 or .sec2, depending on the write order.
+# BROKEN-OUTPUT-FILE-NEXT: 8040
 
 # RUN: llvm-readelf --sections -l %t.so | FileCheck %s -check-prefix BAD-BOTH
 # BAD-BOTH-LABEL: Section Headers:
 # BAD-BOTH: .sec1             PROGBITS        0000000000008000 002000 000100 00  WA  0   0  1
 # BAD-BOTH: .sec2             PROGBITS        0000000000008040 002040 000100 00  WA  0   0  1
 # BAD-BOTH-LABEL: Program Headers:
 # BAD-BOTH-NEXT:  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
 # BAD-BOTH-NEXT:  LOAD 0x001000 0x0000000000000000 0x0000000000000000 0x000100 0x000100 R E 0x1000

llvm/include/llvm/Support/Parallel.h

 namespace parallel {
 
 // Strategy for the default executor used by the parallel routines provided by
 // this file. It defaults to using all hardware threads and should be
 // initialized before the first use of parallel routines.
 extern ThreadPoolStrategy strategy;
 
 namespace detail {
-
-#if LLVM_ENABLE_THREADS
-
 class Latch {
   uint32_t Count;
   mutable std::mutex Mutex;
   mutable std::condition_variable Cond;
 
 public:
   explicit Latch(uint32_t Count = 0) : Count(Count) {}
   ~Latch() {
if (--Count == 0)
       Cond.notify_all();
   }
 
   void sync() const {
     std::unique_lock<std::mutex> lock(Mutex);
     Cond.wait(lock, [&] { return Count == 0; });
   }
 };
+} // namespace detail
 
 class TaskGroup {
-  Latch L;
+  detail::Latch L;
   bool Parallel;
 
 public:
   TaskGroup();
   ~TaskGroup();
 
   void spawn(std::function<void()> f);
 
   void sync() const { L.sync(); }
 };
 
+namespace detail {
+
+#if LLVM_ENABLE_THREADS
 const ptrdiff_t MinParallelSize = 1024;
 
 /// Inclusive median.
 template <class RandomAccessIterator, class Comparator>
 RandomAccessIterator medianOf3(RandomAccessIterator Start,
                                RandomAccessIterator End,
                                const Comparator &Comp) {
   RandomAccessIterator Mid = Start + (std::distance(Start, End) / 2);
Error parallelForEachError(RangeTy &&R, FuncTy Fn) {
   return unwrap(parallelTransformReduce(
       std::begin(R), std::end(R), wrap(Error::success()),
       [](LLVMErrorRef Lhs, LLVMErrorRef Rhs) {
         return wrap(joinErrors(unwrap(Lhs), unwrap(Rhs)));
       },
       [&Fn](auto &&V) { return wrap(Fn(V)); }));
 }
 
+// Spawn an async task to TG and do not wait for it to finish. When
+// ThreadsRequested == 1, the task is executedly eagerly.
+template <class FuncTy>
+void parallelAsyncTask(parallel::TaskGroup &TG, FuncTy Fn) {
+#if LLVM_ENABLE_THREADS
+  if (parallel::strategy.ThreadsRequested != 1) {
+    TG.spawn(Fn);
+    return;
+  }
+#endif
+  Fn();
+}
+
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_PARALLEL_H

llvm/lib/Support/Parallel.cpp

Executor *Executor::getDefaultExecutor() {
 
   static ManagedStatic<ThreadPoolExecutor, ThreadPoolExecutor::Creator,
                        ThreadPoolExecutor::Deleter>
       ManagedExec;
   static std::unique_ptr<ThreadPoolExecutor> Exec(&(*ManagedExec));
   return Exec.get();
 }
 } // namespace
+} // namespace detail
 
 static std::atomic<int> TaskGroupInstances;
 
 // Latch::sync() called by the dtor may cause one thread to block. If is a dead
 // lock if all threads in the default executor are blocked. To prevent the dead
 // lock, only allow the first TaskGroup to run tasks parallelly. In the scenario
 // of nested parallel_for_each(), only the outermost one runs parallelly.
 TaskGroup::TaskGroup() : Parallel(TaskGroupInstances++ == 0) {}
 TaskGroup::~TaskGroup() {
   // We must ensure that all the workloads have finished before decrementing the
   // instances count.
   L.sync();
   --TaskGroupInstances;
 }
 
 void TaskGroup::spawn(std::function<void()> F) {
   if (Parallel) {
     L.inc();
-    Executor::getDefaultExecutor()->add([&, F = std::move(F)] {
+    detail::Executor::getDefaultExecutor()->add([&, F = std::move(F)] {
       F();
       L.dec();
     });
   } else {
     F();
   }
 }
-
-} // namespace detail
 } // namespace parallel
 } // namespace llvm
 #endif // LLVM_ENABLE_THREADS
 
 void llvm::parallelFor(size_t Begin, size_t End,
                        llvm::function_ref<void(size_t)> Fn) {
   // If we have zero or one items, then do not incur the overhead of spinning up
   // a task group.  They are surprisingly expensive, and because they do not
   // support nested parallelism, a single entry task group can block parallel
   // execution underneath them.
 #if LLVM_ENABLE_THREADS
   auto NumItems = End - Begin;
   if (NumItems > 1 && parallel::strategy.ThreadsRequested != 1) {
     // Limit the number of tasks to MaxTasksPerGroup to limit job scheduling
     // overhead on large inputs.
     auto TaskSize = NumItems / parallel::detail::MaxTasksPerGroup;
     if (TaskSize == 0)
       TaskSize = 1;
 
-    parallel::detail::TaskGroup TG;
+    parallel::TaskGroup TG;
     for (; Begin + TaskSize < End; Begin += TaskSize) {
       TG.spawn([=, &Fn] {
         for (size_t I = Begin, E = Begin + TaskSize; I != E; ++I)
           Fn(I);
       });
     }
     for (; Begin != End; ++Begin)
       Fn(Begin);
     return;
   }
 #endif
 
   for (; Begin != End; ++Begin)
     Fn(Begin);
 }