File: | src/gnu/usr.bin/clang/liblldELF/../../../llvm/lld/ELF/Writer.cpp |
Warning: | line 1914, column 29 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- Writer.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 | #include "Writer.h" | |||
10 | #include "AArch64ErrataFix.h" | |||
11 | #include "ARMErrataFix.h" | |||
12 | #include "CallGraphSort.h" | |||
13 | #include "Config.h" | |||
14 | #include "LinkerScript.h" | |||
15 | #include "MapFile.h" | |||
16 | #include "OutputSections.h" | |||
17 | #include "Relocations.h" | |||
18 | #include "SymbolTable.h" | |||
19 | #include "Symbols.h" | |||
20 | #include "SyntheticSections.h" | |||
21 | #include "Target.h" | |||
22 | #include "lld/Common/Arrays.h" | |||
23 | #include "lld/Common/Filesystem.h" | |||
24 | #include "lld/Common/Memory.h" | |||
25 | #include "lld/Common/Strings.h" | |||
26 | #include "llvm/ADT/StringMap.h" | |||
27 | #include "llvm/ADT/StringSwitch.h" | |||
28 | #include "llvm/Support/Parallel.h" | |||
29 | #include "llvm/Support/RandomNumberGenerator.h" | |||
30 | #include "llvm/Support/SHA1.h" | |||
31 | #include "llvm/Support/TimeProfiler.h" | |||
32 | #include "llvm/Support/xxhash.h" | |||
33 | #include <climits> | |||
34 | ||||
35 | #define DEBUG_TYPE"lld" "lld" | |||
36 | ||||
37 | using namespace llvm; | |||
38 | using namespace llvm::ELF; | |||
39 | using namespace llvm::object; | |||
40 | using namespace llvm::support; | |||
41 | using namespace llvm::support::endian; | |||
42 | using namespace lld; | |||
43 | using namespace lld::elf; | |||
44 | ||||
45 | namespace { | |||
46 | // The writer writes a SymbolTable result to a file. | |||
47 | template <class ELFT> class Writer { | |||
48 | public: | |||
49 | LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)using Elf_Addr = typename ELFT::Addr; using Elf_Off = typename ELFT::Off; using Elf_Half = typename ELFT::Half; using Elf_Word = typename ELFT::Word; using Elf_Sword = typename ELFT::Sword ; using Elf_Xword = typename ELFT::Xword; using Elf_Sxword = typename ELFT::Sxword; using uintX_t = typename ELFT::uint; using Elf_Ehdr = typename ELFT::Ehdr; using Elf_Shdr = typename ELFT::Shdr; using Elf_Sym = typename ELFT::Sym; using Elf_Dyn = typename ELFT::Dyn; using Elf_Phdr = typename ELFT::Phdr; using Elf_Rel = typename ELFT::Rel; using Elf_Rela = typename ELFT::Rela; using Elf_Relr = typename ELFT::Relr; using Elf_Verdef = typename ELFT ::Verdef; using Elf_Verdaux = typename ELFT::Verdaux; using Elf_Verneed = typename ELFT::Verneed; using Elf_Vernaux = typename ELFT:: Vernaux; using Elf_Versym = typename ELFT::Versym; using Elf_Hash = typename ELFT::Hash; using Elf_GnuHash = typename ELFT::GnuHash ; using Elf_Nhdr = typename ELFT::Nhdr; using Elf_Note = typename ELFT::Note; using Elf_Note_Iterator = typename ELFT::NoteIterator ; using Elf_CGProfile = typename ELFT::CGProfile; using Elf_BBAddrMap = typename ELFT::BBAddrMap; using Elf_Dyn_Range = typename ELFT ::DynRange; using Elf_Shdr_Range = typename ELFT::ShdrRange; using Elf_Sym_Range = typename ELFT::SymRange; using Elf_Rel_Range = typename ELFT::RelRange; using Elf_Rela_Range = typename ELFT ::RelaRange; using Elf_Relr_Range = typename ELFT::RelrRange; using Elf_Phdr_Range = typename ELFT::PhdrRange; | |||
50 | ||||
51 | Writer() : buffer(errorHandler().outputBuffer) {} | |||
52 | ||||
53 | void run(); | |||
54 | ||||
55 | private: | |||
56 | void copyLocalSymbols(); | |||
57 | void addSectionSymbols(); | |||
58 | void forEachRelSec(llvm::function_ref<void(InputSectionBase &)> fn); | |||
59 | void sortSections(); | |||
60 | void resolveShfLinkOrder(); | |||
61 | void finalizeAddressDependentContent(); | |||
62 | void optimizeBasicBlockJumps(); | |||
63 | void sortInputSections(); | |||
64 | void finalizeSections(); | |||
65 | void checkExecuteOnly(); | |||
66 | void setReservedSymbolSections(); | |||
67 | ||||
68 | std::vector<PhdrEntry *> createPhdrs(Partition &part); | |||
69 | void addPhdrForSection(Partition &part, unsigned shType, unsigned pType, | |||
70 | unsigned pFlags); | |||
71 | void assignFileOffsets(); | |||
72 | void assignFileOffsetsBinary(); | |||
73 | void setPhdrs(Partition &part); | |||
74 | void checkSections(); | |||
75 | void fixSectionAlignments(); | |||
76 | void openFile(); | |||
77 | void writeTrapInstr(); | |||
78 | void writeHeader(); | |||
79 | void writeSections(); | |||
80 | void writeSectionsBinary(); | |||
81 | void writeBuildId(); | |||
82 | ||||
83 | std::unique_ptr<FileOutputBuffer> &buffer; | |||
84 | ||||
85 | void addRelIpltSymbols(); | |||
86 | void addStartEndSymbols(); | |||
87 | void addStartStopSymbols(OutputSection *sec); | |||
88 | ||||
89 | uint64_t fileSize; | |||
90 | uint64_t sectionHeaderOff; | |||
91 | }; | |||
92 | } // anonymous namespace | |||
93 | ||||
94 | static bool isSectionPrefix(StringRef prefix, StringRef name) { | |||
95 | return name.startswith(prefix) || name == prefix.drop_back(); | |||
96 | } | |||
97 | ||||
98 | StringRef elf::getOutputSectionName(const InputSectionBase *s) { | |||
99 | if (config->relocatable) | |||
100 | return s->name; | |||
101 | ||||
102 | // This is for --emit-relocs. If .text.foo is emitted as .text.bar, we want | |||
103 | // to emit .rela.text.foo as .rela.text.bar for consistency (this is not | |||
104 | // technically required, but not doing it is odd). This code guarantees that. | |||
105 | if (auto *isec = dyn_cast<InputSection>(s)) { | |||
106 | if (InputSectionBase *rel = isec->getRelocatedSection()) { | |||
107 | OutputSection *out = rel->getOutputSection(); | |||
108 | if (s->type == SHT_RELA) | |||
109 | return saver.save(".rela" + out->name); | |||
110 | return saver.save(".rel" + out->name); | |||
111 | } | |||
112 | } | |||
113 | ||||
114 | // A BssSection created for a common symbol is identified as "COMMON" in | |||
115 | // linker scripts. It should go to .bss section. | |||
116 | if (s->name == "COMMON") | |||
117 | return ".bss"; | |||
118 | ||||
119 | if (script->hasSectionsCommand) | |||
120 | return s->name; | |||
121 | ||||
122 | // When no SECTIONS is specified, emulate GNU ld's internal linker scripts | |||
123 | // by grouping sections with certain prefixes. | |||
124 | ||||
125 | // GNU ld places text sections with prefix ".text.hot.", ".text.unknown.", | |||
126 | // ".text.unlikely.", ".text.startup." or ".text.exit." before others. | |||
127 | // We provide an option -z keep-text-section-prefix to group such sections | |||
128 | // into separate output sections. This is more flexible. See also | |||
129 | // sortISDBySectionOrder(). | |||
130 | // ".text.unknown" means the hotness of the section is unknown. When | |||
131 | // SampleFDO is used, if a function doesn't have sample, it could be very | |||
132 | // cold or it could be a new function never being sampled. Those functions | |||
133 | // will be kept in the ".text.unknown" section. | |||
134 | // ".text.split." holds symbols which are split out from functions in other | |||
135 | // input sections. For example, with -fsplit-machine-functions, placing the | |||
136 | // cold parts in .text.split instead of .text.unlikely mitigates against poor | |||
137 | // profile inaccuracy. Techniques such as hugepage remapping can make | |||
138 | // conservative decisions at the section granularity. | |||
139 | if (config->zKeepTextSectionPrefix) | |||
140 | for (StringRef v : {".text.hot.", ".text.unknown.", ".text.unlikely.", | |||
141 | ".text.startup.", ".text.exit.", ".text.split."}) | |||
142 | if (isSectionPrefix(v, s->name)) | |||
143 | return v.drop_back(); | |||
144 | ||||
145 | for (StringRef v : | |||
146 | {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.rel.ro.", | |||
147 | ".bss.", ".init_array.", ".fini_array.", ".ctors.", ".dtors.", ".tbss.", | |||
148 | ".gcc_except_table.", ".tdata.", ".ARM.exidx.", ".ARM.extab.", | |||
149 | ".openbsd.randomdata."}) | |||
150 | if (isSectionPrefix(v, s->name)) | |||
151 | return v.drop_back(); | |||
152 | ||||
153 | return s->name; | |||
154 | } | |||
155 | ||||
156 | static bool needsInterpSection() { | |||
157 | return !config->relocatable && !config->shared && | |||
158 | !config->dynamicLinker.empty() && script->needsInterpSection(); | |||
159 | } | |||
160 | ||||
161 | template <class ELFT> void elf::writeResult() { | |||
162 | Writer<ELFT>().run(); | |||
163 | } | |||
164 | ||||
165 | static void removeEmptyPTLoad(std::vector<PhdrEntry *> &phdrs) { | |||
166 | auto it = std::stable_partition( | |||
167 | phdrs.begin(), phdrs.end(), [&](const PhdrEntry *p) { | |||
168 | if (p->p_type != PT_LOAD) | |||
169 | return true; | |||
170 | if (!p->firstSec) | |||
171 | return false; | |||
172 | uint64_t size = p->lastSec->addr + p->lastSec->size - p->firstSec->addr; | |||
173 | return size != 0; | |||
174 | }); | |||
175 | ||||
176 | // Clear OutputSection::ptLoad for sections contained in removed | |||
177 | // segments. | |||
178 | DenseSet<PhdrEntry *> removed(it, phdrs.end()); | |||
179 | for (OutputSection *sec : outputSections) | |||
180 | if (removed.count(sec->ptLoad)) | |||
181 | sec->ptLoad = nullptr; | |||
182 | phdrs.erase(it, phdrs.end()); | |||
183 | } | |||
184 | ||||
185 | void elf::copySectionsIntoPartitions() { | |||
186 | std::vector<InputSectionBase *> newSections; | |||
187 | for (unsigned part = 2; part != partitions.size() + 1; ++part) { | |||
188 | for (InputSectionBase *s : inputSections) { | |||
189 | if (!(s->flags & SHF_ALLOC) || !s->isLive()) | |||
190 | continue; | |||
191 | InputSectionBase *copy; | |||
192 | if (s->type == SHT_NOTE) | |||
193 | copy = make<InputSection>(cast<InputSection>(*s)); | |||
194 | else if (auto *es = dyn_cast<EhInputSection>(s)) | |||
195 | copy = make<EhInputSection>(*es); | |||
196 | else | |||
197 | continue; | |||
198 | copy->partition = part; | |||
199 | newSections.push_back(copy); | |||
200 | } | |||
201 | } | |||
202 | ||||
203 | inputSections.insert(inputSections.end(), newSections.begin(), | |||
204 | newSections.end()); | |||
205 | } | |||
206 | ||||
207 | void elf::combineEhSections() { | |||
208 | llvm::TimeTraceScope timeScope("Combine EH sections"); | |||
209 | for (InputSectionBase *&s : inputSections) { | |||
210 | // Ignore dead sections and the partition end marker (.part.end), | |||
211 | // whose partition number is out of bounds. | |||
212 | if (!s->isLive() || s->partition == 255) | |||
213 | continue; | |||
214 | ||||
215 | Partition &part = s->getPartition(); | |||
216 | if (auto *es = dyn_cast<EhInputSection>(s)) { | |||
217 | part.ehFrame->addSection(es); | |||
218 | s = nullptr; | |||
219 | } else if (s->kind() == SectionBase::Regular && part.armExidx && | |||
220 | part.armExidx->addSection(cast<InputSection>(s))) { | |||
221 | s = nullptr; | |||
222 | } | |||
223 | } | |||
224 | ||||
225 | std::vector<InputSectionBase *> &v = inputSections; | |||
226 | v.erase(std::remove(v.begin(), v.end(), nullptr), v.end()); | |||
227 | } | |||
228 | ||||
229 | static Defined *addOptionalRegular(StringRef name, SectionBase *sec, | |||
230 | uint64_t val, uint8_t stOther = STV_HIDDEN, | |||
231 | uint8_t binding = STB_GLOBAL) { | |||
232 | Symbol *s = symtab->find(name); | |||
233 | if (!s || s->isDefined()) | |||
234 | return nullptr; | |||
235 | ||||
236 | s->resolve(Defined{/*file=*/nullptr, name, binding, stOther, STT_NOTYPE, val, | |||
237 | /*size=*/0, sec}); | |||
238 | return cast<Defined>(s); | |||
239 | } | |||
240 | ||||
241 | static Defined *addAbsolute(StringRef name) { | |||
242 | Symbol *sym = symtab->addSymbol(Defined{nullptr, name, STB_GLOBAL, STV_HIDDEN, | |||
243 | STT_NOTYPE, 0, 0, nullptr}); | |||
244 | return cast<Defined>(sym); | |||
245 | } | |||
246 | ||||
247 | // The linker is expected to define some symbols depending on | |||
248 | // the linking result. This function defines such symbols. | |||
249 | void elf::addReservedSymbols() { | |||
250 | if (config->emachine == EM_MIPS) { | |||
251 | // Define _gp for MIPS. st_value of _gp symbol will be updated by Writer | |||
252 | // so that it points to an absolute address which by default is relative | |||
253 | // to GOT. Default offset is 0x7ff0. | |||
254 | // See "Global Data Symbols" in Chapter 6 in the following document: | |||
255 | // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf | |||
256 | ElfSym::mipsGp = addAbsolute("_gp"); | |||
257 | ||||
258 | // On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between | |||
259 | // start of function and 'gp' pointer into GOT. | |||
260 | if (symtab->find("_gp_disp")) | |||
261 | ElfSym::mipsGpDisp = addAbsolute("_gp_disp"); | |||
262 | ||||
263 | // The __gnu_local_gp is a magic symbol equal to the current value of 'gp' | |||
264 | // pointer. This symbol is used in the code generated by .cpload pseudo-op | |||
265 | // in case of using -mno-shared option. | |||
266 | // https://sourceware.org/ml/binutils/2004-12/msg00094.html | |||
267 | if (symtab->find("__gnu_local_gp")) | |||
268 | ElfSym::mipsLocalGp = addAbsolute("__gnu_local_gp"); | |||
269 | } else if (config->emachine == EM_PPC) { | |||
270 | // glibc *crt1.o has a undefined reference to _SDA_BASE_. Since we don't | |||
271 | // support Small Data Area, define it arbitrarily as 0. | |||
272 | addOptionalRegular("_SDA_BASE_", nullptr, 0, STV_HIDDEN); | |||
273 | } else if (config->emachine == EM_PPC64) { | |||
274 | addPPC64SaveRestore(); | |||
275 | } | |||
276 | ||||
277 | // The Power Architecture 64-bit v2 ABI defines a TableOfContents (TOC) which | |||
278 | // combines the typical ELF GOT with the small data sections. It commonly | |||
279 | // includes .got .toc .sdata .sbss. The .TOC. symbol replaces both | |||
280 | // _GLOBAL_OFFSET_TABLE_ and _SDA_BASE_ from the 32-bit ABI. It is used to | |||
281 | // represent the TOC base which is offset by 0x8000 bytes from the start of | |||
282 | // the .got section. | |||
283 | // We do not allow _GLOBAL_OFFSET_TABLE_ to be defined by input objects as the | |||
284 | // correctness of some relocations depends on its value. | |||
285 | StringRef gotSymName = | |||
286 | (config->emachine == EM_PPC64) ? ".TOC." : "_GLOBAL_OFFSET_TABLE_"; | |||
287 | ||||
288 | if (Symbol *s = symtab->find(gotSymName)) { | |||
289 | if (s->isDefined()) { | |||
290 | error(toString(s->file) + " cannot redefine linker defined symbol '" + | |||
291 | gotSymName + "'"); | |||
292 | return; | |||
293 | } | |||
294 | ||||
295 | uint64_t gotOff = 0; | |||
296 | if (config->emachine == EM_PPC64) | |||
297 | gotOff = 0x8000; | |||
298 | ||||
299 | s->resolve(Defined{/*file=*/nullptr, gotSymName, STB_GLOBAL, STV_HIDDEN, | |||
300 | STT_NOTYPE, gotOff, /*size=*/0, Out::elfHeader}); | |||
301 | ElfSym::globalOffsetTable = cast<Defined>(s); | |||
302 | } | |||
303 | ||||
304 | // __ehdr_start is the location of ELF file headers. Note that we define | |||
305 | // this symbol unconditionally even when using a linker script, which | |||
306 | // differs from the behavior implemented by GNU linker which only define | |||
307 | // this symbol if ELF headers are in the memory mapped segment. | |||
308 | addOptionalRegular("__ehdr_start", Out::elfHeader, 0, STV_HIDDEN); | |||
309 | ||||
310 | // __executable_start is not documented, but the expectation of at | |||
311 | // least the Android libc is that it points to the ELF header. | |||
312 | addOptionalRegular("__executable_start", Out::elfHeader, 0, STV_HIDDEN); | |||
313 | ||||
314 | // __dso_handle symbol is passed to cxa_finalize as a marker to identify | |||
315 | // each DSO. The address of the symbol doesn't matter as long as they are | |||
316 | // different in different DSOs, so we chose the start address of the DSO. | |||
317 | addOptionalRegular("__dso_handle", Out::elfHeader, 0, STV_HIDDEN); | |||
318 | ||||
319 | // If linker script do layout we do not need to create any standard symbols. | |||
320 | if (script->hasSectionsCommand) | |||
321 | return; | |||
322 | ||||
323 | auto add = [](StringRef s, int64_t pos) { | |||
324 | return addOptionalRegular(s, Out::elfHeader, pos, STV_DEFAULT); | |||
325 | }; | |||
326 | ||||
327 | ElfSym::bss = add("__bss_start", 0); | |||
328 | ElfSym::data = add("__data_start", 0); | |||
329 | ElfSym::end1 = add("end", -1); | |||
330 | ElfSym::end2 = add("_end", -1); | |||
331 | ElfSym::etext1 = add("etext", -1); | |||
332 | ElfSym::etext2 = add("_etext", -1); | |||
333 | ElfSym::edata1 = add("edata", -1); | |||
334 | ElfSym::edata2 = add("_edata", -1); | |||
335 | } | |||
336 | ||||
337 | static OutputSection *findSection(StringRef name, unsigned partition = 1) { | |||
338 | for (BaseCommand *base : script->sectionCommands) | |||
339 | if (auto *sec = dyn_cast<OutputSection>(base)) | |||
340 | if (sec->name == name && sec->partition == partition) | |||
341 | return sec; | |||
342 | return nullptr; | |||
343 | } | |||
344 | ||||
345 | template <class ELFT> void elf::createSyntheticSections() { | |||
346 | // Initialize all pointers with NULL. This is needed because | |||
347 | // you can call lld::elf::main more than once as a library. | |||
348 | memset(&Out::first, 0, sizeof(Out)); | |||
349 | ||||
350 | // Add the .interp section first because it is not a SyntheticSection. | |||
351 | // The removeUnusedSyntheticSections() function relies on the | |||
352 | // SyntheticSections coming last. | |||
353 | if (needsInterpSection()) { | |||
354 | for (size_t i = 1; i <= partitions.size(); ++i) { | |||
355 | InputSection *sec = createInterpSection(); | |||
356 | sec->partition = i; | |||
357 | inputSections.push_back(sec); | |||
358 | } | |||
359 | } | |||
360 | ||||
361 | auto add = [](SyntheticSection *sec) { inputSections.push_back(sec); }; | |||
362 | ||||
363 | in.shStrTab = make<StringTableSection>(".shstrtab", false); | |||
364 | ||||
365 | Out::programHeaders = make<OutputSection>("", 0, SHF_ALLOC); | |||
366 | Out::programHeaders->alignment = config->wordsize; | |||
367 | ||||
368 | if (config->strip != StripPolicy::All) { | |||
369 | in.strTab = make<StringTableSection>(".strtab", false); | |||
370 | in.symTab = make<SymbolTableSection<ELFT>>(*in.strTab); | |||
371 | in.symTabShndx = make<SymtabShndxSection>(); | |||
372 | } | |||
373 | ||||
374 | in.bss = make<BssSection>(".bss", 0, 1); | |||
375 | add(in.bss); | |||
376 | ||||
377 | // If there is a SECTIONS command and a .data.rel.ro section name use name | |||
378 | // .data.rel.ro.bss so that we match in the .data.rel.ro output section. | |||
379 | // This makes sure our relro is contiguous. | |||
380 | bool hasDataRelRo = | |||
381 | script->hasSectionsCommand && findSection(".data.rel.ro", 0); | |||
382 | in.bssRelRo = | |||
383 | make<BssSection>(hasDataRelRo ? ".data.rel.ro.bss" : ".bss.rel.ro", 0, 1); | |||
384 | add(in.bssRelRo); | |||
385 | ||||
386 | // Add MIPS-specific sections. | |||
387 | if (config->emachine == EM_MIPS) { | |||
388 | if (!config->shared && config->hasDynSymTab) { | |||
389 | in.mipsRldMap = make<MipsRldMapSection>(); | |||
390 | add(in.mipsRldMap); | |||
391 | } | |||
392 | if (auto *sec = MipsAbiFlagsSection<ELFT>::create()) | |||
393 | add(sec); | |||
394 | if (auto *sec = MipsOptionsSection<ELFT>::create()) | |||
395 | add(sec); | |||
396 | if (auto *sec = MipsReginfoSection<ELFT>::create()) | |||
397 | add(sec); | |||
398 | } | |||
399 | ||||
400 | StringRef relaDynName = config->isRela ? ".rela.dyn" : ".rel.dyn"; | |||
401 | ||||
402 | for (Partition &part : partitions) { | |||
403 | auto add = [&](SyntheticSection *sec) { | |||
404 | sec->partition = part.getNumber(); | |||
405 | inputSections.push_back(sec); | |||
406 | }; | |||
407 | ||||
408 | if (!part.name.empty()) { | |||
409 | part.elfHeader = make<PartitionElfHeaderSection<ELFT>>(); | |||
410 | part.elfHeader->name = part.name; | |||
411 | add(part.elfHeader); | |||
412 | ||||
413 | part.programHeaders = make<PartitionProgramHeadersSection<ELFT>>(); | |||
414 | add(part.programHeaders); | |||
415 | } | |||
416 | ||||
417 | if (config->buildId != BuildIdKind::None) { | |||
418 | part.buildId = make<BuildIdSection>(); | |||
419 | add(part.buildId); | |||
420 | } | |||
421 | ||||
422 | part.dynStrTab = make<StringTableSection>(".dynstr", true); | |||
423 | part.dynSymTab = make<SymbolTableSection<ELFT>>(*part.dynStrTab); | |||
424 | part.dynamic = make<DynamicSection<ELFT>>(); | |||
425 | if (config->androidPackDynRelocs) | |||
426 | part.relaDyn = make<AndroidPackedRelocationSection<ELFT>>(relaDynName); | |||
427 | else | |||
428 | part.relaDyn = | |||
429 | make<RelocationSection<ELFT>>(relaDynName, config->zCombreloc); | |||
430 | ||||
431 | if (config->hasDynSymTab) { | |||
432 | part.dynSymTab = make<SymbolTableSection<ELFT>>(*part.dynStrTab); | |||
433 | add(part.dynSymTab); | |||
434 | ||||
435 | part.verSym = make<VersionTableSection>(); | |||
436 | add(part.verSym); | |||
437 | ||||
438 | if (!namedVersionDefs().empty()) { | |||
439 | part.verDef = make<VersionDefinitionSection>(); | |||
440 | add(part.verDef); | |||
441 | } | |||
442 | ||||
443 | part.verNeed = make<VersionNeedSection<ELFT>>(); | |||
444 | add(part.verNeed); | |||
445 | ||||
446 | if (config->gnuHash) { | |||
447 | part.gnuHashTab = make<GnuHashTableSection>(); | |||
448 | add(part.gnuHashTab); | |||
449 | } | |||
450 | ||||
451 | if (config->sysvHash) { | |||
452 | part.hashTab = make<HashTableSection>(); | |||
453 | add(part.hashTab); | |||
454 | } | |||
455 | ||||
456 | add(part.dynamic); | |||
457 | add(part.dynStrTab); | |||
458 | add(part.relaDyn); | |||
459 | } | |||
460 | ||||
461 | if (config->relrPackDynRelocs) { | |||
462 | part.relrDyn = make<RelrSection<ELFT>>(); | |||
463 | add(part.relrDyn); | |||
464 | } | |||
465 | ||||
466 | if (!config->relocatable) { | |||
467 | if (config->ehFrameHdr) { | |||
468 | part.ehFrameHdr = make<EhFrameHeader>(); | |||
469 | add(part.ehFrameHdr); | |||
470 | } | |||
471 | part.ehFrame = make<EhFrameSection>(); | |||
472 | add(part.ehFrame); | |||
473 | } | |||
474 | ||||
475 | if (config->emachine == EM_ARM && !config->relocatable) { | |||
476 | // The ARMExidxsyntheticsection replaces all the individual .ARM.exidx | |||
477 | // InputSections. | |||
478 | part.armExidx = make<ARMExidxSyntheticSection>(); | |||
479 | add(part.armExidx); | |||
480 | } | |||
481 | } | |||
482 | ||||
483 | if (partitions.size() != 1) { | |||
484 | // Create the partition end marker. This needs to be in partition number 255 | |||
485 | // so that it is sorted after all other partitions. It also has other | |||
486 | // special handling (see createPhdrs() and combineEhSections()). | |||
487 | in.partEnd = make<BssSection>(".part.end", config->maxPageSize, 1); | |||
488 | in.partEnd->partition = 255; | |||
489 | add(in.partEnd); | |||
490 | ||||
491 | in.partIndex = make<PartitionIndexSection>(); | |||
492 | addOptionalRegular("__part_index_begin", in.partIndex, 0); | |||
493 | addOptionalRegular("__part_index_end", in.partIndex, | |||
494 | in.partIndex->getSize()); | |||
495 | add(in.partIndex); | |||
496 | } | |||
497 | ||||
498 | // Add .got. MIPS' .got is so different from the other archs, | |||
499 | // it has its own class. | |||
500 | if (config->emachine == EM_MIPS) { | |||
501 | in.mipsGot = make<MipsGotSection>(); | |||
502 | add(in.mipsGot); | |||
503 | } else { | |||
504 | in.got = make<GotSection>(); | |||
505 | add(in.got); | |||
506 | } | |||
507 | ||||
508 | if (config->emachine == EM_PPC) { | |||
509 | in.ppc32Got2 = make<PPC32Got2Section>(); | |||
510 | add(in.ppc32Got2); | |||
511 | } | |||
512 | ||||
513 | if (config->emachine == EM_PPC64) { | |||
514 | in.ppc64LongBranchTarget = make<PPC64LongBranchTargetSection>(); | |||
515 | add(in.ppc64LongBranchTarget); | |||
516 | } | |||
517 | ||||
518 | in.gotPlt = make<GotPltSection>(); | |||
519 | add(in.gotPlt); | |||
520 | in.igotPlt = make<IgotPltSection>(); | |||
521 | add(in.igotPlt); | |||
522 | ||||
523 | // _GLOBAL_OFFSET_TABLE_ is defined relative to either .got.plt or .got. Treat | |||
524 | // it as a relocation and ensure the referenced section is created. | |||
525 | if (ElfSym::globalOffsetTable && config->emachine != EM_MIPS) { | |||
526 | if (target->gotBaseSymInGotPlt) | |||
527 | in.gotPlt->hasGotPltOffRel = true; | |||
528 | else | |||
529 | in.got->hasGotOffRel = true; | |||
530 | } | |||
531 | ||||
532 | if (config->gdbIndex) | |||
533 | add(GdbIndexSection::create<ELFT>()); | |||
534 | ||||
535 | // We always need to add rel[a].plt to output if it has entries. | |||
536 | // Even for static linking it can contain R_[*]_IRELATIVE relocations. | |||
537 | in.relaPlt = make<RelocationSection<ELFT>>( | |||
538 | config->isRela ? ".rela.plt" : ".rel.plt", /*sort=*/false); | |||
539 | add(in.relaPlt); | |||
540 | ||||
541 | // The relaIplt immediately follows .rel[a].dyn to ensure that the IRelative | |||
542 | // relocations are processed last by the dynamic loader. We cannot place the | |||
543 | // iplt section in .rel.dyn when Android relocation packing is enabled because | |||
544 | // that would cause a section type mismatch. However, because the Android | |||
545 | // dynamic loader reads .rel.plt after .rel.dyn, we can get the desired | |||
546 | // behaviour by placing the iplt section in .rel.plt. | |||
547 | in.relaIplt = make<RelocationSection<ELFT>>( | |||
548 | config->androidPackDynRelocs ? in.relaPlt->name : relaDynName, | |||
549 | /*sort=*/false); | |||
550 | add(in.relaIplt); | |||
551 | ||||
552 | if ((config->emachine == EM_386 || config->emachine == EM_X86_64) && | |||
553 | (config->andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT)) { | |||
554 | in.ibtPlt = make<IBTPltSection>(); | |||
555 | add(in.ibtPlt); | |||
556 | } | |||
557 | ||||
558 | in.plt = config->emachine == EM_PPC ? make<PPC32GlinkSection>() | |||
559 | : make<PltSection>(); | |||
560 | add(in.plt); | |||
561 | in.iplt = make<IpltSection>(); | |||
562 | add(in.iplt); | |||
563 | ||||
564 | if (config->andFeatures) | |||
565 | add(make<GnuPropertySection>()); | |||
566 | ||||
567 | // .note.GNU-stack is always added when we are creating a re-linkable | |||
568 | // object file. Other linkers are using the presence of this marker | |||
569 | // section to control the executable-ness of the stack area, but that | |||
570 | // is irrelevant these days. Stack area should always be non-executable | |||
571 | // by default. So we emit this section unconditionally. | |||
572 | if (config->relocatable) | |||
573 | add(make<GnuStackSection>()); | |||
574 | ||||
575 | if (in.symTab) | |||
576 | add(in.symTab); | |||
577 | if (in.symTabShndx) | |||
578 | add(in.symTabShndx); | |||
579 | add(in.shStrTab); | |||
580 | if (in.strTab) | |||
581 | add(in.strTab); | |||
582 | } | |||
583 | ||||
584 | // The main function of the writer. | |||
585 | template <class ELFT> void Writer<ELFT>::run() { | |||
586 | copyLocalSymbols(); | |||
587 | ||||
588 | if (config->copyRelocs) | |||
589 | addSectionSymbols(); | |||
590 | ||||
591 | // Now that we have a complete set of output sections. This function | |||
592 | // completes section contents. For example, we need to add strings | |||
593 | // to the string table, and add entries to .got and .plt. | |||
594 | // finalizeSections does that. | |||
595 | finalizeSections(); | |||
596 | checkExecuteOnly(); | |||
597 | if (errorCount()) | |||
598 | return; | |||
599 | ||||
600 | // If -compressed-debug-sections is specified, we need to compress | |||
601 | // .debug_* sections. Do it right now because it changes the size of | |||
602 | // output sections. | |||
603 | for (OutputSection *sec : outputSections) | |||
604 | sec->maybeCompress<ELFT>(); | |||
605 | ||||
606 | if (script->hasSectionsCommand) | |||
607 | script->allocateHeaders(mainPart->phdrs); | |||
608 | ||||
609 | // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a | |||
610 | // 0 sized region. This has to be done late since only after assignAddresses | |||
611 | // we know the size of the sections. | |||
612 | for (Partition &part : partitions) | |||
613 | removeEmptyPTLoad(part.phdrs); | |||
614 | ||||
615 | if (!config->oFormatBinary) | |||
616 | assignFileOffsets(); | |||
617 | else | |||
618 | assignFileOffsetsBinary(); | |||
619 | ||||
620 | for (Partition &part : partitions) | |||
621 | setPhdrs(part); | |||
622 | ||||
623 | if (config->relocatable) | |||
624 | for (OutputSection *sec : outputSections) | |||
625 | sec->addr = 0; | |||
626 | ||||
627 | // Handle --print-map(-M)/--Map, --cref and --print-archive-stats=. Dump them | |||
628 | // before checkSections() because the files may be useful in case | |||
629 | // checkSections() or openFile() fails, for example, due to an erroneous file | |||
630 | // size. | |||
631 | writeMapFile(); | |||
632 | writeCrossReferenceTable(); | |||
633 | writeArchiveStats(); | |||
634 | ||||
635 | if (config->checkSections) | |||
636 | checkSections(); | |||
637 | ||||
638 | // It does not make sense try to open the file if we have error already. | |||
639 | if (errorCount()) | |||
640 | return; | |||
641 | ||||
642 | { | |||
643 | llvm::TimeTraceScope timeScope("Write output file"); | |||
644 | // Write the result down to a file. | |||
645 | openFile(); | |||
646 | if (errorCount()) | |||
647 | return; | |||
648 | ||||
649 | if (!config->oFormatBinary) { | |||
650 | if (config->zSeparate != SeparateSegmentKind::None) | |||
651 | writeTrapInstr(); | |||
652 | writeHeader(); | |||
653 | writeSections(); | |||
654 | } else { | |||
655 | writeSectionsBinary(); | |||
656 | } | |||
657 | ||||
658 | // Backfill .note.gnu.build-id section content. This is done at last | |||
659 | // because the content is usually a hash value of the entire output file. | |||
660 | writeBuildId(); | |||
661 | if (errorCount()) | |||
662 | return; | |||
663 | ||||
664 | if (auto e = buffer->commit()) | |||
665 | error("failed to write to the output file: " + toString(std::move(e))); | |||
666 | } | |||
667 | } | |||
668 | ||||
669 | template <class ELFT, class RelTy> | |||
670 | static void markUsedLocalSymbolsImpl(ObjFile<ELFT> *file, | |||
671 | llvm::ArrayRef<RelTy> rels) { | |||
672 | for (const RelTy &rel : rels) { | |||
673 | Symbol &sym = file->getRelocTargetSym(rel); | |||
674 | if (sym.isLocal()) | |||
675 | sym.used = true; | |||
676 | } | |||
677 | } | |||
678 | ||||
679 | // The function ensures that the "used" field of local symbols reflects the fact | |||
680 | // that the symbol is used in a relocation from a live section. | |||
681 | template <class ELFT> static void markUsedLocalSymbols() { | |||
682 | // With --gc-sections, the field is already filled. | |||
683 | // See MarkLive<ELFT>::resolveReloc(). | |||
684 | if (config->gcSections) | |||
685 | return; | |||
686 | // Without --gc-sections, the field is initialized with "true". | |||
687 | // Drop the flag first and then rise for symbols referenced in relocations. | |||
688 | for (InputFile *file : objectFiles) { | |||
689 | ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file); | |||
690 | for (Symbol *b : f->getLocalSymbols()) | |||
691 | b->used = false; | |||
692 | for (InputSectionBase *s : f->getSections()) { | |||
693 | InputSection *isec = dyn_cast_or_null<InputSection>(s); | |||
694 | if (!isec) | |||
695 | continue; | |||
696 | if (isec->type == SHT_REL) | |||
697 | markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rel>()); | |||
698 | else if (isec->type == SHT_RELA) | |||
699 | markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rela>()); | |||
700 | } | |||
701 | } | |||
702 | } | |||
703 | ||||
704 | static bool shouldKeepInSymtab(const Defined &sym) { | |||
705 | if (sym.isSection()) | |||
706 | return false; | |||
707 | ||||
708 | // If --emit-reloc or -r is given, preserve symbols referenced by relocations | |||
709 | // from live sections. | |||
710 | if (config->copyRelocs && sym.used) | |||
711 | return true; | |||
712 | ||||
713 | // Exclude local symbols pointing to .ARM.exidx sections. | |||
714 | // They are probably mapping symbols "$d", which are optional for these | |||
715 | // sections. After merging the .ARM.exidx sections, some of these symbols | |||
716 | // may become dangling. The easiest way to avoid the issue is not to add | |||
717 | // them to the symbol table from the beginning. | |||
718 | if (config->emachine == EM_ARM && sym.section && | |||
719 | sym.section->type == SHT_ARM_EXIDX) | |||
720 | return false; | |||
721 | ||||
722 | if (config->discard == DiscardPolicy::None) | |||
723 | return true; | |||
724 | if (config->discard == DiscardPolicy::All) | |||
725 | return false; | |||
726 | ||||
727 | // In ELF assembly .L symbols are normally discarded by the assembler. | |||
728 | // If the assembler fails to do so, the linker discards them if | |||
729 | // * --discard-locals is used. | |||
730 | // * The symbol is in a SHF_MERGE section, which is normally the reason for | |||
731 | // the assembler keeping the .L symbol. | |||
732 | StringRef name = sym.getName(); | |||
733 | bool isLocal = name.startswith(".L") || name.empty(); | |||
734 | if (!isLocal) | |||
735 | return true; | |||
736 | ||||
737 | if (config->discard == DiscardPolicy::Locals) | |||
738 | return false; | |||
739 | ||||
740 | SectionBase *sec = sym.section; | |||
741 | return !sec || !(sec->flags & SHF_MERGE); | |||
742 | } | |||
743 | ||||
744 | static bool includeInSymtab(const Symbol &b) { | |||
745 | if (!b.isLocal() && !b.isUsedInRegularObj) | |||
746 | return false; | |||
747 | ||||
748 | if (auto *d = dyn_cast<Defined>(&b)) { | |||
749 | // Always include absolute symbols. | |||
750 | SectionBase *sec = d->section; | |||
751 | if (!sec) | |||
752 | return true; | |||
753 | sec = sec->repl; | |||
754 | ||||
755 | // Exclude symbols pointing to garbage-collected sections. | |||
756 | if (isa<InputSectionBase>(sec) && !sec->isLive()) | |||
757 | return false; | |||
758 | ||||
759 | if (auto *s = dyn_cast<MergeInputSection>(sec)) | |||
760 | if (!s->getSectionPiece(d->value)->live) | |||
761 | return false; | |||
762 | return true; | |||
763 | } | |||
764 | return b.used; | |||
765 | } | |||
766 | ||||
767 | // Local symbols are not in the linker's symbol table. This function scans | |||
768 | // each object file's symbol table to copy local symbols to the output. | |||
769 | template <class ELFT> void Writer<ELFT>::copyLocalSymbols() { | |||
770 | if (!in.symTab) | |||
771 | return; | |||
772 | llvm::TimeTraceScope timeScope("Add local symbols"); | |||
773 | if (config->copyRelocs && config->discard != DiscardPolicy::None) | |||
774 | markUsedLocalSymbols<ELFT>(); | |||
775 | for (InputFile *file : objectFiles) { | |||
776 | ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file); | |||
777 | for (Symbol *b : f->getLocalSymbols()) { | |||
778 | assert(b->isLocal() && "should have been caught in initializeSymbols()")((void)0); | |||
779 | auto *dr = dyn_cast<Defined>(b); | |||
780 | ||||
781 | // No reason to keep local undefined symbol in symtab. | |||
782 | if (!dr) | |||
783 | continue; | |||
784 | if (!includeInSymtab(*b)) | |||
785 | continue; | |||
786 | if (!shouldKeepInSymtab(*dr)) | |||
787 | continue; | |||
788 | in.symTab->addSymbol(b); | |||
789 | } | |||
790 | } | |||
791 | } | |||
792 | ||||
793 | // Create a section symbol for each output section so that we can represent | |||
794 | // relocations that point to the section. If we know that no relocation is | |||
795 | // referring to a section (that happens if the section is a synthetic one), we | |||
796 | // don't create a section symbol for that section. | |||
797 | template <class ELFT> void Writer<ELFT>::addSectionSymbols() { | |||
798 | for (BaseCommand *base : script->sectionCommands) { | |||
799 | auto *sec = dyn_cast<OutputSection>(base); | |||
800 | if (!sec) | |||
801 | continue; | |||
802 | auto i = llvm::find_if(sec->sectionCommands, [](BaseCommand *base) { | |||
803 | if (auto *isd = dyn_cast<InputSectionDescription>(base)) | |||
804 | return !isd->sections.empty(); | |||
805 | return false; | |||
806 | }); | |||
807 | if (i == sec->sectionCommands.end()) | |||
808 | continue; | |||
809 | InputSectionBase *isec = cast<InputSectionDescription>(*i)->sections[0]; | |||
810 | ||||
811 | // Relocations are not using REL[A] section symbols. | |||
812 | if (isec->type == SHT_REL || isec->type == SHT_RELA) | |||
813 | continue; | |||
814 | ||||
815 | // Unlike other synthetic sections, mergeable output sections contain data | |||
816 | // copied from input sections, and there may be a relocation pointing to its | |||
817 | // contents if -r or -emit-reloc are given. | |||
818 | if (isa<SyntheticSection>(isec) && !(isec->flags & SHF_MERGE)) | |||
819 | continue; | |||
820 | ||||
821 | // Set the symbol to be relative to the output section so that its st_value | |||
822 | // equals the output section address. Note, there may be a gap between the | |||
823 | // start of the output section and isec. | |||
824 | auto *sym = | |||
825 | make<Defined>(isec->file, "", STB_LOCAL, /*stOther=*/0, STT_SECTION, | |||
826 | /*value=*/0, /*size=*/0, isec->getOutputSection()); | |||
827 | in.symTab->addSymbol(sym); | |||
828 | } | |||
829 | } | |||
830 | ||||
831 | // Today's loaders have a feature to make segments read-only after | |||
832 | // processing dynamic relocations to enhance security. PT_GNU_RELRO | |||
833 | // is defined for that. | |||
834 | // | |||
835 | // This function returns true if a section needs to be put into a | |||
836 | // PT_GNU_RELRO segment. | |||
837 | static bool isRelroSection(const OutputSection *sec) { | |||
838 | if (!config->zRelro) | |||
839 | return false; | |||
840 | ||||
841 | uint64_t flags = sec->flags; | |||
842 | ||||
843 | // Non-allocatable or non-writable sections don't need RELRO because | |||
844 | // they are not writable or not even mapped to memory in the first place. | |||
845 | // RELRO is for sections that are essentially read-only but need to | |||
846 | // be writable only at process startup to allow dynamic linker to | |||
847 | // apply relocations. | |||
848 | if (!(flags & SHF_ALLOC) || !(flags & SHF_WRITE)) | |||
849 | return false; | |||
850 | ||||
851 | // Once initialized, TLS data segments are used as data templates | |||
852 | // for a thread-local storage. For each new thread, runtime | |||
853 | // allocates memory for a TLS and copy templates there. No thread | |||
854 | // are supposed to use templates directly. Thus, it can be in RELRO. | |||
855 | if (flags & SHF_TLS) | |||
856 | return true; | |||
857 | ||||
858 | // .init_array, .preinit_array and .fini_array contain pointers to | |||
859 | // functions that are executed on process startup or exit. These | |||
860 | // pointers are set by the static linker, and they are not expected | |||
861 | // to change at runtime. But if you are an attacker, you could do | |||
862 | // interesting things by manipulating pointers in .fini_array, for | |||
863 | // example. So they are put into RELRO. | |||
864 | uint32_t type = sec->type; | |||
865 | if (type == SHT_INIT_ARRAY || type == SHT_FINI_ARRAY || | |||
866 | type == SHT_PREINIT_ARRAY) | |||
867 | return true; | |||
868 | ||||
869 | // .got contains pointers to external symbols. They are resolved by | |||
870 | // the dynamic linker when a module is loaded into memory, and after | |||
871 | // that they are not expected to change. So, it can be in RELRO. | |||
872 | if (in.got && sec == in.got->getParent()) | |||
873 | return true; | |||
874 | ||||
875 | // .toc is a GOT-ish section for PowerPC64. Their contents are accessed | |||
876 | // through r2 register, which is reserved for that purpose. Since r2 is used | |||
877 | // for accessing .got as well, .got and .toc need to be close enough in the | |||
878 | // virtual address space. Usually, .toc comes just after .got. Since we place | |||
879 | // .got into RELRO, .toc needs to be placed into RELRO too. | |||
880 | if (sec->name.equals(".toc")) | |||
881 | return true; | |||
882 | ||||
883 | // .got.plt contains pointers to external function symbols. They are | |||
884 | // by default resolved lazily, so we usually cannot put it into RELRO. | |||
885 | // However, if "-z now" is given, the lazy symbol resolution is | |||
886 | // disabled, which enables us to put it into RELRO. | |||
887 | if (sec == in.gotPlt->getParent()) | |||
888 | #ifndef __OpenBSD__1 | |||
889 | return config->zNow; | |||
890 | #else | |||
891 | return true; /* kbind(2) means we can always put these in RELRO */ | |||
892 | #endif | |||
893 | ||||
894 | // .dynamic section contains data for the dynamic linker, and | |||
895 | // there's no need to write to it at runtime, so it's better to put | |||
896 | // it into RELRO. | |||
897 | if (sec->name == ".dynamic") | |||
898 | return true; | |||
899 | ||||
900 | // Sections with some special names are put into RELRO. This is a | |||
901 | // bit unfortunate because section names shouldn't be significant in | |||
902 | // ELF in spirit. But in reality many linker features depend on | |||
903 | // magic section names. | |||
904 | StringRef s = sec->name; | |||
905 | return s == ".data.rel.ro" || s == ".bss.rel.ro" || s == ".ctors" || | |||
906 | s == ".dtors" || s == ".jcr" || s == ".eh_frame" || | |||
907 | s == ".fini_array" || s == ".init_array" || | |||
908 | s == ".openbsd.randomdata" || s == ".preinit_array"; | |||
909 | } | |||
910 | ||||
911 | // We compute a rank for each section. The rank indicates where the | |||
912 | // section should be placed in the file. Instead of using simple | |||
913 | // numbers (0,1,2...), we use a series of flags. One for each decision | |||
914 | // point when placing the section. | |||
915 | // Using flags has two key properties: | |||
916 | // * It is easy to check if a give branch was taken. | |||
917 | // * It is easy two see how similar two ranks are (see getRankProximity). | |||
918 | enum RankFlags { | |||
919 | RF_NOT_ADDR_SET = 1 << 27, | |||
920 | RF_NOT_ALLOC = 1 << 26, | |||
921 | RF_PARTITION = 1 << 18, // Partition number (8 bits) | |||
922 | RF_NOT_PART_EHDR = 1 << 17, | |||
923 | RF_NOT_PART_PHDR = 1 << 16, | |||
924 | RF_NOT_INTERP = 1 << 15, | |||
925 | RF_NOT_NOTE = 1 << 14, | |||
926 | RF_WRITE = 1 << 13, | |||
927 | RF_EXEC_WRITE = 1 << 12, | |||
928 | RF_EXEC = 1 << 11, | |||
929 | RF_RODATA = 1 << 10, | |||
930 | RF_NOT_RELRO = 1 << 9, | |||
931 | RF_NOT_TLS = 1 << 8, | |||
932 | RF_BSS = 1 << 7, | |||
933 | RF_PPC_NOT_TOCBSS = 1 << 6, | |||
934 | RF_PPC_TOCL = 1 << 5, | |||
935 | RF_PPC_TOC = 1 << 4, | |||
936 | RF_PPC_GOT = 1 << 3, | |||
937 | RF_PPC_BRANCH_LT = 1 << 2, | |||
938 | RF_MIPS_GPREL = 1 << 1, | |||
939 | RF_MIPS_NOT_GOT = 1 << 0 | |||
940 | }; | |||
941 | ||||
942 | static unsigned getSectionRank(const OutputSection *sec) { | |||
943 | unsigned rank = sec->partition * RF_PARTITION; | |||
944 | ||||
945 | // We want to put section specified by -T option first, so we | |||
946 | // can start assigning VA starting from them later. | |||
947 | if (config->sectionStartMap.count(sec->name)) | |||
948 | return rank; | |||
949 | rank |= RF_NOT_ADDR_SET; | |||
950 | ||||
951 | // Allocatable sections go first to reduce the total PT_LOAD size and | |||
952 | // so debug info doesn't change addresses in actual code. | |||
953 | if (!(sec->flags & SHF_ALLOC)) | |||
954 | return rank | RF_NOT_ALLOC; | |||
955 | ||||
956 | if (sec->type == SHT_LLVM_PART_EHDR) | |||
957 | return rank; | |||
958 | rank |= RF_NOT_PART_EHDR; | |||
959 | ||||
960 | if (sec->type == SHT_LLVM_PART_PHDR) | |||
961 | return rank; | |||
962 | rank |= RF_NOT_PART_PHDR; | |||
963 | ||||
964 | // Put .interp first because some loaders want to see that section | |||
965 | // on the first page of the executable file when loaded into memory. | |||
966 | if (sec->name == ".interp") | |||
967 | return rank; | |||
968 | rank |= RF_NOT_INTERP; | |||
969 | ||||
970 | // Put .note sections (which make up one PT_NOTE) at the beginning so that | |||
971 | // they are likely to be included in a core file even if core file size is | |||
972 | // limited. In particular, we want a .note.gnu.build-id and a .note.tag to be | |||
973 | // included in a core to match core files with executables. | |||
974 | if (sec->type == SHT_NOTE) | |||
975 | return rank; | |||
976 | rank |= RF_NOT_NOTE; | |||
977 | ||||
978 | // Sort sections based on their access permission in the following | |||
979 | // order: R, RX, RWX, RW. This order is based on the following | |||
980 | // considerations: | |||
981 | // * Read-only sections come first such that they go in the | |||
982 | // PT_LOAD covering the program headers at the start of the file. | |||
983 | // * Read-only, executable sections come next. | |||
984 | // * Writable, executable sections follow such that .plt on | |||
985 | // architectures where it needs to be writable will be placed | |||
986 | // between .text and .data. | |||
987 | // * Writable sections come last, such that .bss lands at the very | |||
988 | // end of the last PT_LOAD. | |||
989 | bool isExec = sec->flags & SHF_EXECINSTR; | |||
990 | bool isWrite = sec->flags & SHF_WRITE; | |||
991 | ||||
992 | if (isExec) { | |||
993 | if (isWrite) | |||
994 | rank |= RF_EXEC_WRITE; | |||
995 | else | |||
996 | rank |= RF_EXEC; | |||
997 | } else if (isWrite) { | |||
998 | rank |= RF_WRITE; | |||
999 | } else if (sec->type == SHT_PROGBITS) { | |||
1000 | // Make non-executable and non-writable PROGBITS sections (e.g .rodata | |||
1001 | // .eh_frame) closer to .text. They likely contain PC or GOT relative | |||
1002 | // relocations and there could be relocation overflow if other huge sections | |||
1003 | // (.dynstr .dynsym) were placed in between. | |||
1004 | rank |= RF_RODATA; | |||
1005 | } | |||
1006 | ||||
1007 | // Place RelRo sections first. After considering SHT_NOBITS below, the | |||
1008 | // ordering is PT_LOAD(PT_GNU_RELRO(.data.rel.ro .bss.rel.ro) | .data .bss), | |||
1009 | // where | marks where page alignment happens. An alternative ordering is | |||
1010 | // PT_LOAD(.data | PT_GNU_RELRO( .data.rel.ro .bss.rel.ro) | .bss), but it may | |||
1011 | // waste more bytes due to 2 alignment places. | |||
1012 | if (!isRelroSection(sec)) | |||
1013 | rank |= RF_NOT_RELRO; | |||
1014 | ||||
1015 | // If we got here we know that both A and B are in the same PT_LOAD. | |||
1016 | ||||
1017 | // The TLS initialization block needs to be a single contiguous block in a R/W | |||
1018 | // PT_LOAD, so stick TLS sections directly before the other RelRo R/W | |||
1019 | // sections. Since p_filesz can be less than p_memsz, place NOBITS sections | |||
1020 | // after PROGBITS. | |||
1021 | if (!(sec->flags & SHF_TLS)) | |||
1022 | rank |= RF_NOT_TLS; | |||
1023 | ||||
1024 | // Within TLS sections, or within other RelRo sections, or within non-RelRo | |||
1025 | // sections, place non-NOBITS sections first. | |||
1026 | if (sec->type == SHT_NOBITS) | |||
1027 | rank |= RF_BSS; | |||
1028 | ||||
1029 | // Some architectures have additional ordering restrictions for sections | |||
1030 | // within the same PT_LOAD. | |||
1031 | if (config->emachine == EM_PPC64) { | |||
1032 | // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections | |||
1033 | // that we would like to make sure appear is a specific order to maximize | |||
1034 | // their coverage by a single signed 16-bit offset from the TOC base | |||
1035 | // pointer. Conversely, the special .tocbss section should be first among | |||
1036 | // all SHT_NOBITS sections. This will put it next to the loaded special | |||
1037 | // PPC64 sections (and, thus, within reach of the TOC base pointer). | |||
1038 | StringRef name = sec->name; | |||
1039 | if (name != ".tocbss") | |||
1040 | rank |= RF_PPC_NOT_TOCBSS; | |||
1041 | ||||
1042 | if (name == ".toc1") | |||
1043 | rank |= RF_PPC_TOCL; | |||
1044 | ||||
1045 | if (name == ".toc") | |||
1046 | rank |= RF_PPC_TOC; | |||
1047 | ||||
1048 | if (name == ".got") | |||
1049 | rank |= RF_PPC_GOT; | |||
1050 | ||||
1051 | if (name == ".branch_lt") | |||
1052 | rank |= RF_PPC_BRANCH_LT; | |||
1053 | } | |||
1054 | ||||
1055 | if (config->emachine == EM_MIPS) { | |||
1056 | // All sections with SHF_MIPS_GPREL flag should be grouped together | |||
1057 | // because data in these sections is addressable with a gp relative address. | |||
1058 | if (sec->flags & SHF_MIPS_GPREL) | |||
1059 | rank |= RF_MIPS_GPREL; | |||
1060 | ||||
1061 | if (sec->name != ".got") | |||
1062 | rank |= RF_MIPS_NOT_GOT; | |||
1063 | } | |||
1064 | ||||
1065 | return rank; | |||
1066 | } | |||
1067 | ||||
1068 | static bool compareSections(const BaseCommand *aCmd, const BaseCommand *bCmd) { | |||
1069 | const OutputSection *a = cast<OutputSection>(aCmd); | |||
1070 | const OutputSection *b = cast<OutputSection>(bCmd); | |||
1071 | ||||
1072 | if (a->sortRank != b->sortRank) | |||
1073 | return a->sortRank < b->sortRank; | |||
1074 | ||||
1075 | if (!(a->sortRank & RF_NOT_ADDR_SET)) | |||
1076 | return config->sectionStartMap.lookup(a->name) < | |||
1077 | config->sectionStartMap.lookup(b->name); | |||
1078 | return false; | |||
1079 | } | |||
1080 | ||||
1081 | void PhdrEntry::add(OutputSection *sec) { | |||
1082 | lastSec = sec; | |||
1083 | if (!firstSec) | |||
1084 | firstSec = sec; | |||
1085 | p_align = std::max(p_align, sec->alignment); | |||
1086 | if (p_type == PT_LOAD) | |||
1087 | sec->ptLoad = this; | |||
1088 | } | |||
1089 | ||||
1090 | // The beginning and the ending of .rel[a].plt section are marked | |||
1091 | // with __rel[a]_iplt_{start,end} symbols if it is a statically linked | |||
1092 | // executable. The runtime needs these symbols in order to resolve | |||
1093 | // all IRELATIVE relocs on startup. For dynamic executables, we don't | |||
1094 | // need these symbols, since IRELATIVE relocs are resolved through GOT | |||
1095 | // and PLT. For details, see http://www.airs.com/blog/archives/403. | |||
1096 | template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() { | |||
1097 | if (config->relocatable || config->isPic) | |||
1098 | return; | |||
1099 | ||||
1100 | // By default, __rela_iplt_{start,end} belong to a dummy section 0 | |||
1101 | // because .rela.plt might be empty and thus removed from output. | |||
1102 | // We'll override Out::elfHeader with In.relaIplt later when we are | |||
1103 | // sure that .rela.plt exists in output. | |||
1104 | ElfSym::relaIpltStart = addOptionalRegular( | |||
1105 | config->isRela ? "__rela_iplt_start" : "__rel_iplt_start", | |||
1106 | Out::elfHeader, 0, STV_HIDDEN, STB_WEAK); | |||
1107 | ||||
1108 | ElfSym::relaIpltEnd = addOptionalRegular( | |||
1109 | config->isRela ? "__rela_iplt_end" : "__rel_iplt_end", | |||
1110 | Out::elfHeader, 0, STV_HIDDEN, STB_WEAK); | |||
1111 | } | |||
1112 | ||||
1113 | template <class ELFT> | |||
1114 | void Writer<ELFT>::forEachRelSec( | |||
1115 | llvm::function_ref<void(InputSectionBase &)> fn) { | |||
1116 | // Scan all relocations. Each relocation goes through a series | |||
1117 | // of tests to determine if it needs special treatment, such as | |||
1118 | // creating GOT, PLT, copy relocations, etc. | |||
1119 | // Note that relocations for non-alloc sections are directly | |||
1120 | // processed by InputSection::relocateNonAlloc. | |||
1121 | for (InputSectionBase *isec : inputSections) | |||
1122 | if (isec->isLive() && isa<InputSection>(isec) && (isec->flags & SHF_ALLOC)) | |||
1123 | fn(*isec); | |||
1124 | for (Partition &part : partitions) { | |||
1125 | for (EhInputSection *es : part.ehFrame->sections) | |||
1126 | fn(*es); | |||
1127 | if (part.armExidx && part.armExidx->isLive()) | |||
1128 | for (InputSection *ex : part.armExidx->exidxSections) | |||
1129 | fn(*ex); | |||
1130 | } | |||
1131 | } | |||
1132 | ||||
1133 | // This function generates assignments for predefined symbols (e.g. _end or | |||
1134 | // _etext) and inserts them into the commands sequence to be processed at the | |||
1135 | // appropriate time. This ensures that the value is going to be correct by the | |||
1136 | // time any references to these symbols are processed and is equivalent to | |||
1137 | // defining these symbols explicitly in the linker script. | |||
1138 | template <class ELFT> void Writer<ELFT>::setReservedSymbolSections() { | |||
1139 | if (ElfSym::globalOffsetTable) { | |||
1140 | // The _GLOBAL_OFFSET_TABLE_ symbol is defined by target convention usually | |||
1141 | // to the start of the .got or .got.plt section. | |||
1142 | InputSection *gotSection = in.gotPlt; | |||
1143 | if (!target->gotBaseSymInGotPlt) | |||
1144 | gotSection = in.mipsGot ? cast<InputSection>(in.mipsGot) | |||
1145 | : cast<InputSection>(in.got); | |||
1146 | ElfSym::globalOffsetTable->section = gotSection; | |||
1147 | } | |||
1148 | ||||
1149 | // .rela_iplt_{start,end} mark the start and the end of in.relaIplt. | |||
1150 | if (ElfSym::relaIpltStart && in.relaIplt->isNeeded()) { | |||
1151 | ElfSym::relaIpltStart->section = in.relaIplt; | |||
1152 | ElfSym::relaIpltEnd->section = in.relaIplt; | |||
1153 | ElfSym::relaIpltEnd->value = in.relaIplt->getSize(); | |||
1154 | } | |||
1155 | ||||
1156 | PhdrEntry *last = nullptr; | |||
1157 | PhdrEntry *lastRO = nullptr; | |||
1158 | ||||
1159 | for (Partition &part : partitions) { | |||
1160 | for (PhdrEntry *p : part.phdrs) { | |||
1161 | if (p->p_type != PT_LOAD) | |||
1162 | continue; | |||
1163 | last = p; | |||
1164 | if (!(p->p_flags & PF_W)) | |||
1165 | lastRO = p; | |||
1166 | } | |||
1167 | } | |||
1168 | ||||
1169 | if (lastRO) { | |||
1170 | // _etext is the first location after the last read-only loadable segment. | |||
1171 | if (ElfSym::etext1) | |||
1172 | ElfSym::etext1->section = lastRO->lastSec; | |||
1173 | if (ElfSym::etext2) | |||
1174 | ElfSym::etext2->section = lastRO->lastSec; | |||
1175 | } | |||
1176 | ||||
1177 | if (last) { | |||
1178 | // _edata points to the end of the last mapped initialized section. | |||
1179 | OutputSection *edata = nullptr; | |||
1180 | for (OutputSection *os : outputSections) { | |||
1181 | if (os->type != SHT_NOBITS) | |||
1182 | edata = os; | |||
1183 | if (os == last->lastSec) | |||
1184 | break; | |||
1185 | } | |||
1186 | ||||
1187 | if (ElfSym::edata1) | |||
1188 | ElfSym::edata1->section = edata; | |||
1189 | if (ElfSym::edata2) | |||
1190 | ElfSym::edata2->section = edata; | |||
1191 | ||||
1192 | // _end is the first location after the uninitialized data region. | |||
1193 | if (ElfSym::end1) | |||
1194 | ElfSym::end1->section = last->lastSec; | |||
1195 | if (ElfSym::end2) | |||
1196 | ElfSym::end2->section = last->lastSec; | |||
1197 | } | |||
1198 | ||||
1199 | if (ElfSym::bss) | |||
1200 | ElfSym::bss->section = findSection(".bss"); | |||
1201 | ||||
1202 | if (ElfSym::data) | |||
1203 | ElfSym::data->section = findSection(".data"); | |||
1204 | ||||
1205 | // Setup MIPS _gp_disp/__gnu_local_gp symbols which should | |||
1206 | // be equal to the _gp symbol's value. | |||
1207 | if (ElfSym::mipsGp) { | |||
1208 | // Find GP-relative section with the lowest address | |||
1209 | // and use this address to calculate default _gp value. | |||
1210 | for (OutputSection *os : outputSections) { | |||
1211 | if (os->flags & SHF_MIPS_GPREL) { | |||
1212 | ElfSym::mipsGp->section = os; | |||
1213 | ElfSym::mipsGp->value = 0x7ff0; | |||
1214 | break; | |||
1215 | } | |||
1216 | } | |||
1217 | } | |||
1218 | } | |||
1219 | ||||
1220 | // We want to find how similar two ranks are. | |||
1221 | // The more branches in getSectionRank that match, the more similar they are. | |||
1222 | // Since each branch corresponds to a bit flag, we can just use | |||
1223 | // countLeadingZeros. | |||
1224 | static int getRankProximityAux(OutputSection *a, OutputSection *b) { | |||
1225 | return countLeadingZeros(a->sortRank ^ b->sortRank); | |||
1226 | } | |||
1227 | ||||
1228 | static int getRankProximity(OutputSection *a, BaseCommand *b) { | |||
1229 | auto *sec = dyn_cast<OutputSection>(b); | |||
1230 | return (sec && sec->hasInputSections) ? getRankProximityAux(a, sec) : -1; | |||
1231 | } | |||
1232 | ||||
1233 | // When placing orphan sections, we want to place them after symbol assignments | |||
1234 | // so that an orphan after | |||
1235 | // begin_foo = .; | |||
1236 | // foo : { *(foo) } | |||
1237 | // end_foo = .; | |||
1238 | // doesn't break the intended meaning of the begin/end symbols. | |||
1239 | // We don't want to go over sections since findOrphanPos is the | |||
1240 | // one in charge of deciding the order of the sections. | |||
1241 | // We don't want to go over changes to '.', since doing so in | |||
1242 | // rx_sec : { *(rx_sec) } | |||
1243 | // . = ALIGN(0x1000); | |||
1244 | // /* The RW PT_LOAD starts here*/ | |||
1245 | // rw_sec : { *(rw_sec) } | |||
1246 | // would mean that the RW PT_LOAD would become unaligned. | |||
1247 | static bool shouldSkip(BaseCommand *cmd) { | |||
1248 | if (auto *assign = dyn_cast<SymbolAssignment>(cmd)) | |||
1249 | return assign->name != "."; | |||
1250 | return false; | |||
1251 | } | |||
1252 | ||||
1253 | // We want to place orphan sections so that they share as much | |||
1254 | // characteristics with their neighbors as possible. For example, if | |||
1255 | // both are rw, or both are tls. | |||
1256 | static std::vector<BaseCommand *>::iterator | |||
1257 | findOrphanPos(std::vector<BaseCommand *>::iterator b, | |||
1258 | std::vector<BaseCommand *>::iterator e) { | |||
1259 | OutputSection *sec = cast<OutputSection>(*e); | |||
1260 | ||||
1261 | // Find the first element that has as close a rank as possible. | |||
1262 | auto i = std::max_element(b, e, [=](BaseCommand *a, BaseCommand *b) { | |||
1263 | return getRankProximity(sec, a) < getRankProximity(sec, b); | |||
1264 | }); | |||
1265 | if (i == e) | |||
1266 | return e; | |||
1267 | ||||
1268 | // Consider all existing sections with the same proximity. | |||
1269 | int proximity = getRankProximity(sec, *i); | |||
1270 | for (; i != e; ++i) { | |||
1271 | auto *curSec = dyn_cast<OutputSection>(*i); | |||
1272 | if (!curSec || !curSec->hasInputSections) | |||
1273 | continue; | |||
1274 | if (getRankProximity(sec, curSec) != proximity || | |||
1275 | sec->sortRank < curSec->sortRank) | |||
1276 | break; | |||
1277 | } | |||
1278 | ||||
1279 | auto isOutputSecWithInputSections = [](BaseCommand *cmd) { | |||
1280 | auto *os = dyn_cast<OutputSection>(cmd); | |||
1281 | return os && os->hasInputSections; | |||
1282 | }; | |||
1283 | auto j = std::find_if(llvm::make_reverse_iterator(i), | |||
1284 | llvm::make_reverse_iterator(b), | |||
1285 | isOutputSecWithInputSections); | |||
1286 | i = j.base(); | |||
1287 | ||||
1288 | // As a special case, if the orphan section is the last section, put | |||
1289 | // it at the very end, past any other commands. | |||
1290 | // This matches bfd's behavior and is convenient when the linker script fully | |||
1291 | // specifies the start of the file, but doesn't care about the end (the non | |||
1292 | // alloc sections for example). | |||
1293 | auto nextSec = std::find_if(i, e, isOutputSecWithInputSections); | |||
1294 | if (nextSec == e) | |||
1295 | return e; | |||
1296 | ||||
1297 | while (i != e && shouldSkip(*i)) | |||
1298 | ++i; | |||
1299 | return i; | |||
1300 | } | |||
1301 | ||||
1302 | // Adds random priorities to sections not already in the map. | |||
1303 | static void maybeShuffle(DenseMap<const InputSectionBase *, int> &order) { | |||
1304 | if (config->shuffleSections.empty()) | |||
1305 | return; | |||
1306 | ||||
1307 | std::vector<InputSectionBase *> matched, sections = inputSections; | |||
1308 | matched.reserve(sections.size()); | |||
1309 | for (const auto &patAndSeed : config->shuffleSections) { | |||
1310 | matched.clear(); | |||
1311 | for (InputSectionBase *sec : sections) | |||
1312 | if (patAndSeed.first.match(sec->name)) | |||
1313 | matched.push_back(sec); | |||
1314 | const uint32_t seed = patAndSeed.second; | |||
1315 | if (seed == UINT32_MAX0xffffffffU) { | |||
1316 | // If --shuffle-sections <section-glob>=-1, reverse the section order. The | |||
1317 | // section order is stable even if the number of sections changes. This is | |||
1318 | // useful to catch issues like static initialization order fiasco | |||
1319 | // reliably. | |||
1320 | std::reverse(matched.begin(), matched.end()); | |||
1321 | } else { | |||
1322 | std::mt19937 g(seed ? seed : std::random_device()()); | |||
1323 | llvm::shuffle(matched.begin(), matched.end(), g); | |||
1324 | } | |||
1325 | size_t i = 0; | |||
1326 | for (InputSectionBase *&sec : sections) | |||
1327 | if (patAndSeed.first.match(sec->name)) | |||
1328 | sec = matched[i++]; | |||
1329 | } | |||
1330 | ||||
1331 | // Existing priorities are < 0, so use priorities >= 0 for the missing | |||
1332 | // sections. | |||
1333 | int prio = 0; | |||
1334 | for (InputSectionBase *sec : sections) { | |||
1335 | if (order.try_emplace(sec, prio).second) | |||
1336 | ++prio; | |||
1337 | } | |||
1338 | } | |||
1339 | ||||
1340 | // Builds section order for handling --symbol-ordering-file. | |||
1341 | static DenseMap<const InputSectionBase *, int> buildSectionOrder() { | |||
1342 | DenseMap<const InputSectionBase *, int> sectionOrder; | |||
1343 | // Use the rarely used option -call-graph-ordering-file to sort sections. | |||
1344 | if (!config->callGraphProfile.empty()) | |||
1345 | return computeCallGraphProfileOrder(); | |||
1346 | ||||
1347 | if (config->symbolOrderingFile.empty()) | |||
1348 | return sectionOrder; | |||
1349 | ||||
1350 | struct SymbolOrderEntry { | |||
1351 | int priority; | |||
1352 | bool present; | |||
1353 | }; | |||
1354 | ||||
1355 | // Build a map from symbols to their priorities. Symbols that didn't | |||
1356 | // appear in the symbol ordering file have the lowest priority 0. | |||
1357 | // All explicitly mentioned symbols have negative (higher) priorities. | |||
1358 | DenseMap<StringRef, SymbolOrderEntry> symbolOrder; | |||
1359 | int priority = -config->symbolOrderingFile.size(); | |||
1360 | for (StringRef s : config->symbolOrderingFile) | |||
1361 | symbolOrder.insert({s, {priority++, false}}); | |||
1362 | ||||
1363 | // Build a map from sections to their priorities. | |||
1364 | auto addSym = [&](Symbol &sym) { | |||
1365 | auto it = symbolOrder.find(sym.getName()); | |||
1366 | if (it == symbolOrder.end()) | |||
1367 | return; | |||
1368 | SymbolOrderEntry &ent = it->second; | |||
1369 | ent.present = true; | |||
1370 | ||||
1371 | maybeWarnUnorderableSymbol(&sym); | |||
1372 | ||||
1373 | if (auto *d = dyn_cast<Defined>(&sym)) { | |||
1374 | if (auto *sec = dyn_cast_or_null<InputSectionBase>(d->section)) { | |||
1375 | int &priority = sectionOrder[cast<InputSectionBase>(sec->repl)]; | |||
1376 | priority = std::min(priority, ent.priority); | |||
1377 | } | |||
1378 | } | |||
1379 | }; | |||
1380 | ||||
1381 | // We want both global and local symbols. We get the global ones from the | |||
1382 | // symbol table and iterate the object files for the local ones. | |||
1383 | for (Symbol *sym : symtab->symbols()) | |||
1384 | if (!sym->isLazy()) | |||
1385 | addSym(*sym); | |||
1386 | ||||
1387 | for (InputFile *file : objectFiles) | |||
1388 | for (Symbol *sym : file->getSymbols()) { | |||
1389 | if (!sym->isLocal()) | |||
1390 | break; | |||
1391 | addSym(*sym); | |||
1392 | } | |||
1393 | ||||
1394 | if (config->warnSymbolOrdering) | |||
1395 | for (auto orderEntry : symbolOrder) | |||
1396 | if (!orderEntry.second.present) | |||
1397 | warn("symbol ordering file: no such symbol: " + orderEntry.first); | |||
1398 | ||||
1399 | return sectionOrder; | |||
1400 | } | |||
1401 | ||||
1402 | // Sorts the sections in ISD according to the provided section order. | |||
1403 | static void | |||
1404 | sortISDBySectionOrder(InputSectionDescription *isd, | |||
1405 | const DenseMap<const InputSectionBase *, int> &order) { | |||
1406 | std::vector<InputSection *> unorderedSections; | |||
1407 | std::vector<std::pair<InputSection *, int>> orderedSections; | |||
1408 | uint64_t unorderedSize = 0; | |||
1409 | ||||
1410 | for (InputSection *isec : isd->sections) { | |||
1411 | auto i = order.find(isec); | |||
1412 | if (i == order.end()) { | |||
1413 | unorderedSections.push_back(isec); | |||
1414 | unorderedSize += isec->getSize(); | |||
1415 | continue; | |||
1416 | } | |||
1417 | orderedSections.push_back({isec, i->second}); | |||
1418 | } | |||
1419 | llvm::sort(orderedSections, llvm::less_second()); | |||
1420 | ||||
1421 | // Find an insertion point for the ordered section list in the unordered | |||
1422 | // section list. On targets with limited-range branches, this is the mid-point | |||
1423 | // of the unordered section list. This decreases the likelihood that a range | |||
1424 | // extension thunk will be needed to enter or exit the ordered region. If the | |||
1425 | // ordered section list is a list of hot functions, we can generally expect | |||
1426 | // the ordered functions to be called more often than the unordered functions, | |||
1427 | // making it more likely that any particular call will be within range, and | |||
1428 | // therefore reducing the number of thunks required. | |||
1429 | // | |||
1430 | // For example, imagine that you have 8MB of hot code and 32MB of cold code. | |||
1431 | // If the layout is: | |||
1432 | // | |||
1433 | // 8MB hot | |||
1434 | // 32MB cold | |||
1435 | // | |||
1436 | // only the first 8-16MB of the cold code (depending on which hot function it | |||
1437 | // is actually calling) can call the hot code without a range extension thunk. | |||
1438 | // However, if we use this layout: | |||
1439 | // | |||
1440 | // 16MB cold | |||
1441 | // 8MB hot | |||
1442 | // 16MB cold | |||
1443 | // | |||
1444 | // both the last 8-16MB of the first block of cold code and the first 8-16MB | |||
1445 | // of the second block of cold code can call the hot code without a thunk. So | |||
1446 | // we effectively double the amount of code that could potentially call into | |||
1447 | // the hot code without a thunk. | |||
1448 | size_t insPt = 0; | |||
1449 | if (target->getThunkSectionSpacing() && !orderedSections.empty()) { | |||
1450 | uint64_t unorderedPos = 0; | |||
1451 | for (; insPt != unorderedSections.size(); ++insPt) { | |||
1452 | unorderedPos += unorderedSections[insPt]->getSize(); | |||
1453 | if (unorderedPos > unorderedSize / 2) | |||
1454 | break; | |||
1455 | } | |||
1456 | } | |||
1457 | ||||
1458 | isd->sections.clear(); | |||
1459 | for (InputSection *isec : makeArrayRef(unorderedSections).slice(0, insPt)) | |||
1460 | isd->sections.push_back(isec); | |||
1461 | for (std::pair<InputSection *, int> p : orderedSections) | |||
1462 | isd->sections.push_back(p.first); | |||
1463 | for (InputSection *isec : makeArrayRef(unorderedSections).slice(insPt)) | |||
1464 | isd->sections.push_back(isec); | |||
1465 | } | |||
1466 | ||||
1467 | static void sortSection(OutputSection *sec, | |||
1468 | const DenseMap<const InputSectionBase *, int> &order) { | |||
1469 | StringRef name = sec->name; | |||
1470 | ||||
1471 | // Never sort these. | |||
1472 | if (name == ".init" || name == ".fini") | |||
1473 | return; | |||
1474 | ||||
1475 | // IRelative relocations that usually live in the .rel[a].dyn section should | |||
1476 | // be processed last by the dynamic loader. To achieve that we add synthetic | |||
1477 | // sections in the required order from the beginning so that the in.relaIplt | |||
1478 | // section is placed last in an output section. Here we just do not apply | |||
1479 | // sorting for an output section which holds the in.relaIplt section. | |||
1480 | if (in.relaIplt->getParent() == sec) | |||
1481 | return; | |||
1482 | ||||
1483 | // Sort input sections by priority using the list provided by | |||
1484 | // --symbol-ordering-file or --shuffle-sections=. This is a least significant | |||
1485 | // digit radix sort. The sections may be sorted stably again by a more | |||
1486 | // significant key. | |||
1487 | if (!order.empty()) | |||
1488 | for (BaseCommand *b : sec->sectionCommands) | |||
1489 | if (auto *isd = dyn_cast<InputSectionDescription>(b)) | |||
1490 | sortISDBySectionOrder(isd, order); | |||
1491 | ||||
1492 | // Sort input sections by section name suffixes for | |||
1493 | // __attribute__((init_priority(N))). | |||
1494 | if (name == ".init_array" || name == ".fini_array") { | |||
1495 | if (!script->hasSectionsCommand) | |||
1496 | sec->sortInitFini(); | |||
1497 | return; | |||
1498 | } | |||
1499 | ||||
1500 | // Sort input sections by the special rule for .ctors and .dtors. | |||
1501 | if (name == ".ctors" || name == ".dtors") { | |||
1502 | if (!script->hasSectionsCommand) | |||
1503 | sec->sortCtorsDtors(); | |||
1504 | return; | |||
1505 | } | |||
1506 | ||||
1507 | // .toc is allocated just after .got and is accessed using GOT-relative | |||
1508 | // relocations. Object files compiled with small code model have an | |||
1509 | // addressable range of [.got, .got + 0xFFFC] for GOT-relative relocations. | |||
1510 | // To reduce the risk of relocation overflow, .toc contents are sorted so that | |||
1511 | // sections having smaller relocation offsets are at beginning of .toc | |||
1512 | if (config->emachine == EM_PPC64 && name == ".toc") { | |||
1513 | if (script->hasSectionsCommand) | |||
1514 | return; | |||
1515 | assert(sec->sectionCommands.size() == 1)((void)0); | |||
1516 | auto *isd = cast<InputSectionDescription>(sec->sectionCommands[0]); | |||
1517 | llvm::stable_sort(isd->sections, | |||
1518 | [](const InputSection *a, const InputSection *b) -> bool { | |||
1519 | return a->file->ppc64SmallCodeModelTocRelocs && | |||
1520 | !b->file->ppc64SmallCodeModelTocRelocs; | |||
1521 | }); | |||
1522 | return; | |||
1523 | } | |||
1524 | } | |||
1525 | ||||
1526 | // If no layout was provided by linker script, we want to apply default | |||
1527 | // sorting for special input sections. This also handles --symbol-ordering-file. | |||
1528 | template <class ELFT> void Writer<ELFT>::sortInputSections() { | |||
1529 | // Build the order once since it is expensive. | |||
1530 | DenseMap<const InputSectionBase *, int> order = buildSectionOrder(); | |||
1531 | maybeShuffle(order); | |||
1532 | for (BaseCommand *base : script->sectionCommands) | |||
1533 | if (auto *sec = dyn_cast<OutputSection>(base)) | |||
1534 | sortSection(sec, order); | |||
1535 | } | |||
1536 | ||||
1537 | template <class ELFT> void Writer<ELFT>::sortSections() { | |||
1538 | llvm::TimeTraceScope timeScope("Sort sections"); | |||
1539 | script->adjustSectionsBeforeSorting(); | |||
1540 | ||||
1541 | // Don't sort if using -r. It is not necessary and we want to preserve the | |||
1542 | // relative order for SHF_LINK_ORDER sections. | |||
1543 | if (config->relocatable) | |||
1544 | return; | |||
1545 | ||||
1546 | sortInputSections(); | |||
1547 | ||||
1548 | for (BaseCommand *base : script->sectionCommands) { | |||
1549 | auto *os = dyn_cast<OutputSection>(base); | |||
1550 | if (!os) | |||
1551 | continue; | |||
1552 | os->sortRank = getSectionRank(os); | |||
1553 | ||||
1554 | // We want to assign rude approximation values to outSecOff fields | |||
1555 | // to know the relative order of the input sections. We use it for | |||
1556 | // sorting SHF_LINK_ORDER sections. See resolveShfLinkOrder(). | |||
1557 | uint64_t i = 0; | |||
1558 | for (InputSection *sec : getInputSections(os)) | |||
1559 | sec->outSecOff = i++; | |||
1560 | } | |||
1561 | ||||
1562 | if (!script->hasSectionsCommand) { | |||
1563 | // We know that all the OutputSections are contiguous in this case. | |||
1564 | auto isSection = [](BaseCommand *base) { return isa<OutputSection>(base); }; | |||
1565 | std::stable_sort( | |||
1566 | llvm::find_if(script->sectionCommands, isSection), | |||
1567 | llvm::find_if(llvm::reverse(script->sectionCommands), isSection).base(), | |||
1568 | compareSections); | |||
1569 | ||||
1570 | // Process INSERT commands. From this point onwards the order of | |||
1571 | // script->sectionCommands is fixed. | |||
1572 | script->processInsertCommands(); | |||
1573 | return; | |||
1574 | } | |||
1575 | ||||
1576 | script->processInsertCommands(); | |||
1577 | ||||
1578 | // Orphan sections are sections present in the input files which are | |||
1579 | // not explicitly placed into the output file by the linker script. | |||
1580 | // | |||
1581 | // The sections in the linker script are already in the correct | |||
1582 | // order. We have to figuere out where to insert the orphan | |||
1583 | // sections. | |||
1584 | // | |||
1585 | // The order of the sections in the script is arbitrary and may not agree with | |||
1586 | // compareSections. This means that we cannot easily define a strict weak | |||
1587 | // ordering. To see why, consider a comparison of a section in the script and | |||
1588 | // one not in the script. We have a two simple options: | |||
1589 | // * Make them equivalent (a is not less than b, and b is not less than a). | |||
1590 | // The problem is then that equivalence has to be transitive and we can | |||
1591 | // have sections a, b and c with only b in a script and a less than c | |||
1592 | // which breaks this property. | |||
1593 | // * Use compareSectionsNonScript. Given that the script order doesn't have | |||
1594 | // to match, we can end up with sections a, b, c, d where b and c are in the | |||
1595 | // script and c is compareSectionsNonScript less than b. In which case d | |||
1596 | // can be equivalent to c, a to b and d < a. As a concrete example: | |||
1597 | // .a (rx) # not in script | |||
1598 | // .b (rx) # in script | |||
1599 | // .c (ro) # in script | |||
1600 | // .d (ro) # not in script | |||
1601 | // | |||
1602 | // The way we define an order then is: | |||
1603 | // * Sort only the orphan sections. They are in the end right now. | |||
1604 | // * Move each orphan section to its preferred position. We try | |||
1605 | // to put each section in the last position where it can share | |||
1606 | // a PT_LOAD. | |||
1607 | // | |||
1608 | // There is some ambiguity as to where exactly a new entry should be | |||
1609 | // inserted, because Commands contains not only output section | |||
1610 | // commands but also other types of commands such as symbol assignment | |||
1611 | // expressions. There's no correct answer here due to the lack of the | |||
1612 | // formal specification of the linker script. We use heuristics to | |||
1613 | // determine whether a new output command should be added before or | |||
1614 | // after another commands. For the details, look at shouldSkip | |||
1615 | // function. | |||
1616 | ||||
1617 | auto i = script->sectionCommands.begin(); | |||
1618 | auto e = script->sectionCommands.end(); | |||
1619 | auto nonScriptI = std::find_if(i, e, [](BaseCommand *base) { | |||
1620 | if (auto *sec = dyn_cast<OutputSection>(base)) | |||
1621 | return sec->sectionIndex == UINT32_MAX0xffffffffU; | |||
1622 | return false; | |||
1623 | }); | |||
1624 | ||||
1625 | // Sort the orphan sections. | |||
1626 | std::stable_sort(nonScriptI, e, compareSections); | |||
1627 | ||||
1628 | // As a horrible special case, skip the first . assignment if it is before any | |||
1629 | // section. We do this because it is common to set a load address by starting | |||
1630 | // the script with ". = 0xabcd" and the expectation is that every section is | |||
1631 | // after that. | |||
1632 | auto firstSectionOrDotAssignment = | |||
1633 | std::find_if(i, e, [](BaseCommand *cmd) { return !shouldSkip(cmd); }); | |||
1634 | if (firstSectionOrDotAssignment != e && | |||
1635 | isa<SymbolAssignment>(**firstSectionOrDotAssignment)) | |||
1636 | ++firstSectionOrDotAssignment; | |||
1637 | i = firstSectionOrDotAssignment; | |||
1638 | ||||
1639 | while (nonScriptI != e) { | |||
1640 | auto pos = findOrphanPos(i, nonScriptI); | |||
1641 | OutputSection *orphan = cast<OutputSection>(*nonScriptI); | |||
1642 | ||||
1643 | // As an optimization, find all sections with the same sort rank | |||
1644 | // and insert them with one rotate. | |||
1645 | unsigned rank = orphan->sortRank; | |||
1646 | auto end = std::find_if(nonScriptI + 1, e, [=](BaseCommand *cmd) { | |||
1647 | return cast<OutputSection>(cmd)->sortRank != rank; | |||
1648 | }); | |||
1649 | std::rotate(pos, nonScriptI, end); | |||
1650 | nonScriptI = end; | |||
1651 | } | |||
1652 | ||||
1653 | script->adjustSectionsAfterSorting(); | |||
1654 | } | |||
1655 | ||||
1656 | static bool compareByFilePosition(InputSection *a, InputSection *b) { | |||
1657 | InputSection *la = a->flags & SHF_LINK_ORDER ? a->getLinkOrderDep() : nullptr; | |||
1658 | InputSection *lb = b->flags & SHF_LINK_ORDER ? b->getLinkOrderDep() : nullptr; | |||
1659 | // SHF_LINK_ORDER sections with non-zero sh_link are ordered before | |||
1660 | // non-SHF_LINK_ORDER sections and SHF_LINK_ORDER sections with zero sh_link. | |||
1661 | if (!la || !lb) | |||
1662 | return la && !lb; | |||
1663 | OutputSection *aOut = la->getParent(); | |||
1664 | OutputSection *bOut = lb->getParent(); | |||
1665 | ||||
1666 | if (aOut != bOut) | |||
1667 | return aOut->addr < bOut->addr; | |||
1668 | return la->outSecOff < lb->outSecOff; | |||
1669 | } | |||
1670 | ||||
1671 | template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() { | |||
1672 | llvm::TimeTraceScope timeScope("Resolve SHF_LINK_ORDER"); | |||
1673 | for (OutputSection *sec : outputSections) { | |||
1674 | if (!(sec->flags & SHF_LINK_ORDER)) | |||
1675 | continue; | |||
1676 | ||||
1677 | // The ARM.exidx section use SHF_LINK_ORDER, but we have consolidated | |||
1678 | // this processing inside the ARMExidxsyntheticsection::finalizeContents(). | |||
1679 | if (!config->relocatable && config->emachine == EM_ARM && | |||
1680 | sec->type == SHT_ARM_EXIDX) | |||
1681 | continue; | |||
1682 | ||||
1683 | // Link order may be distributed across several InputSectionDescriptions. | |||
1684 | // Sorting is performed separately. | |||
1685 | std::vector<InputSection **> scriptSections; | |||
1686 | std::vector<InputSection *> sections; | |||
1687 | for (BaseCommand *base : sec->sectionCommands) { | |||
1688 | auto *isd = dyn_cast<InputSectionDescription>(base); | |||
1689 | if (!isd) | |||
1690 | continue; | |||
1691 | bool hasLinkOrder = false; | |||
1692 | scriptSections.clear(); | |||
1693 | sections.clear(); | |||
1694 | for (InputSection *&isec : isd->sections) { | |||
1695 | if (isec->flags & SHF_LINK_ORDER) { | |||
1696 | InputSection *link = isec->getLinkOrderDep(); | |||
1697 | if (link && !link->getParent()) | |||
1698 | error(toString(isec) + ": sh_link points to discarded section " + | |||
1699 | toString(link)); | |||
1700 | hasLinkOrder = true; | |||
1701 | } | |||
1702 | scriptSections.push_back(&isec); | |||
1703 | sections.push_back(isec); | |||
1704 | } | |||
1705 | if (hasLinkOrder && errorCount() == 0) { | |||
1706 | llvm::stable_sort(sections, compareByFilePosition); | |||
1707 | for (int i = 0, n = sections.size(); i != n; ++i) | |||
1708 | *scriptSections[i] = sections[i]; | |||
1709 | } | |||
1710 | } | |||
1711 | } | |||
1712 | } | |||
1713 | ||||
1714 | static void finalizeSynthetic(SyntheticSection *sec) { | |||
1715 | if (sec && sec->isNeeded() && sec->getParent()) { | |||
1716 | llvm::TimeTraceScope timeScope("Finalize synthetic sections", sec->name); | |||
1717 | sec->finalizeContents(); | |||
1718 | } | |||
1719 | } | |||
1720 | ||||
1721 | // We need to generate and finalize the content that depends on the address of | |||
1722 | // InputSections. As the generation of the content may also alter InputSection | |||
1723 | // addresses we must converge to a fixed point. We do that here. See the comment | |||
1724 | // in Writer<ELFT>::finalizeSections(). | |||
1725 | template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() { | |||
1726 | llvm::TimeTraceScope timeScope("Finalize address dependent content"); | |||
1727 | ThunkCreator tc; | |||
1728 | AArch64Err843419Patcher a64p; | |||
1729 | ARMErr657417Patcher a32p; | |||
1730 | script->assignAddresses(); | |||
1731 | // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they | |||
1732 | // do require the relative addresses of OutputSections because linker scripts | |||
1733 | // can assign Virtual Addresses to OutputSections that are not monotonically | |||
1734 | // increasing. | |||
1735 | for (Partition &part : partitions) | |||
1736 | finalizeSynthetic(part.armExidx); | |||
1737 | resolveShfLinkOrder(); | |||
1738 | ||||
1739 | // Converts call x@GDPLT to call __tls_get_addr | |||
1740 | if (config->emachine == EM_HEXAGON) | |||
1741 | hexagonTLSSymbolUpdate(outputSections); | |||
1742 | ||||
1743 | int assignPasses = 0; | |||
1744 | for (;;) { | |||
1745 | bool changed = target->needsThunks && tc.createThunks(outputSections); | |||
1746 | ||||
1747 | // With Thunk Size much smaller than branch range we expect to | |||
1748 | // converge quickly; if we get to 15 something has gone wrong. | |||
1749 | if (changed && tc.pass >= 15) { | |||
1750 | error("thunk creation not converged"); | |||
1751 | break; | |||
1752 | } | |||
1753 | ||||
1754 | if (config->fixCortexA53Errata843419) { | |||
1755 | if (changed) | |||
1756 | script->assignAddresses(); | |||
1757 | changed |= a64p.createFixes(); | |||
1758 | } | |||
1759 | if (config->fixCortexA8) { | |||
1760 | if (changed) | |||
1761 | script->assignAddresses(); | |||
1762 | changed |= a32p.createFixes(); | |||
1763 | } | |||
1764 | ||||
1765 | if (in.mipsGot) | |||
1766 | in.mipsGot->updateAllocSize(); | |||
1767 | ||||
1768 | for (Partition &part : partitions) { | |||
1769 | changed |= part.relaDyn->updateAllocSize(); | |||
1770 | if (part.relrDyn) | |||
1771 | changed |= part.relrDyn->updateAllocSize(); | |||
1772 | } | |||
1773 | ||||
1774 | const Defined *changedSym = script->assignAddresses(); | |||
1775 | if (!changed) { | |||
1776 | // Some symbols may be dependent on section addresses. When we break the | |||
1777 | // loop, the symbol values are finalized because a previous | |||
1778 | // assignAddresses() finalized section addresses. | |||
1779 | if (!changedSym) | |||
1780 | break; | |||
1781 | if (++assignPasses == 5) { | |||
1782 | errorOrWarn("assignment to symbol " + toString(*changedSym) + | |||
1783 | " does not converge"); | |||
1784 | break; | |||
1785 | } | |||
1786 | } | |||
1787 | } | |||
1788 | ||||
1789 | // If addrExpr is set, the address may not be a multiple of the alignment. | |||
1790 | // Warn because this is error-prone. | |||
1791 | for (BaseCommand *cmd : script->sectionCommands) | |||
1792 | if (auto *os = dyn_cast<OutputSection>(cmd)) | |||
1793 | if (os->addr % os->alignment != 0) | |||
1794 | warn("address (0x" + Twine::utohexstr(os->addr) + ") of section " + | |||
1795 | os->name + " is not a multiple of alignment (" + | |||
1796 | Twine(os->alignment) + ")"); | |||
1797 | } | |||
1798 | ||||
1799 | // If Input Sections have been shrunk (basic block sections) then | |||
1800 | // update symbol values and sizes associated with these sections. With basic | |||
1801 | // block sections, input sections can shrink when the jump instructions at | |||
1802 | // the end of the section are relaxed. | |||
1803 | static void fixSymbolsAfterShrinking() { | |||
1804 | for (InputFile *File : objectFiles) { | |||
1805 | parallelForEach(File->getSymbols(), [&](Symbol *Sym) { | |||
1806 | auto *def = dyn_cast<Defined>(Sym); | |||
1807 | if (!def) | |||
1808 | return; | |||
1809 | ||||
1810 | const SectionBase *sec = def->section; | |||
1811 | if (!sec) | |||
1812 | return; | |||
1813 | ||||
1814 | const InputSectionBase *inputSec = dyn_cast<InputSectionBase>(sec->repl); | |||
1815 | if (!inputSec || !inputSec->bytesDropped) | |||
1816 | return; | |||
1817 | ||||
1818 | const size_t OldSize = inputSec->data().size(); | |||
1819 | const size_t NewSize = OldSize - inputSec->bytesDropped; | |||
1820 | ||||
1821 | if (def->value > NewSize && def->value <= OldSize) { | |||
1822 | LLVM_DEBUG(llvm::dbgs()do { } while (false) | |||
1823 | << "Moving symbol " << Sym->getName() << " from "do { } while (false) | |||
1824 | << def->value << " to "do { } while (false) | |||
1825 | << def->value - inputSec->bytesDropped << " bytes\n")do { } while (false); | |||
1826 | def->value -= inputSec->bytesDropped; | |||
1827 | return; | |||
1828 | } | |||
1829 | ||||
1830 | if (def->value + def->size > NewSize && def->value <= OldSize && | |||
1831 | def->value + def->size <= OldSize) { | |||
1832 | LLVM_DEBUG(llvm::dbgs()do { } while (false) | |||
1833 | << "Shrinking symbol " << Sym->getName() << " from "do { } while (false) | |||
1834 | << def->size << " to " << def->size - inputSec->bytesDroppeddo { } while (false) | |||
1835 | << " bytes\n")do { } while (false); | |||
1836 | def->size -= inputSec->bytesDropped; | |||
1837 | } | |||
1838 | }); | |||
1839 | } | |||
1840 | } | |||
1841 | ||||
1842 | // If basic block sections exist, there are opportunities to delete fall thru | |||
1843 | // jumps and shrink jump instructions after basic block reordering. This | |||
1844 | // relaxation pass does that. It is only enabled when --optimize-bb-jumps | |||
1845 | // option is used. | |||
1846 | template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() { | |||
1847 | assert(config->optimizeBBJumps)((void)0); | |||
1848 | ||||
1849 | script->assignAddresses(); | |||
1850 | // For every output section that has executable input sections, this | |||
1851 | // does the following: | |||
1852 | // 1. Deletes all direct jump instructions in input sections that | |||
1853 | // jump to the following section as it is not required. | |||
1854 | // 2. If there are two consecutive jump instructions, it checks | |||
1855 | // if they can be flipped and one can be deleted. | |||
1856 | for (OutputSection *os : outputSections) { | |||
1857 | if (!(os->flags & SHF_EXECINSTR)) | |||
1858 | continue; | |||
1859 | std::vector<InputSection *> sections = getInputSections(os); | |||
1860 | std::vector<unsigned> result(sections.size()); | |||
1861 | // Delete all fall through jump instructions. Also, check if two | |||
1862 | // consecutive jump instructions can be flipped so that a fall | |||
1863 | // through jmp instruction can be deleted. | |||
1864 | parallelForEachN(0, sections.size(), [&](size_t i) { | |||
1865 | InputSection *next = i + 1 < sections.size() ? sections[i + 1] : nullptr; | |||
1866 | InputSection &is = *sections[i]; | |||
1867 | result[i] = | |||
1868 | target->deleteFallThruJmpInsn(is, is.getFile<ELFT>(), next) ? 1 : 0; | |||
1869 | }); | |||
1870 | size_t numDeleted = std::count(result.begin(), result.end(), 1); | |||
1871 | if (numDeleted > 0) { | |||
1872 | script->assignAddresses(); | |||
1873 | LLVM_DEBUG(llvm::dbgs()do { } while (false) | |||
1874 | << "Removing " << numDeleted << " fall through jumps\n")do { } while (false); | |||
1875 | } | |||
1876 | } | |||
1877 | ||||
1878 | fixSymbolsAfterShrinking(); | |||
1879 | ||||
1880 | for (OutputSection *os : outputSections) { | |||
1881 | std::vector<InputSection *> sections = getInputSections(os); | |||
1882 | for (InputSection *is : sections) | |||
1883 | is->trim(); | |||
1884 | } | |||
1885 | } | |||
1886 | ||||
1887 | // In order to allow users to manipulate linker-synthesized sections, | |||
1888 | // we had to add synthetic sections to the input section list early, | |||
1889 | // even before we make decisions whether they are needed. This allows | |||
1890 | // users to write scripts like this: ".mygot : { .got }". | |||
1891 | // | |||
1892 | // Doing it has an unintended side effects. If it turns out that we | |||
1893 | // don't need a .got (for example) at all because there's no | |||
1894 | // relocation that needs a .got, we don't want to emit .got. | |||
1895 | // | |||
1896 | // To deal with the above problem, this function is called after | |||
1897 | // scanRelocations is called to remove synthetic sections that turn | |||
1898 | // out to be empty. | |||
1899 | static void removeUnusedSyntheticSections() { | |||
1900 | // All input synthetic sections that can be empty are placed after | |||
1901 | // all regular ones. Reverse iterate to find the first synthetic section | |||
1902 | // after a non-synthetic one which will be our starting point. | |||
1903 | auto start = std::find_if(inputSections.rbegin(), inputSections.rend(), | |||
1904 | [](InputSectionBase *s) { | |||
1905 | return !isa<SyntheticSection>(s); | |||
1906 | }) | |||
1907 | .base(); | |||
1908 | ||||
1909 | DenseSet<InputSectionDescription *> isdSet; | |||
1910 | // Mark unused synthetic sections for deletion | |||
1911 | auto end = std::stable_partition( | |||
1912 | start, inputSections.end(), [&](InputSectionBase *s) { | |||
1913 | SyntheticSection *ss = dyn_cast<SyntheticSection>(s); | |||
1914 | OutputSection *os = ss->getParent(); | |||
| ||||
1915 | if (!os || ss->isNeeded()) | |||
1916 | return true; | |||
1917 | ||||
1918 | // If we reach here, then ss is an unused synthetic section and we want | |||
1919 | // to remove it from the corresponding input section description, and | |||
1920 | // orphanSections. | |||
1921 | for (BaseCommand *b : os->sectionCommands) | |||
1922 | if (auto *isd = dyn_cast<InputSectionDescription>(b)) | |||
1923 | isdSet.insert(isd); | |||
1924 | ||||
1925 | llvm::erase_if( | |||
1926 | script->orphanSections, | |||
1927 | [=](const InputSectionBase *isec) { return isec == ss; }); | |||
1928 | ||||
1929 | return false; | |||
1930 | }); | |||
1931 | ||||
1932 | DenseSet<InputSectionBase *> unused(end, inputSections.end()); | |||
1933 | for (auto *isd : isdSet) | |||
1934 | llvm::erase_if(isd->sections, | |||
1935 | [=](InputSection *isec) { return unused.count(isec); }); | |||
1936 | ||||
1937 | // Erase unused synthetic sections. | |||
1938 | inputSections.erase(end, inputSections.end()); | |||
1939 | } | |||
1940 | ||||
1941 | // Create output section objects and add them to OutputSections. | |||
1942 | template <class ELFT> void Writer<ELFT>::finalizeSections() { | |||
1943 | Out::preinitArray = findSection(".preinit_array"); | |||
1944 | Out::initArray = findSection(".init_array"); | |||
1945 | Out::finiArray = findSection(".fini_array"); | |||
1946 | ||||
1947 | // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop | |||
1948 | // symbols for sections, so that the runtime can get the start and end | |||
1949 | // addresses of each section by section name. Add such symbols. | |||
1950 | if (!config->relocatable) { | |||
| ||||
1951 | addStartEndSymbols(); | |||
1952 | for (BaseCommand *base : script->sectionCommands) | |||
1953 | if (auto *sec = dyn_cast<OutputSection>(base)) | |||
1954 | addStartStopSymbols(sec); | |||
1955 | } | |||
1956 | ||||
1957 | // Add _DYNAMIC symbol. Unlike GNU gold, our _DYNAMIC symbol has no type. | |||
1958 | // It should be okay as no one seems to care about the type. | |||
1959 | // Even the author of gold doesn't remember why gold behaves that way. | |||
1960 | // https://sourceware.org/ml/binutils/2002-03/msg00360.html | |||
1961 | if (mainPart->dynamic->parent) | |||
1962 | symtab->addSymbol(Defined{/*file=*/nullptr, "_DYNAMIC", STB_WEAK, | |||
1963 | STV_HIDDEN, STT_NOTYPE, | |||
1964 | /*value=*/0, /*size=*/0, mainPart->dynamic}); | |||
1965 | ||||
1966 | // Define __rel[a]_iplt_{start,end} symbols if needed. | |||
1967 | addRelIpltSymbols(); | |||
1968 | ||||
1969 | // RISC-V's gp can address +/- 2 KiB, set it to .sdata + 0x800. This symbol | |||
1970 | // should only be defined in an executable. If .sdata does not exist, its | |||
1971 | // value/section does not matter but it has to be relative, so set its | |||
1972 | // st_shndx arbitrarily to 1 (Out::elfHeader). | |||
1973 | if (config->emachine == EM_RISCV && !config->shared) { | |||
1974 | OutputSection *sec = findSection(".sdata"); | |||
1975 | ElfSym::riscvGlobalPointer = | |||
1976 | addOptionalRegular("__global_pointer$", sec ? sec : Out::elfHeader, | |||
1977 | 0x800, STV_DEFAULT, STB_GLOBAL); | |||
1978 | } | |||
1979 | ||||
1980 | if (config->emachine == EM_X86_64) { | |||
1981 | // On targets that support TLSDESC, _TLS_MODULE_BASE_ is defined in such a | |||
1982 | // way that: | |||
1983 | // | |||
1984 | // 1) Without relaxation: it produces a dynamic TLSDESC relocation that | |||
1985 | // computes 0. | |||
1986 | // 2) With LD->LE relaxation: _TLS_MODULE_BASE_@tpoff = 0 (lowest address in | |||
1987 | // the TLS block). | |||
1988 | // | |||
1989 | // 2) is special cased in @tpoff computation. To satisfy 1), we define it as | |||
1990 | // an absolute symbol of zero. This is different from GNU linkers which | |||
1991 | // define _TLS_MODULE_BASE_ relative to the first TLS section. | |||
1992 | Symbol *s = symtab->find("_TLS_MODULE_BASE_"); | |||
1993 | if (s && s->isUndefined()) { | |||
1994 | s->resolve(Defined{/*file=*/nullptr, s->getName(), STB_GLOBAL, STV_HIDDEN, | |||
1995 | STT_TLS, /*value=*/0, 0, | |||
1996 | /*section=*/nullptr}); | |||
1997 | ElfSym::tlsModuleBase = cast<Defined>(s); | |||
1998 | } | |||
1999 | } | |||
2000 | ||||
2001 | { | |||
2002 | llvm::TimeTraceScope timeScope("Finalize .eh_frame"); | |||
2003 | // This responsible for splitting up .eh_frame section into | |||
2004 | // pieces. The relocation scan uses those pieces, so this has to be | |||
2005 | // earlier. | |||
2006 | for (Partition &part : partitions) | |||
2007 | finalizeSynthetic(part.ehFrame); | |||
2008 | } | |||
2009 | ||||
2010 | for (Symbol *sym : symtab->symbols()) | |||
2011 | sym->isPreemptible = computeIsPreemptible(*sym); | |||
2012 | ||||
2013 | // Change values of linker-script-defined symbols from placeholders (assigned | |||
2014 | // by declareSymbols) to actual definitions. | |||
2015 | script->processSymbolAssignments(); | |||
2016 | ||||
2017 | { | |||
2018 | llvm::TimeTraceScope timeScope("Scan relocations"); | |||
2019 | // Scan relocations. This must be done after every symbol is declared so | |||
2020 | // that we can correctly decide if a dynamic relocation is needed. This is | |||
2021 | // called after processSymbolAssignments() because it needs to know whether | |||
2022 | // a linker-script-defined symbol is absolute. | |||
2023 | ppc64noTocRelax.clear(); | |||
2024 | if (!config->relocatable) { | |||
2025 | forEachRelSec(scanRelocations<ELFT>); | |||
2026 | reportUndefinedSymbols<ELFT>(); | |||
2027 | } | |||
2028 | } | |||
2029 | ||||
2030 | if (in.plt && in.plt->isNeeded()) | |||
2031 | in.plt->addSymbols(); | |||
2032 | if (in.iplt && in.iplt->isNeeded()) | |||
2033 | in.iplt->addSymbols(); | |||
2034 | ||||
2035 | if (config->unresolvedSymbolsInShlib != UnresolvedPolicy::Ignore) { | |||
2036 | auto diagnose = | |||
2037 | config->unresolvedSymbolsInShlib == UnresolvedPolicy::ReportError | |||
2038 | ? errorOrWarn | |||
2039 | : warn; | |||
2040 | // Error on undefined symbols in a shared object, if all of its DT_NEEDED | |||
2041 | // entries are seen. These cases would otherwise lead to runtime errors | |||
2042 | // reported by the dynamic linker. | |||
2043 | // | |||
2044 | // ld.bfd traces all DT_NEEDED to emulate the logic of the dynamic linker to | |||
2045 | // catch more cases. That is too much for us. Our approach resembles the one | |||
2046 | // used in ld.gold, achieves a good balance to be useful but not too smart. | |||
2047 | for (SharedFile *file : sharedFiles) { | |||
2048 | bool allNeededIsKnown = | |||
2049 | llvm::all_of(file->dtNeeded, [&](StringRef needed) { | |||
2050 | return symtab->soNames.count(needed); | |||
2051 | }); | |||
2052 | if (!allNeededIsKnown) | |||
2053 | continue; | |||
2054 | for (Symbol *sym : file->requiredSymbols) | |||
2055 | if (sym->isUndefined() && !sym->isWeak()) | |||
2056 | diagnose(toString(file) + ": undefined reference to " + | |||
2057 | toString(*sym) + " [--no-allow-shlib-undefined]"); | |||
2058 | } | |||
2059 | } | |||
2060 | ||||
2061 | { | |||
2062 | llvm::TimeTraceScope timeScope("Add symbols to symtabs"); | |||
2063 | // Now that we have defined all possible global symbols including linker- | |||
2064 | // synthesized ones. Visit all symbols to give the finishing touches. | |||
2065 | for (Symbol *sym : symtab->symbols()) { | |||
2066 | if (!includeInSymtab(*sym)) | |||
2067 | continue; | |||
2068 | if (in.symTab) | |||
2069 | in.symTab->addSymbol(sym); | |||
2070 | ||||
2071 | if (sym->includeInDynsym()) { | |||
2072 | partitions[sym->partition - 1].dynSymTab->addSymbol(sym); | |||
2073 | if (auto *file = dyn_cast_or_null<SharedFile>(sym->file)) | |||
2074 | if (file->isNeeded && !sym->isUndefined()) | |||
2075 | addVerneed(sym); | |||
2076 | } | |||
2077 | } | |||
2078 | ||||
2079 | // We also need to scan the dynamic relocation tables of the other | |||
2080 | // partitions and add any referenced symbols to the partition's dynsym. | |||
2081 | for (Partition &part : MutableArrayRef<Partition>(partitions).slice(1)) { | |||
2082 | DenseSet<Symbol *> syms; | |||
2083 | for (const SymbolTableEntry &e : part.dynSymTab->getSymbols()) | |||
2084 | syms.insert(e.sym); | |||
2085 | for (DynamicReloc &reloc : part.relaDyn->relocs) | |||
2086 | if (reloc.sym && reloc.needsDynSymIndex() && | |||
2087 | syms.insert(reloc.sym).second) | |||
2088 | part.dynSymTab->addSymbol(reloc.sym); | |||
2089 | } | |||
2090 | } | |||
2091 | ||||
2092 | // Do not proceed if there was an undefined symbol. | |||
2093 | if (errorCount()) | |||
2094 | return; | |||
2095 | ||||
2096 | if (in.mipsGot) | |||
2097 | in.mipsGot->build(); | |||
2098 | ||||
2099 | removeUnusedSyntheticSections(); | |||
2100 | script->diagnoseOrphanHandling(); | |||
2101 | ||||
2102 | sortSections(); | |||
2103 | ||||
2104 | // Now that we have the final list, create a list of all the | |||
2105 | // OutputSections for convenience. | |||
2106 | for (BaseCommand *base : script->sectionCommands) | |||
2107 | if (auto *sec = dyn_cast<OutputSection>(base)) | |||
2108 | outputSections.push_back(sec); | |||
2109 | ||||
2110 | // Prefer command line supplied address over other constraints. | |||
2111 | for (OutputSection *sec : outputSections) { | |||
2112 | auto i = config->sectionStartMap.find(sec->name); | |||
2113 | if (i != config->sectionStartMap.end()) | |||
2114 | sec->addrExpr = [=] { return i->second; }; | |||
2115 | } | |||
2116 | ||||
2117 | // With the outputSections available check for GDPLT relocations | |||
2118 | // and add __tls_get_addr symbol if needed. | |||
2119 | if (config->emachine == EM_HEXAGON && hexagonNeedsTLSSymbol(outputSections)) { | |||
2120 | Symbol *sym = symtab->addSymbol(Undefined{ | |||
2121 | nullptr, "__tls_get_addr", STB_GLOBAL, STV_DEFAULT, STT_NOTYPE}); | |||
2122 | sym->isPreemptible = true; | |||
2123 | partitions[0].dynSymTab->addSymbol(sym); | |||
2124 | } | |||
2125 | ||||
2126 | // This is a bit of a hack. A value of 0 means undef, so we set it | |||
2127 | // to 1 to make __ehdr_start defined. The section number is not | |||
2128 | // particularly relevant. | |||
2129 | Out::elfHeader->sectionIndex = 1; | |||
2130 | ||||
2131 | for (size_t i = 0, e = outputSections.size(); i != e; ++i) { | |||
2132 | OutputSection *sec = outputSections[i]; | |||
2133 | sec->sectionIndex = i + 1; | |||
2134 | sec->shName = in.shStrTab->addString(sec->name); | |||
2135 | } | |||
2136 | ||||
2137 | // Binary and relocatable output does not have PHDRS. | |||
2138 | // The headers have to be created before finalize as that can influence the | |||
2139 | // image base and the dynamic section on mips includes the image base. | |||
2140 | if (!config->relocatable && !config->oFormatBinary) { | |||
2141 | for (Partition &part : partitions) { | |||
2142 | part.phdrs = script->hasPhdrsCommands() ? script->createPhdrs() | |||
2143 | : createPhdrs(part); | |||
2144 | if (config->emachine == EM_ARM) { | |||
2145 | // PT_ARM_EXIDX is the ARM EHABI equivalent of PT_GNU_EH_FRAME | |||
2146 | addPhdrForSection(part, SHT_ARM_EXIDX, PT_ARM_EXIDX, PF_R); | |||
2147 | } | |||
2148 | if (config->emachine == EM_MIPS) { | |||
2149 | // Add separate segments for MIPS-specific sections. | |||
2150 | addPhdrForSection(part, SHT_MIPS_REGINFO, PT_MIPS_REGINFO, PF_R); | |||
2151 | addPhdrForSection(part, SHT_MIPS_OPTIONS, PT_MIPS_OPTIONS, PF_R); | |||
2152 | addPhdrForSection(part, SHT_MIPS_ABIFLAGS, PT_MIPS_ABIFLAGS, PF_R); | |||
2153 | } | |||
2154 | } | |||
2155 | Out::programHeaders->size = sizeof(Elf_Phdr) * mainPart->phdrs.size(); | |||
2156 | ||||
2157 | // Find the TLS segment. This happens before the section layout loop so that | |||
2158 | // Android relocation packing can look up TLS symbol addresses. We only need | |||
2159 | // to care about the main partition here because all TLS symbols were moved | |||
2160 | // to the main partition (see MarkLive.cpp). | |||
2161 | for (PhdrEntry *p : mainPart->phdrs) | |||
2162 | if (p->p_type == PT_TLS) | |||
2163 | Out::tlsPhdr = p; | |||
2164 | } | |||
2165 | ||||
2166 | // Some symbols are defined in term of program headers. Now that we | |||
2167 | // have the headers, we can find out which sections they point to. | |||
2168 | setReservedSymbolSections(); | |||
2169 | ||||
2170 | { | |||
2171 | llvm::TimeTraceScope timeScope("Finalize synthetic sections"); | |||
2172 | ||||
2173 | finalizeSynthetic(in.bss); | |||
2174 | finalizeSynthetic(in.bssRelRo); | |||
2175 | finalizeSynthetic(in.symTabShndx); | |||
2176 | finalizeSynthetic(in.shStrTab); | |||
2177 | finalizeSynthetic(in.strTab); | |||
2178 | finalizeSynthetic(in.got); | |||
2179 | finalizeSynthetic(in.mipsGot); | |||
2180 | finalizeSynthetic(in.igotPlt); | |||
2181 | finalizeSynthetic(in.gotPlt); | |||
2182 | finalizeSynthetic(in.relaIplt); | |||
2183 | finalizeSynthetic(in.relaPlt); | |||
2184 | finalizeSynthetic(in.plt); | |||
2185 | finalizeSynthetic(in.iplt); | |||
2186 | finalizeSynthetic(in.ppc32Got2); | |||
2187 | finalizeSynthetic(in.partIndex); | |||
2188 | ||||
2189 | // Dynamic section must be the last one in this list and dynamic | |||
2190 | // symbol table section (dynSymTab) must be the first one. | |||
2191 | for (Partition &part : partitions) { | |||
2192 | finalizeSynthetic(part.dynSymTab); | |||
2193 | finalizeSynthetic(part.gnuHashTab); | |||
2194 | finalizeSynthetic(part.hashTab); | |||
2195 | finalizeSynthetic(part.verDef); | |||
2196 | finalizeSynthetic(part.relaDyn); | |||
2197 | finalizeSynthetic(part.relrDyn); | |||
2198 | finalizeSynthetic(part.ehFrameHdr); | |||
2199 | finalizeSynthetic(part.verSym); | |||
2200 | finalizeSynthetic(part.verNeed); | |||
2201 | finalizeSynthetic(part.dynamic); | |||
2202 | } | |||
2203 | } | |||
2204 | ||||
2205 | if (!script->hasSectionsCommand && !config->relocatable) | |||
2206 | fixSectionAlignments(); | |||
2207 | ||||
2208 | // This is used to: | |||
2209 | // 1) Create "thunks": | |||
2210 | // Jump instructions in many ISAs have small displacements, and therefore | |||
2211 | // they cannot jump to arbitrary addresses in memory. For example, RISC-V | |||
2212 | // JAL instruction can target only +-1 MiB from PC. It is a linker's | |||
2213 | // responsibility to create and insert small pieces of code between | |||
2214 | // sections to extend the ranges if jump targets are out of range. Such | |||
2215 | // code pieces are called "thunks". | |||
2216 | // | |||
2217 | // We add thunks at this stage. We couldn't do this before this point | |||
2218 | // because this is the earliest point where we know sizes of sections and | |||
2219 | // their layouts (that are needed to determine if jump targets are in | |||
2220 | // range). | |||
2221 | // | |||
2222 | // 2) Update the sections. We need to generate content that depends on the | |||
2223 | // address of InputSections. For example, MIPS GOT section content or | |||
2224 | // android packed relocations sections content. | |||
2225 | // | |||
2226 | // 3) Assign the final values for the linker script symbols. Linker scripts | |||
2227 | // sometimes using forward symbol declarations. We want to set the correct | |||
2228 | // values. They also might change after adding the thunks. | |||
2229 | finalizeAddressDependentContent(); | |||
2230 | if (errorCount()) | |||
2231 | return; | |||
2232 | ||||
2233 | { | |||
2234 | llvm::TimeTraceScope timeScope("Finalize synthetic sections"); | |||
2235 | // finalizeAddressDependentContent may have added local symbols to the | |||
2236 | // static symbol table. | |||
2237 | finalizeSynthetic(in.symTab); | |||
2238 | finalizeSynthetic(in.ppc64LongBranchTarget); | |||
2239 | } | |||
2240 | ||||
2241 | // Relaxation to delete inter-basic block jumps created by basic block | |||
2242 | // sections. Run after in.symTab is finalized as optimizeBasicBlockJumps | |||
2243 | // can relax jump instructions based on symbol offset. | |||
2244 | if (config->optimizeBBJumps) | |||
2245 | optimizeBasicBlockJumps(); | |||
2246 | ||||
2247 | // Fill other section headers. The dynamic table is finalized | |||
2248 | // at the end because some tags like RELSZ depend on result | |||
2249 | // of finalizing other sections. | |||
2250 | for (OutputSection *sec : outputSections) | |||
2251 | sec->finalize(); | |||
2252 | } | |||
2253 | ||||
2254 | // Ensure data sections are not mixed with executable sections when | |||
2255 | // -execute-only is used. -execute-only is a feature to make pages executable | |||
2256 | // but not readable, and the feature is currently supported only on AArch64. | |||
2257 | template <class ELFT> void Writer<ELFT>::checkExecuteOnly() { | |||
2258 | if (!config->executeOnly) | |||
2259 | return; | |||
2260 | ||||
2261 | for (OutputSection *os : outputSections) | |||
2262 | if (os->flags & SHF_EXECINSTR) | |||
2263 | for (InputSection *isec : getInputSections(os)) | |||
2264 | if (!(isec->flags & SHF_EXECINSTR)) | |||
2265 | error("cannot place " + toString(isec) + " into " + toString(os->name) + | |||
2266 | ": -execute-only does not support intermingling data and code"); | |||
2267 | } | |||
2268 | ||||
2269 | // The linker is expected to define SECNAME_start and SECNAME_end | |||
2270 | // symbols for a few sections. This function defines them. | |||
2271 | template <class ELFT> void Writer<ELFT>::addStartEndSymbols() { | |||
2272 | // If a section does not exist, there's ambiguity as to how we | |||
2273 | // define _start and _end symbols for an init/fini section. Since | |||
2274 | // the loader assume that the symbols are always defined, we need to | |||
2275 | // always define them. But what value? The loader iterates over all | |||
2276 | // pointers between _start and _end to run global ctors/dtors, so if | |||
2277 | // the section is empty, their symbol values don't actually matter | |||
2278 | // as long as _start and _end point to the same location. | |||
2279 | // | |||
2280 | // That said, we don't want to set the symbols to 0 (which is | |||
2281 | // probably the simplest value) because that could cause some | |||
2282 | // program to fail to link due to relocation overflow, if their | |||
2283 | // program text is above 2 GiB. We use the address of the .text | |||
2284 | // section instead to prevent that failure. | |||
2285 | // | |||
2286 | // In rare situations, the .text section may not exist. If that's the | |||
2287 | // case, use the image base address as a last resort. | |||
2288 | OutputSection *Default = findSection(".text"); | |||
2289 | if (!Default) | |||
2290 | Default = Out::elfHeader; | |||
2291 | ||||
2292 | auto define = [=](StringRef start, StringRef end, OutputSection *os) { | |||
2293 | if (os) { | |||
2294 | addOptionalRegular(start, os, 0); | |||
2295 | addOptionalRegular(end, os, -1); | |||
2296 | } else { | |||
2297 | addOptionalRegular(start, Default, 0); | |||
2298 | addOptionalRegular(end, Default, 0); | |||
2299 | } | |||
2300 | }; | |||
2301 | ||||
2302 | define("__preinit_array_start", "__preinit_array_end", Out::preinitArray); | |||
2303 | define("__init_array_start", "__init_array_end", Out::initArray); | |||
2304 | define("__fini_array_start", "__fini_array_end", Out::finiArray); | |||
2305 | ||||
2306 | if (OutputSection *sec = findSection(".ARM.exidx")) | |||
2307 | define("__exidx_start", "__exidx_end", sec); | |||
2308 | } | |||
2309 | ||||
2310 | // If a section name is valid as a C identifier (which is rare because of | |||
2311 | // the leading '.'), linkers are expected to define __start_<secname> and | |||
2312 | // __stop_<secname> symbols. They are at beginning and end of the section, | |||
2313 | // respectively. This is not requested by the ELF standard, but GNU ld and | |||
2314 | // gold provide the feature, and used by many programs. | |||
2315 | template <class ELFT> | |||
2316 | void Writer<ELFT>::addStartStopSymbols(OutputSection *sec) { | |||
2317 | StringRef s = sec->name; | |||
2318 | if (!isValidCIdentifier(s)) | |||
2319 | return; | |||
2320 | addOptionalRegular(saver.save("__start_" + s), sec, 0, | |||
2321 | config->zStartStopVisibility); | |||
2322 | addOptionalRegular(saver.save("__stop_" + s), sec, -1, | |||
2323 | config->zStartStopVisibility); | |||
2324 | } | |||
2325 | ||||
2326 | static bool needsPtLoad(OutputSection *sec) { | |||
2327 | if (!(sec->flags & SHF_ALLOC)) | |||
2328 | return false; | |||
2329 | ||||
2330 | // Don't allocate VA space for TLS NOBITS sections. The PT_TLS PHDR is | |||
2331 | // responsible for allocating space for them, not the PT_LOAD that | |||
2332 | // contains the TLS initialization image. | |||
2333 | if ((sec->flags & SHF_TLS) && sec->type == SHT_NOBITS) | |||
2334 | return false; | |||
2335 | return true; | |||
2336 | } | |||
2337 | ||||
2338 | // Linker scripts are responsible for aligning addresses. Unfortunately, most | |||
2339 | // linker scripts are designed for creating two PT_LOADs only, one RX and one | |||
2340 | // RW. This means that there is no alignment in the RO to RX transition and we | |||
2341 | // cannot create a PT_LOAD there. | |||
2342 | static uint64_t computeFlags(uint64_t flags) { | |||
2343 | if (config->omagic) | |||
2344 | return PF_R | PF_W | PF_X; | |||
2345 | if (config->executeOnly && (flags & PF_X)) | |||
2346 | return flags & ~PF_R; | |||
2347 | if (config->singleRoRx && !(flags & PF_W)) | |||
2348 | return flags | PF_X; | |||
2349 | return flags; | |||
2350 | } | |||
2351 | ||||
2352 | // Decide which program headers to create and which sections to include in each | |||
2353 | // one. | |||
2354 | template <class ELFT> | |||
2355 | std::vector<PhdrEntry *> Writer<ELFT>::createPhdrs(Partition &part) { | |||
2356 | std::vector<PhdrEntry *> ret; | |||
2357 | auto addHdr = [&](unsigned type, unsigned flags) -> PhdrEntry * { | |||
2358 | ret.push_back(make<PhdrEntry>(type, flags)); | |||
2359 | return ret.back(); | |||
2360 | }; | |||
2361 | ||||
2362 | unsigned partNo = part.getNumber(); | |||
2363 | bool isMain = partNo == 1; | |||
2364 | ||||
2365 | // Add the first PT_LOAD segment for regular output sections. | |||
2366 | uint64_t flags = computeFlags(PF_R); | |||
2367 | PhdrEntry *load = nullptr; | |||
2368 | ||||
2369 | // nmagic or omagic output does not have PT_PHDR, PT_INTERP, or the readonly | |||
2370 | // PT_LOAD. | |||
2371 | if (!config->nmagic && !config->omagic) { | |||
2372 | // The first phdr entry is PT_PHDR which describes the program header | |||
2373 | // itself. | |||
2374 | if (isMain) | |||
2375 | addHdr(PT_PHDR, PF_R)->add(Out::programHeaders); | |||
2376 | else | |||
2377 | addHdr(PT_PHDR, PF_R)->add(part.programHeaders->getParent()); | |||
2378 | ||||
2379 | // PT_INTERP must be the second entry if exists. | |||
2380 | if (OutputSection *cmd = findSection(".interp", partNo)) | |||
2381 | addHdr(PT_INTERP, cmd->getPhdrFlags())->add(cmd); | |||
2382 | ||||
2383 | // Add the headers. We will remove them if they don't fit. | |||
2384 | // In the other partitions the headers are ordinary sections, so they don't | |||
2385 | // need to be added here. | |||
2386 | if (isMain) { | |||
2387 | load = addHdr(PT_LOAD, flags); | |||
2388 | load->add(Out::elfHeader); | |||
2389 | load->add(Out::programHeaders); | |||
2390 | } | |||
2391 | } | |||
2392 | ||||
2393 | // PT_GNU_RELRO includes all sections that should be marked as | |||
2394 | // read-only by dynamic linker after processing relocations. | |||
2395 | // Current dynamic loaders only support one PT_GNU_RELRO PHDR, give | |||
2396 | // an error message if more than one PT_GNU_RELRO PHDR is required. | |||
2397 | PhdrEntry *relRo = make<PhdrEntry>(PT_GNU_RELRO, PF_R); | |||
2398 | bool inRelroPhdr = false; | |||
2399 | OutputSection *relroEnd = nullptr; | |||
2400 | for (OutputSection *sec : outputSections) { | |||
2401 | if (sec->partition != partNo || !needsPtLoad(sec)) | |||
2402 | continue; | |||
2403 | if (isRelroSection(sec)) { | |||
2404 | inRelroPhdr = true; | |||
2405 | if (!relroEnd) | |||
2406 | relRo->add(sec); | |||
2407 | else | |||
2408 | error("section: " + sec->name + " is not contiguous with other relro" + | |||
2409 | " sections"); | |||
2410 | } else if (inRelroPhdr) { | |||
2411 | inRelroPhdr = false; | |||
2412 | relroEnd = sec; | |||
2413 | } | |||
2414 | } | |||
2415 | ||||
2416 | for (OutputSection *sec : outputSections) { | |||
2417 | if (!needsPtLoad(sec)) | |||
2418 | continue; | |||
2419 | ||||
2420 | // Normally, sections in partitions other than the current partition are | |||
2421 | // ignored. But partition number 255 is a special case: it contains the | |||
2422 | // partition end marker (.part.end). It needs to be added to the main | |||
2423 | // partition so that a segment is created for it in the main partition, | |||
2424 | // which will cause the dynamic loader to reserve space for the other | |||
2425 | // partitions. | |||
2426 | if (sec->partition != partNo) { | |||
2427 | if (isMain && sec->partition == 255) | |||
2428 | addHdr(PT_LOAD, computeFlags(sec->getPhdrFlags()))->add(sec); | |||
2429 | continue; | |||
2430 | } | |||
2431 | ||||
2432 | // Segments are contiguous memory regions that has the same attributes | |||
2433 | // (e.g. executable or writable). There is one phdr for each segment. | |||
2434 | // Therefore, we need to create a new phdr when the next section has | |||
2435 | // different flags or is loaded at a discontiguous address or memory | |||
2436 | // region using AT or AT> linker script command, respectively. At the same | |||
2437 | // time, we don't want to create a separate load segment for the headers, | |||
2438 | // even if the first output section has an AT or AT> attribute. | |||
2439 | uint64_t newFlags = computeFlags(sec->getPhdrFlags()); | |||
2440 | bool sameLMARegion = | |||
2441 | load && !sec->lmaExpr && sec->lmaRegion == load->firstSec->lmaRegion; | |||
2442 | if (!(load && newFlags == flags && sec != relroEnd && | |||
2443 | sec->memRegion == load->firstSec->memRegion && | |||
2444 | (sameLMARegion || load->lastSec == Out::programHeaders))) { | |||
2445 | load = addHdr(PT_LOAD, newFlags); | |||
2446 | flags = newFlags; | |||
2447 | } | |||
2448 | ||||
2449 | load->add(sec); | |||
2450 | } | |||
2451 | ||||
2452 | // Add a TLS segment if any. | |||
2453 | PhdrEntry *tlsHdr = make<PhdrEntry>(PT_TLS, PF_R); | |||
2454 | for (OutputSection *sec : outputSections) | |||
2455 | if (sec->partition == partNo && sec->flags & SHF_TLS) | |||
2456 | tlsHdr->add(sec); | |||
2457 | if (tlsHdr->firstSec) | |||
2458 | ret.push_back(tlsHdr); | |||
2459 | ||||
2460 | // Add an entry for .dynamic. | |||
2461 | if (OutputSection *sec = part.dynamic->getParent()) | |||
2462 | addHdr(PT_DYNAMIC, sec->getPhdrFlags())->add(sec); | |||
2463 | ||||
2464 | if (relRo->firstSec) | |||
2465 | ret.push_back(relRo); | |||
2466 | ||||
2467 | // PT_GNU_EH_FRAME is a special section pointing on .eh_frame_hdr. | |||
2468 | if (part.ehFrame->isNeeded() && part.ehFrameHdr && | |||
2469 | part.ehFrame->getParent() && part.ehFrameHdr->getParent()) | |||
2470 | addHdr(PT_GNU_EH_FRAME, part.ehFrameHdr->getParent()->getPhdrFlags()) | |||
2471 | ->add(part.ehFrameHdr->getParent()); | |||
2472 | ||||
2473 | // PT_OPENBSD_RANDOMIZE is an OpenBSD-specific feature. That makes | |||
2474 | // the dynamic linker fill the segment with random data. | |||
2475 | if (OutputSection *cmd = findSection(".openbsd.randomdata", partNo)) | |||
2476 | addHdr(PT_OPENBSD_RANDOMIZE, cmd->getPhdrFlags())->add(cmd); | |||
2477 | ||||
2478 | if (config->zGnustack != GnuStackKind::None) { | |||
2479 | // PT_GNU_STACK is a special section to tell the loader to make the | |||
2480 | // pages for the stack non-executable. If you really want an executable | |||
2481 | // stack, you can pass -z execstack, but that's not recommended for | |||
2482 | // security reasons. | |||
2483 | unsigned perm = PF_R | PF_W; | |||
2484 | if (config->zGnustack == GnuStackKind::Exec) | |||
2485 | perm |= PF_X; | |||
2486 | addHdr(PT_GNU_STACK, perm)->p_memsz = config->zStackSize; | |||
2487 | } | |||
2488 | ||||
2489 | // PT_OPENBSD_WXNEEDED is a OpenBSD-specific header to mark the executable | |||
2490 | // is expected to perform W^X violations, such as calling mprotect(2) or | |||
2491 | // mmap(2) with PROT_WRITE | PROT_EXEC, which is prohibited by default on | |||
2492 | // OpenBSD. | |||
2493 | if (config->zWxneeded) | |||
2494 | addHdr(PT_OPENBSD_WXNEEDED, PF_X); | |||
2495 | ||||
2496 | if (OutputSection *cmd = findSection(".note.gnu.property", partNo)) | |||
2497 | addHdr(PT_GNU_PROPERTY, PF_R)->add(cmd); | |||
2498 | ||||
2499 | // Create one PT_NOTE per a group of contiguous SHT_NOTE sections with the | |||
2500 | // same alignment. | |||
2501 | PhdrEntry *note = nullptr; | |||
2502 | for (OutputSection *sec : outputSections) { | |||
2503 | if (sec->partition != partNo) | |||
2504 | continue; | |||
2505 | if (sec->type == SHT_NOTE && (sec->flags & SHF_ALLOC)) { | |||
2506 | if (!note || sec->lmaExpr || note->lastSec->alignment != sec->alignment) | |||
2507 | note = addHdr(PT_NOTE, PF_R); | |||
2508 | note->add(sec); | |||
2509 | } else { | |||
2510 | note = nullptr; | |||
2511 | } | |||
2512 | } | |||
2513 | return ret; | |||
2514 | } | |||
2515 | ||||
2516 | template <class ELFT> | |||
2517 | void Writer<ELFT>::addPhdrForSection(Partition &part, unsigned shType, | |||
2518 | unsigned pType, unsigned pFlags) { | |||
2519 | unsigned partNo = part.getNumber(); | |||
2520 | auto i = llvm::find_if(outputSections, [=](OutputSection *cmd) { | |||
2521 | return cmd->partition == partNo && cmd->type == shType; | |||
2522 | }); | |||
2523 | if (i == outputSections.end()) | |||
2524 | return; | |||
2525 | ||||
2526 | PhdrEntry *entry = make<PhdrEntry>(pType, pFlags); | |||
2527 | entry->add(*i); | |||
2528 | part.phdrs.push_back(entry); | |||
2529 | } | |||
2530 | ||||
2531 | // Place the first section of each PT_LOAD to a different page (of maxPageSize). | |||
2532 | // This is achieved by assigning an alignment expression to addrExpr of each | |||
2533 | // such section. | |||
2534 | template <class ELFT> void Writer<ELFT>::fixSectionAlignments() { | |||
2535 | const PhdrEntry *prev; | |||
2536 | auto pageAlign = [&](const PhdrEntry *p) { | |||
2537 | OutputSection *cmd = p->firstSec; | |||
2538 | if (!cmd) | |||
2539 | return; | |||
2540 | cmd->alignExpr = [align = cmd->alignment]() { return align; }; | |||
2541 | if (!cmd->addrExpr) { | |||
2542 | // Prefer advancing to align(dot, maxPageSize) + dot%maxPageSize to avoid | |||
2543 | // padding in the file contents. | |||
2544 | // | |||
2545 | // When -z separate-code is used we must not have any overlap in pages | |||
2546 | // between an executable segment and a non-executable segment. We align to | |||
2547 | // the next maximum page size boundary on transitions between executable | |||
2548 | // and non-executable segments. | |||
2549 | // | |||
2550 | // SHT_LLVM_PART_EHDR marks the start of a partition. The partition | |||
2551 | // sections will be extracted to a separate file. Align to the next | |||
2552 | // maximum page size boundary so that we can find the ELF header at the | |||
2553 | // start. We cannot benefit from overlapping p_offset ranges with the | |||
2554 | // previous segment anyway. | |||
2555 | if (config->zSeparate == SeparateSegmentKind::Loadable || | |||
2556 | (config->zSeparate == SeparateSegmentKind::Code && prev && | |||
2557 | (prev->p_flags & PF_X) != (p->p_flags & PF_X)) || | |||
2558 | cmd->type == SHT_LLVM_PART_EHDR) | |||
2559 | cmd->addrExpr = [] { | |||
2560 | return alignTo(script->getDot(), config->maxPageSize); | |||
2561 | }; | |||
2562 | // PT_TLS is at the start of the first RW PT_LOAD. If `p` includes PT_TLS, | |||
2563 | // it must be the RW. Align to p_align(PT_TLS) to make sure | |||
2564 | // p_vaddr(PT_LOAD)%p_align(PT_LOAD) = 0. Otherwise, if | |||
2565 | // sh_addralign(.tdata) < sh_addralign(.tbss), we will set p_align(PT_TLS) | |||
2566 | // to sh_addralign(.tbss), while p_vaddr(PT_TLS)=p_vaddr(PT_LOAD) may not | |||
2567 | // be congruent to 0 modulo p_align(PT_TLS). | |||
2568 | // | |||
2569 | // Technically this is not required, but as of 2019, some dynamic loaders | |||
2570 | // don't handle p_vaddr%p_align != 0 correctly, e.g. glibc (i386 and | |||
2571 | // x86-64) doesn't make runtime address congruent to p_vaddr modulo | |||
2572 | // p_align for dynamic TLS blocks (PR/24606), FreeBSD rtld has the same | |||
2573 | // bug, musl (TLS Variant 1 architectures) before 1.1.23 handled TLS | |||
2574 | // blocks correctly. We need to keep the workaround for a while. | |||
2575 | else if (Out::tlsPhdr && Out::tlsPhdr->firstSec == p->firstSec) | |||
2576 | cmd->addrExpr = [] { | |||
2577 | return alignTo(script->getDot(), config->maxPageSize) + | |||
2578 | alignTo(script->getDot() % config->maxPageSize, | |||
2579 | Out::tlsPhdr->p_align); | |||
2580 | }; | |||
2581 | else | |||
2582 | cmd->addrExpr = [] { | |||
2583 | return alignTo(script->getDot(), config->maxPageSize) + | |||
2584 | script->getDot() % config->maxPageSize; | |||
2585 | }; | |||
2586 | } | |||
2587 | }; | |||
2588 | ||||
2589 | #ifdef __OpenBSD__1 | |||
2590 | // On i386, produce binaries that are compatible with our W^X implementation | |||
2591 | if (config->emachine == EM_386) { | |||
2592 | auto NXAlign = [](OutputSection *Cmd) { | |||
2593 | if (Cmd && !Cmd->addrExpr) | |||
2594 | Cmd->addrExpr = [=] { | |||
2595 | return alignTo(script->getDot(), 0x20000000); | |||
2596 | }; | |||
2597 | }; | |||
2598 | ||||
2599 | for (Partition &part : partitions) { | |||
2600 | PhdrEntry *firstRW = nullptr; | |||
2601 | for (PhdrEntry *P : part.phdrs) { | |||
2602 | if (P->p_type == PT_LOAD && (P->p_flags & PF_W)) { | |||
2603 | firstRW = P; | |||
2604 | break; | |||
2605 | } | |||
2606 | } | |||
2607 | ||||
2608 | if (firstRW) | |||
2609 | NXAlign(firstRW->firstSec); | |||
2610 | } | |||
2611 | } | |||
2612 | #endif | |||
2613 | ||||
2614 | for (Partition &part : partitions) { | |||
2615 | prev = nullptr; | |||
2616 | for (const PhdrEntry *p : part.phdrs) | |||
2617 | if (p->p_type == PT_LOAD && p->firstSec) { | |||
2618 | pageAlign(p); | |||
2619 | prev = p; | |||
2620 | } | |||
2621 | } | |||
2622 | } | |||
2623 | ||||
2624 | // Compute an in-file position for a given section. The file offset must be the | |||
2625 | // same with its virtual address modulo the page size, so that the loader can | |||
2626 | // load executables without any address adjustment. | |||
2627 | static uint64_t computeFileOffset(OutputSection *os, uint64_t off) { | |||
2628 | // The first section in a PT_LOAD has to have congruent offset and address | |||
2629 | // modulo the maximum page size. | |||
2630 | if (os->ptLoad && os->ptLoad->firstSec == os) | |||
2631 | return alignTo(off, os->ptLoad->p_align, os->addr); | |||
2632 | ||||
2633 | // File offsets are not significant for .bss sections other than the first one | |||
2634 | // in a PT_LOAD. By convention, we keep section offsets monotonically | |||
2635 | // increasing rather than setting to zero. | |||
2636 | if (os->type == SHT_NOBITS) | |||
2637 | return off; | |||
2638 | ||||
2639 | // If the section is not in a PT_LOAD, we just have to align it. | |||
2640 | if (!os->ptLoad) | |||
2641 | return alignTo(off, os->alignment); | |||
2642 | ||||
2643 | // If two sections share the same PT_LOAD the file offset is calculated | |||
2644 | // using this formula: Off2 = Off1 + (VA2 - VA1). | |||
2645 | OutputSection *first = os->ptLoad->firstSec; | |||
2646 | return first->offset + os->addr - first->addr; | |||
2647 | } | |||
2648 | ||||
2649 | // Set an in-file position to a given section and returns the end position of | |||
2650 | // the section. | |||
2651 | static uint64_t setFileOffset(OutputSection *os, uint64_t off) { | |||
2652 | off = computeFileOffset(os, off); | |||
2653 | os->offset = off; | |||
2654 | ||||
2655 | if (os->type == SHT_NOBITS) | |||
2656 | return off; | |||
2657 | return off + os->size; | |||
2658 | } | |||
2659 | ||||
2660 | template <class ELFT> void Writer<ELFT>::assignFileOffsetsBinary() { | |||
2661 | // Compute the minimum LMA of all non-empty non-NOBITS sections as minAddr. | |||
2662 | auto needsOffset = [](OutputSection &sec) { | |||
2663 | return sec.type != SHT_NOBITS && (sec.flags & SHF_ALLOC) && sec.size > 0; | |||
2664 | }; | |||
2665 | uint64_t minAddr = UINT64_MAX0xffffffffffffffffULL; | |||
2666 | for (OutputSection *sec : outputSections) | |||
2667 | if (needsOffset(*sec)) { | |||
2668 | sec->offset = sec->getLMA(); | |||
2669 | minAddr = std::min(minAddr, sec->offset); | |||
2670 | } | |||
2671 | ||||
2672 | // Sections are laid out at LMA minus minAddr. | |||
2673 | fileSize = 0; | |||
2674 | for (OutputSection *sec : outputSections) | |||
2675 | if (needsOffset(*sec)) { | |||
2676 | sec->offset -= minAddr; | |||
2677 | fileSize = std::max(fileSize, sec->offset + sec->size); | |||
2678 | } | |||
2679 | } | |||
2680 | ||||
2681 | static std::string rangeToString(uint64_t addr, uint64_t len) { | |||
2682 | return "[0x" + utohexstr(addr) + ", 0x" + utohexstr(addr + len - 1) + "]"; | |||
2683 | } | |||
2684 | ||||
2685 | // Assign file offsets to output sections. | |||
2686 | template <class ELFT> void Writer<ELFT>::assignFileOffsets() { | |||
2687 | uint64_t off = 0; | |||
2688 | off = setFileOffset(Out::elfHeader, off); | |||
2689 | off = setFileOffset(Out::programHeaders, off); | |||
2690 | ||||
2691 | PhdrEntry *lastRX = nullptr; | |||
2692 | for (Partition &part : partitions) | |||
2693 | for (PhdrEntry *p : part.phdrs) | |||
2694 | if (p->p_type == PT_LOAD && (p->p_flags & PF_X)) | |||
2695 | lastRX = p; | |||
2696 | ||||
2697 | // Layout SHF_ALLOC sections before non-SHF_ALLOC sections. A non-SHF_ALLOC | |||
2698 | // will not occupy file offsets contained by a PT_LOAD. | |||
2699 | for (OutputSection *sec : outputSections) { | |||
2700 | if (!(sec->flags & SHF_ALLOC)) | |||
2701 | continue; | |||
2702 | off = setFileOffset(sec, off); | |||
2703 | ||||
2704 | // If this is a last section of the last executable segment and that | |||
2705 | // segment is the last loadable segment, align the offset of the | |||
2706 | // following section to avoid loading non-segments parts of the file. | |||
2707 | if (config->zSeparate != SeparateSegmentKind::None && lastRX && | |||
2708 | lastRX->lastSec == sec) | |||
2709 | off = alignTo(off, config->commonPageSize); | |||
2710 | } | |||
2711 | for (OutputSection *sec : outputSections) | |||
2712 | if (!(sec->flags & SHF_ALLOC)) | |||
2713 | off = setFileOffset(sec, off); | |||
2714 | ||||
2715 | sectionHeaderOff = alignTo(off, config->wordsize); | |||
2716 | fileSize = sectionHeaderOff + (outputSections.size() + 1) * sizeof(Elf_Shdr); | |||
2717 | ||||
2718 | // Our logic assumes that sections have rising VA within the same segment. | |||
2719 | // With use of linker scripts it is possible to violate this rule and get file | |||
2720 | // offset overlaps or overflows. That should never happen with a valid script | |||
2721 | // which does not move the location counter backwards and usually scripts do | |||
2722 | // not do that. Unfortunately, there are apps in the wild, for example, Linux | |||
2723 | // kernel, which control segment distribution explicitly and move the counter | |||
2724 | // backwards, so we have to allow doing that to support linking them. We | |||
2725 | // perform non-critical checks for overlaps in checkSectionOverlap(), but here | |||
2726 | // we want to prevent file size overflows because it would crash the linker. | |||
2727 | for (OutputSection *sec : outputSections) { | |||
2728 | if (sec->type == SHT_NOBITS) | |||
2729 | continue; | |||
2730 | if ((sec->offset > fileSize) || (sec->offset + sec->size > fileSize)) | |||
2731 | error("unable to place section " + sec->name + " at file offset " + | |||
2732 | rangeToString(sec->offset, sec->size) + | |||
2733 | "; check your linker script for overflows"); | |||
2734 | } | |||
2735 | } | |||
2736 | ||||
2737 | // Finalize the program headers. We call this function after we assign | |||
2738 | // file offsets and VAs to all sections. | |||
2739 | template <class ELFT> void Writer<ELFT>::setPhdrs(Partition &part) { | |||
2740 | for (PhdrEntry *p : part.phdrs) { | |||
2741 | OutputSection *first = p->firstSec; | |||
2742 | OutputSection *last = p->lastSec; | |||
2743 | ||||
2744 | if (first) { | |||
2745 | p->p_filesz = last->offset - first->offset; | |||
2746 | if (last->type != SHT_NOBITS) | |||
2747 | p->p_filesz += last->size; | |||
2748 | ||||
2749 | p->p_memsz = last->addr + last->size - first->addr; | |||
2750 | p->p_offset = first->offset; | |||
2751 | p->p_vaddr = first->addr; | |||
2752 | ||||
2753 | // File offsets in partitions other than the main partition are relative | |||
2754 | // to the offset of the ELF headers. Perform that adjustment now. | |||
2755 | if (part.elfHeader) | |||
2756 | p->p_offset -= part.elfHeader->getParent()->offset; | |||
2757 | ||||
2758 | if (!p->hasLMA) | |||
2759 | p->p_paddr = first->getLMA(); | |||
2760 | } | |||
2761 | ||||
2762 | if (p->p_type == PT_GNU_RELRO) { | |||
2763 | p->p_align = 1; | |||
2764 | // musl/glibc ld.so rounds the size down, so we need to round up | |||
2765 | // to protect the last page. This is a no-op on FreeBSD which always | |||
2766 | // rounds up. | |||
2767 | p->p_memsz = alignTo(p->p_offset + p->p_memsz, config->commonPageSize) - | |||
2768 | p->p_offset; | |||
2769 | } | |||
2770 | } | |||
2771 | } | |||
2772 | ||||
2773 | // A helper struct for checkSectionOverlap. | |||
2774 | namespace { | |||
2775 | struct SectionOffset { | |||
2776 | OutputSection *sec; | |||
2777 | uint64_t offset; | |||
2778 | }; | |||
2779 | } // namespace | |||
2780 | ||||
2781 | // Check whether sections overlap for a specific address range (file offsets, | |||
2782 | // load and virtual addresses). | |||
2783 | static void checkOverlap(StringRef name, std::vector<SectionOffset> §ions, | |||
2784 | bool isVirtualAddr) { | |||
2785 | llvm::sort(sections, [=](const SectionOffset &a, const SectionOffset &b) { | |||
2786 | return a.offset < b.offset; | |||
2787 | }); | |||
2788 | ||||
2789 | // Finding overlap is easy given a vector is sorted by start position. | |||
2790 | // If an element starts before the end of the previous element, they overlap. | |||
2791 | for (size_t i = 1, end = sections.size(); i < end; ++i) { | |||
2792 | SectionOffset a = sections[i - 1]; | |||
2793 | SectionOffset b = sections[i]; | |||
2794 | if (b.offset >= a.offset + a.sec->size) | |||
2795 | continue; | |||
2796 | ||||
2797 | // If both sections are in OVERLAY we allow the overlapping of virtual | |||
2798 | // addresses, because it is what OVERLAY was designed for. | |||
2799 | if (isVirtualAddr && a.sec->inOverlay && b.sec->inOverlay) | |||
2800 | continue; | |||
2801 | ||||
2802 | errorOrWarn("section " + a.sec->name + " " + name + | |||
2803 | " range overlaps with " + b.sec->name + "\n>>> " + a.sec->name + | |||
2804 | " range is " + rangeToString(a.offset, a.sec->size) + "\n>>> " + | |||
2805 | b.sec->name + " range is " + | |||
2806 | rangeToString(b.offset, b.sec->size)); | |||
2807 | } | |||
2808 | } | |||
2809 | ||||
2810 | // Check for overlapping sections and address overflows. | |||
2811 | // | |||
2812 | // In this function we check that none of the output sections have overlapping | |||
2813 | // file offsets. For SHF_ALLOC sections we also check that the load address | |||
2814 | // ranges and the virtual address ranges don't overlap | |||
2815 | template <class ELFT> void Writer<ELFT>::checkSections() { | |||
2816 | // First, check that section's VAs fit in available address space for target. | |||
2817 | for (OutputSection *os : outputSections) | |||
2818 | if ((os->addr + os->size < os->addr) || | |||
2819 | (!ELFT::Is64Bits && os->addr + os->size > UINT32_MAX0xffffffffU)) | |||
2820 | errorOrWarn("section " + os->name + " at 0x" + utohexstr(os->addr) + | |||
2821 | " of size 0x" + utohexstr(os->size) + | |||
2822 | " exceeds available address space"); | |||
2823 | ||||
2824 | // Check for overlapping file offsets. In this case we need to skip any | |||
2825 | // section marked as SHT_NOBITS. These sections don't actually occupy space in | |||
2826 | // the file so Sec->Offset + Sec->Size can overlap with others. If --oformat | |||
2827 | // binary is specified only add SHF_ALLOC sections are added to the output | |||
2828 | // file so we skip any non-allocated sections in that case. | |||
2829 | std::vector<SectionOffset> fileOffs; | |||
2830 | for (OutputSection *sec : outputSections) | |||
2831 | if (sec->size > 0 && sec->type != SHT_NOBITS && | |||
2832 | (!config->oFormatBinary || (sec->flags & SHF_ALLOC))) | |||
2833 | fileOffs.push_back({sec, sec->offset}); | |||
2834 | checkOverlap("file", fileOffs, false); | |||
2835 | ||||
2836 | // When linking with -r there is no need to check for overlapping virtual/load | |||
2837 | // addresses since those addresses will only be assigned when the final | |||
2838 | // executable/shared object is created. | |||
2839 | if (config->relocatable) | |||
2840 | return; | |||
2841 | ||||
2842 | // Checking for overlapping virtual and load addresses only needs to take | |||
2843 | // into account SHF_ALLOC sections since others will not be loaded. | |||
2844 | // Furthermore, we also need to skip SHF_TLS sections since these will be | |||
2845 | // mapped to other addresses at runtime and can therefore have overlapping | |||
2846 | // ranges in the file. | |||
2847 | std::vector<SectionOffset> vmas; | |||
2848 | for (OutputSection *sec : outputSections) | |||
2849 | if (sec->size > 0 && (sec->flags & SHF_ALLOC) && !(sec->flags & SHF_TLS)) | |||
2850 | vmas.push_back({sec, sec->addr}); | |||
2851 | checkOverlap("virtual address", vmas, true); | |||
2852 | ||||
2853 | // Finally, check that the load addresses don't overlap. This will usually be | |||
2854 | // the same as the virtual addresses but can be different when using a linker | |||
2855 | // script with AT(). | |||
2856 | std::vector<SectionOffset> lmas; | |||
2857 | for (OutputSection *sec : outputSections) | |||
2858 | if (sec->size > 0 && (sec->flags & SHF_ALLOC) && !(sec->flags & SHF_TLS)) | |||
2859 | lmas.push_back({sec, sec->getLMA()}); | |||
2860 | checkOverlap("load address", lmas, false); | |||
2861 | } | |||
2862 | ||||
2863 | // The entry point address is chosen in the following ways. | |||
2864 | // | |||
2865 | // 1. the '-e' entry command-line option; | |||
2866 | // 2. the ENTRY(symbol) command in a linker control script; | |||
2867 | // 3. the value of the symbol _start, if present; | |||
2868 | // 4. the number represented by the entry symbol, if it is a number; | |||
2869 | // 5. the address of the first byte of the .text section, if present; | |||
2870 | // 6. the address 0. | |||
2871 | static uint64_t getEntryAddr() { | |||
2872 | // Case 1, 2 or 3 | |||
2873 | if (Symbol *b = symtab->find(config->entry)) | |||
2874 | return b->getVA(); | |||
2875 | ||||
2876 | // Case 4 | |||
2877 | uint64_t addr; | |||
2878 | if (to_integer(config->entry, addr)) | |||
2879 | return addr; | |||
2880 | ||||
2881 | // Case 5 | |||
2882 | if (OutputSection *sec = findSection(".text")) { | |||
2883 | if (config->warnMissingEntry) | |||
2884 | warn("cannot find entry symbol " + config->entry + "; defaulting to 0x" + | |||
2885 | utohexstr(sec->addr)); | |||
2886 | return sec->addr; | |||
2887 | } | |||
2888 | ||||
2889 | // Case 6 | |||
2890 | if (config->warnMissingEntry) | |||
2891 | warn("cannot find entry symbol " + config->entry + | |||
2892 | "; not setting start address"); | |||
2893 | return 0; | |||
2894 | } | |||
2895 | ||||
2896 | static uint16_t getELFType() { | |||
2897 | if (config->isPic) | |||
2898 | return ET_DYN; | |||
2899 | if (config->relocatable) | |||
2900 | return ET_REL; | |||
2901 | return ET_EXEC; | |||
2902 | } | |||
2903 | ||||
2904 | template <class ELFT> void Writer<ELFT>::writeHeader() { | |||
2905 | writeEhdr<ELFT>(Out::bufferStart, *mainPart); | |||
2906 | writePhdrs<ELFT>(Out::bufferStart + sizeof(Elf_Ehdr), *mainPart); | |||
2907 | ||||
2908 | auto *eHdr = reinterpret_cast<Elf_Ehdr *>(Out::bufferStart); | |||
2909 | eHdr->e_type = getELFType(); | |||
2910 | eHdr->e_entry = getEntryAddr(); | |||
2911 | eHdr->e_shoff = sectionHeaderOff; | |||
2912 | ||||
2913 | // Write the section header table. | |||
2914 | // | |||
2915 | // The ELF header can only store numbers up to SHN_LORESERVE in the e_shnum | |||
2916 | // and e_shstrndx fields. When the value of one of these fields exceeds | |||
2917 | // SHN_LORESERVE ELF requires us to put sentinel values in the ELF header and | |||
2918 | // use fields in the section header at index 0 to store | |||
2919 | // the value. The sentinel values and fields are: | |||
2920 | // e_shnum = 0, SHdrs[0].sh_size = number of sections. | |||
2921 | // e_shstrndx = SHN_XINDEX, SHdrs[0].sh_link = .shstrtab section index. | |||
2922 | auto *sHdrs = reinterpret_cast<Elf_Shdr *>(Out::bufferStart + eHdr->e_shoff); | |||
2923 | size_t num = outputSections.size() + 1; | |||
2924 | if (num >= SHN_LORESERVE) | |||
2925 | sHdrs->sh_size = num; | |||
2926 | else | |||
2927 | eHdr->e_shnum = num; | |||
2928 | ||||
2929 | uint32_t strTabIndex = in.shStrTab->getParent()->sectionIndex; | |||
2930 | if (strTabIndex >= SHN_LORESERVE) { | |||
2931 | sHdrs->sh_link = strTabIndex; | |||
2932 | eHdr->e_shstrndx = SHN_XINDEX; | |||
2933 | } else { | |||
2934 | eHdr->e_shstrndx = strTabIndex; | |||
2935 | } | |||
2936 | ||||
2937 | for (OutputSection *sec : outputSections) | |||
2938 | sec->writeHeaderTo<ELFT>(++sHdrs); | |||
2939 | } | |||
2940 | ||||
2941 | // Open a result file. | |||
2942 | template <class ELFT> void Writer<ELFT>::openFile() { | |||
2943 | uint64_t maxSize = config->is64 ? INT64_MAX0x7fffffffffffffffLL : UINT32_MAX0xffffffffU; | |||
2944 | if (fileSize != size_t(fileSize) || maxSize < fileSize) { | |||
2945 | std::string msg; | |||
2946 | raw_string_ostream s(msg); | |||
2947 | s << "output file too large: " << Twine(fileSize) << " bytes\n" | |||
2948 | << "section sizes:\n"; | |||
2949 | for (OutputSection *os : outputSections) | |||
2950 | s << os->name << ' ' << os->size << "\n"; | |||
2951 | error(s.str()); | |||
2952 | return; | |||
2953 | } | |||
2954 | ||||
2955 | unlinkAsync(config->outputFile); | |||
2956 | unsigned flags = 0; | |||
2957 | if (!config->relocatable) | |||
2958 | flags |= FileOutputBuffer::F_executable; | |||
2959 | if (!config->mmapOutputFile) | |||
2960 | flags |= FileOutputBuffer::F_no_mmap; | |||
2961 | Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr = | |||
2962 | FileOutputBuffer::create(config->outputFile, fileSize, flags); | |||
2963 | ||||
2964 | if (!bufferOrErr) { | |||
2965 | error("failed to open " + config->outputFile + ": " + | |||
2966 | llvm::toString(bufferOrErr.takeError())); | |||
2967 | return; | |||
2968 | } | |||
2969 | buffer = std::move(*bufferOrErr); | |||
2970 | Out::bufferStart = buffer->getBufferStart(); | |||
2971 | } | |||
2972 | ||||
2973 | template <class ELFT> void Writer<ELFT>::writeSectionsBinary() { | |||
2974 | for (OutputSection *sec : outputSections) | |||
2975 | if (sec->flags & SHF_ALLOC) | |||
2976 | sec->writeTo<ELFT>(Out::bufferStart + sec->offset); | |||
2977 | } | |||
2978 | ||||
2979 | static void fillTrap(uint8_t *i, uint8_t *end) { | |||
2980 | for (; i + 4 <= end; i += 4) | |||
2981 | memcpy(i, &target->trapInstr, 4); | |||
2982 | } | |||
2983 | ||||
2984 | // Fill the last page of executable segments with trap instructions | |||
2985 | // instead of leaving them as zero. Even though it is not required by any | |||
2986 | // standard, it is in general a good thing to do for security reasons. | |||
2987 | // | |||
2988 | // We'll leave other pages in segments as-is because the rest will be | |||
2989 | // overwritten by output sections. | |||
2990 | template <class ELFT> void Writer<ELFT>::writeTrapInstr() { | |||
2991 | for (Partition &part : partitions) { | |||
2992 | // Fill the last page. | |||
2993 | for (PhdrEntry *p : part.phdrs) | |||
2994 | if (p->p_type == PT_LOAD && (p->p_flags & PF_X)) | |||
2995 | fillTrap(Out::bufferStart + alignDown(p->firstSec->offset + p->p_filesz, | |||
2996 | config->commonPageSize), | |||
2997 | Out::bufferStart + alignTo(p->firstSec->offset + p->p_filesz, | |||
2998 | config->commonPageSize)); | |||
2999 | ||||
3000 | // Round up the file size of the last segment to the page boundary iff it is | |||
3001 | // an executable segment to ensure that other tools don't accidentally | |||
3002 | // trim the instruction padding (e.g. when stripping the file). | |||
3003 | PhdrEntry *last = nullptr; | |||
3004 | for (PhdrEntry *p : part.phdrs) | |||
3005 | if (p->p_type == PT_LOAD) | |||
3006 | last = p; | |||
3007 | ||||
3008 | if (last && (last->p_flags & PF_X)) | |||
3009 | last->p_memsz = last->p_filesz = | |||
3010 | alignTo(last->p_filesz, config->commonPageSize); | |||
3011 | } | |||
3012 | } | |||
3013 | ||||
3014 | // Write section contents to a mmap'ed file. | |||
3015 | template <class ELFT> void Writer<ELFT>::writeSections() { | |||
3016 | // In -r or -emit-relocs mode, write the relocation sections first as in | |||
3017 | // ELf_Rel targets we might find out that we need to modify the relocated | |||
3018 | // section while doing it. | |||
3019 | for (OutputSection *sec : outputSections) | |||
3020 | if (sec->type == SHT_REL || sec->type == SHT_RELA) | |||
3021 | sec->writeTo<ELFT>(Out::bufferStart + sec->offset); | |||
3022 | ||||
3023 | for (OutputSection *sec : outputSections) | |||
3024 | if (sec->type != SHT_REL && sec->type != SHT_RELA) | |||
3025 | sec->writeTo<ELFT>(Out::bufferStart + sec->offset); | |||
3026 | ||||
3027 | // Finally, check that all dynamic relocation addends were written correctly. | |||
3028 | if (config->checkDynamicRelocs && config->writeAddends) { | |||
3029 | for (OutputSection *sec : outputSections) | |||
3030 | if (sec->type == SHT_REL || sec->type == SHT_RELA) | |||
3031 | sec->checkDynRelAddends(Out::bufferStart); | |||
3032 | } | |||
3033 | } | |||
3034 | ||||
3035 | // Computes a hash value of Data using a given hash function. | |||
3036 | // In order to utilize multiple cores, we first split data into 1MB | |||
3037 | // chunks, compute a hash for each chunk, and then compute a hash value | |||
3038 | // of the hash values. | |||
3039 | static void | |||
3040 | computeHash(llvm::MutableArrayRef<uint8_t> hashBuf, | |||
3041 | llvm::ArrayRef<uint8_t> data, | |||
3042 | std::function<void(uint8_t *dest, ArrayRef<uint8_t> arr)> hashFn) { | |||
3043 | std::vector<ArrayRef<uint8_t>> chunks = split(data, 1024 * 1024); | |||
3044 | std::vector<uint8_t> hashes(chunks.size() * hashBuf.size()); | |||
3045 | ||||
3046 | // Compute hash values. | |||
3047 | parallelForEachN(0, chunks.size(), [&](size_t i) { | |||
3048 | hashFn(hashes.data() + i * hashBuf.size(), chunks[i]); | |||
3049 | }); | |||
3050 | ||||
3051 | // Write to the final output buffer. | |||
3052 | hashFn(hashBuf.data(), hashes); | |||
3053 | } | |||
3054 | ||||
3055 | template <class ELFT> void Writer<ELFT>::writeBuildId() { | |||
3056 | if (!mainPart->buildId || !mainPart->buildId->getParent()) | |||
3057 | return; | |||
3058 | ||||
3059 | if (config->buildId == BuildIdKind::Hexstring) { | |||
3060 | for (Partition &part : partitions) | |||
3061 | part.buildId->writeBuildId(config->buildIdVector); | |||
3062 | return; | |||
3063 | } | |||
3064 | ||||
3065 | // Compute a hash of all sections of the output file. | |||
3066 | size_t hashSize = mainPart->buildId->hashSize; | |||
3067 | std::vector<uint8_t> buildId(hashSize); | |||
3068 | llvm::ArrayRef<uint8_t> buf{Out::bufferStart, size_t(fileSize)}; | |||
3069 | ||||
3070 | switch (config->buildId) { | |||
3071 | case BuildIdKind::Fast: | |||
3072 | computeHash(buildId, buf, [](uint8_t *dest, ArrayRef<uint8_t> arr) { | |||
3073 | write64le(dest, xxHash64(arr)); | |||
3074 | }); | |||
3075 | break; | |||
3076 | case BuildIdKind::Md5: | |||
3077 | computeHash(buildId, buf, [&](uint8_t *dest, ArrayRef<uint8_t> arr) { | |||
3078 | memcpy(dest, MD5::hash(arr).data(), hashSize); | |||
3079 | }); | |||
3080 | break; | |||
3081 | case BuildIdKind::Sha1: | |||
3082 | computeHash(buildId, buf, [&](uint8_t *dest, ArrayRef<uint8_t> arr) { | |||
3083 | memcpy(dest, SHA1::hash(arr).data(), hashSize); | |||
3084 | }); | |||
3085 | break; | |||
3086 | case BuildIdKind::Uuid: | |||
3087 | if (auto ec = llvm::getRandomBytes(buildId.data(), hashSize)) | |||
3088 | error("entropy source failure: " + ec.message()); | |||
3089 | break; | |||
3090 | default: | |||
3091 | llvm_unreachable("unknown BuildIdKind")__builtin_unreachable(); | |||
3092 | } | |||
3093 | for (Partition &part : partitions) | |||
3094 | part.buildId->writeBuildId(buildId); | |||
3095 | } | |||
3096 | ||||
3097 | template void elf::createSyntheticSections<ELF32LE>(); | |||
3098 | template void elf::createSyntheticSections<ELF32BE>(); | |||
3099 | template void elf::createSyntheticSections<ELF64LE>(); | |||
3100 | template void elf::createSyntheticSections<ELF64BE>(); | |||
3101 | ||||
3102 | template void elf::writeResult<ELF32LE>(); | |||
3103 | template void elf::writeResult<ELF32BE>(); | |||
3104 | template void elf::writeResult<ELF64LE>(); | |||
3105 | template void elf::writeResult<ELF64BE>(); |
1 | //===----------------------------------------------------------------------===// |
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 | #ifndef _LIBCPP___ALGORITHM_STABLE_PARTITION_H |
10 | #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H |
11 | |
12 | #include <__config> |
13 | #include <__algorithm/rotate.h> |
14 | #include <__iterator/iterator_traits.h> |
15 | #include <__utility/swap.h> |
16 | #include <memory> |
17 | |
18 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
19 | #pragma GCC system_header |
20 | #endif |
21 | |
22 | _LIBCPP_PUSH_MACROSpush_macro("min") push_macro("max") |
23 | #include <__undef_macros> |
24 | |
25 | _LIBCPP_BEGIN_NAMESPACE_STDnamespace std { inline namespace __1 { |
26 | |
27 | template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> |
28 | _ForwardIterator |
29 | __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, |
30 | _Distance __len, _Pair __p, forward_iterator_tag __fit) |
31 | { |
32 | // *__first is known to be false |
33 | // __len >= 1 |
34 | if (__len == 1) |
35 | return __first; |
36 | if (__len == 2) |
37 | { |
38 | _ForwardIterator __m = __first; |
39 | if (__pred(*++__m)) |
40 | { |
41 | swap(*__first, *__m); |
42 | return __m; |
43 | } |
44 | return __first; |
45 | } |
46 | if (__len <= __p.second) |
47 | { // The buffer is big enough to use |
48 | typedef typename iterator_traits<_ForwardIterator>::value_type value_type; |
49 | __destruct_n __d(0); |
50 | unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); |
51 | // Move the falses into the temporary buffer, and the trues to the front of the line |
52 | // Update __first to always point to the end of the trues |
53 | value_type* __t = __p.first; |
54 | ::new ((void*)__t) value_type(_VSTDstd::__1::move(*__first)); |
55 | __d.template __incr<value_type>(); |
56 | ++__t; |
57 | _ForwardIterator __i = __first; |
58 | while (++__i != __last) |
59 | { |
60 | if (__pred(*__i)) |
61 | { |
62 | *__first = _VSTDstd::__1::move(*__i); |
63 | ++__first; |
64 | } |
65 | else |
66 | { |
67 | ::new ((void*)__t) value_type(_VSTDstd::__1::move(*__i)); |
68 | __d.template __incr<value_type>(); |
69 | ++__t; |
70 | } |
71 | } |
72 | // All trues now at start of range, all falses in buffer |
73 | // Move falses back into range, but don't mess up __first which points to first false |
74 | __i = __first; |
75 | for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) |
76 | *__i = _VSTDstd::__1::move(*__t2); |
77 | // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer |
78 | return __first; |
79 | } |
80 | // Else not enough buffer, do in place |
81 | // __len >= 3 |
82 | _ForwardIterator __m = __first; |
83 | _Distance __len2 = __len / 2; // __len2 >= 2 |
84 | _VSTDstd::__1::advance(__m, __len2); |
85 | // recurse on [__first, __m), *__first know to be false |
86 | // F????????????????? |
87 | // f m l |
88 | typedef typename add_lvalue_reference<_Predicate>::type _PredRef; |
89 | _ForwardIterator __first_false = _VSTDstd::__1::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); |
90 | // TTTFFFFF?????????? |
91 | // f ff m l |
92 | // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true |
93 | _ForwardIterator __m1 = __m; |
94 | _ForwardIterator __second_false = __last; |
95 | _Distance __len_half = __len - __len2; |
96 | while (__pred(*__m1)) |
97 | { |
98 | if (++__m1 == __last) |
99 | goto __second_half_done; |
100 | --__len_half; |
101 | } |
102 | // TTTFFFFFTTTF?????? |
103 | // f ff m m1 l |
104 | __second_false = _VSTDstd::__1::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); |
105 | __second_half_done: |
106 | // TTTFFFFFTTTTTFFFFF |
107 | // f ff m sf l |
108 | return _VSTDstd::__1::rotate(__first_false, __m, __second_false); |
109 | // TTTTTTTTFFFFFFFFFF |
110 | // | |
111 | } |
112 | |
113 | template <class _Predicate, class _ForwardIterator> |
114 | _ForwardIterator |
115 | __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, |
116 | forward_iterator_tag) |
117 | { |
118 | const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment |
119 | // Either prove all true and return __first or point to first false |
120 | while (true) |
121 | { |
122 | if (__first == __last) |
123 | return __first; |
124 | if (!__pred(*__first)) |
125 | break; |
126 | ++__first; |
127 | } |
128 | // We now have a reduced range [__first, __last) |
129 | // *__first is known to be false |
130 | typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; |
131 | typedef typename iterator_traits<_ForwardIterator>::value_type value_type; |
132 | difference_type __len = _VSTDstd::__1::distance(__first, __last); |
133 | pair<value_type*, ptrdiff_t> __p(0, 0); |
134 | unique_ptr<value_type, __return_temporary_buffer> __h; |
135 | if (__len >= __alloc_limit) |
136 | { |
137 | __p = _VSTDstd::__1::get_temporary_buffer<value_type>(__len); |
138 | __h.reset(__p.first); |
139 | } |
140 | return _VSTDstd::__1::__stable_partition<typename add_lvalue_reference<_Predicate>::type> |
141 | (__first, __last, __pred, __len, __p, forward_iterator_tag()); |
142 | } |
143 | |
144 | template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> |
145 | _BidirectionalIterator |
146 | __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, |
147 | _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) |
148 | { |
149 | // *__first is known to be false |
150 | // *__last is known to be true |
151 | // __len >= 2 |
152 | if (__len == 2) |
153 | { |
154 | swap(*__first, *__last); |
155 | return __last; |
156 | } |
157 | if (__len == 3) |
158 | { |
159 | _BidirectionalIterator __m = __first; |
160 | if (__pred(*++__m)) |
161 | { |
162 | swap(*__first, *__m); |
163 | swap(*__m, *__last); |
164 | return __last; |
165 | } |
166 | swap(*__m, *__last); |
167 | swap(*__first, *__m); |
168 | return __m; |
169 | } |
170 | if (__len <= __p.second) |
171 | { // The buffer is big enough to use |
172 | typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; |
173 | __destruct_n __d(0); |
174 | unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); |
175 | // Move the falses into the temporary buffer, and the trues to the front of the line |
176 | // Update __first to always point to the end of the trues |
177 | value_type* __t = __p.first; |
178 | ::new ((void*)__t) value_type(_VSTDstd::__1::move(*__first)); |
179 | __d.template __incr<value_type>(); |
180 | ++__t; |
181 | _BidirectionalIterator __i = __first; |
182 | while (++__i != __last) |
183 | { |
184 | if (__pred(*__i)) |
185 | { |
186 | *__first = _VSTDstd::__1::move(*__i); |
187 | ++__first; |
188 | } |
189 | else |
190 | { |
191 | ::new ((void*)__t) value_type(_VSTDstd::__1::move(*__i)); |
192 | __d.template __incr<value_type>(); |
193 | ++__t; |
194 | } |
195 | } |
196 | // move *__last, known to be true |
197 | *__first = _VSTDstd::__1::move(*__i); |
198 | __i = ++__first; |
199 | // All trues now at start of range, all falses in buffer |
200 | // Move falses back into range, but don't mess up __first which points to first false |
201 | for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) |
202 | *__i = _VSTDstd::__1::move(*__t2); |
203 | // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer |
204 | return __first; |
205 | } |
206 | // Else not enough buffer, do in place |
207 | // __len >= 4 |
208 | _BidirectionalIterator __m = __first; |
209 | _Distance __len2 = __len / 2; // __len2 >= 2 |
210 | _VSTDstd::__1::advance(__m, __len2); |
211 | // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false |
212 | // F????????????????T |
213 | // f m l |
214 | _BidirectionalIterator __m1 = __m; |
215 | _BidirectionalIterator __first_false = __first; |
216 | _Distance __len_half = __len2; |
217 | while (!__pred(*--__m1)) |
218 | { |
219 | if (__m1 == __first) |
220 | goto __first_half_done; |
221 | --__len_half; |
222 | } |
223 | // F???TFFF?????????T |
224 | // f m1 m l |
225 | typedef typename add_lvalue_reference<_Predicate>::type _PredRef; |
226 | __first_false = _VSTDstd::__1::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); |
227 | __first_half_done: |
228 | // TTTFFFFF?????????T |
229 | // f ff m l |
230 | // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true |
231 | __m1 = __m; |
232 | _BidirectionalIterator __second_false = __last; |
233 | ++__second_false; |
234 | __len_half = __len - __len2; |
235 | while (__pred(*__m1)) |
236 | { |
237 | if (++__m1 == __last) |
238 | goto __second_half_done; |
239 | --__len_half; |
240 | } |
241 | // TTTFFFFFTTTF?????T |
242 | // f ff m m1 l |
243 | __second_false = _VSTDstd::__1::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); |
244 | __second_half_done: |
245 | // TTTFFFFFTTTTTFFFFF |
246 | // f ff m sf l |
247 | return _VSTDstd::__1::rotate(__first_false, __m, __second_false); |
248 | // TTTTTTTTFFFFFFFFFF |
249 | // | |
250 | } |
251 | |
252 | template <class _Predicate, class _BidirectionalIterator> |
253 | _BidirectionalIterator |
254 | __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, |
255 | bidirectional_iterator_tag) |
256 | { |
257 | typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; |
258 | typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; |
259 | const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment |
260 | // Either prove all true and return __first or point to first false |
261 | while (true) |
262 | { |
263 | if (__first == __last) |
264 | return __first; |
265 | if (!__pred(*__first)) |
266 | break; |
267 | ++__first; |
268 | } |
269 | // __first points to first false, everything prior to __first is already set. |
270 | // Either prove [__first, __last) is all false and return __first, or point __last to last true |
271 | do |
272 | { |
273 | if (__first == --__last) |
274 | return __first; |
275 | } while (!__pred(*__last)); |
276 | // We now have a reduced range [__first, __last] |
277 | // *__first is known to be false |
278 | // *__last is known to be true |
279 | // __len >= 2 |
280 | difference_type __len = _VSTDstd::__1::distance(__first, __last) + 1; |
281 | pair<value_type*, ptrdiff_t> __p(0, 0); |
282 | unique_ptr<value_type, __return_temporary_buffer> __h; |
283 | if (__len >= __alloc_limit) |
284 | { |
285 | __p = _VSTDstd::__1::get_temporary_buffer<value_type>(__len); |
286 | __h.reset(__p.first); |
287 | } |
288 | return _VSTDstd::__1::__stable_partition<typename add_lvalue_reference<_Predicate>::type> |
289 | (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); |
290 | } |
291 | |
292 | template <class _ForwardIterator, class _Predicate> |
293 | inline _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__ )) |
294 | _ForwardIterator |
295 | stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) |
296 | { |
297 | return _VSTDstd::__1::__stable_partition<typename add_lvalue_reference<_Predicate>::type> |
298 | (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); |
299 | } |
300 | |
301 | _LIBCPP_END_NAMESPACE_STD} } |
302 | |
303 | _LIBCPP_POP_MACROSpop_macro("min") pop_macro("max") |
304 | |
305 | #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H |