Bug Summary

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