Runtime can now be set to require relocation

Add a pair of runtime flags -Xrelocate and -Xnorelocate that can force
the runtime to require that all files that are run are relocated, to
prevent attacks based on the known art base address.

Add support for running patchoat on oat files compiled without an image.

Change run-test to have new --prebuild and --relocate flags.

Bug: 15358152

Change-Id: I91166c62dd1ab80e5cbcb7883a2cd0d56afca32d
diff --git a/runtime/base/scoped_flock.cc b/runtime/base/scoped_flock.cc
index 351de3d..bf091d0 100644
--- a/runtime/base/scoped_flock.cc
+++ b/runtime/base/scoped_flock.cc
@@ -58,6 +58,22 @@
   }
 }
 
+bool ScopedFlock::Init(File* file, std::string* error_msg) {
+  file_.reset(new File(dup(file->Fd())));
+  if (file_->Fd() == -1) {
+    file_.reset();
+    *error_msg = StringPrintf("Failed to duplicate open file '%s': %s",
+                              file->GetPath().c_str(), strerror(errno));
+    return false;
+  }
+  if (0 != TEMP_FAILURE_RETRY(flock(file_->Fd(), LOCK_EX))) {
+    file_.reset();
+    *error_msg = StringPrintf("Failed to lock file '%s': %s", file->GetPath().c_str(), strerror(errno));
+    return false;
+  }
+  return true;
+}
+
 File* ScopedFlock::GetFile() {
   CHECK(file_.get() != NULL);
   return file_.get();
diff --git a/runtime/base/scoped_flock.h b/runtime/base/scoped_flock.h
index f8ed805..08612e3 100644
--- a/runtime/base/scoped_flock.h
+++ b/runtime/base/scoped_flock.h
@@ -37,6 +37,10 @@
   // changed (usually due to a new file being created at the same path)
   // between attempts to lock it.
   bool Init(const char* filename, std::string* error_msg);
+  // Attempt to acquire an exclusive file lock (see flock(2)) on 'file'.
+  // Returns true if the lock could be acquired or false if an error
+  // occured.
+  bool Init(File* file, std::string* error_msg);
 
   // Returns the (locked) file associated with this instance.
   File* GetFile();
@@ -45,6 +49,7 @@
   bool HasFile();
 
   ~ScopedFlock();
+
  private:
   std::unique_ptr<File> file_;
   DISALLOW_COPY_AND_ASSIGN(ScopedFlock);
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 3364491..753f2f0 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -814,6 +814,7 @@
         return false;
       }
 
+      // TODO Caller specifically asks for this oat_location. We should honor it. Probably?
       open_oat_file.reset(FindOatFileInOatLocationForDexFile(dex_location, dex_location_checksum,
                                                              oat_location, &error_msg));
 
@@ -938,6 +939,13 @@
                               actual_image_oat_offset);
     return nullptr;
   }
+  int32_t expected_patch_delta = image_header.GetPatchDelta();
+  int32_t actual_patch_delta = oat_file->GetOatHeader().GetImagePatchDelta();
+  if (expected_patch_delta != actual_patch_delta) {
+    *error_msg = StringPrintf("Failed to find oat file at '%s' with expected patch delta %d, "
+                              " found %d", oat_location, expected_patch_delta, actual_patch_delta);
+    return nullptr;
+  }
   const OatFile::OatDexFile* oat_dex_file = oat_file->GetOatDexFile(dex_location,
                                                                     &dex_location_checksum);
   if (oat_dex_file == nullptr) {
@@ -998,19 +1006,23 @@
   // image header from the image for the right instruction set.
   uint32_t image_oat_checksum = 0;
   uintptr_t image_oat_data_begin = 0;
-  if (instruction_set == kRuntimeISA) {
+  int32_t image_patch_delta = 0;
+  if (instruction_set == Runtime::Current()->GetInstructionSet()) {
     const ImageHeader& image_header = image_space->GetImageHeader();
     image_oat_checksum = image_header.GetOatChecksum();
     image_oat_data_begin = reinterpret_cast<uintptr_t>(image_header.GetOatDataBegin());
+    image_patch_delta = image_header.GetPatchDelta();
   } else {
     std::unique_ptr<ImageHeader> image_header(gc::space::ImageSpace::ReadImageHeaderOrDie(
         image_space->GetImageLocation().c_str(), instruction_set));
     image_oat_checksum = image_header->GetOatChecksum();
     image_oat_data_begin = reinterpret_cast<uintptr_t>(image_header->GetOatDataBegin());
+    image_patch_delta = image_header->GetPatchDelta();
   }
   const OatHeader& oat_header = oat_file->GetOatHeader();
   bool image_check = ((oat_header.GetImageFileLocationOatChecksum() == image_oat_checksum)
-                      && (oat_header.GetImageFileLocationOatDataBegin() == image_oat_data_begin));
+                      && (oat_header.GetImageFileLocationOatDataBegin() == image_oat_data_begin)
+                      && (oat_header.GetImagePatchDelta() == image_patch_delta));
 
   const OatFile::OatDexFile* oat_dex_file = oat_file->GetOatDexFile(dex_location,
                                                                     &dex_location_checksum);
@@ -1049,16 +1061,11 @@
   return false;
 }
 
-const OatFile* ClassLinker::LoadOatFileAndVerifyDexFile(const std::string& oat_file_location,
-                                                        const char* dex_location,
-                                                        std::string* error_msg,
-                                                        bool* open_failed) {
-  std::unique_ptr<const OatFile> oat_file(FindOatFileFromOatLocation(oat_file_location, error_msg));
-  if (oat_file.get() == nullptr) {
-    *open_failed = true;
-    return nullptr;
-  }
-  *open_failed = false;
+bool ClassLinker::VerifyOatWithDexFile(const OatFile* oat_file,
+                                       const char* dex_location,
+                                       std::string* error_msg) {
+  CHECK(oat_file != nullptr);
+  CHECK(dex_location != nullptr);
   std::unique_ptr<const DexFile> dex_file;
   uint32_t dex_location_checksum;
   if (!DexFile::GetChecksum(dex_location, &dex_location_checksum, error_msg)) {
@@ -1068,26 +1075,21 @@
     const OatFile::OatDexFile* oat_dex_file = oat_file->GetOatDexFile(dex_location, NULL);
     if (oat_dex_file == nullptr) {
       *error_msg = StringPrintf("Dex checksum mismatch for location '%s' and failed to find oat "
-                                "dex file '%s': %s", oat_file_location.c_str(), dex_location,
+                                "dex file '%s': %s", oat_file->GetLocation().c_str(), dex_location,
                                 error_msg->c_str());
-      return nullptr;
+      return false;
     }
     dex_file.reset(oat_dex_file->OpenDexFile(error_msg));
   } else {
-    bool verified = VerifyOatFileChecksums(oat_file.get(), dex_location, dex_location_checksum,
+    bool verified = VerifyOatFileChecksums(oat_file, dex_location, dex_location_checksum,
                                            kRuntimeISA, error_msg);
     if (!verified) {
-      return nullptr;
+      return false;
     }
     dex_file.reset(oat_file->GetOatDexFile(dex_location,
                                            &dex_location_checksum)->OpenDexFile(error_msg));
   }
-
-  if (dex_file.get() != nullptr) {
-    return oat_file.release();
-  } else {
-    return nullptr;
-  }
+  return dex_file.get() != nullptr;
 }
 
 const OatFile* ClassLinker::FindOatFileContainingDexFileFromDexLocation(
@@ -1097,51 +1099,25 @@
     std::vector<std::string>* error_msgs,
     bool* obsolete_file_cleanup_failed) {
   *obsolete_file_cleanup_failed = false;
-  // Look for an existing file next to dex. for example, for
-  // /foo/bar/baz.jar, look for /foo/bar/<isa>/baz.odex.
-  std::string odex_filename(DexFilenameToOdexFilename(dex_location, isa));
-  bool open_failed;
+  bool already_opened = false;
+  std::string dex_location_str(dex_location);
+  std::unique_ptr<const OatFile> oat_file(OpenOatFileFromDexLocation(dex_location_str, isa,
+                                                                     &already_opened,
+                                                                     obsolete_file_cleanup_failed,
+                                                                     error_msgs));
   std::string error_msg;
-  const OatFile* oat_file = LoadOatFileAndVerifyDexFile(odex_filename, dex_location, &error_msg,
-                                                        &open_failed);
-  if (oat_file != nullptr) {
-    return oat_file;
-  }
-  if (dex_location_checksum == nullptr) {
-    error_msgs->push_back(StringPrintf("Failed to open oat file from %s and no classes.dex found in"
-                                      "%s: %s", odex_filename.c_str(), dex_location,
+  if (oat_file.get() == nullptr) {
+    error_msgs->push_back(StringPrintf("Failed to open oat file from dex location '%s'",
+                                       dex_location));
+    return nullptr;
+  } else if (!VerifyOatWithDexFile(oat_file.get(), dex_location, &error_msg)) {
+    error_msgs->push_back(StringPrintf("Failed to verify oat file '%s' found for dex location "
+                                       "'%s': %s", oat_file->GetLocation().c_str(), dex_location,
                                        error_msg.c_str()));
     return nullptr;
+  } else {
+    return oat_file.release();
   }
-
-  std::string cache_error_msg;
-  const std::string dalvik_cache(GetDalvikCacheOrDie(GetInstructionSetString(kRuntimeISA)));
-  std::string cache_location(GetDalvikCacheFilenameOrDie(dex_location,
-                                                         dalvik_cache.c_str()));
-  oat_file = LoadOatFileAndVerifyDexFile(cache_location, dex_location, &cache_error_msg,
-                                         &open_failed);
-  if (oat_file != nullptr) {
-    return oat_file;
-  }
-
-  if (!open_failed && TEMP_FAILURE_RETRY(unlink(cache_location.c_str())) != 0) {
-    std::string error_msg = StringPrintf("Failed to remove obsolete file from %s when searching"
-                                         "for dex file %s: %s",
-                                         cache_location.c_str(), dex_location, strerror(errno));
-    error_msgs->push_back(error_msg);
-    VLOG(class_linker) << error_msg;
-    // Let the caller know that we couldn't remove the obsolete file.
-    // This is a good indication that further writes may fail as well.
-    *obsolete_file_cleanup_failed = true;
-  }
-
-  std::string compound_msg = StringPrintf("Failed to open oat file from %s (error '%s') or %s "
-                                          "(error '%s').", odex_filename.c_str(), error_msg.c_str(),
-                                          cache_location.c_str(), cache_error_msg.c_str());
-  VLOG(class_linker) << compound_msg;
-  error_msgs->push_back(compound_msg);
-
-  return nullptr;
 }
 
 const OatFile* ClassLinker::FindOpenedOatFileFromOatLocation(const std::string& oat_location) {
@@ -1156,6 +1132,277 @@
   return nullptr;
 }
 
+const OatFile* ClassLinker::OpenOatFileFromDexLocation(const std::string& dex_location,
+                                                       InstructionSet isa,
+                                                       bool *already_opened,
+                                                       bool *obsolete_file_cleanup_failed,
+                                                       std::vector<std::string>* error_msgs) {
+  // Find out if we've already opened the file
+  const OatFile* ret = nullptr;
+  std::string odex_filename(DexFilenameToOdexFilename(dex_location, isa));
+  ret = FindOpenedOatFileFromOatLocation(odex_filename);
+  if (ret != nullptr) {
+    *already_opened = true;
+    return ret;
+  }
+
+  std::string dalvik_cache;
+  bool have_android_data = false;
+  bool have_dalvik_cache = false;
+  GetDalvikCache(GetInstructionSetString(kRuntimeISA), false, &dalvik_cache,
+                 &have_android_data, &have_dalvik_cache);
+  std::string cache_filename;
+  if (have_dalvik_cache) {
+    cache_filename = GetDalvikCacheFilenameOrDie(dex_location.c_str(), dalvik_cache.c_str());
+    ret = FindOpenedOatFileFromOatLocation(cache_filename);
+    if (ret != nullptr) {
+      *already_opened = true;
+      return ret;
+    }
+  } else {
+    // If we need to relocate we should just place odex back where it started.
+    cache_filename = odex_filename;
+  }
+
+  ret = nullptr;
+
+  // We know that neither the odex nor the cache'd version is already in use, if it even exists.
+  //
+  // Now we do the following:
+  // 1) Try and open the odex version
+  // 2) If present, checksum-verified & relocated correctly return it
+  // 3) Close the odex version to free up its address space.
+  // 4) Try and open the cache version
+  // 5) If present, checksum-verified & relocated correctly return it
+  // 6) Close the cache version to free up its address space.
+  // 7) If we should relocate:
+  //   a) If we have opened and checksum-verified the odex version relocate it to
+  //      'cache_filename' and return it
+  //   b) If we have opened and checksum-verified the cache version relocate it in place and return
+  //      it. This should not happen often (I think only the run-test's will hit this case).
+  // 8) If the cache-version was present we should delete it since it must be obsolete if we get to
+  //    this point.
+  // 9) Return nullptr
+
+  *already_opened = false;
+  const Runtime* runtime = Runtime::Current();
+  CHECK(runtime != nullptr);
+  bool executable = !runtime->IsCompiler();
+
+  std::string odex_error_msg;
+  bool should_patch_system = false;
+  bool odex_checksum_verified = false;
+  {
+    // There is a high probability that these both these oat files map similar/the same address
+    // spaces so we must scope them like this so they each gets its turn.
+    std::unique_ptr<OatFile> odex_oat_file(OatFile::Open(odex_filename, odex_filename, NULL,
+                                                         executable, &odex_error_msg));
+    if (odex_oat_file.get() != nullptr && CheckOatFile(odex_oat_file.get(), isa,
+                                                       &odex_checksum_verified,
+                                                       &odex_error_msg)) {
+      error_msgs->push_back(odex_error_msg);
+      return odex_oat_file.release();
+    } else if (odex_checksum_verified) {
+      // We can just relocate
+      should_patch_system = true;
+      odex_error_msg = "Image Patches are incorrect";
+    }
+  }
+
+
+  std::string cache_error_msg;
+  bool should_patch_cache = false;
+  bool cache_checksum_verified = false;
+  if (have_dalvik_cache) {
+    std::unique_ptr<OatFile> cache_oat_file(OatFile::Open(cache_filename, cache_filename, NULL,
+                                                          executable, &cache_error_msg));
+    if (cache_oat_file.get() != nullptr && CheckOatFile(cache_oat_file.get(), isa,
+                                                        &cache_checksum_verified,
+                                                        &cache_error_msg)) {
+      error_msgs->push_back(cache_error_msg);
+      return cache_oat_file.release();
+    } else if (cache_checksum_verified) {
+      // We can just relocate
+      should_patch_cache = true;
+      cache_error_msg = "Image Patches are incorrect";
+    }
+  } else if (have_android_data) {
+    // dalvik_cache does not exist but android data does. This means we should be able to create
+    // it, so we should try.
+    GetDalvikCacheOrDie(GetInstructionSetString(kRuntimeISA), true);
+  }
+
+  ret = nullptr;
+  std::string error_msg;
+  if (runtime->CanRelocate()) {
+    // Run relocation
+    const std::string& image_location =
+        Runtime::Current()->GetHeap()->GetImageSpace()->GetImageLocation();
+    if (odex_checksum_verified && should_patch_system) {
+      ret = PatchAndRetrieveOat(odex_filename, cache_filename, image_location, isa, &error_msg);
+    } else if (cache_checksum_verified && should_patch_cache) {
+      CHECK(have_dalvik_cache);
+      ret = PatchAndRetrieveOat(cache_filename, cache_filename, image_location, isa, &error_msg);
+    }
+  }
+  if (ret == nullptr && have_dalvik_cache && OS::FileExists(cache_filename.c_str())) {
+    // implicitly: were able to fine where the cached version is but we were unable to use it,
+    // either as a destination for relocation or to open a file. We should delete it if it is
+    // there.
+    if (TEMP_FAILURE_RETRY(unlink(cache_filename.c_str())) != 0) {
+      std::string rm_error_msg = StringPrintf("Failed to remove obsolete file from %s when "
+                                              "searching for dex file %s: %s",
+                                              cache_filename.c_str(), dex_location.c_str(),
+                                              strerror(errno));
+      error_msgs->push_back(rm_error_msg);
+      VLOG(class_linker) << rm_error_msg;
+      // Let the caller know that we couldn't remove the obsolete file.
+      // This is a good indication that further writes may fail as well.
+      *obsolete_file_cleanup_failed = true;
+    }
+  }
+  if (ret == nullptr) {
+    VLOG(class_linker) << error_msg;
+    error_msgs->push_back(error_msg);
+    std::string relocation_msg;
+    if (runtime->CanRelocate()) {
+      relocation_msg = StringPrintf(" and relocation failed");
+    }
+    if (have_dalvik_cache && cache_checksum_verified) {
+      error_msg = StringPrintf("Failed to open oat file from %s (error %s) or %s "
+                                "(error %s)%s.", odex_filename.c_str(), odex_error_msg.c_str(),
+                                cache_filename.c_str(), cache_error_msg.c_str(),
+                                relocation_msg.c_str());
+    } else {
+      error_msg = StringPrintf("Failed to open oat file from %s (error %s) (no "
+                               "dalvik_cache availible)%s.", odex_filename.c_str(),
+                               odex_error_msg.c_str(), relocation_msg.c_str());
+    }
+    VLOG(class_linker) << error_msg;
+    error_msgs->push_back(error_msg);
+  }
+  return ret;
+}
+
+const OatFile* ClassLinker::PatchAndRetrieveOat(const std::string& input_oat,
+                                                const std::string& output_oat,
+                                                const std::string& image_location,
+                                                InstructionSet isa,
+                                                std::string* error_msg) {
+  Locks::mutator_lock_->AssertNotHeld(Thread::Current());  // Avoid starving GC.
+  std::string patchoat(Runtime::Current()->GetPatchoatExecutable());
+
+  std::string isa_arg("--instruction-set=");
+  isa_arg += GetInstructionSetString(isa);
+  std::string input_oat_filename_arg("--input-oat-file=");
+  input_oat_filename_arg += input_oat;
+  std::string output_oat_filename_arg("--output-oat-file=");
+  output_oat_filename_arg += output_oat;
+  std::string patched_image_arg("--patched-image-location=");
+  patched_image_arg += image_location;
+
+  std::vector<std::string> argv;
+  argv.push_back(patchoat);
+  argv.push_back(isa_arg);
+  argv.push_back(input_oat_filename_arg);
+  argv.push_back(output_oat_filename_arg);
+  argv.push_back(patched_image_arg);
+
+  std::string command_line(Join(argv, ' '));
+  LOG(INFO) << "Relocate Oat File: " << command_line;
+  bool success = Exec(argv, error_msg);
+  if (success) {
+    std::unique_ptr<OatFile> output(OatFile::Open(output_oat, output_oat, NULL,
+                                                  !Runtime::Current()->IsCompiler(), error_msg));
+    bool checksum_verified = false;
+    if (output.get() != nullptr && CheckOatFile(output.get(), isa, &checksum_verified, error_msg)) {
+      return output.release();
+    } else if (output.get() != nullptr) {
+      *error_msg = StringPrintf("Patching of oat file '%s' succeeded "
+                                "but output file '%s' failed verifcation: %s",
+                                input_oat.c_str(), output_oat.c_str(), error_msg->c_str());
+    } else {
+      *error_msg = StringPrintf("Patching of oat file '%s' succeeded "
+                                "but was unable to open output file '%s': %s",
+                                input_oat.c_str(), output_oat.c_str(), error_msg->c_str());
+    }
+  } else {
+    *error_msg = StringPrintf("Patching of oat file '%s to '%s' "
+                              "failed: %s", input_oat.c_str(), output_oat.c_str(),
+                              error_msg->c_str());
+  }
+  return nullptr;
+}
+
+int32_t ClassLinker::GetRequiredDelta(const OatFile* oat_file, InstructionSet isa) {
+  Runtime* runtime = Runtime::Current();
+  int32_t real_patch_delta;
+  const gc::space::ImageSpace* image_space = runtime->GetHeap()->GetImageSpace();
+  if (isa == Runtime::Current()->GetInstructionSet()) {
+    const ImageHeader& image_header = image_space->GetImageHeader();
+    real_patch_delta = image_header.GetPatchDelta();
+  } else {
+    std::unique_ptr<ImageHeader> image_header(gc::space::ImageSpace::ReadImageHeaderOrDie(
+        image_space->GetImageLocation().c_str(), isa));
+    real_patch_delta = image_header->GetPatchDelta();
+  }
+  const OatHeader& oat_header = oat_file->GetOatHeader();
+  return real_patch_delta - oat_header.GetImagePatchDelta();
+}
+
+bool ClassLinker::CheckOatFile(const OatFile* oat_file, InstructionSet isa,
+                               bool* checksum_verified,
+                               std::string* error_msg) {
+  std::string compound_msg("Oat file failed to verify: ");
+  Runtime* runtime = Runtime::Current();
+  uint32_t real_image_checksum;
+  void* real_image_oat_offset;
+  int32_t real_patch_delta;
+  const gc::space::ImageSpace* image_space = runtime->GetHeap()->GetImageSpace();
+  if (isa == Runtime::Current()->GetInstructionSet()) {
+    const ImageHeader& image_header = image_space->GetImageHeader();
+    real_image_checksum = image_header.GetOatChecksum();
+    real_image_oat_offset = image_header.GetOatDataBegin();
+    real_patch_delta = image_header.GetPatchDelta();
+  } else {
+    std::unique_ptr<ImageHeader> image_header(gc::space::ImageSpace::ReadImageHeaderOrDie(
+        image_space->GetImageLocation().c_str(), isa));
+    real_image_checksum = image_header->GetOatChecksum();
+    real_image_oat_offset = image_header->GetOatDataBegin();
+    real_patch_delta = image_header->GetPatchDelta();
+  }
+
+  const OatHeader& oat_header = oat_file->GetOatHeader();
+
+  uint32_t oat_image_checksum = oat_header.GetImageFileLocationOatChecksum();
+  *checksum_verified = oat_image_checksum == real_image_checksum;
+  if (!*checksum_verified) {
+    compound_msg += StringPrintf(" Oat Image Checksum Incorrect (expected 0x%x, recieved 0x%x)",
+                                 real_image_checksum, oat_image_checksum);
+  }
+
+  void* oat_image_oat_offset =
+      reinterpret_cast<void*>(oat_header.GetImageFileLocationOatDataBegin());
+  bool offset_verified = oat_image_oat_offset == real_image_oat_offset;
+  if (!offset_verified) {
+    compound_msg += StringPrintf(" Oat Image oat offset incorrect (expected 0x%p, recieved 0x%p)",
+                                 real_image_oat_offset, oat_image_oat_offset);
+  }
+
+  int32_t oat_patch_delta = oat_header.GetImagePatchDelta();
+  bool patch_delta_verified = oat_patch_delta == real_patch_delta;
+  if (!patch_delta_verified) {
+    compound_msg += StringPrintf(" Oat image patch delta incorrect (expected 0x%x, recieved 0x%x)",
+                                 real_patch_delta, oat_patch_delta);
+  }
+
+  bool ret = (*checksum_verified && offset_verified && patch_delta_verified);
+  if (ret) {
+    *error_msg = compound_msg;
+  }
+  return ret;
+}
+
 const OatFile* ClassLinker::FindOatFileFromOatLocation(const std::string& oat_location,
                                                        std::string* error_msg) {
   const OatFile* oat_file = FindOpenedOatFileFromOatLocation(oat_location);
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index c17f88d..b108f61 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -265,10 +265,6 @@
                        std::string* error_msg)
       LOCKS_EXCLUDED(Locks::mutator_lock_);
 
-  const OatFile* FindOatFileFromOatLocation(const std::string& location,
-                                            std::string* error_msg)
-      LOCKS_EXCLUDED(dex_lock_);
-
   // Find or create the oat file holding dex_location. Then load all corresponding dex files
   // (if multidex) into the given vector.
   bool OpenDexFilesFromOat(const char* dex_location, const char* oat_location,
@@ -546,9 +542,31 @@
   const OatFile* FindOpenedOatFile(const char* oat_location, const char* dex_location,
                                    const uint32_t* const dex_location_checksum)
       LOCKS_EXCLUDED(dex_lock_);
+
+  // Will open the oat file directly without relocating, even if we could/should do relocation.
+  const OatFile* FindOatFileFromOatLocation(const std::string& oat_location,
+                                            std::string* error_msg)
+      LOCKS_EXCLUDED(dex_lock_);
+
   const OatFile* FindOpenedOatFileFromOatLocation(const std::string& oat_location)
       LOCKS_EXCLUDED(dex_lock_);
 
+  const OatFile* OpenOatFileFromDexLocation(const std::string& dex_location,
+                                            InstructionSet isa,
+                                            bool* already_opened,
+                                            bool* obsolete_file_cleanup_failed,
+                                            std::vector<std::string>* error_msg)
+      LOCKS_EXCLUDED(dex_lock_, Locks::mutator_lock_);
+
+  const OatFile* PatchAndRetrieveOat(const std::string& input, const std::string& output,
+                                     const std::string& image_location, InstructionSet isa,
+                                     std::string* error_msg)
+      LOCKS_EXCLUDED(Locks::mutator_lock_);
+
+  bool CheckOatFile(const OatFile* oat_file, InstructionSet isa,
+                    bool* checksum_verified, std::string* error_msg);
+  int32_t GetRequiredDelta(const OatFile* oat_file, InstructionSet isa);
+
   // Note: will not register the oat file.
   const OatFile* FindOatFileInOatLocationForDexFile(const char* dex_location,
                                                     uint32_t dex_location_checksum,
@@ -575,14 +593,10 @@
                                                              bool* obsolete_file_cleanup_failed)
       LOCKS_EXCLUDED(dex_lock_, Locks::mutator_lock_);
 
-  // Find a verify an oat file with the given dex file. Will return nullptr when the oat file
-  // was not found or the dex file could not be verified.
-  // Note: Does not register the oat file.
-  const OatFile* LoadOatFileAndVerifyDexFile(const std::string& oat_file_location,
-                                             const char* dex_location,
-                                             std::string* error_msg,
-                                             bool* open_failed)
-      LOCKS_EXCLUDED(dex_lock_);
+  // verify an oat file with the given dex file. Will return false when the dex file could not be
+  // verified. Will return true otherwise.
+  bool VerifyOatWithDexFile(const OatFile* oat_file, const char* dex_location,
+                            std::string* error_msg);
 
   mirror::ArtMethod* CreateProxyConstructor(Thread* self, Handle<mirror::Class> klass,
                                             mirror::Class* proxy_class)
@@ -720,6 +734,8 @@
   const void* quick_to_interpreter_bridge_trampoline_;
 
   friend class ImageWriter;  // for GetClassRoots
+  friend class ImageDumper;  // for FindOpenedOatFileFromOatLocation
+  friend class ElfPatcher;  // for FindOpenedOatFileForDexFile & FindOpenedOatFileFromOatLocation
   FRIEND_TEST(ClassLinkerTest, ClassRootDescriptors);
   FRIEND_TEST(mirror::DexCacheTest, Open);
   FRIEND_TEST(ExceptionTest, FindExceptionHandler);
diff --git a/runtime/common_runtime_test.cc b/runtime/common_runtime_test.cc
index f47f13d..2826f89 100644
--- a/runtime/common_runtime_test.cc
+++ b/runtime/common_runtime_test.cc
@@ -199,12 +199,13 @@
   runtime_->GetHeap()->VerifyHeap();  // Check for heap corruption before the test
 }
 
-void CommonRuntimeTest::TearDown() {
-  const char* android_data = getenv("ANDROID_DATA");
-  ASSERT_TRUE(android_data != nullptr);
-  DIR* dir = opendir(dalvik_cache_.c_str());
+
+void CommonRuntimeTest::ClearDirectory(const char* dirpath) {
+  ASSERT_TRUE(dirpath != nullptr);
+  DIR* dir = opendir(dirpath);
   ASSERT_TRUE(dir != nullptr);
   dirent* e;
+  struct stat s;
   while ((e = readdir(dir)) != nullptr) {
     if ((strcmp(e->d_name, ".") == 0) || (strcmp(e->d_name, "..") == 0)) {
       continue;
@@ -212,10 +213,24 @@
     std::string filename(dalvik_cache_);
     filename.push_back('/');
     filename.append(e->d_name);
-    int unlink_result = unlink(filename.c_str());
-    ASSERT_EQ(0, unlink_result);
+    int stat_result = lstat(filename.c_str(), &s);
+    ASSERT_EQ(0, stat_result) << "unable to stat " << filename;
+    if (S_ISDIR(s.st_mode)) {
+      ClearDirectory(filename.c_str());
+      int rmdir_result = rmdir(filename.c_str());
+      ASSERT_EQ(0, rmdir_result) << filename;
+    } else {
+      int unlink_result = unlink(filename.c_str());
+      ASSERT_EQ(0, unlink_result) << filename;
+    }
   }
   closedir(dir);
+}
+
+void CommonRuntimeTest::TearDown() {
+  const char* android_data = getenv("ANDROID_DATA");
+  ASSERT_TRUE(android_data != nullptr);
+  ClearDirectory(dalvik_cache_.c_str());
   int rmdir_cache_result = rmdir(dalvik_cache_.c_str());
   ASSERT_EQ(0, rmdir_cache_result);
   int rmdir_data_result = rmdir(android_data_.c_str());
diff --git a/runtime/common_runtime_test.h b/runtime/common_runtime_test.h
index d045031..eb96352 100644
--- a/runtime/common_runtime_test.h
+++ b/runtime/common_runtime_test.h
@@ -81,6 +81,8 @@
   // Allow subclases such as CommonCompilerTest to add extra options.
   virtual void SetUpRuntimeOptions(RuntimeOptions* options) {}
 
+  void ClearDirectory(const char* dirpath);
+
   virtual void TearDown();
 
   std::string GetLibCoreDexFileName();
diff --git a/runtime/compiler_callbacks.h b/runtime/compiler_callbacks.h
index b07043f..d1a6861 100644
--- a/runtime/compiler_callbacks.h
+++ b/runtime/compiler_callbacks.h
@@ -36,6 +36,10 @@
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) = 0;
     virtual void ClassRejected(ClassReference ref) = 0;
 
+    // Return true if we should attempt to relocate to a random base address if we have not already
+    // done so. Return false if relocating in this way would be problematic.
+    virtual bool IsRelocationPossible() = 0;
+
   protected:
     CompilerCallbacks() { }
 };
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index a87aa89..3eaa64c 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -16,6 +16,8 @@
 
 #include "image_space.h"
 
+#include <random>
+
 #include "base/stl_util.h"
 #include "base/unix_file/fd_file.h"
 #include "base/scoped_flock.h"
@@ -94,86 +96,304 @@
 
 bool ImageSpace::FindImageFilename(const char* image_location,
                                    const InstructionSet image_isa,
-                                   std::string* image_filename,
-                                   bool *is_system) {
+                                   std::string* system_filename,
+                                   bool* has_system,
+                                   std::string* cache_filename,
+                                   bool* dalvik_cache_exists,
+                                   bool* has_cache) {
+  *has_system = false;
+  *has_cache = false;
   // image_location = /system/framework/boot.art
   // system_image_location = /system/framework/<image_isa>/boot.art
   std::string system_image_filename(GetSystemImageFilename(image_location, image_isa));
   if (OS::FileExists(system_image_filename.c_str())) {
-    *image_filename = system_image_filename;
-    *is_system = true;
-    return true;
+    *system_filename = system_image_filename;
+    *has_system = true;
   }
 
-  const std::string dalvik_cache = GetDalvikCacheOrDie(GetInstructionSetString(image_isa));
+  bool have_android_data = false;
+  *dalvik_cache_exists = false;
+  std::string dalvik_cache;
+  GetDalvikCache(GetInstructionSetString(image_isa), true, &dalvik_cache,
+                 &have_android_data, dalvik_cache_exists);
 
-  // Always set output location even if it does not exist,
-  // so that the caller knows where to create the image.
-  //
-  // image_location = /system/framework/boot.art
-  // *image_filename = /data/dalvik-cache/<image_isa>/boot.art
-  *image_filename = GetDalvikCacheFilenameOrDie(image_location, dalvik_cache.c_str());
-  *is_system = false;
-  return OS::FileExists(image_filename->c_str());
+  if (have_android_data && *dalvik_cache_exists) {
+    // Always set output location even if it does not exist,
+    // so that the caller knows where to create the image.
+    //
+    // image_location = /system/framework/boot.art
+    // *image_filename = /data/dalvik-cache/<image_isa>/boot.art
+    std::string error_msg;
+    if (!GetDalvikCacheFilename(image_location, dalvik_cache.c_str(), cache_filename, &error_msg)) {
+      LOG(WARNING) << error_msg;
+      return *has_system;
+    }
+    *has_cache = OS::FileExists(cache_filename->c_str());
+  }
+  return *has_system || *has_cache;
+}
+
+static bool ReadSpecificImageHeader(const char* filename, ImageHeader* image_header) {
+    std::unique_ptr<File> image_file(OS::OpenFileForReading(filename));
+    if (image_file.get() == nullptr) {
+      return false;
+    }
+    const bool success = image_file->ReadFully(image_header, sizeof(ImageHeader));
+    if (!success || !image_header->IsValid()) {
+      return false;
+    }
+    return true;
+}
+
+static int32_t ChooseRelocationOffsetDelta(int32_t min_delta, int32_t max_delta) {
+  CHECK_ALIGNED(min_delta, kPageSize);
+  CHECK_ALIGNED(max_delta, kPageSize);
+  CHECK_LT(min_delta, max_delta);
+
+  std::default_random_engine generator;
+  generator.seed(NanoTime() * getpid());
+  std::uniform_int_distribution<int32_t> distribution(min_delta, max_delta);
+  int32_t r = distribution(generator);
+  if (r % 2 == 0) {
+    r = RoundUp(r, kPageSize);
+  } else {
+    r = RoundDown(r, kPageSize);
+  }
+  CHECK_LT(min_delta, r);
+  CHECK_GT(max_delta, r);
+  CHECK_ALIGNED(r, kPageSize);
+  return r;
+}
+
+bool ImageSpace::RelocateImage(const char* image_location, const char* dest_filename,
+                               InstructionSet isa, std::string* error_msg) {
+  std::string patchoat(Runtime::Current()->GetPatchoatExecutable());
+
+  std::string input_image_location_arg("--input-image-location=");
+  input_image_location_arg += image_location;
+
+  std::string output_image_filename_arg("--output-image-file=");
+  output_image_filename_arg += dest_filename;
+
+  std::string input_oat_location_arg("--input-oat-location=");
+  input_oat_location_arg += ImageHeader::GetOatLocationFromImageLocation(image_location);
+
+  std::string output_oat_filename_arg("--output-oat-file=");
+  output_oat_filename_arg += ImageHeader::GetOatLocationFromImageLocation(dest_filename);
+
+  std::string instruction_set_arg("--instruction-set=");
+  instruction_set_arg += GetInstructionSetString(isa);
+
+  std::string base_offset_arg("--base-offset-delta=");
+  StringAppendF(&base_offset_arg, "%d", ChooseRelocationOffsetDelta(ART_BASE_ADDRESS_MIN_DELTA,
+                                                                    ART_BASE_ADDRESS_MAX_DELTA));
+
+  std::vector<std::string> argv;
+  argv.push_back(patchoat);
+
+  argv.push_back(input_image_location_arg);
+  argv.push_back(output_image_filename_arg);
+
+  argv.push_back(input_oat_location_arg);
+  argv.push_back(output_oat_filename_arg);
+
+  argv.push_back(instruction_set_arg);
+  argv.push_back(base_offset_arg);
+
+  std::string command_line(Join(argv, ' '));
+  LOG(INFO) << "RelocateImage: " << command_line;
+  return Exec(argv, error_msg);
+}
+
+static ImageHeader* ReadSpecificImageHeaderOrDie(const char* filename) {
+  std::unique_ptr<ImageHeader> hdr(new ImageHeader);
+  if (!ReadSpecificImageHeader(filename, hdr.get())) {
+    LOG(FATAL) << "Unable to read image header for " << filename;
+    return nullptr;
+  }
+  return hdr.release();
 }
 
 ImageHeader* ImageSpace::ReadImageHeaderOrDie(const char* image_location,
                                               const InstructionSet image_isa) {
-  std::string image_filename;
-  bool is_system = false;
-  if (FindImageFilename(image_location, image_isa, &image_filename, &is_system)) {
-    std::unique_ptr<File> image_file(OS::OpenFileForReading(image_filename.c_str()));
-    std::unique_ptr<ImageHeader> image_header(new ImageHeader);
-    const bool success = image_file->ReadFully(image_header.get(), sizeof(ImageHeader));
-    if (!success || !image_header->IsValid()) {
-      LOG(FATAL) << "Invalid Image header for: " << image_filename;
-      return nullptr;
+  std::string system_filename;
+  bool has_system = false;
+  std::string cache_filename;
+  bool has_cache = false;
+  bool dalvik_cache_exists = false;
+  if (FindImageFilename(image_location, image_isa, &system_filename, &has_system,
+                        &cache_filename, &dalvik_cache_exists, &has_cache)) {
+    if (Runtime::Current()->ShouldRelocate()) {
+      if (has_system && has_cache) {
+        std::unique_ptr<ImageHeader> sys_hdr(new ImageHeader);
+        std::unique_ptr<ImageHeader> cache_hdr(new ImageHeader);
+        if (!ReadSpecificImageHeader(system_filename.c_str(), sys_hdr.get())) {
+          LOG(FATAL) << "Unable to read image header for " << image_location << " at "
+                     << system_filename;
+          return nullptr;
+        }
+        if (!ReadSpecificImageHeader(cache_filename.c_str(), cache_hdr.get())) {
+          LOG(FATAL) << "Unable to read image header for " << image_location << " at "
+                     << cache_filename;
+          return nullptr;
+        }
+        if (sys_hdr->GetOatChecksum() != cache_hdr->GetOatChecksum()) {
+          LOG(FATAL) << "Unable to find a relocated version of image file " << image_location;
+          return nullptr;
+        }
+        return cache_hdr.release();
+      } else if (!has_cache) {
+        LOG(FATAL) << "Unable to find a relocated version of image file " << image_location;
+        return nullptr;
+      } else if (!has_system && has_cache) {
+        // This can probably just use the cache one.
+        return ReadSpecificImageHeaderOrDie(cache_filename.c_str());
+      }
+    } else {
+      // We don't want to relocate, Just pick the appropriate one if we have it and return.
+      if (has_system && has_cache) {
+        // We want the cache if the checksum matches, otherwise the system.
+        std::unique_ptr<ImageHeader> system(ReadSpecificImageHeaderOrDie(system_filename.c_str()));
+        std::unique_ptr<ImageHeader> cache(ReadSpecificImageHeaderOrDie(cache_filename.c_str()));
+        if (system.get() == nullptr ||
+            (cache.get() != nullptr && cache->GetOatChecksum() == system->GetOatChecksum())) {
+          return cache.release();
+        } else {
+          return system.release();
+        }
+      } else if (has_system) {
+        return ReadSpecificImageHeaderOrDie(system_filename.c_str());
+      } else if (has_cache) {
+        return ReadSpecificImageHeaderOrDie(cache_filename.c_str());
+      }
     }
-
-    return image_header.release();
   }
 
   LOG(FATAL) << "Unable to find image file for: " << image_location;
   return nullptr;
 }
 
+static bool ChecksumsMatch(const char* image_a, const char* image_b) {
+  ImageHeader hdr_a;
+  ImageHeader hdr_b;
+  return ReadSpecificImageHeader(image_a, &hdr_a) && ReadSpecificImageHeader(image_b, &hdr_b)
+      && hdr_a.GetOatChecksum() == hdr_b.GetOatChecksum();
+}
+
 ImageSpace* ImageSpace::Create(const char* image_location,
                                const InstructionSet image_isa) {
-  std::string image_filename;
   std::string error_msg;
-  bool is_system = false;
-  const bool found_image = FindImageFilename(image_location, image_isa, &image_filename,
-                                             &is_system);
+  std::string system_filename;
+  bool has_system = false;
+  std::string cache_filename;
+  bool has_cache = false;
+  bool dalvik_cache_exists = false;
+  const bool found_image = FindImageFilename(image_location, image_isa, &system_filename,
+                                             &has_system, &cache_filename, &dalvik_cache_exists,
+                                             &has_cache);
 
-  // Note that we must not use the file descriptor associated with
-  // ScopedFlock::GetFile to Init the image file. We want the file
-  // descriptor (and the associated exclusive lock) to be released when
-  // we leave Create.
-  ScopedFlock image_lock;
-  image_lock.Init(image_filename.c_str(), &error_msg);
-
+  ImageSpace* space;
+  bool relocate = Runtime::Current()->ShouldRelocate();
   if (found_image) {
-    ImageSpace* space = ImageSpace::Init(image_filename.c_str(), image_location, !is_system,
-                                         &error_msg);
+    const std::string* image_filename;
+    bool is_system = false;
+    bool relocated_version_used = false;
+    if (relocate) {
+      CHECK(dalvik_cache_exists) << "Requiring relocation for image " << image_location << " "
+                                 << "at " << system_filename << " but we do not have any "
+                                 << "dalvik_cache to find/place it in.";
+      if (has_system) {
+        if (has_cache && ChecksumsMatch(system_filename.c_str(), cache_filename.c_str())) {
+          // We already have a relocated version
+          image_filename = &cache_filename;
+          relocated_version_used = true;
+        } else {
+          // We cannot have a relocated version, Relocate the system one and use it.
+          if (RelocateImage(image_location, cache_filename.c_str(), image_isa,
+                            &error_msg)) {
+            relocated_version_used = true;
+            image_filename = &cache_filename;
+          } else {
+            LOG(FATAL) << "Unable to relocate image " << image_location << " "
+                       << "from " << system_filename << " to " << cache_filename << ": "
+                       << error_msg;
+            return nullptr;
+          }
+        }
+      } else {
+        CHECK(has_cache);
+        // We can just use cache's since it should be fine. This might or might not be relocated.
+        image_filename = &cache_filename;
+      }
+    } else {
+      if (has_system && has_cache) {
+        // Check they have the same cksum. If they do use the cache. Otherwise system.
+        if (ChecksumsMatch(system_filename.c_str(), cache_filename.c_str())) {
+          image_filename = &cache_filename;
+          relocated_version_used = true;
+        } else {
+          image_filename = &system_filename;
+        }
+      } else if (has_system) {
+        image_filename = &system_filename;
+      } else {
+        CHECK(has_cache);
+        image_filename = &cache_filename;
+      }
+    }
+    {
+      // Note that we must not use the file descriptor associated with
+      // ScopedFlock::GetFile to Init the image file. We want the file
+      // descriptor (and the associated exclusive lock) to be released when
+      // we leave Create.
+      ScopedFlock image_lock;
+      image_lock.Init(image_filename->c_str(), &error_msg);
+      LOG(INFO) << "Using image file " << image_filename->c_str() << " for image location "
+                << image_location;
+      space = ImageSpace::Init(image_filename->c_str(), image_location,
+                               false, &error_msg);
+    }
     if (space != nullptr) {
       return space;
     }
 
-    // If the /system file exists, it should be up-to-date, don't try to generate it.
-    // If it's not the /system file, log a warning and fall through to GenerateImage.
-    if (is_system) {
-      LOG(FATAL) << "Failed to load image '" << image_filename << "': " << error_msg;
+    // If the /system file exists, it should be up-to-date, don't try to generate it. Same if it is
+    // a relocated copy from something in /system (i.e. checksum's match).
+    // Otherwise, log a warning and fall through to GenerateImage.
+    if (relocated_version_used) {
+      LOG(FATAL) << "Attempted to use relocated version of " << image_location << " "
+                 << "at " << cache_filename << " generated from " << system_filename << " "
+                 << "but image failed to load: " << error_msg;
+      return nullptr;
+    } else if (is_system) {
+      LOG(FATAL) << "Failed to load /system image '" << *image_filename << "': " << error_msg;
       return nullptr;
     } else {
       LOG(WARNING) << error_msg;
     }
   }
 
-  CHECK(GenerateImage(image_filename, &error_msg))
-      << "Failed to generate image '" << image_filename << "': " << error_msg;
-  ImageSpace* space = ImageSpace::Init(image_filename.c_str(), image_location, true, &error_msg);
+  CHECK(dalvik_cache_exists) << "No place to put generated image.";
+  CHECK(GenerateImage(cache_filename, &error_msg))
+      << "Failed to generate image '" << cache_filename << "': " << error_msg;
+  // TODO Should I relocate this image? Sure
+  if (relocate) {
+    if (!RelocateImage(cache_filename.c_str(), cache_filename.c_str(), image_isa, &error_msg)) {
+      LOG(FATAL) << "Failed to relocate newly created image " << cache_filename.c_str();
+      return nullptr;
+    }
+  }
+  {
+    // Note that we must not use the file descriptor associated with
+    // ScopedFlock::GetFile to Init the image file. We want the file
+    // descriptor (and the associated exclusive lock) to be released when
+    // we leave Create.
+    ScopedFlock image_lock;
+    image_lock.Init(cache_filename.c_str(), &error_msg);
+    space = ImageSpace::Init(cache_filename.c_str(), image_location, true, &error_msg);
+  }
   if (space == nullptr) {
-    LOG(FATAL) << "Failed to load image '" << image_filename << "': " << error_msg;
+    LOG(FATAL) << "Failed to load generated image '" << cache_filename << "': " << error_msg;
   }
   return space;
 }
@@ -316,6 +536,15 @@
                               " in image %s", oat_checksum, image_oat_checksum, GetName());
     return nullptr;
   }
+  int32_t image_patch_delta = image_header.GetPatchDelta();
+  int32_t oat_patch_delta = oat_file->GetOatHeader().GetImagePatchDelta();
+  if (oat_patch_delta != image_patch_delta) {
+    // We should have already relocated by this point. Bail out.
+    *error_msg = StringPrintf("Failed to match oat file patch delta %d to expected patch delta %d "
+                              "in image %s", oat_patch_delta, image_patch_delta, GetName());
+    return nullptr;
+  }
+
   return oat_file;
 }
 
diff --git a/runtime/gc/space/image_space.h b/runtime/gc/space/image_space.h
index dd9b580..debca52 100644
--- a/runtime/gc/space/image_space.h
+++ b/runtime/gc/space/image_space.h
@@ -98,6 +98,20 @@
     return false;
   }
 
+  // Returns the filename of the image corresponding to
+  // requested image_location, or the filename where a new image
+  // should be written if one doesn't exist. Looks for a generated
+  // image in the specified location and then in the dalvik-cache.
+  //
+  // Returns true if an image was found, false otherwise.
+  static bool FindImageFilename(const char* image_location,
+                                InstructionSet image_isa,
+                                std::string* system_location,
+                                bool* has_system,
+                                std::string* data_location,
+                                bool* dalvik_cache_exists,
+                                bool* has_data);
+
  private:
   // Tries to initialize an ImageSpace from the given image path,
   // returning NULL on error.
@@ -110,16 +124,8 @@
                           bool validate_oat_file, std::string* error_msg)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  // Returns the filename of the image corresponding to
-  // requested image_location, or the filename where a new image
-  // should be written if one doesn't exist. Looks for a generated
-  // image in the specified location and then in the dalvik-cache.
-  //
-  // Returns true if an image was found, false otherwise.
-  static bool FindImageFilename(const char* image_location,
-                                InstructionSet image_isa,
-                                std::string* location,
-                                bool* is_system);
+  static bool RelocateImage(const char* image_location, const char* dest_filename,
+                            InstructionSet isa, std::string* error_msg);
 
   OatFile* OpenOatFile(const char* image, std::string* error_msg) const
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
diff --git a/runtime/indirect_reference_table.cc b/runtime/indirect_reference_table.cc
index ad798ed..26ddba2 100644
--- a/runtime/indirect_reference_table.cc
+++ b/runtime/indirect_reference_table.cc
@@ -74,6 +74,7 @@
   table_mem_map_.reset(MemMap::MapAnonymous("indirect ref table", nullptr, table_bytes,
                                             PROT_READ | PROT_WRITE, false, &error_str));
   CHECK(table_mem_map_.get() != nullptr) << error_str;
+  CHECK_EQ(table_mem_map_->Size(), table_bytes);
 
   table_ = reinterpret_cast<mirror::Object**>(table_mem_map_->Begin());
   CHECK(table_ != nullptr);
diff --git a/runtime/noop_compiler_callbacks.h b/runtime/noop_compiler_callbacks.h
index 65498de..e9ad353 100644
--- a/runtime/noop_compiler_callbacks.h
+++ b/runtime/noop_compiler_callbacks.h
@@ -32,6 +32,11 @@
 
   void ClassRejected(ClassReference ref) OVERRIDE {}
 
+  // This is only used by compilers which need to be able to run without relocation even when it
+  // would normally be enabled. For example the patchoat executable, and dex2oat --image, both need
+  // to disable the relocation since both deal with writing out the images directly.
+  bool IsRelocationPossible() OVERRIDE { return false; }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(NoopCompilerCallbacks);
 };
diff --git a/runtime/oat.cc b/runtime/oat.cc
index 1421baf..0a8c35b 100644
--- a/runtime/oat.cc
+++ b/runtime/oat.cc
@@ -23,7 +23,7 @@
 namespace art {
 
 const uint8_t OatHeader::kOatMagic[] = { 'o', 'a', 't', '\n' };
-const uint8_t OatHeader::kOatVersion[] = { '0', '3', '7', '\0' };
+const uint8_t OatHeader::kOatVersion[] = { '0', '3', '8', '\0' };
 
 static size_t ComputeOatHeaderSize(const SafeMap<std::string, std::string>* variable_data) {
   size_t estimate = 0U;
@@ -67,6 +67,8 @@
                      const SafeMap<std::string, std::string>* variable_data) {
   memcpy(magic_, kOatMagic, sizeof(kOatMagic));
   memcpy(version_, kOatVersion, sizeof(kOatVersion));
+  executable_offset_ = 0;
+  image_patch_delta_ = 0;
 
   adler32_checksum_ = adler32(0L, Z_NULL, 0);
 
@@ -98,7 +100,6 @@
     UpdateChecksum(&key_value_store_, key_value_store_size_);
   }
 
-  executable_offset_ = 0;
   interpreter_to_interpreter_bridge_offset_ = 0;
   interpreter_to_compiled_code_bridge_offset_ = 0;
   jni_dlsym_lookup_offset_ = 0;
@@ -118,6 +119,12 @@
   if (memcmp(version_, kOatVersion, sizeof(kOatVersion)) != 0) {
     return false;
   }
+  if (!IsAligned<kPageSize>(executable_offset_)) {
+    return false;
+  }
+  if (!IsAligned<kPageSize>(image_patch_delta_)) {
+    return false;
+  }
   return true;
 }
 
@@ -355,6 +362,26 @@
   UpdateChecksum(&quick_to_interpreter_bridge_offset_, sizeof(offset));
 }
 
+int32_t OatHeader::GetImagePatchDelta() const {
+  CHECK(IsValid());
+  return image_patch_delta_;
+}
+
+void OatHeader::RelocateOat(off_t delta) {
+  CHECK(IsValid());
+  CHECK_ALIGNED(delta, kPageSize);
+  image_patch_delta_ += delta;
+  if (image_file_location_oat_data_begin_ != 0) {
+    image_file_location_oat_data_begin_ += delta;
+  }
+}
+
+void OatHeader::SetImagePatchDelta(int32_t off) {
+  CHECK(IsValid());
+  CHECK_ALIGNED(off, kPageSize);
+  image_patch_delta_ = off;
+}
+
 uint32_t OatHeader::GetImageFileLocationOatChecksum() const {
   CHECK(IsValid());
   return image_file_location_oat_checksum_;
diff --git a/runtime/oat.h b/runtime/oat.h
index fbed596..6d5fefe 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -88,6 +88,10 @@
   uint32_t GetQuickToInterpreterBridgeOffset() const;
   void SetQuickToInterpreterBridgeOffset(uint32_t offset);
 
+  int32_t GetImagePatchDelta() const;
+  void RelocateOat(off_t delta);
+  void SetImagePatchDelta(int32_t off);
+
   InstructionSet GetInstructionSet() const;
   const InstructionSetFeatures& GetInstructionSetFeatures() const;
   uint32_t GetImageFileLocationOatChecksum() const;
@@ -129,6 +133,9 @@
   uint32_t quick_resolution_trampoline_offset_;
   uint32_t quick_to_interpreter_bridge_offset_;
 
+  // The amount that the image this oat is associated with has been patched.
+  int32_t image_patch_delta_;
+
   uint32_t image_file_location_oat_checksum_;
   uint32_t image_file_location_oat_data_begin_;
 
diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc
index 86c1bae..f9cc36a 100644
--- a/runtime/oat_file.cc
+++ b/runtime/oat_file.cc
@@ -87,6 +87,11 @@
   return OpenElfFile(file, location, NULL, true, false, error_msg);
 }
 
+OatFile* OatFile::OpenReadable(File* file, const std::string& location, std::string* error_msg) {
+  CheckLocation(location);
+  return OpenElfFile(file, location, NULL, false, false, error_msg);
+}
+
 OatFile* OatFile::OpenDlopen(const std::string& elf_filename,
                              const std::string& location,
                              byte* requested_base,
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index 44f4466..3ec2e84 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -52,6 +52,8 @@
   // ImageWriter which wants to open a writable version from an existing
   // file descriptor for patching.
   static OatFile* OpenWritable(File* file, const std::string& location, std::string* error_msg);
+  // Opens an oat file from an already opened File. Maps it PROT_READ, MAP_PRIVATE.
+  static OatFile* OpenReadable(File* file, const std::string& location, std::string* error_msg);
 
   // Open an oat file backed by a std::vector with the given location.
   static OatFile* OpenMemory(std::vector<uint8_t>& oat_contents,
diff --git a/runtime/parsed_options.cc b/runtime/parsed_options.cc
index 9a1d0f7..8d0aff8 100644
--- a/runtime/parsed_options.cc
+++ b/runtime/parsed_options.cc
@@ -221,6 +221,7 @@
 
   compiler_callbacks_ = nullptr;
   is_zygote_ = false;
+  must_relocate_ = kDefaultMustRelocate;
   if (kPoisonHeapReferences) {
     // kPoisonHeapReferences currently works only with the interpreter only.
     // TODO: make it work with the compiler.
@@ -390,6 +391,7 @@
       ignore_max_footprint_ = true;
     } else if (option == "-XX:LowMemoryMode") {
       low_memory_mode_ = true;
+      // TODO Might want to turn off must_relocate here.
     } else if (option == "-XX:UseTLAB") {
       use_tlab_ = true;
     } else if (option == "-XX:EnableHSpaceCompactForOOM") {
@@ -408,6 +410,14 @@
           reinterpret_cast<const char*>(options[i].second));
     } else if (option == "-Xzygote") {
       is_zygote_ = true;
+    } else if (StartsWith(option, "-Xpatchoat:")) {
+      if (!ParseStringAfterChar(option, ':', &patchoat_executable_)) {
+        return false;
+      }
+    } else if (option == "-Xrelocate") {
+      must_relocate_ = true;
+    } else if (option == "-Xnorelocate") {
+      must_relocate_ = false;
     } else if (option == "-Xint") {
       interpreter_only_ = true;
     } else if (StartsWith(option, "-Xgc:")) {
@@ -758,6 +768,8 @@
   UsageMessage(stream, "  -Xcompiler:filename\n");
   UsageMessage(stream, "  -Xcompiler-option dex2oat-option\n");
   UsageMessage(stream, "  -Ximage-compiler-option dex2oat-option\n");
+  UsageMessage(stream, "  -Xpatchoat:filename\n");
+  UsageMessage(stream, "  -X[no]relocate\n");
   UsageMessage(stream, "\n");
 
   UsageMessage(stream, "The following previously supported Dalvik options are ignored:\n");
diff --git a/runtime/parsed_options.h b/runtime/parsed_options.h
index 23f2bcf..29d5494 100644
--- a/runtime/parsed_options.h
+++ b/runtime/parsed_options.h
@@ -47,6 +47,10 @@
   std::string jni_trace_;
   CompilerCallbacks* compiler_callbacks_;
   bool is_zygote_;
+  // TODO Change this to true when we want it on by default.
+  static constexpr bool kDefaultMustRelocate = false;
+  bool must_relocate_;
+  std::string patchoat_executable_;
   bool interpreter_only_;
   bool is_explicit_gc_disabled_;
   bool use_tlab_;
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 0398365..b7eae85 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -101,6 +101,7 @@
       instruction_set_(kNone),
       compiler_callbacks_(nullptr),
       is_zygote_(false),
+      must_relocate_(false),
       is_concurrent_gc_enabled_(true),
       is_explicit_gc_disabled_(false),
       default_stack_size_(0),
@@ -385,6 +386,15 @@
   return env->NewGlobalRef(system_class_loader.get());
 }
 
+std::string Runtime::GetPatchoatExecutable() const {
+  if (!patchoat_executable_.empty()) {
+    return patchoat_executable_;
+  }
+  std::string patchoat_executable_(GetAndroidRoot());
+  patchoat_executable_ += (kIsDebugBuild ? "/bin/patchoatd" : "/bin/patchoat");
+  return patchoat_executable_;
+}
+
 std::string Runtime::GetCompilerExecutable() const {
   if (!compiler_executable_.empty()) {
     return compiler_executable_;
@@ -557,6 +567,8 @@
   properties_ = options->properties_;
 
   compiler_callbacks_ = options->compiler_callbacks_;
+  patchoat_executable_ = options->patchoat_executable_;
+  must_relocate_ = options->must_relocate_;
   is_zygote_ = options->is_zygote_;
   is_explicit_gc_disabled_ = options->is_explicit_gc_disabled_;
 
diff --git a/runtime/runtime.h b/runtime/runtime.h
index 6a5fe75..c81e36a 100644
--- a/runtime/runtime.h
+++ b/runtime/runtime.h
@@ -26,6 +26,7 @@
 #include <utility>
 #include <vector>
 
+#include "compiler_callbacks.h"
 #include "instrumentation.h"
 #include "instruction_set.h"
 #include "jobject_comparator.h"
@@ -55,7 +56,6 @@
 class MethodVerifier;
 }
 class ClassLinker;
-class CompilerCallbacks;
 class DexFile;
 class InternTable;
 class JavaVMExt;
@@ -92,6 +92,18 @@
     return compiler_callbacks_ != nullptr;
   }
 
+  bool CanRelocate() const {
+    return !IsCompiler() || compiler_callbacks_->IsRelocationPossible();
+  }
+
+  bool ShouldRelocate() const {
+    return must_relocate_ && CanRelocate();
+  }
+
+  bool MustRelocateIfPossible() const {
+    return must_relocate_;
+  }
+
   CompilerCallbacks* GetCompilerCallbacks() {
     return compiler_callbacks_;
   }
@@ -105,6 +117,7 @@
   }
 
   std::string GetCompilerExecutable() const;
+  std::string GetPatchoatExecutable() const;
 
   const std::vector<std::string>& GetCompilerOptions() const {
     return compiler_options_;
@@ -486,10 +499,12 @@
 
   CompilerCallbacks* compiler_callbacks_;
   bool is_zygote_;
+  bool must_relocate_;
   bool is_concurrent_gc_enabled_;
   bool is_explicit_gc_disabled_;
 
   std::string compiler_executable_;
+  std::string patchoat_executable_;
   std::vector<std::string> compiler_options_;
   std::vector<std::string> image_compiler_options_;
 
diff --git a/runtime/utils.cc b/runtime/utils.cc
index 8b1ad39..52cdcc1 100644
--- a/runtime/utils.cc
+++ b/runtime/utils.cc
@@ -1154,22 +1154,55 @@
 }
 
 const char* GetAndroidData() {
+  std::string error_msg;
+  const char* dir = GetAndroidDataSafe(&error_msg);
+  if (dir != nullptr) {
+    return dir;
+  } else {
+    LOG(FATAL) << error_msg;
+    return "";
+  }
+}
+
+const char* GetAndroidDataSafe(std::string* error_msg) {
   const char* android_data = getenv("ANDROID_DATA");
   if (android_data == NULL) {
     if (OS::DirectoryExists("/data")) {
       android_data = "/data";
     } else {
-      LOG(FATAL) << "ANDROID_DATA not set and /data does not exist";
-      return "";
+      *error_msg = "ANDROID_DATA not set and /data does not exist";
+      return nullptr;
     }
   }
   if (!OS::DirectoryExists(android_data)) {
-    LOG(FATAL) << "Failed to find ANDROID_DATA directory " << android_data;
-    return "";
+    *error_msg = StringPrintf("Failed to find ANDROID_DATA directory %s", android_data);
+    return nullptr;
   }
   return android_data;
 }
 
+void GetDalvikCache(const char* subdir, const bool create_if_absent, std::string* dalvik_cache,
+                    bool* have_android_data, bool* dalvik_cache_exists) {
+  CHECK(subdir != nullptr);
+  std::string error_msg;
+  const char* android_data = GetAndroidDataSafe(&error_msg);
+  if (android_data == nullptr) {
+    *have_android_data = false;
+    *dalvik_cache_exists = false;
+    return;
+  } else {
+    *have_android_data = true;
+  }
+  const std::string dalvik_cache_root(StringPrintf("%s/dalvik-cache/", android_data));
+  *dalvik_cache = dalvik_cache_root + subdir;
+  *dalvik_cache_exists = OS::DirectoryExists(dalvik_cache->c_str());
+  if (create_if_absent && !*dalvik_cache_exists && strcmp(android_data, "/data") != 0) {
+    // Don't create the system's /data/dalvik-cache/... because it needs special permissions.
+    *dalvik_cache_exists = ((mkdir(dalvik_cache_root.c_str(), 0700) == 0 || errno == EEXIST) &&
+                            (mkdir(dalvik_cache->c_str(), 0700) == 0 || errno == EEXIST));
+  }
+}
+
 std::string GetDalvikCacheOrDie(const char* subdir, const bool create_if_absent) {
   CHECK(subdir != nullptr);
   const char* android_data = GetAndroidData();
@@ -1196,9 +1229,11 @@
   return dalvik_cache;
 }
 
-std::string GetDalvikCacheFilenameOrDie(const char* location, const char* cache_location) {
+bool GetDalvikCacheFilename(const char* location, const char* cache_location,
+                            std::string* filename, std::string* error_msg) {
   if (location[0] != '/') {
-    LOG(FATAL) << "Expected path in location to be absolute: "<< location;
+    *error_msg = StringPrintf("Expected path in location to be absolute: %s", location);
+    return false;
   }
   std::string cache_file(&location[1]);  // skip leading slash
   if (!EndsWith(location, ".dex") && !EndsWith(location, ".art")) {
@@ -1206,7 +1241,17 @@
     cache_file += DexFile::kClassesDex;
   }
   std::replace(cache_file.begin(), cache_file.end(), '/', '@');
-  return StringPrintf("%s/%s", cache_location, cache_file.c_str());
+  *filename = StringPrintf("%s/%s", cache_location, cache_file.c_str());
+  return true;
+}
+
+std::string GetDalvikCacheFilenameOrDie(const char* location, const char* cache_location) {
+  std::string ret;
+  std::string error_msg;
+  if (!GetDalvikCacheFilename(location, cache_location, &ret, &error_msg)) {
+    LOG(FATAL) << error_msg;
+  }
+  return ret;
 }
 
 static void InsertIsaDirectory(const InstructionSet isa, std::string* filename) {
diff --git a/runtime/utils.h b/runtime/utils.h
index c920050..73872d3 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -439,11 +439,22 @@
 
 // Find $ANDROID_DATA, /data, or abort.
 const char* GetAndroidData();
+// Find $ANDROID_DATA, /data, or return nullptr.
+const char* GetAndroidDataSafe(std::string* error_msg);
 
 // Returns the dalvik-cache location, or dies trying. subdir will be
 // appended to the cache location.
 std::string GetDalvikCacheOrDie(const char* subdir, bool create_if_absent = true);
+// Return true if we found the dalvik cache and stored it in the dalvik_cache argument.
+// have_android_data will be set to true if we have an ANDROID_DATA that exists,
+// dalvik_cache_exists will be true if there is a dalvik-cache directory that is present.
+void GetDalvikCache(const char* subdir, bool create_if_absent, std::string* dalvik_cache,
+                    bool* have_android_data, bool* dalvik_cache_exists);
 
+// Returns the absolute dalvik-cache path for a DexFile or OatFile. The path returned will be
+// rooted at cache_location.
+bool GetDalvikCacheFilename(const char* file_location, const char* cache_location,
+                            std::string* filename, std::string* error_msg);
 // Returns the absolute dalvik-cache path for a DexFile or OatFile, or
 // dies trying. The path returned will be rooted at cache_location.
 std::string GetDalvikCacheFilenameOrDie(const char* file_location,