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