[ELF] - Lazy initialization of MergeInputSection class internals.

[grimar]

Summary

Patch implements a way to lazily fill the Offsets vector of MergeInputSection class.

Now MergeInputSection<ELFT>::Offsets vector is filled much later,
after all GC processing, right after creation of output sections.
This allows to avoid filling it with dead ranges of data.
and opens oportunity to implement decompression
of sections in the way when only live sections are decompressed.
Also after that they should be easily switched to
parrallel_for proccessing here I am sure.

This rework also helped to cut off very similar code in
MergeOutputSection<ELFT>::addSection() and
MergeInputSection<ELFT>::MergeInputSection(), it is combined now
to MergeInputSection<ELFT>::prepareRanges().
Code from MergeOutputSection<ELFT>::addSection() is just gone.

[grimar]

ELF/InputSection.h

15

I`ll remove that line, it is needless.

[ruiu]

I think this change makes sense, but in this design uncompressing sections would be inevitably serialized because it uncompresses sections during section garbage collection and section writing. I'm wondering if there's a way to parallelize it. (You don't really have to parallelize it at this point, but I'm thinking about the design that allows us to parallelize it easily by rewriting a for-loop with a parallel_for)

If there is no GC, we can uncompress all input sections after the name resolution is complete and before Writer::write(). We could simply visit all input sections and uncompress them if compressed.

If GC is present, the situation becomes a bit tricky because we are using getRangeAndSize() in MarkLive.cpp to set live bits of pieces of input sections to true. However, we don't really need any section contents in GC; it just says that "a piece of data at this offset needs to be handled as live." Since we do not merge data at this point, we can still do without reading the section contents. Here's the observation.

• Until Writer::write(), no one needs section contents.
• MergeInputSection only need to know which offsets are live during GC.
• We could uncompress all input sections in parallel whose live bit is on.

So I think there's a room to improve this patch.

[grimar]

In D20433#434391, @ruiu wrote:

I think this change makes sense, but in this design uncompressing sections would be inevitably serialized because it uncompresses sections during section garbage collection and section writing. I'm wondering if there's a way to parallelize it. (You don't really have to parallelize it at this point, but I'm thinking about the design that allows us to parallelize it easily by rewriting a for-loop with a parallel_for)

If there is no GC, we can uncompress all input sections after the name resolution is complete and before Writer::write(). We could simply visit all input sections and uncompress them if compressed.

If GC is present, the situation becomes a bit tricky because we are using getRangeAndSize() in MarkLive.cpp to set live bits of pieces of input sections to true. However, we don't really need any section contents in GC; it just says that "a piece of data at this offset needs to be handled as live." Since we do not merge data at this point, we can still do without reading the section contents. Here's the observation.

• Until Writer::write(), no one needs section contents.
• MergeInputSection only need to know which offsets are live during GC.
• We could uncompress all input sections in parallel whose live bit is on.

So I think there's a room to improve this patch.

Yap, that is true. So I would start from solving the step 2 (know live offsets during GC) first for this patch, I guess.
I`ll try to improve it on all fronts though. Thanks for sharing ideas.

[grimar]

Fully reimplemented initial version of this.

Now MergeInputSection<ELFT>::Offsets vector is filled much later,
after all GC processing, right after creation of output sections.
This allows to avoid filling it with dead ranges of data.
and opens oportunity to implement decompression
of sections in the way when only live sections are decompressed.
Also after that they should be easily switched to
parrallel_for proccessing here I am sure.

This rework also helped to cut off very similar code in
MergeOutputSection<ELFT>::addSection() and
MergeInputSection<ELFT>::MergeInputSection(), it is combined now
to MergeInputSection<ELFT>::prepareRanges().
Code from MergeOutputSection<ELFT>::addSection() is just gone.

[grimar]

Forgot to add: all tests passes ok.

[ruiu]

You don't need to introduce a new notion of range for doing GC lazily. All you have to do is to memorize live offsets and apply it later. Please take a look at http://reviews.llvm.org/D20516

[grimar]

In D20433#436489, @ruiu wrote:

You don't need to introduce a new notion of range for doing GC lazily. All you have to do is to memorize live offsets and apply it later. Please take a look at http://reviews.llvm.org/D20516

I am not doing GC lazily here. I think "memorize live offsets and apply it later" it is almost exactly what this patch do.
At fact it memorize live offsets, but also do not keeps dead pieces when builds a list of them.

I think problem here that my patch was built on a half day old source code, that is probably why it looks like I introduced something new,
but Pieces and Ranges are just about the same.

So your way is to apply live bit and store all pieces, my way was to store only live pieces and that is why I even was need to save
data size separatelly (because I was not able to substract piece 1 offset from piece 2 offset if the latter was dead, I just did not have it in the list).

Actually I was sure that it is slightly better way, I tried to save all possible resources including memory,
since storing dead pieces is a waste. But your approach looks cleaner in implementation for me, so I would go with it.

[ruiu]

r270455 should make things a lot easier to support compressed sections. Now I think basically you want to write InputSection::uncompress() function and call it like this from the driver's link function.

  for (InputSectionBase<ELFT> *S : F->getSections()) {
    if (!S || S == &InputSection<ELFT>::Discarded || !S->Live)
      continue;
    if (S->Compressed)
      S->uncompress();
    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(S))
      MS->splitIntoPieces();
  }
}

ELF/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_INPUT_SECTION_H
 #define LLD_ELF_INPUT_SECTION_H
 
 #include "Config.h"
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"
 
+namespace llvm {
+class StringTableBuilder;
+}
+
 namespace lld {
 namespace elf {
 
 class SymbolBody;
 
 template <class ELFT> class ICF;
 template <class ELFT> class DefinedRegular;
 template <class ELFT> class ObjectFile;

 public:
   SplitInputSection(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                     typename InputSectionBase<ELFT>::Kind SectionKind);
 
   // For each piece of data, we maintain the offsets in the input section and
   // in the output section.
   std::vector<std::pair<uintX_t, uintX_t>> Offsets;
 
-  // Merge input sections may use the following special values as the output
-  // section offset:
-  enum {
-    // The piece is dead.
-    PieceDead = uintX_t(-1),
-    // The piece is live, but an offset has not yet been assigned. After offsets
-    // have been assigned, if the output section uses tail merging, the field
-    // will still have this value and the output section offset is computed
-    // lazilly.
-    PieceLive = uintX_t(-2),
-  };
-
   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t>
   getRangeAndSize(uintX_t Offset);
 };
 
 // This corresponds to a SHF_MERGE section of an input file.
 template <class ELFT> class MergeInputSection : public SplitInputSection<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Shdr Elf_Shdr;
 
 public:
   MergeInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
   static bool classof(const InputSectionBase<ELFT> *S);
   // Translate an offset in the input section to an offset in the output
   // section.
   uintX_t getOffset(uintX_t Offset);
+
+  void prepareRanges(llvm::StringTableBuilder &Builder, bool Lazy);
+
+  // Alive ranges should be marked early during GC.
+  void setRangeLive(uintX_t Offset);
+
+  bool isRangeLive(uintX_t Offset);
+
+  // Updates or create a new range with specified parameters. If GC is enabled,
+  // and range was not marked as live, it is not created.
+  bool checkInRange(uintX_t Offset, uintX_t Size, bool IsLazy);
+
+private:
+  struct Range {
+    uintX_t Size;
+    bool IsLazy;
+  };
+  llvm::DenseMap<uintX_t, Range> AliveRanges;
 };
 
 // This corresponds to a .eh_frame section of an input file.
 template <class ELFT> class EHInputSection : public SplitInputSection<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::uint uintX_t;
   EHInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);

ELF/InputSection.cpp

if (std::all_of(B, B + EntSize, [](char C) { return C == 0; }))
       return I;
   }
   return StringRef::npos;
 }
 
 template <class ELFT>
 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
                                            const Elf_Shdr *Header)
-    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {
+    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {}
+
+template <class ELFT>
+void MergeInputSection<ELFT>::prepareRanges(llvm::StringTableBuilder &Builder,
+                                            bool Lazy) {
   uintX_t EntSize = Header->sh_entsize;
   ArrayRef<uint8_t> D = this->getSectionData();
   StringRef Data((const char *)D.data(), D.size());
   std::vector<std::pair<uintX_t, uintX_t>> &Offsets = this->Offsets;
 
-  uintX_t V = Config->GcSections ? MergeInputSection<ELFT>::PieceDead
-                                 : MergeInputSection<ELFT>::PieceLive;
   if (Header->sh_flags & SHF_STRINGS) {
     uintX_t Offset = 0;
     while (!Data.empty()) {
       size_t End = findNull(Data, EntSize);
       if (End == StringRef::npos)
         fatal("string is not null terminated");
-      Offsets.push_back(std::make_pair(Offset, V));
       uintX_t Size = End + EntSize;
+      StringRef Entry = Data.substr(0, Size);
       Data = Data.substr(Size);
       Offset += Size;
+
+      if (checkInRange(Offset - Size, Size, Lazy))
+        Offsets.push_back(std::make_pair(Offset - Size, Builder.add(Entry)));
     }
     return;
   }
 
   // If this is not of type string, every entry has the same size.
   size_t Size = Data.size();
   assert((Size % EntSize) == 0);
-  for (unsigned I = 0, N = Size; I != N; I += EntSize)
+  for (unsigned I = 0, N = Size; I != N; I += EntSize) {
+    if (checkInRange(I, Size, false)) {
+      uintX_t V = Builder.add(Data.substr(I, EntSize));
       Offsets.push_back(std::make_pair(I, V));
     }
+  }
+}
 
 template <class ELFT>
 bool MergeInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == InputSectionBase<ELFT>::Merge;
 }
 
 template <class ELFT>
 std::pair<std::pair<typename ELFT::uint, typename ELFT::uint> *,
SplitInputSection<ELFT>::getRangeAndSize(uintX_t Offset) {
   return std::make_pair(&*I, End);
 }
 
 template <class ELFT>
 typename ELFT::uint MergeInputSection<ELFT>::getOffset(uintX_t Offset) {
   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
       this->getRangeAndSize(Offset);
   std::pair<uintX_t, uintX_t> *I = T.first;
-  uintX_t End = T.second;
   uintX_t Start = I->first;
+  Range &R = AliveRanges[Start];
 
   // Compute the Addend and if the Base is cached, return.
   uintX_t Addend = Offset - Start;
   uintX_t &Base = I->second;
-  assert(Base != MergeInputSection<ELFT>::PieceDead);
-  if (Base != MergeInputSection<ELFT>::PieceLive)
+  if (!R.IsLazy)
     return Base + Addend;
 
   // Map the base to the offset in the output section and cache it.
   ArrayRef<uint8_t> D = this->getSectionData();
   StringRef Data((const char *)D.data(), D.size());
-  StringRef Entry = Data.substr(Start, End - Start);
+  StringRef Entry = Data.substr(Start, R.Size);
   auto *MOS = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
   Base = MOS->getOffset(Entry);
   return Base + Addend;
 }
 
 template <class ELFT>
+void MergeInputSection<ELFT>::setRangeLive(uintX_t Offset) {
+  AliveRanges[Offset] = {(uintX_t)-1, false};
+}
+
+template <class ELFT>
+bool MergeInputSection<ELFT>::isRangeLive(uintX_t Offset) {
+  if (!Config->GcSections)
+    return true;
+  return AliveRanges.count(Offset) != 0;
+}
+
+template <class ELFT>
+bool MergeInputSection<ELFT>::checkInRange(uintX_t Offset, uintX_t Size,
+                                           bool IsLazy) {
+  auto I = AliveRanges.find(Offset);
+  if (I != AliveRanges.end()) {
+    I->second = {Size, IsLazy};
+    return true;
+  }
+
+  if (Config->GcSections)
+    return false;
+
+  AliveRanges[Offset] = {Size, IsLazy};
+  return true;
+}
+
+template <class ELFT>
 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,
                                                        const Elf_Shdr *Hdr)
     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsReginfo) {
   // Initialize this->Reginfo.
   ArrayRef<uint8_t> D = this->getSectionData();
   if (D.size() != sizeof(Elf_Mips_RegInfo<ELFT>)) {
     error("invalid size of .reginfo section");
     return;

ELF/MarkLive.cpp

 // sections to set their "Live" bits.
 template <class ELFT> void elf::markLive() {
   typedef typename ELFT::uint uintX_t;
   SmallVector<InputSection<ELFT> *, 256> Q;
 
   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
     if (!R.Sec)
       return;
-    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) {
-      std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
-          MS->getRangeAndSize(R.Offset);
-      T.first->second = MergeInputSection<ELFT>::PieceLive;
-    }
+    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec))
+      MS->setRangeLive(R.Offset);
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 
   auto MarkSymbol = [&](const SymbolBody *Sym) {

ELF/OutputSections.h

public:
   MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags,
                      uintX_t Alignment);
   void addSection(InputSectionBase<ELFT> *S) override;
   void writeTo(uint8_t *Buf) override;
   unsigned getOffset(StringRef Val);
   void finalize() override;
   bool shouldTailMerge() const;
 
+  void prepare();
+
 private:
   llvm::StringTableBuilder Builder;
+  std::vector<MergeInputSection<ELFT> *> InputSections;
 };
 
 // FDE or CIE
 template <class ELFT> struct EHRegion {
   typedef typename ELFT::uint uintX_t;
   EHRegion(EHInputSection<ELFT> *S, unsigned Index);
   StringRef data() const;
   EHInputSection<ELFT> *S;

ELF/OutputSections.cpp

template <class ELFT> void MergeOutputSection<ELFT>::writeTo(uint8_t *Buf) {
   }
 }
 
 template <class ELFT>
 void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   auto *S = cast<MergeInputSection<ELFT>>(C);
   S->OutSec = this;
   this->updateAlign(S->Align);
-
-  ArrayRef<uint8_t> D = S->getSectionData();
-  StringRef Data((const char *)D.data(), D.size());
-  uintX_t EntSize = S->getSectionHdr()->sh_entsize;
-  this->Header.sh_entsize = EntSize;
-  MutableArrayRef<std::pair<uintX_t, uintX_t>> Offsets = S->Offsets;
-
-  // If this is of type string, the contents are null-terminated strings.
-  if (this->Header.sh_flags & SHF_STRINGS) {
-    for (unsigned I = 0, N = Offsets.size(); I != N; ++I) {
-      auto &P = Offsets[I];
-      if (P.second == MergeInputSection<ELFT>::PieceDead)
-        continue;
-
-      uintX_t Start = P.first;
-      uintX_t End = (I == N - 1) ? Data.size() : Offsets[I + 1].first;
-      StringRef Entry = Data.substr(Start, End - Start);
-      uintX_t OutputOffset = Builder.add(Entry);
-      if (shouldTailMerge())
-        OutputOffset = MergeInputSection<ELFT>::PieceLive;
-      P.second = OutputOffset;
-    }
-    return;
-  }
+  InputSections.push_back(S);
 
-  // If this is not of type string, every entry has the same size.
-  for (auto &P : Offsets) {
-    if (P.second == (uintX_t)-1)
-      continue;
-    StringRef Entry = Data.substr(P.first, EntSize);
-    P.second = Builder.add(Entry);
-  }
+template <class ELFT> void MergeOutputSection<ELFT>::prepare() {
+  for (MergeInputSection<ELFT> *S : InputSections)
+    S->prepareRanges(Builder, shouldTailMerge());
+  this->Header.sh_entsize = InputSections[0]->getSectionHdr()->sh_entsize;
 }
 
 template <class ELFT>
 unsigned MergeOutputSection<ELFT>::getOffset(StringRef Val) {
   return Builder.getOffset(Val);
 }
 
 template <class ELFT> bool MergeOutputSection<ELFT>::shouldTailMerge() const {

ELF/Writer.cpp

template <class ELFT> static bool includeInSymtab(const SymbolBody &B) {
   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B)) {
     // Always include absolute symbols.
     if (!D->Section)
       return true;
     // Exclude symbols pointing to garbage-collected sections.
     if (!D->Section->Live)
       return false;
     if (auto *S = dyn_cast<MergeInputSection<ELFT>>(D->Section))
-      if (S->getRangeAndSize(D->Value).first->second ==
-          MergeInputSection<ELFT>::PieceDead)
-        return false;
+      return S->isRangeLive(D->Value);
   }
   return true;
 }
 
 // Local symbols are not in the linker's symbol table. This function scans
 // each object file's symbol table to copy local symbols to the output.
 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!Out<ELFT>::SymTab)
template <class ELFT> void Writer<ELFT>::createSections() {
   // A core file does not usually contain unmodified segments except
   // the first page of the executable. Add the build ID section now
   // so that the section is included in the first page.
   if (Out<ELFT>::BuildId)
     OutputSections.push_back(Out<ELFT>::BuildId);
 
   // Create output sections for input object file sections.
   std::vector<OutputSectionBase<ELFT> *> RegularSections;
+  std::vector<MergeOutputSection<ELFT> *> MergeOutputSections;
   OutputSectionFactory<ELFT> Factory;
   for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
        Symtab.getObjectFiles()) {
     for (InputSectionBase<ELFT> *C : F->getSections()) {
       if (isDiscarded(C)) {
         reportDiscarded(C, F);
         continue;
       }
       OutputSectionBase<ELFT> *Sec;
       bool IsNew;
       std::tie(Sec, IsNew) = Factory.create(C, getOutputSectionName(C));
       if (IsNew) {
         OwningSections.emplace_back(Sec);
         OutputSections.push_back(Sec);
         RegularSections.push_back(Sec);
+        if (C->SectionKind == InputSectionBase<ELFT>::Merge)
+          MergeOutputSections.push_back(
+              static_cast<MergeOutputSection<ELFT> *>(Sec));
       }
       Sec->addSection(C);
     }
   }
 
+  for (MergeOutputSection<ELFT> *MS : MergeOutputSections)
+    MS->prepare();
+
   Out<ELFT>::Bss = static_cast<OutputSection<ELFT> *>(
       Factory.lookup(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE));
 
   // If we have a .opd section (used under PPC64 for function descriptors),
   // store a pointer to it here so that we can use it later when processing
   // relocations.
   Out<ELFT>::Opd = Factory.lookup(".opd", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC);