Index: ELF/Chunks.h =================================================================== --- ELF/Chunks.h +++ ELF/Chunks.h @@ -18,6 +18,7 @@ class Defined; template class ObjectFile; +template class OutputSection; // A chunk corresponding a section of an input file. template class SectionChunk { @@ -26,7 +27,7 @@ typedef llvm::object::Elf_Rel_Impl Elf_Rel; public: - SectionChunk(llvm::object::ELFFile *Obj, const Elf_Shdr *Header); + SectionChunk(ObjectFile *F, const Elf_Shdr *Header); // Returns the size of this chunk (even if this is a common or BSS.) size_t getSize() const { return Header->sh_size; } @@ -37,6 +38,9 @@ StringRef getSectionName() const; const Elf_Shdr *getSectionHdr() const { return Header; } + ObjectFile *getFile() { return File; } + void setOutputSection(OutputSection *S) { OS = S; } + OutputSection *getOutputSection() { return OS; } // The writer sets and uses the addresses. uint64_t getOutputSectionOff() { return OutputSectionOff; } @@ -51,8 +55,11 @@ // The alignment of this chunk. The writer uses the value. uint32_t Align = 1; - // A file this chunk was created from. - llvm::object::ELFFile *Obj; + // The file this chunk was created from. + ObjectFile *File; + + // The OutputSection this is assigned to. + OutputSection *OS; const Elf_Shdr *Header; }; Index: ELF/Chunks.cpp =================================================================== --- ELF/Chunks.cpp +++ ELF/Chunks.cpp @@ -9,6 +9,7 @@ #include "Chunks.h" #include "Error.h" +#include "InputFiles.h" using namespace llvm; using namespace llvm::ELF; @@ -17,9 +18,8 @@ using namespace lld::elf2; template -SectionChunk::SectionChunk(object::ELFFile *Obj, - const Elf_Shdr *Header) - : Obj(Obj), Header(Header) { +SectionChunk::SectionChunk(ObjectFile *F, const Elf_Shdr *Header) + : File(F), Header(Header), OS(nullptr) { Align = Header->sh_addralign; } @@ -27,14 +27,14 @@ if (Header->sh_type == SHT_NOBITS) return; // Copy section contents from source object file to output file. - ArrayRef Data = *Obj->getSectionContents(Header); + ArrayRef Data = *File->getObj()->getSectionContents(Header); memcpy(Buf + OutputSectionOff, Data.data(), Data.size()); // FIXME: Relocations } template StringRef SectionChunk::getSectionName() const { - ErrorOr Name = Obj->getSectionName(Header); + ErrorOr Name = File->getObj()->getSectionName(Header); error(Name); return *Name; } Index: ELF/InputFiles.h =================================================================== --- ELF/InputFiles.h +++ ELF/InputFiles.h @@ -11,6 +11,7 @@ #define LLD_ELF_INPUT_FILES_H #include "Chunks.h" +#include "Error.h" #include "lld/Core/LLVM.h" #include "llvm/Object/ELF.h" @@ -67,6 +68,21 @@ typedef typename llvm::object::ELFFile::Elf_Sym_Range Elf_Sym_Range; public: + struct RelocMapInfo { + RelocMapInfo(const Elf_Shdr *S, const Elf_Shdr *RS) + : Section(S), RelocSection(RS) {} + + const Elf_Shdr *Section; + const Elf_Shdr *RelocSection; + + bool operator<(const RelocMapInfo &Other) const { + // Pointer comparison is stable here as all pointers in a given RelocMap + // point to a single memory mapped file. + return std::tie(Section, RelocSection) < + std::tie(Other.Section, Other.RelocSection); + } + }; + bool isCompatibleWith(const ObjectFileBase &Other) const override; static Kind getKind() { @@ -84,12 +100,23 @@ explicit ObjectFile(MemoryBufferRef M) : ObjectFileBase(getKind(), M) {} void parse() override; + const std::vector &getRelocations() const { return RelocMap; } + + SymbolBody *getSymbolBody(uint32_t SymbolIndex) { + // Skip null symbol. + SymbolIndex -= 1; + if (SymbolIndex >= SymbolBodies.size()) + error("Invalid symbol table index."); + return SymbolBodies[SymbolIndex]->getReplacement(); + } // Returns the underying ELF file. llvm::object::ELFFile *getObj() const { return ELFObj.get(); } ArrayRef *> getChunks() { return Chunks; } + const Elf_Shdr *getSymtab() const { return Symtab; } + private: void initializeChunks(); void initializeSymbols(); @@ -102,6 +129,13 @@ std::vector *> Chunks; const Elf_Shdr *Symtab = nullptr; + // Section index to SectionChunk map. Unmapped sections are nullptr. + std::vector *> SparseChunks; + + // This vector contains a sorted list of pairs. This is used to quickly find and iterate over + // the relocations for a given section. + std::vector RelocMap; }; } // namespace elf2 Index: ELF/InputFiles.cpp =================================================================== --- ELF/InputFiles.cpp +++ ELF/InputFiles.cpp @@ -40,22 +40,33 @@ template void elf2::ObjectFile::initializeChunks() { uint64_t Size = ELFObj->getNumSections(); Chunks.reserve(Size); + SparseChunks.reserve(Size); for (const Elf_Shdr &Sec : ELFObj->sections()) { + SectionChunk *SC = nullptr; switch (Sec.sh_type) { case SHT_SYMTAB: Symtab = &Sec; break; case SHT_STRTAB: case SHT_NULL: + break; case SHT_RELA: - case SHT_REL: + case SHT_REL: { + auto RelocatedSec = ELFObj->getSection(Sec.sh_info); + if (!RelocatedSec) + error(RelocatedSec); + RelocMap.emplace_back(*RelocatedSec, &Sec); break; + } default: - auto *C = new (Alloc) SectionChunk(this->getObj(), &Sec); - Chunks.push_back(C); + SC = new (Alloc) SectionChunk(this, &Sec); + Chunks.push_back(SC); break; } + SparseChunks.push_back(SC); } + assert(SparseChunks.size() == Size && "Not all chunks added to SparseChunks"); + std::sort(RelocMap.begin(), RelocMap.end()); } template void elf2::ObjectFile::initializeSymbols() { @@ -87,7 +98,8 @@ case STB_GLOBAL: if (Sym->isUndefined()) return new (Alloc) Undefined(Name); - return new (Alloc) DefinedRegular(Name); + return new (Alloc) + DefinedRegular(Name, Sym, SparseChunks[Sym->st_shndx]); case STB_WEAK: if (Sym->isUndefined()) return new (Alloc) UndefinedWeak(Name); Index: ELF/Symbols.h =================================================================== --- ELF/Symbols.h +++ ELF/Symbols.h @@ -10,6 +10,8 @@ #ifndef LLD_ELF_SYMBOLS_H #define LLD_ELF_SYMBOLS_H +#include "Chunks.h" + #include "lld/Core/LLVM.h" #include "llvm/Object/ELF.h" @@ -85,13 +87,25 @@ }; // Regular defined symbols read from object file symbol tables. -class DefinedRegular : public Defined { +template class DefinedRegular : public Defined { + typedef typename llvm::object::ELFFile::Elf_Sym Elf_Sym; + public: - explicit DefinedRegular(StringRef N) : Defined(DefinedRegularKind, N) {} + explicit DefinedRegular(StringRef N, const Elf_Sym *S, SectionChunk *C); static bool classof(const SymbolBody *S) { return S->kind() == DefinedRegularKind; } + + typename llvm::object::ELFFile::uintX_t getValue() const { + return Sym->st_value; + } + + SectionChunk *getChunk() const { return Chunk; } + +private: + const Elf_Sym *Sym; + SectionChunk *Chunk; }; class DefinedWeak : public Defined { Index: ELF/Symbols.cpp =================================================================== --- ELF/Symbols.cpp +++ ELF/Symbols.cpp @@ -17,6 +17,11 @@ using namespace lld; using namespace lld::elf2; +template +DefinedRegular::DefinedRegular(StringRef N, const Elf_Sym *S, + SectionChunk *C) + : Defined(DefinedRegularKind, N), Sym(S), Chunk(C) {} + // Returns 1, 0 or -1 if this symbol should take precedence // over the Other, tie or lose, respectively. int SymbolBody::compare(SymbolBody *Other) { @@ -42,3 +47,12 @@ } llvm_unreachable("unknown symbol kind"); } + +namespace lld { +namespace elf2 { +template class DefinedRegular; +template class DefinedRegular; +template class DefinedRegular; +template class DefinedRegular; +} +} Index: ELF/Writer.cpp =================================================================== --- ELF/Writer.cpp +++ ELF/Writer.cpp @@ -10,6 +10,7 @@ #include "Chunks.h" #include "Config.h" #include "Error.h" +#include "Symbols.h" #include "SymbolTable.h" #include "Writer.h" @@ -26,7 +27,8 @@ static const int PageSize = 4096; -namespace { +namespace lld { +namespace elf2 { // OutputSection represents a section in an output file. It's a // container of chunks. OutputSection and Chunk are 1:N relationship. // Chunks cannot belong to more than one OutputSections. The writer @@ -45,6 +47,7 @@ Header.sh_flags = sh_flags; } void setVA(uintX_t VA) { Header.sh_addr = VA; } + uintX_t getVA() { return Header.sh_addr; } void setFileOffset(uintX_t Off) { Header.sh_offset = Off; } template void writeHeaderTo(typename ELFFile>::Elf_Shdr *SHdr); @@ -79,7 +82,10 @@ private: std::vector *> Chunks; }; +} // end namespace elf2 +} // end namespace lld +namespace { template class StringTableSection final : public OutputSectionBase { llvm::StringTableBuilder StrTabBuilder; @@ -169,9 +175,51 @@ this->Header.sh_size = Off; } +template +typename llvm::object::ELFFile::uintX_t +getSymVA(DefinedRegular *DR) { + SectionChunk *SC = DR->getChunk(); + OutputSection *OS = SC->getOutputSection(); + return OS->getVA() + SC->getOutputSectionOff() + DR->getValue(); +} + template void OutputSection::writeTo(uint8_t *Buf) { - for (SectionChunk *C : Chunks) + for (SectionChunk *C : Chunks) { C->writeTo(Buf); + const std::vector::RelocMapInfo> &Relocs = + C->getFile()->getRelocations(); + auto Hdr = C->getSectionHdr(); + auto EObj = C->getFile()->getObj(); + uint8_t *Base = Buf + C->getOutputSectionOff(); + // Iterate over all relocation sections that apply to this section. + for (auto I = std::lower_bound( + Relocs.begin(), Relocs.end(), + typename ObjectFile::RelocMapInfo(Hdr, nullptr)), + E = Relocs.end(); + I != E && I->Section == Hdr; ++I) { + // Only support RELA for now. + if (I->RelocSection->sh_type != SHT_RELA) + continue; + for (auto &RI : EObj->relas(I->RelocSection)) { + SymbolBody *Body = + C->getFile() + ->getSymbolBody(RI.getSymbol(EObj->isMips64EL())) + ->getReplacement(); + uintX_t Offset = RI.r_offset; + uint32_t Type = RI.getType(EObj->isMips64EL()); + uintX_t P = getVA() + C->getOutputSectionOff(); + uintX_t SymVA = getSymVA(cast>(Body)); + switch (Type) { + case llvm::ELF::R_X86_64_PC32: + support::endian::write32le(Base + Offset, + SymVA + (RI.r_addend - (P + Offset))); + break; + default: + error(Twine("unrecognized reloc ") + Twine(Type)); + } + } + } + } } template @@ -240,6 +288,7 @@ OutputSections.push_back(Sec); } Sec->addChunk(C); + C->setOutputSection(Sec); } } } Index: test/elf2/relocation.test =================================================================== --- /dev/null +++ test/elf2/relocation.test @@ -0,0 +1,57 @@ +# RUN: yaml2obj -format elf %s -docnum 1 -o %t1obj +# RUN: yaml2obj -format elf %s -docnum 2 -o %t2obj +# RUN: lld -flavor gnu2 %t1obj %t2obj -o %tout +# RUN: llvm-objdump -d %tout | FileCheck %s +# REQUIRES: x86 + +--- +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + OSABI: ELFOSABI_GNU + Type: ET_REL + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x0000000000000004 + Content: E800000000 + - Name: .rela.text + Type: SHT_RELA + Link: .symtab + AddressAlign: 0x0000000000000008 + Info: .text + Relocations: + - Offset: 0x0000000000000001 + Symbol: lulz + Type: R_X86_64_PC32 + Addend: -4 +Symbols: + Global: + - Name: _start + Type: STT_FUNC + Section: .text + - Name: lulz +--- +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + OSABI: ELFOSABI_GNU + Type: ET_REL + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x0000000000000004 + Content: 5548C7C03C00000048C7C7010000000F05 +Symbols: + Global: + - Name: lulz + Type: STT_FUNC + Section: .text + Value: 0 +... + +# CHECK: e8 03 00 00 00 callq 3