[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 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 file symbol locations, they are naturally placed first in the 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

if (errorCount())
     return;
 
   if (auto E = Buffer->commit())
     error("failed to write to the output file: " + toString(std::move(E)));
 }
 
 static bool shouldKeepInSymtab(SectionBase *Sec, StringRef SymName,
                                const Symbol &B) {
-  if (B.isFile() || B.isSection())
+  if (B.isSection())
     return false;
 
   // If sym references a section in a discarded group, don't keep it.
   if (Sec == &InputSection::Discarded)
     return false;
 
   if (Config->Discard == DiscardPolicy::None)
     return true;
do {
         InX::MipsGot->updateAllocSize();
       Changed |= InX::RelaDyn->updateAllocSize();
     } while (Changed);
   }
 
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
+  //
+  // We do not finalize SHT_GROUP here. We can see this type only for
+  // -r output and it can only be finalized after finalization of the
+  // symbol table done in postThunkContents() below.
   for (OutputSection *Sec : OutputSections)
+    if (Sec->Type != SHT_GROUP)
       Sec->finalize<ELFT>();
 
   // createThunks may have added local symbols to the static symbol table
   applySynthetic({InX::SymTab},
                  [](SyntheticSection *SS) { SS->postThunkContents(); });
+
+  for (OutputSection *Sec : OutputSections)
+    if (Sec->Type == SHT_GROUP)
+      Sec->finalize<ELFT>();
 }
 
 // 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/file-sym.s

-# Check that we do not keep STT_FILE symbols in the symbol table
-
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
-# RUN: ld.lld %t.o -shared -o %t.so
-# RUN: llvm-readobj -symbols %t.so | FileCheck %s
-
-# REQUIRES: x86
-
-# CHECK-NOT: Name: xxx
-
-.file "xxx"
-.file ""

test/ELF/local-symbol-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
+
+## 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: 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/lto/data-ordering-lto.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-scei-ps4 %s -o %t.o
 # RUN: llvm-as %p/Inputs/data-ordering-lto.ll -o %t.bc
 
 # Set up the symbol file
 # RUN: echo "tin  " > %t_order_lto.txt
 # RUN: echo "dipsy " >> %t_order_lto.txt
 # RUN: echo "pat " >> %t_order_lto.txt
 
 # RUN: ld.lld --symbol-ordering-file %t_order_lto.txt %t.o %t.bc -o %t2.out
 # RUN: llvm-readobj -elf-output-style=GNU -t %t2.out| FileCheck %s
 
 # Check that the order is tin -> dipsy -> pat.
 
-# CHECK: Symbol table '.symtab' contains 5 entries:
+# CHECK: Symbol table '.symtab' contains 6 entries:
 # CHECK-NEXT:    Num:    Value          Size Type    Bind   Vis      Ndx Name
 # CHECK-NEXT:      0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
-# CHECK-NEXT:      1: 0000000000201000     0 NOTYPE  GLOBAL DEFAULT    1 _start
-# CHECK-NEXT:      2: 0000000000202004     4 OBJECT  GLOBAL DEFAULT    2 dipsy
-# CHECK-NEXT:      3: 0000000000202008     4 OBJECT  GLOBAL DEFAULT    2 pat
-# CHECK-NEXT:      4: 0000000000202000     4 OBJECT  GLOBAL DEFAULT    2 tin
+# CHECK-NEXT:      1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS {{.*}}.o
+# CHECK-NEXT:      2: 0000000000201000     0 NOTYPE  GLOBAL DEFAULT    1 _start
+# CHECK-NEXT:      3: 0000000000202004     4 OBJECT  GLOBAL DEFAULT    2 dipsy
+# CHECK-NEXT:      4: 0000000000202008     4 OBJECT  GLOBAL DEFAULT    2 pat
+# CHECK-NEXT:      5: 0000000000202000     4 OBJECT  GLOBAL DEFAULT    2 tin
 
 .globl _start
 _start:
   movl $pat, %ecx
   movl $dipsy, %ebx
   movl $tin, %eax

test/ELF/lto/parallel-internalize.ll

 ; CHECK-NEXT:     Value: 0x0
 ; CHECK-NEXT:     Size: 0
 ; CHECK-NEXT:     Binding: Local (0x0)
 ; CHECK-NEXT:     Type: None (0x0)
 ; CHECK-NEXT:     Other: 0
 ; CHECK-NEXT:     Section: Undefined (0x0)
 ; CHECK-NEXT:   }
 ; CHECK-NEXT:   Symbol {
+; CHECK-NEXT:     Name: {{.*}}.o
+; CHECK-NEXT:     Value: 0x0
+; CHECK-NEXT:     Size: 0
+; CHECK-NEXT:     Binding: Local
+; CHECK-NEXT:     Type: File
+; CHECK-NEXT:     Other: 0
+; CHECK-NEXT:     Section: Absolute
+; CHECK-NEXT:   }
+; CHECK-NEXT:   Symbol {
+; CHECK-NEXT:     Name: {{.*}}.o
+; CHECK-NEXT:     Value: 0x0
+; CHECK-NEXT:     Size: 0
+; CHECK-NEXT:     Binding: Local
+; CHECK-NEXT:     Type: File
+; CHECK-NEXT:     Other: 0
+; CHECK-NEXT:     Section: Absolute
+; CHECK-NEXT:   }
+; CHECK-NEXT:   Symbol {
 ; CHECK-NEXT:     Name: bar
 ; CHECK-NEXT:     Value: 0x201010
 ; CHECK-NEXT:     Size: 8
 ; CHECK-NEXT:     Binding: Local (0x0)
 ; CHECK-NEXT:     Type: Function (0x2)
 ; CHECK-NEXT:     Other [ (0x2)
 ; CHECK-NEXT:       STV_HIDDEN (0x2)
 ; CHECK-NEXT:     ]

test/ELF/lto/relocatable.ll

 ; REQUIRES: x86
 ; RUN: llvm-as %s -o %t1.o
 ; RUN: ld.lld %t1.o -r -o %t
 ; RUN: llvm-readobj -symbols %t | FileCheck %s
 
 ; CHECK:       Symbols [
 ; CHECK-NEXT:   Symbol {
 ; CHECK-NEXT:     Name:
 ; CHECK-NEXT:     Value: 0x0
 ; CHECK-NEXT:     Size: 0
 ; CHECK-NEXT:     Binding: Local
 ; CHECK-NEXT:     Type: None
 ; CHECK-NEXT:     Other: 0
 ; CHECK-NEXT:     Section: Undefined
 ; CHECK-NEXT:   }
 ; CHECK-NEXT:   Symbol {
+; CHECK-NEXT:     Name: {{.*}}.o
+; CHECK-NEXT:     Value: 0x0
+; CHECK-NEXT:     Size: 0
+; CHECK-NEXT:     Binding: Local
+; CHECK-NEXT:     Type: File
+; CHECK-NEXT:     Other: 0
+; CHECK-NEXT:     Section: Absolute
+; CHECK-NEXT:   }
+; CHECK-NEXT:   Symbol {
 ; CHECK-NEXT:     Name:
 ; CHECK-NEXT:     Value: 0x0
 ; CHECK-NEXT:     Size: 0
 ; CHECK-NEXT:     Binding: Local
 ; CHECK-NEXT:     Type: Section
 ; CHECK-NEXT:     Other: 0
 ; CHECK-NEXT:     Section: .text
 ; CHECK-NEXT:   }

test/ELF/lto/symbol-ordering-lto.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-scei-ps4 %s -o %t.o
 # RUN: llvm-as %p/Inputs/symbol-ordering-lto.ll -o %t.bc
 
 # Set up the symbol file
 # RUN: echo "tin  " > %t_order_lto.txt
 # RUN: echo "_start " >> %t_order_lto.txt
 # RUN: echo "pat " >> %t_order_lto.txt
 
 # RUN: ld.lld --symbol-ordering-file %t_order_lto.txt %t.o %t.bc -o %t2.out
 # RUN: llvm-readobj -elf-output-style=GNU -t %t2.out| FileCheck %s
 
 # Check that the order is tin -> _start -> pat.
 
-# CHECK: Symbol table '.symtab' contains 4 entries:
+# CHECK: Symbol table '.symtab' contains 5 entries:
 # CHECK-NEXT:   Num:    Value          Size Type    Bind   Vis      Ndx Name
 # CHECK-NEXT:     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
-# CHECK-NEXT:     1: 0000000000201008     0 NOTYPE  GLOBAL DEFAULT    1 _start
-# CHECK-NEXT:     2: 0000000000201020     6 FUNC    GLOBAL DEFAULT    1 pat
-# CHECK-NEXT:     3: 0000000000201000     6 FUNC    GLOBAL DEFAULT    1 tin
+# CHECK-NEXT:     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS {{.*}}.o
+# CHECK-NEXT:     2: 0000000000201008     0 NOTYPE  GLOBAL DEFAULT    1 _start
+# CHECK-NEXT:     3: 0000000000201020     6 FUNC    GLOBAL DEFAULT    1 pat
+# CHECK-NEXT:     4: 0000000000201000     6 FUNC    GLOBAL DEFAULT    1 tin
 
 .globl _start
 _start:
   call pat
   call tin

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