[ELF] - Linkerscript: Implemented SORT command

[grimar]

Summary

When the SORT keyword is used, the linker will sort the files or sections into ascending order by name before placing them in the output file.
It is used in FreeBSD script:
https://svnweb.freebsd.org/base/head/sys/conf/ldscript.amd64?revision=284870&view=markup#l139

This is PR28689.

[evgeny777]

ELF/LinkerScript.cpp

137 ↗

(On Diff #65327)

What about SORT(*(.data))? How will .data sections be ordered?

664 ↗

(On Diff #65327)

I would check for "SORT" in readOutputSectionDescription.

[grimar]

ELF/LinkerScript.cpp

137 ↗

(On Diff #65327)

In the same order as linker see them ?

[evgeny777]

ELF/LinkerScript.cpp

137 ↗

(On Diff #65327)

The should be sorted by file names, I think.

[grimar]

ELF/LinkerScript.cpp

137 ↗

(On Diff #65327)

SORT is alias for SORT_BY_NAME.
I do not see anything about sorting by filename in that case.
(https://sourceware.org/binutils/docs/ld/Input-Section-Wildcards.html#Input-Section-Wildcards)

[evgeny777]

ELF/LinkerScript.cpp

137 ↗

(On Diff #65327)

Here is the quote from URL you posted

When the SORT_BY_NAME keyword is used, the linker will sort the files or sections into ascending order by name before placing them in the output file.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

137 ↗

(On Diff #65336)

Agree.

664 ↗

(On Diff #65327)

I prefer my way.
KEEP is just a part of IS description. Input section wildcard can be surrounded by KEEP.
(https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep).

SORT as well as other attributes like EXCLUDE_FILE is relative to wildcards itself. It is not at the same level as KEEP in my understanding.

[evgeny777]

ELF/LinkerScript.cpp

139 ↗

(On Diff #65336)

What exact sorting order should be used? Shouldn't file name have greater priority than section name?

Also how about this one:

*(SORT(*.data.*))

vs this one:

SORT(*)(*.data.*)

[grimar]

ELF/LinkerScript.cpp

139 ↗

(On Diff #65336)

I think my first iteration was correct. SORT can be applied both to sections and to filenames separatelly. Since I am applying it for sections here, no need to sort filenames.
As you mentioned documentation says "the linker will sort the files or sections into ascending order by name". Its a bit confusing, but says correct thing. files OR sections. I am going to revert this to previous iteration.

[grimar]

• Reverted to initial revision.
• Improved testcase.

[emaste]

ELF/LinkerScript.cpp

139 ↗

(On Diff #65336)

Right, it should sort by file or section names independently I think; the common use case is for ctor and dtor section names (this is the case for FreeBSD) and it's definitely the section name that's important there.

KEEP (*(SORT(.dtors.*)))

For reproducible builds though we do want to make sure the sort is stable / deterministic in the non-sorted field.

[emaste]

ELF/LinkerScript.cpp

139 ↗

(On Diff #65341)

My comment crossed your update. To be clear, I think the current version of this block is correct.

[grimar]

ELF/LinkerScript.cpp

139 ↗

(On Diff #65341)

Yep, I understood. Thanks !
Btw I think I never saw sorting by filenames in scripts. I think it is not common and we can postpone the support. What do you think ?

[emaste]

Btw I think I never saw sorting by filenames in scripts. I think it is not common and we can postpone the support. What do you think ?

That seems sensible to me. I'm not aware of linker scripts that sort by filename, and I can't really come up with a compelling use case for it.

[ruiu]

ELF/LinkerScript.cpp

133 ↗

(On Diff #65341)

I don't really want to add more code to this function as it's getting too complicated. Actually it needs to lose weight. Please hold on while I'm trying to split it.

[grimar]

Recent change that introduced LinkerScript<ELFT>::getSectionMap() does not allow
this patch to fit well.
Since I need to know Sort flag state for each InputSectionDescription.
With current code that looks to be impossible.
I am holding this until we have another approach landed.

[grimar]

To clarify what I meant here is that D22683 csuggest some approach, so it would cross my code if I would try to
change something here, so I plan to wait until tomorrow, may be it be landed or some other solution will. If not - I'll suggest the change
requred for this patch to work then.

[ruiu]

I think you should be able to make this change by changing the return type of getSectionMap from std::vector<std::pair<StringRef, ArrayRef<StringRef>> to std::vector<std::pair<StringRef, BaseCommand *>>. The point is that it is not okay to add more and more code to a single function.

[grimar]

In D22749#496455, @ruiu wrote:

I think you should be able to make this change by changing the return type of getSectionMap from std::vector<std::pair<StringRef, ArrayRef<StringRef>> to std::vector<std::pair<StringRef, BaseCommand *>>. The point is that it is not okay to add more and more code to a single function.

Yep, I thought about that, and that finally makes getSectionMap() to be very close with loop on commands, like it was before. May be getSectionMap() is itself excessive ?

[ruiu]

I don't know yet, but we need to do something. It's probably nice to slow down a bit and make the code simpler and easier to read.

[grimar]

Anyways, I`ll update this patch tomorrow, using your suggestion for start for example and we can see then how it looks.

[emaste]

I don't know yet, but we need to do something. It's probably nice to slow down a bit and make the code simpler and easier to read.

One little comment, we're now quite close to fully handling the FreeBSD kernel linker script.

What's missing:

1. AT (D19272)
2. SORT (D22749)
3. Filename specification (e.g. KEEP (*crtbegin.o(.ctors)))
4. EXCLUDE_FILE (D22795)
5. CONSTRUCTORS
6. . = assignment in output section (PR28720)

I think CONSTRUCTORS is just a nop for ELF (and we can delete it from the linker script) and PR28720 can also be addressed easily in FreeBSD's linker script instead of changing lld.

At least as far as the FreeBSD base system and kernel is concerned there's not much left to implement, regardless of whether we pause now to refactor and clean up or not.

ELF/LinkerScript.cpp

139 ↗

(On Diff #65341)

Yes I think it's sensible to postpone support for sorting by filename.

[grimar]

• Rebased.

[grimar]

In D22749#496533, @emaste wrote:

1. Filename specification (e.g. KEEP (*crtbegin.o(.ctors)))

it is D22852.

#CONSTRUCTORS

Constructors is D22848.

[grimar]

• Removed redundant methods.

[grimar]

• Updated comment.

[grimar]

• Removed unrelated change.

[ruiu]

ELF/LinkerScript.cpp

113–123 ↗

(On Diff #65706)

This change makes me wonder why we need the Factory in the linker script. We need to create output sections as instructed by linker scripts. But, the factory may create different output sections with the same name. I started to think that this is not correct.

ELF/LinkerScript.h

137 ↗

(On Diff #65706)

ArrayRef?

[grimar]

ELF/LinkerScript.cpp

113–123 ↗

(On Diff #65706)

Do you mean D22516 and following little discussion about Rafael's experiments in maillist ?
We can think about how to fix that, but since gnu linkers work in that way for a long time, it is probably not so urgent now.

[grimar]

• Addressed review comments + refactored.

[grimar]

By the way, if we create bool Keep field in InputSectionDescription,
that can help to remove the Keep argument from few methods.
I know that Keep is not used after parcing since we have a separate array for keeped sections, but probably that
make code a bit cleaner and can worth that little field.

ELF/LinkerScript.h

137 ↗

(On Diff #65706)

Ok. Though it is ArrayRef<std:unique_ptr<...>> then. I am not sure why,
but I feel it is a bit strange combination.

[ruiu]

ELF/LinkerScript.cpp

120–123 ↗

(On Diff #65894)

This little helper seems to take too much arguments. I'd be nice if you can reduce it (though I have no clear idea how.)

728–730 ↗

(On Diff #65894)

Format.

767 ↗

(On Diff #65894)

peek().startswith("*")

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

120–123 ↗

(On Diff #65894)

I suggest to do sort in separate method then. It helps here + if we will want one day
to support sorting by file name or SORT_BY_ALIGNMENT, we should be able just to extend it/modify.

728–730 ↗

(On Diff #65894)

Fixed.

767 ↗

(On Diff #65894)

Done (in separate NFC commit).

[ruiu]

ELF/LinkerScript.cpp

153 ↗

(On Diff #66042)

Candidate for what? Maybe just Sections is better.

162 ↗

(On Diff #66042)

I don't think making this a separate function improves readability. This is probably better.

if (InCmd->Sort)
  std::stable_sort(Candidates.begin(), Candidates.end(), compareByName);

where compareByName is a separate file-scope function.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

153 ↗

(On Diff #66042)

For adding :) Changed to Sections.

162 ↗

(On Diff #66042)

Done.

[grimar]

• Just rebase.

[• rafael]

There are at least two independent cleanups. They LGTM. Can you commit them and rebase this?

ELF/LinkerScript.cpp

119 ↗

(On Diff #66092)

Can you commit making this a static function as an independent cleanup?

ELF/LinkerScript.h

145 ↗

(On Diff #66092)

Can you commit just the change to return more info first?

[• rafael]

ELF/LinkerScript.cpp

147 ↗

(On Diff #66092)

Maybe getSectionMap should do this filtering?

[grimar]

ELF/LinkerScript.cpp

119 ↗

(On Diff #66092)

This probably intersects with getSectionMap() change, so it probably be a single cleanup patch. Looking.

147 ↗

(On Diff #66092)

For this patch this probably be fine, though generally we can need another commands afaik.
Let me quickly prepare separate cleanup patch(s) with this and other changes.

[grimar]

ELF/LinkerScript.cpp

147 ↗

(On Diff #66092)

Ah no, that is probably not fine. That way getSectionMap() should create and return array of InputSectionDescriptions instead of returning array of commands that already exist. Not sure it is better since we anyways will want to access other commands as well.
This cleanup patch is D22962.

[grimar]

• Rebased.

[grimar]

• clang-format.

[ruiu]

LGTM

lld/trunk/ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}
   static bool classof(const BaseCommand *C);
   StringRef FilePattern;
+  bool Sort = false;
   std::vector<StringRef> ExcludedFiles;
   std::vector<StringRef> SectionPatterns;
 };
 
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;

lld/trunk/ELF/LinkerScript.cpp

static void addSection(OutputSectionFactory<ELFT> &Factory,
   bool IsNew;
   std::tie(Sec, IsNew) = Factory.create(C, Name);
   if (IsNew)
     Out.push_back(Sec);
   Sec->addSection(C);
 }
 
 template <class ELFT>
+static bool compareByName(InputSectionBase<ELFT> *A,
+                          InputSectionBase<ELFT> *B) {
+  return A->getSectionName() < B->getSectionName();
+}
+
+template <class ELFT>
 std::vector<OutputSectionBase<ELFT> *>
 LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   std::vector<OutputSectionBase<ELFT> *> Ret;
 
   for (auto &P : getSectionMap()) {
+    std::vector<InputSectionBase<ELFT> *> Sections;
     StringRef OutputName = P.first;
     const InputSectionDescription *I = P.second;
     for (InputSectionBase<ELFT> *S : getInputSections(I)) {
       if (OutputName == "/DISCARD/") {
         S->Live = false;
         reportDiscarded(S);
         continue;
       }
-      addSection(Factory, Ret, S, OutputName);
+      Sections.push_back(S);
     }
+    if (I->Sort)
+      std::stable_sort(Sections.begin(), Sections.end(), compareByName<ELFT>);
+    for (InputSectionBase<ELFT> *S : Sections)
+      addSection(Factory, Ret, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())
       if (!isDiscarded(S) && !S->OutSec)
         addSection(Factory, Ret, S, getOutputSectionName(S));
private:
   void readSearchDir();
   void readSections();
 
   SymbolAssignment *readAssignment(StringRef Name);
   void readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   std::unique_ptr<InputSectionDescription> readInputSectionDescription();
+  void readInputFilePattern(InputSectionDescription *InCmd, bool Keep);
   void readInputSectionRules(InputSectionDescription *InCmd, bool Keep);
   unsigned readPhdrType();
   void readProvide(bool Hidden);
   void readAlign(OutputSectionCommand *Cmd);
   void readSort();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
return StringSwitch<int>(Op)
       .Case(">=", 2)
       .Case("<=", 2)
       .Case("==", 2)
       .Case("!=", 2)
       .Case("&", 1)
       .Default(-1);
 }
 
-void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd, bool Keep) {
+void ScriptParser::readInputFilePattern(InputSectionDescription *InCmd,
+                                        bool Keep) {
+  while (!Error && !skip(")")) {
+    if (Keep)
+      Opt.KeptSections.push_back(peek());
+    InCmd->SectionPatterns.push_back(next());
+  }
+}
+
+void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd,
+                                         bool Keep) {
   InCmd->FilePattern = next();
   expect("(");
 
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     while (!Error && !skip(")"))
       InCmd->ExcludedFiles.push_back(next());
   }
 
-  while (!Error && !skip(")")) {
-    if (Keep)
-      Opt.KeptSections.push_back(peek());
-    InCmd->SectionPatterns.push_back(next());
+  if (skip("SORT")) {
+    expect("(");
+    InCmd->Sort = true;
+    readInputFilePattern(InCmd, Keep);
+    expect(")");
+    return;
   }
+
+  readInputFilePattern(InCmd, Keep);
 }
 
 std::unique_ptr<InputSectionDescription>
 ScriptParser::readInputSectionDescription() {
   auto InCmd = llvm::make_unique<InputSectionDescription>();
 
   // Input section wildcard can be surrounded by KEEP.
   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep

lld/trunk/test/ELF/linkerscript/Inputs/linkerscript-sort.s

+.section .aaa.5, "a"
+.quad 0x55
+
+.section .aaa.1, "a"
+.quad 0x11
+
+.section .aaa.3, "a"
+.quad 0x33
+
+.section .aaa.2, "a"
+.quad 0x22
+
+.section .aaa.4, "a"
+.quad 0x44

lld/trunk/test/ELF/linkerscript/linkerscript-sort.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+# RUN:   %p/Inputs/linkerscript-sort.s -o %t2.o
+
+# RUN: echo "SECTIONS { .aaa : { *(.aaa.*) } }" > %t1.script
+# RUN: ld.lld -o %t1 --script %t1.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=UNSORTED %s
+# UNSORTED:      Contents of section .aaa:
+# UNSORTED-NEXT:   0120 55000000 00000000 11000000 00000000
+# UNSORTED-NEXT:   0130 33000000 00000000 22000000 00000000
+# UNSORTED-NEXT:   0140 44000000 00000000 05000000 00000000
+# UNSORTED-NEXT:   0150 01000000 00000000 03000000 00000000
+# UNSORTED-NEXT:   0160 02000000 00000000 04000000 00000000
+
+## Check that SORT works (sorted by name of section).
+# RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SORTED_A %s
+# SORTED_A:      Contents of section .aaa:
+# SORTED_A-NEXT:  0120 11000000 00000000 01000000 00000000
+# SORTED_A-NEXT:  0130 22000000 00000000 02000000 00000000
+# SORTED_A-NEXT:  0140 33000000 00000000 03000000 00000000
+# SORTED_A-NEXT:  0150 44000000 00000000 04000000 00000000
+# SORTED_A-NEXT:  0160 55000000 00000000 05000000 00000000
+
+## When we switch the order of files, check that sorting by
+## section names is stable.
+# RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t3.script
+# RUN: ld.lld -o %t3 --script %t3.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_B %s
+# SORTED_B:      Contents of section .aaa:
+# SORTED_B-NEXT:  0120 01000000 00000000 11000000 00000000
+# SORTED_B-NEXT:  0130 02000000 00000000 22000000 00000000
+# SORTED_B-NEXT:  0140 03000000 00000000 33000000 00000000
+# SORTED_B-NEXT:  0150 04000000 00000000 44000000 00000000
+# SORTED_B-NEXT:  0160 05000000 00000000 55000000 00000000
+
+## Check that SORT surrounded with KEEP also works.
+# RUN: echo "SECTIONS { .aaa : { KEEP (*(SORT(.aaa.*))) } }" > %t3.script
+# RUN: ld.lld -o %t3 --script %t3.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_A %s
+
+.global _start
+_start:
+ nop
+
+.section .aaa.5, "a"
+.quad 5
+
+.section .aaa.1, "a"
+.quad 1
+
+.section .aaa.3, "a"
+.quad 3
+
+.section .aaa.2, "a"
+.quad 2
+
+.section .aaa.4, "a"
+.quad 4