contrib/llvm/tools/lld/ELF/SyntheticSections.h

   1 //===- SyntheticSection.h ---------------------------------------*- C++ -*-===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Synthetic sections represent chunks of linker-created data. If you
  11 // need to create a chunk of data that to be included in some section
  12 // in the result, you probably want to create that as a synthetic section.
  13 //
  14 // Synthetic sections are designed as input sections as opposed to
  15 // output sections because we want to allow them to be manipulated
  16 // using linker scripts just like other input sections from regular
  17 // files.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLD_ELF_SYNTHETIC_SECTION_H
  22 #define LLD_ELF_SYNTHETIC_SECTION_H
  23
  24 #include "EhFrame.h"
  25 #include "GdbIndex.h"
  26 #include "InputSection.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 class SharedSymbol;
  36
  37 class SyntheticSection : public InputSection {
  38 public:
  39   SyntheticSection(uint64_t Flags, uint32_t Type, uint32_t Alignment,
  40                    StringRef Name)
  41       : InputSection(nullptr, Flags, Type, Alignment, {}, Name,
  42                      InputSectionBase::Synthetic) {
  43     this->Live = true;
  44   }
  45
  46   virtual ~SyntheticSection() = default;
  47   virtual void writeTo(uint8_t *Buf) = 0;
  48   virtual size_t getSize() const = 0;
  49   virtual void finalizeContents() {}
  50   // If the section has the SHF_ALLOC flag and the size may be changed if
  51   // thunks are added, update the section size.
  52   virtual bool updateAllocSize() { return false; }
  53   // If any additional finalization of contents are needed post thunk creation.
  54   virtual void postThunkContents() {}
  55   virtual bool empty() const { return false; }
  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 empty() const override { return Sections.empty(); }
  74   size_t getSize() const override { return Size; }
  75
  76   template <class ELFT> void addSection(InputSectionBase *S);
  77
  78   std::vector<EhInputSection *> Sections;
  79   size_t NumFdes = 0;
  80
  81   struct FdeData {
  82     uint32_t PcRel;
  83     uint32_t FdeVARel;
  84   };
  85
  86   std::vector<FdeData> getFdeData() const;
  87   ArrayRef<CieRecord *> getCieRecords() const { return CieRecords; }
  88
  89 private:
  90   // This is used only when parsing EhInputSection. We keep it here to avoid
  91   // allocating one for each EhInputSection.
  92   llvm::DenseMap<size_t, CieRecord *> OffsetToCie;
  93
  94   uint64_t Size = 0;
  95
  96   template <class ELFT, class RelTy>
  97   void addSectionAux(EhInputSection *S, llvm::ArrayRef<RelTy> Rels);
  98
  99   template <class ELFT, class RelTy>
 100   CieRecord *addCie(EhSectionPiece &Piece, ArrayRef<RelTy> Rels);
 101
 102   template <class ELFT, class RelTy>
 103   bool isFdeLive(EhSectionPiece &Piece, ArrayRef<RelTy> Rels);
 104
 105   uint64_t getFdePc(uint8_t *Buf, size_t Off, uint8_t Enc) const;
 106
 107   std::vector<CieRecord *> CieRecords;
 108
 109   // CIE records are uniquified by their contents and personality functions.
 110   llvm::DenseMap<std::pair<ArrayRef<uint8_t>, Symbol *>, CieRecord *> CieMap;
 111 };
 112
 113 class GotSection : public SyntheticSection {
 114 public:
 115   GotSection();
 116   size_t getSize() const override { return Size; }
 117   void finalizeContents() override;
 118   bool empty() const override;
 119   void writeTo(uint8_t *Buf) override;
 120
 121   void addEntry(Symbol &Sym);
 122   bool addDynTlsEntry(Symbol &Sym);
 123   bool addTlsIndex();
 124   uint64_t getGlobalDynAddr(const Symbol &B) const;
 125   uint64_t getGlobalDynOffset(const Symbol &B) const;
 126
 127   uint64_t getTlsIndexVA() { return this->getVA() + TlsIndexOff; }
 128   uint32_t getTlsIndexOff() const { return TlsIndexOff; }
 129
 130   // Flag to force GOT to be in output if we have relocations
 131   // that relies on its address.
 132   bool HasGotOffRel = false;
 133
 134 protected:
 135   size_t NumEntries = 0;
 136   uint32_t TlsIndexOff = -1;
 137   uint64_t Size = 0;
 138 };
 139
 140 // .note.gnu.build-id section.
 141 class BuildIdSection : public SyntheticSection {
 142   // First 16 bytes are a header.
 143   static const unsigned HeaderSize = 16;
 144
 145 public:
 146   BuildIdSection();
 147   void writeTo(uint8_t *Buf) override;
 148   size_t getSize() const override { return HeaderSize + HashSize; }
 149   void writeBuildId(llvm::ArrayRef<uint8_t> Buf);
 150
 151 private:
 152   void computeHash(llvm::ArrayRef<uint8_t> Buf,
 153                    std::function<void(uint8_t *, ArrayRef<uint8_t>)> Hash);
 154
 155   size_t HashSize;
 156   uint8_t *HashBuf;
 157 };
 158
 159 // BssSection is used to reserve space for copy relocations and common symbols.
 160 // We create three instances of this class for .bss, .bss.rel.ro and "COMMON",
 161 // that are used for writable symbols, read-only symbols and common symbols,
 162 // respectively.
 163 class BssSection final : public SyntheticSection {
 164 public:
 165   BssSection(StringRef Name, uint64_t Size, uint32_t Alignment);
 166   void writeTo(uint8_t *) override {}
 167   bool empty() const override { return getSize() == 0; }
 168   size_t getSize() const override { return Size; }
 169
 170   static bool classof(const SectionBase *S) { return S->Bss; }
 171   uint64_t Size;
 172 };
 173
 174 class MipsGotSection final : public SyntheticSection {
 175 public:
 176   MipsGotSection();
 177   void writeTo(uint8_t *Buf) override;
 178   size_t getSize() const override { return Size; }
 179   bool updateAllocSize() override;
 180   void finalizeContents() override;
 181   bool empty() const override;
 182
 183   // Join separate GOTs built for each input file to generate
 184   // primary and optional multiple secondary GOTs.
 185   template <class ELFT> void build();
 186
 187   void addEntry(InputFile &File, Symbol &Sym, int64_t Addend, RelExpr Expr);
 188   void addDynTlsEntry(InputFile &File, Symbol &Sym);
 189   void addTlsIndex(InputFile &File);
 190
 191   uint64_t getPageEntryOffset(const InputFile *F, const Symbol &S,
 192                               int64_t Addend) const;
 193   uint64_t getSymEntryOffset(const InputFile *F, const Symbol &S,
 194                              int64_t Addend) const;
 195   uint64_t getGlobalDynOffset(const InputFile *F, const Symbol &S) const;
 196   uint64_t getTlsIndexOffset(const InputFile *F) const;
 197
 198   // Returns the symbol which corresponds to the first entry of the global part
 199   // of GOT on MIPS platform. It is required to fill up MIPS-specific dynamic
 200   // table properties.
 201   // Returns nullptr if the global part is empty.
 202   const Symbol *getFirstGlobalEntry() const;
 203
 204   // Returns the number of entries in the local part of GOT including
 205   // the number of reserved entries.
 206   unsigned getLocalEntriesNum() const;
 207
 208   // Return _gp value for primary GOT (nullptr) or particular input file.
 209   uint64_t getGp(const InputFile *F = nullptr) const;
 210
 211 private:
 212   // MIPS GOT consists of three parts: local, global and tls. Each part
 213   // contains different types of entries. Here is a layout of GOT:
 214   // - Header entries                |
 215   // - Page entries                  |   Local part
 216   // - Local entries (16-bit access) |
 217   // - Local entries (32-bit access) |
 218   // - Normal global entries         ||  Global part
 219   // - Reloc-only global entries     ||
 220   // - TLS entries                   ||| TLS part
 221   //
 222   // Header:
 223   //   Two entries hold predefined value 0x0 and 0x80000000.
 224   // Page entries:
 225   //   These entries created by R_MIPS_GOT_PAGE relocation and R_MIPS_GOT16
 226   //   relocation against local symbols. They are initialized by higher 16-bit
 227   //   of the corresponding symbol's value. So each 64kb of address space
 228   //   requires a single GOT entry.
 229   // Local entries (16-bit access):
 230   //   These entries created by GOT relocations against global non-preemptible
 231   //   symbols so dynamic linker is not necessary to resolve the symbol's
 232   //   values. "16-bit access" means that corresponding relocations address
 233   //   GOT using 16-bit index. Each unique Symbol-Addend pair has its own
 234   //   GOT entry.
 235   // Local entries (32-bit access):
 236   //   These entries are the same as above but created by relocations which
 237   //   address GOT using 32-bit index (R_MIPS_GOT_HI16/LO16 etc).
 238   // Normal global entries:
 239   //   These entries created by GOT relocations against preemptible global
 240   //   symbols. They need to be initialized by dynamic linker and they ordered
 241   //   exactly as the corresponding entries in the dynamic symbols table.
 242   // Reloc-only global entries:
 243   //   These entries created for symbols that are referenced by dynamic
 244   //   relocations R_MIPS_REL32. These entries are not accessed with gp-relative
 245   //   addressing, but MIPS ABI requires that these entries be present in GOT.
 246   // TLS entries:
 247   //   Entries created by TLS relocations.
 248   //
 249   // If the sum of local, global and tls entries is less than 64K only single
 250   // got is enough. Otherwise, multi-got is created. Series of primary and
 251   // multiple secondary GOTs have the following layout:
 252   // - Primary GOT
 253   //     Header
 254   //     Local entries
 255   //     Global entries
 256   //     Relocation only entries
 257   //     TLS entries
 258   //
 259   // - Secondary GOT
 260   //     Local entries
 261   //     Global entries
 262   //     TLS entries
 263   // ...
 264   //
 265   // All GOT entries required by relocations from a single input file entirely
 266   // belong to either primary or one of secondary GOTs. To reference GOT entries
 267   // each GOT has its own _gp value points to the "middle" of the GOT.
 268   // In the code this value loaded to the register which is used for GOT access.
 269   //
 270   // MIPS 32 function's prologue:
 271   //   lui     v0,0x0
 272   //   0: R_MIPS_HI16  _gp_disp
 273   //   addiu   v0,v0,0
 274   //   4: R_MIPS_LO16  _gp_disp
 275   //
 276   // MIPS 64:
 277   //   lui     at,0x0
 278   //   14: R_MIPS_GPREL16  main
 279   //
 280   // Dynamic linker does not know anything about secondary GOTs and cannot
 281   // use a regular MIPS mechanism for GOT entries initialization. So we have
 282   // to use an approach accepted by other architectures and create dynamic
 283   // relocations R_MIPS_REL32 to initialize global entries (and local in case
 284   // of PIC code) in secondary GOTs. But ironically MIPS dynamic linker
 285   // requires GOT entries and correspondingly ordered dynamic symbol table
 286   // entries to deal with dynamic relocations. To handle this problem
 287   // relocation-only section in the primary GOT contains entries for all
 288   // symbols referenced in global parts of secondary GOTs. Although the sum
 289   // of local and normal global entries of the primary got should be less
 290   // than 64K, the size of the primary got (including relocation-only entries
 291   // can be greater than 64K, because parts of the primary got that overflow
 292   // the 64K limit are used only by the dynamic linker at dynamic link-time
 293   // and not by 16-bit gp-relative addressing at run-time.
 294   //
 295   // For complete multi-GOT description see the following link
 296   // https://dmz-portal.mips.com/wiki/MIPS_Multi_GOT
 297
 298   // Number of "Header" entries.
 299   static const unsigned HeaderEntriesNum = 2;
 300
 301   uint64_t Size = 0;
 302
 303   size_t LocalEntriesNum = 0;
 304
 305   // Symbol and addend.
 306   typedef std::pair<Symbol *, int64_t> GotEntry;
 307
 308   struct FileGot {
 309     InputFile *File = nullptr;
 310     size_t StartIndex = 0;
 311
 312     struct PageBlock {
 313       size_t FirstIndex = 0;
 314       size_t Count = 0;
 315     };
 316
 317     // Map output sections referenced by MIPS GOT relocations
 318     // to the description (index/count) "page" entries allocated
 319     // for this section.
 320     llvm::SmallMapVector<const OutputSection *, PageBlock, 16> PagesMap;
 321     // Maps from Symbol+Addend pair or just Symbol to the GOT entry index.
 322     llvm::MapVector<GotEntry, size_t> Local16;
 323     llvm::MapVector<GotEntry, size_t> Local32;
 324     llvm::MapVector<Symbol *, size_t> Global;
 325     llvm::MapVector<Symbol *, size_t> Relocs;
 326     llvm::MapVector<Symbol *, size_t> Tls;
 327     // Set of symbols referenced by dynamic TLS relocations.
 328     llvm::MapVector<Symbol *, size_t> DynTlsSymbols;
 329
 330     // Total number of all entries.
 331     size_t getEntriesNum() const;
 332     // Number of "page" entries.
 333     size_t getPageEntriesNum() const;
 334     // Number of entries require 16-bit index to access.
 335     size_t getIndexedEntriesNum() const;
 336
 337     bool isOverflow() const;
 338   };
 339
 340   // Container of GOT created for each input file.
 341   // After building a final series of GOTs this container
 342   // holds primary and secondary GOT's.
 343   std::vector<FileGot> Gots;
 344
 345   // Return (and create if necessary) `FileGot`.
 346   FileGot &getGot(InputFile &F);
 347
 348   // Try to merge two GOTs. In case of success the `Dst` contains
 349   // result of merging and the function returns true. In case of
 350   // ovwerflow the `Dst` is unchanged and the function returns false.
 351   bool tryMergeGots(FileGot & Dst, FileGot & Src, bool IsPrimary);
 352 };
 353
 354 class GotPltSection final : public SyntheticSection {
 355 public:
 356   GotPltSection();
 357   void addEntry(Symbol &Sym);
 358   size_t getSize() const override;
 359   void writeTo(uint8_t *Buf) override;
 360   bool empty() const override;
 361
 362 private:
 363   std::vector<const Symbol *> Entries;
 364 };
 365
 366 // The IgotPltSection is a Got associated with the PltSection for GNU Ifunc
 367 // Symbols that will be relocated by Target->IRelativeRel.
 368 // On most Targets the IgotPltSection will immediately follow the GotPltSection
 369 // on ARM the IgotPltSection will immediately follow the GotSection.
 370 class IgotPltSection final : public SyntheticSection {
 371 public:
 372   IgotPltSection();
 373   void addEntry(Symbol &Sym);
 374   size_t getSize() const override;
 375   void writeTo(uint8_t *Buf) override;
 376   bool empty() const override { return Entries.empty(); }
 377
 378 private:
 379   std::vector<const Symbol *> Entries;
 380 };
 381
 382 class StringTableSection final : public SyntheticSection {
 383 public:
 384   StringTableSection(StringRef Name, bool Dynamic);
 385   unsigned addString(StringRef S, bool HashIt = true);
 386   void writeTo(uint8_t *Buf) override;
 387   size_t getSize() const override { return Size; }
 388   bool isDynamic() const { return Dynamic; }
 389
 390 private:
 391   const bool Dynamic;
 392
 393   uint64_t Size = 0;
 394
 395   llvm::DenseMap<StringRef, unsigned> StringMap;
 396   std::vector<StringRef> Strings;
 397 };
 398
 399 class DynamicReloc {
 400 public:
 401   DynamicReloc(RelType Type, const InputSectionBase *InputSec,
 402                uint64_t OffsetInSec, bool UseSymVA, Symbol *Sym, int64_t Addend)
 403       : Type(Type), Sym(Sym), InputSec(InputSec), OffsetInSec(OffsetInSec),
 404         UseSymVA(UseSymVA), Addend(Addend), OutputSec(nullptr) {}
 405   // This constructor records dynamic relocation settings used by MIPS
 406   // multi-GOT implementation. It's to relocate addresses of 64kb pages
 407   // lie inside the output section.
 408   DynamicReloc(RelType Type, const InputSectionBase *InputSec,
 409                uint64_t OffsetInSec, const OutputSection *OutputSec,
 410                int64_t Addend)
 411       : Type(Type), Sym(nullptr), InputSec(InputSec), OffsetInSec(OffsetInSec),
 412         UseSymVA(false), Addend(Addend), OutputSec(OutputSec) {}
 413
 414   uint64_t getOffset() const;
 415   uint32_t getSymIndex() const;
 416   const InputSectionBase *getInputSec() const { return InputSec; }
 417
 418   // Computes the addend of the dynamic relocation. Note that this is not the
 419   // same as the Addend member variable as it also includes the symbol address
 420   // if UseSymVA is true.
 421   int64_t computeAddend() const;
 422
 423   RelType Type;
 424
 425 private:
 426   Symbol *Sym;
 427   const InputSectionBase *InputSec = nullptr;
 428   uint64_t OffsetInSec;
 429   // If this member is true, the dynamic relocation will not be against the
 430   // symbol but will instead be a relative relocation that simply adds the
 431   // load address. This means we need to write the symbol virtual address
 432   // plus the original addend as the final relocation addend.
 433   bool UseSymVA;
 434   int64_t Addend;
 435   const OutputSection *OutputSec;
 436 };
 437
 438 template <class ELFT> class DynamicSection final : public SyntheticSection {
 439   typedef typename ELFT::Dyn Elf_Dyn;
 440   typedef typename ELFT::Rel Elf_Rel;
 441   typedef typename ELFT::Rela Elf_Rela;
 442   typedef typename ELFT::Relr Elf_Relr;
 443   typedef typename ELFT::Shdr Elf_Shdr;
 444   typedef typename ELFT::Sym Elf_Sym;
 445
 446   // finalizeContents() fills this vector with the section contents.
 447   std::vector<std::pair<int32_t, std::function<uint64_t()>>> Entries;
 448
 449 public:
 450   DynamicSection();
 451   void finalizeContents() override;
 452   void writeTo(uint8_t *Buf) override;
 453   size_t getSize() const override { return Size; }
 454
 455 private:
 456   void add(int32_t Tag, std::function<uint64_t()> Fn);
 457   void addInt(int32_t Tag, uint64_t Val);
 458   void addInSec(int32_t Tag, InputSection *Sec);
 459   void addInSecRelative(int32_t Tag, InputSection *Sec);
 460   void addOutSec(int32_t Tag, OutputSection *Sec);
 461   void addSize(int32_t Tag, OutputSection *Sec);
 462   void addSym(int32_t Tag, Symbol *Sym);
 463
 464   uint64_t Size = 0;
 465 };
 466
 467 class RelocationBaseSection : public SyntheticSection {
 468 public:
 469   RelocationBaseSection(StringRef Name, uint32_t Type, int32_t DynamicTag,
 470                         int32_t SizeDynamicTag);
 471   void addReloc(RelType DynType, InputSectionBase *IS, uint64_t OffsetInSec,
 472                 Symbol *Sym);
 473   // Add a dynamic relocation that might need an addend. This takes care of
 474   // writing the addend to the output section if needed.
 475   void addReloc(RelType DynType, InputSectionBase *InputSec,
 476                 uint64_t OffsetInSec, Symbol *Sym, int64_t Addend, RelExpr Expr,
 477                 RelType Type);
 478   void addReloc(const DynamicReloc &Reloc);
 479   bool empty() const override { return Relocs.empty(); }
 480   size_t getSize() const override { return Relocs.size() * this->Entsize; }
 481   size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
 482   void finalizeContents() override;
 483   int32_t DynamicTag, SizeDynamicTag;
 484
 485 protected:
 486   std::vector<DynamicReloc> Relocs;
 487   size_t NumRelativeRelocs = 0;
 488 };
 489
 490 template <class ELFT>
 491 class RelocationSection final : public RelocationBaseSection {
 492   typedef typename ELFT::Rel Elf_Rel;
 493   typedef typename ELFT::Rela Elf_Rela;
 494
 495 public:
 496   RelocationSection(StringRef Name, bool Sort);
 497   unsigned getRelocOffset();
 498   void writeTo(uint8_t *Buf) override;
 499
 500 private:
 501   bool Sort;
 502 };
 503
 504 template <class ELFT>
 505 class AndroidPackedRelocationSection final : public RelocationBaseSection {
 506   typedef typename ELFT::Rel Elf_Rel;
 507   typedef typename ELFT::Rela Elf_Rela;
 508
 509 public:
 510   AndroidPackedRelocationSection(StringRef Name);
 511
 512   bool updateAllocSize() override;
 513   size_t getSize() const override { return RelocData.size(); }
 514   void writeTo(uint8_t *Buf) override {
 515     memcpy(Buf, RelocData.data(), RelocData.size());
 516   }
 517
 518 private:
 519   SmallVector<char, 0> RelocData;
 520 };
 521
 522 struct RelativeReloc {
 523   uint64_t getOffset() const { return InputSec->getVA(OffsetInSec); }
 524
 525   const InputSectionBase *InputSec;
 526   uint64_t OffsetInSec;
 527 };
 528
 529 class RelrBaseSection : public SyntheticSection {
 530 public:
 531   RelrBaseSection();
 532   std::vector<RelativeReloc> Relocs;
 533 };
 534
 535 // RelrSection is used to encode offsets for relative relocations.
 536 // Proposal for adding SHT_RELR sections to generic-abi is here:
 537 //   https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg
 538 // For more details, see the comment in RelrSection::updateAllocSize().
 539 template <class ELFT> class RelrSection final : public RelrBaseSection {
 540   typedef typename ELFT::Relr Elf_Relr;
 541
 542 public:
 543   RelrSection();
 544
 545   bool updateAllocSize() override;
 546   size_t getSize() const override { return RelrRelocs.size() * this->Entsize; }
 547   void writeTo(uint8_t *Buf) override {
 548     memcpy(Buf, RelrRelocs.data(), getSize());
 549   }
 550
 551 private:
 552   std::vector<Elf_Relr> RelrRelocs;
 553 };
 554
 555 struct SymbolTableEntry {
 556   Symbol *Sym;
 557   size_t StrTabOffset;
 558 };
 559
 560 class SymbolTableBaseSection : public SyntheticSection {
 561 public:
 562   SymbolTableBaseSection(StringTableSection &StrTabSec);
 563   void finalizeContents() override;
 564   void postThunkContents() override;
 565   size_t getSize() const override { return getNumSymbols() * Entsize; }
 566   void addSymbol(Symbol *Sym);
 567   unsigned getNumSymbols() const { return Symbols.size() + 1; }
 568   size_t getSymbolIndex(Symbol *Sym);
 569   ArrayRef<SymbolTableEntry> getSymbols() const { return Symbols; }
 570
 571 protected:
 572   // A vector of symbols and their string table offsets.
 573   std::vector<SymbolTableEntry> Symbols;
 574
 575   StringTableSection &StrTabSec;
 576
 577   llvm::once_flag OnceFlag;
 578   llvm::DenseMap<Symbol *, size_t> SymbolIndexMap;
 579   llvm::DenseMap<OutputSection *, size_t> SectionIndexMap;
 580 };
 581
 582 template <class ELFT>
 583 class SymbolTableSection final : public SymbolTableBaseSection {
 584   typedef typename ELFT::Sym Elf_Sym;
 585
 586 public:
 587   SymbolTableSection(StringTableSection &StrTabSec);
 588   void writeTo(uint8_t *Buf) override;
 589 };
 590
 591 // Outputs GNU Hash section. For detailed explanation see:
 592 // https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
 593 class GnuHashTableSection final : public SyntheticSection {
 594 public:
 595   GnuHashTableSection();
 596   void finalizeContents() override;
 597   void writeTo(uint8_t *Buf) override;
 598   size_t getSize() const override { return Size; }
 599
 600   // Adds symbols to the hash table.
 601   // Sorts the input to satisfy GNU hash section requirements.
 602   void addSymbols(std::vector<SymbolTableEntry> &Symbols);
 603
 604 private:
 605   enum { Shift2 = 6 };
 606
 607   void writeBloomFilter(uint8_t *Buf);
 608   void writeHashTable(uint8_t *Buf);
 609
 610   struct Entry {
 611     Symbol *Sym;
 612     size_t StrTabOffset;
 613     uint32_t Hash;
 614     uint32_t BucketIdx;
 615   };
 616
 617   std::vector<Entry> Symbols;
 618   size_t MaskWords;
 619   size_t NBuckets = 0;
 620   size_t Size = 0;
 621 };
 622
 623 class HashTableSection final : public SyntheticSection {
 624 public:
 625   HashTableSection();
 626   void finalizeContents() override;
 627   void writeTo(uint8_t *Buf) override;
 628   size_t getSize() const override { return Size; }
 629
 630 private:
 631   size_t Size = 0;
 632 };
 633
 634 // The PltSection is used for both the Plt and Iplt. The former usually has a
 635 // header as its first entry that is used at run-time to resolve lazy binding.
 636 // The latter is used for GNU Ifunc symbols, that will be subject to a
 637 // Target->IRelativeRel.
 638 class PltSection : public SyntheticSection {
 639 public:
 640   PltSection(bool IsIplt);
 641   void writeTo(uint8_t *Buf) override;
 642   size_t getSize() const override;
 643   bool empty() const override { return Entries.empty(); }
 644   void addSymbols();
 645
 646   template <class ELFT> void addEntry(Symbol &Sym);
 647
 648 private:
 649   unsigned getPltRelocOff() const;
 650   std::vector<std::pair<const Symbol *, unsigned>> Entries;
 651   size_t HeaderSize;
 652   bool IsIplt;
 653 };
 654
 655 class GdbIndexSection final : public SyntheticSection {
 656 public:
 657   struct AddressEntry {
 658     InputSection *Section;
 659     uint64_t LowAddress;
 660     uint64_t HighAddress;
 661     uint32_t CuIndex;
 662   };
 663
 664   struct CuEntry {
 665     uint64_t CuOffset;
 666     uint64_t CuLength;
 667   };
 668
 669   struct NameTypeEntry {
 670     llvm::CachedHashStringRef Name;
 671     uint32_t Type;
 672   };
 673
 674   struct GdbChunk {
 675     InputSection *Sec;
 676     std::vector<AddressEntry> AddressAreas;
 677     std::vector<CuEntry> CompilationUnits;
 678   };
 679
 680   struct GdbSymbol {
 681     llvm::CachedHashStringRef Name;
 682     std::vector<uint32_t> CuVector;
 683     uint32_t NameOff;
 684     uint32_t CuVectorOff;
 685   };
 686
 687   GdbIndexSection();
 688   template <typename ELFT> static GdbIndexSection *create();
 689   void writeTo(uint8_t *Buf) override;
 690   size_t getSize() const override { return Size; }
 691   bool empty() const override;
 692
 693 private:
 694   struct GdbIndexHeader {
 695     llvm::support::ulittle32_t Version;
 696     llvm::support::ulittle32_t CuListOff;
 697     llvm::support::ulittle32_t CuTypesOff;
 698     llvm::support::ulittle32_t AddressAreaOff;
 699     llvm::support::ulittle32_t SymtabOff;
 700     llvm::support::ulittle32_t ConstantPoolOff;
 701   };
 702
 703   void initOutputSize();
 704   size_t computeSymtabSize() const;
 705
 706   // Each chunk contains information gathered from debug sections of a
 707   // single object file.
 708   std::vector<GdbChunk> Chunks;
 709
 710   // A symbol table for this .gdb_index section.
 711   std::vector<GdbSymbol> Symbols;
 712
 713   size_t Size;
 714 };
 715
 716 // --eh-frame-hdr option tells linker to construct a header for all the
 717 // .eh_frame sections. This header is placed to a section named .eh_frame_hdr
 718 // and also to a PT_GNU_EH_FRAME segment.
 719 // At runtime the unwinder then can find all the PT_GNU_EH_FRAME segments by
 720 // calling dl_iterate_phdr.
 721 // This section contains a lookup table for quick binary search of FDEs.
 722 // Detailed info about internals can be found in Ian Lance Taylor's blog:
 723 // http://www.airs.com/blog/archives/460 (".eh_frame")
 724 // http://www.airs.com/blog/archives/462 (".eh_frame_hdr")
 725 class EhFrameHeader final : public SyntheticSection {
 726 public:
 727   EhFrameHeader();
 728   void writeTo(uint8_t *Buf) override;
 729   size_t getSize() const override;
 730   bool empty() const override;
 731 };
 732
 733 // For more information about .gnu.version and .gnu.version_r see:
 734 // https://www.akkadia.org/drepper/symbol-versioning
 735
 736 // The .gnu.version_d section which has a section type of SHT_GNU_verdef shall
 737 // contain symbol version definitions. The number of entries in this section
 738 // shall be contained in the DT_VERDEFNUM entry of the .dynamic section.
 739 // The section shall contain an array of Elf_Verdef structures, optionally
 740 // followed by an array of Elf_Verdaux structures.
 741 template <class ELFT>
 742 class VersionDefinitionSection final : public SyntheticSection {
 743   typedef typename ELFT::Verdef Elf_Verdef;
 744   typedef typename ELFT::Verdaux Elf_Verdaux;
 745
 746 public:
 747   VersionDefinitionSection();
 748   void finalizeContents() override;
 749   size_t getSize() const override;
 750   void writeTo(uint8_t *Buf) override;
 751
 752 private:
 753   void writeOne(uint8_t *Buf, uint32_t Index, StringRef Name, size_t NameOff);
 754
 755   unsigned FileDefNameOff;
 756 };
 757
 758 // The .gnu.version section specifies the required version of each symbol in the
 759 // dynamic symbol table. It contains one Elf_Versym for each dynamic symbol
 760 // table entry. An Elf_Versym is just a 16-bit integer that refers to a version
 761 // identifier defined in the either .gnu.version_r or .gnu.version_d section.
 762 // The values 0 and 1 are reserved. All other values are used for versions in
 763 // the own object or in any of the dependencies.
 764 template <class ELFT>
 765 class VersionTableSection final : public SyntheticSection {
 766   typedef typename ELFT::Versym Elf_Versym;
 767
 768 public:
 769   VersionTableSection();
 770   void finalizeContents() override;
 771   size_t getSize() const override;
 772   void writeTo(uint8_t *Buf) override;
 773   bool empty() const override;
 774 };
 775
 776 // The .gnu.version_r section defines the version identifiers used by
 777 // .gnu.version. It contains a linked list of Elf_Verneed data structures. Each
 778 // Elf_Verneed specifies the version requirements for a single DSO, and contains
 779 // a reference to a linked list of Elf_Vernaux data structures which define the
 780 // mapping from version identifiers to version names.
 781 template <class ELFT> class VersionNeedSection final : public SyntheticSection {
 782   typedef typename ELFT::Verneed Elf_Verneed;
 783   typedef typename ELFT::Vernaux Elf_Vernaux;
 784
 785   // A vector of shared files that need Elf_Verneed data structures and the
 786   // string table offsets of their sonames.
 787   std::vector<std::pair<SharedFile<ELFT> *, size_t>> Needed;
 788
 789   // The next available version identifier.
 790   unsigned NextIndex;
 791
 792 public:
 793   VersionNeedSection();
 794   void addSymbol(Symbol *Sym);
 795   void finalizeContents() override;
 796   void writeTo(uint8_t *Buf) override;
 797   size_t getSize() const override;
 798   size_t getNeedNum() const { return Needed.size(); }
 799   bool empty() const override;
 800 };
 801
 802 // MergeSyntheticSection is a class that allows us to put mergeable sections
 803 // with different attributes in a single output sections. To do that
 804 // we put them into MergeSyntheticSection synthetic input sections which are
 805 // attached to regular output sections.
 806 class MergeSyntheticSection : public SyntheticSection {
 807 public:
 808   void addSection(MergeInputSection *MS);
 809   std::vector<MergeInputSection *> Sections;
 810
 811 protected:
 812   MergeSyntheticSection(StringRef Name, uint32_t Type, uint64_t Flags,
 813                         uint32_t Alignment)
 814       : SyntheticSection(Flags, Type, Alignment, Name) {}
 815 };
 816
 817 class MergeTailSection final : public MergeSyntheticSection {
 818 public:
 819   MergeTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
 820                    uint32_t Alignment);
 821
 822   size_t getSize() const override;
 823   void writeTo(uint8_t *Buf) override;
 824   void finalizeContents() override;
 825
 826 private:
 827   llvm::StringTableBuilder Builder;
 828 };
 829
 830 class MergeNoTailSection final : public MergeSyntheticSection {
 831 public:
 832   MergeNoTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
 833                      uint32_t Alignment)
 834       : MergeSyntheticSection(Name, Type, Flags, Alignment) {}
 835
 836   size_t getSize() const override { return Size; }
 837   void writeTo(uint8_t *Buf) override;
 838   void finalizeContents() override;
 839
 840 private:
 841   // We use the most significant bits of a hash as a shard ID.
 842   // The reason why we don't want to use the least significant bits is
 843   // because DenseMap also uses lower bits to determine a bucket ID.
 844   // If we use lower bits, it significantly increases the probability of
 845   // hash collisons.
 846   size_t getShardId(uint32_t Hash) {
 847     return Hash >> (32 - llvm::countTrailingZeros(NumShards));
 848   }
 849
 850   // Section size
 851   size_t Size;
 852
 853   // String table contents
 854   constexpr static size_t NumShards = 32;
 855   std::vector<llvm::StringTableBuilder> Shards;
 856   size_t ShardOffsets[NumShards];
 857 };
 858
 859 // .MIPS.abiflags section.
 860 template <class ELFT>
 861 class MipsAbiFlagsSection final : public SyntheticSection {
 862   typedef llvm::object::Elf_Mips_ABIFlags<ELFT> Elf_Mips_ABIFlags;
 863
 864 public:
 865   static MipsAbiFlagsSection *create();
 866
 867   MipsAbiFlagsSection(Elf_Mips_ABIFlags Flags);
 868   size_t getSize() const override { return sizeof(Elf_Mips_ABIFlags); }
 869   void writeTo(uint8_t *Buf) override;
 870
 871 private:
 872   Elf_Mips_ABIFlags Flags;
 873 };
 874
 875 // .MIPS.options section.
 876 template <class ELFT> class MipsOptionsSection final : public SyntheticSection {
 877   typedef llvm::object::Elf_Mips_Options<ELFT> Elf_Mips_Options;
 878   typedef llvm::object::Elf_Mips_RegInfo<ELFT> Elf_Mips_RegInfo;
 879
 880 public:
 881   static MipsOptionsSection *create();
 882
 883   MipsOptionsSection(Elf_Mips_RegInfo Reginfo);
 884   void writeTo(uint8_t *Buf) override;
 885
 886   size_t getSize() const override {
 887     return sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);
 888   }
 889
 890 private:
 891   Elf_Mips_RegInfo Reginfo;
 892 };
 893
 894 // MIPS .reginfo section.
 895 template <class ELFT> class MipsReginfoSection final : public SyntheticSection {
 896   typedef llvm::object::Elf_Mips_RegInfo<ELFT> Elf_Mips_RegInfo;
 897
 898 public:
 899   static MipsReginfoSection *create();
 900
 901   MipsReginfoSection(Elf_Mips_RegInfo Reginfo);
 902   size_t getSize() const override { return sizeof(Elf_Mips_RegInfo); }
 903   void writeTo(uint8_t *Buf) override;
 904
 905 private:
 906   Elf_Mips_RegInfo Reginfo;
 907 };
 908
 909 // This is a MIPS specific section to hold a space within the data segment
 910 // of executable file which is pointed to by the DT_MIPS_RLD_MAP entry.
 911 // See "Dynamic section" in Chapter 5 in the following document:
 912 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 913 class MipsRldMapSection : public SyntheticSection {
 914 public:
 915   MipsRldMapSection();
 916   size_t getSize() const override { return Config->Wordsize; }
 917   void writeTo(uint8_t *Buf) override {}
 918 };
 919
 920 class ARMExidxSentinelSection : public SyntheticSection {
 921 public:
 922   ARMExidxSentinelSection();
 923   size_t getSize() const override { return 8; }
 924   void writeTo(uint8_t *Buf) override;
 925   bool empty() const override;
 926
 927   static bool classof(const SectionBase *D);
 928
 929   // The last section referenced by a regular .ARM.exidx section.
 930   // It is found and filled in Writer<ELFT>::resolveShfLinkOrder().
 931   // The sentinel points at the end of that section.
 932   InputSection *Highest = nullptr;
 933 };
 934
 935 // A container for one or more linker generated thunks. Instances of these
 936 // thunks including ARM interworking and Mips LA25 PI to non-PI thunks.
 937 class ThunkSection : public SyntheticSection {
 938 public:
 939   // ThunkSection in OS, with desired OutSecOff of Off
 940   ThunkSection(OutputSection *OS, uint64_t Off);
 941
 942   // Add a newly created Thunk to this container:
 943   // Thunk is given offset from start of this InputSection
 944   // Thunk defines a symbol in this InputSection that can be used as target
 945   // of a relocation
 946   void addThunk(Thunk *T);
 947   size_t getSize() const override { return Size; }
 948   void writeTo(uint8_t *Buf) override;
 949   InputSection *getTargetInputSection() const;
 950   bool assignOffsets();
 951
 952 private:
 953   std::vector<Thunk *> Thunks;
 954   size_t Size = 0;
 955 };
 956
 957 InputSection *createInterpSection();
 958 MergeInputSection *createCommentSection();
 959 void decompressSections();
 960 template <class ELFT> void splitSections();
 961 void mergeSections();
 962
 963 Defined *addSyntheticLocal(StringRef Name, uint8_t Type, uint64_t Value,
 964                            uint64_t Size, InputSectionBase &Section);
 965
 966 // Linker generated sections which can be used as inputs.
 967 struct InX {
 968   static InputSection *ARMAttributes;
 969   static BssSection *Bss;
 970   static BssSection *BssRelRo;
 971   static BuildIdSection *BuildId;
 972   static EhFrameHeader *EhFrameHdr;
 973   static EhFrameSection *EhFrame;
 974   static SyntheticSection *Dynamic;
 975   static StringTableSection *DynStrTab;
 976   static SymbolTableBaseSection *DynSymTab;
 977   static GnuHashTableSection *GnuHashTab;
 978   static HashTableSection *HashTab;
 979   static InputSection *Interp;
 980   static GdbIndexSection *GdbIndex;
 981   static GotSection *Got;
 982   static GotPltSection *GotPlt;
 983   static IgotPltSection *IgotPlt;
 984   static MipsGotSection *MipsGot;
 985   static MipsRldMapSection *MipsRldMap;
 986   static PltSection *Plt;
 987   static PltSection *Iplt;
 988   static RelocationBaseSection *RelaDyn;
 989   static RelrBaseSection *RelrDyn;
 990   static RelocationBaseSection *RelaPlt;
 991   static RelocationBaseSection *RelaIplt;
 992   static StringTableSection *ShStrTab;
 993   static StringTableSection *StrTab;
 994   static SymbolTableBaseSection *SymTab;
 995 };
 996
 997 template <class ELFT> struct In {
 998   static VersionDefinitionSection<ELFT> *VerDef;
 999   static VersionTableSection<ELFT> *VerSym;
1000   static VersionNeedSection<ELFT> *VerNeed;
1001 };
1002
1003 template <class ELFT> VersionDefinitionSection<ELFT> *In<ELFT>::VerDef;
1004 template <class ELFT> VersionTableSection<ELFT> *In<ELFT>::VerSym;
1005 template <class ELFT> VersionNeedSection<ELFT> *In<ELFT>::VerNeed;
1006 } // namespace elf
1007 } // namespace lld
1008
1009 #endif