1 //===- OutputSections.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 "OutputSections.h"
10 #include "Config.h"
11 #include "InputFiles.h"
12 #include "LinkerScript.h"
13 #include "Symbols.h"
14 #include "SyntheticSections.h"
15 #include "Target.h"
16 #include "lld/Common/Arrays.h"
17 #include "lld/Common/Memory.h"
18 #include "llvm/BinaryFormat/Dwarf.h"
19 #include "llvm/Config/llvm-config.h" // LLVM_ENABLE_ZLIB
20 #include "llvm/Support/Compression.h"
21 #include "llvm/Support/Parallel.h"
22 #include "llvm/Support/Path.h"
23 #include "llvm/Support/TimeProfiler.h"
24 #if LLVM_ENABLE_ZLIB
25 // Avoid introducing max as a macro from Windows headers.
26 #define NOMINMAX
27 #include <zlib.h>
28 #endif
29 #if LLVM_ENABLE_ZSTD
30 #include <zstd.h>
31 #endif
32
33 using namespace llvm;
34 using namespace llvm::dwarf;
35 using namespace llvm::object;
36 using namespace llvm::support::endian;
37 using namespace llvm::ELF;
38 using namespace lld;
39 using namespace lld::elf;
40
41 uint8_t *Out::bufferStart;
42 PhdrEntry *Out::tlsPhdr;
43 OutputSection *Out::elfHeader;
44 OutputSection *Out::programHeaders;
45 OutputSection *Out::preinitArray;
46 OutputSection *Out::initArray;
47 OutputSection *Out::finiArray;
48
49 SmallVector<OutputSection *, 0> elf::outputSections;
50
getPhdrFlags() const51 uint32_t OutputSection::getPhdrFlags() const {
52 uint32_t ret = 0;
53 if (config->emachine != EM_ARM || !(flags & SHF_ARM_PURECODE))
54 ret |= PF_R;
55 if (flags & SHF_WRITE)
56 ret |= PF_W;
57 if (flags & SHF_EXECINSTR)
58 ret |= PF_X;
59 return ret;
60 }
61
62 template <class ELFT>
writeHeaderTo(typename ELFT::Shdr * shdr)63 void OutputSection::writeHeaderTo(typename ELFT::Shdr *shdr) {
64 shdr->sh_entsize = entsize;
65 shdr->sh_addralign = addralign;
66 shdr->sh_type = type;
67 shdr->sh_offset = offset;
68 shdr->sh_flags = flags;
69 shdr->sh_info = info;
70 shdr->sh_link = link;
71 shdr->sh_addr = addr;
72 shdr->sh_size = size;
73 shdr->sh_name = shName;
74 }
75
OutputSection(StringRef name,uint32_t type,uint64_t flags)76 OutputSection::OutputSection(StringRef name, uint32_t type, uint64_t flags)
77 : SectionBase(Output, name, flags, /*Entsize*/ 0, /*Alignment*/ 1, type,
78 /*Info*/ 0, /*Link*/ 0) {}
79
80 // We allow sections of types listed below to merged into a
81 // single progbits section. This is typically done by linker
82 // scripts. Merging nobits and progbits will force disk space
83 // to be allocated for nobits sections. Other ones don't require
84 // any special treatment on top of progbits, so there doesn't
85 // seem to be a harm in merging them.
86 //
87 // NOTE: clang since rL252300 emits SHT_X86_64_UNWIND .eh_frame sections. Allow
88 // them to be merged into SHT_PROGBITS .eh_frame (GNU as .cfi_*).
canMergeToProgbits(unsigned type)89 static bool canMergeToProgbits(unsigned type) {
90 return type == SHT_NOBITS || type == SHT_PROGBITS || type == SHT_INIT_ARRAY ||
91 type == SHT_PREINIT_ARRAY || type == SHT_FINI_ARRAY ||
92 type == SHT_NOTE ||
93 (type == SHT_X86_64_UNWIND && config->emachine == EM_X86_64);
94 }
95
96 // Record that isec will be placed in the OutputSection. isec does not become
97 // permanent until finalizeInputSections() is called. The function should not be
98 // used after finalizeInputSections() is called. If you need to add an
99 // InputSection post finalizeInputSections(), then you must do the following:
100 //
101 // 1. Find or create an InputSectionDescription to hold InputSection.
102 // 2. Add the InputSection to the InputSectionDescription::sections.
103 // 3. Call commitSection(isec).
recordSection(InputSectionBase * isec)104 void OutputSection::recordSection(InputSectionBase *isec) {
105 partition = isec->partition;
106 isec->parent = this;
107 if (commands.empty() || !isa<InputSectionDescription>(commands.back()))
108 commands.push_back(make<InputSectionDescription>(""));
109 auto *isd = cast<InputSectionDescription>(commands.back());
110 isd->sectionBases.push_back(isec);
111 }
112
113 // Update fields (type, flags, alignment, etc) according to the InputSection
114 // isec. Also check whether the InputSection flags and type are consistent with
115 // other InputSections.
commitSection(InputSection * isec)116 void OutputSection::commitSection(InputSection *isec) {
117 if (LLVM_UNLIKELY(type != isec->type)) {
118 if (hasInputSections || typeIsSet) {
119 if (typeIsSet || !canMergeToProgbits(type) ||
120 !canMergeToProgbits(isec->type)) {
121 // The (NOLOAD) changes the section type to SHT_NOBITS, the intention is
122 // that the contents at that address is provided by some other means.
123 // Some projects (e.g.
124 // https://github.com/ClangBuiltLinux/linux/issues/1597) rely on the
125 // behavior. Other types get an error.
126 if (type != SHT_NOBITS) {
127 errorOrWarn("section type mismatch for " + isec->name + "\n>>> " +
128 toString(isec) + ": " +
129 getELFSectionTypeName(config->emachine, isec->type) +
130 "\n>>> output section " + name + ": " +
131 getELFSectionTypeName(config->emachine, type));
132 }
133 }
134 if (!typeIsSet)
135 type = SHT_PROGBITS;
136 } else {
137 type = isec->type;
138 }
139 }
140 if (!hasInputSections) {
141 // If IS is the first section to be added to this section,
142 // initialize type, entsize and flags from isec.
143 hasInputSections = true;
144 entsize = isec->entsize;
145 flags = isec->flags;
146 } else {
147 // Otherwise, check if new type or flags are compatible with existing ones.
148 if ((flags ^ isec->flags) & SHF_TLS)
149 error("incompatible section flags for " + name + "\n>>> " +
150 toString(isec) + ": 0x" + utohexstr(isec->flags) +
151 "\n>>> output section " + name + ": 0x" + utohexstr(flags));
152 }
153
154 isec->parent = this;
155 uint64_t andMask =
156 config->emachine == EM_ARM ? (uint64_t)SHF_ARM_PURECODE : 0;
157 uint64_t orMask = ~andMask;
158 uint64_t andFlags = (flags & isec->flags) & andMask;
159 uint64_t orFlags = (flags | isec->flags) & orMask;
160 flags = andFlags | orFlags;
161 if (nonAlloc)
162 flags &= ~(uint64_t)SHF_ALLOC;
163
164 addralign = std::max(addralign, isec->addralign);
165
166 // If this section contains a table of fixed-size entries, sh_entsize
167 // holds the element size. If it contains elements of different size we
168 // set sh_entsize to 0.
169 if (entsize != isec->entsize)
170 entsize = 0;
171 }
172
createMergeSynthetic(StringRef name,uint32_t type,uint64_t flags,uint32_t addralign)173 static MergeSyntheticSection *createMergeSynthetic(StringRef name,
174 uint32_t type,
175 uint64_t flags,
176 uint32_t addralign) {
177 if ((flags & SHF_STRINGS) && config->optimize >= 2)
178 return make<MergeTailSection>(name, type, flags, addralign);
179 return make<MergeNoTailSection>(name, type, flags, addralign);
180 }
181
182 // This function scans over the InputSectionBase list sectionBases to create
183 // InputSectionDescription::sections.
184 //
185 // It removes MergeInputSections from the input section array and adds
186 // new synthetic sections at the location of the first input section
187 // that it replaces. It then finalizes each synthetic section in order
188 // to compute an output offset for each piece of each input section.
finalizeInputSections()189 void OutputSection::finalizeInputSections() {
190 std::vector<MergeSyntheticSection *> mergeSections;
191 for (SectionCommand *cmd : commands) {
192 auto *isd = dyn_cast<InputSectionDescription>(cmd);
193 if (!isd)
194 continue;
195 isd->sections.reserve(isd->sectionBases.size());
196 for (InputSectionBase *s : isd->sectionBases) {
197 MergeInputSection *ms = dyn_cast<MergeInputSection>(s);
198 if (!ms) {
199 isd->sections.push_back(cast<InputSection>(s));
200 continue;
201 }
202
203 // We do not want to handle sections that are not alive, so just remove
204 // them instead of trying to merge.
205 if (!ms->isLive())
206 continue;
207
208 auto i = llvm::find_if(mergeSections, [=](MergeSyntheticSection *sec) {
209 // While we could create a single synthetic section for two different
210 // values of Entsize, it is better to take Entsize into consideration.
211 //
212 // With a single synthetic section no two pieces with different Entsize
213 // could be equal, so we may as well have two sections.
214 //
215 // Using Entsize in here also allows us to propagate it to the synthetic
216 // section.
217 //
218 // SHF_STRINGS section with different alignments should not be merged.
219 return sec->flags == ms->flags && sec->entsize == ms->entsize &&
220 (sec->addralign == ms->addralign || !(sec->flags & SHF_STRINGS));
221 });
222 if (i == mergeSections.end()) {
223 MergeSyntheticSection *syn =
224 createMergeSynthetic(s->name, ms->type, ms->flags, ms->addralign);
225 mergeSections.push_back(syn);
226 i = std::prev(mergeSections.end());
227 syn->entsize = ms->entsize;
228 isd->sections.push_back(syn);
229 }
230 (*i)->addSection(ms);
231 }
232
233 // sectionBases should not be used from this point onwards. Clear it to
234 // catch misuses.
235 isd->sectionBases.clear();
236
237 // Some input sections may be removed from the list after ICF.
238 for (InputSection *s : isd->sections)
239 commitSection(s);
240 }
241 for (auto *ms : mergeSections)
242 ms->finalizeContents();
243 }
244
sortByOrder(MutableArrayRef<InputSection * > in,llvm::function_ref<int (InputSectionBase * s)> order)245 static void sortByOrder(MutableArrayRef<InputSection *> in,
246 llvm::function_ref<int(InputSectionBase *s)> order) {
247 std::vector<std::pair<int, InputSection *>> v;
248 for (InputSection *s : in)
249 v.emplace_back(order(s), s);
250 llvm::stable_sort(v, less_first());
251
252 for (size_t i = 0; i < v.size(); ++i)
253 in[i] = v[i].second;
254 }
255
getHeaderSize()256 uint64_t elf::getHeaderSize() {
257 if (config->oFormatBinary)
258 return 0;
259 return Out::elfHeader->size + Out::programHeaders->size;
260 }
261
sort(llvm::function_ref<int (InputSectionBase * s)> order)262 void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
263 assert(isLive());
264 for (SectionCommand *b : commands)
265 if (auto *isd = dyn_cast<InputSectionDescription>(b))
266 sortByOrder(isd->sections, order);
267 }
268
nopInstrFill(uint8_t * buf,size_t size)269 static void nopInstrFill(uint8_t *buf, size_t size) {
270 if (size == 0)
271 return;
272 unsigned i = 0;
273 if (size == 0)
274 return;
275 std::vector<std::vector<uint8_t>> nopFiller = *target->nopInstrs;
276 unsigned num = size / nopFiller.back().size();
277 for (unsigned c = 0; c < num; ++c) {
278 memcpy(buf + i, nopFiller.back().data(), nopFiller.back().size());
279 i += nopFiller.back().size();
280 }
281 unsigned remaining = size - i;
282 if (!remaining)
283 return;
284 assert(nopFiller[remaining - 1].size() == remaining);
285 memcpy(buf + i, nopFiller[remaining - 1].data(), remaining);
286 }
287
288 // Fill [Buf, Buf + Size) with Filler.
289 // This is used for linker script "=fillexp" command.
fill(uint8_t * buf,size_t size,const std::array<uint8_t,4> & filler)290 static void fill(uint8_t *buf, size_t size,
291 const std::array<uint8_t, 4> &filler) {
292 size_t i = 0;
293 for (; i + 4 < size; i += 4)
294 memcpy(buf + i, filler.data(), 4);
295 memcpy(buf + i, filler.data(), size - i);
296 }
297
298 #if LLVM_ENABLE_ZLIB
deflateShard(ArrayRef<uint8_t> in,int level,int flush)299 static SmallVector<uint8_t, 0> deflateShard(ArrayRef<uint8_t> in, int level,
300 int flush) {
301 // 15 and 8 are default. windowBits=-15 is negative to generate raw deflate
302 // data with no zlib header or trailer.
303 z_stream s = {};
304 deflateInit2(&s, level, Z_DEFLATED, -15, 8, Z_DEFAULT_STRATEGY);
305 s.next_in = const_cast<uint8_t *>(in.data());
306 s.avail_in = in.size();
307
308 // Allocate a buffer of half of the input size, and grow it by 1.5x if
309 // insufficient.
310 SmallVector<uint8_t, 0> out;
311 size_t pos = 0;
312 out.resize_for_overwrite(std::max<size_t>(in.size() / 2, 64));
313 do {
314 if (pos == out.size())
315 out.resize_for_overwrite(out.size() * 3 / 2);
316 s.next_out = out.data() + pos;
317 s.avail_out = out.size() - pos;
318 (void)deflate(&s, flush);
319 pos = s.next_out - out.data();
320 } while (s.avail_out == 0);
321 assert(s.avail_in == 0);
322
323 out.truncate(pos);
324 deflateEnd(&s);
325 return out;
326 }
327 #endif
328
329 // Compress section contents if this section contains debug info.
maybeCompress()330 template <class ELFT> void OutputSection::maybeCompress() {
331 using Elf_Chdr = typename ELFT::Chdr;
332 (void)sizeof(Elf_Chdr);
333
334 // Compress only DWARF debug sections.
335 if (config->compressDebugSections == DebugCompressionType::None ||
336 (flags & SHF_ALLOC) || !name.starts_with(".debug_") || size == 0)
337 return;
338
339 llvm::TimeTraceScope timeScope("Compress debug sections");
340 compressed.uncompressedSize = size;
341 auto buf = std::make_unique<uint8_t[]>(size);
342 // Write uncompressed data to a temporary zero-initialized buffer.
343 {
344 parallel::TaskGroup tg;
345 writeTo<ELFT>(buf.get(), tg);
346 }
347
348 #if LLVM_ENABLE_ZSTD
349 // Use ZSTD's streaming compression API which permits parallel workers working
350 // on the stream. See http://facebook.github.io/zstd/zstd_manual.html
351 // "Streaming compression - HowTo".
352 if (config->compressDebugSections == DebugCompressionType::Zstd) {
353 // Allocate a buffer of half of the input size, and grow it by 1.5x if
354 // insufficient.
355 compressed.shards = std::make_unique<SmallVector<uint8_t, 0>[]>(1);
356 SmallVector<uint8_t, 0> &out = compressed.shards[0];
357 out.resize_for_overwrite(std::max<size_t>(size / 2, 32));
358 size_t pos = 0;
359
360 ZSTD_CCtx *cctx = ZSTD_createCCtx();
361 // Ignore error if zstd was not built with ZSTD_MULTITHREAD.
362 (void)ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers,
363 parallel::strategy.compute_thread_count());
364 ZSTD_outBuffer zob = {out.data(), out.size(), 0};
365 ZSTD_EndDirective directive = ZSTD_e_continue;
366 const size_t blockSize = ZSTD_CStreamInSize();
367 do {
368 const size_t n = std::min(static_cast<size_t>(size - pos), blockSize);
369 if (n == size - pos)
370 directive = ZSTD_e_end;
371 ZSTD_inBuffer zib = {buf.get() + pos, n, 0};
372 size_t bytesRemaining = 0;
373 while (zib.pos != zib.size ||
374 (directive == ZSTD_e_end && bytesRemaining != 0)) {
375 if (zob.pos == zob.size) {
376 out.resize_for_overwrite(out.size() * 3 / 2);
377 zob.dst = out.data();
378 zob.size = out.size();
379 }
380 bytesRemaining = ZSTD_compressStream2(cctx, &zob, &zib, directive);
381 assert(!ZSTD_isError(bytesRemaining));
382 }
383 pos += n;
384 } while (directive != ZSTD_e_end);
385 out.resize(zob.pos);
386 ZSTD_freeCCtx(cctx);
387
388 size = sizeof(Elf_Chdr) + out.size();
389 flags |= SHF_COMPRESSED;
390 return;
391 }
392 #endif
393
394 #if LLVM_ENABLE_ZLIB
395 // We chose 1 (Z_BEST_SPEED) as the default compression level because it is
396 // the fastest. If -O2 is given, we use level 6 to compress debug info more by
397 // ~15%. We found that level 7 to 9 doesn't make much difference (~1% more
398 // compression) while they take significant amount of time (~2x), so level 6
399 // seems enough.
400 const int level = config->optimize >= 2 ? 6 : Z_BEST_SPEED;
401
402 // Split input into 1-MiB shards.
403 constexpr size_t shardSize = 1 << 20;
404 auto shardsIn = split(ArrayRef<uint8_t>(buf.get(), size), shardSize);
405 const size_t numShards = shardsIn.size();
406
407 // Compress shards and compute Alder-32 checksums. Use Z_SYNC_FLUSH for all
408 // shards but the last to flush the output to a byte boundary to be
409 // concatenated with the next shard.
410 auto shardsOut = std::make_unique<SmallVector<uint8_t, 0>[]>(numShards);
411 auto shardsAdler = std::make_unique<uint32_t[]>(numShards);
412 parallelFor(0, numShards, [&](size_t i) {
413 shardsOut[i] = deflateShard(shardsIn[i], level,
414 i != numShards - 1 ? Z_SYNC_FLUSH : Z_FINISH);
415 shardsAdler[i] = adler32(1, shardsIn[i].data(), shardsIn[i].size());
416 });
417
418 // Update section size and combine Alder-32 checksums.
419 uint32_t checksum = 1; // Initial Adler-32 value
420 size = sizeof(Elf_Chdr) + 2; // Elf_Chdir and zlib header
421 for (size_t i = 0; i != numShards; ++i) {
422 size += shardsOut[i].size();
423 checksum = adler32_combine(checksum, shardsAdler[i], shardsIn[i].size());
424 }
425 size += 4; // checksum
426
427 compressed.shards = std::move(shardsOut);
428 compressed.numShards = numShards;
429 compressed.checksum = checksum;
430 flags |= SHF_COMPRESSED;
431 #endif
432 }
433
writeInt(uint8_t * buf,uint64_t data,uint64_t size)434 static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
435 if (size == 1)
436 *buf = data;
437 else if (size == 2)
438 write16(buf, data);
439 else if (size == 4)
440 write32(buf, data);
441 else if (size == 8)
442 write64(buf, data);
443 else
444 llvm_unreachable("unsupported Size argument");
445 }
446
447 template <class ELFT>
writeTo(uint8_t * buf,parallel::TaskGroup & tg)448 void OutputSection::writeTo(uint8_t *buf, parallel::TaskGroup &tg) {
449 llvm::TimeTraceScope timeScope("Write sections", name);
450 if (type == SHT_NOBITS)
451 return;
452
453 // If --compress-debug-section is specified and if this is a debug section,
454 // we've already compressed section contents. If that's the case,
455 // just write it down.
456 if (compressed.shards) {
457 auto *chdr = reinterpret_cast<typename ELFT::Chdr *>(buf);
458 chdr->ch_size = compressed.uncompressedSize;
459 chdr->ch_addralign = addralign;
460 buf += sizeof(*chdr);
461 if (config->compressDebugSections == DebugCompressionType::Zstd) {
462 chdr->ch_type = ELFCOMPRESS_ZSTD;
463 memcpy(buf, compressed.shards[0].data(), compressed.shards[0].size());
464 return;
465 }
466 chdr->ch_type = ELFCOMPRESS_ZLIB;
467
468 // Compute shard offsets.
469 auto offsets = std::make_unique<size_t[]>(compressed.numShards);
470 offsets[0] = 2; // zlib header
471 for (size_t i = 1; i != compressed.numShards; ++i)
472 offsets[i] = offsets[i - 1] + compressed.shards[i - 1].size();
473
474 buf[0] = 0x78; // CMF
475 buf[1] = 0x01; // FLG: best speed
476 parallelFor(0, compressed.numShards, [&](size_t i) {
477 memcpy(buf + offsets[i], compressed.shards[i].data(),
478 compressed.shards[i].size());
479 });
480
481 write32be(buf + (size - sizeof(*chdr) - 4), compressed.checksum);
482 return;
483 }
484
485 // Write leading padding.
486 ArrayRef<InputSection *> sections = getInputSections(*this, storage);
487 std::array<uint8_t, 4> filler = getFiller();
488 bool nonZeroFiller = read32(filler.data()) != 0;
489 if (nonZeroFiller)
490 fill(buf, sections.empty() ? size : sections[0]->outSecOff, filler);
491
492 auto fn = [=](size_t begin, size_t end) {
493 size_t numSections = sections.size();
494 for (size_t i = begin; i != end; ++i) {
495 InputSection *isec = sections[i];
496 if (auto *s = dyn_cast<SyntheticSection>(isec))
497 s->writeTo(buf + isec->outSecOff);
498 else
499 isec->writeTo<ELFT>(buf + isec->outSecOff);
500
501 // When in Arm BE8 mode, the linker has to convert the big-endian
502 // instructions to little-endian, leaving the data big-endian.
503 if (config->emachine == EM_ARM && !config->isLE && config->armBe8 &&
504 (flags & SHF_EXECINSTR))
505 convertArmInstructionstoBE8(isec, buf + isec->outSecOff);
506
507 // Fill gaps between sections.
508 if (nonZeroFiller) {
509 uint8_t *start = buf + isec->outSecOff + isec->getSize();
510 uint8_t *end;
511 if (i + 1 == numSections)
512 end = buf + size;
513 else
514 end = buf + sections[i + 1]->outSecOff;
515 if (isec->nopFiller) {
516 assert(target->nopInstrs);
517 nopInstrFill(start, end - start);
518 } else
519 fill(start, end - start, filler);
520 }
521 }
522 };
523
524 // If there is any BYTE()-family command (rare), write the section content
525 // first then process BYTE to overwrite the filler content. The write is
526 // serial due to the limitation of llvm/Support/Parallel.h.
527 bool written = false;
528 size_t numSections = sections.size();
529 for (SectionCommand *cmd : commands)
530 if (auto *data = dyn_cast<ByteCommand>(cmd)) {
531 if (!std::exchange(written, true))
532 fn(0, numSections);
533 writeInt(buf + data->offset, data->expression().getValue(), data->size);
534 }
535 if (written || !numSections)
536 return;
537
538 // There is no data command. Write content asynchronously to overlap the write
539 // time with other output sections. Note, if a linker script specifies
540 // overlapping output sections (needs --noinhibit-exec or --no-check-sections
541 // to supress the error), the output may be non-deterministic.
542 const size_t taskSizeLimit = 4 << 20;
543 for (size_t begin = 0, i = 0, taskSize = 0;;) {
544 taskSize += sections[i]->getSize();
545 bool done = ++i == numSections;
546 if (done || taskSize >= taskSizeLimit) {
547 tg.spawn([=] { fn(begin, i); });
548 if (done)
549 break;
550 begin = i;
551 taskSize = 0;
552 }
553 }
554 }
555
finalizeShtGroup(OutputSection * os,InputSection * section)556 static void finalizeShtGroup(OutputSection *os, InputSection *section) {
557 // sh_link field for SHT_GROUP sections should contain the section index of
558 // the symbol table.
559 os->link = in.symTab->getParent()->sectionIndex;
560
561 if (!section)
562 return;
563
564 // sh_info then contain index of an entry in symbol table section which
565 // provides signature of the section group.
566 ArrayRef<Symbol *> symbols = section->file->getSymbols();
567 os->info = in.symTab->getSymbolIndex(symbols[section->info]);
568
569 // Some group members may be combined or discarded, so we need to compute the
570 // new size. The content will be rewritten in InputSection::copyShtGroup.
571 DenseSet<uint32_t> seen;
572 ArrayRef<InputSectionBase *> sections = section->file->getSections();
573 for (const uint32_t &idx : section->getDataAs<uint32_t>().slice(1))
574 if (OutputSection *osec = sections[read32(&idx)]->getOutputSection())
575 seen.insert(osec->sectionIndex);
576 os->size = (1 + seen.size()) * sizeof(uint32_t);
577 }
578
finalize()579 void OutputSection::finalize() {
580 InputSection *first = getFirstInputSection(this);
581
582 if (flags & SHF_LINK_ORDER) {
583 // We must preserve the link order dependency of sections with the
584 // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
585 // need to translate the InputSection sh_link to the OutputSection sh_link,
586 // all InputSections in the OutputSection have the same dependency.
587 if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
588 link = ex->getLinkOrderDep()->getParent()->sectionIndex;
589 else if (first->flags & SHF_LINK_ORDER)
590 if (auto *d = first->getLinkOrderDep())
591 link = d->getParent()->sectionIndex;
592 }
593
594 if (type == SHT_GROUP) {
595 finalizeShtGroup(this, first);
596 return;
597 }
598
599 if (!config->copyRelocs || (type != SHT_RELA && type != SHT_REL))
600 return;
601
602 // Skip if 'first' is synthetic, i.e. not a section created by --emit-relocs.
603 // Normally 'type' was changed by 'first' so 'first' should be non-null.
604 // However, if the output section is .rela.dyn, 'type' can be set by the empty
605 // synthetic .rela.plt and first can be null.
606 if (!first || isa<SyntheticSection>(first))
607 return;
608
609 link = in.symTab->getParent()->sectionIndex;
610 // sh_info for SHT_REL[A] sections should contain the section header index of
611 // the section to which the relocation applies.
612 InputSectionBase *s = first->getRelocatedSection();
613 info = s->getOutputSection()->sectionIndex;
614 flags |= SHF_INFO_LINK;
615 }
616
617 // Returns true if S is in one of the many forms the compiler driver may pass
618 // crtbegin files.
619 //
620 // Gcc uses any of crtbegin[<empty>|S|T].o.
621 // Clang uses Gcc's plus clang_rt.crtbegin[-<arch>|<empty>].o.
622
isCrt(StringRef s,StringRef beginEnd)623 static bool isCrt(StringRef s, StringRef beginEnd) {
624 s = sys::path::filename(s);
625 if (!s.consume_back(".o"))
626 return false;
627 if (s.consume_front("clang_rt."))
628 return s.consume_front(beginEnd);
629 return s.consume_front(beginEnd) && s.size() <= 1;
630 }
631
632 // .ctors and .dtors are sorted by this order:
633 //
634 // 1. .ctors/.dtors in crtbegin (which contains a sentinel value -1).
635 // 2. The section is named ".ctors" or ".dtors" (priority: 65536).
636 // 3. The section has an optional priority value in the form of ".ctors.N" or
637 // ".dtors.N" where N is a number in the form of %05u (priority: 65535-N).
638 // 4. .ctors/.dtors in crtend (which contains a sentinel value 0).
639 //
640 // For 2 and 3, the sections are sorted by priority from high to low, e.g.
641 // .ctors (65536), .ctors.00100 (65436), .ctors.00200 (65336). In GNU ld's
642 // internal linker scripts, the sorting is by string comparison which can
643 // achieve the same goal given the optional priority values are of the same
644 // length.
645 //
646 // In an ideal world, we don't need this function because .init_array and
647 // .ctors are duplicate features (and .init_array is newer.) However, there
648 // are too many real-world use cases of .ctors, so we had no choice to
649 // support that with this rather ad-hoc semantics.
compCtors(const InputSection * a,const InputSection * b)650 static bool compCtors(const InputSection *a, const InputSection *b) {
651 bool beginA = isCrt(a->file->getName(), "crtbegin");
652 bool beginB = isCrt(b->file->getName(), "crtbegin");
653 if (beginA != beginB)
654 return beginA;
655 bool endA = isCrt(a->file->getName(), "crtend");
656 bool endB = isCrt(b->file->getName(), "crtend");
657 if (endA != endB)
658 return endB;
659 return getPriority(a->name) > getPriority(b->name);
660 }
661
662 // Sorts input sections by the special rules for .ctors and .dtors.
663 // Unfortunately, the rules are different from the one for .{init,fini}_array.
664 // Read the comment above.
sortCtorsDtors()665 void OutputSection::sortCtorsDtors() {
666 assert(commands.size() == 1);
667 auto *isd = cast<InputSectionDescription>(commands[0]);
668 llvm::stable_sort(isd->sections, compCtors);
669 }
670
671 // If an input string is in the form of "foo.N" where N is a number, return N
672 // (65535-N if .ctors.N or .dtors.N). Otherwise, returns 65536, which is one
673 // greater than the lowest priority.
getPriority(StringRef s)674 int elf::getPriority(StringRef s) {
675 size_t pos = s.rfind('.');
676 if (pos == StringRef::npos)
677 return 65536;
678 int v = 65536;
679 if (to_integer(s.substr(pos + 1), v, 10) &&
680 (pos == 6 && (s.starts_with(".ctors") || s.starts_with(".dtors"))))
681 v = 65535 - v;
682 return v;
683 }
684
getFirstInputSection(const OutputSection * os)685 InputSection *elf::getFirstInputSection(const OutputSection *os) {
686 for (SectionCommand *cmd : os->commands)
687 if (auto *isd = dyn_cast<InputSectionDescription>(cmd))
688 if (!isd->sections.empty())
689 return isd->sections[0];
690 return nullptr;
691 }
692
693 ArrayRef<InputSection *>
getInputSections(const OutputSection & os,SmallVector<InputSection *,0> & storage)694 elf::getInputSections(const OutputSection &os,
695 SmallVector<InputSection *, 0> &storage) {
696 ArrayRef<InputSection *> ret;
697 storage.clear();
698 for (SectionCommand *cmd : os.commands) {
699 auto *isd = dyn_cast<InputSectionDescription>(cmd);
700 if (!isd)
701 continue;
702 if (ret.empty()) {
703 ret = isd->sections;
704 } else {
705 if (storage.empty())
706 storage.assign(ret.begin(), ret.end());
707 storage.insert(storage.end(), isd->sections.begin(), isd->sections.end());
708 }
709 }
710 return storage.empty() ? ret : ArrayRef(storage);
711 }
712
713 // Sorts input sections by section name suffixes, so that .foo.N comes
714 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
715 // We want to keep the original order if the priorities are the same
716 // because the compiler keeps the original initialization order in a
717 // translation unit and we need to respect that.
718 // For more detail, read the section of the GCC's manual about init_priority.
sortInitFini()719 void OutputSection::sortInitFini() {
720 // Sort sections by priority.
721 sort([](InputSectionBase *s) { return getPriority(s->name); });
722 }
723
getFiller()724 std::array<uint8_t, 4> OutputSection::getFiller() {
725 if (filler)
726 return *filler;
727 if (flags & SHF_EXECINSTR)
728 return target->trapInstr;
729 return {0, 0, 0, 0};
730 }
731
checkDynRelAddends(const uint8_t * bufStart)732 void OutputSection::checkDynRelAddends(const uint8_t *bufStart) {
733 assert(config->writeAddends && config->checkDynamicRelocs);
734 assert(type == SHT_REL || type == SHT_RELA);
735 SmallVector<InputSection *, 0> storage;
736 ArrayRef<InputSection *> sections = getInputSections(*this, storage);
737 parallelFor(0, sections.size(), [&](size_t i) {
738 // When linking with -r or --emit-relocs we might also call this function
739 // for input .rel[a].<sec> sections which we simply pass through to the
740 // output. We skip over those and only look at the synthetic relocation
741 // sections created during linking.
742 const auto *sec = dyn_cast<RelocationBaseSection>(sections[i]);
743 if (!sec)
744 return;
745 for (const DynamicReloc &rel : sec->relocs) {
746 int64_t addend = rel.addend;
747 const OutputSection *relOsec = rel.inputSec->getOutputSection();
748 assert(relOsec != nullptr && "missing output section for relocation");
749 // Some targets have NOBITS synthetic sections with dynamic relocations
750 // with non-zero addends. Skip such sections.
751 if (is_contained({EM_PPC, EM_PPC64}, config->emachine) &&
752 (rel.inputSec == in.ppc64LongBranchTarget.get() ||
753 rel.inputSec == in.igotPlt.get()))
754 continue;
755 const uint8_t *relocTarget =
756 bufStart + relOsec->offset + rel.inputSec->getOffset(rel.offsetInSec);
757 // For SHT_NOBITS the written addend is always zero.
758 int64_t writtenAddend =
759 relOsec->type == SHT_NOBITS
760 ? 0
761 : target->getImplicitAddend(relocTarget, rel.type);
762 if (addend != writtenAddend)
763 internalLinkerError(
764 getErrorLocation(relocTarget),
765 "wrote incorrect addend value 0x" + utohexstr(writtenAddend) +
766 " instead of 0x" + utohexstr(addend) +
767 " for dynamic relocation " + toString(rel.type) +
768 " at offset 0x" + utohexstr(rel.getOffset()) +
769 (rel.sym ? " against symbol " + toString(*rel.sym) : ""));
770 }
771 });
772 }
773
774 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
775 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
776 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
777 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
778
779 template void OutputSection::writeTo<ELF32LE>(uint8_t *,
780 llvm::parallel::TaskGroup &);
781 template void OutputSection::writeTo<ELF32BE>(uint8_t *,
782 llvm::parallel::TaskGroup &);
783 template void OutputSection::writeTo<ELF64LE>(uint8_t *,
784 llvm::parallel::TaskGroup &);
785 template void OutputSection::writeTo<ELF64BE>(uint8_t *,
786 llvm::parallel::TaskGroup &);
787
788 template void OutputSection::maybeCompress<ELF32LE>();
789 template void OutputSection::maybeCompress<ELF32BE>();
790 template void OutputSection::maybeCompress<ELF64LE>();
791 template void OutputSection::maybeCompress<ELF64BE>();
792