[ELF] - Make implementation of .gdb index to be more natural for futher paralleling.

[grimar]

Summary

As was suggested in comments for D33122,
this patch reimplements .gdb_index in more natural (probably) way.

[ruiu]

Overall, this patch is a bit too scarce of comments. You want to keep it readable for those who don't know what the code is intended to do.

ELF/GdbIndex.h

54–55

uint64_t?

63

There seems a better name than FileGdbIndexData. This represent a chunk of data you read from a DWARF section, right?

ELF/SyntheticSections.cpp

1741–1783

getInfo -> getDebugInfo

1755–1757

Please write in a more natural way.

for (InputSection *Sec : V)
  InputData.push_back(readDwarf(Sec));

1777–1778

When you bitwise-or some values, you usually want to write values from MSB to LSB.

1785

This should return FileGdbIndexData. (In general, you want to avoid mutating a object passed as a reference if writing in a more functional way is doable.)

1807–1811

This does not "find" anything. It computes. get, compute or calculate are good choices.

1814

Addr -> Address

ELF/SyntheticSections.h

519–524

IndexData is not a good variable name.

[grimar]

• Addressed review comments, added more comments.

ELF/GdbIndex.h

54–55

Yes, fixed.

63

That is goes from few debug sections of a object, so I used "File" word. I was thinking about "all data required for bulding gdb index extracted from object file".

Would you prefer something like "GdbIndexDataChunk" ?

ELF/SyntheticSections.cpp

1741–1783

Done.

1755–1757

Done.

1777–1778

Fixed in commit of D33551 patch.

1785

Done.

1807–1811

Ok. FWIW that confusion comes from my native language. Where I can say "find dog in the garden" or "given x = 4 * t, find x if t == 3" and that word "find" would be the same.

1814

Done.

ELF/SyntheticSections.h

519–524

Renamed.

[ruiu]

ELF/GdbIndex.h

70

Let's call it GdbIndexChunk.

ELF/SyntheticSections.h

512–513

an -> a

512–514

Do you mean that the hash table is a map from names to their types? I don't quite get what "it is a separate area ..." means.

519–524

Thanks. I think this is a good name. :)

[grimar]

ELF/SyntheticSections.h

512–514

I was just mean that it is also an area: "A mapped index consists of several areas, laid out in order: ... 5. The symbol table. This is an open-addressed hash table."
(https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html)

Because "is an hash table" itself sounds like some container for something else for me.

[grimar]

• Addressed review comments.

ELF/GdbIndex.h

70

Done.

[ruiu]

ELF/SyntheticSections.cpp

1776

If CuId is actually a 32-bit type, define it as uint32_t from the beginning.

1792–1793

Remove a blank line.

1857–1858

Be consistent -- don't mix CU and Cu. Use Cu consistently in this patch.

[grimar]

• Addressed review comments.

ELF/SyntheticSections.cpp

1776

Done.

1792–1793

Done.

1857–1858

Done.

[grimar]

• Rebased after recent commits done today.

[ruiu]

LGTM

ELF/GdbIndex.h

 
 class InputSection;
 
 // Struct represents single entry of address area of gdb index.
 struct AddressEntry {
   InputSection *Section;
   uint64_t LowAddress;
   uint64_t HighAddress;
-  size_t CuIndex;
+  uint32_t CuIndex;
+};
+
+// Struct represents single entry of compilation units list area of gdb index.
+// It consist of CU offset in .debug_info section and it's size.
+struct CompilationUnitEntry {
+  uint64_t CuOffset;
+  uint64_t CuLength;
+};
+
+// Represents data about symbol and type names which are used
+// to build symbol table and constant pool area of gdb index.
+struct NameTypeEntry {
+  StringRef Name;
+  uint8_t Type;
+};
+
+// We fill one GdbIndexDataChunk for each object where scan of
+// debug information performed. That information futher used
+// for filling gdb index section areas.
+struct GdbIndexChunk {
+  std::vector<AddressEntry> AddressArea;
+  std::vector<CompilationUnitEntry> CompilationUnits;
+  std::vector<NameTypeEntry> NamesAndTypes;
 };
 
 // Element of GdbHashTab hash table.
 struct GdbSymbol {
   GdbSymbol(uint32_t Hash, size_t Offset)
       : NameHash(Hash), NameOffset(Offset) {}
   uint32_t NameHash;
   size_t NameOffset;
   size_t CuVectorIndex;
 };
 
 // This class manages the hashed symbol table for the .gdb_index section.
 // The hash value for a table entry is computed by applying an iterative hash
 // function to the symbol's name.
 class GdbHashTab final {
 public:
   std::pair<bool, GdbSymbol *> add(uint32_t Hash, size_t Offset);
 
   void finalizeContents();
   size_t getCapacity() { return Table.size(); }
   GdbSymbol *getSymbol(size_t I) { return Table[I]; }
 
 private:
   llvm::DenseMap<size_t, GdbSymbol *> Map;
   std::vector<GdbSymbol *> Table;
 };
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SyntheticSections.h

 
 public:
   GdbIndexSection();
   void finalizeContents() override;
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override;
   bool empty() const override;
 
-  // Pairs of [CU Offset, CU length].
-  std::vector<std::pair<uint64_t, uint64_t>> CompilationUnits;
-
-  llvm::StringTableBuilder StringPool;
-
+  // Symbol table is a hash table for types and names.
+  // It is the area of gdb index.
   GdbHashTab SymbolTable;
 
-  // The CU vector portion of the constant pool.
+  // CU vector is a part of constant pool area of section.
   std::vector<std::set<uint32_t>> CuVectors;
 
-  std::vector<AddressEntry> AddressArea;
+  // String pool is also a part of constant pool, it follows CU vectors.
+  llvm::StringTableBuilder StringPool;
+
+  // Each chunk contains information gathered from a debug sections of single
+  // object and used to build different areas of gdb index.
+  std::vector<GdbIndexChunk> Chunks;
 
 private:
-  void readDwarf(InputSection *Sec);
+  GdbIndexChunk readDwarf(InputSection *Sec);
+  void buildIndex();
 
   uint32_t CuTypesOffset;
   uint32_t SymTabOffset;
   uint32_t ConstantPoolOffset;
   uint32_t StringPoolOffset;
 
   size_t CuVectorsSize = 0;
   std::vector<size_t> CuVectorsOffset;

ELF/SyntheticSections.cpp

 // for version 4.
 static uint32_t hash(StringRef Str) {
   uint32_t R = 0;
   for (uint8_t C : Str)
     R = R * 67 + tolower(C) - 113;
   return R;
 }
 
-static std::vector<std::pair<uint64_t, uint64_t>>
-readCuList(DWARFContext &Dwarf, InputSection *Sec) {
-  std::vector<std::pair<uint64_t, uint64_t>> Ret;
+static std::vector<CompilationUnitEntry> readCuList(DWARFContext &Dwarf,
+                                                    InputSection *Sec) {
+  std::vector<CompilationUnitEntry> Ret;
   for (std::unique_ptr<DWARFCompileUnit> &CU : Dwarf.compile_units())
     Ret.push_back({Sec->OutSecOff + CU->getOffset(), CU->getLength() + 4});
   return Ret;
 }
 
-static std::vector<AddressEntry>
-readAddressArea(DWARFContext &Dwarf, InputSection *Sec, size_t CurrentCU) {
+static std::vector<AddressEntry> readAddressArea(DWARFContext &Dwarf,
+                                                 InputSection *Sec) {
   std::vector<AddressEntry> Ret;
 
+  uint32_t CurrentCu = 0;
   for (std::unique_ptr<DWARFCompileUnit> &CU : Dwarf.compile_units()) {
     DWARFAddressRangesVector Ranges;
     CU->collectAddressRanges(Ranges);
 
     ArrayRef<InputSectionBase *> Sections = Sec->File->getSections();
     for (DWARFAddressRange &R : Ranges) {
       InputSectionBase *S = Sections[R.SectionIndex];
       if (!S || S == &InputSection::Discarded || !S->Live)
         continue;
       // Range list with zero size has no effect.
       if (R.LowPC == R.HighPC)
         continue;
-      Ret.push_back({cast<InputSection>(S), R.LowPC, R.HighPC, CurrentCU});
+      Ret.push_back({cast<InputSection>(S), R.LowPC, R.HighPC, CurrentCu});
     }
-    ++CurrentCU;
+    ++CurrentCu;
   }
   return Ret;
 }
 
-static std::vector<std::pair<StringRef, uint8_t>>
-readPubNamesAndTypes(DWARFContext &Dwarf, bool IsLE) {
+static std::vector<NameTypeEntry> readPubNamesAndTypes(DWARFContext &Dwarf,
+                                                       bool IsLE) {
   StringRef Data[] = {Dwarf.getGnuPubNamesSection(),
                       Dwarf.getGnuPubTypesSection()};
 
-  std::vector<std::pair<StringRef, uint8_t>> Ret;
+  std::vector<NameTypeEntry> Ret;
   for (StringRef D : Data) {
     DWARFDebugPubTable PubTable(D, IsLE, true);
     for (const DWARFDebugPubTable::Set &Set : PubTable.getData())
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
         Ret.push_back({Ent.Name, Ent.Descriptor.toBits()});
   }
   return Ret;
 }
 
-void GdbIndexSection::readDwarf(InputSection *Sec) {
-  Expected<std::unique_ptr<object::ObjectFile>> Obj =
-      object::ObjectFile::createObjectFile(Sec->File->MB);
-  if (!Obj) {
-    error(toString(Sec->File) + ": error creating DWARF context");
-    return;
-  }
+static std::vector<InputSection *> getDebugInfoSections() {
+  std::vector<InputSection *> Ret;
+  for (InputSectionBase *S : InputSections)
+    if (InputSection *IS = dyn_cast<InputSection>(S))
+      if (IS->getParent() && IS->Name == ".debug_info")
+        Ret.push_back(IS);
+  return Ret;
 
-  DWARFContextInMemory Dwarf(*Obj.get());
+void GdbIndexSection::buildIndex() {
+  std::vector<InputSection *> V = getDebugInfoSections();
+  if (V.empty())
+    return;
+
+  for (InputSection *Sec : V)
+    Chunks.push_back(readDwarf(Sec));
 
-  size_t CuId = CompilationUnits.size();
-  for (std::pair<uint64_t, uint64_t> &P : readCuList(Dwarf, Sec))
-    CompilationUnits.push_back(P);
-
-  for (AddressEntry &Ent : readAddressArea(Dwarf, Sec, CuId))
-    AddressArea.push_back(Ent);
-
-  std::vector<std::pair<StringRef, uint8_t>> NamesAndTypes =
-      readPubNamesAndTypes(Dwarf, Config->IsLE);
-
-  for (std::pair<StringRef, uint8_t> &Pair : NamesAndTypes) {
-    uint32_t Hash = hash(Pair.first);
-    size_t Offset = StringPool.add(Pair.first);
+  uint32_t CuId = 0;
+  for (GdbIndexChunk &D : Chunks) {
+    for (AddressEntry &E : D.AddressArea)
+      E.CuIndex += CuId;
+
+    // Populate constant pool area.
+    for (NameTypeEntry &NameType : D.NamesAndTypes) {
+      uint32_t Hash = hash(NameType.Name);
+      size_t Offset = StringPool.add(NameType.Name);
 
       bool IsNew;
       GdbSymbol *Sym;
       std::tie(IsNew, Sym) = SymbolTable.add(Hash, Offset);
       if (IsNew) {
         Sym->CuVectorIndex = CuVectors.size();
-      CuVectors.resize(CuVectors.size() + 1);
-    }
+        CuVectors.push_back({});
+      }
+
+      CuVectors[Sym->CuVectorIndex].insert(CuId | (NameType.Type << 24));
+    }
+
+    CuId += D.CompilationUnits.size();
+  }
+}
+
+GdbIndexChunk GdbIndexSection::readDwarf(InputSection *Sec) {
+  Expected<std::unique_ptr<object::ObjectFile>> Obj =
+      object::ObjectFile::createObjectFile(Sec->File->MB);
+  if (!Obj) {
+    error(toString(Sec->File) + ": error creating DWARF context");
+    return {};
+  }
+
+  DWARFContextInMemory Dwarf(*Obj.get());
+
+  GdbIndexChunk Ret;
+  Ret.CompilationUnits = readCuList(Dwarf, Sec);
+  Ret.AddressArea = readAddressArea(Dwarf, Sec);
+  Ret.NamesAndTypes = readPubNamesAndTypes(Dwarf, Config->IsLE);
+  return Ret;
 
-    CuVectors[Sym->CuVectorIndex].insert((Pair.second << 24) | (uint32_t)CuId);
-  }
+static size_t getCuSize(std::vector<GdbIndexChunk> &C) {
+  size_t Ret = 0;
+  for (GdbIndexChunk &D : C)
+    Ret += D.CompilationUnits.size();
+  return Ret;
+
+static size_t getAddressAreaSize(std::vector<GdbIndexChunk> &C) {
+  size_t Ret = 0;
+  for (GdbIndexChunk &D : C)
+    Ret += D.AddressArea.size();
+  return Ret;
 }
 
 void GdbIndexSection::finalizeContents() {
   if (Finalized)
     return;
   Finalized = true;
 
-  for (InputSectionBase *S : InputSections)
-    if (InputSection *IS = dyn_cast<InputSection>(S))
-      if (IS->getParent() && IS->Name == ".debug_info")
-        readDwarf(IS);
+  buildIndex();
 
   SymbolTable.finalizeContents();
 
   // GdbIndex header consist from version fields
   // and 5 more fields with different kinds of offsets.
-  CuTypesOffset = CuListOffset + CompilationUnits.size() * CompilationUnitSize;
-  SymTabOffset = CuTypesOffset + AddressArea.size() * AddressEntrySize;
+  CuTypesOffset = CuListOffset + getCuSize(Chunks) * CompilationUnitSize;
+  SymTabOffset = CuTypesOffset + getAddressAreaSize(Chunks) * AddressEntrySize;
 
   ConstantPoolOffset =
       SymTabOffset + SymbolTable.getCapacity() * SymTabEntrySize;
 
   for (std::set<uint32_t> &CuVec : CuVectors) {
     CuVectorsOffset.push_back(CuVectorsSize);
     CuVectorsSize += OffsetTypeSize * (CuVec.size() + 1);
   }
void GdbIndexSection::writeTo(uint8_t *Buf) {
   write32le(Buf + 4, CuListOffset);        // CU list offset.
   write32le(Buf + 8, CuTypesOffset);       // Types CU list offset.
   write32le(Buf + 12, CuTypesOffset);      // Address area offset.
   write32le(Buf + 16, SymTabOffset);       // Symbol table offset.
   write32le(Buf + 20, ConstantPoolOffset); // Constant pool offset.
   Buf += 24;
 
   // Write the CU list.
-  for (std::pair<uint64_t, uint64_t> CU : CompilationUnits) {
-    write64le(Buf, CU.first);
-    write64le(Buf + 8, CU.second);
+  for (GdbIndexChunk &D : Chunks) {
+    for (CompilationUnitEntry &Cu : D.CompilationUnits) {
+      write64le(Buf, Cu.CuOffset);
+      write64le(Buf + 8, Cu.CuLength);
       Buf += 16;
     }
+  }
 
   // Write the address area.
-  for (AddressEntry &E : AddressArea) {
-    uint64_t BaseAddr = E.Section->getParent()->Addr + E.Section->getOffset(0);
+  for (GdbIndexChunk &D : Chunks) {
+    for (AddressEntry &E : D.AddressArea) {
+      uint64_t BaseAddr =
+          E.Section->getParent()->Addr + E.Section->getOffset(0);
       write64le(Buf, BaseAddr + E.LowAddress);
       write64le(Buf + 8, BaseAddr + E.HighAddress);
       write32le(Buf + 16, E.CuIndex);
       Buf += 20;
     }
+  }
 
   // Write the symbol table.
   for (size_t I = 0; I < SymbolTable.getCapacity(); ++I) {
     GdbSymbol *Sym = SymbolTable.getSymbol(I);
     if (Sym) {
       size_t NameOffset =
           Sym->NameOffset + StringPoolOffset - ConstantPoolOffset;
       size_t CuVectorOffset = CuVectorsOffset[Sym->CuVectorIndex];