Index: ELF/Chunks.h
===================================================================
--- ELF/Chunks.h
+++ ELF/Chunks.h
@@ -17,6 +17,7 @@
 namespace elf2 {
 
 template <class ELFT> class ObjectFile;
+template <class ELFT> class OutputSection;
 
 // A chunk corresponding a section of an input file.
 template <class ELFT> class SectionChunk {
@@ -25,7 +26,7 @@
   typedef llvm::object::Elf_Rel_Impl<ELFT, false> Elf_Rel;
 
 public:
-  SectionChunk(llvm::object::ELFFile<ELFT> *Obj, const Elf_Shdr *Header);
+  SectionChunk(ObjectFile<ELFT> *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; }
@@ -36,6 +37,9 @@
 
   StringRef getSectionName() const;
   const Elf_Shdr *getSectionHdr() const { return Header; }
+  ObjectFile<ELFT> *getFile() { return File; }
+  void setOutputSection(OutputSection<ELFT> *S) { OS = S; }
+  OutputSection<ELFT> *getOutputSection() { return OS; }
 
   // The writer sets and uses the addresses.
   uint64_t getOutputSectionOff() { return OutputSectionOff; }
@@ -50,8 +54,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<ELFT> *Obj;
+  // The file this chunk was created from.
+  ObjectFile<ELFT> *File;
+
+  // The OutputSection this is assigned to.
+  OutputSection<ELFT> *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 <class ELFT>
-SectionChunk<ELFT>::SectionChunk(object::ELFFile<ELFT> *Obj,
-                                 const Elf_Shdr *Header)
-    : Obj(Obj), Header(Header) {
+SectionChunk<ELFT>::SectionChunk(ObjectFile<ELFT> *F, const Elf_Shdr *Header)
+    : File(F), OS(nullptr), Header(Header) {
   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<uint8_t> Data = *Obj->getSectionContents(Header);
+  ArrayRef<uint8_t> Data = *File->getObj()->getSectionContents(Header);
   memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
 
   // FIXME: Relocations
 }
 
 template <class ELFT> StringRef SectionChunk<ELFT>::getSectionName() const {
-  ErrorOr<StringRef> Name = Obj->getSectionName(Header);
+  ErrorOr<StringRef> 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<ELFT>::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,21 @@
 
   explicit ObjectFile(MemoryBufferRef M) : ObjectFileBase(getKind(), M) {}
   void parse() override;
+  const std::vector<RelocMapInfo> &getRelocations() const { return RelocMap; }
+
+  SymbolBody *getSymbolBody(uint32_t SymbolIndex) {
+    if (SymbolIndex >= IndexedSymbolBodies.size())
+      error("Invalid symbol table index.");
+    return IndexedSymbolBodies[SymbolIndex]->getReplacement();
+  }
 
   // Returns the underying ELF file.
   llvm::object::ELFFile<ELFT> *getObj() const { return ELFObj.get(); }
 
   ArrayRef<SectionChunk<ELFT> *> getChunks() { return Chunks; }
 
+  const Elf_Shdr *getSymtab() const { return Symtab; }
+
 private:
   void initializeChunks();
   void initializeSymbols();
@@ -102,6 +127,16 @@
   std::vector<SectionChunk<ELFT> *> Chunks;
 
   const Elf_Shdr *Symtab = nullptr;
+  // Section index to SectionChunk map. Unmapped sections are nullptr.
+  std::vector<SectionChunk<ELFT> *> SparseChunks;
+
+  // Symbol bodies indexed the same as the symbol table.
+  std::vector<SymbolBody *> IndexedSymbolBodies;
+
+  // This vector contains a sorted list of <section, relocation section that
+  // applies to section> pairs. This is used to quickly find and iterate over
+  // the relocations for a given section.
+  std::vector<RelocMapInfo> RelocMap;
 };
 
 } // namespace elf2
Index: ELF/InputFiles.cpp
===================================================================
--- ELF/InputFiles.cpp
+++ ELF/InputFiles.cpp
@@ -40,22 +40,33 @@
 template <class ELFT> void elf2::ObjectFile<ELFT>::initializeChunks() {
   uint64_t Size = ELFObj->getNumSections();
   Chunks.reserve(Size);
+  SparseChunks.reserve(Size);
   for (const Elf_Shdr &Sec : ELFObj->sections()) {
+    SectionChunk<ELFT> *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<ELFT>(this->getObj(), &Sec);
-      Chunks.push_back(C);
+      SC = new (Alloc) SectionChunk<ELFT>(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 <class ELFT> void elf2::ObjectFile<ELFT>::initializeSymbols() {
@@ -69,10 +80,19 @@
   uint32_t FirstNonLocal = Symtab->sh_info;
   if (FirstNonLocal > NumSymbols)
     error("Invalid sh_info in symbol table");
+  Elf_Sym_Range LocalSyms =
+      llvm::make_range(Syms.begin() + 1, Syms.begin() + FirstNonLocal);
   Syms = llvm::make_range(Syms.begin() + FirstNonLocal, Syms.end());
   SymbolBodies.reserve(NumSymbols);
-  for (const Elf_Sym &Sym : Syms)
-    SymbolBodies.push_back(createSymbolBody(StringTable, &Sym));
+  IndexedSymbolBodies.reserve(NumSymbols);
+  IndexedSymbolBodies.push_back(nullptr); // Skip the null entry.
+  for (const Elf_Sym &Sym : LocalSyms)
+    IndexedSymbolBodies.push_back(createSymbolBody(StringTable, &Sym));
+  for (const Elf_Sym &Sym : Syms) {
+    SymbolBody *S = createSymbolBody(StringTable, &Sym);
+    SymbolBodies.push_back(S);
+    IndexedSymbolBodies.push_back(S);
+  }
 }
 
 template <class ELFT>
@@ -84,10 +104,14 @@
   switch (Sym->getBinding()) {
   default:
     error("unexpected binding");
+  case STB_LOCAL:
+    return new (Alloc)
+      DefinedRegular<ELFT>(Name, *Sym, SparseChunks[Sym->st_shndx]);
   case STB_GLOBAL:
     if (Sym->isUndefined())
       return new (Alloc) Undefined<ELFT>(Name, *Sym);
-    return new (Alloc) DefinedRegular<ELFT>(Name, *Sym);
+    return new (Alloc)
+        DefinedRegular<ELFT>(Name, *Sym, SparseChunks[Sym->st_shndx]);
   case STB_WEAK:
     if (Sym->isUndefined())
       return new (Alloc) UndefinedWeak<ELFT>(Name, *Sym);
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"
 
@@ -60,6 +62,7 @@
   // 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
@@ -121,12 +124,21 @@
   typedef typename Base::Elf_Sym Elf_Sym;
 
 public:
-  explicit DefinedRegular(StringRef N, const Elf_Sym &Sym)
-      : Defined<ELFT>(Base::DefinedRegularKind, N, Sym) {}
+  DefinedRegular(StringRef N, const Elf_Sym &Sym, SectionChunk<ELFT> *C)
+      : Defined<ELFT>(Base::DefinedRegularKind, N, Sym), Chunk(C) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == Base::DefinedRegularKind;
   }
+
+  typename llvm::object::ELFFile<ELFT>::uintX_t getValue() const {
+    return Sym.st_value;
+  }
+
+  SectionChunk<ELFT> *getChunk() const { return Chunk; }
+
+private:
+  SectionChunk<ELFT> *Chunk;
 };
 
 template <class ELFT> class DefinedWeak : public Defined<ELFT> {
Index: ELF/Symbols.cpp
===================================================================
--- ELF/Symbols.cpp
+++ ELF/Symbols.cpp
@@ -43,3 +43,12 @@
   }
   llvm_unreachable("unknown symbol kind");
 }
+
+namespace lld {
+namespace elf2 {
+template class DefinedRegular<llvm::object::ELF32LE>;
+template class DefinedRegular<llvm::object::ELF32BE>;
+template class DefinedRegular<llvm::object::ELF64LE>;
+template class DefinedRegular<llvm::object::ELF64BE>;
+}
+}
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"
 #include "Symbols.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 <endianness E>
   void writeHeaderTo(typename ELFFile<ELFType<E, Is64Bits>>::Elf_Shdr *SHdr);
@@ -79,7 +82,10 @@
 private:
   std::vector<SectionChunk<ELFT> *> Chunks;
 };
+} // end namespace elf2
+} // end namespace lld
 
+namespace {
 template <bool Is64Bits>
 class StringTableSection final : public OutputSectionBase<Is64Bits> {
   llvm::StringTableBuilder &StrTabBuilder;
@@ -199,9 +205,55 @@
   this->Header.sh_size = Off;
 }
 
+template <class ELFT>
+typename llvm::object::ELFFile<ELFT>::uintX_t
+getSymVA(DefinedRegular<ELFT> *DR) {
+  SectionChunk<ELFT> *SC = DR->getChunk();
+  OutputSection<ELFT> *OS = SC->getOutputSection();
+  return OS->getVA() + SC->getOutputSectionOff() + DR->getValue();
+}
+
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
-  for (SectionChunk<ELFT> *C : Chunks)
+  for (SectionChunk<ELFT> *C : Chunks) {
     C->writeTo(Buf);
+    const std::vector<typename ObjectFile<ELFT>::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<ELFT>::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();
+        // Skip undefined weak for now.
+        if (isa<UndefinedWeak<ELFT>>(Body))
+          continue;
+        if (!isa<DefinedRegular<ELFT>>(Body))
+          error(Twine("Can't relocate symbol ") + Body->getName());
+        uintX_t Offset = RI.r_offset;
+        uint32_t Type = RI.getType(EObj->isMips64EL());
+        uintX_t P = this->getVA() + C->getOutputSectionOff();
+        uintX_t SymVA = getSymVA<ELFT>(cast<DefinedRegular<ELFT>>(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 <bool Is64Bits>
@@ -302,6 +354,7 @@
         OutputSections.push_back(Sec);
       }
       Sec->addChunk(C);
+      C->setOutputSection(Sec);
     }
   }
 }
Index: test/elf2/relocation.s
===================================================================
--- /dev/null
+++ test/elf2/relocation.s
@@ -0,0 +1,15 @@
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+// RUN: lld -flavor gnu2 %t -o %t2
+// RUN: llvm-objdump -d %t2 | FileCheck %s
+// REQUIRES: x86
+
+
+.section       .text,"ax",@progbits,unique,1
+.global _start
+_start:
+  call lulz
+
+.section       .text,"ax",@progbits,unique,2
+lulz:
+
+// CHECK: e8 00 00 00 00  callq   0