Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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