lib/ReaderWriter/ELF/ELFFile.h

   1 //===- lib/ReaderWriter/ELF/ELFFile.h -------------------------------------===//
   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 #ifndef LLD_READER_WRITER_ELF_FILE_H
  11 #define LLD_READER_WRITER_ELF_FILE_H
  12
  13 #include "Atoms.h"
  14 #include <llvm/ADT/MapVector.h>
  15 #include <map>
  16 #include <unordered_map>
  17
  18 namespace lld {
  19
  20 namespace elf {
  21 /// \brief Read a binary, find out based on the symbol table contents what kind
  22 /// of symbol it is and create corresponding atoms for it
  23 template <class ELFT> class ELFFile : public File {
  24
  25   typedef llvm::object::Elf_Sym_Impl<ELFT> Elf_Sym;
  26   typedef llvm::object::Elf_Shdr_Impl<ELFT> Elf_Shdr;
  27   typedef llvm::object::Elf_Rel_Impl<ELFT, false> Elf_Rel;
  28   typedef llvm::object::Elf_Rel_Impl<ELFT, true> Elf_Rela;
  29   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym_Iter Elf_Sym_Iter;
  30   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela_Iter Elf_Rela_Iter;
  31   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel_Iter Elf_Rel_Iter;
  32   typedef typename llvm::object::ELFFile<ELFT>::Elf_Word Elf_Word;
  33
  34   // A Map is used to hold the atoms that have been divided up
  35   // after reading the section that contains Merge String attributes
  36   struct MergeSectionKey {
  37     MergeSectionKey(const Elf_Shdr *shdr, int64_t offset)
  38         : _shdr(shdr), _offset(offset) {}
  39     // Data members
  40     const Elf_Shdr *_shdr;
  41     int64_t _offset;
  42   };
  43   struct MergeSectionEq {
  44     int64_t operator()(const MergeSectionKey &k) const {
  45       return llvm::hash_combine((int64_t)(k._shdr->sh_name),
  46                                 (int64_t)k._offset);
  47     }
  48     bool operator()(const MergeSectionKey &lhs,
  49                     const MergeSectionKey &rhs) const {
  50       return ((lhs._shdr->sh_name == rhs._shdr->sh_name) &&
  51               (lhs._offset == rhs._offset));
  52     }
  53   };
  54
  55   struct MergeString {
  56     MergeString(int64_t offset, StringRef str, const Elf_Shdr *shdr,
  57                 StringRef sectionName)
  58         : _offset(offset), _string(str), _shdr(shdr),
  59           _sectionName(sectionName) {}
  60     // the offset of this atom
  61     int64_t _offset;
  62     // The content
  63     StringRef _string;
  64     // Section header
  65     const Elf_Shdr *_shdr;
  66     // Section name
  67     StringRef _sectionName;
  68   };
  69
  70   // This is used to find the MergeAtom given a relocation
  71   // offset
  72   typedef std::vector<ELFMergeAtom<ELFT> *> MergeAtomsT;
  73
  74   /// \brief find a mergeAtom given a start offset
  75   struct FindByOffset {
  76     const Elf_Shdr *_shdr;
  77     int64_t _offset;
  78     FindByOffset(const Elf_Shdr *shdr, int64_t offset)
  79         : _shdr(shdr), _offset(offset) {}
  80     bool operator()(const ELFMergeAtom<ELFT> *a) {
  81       int64_t off = a->offset();
  82       return (_shdr->sh_name == a->section()) &&
  83              ((_offset >= off) && (_offset <= off + (int64_t)a->size()));
  84     }
  85   };
  86
  87   /// \brief find a merge atom given a offset
  88   ELFMergeAtom<ELFT> *findMergeAtom(const Elf_Shdr *shdr, uint64_t offset) {
  89     auto it = std::find_if(_mergeAtoms.begin(), _mergeAtoms.end(),
  90                            FindByOffset(shdr, offset));
  91     assert(it != _mergeAtoms.end());
  92     return *it;
  93   }
  94
  95   typedef std::unordered_map<MergeSectionKey, DefinedAtom *, MergeSectionEq,
  96                              MergeSectionEq> MergedSectionMapT;
  97   typedef typename MergedSectionMapT::iterator MergedSectionMapIterT;
  98
  99 public:
 100   ELFFile(StringRef name, ELFLinkingContext &ctx)
 101       : File(name, kindObject), _ordinal(0),
 102         _doStringsMerge(ctx.mergeCommonStrings()), _useWrap(false), _ctx(ctx) {
 103     setLastError(std::error_code());
 104   }
 105
 106   ELFFile(std::unique_ptr<MemoryBuffer> mb, ELFLinkingContext &ctx)
 107       : File(mb->getBufferIdentifier(), kindObject), _mb(std::move(mb)),
 108         _ordinal(0), _doStringsMerge(ctx.mergeCommonStrings()),
 109         _useWrap(ctx.wrapCalls().size()), _ctx(ctx) {}
 110
 111   static ErrorOr<std::unique_ptr<ELFFile>>
 112   create(std::unique_ptr<MemoryBuffer> mb, ELFLinkingContext &ctx);
 113
 114   virtual Reference::KindArch kindArch();
 115
 116   /// \brief Create symbols from LinkingContext.
 117   std::error_code createAtomsFromContext();
 118
 119   /// \brief Read input sections and populate necessary data structures
 120   /// to read them later and create atoms
 121   std::error_code createAtomizableSections();
 122
 123   /// \brief Create mergeable atoms from sections that have the merge attribute
 124   /// set
 125   std::error_code createMergeableAtoms();
 126
 127   /// \brief Add the symbols that the sections contain. The symbols will be
 128   /// converted to atoms for
 129   /// Undefined symbols, absolute symbols
 130   std::error_code createSymbolsFromAtomizableSections();
 131
 132   /// \brief Create individual atoms
 133   std::error_code createAtoms();
 134
 135   const atom_collection<DefinedAtom> &defined() const override {
 136     return _definedAtoms;
 137   }
 138
 139   const atom_collection<UndefinedAtom> &undefined() const override {
 140     return _undefinedAtoms;
 141   }
 142
 143   const atom_collection<SharedLibraryAtom> &sharedLibrary() const override {
 144     return _sharedLibraryAtoms;
 145   }
 146
 147   const atom_collection<AbsoluteAtom> &absolute() const override {
 148     return _absoluteAtoms;
 149   }
 150
 151   Atom *findAtom(const Elf_Sym *sourceSymbol, const Elf_Sym *targetSymbol) {
 152     // All references to atoms inside a group are through undefined atoms.
 153     Atom *targetAtom = _symbolToAtomMapping.lookup(targetSymbol);
 154     StringRef targetSymbolName = targetAtom->name();
 155     if (targetAtom->definition() != Atom::definitionRegular)
 156       return targetAtom;
 157     if ((llvm::dyn_cast<DefinedAtom>(targetAtom))->scope() ==
 158         DefinedAtom::scopeTranslationUnit)
 159       return targetAtom;
 160     if (!redirectReferenceUsingUndefAtom(sourceSymbol, targetSymbol))
 161       return targetAtom;
 162     auto undefForGroupchild = _undefAtomsForGroupChild.find(targetSymbolName);
 163     if (undefForGroupchild != _undefAtomsForGroupChild.end())
 164       return undefForGroupchild->getValue();
 165     auto undefGroupChildAtom =
 166         new (_readerStorage) SimpleUndefinedAtom(*this, targetSymbolName);
 167     _undefinedAtoms._atoms.push_back(undefGroupChildAtom);
 168     return (_undefAtomsForGroupChild[targetSymbolName] = undefGroupChildAtom);
 169   }
 170
 171 protected:
 172   ELFDefinedAtom<ELFT> *createDefinedAtomAndAssignRelocations(
 173       StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
 174       const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
 175       ArrayRef<uint8_t> secContent);
 176
 177   std::error_code doParse() override;
 178
 179   /// \brief Iterate over Elf_Rela relocations list and create references.
 180   virtual void createRelocationReferences(const Elf_Sym *symbol,
 181                                           ArrayRef<uint8_t> content,
 182                                           range<Elf_Rela_Iter> rels);
 183
 184   /// \brief Iterate over Elf_Rel relocations list and create references.
 185   virtual void createRelocationReferences(const Elf_Sym *symbol,
 186                                           ArrayRef<uint8_t> symContent,
 187                                           ArrayRef<uint8_t> secContent,
 188                                           range<Elf_Rel_Iter> rels);
 189
 190   /// \brief After all the Atoms and References are created, update each
 191   /// Reference's target with the Atom pointer it refers to.
 192   void updateReferences();
 193
 194   /// \brief Update the reference if the access corresponds to a merge string
 195   /// section.
 196   void updateReferenceForMergeStringAccess(ELFReference<ELFT> *ref,
 197                                            const Elf_Sym *symbol,
 198                                            const Elf_Shdr *shdr);
 199
 200   /// \brief Do we want to ignore the section. Ignored sections are
 201   /// not processed to create atoms
 202   bool isIgnoredSection(const Elf_Shdr *section);
 203
 204   /// \brief Is the current section be treated as a mergeable string section.
 205   /// The contents of a mergeable string section are null-terminated strings.
 206   /// If the section have mergeable strings, the linker would need to split
 207   /// the section into multiple atoms and mark them mergeByContent.
 208   bool isMergeableStringSection(const Elf_Shdr *section);
 209
 210   /// \brief Returns a new anonymous atom whose size is equal to the
 211   /// section size. That atom will be used to represent the entire
 212   /// section that have no symbols.
 213   ELFDefinedAtom<ELFT> *createSectionAtom(const Elf_Shdr *section,
 214                                           StringRef sectionName,
 215                                           ArrayRef<uint8_t> contents);
 216
 217   /// Returns the symbol's content size. The nextSymbol should be null if the
 218   /// symbol is the last one in the section.
 219   uint64_t symbolContentSize(const Elf_Shdr *section,
 220                              const Elf_Sym *symbol,
 221                              const Elf_Sym *nextSymbol);
 222
 223   void createEdge(ELFDefinedAtom<ELFT> *from, ELFDefinedAtom<ELFT> *to,
 224                   uint32_t edgeKind);
 225
 226   /// Get the section name for a section.
 227   ErrorOr<StringRef> getSectionName(const Elf_Shdr *shdr) const {
 228     if (!shdr)
 229       return StringRef();
 230     return _objFile->getSectionName(shdr);
 231   }
 232
 233   /// Determines if the section occupy memory space.
 234   bool sectionOccupiesMemorySpace(const Elf_Shdr *shdr) const {
 235     return (shdr->sh_type != llvm::ELF::SHT_NOBITS);
 236   }
 237
 238   /// Return the section contents.
 239   ErrorOr<ArrayRef<uint8_t>> getSectionContents(const Elf_Shdr *shdr) const {
 240     if (!shdr || !sectionOccupiesMemorySpace(shdr))
 241       return ArrayRef<uint8_t>();
 242     return _objFile->getSectionContents(shdr);
 243   }
 244
 245   /// Returns true if the symbol is a undefined symbol.
 246   bool isUndefinedSymbol(const Elf_Sym *sym) const {
 247     return (sym->st_shndx == llvm::ELF::SHN_UNDEF);
 248   }
 249
 250   /// Determines if the target wants to create an atom for a section that has no
 251   /// symbol references.
 252   bool handleSectionWithNoSymbols(const Elf_Shdr *shdr,
 253                                   std::vector<Elf_Sym_Iter> &syms) const {
 254     return shdr && (shdr->sh_type == llvm::ELF::SHT_PROGBITS) && syms.empty();
 255   }
 256
 257   /// Handle creation of atoms for .gnu.linkonce sections.
 258   std::error_code handleGnuLinkOnceSection(
 259       StringRef sectionName,
 260       llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection,
 261       const Elf_Shdr *shdr);
 262
 263   // Handle Section groups/COMDAT scetions.
 264   std::error_code handleSectionGroup(
 265       StringRef signature, StringRef groupSectionName,
 266       llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection,
 267       llvm::DenseMap<const Elf_Shdr *, std::vector<StringRef>> &comdatSections,
 268       const Elf_Shdr *shdr);
 269
 270   /// Process the Undefined symbol and create an atom for it.
 271   ErrorOr<ELFUndefinedAtom<ELFT> *>
 272   handleUndefinedSymbol(StringRef symName, const Elf_Sym *sym) {
 273     return new (_readerStorage) ELFUndefinedAtom<ELFT>(*this, symName, sym);
 274   }
 275
 276   /// Returns true if the symbol is a absolute symbol.
 277   bool isAbsoluteSymbol(const Elf_Sym *sym) const {
 278     return (sym->st_shndx == llvm::ELF::SHN_ABS);
 279   }
 280
 281   /// Process the Absolute symbol and create an atom for it.
 282   ErrorOr<ELFAbsoluteAtom<ELFT> *>
 283   handleAbsoluteSymbol(StringRef symName, const Elf_Sym *sym, int64_t value) {
 284     return new (_readerStorage)
 285         ELFAbsoluteAtom<ELFT>(*this, symName, sym, value);
 286   }
 287
 288   /// Returns true if the symbol is common symbol. A common symbol represents a
 289   /// tentive definition in C. It has name, size and alignment constraint, but
 290   /// actual storage has not yet been allocated. (The linker will allocate
 291   /// storage for them in the later pass after coalescing tentative symbols by
 292   /// name.)
 293   virtual bool isCommonSymbol(const Elf_Sym *symbol) const {
 294     return symbol->getType() == llvm::ELF::STT_COMMON ||
 295            symbol->st_shndx == llvm::ELF::SHN_COMMON;
 296   }
 297
 298   /// Returns true if the section is a gnulinkonce section.
 299   bool isGnuLinkOnceSection(StringRef sectionName) const {
 300     return sectionName.startswith(".gnu.linkonce.");
 301   }
 302
 303   /// Returns true if the section is a COMDAT group section.
 304   bool isGroupSection(const Elf_Shdr *shdr) const {
 305     return (shdr->sh_type == llvm::ELF::SHT_GROUP);
 306   }
 307
 308   /// Returns true if the section is a member of some group.
 309   bool isSectionMemberOfGroup(const Elf_Shdr *shdr) const {
 310     return (shdr->sh_flags & llvm::ELF::SHF_GROUP);
 311   }
 312
 313   /// Returns correct st_value for the symbol depending on the architecture.
 314   /// For most architectures it's just a regular st_value with no changes.
 315   virtual uint64_t getSymbolValue(const Elf_Sym *symbol) const {
 316     return symbol->st_value;
 317   }
 318
 319   /// Process the common symbol and create an atom for it.
 320   virtual ErrorOr<ELFCommonAtom<ELFT> *>
 321   handleCommonSymbol(StringRef symName, const Elf_Sym *sym) {
 322     return new (_readerStorage) ELFCommonAtom<ELFT>(*this, symName, sym);
 323   }
 324
 325   /// Returns true if the symbol is a defined symbol.
 326   virtual bool isDefinedSymbol(const Elf_Sym *sym) const {
 327     return (sym->getType() == llvm::ELF::STT_NOTYPE ||
 328             sym->getType() == llvm::ELF::STT_OBJECT ||
 329             sym->getType() == llvm::ELF::STT_FUNC ||
 330             sym->getType() == llvm::ELF::STT_GNU_IFUNC ||
 331             sym->getType() == llvm::ELF::STT_SECTION ||
 332             sym->getType() == llvm::ELF::STT_FILE ||
 333             sym->getType() == llvm::ELF::STT_TLS);
 334   }
 335
 336   /// Process the Defined symbol and create an atom for it.
 337   virtual ErrorOr<ELFDefinedAtom<ELFT> *>
 338   handleDefinedSymbol(StringRef symName, StringRef sectionName,
 339                       const Elf_Sym *sym, const Elf_Shdr *sectionHdr,
 340                       ArrayRef<uint8_t> contentData,
 341                       unsigned int referenceStart, unsigned int referenceEnd,
 342                       std::vector<ELFReference<ELFT> *> &referenceList) {
 343     return new (_readerStorage) ELFDefinedAtom<ELFT>(
 344         *this, symName, sectionName, sym, sectionHdr, contentData,
 345         referenceStart, referenceEnd, referenceList);
 346   }
 347
 348   /// Process the Merge string and create an atom for it.
 349   ErrorOr<ELFMergeAtom<ELFT> *>
 350   handleMergeString(StringRef sectionName, const Elf_Shdr *sectionHdr,
 351                     ArrayRef<uint8_t> contentData, unsigned int offset) {
 352     ELFMergeAtom<ELFT> *mergeAtom = new (_readerStorage)
 353         ELFMergeAtom<ELFT>(*this, sectionName, sectionHdr, contentData, offset);
 354     const MergeSectionKey mergedSectionKey(sectionHdr, offset);
 355     if (_mergedSectionMap.find(mergedSectionKey) == _mergedSectionMap.end())
 356       _mergedSectionMap.insert(std::make_pair(mergedSectionKey, mergeAtom));
 357     return mergeAtom;
 358   }
 359
 360   /// References to the sections comprising a group, from sections
 361   /// outside the group, must be made via global UNDEF symbols,
 362   /// referencing global symbols defined as addresses in the group
 363   /// sections. They may not reference local symbols for addresses in
 364   /// the group's sections, including section symbols.
 365   /// ABI Doc : https://mentorembedded.github.io/cxx-abi/abi/prop-72-comdat.html
 366   /// Does the atom need to be redirected using a separate undefined atom?
 367   bool redirectReferenceUsingUndefAtom(const Elf_Sym *sourceSymbol,
 368                                        const Elf_Sym *targetSymbol) const;
 369
 370   void addReferenceToSymbol(const ELFReference<ELFT> *r, const Elf_Sym *sym) {
 371     _referenceToSymbol[r] = sym;
 372   }
 373
 374   const Elf_Sym *findSymbolForReference(const ELFReference<ELFT> *r) const {
 375     auto elfReferenceToSymbol = _referenceToSymbol.find(r);
 376     if (elfReferenceToSymbol != _referenceToSymbol.end())
 377       return elfReferenceToSymbol->second;
 378     return nullptr;
 379   }
 380
 381   llvm::BumpPtrAllocator _readerStorage;
 382   std::unique_ptr<llvm::object::ELFFile<ELFT> > _objFile;
 383   atom_collection_vector<DefinedAtom> _definedAtoms;
 384   atom_collection_vector<UndefinedAtom> _undefinedAtoms;
 385   atom_collection_vector<SharedLibraryAtom> _sharedLibraryAtoms;
 386   atom_collection_vector<AbsoluteAtom> _absoluteAtoms;
 387
 388   /// \brief _relocationAddendReferences and _relocationReferences contain the
 389   /// list of relocations references.  In ELF, if a section named, ".text" has
 390   /// relocations will also have a section named ".rel.text" or ".rela.text"
 391   /// which will hold the entries.
 392   std::unordered_map<StringRef, range<Elf_Rela_Iter>>
 393   _relocationAddendReferences;
 394   MergedSectionMapT _mergedSectionMap;
 395   std::unordered_map<StringRef, range<Elf_Rel_Iter>> _relocationReferences;
 396   std::vector<ELFReference<ELFT> *> _references;
 397   llvm::DenseMap<const Elf_Sym *, Atom *> _symbolToAtomMapping;
 398   llvm::DenseMap<const ELFReference<ELFT> *, const Elf_Sym *>
 399   _referenceToSymbol;
 400   // Group child atoms have a pair corresponding to the signature and the
 401   // section header of the section that was used for generating the signature.
 402   llvm::DenseMap<const Elf_Sym *, std::pair<StringRef, const Elf_Shdr *>>
 403       _groupChild;
 404   llvm::StringMap<Atom *> _undefAtomsForGroupChild;
 405
 406   /// \brief Atoms that are created for a section that has the merge property
 407   /// set
 408   MergeAtomsT _mergeAtoms;
 409
 410   /// \brief the section and the symbols that are contained within it to create
 411   /// used to create atoms
 412   llvm::MapVector<const Elf_Shdr *, std::vector<Elf_Sym_Iter>> _sectionSymbols;
 413
 414   /// \brief Sections that have merge string property
 415   std::vector<const Elf_Shdr *> _mergeStringSections;
 416
 417   std::unique_ptr<MemoryBuffer> _mb;
 418   int64_t _ordinal;
 419
 420   /// \brief the cached options relevant while reading the ELF File
 421   bool _doStringsMerge;
 422
 423   /// \brief Is --wrap on?
 424   bool _useWrap;
 425
 426   /// \brief The LinkingContext.
 427   ELFLinkingContext &_ctx;
 428
 429   // Wrap map
 430   llvm::StringMap<UndefinedAtom *> _wrapSymbolMap;
 431 };
 432
 433 /// \brief All atoms are owned by a File. To add linker specific atoms
 434 /// the atoms need to be inserted to a file called (RuntimeFile) which
 435 /// are basically additional symbols required by libc and other runtime
 436 /// libraries part of executing a program. This class provides support
 437 /// for adding absolute symbols and undefined symbols
 438 template <class ELFT> class RuntimeFile : public ELFFile<ELFT> {
 439 public:
 440   typedef llvm::object::Elf_Sym_Impl<ELFT> Elf_Sym;
 441   RuntimeFile(ELFLinkingContext &context, StringRef name)
 442       : ELFFile<ELFT>(name, context) {}
 443
 444   /// \brief add a global absolute atom
 445   virtual Atom *addAbsoluteAtom(StringRef symbolName) {
 446     assert(!symbolName.empty() && "AbsoluteAtoms must have a name");
 447     Elf_Sym *symbol = new (this->_readerStorage) Elf_Sym;
 448     symbol->st_name = 0;
 449     symbol->st_value = 0;
 450     symbol->st_shndx = llvm::ELF::SHN_ABS;
 451     symbol->setBindingAndType(llvm::ELF::STB_GLOBAL, llvm::ELF::STT_OBJECT);
 452     symbol->setVisibility(llvm::ELF::STV_DEFAULT);
 453     symbol->st_size = 0;
 454     auto newAtom = this->handleAbsoluteSymbol(symbolName, symbol, -1);
 455     this->_absoluteAtoms._atoms.push_back(*newAtom);
 456     return *newAtom;
 457   }
 458
 459   /// \brief add an undefined atom
 460   virtual Atom *addUndefinedAtom(StringRef symbolName) {
 461     assert(!symbolName.empty() && "UndefinedAtoms must have a name");
 462     Elf_Sym *symbol = new (this->_readerStorage) Elf_Sym;
 463     symbol->st_name = 0;
 464     symbol->st_value = 0;
 465     symbol->st_shndx = llvm::ELF::SHN_UNDEF;
 466     symbol->setBindingAndType(llvm::ELF::STB_GLOBAL, llvm::ELF::STT_NOTYPE);
 467     symbol->setVisibility(llvm::ELF::STV_DEFAULT);
 468     symbol->st_size = 0;
 469     auto newAtom = this->handleUndefinedSymbol(symbolName, symbol);
 470     this->_undefinedAtoms._atoms.push_back(*newAtom);
 471     return *newAtom;
 472   }
 473
 474   // cannot add atoms to Runtime file
 475   virtual void addAtom(const Atom &) {
 476     llvm_unreachable("cannot add atoms to Runtime files");
 477   }
 478 };
 479
 480 template <class ELFT>
 481 ErrorOr<std::unique_ptr<ELFFile<ELFT>>>
 482 ELFFile<ELFT>::create(std::unique_ptr<MemoryBuffer> mb,
 483                       ELFLinkingContext &ctx) {
 484   std::unique_ptr<ELFFile<ELFT>> file(new ELFFile<ELFT>(std::move(mb), ctx));
 485   return std::move(file);
 486 }
 487
 488 template <class ELFT>
 489 std::error_code ELFFile<ELFT>::doParse() {
 490   std::error_code ec;
 491   _objFile.reset(new llvm::object::ELFFile<ELFT>(_mb->getBuffer(), ec));
 492   if (ec)
 493     return ec;
 494
 495   if ((ec = createAtomsFromContext()))
 496     return ec;
 497
 498   // Read input sections from the input file that need to be converted to
 499   // atoms
 500   if ((ec = createAtomizableSections()))
 501     return ec;
 502
 503   // For mergeable strings, we would need to split the section into various
 504   // atoms
 505   if ((ec = createMergeableAtoms()))
 506     return ec;
 507
 508   // Create the necessary symbols that are part of the section that we
 509   // created in createAtomizableSections function
 510   if ((ec = createSymbolsFromAtomizableSections()))
 511     return ec;
 512
 513   // Create the appropriate atoms from the file
 514   if ((ec = createAtoms()))
 515     return ec;
 516   return std::error_code();
 517 }
 518
 519 template <class ELFT> Reference::KindArch ELFFile<ELFT>::kindArch() {
 520   switch (_objFile->getHeader()->e_machine) {
 521   case llvm::ELF::EM_X86_64:
 522     return Reference::KindArch::x86_64;
 523   case llvm::ELF::EM_386:
 524     return Reference::KindArch::x86;
 525   case llvm::ELF::EM_ARM:
 526     return Reference::KindArch::ARM;
 527   case llvm::ELF::EM_HEXAGON:
 528     return Reference::KindArch::Hexagon;
 529   case llvm::ELF::EM_MIPS:
 530     return Reference::KindArch::Mips;
 531   case llvm::ELF::EM_AARCH64:
 532     return Reference::KindArch::AArch64;
 533   }
 534   llvm_unreachable("unsupported e_machine value");
 535 }
 536
 537 template <class ELFT>
 538 std::error_code ELFFile<ELFT>::createAtomizableSections() {
 539   // Handle: SHT_REL and SHT_RELA sections:
 540   // Increment over the sections, when REL/RELA section types are found add
 541   // the contents to the RelocationReferences map.
 542   // Record the number of relocs to guess at preallocating the buffer.
 543   uint64_t totalRelocs = 0;
 544   for (const Elf_Shdr &section : _objFile->sections()) {
 545     if (isIgnoredSection(&section))
 546       continue;
 547
 548     if (isMergeableStringSection(&section)) {
 549       _mergeStringSections.push_back(&section);
 550       continue;
 551     }
 552
 553     if (section.sh_type == llvm::ELF::SHT_RELA) {
 554       auto sHdr = _objFile->getSection(section.sh_info);
 555
 556       auto sectionName = _objFile->getSectionName(sHdr);
 557       if (std::error_code ec = sectionName.getError())
 558         return ec;
 559
 560       auto rai(_objFile->begin_rela(&section));
 561       auto rae(_objFile->end_rela(&section));
 562
 563       _relocationAddendReferences[*sectionName] = make_range(rai, rae);
 564       totalRelocs += std::distance(rai, rae);
 565     } else if (section.sh_type == llvm::ELF::SHT_REL) {
 566       auto sHdr = _objFile->getSection(section.sh_info);
 567
 568       auto sectionName = _objFile->getSectionName(sHdr);
 569       if (std::error_code ec = sectionName.getError())
 570         return ec;
 571
 572       auto ri(_objFile->begin_rel(&section));
 573       auto re(_objFile->end_rel(&section));
 574
 575       _relocationReferences[*sectionName] = make_range(ri, re);
 576       totalRelocs += std::distance(ri, re);
 577     } else {
 578       _sectionSymbols[&section];
 579     }
 580   }
 581   _references.reserve(totalRelocs);
 582   return std::error_code();
 583 }
 584
 585 template <class ELFT> std::error_code ELFFile<ELFT>::createMergeableAtoms() {
 586   // Divide the section that contains mergeable strings into tokens
 587   // TODO
 588   // a) add resolver support to recognize multibyte chars
 589   // b) Create a separate section chunk to write mergeable atoms
 590   std::vector<MergeString *> tokens;
 591   for (const Elf_Shdr *msi : _mergeStringSections) {
 592     auto sectionName = getSectionName(msi);
 593     if (std::error_code ec = sectionName.getError())
 594       return ec;
 595
 596     auto sectionContents = getSectionContents(msi);
 597     if (std::error_code ec = sectionContents.getError())
 598       return ec;
 599
 600     StringRef secCont(reinterpret_cast<const char *>(sectionContents->begin()),
 601                       sectionContents->size());
 602
 603     unsigned int prev = 0;
 604     for (std::size_t i = 0, e = sectionContents->size(); i != e; ++i) {
 605       if ((*sectionContents)[i] == '\0') {
 606         tokens.push_back(new (_readerStorage) MergeString(
 607             prev, secCont.slice(prev, i + 1), msi, *sectionName));
 608         prev = i + 1;
 609       }
 610     }
 611   }
 612
 613   // Create Mergeable atoms
 614   for (const MergeString *tai : tokens) {
 615     ArrayRef<uint8_t> content((const uint8_t *)tai->_string.data(),
 616                               tai->_string.size());
 617     ErrorOr<ELFMergeAtom<ELFT> *> mergeAtom =
 618         handleMergeString(tai->_sectionName, tai->_shdr, content, tai->_offset);
 619     (*mergeAtom)->setOrdinal(++_ordinal);
 620     _definedAtoms._atoms.push_back(*mergeAtom);
 621     _mergeAtoms.push_back(*mergeAtom);
 622   }
 623   return std::error_code();
 624 }
 625
 626 template <class ELFT>
 627 std::error_code ELFFile<ELFT>::createSymbolsFromAtomizableSections() {
 628   // Increment over all the symbols collecting atoms and symbol names for
 629   // later use.
 630   auto SymI = _objFile->begin_symbols(), SymE = _objFile->end_symbols();
 631
 632   // Skip over dummy sym.
 633   if (SymI != SymE)
 634     ++SymI;
 635
 636   for (; SymI != SymE; ++SymI) {
 637     const Elf_Shdr *section = _objFile->getSection(&*SymI);
 638
 639     auto symbolName = _objFile->getSymbolName(SymI);
 640     if (std::error_code ec = symbolName.getError())
 641       return ec;
 642
 643     if (isAbsoluteSymbol(&*SymI)) {
 644       ErrorOr<ELFAbsoluteAtom<ELFT> *> absAtom =
 645           handleAbsoluteSymbol(*symbolName, &*SymI, (int64_t)getSymbolValue(&*SymI));
 646       _absoluteAtoms._atoms.push_back(*absAtom);
 647       _symbolToAtomMapping.insert(std::make_pair(&*SymI, *absAtom));
 648     } else if (isUndefinedSymbol(&*SymI)) {
 649       if (_useWrap &&
 650           (_wrapSymbolMap.find(*symbolName) != _wrapSymbolMap.end())) {
 651         auto wrapAtom = _wrapSymbolMap.find(*symbolName);
 652         _symbolToAtomMapping.insert(
 653             std::make_pair(&*SymI, wrapAtom->getValue()));
 654         continue;
 655       }
 656       ErrorOr<ELFUndefinedAtom<ELFT> *> undefAtom =
 657           handleUndefinedSymbol(*symbolName, &*SymI);
 658       _undefinedAtoms._atoms.push_back(*undefAtom);
 659       _symbolToAtomMapping.insert(std::make_pair(&*SymI, *undefAtom));
 660     } else if (isCommonSymbol(&*SymI)) {
 661       ErrorOr<ELFCommonAtom<ELFT> *> commonAtom =
 662           handleCommonSymbol(*symbolName, &*SymI);
 663       (*commonAtom)->setOrdinal(++_ordinal);
 664       _definedAtoms._atoms.push_back(*commonAtom);
 665       _symbolToAtomMapping.insert(std::make_pair(&*SymI, *commonAtom));
 666     } else if (isDefinedSymbol(&*SymI)) {
 667       _sectionSymbols[section].push_back(SymI);
 668     } else {
 669       llvm::errs() << "Unable to create atom for: " << *symbolName << "\n";
 670       return llvm::object::object_error::parse_failed;
 671     }
 672   }
 673
 674   return std::error_code();
 675 }
 676
 677 template <class ELFT> std::error_code ELFFile<ELFT>::createAtoms() {
 678   // Holds all the atoms that are part of the section. They are the targets of
 679   // the kindGroupChild reference.
 680   llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> atomsForSection;
 681   // group sections have a mapping of the section header to the
 682   // signature/section.
 683   llvm::DenseMap<const Elf_Shdr *, std::pair<StringRef, StringRef>>
 684       groupSections;
 685   // Contains a list of comdat sections for a group.
 686   llvm::DenseMap<const Elf_Shdr *, std::vector<StringRef>> comdatSections;
 687   for (auto &i : _sectionSymbols) {
 688     const Elf_Shdr *section = i.first;
 689     std::vector<Elf_Sym_Iter> &symbols = i.second;
 690
 691     // Sort symbols by position.
 692     std::stable_sort(symbols.begin(), symbols.end(),
 693                      [this](Elf_Sym_Iter a, Elf_Sym_Iter b) {
 694                        return getSymbolValue(&*a) < getSymbolValue(&*b);
 695                      });
 696
 697     ErrorOr<StringRef> sectionName = this->getSectionName(section);
 698     if (std::error_code ec = sectionName.getError())
 699       return ec;
 700
 701     auto sectionContents = getSectionContents(section);
 702     if (std::error_code ec = sectionContents.getError())
 703       return ec;
 704
 705     bool addAtoms = true;
 706
 707     // A section of type SHT_GROUP defines a grouping of sections. The name of a
 708     // symbol from one of the containing object's symbol tables provides a
 709     // signature
 710     // for the section group. The section header of the SHT_GROUP section
 711     // specifies
 712     // the identifying symbol entry, as described : the sh_link member contains
 713     // the section header index of the symbol table section that contains the
 714     // entry.
 715     // The sh_info member contains the symbol table index of the identifying
 716     // entry.
 717     // The sh_flags member of the section header contains 0. The name of the
 718     // section
 719     // (sh_name) is not specified.
 720     if (isGroupSection(section)) {
 721       const Elf_Word *groupMembers =
 722           reinterpret_cast<const Elf_Word *>(sectionContents->data());
 723       const long count = (section->sh_size) / sizeof(Elf_Word);
 724       for (int i = 1; i < count; i++) {
 725         const Elf_Shdr *sHdr = _objFile->getSection(groupMembers[i]);
 726         ErrorOr<StringRef> sectionName = _objFile->getSectionName(sHdr);
 727         if (std::error_code ec = sectionName.getError())
 728           return ec;
 729         comdatSections[section].push_back(*sectionName);
 730       }
 731       const Elf_Sym *symbol = _objFile->getSymbol(section->sh_info);
 732       const Elf_Shdr *symtab = _objFile->getSection(section->sh_link);
 733       ErrorOr<StringRef> symbolName = _objFile->getSymbolName(symtab, symbol);
 734       if (std::error_code ec = symbolName.getError())
 735         return ec;
 736       groupSections.insert(
 737           std::make_pair(section, std::make_pair(*symbolName, *sectionName)));
 738       continue;
 739     }
 740
 741     if (isGnuLinkOnceSection(*sectionName)) {
 742       groupSections.insert(
 743           std::make_pair(section, std::make_pair(*sectionName, *sectionName)));
 744       addAtoms = false;
 745     }
 746
 747     if (isSectionMemberOfGroup(section))
 748       addAtoms = false;
 749
 750     if (handleSectionWithNoSymbols(section, symbols)) {
 751       ELFDefinedAtom<ELFT> *newAtom =
 752           createSectionAtom(section, *sectionName, *sectionContents);
 753       newAtom->setOrdinal(++_ordinal);
 754       if (addAtoms)
 755         _definedAtoms._atoms.push_back(newAtom);
 756       else
 757         atomsForSection[*sectionName].push_back(newAtom);
 758       continue;
 759     }
 760
 761     ELFDefinedAtom<ELFT> *previousAtom = nullptr;
 762     ELFReference<ELFT> *anonFollowedBy = nullptr;
 763
 764     for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
 765       auto symbol = *si;
 766       StringRef symbolName = "";
 767       if (symbol->getType() != llvm::ELF::STT_SECTION) {
 768         auto symName = _objFile->getSymbolName(symbol);
 769         if (std::error_code ec = symName.getError())
 770           return ec;
 771         symbolName = *symName;
 772       }
 773
 774       uint64_t contentSize = symbolContentSize(
 775           section, &*symbol, (si + 1 == se) ? nullptr : &**(si + 1));
 776
 777       // Check to see if we need to add the FollowOn Reference
 778       ELFReference<ELFT> *followOn = nullptr;
 779       if (previousAtom) {
 780         // Replace the followon atom with the anonymous atom that we created,
 781         // so that the next symbol that we create is a followon from the
 782         // anonymous atom.
 783         if (anonFollowedBy) {
 784           followOn = anonFollowedBy;
 785         } else {
 786           followOn = new (_readerStorage)
 787               ELFReference<ELFT>(lld::Reference::kindLayoutAfter);
 788           previousAtom->addReference(followOn);
 789         }
 790       }
 791
 792       ArrayRef<uint8_t> symbolData((const uint8_t *)sectionContents->data() +
 793                                        getSymbolValue(&*symbol),
 794                                    contentSize);
 795
 796       // If the linker finds that a section has global atoms that are in a
 797       // mergeable section, treat them as defined atoms as they shouldn't be
 798       // merged away as well as these symbols have to be part of symbol
 799       // resolution
 800       if (isMergeableStringSection(section)) {
 801         if (symbol->getBinding() == llvm::ELF::STB_GLOBAL) {
 802           auto definedMergeAtom = handleDefinedSymbol(
 803               symbolName, *sectionName, &**si, section, symbolData,
 804               _references.size(), _references.size(), _references);
 805           (*definedMergeAtom)->setOrdinal(++_ordinal);
 806           if (addAtoms)
 807             _definedAtoms._atoms.push_back(*definedMergeAtom);
 808           else
 809             atomsForSection[*sectionName].push_back(*definedMergeAtom);
 810         }
 811         continue;
 812       }
 813
 814       // Don't allocate content to a weak symbol, as they may be merged away.
 815       // Create an anonymous atom to hold the data.
 816       ELFDefinedAtom<ELFT> *anonAtom = nullptr;
 817       anonFollowedBy = nullptr;
 818       if (symbol->getBinding() == llvm::ELF::STB_WEAK) {
 819         // Create anonymous new non-weak ELF symbol that holds the symbol
 820         // data.
 821         auto sym = new (_readerStorage) Elf_Sym(*symbol);
 822         sym->setBinding(llvm::ELF::STB_GLOBAL);
 823         anonAtom = createDefinedAtomAndAssignRelocations(
 824             "", *sectionName, sym, section, symbolData, *sectionContents);
 825         symbolData = ArrayRef<uint8_t>();
 826
 827         // If this is the last atom, let's not create a followon reference.
 828         if (anonAtom && (si + 1) != se) {
 829           anonFollowedBy = new (_readerStorage)
 830               ELFReference<ELFT>(lld::Reference::kindLayoutAfter);
 831           anonAtom->addReference(anonFollowedBy);
 832         }
 833       }
 834
 835       ELFDefinedAtom<ELFT> *newAtom = createDefinedAtomAndAssignRelocations(
 836           symbolName, *sectionName, &*symbol, section, symbolData,
 837           *sectionContents);
 838       newAtom->setOrdinal(++_ordinal);
 839
 840       // If the atom was a weak symbol, let's create a followon reference to
 841       // the anonymous atom that we created.
 842       if (anonAtom)
 843         createEdge(newAtom, anonAtom, Reference::kindLayoutAfter);
 844
 845       if (previousAtom) {
 846         // Set the followon atom to the weak atom that we have created, so
 847         // that they would alias when the file gets written.
 848         followOn->setTarget(anonAtom ? anonAtom : newAtom);
 849       }
 850
 851       // The previous atom is always the atom created before unless the atom
 852       // is a weak atom.
 853       previousAtom = anonAtom ? anonAtom : newAtom;
 854
 855       if (addAtoms)
 856         _definedAtoms._atoms.push_back(newAtom);
 857       else
 858         atomsForSection[*sectionName].push_back(newAtom);
 859
 860       _symbolToAtomMapping.insert(std::make_pair(&*symbol, newAtom));
 861       if (anonAtom) {
 862         anonAtom->setOrdinal(++_ordinal);
 863         if (addAtoms)
 864           _definedAtoms._atoms.push_back(anonAtom);
 865         else
 866           atomsForSection[*sectionName].push_back(anonAtom);
 867       }
 868     }
 869   }
 870
 871   // Iterate over all the group sections to create parent atoms pointing to
 872   // group-child atoms.
 873   for (auto &sect : groupSections) {
 874     StringRef signature = sect.second.first;
 875     StringRef groupSectionName = sect.second.second;
 876     if (isGnuLinkOnceSection(signature))
 877       handleGnuLinkOnceSection(signature, atomsForSection, sect.first);
 878     else if (isGroupSection(sect.first))
 879       handleSectionGroup(signature, groupSectionName, atomsForSection,
 880                          comdatSections, sect.first);
 881   }
 882
 883   updateReferences();
 884   return std::error_code();
 885 }
 886
 887 template <class ELFT>
 888 std::error_code ELFFile<ELFT>::handleGnuLinkOnceSection(
 889     StringRef signature,
 890     llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection,
 891     const Elf_Shdr *shdr) {
 892   // TODO: Check for errors.
 893   unsigned int referenceStart = _references.size();
 894   std::vector<ELFReference<ELFT> *> refs;
 895   for (auto ha : atomsForSection[signature]) {
 896     _groupChild[ha->symbol()] = std::make_pair(signature, shdr);
 897     ELFReference<ELFT> *ref =
 898         new (_readerStorage) ELFReference<ELFT>(lld::Reference::kindGroupChild);
 899     ref->setTarget(ha);
 900     refs.push_back(ref);
 901   }
 902   atomsForSection[signature].clear();
 903   // Create a gnu linkonce atom.
 904   auto gnuLinkOnceAtom = handleDefinedSymbol(
 905       signature, signature, nullptr, shdr, ArrayRef<uint8_t>(), referenceStart,
 906       _references.size(), _references);
 907   (*gnuLinkOnceAtom)->setOrdinal(++_ordinal);
 908   _definedAtoms._atoms.push_back(*gnuLinkOnceAtom);
 909   for (auto reference : refs)
 910     (*gnuLinkOnceAtom)->addReference(reference);
 911   return std::error_code();
 912 }
 913
 914 template <class ELFT>
 915 std::error_code ELFFile<ELFT>::handleSectionGroup(
 916     StringRef signature, StringRef groupSectionName,
 917     llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection,
 918     llvm::DenseMap<const Elf_Shdr *, std::vector<StringRef>> &comdatSections,
 919     const Elf_Shdr *shdr) {
 920   // TODO: Check for errors.
 921   unsigned int referenceStart = _references.size();
 922   std::vector<ELFReference<ELFT> *> refs;
 923   auto sectionNamesInGroup = comdatSections[shdr];
 924   for (auto sectionName : sectionNamesInGroup) {
 925     for (auto ha : atomsForSection[sectionName]) {
 926       _groupChild[ha->symbol()] = std::make_pair(signature, shdr);
 927       ELFReference<ELFT> *ref = new (_readerStorage)
 928           ELFReference<ELFT>(lld::Reference::kindGroupChild);
 929       ref->setTarget(ha);
 930       refs.push_back(ref);
 931     }
 932     atomsForSection[sectionName].clear();
 933   }
 934   // Create a gnu linkonce atom.
 935   auto sectionGroupAtom = handleDefinedSymbol(
 936       signature, groupSectionName, nullptr, shdr, ArrayRef<uint8_t>(),
 937       referenceStart, _references.size(), _references);
 938   (*sectionGroupAtom)->setOrdinal(++_ordinal);
 939   _definedAtoms._atoms.push_back(*sectionGroupAtom);
 940   for (auto reference : refs)
 941     (*sectionGroupAtom)->addReference(reference);
 942   return std::error_code();
 943 }
 944
 945 template <class ELFT> std::error_code ELFFile<ELFT>::createAtomsFromContext() {
 946   if (!_useWrap)
 947     return std::error_code();
 948   // Steps :-
 949   // a) Create an undefined atom for the symbol specified by the --wrap option,
 950   // as that
 951   // may be needed to be pulled from an archive.
 952   // b) Create an undefined atom for __wrap_<symbolname>.
 953   // c) All references to the symbol specified by wrap should point to
 954   // __wrap_<symbolname>
 955   // d) All references to __real_symbol should point to the <symbol>
 956   for (auto &wrapsym : _ctx.wrapCalls()) {
 957     StringRef wrapStr = wrapsym.getKey();
 958     // Create a undefined symbol fror the wrap symbol.
 959     UndefinedAtom *wrapSymAtom =
 960         new (_readerStorage) SimpleUndefinedAtom(*this, wrapStr);
 961     StringRef wrapCallSym =
 962         _ctx.allocateString((llvm::Twine("__wrap_") + wrapStr).str());
 963     StringRef realCallSym =
 964         _ctx.allocateString((llvm::Twine("__real_") + wrapStr).str());
 965     UndefinedAtom *wrapCallAtom =
 966         new (_readerStorage) SimpleUndefinedAtom(*this, wrapCallSym);
 967     // Create maps, when there is call to sym, it should point to wrapCallSym.
 968     _wrapSymbolMap.insert(std::make_pair(wrapStr, wrapCallAtom));
 969     // Whenever there is a reference to realCall it should point to the symbol
 970     // created for each wrap usage.
 971     _wrapSymbolMap.insert(std::make_pair(realCallSym, wrapSymAtom));
 972     _undefinedAtoms._atoms.push_back(wrapSymAtom);
 973     _undefinedAtoms._atoms.push_back(wrapCallAtom);
 974   }
 975   return std::error_code();
 976 }
 977
 978 template <class ELFT>
 979 ELFDefinedAtom<ELFT> *ELFFile<ELFT>::createDefinedAtomAndAssignRelocations(
 980     StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
 981     const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
 982     ArrayRef<uint8_t> secContent) {
 983   unsigned int referenceStart = _references.size();
 984
 985   // Add Rela (those with r_addend) references:
 986   auto rari = _relocationAddendReferences.find(sectionName);
 987   if (rari != _relocationAddendReferences.end())
 988     createRelocationReferences(symbol, symContent, rari->second);
 989
 990   // Add Rel references.
 991   auto rri = _relocationReferences.find(sectionName);
 992   if (rri != _relocationReferences.end())
 993     createRelocationReferences(symbol, symContent, secContent, rri->second);
 994
 995   // Create the DefinedAtom and add it to the list of DefinedAtoms.
 996   return *handleDefinedSymbol(symbolName, sectionName, symbol, section,
 997                               symContent, referenceStart, _references.size(),
 998                               _references);
 999 }
1000
1001 template <class ELFT>
1002 void ELFFile<ELFT>::createRelocationReferences(const Elf_Sym *symbol,
1003                                                ArrayRef<uint8_t> content,
1004                                                range<Elf_Rela_Iter> rels) {
1005   bool isMips64EL = _objFile->isMips64EL();
1006   const auto symValue = getSymbolValue(symbol);
1007   for (const auto &rel : rels) {
1008     if (rel.r_offset < symValue ||
1009         symValue + content.size() <= rel.r_offset)
1010       continue;
1011     auto elfRelocation = new (_readerStorage)
1012         ELFReference<ELFT>(&rel, rel.r_offset - symValue, kindArch(),
1013                            rel.getType(isMips64EL), rel.getSymbol(isMips64EL));
1014     addReferenceToSymbol(elfRelocation, symbol);
1015     _references.push_back(elfRelocation);
1016   }
1017 }
1018
1019 template <class ELFT>
1020 void ELFFile<ELFT>::createRelocationReferences(const Elf_Sym *symbol,
1021                                                ArrayRef<uint8_t> symContent,
1022                                                ArrayRef<uint8_t> secContent,
1023                                                range<Elf_Rel_Iter> rels) {
1024   bool isMips64EL = _objFile->isMips64EL();
1025   const auto symValue = getSymbolValue(symbol);
1026   for (const auto &rel : rels) {
1027     if (rel.r_offset < symValue ||
1028         symValue + symContent.size() <= rel.r_offset)
1029       continue;
1030     auto elfRelocation = new (_readerStorage)
1031         ELFReference<ELFT>(rel.r_offset - symValue, kindArch(),
1032                            rel.getType(isMips64EL), rel.getSymbol(isMips64EL));
1033     int32_t addend = *(symContent.data() + rel.r_offset - symValue);
1034     elfRelocation->setAddend(addend);
1035     addReferenceToSymbol(elfRelocation, symbol);
1036     _references.push_back(elfRelocation);
1037   }
1038 }
1039
1040 template <class ELFT>
1041 void ELFFile<ELFT>::updateReferenceForMergeStringAccess(ELFReference<ELFT> *ref,
1042                                                         const Elf_Sym *symbol,
1043                                                         const Elf_Shdr *shdr) {
1044   // If the target atom is mergeable strefng atom, the atom might have been
1045   // merged with other atom having the same contents. Try to find the
1046   // merged one if that's the case.
1047   int64_t addend = ref->addend();
1048   if (addend < 0)
1049     addend = 0;
1050
1051   const MergeSectionKey ms(shdr, addend);
1052   auto msec = _mergedSectionMap.find(ms);
1053   if (msec != _mergedSectionMap.end()) {
1054     ref->setTarget(msec->second);
1055     return;
1056   }
1057
1058   // The target atom was not merged. Mergeable atoms are not in
1059   // _symbolToAtomMapping, so we cannot find it by calling findAtom(). We
1060   // instead call findMergeAtom().
1061   if (symbol->getType() != llvm::ELF::STT_SECTION)
1062     addend = getSymbolValue(symbol) + addend;
1063   ELFMergeAtom<ELFT> *mergedAtom = findMergeAtom(shdr, addend);
1064   ref->setOffset(addend - mergedAtom->offset());
1065   ref->setAddend(0);
1066   ref->setTarget(mergedAtom);
1067 }
1068
1069 template <class ELFT> void ELFFile<ELFT>::updateReferences() {
1070   for (auto &ri : _references) {
1071     if (ri->kindNamespace() != lld::Reference::KindNamespace::ELF)
1072       continue;
1073     const Elf_Sym *symbol = _objFile->getSymbol(ri->targetSymbolIndex());
1074     const Elf_Shdr *shdr = _objFile->getSection(symbol);
1075
1076     // If the atom is not in mergeable string section, the target atom is
1077     // simply that atom.
1078     if (isMergeableStringSection(shdr))
1079       updateReferenceForMergeStringAccess(ri, symbol, shdr);
1080     else
1081       ri->setTarget(findAtom(findSymbolForReference(ri), symbol));
1082   }
1083 }
1084
1085 template <class ELFT>
1086 bool ELFFile<ELFT>::isIgnoredSection(const Elf_Shdr *section) {
1087   switch (section->sh_type) {
1088   case llvm::ELF::SHT_NULL:
1089   case llvm::ELF::SHT_STRTAB:
1090   case llvm::ELF::SHT_SYMTAB:
1091   case llvm::ELF::SHT_SYMTAB_SHNDX:
1092     return true;
1093   default:
1094     break;
1095   }
1096   return false;
1097 }
1098
1099 template <class ELFT>
1100 bool ELFFile<ELFT>::isMergeableStringSection(const Elf_Shdr *section) {
1101   if (_doStringsMerge && section) {
1102     int64_t sectionFlags = section->sh_flags;
1103     sectionFlags &= ~llvm::ELF::SHF_ALLOC;
1104     // Mergeable string sections have both SHF_MERGE and SHF_STRINGS flags
1105     // set. sh_entsize is the size of each character which is normally 1.
1106     if ((section->sh_entsize < 2) &&
1107         (sectionFlags == (llvm::ELF::SHF_MERGE | llvm::ELF::SHF_STRINGS))) {
1108       return true;
1109     }
1110   }
1111   return false;
1112 }
1113
1114 template <class ELFT>
1115 ELFDefinedAtom<ELFT> *
1116 ELFFile<ELFT>::createSectionAtom(const Elf_Shdr *section, StringRef sectionName,
1117                                  ArrayRef<uint8_t> content) {
1118   Elf_Sym *sym = new (_readerStorage) Elf_Sym;
1119   sym->st_name = 0;
1120   sym->setBindingAndType(llvm::ELF::STB_LOCAL, llvm::ELF::STT_SECTION);
1121   sym->st_other = 0;
1122   sym->st_shndx = 0;
1123   sym->st_value = 0;
1124   sym->st_size = 0;
1125   auto *newAtom = createDefinedAtomAndAssignRelocations(
1126       "", sectionName, sym, section, content, content);
1127   newAtom->setOrdinal(++_ordinal);
1128   return newAtom;
1129 }
1130
1131 template <class ELFT>
1132 uint64_t ELFFile<ELFT>::symbolContentSize(const Elf_Shdr *section,
1133                                           const Elf_Sym *symbol,
1134                                           const Elf_Sym *nextSymbol) {
1135   const auto symValue = getSymbolValue(symbol);
1136   // if this is the last symbol, take up the remaining data.
1137   return nextSymbol ? getSymbolValue(nextSymbol) - symValue
1138                     : section->sh_size - symValue;
1139 }
1140
1141 template <class ELFT>
1142 void ELFFile<ELFT>::createEdge(ELFDefinedAtom<ELFT> *from,
1143                                ELFDefinedAtom<ELFT> *to, uint32_t edgeKind) {
1144   auto reference = new (_readerStorage) ELFReference<ELFT>(edgeKind);
1145   reference->setTarget(to);
1146   from->addReference(reference);
1147 }
1148
1149 /// Does the atom need to be redirected using a separate undefined atom?
1150 template <class ELFT>
1151 bool ELFFile<ELFT>::redirectReferenceUsingUndefAtom(
1152     const Elf_Sym *sourceSymbol, const Elf_Sym *targetSymbol) const {
1153   auto groupChildTarget = _groupChild.find(targetSymbol);
1154
1155   // If the reference is not to a group child atom, there is no need to redirect
1156   // using a undefined atom. Its also not needed if the source and target are
1157   // from the same section.
1158   if ((groupChildTarget == _groupChild.end()) ||
1159       (sourceSymbol->st_shndx == targetSymbol->st_shndx))
1160     return false;
1161
1162   auto groupChildSource = _groupChild.find(sourceSymbol);
1163
1164   // If the source symbol is not in a group, use a undefined symbol too.
1165   if (groupChildSource == _groupChild.end())
1166     return true;
1167
1168   // If the source and child are from the same group, we dont need the
1169   // relocation to go through a undefined symbol.
1170   if (groupChildSource->second.second == groupChildTarget->second.second)
1171     return false;
1172
1173   return true;
1174 }
1175
1176 } // end namespace elf
1177 } // end namespace lld
1178
1179 #endif // LLD_READER_WRITER_ELF_FILE_H