[ELF] - Represent .init_array/.fini_array via synthetic sections.

[grimar]

Summary

I suggest this change, it should open road for fixing PR31224.
This patch introduces InitFiniSection which holds
.init_array/.fini_array sections inside.

Idea is next: we can do the same for .ctors/.dtors in another patch.
Synthetic section for .ctors/.dtors should know how to
change sorting rules on fly depending on output section name.

Then it should be possible to mix .init_array/.ctors and .fini_array/.dtors,
like bfd/gold do easily.

[orivej]

Idea is next: we can do the same for .ctors/.dtors in another patch.
Synthetic section for .ctors/.dtors should know how to change sorting rules on fly depending on output section name.

Does this allow for .ctors and .init_array to be intermixed in the output section? E.g. .ctors.1, .ctors.3, and .init_array.2 contents should be concatenated as reverse(.ctors.1) + .init_array.2 + reverse(.ctors.3).

[ruiu]

I don't see a reason to convert .{init,fini}_array to synthetic sections because we can basically pass through them to results. The other approach I can think of is to convert .{dtors,ctors} to .{init,fini}_array internally so that they are processed as if they were .{init,fini}_array from the beginning.

[orivej]

The other approach I can think of is to convert .{dtors,ctors} to .{init,fini}_array internally so that they are processed as if they were .{init,fini}_array from the beginning.

I did this in https://bugs.llvm.org/show_bug.cgi?id=31224#c22

[grimar]

In D35487#811503, @orivej wrote:

Idea is next: we can do the same for .ctors/.dtors in another patch.
Synthetic section for .ctors/.dtors should know how to change sorting rules on fly depending on output section name.

Does this allow for .ctors and .init_array to be intermixed in the output section? E.g. .ctors.1, .ctors.3, and .init_array.2 contents should be concatenated as reverse(.ctors.1) + .init_array.2 + reverse(.ctors.3).

It should be possible to implement this, but I do not think that is what bfd do when mixing them. So why LLD should ?
I think it is not what bfd do because it's built-in script is (ld.bfd -verbose):

.init_array     :
{
  PROVIDE_HIDDEN (__init_array_start = .);
  KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*) SORT_BY_INIT_PRIORITY(.ctors.*)))
  KEEP (*(.init_array EXCLUDE_FILE (*crtbegin.o *crtbegin?.o *crtend.o *crtend?.o ) .ctors))
  PROVIDE_HIDDEN (__init_array_end = .);
}

So it always places .init_array* first and then .ctors.* I believe.

In D35487#811659, @orivej wrote:

The other approach I can think of is to convert .{dtors,ctors} to .{init,fini}_array internally so that they are processed as if they were .{init,fini}_array from the beginning.

I did this in https://bugs.llvm.org/show_bug.cgi?id=31224#c22

Probably it worth to push it on review to phab then.

[orivej]

It should be possible to implement this, but I do not think that is what bfd do when mixing them. So why LLD should?

I do not know how bfd interprets this script, but its test checks that they are mixed: https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=ld/testsuite/ld-elf/init-mixed.c;h=f401ded4d702be49669ecdc7893f65cc70e9fa7c;hb=HEAD
The need to mix .ctors with .init_array is the reason why gcc could not just add support for .init_array in crtbegin.o and had to change the linker.

Probably it worth to push it on review to phab then.

@ruiu has proposed another approach: https://bugs.llvm.org/show_bug.cgi?id=31224#c26, https://reviews.llvm.org/D35509

[grimar]

D35509 was suggested instead.

ELF/Driver.cpp

template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   if (!Config->Relocatable)
     InputSections.push_back(createCommentSection<ELFT>());
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
   if (Config->GcSections)
     markLive<ELFT>();
   decompressAndMergeSections();
+  if (!Script->Opt.HasSections)
+    createInitFiniSynthetics<ELFT>();
   if (Config->ICF)
     doIcf<ELFT>();
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   bool Noload = false;
 
   template <class ELFT> void finalize();
   template <class ELFT> void writeTo(uint8_t *Buf);
   template <class ELFT> void maybeCompress();
   uint32_t getFiller();
 
   void sort(std::function<int(InputSectionBase *S)> Order);
-  void sortInitFini();
   void sortCtorsDtors();
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.
 struct SectionPattern {
   SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)

ELF/LinkerScript.cpp

bool LinkerScript::shouldKeep(InputSectionBase *S) {
   for (InputSectionDescription *ID : Opt.KeptSections)
     if (ID->FilePat.match(basename(S)))
       for (SectionPattern &P : ID->SectionPatterns)
         if (P.SectionPat.match(S->Name))
           return true;
   return false;
 }
 
-// If an input string is in the form of "foo.N" where N is a number,
-// return N. Otherwise, returns 65536, which is one greater than the
-// lowest priority.
-static int getPriority(StringRef S) {
-  size_t Pos = S.rfind('.');
-  if (Pos == StringRef::npos)
-    return 65536;
-  int V;
-  if (!to_integer(S.substr(Pos + 1), V, 10))
-    return 65536;
-  return V;
-}
-
 // A helper function for the SORT() command.
 static std::function<bool(InputSectionBase *, InputSectionBase *)>
 getComparator(SortSectionPolicy K) {
   switch (K) {
   case SortSectionPolicy::Alignment:
     return [](InputSectionBase *A, InputSectionBase *B) {
       // ">" is not a mistake. Sections with larger alignments are placed
       // before sections with smaller alignments in order to reduce the

 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 // Read the comment above.
 void OutputSectionCommand::sortCtorsDtors() {
   assert(Commands.size() == 1);
   auto *ISD = cast<InputSectionDescription>(Commands[0]);
   std::stable_sort(ISD->Sections.begin(), ISD->Sections.end(), compCtors);
 }
 
-// Sorts input sections by section name suffixes, so that .foo.N comes
-// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
-// We want to keep the original order if the priorities are the same
-// because the compiler keeps the original initialization order in a
-// translation unit and we need to respect that.
-// For more detail, read the section of the GCC's manual about init_priority.
-void OutputSectionCommand::sortInitFini() {
-  // Sort sections by priority.
-  sort([](InputSectionBase *S) { return getPriority(S->Name); });
-}
-
 uint32_t OutputSectionCommand::getFiller() {
   if (Filler)
     return *Filler;
   if (Sec->Flags & SHF_EXECINSTR)
     return Target->TrapInstr;
   return 0;
 }
 

ELF/SyntheticSections.h

 private:
   void finalizeTailMerge();
   void finalizeNoTailMerge();
 
   llvm::StringTableBuilder Builder;
   std::vector<MergeInputSection *> Sections;
 };
 
+// InitFiniSection is a class holding .init_array and .fini_array sections.
+// For such sections sorting rules are special, see finalizeContents() member.
+template <class ELFT> class InitFiniSection final : public SyntheticSection {
+public:
+  InitFiniSection(StringRef Name, uint32_t Type, uint64_t Flags,
+                  uint32_t Alignment)
+      : SyntheticSection(Flags, Type, Alignment, Name) {}
+  void addSection(InputSection *S) { Sections.push_back(S); }
+  void writeTo(uint8_t *Buf) override;
+  void finalizeContents() override;
+  size_t getSize() const override { return Size; }
+
+private:
+  uint64_t Size = 0;
+  std::vector<InputSection *> Sections;
+};
+
 // .MIPS.abiflags section.
 template <class ELFT>
 class MipsAbiFlagsSection final : public SyntheticSection {
   typedef llvm::object::Elf_Mips_ABIFlags<ELFT> Elf_Mips_ABIFlags;
 
 public:
   static MipsAbiFlagsSection *create();
 
private:
   std::vector<const Thunk *> Thunks;
   size_t Size = 0;
 };
 
 template <class ELFT> InputSection *createCommonSection();
 InputSection *createInterpSection();
 template <class ELFT> MergeInputSection *createCommentSection();
 void decompressAndMergeSections();
+template <class ELFT> void createInitFiniSynthetics();
+int getPriority(StringRef S);
 
 SymbolBody *addSyntheticLocal(StringRef Name, uint8_t Type, uint64_t Value,
                               uint64_t Size, InputSectionBase *Section);
 
 // Linker generated sections which can be used as inputs.
 struct InX {
   static InputSection *ARMAttributes;
   static BssSection *Bss;

ELF/SyntheticSections.cpp

void MergeSyntheticSection::finalizeContents() {
   else
     finalizeNoTailMerge();
 }
 
 size_t MergeSyntheticSection::getSize() const {
   return Builder.getSize();
 }
 
+template <class ELFT> void InitFiniSection<ELFT>::writeTo(uint8_t *Buf) {
+  for (InputSection *S : Sections)
+    S->writeTo<ELFT>(Buf);
+}
+
+// Sorts input sections by section name suffixes, so that .foo.N comes
+// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
+// We want to keep the original order if the priorities are the same
+// because the compiler keeps the original initialization order in a
+// translation unit and we need to respect that.
+// For more detail, read the section of the GCC's manual about init_priority.
+template <class ELFT> void InitFiniSection<ELFT>::finalizeContents() {
+  auto Cmp = [](const InputSection *A, const InputSection *B) {
+    return getPriority(A->Name) < getPriority(B->Name);
+  };
+  std::stable_sort(Sections.begin(), Sections.end(), Cmp);
+
+  uint64_t Off = 0;
+  for (InputSection *Sec : Sections) {
+    Off = alignTo(Size, Sec->Alignment);
+    Sec->OutSecOff = Off;
+    Size = Off + Sec->getSize();
+    Alignment = std::max(Alignment, Sec->Alignment);
+  }
+}
+
+template <class T> static void finalizeAndClean(ArrayRef<T *> Sections) {
+  for (auto *Sec : Sections)
+    Sec->finalizeContents();
+  std::vector<InputSectionBase *> &V = InputSections;
+  V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
+}
+
 // This function decompresses compressed sections and scans over the input
 // sections to create mergeable synthetic sections. It removes
 // MergeInputSections from the input section array and adds new synthetic
 // sections at the location of the first input section that it replaces. It then
 // finalizes each synthetic section in order to compute an output offset for
 // each piece of each input section.
 void elf::decompressAndMergeSections() {
   // splitIntoPieces needs to be called on each MergeInputSection before calling
if (I == MergeSections.end()) {
       MergeSections.push_back(Syn);
       I = std::prev(MergeSections.end());
       S = Syn;
     } else {
       S = nullptr;
     }
     (*I)->addSection(MS);
   }
-  for (auto *MS : MergeSections)
-    MS->finalizeContents();
 
-  std::vector<InputSectionBase *> &V = InputSections;
-  V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
+  finalizeAndClean<MergeSyntheticSection>(MergeSections);
+}
+
+template <class ELFT> void elf::createInitFiniSynthetics() {
+  std::vector<InitFiniSection<ELFT> *> InitFiniSections;
+  for (InputSectionBase *&S : InputSections) {
+    if (S->Type != SHT_INIT_ARRAY && S->Type != SHT_FINI_ARRAY)
+      continue;
+
+    StringRef OutsecName = getOutputSectionName(S->Name);
+    uint64_t Flags = S->Flags & ~(uint64_t)SHF_GROUP;
+    auto I = llvm::find_if(InitFiniSections, [=](InitFiniSection<ELFT> *Sec) {
+      return Sec->Name == OutsecName && Sec->Flags == Flags;
+    });
+
+    if (I == InitFiniSections.end()) {
+      InitFiniSection<ELFT> *Syn = make<InitFiniSection<ELFT>>(
+          OutsecName, S->Type, Flags, 0 /*Alignment*/);
+      InitFiniSections.push_back(Syn);
+      Syn->addSection(cast<InputSection>(S));
+      S = Syn;
+    } else {
+      (*I)->addSection(cast<InputSection>(S));
+      S = nullptr;
+    }
+  }
+
+  finalizeAndClean<InitFiniSection<ELFT>>(InitFiniSections);
+}
+
+// If an input string is in the form of "foo.N" where N is a number,
+// return N. Otherwise, returns 65536, which is one greater than the
+// lowest priority.
+int elf::getPriority(StringRef S) {
+  size_t Pos = S.rfind('.');
+  if (Pos == StringRef::npos)
+    return 65536;
+  int V;
+  if (!to_integer(S.substr(Pos + 1), V, 10))
+    return 65536;
+  return V;
 }
 
 MipsRldMapSection::MipsRldMapSection()
     : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, Config->Wordsize,
                        ".rld_map") {}
 
 ARMExidxSentinelSection::ARMExidxSentinelSection()
     : SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,

 template InputSection *elf::createCommonSection<ELF64LE>();
 template InputSection *elf::createCommonSection<ELF64BE>();
 
 template MergeInputSection *elf::createCommentSection<ELF32LE>();
 template MergeInputSection *elf::createCommentSection<ELF32BE>();
 template MergeInputSection *elf::createCommentSection<ELF64LE>();
 template MergeInputSection *elf::createCommentSection<ELF64BE>();
 
+template void elf::createInitFiniSynthetics<ELF32LE>();
+template void elf::createInitFiniSynthetics<ELF32BE>();
+template void elf::createInitFiniSynthetics<ELF64LE>();
+template void elf::createInitFiniSynthetics<ELF64BE>();
+
 template class elf::MipsAbiFlagsSection<ELF32LE>;
 template class elf::MipsAbiFlagsSection<ELF32BE>;
 template class elf::MipsAbiFlagsSection<ELF64LE>;
 template class elf::MipsAbiFlagsSection<ELF64BE>;
 
 template class elf::MipsOptionsSection<ELF32LE>;
 template class elf::MipsOptionsSection<ELF32BE>;
 template class elf::MipsOptionsSection<ELF64LE>;

 template class elf::VersionDefinitionSection<ELF32BE>;
 template class elf::VersionDefinitionSection<ELF64LE>;
 template class elf::VersionDefinitionSection<ELF64BE>;
 
 template class elf::EhFrameSection<ELF32LE>;
 template class elf::EhFrameSection<ELF32BE>;
 template class elf::EhFrameSection<ELF64LE>;
 template class elf::EhFrameSection<ELF64BE>;
+
+template class elf::InitFiniSection<ELF32LE>;
+template class elf::InitFiniSection<ELF32BE>;
+template class elf::InitFiniSection<ELF64LE>;
+template class elf::InitFiniSection<ELF64BE>;

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
   ElfSym::End1 = Add("end");
   ElfSym::End2 = Add("_end");
   ElfSym::Etext1 = Add("etext");
   ElfSym::Etext2 = Add("_etext");
   ElfSym::Edata1 = Add("edata");
   ElfSym::Edata2 = Add("_edata");
 }
 
-// Sort input sections by section name suffixes for
-// __attribute__((init_priority(N))).
-static void sortInitFini(OutputSectionCommand *Cmd) {
-  if (Cmd)
-    Cmd->sortInitFini();
-}
-
 // Sort input sections by the special rule for .ctors and .dtors.
 static void sortCtorsDtors(OutputSectionCommand *Cmd) {
   if (Cmd)
     Cmd->sortCtorsDtors();
 }
 
 // Sort input sections using the list provided by --symbol-ordering-file.
 template <class ELFT> static void sortBySymbolsOrder() {

 
 template <class ELFT> void Writer<ELFT>::createSections() {
   for (InputSectionBase *IS : InputSections)
     if (IS)
       Factory.addInputSec(IS, getOutputSectionName(IS->Name));
 
   Script->fabricateDefaultCommands();
   sortBySymbolsOrder<ELFT>();
-  sortInitFini(findSectionCommand(".init_array"));
-  sortInitFini(findSectionCommand(".fini_array"));
   sortCtorsDtors(findSectionCommand(".ctors"));
   sortCtorsDtors(findSectionCommand(".dtors"));
 }
 
 // We want to find how similar two ranks are.
 // The more branches in getSectionRank that match, the more similar they are.
 // Since each branch corresponds to a bit flag, we can just use
 // countLeadingZeros.