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
33using namespace llvm;
34using namespace llvm::dwarf;
35using namespace llvm::object;
36using namespace llvm::support::endian;
37using namespace llvm::ELF;
38using namespace lld;
39using namespace lld::elf;
40
41uint8_t *Out::bufferStart;
42PhdrEntry *Out::tlsPhdr;
43OutputSection *Out::elfHeader;
44OutputSection *Out::programHeaders;
45OutputSection *Out::preinitArray;
46OutputSection *Out::initArray;
47OutputSection *Out::finiArray;
48
49SmallVector<OutputSection *, 0> elf::outputSections;
50
51uint32_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
62template <class ELFT>
63void 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
76OutputSection::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_*).
89static 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).
104void OutputSection::recordSection(InputSectionBase *isec) {
105 partition = isec->partition;
106 isec->parent = this;
107 if (commands.empty() || !isa<InputSectionDescription>(Val: commands.back()))
108 commands.push_back(Elt: make<InputSectionDescription>(args: ""));
109 auto *isd = cast<InputSectionDescription>(Val: commands.back());
110 isd->sectionBases.push_back(Elt: 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.
116void OutputSection::commitSection(InputSection *isec) {
117 if (LLVM_UNLIKELY(type != isec->type)) {
118 if (hasInputSections || typeIsSet) {
119 if (typeIsSet || !canMergeToProgbits(type) ||
120 !canMergeToProgbits(type: 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(msg: "section type mismatch for " + isec->name + "\n>>> " +
128 toString(isec) + ": " +
129 getELFSectionTypeName(Machine: config->emachine, Type: isec->type) +
130 "\n>>> output section " + name + ": " +
131 getELFSectionTypeName(Machine: config->emachine, Type: 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(msg: "incompatible section flags for " + name + "\n>>> " +
150 toString(isec) + ": 0x" + utohexstr(X: isec->flags) +
151 "\n>>> output section " + name + ": 0x" + utohexstr(X: 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(a: addralign, b: 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
173static 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>(args&: name, args&: type, args&: flags, args&: addralign);
179 return make<MergeNoTailSection>(args&: name, args&: type, args&: flags, args&: 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.
189void OutputSection::finalizeInputSections() {
190 std::vector<MergeSyntheticSection *> mergeSections;
191 for (SectionCommand *cmd : commands) {
192 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
193 if (!isd)
194 continue;
195 isd->sections.reserve(N: isd->sectionBases.size());
196 for (InputSectionBase *s : isd->sectionBases) {
197 MergeInputSection *ms = dyn_cast<MergeInputSection>(Val: s);
198 if (!ms) {
199 isd->sections.push_back(Elt: cast<InputSection>(Val: 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(Range&: mergeSections, P: [=](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(name: s->name, type: ms->type, flags: ms->flags, addralign: ms->addralign);
225 mergeSections.push_back(x: syn);
226 i = std::prev(x: mergeSections.end());
227 syn->entsize = ms->entsize;
228 isd->sections.push_back(Elt: 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(isec: s);
240 }
241 for (auto *ms : mergeSections)
242 ms->finalizeContents();
243}
244
245static 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(args: order(s), args&: s);
250 llvm::stable_sort(Range&: v, C: less_first());
251
252 for (size_t i = 0; i < v.size(); ++i)
253 in[i] = v[i].second;
254}
255
256uint64_t elf::getHeaderSize() {
257 if (config->oFormatBinary)
258 return 0;
259 return Out::elfHeader->size + Out::programHeaders->size;
260}
261
262void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
263 assert(isLive());
264 for (SectionCommand *b : commands)
265 if (auto *isd = dyn_cast<InputSectionDescription>(Val: b))
266 sortByOrder(in: isd->sections, order);
267}
268
269static 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(dest: buf + i, src: nopFiller.back().data(), n: 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(dest: buf + i, src: nopFiller[remaining - 1].data(), n: remaining);
286}
287
288// Fill [Buf, Buf + Size) with Filler.
289// This is used for linker script "=fillexp" command.
290static 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(dest: buf + i, src: filler.data(), n: 4);
295 memcpy(dest: buf + i, src: filler.data(), n: size - i);
296}
297
298#if LLVM_ENABLE_ZLIB
299static 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(N: std::max<size_t>(a: in.size() / 2, b: 64));
313 do {
314 if (pos == out.size())
315 out.resize_for_overwrite(N: out.size() * 3 / 2);
316 s.next_out = out.data() + pos;
317 s.avail_out = out.size() - pos;
318 (void)deflate(strm: &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(N: pos);
324 deflateEnd(strm: &s);
325 return out;
326}
327#endif
328
329// Compress certain non-SHF_ALLOC sections:
330//
331// * (if --compress-debug-sections is specified) non-empty .debug_* sections
332// * (if --compress-sections is specified) matched sections
333template <class ELFT> void OutputSection::maybeCompress() {
334 using Elf_Chdr = typename ELFT::Chdr;
335 (void)sizeof(Elf_Chdr);
336
337 DebugCompressionType ctype = DebugCompressionType::None;
338 for (auto &[glob, t] : config->compressSections)
339 if (glob.match(S: name))
340 ctype = t;
341 if (!(flags & SHF_ALLOC) && config->compressDebugSections &&
342 name.starts_with(Prefix: ".debug_") && size)
343 ctype = *config->compressDebugSections;
344 if (ctype == DebugCompressionType::None)
345 return;
346 if (flags & SHF_ALLOC) {
347 errorOrWarn(msg: "--compress-sections: section '" + name +
348 "' with the SHF_ALLOC flag cannot be compressed");
349 return;
350 }
351
352 llvm::TimeTraceScope timeScope("Compress sections");
353 compressed.uncompressedSize = size;
354 auto buf = std::make_unique<uint8_t[]>(num: size);
355 // Write uncompressed data to a temporary zero-initialized buffer.
356 {
357 parallel::TaskGroup tg;
358 writeTo<ELFT>(buf.get(), tg);
359 }
360 // The generic ABI specifies "The sh_size and sh_addralign fields of the
361 // section header for a compressed section reflect the requirements of the
362 // compressed section." However, 1-byte alignment has been wildly accepted
363 // and utilized for a long time. Removing alignment padding is particularly
364 // useful when there are many compressed output sections.
365 addralign = 1;
366
367#if LLVM_ENABLE_ZSTD
368 // Use ZSTD's streaming compression API which permits parallel workers working
369 // on the stream. See http://facebook.github.io/zstd/zstd_manual.html
370 // "Streaming compression - HowTo".
371 if (ctype == DebugCompressionType::Zstd) {
372 // Allocate a buffer of half of the input size, and grow it by 1.5x if
373 // insufficient.
374 compressed.type = ELFCOMPRESS_ZSTD;
375 compressed.shards = std::make_unique<SmallVector<uint8_t, 0>[]>(num: 1);
376 SmallVector<uint8_t, 0> &out = compressed.shards[0];
377 out.resize_for_overwrite(N: std::max<size_t>(a: size / 2, b: 32));
378 size_t pos = 0;
379
380 ZSTD_CCtx *cctx = ZSTD_createCCtx();
381 // Ignore error if zstd was not built with ZSTD_MULTITHREAD.
382 (void)ZSTD_CCtx_setParameter(cctx, param: ZSTD_c_nbWorkers,
383 value: parallel::strategy.compute_thread_count());
384 ZSTD_outBuffer zob = {.dst: out.data(), .size: out.size(), .pos: 0};
385 ZSTD_EndDirective directive = ZSTD_e_continue;
386 const size_t blockSize = ZSTD_CStreamInSize();
387 do {
388 const size_t n = std::min(a: static_cast<size_t>(size - pos), b: blockSize);
389 if (n == size - pos)
390 directive = ZSTD_e_end;
391 ZSTD_inBuffer zib = {.src: buf.get() + pos, .size: n, .pos: 0};
392 size_t bytesRemaining = 0;
393 while (zib.pos != zib.size ||
394 (directive == ZSTD_e_end && bytesRemaining != 0)) {
395 if (zob.pos == zob.size) {
396 out.resize_for_overwrite(N: out.size() * 3 / 2);
397 zob.dst = out.data();
398 zob.size = out.size();
399 }
400 bytesRemaining = ZSTD_compressStream2(cctx, output: &zob, input: &zib, endOp: directive);
401 assert(!ZSTD_isError(bytesRemaining));
402 }
403 pos += n;
404 } while (directive != ZSTD_e_end);
405 out.resize(N: zob.pos);
406 ZSTD_freeCCtx(cctx);
407
408 size = sizeof(Elf_Chdr) + out.size();
409 flags |= SHF_COMPRESSED;
410 return;
411 }
412#endif
413
414#if LLVM_ENABLE_ZLIB
415 // We chose 1 (Z_BEST_SPEED) as the default compression level because it is
416 // the fastest. If -O2 is given, we use level 6 to compress debug info more by
417 // ~15%. We found that level 7 to 9 doesn't make much difference (~1% more
418 // compression) while they take significant amount of time (~2x), so level 6
419 // seems enough.
420 const int level = config->optimize >= 2 ? 6 : Z_BEST_SPEED;
421
422 // Split input into 1-MiB shards.
423 constexpr size_t shardSize = 1 << 20;
424 auto shardsIn = split(arr: ArrayRef<uint8_t>(buf.get(), size), chunkSize: shardSize);
425 const size_t numShards = shardsIn.size();
426
427 // Compress shards and compute Alder-32 checksums. Use Z_SYNC_FLUSH for all
428 // shards but the last to flush the output to a byte boundary to be
429 // concatenated with the next shard.
430 auto shardsOut = std::make_unique<SmallVector<uint8_t, 0>[]>(num: numShards);
431 auto shardsAdler = std::make_unique<uint32_t[]>(num: numShards);
432 parallelFor(0, numShards, [&](size_t i) {
433 shardsOut[i] = deflateShard(in: shardsIn[i], level,
434 flush: i != numShards - 1 ? Z_SYNC_FLUSH : Z_FINISH);
435 shardsAdler[i] = adler32(adler: 1, buf: shardsIn[i].data(), len: shardsIn[i].size());
436 });
437
438 // Update section size and combine Alder-32 checksums.
439 uint32_t checksum = 1; // Initial Adler-32 value
440 size = sizeof(Elf_Chdr) + 2; // Elf_Chdir and zlib header
441 for (size_t i = 0; i != numShards; ++i) {
442 size += shardsOut[i].size();
443 checksum = adler32_combine(checksum, shardsAdler[i], shardsIn[i].size());
444 }
445 size += 4; // checksum
446
447 compressed.type = ELFCOMPRESS_ZLIB;
448 compressed.shards = std::move(shardsOut);
449 compressed.numShards = numShards;
450 compressed.checksum = checksum;
451 flags |= SHF_COMPRESSED;
452#endif
453}
454
455static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
456 if (size == 1)
457 *buf = data;
458 else if (size == 2)
459 write16(p: buf, v: data);
460 else if (size == 4)
461 write32(p: buf, v: data);
462 else if (size == 8)
463 write64(p: buf, v: data);
464 else
465 llvm_unreachable("unsupported Size argument");
466}
467
468template <class ELFT>
469void OutputSection::writeTo(uint8_t *buf, parallel::TaskGroup &tg) {
470 llvm::TimeTraceScope timeScope("Write sections", name);
471 if (type == SHT_NOBITS)
472 return;
473
474 // If the section is compressed due to
475 // --compress-debug-section/--compress-sections, the content is already known.
476 if (compressed.shards) {
477 auto *chdr = reinterpret_cast<typename ELFT::Chdr *>(buf);
478 chdr->ch_type = compressed.type;
479 chdr->ch_size = compressed.uncompressedSize;
480 chdr->ch_addralign = addralign;
481 buf += sizeof(*chdr);
482 if (compressed.type == ELFCOMPRESS_ZSTD) {
483 memcpy(dest: buf, src: compressed.shards[0].data(), n: compressed.shards[0].size());
484 return;
485 }
486
487 // Compute shard offsets.
488 auto offsets = std::make_unique<size_t[]>(num: compressed.numShards);
489 offsets[0] = 2; // zlib header
490 for (size_t i = 1; i != compressed.numShards; ++i)
491 offsets[i] = offsets[i - 1] + compressed.shards[i - 1].size();
492
493 buf[0] = 0x78; // CMF
494 buf[1] = 0x01; // FLG: best speed
495 parallelFor(0, compressed.numShards, [&](size_t i) {
496 memcpy(dest: buf + offsets[i], src: compressed.shards[i].data(),
497 n: compressed.shards[i].size());
498 });
499
500 write32be(P: buf + (size - sizeof(*chdr) - 4), V: compressed.checksum);
501 return;
502 }
503
504 // Write leading padding.
505 ArrayRef<InputSection *> sections = getInputSections(os: *this, storage);
506 std::array<uint8_t, 4> filler = getFiller();
507 bool nonZeroFiller = read32(p: filler.data()) != 0;
508 if (nonZeroFiller)
509 fill(buf, size: sections.empty() ? size : sections[0]->outSecOff, filler);
510
511 auto fn = [=](size_t begin, size_t end) {
512 size_t numSections = sections.size();
513 for (size_t i = begin; i != end; ++i) {
514 InputSection *isec = sections[i];
515 if (auto *s = dyn_cast<SyntheticSection>(Val: isec))
516 s->writeTo(buf: buf + isec->outSecOff);
517 else
518 isec->writeTo<ELFT>(buf + isec->outSecOff);
519
520 // When in Arm BE8 mode, the linker has to convert the big-endian
521 // instructions to little-endian, leaving the data big-endian.
522 if (config->emachine == EM_ARM && !config->isLE && config->armBe8 &&
523 (flags & SHF_EXECINSTR))
524 convertArmInstructionstoBE8(sec: isec, buf: buf + isec->outSecOff);
525
526 // Fill gaps between sections.
527 if (nonZeroFiller) {
528 uint8_t *start = buf + isec->outSecOff + isec->getSize();
529 uint8_t *end;
530 if (i + 1 == numSections)
531 end = buf + size;
532 else
533 end = buf + sections[i + 1]->outSecOff;
534 if (isec->nopFiller) {
535 assert(target->nopInstrs);
536 nopInstrFill(buf: start, size: end - start);
537 } else
538 fill(buf: start, size: end - start, filler);
539 }
540 }
541 };
542
543 // If there is any BYTE()-family command (rare), write the section content
544 // first then process BYTE to overwrite the filler content. The write is
545 // serial due to the limitation of llvm/Support/Parallel.h.
546 bool written = false;
547 size_t numSections = sections.size();
548 for (SectionCommand *cmd : commands)
549 if (auto *data = dyn_cast<ByteCommand>(Val: cmd)) {
550 if (!std::exchange(obj&: written, new_val: true))
551 fn(0, numSections);
552 writeInt(buf: buf + data->offset, data: data->expression().getValue(), size: data->size);
553 }
554 if (written || !numSections)
555 return;
556
557 // There is no data command. Write content asynchronously to overlap the write
558 // time with other output sections. Note, if a linker script specifies
559 // overlapping output sections (needs --noinhibit-exec or --no-check-sections
560 // to supress the error), the output may be non-deterministic.
561 const size_t taskSizeLimit = 4 << 20;
562 for (size_t begin = 0, i = 0, taskSize = 0;;) {
563 taskSize += sections[i]->getSize();
564 bool done = ++i == numSections;
565 if (done || taskSize >= taskSizeLimit) {
566 tg.spawn(f: [=] { fn(begin, i); });
567 if (done)
568 break;
569 begin = i;
570 taskSize = 0;
571 }
572 }
573}
574
575static void finalizeShtGroup(OutputSection *os, InputSection *section) {
576 // sh_link field for SHT_GROUP sections should contain the section index of
577 // the symbol table.
578 os->link = in.symTab->getParent()->sectionIndex;
579
580 if (!section)
581 return;
582
583 // sh_info then contain index of an entry in symbol table section which
584 // provides signature of the section group.
585 ArrayRef<Symbol *> symbols = section->file->getSymbols();
586 os->info = in.symTab->getSymbolIndex(sym: *symbols[section->info]);
587
588 // Some group members may be combined or discarded, so we need to compute the
589 // new size. The content will be rewritten in InputSection::copyShtGroup.
590 DenseSet<uint32_t> seen;
591 ArrayRef<InputSectionBase *> sections = section->file->getSections();
592 for (const uint32_t &idx : section->getDataAs<uint32_t>().slice(N: 1))
593 if (OutputSection *osec = sections[read32(p: &idx)]->getOutputSection())
594 seen.insert(V: osec->sectionIndex);
595 os->size = (1 + seen.size()) * sizeof(uint32_t);
596}
597
598void OutputSection::finalize() {
599 InputSection *first = getFirstInputSection(os: this);
600
601 if (flags & SHF_LINK_ORDER) {
602 // We must preserve the link order dependency of sections with the
603 // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
604 // need to translate the InputSection sh_link to the OutputSection sh_link,
605 // all InputSections in the OutputSection have the same dependency.
606 if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(Val: first))
607 link = ex->getLinkOrderDep()->getParent()->sectionIndex;
608 else if (first->flags & SHF_LINK_ORDER)
609 if (auto *d = first->getLinkOrderDep())
610 link = d->getParent()->sectionIndex;
611 }
612
613 if (type == SHT_GROUP) {
614 finalizeShtGroup(os: this, section: first);
615 return;
616 }
617
618 if (!config->copyRelocs || !isStaticRelSecType(type))
619 return;
620
621 // Skip if 'first' is synthetic, i.e. not a section created by --emit-relocs.
622 // Normally 'type' was changed by 'first' so 'first' should be non-null.
623 // However, if the output section is .rela.dyn, 'type' can be set by the empty
624 // synthetic .rela.plt and first can be null.
625 if (!first || isa<SyntheticSection>(Val: first))
626 return;
627
628 link = in.symTab->getParent()->sectionIndex;
629 // sh_info for SHT_REL[A] sections should contain the section header index of
630 // the section to which the relocation applies.
631 InputSectionBase *s = first->getRelocatedSection();
632 info = s->getOutputSection()->sectionIndex;
633 flags |= SHF_INFO_LINK;
634}
635
636// Returns true if S is in one of the many forms the compiler driver may pass
637// crtbegin files.
638//
639// Gcc uses any of crtbegin[<empty>|S|T].o.
640// Clang uses Gcc's plus clang_rt.crtbegin[-<arch>|<empty>].o.
641
642static bool isCrt(StringRef s, StringRef beginEnd) {
643 s = sys::path::filename(path: s);
644 if (!s.consume_back(Suffix: ".o"))
645 return false;
646 if (s.consume_front(Prefix: "clang_rt."))
647 return s.consume_front(Prefix: beginEnd);
648 return s.consume_front(Prefix: beginEnd) && s.size() <= 1;
649}
650
651// .ctors and .dtors are sorted by this order:
652//
653// 1. .ctors/.dtors in crtbegin (which contains a sentinel value -1).
654// 2. The section is named ".ctors" or ".dtors" (priority: 65536).
655// 3. The section has an optional priority value in the form of ".ctors.N" or
656// ".dtors.N" where N is a number in the form of %05u (priority: 65535-N).
657// 4. .ctors/.dtors in crtend (which contains a sentinel value 0).
658//
659// For 2 and 3, the sections are sorted by priority from high to low, e.g.
660// .ctors (65536), .ctors.00100 (65436), .ctors.00200 (65336). In GNU ld's
661// internal linker scripts, the sorting is by string comparison which can
662// achieve the same goal given the optional priority values are of the same
663// length.
664//
665// In an ideal world, we don't need this function because .init_array and
666// .ctors are duplicate features (and .init_array is newer.) However, there
667// are too many real-world use cases of .ctors, so we had no choice to
668// support that with this rather ad-hoc semantics.
669static bool compCtors(const InputSection *a, const InputSection *b) {
670 bool beginA = isCrt(s: a->file->getName(), beginEnd: "crtbegin");
671 bool beginB = isCrt(s: b->file->getName(), beginEnd: "crtbegin");
672 if (beginA != beginB)
673 return beginA;
674 bool endA = isCrt(s: a->file->getName(), beginEnd: "crtend");
675 bool endB = isCrt(s: b->file->getName(), beginEnd: "crtend");
676 if (endA != endB)
677 return endB;
678 return getPriority(s: a->name) > getPriority(s: b->name);
679}
680
681// Sorts input sections by the special rules for .ctors and .dtors.
682// Unfortunately, the rules are different from the one for .{init,fini}_array.
683// Read the comment above.
684void OutputSection::sortCtorsDtors() {
685 assert(commands.size() == 1);
686 auto *isd = cast<InputSectionDescription>(Val: commands[0]);
687 llvm::stable_sort(Range&: isd->sections, C: compCtors);
688}
689
690// If an input string is in the form of "foo.N" where N is a number, return N
691// (65535-N if .ctors.N or .dtors.N). Otherwise, returns 65536, which is one
692// greater than the lowest priority.
693int elf::getPriority(StringRef s) {
694 size_t pos = s.rfind(C: '.');
695 if (pos == StringRef::npos)
696 return 65536;
697 int v = 65536;
698 if (to_integer(S: s.substr(Start: pos + 1), Num&: v, Base: 10) &&
699 (pos == 6 && (s.starts_with(Prefix: ".ctors") || s.starts_with(Prefix: ".dtors"))))
700 v = 65535 - v;
701 return v;
702}
703
704InputSection *elf::getFirstInputSection(const OutputSection *os) {
705 for (SectionCommand *cmd : os->commands)
706 if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
707 if (!isd->sections.empty())
708 return isd->sections[0];
709 return nullptr;
710}
711
712ArrayRef<InputSection *>
713elf::getInputSections(const OutputSection &os,
714 SmallVector<InputSection *, 0> &storage) {
715 ArrayRef<InputSection *> ret;
716 storage.clear();
717 for (SectionCommand *cmd : os.commands) {
718 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
719 if (!isd)
720 continue;
721 if (ret.empty()) {
722 ret = isd->sections;
723 } else {
724 if (storage.empty())
725 storage.assign(in_start: ret.begin(), in_end: ret.end());
726 storage.insert(I: storage.end(), From: isd->sections.begin(), To: isd->sections.end());
727 }
728 }
729 return storage.empty() ? ret : ArrayRef(storage);
730}
731
732// Sorts input sections by section name suffixes, so that .foo.N comes
733// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
734// We want to keep the original order if the priorities are the same
735// because the compiler keeps the original initialization order in a
736// translation unit and we need to respect that.
737// For more detail, read the section of the GCC's manual about init_priority.
738void OutputSection::sortInitFini() {
739 // Sort sections by priority.
740 sort(order: [](InputSectionBase *s) { return getPriority(s: s->name); });
741}
742
743std::array<uint8_t, 4> OutputSection::getFiller() {
744 if (filler)
745 return *filler;
746 if (flags & SHF_EXECINSTR)
747 return target->trapInstr;
748 return {0, 0, 0, 0};
749}
750
751void OutputSection::checkDynRelAddends(const uint8_t *bufStart) {
752 assert(config->writeAddends && config->checkDynamicRelocs);
753 assert(isStaticRelSecType(type));
754 SmallVector<InputSection *, 0> storage;
755 ArrayRef<InputSection *> sections = getInputSections(os: *this, storage);
756 parallelFor(Begin: 0, End: sections.size(), Fn: [&](size_t i) {
757 // When linking with -r or --emit-relocs we might also call this function
758 // for input .rel[a].<sec> sections which we simply pass through to the
759 // output. We skip over those and only look at the synthetic relocation
760 // sections created during linking.
761 const auto *sec = dyn_cast<RelocationBaseSection>(Val: sections[i]);
762 if (!sec)
763 return;
764 for (const DynamicReloc &rel : sec->relocs) {
765 int64_t addend = rel.addend;
766 const OutputSection *relOsec = rel.inputSec->getOutputSection();
767 assert(relOsec != nullptr && "missing output section for relocation");
768 // Some targets have NOBITS synthetic sections with dynamic relocations
769 // with non-zero addends. Skip such sections.
770 if (is_contained(Set: {EM_PPC, EM_PPC64}, Element: config->emachine) &&
771 (rel.inputSec == in.ppc64LongBranchTarget.get() ||
772 rel.inputSec == in.igotPlt.get()))
773 continue;
774 const uint8_t *relocTarget =
775 bufStart + relOsec->offset + rel.inputSec->getOffset(offset: rel.offsetInSec);
776 // For SHT_NOBITS the written addend is always zero.
777 int64_t writtenAddend =
778 relOsec->type == SHT_NOBITS
779 ? 0
780 : target->getImplicitAddend(buf: relocTarget, type: rel.type);
781 if (addend != writtenAddend)
782 internalLinkerError(
783 loc: getErrorLocation(loc: relocTarget),
784 msg: "wrote incorrect addend value 0x" + utohexstr(X: writtenAddend) +
785 " instead of 0x" + utohexstr(X: addend) +
786 " for dynamic relocation " + toString(type: rel.type) +
787 " at offset 0x" + utohexstr(X: rel.getOffset()) +
788 (rel.sym ? " against symbol " + toString(*rel.sym) : ""));
789 }
790 });
791}
792
793template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
794template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
795template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
796template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
797
798template void OutputSection::writeTo<ELF32LE>(uint8_t *,
799 llvm::parallel::TaskGroup &);
800template void OutputSection::writeTo<ELF32BE>(uint8_t *,
801 llvm::parallel::TaskGroup &);
802template void OutputSection::writeTo<ELF64LE>(uint8_t *,
803 llvm::parallel::TaskGroup &);
804template void OutputSection::writeTo<ELF64BE>(uint8_t *,
805 llvm::parallel::TaskGroup &);
806
807template void OutputSection::maybeCompress<ELF32LE>();
808template void OutputSection::maybeCompress<ELF32BE>();
809template void OutputSection::maybeCompress<ELF64LE>();
810template void OutputSection::maybeCompress<ELF64BE>();
811

source code of lld/ELF/OutputSections.cpp