[ELF] - Implemented --section-ordering-file option.

[grimar]

Summary

Gold has support for following option:

--section-ordering-file FILENAME

Layout sections in the order specified.

It uses ordering file to layout input sections in the given order.

Original gold commit:
https://sourceware.org/ml/binutils/2010-06/txt00000.txt

Usings in the wild I found:
https://glandium.org/blog/?p=2467
https://reviews.facebook.net/D22713

[grimar]

• Corrected naming of things, minor cleanups.

[grimar]

• Implemented support of combination with linkerscript.

[ruiu]

Is this effort coordinated with Davide?

[davide]

In D25766#574368, @ruiu wrote:

Is this effort coordinated with Davide?

Yes! Thanks George for taking care of this.
BTW, I think the hard part of this feature is trying to evaluate and understand if it's worth it.
You may want to do some benchmarking/write a systap/dtrace script to collect data and feed into the linker and make sure this has some real impact. I recommend to use bare metal for testing and not VM as the results might be unreliable.
Rui, Rafael, what do you think?

[grimar]

In D25766#574420, @davide wrote:

In D25766#574368, @ruiu wrote:

Is this effort coordinated with Davide?

Yes! Thanks George for taking care of this.
BTW, I think the hard part of this feature is trying to evaluate and understand if it's worth it.
You may want to do some benchmarking/write a systap/dtrace script to collect data and feed into the linker and make sure this has some real impact. I recommend to use bare metal for testing and not VM as the results might be unreliable.
Rui, Rafael, what do you think?

After today investigations I found next more or less known ways to produce such file.

• First is use of valgring + icegrind plugin:

https://blog.mozilla.org/tglek/2010/04/07/icegrind-valgrind-plugin-for-optimizing-cold-startup/
https://glandium.org/blog/?p=1008
Method looks a bit outdated though.

• Use of function_reordering_plugin from gcc google branch (https://codereview.appspot.com/5124041, https://codereview.appspot.com/4802070/).

As far I understand along with job it do, it also should produce final_layout.txt file where sections should be dumped in a correct order,
and we should be able to reuse that file for LLD needs.

• facebook/hhvm (https://github.com/facebook/hhvm/tree/master/hphp/tools/hfsort) has tools and scrips for generating sections ordering file for gold, though

I am not sure how much easy can be to reuse it for any other applications.

I am going to check gcc way tomorrow, it seems to me as most easy possible path.

[grimar]

Short update: I was able to use gcc to extract section ordering files. For start I generated order list for clang launch without any arguments.
I used gcc from svn://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9.
For doing these next steps were performed:

1. Build llvm with:

-DCMAKE_BUILD_TYPE=Release -DLLVM_PARALLEL_COMPILE_JOBS=8 -DLLVM_ENABLE_THREADS=true -DCMAKE_CXX_FLAGS="-fPIC -std=c++11 -ffunction-sections -fdata-sections -fprofile-generate=/home/umb/LLVM/gcda" -DCMAKE_C_FLAGS="-fPIC -ffunction-sections -fdata-sections -fprofile-generate=/home/umb/LLVM/gcda" -DCMAKE_C_COMPILER=/home/umb/gcc49google/bin/gcc -DCMAKE_CXX_COMPILER=/home/umb/gcc49google/bin/g++

2. Run binary in the way we are interested in. It was ./clang w/o arguments in my case (.gcda files should be produced after that).

3. Now rebuild llvm with -fprofile-use and use of .gcda files we obtained earlier. Use gold linker.

-DCMAKE_BUILD_TYPE=Release -DLLVM_PARALLEL_COMPILE_JOBS=8 -DLLVM_ENABLE_THREADS=true -DCMAKE_CXX_FLAGS="-B/usr/local/bin -fPIC -std=c++11 -ffunction-sections -fdata-sections -fprofile-dir=/home/umb/LLVM/gcda -fprofile-use -freorder-functions=callgraph -Wl,--plugin-opt,file=/home/umb/LLVM/order.txt" -DCMAKE_C_FLAGS="-B/usr/local/bin -fPIC -ffunction-sections -fdata-sections -fprofile-dir=/home/umb/LLVM/gcda -fprofile-use -freorder-functions=callgraph -Wl,--plugin-opt,file=/home/umb/LLVM/order.txt" -DCMAKE_C_COMPILER=/home/umb/gcc49google/bin/gcc -DCMAKE_CXX_COMPILER=/home/umb/gcc49google/bin/g++

4. Remove order.txt and relink clang, that will create order.txt containing sections order for its executable.

I shared it here: https://drive.google.com/file/d/0B_OWr6ld9gUmd1hnV1k4Z25NQVk/view?usp=sharing
It is 18 megabytes in size.

Order list file contains next sections:
.text.unlikely.*
.text.exit.*
.text.startup.*
.text.hot.*

BTW, both gold and ld recognize suzh sections by name and use names as hint for sorting (no matter was order file used or not).
I did not check how it works, but that is what I saw in bfd/gold source code.
Do we want to implement the same for compatibility ?

Finally, now when I have such file I am going to write a tool or script to prepare it to be used as linker input ordering file (looks it contains excessive data, I'll check) and run some tests.
First one will be estimate clang launch time with sections ordered and without. I am thinking about other possible ones, may be compile simple helloworld ?

[grimar]

I did lot of testing last days and unfortunatly I still can't find a proper way to generate "good" order list of sections
to demonstrate the positive result.
But I can prove that ordering of sections defenetely matters.

When I start lld linked clang under perf, with this patch applied and some empty order file:
perf stat ./clang-4.0 -help

Performance counter stats for './clang-4.0 -help':
         60.445699      task-clock (msec)         #    0.860 CPUs utilized          
                 0      context-switches          #    0.000 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               889      page-faults               #    0.015 M/sec                  
...

Now if I change ordering funtion to return random:

int elf::getSectionFileOrder(StringRef S) {
    return rand() % INT32_MAX;
}

I have:
Performance counter stats for './clang-4.0 -help':
         26.831371      task-clock (msec)         #    0.742 CPUs utilized          
                 2      context-switches          #    0.075 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
             1,963      page-faults               #    0.073 M/sec                  
....

So I observed major slowdown, just because of reordering sections. I think that can probably work as a prove that building
proper ordering file can help to boost the startup of application in theory.

Unfortunately I was unable to generate ordering file that works better than empty or absence of one. I tried to use next method for that:

1. Generated a list of pagefaults: perf trace -F all -o test.txt ./clang-4.0 -help
2. Applied filter: grep -E '(clang-4.0/57467 minfault)' test.txt. That produces a list of faults of next view:

0.092 ( 0.000 ms): clang-4.0/57467 minfault [dl_main+0x54d] => /home/umb/LLVM/build_self/bin/clang-4.0@0x40 (d.)
0.097 ( 0.000 ms): clang-4.0/57467 minfault [dl_main+0x6b1] => /home/umb/LLVM/build_self/bin/clang-4.0@0x881df50 (d.)
0.102 ( 0.000 ms): clang-4.0/57467 minfault [_dl_setup_hash+0x10] => /home/umb/LLVM/build_self/bin/clang-4.0@0x23455a8 (d.)
0.120 ( 0.000 ms): clang-4.0/57467 minfault [strlen+0x26] => /home/umb/LLVM/build_self/bin/clang-4.0@0x2a6ebcf (d.)
0.143 ( 0.000 ms): clang-4.0/57467 minfault [dl_main+0x1aab] => /home/umb/LLVM/build_self/bin/clang-4.0@0x881e128 (d.)
0.153 ( 0.000 ms): clang-4.0/57467 minfault [strchr+0x23] => /home/umb/LLVM/build_self/bin/clang-4.0@0x23f5363 (d.)

3. Generated list of clang binary symbols: readelf -W -s clang-4.0 > symbols.txt
4. Using self written tool generated a order list of sections (it take offset of each page fault, finds proper symbol name and just attach

prefixes like ".text." etc). I posted the result just for reference: https://justpaste.it/zrbs

I checked that sorting really works. But result was worse than without ordering file. Partially because
if getSectionFileOrder() which returns 0 by default, that is wrong I think, so I made it to return INT32_MAX (to place unlisted sections after listed ones).
After that change there is no difference with and without use of ordering file. Even the page faults looks to be almost the same.

[grimar]

Posted timing for first case looks like a mistake, raw average results are:

18 - 23 msec and about 900 page faults for empty file and
25 - 30 msec , and about 1,960 page faults for random sections order.

So about 2x more page faults and about 1.3x more time in average.

[davide]

In D25766#579847, @grimar wrote:

When I start lld linked clang under perf, with this patch applied and some empty order file:
perf stat ./clang-4.0 -help

I'm very skeptical this is a decent testcase, at least alone. ./clang --help takes no time to start up, so, even if you show there's a speed-up it's very hard to understand if it's a real improvement or just noise.
I recommend to try a class of application where load time is a dominant factor, e.g. browsers. I would claim trhat Firefox or Chromium are decent candidates. YMMV.

[grimar]

D26130 was landed. I guess we do not need this one anymore now ?

[grimar]

D26130 was landed as alternative solution.

ELF/Config.h

 #define LLD_ELF_CONFIG_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ELF.h"
 
 #include <vector>
 
+namespace llvm {
+  class Regex;
+}
+
 namespace lld {
 namespace elf {
 
 class InputFile;
 struct Symbol;
 
 enum ELFKind {
   ELFNoneKind,

 struct VersionDefinition {
   VersionDefinition(llvm::StringRef Name, size_t Id) : Name(Name), Id(Id) {}
   llvm::StringRef Name;
   size_t Id;
   std::vector<SymbolVersion> Globals;
   size_t NameOff; // Offset in string table.
 };
 
+struct SectionOrdering {
+  llvm::StringMap<int> NonGlobs;
+  std::vector<std::pair<llvm::Regex, int>> Globs;
+};
+
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   Symbol *EntrySym = nullptr;
   InputFile *FirstElf = nullptr;
   llvm::StringMap<uint64_t> SectionStartMap;
   llvm::StringRef DynamicLinker;
   llvm::StringRef Entry;
   llvm::StringRef Emulation;
   llvm::StringRef Fini;
   llvm::StringRef Init;
   llvm::StringRef LtoAAPipeline;
   llvm::StringRef LtoNewPmPasses;
   llvm::StringRef OutputFile;
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   std::string RPath;
+  std::unique_ptr<SectionOrdering> SectionOrderingFile;
   std::vector<VersionDefinition> VersionDefinitions;
   std::vector<llvm::StringRef> AuxiliaryList;
   std::vector<llvm::StringRef> DynamicList;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> Undefined;
   std::vector<SymbolVersion> VersionScriptGlobals;
   std::vector<uint8_t> BuildIdVector;
   bool AllowMultipleDefinition;

ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->UnresolvedSymbols = getUnresolvedSymbolOption(Args);
 
   Config->Target2 = getTarget2Option(Args);
 
   if (auto *Arg = Args.getLastArg(OPT_dynamic_list))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       parseDynamicList(*Buffer);
 
+  if (auto *Arg = Args.getLastArg(OPT_section_ordering_file))
+    if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+      parseSectionOrderingList(*Buffer);
+
   for (auto *Arg : Args.filtered(OPT_export_dynamic_symbol))
     Config->DynamicList.push_back(Arg->getValue());
 
   if (auto *Arg = Args.getLastArg(OPT_version_script))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       readVersionScript(*Buffer);
 }
 

ELF/Options.td

def reproduce: S<"reproduce">,
   HelpText<"Dump linker invocation and input files for debugging">;
 
 def rpath: S<"rpath">, HelpText<"Add a DT_RUNPATH to the output">;
 
 def relocatable: F<"relocatable">, HelpText<"Create relocatable object file">;
 
 def script: S<"script">, HelpText<"Read linker script">;
 
+def section_ordering_file: S<"section-ordering-file">,
+  HelpText<"Layout sections in the order specified">;
+
 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">;

ELF/OutputSections.h

 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::uint uintX_t;
   OutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
   void addSection(InputSectionBase<ELFT> *C) override;
+  void sortByOrderList();
   void sortInitFini();
   void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
   void finalize() override;
   void assignOffsets() override;
   typename Base::Kind getKind() const override { return Base::Regular; }
   static bool classof(const Base *B) { return B->getKind() == Base::Regular; }
   std::vector<InputSection<ELFT> *> Sections;
+
+private:
+  void sort(std::function<int(StringRef S)> Order);
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef OutputSectionBase<ELFT> Base;
 
 public:

ELF/OutputSections.cpp

template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
   for (InputSection<ELFT> *S : Sections) {
     Off = alignTo(Off, S->Alignment);
     S->OutSecOff = Off;
     Off += S->getSize();
   }
   this->Header.sh_size = Off;
 }
 
-// Sorts input sections by section name suffixes, so that .foo.N comes
-// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
-// We want to keep the original order if the priorities are the same
-// because the compiler keeps the original initialization order in a
-// translation unit and we need to respect that.
-// For more detail, read the section of the GCC's manual about init_priority.
-template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
-  // Sort sections by priority.
-  typedef std::pair<int, InputSection<ELFT> *> Pair;
+template <class ELFT>
+void OutputSection<ELFT>::sort(std::function<int(StringRef S)> Order) {
+  typedef std::pair<uint64_t, InputSection<ELFT> *> Pair;
   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 
   std::vector<Pair> V;
   for (InputSection<ELFT> *S : Sections)
-    V.push_back({getPriority(S->Name), S});
+    V.push_back({Order(S->Name), S});
   std::stable_sort(V.begin(), V.end(), Comp);
   Sections.clear();
   for (Pair &P : V)
     Sections.push_back(P.second);
 }
 
+// Search in the file provided by --section-ordering-file for a section position
+// index. If the section name matches a glob pattern and a non-glob name, then
+// the non-glob position takes precedence.
+static int getOrder(StringRef S) {
+  auto I = Config->SectionOrderingFile->NonGlobs.find(S);
+  if (I != Config->SectionOrderingFile->NonGlobs.end())
+    return I->second;
+  for (std::pair<llvm::Regex, int> &P : Config->SectionOrderingFile->Globs)
+    if (P.first.match(S))
+      return P.second;
+  return 0;
+}
+
+// Sort input sections by order specified in --section-ordering-file.
+template <class ELFT> void OutputSection<ELFT>::sortByOrderList() {
+  sort(getOrder);
+}
+
+// Sorts input sections by section name suffixes, so that .foo.N comes
+// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
+// We want to keep the original order if the priorities are the same
+// because the compiler keeps the original initialization order in a
+// translation unit and we need to respect that.
+// For more detail, read the section of the GCC's manual about init_priority.
+template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
+  sort(getPriority);
+}
+
 // Returns true if S matches /Filename.?\.o$/.
 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
   if (!S.endswith(".o"))
     return false;
   S = S.drop_back(2);
   if (S.endswith(Filename))
     return true;
   return !S.empty() && S.drop_back().endswith(Filename);

ELF/SymbolListFile.h

 #include "lld/Core/LLVM.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 namespace lld {
 namespace elf {
 
 void parseDynamicList(MemoryBufferRef MB);
 
+void parseSectionOrderingList(MemoryBufferRef MB);
+
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SymbolListFile.cpp

while (!atEOF()) {
     }
     expect(";");
   }
 }
 
 void elf::parseDynamicList(MemoryBufferRef MB) {
   DynamicListParser(MB.getBuffer()).run();
 }
+
+// Parse the --section-ordering-file argument. File has form:
+//
+//  sectionName1 sectionName2 [...] sectionNameN
+//
+// Each section name may contain wildcards.
+
+namespace {
+class SectionOrderingListParser final : public ScriptParserBase {
+public:
+  SectionOrderingListParser(StringRef S) : ScriptParserBase(S) {}
+  void run();
+};
+} // end anonymous namespace
+
+void SectionOrderingListParser::run() {
+  Config->SectionOrderingFile.reset(new SectionOrdering());
+
+  int Priority = 0;
+  while (!atEOF() && !Error) {
+    ++Priority;
+    StringRef S = next();
+    if (hasWildcard(S))
+      Config->SectionOrderingFile->Globs.push_back(
+          {compileGlobPatterns({S}), Priority});
+    else
+      Config->SectionOrderingFile->NonGlobs[S] = Priority;
+  }
+}
+
+void elf::parseSectionOrderingList(MemoryBufferRef MB) {
+  SectionOrderingListParser(MB.getBuffer()).run();
+}

ELF/Writer.cpp

for (InputSectionBase<ELFT> *IS : F->getSections()) {
       StringRef OutsecName = getOutputSectionName(IS->Name, Alloc);
       std::tie(Sec, IsNew) = Factory.create(IS, OutsecName);
       if (IsNew)
         OutputSections.push_back(Sec);
       Sec->addSection(IS);
     }
   }
 
+  if (Config->SectionOrderingFile)
+    for (OutputSectionBase<ELFT> *Base : OutputSections)
+      if (OutputSection<ELFT> *Sec = dyn_cast<OutputSection<ELFT>>(Base))
+        Sec->sortByOrderList();
+
   sortInitFini(findSection(".init_array"));
   sortInitFini(findSection(".fini_array"));
   sortCtorsDtors(findSection(".ctors"));
   sortCtorsDtors(findSection(".dtors"));
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
     Sec->assignOffsets();
 }

test/ELF/section-ordering-file.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t.out
+# RUN: llvm-objdump -s %t.out| FileCheck %s --check-prefix=BEFORE
+
+# BEFORE:      Contents of section .text:
+# BEFORE-NEXT:  10120 03040201
+
+# RUN: echo "*zed* .text.bar .text.foo* .text.foobar" > %t_order.txt
+# RUN: ld.lld --section-ordering-file %t_order.txt %t.o -o %t2.out
+# RUN: llvm-objdump -s %t2.out| FileCheck %s --check-prefix=AFTER
+
+# AFTER:      Contents of section .text:
+# AFTER-NEXT:  10120 01020304
+
+.text
+.section .text.foo,"a"
+.byte 3
+
+.section .text.foobar,"a"
+.byte 4
+
+.section .text.bar,"a"
+.byte 2
+
+.section .text.zed,"a"
+.byte 1