[LLD][COFF] Fix ordering of CRT global initializers in COMDAT sections

[aganea]

Summary

(patch by Benoit Rousseau)

This patch fixes a bug where the global variable initializers were sometimes not invoked in the correct order when it involved a C++ template instantiation.

The compiler generates an array of function pointers to the global variable initializers in the .CRT$XCU and .CRT$XIU sub-sections, and then the CRT calls those functions one by one to initialize the global variables. The sections that contain the initializer for a C++ template instantiation have the COMDAT bit set because the linker needs to do some additional work to delete the duplicate definitions.

The initial bug was that the linker puts the COMDAT sections at the end of the non-COMDAT sections, even though they are intended to be called in the same order that they appear in their OBJ.

We had the bug in the Microsoft Cloud SDK. Looking at the disassembly, the code of the library looks a bit like this.

#include <vector>

class State
{
public:
    static std::vector<State*> states;
    State(const char* name)
    {
        s_states.push_back(this);
        // ...
    }

    //
    // ...
    //
};

std::vector<State*> State::states();
State idle("Idle");
State connection_pending("Connection pending");
State connected("Connected");
// ...

Because of the bug, State::states was initialized after the globals idle, connected pushed themselves onto it, which caused State::states to drop all those states. And later on the code accesses them with a std::vector::operator[] and it crashes.

The fix simply sorts the .CRT by section number, after the COMDAT sections have been resolved. I expect the other sections to be independent of the order they appear in the executable (although there could be caching effects in the resulting executable if code that is related is separated by a wide gap in the executable’s code pages)

[aganea]

Please note that this issue occurs only when using MSVC cl.exe. Compiling with clang-cl.exe does not expose the issue.

[rnk]

In D52749#1251695, @aganea wrote:

Please note that this issue occurs only when using MSVC cl.exe. Compiling with clang-cl.exe does not expose the issue.

I was going to say, I think clang generates a single initializer function to avoid relying on the linker's chosen section order.

That's crummy, though. I guess we could limit it to the CRT section, and say anyone relying on section order corresponding to link line order in other sections is out of luck.

[ruiu]

Wow, I was surprised that we still have this kind of silly bugs... Thank you for find this out.

COFF/Writer.cpp

748 ↗

(On Diff #167832)

Maybe you should mention that C++ guarantees that global variables in a single compilation unit are initialized from top to bottom.

1594 ↗

(On Diff #167832)

I don't think you need this guard -- you can still sort an empty or a singleton list.

1614 ↗

(On Diff #167832)

I don't think you need a parallel sort, because the number of sections in a .CRT shouldn't be that large.

test/COFF/crt-dyn-initializer-order.test

1 ↗

(On Diff #167832)

Remove an unnecessary blank line.

[aganea]

In D52749#1251704, @rnk wrote:

In D52749#1251695, @aganea wrote:

Please note that this issue occurs only when using MSVC cl.exe. Compiling with clang-cl.exe does not expose the issue.

I was going to say, I think clang generates a single initializer function to avoid relying on the linker's chosen section order.

That's crummy, though. I guess we could limit it to the CRT section, and say anyone relying on section order corresponding to link line order in other sections is out of luck.

You're right indeed, that is the source of the bug. MSVC cl.exe does this:

- Name:            '.CRT$XCU'
  Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_LNK_COMDAT, IMAGE_SCN_MEM_READ ]
  Alignment:       8
  SectionData:     '0000000000000000'
  Relocations:     
    - VirtualAddress:  0
      SymbolName:      '??__E?Instances@?$TemplatedObject@$0A@@@2V?$vector@PEAU?$TemplatedObject@$0A@@@V?$allocator@PEAU?$TemplatedObject@$0A@@@@std@@@std@@A@@YAXXZ'
      Type:            IMAGE_REL_AMD64_ADDR64
- Name:            '.CRT$XCU'
  Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
  Alignment:       8
  SectionData:     '0000000000000000'
  Relocations:     
    - VirtualAddress:  0
      SymbolName:      '??__Eidle@@YAXXZ'
      Type:            IMAGE_REL_AMD64_ADDR64

While clang-cl does this:

- Name:            '.CRT$XCU'
  Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
  Alignment:       8
  SectionData:     '0000000000000000'
  Relocations:     
    - VirtualAddress:  0
      SymbolName:      _GLOBAL__sub_I_Source1.cpp
      Type:            IMAGE_REL_AMD64_ADDR64

[mstorsjo]

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

Won't this override the internal ordering based on the section name suffixes like .CRT$ABC?

[mstorsjo]

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

Or what actually does getBufferIdentifier() return - the name of the object file? In that case I'd say this is wrong. If it returns the section name it might be ok...

[aganea]

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

@mstorsjo getBufferIdentifier() indeed returns the file name. However at this point, chunks were already grouped by specific section. Meaning that this function will sort only, say, .CRT$XCU chunks at once. Internal TU order is guaranteed by the test below (return SA->SectionNumber < SB->SectionNumber;)

The only side-effect I could see is that this change makes deterministic initialization of global initializers (which in this case, means the TUs will be called in lexicographic order, based on their relative/absolute path and filename). The C++ std says the behavior is "indefinite", but this makes it "definite", at least for LLD. What is your stance on this? @ruiu @zturner @pcc @rnk

[aganea]

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

In an ideal world, it'd be nice if this behavior could be randomized, with a command-line flag. That could trap some (global initialization) issues earlier in the target program, by successive "link"-"run program" runs.

[rnk]

COFF/Chunks.cpp

32–33 ↗

(On Diff #167832)

You should be able to recover the section index with Obj->getCOFFObj()->getSectionID(Header) later. The index should be redundant with the coff_section*, which is a pointer into the section table.

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

You know, this might actually come back and bite us at some point. I agree that the linker should not provide guarantees about the order in which unrelated TUs initialize, but I am aware of a codebase that goes out of its way to maintain a particular ordering of source files in the build system to ensure that some files are initialized first. This codebase has used -fno-init-array on Linux for years to avoid dealing with the reversal of initialization order that happened when GCC moved from .ctors to .init_array.

I think, at the very least, Windows doesn't have anything like crt0.o, which is supposed to come first on the link line. The way that LLD and link.exe sort section names alphabetically makes that unnecessary.

I'm actually surprised that LLD doesn't number each object file so that we can just sort them by input order. It seems like that might be useful elsewhere.

All that said, I'd be fine with reordering input initializers alphabetically and seeing what happens. If anyone is relying on this behavior, they can use #pragma init_seg to mark the initializers that need to run first, and their code base will be less fragile as a result.

[mstorsjo]

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

Ah, sorry, I missed that this was called at that stage. Then I have no objections.

A testcase that shows that ordering of different .CRT$FOO sections (with different FOO part) from different object files is preserved just for clarity, unless we already have that. But maybe there's no need...

[mstorsjo]

Btw, I'd prefer a more precise commit subject - this one makes it sound like it has been completely broken so far, while it's only broken for one specific case.

[aganea]

Addressed all comments. Added more /verbose logging for sections, which also prints the CRT initializers. Extended the test, as requested by @mstorsjo.

Also added tests to show that arbitrary OBJ ordering on the command-line does not affect the layout of CRT section(s). This is a breaking change from the previous behavior of LLD. Please let me know if we should go ahead with that, or if I should retain the previous TUs ordering (which was previously dependent on both the OBJs order on the command-line, and the contents of said OBJs).

COFF/Chunks.cpp

32–33 ↗

(On Diff #167832)

I've removed SectionNumber and added instead SectionChunk::getSectionNumber() for that purpose.

COFF/Writer.cpp

1605 ↗

(On Diff #167832)

Extended the test to illustrate that non-COMDAT .CRT$XXX sections from different OBJs retain their internal ordering.

[mstorsjo]

In D52749#1253003, @aganea wrote:

This is a breaking change from the previous behavior of LLD. Please let me know if we should go ahead with that, or if I should retain the previous TUs ordering (which was previously dependent on both the OBJs order on the command-line, and the contents of said OBJs).

My 2 cents is that I'd prefer keeping the overall order from objs on the command line if the rest of this is implementable while keeping that.

[aganea]

Updated diff. The order of the CRT initializers is now the same as before; with the exception of COMDAT sections which now appear in the same order as declared in the .cpp file.

Please let me know if any other changes are required. Thanks!

[mstorsjo]

With those minor remarks, this patch is ok with me, but I'll let @rnk or @ruiu do the actual approval.

COFF/Writer.cpp

736 ↗

(On Diff #168129)

Hmm, this log line might be useful, but might also add quite a significant amount of spam to the verbose log. At least with mingw targets, all comdats have a separate subsection name like .text$symbolname.

745 ↗

(On Diff #168129)

I'd rather have this comment above the function itself. Being this verbose (which in itself is great!) inline in a function makes you lose focus on the overall structure.

[aganea]

Updated as per Martin's comments.

COFF/Writer.cpp

736 ↗

(On Diff #168129)

I moved it down in the .CRT part.

[mstorsjo]

COFF/Writer.cpp

745 ↗

(On Diff #168129)

I don't see this one addressed even though you checked it as done. I meant moving the large comment to be above the function definition, not here by the function call, to keep the overall structure of createSections as readable as possible.

[aganea]

COFF/Writer.cpp

745 ↗

(On Diff #168129)

Ah sorry about that - please see the updated diff.

[mstorsjo]

This version seems ok to me, but I'd like someone else's ack/approval as well.

[rnk]

lgtm, thanks

[aganea]

Thank you all!

lld/trunk/COFF/Chunks.h

public:
   llvm::iterator_range<symbol_iterator> symbols() const {
     return llvm::make_range(symbol_iterator(File, Relocs.begin()),
                             symbol_iterator(File, Relocs.end()));
   }
 
   // Allow iteration over the associated child chunks for this section.
   ArrayRef<SectionChunk *> children() const { return AssocChildren; }
 
+  // The section ID this chunk belongs to in its Obj.
+  uint32_t getSectionNumber() const;
+
   // A pointer pointing to a replacement for this chunk.
   // Initially it points to "this" object. If this chunk is merged
   // with other chunk by ICF, it points to another chunk,
-  // and this chunk is considrered as dead.
+  // and this chunk is considered as dead.
   SectionChunk *Repl;
 
   // The CRC of the contents as described in the COFF spec 4.5.5.
   // Auxiliary Format 5: Section Definitions. Used for ICF.
   uint32_t Checksum = 0;
 
   const coff_section *Header;
 

lld/trunk/COFF/Chunks.cpp

 }
 
 void SectionChunk::replace(SectionChunk *Other) {
   Alignment = std::max(Alignment, Other->Alignment);
   Other->Repl = Repl;
   Other->Live = false;
 }
 
+uint32_t SectionChunk::getSectionNumber() const {
+  DataRefImpl R;
+  R.p = reinterpret_cast<uintptr_t>(Header);
+  SectionRef S(R, File->getCOFFObj());
+  return S.getIndex() + 1;
+}
+
 CommonChunk::CommonChunk(const COFFSymbolRef S) : Sym(S) {
   // Common symbols are aligned on natural boundaries up to 32 bytes.
   // This is what MSVC link.exe does.
   Alignment = std::min(uint64_t(32), PowerOf2Ceil(Sym.getValue()));
 }
 
 uint32_t CommonChunk::getOutputCharacteristics() const {
   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |

lld/trunk/COFF/Writer.cpp

void markSymbolsForRVATable(ObjFile *File,
                               ArrayRef<SectionChunk *> SymIdxChunks,
                               SymbolRVASet &TableSymbols);
   void maybeAddRVATable(SymbolRVASet TableSymbols, StringRef TableSym,
                         StringRef CountSym);
   void setSectionPermissions();
   void writeSections();
   void writeBuildId();
   void sortExceptionTable();
+  void sortCRTSectionChunks(std::vector<Chunk *> &Chunks);
 
   llvm::Optional<coff_symbol16> createSymbol(Defined *D);
   size_t addEntryToStringTable(StringRef Str);
 
   OutputSection *findSection(StringRef Name);
   void addBaserels();
   void addBaserelBlocks(std::vector<Baserel> &V);
 
void Writer::createSections() {
   // Then create an OutputSection for each section.
   // '$' and all following characters in input section names are
   // discarded when determining output section. So, .text$foo
   // contributes to .text, for example. See PE/COFF spec 3.2.
   for (auto &Pair : Map) {
     StringRef Name = getOutputSectionName(Pair.first.first);
     uint32_t OutChars = Pair.first.second;
 
+    if (Name == ".CRT") {
       // In link.exe, there is a special case for the I386 target where .CRT
       // sections are treated as if they have output characteristics DATA | R if
-    // their characteristics are DATA | R | W. This implements the same special
-    // case for all architectures.
-    if (Name == ".CRT")
+      // their characteristics are DATA | R | W. This implements the same
+      // special case for all architectures.
       OutChars = DATA | R;
 
+      log("Processing section " + Pair.first.first + " -> " + Name);
+
+      sortCRTSectionChunks(Pair.second);
+    }
+
     OutputSection *Sec = CreateSection(Name, OutChars);
     std::vector<Chunk *> &Chunks = Pair.second;
     for (Chunk *C : Chunks)
       Sec->addChunk(C);
   }
 
   // Finally, move some output sections to the end.
   auto SectionOrder = [&](OutputSection *S) {
if (Config->Machine == ARMNT || Config->Machine == ARM64) {
     struct Entry { ulittle32_t Begin, Unwind; };
     sort(parallel::par, (Entry *)Begin, (Entry *)End,
          [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
     return;
   }
   errs() << "warning: don't know how to handle .pdata.\n";
 }
 
+// The CRT section contains, among other things, the array of function
+// pointers that initialize every global variable that is not trivially
+// constructed. The CRT calls them one after the other prior to invoking
+// main().
+//
+// As per C++ spec, 3.6.2/2.3,
+// "Variables with ordered initialization defined within a single
+// translation unit shall be initialized in the order of their definitions
+// in the translation unit"
+//
+// It is therefore critical to sort the chunks containing the function
+// pointers in the order that they are listed in the object file (top to
+// bottom), otherwise global objects might not be initialized in the
+// correct order.
+void Writer::sortCRTSectionChunks(std::vector<Chunk *> &Chunks) {
+  auto SectionChunkOrder = [](const Chunk *A, const Chunk *B) {
+    auto SA = dyn_cast<SectionChunk>(A);
+    auto SB = dyn_cast<SectionChunk>(B);
+    assert(SA && SB && "Non-section chunks in CRT section!");
+
+    StringRef SAObj = SA->File->MB.getBufferIdentifier();
+    StringRef SBObj = SB->File->MB.getBufferIdentifier();
+
+    return SAObj == SBObj && SA->getSectionNumber() < SB->getSectionNumber();
+  };
+  std::stable_sort(Chunks.begin(), Chunks.end(), SectionChunkOrder);
+
+  if (Config->Verbose) {
+    for (auto &C : Chunks) {
+      auto SC = dyn_cast<SectionChunk>(C);
+      log("  " + SC->File->MB.getBufferIdentifier().str() +
+          ", SectionID: " + Twine(SC->getSectionNumber()));
+    }
+  }
+}
+
 OutputSection *Writer::findSection(StringRef Name) {
   for (OutputSection *Sec : OutputSections)
     if (Sec->Name == Name)
       return Sec;
   return nullptr;
 }
 
 uint32_t Writer::getSizeOfInitializedData() {

lld/trunk/test/COFF/Inputs/crt-dyn-initializer-order_1.yaml

+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     55
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     70
+symbols:
+...

lld/trunk/test/COFF/Inputs/crt-dyn-initializer-order_2.yaml

+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     10
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     11
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     12
+symbols:
+...

lld/trunk/test/COFF/crt-dyn-initializer-order.test

+# // a.cpp
+# #include <iostream>
+# #include <vector>
+# 
+# template <int Magic> struct TemplatedObject {
+#   static std::vector<TemplatedObject<Magic> *> Instances;
+#   TemplatedObject() { Instances.push_back(this); }
+# };
+# 
+# using Object = TemplatedObject<0>;
+# template <> std::vector<Object *> Object::Instances{};
+# Object idle{};
+# 
+# int main() {
+#   if (Object::Instances.size() == 0)
+#     std::cout << "It's broken" << std::endl;
+#   else
+#     std::cout << "It works!" << std::endl;
+#   return 0;
+# }
+# // using `clang-cl /c a.cpp | lld-link a.obj` works
+# // using `cl /c a.cpp | lld-link a.obj` fails without lld/COFF/Writer.cpp/Writer::sortSectionChunks()
+
+# RUN: yaml2obj %s > %t.obj
+# RUN: yaml2obj %S/Inputs/crt-dyn-initializer-order_1.yaml > %t1.obj
+# RUN: yaml2obj %S/Inputs/crt-dyn-initializer-order_2.yaml > %t2.obj
+
+# CHECK: Name: .CRT
+# CHECK: Characteristics [
+# CHECK-NEXT: IMAGE_SCN_CNT_INITIALIZED_DATA
+# CHECK-NEXT: IMAGE_SCN_MEM_READ
+# CHECK-NEXT: ]
+# CHECK-NEXT: SectionData (
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t.obj %t1.obj %t2.obj 
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE1
+# CASE1-NEXT: 01020304 55701011 1205
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t.obj %t2.obj %t1.obj 
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE2
+# CASE2-NEXT: 01020304 10111255 7005
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t1.obj %t2.obj %t.obj 
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE3
+# CASE3-NEXT: 01557010 11120203 0405
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t1.obj %t.obj %t2.obj 
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE4
+# CASE4-NEXT: 01557002 03041011 1205
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t2.obj %t1.obj %t.obj 
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE5
+# CASE5-NEXT: 01101112 55700203 0405
+
+# RUN: lld-link /out:%t.dll /entry:__ImageBase /dll %t2.obj %t.obj %t1.obj
+# RUN: llvm-readobj -sections -section-data %t.dll | FileCheck %s --check-prefixes CHECK,CASE6
+# CASE6-NEXT: 01101112 02030455 7005
+
+# CHECK-NEXT: )
+
+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:
+  - Name:            '.CRT$XCA'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     01
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     02
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ, IMAGE_SCN_LNK_COMDAT ]
+    Alignment:       1
+    SectionData:     03
+  - Name:            '.CRT$XCU'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     04
+  - Name:            '.CRT$XCZ'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    SectionData:     05
+symbols:
+  - Name:            '.CRT$XCU'
+    Value:           0
+    SectionNumber:   3
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          1
+      NumberOfRelocations: 0
+      NumberOfLinenumbers: 0
+      CheckSum:        1
+      Number:          2
+      Selection:       IMAGE_COMDAT_SELECT_ASSOCIATIVE
+...