From 2aae2b460965675656aabb1a19d1effc6a2e2c33 Mon Sep 17 00:00:00 2001 From: Simon Atanasyan Date: Fri, 30 May 2014 05:29:46 +0000 Subject: [PATCH] [ELF] Fix incorrect sorting of .init_array / .fini_array sections. 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 orderng. 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 fixes both of the problems. llvm-svn: 209875 --- lld/lib/ReaderWriter/ELF/ArrayOrderPass.cpp | 44 +++++++++++++++++++---------- lld/test/elf/init_array-order.test | 36 +++++++++++++++++++++++ 2 files changed, 65 insertions(+), 15 deletions(-) diff --git a/lld/lib/ReaderWriter/ELF/ArrayOrderPass.cpp b/lld/lib/ReaderWriter/ELF/ArrayOrderPass.cpp index be9cd4b..1339a12 100644 --- a/lld/lib/ReaderWriter/ELF/ArrayOrderPass.cpp +++ b/lld/lib/ReaderWriter/ELF/ArrayOrderPass.cpp @@ -10,32 +10,46 @@ #include "ArrayOrderPass.h" #include +#include namespace lld { namespace elf { void ArrayOrderPass::perform(std::unique_ptr &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; + // 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}[.] sections + // according to their number. Sections without optional + // numer suffix should go last. + + uint32_t leftPriority = std::numeric_limits::max(); + if (!leftNum.empty()) + leftNum.getAsInteger(10, leftPriority); - // Get priortiy - uint16_t leftPriority = 0; - leftSec.rsplit('.').second.getAsInteger(10, leftPriority); - uint16_t rightPriority = 0; - rightSec.rsplit('.').second.getAsInteger(10, rightPriority); + uint32_t rightPriority = std::numeric_limits::max(); + if (!rightNum.empty()) + rightNum.getAsInteger(10, rightPriority); return leftPriority < rightPriority; }); diff --git a/lld/test/elf/init_array-order.test b/lld/test/elf/init_array-order.test index 5d2bf91..1ebb24b 100644 --- a/lld/test/elf/init_array-order.test +++ b/lld/test/elf/init_array-order.test @@ -10,11 +10,31 @@ FileHeader: 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" @@ -23,15 +43,31 @@ Sections: 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 -- 2.7.4