1 //===- Relocations.cpp ----------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains platform-independent functions to process relocations.
11 // I'll describe the overview of this file here.
13 // Simple relocations are easy to handle for the linker. For example,
14 // for R_X86_64_PC64 relocs, the linker just has to fix up locations
15 // with the relative offsets to the target symbols. It would just be
16 // reading records from relocation sections and applying them to output.
18 // But not all relocations are that easy to handle. For example, for
19 // R_386_GOTOFF relocs, the linker has to create new GOT entries for
20 // symbols if they don't exist, and fix up locations with GOT entry
21 // offsets from the beginning of GOT section. So there is more than
22 // fixing addresses in relocation processing.
24 // ELF defines a large number of complex relocations.
26 // The functions in this file analyze relocations and do whatever needs
27 // to be done. It includes, but not limited to, the following.
29 // - create GOT/PLT entries
30 // - create new relocations in .dynsym to let the dynamic linker resolve
31 // them at runtime (since ELF supports dynamic linking, not all
32 // relocations can be resolved at link-time)
33 // - create COPY relocs and reserve space in .bss
34 // - replace expensive relocs (in terms of runtime cost) with cheap ones
35 // - error out infeasible combinations such as PIC and non-relative relocs
37 // Note that the functions in this file don't actually apply relocations
38 // because it doesn't know about the output file nor the output file buffer.
39 // It instead stores Relocation objects to InputSection's Relocations
40 // vector to let it apply later in InputSection::writeTo.
42 //===----------------------------------------------------------------------===//
44 #include "Relocations.h"
46 #include "LinkerScript.h"
47 #include "OutputSections.h"
48 #include "SymbolTable.h"
50 #include "SyntheticSections.h"
53 #include "lld/Common/ErrorHandler.h"
54 #include "lld/Common/Memory.h"
55 #include "lld/Common/Strings.h"
56 #include "llvm/ADT/SmallSet.h"
57 #include "llvm/Support/Endian.h"
58 #include "llvm/Support/raw_ostream.h"
62 using namespace llvm::ELF;
63 using namespace llvm::object;
64 using namespace llvm::support::endian;
67 using namespace lld::elf;
69 static Optional<std::string> getLinkerScriptLocation(const Symbol &Sym) {
70 for (BaseCommand *Base : Script->SectionCommands)
71 if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
77 // Construct a message in the following format.
79 // >>> defined in /home/alice/src/foo.o
80 // >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
81 // >>> /home/alice/src/bar.o:(.text+0x1)
82 static std::string getLocation(InputSectionBase &S, const Symbol &Sym,
84 std::string Msg = "\n>>> defined in ";
86 Msg += toString(Sym.File);
87 else if (Optional<std::string> Loc = getLinkerScriptLocation(Sym))
90 Msg += "\n>>> referenced by ";
91 std::string Src = S.getSrcMsg(Sym, Off);
93 Msg += Src + "\n>>> ";
94 return Msg + S.getObjMsg(Off);
97 // This function is similar to the `handleTlsRelocation`. MIPS does not
98 // support any relaxations for TLS relocations so by factoring out MIPS
99 // handling in to the separate function we can simplify the code and do not
100 // pollute other `handleTlsRelocation` by MIPS `ifs` statements.
101 // Mips has a custom MipsGotSection that handles the writing of GOT entries
102 // without dynamic relocations.
103 static unsigned handleMipsTlsRelocation(RelType Type, Symbol &Sym,
104 InputSectionBase &C, uint64_t Offset,
105 int64_t Addend, RelExpr Expr) {
106 if (Expr == R_MIPS_TLSLD) {
107 In.MipsGot->addTlsIndex(*C.File);
108 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
111 if (Expr == R_MIPS_TLSGD) {
112 In.MipsGot->addDynTlsEntry(*C.File, Sym);
113 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
119 // This function is similar to the `handleMipsTlsRelocation`. ARM also does not
120 // support any relaxations for TLS relocations. ARM is logically similar to Mips
121 // in how it handles TLS, but Mips uses its own custom GOT which handles some
122 // of the cases that ARM uses GOT relocations for.
124 // We look for TLS global dynamic and local dynamic relocations, these may
125 // require the generation of a pair of GOT entries that have associated
126 // dynamic relocations. When the results of the dynamic relocations can be
127 // resolved at static link time we do so. This is necessary for static linking
128 // as there will be no dynamic loader to resolve them at load-time.
130 // The pair of GOT entries created are of the form
131 // GOT[e0] Module Index (Used to find pointer to TLS block at run-time)
132 // GOT[e1] Offset of symbol in TLS block
133 template <class ELFT>
134 static unsigned handleARMTlsRelocation(RelType Type, Symbol &Sym,
135 InputSectionBase &C, uint64_t Offset,
136 int64_t Addend, RelExpr Expr) {
137 // The Dynamic TLS Module Index Relocation for a symbol defined in an
138 // executable is always 1. If the target Symbol is not preemptible then
139 // we know the offset into the TLS block at static link time.
140 bool NeedDynId = Sym.IsPreemptible || Config->Shared;
141 bool NeedDynOff = Sym.IsPreemptible;
143 auto AddTlsReloc = [&](uint64_t Off, RelType Type, Symbol *Dest, bool Dyn) {
145 In.RelaDyn->addReloc(Type, In.Got, Off, Dest);
147 In.Got->Relocations.push_back({R_ABS, Type, Off, 0, Dest});
150 // Local Dynamic is for access to module local TLS variables, while still
151 // being suitable for being dynamically loaded via dlopen.
152 // GOT[e0] is the module index, with a special value of 0 for the current
153 // module. GOT[e1] is unused. There only needs to be one module index entry.
154 if (Expr == R_TLSLD_PC && In.Got->addTlsIndex()) {
155 AddTlsReloc(In.Got->getTlsIndexOff(), Target->TlsModuleIndexRel,
156 NeedDynId ? nullptr : &Sym, NeedDynId);
157 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
161 // Global Dynamic is the most general purpose access model. When we know
162 // the module index and offset of symbol in TLS block we can fill these in
163 // using static GOT relocations.
164 if (Expr == R_TLSGD_PC) {
165 if (In.Got->addDynTlsEntry(Sym)) {
166 uint64_t Off = In.Got->getGlobalDynOffset(Sym);
167 AddTlsReloc(Off, Target->TlsModuleIndexRel, &Sym, NeedDynId);
168 AddTlsReloc(Off + Config->Wordsize, Target->TlsOffsetRel, &Sym,
171 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
177 // Returns the number of relocations processed.
178 template <class ELFT>
180 handleTlsRelocation(RelType Type, Symbol &Sym, InputSectionBase &C,
181 typename ELFT::uint Offset, int64_t Addend, RelExpr Expr) {
185 if (Config->EMachine == EM_ARM)
186 return handleARMTlsRelocation<ELFT>(Type, Sym, C, Offset, Addend, Expr);
187 if (Config->EMachine == EM_MIPS)
188 return handleMipsTlsRelocation(Type, Sym, C, Offset, Addend, Expr);
190 if (isRelExprOneOf<R_TLSDESC, R_AARCH64_TLSDESC_PAGE, R_TLSDESC_CALL>(Expr) &&
192 if (In.Got->addDynTlsEntry(Sym)) {
193 uint64_t Off = In.Got->getGlobalDynOffset(Sym);
194 In.RelaDyn->addReloc(
195 {Target->TlsDescRel, In.Got, Off, !Sym.IsPreemptible, &Sym, 0});
197 if (Expr != R_TLSDESC_CALL)
198 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
202 if (isRelExprOneOf<R_TLSLD_GOT, R_TLSLD_GOT_FROM_END, R_TLSLD_PC,
203 R_TLSLD_HINT>(Expr)) {
204 // Local-Dynamic relocs can be relaxed to Local-Exec.
205 if (!Config->Shared) {
206 C.Relocations.push_back(
207 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_LD_TO_LE), Type,
208 Offset, Addend, &Sym});
209 return Target->TlsGdRelaxSkip;
211 if (Expr == R_TLSLD_HINT)
213 if (In.Got->addTlsIndex())
214 In.RelaDyn->addReloc(Target->TlsModuleIndexRel, In.Got,
215 In.Got->getTlsIndexOff(), nullptr);
216 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
220 // Local-Dynamic relocs can be relaxed to Local-Exec.
221 if (Expr == R_ABS && !Config->Shared) {
222 C.Relocations.push_back(
223 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_LD_TO_LE), Type,
224 Offset, Addend, &Sym});
228 // Local-Dynamic sequence where offset of tls variable relative to dynamic
229 // thread pointer is stored in the got.
230 if (Expr == R_TLSLD_GOT_OFF) {
231 // Local-Dynamic relocs can be relaxed to local-exec
232 if (!Config->Shared) {
233 C.Relocations.push_back({R_RELAX_TLS_LD_TO_LE, Type, Offset, Addend, &Sym});
236 if (!Sym.isInGot()) {
237 In.Got->addEntry(Sym);
238 uint64_t Off = Sym.getGotOffset();
239 In.Got->Relocations.push_back(
240 {R_ABS, Target->TlsOffsetRel, Off, 0, &Sym});
242 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
246 if (isRelExprOneOf<R_TLSDESC, R_AARCH64_TLSDESC_PAGE, R_TLSDESC_CALL,
247 R_TLSGD_GOT, R_TLSGD_GOT_FROM_END, R_TLSGD_PC>(Expr)) {
248 if (Config->Shared) {
249 if (In.Got->addDynTlsEntry(Sym)) {
250 uint64_t Off = In.Got->getGlobalDynOffset(Sym);
251 In.RelaDyn->addReloc(Target->TlsModuleIndexRel, In.Got, Off, &Sym);
253 // If the symbol is preemptible we need the dynamic linker to write
255 uint64_t OffsetOff = Off + Config->Wordsize;
256 if (Sym.IsPreemptible)
257 In.RelaDyn->addReloc(Target->TlsOffsetRel, In.Got, OffsetOff, &Sym);
259 In.Got->Relocations.push_back(
260 {R_ABS, Target->TlsOffsetRel, OffsetOff, 0, &Sym});
262 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
266 // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec
267 // depending on the symbol being locally defined or not.
268 if (Sym.IsPreemptible) {
269 C.Relocations.push_back(
270 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_IE), Type,
271 Offset, Addend, &Sym});
272 if (!Sym.isInGot()) {
273 In.Got->addEntry(Sym);
274 In.RelaDyn->addReloc(Target->TlsGotRel, In.Got, Sym.getGotOffset(),
278 C.Relocations.push_back(
279 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_LE), Type,
280 Offset, Addend, &Sym});
282 return Target->TlsGdRelaxSkip;
285 // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally
287 if (isRelExprOneOf<R_GOT, R_GOT_FROM_END, R_GOT_PC, R_AARCH64_GOT_PAGE_PC,
288 R_GOT_OFF, R_TLSIE_HINT>(Expr) &&
289 !Config->Shared && !Sym.IsPreemptible) {
290 C.Relocations.push_back({R_RELAX_TLS_IE_TO_LE, Type, Offset, Addend, &Sym});
294 if (Expr == R_TLSIE_HINT)
299 static RelType getMipsPairType(RelType Type, bool IsLocal) {
304 // In case of global symbol, the R_MIPS_GOT16 relocation does not
305 // have a pair. Each global symbol has a unique entry in the GOT
306 // and a corresponding instruction with help of the R_MIPS_GOT16
307 // relocation loads an address of the symbol. In case of local
308 // symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold
309 // the high 16 bits of the symbol's value. A paired R_MIPS_LO16
310 // relocations handle low 16 bits of the address. That allows
311 // to allocate only one GOT entry for every 64 KBytes of local data.
312 return IsLocal ? R_MIPS_LO16 : R_MIPS_NONE;
313 case R_MICROMIPS_GOT16:
314 return IsLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE;
316 return R_MIPS_PCLO16;
317 case R_MICROMIPS_HI16:
318 return R_MICROMIPS_LO16;
324 // True if non-preemptable symbol always has the same value regardless of where
325 // the DSO is loaded.
326 static bool isAbsolute(const Symbol &Sym) {
327 if (Sym.isUndefWeak())
329 if (const auto *DR = dyn_cast<Defined>(&Sym))
330 return DR->Section == nullptr; // Absolute symbol.
334 static bool isAbsoluteValue(const Symbol &Sym) {
335 return isAbsolute(Sym) || Sym.isTls();
338 // Returns true if Expr refers a PLT entry.
339 static bool needsPlt(RelExpr Expr) {
340 return isRelExprOneOf<R_PLT_PC, R_PPC_CALL_PLT, R_PLT>(Expr);
343 // Returns true if Expr refers a GOT entry. Note that this function
344 // returns false for TLS variables even though they need GOT, because
345 // TLS variables uses GOT differently than the regular variables.
346 static bool needsGot(RelExpr Expr) {
347 return isRelExprOneOf<R_GOT, R_GOT_OFF, R_HEXAGON_GOT, R_MIPS_GOT_LOCAL_PAGE,
348 R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC,
349 R_GOT_PC, R_GOT_FROM_END>(Expr);
352 // True if this expression is of the form Sym - X, where X is a position in the
353 // file (PC, or GOT for example).
354 static bool isRelExpr(RelExpr Expr) {
355 return isRelExprOneOf<R_PC, R_GOTREL, R_GOTREL_FROM_END, R_MIPS_GOTREL,
356 R_PPC_CALL, R_PPC_CALL_PLT, R_AARCH64_PAGE_PC,
357 R_RELAX_GOT_PC>(Expr);
360 // Returns true if a given relocation can be computed at link-time.
362 // For instance, we know the offset from a relocation to its target at
363 // link-time if the relocation is PC-relative and refers a
364 // non-interposable function in the same executable. This function
365 // will return true for such relocation.
367 // If this function returns false, that means we need to emit a
368 // dynamic relocation so that the relocation will be fixed at load-time.
369 static bool isStaticLinkTimeConstant(RelExpr E, RelType Type, const Symbol &Sym,
370 InputSectionBase &S, uint64_t RelOff) {
371 // These expressions always compute a constant
372 if (isRelExprOneOf<R_GOT_FROM_END, R_GOT_OFF, R_HEXAGON_GOT, R_TLSLD_GOT_OFF,
373 R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF,
374 R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD,
375 R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC,
376 R_GOTONLY_PC_FROM_END, R_PLT_PC, R_TLSGD_GOT,
377 R_TLSGD_GOT_FROM_END, R_TLSGD_PC, R_PPC_CALL_PLT,
378 R_TLSDESC_CALL, R_AARCH64_TLSDESC_PAGE, R_HINT,
379 R_TLSLD_HINT, R_TLSIE_HINT>(E))
382 // These never do, except if the entire file is position dependent or if
383 // only the low bits are used.
384 if (E == R_GOT || E == R_PLT || E == R_TLSDESC)
385 return Target->usesOnlyLowPageBits(Type) || !Config->Pic;
387 if (Sym.IsPreemptible)
392 // The size of a non preemptible symbol is a constant.
396 // For the target and the relocation, we want to know if they are
397 // absolute or relative.
398 bool AbsVal = isAbsoluteValue(Sym);
399 bool RelE = isRelExpr(E);
404 if (!AbsVal && !RelE)
405 return Target->usesOnlyLowPageBits(Type);
407 // Relative relocation to an absolute value. This is normally unrepresentable,
408 // but if the relocation refers to a weak undefined symbol, we allow it to
409 // resolve to the image base. This is a little strange, but it allows us to
410 // link function calls to such symbols. Normally such a call will be guarded
411 // with a comparison, which will load a zero from the GOT.
412 // Another special case is MIPS _gp_disp symbol which represents offset
413 // between start of a function and '_gp' value and defined as absolute just
414 // to simplify the code.
415 assert(AbsVal && RelE);
416 if (Sym.isUndefWeak())
419 error("relocation " + toString(Type) + " cannot refer to absolute symbol: " +
420 toString(Sym) + getLocation(S, Sym, RelOff));
424 static RelExpr toPlt(RelExpr Expr) {
427 return R_PPC_CALL_PLT;
437 static RelExpr fromPlt(RelExpr Expr) {
438 // We decided not to use a plt. Optimize a reference to the plt to a
439 // reference to the symbol itself.
452 // Returns true if a given shared symbol is in a read-only segment in a DSO.
453 template <class ELFT> static bool isReadOnly(SharedSymbol &SS) {
454 typedef typename ELFT::Phdr Elf_Phdr;
456 // Determine if the symbol is read-only by scanning the DSO's program headers.
457 const SharedFile<ELFT> &File = SS.getFile<ELFT>();
458 for (const Elf_Phdr &Phdr : check(File.getObj().program_headers()))
459 if ((Phdr.p_type == ELF::PT_LOAD || Phdr.p_type == ELF::PT_GNU_RELRO) &&
460 !(Phdr.p_flags & ELF::PF_W) && SS.Value >= Phdr.p_vaddr &&
461 SS.Value < Phdr.p_vaddr + Phdr.p_memsz)
466 // Returns symbols at the same offset as a given symbol, including SS itself.
468 // If two or more symbols are at the same offset, and at least one of
469 // them are copied by a copy relocation, all of them need to be copied.
470 // Otherwise, they would refer to different places at runtime.
471 template <class ELFT>
472 static SmallSet<SharedSymbol *, 4> getSymbolsAt(SharedSymbol &SS) {
473 typedef typename ELFT::Sym Elf_Sym;
475 SharedFile<ELFT> &File = SS.getFile<ELFT>();
477 SmallSet<SharedSymbol *, 4> Ret;
478 for (const Elf_Sym &S : File.getGlobalELFSyms()) {
479 if (S.st_shndx == SHN_UNDEF || S.st_shndx == SHN_ABS ||
480 S.getType() == STT_TLS || S.st_value != SS.Value)
482 StringRef Name = check(S.getName(File.getStringTable()));
483 Symbol *Sym = Symtab->find(Name);
484 if (auto *Alias = dyn_cast_or_null<SharedSymbol>(Sym))
490 // When a symbol is copy relocated or we create a canonical plt entry, it is
491 // effectively a defined symbol. In the case of copy relocation the symbol is
492 // in .bss and in the case of a canonical plt entry it is in .plt. This function
493 // replaces the existing symbol with a Defined pointing to the appropriate
495 static void replaceWithDefined(Symbol &Sym, SectionBase *Sec, uint64_t Value,
498 replaceSymbol<Defined>(&Sym, Sym.File, Sym.getName(), Sym.Binding,
499 Sym.StOther, Sym.Type, Value, Size, Sec);
500 Sym.PltIndex = Old.PltIndex;
501 Sym.GotIndex = Old.GotIndex;
502 Sym.VerdefIndex = Old.VerdefIndex;
503 Sym.PPC64BranchltIndex = Old.PPC64BranchltIndex;
504 Sym.IsPreemptible = true;
505 Sym.ExportDynamic = true;
506 Sym.IsUsedInRegularObj = true;
510 // Reserve space in .bss or .bss.rel.ro for copy relocation.
512 // The copy relocation is pretty much a hack. If you use a copy relocation
513 // in your program, not only the symbol name but the symbol's size, RW/RO
514 // bit and alignment become part of the ABI. In addition to that, if the
515 // symbol has aliases, the aliases become part of the ABI. That's subtle,
516 // but if you violate that implicit ABI, that can cause very counter-
517 // intuitive consequences.
519 // So, what is the copy relocation? It's for linking non-position
520 // independent code to DSOs. In an ideal world, all references to data
521 // exported by DSOs should go indirectly through GOT. But if object files
522 // are compiled as non-PIC, all data references are direct. There is no
523 // way for the linker to transform the code to use GOT, as machine
524 // instructions are already set in stone in object files. This is where
525 // the copy relocation takes a role.
527 // A copy relocation instructs the dynamic linker to copy data from a DSO
528 // to a specified address (which is usually in .bss) at load-time. If the
529 // static linker (that's us) finds a direct data reference to a DSO
530 // symbol, it creates a copy relocation, so that the symbol can be
531 // resolved as if it were in .bss rather than in a DSO.
533 // As you can see in this function, we create a copy relocation for the
534 // dynamic linker, and the relocation contains not only symbol name but
535 // various other informtion about the symbol. So, such attributes become a
538 // Note for application developers: I can give you a piece of advice if
539 // you are writing a shared library. You probably should export only
540 // functions from your library. You shouldn't export variables.
542 // As an example what can happen when you export variables without knowing
543 // the semantics of copy relocations, assume that you have an exported
544 // variable of type T. It is an ABI-breaking change to add new members at
545 // end of T even though doing that doesn't change the layout of the
546 // existing members. That's because the space for the new members are not
547 // reserved in .bss unless you recompile the main program. That means they
548 // are likely to overlap with other data that happens to be laid out next
549 // to the variable in .bss. This kind of issue is sometimes very hard to
550 // debug. What's a solution? Instead of exporting a varaible V from a DSO,
551 // define an accessor getV().
552 template <class ELFT> static void addCopyRelSymbol(SharedSymbol &SS) {
553 // Copy relocation against zero-sized symbol doesn't make sense.
554 uint64_t SymSize = SS.getSize();
555 if (SymSize == 0 || SS.Alignment == 0)
556 fatal("cannot create a copy relocation for symbol " + toString(SS));
558 // See if this symbol is in a read-only segment. If so, preserve the symbol's
559 // memory protection by reserving space in the .bss.rel.ro section.
560 bool IsReadOnly = isReadOnly<ELFT>(SS);
561 BssSection *Sec = make<BssSection>(IsReadOnly ? ".bss.rel.ro" : ".bss",
562 SymSize, SS.Alignment);
564 In.BssRelRo->getParent()->addSection(Sec);
566 In.Bss->getParent()->addSection(Sec);
568 // Look through the DSO's dynamic symbol table for aliases and create a
569 // dynamic symbol for each one. This causes the copy relocation to correctly
570 // interpose any aliases.
571 for (SharedSymbol *Sym : getSymbolsAt<ELFT>(SS))
572 replaceWithDefined(*Sym, Sec, 0, Sym->Size);
574 In.RelaDyn->addReloc(Target->CopyRel, Sec, 0, &SS);
577 // MIPS has an odd notion of "paired" relocations to calculate addends.
578 // For example, if a relocation is of R_MIPS_HI16, there must be a
579 // R_MIPS_LO16 relocation after that, and an addend is calculated using
580 // the two relocations.
581 template <class ELFT, class RelTy>
582 static int64_t computeMipsAddend(const RelTy &Rel, const RelTy *End,
583 InputSectionBase &Sec, RelExpr Expr,
585 if (Expr == R_MIPS_GOTREL && IsLocal)
586 return Sec.getFile<ELFT>()->MipsGp0;
588 // The ABI says that the paired relocation is used only for REL.
589 // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
593 RelType Type = Rel.getType(Config->IsMips64EL);
594 uint32_t PairTy = getMipsPairType(Type, IsLocal);
595 if (PairTy == R_MIPS_NONE)
598 const uint8_t *Buf = Sec.data().data();
599 uint32_t SymIndex = Rel.getSymbol(Config->IsMips64EL);
601 // To make things worse, paired relocations might not be contiguous in
602 // the relocation table, so we need to do linear search. *sigh*
603 for (const RelTy *RI = &Rel; RI != End; ++RI)
604 if (RI->getType(Config->IsMips64EL) == PairTy &&
605 RI->getSymbol(Config->IsMips64EL) == SymIndex)
606 return Target->getImplicitAddend(Buf + RI->r_offset, PairTy);
608 warn("can't find matching " + toString(PairTy) + " relocation for " +
613 // Returns an addend of a given relocation. If it is RELA, an addend
614 // is in a relocation itself. If it is REL, we need to read it from an
616 template <class ELFT, class RelTy>
617 static int64_t computeAddend(const RelTy &Rel, const RelTy *End,
618 InputSectionBase &Sec, RelExpr Expr,
621 RelType Type = Rel.getType(Config->IsMips64EL);
624 Addend = getAddend<ELFT>(Rel);
626 const uint8_t *Buf = Sec.data().data();
627 Addend = Target->getImplicitAddend(Buf + Rel.r_offset, Type);
630 if (Config->EMachine == EM_PPC64 && Config->Pic && Type == R_PPC64_TOC)
631 Addend += getPPC64TocBase();
632 if (Config->EMachine == EM_MIPS)
633 Addend += computeMipsAddend<ELFT>(Rel, End, Sec, Expr, IsLocal);
638 // Report an undefined symbol if necessary.
639 // Returns true if this function printed out an error message.
640 static bool maybeReportUndefined(Symbol &Sym, InputSectionBase &Sec,
642 if (Sym.isLocal() || !Sym.isUndefined() || Sym.isWeak())
646 Sym.computeBinding() != STB_LOCAL && Sym.Visibility == STV_DEFAULT;
647 if (Config->UnresolvedSymbols == UnresolvedPolicy::Ignore && CanBeExternal)
651 "undefined symbol: " + toString(Sym) + "\n>>> referenced by ";
653 std::string Src = Sec.getSrcMsg(Sym, Offset);
655 Msg += Src + "\n>>> ";
656 Msg += Sec.getObjMsg(Offset);
658 if (Sym.getName().startswith("_ZTV"))
659 Msg += "\nthe vtable symbol may be undefined because the class is missing "
660 "its key function (see https://lld.llvm.org/missingkeyfunction)";
662 if ((Config->UnresolvedSymbols == UnresolvedPolicy::Warn && CanBeExternal) ||
663 Config->NoinhibitExec) {
672 // MIPS N32 ABI treats series of successive relocations with the same offset
673 // as a single relocation. The similar approach used by N64 ABI, but this ABI
674 // packs all relocations into the single relocation record. Here we emulate
675 // this for the N32 ABI. Iterate over relocation with the same offset and put
676 // theirs types into the single bit-set.
677 template <class RelTy> static RelType getMipsN32RelType(RelTy *&Rel, RelTy *End) {
679 uint64_t Offset = Rel->r_offset;
682 while (Rel != End && Rel->r_offset == Offset)
683 Type |= (Rel++)->getType(Config->IsMips64EL) << (8 * N++);
687 // .eh_frame sections are mergeable input sections, so their input
688 // offsets are not linearly mapped to output section. For each input
689 // offset, we need to find a section piece containing the offset and
690 // add the piece's base address to the input offset to compute the
691 // output offset. That isn't cheap.
693 // This class is to speed up the offset computation. When we process
694 // relocations, we access offsets in the monotonically increasing
695 // order. So we can optimize for that access pattern.
697 // For sections other than .eh_frame, this class doesn't do anything.
701 explicit OffsetGetter(InputSectionBase &Sec) {
702 if (auto *Eh = dyn_cast<EhInputSection>(&Sec))
706 // Translates offsets in input sections to offsets in output sections.
707 // Given offset must increase monotonically. We assume that Piece is
708 // sorted by InputOff.
709 uint64_t get(uint64_t Off) {
713 while (I != Pieces.size() && Pieces[I].InputOff + Pieces[I].Size <= Off)
715 if (I == Pieces.size())
716 fatal(".eh_frame: relocation is not in any piece");
718 // Pieces must be contiguous, so there must be no holes in between.
719 assert(Pieces[I].InputOff <= Off && "Relocation not in any piece");
721 // Offset -1 means that the piece is dead (i.e. garbage collected).
722 if (Pieces[I].OutputOff == -1)
724 return Pieces[I].OutputOff + Off - Pieces[I].InputOff;
728 ArrayRef<EhSectionPiece> Pieces;
733 static void addRelativeReloc(InputSectionBase *IS, uint64_t OffsetInSec,
734 Symbol *Sym, int64_t Addend, RelExpr Expr,
736 // Add a relative relocation. If RelrDyn section is enabled, and the
737 // relocation offset is guaranteed to be even, add the relocation to
738 // the RelrDyn section, otherwise add it to the RelaDyn section.
739 // RelrDyn sections don't support odd offsets. Also, RelrDyn sections
740 // don't store the addend values, so we must write it to the relocated
742 if (In.RelrDyn && IS->Alignment >= 2 && OffsetInSec % 2 == 0) {
743 IS->Relocations.push_back({Expr, Type, OffsetInSec, Addend, Sym});
744 In.RelrDyn->Relocs.push_back({IS, OffsetInSec});
747 In.RelaDyn->addReloc(Target->RelativeRel, IS, OffsetInSec, Sym, Addend, Expr,
751 template <class ELFT, class GotPltSection>
752 static void addPltEntry(PltSection *Plt, GotPltSection *GotPlt,
753 RelocationBaseSection *Rel, RelType Type, Symbol &Sym) {
754 Plt->addEntry<ELFT>(Sym);
755 GotPlt->addEntry(Sym);
757 {Type, GotPlt, Sym.getGotPltOffset(), !Sym.IsPreemptible, &Sym, 0});
760 template <class ELFT> static void addGotEntry(Symbol &Sym) {
761 In.Got->addEntry(Sym);
763 RelExpr Expr = Sym.isTls() ? R_TLS : R_ABS;
764 uint64_t Off = Sym.getGotOffset();
766 // If a GOT slot value can be calculated at link-time, which is now,
767 // we can just fill that out.
769 // (We don't actually write a value to a GOT slot right now, but we
770 // add a static relocation to a Relocations vector so that
771 // InputSection::relocate will do the work for us. We may be able
772 // to just write a value now, but it is a TODO.)
773 bool IsLinkTimeConstant =
774 !Sym.IsPreemptible && (!Config->Pic || isAbsolute(Sym));
775 if (IsLinkTimeConstant) {
776 In.Got->Relocations.push_back({Expr, Target->GotRel, Off, 0, &Sym});
780 // Otherwise, we emit a dynamic relocation to .rel[a].dyn so that
781 // the GOT slot will be fixed at load-time.
782 if (!Sym.isTls() && !Sym.IsPreemptible && Config->Pic && !isAbsolute(Sym)) {
783 addRelativeReloc(In.Got, Off, &Sym, 0, R_ABS, Target->GotRel);
786 In.RelaDyn->addReloc(Sym.isTls() ? Target->TlsGotRel : Target->GotRel, In.Got,
787 Off, &Sym, 0, Sym.IsPreemptible ? R_ADDEND : R_ABS,
791 // Return true if we can define a symbol in the executable that
792 // contains the value/function of a symbol defined in a shared
794 static bool canDefineSymbolInExecutable(Symbol &Sym) {
795 // If the symbol has default visibility the symbol defined in the
796 // executable will preempt it.
797 // Note that we want the visibility of the shared symbol itself, not
798 // the visibility of the symbol in the output file we are producing. That is
799 // why we use Sym.StOther.
800 if ((Sym.StOther & 0x3) == STV_DEFAULT)
803 // If we are allowed to break address equality of functions, defining
804 // a plt entry will allow the program to call the function in the
805 // .so, but the .so and the executable will no agree on the address
806 // of the function. Similar logic for objects.
807 return ((Sym.isFunc() && Config->IgnoreFunctionAddressEquality) ||
808 (Sym.isObject() && Config->IgnoreDataAddressEquality));
811 // The reason we have to do this early scan is as follows
812 // * To mmap the output file, we need to know the size
813 // * For that, we need to know how many dynamic relocs we will have.
814 // It might be possible to avoid this by outputting the file with write:
815 // * Write the allocated output sections, computing addresses.
816 // * Apply relocations, recording which ones require a dynamic reloc.
817 // * Write the dynamic relocations.
818 // * Write the rest of the file.
819 // This would have some drawbacks. For example, we would only know if .rela.dyn
820 // is needed after applying relocations. If it is, it will go after rw and rx
821 // sections. Given that it is ro, we will need an extra PT_LOAD. This
822 // complicates things for the dynamic linker and means we would have to reserve
823 // space for the extra PT_LOAD even if we end up not using it.
824 template <class ELFT, class RelTy>
825 static void processRelocAux(InputSectionBase &Sec, RelExpr Expr, RelType Type,
826 uint64_t Offset, Symbol &Sym, const RelTy &Rel,
828 if (isStaticLinkTimeConstant(Expr, Type, Sym, Sec, Offset)) {
829 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
832 bool CanWrite = (Sec.Flags & SHF_WRITE) || !Config->ZText;
834 // R_GOT refers to a position in the got, even if the symbol is preemptible.
835 bool IsPreemptibleValue = Sym.IsPreemptible && Expr != R_GOT;
837 if (!IsPreemptibleValue) {
838 addRelativeReloc(&Sec, Offset, &Sym, Addend, Expr, Type);
840 } else if (RelType Rel = Target->getDynRel(Type)) {
841 In.RelaDyn->addReloc(Rel, &Sec, Offset, &Sym, Addend, R_ADDEND, Type);
843 // MIPS ABI turns using of GOT and dynamic relocations inside out.
844 // While regular ABI uses dynamic relocations to fill up GOT entries
845 // MIPS ABI requires dynamic linker to fills up GOT entries using
846 // specially sorted dynamic symbol table. This affects even dynamic
847 // relocations against symbols which do not require GOT entries
848 // creation explicitly, i.e. do not have any GOT-relocations. So if
849 // a preemptible symbol has a dynamic relocation we anyway have
850 // to create a GOT entry for it.
851 // If a non-preemptible symbol has a dynamic relocation against it,
852 // dynamic linker takes it st_value, adds offset and writes down
853 // result of the dynamic relocation. In case of preemptible symbol
854 // dynamic linker performs symbol resolution, writes the symbol value
855 // to the GOT entry and reads the GOT entry when it needs to perform
856 // a dynamic relocation.
857 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
858 if (Config->EMachine == EM_MIPS)
859 In.MipsGot->addEntry(*Sec.File, Sym, Addend, Expr);
864 // If the relocation is to a weak undef, and we are producing
865 // executable, give up on it and produce a non preemptible 0.
866 if (!Config->Shared && Sym.isUndefWeak()) {
867 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
871 if (!CanWrite && (Config->Pic && !isRelExpr(Expr))) {
873 "can't create dynamic relocation " + toString(Type) + " against " +
874 (Sym.getName().empty() ? "local symbol" : "symbol: " + toString(Sym)) +
875 " in readonly segment; recompile object files with -fPIC "
876 "or pass '-Wl,-z,notext' to allow text relocations in the output" +
877 getLocation(Sec, Sym, Offset));
881 // Copy relocations are only possible if we are creating an executable.
882 if (Config->Shared) {
883 errorOrWarn("relocation " + toString(Type) +
884 " cannot be used against symbol " + toString(Sym) +
885 "; recompile with -fPIC" + getLocation(Sec, Sym, Offset));
889 // If the symbol is undefined we already reported any relevant errors.
890 if (Sym.isUndefined())
893 if (!canDefineSymbolInExecutable(Sym)) {
894 error("cannot preempt symbol: " + toString(Sym) +
895 getLocation(Sec, Sym, Offset));
899 if (Sym.isObject()) {
900 // Produce a copy relocation.
901 if (auto *SS = dyn_cast<SharedSymbol>(&Sym)) {
902 if (!Config->ZCopyreloc)
903 error("unresolvable relocation " + toString(Type) +
904 " against symbol '" + toString(*SS) +
905 "'; recompile with -fPIC or remove '-z nocopyreloc'" +
906 getLocation(Sec, Sym, Offset));
907 addCopyRelSymbol<ELFT>(*SS);
909 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
914 // This handles a non PIC program call to function in a shared library. In
915 // an ideal world, we could just report an error saying the relocation can
916 // overflow at runtime. In the real world with glibc, crt1.o has a
917 // R_X86_64_PC32 pointing to libc.so.
919 // The general idea on how to handle such cases is to create a PLT entry and
920 // use that as the function value.
922 // For the static linking part, we just return a plt expr and everything
923 // else will use the PLT entry as the address.
925 // The remaining problem is making sure pointer equality still works. We
926 // need the help of the dynamic linker for that. We let it know that we have
927 // a direct reference to a so symbol by creating an undefined symbol with a
928 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to
929 // the value of the symbol we created. This is true even for got entries, so
930 // pointer equality is maintained. To avoid an infinite loop, the only entry
931 // that points to the real function is a dedicated got entry used by the
932 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT,
933 // R_386_JMP_SLOT, etc).
935 // For position independent executable on i386, the plt entry requires ebx
936 // to be set. This causes two problems:
937 // * If some code has a direct reference to a function, it was probably
938 // compiled without -fPIE/-fPIC and doesn't maintain ebx.
939 // * If a library definition gets preempted to the executable, it will have
940 // the wrong ebx value.
941 if (Config->Pie && Config->EMachine == EM_386)
942 errorOrWarn("symbol '" + toString(Sym) +
943 "' cannot be preempted; recompile with -fPIE" +
944 getLocation(Sec, Sym, Offset));
946 addPltEntry<ELFT>(In.Plt, In.GotPlt, In.RelaPlt, Target->PltRel, Sym);
947 if (!Sym.isDefined())
948 replaceWithDefined(Sym, In.Plt, getPltEntryOffset(Sym.PltIndex), 0);
949 Sym.NeedsPltAddr = true;
950 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
954 errorOrWarn("symbol '" + toString(Sym) + "' has no type" +
955 getLocation(Sec, Sym, Offset));
958 struct IRelativeReloc {
960 InputSectionBase *Sec;
965 static std::vector<IRelativeReloc> IRelativeRelocs;
967 template <class ELFT, class RelTy>
968 static void scanReloc(InputSectionBase &Sec, OffsetGetter &GetOffset, RelTy *&I,
970 const RelTy &Rel = *I;
971 Symbol &Sym = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
974 // Deal with MIPS oddity.
975 if (Config->MipsN32Abi) {
976 Type = getMipsN32RelType(I, End);
978 Type = Rel.getType(Config->IsMips64EL);
982 // Get an offset in an output section this relocation is applied to.
983 uint64_t Offset = GetOffset.get(Rel.r_offset);
984 if (Offset == uint64_t(-1))
987 // Skip if the target symbol is an erroneous undefined symbol.
988 if (maybeReportUndefined(Sym, Sec, Rel.r_offset))
991 const uint8_t *RelocatedAddr = Sec.data().begin() + Rel.r_offset;
992 RelExpr Expr = Target->getRelExpr(Type, Sym, RelocatedAddr);
994 // Ignore "hint" relocations because they are only markers for relaxation.
995 if (isRelExprOneOf<R_HINT, R_NONE>(Expr))
998 if (Sym.isGnuIFunc() && !Config->ZText && Config->WarnIfuncTextrel) {
999 warn("using ifunc symbols when text relocations are allowed may produce "
1000 "a binary that will segfault, if the object file is linked with "
1001 "old version of glibc (glibc 2.28 and earlier). If this applies to "
1002 "you, consider recompiling the object files without -fPIC and "
1003 "without -Wl,-z,notext option. Use -no-warn-ifunc-textrel to "
1004 "turn off this warning." +
1005 getLocation(Sec, Sym, Offset));
1008 // Relax relocations.
1010 // If we know that a PLT entry will be resolved within the same ELF module, we
1011 // can skip PLT access and directly jump to the destination function. For
1012 // example, if we are linking a main exectuable, all dynamic symbols that can
1013 // be resolved within the executable will actually be resolved that way at
1014 // runtime, because the main exectuable is always at the beginning of a search
1015 // list. We can leverage that fact.
1016 if (!Sym.IsPreemptible && (!Sym.isGnuIFunc() || Config->ZIfuncNoplt)) {
1017 if (Expr == R_GOT_PC && !isAbsoluteValue(Sym))
1018 Expr = Target->adjustRelaxExpr(Type, RelocatedAddr, Expr);
1020 Expr = fromPlt(Expr);
1023 // This relocation does not require got entry, but it is relative to got and
1024 // needs it to be created. Here we request for that.
1025 if (isRelExprOneOf<R_GOTONLY_PC, R_GOTONLY_PC_FROM_END, R_GOTREL,
1026 R_GOTREL_FROM_END, R_PPC_TOC>(Expr))
1027 In.Got->HasGotOffRel = true;
1030 int64_t Addend = computeAddend<ELFT>(Rel, End, Sec, Expr, Sym.isLocal());
1032 // Process some TLS relocations, including relaxing TLS relocations.
1033 // Note that this function does not handle all TLS relocations.
1034 if (unsigned Processed =
1035 handleTlsRelocation<ELFT>(Type, Sym, Sec, Offset, Addend, Expr)) {
1036 I += (Processed - 1);
1040 // We were asked not to generate PLT entries for ifuncs. Instead, pass the
1041 // direct relocation on through.
1042 if (Sym.isGnuIFunc() && Config->ZIfuncNoplt) {
1043 Sym.ExportDynamic = true;
1044 In.RelaDyn->addReloc(Type, &Sec, Offset, &Sym, Addend, R_ADDEND, Type);
1048 // Non-preemptible ifuncs require special handling. First, handle the usual
1049 // case where the symbol isn't one of these.
1050 if (!Sym.isGnuIFunc() || Sym.IsPreemptible) {
1051 // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol.
1052 if (needsPlt(Expr) && !Sym.isInPlt())
1053 addPltEntry<ELFT>(In.Plt, In.GotPlt, In.RelaPlt, Target->PltRel, Sym);
1055 // Create a GOT slot if a relocation needs GOT.
1056 if (needsGot(Expr)) {
1057 if (Config->EMachine == EM_MIPS) {
1058 // MIPS ABI has special rules to process GOT entries and doesn't
1059 // require relocation entries for them. A special case is TLS
1060 // relocations. In that case dynamic loader applies dynamic
1061 // relocations to initialize TLS GOT entries.
1062 // See "Global Offset Table" in Chapter 5 in the following document
1063 // for detailed description:
1064 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1065 In.MipsGot->addEntry(*Sec.File, Sym, Addend, Expr);
1066 } else if (!Sym.isInGot()) {
1067 addGotEntry<ELFT>(Sym);
1071 // Handle a reference to a non-preemptible ifunc. These are special in a
1074 // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have
1075 // a fixed value. But assuming that all references to the ifunc are
1076 // GOT-generating or PLT-generating, the handling of an ifunc is
1077 // relatively straightforward. We create a PLT entry in Iplt, which is
1078 // usually at the end of .plt, which makes an indirect call using a
1079 // matching GOT entry in IgotPlt, which is usually at the end of .got.plt.
1080 // The GOT entry is relocated using an IRELATIVE relocation in RelaIplt,
1081 // which is usually at the end of .rela.plt. Unlike most relocations in
1082 // .rela.plt, which may be evaluated lazily without -z now, dynamic
1083 // loaders evaluate IRELATIVE relocs eagerly, which means that for
1084 // IRELATIVE relocs only, GOT-generating relocations can point directly to
1085 // .got.plt without requiring a separate GOT entry.
1087 // - Despite the fact that an ifunc does not have a fixed value, compilers
1088 // that are not passed -fPIC will assume that they do, and will emit
1089 // direct (non-GOT-generating, non-PLT-generating) relocations to the
1090 // symbol. This means that if a direct relocation to the symbol is
1091 // seen, the linker must set a value for the symbol, and this value must
1092 // be consistent no matter what type of reference is made to the symbol.
1093 // This can be done by creating a PLT entry for the symbol in the way
1094 // described above and making it canonical, that is, making all references
1095 // point to the PLT entry instead of the resolver. In lld we also store
1096 // the address of the PLT entry in the dynamic symbol table, which means
1097 // that the symbol will also have the same value in other modules.
1098 // Because the value loaded from the GOT needs to be consistent with
1099 // the value computed using a direct relocation, a non-preemptible ifunc
1100 // may end up with two GOT entries, one in .got.plt that points to the
1101 // address returned by the resolver and is used only by the PLT entry,
1102 // and another in .got that points to the PLT entry and is used by
1103 // GOT-generating relocations.
1105 // - The fact that these symbols do not have a fixed value makes them an
1106 // exception to the general rule that a statically linked executable does
1107 // not require any form of dynamic relocation. To handle these relocations
1108 // correctly, the IRELATIVE relocations are stored in an array which a
1109 // statically linked executable's startup code must enumerate using the
1110 // linker-defined symbols __rela?_iplt_{start,end}.
1112 // - An absolute relocation to a non-preemptible ifunc (such as a global
1113 // variable containing a pointer to the ifunc) needs to be relocated in
1114 // the exact same way as a GOT entry, so we can avoid needing to make the
1115 // PLT entry canonical by translating such relocations into IRELATIVE
1116 // relocations in the RelaIplt.
1117 if (!Sym.isInPlt()) {
1118 // Create PLT and GOTPLT slots for the symbol.
1119 Sym.IsInIplt = true;
1121 // Create a copy of the symbol to use as the target of the IRELATIVE
1122 // relocation in the IgotPlt. This is in case we make the PLT canonical
1123 // later, which would overwrite the original symbol.
1125 // FIXME: Creating a copy of the symbol here is a bit of a hack. All
1126 // that's really needed to create the IRELATIVE is the section and value,
1127 // so ideally we should just need to copy those.
1128 auto *DirectSym = make<Defined>(cast<Defined>(Sym));
1129 addPltEntry<ELFT>(In.Iplt, In.IgotPlt, In.RelaIplt, Target->IRelativeRel,
1131 Sym.PltIndex = DirectSym->PltIndex;
1133 if (Expr == R_ABS && Addend == 0 && (Sec.Flags & SHF_WRITE)) {
1134 // We might be able to represent this as an IRELATIVE. But we don't know
1135 // yet whether some later relocation will make the symbol point to a
1136 // canonical PLT, which would make this either a dynamic RELATIVE (PIC) or
1137 // static (non-PIC) relocation. So we keep a record of the information
1138 // required to process the relocation, and after scanRelocs() has been
1139 // called on all relocations, the relocation is resolved by
1140 // addIRelativeRelocs().
1141 IRelativeRelocs.push_back({Type, &Sec, Offset, &Sym});
1144 if (needsGot(Expr)) {
1145 // Redirect GOT accesses to point to the Igot.
1147 // This field is also used to keep track of whether we ever needed a GOT
1148 // entry. If we did and we make the PLT canonical later, we'll need to
1149 // create a GOT entry pointing to the PLT entry for Sym.
1150 Sym.GotInIgot = true;
1151 } else if (!needsPlt(Expr)) {
1152 // Make the ifunc's PLT entry canonical by changing the value of its
1153 // symbol to redirect all references to point to it.
1154 unsigned EntryOffset = Sym.PltIndex * Target->PltEntrySize;
1155 if (Config->ZRetpolineplt)
1156 EntryOffset += Target->PltHeaderSize;
1158 auto &D = cast<Defined>(Sym);
1159 D.Section = In.Iplt;
1160 D.Value = EntryOffset;
1162 // It's important to set the symbol type here so that dynamic loaders
1163 // don't try to call the PLT as if it were an ifunc resolver.
1166 if (Sym.GotInIgot) {
1167 // We previously encountered a GOT generating reference that we
1168 // redirected to the Igot. Now that the PLT entry is canonical we must
1169 // clear the redirection to the Igot and add a GOT entry. As we've
1170 // changed the symbol type to STT_FUNC future GOT generating references
1171 // will naturally use this GOT entry.
1173 // We don't need to worry about creating a MIPS GOT here because ifuncs
1174 // aren't a thing on MIPS.
1175 Sym.GotInIgot = false;
1176 addGotEntry<ELFT>(Sym);
1181 processRelocAux<ELFT>(Sec, Expr, Type, Offset, Sym, Rel, Addend);
1184 template <class ELFT, class RelTy>
1185 static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
1186 OffsetGetter GetOffset(Sec);
1188 // Not all relocations end up in Sec.Relocations, but a lot do.
1189 Sec.Relocations.reserve(Rels.size());
1191 for (auto I = Rels.begin(), End = Rels.end(); I != End;)
1192 scanReloc<ELFT>(Sec, GetOffset, I, End);
1194 // Sort relocations by offset to binary search for R_RISCV_PCREL_HI20
1195 if (Config->EMachine == EM_RISCV)
1196 std::stable_sort(Sec.Relocations.begin(), Sec.Relocations.end(),
1197 RelocationOffsetComparator{});
1200 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
1201 if (S.AreRelocsRela)
1202 scanRelocs<ELFT>(S, S.relas<ELFT>());
1204 scanRelocs<ELFT>(S, S.rels<ELFT>());
1207 // Figure out which representation to use for any absolute relocs to
1208 // non-preemptible ifuncs that we visited during scanRelocs().
1209 void elf::addIRelativeRelocs() {
1210 for (IRelativeReloc &R : IRelativeRelocs) {
1211 if (R.Sym->Type == STT_GNU_IFUNC)
1212 In.RelaIplt->addReloc(
1213 {Target->IRelativeRel, R.Sec, R.Offset, true, R.Sym, 0});
1214 else if (Config->Pic)
1215 addRelativeReloc(R.Sec, R.Offset, R.Sym, 0, R_ABS, R.Type);
1217 R.Sec->Relocations.push_back({R_ABS, R.Type, R.Offset, 0, R.Sym});
1219 IRelativeRelocs.clear();
1222 static bool mergeCmp(const InputSection *A, const InputSection *B) {
1223 // std::merge requires a strict weak ordering.
1224 if (A->OutSecOff < B->OutSecOff)
1227 if (A->OutSecOff == B->OutSecOff) {
1228 auto *TA = dyn_cast<ThunkSection>(A);
1229 auto *TB = dyn_cast<ThunkSection>(B);
1231 // Check if Thunk is immediately before any specific Target
1232 // InputSection for example Mips LA25 Thunks.
1233 if (TA && TA->getTargetInputSection() == B)
1236 // Place Thunk Sections without specific targets before
1237 // non-Thunk Sections.
1238 if (TA && !TB && !TA->getTargetInputSection())
1245 // Call Fn on every executable InputSection accessed via the linker script
1246 // InputSectionDescription::Sections.
1247 static void forEachInputSectionDescription(
1248 ArrayRef<OutputSection *> OutputSections,
1249 llvm::function_ref<void(OutputSection *, InputSectionDescription *)> Fn) {
1250 for (OutputSection *OS : OutputSections) {
1251 if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
1253 for (BaseCommand *BC : OS->SectionCommands)
1254 if (auto *ISD = dyn_cast<InputSectionDescription>(BC))
1259 // Thunk Implementation
1261 // Thunks (sometimes called stubs, veneers or branch islands) are small pieces
1262 // of code that the linker inserts inbetween a caller and a callee. The thunks
1263 // are added at link time rather than compile time as the decision on whether
1264 // a thunk is needed, such as the caller and callee being out of range, can only
1265 // be made at link time.
1267 // It is straightforward to tell given the current state of the program when a
1268 // thunk is needed for a particular call. The more difficult part is that
1269 // the thunk needs to be placed in the program such that the caller can reach
1270 // the thunk and the thunk can reach the callee; furthermore, adding thunks to
1271 // the program alters addresses, which can mean more thunks etc.
1273 // In lld we have a synthetic ThunkSection that can hold many Thunks.
1274 // The decision to have a ThunkSection act as a container means that we can
1275 // more easily handle the most common case of a single block of contiguous
1276 // Thunks by inserting just a single ThunkSection.
1278 // The implementation of Thunks in lld is split across these areas
1279 // Relocations.cpp : Framework for creating and placing thunks
1280 // Thunks.cpp : The code generated for each supported thunk
1281 // Target.cpp : Target specific hooks that the framework uses to decide when
1283 // Synthetic.cpp : Implementation of ThunkSection
1284 // Writer.cpp : Iteratively call framework until no more Thunks added
1286 // Thunk placement requirements:
1287 // Mips LA25 thunks. These must be placed immediately before the callee section
1288 // We can assume that the caller is in range of the Thunk. These are modelled
1289 // by Thunks that return the section they must precede with
1290 // getTargetInputSection().
1292 // ARM interworking and range extension thunks. These thunks must be placed
1293 // within range of the caller. All implemented ARM thunks can always reach the
1294 // callee as they use an indirect jump via a register that has no range
1297 // Thunk placement algorithm:
1298 // For Mips LA25 ThunkSections; the placement is explicit, it has to be before
1299 // getTargetInputSection().
1301 // For thunks that must be placed within range of the caller there are many
1302 // possible choices given that the maximum range from the caller is usually
1303 // much larger than the average InputSection size. Desirable properties include:
1304 // - Maximize reuse of thunks by multiple callers
1305 // - Minimize number of ThunkSections to simplify insertion
1306 // - Handle impact of already added Thunks on addresses
1307 // - Simple to understand and implement
1309 // In lld for the first pass, we pre-create one or more ThunkSections per
1310 // InputSectionDescription at Target specific intervals. A ThunkSection is
1311 // placed so that the estimated end of the ThunkSection is within range of the
1312 // start of the InputSectionDescription or the previous ThunkSection. For
1314 // InputSectionDescription
1324 // The intention is that we can add a Thunk to a ThunkSection that is well
1325 // spaced enough to service a number of callers without having to do a lot
1326 // of work. An important principle is that it is not an error if a Thunk cannot
1327 // be placed in a pre-created ThunkSection; when this happens we create a new
1328 // ThunkSection placed next to the caller. This allows us to handle the vast
1329 // majority of thunks simply, but also handle rare cases where the branch range
1330 // is smaller than the target specific spacing.
1332 // The algorithm is expected to create all the thunks that are needed in a
1333 // single pass, with a small number of programs needing a second pass due to
1334 // the insertion of thunks in the first pass increasing the offset between
1335 // callers and callees that were only just in range.
1337 // A consequence of allowing new ThunkSections to be created outside of the
1338 // pre-created ThunkSections is that in rare cases calls to Thunks that were in
1339 // range in pass K, are out of range in some pass > K due to the insertion of
1340 // more Thunks in between the caller and callee. When this happens we retarget
1341 // the relocation back to the original target and create another Thunk.
1343 // Remove ThunkSections that are empty, this should only be the initial set
1344 // precreated on pass 0.
1346 // Insert the Thunks for OutputSection OS into their designated place
1347 // in the Sections vector, and recalculate the InputSection output section
1349 // This may invalidate any output section offsets stored outside of InputSection
1350 void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
1351 forEachInputSectionDescription(
1352 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1353 if (ISD->ThunkSections.empty())
1356 // Remove any zero sized precreated Thunks.
1357 llvm::erase_if(ISD->ThunkSections,
1358 [](const std::pair<ThunkSection *, uint32_t> &TS) {
1359 return TS.first->getSize() == 0;
1362 // ISD->ThunkSections contains all created ThunkSections, including
1363 // those inserted in previous passes. Extract the Thunks created this
1364 // pass and order them in ascending OutSecOff.
1365 std::vector<ThunkSection *> NewThunks;
1366 for (const std::pair<ThunkSection *, uint32_t> TS : ISD->ThunkSections)
1367 if (TS.second == Pass)
1368 NewThunks.push_back(TS.first);
1369 std::stable_sort(NewThunks.begin(), NewThunks.end(),
1370 [](const ThunkSection *A, const ThunkSection *B) {
1371 return A->OutSecOff < B->OutSecOff;
1374 // Merge sorted vectors of Thunks and InputSections by OutSecOff
1375 std::vector<InputSection *> Tmp;
1376 Tmp.reserve(ISD->Sections.size() + NewThunks.size());
1378 std::merge(ISD->Sections.begin(), ISD->Sections.end(),
1379 NewThunks.begin(), NewThunks.end(), std::back_inserter(Tmp),
1382 ISD->Sections = std::move(Tmp);
1386 // Find or create a ThunkSection within the InputSectionDescription (ISD) that
1387 // is in range of Src. An ISD maps to a range of InputSections described by a
1388 // linker script section pattern such as { .text .text.* }.
1389 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *OS, InputSection *IS,
1390 InputSectionDescription *ISD,
1391 uint32_t Type, uint64_t Src) {
1392 for (std::pair<ThunkSection *, uint32_t> TP : ISD->ThunkSections) {
1393 ThunkSection *TS = TP.first;
1394 uint64_t TSBase = OS->Addr + TS->OutSecOff;
1395 uint64_t TSLimit = TSBase + TS->getSize();
1396 if (Target->inBranchRange(Type, Src, (Src > TSLimit) ? TSBase : TSLimit))
1400 // No suitable ThunkSection exists. This can happen when there is a branch
1401 // with lower range than the ThunkSection spacing or when there are too
1402 // many Thunks. Create a new ThunkSection as close to the InputSection as
1403 // possible. Error if InputSection is so large we cannot place ThunkSection
1404 // anywhere in Range.
1405 uint64_t ThunkSecOff = IS->OutSecOff;
1406 if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff)) {
1407 ThunkSecOff = IS->OutSecOff + IS->getSize();
1408 if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff))
1409 fatal("InputSection too large for range extension thunk " +
1410 IS->getObjMsg(Src - (OS->Addr + IS->OutSecOff)));
1412 return addThunkSection(OS, ISD, ThunkSecOff);
1415 // Add a Thunk that needs to be placed in a ThunkSection that immediately
1416 // precedes its Target.
1417 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
1418 ThunkSection *TS = ThunkedSections.lookup(IS);
1422 // Find InputSectionRange within Target Output Section (TOS) that the
1423 // InputSection (IS) that we need to precede is in.
1424 OutputSection *TOS = IS->getParent();
1425 for (BaseCommand *BC : TOS->SectionCommands) {
1426 auto *ISD = dyn_cast<InputSectionDescription>(BC);
1427 if (!ISD || ISD->Sections.empty())
1430 InputSection *First = ISD->Sections.front();
1431 InputSection *Last = ISD->Sections.back();
1433 if (IS->OutSecOff < First->OutSecOff || Last->OutSecOff < IS->OutSecOff)
1436 TS = addThunkSection(TOS, ISD, IS->OutSecOff);
1437 ThunkedSections[IS] = TS;
1444 // Create one or more ThunkSections per OS that can be used to place Thunks.
1445 // We attempt to place the ThunkSections using the following desirable
1447 // - Within range of the maximum number of callers
1448 // - Minimise the number of ThunkSections
1450 // We follow a simple but conservative heuristic to place ThunkSections at
1451 // offsets that are multiples of a Target specific branch range.
1452 // For an InputSectionDescription that is smaller than the range, a single
1453 // ThunkSection at the end of the range will do.
1455 // For an InputSectionDescription that is more than twice the size of the range,
1456 // we place the last ThunkSection at range bytes from the end of the
1457 // InputSectionDescription in order to increase the likelihood that the
1458 // distance from a thunk to its target will be sufficiently small to
1459 // allow for the creation of a short thunk.
1460 void ThunkCreator::createInitialThunkSections(
1461 ArrayRef<OutputSection *> OutputSections) {
1462 uint32_t ThunkSectionSpacing = Target->getThunkSectionSpacing();
1464 forEachInputSectionDescription(
1465 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1466 if (ISD->Sections.empty())
1469 uint32_t ISDBegin = ISD->Sections.front()->OutSecOff;
1471 ISD->Sections.back()->OutSecOff + ISD->Sections.back()->getSize();
1472 uint32_t LastThunkLowerBound = -1;
1473 if (ISDEnd - ISDBegin > ThunkSectionSpacing * 2)
1474 LastThunkLowerBound = ISDEnd - ThunkSectionSpacing;
1477 uint32_t PrevISLimit = ISDBegin;
1478 uint32_t ThunkUpperBound = ISDBegin + ThunkSectionSpacing;
1480 for (const InputSection *IS : ISD->Sections) {
1481 ISLimit = IS->OutSecOff + IS->getSize();
1482 if (ISLimit > ThunkUpperBound) {
1483 addThunkSection(OS, ISD, PrevISLimit);
1484 ThunkUpperBound = PrevISLimit + ThunkSectionSpacing;
1486 if (ISLimit > LastThunkLowerBound)
1488 PrevISLimit = ISLimit;
1490 addThunkSection(OS, ISD, ISLimit);
1494 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
1495 InputSectionDescription *ISD,
1497 auto *TS = make<ThunkSection>(OS, Off);
1498 ISD->ThunkSections.push_back({TS, Pass});
1502 std::pair<Thunk *, bool> ThunkCreator::getThunk(Symbol &Sym, RelType Type,
1504 std::vector<Thunk *> *ThunkVec = nullptr;
1506 // We use (section, offset) pair to find the thunk position if possible so
1507 // that we create only one thunk for aliased symbols or ICFed sections.
1508 if (auto *D = dyn_cast<Defined>(&Sym))
1509 if (!D->isInPlt() && D->Section)
1510 ThunkVec = &ThunkedSymbolsBySection[{D->Section->Repl, D->Value}];
1512 ThunkVec = &ThunkedSymbols[&Sym];
1514 // Check existing Thunks for Sym to see if they can be reused
1515 for (Thunk *T : *ThunkVec)
1516 if (T->isCompatibleWith(Type) &&
1517 Target->inBranchRange(Type, Src, T->getThunkTargetSym()->getVA()))
1518 return std::make_pair(T, false);
1520 // No existing compatible Thunk in range, create a new one
1521 Thunk *T = addThunk(Type, Sym);
1522 ThunkVec->push_back(T);
1523 return std::make_pair(T, true);
1526 // Return true if the relocation target is an in range Thunk.
1527 // Return false if the relocation is not to a Thunk. If the relocation target
1528 // was originally to a Thunk, but is no longer in range we revert the
1529 // relocation back to its original non-Thunk target.
1530 bool ThunkCreator::normalizeExistingThunk(Relocation &Rel, uint64_t Src) {
1531 if (Thunk *T = Thunks.lookup(Rel.Sym)) {
1532 if (Target->inBranchRange(Rel.Type, Src, Rel.Sym->getVA()))
1534 Rel.Sym = &T->Destination;
1535 if (Rel.Sym->isInPlt())
1536 Rel.Expr = toPlt(Rel.Expr);
1541 // Process all relocations from the InputSections that have been assigned
1542 // to InputSectionDescriptions and redirect through Thunks if needed. The
1543 // function should be called iteratively until it returns false.
1546 // All InputSections that may need a Thunk are reachable from
1547 // OutputSectionCommands.
1549 // All OutputSections have an address and all InputSections have an offset
1550 // within the OutputSection.
1552 // The offsets between caller (relocation place) and callee
1553 // (relocation target) will not be modified outside of createThunks().
1556 // If return value is true then ThunkSections have been inserted into
1557 // OutputSections. All relocations that needed a Thunk based on the information
1558 // available to createThunks() on entry have been redirected to a Thunk. Note
1559 // that adding Thunks changes offsets between caller and callee so more Thunks
1562 // If return value is false then no more Thunks are needed, and createThunks has
1563 // made no changes. If the target requires range extension thunks, currently
1564 // ARM, then any future change in offset between caller and callee risks a
1565 // relocation out of range error.
1566 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
1567 bool AddressesChanged = false;
1569 if (Pass == 0 && Target->getThunkSectionSpacing())
1570 createInitialThunkSections(OutputSections);
1572 // With Thunk Size much smaller than branch range we expect to
1573 // converge quickly; if we get to 10 something has gone wrong.
1575 fatal("thunk creation not converged");
1577 // Create all the Thunks and insert them into synthetic ThunkSections. The
1578 // ThunkSections are later inserted back into InputSectionDescriptions.
1579 // We separate the creation of ThunkSections from the insertion of the
1580 // ThunkSections as ThunkSections are not always inserted into the same
1581 // InputSectionDescription as the caller.
1582 forEachInputSectionDescription(
1583 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1584 for (InputSection *IS : ISD->Sections)
1585 for (Relocation &Rel : IS->Relocations) {
1586 uint64_t Src = IS->getVA(Rel.Offset);
1588 // If we are a relocation to an existing Thunk, check if it is
1589 // still in range. If not then Rel will be altered to point to its
1590 // original target so another Thunk can be generated.
1591 if (Pass > 0 && normalizeExistingThunk(Rel, Src))
1594 if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Src,
1600 std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src);
1603 // Find or create a ThunkSection for the new Thunk
1605 if (auto *TIS = T->getTargetInputSection())
1606 TS = getISThunkSec(TIS);
1608 TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src);
1610 Thunks[T->getThunkTargetSym()] = T;
1613 // Redirect relocation to Thunk, we never go via the PLT to a Thunk
1614 Rel.Sym = T->getThunkTargetSym();
1615 Rel.Expr = fromPlt(Rel.Expr);
1618 for (auto &P : ISD->ThunkSections)
1619 AddressesChanged |= P.first->assignOffsets();
1622 for (auto &P : ThunkedSections)
1623 AddressesChanged |= P.second->assignOffsets();
1625 // Merge all created synthetic ThunkSections back into OutputSection
1626 mergeThunks(OutputSections);
1628 return AddressesChanged;
1631 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
1632 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
1633 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
1634 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);