//===- Writer.cpp ---------------------------------------------------------===// // // The LLVM Linker // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #include "Writer.h" #include "Chunks.h" #include "Config.h" #include "Error.h" #include "Symbols.h" #include "SymbolTable.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/MC/StringTableBuilder.h" #include "llvm/Support/FileOutputBuffer.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; using namespace llvm::ELF; using namespace llvm::object; using namespace lld; using namespace lld::elf2; static const int PageSize = 4096; namespace { // 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 // creates multiple OutputSections and assign them unique, // non-overlapping file offsets and VAs. template class OutputSectionBase { public: typedef typename std::conditional::type uintX_t; typedef typename std::conditional::type HeaderT; OutputSectionBase(StringRef Name, uint32_t sh_type, uintX_t sh_flags) : Name(Name) { memset(&Header, 0, sizeof(HeaderT)); Header.sh_type = sh_type; 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); StringRef getName() { return Name; } void setNameOffset(uintX_t Offset) { Header.sh_name = Offset; } unsigned getSectionIndex() const { return SectionIndex; } void setSectionIndex(unsigned I) { SectionIndex = I; } // Returns the size of the section in the output file. uintX_t getSize() { return Header.sh_size; } void setSize(uintX_t Val) { Header.sh_size = Val; } uintX_t getFlags() { return Header.sh_flags; } uintX_t getFileOff() { return Header.sh_offset; } uintX_t getAlign() { // The ELF spec states that a value of 0 means the section has no alignment // constraits. return std::max(Header.sh_addralign, 1); } uint32_t getType() { return Header.sh_type; } virtual void finalize() {} virtual void writeTo(uint8_t *Buf) = 0; protected: StringRef Name; HeaderT Header; unsigned SectionIndex; ~OutputSectionBase() = default; }; } template class lld::elf2::OutputSection final : public OutputSectionBase { public: typedef typename OutputSectionBase::uintX_t uintX_t; typedef typename ELFFile::Elf_Shdr Elf_Shdr; typedef typename ELFFile::Elf_Rela Elf_Rela; OutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_flags) : OutputSectionBase(Name, sh_type, sh_flags) {} void addChunk(SectionChunk *C); void writeTo(uint8_t *Buf) override; private: std::vector *> Chunks; }; namespace { template class StringTableSection final : public OutputSectionBase { public: llvm::StringTableBuilder StrTabBuilder; typedef typename OutputSectionBase::uintX_t uintX_t; StringTableSection() : OutputSectionBase(".strtab", SHT_STRTAB, 0) { this->Header.sh_addralign = 1; } void add(StringRef S) { StrTabBuilder.add(S); } size_t getFileOff(StringRef S) { return StrTabBuilder.getOffset(S); } void writeTo(uint8_t *Buf) override; void finalize() override { StrTabBuilder.finalize(StringTableBuilder::ELF); this->Header.sh_size = StrTabBuilder.data().size(); } }; template class SymbolTableSection final : public OutputSectionBase { public: typedef typename ELFFile::Elf_Sym Elf_Sym; typedef typename OutputSectionBase::uintX_t uintX_t; SymbolTableSection(SymbolTable &Table, StringTableSection &StrTabSec) : OutputSectionBase(".symtab", SHT_SYMTAB, 0), Table(Table), Builder(StrTabSec.StrTabBuilder), StrTabSec(StrTabSec) { typedef OutputSectionBase Base; typename Base::HeaderT &Header = this->Header; // For now the only local symbol is going to be the one at index 0 Header.sh_info = 1; Header.sh_entsize = sizeof(Elf_Sym); Header.sh_addralign = ELFT::Is64Bits ? 8 : 4; } void finalize() override { this->Header.sh_size = (NumVisible + 1) * sizeof(Elf_Sym); this->Header.sh_link = StrTabSec.getSectionIndex(); } void writeTo(uint8_t *Buf) override; const SymbolTable &getSymTable() { return Table; } OutputSection *BSSSec = nullptr; unsigned NumVisible = 0; private: SymbolTable &Table; llvm::StringTableBuilder &Builder; const StringTableSection &StrTabSec; }; template class DynamicSection final : public OutputSectionBase { public: DynamicSection(const StringTableSection &StrTabSec) : OutputSectionBase(".dynamic", SHT_DYNAMIC, SHF_ALLOC | SHF_WRITE), StrTabSec(StrTabSec) { typedef OutputSectionBase Base; typename Base::HeaderT &Header = this->Header; Header.sh_addralign = Is64Bits ? 8 : 4; Header.sh_entsize = Is64Bits ? 16 : 8; } void finalize() override { this->Header.sh_link = StrTabSec.getSectionIndex(); } void writeTo(uint8_t *Buf) override {} private: const StringTableSection &StrTabSec; }; // The writer writes a SymbolTable result to a file. template class Writer { public: typedef typename ELFFile::uintX_t uintX_t; typedef typename ELFFile::Elf_Shdr Elf_Shdr; typedef typename ELFFile::Elf_Ehdr Elf_Ehdr; typedef typename ELFFile::Elf_Phdr Elf_Phdr; typedef typename ELFFile::Elf_Sym Elf_Sym; Writer(SymbolTable *T) : SymTable(*T, StringTable), DynamicSec(StringTable) {} void run(); private: void createSections(); void assignAddresses(); void openFile(StringRef OutputPath); void writeHeader(); void writeSections(); std::unique_ptr Buffer; llvm::SpecificBumpPtrAllocator> CAlloc; std::vector *> OutputSections; unsigned getNumSections() const { return OutputSections.size() + 1; } uintX_t FileSize; uintX_t SizeOfHeaders; uintX_t SectionHeaderOff; StringTableSection StringTable; SymbolTableSection SymTable; DynamicSection DynamicSec; }; } // anonymous namespace namespace lld { namespace elf2 { template void writeResult(SymbolTable *Symtab) { Writer(Symtab).run(); } template void writeResult(SymbolTable *); template void writeResult(SymbolTable *); template void writeResult(SymbolTable *); template void writeResult(SymbolTable *); } // namespace elf2 } // namespace lld // The main function of the writer. template void Writer::run() { createSections(); assignAddresses(); openFile(Config->OutputFile); writeHeader(); writeSections(); error(Buffer->commit()); } template void OutputSection::addChunk(SectionChunk *C) { Chunks.push_back(C); C->setOutputSection(this); uint32_t Align = C->getAlign(); if (Align > this->Header.sh_addralign) this->Header.sh_addralign = Align; uintX_t Off = this->Header.sh_size; Off = RoundUpToAlignment(Off, Align); C->setOutputSectionOff(Off); Off += C->getSize(); this->Header.sh_size = Off; } template static typename ELFFile::uintX_t getSymVA(DefinedRegular *DR) { const SectionChunk *SC = &DR->Section; OutputSection *OS = SC->getOutputSection(); return OS->getVA() + SC->getOutputSectionOff() + DR->Sym.st_value; } template void OutputSection::writeTo(uint8_t *Buf) { for (SectionChunk *C : Chunks) { C->writeTo(Buf); ObjectFile *File = C->getFile(); ELFFile *EObj = File->getObj(); uint8_t *Base = Buf + C->getOutputSectionOff(); // Iterate over all relocation sections that apply to this section. for (const Elf_Shdr *RelSec : C->RelocSections) { // Only support RELA for now. if (RelSec->sh_type != SHT_RELA) continue; for (const Elf_Rela &RI : EObj->relas(RelSec)) { uint32_t SymIndex = RI.getSymbol(EObj->isMips64EL()); SymbolBody *Body = File->getSymbolBody(SymIndex); if (!Body) continue; // Skip unsupported for now. if (!isa>(Body)) continue; uintX_t Offset = RI.r_offset; uint32_t Type = RI.getType(EObj->isMips64EL()); uintX_t P = this->getVA() + C->getOutputSectionOff(); uintX_t SymVA = getSymVA(cast>(Body)); uint8_t *Location = Base + Offset; switch (Type) { case llvm::ELF::R_X86_64_PC32: support::endian::write32le(Location, SymVA + (RI.r_addend - (P + Offset))); break; case llvm::ELF::R_X86_64_32: support::endian::write32le(Location, SymVA + RI.r_addend); break; default: llvm::errs() << Twine("unrecognized reloc ") + Twine(Type) << '\n'; break; } } } } } template void StringTableSection::writeTo(uint8_t *Buf) { StringRef Data = StrTabBuilder.data(); memcpy(Buf, Data.data(), Data.size()); } template static int compareSym(const typename ELFFile::Elf_Sym *A, const typename ELFFile::Elf_Sym *B) { uint32_t AN = A->st_name; uint32_t BN = B->st_name; assert(AN != BN); return AN - BN; } static bool includeInSymtab(const SymbolBody &B) { if (B.isLazy()) return false; if (!B.isUsedInRegularObj()) return false; uint8_t V = B.getMostConstrainingVisibility(); if (V != STV_DEFAULT && V != STV_PROTECTED) return false; return true; } template void SymbolTableSection::writeTo(uint8_t *Buf) { uint8_t *BufStart = Buf; Buf += sizeof(Elf_Sym); for (auto &P : Table.getSymbols()) { StringRef Name = P.first; Symbol *Sym = P.second; SymbolBody *Body = Sym->Body; if (!includeInSymtab(*Body)) continue; const Elf_Sym &InputSym = cast>(Body)->Sym; auto *ESym = reinterpret_cast(Buf); ESym->st_name = Builder.getOffset(Name); const SectionChunk *Section = nullptr; OutputSection *Out = nullptr; switch (Body->kind()) { case SymbolBody::DefinedRegularKind: Section = &cast>(Body)->Section; break; case SymbolBody::DefinedCommonKind: Out = BSSSec; break; case SymbolBody::UndefinedKind: if (!Body->isWeak()) error(Twine("undefined symbol: ") + Name); case SymbolBody::DefinedAbsoluteKind: case SymbolBody::SharedKind: break; case SymbolBody::LazyKind: llvm_unreachable("Lazy symbol got to output symbol table!"); } ESym->setBindingAndType(InputSym.getBinding(), InputSym.getType()); ESym->st_size = InputSym.st_size; ESym->setVisibility(Body->getMostConstrainingVisibility()); if (InputSym.isAbsolute()) { ESym->st_shndx = SHN_ABS; ESym->st_value = InputSym.st_value; } if (Section) Out = Section->getOutputSection(); if (Out) { ESym->st_shndx = Out->getSectionIndex(); uintX_t VA = Out->getVA(); if (Section) VA += Section->getOutputSectionOff(); if (auto *C = dyn_cast>(Body)) VA += C->OffsetInBSS; else VA += InputSym.st_value; ESym->st_value = VA; } Buf += sizeof(Elf_Sym); } // The order the global symbols are in is not defined. We can use an arbitrary // order, but it has to be reproducible. That is true even when cross linking. // The default hashing of StringRef produces different results on 32 and 64 // bit systems so we sort by st_name. That is arbitrary but deterministic. // FIXME: Experiment with passing in a custom hashing instead. auto *Syms = reinterpret_cast(BufStart); ++Syms; array_pod_sort(Syms, Syms + NumVisible, compareSym); } template template void OutputSectionBase::writeHeaderTo( typename ELFFile>::Elf_Shdr *SHdr) { SHdr->sh_name = Header.sh_name; SHdr->sh_type = Header.sh_type; SHdr->sh_flags = Header.sh_flags; SHdr->sh_addr = Header.sh_addr; SHdr->sh_offset = Header.sh_offset; SHdr->sh_size = Header.sh_size; SHdr->sh_link = Header.sh_link; SHdr->sh_info = Header.sh_info; SHdr->sh_addralign = Header.sh_addralign; SHdr->sh_entsize = Header.sh_entsize; } namespace { template struct SectionKey { typedef typename std::conditional::type uintX_t; StringRef Name; uint32_t sh_type; uintX_t sh_flags; }; } namespace llvm { template struct DenseMapInfo> { static SectionKey getEmptyKey() { return SectionKey{DenseMapInfo::getEmptyKey(), 0, 0}; } static SectionKey getTombstoneKey() { return SectionKey{DenseMapInfo::getTombstoneKey(), 0, 0}; } static unsigned getHashValue(const SectionKey &Val) { return hash_combine(Val.Name, Val.sh_type, Val.sh_flags); } static bool isEqual(const SectionKey &LHS, const SectionKey &RHS) { return DenseMapInfo::isEqual(LHS.Name, RHS.Name) && LHS.sh_type == RHS.sh_type && LHS.sh_flags == RHS.sh_flags; } }; } template static bool cmpAlign(const DefinedCommon *A, const DefinedCommon *B) { return A->MaxAlignment > B->MaxAlignment; } template static bool compSec(OutputSectionBase *A, OutputSectionBase *B) { // Place SHF_ALLOC sections first. return (A->getFlags() & SHF_ALLOC) && !(B->getFlags() & SHF_ALLOC); } // Create output section objects and add them to OutputSections. template void Writer::createSections() { SmallDenseMap, OutputSection *> Map; auto getSection = [&](StringRef Name, uint32_t sh_type, uintX_t sh_flags) -> OutputSection * { SectionKey Key{Name, sh_type, sh_flags}; OutputSection *&Sec = Map[Key]; if (!Sec) { Sec = new (CAlloc.Allocate()) OutputSection(Key.Name, Key.sh_type, Key.sh_flags); OutputSections.push_back(Sec); } return Sec; }; const SymbolTable &Symtab = SymTable.getSymTable(); for (const std::unique_ptr &FileB : Symtab.getObjectFiles()) { auto &File = cast>(*FileB); for (SectionChunk *C : File.getChunks()) { if (!C) continue; const Elf_Shdr *H = C->getSectionHdr(); OutputSection *Sec = getSection(C->getSectionName(), H->sh_type, H->sh_flags); Sec->addChunk(C); } } SymTable.BSSSec = getSection(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE); OutputSection *BSSSec = SymTable.BSSSec; // FIXME: Try to avoid the extra walk over all global symbols. unsigned &NumVisible = SymTable.NumVisible; llvm::StringTableBuilder &Builder = StringTable.StrTabBuilder; std::vector *> CommonSymbols; for (auto &P : Symtab.getSymbols()) { StringRef Name = P.first; SymbolBody *Body = P.second->Body; if (auto *C = dyn_cast>(Body)) CommonSymbols.push_back(C); if (!includeInSymtab(*Body)) continue; NumVisible++; Builder.add(Name); } // Sort the common symbols by alignment as an heuristic to pack them better. std::stable_sort(CommonSymbols.begin(), CommonSymbols.end(), cmpAlign); uintX_t Off = BSSSec->getSize(); for (DefinedCommon *C : CommonSymbols) { const Elf_Sym &Sym = C->Sym; uintX_t Align = C->MaxAlignment; Off = RoundUpToAlignment(Off, Align); C->OffsetInBSS = Off; Off += Sym.st_size; } BSSSec->setSize(Off); OutputSections.push_back(&SymTable); OutputSections.push_back(&StringTable); const std::vector> &SharedFiles = Symtab.getSharedFiles(); if (!SharedFiles.empty()) OutputSections.push_back(&DynamicSec); std::stable_sort(OutputSections.begin(), OutputSections.end(), compSec); for (unsigned I = 0, N = OutputSections.size(); I < N; ++I) OutputSections[I]->setSectionIndex(I + 1); } // Visits all sections to assign incremental, non-overlapping RVAs and // file offsets. template void Writer::assignAddresses() { SizeOfHeaders = RoundUpToAlignment(sizeof(Elf_Ehdr), PageSize); uintX_t VA = 0x1000; // The first page is kept unmapped. uintX_t FileOff = SizeOfHeaders; for (OutputSectionBase *Sec : OutputSections) { StringTable.add(Sec->getName()); Sec->finalize(); uintX_t Align = Sec->getAlign(); uintX_t Size = Sec->getSize(); if (Sec->getFlags() & SHF_ALLOC) { Sec->setVA(VA); VA += RoundUpToAlignment(Size, Align); } Sec->setFileOffset(FileOff); if (Sec->getType() != SHT_NOBITS) FileOff += RoundUpToAlignment(Size, Align); } FileOff += OffsetToAlignment(FileOff, ELFT::Is64Bits ? 8 : 4); // Add space for section headers. SectionHeaderOff = FileOff; FileOff += getNumSections() * sizeof(Elf_Shdr); FileSize = SizeOfHeaders + RoundUpToAlignment(FileOff - SizeOfHeaders, 8); } template void Writer::writeHeader() { uint8_t *Buf = Buffer->getBufferStart(); auto *EHdr = reinterpret_cast(Buf); EHdr->e_ident[EI_MAG0] = 0x7F; EHdr->e_ident[EI_MAG1] = 0x45; EHdr->e_ident[EI_MAG2] = 0x4C; EHdr->e_ident[EI_MAG3] = 0x46; EHdr->e_ident[EI_CLASS] = ELFT::Is64Bits ? ELFCLASS64 : ELFCLASS32; EHdr->e_ident[EI_DATA] = ELFT::TargetEndianness == llvm::support::little ? ELFDATA2LSB : ELFDATA2MSB; EHdr->e_ident[EI_VERSION] = EV_CURRENT; EHdr->e_ident[EI_OSABI] = ELFOSABI_NONE; EHdr->e_type = ET_EXEC; const SymbolTable &Symtab = SymTable.getSymTable(); auto &FirstObj = cast>(*Symtab.getFirstELF()); EHdr->e_machine = FirstObj.getEMachine(); EHdr->e_version = EV_CURRENT; EHdr->e_entry = getSymVA( cast>(Symtab.getEntrySym()->getReplacement())); EHdr->e_phoff = sizeof(Elf_Ehdr); EHdr->e_shoff = SectionHeaderOff; EHdr->e_ehsize = sizeof(Elf_Ehdr); EHdr->e_phentsize = sizeof(Elf_Phdr); EHdr->e_phnum = 1; EHdr->e_shentsize = sizeof(Elf_Shdr); EHdr->e_shnum = getNumSections(); EHdr->e_shstrndx = StringTable.getSectionIndex(); auto PHdrs = reinterpret_cast(Buf + EHdr->e_phoff); PHdrs->p_type = PT_LOAD; PHdrs->p_flags = PF_R | PF_X; PHdrs->p_offset = 0x0000; PHdrs->p_vaddr = 0x400000; PHdrs->p_paddr = PHdrs->p_vaddr; PHdrs->p_filesz = FileSize; PHdrs->p_memsz = FileSize; PHdrs->p_align = 0x4000; auto SHdrs = reinterpret_cast(Buf + EHdr->e_shoff); // First entry is null. ++SHdrs; for (OutputSectionBase *Sec : OutputSections) { Sec->setNameOffset(StringTable.getFileOff(Sec->getName())); Sec->template writeHeaderTo(SHdrs++); } } template void Writer::openFile(StringRef Path) { ErrorOr> BufferOrErr = FileOutputBuffer::create(Path, FileSize, FileOutputBuffer::F_executable); error(BufferOrErr, Twine("failed to open ") + Path); Buffer = std::move(*BufferOrErr); } // Write section contents to a mmap'ed file. template void Writer::writeSections() { uint8_t *Buf = Buffer->getBufferStart(); for (OutputSectionBase *Sec : OutputSections) Sec->writeTo(Buf + Sec->getFileOff()); }