//===- 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(const Symbol &sym) { … } static std::string getDefinedLocation(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(InputSectionBase &s, const Symbol &sym, uint64_t off) { … } void elf::reportRangeError(uint8_t *loc, const Relocation &rel, const Twine &v, int64_t min, uint64_t max) { … } void elf::reportRangeError(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(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(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(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(const UndefinedDiag &undef, bool correctSpelling) { … } void elf::reportUndefinedSymbols() { … } // Report an undefined symbol if necessary. // Returns true if the undefined symbol will produce an error message. static bool maybeReportUndefined(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(Symbol &sym) { … } static void addTpOffsetGotEntry(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(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(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. static unsigned handleTlsRelocation(RelType type, Symbol &sym, InputSectionBase &c, uint64_t offset, int64_t addend, RelExpr expr) { … } 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() { … } static bool handleNonPreemptibleIfunc(Symbol &sym, uint16_t flags) { … } void elf::postScanRelocations() { … } 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(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) { … } // 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(ArrayRef<OutputSection *> outputSections) { … } static bool matchesRefTo(const NoCrossRefCommand &cmd, StringRef osec) { … } template <class ELFT, class Rels> static void scanCrossRefs(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() { … } template void elf::scanRelocations<ELF32LE>(); template void elf::scanRelocations<ELF32BE>(); template void elf::scanRelocations<ELF64LE>(); template void elf::scanRelocations<ELF64BE>(); template void elf::checkNoCrossRefs<ELF32LE>(); template void elf::checkNoCrossRefs<ELF32BE>(); template void elf::checkNoCrossRefs<ELF64LE>(); template void elf::checkNoCrossRefs<ELF64BE>();
Codebase Browser
llvm