diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 704d69a..cb9a7e6 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -251,6 +251,7 @@
   compiler/elf_writer_test.cc \
   compiler/image_test.cc \
   compiler/jni/jni_compiler_test.cc \
+  compiler/linker/multi_oat_relative_patcher_test.cc \
   compiler/linker/output_stream_test.cc \
   compiler/oat_test.cc \
   compiler/optimizing/bounds_check_elimination_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 159e9cf..33b89bb 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -61,6 +61,7 @@
 	driver/dex_compilation_unit.cc \
 	linker/buffered_output_stream.cc \
 	linker/file_output_stream.cc \
+	linker/multi_oat_relative_patcher.cc \
 	linker/output_stream.cc \
 	linker/vector_output_stream.cc \
 	linker/relative_patcher.cc \
diff --git a/compiler/common_compiler_test.cc b/compiler/common_compiler_test.cc
index e4bfac9..239bc59 100644
--- a/compiler/common_compiler_test.cc
+++ b/compiler/common_compiler_test.cc
@@ -194,16 +194,15 @@
                                             kind,
                                             isa,
                                             instruction_set_features_.get(),
-                                            true,
+                                            /* boot_image */ true,
                                             GetImageClasses(),
                                             GetCompiledClasses(),
                                             GetCompiledMethods(),
-                                            2,
-                                            true,
-                                            true,
+                                            /* thread_count */ 2,
+                                            /* dump_stats */ true,
+                                            /* dump_passes */ true,
                                             timer_.get(),
-                                            -1,
-                                            /* dex_to_oat_map */ nullptr,
+                                            /* swap_fd */ -1,
                                             GetProfileCompilationInfo()));
   // We typically don't generate an image in unit tests, disable this optimization by default.
   compiler_driver_->SetSupportBootImageFixup(false);
diff --git a/compiler/dex/quick/quick_cfi_test.cc b/compiler/dex/quick/quick_cfi_test.cc
index 0cd41bb..6c6c9cf 100644
--- a/compiler/dex/quick/quick_cfi_test.cc
+++ b/compiler/dex/quick/quick_cfi_test.cc
@@ -84,17 +84,16 @@
                           Compiler::kQuick,
                           isa,
                           isa_features.get(),
-                          false,
-                          nullptr,
-                          nullptr,
-                          nullptr,
-                          0,
-                          false,
-                          false,
-                          0,
-                          -1,
-                          nullptr,
-                          nullptr);
+                          /* boot_image */ false,
+                          /* image_classes */ nullptr,
+                          /* compiled_classes */ nullptr,
+                          /* compiled_methods */ nullptr,
+                          /* thread_count */ 0,
+                          /* dump_stats */ false,
+                          /* dump_passes */ false,
+                          /* timer */ nullptr,
+                          /* swap_fd */ -1,
+                          /* profile_compilation_info */ nullptr);
     ClassLinker* linker = nullptr;
     CompilationUnit cu(&pool, isa, &driver, linker);
     DexFile::CodeItem code_item { 0, 0, 0, 0, 0, 0, { 0 } };  // NOLINT
diff --git a/compiler/dex/quick/x86/quick_assemble_x86_test.cc b/compiler/dex/quick/x86/quick_assemble_x86_test.cc
index efdc333..ff0ecea 100644
--- a/compiler/dex/quick/x86/quick_assemble_x86_test.cc
+++ b/compiler/dex/quick/x86/quick_assemble_x86_test.cc
@@ -64,18 +64,17 @@
         method_inliner_map_.get(),
         Compiler::kQuick,
         isa_,
-        nullptr,
-        false,
-        nullptr,
-        nullptr,
-        nullptr,
-        0,
-        false,
-        false,
-        0,
-        -1,
-        nullptr,
-        nullptr));
+        /* instruction_set_features*/ nullptr,
+        /* boot_image */ false,
+        /* image_classes */ nullptr,
+        /* compiled_classes */ nullptr,
+        /* compiled_methods */ nullptr,
+        /* thread_count */ 0,
+        /* dump_stats */ false,
+        /* dump_passes */ false,
+        /* timer */ nullptr,
+        /* swap_fd */ -1,
+        /* profile_compilation_info */ nullptr));
     cu_.reset(new CompilationUnit(pool_.get(), isa_, compiler_driver_.get(), nullptr));
     DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>(
         cu_->arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
diff --git a/compiler/driver/compiled_method_storage_test.cc b/compiler/driver/compiled_method_storage_test.cc
index 2e2d1f9..0695cb5 100644
--- a/compiler/driver/compiled_method_storage_test.cc
+++ b/compiler/driver/compiled_method_storage_test.cc
@@ -32,19 +32,19 @@
   CompilerDriver driver(&compiler_options,
                         &verification_results,
                         &method_inliner_map,
-                        Compiler::kOptimizing, kNone,
-                        nullptr,
-                        false,
-                        nullptr,
-                        nullptr,
-                        nullptr,
-                        1u,
-                        false,
-                        false,
-                        nullptr,
-                        -1,
-                        nullptr,
-                        nullptr);
+                        Compiler::kOptimizing,
+                        /* instruction_set_ */ kNone,
+                        /* instruction_set_features */ nullptr,
+                        /* boot_image */ false,
+                        /* image_classes */ nullptr,
+                        /* compiled_classes */ nullptr,
+                        /* compiled_methods */ nullptr,
+                        /* thread_count */ 1u,
+                        /* dump_stats */ false,
+                        /* dump_passes */ false,
+                        /* timer */ nullptr,
+                        /* swap_fd */ -1,
+                        /* profile_compilation_info */ nullptr);
   CompiledMethodStorage* storage = driver.GetCompiledMethodStorage();
 
   ASSERT_TRUE(storage->DedupeEnabled());  // The default.
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 670fe94..e80730f 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -342,12 +342,15 @@
     Compiler::Kind compiler_kind,
     InstructionSet instruction_set,
     const InstructionSetFeatures* instruction_set_features,
-    bool boot_image, std::unordered_set<std::string>* image_classes,
+    bool boot_image,
+    std::unordered_set<std::string>* image_classes,
     std::unordered_set<std::string>* compiled_classes,
     std::unordered_set<std::string>* compiled_methods,
-    size_t thread_count, bool dump_stats, bool dump_passes,
-    CumulativeLogger* timer, int swap_fd,
-    const std::unordered_map<const DexFile*, const char*>* dex_to_oat_map,
+    size_t thread_count,
+    bool dump_stats,
+    bool dump_passes,
+    CumulativeLogger* timer,
+    int swap_fd,
     const ProfileCompilationInfo* profile_compilation_info)
     : compiler_options_(compiler_options),
       verification_results_(verification_results),
@@ -374,7 +377,6 @@
       compiler_context_(nullptr),
       support_boot_image_fixup_(instruction_set != kMips && instruction_set != kMips64),
       dex_files_for_oat_file_(nullptr),
-      dex_file_oat_filename_map_(dex_to_oat_map),
       compiled_method_storage_(swap_fd),
       profile_compilation_info_(profile_compilation_info) {
   DCHECK(compiler_options_ != nullptr);
@@ -1678,12 +1680,6 @@
       use_dex_cache = true;
     }
   }
-  if (!use_dex_cache && IsBootImage()) {
-    if (!AreInSameOatFile(&(const_cast<mirror::Class*>(referrer_class)->GetDexFile()),
-                          &declaring_class->GetDexFile())) {
-      use_dex_cache = true;
-    }
-  }
   // The method is defined not within this dex file. We need a dex cache slot within the current
   // dex file or direct pointers.
   bool must_use_direct_pointers = false;
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index 5e35cbb..ca340ee 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -94,9 +94,11 @@
                  bool boot_image, std::unordered_set<std::string>* image_classes,
                  std::unordered_set<std::string>* compiled_classes,
                  std::unordered_set<std::string>* compiled_methods,
-                 size_t thread_count, bool dump_stats, bool dump_passes,
-                 CumulativeLogger* timer, int swap_fd,
-                 const std::unordered_map<const DexFile*, const char*>* dex_to_oat_map,
+                 size_t thread_count,
+                 bool dump_stats,
+                 bool dump_passes,
+                 CumulativeLogger* timer,
+                 int swap_fd,
                  const ProfileCompilationInfo* profile_compilation_info);
 
   ~CompilerDriver();
@@ -113,20 +115,6 @@
         : ArrayRef<const DexFile* const>();
   }
 
-  // Are the given dex files compiled into the same oat file? Should only be called after
-  // GetDexFilesForOatFile, as the conservative answer (when we don't have a map) is true.
-  bool AreInSameOatFile(const DexFile* d1, const DexFile* d2) {
-    if (dex_file_oat_filename_map_ == nullptr) {
-      // TODO: Check for this wrt/ apps and boot image calls.
-      return true;
-    }
-    auto it1 = dex_file_oat_filename_map_->find(d1);
-    DCHECK(it1 != dex_file_oat_filename_map_->end());
-    auto it2 = dex_file_oat_filename_map_->find(d2);
-    DCHECK(it2 != dex_file_oat_filename_map_->end());
-    return it1->second == it2->second;
-  }
-
   void CompileAll(jobject class_loader,
                   const std::vector<const DexFile*>& dex_files,
                   TimingLogger* timings)
@@ -700,9 +688,6 @@
   // List of dex files that will be stored in the oat file.
   const std::vector<const DexFile*>* dex_files_for_oat_file_;
 
-  // Map from dex files to the oat file (name) they will be compiled into.
-  const std::unordered_map<const DexFile*, const char*>* dex_file_oat_filename_map_;
-
   CompiledMethodStorage compiled_method_storage_;
 
   // Info for profile guided compilation.
diff --git a/compiler/elf_builder.h b/compiler/elf_builder.h
index b673eeb..f7da609 100644
--- a/compiler/elf_builder.h
+++ b/compiler/elf_builder.h
@@ -86,12 +86,24 @@
   // Base class of all sections.
   class Section : public OutputStream {
    public:
-    Section(ElfBuilder<ElfTypes>* owner, const std::string& name,
-            Elf_Word type, Elf_Word flags, const Section* link,
-            Elf_Word info, Elf_Word align, Elf_Word entsize)
-        : OutputStream(name), owner_(owner), header_(),
-          section_index_(0), name_(name), link_(link),
-          started_(false), finished_(false), phdr_flags_(PF_R), phdr_type_(0) {
+    Section(ElfBuilder<ElfTypes>* owner,
+            const std::string& name,
+            Elf_Word type,
+            Elf_Word flags,
+            const Section* link,
+            Elf_Word info,
+            Elf_Word align,
+            Elf_Word entsize)
+        : OutputStream(name),
+          owner_(owner),
+          header_(),
+          section_index_(0),
+          name_(name),
+          link_(link),
+          started_(false),
+          finished_(false),
+          phdr_flags_(PF_R),
+          phdr_type_(0) {
       DCHECK_GE(align, 1u);
       header_.sh_type = type;
       header_.sh_flags = flags;
@@ -228,12 +240,84 @@
     DISALLOW_COPY_AND_ASSIGN(Section);
   };
 
-  // Writer of .dynstr .strtab and .shstrtab sections.
+  class CachedSection : public Section {
+   public:
+    CachedSection(ElfBuilder<ElfTypes>* owner,
+                  const std::string& name,
+                  Elf_Word type,
+                  Elf_Word flags,
+                  const Section* link,
+                  Elf_Word info,
+                  Elf_Word align,
+                  Elf_Word entsize)
+        : Section(owner, name, type, flags, link, info, align, entsize), cache_() { }
+
+    Elf_Word Add(const void* data, size_t length) {
+      Elf_Word offset = cache_.size();
+      const uint8_t* d = reinterpret_cast<const uint8_t*>(data);
+      cache_.insert(cache_.end(), d, d + length);
+      return offset;
+    }
+
+    Elf_Word GetCacheSize() {
+      return cache_.size();
+    }
+
+    void Write() {
+      this->WriteFully(cache_.data(), cache_.size());
+      cache_.clear();
+      cache_.shrink_to_fit();
+    }
+
+    void WriteCachedSection() {
+      this->Start();
+      Write();
+      this->End();
+    }
+
+   private:
+    std::vector<uint8_t> cache_;
+  };
+
+  // Writer of .dynstr section.
+  class CachedStringSection FINAL : public CachedSection {
+   public:
+    CachedStringSection(ElfBuilder<ElfTypes>* owner,
+                        const std::string& name,
+                        Elf_Word flags,
+                        Elf_Word align)
+        : CachedSection(owner,
+                        name,
+                        SHT_STRTAB,
+                        flags,
+                        /* link */ nullptr,
+                        /* info */ 0,
+                        align,
+                        /* entsize */ 0) { }
+
+    Elf_Word Add(const std::string& name) {
+      if (CachedSection::GetCacheSize() == 0u) {
+        DCHECK(name.empty());
+      }
+      return CachedSection::Add(name.c_str(), name.length() + 1);
+    }
+  };
+
+  // Writer of .strtab and .shstrtab sections.
   class StringSection FINAL : public Section {
    public:
-    StringSection(ElfBuilder<ElfTypes>* owner, const std::string& name,
-                  Elf_Word flags, Elf_Word align)
-        : Section(owner, name, SHT_STRTAB, flags, nullptr, 0, align, 0),
+    StringSection(ElfBuilder<ElfTypes>* owner,
+                  const std::string& name,
+                  Elf_Word flags,
+                  Elf_Word align)
+        : Section(owner,
+                  name,
+                  SHT_STRTAB,
+                  flags,
+                  /* link */ nullptr,
+                  /* info */ 0,
+                  align,
+                  /* entsize */ 0),
           current_offset_(0) {
     }
 
@@ -252,42 +336,60 @@
   };
 
   // Writer of .dynsym and .symtab sections.
-  class SymbolSection FINAL : public Section {
+  class SymbolSection FINAL : public CachedSection {
    public:
-    SymbolSection(ElfBuilder<ElfTypes>* owner, const std::string& name,
-                  Elf_Word type, Elf_Word flags, StringSection* strtab)
-        : Section(owner, name, type, flags, strtab, 0,
-                  sizeof(Elf_Off), sizeof(Elf_Sym)) {
+    SymbolSection(ElfBuilder<ElfTypes>* owner,
+                  const std::string& name,
+                  Elf_Word type,
+                  Elf_Word flags,
+                  Section* strtab)
+        : CachedSection(owner,
+                        name,
+                        type,
+                        flags,
+                        strtab,
+                        /* info */ 0,
+                        sizeof(Elf_Off),
+                        sizeof(Elf_Sym)) {
+      // The symbol table always has to start with NULL symbol.
+      Elf_Sym null_symbol = Elf_Sym();
+      CachedSection::Add(&null_symbol, sizeof(null_symbol));
     }
 
     // Buffer symbol for this section.  It will be written later.
     // If the symbol's section is null, it will be considered absolute (SHN_ABS).
     // (we use this in JIT to reference code which is stored outside the debug ELF file)
-    void Add(Elf_Word name, const Section* section,
-             Elf_Addr addr, bool is_relative, Elf_Word size,
-             uint8_t binding, uint8_t type, uint8_t other = 0) {
+    void Add(Elf_Word name,
+             const Section* section,
+             Elf_Addr addr,
+             bool is_relative,
+             Elf_Word size,
+             uint8_t binding,
+             uint8_t type,
+             uint8_t other = 0) {
+      DCHECK(section != nullptr || !is_relative);
+      Elf_Addr abs_addr = addr + (is_relative ? section->GetAddress() : 0);
+      Elf_Word section_index =
+          (section != nullptr) ? section->GetSectionIndex() : static_cast<Elf_Word>(SHN_ABS);
+      Add(name, section_index, abs_addr, size, binding, type, other);
+    }
+
+    void Add(Elf_Word name,
+             Elf_Word section_index,
+             Elf_Addr addr,
+             Elf_Word size,
+             uint8_t binding,
+             uint8_t type,
+             uint8_t other = 0) {
       Elf_Sym sym = Elf_Sym();
       sym.st_name = name;
-      sym.st_value = addr + (is_relative ? section->GetAddress() : 0);
+      sym.st_value = addr;
       sym.st_size = size;
       sym.st_other = other;
-      sym.st_shndx = (section != nullptr ? section->GetSectionIndex()
-                                         : static_cast<Elf_Word>(SHN_ABS));
+      sym.st_shndx = section_index;
       sym.st_info = (binding << 4) + (type & 0xf);
-      symbols_.push_back(sym);
+      CachedSection::Add(&sym, sizeof(sym));
     }
-
-    void Write() {
-      // The symbol table always has to start with NULL symbol.
-      Elf_Sym null_symbol = Elf_Sym();
-      this->WriteFully(&null_symbol, sizeof(null_symbol));
-      this->WriteFully(symbols_.data(), symbols_.size() * sizeof(symbols_[0]));
-      symbols_.clear();
-      symbols_.shrink_to_fit();
-    }
-
-   private:
-    std::vector<Elf_Sym> symbols_;
   };
 
   ElfBuilder(InstructionSet isa, OutputStream* output)
@@ -309,6 +411,8 @@
         debug_line_(this, ".debug_line", SHT_PROGBITS, 0, nullptr, 0, 1, 0),
         shstrtab_(this, ".shstrtab", 0, 1),
         started_(false),
+        write_program_headers_(false),
+        loaded_size_(0u),
         virtual_address_(0) {
     text_.phdr_flags_ = PF_R | PF_X;
     bss_.phdr_flags_ = PF_R | PF_W;
@@ -380,6 +484,14 @@
   void End() {
     DCHECK(started_);
 
+    // Note: loaded_size_ == 0 for tests that don't write .rodata, .text, .bss,
+    // .dynstr, dynsym, .hash and .dynamic. These tests should not read loaded_size_.
+    // TODO: Either refactor the .eh_frame creation so that it counts towards loaded_size_,
+    // or remove all support for .eh_frame. (The currently unused .eh_frame counts towards
+    // the virtual_address_ but we don't consider it for loaded_size_.)
+    CHECK(loaded_size_ == 0 || loaded_size_ == RoundUp(virtual_address_, kPageSize))
+        << loaded_size_ << " " << virtual_address_;
+
     // Write section names and finish the section headers.
     shstrtab_.Start();
     shstrtab_.Write("");
@@ -434,45 +546,58 @@
   // information like the address and size of .rodata and .text.
   // It also contains other metadata like the SONAME.
   // The .dynamic section is found using the PT_DYNAMIC program header.
-  void WriteDynamicSection(const std::string& elf_file_path) {
+  void PrepareDynamicSection(const std::string& elf_file_path,
+                             Elf_Word rodata_size,
+                             Elf_Word text_size,
+                             Elf_Word bss_size) {
     std::string soname(elf_file_path);
     size_t directory_separator_pos = soname.rfind('/');
     if (directory_separator_pos != std::string::npos) {
       soname = soname.substr(directory_separator_pos + 1);
     }
 
-    dynstr_.Start();
-    dynstr_.Write("");  // dynstr should start with empty string.
-    dynsym_.Add(dynstr_.Write("oatdata"), &rodata_, 0, true,
-                rodata_.GetSize(), STB_GLOBAL, STT_OBJECT);
-    if (text_.GetSize() != 0u) {
-      dynsym_.Add(dynstr_.Write("oatexec"), &text_, 0, true,
-                  text_.GetSize(), STB_GLOBAL, STT_OBJECT);
-      dynsym_.Add(dynstr_.Write("oatlastword"), &text_, text_.GetSize() - 4,
-                  true, 4, STB_GLOBAL, STT_OBJECT);
-    } else if (rodata_.GetSize() != 0) {
-      // rodata_ can be size 0 for dwarf_test.
-      dynsym_.Add(dynstr_.Write("oatlastword"), &rodata_, rodata_.GetSize() - 4,
-                  true, 4, STB_GLOBAL, STT_OBJECT);
-    }
-    if (bss_.finished_) {
-      dynsym_.Add(dynstr_.Write("oatbss"), &bss_,
-                  0, true, bss_.GetSize(), STB_GLOBAL, STT_OBJECT);
-      dynsym_.Add(dynstr_.Write("oatbsslastword"), &bss_,
-                  bss_.GetSize() - 4, true, 4, STB_GLOBAL, STT_OBJECT);
-    }
-    Elf_Word soname_offset = dynstr_.Write(soname);
-    dynstr_.End();
+    // Calculate addresses of .text, .bss and .dynstr.
+    DCHECK_EQ(rodata_.header_.sh_addralign, static_cast<Elf_Word>(kPageSize));
+    DCHECK_EQ(text_.header_.sh_addralign, static_cast<Elf_Word>(kPageSize));
+    DCHECK_EQ(bss_.header_.sh_addralign, static_cast<Elf_Word>(kPageSize));
+    DCHECK_EQ(dynstr_.header_.sh_addralign, static_cast<Elf_Word>(kPageSize));
+    Elf_Word rodata_address = rodata_.GetAddress();
+    Elf_Word text_address = RoundUp(rodata_address + rodata_size, kPageSize);
+    Elf_Word bss_address = RoundUp(text_address + text_size, kPageSize);
+    Elf_Word dynstr_address = RoundUp(bss_address + bss_size, kPageSize);
 
-    dynsym_.Start();
-    dynsym_.Write();
-    dynsym_.End();
+    // Cache .dynstr, .dynsym and .hash data.
+    dynstr_.Add("");  // dynstr should start with empty string.
+    Elf_Word rodata_index = rodata_.GetSectionIndex();
+    Elf_Word oatdata = dynstr_.Add("oatdata");
+    dynsym_.Add(oatdata, rodata_index, rodata_address, rodata_size, STB_GLOBAL, STT_OBJECT);
+    if (text_size != 0u) {
+      Elf_Word text_index = rodata_index + 1u;
+      Elf_Word oatexec = dynstr_.Add("oatexec");
+      dynsym_.Add(oatexec, text_index, text_address, text_size, STB_GLOBAL, STT_OBJECT);
+      Elf_Word oatlastword = dynstr_.Add("oatlastword");
+      Elf_Word oatlastword_address = text_address + text_size - 4;
+      dynsym_.Add(oatlastword, text_index, oatlastword_address, 4, STB_GLOBAL, STT_OBJECT);
+    } else if (rodata_size != 0) {
+      // rodata_ can be size 0 for dwarf_test.
+      Elf_Word oatlastword = dynstr_.Add("oatlastword");
+      Elf_Word oatlastword_address = rodata_address + rodata_size - 4;
+      dynsym_.Add(oatlastword, rodata_index, oatlastword_address, 4, STB_GLOBAL, STT_OBJECT);
+    }
+    if (bss_size != 0u) {
+      Elf_Word bss_index = rodata_index + 1u + (text_size != 0 ? 1u : 0u);
+      Elf_Word oatbss = dynstr_.Add("oatbss");
+      dynsym_.Add(oatbss, bss_index, bss_address, bss_size, STB_GLOBAL, STT_OBJECT);
+      Elf_Word oatbsslastword = dynstr_.Add("oatbsslastword");
+      Elf_Word bsslastword_address = bss_address + bss_size - 4;
+      dynsym_.Add(oatbsslastword, bss_index, bsslastword_address, 4, STB_GLOBAL, STT_OBJECT);
+    }
+    Elf_Word soname_offset = dynstr_.Add(soname);
 
     // We do not really need a hash-table since there is so few entries.
     // However, the hash-table is the only way the linker can actually
     // determine the number of symbols in .dynsym so it is required.
-    hash_.Start();
-    int count = dynsym_.GetSize() / sizeof(Elf_Sym);  // Includes NULL.
+    int count = dynsym_.GetCacheSize() / sizeof(Elf_Sym);  // Includes NULL.
     std::vector<Elf_Word> hash;
     hash.push_back(1);  // Number of buckets.
     hash.push_back(count);  // Number of chains.
@@ -484,21 +609,44 @@
       hash.push_back(i + 1);  // Each symbol points to the next one.
     }
     hash.push_back(0);  // Last symbol terminates the chain.
-    hash_.WriteFully(hash.data(), hash.size() * sizeof(hash[0]));
-    hash_.End();
+    hash_.Add(hash.data(), hash.size() * sizeof(hash[0]));
 
-    dynamic_.Start();
+    // Calculate addresses of .dynsym, .hash and .dynamic.
+    DCHECK_EQ(dynstr_.header_.sh_flags, dynsym_.header_.sh_flags);
+    DCHECK_EQ(dynsym_.header_.sh_flags, hash_.header_.sh_flags);
+    Elf_Word dynsym_address =
+        RoundUp(dynstr_address + dynstr_.GetCacheSize(), dynsym_.header_.sh_addralign);
+    Elf_Word hash_address =
+        RoundUp(dynsym_address + dynsym_.GetCacheSize(), hash_.header_.sh_addralign);
+    DCHECK_EQ(dynamic_.header_.sh_addralign, static_cast<Elf_Word>(kPageSize));
+    Elf_Word dynamic_address = RoundUp(hash_address + dynsym_.GetCacheSize(), kPageSize);
+
     Elf_Dyn dyns[] = {
-      { DT_HASH, { hash_.GetAddress() } },
-      { DT_STRTAB, { dynstr_.GetAddress() } },
-      { DT_SYMTAB, { dynsym_.GetAddress() } },
+      { DT_HASH, { hash_address } },
+      { DT_STRTAB, { dynstr_address } },
+      { DT_SYMTAB, { dynsym_address } },
       { DT_SYMENT, { sizeof(Elf_Sym) } },
-      { DT_STRSZ, { dynstr_.GetSize() } },
+      { DT_STRSZ, { dynstr_.GetCacheSize() } },
       { DT_SONAME, { soname_offset } },
       { DT_NULL, { 0 } },
     };
-    dynamic_.WriteFully(&dyns, sizeof(dyns));
-    dynamic_.End();
+    dynamic_.Add(&dyns, sizeof(dyns));
+
+    loaded_size_ = RoundUp(dynamic_address + dynamic_.GetCacheSize(), kPageSize);
+  }
+
+  void WriteDynamicSection() {
+    dynstr_.WriteCachedSection();
+    dynsym_.WriteCachedSection();
+    hash_.WriteCachedSection();
+    dynamic_.WriteCachedSection();
+
+    CHECK_EQ(loaded_size_, RoundUp(dynamic_.GetAddress() + dynamic_.GetSize(), kPageSize));
+  }
+
+  Elf_Word GetLoadedSize() {
+    CHECK_NE(loaded_size_, 0u);
+    return loaded_size_;
   }
 
   // Returns true if all writes and seeks on the output stream succeeded.
@@ -676,10 +824,10 @@
   Section rodata_;
   Section text_;
   Section bss_;
-  StringSection dynstr_;
+  CachedStringSection dynstr_;
   SymbolSection dynsym_;
-  Section hash_;
-  Section dynamic_;
+  CachedSection hash_;
+  CachedSection dynamic_;
   Section eh_frame_;
   Section eh_frame_hdr_;
   StringSection strtab_;
@@ -694,12 +842,14 @@
   std::vector<Section*> sections_;
 
   bool started_;
+  bool write_program_headers_;
+
+  // The size of the memory taken by the ELF file when loaded.
+  size_t loaded_size_;
 
   // Used for allocation of virtual address space.
   Elf_Addr virtual_address_;
 
-  size_t write_program_headers_;
-
   DISALLOW_COPY_AND_ASSIGN(ElfBuilder);
 };
 
diff --git a/compiler/elf_writer.h b/compiler/elf_writer.h
index d50a08c..c9ea0083 100644
--- a/compiler/elf_writer.h
+++ b/compiler/elf_writer.h
@@ -52,14 +52,12 @@
   virtual ~ElfWriter() {}
 
   virtual void Start() = 0;
-  virtual void PrepareDebugInfo(size_t rodata_section_size,
-                                size_t text_section_size,
-                                const ArrayRef<const debug::MethodDebugInfo>& method_infos) = 0;
+  virtual void SetLoadedSectionSizes(size_t rodata_size, size_t text_size, size_t bss_size) = 0;
+  virtual void PrepareDebugInfo(const ArrayRef<const debug::MethodDebugInfo>& method_infos) = 0;
   virtual OutputStream* StartRoData() = 0;
   virtual void EndRoData(OutputStream* rodata) = 0;
   virtual OutputStream* StartText() = 0;
   virtual void EndText(OutputStream* text) = 0;
-  virtual void SetBssSize(size_t bss_size) = 0;
   virtual void WriteDynamicSection() = 0;
   virtual void WriteDebugInfo(const ArrayRef<const debug::MethodDebugInfo>& method_infos) = 0;
   virtual void WritePatchLocations(const ArrayRef<const uintptr_t>& patch_locations) = 0;
@@ -70,6 +68,9 @@
   // should Seek() back to the position where the stream was before this operation.
   virtual OutputStream* GetStream() = 0;
 
+  // Get the size that the loaded ELF file will occupy in memory.
+  virtual size_t GetLoadedSize() = 0;
+
  protected:
   ElfWriter() = default;
 };
diff --git a/compiler/elf_writer_quick.cc b/compiler/elf_writer_quick.cc
index 1d71e57..19346ec 100644
--- a/compiler/elf_writer_quick.cc
+++ b/compiler/elf_writer_quick.cc
@@ -88,14 +88,12 @@
   ~ElfWriterQuick();
 
   void Start() OVERRIDE;
-  void PrepareDebugInfo(size_t rodata_section_size,
-                        size_t text_section_size,
-                        const ArrayRef<const debug::MethodDebugInfo>& method_infos) OVERRIDE;
+  void SetLoadedSectionSizes(size_t rodata_size, size_t text_size, size_t bss_size) OVERRIDE;
+  void PrepareDebugInfo(const ArrayRef<const debug::MethodDebugInfo>& method_infos) OVERRIDE;
   OutputStream* StartRoData() OVERRIDE;
   void EndRoData(OutputStream* rodata) OVERRIDE;
   OutputStream* StartText() OVERRIDE;
   void EndText(OutputStream* text) OVERRIDE;
-  void SetBssSize(size_t bss_size) OVERRIDE;
   void WriteDynamicSection() OVERRIDE;
   void WriteDebugInfo(const ArrayRef<const debug::MethodDebugInfo>& method_infos) OVERRIDE;
   void WritePatchLocations(const ArrayRef<const uintptr_t>& patch_locations) OVERRIDE;
@@ -103,12 +101,17 @@
 
   virtual OutputStream* GetStream() OVERRIDE;
 
+  size_t GetLoadedSize() OVERRIDE;
+
   static void EncodeOatPatches(const std::vector<uintptr_t>& locations,
                                std::vector<uint8_t>* buffer);
 
  private:
   const CompilerOptions* const compiler_options_;
   File* const elf_file_;
+  size_t rodata_size_;
+  size_t text_size_;
+  size_t bss_size_;
   std::unique_ptr<BufferedOutputStream> output_stream_;
   std::unique_ptr<ElfBuilder<ElfTypes>> builder_;
   std::unique_ptr<DebugInfoTask> debug_info_task_;
@@ -134,6 +137,9 @@
     : ElfWriter(),
       compiler_options_(compiler_options),
       elf_file_(elf_file),
+      rodata_size_(0u),
+      text_size_(0u),
+      bss_size_(0u),
       output_stream_(MakeUnique<BufferedOutputStream>(MakeUnique<FileOutputStream>(elf_file))),
       builder_(new ElfBuilder<ElfTypes>(instruction_set, output_stream_.get())) {}
 
@@ -146,6 +152,19 @@
 }
 
 template <typename ElfTypes>
+void ElfWriterQuick<ElfTypes>::SetLoadedSectionSizes(size_t rodata_size,
+                                                     size_t text_size,
+                                                     size_t bss_size) {
+  DCHECK_EQ(rodata_size_, 0u);
+  rodata_size_ = rodata_size;
+  DCHECK_EQ(text_size_, 0u);
+  text_size_ = text_size;
+  DCHECK_EQ(bss_size_, 0u);
+  bss_size_ = bss_size;
+  builder_->PrepareDynamicSection(elf_file_->GetPath(), rodata_size_, text_size_, bss_size_);
+}
+
+template <typename ElfTypes>
 OutputStream* ElfWriterQuick<ElfTypes>::StartRoData() {
   auto* rodata = builder_->GetRoData();
   rodata->Start();
@@ -172,31 +191,21 @@
 }
 
 template <typename ElfTypes>
-void ElfWriterQuick<ElfTypes>::SetBssSize(size_t bss_size) {
-  auto* bss = builder_->GetBss();
-  if (bss_size != 0u) {
-    bss->WriteNoBitsSection(bss_size);
-  }
-}
-
-template <typename ElfTypes>
 void ElfWriterQuick<ElfTypes>::WriteDynamicSection() {
-  builder_->WriteDynamicSection(elf_file_->GetPath());
+  if (bss_size_ != 0u) {
+    builder_->GetBss()->WriteNoBitsSection(bss_size_);
+  }
+  builder_->WriteDynamicSection();
 }
 
 template <typename ElfTypes>
 void ElfWriterQuick<ElfTypes>::PrepareDebugInfo(
-    size_t rodata_section_size,
-    size_t text_section_size,
     const ArrayRef<const debug::MethodDebugInfo>& method_infos) {
   if (!method_infos.empty() && compiler_options_->GetGenerateMiniDebugInfo()) {
     // Prepare the mini-debug-info in background while we do other I/O.
     Thread* self = Thread::Current();
     debug_info_task_ = std::unique_ptr<DebugInfoTask>(
-        new DebugInfoTask(builder_->GetIsa(),
-                          rodata_section_size,
-                          text_section_size,
-                          method_infos));
+        new DebugInfoTask(builder_->GetIsa(), rodata_size_, text_size_, method_infos));
     debug_info_thread_pool_ = std::unique_ptr<ThreadPool>(
         new ThreadPool("Mini-debug-info writer", 1));
     debug_info_thread_pool_->AddTask(self, debug_info_task_.get());
@@ -245,6 +254,11 @@
   return builder_->GetStream();
 }
 
+template <typename ElfTypes>
+size_t ElfWriterQuick<ElfTypes>::GetLoadedSize() {
+  return builder_->GetLoadedSize();
+}
+
 // Explicit instantiations
 template class ElfWriterQuick<ElfTypes32>;
 template class ElfWriterQuick<ElfTypes64>;
diff --git a/compiler/image_test.cc b/compiler/image_test.cc
index 4920f9b..992af29 100644
--- a/compiler/image_test.cc
+++ b/compiler/image_test.cc
@@ -28,6 +28,7 @@
 #include "elf_writer_quick.h"
 #include "gc/space/image_space.h"
 #include "image_writer.h"
+#include "linker/multi_oat_relative_patcher.h"
 #include "lock_word.h"
 #include "mirror/object-inl.h"
 #include "oat_writer.h"
@@ -72,10 +73,10 @@
   ScratchFile oat_file(OS::CreateEmptyFile(oat_filename.c_str()));
 
   const uintptr_t requested_image_base = ART_BASE_ADDRESS;
-  std::unordered_map<const DexFile*, const char*> dex_file_to_oat_filename_map;
+  std::unordered_map<const DexFile*, size_t> dex_file_to_oat_index_map;
   std::vector<const char*> oat_filename_vector(1, oat_filename.c_str());
   for (const DexFile* dex_file : class_linker->GetBootClassPath()) {
-    dex_file_to_oat_filename_map.emplace(dex_file, oat_filename.c_str());
+    dex_file_to_oat_index_map.emplace(dex_file, 0);
   }
   std::unique_ptr<ImageWriter> writer(new ImageWriter(*compiler_driver_,
                                                       requested_image_base,
@@ -83,7 +84,7 @@
                                                       /*compile_app_image*/false,
                                                       storage_mode,
                                                       oat_filename_vector,
-                                                      dex_file_to_oat_filename_map));
+                                                      dex_file_to_oat_index_map));
   // TODO: compile_pic should be a test argument.
   {
     {
@@ -123,10 +124,22 @@
           &opened_dex_files_map,
           &opened_dex_files);
       ASSERT_TRUE(dex_files_ok);
-      oat_writer.PrepareLayout(compiler_driver_.get(), writer.get(), dex_files);
+
       bool image_space_ok = writer->PrepareImageAddressSpace();
       ASSERT_TRUE(image_space_ok);
 
+      linker::MultiOatRelativePatcher patcher(compiler_driver_->GetInstructionSet(),
+                                              instruction_set_features_.get());
+      oat_writer.PrepareLayout(compiler_driver_.get(), writer.get(), dex_files, &patcher);
+      size_t rodata_size = oat_writer.GetOatHeader().GetExecutableOffset();
+      size_t text_size = oat_writer.GetSize() - rodata_size;
+      elf_writer->SetLoadedSectionSizes(rodata_size, text_size, oat_writer.GetBssSize());
+
+      writer->UpdateOatFileLayout(/* oat_index */ 0u,
+                                  elf_writer->GetLoadedSize(),
+                                  oat_writer.GetOatDataOffset(),
+                                  oat_writer.GetSize());
+
       bool rodata_ok = oat_writer.WriteRodata(rodata);
       ASSERT_TRUE(rodata_ok);
       elf_writer->EndRoData(rodata);
@@ -139,13 +152,13 @@
       bool header_ok = oat_writer.WriteHeader(elf_writer->GetStream(), 0u, 0u, 0u);
       ASSERT_TRUE(header_ok);
 
-      elf_writer->SetBssSize(oat_writer.GetBssSize());
+      writer->UpdateOatFileHeader(/* oat_index */ 0u, oat_writer.GetOatHeader());
+
       elf_writer->WriteDynamicSection();
       elf_writer->WriteDebugInfo(oat_writer.GetMethodDebugInfo());
       elf_writer->WritePatchLocations(oat_writer.GetAbsolutePatchLocations());
 
       bool success = elf_writer->End();
-
       ASSERT_TRUE(success);
     }
   }
@@ -158,12 +171,10 @@
     std::vector<const char*> dup_image_filename(1, image_file.GetFilename().c_str());
     bool success_image = writer->Write(kInvalidFd,
                                        dup_image_filename,
-                                       kInvalidFd,
-                                       dup_oat_filename,
-                                       dup_oat_filename[0]);
+                                       dup_oat_filename);
     ASSERT_TRUE(success_image);
     bool success_fixup = ElfWriter::Fixup(dup_oat.get(),
-                                          writer->GetOatDataBegin(dup_oat_filename[0]));
+                                          writer->GetOatDataBegin(0));
     ASSERT_TRUE(success_fixup);
 
     ASSERT_EQ(dup_oat->FlushCloseOrErase(), 0) << "Could not flush and close oat file "
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index a8de86d..97ad9b3 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -159,9 +159,7 @@
 
 bool ImageWriter::Write(int image_fd,
                         const std::vector<const char*>& image_filenames,
-                        int oat_fd,
-                        const std::vector<const char*>& oat_filenames,
-                        const std::string& oat_location) {
+                        const std::vector<const char*>& oat_filenames) {
   // If image_fd or oat_fd are not kInvalidFd then we may have empty strings in image_filenames or
   // oat_filenames.
   CHECK(!image_filenames.empty());
@@ -169,95 +167,13 @@
     CHECK_EQ(image_filenames.size(), 1u);
   }
   CHECK(!oat_filenames.empty());
-  if (oat_fd != kInvalidFd) {
-    CHECK_EQ(oat_filenames.size(), 1u);
-  }
   CHECK_EQ(image_filenames.size(), oat_filenames.size());
 
-  size_t oat_file_offset = 0;
-
-  for (size_t i = 0; i < oat_filenames.size(); ++i) {
-    const char* oat_filename = oat_filenames[i];
-    std::unique_ptr<File> oat_file;
-
-    if (oat_fd != -1) {
-      if (strlen(oat_filename) == 0u) {
-        oat_file.reset(new File(oat_fd, false));
-      } else {
-        oat_file.reset(new File(oat_fd, oat_filename, false));
-      }
-      int length = oat_file->GetLength();
-      if (length < 0) {
-        PLOG(ERROR) << "Oat file has negative length " << length;
-        return false;
-      } else {
-        // Leave the fd open since dex2oat still needs to write out the oat file with the fd.
-        oat_file->DisableAutoClose();
-      }
-    } else {
-      oat_file.reset(OS::OpenFileReadWrite(oat_filename));
-    }
-    if (oat_file == nullptr) {
-      PLOG(ERROR) << "Failed to open oat file " << oat_filename;
-      return false;
-    }
-    std::string error_msg;
-    oat_file_ = OatFile::OpenReadable(oat_file.get(), oat_filename, nullptr, &error_msg);
-    if (oat_file_ == nullptr) {
-      PLOG(ERROR) << "Failed to open writable oat file " << oat_filename;
-      oat_file->Erase();
-      return false;
-    }
-    Runtime::Current()->GetOatFileManager().RegisterOatFile(
-        std::unique_ptr<const OatFile>(oat_file_));
-
-    const OatHeader& oat_header = oat_file_->GetOatHeader();
-    ImageInfo& image_info = GetImageInfo(oat_filename);
-
-    size_t oat_loaded_size = 0;
-    size_t oat_data_offset = 0;
-    ElfWriter::GetOatElfInformation(oat_file.get(), &oat_loaded_size, &oat_data_offset);
-
-    DCHECK_EQ(image_info.oat_offset_, oat_file_offset);
-    oat_file_offset += oat_loaded_size;
-
-    if (i == 0) {
-      // Primary oat file, read the trampolines.
-      image_info.oat_address_offsets_[kOatAddressInterpreterToInterpreterBridge] =
-          oat_header.GetInterpreterToInterpreterBridgeOffset();
-      image_info.oat_address_offsets_[kOatAddressInterpreterToCompiledCodeBridge] =
-          oat_header.GetInterpreterToCompiledCodeBridgeOffset();
-      image_info.oat_address_offsets_[kOatAddressJNIDlsymLookup] =
-          oat_header.GetJniDlsymLookupOffset();
-      image_info.oat_address_offsets_[kOatAddressQuickGenericJNITrampoline] =
-          oat_header.GetQuickGenericJniTrampolineOffset();
-      image_info.oat_address_offsets_[kOatAddressQuickIMTConflictTrampoline] =
-          oat_header.GetQuickImtConflictTrampolineOffset();
-      image_info.oat_address_offsets_[kOatAddressQuickResolutionTrampoline] =
-          oat_header.GetQuickResolutionTrampolineOffset();
-      image_info.oat_address_offsets_[kOatAddressQuickToInterpreterBridge] =
-          oat_header.GetQuickToInterpreterBridgeOffset();
-    }
-
-
-    {
-      ScopedObjectAccess soa(Thread::Current());
-      CreateHeader(oat_loaded_size, oat_data_offset);
-      CopyAndFixupNativeData();
-    }
-
-    SetOatChecksumFromElfFile(oat_file.get());
-
-    if (oat_fd != -1) {
-      // Leave fd open for caller.
-      if (oat_file->Flush() != 0) {
-        LOG(ERROR) << "Failed to flush oat file " << oat_filename << " for " << oat_location;
-        return false;
-      }
-    } else if (oat_file->FlushCloseOrErase() != 0) {
-      LOG(ERROR) << "Failed to flush and close oat file " << oat_filename
-                 << " for " << oat_location;
-      return false;
+  {
+    ScopedObjectAccess soa(Thread::Current());
+    for (size_t i = 0; i < oat_filenames.size(); ++i) {
+      CreateHeader(i);
+      CopyAndFixupNativeData(i);
     }
   }
 
@@ -270,8 +186,7 @@
 
   for (size_t i = 0; i < image_filenames.size(); ++i) {
     const char* image_filename = image_filenames[i];
-    const char* oat_filename = oat_filenames[i];
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+    ImageInfo& image_info = GetImageInfo(i);
     std::unique_ptr<File> image_file;
     if (image_fd != kInvalidFd) {
       if (strlen(image_filename) == 0u) {
@@ -393,8 +308,8 @@
   DCHECK(object != nullptr);
   DCHECK_NE(image_objects_offset_begin_, 0u);
 
-  const char* oat_filename = GetOatFilename(object);
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(object);
+  ImageInfo& image_info = GetImageInfo(oat_index);
   size_t bin_slot_offset = image_info.bin_slot_offsets_[bin_slot.GetBin()];
   size_t new_offset = bin_slot_offset + bin_slot.GetIndex();
   DCHECK_ALIGNED(new_offset, kObjectAlignment);
@@ -414,8 +329,8 @@
   DCHECK(IsImageOffsetAssigned(object));
   LockWord lock_word = object->GetLockWord(false);
   size_t offset = lock_word.ForwardingAddress();
-  const char* oat_filename = GetOatFilename(object);
-  const ImageInfo& image_info = GetConstImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(object);
+  const ImageInfo& image_info = GetImageInfo(oat_index);
   DCHECK_LT(offset, image_info.image_end_);
   return offset;
 }
@@ -458,8 +373,8 @@
   // Set the slot size early to avoid DCHECK() failures in IsImageBinSlotAssigned()
   // when AssignImageBinSlot() assigns their indexes out or order.
   for (const DexFile* dex_file : compiler_driver_.GetDexFilesForOatFile()) {
-    auto it = dex_file_oat_filename_map_.find(dex_file);
-    DCHECK(it != dex_file_oat_filename_map_.end()) << dex_file->GetLocation();
+    auto it = dex_file_oat_index_map_.find(dex_file);
+    DCHECK(it != dex_file_oat_index_map_.end()) << dex_file->GetLocation();
     ImageInfo& image_info = GetImageInfo(it->second);
     image_info.dex_cache_array_starts_.Put(dex_file, image_info.bin_slot_sizes_[kBinDexCacheArray]);
     DexCacheArraysLayout layout(target_ptr_size_, dex_file);
@@ -478,8 +393,8 @@
     const DexFile* dex_file = dex_cache->GetDexFile();
     DexCacheArraysLayout layout(target_ptr_size_, dex_file);
     DCHECK(layout.Valid());
-    const char* oat_filename = GetOatFilenameForDexCache(dex_cache);
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+    size_t oat_index = GetOatIndexForDexCache(dex_cache);
+    ImageInfo& image_info = GetImageInfo(oat_index);
     uint32_t start = image_info.dex_cache_array_starts_.Get(dex_file);
     DCHECK_EQ(dex_file->NumTypeIds() != 0u, dex_cache->GetResolvedTypes() != nullptr);
     AddDexCacheArrayRelocation(dex_cache->GetResolvedTypes(),
@@ -501,9 +416,9 @@
 void ImageWriter::AddDexCacheArrayRelocation(void* array, size_t offset, DexCache* dex_cache) {
   if (array != nullptr) {
     DCHECK(!IsInBootImage(array));
-    const char* oat_filename = GetOatFilenameForDexCache(dex_cache);
+    size_t oat_index = GetOatIndexForDexCache(dex_cache);
     native_object_relocations_.emplace(array,
-        NativeObjectRelocation { oat_filename, offset, kNativeObjectRelocationTypeDexCacheArray });
+        NativeObjectRelocation { oat_index, offset, kNativeObjectRelocationTypeDexCacheArray });
   }
 }
 
@@ -618,8 +533,8 @@
     }  // else bin = kBinRegular
   }
 
-  const char* oat_filename = GetOatFilename(object);
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(object);
+  ImageInfo& image_info = GetImageInfo(oat_index);
 
   size_t offset_delta = RoundUp(object_size, kObjectAlignment);  // 64-bit alignment
   current_offset = image_info.bin_slot_sizes_[bin];  // How many bytes the current bin is at (aligned).
@@ -655,8 +570,8 @@
     LockWord lock_word = object->GetLockWord(false);
     size_t offset = lock_word.ForwardingAddress();
     BinSlot bin_slot(offset);
-    const char* oat_filename = GetOatFilename(object);
-    const ImageInfo& image_info = GetConstImageInfo(oat_filename);
+    size_t oat_index = GetOatIndex(object);
+    const ImageInfo& image_info = GetImageInfo(oat_index);
     DCHECK_LT(bin_slot.GetIndex(), image_info.bin_slot_sizes_[bin_slot.GetBin()])
         << "bin slot offset should not exceed the size of that bin";
   }
@@ -672,16 +587,15 @@
   DCHECK_LE(offset, std::numeric_limits<uint32_t>::max());
 
   BinSlot bin_slot(static_cast<uint32_t>(offset));
-  const char* oat_filename = GetOatFilename(object);
-  const ImageInfo& image_info = GetConstImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(object);
+  const ImageInfo& image_info = GetImageInfo(oat_index);
   DCHECK_LT(bin_slot.GetIndex(), image_info.bin_slot_sizes_[bin_slot.GetBin()]);
 
   return bin_slot;
 }
 
 bool ImageWriter::AllocMemory() {
-  for (const char* oat_filename : oat_filenames_) {
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+  for (ImageInfo& image_info : image_infos_) {
     ImageSection unused_sections[ImageHeader::kSectionCount];
     const size_t length = RoundUp(
         image_info.CreateImageSections(target_ptr_size_, unused_sections),
@@ -970,8 +884,7 @@
 
 mirror::String* ImageWriter::FindInternedString(mirror::String* string) {
   Thread* const self = Thread::Current();
-  for (auto& pair : image_info_map_) {
-    const ImageInfo& image_info = pair.second;
+  for (const ImageInfo& image_info : image_infos_) {
     mirror::String* const found = image_info.intern_table_->LookupStrong(self, string);
     DCHECK(image_info.intern_table_->LookupWeak(self, string) == nullptr)
         << string->ToModifiedUtf8();
@@ -998,8 +911,8 @@
   DCHECK(obj != nullptr);
   // if it is a string, we want to intern it if its not interned.
   if (obj->GetClass()->IsStringClass()) {
-    const char* oat_filename = GetOatFilename(obj);
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+    size_t oat_index = GetOatIndex(obj);
+    ImageInfo& image_info = GetImageInfo(oat_index);
 
     // we must be an interned string that was forward referenced and already assigned
     if (IsImageBinSlotAssigned(obj)) {
@@ -1028,7 +941,7 @@
   AssignImageBinSlot(obj);
 }
 
-ObjectArray<Object>* ImageWriter::CreateImageRoots(const char* oat_filename) const {
+ObjectArray<Object>* ImageWriter::CreateImageRoots(size_t oat_index) const {
   Runtime* runtime = Runtime::Current();
   ClassLinker* class_linker = runtime->GetClassLinker();
   Thread* self = Thread::Current();
@@ -1037,10 +950,10 @@
       class_linker->FindSystemClass(self, "[Ljava/lang/Object;")));
 
   std::unordered_set<const DexFile*> image_dex_files;
-  for (auto& pair : dex_file_oat_filename_map_) {
+  for (auto& pair : dex_file_oat_index_map_) {
     const DexFile* image_dex_file = pair.first;
-    const char* image_oat_filename = pair.second;
-    if (strcmp(oat_filename, image_oat_filename) == 0) {
+    size_t image_oat_index = pair.second;
+    if (oat_index == image_oat_index) {
       image_dex_files.insert(image_dex_file);
     }
   }
@@ -1165,8 +1078,8 @@
       LengthPrefixedArray<ArtField>* fields[] = {
           as_klass->GetSFieldsPtr(), as_klass->GetIFieldsPtr(),
       };
-      const char* oat_file = GetOatFilenameForDexCache(dex_cache);
-      ImageInfo& image_info = GetImageInfo(oat_file);
+      size_t oat_index = GetOatIndexForDexCache(dex_cache);
+      ImageInfo& image_info = GetImageInfo(oat_index);
       {
         // Note: This table is only accessed from the image writer, so the lock is technically
         // unnecessary.
@@ -1184,8 +1097,11 @@
                                                   << " already forwarded";
           size_t& offset = image_info.bin_slot_sizes_[kBinArtField];
           DCHECK(!IsInBootImage(cur_fields));
-          native_object_relocations_.emplace(cur_fields,
-              NativeObjectRelocation {oat_file, offset, kNativeObjectRelocationTypeArtFieldArray });
+          native_object_relocations_.emplace(
+              cur_fields,
+              NativeObjectRelocation {
+                  oat_index, offset, kNativeObjectRelocationTypeArtFieldArray
+              });
           offset += header_size;
           // Forward individual fields so that we can quickly find where they belong.
           for (size_t i = 0, count = cur_fields->size(); i < count; ++i) {
@@ -1195,8 +1111,9 @@
             CHECK(it2 == native_object_relocations_.end()) << "Field at index=" << i
                 << " already assigned " << PrettyField(field) << " static=" << field->IsStatic();
             DCHECK(!IsInBootImage(field));
-            native_object_relocations_.emplace(field,
-                NativeObjectRelocation {oat_file, offset, kNativeObjectRelocationTypeArtField });
+            native_object_relocations_.emplace(
+                field,
+                NativeObjectRelocation { oat_index, offset, kNativeObjectRelocationTypeArtField });
             offset += sizeof(ArtField);
           }
         }
@@ -1229,13 +1146,13 @@
         DCHECK(!IsInBootImage(array));
         native_object_relocations_.emplace(array,
             NativeObjectRelocation {
-                oat_file,
+                oat_index,
                 offset,
                 any_dirty ? kNativeObjectRelocationTypeArtMethodArrayDirty
                           : kNativeObjectRelocationTypeArtMethodArrayClean });
         offset += header_size;
         for (auto& m : as_klass->GetMethods(target_ptr_size_)) {
-          AssignMethodOffset(&m, type, oat_file);
+          AssignMethodOffset(&m, type, oat_index);
         }
         (any_dirty ? dirty_methods_ : clean_methods_) += num_methods;
       }
@@ -1263,14 +1180,14 @@
 
 void ImageWriter::AssignMethodOffset(ArtMethod* method,
                                      NativeObjectRelocationType type,
-                                     const char* oat_filename) {
+                                     size_t oat_index) {
   DCHECK(!IsInBootImage(method));
   auto it = native_object_relocations_.find(method);
   CHECK(it == native_object_relocations_.end()) << "Method " << method << " already assigned "
       << PrettyMethod(method);
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+  ImageInfo& image_info = GetImageInfo(oat_index);
   size_t& offset = image_info.bin_slot_sizes_[BinTypeForNativeRelocationType(type)];
-  native_object_relocations_.emplace(method, NativeObjectRelocation { oat_filename, offset, type });
+  native_object_relocations_.emplace(method, NativeObjectRelocation { oat_index, offset, type });
   offset += ArtMethod::Size(target_ptr_size_);
 }
 
@@ -1305,9 +1222,8 @@
   Thread* const self = Thread::Current();
   StackHandleScopeCollection handles(self);
   std::vector<Handle<ObjectArray<Object>>> image_roots;
-  for (const char* oat_filename : oat_filenames_) {
-    std::string image_filename = oat_filename;
-    image_roots.push_back(handles.NewHandle(CreateImageRoots(image_filename.c_str())));
+  for (size_t i = 0, size = oat_filenames_.size(); i != size; ++i) {
+    image_roots.push_back(handles.NewHandle(CreateImageRoots(i)));
   }
 
   auto* runtime = Runtime::Current();
@@ -1333,12 +1249,12 @@
   const auto image_method_type = kNativeObjectRelocationTypeArtMethodArrayClean;
   auto it = native_object_relocations_.find(&image_method_array_);
   CHECK(it == native_object_relocations_.end());
-  ImageInfo& default_image_info = GetImageInfo(default_oat_filename_);
+  ImageInfo& default_image_info = GetImageInfo(GetDefaultOatIndex());
   size_t& offset =
       default_image_info.bin_slot_sizes_[BinTypeForNativeRelocationType(image_method_type)];
   if (!compile_app_image_) {
     native_object_relocations_.emplace(&image_method_array_,
-        NativeObjectRelocation { default_oat_filename_, offset, image_method_type });
+        NativeObjectRelocation { GetDefaultOatIndex(), offset, image_method_type });
   }
   size_t method_alignment = ArtMethod::Alignment(target_ptr_size_);
   const size_t array_size = LengthPrefixedArray<ArtMethod>::ComputeSize(
@@ -1350,15 +1266,14 @@
     CHECK(m->IsRuntimeMethod());
     DCHECK_EQ(compile_app_image_, IsInBootImage(m)) << "Trampolines should be in boot image";
     if (!IsInBootImage(m)) {
-      AssignMethodOffset(m, kNativeObjectRelocationTypeArtMethodClean, default_oat_filename_);
+      AssignMethodOffset(m, kNativeObjectRelocationTypeArtMethodClean, GetDefaultOatIndex());
     }
   }
   // Calculate size of the dex cache arrays slot and prepare offsets.
   PrepareDexCacheArraySlots();
 
   // Calculate the sizes of the intern tables and class tables.
-  for (const char* oat_filename : oat_filenames_) {
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+  for (ImageInfo& image_info : image_infos_) {
     // Calculate how big the intern table will be after being serialized.
     InternTable* const intern_table = image_info.intern_table_.get();
     CHECK_EQ(intern_table->WeakSize(), 0u) << " should have strong interned all the strings";
@@ -1369,8 +1284,7 @@
   }
 
   // Calculate bin slot offsets.
-  for (const char* oat_filename : oat_filenames_) {
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+  for (ImageInfo& image_info : image_infos_) {
     size_t bin_offset = image_objects_offset_begin_;
     for (size_t i = 0; i != kBinSize; ++i) {
       image_info.bin_slot_offsets_[i] = bin_offset;
@@ -1390,8 +1304,7 @@
 
   // Calculate image offsets.
   size_t image_offset = 0;
-  for (const char* oat_filename : oat_filenames_) {
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+  for (ImageInfo& image_info : image_infos_) {
     image_info.image_begin_ = global_image_begin_ + image_offset;
     image_info.image_offset_ = image_offset;
     ImageSection unused_sections[ImageHeader::kSectionCount];
@@ -1408,8 +1321,7 @@
   // DCHECK_EQ(image_end_, GetBinSizeSum(kBinMirrorCount) + image_objects_offset_begin_);
 
   size_t i = 0;
-  for (const char* oat_filename : oat_filenames_) {
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+  for (ImageInfo& image_info : image_infos_) {
     image_info.image_roots_address_ = PointerToLowMemUInt32(GetImageAddress(image_roots[i].Get()));
     i++;
   }
@@ -1418,7 +1330,7 @@
   for (auto& pair : native_object_relocations_) {
     NativeObjectRelocation& relocation = pair.second;
     Bin bin_type = BinTypeForNativeRelocationType(relocation.type);
-    ImageInfo& image_info = GetImageInfo(relocation.oat_filename);
+    ImageInfo& image_info = GetImageInfo(relocation.oat_index);
     relocation.offset += image_info.bin_slot_offsets_[bin_type];
   }
 
@@ -1467,15 +1379,11 @@
   return cur_pos;
 }
 
-void ImageWriter::CreateHeader(size_t oat_loaded_size, size_t oat_data_offset) {
-  CHECK_NE(0U, oat_loaded_size);
-  const char* oat_filename = oat_file_->GetLocation().c_str();
-  ImageInfo& image_info = GetImageInfo(oat_filename);
-  const uint8_t* oat_file_begin = GetOatFileBegin(oat_filename);
-  const uint8_t* oat_file_end = oat_file_begin + oat_loaded_size;
-  image_info.oat_data_begin_ = const_cast<uint8_t*>(oat_file_begin) + oat_data_offset;
-  const uint8_t* oat_data_end = image_info.oat_data_begin_ + oat_file_->Size();
-  image_info.oat_size_ = oat_file_->Size();
+void ImageWriter::CreateHeader(size_t oat_index) {
+  ImageInfo& image_info = GetImageInfo(oat_index);
+  const uint8_t* oat_file_begin = image_info.oat_file_begin_;
+  const uint8_t* oat_file_end = oat_file_begin + image_info.oat_loaded_size_;
+  const uint8_t* oat_data_end = image_info.oat_data_begin_ + image_info.oat_size_;
 
   // Create the image sections.
   ImageSection sections[ImageHeader::kSectionCount];
@@ -1486,7 +1394,7 @@
   auto* bitmap_section = &sections[ImageHeader::kSectionImageBitmap];
   *bitmap_section = ImageSection(RoundUp(image_end, kPageSize), RoundUp(bitmap_bytes, kPageSize));
   if (VLOG_IS_ON(compiler)) {
-    LOG(INFO) << "Creating header for " << oat_filename;
+    LOG(INFO) << "Creating header for " << oat_filenames_[oat_index];
     size_t idx = 0;
     for (const ImageSection& section : sections) {
       LOG(INFO) << static_cast<ImageHeader::ImageSections>(idx) << " " << section;
@@ -1515,7 +1423,7 @@
                                                image_end,
                                                sections,
                                                image_info.image_roots_address_,
-                                               oat_file_->GetOatHeader().GetChecksum(),
+                                               image_info.oat_checksum_,
                                                PointerToLowMemUInt32(oat_file_begin),
                                                PointerToLowMemUInt32(image_info.oat_data_begin_),
                                                PointerToLowMemUInt32(oat_data_end),
@@ -1534,8 +1442,8 @@
 ArtMethod* ImageWriter::GetImageMethodAddress(ArtMethod* method) {
   auto it = native_object_relocations_.find(method);
   CHECK(it != native_object_relocations_.end()) << PrettyMethod(method) << " @ " << method;
-  const char* oat_filename = GetOatFilename(method->GetDexCache());
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(method->GetDexCache());
+  ImageInfo& image_info = GetImageInfo(oat_index);
   CHECK_GE(it->second.offset, image_info.image_end_) << "ArtMethods should be after Objects";
   return reinterpret_cast<ArtMethod*>(image_info.image_begin_ + it->second.offset);
 }
@@ -1564,14 +1472,13 @@
   ImageWriter* const image_writer_;
 };
 
-void ImageWriter::CopyAndFixupNativeData() {
-  const char* oat_filename = oat_file_->GetLocation().c_str();
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+void ImageWriter::CopyAndFixupNativeData(size_t oat_index) {
+  ImageInfo& image_info = GetImageInfo(oat_index);
   // Copy ArtFields and methods to their locations and update the array for convenience.
   for (auto& pair : native_object_relocations_) {
     NativeObjectRelocation& relocation = pair.second;
     // Only work with fields and methods that are in the current oat file.
-    if (strcmp(relocation.oat_filename, oat_filename) != 0) {
+    if (relocation.oat_index != oat_index) {
       continue;
     }
     auto* dest = image_info.image_->Begin() + relocation.offset;
@@ -1617,7 +1524,7 @@
     ArtMethod* method = image_methods_[i];
     CHECK(method != nullptr);
     // Only place runtime methods in the image of the default oat file.
-    if (method->IsRuntimeMethod() && strcmp(default_oat_filename_, oat_filename) != 0) {
+    if (method->IsRuntimeMethod() && oat_index != GetDefaultOatIndex()) {
       continue;
     }
     if (!IsInBootImage(method)) {
@@ -1722,7 +1629,7 @@
         }
         UNREACHABLE();
       } else {
-        ImageInfo& image_info = GetImageInfo(it->second.oat_filename);
+        ImageInfo& image_info = GetImageInfo(it->second.oat_index);
         elem = image_info.image_begin_ + it->second.offset;
       }
     }
@@ -1735,8 +1642,8 @@
     return;
   }
   size_t offset = GetImageOffset(obj);
-  const char* oat_filename = GetOatFilename(obj);
-  ImageInfo& image_info = GetImageInfo(oat_filename);
+  size_t oat_index = GetOatIndex(obj);
+  ImageInfo& image_info = GetImageInfo(oat_index);
   auto* dst = reinterpret_cast<Object*>(image_info.image_->Begin() + offset);
   DCHECK_LT(offset, image_info.image_end_);
   const auto* src = reinterpret_cast<const uint8_t*>(obj);
@@ -1828,7 +1735,7 @@
     CHECK(it != native_object_relocations_.end()) << obj << " spaces "
         << Runtime::Current()->GetHeap()->DumpSpaces();
     const NativeObjectRelocation& relocation = it->second;
-    ImageInfo& image_info = GetImageInfo(relocation.oat_filename);
+    ImageInfo& image_info = GetImageInfo(relocation.oat_index);
     return reinterpret_cast<T*>(image_info.image_begin_ + relocation.offset);
   }
 }
@@ -1838,8 +1745,8 @@
   if (obj == nullptr || IsInBootImage(obj)) {
     return obj;
   } else {
-    const char* oat_filename = GetOatFilenameForDexCache(dex_cache);
-    ImageInfo& image_info = GetImageInfo(oat_filename);
+    size_t oat_index = GetOatIndexForDexCache(dex_cache);
+    ImageInfo& image_info = GetImageInfo(oat_index);
     return reinterpret_cast<T*>(image_info.image_->Begin() + NativeOffsetInImage(obj));
   }
 }
@@ -2122,34 +2029,6 @@
   }
 }
 
-static OatHeader* GetOatHeaderFromElf(ElfFile* elf) {
-  uint64_t data_sec_offset;
-  bool has_data_sec = elf->GetSectionOffsetAndSize(".rodata", &data_sec_offset, nullptr);
-  if (!has_data_sec) {
-    return nullptr;
-  }
-  return reinterpret_cast<OatHeader*>(elf->Begin() + data_sec_offset);
-}
-
-void ImageWriter::SetOatChecksumFromElfFile(File* elf_file) {
-  std::string error_msg;
-  std::unique_ptr<ElfFile> elf(ElfFile::Open(elf_file,
-                                             PROT_READ | PROT_WRITE,
-                                             MAP_SHARED,
-                                             &error_msg));
-  if (elf.get() == nullptr) {
-    LOG(FATAL) << "Unable open oat file: " << error_msg;
-    return;
-  }
-  OatHeader* oat_header = GetOatHeaderFromElf(elf.get());
-  CHECK(oat_header != nullptr);
-  CHECK(oat_header->IsValid());
-
-  ImageInfo& image_info = GetImageInfo(oat_file_->GetLocation().c_str());
-  ImageHeader* image_header = reinterpret_cast<ImageHeader*>(image_info.image_->Begin());
-  image_header->SetOatChecksum(oat_header->GetChecksum());
-}
-
 size_t ImageWriter::GetBinSizeSum(ImageWriter::ImageInfo& image_info, ImageWriter::Bin up_to) const {
   DCHECK_LE(up_to, kBinSize);
   return std::accumulate(&image_info.bin_slot_sizes_[0],
@@ -2180,19 +2059,6 @@
   return lockword_ & ~kBinMask;
 }
 
-uint8_t* ImageWriter::GetOatFileBegin(const char* oat_filename) const {
-  uintptr_t last_image_end = 0;
-  for (const char* oat_fn : oat_filenames_) {
-    const ImageInfo& image_info = GetConstImageInfo(oat_fn);
-    DCHECK(image_info.image_begin_ != nullptr);
-    uintptr_t this_end = reinterpret_cast<uintptr_t>(image_info.image_begin_) +
-        image_info.image_size_;
-    last_image_end = std::max(this_end, last_image_end);
-  }
-  const ImageInfo& image_info = GetConstImageInfo(oat_filename);
-  return reinterpret_cast<uint8_t*>(last_image_end) + image_info.oat_offset_;
-}
-
 ImageWriter::Bin ImageWriter::BinTypeForNativeRelocationType(NativeObjectRelocationType type) {
   switch (type) {
     case kNativeObjectRelocationTypeArtField:
@@ -2210,91 +2076,110 @@
   UNREACHABLE();
 }
 
-const char* ImageWriter::GetOatFilename(mirror::Object* obj) const {
+size_t ImageWriter::GetOatIndex(mirror::Object* obj) const {
   if (compile_app_image_) {
-    return default_oat_filename_;
+    return GetDefaultOatIndex();
   } else {
-    return GetOatFilenameForDexCache(obj->IsDexCache() ? obj->AsDexCache() :
-        obj->IsClass() ? obj->AsClass()->GetDexCache() : obj->GetClass()->GetDexCache());
+    mirror::DexCache* dex_cache =
+        obj->IsDexCache() ? obj->AsDexCache()
+                          : obj->IsClass() ? obj->AsClass()->GetDexCache()
+                                           : obj->GetClass()->GetDexCache();
+    return GetOatIndexForDexCache(dex_cache);
   }
 }
 
-const char* ImageWriter::GetOatFilenameForDexCache(mirror::DexCache* dex_cache) const {
-  if (compile_app_image_ || dex_cache == nullptr) {
-    return default_oat_filename_;
+size_t ImageWriter::GetOatIndexForDexFile(const DexFile* dex_file) const {
+  if (compile_app_image_) {
+    return GetDefaultOatIndex();
   } else {
-    auto it = dex_file_oat_filename_map_.find(dex_cache->GetDexFile());
-    DCHECK(it != dex_file_oat_filename_map_.end()) << dex_cache->GetDexFile()->GetLocation();
+    auto it = dex_file_oat_index_map_.find(dex_file);
+    DCHECK(it != dex_file_oat_index_map_.end()) << dex_file->GetLocation();
     return it->second;
   }
 }
 
-ImageWriter::ImageInfo& ImageWriter::GetImageInfo(const char* oat_filename) {
-  auto it = image_info_map_.find(oat_filename);
-  DCHECK(it != image_info_map_.end());
-  return it->second;
+size_t ImageWriter::GetOatIndexForDexCache(mirror::DexCache* dex_cache) const {
+  if (dex_cache == nullptr) {
+    return GetDefaultOatIndex();
+  } else {
+    return GetOatIndexForDexFile(dex_cache->GetDexFile());
+  }
 }
 
-const ImageWriter::ImageInfo& ImageWriter::GetConstImageInfo(const char* oat_filename) const {
-  auto it = image_info_map_.find(oat_filename);
-  DCHECK(it != image_info_map_.end());
-  return it->second;
-}
+void ImageWriter::UpdateOatFileLayout(size_t oat_index,
+                                      size_t oat_loaded_size,
+                                      size_t oat_data_offset,
+                                      size_t oat_data_size) {
+  const uint8_t* images_end = image_infos_.back().image_begin_ + image_infos_.back().image_size_;
+  for (const ImageInfo& info : image_infos_) {
+    DCHECK_LE(info.image_begin_ + info.image_size_, images_end);
+  }
+  DCHECK(images_end != nullptr);  // Image space must be ready.
 
-const ImageWriter::ImageInfo& ImageWriter::GetImageInfo(size_t index) const {
-  DCHECK_LT(index, oat_filenames_.size());
-  return GetConstImageInfo(oat_filenames_[index]);
-}
+  ImageInfo& cur_image_info = GetImageInfo(oat_index);
+  cur_image_info.oat_file_begin_ = images_end + cur_image_info.oat_offset_;
+  cur_image_info.oat_loaded_size_ = oat_loaded_size;
+  cur_image_info.oat_data_begin_ = cur_image_info.oat_file_begin_ + oat_data_offset;
+  cur_image_info.oat_size_ = oat_data_size;
 
-void ImageWriter::UpdateOatFile(File* oat_file, const char* oat_filename) {
-  DCHECK(oat_file != nullptr);
   if (compile_app_image_) {
     CHECK_EQ(oat_filenames_.size(), 1u) << "App image should have no next image.";
     return;
   }
-  ImageInfo& cur_image_info = GetImageInfo(oat_filename);
 
   // Update the oat_offset of the next image info.
-  auto it = std::find(oat_filenames_.begin(), oat_filenames_.end(), oat_filename);
-  DCHECK(it != oat_filenames_.end());
-
-  it++;
-  if (it != oat_filenames_.end()) {
-    size_t oat_loaded_size = 0;
-    size_t oat_data_offset = 0;
-    ElfWriter::GetOatElfInformation(oat_file, &oat_loaded_size, &oat_data_offset);
+  if (oat_index + 1u != oat_filenames_.size()) {
     // There is a following one.
-    ImageInfo& next_image_info = GetImageInfo(*it);
+    ImageInfo& next_image_info = GetImageInfo(oat_index + 1u);
     next_image_info.oat_offset_ = cur_image_info.oat_offset_ + oat_loaded_size;
   }
 }
 
+void ImageWriter::UpdateOatFileHeader(size_t oat_index, const OatHeader& oat_header) {
+  ImageInfo& cur_image_info = GetImageInfo(oat_index);
+  cur_image_info.oat_checksum_ = oat_header.GetChecksum();
+
+  if (oat_index == GetDefaultOatIndex()) {
+    // Primary oat file, read the trampolines.
+    cur_image_info.oat_address_offsets_[kOatAddressInterpreterToInterpreterBridge] =
+        oat_header.GetInterpreterToInterpreterBridgeOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressInterpreterToCompiledCodeBridge] =
+        oat_header.GetInterpreterToCompiledCodeBridgeOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressJNIDlsymLookup] =
+        oat_header.GetJniDlsymLookupOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressQuickGenericJNITrampoline] =
+        oat_header.GetQuickGenericJniTrampolineOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressQuickIMTConflictTrampoline] =
+        oat_header.GetQuickImtConflictTrampolineOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressQuickResolutionTrampoline] =
+        oat_header.GetQuickResolutionTrampolineOffset();
+    cur_image_info.oat_address_offsets_[kOatAddressQuickToInterpreterBridge] =
+        oat_header.GetQuickToInterpreterBridgeOffset();
+  }
+}
+
 ImageWriter::ImageWriter(
     const CompilerDriver& compiler_driver,
     uintptr_t image_begin,
     bool compile_pic,
     bool compile_app_image,
     ImageHeader::StorageMode image_storage_mode,
-    const std::vector<const char*> oat_filenames,
-    const std::unordered_map<const DexFile*, const char*>& dex_file_oat_filename_map)
+    const std::vector<const char*>& oat_filenames,
+    const std::unordered_map<const DexFile*, size_t>& dex_file_oat_index_map)
     : compiler_driver_(compiler_driver),
       global_image_begin_(reinterpret_cast<uint8_t*>(image_begin)),
       image_objects_offset_begin_(0),
-      oat_file_(nullptr),
       compile_pic_(compile_pic),
       compile_app_image_(compile_app_image),
       target_ptr_size_(InstructionSetPointerSize(compiler_driver_.GetInstructionSet())),
+      image_infos_(oat_filenames.size()),
       image_method_array_(ImageHeader::kImageMethodsCount),
       dirty_methods_(0u),
       clean_methods_(0u),
       image_storage_mode_(image_storage_mode),
-      dex_file_oat_filename_map_(dex_file_oat_filename_map),
       oat_filenames_(oat_filenames),
-      default_oat_filename_(oat_filenames[0]) {
+      dex_file_oat_index_map_(dex_file_oat_index_map) {
   CHECK_NE(image_begin, 0U);
-  for (const char* oat_filename : oat_filenames) {
-    image_info_map_.emplace(oat_filename, ImageInfo());
-  }
   std::fill_n(image_methods_, arraysize(image_methods_), nullptr);
 }
 
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index b227c44..34d47bc 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -27,6 +27,7 @@
 #include <ostream>
 
 #include "base/bit_utils.h"
+#include "base/dchecked_vector.h"
 #include "base/length_prefixed_array.h"
 #include "base/macros.h"
 #include "driver/compiler_driver.h"
@@ -59,20 +60,19 @@
               bool compile_pic,
               bool compile_app_image,
               ImageHeader::StorageMode image_storage_mode,
-              const std::vector<const char*> oat_filenames,
-              const std::unordered_map<const DexFile*, const char*>& dex_file_oat_filename_map);
+              const std::vector<const char*>& oat_filenames,
+              const std::unordered_map<const DexFile*, size_t>& dex_file_oat_index_map);
 
   bool PrepareImageAddressSpace();
 
   bool IsImageAddressSpaceReady() const {
-    bool ready = !image_info_map_.empty();
-    for (auto& pair : image_info_map_) {
-      const ImageInfo& image_info = pair.second;
+    DCHECK(!image_infos_.empty());
+    for (const ImageInfo& image_info : image_infos_) {
       if (image_info.image_roots_address_ == 0u) {
         return false;
       }
     }
-    return ready;
+    return true;
   }
 
   template <typename T>
@@ -80,8 +80,8 @@
     if (object == nullptr || IsInBootImage(object)) {
       return object;
     } else {
-      const char* oat_filename = GetOatFilename(object);
-      const ImageInfo& image_info = GetConstImageInfo(oat_filename);
+      size_t oat_index = GetOatIndex(object);
+      const ImageInfo& image_info = GetImageInfo(oat_index);
       return reinterpret_cast<T*>(image_info.image_begin_ + GetImageOffset(object));
     }
   }
@@ -91,9 +91,9 @@
   template <typename PtrType>
   PtrType GetDexCacheArrayElementImageAddress(const DexFile* dex_file, uint32_t offset)
       const SHARED_REQUIRES(Locks::mutator_lock_) {
-    auto oat_it = dex_file_oat_filename_map_.find(dex_file);
-    DCHECK(oat_it != dex_file_oat_filename_map_.end());
-    const ImageInfo& image_info = GetConstImageInfo(oat_it->second);
+    auto oat_it = dex_file_oat_index_map_.find(dex_file);
+    DCHECK(oat_it != dex_file_oat_index_map_.end());
+    const ImageInfo& image_info = GetImageInfo(oat_it->second);
     auto it = image_info.dex_cache_array_starts_.find(dex_file);
     DCHECK(it != image_info.dex_cache_array_starts_.end());
     return reinterpret_cast<PtrType>(
@@ -101,7 +101,13 @@
             it->second + offset);
   }
 
-  uint8_t* GetOatFileBegin(const char* oat_filename) const;
+  size_t GetOatFileOffset(size_t oat_index) const {
+    return GetImageInfo(oat_index).oat_offset_;
+  }
+
+  const uint8_t* GetOatFileBegin(size_t oat_index) const {
+    return GetImageInfo(oat_index).oat_file_begin_;
+  }
 
   // If image_fd is not kInvalidFd, then we use that for the image file. Otherwise we open
   // the names in image_filenames.
@@ -109,21 +115,32 @@
   // the names in oat_filenames.
   bool Write(int image_fd,
              const std::vector<const char*>& image_filenames,
-             int oat_fd,
-             const std::vector<const char*>& oat_filenames,
-             const std::string& oat_location)
+             const std::vector<const char*>& oat_filenames)
       REQUIRES(!Locks::mutator_lock_);
 
-  uintptr_t GetOatDataBegin(const char* oat_filename) {
-    return reinterpret_cast<uintptr_t>(GetImageInfo(oat_filename).oat_data_begin_);
+  uintptr_t GetOatDataBegin(size_t oat_index) {
+    return reinterpret_cast<uintptr_t>(GetImageInfo(oat_index).oat_data_begin_);
   }
 
-  const char* GetOatFilenameForDexCache(mirror::DexCache* dex_cache) const
+  // Get the index of the oat file containing the dex file.
+  //
+  // This "oat_index" is used to retrieve information about the the memory layout
+  // of the oat file and its associated image file, needed for link-time patching
+  // of references to the image or across oat files.
+  size_t GetOatIndexForDexFile(const DexFile* dex_file) const;
+
+  // Get the index of the oat file containing the dex file served by the dex cache.
+  size_t GetOatIndexForDexCache(mirror::DexCache* dex_cache) const
       SHARED_REQUIRES(Locks::mutator_lock_);
 
-  // Update the oat size for the given oat file. This will make the oat_offset for the next oat
-  // file valid.
-  void UpdateOatFile(File* oat_file, const char* oat_filename);
+  // Update the oat layout for the given oat file.
+  // This will make the oat_offset for the next oat file valid.
+  void UpdateOatFileLayout(size_t oat_index,
+                           size_t oat_loaded_size,
+                           size_t oat_data_offset,
+                           size_t oat_data_size);
+  // Update information about the oat header, i.e. checksum and trampoline offsets.
+  void UpdateOatFileHeader(size_t oat_index, const OatHeader& oat_header);
 
  private:
   bool AllocMemory();
@@ -247,10 +264,13 @@
     // Offset of the oat file for this image from start of oat files. This is
     // valid when the previous oat file has been written.
     size_t oat_offset_ = 0;
-    // Start of oatdata in the corresponding oat file. This is
-    // valid when the images have been layed out.
-    uint8_t* oat_data_begin_ = nullptr;
+    // Layout of the loaded ELF file containing the oat file, valid after UpdateOatFileLayout().
+    const uint8_t* oat_file_begin_ = nullptr;
+    size_t oat_loaded_size_ = 0;
+    const uint8_t* oat_data_begin_ = nullptr;
     size_t oat_size_ = 0;  // Size of the corresponding oat data.
+    // The oat header checksum, valid after UpdateOatFileHeader().
+    uint32_t oat_checksum_ = 0u;
 
     // Image bitmap which lets us know where the objects inside of the image reside.
     std::unique_ptr<gc::accounting::ContinuousSpaceBitmap> image_bitmap_;
@@ -310,8 +330,8 @@
   mirror::Object* GetLocalAddress(mirror::Object* object) const
       SHARED_REQUIRES(Locks::mutator_lock_) {
     size_t offset = GetImageOffset(object);
-    const char* oat_filename = GetOatFilename(object);
-    const ImageInfo& image_info = GetConstImageInfo(oat_filename);
+    size_t oat_index = GetOatIndex(object);
+    const ImageInfo& image_info = GetImageInfo(oat_index);
     uint8_t* dst = image_info.image_->Begin() + offset;
     return reinterpret_cast<mirror::Object*>(dst);
   }
@@ -348,9 +368,9 @@
   // Lays out where the image objects will be at runtime.
   void CalculateNewObjectOffsets()
       SHARED_REQUIRES(Locks::mutator_lock_);
-  void CreateHeader(size_t oat_loaded_size, size_t oat_data_offset)
+  void CreateHeader(size_t oat_index)
       SHARED_REQUIRES(Locks::mutator_lock_);
-  mirror::ObjectArray<mirror::Object>* CreateImageRoots(const char* oat_filename) const
+  mirror::ObjectArray<mirror::Object>* CreateImageRoots(size_t oat_index) const
       SHARED_REQUIRES(Locks::mutator_lock_);
   void CalculateObjectBinSlots(mirror::Object* obj)
       SHARED_REQUIRES(Locks::mutator_lock_);
@@ -367,7 +387,7 @@
       SHARED_REQUIRES(Locks::mutator_lock_);
 
   // Creates the contiguous image in memory and adjusts pointers.
-  void CopyAndFixupNativeData() SHARED_REQUIRES(Locks::mutator_lock_);
+  void CopyAndFixupNativeData(size_t oat_index) SHARED_REQUIRES(Locks::mutator_lock_);
   void CopyAndFixupObjects() SHARED_REQUIRES(Locks::mutator_lock_);
   static void CopyAndFixupObjectsCallback(mirror::Object* obj, void* arg)
       SHARED_REQUIRES(Locks::mutator_lock_);
@@ -392,9 +412,6 @@
                               bool* quick_is_interpreted)
       SHARED_REQUIRES(Locks::mutator_lock_);
 
-  // Patches references in OatFile to expect runtime addresses.
-  void SetOatChecksumFromElfFile(File* elf_file);
-
   // Calculate the sum total of the bin slot sizes in [0, up_to). Defaults to all bins.
   size_t GetBinSizeSum(ImageInfo& image_info, Bin up_to = kBinSize) const;
 
@@ -404,7 +421,7 @@
   // Assign the offset for an ArtMethod.
   void AssignMethodOffset(ArtMethod* method,
                           NativeObjectRelocationType type,
-                          const char* oat_filename)
+                          size_t oat_index)
       SHARED_REQUIRES(Locks::mutator_lock_);
 
   // Return true if klass is loaded by the boot class loader but not in the boot image.
@@ -441,15 +458,21 @@
   // Return true if ptr is within the boot oat file.
   bool IsInBootOatFile(const void* ptr) const;
 
-  const char* GetOatFilename(mirror::Object* object) const SHARED_REQUIRES(Locks::mutator_lock_);
+  // Get the index of the oat file associated with the object.
+  size_t GetOatIndex(mirror::Object* object) const SHARED_REQUIRES(Locks::mutator_lock_);
 
-  const char* GetDefaultOatFilename() const {
-    return default_oat_filename_;
+  // The oat index for shared data in multi-image and all data in single-image compilation.
+  size_t GetDefaultOatIndex() const {
+    return 0u;
   }
 
-  ImageInfo& GetImageInfo(const char* oat_filename);
-  const ImageInfo& GetConstImageInfo(const char* oat_filename) const;
-  const ImageInfo& GetImageInfo(size_t index) const;
+  ImageInfo& GetImageInfo(size_t oat_index) {
+    return image_infos_[oat_index];
+  }
+
+  const ImageInfo& GetImageInfo(size_t oat_index) const {
+    return image_infos_[oat_index];
+  }
 
   // Find an already strong interned string in the other images or in the boot image. Used to
   // remove duplicates in the multi image and app image case.
@@ -463,9 +486,6 @@
   // Offset from image_begin_ to where the first object is in image_.
   size_t image_objects_offset_begin_;
 
-  // oat file with code for this image
-  OatFile* oat_file_;
-
   // Pointer arrays that need to be updated. Since these are only some int and long arrays, we need
   // to keep track. These include vtable arrays, iftable arrays, and dex caches.
   std::unordered_map<mirror::PointerArray*, Bin> pointer_arrays_;
@@ -481,14 +501,14 @@
   // Size of pointers on the target architecture.
   size_t target_ptr_size_;
 
-  // Mapping of oat filename to image data.
-  std::unordered_map<std::string, ImageInfo> image_info_map_;
+  // Image data indexed by the oat file index.
+  dchecked_vector<ImageInfo> image_infos_;
 
   // ArtField, ArtMethod relocating map. These are allocated as array of structs but we want to
   // have one entry per art field for convenience. ArtFields are placed right after the end of the
   // image objects (aka sum of bin_slot_sizes_). ArtMethods are placed right after the ArtFields.
   struct NativeObjectRelocation {
-    const char* oat_filename;
+    size_t oat_index;
     uintptr_t offset;
     NativeObjectRelocationType type;
 
@@ -520,10 +540,11 @@
   // Which mode the image is stored as, see image.h
   const ImageHeader::StorageMode image_storage_mode_;
 
-  // Map of dex files to the oat filenames that they were compiled into.
-  const std::unordered_map<const DexFile*, const char*>& dex_file_oat_filename_map_;
-  const std::vector<const char*> oat_filenames_;
-  const char* default_oat_filename_;
+  // The file names of oat files.
+  const std::vector<const char*>& oat_filenames_;
+
+  // Map of dex files to the indexes of oat files that they were compiled into.
+  const std::unordered_map<const DexFile*, size_t>& dex_file_oat_index_map_;
 
   friend class ContainsBootClassLoaderNonImageClassVisitor;
   friend class FixupClassVisitor;
diff --git a/compiler/jit/jit_compiler.cc b/compiler/jit/jit_compiler.cc
index 3fe7861..c2b29eb 100644
--- a/compiler/jit/jit_compiler.cc
+++ b/compiler/jit/jit_compiler.cc
@@ -172,7 +172,6 @@
       /* dump_passes */ false,
       cumulative_logger_.get(),
       /* swap_fd */ -1,
-      /* dex to oat map */ nullptr,
       /* profile_compilation_info */ nullptr));
   // Disable dedupe so we can remove compiled methods.
   compiler_driver_->SetDedupeEnabled(false);
diff --git a/compiler/linker/arm/relative_patcher_arm_base.cc b/compiler/linker/arm/relative_patcher_arm_base.cc
index 73b0fac..682b008 100644
--- a/compiler/linker/arm/relative_patcher_arm_base.cc
+++ b/compiler/linker/arm/relative_patcher_arm_base.cc
@@ -40,6 +40,11 @@
                                                 MethodReference(nullptr, 0u),
                                                 aligned_offset);
   if (needs_thunk) {
+    // All remaining patches will be handled by this thunk.
+    DCHECK(!unprocessed_patches_.empty());
+    DCHECK_LE(aligned_offset - unprocessed_patches_.front().second, max_positive_displacement_);
+    unprocessed_patches_.clear();
+
     thunk_locations_.push_back(aligned_offset);
     offset = CompiledMethod::AlignCode(aligned_offset + thunk_code_.size(), instruction_set_);
   }
diff --git a/compiler/linker/arm/relative_patcher_arm_base.h b/compiler/linker/arm/relative_patcher_arm_base.h
index f80dd96..25fd35e 100644
--- a/compiler/linker/arm/relative_patcher_arm_base.h
+++ b/compiler/linker/arm/relative_patcher_arm_base.h
@@ -27,18 +27,23 @@
 
 class ArmBaseRelativePatcher : public RelativePatcher {
  public:
-  uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method,
+  uint32_t ReserveSpace(uint32_t offset,
+                        const CompiledMethod* compiled_method,
                         MethodReference method_ref) OVERRIDE;
   uint32_t ReserveSpaceEnd(uint32_t offset) OVERRIDE;
   uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE;
 
  protected:
   ArmBaseRelativePatcher(RelativePatcherTargetProvider* provider,
-                         InstructionSet instruction_set, std::vector<uint8_t> thunk_code,
-                         uint32_t max_positive_displacement, uint32_t max_negative_displacement);
+                         InstructionSet instruction_set,
+                         std::vector<uint8_t> thunk_code,
+                         uint32_t max_positive_displacement,
+                         uint32_t max_negative_displacement);
 
-  uint32_t ReserveSpaceInternal(uint32_t offset, const CompiledMethod* compiled_method,
-                                MethodReference method_ref, uint32_t max_extra_space);
+  uint32_t ReserveSpaceInternal(uint32_t offset,
+                                const CompiledMethod* compiled_method,
+                                MethodReference method_ref,
+                                uint32_t max_extra_space);
   uint32_t CalculateDisplacement(uint32_t patch_offset, uint32_t target_offset);
 
  private:
diff --git a/compiler/linker/arm/relative_patcher_thumb2.cc b/compiler/linker/arm/relative_patcher_thumb2.cc
index 5f4f760..c090dff 100644
--- a/compiler/linker/arm/relative_patcher_thumb2.cc
+++ b/compiler/linker/arm/relative_patcher_thumb2.cc
@@ -28,8 +28,10 @@
                              kMaxPositiveDisplacement, kMaxNegativeDisplacement) {
 }
 
-void Thumb2RelativePatcher::PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                                      uint32_t patch_offset, uint32_t target_offset) {
+void Thumb2RelativePatcher::PatchCall(std::vector<uint8_t>* code,
+                                      uint32_t literal_offset,
+                                      uint32_t patch_offset,
+                                      uint32_t target_offset) {
   DCHECK_LE(literal_offset + 4u, code->size());
   DCHECK_EQ(literal_offset & 1u, 0u);
   DCHECK_EQ(patch_offset & 1u, 0u);
diff --git a/compiler/linker/arm/relative_patcher_thumb2.h b/compiler/linker/arm/relative_patcher_thumb2.h
index 006d6fb..0d903c0 100644
--- a/compiler/linker/arm/relative_patcher_thumb2.h
+++ b/compiler/linker/arm/relative_patcher_thumb2.h
@@ -26,10 +26,14 @@
  public:
   explicit Thumb2RelativePatcher(RelativePatcherTargetProvider* provider);
 
-  void PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                 uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
-  void PatchDexCacheReference(std::vector<uint8_t>* code, const LinkerPatch& patch,
-                              uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
+  void PatchCall(std::vector<uint8_t>* code,
+                 uint32_t literal_offset,
+                 uint32_t patch_offset,
+                 uint32_t target_offset) OVERRIDE;
+  void PatchDexCacheReference(std::vector<uint8_t>* code,
+                              const LinkerPatch& patch,
+                              uint32_t patch_offset,
+                              uint32_t target_offset) OVERRIDE;
 
  private:
   static std::vector<uint8_t> CompileThunkCode();
diff --git a/compiler/linker/arm64/relative_patcher_arm64.cc b/compiler/linker/arm64/relative_patcher_arm64.cc
index 3d4c218..a81c85c 100644
--- a/compiler/linker/arm64/relative_patcher_arm64.cc
+++ b/compiler/linker/arm64/relative_patcher_arm64.cc
@@ -131,8 +131,10 @@
   return ArmBaseRelativePatcher::WriteThunks(out, offset);
 }
 
-void Arm64RelativePatcher::PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                                     uint32_t patch_offset, uint32_t target_offset) {
+void Arm64RelativePatcher::PatchCall(std::vector<uint8_t>* code,
+                                     uint32_t literal_offset,
+                                     uint32_t patch_offset, uint32_t
+                                     target_offset) {
   DCHECK_LE(literal_offset + 4u, code->size());
   DCHECK_EQ(literal_offset & 3u, 0u);
   DCHECK_EQ(patch_offset & 3u, 0u);
diff --git a/compiler/linker/arm64/relative_patcher_arm64.h b/compiler/linker/arm64/relative_patcher_arm64.h
index 2d07e75..f9b76e6 100644
--- a/compiler/linker/arm64/relative_patcher_arm64.h
+++ b/compiler/linker/arm64/relative_patcher_arm64.h
@@ -28,14 +28,19 @@
   Arm64RelativePatcher(RelativePatcherTargetProvider* provider,
                        const Arm64InstructionSetFeatures* features);
 
-  uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method,
+  uint32_t ReserveSpace(uint32_t offset,
+                        const CompiledMethod* compiled_method,
                         MethodReference method_ref) OVERRIDE;
   uint32_t ReserveSpaceEnd(uint32_t offset) OVERRIDE;
   uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE;
-  void PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                 uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
-  void PatchDexCacheReference(std::vector<uint8_t>* code, const LinkerPatch& patch,
-                              uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
+  void PatchCall(std::vector<uint8_t>* code,
+                 uint32_t literal_offset,
+                 uint32_t patch_offset,
+                 uint32_t target_offset) OVERRIDE;
+  void PatchDexCacheReference(std::vector<uint8_t>* code,
+                              const LinkerPatch& patch,
+                              uint32_t patch_offset,
+                              uint32_t target_offset) OVERRIDE;
 
  private:
   static std::vector<uint8_t> CompileThunkCode();
diff --git a/compiler/linker/multi_oat_relative_patcher.cc b/compiler/linker/multi_oat_relative_patcher.cc
new file mode 100644
index 0000000..e9e242b
--- /dev/null
+++ b/compiler/linker/multi_oat_relative_patcher.cc
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "multi_oat_relative_patcher.h"
+
+#include "globals.h"
+#include "base/bit_utils.h"
+#include "base/logging.h"
+
+namespace art {
+namespace linker {
+
+MultiOatRelativePatcher::MultiOatRelativePatcher(InstructionSet instruction_set,
+                                                 const InstructionSetFeatures* features)
+    : method_offset_map_(),
+      relative_patcher_(
+          linker::RelativePatcher::Create(instruction_set, features, &method_offset_map_)),
+      adjustment_(0u),
+      instruction_set_(instruction_set),
+      start_size_code_alignment_(0u),
+      start_size_relative_call_thunks_(0u),
+      start_size_misc_thunks_(0u) {
+}
+
+void MultiOatRelativePatcher::StartOatFile(uint32_t adjustment) {
+  DCHECK_ALIGNED(adjustment, kPageSize);
+  adjustment_ = adjustment;
+
+  start_size_code_alignment_ = relative_patcher_->CodeAlignmentSize();
+  start_size_relative_call_thunks_ = relative_patcher_->RelativeCallThunksSize();
+  start_size_misc_thunks_ = relative_patcher_->MiscThunksSize();
+}
+
+uint32_t MultiOatRelativePatcher::CodeAlignmentSize() const {
+  DCHECK_GE(relative_patcher_->CodeAlignmentSize(), start_size_code_alignment_);
+  return relative_patcher_->CodeAlignmentSize() - start_size_code_alignment_;
+}
+
+uint32_t MultiOatRelativePatcher::RelativeCallThunksSize() const {
+  DCHECK_GE(relative_patcher_->RelativeCallThunksSize(), start_size_relative_call_thunks_);
+  return relative_patcher_->RelativeCallThunksSize() - start_size_relative_call_thunks_;
+}
+
+uint32_t MultiOatRelativePatcher::MiscThunksSize() const {
+  DCHECK_GE(relative_patcher_->MiscThunksSize(), start_size_misc_thunks_);
+  return relative_patcher_->MiscThunksSize() - start_size_misc_thunks_;
+}
+
+std::pair<bool, uint32_t> MultiOatRelativePatcher::MethodOffsetMap::FindMethodOffset(
+    MethodReference ref) {
+  auto it = map.find(ref);
+  if (it == map.end()) {
+    return std::pair<bool, uint32_t>(false, 0u);
+  } else {
+    return std::pair<bool, uint32_t>(true, it->second);
+  }
+}
+}  // namespace linker
+}  // namespace art
diff --git a/compiler/linker/multi_oat_relative_patcher.h b/compiler/linker/multi_oat_relative_patcher.h
new file mode 100644
index 0000000..1727d52
--- /dev/null
+++ b/compiler/linker/multi_oat_relative_patcher.h
@@ -0,0 +1,146 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_LINKER_MULTI_OAT_RELATIVE_PATCHER_H_
+#define ART_COMPILER_LINKER_MULTI_OAT_RELATIVE_PATCHER_H_
+
+#include "arch/instruction_set.h"
+#include "method_reference.h"
+#include "relative_patcher.h"
+#include "safe_map.h"
+
+namespace art {
+
+class CompiledMethod;
+class LinkerPatch;
+class InstructionSetFeatures;
+
+namespace linker {
+
+// MultiOatRelativePatcher is a helper class for handling patching across
+// any number of oat files. It provides storage for method code offsets
+// and wraps RelativePatcher calls, adjusting relative offsets according
+// to the value set by SetAdjustment().
+class MultiOatRelativePatcher FINAL {
+ public:
+  using const_iterator =
+      SafeMap<MethodReference, uint32_t, MethodReferenceComparator>::const_iterator;
+
+  MultiOatRelativePatcher(InstructionSet instruction_set, const InstructionSetFeatures* features);
+
+  // Mark the start of a new oat file (for statistics retrieval) and set the
+  // adjustment for a new oat file to apply to all relative offsets that are
+  // passed to the MultiOatRelativePatcher.
+  //
+  // The adjustment should be the global offset of the base from which relative
+  // offsets are calculated, such as the start of .rodata for the current oat file.
+  // It must must never point directly to a method's code to avoid relative offsets
+  // with value 0 because this value is used as a missing offset indication in
+  // GetOffset() and an error indication in WriteThunks(). Additionally, it must be
+  // page-aligned, so that it does not skew alignment calculations, say arm64 ADRP.
+  void StartOatFile(uint32_t adjustment);
+
+  // Get relative offset. Returns 0 when the offset has not been set yet.
+  uint32_t GetOffset(MethodReference method_ref) {
+    auto it = method_offset_map_.map.find(method_ref);
+    return (it != method_offset_map_.map.end()) ? it->second - adjustment_ : 0u;
+  }
+
+  // Set the offset.
+  void SetOffset(MethodReference method_ref, uint32_t offset) {
+    method_offset_map_.map.Put(method_ref, offset + adjustment_);
+  }
+
+  // Wrapper around RelativePatcher::ReserveSpace(), doing offset adjustment.
+  uint32_t ReserveSpace(uint32_t offset,
+                        const CompiledMethod* compiled_method,
+                        MethodReference method_ref) {
+    offset += adjustment_;
+    offset = relative_patcher_->ReserveSpace(offset, compiled_method, method_ref);
+    offset -= adjustment_;
+    return offset;
+  }
+
+  // Wrapper around RelativePatcher::ReserveSpaceEnd(), doing offset adjustment.
+  uint32_t ReserveSpaceEnd(uint32_t offset) {
+    offset += adjustment_;
+    offset = relative_patcher_->ReserveSpaceEnd(offset);
+    offset -= adjustment_;
+    return offset;
+  }
+
+  // Wrapper around RelativePatcher::WriteThunks(), doing offset adjustment.
+  uint32_t WriteThunks(OutputStream* out, uint32_t offset) {
+    offset += adjustment_;
+    offset = relative_patcher_->WriteThunks(out, offset);
+    if (offset != 0u) {  // 0u indicates write error.
+      offset -= adjustment_;
+    }
+    return offset;
+  }
+
+  // Wrapper around RelativePatcher::PatchCall(), doing offset adjustment.
+  void PatchCall(std::vector<uint8_t>* code,
+                 uint32_t literal_offset,
+                 uint32_t patch_offset,
+                 uint32_t target_offset) {
+    patch_offset += adjustment_;
+    target_offset += adjustment_;
+    relative_patcher_->PatchCall(code, literal_offset, patch_offset, target_offset);
+  }
+
+  // Wrapper around RelativePatcher::PatchDexCacheReference(), doing offset adjustment.
+  void PatchDexCacheReference(std::vector<uint8_t>* code,
+                              const LinkerPatch& patch,
+                              uint32_t patch_offset,
+                              uint32_t target_offset) {
+    patch_offset += adjustment_;
+    target_offset += adjustment_;
+    relative_patcher_->PatchDexCacheReference(code, patch, patch_offset, target_offset);
+  }
+
+  // Wrappers around RelativePatcher for statistics retrieval.
+  uint32_t CodeAlignmentSize() const;
+  uint32_t RelativeCallThunksSize() const;
+  uint32_t MiscThunksSize() const;
+
+ private:
+  // Map method reference to assigned offset.
+  // Wrap the map in a class implementing linker::RelativePatcherTargetProvider.
+  class MethodOffsetMap : public linker::RelativePatcherTargetProvider {
+   public:
+    std::pair<bool, uint32_t> FindMethodOffset(MethodReference ref) OVERRIDE;
+    SafeMap<MethodReference, uint32_t, MethodReferenceComparator> map;
+  };
+
+  MethodOffsetMap method_offset_map_;
+  std::unique_ptr<RelativePatcher> relative_patcher_;
+  uint32_t adjustment_;
+  InstructionSet instruction_set_;
+
+  uint32_t start_size_code_alignment_;
+  uint32_t start_size_relative_call_thunks_;
+  uint32_t start_size_misc_thunks_;
+
+  friend class MultiOatRelativePatcherTest;
+
+  DISALLOW_COPY_AND_ASSIGN(MultiOatRelativePatcher);
+};
+
+}  // namespace linker
+}  // namespace art
+
+#endif  // ART_COMPILER_LINKER_MULTI_OAT_RELATIVE_PATCHER_H_
diff --git a/compiler/linker/multi_oat_relative_patcher_test.cc b/compiler/linker/multi_oat_relative_patcher_test.cc
new file mode 100644
index 0000000..792cdfe
--- /dev/null
+++ b/compiler/linker/multi_oat_relative_patcher_test.cc
@@ -0,0 +1,299 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "compiled_method.h"
+#include "gtest/gtest.h"
+#include "multi_oat_relative_patcher.h"
+#include "vector_output_stream.h"
+
+namespace art {
+namespace linker {
+
+static const MethodReference kNullMethodRef = MethodReference(nullptr, 0u);
+
+static bool EqualRef(MethodReference lhs, MethodReference rhs) {
+  return lhs.dex_file == rhs.dex_file && lhs.dex_method_index == rhs.dex_method_index;
+}
+
+class MultiOatRelativePatcherTest : public testing::Test {
+ protected:
+  class MockPatcher : public RelativePatcher {
+   public:
+    MockPatcher() { }
+
+    uint32_t ReserveSpace(uint32_t offset,
+                          const CompiledMethod* compiled_method ATTRIBUTE_UNUSED,
+                          MethodReference method_ref) OVERRIDE {
+      last_reserve_offset_ = offset;
+      last_reserve_method_ = method_ref;
+      offset += next_reserve_adjustment_;
+      next_reserve_adjustment_ = 0u;
+      return offset;
+    }
+
+    uint32_t ReserveSpaceEnd(uint32_t offset) OVERRIDE {
+      last_reserve_offset_ = offset;
+      last_reserve_method_ = kNullMethodRef;
+      offset += next_reserve_adjustment_;
+      next_reserve_adjustment_ = 0u;
+      return offset;
+    }
+
+    uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE {
+      last_write_offset_ = offset;
+      if (next_write_alignment_ != 0u) {
+        offset += next_write_alignment_;
+        bool success = WriteCodeAlignment(out, next_write_alignment_);
+        CHECK(success);
+        next_write_alignment_ = 0u;
+      }
+      if (next_write_call_thunk_ != 0u) {
+        offset += next_write_call_thunk_;
+        std::vector<uint8_t> thunk(next_write_call_thunk_, 'c');
+        bool success = WriteRelCallThunk(out, ArrayRef<const uint8_t>(thunk));
+        CHECK(success);
+        next_write_call_thunk_ = 0u;
+      }
+      if (next_write_misc_thunk_ != 0u) {
+        offset += next_write_misc_thunk_;
+        std::vector<uint8_t> thunk(next_write_misc_thunk_, 'm');
+        bool success = WriteMiscThunk(out, ArrayRef<const uint8_t>(thunk));
+        CHECK(success);
+        next_write_misc_thunk_ = 0u;
+      }
+      return offset;
+    }
+
+    void PatchCall(std::vector<uint8_t>* code ATTRIBUTE_UNUSED,
+                   uint32_t literal_offset,
+                   uint32_t patch_offset,
+                   uint32_t target_offset) OVERRIDE {
+      last_literal_offset_ = literal_offset;
+      last_patch_offset_ = patch_offset;
+      last_target_offset_ = target_offset;
+    }
+
+    void PatchDexCacheReference(std::vector<uint8_t>* code ATTRIBUTE_UNUSED,
+                                const LinkerPatch& patch,
+                                uint32_t patch_offset,
+                                uint32_t target_offset) OVERRIDE {
+      last_literal_offset_ = patch.LiteralOffset();
+      last_patch_offset_ = patch_offset;
+      last_target_offset_ = target_offset;
+    }
+
+    uint32_t last_reserve_offset_ = 0u;
+    MethodReference last_reserve_method_ = kNullMethodRef;
+    uint32_t next_reserve_adjustment_ = 0u;
+
+    uint32_t last_write_offset_ = 0u;
+    uint32_t next_write_alignment_ = 0u;
+    uint32_t next_write_call_thunk_ = 0u;
+    uint32_t next_write_misc_thunk_ = 0u;
+
+    uint32_t last_literal_offset_ = 0u;
+    uint32_t last_patch_offset_ = 0u;
+    uint32_t last_target_offset_ = 0u;
+  };
+
+  MultiOatRelativePatcherTest()
+      : instruction_set_features_(InstructionSetFeatures::FromCppDefines()),
+        patcher_(kRuntimeISA, instruction_set_features_.get()) {
+    std::unique_ptr<MockPatcher> mock(new MockPatcher());
+    mock_ = mock.get();
+    patcher_.relative_patcher_ = std::move(mock);
+  }
+
+  std::unique_ptr<const InstructionSetFeatures> instruction_set_features_;
+  MultiOatRelativePatcher patcher_;
+  MockPatcher* mock_;
+};
+
+TEST_F(MultiOatRelativePatcherTest, Offsets) {
+  const DexFile* dex_file = reinterpret_cast<const DexFile*>(1);
+  MethodReference ref1(dex_file, 1u);
+  MethodReference ref2(dex_file, 2u);
+  EXPECT_EQ(0u, patcher_.GetOffset(ref1));
+  EXPECT_EQ(0u, patcher_.GetOffset(ref2));
+
+  uint32_t adjustment1 = 0x1000;
+  patcher_.StartOatFile(adjustment1);
+  EXPECT_EQ(0u, patcher_.GetOffset(ref1));
+  EXPECT_EQ(0u, patcher_.GetOffset(ref2));
+
+  uint32_t off1 = 0x1234;
+  patcher_.SetOffset(ref1, off1);
+  EXPECT_EQ(off1, patcher_.GetOffset(ref1));
+  EXPECT_EQ(0u, patcher_.GetOffset(ref2));
+
+  uint32_t adjustment2 = 0x30000;
+  patcher_.StartOatFile(adjustment2);
+  EXPECT_EQ(off1 + adjustment1 - adjustment2, patcher_.GetOffset(ref1));
+  EXPECT_EQ(0u, patcher_.GetOffset(ref2));
+
+  uint32_t off2 = 0x4321;
+  patcher_.SetOffset(ref2, off2);
+  EXPECT_EQ(off1 + adjustment1 - adjustment2, patcher_.GetOffset(ref1));
+  EXPECT_EQ(off2, patcher_.GetOffset(ref2));
+
+  uint32_t adjustment3 = 0x78000;
+  patcher_.StartOatFile(adjustment3);
+  EXPECT_EQ(off1 + adjustment1 - adjustment3, patcher_.GetOffset(ref1));
+  EXPECT_EQ(off2 + adjustment2 - adjustment3, patcher_.GetOffset(ref2));
+}
+
+TEST_F(MultiOatRelativePatcherTest, OffsetsInReserve) {
+  const DexFile* dex_file = reinterpret_cast<const DexFile*>(1);
+  MethodReference ref1(dex_file, 1u);
+  MethodReference ref2(dex_file, 2u);
+  MethodReference ref3(dex_file, 3u);
+  const CompiledMethod* method = reinterpret_cast<const CompiledMethod*>(-1);
+
+  uint32_t adjustment1 = 0x1000;
+  patcher_.StartOatFile(adjustment1);
+
+  uint32_t method1_offset = 0x100;
+  uint32_t method1_offset_check = patcher_.ReserveSpace(method1_offset, method, ref1);
+  ASSERT_EQ(adjustment1 + method1_offset, mock_->last_reserve_offset_);
+  ASSERT_TRUE(EqualRef(ref1, mock_->last_reserve_method_));
+  ASSERT_EQ(method1_offset, method1_offset_check);
+
+  uint32_t method2_offset = 0x1230;
+  uint32_t method2_reserve_adjustment = 0x10;
+  mock_->next_reserve_adjustment_ = method2_reserve_adjustment;
+  uint32_t method2_offset_adjusted = patcher_.ReserveSpace(method2_offset, method, ref2);
+  ASSERT_EQ(adjustment1 + method2_offset, mock_->last_reserve_offset_);
+  ASSERT_TRUE(EqualRef(ref2, mock_->last_reserve_method_));
+  ASSERT_EQ(method2_offset + method2_reserve_adjustment, method2_offset_adjusted);
+
+  uint32_t end1_offset = 0x4320;
+  uint32_t end1_offset_check = patcher_.ReserveSpaceEnd(end1_offset);
+  ASSERT_EQ(adjustment1 + end1_offset, mock_->last_reserve_offset_);
+  ASSERT_TRUE(EqualRef(kNullMethodRef, mock_->last_reserve_method_));
+  ASSERT_EQ(end1_offset, end1_offset_check);
+
+  uint32_t adjustment2 = 0xd000;
+  patcher_.StartOatFile(adjustment2);
+
+  uint32_t method3_offset = 0xf00;
+  uint32_t method3_offset_check = patcher_.ReserveSpace(method3_offset, method, ref3);
+  ASSERT_EQ(adjustment2 + method3_offset, mock_->last_reserve_offset_);
+  ASSERT_TRUE(EqualRef(ref3, mock_->last_reserve_method_));
+  ASSERT_EQ(method3_offset, method3_offset_check);
+
+  uint32_t end2_offset = 0x2400;
+  uint32_t end2_reserve_adjustment = 0x20;
+  mock_->next_reserve_adjustment_ = end2_reserve_adjustment;
+  uint32_t end2_offset_adjusted = patcher_.ReserveSpaceEnd(end2_offset);
+  ASSERT_EQ(adjustment2 + end2_offset, mock_->last_reserve_offset_);
+  ASSERT_TRUE(EqualRef(kNullMethodRef, mock_->last_reserve_method_));
+  ASSERT_EQ(end2_offset + end2_reserve_adjustment, end2_offset_adjusted);
+}
+
+TEST_F(MultiOatRelativePatcherTest, Write) {
+  std::vector<uint8_t> output;
+  VectorOutputStream vos("output", &output);
+
+  uint32_t adjustment1 = 0x1000;
+  patcher_.StartOatFile(adjustment1);
+
+  uint32_t method1_offset = 0x100;
+  uint32_t method1_offset_check = patcher_.WriteThunks(&vos, method1_offset);
+  ASSERT_EQ(adjustment1 + method1_offset, mock_->last_write_offset_);
+  ASSERT_EQ(method1_offset, method1_offset_check);
+  vos.WriteFully("1", 1);  // Mark method1.
+
+  uint32_t method2_offset = 0x1230;
+  uint32_t method2_alignment_size = 1;
+  uint32_t method2_call_thunk_size = 2;
+  mock_->next_write_alignment_ = method2_alignment_size;
+  mock_->next_write_call_thunk_ = method2_call_thunk_size;
+  uint32_t method2_offset_adjusted = patcher_.WriteThunks(&vos, method2_offset);
+  ASSERT_EQ(adjustment1 + method2_offset, mock_->last_write_offset_);
+  ASSERT_EQ(method2_offset + method2_alignment_size + method2_call_thunk_size,
+            method2_offset_adjusted);
+  vos.WriteFully("2", 1);  // Mark method2.
+
+  EXPECT_EQ(method2_alignment_size, patcher_.CodeAlignmentSize());
+  EXPECT_EQ(method2_call_thunk_size, patcher_.RelativeCallThunksSize());
+
+  uint32_t adjustment2 = 0xd000;
+  patcher_.StartOatFile(adjustment2);
+
+  uint32_t method3_offset = 0xf00;
+  uint32_t method3_alignment_size = 2;
+  uint32_t method3_misc_thunk_size = 1;
+  mock_->next_write_alignment_ = method3_alignment_size;
+  mock_->next_write_misc_thunk_ = method3_misc_thunk_size;
+  uint32_t method3_offset_adjusted = patcher_.WriteThunks(&vos, method3_offset);
+  ASSERT_EQ(adjustment2 + method3_offset, mock_->last_write_offset_);
+  ASSERT_EQ(method3_offset + method3_alignment_size + method3_misc_thunk_size,
+            method3_offset_adjusted);
+  vos.WriteFully("3", 1);  // Mark method3.
+
+  EXPECT_EQ(method3_alignment_size, patcher_.CodeAlignmentSize());
+  EXPECT_EQ(method3_misc_thunk_size, patcher_.MiscThunksSize());
+
+  uint8_t expected_output[] = {
+      '1',
+      0, 'c', 'c', '2',
+      0, 0, 'm', '3',
+  };
+  ASSERT_EQ(arraysize(expected_output), output.size());
+  for (size_t i = 0; i != arraysize(expected_output); ++i) {
+    ASSERT_EQ(expected_output[i], output[i]) << i;
+  }
+}
+
+TEST_F(MultiOatRelativePatcherTest, Patch) {
+  std::vector<uint8_t> code(16);
+
+  uint32_t adjustment1 = 0x1000;
+  patcher_.StartOatFile(adjustment1);
+
+  uint32_t method1_literal_offset = 4u;
+  uint32_t method1_patch_offset = 0x1234u;
+  uint32_t method1_target_offset = 0x8888u;
+  patcher_.PatchCall(&code, method1_literal_offset, method1_patch_offset, method1_target_offset);
+  DCHECK_EQ(method1_literal_offset, mock_->last_literal_offset_);
+  DCHECK_EQ(method1_patch_offset + adjustment1, mock_->last_patch_offset_);
+  DCHECK_EQ(method1_target_offset + adjustment1, mock_->last_target_offset_);
+
+  uint32_t method2_literal_offset = 12u;
+  uint32_t method2_patch_offset = 0x7654u;
+  uint32_t method2_target_offset = 0xccccu;
+  LinkerPatch method2_patch =
+      LinkerPatch::DexCacheArrayPatch(method2_literal_offset, nullptr, 0u, 1234u);
+  patcher_.PatchDexCacheReference(
+      &code, method2_patch, method2_patch_offset, method2_target_offset);
+  DCHECK_EQ(method2_literal_offset, mock_->last_literal_offset_);
+  DCHECK_EQ(method2_patch_offset + adjustment1, mock_->last_patch_offset_);
+  DCHECK_EQ(method2_target_offset + adjustment1, mock_->last_target_offset_);
+
+  uint32_t adjustment2 = 0xd000;
+  patcher_.StartOatFile(adjustment2);
+
+  uint32_t method3_literal_offset = 8u;
+  uint32_t method3_patch_offset = 0x108u;
+  uint32_t method3_target_offset = 0x200u;
+  patcher_.PatchCall(&code, method3_literal_offset, method3_patch_offset, method3_target_offset);
+  DCHECK_EQ(method3_literal_offset, mock_->last_literal_offset_);
+  DCHECK_EQ(method3_patch_offset + adjustment2, mock_->last_patch_offset_);
+  DCHECK_EQ(method3_target_offset + adjustment2, mock_->last_target_offset_);
+}
+
+}  // namespace linker
+}  // namespace art
diff --git a/compiler/linker/relative_patcher.cc b/compiler/linker/relative_patcher.cc
index 82702dc..6727c17 100644
--- a/compiler/linker/relative_patcher.cc
+++ b/compiler/linker/relative_patcher.cc
@@ -34,7 +34,8 @@
 namespace linker {
 
 std::unique_ptr<RelativePatcher> RelativePatcher::Create(
-    InstructionSet instruction_set, const InstructionSetFeatures* features,
+    InstructionSet instruction_set,
+    const InstructionSetFeatures* features,
     RelativePatcherTargetProvider* provider) {
   class RelativePatcherNone FINAL : public RelativePatcher {
    public:
diff --git a/compiler/linker/relative_patcher.h b/compiler/linker/relative_patcher.h
index 8a9f3f8..ba37451 100644
--- a/compiler/linker/relative_patcher.h
+++ b/compiler/linker/relative_patcher.h
@@ -83,23 +83,31 @@
   }
 
   // Reserve space for thunks if needed before a method, return adjusted offset.
-  virtual uint32_t ReserveSpace(uint32_t offset, const CompiledMethod* compiled_method,
+  virtual uint32_t ReserveSpace(uint32_t offset,
+                                const CompiledMethod* compiled_method,
                                 MethodReference method_ref) = 0;
 
   // Reserve space for thunks if needed after the last method, return adjusted offset.
+  // The caller may use this method to preemptively force thunk space reservation and
+  // then resume reservation for more methods. This is useful when there is a gap in
+  // the .text segment, for example when going to the next oat file for multi-image.
   virtual uint32_t ReserveSpaceEnd(uint32_t offset) = 0;
 
-  // Write relative call thunks if needed, return adjusted offset.
+  // Write relative call thunks if needed, return adjusted offset. Returns 0 on write failure.
   virtual uint32_t WriteThunks(OutputStream* out, uint32_t offset) = 0;
 
   // Patch method code. The input displacement is relative to the patched location,
   // the patcher may need to adjust it if the correct base is different.
-  virtual void PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                         uint32_t patch_offset, uint32_t target_offset) = 0;
+  virtual void PatchCall(std::vector<uint8_t>* code,
+                         uint32_t literal_offset,
+                         uint32_t patch_offset,
+                         uint32_t target_offset) = 0;
 
   // Patch a reference to a dex cache location.
-  virtual void PatchDexCacheReference(std::vector<uint8_t>* code, const LinkerPatch& patch,
-                                      uint32_t patch_offset, uint32_t target_offset) = 0;
+  virtual void PatchDexCacheReference(std::vector<uint8_t>* code,
+                                      const LinkerPatch& patch,
+                                      uint32_t patch_offset,
+                                      uint32_t target_offset) = 0;
 
  protected:
   RelativePatcher()
diff --git a/compiler/linker/relative_patcher_test.h b/compiler/linker/relative_patcher_test.h
index bf8e786..704135a 100644
--- a/compiler/linker/relative_patcher_test.h
+++ b/compiler/linker/relative_patcher_test.h
@@ -44,10 +44,22 @@
       : compiler_options_(),
         verification_results_(&compiler_options_),
         inliner_map_(),
-        driver_(&compiler_options_, &verification_results_, &inliner_map_,
-                Compiler::kQuick, instruction_set, nullptr,
-                false, nullptr, nullptr, nullptr, 1u,
-                false, false, nullptr, -1, nullptr, nullptr),
+        driver_(&compiler_options_,
+                &verification_results_,
+                &inliner_map_,
+                Compiler::kQuick,
+                instruction_set,
+                /* instruction_set_features*/ nullptr,
+                /* boot_image */ false,
+                /* image_classes */ nullptr,
+                /* compiled_classes */ nullptr,
+                /* compiled_methods */ nullptr,
+                /* thread_count */ 1u,
+                /* dump_stats */ false,
+                /* dump_passes */ false,
+                /* timer */ nullptr,
+                /* swap_fd */ -1,
+                /* profile_compilation_info */ nullptr),
         error_msg_(),
         instruction_set_(instruction_set),
         features_(InstructionSetFeatures::FromVariant(instruction_set, variant, &error_msg_)),
@@ -138,8 +150,10 @@
                                 offset + patch.LiteralOffset(), target_offset);
           } else if (patch.Type() == kLinkerPatchDexCacheArray) {
             uint32_t target_offset = dex_cache_arrays_begin_ + patch.TargetDexCacheElementOffset();
-            patcher_->PatchDexCacheReference(&patched_code_, patch,
-                                             offset + patch.LiteralOffset(), target_offset);
+            patcher_->PatchDexCacheReference(&patched_code_,
+                                             patch,
+                                             offset + patch.LiteralOffset(),
+                                             target_offset);
           } else {
             LOG(FATAL) << "Bad patch type.";
           }
diff --git a/compiler/linker/x86/relative_patcher_x86.h b/compiler/linker/x86/relative_patcher_x86.h
index 0c881f0..ddc244c 100644
--- a/compiler/linker/x86/relative_patcher_x86.h
+++ b/compiler/linker/x86/relative_patcher_x86.h
@@ -26,8 +26,10 @@
  public:
   X86RelativePatcher() { }
 
-  void PatchDexCacheReference(std::vector<uint8_t>* code, const LinkerPatch& patch,
-                              uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
+  void PatchDexCacheReference(std::vector<uint8_t>* code,
+                              const LinkerPatch& patch,
+                              uint32_t patch_offset,
+                              uint32_t target_offset) OVERRIDE;
 };
 
 }  // namespace linker
diff --git a/compiler/linker/x86/relative_patcher_x86_base.cc b/compiler/linker/x86/relative_patcher_x86_base.cc
index bc285a7..bf3a648 100644
--- a/compiler/linker/x86/relative_patcher_x86_base.cc
+++ b/compiler/linker/x86/relative_patcher_x86_base.cc
@@ -34,8 +34,10 @@
   return offset;  // No thunks added; no limit on relative call distance.
 }
 
-void X86BaseRelativePatcher::PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                                       uint32_t patch_offset, uint32_t target_offset) {
+void X86BaseRelativePatcher::PatchCall(std::vector<uint8_t>* code,
+                                       uint32_t literal_offset,
+                                       uint32_t patch_offset,
+                                       uint32_t target_offset) {
   DCHECK_LE(literal_offset + 4u, code->size());
   // Unsigned arithmetic with its well-defined overflow behavior is just fine here.
   uint32_t displacement = target_offset - patch_offset;
diff --git a/compiler/linker/x86/relative_patcher_x86_base.h b/compiler/linker/x86/relative_patcher_x86_base.h
index 9200709..ca83a72 100644
--- a/compiler/linker/x86/relative_patcher_x86_base.h
+++ b/compiler/linker/x86/relative_patcher_x86_base.h
@@ -29,8 +29,10 @@
                         MethodReference method_ref) OVERRIDE;
   uint32_t ReserveSpaceEnd(uint32_t offset) OVERRIDE;
   uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE;
-  void PatchCall(std::vector<uint8_t>* code, uint32_t literal_offset,
-                 uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
+  void PatchCall(std::vector<uint8_t>* code,
+                 uint32_t literal_offset,
+                 uint32_t patch_offset,
+                 uint32_t target_offset) OVERRIDE;
 
  protected:
   X86BaseRelativePatcher() { }
diff --git a/compiler/linker/x86_64/relative_patcher_x86_64.cc b/compiler/linker/x86_64/relative_patcher_x86_64.cc
index 598f3ac..e571f50 100644
--- a/compiler/linker/x86_64/relative_patcher_x86_64.cc
+++ b/compiler/linker/x86_64/relative_patcher_x86_64.cc
@@ -23,7 +23,8 @@
 
 void X86_64RelativePatcher::PatchDexCacheReference(std::vector<uint8_t>* code,
                                                    const LinkerPatch& patch,
-                                                   uint32_t patch_offset, uint32_t target_offset) {
+                                                   uint32_t patch_offset,
+                                                   uint32_t target_offset) {
   DCHECK_LE(patch.LiteralOffset() + 4u, code->size());
   // Unsigned arithmetic with its well-defined overflow behavior is just fine here.
   uint32_t displacement = target_offset - patch_offset;
diff --git a/compiler/linker/x86_64/relative_patcher_x86_64.h b/compiler/linker/x86_64/relative_patcher_x86_64.h
index af687b4..feecb3a 100644
--- a/compiler/linker/x86_64/relative_patcher_x86_64.h
+++ b/compiler/linker/x86_64/relative_patcher_x86_64.h
@@ -26,8 +26,10 @@
  public:
   X86_64RelativePatcher() { }
 
-  void PatchDexCacheReference(std::vector<uint8_t>* code, const LinkerPatch& patch,
-                              uint32_t patch_offset, uint32_t target_offset) OVERRIDE;
+  void PatchDexCacheReference(std::vector<uint8_t>* code,
+                              const LinkerPatch& patch,
+                              uint32_t patch_offset,
+                              uint32_t target_offset) OVERRIDE;
 };
 
 }  // namespace linker
diff --git a/compiler/oat_test.cc b/compiler/oat_test.cc
index d3b404a..21ddb80 100644
--- a/compiler/oat_test.cc
+++ b/compiler/oat_test.cc
@@ -31,6 +31,7 @@
 #include "elf_writer.h"
 #include "elf_writer_quick.h"
 #include "entrypoints/quick/quick_entrypoints.h"
+#include "linker/multi_oat_relative_patcher.h"
 #include "linker/vector_output_stream.h"
 #include "mirror/class-inl.h"
 #include "mirror/object-inl.h"
@@ -111,17 +112,16 @@
                                               compiler_kind,
                                               insn_set,
                                               insn_features_.get(),
-                                              false,
-                                              nullptr,
-                                              nullptr,
-                                              nullptr,
-                                              2,
-                                              true,
-                                              true,
+                                              /* boot_image */ false,
+                                              /* image_classes */ nullptr,
+                                              /* compiled_classes */ nullptr,
+                                              /* compiled_methods */ nullptr,
+                                              /* thread_count */ 2,
+                                              /* dump_stats */ true,
+                                              /* dump_passes */ true,
                                               timer_.get(),
-                                              -1,
-                                              nullptr,
-                                              nullptr));
+                                              /* swap_fd */ -1,
+                                              /* profile_compilation_info */ nullptr));
   }
 
   bool WriteElf(File* file,
@@ -200,7 +200,13 @@
       ScopedObjectAccess soa(Thread::Current());
       class_linker->RegisterDexFile(*dex_file, runtime->GetLinearAlloc());
     }
-    oat_writer.PrepareLayout(compiler_driver_.get(), nullptr, dex_files);
+    linker::MultiOatRelativePatcher patcher(compiler_driver_->GetInstructionSet(),
+                                            instruction_set_features_.get());
+    oat_writer.PrepareLayout(compiler_driver_.get(), nullptr, dex_files, &patcher);
+    size_t rodata_size = oat_writer.GetOatHeader().GetExecutableOffset();
+    size_t text_size = oat_writer.GetSize() - rodata_size;
+    elf_writer->SetLoadedSectionSizes(rodata_size, text_size, oat_writer.GetBssSize());
+
     if (!oat_writer.WriteRodata(rodata)) {
       return false;
     }
@@ -216,7 +222,6 @@
       return false;
     }
 
-    elf_writer->SetBssSize(oat_writer.GetBssSize());
     elf_writer->WriteDynamicSection();
     elf_writer->WriteDebugInfo(oat_writer.GetMethodDebugInfo());
     elf_writer->WritePatchLocations(oat_writer.GetAbsolutePatchLocations());
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index 47dcfd5..c60b02a 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -38,8 +38,8 @@
 #include "gc/space/space.h"
 #include "handle_scope-inl.h"
 #include "image_writer.h"
+#include "linker/multi_oat_relative_patcher.h"
 #include "linker/output_stream.h"
-#include "linker/relative_patcher.h"
 #include "mirror/array.h"
 #include "mirror/class_loader.h"
 #include "mirror/dex_cache-inl.h"
@@ -292,7 +292,8 @@
     size_oat_class_status_(0),
     size_oat_class_method_bitmaps_(0),
     size_oat_class_method_offsets_(0),
-    method_offset_map_() {
+    relative_patcher_(nullptr),
+    absolute_patch_locations_() {
 }
 
 bool OatWriter::AddDexFileSource(const char* filename,
@@ -438,21 +439,21 @@
 
 void OatWriter::PrepareLayout(const CompilerDriver* compiler,
                               ImageWriter* image_writer,
-                              const std::vector<const DexFile*>& dex_files) {
+                              const std::vector<const DexFile*>& dex_files,
+                              linker::MultiOatRelativePatcher* relative_patcher) {
   CHECK(write_state_ == WriteState::kPrepareLayout);
 
-  dex_files_ = &dex_files;
-
   compiler_driver_ = compiler;
   image_writer_ = image_writer;
+  dex_files_ = &dex_files;
+  relative_patcher_ = relative_patcher;
+  SetMultiOatRelativePatcherAdjustment();
+
   if (compiling_boot_image_) {
     CHECK(image_writer_ != nullptr);
   }
   InstructionSet instruction_set = compiler_driver_->GetInstructionSet();
   CHECK_EQ(instruction_set, oat_header_->GetInstructionSet());
-  const InstructionSetFeatures* features = compiler_driver_->GetInstructionSetFeatures();
-  relative_patcher_ = linker::RelativePatcher::Create(instruction_set, features,
-                                                      &method_offset_map_);
 
   uint32_t offset = size_;
   {
@@ -727,13 +728,11 @@
       // Deduplicate code arrays if we are not producing debuggable code.
       bool deduped = false;
       MethodReference method_ref(dex_file_, it.GetMemberIndex());
-      auto method_lb = writer_->method_offset_map_.map.lower_bound(method_ref);
       if (debuggable_) {
-        if (method_lb != writer_->method_offset_map_.map.end() &&
-            !writer_->method_offset_map_.map.key_comp()(method_ref, method_lb->first)) {
+        quick_code_offset = writer_->relative_patcher_->GetOffset(method_ref);
+        if (quick_code_offset != 0u) {
           // Duplicate methods, we want the same code for both of them so that the oat writer puts
           // the same code in both ArtMethods so that we do not get different oat code at runtime.
-          quick_code_offset = method_lb->second;
           deduped = true;
         } else {
           quick_code_offset = NewQuickCodeOffset(compiled_method, it, thumb_offset);
@@ -750,14 +749,14 @@
       }
 
       if (code_size != 0) {
-        if (method_lb != writer_->method_offset_map_.map.end() &&
-            !writer_->method_offset_map_.map.key_comp()(method_ref, method_lb->first)) {
+        if (writer_->relative_patcher_->GetOffset(method_ref) != 0u) {
           // TODO: Should this be a hard failure?
           LOG(WARNING) << "Multiple definitions of "
               << PrettyMethod(method_ref.dex_method_index, *method_ref.dex_file)
-              << " offsets " << method_lb->second << " " << quick_code_offset;
+              << " offsets " << writer_->relative_patcher_->GetOffset(method_ref)
+              << " " << quick_code_offset;
         } else {
-          writer_->method_offset_map_.map.PutBefore(method_lb, method_ref, quick_code_offset);
+          writer_->relative_patcher_->SetOffset(method_ref, quick_code_offset);
         }
       }
 
@@ -1106,27 +1105,29 @@
           patched_code_.assign(quick_code.begin(), quick_code.end());
           quick_code = ArrayRef<const uint8_t>(patched_code_);
           for (const LinkerPatch& patch : compiled_method->GetPatches()) {
+            uint32_t literal_offset = patch.LiteralOffset();
             if (patch.Type() == kLinkerPatchCallRelative) {
               // NOTE: Relative calls across oat files are not supported.
               uint32_t target_offset = GetTargetOffset(patch);
-              uint32_t literal_offset = patch.LiteralOffset();
-              writer_->relative_patcher_->PatchCall(&patched_code_, literal_offset,
-                                                     offset_ + literal_offset, target_offset);
+              writer_->relative_patcher_->PatchCall(&patched_code_,
+                                                    literal_offset,
+                                                    offset_ + literal_offset,
+                                                    target_offset);
             } else if (patch.Type() == kLinkerPatchDexCacheArray) {
               uint32_t target_offset = GetDexCacheOffset(patch);
-              uint32_t literal_offset = patch.LiteralOffset();
-              writer_->relative_patcher_->PatchDexCacheReference(&patched_code_, patch,
+              writer_->relative_patcher_->PatchDexCacheReference(&patched_code_,
+                                                                 patch,
                                                                  offset_ + literal_offset,
                                                                  target_offset);
             } else if (patch.Type() == kLinkerPatchCall) {
               uint32_t target_offset = GetTargetOffset(patch);
-              PatchCodeAddress(&patched_code_, patch.LiteralOffset(), target_offset);
+              PatchCodeAddress(&patched_code_, literal_offset, target_offset);
             } else if (patch.Type() == kLinkerPatchMethod) {
               ArtMethod* method = GetTargetMethod(patch);
-              PatchMethodAddress(&patched_code_, patch.LiteralOffset(), method);
+              PatchMethodAddress(&patched_code_, literal_offset, method);
             } else if (patch.Type() == kLinkerPatchType) {
               mirror::Class* type = GetTargetType(patch);
-              PatchObjectAddress(&patched_code_, patch.LiteralOffset(), type);
+              PatchObjectAddress(&patched_code_, literal_offset, type);
             }
           }
         }
@@ -1172,16 +1173,16 @@
   }
 
   uint32_t GetTargetOffset(const LinkerPatch& patch) SHARED_REQUIRES(Locks::mutator_lock_) {
-    auto target_it = writer_->method_offset_map_.map.find(patch.TargetMethod());
-    uint32_t target_offset =
-        (target_it != writer_->method_offset_map_.map.end()) ? target_it->second : 0u;
-    // If there's no compiled code, point to the correct trampoline.
+    uint32_t target_offset = writer_->relative_patcher_->GetOffset(patch.TargetMethod());
+    // If there's no new compiled code, either we're compiling an app and the target method
+    // is in the boot image, or we need to point to the correct trampoline.
     if (UNLIKELY(target_offset == 0)) {
       ArtMethod* target = GetTargetMethod(patch);
       DCHECK(target != nullptr);
       size_t size = GetInstructionSetPointerSize(writer_->compiler_driver_->GetInstructionSet());
       const void* oat_code_offset = target->GetEntryPointFromQuickCompiledCodePtrSize(size);
       if (oat_code_offset != 0) {
+        DCHECK(!writer_->HasBootImage());
         DCHECK(!Runtime::Current()->GetClassLinker()->IsQuickResolutionStub(oat_code_offset));
         DCHECK(!Runtime::Current()->GetClassLinker()->IsQuickToInterpreterBridge(oat_code_offset));
         DCHECK(!Runtime::Current()->GetClassLinker()->IsQuickGenericJniStub(oat_code_offset));
@@ -1206,11 +1207,10 @@
 
   uint32_t GetDexCacheOffset(const LinkerPatch& patch) SHARED_REQUIRES(Locks::mutator_lock_) {
     if (writer_->HasBootImage()) {
-      auto* element = writer_->image_writer_->GetDexCacheArrayElementImageAddress<const uint8_t*>(
-              patch.TargetDexCacheDexFile(), patch.TargetDexCacheElementOffset());
-      const char* oat_filename = writer_->image_writer_->GetOatFilenameForDexCache(dex_cache_);
-      const uint8_t* oat_data =
-          writer_->image_writer_->GetOatFileBegin(oat_filename) + file_offset_;
+      uintptr_t element = writer_->image_writer_->GetDexCacheArrayElementImageAddress<uintptr_t>(
+          patch.TargetDexCacheDexFile(), patch.TargetDexCacheElementOffset());
+      size_t oat_index = writer_->image_writer_->GetOatIndexForDexCache(dex_cache_);
+      uintptr_t oat_data = writer_->image_writer_->GetOatDataBegin(oat_index);
       return element - oat_data;
     } else {
       size_t start = writer_->dex_cache_arrays_offsets_.Get(patch.TargetDexCacheDexFile());
@@ -1270,9 +1270,13 @@
       SHARED_REQUIRES(Locks::mutator_lock_) {
     uint32_t address = target_offset;
     if (writer_->HasBootImage()) {
-      const char* oat_filename = writer_->image_writer_->GetOatFilenameForDexCache(dex_cache_);
-      address = PointerToLowMemUInt32(writer_->image_writer_->GetOatFileBegin(oat_filename) +
-                                      writer_->oat_data_offset_ + target_offset);
+      size_t oat_index = writer_->image_writer_->GetOatIndexForDexCache(dex_cache_);
+      // TODO: Clean up offset types.
+      // The target_offset must be treated as signed for cross-oat patching.
+      const void* target = reinterpret_cast<const void*>(
+          writer_->image_writer_->GetOatDataBegin(oat_index) +
+          static_cast<int32_t>(target_offset));
+      address = PointerToLowMemUInt32(target);
     }
     DCHECK_LE(offset + 4, code->size());
     uint8_t* data = &(*code)[offset];
@@ -1540,6 +1544,8 @@
 bool OatWriter::WriteCode(OutputStream* out) {
   CHECK(write_state_ == WriteState::kWriteText);
 
+  SetMultiOatRelativePatcherAdjustment();
+
   const size_t file_offset = oat_data_offset_;
   size_t relative_offset = oat_header_->GetExecutableOffset();
   DCHECK_OFFSET();
@@ -1781,7 +1787,7 @@
   return relative_offset;
 }
 
-bool OatWriter::GetOatDataOffset(OutputStream* out) {
+bool OatWriter::RecordOatDataOffset(OutputStream* out) {
   // Get the elf file offset of the oat file.
   const off_t raw_file_offset = out->Seek(0, kSeekCurrent);
   if (raw_file_offset == static_cast<off_t>(-1)) {
@@ -1833,7 +1839,7 @@
   TimingLogger::ScopedTiming split("WriteDexFiles", timings_);
 
   // Get the elf file offset of the oat file.
-  if (!GetOatDataOffset(rodata)) {
+  if (!RecordOatDataOffset(rodata)) {
     return false;
   }
 
@@ -2261,12 +2267,15 @@
   return out->WriteFully(data, size);
 }
 
-std::pair<bool, uint32_t> OatWriter::MethodOffsetMap::FindMethodOffset(MethodReference ref) {
-  auto it = map.find(ref);
-  if (it == map.end()) {
-    return std::pair<bool, uint32_t>(false, 0u);
-  } else {
-    return std::pair<bool, uint32_t>(true, it->second);
+void OatWriter::SetMultiOatRelativePatcherAdjustment() {
+  DCHECK(dex_files_ != nullptr);
+  DCHECK(relative_patcher_ != nullptr);
+  DCHECK_NE(oat_data_offset_, 0u);
+  if (image_writer_ != nullptr && !dex_files_->empty()) {
+    // The oat data begin may not be initialized yet but the oat file offset is ready.
+    size_t oat_index = image_writer_->GetOatIndexForDexFile(dex_files_->front());
+    size_t elf_file_offset = image_writer_->GetOatFileOffset(oat_index);
+    relative_patcher_->StartOatFile(elf_file_offset + oat_data_offset_);
   }
 }
 
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index 5a55fc6..74aab4e 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -47,6 +47,10 @@
 struct MethodDebugInfo;
 }  // namespace debug
 
+namespace linker {
+class MultiOatRelativePatcher;
+}  // namespace linker
+
 // OatHeader         variable length with count of D OatDexFiles
 //
 // OatDexFile[0]     one variable sized OatDexFile with offsets to Dex and OatClasses
@@ -153,7 +157,8 @@
   // Prepare layout of remaining data.
   void PrepareLayout(const CompilerDriver* compiler,
                      ImageWriter* image_writer,
-                     const std::vector<const DexFile*>& dex_files);
+                     const std::vector<const DexFile*>& dex_files,
+                     linker::MultiOatRelativePatcher* relative_patcher);
   // Write the rest of .rodata section (ClassOffsets[], OatClass[], maps).
   bool WriteRodata(OutputStream* out);
   // Write the code to the .text section.
@@ -187,6 +192,10 @@
     return bss_size_;
   }
 
+  size_t GetOatDataOffset() const {
+    return oat_data_offset_;
+  }
+
   ArrayRef<const uintptr_t> GetAbsolutePatchLocations() const {
     return ArrayRef<const uintptr_t>(absolute_patch_locations_);
   }
@@ -249,7 +258,7 @@
   size_t WriteCode(OutputStream* out, const size_t file_offset, size_t relative_offset);
   size_t WriteCodeDexFiles(OutputStream* out, const size_t file_offset, size_t relative_offset);
 
-  bool GetOatDataOffset(OutputStream* out);
+  bool RecordOatDataOffset(OutputStream* out);
   bool ReadDexFileHeader(File* file, OatDexFile* oat_dex_file);
   bool ValidateDexFileHeader(const uint8_t* raw_header, const char* location);
   bool WriteDexFiles(OutputStream* rodata, File* file);
@@ -268,6 +277,7 @@
                              const std::vector<std::unique_ptr<const DexFile>>& opened_dex_files);
   bool WriteCodeAlignment(OutputStream* out, uint32_t aligned_code_delta);
   bool WriteData(OutputStream* out, const void* data, size_t size);
+  void SetMultiOatRelativePatcherAdjustment();
 
   enum class WriteState {
     kAddingDexFileSources,
@@ -358,20 +368,12 @@
   uint32_t size_oat_class_method_bitmaps_;
   uint32_t size_oat_class_method_offsets_;
 
-  std::unique_ptr<linker::RelativePatcher> relative_patcher_;
+  // The helper for processing relative patches is external so that we can patch across oat files.
+  linker::MultiOatRelativePatcher* relative_patcher_;
 
   // The locations of absolute patches relative to the start of the executable section.
   dchecked_vector<uintptr_t> absolute_patch_locations_;
 
-  // Map method reference to assigned offset.
-  // Wrap the map in a class implementing linker::RelativePatcherTargetProvider.
-  class MethodOffsetMap FINAL : public linker::RelativePatcherTargetProvider {
-   public:
-    std::pair<bool, uint32_t> FindMethodOffset(MethodReference ref) OVERRIDE;
-    SafeMap<MethodReference, uint32_t, MethodReferenceComparator> map;
-  };
-  MethodOffsetMap method_offset_map_;
-
   DISALLOW_COPY_AND_ASSIGN(OatWriter);
 };
 
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 541fb5a..9427eaf 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -65,6 +65,7 @@
 #include "interpreter/unstarted_runtime.h"
 #include "jit/offline_profiling_info.h"
 #include "leb128.h"
+#include "linker/multi_oat_relative_patcher.h"
 #include "mirror/class-inl.h"
 #include "mirror/class_loader.h"
 #include "mirror/object-inl.h"
@@ -1408,7 +1409,7 @@
         if (opened_dex_files_map != nullptr) {
           opened_dex_files_maps_.push_back(std::move(opened_dex_files_map));
           for (std::unique_ptr<const DexFile>& dex_file : opened_dex_files) {
-            dex_file_oat_filename_map_.emplace(dex_file.get(), oat_filenames_[i]);
+            dex_file_oat_index_map_.emplace(dex_file.get(), i);
             opened_dex_files_.push_back(std::move(dex_file));
           }
         } else {
@@ -1557,13 +1558,12 @@
                                      IsBootImage(),
                                      image_classes_.release(),
                                      compiled_classes_.release(),
-                                     nullptr,
+                                     /* compiled_methods */ nullptr,
                                      thread_count_,
                                      dump_stats_,
                                      dump_passes_,
                                      compiler_phases_timings_.get(),
                                      swap_fd_,
-                                     &dex_file_oat_filename_map_,
                                      profile_compilation_info_.get()));
     driver_->SetDexFilesForOatFile(dex_files_);
     driver_->CompileAll(class_loader_, dex_files_, timings_);
@@ -1667,7 +1667,7 @@
                                           IsAppImage(),
                                           image_storage_mode_,
                                           oat_filenames_,
-                                          dex_file_oat_filename_map_));
+                                          dex_file_oat_index_map_));
 
       // We need to prepare method offsets in the image address space for direct method patching.
       TimingLogger::ScopedTiming t2("dex2oat Prepare image address space", timings_);
@@ -1677,21 +1677,39 @@
       }
     }
 
+    linker::MultiOatRelativePatcher patcher(instruction_set_, instruction_set_features_.get());
     {
       TimingLogger::ScopedTiming t2("dex2oat Write ELF", timings_);
       for (size_t i = 0, size = oat_files_.size(); i != size; ++i) {
+        std::unique_ptr<ElfWriter>& elf_writer = elf_writers_[i];
+        std::unique_ptr<OatWriter>& oat_writer = oat_writers_[i];
+
+        std::vector<const DexFile*>& dex_files = dex_files_per_oat_file_[i];
+        oat_writer->PrepareLayout(driver_.get(), image_writer_.get(), dex_files, &patcher);
+
+        size_t rodata_size = oat_writer->GetOatHeader().GetExecutableOffset();
+        size_t text_size = oat_writer->GetSize() - rodata_size;
+        elf_writer->SetLoadedSectionSizes(rodata_size, text_size, oat_writer->GetBssSize());
+
+        if (IsImage()) {
+          // Update oat layout.
+          DCHECK(image_writer_ != nullptr);
+          DCHECK_LT(i, oat_filenames_.size());
+          image_writer_->UpdateOatFileLayout(i,
+                                             elf_writer->GetLoadedSize(),
+                                             oat_writer->GetOatDataOffset(),
+                                             oat_writer->GetSize());
+        }
+      }
+
+      for (size_t i = 0, size = oat_files_.size(); i != size; ++i) {
         std::unique_ptr<File>& oat_file = oat_files_[i];
         std::unique_ptr<ElfWriter>& elf_writer = elf_writers_[i];
         std::unique_ptr<OatWriter>& oat_writer = oat_writers_[i];
 
-        std::vector<const DexFile*>& dex_files = dex_files_per_oat_file_[i];
-        oat_writer->PrepareLayout(driver_.get(), image_writer_.get(), dex_files);
-
         // We need to mirror the layout of the ELF file in the compressed debug-info.
-        // Therefore we need to propagate the sizes of at least those sections.
-        size_t rodata_size = oat_writer->GetOatHeader().GetExecutableOffset();
-        size_t text_size = oat_writer->GetSize() - rodata_size;
-        elf_writer->PrepareDebugInfo(rodata_size, text_size, oat_writer->GetMethodDebugInfo());
+        // Therefore PrepareDebugInfo() relies on the SetLoadedSectionSizes() call further above.
+        elf_writer->PrepareDebugInfo(oat_writer->GetMethodDebugInfo());
 
         OutputStream*& rodata = rodata_[i];
         DCHECK(rodata != nullptr);
@@ -1717,7 +1735,13 @@
           return false;
         }
 
-        elf_writer->SetBssSize(oat_writer->GetBssSize());
+        if (IsImage()) {
+          // Update oat header information.
+          DCHECK(image_writer_ != nullptr);
+          DCHECK_LT(i, oat_filenames_.size());
+          image_writer_->UpdateOatFileHeader(i, oat_writer->GetOatHeader());
+        }
+
         elf_writer->WriteDynamicSection();
         elf_writer->WriteDebugInfo(oat_writer->GetMethodDebugInfo());
         elf_writer->WritePatchLocations(oat_writer->GetAbsolutePatchLocations());
@@ -1731,19 +1755,10 @@
         if (oat_files_[i] != nullptr) {
           if (oat_files_[i]->Flush() != 0) {
             PLOG(ERROR) << "Failed to flush oat file: " << oat_filenames_[i];
-            oat_files_[i]->Erase();
             return false;
           }
         }
 
-        if (IsImage()) {
-          // Update oat estimates.
-          DCHECK(image_writer_ != nullptr);
-          DCHECK_LT(i, oat_filenames_.size());
-
-          image_writer_->UpdateOatFile(oat_file.get(), oat_filenames_[i]);
-        }
-
         VLOG(compiler) << "Oat file written successfully: " << oat_filenames_[i];
 
         oat_writer.reset();
@@ -2226,22 +2241,21 @@
     }
     if (!image_writer_->Write(app_image_fd_,
                               image_filenames_,
-                              oat_fd_,
-                              oat_filenames_,
-                              oat_location_)) {
+                              oat_filenames_)) {
       LOG(ERROR) << "Failure during image file creation";
       return false;
     }
 
     // We need the OatDataBegin entries.
-    std::map<const char*, uintptr_t> oat_data_begins;
-    for (const char* oat_filename : oat_filenames_) {
-      oat_data_begins.emplace(oat_filename, image_writer_->GetOatDataBegin(oat_filename));
+    dchecked_vector<uintptr_t> oat_data_begins;
+    for (size_t i = 0, size = oat_filenames_.size(); i != size; ++i) {
+      oat_data_begins.push_back(image_writer_->GetOatDataBegin(i));
     }
     // Destroy ImageWriter before doing FixupElf.
     image_writer_.reset();
 
-    for (const char* oat_filename : oat_filenames_) {
+    for (size_t i = 0, size = oat_filenames_.size(); i != size; ++i) {
+      const char* oat_filename = oat_filenames_[i];
       // Do not fix up the ELF file if we are --compile-pic or compiling the app image
       if (!compiler_options_->GetCompilePic() && IsBootImage()) {
         std::unique_ptr<File> oat_file(OS::OpenFileReadWrite(oat_filename));
@@ -2250,9 +2264,7 @@
           return false;
         }
 
-        uintptr_t oat_data_begin = oat_data_begins.find(oat_filename)->second;
-
-        if (!ElfWriter::Fixup(oat_file.get(), oat_data_begin)) {
+        if (!ElfWriter::Fixup(oat_file.get(), oat_data_begins[i])) {
           oat_file->Erase();
           LOG(ERROR) << "Failed to fixup ELF file " << oat_file->GetPath();
           return false;
@@ -2468,7 +2480,7 @@
   TimingLogger* timings_;
   std::unique_ptr<CumulativeLogger> compiler_phases_timings_;
   std::vector<std::vector<const DexFile*>> dex_files_per_oat_file_;
-  std::unordered_map<const DexFile*, const char*> dex_file_oat_filename_map_;
+  std::unordered_map<const DexFile*, size_t> dex_file_oat_index_map_;
 
   // Backing storage.
   std::vector<std::string> char_backing_storage_;
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index af08fc4..e30b968 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -145,7 +145,9 @@
       bss->WriteNoBitsSection(oat_file_->BssSize());
     }
 
-    builder_->WriteDynamicSection(elf_file->GetPath());
+    builder_->PrepareDynamicSection(
+        elf_file->GetPath(), rodata_size, text_size, oat_file_->BssSize());
+    builder_->WriteDynamicSection();
 
     Walk(&art::OatSymbolizer::RegisterForDedup);
 
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index a8b48ee..0e5b503 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -99,16 +99,16 @@
   }
 
   // Used to insert a new mapping at a known position for better performance.
-  iterator PutBefore(iterator pos, const K& k, const V& v) {
+  iterator PutBefore(const_iterator pos, const K& k, const V& v) {
     // Check that we're using the correct position and the key is not in the map.
     DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
-    DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
+    DCHECK(pos == map_.begin() || map_.key_comp()((--const_iterator(pos))->first, k));
     return map_.emplace_hint(pos, k, v);
   }
-  iterator PutBefore(iterator pos, const K& k, V&& v) {
+  iterator PutBefore(const_iterator pos, const K& k, V&& v) {
     // Check that we're using the correct position and the key is not in the map.
     DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
-    DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
+    DCHECK(pos == map_.begin() || map_.key_comp()((--const_iterator(pos))->first, k));
     return map_.emplace_hint(pos, k, std::move(v));
   }