brintos / llvm-project-archived public Read only

1//===- SyntheticSections.cpp ----------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains linker-synthesized sections. Currently,10// synthetic sections are created either output sections or input sections,11// but we are rewriting code so that all synthetic sections are created as12// input sections.13//14//===----------------------------------------------------------------------===//15 16#include "SyntheticSections.h"17#include "Config.h"18#include "DWARF.h"19#include "EhFrame.h"20#include "InputFiles.h"21#include "LinkerScript.h"22#include "OutputSections.h"23#include "SymbolTable.h"24#include "Symbols.h"25#include "Target.h"26#include "Thunks.h"27#include "Writer.h"28#include "lld/Common/Version.h"29#include "llvm/ADT/STLExtras.h"30#include "llvm/ADT/Sequence.h"31#include "llvm/ADT/SetOperations.h"32#include "llvm/ADT/StringExtras.h"33#include "llvm/BinaryFormat/Dwarf.h"34#include "llvm/BinaryFormat/ELF.h"35#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"36#include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"37#include "llvm/Support/DJB.h"38#include "llvm/Support/Endian.h"39#include "llvm/Support/LEB128.h"40#include "llvm/Support/Parallel.h"41#include "llvm/Support/TimeProfiler.h"42#include <cinttypes>43#include <cstdlib>44 45using namespace llvm;46using namespace llvm::dwarf;47using namespace llvm::ELF;48using namespace llvm::object;49using namespace llvm::support;50using namespace lld;51using namespace lld::elf;52 53using llvm::support::endian::read32le;54using llvm::support::endian::write32le;55using llvm::support::endian::write64le;56 57static uint64_t readUint(Ctx &ctx, uint8_t *buf) {58  return ctx.arg.is64 ? read64(ctx, buf) : read32(ctx, buf);59}60 61static void writeUint(Ctx &ctx, uint8_t *buf, uint64_t val) {62  if (ctx.arg.is64)63    write64(ctx, buf, val);64  else65    write32(ctx, buf, val);66}67 68// Returns an LLD version string.69static ArrayRef<uint8_t> getVersion(Ctx &ctx) {70  // Check LLD_VERSION first for ease of testing.71  // You can get consistent output by using the environment variable.72  // This is only for testing.73  StringRef s = getenv("LLD_VERSION");74  if (s.empty())75    s = ctx.saver.save(Twine("Linker: ") + getLLDVersion());76 77  // +1 to include the terminating '\0'.78  return {(const uint8_t *)s.data(), s.size() + 1};79}80 81// Creates a .comment section containing LLD version info.82// With this feature, you can identify LLD-generated binaries easily83// by "readelf --string-dump .comment <file>".84// The returned object is a mergeable string section.85MergeInputSection *elf::createCommentSection(Ctx &ctx) {86  auto *sec =87      make<MergeInputSection>(ctx, ".comment", SHT_PROGBITS,88                              SHF_MERGE | SHF_STRINGS, 1, getVersion(ctx));89  sec->splitIntoPieces();90  return sec;91}92 93// .MIPS.abiflags section.94template <class ELFT>95MipsAbiFlagsSection<ELFT>::MipsAbiFlagsSection(Ctx &ctx,96                                               Elf_Mips_ABIFlags flags)97    : SyntheticSection(ctx, ".MIPS.abiflags", SHT_MIPS_ABIFLAGS, SHF_ALLOC, 8),98      flags(flags) {99  this->entsize = sizeof(Elf_Mips_ABIFlags);100}101 102template <class ELFT> void MipsAbiFlagsSection<ELFT>::writeTo(uint8_t *buf) {103  memcpy(buf, &flags, sizeof(flags));104}105 106template <class ELFT>107std::unique_ptr<MipsAbiFlagsSection<ELFT>>108MipsAbiFlagsSection<ELFT>::create(Ctx &ctx) {109  Elf_Mips_ABIFlags flags = {};110  bool create = false;111 112  for (InputSectionBase *sec : ctx.inputSections) {113    if (sec->type != SHT_MIPS_ABIFLAGS)114      continue;115    sec->markDead();116    create = true;117 118    const size_t size = sec->content().size();119    // Older version of BFD (such as the default FreeBSD linker) concatenate120    // .MIPS.abiflags instead of merging. To allow for this case (or potential121    // zero padding) we ignore everything after the first Elf_Mips_ABIFlags122    if (size < sizeof(Elf_Mips_ABIFlags)) {123      Err(ctx) << sec->file << ": invalid size of .MIPS.abiflags section: got "124               << size << " instead of " << sizeof(Elf_Mips_ABIFlags);125      return nullptr;126    }127    auto *s =128        reinterpret_cast<const Elf_Mips_ABIFlags *>(sec->content().data());129    if (s->version != 0) {130      Err(ctx) << sec->file << ": unexpected .MIPS.abiflags version "131               << s->version;132      return nullptr;133    }134 135    // LLD checks ISA compatibility in calcMipsEFlags(). Here we just136    // select the highest number of ISA/Rev/Ext.137    flags.isa_level = std::max(flags.isa_level, s->isa_level);138    flags.isa_rev = std::max(flags.isa_rev, s->isa_rev);139    flags.isa_ext = std::max(flags.isa_ext, s->isa_ext);140    flags.gpr_size = std::max(flags.gpr_size, s->gpr_size);141    flags.cpr1_size = std::max(flags.cpr1_size, s->cpr1_size);142    flags.cpr2_size = std::max(flags.cpr2_size, s->cpr2_size);143    flags.ases |= s->ases;144    flags.flags1 |= s->flags1;145    flags.flags2 |= s->flags2;146    flags.fp_abi =147        elf::getMipsFpAbiFlag(ctx, sec->file, flags.fp_abi, s->fp_abi);148  };149 150  if (create)151    return std::make_unique<MipsAbiFlagsSection<ELFT>>(ctx, flags);152  return nullptr;153}154 155// .MIPS.options section.156template <class ELFT>157MipsOptionsSection<ELFT>::MipsOptionsSection(Ctx &ctx, Elf_Mips_RegInfo reginfo)158    : SyntheticSection(ctx, ".MIPS.options", SHT_MIPS_OPTIONS, SHF_ALLOC, 8),159      reginfo(reginfo) {160  this->entsize = sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);161}162 163template <class ELFT> void MipsOptionsSection<ELFT>::writeTo(uint8_t *buf) {164  auto *options = reinterpret_cast<Elf_Mips_Options *>(buf);165  options->kind = ODK_REGINFO;166  options->size = getSize();167 168  if (!ctx.arg.relocatable)169    reginfo.ri_gp_value = ctx.in.mipsGot->getGp();170  memcpy(buf + sizeof(Elf_Mips_Options), &reginfo, sizeof(reginfo));171}172 173template <class ELFT>174std::unique_ptr<MipsOptionsSection<ELFT>>175MipsOptionsSection<ELFT>::create(Ctx &ctx) {176  // N64 ABI only.177  if (!ELFT::Is64Bits)178    return nullptr;179 180  SmallVector<InputSectionBase *, 0> sections;181  for (InputSectionBase *sec : ctx.inputSections)182    if (sec->type == SHT_MIPS_OPTIONS)183      sections.push_back(sec);184 185  if (sections.empty())186    return nullptr;187 188  Elf_Mips_RegInfo reginfo = {};189  for (InputSectionBase *sec : sections) {190    sec->markDead();191 192    ArrayRef<uint8_t> d = sec->content();193    while (!d.empty()) {194      if (d.size() < sizeof(Elf_Mips_Options)) {195        Err(ctx) << sec->file << ": invalid size of .MIPS.options section";196        break;197      }198 199      auto *opt = reinterpret_cast<const Elf_Mips_Options *>(d.data());200      if (opt->kind == ODK_REGINFO) {201        reginfo.ri_gprmask |= opt->getRegInfo().ri_gprmask;202        sec->getFile<ELFT>()->mipsGp0 = opt->getRegInfo().ri_gp_value;203        break;204      }205 206      if (!opt->size) {207        Err(ctx) << sec->file << ": zero option descriptor size";208        break;209      }210      d = d.slice(opt->size);211    }212  };213 214  return std::make_unique<MipsOptionsSection<ELFT>>(ctx, reginfo);215}216 217// MIPS .reginfo section.218template <class ELFT>219MipsReginfoSection<ELFT>::MipsReginfoSection(Ctx &ctx, Elf_Mips_RegInfo reginfo)220    : SyntheticSection(ctx, ".reginfo", SHT_MIPS_REGINFO, SHF_ALLOC, 4),221      reginfo(reginfo) {222  this->entsize = sizeof(Elf_Mips_RegInfo);223}224 225template <class ELFT> void MipsReginfoSection<ELFT>::writeTo(uint8_t *buf) {226  if (!ctx.arg.relocatable)227    reginfo.ri_gp_value = ctx.in.mipsGot->getGp();228  memcpy(buf, &reginfo, sizeof(reginfo));229}230 231template <class ELFT>232std::unique_ptr<MipsReginfoSection<ELFT>>233MipsReginfoSection<ELFT>::create(Ctx &ctx) {234  // Section should be alive for O32 and N32 ABIs only.235  if (ELFT::Is64Bits)236    return nullptr;237 238  SmallVector<InputSectionBase *, 0> sections;239  for (InputSectionBase *sec : ctx.inputSections)240    if (sec->type == SHT_MIPS_REGINFO)241      sections.push_back(sec);242 243  if (sections.empty())244    return nullptr;245 246  Elf_Mips_RegInfo reginfo = {};247  for (InputSectionBase *sec : sections) {248    sec->markDead();249 250    if (sec->content().size() != sizeof(Elf_Mips_RegInfo)) {251      Err(ctx) << sec->file << ": invalid size of .reginfo section";252      return nullptr;253    }254 255    auto *r = reinterpret_cast<const Elf_Mips_RegInfo *>(sec->content().data());256    reginfo.ri_gprmask |= r->ri_gprmask;257    sec->getFile<ELFT>()->mipsGp0 = r->ri_gp_value;258  };259 260  return std::make_unique<MipsReginfoSection<ELFT>>(ctx, reginfo);261}262 263InputSection *elf::createInterpSection(Ctx &ctx) {264  // StringSaver guarantees that the returned string ends with '\0'.265  StringRef s = ctx.saver.save(ctx.arg.dynamicLinker);266  ArrayRef<uint8_t> contents = {(const uint8_t *)s.data(), s.size() + 1};267 268  return make<InputSection>(ctx.internalFile, ".interp", SHT_PROGBITS,269                            SHF_ALLOC,270                            /*addralign=*/1, /*entsize=*/0, contents);271}272 273Defined *elf::addSyntheticLocal(Ctx &ctx, StringRef name, uint8_t type,274                                uint64_t value, uint64_t size,275                                InputSectionBase &section) {276  Defined *s = makeDefined(ctx, section.file, name, STB_LOCAL, STV_DEFAULT,277                           type, value, size, &section);278  if (ctx.in.symTab)279    ctx.in.symTab->addSymbol(s);280 281  if (ctx.arg.emachine == EM_ARM && !ctx.arg.isLE && ctx.arg.armBe8 &&282      (section.flags & SHF_EXECINSTR))283    // Adding Linker generated mapping symbols to the arm specific mapping284    // symbols list.285    addArmSyntheticSectionMappingSymbol(s);286 287  return s;288}289 290static size_t getHashSize(Ctx &ctx) {291  switch (ctx.arg.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 ctx.arg.buildIdVector.size();301  default:302    llvm_unreachable("unknown BuildIdKind");303  }304}305 306// This class represents a linker-synthesized .note.gnu.property section.307//308// In x86 and AArch64, object files may contain feature flags indicating the309// features that they have used. The flags are stored in a .note.gnu.property310// section.311//312// lld reads the sections from input files and merges them by computing AND of313// the flags. The result is written as a new .note.gnu.property section.314//315// If the flag is zero (which indicates that the intersection of the feature316// sets is empty, or some input files didn't have .note.gnu.property sections),317// we don't create this section.318GnuPropertySection::GnuPropertySection(Ctx &ctx)319    : SyntheticSection(ctx, ".note.gnu.property", SHT_NOTE, SHF_ALLOC,320                       ctx.arg.wordsize) {}321 322void GnuPropertySection::writeTo(uint8_t *buf) {323  uint32_t featureAndType;324  switch (ctx.arg.emachine) {325  case EM_386:326  case EM_X86_64:327    featureAndType = GNU_PROPERTY_X86_FEATURE_1_AND;328    break;329  case EM_AARCH64:330    featureAndType = GNU_PROPERTY_AARCH64_FEATURE_1_AND;331    break;332  case EM_RISCV:333    featureAndType = GNU_PROPERTY_RISCV_FEATURE_1_AND;334    break;335  default:336    llvm_unreachable(337        "target machine does not support .note.gnu.property section");338  }339 340  write32(ctx, buf, 4);                          // Name size341  write32(ctx, buf + 4, getSize() - 16);         // Content size342  write32(ctx, buf + 8, NT_GNU_PROPERTY_TYPE_0); // Type343  memcpy(buf + 12, "GNU", 4);               // Name string344 345  unsigned offset = 16;346  if (ctx.arg.andFeatures != 0) {347    write32(ctx, buf + offset + 0, featureAndType);      // Feature type348    write32(ctx, buf + offset + 4, 4);                   // Feature size349    write32(ctx, buf + offset + 8, ctx.arg.andFeatures); // Feature flags350    if (ctx.arg.is64)351      write32(ctx, buf + offset + 12, 0); // Padding352    offset += 16;353  }354 355  if (ctx.aarch64PauthAbiCoreInfo) {356    write32(ctx, buf + offset + 0, GNU_PROPERTY_AARCH64_FEATURE_PAUTH);357    write32(ctx, buf + offset + 4, AArch64PauthAbiCoreInfo::size());358    write64(ctx, buf + offset + 8, ctx.aarch64PauthAbiCoreInfo->platform);359    write64(ctx, buf + offset + 16, ctx.aarch64PauthAbiCoreInfo->version);360  }361}362 363size_t GnuPropertySection::getSize() const {364  uint32_t contentSize = 0;365  if (ctx.arg.andFeatures != 0)366    contentSize += ctx.arg.is64 ? 16 : 12;367  if (ctx.aarch64PauthAbiCoreInfo)368    contentSize += 4 + 4 + AArch64PauthAbiCoreInfo::size();369  assert(contentSize != 0);370  return contentSize + 16;371}372 373BuildIdSection::BuildIdSection(Ctx &ctx)374    : SyntheticSection(ctx, ".note.gnu.build-id", SHT_NOTE, SHF_ALLOC, 4),375      hashSize(getHashSize(ctx)) {}376 377void BuildIdSection::writeTo(uint8_t *buf) {378  write32(ctx, buf, 4);                   // Name size379  write32(ctx, buf + 4, hashSize);        // Content size380  write32(ctx, buf + 8, NT_GNU_BUILD_ID); // Type381  memcpy(buf + 12, "GNU", 4);           // Name string382  hashBuf = buf + 16;383}384 385void BuildIdSection::writeBuildId(ArrayRef<uint8_t> buf) {386  assert(buf.size() == hashSize);387  memcpy(hashBuf, buf.data(), hashSize);388}389 390BssSection::BssSection(Ctx &ctx, StringRef name, uint64_t size,391                       uint32_t alignment)392    : SyntheticSection(ctx, name, SHT_NOBITS, SHF_ALLOC | SHF_WRITE,393                       alignment) {394  this->bss = true;395  this->size = size;396}397 398EhFrameSection::EhFrameSection(Ctx &ctx)399    : SyntheticSection(ctx, ".eh_frame", SHT_PROGBITS, SHF_ALLOC, 1) {}400 401// Search for an existing CIE record or create a new one.402// CIE records from input object files are uniquified by their contents403// and where their relocations point to.404CieRecord *EhFrameSection::addCie(EhSectionPiece &cie,405                                  ArrayRef<Relocation> rels) {406  Symbol *personality = nullptr;407  unsigned firstRelI = cie.firstRelocation;408  if (firstRelI != (unsigned)-1)409    personality = rels[firstRelI].sym;410 411  // Search for an existing CIE by CIE contents/relocation target pair.412  CieRecord *&rec = cieMap[{cie.data(), personality}];413 414  // If not found, create a new one.415  if (!rec) {416    rec = make<CieRecord>();417    rec->cie = &cie;418    cieRecords.push_back(rec);419  }420  return rec;421}422 423// There is one FDE per function. Returns a non-null pointer to the function424// symbol if the given FDE points to a live function.425Defined *EhFrameSection::isFdeLive(EhSectionPiece &fde,426                                   ArrayRef<Relocation> rels) {427  // An FDE should point to some function because FDEs are to describe428  // functions. That's however not always the case due to an issue of429  // ld.gold with -r. ld.gold may discard only functions and leave their430  // corresponding FDEs, which results in creating bad .eh_frame sections.431  // To deal with that, we ignore such FDEs.432  unsigned firstRelI = fde.firstRelocation;433  if (firstRelI == (unsigned)-1)434    return nullptr;435 436  // FDEs for garbage-collected or merged-by-ICF sections, or sections in437  // another partition, are dead.438  if (auto *d = dyn_cast<Defined>(rels[firstRelI].sym))439    if (!d->folded && d->section && d->section->partition == partition)440      return d;441  return nullptr;442}443 444// .eh_frame is a sequence of CIE or FDE records. In general, there445// is one CIE record per input object file which is followed by446// a list of FDEs. This function searches an existing CIE or create a new447// one and associates FDEs to the CIE.448template <endianness e> void EhFrameSection::addRecords(EhInputSection *sec) {449  auto rels = sec->rels;450  offsetToCie.clear();451  for (EhSectionPiece &cie : sec->cies)452    offsetToCie[cie.inputOff] = addCie(cie, rels);453  for (EhSectionPiece &fde : sec->fdes) {454    uint32_t id = endian::read32<e>(fde.data().data() + 4);455    CieRecord *rec = offsetToCie[fde.inputOff + 4 - id];456    if (!rec)457      Fatal(ctx) << sec << ": invalid CIE reference";458 459    if (!isFdeLive(fde, rels))460      continue;461    rec->fdes.push_back(&fde);462    numFdes++;463  }464}465 466// Used by ICF<ELFT>::handleLSDA(). This function is very similar to467// EhFrameSection::addRecords().468template <class ELFT>469void EhFrameSection::iterateFDEWithLSDAAux(470    EhInputSection &sec, DenseSet<size_t> &ciesWithLSDA,471    llvm::function_ref<void(InputSection &)> fn) {472  for (EhSectionPiece &cie : sec.cies)473    if (hasLSDA(cie))474      ciesWithLSDA.insert(cie.inputOff);475  for (EhSectionPiece &fde : sec.fdes) {476    uint32_t id = endian::read32<ELFT::Endianness>(fde.data().data() + 4);477    if (!ciesWithLSDA.contains(fde.inputOff + 4 - id))478      continue;479 480    // The CIE has a LSDA argument. Call fn with d's section.481    if (Defined *d = isFdeLive(fde, sec.rels))482      if (auto *s = dyn_cast_or_null<InputSection>(d->section))483        fn(*s);484  }485}486 487template <class ELFT>488void EhFrameSection::iterateFDEWithLSDA(489    llvm::function_ref<void(InputSection &)> fn) {490  DenseSet<size_t> ciesWithLSDA;491  for (EhInputSection *sec : sections) {492    ciesWithLSDA.clear();493    iterateFDEWithLSDAAux<ELFT>(*sec, ciesWithLSDA, fn);494  }495}496 497static void writeCieFde(Ctx &ctx, uint8_t *buf, ArrayRef<uint8_t> d) {498  memcpy(buf, d.data(), d.size());499  // Fix the size field. -4 since size does not include the size field itself.500  write32(ctx, buf, d.size() - 4);501}502 503void EhFrameSection::finalizeContents() {504  assert(!this->size); // Not finalized.505 506  switch (ctx.arg.ekind) {507  case ELFNoneKind:508    llvm_unreachable("invalid ekind");509  case ELF32LEKind:510  case ELF64LEKind:511    for (EhInputSection *sec : sections)512      if (sec->isLive())513        addRecords<endianness::little>(sec);514    break;515  case ELF32BEKind:516  case ELF64BEKind:517    for (EhInputSection *sec : sections)518      if (sec->isLive())519        addRecords<endianness::big>(sec);520    break;521  }522 523  size_t off = 0;524  for (CieRecord *rec : cieRecords) {525    rec->cie->outputOff = off;526    off += rec->cie->size;527 528    for (EhSectionPiece *fde : rec->fdes) {529      fde->outputOff = off;530      off += fde->size;531    }532  }533 534  // The LSB standard does not allow a .eh_frame section with zero535  // Call Frame Information records. glibc unwind-dw2-fde.c536  // classify_object_over_fdes expects there is a CIE record length 0 as a537  // terminator. Thus we add one unconditionally.538  off += 4;539 540  this->size = off;541}542 543static uint64_t readFdeAddr(Ctx &ctx, uint8_t *buf, int size) {544  switch (size) {545  case DW_EH_PE_udata2:546    return read16(ctx, buf);547  case DW_EH_PE_sdata2:548    return (int16_t)read16(ctx, buf);549  case DW_EH_PE_udata4:550    return read32(ctx, buf);551  case DW_EH_PE_sdata4:552    return (int32_t)read32(ctx, buf);553  case DW_EH_PE_udata8:554  case DW_EH_PE_sdata8:555    return read64(ctx, buf);556  case DW_EH_PE_absptr:557    return readUint(ctx, buf);558  }559  Err(ctx) << "unknown FDE size encoding";560  return 0;561}562 563// Returns the VA to which a given FDE (on a mmap'ed buffer) is applied to.564// We need it to create .eh_frame_hdr section.565uint64_t EhFrameSection::getFdePc(uint8_t *buf, size_t fdeOff,566                                  uint8_t enc) const {567  // The starting address to which this FDE applies is568  // stored at FDE + 8 byte. And this offset is within569  // the .eh_frame section.570  size_t off = fdeOff + 8;571  uint64_t addr = readFdeAddr(ctx, buf + off, enc & 0xf);572  if ((enc & 0x70) == DW_EH_PE_absptr)573    return ctx.arg.is64 ? addr : uint32_t(addr);574  if ((enc & 0x70) == DW_EH_PE_pcrel)575    return addr + getParent()->addr + off + outSecOff;576  Err(ctx) << "unknown FDE size relative encoding";577  return 0;578}579 580void EhFrameSection::writeTo(uint8_t *buf) {581  // Write CIE and FDE records.582  for (CieRecord *rec : cieRecords) {583    size_t cieOffset = rec->cie->outputOff;584    writeCieFde(ctx, buf + cieOffset, rec->cie->data());585 586    for (EhSectionPiece *fde : rec->fdes) {587      size_t off = fde->outputOff;588      writeCieFde(ctx, buf + off, fde->data());589 590      // FDE's second word should have the offset to an associated CIE.591      // Write it.592      write32(ctx, buf + off + 4, off + 4 - cieOffset);593    }594  }595 596  // Apply relocations to .eh_frame entries. This includes CIE personality597  // pointers, FDE initial_location fields, and LSDA pointers.598  for (EhInputSection *s : sections)599    ctx.target->relocateEh(*s, buf);600 601  EhFrameHeader *hdr = getPartition(ctx).ehFrameHdr.get();602  if (!hdr || !hdr->getParent())603    return;604 605  // Write the .eh_frame_hdr section, which contains a binary search table of606  // pointers to FDEs. This must be written after .eh_frame relocation since607  // the content depends on relocated initial_location fields in FDEs.608  using FdeData = EhFrameSection::FdeData;609  SmallVector<FdeData, 0> fdes;610  uint64_t va = hdr->getVA();611  for (CieRecord *rec : cieRecords) {612    uint8_t enc = getFdeEncoding(rec->cie);613    for (EhSectionPiece *fde : rec->fdes) {614      uint64_t pc = getFdePc(buf, fde->outputOff, enc);615      uint64_t fdeVA = getParent()->addr + fde->outputOff;616      if (!isInt<32>(pc - va)) {617        Err(ctx) << fde->sec << ": PC offset is too large: 0x"618                 << Twine::utohexstr(pc - va);619        continue;620      }621      fdes.push_back({uint32_t(pc - va), uint32_t(fdeVA - va)});622    }623  }624 625  // Sort the FDE list by their PC and uniqueify. Usually there is only626  // one FDE for a PC (i.e. function), but if ICF merges two functions627  // into one, there can be more than one FDEs pointing to the address.628  llvm::stable_sort(fdes, [](const FdeData &a, const FdeData &b) {629    return a.pcRel < b.pcRel;630  });631  fdes.erase(632      llvm::unique(fdes, [](auto &a, auto &b) { return a.pcRel == b.pcRel; }),633      fdes.end());634 635  // Write header.636  uint8_t *hdrBuf = ctx.bufferStart + hdr->getParent()->offset + hdr->outSecOff;637  hdrBuf[0] = 1;                                  // version638  hdrBuf[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;   // eh_frame_ptr_enc639  hdrBuf[2] = DW_EH_PE_udata4;                    // fde_count_enc640  hdrBuf[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4; // table_enc641  write32(ctx, hdrBuf + 4,642          getParent()->addr - hdr->getVA() - 4); // eh_frame_ptr643  write32(ctx, hdrBuf + 8, fdes.size());         // fde_count644  hdrBuf += 12;645 646  // Write binary search table. Each entry describes the starting PC and the FDE647  // address.648  for (FdeData &fde : fdes) {649    write32(ctx, hdrBuf, fde.pcRel);650    write32(ctx, hdrBuf + 4, fde.fdeVARel);651    hdrBuf += 8;652  }653}654 655EhFrameHeader::EhFrameHeader(Ctx &ctx)656    : SyntheticSection(ctx, ".eh_frame_hdr", SHT_PROGBITS, SHF_ALLOC, 4) {}657 658void EhFrameHeader::writeTo(uint8_t *buf) {659  // The section content is written during EhFrameSection::writeTo.660}661 662size_t EhFrameHeader::getSize() const {663  // .eh_frame_hdr has a 12 bytes header followed by an array of FDEs.664  return 12 + getPartition(ctx).ehFrame->numFdes * 8;665}666 667bool EhFrameHeader::isNeeded() const {668  return isLive() && getPartition(ctx).ehFrame->isNeeded();669}670 671GotSection::GotSection(Ctx &ctx)672    : SyntheticSection(ctx, ".got", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE,673                       ctx.target->gotEntrySize) {674  numEntries = ctx.target->gotHeaderEntriesNum;675}676 677void GotSection::addConstant(const Relocation &r) { relocations.push_back(r); }678void GotSection::addEntry(const Symbol &sym) {679  assert(sym.auxIdx == ctx.symAux.size() - 1);680  ctx.symAux.back().gotIdx = numEntries++;681}682 683void GotSection::addAuthEntry(const Symbol &sym) {684  authEntries.push_back(685      {(numEntries - 1) * ctx.target->gotEntrySize, sym.isFunc()});686}687 688bool GotSection::addTlsDescEntry(const Symbol &sym) {689  assert(sym.auxIdx == ctx.symAux.size() - 1);690  ctx.symAux.back().tlsDescIdx = numEntries;691  numEntries += 2;692  return true;693}694 695void GotSection::addTlsDescAuthEntry() {696  authEntries.push_back({(numEntries - 2) * ctx.target->gotEntrySize, true});697  authEntries.push_back({(numEntries - 1) * ctx.target->gotEntrySize, false});698}699 700bool GotSection::addDynTlsEntry(const Symbol &sym) {701  assert(sym.auxIdx == ctx.symAux.size() - 1);702  ctx.symAux.back().tlsGdIdx = numEntries;703  // Global Dynamic TLS entries take two GOT slots.704  numEntries += 2;705  return true;706}707 708// Reserves TLS entries for a TLS module ID and a TLS block offset.709// In total it takes two GOT slots.710bool GotSection::addTlsIndex() {711  if (tlsIndexOff != uint32_t(-1))712    return false;713  tlsIndexOff = numEntries * ctx.target->gotEntrySize;714  numEntries += 2;715  return true;716}717 718uint32_t GotSection::getTlsDescOffset(const Symbol &sym) const {719  return sym.getTlsDescIdx(ctx) * ctx.target->gotEntrySize;720}721 722uint64_t GotSection::getTlsDescAddr(const Symbol &sym) const {723  return getVA() + getTlsDescOffset(sym);724}725 726uint64_t GotSection::getGlobalDynAddr(const Symbol &b) const {727  return this->getVA() + b.getTlsGdIdx(ctx) * ctx.target->gotEntrySize;728}729 730uint64_t GotSection::getGlobalDynOffset(const Symbol &b) const {731  return b.getTlsGdIdx(ctx) * ctx.target->gotEntrySize;732}733 734void GotSection::finalizeContents() {735  if (ctx.arg.emachine == EM_PPC64 &&736      numEntries <= ctx.target->gotHeaderEntriesNum &&737      !ctx.sym.globalOffsetTable)738    size = 0;739  else740    size = numEntries * ctx.target->gotEntrySize;741}742 743bool GotSection::isNeeded() const {744  // Needed if the GOT symbol is used or the number of entries is more than just745  // the header. A GOT with just the header may not be needed.746  return hasGotOffRel || numEntries > ctx.target->gotHeaderEntriesNum;747}748 749void GotSection::writeTo(uint8_t *buf) {750  // On PPC64 .got may be needed but empty. Skip the write.751  if (size == 0)752    return;753  ctx.target->writeGotHeader(buf);754  ctx.target->relocateAlloc(*this, buf);755  for (const AuthEntryInfo &authEntry : authEntries) {756    // https://github.com/ARM-software/abi-aa/blob/2024Q3/pauthabielf64/pauthabielf64.rst#default-signing-schema757    //   Signed GOT entries use the IA key for symbols of type STT_FUNC and the758    //   DA key for all other symbol types, with the address of the GOT entry as759    //   the modifier. The static linker must encode the signing schema into the760    //   GOT slot.761    //762    // https://github.com/ARM-software/abi-aa/blob/2024Q3/pauthabielf64/pauthabielf64.rst#encoding-the-signing-schema763    //   If address diversity is set and the discriminator764    //   is 0 then modifier = Place765    uint8_t *dest = buf + authEntry.offset;766    uint64_t key = authEntry.isSymbolFunc ? /*IA=*/0b00 : /*DA=*/0b10;767    uint64_t addrDiversity = 1;768    write64(ctx, dest, (addrDiversity << 63) | (key << 60));769  }770}771 772static uint64_t getMipsPageCount(uint64_t size) {773  return (size + 0xfffe) / 0xffff + 1;774}775 776MipsGotSection::MipsGotSection(Ctx &ctx)777    : SyntheticSection(ctx, ".got", SHT_PROGBITS,778                       SHF_ALLOC | SHF_WRITE | SHF_MIPS_GPREL, 16) {}779 780void MipsGotSection::addEntry(InputFile &file, Symbol &sym, int64_t addend,781                              RelExpr expr) {782  FileGot &g = getGot(file);783  if (expr == RE_MIPS_GOT_LOCAL_PAGE) {784    if (const OutputSection *os = sym.getOutputSection())785      g.pagesMap.insert({os, {&sym}});786    else787      g.local16.insert({{nullptr, getMipsPageAddr(sym.getVA(ctx, addend))}, 0});788  } else if (sym.isTls())789    g.tls.insert({&sym, 0});790  else if (sym.isPreemptible && expr == R_ABS)791    g.relocs.insert({&sym, 0});792  else if (sym.isPreemptible)793    g.global.insert({&sym, 0});794  else if (expr == RE_MIPS_GOT_OFF32)795    g.local32.insert({{&sym, addend}, 0});796  else797    g.local16.insert({{&sym, addend}, 0});798}799 800void MipsGotSection::addDynTlsEntry(InputFile &file, Symbol &sym) {801  getGot(file).dynTlsSymbols.insert({&sym, 0});802}803 804void MipsGotSection::addTlsIndex(InputFile &file) {805  getGot(file).dynTlsSymbols.insert({nullptr, 0});806}807 808size_t MipsGotSection::FileGot::getEntriesNum() const {809  return getPageEntriesNum() + local16.size() + global.size() + relocs.size() +810         tls.size() + dynTlsSymbols.size() * 2;811}812 813size_t MipsGotSection::FileGot::getPageEntriesNum() const {814  size_t num = 0;815  for (const std::pair<const OutputSection *, FileGot::PageBlock> &p : pagesMap)816    num += p.second.count;817  return num;818}819 820size_t MipsGotSection::FileGot::getIndexedEntriesNum() const {821  size_t count = getPageEntriesNum() + local16.size() + global.size();822  // If there are relocation-only entries in the GOT, TLS entries823  // are allocated after them. TLS entries should be addressable824  // by 16-bit index so count both reloc-only and TLS entries.825  if (!tls.empty() || !dynTlsSymbols.empty())826    count += relocs.size() + tls.size() + dynTlsSymbols.size() * 2;827  return count;828}829 830MipsGotSection::FileGot &MipsGotSection::getGot(InputFile &f) {831  if (f.mipsGotIndex == uint32_t(-1)) {832    gots.emplace_back();833    gots.back().file = &f;834    f.mipsGotIndex = gots.size() - 1;835  }836  return gots[f.mipsGotIndex];837}838 839uint64_t MipsGotSection::getPageEntryOffset(const InputFile *f,840                                            const Symbol &sym,841                                            int64_t addend) const {842  const FileGot &g = gots[f->mipsGotIndex];843  uint64_t index = 0;844  if (const OutputSection *outSec = sym.getOutputSection()) {845    uint64_t secAddr = getMipsPageAddr(outSec->addr);846    uint64_t symAddr = getMipsPageAddr(sym.getVA(ctx, addend));847    index = g.pagesMap.lookup(outSec).firstIndex + (symAddr - secAddr) / 0xffff;848  } else {849    index =850        g.local16.lookup({nullptr, getMipsPageAddr(sym.getVA(ctx, addend))});851  }852  return index * ctx.arg.wordsize;853}854 855uint64_t MipsGotSection::getSymEntryOffset(const InputFile *f, const Symbol &s,856                                           int64_t addend) const {857  const FileGot &g = gots[f->mipsGotIndex];858  Symbol *sym = const_cast<Symbol *>(&s);859  if (sym->isTls())860    return g.tls.lookup(sym) * ctx.arg.wordsize;861  if (sym->isPreemptible)862    return g.global.lookup(sym) * ctx.arg.wordsize;863  return g.local16.lookup({sym, addend}) * ctx.arg.wordsize;864}865 866uint64_t MipsGotSection::getTlsIndexOffset(const InputFile *f) const {867  const FileGot &g = gots[f->mipsGotIndex];868  return g.dynTlsSymbols.lookup(nullptr) * ctx.arg.wordsize;869}870 871uint64_t MipsGotSection::getGlobalDynOffset(const InputFile *f,872                                            const Symbol &s) const {873  const FileGot &g = gots[f->mipsGotIndex];874  Symbol *sym = const_cast<Symbol *>(&s);875  return g.dynTlsSymbols.lookup(sym) * ctx.arg.wordsize;876}877 878const Symbol *MipsGotSection::getFirstGlobalEntry() const {879  if (gots.empty())880    return nullptr;881  const FileGot &primGot = gots.front();882  if (!primGot.global.empty())883    return primGot.global.front().first;884  if (!primGot.relocs.empty())885    return primGot.relocs.front().first;886  return nullptr;887}888 889unsigned MipsGotSection::getLocalEntriesNum() const {890  if (gots.empty())891    return headerEntriesNum;892  return headerEntriesNum + gots.front().getPageEntriesNum() +893         gots.front().local16.size();894}895 896bool MipsGotSection::tryMergeGots(FileGot &dst, FileGot &src, bool isPrimary) {897  FileGot tmp = dst;898  set_union(tmp.pagesMap, src.pagesMap);899  set_union(tmp.local16, src.local16);900  set_union(tmp.global, src.global);901  set_union(tmp.relocs, src.relocs);902  set_union(tmp.tls, src.tls);903  set_union(tmp.dynTlsSymbols, src.dynTlsSymbols);904 905  size_t count = isPrimary ? headerEntriesNum : 0;906  count += tmp.getIndexedEntriesNum();907 908  if (count * ctx.arg.wordsize > ctx.arg.mipsGotSize)909    return false;910 911  std::swap(tmp, dst);912  return true;913}914 915void MipsGotSection::finalizeContents() { updateAllocSize(ctx); }916 917bool MipsGotSection::updateAllocSize(Ctx &ctx) {918  size = headerEntriesNum * ctx.arg.wordsize;919  for (const FileGot &g : gots)920    size += g.getEntriesNum() * ctx.arg.wordsize;921  return false;922}923 924void MipsGotSection::build() {925  if (gots.empty())926    return;927 928  std::vector<FileGot> mergedGots(1);929 930  // For each GOT move non-preemptible symbols from the `Global`931  // to `Local16` list. Preemptible symbol might become non-preemptible932  // one if, for example, it gets a related copy relocation.933  for (FileGot &got : gots) {934    for (auto &p: got.global)935      if (!p.first->isPreemptible)936        got.local16.insert({{p.first, 0}, 0});937    got.global.remove_if([&](const std::pair<Symbol *, size_t> &p) {938      return !p.first->isPreemptible;939    });940  }941 942  // For each GOT remove "reloc-only" entry if there is "global"943  // entry for the same symbol. And add local entries which indexed944  // using 32-bit value at the end of 16-bit entries.945  for (FileGot &got : gots) {946    got.relocs.remove_if([&](const std::pair<Symbol *, size_t> &p) {947      return got.global.count(p.first);948    });949    set_union(got.local16, got.local32);950    got.local32.clear();951  }952 953  // Evaluate number of "reloc-only" entries in the resulting GOT.954  // To do that put all unique "reloc-only" and "global" entries955  // from all GOTs to the future primary GOT.956  FileGot *primGot = &mergedGots.front();957  for (FileGot &got : gots) {958    set_union(primGot->relocs, got.global);959    set_union(primGot->relocs, got.relocs);960    got.relocs.clear();961  }962 963  // Evaluate number of "page" entries in each GOT.964  for (FileGot &got : gots) {965    for (std::pair<const OutputSection *, FileGot::PageBlock> &p :966         got.pagesMap) {967      const OutputSection *os = p.first;968      uint64_t secSize = 0;969      for (SectionCommand *cmd : os->commands) {970        if (auto *isd = dyn_cast<InputSectionDescription>(cmd))971          for (InputSection *isec : isd->sections) {972            uint64_t off = alignToPowerOf2(secSize, isec->addralign);973            secSize = off + isec->getSize();974          }975      }976      p.second.count = getMipsPageCount(secSize);977    }978  }979 980  // Merge GOTs. Try to join as much as possible GOTs but do not exceed981  // maximum GOT size. At first, try to fill the primary GOT because982  // the primary GOT can be accessed in the most effective way. If it983  // is not possible, try to fill the last GOT in the list, and finally984  // create a new GOT if both attempts failed.985  for (FileGot &srcGot : gots) {986    InputFile *file = srcGot.file;987    if (tryMergeGots(mergedGots.front(), srcGot, true)) {988      file->mipsGotIndex = 0;989    } else {990      // If this is the first time we failed to merge with the primary GOT,991      // MergedGots.back() will also be the primary GOT. We must make sure not992      // to try to merge again with isPrimary=false, as otherwise, if the993      // inputs are just right, we could allow the primary GOT to become 1 or 2994      // words bigger due to ignoring the header size.995      if (mergedGots.size() == 1 ||996          !tryMergeGots(mergedGots.back(), srcGot, false)) {997        mergedGots.emplace_back();998        std::swap(mergedGots.back(), srcGot);999      }1000      file->mipsGotIndex = mergedGots.size() - 1;1001    }1002  }1003  std::swap(gots, mergedGots);1004 1005  // Reduce number of "reloc-only" entries in the primary GOT1006  // by subtracting "global" entries in the primary GOT.1007  primGot = &gots.front();1008  primGot->relocs.remove_if([&](const std::pair<Symbol *, size_t> &p) {1009    return primGot->global.count(p.first);1010  });1011 1012  // Calculate indexes for each GOT entry.1013  size_t index = headerEntriesNum;1014  for (FileGot &got : gots) {1015    got.startIndex = &got == primGot ? 0 : index;1016    for (std::pair<const OutputSection *, FileGot::PageBlock> &p :1017         got.pagesMap) {1018      // For each output section referenced by GOT page relocations calculate1019      // and save into pagesMap an upper bound of MIPS GOT entries required1020      // to store page addresses of local symbols. We assume the worst case -1021      // each 64kb page of the output section has at least one GOT relocation1022      // against it. And take in account the case when the section intersects1023      // page boundaries.1024      p.second.firstIndex = index;1025      index += p.second.count;1026    }1027    for (auto &p: got.local16)1028      p.second = index++;1029    for (auto &p: got.global)1030      p.second = index++;1031    for (auto &p: got.relocs)1032      p.second = index++;1033    for (auto &p: got.tls)1034      p.second = index++;1035    for (auto &p: got.dynTlsSymbols) {1036      p.second = index;1037      index += 2;1038    }1039  }1040 1041  // Update SymbolAux::gotIdx field to use this1042  // value later in the `sortMipsSymbols` function.1043  for (auto &p : primGot->global) {1044    if (p.first->auxIdx == 0)1045      p.first->allocateAux(ctx);1046    ctx.symAux.back().gotIdx = p.second;1047  }1048  for (auto &p : primGot->relocs) {1049    if (p.first->auxIdx == 0)1050      p.first->allocateAux(ctx);1051    ctx.symAux.back().gotIdx = p.second;1052  }1053 1054  // Create dynamic relocations.1055  for (FileGot &got : gots) {1056    // Create dynamic relocations for TLS entries.1057    for (std::pair<Symbol *, size_t> &p : got.tls) {1058      Symbol *s = p.first;1059      uint64_t offset = p.second * ctx.arg.wordsize;1060      // When building a shared library we still need a dynamic relocation1061      // for the TP-relative offset as we don't know how much other data will1062      // be allocated before us in the static TLS block.1063      if (s->isPreemptible || ctx.arg.shared)1064        ctx.mainPart->relaDyn->addReloc(1065            {ctx.target->tlsGotRel, this, offset, true, *s, 0, R_ABS});1066    }1067    for (std::pair<Symbol *, size_t> &p : got.dynTlsSymbols) {1068      Symbol *s = p.first;1069      uint64_t offset = p.second * ctx.arg.wordsize;1070      if (s == nullptr) {1071        if (!ctx.arg.shared)1072          continue;1073        ctx.mainPart->relaDyn->addReloc(1074            {ctx.target->tlsModuleIndexRel, this, offset});1075      } else {1076        // When building a shared library we still need a dynamic relocation1077        // for the module index. Therefore only checking for1078        // S->isPreemptible is not sufficient (this happens e.g. for1079        // thread-locals that have been marked as local through a linker script)1080        if (!s->isPreemptible && !ctx.arg.shared)1081          continue;1082        ctx.mainPart->relaDyn->addSymbolReloc(ctx.target->tlsModuleIndexRel,1083                                              *this, offset, *s);1084        // However, we can skip writing the TLS offset reloc for non-preemptible1085        // symbols since it is known even in shared libraries1086        if (!s->isPreemptible)1087          continue;1088        offset += ctx.arg.wordsize;1089        ctx.mainPart->relaDyn->addSymbolReloc(ctx.target->tlsOffsetRel, *this,1090                                              offset, *s);1091      }1092    }1093 1094    // Do not create dynamic relocations for non-TLS1095    // entries in the primary GOT.1096    if (&got == primGot)1097      continue;1098 1099    // Dynamic relocations for "global" entries.1100    for (const std::pair<Symbol *, size_t> &p : got.global) {1101      uint64_t offset = p.second * ctx.arg.wordsize;1102      ctx.mainPart->relaDyn->addSymbolReloc(ctx.target->relativeRel, *this,1103                                            offset, *p.first);1104    }1105    if (!ctx.arg.isPic)1106      continue;1107    // Dynamic relocations for "local" entries in case of PIC.1108    for (const std::pair<const OutputSection *, FileGot::PageBlock> &l :1109         got.pagesMap) {1110      size_t pageCount = l.second.count;1111      for (size_t pi = 0; pi < pageCount; ++pi) {1112        uint64_t offset = (l.second.firstIndex + pi) * ctx.arg.wordsize;1113        ctx.mainPart->relaDyn->addReloc(1114            {ctx.target->relativeRel, this, offset, false, *l.second.repSym,1115             int64_t(pi * 0x10000), RE_MIPS_OSEC_LOCAL_PAGE});1116      }1117    }1118    for (const std::pair<GotEntry, size_t> &p : got.local16) {1119      uint64_t offset = p.second * ctx.arg.wordsize;1120      ctx.mainPart->relaDyn->addReloc({ctx.target->relativeRel, this, offset,1121                                       false, *p.first.first, p.first.second,1122                                       R_ABS});1123    }1124  }1125}1126 1127bool MipsGotSection::isNeeded() const {1128  // We add the .got section to the result for dynamic MIPS target because1129  // its address and properties are mentioned in the .dynamic section.1130  return !ctx.arg.relocatable;1131}1132 1133uint64_t MipsGotSection::getGp(const InputFile *f) const {1134  // For files without related GOT or files refer a primary GOT1135  // returns "common" _gp value. For secondary GOTs calculate1136  // individual _gp values.1137  if (!f || f->mipsGotIndex == uint32_t(-1) || f->mipsGotIndex == 0)1138    return ctx.sym.mipsGp->getVA(ctx, 0);1139  return getVA() + gots[f->mipsGotIndex].startIndex * ctx.arg.wordsize + 0x7ff0;1140}1141 1142void MipsGotSection::writeTo(uint8_t *buf) {1143  // Set the MSB of the second GOT slot. This is not required by any1144  // MIPS ABI documentation, though.1145  //1146  // There is a comment in glibc saying that "The MSB of got[1] of a1147  // gnu object is set to identify gnu objects," and in GNU gold it1148  // says "the second entry will be used by some runtime loaders".1149  // But how this field is being used is unclear.1150  //1151  // We are not really willing to mimic other linkers behaviors1152  // without understanding why they do that, but because all files1153  // generated by GNU tools have this special GOT value, and because1154  // we've been doing this for years, it is probably a safe bet to1155  // keep doing this for now. We really need to revisit this to see1156  // if we had to do this.1157  writeUint(ctx, buf + ctx.arg.wordsize,1158            (uint64_t)1 << (ctx.arg.wordsize * 8 - 1));1159  for (const FileGot &g : gots) {1160    auto write = [&](size_t i, const Symbol *s, int64_t a) {1161      uint64_t va = a;1162      if (s)1163        va = s->getVA(ctx, a);1164      writeUint(ctx, buf + i * ctx.arg.wordsize, va);1165    };1166    // Write 'page address' entries to the local part of the GOT.1167    for (const std::pair<const OutputSection *, FileGot::PageBlock> &l :1168         g.pagesMap) {1169      size_t pageCount = l.second.count;1170      uint64_t firstPageAddr = getMipsPageAddr(l.first->addr);1171      for (size_t pi = 0; pi < pageCount; ++pi)1172        write(l.second.firstIndex + pi, nullptr, firstPageAddr + pi * 0x10000);1173    }1174    // Local, global, TLS, reloc-only  entries.1175    // If TLS entry has a corresponding dynamic relocations, leave it1176    // initialized by zero. Write down adjusted TLS symbol's values otherwise.1177    // To calculate the adjustments use offsets for thread-local storage.1178    // http://web.archive.org/web/20190324223224/https://www.linux-mips.org/wiki/NPTL1179    for (const std::pair<GotEntry, size_t> &p : g.local16)1180      write(p.second, p.first.first, p.first.second);1181    // Write VA to the primary GOT only. For secondary GOTs that1182    // will be done by REL32 dynamic relocations.1183    if (&g == &gots.front())1184      for (const std::pair<Symbol *, size_t> &p : g.global)1185        write(p.second, p.first, 0);1186    for (const std::pair<Symbol *, size_t> &p : g.relocs)1187      write(p.second, p.first, 0);1188    for (const std::pair<Symbol *, size_t> &p : g.tls)1189      write(p.second, p.first,1190            p.first->isPreemptible || ctx.arg.shared ? 0 : -0x7000);1191    for (const std::pair<Symbol *, size_t> &p : g.dynTlsSymbols) {1192      if (p.first == nullptr && !ctx.arg.shared)1193        write(p.second, nullptr, 1);1194      else if (p.first && !p.first->isPreemptible) {1195        // If we are emitting a shared library with relocations we mustn't write1196        // anything to the GOT here. When using Elf_Rel relocations the value1197        // one will be treated as an addend and will cause crashes at runtime1198        if (!ctx.arg.shared)1199          write(p.second, nullptr, 1);1200        write(p.second + 1, p.first, -0x8000);1201      }1202    }1203  }1204}1205 1206// On PowerPC the .plt section is used to hold the table of function addresses1207// instead of the .got.plt, and the type is SHT_NOBITS similar to a .bss1208// section. I don't know why we have a BSS style type for the section but it is1209// consistent across both 64-bit PowerPC ABIs as well as the 32-bit PowerPC ABI.1210GotPltSection::GotPltSection(Ctx &ctx)1211    : SyntheticSection(ctx, ".got.plt", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE,1212                       ctx.target->gotEntrySize) {1213  if (ctx.arg.emachine == EM_PPC) {1214    name = ".plt";1215  } else if (ctx.arg.emachine == EM_PPC64) {1216    type = SHT_NOBITS;1217    name = ".plt";1218  }1219}1220 1221void GotPltSection::addEntry(Symbol &sym) {1222  assert(sym.auxIdx == ctx.symAux.size() - 1 &&1223         ctx.symAux.back().pltIdx == entries.size());1224  entries.push_back(&sym);1225}1226 1227size_t GotPltSection::getSize() const {1228  return (ctx.target->gotPltHeaderEntriesNum + entries.size()) *1229         ctx.target->gotEntrySize;1230}1231 1232void GotPltSection::writeTo(uint8_t *buf) {1233  ctx.target->writeGotPltHeader(buf);1234  buf += ctx.target->gotPltHeaderEntriesNum * ctx.target->gotEntrySize;1235  for (const Symbol *b : entries) {1236    ctx.target->writeGotPlt(buf, *b);1237    buf += ctx.target->gotEntrySize;1238  }1239}1240 1241bool GotPltSection::isNeeded() const {1242  // We need to emit GOTPLT even if it's empty if there's a relocation relative1243  // to it.1244  return !entries.empty() || hasGotPltOffRel;1245}1246 1247static StringRef getIgotPltName(Ctx &ctx) {1248  // On ARM the IgotPltSection is part of the GotSection.1249  if (ctx.arg.emachine == EM_ARM)1250    return ".got";1251 1252  // On PowerPC64 the GotPltSection is renamed to '.plt' so the IgotPltSection1253  // needs to be named the same.1254  if (ctx.arg.emachine == EM_PPC64)1255    return ".plt";1256 1257  return ".got.plt";1258}1259 1260// On PowerPC64 the GotPltSection type is SHT_NOBITS so we have to follow suit1261// with the IgotPltSection.1262IgotPltSection::IgotPltSection(Ctx &ctx)1263    : SyntheticSection(ctx, getIgotPltName(ctx),1264                       ctx.arg.emachine == EM_PPC64 ? SHT_NOBITS : SHT_PROGBITS,1265                       SHF_ALLOC | SHF_WRITE, ctx.target->gotEntrySize) {}1266 1267void IgotPltSection::addEntry(Symbol &sym) {1268  assert(ctx.symAux.back().pltIdx == entries.size());1269  entries.push_back(&sym);1270}1271 1272size_t IgotPltSection::getSize() const {1273  return entries.size() * ctx.target->gotEntrySize;1274}1275 1276void IgotPltSection::writeTo(uint8_t *buf) {1277  for (const Symbol *b : entries) {1278    ctx.target->writeIgotPlt(buf, *b);1279    buf += ctx.target->gotEntrySize;1280  }1281}1282 1283StringTableSection::StringTableSection(Ctx &ctx, StringRef name, bool dynamic)1284    : SyntheticSection(ctx, name, SHT_STRTAB, dynamic ? (uint64_t)SHF_ALLOC : 0,1285                       1),1286      dynamic(dynamic) {1287  // ELF string tables start with a NUL byte.1288  strings.push_back("");1289  stringMap.try_emplace(CachedHashStringRef(""), 0);1290  size = 1;1291}1292 1293// Adds a string to the string table. If `hashIt` is true we hash and check for1294// duplicates. It is optional because the name of global symbols are already1295// uniqued and hashing them again has a big cost for a small value: uniquing1296// them with some other string that happens to be the same.1297unsigned StringTableSection::addString(StringRef s, bool hashIt) {1298  if (hashIt) {1299    auto r = stringMap.try_emplace(CachedHashStringRef(s), size);1300    if (!r.second)1301      return r.first->second;1302  }1303  if (s.empty())1304    return 0;1305  unsigned ret = this->size;1306  this->size = this->size + s.size() + 1;1307  strings.push_back(s);1308  return ret;1309}1310 1311void StringTableSection::writeTo(uint8_t *buf) {1312  for (StringRef s : strings) {1313    memcpy(buf, s.data(), s.size());1314    buf[s.size()] = '\0';1315    buf += s.size() + 1;1316  }1317}1318 1319// Returns the number of entries in .gnu.version_d: the number of1320// non-VER_NDX_LOCAL-non-VER_NDX_GLOBAL definitions, plus 1.1321// Note that we don't support vd_cnt > 1 yet.1322static unsigned getVerDefNum(Ctx &ctx) {1323  return namedVersionDefs(ctx).size() + 1;1324}1325 1326template <class ELFT>1327DynamicSection<ELFT>::DynamicSection(Ctx &ctx)1328    : SyntheticSection(ctx, ".dynamic", SHT_DYNAMIC, SHF_ALLOC | SHF_WRITE,1329                       ctx.arg.wordsize) {1330  this->entsize = ELFT::Is64Bits ? 16 : 8;1331 1332  // .dynamic section is not writable on MIPS and on Fuchsia OS1333  // which passes -z rodynamic.1334  // See "Special Section" in Chapter 4 in the following document:1335  // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf1336  if (ctx.arg.emachine == EM_MIPS || ctx.arg.zRodynamic)1337    this->flags = SHF_ALLOC;1338}1339 1340// The output section .rela.dyn may include these synthetic sections:1341//1342// - part.relaDyn1343// - ctx.in.relaPlt: this is included if a linker script places .rela.plt inside1344//   .rela.dyn1345//1346// DT_RELASZ is the total size of the included sections.1347static uint64_t addRelaSz(Ctx &ctx, const RelocationBaseSection &relaDyn) {1348  size_t size = relaDyn.getSize();1349  if (ctx.in.relaPlt->getParent() == relaDyn.getParent())1350    size += ctx.in.relaPlt->getSize();1351  return size;1352}1353 1354// A Linker script may assign the RELA relocation sections to the same1355// output section. When this occurs we cannot just use the OutputSection1356// Size. Moreover the [DT_JMPREL, DT_JMPREL + DT_PLTRELSZ) is permitted to1357// overlap with the [DT_RELA, DT_RELA + DT_RELASZ).1358static uint64_t addPltRelSz(Ctx &ctx) { return ctx.in.relaPlt->getSize(); }1359 1360// Add remaining entries to complete .dynamic contents.1361template <class ELFT>1362std::vector<std::pair<int32_t, uint64_t>>1363DynamicSection<ELFT>::computeContents() {1364  elf::Partition &part = getPartition(ctx);1365  bool isMain = part.name.empty();1366  std::vector<std::pair<int32_t, uint64_t>> entries;1367 1368  auto addInt = [&](int32_t tag, uint64_t val) {1369    entries.emplace_back(tag, val);1370  };1371  auto addInSec = [&](int32_t tag, const InputSection &sec) {1372    entries.emplace_back(tag, sec.getVA());1373  };1374 1375  for (StringRef s : ctx.arg.filterList)1376    addInt(DT_FILTER, part.dynStrTab->addString(s));1377  for (StringRef s : ctx.arg.auxiliaryList)1378    addInt(DT_AUXILIARY, part.dynStrTab->addString(s));1379 1380  if (!ctx.arg.rpath.empty())1381    addInt(ctx.arg.enableNewDtags ? DT_RUNPATH : DT_RPATH,1382           part.dynStrTab->addString(ctx.arg.rpath));1383 1384  for (SharedFile *file : ctx.sharedFiles)1385    if (file->isNeeded)1386      addInt(DT_NEEDED, part.dynStrTab->addString(file->soName));1387 1388  if (isMain) {1389    if (!ctx.arg.soName.empty())1390      addInt(DT_SONAME, part.dynStrTab->addString(ctx.arg.soName));1391  } else {1392    if (!ctx.arg.soName.empty())1393      addInt(DT_NEEDED, part.dynStrTab->addString(ctx.arg.soName));1394    addInt(DT_SONAME, part.dynStrTab->addString(part.name));1395  }1396 1397  // Set DT_FLAGS and DT_FLAGS_1.1398  uint32_t dtFlags = 0;1399  uint32_t dtFlags1 = 0;1400  if (ctx.arg.bsymbolic == BsymbolicKind::All)1401    dtFlags |= DF_SYMBOLIC;1402  if (ctx.arg.zGlobal)1403    dtFlags1 |= DF_1_GLOBAL;1404  if (ctx.arg.zInitfirst)1405    dtFlags1 |= DF_1_INITFIRST;1406  if (ctx.arg.zInterpose)1407    dtFlags1 |= DF_1_INTERPOSE;1408  if (ctx.arg.zNodefaultlib)1409    dtFlags1 |= DF_1_NODEFLIB;1410  if (ctx.arg.zNodelete)1411    dtFlags1 |= DF_1_NODELETE;1412  if (ctx.arg.zNodlopen)1413    dtFlags1 |= DF_1_NOOPEN;1414  if (ctx.arg.pie)1415    dtFlags1 |= DF_1_PIE;1416  if (ctx.arg.zNow) {1417    dtFlags |= DF_BIND_NOW;1418    dtFlags1 |= DF_1_NOW;1419  }1420  if (ctx.arg.zOrigin) {1421    dtFlags |= DF_ORIGIN;1422    dtFlags1 |= DF_1_ORIGIN;1423  }1424  if (!ctx.arg.zText)1425    dtFlags |= DF_TEXTREL;1426  if (ctx.hasTlsIe && ctx.arg.shared)1427    dtFlags |= DF_STATIC_TLS;1428 1429  if (dtFlags)1430    addInt(DT_FLAGS, dtFlags);1431  if (dtFlags1)1432    addInt(DT_FLAGS_1, dtFlags1);1433 1434  // DT_DEBUG is a pointer to debug information used by debuggers at runtime. We1435  // need it for each process, so we don't write it for DSOs. The loader writes1436  // the pointer into this entry.1437  //1438  // DT_DEBUG is the only .dynamic entry that needs to be written to. Some1439  // systems (currently only Fuchsia OS) provide other means to give the1440  // debugger this information. Such systems may choose make .dynamic read-only.1441  // If the target is such a system (used -z rodynamic) don't write DT_DEBUG.1442  if (!ctx.arg.shared && !ctx.arg.relocatable && !ctx.arg.zRodynamic)1443    addInt(DT_DEBUG, 0);1444 1445  if (part.relaDyn->isNeeded()) {1446    addInSec(part.relaDyn->dynamicTag, *part.relaDyn);1447    entries.emplace_back(part.relaDyn->sizeDynamicTag,1448                         addRelaSz(ctx, *part.relaDyn));1449 1450    bool isRela = ctx.arg.isRela;1451    addInt(isRela ? DT_RELAENT : DT_RELENT,1452           isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel));1453 1454    // MIPS dynamic loader does not support RELCOUNT tag.1455    // The problem is in the tight relation between dynamic1456    // relocations and GOT. So do not emit this tag on MIPS.1457    if (ctx.arg.emachine != EM_MIPS) {1458      size_t numRelativeRels = part.relaDyn->getRelativeRelocCount();1459      if (ctx.arg.zCombreloc && numRelativeRels)1460        addInt(isRela ? DT_RELACOUNT : DT_RELCOUNT, numRelativeRels);1461    }1462  }1463  if (part.relrDyn && part.relrDyn->getParent() &&1464      !part.relrDyn->relocs.empty()) {1465    addInSec(ctx.arg.useAndroidRelrTags ? DT_ANDROID_RELR : DT_RELR,1466             *part.relrDyn);1467    addInt(ctx.arg.useAndroidRelrTags ? DT_ANDROID_RELRSZ : DT_RELRSZ,1468           part.relrDyn->getParent()->size);1469    addInt(ctx.arg.useAndroidRelrTags ? DT_ANDROID_RELRENT : DT_RELRENT,1470           sizeof(Elf_Relr));1471  }1472  if (part.relrAuthDyn && part.relrAuthDyn->getParent() &&1473      !part.relrAuthDyn->relocs.empty()) {1474    addInSec(DT_AARCH64_AUTH_RELR, *part.relrAuthDyn);1475    addInt(DT_AARCH64_AUTH_RELRSZ, part.relrAuthDyn->getParent()->size);1476    addInt(DT_AARCH64_AUTH_RELRENT, sizeof(Elf_Relr));1477  }1478  if (isMain && ctx.in.relaPlt->isNeeded()) {1479    addInSec(DT_JMPREL, *ctx.in.relaPlt);1480    entries.emplace_back(DT_PLTRELSZ, addPltRelSz(ctx));1481    switch (ctx.arg.emachine) {1482    case EM_MIPS:1483      addInSec(DT_MIPS_PLTGOT, *ctx.in.gotPlt);1484      break;1485    case EM_S390:1486      addInSec(DT_PLTGOT, *ctx.in.got);1487      break;1488    case EM_SPARCV9:1489      addInSec(DT_PLTGOT, *ctx.in.plt);1490      break;1491    case EM_AARCH64:1492      if (llvm::find_if(ctx.in.relaPlt->relocs, [&ctx = ctx](1493                                                    const DynamicReloc &r) {1494            return r.type == ctx.target->pltRel &&1495                   r.sym->stOther & STO_AARCH64_VARIANT_PCS;1496          }) != ctx.in.relaPlt->relocs.end())1497        addInt(DT_AARCH64_VARIANT_PCS, 0);1498      addInSec(DT_PLTGOT, *ctx.in.gotPlt);1499      break;1500    case EM_RISCV:1501      if (llvm::any_of(ctx.in.relaPlt->relocs, [&ctx = ctx](1502                                                   const DynamicReloc &r) {1503            return r.type == ctx.target->pltRel &&1504                   (r.sym->stOther & STO_RISCV_VARIANT_CC);1505          }))1506        addInt(DT_RISCV_VARIANT_CC, 0);1507      [[fallthrough]];1508    default:1509      addInSec(DT_PLTGOT, *ctx.in.gotPlt);1510      break;1511    }1512    addInt(DT_PLTREL, ctx.arg.isRela ? DT_RELA : DT_REL);1513  }1514 1515  if (ctx.arg.emachine == EM_AARCH64) {1516    if (ctx.arg.andFeatures & GNU_PROPERTY_AARCH64_FEATURE_1_BTI)1517      addInt(DT_AARCH64_BTI_PLT, 0);1518    if (ctx.arg.zPacPlt)1519      addInt(DT_AARCH64_PAC_PLT, 0);1520 1521    if (hasMemtag(ctx)) {1522      addInt(DT_AARCH64_MEMTAG_MODE, ctx.arg.androidMemtagMode == NT_MEMTAG_LEVEL_ASYNC);1523      addInt(DT_AARCH64_MEMTAG_HEAP, ctx.arg.androidMemtagHeap);1524      addInt(DT_AARCH64_MEMTAG_STACK, ctx.arg.androidMemtagStack);1525      if (ctx.mainPart->memtagGlobalDescriptors->isNeeded()) {1526        addInSec(DT_AARCH64_MEMTAG_GLOBALS,1527                 *ctx.mainPart->memtagGlobalDescriptors);1528        addInt(DT_AARCH64_MEMTAG_GLOBALSSZ,1529               ctx.mainPart->memtagGlobalDescriptors->getSize());1530      }1531    }1532  }1533 1534  addInSec(DT_SYMTAB, *part.dynSymTab);1535  addInt(DT_SYMENT, sizeof(Elf_Sym));1536  addInSec(DT_STRTAB, *part.dynStrTab);1537  addInt(DT_STRSZ, part.dynStrTab->getSize());1538  if (!ctx.arg.zText)1539    addInt(DT_TEXTREL, 0);1540  if (part.gnuHashTab && part.gnuHashTab->getParent())1541    addInSec(DT_GNU_HASH, *part.gnuHashTab);1542  if (part.hashTab && part.hashTab->getParent())1543    addInSec(DT_HASH, *part.hashTab);1544 1545  if (isMain) {1546    if (ctx.out.preinitArray) {1547      addInt(DT_PREINIT_ARRAY, ctx.out.preinitArray->addr);1548      addInt(DT_PREINIT_ARRAYSZ, ctx.out.preinitArray->size);1549    }1550    if (ctx.out.initArray) {1551      addInt(DT_INIT_ARRAY, ctx.out.initArray->addr);1552      addInt(DT_INIT_ARRAYSZ, ctx.out.initArray->size);1553    }1554    if (ctx.out.finiArray) {1555      addInt(DT_FINI_ARRAY, ctx.out.finiArray->addr);1556      addInt(DT_FINI_ARRAYSZ, ctx.out.finiArray->size);1557    }1558 1559    if (Symbol *b = ctx.symtab->find(ctx.arg.init))1560      if (b->isDefined())1561        addInt(DT_INIT, b->getVA(ctx));1562    if (Symbol *b = ctx.symtab->find(ctx.arg.fini))1563      if (b->isDefined())1564        addInt(DT_FINI, b->getVA(ctx));1565  }1566 1567  if (part.verSym && part.verSym->isNeeded())1568    addInSec(DT_VERSYM, *part.verSym);1569  if (part.verDef && part.verDef->isLive()) {1570    addInSec(DT_VERDEF, *part.verDef);1571    addInt(DT_VERDEFNUM, getVerDefNum(ctx));1572  }1573  if (part.verNeed && part.verNeed->isNeeded()) {1574    addInSec(DT_VERNEED, *part.verNeed);1575    unsigned needNum = 0;1576    for (SharedFile *f : ctx.sharedFiles)1577      if (!f->vernauxs.empty())1578        ++needNum;1579    addInt(DT_VERNEEDNUM, needNum);1580  }1581 1582  if (ctx.arg.emachine == EM_MIPS) {1583    addInt(DT_MIPS_RLD_VERSION, 1);1584    addInt(DT_MIPS_FLAGS, RHF_NOTPOT);1585    addInt(DT_MIPS_BASE_ADDRESS, ctx.target->getImageBase());1586    addInt(DT_MIPS_SYMTABNO, part.dynSymTab->getNumSymbols());1587    addInt(DT_MIPS_LOCAL_GOTNO, ctx.in.mipsGot->getLocalEntriesNum());1588 1589    if (const Symbol *b = ctx.in.mipsGot->getFirstGlobalEntry())1590      addInt(DT_MIPS_GOTSYM, b->dynsymIndex);1591    else1592      addInt(DT_MIPS_GOTSYM, part.dynSymTab->getNumSymbols());1593    addInSec(DT_PLTGOT, *ctx.in.mipsGot);1594    if (ctx.in.mipsRldMap) {1595      if (!ctx.arg.pie)1596        addInSec(DT_MIPS_RLD_MAP, *ctx.in.mipsRldMap);1597      // Store the offset to the .rld_map section1598      // relative to the address of the tag.1599      addInt(DT_MIPS_RLD_MAP_REL,1600             ctx.in.mipsRldMap->getVA() - (getVA() + entries.size() * entsize));1601    }1602  }1603 1604  // DT_PPC_GOT indicates to glibc Secure PLT is used. If DT_PPC_GOT is absent,1605  // glibc assumes the old-style BSS PLT layout which we don't support.1606  if (ctx.arg.emachine == EM_PPC)1607    addInSec(DT_PPC_GOT, *ctx.in.got);1608 1609  // Glink dynamic tag is required by the V2 abi if the plt section isn't empty.1610  if (ctx.arg.emachine == EM_PPC64 && ctx.in.plt->isNeeded()) {1611    // The Glink tag points to 32 bytes before the first lazy symbol resolution1612    // stub, which starts directly after the header.1613    addInt(DT_PPC64_GLINK,1614           ctx.in.plt->getVA() + ctx.target->pltHeaderSize - 32);1615  }1616 1617  if (ctx.arg.emachine == EM_PPC64)1618    addInt(DT_PPC64_OPT, ctx.target->ppc64DynamicSectionOpt);1619 1620  addInt(DT_NULL, 0);1621  return entries;1622}1623 1624template <class ELFT> void DynamicSection<ELFT>::finalizeContents() {1625  if (OutputSection *sec = getPartition(ctx).dynStrTab->getParent())1626    getParent()->link = sec->sectionIndex;1627  this->size = computeContents().size() * this->entsize;1628}1629 1630template <class ELFT> void DynamicSection<ELFT>::writeTo(uint8_t *buf) {1631  auto *p = reinterpret_cast<Elf_Dyn *>(buf);1632 1633  for (std::pair<int32_t, uint64_t> kv : computeContents()) {1634    p->d_tag = kv.first;1635    p->d_un.d_val = kv.second;1636    ++p;1637  }1638}1639 1640uint64_t DynamicReloc::getOffset() const {1641  return inputSec->getVA(offsetInSec);1642}1643 1644int64_t DynamicReloc::computeAddend(Ctx &ctx) const {1645  assert(!isFinal && "addend already computed");1646  uint64_t ca = inputSec->getRelocTargetVA(1647      ctx, Relocation{expr, type, 0, addend, sym}, getOffset());1648  return ctx.arg.is64 ? ca : SignExtend64<32>(ca);1649}1650 1651uint32_t DynamicReloc::getSymIndex(SymbolTableBaseSection *symTab) const {1652  if (!needsDynSymIndex())1653    return 0;1654 1655  size_t index = symTab->getSymbolIndex(*sym);1656  assert((index != 0 ||1657          (type != symTab->ctx.target->gotRel &&1658           type != symTab->ctx.target->pltRel) ||1659          !symTab->ctx.mainPart->dynSymTab->getParent()) &&1660         "GOT or PLT relocation must refer to symbol in dynamic symbol table");1661  return index;1662}1663 1664RelocationBaseSection::RelocationBaseSection(Ctx &ctx, StringRef name,1665                                             uint32_t type, int32_t dynamicTag,1666                                             int32_t sizeDynamicTag,1667                                             bool combreloc,1668                                             unsigned concurrency)1669    : SyntheticSection(ctx, name, type, SHF_ALLOC, ctx.arg.wordsize),1670      dynamicTag(dynamicTag), sizeDynamicTag(sizeDynamicTag),1671      relocsVec(concurrency), combreloc(combreloc) {}1672 1673void RelocationBaseSection::addSymbolReloc(1674    RelType dynType, InputSectionBase &isec, uint64_t offsetInSec, Symbol &sym,1675    int64_t addend, std::optional<RelType> addendRelType) {1676  addReloc(true, dynType, isec, offsetInSec, sym, addend, R_ADDEND,1677           addendRelType ? *addendRelType : ctx.target->noneRel);1678}1679 1680void RelocationBaseSection::addAddendOnlyRelocIfNonPreemptible(1681    RelType dynType, InputSectionBase &isec, uint64_t offsetInSec, Symbol &sym,1682    RelType addendRelType) {1683  // No need to write an addend to the section for preemptible symbols.1684  if (sym.isPreemptible)1685    addReloc({dynType, &isec, offsetInSec, true, sym, 0, R_ADDEND});1686  else1687    addReloc(false, dynType, isec, offsetInSec, sym, 0, R_ABS, addendRelType);1688}1689 1690void RelocationBaseSection::mergeRels() {1691  size_t newSize = relocs.size();1692  for (const auto &v : relocsVec)1693    newSize += v.size();1694  relocs.reserve(newSize);1695  for (const auto &v : relocsVec)1696    llvm::append_range(relocs, v);1697  relocsVec.clear();1698}1699 1700void RelocationBaseSection::partitionRels() {1701  if (!combreloc)1702    return;1703  const RelType relativeRel = ctx.target->relativeRel;1704  numRelativeRelocs =1705      std::stable_partition(relocs.begin(), relocs.end(),1706                            [=](auto &r) { return r.type == relativeRel; }) -1707      relocs.begin();1708}1709 1710void RelocationBaseSection::finalizeContents() {1711  SymbolTableBaseSection *symTab = getPartition(ctx).dynSymTab.get();1712 1713  // When linking glibc statically, .rel{,a}.plt contains R_*_IRELATIVE1714  // relocations due to IFUNC (e.g. strcpy). sh_link will be set to 0 in that1715  // case.1716  if (symTab && symTab->getParent())1717    getParent()->link = symTab->getParent()->sectionIndex;1718  else1719    getParent()->link = 0;1720 1721  if (ctx.in.relaPlt.get() == this && ctx.in.gotPlt->getParent()) {1722    getParent()->flags |= ELF::SHF_INFO_LINK;1723    getParent()->info = ctx.in.gotPlt->getParent()->sectionIndex;1724  }1725}1726 1727void DynamicReloc::finalize(Ctx &ctx, SymbolTableBaseSection *symt) {1728  r_offset = getOffset();1729  r_sym = getSymIndex(symt);1730  addend = computeAddend(ctx);1731  isFinal = true; // Catch errors1732}1733 1734void RelocationBaseSection::computeRels() {1735  SymbolTableBaseSection *symTab = getPartition(ctx).dynSymTab.get();1736  parallelForEach(relocs, [&ctx = ctx, symTab](DynamicReloc &rel) {1737    rel.finalize(ctx, symTab);1738  });1739 1740  auto irelative = std::stable_partition(1741      relocs.begin() + numRelativeRelocs, relocs.end(),1742      [t = ctx.target->iRelativeRel](auto &r) { return r.type != t; });1743 1744  // Sort by (!IsRelative,SymIndex,r_offset). DT_REL[A]COUNT requires us to1745  // place R_*_RELATIVE first. SymIndex is to improve locality, while r_offset1746  // is to make results easier to read.1747  if (combreloc) {1748    auto nonRelative = relocs.begin() + numRelativeRelocs;1749    parallelSort(relocs.begin(), nonRelative,1750                 [&](auto &a, auto &b) { return a.r_offset < b.r_offset; });1751    // Non-relative relocations are few, so don't bother with parallelSort.1752    llvm::sort(nonRelative, irelative, [&](auto &a, auto &b) {1753      return std::tie(a.r_sym, a.r_offset) < std::tie(b.r_sym, b.r_offset);1754    });1755  }1756}1757 1758template <class ELFT>1759RelocationSection<ELFT>::RelocationSection(Ctx &ctx, StringRef name,1760                                           bool combreloc, unsigned concurrency)1761    : RelocationBaseSection(ctx, name, ctx.arg.isRela ? SHT_RELA : SHT_REL,1762                            ctx.arg.isRela ? DT_RELA : DT_REL,1763                            ctx.arg.isRela ? DT_RELASZ : DT_RELSZ, combreloc,1764                            concurrency) {1765  this->entsize = ctx.arg.isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);1766}1767 1768template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *buf) {1769  computeRels();1770  for (const DynamicReloc &rel : relocs) {1771    auto *p = reinterpret_cast<Elf_Rela *>(buf);1772    p->r_offset = rel.r_offset;1773    p->setSymbolAndType(rel.r_sym, rel.type, ctx.arg.isMips64EL);1774    if (ctx.arg.isRela)1775      p->r_addend = rel.addend;1776    buf += ctx.arg.isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);1777  }1778}1779 1780RelrBaseSection::RelrBaseSection(Ctx &ctx, unsigned concurrency,1781                                 bool isAArch64Auth)1782    : SyntheticSection(1783          ctx, isAArch64Auth ? ".relr.auth.dyn" : ".relr.dyn",1784          isAArch64Auth1785              ? SHT_AARCH64_AUTH_RELR1786              : (ctx.arg.useAndroidRelrTags ? SHT_ANDROID_RELR : SHT_RELR),1787          SHF_ALLOC, ctx.arg.wordsize),1788      relocsVec(concurrency) {}1789 1790void RelrBaseSection::mergeRels() {1791  size_t newSize = relocs.size();1792  for (const auto &v : relocsVec)1793    newSize += v.size();1794  relocs.reserve(newSize);1795  for (const auto &v : relocsVec)1796    llvm::append_range(relocs, v);1797  relocsVec.clear();1798}1799 1800template <class ELFT>1801AndroidPackedRelocationSection<ELFT>::AndroidPackedRelocationSection(1802    Ctx &ctx, StringRef name, unsigned concurrency)1803    : RelocationBaseSection(1804          ctx, name, ctx.arg.isRela ? SHT_ANDROID_RELA : SHT_ANDROID_REL,1805          ctx.arg.isRela ? DT_ANDROID_RELA : DT_ANDROID_REL,1806          ctx.arg.isRela ? DT_ANDROID_RELASZ : DT_ANDROID_RELSZ,1807          /*combreloc=*/false, concurrency) {1808  this->entsize = 1;1809}1810 1811template <class ELFT>1812bool AndroidPackedRelocationSection<ELFT>::updateAllocSize(Ctx &ctx) {1813  // This function computes the contents of an Android-format packed relocation1814  // section.1815  //1816  // This format compresses relocations by using relocation groups to factor out1817  // fields that are common between relocations and storing deltas from previous1818  // relocations in SLEB128 format (which has a short representation for small1819  // numbers). A good example of a relocation type with common fields is1820  // R_*_RELATIVE, which is normally used to represent function pointers in1821  // vtables. In the REL format, each relative relocation has the same r_info1822  // field, and is only different from other relative relocations in terms of1823  // the r_offset field. By sorting relocations by offset, grouping them by1824  // r_info and representing each relocation with only the delta from the1825  // previous offset, each 8-byte relocation can be compressed to as little as 11826  // byte (or less with run-length encoding). This relocation packer was able to1827  // reduce the size of the relocation section in an Android Chromium DSO from1828  // 2,911,184 bytes to 174,693 bytes, or 6% of the original size.1829  //1830  // A relocation section consists of a header containing the literal bytes1831  // 'APS2' followed by a sequence of SLEB128-encoded integers. The first two1832  // elements are the total number of relocations in the section and an initial1833  // r_offset value. The remaining elements define a sequence of relocation1834  // groups. Each relocation group starts with a header consisting of the1835  // following elements:1836  //1837  // - the number of relocations in the relocation group1838  // - flags for the relocation group1839  // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is set) the r_offset delta1840  //   for each relocation in the group.1841  // - (if RELOCATION_GROUPED_BY_INFO_FLAG is set) the value of the r_info1842  //   field for each relocation in the group.1843  // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG and1844  //   RELOCATION_GROUPED_BY_ADDEND_FLAG are set) the r_addend delta for1845  //   each relocation in the group.1846  //1847  // Following the relocation group header are descriptions of each of the1848  // relocations in the group. They consist of the following elements:1849  //1850  // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is not set) the r_offset1851  //   delta for this relocation.1852  // - (if RELOCATION_GROUPED_BY_INFO_FLAG is not set) the value of the r_info1853  //   field for this relocation.1854  // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG is set and1855  //   RELOCATION_GROUPED_BY_ADDEND_FLAG is not set) the r_addend delta for1856  //   this relocation.1857 1858  size_t oldSize = relocData.size();1859 1860  relocData = {'A', 'P', 'S', '2'};1861  raw_svector_ostream os(relocData);1862  auto add = [&](int64_t v) { encodeSLEB128(v, os); };1863 1864  // The format header includes the number of relocations and the initial1865  // offset (we set this to zero because the first relocation group will1866  // perform the initial adjustment).1867  add(relocs.size());1868  add(0);1869 1870  std::vector<Elf_Rela> relatives, nonRelatives;1871 1872  for (const DynamicReloc &rel : relocs) {1873    Elf_Rela r;1874    r.r_offset = rel.getOffset();1875    r.setSymbolAndType(rel.getSymIndex(getPartition(ctx).dynSymTab.get()),1876                       rel.type, false);1877    r.r_addend = ctx.arg.isRela ? rel.computeAddend(ctx) : 0;1878 1879    if (r.getType(ctx.arg.isMips64EL) == ctx.target->relativeRel)1880      relatives.push_back(r);1881    else1882      nonRelatives.push_back(r);1883  }1884 1885  llvm::sort(relatives, [](const Elf_Rel &a, const Elf_Rel &b) {1886    return a.r_offset < b.r_offset;1887  });1888 1889  // Try to find groups of relative relocations which are spaced one word1890  // apart from one another. These generally correspond to vtable entries. The1891  // format allows these groups to be encoded using a sort of run-length1892  // encoding, but each group will cost 7 bytes in addition to the offset from1893  // the previous group, so it is only profitable to do this for groups of1894  // size 8 or larger.1895  std::vector<Elf_Rela> ungroupedRelatives;1896  std::vector<std::vector<Elf_Rela>> relativeGroups;1897  for (auto i = relatives.begin(), e = relatives.end(); i != e;) {1898    std::vector<Elf_Rela> group;1899    do {1900      group.push_back(*i++);1901    } while (i != e && (i - 1)->r_offset + ctx.arg.wordsize == i->r_offset);1902 1903    if (group.size() < 8)1904      ungroupedRelatives.insert(ungroupedRelatives.end(), group.begin(),1905                                group.end());1906    else1907      relativeGroups.emplace_back(std::move(group));1908  }1909 1910  // For non-relative relocations, we would like to:1911  //   1. Have relocations with the same symbol offset to be consecutive, so1912  //      that the runtime linker can speed-up symbol lookup by implementing an1913  //      1-entry cache.1914  //   2. Group relocations by r_info to reduce the size of the relocation1915  //      section.1916  // Since the symbol offset is the high bits in r_info, sorting by r_info1917  // allows us to do both.1918  //1919  // For Rela, we also want to sort by r_addend when r_info is the same. This1920  // enables us to group by r_addend as well.1921  llvm::sort(nonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) {1922    return std::tie(a.r_info, a.r_addend, a.r_offset) <1923           std::tie(b.r_info, b.r_addend, b.r_offset);1924  });1925 1926  // Group relocations with the same r_info. Note that each group emits a group1927  // header and that may make the relocation section larger. It is hard to1928  // estimate the size of a group header as the encoded size of that varies1929  // based on r_info. However, we can approximate this trade-off by the number1930  // of values encoded. Each group header contains 3 values, and each relocation1931  // in a group encodes one less value, as compared to when it is not grouped.1932  // Therefore, we only group relocations if there are 3 or more of them with1933  // the same r_info.1934  //1935  // For Rela, the addend for most non-relative relocations is zero, and thus we1936  // can usually get a smaller relocation section if we group relocations with 01937  // addend as well.1938  std::vector<Elf_Rela> ungroupedNonRelatives;1939  std::vector<std::vector<Elf_Rela>> nonRelativeGroups;1940  for (auto i = nonRelatives.begin(), e = nonRelatives.end(); i != e;) {1941    auto j = i + 1;1942    while (j != e && i->r_info == j->r_info &&1943           (!ctx.arg.isRela || i->r_addend == j->r_addend))1944      ++j;1945    if (j - i < 3 || (ctx.arg.isRela && i->r_addend != 0))1946      ungroupedNonRelatives.insert(ungroupedNonRelatives.end(), i, j);1947    else1948      nonRelativeGroups.emplace_back(i, j);1949    i = j;1950  }1951 1952  // Sort ungrouped relocations by offset to minimize the encoded length.1953  llvm::sort(ungroupedNonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) {1954    return a.r_offset < b.r_offset;1955  });1956 1957  unsigned hasAddendIfRela =1958      ctx.arg.isRela ? RELOCATION_GROUP_HAS_ADDEND_FLAG : 0;1959 1960  uint64_t offset = 0;1961  uint64_t addend = 0;1962 1963  // Emit the run-length encoding for the groups of adjacent relative1964  // relocations. Each group is represented using two groups in the packed1965  // format. The first is used to set the current offset to the start of the1966  // group (and also encodes the first relocation), and the second encodes the1967  // remaining relocations.1968  for (std::vector<Elf_Rela> &g : relativeGroups) {1969    // The first relocation in the group.1970    add(1);1971    add(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |1972        RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);1973    add(g[0].r_offset - offset);1974    add(ctx.target->relativeRel);1975    if (ctx.arg.isRela) {1976      add(g[0].r_addend - addend);1977      addend = g[0].r_addend;1978    }1979 1980    // The remaining relocations.1981    add(g.size() - 1);1982    add(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |1983        RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);1984    add(ctx.arg.wordsize);1985    add(ctx.target->relativeRel);1986    if (ctx.arg.isRela) {1987      for (const auto &i : llvm::drop_begin(g)) {1988        add(i.r_addend - addend);1989        addend = i.r_addend;1990      }1991    }1992 1993    offset = g.back().r_offset;1994  }1995 1996  // Now the ungrouped relatives.1997  if (!ungroupedRelatives.empty()) {1998    add(ungroupedRelatives.size());1999    add(RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);2000    add(ctx.target->relativeRel);2001    for (Elf_Rela &r : ungroupedRelatives) {2002      add(r.r_offset - offset);2003      offset = r.r_offset;2004      if (ctx.arg.isRela) {2005        add(r.r_addend - addend);2006        addend = r.r_addend;2007      }2008    }2009  }2010 2011  // Grouped non-relatives.2012  for (ArrayRef<Elf_Rela> g : nonRelativeGroups) {2013    add(g.size());2014    add(RELOCATION_GROUPED_BY_INFO_FLAG);2015    add(g[0].r_info);2016    for (const Elf_Rela &r : g) {2017      add(r.r_offset - offset);2018      offset = r.r_offset;2019    }2020    addend = 0;2021  }2022 2023  // Finally the ungrouped non-relative relocations.2024  if (!ungroupedNonRelatives.empty()) {2025    add(ungroupedNonRelatives.size());2026    add(hasAddendIfRela);2027    for (Elf_Rela &r : ungroupedNonRelatives) {2028      add(r.r_offset - offset);2029      offset = r.r_offset;2030      add(r.r_info);2031      if (ctx.arg.isRela) {2032        add(r.r_addend - addend);2033        addend = r.r_addend;2034      }2035    }2036  }2037 2038  // Don't allow the section to shrink; otherwise the size of the section can2039  // oscillate infinitely.2040  if (relocData.size() < oldSize)2041    relocData.append(oldSize - relocData.size(), 0);2042 2043  // Returns whether the section size changed. We need to keep recomputing both2044  // section layout and the contents of this section until the size converges2045  // because changing this section's size can affect section layout, which in2046  // turn can affect the sizes of the LEB-encoded integers stored in this2047  // section.2048  return relocData.size() != oldSize;2049}2050 2051template <class ELFT>2052RelrSection<ELFT>::RelrSection(Ctx &ctx, unsigned concurrency,2053                               bool isAArch64Auth)2054    : RelrBaseSection(ctx, concurrency, isAArch64Auth) {2055  this->entsize = ctx.arg.wordsize;2056}2057 2058template <class ELFT> bool RelrSection<ELFT>::updateAllocSize(Ctx &ctx) {2059  // This function computes the contents of an SHT_RELR packed relocation2060  // section.2061  //2062  // Proposal for adding SHT_RELR sections to generic-abi is here:2063  //   https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg2064  //2065  // The encoded sequence of Elf64_Relr entries in a SHT_RELR section looks2066  // like [ AAAAAAAA BBBBBBB1 BBBBBBB1 ... AAAAAAAA BBBBBB1 ... ]2067  //2068  // i.e. start with an address, followed by any number of bitmaps. The address2069  // entry encodes 1 relocation. The subsequent bitmap entries encode up to 632070  // relocations each, at subsequent offsets following the last address entry.2071  //2072  // The bitmap entries must have 1 in the least significant bit. The assumption2073  // here is that an address cannot have 1 in lsb. Odd addresses are not2074  // supported.2075  //2076  // Excluding the least significant bit in the bitmap, each non-zero bit in2077  // the bitmap represents a relocation to be applied to a corresponding machine2078  // word that follows the base address word. The second least significant bit2079  // represents the machine word immediately following the initial address, and2080  // each bit that follows represents the next word, in linear order. As such,2081  // a single bitmap can encode up to 31 relocations in a 32-bit object, and2082  // 63 relocations in a 64-bit object.2083  //2084  // This encoding has a couple of interesting properties:2085  // 1. Looking at any entry, it is clear whether it's an address or a bitmap:2086  //    even means address, odd means bitmap.2087  // 2. Just a simple list of addresses is a valid encoding.2088 2089  size_t oldSize = relrRelocs.size();2090  relrRelocs.clear();2091 2092  const size_t wordsize = sizeof(typename ELFT::uint);2093 2094  // Number of bits to use for the relocation offsets bitmap.2095  // Must be either 63 or 31.2096  const size_t nBits = wordsize * 8 - 1;2097 2098  // Get offsets for all relative relocations and sort them.2099  std::unique_ptr<uint64_t[]> offsets(new uint64_t[relocs.size()]);2100  for (auto [i, r] : llvm::enumerate(relocs))2101    offsets[i] = r.getOffset();2102  llvm::sort(offsets.get(), offsets.get() + relocs.size());2103 2104  // For each leading relocation, find following ones that can be folded2105  // as a bitmap and fold them.2106  for (size_t i = 0, e = relocs.size(); i != e;) {2107    // Add a leading relocation.2108    relrRelocs.push_back(Elf_Relr(offsets[i]));2109    uint64_t base = offsets[i] + wordsize;2110    ++i;2111 2112    // Find foldable relocations to construct bitmaps.2113    for (;;) {2114      uint64_t bitmap = 0;2115      for (; i != e; ++i) {2116        uint64_t d = offsets[i] - base;2117        if (d >= nBits * wordsize || d % wordsize)2118          break;2119        bitmap |= uint64_t(1) << (d / wordsize);2120      }2121      if (!bitmap)2122        break;2123      relrRelocs.push_back(Elf_Relr((bitmap << 1) | 1));2124      base += nBits * wordsize;2125    }2126  }2127 2128  // Don't allow the section to shrink; otherwise the size of the section can2129  // oscillate infinitely. Trailing 1s do not decode to more relocations.2130  if (relrRelocs.size() < oldSize) {2131    Log(ctx) << ".relr.dyn needs " << (oldSize - relrRelocs.size())2132             << " padding word(s)";2133    relrRelocs.resize(oldSize, Elf_Relr(1));2134  }2135 2136  return relrRelocs.size() != oldSize;2137}2138 2139SymbolTableBaseSection::SymbolTableBaseSection(Ctx &ctx,2140                                               StringTableSection &strTabSec)2141    : SyntheticSection(ctx, strTabSec.isDynamic() ? ".dynsym" : ".symtab",2142                       strTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,2143                       strTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,2144                       ctx.arg.wordsize),2145      strTabSec(strTabSec) {}2146 2147// Orders symbols according to their positions in the GOT,2148// in compliance with MIPS ABI rules.2149// See "Global Offset Table" in Chapter 5 in the following document2150// for detailed description:2151// ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf2152static void sortMipsSymbols(Ctx &ctx, SmallVector<SymbolTableEntry, 0> &syms) {2153  llvm::stable_sort(syms,2154                    [&](const SymbolTableEntry &l, const SymbolTableEntry &r) {2155                      // Sort entries related to non-local preemptible symbols2156                      // by GOT indexes. All other entries go to the beginning2157                      // of a dynsym in arbitrary order.2158                      if (l.sym->isInGot(ctx) && r.sym->isInGot(ctx))2159                        return l.sym->getGotIdx(ctx) < r.sym->getGotIdx(ctx);2160                      if (!l.sym->isInGot(ctx) && !r.sym->isInGot(ctx))2161                        return false;2162                      return !l.sym->isInGot(ctx);2163                    });2164}2165 2166void SymbolTableBaseSection::finalizeContents() {2167  if (OutputSection *sec = strTabSec.getParent())2168    getParent()->link = sec->sectionIndex;2169 2170  if (this->type != SHT_DYNSYM) {2171    sortSymTabSymbols();2172    return;2173  }2174 2175  // If it is a .dynsym, there should be no local symbols, but we need2176  // to do a few things for the dynamic linker.2177 2178  // Section's Info field has the index of the first non-local symbol.2179  // Because the first symbol entry is a null entry, 1 is the first.2180  getParent()->info = 1;2181 2182  if (getPartition(ctx).gnuHashTab) {2183    // NB: It also sorts Symbols to meet the GNU hash table requirements.2184    getPartition(ctx).gnuHashTab->addSymbols(symbols);2185  } else if (ctx.arg.emachine == EM_MIPS) {2186    sortMipsSymbols(ctx, symbols);2187  }2188 2189  // Only the main partition's dynsym indexes are stored in the symbols2190  // themselves. All other partitions use a lookup table.2191  if (this == ctx.mainPart->dynSymTab.get()) {2192    size_t i = 0;2193    for (const SymbolTableEntry &s : symbols)2194      s.sym->dynsymIndex = ++i;2195  }2196}2197 2198// The ELF spec requires that all local symbols precede global symbols, so we2199// sort symbol entries in this function. (For .dynsym, we don't do that because2200// symbols for dynamic linking are inherently all globals.)2201//2202// Aside from above, we put local symbols in groups starting with the STT_FILE2203// symbol. That is convenient for purpose of identifying where are local symbols2204// coming from.2205void SymbolTableBaseSection::sortSymTabSymbols() {2206  // Move all local symbols before global symbols.2207  auto e = std::stable_partition(2208      symbols.begin(), symbols.end(),2209      [](const SymbolTableEntry &s) { return s.sym->isLocal(); });2210  size_t numLocals = e - symbols.begin();2211  getParent()->info = numLocals + 1;2212 2213  // We want to group the local symbols by file. For that we rebuild the local2214  // part of the symbols vector. We do not need to care about the STT_FILE2215  // symbols, they are already naturally placed first in each group. That2216  // happens because STT_FILE is always the first symbol in the object and hence2217  // precede all other local symbols we add for a file.2218  MapVector<InputFile *, SmallVector<SymbolTableEntry, 0>> arr;2219  for (const SymbolTableEntry &s : llvm::make_range(symbols.begin(), e))2220    arr[s.sym->file].push_back(s);2221 2222  auto i = symbols.begin();2223  for (auto &p : arr)2224    for (SymbolTableEntry &entry : p.second)2225      *i++ = entry;2226}2227 2228void SymbolTableBaseSection::addSymbol(Symbol *b) {2229  // Adding a local symbol to a .dynsym is a bug.2230  assert(this->type != SHT_DYNSYM || !b->isLocal());2231  symbols.push_back({b, strTabSec.addString(b->getName(), false)});2232}2233 2234size_t SymbolTableBaseSection::getSymbolIndex(const Symbol &sym) {2235  if (this == ctx.mainPart->dynSymTab.get())2236    return sym.dynsymIndex;2237 2238  // Initializes symbol lookup tables lazily. This is used only for -r,2239  // --emit-relocs and dynsyms in partitions other than the main one.2240  llvm::call_once(onceFlag, [&] {2241    symbolIndexMap.reserve(symbols.size());2242    size_t i = 0;2243    for (const SymbolTableEntry &e : symbols) {2244      if (e.sym->type == STT_SECTION)2245        sectionIndexMap[e.sym->getOutputSection()] = ++i;2246      else2247        symbolIndexMap[e.sym] = ++i;2248    }2249  });2250 2251  // Section symbols are mapped based on their output sections2252  // to maintain their semantics.2253  if (sym.type == STT_SECTION)2254    return sectionIndexMap.lookup(sym.getOutputSection());2255  return symbolIndexMap.lookup(&sym);2256}2257 2258template <class ELFT>2259SymbolTableSection<ELFT>::SymbolTableSection(Ctx &ctx,2260                                             StringTableSection &strTabSec)2261    : SymbolTableBaseSection(ctx, strTabSec) {2262  this->entsize = sizeof(Elf_Sym);2263}2264 2265static BssSection *getCommonSec(bool relocatable, Symbol *sym) {2266  if (relocatable)2267    if (auto *d = dyn_cast<Defined>(sym))2268      return dyn_cast_or_null<BssSection>(d->section);2269  return nullptr;2270}2271 2272static uint32_t getSymSectionIndex(Symbol *sym) {2273  assert(!(sym->hasFlag(NEEDS_COPY) && sym->isObject()));2274  if (!isa<Defined>(sym) || sym->hasFlag(NEEDS_COPY))2275    return SHN_UNDEF;2276  if (const OutputSection *os = sym->getOutputSection())2277    return os->sectionIndex >= SHN_LORESERVE ? (uint32_t)SHN_XINDEX2278                                             : os->sectionIndex;2279  return SHN_ABS;2280}2281 2282// Write the internal symbol table contents to the output symbol table.2283template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *buf) {2284  // The first entry is a null entry as per the ELF spec.2285  buf += sizeof(Elf_Sym);2286 2287  auto *eSym = reinterpret_cast<Elf_Sym *>(buf);2288  bool relocatable = ctx.arg.relocatable;2289  for (SymbolTableEntry &ent : symbols) {2290    Symbol *sym = ent.sym;2291    bool isDefinedHere = type == SHT_SYMTAB || sym->partition == partition;2292 2293    // Set st_name, st_info and st_other.2294    eSym->st_name = ent.strTabOffset;2295    eSym->setBindingAndType(sym->binding, sym->type);2296    eSym->st_other = sym->stOther;2297 2298    if (BssSection *commonSec = getCommonSec(relocatable, sym)) {2299      // When -r is specified, a COMMON symbol is not allocated. Its st_shndx2300      // holds SHN_COMMON and st_value holds the alignment.2301      eSym->st_shndx = SHN_COMMON;2302      eSym->st_value = commonSec->addralign;2303      eSym->st_size = cast<Defined>(sym)->size;2304    } else {2305      const uint32_t shndx = getSymSectionIndex(sym);2306      if (isDefinedHere) {2307        eSym->st_shndx = shndx;2308        eSym->st_value = sym->getVA(ctx);2309        // Copy symbol size if it is a defined symbol. st_size is not2310        // significant for undefined symbols, so whether copying it or not is up2311        // to us if that's the case. We'll leave it as zero because by not2312        // setting a value, we can get the exact same outputs for two sets of2313        // input files that differ only in undefined symbol size in DSOs.2314        eSym->st_size = shndx != SHN_UNDEF ? cast<Defined>(sym)->size : 0;2315      } else {2316        eSym->st_shndx = 0;2317        eSym->st_value = 0;2318        eSym->st_size = 0;2319      }2320    }2321 2322    ++eSym;2323  }2324 2325  // On MIPS we need to mark symbol which has a PLT entry and requires2326  // pointer equality by STO_MIPS_PLT flag. That is necessary to help2327  // dynamic linker distinguish such symbols and MIPS lazy-binding stubs.2328  // https://sourceware.org/ml/binutils/2008-07/txt00000.txt2329  if (ctx.arg.emachine == EM_MIPS) {2330    auto *eSym = reinterpret_cast<Elf_Sym *>(buf);2331 2332    for (SymbolTableEntry &ent : symbols) {2333      Symbol *sym = ent.sym;2334      if (sym->isInPlt(ctx) && sym->hasFlag(NEEDS_COPY))2335        eSym->st_other |= STO_MIPS_PLT;2336      if (isMicroMips(ctx)) {2337        // We already set the less-significant bit for symbols2338        // marked by the `STO_MIPS_MICROMIPS` flag and for microMIPS PLT2339        // records. That allows us to distinguish such symbols in2340        // the `MIPS<ELFT>::relocate()` routine. Now we should2341        // clear that bit for non-dynamic symbol table, so tools2342        // like `objdump` will be able to deal with a correct2343        // symbol position.2344        if (sym->isDefined() &&2345            ((sym->stOther & STO_MIPS_MICROMIPS) || sym->hasFlag(NEEDS_COPY))) {2346          if (!strTabSec.isDynamic())2347            eSym->st_value &= ~1;2348          eSym->st_other |= STO_MIPS_MICROMIPS;2349        }2350      }2351      if (ctx.arg.relocatable)2352        if (auto *d = dyn_cast<Defined>(sym))2353          if (isMipsPIC<ELFT>(d))2354            eSym->st_other |= STO_MIPS_PIC;2355      ++eSym;2356    }2357  }2358}2359 2360SymtabShndxSection::SymtabShndxSection(Ctx &ctx)2361    : SyntheticSection(ctx, ".symtab_shndx", SHT_SYMTAB_SHNDX, 0, 4) {2362  this->entsize = 4;2363}2364 2365void SymtabShndxSection::writeTo(uint8_t *buf) {2366  // We write an array of 32 bit values, where each value has 1:1 association2367  // with an entry in ctx.in.symTab if the corresponding entry contains2368  // SHN_XINDEX, we need to write actual index, otherwise, we must write2369  // SHN_UNDEF(0).2370  buf += 4; // Ignore .symtab[0] entry.2371  bool relocatable = ctx.arg.relocatable;2372  for (const SymbolTableEntry &entry : ctx.in.symTab->getSymbols()) {2373    if (!getCommonSec(relocatable, entry.sym) &&2374        getSymSectionIndex(entry.sym) == SHN_XINDEX)2375      write32(ctx, buf, entry.sym->getOutputSection()->sectionIndex);2376    buf += 4;2377  }2378}2379 2380bool SymtabShndxSection::isNeeded() const {2381  // SHT_SYMTAB can hold symbols with section indices values up to2382  // SHN_LORESERVE. If we need more, we want to use extension SHT_SYMTAB_SHNDX2383  // section. Problem is that we reveal the final section indices a bit too2384  // late, and we do not know them here. For simplicity, we just always create2385  // a .symtab_shndx section when the amount of output sections is huge.2386  size_t size = 0;2387  for (SectionCommand *cmd : ctx.script->sectionCommands)2388    if (isa<OutputDesc>(cmd))2389      ++size;2390  return size >= SHN_LORESERVE;2391}2392 2393void SymtabShndxSection::finalizeContents() {2394  getParent()->link = ctx.in.symTab->getParent()->sectionIndex;2395}2396 2397size_t SymtabShndxSection::getSize() const {2398  return ctx.in.symTab->getNumSymbols() * 4;2399}2400 2401// .hash and .gnu.hash sections contain on-disk hash tables that map2402// symbol names to their dynamic symbol table indices. Their purpose2403// is to help the dynamic linker resolve symbols quickly. If ELF files2404// don't have them, the dynamic linker has to do linear search on all2405// dynamic symbols, which makes programs slower. Therefore, a .hash2406// section is added to a DSO by default.2407//2408// The Unix semantics of resolving dynamic symbols is somewhat expensive.2409// Each ELF file has a list of DSOs that the ELF file depends on and a2410// list of dynamic symbols that need to be resolved from any of the2411// DSOs. That means resolving all dynamic symbols takes O(m)*O(n)2412// where m is the number of DSOs and n is the number of dynamic2413// symbols. For modern large programs, both m and n are large.  So2414// making each step faster by using hash tables substantially2415// improves time to load programs.2416//2417// (Note that this is not the only way to design the shared library.2418// For instance, the Windows DLL takes a different approach. On2419// Windows, each dynamic symbol has a name of DLL from which the symbol2420// has to be resolved. That makes the cost of symbol resolution O(n).2421// This disables some hacky techniques you can use on Unix such as2422// LD_PRELOAD, but this is arguably better semantics than the Unix ones.)2423//2424// Due to historical reasons, we have two different hash tables, .hash2425// and .gnu.hash. They are for the same purpose, and .gnu.hash is a new2426// and better version of .hash. .hash is just an on-disk hash table, but2427// .gnu.hash has a bloom filter in addition to a hash table to skip2428// DSOs very quickly. If you are sure that your dynamic linker knows2429// about .gnu.hash, you want to specify --hash-style=gnu. Otherwise, a2430// safe bet is to specify --hash-style=both for backward compatibility.2431GnuHashTableSection::GnuHashTableSection(Ctx &ctx)2432    : SyntheticSection(ctx, ".gnu.hash", SHT_GNU_HASH, SHF_ALLOC,2433                       ctx.arg.wordsize) {}2434 2435void GnuHashTableSection::finalizeContents() {2436  if (OutputSection *sec = getPartition(ctx).dynSymTab->getParent())2437    getParent()->link = sec->sectionIndex;2438 2439  // Computes bloom filter size in word size. We want to allocate 122440  // bits for each symbol. It must be a power of two.2441  if (symbols.empty()) {2442    maskWords = 1;2443  } else {2444    uint64_t numBits = symbols.size() * 12;2445    maskWords = NextPowerOf2(numBits / (ctx.arg.wordsize * 8));2446  }2447 2448  size = 16;                            // Header2449  size += ctx.arg.wordsize * maskWords; // Bloom filter2450  size += nBuckets * 4;                 // Hash buckets2451  size += symbols.size() * 4;           // Hash values2452}2453 2454void GnuHashTableSection::writeTo(uint8_t *buf) {2455  // Write a header.2456  write32(ctx, buf, nBuckets);2457  write32(ctx, buf + 4,2458          getPartition(ctx).dynSymTab->getNumSymbols() - symbols.size());2459  write32(ctx, buf + 8, maskWords);2460  write32(ctx, buf + 12, Shift2);2461  buf += 16;2462 2463  // Write the 2-bit bloom filter.2464  const unsigned c = ctx.arg.is64 ? 64 : 32;2465  for (const Entry &sym : symbols) {2466    // When C = 64, we choose a word with bits [6:...] and set 1 to two bits in2467    // the word using bits [0:5] and [26:31].2468    size_t i = (sym.hash / c) & (maskWords - 1);2469    uint64_t val = readUint(ctx, buf + i * ctx.arg.wordsize);2470    val |= uint64_t(1) << (sym.hash % c);2471    val |= uint64_t(1) << ((sym.hash >> Shift2) % c);2472    writeUint(ctx, buf + i * ctx.arg.wordsize, val);2473  }2474  buf += ctx.arg.wordsize * maskWords;2475 2476  // Write the hash table.2477  uint32_t *buckets = reinterpret_cast<uint32_t *>(buf);2478  uint32_t oldBucket = -1;2479  uint32_t *values = buckets + nBuckets;2480  for (auto i = symbols.begin(), e = symbols.end(); i != e; ++i) {2481    // Write a hash value. It represents a sequence of chains that share the2482    // same hash modulo value. The last element of each chain is terminated by2483    // LSB 1.2484    uint32_t hash = i->hash;2485    bool isLastInChain = (i + 1) == e || i->bucketIdx != (i + 1)->bucketIdx;2486    hash = isLastInChain ? hash | 1 : hash & ~1;2487    write32(ctx, values++, hash);2488 2489    if (i->bucketIdx == oldBucket)2490      continue;2491    // Write a hash bucket. Hash buckets contain indices in the following hash2492    // value table.2493    write32(ctx, buckets + i->bucketIdx,2494            getPartition(ctx).dynSymTab->getSymbolIndex(*i->sym));2495    oldBucket = i->bucketIdx;2496  }2497}2498 2499// Add symbols to this symbol hash table. Note that this function2500// destructively sort a given vector -- which is needed because2501// GNU-style hash table places some sorting requirements.2502void GnuHashTableSection::addSymbols(SmallVectorImpl<SymbolTableEntry> &v) {2503  // We cannot use 'auto' for Mid because GCC 6.1 cannot deduce2504  // its type correctly.2505  auto mid =2506      std::stable_partition(v.begin(), v.end(), [&](const SymbolTableEntry &s) {2507        return !s.sym->isDefined() || s.sym->partition != partition;2508      });2509 2510  // We chose load factor 4 for the on-disk hash table. For each hash2511  // collision, the dynamic linker will compare a uint32_t hash value.2512  // Since the integer comparison is quite fast, we believe we can2513  // make the load factor even larger. 4 is just a conservative choice.2514  //2515  // Note that we don't want to create a zero-sized hash table because2516  // Android loader as of 2018 doesn't like a .gnu.hash containing such2517  // table. If that's the case, we create a hash table with one unused2518  // dummy slot.2519  nBuckets = std::max<size_t>((v.end() - mid) / 4, 1);2520 2521  if (mid == v.end())2522    return;2523 2524  for (SymbolTableEntry &ent : llvm::make_range(mid, v.end())) {2525    Symbol *b = ent.sym;2526    uint32_t hash = hashGnu(b->getName());2527    uint32_t bucketIdx = hash % nBuckets;2528    symbols.push_back({b, ent.strTabOffset, hash, bucketIdx});2529  }2530 2531  llvm::sort(symbols, [](const Entry &l, const Entry &r) {2532    return std::tie(l.bucketIdx, l.strTabOffset) <2533           std::tie(r.bucketIdx, r.strTabOffset);2534  });2535 2536  v.erase(mid, v.end());2537  for (const Entry &ent : symbols)2538    v.push_back({ent.sym, ent.strTabOffset});2539}2540 2541HashTableSection::HashTableSection(Ctx &ctx)2542    : SyntheticSection(ctx, ".hash", SHT_HASH, SHF_ALLOC, 4) {2543  this->entsize = 4;2544}2545 2546void HashTableSection::finalizeContents() {2547  SymbolTableBaseSection *symTab = getPartition(ctx).dynSymTab.get();2548 2549  if (OutputSection *sec = symTab->getParent())2550    getParent()->link = sec->sectionIndex;2551 2552  unsigned numEntries = 2;               // nbucket and nchain.2553  numEntries += symTab->getNumSymbols(); // The chain entries.2554 2555  // Create as many buckets as there are symbols.2556  numEntries += symTab->getNumSymbols();2557  this->size = numEntries * 4;2558}2559 2560void HashTableSection::writeTo(uint8_t *buf) {2561  SymbolTableBaseSection *symTab = getPartition(ctx).dynSymTab.get();2562  unsigned numSymbols = symTab->getNumSymbols();2563 2564  uint32_t *p = reinterpret_cast<uint32_t *>(buf);2565  write32(ctx, p++, numSymbols); // nbucket2566  write32(ctx, p++, numSymbols); // nchain2567 2568  uint32_t *buckets = p;2569  uint32_t *chains = p + numSymbols;2570 2571  for (const SymbolTableEntry &s : symTab->getSymbols()) {2572    Symbol *sym = s.sym;2573    StringRef name = sym->getName();2574    unsigned i = sym->dynsymIndex;2575    uint32_t hash = hashSysV(name) % numSymbols;2576    chains[i] = buckets[hash];2577    write32(ctx, buckets + hash, i);2578  }2579}2580 2581PltSection::PltSection(Ctx &ctx)2582    : SyntheticSection(ctx, ".plt", SHT_PROGBITS, SHF_ALLOC | SHF_EXECINSTR,2583                       16),2584      headerSize(ctx.target->pltHeaderSize) {2585  // On AArch64, PLT entries only do loads from the .got.plt section, so the2586  // .plt section can be marked with the SHF_AARCH64_PURECODE section flag.2587  if (ctx.arg.emachine == EM_AARCH64)2588    this->flags |= SHF_AARCH64_PURECODE;2589 2590  // On PowerPC, this section contains lazy symbol resolvers.2591  if (ctx.arg.emachine == EM_PPC64) {2592    name = ".glink";2593    addralign = 4;2594  }2595 2596  // On x86 when IBT is enabled, this section contains the second PLT (lazy2597  // symbol resolvers).2598  if ((ctx.arg.emachine == EM_386 || ctx.arg.emachine == EM_X86_64) &&2599      (ctx.arg.andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT))2600    name = ".plt.sec";2601 2602  // The PLT needs to be writable on SPARC as the dynamic linker will2603  // modify the instructions in the PLT entries.2604  if (ctx.arg.emachine == EM_SPARCV9)2605    this->flags |= SHF_WRITE;2606}2607 2608void PltSection::writeTo(uint8_t *buf) {2609  // At beginning of PLT, we have code to call the dynamic2610  // linker to resolve dynsyms at runtime. Write such code.2611  ctx.target->writePltHeader(buf);2612  size_t off = headerSize;2613 2614  for (const Symbol *sym : entries) {2615    ctx.target->writePlt(buf + off, *sym, getVA() + off);2616    off += ctx.target->pltEntrySize;2617  }2618}2619 2620void PltSection::addEntry(Symbol &sym) {2621  assert(sym.auxIdx == ctx.symAux.size() - 1);2622  ctx.symAux.back().pltIdx = entries.size();2623  entries.push_back(&sym);2624}2625 2626size_t PltSection::getSize() const {2627  return headerSize + entries.size() * ctx.target->pltEntrySize;2628}2629 2630bool PltSection::isNeeded() const {2631  // For -z retpolineplt, .iplt needs the .plt header.2632  return !entries.empty() || (ctx.arg.zRetpolineplt && ctx.in.iplt->isNeeded());2633}2634 2635// Used by ARM to add mapping symbols in the PLT section, which aid2636// disassembly.2637void PltSection::addSymbols() {2638  ctx.target->addPltHeaderSymbols(*this);2639 2640  size_t off = headerSize;2641  for (size_t i = 0; i < entries.size(); ++i) {2642    ctx.target->addPltSymbols(*this, off);2643    off += ctx.target->pltEntrySize;2644  }2645}2646 2647IpltSection::IpltSection(Ctx &ctx)2648    : SyntheticSection(ctx, ".iplt", SHT_PROGBITS, SHF_ALLOC | SHF_EXECINSTR,2649                       16) {2650  // On AArch64, PLT entries only do loads from the .got.plt section, so the2651  // .iplt section can be marked with the SHF_AARCH64_PURECODE section flag.2652  if (ctx.arg.emachine == EM_AARCH64)2653    this->flags |= SHF_AARCH64_PURECODE;2654 2655  if (ctx.arg.emachine == EM_PPC || ctx.arg.emachine == EM_PPC64) {2656    name = ".glink";2657    addralign = 4;2658  }2659}2660 2661void IpltSection::writeTo(uint8_t *buf) {2662  uint32_t off = 0;2663  for (const Symbol *sym : entries) {2664    ctx.target->writeIplt(buf + off, *sym, getVA() + off);2665    off += ctx.target->ipltEntrySize;2666  }2667}2668 2669size_t IpltSection::getSize() const {2670  return entries.size() * ctx.target->ipltEntrySize;2671}2672 2673void IpltSection::addEntry(Symbol &sym) {2674  assert(sym.auxIdx == ctx.symAux.size() - 1);2675  ctx.symAux.back().pltIdx = entries.size();2676  entries.push_back(&sym);2677}2678 2679// ARM uses mapping symbols to aid disassembly.2680void IpltSection::addSymbols() {2681  size_t off = 0;2682  for (size_t i = 0, e = entries.size(); i != e; ++i) {2683    ctx.target->addPltSymbols(*this, off);2684    off += ctx.target->pltEntrySize;2685  }2686}2687 2688PPC32GlinkSection::PPC32GlinkSection(Ctx &ctx) : PltSection(ctx) {2689  name = ".glink";2690  addralign = 4;2691}2692 2693void PPC32GlinkSection::writeTo(uint8_t *buf) {2694  writePPC32GlinkSection(ctx, buf, entries.size());2695}2696 2697size_t PPC32GlinkSection::getSize() const {2698  return headerSize + entries.size() * ctx.target->pltEntrySize + footerSize;2699}2700 2701// This is an x86-only extra PLT section and used only when a security2702// enhancement feature called CET is enabled. In this comment, I'll explain what2703// the feature is and why we have two PLT sections if CET is enabled.2704//2705// So, what does CET do? CET introduces a new restriction to indirect jump2706// instructions. CET works this way. Assume that CET is enabled. Then, if you2707// execute an indirect jump instruction, the processor verifies that a special2708// "landing pad" instruction (which is actually a repurposed NOP instruction and2709// now called "endbr32" or "endbr64") is at the jump target. If the jump target2710// does not start with that instruction, the processor raises an exception2711// instead of continuing executing code.2712//2713// If CET is enabled, the compiler emits endbr to all locations where indirect2714// jumps may jump to.2715//2716// This mechanism makes it extremely hard to transfer the control to a middle of2717// a function that is not supporsed to be a indirect jump target, preventing2718// certain types of attacks such as ROP or JOP.2719//2720// Note that the processors in the market as of 2019 don't actually support the2721// feature. Only the spec is available at the moment.2722//2723// Now, I'll explain why we have this extra PLT section for CET.2724//2725// Since you can indirectly jump to a PLT entry, we have to make PLT entries2726// start with endbr. The problem is there's no extra space for endbr (which is 42727// bytes long), as the PLT entry is only 16 bytes long and all bytes are already2728// used.2729//2730// In order to deal with the issue, we split a PLT entry into two PLT entries.2731// Remember that each PLT entry contains code to jump to an address read from2732// .got.plt AND code to resolve a dynamic symbol lazily. With the 2-PLT scheme,2733// the former code is written to .plt.sec, and the latter code is written to2734// .plt.2735//2736// Lazy symbol resolution in the 2-PLT scheme works in the usual way, except2737// that the regular .plt is now called .plt.sec and .plt is repurposed to2738// contain only code for lazy symbol resolution.2739//2740// In other words, this is how the 2-PLT scheme works. Application code is2741// supposed to jump to .plt.sec to call an external function. Each .plt.sec2742// entry contains code to read an address from a corresponding .got.plt entry2743// and jump to that address. Addresses in .got.plt initially point to .plt, so2744// when an application calls an external function for the first time, the2745// control is transferred to a function that resolves a symbol name from2746// external shared object files. That function then rewrites a .got.plt entry2747// with a resolved address, so that the subsequent function calls directly jump2748// to a desired location from .plt.sec.2749//2750// There is an open question as to whether the 2-PLT scheme was desirable or2751// not. We could have simply extended the PLT entry size to 32-bytes to2752// accommodate endbr, and that scheme would have been much simpler than the2753// 2-PLT scheme. One reason to split PLT was, by doing that, we could keep hot2754// code (.plt.sec) from cold code (.plt). But as far as I know no one proved2755// that the optimization actually makes a difference.2756//2757// That said, the 2-PLT scheme is a part of the ABI, debuggers and other tools2758// depend on it, so we implement the ABI.2759IBTPltSection::IBTPltSection(Ctx &ctx)2760    : SyntheticSection(ctx, ".plt", SHT_PROGBITS, SHF_ALLOC | SHF_EXECINSTR,2761                       16) {}2762 2763void IBTPltSection::writeTo(uint8_t *buf) {2764  ctx.target->writeIBTPlt(buf, ctx.in.plt->getNumEntries());2765}2766 2767size_t IBTPltSection::getSize() const {2768  // 16 is the header size of .plt.2769  return 16 + ctx.in.plt->getNumEntries() * ctx.target->pltEntrySize;2770}2771 2772bool IBTPltSection::isNeeded() const { return ctx.in.plt->getNumEntries() > 0; }2773 2774RelroPaddingSection::RelroPaddingSection(Ctx &ctx)2775    : SyntheticSection(ctx, ".relro_padding", SHT_NOBITS, SHF_ALLOC | SHF_WRITE,2776                       1) {}2777 2778PaddingSection::PaddingSection(Ctx &ctx, uint64_t amount, OutputSection *parent)2779    : SyntheticSection(ctx, ".padding", SHT_PROGBITS, SHF_ALLOC, 1) {2780  size = amount;2781  this->parent = parent;2782}2783 2784void PaddingSection::writeTo(uint8_t *buf) {2785  std::array<uint8_t, 4> filler = getParent()->getFiller(ctx);2786  uint8_t *end = buf + size;2787  for (; buf + 4 <= end; buf += 4)2788    memcpy(buf, &filler[0], 4);2789  memcpy(buf, &filler[0], end - buf);2790}2791 2792// The string hash function for .gdb_index.2793static uint32_t computeGdbHash(StringRef s) {2794  uint32_t h = 0;2795  for (uint8_t c : s)2796    h = h * 67 + toLower(c) - 113;2797  return h;2798}2799 2800// 4-byte alignment ensures that values in the hash lookup table and the name2801// table are aligned.2802DebugNamesBaseSection::DebugNamesBaseSection(Ctx &ctx)2803    : SyntheticSection(ctx, ".debug_names", SHT_PROGBITS, 0, 4) {}2804 2805// Get the size of the .debug_names section header in bytes for DWARF32:2806static uint32_t getDebugNamesHeaderSize(uint32_t augmentationStringSize) {2807  return /* unit length */ 4 +2808         /* version */ 2 +2809         /* padding */ 2 +2810         /* CU count */ 4 +2811         /* TU count */ 4 +2812         /* Foreign TU count */ 4 +2813         /* Bucket Count */ 4 +2814         /* Name Count */ 4 +2815         /* Abbrev table size */ 4 +2816         /* Augmentation string size */ 4 +2817         /* Augmentation string */ augmentationStringSize;2818}2819 2820static Expected<DebugNamesBaseSection::IndexEntry *>2821readEntry(uint64_t &offset, const DWARFDebugNames::NameIndex &ni,2822          uint64_t entriesBase, DWARFDataExtractor &namesExtractor,2823          const LLDDWARFSection &namesSec) {2824  auto ie = makeThreadLocal<DebugNamesBaseSection::IndexEntry>();2825  ie->poolOffset = offset;2826  Error err = Error::success();2827  uint64_t ulebVal = namesExtractor.getULEB128(&offset, &err);2828  if (err)2829    return createStringError(inconvertibleErrorCode(),2830                             "invalid abbrev code: %s",2831                             llvm::toString(std::move(err)).c_str());2832  if (!isUInt<32>(ulebVal))2833    return createStringError(inconvertibleErrorCode(),2834                             "abbrev code too large for DWARF32: %" PRIu64,2835                             ulebVal);2836  ie->abbrevCode = static_cast<uint32_t>(ulebVal);2837  auto it = ni.getAbbrevs().find_as(ie->abbrevCode);2838  if (it == ni.getAbbrevs().end())2839    return createStringError(inconvertibleErrorCode(),2840                             "abbrev code not found in abbrev table: %" PRIu32,2841                             ie->abbrevCode);2842 2843  DebugNamesBaseSection::AttrValue attr, cuAttr = {0, 0};2844  for (DWARFDebugNames::AttributeEncoding a : it->Attributes) {2845    if (a.Index == dwarf::DW_IDX_parent) {2846      if (a.Form == dwarf::DW_FORM_ref4) {2847        attr.attrValue = namesExtractor.getU32(&offset, &err);2848        attr.attrSize = 4;2849        ie->parentOffset = entriesBase + attr.attrValue;2850      } else if (a.Form != DW_FORM_flag_present)2851        return createStringError(inconvertibleErrorCode(),2852                                 "invalid form for DW_IDX_parent");2853    } else {2854      switch (a.Form) {2855      case DW_FORM_data1:2856      case DW_FORM_ref1: {2857        attr.attrValue = namesExtractor.getU8(&offset, &err);2858        attr.attrSize = 1;2859        break;2860      }2861      case DW_FORM_data2:2862      case DW_FORM_ref2: {2863        attr.attrValue = namesExtractor.getU16(&offset, &err);2864        attr.attrSize = 2;2865        break;2866      }2867      case DW_FORM_data4:2868      case DW_FORM_ref4: {2869        attr.attrValue = namesExtractor.getU32(&offset, &err);2870        attr.attrSize = 4;2871        break;2872      }2873      default:2874        return createStringError(2875            inconvertibleErrorCode(),2876            "unrecognized form encoding %d in abbrev table", a.Form);2877      }2878    }2879    if (err)2880      return createStringError(inconvertibleErrorCode(),2881                               "error while reading attributes: %s",2882                               llvm::toString(std::move(err)).c_str());2883    if (a.Index == DW_IDX_compile_unit)2884      cuAttr = attr;2885    else if (a.Form != DW_FORM_flag_present)2886      ie->attrValues.push_back(attr);2887  }2888  // Canonicalize abbrev by placing the CU/TU index at the end.2889  ie->attrValues.push_back(cuAttr);2890  return ie;2891}2892 2893void DebugNamesBaseSection::parseDebugNames(2894    Ctx &ctx, InputChunk &inputChunk, OutputChunk &chunk,2895    DWARFDataExtractor &namesExtractor, DataExtractor &strExtractor,2896    function_ref<SmallVector<uint32_t, 0>(2897        uint32_t numCus, const DWARFDebugNames::Header &,2898        const DWARFDebugNames::DWARFDebugNamesOffsets &)>2899        readOffsets) {2900  const LLDDWARFSection &namesSec = inputChunk.section;2901  DenseMap<uint32_t, IndexEntry *> offsetMap;2902  // Number of CUs seen in previous NameIndex sections within current chunk.2903  uint32_t numCus = 0;2904  for (const DWARFDebugNames::NameIndex &ni : *inputChunk.llvmDebugNames) {2905    NameData &nd = inputChunk.nameData.emplace_back();2906    nd.hdr = ni.getHeader();2907    if (nd.hdr.Format != DwarfFormat::DWARF32) {2908      Err(ctx) << namesSec.sec2909               << ": found DWARF64, which is currently unsupported";2910      return;2911    }2912    if (nd.hdr.Version != 5) {2913      Err(ctx) << namesSec.sec << ": unsupported version: " << nd.hdr.Version;2914      return;2915    }2916    uint32_t dwarfSize = dwarf::getDwarfOffsetByteSize(DwarfFormat::DWARF32);2917    DWARFDebugNames::DWARFDebugNamesOffsets locs = ni.getOffsets();2918    if (locs.EntriesBase > namesExtractor.getData().size()) {2919      Err(ctx) << namesSec.sec << ": entry pool start is beyond end of section";2920      return;2921    }2922 2923    SmallVector<uint32_t, 0> entryOffsets = readOffsets(numCus, nd.hdr, locs);2924 2925    // Read the entry pool.2926    offsetMap.clear();2927    nd.nameEntries.resize(nd.hdr.NameCount);2928    for (auto i : seq(nd.hdr.NameCount)) {2929      NameEntry &ne = nd.nameEntries[i];2930      uint64_t strOffset = locs.StringOffsetsBase + i * dwarfSize;2931      ne.stringOffset = strOffset;2932      uint64_t strp = namesExtractor.getRelocatedValue(dwarfSize, &strOffset);2933      StringRef name = strExtractor.getCStrRef(&strp);2934      ne.name = name.data();2935      ne.hashValue = caseFoldingDjbHash(name);2936 2937      // Read a series of index entries that end with abbreviation code 0.2938      uint64_t offset = locs.EntriesBase + entryOffsets[i];2939      while (offset < namesSec.Data.size() && namesSec.Data[offset] != 0) {2940        // Read & store all entries (for the same string).2941        Expected<IndexEntry *> ieOrErr =2942            readEntry(offset, ni, locs.EntriesBase, namesExtractor, namesSec);2943        if (!ieOrErr) {2944          Err(ctx) << namesSec.sec << ": " << ieOrErr.takeError();2945          return;2946        }2947        ne.indexEntries.push_back(std::move(*ieOrErr));2948      }2949      if (offset >= namesSec.Data.size())2950        Err(ctx) << namesSec.sec << ": index entry is out of bounds";2951 2952      for (IndexEntry &ie : ne.entries())2953        offsetMap[ie.poolOffset] = &ie;2954    }2955 2956    // Assign parent pointers, which will be used to update DW_IDX_parent index2957    // attributes. Note: offsetMap[0] does not exist, so parentOffset == 0 will2958    // get parentEntry == null as well.2959    for (NameEntry &ne : nd.nameEntries)2960      for (IndexEntry &ie : ne.entries())2961        ie.parentEntry = offsetMap.lookup(ie.parentOffset);2962    numCus += nd.hdr.CompUnitCount;2963  }2964}2965 2966// Compute the form for output DW_IDX_compile_unit attributes, similar to2967// DIEInteger::BestForm. The input form (often DW_FORM_data1) may not hold all2968// the merged CU indices.2969std::pair<uint8_t, dwarf::Form> static getMergedCuCountForm(2970    uint32_t compUnitCount) {2971  if (compUnitCount > UINT16_MAX)2972    return {4, DW_FORM_data4};2973  if (compUnitCount > UINT8_MAX)2974    return {2, DW_FORM_data2};2975  return {1, DW_FORM_data1};2976}2977 2978void DebugNamesBaseSection::computeHdrAndAbbrevTable(2979    MutableArrayRef<InputChunk> inputChunks) {2980  TimeTraceScope timeScope("Merge .debug_names", "hdr and abbrev table");2981  size_t numCu = 0;2982  hdr.Format = DwarfFormat::DWARF32;2983  hdr.Version = 5;2984  hdr.CompUnitCount = 0;2985  hdr.LocalTypeUnitCount = 0;2986  hdr.ForeignTypeUnitCount = 0;2987  hdr.AugmentationStringSize = 0;2988 2989  // Compute CU and TU counts.2990  for (auto i : seq(numChunks)) {2991    InputChunk &inputChunk = inputChunks[i];2992    inputChunk.baseCuIdx = numCu;2993    numCu += chunks[i].compUnits.size();2994    for (const NameData &nd : inputChunk.nameData) {2995      hdr.CompUnitCount += nd.hdr.CompUnitCount;2996      // TODO: We don't handle type units yet, so LocalTypeUnitCount &2997      // ForeignTypeUnitCount are left as 0.2998      if (nd.hdr.LocalTypeUnitCount || nd.hdr.ForeignTypeUnitCount)2999        Warn(ctx) << inputChunk.section.sec3000                  << ": type units are not implemented";3001      // If augmentation strings are not identical, use an empty string.3002      if (i == 0) {3003        hdr.AugmentationStringSize = nd.hdr.AugmentationStringSize;3004        hdr.AugmentationString = nd.hdr.AugmentationString;3005      } else if (hdr.AugmentationString != nd.hdr.AugmentationString) {3006        // There are conflicting augmentation strings, so it's best for the3007        // merged index to not use an augmentation string.3008        hdr.AugmentationStringSize = 0;3009        hdr.AugmentationString.clear();3010      }3011    }3012  }3013 3014  // Create the merged abbrev table, uniquifyinng the input abbrev tables and3015  // computing mapping from old (per-cu) abbrev codes to new (merged) abbrev3016  // codes.3017  FoldingSet<Abbrev> abbrevSet;3018  // Determine the form for the DW_IDX_compile_unit attributes in the merged3019  // index. The input form may not be big enough for all CU indices.3020  dwarf::Form cuAttrForm = getMergedCuCountForm(hdr.CompUnitCount).second;3021  for (InputChunk &inputChunk : inputChunks) {3022    for (auto [i, ni] : enumerate(*inputChunk.llvmDebugNames)) {3023      for (const DWARFDebugNames::Abbrev &oldAbbrev : ni.getAbbrevs()) {3024        // Canonicalize abbrev by placing the CU/TU index at the end,3025        // similar to 'parseDebugNames'.3026        Abbrev abbrev;3027        DWARFDebugNames::AttributeEncoding cuAttr(DW_IDX_compile_unit,3028                                                  cuAttrForm);3029        abbrev.code = oldAbbrev.Code;3030        abbrev.tag = oldAbbrev.Tag;3031        for (DWARFDebugNames::AttributeEncoding a : oldAbbrev.Attributes) {3032          if (a.Index == DW_IDX_compile_unit)3033            cuAttr.Index = a.Index;3034          else3035            abbrev.attributes.push_back({a.Index, a.Form});3036        }3037        // Put the CU/TU index at the end of the attributes list.3038        abbrev.attributes.push_back(cuAttr);3039 3040        // Profile the abbrev, get or assign a new code, then record the abbrev3041        // code mapping.3042        FoldingSetNodeID id;3043        abbrev.Profile(id);3044        uint32_t newCode;3045        void *insertPos;3046        if (Abbrev *existing = abbrevSet.FindNodeOrInsertPos(id, insertPos)) {3047          // Found it; we've already seen an identical abbreviation.3048          newCode = existing->code;3049        } else {3050          Abbrev *abbrev2 =3051              new (abbrevAlloc.Allocate()) Abbrev(std::move(abbrev));3052          abbrevSet.InsertNode(abbrev2, insertPos);3053          abbrevTable.push_back(abbrev2);3054          newCode = abbrevTable.size();3055          abbrev2->code = newCode;3056        }3057        inputChunk.nameData[i].abbrevCodeMap[oldAbbrev.Code] = newCode;3058      }3059    }3060  }3061 3062  // Compute the merged abbrev table.3063  raw_svector_ostream os(abbrevTableBuf);3064  for (Abbrev *abbrev : abbrevTable) {3065    encodeULEB128(abbrev->code, os);3066    encodeULEB128(abbrev->tag, os);3067    for (DWARFDebugNames::AttributeEncoding a : abbrev->attributes) {3068      encodeULEB128(a.Index, os);3069      encodeULEB128(a.Form, os);3070    }3071    os.write("\0", 2); // attribute specification end3072  }3073  os.write(0); // abbrev table end3074  hdr.AbbrevTableSize = abbrevTableBuf.size();3075}3076 3077void DebugNamesBaseSection::Abbrev::Profile(FoldingSetNodeID &id) const {3078  id.AddInteger(tag);3079  for (const DWARFDebugNames::AttributeEncoding &attr : attributes) {3080    id.AddInteger(attr.Index);3081    id.AddInteger(attr.Form);3082  }3083}3084 3085std::pair<uint32_t, uint32_t> DebugNamesBaseSection::computeEntryPool(3086    MutableArrayRef<InputChunk> inputChunks) {3087  TimeTraceScope timeScope("Merge .debug_names", "entry pool");3088  // Collect and de-duplicate all the names (preserving all the entries).3089  // Speed it up using multithreading, as the number of symbols can be in the3090  // order of millions.3091  const size_t concurrency =3092      bit_floor(std::min<size_t>(ctx.arg.threadCount, numShards));3093  const size_t shift = 32 - countr_zero(numShards);3094  const uint8_t cuAttrSize = getMergedCuCountForm(hdr.CompUnitCount).first;3095  DenseMap<CachedHashStringRef, size_t> maps[numShards];3096 3097  parallelFor(0, concurrency, [&](size_t threadId) {3098    for (auto i : seq(numChunks)) {3099      InputChunk &inputChunk = inputChunks[i];3100      for (auto j : seq(inputChunk.nameData.size())) {3101        NameData &nd = inputChunk.nameData[j];3102        // Deduplicate the NameEntry records (based on the string/name),3103        // appending all IndexEntries from duplicate NameEntry records to3104        // the single preserved copy.3105        for (NameEntry &ne : nd.nameEntries) {3106          auto shardId = ne.hashValue >> shift;3107          if ((shardId & (concurrency - 1)) != threadId)3108            continue;3109 3110          ne.chunkIdx = i;3111          for (IndexEntry &ie : ne.entries()) {3112            // Update the IndexEntry's abbrev code to match the merged3113            // abbreviations.3114            ie.abbrevCode = nd.abbrevCodeMap[ie.abbrevCode];3115            // Update the DW_IDX_compile_unit attribute (the last one after3116            // canonicalization) to have correct merged offset value and size.3117            auto &back = ie.attrValues.back();3118            back.attrValue += inputChunk.baseCuIdx + j;3119            back.attrSize = cuAttrSize;3120          }3121 3122          auto &nameVec = nameVecs[shardId];3123          auto [it, inserted] = maps[shardId].try_emplace(3124              CachedHashStringRef(ne.name, ne.hashValue), nameVec.size());3125          if (inserted)3126            nameVec.push_back(std::move(ne));3127          else3128            nameVec[it->second].indexEntries.append(std::move(ne.indexEntries));3129        }3130      }3131    }3132  });3133 3134  // Compute entry offsets in parallel. First, compute offsets relative to the3135  // current shard.3136  uint32_t offsets[numShards];3137  parallelFor(0, numShards, [&](size_t shard) {3138    uint32_t offset = 0;3139    for (NameEntry &ne : nameVecs[shard]) {3140      ne.entryOffset = offset;3141      for (IndexEntry &ie : ne.entries()) {3142        ie.poolOffset = offset;3143        offset += getULEB128Size(ie.abbrevCode);3144        for (AttrValue value : ie.attrValues)3145          offset += value.attrSize;3146      }3147      ++offset; // index entry sentinel3148    }3149    offsets[shard] = offset;3150  });3151  // Then add shard offsets.3152  std::partial_sum(offsets, std::end(offsets), offsets);3153  parallelFor(1, numShards, [&](size_t shard) {3154    uint32_t offset = offsets[shard - 1];3155    for (NameEntry &ne : nameVecs[shard]) {3156      ne.entryOffset += offset;3157      for (IndexEntry &ie : ne.entries())3158        ie.poolOffset += offset;3159    }3160  });3161 3162  // Update the DW_IDX_parent entries that refer to real parents (have3163  // DW_FORM_ref4).3164  parallelFor(0, numShards, [&](size_t shard) {3165    for (NameEntry &ne : nameVecs[shard]) {3166      for (IndexEntry &ie : ne.entries()) {3167        if (!ie.parentEntry)3168          continue;3169        // Abbrevs are indexed starting at 1; vector starts at 0. (abbrevCode3170        // corresponds to position in the merged table vector).3171        const Abbrev *abbrev = abbrevTable[ie.abbrevCode - 1];3172        for (const auto &[a, v] : zip_equal(abbrev->attributes, ie.attrValues))3173          if (a.Index == DW_IDX_parent && a.Form == DW_FORM_ref4)3174            v.attrValue = ie.parentEntry->poolOffset;3175      }3176    }3177  });3178 3179  // Return (entry pool size, number of entries).3180  uint32_t num = 0;3181  for (auto &map : maps)3182    num += map.size();3183  return {offsets[numShards - 1], num};3184}3185 3186void DebugNamesBaseSection::init(3187    function_ref<void(InputFile *, InputChunk &, OutputChunk &)> parseFile) {3188  TimeTraceScope timeScope("Merge .debug_names");3189  // Collect and remove input .debug_names sections. Save InputSection pointers3190  // to relocate string offsets in `writeTo`.3191  SetVector<InputFile *> files;3192  for (InputSectionBase *s : ctx.inputSections) {3193    InputSection *isec = dyn_cast<InputSection>(s);3194    if (!isec)3195      continue;3196    if (!(s->flags & SHF_ALLOC) && s->name == ".debug_names") {3197      s->markDead();3198      inputSections.push_back(isec);3199      files.insert(isec->file);3200    }3201  }3202 3203  // Parse input .debug_names sections and extract InputChunk and OutputChunk3204  // data. OutputChunk contains CU information, which will be needed by3205  // `writeTo`.3206  auto inputChunksPtr = std::make_unique<InputChunk[]>(files.size());3207  MutableArrayRef<InputChunk> inputChunks(inputChunksPtr.get(), files.size());3208  numChunks = files.size();3209  chunks = std::make_unique<OutputChunk[]>(files.size());3210  {3211    TimeTraceScope timeScope("Merge .debug_names", "parse");3212    parallelFor(0, files.size(), [&](size_t i) {3213      parseFile(files[i], inputChunks[i], chunks[i]);3214    });3215  }3216 3217  // Compute section header (except unit_length), abbrev table, and entry pool.3218  computeHdrAndAbbrevTable(inputChunks);3219  uint32_t entryPoolSize;3220  std::tie(entryPoolSize, hdr.NameCount) = computeEntryPool(inputChunks);3221  hdr.BucketCount = dwarf::getDebugNamesBucketCount(hdr.NameCount);3222 3223  // Compute the section size. Subtract 4 to get the unit_length for DWARF32.3224  uint32_t hdrSize = getDebugNamesHeaderSize(hdr.AugmentationStringSize);3225  size = findDebugNamesOffsets(hdrSize, hdr).EntriesBase + entryPoolSize;3226  hdr.UnitLength = size - 4;3227}3228 3229template <class ELFT>3230DebugNamesSection<ELFT>::DebugNamesSection(Ctx &ctx)3231    : DebugNamesBaseSection(ctx) {3232  init([&](InputFile *f, InputChunk &inputChunk, OutputChunk &chunk) {3233    auto *file = cast<ObjFile<ELFT>>(f);3234    DWARFContext dwarf(std::make_unique<LLDDwarfObj<ELFT>>(file));3235    auto &dobj = static_cast<const LLDDwarfObj<ELFT> &>(dwarf.getDWARFObj());3236    chunk.infoSec = dobj.getInfoSection();3237    DWARFDataExtractor namesExtractor(dobj, dobj.getNamesSection(),3238                                      ELFT::Endianness == endianness::little,3239                                      ELFT::Is64Bits ? 8 : 4);3240    // .debug_str is needed to get symbol names from string offsets.3241    DataExtractor strExtractor(dobj.getStrSection(),3242                               ELFT::Endianness == endianness::little,3243                               ELFT::Is64Bits ? 8 : 4);3244    inputChunk.section = dobj.getNamesSection();3245 3246    inputChunk.llvmDebugNames.emplace(namesExtractor, strExtractor);3247    if (Error e = inputChunk.llvmDebugNames->extract()) {3248      Err(ctx) << dobj.getNamesSection().sec << ": " << std::move(e);3249    }3250    parseDebugNames(3251        ctx, inputChunk, chunk, namesExtractor, strExtractor,3252        [&chunk, namesData = dobj.getNamesSection().Data.data()](3253            uint32_t numCus, const DWARFDebugNames::Header &hdr,3254            const DWARFDebugNames::DWARFDebugNamesOffsets &locs) {3255          // Read CU offsets, which are relocated by .debug_info + X3256          // relocations. Record the section offset to be relocated by3257          // `finalizeContents`.3258          chunk.compUnits.resize_for_overwrite(numCus + hdr.CompUnitCount);3259          for (auto i : seq(hdr.CompUnitCount))3260            chunk.compUnits[numCus + i] = locs.CUsBase + i * 4;3261 3262          // Read entry offsets.3263          const char *p = namesData + locs.EntryOffsetsBase;3264          SmallVector<uint32_t, 0> entryOffsets;3265          entryOffsets.resize_for_overwrite(hdr.NameCount);3266          for (uint32_t &offset : entryOffsets)3267            offset = endian::readNext<uint32_t, ELFT::Endianness, unaligned>(p);3268          return entryOffsets;3269        });3270  });3271}3272 3273template <class ELFT>3274template <class RelTy>3275void DebugNamesSection<ELFT>::getNameRelocs(3276    const InputFile &file, DenseMap<uint32_t, uint32_t> &relocs,3277    Relocs<RelTy> rels) {3278  for (const RelTy &rel : rels) {3279    Symbol &sym = file.getRelocTargetSym(rel);3280    relocs[rel.r_offset] = sym.getVA(ctx, getAddend<ELFT>(rel));3281  }3282}3283 3284template <class ELFT> void DebugNamesSection<ELFT>::finalizeContents() {3285  // Get relocations of .debug_names sections.3286  auto relocs = std::make_unique<DenseMap<uint32_t, uint32_t>[]>(numChunks);3287  parallelFor(0, numChunks, [&](size_t i) {3288    InputSection *sec = inputSections[i];3289    invokeOnRelocs(*sec, getNameRelocs, *sec->file, relocs.get()[i]);3290 3291    // Relocate CU offsets with .debug_info + X relocations.3292    OutputChunk &chunk = chunks.get()[i];3293    for (auto [j, cuOffset] : enumerate(chunk.compUnits))3294      cuOffset = relocs.get()[i].lookup(cuOffset);3295  });3296 3297  // Relocate string offsets in the name table with .debug_str + X relocations.3298  parallelForEach(nameVecs, [&](auto &nameVec) {3299    for (NameEntry &ne : nameVec)3300      ne.stringOffset = relocs.get()[ne.chunkIdx].lookup(ne.stringOffset);3301  });3302}3303 3304template <class ELFT> void DebugNamesSection<ELFT>::writeTo(uint8_t *buf) {3305  [[maybe_unused]] const uint8_t *const beginBuf = buf;3306  // Write the header.3307  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.UnitLength);3308  endian::writeNext<uint16_t, ELFT::Endianness>(buf, hdr.Version);3309  buf += 2; // padding3310  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.CompUnitCount);3311  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.LocalTypeUnitCount);3312  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.ForeignTypeUnitCount);3313  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.BucketCount);3314  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.NameCount);3315  endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.AbbrevTableSize);3316  endian::writeNext<uint32_t, ELFT::Endianness>(buf,3317                                                hdr.AugmentationStringSize);3318  memcpy(buf, hdr.AugmentationString.c_str(), hdr.AugmentationString.size());3319  buf += hdr.AugmentationStringSize;3320 3321  // Write the CU list.3322  for (auto &chunk : getChunks())3323    for (uint32_t cuOffset : chunk.compUnits)3324      endian::writeNext<uint32_t, ELFT::Endianness>(buf, cuOffset);3325 3326  // TODO: Write the local TU list, then the foreign TU list..3327 3328  // Write the hash lookup table.3329  SmallVector<SmallVector<NameEntry *, 0>, 0> buckets(hdr.BucketCount);3330  // Symbols enter into a bucket whose index is the hash modulo bucket_count.3331  for (auto &nameVec : nameVecs)3332    for (NameEntry &ne : nameVec)3333      buckets[ne.hashValue % hdr.BucketCount].push_back(&ne);3334 3335  // Write buckets (accumulated bucket counts).3336  uint32_t bucketIdx = 1;3337  for (const SmallVector<NameEntry *, 0> &bucket : buckets) {3338    if (!bucket.empty())3339      endian::write32<ELFT::Endianness>(buf, bucketIdx);3340    buf += 4;3341    bucketIdx += bucket.size();3342  }3343  // Write the hashes.3344  for (const SmallVector<NameEntry *, 0> &bucket : buckets)3345    for (const NameEntry *e : bucket)3346      endian::writeNext<uint32_t, ELFT::Endianness>(buf, e->hashValue);3347 3348  // Write the name table. The name entries are ordered by bucket_idx and3349  // correspond one-to-one with the hash lookup table.3350  //3351  // First, write the relocated string offsets.3352  for (const SmallVector<NameEntry *, 0> &bucket : buckets)3353    for (const NameEntry *ne : bucket)3354      endian::writeNext<uint32_t, ELFT::Endianness>(buf, ne->stringOffset);3355 3356  // Then write the entry offsets.3357  for (const SmallVector<NameEntry *, 0> &bucket : buckets)3358    for (const NameEntry *ne : bucket)3359      endian::writeNext<uint32_t, ELFT::Endianness>(buf, ne->entryOffset);3360 3361  // Write the abbrev table.3362  buf = llvm::copy(abbrevTableBuf, buf);3363 3364  // Write the entry pool. Unlike the name table, the name entries follow the3365  // nameVecs order computed by `computeEntryPool`.3366  for (auto &nameVec : nameVecs) {3367    for (NameEntry &ne : nameVec) {3368      // Write all the entries for the string.3369      for (const IndexEntry &ie : ne.entries()) {3370        buf += encodeULEB128(ie.abbrevCode, buf);3371        for (AttrValue value : ie.attrValues) {3372          switch (value.attrSize) {3373          case 1:3374            *buf++ = value.attrValue;3375            break;3376          case 2:3377            endian::writeNext<uint16_t, ELFT::Endianness>(buf, value.attrValue);3378            break;3379          case 4:3380            endian::writeNext<uint32_t, ELFT::Endianness>(buf, value.attrValue);3381            break;3382          default:3383            llvm_unreachable("invalid attrSize");3384          }3385        }3386      }3387      ++buf; // index entry sentinel3388    }3389  }3390  assert(uint64_t(buf - beginBuf) == size);3391}3392 3393GdbIndexSection::GdbIndexSection(Ctx &ctx)3394    : SyntheticSection(ctx, ".gdb_index", SHT_PROGBITS, 0, 1) {}3395 3396// Returns the desired size of an on-disk hash table for a .gdb_index section.3397// There's a tradeoff between size and collision rate. We aim 75% utilization.3398size_t GdbIndexSection::computeSymtabSize() const {3399  return std::max<size_t>(NextPowerOf2(symbols.size() * 4 / 3), 1024);3400}3401 3402static SmallVector<GdbIndexSection::CuEntry, 0>3403readCuList(DWARFContext &dwarf) {3404  SmallVector<GdbIndexSection::CuEntry, 0> ret;3405  for (std::unique_ptr<DWARFUnit> &cu : dwarf.compile_units())3406    ret.push_back({cu->getOffset(), cu->getLength() + 4});3407  return ret;3408}3409 3410static SmallVector<GdbIndexSection::AddressEntry, 0>3411readAddressAreas(Ctx &ctx, DWARFContext &dwarf, InputSection *sec) {3412  SmallVector<GdbIndexSection::AddressEntry, 0> ret;3413 3414  uint32_t cuIdx = 0;3415  for (std::unique_ptr<DWARFUnit> &cu : dwarf.compile_units()) {3416    if (Error e = cu->tryExtractDIEsIfNeeded(false)) {3417      Warn(ctx) << sec << ": " << std::move(e);3418      return {};3419    }3420    Expected<DWARFAddressRangesVector> ranges = cu->collectAddressRanges();3421    if (!ranges) {3422      Warn(ctx) << sec << ": " << ranges.takeError();3423      return {};3424    }3425 3426    ArrayRef<InputSectionBase *> sections = sec->file->getSections();3427    for (DWARFAddressRange &r : *ranges) {3428      if (r.SectionIndex == -1ULL)3429        continue;3430      // Range list with zero size has no effect.3431      InputSectionBase *s = sections[r.SectionIndex];3432      if (s && s != &InputSection::discarded && s->isLive())3433        if (r.LowPC != r.HighPC)3434          ret.push_back({cast<InputSection>(s), r.LowPC, r.HighPC, cuIdx});3435    }3436    ++cuIdx;3437  }3438 3439  return ret;3440}3441 3442template <class ELFT>3443static SmallVector<GdbIndexSection::NameAttrEntry, 0>3444readPubNamesAndTypes(Ctx &ctx, const LLDDwarfObj<ELFT> &obj,3445                     const SmallVectorImpl<GdbIndexSection::CuEntry> &cus) {3446  const LLDDWARFSection &pubNames = obj.getGnuPubnamesSection();3447  const LLDDWARFSection &pubTypes = obj.getGnuPubtypesSection();3448 3449  SmallVector<GdbIndexSection::NameAttrEntry, 0> ret;3450  for (const LLDDWARFSection *pub : {&pubNames, &pubTypes}) {3451    DWARFDataExtractor data(obj, *pub, ELFT::Endianness == endianness::little,3452                            ELFT::Is64Bits ? 8 : 4);3453    DWARFDebugPubTable table;3454    table.extract(data, /*GnuStyle=*/true, [&](Error e) {3455      Warn(ctx) << pub->sec << ": " << std::move(e);3456    });3457    for (const DWARFDebugPubTable::Set &set : table.getData()) {3458      // The value written into the constant pool is kind << 24 | cuIndex. As we3459      // don't know how many compilation units precede this object to compute3460      // cuIndex, we compute (kind << 24 | cuIndexInThisObject) instead, and add3461      // the number of preceding compilation units later.3462      uint32_t i = llvm::partition_point(cus,3463                                         [&](GdbIndexSection::CuEntry cu) {3464                                           return cu.cuOffset < set.Offset;3465                                         }) -3466                   cus.begin();3467      for (const DWARFDebugPubTable::Entry &ent : set.Entries)3468        ret.push_back({{ent.Name, computeGdbHash(ent.Name)},3469                       (ent.Descriptor.toBits() << 24) | i});3470    }3471  }3472  return ret;3473}3474 3475// Create a list of symbols from a given list of symbol names and types3476// by uniquifying them by name.3477static std::pair<SmallVector<GdbIndexSection::GdbSymbol, 0>, size_t>3478createSymbols(3479    Ctx &ctx,3480    ArrayRef<SmallVector<GdbIndexSection::NameAttrEntry, 0>> nameAttrs,3481    const SmallVector<GdbIndexSection::GdbChunk, 0> &chunks) {3482  using GdbSymbol = GdbIndexSection::GdbSymbol;3483  using NameAttrEntry = GdbIndexSection::NameAttrEntry;3484 3485  // For each chunk, compute the number of compilation units preceding it.3486  uint32_t cuIdx = 0;3487  std::unique_ptr<uint32_t[]> cuIdxs(new uint32_t[chunks.size()]);3488  for (uint32_t i = 0, e = chunks.size(); i != e; ++i) {3489    cuIdxs[i] = cuIdx;3490    cuIdx += chunks[i].compilationUnits.size();3491  }3492 3493  // Collect the compilation unitss for each unique name. Speed it up using3494  // multi-threading as the number of symbols can be in the order of millions.3495  // Shard GdbSymbols by hash's high bits.3496  constexpr size_t numShards = 32;3497  const size_t concurrency =3498      llvm::bit_floor(std::min<size_t>(ctx.arg.threadCount, numShards));3499  const size_t shift = 32 - llvm::countr_zero(numShards);3500  auto map =3501      std::make_unique<DenseMap<CachedHashStringRef, size_t>[]>(numShards);3502  auto symbols = std::make_unique<SmallVector<GdbSymbol, 0>[]>(numShards);3503  parallelFor(0, concurrency, [&](size_t threadId) {3504    uint32_t i = 0;3505    for (ArrayRef<NameAttrEntry> entries : nameAttrs) {3506      for (const NameAttrEntry &ent : entries) {3507        size_t shardId = ent.name.hash() >> shift;3508        if ((shardId & (concurrency - 1)) != threadId)3509          continue;3510 3511        uint32_t v = ent.cuIndexAndAttrs + cuIdxs[i];3512        auto [it, inserted] =3513            map[shardId].try_emplace(ent.name, symbols[shardId].size());3514        if (inserted)3515          symbols[shardId].push_back({ent.name, {v}, 0, 0});3516        else3517          symbols[shardId][it->second].cuVector.push_back(v);3518      }3519      ++i;3520    }3521  });3522 3523  size_t numSymbols = 0;3524  for (ArrayRef<GdbSymbol> v : ArrayRef(symbols.get(), numShards))3525    numSymbols += v.size();3526 3527  // The return type is a flattened vector, so we'll copy each vector3528  // contents to Ret.3529  SmallVector<GdbSymbol, 0> ret;3530  ret.reserve(numSymbols);3531  for (SmallVector<GdbSymbol, 0> &vec :3532       MutableArrayRef(symbols.get(), numShards))3533    for (GdbSymbol &sym : vec)3534      ret.push_back(std::move(sym));3535 3536  // CU vectors and symbol names are adjacent in the output file.3537  // We can compute their offsets in the output file now.3538  size_t off = 0;3539  for (GdbSymbol &sym : ret) {3540    sym.cuVectorOff = off;3541    off += (sym.cuVector.size() + 1) * 4;3542  }3543  for (GdbSymbol &sym : ret) {3544    sym.nameOff = off;3545    off += sym.name.size() + 1;3546  }3547  // If off overflows, the last symbol's nameOff likely overflows.3548  if (!isUInt<32>(off))3549    Err(ctx) << "--gdb-index: constant pool size (" << off3550             << ") exceeds UINT32_MAX";3551 3552  return {ret, off};3553}3554 3555// Returns a newly-created .gdb_index section.3556template <class ELFT>3557std::unique_ptr<GdbIndexSection> GdbIndexSection::create(Ctx &ctx) {3558  llvm::TimeTraceScope timeScope("Create gdb index");3559 3560  // Collect InputFiles with .debug_info. See the comment in3561  // LLDDwarfObj<ELFT>::LLDDwarfObj. If we do lightweight parsing in the future,3562  // note that isec->data() may uncompress the full content, which should be3563  // parallelized.3564  SetVector<InputFile *> files;3565  for (InputSectionBase *s : ctx.inputSections) {3566    InputSection *isec = dyn_cast<InputSection>(s);3567    if (!isec)3568      continue;3569    // .debug_gnu_pub{names,types} are useless in executables.3570    // They are present in input object files solely for creating3571    // a .gdb_index. So we can remove them from the output.3572    if (s->name == ".debug_gnu_pubnames" || s->name == ".debug_gnu_pubtypes")3573      s->markDead();3574    else if (isec->name == ".debug_info")3575      files.insert(isec->file);3576  }3577  // Drop .rel[a].debug_gnu_pub{names,types} for --emit-relocs.3578  llvm::erase_if(ctx.inputSections, [](InputSectionBase *s) {3579    if (auto *isec = dyn_cast<InputSection>(s))3580      if (InputSectionBase *rel = isec->getRelocatedSection())3581        return !rel->isLive();3582    return !s->isLive();3583  });3584 3585  SmallVector<GdbChunk, 0> chunks(files.size());3586  SmallVector<SmallVector<NameAttrEntry, 0>, 0> nameAttrs(files.size());3587 3588  parallelFor(0, files.size(), [&](size_t i) {3589    // To keep memory usage low, we don't want to keep cached DWARFContext, so3590    // avoid getDwarf() here.3591    ObjFile<ELFT> *file = cast<ObjFile<ELFT>>(files[i]);3592    DWARFContext dwarf(std::make_unique<LLDDwarfObj<ELFT>>(file));3593    auto &dobj = static_cast<const LLDDwarfObj<ELFT> &>(dwarf.getDWARFObj());3594 3595    // If the are multiple compile units .debug_info (very rare ld -r --unique),3596    // this only picks the last one. Other address ranges are lost.3597    chunks[i].sec = dobj.getInfoSection();3598    chunks[i].compilationUnits = readCuList(dwarf);3599    chunks[i].addressAreas = readAddressAreas(ctx, dwarf, chunks[i].sec);3600    nameAttrs[i] =3601        readPubNamesAndTypes<ELFT>(ctx, dobj, chunks[i].compilationUnits);3602  });3603 3604  auto ret = std::make_unique<GdbIndexSection>(ctx);3605  ret->chunks = std::move(chunks);3606  std::tie(ret->symbols, ret->size) =3607      createSymbols(ctx, nameAttrs, ret->chunks);3608 3609  // Count the areas other than the constant pool.3610  ret->size += sizeof(GdbIndexHeader) + ret->computeSymtabSize() * 8;3611  for (GdbChunk &chunk : ret->chunks)3612    ret->size +=3613        chunk.compilationUnits.size() * 16 + chunk.addressAreas.size() * 20;3614 3615  return ret;3616}3617 3618void GdbIndexSection::writeTo(uint8_t *buf) {3619  // Write the header.3620  auto *hdr = reinterpret_cast<GdbIndexHeader *>(buf);3621  uint8_t *start = buf;3622  hdr->version = 7;3623  buf += sizeof(*hdr);3624 3625  // Write the CU list.3626  hdr->cuListOff = buf - start;3627  for (GdbChunk &chunk : chunks) {3628    for (CuEntry &cu : chunk.compilationUnits) {3629      write64le(buf, chunk.sec->outSecOff + cu.cuOffset);3630      write64le(buf + 8, cu.cuLength);3631      buf += 16;3632    }3633  }3634 3635  // Write the address area.3636  hdr->cuTypesOff = buf - start;3637  hdr->addressAreaOff = buf - start;3638  uint32_t cuOff = 0;3639  for (GdbChunk &chunk : chunks) {3640    for (AddressEntry &e : chunk.addressAreas) {3641      // In the case of ICF there may be duplicate address range entries.3642      const uint64_t baseAddr = e.section->repl->getVA(0);3643      write64le(buf, baseAddr + e.lowAddress);3644      write64le(buf + 8, baseAddr + e.highAddress);3645      write32le(buf + 16, e.cuIndex + cuOff);3646      buf += 20;3647    }3648    cuOff += chunk.compilationUnits.size();3649  }3650 3651  // Write the on-disk open-addressing hash table containing symbols.3652  hdr->symtabOff = buf - start;3653  size_t symtabSize = computeSymtabSize();3654  uint32_t mask = symtabSize - 1;3655 3656  for (GdbSymbol &sym : symbols) {3657    uint32_t h = sym.name.hash();3658    uint32_t i = h & mask;3659    uint32_t step = ((h * 17) & mask) | 1;3660 3661    while (read32le(buf + i * 8))3662      i = (i + step) & mask;3663 3664    write32le(buf + i * 8, sym.nameOff);3665    write32le(buf + i * 8 + 4, sym.cuVectorOff);3666  }3667 3668  buf += symtabSize * 8;3669 3670  // Write the string pool.3671  hdr->constantPoolOff = buf - start;3672  parallelForEach(symbols, [&](GdbSymbol &sym) {3673    memcpy(buf + sym.nameOff, sym.name.data(), sym.name.size());3674  });3675 3676  // Write the CU vectors.3677  for (GdbSymbol &sym : symbols) {3678    write32le(buf, sym.cuVector.size());3679    buf += 4;3680    for (uint32_t val : sym.cuVector) {3681      write32le(buf, val);3682      buf += 4;3683    }3684  }3685}3686 3687bool GdbIndexSection::isNeeded() const { return !chunks.empty(); }3688 3689VersionDefinitionSection::VersionDefinitionSection(Ctx &ctx)3690    : SyntheticSection(ctx, ".gnu.version_d", SHT_GNU_verdef, SHF_ALLOC,3691                       sizeof(uint32_t)) {}3692 3693StringRef VersionDefinitionSection::getFileDefName() {3694  if (!getPartition(ctx).name.empty())3695    return getPartition(ctx).name;3696  if (!ctx.arg.soName.empty())3697    return ctx.arg.soName;3698  return ctx.arg.outputFile;3699}3700 3701void VersionDefinitionSection::finalizeContents() {3702  fileDefNameOff = getPartition(ctx).dynStrTab->addString(getFileDefName());3703  for (const VersionDefinition &v : namedVersionDefs(ctx))3704    verDefNameOffs.push_back(getPartition(ctx).dynStrTab->addString(v.name));3705 3706  if (OutputSection *sec = getPartition(ctx).dynStrTab->getParent())3707    getParent()->link = sec->sectionIndex;3708 3709  // sh_info should be set to the number of definitions. This fact is missed in3710  // documentation, but confirmed by binutils community:3711  // https://sourceware.org/ml/binutils/2014-11/msg00355.html3712  getParent()->info = getVerDefNum(ctx);3713}3714 3715void VersionDefinitionSection::writeOne(uint8_t *buf, uint32_t index,3716                                        StringRef name, size_t nameOff) {3717  uint16_t flags = index == 1 ? VER_FLG_BASE : 0;3718 3719  // Write a verdef.3720  write16(ctx, buf, 1);                  // vd_version3721  write16(ctx, buf + 2, flags);          // vd_flags3722  write16(ctx, buf + 4, index);          // vd_ndx3723  write16(ctx, buf + 6, 1);              // vd_cnt3724  write32(ctx, buf + 8, hashSysV(name)); // vd_hash3725  write32(ctx, buf + 12, 20);            // vd_aux3726  write32(ctx, buf + 16, 28);            // vd_next3727 3728  // Write a veraux.3729  write32(ctx, buf + 20, nameOff); // vda_name3730  write32(ctx, buf + 24, 0);       // vda_next3731}3732 3733void VersionDefinitionSection::writeTo(uint8_t *buf) {3734  writeOne(buf, 1, getFileDefName(), fileDefNameOff);3735 3736  auto nameOffIt = verDefNameOffs.begin();3737  for (const VersionDefinition &v : namedVersionDefs(ctx)) {3738    buf += EntrySize;3739    writeOne(buf, v.id, v.name, *nameOffIt++);3740  }3741 3742  // Need to terminate the last version definition.3743  write32(ctx, buf + 16, 0); // vd_next3744}3745 3746size_t VersionDefinitionSection::getSize() const {3747  return EntrySize * getVerDefNum(ctx);3748}3749 3750// .gnu.version is a table where each entry is 2 byte long.3751VersionTableSection::VersionTableSection(Ctx &ctx)3752    : SyntheticSection(ctx, ".gnu.version", SHT_GNU_versym, SHF_ALLOC,3753                       sizeof(uint16_t)) {3754  this->entsize = 2;3755}3756 3757void VersionTableSection::finalizeContents() {3758  if (OutputSection *osec = getPartition(ctx).dynSymTab->getParent())3759    getParent()->link = osec->sectionIndex;3760}3761 3762size_t VersionTableSection::getSize() const {3763  return (getPartition(ctx).dynSymTab->getSymbols().size() + 1) * 2;3764}3765 3766void VersionTableSection::writeTo(uint8_t *buf) {3767  buf += 2;3768  for (const SymbolTableEntry &s : getPartition(ctx).dynSymTab->getSymbols()) {3769    // For an unextracted lazy symbol (undefined weak), it must have been3770    // converted to Undefined.3771    assert(!s.sym->isLazy());3772    // Undefined symbols should use index 0 when unversioned.3773    write16(ctx, buf, s.sym->isUndefined() ? 0 : s.sym->versionId);3774    buf += 2;3775  }3776}3777 3778bool VersionTableSection::isNeeded() const {3779  return isLive() &&3780         (getPartition(ctx).verDef || getPartition(ctx).verNeed->isNeeded());3781}3782 3783void elf::addVerneed(Ctx &ctx, Symbol &ss) {3784  auto &file = cast<SharedFile>(*ss.file);3785  if (ss.versionId == VER_NDX_GLOBAL)3786    return;3787 3788  if (file.vernauxs.empty())3789    file.vernauxs.resize(file.verdefs.size());3790 3791  // Select a version identifier for the vernaux data structure, if we haven't3792  // already allocated one. The verdef identifiers cover the range3793  // [1..getVerDefNum(ctx)]; this causes the vernaux identifiers to start from3794  // getVerDefNum(ctx)+1.3795  if (file.vernauxs[ss.versionId] == 0)3796    file.vernauxs[ss.versionId] = ++ctx.vernauxNum + getVerDefNum(ctx);3797 3798  ss.versionId = file.vernauxs[ss.versionId];3799}3800 3801template <class ELFT>3802VersionNeedSection<ELFT>::VersionNeedSection(Ctx &ctx)3803    : SyntheticSection(ctx, ".gnu.version_r", SHT_GNU_verneed, SHF_ALLOC,3804                       sizeof(uint32_t)) {}3805 3806template <class ELFT> void VersionNeedSection<ELFT>::finalizeContents() {3807  for (SharedFile *f : ctx.sharedFiles) {3808    if (f->vernauxs.empty())3809      continue;3810    verneeds.emplace_back();3811    Verneed &vn = verneeds.back();3812    vn.nameStrTab = getPartition(ctx).dynStrTab->addString(f->soName);3813    bool isLibc = ctx.arg.relrGlibc && f->soName.starts_with("libc.so.");3814    bool isGlibc2 = false;3815    for (unsigned i = 0; i != f->vernauxs.size(); ++i) {3816      if (f->vernauxs[i] == 0)3817        continue;3818      auto *verdef =3819          reinterpret_cast<const typename ELFT::Verdef *>(f->verdefs[i]);3820      StringRef ver(f->getStringTable().data() + verdef->getAux()->vda_name);3821      if (isLibc && ver.starts_with("GLIBC_2."))3822        isGlibc2 = true;3823      vn.vernauxs.push_back({verdef->vd_hash, f->vernauxs[i],3824                             getPartition(ctx).dynStrTab->addString(ver)});3825    }3826    if (isGlibc2) {3827      const char *ver = "GLIBC_ABI_DT_RELR";3828      vn.vernauxs.push_back({hashSysV(ver),3829                             ++ctx.vernauxNum + getVerDefNum(ctx),3830                             getPartition(ctx).dynStrTab->addString(ver)});3831    }3832  }3833 3834  if (OutputSection *sec = getPartition(ctx).dynStrTab->getParent())3835    getParent()->link = sec->sectionIndex;3836  getParent()->info = verneeds.size();3837}3838 3839template <class ELFT> void VersionNeedSection<ELFT>::writeTo(uint8_t *buf) {3840  // The Elf_Verneeds need to appear first, followed by the Elf_Vernauxs.3841  auto *verneed = reinterpret_cast<Elf_Verneed *>(buf);3842  auto *vernaux = reinterpret_cast<Elf_Vernaux *>(verneed + verneeds.size());3843 3844  for (auto &vn : verneeds) {3845    // Create an Elf_Verneed for this DSO.3846    verneed->vn_version = 1;3847    verneed->vn_cnt = vn.vernauxs.size();3848    verneed->vn_file = vn.nameStrTab;3849    verneed->vn_aux =3850        reinterpret_cast<char *>(vernaux) - reinterpret_cast<char *>(verneed);3851    verneed->vn_next = sizeof(Elf_Verneed);3852    ++verneed;3853 3854    // Create the Elf_Vernauxs for this Elf_Verneed.3855    for (auto &vna : vn.vernauxs) {3856      vernaux->vna_hash = vna.hash;3857      vernaux->vna_flags = 0;3858      vernaux->vna_other = vna.verneedIndex;3859      vernaux->vna_name = vna.nameStrTab;3860      vernaux->vna_next = sizeof(Elf_Vernaux);3861      ++vernaux;3862    }3863 3864    vernaux[-1].vna_next = 0;3865  }3866  verneed[-1].vn_next = 0;3867}3868 3869template <class ELFT> size_t VersionNeedSection<ELFT>::getSize() const {3870  return verneeds.size() * sizeof(Elf_Verneed) +3871         ctx.vernauxNum * sizeof(Elf_Vernaux);3872}3873 3874template <class ELFT> bool VersionNeedSection<ELFT>::isNeeded() const {3875  return isLive() && ctx.vernauxNum != 0;3876}3877 3878void MergeSyntheticSection::addSection(MergeInputSection *ms) {3879  ms->parent = this;3880  sections.push_back(ms);3881  assert(addralign == ms->addralign || !(ms->flags & SHF_STRINGS));3882  addralign = std::max(addralign, ms->addralign);3883}3884 3885MergeTailSection::MergeTailSection(Ctx &ctx, StringRef name, uint32_t type,3886                                   uint64_t flags, uint32_t alignment)3887    : MergeSyntheticSection(ctx, name, type, flags, alignment),3888      builder(StringTableBuilder::RAW, llvm::Align(alignment)) {}3889 3890size_t MergeTailSection::getSize() const { return builder.getSize(); }3891 3892void MergeTailSection::writeTo(uint8_t *buf) { builder.write(buf); }3893 3894void MergeTailSection::finalizeContents() {3895  // Add all string pieces to the string table builder to create section3896  // contents.3897  for (MergeInputSection *sec : sections)3898    for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)3899      if (sec->pieces[i].live)3900        builder.add(sec->getData(i));3901 3902  // Fix the string table content. After this, the contents will never change.3903  builder.finalize();3904 3905  // finalize() fixed tail-optimized strings, so we can now get3906  // offsets of strings. Get an offset for each string and save it3907  // to a corresponding SectionPiece for easy access.3908  for (MergeInputSection *sec : sections)3909    for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)3910      if (sec->pieces[i].live)3911        sec->pieces[i].outputOff = builder.getOffset(sec->getData(i));3912}3913 3914void MergeNoTailSection::writeTo(uint8_t *buf) {3915  parallelFor(0, numShards,3916              [&](size_t i) { shards[i].write(buf + shardOffsets[i]); });3917}3918 3919// This function is very hot (i.e. it can take several seconds to finish)3920// because sometimes the number of inputs is in an order of magnitude of3921// millions. So, we use multi-threading.3922//3923// For any strings S and T, we know S is not mergeable with T if S's hash3924// value is different from T's. If that's the case, we can safely put S and3925// T into different string builders without worrying about merge misses.3926// We do it in parallel.3927void MergeNoTailSection::finalizeContents() {3928  // Initializes string table builders.3929  for (size_t i = 0; i < numShards; ++i)3930    shards.emplace_back(StringTableBuilder::RAW, llvm::Align(addralign));3931 3932  // Concurrency level. Must be a power of 2 to avoid expensive modulo3933  // operations in the following tight loop.3934  const size_t concurrency =3935      llvm::bit_floor(std::min<size_t>(ctx.arg.threadCount, numShards));3936 3937  // Add section pieces to the builders.3938  parallelFor(0, concurrency, [&](size_t threadId) {3939    for (MergeInputSection *sec : sections) {3940      for (size_t i = 0, e = sec->pieces.size(); i != e; ++i) {3941        if (!sec->pieces[i].live)3942          continue;3943        size_t shardId = getShardId(sec->pieces[i].hash);3944        if ((shardId & (concurrency - 1)) == threadId)3945          sec->pieces[i].outputOff = shards[shardId].add(sec->getData(i));3946      }3947    }3948  });3949 3950  // Compute an in-section offset for each shard.3951  size_t off = 0;3952  for (size_t i = 0; i < numShards; ++i) {3953    shards[i].finalizeInOrder();3954    if (shards[i].getSize() > 0)3955      off = alignToPowerOf2(off, addralign);3956    shardOffsets[i] = off;3957    off += shards[i].getSize();3958  }3959  size = off;3960 3961  // So far, section pieces have offsets from beginning of shards, but3962  // we want offsets from beginning of the whole section. Fix them.3963  parallelForEach(sections, [&](MergeInputSection *sec) {3964    for (SectionPiece &piece : sec->pieces)3965      if (piece.live)3966        piece.outputOff += shardOffsets[getShardId(piece.hash)];3967  });3968}3969 3970template <class ELFT> void elf::splitSections(Ctx &ctx) {3971  llvm::TimeTraceScope timeScope("Split sections");3972  // splitIntoPieces needs to be called on each MergeInputSection3973  // before calling finalizeContents().3974  parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {3975    for (InputSectionBase *sec : file->getSections()) {3976      if (!sec)3977        continue;3978      if (auto *s = dyn_cast<MergeInputSection>(sec))3979        s->splitIntoPieces();3980      else if (auto *eh = dyn_cast<EhInputSection>(sec))3981        eh->split<ELFT>();3982    }3983  });3984}3985 3986void elf::combineEhSections(Ctx &ctx) {3987  llvm::TimeTraceScope timeScope("Combine EH sections");3988  for (EhInputSection *sec : ctx.ehInputSections) {3989    EhFrameSection &eh = *sec->getPartition(ctx).ehFrame;3990    sec->parent = &eh;3991    eh.addralign = std::max(eh.addralign, sec->addralign);3992    eh.sections.push_back(sec);3993    llvm::append_range(eh.dependentSections, sec->dependentSections);3994  }3995 3996  if (!ctx.mainPart->armExidx)3997    return;3998  llvm::erase_if(ctx.inputSections, [&](InputSectionBase *s) {3999    // Ignore dead sections and the partition end marker (.part.end),4000    // whose partition number is out of bounds.4001    if (!s->isLive() || s->partition == 255)4002      return false;4003    Partition &part = s->getPartition(ctx);4004    return s->kind() == SectionBase::Regular && part.armExidx &&4005           part.armExidx->addSection(cast<InputSection>(s));4006  });4007}4008 4009MipsRldMapSection::MipsRldMapSection(Ctx &ctx)4010    : SyntheticSection(ctx, ".rld_map", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE,4011                       ctx.arg.wordsize) {}4012 4013ARMExidxSyntheticSection::ARMExidxSyntheticSection(Ctx &ctx)4014    : SyntheticSection(ctx, ".ARM.exidx", SHT_ARM_EXIDX,4015                       SHF_ALLOC | SHF_LINK_ORDER, ctx.arg.wordsize) {}4016 4017static InputSection *findExidxSection(InputSection *isec) {4018  for (InputSection *d : isec->dependentSections)4019    if (d->type == SHT_ARM_EXIDX && d->isLive())4020      return d;4021  return nullptr;4022}4023 4024static bool isValidExidxSectionDep(InputSection *isec) {4025  return (isec->flags & SHF_ALLOC) && (isec->flags & SHF_EXECINSTR) &&4026         isec->getSize() > 0;4027}4028 4029bool ARMExidxSyntheticSection::addSection(InputSection *isec) {4030  if (isec->type == SHT_ARM_EXIDX) {4031    if (InputSection *dep = isec->getLinkOrderDep())4032      if (isValidExidxSectionDep(dep)) {4033        exidxSections.push_back(isec);4034        // Every exidxSection is 8 bytes, we need an estimate of4035        // size before assignAddresses can be called. Final size4036        // will only be known after finalize is called.4037        size += 8;4038      }4039    return true;4040  }4041 4042  if (isValidExidxSectionDep(isec)) {4043    executableSections.push_back(isec);4044    return false;4045  }4046 4047  // FIXME: we do not output a relocation section when --emit-relocs is used4048  // as we do not have relocation sections for linker generated table entries4049  // and we would have to erase at a late stage relocations from merged entries.4050  // Given that exception tables are already position independent and a binary4051  // analyzer could derive the relocations we choose to erase the relocations.4052  if (ctx.arg.emitRelocs && isec->type == SHT_REL)4053    if (InputSectionBase *ex = isec->getRelocatedSection())4054      if (isa<InputSection>(ex) && ex->type == SHT_ARM_EXIDX)4055        return true;4056 4057  return false;4058}4059 4060// References to .ARM.Extab Sections have bit 31 clear and are not the4061// special EXIDX_CANTUNWIND bit-pattern.4062static bool isExtabRef(uint32_t unwind) {4063  return (unwind & 0x80000000) == 0 && unwind != 0x1;4064}4065 4066// Return true if the .ARM.exidx section Cur can be merged into the .ARM.exidx4067// section Prev, where Cur follows Prev in the table. This can be done if the4068// unwinding instructions in Cur are identical to Prev. Linker generated4069// EXIDX_CANTUNWIND entries are represented by nullptr as they do not have an4070// InputSection.4071static bool isDuplicateArmExidxSec(Ctx &ctx, InputSection *prev,4072                                   InputSection *cur) {4073  // Get the last table Entry from the previous .ARM.exidx section. If Prev is4074  // nullptr then it will be a synthesized EXIDX_CANTUNWIND entry.4075  uint32_t prevUnwind = 1;4076  if (prev)4077    prevUnwind =4078        read32(ctx, prev->content().data() + prev->content().size() - 4);4079  if (isExtabRef(prevUnwind))4080    return false;4081 4082  // We consider the unwind instructions of an .ARM.exidx table entry4083  // a duplicate if the previous unwind instructions if:4084  // - Both are the special EXIDX_CANTUNWIND.4085  // - Both are the same inline unwind instructions.4086  // We do not attempt to follow and check links into .ARM.extab tables as4087  // consecutive identical entries are rare and the effort to check that they4088  // are identical is high.4089 4090  // If Cur is nullptr then this is synthesized EXIDX_CANTUNWIND entry.4091  if (cur == nullptr)4092    return prevUnwind == 1;4093 4094  for (uint32_t offset = 4; offset < (uint32_t)cur->content().size(); offset +=8) {4095    uint32_t curUnwind = read32(ctx, cur->content().data() + offset);4096    if (isExtabRef(curUnwind) || curUnwind != prevUnwind)4097      return false;4098  }4099  // All table entries in this .ARM.exidx Section can be merged into the4100  // previous Section.4101  return true;4102}4103 4104// The .ARM.exidx table must be sorted in ascending order of the address of the4105// functions the table describes. std::optionally duplicate adjacent table4106// entries can be removed. At the end of the function the executableSections4107// must be sorted in ascending order of address, Sentinel is set to the4108// InputSection with the highest address and any InputSections that have4109// mergeable .ARM.exidx table entries are removed from it.4110void ARMExidxSyntheticSection::finalizeContents() {4111  // Ensure that any fixed-point iterations after the first see the original set4112  // of sections.4113  if (!originalExecutableSections.empty())4114    executableSections = originalExecutableSections;4115  else if (ctx.arg.enableNonContiguousRegions)4116    originalExecutableSections = executableSections;4117 4118  // The executableSections and exidxSections that we use to derive the final4119  // contents of this SyntheticSection are populated before4120  // processSectionCommands() and ICF. A /DISCARD/ entry in SECTIONS command or4121  // ICF may remove executable InputSections and their dependent .ARM.exidx4122  // section that we recorded earlier.4123  auto isDiscarded = [](const InputSection *isec) { return !isec->isLive(); };4124  llvm::erase_if(exidxSections, isDiscarded);4125  // We need to remove discarded InputSections and InputSections without4126  // .ARM.exidx sections that if we generated the .ARM.exidx it would be out4127  // of range.4128  auto isDiscardedOrOutOfRange = [this](InputSection *isec) {4129    if (!isec->isLive())4130      return true;4131    if (findExidxSection(isec))4132      return false;4133    int64_t off = static_cast<int64_t>(isec->getVA() - getVA());4134    return off != llvm::SignExtend64(off, 31);4135  };4136  llvm::erase_if(executableSections, isDiscardedOrOutOfRange);4137 4138  // Sort the executable sections that may or may not have associated4139  // .ARM.exidx sections by order of ascending address. This requires the4140  // relative positions of InputSections and OutputSections to be known.4141  auto compareByFilePosition = [](const InputSection *a,4142                                  const InputSection *b) {4143    OutputSection *aOut = a->getParent();4144    OutputSection *bOut = b->getParent();4145 4146    if (aOut != bOut)4147      return aOut->addr < bOut->addr;4148    return a->outSecOff < b->outSecOff;4149  };4150  llvm::stable_sort(executableSections, compareByFilePosition);4151  sentinel = executableSections.back();4152  // std::optionally merge adjacent duplicate entries.4153  if (ctx.arg.mergeArmExidx) {4154    SmallVector<InputSection *, 0> selectedSections;4155    selectedSections.reserve(executableSections.size());4156    selectedSections.push_back(executableSections[0]);4157    size_t prev = 0;4158    for (size_t i = 1; i < executableSections.size(); ++i) {4159      InputSection *ex1 = findExidxSection(executableSections[prev]);4160      InputSection *ex2 = findExidxSection(executableSections[i]);4161      if (!isDuplicateArmExidxSec(ctx, ex1, ex2)) {4162        selectedSections.push_back(executableSections[i]);4163        prev = i;4164      }4165    }4166    executableSections = std::move(selectedSections);4167  }4168  // offset is within the SyntheticSection.4169  size_t offset = 0;4170  size = 0;4171  for (InputSection *isec : executableSections) {4172    if (InputSection *d = findExidxSection(isec)) {4173      d->outSecOff = offset;4174      d->parent = getParent();4175      offset += d->getSize();4176    } else {4177      offset += 8;4178    }4179  }4180  // Size includes Sentinel.4181  size = offset + 8;4182}4183 4184InputSection *ARMExidxSyntheticSection::getLinkOrderDep() const {4185  return executableSections.front();4186}4187 4188// To write the .ARM.exidx table from the ExecutableSections we have three cases4189// 1.) The InputSection has a .ARM.exidx InputSection in its dependent sections.4190//     We write the .ARM.exidx section contents and apply its relocations.4191// 2.) The InputSection does not have a dependent .ARM.exidx InputSection. We4192//     must write the contents of an EXIDX_CANTUNWIND directly. We use the4193//     start of the InputSection as the purpose of the linker generated4194//     section is to terminate the address range of the previous entry.4195// 3.) A trailing EXIDX_CANTUNWIND sentinel section is required at the end of4196//     the table to terminate the address range of the final entry.4197void ARMExidxSyntheticSection::writeTo(uint8_t *buf) {4198 4199  // A linker generated CANTUNWIND entry is made up of two words:4200  // 0x0 with R_ARM_PREL31 relocation to target.4201  // 0x1 with EXIDX_CANTUNWIND.4202  uint64_t offset = 0;4203  for (InputSection *isec : executableSections) {4204    assert(isec->getParent() != nullptr);4205    if (InputSection *d = findExidxSection(isec)) {4206      for (int dataOffset = 0; dataOffset != (int)d->content().size();4207           dataOffset += 4)4208        write32(ctx, buf + offset + dataOffset,4209                read32(ctx, d->content().data() + dataOffset));4210      // Recalculate outSecOff as finalizeAddressDependentContent()4211      // may have altered syntheticSection outSecOff.4212      d->outSecOff = offset + outSecOff;4213      ctx.target->relocateAlloc(*d, buf + offset);4214      offset += d->getSize();4215    } else {4216      // A Linker generated CANTUNWIND section.4217      write32(ctx, buf + offset + 0, 0x0);4218      write32(ctx, buf + offset + 4, 0x1);4219      uint64_t s = isec->getVA();4220      uint64_t p = getVA() + offset;4221      ctx.target->relocateNoSym(buf + offset, R_ARM_PREL31, s - p);4222      offset += 8;4223    }4224  }4225  // Write Sentinel CANTUNWIND entry.4226  write32(ctx, buf + offset + 0, 0x0);4227  write32(ctx, buf + offset + 4, 0x1);4228  uint64_t s = sentinel->getVA(sentinel->getSize());4229  uint64_t p = getVA() + offset;4230  ctx.target->relocateNoSym(buf + offset, R_ARM_PREL31, s - p);4231  assert(size == offset + 8);4232}4233 4234bool ARMExidxSyntheticSection::isNeeded() const {4235  return llvm::any_of(exidxSections,4236                      [](InputSection *isec) { return isec->isLive(); });4237}4238 4239ThunkSection::ThunkSection(Ctx &ctx, OutputSection *os, uint64_t off)4240    : SyntheticSection(ctx, ".text.thunk", SHT_PROGBITS,4241                       SHF_ALLOC | SHF_EXECINSTR,4242                       ctx.arg.emachine == EM_PPC64 ? 16 : 4) {4243  this->parent = os;4244  this->outSecOff = off;4245}4246 4247size_t ThunkSection::getSize() const {4248  if (roundUpSizeForErrata)4249    return alignTo(size, 4096);4250  return size;4251}4252 4253void ThunkSection::addThunk(Thunk *t) {4254  thunks.push_back(t);4255  t->addSymbols(*this);4256}4257 4258void ThunkSection::writeTo(uint8_t *buf) {4259  for (Thunk *t : thunks)4260    t->writeTo(buf + t->offset);4261}4262 4263InputSection *ThunkSection::getTargetInputSection() const {4264  if (thunks.empty())4265    return nullptr;4266  const Thunk *t = thunks.front();4267  return t->getTargetInputSection();4268}4269 4270bool ThunkSection::assignOffsets() {4271  uint64_t off = 0;4272  bool changed = false;4273  for (Thunk *t : thunks) {4274    if (t->alignment > addralign) {4275      addralign = t->alignment;4276      changed = true;4277    }4278    off = alignToPowerOf2(off, t->alignment);4279    t->setOffset(off);4280    uint32_t size = t->size();4281    t->getThunkTargetSym()->size = size;4282    off += size;4283  }4284  if (off != size)4285    changed = true;4286  size = off;4287  return changed;4288}4289 4290PPC32Got2Section::PPC32Got2Section(Ctx &ctx)4291    : SyntheticSection(ctx, ".got2", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE, 4) {}4292 4293bool PPC32Got2Section::isNeeded() const {4294  // See the comment below. This is not needed if there is no other4295  // InputSection.4296  for (SectionCommand *cmd : getParent()->commands)4297    if (auto *isd = dyn_cast<InputSectionDescription>(cmd))4298      for (InputSection *isec : isd->sections)4299        if (isec != this)4300          return true;4301  return false;4302}4303 4304void PPC32Got2Section::finalizeContents() {4305  // PPC32 may create multiple GOT sections for -fPIC/-fPIE, one per file in4306  // .got2 . This function computes outSecOff of each .got2 to be used in4307  // PPC32PltCallStub::writeTo(). The purpose of this empty synthetic section is4308  // to collect input sections named ".got2".4309  for (SectionCommand *cmd : getParent()->commands)4310    if (auto *isd = dyn_cast<InputSectionDescription>(cmd)) {4311      for (InputSection *isec : isd->sections) {4312        // isec->file may be nullptr for MergeSyntheticSection.4313        if (isec != this && isec->file)4314          isec->file->ppc32Got2 = isec;4315      }4316    }4317}4318 4319// If linking position-dependent code then the table will store the addresses4320// directly in the binary so the section has type SHT_PROGBITS. If linking4321// position-independent code the section has type SHT_NOBITS since it will be4322// allocated and filled in by the dynamic linker.4323PPC64LongBranchTargetSection::PPC64LongBranchTargetSection(Ctx &ctx)4324    : SyntheticSection(ctx, ".branch_lt",4325                       ctx.arg.isPic ? SHT_NOBITS : SHT_PROGBITS,4326                       SHF_ALLOC | SHF_WRITE, 8) {}4327 4328uint64_t PPC64LongBranchTargetSection::getEntryVA(const Symbol *sym,4329                                                  int64_t addend) {4330  return getVA() + entry_index.find({sym, addend})->second * 8;4331}4332 4333std::optional<uint32_t>4334PPC64LongBranchTargetSection::addEntry(const Symbol *sym, int64_t addend) {4335  auto res =4336      entry_index.try_emplace(std::make_pair(sym, addend), entries.size());4337  if (!res.second)4338    return std::nullopt;4339  entries.emplace_back(sym, addend);4340  return res.first->second;4341}4342 4343size_t PPC64LongBranchTargetSection::getSize() const {4344  return entries.size() * 8;4345}4346 4347void PPC64LongBranchTargetSection::writeTo(uint8_t *buf) {4348  // If linking non-pic we have the final addresses of the targets and they get4349  // written to the table directly. For pic the dynamic linker will allocate4350  // the section and fill it.4351  if (ctx.arg.isPic)4352    return;4353 4354  for (auto entry : entries) {4355    const Symbol *sym = entry.first;4356    int64_t addend = entry.second;4357    assert(sym->getVA(ctx));4358    // Need calls to branch to the local entry-point since a long-branch4359    // must be a local-call.4360    write64(ctx, buf,4361            sym->getVA(ctx, addend) +4362                getPPC64GlobalEntryToLocalEntryOffset(ctx, sym->stOther));4363    buf += 8;4364  }4365}4366 4367bool PPC64LongBranchTargetSection::isNeeded() const {4368  // `removeUnusedSyntheticSections()` is called before thunk allocation which4369  // is too early to determine if this section will be empty or not. We need4370  // Finalized to keep the section alive until after thunk creation. Finalized4371  // only gets set to true once `finalizeSections()` is called after thunk4372  // creation. Because of this, if we don't create any long-branch thunks we end4373  // up with an empty .branch_lt section in the binary.4374  return !finalized || !entries.empty();4375}4376 4377static uint8_t getAbiVersion(Ctx &ctx) {4378  // MIPS non-PIC executable gets ABI version 1.4379  if (ctx.arg.emachine == EM_MIPS) {4380    if (!ctx.arg.isPic && !ctx.arg.relocatable &&4381        (ctx.arg.eflags & (EF_MIPS_PIC | EF_MIPS_CPIC)) == EF_MIPS_CPIC)4382      return 1;4383    return 0;4384  }4385 4386  if (ctx.arg.emachine == EM_AMDGPU && !ctx.objectFiles.empty()) {4387    uint8_t ver = ctx.objectFiles[0]->abiVersion;4388    for (InputFile *file : ArrayRef(ctx.objectFiles).slice(1))4389      if (file->abiVersion != ver)4390        Err(ctx) << "incompatible ABI version: " << file;4391    return ver;4392  }4393 4394  return 0;4395}4396 4397template <typename ELFT>4398void elf::writeEhdr(Ctx &ctx, uint8_t *buf, Partition &part) {4399  memcpy(buf, "\177ELF", 4);4400 4401  auto *eHdr = reinterpret_cast<typename ELFT::Ehdr *>(buf);4402  eHdr->e_ident[EI_CLASS] = ELFT::Is64Bits ? ELFCLASS64 : ELFCLASS32;4403  eHdr->e_ident[EI_DATA] =4404      ELFT::Endianness == endianness::little ? ELFDATA2LSB : ELFDATA2MSB;4405  eHdr->e_ident[EI_VERSION] = EV_CURRENT;4406  eHdr->e_ident[EI_OSABI] = ctx.arg.osabi;4407  eHdr->e_ident[EI_ABIVERSION] = getAbiVersion(ctx);4408  eHdr->e_machine = ctx.arg.emachine;4409  eHdr->e_version = EV_CURRENT;4410  eHdr->e_flags = ctx.arg.eflags;4411  eHdr->e_ehsize = sizeof(typename ELFT::Ehdr);4412  eHdr->e_phnum = part.phdrs.size();4413  eHdr->e_shentsize = sizeof(typename ELFT::Shdr);4414 4415  if (!ctx.arg.relocatable) {4416    eHdr->e_phoff = sizeof(typename ELFT::Ehdr);4417    eHdr->e_phentsize = sizeof(typename ELFT::Phdr);4418  }4419}4420 4421template <typename ELFT> void elf::writePhdrs(uint8_t *buf, Partition &part) {4422  // Write the program header table.4423  auto *hBuf = reinterpret_cast<typename ELFT::Phdr *>(buf);4424  for (std::unique_ptr<PhdrEntry> &p : part.phdrs) {4425    hBuf->p_type = p->p_type;4426    hBuf->p_flags = p->p_flags;4427    hBuf->p_offset = p->p_offset;4428    hBuf->p_vaddr = p->p_vaddr;4429    hBuf->p_paddr = p->p_paddr;4430    hBuf->p_filesz = p->p_filesz;4431    hBuf->p_memsz = p->p_memsz;4432    hBuf->p_align = p->p_align;4433    ++hBuf;4434  }4435}4436 4437template <typename ELFT>4438PartitionElfHeaderSection<ELFT>::PartitionElfHeaderSection(Ctx &ctx)4439    : SyntheticSection(ctx, "", SHT_LLVM_PART_EHDR, SHF_ALLOC, 1) {}4440 4441template <typename ELFT>4442size_t PartitionElfHeaderSection<ELFT>::getSize() const {4443  return sizeof(typename ELFT::Ehdr);4444}4445 4446template <typename ELFT>4447void PartitionElfHeaderSection<ELFT>::writeTo(uint8_t *buf) {4448  writeEhdr<ELFT>(ctx, buf, getPartition(ctx));4449 4450  // Loadable partitions are always ET_DYN.4451  auto *eHdr = reinterpret_cast<typename ELFT::Ehdr *>(buf);4452  eHdr->e_type = ET_DYN;4453}4454 4455template <typename ELFT>4456PartitionProgramHeadersSection<ELFT>::PartitionProgramHeadersSection(Ctx &ctx)4457    : SyntheticSection(ctx, ".phdrs", SHT_LLVM_PART_PHDR, SHF_ALLOC, 1) {}4458 4459template <typename ELFT>4460size_t PartitionProgramHeadersSection<ELFT>::getSize() const {4461  return sizeof(typename ELFT::Phdr) * getPartition(ctx).phdrs.size();4462}4463 4464template <typename ELFT>4465void PartitionProgramHeadersSection<ELFT>::writeTo(uint8_t *buf) {4466  writePhdrs<ELFT>(buf, getPartition(ctx));4467}4468 4469PartitionIndexSection::PartitionIndexSection(Ctx &ctx)4470    : SyntheticSection(ctx, ".rodata", SHT_PROGBITS, SHF_ALLOC, 4) {}4471 4472size_t PartitionIndexSection::getSize() const {4473  return 12 * (ctx.partitions.size() - 1);4474}4475 4476void PartitionIndexSection::finalizeContents() {4477  for (size_t i = 1; i != ctx.partitions.size(); ++i)4478    ctx.partitions[i].nameStrTab =4479        ctx.mainPart->dynStrTab->addString(ctx.partitions[i].name);4480}4481 4482void PartitionIndexSection::writeTo(uint8_t *buf) {4483  uint64_t va = getVA();4484  for (size_t i = 1; i != ctx.partitions.size(); ++i) {4485    write32(ctx, buf,4486            ctx.mainPart->dynStrTab->getVA() + ctx.partitions[i].nameStrTab -4487                va);4488    write32(ctx, buf + 4, ctx.partitions[i].elfHeader->getVA() - (va + 4));4489 4490    SyntheticSection *next = i == ctx.partitions.size() - 14491                                 ? ctx.in.partEnd.get()4492                                 : ctx.partitions[i + 1].elfHeader.get();4493    write32(ctx, buf + 8, next->getVA() - ctx.partitions[i].elfHeader->getVA());4494 4495    va += 12;4496    buf += 12;4497  }4498}4499 4500static bool needsInterpSection(Ctx &ctx) {4501  return !ctx.arg.relocatable && !ctx.arg.shared &&4502         !ctx.arg.dynamicLinker.empty() && ctx.script->needsInterpSection();4503}4504 4505bool elf::hasMemtag(Ctx &ctx) {4506  return ctx.arg.emachine == EM_AARCH64 &&4507         ctx.arg.androidMemtagMode != ELF::NT_MEMTAG_LEVEL_NONE;4508}4509 4510// Fully static executables don't support MTE globals at this point in time, as4511// we currently rely on:4512//   - A dynamic loader to process relocations, and4513//   - Dynamic entries.4514// This restriction could be removed in future by re-using some of the ideas4515// that ifuncs use in fully static executables.4516bool elf::canHaveMemtagGlobals(Ctx &ctx) {4517  return hasMemtag(ctx) &&4518         (ctx.arg.relocatable || ctx.arg.shared || needsInterpSection(ctx));4519}4520 4521constexpr char kMemtagAndroidNoteName[] = "Android";4522void MemtagAndroidNote::writeTo(uint8_t *buf) {4523  static_assert(4524      sizeof(kMemtagAndroidNoteName) == 8,4525      "Android 11 & 12 have an ABI that the note name is 8 bytes long. Keep it "4526      "that way for backwards compatibility.");4527 4528  write32(ctx, buf, sizeof(kMemtagAndroidNoteName));4529  write32(ctx, buf + 4, sizeof(uint32_t));4530  write32(ctx, buf + 8, ELF::NT_ANDROID_TYPE_MEMTAG);4531  memcpy(buf + 12, kMemtagAndroidNoteName, sizeof(kMemtagAndroidNoteName));4532  buf += 12 + alignTo(sizeof(kMemtagAndroidNoteName), 4);4533 4534  uint32_t value = 0;4535  value |= ctx.arg.androidMemtagMode;4536  if (ctx.arg.androidMemtagHeap)4537    value |= ELF::NT_MEMTAG_HEAP;4538  // Note, MTE stack is an ABI break. Attempting to run an MTE stack-enabled4539  // binary on Android 11 or 12 will result in a checkfail in the loader.4540  if (ctx.arg.androidMemtagStack)4541    value |= ELF::NT_MEMTAG_STACK;4542  write32(ctx, buf, value); // note value4543}4544 4545size_t MemtagAndroidNote::getSize() const {4546  return sizeof(llvm::ELF::Elf64_Nhdr) +4547         /*namesz=*/alignTo(sizeof(kMemtagAndroidNoteName), 4) +4548         /*descsz=*/sizeof(uint32_t);4549}4550 4551void PackageMetadataNote::writeTo(uint8_t *buf) {4552  write32(ctx, buf, 4);4553  write32(ctx, buf + 4, ctx.arg.packageMetadata.size() + 1);4554  write32(ctx, buf + 8, FDO_PACKAGING_METADATA);4555  memcpy(buf + 12, "FDO", 4);4556  memcpy(buf + 16, ctx.arg.packageMetadata.data(),4557         ctx.arg.packageMetadata.size());4558}4559 4560size_t PackageMetadataNote::getSize() const {4561  return sizeof(llvm::ELF::Elf64_Nhdr) + 4 +4562         alignTo(ctx.arg.packageMetadata.size() + 1, 4);4563}4564 4565// Helper function, return the size of the ULEB128 for 'v', optionally writing4566// it to `*(buf + offset)` if `buf` is non-null.4567static size_t computeOrWriteULEB128(uint64_t v, uint8_t *buf, size_t offset) {4568  if (buf)4569    return encodeULEB128(v, buf + offset);4570  return getULEB128Size(v);4571}4572 4573// https://github.com/ARM-software/abi-aa/blob/main/memtagabielf64/memtagabielf64.rst#83encoding-of-sht_aarch64_memtag_globals_dynamic4574constexpr uint64_t kMemtagStepSizeBits = 3;4575constexpr uint64_t kMemtagGranuleSize = 16;4576static size_t4577createMemtagGlobalDescriptors(Ctx &ctx,4578                              const SmallVector<const Symbol *, 0> &symbols,4579                              uint8_t *buf = nullptr) {4580  size_t sectionSize = 0;4581  uint64_t lastGlobalEnd = 0;4582 4583  for (const Symbol *sym : symbols) {4584    if (!includeInSymtab(ctx, *sym))4585      continue;4586    const uint64_t addr = sym->getVA(ctx);4587    const uint64_t size = sym->getSize();4588 4589    if (addr <= kMemtagGranuleSize && buf != nullptr)4590      Err(ctx) << "address of the tagged symbol \"" << sym->getName()4591               << "\" falls in the ELF header. This is indicative of a "4592                  "compiler/linker bug";4593    if (addr % kMemtagGranuleSize != 0)4594      Err(ctx) << "address of the tagged symbol \"" << sym->getName()4595               << "\" at 0x" << Twine::utohexstr(addr)4596               << "\" is not granule (16-byte) aligned";4597    if (size == 0)4598      Err(ctx) << "size of the tagged symbol \"" << sym->getName()4599               << "\" is not allowed to be zero";4600    if (size % kMemtagGranuleSize != 0)4601      Err(ctx) << "size of the tagged symbol \"" << sym->getName()4602               << "\" (size 0x" << Twine::utohexstr(size)4603               << ") is not granule (16-byte) aligned";4604 4605    const uint64_t sizeToEncode = size / kMemtagGranuleSize;4606    const uint64_t stepToEncode = ((addr - lastGlobalEnd) / kMemtagGranuleSize)4607                                  << kMemtagStepSizeBits;4608    if (sizeToEncode < (1 << kMemtagStepSizeBits)) {4609      sectionSize += computeOrWriteULEB128(stepToEncode | sizeToEncode, buf, sectionSize);4610    } else {4611      sectionSize += computeOrWriteULEB128(stepToEncode, buf, sectionSize);4612      sectionSize += computeOrWriteULEB128(sizeToEncode - 1, buf, sectionSize);4613    }4614    lastGlobalEnd = addr + size;4615  }4616 4617  return sectionSize;4618}4619 4620bool MemtagGlobalDescriptors::updateAllocSize(Ctx &ctx) {4621  size_t oldSize = getSize();4622  llvm::stable_sort(symbols, [&ctx = ctx](const Symbol *s1, const Symbol *s2) {4623    return s1->getVA(ctx) < s2->getVA(ctx);4624  });4625  return oldSize != getSize();4626}4627 4628void MemtagGlobalDescriptors::writeTo(uint8_t *buf) {4629  createMemtagGlobalDescriptors(ctx, symbols, buf);4630}4631 4632size_t MemtagGlobalDescriptors::getSize() const {4633  return createMemtagGlobalDescriptors(ctx, symbols);4634}4635 4636static OutputSection *findSection(Ctx &ctx, StringRef name) {4637  for (SectionCommand *cmd : ctx.script->sectionCommands)4638    if (auto *osd = dyn_cast<OutputDesc>(cmd))4639      if (osd->osec.name == name)4640        return &osd->osec;4641  return nullptr;4642}4643 4644static Defined *addOptionalRegular(Ctx &ctx, StringRef name, SectionBase *sec,4645                                   uint64_t val, uint8_t stOther = STV_HIDDEN) {4646  Symbol *s = ctx.symtab->find(name);4647  if (!s || s->isDefined() || s->isCommon())4648    return nullptr;4649 4650  s->resolve(ctx, Defined{ctx, ctx.internalFile, StringRef(), STB_GLOBAL,4651                          stOther, STT_NOTYPE, val,4652                          /*size=*/0, sec});4653  s->isUsedInRegularObj = true;4654  return cast<Defined>(s);4655}4656 4657template <class ELFT> void elf::createSyntheticSections(Ctx &ctx) {4658  // Add the .interp section first because it is not a SyntheticSection.4659  // The removeUnusedSyntheticSections() function relies on the4660  // SyntheticSections coming last.4661  if (needsInterpSection(ctx)) {4662    for (size_t i = 1; i <= ctx.partitions.size(); ++i) {4663      InputSection *sec = createInterpSection(ctx);4664      sec->partition = i;4665      ctx.inputSections.push_back(sec);4666    }4667  }4668 4669  auto add = [&](SyntheticSection &sec) { ctx.inputSections.push_back(&sec); };4670 4671  if (ctx.arg.zSectionHeader)4672    ctx.in.shStrTab =4673        std::make_unique<StringTableSection>(ctx, ".shstrtab", false);4674 4675  ctx.out.programHeaders =4676      std::make_unique<OutputSection>(ctx, "", 0, SHF_ALLOC);4677  ctx.out.programHeaders->addralign = ctx.arg.wordsize;4678 4679  if (ctx.arg.strip != StripPolicy::All) {4680    ctx.in.strTab = std::make_unique<StringTableSection>(ctx, ".strtab", false);4681    ctx.in.symTab =4682        std::make_unique<SymbolTableSection<ELFT>>(ctx, *ctx.in.strTab);4683    ctx.in.symTabShndx = std::make_unique<SymtabShndxSection>(ctx);4684  }4685 4686  ctx.in.bss = std::make_unique<BssSection>(ctx, ".bss", 0, 1);4687  add(*ctx.in.bss);4688 4689  // If there is a SECTIONS command and a .data.rel.ro section name use name4690  // .data.rel.ro.bss so that we match in the .data.rel.ro output section.4691  // This makes sure our relro is contiguous.4692  bool hasDataRelRo =4693      ctx.script->hasSectionsCommand && findSection(ctx, ".data.rel.ro");4694  ctx.in.bssRelRo = std::make_unique<BssSection>(4695      ctx, hasDataRelRo ? ".data.rel.ro.bss" : ".bss.rel.ro", 0, 1);4696  add(*ctx.in.bssRelRo);4697 4698  // Add MIPS-specific sections.4699  if (ctx.arg.emachine == EM_MIPS) {4700    if (!ctx.arg.shared && ctx.hasDynsym) {4701      ctx.in.mipsRldMap = std::make_unique<MipsRldMapSection>(ctx);4702      add(*ctx.in.mipsRldMap);4703    }4704    if ((ctx.in.mipsAbiFlags = MipsAbiFlagsSection<ELFT>::create(ctx)))4705      add(*ctx.in.mipsAbiFlags);4706    if ((ctx.in.mipsOptions = MipsOptionsSection<ELFT>::create(ctx)))4707      add(*ctx.in.mipsOptions);4708    if ((ctx.in.mipsReginfo = MipsReginfoSection<ELFT>::create(ctx)))4709      add(*ctx.in.mipsReginfo);4710  }4711 4712  StringRef relaDynName = ctx.arg.isRela ? ".rela.dyn" : ".rel.dyn";4713 4714  const unsigned threadCount = ctx.arg.threadCount;4715  for (Partition &part : ctx.partitions) {4716    auto add = [&](SyntheticSection &sec) {4717      sec.partition = part.getNumber(ctx);4718      ctx.inputSections.push_back(&sec);4719    };4720 4721    if (!part.name.empty()) {4722      part.elfHeader = std::make_unique<PartitionElfHeaderSection<ELFT>>(ctx);4723      part.elfHeader->name = part.name;4724      add(*part.elfHeader);4725 4726      part.programHeaders =4727          std::make_unique<PartitionProgramHeadersSection<ELFT>>(ctx);4728      add(*part.programHeaders);4729    }4730 4731    if (ctx.arg.buildId != BuildIdKind::None) {4732      part.buildId = std::make_unique<BuildIdSection>(ctx);4733      add(*part.buildId);4734    }4735 4736    // dynSymTab is always present to simplify several finalizeSections4737    // functions.4738    part.dynStrTab = std::make_unique<StringTableSection>(ctx, ".dynstr", true);4739    part.dynSymTab =4740        std::make_unique<SymbolTableSection<ELFT>>(ctx, *part.dynStrTab);4741 4742    if (ctx.arg.relocatable)4743      continue;4744    part.dynamic = std::make_unique<DynamicSection<ELFT>>(ctx);4745 4746    if (hasMemtag(ctx)) {4747      part.memtagAndroidNote = std::make_unique<MemtagAndroidNote>(ctx);4748      add(*part.memtagAndroidNote);4749      if (canHaveMemtagGlobals(ctx)) {4750        part.memtagGlobalDescriptors =4751            std::make_unique<MemtagGlobalDescriptors>(ctx);4752        add(*part.memtagGlobalDescriptors);4753      }4754    }4755 4756    if (ctx.arg.androidPackDynRelocs)4757      part.relaDyn = std::make_unique<AndroidPackedRelocationSection<ELFT>>(4758          ctx, relaDynName, threadCount);4759    else4760      part.relaDyn = std::make_unique<RelocationSection<ELFT>>(4761          ctx, relaDynName, ctx.arg.zCombreloc, threadCount);4762 4763    if (ctx.hasDynsym) {4764      add(*part.dynSymTab);4765 4766      part.verSym = std::make_unique<VersionTableSection>(ctx);4767      add(*part.verSym);4768 4769      if (!namedVersionDefs(ctx).empty()) {4770        part.verDef = std::make_unique<VersionDefinitionSection>(ctx);4771        add(*part.verDef);4772      }4773 4774      part.verNeed = std::make_unique<VersionNeedSection<ELFT>>(ctx);4775      add(*part.verNeed);4776 4777      if (ctx.arg.gnuHash) {4778        part.gnuHashTab = std::make_unique<GnuHashTableSection>(ctx);4779        add(*part.gnuHashTab);4780      }4781 4782      if (ctx.arg.sysvHash) {4783        part.hashTab = std::make_unique<HashTableSection>(ctx);4784        add(*part.hashTab);4785      }4786 4787      add(*part.dynamic);4788      add(*part.dynStrTab);4789    }4790    add(*part.relaDyn);4791 4792    if (ctx.arg.relrPackDynRelocs) {4793      part.relrDyn = std::make_unique<RelrSection<ELFT>>(ctx, threadCount);4794      add(*part.relrDyn);4795      part.relrAuthDyn = std::make_unique<RelrSection<ELFT>>(4796          ctx, threadCount, /*isAArch64Auth=*/true);4797      add(*part.relrAuthDyn);4798    }4799 4800    if (ctx.arg.ehFrameHdr) {4801      part.ehFrameHdr = std::make_unique<EhFrameHeader>(ctx);4802      add(*part.ehFrameHdr);4803    }4804    part.ehFrame = std::make_unique<EhFrameSection>(ctx);4805    add(*part.ehFrame);4806 4807    if (ctx.arg.emachine == EM_ARM) {4808      // This section replaces all the individual .ARM.exidx InputSections.4809      part.armExidx = std::make_unique<ARMExidxSyntheticSection>(ctx);4810      add(*part.armExidx);4811    }4812 4813    if (!ctx.arg.packageMetadata.empty()) {4814      part.packageMetadataNote = std::make_unique<PackageMetadataNote>(ctx);4815      add(*part.packageMetadataNote);4816    }4817  }4818 4819  if (ctx.partitions.size() != 1) {4820    // Create the partition end marker. This needs to be in partition number 2554821    // so that it is sorted after all other partitions. It also has other4822    // special handling (see createPhdrs() and combineEhSections()).4823    ctx.in.partEnd =4824        std::make_unique<BssSection>(ctx, ".part.end", ctx.arg.maxPageSize, 1);4825    ctx.in.partEnd->partition = 255;4826    add(*ctx.in.partEnd);4827 4828    ctx.in.partIndex = std::make_unique<PartitionIndexSection>(ctx);4829    addOptionalRegular(ctx, "__part_index_begin", ctx.in.partIndex.get(), 0);4830    addOptionalRegular(ctx, "__part_index_end", ctx.in.partIndex.get(),4831                       ctx.in.partIndex->getSize());4832    add(*ctx.in.partIndex);4833  }4834 4835  // Add .got. MIPS' .got is so different from the other archs,4836  // it has its own class.4837  if (ctx.arg.emachine == EM_MIPS) {4838    ctx.in.mipsGot = std::make_unique<MipsGotSection>(ctx);4839    add(*ctx.in.mipsGot);4840  } else {4841    ctx.in.got = std::make_unique<GotSection>(ctx);4842    add(*ctx.in.got);4843  }4844 4845  if (ctx.arg.emachine == EM_PPC) {4846    ctx.in.ppc32Got2 = std::make_unique<PPC32Got2Section>(ctx);4847    add(*ctx.in.ppc32Got2);4848  }4849 4850  if (ctx.arg.emachine == EM_PPC64) {4851    ctx.in.ppc64LongBranchTarget =4852        std::make_unique<PPC64LongBranchTargetSection>(ctx);4853    add(*ctx.in.ppc64LongBranchTarget);4854  }4855 4856  ctx.in.gotPlt = std::make_unique<GotPltSection>(ctx);4857  add(*ctx.in.gotPlt);4858  ctx.in.igotPlt = std::make_unique<IgotPltSection>(ctx);4859  add(*ctx.in.igotPlt);4860  // Add .relro_padding if DATA_SEGMENT_RELRO_END is used; otherwise, add the4861  // section in the absence of PHDRS/SECTIONS commands.4862  if (ctx.arg.zRelro &&4863      ((ctx.script->phdrsCommands.empty() && !ctx.script->hasSectionsCommand) ||4864       ctx.script->seenRelroEnd)) {4865    ctx.in.relroPadding = std::make_unique<RelroPaddingSection>(ctx);4866    add(*ctx.in.relroPadding);4867  }4868 4869  if (ctx.arg.emachine == EM_ARM) {4870    ctx.in.armCmseSGSection = std::make_unique<ArmCmseSGSection>(ctx);4871    add(*ctx.in.armCmseSGSection);4872  }4873 4874  // _GLOBAL_OFFSET_TABLE_ is defined relative to either .got.plt or .got. Treat4875  // it as a relocation and ensure the referenced section is created.4876  if (ctx.sym.globalOffsetTable && ctx.arg.emachine != EM_MIPS) {4877    if (ctx.target->gotBaseSymInGotPlt)4878      ctx.in.gotPlt->hasGotPltOffRel = true;4879    else4880      ctx.in.got->hasGotOffRel = true;4881  }4882 4883  // We always need to add rel[a].plt to output if it has entries.4884  // Even for static linking it can contain R_[*]_IRELATIVE relocations.4885  ctx.in.relaPlt = std::make_unique<RelocationSection<ELFT>>(4886      ctx, ctx.arg.isRela ? ".rela.plt" : ".rel.plt", /*sort=*/false,4887      /*threadCount=*/1);4888  add(*ctx.in.relaPlt);4889 4890  if ((ctx.arg.emachine == EM_386 || ctx.arg.emachine == EM_X86_64) &&4891      (ctx.arg.andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT)) {4892    ctx.in.ibtPlt = std::make_unique<IBTPltSection>(ctx);4893    add(*ctx.in.ibtPlt);4894  }4895 4896  if (ctx.arg.emachine == EM_PPC)4897    ctx.in.plt = std::make_unique<PPC32GlinkSection>(ctx);4898  else4899    ctx.in.plt = std::make_unique<PltSection>(ctx);4900  add(*ctx.in.plt);4901  ctx.in.iplt = std::make_unique<IpltSection>(ctx);4902  add(*ctx.in.iplt);4903 4904  if (ctx.arg.andFeatures || ctx.aarch64PauthAbiCoreInfo) {4905    ctx.in.gnuProperty = std::make_unique<GnuPropertySection>(ctx);4906    add(*ctx.in.gnuProperty);4907  }4908 4909  if (ctx.arg.debugNames) {4910    ctx.in.debugNames = std::make_unique<DebugNamesSection<ELFT>>(ctx);4911    add(*ctx.in.debugNames);4912  }4913 4914  if (ctx.arg.gdbIndex) {4915    ctx.in.gdbIndex = GdbIndexSection::create<ELFT>(ctx);4916    add(*ctx.in.gdbIndex);4917  }4918 4919  // .note.GNU-stack is always added when we are creating a re-linkable4920  // object file. Other linkers are using the presence of this marker4921  // section to control the executable-ness of the stack area, but that4922  // is irrelevant these days. Stack area should always be non-executable4923  // by default. So we emit this section unconditionally.4924  if (ctx.arg.relocatable) {4925    ctx.in.gnuStack = std::make_unique<GnuStackSection>(ctx);4926    add(*ctx.in.gnuStack);4927  }4928 4929  if (ctx.in.symTab)4930    add(*ctx.in.symTab);4931  if (ctx.in.symTabShndx)4932    add(*ctx.in.symTabShndx);4933  if (ctx.in.shStrTab)4934    add(*ctx.in.shStrTab);4935  if (ctx.in.strTab)4936    add(*ctx.in.strTab);4937}4938 4939template void elf::splitSections<ELF32LE>(Ctx &);4940template void elf::splitSections<ELF32BE>(Ctx &);4941template void elf::splitSections<ELF64LE>(Ctx &);4942template void elf::splitSections<ELF64BE>(Ctx &);4943 4944template void EhFrameSection::iterateFDEWithLSDA<ELF32LE>(4945    function_ref<void(InputSection &)>);4946template void EhFrameSection::iterateFDEWithLSDA<ELF32BE>(4947    function_ref<void(InputSection &)>);4948template void EhFrameSection::iterateFDEWithLSDA<ELF64LE>(4949    function_ref<void(InputSection &)>);4950template void EhFrameSection::iterateFDEWithLSDA<ELF64BE>(4951    function_ref<void(InputSection &)>);4952 4953template class elf::SymbolTableSection<ELF32LE>;4954template class elf::SymbolTableSection<ELF32BE>;4955template class elf::SymbolTableSection<ELF64LE>;4956template class elf::SymbolTableSection<ELF64BE>;4957 4958template void elf::writeEhdr<ELF32LE>(Ctx &, uint8_t *Buf, Partition &Part);4959template void elf::writeEhdr<ELF32BE>(Ctx &, uint8_t *Buf, Partition &Part);4960template void elf::writeEhdr<ELF64LE>(Ctx &, uint8_t *Buf, Partition &Part);4961template void elf::writeEhdr<ELF64BE>(Ctx &, uint8_t *Buf, Partition &Part);4962 4963template void elf::writePhdrs<ELF32LE>(uint8_t *Buf, Partition &Part);4964template void elf::writePhdrs<ELF32BE>(uint8_t *Buf, Partition &Part);4965template void elf::writePhdrs<ELF64LE>(uint8_t *Buf, Partition &Part);4966template void elf::writePhdrs<ELF64BE>(uint8_t *Buf, Partition &Part);4967 4968template void elf::createSyntheticSections<ELF32LE>(Ctx &);4969template void elf::createSyntheticSections<ELF32BE>(Ctx &);4970template void elf::createSyntheticSections<ELF64LE>(Ctx &);4971template void elf::createSyntheticSections<ELF64BE>(Ctx &);4972