[ELF] .gdb_index: fix CuOff when a .debug_info section contains more than 1 CU

[MaskRay]

Summary

Idx passed to readPubNamesAndTypes was an index into Chunks, not an
index into the CU list. This would be incorrect if some .debug_info
section contained more than 1 CU.

In real world, glibc Scrt1.o is a partial link of start.os abi-note.o init.o and contains 2 CUs in debug builds.
Without this patch, any application linking such Scrt1.o would have invalid .gdb_index
The issue could be demonstrated by:

(gdb) py print(gdb.lookup_global_symbol('main'))
None

[MaskRay]

.

[MaskRay]

.

[dblaikie]

I think this would fail at least in the following example:

• Compile one file with gnu-pubnames and one withou
• ld -r the two together (non-pubnames first, then pubnames one)
• link those

I believe that'll produce a different (& incorrect) gdb-index compared to skipping the -r step and linking the two objects directly, maybe? (I haven't looked at the code carefully/completely enough to understand the CU counting aspect - but suffice to say, the linker shouldn't assume there are as many gnu_pubnames contributions/sets as there are CUs - or that they're in the same order, for that matter)

Probably the right solution is to store the Offset (DWARFDebugPubTable::Set::Offset) that describes the CU from the pubnames - then lookup that offset to determine the CU index - possibly by a search within a sorted list of CU offsets, built by a walk of the CUs in the input)

[MaskRay]

Use debug_info_offset to index into CUs

[MaskRay]

Description

[grimar]

Testcase?

[MaskRay]

Add test gdb-index-multiple-cu.s

[MaskRay]

Rebase

[ruiu]

ELF/SyntheticSections.cpp

2425–2426

Not sure if I understand this comment, because this comment explains only the tricky part of the code but doesn't explain the normal condition. I'd just explain what I represents and don't focus too much on the detail.

2428

Can you use a regular for loop instead of std::lower_bound? I think std::lower_bound with a lambda is not very easy to read because because a lambda of the third argument takes two arguments, even though Off is actually just Set.Offset in this case.

[MaskRay]

Address comments

[MaskRay]

The thing we've done in readPubNamesAndTypes (try getting the correct CuIndexInObject) is a plus. The mechanism is not clearly specified and I think gold only handles the first .debug_gnu_pubnames set and ignores the rest.

https://sourceware.org/git/?p=binutils-gdb.git;a=blob;hb=160fc977b6f33e5ef51f6c1f3cdcb57965c522c8;f=gold/gdb-index.cc#l864

[ruiu]

LGTM

[dblaikie]

(ah, I see I hadn't posted my first feedback earlier (written but unsubmitted) - oops, sorry about that)

ELF/SyntheticSections.cpp

2431

CUs[*].CuOff is necessarily increasing, because it's the offset as the CUs are read from the input, but there's no reason to believe that Set.Offset is necessarily increasing - pubnames could be in any order relative to the CUs.

lld/trunk/ELF/SyntheticSections.cpp

2432 ↗

(On Diff #173818)

Could you fix this? This assumption seems pretty subtle/likely to break valid DWARF in surprising/hard to diagnose ways.

Moving the declaration of I into the for(Set) loop (ie: putting it just before this while loop) should suffice - and a test case with 2 pubnames in the reverse order to CUs would demonstrate the fix?

(would be nice to do a binary search rather than a linear one on the CU offsets, since they are naturally sorted by offset)

[MaskRay]

lld/trunk/ELF/SyntheticSections.cpp

2432 ↗

(On Diff #173818)

I used std::lower_bound(CUs.begin(), CUs.end(), ...) - CUs.begin()) in a former version but @ruiu thought it was too complicated...

[dblaikie]

lld/trunk/ELF/SyntheticSections.cpp

2432 ↗

(On Diff #173818)

*nod* std::lower_bound is a somewhat awkward API, but the general goal of using a binary search still seems achievable with readable/not-so-awkward code.

Having a convenient binary search API that takes a lambda/functor without also taking the comparison object, instead relying on the functor to have that parameter hardcoded/captured, seems useful. Not sure what to name it (naming it llvm::binary_search would be likely to get mixed up with the interface to std::binary_search, which has the similar API quirks to std::lower_bound, unfortunately) though.

ELF/SyntheticSections.cpp

for (DWARFAddressRange &R : Ranges) {
       Ret.push_back({IS, R.LowPC - Offset, R.HighPC - Offset, CuIdx});
     }
     ++CuIdx;
   }
   return Ret;
 }
 
 static std::vector<GdbIndexSection::NameTypeEntry>
-readPubNamesAndTypes(DWARFContext &Dwarf, uint32_t Idx) {
+readPubNamesAndTypes(DWARFContext &Dwarf,
+                     const std::vector<GdbIndexSection::CuEntry> &CUs) {
   StringRef Sec1 = Dwarf.getDWARFObj().getGnuPubNamesSection();
   StringRef Sec2 = Dwarf.getDWARFObj().getGnuPubTypesSection();
 
   std::vector<GdbIndexSection::NameTypeEntry> Ret;
   for (StringRef Sec : {Sec1, Sec2}) {
     DWARFDebugPubTable Table(Sec, Config->IsLE, true);
-    for (const DWARFDebugPubTable::Set &Set : Table.getData())
+    for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
+      // The CU offset should be added to I when the entry is written into the
+      // constant pool.
+      uint32_t I =
+          std::lower_bound(CUs.begin(), CUs.end(), Set.Offset,
+                           [](const GdbIndexSection::CuEntry &CU,
+                              uint32_t Off) { return CU.CuOffset < Off; }) -
+          CUs.begin();
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
         Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
-                       (Ent.Descriptor.toBits() << 24) | Idx});
+                       (Ent.Descriptor.toBits() << 24) | I});
+    }
   }
   return Ret;
 }
 
 // Create a list of symbols from a given list of symbol names and types
 // by uniquifying them by name.
 static std::vector<GdbIndexSection::GdbSymbol>
-createSymbols(ArrayRef<std::vector<GdbIndexSection::NameTypeEntry>> NameTypes) {
+createSymbols(ArrayRef<std::vector<GdbIndexSection::NameTypeEntry>> NameTypes,
+              const std::vector<GdbIndexSection::GdbChunk> &Chunks) {
   typedef GdbIndexSection::GdbSymbol GdbSymbol;
   typedef GdbIndexSection::NameTypeEntry NameTypeEntry;
 
+  uint32_t CuOff = 0;
+  std::vector<uint32_t> CuOffs(Chunks.size());
+  for (uint32_t I = 0, E = Chunks.size(); I != E; ++I) {
+    CuOffs[I] = CuOff;
+    CuOff += Chunks[I].CompilationUnits.size();
+  }
+
   // The number of symbols we will handle in this function is of the order
   // of millions for very large executables, so we use multi-threading to
   // speed it up.
   size_t NumShards = 32;
   size_t Concurrency = 1;
   if (ThreadsEnabled)
     Concurrency =
         std::min<size_t>(PowerOf2Floor(hardware_concurrency()), NumShards);
 
   // A sharded map to uniquify symbols by name.
   std::vector<DenseMap<CachedHashStringRef, size_t>> Map(NumShards);
   size_t Shift = 32 - countTrailingZeros(NumShards);
 
   // Instantiate GdbSymbols while uniqufying them by name.
   std::vector<std::vector<GdbSymbol>> Symbols(NumShards);
   parallelForEachN(0, Concurrency, [&](size_t ThreadId) {
+    uint32_t I = 0;
     for (ArrayRef<NameTypeEntry> Entries : NameTypes) {
       for (const NameTypeEntry &Ent : Entries) {
         size_t ShardId = Ent.Name.hash() >> Shift;
         if ((ShardId & (Concurrency - 1)) != ThreadId)
           continue;
 
+        uint32_t V = Ent.Type + CuOffs[I];
         size_t &Idx = Map[ShardId][Ent.Name];
         if (Idx) {
-          Symbols[ShardId][Idx - 1].CuVector.push_back(Ent.Type);
+          Symbols[ShardId][Idx - 1].CuVector.push_back(V);
           continue;
         }
 
         Idx = Symbols[ShardId].size() + 1;
-        Symbols[ShardId].push_back({Ent.Name, {Ent.Type}, 0, 0});
+        Symbols[ShardId].push_back({Ent.Name, {V}, 0, 0});
       }
+      ++I;
     }
   });
 
   size_t NumSymbols = 0;
   for (ArrayRef<GdbSymbol> V : Symbols)
     NumSymbols += V.size();
 
   // The return type is a flattened vector, so we'll copy each vector
template <class ELFT> GdbIndexSection *GdbIndexSection::create() {
 
   parallelForEachN(0, Sections.size(), [&](size_t I) {
     ObjFile<ELFT> *File = Sections[I]->getFile<ELFT>();
     DWARFContext Dwarf(make_unique<LLDDwarfObj<ELFT>>(File));
 
     Chunks[I].Sec = Sections[I];
     Chunks[I].CompilationUnits = readCuList(Dwarf);
     Chunks[I].AddressAreas = readAddressAreas(Dwarf, Sections[I]);
-    NameTypes[I] = readPubNamesAndTypes(Dwarf, I);
+    NameTypes[I] = readPubNamesAndTypes(Dwarf, Chunks[I].CompilationUnits);
   });
 
   auto *Ret = make<GdbIndexSection>();
   Ret->Chunks = std::move(Chunks);
-  Ret->Symbols = createSymbols(NameTypes);
+  Ret->Symbols = createSymbols(NameTypes, Ret->Chunks);
   Ret->initOutputSize();
   return Ret;
 }
 
 void GdbIndexSection::writeTo(uint8_t *Buf) {
   // Write the header.
   auto *Hdr = reinterpret_cast<GdbIndexHeader *>(Buf);
   uint8_t *Start = Buf;