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

   1 //===- OutputSections.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 #include "OutputSections.h"
  11 #include "Config.h"
  12 #include "EhFrame.h"
  13 #include "LinkerScript.h"
  14 #include "Strings.h"
  15 #include "SymbolTable.h"
  16 #include "Target.h"
  17 #include "lld/Core/Parallel.h"
  18 #include "llvm/Support/Dwarf.h"
  19 #include "llvm/Support/MD5.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include "llvm/Support/SHA1.h"
  22 #include <map>
  23
  24 using namespace llvm;
  25 using namespace llvm::dwarf;
  26 using namespace llvm::object;
  27 using namespace llvm::support::endian;
  28 using namespace llvm::ELF;
  29
  30 using namespace lld;
  31 using namespace lld::elf;
  32
  33 template <class ELFT>
  34 OutputSectionBase<ELFT>::OutputSectionBase(StringRef Name, uint32_t Type,
  35                                            uintX_t Flags)
  36     : Name(Name) {
  37   memset(&Header, 0, sizeof(Elf_Shdr));
  38   Header.sh_type = Type;
  39   Header.sh_flags = Flags;
  40   Header.sh_addralign = 1;
  41 }
  42
  43 template <class ELFT>
  44 void OutputSectionBase<ELFT>::writeHeaderTo(Elf_Shdr *Shdr) {
  45   *Shdr = Header;
  46 }
  47
  48 template <class ELFT>
  49 GotPltSection<ELFT>::GotPltSection()
  50     : OutputSectionBase<ELFT>(".got.plt", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE) {
  51   this->Header.sh_addralign = Target->GotPltEntrySize;
  52 }
  53
  54 template <class ELFT> void GotPltSection<ELFT>::addEntry(SymbolBody &Sym) {
  55   Sym.GotPltIndex = Target->GotPltHeaderEntriesNum + Entries.size();
  56   Entries.push_back(&Sym);
  57 }
  58
  59 template <class ELFT> bool GotPltSection<ELFT>::empty() const {
  60   return Entries.empty();
  61 }
  62
  63 template <class ELFT> void GotPltSection<ELFT>::finalize() {
  64   this->Header.sh_size = (Target->GotPltHeaderEntriesNum + Entries.size()) *
  65                          Target->GotPltEntrySize;
  66 }
  67
  68 template <class ELFT> void GotPltSection<ELFT>::writeTo(uint8_t *Buf) {
  69   Target->writeGotPltHeader(Buf);
  70   Buf += Target->GotPltHeaderEntriesNum * Target->GotPltEntrySize;
  71   for (const SymbolBody *B : Entries) {
  72     Target->writeGotPlt(Buf, *B);
  73     Buf += sizeof(uintX_t);
  74   }
  75 }
  76
  77 template <class ELFT>
  78 GotSection<ELFT>::GotSection()
  79     : OutputSectionBase<ELFT>(".got", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE) {
  80   if (Config->EMachine == EM_MIPS)
  81     this->Header.sh_flags |= SHF_MIPS_GPREL;
  82   this->Header.sh_addralign = Target->GotEntrySize;
  83 }
  84
  85 template <class ELFT>
  86 void GotSection<ELFT>::addEntry(SymbolBody &Sym) {
  87   Sym.GotIndex = Entries.size();
  88   Entries.push_back(&Sym);
  89 }
  90
  91 template <class ELFT>
  92 void GotSection<ELFT>::addMipsEntry(SymbolBody &Sym, uintX_t Addend,
  93                                     RelExpr Expr) {
  94   // For "true" local symbols which can be referenced from the same module
  95   // only compiler creates two instructions for address loading:
  96   //
  97   // lw   $8, 0($gp) # R_MIPS_GOT16
  98   // addi $8, $8, 0  # R_MIPS_LO16
  99   //
 100   // The first instruction loads high 16 bits of the symbol address while
 101   // the second adds an offset. That allows to reduce number of required
 102   // GOT entries because only one global offset table entry is necessary
 103   // for every 64 KBytes of local data. So for local symbols we need to
 104   // allocate number of GOT entries to hold all required "page" addresses.
 105   //
 106   // All global symbols (hidden and regular) considered by compiler uniformly.
 107   // It always generates a single `lw` instruction and R_MIPS_GOT16 relocation
 108   // to load address of the symbol. So for each such symbol we need to
 109   // allocate dedicated GOT entry to store its address.
 110   //
 111   // If a symbol is preemptible we need help of dynamic linker to get its
 112   // final address. The corresponding GOT entries are allocated in the
 113   // "global" part of GOT. Entries for non preemptible global symbol allocated
 114   // in the "local" part of GOT.
 115   //
 116   // See "Global Offset Table" in Chapter 5:
 117   // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 118   if (Expr == R_MIPS_GOT_LOCAL_PAGE) {
 119     // At this point we do not know final symbol value so to reduce number
 120     // of allocated GOT entries do the following trick. Save all output
 121     // sections referenced by GOT relocations. Then later in the `finalize`
 122     // method calculate number of "pages" required to cover all saved output
 123     // section and allocate appropriate number of GOT entries.
 124     auto *OutSec = cast<DefinedRegular<ELFT>>(&Sym)->Section->OutSec;
 125     MipsOutSections.insert(OutSec);
 126     return;
 127   }
 128   if (Sym.isTls()) {
 129     // GOT entries created for MIPS TLS relocations behave like
 130     // almost GOT entries from other ABIs. They go to the end
 131     // of the global offset table.
 132     Sym.GotIndex = Entries.size();
 133     Entries.push_back(&Sym);
 134     return;
 135   }
 136   auto AddEntry = [&](SymbolBody &S, uintX_t A, MipsGotEntries &Items) {
 137     if (S.isInGot() && !A)
 138       return;
 139     size_t NewIndex = Items.size();
 140     if (!MipsGotMap.insert({{&S, A}, NewIndex}).second)
 141       return;
 142     Items.emplace_back(&S, A);
 143     if (!A)
 144       S.GotIndex = NewIndex;
 145   };
 146   if (Sym.isPreemptible()) {
 147     // Ignore addends for preemptible symbols. They got single GOT entry anyway.
 148     AddEntry(Sym, 0, MipsGlobal);
 149     Sym.IsInGlobalMipsGot = true;
 150   } else
 151     AddEntry(Sym, Addend, MipsLocal);
 152 }
 153
 154 template <class ELFT> bool GotSection<ELFT>::addDynTlsEntry(SymbolBody &Sym) {
 155   if (Sym.GlobalDynIndex != -1U)
 156     return false;
 157   Sym.GlobalDynIndex = Entries.size();
 158   // Global Dynamic TLS entries take two GOT slots.
 159   Entries.push_back(nullptr);
 160   Entries.push_back(&Sym);
 161   return true;
 162 }
 163
 164 // Reserves TLS entries for a TLS module ID and a TLS block offset.
 165 // In total it takes two GOT slots.
 166 template <class ELFT> bool GotSection<ELFT>::addTlsIndex() {
 167   if (TlsIndexOff != uint32_t(-1))
 168     return false;
 169   TlsIndexOff = Entries.size() * sizeof(uintX_t);
 170   Entries.push_back(nullptr);
 171   Entries.push_back(nullptr);
 172   return true;
 173 }
 174
 175 template <class ELFT>
 176 typename GotSection<ELFT>::uintX_t
 177 GotSection<ELFT>::getMipsLocalPageOffset(uintX_t EntryValue) {
 178   // Initialize the entry by the %hi(EntryValue) expression
 179   // but without right-shifting.
 180   EntryValue = (EntryValue + 0x8000) & ~0xffff;
 181   // Take into account MIPS GOT header.
 182   // See comment in the GotSection::writeTo.
 183   size_t NewIndex = MipsLocalGotPos.size() + 2;
 184   auto P = MipsLocalGotPos.insert(std::make_pair(EntryValue, NewIndex));
 185   assert(!P.second || MipsLocalGotPos.size() <= MipsPageEntries);
 186   return (uintX_t)P.first->second * sizeof(uintX_t) - MipsGPOffset;
 187 }
 188
 189 template <class ELFT>
 190 typename GotSection<ELFT>::uintX_t
 191 GotSection<ELFT>::getMipsGotOffset(const SymbolBody &B, uintX_t Addend) const {
 192   uintX_t Off = MipsPageEntries;
 193   if (B.isTls())
 194     Off += MipsLocal.size() + MipsGlobal.size() + B.GotIndex;
 195   else if (B.IsInGlobalMipsGot)
 196     Off += MipsLocal.size() + B.GotIndex;
 197   else if (B.isInGot())
 198     Off += B.GotIndex;
 199   else {
 200     auto It = MipsGotMap.find({&B, Addend});
 201     assert(It != MipsGotMap.end());
 202     Off += It->second;
 203   }
 204   return Off * sizeof(uintX_t) - MipsGPOffset;
 205 }
 206
 207 template <class ELFT>
 208 typename GotSection<ELFT>::uintX_t GotSection<ELFT>::getMipsTlsOffset() {
 209   return (MipsPageEntries + MipsLocal.size() + MipsGlobal.size()) *
 210          sizeof(uintX_t);
 211 }
 212
 213 template <class ELFT>
 214 typename GotSection<ELFT>::uintX_t
 215 GotSection<ELFT>::getGlobalDynAddr(const SymbolBody &B) const {
 216   return this->getVA() + B.GlobalDynIndex * sizeof(uintX_t);
 217 }
 218
 219 template <class ELFT>
 220 typename GotSection<ELFT>::uintX_t
 221 GotSection<ELFT>::getGlobalDynOffset(const SymbolBody &B) const {
 222   return B.GlobalDynIndex * sizeof(uintX_t);
 223 }
 224
 225 template <class ELFT>
 226 const SymbolBody *GotSection<ELFT>::getMipsFirstGlobalEntry() const {
 227   return MipsGlobal.empty() ? nullptr : MipsGlobal.front().first;
 228 }
 229
 230 template <class ELFT>
 231 unsigned GotSection<ELFT>::getMipsLocalEntriesNum() const {
 232   return MipsPageEntries + MipsLocal.size();
 233 }
 234
 235 template <class ELFT> void GotSection<ELFT>::finalize() {
 236   size_t EntriesNum = Entries.size();
 237   if (Config->EMachine == EM_MIPS) {
 238     // Take into account MIPS GOT header.
 239     // See comment in the GotSection::writeTo.
 240     MipsPageEntries += 2;
 241     for (const OutputSectionBase<ELFT> *OutSec : MipsOutSections) {
 242       // Calculate an upper bound of MIPS GOT entries required to store page
 243       // addresses of local symbols. We assume the worst case - each 64kb
 244       // page of the output section has at least one GOT relocation against it.
 245       // Add 0x8000 to the section's size because the page address stored
 246       // in the GOT entry is calculated as (value + 0x8000) & ~0xffff.
 247       MipsPageEntries += (OutSec->getSize() + 0x8000 + 0xfffe) / 0xffff;
 248     }
 249     EntriesNum += MipsPageEntries + MipsLocal.size() + MipsGlobal.size();
 250   }
 251   this->Header.sh_size = EntriesNum * sizeof(uintX_t);
 252 }
 253
 254 template <class ELFT> void GotSection<ELFT>::writeMipsGot(uint8_t *&Buf) {
 255   // Set the MSB of the second GOT slot. This is not required by any
 256   // MIPS ABI documentation, though.
 257   //
 258   // There is a comment in glibc saying that "The MSB of got[1] of a
 259   // gnu object is set to identify gnu objects," and in GNU gold it
 260   // says "the second entry will be used by some runtime loaders".
 261   // But how this field is being used is unclear.
 262   //
 263   // We are not really willing to mimic other linkers behaviors
 264   // without understanding why they do that, but because all files
 265   // generated by GNU tools have this special GOT value, and because
 266   // we've been doing this for years, it is probably a safe bet to
 267   // keep doing this for now. We really need to revisit this to see
 268   // if we had to do this.
 269   auto *P = reinterpret_cast<typename ELFT::Off *>(Buf);
 270   P[1] = uintX_t(1) << (ELFT::Is64Bits ? 63 : 31);
 271   // Write 'page address' entries to the local part of the GOT.
 272   for (std::pair<uintX_t, size_t> &L : MipsLocalGotPos) {
 273     uint8_t *Entry = Buf + L.second * sizeof(uintX_t);
 274     write<uintX_t, ELFT::TargetEndianness, sizeof(uintX_t)>(Entry, L.first);
 275   }
 276   Buf += MipsPageEntries * sizeof(uintX_t);
 277   auto AddEntry = [&](const MipsGotEntry &SA) {
 278     uint8_t *Entry = Buf;
 279     Buf += sizeof(uintX_t);
 280     const SymbolBody* Body = SA.first;
 281     uintX_t VA = Body->template getVA<ELFT>(SA.second);
 282     write<uintX_t, ELFT::TargetEndianness, sizeof(uintX_t)>(Entry, VA);
 283   };
 284   std::for_each(std::begin(MipsLocal), std::end(MipsLocal), AddEntry);
 285   std::for_each(std::begin(MipsGlobal), std::end(MipsGlobal), AddEntry);
 286 }
 287
 288 template <class ELFT> void GotSection<ELFT>::writeTo(uint8_t *Buf) {
 289   if (Config->EMachine == EM_MIPS)
 290     writeMipsGot(Buf);
 291   for (const SymbolBody *B : Entries) {
 292     uint8_t *Entry = Buf;
 293     Buf += sizeof(uintX_t);
 294     if (!B)
 295       continue;
 296     if (B->isPreemptible())
 297       continue; // The dynamic linker will take care of it.
 298     uintX_t VA = B->getVA<ELFT>();
 299     write<uintX_t, ELFT::TargetEndianness, sizeof(uintX_t)>(Entry, VA);
 300   }
 301 }
 302
 303 template <class ELFT>
 304 PltSection<ELFT>::PltSection()
 305     : OutputSectionBase<ELFT>(".plt", SHT_PROGBITS, SHF_ALLOC | SHF_EXECINSTR) {
 306   this->Header.sh_addralign = 16;
 307 }
 308
 309 template <class ELFT> void PltSection<ELFT>::writeTo(uint8_t *Buf) {
 310   // At beginning of PLT, we have code to call the dynamic linker
 311   // to resolve dynsyms at runtime. Write such code.
 312   Target->writePltHeader(Buf);
 313   size_t Off = Target->PltHeaderSize;
 314
 315   for (auto &I : Entries) {
 316     const SymbolBody *B = I.first;
 317     unsigned RelOff = I.second;
 318     uint64_t Got = B->getGotPltVA<ELFT>();
 319     uint64_t Plt = this->getVA() + Off;
 320     Target->writePlt(Buf + Off, Got, Plt, B->PltIndex, RelOff);
 321     Off += Target->PltEntrySize;
 322   }
 323 }
 324
 325 template <class ELFT> void PltSection<ELFT>::addEntry(SymbolBody &Sym) {
 326   Sym.PltIndex = Entries.size();
 327   unsigned RelOff = Out<ELFT>::RelaPlt->getRelocOffset();
 328   Entries.push_back(std::make_pair(&Sym, RelOff));
 329 }
 330
 331 template <class ELFT> void PltSection<ELFT>::finalize() {
 332   this->Header.sh_size =
 333       Target->PltHeaderSize + Entries.size() * Target->PltEntrySize;
 334 }
 335
 336 template <class ELFT>
 337 RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
 338     : OutputSectionBase<ELFT>(Name, Config->Rela ? SHT_RELA : SHT_REL,
 339                               SHF_ALLOC),
 340       Sort(Sort) {
 341   this->Header.sh_entsize = Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
 342   this->Header.sh_addralign = sizeof(uintX_t);
 343 }
 344
 345 template <class ELFT>
 346 void RelocationSection<ELFT>::addReloc(const DynamicReloc<ELFT> &Reloc) {
 347   Relocs.push_back(Reloc);
 348 }
 349
 350 template <class ELFT, class RelTy>
 351 static bool compRelocations(const RelTy &A, const RelTy &B) {
 352   return A.getSymbol(Config->Mips64EL) < B.getSymbol(Config->Mips64EL);
 353 }
 354
 355 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
 356   uint8_t *BufBegin = Buf;
 357   for (const DynamicReloc<ELFT> &Rel : Relocs) {
 358     auto *P = reinterpret_cast<Elf_Rela *>(Buf);
 359     Buf += Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
 360
 361     if (Config->Rela)
 362       P->r_addend = Rel.getAddend();
 363     P->r_offset = Rel.getOffset();
 364     if (Config->EMachine == EM_MIPS && Rel.getOutputSec() == Out<ELFT>::Got)
 365       // Dynamic relocation against MIPS GOT section make deal TLS entries
 366       // allocated in the end of the GOT. We need to adjust the offset to take
 367       // in account 'local' and 'global' GOT entries.
 368       P->r_offset += Out<ELFT>::Got->getMipsTlsOffset();
 369     P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->Mips64EL);
 370   }
 371
 372   if (Sort) {
 373     if (Config->Rela)
 374       std::stable_sort((Elf_Rela *)BufBegin,
 375                        (Elf_Rela *)BufBegin + Relocs.size(),
 376                        compRelocations<ELFT, Elf_Rela>);
 377     else
 378       std::stable_sort((Elf_Rel *)BufBegin, (Elf_Rel *)BufBegin + Relocs.size(),
 379                        compRelocations<ELFT, Elf_Rel>);
 380   }
 381 }
 382
 383 template <class ELFT> unsigned RelocationSection<ELFT>::getRelocOffset() {
 384   return this->Header.sh_entsize * Relocs.size();
 385 }
 386
 387 template <class ELFT> void RelocationSection<ELFT>::finalize() {
 388   this->Header.sh_link = Static ? Out<ELFT>::SymTab->SectionIndex
 389                                 : Out<ELFT>::DynSymTab->SectionIndex;
 390   this->Header.sh_size = Relocs.size() * this->Header.sh_entsize;
 391 }
 392
 393 template <class ELFT>
 394 InterpSection<ELFT>::InterpSection()
 395     : OutputSectionBase<ELFT>(".interp", SHT_PROGBITS, SHF_ALLOC) {
 396   this->Header.sh_size = Config->DynamicLinker.size() + 1;
 397 }
 398
 399 template <class ELFT> void InterpSection<ELFT>::writeTo(uint8_t *Buf) {
 400   StringRef S = Config->DynamicLinker;
 401   memcpy(Buf, S.data(), S.size());
 402 }
 403
 404 template <class ELFT>
 405 HashTableSection<ELFT>::HashTableSection()
 406     : OutputSectionBase<ELFT>(".hash", SHT_HASH, SHF_ALLOC) {
 407   this->Header.sh_entsize = sizeof(Elf_Word);
 408   this->Header.sh_addralign = sizeof(Elf_Word);
 409 }
 410
 411 static uint32_t hashSysv(StringRef Name) {
 412   uint32_t H = 0;
 413   for (char C : Name) {
 414     H = (H << 4) + C;
 415     uint32_t G = H & 0xf0000000;
 416     if (G)
 417       H ^= G >> 24;
 418     H &= ~G;
 419   }
 420   return H;
 421 }
 422
 423 template <class ELFT> void HashTableSection<ELFT>::finalize() {
 424   this->Header.sh_link = Out<ELFT>::DynSymTab->SectionIndex;
 425
 426   unsigned NumEntries = 2;                             // nbucket and nchain.
 427   NumEntries += Out<ELFT>::DynSymTab->getNumSymbols(); // The chain entries.
 428
 429   // Create as many buckets as there are symbols.
 430   // FIXME: This is simplistic. We can try to optimize it, but implementing
 431   // support for SHT_GNU_HASH is probably even more profitable.
 432   NumEntries += Out<ELFT>::DynSymTab->getNumSymbols();
 433   this->Header.sh_size = NumEntries * sizeof(Elf_Word);
 434 }
 435
 436 template <class ELFT> void HashTableSection<ELFT>::writeTo(uint8_t *Buf) {
 437   unsigned NumSymbols = Out<ELFT>::DynSymTab->getNumSymbols();
 438   auto *P = reinterpret_cast<Elf_Word *>(Buf);
 439   *P++ = NumSymbols; // nbucket
 440   *P++ = NumSymbols; // nchain
 441
 442   Elf_Word *Buckets = P;
 443   Elf_Word *Chains = P + NumSymbols;
 444
 445   for (const std::pair<SymbolBody *, unsigned> &P :
 446        Out<ELFT>::DynSymTab->getSymbols()) {
 447     SymbolBody *Body = P.first;
 448     StringRef Name = Body->getName();
 449     unsigned I = Body->DynsymIndex;
 450     uint32_t Hash = hashSysv(Name) % NumSymbols;
 451     Chains[I] = Buckets[Hash];
 452     Buckets[Hash] = I;
 453   }
 454 }
 455
 456 static uint32_t hashGnu(StringRef Name) {
 457   uint32_t H = 5381;
 458   for (uint8_t C : Name)
 459     H = (H << 5) + H + C;
 460   return H;
 461 }
 462
 463 template <class ELFT>
 464 GnuHashTableSection<ELFT>::GnuHashTableSection()
 465     : OutputSectionBase<ELFT>(".gnu.hash", SHT_GNU_HASH, SHF_ALLOC) {
 466   this->Header.sh_entsize = ELFT::Is64Bits ? 0 : 4;
 467   this->Header.sh_addralign = sizeof(uintX_t);
 468 }
 469
 470 template <class ELFT>
 471 unsigned GnuHashTableSection<ELFT>::calcNBuckets(unsigned NumHashed) {
 472   if (!NumHashed)
 473     return 0;
 474
 475   // These values are prime numbers which are not greater than 2^(N-1) + 1.
 476   // In result, for any particular NumHashed we return a prime number
 477   // which is not greater than NumHashed.
 478   static const unsigned Primes[] = {
 479       1,   1,    3,    3,    7,    13,    31,    61,    127,   251,
 480       509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071};
 481
 482   return Primes[std::min<unsigned>(Log2_32_Ceil(NumHashed),
 483                                    array_lengthof(Primes) - 1)];
 484 }
 485
 486 // Bloom filter estimation: at least 8 bits for each hashed symbol.
 487 // GNU Hash table requirement: it should be a power of 2,
 488 //   the minimum value is 1, even for an empty table.
 489 // Expected results for a 32-bit target:
 490 //   calcMaskWords(0..4)   = 1
 491 //   calcMaskWords(5..8)   = 2
 492 //   calcMaskWords(9..16)  = 4
 493 // For a 64-bit target:
 494 //   calcMaskWords(0..8)   = 1
 495 //   calcMaskWords(9..16)  = 2
 496 //   calcMaskWords(17..32) = 4
 497 template <class ELFT>
 498 unsigned GnuHashTableSection<ELFT>::calcMaskWords(unsigned NumHashed) {
 499   if (!NumHashed)
 500     return 1;
 501   return NextPowerOf2((NumHashed - 1) / sizeof(Elf_Off));
 502 }
 503
 504 template <class ELFT> void GnuHashTableSection<ELFT>::finalize() {
 505   unsigned NumHashed = Symbols.size();
 506   NBuckets = calcNBuckets(NumHashed);
 507   MaskWords = calcMaskWords(NumHashed);
 508   // Second hash shift estimation: just predefined values.
 509   Shift2 = ELFT::Is64Bits ? 6 : 5;
 510
 511   this->Header.sh_link = Out<ELFT>::DynSymTab->SectionIndex;
 512   this->Header.sh_size = sizeof(Elf_Word) * 4            // Header
 513                          + sizeof(Elf_Off) * MaskWords   // Bloom Filter
 514                          + sizeof(Elf_Word) * NBuckets   // Hash Buckets
 515                          + sizeof(Elf_Word) * NumHashed; // Hash Values
 516 }
 517
 518 template <class ELFT> void GnuHashTableSection<ELFT>::writeTo(uint8_t *Buf) {
 519   writeHeader(Buf);
 520   if (Symbols.empty())
 521     return;
 522   writeBloomFilter(Buf);
 523   writeHashTable(Buf);
 524 }
 525
 526 template <class ELFT>
 527 void GnuHashTableSection<ELFT>::writeHeader(uint8_t *&Buf) {
 528   auto *P = reinterpret_cast<Elf_Word *>(Buf);
 529   *P++ = NBuckets;
 530   *P++ = Out<ELFT>::DynSymTab->getNumSymbols() - Symbols.size();
 531   *P++ = MaskWords;
 532   *P++ = Shift2;
 533   Buf = reinterpret_cast<uint8_t *>(P);
 534 }
 535
 536 template <class ELFT>
 537 void GnuHashTableSection<ELFT>::writeBloomFilter(uint8_t *&Buf) {
 538   unsigned C = sizeof(Elf_Off) * 8;
 539
 540   auto *Masks = reinterpret_cast<Elf_Off *>(Buf);
 541   for (const SymbolData &Sym : Symbols) {
 542     size_t Pos = (Sym.Hash / C) & (MaskWords - 1);
 543     uintX_t V = (uintX_t(1) << (Sym.Hash % C)) |
 544                 (uintX_t(1) << ((Sym.Hash >> Shift2) % C));
 545     Masks[Pos] |= V;
 546   }
 547   Buf += sizeof(Elf_Off) * MaskWords;
 548 }
 549
 550 template <class ELFT>
 551 void GnuHashTableSection<ELFT>::writeHashTable(uint8_t *Buf) {
 552   Elf_Word *Buckets = reinterpret_cast<Elf_Word *>(Buf);
 553   Elf_Word *Values = Buckets + NBuckets;
 554
 555   int PrevBucket = -1;
 556   int I = 0;
 557   for (const SymbolData &Sym : Symbols) {
 558     int Bucket = Sym.Hash % NBuckets;
 559     assert(PrevBucket <= Bucket);
 560     if (Bucket != PrevBucket) {
 561       Buckets[Bucket] = Sym.Body->DynsymIndex;
 562       PrevBucket = Bucket;
 563       if (I > 0)
 564         Values[I - 1] |= 1;
 565     }
 566     Values[I] = Sym.Hash & ~1;
 567     ++I;
 568   }
 569   if (I > 0)
 570     Values[I - 1] |= 1;
 571 }
 572
 573 // Add symbols to this symbol hash table. Note that this function
 574 // destructively sort a given vector -- which is needed because
 575 // GNU-style hash table places some sorting requirements.
 576 template <class ELFT>
 577 void GnuHashTableSection<ELFT>::addSymbols(
 578     std::vector<std::pair<SymbolBody *, size_t>> &V) {
 579   // Ideally this will just be 'auto' but GCC 6.1 is not able
 580   // to deduce it correctly.
 581   std::vector<std::pair<SymbolBody *, size_t>>::iterator Mid =
 582       std::stable_partition(V.begin(), V.end(),
 583                             [](std::pair<SymbolBody *, size_t> &P) {
 584                               return P.first->isUndefined();
 585                             });
 586   if (Mid == V.end())
 587     return;
 588   for (auto I = Mid, E = V.end(); I != E; ++I) {
 589     SymbolBody *B = I->first;
 590     size_t StrOff = I->second;
 591     Symbols.push_back({B, StrOff, hashGnu(B->getName())});
 592   }
 593
 594   unsigned NBuckets = calcNBuckets(Symbols.size());
 595   std::stable_sort(Symbols.begin(), Symbols.end(),
 596                    [&](const SymbolData &L, const SymbolData &R) {
 597                      return L.Hash % NBuckets < R.Hash % NBuckets;
 598                    });
 599
 600   V.erase(Mid, V.end());
 601   for (const SymbolData &Sym : Symbols)
 602     V.push_back({Sym.Body, Sym.STName});
 603 }
 604
 605 // Returns the number of version definition entries. Because the first entry
 606 // is for the version definition itself, it is the number of versioned symbols
 607 // plus one. Note that we don't support multiple versions yet.
 608 static unsigned getVerDefNum() { return Config->VersionDefinitions.size() + 1; }
 609
 610 template <class ELFT>
 611 DynamicSection<ELFT>::DynamicSection()
 612     : OutputSectionBase<ELFT>(".dynamic", SHT_DYNAMIC, SHF_ALLOC | SHF_WRITE) {
 613   Elf_Shdr &Header = this->Header;
 614   Header.sh_addralign = sizeof(uintX_t);
 615   Header.sh_entsize = ELFT::Is64Bits ? 16 : 8;
 616
 617   // .dynamic section is not writable on MIPS.
 618   // See "Special Section" in Chapter 4 in the following document:
 619   // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 620   if (Config->EMachine == EM_MIPS)
 621     Header.sh_flags = SHF_ALLOC;
 622 }
 623
 624 template <class ELFT> void DynamicSection<ELFT>::finalize() {
 625   if (this->Header.sh_size)
 626     return; // Already finalized.
 627
 628   Elf_Shdr &Header = this->Header;
 629   Header.sh_link = Out<ELFT>::DynStrTab->SectionIndex;
 630
 631   auto Add = [=](Entry E) { Entries.push_back(E); };
 632
 633   // Add strings. We know that these are the last strings to be added to
 634   // DynStrTab and doing this here allows this function to set DT_STRSZ.
 635   if (!Config->RPath.empty())
 636     Add({Config->EnableNewDtags ? DT_RUNPATH : DT_RPATH,
 637          Out<ELFT>::DynStrTab->addString(Config->RPath)});
 638   for (const std::unique_ptr<SharedFile<ELFT>> &F :
 639        Symtab<ELFT>::X->getSharedFiles())
 640     if (F->isNeeded())
 641       Add({DT_NEEDED, Out<ELFT>::DynStrTab->addString(F->getSoName())});
 642   if (!Config->SoName.empty())
 643     Add({DT_SONAME, Out<ELFT>::DynStrTab->addString(Config->SoName)});
 644
 645   Out<ELFT>::DynStrTab->finalize();
 646
 647   if (Out<ELFT>::RelaDyn->hasRelocs()) {
 648     bool IsRela = Config->Rela;
 649     Add({IsRela ? DT_RELA : DT_REL, Out<ELFT>::RelaDyn});
 650     Add({IsRela ? DT_RELASZ : DT_RELSZ, Out<ELFT>::RelaDyn->getSize()});
 651     Add({IsRela ? DT_RELAENT : DT_RELENT,
 652          uintX_t(IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel))});
 653   }
 654   if (Out<ELFT>::RelaPlt && Out<ELFT>::RelaPlt->hasRelocs()) {
 655     Add({DT_JMPREL, Out<ELFT>::RelaPlt});
 656     Add({DT_PLTRELSZ, Out<ELFT>::RelaPlt->getSize()});
 657     Add({Config->EMachine == EM_MIPS ? DT_MIPS_PLTGOT : DT_PLTGOT,
 658          Out<ELFT>::GotPlt});
 659     Add({DT_PLTREL, uint64_t(Config->Rela ? DT_RELA : DT_REL)});
 660   }
 661
 662   Add({DT_SYMTAB, Out<ELFT>::DynSymTab});
 663   Add({DT_SYMENT, sizeof(Elf_Sym)});
 664   Add({DT_STRTAB, Out<ELFT>::DynStrTab});
 665   Add({DT_STRSZ, Out<ELFT>::DynStrTab->getSize()});
 666   if (Out<ELFT>::GnuHashTab)
 667     Add({DT_GNU_HASH, Out<ELFT>::GnuHashTab});
 668   if (Out<ELFT>::HashTab)
 669     Add({DT_HASH, Out<ELFT>::HashTab});
 670
 671   if (PreInitArraySec) {
 672     Add({DT_PREINIT_ARRAY, PreInitArraySec});
 673     Add({DT_PREINIT_ARRAYSZ, PreInitArraySec->getSize()});
 674   }
 675   if (InitArraySec) {
 676     Add({DT_INIT_ARRAY, InitArraySec});
 677     Add({DT_INIT_ARRAYSZ, (uintX_t)InitArraySec->getSize()});
 678   }
 679   if (FiniArraySec) {
 680     Add({DT_FINI_ARRAY, FiniArraySec});
 681     Add({DT_FINI_ARRAYSZ, (uintX_t)FiniArraySec->getSize()});
 682   }
 683
 684   if (SymbolBody *B = Symtab<ELFT>::X->find(Config->Init))
 685     Add({DT_INIT, B});
 686   if (SymbolBody *B = Symtab<ELFT>::X->find(Config->Fini))
 687     Add({DT_FINI, B});
 688
 689   uint32_t DtFlags = 0;
 690   uint32_t DtFlags1 = 0;
 691   if (Config->Bsymbolic)
 692     DtFlags |= DF_SYMBOLIC;
 693   if (Config->ZNodelete)
 694     DtFlags1 |= DF_1_NODELETE;
 695   if (Config->ZNow) {
 696     DtFlags |= DF_BIND_NOW;
 697     DtFlags1 |= DF_1_NOW;
 698   }
 699   if (Config->ZOrigin) {
 700     DtFlags |= DF_ORIGIN;
 701     DtFlags1 |= DF_1_ORIGIN;
 702   }
 703
 704   if (DtFlags)
 705     Add({DT_FLAGS, DtFlags});
 706   if (DtFlags1)
 707     Add({DT_FLAGS_1, DtFlags1});
 708
 709   if (!Config->Entry.empty())
 710     Add({DT_DEBUG, (uint64_t)0});
 711
 712   bool HasVerNeed = Out<ELFT>::VerNeed->getNeedNum() != 0;
 713   if (HasVerNeed || Out<ELFT>::VerDef)
 714     Add({DT_VERSYM, Out<ELFT>::VerSym});
 715   if (Out<ELFT>::VerDef) {
 716     Add({DT_VERDEF, Out<ELFT>::VerDef});
 717     Add({DT_VERDEFNUM, getVerDefNum()});
 718   }
 719   if (HasVerNeed) {
 720     Add({DT_VERNEED, Out<ELFT>::VerNeed});
 721     Add({DT_VERNEEDNUM, Out<ELFT>::VerNeed->getNeedNum()});
 722   }
 723
 724   if (Config->EMachine == EM_MIPS) {
 725     Add({DT_MIPS_RLD_VERSION, 1});
 726     Add({DT_MIPS_FLAGS, RHF_NOTPOT});
 727     Add({DT_MIPS_BASE_ADDRESS, Config->ImageBase});
 728     Add({DT_MIPS_SYMTABNO, Out<ELFT>::DynSymTab->getNumSymbols()});
 729     Add({DT_MIPS_LOCAL_GOTNO, Out<ELFT>::Got->getMipsLocalEntriesNum()});
 730     if (const SymbolBody *B = Out<ELFT>::Got->getMipsFirstGlobalEntry())
 731       Add({DT_MIPS_GOTSYM, B->DynsymIndex});
 732     else
 733       Add({DT_MIPS_GOTSYM, Out<ELFT>::DynSymTab->getNumSymbols()});
 734     Add({DT_PLTGOT, Out<ELFT>::Got});
 735     if (Out<ELFT>::MipsRldMap)
 736       Add({DT_MIPS_RLD_MAP, Out<ELFT>::MipsRldMap});
 737   }
 738
 739   // +1 for DT_NULL
 740   Header.sh_size = (Entries.size() + 1) * Header.sh_entsize;
 741 }
 742
 743 template <class ELFT> void DynamicSection<ELFT>::writeTo(uint8_t *Buf) {
 744   auto *P = reinterpret_cast<Elf_Dyn *>(Buf);
 745
 746   for (const Entry &E : Entries) {
 747     P->d_tag = E.Tag;
 748     switch (E.Kind) {
 749     case Entry::SecAddr:
 750       P->d_un.d_ptr = E.OutSec->getVA();
 751       break;
 752     case Entry::SymAddr:
 753       P->d_un.d_ptr = E.Sym->template getVA<ELFT>();
 754       break;
 755     case Entry::PlainInt:
 756       P->d_un.d_val = E.Val;
 757       break;
 758     }
 759     ++P;
 760   }
 761 }
 762
 763 template <class ELFT>
 764 EhFrameHeader<ELFT>::EhFrameHeader()
 765     : OutputSectionBase<ELFT>(".eh_frame_hdr", SHT_PROGBITS, SHF_ALLOC) {}
 766
 767 // .eh_frame_hdr contains a binary search table of pointers to FDEs.
 768 // Each entry of the search table consists of two values,
 769 // the starting PC from where FDEs covers, and the FDE's address.
 770 // It is sorted by PC.
 771 template <class ELFT> void EhFrameHeader<ELFT>::writeTo(uint8_t *Buf) {
 772   const endianness E = ELFT::TargetEndianness;
 773
 774   // Sort the FDE list by their PC and uniqueify. Usually there is only
 775   // one FDE for a PC (i.e. function), but if ICF merges two functions
 776   // into one, there can be more than one FDEs pointing to the address.
 777   auto Less = [](const FdeData &A, const FdeData &B) { return A.Pc < B.Pc; };
 778   std::stable_sort(Fdes.begin(), Fdes.end(), Less);
 779   auto Eq = [](const FdeData &A, const FdeData &B) { return A.Pc == B.Pc; };
 780   Fdes.erase(std::unique(Fdes.begin(), Fdes.end(), Eq), Fdes.end());
 781
 782   Buf[0] = 1;
 783   Buf[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;
 784   Buf[2] = DW_EH_PE_udata4;
 785   Buf[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4;
 786   write32<E>(Buf + 4, Out<ELFT>::EhFrame->getVA() - this->getVA() - 4);
 787   write32<E>(Buf + 8, Fdes.size());
 788   Buf += 12;
 789
 790   uintX_t VA = this->getVA();
 791   for (FdeData &Fde : Fdes) {
 792     write32<E>(Buf, Fde.Pc - VA);
 793     write32<E>(Buf + 4, Fde.FdeVA - VA);
 794     Buf += 8;
 795   }
 796 }
 797
 798 template <class ELFT> void EhFrameHeader<ELFT>::finalize() {
 799   // .eh_frame_hdr has a 12 bytes header followed by an array of FDEs.
 800   this->Header.sh_size = 12 + Out<ELFT>::EhFrame->NumFdes * 8;
 801 }
 802
 803 template <class ELFT>
 804 void EhFrameHeader<ELFT>::addFde(uint32_t Pc, uint32_t FdeVA) {
 805   Fdes.push_back({Pc, FdeVA});
 806 }
 807
 808 template <class ELFT>
 809 OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags)
 810     : OutputSectionBase<ELFT>(Name, Type, Flags) {
 811   if (Type == SHT_RELA)
 812     this->Header.sh_entsize = sizeof(Elf_Rela);
 813   else if (Type == SHT_REL)
 814     this->Header.sh_entsize = sizeof(Elf_Rel);
 815 }
 816
 817 template <class ELFT> void OutputSection<ELFT>::finalize() {
 818   uint32_t Type = this->Header.sh_type;
 819   if (Type != SHT_RELA && Type != SHT_REL)
 820     return;
 821   this->Header.sh_link = Out<ELFT>::SymTab->SectionIndex;
 822   // sh_info for SHT_REL[A] sections should contain the section header index of
 823   // the section to which the relocation applies.
 824   InputSectionBase<ELFT> *S = Sections[0]->getRelocatedSection();
 825   this->Header.sh_info = S->OutSec->SectionIndex;
 826 }
 827
 828 template <class ELFT>
 829 void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
 830   assert(C->Live);
 831   auto *S = cast<InputSection<ELFT>>(C);
 832   Sections.push_back(S);
 833   S->OutSec = this;
 834   this->updateAlignment(S->Alignment);
 835 }
 836
 837 // If an input string is in the form of "foo.N" where N is a number,
 838 // return N. Otherwise, returns 65536, which is one greater than the
 839 // lowest priority.
 840 static int getPriority(StringRef S) {
 841   size_t Pos = S.rfind('.');
 842   if (Pos == StringRef::npos)
 843     return 65536;
 844   int V;
 845   if (S.substr(Pos + 1).getAsInteger(10, V))
 846     return 65536;
 847   return V;
 848 }
 849
 850 // This function is called after we sort input sections
 851 // and scan relocations to setup sections' offsets.
 852 template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
 853   uintX_t Off = this->Header.sh_size;
 854   for (InputSection<ELFT> *S : Sections) {
 855     Off = alignTo(Off, S->Alignment);
 856     S->OutSecOff = Off;
 857     Off += S->getSize();
 858   }
 859   this->Header.sh_size = Off;
 860 }
 861
 862 // Sorts input sections by section name suffixes, so that .foo.N comes
 863 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 864 // We want to keep the original order if the priorities are the same
 865 // because the compiler keeps the original initialization order in a
 866 // translation unit and we need to respect that.
 867 // For more detail, read the section of the GCC's manual about init_priority.
 868 template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
 869   // Sort sections by priority.
 870   typedef std::pair<int, InputSection<ELFT> *> Pair;
 871   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 872
 873   std::vector<Pair> V;
 874   for (InputSection<ELFT> *S : Sections)
 875     V.push_back({getPriority(S->getSectionName()), S});
 876   std::stable_sort(V.begin(), V.end(), Comp);
 877   Sections.clear();
 878   for (Pair &P : V)
 879     Sections.push_back(P.second);
 880 }
 881
 882 // Returns true if S matches /Filename.?\.o$/.
 883 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
 884   if (!S.endswith(".o"))
 885     return false;
 886   S = S.drop_back(2);
 887   if (S.endswith(Filename))
 888     return true;
 889   return !S.empty() && S.drop_back().endswith(Filename);
 890 }
 891
 892 static bool isCrtbegin(StringRef S) { return isCrtBeginEnd(S, "crtbegin"); }
 893 static bool isCrtend(StringRef S) { return isCrtBeginEnd(S, "crtend"); }
 894
 895 // .ctors and .dtors are sorted by this priority from highest to lowest.
 896 //
 897 //  1. The section was contained in crtbegin (crtbegin contains
 898 //     some sentinel value in its .ctors and .dtors so that the runtime
 899 //     can find the beginning of the sections.)
 900 //
 901 //  2. The section has an optional priority value in the form of ".ctors.N"
 902 //     or ".dtors.N" where N is a number. Unlike .{init,fini}_array,
 903 //     they are compared as string rather than number.
 904 //
 905 //  3. The section is just ".ctors" or ".dtors".
 906 //
 907 //  4. The section was contained in crtend, which contains an end marker.
 908 //
 909 // In an ideal world, we don't need this function because .init_array and
 910 // .ctors are duplicate features (and .init_array is newer.) However, there
 911 // are too many real-world use cases of .ctors, so we had no choice to
 912 // support that with this rather ad-hoc semantics.
 913 template <class ELFT>
 914 static bool compCtors(const InputSection<ELFT> *A,
 915                       const InputSection<ELFT> *B) {
 916   bool BeginA = isCrtbegin(A->getFile()->getName());
 917   bool BeginB = isCrtbegin(B->getFile()->getName());
 918   if (BeginA != BeginB)
 919     return BeginA;
 920   bool EndA = isCrtend(A->getFile()->getName());
 921   bool EndB = isCrtend(B->getFile()->getName());
 922   if (EndA != EndB)
 923     return EndB;
 924   StringRef X = A->getSectionName();
 925   StringRef Y = B->getSectionName();
 926   assert(X.startswith(".ctors") || X.startswith(".dtors"));
 927   assert(Y.startswith(".ctors") || Y.startswith(".dtors"));
 928   X = X.substr(6);
 929   Y = Y.substr(6);
 930   if (X.empty() && Y.empty())
 931     return false;
 932   return X < Y;
 933 }
 934
 935 // Sorts input sections by the special rules for .ctors and .dtors.
 936 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 937 // Read the comment above.
 938 template <class ELFT> void OutputSection<ELFT>::sortCtorsDtors() {
 939   std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
 940 }
 941
 942 static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
 943   size_t I = 0;
 944   for (; I + A.size() < Size; I += A.size())
 945     memcpy(Buf + I, A.data(), A.size());
 946   memcpy(Buf + I, A.data(), Size - I);
 947 }
 948
 949 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
 950   ArrayRef<uint8_t> Filler = Script<ELFT>::X->getFiller(this->Name);
 951   if (!Filler.empty())
 952     fill(Buf, this->getSize(), Filler);
 953   if (Config->Threads) {
 954     parallel_for_each(Sections.begin(), Sections.end(),
 955                       [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
 956   } else {
 957     for (InputSection<ELFT> *C : Sections)
 958       C->writeTo(Buf);
 959   }
 960 }
 961
 962 template <class ELFT>
 963 EhOutputSection<ELFT>::EhOutputSection()
 964     : OutputSectionBase<ELFT>(".eh_frame", SHT_PROGBITS, SHF_ALLOC) {}
 965
 966 // Returns the first relocation that points to a region
 967 // between Begin and Begin+Size.
 968 template <class IntTy, class RelTy>
 969 static const RelTy *getReloc(IntTy Begin, IntTy Size, ArrayRef<RelTy> &Rels) {
 970   for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
 971     if (I->r_offset < Begin)
 972       continue;
 973
 974     // Truncate Rels for fast access. That means we expect that the
 975     // relocations are sorted and we are looking up symbols in
 976     // sequential order. It is naturally satisfied for .eh_frame.
 977     Rels = Rels.slice(I - Rels.begin());
 978     if (I->r_offset < Begin + Size)
 979       return I;
 980     return nullptr;
 981   }
 982   Rels = ArrayRef<RelTy>();
 983   return nullptr;
 984 }
 985
 986 // Search for an existing CIE record or create a new one.
 987 // CIE records from input object files are uniquified by their contents
 988 // and where their relocations point to.
 989 template <class ELFT>
 990 template <class RelTy>
 991 CieRecord *EhOutputSection<ELFT>::addCie(SectionPiece &Piece,
 992                                          EhInputSection<ELFT> *Sec,
 993                                          ArrayRef<RelTy> &Rels) {
 994   const endianness E = ELFT::TargetEndianness;
 995   if (read32<E>(Piece.data().data() + 4) != 0)
 996     fatal("CIE expected at beginning of .eh_frame: " + Sec->getSectionName());
 997
 998   SymbolBody *Personality = nullptr;
 999   if (const RelTy *Rel = getReloc(Piece.InputOff, Piece.size(), Rels))
1000     Personality = &Sec->getFile()->getRelocTargetSym(*Rel);
1001
1002   // Search for an existing CIE by CIE contents/relocation target pair.
1003   CieRecord *Cie = &CieMap[{Piece.data(), Personality}];
1004
1005   // If not found, create a new one.
1006   if (Cie->Piece == nullptr) {
1007     Cie->Piece = &Piece;
1008     Cies.push_back(Cie);
1009   }
1010   return Cie;
1011 }
1012
1013 // There is one FDE per function. Returns true if a given FDE
1014 // points to a live function.
1015 template <class ELFT>
1016 template <class RelTy>
1017 bool EhOutputSection<ELFT>::isFdeLive(SectionPiece &Piece,
1018                                       EhInputSection<ELFT> *Sec,
1019                                       ArrayRef<RelTy> &Rels) {
1020   const RelTy *Rel = getReloc(Piece.InputOff, Piece.size(), Rels);
1021   if (!Rel)
1022     fatal("FDE doesn't reference another section");
1023   SymbolBody &B = Sec->getFile()->getRelocTargetSym(*Rel);
1024   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
1025   if (!D || !D->Section)
1026     return false;
1027   InputSectionBase<ELFT> *Target = D->Section->Repl;
1028   return Target && Target->Live;
1029 }
1030
1031 // .eh_frame is a sequence of CIE or FDE records. In general, there
1032 // is one CIE record per input object file which is followed by
1033 // a list of FDEs. This function searches an existing CIE or create a new
1034 // one and associates FDEs to the CIE.
1035 template <class ELFT>
1036 template <class RelTy>
1037 void EhOutputSection<ELFT>::addSectionAux(EhInputSection<ELFT> *Sec,
1038                                           ArrayRef<RelTy> Rels) {
1039   const endianness E = ELFT::TargetEndianness;
1040
1041   DenseMap<size_t, CieRecord *> OffsetToCie;
1042   for (SectionPiece &Piece : Sec->Pieces) {
1043     // The empty record is the end marker.
1044     if (Piece.size() == 4)
1045       return;
1046
1047     size_t Offset = Piece.InputOff;
1048     uint32_t ID = read32<E>(Piece.data().data() + 4);
1049     if (ID == 0) {
1050       OffsetToCie[Offset] = addCie(Piece, Sec, Rels);
1051       continue;
1052     }
1053
1054     uint32_t CieOffset = Offset + 4 - ID;
1055     CieRecord *Cie = OffsetToCie[CieOffset];
1056     if (!Cie)
1057       fatal("invalid CIE reference");
1058
1059     if (!isFdeLive(Piece, Sec, Rels))
1060       continue;
1061     Cie->FdePieces.push_back(&Piece);
1062     NumFdes++;
1063   }
1064 }
1065
1066 template <class ELFT>
1067 void EhOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
1068   auto *Sec = cast<EhInputSection<ELFT>>(C);
1069   Sec->OutSec = this;
1070   this->updateAlignment(Sec->Alignment);
1071   Sections.push_back(Sec);
1072
1073   // .eh_frame is a sequence of CIE or FDE records. This function
1074   // splits it into pieces so that we can call
1075   // SplitInputSection::getSectionPiece on the section.
1076   Sec->split();
1077   if (Sec->Pieces.empty())
1078     return;
1079
1080   if (const Elf_Shdr *RelSec = Sec->RelocSection) {
1081     ELFFile<ELFT> &Obj = Sec->getFile()->getObj();
1082     if (RelSec->sh_type == SHT_RELA)
1083       addSectionAux(Sec, Obj.relas(RelSec));
1084     else
1085       addSectionAux(Sec, Obj.rels(RelSec));
1086     return;
1087   }
1088   addSectionAux(Sec, makeArrayRef<Elf_Rela>(nullptr, nullptr));
1089 }
1090
1091 template <class ELFT>
1092 static void writeCieFde(uint8_t *Buf, ArrayRef<uint8_t> D) {
1093   memcpy(Buf, D.data(), D.size());
1094
1095   // Fix the size field. -4 since size does not include the size field itself.
1096   const endianness E = ELFT::TargetEndianness;
1097   write32<E>(Buf, alignTo(D.size(), sizeof(typename ELFT::uint)) - 4);
1098 }
1099
1100 template <class ELFT> void EhOutputSection<ELFT>::finalize() {
1101   if (this->Header.sh_size)
1102     return; // Already finalized.
1103
1104   size_t Off = 0;
1105   for (CieRecord *Cie : Cies) {
1106     Cie->Piece->OutputOff = Off;
1107     Off += alignTo(Cie->Piece->size(), sizeof(uintX_t));
1108
1109     for (SectionPiece *Fde : Cie->FdePieces) {
1110       Fde->OutputOff = Off;
1111       Off += alignTo(Fde->size(), sizeof(uintX_t));
1112     }
1113   }
1114   this->Header.sh_size = Off;
1115 }
1116
1117 template <class ELFT> static uint64_t readFdeAddr(uint8_t *Buf, int Size) {
1118   const endianness E = ELFT::TargetEndianness;
1119   switch (Size) {
1120   case DW_EH_PE_udata2:
1121     return read16<E>(Buf);
1122   case DW_EH_PE_udata4:
1123     return read32<E>(Buf);
1124   case DW_EH_PE_udata8:
1125     return read64<E>(Buf);
1126   case DW_EH_PE_absptr:
1127     if (ELFT::Is64Bits)
1128       return read64<E>(Buf);
1129     return read32<E>(Buf);
1130   }
1131   fatal("unknown FDE size encoding");
1132 }
1133
1134 // Returns the VA to which a given FDE (on a mmap'ed buffer) is applied to.
1135 // We need it to create .eh_frame_hdr section.
1136 template <class ELFT>
1137 typename ELFT::uint EhOutputSection<ELFT>::getFdePc(uint8_t *Buf, size_t FdeOff,
1138                                                     uint8_t Enc) {
1139   // The starting address to which this FDE applies is
1140   // stored at FDE + 8 byte.
1141   size_t Off = FdeOff + 8;
1142   uint64_t Addr = readFdeAddr<ELFT>(Buf + Off, Enc & 0x7);
1143   if ((Enc & 0x70) == DW_EH_PE_absptr)
1144     return Addr;
1145   if ((Enc & 0x70) == DW_EH_PE_pcrel)
1146     return Addr + this->getVA() + Off;
1147   fatal("unknown FDE size relative encoding");
1148 }
1149
1150 template <class ELFT> void EhOutputSection<ELFT>::writeTo(uint8_t *Buf) {
1151   const endianness E = ELFT::TargetEndianness;
1152   for (CieRecord *Cie : Cies) {
1153     size_t CieOffset = Cie->Piece->OutputOff;
1154     writeCieFde<ELFT>(Buf + CieOffset, Cie->Piece->data());
1155
1156     for (SectionPiece *Fde : Cie->FdePieces) {
1157       size_t Off = Fde->OutputOff;
1158       writeCieFde<ELFT>(Buf + Off, Fde->data());
1159
1160       // FDE's second word should have the offset to an associated CIE.
1161       // Write it.
1162       write32<E>(Buf + Off + 4, Off + 4 - CieOffset);
1163     }
1164   }
1165
1166   for (EhInputSection<ELFT> *S : Sections)
1167     S->relocate(Buf, nullptr);
1168
1169   // Construct .eh_frame_hdr. .eh_frame_hdr is a binary search table
1170   // to get a FDE from an address to which FDE is applied. So here
1171   // we obtain two addresses and pass them to EhFrameHdr object.
1172   if (Out<ELFT>::EhFrameHdr) {
1173     for (CieRecord *Cie : Cies) {
1174       uint8_t Enc = getFdeEncoding<ELFT>(Cie->Piece->data());
1175       for (SectionPiece *Fde : Cie->FdePieces) {
1176         uintX_t Pc = getFdePc(Buf, Fde->OutputOff, Enc);
1177         uintX_t FdeVA = this->getVA() + Fde->OutputOff;
1178         Out<ELFT>::EhFrameHdr->addFde(Pc, FdeVA);
1179       }
1180     }
1181   }
1182 }
1183
1184 template <class ELFT>
1185 MergeOutputSection<ELFT>::MergeOutputSection(StringRef Name, uint32_t Type,
1186                                              uintX_t Flags, uintX_t Alignment)
1187     : OutputSectionBase<ELFT>(Name, Type, Flags),
1188       Builder(StringTableBuilder::RAW, Alignment) {}
1189
1190 template <class ELFT> void MergeOutputSection<ELFT>::writeTo(uint8_t *Buf) {
1191   if (shouldTailMerge()) {
1192     StringRef Data = Builder.data();
1193     memcpy(Buf, Data.data(), Data.size());
1194     return;
1195   }
1196   for (const std::pair<CachedHash<StringRef>, size_t> &P : Builder.getMap()) {
1197     StringRef Data = P.first.Val;
1198     memcpy(Buf + P.second, Data.data(), Data.size());
1199   }
1200 }
1201
1202 static StringRef toStringRef(ArrayRef<uint8_t> A) {
1203   return {(const char *)A.data(), A.size()};
1204 }
1205
1206 template <class ELFT>
1207 void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
1208   auto *Sec = cast<MergeInputSection<ELFT>>(C);
1209   Sec->OutSec = this;
1210   this->updateAlignment(Sec->Alignment);
1211   this->Header.sh_entsize = Sec->getSectionHdr()->sh_entsize;
1212   Sections.push_back(Sec);
1213
1214   bool IsString = this->Header.sh_flags & SHF_STRINGS;
1215
1216   for (SectionPiece &Piece : Sec->Pieces) {
1217     if (!Piece.Live)
1218       continue;
1219     uintX_t OutputOffset = Builder.add(toStringRef(Piece.data()));
1220     if (!IsString || !shouldTailMerge())
1221       Piece.OutputOff = OutputOffset;
1222   }
1223 }
1224
1225 template <class ELFT>
1226 unsigned MergeOutputSection<ELFT>::getOffset(StringRef Val) {
1227   return Builder.getOffset(Val);
1228 }
1229
1230 template <class ELFT> bool MergeOutputSection<ELFT>::shouldTailMerge() const {
1231   return Config->Optimize >= 2 && this->Header.sh_flags & SHF_STRINGS;
1232 }
1233
1234 template <class ELFT> void MergeOutputSection<ELFT>::finalize() {
1235   if (shouldTailMerge())
1236     Builder.finalize();
1237   this->Header.sh_size = Builder.getSize();
1238 }
1239
1240 template <class ELFT> void MergeOutputSection<ELFT>::finalizePieces() {
1241   for (MergeInputSection<ELFT> *Sec : Sections)
1242     Sec->finalizePieces();
1243 }
1244
1245 template <class ELFT>
1246 StringTableSection<ELFT>::StringTableSection(StringRef Name, bool Dynamic)
1247     : OutputSectionBase<ELFT>(Name, SHT_STRTAB,
1248                               Dynamic ? (uintX_t)SHF_ALLOC : 0),
1249       Dynamic(Dynamic) {}
1250
1251 // Adds a string to the string table. If HashIt is true we hash and check for
1252 // duplicates. It is optional because the name of global symbols are already
1253 // uniqued and hashing them again has a big cost for a small value: uniquing
1254 // them with some other string that happens to be the same.
1255 template <class ELFT>
1256 unsigned StringTableSection<ELFT>::addString(StringRef S, bool HashIt) {
1257   if (HashIt) {
1258     auto R = StringMap.insert(std::make_pair(S, Size));
1259     if (!R.second)
1260       return R.first->second;
1261   }
1262   unsigned Ret = Size;
1263   Size += S.size() + 1;
1264   Strings.push_back(S);
1265   return Ret;
1266 }
1267
1268 template <class ELFT> void StringTableSection<ELFT>::writeTo(uint8_t *Buf) {
1269   // ELF string tables start with NUL byte, so advance the pointer by one.
1270   ++Buf;
1271   for (StringRef S : Strings) {
1272     memcpy(Buf, S.data(), S.size());
1273     Buf += S.size() + 1;
1274   }
1275 }
1276
1277 template <class ELFT>
1278 typename ELFT::uint DynamicReloc<ELFT>::getOffset() const {
1279   if (OutputSec)
1280     return OutputSec->getVA() + OffsetInSec;
1281   return InputSec->OutSec->getVA() + InputSec->getOffset(OffsetInSec);
1282 }
1283
1284 template <class ELFT>
1285 typename ELFT::uint DynamicReloc<ELFT>::getAddend() const {
1286   if (UseSymVA)
1287     return Sym->getVA<ELFT>(Addend);
1288   return Addend;
1289 }
1290
1291 template <class ELFT> uint32_t DynamicReloc<ELFT>::getSymIndex() const {
1292   if (Sym && !UseSymVA)
1293     return Sym->DynsymIndex;
1294   return 0;
1295 }
1296
1297 template <class ELFT>
1298 SymbolTableSection<ELFT>::SymbolTableSection(
1299     StringTableSection<ELFT> &StrTabSec)
1300     : OutputSectionBase<ELFT>(StrTabSec.isDynamic() ? ".dynsym" : ".symtab",
1301                               StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
1302                               StrTabSec.isDynamic() ? (uintX_t)SHF_ALLOC : 0),
1303       StrTabSec(StrTabSec) {
1304   this->Header.sh_entsize = sizeof(Elf_Sym);
1305   this->Header.sh_addralign = sizeof(uintX_t);
1306 }
1307
1308 // Orders symbols according to their positions in the GOT,
1309 // in compliance with MIPS ABI rules.
1310 // See "Global Offset Table" in Chapter 5 in the following document
1311 // for detailed description:
1312 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1313 static bool sortMipsSymbols(const std::pair<SymbolBody *, unsigned> &L,
1314                             const std::pair<SymbolBody *, unsigned> &R) {
1315   // Sort entries related to non-local preemptible symbols by GOT indexes.
1316   // All other entries go to the first part of GOT in arbitrary order.
1317   bool LIsInLocalGot = !L.first->IsInGlobalMipsGot;
1318   bool RIsInLocalGot = !R.first->IsInGlobalMipsGot;
1319   if (LIsInLocalGot || RIsInLocalGot)
1320     return !RIsInLocalGot;
1321   return L.first->GotIndex < R.first->GotIndex;
1322 }
1323
1324 static uint8_t getSymbolBinding(SymbolBody *Body) {
1325   Symbol *S = Body->symbol();
1326   uint8_t Visibility = S->Visibility;
1327   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
1328     return STB_LOCAL;
1329   if (Config->NoGnuUnique && S->Binding == STB_GNU_UNIQUE)
1330     return STB_GLOBAL;
1331   return S->Binding;
1332 }
1333
1334 template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
1335   if (this->Header.sh_size)
1336     return; // Already finalized.
1337
1338   this->Header.sh_size = getNumSymbols() * sizeof(Elf_Sym);
1339   this->Header.sh_link = StrTabSec.SectionIndex;
1340   this->Header.sh_info = NumLocals + 1;
1341
1342   if (Config->Relocatable) {
1343     size_t I = NumLocals;
1344     for (const std::pair<SymbolBody *, size_t> &P : Symbols)
1345       P.first->DynsymIndex = ++I;
1346     return;
1347   }
1348
1349   if (!StrTabSec.isDynamic()) {
1350     std::stable_sort(Symbols.begin(), Symbols.end(),
1351                      [](const std::pair<SymbolBody *, unsigned> &L,
1352                         const std::pair<SymbolBody *, unsigned> &R) {
1353                        return getSymbolBinding(L.first) == STB_LOCAL &&
1354                               getSymbolBinding(R.first) != STB_LOCAL;
1355                      });
1356     return;
1357   }
1358   if (Out<ELFT>::GnuHashTab)
1359     // NB: It also sorts Symbols to meet the GNU hash table requirements.
1360     Out<ELFT>::GnuHashTab->addSymbols(Symbols);
1361   else if (Config->EMachine == EM_MIPS)
1362     std::stable_sort(Symbols.begin(), Symbols.end(), sortMipsSymbols);
1363   size_t I = 0;
1364   for (const std::pair<SymbolBody *, size_t> &P : Symbols)
1365     P.first->DynsymIndex = ++I;
1366 }
1367
1368 template <class ELFT>
1369 void SymbolTableSection<ELFT>::addSymbol(SymbolBody *B) {
1370   Symbols.push_back({B, StrTabSec.addString(B->getName(), false)});
1371 }
1372
1373 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
1374   Buf += sizeof(Elf_Sym);
1375
1376   // All symbols with STB_LOCAL binding precede the weak and global symbols.
1377   // .dynsym only contains global symbols.
1378   if (!Config->DiscardAll && !StrTabSec.isDynamic())
1379     writeLocalSymbols(Buf);
1380
1381   writeGlobalSymbols(Buf);
1382 }
1383
1384 template <class ELFT>
1385 void SymbolTableSection<ELFT>::writeLocalSymbols(uint8_t *&Buf) {
1386   // Iterate over all input object files to copy their local symbols
1387   // to the output symbol table pointed by Buf.
1388   for (const std::unique_ptr<ObjectFile<ELFT>> &File :
1389        Symtab<ELFT>::X->getObjectFiles()) {
1390     for (const std::pair<const DefinedRegular<ELFT> *, size_t> &P :
1391          File->KeptLocalSyms) {
1392       const DefinedRegular<ELFT> &Body = *P.first;
1393       InputSectionBase<ELFT> *Section = Body.Section;
1394       auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
1395
1396       if (!Section) {
1397         ESym->st_shndx = SHN_ABS;
1398         ESym->st_value = Body.Value;
1399       } else {
1400         const OutputSectionBase<ELFT> *OutSec = Section->OutSec;
1401         ESym->st_shndx = OutSec->SectionIndex;
1402         ESym->st_value = OutSec->getVA() + Section->getOffset(Body);
1403       }
1404       ESym->st_name = P.second;
1405       ESym->st_size = Body.template getSize<ELFT>();
1406       ESym->setBindingAndType(STB_LOCAL, Body.Type);
1407       Buf += sizeof(*ESym);
1408     }
1409   }
1410 }
1411
1412 template <class ELFT>
1413 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
1414   // Write the internal symbol table contents to the output symbol table
1415   // pointed by Buf.
1416   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
1417   for (const std::pair<SymbolBody *, size_t> &P : Symbols) {
1418     SymbolBody *Body = P.first;
1419     size_t StrOff = P.second;
1420
1421     uint8_t Type = Body->Type;
1422     uintX_t Size = Body->getSize<ELFT>();
1423
1424     ESym->setBindingAndType(getSymbolBinding(Body), Type);
1425     ESym->st_size = Size;
1426     ESym->st_name = StrOff;
1427     ESym->setVisibility(Body->symbol()->Visibility);
1428     ESym->st_value = Body->getVA<ELFT>();
1429
1430     if (const OutputSectionBase<ELFT> *OutSec = getOutputSection(Body))
1431       ESym->st_shndx = OutSec->SectionIndex;
1432     else if (isa<DefinedRegular<ELFT>>(Body))
1433       ESym->st_shndx = SHN_ABS;
1434
1435     // On MIPS we need to mark symbol which has a PLT entry and requires pointer
1436     // equality by STO_MIPS_PLT flag. That is necessary to help dynamic linker
1437     // distinguish such symbols and MIPS lazy-binding stubs.
1438     // https://sourceware.org/ml/binutils/2008-07/txt00000.txt
1439     if (Config->EMachine == EM_MIPS && Body->isInPlt() &&
1440         Body->NeedsCopyOrPltAddr)
1441       ESym->st_other |= STO_MIPS_PLT;
1442     ++ESym;
1443   }
1444 }
1445
1446 template <class ELFT>
1447 const OutputSectionBase<ELFT> *
1448 SymbolTableSection<ELFT>::getOutputSection(SymbolBody *Sym) {
1449   switch (Sym->kind()) {
1450   case SymbolBody::DefinedSyntheticKind:
1451     return cast<DefinedSynthetic<ELFT>>(Sym)->Section;
1452   case SymbolBody::DefinedRegularKind: {
1453     auto &D = cast<DefinedRegular<ELFT>>(*Sym);
1454     if (D.Section)
1455       return D.Section->OutSec;
1456     break;
1457   }
1458   case SymbolBody::DefinedCommonKind:
1459     return Out<ELFT>::Bss;
1460   case SymbolBody::SharedKind:
1461     if (cast<SharedSymbol<ELFT>>(Sym)->needsCopy())
1462       return Out<ELFT>::Bss;
1463     break;
1464   case SymbolBody::UndefinedKind:
1465   case SymbolBody::LazyArchiveKind:
1466   case SymbolBody::LazyObjectKind:
1467     break;
1468   case SymbolBody::DefinedBitcodeKind:
1469     llvm_unreachable("should have been replaced");
1470   }
1471   return nullptr;
1472 }
1473
1474 template <class ELFT>
1475 VersionDefinitionSection<ELFT>::VersionDefinitionSection()
1476     : OutputSectionBase<ELFT>(".gnu.version_d", SHT_GNU_verdef, SHF_ALLOC) {
1477   this->Header.sh_addralign = sizeof(uint32_t);
1478 }
1479
1480 static StringRef getFileDefName() {
1481   if (!Config->SoName.empty())
1482     return Config->SoName;
1483   return Config->OutputFile;
1484 }
1485
1486 template <class ELFT> void VersionDefinitionSection<ELFT>::finalize() {
1487   FileDefNameOff = Out<ELFT>::DynStrTab->addString(getFileDefName());
1488   for (VersionDefinition &V : Config->VersionDefinitions)
1489     V.NameOff = Out<ELFT>::DynStrTab->addString(V.Name);
1490
1491   this->Header.sh_size =
1492       (sizeof(Elf_Verdef) + sizeof(Elf_Verdaux)) * getVerDefNum();
1493   this->Header.sh_link = Out<ELFT>::DynStrTab->SectionIndex;
1494
1495   // sh_info should be set to the number of definitions. This fact is missed in
1496   // documentation, but confirmed by binutils community:
1497   // https://sourceware.org/ml/binutils/2014-11/msg00355.html
1498   this->Header.sh_info = getVerDefNum();
1499 }
1500
1501 template <class ELFT>
1502 void VersionDefinitionSection<ELFT>::writeOne(uint8_t *Buf, uint32_t Index,
1503                                               StringRef Name, size_t NameOff) {
1504   auto *Verdef = reinterpret_cast<Elf_Verdef *>(Buf);
1505   Verdef->vd_version = 1;
1506   Verdef->vd_cnt = 1;
1507   Verdef->vd_aux = sizeof(Elf_Verdef);
1508   Verdef->vd_next = sizeof(Elf_Verdef) + sizeof(Elf_Verdaux);
1509   Verdef->vd_flags = (Index == 1 ? VER_FLG_BASE : 0);
1510   Verdef->vd_ndx = Index;
1511   Verdef->vd_hash = hashSysv(Name);
1512
1513   auto *Verdaux = reinterpret_cast<Elf_Verdaux *>(Buf + sizeof(Elf_Verdef));
1514   Verdaux->vda_name = NameOff;
1515   Verdaux->vda_next = 0;
1516 }
1517
1518 template <class ELFT>
1519 void VersionDefinitionSection<ELFT>::writeTo(uint8_t *Buf) {
1520   writeOne(Buf, 1, getFileDefName(), FileDefNameOff);
1521
1522   for (VersionDefinition &V : Config->VersionDefinitions) {
1523     Buf += sizeof(Elf_Verdef) + sizeof(Elf_Verdaux);
1524     writeOne(Buf, V.Id, V.Name, V.NameOff);
1525   }
1526
1527   // Need to terminate the last version definition.
1528   Elf_Verdef *Verdef = reinterpret_cast<Elf_Verdef *>(Buf);
1529   Verdef->vd_next = 0;
1530 }
1531
1532 template <class ELFT>
1533 VersionTableSection<ELFT>::VersionTableSection()
1534     : OutputSectionBase<ELFT>(".gnu.version", SHT_GNU_versym, SHF_ALLOC) {
1535   this->Header.sh_addralign = sizeof(uint16_t);
1536 }
1537
1538 template <class ELFT> void VersionTableSection<ELFT>::finalize() {
1539   this->Header.sh_size =
1540       sizeof(Elf_Versym) * (Out<ELFT>::DynSymTab->getSymbols().size() + 1);
1541   this->Header.sh_entsize = sizeof(Elf_Versym);
1542   // At the moment of june 2016 GNU docs does not mention that sh_link field
1543   // should be set, but Sun docs do. Also readelf relies on this field.
1544   this->Header.sh_link = Out<ELFT>::DynSymTab->SectionIndex;
1545 }
1546
1547 template <class ELFT> void VersionTableSection<ELFT>::writeTo(uint8_t *Buf) {
1548   auto *OutVersym = reinterpret_cast<Elf_Versym *>(Buf) + 1;
1549   for (const std::pair<SymbolBody *, size_t> &P :
1550        Out<ELFT>::DynSymTab->getSymbols()) {
1551     OutVersym->vs_index = P.first->symbol()->VersionId;
1552     ++OutVersym;
1553   }
1554 }
1555
1556 template <class ELFT>
1557 VersionNeedSection<ELFT>::VersionNeedSection()
1558     : OutputSectionBase<ELFT>(".gnu.version_r", SHT_GNU_verneed, SHF_ALLOC) {
1559   this->Header.sh_addralign = sizeof(uint32_t);
1560
1561   // Identifiers in verneed section start at 2 because 0 and 1 are reserved
1562   // for VER_NDX_LOCAL and VER_NDX_GLOBAL.
1563   // First identifiers are reserved by verdef section if it exist.
1564   NextIndex = getVerDefNum() + 1;
1565 }
1566
1567 template <class ELFT>
1568 void VersionNeedSection<ELFT>::addSymbol(SharedSymbol<ELFT> *SS) {
1569   if (!SS->Verdef) {
1570     SS->symbol()->VersionId = VER_NDX_GLOBAL;
1571     return;
1572   }
1573   SharedFile<ELFT> *F = SS->file();
1574   // If we don't already know that we need an Elf_Verneed for this DSO, prepare
1575   // to create one by adding it to our needed list and creating a dynstr entry
1576   // for the soname.
1577   if (F->VerdefMap.empty())
1578     Needed.push_back({F, Out<ELFT>::DynStrTab->addString(F->getSoName())});
1579   typename SharedFile<ELFT>::NeededVer &NV = F->VerdefMap[SS->Verdef];
1580   // If we don't already know that we need an Elf_Vernaux for this Elf_Verdef,
1581   // prepare to create one by allocating a version identifier and creating a
1582   // dynstr entry for the version name.
1583   if (NV.Index == 0) {
1584     NV.StrTab = Out<ELFT>::DynStrTab->addString(
1585         SS->file()->getStringTable().data() + SS->Verdef->getAux()->vda_name);
1586     NV.Index = NextIndex++;
1587   }
1588   SS->symbol()->VersionId = NV.Index;
1589 }
1590
1591 template <class ELFT> void VersionNeedSection<ELFT>::writeTo(uint8_t *Buf) {
1592   // The Elf_Verneeds need to appear first, followed by the Elf_Vernauxs.
1593   auto *Verneed = reinterpret_cast<Elf_Verneed *>(Buf);
1594   auto *Vernaux = reinterpret_cast<Elf_Vernaux *>(Verneed + Needed.size());
1595
1596   for (std::pair<SharedFile<ELFT> *, size_t> &P : Needed) {
1597     // Create an Elf_Verneed for this DSO.
1598     Verneed->vn_version = 1;
1599     Verneed->vn_cnt = P.first->VerdefMap.size();
1600     Verneed->vn_file = P.second;
1601     Verneed->vn_aux =
1602         reinterpret_cast<char *>(Vernaux) - reinterpret_cast<char *>(Verneed);
1603     Verneed->vn_next = sizeof(Elf_Verneed);
1604     ++Verneed;
1605
1606     // Create the Elf_Vernauxs for this Elf_Verneed. The loop iterates over
1607     // VerdefMap, which will only contain references to needed version
1608     // definitions. Each Elf_Vernaux is based on the information contained in
1609     // the Elf_Verdef in the source DSO. This loop iterates over a std::map of
1610     // pointers, but is deterministic because the pointers refer to Elf_Verdef
1611     // data structures within a single input file.
1612     for (auto &NV : P.first->VerdefMap) {
1613       Vernaux->vna_hash = NV.first->vd_hash;
1614       Vernaux->vna_flags = 0;
1615       Vernaux->vna_other = NV.second.Index;
1616       Vernaux->vna_name = NV.second.StrTab;
1617       Vernaux->vna_next = sizeof(Elf_Vernaux);
1618       ++Vernaux;
1619     }
1620
1621     Vernaux[-1].vna_next = 0;
1622   }
1623   Verneed[-1].vn_next = 0;
1624 }
1625
1626 template <class ELFT> void VersionNeedSection<ELFT>::finalize() {
1627   this->Header.sh_link = Out<ELFT>::DynStrTab->SectionIndex;
1628   this->Header.sh_info = Needed.size();
1629   unsigned Size = Needed.size() * sizeof(Elf_Verneed);
1630   for (std::pair<SharedFile<ELFT> *, size_t> &P : Needed)
1631     Size += P.first->VerdefMap.size() * sizeof(Elf_Vernaux);
1632   this->Header.sh_size = Size;
1633 }
1634
1635 template <class ELFT>
1636 BuildIdSection<ELFT>::BuildIdSection(size_t HashSize)
1637     : OutputSectionBase<ELFT>(".note.gnu.build-id", SHT_NOTE, SHF_ALLOC),
1638       HashSize(HashSize) {
1639   // 16 bytes for the note section header.
1640   this->Header.sh_size = 16 + HashSize;
1641 }
1642
1643 template <class ELFT> void BuildIdSection<ELFT>::writeTo(uint8_t *Buf) {
1644   const endianness E = ELFT::TargetEndianness;
1645   write32<E>(Buf, 4);                   // Name size
1646   write32<E>(Buf + 4, HashSize);        // Content size
1647   write32<E>(Buf + 8, NT_GNU_BUILD_ID); // Type
1648   memcpy(Buf + 12, "GNU", 4);           // Name string
1649   HashBuf = Buf + 16;
1650 }
1651
1652 template <class ELFT>
1653 void BuildIdFnv1<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
1654   const endianness E = ELFT::TargetEndianness;
1655
1656   // 64-bit FNV-1 hash
1657   uint64_t Hash = 0xcbf29ce484222325;
1658   for (ArrayRef<uint8_t> Buf : Bufs) {
1659     for (uint8_t B : Buf) {
1660       Hash *= 0x100000001b3;
1661       Hash ^= B;
1662     }
1663   }
1664   write64<E>(this->HashBuf, Hash);
1665 }
1666
1667 template <class ELFT>
1668 void BuildIdMd5<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
1669   MD5 Hash;
1670   for (ArrayRef<uint8_t> Buf : Bufs)
1671     Hash.update(Buf);
1672   MD5::MD5Result Res;
1673   Hash.final(Res);
1674   memcpy(this->HashBuf, Res, 16);
1675 }
1676
1677 template <class ELFT>
1678 void BuildIdSha1<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
1679   SHA1 Hash;
1680   for (ArrayRef<uint8_t> Buf : Bufs)
1681     Hash.update(Buf);
1682   memcpy(this->HashBuf, Hash.final().data(), 20);
1683 }
1684
1685 template <class ELFT>
1686 BuildIdHexstring<ELFT>::BuildIdHexstring()
1687     : BuildIdSection<ELFT>(Config->BuildIdVector.size()) {}
1688
1689 template <class ELFT>
1690 void BuildIdHexstring<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
1691   memcpy(this->HashBuf, Config->BuildIdVector.data(),
1692          Config->BuildIdVector.size());
1693 }
1694
1695 template <class ELFT>
1696 MipsReginfoOutputSection<ELFT>::MipsReginfoOutputSection()
1697     : OutputSectionBase<ELFT>(".reginfo", SHT_MIPS_REGINFO, SHF_ALLOC) {
1698   this->Header.sh_addralign = 4;
1699   this->Header.sh_entsize = sizeof(Elf_Mips_RegInfo);
1700   this->Header.sh_size = sizeof(Elf_Mips_RegInfo);
1701 }
1702
1703 template <class ELFT>
1704 void MipsReginfoOutputSection<ELFT>::writeTo(uint8_t *Buf) {
1705   auto *R = reinterpret_cast<Elf_Mips_RegInfo *>(Buf);
1706   R->ri_gp_value = Out<ELFT>::Got->getVA() + MipsGPOffset;
1707   R->ri_gprmask = GprMask;
1708 }
1709
1710 template <class ELFT>
1711 void MipsReginfoOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
1712   // Copy input object file's .reginfo gprmask to output.
1713   auto *S = cast<MipsReginfoInputSection<ELFT>>(C);
1714   GprMask |= S->Reginfo->ri_gprmask;
1715   S->OutSec = this;
1716 }
1717
1718 template <class ELFT>
1719 MipsOptionsOutputSection<ELFT>::MipsOptionsOutputSection()
1720     : OutputSectionBase<ELFT>(".MIPS.options", SHT_MIPS_OPTIONS,
1721                               SHF_ALLOC | SHF_MIPS_NOSTRIP) {
1722   this->Header.sh_addralign = 8;
1723   this->Header.sh_entsize = 1;
1724   this->Header.sh_size = sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);
1725 }
1726
1727 template <class ELFT>
1728 void MipsOptionsOutputSection<ELFT>::writeTo(uint8_t *Buf) {
1729   auto *Opt = reinterpret_cast<Elf_Mips_Options *>(Buf);
1730   Opt->kind = ODK_REGINFO;
1731   Opt->size = this->Header.sh_size;
1732   Opt->section = 0;
1733   Opt->info = 0;
1734   auto *Reg = reinterpret_cast<Elf_Mips_RegInfo *>(Buf + sizeof(*Opt));
1735   Reg->ri_gp_value = Out<ELFT>::Got->getVA() + MipsGPOffset;
1736   Reg->ri_gprmask = GprMask;
1737 }
1738
1739 template <class ELFT>
1740 void MipsOptionsOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
1741   auto *S = cast<MipsOptionsInputSection<ELFT>>(C);
1742   if (S->Reginfo)
1743     GprMask |= S->Reginfo->ri_gprmask;
1744   S->OutSec = this;
1745 }
1746
1747 template <class ELFT>
1748 std::pair<OutputSectionBase<ELFT> *, bool>
1749 OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
1750                                    StringRef OutsecName) {
1751   SectionKey<ELFT::Is64Bits> Key = createKey(C, OutsecName);
1752   OutputSectionBase<ELFT> *&Sec = Map[Key];
1753   if (Sec)
1754     return {Sec, false};
1755
1756   switch (C->SectionKind) {
1757   case InputSectionBase<ELFT>::Regular:
1758     Sec = new OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
1759     break;
1760   case InputSectionBase<ELFT>::EHFrame:
1761     return {Out<ELFT>::EhFrame, false};
1762   case InputSectionBase<ELFT>::Merge:
1763     Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
1764                                        Key.Alignment);
1765     break;
1766   case InputSectionBase<ELFT>::MipsReginfo:
1767     Sec = new MipsReginfoOutputSection<ELFT>();
1768     break;
1769   case InputSectionBase<ELFT>::MipsOptions:
1770     Sec = new MipsOptionsOutputSection<ELFT>();
1771     break;
1772   }
1773   return {Sec, true};
1774 }
1775
1776 template <class ELFT>
1777 OutputSectionBase<ELFT> *OutputSectionFactory<ELFT>::lookup(StringRef Name,
1778                                                             uint32_t Type,
1779                                                             uintX_t Flags) {
1780   return Map.lookup({Name, Type, Flags, 0});
1781 }
1782
1783 template <class ELFT>
1784 SectionKey<ELFT::Is64Bits>
1785 OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
1786                                       StringRef OutsecName) {
1787   const Elf_Shdr *H = C->getSectionHdr();
1788   uintX_t Flags = H->sh_flags & ~SHF_GROUP & ~SHF_COMPRESSED;
1789
1790   // For SHF_MERGE we create different output sections for each alignment.
1791   // This makes each output section simple and keeps a single level mapping from
1792   // input to output.
1793   uintX_t Alignment = 0;
1794   if (isa<MergeInputSection<ELFT>>(C))
1795     Alignment = std::max(H->sh_addralign, H->sh_entsize);
1796
1797   uint32_t Type = H->sh_type;
1798   return SectionKey<ELFT::Is64Bits>{OutsecName, Type, Flags, Alignment};
1799 }
1800
1801 template <bool Is64Bits>
1802 typename lld::elf::SectionKey<Is64Bits>
1803 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getEmptyKey() {
1804   return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getEmptyKey(), 0, 0, 0};
1805 }
1806
1807 template <bool Is64Bits>
1808 typename lld::elf::SectionKey<Is64Bits>
1809 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getTombstoneKey() {
1810   return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getTombstoneKey(), 0, 0,
1811                               0};
1812 }
1813
1814 template <bool Is64Bits>
1815 unsigned
1816 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getHashValue(const Key &Val) {
1817   return hash_combine(Val.Name, Val.Type, Val.Flags, Val.Alignment);
1818 }
1819
1820 template <bool Is64Bits>
1821 bool DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::isEqual(const Key &LHS,
1822                                                            const Key &RHS) {
1823   return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
1824          LHS.Type == RHS.Type && LHS.Flags == RHS.Flags &&
1825          LHS.Alignment == RHS.Alignment;
1826 }
1827
1828 namespace llvm {
1829 template struct DenseMapInfo<SectionKey<true>>;
1830 template struct DenseMapInfo<SectionKey<false>>;
1831 }
1832
1833 namespace lld {
1834 namespace elf {
1835 template class OutputSectionBase<ELF32LE>;
1836 template class OutputSectionBase<ELF32BE>;
1837 template class OutputSectionBase<ELF64LE>;
1838 template class OutputSectionBase<ELF64BE>;
1839
1840 template class EhFrameHeader<ELF32LE>;
1841 template class EhFrameHeader<ELF32BE>;
1842 template class EhFrameHeader<ELF64LE>;
1843 template class EhFrameHeader<ELF64BE>;
1844
1845 template class GotPltSection<ELF32LE>;
1846 template class GotPltSection<ELF32BE>;
1847 template class GotPltSection<ELF64LE>;
1848 template class GotPltSection<ELF64BE>;
1849
1850 template class GotSection<ELF32LE>;
1851 template class GotSection<ELF32BE>;
1852 template class GotSection<ELF64LE>;
1853 template class GotSection<ELF64BE>;
1854
1855 template class PltSection<ELF32LE>;
1856 template class PltSection<ELF32BE>;
1857 template class PltSection<ELF64LE>;
1858 template class PltSection<ELF64BE>;
1859
1860 template class RelocationSection<ELF32LE>;
1861 template class RelocationSection<ELF32BE>;
1862 template class RelocationSection<ELF64LE>;
1863 template class RelocationSection<ELF64BE>;
1864
1865 template class InterpSection<ELF32LE>;
1866 template class InterpSection<ELF32BE>;
1867 template class InterpSection<ELF64LE>;
1868 template class InterpSection<ELF64BE>;
1869
1870 template class GnuHashTableSection<ELF32LE>;
1871 template class GnuHashTableSection<ELF32BE>;
1872 template class GnuHashTableSection<ELF64LE>;
1873 template class GnuHashTableSection<ELF64BE>;
1874
1875 template class HashTableSection<ELF32LE>;
1876 template class HashTableSection<ELF32BE>;
1877 template class HashTableSection<ELF64LE>;
1878 template class HashTableSection<ELF64BE>;
1879
1880 template class DynamicSection<ELF32LE>;
1881 template class DynamicSection<ELF32BE>;
1882 template class DynamicSection<ELF64LE>;
1883 template class DynamicSection<ELF64BE>;
1884
1885 template class OutputSection<ELF32LE>;
1886 template class OutputSection<ELF32BE>;
1887 template class OutputSection<ELF64LE>;
1888 template class OutputSection<ELF64BE>;
1889
1890 template class EhOutputSection<ELF32LE>;
1891 template class EhOutputSection<ELF32BE>;
1892 template class EhOutputSection<ELF64LE>;
1893 template class EhOutputSection<ELF64BE>;
1894
1895 template class MipsReginfoOutputSection<ELF32LE>;
1896 template class MipsReginfoOutputSection<ELF32BE>;
1897 template class MipsReginfoOutputSection<ELF64LE>;
1898 template class MipsReginfoOutputSection<ELF64BE>;
1899
1900 template class MipsOptionsOutputSection<ELF32LE>;
1901 template class MipsOptionsOutputSection<ELF32BE>;
1902 template class MipsOptionsOutputSection<ELF64LE>;
1903 template class MipsOptionsOutputSection<ELF64BE>;
1904
1905 template class MergeOutputSection<ELF32LE>;
1906 template class MergeOutputSection<ELF32BE>;
1907 template class MergeOutputSection<ELF64LE>;
1908 template class MergeOutputSection<ELF64BE>;
1909
1910 template class StringTableSection<ELF32LE>;
1911 template class StringTableSection<ELF32BE>;
1912 template class StringTableSection<ELF64LE>;
1913 template class StringTableSection<ELF64BE>;
1914
1915 template class SymbolTableSection<ELF32LE>;
1916 template class SymbolTableSection<ELF32BE>;
1917 template class SymbolTableSection<ELF64LE>;
1918 template class SymbolTableSection<ELF64BE>;
1919
1920 template class VersionTableSection<ELF32LE>;
1921 template class VersionTableSection<ELF32BE>;
1922 template class VersionTableSection<ELF64LE>;
1923 template class VersionTableSection<ELF64BE>;
1924
1925 template class VersionNeedSection<ELF32LE>;
1926 template class VersionNeedSection<ELF32BE>;
1927 template class VersionNeedSection<ELF64LE>;
1928 template class VersionNeedSection<ELF64BE>;
1929
1930 template class VersionDefinitionSection<ELF32LE>;
1931 template class VersionDefinitionSection<ELF32BE>;
1932 template class VersionDefinitionSection<ELF64LE>;
1933 template class VersionDefinitionSection<ELF64BE>;
1934
1935 template class BuildIdSection<ELF32LE>;
1936 template class BuildIdSection<ELF32BE>;
1937 template class BuildIdSection<ELF64LE>;
1938 template class BuildIdSection<ELF64BE>;
1939
1940 template class BuildIdFnv1<ELF32LE>;
1941 template class BuildIdFnv1<ELF32BE>;
1942 template class BuildIdFnv1<ELF64LE>;
1943 template class BuildIdFnv1<ELF64BE>;
1944
1945 template class BuildIdMd5<ELF32LE>;
1946 template class BuildIdMd5<ELF32BE>;
1947 template class BuildIdMd5<ELF64LE>;
1948 template class BuildIdMd5<ELF64BE>;
1949
1950 template class BuildIdSha1<ELF32LE>;
1951 template class BuildIdSha1<ELF32BE>;
1952 template class BuildIdSha1<ELF64LE>;
1953 template class BuildIdSha1<ELF64BE>;
1954
1955 template class BuildIdHexstring<ELF32LE>;
1956 template class BuildIdHexstring<ELF32BE>;
1957 template class BuildIdHexstring<ELF64LE>;
1958 template class BuildIdHexstring<ELF64BE>;
1959
1960 template class OutputSectionFactory<ELF32LE>;
1961 template class OutputSectionFactory<ELF32BE>;
1962 template class OutputSectionFactory<ELF64LE>;
1963 template class OutputSectionFactory<ELF64BE>;
1964 }
1965 }