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, LLVM_ENABLE_ZSTD
20#include "llvm/Support/Compression.h"
21#include "llvm/Support/LEB128.h"
22#include "llvm/Support/Parallel.h"
23#include "llvm/Support/Path.h"
24#include "llvm/Support/TimeProfiler.h"
25#undef in
26#if LLVM_ENABLE_ZLIB
27// Avoid introducing max as a macro from Windows headers.
28#define NOMINMAX
29#include <zlib.h>
30#endif
31#if LLVM_ENABLE_ZSTD
32#include <zstd.h>
33#endif
34
35using namespace llvm;
36using namespace llvm::dwarf;
37using namespace llvm::object;
38using namespace llvm::support::endian;
39using namespace llvm::ELF;
40using namespace lld;
41using namespace lld::elf;
42
43uint32_t OutputSection::getPhdrFlags() const {
44 uint32_t ret = 0;
45 bool purecode =
46 (ctx.arg.emachine == EM_ARM && (flags & SHF_ARM_PURECODE)) ||
47 (ctx.arg.emachine == EM_AARCH64 && (flags & SHF_AARCH64_PURECODE));
48 if (!purecode)
49 ret |= PF_R;
50 if (flags & SHF_WRITE)
51 ret |= PF_W;
52 if (flags & SHF_EXECINSTR)
53 ret |= PF_X;
54 return ret;
55}
56
57template <class ELFT>
58void OutputSection::writeHeaderTo(typename ELFT::Shdr *shdr) {
59 shdr->sh_entsize = entsize;
60 shdr->sh_addralign = addralign;
61 shdr->sh_type = type;
62 shdr->sh_offset = offset;
63 shdr->sh_flags = flags;
64 shdr->sh_info = info;
65 shdr->sh_link = link;
66 shdr->sh_addr = addr;
67 shdr->sh_size = size;
68 shdr->sh_name = shName;
69}
70
71OutputSection::OutputSection(Ctx &ctx, StringRef name, uint32_t type,
72 uint64_t flags)
73 : SectionBase(Output, ctx.internalFile, name, type, flags, /*link=*/0,
74 /*info=*/0, /*addralign=*/1, /*entsize=*/0),
75 ctx(ctx) {}
76
77uint64_t OutputSection::getLMA() const {
78 return ptLoad ? addr + ptLoad->lmaOffset : addr;
79}
80
81// We allow sections of types listed below to merged into a
82// single progbits section. This is typically done by linker
83// scripts. Merging nobits and progbits will force disk space
84// to be allocated for nobits sections. Other ones don't require
85// any special treatment on top of progbits, so there doesn't
86// seem to be a harm in merging them.
87//
88// NOTE: clang since rL252300 emits SHT_X86_64_UNWIND .eh_frame sections. Allow
89// them to be merged into SHT_PROGBITS .eh_frame (GNU as .cfi_*).
90static bool canMergeToProgbits(Ctx &ctx, unsigned type) {
91 return type == SHT_NOBITS || type == SHT_PROGBITS || type == SHT_INIT_ARRAY ||
92 type == SHT_PREINIT_ARRAY || type == SHT_FINI_ARRAY ||
93 type == SHT_NOTE ||
94 (type == SHT_X86_64_UNWIND && ctx.arg.emachine == EM_X86_64) ||
95 type == SHT_LLVM_CFI_JUMP_TABLE;
96}
97
98// Record that isec will be placed in the OutputSection. isec does not become
99// permanent until finalizeInputSections() is called. The function should not be
100// used after finalizeInputSections() is called. If you need to add an
101// InputSection post finalizeInputSections(), then you must do the following:
102//
103// 1. Find or create an InputSectionDescription to hold InputSection.
104// 2. Add the InputSection to the InputSectionDescription::sections.
105// 3. Call commitSection(isec).
106void OutputSection::recordSection(InputSectionBase *isec) {
107 partition = isec->partition;
108 isec->parent = this;
109 if (commands.empty() || !isa<InputSectionDescription>(Val: commands.back()))
110 commands.push_back(Elt: make<InputSectionDescription>(args: ""));
111 auto *isd = cast<InputSectionDescription>(Val: commands.back());
112 isd->sectionBases.push_back(Elt: isec);
113}
114
115// Update fields (type, flags, alignment, etc) according to the InputSection
116// isec. Also check whether the InputSection flags and type are consistent with
117// other InputSections.
118void OutputSection::commitSection(InputSection *isec) {
119 if (LLVM_UNLIKELY(type != isec->type)) {
120 if (!hasInputSections && !typeIsSet) {
121 type = isec->type;
122 } else if (isStaticRelSecType(type) && isStaticRelSecType(type: isec->type) &&
123 (type == SHT_CREL) != (isec->type == SHT_CREL)) {
124 // Combine mixed SHT_REL[A] and SHT_CREL to SHT_CREL.
125 type = SHT_CREL;
126 if (type == SHT_REL) {
127 if (name.consume_front(Prefix: ".rel"))
128 name = ctx.saver.save(S: ".crel" + name);
129 } else if (name.consume_front(Prefix: ".rela")) {
130 name = ctx.saver.save(S: ".crel" + name);
131 }
132 } else {
133 if (typeIsSet || !canMergeToProgbits(ctx, type) ||
134 !canMergeToProgbits(ctx, type: isec->type)) {
135 // The (NOLOAD) changes the section type to SHT_NOBITS, the intention is
136 // that the contents at that address is provided by some other means.
137 // Some projects (e.g.
138 // https://github.com/ClangBuiltLinux/linux/issues/1597) rely on the
139 // behavior. Other types get an error.
140 if (type != SHT_NOBITS) {
141 Err(ctx) << "section type mismatch for " << isec->name << "\n>>> "
142 << isec << ": "
143 << getELFSectionTypeName(Machine: ctx.arg.emachine, Type: isec->type)
144 << "\n>>> output section " << name << ": "
145 << getELFSectionTypeName(Machine: ctx.arg.emachine, Type: type);
146 }
147 }
148 if (!typeIsSet)
149 type = SHT_PROGBITS;
150 }
151 }
152 if (!hasInputSections) {
153 // If IS is the first section to be added to this section,
154 // initialize type, entsize and flags from isec.
155 hasInputSections = true;
156 entsize = isec->entsize;
157 flags = isec->flags;
158 } else {
159 // Otherwise, check if new type or flags are compatible with existing ones.
160 if ((flags ^ isec->flags) & SHF_TLS)
161 ErrAlways(ctx) << "incompatible section flags for " << name << "\n>>> "
162 << isec << ": 0x" << utohexstr(X: isec->flags, LowerCase: true)
163 << "\n>>> output section " << name << ": 0x"
164 << utohexstr(X: flags, LowerCase: true);
165 }
166
167 isec->parent = this;
168 uint64_t andMask = 0;
169 if (ctx.arg.emachine == EM_ARM)
170 andMask |= (uint64_t)SHF_ARM_PURECODE;
171 if (ctx.arg.emachine == EM_AARCH64)
172 andMask |= (uint64_t)SHF_AARCH64_PURECODE;
173 uint64_t orMask = ~andMask;
174 uint64_t andFlags = (flags & isec->flags) & andMask;
175 uint64_t orFlags = (flags | isec->flags) & orMask;
176 flags = andFlags | orFlags;
177 if (nonAlloc)
178 flags &= ~(uint64_t)SHF_ALLOC;
179
180 addralign = std::max(a: addralign, b: isec->addralign);
181
182 // If this section contains a table of fixed-size entries, sh_entsize
183 // holds the element size. If it contains elements of different size we
184 // set sh_entsize to 0.
185 if (entsize != isec->entsize)
186 entsize = 0;
187}
188
189static MergeSyntheticSection *createMergeSynthetic(Ctx &ctx, StringRef name,
190 uint32_t type,
191 uint64_t flags,
192 uint32_t addralign) {
193 if ((flags & SHF_STRINGS) && ctx.arg.optimize >= 2)
194 return make<MergeTailSection>(args&: ctx, args&: name, args&: type, args&: flags, args&: addralign);
195 return make<MergeNoTailSection>(args&: ctx, args&: name, args&: type, args&: flags, args&: addralign);
196}
197
198// This function scans over the InputSectionBase list sectionBases to create
199// InputSectionDescription::sections.
200//
201// It removes MergeInputSections from the input section array and adds
202// new synthetic sections at the location of the first input section
203// that it replaces. It then finalizes each synthetic section in order
204// to compute an output offset for each piece of each input section.
205void OutputSection::finalizeInputSections() {
206 auto *script = ctx.script;
207 std::vector<MergeSyntheticSection *> mergeSections;
208 for (SectionCommand *cmd : commands) {
209 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
210 if (!isd)
211 continue;
212 isd->sections.reserve(N: isd->sectionBases.size());
213 for (InputSectionBase *s : isd->sectionBases) {
214 MergeInputSection *ms = dyn_cast<MergeInputSection>(Val: s);
215 if (!ms) {
216 isd->sections.push_back(Elt: cast<InputSection>(Val: s));
217 continue;
218 }
219
220 // We do not want to handle sections that are not alive, so just remove
221 // them instead of trying to merge.
222 if (!ms->isLive())
223 continue;
224
225 auto i = llvm::find_if(Range&: mergeSections, P: [=](MergeSyntheticSection *sec) {
226 // While we could create a single synthetic section for two different
227 // values of Entsize, it is better to take Entsize into consideration.
228 //
229 // With a single synthetic section no two pieces with different Entsize
230 // could be equal, so we may as well have two sections.
231 //
232 // Using Entsize in here also allows us to propagate it to the synthetic
233 // section.
234 //
235 // SHF_STRINGS section with different alignments should not be merged.
236 return sec->flags == ms->flags && sec->entsize == ms->entsize &&
237 (sec->addralign == ms->addralign || !(sec->flags & SHF_STRINGS));
238 });
239 if (i == mergeSections.end()) {
240 MergeSyntheticSection *syn = createMergeSynthetic(
241 ctx, name: s->name, type: ms->type, flags: ms->flags, addralign: ms->addralign);
242 mergeSections.push_back(x: syn);
243 i = std::prev(x: mergeSections.end());
244 syn->entsize = ms->entsize;
245 isd->sections.push_back(Elt: syn);
246 // The merge synthetic section inherits the potential spill locations of
247 // its first contained section.
248 auto it = script->potentialSpillLists.find(Val: ms);
249 if (it != script->potentialSpillLists.end())
250 script->potentialSpillLists.try_emplace(Key: syn, Args&: it->second);
251 }
252 (*i)->addSection(ms);
253 }
254
255 // sectionBases should not be used from this point onwards. Clear it to
256 // catch misuses.
257 isd->sectionBases.clear();
258
259 // Some input sections may be removed from the list after ICF.
260 for (InputSection *s : isd->sections)
261 commitSection(isec: s);
262 }
263 for (auto *ms : mergeSections) {
264 // Merging may have increased the alignment of a spillable section. Update
265 // the alignment of potential spill sections and their containing output
266 // sections.
267 if (auto it = script->potentialSpillLists.find(Val: ms);
268 it != script->potentialSpillLists.end()) {
269 for (PotentialSpillSection *s = it->second.head; s; s = s->next) {
270 s->addralign = std::max(a: s->addralign, b: ms->addralign);
271 s->parent->addralign = std::max(a: s->parent->addralign, b: s->addralign);
272 }
273 }
274
275 ms->finalizeContents();
276 }
277}
278
279static void sortByOrder(MutableArrayRef<InputSection *> in,
280 llvm::function_ref<int(InputSectionBase *s)> order) {
281 std::vector<std::pair<int, InputSection *>> v;
282 for (InputSection *s : in)
283 v.emplace_back(args: order(s), args&: s);
284 llvm::stable_sort(Range&: v, C: less_first());
285
286 for (size_t i = 0; i < v.size(); ++i)
287 in[i] = v[i].second;
288}
289
290uint64_t elf::getHeaderSize(Ctx &ctx) {
291 if (ctx.arg.oFormatBinary)
292 return 0;
293 return ctx.out.elfHeader->size + ctx.out.programHeaders->size;
294}
295
296void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
297 assert(isLive());
298 for (SectionCommand *b : commands)
299 if (auto *isd = dyn_cast<InputSectionDescription>(Val: b))
300 sortByOrder(in: isd->sections, order);
301}
302
303static void nopInstrFill(Ctx &ctx, uint8_t *buf, size_t size) {
304 if (size == 0)
305 return;
306 unsigned i = 0;
307 std::vector<std::vector<uint8_t>> nopFiller = *ctx.target->nopInstrs;
308 unsigned num = size / nopFiller.back().size();
309 for (unsigned c = 0; c < num; ++c) {
310 memcpy(dest: buf + i, src: nopFiller.back().data(), n: nopFiller.back().size());
311 i += nopFiller.back().size();
312 }
313 unsigned remaining = size - i;
314 if (!remaining)
315 return;
316 assert(nopFiller[remaining - 1].size() == remaining);
317 memcpy(dest: buf + i, src: nopFiller[remaining - 1].data(), n: remaining);
318}
319
320// Fill [Buf, Buf + Size) with Filler.
321// This is used for linker script "=fillexp" command.
322static void fill(uint8_t *buf, size_t size,
323 const std::array<uint8_t, 4> &filler) {
324 size_t i = 0;
325 for (; i + 4 < size; i += 4)
326 memcpy(dest: buf + i, src: filler.data(), n: 4);
327 memcpy(dest: buf + i, src: filler.data(), n: size - i);
328}
329
330#if LLVM_ENABLE_ZLIB
331static SmallVector<uint8_t, 0> deflateShard(Ctx &ctx, ArrayRef<uint8_t> in,
332 int level, int flush) {
333 // 15 and 8 are default. windowBits=-15 is negative to generate raw deflate
334 // data with no zlib header or trailer.
335 z_stream s = {};
336 auto res = deflateInit2(&s, level, Z_DEFLATED, -15, 8, Z_DEFAULT_STRATEGY);
337 if (res != 0) {
338 Err(ctx) << "--compress-sections: deflateInit2 returned " << res;
339 return {};
340 }
341 s.next_in = const_cast<uint8_t *>(in.data());
342 s.avail_in = in.size();
343
344 // Allocate a buffer of half of the input size, and grow it by 1.5x if
345 // insufficient.
346 SmallVector<uint8_t, 0> out;
347 size_t pos = 0;
348 out.resize_for_overwrite(N: std::max<size_t>(a: in.size() / 2, b: 64));
349 do {
350 if (pos == out.size())
351 out.resize_for_overwrite(N: out.size() * 3 / 2);
352 s.next_out = out.data() + pos;
353 s.avail_out = out.size() - pos;
354 (void)deflate(strm: &s, flush);
355 pos = s.next_out - out.data();
356 } while (s.avail_out == 0);
357 assert(s.avail_in == 0);
358
359 out.truncate(N: pos);
360 deflateEnd(strm: &s);
361 return out;
362}
363#endif
364
365// Compress certain non-SHF_ALLOC sections:
366//
367// * (if --compress-debug-sections is specified) non-empty .debug_* sections
368// * (if --compress-sections is specified) matched sections
369template <class ELFT> void OutputSection::maybeCompress(Ctx &ctx) {
370 using Elf_Chdr = typename ELFT::Chdr;
371 (void)sizeof(Elf_Chdr);
372
373 DebugCompressionType ctype = DebugCompressionType::None;
374 size_t compressedSize = sizeof(Elf_Chdr);
375 unsigned level = 0; // default compression level
376 if (!(flags & SHF_ALLOC) && ctx.arg.compressDebugSections &&
377 name.starts_with(Prefix: ".debug_"))
378 ctype = *ctx.arg.compressDebugSections;
379 for (auto &[glob, t, l] : ctx.arg.compressSections)
380 if (glob.match(S: name))
381 std::tie(args&: ctype, args&: level) = {t, l};
382 if (ctype == DebugCompressionType::None)
383 return;
384 if (flags & SHF_ALLOC) {
385 Err(ctx) << "--compress-sections: section '" << name
386 << "' with the SHF_ALLOC flag cannot be compressed";
387 return;
388 }
389
390 llvm::TimeTraceScope timeScope("Compress sections");
391 auto buf = std::make_unique<uint8_t[]>(num: size);
392 // Write uncompressed data to a temporary zero-initialized buffer.
393 {
394 parallel::TaskGroup tg;
395 writeTo<ELFT>(ctx, buf.get(), tg);
396 }
397 // The generic ABI specifies "The sh_size and sh_addralign fields of the
398 // section header for a compressed section reflect the requirements of the
399 // compressed section." However, 1-byte alignment has been wildly accepted
400 // and utilized for a long time. Removing alignment padding is particularly
401 // useful when there are many compressed output sections.
402 addralign = 1;
403
404 // Split input into 1-MiB shards.
405 [[maybe_unused]] constexpr size_t shardSize = 1 << 20;
406 auto shardsIn = split(arr: ArrayRef<uint8_t>(buf.get(), size), chunkSize: shardSize);
407 const size_t numShards = shardsIn.size();
408 auto shardsOut = std::make_unique<SmallVector<uint8_t, 0>[]>(num: numShards);
409
410#if LLVM_ENABLE_ZSTD
411 // Use ZSTD's streaming compression API. See
412 // http://facebook.github.io/zstd/zstd_manual.html "Streaming compression -
413 // HowTo".
414 if (ctype == DebugCompressionType::Zstd) {
415 parallelFor(0, numShards, [&](size_t i) {
416 SmallVector<uint8_t, 0> out;
417 ZSTD_CCtx *cctx = ZSTD_createCCtx();
418 ZSTD_CCtx_setParameter(cctx, param: ZSTD_c_compressionLevel, value: level);
419 ZSTD_inBuffer zib = {.src: shardsIn[i].data(), .size: shardsIn[i].size(), .pos: 0};
420 ZSTD_outBuffer zob = {.dst: nullptr, .size: 0, .pos: 0};
421 size_t size;
422 do {
423 // Allocate a buffer of half of the input size, and grow it by 1.5x if
424 // insufficient.
425 if (zob.pos == zob.size) {
426 out.resize_for_overwrite(
427 N: zob.size ? zob.size * 3 / 2 : std::max<size_t>(a: zib.size / 4, b: 64));
428 zob = {.dst: out.data(), .size: out.size(), .pos: zob.pos};
429 }
430 size = ZSTD_compressStream2(cctx, output: &zob, input: &zib, endOp: ZSTD_e_end);
431 assert(!ZSTD_isError(size));
432 } while (size != 0);
433 out.truncate(N: zob.pos);
434 ZSTD_freeCCtx(cctx);
435 shardsOut[i] = std::move(out);
436 });
437 compressed.type = ELFCOMPRESS_ZSTD;
438 for (size_t i = 0; i != numShards; ++i)
439 compressedSize += shardsOut[i].size();
440 }
441#endif
442
443#if LLVM_ENABLE_ZLIB
444 // We chose 1 (Z_BEST_SPEED) as the default compression level because it is
445 // fast and provides decent compression ratios.
446 if (ctype == DebugCompressionType::Zlib) {
447 if (!level)
448 level = Z_BEST_SPEED;
449
450 // Compress shards and compute Alder-32 checksums. Use Z_SYNC_FLUSH for all
451 // shards but the last to flush the output to a byte boundary to be
452 // concatenated with the next shard.
453 auto shardsAdler = std::make_unique<uint32_t[]>(num: numShards);
454 parallelFor(0, numShards, [&](size_t i) {
455 shardsOut[i] = deflateShard(ctx, in: shardsIn[i], level,
456 flush: i != numShards - 1 ? Z_SYNC_FLUSH : Z_FINISH);
457 shardsAdler[i] = adler32(adler: 1, buf: shardsIn[i].data(), len: shardsIn[i].size());
458 });
459
460 // Update section size and combine Alder-32 checksums.
461 uint32_t checksum = 1; // Initial Adler-32 value
462 compressedSize += 2; // Elf_Chdir and zlib header
463 for (size_t i = 0; i != numShards; ++i) {
464 compressedSize += shardsOut[i].size();
465 checksum = adler32_combine(checksum, shardsAdler[i], shardsIn[i].size());
466 }
467 compressedSize += 4; // checksum
468 compressed.type = ELFCOMPRESS_ZLIB;
469 compressed.checksum = checksum;
470 }
471#endif
472
473 if (compressedSize >= size)
474 return;
475 compressed.uncompressedSize = size;
476 compressed.shards = std::move(shardsOut);
477 compressed.numShards = numShards;
478 size = compressedSize;
479 flags |= SHF_COMPRESSED;
480}
481
482static void writeInt(Ctx &ctx, uint8_t *buf, uint64_t data, uint64_t size) {
483 if (size == 1)
484 *buf = data;
485 else if (size == 2)
486 write16(ctx, p: buf, v: data);
487 else if (size == 4)
488 write32(ctx, p: buf, v: data);
489 else if (size == 8)
490 write64(ctx, p: buf, v: data);
491 else
492 llvm_unreachable("unsupported Size argument");
493}
494
495template <class ELFT>
496void OutputSection::writeTo(Ctx &ctx, uint8_t *buf, parallel::TaskGroup &tg) {
497 llvm::TimeTraceScope timeScope("Write sections", name);
498 if (type == SHT_NOBITS)
499 return;
500 if (type == SHT_CREL && !(flags & SHF_ALLOC)) {
501 buf += encodeULEB128(Value: crelHeader, p: buf);
502 memcpy(dest: buf, src: crelBody.data(), n: crelBody.size());
503 return;
504 }
505
506 // If the section is compressed due to
507 // --compress-debug-section/--compress-sections, the content is already known.
508 if (compressed.shards) {
509 auto *chdr = reinterpret_cast<typename ELFT::Chdr *>(buf);
510 chdr->ch_type = compressed.type;
511 chdr->ch_size = compressed.uncompressedSize;
512 chdr->ch_addralign = addralign;
513 buf += sizeof(*chdr);
514
515 auto offsets = std::make_unique<size_t[]>(num: compressed.numShards);
516 if (compressed.type == ELFCOMPRESS_ZLIB) {
517 buf[0] = 0x78; // CMF
518 buf[1] = 0x01; // FLG: best speed
519 offsets[0] = 2; // zlib header
520 write32be(P: buf + (size - sizeof(*chdr) - 4), V: compressed.checksum);
521 }
522
523 // Compute shard offsets.
524 for (size_t i = 1; i != compressed.numShards; ++i)
525 offsets[i] = offsets[i - 1] + compressed.shards[i - 1].size();
526 parallelFor(0, compressed.numShards, [&](size_t i) {
527 memcpy(dest: buf + offsets[i], src: compressed.shards[i].data(),
528 n: compressed.shards[i].size());
529 });
530 return;
531 }
532
533 // Write leading padding.
534 ArrayRef<InputSection *> sections = getInputSections(os: *this, storage);
535 std::array<uint8_t, 4> filler = getFiller(ctx);
536 bool nonZeroFiller = read32(ctx, p: filler.data()) != 0;
537 if (nonZeroFiller)
538 fill(buf, size: sections.empty() ? size : sections[0]->outSecOff, filler);
539
540 auto fn = [=, &ctx](size_t begin, size_t end) {
541 size_t numSections = sections.size();
542 for (size_t i = begin; i != end; ++i) {
543 InputSection *isec = sections[i];
544 if (auto *s = dyn_cast<SyntheticSection>(Val: isec))
545 s->writeTo(buf: buf + isec->outSecOff);
546 else
547 isec->writeTo<ELFT>(ctx, buf + isec->outSecOff);
548
549 // When in Arm BE8 mode, the linker has to convert the big-endian
550 // instructions to little-endian, leaving the data big-endian.
551 if (ctx.arg.emachine == EM_ARM && !ctx.arg.isLE && ctx.arg.armBe8 &&
552 (flags & SHF_EXECINSTR))
553 convertArmInstructionstoBE8(ctx, sec: isec, buf: buf + isec->outSecOff);
554
555 // Fill gaps between sections.
556 if (nonZeroFiller) {
557 uint8_t *start = buf + isec->outSecOff + isec->getSize();
558 uint8_t *end;
559 if (i + 1 == numSections)
560 end = buf + size;
561 else
562 end = buf + sections[i + 1]->outSecOff;
563 if (isec->nopFiller) {
564 assert(ctx.target->nopInstrs);
565 nopInstrFill(ctx, buf: start, size: end - start);
566 } else
567 fill(buf: start, size: end - start, filler);
568 }
569 }
570 };
571
572 // If there is any BYTE()-family command (rare), write the section content
573 // first then process BYTE to overwrite the filler content. The write is
574 // serial due to the limitation of llvm/Support/Parallel.h.
575 bool written = false;
576 size_t numSections = sections.size();
577 for (SectionCommand *cmd : commands)
578 if (auto *data = dyn_cast<ByteCommand>(Val: cmd)) {
579 if (!std::exchange(obj&: written, new_val: true))
580 fn(0, numSections);
581 writeInt(ctx, buf: buf + data->offset, data: data->expression().getValue(),
582 size: data->size);
583 }
584 if (written || !numSections)
585 return;
586
587 // There is no data command. Write content asynchronously to overlap the write
588 // time with other output sections. Note, if a linker script specifies
589 // overlapping output sections (needs --noinhibit-exec or --no-check-sections
590 // to supress the error), the output may be non-deterministic.
591 const size_t taskSizeLimit = 4 << 20;
592 for (size_t begin = 0, i = 0, taskSize = 0;;) {
593 taskSize += sections[i]->getSize();
594 bool done = ++i == numSections;
595 if (done || taskSize >= taskSizeLimit) {
596 tg.spawn(f: [=] { fn(begin, i); });
597 if (done)
598 break;
599 begin = i;
600 taskSize = 0;
601 }
602 }
603}
604
605static void finalizeShtGroup(Ctx &ctx, OutputSection *os,
606 InputSection *section) {
607 // sh_link field for SHT_GROUP sections should contain the section index of
608 // the symbol table.
609 os->link = ctx.in.symTab->getParent()->sectionIndex;
610
611 if (!section)
612 return;
613
614 // sh_info then contain index of an entry in symbol table section which
615 // provides signature of the section group.
616 ArrayRef<Symbol *> symbols = section->file->getSymbols();
617 os->info = ctx.in.symTab->getSymbolIndex(sym: *symbols[section->info]);
618
619 // Some group members may be combined or discarded, so we need to compute the
620 // new size. The content will be rewritten in InputSection::copyShtGroup.
621 DenseSet<uint32_t> seen;
622 ArrayRef<InputSectionBase *> sections = section->file->getSections();
623 for (auto &idx : section->getDataAs<std::array<char, 4>>().slice(N: 1))
624 if (OutputSection *osec = sections[read32(ctx, p: &idx)]->getOutputSection())
625 seen.insert(V: osec->sectionIndex);
626 os->size = (1 + seen.size()) * sizeof(uint32_t);
627}
628
629template <class uint>
630LLVM_ATTRIBUTE_ALWAYS_INLINE static void
631encodeOneCrel(Ctx &ctx, raw_svector_ostream &os,
632 Elf_Crel<sizeof(uint) == 8> &out, uint offset, const Symbol &sym,
633 uint32_t type, uint addend) {
634 const auto deltaOffset = static_cast<uint64_t>(offset - out.r_offset);
635 out.r_offset = offset;
636 int64_t symidx = ctx.in.symTab->getSymbolIndex(sym);
637 if (sym.type == STT_SECTION) {
638 auto *d = dyn_cast<Defined>(Val: &sym);
639 if (d) {
640 SectionBase *section = d->section;
641 assert(section->isLive());
642 addend = sym.getVA(ctx, addend) - section->getOutputSection()->addr;
643 } else {
644 // Encode R_*_NONE(symidx=0).
645 symidx = type = addend = 0;
646 }
647 }
648
649 // Similar to llvm::ELF::encodeCrel.
650 uint8_t b = deltaOffset * 8 + (out.r_symidx != symidx) +
651 (out.r_type != type ? 2 : 0) +
652 (uint(out.r_addend) != addend ? 4 : 0);
653 if (deltaOffset < 0x10) {
654 os << char(b);
655 } else {
656 os << char(b | 0x80);
657 encodeULEB128(Value: deltaOffset >> 4, OS&: os);
658 }
659 if (b & 1) {
660 encodeSLEB128(Value: static_cast<int32_t>(symidx - out.r_symidx), OS&: os);
661 out.r_symidx = symidx;
662 }
663 if (b & 2) {
664 encodeSLEB128(Value: static_cast<int32_t>(type - out.r_type), OS&: os);
665 out.r_type = type;
666 }
667 if (b & 4) {
668 encodeSLEB128(std::make_signed_t<uint>(addend - out.r_addend), os);
669 out.r_addend = addend;
670 }
671}
672
673template <class ELFT>
674static size_t relToCrel(Ctx &ctx, raw_svector_ostream &os,
675 Elf_Crel<ELFT::Is64Bits> &out, InputSection *relSec,
676 InputSectionBase *sec) {
677 const auto &file = *cast<ELFFileBase>(Val: relSec->file);
678 if (relSec->type == SHT_REL) {
679 // REL conversion is complex and unsupported yet.
680 Err(ctx) << relSec << ": REL cannot be converted to CREL";
681 return 0;
682 }
683 auto rels = relSec->getDataAs<typename ELFT::Rela>();
684 for (auto rel : rels) {
685 encodeOneCrel<typename ELFT::uint>(
686 ctx, os, out, sec->getVA(offset: rel.r_offset), file.getRelocTargetSym(rel),
687 rel.getType(ctx.arg.isMips64EL), getAddend<ELFT>(rel));
688 }
689 return rels.size();
690}
691
692// Compute the content of a non-alloc CREL section due to -r or --emit-relocs.
693// Input CREL sections are decoded while REL[A] need to be converted.
694template <bool is64> void OutputSection::finalizeNonAllocCrel(Ctx &ctx) {
695 using uint = typename Elf_Crel_Impl<is64>::uint;
696 raw_svector_ostream os(crelBody);
697 uint64_t totalCount = 0;
698 Elf_Crel<is64> out{};
699 assert(commands.size() == 1);
700 auto *isd = cast<InputSectionDescription>(Val: commands[0]);
701 for (InputSection *relSec : isd->sections) {
702 const auto &file = *cast<ELFFileBase>(Val: relSec->file);
703 InputSectionBase *sec = relSec->getRelocatedSection();
704 if (relSec->type == SHT_CREL) {
705 RelocsCrel<is64> entries(relSec->content_);
706 totalCount += entries.size();
707 for (Elf_Crel_Impl<is64> r : entries) {
708 encodeOneCrel<uint>(ctx, os, out, uint(sec->getVA(offset: r.r_offset)),
709 file.getSymbol(symbolIndex: r.r_symidx), r.r_type, r.r_addend);
710 }
711 continue;
712 }
713
714 // Convert REL[A] to CREL.
715 if constexpr (is64) {
716 totalCount += ctx.arg.isLE
717 ? relToCrel<ELF64LE>(ctx, os, out, relSec, sec)
718 : relToCrel<ELF64BE>(ctx, os, out, relSec, sec);
719 } else {
720 totalCount += ctx.arg.isLE
721 ? relToCrel<ELF32LE>(ctx, os, out, relSec, sec)
722 : relToCrel<ELF32BE>(ctx, os, out, relSec, sec);
723 }
724 }
725
726 crelHeader = totalCount * 8 + 4;
727 size = getULEB128Size(Value: crelHeader) + crelBody.size();
728}
729
730void OutputSection::finalize(Ctx &ctx) {
731 InputSection *first = getFirstInputSection(os: this);
732
733 if (flags & SHF_LINK_ORDER) {
734 // We must preserve the link order dependency of sections with the
735 // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
736 // need to translate the InputSection sh_link to the OutputSection sh_link,
737 // all InputSections in the OutputSection have the same dependency.
738 if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(Val: first))
739 link = ex->getLinkOrderDep()->getParent()->sectionIndex;
740 else if (first->flags & SHF_LINK_ORDER)
741 if (auto *d = first->getLinkOrderDep())
742 link = d->getParent()->sectionIndex;
743 }
744
745 if (type == SHT_GROUP) {
746 finalizeShtGroup(ctx, os: this, section: first);
747 return;
748 }
749
750 if (!ctx.arg.copyRelocs || !isStaticRelSecType(type))
751 return;
752
753 // Skip if 'first' is synthetic, i.e. not a section created by --emit-relocs.
754 // Normally 'type' was changed by 'first' so 'first' should be non-null.
755 // However, if the output section is .rela.dyn, 'type' can be set by the empty
756 // synthetic .rela.plt and first can be null.
757 if (!first || isa<SyntheticSection>(Val: first))
758 return;
759
760 link = ctx.in.symTab->getParent()->sectionIndex;
761 // sh_info for SHT_REL[A] sections should contain the section header index of
762 // the section to which the relocation applies.
763 InputSectionBase *s = first->getRelocatedSection();
764 info = s->getOutputSection()->sectionIndex;
765 flags |= SHF_INFO_LINK;
766 // Finalize the content of non-alloc CREL.
767 if (type == SHT_CREL) {
768 if (ctx.arg.is64)
769 finalizeNonAllocCrel<true>(ctx);
770 else
771 finalizeNonAllocCrel<false>(ctx);
772 }
773}
774
775// Returns true if S is in one of the many forms the compiler driver may pass
776// crtbegin files.
777//
778// Gcc uses any of crtbegin[<empty>|S|T].o.
779// Clang uses Gcc's plus clang_rt.crtbegin[-<arch>|<empty>].o.
780
781static bool isCrt(StringRef s, StringRef beginEnd) {
782 s = sys::path::filename(path: s);
783 if (!s.consume_back(Suffix: ".o"))
784 return false;
785 if (s.consume_front(Prefix: "clang_rt."))
786 return s.consume_front(Prefix: beginEnd);
787 return s.consume_front(Prefix: beginEnd) && s.size() <= 1;
788}
789
790// .ctors and .dtors are sorted by this order:
791//
792// 1. .ctors/.dtors in crtbegin (which contains a sentinel value -1).
793// 2. The section is named ".ctors" or ".dtors" (priority: 65536).
794// 3. The section has an optional priority value in the form of ".ctors.N" or
795// ".dtors.N" where N is a number in the form of %05u (priority: 65535-N).
796// 4. .ctors/.dtors in crtend (which contains a sentinel value 0).
797//
798// For 2 and 3, the sections are sorted by priority from high to low, e.g.
799// .ctors (65536), .ctors.00100 (65436), .ctors.00200 (65336). In GNU ld's
800// internal linker scripts, the sorting is by string comparison which can
801// achieve the same goal given the optional priority values are of the same
802// length.
803//
804// In an ideal world, we don't need this function because .init_array and
805// .ctors are duplicate features (and .init_array is newer.) However, there
806// are too many real-world use cases of .ctors, so we had no choice to
807// support that with this rather ad-hoc semantics.
808static bool compCtors(const InputSection *a, const InputSection *b) {
809 bool beginA = isCrt(s: a->file->getName(), beginEnd: "crtbegin");
810 bool beginB = isCrt(s: b->file->getName(), beginEnd: "crtbegin");
811 if (beginA != beginB)
812 return beginA;
813 bool endA = isCrt(s: a->file->getName(), beginEnd: "crtend");
814 bool endB = isCrt(s: b->file->getName(), beginEnd: "crtend");
815 if (endA != endB)
816 return endB;
817 return getPriority(s: a->name) > getPriority(s: b->name);
818}
819
820// Sorts input sections by the special rules for .ctors and .dtors.
821// Unfortunately, the rules are different from the one for .{init,fini}_array.
822// Read the comment above.
823void OutputSection::sortCtorsDtors() {
824 assert(commands.size() == 1);
825 auto *isd = cast<InputSectionDescription>(Val: commands[0]);
826 llvm::stable_sort(Range&: isd->sections, C: compCtors);
827}
828
829// If an input string is in the form of "foo.N" where N is a number, return N
830// (65535-N if .ctors.N or .dtors.N). Otherwise, returns 65536, which is one
831// greater than the lowest priority.
832int elf::getPriority(StringRef s) {
833 size_t pos = s.rfind(C: '.');
834 if (pos == StringRef::npos)
835 return 65536;
836 int v = 65536;
837 if (to_integer(S: s.substr(Start: pos + 1), Num&: v, Base: 10) &&
838 (pos == 6 && (s.starts_with(Prefix: ".ctors") || s.starts_with(Prefix: ".dtors"))))
839 v = 65535 - v;
840 return v;
841}
842
843InputSection *elf::getFirstInputSection(const OutputSection *os) {
844 for (SectionCommand *cmd : os->commands)
845 if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
846 if (!isd->sections.empty())
847 return isd->sections[0];
848 return nullptr;
849}
850
851ArrayRef<InputSection *>
852elf::getInputSections(const OutputSection &os,
853 SmallVector<InputSection *, 0> &storage) {
854 ArrayRef<InputSection *> ret;
855 storage.clear();
856 for (SectionCommand *cmd : os.commands) {
857 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
858 if (!isd)
859 continue;
860 if (ret.empty()) {
861 ret = isd->sections;
862 } else {
863 if (storage.empty())
864 storage.assign(in_start: ret.begin(), in_end: ret.end());
865 storage.insert(I: storage.end(), From: isd->sections.begin(), To: isd->sections.end());
866 }
867 }
868 return storage.empty() ? ret : ArrayRef(storage);
869}
870
871// Sorts input sections by section name suffixes, so that .foo.N comes
872// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
873// We want to keep the original order if the priorities are the same
874// because the compiler keeps the original initialization order in a
875// translation unit and we need to respect that.
876// For more detail, read the section of the GCC's manual about init_priority.
877void OutputSection::sortInitFini() {
878 // Sort sections by priority.
879 sort(order: [](InputSectionBase *s) { return getPriority(s: s->name); });
880}
881
882std::array<uint8_t, 4> OutputSection::getFiller(Ctx &ctx) {
883 if (filler)
884 return *filler;
885 if (!(flags & SHF_EXECINSTR))
886 return {0, 0, 0, 0};
887 if (ctx.arg.relocatable && ctx.arg.emachine == EM_RISCV) {
888 // See RISCV::maybeSynthesizeAlign: Synthesized NOP bytes and ALIGN
889 // relocations might be needed between two input sections. Use a NOP for the
890 // filler.
891 if (ctx.arg.eflags & EF_RISCV_RVC)
892 return {1, 0, 1, 0};
893 return {0x13, 0, 0, 0};
894 }
895 if (ctx.arg.relocatable && ctx.arg.emachine == EM_LOONGARCH)
896 return {0, 0, 0x40, 0x03};
897 return ctx.target->trapInstr;
898}
899
900void OutputSection::checkDynRelAddends(Ctx &ctx) {
901 assert(ctx.arg.writeAddends && ctx.arg.checkDynamicRelocs);
902 assert(isStaticRelSecType(type));
903 SmallVector<InputSection *, 0> storage;
904 ArrayRef<InputSection *> sections = getInputSections(os: *this, storage);
905 parallelFor(Begin: 0, End: sections.size(), Fn: [&](size_t i) {
906 // When linking with -r or --emit-relocs we might also call this function
907 // for input .rel[a].<sec> sections which we simply pass through to the
908 // output. We skip over those and only look at the synthetic relocation
909 // sections created during linking.
910 if (!SyntheticSection::classof(sec: sections[i]) ||
911 !is_contained(Set: {ELF::SHT_REL, ELF::SHT_RELA, ELF::SHT_RELR},
912 Element: sections[i]->type))
913 return;
914 const auto *sec = cast<RelocationBaseSection>(Val: sections[i]);
915 if (!sec)
916 return;
917 for (const DynamicReloc &rel : sec->relocs) {
918 int64_t addend = rel.addend;
919 const OutputSection *relOsec = rel.inputSec->getOutputSection();
920 assert(relOsec != nullptr && "missing output section for relocation");
921 // Some targets have NOBITS synthetic sections with dynamic relocations
922 // with non-zero addends. Skip such sections.
923 if (is_contained(Set: {EM_PPC, EM_PPC64}, Element: ctx.arg.emachine) &&
924 (rel.inputSec == ctx.in.ppc64LongBranchTarget.get() ||
925 rel.inputSec == ctx.in.igotPlt.get()))
926 continue;
927 const uint8_t *relocTarget = ctx.bufferStart + relOsec->offset +
928 rel.inputSec->getOffset(offset: rel.offsetInSec);
929 // For SHT_NOBITS the written addend is always zero.
930 int64_t writtenAddend =
931 relOsec->type == SHT_NOBITS
932 ? 0
933 : ctx.target->getImplicitAddend(buf: relocTarget, type: rel.type);
934 if (addend != writtenAddend)
935 InternalErr(ctx, buf: relocTarget)
936 << "wrote incorrect addend value 0x" << utohexstr(X: writtenAddend)
937 << " instead of 0x" << utohexstr(X: addend)
938 << " for dynamic relocation " << rel.type << " at offset 0x"
939 << utohexstr(X: rel.getOffset())
940 << (rel.sym ? " against symbol " + rel.sym->getName() : "");
941 }
942 });
943}
944
945template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
946template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
947template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
948template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
949
950template void OutputSection::writeTo<ELF32LE>(Ctx &, uint8_t *,
951 llvm::parallel::TaskGroup &);
952template void OutputSection::writeTo<ELF32BE>(Ctx &, uint8_t *,
953 llvm::parallel::TaskGroup &);
954template void OutputSection::writeTo<ELF64LE>(Ctx &, uint8_t *,
955 llvm::parallel::TaskGroup &);
956template void OutputSection::writeTo<ELF64BE>(Ctx &, uint8_t *,
957 llvm::parallel::TaskGroup &);
958
959template void OutputSection::maybeCompress<ELF32LE>(Ctx &);
960template void OutputSection::maybeCompress<ELF32BE>(Ctx &);
961template void OutputSection::maybeCompress<ELF64LE>(Ctx &);
962template void OutputSection::maybeCompress<ELF64BE>(Ctx &);
963