[patch] Merge identical strings (Rafael's patch)

[ruiu]

ELF/InputFiles.h

132

unsigned -> size_t.

It is better to write a comment about the number. (The offset in .dynsym for a symbol.)

ELF/OutputSections.cpp

615

You want to update this comment (it no longer reserve strings.)

1348

Can you describe the background why we have HashIt? Particularly, about the fact that we do uniquify strings only for local symbols and why.

[• rafael]

I will implement the other suggestions in a second.

ELF/InputFiles.h

132

This is st_name, which is Elf_Word, so always 32 bits.

ELF/InputFiles.h

   // R_MIPS_GPREL16 / R_MIPS_GPREL32 relocations.
   uint32_t getMipsGp0() const;
 
-  std::vector<const Elf_Sym *> KeptLocalSyms;
+  std::vector<std::pair<const Elf_Sym *, unsigned>> KeptLocalSyms;
 
 private:
   void initializeSections(llvm::DenseSet<StringRef> &ComdatGroups);

ELF/OutputSections.h

 
 #include "lld/Core/LLVM.h"
 
-#include "llvm/ADT/MapVector.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Object/ELF.h"
 

   void setVA(uintX_t VA) { Header.sh_addr = VA; }
   uintX_t getVA() const { return Header.sh_addr; }
   void setFileOffset(uintX_t Off) { Header.sh_offset = Off; }
+  void setSHName(unsigned Val) { Header.sh_name = Val; }
   void writeHeaderTo(Elf_Shdr *SHdr);
   StringRef getName() { return Name; }
 

 
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
-  void addLocalSymbol(StringRef Name);
   void addSymbol(SymbolBody *Body);
   StringTableSection<ELFT> &getStrTabSec() const { return StrTabSec; }
   unsigned getNumSymbols() const { return NumLocals + Symbols.size() + 1; }
 
-  ArrayRef<SymbolBody *> getSymbols() const { return Symbols; }
+  ArrayRef<std::pair<SymbolBody *, unsigned>> getSymbols() const {
+    return Symbols;
+  }
+
+  unsigned NumLocals = 0;
+  StringTableSection<ELFT> &StrTabSec;
 
 private:
   void writeLocalSymbols(uint8_t *&Buf);

   static uint8_t getSymbolBinding(SymbolBody *Body);
 
   SymbolTable<ELFT> &Table;
-  StringTableSection<ELFT> &StrTabSec;
-  std::vector<SymbolBody *> Symbols;
-  unsigned NumLocals = 0;
+  std::vector<std::pair<SymbolBody *, unsigned>> Symbols;
 };
 
 template <class ELFT>

 public:
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   StringTableSection(StringRef Name, bool Dynamic);
-  void reserve(StringRef S);
-  size_t addString(StringRef S);
+  size_t addString(StringRef S, bool HashIt = true);
   void writeTo(uint8_t *Buf) override;
-  size_t getSize() const { return Used + Reserved; }
+  size_t getSize() const { return Size; }
   void finalize() override { this->Header.sh_size = getSize(); }
   bool isDynamic() const { return Dynamic; }
 
 private:
   const bool Dynamic;
+  llvm::DenseMap<StringRef, size_t> StringMap;
   std::vector<StringRef> Strings;
-  size_t Used = 1; // ELF string tables start with a NUL byte, so 1.
-  size_t Reserved = 0;
+  size_t Size = 1; // ELF string tables start with a NUL byte, so 1.
 };
 
 template <class ELFT>

 
   // Adds symbols to the hash table.
   // Sorts the input to satisfy GNU hash section requirements.
-  void addSymbols(std::vector<SymbolBody *> &Symbols);
+  void addSymbols(std::vector<std::pair<SymbolBody *, unsigned>> &Symbols);
 
 private:
   static unsigned calcNBuckets(unsigned NumHashed);

 
   struct HashedSymbolData {
     SymbolBody *Body;
+    unsigned STName;
     uint32_t Hash;
   };
 

ELF/OutputSections.cpp

 
 template <class ELFT>
 void OutputSectionBase<ELFT>::writeHeaderTo(Elf_Shdr *SHdr) {
-  Header.sh_name = Out<ELFT>::ShStrTab->addString(Name);
   *SHdr = Header;
 }
 

   Elf_Word *Buckets = P;
   Elf_Word *Chains = P + NumSymbols;
 
-  for (SymbolBody *Body : Out<ELFT>::DynSymTab->getSymbols()) {
+  for (const std::pair<SymbolBody *, unsigned> &P :
+       Out<ELFT>::DynSymTab->getSymbols()) {
+    SymbolBody *Body = P.first;
     StringRef Name = Body->getName();
     unsigned I = Body->DynamicSymbolTableIndex;
     uint32_t Hash = hashSysv(Name) % NumSymbols;

 }
 
 template <class ELFT>
-void GnuHashTableSection<ELFT>::addSymbols(std::vector<SymbolBody *> &Symbols) {
-  std::vector<SymbolBody *> NotHashed;
+void GnuHashTableSection<ELFT>::addSymbols(
+    std::vector<std::pair<SymbolBody *, unsigned>> &Symbols) {
+  std::vector<std::pair<SymbolBody *, unsigned>> NotHashed;
   NotHashed.reserve(Symbols.size());
   HashedSymbols.reserve(Symbols.size());
-  for (SymbolBody *B : Symbols) {
+  for (const std::pair<SymbolBody *, unsigned> &P : Symbols) {
+    SymbolBody *B = P.first;
     if (includeInGnuHashTable(B))
-      HashedSymbols.push_back(HashedSymbolData{B, hashGnu(B->getName())});
+      HashedSymbols.push_back(
+          HashedSymbolData{B, P.second, hashGnu(B->getName())});
     else
-      NotHashed.push_back(B);
+      NotHashed.push_back(P);
   }
   if (HashedSymbols.empty())
     return;

 
   Symbols = std::move(NotHashed);
   for (const HashedSymbolData &Item : HashedSymbols)
-    Symbols.push_back(Item.Body);
+    Symbols.push_back(std::make_pair(Item.Body, Item.STName));
 }
 
 template <class ELFT>

   Elf_Shdr &Header = this->Header;
   Header.sh_link = Out<ELFT>::DynStrTab->SectionIndex;
 
+  auto Add = [=](Entry E) { Entries.push_back(E); };
+
   // Reserve strings. We know that these are the last string to be added to
   // DynStrTab and doing this here allows this function to set DT_STRSZ.
   if (!Config->RPath.empty())
-    Out<ELFT>::DynStrTab->reserve(Config->RPath);
-  if (!Config->SoName.empty())
-    Out<ELFT>::DynStrTab->reserve(Config->SoName);
+    Add({Config->EnableNewDtags ? DT_RUNPATH : DT_RPATH,
+         Out<ELFT>::DynStrTab->addString(Config->RPath)});
   for (const std::unique_ptr<SharedFile<ELFT>> &F : SymTab.getSharedFiles())
     if (F->isNeeded())
-      Out<ELFT>::DynStrTab->reserve(F->getSoName());
+      Add({DT_NEEDED, Out<ELFT>::DynStrTab->addString(F->getSoName())});
+  if (!Config->SoName.empty())
+    Add({DT_SONAME, Out<ELFT>::DynStrTab->addString(Config->SoName)});
+
   Out<ELFT>::DynStrTab->finalize();
 
-  auto Add = [=](Entry E) { Entries.push_back(E); };
 
   if (Out<ELFT>::RelaDyn->hasRelocs()) {
     bool IsRela = Out<ELFT>::RelaDyn->isRela();

   if (Out<ELFT>::HashTab)
     Add({DT_HASH, Out<ELFT>::HashTab});
 
-  if (!Config->RPath.empty())
-    Add({Config->EnableNewDtags ? DT_RUNPATH : DT_RPATH,
-         Out<ELFT>::DynStrTab->addString(Config->RPath)});
-
-  if (!Config->SoName.empty())
-    Add({DT_SONAME, Out<ELFT>::DynStrTab->addString(Config->SoName)});
-
   if (PreInitArraySec) {
     Add({DT_PREINIT_ARRAY, PreInitArraySec});
     Add({DT_PREINIT_ARRAYSZ, PreInitArraySec->getSize()});

     Add({DT_FINI_ARRAYSZ, (uintX_t)FiniArraySec->getSize()});
   }
 
-  for (const std::unique_ptr<SharedFile<ELFT>> &F : SymTab.getSharedFiles())
-    if (F->isNeeded())
-      Add({DT_NEEDED, Out<ELFT>::DynStrTab->addString(F->getSoName())});
-
   if (SymbolBody *B = SymTab.find(Config->Init))
     Add({DT_INIT, B});
   if (SymbolBody *B = SymTab.find(Config->Fini))

 void EHOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   auto *S = cast<EHInputSection<ELFT>>(C);
   const Elf_Shdr *RelSec = S->RelocSection;
-  if (!RelSec)
-    return addSectionAux(
-        S, make_range((const Elf_Rela *)nullptr, (const Elf_Rela *)nullptr));
+  if (!RelSec) {
+    addSectionAux(S, make_range<const Elf_Rela *>(nullptr, nullptr));
+    return;
+  }
   ELFFile<ELFT> &Obj = S->getFile()->getObj();
   if (RelSec->sh_type == SHT_RELA)
-    return addSectionAux(S, Obj.relas(RelSec));
-  return addSectionAux(S, Obj.rels(RelSec));
+    addSectionAux(S, Obj.relas(RelSec));
+  else
+    addSectionAux(S, Obj.rels(RelSec));
 }
 
 template <class ELFT>

   this->Header.sh_addralign = 1;
 }
 
-// String tables are created in two phases. First you call reserve()
-// to reserve room in the string table, and then call addString() to actually
-// add that string.
-//
-// Why two phases? We want to know the size of the string table as early as
-// possible to fix file layout. So we have separated finalize(), which
-// determines the size of the section, from writeTo(), which writes the section
-// contents to the output buffer. If we merge reserve() with addString(),
-// we need a plumbing work for finalize() and writeTo() so that offsets
-// we obtained in the former function can be written in the latter.
-// This design eliminated that need.
-template <class ELFT> void StringTableSection<ELFT>::reserve(StringRef S) {
-  Reserved += S.size() + 1; // +1 for NUL
-}
-
-// Adds a string to the string table. You must call reserve() with the
-// same string before calling addString().
-template <class ELFT> size_t StringTableSection<ELFT>::addString(StringRef S) {
-  size_t Pos = Used;
+// Adds a string to the string table.
+template <class ELFT>
+size_t StringTableSection<ELFT>::addString(StringRef S, bool HashIt) {
+  if (HashIt) {
+    auto R = StringMap.insert(std::make_pair(S, Size));
+    if (!R.second)
+      return R.first->second;
+  }
+  size_t Ret = Size;
+  Size += S.size() + 1;
   Strings.push_back(S);
-  Used += S.size() + 1;
-  Reserved -= S.size() + 1;
-  assert((int64_t)Reserved >= 0);
-  return Pos;
+  return Ret;
 }
 
 template <class ELFT> void StringTableSection<ELFT>::writeTo(uint8_t *Buf) {

     : OutputSectionBase<ELFT>(StrTabSec.isDynamic() ? ".dynsym" : ".symtab",
                               StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
                               StrTabSec.isDynamic() ? (uintX_t)SHF_ALLOC : 0),
-      Table(Table), StrTabSec(StrTabSec) {
+      StrTabSec(StrTabSec), Table(Table) {
   this->Header.sh_entsize = sizeof(Elf_Sym);
   this->Header.sh_addralign = ELFT::Is64Bits ? 8 : 4;
 }

 // See "Global Offset Table" in Chapter 5 in the following document
 // for detailed description:
 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
-static bool sortMipsSymbols(SymbolBody *L, SymbolBody *R) {
-  if (!L->isInGot() || !R->isInGot())
-    return R->isInGot();
-  return L->GotIndex < R->GotIndex;
+static bool sortMipsSymbols(const std::pair<SymbolBody *, unsigned> &L,
+                            const std::pair<SymbolBody *, unsigned> &R) {
+  if (!L.first->isInGot() || !R.first->isInGot())
+    return R.first->isInGot();
+  return L.first->GotIndex < R.first->GotIndex;
 }
 
 template <class ELFT> void SymbolTableSection<ELFT>::finalize() {

 
   if (!StrTabSec.isDynamic()) {
     std::stable_sort(Symbols.begin(), Symbols.end(),
-                     [](SymbolBody *L, SymbolBody *R) {
-                       return getSymbolBinding(L) == STB_LOCAL &&
-                              getSymbolBinding(R) != STB_LOCAL;
+                     [](const std::pair<SymbolBody *, unsigned> &L,
+                        const std::pair<SymbolBody *, unsigned> &R) {
+                       return getSymbolBinding(L.first) == STB_LOCAL &&
+                              getSymbolBinding(R.first) != STB_LOCAL;
                      });
     return;
   }

   else if (Config->EMachine == EM_MIPS)
     std::stable_sort(Symbols.begin(), Symbols.end(), sortMipsSymbols);
   size_t I = 0;
-  for (SymbolBody *B : Symbols)
-    B->DynamicSymbolTableIndex = ++I;
-}
-
-template <class ELFT>
-void SymbolTableSection<ELFT>::addLocalSymbol(StringRef Name) {
-  StrTabSec.reserve(Name);
-  ++NumLocals;
+  for (const std::pair<SymbolBody *, unsigned> &P : Symbols)
+    P.first->DynamicSymbolTableIndex = ++I;
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::addSymbol(SymbolBody *Body) {
-  StrTabSec.reserve(Body->getName());
-  Symbols.push_back(Body);
+  Symbols.push_back(
+      std::make_pair(Body, StrTabSec.addString(Body->getName(), false)));
 }
 
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {

   // Iterate over all input object files to copy their local symbols
   // to the output symbol table pointed by Buf.
   for (const std::unique_ptr<ObjectFile<ELFT>> &File : Table.getObjectFiles()) {
-    for (const Elf_Sym *Sym : File->KeptLocalSyms) {
-      ErrorOr<StringRef> SymNameOrErr = Sym->getName(File->getStringTable());
-      error(SymNameOrErr);
-      StringRef SymName = *SymNameOrErr;
+    for (const std::pair<const Elf_Sym *, unsigned> &P : File->KeptLocalSyms) {
+      const Elf_Sym *Sym = P.first;
 
       auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
       uintX_t VA = 0;

         if (Config->EMachine != EM_AMDGPU)
           VA += OutSec->getVA();
       }
-      ESym->st_name = StrTabSec.addString(SymName);
+      ESym->st_name = P.second;
       ESym->st_size = Sym->st_size;
       ESym->setBindingAndType(Sym->getBinding(), Sym->getType());
       ESym->st_value = VA;

   // Write the internal symbol table contents to the output symbol table
   // pointed by Buf.
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
-  for (SymbolBody *Body : Symbols) {
+  for (const std::pair<SymbolBody *, unsigned> &P : Symbols) {
+    SymbolBody *Body = P.first;
     const OutputSectionBase<ELFT> *OutSec = nullptr;
 
     switch (Body->kind()) {

       break;
     }
 
-    StringRef Name = Body->getName();
-    ESym->st_name = StrTabSec.addString(Name);
+    ESym->st_name = P.second;
 
     unsigned char Type = STT_NOTYPE;
     uintX_t Size = 0;

ELF/Writer.cpp

         if (!Section->isLive())
           continue;
       }
-      Out<ELFT>::SymTab->addLocalSymbol(SymName);
-      F->KeptLocalSyms.push_back(&Sym);
+      ++Out<ELFT>::SymTab->NumLocals;
+      F->KeptLocalSyms.push_back(std::make_pair(
+          &Sym, Out<ELFT>::SymTab->StrTabSec.addString(SymName)));
     }
   }
 }

   }
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
-    Out<ELFT>::ShStrTab->reserve(Sec->getName());
+    Sec->setSHName(Out<ELFT>::ShStrTab->addString(Sec->getName()));
 
   // Finalizers fix each section's size.
   // .dynsym is finalized early since that may fill up .gnu.hash.

test/ELF/dynamic-reloc.s

 
 // CHECK: DynamicSection [
 // CHECK-NEXT:  Tag                Type                 Name/Value
+// CHECK-NEXT:  0x0000000000000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:  0x0000000000000017 JMPREL
 // CHECK-NEXT:  0x0000000000000002 PLTRELSZ             24 (bytes)
 // CHECK-NEXT:  0x0000000000000003 PLTGOT

 // CHECK-NEXT:  0x0000000000000005 STRTAB
 // CHECK-NEXT:  0x000000000000000A STRSZ
 // CHECK-NEXT:  0x0000000000000004 HASH
-// CHECK-NEXT:  0x0000000000000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:  0x0000000000000015 DEBUG                0x0
 // CHECK-NEXT:  0x0000000000000000 NULL                 0x0
 // CHECK-NEXT: ]

test/ELF/linkerscript-sections.s

 # SEC-DEFAULT: 4 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-DEFAULT: 5 .shstrtab     00000002 {{[0-9a-f]*}}
 # SEC-DEFAULT: 6 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-DEFAULT: 7 .shstrtab     0000003c {{[0-9a-f]*}}
+# SEC-DEFAULT: 7 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-DEFAULT: 8 .strtab       00000008 {{[0-9a-f]*}}
 
 # Sections are put in order specified in linker script.

 # SEC-ORDER: 1 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-ORDER: 2 other         00000003 {{[0-9a-f]*}} DATA
 # SEC-ORDER: 3 .shstrtab     00000002 {{[0-9a-f]*}}
-# SEC-ORDER: 4 .shstrtab     0000003c {{[0-9a-f]*}}
+# SEC-ORDER: 4 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-ORDER: 5 .symtab       00000030 {{[0-9a-f]*}}
 # SEC-ORDER: 6 .strtab       00000008 {{[0-9a-f]*}}
 # SEC-ORDER: 7 .data         00000020 {{[0-9a-f]*}} DATA

 # SEC-SWAP-NAMES: 4 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-SWAP-NAMES: 5 .shstrtab     00000002 {{[0-9a-f]*}}
 # SEC-SWAP-NAMES: 6 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-SWAP-NAMES: 7 .shstrtab     0000003c {{[0-9a-f]*}}
+# SEC-SWAP-NAMES: 7 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-SWAP-NAMES: 8 .strtab       00000008 {{[0-9a-f]*}}
 
 # .shstrtab from the input object file is discarded.

 # SEC-MULTI: 3 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-MULTI: 4 .shstrtab     00000002 {{[0-9a-f]*}}
 # SEC-MULTI: 5 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-MULTI: 6 .shstrtab     00000036 {{[0-9a-f]*}}
+# SEC-MULTI: 6 .shstrtab     0000002c {{[0-9a-f]*}}
 # SEC-MULTI: 7 .strtab       00000008 {{[0-9a-f]*}}
 
 .globl _start;

test/ELF/shared-be.s

 
 // CHECK:      DynamicSection [
 // CHECK-NEXT:   Tag                Type                 Name/Value
+// CHECK-NEXT:   0x000000000000001D RUNPATH              foo:bar
+// CHECK-NEXT:   0x0000000000000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:   0x0000000000000007 RELA                 [[RELADDR]]
 // CHECK-NEXT:   0x0000000000000008 RELASZ               [[RELSIZE]] (bytes)
 // CHECK-NEXT:   0x0000000000000009 RELAENT              [[RELENT]] (bytes)
-// CHECK:        0x000000000000001D RUNPATH              foo:bar
-// CHECK-NEXT:   0x0000000000000001 NEEDED               SharedLibrary ({{.*}}2.so)
-// CHECK-NEXT:   0x0000000000000015 DEBUG                0x0
+// CHECK:        0x0000000000000015 DEBUG                0x0
 // CHECK-NEXT:   0x0000000000000000 NULL                 0x0
 // CHECK-NEXT: ]
 

test/ELF/shared.s

 
 // CHECK:      DynamicSection [
 // CHECK-NEXT:   Tag        Type                 Name/Value
+// CHECK-NEXT:   0x0000001D RUNPATH              foo:bar
+// CHECK-NEXT:   0x00000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:   0x00000011 REL                  [[RELADDR]]
 // CHECK-NEXT:   0x00000012 RELSZ                [[RELSIZE]] (bytes)
 // CHECK-NEXT:   0x00000013 RELENT               [[RELENT]] (bytes)

 // CHECK-NEXT:   0x00000005 STRTAB               [[DYNSTRADDR]]
 // CHECK-NEXT:   0x0000000A STRSZ
 // CHECK-NEXT:   0x00000004 HASH                 [[HASHADDR]]
-// CHECK-NEXT:   0x0000001D RUNPATH              foo:bar
-// CHECK-NEXT:   0x00000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:   0x00000015 DEBUG                0x0
 // CHECK-NEXT:   0x00000000 NULL                 0x0
 // CHECK-NEXT: ]

test/ELF/string-table.s

 // CHECK-NEXT:  EntrySize: 0
 // CHECK-NEXT:  SectionData (
 // CHECK-NEXT:    0000: 00626172 002E7465 78740066 6F6F6261  |.bar..text.fooba|
-// CHECK-NEXT:    0010: 7200666F 6F626172 00666F6F 62617200  |r.foobar.foobar.|
-// CHECK-NEXT:    0020: 2E73796D 74616200 2E736873 74727461  |.symtab..shstrta|
-// CHECK-NEXT:    0030: 62002E73 74727461 6200               |b..strtab.|
+// CHECK-NEXT:    0010: 72002E73 796D7461 62002E73 68737472  |r..symtab..shstr|
+// CHECK-NEXT:    0020: 74616200 2E737472 74616200           |tab..strtab.|
 // CHECK-NEXT:  )
 // CHECK-NEXT:}
 // CHECK:        Name: .strtab