Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D LLD_VENDOR="Debian" -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/lld/ELF -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/lld/ELF -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/lld/include -I tools/lld/include -I include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-01-19-134126-35450-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/lld/ELF/Relocations.cpp

/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/lld/ELF/Relocations.cpp

1//===- Relocations.cpp ----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains platform-independent functions to process relocations.
10// I'll describe the overview of this file here.
11//
12// Simple relocations are easy to handle for the linker. For example,
13// for R_X86_64_PC64 relocs, the linker just has to fix up locations
14// with the relative offsets to the target symbols. It would just be
15// reading records from relocation sections and applying them to output.
16//
17// But not all relocations are that easy to handle. For example, for
18// R_386_GOTOFF relocs, the linker has to create new GOT entries for
19// symbols if they don't exist, and fix up locations with GOT entry
20// offsets from the beginning of GOT section. So there is more than
21// fixing addresses in relocation processing.
22//
23// ELF defines a large number of complex relocations.
24//
25// The functions in this file analyze relocations and do whatever needs
26// to be done. It includes, but not limited to, the following.
27//
28// - create GOT/PLT entries
29// - create new relocations in .dynsym to let the dynamic linker resolve
30// them at runtime (since ELF supports dynamic linking, not all
31// relocations can be resolved at link-time)
32// - create COPY relocs and reserve space in .bss
33// - replace expensive relocs (in terms of runtime cost) with cheap ones
34// - error out infeasible combinations such as PIC and non-relative relocs
35//
36// Note that the functions in this file don't actually apply relocations
37// because it doesn't know about the output file nor the output file buffer.
38// It instead stores Relocation objects to InputSection's Relocations
39// vector to let it apply later in InputSection::writeTo.
40//
41//===----------------------------------------------------------------------===//
42
43#include "Relocations.h"
44#include "Config.h"
45#include "LinkerScript.h"
46#include "OutputSections.h"
47#include "SymbolTable.h"
48#include "Symbols.h"
49#include "SyntheticSections.h"
50#include "Target.h"
51#include "Thunks.h"
52#include "lld/Common/ErrorHandler.h"
53#include "lld/Common/Memory.h"
54#include "lld/Common/Strings.h"
55#include "llvm/ADT/SmallSet.h"
56#include "llvm/Demangle/Demangle.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;
65using namespace lld;
66using namespace lld::elf;
67
68static Optional<std::string> getLinkerScriptLocation(const Symbol &sym) {
69 for (SectionCommand *cmd : script->sectionCommands)
70 if (auto *assign = dyn_cast<SymbolAssignment>(cmd))
71 if (assign->sym == &sym)
72 return assign->location;
73 return None;
74}
75
76static std::string getDefinedLocation(const Symbol &sym) {
77 const char msg[] = "\n>>> defined in ";
78 if (sym.file)
79 return msg + toString(sym.file);
80 if (Optional<std::string> loc = getLinkerScriptLocation(sym))
81 return msg + *loc;
82 return "";
83}
84
85// Construct a message in the following format.
86//
87// >>> defined in /home/alice/src/foo.o
88// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
89// >>> /home/alice/src/bar.o:(.text+0x1)
90static std::string getLocation(InputSectionBase &s, const Symbol &sym,
91 uint64_t off) {
92 std::string msg = getDefinedLocation(sym) + "\n>>> referenced by ";
93 std::string src = s.getSrcMsg(sym, off);
94 if (!src.empty())
95 msg += src + "\n>>> ";
96 return msg + s.getObjMsg(off);
97}
98
99void elf::reportRangeError(uint8_t *loc, const Relocation &rel, const Twine &v,
100 int64_t min, uint64_t max) {
101 ErrorPlace errPlace = getErrorPlace(loc);
102 std::string hint;
103 if (rel.sym && !rel.sym->isSection())
104 hint = "; references " + lld::toString(*rel.sym);
105 if (!errPlace.srcLoc.empty())
106 hint += "\n>>> referenced by " + errPlace.srcLoc;
107 if (rel.sym && !rel.sym->isSection())
108 hint += getDefinedLocation(*rel.sym);
109
110 if (errPlace.isec && errPlace.isec->name.startswith(".debug"))
111 hint += "; consider recompiling with -fdebug-types-section to reduce size "
112 "of debug sections";
113
114 errorOrWarn(errPlace.loc + "relocation " + lld::toString(rel.type) +
115 " out of range: " + v.str() + " is not in [" + Twine(min).str() +
116 ", " + Twine(max).str() + "]" + hint);
117}
118
119void elf::reportRangeError(uint8_t *loc, int64_t v, int n, const Symbol &sym,
120 const Twine &msg) {
121 ErrorPlace errPlace = getErrorPlace(loc);
122 std::string hint;
123 if (!sym.getName().empty())
124 hint = "; references " + lld::toString(sym) + getDefinedLocation(sym);
125 errorOrWarn(errPlace.loc + msg + " is out of range: " + Twine(v) +
126 " is not in [" + Twine(llvm::minIntN(n)) + ", " +
127 Twine(llvm::maxIntN(n)) + "]" + hint);
128}
129
130// Build a bitmask with one bit set for each 64 subset of RelExpr.
131static constexpr uint64_t buildMask() { return 0; }
132
133template <typename... Tails>
134static constexpr uint64_t buildMask(int head, Tails... tails) {
135 return (0 <= head && head < 64 ? uint64_t(1) << head : 0) |
136 buildMask(tails...);
137}
138
139// Return true if `Expr` is one of `Exprs`.
140// There are more than 64 but less than 128 RelExprs, so we divide the set of
141// exprs into [0, 64) and [64, 128) and represent each range as a constant
142// 64-bit mask. Then we decide which mask to test depending on the value of
143// expr and use a simple shift and bitwise-and to test for membership.
144template <RelExpr... Exprs> static bool oneof(RelExpr expr) {
145 assert(0 <= expr && (int)expr < 128 &&(static_cast <bool> (0 <= expr && (int)expr <
128 && "RelExpr is too large for 128-bit mask!") ? void
(0) : __assert_fail ("0 <= expr && (int)expr < 128 && \"RelExpr is too large for 128-bit mask!\""
, "lld/ELF/Relocations.cpp", 146, __extension__ __PRETTY_FUNCTION__
))
146 "RelExpr is too large for 128-bit mask!")(static_cast <bool> (0 <= expr && (int)expr <
128 && "RelExpr is too large for 128-bit mask!") ? void
(0) : __assert_fail ("0 <= expr && (int)expr < 128 && \"RelExpr is too large for 128-bit mask!\""
, "lld/ELF/Relocations.cpp", 146, __extension__ __PRETTY_FUNCTION__
))
;
147
148 if (expr >= 64)
149 return (uint64_t(1) << (expr - 64)) & buildMask((Exprs - 64)...);
150 return (uint64_t(1) << expr) & buildMask(Exprs...);
151}
152
153static RelType getMipsPairType(RelType type, bool isLocal) {
154 switch (type) {
155 case R_MIPS_HI16:
156 return R_MIPS_LO16;
157 case R_MIPS_GOT16:
158 // In case of global symbol, the R_MIPS_GOT16 relocation does not
159 // have a pair. Each global symbol has a unique entry in the GOT
160 // and a corresponding instruction with help of the R_MIPS_GOT16
161 // relocation loads an address of the symbol. In case of local
162 // symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold
163 // the high 16 bits of the symbol's value. A paired R_MIPS_LO16
164 // relocations handle low 16 bits of the address. That allows
165 // to allocate only one GOT entry for every 64 KBytes of local data.
166 return isLocal ? R_MIPS_LO16 : R_MIPS_NONE;
167 case R_MICROMIPS_GOT16:
168 return isLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE;
169 case R_MIPS_PCHI16:
170 return R_MIPS_PCLO16;
171 case R_MICROMIPS_HI16:
172 return R_MICROMIPS_LO16;
173 default:
174 return R_MIPS_NONE;
175 }
176}
177
178// True if non-preemptable symbol always has the same value regardless of where
179// the DSO is loaded.
180static bool isAbsolute(const Symbol &sym) {
181 if (sym.isUndefWeak())
182 return true;
183 if (const auto *dr = dyn_cast<Defined>(&sym))
184 return dr->section == nullptr; // Absolute symbol.
185 return false;
186}
187
188static bool isAbsoluteValue(const Symbol &sym) {
189 return isAbsolute(sym) || sym.isTls();
190}
191
192// Returns true if Expr refers a PLT entry.
193static bool needsPlt(RelExpr expr) {
194 return oneof<R_PLT, R_PLT_PC, R_PLT_GOTPLT, R_PPC32_PLTREL, R_PPC64_CALL_PLT>(
195 expr);
196}
197
198// Returns true if Expr refers a GOT entry. Note that this function
199// returns false for TLS variables even though they need GOT, because
200// TLS variables uses GOT differently than the regular variables.
201static bool needsGot(RelExpr expr) {
202 return oneof<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF,
203 R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT,
204 R_AARCH64_GOT_PAGE>(expr);
205}
206
207// True if this expression is of the form Sym - X, where X is a position in the
208// file (PC, or GOT for example).
209static bool isRelExpr(RelExpr expr) {
210 return oneof<R_PC, R_GOTREL, R_GOTPLTREL, R_MIPS_GOTREL, R_PPC64_CALL,
211 R_PPC64_RELAX_TOC, R_AARCH64_PAGE_PC, R_RELAX_GOT_PC,
212 R_RISCV_PC_INDIRECT, R_PPC64_RELAX_GOT_PC>(expr);
213}
214
215
216static RelExpr toPlt(RelExpr expr) {
217 switch (expr) {
218 case R_PPC64_CALL:
219 return R_PPC64_CALL_PLT;
220 case R_PC:
221 return R_PLT_PC;
222 case R_ABS:
223 return R_PLT;
224 default:
225 return expr;
226 }
227}
228
229static RelExpr fromPlt(RelExpr expr) {
230 // We decided not to use a plt. Optimize a reference to the plt to a
231 // reference to the symbol itself.
232 switch (expr) {
233 case R_PLT_PC:
234 case R_PPC32_PLTREL:
235 return R_PC;
236 case R_PPC64_CALL_PLT:
237 return R_PPC64_CALL;
238 case R_PLT:
239 return R_ABS;
240 case R_PLT_GOTPLT:
241 return R_GOTPLTREL;
242 default:
243 return expr;
244 }
245}
246
247// Returns true if a given shared symbol is in a read-only segment in a DSO.
248template <class ELFT> static bool isReadOnly(SharedSymbol &ss) {
249 using Elf_Phdr = typename ELFT::Phdr;
250
251 // Determine if the symbol is read-only by scanning the DSO's program headers.
252 const SharedFile &file = ss.getFile();
253 for (const Elf_Phdr &phdr :
254 check(file.template getObj<ELFT>().program_headers()))
255 if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) &&
256 !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr &&
257 ss.value < phdr.p_vaddr + phdr.p_memsz)
258 return true;
259 return false;
260}
261
262// Returns symbols at the same offset as a given symbol, including SS itself.
263//
264// If two or more symbols are at the same offset, and at least one of
265// them are copied by a copy relocation, all of them need to be copied.
266// Otherwise, they would refer to different places at runtime.
267template <class ELFT>
268static SmallSet<SharedSymbol *, 4> getSymbolsAt(SharedSymbol &ss) {
269 using Elf_Sym = typename ELFT::Sym;
270
271 SharedFile &file = ss.getFile();
272
273 SmallSet<SharedSymbol *, 4> ret;
274 for (const Elf_Sym &s : file.template getGlobalELFSyms<ELFT>()) {
275 if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS ||
276 s.getType() == STT_TLS || s.st_value != ss.value)
277 continue;
278 StringRef name = check(s.getName(file.getStringTable()));
279 Symbol *sym = symtab->find(name);
280 if (auto *alias = dyn_cast_or_null<SharedSymbol>(sym))
281 ret.insert(alias);
282 }
283
284 // The loop does not check SHT_GNU_verneed, so ret does not contain
285 // non-default version symbols. If ss has a non-default version, ret won't
286 // contain ss. Just add ss unconditionally. If a non-default version alias is
287 // separately copy relocated, it and ss will have different addresses.
288 // Fortunately this case is impractical and fails with GNU ld as well.
289 ret.insert(&ss);
290 return ret;
291}
292
293// When a symbol is copy relocated or we create a canonical plt entry, it is
294// effectively a defined symbol. In the case of copy relocation the symbol is
295// in .bss and in the case of a canonical plt entry it is in .plt. This function
296// replaces the existing symbol with a Defined pointing to the appropriate
297// location.
298static void replaceWithDefined(Symbol &sym, SectionBase &sec, uint64_t value,
299 uint64_t size) {
300 Symbol old = sym;
301
302 sym.replace(Defined{sym.file, sym.getName(), sym.binding, sym.stOther,
303 sym.type, value, size, &sec});
304
305 sym.auxIdx = old.auxIdx;
306 sym.verdefIndex = old.verdefIndex;
307 sym.exportDynamic = true;
308 sym.isUsedInRegularObj = true;
309 // A copy relocated alias may need a GOT entry.
310 sym.needsGot = old.needsGot;
311}
312
313// Reserve space in .bss or .bss.rel.ro for copy relocation.
314//
315// The copy relocation is pretty much a hack. If you use a copy relocation
316// in your program, not only the symbol name but the symbol's size, RW/RO
317// bit and alignment become part of the ABI. In addition to that, if the
318// symbol has aliases, the aliases become part of the ABI. That's subtle,
319// but if you violate that implicit ABI, that can cause very counter-
320// intuitive consequences.
321//
322// So, what is the copy relocation? It's for linking non-position
323// independent code to DSOs. In an ideal world, all references to data
324// exported by DSOs should go indirectly through GOT. But if object files
325// are compiled as non-PIC, all data references are direct. There is no
326// way for the linker to transform the code to use GOT, as machine
327// instructions are already set in stone in object files. This is where
328// the copy relocation takes a role.
329//
330// A copy relocation instructs the dynamic linker to copy data from a DSO
331// to a specified address (which is usually in .bss) at load-time. If the
332// static linker (that's us) finds a direct data reference to a DSO
333// symbol, it creates a copy relocation, so that the symbol can be
334// resolved as if it were in .bss rather than in a DSO.
335//
336// As you can see in this function, we create a copy relocation for the
337// dynamic linker, and the relocation contains not only symbol name but
338// various other information about the symbol. So, such attributes become a
339// part of the ABI.
340//
341// Note for application developers: I can give you a piece of advice if
342// you are writing a shared library. You probably should export only
343// functions from your library. You shouldn't export variables.
344//
345// As an example what can happen when you export variables without knowing
346// the semantics of copy relocations, assume that you have an exported
347// variable of type T. It is an ABI-breaking change to add new members at
348// end of T even though doing that doesn't change the layout of the
349// existing members. That's because the space for the new members are not
350// reserved in .bss unless you recompile the main program. That means they
351// are likely to overlap with other data that happens to be laid out next
352// to the variable in .bss. This kind of issue is sometimes very hard to
353// debug. What's a solution? Instead of exporting a variable V from a DSO,
354// define an accessor getV().
355template <class ELFT> static void addCopyRelSymbolImpl(SharedSymbol &ss) {
356 // Copy relocation against zero-sized symbol doesn't make sense.
357 uint64_t symSize = ss.getSize();
358 if (symSize == 0 || ss.alignment == 0)
359 fatal("cannot create a copy relocation for symbol " + toString(ss));
360
361 // See if this symbol is in a read-only segment. If so, preserve the symbol's
362 // memory protection by reserving space in the .bss.rel.ro section.
363 bool isRO = isReadOnly<ELFT>(ss);
364 BssSection *sec =
365 make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment);
366 OutputSection *osec = (isRO ? in.bssRelRo : in.bss)->getParent();
367
368 // At this point, sectionBases has been migrated to sections. Append sec to
369 // sections.
370 if (osec->commands.empty() ||
371 !isa<InputSectionDescription>(osec->commands.back()))
372 osec->commands.push_back(make<InputSectionDescription>(""));
373 auto *isd = cast<InputSectionDescription>(osec->commands.back());
374 isd->sections.push_back(sec);
375 osec->commitSection(sec);
376
377 // Look through the DSO's dynamic symbol table for aliases and create a
378 // dynamic symbol for each one. This causes the copy relocation to correctly
379 // interpose any aliases.
380 for (SharedSymbol *sym : getSymbolsAt<ELFT>(ss))
381 replaceWithDefined(*sym, *sec, 0, sym->size);
382
383 mainPart->relaDyn->addSymbolReloc(target->copyRel, *sec, 0, ss);
384}
385
386static void addCopyRelSymbol(SharedSymbol &ss) {
387 const SharedFile &file = ss.getFile();
388 switch (file.ekind) {
389 case ELF32LEKind:
390 addCopyRelSymbolImpl<ELF32LE>(ss);
391 break;
392 case ELF32BEKind:
393 addCopyRelSymbolImpl<ELF32BE>(ss);
394 break;
395 case ELF64LEKind:
396 addCopyRelSymbolImpl<ELF64LE>(ss);
397 break;
398 case ELF64BEKind:
399 addCopyRelSymbolImpl<ELF64BE>(ss);
400 break;
401 default:
402 llvm_unreachable("")::llvm::llvm_unreachable_internal("", "lld/ELF/Relocations.cpp"
, 402)
;
403 }
404}
405
406// .eh_frame sections are mergeable input sections, so their input
407// offsets are not linearly mapped to output section. For each input
408// offset, we need to find a section piece containing the offset and
409// add the piece's base address to the input offset to compute the
410// output offset. That isn't cheap.
411//
412// This class is to speed up the offset computation. When we process
413// relocations, we access offsets in the monotonically increasing
414// order. So we can optimize for that access pattern.
415//
416// For sections other than .eh_frame, this class doesn't do anything.
417namespace {
418class OffsetGetter {
419public:
420 explicit OffsetGetter(InputSectionBase &sec) {
421 if (auto *eh = dyn_cast<EhInputSection>(&sec))
422 pieces = eh->pieces;
423 }
424
425 // Translates offsets in input sections to offsets in output sections.
426 // Given offset must increase monotonically. We assume that Piece is
427 // sorted by inputOff.
428 uint64_t get(uint64_t off) {
429 if (pieces.empty())
430 return off;
431
432 while (i != pieces.size() && pieces[i].inputOff + pieces[i].size <= off)
433 ++i;
434 if (i == pieces.size())
435 fatal(".eh_frame: relocation is not in any piece");
436
437 // Pieces must be contiguous, so there must be no holes in between.
438 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\""
, "lld/ELF/Relocations.cpp", 438, __extension__ __PRETTY_FUNCTION__
))
;
439
440 // Offset -1 means that the piece is dead (i.e. garbage collected).
441 if (pieces[i].outputOff == -1)
442 return -1;
443 return pieces[i].outputOff + off - pieces[i].inputOff;
444 }
445
446private:
447 ArrayRef<EhSectionPiece> pieces;
448 size_t i = 0;
449};
450
451// This class encapsulates states needed to scan relocations for one
452// InputSectionBase.
453class RelocationScanner {
454public:
455 explicit RelocationScanner(InputSectionBase &sec)
456 : sec(sec), getter(sec), config(elf::config.get()), target(*elf::target) {
457 }
458 template <class ELFT, class RelTy> void scan(ArrayRef<RelTy> rels);
459
460private:
461 InputSectionBase &sec;
462 OffsetGetter getter;
463 const Configuration *const config;
464 const TargetInfo &target;
465
466 // End of relocations, used by Mips/PPC64.
467 const void *end = nullptr;
468
469 template <class RelTy> RelType getMipsN32RelType(RelTy *&rel) const;
470 template <class ELFT, class RelTy>
471 int64_t computeMipsAddend(const RelTy &rel, RelExpr expr, bool isLocal) const;
472 template <class ELFT, class RelTy>
473 int64_t computeAddend(const RelTy &rel, RelExpr expr, bool isLocal) const;
474 bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
475 uint64_t relOff) const;
476 void processAux(RelExpr expr, RelType type, uint64_t offset, Symbol &sym,
477 int64_t addend) const;
478 template <class ELFT, class RelTy> void scanOne(RelTy *&i);
479};
480} // namespace
481
482// MIPS has an odd notion of "paired" relocations to calculate addends.
483// For example, if a relocation is of R_MIPS_HI16, there must be a
484// R_MIPS_LO16 relocation after that, and an addend is calculated using
485// the two relocations.
486template <class ELFT, class RelTy>
487int64_t RelocationScanner::computeMipsAddend(const RelTy &rel, RelExpr expr,
488 bool isLocal) const {
489 if (expr == R_MIPS_GOTREL && isLocal)
490 return sec.getFile<ELFT>()->mipsGp0;
491
492 // The ABI says that the paired relocation is used only for REL.
493 // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
494 if (RelTy::IsRela)
495 return 0;
496
497 RelType type = rel.getType(config->isMips64EL);
498 uint32_t pairTy = getMipsPairType(type, isLocal);
499 if (pairTy == R_MIPS_NONE)
500 return 0;
501
502 const uint8_t *buf = sec.data().data();
503 uint32_t symIndex = rel.getSymbol(config->isMips64EL);
504
505 // To make things worse, paired relocations might not be contiguous in
506 // the relocation table, so we need to do linear search. *sigh*
507 for (const RelTy *ri = &rel; ri != static_cast<const RelTy *>(end); ++ri)
508 if (ri->getType(config->isMips64EL) == pairTy &&
509 ri->getSymbol(config->isMips64EL) == symIndex)
510 return target.getImplicitAddend(buf + ri->r_offset, pairTy);
511
512 warn("can't find matching " + toString(pairTy) + " relocation for " +
513 toString(type));
514 return 0;
515}
516
517// Returns an addend of a given relocation. If it is RELA, an addend
518// is in a relocation itself. If it is REL, we need to read it from an
519// input section.
520template <class ELFT, class RelTy>
521int64_t RelocationScanner::computeAddend(const RelTy &rel, RelExpr expr,
522 bool isLocal) const {
523 int64_t addend;
524 RelType type = rel.getType(config->isMips64EL);
525
526 if (RelTy::IsRela) {
527 addend = getAddend<ELFT>(rel);
528 } else {
529 const uint8_t *buf = sec.data().data();
530 addend = target.getImplicitAddend(buf + rel.r_offset, type);
531 }
532
533 if (config->emachine == EM_PPC64 && config->isPic && type == R_PPC64_TOC)
534 addend += getPPC64TocBase();
535 if (config->emachine == EM_MIPS)
536 addend += computeMipsAddend<ELFT>(rel, expr, isLocal);
537
538 return addend;
539}
540
541// Custom error message if Sym is defined in a discarded section.
542template <class ELFT>
543static std::string maybeReportDiscarded(Undefined &sym) {
544 auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file);
545 if (!file || !sym.discardedSecIdx ||
546 file->getSections()[sym.discardedSecIdx] != &InputSection::discarded)
547 return "";
548 ArrayRef<typename ELFT::Shdr> objSections =
549 file->template getELFShdrs<ELFT>();
550
551 std::string msg;
552 if (sym.type == ELF::STT_SECTION) {
553 msg = "relocation refers to a discarded section: ";
554 msg += CHECK(check2((file->getObj().getSectionName(objSections[sym.discardedSecIdx
])), [&] { return toString(file); })
555 file->getObj().getSectionName(objSections[sym.discardedSecIdx]), file)check2((file->getObj().getSectionName(objSections[sym.discardedSecIdx
])), [&] { return toString(file); })
;
556 } else {
557 msg = "relocation refers to a symbol in a discarded section: " +
558 toString(sym);
559 }
560 msg += "\n>>> defined in " + toString(file);
561
562 Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1];
563 if (elfSec.sh_type != SHT_GROUP)
564 return msg;
565
566 // If the discarded section is a COMDAT.
567 StringRef signature = file->getShtGroupSignature(objSections, elfSec);
568 if (const InputFile *prevailing =
569 symtab->comdatGroups.lookup(CachedHashStringRef(signature)))
570 msg += "\n>>> section group signature: " + signature.str() +
571 "\n>>> prevailing definition is in " + toString(prevailing);
572 return msg;
573}
574
575// Undefined diagnostics are collected in a vector and emitted once all of
576// them are known, so that some postprocessing on the list of undefined symbols
577// can happen before lld emits diagnostics.
578struct UndefinedDiag {
579 Undefined *sym;
580 struct Loc {
581 InputSectionBase *sec;
582 uint64_t offset;
583 };
584 std::vector<Loc> locs;
585 bool isWarning;
586};
587
588static std::vector<UndefinedDiag> undefs;
589
590// Check whether the definition name def is a mangled function name that matches
591// the reference name ref.
592static bool canSuggestExternCForCXX(StringRef ref, StringRef def) {
593 llvm::ItaniumPartialDemangler d;
594 std::string name = def.str();
595 if (d.partialDemangle(name.c_str()))
596 return false;
597 char *buf = d.getFunctionName(nullptr, nullptr);
598 if (!buf)
599 return false;
600 bool ret = ref == buf;
601 free(buf);
602 return ret;
603}
604
605// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
606// the suggested symbol, which is either in the symbol table, or in the same
607// file of sym.
608static const Symbol *getAlternativeSpelling(const Undefined &sym,
609 std::string &pre_hint,
610 std::string &post_hint) {
611 DenseMap<StringRef, const Symbol *> map;
612 if (sym.file && sym.file->kind() == InputFile::ObjKind) {
613 auto *file = cast<ELFFileBase>(sym.file);
614 // If sym is a symbol defined in a discarded section, maybeReportDiscarded()
615 // will give an error. Don't suggest an alternative spelling.
616 if (file && sym.discardedSecIdx != 0 &&
617 file->getSections()[sym.discardedSecIdx] == &InputSection::discarded)
618 return nullptr;
619
620 // Build a map of local defined symbols.
621 for (const Symbol *s : sym.file->getSymbols())
622 if (s->isLocal() && s->isDefined() && !s->getName().empty())
623 map.try_emplace(s->getName(), s);
624 }
625
626 auto suggest = [&](StringRef newName) -> const Symbol * {
627 // If defined locally.
628 if (const Symbol *s = map.lookup(newName))
629 return s;
630
631 // If in the symbol table and not undefined.
632 if (const Symbol *s = symtab->find(newName))
633 if (!s->isUndefined())
634 return s;
635
636 return nullptr;
637 };
638
639 // This loop enumerates all strings of Levenshtein distance 1 as typo
640 // correction candidates and suggests the one that exists as a non-undefined
641 // symbol.
642 StringRef name = sym.getName();
643 for (size_t i = 0, e = name.size(); i != e + 1; ++i) {
644 // Insert a character before name[i].
645 std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str();
646 for (char c = '0'; c <= 'z'; ++c) {
647 newName[i] = c;
648 if (const Symbol *s = suggest(newName))
649 return s;
650 }
651 if (i == e)
652 break;
653
654 // Substitute name[i].
655 newName = std::string(name);
656 for (char c = '0'; c <= 'z'; ++c) {
657 newName[i] = c;
658 if (const Symbol *s = suggest(newName))
659 return s;
660 }
661
662 // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is
663 // common.
664 if (i + 1 < e) {
665 newName[i] = name[i + 1];
666 newName[i + 1] = name[i];
667 if (const Symbol *s = suggest(newName))
668 return s;
669 }
670
671 // Delete name[i].
672 newName = (name.substr(0, i) + name.substr(i + 1)).str();
673 if (const Symbol *s = suggest(newName))
674 return s;
675 }
676
677 // Case mismatch, e.g. Foo vs FOO.
678 for (auto &it : map)
679 if (name.equals_insensitive(it.first))
680 return it.second;
681 for (Symbol *sym : symtab->symbols())
682 if (!sym->isUndefined() && name.equals_insensitive(sym->getName()))
683 return sym;
684
685 // The reference may be a mangled name while the definition is not. Suggest a
686 // missing extern "C".
687 if (name.startswith("_Z")) {
688 std::string buf = name.str();
689 llvm::ItaniumPartialDemangler d;
690 if (!d.partialDemangle(buf.c_str()))
691 if (char *buf = d.getFunctionName(nullptr, nullptr)) {
692 const Symbol *s = suggest(buf);
693 free(buf);
694 if (s) {
695 pre_hint = ": extern \"C\" ";
696 return s;
697 }
698 }
699 } else {
700 const Symbol *s = nullptr;
701 for (auto &it : map)
702 if (canSuggestExternCForCXX(name, it.first)) {
703 s = it.second;
704 break;
705 }
706 if (!s)
707 for (Symbol *sym : symtab->symbols())
708 if (canSuggestExternCForCXX(name, sym->getName())) {
709 s = sym;
710 break;
711 }
712 if (s) {
713 pre_hint = " to declare ";
714 post_hint = " as extern \"C\"?";
715 return s;
716 }
717 }
718
719 return nullptr;
720}
721
722template <class ELFT>
723static void reportUndefinedSymbol(const UndefinedDiag &undef,
724 bool correctSpelling) {
725 Undefined &sym = *undef.sym;
726
727 auto visibility = [&]() -> std::string {
728 switch (sym.visibility) {
729 case STV_INTERNAL:
730 return "internal ";
731 case STV_HIDDEN:
732 return "hidden ";
733 case STV_PROTECTED:
734 return "protected ";
735 default:
736 return "";
737 }
738 };
739
740 std::string msg = maybeReportDiscarded<ELFT>(sym);
741 if (msg.empty())
742 msg = "undefined " + visibility() + "symbol: " + toString(sym);
743
744 const size_t maxUndefReferences = 3;
745 size_t i = 0;
746 for (UndefinedDiag::Loc l : undef.locs) {
747 if (i >= maxUndefReferences)
748 break;
749 InputSectionBase &sec = *l.sec;
750 uint64_t offset = l.offset;
751
752 msg += "\n>>> referenced by ";
753 std::string src = sec.getSrcMsg(sym, offset);
754 if (!src.empty())
755 msg += src + "\n>>> ";
756 msg += sec.getObjMsg(offset);
757 i++;
758 }
759
760 if (i < undef.locs.size())
761 msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times")
762 .str();
763
764 if (correctSpelling) {
765 std::string pre_hint = ": ", post_hint;
766 if (const Symbol *corrected =
767 getAlternativeSpelling(sym, pre_hint, post_hint)) {
768 msg += "\n>>> did you mean" + pre_hint + toString(*corrected) + post_hint;
769 if (corrected->file)
770 msg += "\n>>> defined in: " + toString(corrected->file);
771 }
772 }
773
774 if (sym.getName().startswith("_ZTV"))
775 msg +=
776 "\n>>> the vtable symbol may be undefined because the class is missing "
777 "its key function (see https://lld.llvm.org/missingkeyfunction)";
778 if (config->gcSections && config->zStartStopGC &&
779 sym.getName().startswith("__start_")) {
780 msg += "\n>>> the encapsulation symbol needs to be retained under "
781 "--gc-sections properly; consider -z nostart-stop-gc "
782 "(see https://lld.llvm.org/ELF/start-stop-gc)";
783 }
784
785 if (undef.isWarning)
786 warn(msg);
787 else
788 error(msg, ErrorTag::SymbolNotFound, {sym.getName()});
789}
790
791template <class ELFT> void elf::reportUndefinedSymbols() {
792 // Find the first "undefined symbol" diagnostic for each diagnostic, and
793 // collect all "referenced from" lines at the first diagnostic.
794 DenseMap<Symbol *, UndefinedDiag *> firstRef;
795 for (UndefinedDiag &undef : undefs) {
796 assert(undef.locs.size() == 1)(static_cast <bool> (undef.locs.size() == 1) ? void (0)
: __assert_fail ("undef.locs.size() == 1", "lld/ELF/Relocations.cpp"
, 796, __extension__ __PRETTY_FUNCTION__))
;
797 if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) {
798 canon->locs.push_back(undef.locs[0]);
799 undef.locs.clear();
800 } else
801 firstRef[undef.sym] = &undef;
802 }
803
804 // Enable spell corrector for the first 2 diagnostics.
805 for (auto it : enumerate(undefs))
806 if (!it.value().locs.empty())
807 reportUndefinedSymbol<ELFT>(it.value(), it.index() < 2);
808 undefs.clear();
809}
810
811// Report an undefined symbol if necessary.
812// Returns true if the undefined symbol will produce an error message.
813static bool maybeReportUndefined(Undefined &sym, InputSectionBase &sec,
814 uint64_t offset) {
815 // If versioned, issue an error (even if the symbol is weak) because we don't
816 // know the defining filename which is required to construct a Verneed entry.
817 if (sym.hasVersionSuffix) {
818 undefs.push_back({&sym, {{&sec, offset}}, false});
819 return true;
820 }
821 if (sym.isWeak())
822 return false;
823
824 bool canBeExternal = !sym.isLocal() && sym.visibility == STV_DEFAULT;
825 if (config->unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal)
826 return false;
827
828 // clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc
829 // which references a switch table in a discarded .rodata/.text section. The
830 // .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF
831 // spec says references from outside the group to a STB_LOCAL symbol are not
832 // allowed. Work around the bug.
833 //
834 // PPC32 .got2 is similar but cannot be fixed. Multiple .got2 is infeasible
835 // because .LC0-.LTOC is not representable if the two labels are in different
836 // .got2
837 if (sym.discardedSecIdx != 0 && (sec.name == ".got2" || sec.name == ".toc"))
838 return false;
839
840 bool isWarning =
841 (config->unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) ||
842 config->noinhibitExec;
843 undefs.push_back({&sym, {{&sec, offset}}, isWarning});
844 return !isWarning;
845}
846
847// MIPS N32 ABI treats series of successive relocations with the same offset
848// as a single relocation. The similar approach used by N64 ABI, but this ABI
849// packs all relocations into the single relocation record. Here we emulate
850// this for the N32 ABI. Iterate over relocation with the same offset and put
851// theirs types into the single bit-set.
852template <class RelTy>
853RelType RelocationScanner::getMipsN32RelType(RelTy *&rel) const {
854 RelType type = 0;
855 uint64_t offset = rel->r_offset;
856
857 int n = 0;
858 while (rel != static_cast<const RelTy *>(end) && rel->r_offset == offset)
859 type |= (rel++)->getType(config->isMips64EL) << (8 * n++);
860 return type;
861}
862
863static void addRelativeReloc(InputSectionBase &isec, uint64_t offsetInSec,
864 Symbol &sym, int64_t addend, RelExpr expr,
865 RelType type) {
866 Partition &part = isec.getPartition();
867
868 // Add a relative relocation. If relrDyn section is enabled, and the
869 // relocation offset is guaranteed to be even, add the relocation to
870 // the relrDyn section, otherwise add it to the relaDyn section.
871 // relrDyn sections don't support odd offsets. Also, relrDyn sections
872 // don't store the addend values, so we must write it to the relocated
873 // address.
874 if (part.relrDyn && isec.alignment >= 2 && offsetInSec % 2 == 0) {
875 isec.relocations.push_back({expr, type, offsetInSec, addend, &sym});
876 part.relrDyn->relocs.push_back({&isec, offsetInSec});
877 return;
878 }
879 part.relaDyn->addRelativeReloc(target->relativeRel, isec, offsetInSec, sym,
880 addend, type, expr);
881}
882
883template <class PltSection, class GotPltSection>
884static void addPltEntry(PltSection &plt, GotPltSection &gotPlt,
885 RelocationBaseSection &rel, RelType type, Symbol &sym) {
886 plt.addEntry(sym);
887 gotPlt.addEntry(sym);
888 rel.addReloc({type, &gotPlt, sym.getGotPltOffset(),
889 sym.isPreemptible ? DynamicReloc::AgainstSymbol
890 : DynamicReloc::AddendOnlyWithTargetVA,
891 sym, 0, R_ABS});
892}
893
894static void addGotEntry(Symbol &sym) {
895 in.got->addEntry(sym);
896 uint64_t off = sym.getGotOffset();
897
898 // If preemptible, emit a GLOB_DAT relocation.
899 if (sym.isPreemptible) {
900 mainPart->relaDyn->addReloc({target->gotRel, in.got.get(), off,
901 DynamicReloc::AgainstSymbol, sym, 0, R_ABS});
902 return;
903 }
904
905 // Otherwise, the value is either a link-time constant or the load base
906 // plus a constant.
907 if (!config->isPic || isAbsolute(sym))
908 in.got->relocations.push_back({R_ABS, target->symbolicRel, off, 0, &sym});
909 else
910 addRelativeReloc(*in.got, off, sym, 0, R_ABS, target->symbolicRel);
911}
912
913static void addTpOffsetGotEntry(Symbol &sym) {
914 in.got->addEntry(sym);
915 uint64_t off = sym.getGotOffset();
916 if (!sym.isPreemptible && !config->isPic) {
917 in.got->relocations.push_back({R_TPREL, target->symbolicRel, off, 0, &sym});
918 return;
919 }
920 mainPart->relaDyn->addAddendOnlyRelocIfNonPreemptible(
921 target->tlsGotRel, *in.got, off, sym, target->symbolicRel);
922}
923
924// Return true if we can define a symbol in the executable that
925// contains the value/function of a symbol defined in a shared
926// library.
927static bool canDefineSymbolInExecutable(Symbol &sym) {
928 // If the symbol has default visibility the symbol defined in the
929 // executable will preempt it.
930 // Note that we want the visibility of the shared symbol itself, not
931 // the visibility of the symbol in the output file we are producing. That is
932 // why we use Sym.stOther.
933 if ((sym.stOther & 0x3) == STV_DEFAULT)
934 return true;
935
936 // If we are allowed to break address equality of functions, defining
937 // a plt entry will allow the program to call the function in the
938 // .so, but the .so and the executable will no agree on the address
939 // of the function. Similar logic for objects.
940 return ((sym.isFunc() && config->ignoreFunctionAddressEquality) ||
941 (sym.isObject() && config->ignoreDataAddressEquality));
942}
943
944// Returns true if a given relocation can be computed at link-time.
945// This only handles relocation types expected in processRelocAux.
946//
947// For instance, we know the offset from a relocation to its target at
948// link-time if the relocation is PC-relative and refers a
949// non-interposable function in the same executable. This function
950// will return true for such relocation.
951//
952// If this function returns false, that means we need to emit a
953// dynamic relocation so that the relocation will be fixed at load-time.
954bool RelocationScanner::isStaticLinkTimeConstant(RelExpr e, RelType type,
955 const Symbol &sym,
956 uint64_t relOff) const {
957 // These expressions always compute a constant
958 if (oneof<R_GOTPLT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL,
959 R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC,
960 R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
961 R_PLT_PC, R_PLT_GOTPLT, R_PPC32_PLTREL, R_PPC64_CALL_PLT,
962 R_PPC64_RELAX_TOC, R_RISCV_ADD, R_AARCH64_GOT_PAGE>(e))
963 return true;
964
965 // These never do, except if the entire file is position dependent or if
966 // only the low bits are used.
967 if (e == R_GOT || e == R_PLT)
968 return target.usesOnlyLowPageBits(type) || !config->isPic;
969
970 if (sym.isPreemptible)
971 return false;
972 if (!config->isPic)
973 return true;
974
975 // The size of a non preemptible symbol is a constant.
976 if (e == R_SIZE)
977 return true;
978
979 // For the target and the relocation, we want to know if they are
980 // absolute or relative.
981 bool absVal = isAbsoluteValue(sym);
982 bool relE = isRelExpr(e);
983 if (absVal && !relE)
984 return true;
985 if (!absVal && relE)
986 return true;
987 if (!absVal && !relE)
988 return target.usesOnlyLowPageBits(type);
989
990 assert(absVal && relE)(static_cast <bool> (absVal && relE) ? void (0)
: __assert_fail ("absVal && relE", "lld/ELF/Relocations.cpp"
, 990, __extension__ __PRETTY_FUNCTION__))
;
991
992 // Allow R_PLT_PC (optimized to R_PC here) to a hidden undefined weak symbol
993 // in PIC mode. This is a little strange, but it allows us to link function
994 // calls to such symbols (e.g. glibc/stdlib/exit.c:__run_exit_handlers).
995 // Normally such a call will be guarded with a comparison, which will load a
996 // zero from the GOT.
997 if (sym.isUndefWeak())
998 return true;
999
1000 // We set the final symbols values for linker script defined symbols later.
1001 // They always can be computed as a link time constant.
1002 if (sym.scriptDefined)
1003 return true;
1004
1005 error("relocation " + toString(type) + " cannot refer to absolute symbol: " +
1006 toString(sym) + getLocation(sec, sym, relOff));
1007 return true;
1008}
1009
1010// The reason we have to do this early scan is as follows
1011// * To mmap the output file, we need to know the size
1012// * For that, we need to know how many dynamic relocs we will have.
1013// It might be possible to avoid this by outputting the file with write:
1014// * Write the allocated output sections, computing addresses.
1015// * Apply relocations, recording which ones require a dynamic reloc.
1016// * Write the dynamic relocations.
1017// * Write the rest of the file.
1018// This would have some drawbacks. For example, we would only know if .rela.dyn
1019// is needed after applying relocations. If it is, it will go after rw and rx
1020// sections. Given that it is ro, we will need an extra PT_LOAD. This
1021// complicates things for the dynamic linker and means we would have to reserve
1022// space for the extra PT_LOAD even if we end up not using it.
1023void RelocationScanner::processAux(RelExpr expr, RelType type, uint64_t offset,
1024 Symbol &sym, int64_t addend) const {
1025 // If the relocation is known to be a link-time constant, we know no dynamic
1026 // relocation will be created, pass the control to relocateAlloc() or
1027 // relocateNonAlloc() to resolve it.
1028 //
1029 // The behavior of an undefined weak reference is implementation defined. For
1030 // non-link-time constants, we resolve relocations statically (let
1031 // relocate{,Non}Alloc() resolve them) for -no-pie and try producing dynamic
1032 // relocations for -pie and -shared.
1033 //
1034 // The general expectation of -no-pie static linking is that there is no
1035 // dynamic relocation (except IRELATIVE). Emitting dynamic relocations for
1036 // -shared matches the spirit of its -z undefs default. -pie has freedom on
1037 // choices, and we choose dynamic relocations to be consistent with the
1038 // handling of GOT-generating relocations.
1039 if (isStaticLinkTimeConstant(expr, type, sym, offset) ||
1040 (!config->isPic && sym.isUndefWeak())) {
1041 sec.relocations.push_back({expr, type, offset, addend, &sym});
1042 return;
1043 }
1044
1045 bool canWrite = (sec.flags & SHF_WRITE) || !config->zText;
1046 if (canWrite) {
1047 RelType rel = target.getDynRel(type);
1048 if (expr == R_GOT || (rel == target.symbolicRel && !sym.isPreemptible)) {
1049 addRelativeReloc(sec, offset, sym, addend, expr, type);
1050 return;
1051 } else if (rel != 0) {
1052 if (config->emachine == EM_MIPS && rel == target.symbolicRel)
1053 rel = target.relativeRel;
1054 sec.getPartition().relaDyn->addSymbolReloc(rel, sec, offset, sym, addend,
1055 type);
1056
1057 // MIPS ABI turns using of GOT and dynamic relocations inside out.
1058 // While regular ABI uses dynamic relocations to fill up GOT entries
1059 // MIPS ABI requires dynamic linker to fills up GOT entries using
1060 // specially sorted dynamic symbol table. This affects even dynamic
1061 // relocations against symbols which do not require GOT entries
1062 // creation explicitly, i.e. do not have any GOT-relocations. So if
1063 // a preemptible symbol has a dynamic relocation we anyway have
1064 // to create a GOT entry for it.
1065 // If a non-preemptible symbol has a dynamic relocation against it,
1066 // dynamic linker takes it st_value, adds offset and writes down
1067 // result of the dynamic relocation. In case of preemptible symbol
1068 // dynamic linker performs symbol resolution, writes the symbol value
1069 // to the GOT entry and reads the GOT entry when it needs to perform
1070 // a dynamic relocation.
1071 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
1072 if (config->emachine == EM_MIPS)
1073 in.mipsGot->addEntry(*sec.file, sym, addend, expr);
1074 return;
1075 }
1076 }
1077
1078 // When producing an executable, we can perform copy relocations (for
1079 // STT_OBJECT) and canonical PLT (for STT_FUNC).
1080 if (!config->shared) {
1081 if (!canDefineSymbolInExecutable(sym)) {
1082 errorOrWarn("cannot preempt symbol: " + toString(sym) +
1083 getLocation(sec, sym, offset));
1084 return;
1085 }
1086
1087 if (sym.isObject()) {
1088 // Produce a copy relocation.
1089 if (auto *ss = dyn_cast<SharedSymbol>(&sym)) {
1090 if (!config->zCopyreloc)
1091 error("unresolvable relocation " + toString(type) +
1092 " against symbol '" + toString(*ss) +
1093 "'; recompile with -fPIC or remove '-z nocopyreloc'" +
1094 getLocation(sec, sym, offset));
1095 sym.needsCopy = true;
1096 }
1097 sec.relocations.push_back({expr, type, offset, addend, &sym});
1098 return;
1099 }
1100
1101 // This handles a non PIC program call to function in a shared library. In
1102 // an ideal world, we could just report an error saying the relocation can
1103 // overflow at runtime. In the real world with glibc, crt1.o has a
1104 // R_X86_64_PC32 pointing to libc.so.
1105 //
1106 // The general idea on how to handle such cases is to create a PLT entry and
1107 // use that as the function value.
1108 //
1109 // For the static linking part, we just return a plt expr and everything
1110 // else will use the PLT entry as the address.
1111 //
1112 // The remaining problem is making sure pointer equality still works. We
1113 // need the help of the dynamic linker for that. We let it know that we have
1114 // a direct reference to a so symbol by creating an undefined symbol with a
1115 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to
1116 // the value of the symbol we created. This is true even for got entries, so
1117 // pointer equality is maintained. To avoid an infinite loop, the only entry
1118 // that points to the real function is a dedicated got entry used by the
1119 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT,
1120 // R_386_JMP_SLOT, etc).
1121
1122 // For position independent executable on i386, the plt entry requires ebx
1123 // to be set. This causes two problems:
1124 // * If some code has a direct reference to a function, it was probably
1125 // compiled without -fPIE/-fPIC and doesn't maintain ebx.
1126 // * If a library definition gets preempted to the executable, it will have
1127 // the wrong ebx value.
1128 if (sym.isFunc()) {
1129 if (config->pie && config->emachine == EM_386)
1130 errorOrWarn("symbol '" + toString(sym) +
1131 "' cannot be preempted; recompile with -fPIE" +
1132 getLocation(sec, sym, offset));
1133 sym.needsCopy = true;
1134 sym.needsPlt = true;
1135 sec.relocations.push_back({expr, type, offset, addend, &sym});
1136 return;
1137 }
1138 }
1139
1140 errorOrWarn("relocation " + toString(type) + " cannot be used against " +
1141 (sym.getName().empty() ? "local symbol"
1142 : "symbol '" + toString(sym) + "'") +
1143 "; recompile with -fPIC" + getLocation(sec, sym, offset));
1144}
1145
1146// This function is similar to the `handleTlsRelocation`. MIPS does not
1147// support any relaxations for TLS relocations so by factoring out MIPS
1148// handling in to the separate function we can simplify the code and do not
1149// pollute other `handleTlsRelocation` by MIPS `ifs` statements.
1150// Mips has a custom MipsGotSection that handles the writing of GOT entries
1151// without dynamic relocations.
1152static unsigned handleMipsTlsRelocation(RelType type, Symbol &sym,
1153 InputSectionBase &c, uint64_t offset,
1154 int64_t addend, RelExpr expr) {
1155 if (expr == R_MIPS_TLSLD) {
1156 in.mipsGot->addTlsIndex(*c.file);
1157 c.relocations.push_back({expr, type, offset, addend, &sym});
1158 return 1;
1159 }
1160 if (expr == R_MIPS_TLSGD) {
1161 in.mipsGot->addDynTlsEntry(*c.file, sym);
1162 c.relocations.push_back({expr, type, offset, addend, &sym});
1163 return 1;
1164 }
1165 return 0;
1166}
1167
1168// Notes about General Dynamic and Local Dynamic TLS models below. They may
1169// require the generation of a pair of GOT entries that have associated dynamic
1170// relocations. The pair of GOT entries created are of the form GOT[e0] Module
1171// Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of
1172// symbol in TLS block.
1173//
1174// Returns the number of relocations processed.
1175static unsigned handleTlsRelocation(RelType type, Symbol &sym,
1176 InputSectionBase &c, uint64_t offset,
1177 int64_t addend, RelExpr expr) {
1178 if (!sym.isTls())
1179 return 0;
1180
1181 if (config->emachine == EM_MIPS)
1182 return handleMipsTlsRelocation(type, sym, c, offset, addend, expr);
1183
1184 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC,
1185 R_TLSDESC_GOTPLT>(expr) &&
1186 config->shared) {
1187 if (expr != R_TLSDESC_CALL) {
1188 sym.needsTlsDesc = true;
1189 c.relocations.push_back({expr, type, offset, addend, &sym});
1190 }
1191 return 1;
1192 }
1193
1194 // ARM, Hexagon and RISC-V do not support GD/LD to IE/LE relaxation. For
1195 // PPC64, if the file has missing R_PPC64_TLSGD/R_PPC64_TLSLD, disable
1196 // relaxation as well.
1197 bool toExecRelax = !config->shared && config->emachine != EM_ARM &&
1198 config->emachine != EM_HEXAGON &&
1199 config->emachine != EM_RISCV &&
1200 !c.file->ppc64DisableTLSRelax;
1201
1202 // If we are producing an executable and the symbol is non-preemptable, it
1203 // must be defined and the code sequence can be relaxed to use Local-Exec.
1204 //
1205 // ARM and RISC-V do not support any relaxations for TLS relocations, however,
1206 // we can omit the DTPMOD dynamic relocations and resolve them at link time
1207 // because them are always 1. This may be necessary for static linking as
1208 // DTPMOD may not be expected at load time.
1209 bool isLocalInExecutable = !sym.isPreemptible && !config->shared;
1210
1211 // Local Dynamic is for access to module local TLS variables, while still
1212 // being suitable for being dynamically loaded via dlopen. GOT[e0] is the
1213 // module index, with a special value of 0 for the current module. GOT[e1] is
1214 // unused. There only needs to be one module index entry.
1215 if (oneof<R_TLSLD_GOT, R_TLSLD_GOTPLT, R_TLSLD_PC, R_TLSLD_HINT>(
1216 expr)) {
1217 // Local-Dynamic relocs can be relaxed to Local-Exec.
1218 if (toExecRelax) {
1219 c.relocations.push_back(
1220 {target->adjustTlsExpr(type, R_RELAX_TLS_LD_TO_LE), type, offset,
1221 addend, &sym});
1222 return target->getTlsGdRelaxSkip(type);
1223 }
1224 if (expr == R_TLSLD_HINT)
1225 return 1;
1226 sym.needsTlsLd = true;
1227 c.relocations.push_back({expr, type, offset, addend, &sym});
1228 return 1;
1229 }
1230
1231 // Local-Dynamic relocs can be relaxed to Local-Exec.
1232 if (expr == R_DTPREL) {
1233 if (toExecRelax)
1234 expr = target->adjustTlsExpr(type, R_RELAX_TLS_LD_TO_LE);
1235 c.relocations.push_back({expr, type, offset, addend, &sym});
1236 return 1;
1237 }
1238
1239 // Local-Dynamic sequence where offset of tls variable relative to dynamic
1240 // thread pointer is stored in the got. This cannot be relaxed to Local-Exec.
1241 if (expr == R_TLSLD_GOT_OFF) {
1242 sym.needsGotDtprel = true;
1243 c.relocations.push_back({expr, type, offset, addend, &sym});
1244 return 1;
1245 }
1246
1247 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC,
1248 R_TLSDESC_GOTPLT, R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC>(expr)) {
1249 if (!toExecRelax) {
1250 sym.needsTlsGd = true;
1251 c.relocations.push_back({expr, type, offset, addend, &sym});
1252 return 1;
1253 }
1254
1255 // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec
1256 // depending on the symbol being locally defined or not.
1257 if (sym.isPreemptible) {
1258 sym.needsTlsGdToIe = true;
1259 c.relocations.push_back(
1260 {target->adjustTlsExpr(type, R_RELAX_TLS_GD_TO_IE), type, offset,
1261 addend, &sym});
1262 } else {
1263 c.relocations.push_back(
1264 {target->adjustTlsExpr(type, R_RELAX_TLS_GD_TO_LE), type, offset,
1265 addend, &sym});
1266 }
1267 return target->getTlsGdRelaxSkip(type);
1268 }
1269
1270 if (oneof<R_GOT, R_GOTPLT, R_GOT_PC, R_AARCH64_GOT_PAGE_PC, R_GOT_OFF,
1271 R_TLSIE_HINT>(expr)) {
1272 // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally
1273 // defined.
1274 if (toExecRelax && isLocalInExecutable) {
1275 c.relocations.push_back(
1276 {R_RELAX_TLS_IE_TO_LE, type, offset, addend, &sym});
1277 } else if (expr != R_TLSIE_HINT) {
1278 sym.needsTlsIe = true;
1279 // R_GOT needs a relative relocation for PIC on i386 and Hexagon.
1280 if (expr == R_GOT && config->isPic && !target->usesOnlyLowPageBits(type))
1281 addRelativeReloc(c, offset, sym, addend, expr, type);
1282 else
1283 c.relocations.push_back({expr, type, offset, addend, &sym});
1284 }
1285 return 1;
1286 }
1287
1288 return 0;
1289}
1290
1291template <class ELFT, class RelTy> void RelocationScanner::scanOne(RelTy *&i) {
1292 const RelTy &rel = *i;
1293 uint32_t symIndex = rel.getSymbol(config->isMips64EL);
1294 Symbol &sym = sec.getFile<ELFT>()->getSymbol(symIndex);
1295 RelType type;
1296
1297 // Deal with MIPS oddity.
1298 if (config->mipsN32Abi) {
1299 type = getMipsN32RelType(i);
1300 } else {
1301 type = rel.getType(config->isMips64EL);
1302 ++i;
1303 }
1304
1305 // Get an offset in an output section this relocation is applied to.
1306 uint64_t offset = getter.get(rel.r_offset);
1307 if (offset == uint64_t(-1))
1308 return;
1309
1310 // Error if the target symbol is undefined. Symbol index 0 may be used by
1311 // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them.
1312 if (sym.isUndefined() && symIndex != 0 &&
1313 maybeReportUndefined(cast<Undefined>(sym), sec, offset))
1314 return;
1315
1316 const uint8_t *relocatedAddr = sec.data().begin() + offset;
1317 RelExpr expr = target.getRelExpr(type, sym, relocatedAddr);
1318
1319 // Ignore R_*_NONE and other marker relocations.
1320 if (expr == R_NONE)
1321 return;
1322
1323 // Read an addend.
1324 int64_t addend = computeAddend<ELFT>(rel, expr, sym.isLocal());
1325
1326 if (config->emachine == EM_PPC64) {
1327 // We can separate the small code model relocations into 2 categories:
1328 // 1) Those that access the compiler generated .toc sections.
1329 // 2) Those that access the linker allocated got entries.
1330 // lld allocates got entries to symbols on demand. Since we don't try to
1331 // sort the got entries in any way, we don't have to track which objects
1332 // have got-based small code model relocs. The .toc sections get placed
1333 // after the end of the linker allocated .got section and we do sort those
1334 // so sections addressed with small code model relocations come first.
1335 if (type == R_PPC64_TOC16 || type == R_PPC64_TOC16_DS)
1336 sec.file->ppc64SmallCodeModelTocRelocs = true;
1337
1338 // Record the TOC entry (.toc + addend) as not relaxable. See the comment in
1339 // InputSectionBase::relocateAlloc().
1340 if (type == R_PPC64_TOC16_LO && sym.isSection() && isa<Defined>(sym) &&
1341 cast<Defined>(sym).section->name == ".toc")
1342 ppc64noTocRelax.insert({&sym, addend});
1343
1344 if ((type == R_PPC64_TLSGD && expr == R_TLSDESC_CALL) ||
1345 (type == R_PPC64_TLSLD && expr == R_TLSLD_HINT)) {
1346 if (i == end) {
1347 errorOrWarn("R_PPC64_TLSGD/R_PPC64_TLSLD may not be the last "
1348 "relocation" +
1349 getLocation(sec, sym, offset));
1350 return;
1351 }
1352
1353 // Offset the 4-byte aligned R_PPC64_TLSGD by one byte in the NOTOC case,
1354 // so we can discern it later from the toc-case.
1355 if (i->getType(/*isMips64EL=*/false) == R_PPC64_REL24_NOTOC)
1356 ++offset;
1357 }
1358 }
1359
1360 // If the relocation does not emit a GOT or GOTPLT entry but its computation
1361 // uses their addresses, we need GOT or GOTPLT to be created.
1362 //
1363 // The 5 types that relative GOTPLT are all x86 and x86-64 specific.
1364 if (oneof<R_GOTPLTONLY_PC, R_GOTPLTREL, R_GOTPLT, R_PLT_GOTPLT,
1365 R_TLSDESC_GOTPLT, R_TLSGD_GOTPLT>(expr)) {
1366 in.gotPlt->hasGotPltOffRel = true;
1367 } else if (oneof<R_GOTONLY_PC, R_GOTREL, R_PPC32_PLTREL, R_PPC64_TOCBASE,
1368 R_PPC64_RELAX_TOC>(expr)) {
1369 in.got->hasGotOffRel = true;
1370 }
1371
1372 // Process TLS relocations, including relaxing TLS relocations. Note that
1373 // R_TPREL and R_TPREL_NEG relocations are resolved in processAux.
1374 if (expr == R_TPREL || expr == R_TPREL_NEG) {
1375 if (config->shared) {
1376 errorOrWarn("relocation " + toString(type) + " against " + toString(sym) +
1377 " cannot be used with -shared" +
1378 getLocation(sec, sym, offset));
1379 return;
1380 }
1381 } else if (unsigned processed =
1382 handleTlsRelocation(type, sym, sec, offset, addend, expr)) {
1383 i += (processed - 1);
1384 return;
1385 }
1386
1387 // Relax relocations.
1388 //
1389 // If we know that a PLT entry will be resolved within the same ELF module, we
1390 // can skip PLT access and directly jump to the destination function. For
1391 // example, if we are linking a main executable, all dynamic symbols that can
1392 // be resolved within the executable will actually be resolved that way at
1393 // runtime, because the main executable is always at the beginning of a search
1394 // list. We can leverage that fact.
1395 if (!sym.isPreemptible && (!sym.isGnuIFunc() || config->zIfuncNoplt)) {
1396 if (expr != R_GOT_PC) {
1397 // The 0x8000 bit of r_addend of R_PPC_PLTREL24 is used to choose call
1398 // stub type. It should be ignored if optimized to R_PC.
1399 if (config->emachine == EM_PPC && expr == R_PPC32_PLTREL)
1400 addend &= ~0x8000;
1401 // R_HEX_GD_PLT_B22_PCREL (call a@GDPLT) is transformed into
1402 // call __tls_get_addr even if the symbol is non-preemptible.
1403 if (!(config->emachine == EM_HEXAGON &&
1404 (type == R_HEX_GD_PLT_B22_PCREL ||
1405 type == R_HEX_GD_PLT_B22_PCREL_X ||
1406 type == R_HEX_GD_PLT_B32_PCREL_X)))
1407 expr = fromPlt(expr);
1408 } else if (!isAbsoluteValue(sym)) {
1409 expr = target.adjustGotPcExpr(type, addend, relocatedAddr);
1410 }
1411 }
1412
1413 // We were asked not to generate PLT entries for ifuncs. Instead, pass the
1414 // direct relocation on through.
1415 if (sym.isGnuIFunc() && config->zIfuncNoplt) {
1416 sym.exportDynamic = true;
1417 mainPart->relaDyn->addSymbolReloc(type, sec, offset, sym, addend, type);
1418 return;
1419 }
1420
1421 if (needsGot(expr)) {
1422 if (config->emachine == EM_MIPS) {
1423 // MIPS ABI has special rules to process GOT entries and doesn't
1424 // require relocation entries for them. A special case is TLS
1425 // relocations. In that case dynamic loader applies dynamic
1426 // relocations to initialize TLS GOT entries.
1427 // See "Global Offset Table" in Chapter 5 in the following document
1428 // for detailed description:
1429 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1430 in.mipsGot->addEntry(*sec.file, sym, addend, expr);
1431 } else {
1432 sym.needsGot = true;
1433 }
1434 } else if (needsPlt(expr)) {
1435 sym.needsPlt = true;
1436 } else {
1437 sym.hasDirectReloc = true;
1438 }
1439
1440 processAux(expr, type, offset, sym, addend);
1441}
1442
1443// R_PPC64_TLSGD/R_PPC64_TLSLD is required to mark `bl __tls_get_addr` for
1444// General Dynamic/Local Dynamic code sequences. If a GD/LD GOT relocation is
1445// found but no R_PPC64_TLSGD/R_PPC64_TLSLD is seen, we assume that the
1446// instructions are generated by very old IBM XL compilers. Work around the
1447// issue by disabling GD/LD to IE/LE relaxation.
1448template <class RelTy>
1449static void checkPPC64TLSRelax(InputSectionBase &sec, ArrayRef<RelTy> rels) {
1450 // Skip if sec is synthetic (sec.file is null) or if sec has been marked.
1451 if (!sec.file || sec.file->ppc64DisableTLSRelax)
1452 return;
1453 bool hasGDLD = false;
1454 for (const RelTy &rel : rels) {
1455 RelType type = rel.getType(false);
1456 switch (type) {
1457 case R_PPC64_TLSGD:
1458 case R_PPC64_TLSLD:
1459 return; // Found a marker
1460 case R_PPC64_GOT_TLSGD16:
1461 case R_PPC64_GOT_TLSGD16_HA:
1462 case R_PPC64_GOT_TLSGD16_HI:
1463 case R_PPC64_GOT_TLSGD16_LO:
1464 case R_PPC64_GOT_TLSLD16:
1465 case R_PPC64_GOT_TLSLD16_HA:
1466 case R_PPC64_GOT_TLSLD16_HI:
1467 case R_PPC64_GOT_TLSLD16_LO:
1468 hasGDLD = true;
1469 break;
1470 }
1471 }
1472 if (hasGDLD) {
1473 sec.file->ppc64DisableTLSRelax = true;
1474 warn(toString(sec.file) +
1475 ": disable TLS relaxation due to R_PPC64_GOT_TLS* relocations without "
1476 "R_PPC64_TLSGD/R_PPC64_TLSLD relocations");
1477 }
1478}
1479
1480template <class ELFT, class RelTy>
1481void RelocationScanner::scan(ArrayRef<RelTy> rels) {
1482 // Not all relocations end up in Sec.Relocations, but a lot do.
1483 sec.relocations.reserve(rels.size());
1484
1485 if (config->emachine == EM_PPC64)
1486 checkPPC64TLSRelax<RelTy>(sec, rels);
1487
1488 // For EhInputSection, OffsetGetter expects the relocations to be sorted by
1489 // r_offset. In rare cases (.eh_frame pieces are reordered by a linker
1490 // script), the relocations may be unordered.
1491 SmallVector<RelTy, 0> storage;
1492 if (isa<EhInputSection>(sec))
1493 rels = sortRels(rels, storage);
1494
1495 end = static_cast<const void *>(rels.end());
1496 for (auto i = rels.begin(); i != end;)
1497 scanOne<ELFT>(i);
1498
1499 // Sort relocations by offset for more efficient searching for
1500 // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64.
1501 if (config->emachine == EM_RISCV ||
1502 (config->emachine == EM_PPC64 && sec.name == ".toc"))
1503 llvm::stable_sort(sec.relocations,
1504 [](const Relocation &lhs, const Relocation &rhs) {
1505 return lhs.offset < rhs.offset;
1506 });
1507}
1508
1509template <class ELFT> void elf::scanRelocations(InputSectionBase &s) {
1510 RelocationScanner scanner(s);
1511 const RelsOrRelas<ELFT> rels = s.template relsOrRelas<ELFT>();
1512 if (rels.areRelocsRel())
1513 scanner.template scan<ELFT>(rels.rels);
1514 else
1515 scanner.template scan<ELFT>(rels.relas);
1516}
1517
1518static bool handleNonPreemptibleIfunc(Symbol &sym) {
1519 // Handle a reference to a non-preemptible ifunc. These are special in a
1520 // few ways:
1521 //
1522 // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have
1523 // a fixed value. But assuming that all references to the ifunc are
1524 // GOT-generating or PLT-generating, the handling of an ifunc is
1525 // relatively straightforward. We create a PLT entry in Iplt, which is
1526 // usually at the end of .plt, which makes an indirect call using a
1527 // matching GOT entry in igotPlt, which is usually at the end of .got.plt.
1528 // The GOT entry is relocated using an IRELATIVE relocation in relaIplt,
1529 // which is usually at the end of .rela.plt. Unlike most relocations in
1530 // .rela.plt, which may be evaluated lazily without -z now, dynamic
1531 // loaders evaluate IRELATIVE relocs eagerly, which means that for
1532 // IRELATIVE relocs only, GOT-generating relocations can point directly to
1533 // .got.plt without requiring a separate GOT entry.
1534 //
1535 // - Despite the fact that an ifunc does not have a fixed value, compilers
1536 // that are not passed -fPIC will assume that they do, and will emit
1537 // direct (non-GOT-generating, non-PLT-generating) relocations to the
1538 // symbol. This means that if a direct relocation to the symbol is
1539 // seen, the linker must set a value for the symbol, and this value must
1540 // be consistent no matter what type of reference is made to the symbol.
1541 // This can be done by creating a PLT entry for the symbol in the way
1542 // described above and making it canonical, that is, making all references
1543 // point to the PLT entry instead of the resolver. In lld we also store
1544 // the address of the PLT entry in the dynamic symbol table, which means
1545 // that the symbol will also have the same value in other modules.
1546 // Because the value loaded from the GOT needs to be consistent with
1547 // the value computed using a direct relocation, a non-preemptible ifunc
1548 // may end up with two GOT entries, one in .got.plt that points to the
1549 // address returned by the resolver and is used only by the PLT entry,
1550 // and another in .got that points to the PLT entry and is used by
1551 // GOT-generating relocations.
1552 //
1553 // - The fact that these symbols do not have a fixed value makes them an
1554 // exception to the general rule that a statically linked executable does
1555 // not require any form of dynamic relocation. To handle these relocations
1556 // correctly, the IRELATIVE relocations are stored in an array which a
1557 // statically linked executable's startup code must enumerate using the
1558 // linker-defined symbols __rela?_iplt_{start,end}.
1559 if (!sym.isGnuIFunc() || sym.isPreemptible || config->zIfuncNoplt)
1560 return false;
1561 // Skip unreferenced non-preemptible ifunc.
1562 if (!(sym.needsGot || sym.needsPlt || sym.hasDirectReloc))
1563 return true;
1564
1565 sym.isInIplt = true;
1566
1567 // Create an Iplt and the associated IRELATIVE relocation pointing to the
1568 // original section/value pairs. For non-GOT non-PLT relocation case below, we
1569 // may alter section/value, so create a copy of the symbol to make
1570 // section/value fixed.
1571 auto *directSym = makeDefined(cast<Defined>(sym));
1572 directSym->allocateAux();
1573 addPltEntry(*in.iplt, *in.igotPlt, *in.relaIplt, target->iRelativeRel,
1574 *directSym);
1575 sym.allocateAux();
1576 symAux.back().pltIdx = symAux[directSym->auxIdx].pltIdx;
1577
1578 if (sym.hasDirectReloc) {
1579 // Change the value to the IPLT and redirect all references to it.
1580 auto &d = cast<Defined>(sym);
1581 d.section = in.iplt.get();
1582 d.value = d.getPltIdx() * target->ipltEntrySize;
1583 d.size = 0;
1584 // It's important to set the symbol type here so that dynamic loaders
1585 // don't try to call the PLT as if it were an ifunc resolver.
1586 d.type = STT_FUNC;
1587
1588 if (sym.needsGot)
1589 addGotEntry(sym);
1590 } else if (sym.needsGot) {
1591 // Redirect GOT accesses to point to the Igot.
1592 sym.gotInIgot = true;
1593 }
1594 return true;
1595}
1596
1597void elf::postScanRelocations() {
1598 auto fn = [](Symbol &sym) {
1599 if (handleNonPreemptibleIfunc(sym))
1600 return;
1601 if (!sym.needsDynReloc())
1602 return;
1603 sym.allocateAux();
1604
1605 if (sym.needsGot)
1606 addGotEntry(sym);
1607 if (sym.needsPlt)
1608 addPltEntry(*in.plt, *in.gotPlt, *in.relaPlt, target->pltRel, sym);
1609 if (sym.needsCopy) {
1610 if (sym.isObject()) {
1611 addCopyRelSymbol(cast<SharedSymbol>(sym));
1612 // needsCopy is cleared for sym and its aliases so that in later
1613 // iterations aliases won't cause redundant copies.
1614 assert(!sym.needsCopy)(static_cast <bool> (!sym.needsCopy) ? void (0) : __assert_fail
("!sym.needsCopy", "lld/ELF/Relocations.cpp", 1614, __extension__
__PRETTY_FUNCTION__))
;
1615 } else {
1616 assert(sym.isFunc() && sym.needsPlt)(static_cast <bool> (sym.isFunc() && sym.needsPlt
) ? void (0) : __assert_fail ("sym.isFunc() && sym.needsPlt"
, "lld/ELF/Relocations.cpp", 1616, __extension__ __PRETTY_FUNCTION__
))
;
1617 if (!sym.isDefined()) {
1618 replaceWithDefined(sym, *in.plt,
1619 target->pltHeaderSize +
1620 target->pltEntrySize * sym.getPltIdx(),
1621 0);
1622 sym.needsCopy = true;
1623 if (config->emachine == EM_PPC) {
1624 // PPC32 canonical PLT entries are at the beginning of .glink
1625 cast<Defined>(sym).value = in.plt->headerSize;
1626 in.plt->headerSize += 16;
1627 cast<PPC32GlinkSection>(*in.plt).canonical_plts.push_back(&sym);
1628 }
1629 }
1630 }
1631 }
1632
1633 if (!sym.isTls())
1634 return;
1635 bool isLocalInExecutable = !sym.isPreemptible && !config->shared;
1636
1637 if (sym.needsTlsDesc) {
1638 in.got->addTlsDescEntry(sym);
1639 mainPart->relaDyn->addAddendOnlyRelocIfNonPreemptible(
1640 target->tlsDescRel, *in.got, in.got->getTlsDescOffset(sym), sym,
1641 target->tlsDescRel);
1642 }
1643 if (sym.needsTlsGd) {
1644 in.got->addDynTlsEntry(sym);
1645 uint64_t off = in.got->getGlobalDynOffset(sym);
1646 if (isLocalInExecutable)
1647 // Write one to the GOT slot.
1648 in.got->relocations.push_back(
1649 {R_ADDEND, target->symbolicRel, off, 1, &sym});
1650 else
1651 mainPart->relaDyn->addSymbolReloc(target->tlsModuleIndexRel, *in.got,
1652 off, sym);
1653
1654 // If the symbol is preemptible we need the dynamic linker to write
1655 // the offset too.
1656 uint64_t offsetOff = off + config->wordsize;
1657 if (sym.isPreemptible)
1658 mainPart->relaDyn->addSymbolReloc(target->tlsOffsetRel, *in.got,
1659 offsetOff, sym);
1660 else
1661 in.got->relocations.push_back(
1662 {R_ABS, target->tlsOffsetRel, offsetOff, 0, &sym});
1663 }
1664 if (sym.needsTlsGdToIe) {
1665 in.got->addEntry(sym);
1666 mainPart->relaDyn->addSymbolReloc(target->tlsGotRel, *in.got,
1667 sym.getGotOffset(), sym);
1668 }
1669
1670 if (sym.needsTlsLd && in.got->addTlsIndex()) {
1671 if (isLocalInExecutable)
1672 in.got->relocations.push_back(
1673 {R_ADDEND, target->symbolicRel, in.got->getTlsIndexOff(), 1, &sym});
1674 else
1675 mainPart->relaDyn->addReloc({target->tlsModuleIndexRel, in.got.get(),
1676 in.got->getTlsIndexOff()});
1677 }
1678 if (sym.needsGotDtprel) {
1679 in.got->addEntry(sym);
1680 in.got->relocations.push_back(
1681 {R_ABS, target->tlsOffsetRel, sym.getGotOffset(), 0, &sym});
1682 }
1683
1684 if (sym.needsTlsIe && !sym.needsTlsGdToIe)
1685 addTpOffsetGotEntry(sym);
1686 };
1687
1688 assert(symAux.empty())(static_cast <bool> (symAux.empty()) ? void (0) : __assert_fail
("symAux.empty()", "lld/ELF/Relocations.cpp", 1688, __extension__
__PRETTY_FUNCTION__))
;
1689 for (Symbol *sym : symtab->symbols())
1690 fn(*sym);
1691
1692 // Local symbols may need the aforementioned non-preemptible ifunc and GOT
1693 // handling. They don't need regular PLT.
1694 for (ELFFileBase *file : objectFiles)
1695 for (Symbol *sym : file->getLocalSymbols())
1696 fn(*sym);
1697}
1698
1699static bool mergeCmp(const InputSection *a, const InputSection *b) {
1700 // std::merge requires a strict weak ordering.
1701 if (a->outSecOff < b->outSecOff)
1702 return true;
1703
1704 if (a->outSecOff == b->outSecOff) {
1705 auto *ta = dyn_cast<ThunkSection>(a);
1706 auto *tb = dyn_cast<ThunkSection>(b);
1707
1708 // Check if Thunk is immediately before any specific Target
1709 // InputSection for example Mips LA25 Thunks.
1710 if (ta && ta->getTargetInputSection() == b)
1711 return true;
1712
1713 // Place Thunk Sections without specific targets before
1714 // non-Thunk Sections.
1715 if (ta && !tb && !ta->getTargetInputSection())
1716 return true;
1717 }
1718
1719 return false;
1720}
1721
1722// Call Fn on every executable InputSection accessed via the linker script
1723// InputSectionDescription::Sections.
1724static void forEachInputSectionDescription(
1725 ArrayRef<OutputSection *> outputSections,
1726 llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) {
1727 for (OutputSection *os : outputSections) {
1728 if (!(os->flags & SHF_ALLOC) || !(os->flags & SHF_EXECINSTR))
1729 continue;
1730 for (SectionCommand *bc : os->commands)
1731 if (auto *isd = dyn_cast<InputSectionDescription>(bc))
1732 fn(os, isd);
1733 }
1734}
1735
1736// Thunk Implementation
1737//
1738// Thunks (sometimes called stubs, veneers or branch islands) are small pieces
1739// of code that the linker inserts inbetween a caller and a callee. The thunks
1740// are added at link time rather than compile time as the decision on whether
1741// a thunk is needed, such as the caller and callee being out of range, can only
1742// be made at link time.
1743//
1744// It is straightforward to tell given the current state of the program when a
1745// thunk is needed for a particular call. The more difficult part is that
1746// the thunk needs to be placed in the program such that the caller can reach
1747// the thunk and the thunk can reach the callee; furthermore, adding thunks to
1748// the program alters addresses, which can mean more thunks etc.
1749//
1750// In lld we have a synthetic ThunkSection that can hold many Thunks.
1751// The decision to have a ThunkSection act as a container means that we can
1752// more easily handle the most common case of a single block of contiguous
1753// Thunks by inserting just a single ThunkSection.
1754//
1755// The implementation of Thunks in lld is split across these areas
1756// Relocations.cpp : Framework for creating and placing thunks
1757// Thunks.cpp : The code generated for each supported thunk
1758// Target.cpp : Target specific hooks that the framework uses to decide when
1759// a thunk is used
1760// Synthetic.cpp : Implementation of ThunkSection
1761// Writer.cpp : Iteratively call framework until no more Thunks added
1762//
1763// Thunk placement requirements:
1764// Mips LA25 thunks. These must be placed immediately before the callee section
1765// We can assume that the caller is in range of the Thunk. These are modelled
1766// by Thunks that return the section they must precede with
1767// getTargetInputSection().
1768//
1769// ARM interworking and range extension thunks. These thunks must be placed
1770// within range of the caller. All implemented ARM thunks can always reach the
1771// callee as they use an indirect jump via a register that has no range
1772// restrictions.
1773//
1774// Thunk placement algorithm:
1775// For Mips LA25 ThunkSections; the placement is explicit, it has to be before
1776// getTargetInputSection().
1777//
1778// For thunks that must be placed within range of the caller there are many
1779// possible choices given that the maximum range from the caller is usually
1780// much larger than the average InputSection size. Desirable properties include:
1781// - Maximize reuse of thunks by multiple callers
1782// - Minimize number of ThunkSections to simplify insertion
1783// - Handle impact of already added Thunks on addresses
1784// - Simple to understand and implement
1785//
1786// In lld for the first pass, we pre-create one or more ThunkSections per
1787// InputSectionDescription at Target specific intervals. A ThunkSection is
1788// placed so that the estimated end of the ThunkSection is within range of the
1789// start of the InputSectionDescription or the previous ThunkSection. For
1790// example:
1791// InputSectionDescription
1792// Section 0
1793// ...
1794// Section N
1795// ThunkSection 0
1796// Section N + 1
1797// ...
1798// Section N + K
1799// Thunk Section 1
1800//
1801// The intention is that we can add a Thunk to a ThunkSection that is well
1802// spaced enough to service a number of callers without having to do a lot
1803// of work. An important principle is that it is not an error if a Thunk cannot
1804// be placed in a pre-created ThunkSection; when this happens we create a new
1805// ThunkSection placed next to the caller. This allows us to handle the vast
1806// majority of thunks simply, but also handle rare cases where the branch range
1807// is smaller than the target specific spacing.
1808//
1809// The algorithm is expected to create all the thunks that are needed in a
1810// single pass, with a small number of programs needing a second pass due to
1811// the insertion of thunks in the first pass increasing the offset between
1812// callers and callees that were only just in range.
1813//
1814// A consequence of allowing new ThunkSections to be created outside of the
1815// pre-created ThunkSections is that in rare cases calls to Thunks that were in
1816// range in pass K, are out of range in some pass > K due to the insertion of
1817// more Thunks in between the caller and callee. When this happens we retarget
1818// the relocation back to the original target and create another Thunk.
1819
1820// Remove ThunkSections that are empty, this should only be the initial set
1821// precreated on pass 0.
1822
1823// Insert the Thunks for OutputSection OS into their designated place
1824// in the Sections vector, and recalculate the InputSection output section
1825// offsets.
1826// This may invalidate any output section offsets stored outside of InputSection
1827void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) {
1828 forEachInputSectionDescription(
1829 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
1830 if (isd->thunkSections.empty())
1831 return;
1832
1833 // Remove any zero sized precreated Thunks.
1834 llvm::erase_if(isd->thunkSections,
1835 [](const std::pair<ThunkSection *, uint32_t> &ts) {
1836 return ts.first->getSize() == 0;
1837 });
1838
1839 // ISD->ThunkSections contains all created ThunkSections, including
1840 // those inserted in previous passes. Extract the Thunks created this
1841 // pass and order them in ascending outSecOff.
1842 std::vector<ThunkSection *> newThunks;
1843 for (std::pair<ThunkSection *, uint32_t> ts : isd->thunkSections)
1844 if (ts.second == pass)
1845 newThunks.push_back(ts.first);
1846 llvm::stable_sort(newThunks,
1847 [](const ThunkSection *a, const ThunkSection *b) {
1848 return a->outSecOff < b->outSecOff;
1849 });
1850
1851 // Merge sorted vectors of Thunks and InputSections by outSecOff
1852 SmallVector<InputSection *, 0> tmp;
1853 tmp.reserve(isd->sections.size() + newThunks.size());
1854
1855 std::merge(isd->sections.begin(), isd->sections.end(),
1856 newThunks.begin(), newThunks.end(), std::back_inserter(tmp),
1857 mergeCmp);
1858
1859 isd->sections = std::move(tmp);
1860 });
1861}
1862
1863// Find or create a ThunkSection within the InputSectionDescription (ISD) that
1864// is in range of Src. An ISD maps to a range of InputSections described by a
1865// linker script section pattern such as { .text .text.* }.
1866ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os,
1867 InputSection *isec,
1868 InputSectionDescription *isd,
1869 const Relocation &rel,
1870 uint64_t src) {
1871 for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) {
1872 ThunkSection *ts = tp.first;
1873 uint64_t tsBase = os->addr + ts->outSecOff + rel.addend;
1874 uint64_t tsLimit = tsBase + ts->getSize() + rel.addend;
1875 if (target->inBranchRange(rel.type, src,
1876 (src > tsLimit) ? tsBase : tsLimit))
1877 return ts;
1878 }
1879
1880 // No suitable ThunkSection exists. This can happen when there is a branch
1881 // with lower range than the ThunkSection spacing or when there are too
1882 // many Thunks. Create a new ThunkSection as close to the InputSection as
1883 // possible. Error if InputSection is so large we cannot place ThunkSection
1884 // anywhere in Range.
1885 uint64_t thunkSecOff = isec->outSecOff;
1886 if (!target->inBranchRange(rel.type, src,
1887 os->addr + thunkSecOff + rel.addend)) {
1888 thunkSecOff = isec->outSecOff + isec->getSize();
1889 if (!target->inBranchRange(rel.type, src,
1890 os->addr + thunkSecOff + rel.addend))
1891 fatal("InputSection too large for range extension thunk " +
1892 isec->getObjMsg(src - (os->addr + isec->outSecOff)));
1893 }
1894 return addThunkSection(os, isd, thunkSecOff);
1895}
1896
1897// Add a Thunk that needs to be placed in a ThunkSection that immediately
1898// precedes its Target.
1899ThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) {
1900 ThunkSection *ts = thunkedSections.lookup(isec);
1901 if (ts)
1902 return ts;
1903
1904 // Find InputSectionRange within Target Output Section (TOS) that the
1905 // InputSection (IS) that we need to precede is in.
1906 OutputSection *tos = isec->getParent();
1907 for (SectionCommand *bc : tos->commands) {
1908 auto *isd = dyn_cast<InputSectionDescription>(bc);
1909 if (!isd || isd->sections.empty())
1910 continue;
1911
1912 InputSection *first = isd->sections.front();
1913 InputSection *last = isd->sections.back();
1914
1915 if (isec->outSecOff < first->outSecOff || last->outSecOff < isec->outSecOff)
1916 continue;
1917
1918 ts = addThunkSection(tos, isd, isec->outSecOff);
1919 thunkedSections[isec] = ts;
1920 return ts;
1921 }
1922
1923 return nullptr;
1924}
1925
1926// Create one or more ThunkSections per OS that can be used to place Thunks.
1927// We attempt to place the ThunkSections using the following desirable
1928// properties:
1929// - Within range of the maximum number of callers
1930// - Minimise the number of ThunkSections
1931//
1932// We follow a simple but conservative heuristic to place ThunkSections at
1933// offsets that are multiples of a Target specific branch range.
1934// For an InputSectionDescription that is smaller than the range, a single
1935// ThunkSection at the end of the range will do.
1936//
1937// For an InputSectionDescription that is more than twice the size of the range,
1938// we place the last ThunkSection at range bytes from the end of the
1939// InputSectionDescription in order to increase the likelihood that the
1940// distance from a thunk to its target will be sufficiently small to
1941// allow for the creation of a short thunk.
1942void ThunkCreator::createInitialThunkSections(
1943 ArrayRef<OutputSection *> outputSections) {
1944 uint32_t thunkSectionSpacing = target->getThunkSectionSpacing();
1945
1946 forEachInputSectionDescription(
1947 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
1948 if (isd->sections.empty())
1
Calling 'SmallVectorBase::empty'
4
Returning from 'SmallVectorBase::empty'
5
Taking false branch
1949 return;
1950
1951 uint32_t isdBegin = isd->sections.front()->outSecOff;
1952 uint32_t isdEnd =
1953 isd->sections.back()->outSecOff + isd->sections.back()->getSize();
1954 uint32_t lastThunkLowerBound = -1;
1955 if (isdEnd - isdBegin > thunkSectionSpacing * 2)
6
Assuming the condition is false
7
Taking false branch
1956 lastThunkLowerBound = isdEnd - thunkSectionSpacing;
1957
1958 uint32_t isecLimit;
8
'isecLimit' declared without an initial value
1959 uint32_t prevIsecLimit = isdBegin;
1960 uint32_t thunkUpperBound = isdBegin + thunkSectionSpacing;
1961
1962 for (const InputSection *isec : isd->sections) {
9
Assuming '__begin1' is equal to '__end1'
1963 isecLimit = isec->outSecOff + isec->getSize();
1964 if (isecLimit > thunkUpperBound) {
1965 addThunkSection(os, isd, prevIsecLimit);
1966 thunkUpperBound = prevIsecLimit + thunkSectionSpacing;
1967 }
1968 if (isecLimit > lastThunkLowerBound)
1969 break;
1970 prevIsecLimit = isecLimit;
1971 }
1972 addThunkSection(os, isd, isecLimit);
10
3rd function call argument is an uninitialized value
1973 });
1974}
1975
1976ThunkSection *ThunkCreator::addThunkSection(OutputSection *os,
1977 InputSectionDescription *isd,
1978 uint64_t off) {
1979 auto *ts = make<ThunkSection>(os, off);
1980 ts->partition = os->partition;
1981 if ((config->fixCortexA53Errata843419 || config->fixCortexA8) &&
1982 !isd->sections.empty()) {
1983 // The errata fixes are sensitive to addresses modulo 4 KiB. When we add
1984 // thunks we disturb the base addresses of sections placed after the thunks
1985 // this makes patches we have generated redundant, and may cause us to
1986 // generate more patches as different instructions are now in sensitive
1987 // locations. When we generate more patches we may force more branches to
1988 // go out of range, causing more thunks to be generated. In pathological
1989 // cases this can cause the address dependent content pass not to converge.
1990 // We fix this by rounding up the size of the ThunkSection to 4KiB, this
1991 // limits the insertion of a ThunkSection on the addresses modulo 4 KiB,
1992 // which means that adding Thunks to the section does not invalidate
1993 // errata patches for following code.
1994 // Rounding up the size to 4KiB has consequences for code-size and can
1995 // trip up linker script defined assertions. For example the linux kernel
1996 // has an assertion that what LLD represents as an InputSectionDescription
1997 // does not exceed 4 KiB even if the overall OutputSection is > 128 Mib.
1998 // We use the heuristic of rounding up the size when both of the following
1999 // conditions are true:
2000 // 1.) The OutputSection is larger than the ThunkSectionSpacing. This
2001 // accounts for the case where no single InputSectionDescription is
2002 // larger than the OutputSection size. This is conservative but simple.
2003 // 2.) The InputSectionDescription is larger than 4 KiB. This will prevent
2004 // any assertion failures that an InputSectionDescription is < 4 KiB
2005 // in size.
2006 uint64_t isdSize = isd->sections.back()->outSecOff +
2007 isd->sections.back()->getSize() -
2008 isd->sections.front()->outSecOff;
2009 if (os->size > target->getThunkSectionSpacing() && isdSize > 4096)
2010 ts->roundUpSizeForErrata = true;
2011 }
2012 isd->thunkSections.push_back({ts, pass});
2013 return ts;
2014}
2015
2016static bool isThunkSectionCompatible(InputSection *source,
2017 SectionBase *target) {
2018 // We can't reuse thunks in different loadable partitions because they might
2019 // not be loaded. But partition 1 (the main partition) will always be loaded.
2020 if (source->partition != target->partition)
2021 return target->partition == 1;
2022 return true;
2023}
2024
2025static int64_t getPCBias(RelType type) {
2026 if (config->emachine != EM_ARM)
2027 return 0;
2028 switch (type) {
2029 case R_ARM_THM_JUMP19:
2030 case R_ARM_THM_JUMP24:
2031 case R_ARM_THM_CALL:
2032 return 4;
2033 default:
2034 return 8;
2035 }
2036}
2037
2038std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
2039 Relocation &rel, uint64_t src) {
2040 std::vector<Thunk *> *thunkVec = nullptr;
2041 // Arm and Thumb have a PC Bias of 8 and 4 respectively, this is cancelled
2042 // out in the relocation addend. We compensate for the PC bias so that
2043 // an Arm and Thumb relocation to the same destination get the same keyAddend,
2044 // which is usually 0.
2045 int64_t keyAddend = rel.addend + getPCBias(rel.type);
2046
2047 // We use a ((section, offset), addend) pair to find the thunk position if
2048 // possible so that we create only one thunk for aliased symbols or ICFed
2049 // sections. There may be multiple relocations sharing the same (section,
2050 // offset + addend) pair. We may revert the relocation back to its original
2051 // non-Thunk target, so we cannot fold offset + addend.
2052 if (auto *d = dyn_cast<Defined>(rel.sym))
2053 if (!d->isInPlt() && d->section)
2054 thunkVec = &thunkedSymbolsBySectionAndAddend[{{d->section, d->value},
2055 keyAddend}];
2056 if (!thunkVec)
2057 thunkVec = &thunkedSymbols[{rel.sym, keyAddend}];
2058
2059 // Check existing Thunks for Sym to see if they can be reused
2060 for (Thunk *t : *thunkVec)
2061 if (isThunkSectionCompatible(isec, t->getThunkTargetSym()->section) &&
2062 t->isCompatibleWith(*isec, rel) &&
2063 target->inBranchRange(rel.type, src,
2064 t->getThunkTargetSym()->getVA(rel.addend)))
2065 return std::make_pair(t, false);
2066
2067 // No existing compatible Thunk in range, create a new one
2068 Thunk *t = addThunk(*isec, rel);
2069 thunkVec->push_back(t);
2070 return std::make_pair(t, true);
2071}
2072
2073// Return true if the relocation target is an in range Thunk.
2074// Return false if the relocation is not to a Thunk. If the relocation target
2075// was originally to a Thunk, but is no longer in range we revert the
2076// relocation back to its original non-Thunk target.
2077bool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) {
2078 if (Thunk *t = thunks.lookup(rel.sym)) {
2079 if (target->inBranchRange(rel.type, src, rel.sym->getVA(rel.addend)))
2080 return true;
2081 rel.sym = &t->destination;
2082 rel.addend = t->addend;
2083 if (rel.sym->isInPlt())
2084 rel.expr = toPlt(rel.expr);
2085 }
2086 return false;
2087}
2088
2089// Process all relocations from the InputSections that have been assigned
2090// to InputSectionDescriptions and redirect through Thunks if needed. The
2091// function should be called iteratively until it returns false.
2092//
2093// PreConditions:
2094// All InputSections that may need a Thunk are reachable from
2095// OutputSectionCommands.
2096//
2097// All OutputSections have an address and all InputSections have an offset
2098// within the OutputSection.
2099//
2100// The offsets between caller (relocation place) and callee
2101// (relocation target) will not be modified outside of createThunks().
2102//
2103// PostConditions:
2104// If return value is true then ThunkSections have been inserted into
2105// OutputSections. All relocations that needed a Thunk based on the information
2106// available to createThunks() on entry have been redirected to a Thunk. Note
2107// that adding Thunks changes offsets between caller and callee so more Thunks
2108// may be required.
2109//
2110// If return value is false then no more Thunks are needed, and createThunks has
2111// made no changes. If the target requires range extension thunks, currently
2112// ARM, then any future change in offset between caller and callee risks a
2113// relocation out of range error.
2114bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) {
2115 bool addressesChanged = false;
2116
2117 if (pass == 0 && target->getThunkSectionSpacing())
2118 createInitialThunkSections(outputSections);
2119
2120 // Create all the Thunks and insert them into synthetic ThunkSections. The
2121 // ThunkSections are later inserted back into InputSectionDescriptions.
2122 // We separate the creation of ThunkSections from the insertion of the
2123 // ThunkSections as ThunkSections are not always inserted into the same
2124 // InputSectionDescription as the caller.
2125 forEachInputSectionDescription(
2126 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
2127 for (InputSection *isec : isd->sections)
2128 for (Relocation &rel : isec->relocations) {
2129 uint64_t src = isec->getVA(rel.offset);
2130
2131 // If we are a relocation to an existing Thunk, check if it is
2132 // still in range. If not then Rel will be altered to point to its
2133 // original target so another Thunk can be generated.
2134 if (pass > 0 && normalizeExistingThunk(rel, src))
2135 continue;
2136
2137 if (!target->needsThunk(rel.expr, rel.type, isec->file, src,
2138 *rel.sym, rel.addend))
2139 continue;
2140
2141 Thunk *t;
2142 bool isNew;
2143 std::tie(t, isNew) = getThunk(isec, rel, src);
2144
2145 if (isNew) {
2146 // Find or create a ThunkSection for the new Thunk
2147 ThunkSection *ts;
2148 if (auto *tis = t->getTargetInputSection())
2149 ts = getISThunkSec(tis);
2150 else
2151 ts = getISDThunkSec(os, isec, isd, rel, src);
2152 ts->addThunk(t);
2153 thunks[t->getThunkTargetSym()] = t;
2154 }
2155
2156 // Redirect relocation to Thunk, we never go via the PLT to a Thunk
2157 rel.sym = t->getThunkTargetSym();
2158 rel.expr = fromPlt(rel.expr);
2159
2160 // On AArch64 and PPC, a jump/call relocation may be encoded as
2161 // STT_SECTION + non-zero addend, clear the addend after
2162 // redirection.
2163 if (config->emachine != EM_MIPS)
2164 rel.addend = -getPCBias(rel.type);
2165 }
2166
2167 for (auto &p : isd->thunkSections)
2168 addressesChanged |= p.first->assignOffsets();
2169 });
2170
2171 for (auto &p : thunkedSections)
2172 addressesChanged |= p.second->assignOffsets();
2173
2174 // Merge all created synthetic ThunkSections back into OutputSection
2175 mergeThunks(outputSections);
2176 ++pass;
2177 return addressesChanged;
2178}
2179
2180// The following aid in the conversion of call x@GDPLT to call __tls_get_addr
2181// hexagonNeedsTLSSymbol scans for relocations would require a call to
2182// __tls_get_addr.
2183// hexagonTLSSymbolUpdate rebinds the relocation to __tls_get_addr.
2184bool elf::hexagonNeedsTLSSymbol(ArrayRef<OutputSection *> outputSections) {
2185 bool needTlsSymbol = false;
2186 forEachInputSectionDescription(
2187 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
2188 for (InputSection *isec : isd->sections)
2189 for (Relocation &rel : isec->relocations)
2190 if (rel.sym->type == llvm::ELF::STT_TLS && rel.expr == R_PLT_PC) {
2191 needTlsSymbol = true;
2192 return;
2193 }
2194 });
2195 return needTlsSymbol;
2196}
2197
2198void elf::hexagonTLSSymbolUpdate(ArrayRef<OutputSection *> outputSections) {
2199 Symbol *sym = symtab->find("__tls_get_addr");
2200 if (!sym)
2201 return;
2202 bool needEntry = true;
2203 forEachInputSectionDescription(
2204 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
2205 for (InputSection *isec : isd->sections)
2206 for (Relocation &rel : isec->relocations)
2207 if (rel.sym->type == llvm::ELF::STT_TLS && rel.expr == R_PLT_PC) {
2208 if (needEntry) {
2209 sym->allocateAux();
2210 addPltEntry(*in.plt, *in.gotPlt, *in.relaPlt, target->pltRel,
2211 *sym);
2212 needEntry = false;
2213 }
2214 rel.sym = sym;
2215 }
2216 });
2217}
2218
2219template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
2220template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
2221template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
2222template void elf::scanRelocations<ELF64BE>(InputSectionBase &);
2223template void elf::reportUndefinedSymbols<ELF32LE>();
2224template void elf::reportUndefinedSymbols<ELF32BE>();
2225template void elf::reportUndefinedSymbols<ELF64LE>();
2226template void elf::reportUndefinedSymbols<ELF64BE>();

/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/MemAlloc.h"
20#include "llvm/Support/type_traits.h"
21#include <algorithm>
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25#include <cstring>
26#include <functional>
27#include <initializer_list>
28#include <iterator>
29#include <limits>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
47 void *BeginX;
48 Size_T Size = 0, Capacity;
49
50 /// The maximum value of the Size_T used.
51 static constexpr size_t SizeTypeMax() {
52 return std::numeric_limits<Size_T>::max();
53 }
54
55 SmallVectorBase() = delete;
56 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57 : BeginX(FirstEl), Capacity(TotalCapacity) {}
58
59 /// This is a helper for \a grow() that's out of line to reduce code
60 /// duplication. This function will report a fatal error if it can't grow at
61 /// least to \p MinSize.
62 void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
63
64 /// This is an implementation of the grow() method which only works
65 /// on POD-like data types and is out of line to reduce code duplication.
66 /// This function will report a fatal error if it cannot increase capacity.
67 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
68
69public:
70 size_t size() const { return Size; }
71 size_t capacity() const { return Capacity; }
72
73 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
2
Assuming field 'Size' is not equal to 0, which participates in a condition later
3
Returning zero, which participates in a condition later
74
75protected:
76 /// Set the array size to \p N, which the current array must have enough
77 /// capacity for.
78 ///
79 /// This does not construct or destroy any elements in the vector.
80 void set_size(size_t N) {
81 assert(N <= capacity())(static_cast <bool> (N <= capacity()) ? void (0) : __assert_fail
("N <= capacity()", "llvm/include/llvm/ADT/SmallVector.h"
, 81, __extension__ __PRETTY_FUNCTION__))
;
82 Size = N;
83 }
84};
85
86template <class T>
87using SmallVectorSizeType =
88 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
89 uint32_t>::type;
90
91/// Figure out the offset of the first element.
92template <class T, typename = void> struct SmallVectorAlignmentAndSize {
93 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
94 SmallVectorBase<SmallVectorSizeType<T>>)];
95 alignas(T) char FirstEl[sizeof(T)];
96};
97
98/// This is the part of SmallVectorTemplateBase which does not depend on whether
99/// the type T is a POD. The extra dummy template argument is used by ArrayRef
100/// to avoid unnecessarily requiring T to be complete.
101template <typename T, typename = void>
102class SmallVectorTemplateCommon
103 : public SmallVectorBase<SmallVectorSizeType<T>> {
104 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
105
106 /// Find the address of the first element. For this pointer math to be valid
107 /// with small-size of 0 for T with lots of alignment, it's important that
108 /// SmallVectorStorage is properly-aligned even for small-size of 0.
109 void *getFirstEl() const {
110 return const_cast<void *>(reinterpret_cast<const void *>(
111 reinterpret_cast<const char *>(this) +
112 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
113 }
114 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
115
116protected:
117 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
118
119 void grow_pod(size_t MinSize, size_t TSize) {
120 Base::grow_pod(getFirstEl(), MinSize, TSize);
121 }
122
123 /// Return true if this is a smallvector which has not had dynamic
124 /// memory allocated for it.
125 bool isSmall() const { return this->BeginX == getFirstEl(); }
126
127 /// Put this vector in a state of being small.
128 void resetToSmall() {
129 this->BeginX = getFirstEl();
130 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
131 }
132
133 /// Return true if V is an internal reference to the given range.
134 bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
135 // Use std::less to avoid UB.
136 std::less<> LessThan;
137 return !LessThan(V, First) && LessThan(V, Last);
138 }
139
140 /// Return true if V is an internal reference to this vector.
141 bool isReferenceToStorage(const void *V) const {
142 return isReferenceToRange(V, this->begin(), this->end());
143 }
144
145 /// Return true if First and Last form a valid (possibly empty) range in this
146 /// vector's storage.
147 bool isRangeInStorage(const void *First, const void *Last) const {
148 // Use std::less to avoid UB.
149 std::less<> LessThan;
150 return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
151 !LessThan(this->end(), Last);
152 }
153
154 /// Return true unless Elt will be invalidated by resizing the vector to
155 /// NewSize.
156 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
157 // Past the end.
158 if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
159 return true;
160
161 // Return false if Elt will be destroyed by shrinking.
162 if (NewSize <= this->size())
163 return Elt < this->begin() + NewSize;
164
165 // Return false if we need to grow.
166 return NewSize <= this->capacity();
167 }
168
169 /// Check whether Elt will be invalidated by resizing the vector to NewSize.
170 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
171 assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
))
172 "Attempting to reference an element of the vector in an operation "(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
))
173 "that invalidates it")(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
))
;
174 }
175
176 /// Check whether Elt will be invalidated by increasing the size of the
177 /// vector by N.
178 void assertSafeToAdd(const void *Elt, size_t N = 1) {
179 this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
180 }
181
182 /// Check whether any part of the range will be invalidated by clearing.
183 void assertSafeToReferenceAfterClear(const T *From, const T *To) {
184 if (From == To)
185 return;
186 this->assertSafeToReferenceAfterResize(From, 0);
187 this->assertSafeToReferenceAfterResize(To - 1, 0);
188 }
189 template <
190 class ItTy,
191 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
192 bool> = false>
193 void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
194
195 /// Check whether any part of the range will be invalidated by growing.
196 void assertSafeToAddRange(const T *From, const T *To) {
197 if (From == To)
198 return;
199 this->assertSafeToAdd(From, To - From);
200 this->assertSafeToAdd(To - 1, To - From);
201 }
202 template <
203 class ItTy,
204 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
205 bool> = false>
206 void assertSafeToAddRange(ItTy, ItTy) {}
207
208 /// Reserve enough space to add one element, and return the updated element
209 /// pointer in case it was a reference to the storage.
210 template <class U>
211 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
212 size_t N) {
213 size_t NewSize = This->size() + N;
214 if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
)
)
215 return &Elt;
216
217 bool ReferencesStorage = false;
218 int64_t Index = -1;
219 if (!U::TakesParamByValue) {
220 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)
) {
221 ReferencesStorage = true;
222 Index = &Elt - This->begin();
223 }
224 }
225 This->grow(NewSize);
226 return ReferencesStorage ? This->begin() + Index : &Elt;
227 }
228
229public:
230 using size_type = size_t;
231 using difference_type = ptrdiff_t;
232 using value_type = T;
233 using iterator = T *;
234 using const_iterator = const T *;
235
236 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
237 using reverse_iterator = std::reverse_iterator<iterator>;
238
239 using reference = T &;
240 using const_reference = const T &;
241 using pointer = T *;
242 using const_pointer = const T *;
243
244 using Base::capacity;
245 using Base::empty;
246 using Base::size;
247
248 // forward iterator creation methods.
249 iterator begin() { return (iterator)this->BeginX; }
250 const_iterator begin() const { return (const_iterator)this->BeginX; }
251 iterator end() { return begin() + size(); }
252 const_iterator end() const { return begin() + size(); }
253
254 // reverse iterator creation methods.
255 reverse_iterator rbegin() { return reverse_iterator(end()); }
256 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
257 reverse_iterator rend() { return reverse_iterator(begin()); }
258 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
259
260 size_type size_in_bytes() const { return size() * sizeof(T); }
261 size_type max_size() const {
262 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
263 }
264
265 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
266
267 /// Return a pointer to the vector's buffer, even if empty().
268 pointer data() { return pointer(begin()); }
269 /// Return a pointer to the vector's buffer, even if empty().
270 const_pointer data() const { return const_pointer(begin()); }
271
272 reference operator[](size_type idx) {
273 assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
("idx < size()", "llvm/include/llvm/ADT/SmallVector.h", 273
, __extension__ __PRETTY_FUNCTION__))
;
274 return begin()[idx];
275 }
276 const_reference operator[](size_type idx) const {
277 assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
("idx < size()", "llvm/include/llvm/ADT/SmallVector.h", 277
, __extension__ __PRETTY_FUNCTION__))
;
278 return begin()[idx];
279 }
280
281 reference front() {
282 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 282, __extension__
__PRETTY_FUNCTION__))
;
283 return begin()[0];
284 }
285 const_reference front() const {
286 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 286, __extension__
__PRETTY_FUNCTION__))
;
287 return begin()[0];
288 }
289
290 reference back() {
291 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 291, __extension__
__PRETTY_FUNCTION__))
;
292 return end()[-1];
293 }
294 const_reference back() const {
295 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 295, __extension__
__PRETTY_FUNCTION__))
;
296 return end()[-1];
297 }
298};
299
300/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
301/// method implementations that are designed to work with non-trivial T's.
302///
303/// We approximate is_trivially_copyable with trivial move/copy construction and
304/// trivial destruction. While the standard doesn't specify that you're allowed
305/// copy these types with memcpy, there is no way for the type to observe this.
306/// This catches the important case of std::pair<POD, POD>, which is not
307/// trivially assignable.
308template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
309 (is_trivially_move_constructible<T>::value) &&
310 std::is_trivially_destructible<T>::value>
311class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
312 friend class SmallVectorTemplateCommon<T>;
313
314protected:
315 static constexpr bool TakesParamByValue = false;
316 using ValueParamT = const T &;
317
318 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
319
320 static void destroy_range(T *S, T *E) {
321 while (S != E) {
322 --E;
323 E->~T();
324 }
325 }
326
327 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
328 /// constructing elements as needed.
329 template<typename It1, typename It2>
330 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
331 std::uninitialized_copy(std::make_move_iterator(I),
332 std::make_move_iterator(E), Dest);
333 }
334
335 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
336 /// constructing elements as needed.
337 template<typename It1, typename It2>
338 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
339 std::uninitialized_copy(I, E, Dest);
340 }
341
342 /// Grow the allocated memory (without initializing new elements), doubling
343 /// the size of the allocated memory. Guarantees space for at least one more
344 /// element, or MinSize more elements if specified.
345 void grow(size_t MinSize = 0);
346
347 /// Create a new allocation big enough for \p MinSize and pass back its size
348 /// in \p NewCapacity. This is the first section of \a grow().
349 T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
350 return static_cast<T *>(
351 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
352 MinSize, sizeof(T), NewCapacity));
353 }
354
355 /// Move existing elements over to the new allocation \p NewElts, the middle
356 /// section of \a grow().
357 void moveElementsForGrow(T *NewElts);
358
359 /// Transfer ownership of the allocation, finishing up \a grow().
360 void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
361
362 /// Reserve enough space to add one element, and return the updated element
363 /// pointer in case it was a reference to the storage.
364 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
365 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
366 }
367
368 /// Reserve enough space to add one element, and return the updated element
369 /// pointer in case it was a reference to the storage.
370 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
371 return const_cast<T *>(
372 this->reserveForParamAndGetAddressImpl(this, Elt, N));
373 }
374
375 static T &&forward_value_param(T &&V) { return std::move(V); }
376 static const T &forward_value_param(const T &V) { return V; }
377
378 void growAndAssign(size_t NumElts, const T &Elt) {
379 // Grow manually in case Elt is an internal reference.
380 size_t NewCapacity;
381 T *NewElts = mallocForGrow(NumElts, NewCapacity);
382 std::uninitialized_fill_n(NewElts, NumElts, Elt);
383 this->destroy_range(this->begin(), this->end());
384 takeAllocationForGrow(NewElts, NewCapacity);
385 this->set_size(NumElts);
386 }
387
388 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
389 // Grow manually in case one of Args is an internal reference.
390 size_t NewCapacity;
391 T *NewElts = mallocForGrow(0, NewCapacity);
392 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
393 moveElementsForGrow(NewElts);
394 takeAllocationForGrow(NewElts, NewCapacity);
395 this->set_size(this->size() + 1);
396 return this->back();
397 }
398
399public:
400 void push_back(const T &Elt) {
401 const T *EltPtr = reserveForParamAndGetAddress(Elt);
402 ::new ((void *)this->end()) T(*EltPtr);
403 this->set_size(this->size() + 1);
404 }
405
406 void push_back(T &&Elt) {
407 T *EltPtr = reserveForParamAndGetAddress(Elt);
408 ::new ((void *)this->end()) T(::std::move(*EltPtr));
409 this->set_size(this->size() + 1);
410 }
411
412 void pop_back() {
413 this->set_size(this->size() - 1);
414 this->end()->~T();
415 }
416};
417
418// Define this out-of-line to dissuade the C++ compiler from inlining it.
419template <typename T, bool TriviallyCopyable>
420void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
421 size_t NewCapacity;
422 T *NewElts = mallocForGrow(MinSize, NewCapacity);
423 moveElementsForGrow(NewElts);
424 takeAllocationForGrow(NewElts, NewCapacity);
425}
426
427// Define this out-of-line to dissuade the C++ compiler from inlining it.
428template <typename T, bool TriviallyCopyable>
429void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
430 T *NewElts) {
431 // Move the elements over.
432 this->uninitialized_move(this->begin(), this->end(), NewElts);
433
434 // Destroy the original elements.
435 destroy_range(this->begin(), this->end());
436}
437
438// Define this out-of-line to dissuade the C++ compiler from inlining it.
439template <typename T, bool TriviallyCopyable>
440void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
441 T *NewElts, size_t NewCapacity) {
442 // If this wasn't grown from the inline copy, deallocate the old space.
443 if (!this->isSmall())
444 free(this->begin());
445
446 this->BeginX = NewElts;
447 this->Capacity = NewCapacity;
448}
449
450/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
451/// method implementations that are designed to work with trivially copyable
452/// T's. This allows using memcpy in place of copy/move construction and
453/// skipping destruction.
454template <typename T>
455class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
456 friend class SmallVectorTemplateCommon<T>;
457
458protected:
459 /// True if it's cheap enough to take parameters by value. Doing so avoids
460 /// overhead related to mitigations for reference invalidation.
461 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
462
463 /// Either const T& or T, depending on whether it's cheap enough to take
464 /// parameters by value.
465 using ValueParamT =
466 typename std::conditional<TakesParamByValue, T, const T &>::type;
467
468 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
469
470 // No need to do a destroy loop for POD's.
471 static void destroy_range(T *, T *) {}
472
473 /// Move the range [I, E) onto the uninitialized memory
474 /// starting with "Dest", constructing elements into it as needed.
475 template<typename It1, typename It2>
476 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
477 // Just do a copy.
478 uninitialized_copy(I, E, Dest);
479 }
480
481 /// Copy the range [I, E) onto the uninitialized memory
482 /// starting with "Dest", constructing elements into it as needed.
483 template<typename It1, typename It2>
484 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
485 // Arbitrary iterator types; just use the basic implementation.
486 std::uninitialized_copy(I, E, Dest);
487 }
488
489 /// Copy the range [I, E) onto the uninitialized memory
490 /// starting with "Dest", constructing elements into it as needed.
491 template <typename T1, typename T2>
492 static void uninitialized_copy(
493 T1 *I, T1 *E, T2 *Dest,
494 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
495 T2>::value> * = nullptr) {
496 // Use memcpy for PODs iterated by pointers (which includes SmallVector
497 // iterators): std::uninitialized_copy optimizes to memmove, but we can
498 // use memcpy here. Note that I and E are iterators and thus might be
499 // invalid for memcpy if they are equal.
500 if (I != E)
501 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
502 }
503
504 /// Double the size of the allocated memory, guaranteeing space for at
505 /// least one more element or MinSize if specified.
506 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
507
508 /// Reserve enough space to add one element, and return the updated element
509 /// pointer in case it was a reference to the storage.
510 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
511 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
512 }
513
514 /// Reserve enough space to add one element, and return the updated element
515 /// pointer in case it was a reference to the storage.
516 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
517 return const_cast<T *>(
518 this->reserveForParamAndGetAddressImpl(this, Elt, N));
519 }
520
521 /// Copy \p V or return a reference, depending on \a ValueParamT.
522 static ValueParamT forward_value_param(ValueParamT V) { return V; }
523
524 void growAndAssign(size_t NumElts, T Elt) {
525 // Elt has been copied in case it's an internal reference, side-stepping
526 // reference invalidation problems without losing the realloc optimization.
527 this->set_size(0);
528 this->grow(NumElts);
529 std::uninitialized_fill_n(this->begin(), NumElts, Elt);
530 this->set_size(NumElts);
531 }
532
533 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
534 // Use push_back with a copy in case Args has an internal reference,
535 // side-stepping reference invalidation problems without losing the realloc
536 // optimization.
537 push_back(T(std::forward<ArgTypes>(Args)...));
538 return this->back();
539 }
540
541public:
542 void push_back(ValueParamT Elt) {
543 const T *EltPtr = reserveForParamAndGetAddress(Elt);
544 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
545 this->set_size(this->size() + 1);
546 }
547
548 void pop_back() { this->set_size(this->size() - 1); }
549};
550
551/// This class consists of common code factored out of the SmallVector class to
552/// reduce code duplication based on the SmallVector 'N' template parameter.
553template <typename T>
554class SmallVectorImpl : public SmallVectorTemplateBase<T> {
555 using SuperClass = SmallVectorTemplateBase<T>;
556
557public:
558 using iterator = typename SuperClass::iterator;
559 using const_iterator = typename SuperClass::const_iterator;
560 using reference = typename SuperClass::reference;
561 using size_type = typename SuperClass::size_type;
562
563protected:
564 using SmallVectorTemplateBase<T>::TakesParamByValue;
565 using ValueParamT = typename SuperClass::ValueParamT;
566
567 // Default ctor - Initialize to empty.
568 explicit SmallVectorImpl(unsigned N)
569 : SmallVectorTemplateBase<T>(N) {}
570
571public:
572 SmallVectorImpl(const SmallVectorImpl &) = delete;
573
574 ~SmallVectorImpl() {
575 // Subclass has already destructed this vector's elements.
576 // If this wasn't grown from the inline copy, deallocate the old space.
577 if (!this->isSmall())
578 free(this->begin());
579 }
580
581 void clear() {
582 this->destroy_range(this->begin(), this->end());
583 this->Size = 0;
584 }
585
586private:
587 // Make set_size() private to avoid misuse in subclasses.
588 using SuperClass::set_size;
589
590 template <bool ForOverwrite> void resizeImpl(size_type N) {
591 if (N == this->size())
592 return;
593
594 if (N < this->size()) {
595 this->truncate(N);
596 return;
597 }
598
599 this->reserve(N);
600 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
601 if (ForOverwrite)
602 new (&*I) T;
603 else
604 new (&*I) T();
605 this->set_size(N);
606 }
607
608public:
609 void resize(size_type N) { resizeImpl<false>(N); }
610
611 /// Like resize, but \ref T is POD, the new values won't be initialized.
612 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
613
614 /// Like resize, but requires that \p N is less than \a size().
615 void truncate(size_type N) {
616 assert(this->size() >= N && "Cannot increase size with truncate")(static_cast <bool> (this->size() >= N &&
"Cannot increase size with truncate") ? void (0) : __assert_fail
("this->size() >= N && \"Cannot increase size with truncate\""
, "llvm/include/llvm/ADT/SmallVector.h", 616, __extension__ __PRETTY_FUNCTION__
))
;
617 this->destroy_range(this->begin() + N, this->end());
618 this->set_size(N);
619 }
620
621 void resize(size_type N, ValueParamT NV) {
622 if (N == this->size())
623 return;
624
625 if (N < this->size()) {
626 this->truncate(N);
627 return;
628 }
629
630 // N > this->size(). Defer to append.
631 this->append(N - this->size(), NV);
632 }
633
634 void reserve(size_type N) {
635 if (this->capacity() < N)
636 this->grow(N);
637 }
638
639 void pop_back_n(size_type NumItems) {
640 assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void
(0) : __assert_fail ("this->size() >= NumItems", "llvm/include/llvm/ADT/SmallVector.h"
, 640, __extension__ __PRETTY_FUNCTION__))
;
641 truncate(this->size() - NumItems);
642 }
643
644 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
645 T Result = ::std::move(this->back());
646 this->pop_back();
647 return Result;
648 }
649
650 void swap(SmallVectorImpl &RHS);
651
652 /// Add the specified range to the end of the SmallVector.
653 template <typename in_iter,
654 typename = std::enable_if_t<std::is_convertible<
655 typename std::iterator_traits<in_iter>::iterator_category,
656 std::input_iterator_tag>::value>>
657 void append(in_iter in_start, in_iter in_end) {
658 this->assertSafeToAddRange(in_start, in_end);
659 size_type NumInputs = std::distance(in_start, in_end);
660 this->reserve(this->size() + NumInputs);
661 this->uninitialized_copy(in_start, in_end, this->end());
662 this->set_size(this->size() + NumInputs);
663 }
664
665 /// Append \p NumInputs copies of \p Elt to the end.
666 void append(size_type NumInputs, ValueParamT Elt) {
667 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
668 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
669 this->set_size(this->size() + NumInputs);
670 }
671
672 void append(std::initializer_list<T> IL) {
673 append(IL.begin(), IL.end());
674 }
675
676 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
677
678 void assign(size_type NumElts, ValueParamT Elt) {
679 // Note that Elt could be an internal reference.
680 if (NumElts > this->capacity()) {
681 this->growAndAssign(NumElts, Elt);
682 return;
683 }
684
685 // Assign over existing elements.
686 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
687 if (NumElts > this->size())
688 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
689 else if (NumElts < this->size())
690 this->destroy_range(this->begin() + NumElts, this->end());
691 this->set_size(NumElts);
692 }
693
694 // FIXME: Consider assigning over existing elements, rather than clearing &
695 // re-initializing them - for all assign(...) variants.
696
697 template <typename in_iter,
698 typename = std::enable_if_t<std::is_convertible<
699 typename std::iterator_traits<in_iter>::iterator_category,
700 std::input_iterator_tag>::value>>
701 void assign(in_iter in_start, in_iter in_end) {
702 this->assertSafeToReferenceAfterClear(in_start, in_end);
703 clear();
704 append(in_start, in_end);
705 }
706
707 void assign(std::initializer_list<T> IL) {
708 clear();
709 append(IL);
710 }
711
712 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
713
714 iterator erase(const_iterator CI) {
715 // Just cast away constness because this is a non-const member function.
716 iterator I = const_cast<iterator>(CI);
717
718 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(CI) &&
"Iterator to erase is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 718, __extension__ __PRETTY_FUNCTION__
))
;
719
720 iterator N = I;
721 // Shift all elts down one.
722 std::move(I+1, this->end(), I);
723 // Drop the last elt.
724 this->pop_back();
725 return(N);
726 }
727
728 iterator erase(const_iterator CS, const_iterator CE) {
729 // Just cast away constness because this is a non-const member function.
730 iterator S = const_cast<iterator>(CS);
731 iterator E = const_cast<iterator>(CE);
732
733 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast <bool> (this->isRangeInStorage(S, E) &&
"Range to erase is out of bounds.") ? void (0) : __assert_fail
("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 733, __extension__ __PRETTY_FUNCTION__
))
;
734
735 iterator N = S;
736 // Shift all elts down.
737 iterator I = std::move(E, this->end(), S);
738 // Drop the last elts.
739 this->destroy_range(I, this->end());
740 this->set_size(I - this->begin());
741 return(N);
742 }
743
744private:
745 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
746 // Callers ensure that ArgType is derived from T.
747 static_assert(
748 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
749 T>::value,
750 "ArgType must be derived from T!");
751
752 if (I == this->end()) { // Important special case for empty vector.
753 this->push_back(::std::forward<ArgType>(Elt));
754 return this->end()-1;
755 }
756
757 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 757, __extension__ __PRETTY_FUNCTION__
))
;
758
759 // Grow if necessary.
760 size_t Index = I - this->begin();
761 std::remove_reference_t<ArgType> *EltPtr =
762 this->reserveForParamAndGetAddress(Elt);
763 I = this->begin() + Index;
764
765 ::new ((void*) this->end()) T(::std::move(this->back()));
766 // Push everything else over.
767 std::move_backward(I, this->end()-1, this->end());
768 this->set_size(this->size() + 1);
769
770 // If we just moved the element we're inserting, be sure to update
771 // the reference (never happens if TakesParamByValue).
772 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
773 "ArgType must be 'T' when taking by value!");
774 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
775 ++EltPtr;
776
777 *I = ::std::forward<ArgType>(*EltPtr);
778 return I;
779 }
780
781public:
782 iterator insert(iterator I, T &&Elt) {
783 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
784 }
785
786 iterator insert(iterator I, const T &Elt) {
787 return insert_one_impl(I, this->forward_value_param(Elt));
788 }
789
790 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
791 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
792 size_t InsertElt = I - this->begin();
793
794 if (I == this->end()) { // Important special case for empty vector.
795 append(NumToInsert, Elt);
796 return this->begin()+InsertElt;
797 }
798
799 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 799, __extension__ __PRETTY_FUNCTION__
))
;
800
801 // Ensure there is enough space, and get the (maybe updated) address of
802 // Elt.
803 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
804
805 // Uninvalidate the iterator.
806 I = this->begin()+InsertElt;
807
808 // If there are more elements between the insertion point and the end of the
809 // range than there are being inserted, we can use a simple approach to
810 // insertion. Since we already reserved space, we know that this won't
811 // reallocate the vector.
812 if (size_t(this->end()-I) >= NumToInsert) {
813 T *OldEnd = this->end();
814 append(std::move_iterator<iterator>(this->end() - NumToInsert),
815 std::move_iterator<iterator>(this->end()));
816
817 // Copy the existing elements that get replaced.
818 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
819
820 // If we just moved the element we're inserting, be sure to update
821 // the reference (never happens if TakesParamByValue).
822 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
823 EltPtr += NumToInsert;
824
825 std::fill_n(I, NumToInsert, *EltPtr);
826 return I;
827 }
828
829 // Otherwise, we're inserting more elements than exist already, and we're
830 // not inserting at the end.
831
832 // Move over the elements that we're about to overwrite.
833 T *OldEnd = this->end();
834 this->set_size(this->size() + NumToInsert);
835 size_t NumOverwritten = OldEnd-I;
836 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
837
838 // If we just moved the element we're inserting, be sure to update
839 // the reference (never happens if TakesParamByValue).
840 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
841 EltPtr += NumToInsert;
842
843 // Replace the overwritten part.
844 std::fill_n(I, NumOverwritten, *EltPtr);
845
846 // Insert the non-overwritten middle part.
847 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
848 return I;
849 }
850
851 template <typename ItTy,
852 typename = std::enable_if_t<std::is_convertible<
853 typename std::iterator_traits<ItTy>::iterator_category,
854 std::input_iterator_tag>::value>>
855 iterator insert(iterator I, ItTy From, ItTy To) {
856 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
857 size_t InsertElt = I - this->begin();
858
859 if (I == this->end()) { // Important special case for empty vector.
860 append(From, To);
861 return this->begin()+InsertElt;
862 }
863
864 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 864, __extension__ __PRETTY_FUNCTION__
))
;
865
866 // Check that the reserve that follows doesn't invalidate the iterators.
867 this->assertSafeToAddRange(From, To);
868
869 size_t NumToInsert = std::distance(From, To);
870
871 // Ensure there is enough space.
872 reserve(this->size() + NumToInsert);
873
874 // Uninvalidate the iterator.
875 I = this->begin()+InsertElt;
876
877 // If there are more elements between the insertion point and the end of the
878 // range than there are being inserted, we can use a simple approach to
879 // insertion. Since we already reserved space, we know that this won't
880 // reallocate the vector.
881 if (size_t(this->end()-I) >= NumToInsert) {
882 T *OldEnd = this->end();
883 append(std::move_iterator<iterator>(this->end() - NumToInsert),
884 std::move_iterator<iterator>(this->end()));
885
886 // Copy the existing elements that get replaced.
887 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
888
889 std::copy(From, To, I);
890 return I;
891 }
892
893 // Otherwise, we're inserting more elements than exist already, and we're
894 // not inserting at the end.
895
896 // Move over the elements that we're about to overwrite.
897 T *OldEnd = this->end();
898 this->set_size(this->size() + NumToInsert);
899 size_t NumOverwritten = OldEnd-I;
900 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
901
902 // Replace the overwritten part.
903 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
904 *J = *From;
905 ++J; ++From;
906 }
907
908 // Insert the non-overwritten middle part.
909 this->uninitialized_copy(From, To, OldEnd);
910 return I;
911 }
912
913 void insert(iterator I, std::initializer_list<T> IL) {
914 insert(I, IL.begin(), IL.end());
915 }
916
917 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
918 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
919 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
920
921 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
922 this->set_size(this->size() + 1);
923 return this->back();
924 }
925
926 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
927
928 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
929
930 bool operator==(const SmallVectorImpl &RHS) const {
931 if (this->size() != RHS.size()) return false;
932 return std::equal(this->begin(), this->end(), RHS.begin());
933 }
934 bool operator!=(const SmallVectorImpl &RHS) const {
935 return !(*this == RHS);
936 }
937
938 bool operator<(const SmallVectorImpl &RHS) const {
939 return std::lexicographical_compare(this->begin(), this->end(),
940 RHS.begin(), RHS.end());
941 }
942};
943
944template <typename T>
945void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
946 if (this == &RHS) return;
947
948 // We can only avoid copying elements if neither vector is small.
949 if (!this->isSmall() && !RHS.isSmall()) {
950 std::swap(this->BeginX, RHS.BeginX);
951 std::swap(this->Size, RHS.Size);
952 std::swap(this->Capacity, RHS.Capacity);
953 return;
954 }
955 this->reserve(RHS.size());
956 RHS.reserve(this->size());
957
958 // Swap the shared elements.
959 size_t NumShared = this->size();
960 if (NumShared > RHS.size()) NumShared = RHS.size();
961 for (size_type i = 0; i != NumShared; ++i)
962 std::swap((*this)[i], RHS[i]);
963
964 // Copy over the extra elts.
965 if (this->size() > RHS.size()) {
966 size_t EltDiff = this->size() - RHS.size();
967 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
968 RHS.set_size(RHS.size() + EltDiff);
969 this->destroy_range(this->begin()+NumShared, this->end());
970 this->set_size(NumShared);
971 } else if (RHS.size() > this->size()) {
972 size_t EltDiff = RHS.size() - this->size();
973 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
974 this->set_size(this->size() + EltDiff);
975 this->destroy_range(RHS.begin()+NumShared, RHS.end());
976 RHS.set_size(NumShared);
977 }
978}
979
980template <typename T>
981SmallVectorImpl<T> &SmallVectorImpl<T>::
982 operator=(const SmallVectorImpl<T> &RHS) {
983 // Avoid self-assignment.
984 if (this == &RHS) return *this;
985
986 // If we already have sufficient space, assign the common elements, then
987 // destroy any excess.
988 size_t RHSSize = RHS.size();
989 size_t CurSize = this->size();
990 if (CurSize >= RHSSize) {
991 // Assign common elements.
992 iterator NewEnd;
993 if (RHSSize)
994 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
995 else
996 NewEnd = this->begin();
997
998 // Destroy excess elements.
999 this->destroy_range(NewEnd, this->end());
1000
1001 // Trim.
1002 this->set_size(RHSSize);
1003 return *this;
1004 }
1005
1006 // If we have to grow to have enough elements, destroy the current elements.
1007 // This allows us to avoid copying them during the grow.
1008 // FIXME: don't do this if they're efficiently moveable.
1009 if (this->capacity() < RHSSize) {
1010 // Destroy current elements.
1011 this->clear();
1012 CurSize = 0;
1013 this->grow(RHSSize);
1014 } else if (CurSize) {
1015 // Otherwise, use assignment for the already-constructed elements.
1016 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1017 }
1018
1019 // Copy construct the new elements in place.
1020 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1021 this->begin()+CurSize);
1022
1023 // Set end.
1024 this->set_size(RHSSize);
1025 return *this;
1026}
1027
1028template <typename T>
1029SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1030 // Avoid self-assignment.
1031 if (this == &RHS) return *this;
1032
1033 // If the RHS isn't small, clear this vector and then steal its buffer.
1034 if (!RHS.isSmall()) {
1035 this->destroy_range(this->begin(), this->end());
1036 if (!this->isSmall()) free(this->begin());
1037 this->BeginX = RHS.BeginX;
1038 this->Size = RHS.Size;
1039 this->Capacity = RHS.Capacity;
1040 RHS.resetToSmall();
1041 return *this;
1042 }
1043
1044 // If we already have sufficient space, assign the common elements, then
1045 // destroy any excess.
1046 size_t RHSSize = RHS.size();
1047 size_t CurSize = this->size();
1048 if (CurSize >= RHSSize) {
1049 // Assign common elements.
1050 iterator NewEnd = this->begin();
1051 if (RHSSize)
1052 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1053
1054 // Destroy excess elements and trim the bounds.
1055 this->destroy_range(NewEnd, this->end());
1056 this->set_size(RHSSize);
1057
1058 // Clear the RHS.
1059 RHS.clear();
1060
1061 return *this;
1062 }
1063
1064 // If we have to grow to have enough elements, destroy the current elements.
1065 // This allows us to avoid copying them during the grow.
1066 // FIXME: this may not actually make any sense if we can efficiently move
1067 // elements.
1068 if (this->capacity() < RHSSize) {
1069 // Destroy current elements.
1070 this->clear();
1071 CurSize = 0;
1072 this->grow(RHSSize);
1073 } else if (CurSize) {
1074 // Otherwise, use assignment for the already-constructed elements.
1075 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1076 }
1077
1078 // Move-construct the new elements in place.
1079 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1080 this->begin()+CurSize);
1081
1082 // Set end.
1083 this->set_size(RHSSize);
1084
1085 RHS.clear();
1086 return *this;
1087}
1088
1089/// Storage for the SmallVector elements. This is specialized for the N=0 case
1090/// to avoid allocating unnecessary storage.
1091template <typename T, unsigned N>
1092struct SmallVectorStorage {
1093 alignas(T) char InlineElts[N * sizeof(T)];
1094};
1095
1096/// We need the storage to be properly aligned even for small-size of 0 so that
1097/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1098/// well-defined.
1099template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1100
1101/// Forward declaration of SmallVector so that
1102/// calculateSmallVectorDefaultInlinedElements can reference
1103/// `sizeof(SmallVector<T, 0>)`.
1104template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1105
1106/// Helper class for calculating the default number of inline elements for
1107/// `SmallVector<T>`.
1108///
1109/// This should be migrated to a constexpr function when our minimum
1110/// compiler support is enough for multi-statement constexpr functions.
1111template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1112 // Parameter controlling the default number of inlined elements
1113 // for `SmallVector<T>`.
1114 //
1115 // The default number of inlined elements ensures that
1116 // 1. There is at least one inlined element.
1117 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1118 // it contradicts 1.
1119 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1120
1121 // static_assert that sizeof(T) is not "too big".
1122 //
1123 // Because our policy guarantees at least one inlined element, it is possible
1124 // for an arbitrarily large inlined element to allocate an arbitrarily large
1125 // amount of inline storage. We generally consider it an antipattern for a
1126 // SmallVector to allocate an excessive amount of inline storage, so we want
1127 // to call attention to these cases and make sure that users are making an
1128 // intentional decision if they request a lot of inline storage.
1129 //
1130 // We want this assertion to trigger in pathological cases, but otherwise
1131 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1132 // larger than kPreferredSmallVectorSizeof (otherwise,
1133 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1134 // pattern seems useful in practice).
1135 //
1136 // One wrinkle is that this assertion is in theory non-portable, since
1137 // sizeof(T) is in general platform-dependent. However, we don't expect this
1138 // to be much of an issue, because most LLVM development happens on 64-bit
1139 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1140 // 32-bit hosts, dodging the issue. The reverse situation, where development
1141 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1142 // 64-bit host, is expected to be very rare.
1143 static_assert(
1144 sizeof(T) <= 256,
1145 "You are trying to use a default number of inlined elements for "
1146 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1147 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1148 "sure you really want that much inline storage.");
1149
1150 // Discount the size of the header itself when calculating the maximum inline
1151 // bytes.
1152 static constexpr size_t PreferredInlineBytes =
1153 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1154 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1155 static constexpr size_t value =
1156 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1157};
1158
1159/// This is a 'vector' (really, a variable-sized array), optimized
1160/// for the case when the array is small. It contains some number of elements
1161/// in-place, which allows it to avoid heap allocation when the actual number of
1162/// elements is below that threshold. This allows normal "small" cases to be
1163/// fast without losing generality for large inputs.
1164///
1165/// \note
1166/// In the absence of a well-motivated choice for the number of inlined
1167/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1168/// omitting the \p N). This will choose a default number of inlined elements
1169/// reasonable for allocation on the stack (for example, trying to keep \c
1170/// sizeof(SmallVector<T>) around 64 bytes).
1171///
1172/// \warning This does not attempt to be exception safe.
1173///
1174/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1175template <typename T,
1176 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1177class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1178 SmallVectorStorage<T, N> {
1179public:
1180 SmallVector() : SmallVectorImpl<T>(N) {}
1181
1182 ~SmallVector() {
1183 // Destroy the constructed elements in the vector.
1184 this->destroy_range(this->begin(), this->end());
1185 }
1186
1187 explicit SmallVector(size_t Size, const T &Value = T())
1188 : SmallVectorImpl<T>(N) {
1189 this->assign(Size, Value);
1190 }
1191
1192 template <typename ItTy,
1193 typename = std::enable_if_t<std::is_convertible<
1194 typename std::iterator_traits<ItTy>::iterator_category,
1195 std::input_iterator_tag>::value>>
1196 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1197 this->append(S, E);
1198 }
1199
1200 template <typename RangeTy>
1201 explicit SmallVector(const iterator_range<RangeTy> &R)
1202 : SmallVectorImpl<T>(N) {
1203 this->append(R.begin(), R.end());
1204 }
1205
1206 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1207 this->assign(IL);
1208 }
1209
1210 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1211 if (!RHS.empty())
1212 SmallVectorImpl<T>::operator=(RHS);
1213 }
1214
1215 SmallVector &operator=(const SmallVector &RHS) {
1216 SmallVectorImpl<T>::operator=(RHS);
1217 return *this;
1218 }
1219
1220 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1221 if (!RHS.empty())
1222 SmallVectorImpl<T>::operator=(::std::move(RHS));
1223 }
1224
1225 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1226 if (!RHS.empty())
1227 SmallVectorImpl<T>::operator=(::std::move(RHS));
1228 }
1229
1230 SmallVector &operator=(SmallVector &&RHS) {
1231 SmallVectorImpl<T>::operator=(::std::move(RHS));
1232 return *this;
1233 }
1234
1235 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1236 SmallVectorImpl<T>::operator=(::std::move(RHS));
1237 return *this;
1238 }
1239
1240 SmallVector &operator=(std::initializer_list<T> IL) {
1241 this->assign(IL);
1242 return *this;
1243 }
1244};
1245
1246template <typename T, unsigned N>
1247inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1248 return X.capacity_in_bytes();
1249}
1250
1251template <typename RangeType>
1252using ValueTypeFromRangeType =
1253 typename std::remove_const<typename std::remove_reference<
1254 decltype(*std::begin(std::declval<RangeType &>()))>::type>::type;
1255
1256/// Given a range of type R, iterate the entire range and return a
1257/// SmallVector with elements of the vector. This is useful, for example,
1258/// when you want to iterate a range and then sort the results.
1259template <unsigned Size, typename R>
1260SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) {
1261 return {std::begin(Range), std::end(Range)};
1262}
1263template <typename R>
1264SmallVector<ValueTypeFromRangeType<R>,
1265 CalculateSmallVectorDefaultInlinedElements<
1266 ValueTypeFromRangeType<R>>::value>
1267to_vector(R &&Range) {
1268 return {std::begin(Range), std::end(Range)};
1269}
1270
1271} // end namespace llvm
1272
1273namespace std {
1274
1275 /// Implement std::swap in terms of SmallVector swap.
1276 template<typename T>
1277 inline void
1278 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1279 LHS.swap(RHS);
1280 }
1281
1282 /// Implement std::swap in terms of SmallVector swap.
1283 template<typename T, unsigned N>
1284 inline void
1285 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1286 LHS.swap(RHS);
1287 }
1288
1289} // end namespace std
1290
1291#endif // LLVM_ADT_SMALLVECTOR_H