diff options
-rw-r--r-- | lld/lib/ReaderWriter/ELF/Atoms.h | 90 | ||||
-rw-r--r-- | lld/lib/ReaderWriter/ELF/File.h | 181 | ||||
-rw-r--r-- | lld/test/elf/Inputs/bar.o.x86-64 | bin | 0 -> 1240 bytes | |||
-rw-r--r-- | lld/test/elf/Inputs/constants-merge.x86-64 | bin | 0 -> 1232 bytes | |||
-rw-r--r-- | lld/test/elf/Inputs/foo.o.x86-64 | bin | 0 -> 1240 bytes | |||
-rw-r--r-- | lld/test/elf/mergeatoms.objtxt | 5 | ||||
-rw-r--r-- | lld/test/elf/mergeconstants.objtxt | 16 | ||||
-rw-r--r-- | lld/test/elf/reloc.objtxt | 154 |
8 files changed, 360 insertions, 86 deletions
diff --git a/lld/lib/ReaderWriter/ELF/Atoms.h b/lld/lib/ReaderWriter/ELF/Atoms.h index 9cff16b194c..7c6e6ec61e2 100644 --- a/lld/lib/ReaderWriter/ELF/Atoms.h +++ b/lld/lib/ReaderWriter/ELF/Atoms.h @@ -69,9 +69,9 @@ public: return _addend; } - virtual void setAddend(Addend A) { - _addend = A; - } + virtual void setOffset(uint64_t off) { _offsetInAtom = off; } + + virtual void setAddend(Addend A) { _addend = A; } virtual void setTarget(const Atom *newAtom) { _target = newAtom; } @@ -438,8 +438,88 @@ private: uint64_t _ordinal; unsigned int _referenceStartIndex; unsigned int _referenceEndIndex; - std::vector<ELFReference<ELFT>*> & - _referenceList; + std::vector<ELFReference<ELFT> *> &_referenceList; +}; + +/// \brief This atom stores mergeable Strings +template <class ELFT> class ELFMergeAtom LLVM_FINAL : public DefinedAtom { + typedef llvm::object::Elf_Shdr_Impl<ELFT> Elf_Shdr; + +public: + ELFMergeAtom(const ELFFile<ELFT> &file, StringRef sectionName, + const Elf_Shdr *section, llvm::ArrayRef<uint8_t> contentData, + uint64_t offset) + : _owningFile(file), _sectionName(sectionName), _section(section), + _contentData(contentData), _offset(offset) { + static uint64_t orderNumber = 0; + _ordinal = ++orderNumber; + } + + virtual const class ELFFile<ELFT> &file() const { + return _owningFile; + } virtual StringRef name() const { + return ""; + } + + virtual uint64_t offset() const { return _offset; } + + virtual uint64_t ordinal() const { return _ordinal; } + + virtual uint64_t size() const { return _contentData.size(); } + + virtual Scope scope() const { return scopeTranslationUnit; } + + virtual Interposable interposable() const { return interposeNo; } + + virtual Merge merge() const { return mergeByContent; } + + virtual ContentType contentType() const { return typeConstant; } + + virtual Alignment alignment() const { + return Alignment(llvm::Log2_64(_section->sh_addralign)); + } + + virtual SectionChoice sectionChoice() const { return sectionCustomRequired; } + + virtual StringRef customSectionName() const { return _sectionName; } + + virtual SectionPosition sectionPosition() const { return sectionPositionAny; } + + virtual DeadStripKind deadStrip() const { return deadStripNormal; } + + virtual ContentPermissions permissions() const { return permR__; } + + virtual bool isThumb() const { return false; } + + virtual bool isAlias() const { return false; } + + virtual llvm::ArrayRef<uint8_t> rawContent() const { return _contentData; } + + DefinedAtom::reference_iterator begin() const { + uintptr_t index = 0; + const void *it = reinterpret_cast<const void *>(index); + return reference_iterator(*this, it); + } + + DefinedAtom::reference_iterator end() const { + uintptr_t index = 0; + const void *it = reinterpret_cast<const void *>(index); + return reference_iterator(*this, it); + } + + const Reference *derefIterator(const void *It) const { return nullptr; } + + void incrementIterator(const void *&It) const {} + +private: + + const ELFFile<ELFT> &_owningFile; + StringRef _sectionName; + const Elf_Shdr *_section; + /// \brief Holds the bits that make up the atom. + llvm::ArrayRef<uint8_t> _contentData; + uint64_t _ordinal; + uint64_t _offset; }; /// \brief An atom from a shared library. diff --git a/lld/lib/ReaderWriter/ELF/File.h b/lld/lib/ReaderWriter/ELF/File.h index f1123ef539f..c68742d73f5 100644 --- a/lld/lib/ReaderWriter/ELF/File.h +++ b/lld/lib/ReaderWriter/ELF/File.h @@ -48,6 +48,69 @@ template <class ELFT> class ELFFile : public File { typedef llvm::object::Elf_Rel_Impl<ELFT, false> Elf_Rel; typedef llvm::object::Elf_Rel_Impl<ELFT, true> Elf_Rela; + // A Map is used to hold the atoms that have been divided up + // after reading the section that contains Merge String attributes + struct MergeSectionKey { + MergeSectionKey(const Elf_Shdr *shdr, int32_t offset) + : _shdr(shdr), _offset(offset) { + } + // Data members + const Elf_Shdr *_shdr; + int32_t _offset; + }; + struct MergeSectionEq { + int64_t operator()(const MergeSectionKey &k) const { + return llvm::hash_combine((int64_t)(k._shdr->sh_name), + (int64_t) k._offset); + } + bool operator()(const MergeSectionKey &lhs, + const MergeSectionKey &rhs) const { + return ((lhs._shdr->sh_name == rhs._shdr->sh_name) && + (lhs._offset == rhs._offset)); + } + }; + + struct MergeString { + MergeString(int32_t offset, StringRef str, const Elf_Shdr *shdr, + StringRef sectionName) + : _offset(offset), _string(str), _shdr(shdr), + _sectionName(sectionName) { + } + // the offset of this atom + int32_t _offset; + // The content + StringRef _string; + // Section header + const Elf_Shdr *_shdr; + // Section name + StringRef _sectionName; + }; + + // This is used to find the MergeAtom given a relocation + // offset + typedef std::vector<ELFMergeAtom<ELFT> *> MergeAtomsT; + typedef typename MergeAtomsT::iterator MergeAtomsIter; + + /// \brief find a mergeAtom given a start offset + struct FindByOffset { + uint64_t _offset; + FindByOffset(uint64_t offset) : _offset(offset) {} + bool operator()(const ELFMergeAtom<ELFT> *a) { + uint64_t off = a->offset(); + return ((_offset >= off) && (_offset <= off + a->size())); + } + }; + + /// \brief find a merge atom given a offset + MergeAtomsIter findMergeAtom(uint64_t offset) { + return std::find_if(_mergeAtoms.begin(), _mergeAtoms.end(), + FindByOffset(offset)); + } + + typedef std::unordered_map<MergeSectionKey, DefinedAtom *, MergeSectionEq, + MergeSectionEq> MergedSectionMapT; + typedef typename MergedSectionMapT::iterator MergedSectionMapIterT; + public: ELFFile(const ELFTargetInfo &ti, StringRef name) : File(name), _elfTargetInfo(ti) { @@ -77,6 +140,9 @@ public: std::map<const Elf_Shdr *, std::vector<const Elf_Sym *> > sectionSymbols; + // Sections that have merge string property + std::vector<const Elf_Shdr *> mergeStringSections; + // Handle: SHT_REL and SHT_RELA sections: // Increment over the sections, when REL/RELA section types are found add // the contents to the RelocationReferences map. @@ -97,6 +163,18 @@ public: if (section->sh_size == 0) continue; + int64_t sectionFlags = section->sh_flags; + sectionFlags &= ~llvm::ELF::SHF_ALLOC; + + // If the section have mergeable strings, the linker would + // need to split the section into multiple atoms and mark them + // mergeByContent + if ((section->sh_entsize < 2) && + (sectionFlags == (llvm::ELF::SHF_MERGE | llvm::ELF::SHF_STRINGS))) { + mergeStringSections.push_back(section); + continue; + } + // Create a sectionSymbols entry for every progbits section. if (section->sh_type == llvm::ELF::SHT_PROGBITS) sectionSymbols[section]; @@ -136,6 +214,43 @@ public: } } + // Divide the section that contains mergeable strings into tokens + // TODO + // a) add resolver support to recognize multibyte chars + // b) Create a seperate section chunk to write mergeable atoms + std::vector<MergeString *> tokens; + for (auto msi : mergeStringSections) { + StringRef sectionContents; + StringRef sectionName; + if ((EC = _objFile->getSectionName(msi, sectionName))) + return; + + if ((EC = _objFile->getSectionContents(msi, sectionContents))) + return; + + unsigned int prev = 0; + for (std::size_t i = 0, e = sectionContents.size(); i != e; ++i) { + if (sectionContents[i] == '\0') { + tokens.push_back(new (_readerStorage) MergeString( + prev, sectionContents.slice(prev, i + 1), msi, sectionName)); + prev = i + 1; + } + } + } + + // Create Mergeable atoms + for (auto tai : tokens) { + ArrayRef<uint8_t> content((const uint8_t *)tai->_string.data(), + tai->_string.size()); + ELFMergeAtom<ELFT> *mergeAtom = new (_readerStorage) ELFMergeAtom<ELFT>( + *this, tai->_sectionName, tai->_shdr, content, tai->_offset); + const MergeSectionKey mergedSectionKey(tai->_shdr, tai->_offset); + if (_mergedSectionMap.find(mergedSectionKey) == _mergedSectionMap.end()) + _mergedSectionMap.insert(std::make_pair(mergedSectionKey, mergeAtom)); + _definedAtoms._atoms.push_back(mergeAtom); + _mergeAtoms.push_back(mergeAtom); + } + // Increment over all the symbols collecting atoms and symbol names for // later use. llvm::object::symbol_iterator it(_objFile->begin_symbols()); @@ -151,6 +266,15 @@ public: const Elf_Shdr *section = _objFile->getElfSection(sit); const Elf_Sym *symbol = _objFile->getElfSymbol(it); + // If its a merge section, the atoms have already + // been created, lets not create the atoms again + int64_t sectionFlags = section->sh_flags; + sectionFlags &= ~llvm::ELF::SHF_ALLOC; + if ((section->sh_entsize < 2) && + (sectionFlags == (llvm::ELF::SHF_MERGE | llvm::ELF::SHF_STRINGS))) { + continue; + } + StringRef symbolName; if ((EC = _objFile->getSymbolName(section, symbol, symbolName))) return; @@ -278,14 +402,12 @@ public: // Check to see if we need to add the FollowOn Reference // We dont want to do for symbols that are // a) common symbols - // b) the atoms have the merge attribute set // so, lets add a follow-on reference from the previous atom to the // current atom as well as lets add a preceded-by reference from the // current atom to the previous atom, so that the previous atom // is not removed in any case ELFReference<ELFT> *followOn = nullptr; - if (!isCommon && previous_atom && - previous_atom->merge() == DefinedAtom::mergeNo) { + if (!isCommon && previous_atom) { followOn = new (_readerStorage) ELFReference<ELFT>(lld::Reference::kindLayoutAfter); previous_atom->addReference(followOn); @@ -297,15 +419,22 @@ public: // If we are inserting a followOn reference, lets add a precededBy // reference too if (followOn) { - ELFReference<ELFT> *precededBy = nullptr; + ELFReference<ELFT> *precededby = nullptr; followOn->setTarget(newAtom); - precededBy = new (_readerStorage) - ELFReference<ELFT>(lld::Reference::kindLayoutBefore); - precededBy->setTarget(previous_atom); - newAtom->addReference(precededBy); + // Add a preceded by reference only if the current atom is not a + // weak atom + if ((*si)->getBinding() != llvm::ELF::STB_WEAK) { + precededby = new (_readerStorage) + ELFReference<ELFT>(lld::Reference::kindLayoutBefore); + precededby->setTarget(previous_atom); + newAtom->addReference(precededby); + } } - previous_atom = newAtom; + // The previous atom is always the atom created before unless + // the atom is a weak atom + if ((*si)->getBinding() != llvm::ELF::STB_WEAK) + previous_atom = newAtom; _definedAtoms._atoms.push_back(newAtom); _symbolToAtomMapping.insert(std::make_pair((*si), newAtom)); @@ -319,7 +448,31 @@ public: for (auto &ri : _references) { if (ri->kind() >= lld::Reference::kindTargetLow) { const Elf_Sym *Symbol = _objFile->getElfSymbol(ri->targetSymbolIndex()); - ri->setTarget(findAtom(Symbol)); + const Elf_Shdr *shdr = _objFile->getSection(Symbol); + int64_t sectionFlags = 0; + if (shdr) + sectionFlags = shdr->sh_flags; + sectionFlags &= ~llvm::ELF::SHF_ALLOC; + + // If the section has mergeable strings, then make the relocation + // refer to the MergeAtom to allow deduping + if (shdr && (shdr->sh_entsize < 2) && + (sectionFlags == (llvm::ELF::SHF_MERGE | llvm::ELF::SHF_STRINGS))) { + const MergeSectionKey ms(shdr, ri->addend()); + if (_mergedSectionMap.find(ms) == _mergedSectionMap.end()) { + MergeAtomsIter mai = findMergeAtom(ri->addend()); + if (mai != _mergeAtoms.end()) { + ri->setOffset(ri->addend() - ((*mai)->offset())); + ri->setAddend(0); + ri->setTarget(*mai); + } // check + else + llvm_unreachable("unable to find a merge atom"); + } // find + else + ri->setTarget(_mergedSectionMap[ms]); + } else + ri->setTarget(findAtom(Symbol)); } } } @@ -347,6 +500,7 @@ public: } private: + ELFDefinedAtom<ELFT> *createDefinedAtomAndAssignRelocations( StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol, const Elf_Shdr *section, ArrayRef<uint8_t> content) { @@ -380,6 +534,11 @@ private: (ri->r_offset < symbol->st_value + content.size())) { auto *ERef = new (_readerStorage) ELFReference<ELFT>(ri, ri->r_offset - symbol->st_value, nullptr); + // Read the addend from the section contents + // TODO : We should move the way lld reads relocations totally from + // ELFObjectFile + int32_t addend = *(content.data() + ri->r_offset - symbol->st_value); + ERef->setAddend(addend); _references.push_back(ERef); } } @@ -403,12 +562,14 @@ private: /// the SHT_REL(A) section name. std::unordered_map<StringRef, std::vector<const Elf_Rela *> > _relocationAddendRefences; + MergedSectionMapT _mergedSectionMap; std::unordered_map<StringRef, std::vector<const Elf_Rel *> > _relocationReferences; std::vector<ELFReference<ELFT> *> _references; llvm::DenseMap<const Elf_Sym *, Atom *> _symbolToAtomMapping; llvm::BumpPtrAllocator _readerStorage; const ELFTargetInfo &_elfTargetInfo; + MergeAtomsT _mergeAtoms; }; } // end namespace elf } // end namespace lld diff --git a/lld/test/elf/Inputs/bar.o.x86-64 b/lld/test/elf/Inputs/bar.o.x86-64 Binary files differnew file mode 100644 index 00000000000..467485f0bb9 --- /dev/null +++ b/lld/test/elf/Inputs/bar.o.x86-64 diff --git a/lld/test/elf/Inputs/constants-merge.x86-64 b/lld/test/elf/Inputs/constants-merge.x86-64 Binary files differnew file mode 100644 index 00000000000..0087eb8f8cb --- /dev/null +++ b/lld/test/elf/Inputs/constants-merge.x86-64 diff --git a/lld/test/elf/Inputs/foo.o.x86-64 b/lld/test/elf/Inputs/foo.o.x86-64 Binary files differnew file mode 100644 index 00000000000..72a89eefa8e --- /dev/null +++ b/lld/test/elf/Inputs/foo.o.x86-64 diff --git a/lld/test/elf/mergeatoms.objtxt b/lld/test/elf/mergeatoms.objtxt new file mode 100644 index 00000000000..f36c6c2e695 --- /dev/null +++ b/lld/test/elf/mergeatoms.objtxt @@ -0,0 +1,5 @@ +RUN: lld-core -reader ELF -writer ELF -o %t1 %p/Inputs/foo.o.x86-64 \ +RUN: %p/Inputs/bar.o.x86-64 +RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=mergeAtoms %s + +mergeAtoms: 1000 62617200 666f6f00 bar.foo. diff --git a/lld/test/elf/mergeconstants.objtxt b/lld/test/elf/mergeconstants.objtxt new file mode 100644 index 00000000000..bf5c8cf2e1e --- /dev/null +++ b/lld/test/elf/mergeconstants.objtxt @@ -0,0 +1,16 @@ +RUN: lld-core -reader ELF %p/Inputs/constants-merge.x86-64 | FileCheck -check-prefix=mergeAtoms %s + +mergeAtoms: - name: foo +mergeAtoms: scope: global +mergeAtoms: type: data +mergeAtoms: content: [ 00, 00, 00, 00, 00, 00, 00, 00 ] +mergeAtoms: alignment: 2^3 +mergeAtoms: section-choice: custom-required +mergeAtoms: section-name: .data +mergeAtoms: references: +mergeAtoms: - kind: <unknown> +mergeAtoms: offset: 3 +mergeAtoms: target: L001 +mergeAtoms: - kind: layout-before +mergeAtoms: offset: 0 +mergeAtoms: target: bar diff --git a/lld/test/elf/reloc.objtxt b/lld/test/elf/reloc.objtxt index 5dd776bd2ee..3eb22671eb6 100644 --- a/lld/test/elf/reloc.objtxt +++ b/lld/test/elf/reloc.objtxt @@ -1,73 +1,85 @@ RUN: lld-core -reader ELF %p/Inputs/reloc-test.elf-i386 | FileCheck %s -check-prefix ELF-i386 -ELF-i386:--- -ELF-i386:defined-atoms: -ELF-i386: - name: .text -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .text - -ELF-i386: - name: .data -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .data - -ELF-i386: - name: .bss -ELF-i386: type: zero-fill -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .bss - -ELF-i386: - name: .rodata.str1.1 -ELF-i386: type: constant -ELF-i386: content: [ 68, 65, 6C, 6C, 6F, 20, 77, 6F, 72, 6C, 64, 00 ] -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .rodata.str1.1 - -ELF-i386: - name: .text.startup -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .text.startup - -ELF-i386: - name: main -ELF-i386: scope: global -ELF-i386: content: [ 55, 89, E5, 83, E4, F0, 83, EC, 10, C7, 04, 24, -ELF-i386: 00, 00, 00, 00, E8, FC, FF, FF, FF, 31, C0, C9, -ELF-i386: C3 ] -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .text.startup -ELF-i386: references: -ELF-i386: - kind: <unknown> -ELF-i386: offset: 12 -ELF-i386: target: .rodata.str1.1 -ELF-i386: - kind: call32 -ELF-i386: offset: 17 -ELF-i386: target: puts - -ELF-i386: - name: .comment -ELF-i386: type: constant -ELF-i386: content: [ 00, 47, 43, 43, 3A, 20, 28, 47, 4E, 55, 29, 20, -ELF-i386: 34, 2E, 37, 2E, 30, 00 ] -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .comment - -ELF-i386: - name: .note.GNU-stack -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .note.GNU-stack - -ELF-i386: - name: .eh_frame -ELF-i386: content: [ 14, 00, 00, 00, 00, 00, 00, 00, 01, 7A, 52, 00, -ELF-i386: 01, 7C, 08, 01, 1B, 0C, 04, 04, 88, 01, 00, 00, -ELF-i386: 1C, 00, 00, 00, 1C, 00, 00, 00, 00, 00, 00, 00, -ELF-i386: 19, 00, 00, 00, 00, 41, 0E, 08, 85, 02, 42, 0D, -ELF-i386: 05, 55, C5, 0C, 04, 04, 00, 00 ] -ELF-i386: section-choice: custom-required -ELF-i386: section-name: .eh_frame -ELF-i386: references: -ELF-i386: - kind: call32 -ELF-i386: offset: 32 -ELF-i386: target: .text.startup - -ELF-i386:undefined-atoms: -ELF-i386: - name: puts - -ELF-i386:absolute-atoms: -ELF-i386: - name: test.c -ELF-i386: value: 0x0 -ELF-i386:... +ELF-i386: defined-atoms: +ELF-i386: - ref-name: L000 +ELF-i386: type: constant +ELF-i386: content: [ 68, 65, 6C, 6C, 6F, 20, 77, 6F, 72, 6C, 64, 00 ] +ELF-i386: merge: by-content +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .rodata.str1.1 +ELF-i386: - type: constant +ELF-i386: content: [ 00 ] +ELF-i386: merge: by-content +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .comment +ELF-i386: - type: constant +ELF-i386: content: [ 47, 43, 43, 3A, 20, 28, 47, 4E, 55, 29, 20, 34, +ELF-i386: 2E, 37, 2E, 30, 00 ] +ELF-i386: merge: by-content +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .comment +ELF-i386: - name: .text +ELF-i386: alignment: 2^2 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .text +ELF-i386: - name: .data +ELF-i386: type: data +ELF-i386: alignment: 2^2 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .data +ELF-i386: - name: .bss +ELF-i386: type: zero-fill +ELF-i386: alignment: 2^2 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .bss +ELF-i386: - name: .text.startup +ELF-i386: alignment: 2^4 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .text.startup +ELF-i386: references: +ELF-i386: - kind: layout-after +ELF-i386: offset: 0 +ELF-i386: target: main +ELF-i386: - name: main +ELF-i386: scope: global +ELF-i386: content: [ 55, 89, E5, 83, E4, F0, 83, EC, 10, C7, 04, 24, +ELF-i386: 00, 00, 00, 00, E8, FC, FF, FF, FF, 31, C0, C9, +ELF-i386: C3 ] +ELF-i386: alignment: 2^4 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .text.startup +ELF-i386: references: +ELF-i386: - kind: <unknown> +ELF-i386: offset: 12 +ELF-i386: target: L000 +ELF-i386: - kind: call32 +ELF-i386: offset: 17 +ELF-i386: target: puts +ELF-i386: addend: 252 +ELF-i386: - kind: layout-before +ELF-i386: offset: 0 +ELF-i386: target: .text.startup +ELF-i386: - name: .note.GNU-stack +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .note.GNU-stack +ELF-i386: permissions: r-- +ELF-i386: - name: .eh_frame +ELF-i386: content: [ 14, 00, 00, 00, 00, 00, 00, 00, 01, 7A, 52, 00, +ELF-i386: 01, 7C, 08, 01, 1B, 0C, 04, 04, 88, 01, 00, 00, +ELF-i386: 1C, 00, 00, 00, 1C, 00, 00, 00, 00, 00, 00, 00, +ELF-i386: 19, 00, 00, 00, 00, 41, 0E, 08, 85, 02, 42, 0D, +ELF-i386: 05, 55, C5, 0C, 04, 04, 00, 00 ] +ELF-i386: alignment: 2^2 +ELF-i386: section-choice: custom-required +ELF-i386: section-name: .eh_frame +ELF-i386: permissions: r-- +ELF-i386: references: +ELF-i386: - kind: call32 +ELF-i386: offset: 32 +ELF-i386: target: .text.startup +ELF-i386: undefined-atoms: +ELF-i386: - name: puts +ELF-i386: absolute-atoms: +ELF-i386: - name: test.c +ELF-i386: scope: static +ELF-i386: value: 0x0000000000000000 |