Bug Summary

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