Writer.cpp | Explore in Territory

//===- 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 "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>

#define DEBUG_TYPE …

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

namespace {
// The writer writes a SymbolTable result to a file.
template <class ELFT> class Writer { … };
} // anonymous namespace

template <class ELFT> void elf::writeResult(Ctx &ctx) { … }

static void removeEmptyPTLoad(Ctx &ctx, SmallVector<PhdrEntry *, 0> &phdrs) { … }

void elf::copySectionsIntoPartitions(Ctx &ctx) { … }

static Defined *addOptionalRegular(Ctx &ctx, StringRef name, SectionBase *sec,
                                   uint64_t val, uint8_t stOther = STV_HIDDEN) { … }

// The linker is expected to define some symbols depending on
// the linking result. This function defines such symbols.
void elf::addReservedSymbols(Ctx &ctx) { … }

static void demoteDefined(Defined &sym, DenseMap<SectionBase *, size_t> &map) { … }

// 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.
static void demoteSymbolsAndComputeIsPreemptible(Ctx &ctx) { … }

static OutputSection *findSection(Ctx &ctx, StringRef name,
                                  unsigned partition = 1) { … }

// The main function of the writer.
template <class ELFT> void Writer<ELFT>::run() { … }

template <class ELFT, class RelTy>
static void markUsedLocalSymbolsImpl(ObjFile<ELFT> *file,
                                     llvm::ArrayRef<RelTy> rels) { … }

// 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 <class ELFT> static void markUsedLocalSymbols(Ctx &ctx) { … }

static bool shouldKeepInSymtab(Ctx &ctx, const Defined &sym) { … }

bool elf::includeInSymtab(Ctx &ctx, const Symbol &b) { … }

// 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
static void demoteAndCopyLocalSymbols(Ctx &ctx) { … }

// 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 <class ELFT> void Writer<ELFT>::addSectionSymbols() { … }

// 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.
static bool isRelroSection(Ctx &ctx, const OutputSection *sec) { … }

// 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 { … };

unsigned elf::getSectionRank(Ctx &ctx, OutputSection &osec) { … }

static bool compareSections(const SectionCommand *aCmd,
                            const SectionCommand *bCmd) { … }

void PhdrEntry::add(OutputSection *sec) { … }

// 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 <class ELFT> void Writer<ELFT>::addRelIpltSymbols() { … }

// 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 <class ELFT> void Writer<ELFT>::setReservedSymbolSections() { … }

// 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.
static int getRankProximity(OutputSection *a, SectionCommand *b) { … }

// 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.
static bool shouldSkip(SectionCommand *cmd) { … }

// 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) { … }

// Adds random priorities to sections not already in the map.
static void maybeShuffle(Ctx &ctx,
                         DenseMap<const InputSectionBase *, int> &order) { … }

// Builds section order for handling --symbol-ordering-file.
static DenseMap<const InputSectionBase *, int> buildSectionOrder(Ctx &ctx) { … }

// Sorts the sections in ISD according to the provided section order.
static void
sortISDBySectionOrder(Ctx &ctx, InputSectionDescription *isd,
                      const DenseMap<const InputSectionBase *, int> &order,
                      bool executableOutputSection) { … }

static void sortSection(Ctx &ctx, OutputSection &osec,
                        const DenseMap<const InputSectionBase *, int> &order) { … }

// If no layout was provided by linker script, we want to apply default
// sorting for special input sections. This also handles --symbol-ordering-file.
template <class ELFT> void Writer<ELFT>::sortInputSections() { … }

template <class ELFT> void Writer<ELFT>::sortSections() { … }

template <class ELFT> void Writer<ELFT>::sortOrphanSections() { … }

static bool compareByFilePosition(InputSection *a, InputSection *b) { … }

template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() { … }

static void finalizeSynthetic(Ctx &ctx, SyntheticSection *sec) { … }

// We need to generate and finalize the content that depends on the address of
// InputSections. As the generation of the content may also alter InputSection
// addresses we must converge to a fixed point. We do that here. See the comment
// in Writer<ELFT>::finalizeSections().
template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() { … }

// If Input Sections have been shrunk (basic block sections) then
// update symbol values and sizes associated with these sections.  With basic
// block sections, input sections can shrink when the jump instructions at
// the end of the section are relaxed.
static void fixSymbolsAfterShrinking(Ctx &ctx) { … }

// If basic block sections exist, there are opportunities to delete fall thru
// jumps and shrink jump instructions after basic block reordering.  This
// relaxation pass does that.  It is only enabled when --optimize-bb-jumps
// option is used.
template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() { … }

// In order to allow users to manipulate linker-synthesized sections,
// we had to add synthetic sections to the input section list early,
// even before we make decisions whether they are needed. This allows
// users to write scripts like this: ".mygot : { .got }".
//
// Doing it has an unintended side effects. If it turns out that we
// don't need a .got (for example) at all because there's no
// relocation that needs a .got, we don't want to emit .got.
//
// To deal with the above problem, this function is called after
// scanRelocations is called to remove synthetic sections that turn
// out to be empty.
static void removeUnusedSyntheticSections(Ctx &ctx) { … }

// Create output section objects and add them to OutputSections.
template <class ELFT> void Writer<ELFT>::finalizeSections() { … }

// Ensure data sections are not mixed with executable sections when
// --execute-only is used. --execute-only make pages executable but not
// readable.
template <class ELFT> void Writer<ELFT>::checkExecuteOnly() { … }

// The linker is expected to define SECNAME_start and SECNAME_end
// symbols for a few sections. This function defines them.
template <class ELFT> void Writer<ELFT>::addStartEndSymbols() { … }

// If a section name is valid as a C identifier (which is rare because of
// the leading '.'), linkers are expected to define __start_<secname> and
// __stop_<secname> symbols. They are at beginning and end of the section,
// respectively. This is not requested by the ELF standard, but GNU ld and
// gold provide the feature, and used by many programs.
template <class ELFT>
void Writer<ELFT>::addStartStopSymbols(OutputSection &osec) { … }

static bool needsPtLoad(OutputSection *sec) { … }

// Adjust phdr flags according to certain options.
static uint64_t computeFlags(Ctx &ctx, uint64_t flags) { … }

// Decide which program headers to create and which sections to include in each
// one.
template <class ELFT>
SmallVector<PhdrEntry *, 0> Writer<ELFT>::createPhdrs(Partition &part) { … }

template <class ELFT>
void Writer<ELFT>::addPhdrForSection(Partition &part, unsigned shType,
                                     unsigned pType, unsigned pFlags) { … }

// Place the first section of each PT_LOAD to a different page (of maxPageSize).
// This is achieved by assigning an alignment expression to addrExpr of each
// such section.
template <class ELFT> void Writer<ELFT>::fixSectionAlignments() { … }

// Compute an in-file position for a given section. The file offset must be the
// same with its virtual address modulo the page size, so that the loader can
// load executables without any address adjustment.
static uint64_t computeFileOffset(Ctx &ctx, OutputSection *os, uint64_t off) { … }

template <class ELFT> void Writer<ELFT>::assignFileOffsetsBinary() { … }

static std::string rangeToString(uint64_t addr, uint64_t len) { … }

// Assign file offsets to output sections.
template <class ELFT> void Writer<ELFT>::assignFileOffsets() { … }

// Finalize the program headers. We call this function after we assign
// file offsets and VAs to all sections.
template <class ELFT> void Writer<ELFT>::setPhdrs(Partition &part) { … }

// A helper struct for checkSectionOverlap.
namespace {
struct SectionOffset { … };
} // namespace

// Check whether sections overlap for a specific address range (file offsets,
// load and virtual addresses).
static void checkOverlap(StringRef name, std::vector<SectionOffset> &sections,
                         bool isVirtualAddr) { … }

// Check for overlapping sections and address overflows.
//
// In this function we check that none of the output sections have overlapping
// file offsets. For SHF_ALLOC sections we also check that the load address
// ranges and the virtual address ranges don't overlap
template <class ELFT> void Writer<ELFT>::checkSections() { … }

// The entry point address is chosen in the following ways.
//
// 1. the '-e' entry command-line option;
// 2. the ENTRY(symbol) command in a linker control script;
// 3. the value of the symbol _start, if present;
// 4. the number represented by the entry symbol, if it is a number;
// 5. the address 0.
static uint64_t getEntryAddr(Ctx &ctx) { … }

static uint16_t getELFType(Ctx &ctx) { … }

template <class ELFT> void Writer<ELFT>::writeHeader() { … }

// Open a result file.
template <class ELFT> void Writer<ELFT>::openFile() { … }

template <class ELFT> void Writer<ELFT>::writeSectionsBinary() { … }

static void fillTrap(std::array<uint8_t, 4> trapInstr, uint8_t *i,
                     uint8_t *end) { … }

// Fill the last page of executable segments with trap instructions
// instead of leaving them as zero. Even though it is not required by any
// standard, it is in general a good thing to do for security reasons.
//
// We'll leave other pages in segments as-is because the rest will be
// overwritten by output sections.
template <class ELFT> void Writer<ELFT>::writeTrapInstr() { … }

// Write section contents to a mmap'ed file.
template <class ELFT> void Writer<ELFT>::writeSections() { … }

// Computes a hash value of Data using a given hash function.
// In order to utilize multiple cores, we first split data into 1MB
// chunks, compute a hash for each chunk, and then compute a hash value
// of the hash values.
static void
computeHash(llvm::MutableArrayRef<uint8_t> hashBuf,
            llvm::ArrayRef<uint8_t> data,
            std::function<void(uint8_t *dest, ArrayRef<uint8_t> arr)> hashFn) { … }

template <class ELFT> void Writer<ELFT>::writeBuildId() { … }

template void elf::writeResult<ELF32LE>(Ctx &);
template void elf::writeResult<ELF32BE>(Ctx &);
template void elf::writeResult<ELF64LE>(Ctx &);
template void elf::writeResult<ELF64BE>(Ctx &);
llvm/lld/ELF/Writer.cpp
