[ELF] Fix incorrect sorting of .init_array / .fini_array sections

[atanasyan]

Summary

The main problem is in the predicate passed to the std::stable_sort(). This predicate always returns false if both section's names do not start with .init_array or .fini_array prefixes. In short, it does not define a strict weak ordering. Suppose we have the following sections:

.A .init_array.1 .init_array.2

The predicate states that:

not .init_array.1 < .A
not .A < .init_array.2
but .init_array.1 < .init_array.2 !!!

The second problem is that .init_array section without number should go last in the list. Not it has the lowest priority '0' and goes first.

The patch fix both of the problems.

[ruiu]

LGTM. I remember I once fixed a similar issue in LayoutPass whose
compare function was not strict weak ordering.

[• shankar.easwaran]

LGTM

[atanasyan]

Thanks for review.

Closed by commit rL209875.

lib/ReaderWriter/ELF/ArrayOrderPass.cpp

 //===- lib/ReaderWriter/ELF/ArrayOrderPass.cpp ----------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ArrayOrderPass.h"
 
 #include <algorithm>
+#include <limits>
 
 namespace lld {
 namespace elf {
 void ArrayOrderPass::perform(std::unique_ptr<MutableFile> &f) {
   auto definedAtoms = f->definedAtoms();
-  std::stable_sort(definedAtoms.begin(), definedAtoms.end(),
-                   [](const DefinedAtom *left, const DefinedAtom *right) {
-    if (left->sectionChoice() != DefinedAtom::sectionCustomRequired ||
-        right->sectionChoice() != DefinedAtom::sectionCustomRequired)
+
+  // Move sections need to be sorted into the separate continious group.
+  // That reduces a number of sorting elements and simplifies conditions
+  // in the sorting predicate.
+  auto last = std::stable_partition(definedAtoms.begin(), definedAtoms.end(),
+                                    [](const DefinedAtom *atom) {
+    if (atom->sectionChoice() != DefinedAtom::sectionCustomRequired)
       return false;
 
+    StringRef name = atom->customSectionName();
+    return name.startswith(".init_array") || name.startswith(".fini_array");
+  });
+
+  std::stable_sort(definedAtoms.begin(), last,
+                   [](const DefinedAtom *left, const DefinedAtom *right) {
     StringRef leftSec = left->customSectionName();
     StringRef rightSec = right->customSectionName();
 
-    // Both sections start with the same array type.
-    if (!(leftSec.startswith(".init_array") &&
-          rightSec.startswith(".init_array")) &&
-        !(leftSec.startswith(".fini_array") &&
-          rightSec.startswith(".fini_array")))
-      return false;
-
-    // Get priortiy
-    uint16_t leftPriority = 0;
-    leftSec.rsplit('.').second.getAsInteger(10, leftPriority);
-    uint16_t rightPriority = 0;
-    rightSec.rsplit('.').second.getAsInteger(10, rightPriority);
+    // Drop the front dot from the section name and get
+    // an optional section's number starting after the second dot.
+    StringRef leftNum = leftSec.drop_front().rsplit('.').second;
+    StringRef rightNum = rightSec.drop_front().rsplit('.').second;
+
+    // Sort {.init_array, .fini_array}[.<num>] sections
+    // according to their number. Sections without optional
+    // numer suffix should go last.
+
+    uint32_t leftPriority = std::numeric_limits<uint32_t>::max();
+    if (!leftNum.empty())
+      leftNum.getAsInteger(10, leftPriority);
+
+    uint32_t rightPriority = std::numeric_limits<uint32_t>::max();
+    if (!rightNum.empty())
+      rightNum.getAsInteger(10, rightPriority);
 
     return leftPriority < rightPriority;
   });
 }
 } // end namespace elf
 } // end namespace lld

test/elf/init_array-order.test

 #RUN: yaml2obj -format=elf %s > %t
 #RUN: lld -flavor gnu -target x86_64-linux %t --noinhibit-exec \
 #RUN:   --output-filetype=yaml | FileCheck %s
 
 !ELF
 FileHeader:
   Class: ELFCLASS64
   Data: ELFDATA2LSB
   Type: ET_REL
   Machine: EM_X86_64
 
 Sections:
+- Name: .text
+  Type: SHT_PROGBITS
+  Content: "1100000000000000"
+  AddressAlign: 8
+  Flags: [SHF_ALLOC, SHF_EXECINSTR]
 - Name: .init_array.2
   Type: SHT_INIT_ARRAY
   Content: "0200000000000000"
   AddressAlign: 8
   Flags: [SHF_ALLOC]
+- Name: .init_array.3
+  Type: SHT_INIT_ARRAY
+  Content: "0300000000000000"
+  AddressAlign: 8
+  Flags: [SHF_ALLOC]
+- Name: .init_array
+  Type: SHT_INIT_ARRAY
+  Content: "9900000000000000"
+  AddressAlign: 8
+  Flags: [SHF_ALLOC]
+- Name: .data
+  Type: SHT_PROGBITS
+  Content: "2200000000000000"
+  AddressAlign: 8
+  Flags: [SHF_ALLOC, SHF_WRITE]
 - Name: .init_array.1
   Type: SHT_INIT_ARRAY
   Content: "0100000000000000"
   AddressAlign: 8
   Flags: [SHF_ALLOC]
 
 Symbols:
   Local:
+  - Name: .text
+    Type: STT_SECTION
+    Section: .text
+  - Name: .data
+    Type: STT_SECTION
+    Section: .data
+  - Name: .init_array.3
+    Type: STT_SECTION
+    Section: .init_array.3
   - Name: .init_array.2
     Type: STT_SECTION
     Section: .init_array.2
   - Name: .init_array.1
     Type: STT_SECTION
     Section: .init_array.1
+  - Name: .init_array
+    Type: STT_SECTION
+    Section: .init_array
 
 #CHECK: defined-atoms:
 #CHECK:   content: [ 01,
 #CHECK:   section-name: .init_array.1
 #CHECK:   content: [ 02,
 #CHECK:   section-name: .init_array.2
+#CHECK:   content: [ 03,
+#CHECK:   section-name: .init_array.3
+#CHECK:   content: [ 99,
+#CHECK:   section-name: .init_array