contrib/llvm/tools/lld/ELF/GdbIndex.cpp

   1 //===- GdbIndex.cpp -------------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // File contains classes for implementation of --gdb-index command line option.
  11 //
  12 // If that option is used, linker should emit a .gdb_index section that allows
  13 // debugger to locate and read .dwo files, containing neccessary debug
  14 // information.
  15 // More information about implementation can be found in DWARF specification,
  16 // latest version is available at http://dwarfstd.org.
  17 //
  18 // .gdb_index section format:
  19 //  (Information is based on/taken from
  20 //  https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html (*))
  21 //
  22 // A mapped index consists of several areas, laid out in order:
  23 // 1) The file header.
  24 // 2) "The CU (compilation unit) list. This is a sequence of pairs of 64-bit
  25 //    little-endian values, sorted by the CU offset. The first element in each
  26 //    pair is the offset of a CU in the .debug_info section. The second element
  27 //    in each pair is the length of that CU. References to a CU elsewhere in the
  28 //    map are done using a CU index, which is just the 0-based index into this
  29 //    table. Note that if there are type CUs, then conceptually CUs and type CUs
  30 //    form a single list for the purposes of CU indices."(*)
  31 // 3) The types CU list. Depricated as .debug_types does not appear in the DWARF
  32 //    v5 specification.
  33 // 4) The address area. The address area is a sequence of address
  34 //    entries, where each entrie contains low address, high address and CU
  35 //    index.
  36 // 5) "The symbol table. This is an open-addressed hash table. The size of the
  37 //    hash table is always a power of 2. Each slot in the hash table consists of
  38 //    a pair of offset_type values. The first value is the offset of the
  39 //    symbol's name in the constant pool. The second value is the offset of the
  40 //    CU vector in the constant pool."(*)
  41 // 6) "The constant pool. This is simply a bunch of bytes. It is organized so
  42 //    that alignment is correct: CU vectors are stored first, followed by
  43 //    strings." (*)
  44 //
  45 // For constructing the .gdb_index section following steps should be performed:
  46 // 1) For file header nothing special should be done. It contains the offsets to
  47 //    the areas below.
  48 // 2) Scan the compilation unit headers of the .debug_info sections to build a
  49 //    list of compilation units.
  50 // 3) CU Types are no longer needed as DWARF skeleton type units never made it
  51 //    into the standard. lld does nothing to support parsing of .debug_types
  52 //    and generates empty types CU area in .gdb_index section.
  53 // 4) Address area entries are extracted from DW_TAG_compile_unit DIEs of
  54 //   .debug_info sections.
  55 // 5) For building the symbol table linker extracts the public names from the
  56 //   .debug_gnu_pubnames and .debug_gnu_pubtypes sections. Then it builds the
  57 //   hashtable in according to .gdb_index format specification.
  58 // 6) Constant pool is populated at the same time as symbol table.
  59 //===----------------------------------------------------------------------===//
  60
  61 #include "GdbIndex.h"
  62 #include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
  63 #include "llvm/Object/ELFObjectFile.h"
  64
  65 using namespace llvm;
  66 using namespace llvm::object;
  67 using namespace lld::elf;
  68
  69 template <class ELFT>
  70 GdbIndexBuilder<ELFT>::GdbIndexBuilder(InputSection<ELFT> *DebugInfoSec)
  71     : DebugInfoSec(DebugInfoSec) {
  72   if (Expected<std::unique_ptr<object::ObjectFile>> Obj =
  73           object::ObjectFile::createObjectFile(DebugInfoSec->getFile()->MB))
  74     Dwarf.reset(new DWARFContextInMemory(*Obj.get(), this));
  75   else
  76     error(toString(DebugInfoSec->getFile()) + ": error creating DWARF context");
  77 }
  78
  79 template <class ELFT>
  80 std::vector<std::pair<typename ELFT::uint, typename ELFT::uint>>
  81 GdbIndexBuilder<ELFT>::readCUList() {
  82   std::vector<std::pair<uintX_t, uintX_t>> Ret;
  83   for (std::unique_ptr<DWARFCompileUnit> &CU : Dwarf->compile_units())
  84     Ret.push_back(
  85         {DebugInfoSec->OutSecOff + CU->getOffset(), CU->getLength() + 4});
  86   return Ret;
  87 }
  88
  89 template <class ELFT>
  90 std::vector<std::pair<StringRef, uint8_t>>
  91 GdbIndexBuilder<ELFT>::readPubNamesAndTypes() {
  92   const bool IsLE = ELFT::TargetEndianness == llvm::support::little;
  93   StringRef Data[] = {Dwarf->getGnuPubNamesSection(),
  94                       Dwarf->getGnuPubTypesSection()};
  95
  96   std::vector<std::pair<StringRef, uint8_t>> Ret;
  97   for (StringRef D : Data) {
  98     DWARFDebugPubTable PubTable(D, IsLE, true);
  99     for (const DWARFDebugPubTable::Set &S : PubTable.getData())
 100       for (const DWARFDebugPubTable::Entry &E : S.Entries)
 101         Ret.push_back({E.Name, E.Descriptor.toBits()});
 102   }
 103   return Ret;
 104 }
 105
 106 std::pair<bool, GdbSymbol *> GdbHashTab::add(uint32_t Hash, size_t Offset) {
 107   if (Size * 4 / 3 >= Table.size())
 108     expand();
 109
 110   GdbSymbol **Slot = findSlot(Hash, Offset);
 111   bool New = false;
 112   if (*Slot == nullptr) {
 113     ++Size;
 114     *Slot = new (Alloc) GdbSymbol(Hash, Offset);
 115     New = true;
 116   }
 117   return {New, *Slot};
 118 }
 119
 120 void GdbHashTab::expand() {
 121   if (Table.empty()) {
 122     Table.resize(InitialSize);
 123     return;
 124   }
 125   std::vector<GdbSymbol *> NewTable(Table.size() * 2);
 126   NewTable.swap(Table);
 127
 128   for (GdbSymbol *Sym : NewTable) {
 129     if (!Sym)
 130       continue;
 131     GdbSymbol **Slot = findSlot(Sym->NameHash, Sym->NameOffset);
 132     *Slot = Sym;
 133   }
 134 }
 135
 136 // Methods finds a slot for symbol with given hash. The step size used to find
 137 // the next candidate slot when handling a hash collision is specified in
 138 // .gdb_index section format. The hash value for a table entry is computed by
 139 // applying an iterative hash function to the symbol's name.
 140 GdbSymbol **GdbHashTab::findSlot(uint32_t Hash, size_t Offset) {
 141   uint32_t Index = Hash & (Table.size() - 1);
 142   uint32_t Step = ((Hash * 17) & (Table.size() - 1)) | 1;
 143
 144   for (;;) {
 145     GdbSymbol *S = Table[Index];
 146     if (!S || ((S->NameOffset == Offset) && (S->NameHash == Hash)))
 147       return &Table[Index];
 148     Index = (Index + Step) & (Table.size() - 1);
 149   }
 150 }
 151
 152 template <class ELFT>
 153 static InputSectionBase<ELFT> *
 154 findSection(ArrayRef<InputSectionBase<ELFT> *> Arr, uint64_t Offset) {
 155   for (InputSectionBase<ELFT> *S : Arr)
 156     if (S && S != &InputSection<ELFT>::Discarded)
 157       if (Offset >= S->Offset && Offset < S->Offset + S->getSize())
 158         return S;
 159   return nullptr;
 160 }
 161
 162 template <class ELFT>
 163 std::vector<AddressEntry<ELFT>>
 164 GdbIndexBuilder<ELFT>::readAddressArea(size_t CurrentCU) {
 165   std::vector<AddressEntry<ELFT>> Ret;
 166   for (const auto &CU : Dwarf->compile_units()) {
 167     DWARFAddressRangesVector Ranges;
 168     CU->collectAddressRanges(Ranges);
 169
 170     ArrayRef<InputSectionBase<ELFT> *> Sections =
 171         DebugInfoSec->getFile()->getSections();
 172
 173     for (std::pair<uint64_t, uint64_t> &R : Ranges)
 174       if (InputSectionBase<ELFT> *S = findSection(Sections, R.first))
 175         Ret.push_back(
 176             {S, R.first - S->Offset, R.second - S->Offset, CurrentCU});
 177     ++CurrentCU;
 178   }
 179   return Ret;
 180 }
 181
 182 // We return file offset as load address for allocatable sections. That is
 183 // currently used for collecting address ranges in readAddressArea(). We are
 184 // able then to find section index that range belongs to.
 185 template <class ELFT>
 186 uint64_t GdbIndexBuilder<ELFT>::getSectionLoadAddress(
 187     const object::SectionRef &Sec) const {
 188   if (static_cast<const ELFSectionRef &>(Sec).getFlags() & ELF::SHF_ALLOC)
 189     return static_cast<const ELFSectionRef &>(Sec).getOffset();
 190   return 0;
 191 }
 192
 193 template <class ELFT>
 194 std::unique_ptr<LoadedObjectInfo> GdbIndexBuilder<ELFT>::clone() const {
 195   return {};
 196 }
 197
 198 namespace lld {
 199 namespace elf {
 200 template class GdbIndexBuilder<ELF32LE>;
 201 template class GdbIndexBuilder<ELF32BE>;
 202 template class GdbIndexBuilder<ELF64LE>;
 203 template class GdbIndexBuilder<ELF64BE>;
 204 }
 205 }