Simplify handling of SHF_LINK_ORDER

[• rafael]

Summary

It seems a lot simpler to just sort the sections and let the relocations do the rest.

[ruiu]

I'm fine as long as Peter is OK with this.

[peter.smith]

Looks good to me. The earlier we can do the re-ordering the better.

I'm currently trying to investigate some test failures in libcxxabi, libcxx using libunwind to do with ARM exceptions. I've got 6 failures in libcxxabi and 44 failures in libcxx when I run it with lld on ARM [*]. I'll run this past the tests on Monday (getting too late in the evening for me to function properly). If I turn up any extra problems I'll let you know.

• Only difference I can find between ld.bfd and lld is that ld.bfd (and gold) generate a .cantunwind entry for sections that don't have a .ARM.exidx entry.

[peter.smith]

I ran the libcxx and libcxxabi test suites without any problems before and after this change, which is good news. I found out that the test failures were caused by libunwind depending on ld.bfd putting a sentinel EXIDX_CANTUNWIND as the last element of the table and have raised PR31091 to cover.

[• espindola]

287365

ELF/OutputSections.cpp

 }
 
 template <class ELFT>
 OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags)
     : OutputSectionBase(Name, Type, Flags) {
   this->Entsize = getEntsize<ELFT>(Type);
 }
 
+template <typename ELFT>
+static bool compareByFilePosition(InputSection<ELFT> *A,
+                                  InputSection<ELFT> *B) {
+  auto *LA = cast<InputSection<ELFT>>(A->getLinkOrderDep());
+  auto *LB = cast<InputSection<ELFT>>(B->getLinkOrderDep());
+  OutputSectionBase *AOut = LA->OutSec;
+  OutputSectionBase *BOut = LB->OutSec;
+  if (AOut != BOut)
+    return AOut->SectionIndex < BOut->SectionIndex;
+  return LA->OutSecOff < LB->OutSecOff;
+}
+
 template <class ELFT> void OutputSection<ELFT>::finalize() {
   if ((this->Flags & SHF_LINK_ORDER) && !this->Sections.empty()) {
+    std::sort(Sections.begin(), Sections.end(), compareByFilePosition<ELFT>);
+    Size = 0;
+    assignOffsets();
+
     // 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 = this->Sections.front()->getLinkOrderDep())
       this->Link = D->OutSec->SectionIndex;
   }
 

ELF/Writer.cpp

 
 template <class ELFT> void Writer<ELFT>::writeSectionsBinary() {
   uint8_t *Buf = Buffer->getBufferStart();
   for (OutputSectionBase *Sec : OutputSections)
     if (Sec->Flags & SHF_ALLOC)
       Sec->writeTo(Buf + Sec->Offset);
 }
 
-// Convert the .ARM.exidx table entries that use relative PREL31 offsets to
-// Absolute addresses. This form is internal to LLD and is only used to
-// make reordering the table simpler.
-static void ARMExidxEntryPrelToAbs(uint8_t *Loc, uint64_t EntryVA) {
-  uint64_t Addr = Target->getImplicitAddend(Loc, R_ARM_PREL31) + EntryVA;
-  bool InlineEntry =
-      (read32le(Loc + 4) == 1 || (read32le(Loc + 4) & 0x80000000));
-  if (InlineEntry)
-    // Set flag in unused bit of code address so that when we convert back we
-    // know which table entries to leave alone.
-    Addr |= 0x1;
-  else
-    write32le(Loc + 4,
-              Target->getImplicitAddend(Loc + 4, R_ARM_PREL31) + EntryVA + 4);
-  write32le(Loc, Addr);
-}
-
-// Convert the .ARM.exidx table entries from the internal to LLD form using
-// absolute addresses back to relative PREL31 offsets.
-static void ARMExidxEntryAbsToPrel(uint8_t *Loc, uint64_t EntryVA) {
-  uint64_t Off = read32le(Loc) - EntryVA;
-  // ARMExidxEntryPreltoAbs sets bit 0 if the table entry has inline data
-  // that is not an address
-  bool InlineEntry = Off & 0x1;
-  Target->relocateOne(Loc, R_ARM_PREL31, Off & ~0x1);
-  if (!InlineEntry)
-    Target->relocateOne(Loc + 4, R_ARM_PREL31,
-                        read32le(Loc + 4) - (EntryVA + 4));
-}
-
-// The table formed by the .ARM.exidx OutputSection has entries with two
-// 4-byte fields:
-// | PREL31 offset to function | Action to take for function |
-// The table must be ordered in ascending virtual address of the functions
-// identified by the first field of the table. Instead of using the
-// SHF_LINK_ORDER dependency to reorder the sections prior to relocation we
-// sort the table post-relocation.
-// Ref: Exception handling ABI for the ARM architecture
-static void sortARMExidx(uint8_t *Buf, uint64_t OutSecVA, uint64_t Size) {
-  struct ARMExidxEntry {
-    ulittle32_t Target;
-    ulittle32_t Action;
-  };
-  ARMExidxEntry *Start = (ARMExidxEntry *)Buf;
-  size_t NumEnt = Size / sizeof(ARMExidxEntry);
-  for (uint64_t Off = 0; Off < Size; Off += 8)
-    ARMExidxEntryPrelToAbs(Buf + Off, OutSecVA + Off);
-  std::stable_sort(Start, Start + NumEnt,
-                   [](const ARMExidxEntry &A, const ARMExidxEntry &B) {
-                     return A.Target < B.Target;
-                   });
-  for (uint64_t Off = 0; Off < Size; Off += 8)
-    ARMExidxEntryAbsToPrel(Buf + Off, OutSecVA + Off);
-}
-
 // Write section contents to a mmap'ed file.
 template <class ELFT> void Writer<ELFT>::writeSections() {
   uint8_t *Buf = Buffer->getBufferStart();
 
   // Finalize MIPS .reginfo and .MIPS.options sections
   // because they contain offsets to .got and _gp.
   if (In<ELFT>::MipsReginfo)
     In<ELFT>::MipsReginfo->finalize();
   if (In<ELFT>::MipsOptions)
     In<ELFT>::MipsOptions->finalize();
 
   // PPC64 needs to process relocations in the .opd section
   // before processing relocations in code-containing sections.
   Out<ELFT>::Opd = findSection(".opd");
   if (Out<ELFT>::Opd) {
     Out<ELFT>::OpdBuf = Buf + Out<ELFT>::Opd->Offset;
     Out<ELFT>::Opd->writeTo(Buf + Out<ELFT>::Opd->Offset);
   }
 
   for (OutputSectionBase *Sec : OutputSections)
     if (Sec != Out<ELFT>::Opd && Sec != Out<ELFT>::EhFrameHdr)
       Sec->writeTo(Buf + Sec->Offset);
 
-  OutputSectionBase *ARMExidx = findSection(".ARM.exidx");
-  if (!Config->Relocatable)
-    if (auto *OS = dyn_cast_or_null<OutputSection<ELFT>>(ARMExidx))
-      sortARMExidx(Buf + OS->Offset, OS->Addr, OS->Size);
-
   // The .eh_frame_hdr depends on .eh_frame section contents, therefore
   // it should be written after .eh_frame is written.
   if (!Out<ELFT>::EhFrame->empty() && Out<ELFT>::EhFrameHdr)
     Out<ELFT>::EhFrameHdr->writeTo(Buf + Out<ELFT>::EhFrameHdr->Offset);
 }
 
 template <class ELFT> void Writer<ELFT>::writeBuildId() {
   if (!In<ELFT>::BuildId || !In<ELFT>::BuildId->OutSec)