SyntheticSections.cpp

//===- SyntheticSections.cpp ----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains linker-synthesized sections. Currently,
// synthetic sections are created either output sections or input sections,
// but we are rewriting code so that all synthetic sections are created as
// input sections.
//
//===----------------------------------------------------------------------===//

#include"SyntheticSections.h"
#include"Config.h"
#include"InputFiles.h"
#include"LinkerScript.h"
#include"OutputSections.h"
#include"SymbolTable.h"
#include"Symbols.h"
#include"Target.h"
#include"Writer.h"
#include"lld/Common/ErrorHandler.h"
#include"lld/Common/Memory.h"
#include"lld/Common/Strings.h"
#include"lld/Common/Threads.h"
#include"lld/Common/Version.h"
#include"llvm/ADT/SetOperations.h"
#include"llvm/ADT/StringExtras.h"
#include"llvm/BinaryFormat/Dwarf.h"
#include"llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
#include"llvm/Object/ELFObjectFile.h"
#include"llvm/Support/Compression.h"
#include"llvm/Support/Endian.h"
#include"llvm/Support/LEB128.h"
#include"llvm/Support/MD5.h"
#include<cstdlib>
#include<thread>

usingnamespacellvm;
usingnamespacellvm::dwarf;
usingnamespacellvm::ELF;
usingnamespacellvm::object;
usingnamespacellvm::support;

usingnamespacelld;
usingnamespacelld::elf;

using llvm::support::endian::read32le;
using llvm::support::endian::write32le;
using llvm::support::endian::write64le;

constexprsize_t MergeNoTailSection::NumShards;

staticuint64_treadUint(uint8_t *Buf) {
return Config->Is64 ? read64(Buf) : read32(Buf);
}

staticvoidwriteUint(uint8_t *Buf, uint64_t Val) {
if (Config->Is64)
write64(Buf, Val);
else
write32(Buf, Val);
}

// Returns an LLD version string.
static ArrayRef<uint8_t> getVersion() {
// Check LLD_VERSION first for ease of testing.
// You can get consistent output by using the environment variable.
// This is only for testing.
 StringRef S = getenv("LLD_VERSION");
if (S.empty())
 S = Saver.save(Twine("Linker: ") + getLLDVersion());

// +1 to include the terminating '\0'.
return {(constuint8_t *)S.data(), S.size() + 1};
}

// Creates a .comment section containing LLD version info.
// With this feature, you can identify LLD-generated binaries easily
// by "readelf --string-dump .comment <file>".
// The returned object is a mergeable string section.
MergeInputSection *elf::createCommentSection() {
return make<MergeInputSection>(SHF_MERGE | SHF_STRINGS, SHT_PROGBITS, 1,
getVersion(), ".comment");
}

// .MIPS.abiflags section.
template <classELFT>
MipsAbiFlagsSection<ELFT>::MipsAbiFlagsSection(Elf_Mips_ABIFlags Flags)
 : SyntheticSection(SHF_ALLOC, SHT_MIPS_ABIFLAGS, 8, ".MIPS.abiflags"),
Flags(Flags) {
this->Entsize = sizeof(Elf_Mips_ABIFlags);
}

template <classELFT> void MipsAbiFlagsSection<ELFT>::writeTo(uint8_t *Buf) {
memcpy(Buf, &Flags, sizeof(Flags));
}

template <classELFT>
MipsAbiFlagsSection<ELFT> *MipsAbiFlagsSection<ELFT>::create() {
 Elf_Mips_ABIFlags Flags = {};
bool Create = false;

for (InputSectionBase *Sec : InputSections) {
if (Sec->Type != SHT_MIPS_ABIFLAGS)
continue;
 Sec->markDead();
 Create = true;

 std::string Filename = toString(Sec->File);
constsize_tSize = Sec->data().size();
// Older version of BFD (such as the default FreeBSD linker) concatenate
// .MIPS.abiflags instead of merging. To allow for this case (or potential
// zero padding) we ignore everything after the first Elf_Mips_ABIFlags
if (Size < sizeof(Elf_Mips_ABIFlags)) {
error(Filename + ": invalid size of .MIPS.abiflags section: got " +
Twine(Size) + " instead of " + Twine(sizeof(Elf_Mips_ABIFlags)));
returnnullptr;
 }
auto *S = reinterpret_cast<const Elf_Mips_ABIFlags *>(Sec->data().data());
if (S->version != 0) {
error(Filename + ": unexpected .MIPS.abiflags version " +
Twine(S->version));
returnnullptr;
 }

// LLD checks ISA compatibility in calcMipsEFlags(). Here we just
// select the highest number of ISA/Rev/Ext.
 Flags.isa_level = std::max(Flags.isa_level, S->isa_level);
 Flags.isa_rev = std::max(Flags.isa_rev, S->isa_rev);
 Flags.isa_ext = std::max(Flags.isa_ext, S->isa_ext);
 Flags.gpr_size = std::max(Flags.gpr_size, S->gpr_size);
 Flags.cpr1_size = std::max(Flags.cpr1_size, S->cpr1_size);
 Flags.cpr2_size = std::max(Flags.cpr2_size, S->cpr2_size);
 Flags.ases |= S->ases;
 Flags.flags1 |= S->flags1;
 Flags.flags2 |= S->flags2;
 Flags.fp_abi = elf::getMipsFpAbiFlag(Flags.fp_abi, S->fp_abi, Filename);
 };

if (Create)
return make<MipsAbiFlagsSection<ELFT>>(Flags);
returnnullptr;
}

// .MIPS.options section.
template <classELFT>
MipsOptionsSection<ELFT>::MipsOptionsSection(Elf_Mips_RegInfo Reginfo)
 : SyntheticSection(SHF_ALLOC, SHT_MIPS_OPTIONS, 8, ".MIPS.options"),
Reginfo(Reginfo) {
this->Entsize = sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);
}

template <classELFT> void MipsOptionsSection<ELFT>::writeTo(uint8_t *Buf) {
auto *Options = reinterpret_cast<Elf_Mips_Options *>(Buf);
 Options->kind = ODK_REGINFO;
 Options->size = getSize();

if (!Config->Relocatable)
 Reginfo.ri_gp_value = In.MipsGot->getGp();
memcpy(Buf + sizeof(Elf_Mips_Options), &Reginfo, sizeof(Reginfo));
}

template <classELFT>
MipsOptionsSection<ELFT> *MipsOptionsSection<ELFT>::create() {
// N64 ABI only.
if (!ELFT::Is64Bits)
returnnullptr;

 std::vector<InputSectionBase *> Sections;
for (InputSectionBase *Sec : InputSections)
if (Sec->Type == SHT_MIPS_OPTIONS)
 Sections.push_back(Sec);

if (Sections.empty())
returnnullptr;

 Elf_Mips_RegInfo Reginfo = {};
for (InputSectionBase *Sec : Sections) {
 Sec->markDead();

 std::string Filename = toString(Sec->File);
 ArrayRef<uint8_t> D = Sec->data();

while (!D.empty()) {
if (D.size() < sizeof(Elf_Mips_Options)) {
error(Filename + ": invalid size of .MIPS.options section");
break;
 }

auto *Opt = reinterpret_cast<const Elf_Mips_Options *>(D.data());
if (Opt->kind == ODK_REGINFO) {
 Reginfo.ri_gprmask |= Opt->getRegInfo().ri_gprmask;
 Sec->getFile<ELFT>()->MipsGp0 = Opt->getRegInfo().ri_gp_value;
break;
 }

if (!Opt->size)
fatal(Filename + ": zero option descriptor size");
 D = D.slice(Opt->size);
 }
 };

return make<MipsOptionsSection<ELFT>>(Reginfo);
}

// MIPS .reginfo section.
template <classELFT>
MipsReginfoSection<ELFT>::MipsReginfoSection(Elf_Mips_RegInfo Reginfo)
 : SyntheticSection(SHF_ALLOC, SHT_MIPS_REGINFO, 4, ".reginfo"),
Reginfo(Reginfo) {
this->Entsize = sizeof(Elf_Mips_RegInfo);
}

template <classELFT> void MipsReginfoSection<ELFT>::writeTo(uint8_t *Buf) {
if (!Config->Relocatable)
 Reginfo.ri_gp_value = In.MipsGot->getGp();
memcpy(Buf, &Reginfo, sizeof(Reginfo));
}

template <classELFT>
MipsReginfoSection<ELFT> *MipsReginfoSection<ELFT>::create() {
// Section should be alive for O32 and N32 ABIs only.
if (ELFT::Is64Bits)
returnnullptr;

 std::vector<InputSectionBase *> Sections;
for (InputSectionBase *Sec : InputSections)
if (Sec->Type == SHT_MIPS_REGINFO)
 Sections.push_back(Sec);

if (Sections.empty())
returnnullptr;

 Elf_Mips_RegInfo Reginfo = {};
for (InputSectionBase *Sec : Sections) {
 Sec->markDead();

if (Sec->data().size() != sizeof(Elf_Mips_RegInfo)) {
error(toString(Sec->File) + ": invalid size of .reginfo section");
returnnullptr;
 }

auto *R = reinterpret_cast<const Elf_Mips_RegInfo *>(Sec->data().data());
 Reginfo.ri_gprmask |= R->ri_gprmask;
 Sec->getFile<ELFT>()->MipsGp0 = R->ri_gp_value;
 };

return make<MipsReginfoSection<ELFT>>(Reginfo);
}

InputSection *elf::createInterpSection() {
// StringSaver guarantees that the returned string ends with '\0'.
 StringRef S = Saver.save(Config->DynamicLinker);
 ArrayRef<uint8_t> Contents = {(constuint8_t *)S.data(), S.size() + 1};

auto *Sec = make<InputSection>(nullptr, SHF_ALLOC, SHT_PROGBITS, 1, Contents,
".interp");
 Sec->markLive();
return Sec;
}

Defined *elf::addSyntheticLocal(StringRef Name, uint8_t Type, uint64_t Value,
uint64_tSize, InputSectionBase &Section) {
auto *S = make<Defined>(Section.File, Name, STB_LOCAL, STV_DEFAULT, Type,
 Value, Size, &Section);
if (In.SymTab)
 In.SymTab->addSymbol(S);
return S;
}

staticsize_tgetHashSize() {
switch (Config->BuildId) {
case BuildIdKind::Fast:
return8;
case BuildIdKind::Md5:
case BuildIdKind::Uuid:
return16;
case BuildIdKind::Sha1:
return20;
case BuildIdKind::Hexstring:
return Config->BuildIdVector.size();
default:
llvm_unreachable("unknown BuildIdKind");
 }
}

// This class represents a linker-synthesized .note.gnu.property section.
//
// In x86 and AArch64, object files may contain feature flags indicating the
// features that they have used. The flags are stored in a .note.gnu.property
// section.
//
// lld reads the sections from input files and merges them by computing AND of
// the flags. The result is written as a new .note.gnu.property section.
//
// If the flag is zero (which indicates that the intersection of the feature
// sets is empty, or some input files didn't have .note.gnu.property sections),
// we don't create this section.
GnuPropertySection::GnuPropertySection()
 : SyntheticSection(llvm::ELF::SHF_ALLOC, llvm::ELF::SHT_NOTE, 4,
".note.gnu.property") {}

voidGnuPropertySection::writeTo(uint8_t *Buf) {
uint32_t FeatureAndType = Config->EMachine == EM_AARCH64
 ? GNU_PROPERTY_AARCH64_FEATURE_1_AND
 : GNU_PROPERTY_X86_FEATURE_1_AND;

write32(Buf, 4); // Name size
write32(Buf + 4, Config->Is64 ? 16 : 12); // Content size
write32(Buf + 8, NT_GNU_PROPERTY_TYPE_0); // Type
memcpy(Buf + 12, "GNU", 4); // Name string
write32(Buf + 16, FeatureAndType); // Feature type
write32(Buf + 20, 4); // Feature size
write32(Buf + 24, Config->AndFeatures); // Feature flags
if (Config->Is64)
write32(Buf + 28, 0); // Padding
}

size_tGnuPropertySection::getSize() const { return Config->Is64 ? 32 : 28; }

BuildIdSection::BuildIdSection()
 : SyntheticSection(SHF_ALLOC, SHT_NOTE, 4, ".note.gnu.build-id"),
 HashSize(getHashSize()) {}

voidBuildIdSection::writeTo(uint8_t *Buf) {
write32(Buf, 4); // Name size
write32(Buf + 4, HashSize); // Content size
write32(Buf + 8, NT_GNU_BUILD_ID); // Type
memcpy(Buf + 12, "GNU", 4); // Name string
 HashBuf = Buf + 16;
}

voidBuildIdSection::writeBuildId(ArrayRef<uint8_t> Buf) {
assert(Buf.size() == HashSize);
memcpy(HashBuf, Buf.data(), HashSize);
}

BssSection::BssSection(StringRef Name, uint64_tSize, uint32_t Alignment)
 : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_NOBITS, Alignment, Name) {
this->Bss = true;
this->Size = Size;
}

EhFrameSection::EhFrameSection()
 : SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 1, ".eh_frame") {}

// Search for an existing CIE record or create a new one.
// CIE records from input object files are uniquified by their contents
// and where their relocations point to.
template <classELFT, classRelTy>
CieRecord *EhFrameSection::addCie(EhSectionPiece &Cie, ArrayRef<RelTy> Rels) {
 Symbol *Personality = nullptr;
unsigned FirstRelI = Cie.FirstRelocation;
if (FirstRelI != (unsigned)-1)
 Personality =
 &Cie.Sec->templategetFile<ELFT>()->getRelocTargetSym(Rels[FirstRelI]);

// Search for an existing CIE by CIE contents/relocation target pair.
 CieRecord *&Rec = CieMap[{Cie.data(), Personality}];

// If not found, create a new one.
if (!Rec) {
 Rec = make<CieRecord>();
 Rec->Cie = &Cie;
 CieRecords.push_back(Rec);
 }
return Rec;
}

// There is one FDE per function. Returns true if a given FDE
// points to a live function.
template <classELFT, classRelTy>
boolEhFrameSection::isFdeLive(EhSectionPiece &Fde, ArrayRef<RelTy> Rels) {
auto *Sec = cast<EhInputSection>(Fde.Sec);
unsigned FirstRelI = Fde.FirstRelocation;

// An FDE should point to some function because FDEs are to describe
// functions. That's however not always the case due to an issue of
// ld.gold with -r. ld.gold may discard only functions and leave their
// corresponding FDEs, which results in creating bad .eh_frame sections.
// To deal with that, we ignore such FDEs.
if (FirstRelI == (unsigned)-1)
returnfalse;

const RelTy &Rel = Rels[FirstRelI];
 Symbol &B = Sec->templategetFile<ELFT>()->getRelocTargetSym(Rel);

// FDEs for garbage-collected or merged-by-ICF sections, or sections in
// another partition, are dead.
if (auto *D = dyn_cast<Defined>(&B))
if (SectionBase *Sec = D->Section)
return Sec->Partition == Partition;
returnfalse;
}

// .eh_frame is a sequence of CIE or FDE records. In general, there
// is one CIE record per input object file which is followed by
// a list of FDEs. This function searches an existing CIE or create a new
// one and associates FDEs to the CIE.
template <classELFT, classRelTy>
voidEhFrameSection::addSectionAux(EhInputSection *Sec, ArrayRef<RelTy> Rels) {
 OffsetToCie.clear();
for (EhSectionPiece &Piece : Sec->Pieces) {
// The empty record is the end marker.
if (Piece.Size == 4)
return;

size_t Offset = Piece.InputOff;
uint32_t ID = read32(Piece.data().data() + 4);
if (ID == 0) {
 OffsetToCie[Offset] = addCie<ELFT>(Piece, Rels);
continue;
 }

uint32_t CieOffset = Offset + 4 - ID;
 CieRecord *Rec = OffsetToCie[CieOffset];
if (!Rec)
fatal(toString(Sec) + ": invalid CIE reference");

if (!isFdeLive<ELFT>(Piece, Rels))
continue;
 Rec->Fdes.push_back(&Piece);
 NumFdes++;
 }
}

template <classELFT> voidEhFrameSection::addSection(InputSectionBase *C) {
auto *Sec = cast<EhInputSection>(C);
 Sec->Parent = this;

 Alignment = std::max(Alignment, Sec->Alignment);
 Sections.push_back(Sec);

for (auto *DS : Sec->DependentSections)
 DependentSections.push_back(DS);

if (Sec->Pieces.empty())
return;

if (Sec->AreRelocsRela)
 addSectionAux<ELFT>(Sec, Sec->templaterelas<ELFT>());
else
 addSectionAux<ELFT>(Sec, Sec->templaterels<ELFT>());
}

staticvoidwriteCieFde(uint8_t *Buf, ArrayRef<uint8_t> D) {
memcpy(Buf, D.data(), D.size());

size_t Aligned = alignTo(D.size(), Config->Wordsize);

// Zero-clear trailing padding if it exists.
memset(Buf + D.size(), 0, Aligned - D.size());

// Fix the size field. -4 since size does not include the size field itself.
write32(Buf, Aligned - 4);
}

voidEhFrameSection::finalizeContents() {
assert(!this->Size); // Not finalized.
size_t Off = 0;
for (CieRecord *Rec : CieRecords) {
 Rec->Cie->OutputOff = Off;
 Off += alignTo(Rec->Cie->Size, Config->Wordsize);

for (EhSectionPiece *Fde : Rec->Fdes) {
 Fde->OutputOff = Off;
 Off += alignTo(Fde->Size, Config->Wordsize);
 }
 }

// The LSB standard does not allow a .eh_frame section with zero
// Call Frame Information records. glibc unwind-dw2-fde.c
// classify_object_over_fdes expects there is a CIE record length 0 as a
// terminator. Thus we add one unconditionally.
 Off += 4;

this->Size = Off;
}

// Returns data for .eh_frame_hdr. .eh_frame_hdr is a binary search table
// to get an FDE from an address to which FDE is applied. This function
// returns a list of such pairs.
std::vector<EhFrameSection::FdeData> EhFrameSection::getFdeData() const {
uint8_t *Buf = Out::BufferStart + getParent()->Offset + OutSecOff;
 std::vector<FdeData> Ret;

uint64_t VA = getPartition().EhFrameHdr->getVA();
for (CieRecord *Rec : CieRecords) {
uint8_t Enc = getFdeEncoding(Rec->Cie);
for (EhSectionPiece *Fde : Rec->Fdes) {
uint64_t Pc = getFdePc(Buf, Fde->OutputOff, Enc);
uint64_t FdeVA = getParent()->Addr + Fde->OutputOff;
if (!isInt<32>(Pc - VA))
fatal(toString(Fde->Sec) + ": PC offset is too large: 0x" +
Twine::utohexstr(Pc - VA));
 Ret.push_back({uint32_t(Pc - VA), uint32_t(FdeVA - VA)});
 }
 }

// Sort the FDE list by their PC and uniqueify. Usually there is only
// one FDE for a PC (i.e. function), but if ICF merges two functions
// into one, there can be more than one FDEs pointing to the address.
auto Less = [](const FdeData &A, const FdeData &B) {
return A.PcRel < B.PcRel;
 };
llvm::stable_sort(Ret, Less);
auto Eq = [](const FdeData &A, const FdeData &B) {
return A.PcRel == B.PcRel;
 };
 Ret.erase(std::unique(Ret.begin(), Ret.end(), Eq), Ret.end());

return Ret;
}

staticuint64_treadFdeAddr(uint8_t *Buf, intSize) {
switch (Size) {
case DW_EH_PE_udata2:
returnread16(Buf);
case DW_EH_PE_sdata2:
return (int16_t)read16(Buf);
case DW_EH_PE_udata4:
returnread32(Buf);
case DW_EH_PE_sdata4:
return (int32_t)read32(Buf);
case DW_EH_PE_udata8:
case DW_EH_PE_sdata8:
returnread64(Buf);
case DW_EH_PE_absptr:
returnreadUint(Buf);
 }
fatal("unknown FDE size encoding");
}

// Returns the VA to which a given FDE (on a mmap'ed buffer) is applied to.
// We need it to create .eh_frame_hdr section.
uint64_tEhFrameSection::getFdePc(uint8_t *Buf, size_t FdeOff,
uint8_t Enc) const {
// The starting address to which this FDE applies is
// stored at FDE + 8 byte.
size_t Off = FdeOff + 8;
uint64_t Addr = readFdeAddr(Buf + Off, Enc & 0xf);
if ((Enc & 0x70) == DW_EH_PE_absptr)
return Addr;
if ((Enc & 0x70) == DW_EH_PE_pcrel)
return Addr + getParent()->Addr + Off;
fatal("unknown FDE size relative encoding");
}

voidEhFrameSection::writeTo(uint8_t *Buf) {
// Write CIE and FDE records.
for (CieRecord *Rec : CieRecords) {
size_t CieOffset = Rec->Cie->OutputOff;
writeCieFde(Buf + CieOffset, Rec->Cie->data());

for (EhSectionPiece *Fde : Rec->Fdes) {
size_t Off = Fde->OutputOff;
writeCieFde(Buf + Off, Fde->data());

// FDE's second word should have the offset to an associated CIE.
// Write it.
write32(Buf + Off + 4, Off + 4 - CieOffset);
 }
 }

// Apply relocations. .eh_frame section contents are not contiguous
// in the output buffer, but relocateAlloc() still works because
// getOffset() takes care of discontiguous section pieces.
for (EhInputSection *S : Sections)
 S->relocateAlloc(Buf, nullptr);

if (getPartition().EhFrameHdr && getPartition().EhFrameHdr->getParent())
getPartition().EhFrameHdr->write();
}

GotSection::GotSection()
 : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, Config->Wordsize,
".got") {
// PPC64 saves the ElfSym::GlobalOffsetTable .TOC. as the first entry in the
// .got. If there are no references to .TOC. in the symbol table,
// ElfSym::GlobalOffsetTable will not be defined and we won't need to save
// .TOC. in the .got. When it is defined, we increase NumEntries by the number
// of entries used to emit ElfSym::GlobalOffsetTable.
if (ElfSym::GlobalOffsetTable && !Target->GotBaseSymInGotPlt)
 NumEntries += Target->GotHeaderEntriesNum;
}

voidGotSection::addEntry(Symbol &Sym) {
 Sym.GotIndex = NumEntries;
 ++NumEntries;
}

boolGotSection::addDynTlsEntry(Symbol &Sym) {
if (Sym.GlobalDynIndex != -1U)
returnfalse;
 Sym.GlobalDynIndex = NumEntries;
// Global Dynamic TLS entries take two GOT slots.
 NumEntries += 2;
returntrue;
}

// Reserves TLS entries for a TLS module ID and a TLS block offset.
// In total it takes two GOT slots.
boolGotSection::addTlsIndex() {
if (TlsIndexOff != uint32_t(-1))
returnfalse;
 TlsIndexOff = NumEntries * Config->Wordsize;
 NumEntries += 2;
returntrue;
}

uint64_tGotSection::getGlobalDynAddr(const Symbol &B) const {
returnthis->getVA() + B.GlobalDynIndex * Config->Wordsize;
}

uint64_tGotSection::getGlobalDynOffset(const Symbol &B) const {
return B.GlobalDynIndex * Config->Wordsize;
}

voidGotSection::finalizeContents() {
Size = NumEntries * Config->Wordsize;
}

boolGotSection::isNeeded() const {
// We need to emit a GOT even if it's empty if there's a relocation that is
// relative to GOT(such as GOTOFFREL).
return NumEntries || HasGotOffRel;
}

voidGotSection::writeTo(uint8_t *Buf) {
// Buf points to the start of this section's buffer,
// whereas InputSectionBase::relocateAlloc() expects its argument
// to point to the start of the output section.
 Target->writeGotHeader(Buf);
relocateAlloc(Buf - OutSecOff, Buf - OutSecOff + Size);
}

staticuint64_tgetMipsPageAddr(uint64_t Addr) {
return (Addr + 0x8000) & ~0xffff;
}

staticuint64_tgetMipsPageCount(uint64_tSize) {
return (Size + 0xfffe) / 0xffff + 1;
}

MipsGotSection::MipsGotSection()
 : SyntheticSection(SHF_ALLOC | SHF_WRITE | SHF_MIPS_GPREL, SHT_PROGBITS, 16,
".got") {}

voidMipsGotSection::addEntry(InputFile &File, Symbol &Sym, int64_t Addend,
 RelExpr Expr) {
 FileGot &G = getGot(File);
if (Expr == R_MIPS_GOT_LOCAL_PAGE) {
if (const OutputSection *OS = Sym.getOutputSection())
 G.PagesMap.insert({OS, {}});
else
 G.Local16.insert({{nullptr, getMipsPageAddr(Sym.getVA(Addend))}, 0});
 } elseif (Sym.isTls())
 G.Tls.insert({&Sym, 0});
elseif (Sym.IsPreemptible && Expr == R_ABS)
 G.Relocs.insert({&Sym, 0});
elseif (Sym.IsPreemptible)
 G.Global.insert({&Sym, 0});
elseif (Expr == R_MIPS_GOT_OFF32)
 G.Local32.insert({{&Sym, Addend}, 0});
else
 G.Local16.insert({{&Sym, Addend}, 0});
}

voidMipsGotSection::addDynTlsEntry(InputFile &File, Symbol &Sym) {
getGot(File).DynTlsSymbols.insert({&Sym, 0});
}

voidMipsGotSection::addTlsIndex(InputFile &File) {
getGot(File).DynTlsSymbols.insert({nullptr, 0});
}

size_tMipsGotSection::FileGot::getEntriesNum() const {
returngetPageEntriesNum() + Local16.size() + Global.size() + Relocs.size() +
 Tls.size() + DynTlsSymbols.size() * 2;
}

size_tMipsGotSection::FileGot::getPageEntriesNum() const {
size_t Num = 0;
for (const std::pair<const OutputSection *, FileGot::PageBlock> &P : PagesMap)
 Num += P.second.Count;
return Num;
}

size_tMipsGotSection::FileGot::getIndexedEntriesNum() const {
size_t Count = getPageEntriesNum() + Local16.size() + Global.size();
// If there are relocation-only entries in the GOT, TLS entries
// are allocated after them. TLS entries should be addressable
// by 16-bit index so count both reloc-only and TLS entries.
if (!Tls.empty() || !DynTlsSymbols.empty())
 Count += Relocs.size() + Tls.size() + DynTlsSymbols.size() * 2;
return Count;
}

MipsGotSection::FileGot &MipsGotSection::getGot(InputFile &F) {
if (!F.MipsGotIndex.hasValue()) {
 Gots.emplace_back();
 Gots.back().File = &F;
 F.MipsGotIndex = Gots.size() - 1;
 }
return Gots[*F.MipsGotIndex];
}

uint64_tMipsGotSection::getPageEntryOffset(const InputFile *F,
const Symbol &Sym,
int64_t Addend) const {
const FileGot &G = Gots[*F->MipsGotIndex];
uint64_t Index = 0;
if (const OutputSection *OutSec = Sym.getOutputSection()) {
uint64_t SecAddr = getMipsPageAddr(OutSec->Addr);
uint64_t SymAddr = getMipsPageAddr(Sym.getVA(Addend));
 Index = G.PagesMap.lookup(OutSec).FirstIndex + (SymAddr - SecAddr) / 0xffff;
 } else {
 Index = G.Local16.lookup({nullptr, getMipsPageAddr(Sym.getVA(Addend))});
 }
return Index * Config->Wordsize;
}

uint64_tMipsGotSection::getSymEntryOffset(const InputFile *F, const Symbol &S,
int64_t Addend) const {
const FileGot &G = Gots[*F->MipsGotIndex];
 Symbol *Sym = const_cast<Symbol *>(&S);
if (Sym->isTls())
return G.Tls.lookup(Sym) * Config->Wordsize;
if (Sym->IsPreemptible)
return G.Global.lookup(Sym) * Config->Wordsize;
return G.Local16.lookup({Sym, Addend}) * Config->Wordsize;
}

uint64_tMipsGotSection::getTlsIndexOffset(const InputFile *F) const {
const FileGot &G = Gots[*F->MipsGotIndex];
return G.DynTlsSymbols.lookup(nullptr) * Config->Wordsize;
}

uint64_tMipsGotSection::getGlobalDynOffset(const InputFile *F,
const Symbol &S) const {
const FileGot &G = Gots[*F->MipsGotIndex];
 Symbol *Sym = const_cast<Symbol *>(&S);
return G.DynTlsSymbols.lookup(Sym) * Config->Wordsize;
}

const Symbol *MipsGotSection::getFirstGlobalEntry() const {
if (Gots.empty())
returnnullptr;
const FileGot &PrimGot = Gots.front();
if (!PrimGot.Global.empty())
return PrimGot.Global.front().first;
if (!PrimGot.Relocs.empty())
return PrimGot.Relocs.front().first;
returnnullptr;
}

unsignedMipsGotSection::getLocalEntriesNum() const {
if (Gots.empty())
return HeaderEntriesNum;
return HeaderEntriesNum + Gots.front().getPageEntriesNum() +
 Gots.front().Local16.size();
}

boolMipsGotSection::tryMergeGots(FileGot &Dst, FileGot &Src, bool IsPrimary) {
 FileGot Tmp = Dst;
set_union(Tmp.PagesMap, Src.PagesMap);
set_union(Tmp.Local16, Src.Local16);
set_union(Tmp.Global, Src.Global);
set_union(Tmp.Relocs, Src.Relocs);
set_union(Tmp.Tls, Src.Tls);
set_union(Tmp.DynTlsSymbols, Src.DynTlsSymbols);

size_t Count = IsPrimary ? HeaderEntriesNum : 0;
 Count += Tmp.getIndexedEntriesNum();

if (Count * Config->Wordsize > Config->MipsGotSize)
returnfalse;

std::swap(Tmp, Dst);
returntrue;
}

voidMipsGotSection::finalizeContents() { updateAllocSize(); }

boolMipsGotSection::updateAllocSize() {
Size = HeaderEntriesNum * Config->Wordsize;
for (const FileGot &G : Gots)
Size += G.getEntriesNum() * Config->Wordsize;
returnfalse;
}

voidMipsGotSection::build() {
if (Gots.empty())
return;

 std::vector<FileGot> MergedGots(1);

// For each GOT move non-preemptible symbols from the `Global`
// to `Local16` list. Preemptible symbol might become non-preemptible
// one if, for example, it gets a related copy relocation.
for (FileGot &Got : Gots) {
for (auto &P: Got.Global)
if (!P.first->IsPreemptible)
 Got.Local16.insert({{P.first, 0}, 0});
 Got.Global.remove_if([&](const std::pair<Symbol *, size_t> &P) {
return !P.first->IsPreemptible;
 });
 }

// For each GOT remove "reloc-only" entry if there is "global"
// entry for the same symbol. And add local entries which indexed
// using 32-bit value at the end of 16-bit entries.
for (FileGot &Got : Gots) {
 Got.Relocs.remove_if([&](const std::pair<Symbol *, size_t> &P) {
return Got.Global.count(P.first);
 });
set_union(Got.Local16, Got.Local32);
 Got.Local32.clear();
 }

// Evaluate number of "reloc-only" entries in the resulting GOT.
// To do that put all unique "reloc-only" and "global" entries
// from all GOTs to the future primary GOT.
 FileGot *PrimGot = &MergedGots.front();
for (FileGot &Got : Gots) {
set_union(PrimGot->Relocs, Got.Global);
set_union(PrimGot->Relocs, Got.Relocs);
 Got.Relocs.clear();
 }

// Evaluate number of "page" entries in each GOT.
for (FileGot &Got : Gots) {
for (std::pair<const OutputSection *, FileGot::PageBlock> &P :
 Got.PagesMap) {
const OutputSection *OS = P.first;
uint64_t SecSize = 0;
for (BaseCommand *Cmd : OS->SectionCommands) {
if (auto *ISD = dyn_cast<InputSectionDescription>(Cmd))
for (InputSection *IS : ISD->Sections) {
uint64_t Off = alignTo(SecSize, IS->Alignment);
 SecSize = Off + IS->getSize();
 }
 }
 P.second.Count = getMipsPageCount(SecSize);
 }
 }

// Merge GOTs. Try to join as much as possible GOTs but do not exceed
// maximum GOT size. At first, try to fill the primary GOT because
// the primary GOT can be accessed in the most effective way. If it
// is not possible, try to fill the last GOT in the list, and finally
// create a new GOT if both attempts failed.
for (FileGot &SrcGot : Gots) {
 InputFile *File = SrcGot.File;
if (tryMergeGots(MergedGots.front(), SrcGot, true)) {
 File->MipsGotIndex = 0;
 } else {
// If this is the first time we failed to merge with the primary GOT,
// MergedGots.back() will also be the primary GOT. We must make sure not
// to try to merge again with IsPrimary=false, as otherwise, if the
// inputs are just right, we could allow the primary GOT to become 1 or 2
// words too big due to ignoring the header size.
if (MergedGots.size() == 1 ||
 !tryMergeGots(MergedGots.back(), SrcGot, false)) {
 MergedGots.emplace_back();
std::swap(MergedGots.back(), SrcGot);
 }
 File->MipsGotIndex = MergedGots.size() - 1;
 }
 }
std::swap(Gots, MergedGots);

// Reduce number of "reloc-only" entries in the primary GOT
// by substracting "global" entries exist in the primary GOT.
 PrimGot = &Gots.front();
 PrimGot->Relocs.remove_if([&](const std::pair<Symbol *, size_t> &P) {
return PrimGot->Global.count(P.first);
 });

// Calculate indexes for each GOT entry.
size_t Index = HeaderEntriesNum;
for (FileGot &Got : Gots) {
 Got.StartIndex = &Got == PrimGot ? 0 : Index;
for (std::pair<const OutputSection *, FileGot::PageBlock> &P :
 Got.PagesMap) {
// For each output section referenced by GOT page relocations calculate
// and save into PagesMap an upper bound of MIPS GOT entries required
// to store page addresses of local symbols. We assume the worst case -
// each 64kb page of the output section has at least one GOT relocation
// against it. And take in account the case when the section intersects
// page boundaries.
 P.second.FirstIndex = Index;
 Index += P.second.Count;
 }
for (auto &P: Got.Local16)
 P.second = Index++;
for (auto &P: Got.Global)
 P.second = Index++;
for (auto &P: Got.Relocs)
 P.second = Index++;
for (auto &P: Got.Tls)
 P.second = Index++;
for (auto &P: Got.DynTlsSymbols) {
 P.second = Index;
 Index += 2;
 }
 }

// Update Symbol::GotIndex field to use this
// value later in the `sortMipsSymbols` function.
for (auto &P : PrimGot->Global)
 P.first->GotIndex = P.second;
for (auto &P : PrimGot->Relocs)
 P.first->GotIndex = P.second;

// Create dynamic relocations.
for (FileGot &Got : Gots) {
// Create dynamic relocations for TLS entries.
for (std::pair<Symbol *, size_t> &P : Got.Tls) {
 Symbol *S = P.first;
uint64_t Offset = P.second * Config->Wordsize;
if (S->IsPreemptible)
 Main->RelaDyn->addReloc(Target->TlsGotRel, this, Offset, S);
 }
for (std::pair<Symbol *, size_t> &P : Got.DynTlsSymbols) {
 Symbol *S = P.first;
uint64_t Offset = P.second * Config->Wordsize;
if (S == nullptr) {
if (!Config->Pic)
continue;
 Main->RelaDyn->addReloc(Target->TlsModuleIndexRel, this, Offset, S);
 } else {
// When building a shared library we still need a dynamic relocation
// for the module index. Therefore only checking for
// S->IsPreemptible is not sufficient (this happens e.g. for
// thread-locals that have been marked as local through a linker script)
if (!S->IsPreemptible && !Config->Pic)
continue;
 Main->RelaDyn->addReloc(Target->TlsModuleIndexRel, this, Offset, S);
// However, we can skip writing the TLS offset reloc for non-preemptible
// symbols since it is known even in shared libraries
if (!S->IsPreemptible)
continue;
 Offset += Config->Wordsize;
 Main->RelaDyn->addReloc(Target->TlsOffsetRel, this, Offset, S);
 }
 }

// Do not create dynamic relocations for non-TLS
// entries in the primary GOT.
if (&Got == PrimGot)
continue;

// Dynamic relocations for "global" entries.
for (const std::pair<Symbol *, size_t> &P : Got.Global) {
uint64_t Offset = P.second * Config->Wordsize;
 Main->RelaDyn->addReloc(Target->RelativeRel, this, Offset, P.first);
 }
if (!Config->Pic)
continue;
// Dynamic relocations for "local" entries in case of PIC.
for (const std::pair<const OutputSection *, FileGot::PageBlock> &L :
 Got.PagesMap) {
size_t PageCount = L.second.Count;
for (size_t PI = 0; PI < PageCount; ++PI) {
uint64_t Offset = (L.second.FirstIndex + PI) * Config->Wordsize;
 Main->RelaDyn->addReloc({Target->RelativeRel, this, Offset, L.first,
int64_t(PI * 0x10000)});
 }
 }
for (const std::pair<GotEntry, size_t> &P : Got.Local16) {
uint64_t Offset = P.second * Config->Wordsize;
 Main->RelaDyn->addReloc({Target->RelativeRel, this, Offset, true,
 P.first.first, P.first.second});
 }
 }
}

boolMipsGotSection::isNeeded() const {
// We add the .got section to the result for dynamic MIPS target because
// its address and properties are mentioned in the .dynamic section.
return !Config->Relocatable;
}

uint64_tMipsGotSection::getGp(const InputFile *F) const {
// For files without related GOT or files refer a primary GOT
// returns "common" _gp value. For secondary GOTs calculate
// individual _gp values.
if (!F || !F->MipsGotIndex.hasValue() || *F->MipsGotIndex == 0)
return ElfSym::MipsGp->getVA(0);
returngetVA() + Gots[*F->MipsGotIndex].StartIndex * Config->Wordsize +
0x7ff0;
}

voidMipsGotSection::writeTo(uint8_t *Buf) {
// Set the MSB of the second GOT slot. This is not required by any