Writer.cpp

//===- Writer.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
//
//===----------------------------------------------------------------------===//

#include"Writer.h"
#include"AArch64ErrataFix.h"
#include"ARMErrataFix.h"
#include"BPSectionOrderer.h"
#include"CallGraphSort.h"
#include"Config.h"
#include"InputFiles.h"
#include"LinkerScript.h"
#include"MapFile.h"
#include"OutputSections.h"
#include"Relocations.h"
#include"SymbolTable.h"
#include"Symbols.h"
#include"SyntheticSections.h"
#include"Target.h"
#include"lld/Common/Arrays.h"
#include"lld/Common/CommonLinkerContext.h"
#include"lld/Common/Filesystem.h"
#include"lld/Common/Strings.h"
#include"llvm/ADT/STLExtras.h"
#include"llvm/ADT/StringMap.h"
#include"llvm/Support/BLAKE3.h"
#include"llvm/Support/Parallel.h"
#include"llvm/Support/RandomNumberGenerator.h"
#include"llvm/Support/TimeProfiler.h"
#include"llvm/Support/xxhash.h"
#include<climits>

#defineDEBUG_TYPE"lld"

usingnamespacellvm;
usingnamespacellvm::ELF;
usingnamespacellvm::object;
usingnamespacellvm::support;
usingnamespacellvm::support::endian;
usingnamespacelld;
usingnamespacelld::elf;

namespace {
// The writer writes a SymbolTable result to a file.
template <classELFT> classWriter {
public:
LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)

Writer(Ctx &ctx) : ctx(ctx), buffer(ctx.e.outputBuffer), tc(ctx) {}

voidrun();

private:
voidaddSectionSymbols();
voidsortSections();
voidresolveShfLinkOrder();
voidfinalizeAddressDependentContent();
voidoptimizeBasicBlockJumps();
voidsortInputSections();
voidsortOrphanSections();
voidfinalizeSections();
voidcheckExecuteOnly();
voidcheckExecuteOnlyReport();
voidsetReservedSymbolSections();

 SmallVector<std::unique_ptr<PhdrEntry>, 0> createPhdrs(Partition &part);
voidaddPhdrForSection(Partition &part, unsigned shType, unsigned pType,
unsigned pFlags);
voidassignFileOffsets();
voidassignFileOffsetsBinary();
voidsetPhdrs(Partition &part);
voidcheckSections();
voidfixSectionAlignments();
voidopenFile();
voidwriteTrapInstr();
voidwriteHeader();
voidwriteSections();
voidwriteSectionsBinary();
voidwriteBuildId();

 Ctx &ctx;
 std::unique_ptr<FileOutputBuffer> &buffer;
// ThunkCreator holds Thunks that are used at writeTo time.
 ThunkCreator tc;

voidaddRelIpltSymbols();
voidaddStartEndSymbols();
voidaddStartStopSymbols(OutputSection &osec);

uint64_t fileSize;
uint64_t sectionHeaderOff;
};
} // anonymous namespace

template <classELFT> voidelf::writeResult(Ctx &ctx) {
 Writer<ELFT>(ctx).run();
}

staticvoid
removeEmptyPTLoad(Ctx &ctx, SmallVector<std::unique_ptr<PhdrEntry>, 0> &phdrs) {
auto it = std::stable_partition(phdrs.begin(), phdrs.end(), [&](auto &p) {
if (p->p_type != PT_LOAD)
returntrue;
if (!p->firstSec)
returnfalse;
uint64_t size = p->lastSec->addr + p->lastSec->size - p->firstSec->addr;
return size != 0;
 });

// Clear OutputSection::ptLoad for sections contained in removed
// segments.
 DenseSet<PhdrEntry *> removed;
for (auto it2 = it; it2 != phdrs.end(); ++it2)
 removed.insert(it2->get());
for (OutputSection *sec : ctx.outputSections)
if (removed.count(sec->ptLoad))
 sec->ptLoad = nullptr;
 phdrs.erase(it, phdrs.end());
}

voidelf::copySectionsIntoPartitions(Ctx &ctx) {
 SmallVector<InputSectionBase *, 0> newSections;
constsize_t ehSize = ctx.ehInputSections.size();
for (unsigned part = 2; part != ctx.partitions.size() + 1; ++part) {
for (InputSectionBase *s : ctx.inputSections) {
if (!(s->flags & SHF_ALLOC) || !s->isLive() || s->type != SHT_NOTE)
continue;
auto *copy = make<InputSection>(cast<InputSection>(*s));
 copy->partition = part;
 newSections.push_back(copy);
 }
for (size_t i = 0; i != ehSize; ++i) {
assert(ctx.ehInputSections[i]->isLive());
auto *copy = make<EhInputSection>(*ctx.ehInputSections[i]);
 copy->partition = part;
 ctx.ehInputSections.push_back(copy);
 }
 }

 ctx.inputSections.insert(ctx.inputSections.end(), newSections.begin(),
 newSections.end());
}

static Defined *addOptionalRegular(Ctx &ctx, StringRef name, SectionBase *sec,
uint64_t val, uint8_t stOther = STV_HIDDEN) {
 Symbol *s = ctx.symtab->find(name);
if (!s || s->isDefined() || s->isCommon())
returnnullptr;

 ctx.synthesizedSymbols.push_back(s);
 s->resolve(ctx, Defined{ctx, ctx.internalFile, StringRef(), STB_GLOBAL,
 stOther, STT_NOTYPE, val,
/*size=*/0, sec});
 s->isUsedInRegularObj = true;
return cast<Defined>(s);
}

// The linker is expected to define some symbols depending on
// the linking result. This function defines such symbols.
voidelf::addReservedSymbols(Ctx &ctx) {
if (ctx.arg.emachine == EM_MIPS) {
auto addAbsolute = [&](StringRef name) {
 Symbol *sym =
 ctx.symtab->addSymbol(Defined{ctx, ctx.internalFile, name, STB_GLOBAL,
 STV_HIDDEN, STT_NOTYPE, 0, 0, nullptr});
 sym->isUsedInRegularObj = true;
return cast<Defined>(sym);
 };
// Define _gp for MIPS. st_value of _gp symbol will be updated by Writer
// so that it points to an absolute address which by default is relative
// to GOT. Default offset is 0x7ff0.
// See "Global Data Symbols" in Chapter 6 in the following document:
// ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 ctx.sym.mipsGp = addAbsolute("_gp");

// On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between
// start of function and 'gp' pointer into GOT.
if (ctx.symtab->find("_gp_disp"))
 ctx.sym.mipsGpDisp = addAbsolute("_gp_disp");

// The __gnu_local_gp is a magic symbol equal to the current value of 'gp'
// pointer. This symbol is used in the code generated by .cpload pseudo-op
// in case of using -mno-shared option.
// https://sourceware.org/ml/binutils/2004-12/msg00094.html
if (ctx.symtab->find("__gnu_local_gp"))
 ctx.sym.mipsLocalGp = addAbsolute("__gnu_local_gp");
 } elseif (ctx.arg.emachine == EM_PPC) {
// glibc *crt1.o has a undefined reference to _SDA_BASE_. Since we don't
// support Small Data Area, define it arbitrarily as 0.
addOptionalRegular(ctx, "_SDA_BASE_", nullptr, 0, STV_HIDDEN);
 } elseif (ctx.arg.emachine == EM_PPC64) {
addPPC64SaveRestore(ctx);
 }

// The Power Architecture 64-bit v2 ABI defines a TableOfContents (TOC) which
// combines the typical ELF GOT with the small data sections. It commonly
// includes .got .toc .sdata .sbss. The .TOC. symbol replaces both
// _GLOBAL_OFFSET_TABLE_ and _SDA_BASE_ from the 32-bit ABI. It is used to
// represent the TOC base which is offset by 0x8000 bytes from the start of
// the .got section.
// We do not allow _GLOBAL_OFFSET_TABLE_ to be defined by input objects as the
// correctness of some relocations depends on its value.
 StringRef gotSymName =
 (ctx.arg.emachine == EM_PPC64) ? ".TOC." : "_GLOBAL_OFFSET_TABLE_";

if (Symbol *s = ctx.symtab->find(gotSymName)) {
if (s->isDefined()) {
ErrAlways(ctx) << s->file << " cannot redefine linker defined symbol '"
 << gotSymName << "'";
return;
 }

uint64_t gotOff = 0;
if (ctx.arg.emachine == EM_PPC64)
 gotOff = 0x8000;

 s->resolve(ctx, Defined{ctx, ctx.internalFile, StringRef(), STB_GLOBAL,
 STV_HIDDEN, STT_NOTYPE, gotOff, /*size=*/0,
 ctx.out.elfHeader.get()});
 ctx.sym.globalOffsetTable = cast<Defined>(s);
 }

// __ehdr_start is the location of ELF file headers. Note that we define
// this symbol unconditionally even when using a linker script, which
// differs from the behavior implemented by GNU linker which only define
// this symbol if ELF headers are in the memory mapped segment.
addOptionalRegular(ctx, "__ehdr_start", ctx.out.elfHeader.get(), 0,
 STV_HIDDEN);

// __executable_start is not documented, but the expectation of at
// least the Android libc is that it points to the ELF header.
addOptionalRegular(ctx, "__executable_start", ctx.out.elfHeader.get(), 0,
 STV_HIDDEN);

// __dso_handle symbol is passed to cxa_finalize as a marker to identify
// each DSO. The address of the symbol doesn't matter as long as they are
// different in different DSOs, so we chose the start address of the DSO.
addOptionalRegular(ctx, "__dso_handle", ctx.out.elfHeader.get(), 0,
 STV_HIDDEN);

// If linker script do layout we do not need to create any standard symbols.
if (ctx.script->hasSectionsCommand)
return;

auto add = [&](StringRef s, int64_t pos) {
returnaddOptionalRegular(ctx, s, ctx.out.elfHeader.get(), pos,
 STV_DEFAULT);
 };

 ctx.sym.bss = add("__bss_start", 0);
 ctx.sym.end1 = add("end", -1);
 ctx.sym.end2 = add("_end", -1);
 ctx.sym.etext1 = add("etext", -1);
 ctx.sym.etext2 = add("_etext", -1);
 ctx.sym.edata1 = add("edata", -1);
 ctx.sym.edata2 = add("_edata", -1);
}

staticvoiddemoteDefined(Defined &sym, DenseMap<SectionBase *, size_t> &map) {
if (map.empty())
for (auto [i, sec] : llvm::enumerate(sym.file->getSections()))
 map.try_emplace(sec, i);
// Change WEAK to GLOBAL so that if a scanned relocation references sym,
// maybeReportUndefined will report an error.
uint8_t binding = sym.isWeak() ? uint8_t(STB_GLOBAL) : sym.binding;
Undefined(sym.file, sym.getName(), binding, sym.stOther, sym.type,
/*discardedSecIdx=*/map.lookup(sym.section))
 .overwrite(sym);
// Eliminate from the symbol table, otherwise we would leave an undefined
// symbol if the symbol is unreferenced in the absence of GC.
 sym.isUsedInRegularObj = false;
}

// If all references to a DSO happen to be weak, the DSO is not added to
// DT_NEEDED. If that happens, replace ShardSymbol with Undefined to avoid
// dangling references to an unneeded DSO. Use a weak binding to avoid
// --no-allow-shlib-undefined diagnostics. Similarly, demote lazy symbols.
//
// In addition, demote symbols defined in discarded sections, so that
// references to /DISCARD/ discarded symbols will lead to errors.
staticvoiddemoteSymbolsAndComputeIsPreemptible(Ctx &ctx) {
 llvm::TimeTraceScope timeScope("Demote symbols");
 DenseMap<InputFile *, DenseMap<SectionBase *, size_t>> sectionIndexMap;
bool maybePreemptible = ctx.sharedFiles.size() || ctx.arg.shared;
for (Symbol *sym : ctx.symtab->getSymbols()) {
if (auto *d = dyn_cast<Defined>(sym)) {
if (d->section && !d->section->isLive())
demoteDefined(*d, sectionIndexMap[d->file]);
 } else {
auto *s = dyn_cast<SharedSymbol>(sym);
if (sym->isLazy() || (s && !cast<SharedFile>(s->file)->isNeeded)) {
uint8_t binding = sym->isLazy() ? sym->binding : uint8_t(STB_WEAK);
Undefined(ctx.internalFile, sym->getName(), binding, sym->stOther,
 sym->type)
 .overwrite(*sym);
 sym->versionId = VER_NDX_GLOBAL;
 }
 }

if (maybePreemptible)
 sym->isPreemptible = (sym->isUndefined() || sym->isExported) &&
computeIsPreemptible(ctx, *sym);
 }
}

static OutputSection *findSection(Ctx &ctx, StringRef name,
unsigned partition = 1) {
for (SectionCommand *cmd : ctx.script->sectionCommands)
if (auto *osd = dyn_cast<OutputDesc>(cmd))
if (osd->osec.name == name && osd->osec.partition == partition)
return &osd->osec;
returnnullptr;
}

// The main function of the writer.
template <classELFT> void Writer<ELFT>::run() {
// Now that we have a complete set of output sections. This function
// completes section contents. For example, we need to add strings
// to the string table, and add entries to .got and .plt.
// finalizeSections does that.
finalizeSections();
checkExecuteOnly();
checkExecuteOnlyReport();

// If --compressed-debug-sections is specified, compress .debug_* sections.
// Do it right now because it changes the size of output sections.
for (OutputSection *sec : ctx.outputSections)
 sec->maybeCompress<ELFT>(ctx);

if (ctx.script->hasSectionsCommand)
 ctx.script->allocateHeaders(ctx.mainPart->phdrs);

// Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
// 0 sized region. This has to be done late since only after assignAddresses
// we know the size of the sections.
for (Partition &part : ctx.partitions)
removeEmptyPTLoad(ctx, part.phdrs);

if (!ctx.arg.oFormatBinary)
assignFileOffsets();
else
assignFileOffsetsBinary();

for (Partition &part : ctx.partitions)
setPhdrs(part);

// Handle --print-map(-M)/--Map and --cref. Dump them before checkSections()
// because the files may be useful in case checkSections() or openFile()
// fails, for example, due to an erroneous file size.
writeMapAndCref(ctx);

// Handle --print-memory-usage option.
if (ctx.arg.printMemoryUsage)
 ctx.script->printMemoryUsage(ctx.e.outs());

if (ctx.arg.checkSections)
checkSections();

// It does not make sense try to open the file if we have error already.
if (errCount(ctx))
return;

 {
 llvm::TimeTraceScope timeScope("Write output file");
// Write the result down to a file.
openFile();
if (errCount(ctx))
return;

if (!ctx.arg.oFormatBinary) {
if (ctx.arg.zSeparate != SeparateSegmentKind::None)
writeTrapInstr();
writeHeader();
writeSections();
 } else {
writeSectionsBinary();
 }

// Backfill .note.gnu.build-id section content. This is done at last
// because the content is usually a hash value of the entire output file.
writeBuildId();
if (errCount(ctx))
return;

if (!ctx.e.disableOutput) {
if (auto e = buffer->commit())
Err(ctx) << "failed to write output '" << buffer->getPath()
 << "': " << std::move(e);
 }

if (!ctx.arg.cmseOutputLib.empty())
 writeARMCmseImportLib<ELFT>(ctx);
 }
}

template <classELFT, classRelTy>
staticvoidmarkUsedLocalSymbolsImpl(ObjFile<ELFT> *file,
 llvm::ArrayRef<RelTy> rels) {
for (const RelTy &rel : rels) {
 Symbol &sym = file->getRelocTargetSym(rel);
if (sym.isLocal())
 sym.used = true;
 }
}

// The function ensures that the "used" field of local symbols reflects the fact
// that the symbol is used in a relocation from a live section.
template <classELFT> staticvoidmarkUsedLocalSymbols(Ctx &ctx) {
// With --gc-sections, the field is already filled.
// See MarkLive<ELFT>::resolveReloc().
if (ctx.arg.gcSections)
return;
for (ELFFileBase *file : ctx.objectFiles) {
 ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
for (InputSectionBase *s : f->getSections()) {
 InputSection *isec = dyn_cast_or_null<InputSection>(s);
if (!isec)
continue;
if (isec->type == SHT_REL) {
markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rel>());
 } elseif (isec->type == SHT_RELA) {
markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rela>());
 } elseif (isec->type == SHT_CREL) {
// The is64=true variant also works with ELF32 since only the r_symidx
// member is used.
for (Elf_Crel_Impl<true> r : RelocsCrel<true>(isec->content_)) {
 Symbol &sym = file->getSymbol(r.r_symidx);
if (sym.isLocal())
 sym.used = true;
 }
 }
 }
 }
}

staticboolshouldKeepInSymtab(Ctx &ctx, const Defined &sym) {
if (sym.isSection())
returnfalse;

// If --emit-reloc or -r is given, preserve symbols referenced by relocations
// from live sections.
if (sym.used && ctx.arg.copyRelocs)
returntrue;

// Exclude local symbols pointing to .ARM.exidx sections.
// They are probably mapping symbols "$d", which are optional for these
// sections. After merging the .ARM.exidx sections, some of these symbols
// may become dangling. The easiest way to avoid the issue is not to add
// them to the symbol table from the beginning.
if (ctx.arg.emachine == EM_ARM && sym.section &&
 sym.section->type == SHT_ARM_EXIDX)
returnfalse;

if (ctx.arg.discard == DiscardPolicy::None)
returntrue;
if (ctx.arg.discard == DiscardPolicy::All)
returnfalse;

// In ELF assembly .L symbols are normally discarded by the assembler.
// If the assembler fails to do so, the linker discards them if
// * --discard-locals is used.
// * The symbol is in a SHF_MERGE section, which is normally the reason for
// the assembler keeping the .L symbol.
if (sym.getName().starts_with(".L") &&
 (ctx.arg.discard == DiscardPolicy::Locals ||
 (sym.section && (sym.section->flags & SHF_MERGE))))
returnfalse;
returntrue;
}

boolelf::includeInSymtab(Ctx &ctx, const Symbol &b) {
if (auto *d = dyn_cast<Defined>(&b)) {
// Always include absolute symbols.
 SectionBase *sec = d->section;
if (!sec)
returntrue;
assert(sec->isLive());

if (auto *s = dyn_cast<MergeInputSection>(sec))
return s->getSectionPiece(d->value).live;
returntrue;
 }
return b.used || !ctx.arg.gcSections;
}

// Scan local symbols to:
//
// - demote symbols defined relative to /DISCARD/ discarded input sections so
// that relocations referencing them will lead to errors.
// - copy eligible symbols to .symTab
staticvoiddemoteAndCopyLocalSymbols(Ctx &ctx) {
 llvm::TimeTraceScope timeScope("Add local symbols");
for (ELFFileBase *file : ctx.objectFiles) {
 DenseMap<SectionBase *, size_t> sectionIndexMap;
for (Symbol *b : file->getLocalSymbols()) {
assert(b->isLocal() && "should have been caught in initializeSymbols()");
auto *dr = dyn_cast<Defined>(b);
if (!dr)
continue;

if (dr->section && !dr->section->isLive())
demoteDefined(*dr, sectionIndexMap);
elseif (ctx.in.symTab && includeInSymtab(ctx, *b) &&
shouldKeepInSymtab(ctx, *dr))
 ctx.in.symTab->addSymbol(b);
 }
 }
}

// Create a section symbol for each output section so that we can represent
// relocations that point to the section. If we know that no relocation is
// referring to a section (that happens if the section is a synthetic one), we
// don't create a section symbol for that section.
template <classELFT> void Writer<ELFT>::addSectionSymbols() {
for (SectionCommand *cmd : ctx.script->sectionCommands) {
auto *osd = dyn_cast<OutputDesc>(cmd);
if (!osd)
continue;
 OutputSection &osec = osd->osec;
 InputSectionBase *isec = nullptr;
// Iterate over all input sections and add a STT_SECTION symbol if any input
// section may be a relocation target.
for (SectionCommand *cmd : osec.commands) {
auto *isd = dyn_cast<InputSectionDescription>(cmd);
if (!isd)
continue;
for (InputSectionBase *s : isd->sections) {
// Relocations are not using REL[A] section symbols.
if (isStaticRelSecType(s->type))
continue;

// Unlike other synthetic sections, mergeable output sections contain
// data copied from input sections, and there may be a relocation
// pointing to its contents if -r or --emit-reloc is given.
if (isa<SyntheticSection>(s) && !(s->flags & SHF_MERGE))
continue;

 isec = s;
break;
 }
 }
if (!isec)
continue;

// Set the symbol to be relative to the output section so that its st_value
// equals the output section address. Note, there may be a gap between the
// start of the output section and isec.
 ctx.in.symTab->addSymbol(makeDefined(ctx, isec->file, "", STB_LOCAL,
/*stOther=*/0, STT_SECTION,
/*value=*/0, /*size=*/0, &osec));
 }
}

// Today's loaders have a feature to make segments read-only after
// processing dynamic relocations to enhance security. PT_GNU_RELRO
// is defined for that.
//
// This function returns true if a section needs to be put into a
// PT_GNU_RELRO segment.
staticboolisRelroSection(Ctx &ctx, const OutputSection *sec) {
if (!ctx.arg.zRelro)
returnfalse;
if (sec->relro)
returntrue;

uint64_t flags = sec->flags;

// Non-allocatable or non-writable sections don't need RELRO because
// they are not writable or not even mapped to memory in the first place.
// RELRO is for sections that are essentially read-only but need to
// be writable only at process startup to allow dynamic linker to
// apply relocations.
if (!(flags & SHF_ALLOC) || !(flags & SHF_WRITE))
returnfalse;

// Once initialized, TLS data segments are used as data templates
// for a thread-local storage. For each new thread, runtime
// allocates memory for a TLS and copy templates there. No thread
// are supposed to use templates directly. Thus, it can be in RELRO.
if (flags & SHF_TLS)
returntrue;

// .init_array, .preinit_array and .fini_array contain pointers to
// functions that are executed on process startup or exit. These
// pointers are set by the static linker, and they are not expected
// to change at runtime. But if you are an attacker, you could do
// interesting things by manipulating pointers in .fini_array, for
// example. So they are put into RELRO.
uint32_t type = sec->type;
if (type == SHT_INIT_ARRAY || type == SHT_FINI_ARRAY ||
 type == SHT_PREINIT_ARRAY)
returntrue;

// .got contains pointers to external symbols. They are resolved by
// the dynamic linker when a module is loaded into memory, and after
// that they are not expected to change. So, it can be in RELRO.
if (ctx.in.got && sec == ctx.in.got->getParent())
returntrue;

// .toc is a GOT-ish section for PowerPC64. Their contents are accessed
// through r2 register, which is reserved for that purpose. Since r2 is used
// for accessing .got as well, .got and .toc need to be close enough in the
// virtual address space. Usually, .toc comes just after .got. Since we place
// .got into RELRO, .toc needs to be placed into RELRO too.
if (sec->name == ".toc")
returntrue;

// .got.plt contains pointers to external function symbols. They are
// by default resolved lazily, so we usually cannot put it into RELRO.
// However, if "-z now" is given, the lazy symbol resolution is
// disabled, which enables us to put it into RELRO.
if (sec == ctx.in.gotPlt->getParent())
return ctx.arg.zNow;

if (ctx.in.relroPadding && sec == ctx.in.relroPadding->getParent())
returntrue;

// .dynamic section contains data for the dynamic linker, and
// there's no need to write to it at runtime, so it's better to put
// it into RELRO.
if (sec->name == ".dynamic")
returntrue;

// Sections with some special names are put into RELRO. This is a
// bit unfortunate because section names shouldn't be significant in
// ELF in spirit. But in reality many linker features depend on
// magic section names.
 StringRef s = sec->name;

bool abiAgnostic = s == ".data.rel.ro" || s == ".bss.rel.ro" ||
 s == ".ctors" || s == ".dtors" || s == ".jcr" ||
 s == ".eh_frame" || s == ".fini_array" ||
 s == ".init_array" || s == ".preinit_array";

bool abiSpecific =
 ctx.arg.osabi == ELFOSABI_OPENBSD && s == ".openbsd.randomdata";

return abiAgnostic || abiSpecific;
}

// We compute a rank for each section. The rank indicates where the
// section should be placed in the file. Instead of using simple
// numbers (0,1,2...), we use a series of flags. One for each decision
// point when placing the section.
// Using flags has two key properties:
// * It is easy to check if a give branch was taken.
// * It is easy two see how similar two ranks are (see getRankProximity).
enum RankFlags {
 RF_NOT_ADDR_SET = 1 << 27,
 RF_NOT_ALLOC = 1 << 26,
 RF_PARTITION = 1 << 18, // Partition number (8 bits)
 RF_LARGE_ALT = 1 << 15,
 RF_WRITE = 1 << 14,
 RF_EXEC_WRITE = 1 << 13,
 RF_EXEC = 1 << 12,
 RF_RODATA = 1 << 11,
 RF_LARGE = 1 << 10,
 RF_NOT_RELRO = 1 << 9,
 RF_NOT_TLS = 1 << 8,
 RF_BSS = 1 << 7,
};

unsignedelf::getSectionRank(Ctx &ctx, OutputSection &osec) {
unsigned rank = osec.partition * RF_PARTITION;

// We want to put section specified by -T option first, so we
// can start assigning VA starting from them later.
if (ctx.arg.sectionStartMap.count(osec.name))
return rank;
 rank |= RF_NOT_ADDR_SET;

// Allocatable sections go first to reduce the total PT_LOAD size and
// so debug info doesn't change addresses in actual code.
if (!(osec.flags & SHF_ALLOC))
return rank | RF_NOT_ALLOC;

// Sort sections based on their access permission in the following
// order: R, RX, RXW, RW(RELRO), RW(non-RELRO).
//
// Read-only sections come first such that they go in the PT_LOAD covering the
// program headers at the start of the file.
//
// The layout for writable sections is PT_LOAD(PT_GNU_RELRO(.data.rel.ro
// .bss.rel.ro) | .data .bss), where | marks where page alignment happens.
// An alternative ordering is PT_LOAD(.data | PT_GNU_RELRO( .data.rel.ro
// .bss.rel.ro) | .bss), but it may waste more bytes due to 2 alignment
// places.
bool isExec = osec.flags & SHF_EXECINSTR;
bool isWrite = osec.flags & SHF_WRITE;

if (!isWrite && !isExec) {
// Among PROGBITS sections, place .lrodata further from .text.
// For -z lrodata-after-bss, place .lrodata after .lbss like GNU ld. This
// layout has one extra PT_LOAD, but alleviates relocation overflow
// pressure for absolute relocations referencing small data from -fno-pic
// relocatable files.
if (osec.flags & SHF_X86_64_LARGE && ctx.arg.emachine == EM_X86_64)
 rank |= ctx.arg.zLrodataAfterBss ? RF_LARGE_ALT : 0;
else
 rank |= ctx.arg.zLrodataAfterBss ? 0 : RF_LARGE;

if (osec.type == SHT_LLVM_PART_EHDR)
 ;
elseif (osec.type == SHT_LLVM_PART_PHDR)
 rank |= 1;
elseif (osec.name == ".interp")
 rank |= 2;
// Put .note sections at the beginning so that they are likely to be
// included in a truncate core file. In particular, .note.gnu.build-id, if
// available, can identify the object file.
elseif (osec.type == SHT_NOTE)
 rank |= 3;
// Make PROGBITS sections (e.g .rodata .eh_frame) closer to .text to
// alleviate relocation overflow pressure. Large special sections such as
// .dynstr and .dynsym can be away from .text.
elseif (osec.type != SHT_PROGBITS)
 rank |= 4;
else
 rank |= RF_RODATA;
 } elseif (isExec) {
 rank |= isWrite ? RF_EXEC_WRITE : RF_EXEC;
 } else {
 rank |= RF_WRITE;
// The TLS initialization block needs to be a single contiguous block. Place
// TLS sections directly before the other RELRO sections.
if (!(osec.flags & SHF_TLS))
 rank |= RF_NOT_TLS;
if (isRelroSection(ctx, &osec))
 osec.relro = true;
else
 rank |= RF_NOT_RELRO;
// Place .ldata and .lbss after .bss. Making .bss closer to .text
// alleviates relocation overflow pressure.
// For -z lrodata-after-bss, place .lbss/.lrodata/.ldata after .bss.
// .bss/.lbss being adjacent reuses the NOBITS size optimization.
if (osec.flags & SHF_X86_64_LARGE && ctx.arg.emachine == EM_X86_64) {
 rank |= ctx.arg.zLrodataAfterBss
 ? (osec.type == SHT_NOBITS ? 1 : RF_LARGE_ALT)
 : RF_LARGE;
 }
 }

// Within TLS sections, or within other RelRo sections, or within non-RelRo
// sections, place non-NOBITS sections first.
if (osec.type == SHT_NOBITS)
 rank |= RF_BSS;

// Some architectures have additional ordering restrictions for sections
// within the same PT_LOAD.
if (ctx.arg.emachine == EM_PPC64) {
// PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections
// that we would like to make sure appear is a specific order to maximize
// their coverage by a single signed 16-bit offset from the TOC base
// pointer.
 StringRef name = osec.name;
if (name == ".got")
 rank |= 1;
elseif (name == ".toc")
 rank |= 2;
 }

if (ctx.arg.emachine == EM_MIPS) {
if (osec.name != ".got")
 rank |= 1;
// All sections with SHF_MIPS_GPREL flag should be grouped together
// because data in these sections is addressable with a gp relative address.
if (osec.flags & SHF_MIPS_GPREL)
 rank |= 2;
 }

if (ctx.arg.emachine == EM_RISCV) {
// .sdata and .sbss are placed closer to make GP relaxation more profitable
// and match GNU ld.
 StringRef name = osec.name;
if (name == ".sdata" || (osec.type == SHT_NOBITS && name != ".sbss"))
 rank |= 1;
 }

return rank;
}

staticboolcompareSections(Ctx &ctx, const SectionCommand *aCmd,
const SectionCommand *bCmd) {
const OutputSection *a = &cast<OutputDesc>(aCmd)->osec;
const OutputSection *b = &cast<OutputDesc>(bCmd)->osec;

if (a->sortRank != b->sortRank)
return a->sortRank < b->sortRank;

if (!(a->sortRank & RF_NOT_ADDR_SET))
return ctx.arg.sectionStartMap.lookup(a->name) <
 ctx.arg.sectionStartMap.lookup(b->name);
returnfalse;
}

voidPhdrEntry::add(OutputSection *sec) {
 lastSec = sec;
if (!firstSec)
 firstSec = sec;
 p_align = std::max(p_align, sec->addralign);
if (p_type == PT_LOAD)
 sec->ptLoad = this;
}

// A statically linked position-dependent executable should only contain
// IRELATIVE relocations and no other dynamic relocations. Encapsulation symbols
// __rel[a]_iplt_{start,end} will be defined for .rel[a].dyn, to be
// processed by the libc runtime. Other executables or DSOs use dynamic tags
// instead.
template <classELFT> void Writer<ELFT>::addRelIpltSymbols() {
if (ctx.arg.isPic)
return;

// __rela_iplt_{start,end} are initially defined relative to dummy section 0.
// We'll override ctx.out.elfHeader with relaDyn later when we are sure that
// .rela.dyn will be present in the output.
 std::string name = ctx.arg.isRela ? "__rela_iplt_start" : "__rel_iplt_start";
 ctx.sym.relaIpltStart =
addOptionalRegular(ctx, name, ctx.out.elfHeader.get(), 0, STV_HIDDEN);
 name.replace(name.size() - 5, 5, "end");
 ctx.sym.relaIpltEnd =
addOptionalRegular(ctx, name, ctx.out.elfHeader.get(), 0, STV_HIDDEN);
}

// This function generates assignments for predefined symbols (e.g. _end or
// _etext) and inserts them into the commands sequence to be processed at the
// appropriate time. This ensures that the value is going to be correct by the
// time any references to these symbols are processed and is equivalent to
// defining these symbols explicitly in the linker script.
template <classELFT> void Writer<ELFT>::setReservedSymbolSections() {
if (ctx.sym.globalOffsetTable) {
// The _GLOBAL_OFFSET_TABLE_ symbol is defined by target convention usually
// to the start of the .got or .got.plt section.
 InputSection *sec = ctx.in.gotPlt.get();
if (!ctx.target->gotBaseSymInGotPlt)
 sec = ctx.in.mipsGot ? cast<InputSection>(ctx.in.mipsGot.get())
 : cast<InputSection>(ctx.in.got.get());
 ctx.sym.globalOffsetTable->section = sec;
 }

// .rela_iplt_{start,end} mark the start and the end of the section containing
// IRELATIVE relocations.
if (ctx.sym.relaIpltStart) {
auto &dyn = getIRelativeSection(ctx);
if (dyn.isNeeded()) {
 ctx.sym.relaIpltStart->section = &dyn;
 ctx.sym.relaIpltEnd->section = &dyn;
 ctx.sym.relaIpltEnd->value = dyn.getSize();
 }
 }

 PhdrEntry *last = nullptr;
 OutputSection *lastRO = nullptr;
auto isLarge = [&ctx = ctx](OutputSection *osec) {
return ctx.arg.emachine == EM_X86_64 && osec->flags & SHF_X86_64_LARGE;
 };
for (Partition &part : ctx.partitions) {
for (auto &p : part.phdrs) {
if (p->p_type != PT_LOAD)
continue;
 last = p.get();
if (!(p->p_flags & PF_W) && p->lastSec && !isLarge(p->lastSec))
 lastRO = p->lastSec;
 }
 }

if (lastRO) {
// _etext is the first location after the last read-only loadable segment
// that does not contain large sections.
if (ctx.sym.etext1)
 ctx.sym.etext1->section = lastRO;
if (ctx.sym.etext2)
 ctx.sym.etext2->section = lastRO;
 }

if (last) {
// _edata points to the end of the last non-large mapped initialized
// section.
 OutputSection *edata = nullptr;
for (OutputSection *os : ctx.outputSections) {
if (os->type != SHT_NOBITS && !isLarge(os))
 edata = os;
if (os == last->lastSec)
break;
 }

if (ctx.sym.edata1)
 ctx.sym.edata1->section = edata;
if (ctx.sym.edata2)
 ctx.sym.edata2->section = edata;

// _end is the first location after the uninitialized data region.
if (ctx.sym.end1)
 ctx.sym.end1->section = last->lastSec;
if (ctx.sym.end2)
 ctx.sym.end2->section = last->lastSec;
 }

if (ctx.sym.bss) {
// On RISC-V, set __bss_start to the start of .sbss if present.
 OutputSection *sbss =
 ctx.arg.emachine == EM_RISCV ? findSection(ctx, ".sbss") : nullptr;
 ctx.sym.bss->section = sbss ? sbss : findSection(ctx, ".bss");
 }

// Setup MIPS _gp_disp/__gnu_local_gp symbols which should
// be equal to the _gp symbol's value.
if (ctx.sym.mipsGp) {
// Find GP-relative section with the lowest address
// and use this address to calculate default _gp value.
for (OutputSection *os : ctx.outputSections) {
if (os->flags & SHF_MIPS_GPREL) {
 ctx.sym.mipsGp->section = os;
 ctx.sym.mipsGp->value = 0x7ff0;
break;
 }
 }
 }
}

// We want to find how similar two ranks are.
// The more branches in getSectionRank that match, the more similar they are.
// Since each branch corresponds to a bit flag, we can just use
// countLeadingZeros.
staticintgetRankProximity(OutputSection *a, SectionCommand *b) {
auto *osd = dyn_cast<OutputDesc>(b);
return (osd && osd->osec.hasInputSections)
 ? llvm::countl_zero(a->sortRank ^ osd->osec.sortRank)
 : -1;
}

// When placing orphan sections, we want to place them after symbol assignments
// so that an orphan after
// begin_foo = .;
// foo : { *(foo) }
// end_foo = .;
// doesn't break the intended meaning of the begin/end symbols.
// We don't want to go over sections since findOrphanPos is the
// one in charge of deciding the order of the sections.
// We don't want to go over changes to '.', since doing so in
// rx_sec : { *(rx_sec) }
// . = ALIGN(0x1000);
// /* The RW PT_LOAD starts here*/
// rw_sec : { *(rw_sec) }
// would mean that the RW PT_LOAD would become unaligned.
staticboolshouldSkip(SectionCommand *cmd) {
if (auto *assign = dyn_cast<SymbolAssignment>(cmd))
return assign->name != ".";
returnfalse;
}

// We want to place orphan sections so that they share as much
// characteristics with their neighbors as possible. For example, if
// both are rw, or both are tls.
static SmallVectorImpl<SectionCommand *>::iterator
findOrphanPos(Ctx &ctx, SmallVectorImpl<SectionCommand *>::iterator b,
 SmallVectorImpl<SectionCommand *>::iterator e) {
// Place non-alloc orphan sections at the end. This matches how we assign file
// offsets to non-alloc sections.
 OutputSection *sec = &cast<OutputDesc>(*e)->osec;
if (!(sec->flags & SHF_ALLOC))
return e;

// As a special case, place .relro_padding before the SymbolAssignment using
// DATA_SEGMENT_RELRO_END, if present.
if (ctx.in.relroPadding && sec == ctx.in.relroPadding->getParent()) {
auto i = std::find_if(b, e, [=](SectionCommand *a) {
if (auto *assign = dyn_cast<SymbolAssignment>(a))
return assign->dataSegmentRelroEnd;
returnfalse;
 });
if (i != e)
return i;
 }

// Find the most similar output section as the anchor. Rank Proximity is a
// value in the range [-1, 32] where [0, 32] indicates potential anchors (0:
// least similar; 32: identical). -1 means not an anchor.
//
// In the event of proximity ties, we select the first or last section
// depending on whether the orphan's rank is smaller.
int maxP = 0;
auto i = e;
for (auto j = b; j != e; ++j) {
int p = getRankProximity(sec, *j);
if (p > maxP ||
 (p == maxP && cast<OutputDesc>(*j)->osec.sortRank <= sec->sortRank)) {
 maxP = p;
 i = j;
 }
 }
if (i == e)
return e;

auto isOutputSecWithInputSections = [](SectionCommand *cmd) {
auto *osd = dyn_cast<OutputDesc>(cmd);