ELF: Move verneed tracking data structures out of VersionNeedSection.

[pcc]

Summary

For partitions I intend to use the same set of version indexes in
each partition for simplicity. Since each partition will need its own
VersionNeedSection this will require moving the verneed tracking out of
VersionNeedSection. The way I've done this is to move most of the tracking
into SharedFile. What will eventually become the per-partition tracking
still lives in VersionNeedSection.

As a bonus the code gets a little simpler and more consistent with how we
handle verdef.

Depends on D60305

[ruiu]

lld/ELF/SyntheticSections.cpp

2796–2797

So the computed numbers start with one plus the number of versions in given version scripts, but it isn't easy to see that from the code. I'd write a comment.

[pcc]

• Add comment

[ruiu]

LGTM

lld/ELF/Driver.cpp

bool elf::link(ArrayRef<const char *> Args, bool CanExitEarly,
   Config = make<Configuration>();
   Driver = make<LinkerDriver>();
   Script = make<LinkerScript>();
   Symtab = make<SymbolTable>();
 
   Tar = nullptr;
   memset(&In, 0, sizeof(In));
 
+  SharedFile::VernauxNum = 0;
+
   Config->ProgName = Args[0];
 
   Driver->main(Args);
 
   // Exit immediately if we don't need to return to the caller.
   // This saves time because the overhead of calling destructors
   // for all globally-allocated objects is not negligible.
   if (CanExitEarly)

lld/ELF/InputFiles.h

public:
   std::unique_ptr<llvm::lto::InputFile> Obj;
 };
 
 // .so file.
 class SharedFile : public ELFFileBase {
 public:
   // This is actually a vector of Elf_Verdef pointers.
   std::vector<const void *> Verdefs;
+
+  // If the output file needs Elf_Verneed data structures for this file, this is
+  // a vector of Elf_Vernaux version identifiers that map onto the entries in
+  // Verdefs, otherwise it is empty.
+  std::vector<unsigned> Vernauxs;
+
+  static unsigned VernauxNum;
+
   std::vector<StringRef> DtNeeded;
   std::string SoName;
 
   static bool classof(const InputFile *F) { return F->kind() == SharedKind; }
 
   SharedFile(MemoryBufferRef M, StringRef DefaultSoName);
 
   template <typename ELFT> void parse();
 
-  struct NeededVer {
-    // The string table offset of the version name in the output file.
-    size_t StrTab;
-
-    // The version identifier for this version name.
-    uint16_t Index;
-  };
-
-  // Mapping from Elf_Verdef data structures to information about Elf_Vernaux
-  // data structures in the output file.
-  std::map<const void *, NeededVer> VerdefMap;
-
   // Used for --no-allow-shlib-undefined.
   bool AllNeededIsKnown;
 
   // Used for --as-needed
   bool IsNeeded;
 };
 
 class BinaryFile : public InputFile {

lld/ELF/InputFiles.cpp

if (Tar && C.getParent()->isThin())
     Tar->append(relativeToRoot(CHECK(C.getFullName(), this)), MB.getBuffer());
 
   InputFile *File = createObjectFile(
       MB, getName(), C.getParent()->isThin() ? 0 : C.getChildOffset());
   File->GroupId = GroupId;
   return File;
 }
 
+unsigned SharedFile::VernauxNum;
+
 SharedFile::SharedFile(MemoryBufferRef M, StringRef DefaultSoName)
     : ELFFileBase(SharedKind, M), SoName(DefaultSoName),
       IsNeeded(!Config->AsNeeded) {}
 
 // Fully parse the shared object file.
 //
 // This function parses symbol versions. If a DSO has version information,
 // the file has a ".gnu.version_d" section which contains symbol version

lld/ELF/SyntheticSections.h

 public:
   VersionTableSection();
   void finalizeContents() override;
   size_t getSize() const override;
   void writeTo(uint8_t *Buf) override;
   bool isNeeded() const override;
 };
 
-class VersionNeedBaseSection : public SyntheticSection {
-protected:
-  // The next available version identifier.
-  unsigned NextIndex;
-
-public:
-  VersionNeedBaseSection();
-  virtual void addSymbol(Symbol *Sym) = 0;
-  virtual size_t getNeedNum() const = 0;
-};
-
 // The .gnu.version_r section defines the version identifiers used by
 // .gnu.version. It contains a linked list of Elf_Verneed data structures. Each
 // Elf_Verneed specifies the version requirements for a single DSO, and contains
 // a reference to a linked list of Elf_Vernaux data structures which define the
 // mapping from version identifiers to version names.
 template <class ELFT>
-class VersionNeedSection final : public VersionNeedBaseSection {
+class VersionNeedSection final : public SyntheticSection {
   using Elf_Verneed = typename ELFT::Verneed;
   using Elf_Vernaux = typename ELFT::Vernaux;
 
-  // A vector of shared files that need Elf_Verneed data structures and the
-  // string table offsets of their sonames.
-  std::vector<std::pair<SharedFile *, size_t>> Needed;
+  struct Vernaux {
+    uint64_t Hash;
+    uint32_t VerneedIndex;
+    uint64_t NameStrTab;
+  };
+
+  struct Verneed {
+    uint64_t NameStrTab;
+    std::vector<Vernaux> Vernauxs;
+  };
+
+  std::vector<Verneed> Verneeds;
 
 public:
-  void addSymbol(Symbol *Sym) override;
+  VersionNeedSection();
   void finalizeContents() override;
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override;
-  size_t getNeedNum() const override { return Needed.size(); }
   bool isNeeded() const override;
 };
 
 // MergeSyntheticSection is a class that allows us to put mergeable sections
 // with different attributes in a single output sections. To do that
 // we put them into MergeSyntheticSection synthetic input sections which are
 // attached to regular output sections.
 class MergeSyntheticSection : public SyntheticSection {

 InputSection *createInterpSection();
 MergeInputSection *createCommentSection();
 template <class ELFT> void splitSections();
 void mergeSections();
 
 Defined *addSyntheticLocal(StringRef Name, uint8_t Type, uint64_t Value,
                            uint64_t Size, InputSectionBase &Section);
 
+void addVerneed(Symbol *SS);
+
 // Linker generated sections which can be used as inputs.
 struct InStruct {
   InputSection *ARMAttributes;
   ARMExidxSyntheticSection *ARMExidx;
   BssSection *Bss;
   BssSection *BssRelRo;
   BuildIdSection *BuildId;
   EhFrameHeader *EhFrameHdr;
struct InStruct {
   RelrBaseSection *RelrDyn;
   RelocationBaseSection *RelaPlt;
   RelocationBaseSection *RelaIplt;
   StringTableSection *ShStrTab;
   StringTableSection *StrTab;
   SymbolTableBaseSection *SymTab;
   SymtabShndxSection *SymTabShndx;
   VersionDefinitionSection *VerDef;
-  VersionNeedBaseSection *VerNeed;
+  SyntheticSection *VerNeed;
   VersionTableSection *VerSym;
 };
 
 extern InStruct In;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/SyntheticSections.cpp

template <class ELFT> void DynamicSection<ELFT>::finalizeContents() {
 
   if (Symbol *B = Symtab->find(Config->Init))
     if (B->isDefined())
       addSym(DT_INIT, B);
   if (Symbol *B = Symtab->find(Config->Fini))
     if (B->isDefined())
       addSym(DT_FINI, B);
 
-  bool HasVerNeed = In.VerNeed->getNeedNum() != 0;
+  bool HasVerNeed = SharedFile::VernauxNum != 0;
   if (HasVerNeed || In.VerDef)
     addInSec(DT_VERSYM, In.VerSym);
   if (In.VerDef) {
     addInSec(DT_VERDEF, In.VerDef);
     addInt(DT_VERDEFNUM, getVerDefNum());
   }
   if (HasVerNeed) {
     addInSec(DT_VERNEED, In.VerNeed);
-    addInt(DT_VERNEEDNUM, In.VerNeed->getNeedNum());
+    unsigned NeedNum = 0;
+    for (SharedFile *F : SharedFiles)
+      if (!F->Vernauxs.empty())
+        ++NeedNum;
+    addInt(DT_VERNEEDNUM, NeedNum);
   }
 
   if (Config->EMachine == EM_MIPS) {
     addInt(DT_MIPS_RLD_VERSION, 1);
     addInt(DT_MIPS_FLAGS, RHF_NOTPOT);
     addInt(DT_MIPS_BASE_ADDRESS, Target->getImageBase());
     addInt(DT_MIPS_SYMTABNO, In.DynSymTab->getNumSymbols());
 
for (const SymbolTableEntry &S : In.DynSymTab->getSymbols()) {
     Buf += 2;
   }
 }
 
 bool VersionTableSection::isNeeded() const {
   return In.VerDef || In.VerNeed->isNeeded();
 }
 
-VersionNeedBaseSection::VersionNeedBaseSection()
-    : SyntheticSection(SHF_ALLOC, SHT_GNU_verneed, sizeof(uint32_t),
-                       ".gnu.version_r") {
-  // Identifiers in verneed section start at 2 because 0 and 1 are reserved
-  // for VER_NDX_LOCAL and VER_NDX_GLOBAL.
-  // First identifiers are reserved by verdef section if it exist.
-  NextIndex = getVerDefNum() + 1;
-}
-
-template <class ELFT> void VersionNeedSection<ELFT>::addSymbol(Symbol *SS) {
+void elf::addVerneed(Symbol *SS) {
   auto &File = cast<SharedFile>(*SS->File);
   if (SS->VerdefIndex == VER_NDX_GLOBAL) {
     SS->VersionId = VER_NDX_GLOBAL;
     return;
   }
 
-  // If we don't already know that we need an Elf_Verneed for this DSO, prepare
-  // to create one by adding it to our needed list and creating a dynstr entry
-  // for the soname.
-  if (File.VerdefMap.empty())
-    Needed.push_back({&File, In.DynStrTab->addString(File.SoName)});
-  auto *Ver = reinterpret_cast<const typename ELFT::Verdef *>(
-      File.Verdefs[SS->VerdefIndex]);
-  typename SharedFile::NeededVer &NV = File.VerdefMap[Ver];
-
-  // If we don't already know that we need an Elf_Vernaux for this Elf_Verdef,
-  // prepare to create one by allocating a version identifier and creating a
-  // dynstr entry for the version name.
-  if (NV.Index == 0) {
-    NV.StrTab = In.DynStrTab->addString(File.getStringTable().data() +
-                                        Ver->getAux()->vda_name);
-    NV.Index = NextIndex++;
-  }
-  SS->VersionId = NV.Index;
+  if (File.Vernauxs.empty())
+    File.Vernauxs.resize(File.Verdefs.size());
+
+  // Select a version identifier for the vernaux data structure, if we haven't
+  // already allocated one. The verdef identifiers cover the range
+  // [1..getVerDefNum()]; this causes the vernaux identifiers to start from
+  // getVerDefNum()+1.
+  if (File.Vernauxs[SS->VerdefIndex] == 0)
+    File.Vernauxs[SS->VerdefIndex] = ++SharedFile::VernauxNum + getVerDefNum();
+
+  SS->VersionId = File.Vernauxs[SS->VerdefIndex];
+
+template <class ELFT>
+VersionNeedSection<ELFT>::VersionNeedSection()
+    : SyntheticSection(SHF_ALLOC, SHT_GNU_verneed, sizeof(uint32_t),
+                       ".gnu.version_r") {}
+
+template <class ELFT> void VersionNeedSection<ELFT>::finalizeContents() {
+  for (SharedFile *F : SharedFiles) {
+    if (F->Vernauxs.empty())
+      continue;
+    Verneeds.emplace_back();
+    Verneed &VN = Verneeds.back();
+    VN.NameStrTab = In.DynStrTab->addString(F->SoName);
+    for (unsigned I = 0; I != F->Vernauxs.size(); ++I) {
+      if (F->Vernauxs[I] == 0)
+        continue;
+      auto *Verdef =
+          reinterpret_cast<const typename ELFT::Verdef *>(F->Verdefs[I]);
+      VN.Vernauxs.push_back(
+          {Verdef->vd_hash, F->Vernauxs[I],
+           In.DynStrTab->addString(F->getStringTable().data() +
+                                   Verdef->getAux()->vda_name)});
+    }
+  }
+
+  if (OutputSection *Sec = In.DynStrTab->getParent())
+    getParent()->Link = Sec->SectionIndex;
+  getParent()->Info = Verneeds.size();
 }
 
 template <class ELFT> void VersionNeedSection<ELFT>::writeTo(uint8_t *Buf) {
   // The Elf_Verneeds need to appear first, followed by the Elf_Vernauxs.
   auto *Verneed = reinterpret_cast<Elf_Verneed *>(Buf);
-  auto *Vernaux = reinterpret_cast<Elf_Vernaux *>(Verneed + Needed.size());
+  auto *Vernaux = reinterpret_cast<Elf_Vernaux *>(Verneed + Verneeds.size());
 
-  for (std::pair<SharedFile *, size_t> &P : Needed) {
+  for (auto &VN : Verneeds) {
     // Create an Elf_Verneed for this DSO.
     Verneed->vn_version = 1;
-    Verneed->vn_cnt = P.first->VerdefMap.size();
-    Verneed->vn_file = P.second;
+    Verneed->vn_cnt = VN.Vernauxs.size();
+    Verneed->vn_file = VN.NameStrTab;
     Verneed->vn_aux =
         reinterpret_cast<char *>(Vernaux) - reinterpret_cast<char *>(Verneed);
     Verneed->vn_next = sizeof(Elf_Verneed);
     ++Verneed;
 
-    // Create the Elf_Vernauxs for this Elf_Verneed. The loop iterates over
-    // VerdefMap, which will only contain references to needed version
-    // definitions. Each Elf_Vernaux is based on the information contained in
-    // the Elf_Verdef in the source DSO. This loop iterates over a std::map of
-    // pointers, but is deterministic because the pointers refer to Elf_Verdef
-    // data structures within a single input file.
-    for (auto &NV : P.first->VerdefMap) {
-      Vernaux->vna_hash =
-          reinterpret_cast<const typename ELFT::Verdef *>(NV.first)->vd_hash;
+    // Create the Elf_Vernauxs for this Elf_Verneed.
+    for (auto &VNA : VN.Vernauxs) {
+      Vernaux->vna_hash = VNA.Hash;
       Vernaux->vna_flags = 0;
-      Vernaux->vna_other = NV.second.Index;
-      Vernaux->vna_name = NV.second.StrTab;
+      Vernaux->vna_other = VNA.VerneedIndex;
+      Vernaux->vna_name = VNA.NameStrTab;
       Vernaux->vna_next = sizeof(Elf_Vernaux);
       ++Vernaux;
     }
 
     Vernaux[-1].vna_next = 0;
   }
   Verneed[-1].vn_next = 0;
 }
 
-template <class ELFT> void VersionNeedSection<ELFT>::finalizeContents() {
-  if (OutputSection *Sec = In.DynStrTab->getParent())
-    getParent()->Link = Sec->SectionIndex;
-  getParent()->Info = Needed.size();
-}
-
 template <class ELFT> size_t VersionNeedSection<ELFT>::getSize() const {
-  unsigned Size = Needed.size() * sizeof(Elf_Verneed);
-  for (const std::pair<SharedFile *, size_t> &P : Needed)
-    Size += P.first->VerdefMap.size() * sizeof(Elf_Vernaux);
-  return Size;
+  return Verneeds.size() * sizeof(Elf_Verneed) +
+         SharedFile::VernauxNum * sizeof(Elf_Vernaux);
 }
 
 template <class ELFT> bool VersionNeedSection<ELFT>::isNeeded() const {
-  return getNeedNum() != 0;
+  return SharedFile::VernauxNum != 0;
 }
 
 void MergeSyntheticSection::addSection(MergeInputSection *MS) {
   MS->Parent = this;
   Sections.push_back(MS);
 }
 
 MergeTailSection::MergeTailSection(StringRef Name, uint32_t Type,

lld/ELF/Writer.cpp

if (!includeInSymtab(*Sym))
       continue;
     if (In.SymTab)
       In.SymTab->addSymbol(Sym);
 
     if (Sym->includeInDynsym()) {
       In.DynSymTab->addSymbol(Sym);
       if (auto *File = dyn_cast_or_null<SharedFile>(Sym->File))
         if (File->IsNeeded && !Sym->isUndefined())
-          In.VerNeed->addSymbol(Sym);
+          addVerneed(Sym);
     }
   }
 
   // Do not proceed if there was an undefined symbol.
   if (errorCount())
     return;
 
   if (In.MipsGot)

lld/test/ELF/verneed.s

 # CHECK-NEXT:     Address: 0x2002E0
 # CHECK-NEXT:     Offset: 0x2E0
 # CHECK-NEXT:     Size: 47
 # CHECK-NEXT:     Link: 0
 # CHECK-NEXT:     Info: 0
 # CHECK-NEXT:     AddressAlignment: 1
 # CHECK-NEXT:     EntrySize: 0
 # CHECK-NEXT:     SectionData (
-# CHECK-NEXT:       0000: 00663100 7665726E 65656431 2E736F2E  |.f1.verneed1.so.|
-# CHECK-NEXT:       0010: 30007633 00663200 76320067 31007665  |0.v3.f2.v2.g1.ve|
+# CHECK-NEXT:       0000: 00663100 66320067 31007665 726E6565  |.f1.f2.g1.vernee|
+# CHECK-NEXT:       0010: 64312E73 6F2E3000 76320076 33007665  |d1.so.0.v2.v3.ve|
 # CHECK-NEXT:       0020: 726E6565 64322E73 6F2E3000 763100    |rneed2.so.0.v1.|
 # CHECK-NEXT:     )
 # CHECK-NEXT:   }
 
 # CHECK:      DynamicSymbols [
 # CHECK-NEXT:   Symbol {
 # CHECK-NEXT:     Name:
 # CHECK-NEXT:     Value: 0x0