llvm/lld/ELF/Relocations.cpp

//===- Relocations.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 platform-independent functions to process relocations.
// I'll describe the overview of this file here.
//
// Simple relocations are easy to handle for the linker. For example,
// for R_X86_64_PC64 relocs, the linker just has to fix up locations
// with the relative offsets to the target symbols. It would just be
// reading records from relocation sections and applying them to output.
//
// But not all relocations are that easy to handle. For example, for
// R_386_GOTOFF relocs, the linker has to create new GOT entries for
// symbols if they don't exist, and fix up locations with GOT entry
// offsets from the beginning of GOT section. So there is more than
// fixing addresses in relocation processing.
//
// ELF defines a large number of complex relocations.
//
// The functions in this file analyze relocations and do whatever needs
// to be done. It includes, but not limited to, the following.
//
//  - create GOT/PLT entries
//  - create new relocations in .dynsym to let the dynamic linker resolve
//    them at runtime (since ELF supports dynamic linking, not all
//    relocations can be resolved at link-time)
//  - create COPY relocs and reserve space in .bss
//  - replace expensive relocs (in terms of runtime cost) with cheap ones
//  - error out infeasible combinations such as PIC and non-relative relocs
//
// Note that the functions in this file don't actually apply relocations
// because it doesn't know about the output file nor the output file buffer.
// It instead stores Relocation objects to InputSection's Relocations
// vector to let it apply later in InputSection::writeTo.
//
//===----------------------------------------------------------------------===//

#include "Relocations.h"
#include "Config.h"
#include "InputFiles.h"
#include "LinkerScript.h"
#include "OutputSections.h"
#include "SymbolTable.h"
#include "Symbols.h"
#include "SyntheticSections.h"
#include "Target.h"
#include "Thunks.h"
#include "lld/Common/ErrorHandler.h"
#include "lld/Common/Memory.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/BinaryFormat/ELF.h"
#include "llvm/Demangle/Demangle.h"
#include "llvm/Support/Endian.h"
#include <algorithm>

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

static std::optional<std::string> getLinkerScriptLocation(Ctx &ctx,
                                                          const Symbol &sym) { … }

static std::string getDefinedLocation(Ctx &ctx, const Symbol &sym) { … }

// Construct a message in the following format.
//
// >>> defined in /home/alice/src/foo.o
// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
// >>>               /home/alice/src/bar.o:(.text+0x1)
static std::string getLocation(Ctx &ctx, InputSectionBase &s, const Symbol &sym,
                               uint64_t off) { … }

void elf::reportRangeError(Ctx &, uint8_t *loc, const Relocation &rel,
                           const Twine &v, int64_t min, uint64_t max) { … }

void elf::reportRangeError(Ctx &ctx, uint8_t *loc, int64_t v, int n,
                           const Symbol &sym, const Twine &msg) { … }

// Build a bitmask with one bit set for each 64 subset of RelExpr.
static constexpr uint64_t buildMask() { … }

template <typename... Tails>
static constexpr uint64_t buildMask(int head, Tails... tails) { … }

// Return true if `Expr` is one of `Exprs`.
// There are more than 64 but less than 128 RelExprs, so we divide the set of
// exprs into [0, 64) and [64, 128) and represent each range as a constant
// 64-bit mask. Then we decide which mask to test depending on the value of
// expr and use a simple shift and bitwise-and to test for membership.
template <RelExpr... Exprs> static bool oneof(RelExpr expr) { … }

static RelType getMipsPairType(RelType type, bool isLocal) { … }

// True if non-preemptable symbol always has the same value regardless of where
// the DSO is loaded.
static bool isAbsolute(const Symbol &sym) { … }

static bool isAbsoluteValue(const Symbol &sym) { … }

// Returns true if Expr refers a PLT entry.
static bool needsPlt(RelExpr expr) { … }

bool lld::elf::needsGot(RelExpr expr) { … }

// True if this expression is of the form Sym - X, where X is a position in the
// file (PC, or GOT for example).
static bool isRelExpr(RelExpr expr) { … }

static RelExpr toPlt(RelExpr expr) { … }

static RelExpr fromPlt(RelExpr expr) { … }

// Returns true if a given shared symbol is in a read-only segment in a DSO.
template <class ELFT> static bool isReadOnly(SharedSymbol &ss) { … }

// Returns symbols at the same offset as a given symbol, including SS itself.
//
// If two or more symbols are at the same offset, and at least one of
// them are copied by a copy relocation, all of them need to be copied.
// Otherwise, they would refer to different places at runtime.
template <class ELFT>
static SmallSet<SharedSymbol *, 4> getSymbolsAt(Ctx &ctx, SharedSymbol &ss) { … }

// When a symbol is copy relocated or we create a canonical plt entry, it is
// effectively a defined symbol. In the case of copy relocation the symbol is
// in .bss and in the case of a canonical plt entry it is in .plt. This function
// replaces the existing symbol with a Defined pointing to the appropriate
// location.
static void replaceWithDefined(Symbol &sym, SectionBase &sec, uint64_t value,
                               uint64_t size) { … }

// Reserve space in .bss or .bss.rel.ro for copy relocation.
//
// The copy relocation is pretty much a hack. If you use a copy relocation
// in your program, not only the symbol name but the symbol's size, RW/RO
// bit and alignment become part of the ABI. In addition to that, if the
// symbol has aliases, the aliases become part of the ABI. That's subtle,
// but if you violate that implicit ABI, that can cause very counter-
// intuitive consequences.
//
// So, what is the copy relocation? It's for linking non-position
// independent code to DSOs. In an ideal world, all references to data
// exported by DSOs should go indirectly through GOT. But if object files
// are compiled as non-PIC, all data references are direct. There is no
// way for the linker to transform the code to use GOT, as machine
// instructions are already set in stone in object files. This is where
// the copy relocation takes a role.
//
// A copy relocation instructs the dynamic linker to copy data from a DSO
// to a specified address (which is usually in .bss) at load-time. If the
// static linker (that's us) finds a direct data reference to a DSO
// symbol, it creates a copy relocation, so that the symbol can be
// resolved as if it were in .bss rather than in a DSO.
//
// As you can see in this function, we create a copy relocation for the
// dynamic linker, and the relocation contains not only symbol name but
// various other information about the symbol. So, such attributes become a
// part of the ABI.
//
// Note for application developers: I can give you a piece of advice if
// you are writing a shared library. You probably should export only
// functions from your library. You shouldn't export variables.
//
// As an example what can happen when you export variables without knowing
// the semantics of copy relocations, assume that you have an exported
// variable of type T. It is an ABI-breaking change to add new members at
// end of T even though doing that doesn't change the layout of the
// existing members. That's because the space for the new members are not
// reserved in .bss unless you recompile the main program. That means they
// are likely to overlap with other data that happens to be laid out next
// to the variable in .bss. This kind of issue is sometimes very hard to
// debug. What's a solution? Instead of exporting a variable V from a DSO,
// define an accessor getV().
template <class ELFT> static void addCopyRelSymbol(Ctx &ctx, SharedSymbol &ss) { … }

// .eh_frame sections are mergeable input sections, so their input
// offsets are not linearly mapped to output section. For each input
// offset, we need to find a section piece containing the offset and
// add the piece's base address to the input offset to compute the
// output offset. That isn't cheap.
//
// This class is to speed up the offset computation. When we process
// relocations, we access offsets in the monotonically increasing
// order. So we can optimize for that access pattern.
//
// For sections other than .eh_frame, this class doesn't do anything.
namespace {
class OffsetGetter { … };

// This class encapsulates states needed to scan relocations for one
// InputSectionBase.
class RelocationScanner { … };
} // namespace

// MIPS has an odd notion of "paired" relocations to calculate addends.
// For example, if a relocation is of R_MIPS_HI16, there must be a
// R_MIPS_LO16 relocation after that, and an addend is calculated using
// the two relocations.
template <class ELFT, class RelTy>
int64_t RelocationScanner::computeMipsAddend(const RelTy &rel, RelExpr expr,
                                             bool isLocal) const { … }

// Custom error message if Sym is defined in a discarded section.
template <class ELFT>
static std::string maybeReportDiscarded(Ctx &ctx, Undefined &sym) { … }

namespace {
// Undefined diagnostics are collected in a vector and emitted once all of
// them are known, so that some postprocessing on the list of undefined symbols
// can happen before lld emits diagnostics.
struct UndefinedDiag { … };

std::vector<UndefinedDiag> undefs;
std::mutex relocMutex;
}

// Check whether the definition name def is a mangled function name that matches
// the reference name ref.
static bool canSuggestExternCForCXX(StringRef ref, StringRef def) { … }

// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
// the suggested symbol, which is either in the symbol table, or in the same
// file of sym.
static const Symbol *getAlternativeSpelling(const Undefined &sym,
                                            std::string &pre_hint,
                                            std::string &post_hint) { … }

static void reportUndefinedSymbol(Ctx &ctx, const UndefinedDiag &undef,
                                  bool correctSpelling) { … }

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

// Report an undefined symbol if necessary.
// Returns true if the undefined symbol will produce an error message.
static bool maybeReportUndefined(Ctx &ctx, Undefined &sym,
                                 InputSectionBase &sec, uint64_t offset) { … }

// MIPS N32 ABI treats series of successive relocations with the same offset
// as a single relocation. The similar approach used by N64 ABI, but this ABI
// packs all relocations into the single relocation record. Here we emulate
// this for the N32 ABI. Iterate over relocation with the same offset and put
// theirs types into the single bit-set.
template <class RelTy>
RelType RelocationScanner::getMipsN32RelType(RelTy *&rel) const { … }

template <bool shard = false>
static void addRelativeReloc(InputSectionBase &isec, uint64_t offsetInSec,
                             Symbol &sym, int64_t addend, RelExpr expr,
                             RelType type) { … }

template <class PltSection, class GotPltSection>
static void addPltEntry(PltSection &plt, GotPltSection &gotPlt,
                        RelocationBaseSection &rel, RelType type, Symbol &sym) { … }

void elf::addGotEntry(Ctx &ctx, Symbol &sym) { … }

static void addTpOffsetGotEntry(Ctx &ctx, Symbol &sym) { … }

// Return true if we can define a symbol in the executable that
// contains the value/function of a symbol defined in a shared
// library.
static bool canDefineSymbolInExecutable(Ctx &ctx, Symbol &sym) { … }

// Returns true if a given relocation can be computed at link-time.
// This only handles relocation types expected in processAux.
//
// For instance, we know the offset from a relocation to its target at
// link-time if the relocation is PC-relative and refers a
// non-interposable function in the same executable. This function
// will return true for such relocation.
//
// If this function returns false, that means we need to emit a
// dynamic relocation so that the relocation will be fixed at load-time.
bool RelocationScanner::isStaticLinkTimeConstant(RelExpr e, RelType type,
                                                 const Symbol &sym,
                                                 uint64_t relOff) const { … }

// The reason we have to do this early scan is as follows
// * To mmap the output file, we need to know the size
// * For that, we need to know how many dynamic relocs we will have.
// It might be possible to avoid this by outputting the file with write:
// * Write the allocated output sections, computing addresses.
// * Apply relocations, recording which ones require a dynamic reloc.
// * Write the dynamic relocations.
// * Write the rest of the file.
// This would have some drawbacks. For example, we would only know if .rela.dyn
// is needed after applying relocations. If it is, it will go after rw and rx
// sections. Given that it is ro, we will need an extra PT_LOAD. This
// complicates things for the dynamic linker and means we would have to reserve
// space for the extra PT_LOAD even if we end up not using it.
void RelocationScanner::processAux(RelExpr expr, RelType type, uint64_t offset,
                                   Symbol &sym, int64_t addend) const { … }

// This function is similar to the `handleTlsRelocation`. MIPS does not
// support any relaxations for TLS relocations so by factoring out MIPS
// handling in to the separate function we can simplify the code and do not
// pollute other `handleTlsRelocation` by MIPS `ifs` statements.
// Mips has a custom MipsGotSection that handles the writing of GOT entries
// without dynamic relocations.
static unsigned handleMipsTlsRelocation(Ctx &ctx, RelType type, Symbol &sym,
                                        InputSectionBase &c, uint64_t offset,
                                        int64_t addend, RelExpr expr) { … }

// Notes about General Dynamic and Local Dynamic TLS models below. They may
// require the generation of a pair of GOT entries that have associated dynamic
// relocations. The pair of GOT entries created are of the form GOT[e0] Module
// Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of
// symbol in TLS block.
//
// Returns the number of relocations processed.
unsigned RelocationScanner::handleTlsRelocation(RelExpr expr, RelType type,
                                                uint64_t offset, Symbol &sym,
                                                int64_t addend) { … }

template <class ELFT, class RelTy>
void RelocationScanner::scanOne(typename Relocs<RelTy>::const_iterator &i) { … }

// R_PPC64_TLSGD/R_PPC64_TLSLD is required to mark `bl __tls_get_addr` for
// General Dynamic/Local Dynamic code sequences. If a GD/LD GOT relocation is
// found but no R_PPC64_TLSGD/R_PPC64_TLSLD is seen, we assume that the
// instructions are generated by very old IBM XL compilers. Work around the
// issue by disabling GD/LD to IE/LE relaxation.
template <class RelTy>
static void checkPPC64TLSRelax(InputSectionBase &sec, Relocs<RelTy> rels) { … }

template <class ELFT, class RelTy>
void RelocationScanner::scan(Relocs<RelTy> rels) { … }

template <class ELFT>
void RelocationScanner::scanSection(InputSectionBase &s, bool isEH) { … }

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

static bool handleNonPreemptibleIfunc(Ctx &ctx, Symbol &sym, uint16_t flags) { … }

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

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

// Call Fn on every executable InputSection accessed via the linker script
// InputSectionDescription::Sections.
static void forEachInputSectionDescription(
    ArrayRef<OutputSection *> outputSections,
    llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) { … }

// Thunk Implementation
//
// Thunks (sometimes called stubs, veneers or branch islands) are small pieces
// of code that the linker inserts inbetween a caller and a callee. The thunks
// are added at link time rather than compile time as the decision on whether
// a thunk is needed, such as the caller and callee being out of range, can only
// be made at link time.
//
// It is straightforward to tell given the current state of the program when a
// thunk is needed for a particular call. The more difficult part is that
// the thunk needs to be placed in the program such that the caller can reach
// the thunk and the thunk can reach the callee; furthermore, adding thunks to
// the program alters addresses, which can mean more thunks etc.
//
// In lld we have a synthetic ThunkSection that can hold many Thunks.
// The decision to have a ThunkSection act as a container means that we can
// more easily handle the most common case of a single block of contiguous
// Thunks by inserting just a single ThunkSection.
//
// The implementation of Thunks in lld is split across these areas
// Relocations.cpp : Framework for creating and placing thunks
// Thunks.cpp : The code generated for each supported thunk
// Target.cpp : Target specific hooks that the framework uses to decide when
//              a thunk is used
// Synthetic.cpp : Implementation of ThunkSection
// Writer.cpp : Iteratively call framework until no more Thunks added
//
// Thunk placement requirements:
// Mips LA25 thunks. These must be placed immediately before the callee section
// We can assume that the caller is in range of the Thunk. These are modelled
// by Thunks that return the section they must precede with
// getTargetInputSection().
//
// ARM interworking and range extension thunks. These thunks must be placed
// within range of the caller. All implemented ARM thunks can always reach the
// callee as they use an indirect jump via a register that has no range
// restrictions.
//
// Thunk placement algorithm:
// For Mips LA25 ThunkSections; the placement is explicit, it has to be before
// getTargetInputSection().
//
// For thunks that must be placed within range of the caller there are many
// possible choices given that the maximum range from the caller is usually
// much larger than the average InputSection size. Desirable properties include:
// - Maximize reuse of thunks by multiple callers
// - Minimize number of ThunkSections to simplify insertion
// - Handle impact of already added Thunks on addresses
// - Simple to understand and implement
//
// In lld for the first pass, we pre-create one or more ThunkSections per
// InputSectionDescription at Target specific intervals. A ThunkSection is
// placed so that the estimated end of the ThunkSection is within range of the
// start of the InputSectionDescription or the previous ThunkSection. For
// example:
// InputSectionDescription
// Section 0
// ...
// Section N
// ThunkSection 0
// Section N + 1
// ...
// Section N + K
// Thunk Section 1
//
// The intention is that we can add a Thunk to a ThunkSection that is well
// spaced enough to service a number of callers without having to do a lot
// of work. An important principle is that it is not an error if a Thunk cannot
// be placed in a pre-created ThunkSection; when this happens we create a new
// ThunkSection placed next to the caller. This allows us to handle the vast
// majority of thunks simply, but also handle rare cases where the branch range
// is smaller than the target specific spacing.
//
// The algorithm is expected to create all the thunks that are needed in a
// single pass, with a small number of programs needing a second pass due to
// the insertion of thunks in the first pass increasing the offset between
// callers and callees that were only just in range.
//
// A consequence of allowing new ThunkSections to be created outside of the
// pre-created ThunkSections is that in rare cases calls to Thunks that were in
// range in pass K, are out of range in some pass > K due to the insertion of
// more Thunks in between the caller and callee. When this happens we retarget
// the relocation back to the original target and create another Thunk.

// Remove ThunkSections that are empty, this should only be the initial set
// precreated on pass 0.

// Insert the Thunks for OutputSection OS into their designated place
// in the Sections vector, and recalculate the InputSection output section
// offsets.
// This may invalidate any output section offsets stored outside of InputSection
void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) { … }

static int64_t getPCBias(Ctx &ctx, RelType type) { … }

// Find or create a ThunkSection within the InputSectionDescription (ISD) that
// is in range of Src. An ISD maps to a range of InputSections described by a
// linker script section pattern such as { .text .text.* }.
ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os,
                                           InputSection *isec,
                                           InputSectionDescription *isd,
                                           const Relocation &rel,
                                           uint64_t src) { … }

// Add a Thunk that needs to be placed in a ThunkSection that immediately
// precedes its Target.
ThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) { … }

// Create one or more ThunkSections per OS that can be used to place Thunks.
// We attempt to place the ThunkSections using the following desirable
// properties:
// - Within range of the maximum number of callers
// - Minimise the number of ThunkSections
//
// We follow a simple but conservative heuristic to place ThunkSections at
// offsets that are multiples of a Target specific branch range.
// For an InputSectionDescription that is smaller than the range, a single
// ThunkSection at the end of the range will do.
//
// For an InputSectionDescription that is more than twice the size of the range,
// we place the last ThunkSection at range bytes from the end of the
// InputSectionDescription in order to increase the likelihood that the
// distance from a thunk to its target will be sufficiently small to
// allow for the creation of a short thunk.
void ThunkCreator::createInitialThunkSections(
    ArrayRef<OutputSection *> outputSections) { … }

ThunkSection *ThunkCreator::addThunkSection(OutputSection *os,
                                            InputSectionDescription *isd,
                                            uint64_t off) { … }

static bool isThunkSectionCompatible(InputSection *source,
                                     SectionBase *target) { … }

std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
                                                Relocation &rel, uint64_t src) { … }

std::pair<Thunk *, bool> ThunkCreator::getSyntheticLandingPad(Defined &d,
                                                              int64_t a) { … }

// Return true if the relocation target is an in range Thunk.
// Return false if the relocation is not to a Thunk. If the relocation target
// was originally to a Thunk, but is no longer in range we revert the
// relocation back to its original non-Thunk target.
bool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) { … }

// Process all relocations from the InputSections that have been assigned
// to InputSectionDescriptions and redirect through Thunks if needed. The
// function should be called iteratively until it returns false.
//
// PreConditions:
// All InputSections that may need a Thunk are reachable from
// OutputSectionCommands.
//
// All OutputSections have an address and all InputSections have an offset
// within the OutputSection.
//
// The offsets between caller (relocation place) and callee
// (relocation target) will not be modified outside of createThunks().
//
// PostConditions:
// If return value is true then ThunkSections have been inserted into
// OutputSections. All relocations that needed a Thunk based on the information
// available to createThunks() on entry have been redirected to a Thunk. Note
// that adding Thunks changes offsets between caller and callee so more Thunks
// may be required.
//
// If return value is false then no more Thunks are needed, and createThunks has
// made no changes. If the target requires range extension thunks, currently
// ARM, then any future change in offset between caller and callee risks a
// relocation out of range error.
bool ThunkCreator::createThunks(uint32_t pass,
                                ArrayRef<OutputSection *> outputSections) { … }

// The following aid in the conversion of call x@GDPLT to call __tls_get_addr
// hexagonNeedsTLSSymbol scans for relocations would require a call to
// __tls_get_addr.
// hexagonTLSSymbolUpdate rebinds the relocation to __tls_get_addr.
bool elf::hexagonNeedsTLSSymbol(ArrayRef<OutputSection *> outputSections) { … }

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

static bool matchesRefTo(const NoCrossRefCommand &cmd, StringRef osec) { … }

template <class ELFT, class Rels>
static void scanCrossRefs(Ctx &ctx, const NoCrossRefCommand &cmd,
                          OutputSection *osec, InputSection *sec, Rels rels) { … }

// For each output section described by at least one NOCROSSREFS(_TO) command,
// scan relocations from its input sections for prohibited cross references.
template <class ELFT> void elf::checkNoCrossRefs(Ctx &ctx) { … }

template void elf::scanRelocations<ELF32LE>(Ctx &);
template void elf::scanRelocations<ELF32BE>(Ctx &);
template void elf::scanRelocations<ELF64LE>(Ctx &);
template void elf::scanRelocations<ELF64BE>(Ctx &);

template void elf::checkNoCrossRefs<ELF32LE>(Ctx &);
template void elf::checkNoCrossRefs<ELF32BE>(Ctx &);
template void elf::checkNoCrossRefs<ELF64LE>(Ctx &);
template void elf::checkNoCrossRefs<ELF64BE>(Ctx &);