[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

2426–2427 ↗

(On Diff #173616)

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.

2429 ↗

(On Diff #173616)

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

2432 ↗

(On Diff #173617)

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

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

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

*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.

lld/trunk/ELF/SyntheticSections.cpp

for (std::unique_ptr<DWARFUnit> &Cu : Dwarf.compile_units()) {
     }
     ++CuIdx;
   }
   return Ret;
 }
 
 template <class ELFT>
 static std::vector<GdbIndexSection::NameTypeEntry>
-readPubNamesAndTypes(DWARFContext &Dwarf, uint32_t Idx) {
-  auto &Obj = static_cast<const LLDDwarfObj<ELFT> &>(Dwarf.getDWARFObj());
+readPubNamesAndTypes(const LLDDwarfObj<ELFT> &Obj,
+                     const std::vector<GdbIndexSection::CuEntry> &CUs) {
   const DWARFSection &PubNames = Obj.getGnuPubNamesSection();
   const DWARFSection &PubTypes = Obj.getGnuPubTypesSection();
 
   std::vector<GdbIndexSection::NameTypeEntry> Ret;
   for (const DWARFSection *Pub : {&PubNames, &PubTypes}) {
     DWARFDebugPubTable Table(Obj, *Pub, Config->IsLE, true);
-    for (const DWARFDebugPubTable::Set &Set : Table.getData())
+    uint32_t I = 0;
+    for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
+      // The value written into the constant pool is Kind << 24 | CuIndex. As we
+      // don't know how many compilation units precede this object to compute
+      // CuIndex, we compute (Kind << 24 | CuIndexInThisObject) instead, and add
+      // the number of preceding compilation units later.
+      //
+      // We assume both CUs[*].CuOff and Set.Offset are increasing.
+      while (I < CUs.size() && CUs[I].CuOffset < Set.Offset)
+        ++I;
       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;
 
+  // For each chunk, compute the number of compilation units preceding it.
+  uint32_t CuIdx = 0;
+  std::vector<uint32_t> CuIdxs(Chunks.size());
+  for (uint32_t I = 0, E = Chunks.size(); I != E; ++I) {
+    CuIdxs[I] = CuIdx;
+    CuIdx += 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 + CuIdxs[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<ELFT>(Dwarf, I);
+    NameTypes[I] = readPubNamesAndTypes<ELFT>(
+        static_cast<const LLDDwarfObj<ELFT> &>(Dwarf.getDWARFObj()),
+        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;

lld/trunk/test/ELF/gdb-index-multiple-cu.s

+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld --gdb-index %t.o -o %t
+# RUN: llvm-dwarfdump -gdb-index %t | FileCheck %s
+
+# Kind << 24 | CuIndex = 48 << 24 | 1 = 0x30000001
+# CHECK: Constant pool
+# CHECK-NEXT: 0(0x0): 0x30000001
+
+.globl _start
+_start:
+  ret
+
+.section .debug_abbrev,"",@progbits
+  .byte 1              # Abbreviation Code
+  .byte 17             # DW_TAG_compile_unit
+  .byte 1              # DW_CHILDREN_yes
+  .ascii  "\264B"        # DW_AT_GNU_pubnames
+  .byte 12             # DW_FORM_flag
+  .byte 0              # EOM(1)
+  .byte 0              # EOM(2)
+  .byte 2              # Abbreviation Code
+  .byte 46             # DW_TAG_subprogram
+  .byte 0              # DW_CHILDREN_no
+  .byte 3              # DW_AT_name
+  .byte 8              # DW_FORM_string
+  .byte 0              # EOM(1)
+  .byte 0              # EOM(2)
+  .byte 0
+
+.section .debug_info,"",@progbits
+.Lcu_begin0:
+  .long .Lcu_end0 - .Lcu_begin0 - 4
+  .short  4              # DWARF version number
+  .long 0              # Offset Into Abbrev. Section
+  .byte 4              # Address Size
+  .byte 1              # Abbrev [1] DW_TAG_compile_unit
+  .byte 0              # DW_AT_GNU_pubnames
+  .byte 0
+.Lcu_end0:
+.Lcu_begin1:
+  .long .Lcu_end1 - .Lcu_begin1 - 4
+  .short  4              # DWARF version number
+  .long 0              # Offset Into Abbrev. Section
+  .byte 4              # Address Size
+.Ldie:
+  .byte 1              # Abbrev [1] DW_TAG_compile_unit
+  .byte 1              # DW_AT_GNU_pubnames
+  .byte 2              # Abbrev [2] DW_TAG_subprogram
+  .asciz  "_start"       # DW_AT_name
+  .byte 0
+.Lcu_end1:
+
+# .debug_gnu_pubnames has just one set, associated with .Lcu_begin1 (CuIndex: 1)
+.section .debug_gnu_pubnames,"",@progbits
+  .long .LpubNames_end1-.LpubNames_begin1
+.LpubNames_begin1:
+  .short  2              # Version
+  .long .Lcu_begin1    # CU Offset
+  .long .Lcu_end1 - .Lcu_begin1
+  .long .Ldie - .Lcu_begin1
+  .byte 48             # Kind: FUNCTION, EXTERNAL
+  .asciz  "_start"       # External Name
+  .long 0
+.LpubNames_end1: