contrib/llvm-project/lld/ELF/SyntheticSections.h

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