Index: lld/trunk/CMakeLists.txt =================================================================== --- lld/trunk/CMakeLists.txt +++ lld/trunk/CMakeLists.txt @@ -97,3 +97,4 @@ add_subdirectory(docs) add_subdirectory(COFF) +add_subdirectory(ELF) Index: lld/trunk/ELF/CMakeLists.txt =================================================================== --- lld/trunk/ELF/CMakeLists.txt +++ lld/trunk/ELF/CMakeLists.txt @@ -0,0 +1,20 @@ +set(LLVM_TARGET_DEFINITIONS Options.td) +tablegen(LLVM Options.inc -gen-opt-parser-defs) +add_public_tablegen_target(ELFOptionsTableGen) + +add_llvm_library(lldELF2 + Chunks.cpp + Driver.cpp + DriverUtils.cpp + InputFiles.cpp + SymbolTable.cpp + Symbols.cpp + Writer.cpp + + LINK_COMPONENTS + Object + Option + Support + ) + +add_dependencies(lldELF2 ELFOptionsTableGen) Index: lld/trunk/ELF/Chunks.h =================================================================== --- lld/trunk/ELF/Chunks.h +++ lld/trunk/ELF/Chunks.h @@ -0,0 +1,93 @@ +//===- Chunks.h -----------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_CHUNKS_H +#define LLD_ELF_CHUNKS_H + +#include "lld/Core/LLVM.h" +#include "llvm/Object/ELF.h" + +namespace lld { +namespace elf2 { + +class Defined; +template class ObjectFile; +class OutputSection; + +// A Chunk represents a chunk of data that will occupy space in the +// output (if the resolver chose that). It may or may not be backed by +// a section of an input file. It could be linker-created data, or +// doesn't even have actual data (if common or bss). +class Chunk { +public: + virtual ~Chunk() = default; + + // Returns the size of this chunk (even if this is a common or BSS.) + virtual size_t getSize() const = 0; + + // Write this chunk to a mmap'ed file, assuming Buf is pointing to + // beginning of the file. Because this function may use VA values + // of other chunks for relocations, you need to set them properly + // before calling this function. + virtual void writeTo(uint8_t *Buf) = 0; + + // The writer sets and uses the addresses. + uint64_t getVA() { return VA; } + uint64_t getFileOff() { return FileOff; } + uint32_t getAlign() { return Align; } + void setVA(uint64_t V) { VA = V; } + void setFileOff(uint64_t V) { FileOff = V; } + + // Returns the section name if this is a section chunk. + // It is illegal to call this function on non-section chunks. + virtual StringRef getSectionName() const = 0; + + // An output section has pointers to chunks in the section, and each + // chunk has a back pointer to an output section. + void setOutputSection(OutputSection *O) { Out = O; } + OutputSection *getOutputSection() { return Out; } + +protected: + // The VA of this chunk in the output. The writer sets a value. + uint64_t VA = 0; + + // The offset from beginning of the output file. The writer sets a value. + uint64_t FileOff = 0; + + // The output section for this chunk. + OutputSection *Out = nullptr; + + // The alignment of this chunk. The writer uses the value. + uint32_t Align = 1; +}; + +// A chunk corresponding a section of an input file. +template class SectionChunk : public Chunk { + typedef llvm::object::Elf_Shdr_Impl Elf_Shdr; + typedef llvm::object::Elf_Rel_Impl Elf_Rela; + typedef llvm::object::Elf_Rel_Impl Elf_Rel; + +public: + SectionChunk(llvm::object::ELFFile *Obj, const Elf_Shdr *Header); + size_t getSize() const override { return Header->sh_size; } + void writeTo(uint8_t *Buf) override; + StringRef getSectionName() const override { return SectionName; } + +private: + // A file this chunk was created from. + llvm::object::ELFFile *Obj; + + const Elf_Shdr *Header; + StringRef SectionName; +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/Chunks.cpp =================================================================== --- lld/trunk/ELF/Chunks.cpp +++ lld/trunk/ELF/Chunks.cpp @@ -0,0 +1,48 @@ +//===- Chunks.cpp ---------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "Chunks.h" +#include "Driver.h" + +using namespace llvm; +using namespace llvm::ELF; + +using namespace lld; +using namespace lld::elf2; + +template +SectionChunk::SectionChunk(object::ELFFile *Obj, + const Elf_Shdr *Header) + : Obj(Obj), Header(Header) { + // Initialize SectionName. + ErrorOr Name = Obj->getSectionName(Header); + error(Name); + SectionName = *Name; + + Align = Header->sh_addralign; +} + +template void SectionChunk::writeTo(uint8_t *Buf) { + if (Header->sh_type == SHT_NOBITS) + return; + // Copy section contents from source object file to output file. + ArrayRef Data = *Obj->getSectionContents(Header); + memcpy(Buf + FileOff, Data.data(), Data.size()); + + // FIXME: Relocations +} + +namespace lld { +namespace elf2 { +template class SectionChunk; +template class SectionChunk; +template class SectionChunk; +template class SectionChunk; +} +} Index: lld/trunk/ELF/Config.h =================================================================== --- lld/trunk/ELF/Config.h +++ lld/trunk/ELF/Config.h @@ -0,0 +1,27 @@ +//===- Config.h -----------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_CONFIG_H +#define LLD_ELF_CONFIG_H + +#include "llvm/ADT/StringRef.h" + +namespace lld { +namespace elf2 { + +struct Configuration { + llvm::StringRef OutputFile; +}; + +extern Configuration *Config; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/Driver.h =================================================================== --- lld/trunk/ELF/Driver.h +++ lld/trunk/ELF/Driver.h @@ -0,0 +1,67 @@ +//===- Driver.h -----------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_DRIVER_H +#define LLD_ELF_DRIVER_H + +#include "lld/Core/LLVM.h" +#include "llvm/Option/ArgList.h" + +namespace lld { +namespace elf2 { + +class LinkerDriver; +extern LinkerDriver *Driver; + +class InputFile; + +// Entry point of the ELF linker. +void link(ArrayRef Args); + +void error(Twine Msg); +void error(std::error_code EC, Twine Prefix); +void error(std::error_code EC); +template void error(const ErrorOr &V, Twine Prefix) { + error(V.getError(), Prefix); +} +template void error(const ErrorOr &V) { error(V.getError()); } + +class ArgParser { +public: + // Parses command line options. + llvm::opt::InputArgList parse(ArrayRef Args); +}; + +class LinkerDriver { +public: + void link(ArrayRef Args); + +private: + ArgParser Parser; + + // Opens a file. Path has to be resolved already. + MemoryBufferRef openFile(StringRef Path); + + // Driver is the owner of all opened files. + // InputFiles have MemoryBufferRefs to them. + std::vector> OwningMBs; +}; + +// Create enum with OPT_xxx values for each option in Options.td +enum { + OPT_INVALID = 0, +#define OPTION(_1, _2, ID, _4, _5, _6, _7, _8, _9, _10, _11) OPT_##ID, +#include "Options.inc" +#undef OPTION +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/Driver.cpp =================================================================== --- lld/trunk/ELF/Driver.cpp +++ lld/trunk/ELF/Driver.cpp @@ -0,0 +1,104 @@ +//===- Driver.cpp ---------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "Driver.h" +#include "Config.h" +#include "Writer.h" +#include "llvm/ADT/STLExtras.h" + +using namespace llvm; + +using namespace lld; +using namespace lld::elf2; + +namespace lld { +namespace elf2 { +Configuration *Config; +LinkerDriver *Driver; + +void link(ArrayRef Args) { + auto C = make_unique(); + Config = C.get(); + auto D = make_unique(); + Driver = D.get(); + Driver->link(Args.slice(1)); +} + +void error(Twine Msg) { + errs() << Msg << "\n"; + exit(1); +} + +void error(std::error_code EC, Twine Prefix) { + if (!EC) + return; + error(Prefix + ": " + EC.message()); +} + +void error(std::error_code EC) { + if (!EC) + return; + error(EC.message()); +} +} +} + +// Opens a file. Path has to be resolved already. +// Newly created memory buffers are owned by this driver. +MemoryBufferRef LinkerDriver::openFile(StringRef Path) { + ErrorOr> MBOrErr = MemoryBuffer::getFile(Path); + error(MBOrErr, Twine("cannot open ") + Path); + std::unique_ptr &MB = *MBOrErr; + MemoryBufferRef MBRef = MB->getMemBufferRef(); + OwningMBs.push_back(std::move(MB)); // take ownership + return MBRef; +} + +static std::unique_ptr createFile(MemoryBufferRef MB) { + return std::unique_ptr(new ObjectFile(MB)); +} + +void LinkerDriver::link(ArrayRef ArgsArr) { + // Parse command line options. + opt::InputArgList Args = Parser.parse(ArgsArr); + + // Handle -o + if (auto *Arg = Args.getLastArg(OPT_output)) + Config->OutputFile = Arg->getValue(); + if (Config->OutputFile.empty()) + error("-o must be specified."); + + // Create a list of input files. + std::vector Inputs; + + for (auto *Arg : Args.filtered(OPT_INPUT)) { + StringRef Path = Arg->getValue(); + Inputs.push_back(openFile(Path)); + } + + if (Inputs.empty()) + error("no input files."); + + // Create a symbol table. + SymbolTable Symtab; + + // Parse all input files and put all symbols to the symbol table. + // The symbol table will take care of name resolution. + for (MemoryBufferRef MB : Inputs) { + std::unique_ptr File = createFile(MB); + Symtab.addFile(std::move(File)); + } + + // Make sure we have resolved all symbols. + Symtab.reportRemainingUndefines(); + + // Write the result. + Writer Out(&Symtab); + Out.write(Config->OutputFile); +} Index: lld/trunk/ELF/DriverUtils.cpp =================================================================== --- lld/trunk/ELF/DriverUtils.cpp +++ lld/trunk/ELF/DriverUtils.cpp @@ -0,0 +1,63 @@ +//===- DriverUtils.cpp ----------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains utility functions for the driver. Because there +// are so many small functions, we created this separate file to make +// Driver.cpp less cluttered. +// +//===----------------------------------------------------------------------===// + +#include "Driver.h" +#include "llvm/ADT/STLExtras.h" + +using namespace llvm; + +using namespace lld; +using namespace lld::elf2; + +// Create OptTable + +// Create prefix string literals used in Options.td +#define PREFIX(NAME, VALUE) const char *const NAME[] = VALUE; +#include "Options.inc" +#undef PREFIX + +// Create table mapping all options defined in Options.td +static const opt::OptTable::Info infoTable[] = { +#define OPTION(X1, X2, ID, KIND, GROUP, ALIAS, X6, X7, X8, X9, X10) \ + { \ + X1, X2, X9, X10, OPT_##ID, opt::Option::KIND##Class, X8, X7, OPT_##GROUP, \ + OPT_##ALIAS, X6 \ + } \ + , +#include "Options.inc" +#undef OPTION +}; + +class ELFOptTable : public opt::OptTable { +public: + ELFOptTable() : OptTable(infoTable, array_lengthof(infoTable)) {} +}; + +// Parses a given list of options. +opt::InputArgList ArgParser::parse(ArrayRef Argv) { + // Make InputArgList from string vectors. + ELFOptTable Table; + unsigned MissingIndex; + unsigned MissingCount; + + opt::InputArgList Args = Table.ParseArgs(Argv, MissingIndex, MissingCount); + if (MissingCount) + error(Twine("missing arg value for \"") + Args.getArgString(MissingIndex) + + "\", expected " + Twine(MissingCount) + + (MissingCount == 1 ? " argument.\n" : " arguments")); + for (auto *Arg : Args.filtered(OPT_UNKNOWN)) + error(Twine("unknown argument: ") + Arg->getSpelling()); + return Args; +} Index: lld/trunk/ELF/InputFiles.h =================================================================== --- lld/trunk/ELF/InputFiles.h +++ lld/trunk/ELF/InputFiles.h @@ -0,0 +1,78 @@ +//===- InputFiles.h -------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_INPUT_FILES_H +#define LLD_ELF_INPUT_FILES_H + +#include "lld/Core/LLVM.h" +#include "llvm/Object/ELF.h" + +namespace lld { +namespace elf2 { +class SymbolBody; +class Chunk; + +// The root class of input files. +class InputFile { +public: + enum Kind { ObjectKind }; + Kind kind() const { return FileKind; } + virtual ~InputFile() {} + + // Returns symbols defined by this file. + virtual ArrayRef getSymbols() = 0; + + // Reads a file (constructors don't do that). + virtual void parse() = 0; + +protected: + explicit InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {} + MemoryBufferRef MB; + +private: + const Kind FileKind; +}; + +// .o file. +template class ObjectFile : public InputFile { + typedef typename llvm::object::ELFFile::Elf_Sym Elf_Sym; + typedef typename llvm::object::ELFFile::Elf_Shdr Elf_Shdr; + typedef typename llvm::object::ELFFile::Elf_Sym_Range Elf_Sym_Range; + +public: + explicit ObjectFile(MemoryBufferRef M) : InputFile(ObjectKind, M) {} + static bool classof(const InputFile *F) { return F->kind() == ObjectKind; } + void parse() override; + ArrayRef getChunks() { return Chunks; } + ArrayRef getSymbols() override { return SymbolBodies; } + + // Returns the underying ELF file. + llvm::object::ELFFile *getObj() { return ELFObj.get(); } + +private: + void initializeChunks(); + void initializeSymbols(); + + SymbolBody *createSymbolBody(StringRef StringTable, const Elf_Sym *Sym); + + std::unique_ptr> ELFObj; + llvm::BumpPtrAllocator Alloc; + + // List of all chunks defined by this file. This includes both section + // chunks and non-section chunks for common symbols. + std::vector Chunks; + + // List of all symbols referenced or defined by this file. + std::vector SymbolBodies; +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/InputFiles.cpp =================================================================== --- lld/trunk/ELF/InputFiles.cpp +++ lld/trunk/ELF/InputFiles.cpp @@ -0,0 +1,78 @@ +//===- InputFiles.cpp -----------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "InputFiles.h" +#include "Chunks.h" +#include "Symbols.h" +#include "Driver.h" +#include "llvm/ADT/STLExtras.h" + +using namespace llvm::ELF; + +using namespace lld; +using namespace lld::elf2; + +template void elf2::ObjectFile::parse() { + // Parse a memory buffer as a ELF file. + std::error_code EC; + ELFObj = llvm::make_unique>(MB.getBuffer(), EC); + error(EC); + + // Read section and symbol tables. + initializeChunks(); + initializeSymbols(); +} + +template void elf2::ObjectFile::initializeChunks() { + uint64_t Size = ELFObj->getNumSections(); + Chunks.reserve(Size); + for (const Elf_Shdr &Sec : ELFObj->sections()) { + if (Sec.sh_flags & SHF_ALLOC) { + auto *C = new (Alloc) SectionChunk(this->getObj(), &Sec); + Chunks.push_back(C); + } + } +} + +template void elf2::ObjectFile::initializeSymbols() { + const Elf_Shdr *Symtab = ELFObj->getDotSymtabSec(); + ErrorOr StringTableOrErr = + ELFObj->getStringTableForSymtab(*Symtab); + error(StringTableOrErr.getError()); + StringRef StringTable = *StringTableOrErr; + + Elf_Sym_Range Syms = ELFObj->symbols(); + Syms = Elf_Sym_Range(Syms.begin() + 1, Syms.end()); + auto NumSymbols = std::distance(Syms.begin(), Syms.end()); + SymbolBodies.reserve(NumSymbols); + for (const Elf_Sym &Sym : Syms) { + if (SymbolBody *Body = createSymbolBody(StringTable, &Sym)) + SymbolBodies.push_back(Body); + } +} + +template +SymbolBody *elf2::ObjectFile::createSymbolBody(StringRef StringTable, + const Elf_Sym *Sym) { + ErrorOr NameOrErr = Sym->getName(StringTable); + error(NameOrErr.getError()); + StringRef Name = *NameOrErr; + if (Sym->isUndefined()) + return new (Alloc) Undefined(Name); + return new (Alloc) DefinedRegular(Name); +} + +namespace lld { +namespace elf2 { +template class elf2::ObjectFile; +template class elf2::ObjectFile; +template class elf2::ObjectFile; +template class elf2::ObjectFile; +} +} Index: lld/trunk/ELF/Options.td =================================================================== --- lld/trunk/ELF/Options.td +++ lld/trunk/ELF/Options.td @@ -0,0 +1,8 @@ +include "llvm/Option/OptParser.td" + +//===----------------------------------------------------------------------===// +/// Utility Functions +//===----------------------------------------------------------------------===// + +def output : Separate<["-"], "o">, MetaVarName<"">, + HelpText<"Path to file to write output">; Index: lld/trunk/ELF/README.md =================================================================== --- lld/trunk/ELF/README.md +++ lld/trunk/ELF/README.md @@ -0,0 +1,12 @@ +The New ELF Linker +================== +This directory contains a port of the new PE/COFF linker for ELF. + +Overall Design +-------------- +See COFF/README.md for details on the design. + +Capabilities +------------ +This linker can currently generate a valid ELF file that can be run on linux +from a single input file. Index: lld/trunk/ELF/SymbolTable.h =================================================================== --- lld/trunk/ELF/SymbolTable.h +++ lld/trunk/ELF/SymbolTable.h @@ -0,0 +1,58 @@ +//===- SymbolTable.h ------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_SYMBOL_TABLE_H +#define LLD_ELF_SYMBOL_TABLE_H + +#include "InputFiles.h" +#include + +namespace lld { +namespace elf2 { +class Defined; +struct Symbol; + +// SymbolTable is a bucket of all known symbols, including defined, +// undefined, or lazy symbols (the last one is symbols in archive +// files whose archive members are not yet loaded). +// +// We put all symbols of all files to a SymbolTable, and the +// SymbolTable selects the "best" symbols if there are name +// conflicts. For example, obviously, a defined symbol is better than +// an undefined symbol. Or, if there's a conflict between a lazy and a +// undefined, it'll read an archive member to read a real definition +// to replace the lazy symbol. The logic is implemented in resolve(). +template class SymbolTable { +public: + SymbolTable(); + + void addFile(std::unique_ptr File); + + // Print an error message on undefined symbols. + void reportRemainingUndefines(); + + // Returns a list of chunks of selected symbols. + std::vector getChunks(); + + // The writer needs to infer the machine type from the object files. + std::vector>> ObjectFiles; + +private: + void addObject(ObjectFile *File); + + void resolve(SymbolBody *Body); + + std::unordered_map Symtab; + llvm::BumpPtrAllocator Alloc; +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/SymbolTable.cpp =================================================================== --- lld/trunk/ELF/SymbolTable.cpp +++ lld/trunk/ELF/SymbolTable.cpp @@ -0,0 +1,87 @@ +//===- SymbolTable.cpp ----------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "SymbolTable.h" +#include "Driver.h" +#include "Symbols.h" + +using namespace llvm; + +using namespace lld; +using namespace lld::elf2; + +template SymbolTable::SymbolTable() { + resolve(new (Alloc) Undefined("_start")); +} + +template +void SymbolTable::addFile(std::unique_ptr File) { + File->parse(); + InputFile *FileP = File.release(); + auto *P = cast>(FileP); + addObject(P); + return; +} + +template +void SymbolTable::addObject(ObjectFile *File) { + ObjectFiles.emplace_back(File); + for (SymbolBody *Body : File->getSymbols()) + if (Body->isExternal()) + resolve(Body); +} + +template void SymbolTable::reportRemainingUndefines() { + for (auto &I : Symtab) { + Symbol *Sym = I.second; + if (auto *Undef = dyn_cast(Sym->Body)) + error(Twine("undefined symbol: ") + Undef->getName()); + } +} + +// This function resolves conflicts if there's an existing symbol with +// the same name. Decisions are made based on symbol type. +template void SymbolTable::resolve(SymbolBody *New) { + // Find an existing Symbol or create and insert a new one. + StringRef Name = New->getName(); + Symbol *&Sym = Symtab[Name]; + if (!Sym) { + Sym = new (Alloc) Symbol(New); + New->setBackref(Sym); + return; + } + New->setBackref(Sym); + + // compare() returns -1, 0, or 1 if the lhs symbol is less preferable, + // equivalent (conflicting), or more preferable, respectively. + SymbolBody *Existing = Sym->Body; + int comp = Existing->compare(New); + if (comp < 0) + Sym->Body = New; + if (comp == 0) + error(Twine("duplicate symbol: ") + Name); +} + +template std::vector SymbolTable::getChunks() { + std::vector Res; + for (std::unique_ptr> &File : ObjectFiles) { + ArrayRef V = File->getChunks(); + Res.insert(Res.end(), V.begin(), V.end()); + } + return Res; +} + +namespace lld { +namespace elf2 { +template class SymbolTable; +template class SymbolTable; +template class SymbolTable; +template class SymbolTable; +} +} Index: lld/trunk/ELF/Symbols.h =================================================================== --- lld/trunk/ELF/Symbols.h +++ lld/trunk/ELF/Symbols.h @@ -0,0 +1,123 @@ +//===- Symbols.h ----------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_SYMBOLS_H +#define LLD_ELF_SYMBOLS_H + +#include "lld/Core/LLVM.h" +#include "llvm/Object/ELF.h" + +namespace lld { +namespace elf2 { + +using llvm::object::ELFFile; + +class Chunk; +class InputFile; +class SymbolBody; + +// A real symbol object, SymbolBody, is usually accessed indirectly +// through a Symbol. There's always one Symbol for each symbol name. +// The resolver updates SymbolBody pointers as it resolves symbols. +struct Symbol { + explicit Symbol(SymbolBody *P) : Body(P) {} + SymbolBody *Body; +}; + +// The base class for real symbol classes. +class SymbolBody { +public: + enum Kind { + DefinedFirst, + DefinedRegularKind, + DefinedLast, + UndefinedKind, + }; + + Kind kind() const { return SymbolKind; } + virtual ~SymbolBody() {} + + // Returns true if this is an external symbol. + virtual bool isExternal() { return true; } + + // Returns the symbol name. + virtual StringRef getName() = 0; + + // A SymbolBody has a backreference to a Symbol. Originally they are + // doubly-linked. A backreference will never change. But the pointer + // in the Symbol may be mutated by the resolver. If you have a + // pointer P to a SymbolBody and are not sure whether the resolver + // has chosen the object among other objects having the same name, + // you can access P->Backref->Body to get the resolver's result. + void setBackref(Symbol *P) { Backref = P; } + SymbolBody *getReplacement() { return Backref ? Backref->Body : this; } + + // Decides which symbol should "win" in the symbol table, this or + // the Other. Returns 1 if this wins, -1 if the Other wins, or 0 if + // they are duplicate (conflicting) symbols. + virtual int compare(SymbolBody *Other) = 0; + +protected: + SymbolBody(Kind K) : SymbolKind(K) {} + +private: + const Kind SymbolKind; + Symbol *Backref = nullptr; +}; + +// The base class for any defined symbols, including absolute symbols, +// etc. +class Defined : public SymbolBody { +public: + Defined(Kind K) : SymbolBody(K) {} + + static bool classof(const SymbolBody *S) { + Kind K = S->kind(); + return DefinedFirst <= K && K <= DefinedLast; + } + + int compare(SymbolBody *Other) override; +}; + +// Regular defined symbols read from object file symbol tables. +template class DefinedRegular : public Defined { +public: + DefinedRegular(StringRef Name); + + static bool classof(const SymbolBody *S) { + return S->kind() == DefinedRegularKind; + } + + StringRef getName() override; + int compare(SymbolBody *Other) override; + +private: + StringRef Name; +}; + +// Undefined symbols. +class Undefined : public SymbolBody { +public: + explicit Undefined(StringRef N) : SymbolBody(UndefinedKind), Name(N) {} + + static bool classof(const SymbolBody *S) { + return S->kind() == UndefinedKind; + } + StringRef getName() override { return Name; } + + int compare(SymbolBody *Other) override; + +private: + StringRef Name; +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/Symbols.cpp =================================================================== --- lld/trunk/ELF/Symbols.cpp +++ lld/trunk/ELF/Symbols.cpp @@ -0,0 +1,57 @@ +//===- Symbols.cpp --------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "Symbols.h" +#include "Chunks.h" + +using namespace llvm::object; + +using namespace lld; +using namespace lld::elf2; + +template +DefinedRegular::DefinedRegular(StringRef Name) + : Defined(DefinedRegularKind), Name(Name) {} + +// Returns 1, 0 or -1 if this symbol should take precedence +// over the Other, tie or lose, respectively. +template int DefinedRegular::compare(SymbolBody *Other) { + if (Other->kind() < kind()) + return -Other->compare(this); + auto *R = dyn_cast(Other); + if (!R) + return 1; + + return 0; +} + +int Defined::compare(SymbolBody *Other) { + if (Other->kind() < kind()) + return -Other->compare(this); + if (isa(Other)) + return 0; + return 1; +} + +int Undefined::compare(SymbolBody *Other) { + if (Other->kind() < kind()) + return -Other->compare(this); + return 1; +} + +template StringRef DefinedRegular::getName() { return Name; } + +namespace lld { +namespace elf2 { +template class DefinedRegular; +template class DefinedRegular; +template class DefinedRegular; +template class DefinedRegular; +} +} Index: lld/trunk/ELF/Writer.h =================================================================== --- lld/trunk/ELF/Writer.h +++ lld/trunk/ELF/Writer.h @@ -0,0 +1,74 @@ +//===- Writer.h -----------------------------------------------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_WRITER_H +#define LLD_ELF_WRITER_H + +#include "SymbolTable.h" +#include "llvm/Support/FileOutputBuffer.h" + +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 +// creates multiple OutputSections and assign them unique, +// non-overlapping file offsets and VAs. +class OutputSection { +public: + OutputSection(StringRef Name) : Name(Name), Header({}) {} + void setVA(uint64_t); + void setFileOffset(uint64_t); + void addChunk(Chunk *C); + std::vector &getChunks() { return Chunks; } + + // Returns the size of the section in the output file. + uint64_t getSize() { return Header.sh_size; } + + // Set offset into the string table storing this section name. + // Used only when the name is longer than 8 bytes. + void setStringTableOff(uint32_t V) { StringTableOff = V; } + +private: + StringRef Name; + llvm::ELF::Elf64_Shdr Header; + uint32_t StringTableOff = 0; + std::vector Chunks; +}; + +// The writer writes a SymbolTable result to a file. +template class Writer { +public: + explicit Writer(SymbolTable *T); + ~Writer(); + void write(StringRef Path); + +private: + void createSections(); + void assignAddresses(); + void openFile(StringRef OutputPath); + void writeHeader(); + void writeSections(); + + SymbolTable *Symtab; + std::unique_ptr Buffer; + llvm::SpecificBumpPtrAllocator CAlloc; + std::vector OutputSections; + + uint64_t FileSize; + uint64_t SizeOfImage; + uint64_t SizeOfHeaders; + + std::vector> Chunks; +}; + +} // namespace elf2 +} // namespace lld + +#endif Index: lld/trunk/ELF/Writer.cpp =================================================================== --- lld/trunk/ELF/Writer.cpp +++ lld/trunk/ELF/Writer.cpp @@ -0,0 +1,161 @@ +//===- 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 "Driver.h" + +using namespace llvm; +using namespace llvm::ELF; +using namespace llvm::object; + +using namespace lld; +using namespace lld::elf2; + +static const int PageSize = 4096; + +template Writer::Writer(SymbolTable *T) : Symtab(T) {} +template Writer::~Writer() {} + +// The main function of the writer. +template void Writer::write(StringRef OutputPath) { + createSections(); + assignAddresses(); + openFile(OutputPath); + writeHeader(); + writeSections(); + error(Buffer->commit()); +} + +void OutputSection::setVA(uint64_t VA) { + Header.sh_addr = VA; + for (Chunk *C : Chunks) + C->setVA(C->getVA() + VA); +} + +void OutputSection::setFileOffset(uint64_t Off) { + if (Header.sh_size == 0) + return; + Header.sh_offset = Off; + for (Chunk *C : Chunks) + C->setFileOff(C->getFileOff() + Off); +} + +void OutputSection::addChunk(Chunk *C) { + Chunks.push_back(C); + C->setOutputSection(this); + uint64_t Off = Header.sh_size; + Off = RoundUpToAlignment(Off, C->getAlign()); + C->setVA(Off); + C->setFileOff(Off); + Off += C->getSize(); + Header.sh_size = Off; +} + +static int compare(const Chunk *A, const Chunk *B) { + return A->getSectionName() < B->getSectionName(); +} + +// Create output section objects and add them to OutputSections. +template void Writer::createSections() { + std::vector Chunks = Symtab->getChunks(); + if (Chunks.empty()) + return; + std::sort(Chunks.begin(), Chunks.end(), compare); + + Chunk *Prev = nullptr; + OutputSection *Sec = nullptr; + for (Chunk *C : Chunks) { + if (Prev == nullptr || Prev->getSectionName() != C->getSectionName()) { + Sec = new (CAlloc.Allocate()) OutputSection(C->getSectionName()); + OutputSections.push_back(Sec); + Prev = C; + } + Sec->addChunk(C); + } +} + +// Visits all sections to assign incremental, non-overlapping RVAs and +// file offsets. +template void Writer::assignAddresses() { + SizeOfHeaders = RoundUpToAlignment(sizeof(Elf_Ehdr_Impl) + + sizeof(Elf_Shdr_Impl) * + OutputSections.size(), + PageSize); + uint64_t VA = 0x1000; // The first page is kept unmapped. + uint64_t FileOff = SizeOfHeaders; + for (OutputSection *Sec : OutputSections) { + Sec->setVA(VA); + Sec->setFileOffset(FileOff); + VA += RoundUpToAlignment(Sec->getSize(), PageSize); + FileOff += RoundUpToAlignment(Sec->getSize(), 8); + } + SizeOfImage = SizeOfHeaders + RoundUpToAlignment(VA - 0x1000, PageSize); + 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] = ELFCLASS64; + EHdr->e_ident[EI_DATA] = ELFDATA2LSB; + EHdr->e_ident[EI_VERSION] = EV_CURRENT; + EHdr->e_ident[EI_OSABI] = ELFOSABI_GNU; + + EHdr->e_type = ET_EXEC; + EHdr->e_machine = EM_X86_64; + EHdr->e_version = EV_CURRENT; + EHdr->e_entry = 0x401000; + EHdr->e_phoff = sizeof(Elf_Ehdr_Impl); + EHdr->e_shoff = 0; + EHdr->e_ehsize = sizeof(Elf_Ehdr_Impl); + EHdr->e_phentsize = sizeof(Elf_Phdr_Impl); + EHdr->e_phnum = 1; + EHdr->e_shentsize = sizeof(Elf_Shdr_Impl); + EHdr->e_shnum = 0; + EHdr->e_shstrndx = 0; + + 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; +} + +template void Writer::openFile(StringRef Path) { + std::error_code EC = FileOutputBuffer::create(Path, FileSize, Buffer, + FileOutputBuffer::F_executable); + error(EC, Twine("failed to open ") + Path); +} + +// Write section contents to a mmap'ed file. +template void Writer::writeSections() { + uint8_t *Buf = Buffer->getBufferStart(); + for (OutputSection *Sec : OutputSections) { + for (Chunk *C : Sec->getChunks()) + C->writeTo(Buf); + } +} + +namespace lld { +namespace elf2 { +template class Writer; +template class Writer; +template class Writer; +template class Writer; +} +} Index: lld/trunk/include/lld/Driver/Driver.h =================================================================== --- lld/trunk/include/lld/Driver/Driver.h +++ lld/trunk/include/lld/Driver/Driver.h @@ -146,6 +146,10 @@ bool link(llvm::ArrayRef args); } +namespace elf2 { +void link(llvm::ArrayRef args); +} + /// Driver for lld unit tests class CoreDriver : public Driver { public: Index: lld/trunk/lib/Driver/CMakeLists.txt =================================================================== --- lld/trunk/lib/Driver/CMakeLists.txt +++ lld/trunk/lib/Driver/CMakeLists.txt @@ -24,6 +24,7 @@ lldCOFF lldPECOFF lldELF + lldELF2 lldAArch64ELFTarget lldARMELFTarget lldHexagonELFTarget Index: lld/trunk/lib/Driver/UniversalDriver.cpp =================================================================== --- lld/trunk/lib/Driver/UniversalDriver.cpp +++ lld/trunk/lib/Driver/UniversalDriver.cpp @@ -69,6 +69,7 @@ enum class Flavor { invalid, gnu_ld, // -flavor gnu + gnu_ld2, // -flavor gnu2 win_link, // -flavor link win_link2, // -flavor link2 darwin_ld, // -flavor darwin @@ -85,6 +86,7 @@ static Flavor strToFlavor(StringRef str) { return llvm::StringSwitch(str) .Case("gnu", Flavor::gnu_ld) + .Case("gnu2", Flavor::gnu_ld2) .Case("link", Flavor::win_link) .Case("lld-link", Flavor::win_link) .Case("link2", Flavor::win_link2) @@ -202,6 +204,9 @@ switch (flavor) { case Flavor::gnu_ld: return GnuLdDriver::linkELF(args, diagnostics); + case Flavor::gnu_ld2: + elf2::link(args); + return true; case Flavor::darwin_ld: return DarwinLdDriver::linkMachO(args, diagnostics); case Flavor::win_link: Index: lld/trunk/test/elf2/basic.test =================================================================== --- lld/trunk/test/elf2/basic.test +++ lld/trunk/test/elf2/basic.test @@ -0,0 +1,78 @@ +# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t +# RUN: lld -flavor gnu2 %t -o %t2 +# RUN: llvm-readobj -file-headers -program-headers %t2 | FileCheck %s +# REQUIRES: x86 + +# exits with return code 42 on linux +.globl _start; +_start: + mov $60, %rax + mov $42, %rdi + syscall + +# CHECK: ElfHeader { +# CHECK-NEXT: Ident { +# CHECK-NEXT: Magic: (7F 45 4C 46) +# CHECK-NEXT: Class: 64-bit (0x2) +# CHECK-NEXT: DataEncoding: LittleEndian (0x1) +# CHECK-NEXT: FileVersion: 1 +# CHECK-NEXT: OS/ABI: GNU/Linux (0x3) +# CHECK-NEXT: ABIVersion: 0 +# CHECK-NEXT: Unused: (00 00 00 00 00 00 00) +# CHECK-NEXT: } +# CHECK-NEXT: Type: Executable (0x2) +# CHECK-NEXT: Machine: EM_X86_64 (0x3E) +# CHECK-NEXT: Version: 1 +# CHECK-NEXT: Entry: 0x401000 +# CHECK-NEXT: ProgramHeaderOffset: 0x40 +# CHECK-NEXT: SectionHeaderOffset: 0x0 +# CHECK-NEXT: Flags [ (0x0) +# CHECK-NEXT: ] +# CHECK-NEXT: HeaderSize: 64 +# CHECK-NEXT: ProgramHeaderEntrySize: 56 +# CHECK-NEXT: ProgramHeaderCount: 1 +# CHECK-NEXT: SectionHeaderEntrySize: 64 +# CHECK-NEXT: SectionHeaderCount: 0 +# CHECK-NEXT: StringTableSectionIndex: 0 +# CHECK-NEXT: } +# CHECK-NEXT: ProgramHeaders [ +# CHECK-NEXT: ProgramHeader { +# CHECK-NEXT: Type: PT_LOAD (0x1) +# CHECK-NEXT: Offset: 0x0 +# CHECK-NEXT: VirtualAddress: 0x400000 +# CHECK-NEXT: PhysicalAddress: 0x400000 +# CHECK-NEXT: FileSize: 4112 +# CHECK-NEXT: MemSize: 4112 +# CHECK-NEXT: Flags [ (0x5) +# CHECK-NEXT: PF_R (0x4) +# CHECK-NEXT: PF_X (0x1) +# CHECK-NEXT: ] +# CHECK-NEXT: Alignment: 16384 +# CHECK-NEXT: } +# CHECK-NEXT: ] + +# RUN: not lld -flavor gnu2 %t 2>&1 | FileCheck --check-prefix=NO_O %s +# NO_O: -o must be specified. + +# RUN: not lld -flavor gnu2 %t.foo -o %t2 2>&1 | \ +# RUN: FileCheck --check-prefix=MISSING %s +# MISSING: cannot open {{.*}}.foo: {{[Nn]}}o such file or directory + +# RUN: not lld -flavor gnu2 -o %t2 2>&1 | \ +# RUN: FileCheck --check-prefix=NO_INPUT %s +# NO_INPUT: no input files. + +# RUN: mkdir -p %t.dir +# RUN: not lld -flavor gnu2 %t.dir -o %t2 2>&1 | \ +# RUN: FileCheck --check-prefix=CANNOT_OPEN %s +# CANNOT_OPEN: cannot open {{.*}}.dir: {{[Ii]}}s a directory + +# RUN: not lld -flavor gnu2 %t -o 2>&1 | FileCheck --check-prefix=NO_O_VAL %s +# NO_O_VAL: missing arg value for "-o", expected 1 argument. + +# RUN: not lld -flavor gnu2 --foo 2>&1 | FileCheck --check-prefix=UNKNOWN %s +# UNKNOWN: unknown argument: --foo + +# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t +# RUN: not lld -flavor gnu2 %t %t -o %t2 2>&1 | FileCheck --check-prefix=DUP %s +# DUP: duplicate symbol: _start Index: lld/trunk/test/elf2/undef.test =================================================================== --- lld/trunk/test/elf2/undef.test +++ lld/trunk/test/elf2/undef.test @@ -0,0 +1,8 @@ +# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t +# RUN: not lld -flavor gnu2 %t -o %t2 2>&1 | FileCheck %s +# CHECK: undefined symbol: foo +# REQUIRES: x86 + + .globl _start; +_start: + call foo