Bug Summary

File:tools/lld/ELF/Relocations.cpp
Warning:line 1269, column 9
3rd function call argument is an uninitialized value

Annotated Source Code

1//===- Relocations.cpp ----------------------------------------------------===//
2//
3// The LLVM Linker
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains platform-independent functions to process relocations.
11// I'll describe the overview of this file here.
12//
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.
17//
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.
23//
24// ELF defines a large number of complex relocations.
25//
26// The functions in this file analyze relocations and do whatever needs
27// to be done. It includes, but not limited to, the following.
28//
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
36//
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.
41//
42//===----------------------------------------------------------------------===//
43
44#include "Relocations.h"
45#include "Config.h"
46#include "LinkerScript.h"
47#include "Memory.h"
48#include "OutputSections.h"
49#include "Strings.h"
50#include "SymbolTable.h"
51#include "SyntheticSections.h"
52#include "Target.h"
53#include "Thunks.h"
54
55#include "llvm/Support/Endian.h"
56#include "llvm/Support/raw_ostream.h"
57#include <algorithm>
58
59using namespace llvm;
60using namespace llvm::ELF;
61using namespace llvm::object;
62using namespace llvm::support::endian;
63
64using namespace lld;
65using namespace lld::elf;
66
67// Construct a message in the following format.
68//
69// >>> defined in /home/alice/src/foo.o
70// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
71// >>> /home/alice/src/bar.o:(.text+0x1)
72template <class ELFT>
73static std::string getLocation(InputSectionBase &S, const Symbol &Sym,
74 uint64_t Off) {
75 std::string Msg =
76 "\n>>> defined in " + toString(Sym.getFile()) + "\n>>> referenced by ";
77 std::string Src = S.getSrcMsg<ELFT>(Sym, Off);
78 if (!Src.empty())
79 Msg += Src + "\n>>> ";
80 return Msg + S.getObjMsg(Off);
81}
82
83// This is a MIPS-specific rule.
84//
85// In case of MIPS GP-relative relocations always resolve to a definition
86// in a regular input file, ignoring the one-definition rule. So we,
87// for example, should not attempt to create a dynamic relocation even
88// if the target symbol is preemptible. There are two two MIPS GP-relative
89// relocations R_MIPS_GPREL16 and R_MIPS_GPREL32. But only R_MIPS_GPREL16
90// can be against a preemptible symbol.
91//
92// To get MIPS relocation type we apply 0xff mask. In case of O32 ABI all
93// relocation types occupy eight bit. In case of N64 ABI we extract first
94// relocation from 3-in-1 packet because only the first relocation can
95// be against a real symbol.
96static bool isMipsGprel(RelType Type) {
97 if (Config->EMachine != EM_MIPS)
98 return false;
99 Type &= 0xff;
100 return Type == R_MIPS_GPREL16 || Type == R_MICROMIPS_GPREL16 ||
101 Type == R_MICROMIPS_GPREL7_S2;
102}
103
104// This function is similar to the `handleTlsRelocation`. MIPS does not
105// support any relaxations for TLS relocations so by factoring out MIPS
106// handling in to the separate function we can simplify the code and do not
107// pollute other `handleTlsRelocation` by MIPS `ifs` statements.
108// Mips has a custom MipsGotSection that handles the writing of GOT entries
109// without dynamic relocations.
110template <class ELFT>
111static unsigned handleMipsTlsRelocation(RelType Type, Symbol &Sym,
112 InputSectionBase &C, uint64_t Offset,
113 int64_t Addend, RelExpr Expr) {
114 if (Expr == R_MIPS_TLSLD) {
115 if (InX::MipsGot->addTlsIndex() && Config->Pic)
116 In<ELFT>::RelaDyn->addReloc({Target->TlsModuleIndexRel, InX::MipsGot,
117 InX::MipsGot->getTlsIndexOff(), false,
118 nullptr, 0});
119 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
120 return 1;
121 }
122
123 if (Expr == R_MIPS_TLSGD) {
124 if (InX::MipsGot->addDynTlsEntry(Sym) && Sym.IsPreemptible) {
125 uint64_t Off = InX::MipsGot->getGlobalDynOffset(Sym);
126 In<ELFT>::RelaDyn->addReloc(
127 {Target->TlsModuleIndexRel, InX::MipsGot, Off, false, &Sym, 0});
128 if (Sym.IsPreemptible)
129 In<ELFT>::RelaDyn->addReloc({Target->TlsOffsetRel, InX::MipsGot,
130 Off + Config->Wordsize, false, &Sym, 0});
131 }
132 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
133 return 1;
134 }
135 return 0;
136}
137
138// This function is similar to the `handleMipsTlsRelocation`. ARM also does not
139// support any relaxations for TLS relocations. ARM is logically similar to Mips
140// in how it handles TLS, but Mips uses its own custom GOT which handles some
141// of the cases that ARM uses GOT relocations for.
142//
143// We look for TLS global dynamic and local dynamic relocations, these may
144// require the generation of a pair of GOT entries that have associated
145// dynamic relocations. When the results of the dynamic relocations can be
146// resolved at static link time we do so. This is necessary for static linking
147// as there will be no dynamic loader to resolve them at load-time.
148//
149// The pair of GOT entries created are of the form
150// GOT[e0] Module Index (Used to find pointer to TLS block at run-time)
151// GOT[e1] Offset of symbol in TLS block
152template <class ELFT>
153static unsigned handleARMTlsRelocation(RelType Type, Symbol &Sym,
154 InputSectionBase &C, uint64_t Offset,
155 int64_t Addend, RelExpr Expr) {
156 // The Dynamic TLS Module Index Relocation for a symbol defined in an
157 // executable is always 1. If the target Symbol is not preemptible then
158 // we know the offset into the TLS block at static link time.
159 bool NeedDynId = Sym.IsPreemptible || Config->Shared;
160 bool NeedDynOff = Sym.IsPreemptible;
161
162 auto AddTlsReloc = [&](uint64_t Off, RelType Type, Symbol *Dest, bool Dyn) {
163 if (Dyn)
164 In<ELFT>::RelaDyn->addReloc({Type, InX::Got, Off, false, Dest, 0});
165 else
166 InX::Got->Relocations.push_back({R_ABS, Type, Off, 0, Dest});
167 };
168
169 // Local Dynamic is for access to module local TLS variables, while still
170 // being suitable for being dynamically loaded via dlopen.
171 // GOT[e0] is the module index, with a special value of 0 for the current
172 // module. GOT[e1] is unused. There only needs to be one module index entry.
173 if (Expr == R_TLSLD_PC && InX::Got->addTlsIndex()) {
174 AddTlsReloc(InX::Got->getTlsIndexOff(), Target->TlsModuleIndexRel,
175 NeedDynId ? nullptr : &Sym, NeedDynId);
176 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
177 return 1;
178 }
179
180 // Global Dynamic is the most general purpose access model. When we know
181 // the module index and offset of symbol in TLS block we can fill these in
182 // using static GOT relocations.
183 if (Expr == R_TLSGD_PC) {
184 if (InX::Got->addDynTlsEntry(Sym)) {
185 uint64_t Off = InX::Got->getGlobalDynOffset(Sym);
186 AddTlsReloc(Off, Target->TlsModuleIndexRel, &Sym, NeedDynId);
187 AddTlsReloc(Off + Config->Wordsize, Target->TlsOffsetRel, &Sym,
188 NeedDynOff);
189 }
190 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
191 return 1;
192 }
193 return 0;
194}
195
196// Returns the number of relocations processed.
197template <class ELFT>
198static unsigned
199handleTlsRelocation(RelType Type, Symbol &Sym, InputSectionBase &C,
200 typename ELFT::uint Offset, int64_t Addend, RelExpr Expr) {
201 if (!(C.Flags & SHF_ALLOC))
202 return 0;
203
204 if (!Sym.isTls())
205 return 0;
206
207 if (Config->EMachine == EM_ARM)
208 return handleARMTlsRelocation<ELFT>(Type, Sym, C, Offset, Addend, Expr);
209 if (Config->EMachine == EM_MIPS)
210 return handleMipsTlsRelocation<ELFT>(Type, Sym, C, Offset, Addend, Expr);
211
212 if (isRelExprOneOf<R_TLSDESC, R_TLSDESC_PAGE, R_TLSDESC_CALL>(Expr) &&
213 Config->Shared) {
214 if (InX::Got->addDynTlsEntry(Sym)) {
215 uint64_t Off = InX::Got->getGlobalDynOffset(Sym);
216 In<ELFT>::RelaDyn->addReloc(
217 {Target->TlsDescRel, InX::Got, Off, !Sym.IsPreemptible, &Sym, 0});
218 }
219 if (Expr != R_TLSDESC_CALL)
220 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
221 return 1;
222 }
223
224 if (isRelExprOneOf<R_TLSLD_PC, R_TLSLD>(Expr)) {
225 // Local-Dynamic relocs can be relaxed to Local-Exec.
226 if (!Config->Shared) {
227 C.Relocations.push_back(
228 {R_RELAX_TLS_LD_TO_LE, Type, Offset, Addend, &Sym});
229 return 2;
230 }
231 if (InX::Got->addTlsIndex())
232 In<ELFT>::RelaDyn->addReloc({Target->TlsModuleIndexRel, InX::Got,
233 InX::Got->getTlsIndexOff(), false, nullptr,
234 0});
235 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
236 return 1;
237 }
238
239 // Local-Dynamic relocs can be relaxed to Local-Exec.
240 if (isRelExprOneOf<R_ABS, R_TLSLD, R_TLSLD_PC>(Expr) && !Config->Shared) {
241 C.Relocations.push_back({R_RELAX_TLS_LD_TO_LE, Type, Offset, Addend, &Sym});
242 return 1;
243 }
244
245 if (isRelExprOneOf<R_TLSDESC, R_TLSDESC_PAGE, R_TLSDESC_CALL, R_TLSGD,
246 R_TLSGD_PC>(Expr)) {
247 if (Config->Shared) {
248 if (InX::Got->addDynTlsEntry(Sym)) {
249 uint64_t Off = InX::Got->getGlobalDynOffset(Sym);
250 In<ELFT>::RelaDyn->addReloc(
251 {Target->TlsModuleIndexRel, InX::Got, Off, false, &Sym, 0});
252
253 // If the symbol is preemptible we need the dynamic linker to write
254 // the offset too.
255 uint64_t OffsetOff = Off + Config->Wordsize;
256 if (Sym.IsPreemptible)
257 In<ELFT>::RelaDyn->addReloc(
258 {Target->TlsOffsetRel, InX::Got, OffsetOff, false, &Sym, 0});
259 else
260 InX::Got->Relocations.push_back(
261 {R_ABS, Target->TlsOffsetRel, OffsetOff, 0, &Sym});
262 }
263 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
264 return 1;
265 }
266
267 // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec
268 // depending on the symbol being locally defined or not.
269 if (Sym.IsPreemptible) {
270 C.Relocations.push_back(
271 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_IE), Type,
272 Offset, Addend, &Sym});
273 if (!Sym.isInGot()) {
274 InX::Got->addEntry(Sym);
275 In<ELFT>::RelaDyn->addReloc(
276 {Target->TlsGotRel, InX::Got, Sym.getGotOffset(), false, &Sym, 0});
277 }
278 } else {
279 C.Relocations.push_back(
280 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_LE), Type,
281 Offset, Addend, &Sym});
282 }
283 return Target->TlsGdRelaxSkip;
284 }
285
286 // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally
287 // defined.
288 if (isRelExprOneOf<R_GOT, R_GOT_FROM_END, R_GOT_PC, R_GOT_PAGE_PC>(Expr) &&
289 !Config->Shared && !Sym.IsPreemptible) {
290 C.Relocations.push_back({R_RELAX_TLS_IE_TO_LE, Type, Offset, Addend, &Sym});
291 return 1;
292 }
293
294 if (Expr == R_TLSDESC_CALL)
295 return 1;
296 return 0;
297}
298
299static RelType getMipsPairType(RelType Type, bool IsLocal) {
300 switch (Type) {
301 case R_MIPS_HI16:
302 return R_MIPS_LO16;
303 case R_MIPS_GOT16:
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;
315 case R_MIPS_PCHI16:
316 return R_MIPS_PCLO16;
317 case R_MICROMIPS_HI16:
318 return R_MICROMIPS_LO16;
319 default:
320 return R_MIPS_NONE;
321 }
322}
323
324// True if non-preemptable symbol always has the same value regardless of where
325// the DSO is loaded.
326static bool isAbsolute(const Symbol &Sym) {
327 if (Sym.isUndefWeak())
328 return true;
329 if (const auto *DR = dyn_cast<Defined>(&Sym))
330 return DR->Section == nullptr; // Absolute symbol.
331 return false;
332}
333
334static bool isAbsoluteValue(const Symbol &Sym) {
335 return isAbsolute(Sym) || Sym.isTls();
336}
337
338// Returns true if Expr refers a PLT entry.
339static bool needsPlt(RelExpr Expr) {
340 return isRelExprOneOf<R_PLT_PC, R_PPC_PLT_OPD, R_PLT, R_PLT_PAGE_PC>(Expr);
341}
342
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.
346static bool needsGot(RelExpr Expr) {
347 return isRelExprOneOf<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF,
348 R_MIPS_GOT_OFF32, R_GOT_PAGE_PC, R_GOT_PC,
349 R_GOT_FROM_END>(Expr);
350}
351
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).
354static bool isRelExpr(RelExpr Expr) {
355 return isRelExprOneOf<R_PC, R_GOTREL, R_GOTREL_FROM_END, R_MIPS_GOTREL,
356 R_PAGE_PC, R_RELAX_GOT_PC>(Expr);
357}
358
359// Returns true if a given relocation can be computed at link-time.
360//
361// For instance, we know the offset from a relocation to its target at
362// link-time if the relocation is PC-relative and refers a
363// non-interposable function in the same executable. This function
364// will return true for such relocation.
365//
366// If this function returns false, that means we need to emit a
367// dynamic relocation so that the relocation will be fixed at load-time.
368template <class ELFT>
369static 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_SIZE, R_GOT_FROM_END, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE,
373 R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC,
374 R_MIPS_TLSGD, R_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC,
375 R_GOTONLY_PC_FROM_END, R_PLT_PC, R_TLSGD_PC, R_TLSGD,
376 R_PPC_PLT_OPD, R_TLSDESC_CALL, R_TLSDESC_PAGE, R_HINT>(E))
377 return true;
378
379 // These never do, except if the entire file is position dependent or if
380 // only the low bits are used.
381 if (E == R_GOT || E == R_PLT || E == R_TLSDESC)
382 return Target->usesOnlyLowPageBits(Type) || !Config->Pic;
383
384 if (Sym.IsPreemptible)
385 return false;
386 if (!Config->Pic)
387 return true;
388
389 // For the target and the relocation, we want to know if they are
390 // absolute or relative.
391 bool AbsVal = isAbsoluteValue(Sym);
392 bool RelE = isRelExpr(E);
393 if (AbsVal && !RelE)
394 return true;
395 if (!AbsVal && RelE)
396 return true;
397 if (!AbsVal && !RelE)
398 return Target->usesOnlyLowPageBits(Type);
399
400 // Relative relocation to an absolute value. This is normally unrepresentable,
401 // but if the relocation refers to a weak undefined symbol, we allow it to
402 // resolve to the image base. This is a little strange, but it allows us to
403 // link function calls to such symbols. Normally such a call will be guarded
404 // with a comparison, which will load a zero from the GOT.
405 // Another special case is MIPS _gp_disp symbol which represents offset
406 // between start of a function and '_gp' value and defined as absolute just
407 // to simplify the code.
408 assert(AbsVal && RelE)(static_cast <bool> (AbsVal && RelE) ? void (0)
: __assert_fail ("AbsVal && RelE", "/build/llvm-toolchain-snapshot-6.0~svn318693/tools/lld/ELF/Relocations.cpp"
, 408, __extension__ __PRETTY_FUNCTION__))
;
409 if (Sym.isUndefWeak())
410 return true;
411
412 error("relocation " + toString(Type) + " cannot refer to absolute symbol: " +
413 toString(Sym) + getLocation<ELFT>(S, Sym, RelOff));
414 return true;
415}
416
417static RelExpr toPlt(RelExpr Expr) {
418 if (Expr == R_PPC_OPD)
419 return R_PPC_PLT_OPD;
420 if (Expr == R_PC)
421 return R_PLT_PC;
422 if (Expr == R_PAGE_PC)
423 return R_PLT_PAGE_PC;
424 if (Expr == R_ABS)
425 return R_PLT;
426 return Expr;
427}
428
429static RelExpr fromPlt(RelExpr Expr) {
430 // We decided not to use a plt. Optimize a reference to the plt to a
431 // reference to the symbol itself.
432 if (Expr == R_PLT_PC)
433 return R_PC;
434 if (Expr == R_PPC_PLT_OPD)
435 return R_PPC_OPD;
436 if (Expr == R_PLT)
437 return R_ABS;
438 return Expr;
439}
440
441// Returns true if a given shared symbol is in a read-only segment in a DSO.
442template <class ELFT> static bool isReadOnly(SharedSymbol *SS) {
443 typedef typename ELFT::Phdr Elf_Phdr;
444
445 // Determine if the symbol is read-only by scanning the DSO's program headers.
446 const SharedFile<ELFT> *File = SS->getFile<ELFT>();
447 for (const Elf_Phdr &Phdr : check(File->getObj().program_headers()))
448 if ((Phdr.p_type == ELF::PT_LOAD || Phdr.p_type == ELF::PT_GNU_RELRO) &&
449 !(Phdr.p_flags & ELF::PF_W) && SS->Value >= Phdr.p_vaddr &&
450 SS->Value < Phdr.p_vaddr + Phdr.p_memsz)
451 return true;
452 return false;
453}
454
455// Returns symbols at the same offset as a given symbol, including SS itself.
456//
457// If two or more symbols are at the same offset, and at least one of
458// them are copied by a copy relocation, all of them need to be copied.
459// Otherwise, they would refer different places at runtime.
460template <class ELFT>
461static std::vector<SharedSymbol *> getSymbolsAt(SharedSymbol *SS) {
462 typedef typename ELFT::Sym Elf_Sym;
463
464 SharedFile<ELFT> *File = SS->getFile<ELFT>();
465
466 std::vector<SharedSymbol *> Ret;
467 for (const Elf_Sym &S : File->getGlobalELFSyms()) {
468 if (S.st_shndx == SHN_UNDEF || S.st_shndx == SHN_ABS ||
469 S.st_value != SS->Value)
470 continue;
471 StringRef Name = check(S.getName(File->getStringTable()));
472 Symbol *Sym = Symtab->find(Name);
473 if (auto *Alias = dyn_cast_or_null<SharedSymbol>(Sym))
474 Ret.push_back(Alias);
475 }
476 return Ret;
477}
478
479// Reserve space in .bss or .bss.rel.ro for copy relocation.
480//
481// The copy relocation is pretty much a hack. If you use a copy relocation
482// in your program, not only the symbol name but the symbol's size, RW/RO
483// bit and alignment become part of the ABI. In addition to that, if the
484// symbol has aliases, the aliases become part of the ABI. That's subtle,
485// but if you violate that implicit ABI, that can cause very counter-
486// intuitive consequences.
487//
488// So, what is the copy relocation? It's for linking non-position
489// independent code to DSOs. In an ideal world, all references to data
490// exported by DSOs should go indirectly through GOT. But if object files
491// are compiled as non-PIC, all data references are direct. There is no
492// way for the linker to transform the code to use GOT, as machine
493// instructions are already set in stone in object files. This is where
494// the copy relocation takes a role.
495//
496// A copy relocation instructs the dynamic linker to copy data from a DSO
497// to a specified address (which is usually in .bss) at load-time. If the
498// static linker (that's us) finds a direct data reference to a DSO
499// symbol, it creates a copy relocation, so that the symbol can be
500// resolved as if it were in .bss rather than in a DSO.
501//
502// As you can see in this function, we create a copy relocation for the
503// dynamic linker, and the relocation contains not only symbol name but
504// various other informtion about the symbol. So, such attributes become a
505// part of the ABI.
506//
507// Note for application developers: I can give you a piece of advice if
508// you are writing a shared library. You probably should export only
509// functions from your library. You shouldn't export variables.
510//
511// As an example what can happen when you export variables without knowing
512// the semantics of copy relocations, assume that you have an exported
513// variable of type T. It is an ABI-breaking change to add new members at
514// end of T even though doing that doesn't change the layout of the
515// existing members. That's because the space for the new members are not
516// reserved in .bss unless you recompile the main program. That means they
517// are likely to overlap with other data that happens to be laid out next
518// to the variable in .bss. This kind of issue is sometimes very hard to
519// debug. What's a solution? Instead of exporting a varaible V from a DSO,
520// define an accessor getV().
521template <class ELFT> static void addCopyRelSymbol(SharedSymbol *SS) {
522 // Copy relocation against zero-sized symbol doesn't make sense.
523 uint64_t SymSize = SS->getSize();
524 if (SymSize == 0)
525 fatal("cannot create a copy relocation for symbol " + toString(*SS));
526
527 // See if this symbol is in a read-only segment. If so, preserve the symbol's
528 // memory protection by reserving space in the .bss.rel.ro section.
529 bool IsReadOnly = isReadOnly<ELFT>(SS);
530 BssSection *Sec = make<BssSection>(IsReadOnly ? ".bss.rel.ro" : ".bss",
531 SymSize, SS->Alignment);
532 if (IsReadOnly)
533 InX::BssRelRo->getParent()->addSection(Sec);
534 else
535 InX::Bss->getParent()->addSection(Sec);
536
537 // Look through the DSO's dynamic symbol table for aliases and create a
538 // dynamic symbol for each one. This causes the copy relocation to correctly
539 // interpose any aliases.
540 for (SharedSymbol *Sym : getSymbolsAt<ELFT>(SS)) {
541 Sym->CopyRelSec = Sec;
542 Sym->IsPreemptible = false;
543 Sym->IsUsedInRegularObj = true;
544 }
545
546 In<ELFT>::RelaDyn->addReloc({Target->CopyRel, Sec, 0, false, SS, 0});
547}
548
549static void errorOrWarn(const Twine &Msg) {
550 if (!Config->NoinhibitExec)
551 error(Msg);
552 else
553 warn(Msg);
554}
555
556template <class ELFT>
557static RelExpr adjustExpr(Symbol &Sym, RelExpr Expr, RelType Type,
558 InputSectionBase &S, uint64_t RelOff) {
559 // We can create any dynamic relocation if a section is simply writable.
560 if (S.Flags & SHF_WRITE)
561 return Expr;
562
563 // Or, if we are allowed to create dynamic relocations against
564 // read-only sections (i.e. unless "-z notext" is given),
565 // we can create a dynamic relocation as we want, too.
566 if (!Config->ZText)
567 return Expr;
568
569 // If a relocation can be applied at link-time, we don't need to
570 // create a dynamic relocation in the first place.
571 if (isStaticLinkTimeConstant<ELFT>(Expr, Type, Sym, S, RelOff))
572 return Expr;
573
574 // If we got here we know that this relocation would require the dynamic
575 // linker to write a value to read only memory.
576
577 // If the relocation is to a weak undef, give up on it and produce a
578 // non preemptible 0.
579 if (Sym.isUndefWeak()) {
580 Sym.IsPreemptible = false;
581 return Expr;
582 }
583
584 // We can hack around it if we are producing an executable and
585 // the refered symbol can be preemepted to refer to the executable.
586 if (Config->Shared || (Config->Pic && !isRelExpr(Expr))) {
587 error(
588 "can't create dynamic relocation " + toString(Type) + " against " +
589 (Sym.getName().empty() ? "local symbol" : "symbol: " + toString(Sym)) +
590 " in readonly segment; recompile object files with -fPIC" +
591 getLocation<ELFT>(S, Sym, RelOff));
592 return Expr;
593 }
594
595 if (Sym.getVisibility() != STV_DEFAULT) {
596 error("cannot preempt symbol: " + toString(Sym) +
597 getLocation<ELFT>(S, Sym, RelOff));
598 return Expr;
599 }
600
601 if (Sym.isObject()) {
602 // Produce a copy relocation.
603 auto *B = cast<SharedSymbol>(&Sym);
604 if (!B->CopyRelSec) {
605 if (Config->ZNocopyreloc)
606 error("unresolvable relocation " + toString(Type) +
607 " against symbol '" + toString(*B) +
608 "'; recompile with -fPIC or remove '-z nocopyreloc'" +
609 getLocation<ELFT>(S, Sym, RelOff));
610
611 addCopyRelSymbol<ELFT>(B);
612 }
613 return Expr;
614 }
615
616 if (Sym.isFunc()) {
617 // This handles a non PIC program call to function in a shared library. In
618 // an ideal world, we could just report an error saying the relocation can
619 // overflow at runtime. In the real world with glibc, crt1.o has a
620 // R_X86_64_PC32 pointing to libc.so.
621 //
622 // The general idea on how to handle such cases is to create a PLT entry and
623 // use that as the function value.
624 //
625 // For the static linking part, we just return a plt expr and everything
626 // else will use the the PLT entry as the address.
627 //
628 // The remaining problem is making sure pointer equality still works. We
629 // need the help of the dynamic linker for that. We let it know that we have
630 // a direct reference to a so symbol by creating an undefined symbol with a
631 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to
632 // the value of the symbol we created. This is true even for got entries, so
633 // pointer equality is maintained. To avoid an infinite loop, the only entry
634 // that points to the real function is a dedicated got entry used by the
635 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT,
636 // R_386_JMP_SLOT, etc).
637 Sym.NeedsPltAddr = true;
638 Sym.IsPreemptible = false;
639 return toPlt(Expr);
640 }
641
642 errorOrWarn("symbol '" + toString(Sym) + "' defined in " +
643 toString(Sym.getFile()) + " has no type");
644 return Expr;
645}
646
647// MIPS has an odd notion of "paired" relocations to calculate addends.
648// For example, if a relocation is of R_MIPS_HI16, there must be a
649// R_MIPS_LO16 relocation after that, and an addend is calculated using
650// the two relocations.
651template <class ELFT, class RelTy>
652static int64_t computeMipsAddend(const RelTy &Rel, const RelTy *End,
653 InputSectionBase &Sec, RelExpr Expr,
654 bool IsLocal) {
655 if (Expr == R_MIPS_GOTREL && IsLocal)
656 return Sec.getFile<ELFT>()->MipsGp0;
657
658 // The ABI says that the paired relocation is used only for REL.
659 // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
660 if (RelTy::IsRela)
661 return 0;
662
663 RelType Type = Rel.getType(Config->IsMips64EL);
664 uint32_t PairTy = getMipsPairType(Type, IsLocal);
665 if (PairTy == R_MIPS_NONE)
666 return 0;
667
668 const uint8_t *Buf = Sec.Data.data();
669 uint32_t SymIndex = Rel.getSymbol(Config->IsMips64EL);
670
671 // To make things worse, paired relocations might not be contiguous in
672 // the relocation table, so we need to do linear search. *sigh*
673 for (const RelTy *RI = &Rel; RI != End; ++RI)
674 if (RI->getType(Config->IsMips64EL) == PairTy &&
675 RI->getSymbol(Config->IsMips64EL) == SymIndex)
676 return Target->getImplicitAddend(Buf + RI->r_offset, PairTy);
677
678 warn("can't find matching " + toString(PairTy) + " relocation for " +
679 toString(Type));
680 return 0;
681}
682
683// Returns an addend of a given relocation. If it is RELA, an addend
684// is in a relocation itself. If it is REL, we need to read it from an
685// input section.
686template <class ELFT, class RelTy>
687static int64_t computeAddend(const RelTy &Rel, const RelTy *End,
688 InputSectionBase &Sec, RelExpr Expr,
689 bool IsLocal) {
690 int64_t Addend;
691 RelType Type = Rel.getType(Config->IsMips64EL);
692
693 if (RelTy::IsRela) {
694 Addend = getAddend<ELFT>(Rel);
695 } else {
696 const uint8_t *Buf = Sec.Data.data();
697 Addend = Target->getImplicitAddend(Buf + Rel.r_offset, Type);
698 }
699
700 if (Config->EMachine == EM_PPC64 && Config->Pic && Type == R_PPC64_TOC)
701 Addend += getPPC64TocBase();
702 if (Config->EMachine == EM_MIPS)
703 Addend += computeMipsAddend<ELFT>(Rel, End, Sec, Expr, IsLocal);
704
705 return Addend;
706}
707
708// Report an undefined symbol if necessary.
709// Returns true if this function printed out an error message.
710template <class ELFT>
711static bool maybeReportUndefined(Symbol &Sym, InputSectionBase &Sec,
712 uint64_t Offset) {
713 if (Config->UnresolvedSymbols == UnresolvedPolicy::IgnoreAll)
714 return false;
715
716 if (Sym.isLocal() || !Sym.isUndefined() || Sym.isWeak())
717 return false;
718
719 bool CanBeExternal =
720 Sym.computeBinding() != STB_LOCAL && Sym.getVisibility() == STV_DEFAULT;
721 if (Config->UnresolvedSymbols == UnresolvedPolicy::Ignore && CanBeExternal)
722 return false;
723
724 std::string Msg =
725 "undefined symbol: " + toString(Sym) + "\n>>> referenced by ";
726
727 std::string Src = Sec.getSrcMsg<ELFT>(Sym, Offset);
728 if (!Src.empty())
729 Msg += Src + "\n>>> ";
730 Msg += Sec.getObjMsg(Offset);
731
732 if ((Config->UnresolvedSymbols == UnresolvedPolicy::Warn && CanBeExternal) ||
733 Config->NoinhibitExec) {
734 warn(Msg);
735 return false;
736 }
737
738 error(Msg);
739 return true;
740}
741
742// MIPS N32 ABI treats series of successive relocations with the same offset
743// as a single relocation. The similar approach used by N64 ABI, but this ABI
744// packs all relocations into the single relocation record. Here we emulate
745// this for the N32 ABI. Iterate over relocation with the same offset and put
746// theirs types into the single bit-set.
747template <class RelTy> static RelType getMipsN32RelType(RelTy *&Rel, RelTy *End) {
748 RelType Type = Rel->getType(Config->IsMips64EL);
749 uint64_t Offset = Rel->r_offset;
750
751 int N = 0;
752 while (Rel + 1 != End && (Rel + 1)->r_offset == Offset)
753 Type |= (++Rel)->getType(Config->IsMips64EL) << (8 * ++N);
754 return Type;
755}
756
757// .eh_frame sections are mergeable input sections, so their input
758// offsets are not linearly mapped to output section. For each input
759// offset, we need to find a section piece containing the offset and
760// add the piece's base address to the input offset to compute the
761// output offset. That isn't cheap.
762//
763// This class is to speed up the offset computation. When we process
764// relocations, we access offsets in the monotonically increasing
765// order. So we can optimize for that access pattern.
766//
767// For sections other than .eh_frame, this class doesn't do anything.
768namespace {
769class OffsetGetter {
770public:
771 explicit OffsetGetter(InputSectionBase &Sec) {
772 if (auto *Eh = dyn_cast<EhInputSection>(&Sec))
773 Pieces = Eh->Pieces;
774 }
775
776 // Translates offsets in input sections to offsets in output sections.
777 // Given offset must increase monotonically. We assume that Piece is
778 // sorted by InputOff.
779 uint64_t get(uint64_t Off) {
780 if (Pieces.empty())
781 return Off;
782
783 while (I != Pieces.size() && Pieces[I].InputOff + Pieces[I].Size <= Off)
784 ++I;
785 if (I == Pieces.size())
786 return Off;
787
788 // Pieces must be contiguous, so there must be no holes in between.
789 assert(Pieces[I].InputOff <= Off && "Relocation not in any piece")(static_cast <bool> (Pieces[I].InputOff <= Off &&
"Relocation not in any piece") ? void (0) : __assert_fail ("Pieces[I].InputOff <= Off && \"Relocation not in any piece\""
, "/build/llvm-toolchain-snapshot-6.0~svn318693/tools/lld/ELF/Relocations.cpp"
, 789, __extension__ __PRETTY_FUNCTION__))
;
790
791 // Offset -1 means that the piece is dead (i.e. garbage collected).
792 if (Pieces[I].OutputOff == -1)
793 return -1;
794 return Pieces[I].OutputOff + Off - Pieces[I].InputOff;
795 }
796
797private:
798 ArrayRef<EhSectionPiece> Pieces;
799 size_t I = 0;
800};
801} // namespace
802
803template <class ELFT, class GotPltSection>
804static void addPltEntry(PltSection *Plt, GotPltSection *GotPlt,
805 RelocationSection<ELFT> *Rel, RelType Type, Symbol &Sym,
806 bool UseSymVA) {
807 Plt->addEntry<ELFT>(Sym);
808 GotPlt->addEntry(Sym);
809 Rel->addReloc({Type, GotPlt, Sym.getGotPltOffset(), UseSymVA, &Sym, 0});
810}
811
812template <class ELFT> static void addGotEntry(Symbol &Sym, bool Preemptible) {
813 InX::Got->addEntry(Sym);
814
815 RelExpr Expr = Sym.isTls() ? R_TLS : R_ABS;
816 uint64_t Off = Sym.getGotOffset();
817
818 // If a GOT slot value can be calculated at link-time, which is now,
819 // we can just fill that out.
820 //
821 // (We don't actually write a value to a GOT slot right now, but we
822 // add a static relocation to a Relocations vector so that
823 // InputSection::relocate will do the work for us. We may be able
824 // to just write a value now, but it is a TODO.)
825 bool IsLinkTimeConstant = !Preemptible && (!Config->Pic || isAbsolute(Sym));
826 if (IsLinkTimeConstant) {
827 InX::Got->Relocations.push_back({Expr, Target->GotRel, Off, 0, &Sym});
828 return;
829 }
830
831 // Otherwise, we emit a dynamic relocation to .rel[a].dyn so that
832 // the GOT slot will be fixed at load-time.
833 RelType Type;
834 if (Sym.isTls())
835 Type = Target->TlsGotRel;
836 else if (!Preemptible && Config->Pic && !isAbsolute(Sym))
837 Type = Target->RelativeRel;
838 else
839 Type = Target->GotRel;
840 In<ELFT>::RelaDyn->addReloc({Type, InX::Got, Off, !Preemptible, &Sym, 0});
841
842 // REL type relocations don't have addend fields unlike RELAs, and
843 // their addends are stored to the section to which they are applied.
844 // So, store addends if we need to.
845 //
846 // This is ugly -- the difference between REL and RELA should be
847 // handled in a better way. It's a TODO.
848 if (!Config->IsRela)
849 InX::Got->Relocations.push_back({R_ABS, Target->GotRel, Off, 0, &Sym});
850}
851
852// The reason we have to do this early scan is as follows
853// * To mmap the output file, we need to know the size
854// * For that, we need to know how many dynamic relocs we will have.
855// It might be possible to avoid this by outputting the file with write:
856// * Write the allocated output sections, computing addresses.
857// * Apply relocations, recording which ones require a dynamic reloc.
858// * Write the dynamic relocations.
859// * Write the rest of the file.
860// This would have some drawbacks. For example, we would only know if .rela.dyn
861// is needed after applying relocations. If it is, it will go after rw and rx
862// sections. Given that it is ro, we will need an extra PT_LOAD. This
863// complicates things for the dynamic linker and means we would have to reserve
864// space for the extra PT_LOAD even if we end up not using it.
865template <class ELFT, class RelTy>
866static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
867 OffsetGetter GetOffset(Sec);
868
869 for (auto I = Rels.begin(), End = Rels.end(); I != End; ++I) {
870 const RelTy &Rel = *I;
871 Symbol &Sym = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
872 RelType Type = Rel.getType(Config->IsMips64EL);
873
874 // Deal with MIPS oddity.
875 if (Config->MipsN32Abi)
876 Type = getMipsN32RelType(I, End);
877
878 // Get an offset in an output section this relocation is applied to.
879 uint64_t Offset = GetOffset.get(Rel.r_offset);
880 if (Offset == uint64_t(-1))
881 continue;
882
883 // Skip if the target symbol is an erroneous undefined symbol.
884 if (maybeReportUndefined<ELFT>(Sym, Sec, Rel.r_offset))
885 continue;
886
887 RelExpr Expr =
888 Target->getRelExpr(Type, Sym, Sec.Data.begin() + Rel.r_offset);
889
890 // Ignore "hint" relocations because they are only markers for relaxation.
891 if (isRelExprOneOf<R_HINT, R_NONE>(Expr))
892 continue;
893
894 // Handle yet another MIPS-ness.
895 if (isMipsGprel(Type)) {
896 int64_t Addend = computeAddend<ELFT>(Rel, End, Sec, Expr, Sym.isLocal());
897 Sec.Relocations.push_back({R_MIPS_GOTREL, Type, Offset, Addend, &Sym});
898 continue;
899 }
900
901 bool Preemptible = Sym.IsPreemptible;
902
903 // Strenghten or relax a PLT access.
904 //
905 // GNU ifunc symbols must be accessed via PLT because their addresses
906 // are determined by runtime.
907 //
908 // On the other hand, if we know that a PLT entry will be resolved within
909 // the same ELF module, we can skip PLT access and directly jump to the
910 // destination function. For example, if we are linking a main exectuable,
911 // all dynamic symbols that can be resolved within the executable will
912 // actually be resolved that way at runtime, because the main exectuable
913 // is always at the beginning of a search list. We can leverage that fact.
914 if (Sym.isGnuIFunc())
915 Expr = toPlt(Expr);
916 else if (!Preemptible && Expr == R_GOT_PC && !isAbsoluteValue(Sym))
917 Expr =
918 Target->adjustRelaxExpr(Type, Sec.Data.data() + Rel.r_offset, Expr);
919 else if (!Preemptible)
920 Expr = fromPlt(Expr);
921
922 Expr = adjustExpr<ELFT>(Sym, Expr, Type, Sec, Rel.r_offset);
923 if (errorCount())
924 continue;
925
926 // This relocation does not require got entry, but it is relative to got and
927 // needs it to be created. Here we request for that.
928 if (isRelExprOneOf<R_GOTONLY_PC, R_GOTONLY_PC_FROM_END, R_GOTREL,
929 R_GOTREL_FROM_END, R_PPC_TOC>(Expr))
930 InX::Got->HasGotOffRel = true;
931
932 // Read an addend.
933 int64_t Addend = computeAddend<ELFT>(Rel, End, Sec, Expr, Sym.isLocal());
934
935 // Process some TLS relocations, including relaxing TLS relocations.
936 // Note that this function does not handle all TLS relocations.
937 if (unsigned Processed =
938 handleTlsRelocation<ELFT>(Type, Sym, Sec, Offset, Addend, Expr)) {
939 I += (Processed - 1);
940 continue;
941 }
942
943 // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol.
944 if (needsPlt(Expr) && !Sym.isInPlt()) {
945 if (Sym.isGnuIFunc() && !Preemptible)
946 addPltEntry(InX::Iplt, InX::IgotPlt, In<ELFT>::RelaIplt,
947 Target->IRelativeRel, Sym, true);
948 else
949 addPltEntry(InX::Plt, InX::GotPlt, In<ELFT>::RelaPlt, Target->PltRel,
950 Sym, !Preemptible);
951 }
952
953 // Create a GOT slot if a relocation needs GOT.
954 if (needsGot(Expr)) {
955 if (Config->EMachine == EM_MIPS) {
956 // MIPS ABI has special rules to process GOT entries and doesn't
957 // require relocation entries for them. A special case is TLS
958 // relocations. In that case dynamic loader applies dynamic
959 // relocations to initialize TLS GOT entries.
960 // See "Global Offset Table" in Chapter 5 in the following document
961 // for detailed description:
962 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
963 InX::MipsGot->addEntry(Sym, Addend, Expr);
964 if (Sym.isTls() && Sym.IsPreemptible)
965 In<ELFT>::RelaDyn->addReloc({Target->TlsGotRel, InX::MipsGot,
966 Sym.getGotOffset(), false, &Sym, 0});
967 } else if (!Sym.isInGot()) {
968 addGotEntry<ELFT>(Sym, Preemptible);
969 }
970 }
971
972 if (!needsPlt(Expr) && !needsGot(Expr) && Sym.IsPreemptible) {
973 // We don't know anything about the finaly symbol. Just ask the dynamic
974 // linker to handle the relocation for us.
975 if (!Target->isPicRel(Type))
976 errorOrWarn(
977 "relocation " + toString(Type) +
978 " cannot be used against shared object; recompile with -fPIC" +
979 getLocation<ELFT>(Sec, Sym, Offset));
980
981 In<ELFT>::RelaDyn->addReloc(
982 {Target->getDynRel(Type), &Sec, Offset, false, &Sym, Addend});
983
984 // MIPS ABI turns using of GOT and dynamic relocations inside out.
985 // While regular ABI uses dynamic relocations to fill up GOT entries
986 // MIPS ABI requires dynamic linker to fills up GOT entries using
987 // specially sorted dynamic symbol table. This affects even dynamic
988 // relocations against symbols which do not require GOT entries
989 // creation explicitly, i.e. do not have any GOT-relocations. So if
990 // a preemptible symbol has a dynamic relocation we anyway have
991 // to create a GOT entry for it.
992 // If a non-preemptible symbol has a dynamic relocation against it,
993 // dynamic linker takes it st_value, adds offset and writes down
994 // result of the dynamic relocation. In case of preemptible symbol
995 // dynamic linker performs symbol resolution, writes the symbol value
996 // to the GOT entry and reads the GOT entry when it needs to perform
997 // a dynamic relocation.
998 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
999 if (Config->EMachine == EM_MIPS)
1000 InX::MipsGot->addEntry(Sym, Addend, Expr);
1001 continue;
1002 }
1003
1004 // If the relocation points to something in the file, we can process it.
1005 bool IsConstant =
1006 isStaticLinkTimeConstant<ELFT>(Expr, Type, Sym, Sec, Rel.r_offset);
1007
1008 // The size is not going to change, so we fold it in here.
1009 if (Expr == R_SIZE)
1010 Addend += Sym.getSize();
1011
1012 // If the produced value is a constant, we just remember to write it
1013 // when outputting this section. We also have to do it if the format
1014 // uses Elf_Rel, since in that case the written value is the addend.
1015 if (IsConstant) {
1016 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
1017 continue;
1018 }
1019
1020 // If the output being produced is position independent, the final value
1021 // is still not known. In that case we still need some help from the
1022 // dynamic linker. We can however do better than just copying the incoming
1023 // relocation. We can process some of it and and just ask the dynamic
1024 // linker to add the load address.
1025 if (Config->IsRela) {
1026 In<ELFT>::RelaDyn->addReloc(
1027 {Target->RelativeRel, &Sec, Offset, true, &Sym, Addend});
1028 } else {
1029 // In REL, addends are stored to the target section.
1030 In<ELFT>::RelaDyn->addReloc(
1031 {Target->RelativeRel, &Sec, Offset, true, &Sym, 0});
1032 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
1033 }
1034 }
1035}
1036
1037template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
1038 if (S.AreRelocsRela)
1039 scanRelocs<ELFT>(S, S.relas<ELFT>());
1040 else
1041 scanRelocs<ELFT>(S, S.rels<ELFT>());
1042}
1043
1044// Thunk Implementation
1045//
1046// Thunks (sometimes called stubs, veneers or branch islands) are small pieces
1047// of code that the linker inserts inbetween a caller and a callee. The thunks
1048// are added at link time rather than compile time as the decision on whether
1049// a thunk is needed, such as the caller and callee being out of range, can only
1050// be made at link time.
1051//
1052// It is straightforward to tell given the current state of the program when a
1053// thunk is needed for a particular call. The more difficult part is that
1054// the thunk needs to be placed in the program such that the caller can reach
1055// the thunk and the thunk can reach the callee; furthermore, adding thunks to
1056// the program alters addresses, which can mean more thunks etc.
1057//
1058// In lld we have a synthetic ThunkSection that can hold many Thunks.
1059// The decision to have a ThunkSection act as a container means that we can
1060// more easily handle the most common case of a single block of contiguous
1061// Thunks by inserting just a single ThunkSection.
1062//
1063// The implementation of Thunks in lld is split across these areas
1064// Relocations.cpp : Framework for creating and placing thunks
1065// Thunks.cpp : The code generated for each supported thunk
1066// Target.cpp : Target specific hooks that the framework uses to decide when
1067// a thunk is used
1068// Synthetic.cpp : Implementation of ThunkSection
1069// Writer.cpp : Iteratively call framework until no more Thunks added
1070//
1071// Thunk placement requirements:
1072// Mips LA25 thunks. These must be placed immediately before the callee section
1073// We can assume that the caller is in range of the Thunk. These are modelled
1074// by Thunks that return the section they must precede with
1075// getTargetInputSection().
1076//
1077// ARM interworking and range extension thunks. These thunks must be placed
1078// within range of the caller. All implemented ARM thunks can always reach the
1079// callee as they use an indirect jump via a register that has no range
1080// restrictions.
1081//
1082// Thunk placement algorithm:
1083// For Mips LA25 ThunkSections; the placement is explicit, it has to be before
1084// getTargetInputSection().
1085//
1086// For thunks that must be placed within range of the caller there are many
1087// possible choices given that the maximum range from the caller is usually
1088// much larger than the average InputSection size. Desirable properties include:
1089// - Maximize reuse of thunks by multiple callers
1090// - Minimize number of ThunkSections to simplify insertion
1091// - Handle impact of already added Thunks on addresses
1092// - Simple to understand and implement
1093//
1094// In lld for the first pass, we pre-create one or more ThunkSections per
1095// InputSectionDescription at Target specific intervals. A ThunkSection is
1096// placed so that the estimated end of the ThunkSection is within range of the
1097// start of the InputSectionDescription or the previous ThunkSection. For
1098// example:
1099// InputSectionDescription
1100// Section 0
1101// ...
1102// Section N
1103// ThunkSection 0
1104// Section N + 1
1105// ...
1106// Section N + K
1107// Thunk Section 1
1108//
1109// The intention is that we can add a Thunk to a ThunkSection that is well
1110// spaced enough to service a number of callers without having to do a lot
1111// of work. An important principle is that it is not an error if a Thunk cannot
1112// be placed in a pre-created ThunkSection; when this happens we create a new
1113// ThunkSection placed next to the caller. This allows us to handle the vast
1114// majority of thunks simply, but also handle rare cases where the branch range
1115// is smaller than the target specific spacing.
1116//
1117// The algorithm is expected to create all the thunks that are needed in a
1118// single pass, with a small number of programs needing a second pass due to
1119// the insertion of thunks in the first pass increasing the offset between
1120// callers and callees that were only just in range.
1121//
1122// A consequence of allowing new ThunkSections to be created outside of the
1123// pre-created ThunkSections is that in rare cases calls to Thunks that were in
1124// range in pass K, are out of range in some pass > K due to the insertion of
1125// more Thunks in between the caller and callee. When this happens we retarget
1126// the relocation back to the original target and create another Thunk.
1127
1128// Remove ThunkSections that are empty, this should only be the initial set
1129// precreated on pass 0.
1130
1131// Insert the Thunks for OutputSection OS into their designated place
1132// in the Sections vector, and recalculate the InputSection output section
1133// offsets.
1134// This may invalidate any output section offsets stored outside of InputSection
1135void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
1136 forEachInputSectionDescription(
1137 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1138 if (ISD->ThunkSections.empty())
1139 return;
1140
1141 // Remove any zero sized precreated Thunks.
1142 llvm::erase_if(ISD->ThunkSections,
1143 [](const std::pair<ThunkSection *, uint32_t> &TS) {
1144 return TS.first->getSize() == 0;
1145 });
1146 // ISD->ThunkSections contains all created ThunkSections, including
1147 // those inserted in previous passes. Extract the Thunks created this
1148 // pass and order them in ascending OutSecOff.
1149 std::vector<ThunkSection *> NewThunks;
1150 for (const std::pair<ThunkSection *, uint32_t> TS : ISD->ThunkSections)
1151 if (TS.second == Pass)
1152 NewThunks.push_back(TS.first);
1153 std::stable_sort(NewThunks.begin(), NewThunks.end(),
1154 [](const ThunkSection *A, const ThunkSection *B) {
1155 return A->OutSecOff < B->OutSecOff;
1156 });
1157
1158 // Merge sorted vectors of Thunks and InputSections by OutSecOff
1159 std::vector<InputSection *> Tmp;
1160 Tmp.reserve(ISD->Sections.size() + NewThunks.size());
1161 auto MergeCmp = [](const InputSection *A, const InputSection *B) {
1162 // std::merge requires a strict weak ordering.
1163 if (A->OutSecOff < B->OutSecOff)
1164 return true;
1165 if (A->OutSecOff == B->OutSecOff) {
1166 auto *TA = dyn_cast<ThunkSection>(A);
1167 auto *TB = dyn_cast<ThunkSection>(B);
1168 // Check if Thunk is immediately before any specific Target
1169 // InputSection for example Mips LA25 Thunks.
1170 if (TA && TA->getTargetInputSection() == B)
1171 return true;
1172 if (TA && !TB && !TA->getTargetInputSection())
1173 // Place Thunk Sections without specific targets before
1174 // non-Thunk Sections.
1175 return true;
1176 }
1177 return false;
1178 };
1179 std::merge(ISD->Sections.begin(), ISD->Sections.end(),
1180 NewThunks.begin(), NewThunks.end(), std::back_inserter(Tmp),
1181 MergeCmp);
1182 ISD->Sections = std::move(Tmp);
1183 });
1184}
1185
1186// Find or create a ThunkSection within the InputSectionDescription (ISD) that
1187// is in range of Src. An ISD maps to a range of InputSections described by a
1188// linker script section pattern such as { .text .text.* }.
1189ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *OS, InputSection *IS,
1190 InputSectionDescription *ISD,
1191 uint32_t Type, uint64_t Src) {
1192 for (std::pair<ThunkSection *, uint32_t> TP : ISD->ThunkSections) {
1193 ThunkSection *TS = TP.first;
1194 uint64_t TSBase = OS->Addr + TS->OutSecOff;
1195 uint64_t TSLimit = TSBase + TS->getSize();
1196 if (Target->inBranchRange(Type, Src, (Src > TSLimit) ? TSBase : TSLimit))
1197 return TS;
1198 }
1199
1200 // No suitable ThunkSection exists. This can happen when there is a branch
1201 // with lower range than the ThunkSection spacing or when there are too
1202 // many Thunks. Create a new ThunkSection as close to the InputSection as
1203 // possible. Error if InputSection is so large we cannot place ThunkSection
1204 // anywhere in Range.
1205 uint64_t ThunkSecOff = IS->OutSecOff;
1206 if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff)) {
1207 ThunkSecOff = IS->OutSecOff + IS->getSize();
1208 if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff))
1209 fatal("InputSection too large for range extension thunk " +
1210 IS->getObjMsg(Src - (OS->Addr + IS->OutSecOff)));
1211 }
1212 return addThunkSection(OS, ISD, ThunkSecOff);
1213}
1214
1215// Add a Thunk that needs to be placed in a ThunkSection that immediately
1216// precedes its Target.
1217ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
1218 ThunkSection *TS = ThunkedSections.lookup(IS);
1219 if (TS)
1220 return TS;
1221
1222 // Find InputSectionRange within Target Output Section (TOS) that the
1223 // InputSection (IS) that we need to precede is in.
1224 OutputSection *TOS = IS->getParent();
1225 for (BaseCommand *BC : TOS->SectionCommands)
1226 if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
1227 if (ISD->Sections.empty())
1228 continue;
1229 InputSection *first = ISD->Sections.front();
1230 InputSection *last = ISD->Sections.back();
1231 if (IS->OutSecOff >= first->OutSecOff &&
1232 IS->OutSecOff <= last->OutSecOff) {
1233 TS = addThunkSection(TOS, ISD, IS->OutSecOff);
1234 ThunkedSections[IS] = TS;
1235 break;
1236 }
1237 }
1238 return TS;
1239}
1240
1241// Create one or more ThunkSections per OS that can be used to place Thunks.
1242// We attempt to place the ThunkSections using the following desirable
1243// properties:
1244// - Within range of the maximum number of callers
1245// - Minimise the number of ThunkSections
1246//
1247// We follow a simple but conservative heuristic to place ThunkSections at
1248// offsets that are multiples of a Target specific branch range.
1249// For an InputSectionRange that is smaller than the range, a single
1250// ThunkSection at the end of the range will do.
1251void ThunkCreator::createInitialThunkSections(
1252 ArrayRef<OutputSection *> OutputSections) {
1253 forEachInputSectionDescription(
1254 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1255 if (ISD->Sections.empty())
1
Assuming the condition is false
2
Taking false branch
1256 return;
1257 uint32_t ISLimit;
3
'ISLimit' declared without an initial value
1258 uint32_t PrevISLimit = ISD->Sections.front()->OutSecOff;
1259 uint32_t ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
1260
1261 for (const InputSection *IS : ISD->Sections) {
1262 ISLimit = IS->OutSecOff + IS->getSize();
1263 if (ISLimit > ThunkUpperBound) {
1264 addThunkSection(OS, ISD, PrevISLimit);
1265 ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
1266 }
1267 PrevISLimit = ISLimit;
1268 }
1269 addThunkSection(OS, ISD, ISLimit);
4
3rd function call argument is an uninitialized value
1270 });
1271}
1272
1273ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
1274 InputSectionDescription *ISD,
1275 uint64_t Off) {
1276 auto *TS = make<ThunkSection>(OS, Off);
1277 ISD->ThunkSections.push_back(std::make_pair(TS, Pass));
1278 return TS;
1279}
1280
1281std::pair<Thunk *, bool> ThunkCreator::getThunk(Symbol &Sym, RelType Type,
1282 uint64_t Src) {
1283 auto Res = ThunkedSymbols.insert({&Sym, std::vector<Thunk *>()});
1284 if (!Res.second) {
1285 // Check existing Thunks for Sym to see if they can be reused
1286 for (Thunk *ET : Res.first->second)
1287 if (ET->isCompatibleWith(Type) &&
1288 Target->inBranchRange(Type, Src, ET->ThunkSym->getVA()))
1289 return std::make_pair(ET, false);
1290 }
1291 // No existing compatible Thunk in range, create a new one
1292 Thunk *T = addThunk(Type, Sym);
1293 Res.first->second.push_back(T);
1294 return std::make_pair(T, true);
1295}
1296
1297// Call Fn on every executable InputSection accessed via the linker script
1298// InputSectionDescription::Sections.
1299void ThunkCreator::forEachInputSectionDescription(
1300 ArrayRef<OutputSection *> OutputSections,
1301 std::function<void(OutputSection *, InputSectionDescription *)> Fn) {
1302 for (OutputSection *OS : OutputSections) {
1303 if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
1304 continue;
1305 for (BaseCommand *BC : OS->SectionCommands)
1306 if (auto *ISD = dyn_cast<InputSectionDescription>(BC))
1307 Fn(OS, ISD);
1308 }
1309}
1310
1311// Return true if the relocation target is an in range Thunk.
1312// Return false if the relocation is not to a Thunk. If the relocation target
1313// was originally to a Thunk, but is no longer in range we revert the
1314// relocation back to its original non-Thunk target.
1315bool ThunkCreator::normalizeExistingThunk(Relocation &Rel, uint64_t Src) {
1316 if (Thunk *ET = Thunks.lookup(Rel.Sym)) {
1317 if (Target->inBranchRange(Rel.Type, Src, Rel.Sym->getVA()))
1318 return true;
1319 Rel.Sym = &ET->Destination;
1320 if (Rel.Sym->isInPlt())
1321 Rel.Expr = toPlt(Rel.Expr);
1322 }
1323 return false;
1324}
1325
1326// Process all relocations from the InputSections that have been assigned
1327// to InputSectionDescriptions and redirect through Thunks if needed. The
1328// function should be called iteratively until it returns false.
1329//
1330// PreConditions:
1331// All InputSections that may need a Thunk are reachable from
1332// OutputSectionCommands.
1333//
1334// All OutputSections have an address and all InputSections have an offset
1335// within the OutputSection.
1336//
1337// The offsets between caller (relocation place) and callee
1338// (relocation target) will not be modified outside of createThunks().
1339//
1340// PostConditions:
1341// If return value is true then ThunkSections have been inserted into
1342// OutputSections. All relocations that needed a Thunk based on the information
1343// available to createThunks() on entry have been redirected to a Thunk. Note
1344// that adding Thunks changes offsets between caller and callee so more Thunks
1345// may be required.
1346//
1347// If return value is false then no more Thunks are needed, and createThunks has
1348// made no changes. If the target requires range extension thunks, currently
1349// ARM, then any future change in offset between caller and callee risks a
1350// relocation out of range error.
1351bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
1352 bool AddressesChanged = false;
1353 if (Pass == 0 && Target->ThunkSectionSpacing)
1354 createInitialThunkSections(OutputSections);
1355 else if (Pass == 10)
1356 // With Thunk Size much smaller than branch range we expect to
1357 // converge quickly; if we get to 10 something has gone wrong.
1358 fatal("thunk creation not converged");
1359
1360 // Create all the Thunks and insert them into synthetic ThunkSections. The
1361 // ThunkSections are later inserted back into InputSectionDescriptions.
1362 // We separate the creation of ThunkSections from the insertion of the
1363 // ThunkSections as ThunkSections are not always inserted into the same
1364 // InputSectionDescription as the caller.
1365 forEachInputSectionDescription(
1366 OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
1367 for (InputSection *IS : ISD->Sections)
1368 for (Relocation &Rel : IS->Relocations) {
1369 uint64_t Src = OS->Addr + IS->OutSecOff + Rel.Offset;
1370
1371 // If we are a relocation to an existing Thunk, check if it is
1372 // still in range. If not then Rel will be altered to point to its
1373 // original target so another Thunk can be generated.
1374 if (Pass > 0 && normalizeExistingThunk(Rel, Src))
1375 continue;
1376
1377 if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Src,
1378 *Rel.Sym))
1379 continue;
1380 Thunk *T;
1381 bool IsNew;
1382 std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src);
1383 if (IsNew) {
1384 AddressesChanged = true;
1385 // Find or create a ThunkSection for the new Thunk
1386 ThunkSection *TS;
1387 if (auto *TIS = T->getTargetInputSection())
1388 TS = getISThunkSec(TIS);
1389 else
1390 TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src);
1391 TS->addThunk(T);
1392 Thunks[T->ThunkSym] = T;
1393 }
1394 // Redirect relocation to Thunk, we never go via the PLT to a Thunk
1395 Rel.Sym = T->ThunkSym;
1396 Rel.Expr = fromPlt(Rel.Expr);
1397 }
1398 });
1399 // Merge all created synthetic ThunkSections back into OutputSection
1400 mergeThunks(OutputSections);
1401 ++Pass;
1402 return AddressesChanged;
1403}
1404
1405template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
1406template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
1407template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
1408template void elf::scanRelocations<ELF64BE>(InputSectionBase &);