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

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