[LLD/ELF2] Initial support for local symbols in symtab

[davide]

Summary

Maybe this can be shrunk, and local.s needs some cleanup. Would appreciate comments, as I have other patches building on top of this one (I'll propose later if we're OK with the scaffolding).

[silvas]

test/elf2/local.s

14

Offset doesn't seem to matter for this test?

16–17

Do we care about these indices? We aren't checking that 5 and 4 are a particular thing.

32

I don't think we need to check the exact string table index.

[denis-protivensky]

ELF/InputFiles.cpp

78

return llvm::make_range... for consistency

ELF/Writer.cpp

551

Maybe better to rename BufStart to something like BufVisible since it points to the start of visible symbols?

614

Looks like Syms = BufStart = pointer to the buffer with STN_UNDEF and local symbols already skipped, so you need to pass Syms + NumVisible as the array end.

[• rafael]

Please git-clang-format it.

The current behavior is equivalent to --discard-all. Please add that
option and use it in the existing tests.

For local.s, use FileCheck variables to check what Link points to or
just use "Link :". We test that in other tests already.

There is duplicated code between getNonLocalSymbols and
getLocalSymbols. Can you create a getSymbols(bool Local) helper?

This crashes trying to add local symbols to the dynamic symbol table:

$ cat t.s

.global foo

foo:
bar:
$ clang -c t.s
$ ./build/bin/lld -flavor gnu2 t.o -o t.so -shared
lld: /home/espindola/llvm/llvm/include/llvm/MC/StringTableBuilder.h:54:
size_t llvm::StringTableBuilder::getOffset(llvm::StringRef) const:
Assertion `I != StringIndexMap.end() && "String is not in table!"'
failed.

uint8_t *BufStart = Buf;

The name is not very appropriate anymore. It now points to the start
of the global symbols.

Cheers,
Rafael

[davide]

Hopefully addressed (almost) all the comments.

• Cleaned up tests
• Fixup crash reported by Rafael + added a new test for that
• Rename variables

I'll refactor getLocalSymbols() and getNonLocalSymbols() in a separate NFC patch. I put an XXX on top of the function so I won't forget.
Also, I think I ran clang-format correctly on my svn checkout, but please double check.

[davide]

Fix typo in comment: s/dynsm/dynsym.
Also, previous patch introduces -discard-all option and uses it in test, as proposed by Rafael.

[davide]

• Clean up tests a little bit more.

[• rafael]

Looking pretty good.

Is there a big reason for not refactoring the duplicated code in this patch?

ELF/InputFiles.cpp

75

s/XXX/FIXME/

Please do fix it on the next patch.

84

This should be >=. Which is one of the reason I asked to avoid the code duplication.

test/elf2/local-dynamic.s

4 ↗

(On Diff #34836)

Instead of -s you can use

llvm-leadobj -t -dyn-symbols.

[davide]

New patch:

• refactor to reduce duplication (thank you for keeping me honest)
• use -dynsym instead of -s for test

[• rafael]

LGTM with a nit.

ELF/InputFiles.cpp

66

We normally put {} in both the if and the else or in neither.

71

You don't need this special case. The line bellow becomes

return llvm::make_range(Syms.begin() + 1, Syms.begin() + 1);

Which is a valid empty range.

With that you can also drop the {

ELF/InputFiles.h

 public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
 
   llvm::object::ELFFile<ELFT> *getObj() const { return ELFObj.get(); }
 
   uint16_t getEMachine() const { return getObj()->getHeader()->e_machine; }
 
+  StringRef getStringTable() const { return StringTable; }
+
 protected:
   std::unique_ptr<llvm::object::ELFFile<ELFT>> ELFObj;
   const Elf_Shdr *Symtab = nullptr;
   StringRef StringTable;
   Elf_Sym_Range getNonLocalSymbols();
 
   void openELF(MemoryBufferRef MB);
 };
public:
 
   SymbolBody *getSymbolBody(uint32_t SymbolIndex) {
     uint32_t FirstNonLocal = this->Symtab->sh_info;
     if (SymbolIndex < FirstNonLocal)
       return nullptr;
     return SymbolBodies[SymbolIndex - FirstNonLocal]->getReplacement();
   }
 
+  Elf_Sym_Range getLocalSymbols();
+
 private:
   void initializeChunks();
   void initializeSymbols();
 
   SymbolBody *createSymbolBody(StringRef StringTable, const Elf_Sym *Sym);
 
   // List of all chunks defined by this file.
   std::vector<SectionChunk<ELFT> *> Chunks;

ELF/InputFiles.cpp

 typename ELFData<ELFT>::Elf_Sym_Range ELFData<ELFT>::getNonLocalSymbols() {
   if (!Symtab)
     return Elf_Sym_Range(nullptr, nullptr);
 
   ErrorOr<StringRef> StringTableOrErr =
       ELFObj->getStringTableForSymtab(*Symtab);
   error(StringTableOrErr.getError());
   StringTable = *StringTableOrErr;
 
   Elf_Sym_Range Syms = ELFObj->symbols(Symtab);
   uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
   uint32_t FirstNonLocal = Symtab->sh_info;
   if (FirstNonLocal > NumSymbols)
     error("Invalid sh_info in symbol table");
   return llvm::make_range(Syms.begin() + FirstNonLocal, Syms.end());
 }
 
+template <class ELFT>
+typename ObjectFile<ELFT>::Elf_Sym_Range ObjectFile<ELFT>::getLocalSymbols() {
+  if (!this->Symtab)
+    return Elf_Sym_Range(nullptr, nullptr);
+  Elf_Sym_Range Syms = this->ELFObj->symbols(this->Symtab);
+  uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
+  uint32_t LastLocal = this->Symtab->sh_info - 1;
+  if (LastLocal > NumSymbols)
+    error("Invalid sh_info in symbol table");
+
+  // No local symbols.
+  if (LastLocal == 0)
+    return llvm::make_range(nullptr, nullptr);
+
+  // Skip over dummy symbol.
+  return llvm::make_range(Syms.begin() + 1, Syms.begin() + LastLocal + 1);
+}
+
 template <class ELFT> void elf2::ObjectFile<ELFT>::parse() {
   this->openELF(MB);
 
   // Read section and symbol tables.
   initializeChunks();
   initializeSymbols();
 }
 

ELF/Writer.cpp

 };
 
 template <class ELFT> class Writer;
 
 template <class ELFT>
 class SymbolTableSection final : public OutputSectionBase<ELFT::Is64Bits> {
 public:
   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
+  typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
   typedef typename OutputSectionBase<ELFT::Is64Bits>::uintX_t uintX_t;
   SymbolTableSection(Writer<ELFT> &W, SymbolTable &Table,
                      StringTableSection<ELFT::Is64Bits> &StrTabSec)
       : OutputSectionBase<ELFT::Is64Bits>(
             StrTabSec.isDynamic() ? ".dynsym" : ".symtab",
             StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
             StrTabSec.isDynamic() ? (uintX_t)SHF_ALLOC : 0),
         Table(Table), StrTabSec(StrTabSec), W(W) {
     typedef OutputSectionBase<ELFT::Is64Bits> Base;
     typename Base::HeaderT &Header = this->Header;
 
-    // For now the only local symbol is going to be the one at index 0
-    Header.sh_info = 1;
-
     Header.sh_entsize = sizeof(Elf_Sym);
     Header.sh_addralign = ELFT::Is64Bits ? 8 : 4;
   }
 
   void finalize() override {
     this->Header.sh_size = getNumSymbols() * sizeof(Elf_Sym);
     this->Header.sh_link = StrTabSec.getSectionIndex();
+    this->Header.sh_info = NumLocals + 1;
   }
 
   void writeTo(uint8_t *Buf) override;
 
   const SymbolTable &getSymTable() const { return Table; }
 
-  void addSymbol(StringRef Name) {
+  void addSymbol(StringRef Name, bool isLocal = false) {
     StrTabSec.add(Name);
     ++NumVisible;
+    if (isLocal)
+      ++NumLocals;
   }
 
   StringTableSection<ELFT::Is64Bits> &getStrTabSec() { return StrTabSec; }
   unsigned getNumSymbols() const { return NumVisible + 1; }
 
 private:
   SymbolTable &Table;
   StringTableSection<ELFT::Is64Bits> &StrTabSec;
   unsigned NumVisible = 0;
+  unsigned NumLocals = 0;
   const Writer<ELFT> &W;
 };
 
 template <class ELFT>
 class HashTableSection final : public OutputSectionBase<ELFT::Is64Bits> {
   typedef typename ELFFile<ELFT>::Elf_Word Elf_Word;
 
 public:

 // The writer writes a SymbolTable result to a file.
 template <class ELFT> class Writer {
 public:
   typedef typename ELFFile<ELFT>::uintX_t uintX_t;
   typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename ELFFile<ELFT>::Elf_Ehdr Elf_Ehdr;
   typedef typename ELFFile<ELFT>::Elf_Phdr Elf_Phdr;
   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
+  typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
   Writer(SymbolTable *T)
       : SymTabSec(*this, *T, StrTabSec), DynSymSec(*this, *T, DynStrSec),
         HashSec(DynSymSec), DynamicSec(*T, HashSec) {}
   void run();
 
   const OutputSection<ELFT> &getBSS() const {
     assert(BSSSec);
     return *BSSSec;
if (!B.isUsedInRegularObj())
     return false;
   uint8_t V = B.getMostConstrainingVisibility();
   if (V != STV_DEFAULT && V != STV_PROTECTED)
     return false;
   return true;
 }
 
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
-  uint8_t *BufStart = Buf;
+  Buf += sizeof(Elf_Sym);
 
+  // Local symbols precede other symbols.
+  for (const std::unique_ptr<ObjectFileBase> &FileB : Table.getObjectFiles()) {
+    auto &File = cast<ObjectFile<ELFT>>(*FileB);
+    Elf_Sym_Range Syms = File.getLocalSymbols();
+    for (const Elf_Sym &Sym: Syms) {
+      auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
+      ErrorOr<StringRef> SymName = Sym.getName(File.getStringTable());
+      ESym->st_name = (SymName) ? StrTabSec.getFileOff(*SymName) : 0;
+      ESym->st_value = Sym.st_value;
+      ESym->st_size = Sym.st_size;
       Buf += sizeof(Elf_Sym);
+    }
+  }
+
+  uint8_t *BufStart = Buf;
+
   for (auto &P : Table.getSymbols()) {
     StringRef Name = P.first;
     Symbol *Sym = P.second;
     SymbolBody *Body = Sym->Body;
     if (!includeInSymtab(*Body))
       continue;
     const Elf_Sym &InputSym = cast<ELFSymbolBody<ELFT>>(Body)->Sym;
 
template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   }
 
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we sort by st_name. That is arbitrary but deterministic.
   // FIXME: Experiment with passing in a custom hashing instead.
   auto *Syms = reinterpret_cast<Elf_Sym *>(BufStart);
-  ++Syms;
-  array_pod_sort(Syms, Syms + NumVisible, compareSym<ELFT>);
+  array_pod_sort(Syms, Syms + NumVisible - NumLocals, compareSym<ELFT>);
 }
 
 template <bool Is64Bits>
 template <endianness E>
 void OutputSectionBase<Is64Bits>::writeHeaderTo(
     typename ELFFile<ELFType<E, Is64Bits>>::Elf_Shdr *SHdr) {
   SHdr->sh_name = Header.sh_name;
   SHdr->sh_type = Header.sh_type;
if (!Sec) {
       OutputSections.push_back(Sec);
     }
     return Sec;
   };
 
   const SymbolTable &Symtab = SymTabSec.getSymTable();
   for (const std::unique_ptr<ObjectFileBase> &FileB : Symtab.getObjectFiles()) {
     auto &File = cast<ObjectFile<ELFT>>(*FileB);
+    Elf_Sym_Range Syms = File.getLocalSymbols();
+    for (const Elf_Sym &Sym: Syms) {
+      ErrorOr<StringRef> SymName = Sym.getName(File.getStringTable());
+      if (SymName)
+        SymTabSec.addSymbol(*SymName, true);
+    }
     for (SectionChunk<ELFT> *C : File.getChunks()) {
       if (!C)
         continue;
       const Elf_Shdr *H = C->getSectionHdr();
       OutputSection<ELFT> *Sec =
           getSection(C->getSectionName(), H->sh_type, H->sh_flags);
       Sec->addChunk(C);
     }

test/elf2/basic64be.s

 # CHECK-NEXT:     ABIVersion: 0
 # CHECK-NEXT:     Unused: (00 00 00 00 00 00 00)
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Type: Executable (0x2)
 # CHECK-NEXT:   Machine: EM_PPC64 (0x15)
 # CHECK-NEXT:   Version: 1
 # CHECK-NEXT:   Entry: 0x12000
 # CHECK-NEXT:   ProgramHeaderOffset: 0x40
-# CHECK-NEXT:   SectionHeaderOffset: 0x2078
+# CHECK-NEXT:   SectionHeaderOffset: 0x2090
 # CHECK-NEXT:   Flags [ (0x0)
 # CHECK-NEXT:   ]
 # CHECK-NEXT:   HeaderSize: 64
 # CHECK-NEXT:   ProgramHeaderEntrySize: 56
 # CHECK-NEXT:   ProgramHeaderCount: 3
 # CHECK-NEXT:   SectionHeaderEntrySize: 64
 # CHECK-NEXT:   SectionHeaderCount: 7
 # CHECK-NEXT:    StringTableSectionIndex: 6

 # CHECK-NEXT:   Section {
 # CHECK-NEXT:     Index: 5
 # CHECK-NEXT:     Name: .symtab
 # CHECK-NEXT:     Type: SHT_SYMTAB
 # CHECK-NEXT:     Flags [
 # CHECK-NEXT:     ]
 # CHECK-NEXT:     Address: 0x0
 # CHECK-NEXT:     Offset: 0x2018
-# CHECK-NEXT:     Size: 48
+# CHECK-NEXT:     Size: 72
 # CHECK-NEXT:     Link: 6
-# CHECK-NEXT:     Info: 1
+# CHECK-NEXT:     Info: 2
 # CHECK-NEXT:     AddressAlignment: 8
 # CHECK-NEXT:     EntrySize: 24
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Section {
 # CHECK-NEXT:     Index: 6
 # CHECK-NEXT:     Name: .strtab
 # CHECK-NEXT:     Type: SHT_STRTAB (0x3)
 # CHECK-NEXT:     Flags [ (0x0)
 # CHECK-NEXT:     ]
 # CHECK-NEXT:     Address: 0x0
-# CHECK-NEXT:     Offset: 0x2048
+# CHECK-NEXT:     Offset: 0x2060
 # CHECK-NEXT:     Size: 46
 # CHECK-NEXT:     Link: 0
 # CHECK-NEXT:     Info: 0
 # CHECK-NEXT:     AddressAlignment: 1
 # CHECK-NEXT:     EntrySize: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 # CHECK-NEXT: ProgramHeaders [

test/elf2/local.s

+// Check that symbol table is correctly populated with local symbols.
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+// RUN: lld -flavor gnu2 %t -o %t1
+// RUN: llvm-readobj -t -s %t1 | FileCheck %s
+// REQUIRES: x86
+
+// CHECK:   Section {
+// CHECK:     Index: 4
+// CHECK:     Name: .symtab (40)
+// CHECK:     Type: SHT_SYMTAB (0x2)
+// CHECK:     Flags [ (0x0)
+// CHECK:     ]
+// CHECK:     Address: 0x0
+// CHECK:     Offset: 0x1000
+// CHECK:     Size: 120
+// CHECK:     Link: 5
+// CHECK:     Info: 4
+// CHECK:     AddressAlignment: 8
+// CHECK:     EntrySize: 24
+// CHECK:   }
+// CHECK: Symbols [
+// CHECK:   Symbol {
+// CHECK:     Name:  (0)
+// CHECK:     Value: 0x0
+// CHECK:     Size: 0
+// CHECK:     Binding: Local (0x0)
+// CHECK:     Type: None (0x0)
+// CHECK:     Other: 0
+// CHECK:     Section: Undefined (0x0)
+// CHECK:   }
+// CHECK:   Symbol {
+// CHECK:     Name: blah (27)
+// CHECK:     Value: 0x0
+// CHECK:     Size: 0
+// CHECK:     Binding: Local (0x0)
+// CHECK:     Type: None (0x0)
+// CHECK:     Other: 0
+// CHECK:     Section: Undefined (0x0)
+// CHECK:   }
+// CHECK:   Symbol {
+// CHECK:     Name: foo (23)
+// CHECK:     Value: 0x0
+// CHECK:     Size: 0
+// CHECK:     Binding: Local (0x0)
+// CHECK:     Type: None (0x0)
+// CHECK:     Other: 0
+// CHECK:     Section: Undefined (0x0)
+// CHECK:   }
+// CHECK:   Symbol {
+// CHECK:     Name: goo (19)
+// CHECK:     Value: 0x0
+// CHECK:     Size: 0
+// CHECK:     Binding: Local (0x0)
+// CHECK:     Type: None (0x0)
+// CHECK:     Other: 0
+// CHECK:     Section: Undefined (0x0)
+// CHECK:   }
+// CHECK:   Symbol {
+// CHECK:     Name: _start (7)
+// CHECK:     Value: 0x11000
+// CHECK:     Size: 0
+// CHECK:     Binding: Global (0x1)
+// CHECK:     Type: None (0x0)
+// CHECK:     Other: 0
+// CHECK:     Section: .text (0x1)
+// CHECK:   }
+// CHECK: ]
+
+.globl _start
+_start:
+
+blah:
+foo:
+goo:

test/elf2/resolution.s

 // 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: local
+// CHECK-NEXT:     Value: 0x1
+// 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: local
+// 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: _start
 // CHECK-NEXT:     Value:
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Global
 // CHECK-NEXT:     Type: None
 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: .text
 // CHECK-NEXT:   }