xref: /freebsd/contrib/llvm-project/lld/ELF/SyntheticSections.h (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
1 //===- SyntheticSection.h ---------------------------------------*- C++ -*-===//
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 // Synthetic sections represent chunks of linker-created data. If you
10 // need to create a chunk of data that to be included in some section
11 // in the result, you probably want to create that as a synthetic section.
12 //
13 // Synthetic sections are designed as input sections as opposed to
14 // output sections because we want to allow them to be manipulated
15 // using linker scripts just like other input sections from regular
16 // files.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLD_ELF_SYNTHETIC_SECTIONS_H
21 #define LLD_ELF_SYNTHETIC_SECTIONS_H
22 
23 #include "DWARF.h"
24 #include "EhFrame.h"
25 #include "InputSection.h"
26 #include "llvm/ADT/DenseSet.h"
27 #include "llvm/ADT/MapVector.h"
28 #include "llvm/MC/StringTableBuilder.h"
29 #include "llvm/Support/Endian.h"
30 #include <functional>
31 
32 namespace lld {
33 namespace elf {
34 class Defined;
35 struct PhdrEntry;
36 class SymbolTableBaseSection;
37 class VersionNeedBaseSection;
38 
39 class SyntheticSection : public InputSection {
40 public:
41   SyntheticSection(uint64_t flags, uint32_t type, uint32_t alignment,
42                    StringRef name)
43       : InputSection(nullptr, flags, type, alignment, {}, name,
44                      InputSectionBase::Synthetic) {
45     markLive();
46   }
47 
48   virtual ~SyntheticSection() = default;
49   virtual void writeTo(uint8_t *buf) = 0;
50   virtual size_t getSize() const = 0;
51   virtual void finalizeContents() {}
52   // If the section has the SHF_ALLOC flag and the size may be changed if
53   // thunks are added, update the section size.
54   virtual bool updateAllocSize() { return false; }
55   virtual bool isNeeded() const { return true; }
56 
57   static bool classof(const SectionBase *d) {
58     return d->kind() == InputSectionBase::Synthetic;
59   }
60 };
61 
62 struct CieRecord {
63   EhSectionPiece *cie = nullptr;
64   std::vector<EhSectionPiece *> fdes;
65 };
66 
67 // Section for .eh_frame.
68 class EhFrameSection final : public SyntheticSection {
69 public:
70   EhFrameSection();
71   void writeTo(uint8_t *buf) override;
72   void finalizeContents() override;
73   bool isNeeded() const override { return !sections.empty(); }
74   size_t getSize() const override { return size; }
75 
76   static bool classof(const SectionBase *d) {
77     return SyntheticSection::classof(d) && d->name == ".eh_frame";
78   }
79 
80   void addSection(EhInputSection *sec);
81 
82   std::vector<EhInputSection *> sections;
83   size_t numFdes = 0;
84 
85   struct FdeData {
86     uint32_t pcRel;
87     uint32_t fdeVARel;
88   };
89 
90   std::vector<FdeData> getFdeData() const;
91   ArrayRef<CieRecord *> getCieRecords() const { return cieRecords; }
92   template <class ELFT>
93   void iterateFDEWithLSDA(llvm::function_ref<void(InputSection &)> fn);
94 
95 private:
96   // This is used only when parsing EhInputSection. We keep it here to avoid
97   // allocating one for each EhInputSection.
98   llvm::DenseMap<size_t, CieRecord *> offsetToCie;
99 
100   uint64_t size = 0;
101 
102   template <class ELFT, class RelTy>
103   void addRecords(EhInputSection *s, llvm::ArrayRef<RelTy> rels);
104   template <class ELFT> void addSectionAux(EhInputSection *s);
105   template <class ELFT, class RelTy>
106   void iterateFDEWithLSDAAux(EhInputSection &sec, ArrayRef<RelTy> rels,
107                              llvm::DenseSet<size_t> &ciesWithLSDA,
108                              llvm::function_ref<void(InputSection &)> fn);
109 
110   template <class ELFT, class RelTy>
111   CieRecord *addCie(EhSectionPiece &piece, ArrayRef<RelTy> rels);
112 
113   template <class ELFT, class RelTy>
114   Defined *isFdeLive(EhSectionPiece &piece, ArrayRef<RelTy> rels);
115 
116   uint64_t getFdePc(uint8_t *buf, size_t off, uint8_t enc) const;
117 
118   std::vector<CieRecord *> cieRecords;
119 
120   // CIE records are uniquified by their contents and personality functions.
121   llvm::DenseMap<std::pair<ArrayRef<uint8_t>, Symbol *>, CieRecord *> cieMap;
122 };
123 
124 class GotSection : public SyntheticSection {
125 public:
126   GotSection();
127   size_t getSize() const override { return size; }
128   void finalizeContents() override;
129   bool isNeeded() const override;
130   void writeTo(uint8_t *buf) override;
131 
132   void addEntry(Symbol &sym);
133   bool addDynTlsEntry(Symbol &sym);
134   bool addTlsIndex();
135   uint64_t getGlobalDynAddr(const Symbol &b) const;
136   uint64_t getGlobalDynOffset(const Symbol &b) const;
137 
138   uint64_t getTlsIndexVA() { return this->getVA() + tlsIndexOff; }
139   uint32_t getTlsIndexOff() const { return tlsIndexOff; }
140 
141   // Flag to force GOT to be in output if we have relocations
142   // that relies on its address.
143   bool hasGotOffRel = false;
144 
145 protected:
146   size_t numEntries = 0;
147   uint32_t tlsIndexOff = -1;
148   uint64_t size = 0;
149 };
150 
151 // .note.GNU-stack section.
152 class GnuStackSection : public SyntheticSection {
153 public:
154   GnuStackSection()
155       : SyntheticSection(0, llvm::ELF::SHT_PROGBITS, 1, ".note.GNU-stack") {}
156   void writeTo(uint8_t *buf) override {}
157   size_t getSize() const override { return 0; }
158 };
159 
160 class GnuPropertySection : public SyntheticSection {
161 public:
162   GnuPropertySection();
163   void writeTo(uint8_t *buf) override;
164   size_t getSize() const override;
165 };
166 
167 // .note.gnu.build-id section.
168 class BuildIdSection : public SyntheticSection {
169   // First 16 bytes are a header.
170   static const unsigned headerSize = 16;
171 
172 public:
173   const size_t hashSize;
174   BuildIdSection();
175   void writeTo(uint8_t *buf) override;
176   size_t getSize() const override { return headerSize + hashSize; }
177   void writeBuildId(llvm::ArrayRef<uint8_t> buf);
178 
179 private:
180   uint8_t *hashBuf;
181 };
182 
183 // BssSection is used to reserve space for copy relocations and common symbols.
184 // We create three instances of this class for .bss, .bss.rel.ro and "COMMON",
185 // that are used for writable symbols, read-only symbols and common symbols,
186 // respectively.
187 class BssSection final : public SyntheticSection {
188 public:
189   BssSection(StringRef name, uint64_t size, uint32_t alignment);
190   void writeTo(uint8_t *) override {
191     llvm_unreachable("unexpected writeTo() call for SHT_NOBITS section");
192   }
193   bool isNeeded() const override { return size != 0; }
194   size_t getSize() const override { return size; }
195 
196   static bool classof(const SectionBase *s) { return s->bss; }
197   uint64_t size;
198 };
199 
200 class MipsGotSection final : public SyntheticSection {
201 public:
202   MipsGotSection();
203   void writeTo(uint8_t *buf) override;
204   size_t getSize() const override { return size; }
205   bool updateAllocSize() override;
206   void finalizeContents() override;
207   bool isNeeded() const override;
208 
209   // Join separate GOTs built for each input file to generate
210   // primary and optional multiple secondary GOTs.
211   void build();
212 
213   void addEntry(InputFile &file, Symbol &sym, int64_t addend, RelExpr expr);
214   void addDynTlsEntry(InputFile &file, Symbol &sym);
215   void addTlsIndex(InputFile &file);
216 
217   uint64_t getPageEntryOffset(const InputFile *f, const Symbol &s,
218                               int64_t addend) const;
219   uint64_t getSymEntryOffset(const InputFile *f, const Symbol &s,
220                              int64_t addend) const;
221   uint64_t getGlobalDynOffset(const InputFile *f, const Symbol &s) const;
222   uint64_t getTlsIndexOffset(const InputFile *f) const;
223 
224   // Returns the symbol which corresponds to the first entry of the global part
225   // of GOT on MIPS platform. It is required to fill up MIPS-specific dynamic
226   // table properties.
227   // Returns nullptr if the global part is empty.
228   const Symbol *getFirstGlobalEntry() const;
229 
230   // Returns the number of entries in the local part of GOT including
231   // the number of reserved entries.
232   unsigned getLocalEntriesNum() const;
233 
234   // Return _gp value for primary GOT (nullptr) or particular input file.
235   uint64_t getGp(const InputFile *f = nullptr) const;
236 
237 private:
238   // MIPS GOT consists of three parts: local, global and tls. Each part
239   // contains different types of entries. Here is a layout of GOT:
240   // - Header entries                |
241   // - Page entries                  |   Local part
242   // - Local entries (16-bit access) |
243   // - Local entries (32-bit access) |
244   // - Normal global entries         ||  Global part
245   // - Reloc-only global entries     ||
246   // - TLS entries                   ||| TLS part
247   //
248   // Header:
249   //   Two entries hold predefined value 0x0 and 0x80000000.
250   // Page entries:
251   //   These entries created by R_MIPS_GOT_PAGE relocation and R_MIPS_GOT16
252   //   relocation against local symbols. They are initialized by higher 16-bit
253   //   of the corresponding symbol's value. So each 64kb of address space
254   //   requires a single GOT entry.
255   // Local entries (16-bit access):
256   //   These entries created by GOT relocations against global non-preemptible
257   //   symbols so dynamic linker is not necessary to resolve the symbol's
258   //   values. "16-bit access" means that corresponding relocations address
259   //   GOT using 16-bit index. Each unique Symbol-Addend pair has its own
260   //   GOT entry.
261   // Local entries (32-bit access):
262   //   These entries are the same as above but created by relocations which
263   //   address GOT using 32-bit index (R_MIPS_GOT_HI16/LO16 etc).
264   // Normal global entries:
265   //   These entries created by GOT relocations against preemptible global
266   //   symbols. They need to be initialized by dynamic linker and they ordered
267   //   exactly as the corresponding entries in the dynamic symbols table.
268   // Reloc-only global entries:
269   //   These entries created for symbols that are referenced by dynamic
270   //   relocations R_MIPS_REL32. These entries are not accessed with gp-relative
271   //   addressing, but MIPS ABI requires that these entries be present in GOT.
272   // TLS entries:
273   //   Entries created by TLS relocations.
274   //
275   // If the sum of local, global and tls entries is less than 64K only single
276   // got is enough. Otherwise, multi-got is created. Series of primary and
277   // multiple secondary GOTs have the following layout:
278   // - Primary GOT
279   //     Header
280   //     Local entries
281   //     Global entries
282   //     Relocation only entries
283   //     TLS entries
284   //
285   // - Secondary GOT
286   //     Local entries
287   //     Global entries
288   //     TLS entries
289   // ...
290   //
291   // All GOT entries required by relocations from a single input file entirely
292   // belong to either primary or one of secondary GOTs. To reference GOT entries
293   // each GOT has its own _gp value points to the "middle" of the GOT.
294   // In the code this value loaded to the register which is used for GOT access.
295   //
296   // MIPS 32 function's prologue:
297   //   lui     v0,0x0
298   //   0: R_MIPS_HI16  _gp_disp
299   //   addiu   v0,v0,0
300   //   4: R_MIPS_LO16  _gp_disp
301   //
302   // MIPS 64:
303   //   lui     at,0x0
304   //   14: R_MIPS_GPREL16  main
305   //
306   // Dynamic linker does not know anything about secondary GOTs and cannot
307   // use a regular MIPS mechanism for GOT entries initialization. So we have
308   // to use an approach accepted by other architectures and create dynamic
309   // relocations R_MIPS_REL32 to initialize global entries (and local in case
310   // of PIC code) in secondary GOTs. But ironically MIPS dynamic linker
311   // requires GOT entries and correspondingly ordered dynamic symbol table
312   // entries to deal with dynamic relocations. To handle this problem
313   // relocation-only section in the primary GOT contains entries for all
314   // symbols referenced in global parts of secondary GOTs. Although the sum
315   // of local and normal global entries of the primary got should be less
316   // than 64K, the size of the primary got (including relocation-only entries
317   // can be greater than 64K, because parts of the primary got that overflow
318   // the 64K limit are used only by the dynamic linker at dynamic link-time
319   // and not by 16-bit gp-relative addressing at run-time.
320   //
321   // For complete multi-GOT description see the following link
322   // https://dmz-portal.mips.com/wiki/MIPS_Multi_GOT
323 
324   // Number of "Header" entries.
325   static const unsigned headerEntriesNum = 2;
326 
327   uint64_t size = 0;
328 
329   // Symbol and addend.
330   using GotEntry = std::pair<Symbol *, int64_t>;
331 
332   struct FileGot {
333     InputFile *file = nullptr;
334     size_t startIndex = 0;
335 
336     struct PageBlock {
337       size_t firstIndex;
338       size_t count;
339       PageBlock() : firstIndex(0), count(0) {}
340     };
341 
342     // Map output sections referenced by MIPS GOT relocations
343     // to the description (index/count) "page" entries allocated
344     // for this section.
345     llvm::SmallMapVector<const OutputSection *, PageBlock, 16> pagesMap;
346     // Maps from Symbol+Addend pair or just Symbol to the GOT entry index.
347     llvm::MapVector<GotEntry, size_t> local16;
348     llvm::MapVector<GotEntry, size_t> local32;
349     llvm::MapVector<Symbol *, size_t> global;
350     llvm::MapVector<Symbol *, size_t> relocs;
351     llvm::MapVector<Symbol *, size_t> tls;
352     // Set of symbols referenced by dynamic TLS relocations.
353     llvm::MapVector<Symbol *, size_t> dynTlsSymbols;
354 
355     // Total number of all entries.
356     size_t getEntriesNum() const;
357     // Number of "page" entries.
358     size_t getPageEntriesNum() const;
359     // Number of entries require 16-bit index to access.
360     size_t getIndexedEntriesNum() const;
361   };
362 
363   // Container of GOT created for each input file.
364   // After building a final series of GOTs this container
365   // holds primary and secondary GOT's.
366   std::vector<FileGot> gots;
367 
368   // Return (and create if necessary) `FileGot`.
369   FileGot &getGot(InputFile &f);
370 
371   // Try to merge two GOTs. In case of success the `Dst` contains
372   // result of merging and the function returns true. In case of
373   // overflow the `Dst` is unchanged and the function returns false.
374   bool tryMergeGots(FileGot & dst, FileGot & src, bool isPrimary);
375 };
376 
377 class GotPltSection final : public SyntheticSection {
378 public:
379   GotPltSection();
380   void addEntry(Symbol &sym);
381   size_t getSize() const override;
382   void writeTo(uint8_t *buf) override;
383   bool isNeeded() const override;
384 
385   // Flag to force GotPlt to be in output if we have relocations
386   // that relies on its address.
387   bool hasGotPltOffRel = false;
388 
389 private:
390   std::vector<const Symbol *> entries;
391 };
392 
393 // The IgotPltSection is a Got associated with the PltSection for GNU Ifunc
394 // Symbols that will be relocated by Target->IRelativeRel.
395 // On most Targets the IgotPltSection will immediately follow the GotPltSection
396 // on ARM the IgotPltSection will immediately follow the GotSection.
397 class IgotPltSection final : public SyntheticSection {
398 public:
399   IgotPltSection();
400   void addEntry(Symbol &sym);
401   size_t getSize() const override;
402   void writeTo(uint8_t *buf) override;
403   bool isNeeded() const override { return !entries.empty(); }
404 
405 private:
406   std::vector<const Symbol *> entries;
407 };
408 
409 class StringTableSection final : public SyntheticSection {
410 public:
411   StringTableSection(StringRef name, bool dynamic);
412   unsigned addString(StringRef s, bool hashIt = true);
413   void writeTo(uint8_t *buf) override;
414   size_t getSize() const override { return size; }
415   bool isDynamic() const { return dynamic; }
416 
417 private:
418   const bool dynamic;
419 
420   uint64_t size = 0;
421 
422   llvm::DenseMap<StringRef, unsigned> stringMap;
423   std::vector<StringRef> strings;
424 };
425 
426 class DynamicReloc {
427 public:
428   DynamicReloc(RelType type, const InputSectionBase *inputSec,
429                uint64_t offsetInSec, bool useSymVA, Symbol *sym, int64_t addend)
430       : type(type), sym(sym), inputSec(inputSec), offsetInSec(offsetInSec),
431         useSymVA(useSymVA), addend(addend), outputSec(nullptr) {}
432   // This constructor records dynamic relocation settings used by MIPS
433   // multi-GOT implementation. It's to relocate addresses of 64kb pages
434   // lie inside the output section.
435   DynamicReloc(RelType type, const InputSectionBase *inputSec,
436                uint64_t offsetInSec, const OutputSection *outputSec,
437                int64_t addend)
438       : type(type), sym(nullptr), inputSec(inputSec), offsetInSec(offsetInSec),
439         useSymVA(false), addend(addend), outputSec(outputSec) {}
440 
441   uint64_t getOffset() const;
442   uint32_t getSymIndex(SymbolTableBaseSection *symTab) const;
443 
444   // Computes the addend of the dynamic relocation. Note that this is not the
445   // same as the addend member variable as it also includes the symbol address
446   // if useSymVA is true.
447   int64_t computeAddend() const;
448 
449   RelType type;
450 
451   Symbol *sym;
452   const InputSectionBase *inputSec = nullptr;
453   uint64_t offsetInSec;
454   // If this member is true, the dynamic relocation will not be against the
455   // symbol but will instead be a relative relocation that simply adds the
456   // load address. This means we need to write the symbol virtual address
457   // plus the original addend as the final relocation addend.
458   bool useSymVA;
459   int64_t addend;
460   const OutputSection *outputSec;
461 };
462 
463 template <class ELFT> class DynamicSection final : public SyntheticSection {
464   LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
465 
466   // finalizeContents() fills this vector with the section contents.
467   std::vector<std::pair<int32_t, std::function<uint64_t()>>> entries;
468 
469 public:
470   DynamicSection();
471   void finalizeContents() override;
472   void writeTo(uint8_t *buf) override;
473   size_t getSize() const override { return size; }
474 
475 private:
476   void add(int32_t tag, std::function<uint64_t()> fn);
477   void addInt(int32_t tag, uint64_t val);
478   void addInSec(int32_t tag, InputSection *sec);
479   void addInSecRelative(int32_t tag, InputSection *sec);
480   void addOutSec(int32_t tag, OutputSection *sec);
481   void addSize(int32_t tag, OutputSection *sec);
482   void addSym(int32_t tag, Symbol *sym);
483 
484   uint64_t size = 0;
485 };
486 
487 class RelocationBaseSection : public SyntheticSection {
488 public:
489   RelocationBaseSection(StringRef name, uint32_t type, int32_t dynamicTag,
490                         int32_t sizeDynamicTag);
491   void addReloc(RelType dynType, InputSectionBase *isec, uint64_t offsetInSec,
492                 Symbol *sym);
493   // Add a dynamic relocation that might need an addend. This takes care of
494   // writing the addend to the output section if needed.
495   void addReloc(RelType dynType, InputSectionBase *inputSec,
496                 uint64_t offsetInSec, Symbol *sym, int64_t addend, RelExpr expr,
497                 RelType type);
498   void addReloc(const DynamicReloc &reloc);
499   bool isNeeded() const override { return !relocs.empty(); }
500   size_t getSize() const override { return relocs.size() * this->entsize; }
501   size_t getRelativeRelocCount() const { return numRelativeRelocs; }
502   void finalizeContents() override;
503   int32_t dynamicTag, sizeDynamicTag;
504   std::vector<DynamicReloc> relocs;
505 
506 protected:
507   size_t numRelativeRelocs = 0;
508 };
509 
510 template <class ELFT>
511 class RelocationSection final : public RelocationBaseSection {
512   using Elf_Rel = typename ELFT::Rel;
513   using Elf_Rela = typename ELFT::Rela;
514 
515 public:
516   RelocationSection(StringRef name, bool sort);
517   void writeTo(uint8_t *buf) override;
518 
519 private:
520   bool sort;
521 };
522 
523 template <class ELFT>
524 class AndroidPackedRelocationSection final : public RelocationBaseSection {
525   using Elf_Rel = typename ELFT::Rel;
526   using Elf_Rela = typename ELFT::Rela;
527 
528 public:
529   AndroidPackedRelocationSection(StringRef name);
530 
531   bool updateAllocSize() override;
532   size_t getSize() const override { return relocData.size(); }
533   void writeTo(uint8_t *buf) override {
534     memcpy(buf, relocData.data(), relocData.size());
535   }
536 
537 private:
538   SmallVector<char, 0> relocData;
539 };
540 
541 struct RelativeReloc {
542   uint64_t getOffset() const { return inputSec->getVA(offsetInSec); }
543 
544   const InputSectionBase *inputSec;
545   uint64_t offsetInSec;
546 };
547 
548 class RelrBaseSection : public SyntheticSection {
549 public:
550   RelrBaseSection();
551   bool isNeeded() const override { return !relocs.empty(); }
552   std::vector<RelativeReloc> relocs;
553 };
554 
555 // RelrSection is used to encode offsets for relative relocations.
556 // Proposal for adding SHT_RELR sections to generic-abi is here:
557 //   https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg
558 // For more details, see the comment in RelrSection::updateAllocSize().
559 template <class ELFT> class RelrSection final : public RelrBaseSection {
560   using Elf_Relr = typename ELFT::Relr;
561 
562 public:
563   RelrSection();
564 
565   bool updateAllocSize() override;
566   size_t getSize() const override { return relrRelocs.size() * this->entsize; }
567   void writeTo(uint8_t *buf) override {
568     memcpy(buf, relrRelocs.data(), getSize());
569   }
570 
571 private:
572   std::vector<Elf_Relr> relrRelocs;
573 };
574 
575 struct SymbolTableEntry {
576   Symbol *sym;
577   size_t strTabOffset;
578 };
579 
580 class SymbolTableBaseSection : public SyntheticSection {
581 public:
582   SymbolTableBaseSection(StringTableSection &strTabSec);
583   void finalizeContents() override;
584   size_t getSize() const override { return getNumSymbols() * entsize; }
585   void addSymbol(Symbol *sym);
586   unsigned getNumSymbols() const { return symbols.size() + 1; }
587   size_t getSymbolIndex(Symbol *sym);
588   ArrayRef<SymbolTableEntry> getSymbols() const { return symbols; }
589 
590 protected:
591   void sortSymTabSymbols();
592 
593   // A vector of symbols and their string table offsets.
594   std::vector<SymbolTableEntry> symbols;
595 
596   StringTableSection &strTabSec;
597 
598   llvm::once_flag onceFlag;
599   llvm::DenseMap<Symbol *, size_t> symbolIndexMap;
600   llvm::DenseMap<OutputSection *, size_t> sectionIndexMap;
601 };
602 
603 template <class ELFT>
604 class SymbolTableSection final : public SymbolTableBaseSection {
605   using Elf_Sym = typename ELFT::Sym;
606 
607 public:
608   SymbolTableSection(StringTableSection &strTabSec);
609   void writeTo(uint8_t *buf) override;
610 };
611 
612 class SymtabShndxSection final : public SyntheticSection {
613 public:
614   SymtabShndxSection();
615 
616   void writeTo(uint8_t *buf) override;
617   size_t getSize() const override;
618   bool isNeeded() const override;
619   void finalizeContents() override;
620 };
621 
622 // Outputs GNU Hash section. For detailed explanation see:
623 // https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
624 class GnuHashTableSection final : public SyntheticSection {
625 public:
626   GnuHashTableSection();
627   void finalizeContents() override;
628   void writeTo(uint8_t *buf) override;
629   size_t getSize() const override { return size; }
630 
631   // Adds symbols to the hash table.
632   // Sorts the input to satisfy GNU hash section requirements.
633   void addSymbols(std::vector<SymbolTableEntry> &symbols);
634 
635 private:
636   // See the comment in writeBloomFilter.
637   enum { Shift2 = 26 };
638 
639   void writeBloomFilter(uint8_t *buf);
640   void writeHashTable(uint8_t *buf);
641 
642   struct Entry {
643     Symbol *sym;
644     size_t strTabOffset;
645     uint32_t hash;
646     uint32_t bucketIdx;
647   };
648 
649   std::vector<Entry> symbols;
650   size_t maskWords;
651   size_t nBuckets = 0;
652   size_t size = 0;
653 };
654 
655 class HashTableSection final : public SyntheticSection {
656 public:
657   HashTableSection();
658   void finalizeContents() override;
659   void writeTo(uint8_t *buf) override;
660   size_t getSize() const override { return size; }
661 
662 private:
663   size_t size = 0;
664 };
665 
666 // Used for PLT entries. It usually has a PLT header for lazy binding. Each PLT
667 // entry is associated with a JUMP_SLOT relocation, which may be resolved lazily
668 // at runtime.
669 //
670 // On PowerPC, this section contains lazy symbol resolvers. A branch instruction
671 // jumps to a PLT call stub, which will then jump to the target (BIND_NOW) or a
672 // lazy symbol resolver.
673 //
674 // On x86 when IBT is enabled, this section (.plt.sec) contains PLT call stubs.
675 // A call instruction jumps to a .plt.sec entry, which will then jump to the
676 // target (BIND_NOW) or a .plt entry.
677 class PltSection : public SyntheticSection {
678 public:
679   PltSection();
680   void writeTo(uint8_t *buf) override;
681   size_t getSize() const override;
682   bool isNeeded() const override;
683   void addSymbols();
684   void addEntry(Symbol &sym);
685   size_t getNumEntries() const { return entries.size(); }
686 
687   size_t headerSize;
688 
689   std::vector<const Symbol *> entries;
690 };
691 
692 // Used for non-preemptible ifuncs. It does not have a header. Each entry is
693 // associated with an IRELATIVE relocation, which will be resolved eagerly at
694 // runtime. PltSection can only contain entries associated with JUMP_SLOT
695 // relocations, so IPLT entries are in a separate section.
696 class IpltSection final : public SyntheticSection {
697   std::vector<const Symbol *> entries;
698 
699 public:
700   IpltSection();
701   void writeTo(uint8_t *buf) override;
702   size_t getSize() const override;
703   bool isNeeded() const override { return !entries.empty(); }
704   void addSymbols();
705   void addEntry(Symbol &sym);
706 };
707 
708 class PPC32GlinkSection : public PltSection {
709 public:
710   PPC32GlinkSection();
711   void writeTo(uint8_t *buf) override;
712   size_t getSize() const override;
713 
714   std::vector<const Symbol *> canonical_plts;
715   static constexpr size_t footerSize = 64;
716 };
717 
718 // This is x86-only.
719 class IBTPltSection : public SyntheticSection {
720 public:
721   IBTPltSection();
722   void writeTo(uint8_t *Buf) override;
723   size_t getSize() const override;
724 };
725 
726 class GdbIndexSection final : public SyntheticSection {
727 public:
728   struct AddressEntry {
729     InputSection *section;
730     uint64_t lowAddress;
731     uint64_t highAddress;
732     uint32_t cuIndex;
733   };
734 
735   struct CuEntry {
736     uint64_t cuOffset;
737     uint64_t cuLength;
738   };
739 
740   struct NameAttrEntry {
741     llvm::CachedHashStringRef name;
742     uint32_t cuIndexAndAttrs;
743   };
744 
745   struct GdbChunk {
746     InputSection *sec;
747     std::vector<AddressEntry> addressAreas;
748     std::vector<CuEntry> compilationUnits;
749   };
750 
751   struct GdbSymbol {
752     llvm::CachedHashStringRef name;
753     std::vector<uint32_t> cuVector;
754     uint32_t nameOff;
755     uint32_t cuVectorOff;
756   };
757 
758   GdbIndexSection();
759   template <typename ELFT> static GdbIndexSection *create();
760   void writeTo(uint8_t *buf) override;
761   size_t getSize() const override { return size; }
762   bool isNeeded() const override;
763 
764 private:
765   struct GdbIndexHeader {
766     llvm::support::ulittle32_t version;
767     llvm::support::ulittle32_t cuListOff;
768     llvm::support::ulittle32_t cuTypesOff;
769     llvm::support::ulittle32_t addressAreaOff;
770     llvm::support::ulittle32_t symtabOff;
771     llvm::support::ulittle32_t constantPoolOff;
772   };
773 
774   void initOutputSize();
775   size_t computeSymtabSize() const;
776 
777   // Each chunk contains information gathered from debug sections of a
778   // single object file.
779   std::vector<GdbChunk> chunks;
780 
781   // A symbol table for this .gdb_index section.
782   std::vector<GdbSymbol> symbols;
783 
784   size_t size;
785 };
786 
787 // --eh-frame-hdr option tells linker to construct a header for all the
788 // .eh_frame sections. This header is placed to a section named .eh_frame_hdr
789 // and also to a PT_GNU_EH_FRAME segment.
790 // At runtime the unwinder then can find all the PT_GNU_EH_FRAME segments by
791 // calling dl_iterate_phdr.
792 // This section contains a lookup table for quick binary search of FDEs.
793 // Detailed info about internals can be found in Ian Lance Taylor's blog:
794 // http://www.airs.com/blog/archives/460 (".eh_frame")
795 // http://www.airs.com/blog/archives/462 (".eh_frame_hdr")
796 class EhFrameHeader final : public SyntheticSection {
797 public:
798   EhFrameHeader();
799   void write();
800   void writeTo(uint8_t *buf) override;
801   size_t getSize() const override;
802   bool isNeeded() const override;
803 };
804 
805 // For more information about .gnu.version and .gnu.version_r see:
806 // https://www.akkadia.org/drepper/symbol-versioning
807 
808 // The .gnu.version_d section which has a section type of SHT_GNU_verdef shall
809 // contain symbol version definitions. The number of entries in this section
810 // shall be contained in the DT_VERDEFNUM entry of the .dynamic section.
811 // The section shall contain an array of Elf_Verdef structures, optionally
812 // followed by an array of Elf_Verdaux structures.
813 class VersionDefinitionSection final : public SyntheticSection {
814 public:
815   VersionDefinitionSection();
816   void finalizeContents() override;
817   size_t getSize() const override;
818   void writeTo(uint8_t *buf) override;
819 
820 private:
821   enum { EntrySize = 28 };
822   void writeOne(uint8_t *buf, uint32_t index, StringRef name, size_t nameOff);
823   StringRef getFileDefName();
824 
825   unsigned fileDefNameOff;
826   std::vector<unsigned> verDefNameOffs;
827 };
828 
829 // The .gnu.version section specifies the required version of each symbol in the
830 // dynamic symbol table. It contains one Elf_Versym for each dynamic symbol
831 // table entry. An Elf_Versym is just a 16-bit integer that refers to a version
832 // identifier defined in the either .gnu.version_r or .gnu.version_d section.
833 // The values 0 and 1 are reserved. All other values are used for versions in
834 // the own object or in any of the dependencies.
835 class VersionTableSection final : public SyntheticSection {
836 public:
837   VersionTableSection();
838   void finalizeContents() override;
839   size_t getSize() const override;
840   void writeTo(uint8_t *buf) override;
841   bool isNeeded() const override;
842 };
843 
844 // The .gnu.version_r section defines the version identifiers used by
845 // .gnu.version. It contains a linked list of Elf_Verneed data structures. Each
846 // Elf_Verneed specifies the version requirements for a single DSO, and contains
847 // a reference to a linked list of Elf_Vernaux data structures which define the
848 // mapping from version identifiers to version names.
849 template <class ELFT>
850 class VersionNeedSection final : public SyntheticSection {
851   using Elf_Verneed = typename ELFT::Verneed;
852   using Elf_Vernaux = typename ELFT::Vernaux;
853 
854   struct Vernaux {
855     uint64_t hash;
856     uint32_t verneedIndex;
857     uint64_t nameStrTab;
858   };
859 
860   struct Verneed {
861     uint64_t nameStrTab;
862     std::vector<Vernaux> vernauxs;
863   };
864 
865   std::vector<Verneed> verneeds;
866 
867 public:
868   VersionNeedSection();
869   void finalizeContents() override;
870   void writeTo(uint8_t *buf) override;
871   size_t getSize() const override;
872   bool isNeeded() const override;
873 };
874 
875 // MergeSyntheticSection is a class that allows us to put mergeable sections
876 // with different attributes in a single output sections. To do that
877 // we put them into MergeSyntheticSection synthetic input sections which are
878 // attached to regular output sections.
879 class MergeSyntheticSection : public SyntheticSection {
880 public:
881   void addSection(MergeInputSection *ms);
882   std::vector<MergeInputSection *> sections;
883 
884 protected:
885   MergeSyntheticSection(StringRef name, uint32_t type, uint64_t flags,
886                         uint32_t alignment)
887       : SyntheticSection(flags, type, alignment, name) {}
888 };
889 
890 class MergeTailSection final : public MergeSyntheticSection {
891 public:
892   MergeTailSection(StringRef name, uint32_t type, uint64_t flags,
893                    uint32_t alignment);
894 
895   size_t getSize() const override;
896   void writeTo(uint8_t *buf) override;
897   void finalizeContents() override;
898 
899 private:
900   llvm::StringTableBuilder builder;
901 };
902 
903 class MergeNoTailSection final : public MergeSyntheticSection {
904 public:
905   MergeNoTailSection(StringRef name, uint32_t type, uint64_t flags,
906                      uint32_t alignment)
907       : MergeSyntheticSection(name, type, flags, alignment) {}
908 
909   size_t getSize() const override { return size; }
910   void writeTo(uint8_t *buf) override;
911   void finalizeContents() override;
912 
913 private:
914   // We use the most significant bits of a hash as a shard ID.
915   // The reason why we don't want to use the least significant bits is
916   // because DenseMap also uses lower bits to determine a bucket ID.
917   // If we use lower bits, it significantly increases the probability of
918   // hash collisons.
919   size_t getShardId(uint32_t hash) {
920     assert((hash >> 31) == 0);
921     return hash >> (31 - llvm::countTrailingZeros(numShards));
922   }
923 
924   // Section size
925   size_t size;
926 
927   // String table contents
928   constexpr static size_t numShards = 32;
929   std::vector<llvm::StringTableBuilder> shards;
930   size_t shardOffsets[numShards];
931 };
932 
933 // .MIPS.abiflags section.
934 template <class ELFT>
935 class MipsAbiFlagsSection final : public SyntheticSection {
936   using Elf_Mips_ABIFlags = llvm::object::Elf_Mips_ABIFlags<ELFT>;
937 
938 public:
939   static MipsAbiFlagsSection *create();
940 
941   MipsAbiFlagsSection(Elf_Mips_ABIFlags flags);
942   size_t getSize() const override { return sizeof(Elf_Mips_ABIFlags); }
943   void writeTo(uint8_t *buf) override;
944 
945 private:
946   Elf_Mips_ABIFlags flags;
947 };
948 
949 // .MIPS.options section.
950 template <class ELFT> class MipsOptionsSection final : public SyntheticSection {
951   using Elf_Mips_Options = llvm::object::Elf_Mips_Options<ELFT>;
952   using Elf_Mips_RegInfo = llvm::object::Elf_Mips_RegInfo<ELFT>;
953 
954 public:
955   static MipsOptionsSection *create();
956 
957   MipsOptionsSection(Elf_Mips_RegInfo reginfo);
958   void writeTo(uint8_t *buf) override;
959 
960   size_t getSize() const override {
961     return sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);
962   }
963 
964 private:
965   Elf_Mips_RegInfo reginfo;
966 };
967 
968 // MIPS .reginfo section.
969 template <class ELFT> class MipsReginfoSection final : public SyntheticSection {
970   using Elf_Mips_RegInfo = llvm::object::Elf_Mips_RegInfo<ELFT>;
971 
972 public:
973   static MipsReginfoSection *create();
974 
975   MipsReginfoSection(Elf_Mips_RegInfo reginfo);
976   size_t getSize() const override { return sizeof(Elf_Mips_RegInfo); }
977   void writeTo(uint8_t *buf) override;
978 
979 private:
980   Elf_Mips_RegInfo reginfo;
981 };
982 
983 // This is a MIPS specific section to hold a space within the data segment
984 // of executable file which is pointed to by the DT_MIPS_RLD_MAP entry.
985 // See "Dynamic section" in Chapter 5 in the following document:
986 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
987 class MipsRldMapSection : public SyntheticSection {
988 public:
989   MipsRldMapSection();
990   size_t getSize() const override { return config->wordsize; }
991   void writeTo(uint8_t *buf) override {}
992 };
993 
994 // Representation of the combined .ARM.Exidx input sections. We process these
995 // as a SyntheticSection like .eh_frame as we need to merge duplicate entries
996 // and add terminating sentinel entries.
997 //
998 // The .ARM.exidx input sections after SHF_LINK_ORDER processing is done form
999 // a table that the unwinder can derive (Addresses are encoded as offsets from
1000 // table):
1001 // | Address of function | Unwind instructions for function |
1002 // where the unwind instructions are either a small number of unwind or the
1003 // special EXIDX_CANTUNWIND entry representing no unwinding information.
1004 // When an exception is thrown from an address A, the unwinder searches the
1005 // table for the closest table entry with Address of function <= A. This means
1006 // that for two consecutive table entries:
1007 // | A1 | U1 |
1008 // | A2 | U2 |
1009 // The range of addresses described by U1 is [A1, A2)
1010 //
1011 // There are two cases where we need a linker generated table entry to fixup
1012 // the address ranges in the table
1013 // Case 1:
1014 // - A sentinel entry added with an address higher than all
1015 // executable sections. This was needed to work around libunwind bug pr31091.
1016 // - After address assignment we need to find the highest addressed executable
1017 // section and use the limit of that section so that the unwinder never
1018 // matches it.
1019 // Case 2:
1020 // - InputSections without a .ARM.exidx section (usually from Assembly)
1021 // need a table entry so that they terminate the range of the previously
1022 // function. This is pr40277.
1023 //
1024 // Instead of storing pointers to the .ARM.exidx InputSections from
1025 // InputObjects, we store pointers to the executable sections that need
1026 // .ARM.exidx sections. We can then use the dependentSections of these to
1027 // either find the .ARM.exidx section or know that we need to generate one.
1028 class ARMExidxSyntheticSection : public SyntheticSection {
1029 public:
1030   ARMExidxSyntheticSection();
1031 
1032   // Add an input section to the ARMExidxSyntheticSection. Returns whether the
1033   // section needs to be removed from the main input section list.
1034   bool addSection(InputSection *isec);
1035 
1036   size_t getSize() const override { return size; }
1037   void writeTo(uint8_t *buf) override;
1038   bool isNeeded() const override;
1039   // Sort and remove duplicate entries.
1040   void finalizeContents() override;
1041   InputSection *getLinkOrderDep() const;
1042 
1043   static bool classof(const SectionBase *d);
1044 
1045   // Links to the ARMExidxSections so we can transfer the relocations once the
1046   // layout is known.
1047   std::vector<InputSection *> exidxSections;
1048 
1049 private:
1050   size_t size = 0;
1051 
1052   // Instead of storing pointers to the .ARM.exidx InputSections from
1053   // InputObjects, we store pointers to the executable sections that need
1054   // .ARM.exidx sections. We can then use the dependentSections of these to
1055   // either find the .ARM.exidx section or know that we need to generate one.
1056   std::vector<InputSection *> executableSections;
1057 
1058   // The executable InputSection with the highest address to use for the
1059   // sentinel. We store separately from ExecutableSections as merging of
1060   // duplicate entries may mean this InputSection is removed from
1061   // ExecutableSections.
1062   InputSection *sentinel = nullptr;
1063 };
1064 
1065 // A container for one or more linker generated thunks. Instances of these
1066 // thunks including ARM interworking and Mips LA25 PI to non-PI thunks.
1067 class ThunkSection : public SyntheticSection {
1068 public:
1069   // ThunkSection in OS, with desired outSecOff of Off
1070   ThunkSection(OutputSection *os, uint64_t off);
1071 
1072   // Add a newly created Thunk to this container:
1073   // Thunk is given offset from start of this InputSection
1074   // Thunk defines a symbol in this InputSection that can be used as target
1075   // of a relocation
1076   void addThunk(Thunk *t);
1077   size_t getSize() const override;
1078   void writeTo(uint8_t *buf) override;
1079   InputSection *getTargetInputSection() const;
1080   bool assignOffsets();
1081 
1082   // When true, round up reported size of section to 4 KiB. See comment
1083   // in addThunkSection() for more details.
1084   bool roundUpSizeForErrata = false;
1085 
1086 private:
1087   std::vector<Thunk *> thunks;
1088   size_t size = 0;
1089 };
1090 
1091 // Used to compute outSecOff of .got2 in each object file. This is needed to
1092 // synthesize PLT entries for PPC32 Secure PLT ABI.
1093 class PPC32Got2Section final : public SyntheticSection {
1094 public:
1095   PPC32Got2Section();
1096   size_t getSize() const override { return 0; }
1097   bool isNeeded() const override;
1098   void finalizeContents() override;
1099   void writeTo(uint8_t *buf) override {}
1100 };
1101 
1102 // This section is used to store the addresses of functions that are called
1103 // in range-extending thunks on PowerPC64. When producing position dependent
1104 // code the addresses are link-time constants and the table is written out to
1105 // the binary. When producing position-dependent code the table is allocated and
1106 // filled in by the dynamic linker.
1107 class PPC64LongBranchTargetSection final : public SyntheticSection {
1108 public:
1109   PPC64LongBranchTargetSection();
1110   uint64_t getEntryVA(const Symbol *sym, int64_t addend);
1111   llvm::Optional<uint32_t> addEntry(const Symbol *sym, int64_t addend);
1112   size_t getSize() const override;
1113   void writeTo(uint8_t *buf) override;
1114   bool isNeeded() const override;
1115   void finalizeContents() override { finalized = true; }
1116 
1117 private:
1118   std::vector<std::pair<const Symbol *, int64_t>> entries;
1119   llvm::DenseMap<std::pair<const Symbol *, int64_t>, uint32_t> entry_index;
1120   bool finalized = false;
1121 };
1122 
1123 template <typename ELFT>
1124 class PartitionElfHeaderSection : public SyntheticSection {
1125 public:
1126   PartitionElfHeaderSection();
1127   size_t getSize() const override;
1128   void writeTo(uint8_t *buf) override;
1129 };
1130 
1131 template <typename ELFT>
1132 class PartitionProgramHeadersSection : public SyntheticSection {
1133 public:
1134   PartitionProgramHeadersSection();
1135   size_t getSize() const override;
1136   void writeTo(uint8_t *buf) override;
1137 };
1138 
1139 class PartitionIndexSection : public SyntheticSection {
1140 public:
1141   PartitionIndexSection();
1142   size_t getSize() const override;
1143   void finalizeContents() override;
1144   void writeTo(uint8_t *buf) override;
1145 };
1146 
1147 InputSection *createInterpSection();
1148 MergeInputSection *createCommentSection();
1149 MergeSyntheticSection *createMergeSynthetic(StringRef name, uint32_t type,
1150                                             uint64_t flags, uint32_t alignment);
1151 template <class ELFT> void splitSections();
1152 
1153 template <typename ELFT> void writeEhdr(uint8_t *buf, Partition &part);
1154 template <typename ELFT> void writePhdrs(uint8_t *buf, Partition &part);
1155 
1156 Defined *addSyntheticLocal(StringRef name, uint8_t type, uint64_t value,
1157                            uint64_t size, InputSectionBase &section);
1158 
1159 void addVerneed(Symbol *ss);
1160 
1161 // Linker generated per-partition sections.
1162 struct Partition {
1163   StringRef name;
1164   uint64_t nameStrTab;
1165 
1166   SyntheticSection *elfHeader;
1167   SyntheticSection *programHeaders;
1168   std::vector<PhdrEntry *> phdrs;
1169 
1170   ARMExidxSyntheticSection *armExidx;
1171   BuildIdSection *buildId;
1172   SyntheticSection *dynamic;
1173   StringTableSection *dynStrTab;
1174   SymbolTableBaseSection *dynSymTab;
1175   EhFrameHeader *ehFrameHdr;
1176   EhFrameSection *ehFrame;
1177   GnuHashTableSection *gnuHashTab;
1178   HashTableSection *hashTab;
1179   RelocationBaseSection *relaDyn;
1180   RelrBaseSection *relrDyn;
1181   VersionDefinitionSection *verDef;
1182   SyntheticSection *verNeed;
1183   VersionTableSection *verSym;
1184 
1185   unsigned getNumber() const { return this - &partitions[0] + 1; }
1186 };
1187 
1188 extern Partition *mainPart;
1189 
1190 inline Partition &SectionBase::getPartition() const {
1191   assert(isLive());
1192   return partitions[partition - 1];
1193 }
1194 
1195 // Linker generated sections which can be used as inputs and are not specific to
1196 // a partition.
1197 struct InStruct {
1198   InputSection *attributes;
1199   BssSection *bss;
1200   BssSection *bssRelRo;
1201   GotSection *got;
1202   GotPltSection *gotPlt;
1203   IgotPltSection *igotPlt;
1204   PPC64LongBranchTargetSection *ppc64LongBranchTarget;
1205   MipsGotSection *mipsGot;
1206   MipsRldMapSection *mipsRldMap;
1207   SyntheticSection *partEnd;
1208   SyntheticSection *partIndex;
1209   PltSection *plt;
1210   IpltSection *iplt;
1211   PPC32Got2Section *ppc32Got2;
1212   IBTPltSection *ibtPlt;
1213   RelocationBaseSection *relaPlt;
1214   RelocationBaseSection *relaIplt;
1215   StringTableSection *shStrTab;
1216   StringTableSection *strTab;
1217   SymbolTableBaseSection *symTab;
1218   SymtabShndxSection *symTabShndx;
1219 };
1220 
1221 extern InStruct in;
1222 
1223 } // namespace elf
1224 } // namespace lld
1225 
1226 #endif
1227