[ELF] - Reorder local symbols.

[grimar]

Summary

This fixes PR36716 (https://bugs.llvm.org/show_bug.cgi?id=36716),

Patch sorts local symbols to match the
following order: file1, local1, hidden1, file2, local2, hidden2 ...

[grimar]

• Finished unfinished comment in the test case.

[grimar]

• Rebased.
• Simplified.

[ruiu]

ELF/SyntheticSections.cpp

1571

How does this guarantee that a local symbol group for some file always starts with a STT_FILE symbol?

[• espindola]

ELF/SyntheticSections.cpp

1571

It is not obvious and needs a comment, but it should work:

We first add local symbols to the symbol table in copyLocalSymbols. Each STT_FILE in the original .o will precede other local symbols.

The hidden symbols are added in finalizeSections, so they are also after STT_FILE.

Finally this uses a stable_sort, so the above properties remain.

One thing that is not clear is where do we put STT_SECTION created by addSectionSymbols.

Also, could we merge the partition and the sort?

[ruiu]

Also, could we merge the partition and the sort?

I thought the same thing, but I guess separating partition and sort is faster than merging them into one sort function call. Partition is O(n) and sort is O(n log n). So, IIUC, partitioning into local and global symbols first and then sorting only the local part should be faster than sorting the entire vector.

[• espindola]

In D45325#1062280, @ruiu wrote:

Also, could we merge the partition and the sort?

I thought the same thing, but I guess separating partition and sort is faster than merging them into one sort function call. Partition is O(n) and sort is O(n log n). So, IIUC, partitioning into local and global symbols first and then sorting only the local part should be faster than sorting the entire vector.

Sounds good. Lets keep both for now.

[grimar]

In D45325#1062289, @espindola wrote:

In D45325#1062280, @ruiu wrote:

Also, could we merge the partition and the sort?

I thought the same thing, but I guess separating partition and sort is faster than merging them into one sort function call. Partition is O(n) and sort is O(n log n). So, IIUC, partitioning into local and global symbols first and then sorting only the local part should be faster than sorting the entire vector.

Sounds good. Lets keep both for now.

And it also makes final code simpler IMO. We need to set Info to the number of locals and it is simple to do with partitioning.

[grimar]

• Addressed review comments.

ELF/SyntheticSections.cpp

1571

One thing that is not clear is where do we put STT_SECTION created by addSectionSymbols.

We create them before hidden symbols, hence they are placed before them. I updated the test case.

Should we place them right after the STT_FILE? It seems a bit nicer,
though they are created only for --emit-relocs and -r, so I am not sure we should care.

[• espindola]

LGTM

I think this is fine. It is a bit funny that we count the section symbols as being part of the first file that had that section, but that is unlikely to be a problem.

[grimar]

In D45325#1063671, @espindola wrote:

LGTM

I think this is fine. It is a bit funny that we count the section symbols as being part of the first file that had that section, but that is unlikely to be a problem.

We could just stop passing the file when we create them in addSectionSymbols probably.

ELF/SyntheticSections.cpp

void SymbolTableBaseSection::finalizeContents() {
   size_t I = 0;
   for (const SymbolTableEntry &S : Symbols)
     S.Sym->DynsymIndex = ++I;
 }
 
 // The ELF spec requires that all local symbols precede global symbols, so we
 // sort symbol entries in this function. (For .dynsym, we don't do that because
 // symbols for dynamic linking are inherently all globals.)
+//
+// Aside from above, we put local symbols in groups starting with the STT_FILE
+// symbol. That is convenient for purpose of identifying where are local symbols
+// coming from.
 void SymbolTableBaseSection::postThunkContents() {
   if (this->Type == SHT_DYNSYM)
     return;
-  // move all local symbols before global symbols.
-  auto It = std::stable_partition(
+
+  // Move all local symbols before global symbols.
+  auto E = std::stable_partition(
       Symbols.begin(), Symbols.end(), [](const SymbolTableEntry &S) {
         return S.Sym->isLocal() || S.Sym->computeBinding() == STB_LOCAL;
       });
-  size_t NumLocals = It - Symbols.begin();
+  size_t NumLocals = E - Symbols.begin();
   getParent()->Info = NumLocals + 1;
+
+  // Assign the growing unique ID for each local symbol's file.
+  DenseMap<InputFile *, unsigned> FileIDs;
+  for (auto I = Symbols.begin(); I != E; ++I)
+    FileIDs.insert({I->Sym->File, FileIDs.size()});
+
+  // Sort the local symbols to group them by file. We do not need to care about
+  // the STT_FILE symbols, they are already naturally placed first in each group.
+  std::stable_sort(Symbols.begin(), E,
+                   [&](const SymbolTableEntry &L, const SymbolTableEntry &R) {
+                     return FileIDs[L.Sym->File] < FileIDs[R.Sym->File];
+                   });
 }
 
 void SymbolTableBaseSection::addSymbol(Symbol *B) {
   // Adding a local symbol to a .dynsym is a bug.
   assert(this->Type != SHT_DYNSYM || !B->isLocal());
 
   bool HashIt = B->isLocal();
   Symbols.push_back({B, StrTabSec.addString(B->getName(), HashIt)});

ELF/Writer.cpp

do {
         Changed |= A64P.createFixes();
       }
       if (InX::MipsGot)
         InX::MipsGot->updateAllocSize();
       Changed |= InX::RelaDyn->updateAllocSize();
     } while (Changed);
   }
 
+  // createThunks may have added local symbols to the static symbol table
+  applySynthetic({InX::SymTab},
+                 [](SyntheticSection *SS) { SS->postThunkContents(); });
+
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
-
-  // createThunks may have added local symbols to the static symbol table
-  applySynthetic({InX::SymTab},
-                 [](SyntheticSection *SS) { SS->postThunkContents(); });
 }
 
 // The linker is expected to define SECNAME_start and SECNAME_end
 // symbols for a few sections. This function defines them.
 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
   auto Define = [&](StringRef Start, StringRef End, OutputSection *OS) {
     // These symbols resolve to the image base if the section does not exist.
     // A special value -1 indicates end of the section.

test/ELF/local-symbols-order.s

 # REQUIRES: x86
 
 # RUN: echo '.file "file2"; foo2:; .global bar2; .hidden bar2; bar2:' > %t2.s
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %t2.s -o %t2.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 
 # RUN: ld.lld -o %t %t1.o %t2.o
 # RUN: llvm-readobj -symbols -elf-output-style=GNU %t | FileCheck %s
 
-## Show the order of the local symbols produced currently by LLD.
+## Check we sort local symbols to match the
+## following order: file1, local1, hidden1, file2, local2, hidden2 ...
 
 # CHECK:      Num:    Value          Size Type    Bind   Vis      Ndx Name
 # CHECK-NEXT:   0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
 # CHECK-NEXT:   1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS file1
 # CHECK-NEXT:   2: 0000000000201000     0 NOTYPE  LOCAL  DEFAULT    1 foo1
-# CHECK-NEXT:   3: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS file2
-# CHECK-NEXT:   4: 0000000000201000     0 NOTYPE  LOCAL  DEFAULT    1 foo2
-# CHECK-NEXT:   5: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     1 bar1
+# CHECK-NEXT:   3: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     1 bar1
+# CHECK-NEXT:   4: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS file2
+# CHECK-NEXT:   5: 0000000000201000     0 NOTYPE  LOCAL  DEFAULT    1 foo2
 # CHECK-NEXT:   6: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     1 bar2
 
 foo1:
 
 .global bar1
 .hidden bar1
 bar1:
 
 .file "file1"

test/ELF/relocatable-comdat-multiple.s

 # CHECK-NEXT:       .text.a
 # CHECK-NEXT:       .text.b
 # CHECK-NEXT:     ]
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Group {
 # CHECK-NEXT:     Name: .group
 # CHECK-NEXT:     Index: 5
 # CHECK-NEXT:     Link: 8
-# CHECK-NEXT:     Info: 2
+# CHECK-NEXT:     Info: 6
 # CHECK-NEXT:     Type: COMDAT
 # CHECK-NEXT:     Signature: bbb
 # CHECK-NEXT:     Section(s) in group [
 # CHECK-NEXT:       .text.c
 # CHECK-NEXT:       .text.d
 # CHECK-NEXT:     ]
 # CHECK-NEXT:   }
 # CHECK-NEXT: }
 
 .section .text.a,"axG",@progbits,aaa,comdat
 .section .text.b,"axG",@progbits,aaa,comdat