[ELF] - Fix "--symbol-ordering-file doesn't work with linker scripts"

[grimar]

Summary

This is PR33889,

Patch adds support of combination of linkerscript and
-symbol-ordering-file option.

If no sorting commands are present in script inside section declaration
and no --sort-section option specified, code uses sorting from ordering
file if any exist.

[grimar]

• Cosmetic changes.

[ruiu]

ELF/Config.h

80 ↗

(On Diff #108097)

SectionsOrder -> SectionOrder

I don't think it is a good idea to make this available everywhere. Please just keep SymbolOrderingFile like before. When you need SectionOrder, compute it and store it to a local variable.

ELF/LinkerScript.cpp

245

SymbolsOrder -> SymbolOrder

[grimar]

• Addressed review comments.

[ruiu]

This can be simplified, but I'll do that later. Please submit. LGTM

ELF/InputSection.h

private:
   void copyRelocations(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   template <class ELFT> void copyShtGroup(uint8_t *Buf);
 };
 
 // The list of all input sections.
 extern std::vector<InputSectionBase *> InputSections;
 
+// Builds section order for handling --symbol-ordering-file.
+template <class ELFT> llvm::DenseMap<SectionBase *, int> buildSectionOrder();
+
 } // namespace elf
 
 std::string toString(const elf::InputSectionBase *);
 } // namespace lld
 
 #endif

ELF/InputSection.cpp

 
 std::vector<InputSectionBase *> elf::InputSections;
 
 // Returns a string to construct an error message.
 std::string lld::toString(const InputSectionBase *Sec) {
   return (toString(Sec->File) + ":(" + Sec->Name + ")").str();
 }
 
+template <class ELFT> DenseMap<SectionBase *, int> elf::buildSectionOrder() {
+  // Build a map from symbols to their priorities. Symbols that didn't
+  // appear in the symbol ordering file have the lowest priority 0.
+  // All explicitly mentioned symbols have negative (higher) priorities.
+  DenseMap<StringRef, int> SymbolOrder;
+  int Priority = -Config->SymbolOrderingFile.size();
+  for (StringRef S : Config->SymbolOrderingFile)
+    SymbolOrder.insert({S, Priority++});
+
+  // Build a map from sections to their priorities.
+  DenseMap<SectionBase *, int> SectionOrder;
+  for (ObjFile<ELFT> *File : ObjFile<ELFT>::Instances) {
+    for (SymbolBody *Body : File->getSymbols()) {
+      auto *D = dyn_cast<DefinedRegular>(Body);
+      if (!D || !D->Section)
+        continue;
+      int &Priority = SectionOrder[D->Section];
+      Priority = std::min(Priority, SymbolOrder.lookup(D->getName()));
+    }
+  }
+  return SectionOrder;
+}
+
 template <class ELFT>
 static ArrayRef<uint8_t> getSectionContents(ObjFile<ELFT> *File,
                                             const typename ELFT::Shdr *Hdr) {
   if (!File || Hdr->sh_type == SHT_NOBITS)
     return makeArrayRef<uint8_t>(nullptr, Hdr->sh_size);
   return check(File->getObj().getSectionContents(Hdr));
 }
 
uint64_t MergeInputSection::getOffset(uint64_t Offset) const {
   const SectionPiece &Piece = *this->getSectionPiece(Offset);
   if (!Piece.Live)
     return 0;
 
   uint64_t Addend = Offset - Piece.InputOff;
   return Piece.OutputOff + Addend;
 }
 
+template DenseMap<SectionBase *, int> elf::buildSectionOrder<ELF32LE>();
+template DenseMap<SectionBase *, int> elf::buildSectionOrder<ELF32BE>();
+template DenseMap<SectionBase *, int> elf::buildSectionOrder<ELF64LE>();
+template DenseMap<SectionBase *, int> elf::buildSectionOrder<ELF64BE>();
+
 template InputSection::InputSection(ObjFile<ELF32LE> *, const ELF32LE::Shdr *,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF32BE> *, const ELF32BE::Shdr *,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64LE> *, const ELF64LE::Shdr *,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64BE> *, const ELF64BE::Shdr *,
                                     StringRef);

ELF/LinkerScript.cpp

 }
 
 static void sortSections(InputSection **Begin, InputSection **End,
                          SortSectionPolicy K) {
   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
     std::stable_sort(Begin, End, getComparator(K));
 }
 
+static llvm::DenseMap<SectionBase *, int> getSectionOrder() {
+  switch (Config->EKind) {
+  case ELF32LEKind:
+    return buildSectionOrder<ELF32LE>();
+  case ELF32BEKind:
+    return buildSectionOrder<ELF32BE>();
+  case ELF64LEKind:
+    return buildSectionOrder<ELF64LE>();
+  case ELF64BEKind:
+    return buildSectionOrder<ELF64BE>();
+  default:
+    llvm_unreachable("unknown ELF type");
+  }
+}
+
+static void sortBySymbolOrder(InputSection **Begin, InputSection **End) {
+  if (Config->SymbolOrderingFile.empty())
+    return;
+  static llvm::DenseMap<SectionBase *, int> Order = getSectionOrder();
+  MutableArrayRef<InputSection *> In(Begin, End - Begin);
+  sortByOrder(In, [&](InputSectionBase *S) { return Order.lookup(S); });
+}
+
 // Compute and remember which sections the InputSectionDescription matches.
 std::vector<InputSection *>
 LinkerScript::computeInputSections(const InputSectionDescription *Cmd) {
   std::vector<InputSection *> Ret;
 
   // Collects all sections that satisfy constraints of Cmd.
   for (const SectionPattern &Pat : Cmd->SectionPatterns) {
     size_t SizeBefore = Ret.size();
for (const SectionPattern &Pat : Cmd->SectionPatterns) {
     // line option is respected even if a SORT command is given, the exact
     // behavior we have here is a bit complicated. Here are the rules.
     //
     // 1. If two SORT commands are given, --sort-section is ignored.
     // 2. If one SORT command is given, and if it is not SORT_NONE,
     //    --sort-section is handled as an inner SORT command.
     // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
     // 4. If no SORT command is given, sort according to --sort-section.
+    // 5. If no SORT commands are given and --sort-section is not specified,
+    //    apply sorting provided by --symbol-ordering-file if any exist.
     InputSection **Begin = Ret.data() + SizeBefore;
     InputSection **End = Ret.data() + Ret.size();
+    if (Pat.SortOuter == SortSectionPolicy::Default &&
+        Config->SortSection == SortSectionPolicy::Default) {
+      sortBySymbolOrder(Begin, End);
+      continue;
+    }
     if (Pat.SortOuter != SortSectionPolicy::None) {
       if (Pat.SortInner == SortSectionPolicy::Default)
         sortSections(Begin, End, Config->SortSection);
       else
         sortSections(Begin, End, Pat.SortInner);
       sortSections(Begin, End, Pat.SortOuter);
     }
   }

ELF/OutputSections.h

void addInputSec(InputSectionBase *IS, StringRef OutsecName,
                    OutputSection *&Sec);
 
 private:
   llvm::SmallDenseMap<SectionKey, OutputSection *> Map;
 };
 
 uint64_t getHeaderSize();
 void reportDiscarded(InputSectionBase *IS);
+void sortByOrder(llvm::MutableArrayRef<InputSection *> In,
+                 std::function<int(InputSectionBase *S)> Order);
 
 extern std::vector<OutputSection *> OutputSections;
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/OutputSections.cpp

 // any special treatment on top of progbits, so there doesn't
 // seem to be a harm in merging them.
 static bool canMergeToProgbits(unsigned Type) {
   return Type == SHT_NOBITS || Type == SHT_PROGBITS || Type == SHT_INIT_ARRAY ||
          Type == SHT_PREINIT_ARRAY || Type == SHT_FINI_ARRAY ||
          Type == SHT_NOTE;
 }
 
+void elf::sortByOrder(MutableArrayRef<InputSection *> In,
+                      std::function<int(InputSectionBase *S)> Order) {
+  typedef std::pair<int, InputSection *> Pair;
+  auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
+
+  std::vector<Pair> V;
+  for (InputSection *S : In)
+    V.push_back({Order(S), S});
+  std::stable_sort(V.begin(), V.end(), Comp);
+
+  for (size_t I = 0; I < V.size(); ++I)
+    In[I] = V[I].second;
+}
+
 void elf::reportDiscarded(InputSectionBase *IS) {
   if (!Config->PrintGcSections)
     return;
   message("removing unused section from '" + IS->Name + "' in file '" +
           IS->File->getName() + "'");
 }
 
 void OutputSectionFactory::addInputSec(InputSectionBase *IS,
uint64_t elf::getHeaderSize() {
   return Out::ElfHeader->Size + Out::ProgramHeaders->Size;
 }
 
 bool OutputSection::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;
 }
 
 void OutputSection::sort(std::function<int(InputSectionBase *S)> Order) {
-  typedef std::pair<int, InputSection *> Pair;
-  auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
-
-  std::vector<Pair> V;
   assert(Commands.size() == 1);
-  auto *ISD = cast<InputSectionDescription>(Commands[0]);
-  for (InputSection *S : ISD->Sections)
-    V.push_back({Order(S), S});
-  std::stable_sort(V.begin(), V.end(), Comp);
-  ISD->Sections.clear();
-  for (Pair &P : V)
-    ISD->Sections.push_back(P.second);
+  sortByOrder(cast<InputSectionDescription>(Commands[0])->Sections, Order);
 }
 
 // Fill [Buf, Buf + Size) with Filler.
 // This is used for linker script "=fillexp" command.
 static void fill(uint8_t *Buf, size_t Size, uint32_t Filler) {
   size_t I = 0;
   for (; I + 4 < Size; I += 4)
     memcpy(Buf + I, &Filler, 4);

ELF/Writer.cpp

if (Cmd)
     Cmd->sortCtorsDtors();
 }
 
 // Sort input sections using the list provided by --symbol-ordering-file.
 template <class ELFT> static void sortBySymbolsOrder() {
   if (Config->SymbolOrderingFile.empty())
     return;
 
-  // Build a map from symbols to their priorities. Symbols that didn't
-  // appear in the symbol ordering file have the lowest priority 0.
-  // All explicitly mentioned symbols have negative (higher) priorities.
-  DenseMap<StringRef, int> SymbolOrder;
-  int Priority = -Config->SymbolOrderingFile.size();
-  for (StringRef S : Config->SymbolOrderingFile)
-    SymbolOrder.insert({S, Priority++});
-
-  // Build a map from sections to their priorities.
-  DenseMap<SectionBase *, int> SectionOrder;
-  for (ObjFile<ELFT> *File : ObjFile<ELFT>::Instances) {
-    for (SymbolBody *Body : File->getSymbols()) {
-      auto *D = dyn_cast<DefinedRegular>(Body);
-      if (!D || !D->Section)
-        continue;
-      int &Priority = SectionOrder[D->Section];
-      Priority = std::min(Priority, SymbolOrder.lookup(D->getName()));
-    }
-  }
-
   // Sort sections by priority.
+  DenseMap<SectionBase *, int> SectionOrder = buildSectionOrder<ELFT>();
   for (BaseCommand *Base : Script->Opt.Commands)
     if (auto *Sec = dyn_cast<OutputSection>(Base))
       Sec->sort([&](InputSectionBase *S) { return SectionOrder.lookup(S); });
 }
 
 template <class ELFT>
 void Writer<ELFT>::forEachRelSec(std::function<void(InputSectionBase &)> Fn) {
   for (InputSectionBase *IS : InputSections) {

test/ELF/linkerscript/symbol-ordering-file.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: echo "SECTIONS { .foo : { *(.foo) } }" > %t.script
+
+# RUN: ld.lld %t.o --script %t.script -o %t.out
+# RUN: llvm-objdump -s %t.out| FileCheck %s --check-prefix=BEFORE
+# BEFORE:      Contents of section .foo:
+# BEFORE-NEXT: 1122 
+
+# RUN: echo "_foo2" > %t.ord
+# RUN: echo "_foo1" >> %t.ord
+# RUN: ld.lld --symbol-ordering-file %t.ord %t.o --script %t.script -o %t2.out
+# RUN: llvm-objdump -s %t2.out| FileCheck %s --check-prefix=AFTER
+# AFTER:      Contents of section .foo:
+# AFTER-NEXT: 2211
+
+.section .foo,"ax",@progbits,unique,1
+_foo1:
+ .byte 0x11
+
+.section .foo,"ax",@progbits,unique,2
+_foo2:
+ .byte 0x22