[ELF] - Implemented --sort-section cmd line option and SORT_NONE script command.

[grimar]

Summary

This fixes Bug 30385 - SORT_NONE not implemented,

`SORT_NONE' disables section sorting by ignoring the command line
section sorting option.

That is why this patch also implements --sort-section option.

Full rules of applying sorting (from ld manual) are:

When both command line section sorting option and linker script

section sorting command are used, section sorting command always takes
precedence over the command line option.

If the section sorting command in linker script isn't nested, the

command line option will make the section sorting command to be treated
as nested sorting command.

1. SORT_BY_NAME' (wildcard section pattern ) with --sort-sections alignment' is equivalent to SORT_BY_NAME' (SORT_BY_ALIGNMENT' (wildcard section pattern)).
2. SORT_BY_ALIGNMENT' (wildcard section pattern) with --sort-section name' is equivalent to SORT_BY_ALIGNMENT' (SORT_BY_NAME' (wildcard section pattern)).
   
   If the section sorting command in linker script is nested, the

command line option will be ignored.

[• rafael]

ELF/LinkerScript.cpp

1010

Please change the Config to store the parsed enum value.
Can you make it an error to pass an unknown value?

[grimar]

ELF/LinkerScript.cpp

1010

Ok, sure.

[ruiu]

ELF/LinkerScript.cpp

979–981

This naming scheme is confusing. SORT_NONE is mapped to SortDisabled, and SortNone doesn't mean SORT_NONE?

1035

We are reading something here, but you are applying? This function name doesn't feel right.

[grimar]

ELF/LinkerScript.cpp

979–981

Yes, a bit confusing, but according to documentation SORT_NONE is used to _disable_ sorting. A agree that probably better to map it to SortNone, but what is better name for absence of sorting (which is none) ? SortEmpty probably ?

[ruiu]

ELF/LinkerScript.cpp

979–981

I don't know. Null, Empty, Void, Dont, etc... Nothing feels right. I thought about it for a few minutes but didn't come up with a good name. Maybe just return 0?

[grimar]

ELF/LinkerScript.cpp

979–981

It is probably a bit strange to return 0 when we have enum. Also problem is that we use the code like that:

if (Cmd->SortInner)
  std::stable_sort(V.begin(), V.end(), getComparator(Cmd->SortInner));
if (Cmd->SortOuter)
  std::stable_sort(V.begin(), V.end(), getComparator(Cmd->SortOuter));

So in that case for this to work we will need to modify start value of enum:

enum SortKind { SortDisabled = 1, SortByName, SortByAlignment };

What is not very beautiful IMO. I`ll think more about that.

[ruiu]

ELF/LinkerScript.cpp

979–981

If you don't come up with a good name, I don't think = 1 is ugly.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

979–981

I tried this, but result was not very clean: D24655

But then during addressing Rafael's comments, anyways I found that probably anyways we want to have SortSectionPolicy that does not need to duplcate entries of SortKind enum and can be reused for linkerscript, so I ended with current code, I think it is looks much more clear.

1035

I think we read sort kind in readSortKind() above, by "applying" I was mean that we select/calculate/apply final value basing on rules. Renamed to selectSortKind.

[• rafael]

I like it. It adds a separation from parsing and deciding which sorting to actually use.

LGTM, but wait to see if Rui agrees.

[ruiu]

ELF/LinkerScript.cpp

130–134

Convert this to a switch with a default statement with llvm_unreacahble, so that it reports an error if SortSectionPolicy is not one of Priority, Name nor Alignment.

988

It's hard to figure out the final output of this function. Can you describe it for me? I think it's hard to understand because you update Cmd and then fix its members in the second pass using this function. Why don't you set the proper values in the first place in one shot?

[grimar]

ELF/LinkerScript.cpp

988

In short: you have SORT type specified by --sort-section in Config->SortSection and types that are specified in script. Depending on if you have Outer/Inner rule set by script for sections it should either ignore either use or even mix with rules from --sort-section.
So final output is mixing commandline and script.

This SORT applying logic is described at https://sourceware.org/binutils/docs/ld/Input-Section-Wildcards.html page and it is not just that trivial,
so I think it is much better to split reading of the script and mixing sorting types, like this method do to keep logic simplier.

[ruiu]

LGTM. I have an idea to simplify but it is probably beyond being a code review comment, so please go ahead. I'll make a patch and send it to you.

[grimar]

In D24604#545191, @ruiu wrote:

LGTM. I have an idea to simplify but it is probably beyond being a code review comment, so please go ahead. I'll make a patch and send it to you.

Thanks ! That have a conflicts now, I am plan to resolve it and commit at my early tomorrow.

[grimar]

In D24604#545247, @grimar wrote:

In D24604#545191, @ruiu wrote:

LGTM. I have an idea to simplify but it is probably beyond being a code review comment, so please go ahead. I'll make a patch and send it to you.

Thanks ! That have a conflicts now, I am plan to resolve it and commit at my early tomorrow.

Conflicts were trivial though, so r281771.

ELF/Config.h

 enum class DiscardPolicy { Default, All, Locals, None };
 
 // For --strip-{all,debug}.
 enum class StripPolicy { None, All, Debug };
 
 // For --unresolved-symbols.
 enum class UnresolvedPolicy { NoUndef, ReportError, Warn, Ignore };
 
+// For --sort-section and linkerscript sorting rules.
+enum class SortSectionPolicy { None, IgnoreConfig, Alignment, Name, Priority };
+
 struct SymbolVersion {
   llvm::StringRef Name;
   bool IsExternCpp;
   bool HasWildcards;
 };
 
 // This struct contains symbols version definition that
 // can be found in version script if it is used for link.
struct Configuration {
   bool WarnCommon;
   bool ZCombreloc;
   bool ZExecStack;
   bool ZNodelete;
   bool ZNow;
   bool ZOrigin;
   bool ZRelro;
   DiscardPolicy Discard;
+  SortSectionPolicy SortSection;
   StripPolicy Strip = StripPolicy::None;
   UnresolvedPolicy UnresolvedSymbols;
   BuildIdKind BuildId = BuildIdKind::None;
   ELFKind EKind = ELFNoneKind;
   uint16_t DefaultSymbolVersion = llvm::ELF::VER_NDX_GLOBAL;
   uint16_t EMachine = llvm::ELF::EM_NONE;
   uint64_t EntryAddr = 0;
   uint64_t ImageBase;

ELF/Driver.cpp

if (auto *Arg = Args.getLastArg(OPT_Ttext))
     Ret[".text"] = parseSectionAddress(Arg->getValue(), Arg);
   if (auto *Arg = Args.getLastArg(OPT_Tdata))
     Ret[".data"] = parseSectionAddress(Arg->getValue(), Arg);
   if (auto *Arg = Args.getLastArg(OPT_Tbss))
     Ret[".bss"] = parseSectionAddress(Arg->getValue(), Arg);
   return Ret;
 }
 
+static SortSectionPolicy getSortKind(opt::InputArgList &Args) {
+  StringRef S = getString(Args, OPT_sort_section);
+  if (S == "alignment")
+    return SortSectionPolicy::Alignment;
+  if (S == "name")
+    return SortSectionPolicy::Name;
+  if (!S.empty())
+    error("unknown --sort-section rule: " + S);
+  return SortSectionPolicy::None;
+}
+
 // Initializes Config members by the command line options.
 void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   for (auto *Arg : Args.filtered(OPT_L))
     Config->SearchPaths.push_back(Arg->getValue());
 
   std::vector<StringRef> RPaths;
   for (auto *Arg : Args.filtered(OPT_rpath))
     RPaths.push_back(Arg->getValue());
void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   for (auto *Arg : Args.filtered(OPT_auxiliary))
     Config->AuxiliaryList.push_back(Arg->getValue());
   if (!Config->Shared && !Config->AuxiliaryList.empty())
     error("-f may not be used without -shared");
 
   for (auto *Arg : Args.filtered(OPT_undefined))
     Config->Undefined.push_back(Arg->getValue());
 
+  Config->SortSection = getSortKind(Args);
+
   Config->UnresolvedSymbols = getUnresolvedSymbolOption(Args);
 
   if (auto *Arg = Args.getLastArg(OPT_dynamic_list))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       parseDynamicList(*Buffer);
 
   for (auto *Arg : Args.filtered(OPT_export_dynamic_symbol))
     Config->DynamicList.push_back(Arg->getValue());

ELF/LinkerScript.h

 //===- LinkerScript.h -------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_LINKER_SCRIPT_H
 #define LLD_ELF_LINKER_SCRIPT_H
 
+#include "Config.h"
 #include "Strings.h"
 #include "Writer.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Regex.h"
struct OutputSectionCommand : BaseCommand {
   Expr LmaExpr;
   Expr SubalignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
-enum SortKind { SortNone, SortByPriority, SortByName, SortByAlignment };
-
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
       : BaseCommand(InputSectionKind),
         FileRe(compileGlobPatterns({FilePattern})) {}
   static bool classof(const BaseCommand *C);
   llvm::Regex FileRe;
-  SortKind SortOuter = SortNone;
-  SortKind SortInner = SortNone;
+  SortSectionPolicy SortOuter = SortSectionPolicy::None;
+  SortSectionPolicy SortInner = SortSectionPolicy::None;
   llvm::Regex ExcludedFileRe;
   llvm::Regex SectionRe;
 };
 
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
   static bool classof(const BaseCommand *C);
   Expr Expression;

ELF/LinkerScript.cpp

 static bool compareAlignment(InputSectionData *A, InputSectionData *B) {
   // ">" is not a mistake. Larger alignments are placed before smaller
   // alignments in order to reduce the amount of padding necessary.
   // This is compatible with GNU.
   return A->Alignment > B->Alignment;
 }
 
 static std::function<bool(InputSectionData *, InputSectionData *)>
-getComparator(SortKind K) {
-  if (K == SortByPriority)
+getComparator(SortSectionPolicy K) {
+  if (K == SortSectionPolicy::Priority)
     return comparePriority;
-  if (K == SortByName)
+  if (K == SortSectionPolicy::Name)
     return compareName;
   return compareAlignment;
 }
 
 static bool checkConstraint(uint64_t Flags, ConstraintKind Kind) {
   bool RO = (Kind == ConstraintKind::ReadOnly);
   bool RW = (Kind == ConstraintKind::ReadWrite);
   bool Writable = Flags & SHF_WRITE;
   return !(RO && Writable) && !(RW && !Writable);
 }
if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base.get())) {
       OutCmd->GoesAfter = Ret.empty() ? nullptr : Ret.back();
       continue;
     }
 
     auto *Cmd = cast<InputSectionDescription>(Base.get());
     std::vector<InputSectionBase<ELFT> *> V = getInputSections(Cmd);
     if (!matchConstraints<ELFT>(V, OutCmd.Constraint))
       continue;
-    if (Cmd->SortInner)
+    if (Cmd->SortInner != SortSectionPolicy::None)
       std::stable_sort(V.begin(), V.end(), getComparator(Cmd->SortInner));
-    if (Cmd->SortOuter)
+    if (Cmd->SortOuter != SortSectionPolicy::None)
       std::stable_sort(V.begin(), V.end(), getComparator(Cmd->SortOuter));
 
     // Add all input sections corresponding to rule 'Cmd' to
     // resulting vector. We do not add duplicate input sections.
     for (InputSectionBase<ELFT> *S : V)
       if (SectionIndex.insert(S).second)
         Ret.push_back(S);
   }
private:
   std::vector<uint8_t> readFill();
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller(StringRef Tok);
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   Regex readFilePatterns();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
-  SortKind readSortKind();
+  SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok, bool MakeAbsolute);
   void readSort();
   Expr readAssert();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();

 
 Regex ScriptParser::readFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !skip(")"))
     V.push_back(next());
   return compileGlobPatterns(V);
 }
 
-SortKind ScriptParser::readSortKind() {
+SortSectionPolicy ScriptParser::readSortKind() {
   if (skip("SORT") || skip("SORT_BY_NAME"))
-    return SortByName;
+    return SortSectionPolicy::Name;
   if (skip("SORT_BY_ALIGNMENT"))
-    return SortByAlignment;
+    return SortSectionPolicy::Alignment;
   if (skip("SORT_BY_INIT_PRIORITY"))
-    return SortByPriority;
-  return SortNone;
+    return SortSectionPolicy::Priority;
+  // `SORT_NONE' disables section sorting by ignoring the command line
+  // section sorting option.
+  if (skip("SORT_NONE"))
+    return SortSectionPolicy::IgnoreConfig;
+  return SortSectionPolicy::None;
+}
+
+static void selectSortKind(InputSectionDescription *Cmd) {
+  if (Cmd->SortOuter == SortSectionPolicy::IgnoreConfig) {
+    Cmd->SortOuter = SortSectionPolicy::None;
+    return;
+  }
+
+  if (Cmd->SortOuter != SortSectionPolicy::None) {
+    // If the section sorting command in linker script is nested, the command
+    // line option will be ignored.
+    if (Cmd->SortInner != SortSectionPolicy::None)
+      return;
+    // If the section sorting command in linker script isn't nested, the
+    // command line option will make the section sorting command to be treated
+    // as nested sorting command.
+    Cmd->SortInner = Config->SortSection;
+    return;
+  }
+  // If sorting rule not specified, use command line option.
+  Cmd->SortOuter = Config->SortSection;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionRules(StringRef FilePattern) {
   auto *Cmd = new InputSectionDescription(FilePattern);
   expect("(");
 
   // Read EXCLUDE_FILE().
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     Cmd->ExcludedFileRe = readFilePatterns();
   }
 
   // Read SORT().
-  if (SortKind K1 = readSortKind()) {
+  SortSectionPolicy K1 = readSortKind();
+  if (K1 != SortSectionPolicy::None) {
     Cmd->SortOuter = K1;
     expect("(");
-    if (SortKind K2 = readSortKind()) {
+    SortSectionPolicy K2 = readSortKind();
+    if (K2 != SortSectionPolicy::None) {
       Cmd->SortInner = K2;
       expect("(");
       Cmd->SectionRe = readFilePatterns();
       expect(")");
     } else {
       Cmd->SectionRe = readFilePatterns();
     }
     expect(")");
+    selectSortKind(Cmd);
     return Cmd;
   }
 
+  selectSortKind(Cmd);
   Cmd->SectionRe = readFilePatterns();
   return Cmd;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionDescription(StringRef Tok) {
   // Input section wildcard can be surrounded by KEEP.
   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep

ELF/Options.td

 
 def section_start: S<"section-start">, MetaVarName<"<address>">,
   HelpText<"Set address of section">;
 
 def shared: F<"shared">, HelpText<"Build a shared object">;
 
 def soname: J<"soname=">, HelpText<"Set DT_SONAME">;
 
+def sort_section: S<"sort-section">, HelpText<"Specifies sections sorting rule when linkerscript is used">;
+
 def start_lib: F<"start-lib">,
   HelpText<"Start a grouping of objects that should be treated as if they were together in an archive">;
 
 def strip_all: F<"strip-all">, HelpText<"Strip all symbols">;
 
 def strip_debug: F<"strip-debug">, HelpText<"Strip debugging information">;
 
 def sysroot: J<"sysroot=">, HelpText<"Set the system root">;

test/ELF/linkerscript/sort-nested.s

 # RUN: ld.lld -o %t2 --script %t2.script %t1.o %t2.o
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SORTED_NA %s
 # SORTED_NA: Contents of section .aaa:
 # SORTED_NA:   01000000 00000000 00000000 00000000
 # SORTED_NA:   11000000 00000000 22000000 00000000
 # SORTED_NA:   02000000 00000000 00000000 00000000
 # SORTED_NA:   55000000 00000000
 
+## If the section sorting command in linker script isn't nested, the
+## command line option will make the section sorting command to be treated
+## as nested sorting command.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_ALIGNMENT(.aaa.*)) } }" > %t3.script
+# RUN: ld.lld --sort-section name -o %t3 --script %t3.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_AN %s
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_NAME(.aaa.*)) } }" > %t4.script
+# RUN: ld.lld --sort-section alignment -o %t4 --script %t4.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t4 | FileCheck -check-prefix=SORTED_NA %s
+
 .global _start
 _start:
  nop
 
 .section .aaa.1, "a"
 .align 32
 .quad 1
 
 .section .aaa.2, "a"
 .align 2
 .quad 2
 
 .section .aaa.5, "a"
 .align 16
 .quad 0x55

test/ELF/linkerscript/sort.s

 # SORTED_ALIGNMENT-NEXT:  0130 00000000 00000000 00000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0140 11000000 00000000 00000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0150 04000000 00000000 00000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0160 22000000 00000000 03000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0170 33000000 00000000 02000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0180 44000000 00000000 01000000 00000000
 # SORTED_ALIGNMENT-NEXT:  0190 55000000 00000000
 
+## SORT_NONE itself does not sort anything.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_NONE(.aaa.*)) } }" > %t6.script
+# RUN: ld.lld -o %t7 --script %t6.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t7 | FileCheck -check-prefix=UNSORTED %s
+
+## Check --sort-section alignment option.
+# RUN: echo "SECTIONS { .aaa : { *(.aaa.*) } }" > %t7.script
+# RUN: ld.lld --sort-section alignment -o %t8 --script %t7.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t8 | FileCheck -check-prefix=SORTED_ALIGNMENT %s
+
+## Check --sort-section name option.
+# RUN: echo "SECTIONS { .aaa : { *(.aaa.*) } }" > %t8.script
+# RUN: ld.lld --sort-section name -o %t9 --script %t8.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t9 | FileCheck -check-prefix=SORTED_B %s
+
+## SORT_NONE disables the --sort-section.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_NONE(.aaa.*)) } }" > %t9.script
+# RUN: ld.lld --sort-section name -o %t10 --script %t9.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t10 | FileCheck -check-prefix=UNSORTED %s
+
+
 .global _start
 _start:
  nop
 
 .section .aaa.5, "a"
 .align 32
 .quad 5