[ELF] - Drop SHF_LINK_ORDER flag from output.

[grimar]

Summary

As was discussed in D37736 thread, we can drop SHF_LINK_ORDER
and do that early enough, so that this flag will not affect on
flags of sections that contains only symbol assignments and created in
adjustSectionsBeforeSorting().

It also looks there is no reason to keep this flag when doing final link.
this patch preserves it only when -r is given.

[ruiu]

ELF/Driver.cpp

976

This is not something I meant by "drop it early when it is processed". It just drops the flag at an arbitrary point instead of when SHF_LINK_ORDER is processed. Also, this kind of code shouldn't be in the driver.

[ruiu]

If you initialize LinkOrderDep based on SHF_LINK_ORDER, why don't you drop the flag when you initialize it?

[grimar]

In D38170#879013, @ruiu wrote:

If you initialize LinkOrderDep based on SHF_LINK_ORDER, why don't you drop the flag when you initialize it?

Not sure what you mean, I drop the flag in scanLinkOrder at line 989, exactly at the point where I initialize LinkOrderDep.

[grimar]

ELF/Driver.cpp

976

It is processed in OutputSection::finalize() because at that place we know the order of output sections and can sort input sections in according to order flags. I could drop the flag there, but it would make this patch useless, since its aim not just to drop the flag (it is itself harmless in output I believe), but do that before we create sections in adjustSectionsBeforeSorting, so that SHF_LINK_ORDER flag do not spread on them.

[peter.smith]

I agree that the SHF_LINK_ORDER flag shouldn't need to be kept in a non-relocatable object, I kept it in I've run into at least one ELF disassembler that complained about it not being there as it was inferring that one should be there from the .ARM.exidx section name. This was many years ago and I can't remember the program though. It might be worth trying to output the exceptions with GNU readelf just to check.

The reordering of the link order sections can be moved earlier than finalize(), as soon as the order of InputSections within the OutputSections is known.

I've not got any major objections to the patch, my one minor concern is that we are treating the SHF_LINK_ORDER flag differently to all/most of the other ELF flags which could catch someone out in the future if they weren't aware of it. I'm not sure if there is a good solution for that as I don't know where a comment could be put that we could guarantee a future developer would see.

[ruiu]

What I meant by "drop SHF_LINK_ORDER early" is something like this: https://reviews.llvm.org/D38269

This patch does not actually work and is not intended to be submitted, but I believe you can understand the idea.

[grimar]

In D38170#880817, @ruiu wrote:

What I meant by "drop SHF_LINK_ORDER early" is something like this: https://reviews.llvm.org/D38269

This patch does not actually work and is not intended to be submitted, but I believe you can understand the idea.

Thanks for sample. Honestly dropping the flag in InputSection constructor was the first thing I tried. But I did not check
for Link != 0 that time I think. I remember it crashed for me when accessed null section and made me think we can not access
to other sections there because them may be not initialized yet.
So that time seems I did wrong conclusion that SHF_LINK_ORDER section was placed
earlier than its target in object from testcase that failed for me and that is why I had to add scanLinkOrder separatelly.
Indeed dropping flag in constructor looks much better.
Thanks again ! I am going to update this patch soon.

[grimar]

• Updated implementation according to review comment.

[ruiu]

ELF/InputSection.cpp

97–98

"a section with SHF_LINK_ORDER should not refer a non-regular section: " + toString(Sec)

ELF/InputSection.h

185

As always, it needs a comment.

ELF/OutputSections.cpp

447

This is O(N^2) where N is the number of input sections. Please don't do that.

[grimar]

• Addressed review comments.

ELF/InputSection.cpp

97–98

Changed in r314392 (it was legacy text).

ELF/InputSection.h

185

Done.

ELF/OutputSections.cpp

447

I believe that is O(Mx) here. Where M is amount of sections in output section, so that M0+M1+....+Mn == N,
where N is total amount of input sections. Overall complexity is O(N).
Because for each output section this function scans over its input sections once.

I think you was confused by incorrect code style in OutputSection::finalize(), I fixed it in r314394.

[ruiu]

ELF/InputSection.cpp

94

Inline this function.

ELF/InputSection.h

185–187

// A value of an SHF_LINK_ORDER flag. If a section doesn't have an SHF_LINK_ORDER, it's nullptr.

ELF/OutputSections.cpp

447

I still do not understand this. It doesn't seem correct. You need to handle two or LinkOrderSections, right? Why can you assume that there is always up to one LinkOrderSection?

[grimar]

• Addressed review comments.

ELF/OutputSections.cpp

447

I do not assume it. For non-relocatable case all what I need is to know if we have
link order sections or not, so that we can sort them. In that case any value
except 0 is enough.

For -r case I believe proper behavior would be to merge together only sections that have
the same parent output sections for their link - order sections.
So link order index should be always the same.

FWIW, original code set sh_link value using first input section's value,
what does not seem correct either.

I changed code a little to make my intentions more clear, is it looks better now ?

[grimar]

In favor of D37736.

ELF/Driver.cpp

static void excludeLibs(opt::InputArgList &Args, ArrayRef<InputFile *> Files) {
 
   for (InputFile *File : Files)
     if (auto *F = dyn_cast<ArchiveFile>(File))
       if (All || Libs.count(path::filename(F->getName())))
         for (SymbolBody *Sym : F->getSymbols())
           Sym->symbol()->VersionId = VER_NDX_LOCAL;
 }
 
+static void scanLinkOrder() {
+  for (InputSectionBase *S : InputSections) {
+    if (!(S->Flags & SHF_LINK_ORDER))
+      continue;
+
+    InputSectionBase *Sec = S->File->getSections()[S->Link];
+    if (InputSection *IS = dyn_cast<InputSection>(Sec))
+      S->LinkOrderDep = IS;
+    else
+      error("Merge and .eh_frame sections are not supported with "
+            "SHF_LINK_ORDER " +
+            toString(Sec));
+
+    if (!Config->Relocatable)
+      S->Flags &= ~(uint64_t)SHF_LINK_ORDER;
+  }
+}
+
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   Target = getTarget();
 
   Config->MaxPageSize = getMaxPageSize(Args);
   Config->ImageBase = getImageBase(Args);
 
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // This adds a .comment section containing a version string. We have to add it
   // before decompressAndMergeSections because the .comment section is a
   // mergeable section.
   if (!Config->Relocatable)
     InputSections.push_back(createCommentSection<ELFT>());
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
+  scanLinkOrder();
   if (Config->GcSections)
     markLive<ELFT>();
   decompressAndMergeSections();
   if (Config->ICF)
     doIcf<ELFT>();
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/ICF.cpp

template <class ELFT> void ICF<ELFT>::run() {
   });
 
   // Mark ARM Exception Index table sections that refer to folded code
   // sections as not live. These sections have an implict dependency
   // via the link order dependency.
   if (Config->EMachine == EM_ARM)
     for (InputSectionBase *Sec : InputSections)
       if (auto *S = dyn_cast<InputSection>(Sec))
-        if (S->Flags & SHF_LINK_ORDER)
-          S->Live = S->getLinkOrderDep()->Live;
+        if (S->LinkOrderDep)
+          S->Live = S->LinkOrderDep->Live;
 }
 
 // ICF entry point function.
 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
 
 template void elf::doIcf<ELF32LE>();
 template void elf::doIcf<ELF32BE>();
 template void elf::doIcf<ELF64LE>();
 template void elf::doIcf<ELF64BE>();

ELF/InputSection.h

public:
   size_t getSize() const;
 
   template <class ELFT> ObjFile<ELFT> *getFile() const;
 
   template <class ELFT> llvm::object::ELFFile<ELFT> getObj() const {
     return getFile<ELFT>()->getObj();
   }
 
-  InputSection *getLinkOrderDep() const;
-
   void uncompress();
 
   // Returns a source location string. Used to construct an error message.
   template <class ELFT> std::string getLocation(uint64_t Offset);
   template <class ELFT> std::string getSrcMsg(uint64_t Offset);
   template <class ELFT> std::string getObjMsg(uint64_t Offset);
 
   template <class ELFT> void relocate(uint8_t *Buf, uint8_t *BufEnd);
   void relocateAlloc(uint8_t *Buf, uint8_t *BufEnd);
   template <class ELFT> void relocateNonAlloc(uint8_t *Buf, uint8_t *BufEnd);
 
   std::vector<Relocation> Relocations;
 
   template <typename T> llvm::ArrayRef<T> getDataAs() const {
     size_t S = Data.size();
     assert(S % sizeof(T) == 0);
     return llvm::makeArrayRef<T>((const T *)Data.data(), S / sizeof(T));
   }
 
+  InputSection *LinkOrderDep = nullptr;
+
 private:
   // A pointer that owns uncompressed data if a section is compressed by zlib.
   // Since the feature is not used often, this is usually a nullptr.
   std::unique_ptr<char[]> UncompressBuf;
 };
 
 // SectionPiece represents a piece of splittable section contents.
 // We allocate a lot of these and binary search on them. This means that they
 // have to be as compact as possible, which is why we don't store the size (can

ELF/InputSection.cpp

static bool isLiveByDefault(uint64_t Flags, uint32_t Type) {
 
   // Besides that, relocation sections can also be GCed because their
   // relocation target sections may be GCed. This doesn't really matter
   // in most cases because the linker usually consumes relocation
   // sections instead of emitting them, but -emit-reloc needs this.
   return Type != SHT_REL && Type != SHT_RELA;
 }
 
 InputSectionBase::InputSectionBase(InputFile *File, uint64_t Flags,
                                    uint32_t Type, uint64_t Entsize,
                                    uint32_t Link, uint32_t Info,
                                    uint32_t Alignment, ArrayRef<uint8_t> Data,
                                    StringRef Name, Kind SectionKind)
     : SectionBase(SectionKind, Name, Flags, Entsize, Alignment, Type, Info,
                   Link),
       File(File), Data(Data), Repl(this) {
   Live = isLiveByDefault(Flags, Type);
   Assigned = false;
   NumRelocations = 0;
   AreRelocsRela = false;
 
void InputSectionBase::uncompress() {
   this->Data = makeArrayRef((uint8_t *)UncompressBuf.get(), Size);
   this->Flags &= ~(uint64_t)SHF_COMPRESSED;
 }
 
 uint64_t SectionBase::getOffset(const DefinedRegular &Sym) const {
   return getOffset(Sym.Value);
 }
 
-InputSection *InputSectionBase::getLinkOrderDep() const {
-  if ((Flags & SHF_LINK_ORDER) && Link != 0) {
-    InputSectionBase *L = File->getSections()[Link];
-    if (auto *IS = dyn_cast<InputSection>(L))
-      return IS;
-    error(
-        "Merge and .eh_frame sections are not supported with SHF_LINK_ORDER " +
-        toString(L));
-  }
-  return nullptr;
-}
 
 // Returns a source location string. Used to construct an error message.
 template <class ELFT>
 std::string InputSectionBase::getLocation(uint64_t Offset) {
   // We don't have file for synthetic sections.
   if (getFile<ELFT>() == nullptr)
     return (Config->OutputFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")")
         .str();

ELF/MarkLive.cpp

template <class ELFT> void elf::markLive() {
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase *Sec : InputSections) {
     // .eh_frame is always marked as live now, but also it can reference to
     // sections that contain personality. We preserve all non-text sections
     // referred by .eh_frame here.
     if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec))
       scanEhFrameSection<ELFT>(*EH, Enqueue);
-    if (Sec->Flags & SHF_LINK_ORDER)
+    if (Sec->LinkOrderDep)
       continue;
     if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec))
       Enqueue(Sec, 0);
     else if (isValidCIdentifier(Sec->Name)) {
       CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
       CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec);
     }
   }

ELF/OutputSections.cpp

if (auto *Data = dyn_cast<BytesDataCommand>(Base))
       writeInt(Buf + Data->Offset, Data->Expression().getValue(), Data->Size);
 }
 
 static bool compareByFilePosition(InputSection *A, InputSection *B) {
   // Synthetic doesn't have link order dependecy, stable_sort will keep it last
   if (A->kind() == InputSectionBase::Synthetic ||
       B->kind() == InputSectionBase::Synthetic)
     return false;
-  InputSection *LA = A->getLinkOrderDep();
-  InputSection *LB = B->getLinkOrderDep();
-  OutputSection *AOut = LA->getParent();
-  OutputSection *BOut = LB->getParent();
+  OutputSection *AOut = A->LinkOrderDep->getParent();
+  OutputSection *BOut = B->LinkOrderDep->getParent();
   if (AOut != BOut)
     return AOut->SectionIndex < BOut->SectionIndex;
-  return LA->OutSecOff < LB->OutSecOff;
+  return A->LinkOrderDep->OutSecOff < B->LinkOrderDep->OutSecOff;
 }
 
 template <class ELFT>
 static void finalizeShtGroup(OutputSection *OS,
                              ArrayRef<InputSection *> Sections) {
   assert(Config->Relocatable && Sections.size() == 1);
 
   // sh_link field for SHT_GROUP sections should contain the section index of
   // the symbol table.
   OS->Link = InX::SymTab->getParent()->SectionIndex;
 
   // sh_info then contain index of an entry in symbol table section which
   // provides signature of the section group.
   ObjFile<ELFT> *Obj = Sections[0]->getFile<ELFT>();
   ArrayRef<SymbolBody *> Symbols = Obj->getSymbols();
   OS->Info = InX::SymTab->getSymbolIndex(Symbols[Sections[0]->Info]);
 }
 
+static Optional<uint32_t> getLinkOrder(ArrayRef<InputSection *> V) {
+  for (InputSection *IS : V)
+    if (IS->LinkOrderDep)
+      return IS->LinkOrderDep->getParent()->SectionIndex;
+  return None;
+}
+
 template <class ELFT> void OutputSection::finalize() {
   // Link order may be distributed across several InputSectionDescriptions
   // but sort must consider them all at once.
   std::vector<InputSection **> ScriptSections;
   std::vector<InputSection *> Sections;
   for (BaseCommand *Base : Commands)
     if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
       for (InputSection *&IS : ISD->Sections) {
         ScriptSections.push_back(&IS);
         Sections.push_back(IS);
       }
 
-  if (Flags & SHF_LINK_ORDER) {
+  if (Optional<uint32_t> LinkOrder = getLinkOrder(Sections)) {
     std::stable_sort(Sections.begin(), Sections.end(), compareByFilePosition);
     for (int I = 0, N = Sections.size(); I < N; ++I)
       *ScriptSections[I] = Sections[I];
 
-    // We must preserve the link order dependency of sections with the
-    // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
-    // need to translate the InputSection sh_link to the OutputSection sh_link,
-    // all InputSections in the OutputSection have the same dependency.
-    if (auto *D = Sections.front()->getLinkOrderDep())
-      Link = D->getParent()->SectionIndex;
+    // If -r is given we preserve SHF_LINK_ORDER flag. In that case we must
+    // preserve the link order dependency. The dependency is indicated by the
+    // sh_link field. We need to translate the InputSection sh_link to the
+    // OutputSection sh_link, all InputSections in the OutputSection have the
+    // same dependency.
+    if (this->Flags & SHF_LINK_ORDER)
+      this->Link = *LinkOrder;
   }
 
   if (Type == SHT_GROUP) {
     finalizeShtGroup<ELFT>(this, Sections);
     return;
   }
 
   if (!Config->CopyRelocs || (Type != SHT_RELA && Type != SHT_REL))

ELF/SyntheticSections.cpp

void elf::decompressAndMergeSections() {
   V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
 }
 
 MipsRldMapSection::MipsRldMapSection()
     : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, Config->Wordsize,
                        ".rld_map") {}
 
 ARMExidxSentinelSection::ARMExidxSentinelSection()
-    : SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,
-                       Config->Wordsize, ".ARM.exidx") {}
+    : SyntheticSection(SHF_ALLOC, SHT_ARM_EXIDX, Config->Wordsize,
+                       ".ARM.exidx") {}
 
 // Write a terminating sentinel entry to the end of the .ARM.exidx table.
 // This section will have been sorted last in the .ARM.exidx table.
 // This table entry will have the form:
 // | PREL31 upper bound of code that has exception tables | EXIDX_CANTUNWIND |
 // The sentinel must have the PREL31 value of an address higher than any
 // address described by any other table entry.
 void ARMExidxSentinelSection::writeTo(uint8_t *Buf) {
   // The Sections are sorted in order of ascending PREL31 address with the
   // sentinel last. We need to find the InputSection that precedes the
   // sentinel. By construction the Sentinel is in the last
   // InputSectionDescription as the InputSection that precedes it.
   OutputSection *C = getParent();
   auto ISD = std::find_if(C->Commands.rbegin(), C->Commands.rend(),
                           [](const BaseCommand *Base) {
                             return isa<InputSectionDescription>(Base);
                           });
   auto L = cast<InputSectionDescription>(*ISD);
   InputSection *Highest = L->Sections[L->Sections.size() - 2];
-  InputSection *LS = Highest->getLinkOrderDep();
+  InputSection *LS = Highest->LinkOrderDep;
   uint64_t S = LS->getParent()->Addr + LS->getOffset(LS->getSize());
   uint64_t P = getVA();
   Target->relocateOne(Buf, R_ARM_PREL31, S - P);
   write32le(Buf + 4, 0x1);
 }
 
 ThunkSection::ThunkSection(OutputSection *OS, uint64_t Off)
     : SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS,

test/ELF/arm-exidx-canunwind.s

 // CHECK-EXIDX-NEXT: Contents of section .ARM.extab:
 // 100ec + f28 = 11014 = __gxx_personality_v0
 // CHECK-EXIDX-NEXT: 100ec 280f0000 b0b0b000 00000000
 
 // CHECK-PT:          Name: .ARM.exidx
 // CHECK-PT-NEXT:     Type: SHT_ARM_EXIDX (0x70000001)
 // CHECK-PT-NEXT:     Flags [
 // CHECK-PT-NEXT:       SHF_ALLOC
-// CHECK-PT-NEXT:       SHF_LINK_ORDER
 // CHECK-PT-NEXT:     ]
 // CHECK-PT-NEXT:     Address: 0x100D4
 // CHECK-PT-NEXT:     Offset: 0xD4
 // CHECK-PT-NEXT:     Size: 24
 
 // CHECK-PT:          Type: PT_ARM_EXIDX (0x70000001)
 // CHECK-PT-NEXT:     Offset: 0xD4
 // CHECK-PT-NEXT:     VirtualAddress: 0x100D4
 // CHECK-PT-NEXT:     PhysicalAddress: 0x100D4
 // CHECK-PT-NEXT:     FileSize: 24
 // CHECK-PT-NEXT:     MemSize: 24
 // CHECK-PT-NEXT:     Flags [ (0x4)
 // CHECK-PT-NEXT:       PF_R (0x4)
 // CHECK-PT-NEXT:     ]
 // CHECK-PT-NEXT:     Alignment: 4
 // CHECK-PT-NEXT:   }

test/ELF/arm-exidx-link.s

 // REQUIRES: arm
 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t.o
 // RUN: ld.lld %t.o -o %t.so -shared
 // RUN: llvm-readobj -s %t.so | FileCheck %s
 
 // CHECK:      Name: .ARM.exidx
 // CHECK-NEXT: Type: SHT_ARM_EXIDX
 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
-// CHECK-NEXT:   SHF_LINK_ORDER
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address:
 // CHECK-NEXT: Offset:
 // CHECK-NEXT: Size:
-// CHECK-NEXT: Link: [[INDEX:.*]]
-
-// CHECK:      Index: [[INDEX]]
-// CHECK-NEXT: Name: .text
+// CHECK-NEXT: Link: 0
 
+// RUN: ld.lld %t.o -o %t2.o -r
+// RUN: llvm-readobj -s %t2.o | FileCheck %s --check-prefix=RELOC
+// RELOC:      Index: 1
+// RELOC-NEXT: Name: .text
+// RELOC:      Name: .ARM.exidx
+// RELOC-NEXT: Type: SHT_ARM_EXIDX
+// RELOC-NEXT: Flags [
+// RELOC-NEXT:   SHF_ALLOC
+// RELOC-NEXT:   SHF_LINK_ORDER
+// RELOC-NEXT: ]
+// RELOC-NEXT: Address:
+// RELOC-NEXT: Offset:
+// RELOC-NEXT: Size:
+// RELOC-NEXT: Link: 1
 
         f:
   .fnstart
   bx  lr
   .cantunwind
   .fnend

test/ELF/arm-exidx-order.s

 // CHECK-EXIDX-NEXT:  10114 0c0f0000 01000000
 
 // Check that PT_ARM_EXIDX program header has been generated that describes
 // the .ARM.exidx output section
 // CHECK-PT:          Name: .ARM.exidx
 // CHECK-PT-NEXT:     Type: SHT_ARM_EXIDX (0x70000001)
 // CHECK-PT-NEXT:     Flags [
 // CHECK-PT-NEXT:       SHF_ALLOC
-// CHECK-PT-NEXT:       SHF_LINK_ORDER
 // CHECK-PT-NEXT:     ]
 // CHECK-PT-NEXT:     Address: 0x100D4
 // CHECK-PT-NEXT:     Offset: 0xD4
 // CHECK-PT-NEXT:     Size: 80
 
 // CHECK-PT:          Type: PT_ARM_EXIDX (0x70000001)
 // CHECK-PT-NEXT:     Offset: 0xD4
 // CHECK-PT-NEXT:     VirtualAddress: 0x100D4

test/ELF/arm-exidx-output.s

  .cantunwind
  .fnend
 
 // CHECK:         Section {
 // CHECK:         Name: .ARM.exidx
 // CHECK-NEXT:    Type: SHT_ARM_EXIDX (0x70000001)
 // CHECK-NEXT:    Flags [
 // CHECK-NEXT:      SHF_ALLOC
-// CHECK-NEXT:      SHF_LINK_ORDER
 // CHECK-NEXT:    ]
 
 // CHECK-NOT:     Name: .ARM.exidx.text.f1
 // CHECK-NOT:     Name: .ARM.exidx.text.f2