Deduplicate interned image strings.

Also fix a bug in relocation; even for -Xnorelocate we need
to relocate second and later extension if it's not compiled
against all previous boot image components.

Also clean up InternTable includes.

Test: New tests in image_space_test.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Test: aosp_taimen-userdebug boots.
Bug: 152037801
Change-Id: Ie6ae70721f4ffb48950bd248ffa123dee460bcd7

15 files changed, 664 insertions, 218 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 86e949457e..b3cac26374 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -30,6 +30,8 @@ GTEST_DEX_DIRECTORIES := \
   ErroneousA \
   ErroneousB \
   ErroneousInit \
+  Extension1 \
+  Extension2 \
   ForClassLoaderA \
   ForClassLoaderB \
   ForClassLoaderC \
@@ -227,7 +229,7 @@ ART_GTEST_jni_compiler_test_DEX_DEPS := MyClassNatives
 ART_GTEST_jni_internal_test_DEX_DEPS := AllFields StaticLeafMethods MyClassNatives
 ART_GTEST_oat_file_assistant_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS)
 ART_GTEST_dexoptanalyzer_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS)
-ART_GTEST_image_space_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS)
+ART_GTEST_image_space_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS) Extension1 Extension2
 ART_GTEST_oat_file_test_DEX_DEPS := Main MultiDex MainUncompressedAligned MultiDexUncompressedAligned MainStripped Nested MultiDexModifiedSecondary
 ART_GTEST_oat_test_DEX_DEPS := Main
 ART_GTEST_oat_writer_test_DEX_DEPS := Main
diff --git a/dex2oat/dex2oat_image_test.cc b/dex2oat/dex2oat_image_test.cc
index 9fd632f0c2..d01b64f639 100644
--- a/dex2oat/dex2oat_image_test.cc
+++ b/dex2oat/dex2oat_image_test.cc
@@ -41,8 +41,8 @@
 #include "dex/dex_file-inl.h"
 #include "dex/dex_file_loader.h"
 #include "dex/method_reference.h"
+#include "dex/type_reference.h"
 #include "gc/space/image_space.h"
-#include "profile/profile_compilation_info.h"
 #include "runtime.h"
 #include "scoped_thread_state_change-inl.h"
 #include "thread-current-inl.h"
@@ -73,89 +73,11 @@ class Dex2oatImageTest : public CommonRuntimeTest {
     options->emplace_back("-Xnoimage-dex2oat", nullptr);
   }
 
-  // Visitors take method and type references
-  template <typename MethodVisitor, typename ClassVisitor>
-  void VisitLibcoreDexes(const MethodVisitor& method_visitor,
-                         const ClassVisitor& class_visitor,
-                         size_t method_frequency = 1,
-                         size_t class_frequency = 1) {
-    std::vector<std::string> dexes = GetLibCoreDexFileNames();
-    ArrayRef<const std::string> dexes_array(dexes);
-    VisitDexes(dexes_array, method_visitor, class_visitor, method_frequency, class_frequency);
-  }
-
-  // Visitors take method and type references
-  template <typename MethodVisitor, typename ClassVisitor>
-  void VisitDexes(ArrayRef<const std::string> dexes,
-                  const MethodVisitor& method_visitor,
-                  const ClassVisitor& class_visitor,
-                  size_t method_frequency = 1,
-                  size_t class_frequency = 1) {
-    size_t method_counter = 0;
-    size_t class_counter = 0;
-    for (const std::string& dex : dexes) {
-      std::vector<std::unique_ptr<const DexFile>> dex_files;
-      std::string error_msg;
-      const ArtDexFileLoader dex_file_loader;
-      CHECK(dex_file_loader.Open(dex.c_str(),
-                                 dex,
-                                 /*verify*/ true,
-                                 /*verify_checksum*/ false,
-                                 &error_msg,
-                                 &dex_files))
-          << error_msg;
-      for (const std::unique_ptr<const DexFile>& dex_file : dex_files) {
-        for (size_t i = 0; i < dex_file->NumMethodIds(); ++i) {
-          if (++method_counter % method_frequency == 0) {
-            method_visitor(MethodReference(dex_file.get(), i));
-          }
-        }
-        for (size_t i = 0; i < dex_file->NumTypeIds(); ++i) {
-          if (++class_counter % class_frequency == 0) {
-            class_visitor(TypeReference(dex_file.get(), dex::TypeIndex(i)));
-          }
-        }
-      }
-    }
-  }
-
   static void WriteLine(File* file, std::string line) {
     line += '\n';
     EXPECT_TRUE(file->WriteFully(&line[0], line.length()));
   }
 
-  void GenerateProfile(ArrayRef<const std::string> dexes,
-                       File* out_file,
-                       size_t method_frequency,
-                       size_t type_frequency) {
-    ProfileCompilationInfo profile;
-    VisitDexes(
-        dexes,
-        [&profile](MethodReference ref) {
-          uint32_t flags = ProfileCompilationInfo::MethodHotness::kFlagHot |
-              ProfileCompilationInfo::MethodHotness::kFlagStartup;
-          EXPECT_TRUE(profile.AddMethod(
-              ProfileMethodInfo(ref),
-              static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags)));
-        },
-        [&profile](TypeReference ref) {
-          std::set<dex::TypeIndex> classes;
-          classes.insert(ref.TypeIndex());
-          EXPECT_TRUE(profile.AddClassesForDex(ref.dex_file, classes.begin(), classes.end()));
-        },
-        method_frequency,
-        type_frequency);
-    profile.Save(out_file->Fd());
-    EXPECT_EQ(out_file->Flush(), 0);
-  }
-
-  void GenerateMethods(File* out_file, size_t frequency = 1) {
-    VisitLibcoreDexes([out_file](MethodReference ref) {
-      WriteLine(out_file, ref.PrettyMethod());
-    }, VoidFunctor(), frequency, frequency);
-    EXPECT_EQ(out_file->Flush(), 0);
-  }
-
   void AddRuntimeArg(std::vector<std::string>& args, const std::string& arg) {
     args.push_back("--runtime-arg");
     args.push_back(arg);
@@ -316,8 +238,9 @@ TEST_F(Dex2oatImageTest, TestModesAndFilters) {
   // Test dirty image objects.
   {
     ScratchFile classes;
-    VisitLibcoreDexes(VoidFunctor(),
-                      [&](TypeReference ref) {
+    VisitDexes(libcore_dexes_array,
+               VoidFunctor(),
+               [&](TypeReference ref) {
       WriteLine(classes.GetFile(), ref.dex_file->PrettyType(ref.TypeIndex()));
     }, /*method_frequency=*/ 1u, /*class_frequency=*/ 1u);
     ImageSizes image_classes_sizes = CompileImageAndGetSizes(
diff --git a/dex2oat/linker/image_writer.h b/dex2oat/linker/image_writer.h
index 22fd8f48ca..769f2ff319 100644
--- a/dex2oat/linker/image_writer.h
+++ b/dex2oat/linker/image_writer.h
@@ -27,6 +27,7 @@
 #include <stack>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 
 #include "art_method.h"
 #include "base/bit_utils.h"
diff --git a/libartbase/base/common_art_test.h b/libartbase/base/common_art_test.h
index 8d2693f784..8cd25c343f 100644
--- a/libartbase/base/common_art_test.h
+++ b/libartbase/base/common_art_test.h
@@ -28,6 +28,7 @@
 
 #include "base/file_utils.h"
 #include "base/globals.h"
+#include "base/memory_tool.h"
 #include "base/mutex.h"
 #include "base/os.h"
 #include "base/unix_file/fd_file.h"
diff --git a/runtime/common_runtime_test.cc b/runtime/common_runtime_test.cc
index 640e182dbd..a846346edd 100644
--- a/runtime/common_runtime_test.cc
+++ b/runtime/common_runtime_test.cc
@@ -41,7 +41,9 @@
 #include "dex/art_dex_file_loader.h"
 #include "dex/dex_file-inl.h"
 #include "dex/dex_file_loader.h"
+#include "dex/method_reference.h"
 #include "dex/primitive.h"
+#include "dex/type_reference.h"
 #include "gc/heap.h"
 #include "gc/space/image_space.h"
 #include "gc_root-inl.h"
@@ -56,6 +58,7 @@
 #include "mirror/object_array-alloc-inl.h"
 #include "native/dalvik_system_DexFile.h"
 #include "noop_compiler_callbacks.h"
+#include "profile/profile_compilation_info.h"
 #include "runtime-inl.h"
 #include "scoped_thread_state_change-inl.h"
 #include "thread.h"
@@ -408,18 +411,16 @@ void CommonRuntimeTestImpl::MakeInterpreted(ObjPtr<mirror::Class> klass) {
 }
 
 bool CommonRuntimeTestImpl::StartDex2OatCommandLine(/*out*/std::vector<std::string>* argv,
-                                                    /*out*/std::string* error_msg) {
+                                                    /*out*/std::string* error_msg,
+                                                    bool use_runtime_bcp_and_image) {
   DCHECK(argv != nullptr);
   DCHECK(argv->empty());
 
   Runtime* runtime = Runtime::Current();
-  const std::vector<gc::space::ImageSpace*>& image_spaces =
-      runtime->GetHeap()->GetBootImageSpaces();
-  if (image_spaces.empty()) {
+  if (use_runtime_bcp_and_image && runtime->GetHeap()->GetBootImageSpaces().empty()) {
     *error_msg = "No image location found for Dex2Oat.";
     return false;
   }
-  std::string image_location = image_spaces[0]->GetImageLocation();
 
   argv->push_back(runtime->GetCompilerExecutable());
   if (runtime->IsJavaDebuggable()) {
@@ -427,12 +428,17 @@ bool CommonRuntimeTestImpl::StartDex2OatCommandLine(/*out*/std::vector<std::stri
   }
   runtime->AddCurrentRuntimeFeaturesAsDex2OatArguments(argv);
 
-  argv->push_back("--runtime-arg");
-  argv->push_back(GetClassPathOption("-Xbootclasspath:", GetLibCoreDexFileNames()));
-  argv->push_back("--runtime-arg");
-  argv->push_back(GetClassPathOption("-Xbootclasspath-locations:", GetLibCoreDexLocations()));
+  if (use_runtime_bcp_and_image) {
+    argv->push_back("--runtime-arg");
+    argv->push_back(GetClassPathOption("-Xbootclasspath:", GetLibCoreDexFileNames()));
+    argv->push_back("--runtime-arg");
+    argv->push_back(GetClassPathOption("-Xbootclasspath-locations:", GetLibCoreDexLocations()));
 
-  argv->push_back("--boot-image=" + image_location);
+    const std::vector<gc::space::ImageSpace*>& image_spaces =
+        runtime->GetHeap()->GetBootImageSpaces();
+    DCHECK(!image_spaces.empty());
+    argv->push_back("--boot-image=" + image_spaces[0]->GetImageLocation());
+  }
 
   std::vector<std::string> compiler_options = runtime->GetCompilerOptions();
   argv->insert(argv->end(), compiler_options.begin(), compiler_options.end());
@@ -560,6 +566,64 @@ bool CommonRuntimeTestImpl::IsTransactionAborted() {
   return Runtime::Current()->IsTransactionAborted();
 }
 
+void CommonRuntimeTestImpl::VisitDexes(ArrayRef<const std::string> dexes,
+                                       const std::function<void(MethodReference)>& method_visitor,
+                                       const std::function<void(TypeReference)>& class_visitor,
+                                       size_t method_frequency,
+                                       size_t class_frequency) {
+  size_t method_counter = 0;
+  size_t class_counter = 0;
+  for (const std::string& dex : dexes) {
+    std::vector<std::unique_ptr<const DexFile>> dex_files;
+    std::string error_msg;
+    const ArtDexFileLoader dex_file_loader;
+    CHECK(dex_file_loader.Open(dex.c_str(),
+                               dex,
+                               /*verify*/ true,
+                               /*verify_checksum*/ false,
+                               &error_msg,
+                               &dex_files))
+        << error_msg;
+    for (const std::unique_ptr<const DexFile>& dex_file : dex_files) {
+      for (size_t i = 0; i < dex_file->NumMethodIds(); ++i) {
+        if (++method_counter % method_frequency == 0) {
+          method_visitor(MethodReference(dex_file.get(), i));
+        }
+      }
+      for (size_t i = 0; i < dex_file->NumTypeIds(); ++i) {
+        if (++class_counter % class_frequency == 0) {
+          class_visitor(TypeReference(dex_file.get(), dex::TypeIndex(i)));
+        }
+      }
+    }
+  }
+}
+
+void CommonRuntimeTestImpl::GenerateProfile(ArrayRef<const std::string> dexes,
+                                            File* out_file,
+                                            size_t method_frequency,
+                                            size_t type_frequency) {
+  ProfileCompilationInfo profile;
+  VisitDexes(
+      dexes,
+      [&profile](MethodReference ref) {
+        uint32_t flags = ProfileCompilationInfo::MethodHotness::kFlagHot |
+            ProfileCompilationInfo::MethodHotness::kFlagStartup;
+        EXPECT_TRUE(profile.AddMethod(
+            ProfileMethodInfo(ref),
+            static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags)));
+      },
+      [&profile](TypeReference ref) {
+        std::set<dex::TypeIndex> classes;
+        classes.insert(ref.TypeIndex());
+        EXPECT_TRUE(profile.AddClassesForDex(ref.dex_file, classes.begin(), classes.end()));
+      },
+      method_frequency,
+      type_frequency);
+  profile.Save(out_file->Fd());
+  EXPECT_EQ(out_file->Flush(), 0);
+}
+
 CheckJniAbortCatcher::CheckJniAbortCatcher() : vm_(Runtime::Current()->GetJavaVM()) {
   vm_->SetCheckJniAbortHook(Hook, &actual_);
 }
diff --git a/runtime/common_runtime_test.h b/runtime/common_runtime_test.h
index 2dc8744834..711bc59cbe 100644
--- a/runtime/common_runtime_test.h
+++ b/runtime/common_runtime_test.h
@@ -20,6 +20,7 @@
 #include <gtest/gtest.h>
 #include <jni.h>
 
+#include <functional>
 #include <string>
 
 #include <android-base/logging.h>
@@ -38,6 +39,9 @@
 
 namespace art {
 
+class MethodReference;
+class TypeReference;
+
 using LogSeverity = android::base::LogSeverity;
 using ScopedLogSeverity = android::base::ScopedLogSeverity;
 
@@ -111,7 +115,8 @@ class CommonRuntimeTestImpl : public CommonArtTestImpl {
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   bool StartDex2OatCommandLine(/*out*/std::vector<std::string>* argv,
-                               /*out*/std::string* error_msg);
+                               /*out*/std::string* error_msg,
+                               bool use_runtime_bcp_and_image = true);
 
   bool CompileBootImage(const std::vector<std::string>& extra_args,
                         const std::string& image_file_name_prefix,
@@ -162,6 +167,17 @@ class CommonRuntimeTestImpl : public CommonArtTestImpl {
                                         jobject parent_loader,
                                         jobject shared_libraries = nullptr);
 
+  void VisitDexes(ArrayRef<const std::string> dexes,
+                  const std::function<void(MethodReference)>& method_visitor,
+                  const std::function<void(TypeReference)>& class_visitor,
+                  size_t method_frequency = 1u,
+                  size_t class_frequency = 1u);
+
+  void GenerateProfile(ArrayRef<const std::string> dexes,
+                       File* out_file,
+                       size_t method_frequency = 1u,
+                       size_t type_frequency = 1u);
+
   std::unique_ptr<Runtime> runtime_;
 
   // The class_linker_, java_lang_dex_file_, and boot_class_path_ are all
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index 147c6b474a..edec8a53f6 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -675,6 +675,52 @@ class ImageSpace::ClassTableVisitor final {
   ReferenceVisitor reference_visitor_;
 };
 
+class ImageSpace::RemapInternedStringsVisitor {
+ public:
+  explicit RemapInternedStringsVisitor(SafeMap<mirror::String*, mirror::String*> intern_remap)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      : intern_remap_(std::move(intern_remap)),
+        string_class_(GetStringClass()) {}
+
+  // Visitor for VisitReferences().
+  ALWAYS_INLINE void operator()(ObjPtr<mirror::Object> object,
+                                MemberOffset field_offset,
+                                bool is_static ATTRIBUTE_UNUSED)
+      const REQUIRES_SHARED(Locks::mutator_lock_) {
+    ObjPtr<mirror::Object> old_value =
+        object->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(field_offset);
+    if (old_value != nullptr &&
+        old_value->GetClass<kVerifyNone, kWithoutReadBarrier>() == string_class_) {
+      auto it = intern_remap_.find(old_value->AsString().Ptr());
+      if (it != intern_remap_.end()) {
+        mirror::String* new_value = it->second;
+        object->SetFieldObjectWithoutWriteBarrier</*kTransactionActive=*/ false,
+                                                  /*kCheckTransaction=*/ true,
+                                                  kVerifyNone>(field_offset, new_value);
+      }
+    }
+  }
+  // Visitor for VisitReferences(), java.lang.ref.Reference case.
+  ALWAYS_INLINE void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    DCHECK(klass->IsTypeOfReferenceClass());
+    this->operator()(ref, mirror::Reference::ReferentOffset(), /*is_static=*/ false);
+  }
+  // Ignore class native roots; not called from VisitReferences() for kVisitNativeRoots == false.
+  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root ATTRIBUTE_UNUSED)
+      const {}
+  void VisitRoot(mirror::CompressedReference<mirror::Object>* root ATTRIBUTE_UNUSED) const {}
+
+ private:
+  mirror::Class* GetStringClass() REQUIRES_SHARED(Locks::mutator_lock_) {
+    DCHECK(!intern_remap_.empty());
+    return intern_remap_.begin()->first->GetClass<kVerifyNone, kWithoutReadBarrier>();
+  }
+
+  const SafeMap<mirror::String*, mirror::String*> intern_remap_;
+  mirror::Class* const string_class_;
+};
+
 // Helper class encapsulating loading, so we can access private ImageSpace members (this is a
 // nested class), but not declare functions in the header.
 class ImageSpace::Loader {
@@ -682,64 +728,91 @@ class ImageSpace::Loader {
   static std::unique_ptr<ImageSpace> InitAppImage(const char* image_filename,
                                                   const char* image_location,
                                                   const OatFile* oat_file,
-                                                  /*inout*/MemMap* image_reservation,
+                                                  ArrayRef<ImageSpace* const> boot_image_spaces,
                                                   /*out*/std::string* error_msg)
       REQUIRES_SHARED(Locks::mutator_lock_) {
     TimingLogger logger(__PRETTY_FUNCTION__, /*precise=*/ true, VLOG_IS_ON(image));
 
     std::unique_ptr<ImageSpace> space = Init(image_filename,
                                              image_location,
-                                             oat_file,
                                              &logger,
-                                             image_reservation,
+                                             /*image_reservation=*/ nullptr,
                                              error_msg);
     if (space != nullptr) {
-      uint32_t expected_reservation_size =
-          RoundUp(space->GetImageHeader().GetImageSize(), kPageSize);
+      space->oat_file_non_owned_ = oat_file;
+      const ImageHeader& image_header = space->GetImageHeader();
+
+      // Check the oat file checksum.
+      const uint32_t oat_checksum = oat_file->GetOatHeader().GetChecksum();
+      const uint32_t image_oat_checksum = image_header.GetOatChecksum();
+      if (oat_checksum != image_oat_checksum) {
+        *error_msg = StringPrintf("Oat checksum 0x%x does not match the image one 0x%x in image %s",
+                                  oat_checksum,
+                                  image_oat_checksum,
+                                  image_filename);
+        return nullptr;
+      }
+      size_t boot_image_space_dependencies;
+      if (!ValidateBootImageChecksum(image_filename,
+                                     image_header,
+                                     oat_file,
+                                     boot_image_spaces,
+                                     &boot_image_space_dependencies,
+                                     error_msg)) {
+        DCHECK(!error_msg->empty());
+        return nullptr;
+      }
+
+      uint32_t expected_reservation_size = RoundUp(image_header.GetImageSize(), kPageSize);
       if (!CheckImageReservationSize(*space, expected_reservation_size, error_msg) ||
           !CheckImageComponentCount(*space, /*expected_component_count=*/ 1u, error_msg)) {
         return nullptr;
       }
 
-      TimingLogger::ScopedTiming timing("RelocateImage", &logger);
-      ImageHeader* image_header = reinterpret_cast<ImageHeader*>(space->GetMemMap()->Begin());
-      const PointerSize pointer_size = image_header->GetPointerSize();
-      bool result;
-      if (pointer_size == PointerSize::k64) {
-        result = RelocateInPlace<PointerSize::k64>(*image_header,
-                                                   space->GetMemMap()->Begin(),
-                                                   space->GetLiveBitmap(),
-                                                   oat_file,
-                                                   error_msg);
-      } else {
-        result = RelocateInPlace<PointerSize::k32>(*image_header,
-                                                   space->GetMemMap()->Begin(),
-                                                   space->GetLiveBitmap(),
-                                                   oat_file,
-                                                   error_msg);
+      {
+        TimingLogger::ScopedTiming timing("RelocateImage", &logger);
+        const PointerSize pointer_size = image_header.GetPointerSize();
+        uint32_t boot_image_begin =
+            reinterpret_cast32<uint32_t>(boot_image_spaces.front()->Begin());
+        bool result;
+        if (pointer_size == PointerSize::k64) {
+          result = RelocateInPlace<PointerSize::k64>(boot_image_begin,
+                                                     space->GetMemMap()->Begin(),
+                                                     space->GetLiveBitmap(),
+                                                     oat_file,
+                                                     error_msg);
+        } else {
+          result = RelocateInPlace<PointerSize::k32>(boot_image_begin,
+                                                     space->GetMemMap()->Begin(),
+                                                     space->GetLiveBitmap(),
+                                                     oat_file,
+                                                     error_msg);
+        }
+        if (!result) {
+          return nullptr;
+        }
       }
-      if (!result) {
-        return nullptr;
+
+      DCHECK_LE(boot_image_space_dependencies, boot_image_spaces.size());
+      if (boot_image_space_dependencies != boot_image_spaces.size()) {
+        TimingLogger::ScopedTiming timing("DeduplicateInternedStrings", &logger);
+        // There shall be no duplicates with boot image spaces this app image depends on.
+        ArrayRef<ImageSpace* const> old_spaces =
+            boot_image_spaces.SubArray(/*pos=*/ boot_image_space_dependencies);
+        SafeMap<mirror::String*, mirror::String*> intern_remap;
+        RemoveInternTableDuplicates(old_spaces, space.get(), &intern_remap);
+        if (!intern_remap.empty()) {
+          RemapInternedStringDuplicates(std::move(intern_remap), space.get());
+        }
+      }
+
+      const ImageHeader& primary_header = boot_image_spaces.front()->GetImageHeader();
+      static_assert(static_cast<size_t>(ImageHeader::kResolutionMethod) == 0u);
+      for (size_t i = 0u; i != static_cast<size_t>(ImageHeader::kImageMethodsCount); ++i) {
+        ImageHeader::ImageMethod method = static_cast<ImageHeader::ImageMethod>(i);
+        CHECK_EQ(primary_header.GetImageMethod(method), image_header.GetImageMethod(method))
+            << method;
       }
-      Runtime* runtime = Runtime::Current();
-      CHECK_EQ(runtime->GetResolutionMethod(),
-               image_header->GetImageMethod(ImageHeader::kResolutionMethod));
-      CHECK_EQ(runtime->GetImtConflictMethod(),
-               image_header->GetImageMethod(ImageHeader::kImtConflictMethod));
-      CHECK_EQ(runtime->GetImtUnimplementedMethod(),
-               image_header->GetImageMethod(ImageHeader::kImtUnimplementedMethod));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveAllCalleeSaves),
-               image_header->GetImageMethod(ImageHeader::kSaveAllCalleeSavesMethod));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveRefsOnly),
-               image_header->GetImageMethod(ImageHeader::kSaveRefsOnlyMethod));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveRefsAndArgs),
-               image_header->GetImageMethod(ImageHeader::kSaveRefsAndArgsMethod));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveEverything),
-               image_header->GetImageMethod(ImageHeader::kSaveEverythingMethod));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveEverythingForClinit),
-               image_header->GetImageMethod(ImageHeader::kSaveEverythingMethodForClinit));
-      CHECK_EQ(runtime->GetCalleeSaveMethod(CalleeSaveType::kSaveEverythingForSuspendCheck),
-               image_header->GetImageMethod(ImageHeader::kSaveEverythingMethodForSuspendCheck));
 
       VLOG(image) << "ImageSpace::Loader::InitAppImage exiting " << *space.get();
     }
@@ -751,7 +824,6 @@ class ImageSpace::Loader {
 
   static std::unique_ptr<ImageSpace> Init(const char* image_filename,
                                           const char* image_location,
-                                          const OatFile* oat_file,
                                           TimingLogger* logger,
                                           /*inout*/MemMap* image_reservation,
                                           /*out*/std::string* error_msg)
@@ -772,7 +844,6 @@ class ImageSpace::Loader {
                 image_filename,
                 image_location,
                 /* profile_file=*/ "",
-                oat_file,
                 /*allow_direct_mapping=*/ true,
                 logger,
                 image_reservation,
@@ -783,7 +854,6 @@ class ImageSpace::Loader {
                                           const char* image_filename,
                                           const char* image_location,
                                           const char* profile_file,
-                                          const OatFile* oat_file,
                                           bool allow_direct_mapping,
                                           TimingLogger* logger,
                                           /*inout*/MemMap* image_reservation,
@@ -794,60 +864,41 @@ class ImageSpace::Loader {
 
     VLOG(image) << "ImageSpace::Init entering image_filename=" << image_filename;
 
-    ImageHeader temp_image_header;
-    ImageHeader* image_header = &temp_image_header;
+    ImageHeader image_header;
     {
       TimingLogger::ScopedTiming timing("ReadImageHeader", logger);
-      bool success = file->PreadFully(image_header, sizeof(*image_header), /*offset=*/ 0u);
-      if (!success || !image_header->IsValid()) {
+      bool success = file->PreadFully(&image_header, sizeof(image_header), /*offset=*/ 0u);
+      if (!success || !image_header.IsValid()) {
         *error_msg = StringPrintf("Invalid image header in '%s'", image_filename);
         return nullptr;
       }
     }
     // Check that the file is larger or equal to the header size + data size.
     const uint64_t image_file_size = static_cast<uint64_t>(file->GetLength());
-    if (image_file_size < sizeof(ImageHeader) + image_header->GetDataSize()) {
+    if (image_file_size < sizeof(ImageHeader) + image_header.GetDataSize()) {
       *error_msg = StringPrintf(
           "Image file truncated: %" PRIu64 " vs. %" PRIu64 ".",
            image_file_size,
-           static_cast<uint64_t>(sizeof(ImageHeader) + image_header->GetDataSize()));
+           static_cast<uint64_t>(sizeof(ImageHeader) + image_header.GetDataSize()));
       return nullptr;
     }
 
-    if (oat_file != nullptr) {
-      // If we have an oat file (i.e. for app image), check the oat file checksum.
-      // Otherwise, we open the oat file after the image and check the checksum there.
-      const uint32_t oat_checksum = oat_file->GetOatHeader().GetChecksum();
-      const uint32_t image_oat_checksum = image_header->GetOatChecksum();
-      if (oat_checksum != image_oat_checksum) {
-        *error_msg = StringPrintf("Oat checksum 0x%x does not match the image one 0x%x in image %s",
-                                  oat_checksum,
-                                  image_oat_checksum,
-                                  image_filename);
-        return nullptr;
-      }
-      if (!ValidateBootImageChecksum(image_filename, *image_header, oat_file, error_msg)) {
-        DCHECK(!error_msg->empty());
-        return nullptr;
-      }
-    }
-
     if (VLOG_IS_ON(startup)) {
       LOG(INFO) << "Dumping image sections";
       for (size_t i = 0; i < ImageHeader::kSectionCount; ++i) {
         const auto section_idx = static_cast<ImageHeader::ImageSections>(i);
-        auto& section = image_header->GetImageSection(section_idx);
+        auto& section = image_header.GetImageSection(section_idx);
         LOG(INFO) << section_idx << " start="
-            << reinterpret_cast<void*>(image_header->GetImageBegin() + section.Offset()) << " "
+            << reinterpret_cast<void*>(image_header.GetImageBegin() + section.Offset()) << " "
             << section;
       }
     }
 
-    const auto& bitmap_section = image_header->GetImageBitmapSection();
+    const auto& bitmap_section = image_header.GetImageBitmapSection();
     // The location we want to map from is the first aligned page after the end of the stored
     // (possibly compressed) data.
-    const size_t image_bitmap_offset = RoundUp(sizeof(ImageHeader) + image_header->GetDataSize(),
-                                               kPageSize);
+    const size_t image_bitmap_offset =
+        RoundUp(sizeof(ImageHeader) + image_header.GetDataSize(), kPageSize);
     const size_t end_of_bitmap = image_bitmap_offset + bitmap_section.Size();
     if (end_of_bitmap != image_file_size) {
       *error_msg = StringPrintf(
@@ -866,7 +917,7 @@ class ImageSpace::Loader {
     MemMap map = LoadImageFile(
         image_filename,
         image_location,
-        *image_header,
+        image_header,
         file->Fd(),
         allow_direct_mapping,
         logger,
@@ -876,7 +927,7 @@ class ImageSpace::Loader {
       DCHECK(!error_msg->empty());
       return nullptr;
     }
-    DCHECK_EQ(0, memcmp(image_header, map.Begin(), sizeof(ImageHeader)));
+    DCHECK_EQ(0, memcmp(&image_header, map.Begin(), sizeof(ImageHeader)));
 
     MemMap image_bitmap_map = MemMap::MapFile(bitmap_section.Size(),
                                               PROT_READ,
@@ -890,15 +941,12 @@ class ImageSpace::Loader {
       *error_msg = StringPrintf("Failed to map image bitmap: %s", error_msg->c_str());
       return nullptr;
     }
-    // Loaded the map, use the image header from the file now in case we patch it with
-    // RelocateInPlace.
-    image_header = reinterpret_cast<ImageHeader*>(map.Begin());
     const uint32_t bitmap_index = ImageSpace::bitmap_index_.fetch_add(1);
     std::string bitmap_name(StringPrintf("imagespace %s live-bitmap %u",
                                          image_filename,
                                          bitmap_index));
     // Bitmap only needs to cover until the end of the mirror objects section.
-    const ImageSection& image_objects = image_header->GetObjectsSection();
+    const ImageSection& image_objects = image_header.GetObjectsSection();
     // We only want the mirror object, not the ArtFields and ArtMethods.
     uint8_t* const image_end = map.Begin() + image_objects.End();
     accounting::ContinuousSpaceBitmap bitmap;
@@ -922,7 +970,6 @@ class ImageSpace::Loader {
                                                      std::move(map),
                                                      std::move(bitmap),
                                                      image_end));
-    space->oat_file_non_owned_ = oat_file;
     return space;
   }
 
@@ -954,21 +1001,91 @@ class ImageSpace::Loader {
     return true;
   }
 
+  template <typename Container>
+  static void RemoveInternTableDuplicates(
+      const Container& old_spaces,
+      /*inout*/ImageSpace* new_space,
+      /*inout*/SafeMap<mirror::String*, mirror::String*>* intern_remap)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    const ImageSection& new_interns = new_space->GetImageHeader().GetInternedStringsSection();
+    if (new_interns.Size() != 0u) {
+      const uint8_t* new_data = new_space->Begin() + new_interns.Offset();
+      size_t new_read_count;
+      InternTable::UnorderedSet new_set(new_data, /*make_copy_of_data=*/ false, &new_read_count);
+      for (const auto& old_space : old_spaces) {
+        const ImageSection& old_interns = old_space->GetImageHeader().GetInternedStringsSection();
+        if (old_interns.Size() != 0u) {
+          const uint8_t* old_data = old_space->Begin() + old_interns.Offset();
+          size_t old_read_count;
+          InternTable::UnorderedSet old_set(
+              old_data, /*make_copy_of_data=*/ false, &old_read_count);
+          RemoveDuplicates(old_set, &new_set, intern_remap);
+        }
+      }
+    }
+  }
+
+  static void RemapInternedStringDuplicates(
+      SafeMap<mirror::String*, mirror::String*>&& intern_remap,
+      ImageSpace* new_space) REQUIRES_SHARED(Locks::mutator_lock_) {
+    RemapInternedStringsVisitor visitor(std::move(intern_remap));
+    static_assert(IsAligned<kObjectAlignment>(sizeof(ImageHeader)), "Header alignment check");
+    uint32_t objects_end = new_space->GetImageHeader().GetObjectsSection().Size();
+    DCHECK_ALIGNED(objects_end, kObjectAlignment);
+    for (uint32_t pos = sizeof(ImageHeader); pos != objects_end; ) {
+      mirror::Object* object = reinterpret_cast<mirror::Object*>(new_space->Begin() + pos);
+      object->VisitReferences</*kVisitNativeRoots=*/ false,
+                              kVerifyNone,
+                              kWithoutReadBarrier>(visitor, visitor);
+      pos += RoundUp(object->SizeOf<kVerifyNone>(), kObjectAlignment);
+    }
+  }
+
  private:
+  // Remove duplicates found in the `old_set` from the `new_set`.
+  // Record the removed Strings for remapping. No read barriers are needed as the
+  // tables are either just being loaded and not yet a part of the heap, or boot
+  // image intern tables with non-moveable Strings used when loading an app image.
+  static void RemoveDuplicates(const InternTable::UnorderedSet& old_set,
+                               /*inout*/InternTable::UnorderedSet* new_set,
+                               /*inout*/SafeMap<mirror::String*, mirror::String*>* intern_remap)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (old_set.size() < new_set->size()) {
+      for (const GcRoot<mirror::String>& old_s : old_set) {
+        auto new_it = new_set->find(old_s);
+        if (UNLIKELY(new_it != new_set->end())) {
+          intern_remap->Put(new_it->Read<kWithoutReadBarrier>(), old_s.Read<kWithoutReadBarrier>());
+          new_set->erase(new_it);
+        }
+      }
+    } else {
+      for (auto new_it = new_set->begin(), end = new_set->end(); new_it != end; ) {
+        auto old_it = old_set.find(*new_it);
+        if (UNLIKELY(old_it != old_set.end())) {
+          intern_remap->Put(new_it->Read<kWithoutReadBarrier>(),
+                            old_it->Read<kWithoutReadBarrier>());
+          new_it = new_set->erase(new_it);
+        } else {
+          ++new_it;
+        }
+      }
+    }
+  }
+
   static bool ValidateBootImageChecksum(const char* image_filename,
                                         const ImageHeader& image_header,
                                         const OatFile* oat_file,
+                                        ArrayRef<ImageSpace* const> boot_image_spaces,
+                                        /*out*/size_t* boot_image_space_dependencies,
                                         /*out*/std::string* error_msg) {
     // Use the boot image component count to calculate the checksum from
     // the appropriate number of boot image chunks.
-    const std::vector<ImageSpace*>& image_spaces =
-        Runtime::Current()->GetHeap()->GetBootImageSpaces();
     uint32_t boot_image_component_count = image_header.GetBootImageComponentCount();
-    size_t image_spaces_size = image_spaces.size();
-    if (boot_image_component_count > image_spaces_size) {
+    size_t boot_image_spaces_size = boot_image_spaces.size();
+    if (boot_image_component_count > boot_image_spaces_size) {
       *error_msg = StringPrintf("Too many boot image dependencies (%u > %zu) in image %s",
                                 boot_image_component_count,
-                                image_spaces_size,
+                                boot_image_spaces_size,
                                 image_filename);
       return false;
     }
@@ -977,7 +1094,7 @@ class ImageSpace::Loader {
     size_t space_pos = 0u;
     uint64_t boot_image_size = 0u;
     for (size_t component_count = 0u; component_count != boot_image_component_count; ) {
-      const ImageHeader& current_header = image_spaces[space_pos]->GetImageHeader();
+      const ImageHeader& current_header = boot_image_spaces[space_pos]->GetImageHeader();
       if (current_header.GetComponentCount() > boot_image_component_count - component_count) {
         *error_msg = StringPrintf("Boot image component count in %s ends in the middle of a chunk, "
                                       "%u is between %zu and %zu",
@@ -1001,7 +1118,7 @@ class ImageSpace::Loader {
       return false;
     }
     if (image_header.GetBootImageSize() != boot_image_size) {
-      *error_msg = StringPrintf("Boot image size (0x%08x != 0x%08" PRIx64 ") in image %s",
+      *error_msg = StringPrintf("Boot image size mismatch (0x%08x != 0x%08" PRIx64 ") in image %s",
                                 image_header.GetBootImageSize(),
                                 boot_image_size,
                                 image_filename);
@@ -1029,6 +1146,7 @@ class ImageSpace::Loader {
         return false;
       }
     }
+    *boot_image_space_dependencies = space_pos;
     return true;
   }
 
@@ -1263,38 +1381,37 @@ class ImageSpace::Loader {
   // address. In place means modifying a single ImageSpace in place rather than relocating from
   // one ImageSpace to another.
   template <PointerSize kPointerSize>
-  static bool RelocateInPlace(ImageHeader& image_header,
+  static bool RelocateInPlace(uint32_t boot_image_begin,
                               uint8_t* target_base,
                               accounting::ContinuousSpaceBitmap* bitmap,
                               const OatFile* app_oat_file,
                               std::string* error_msg) {
     DCHECK(error_msg != nullptr);
     // Set up sections.
-    gc::Heap* const heap = Runtime::Current()->GetHeap();
-    uint32_t boot_image_begin = heap->GetBootImagesStartAddress();
-    const uint32_t boot_image_size = image_header.GetBootImageSize();
-    const ImageSection& objects_section = image_header.GetObjectsSection();
+    ImageHeader* image_header = reinterpret_cast<ImageHeader*>(target_base);
+    const uint32_t boot_image_size = image_header->GetBootImageSize();
+    const ImageSection& objects_section = image_header->GetObjectsSection();
     // Where the app image objects are mapped to.
     uint8_t* objects_location = target_base + objects_section.Offset();
     TimingLogger logger(__FUNCTION__, true, false);
-    RelocationRange boot_image(image_header.GetBootImageBegin(),
+    RelocationRange boot_image(image_header->GetBootImageBegin(),
                                boot_image_begin,
                                boot_image_size);
     // Metadata is everything after the objects section, use exclusion to be safe.
     RelocationRange app_image_metadata(
-        reinterpret_cast<uintptr_t>(image_header.GetImageBegin()) + objects_section.End(),
+        reinterpret_cast<uintptr_t>(image_header->GetImageBegin()) + objects_section.End(),
         reinterpret_cast<uintptr_t>(target_base) + objects_section.End(),
-        image_header.GetImageSize() - objects_section.End());
+        image_header->GetImageSize() - objects_section.End());
     // App image heap objects, may be mapped in the heap.
     RelocationRange app_image_objects(
-        reinterpret_cast<uintptr_t>(image_header.GetImageBegin()) + objects_section.Offset(),
+        reinterpret_cast<uintptr_t>(image_header->GetImageBegin()) + objects_section.Offset(),
         reinterpret_cast<uintptr_t>(objects_location),
         objects_section.Size());
     // Use the oat data section since this is where the OatFile::Begin is.
-    RelocationRange app_oat(reinterpret_cast<uintptr_t>(image_header.GetOatDataBegin()),
+    RelocationRange app_oat(reinterpret_cast<uintptr_t>(image_header->GetOatDataBegin()),
                             // Not necessarily in low 4GB.
                             reinterpret_cast<uintptr_t>(app_oat_file->Begin()),
-                            image_header.GetOatDataEnd() - image_header.GetOatDataBegin());
+                            image_header->GetOatDataEnd() - image_header->GetOatDataBegin());
     VLOG(image) << "App image metadata " << app_image_metadata;
     VLOG(image) << "App image objects " << app_image_objects;
     VLOG(image) << "App oat " << app_oat;
@@ -1322,12 +1439,12 @@ class ImageSpace::Loader {
       gc::accounting::ContinuousSpaceBitmap visited_bitmap(
           gc::accounting::ContinuousSpaceBitmap::Create("Relocate bitmap",
                                                         target_base,
-                                                        image_header.GetImageSize()));
+                                                        image_header->GetImageSize()));
       {
         TimingLogger::ScopedTiming timing("Fixup classes", &logger);
         ObjPtr<mirror::Class> class_class = [&]() NO_THREAD_SAFETY_ANALYSIS {
           ObjPtr<mirror::ObjectArray<mirror::Object>> image_roots = app_image_objects.ToDest(
-              image_header.GetImageRoots<kWithoutReadBarrier>().Ptr());
+              image_header->GetImageRoots<kWithoutReadBarrier>().Ptr());
           int32_t class_roots_index = enum_cast<int32_t>(ImageHeader::kClassRoots);
           DCHECK_LT(class_roots_index, image_roots->GetLength<kVerifyNone>());
           ObjPtr<mirror::ObjectArray<mirror::Class>> class_roots =
@@ -1335,7 +1452,7 @@ class ImageSpace::Loader {
                   image_roots->GetWithoutChecks<kVerifyNone>(class_roots_index).Ptr()));
           return GetClassRoot<mirror::Class, kWithoutReadBarrier>(class_roots);
         }();
-        const auto& class_table_section = image_header.GetClassTableSection();
+        const auto& class_table_section = image_header->GetClassTableSection();
         if (class_table_section.Size() > 0u) {
           ScopedObjectAccess soa(Thread::Current());
           ClassTableVisitor class_table_visitor(forward_object);
@@ -1394,13 +1511,13 @@ class ImageSpace::Loader {
       bitmap->VisitMarkedRange(objects_begin, objects_end, fixup_object_visitor);
       // Fixup image roots.
       CHECK(app_image_objects.InSource(reinterpret_cast<uintptr_t>(
-          image_header.GetImageRoots<kWithoutReadBarrier>().Ptr())));
-      image_header.RelocateImageReferences(app_image_objects.Delta());
-      image_header.RelocateBootImageReferences(boot_image.Delta());
-      CHECK_EQ(image_header.GetImageBegin(), target_base);
+          image_header->GetImageRoots<kWithoutReadBarrier>().Ptr())));
+      image_header->RelocateImageReferences(app_image_objects.Delta());
+      image_header->RelocateBootImageReferences(boot_image.Delta());
+      CHECK_EQ(image_header->GetImageBegin(), target_base);
       // Fix up dex cache DexFile pointers.
       ObjPtr<mirror::ObjectArray<mirror::DexCache>> dex_caches =
-          image_header.GetImageRoot<kWithoutReadBarrier>(ImageHeader::kDexCaches)
+          image_header->GetImageRoot<kWithoutReadBarrier>(ImageHeader::kDexCaches)
               ->AsObjectArray<mirror::DexCache, kVerifyNone>();
       for (int32_t i = 0, count = dex_caches->GetLength(); i < count; ++i) {
         ObjPtr<mirror::DexCache> dex_cache = dex_caches->Get<kVerifyNone, kWithoutReadBarrier>(i);
@@ -1411,7 +1528,7 @@ class ImageSpace::Loader {
     {
       // Only touches objects in the app image, no need for mutator lock.
       TimingLogger::ScopedTiming timing("Fixup methods", &logger);
-      image_header.VisitPackedArtMethods([&](ArtMethod& method) NO_THREAD_SAFETY_ANALYSIS {
+      image_header->VisitPackedArtMethods([&](ArtMethod& method) NO_THREAD_SAFETY_ANALYSIS {
         // TODO: Consider a separate visitor for runtime vs normal methods.
         if (UNLIKELY(method.IsRuntimeMethod())) {
           ImtConflictTable* table = method.GetImtConflictTable(kPointerSize);
@@ -1436,21 +1553,21 @@ class ImageSpace::Loader {
       {
         // Only touches objects in the app image, no need for mutator lock.
         TimingLogger::ScopedTiming timing("Fixup fields", &logger);
-        image_header.VisitPackedArtFields([&](ArtField& field) NO_THREAD_SAFETY_ANALYSIS {
+        image_header->VisitPackedArtFields([&](ArtField& field) NO_THREAD_SAFETY_ANALYSIS {
           patch_object_visitor.template PatchGcRoot</*kMayBeNull=*/ false>(
               &field.DeclaringClassRoot());
         }, target_base);
       }
       {
         TimingLogger::ScopedTiming timing("Fixup imt", &logger);
-        image_header.VisitPackedImTables(forward_metadata, target_base, kPointerSize);
+        image_header->VisitPackedImTables(forward_metadata, target_base, kPointerSize);
       }
       {
         TimingLogger::ScopedTiming timing("Fixup conflict tables", &logger);
-        image_header.VisitPackedImtConflictTables(forward_metadata, target_base, kPointerSize);
+        image_header->VisitPackedImtConflictTables(forward_metadata, target_base, kPointerSize);
       }
       // Fix up the intern table.
-      const auto& intern_table_section = image_header.GetInternedStringsSection();
+      const auto& intern_table_section = image_header->GetInternedStringsSection();
       if (intern_table_section.Size() > 0u) {
         TimingLogger::ScopedTiming timing("Fixup intern table", &logger);
         ScopedObjectAccess soa(Thread::Current());
@@ -2539,6 +2656,7 @@ class ImageSpace::BootImageLoader {
     }
 
     MaybeRelocateSpaces(spaces, logger);
+    DeduplicateInternedStrings(ArrayRef<const std::unique_ptr<ImageSpace>>(spaces), logger);
     boot_image_spaces->swap(spaces);
     *extra_reservation = std::move(local_extra_reservation);
     return true;
@@ -2680,6 +2798,9 @@ class ImageSpace::BootImageLoader {
         ? static_cast<int64_t>(reinterpret_cast32<uint32_t>(spaces.front()->Begin())) -
               static_cast<int64_t>(image_begin)
         : base_diff64;
+    if (base_diff64 == 0 && current_diff64 == 0) {
+      return;
+    }
     uint32_t base_diff = static_cast<uint32_t>(base_diff64);
     uint32_t current_diff = static_cast<uint32_t>(current_diff64);
 
@@ -2719,7 +2840,8 @@ class ImageSpace::BootImageLoader {
       class_roots = ObjPtr<mirror::ObjectArray<mirror::Class>>::DownCast(base_relocate_visitor(
           image_roots->GetWithoutChecks<kVerifyNone>(class_roots_index).Ptr()));
       if (kExtension) {
-        DCHECK(patched_objects->Test(class_roots.Ptr()));
+        // Class roots must have been visited if we relocated the primary boot image.
+        DCHECK(base_diff == 0 || patched_objects->Test(class_roots.Ptr()));
         class_class = GetClassRoot<mirror::Class, kWithoutReadBarrier>(class_roots);
         method_class = GetClassRoot<mirror::Method, kWithoutReadBarrier>(class_roots);
         constructor_class = GetClassRoot<mirror::Constructor, kWithoutReadBarrier>(class_roots);
@@ -2868,7 +2990,6 @@ class ImageSpace::BootImageLoader {
         static_cast<int64_t>(reinterpret_cast32<uint32_t>(first_space_header.GetImageBegin()));
     if (!relocate_) {
       DCHECK_EQ(base_diff64, 0);
-      return;
     }
 
     ArrayRef<const std::unique_ptr<ImageSpace>> spaces_ref(spaces);
@@ -2880,6 +3001,56 @@ class ImageSpace::BootImageLoader {
     }
   }
 
+  void DeduplicateInternedStrings(ArrayRef<const std::unique_ptr<ImageSpace>> spaces,
+                                  TimingLogger* logger) REQUIRES_SHARED(Locks::mutator_lock_) {
+    TimingLogger::ScopedTiming timing("DeduplicateInternedStrings", logger);
+    DCHECK(!spaces.empty());
+    size_t num_spaces = spaces.size();
+    const ImageHeader& primary_header = spaces.front()->GetImageHeader();
+    size_t primary_image_count = primary_header.GetImageSpaceCount();
+    DCHECK_LE(primary_image_count, num_spaces);
+    DCHECK_EQ(primary_image_count, primary_header.GetComponentCount());
+    size_t component_count = primary_image_count;
+    size_t space_pos = primary_image_count;
+    while (space_pos != num_spaces) {
+      const ImageHeader& current_header = spaces[space_pos]->GetImageHeader();
+      size_t image_space_count = current_header.GetImageSpaceCount();
+      DCHECK_LE(image_space_count, num_spaces - space_pos);
+      size_t dependency_component_count = current_header.GetBootImageComponentCount();
+      DCHECK_LE(dependency_component_count, component_count);
+      if (dependency_component_count < component_count) {
+        // There shall be no duplicate strings with the components that this space depends on.
+        // Find the end of the dependencies, i.e. start of non-dependency images.
+        size_t start_component_count = primary_image_count;
+        size_t start_pos = primary_image_count;
+        while (start_component_count != dependency_component_count) {
+          const ImageHeader& dependency_header = spaces[start_pos]->GetImageHeader();
+          DCHECK_LE(dependency_header.GetComponentCount(),
+                    dependency_component_count - start_component_count);
+          start_component_count += dependency_header.GetComponentCount();
+          start_pos += dependency_header.GetImageSpaceCount();
+        }
+        // Remove duplicates from all intern tables belonging to the chunk.
+        ArrayRef<const std::unique_ptr<ImageSpace>> old_spaces =
+            spaces.SubArray(/*pos=*/ start_pos, space_pos - start_pos);
+        SafeMap<mirror::String*, mirror::String*> intern_remap;
+        for (size_t i = 0; i != image_space_count; ++i) {
+          ImageSpace* new_space = spaces[space_pos + i].get();
+          Loader::RemoveInternTableDuplicates(old_spaces, new_space, &intern_remap);
+        }
+        // Remap string for all spaces belonging to the chunk.
+        if (!intern_remap.empty()) {
+          for (size_t i = 0; i != image_space_count; ++i) {
+            ImageSpace* new_space = spaces[space_pos + i].get();
+            Loader::RemapInternedStringDuplicates(std::move(intern_remap), new_space);
+          }
+        }
+      }
+      component_count += current_header.GetComponentCount();
+      space_pos += image_space_count;
+    }
+  }
+
   std::unique_ptr<ImageSpace> Load(const std::string& image_location,
                                    const std::string& image_filename,
                                    const std::string& profile_file,
@@ -2899,7 +3070,6 @@ class ImageSpace::BootImageLoader {
                                                         image_filename.c_str(),
                                                         image_location.c_str(),
                                                         profile_file.c_str(),
-                                                        /*oat_file=*/ nullptr,
                                                         /*allow_direct_mapping=*/ false,
                                                         logger,
                                                         image_reservation,
@@ -2936,7 +3106,6 @@ class ImageSpace::BootImageLoader {
     // file name.
     return Loader::Init(image_filename.c_str(),
                         image_location.c_str(),
-                        /*oat_file=*/ nullptr,
                         logger,
                         image_reservation,
                         error_msg);
@@ -3549,10 +3718,23 @@ std::unique_ptr<ImageSpace> ImageSpace::CreateFromAppImage(const char* image,
                                                            const OatFile* oat_file,
                                                            std::string* error_msg) {
   // Note: The oat file has already been validated.
+  const std::vector<ImageSpace*>& boot_image_spaces =
+      Runtime::Current()->GetHeap()->GetBootImageSpaces();
+  return CreateFromAppImage(image,
+                            oat_file,
+                            ArrayRef<ImageSpace* const>(boot_image_spaces),
+                            error_msg);
+}
+
+std::unique_ptr<ImageSpace> ImageSpace::CreateFromAppImage(
+    const char* image,
+    const OatFile* oat_file,
+    ArrayRef<ImageSpace* const> boot_image_spaces,
+    std::string* error_msg) {
   return Loader::InitAppImage(image,
                               image,
                               oat_file,
-                              /*image_reservation=*/ nullptr,
+                              boot_image_spaces,
                               error_msg);
 }
 
diff --git a/runtime/gc/space/image_space.h b/runtime/gc/space/image_space.h
index cf23e7593f..4ddc5191f7 100644
--- a/runtime/gc/space/image_space.h
+++ b/runtime/gc/space/image_space.h
@@ -136,11 +136,18 @@ class ImageSpace : public MemMapSpace {
       /*out*/std::vector<std::unique_ptr<ImageSpace>>* boot_image_spaces,
       /*out*/MemMap* extra_reservation) REQUIRES_SHARED(Locks::mutator_lock_);
 
-  // Try to open an existing app image space.
+  // Try to open an existing app image space for an oat file,
+  // using the boot image spaces from the current Runtime.
   static std::unique_ptr<ImageSpace> CreateFromAppImage(const char* image,
                                                         const OatFile* oat_file,
                                                         std::string* error_msg)
       REQUIRES_SHARED(Locks::mutator_lock_);
+  // Try to open an existing app image space for an the oat file and given boot image spaces.
+  static std::unique_ptr<ImageSpace> CreateFromAppImage(
+      const char* image,
+      const OatFile* oat_file,
+      ArrayRef<ImageSpace* const> boot_image_spaces,
+      std::string* error_msg) REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Checks whether we have a primary boot image on the disk.
   static bool IsBootClassPathOnDisk(InstructionSet image_isa);
@@ -317,6 +324,7 @@ class ImageSpace : public MemMapSpace {
   class BootImageLoader;
   template <typename ReferenceVisitor>
   class ClassTableVisitor;
+  class RemapInternedStringsVisitor;
   class Loader;
   template <typename PatchObjectVisitor>
   class PatchArtFieldVisitor;
diff --git a/runtime/gc/space/image_space_test.cc b/runtime/gc/space/image_space_test.cc
index 580b49062d..b08c68056b 100644
--- a/runtime/gc/space/image_space_test.cc
+++ b/runtime/gc/space/image_space_test.cc
@@ -16,18 +16,211 @@
 
 #include <gtest/gtest.h>
 
+#include "android-base/logging.h"
 #include "android-base/stringprintf.h"
 #include "android-base/strings.h"
 
 #include "base/stl_util.h"
 #include "class_linker.h"
 #include "dexopt_test.h"
+#include "dex/utf.h"
+#include "intern_table.h"
 #include "noop_compiler_callbacks.h"
+#include "oat_file.h"
 
 namespace art {
 namespace gc {
 namespace space {
 
+class ImageSpaceTest : public CommonRuntimeTest {
+ protected:
+  void SetUpRuntimeOptions(RuntimeOptions* options) override {
+    // Disable implicit dex2oat invocations when loading image spaces.
+    options->emplace_back("-Xnoimage-dex2oat", nullptr);
+    // Disable relocation.
+    options->emplace_back("-Xnorelocate", nullptr);
+  }
+
+  std::string GetFilenameBase(const std::string& full_path) {
+    size_t slash_pos = full_path.rfind('/');
+    CHECK_NE(std::string::npos, slash_pos);
+    size_t dot_pos = full_path.rfind('.');
+    CHECK_NE(std::string::npos, dot_pos);
+    CHECK_GT(dot_pos, slash_pos + 1u);
+    return full_path.substr(slash_pos + 1u, dot_pos - (slash_pos + 1u));
+  }
+};
+
+TEST_F(ImageSpaceTest, StringDeduplication) {
+  const char* const kBaseNames[] = { "Extension1", "Extension2" };
+
+  ScratchDir scratch;
+  const std::string& scratch_dir = scratch.GetPath();
+  std::string image_dir = scratch_dir + GetInstructionSetString(kRuntimeISA);
+  int mkdir_result = mkdir(image_dir.c_str(), 0700);
+  ASSERT_EQ(0, mkdir_result);
+
+  // Prepare boot class path variables, exclude conscrypt which is not in the primary boot image.
+  std::vector<std::string> bcp = GetLibCoreDexFileNames();
+  std::vector<std::string> bcp_locations = GetLibCoreDexLocations();
+  CHECK_EQ(bcp.size(), bcp_locations.size());
+  ASSERT_NE(std::string::npos, bcp.back().find("conscrypt"));
+  bcp.pop_back();
+  bcp_locations.pop_back();
+  std::string base_bcp_string = android::base::Join(bcp, ':');
+  std::string base_bcp_locations_string = android::base::Join(bcp_locations, ':');
+  std::string base_image_location = GetImageLocation();
+
+  // Compile the two extensions independently.
+  std::vector<std::string> extension_image_locations;
+  for (const char* base_name : kBaseNames) {
+    std::string jar_name = GetTestDexFileName(base_name);
+    ArrayRef<const std::string> dex_files(&jar_name, /*size=*/ 1u);
+    ScratchFile profile_file;
+    GenerateProfile(dex_files, profile_file.GetFile());
+    std::vector<std::string> extra_args = {
+        "--profile-file=" + profile_file.GetFilename(),
+        "--runtime-arg",
+        "-Xbootclasspath:" + base_bcp_string + ':' + jar_name,
+        "--runtime-arg",
+        "-Xbootclasspath-locations:" + base_bcp_locations_string + ':' + jar_name,
+        "--boot-image=" + base_image_location,
+    };
+    std::string prefix = GetFilenameBase(base_image_location);
+    std::string error_msg;
+    bool success = CompileBootImage(extra_args, image_dir + '/' + prefix, dex_files, &error_msg);
+    ASSERT_TRUE(success) << error_msg;
+    bcp.push_back(jar_name);
+    bcp_locations.push_back(jar_name);
+    extension_image_locations.push_back(
+        scratch_dir + prefix + '-' + GetFilenameBase(jar_name) + ".art");
+  }
+
+  // Also compile the second extension as an app with app image.
+  const char* app_base_name = kBaseNames[std::size(kBaseNames) - 1u];
+  std::string app_jar_name = GetTestDexFileName(app_base_name);
+  std::string app_odex_name = scratch_dir + app_base_name + ".odex";
+  std::string app_image_name = scratch_dir + app_base_name + ".art";
+  {
+    ArrayRef<const std::string> dex_files(&app_jar_name, /*size=*/ 1u);
+    ScratchFile profile_file;
+    GenerateProfile(dex_files, profile_file.GetFile());
+    std::vector<std::string> argv;
+    std::string error_msg;
+    bool success = StartDex2OatCommandLine(&argv, &error_msg, /*use_runtime_bcp_and_image=*/ false);
+    ASSERT_TRUE(success) << error_msg;
+    argv.insert(argv.end(), {
+        "--profile-file=" + profile_file.GetFilename(),
+        "--runtime-arg",
+        "-Xbootclasspath:" + base_bcp_string,
+        "--runtime-arg",
+        "-Xbootclasspath-locations:" + base_bcp_locations_string,
+        "--boot-image=" + base_image_location,
+        "--dex-file=" + app_jar_name,
+        "--dex-location=" + app_jar_name,
+        "--oat-file=" + app_odex_name,
+        "--app-image-file=" + app_image_name,
+        "--initialize-app-image-classes=true",
+    });
+    success = RunDex2Oat(argv, &error_msg);
+    ASSERT_TRUE(success) << error_msg;
+  }
+
+  std::string full_image_locations;
+  std::vector<std::unique_ptr<gc::space::ImageSpace>> boot_image_spaces;
+  MemMap extra_reservation;
+  auto load_boot_image = [&]() REQUIRES_SHARED(Locks::mutator_lock_) {
+    boot_image_spaces.clear();
+    extra_reservation = MemMap::Invalid();
+    return ImageSpace::LoadBootImage(bcp,
+                                     bcp_locations,
+                                     full_image_locations,
+                                     kRuntimeISA,
+                                     ImageSpaceLoadingOrder::kSystemFirst,
+                                     /*relocate=*/ false,
+                                     /*executable=*/ true,
+                                     /*is_zygote=*/ false,
+                                     /*extra_reservation_size=*/ 0u,
+                                     &boot_image_spaces,
+                                     &extra_reservation);
+  };
+
+  const char test_string[] = "SharedBootImageExtensionTestString";
+  size_t test_string_length = std::size(test_string) - 1u;  // Equals UTF-16 length.
+  uint32_t hash = ComputeUtf16HashFromModifiedUtf8(test_string, test_string_length);
+  InternTable::Utf8String utf8_test_string(test_string_length, test_string, hash);
+  auto contains_test_string = [utf8_test_string](ImageSpace* space)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    const ImageHeader& image_header = space->GetImageHeader();
+    if (image_header.GetInternedStringsSection().Size() != 0u) {
+      const uint8_t* data = space->Begin() + image_header.GetInternedStringsSection().Offset();
+      size_t read_count;
+      InternTable::UnorderedSet temp_set(data, /*make_copy_of_data=*/ false, &read_count);
+      return temp_set.find(utf8_test_string) != temp_set.end();
+    } else {
+      return false;
+    }
+  };
+
+  // Load extensions and test for the presence of the test string.
+  ScopedObjectAccess soa(Thread::Current());
+  ASSERT_EQ(2u, extension_image_locations.size());
+  full_image_locations = base_image_location +
+                             ImageSpace::kComponentSeparator + extension_image_locations[0] +
+                             ImageSpace::kComponentSeparator + extension_image_locations[1];
+  bool success = load_boot_image();
+  ASSERT_TRUE(success);
+  ASSERT_EQ(bcp.size(), boot_image_spaces.size());
+  EXPECT_TRUE(contains_test_string(boot_image_spaces[boot_image_spaces.size() - 2u].get()));
+  // The string in the second extension should be replaced and removed from interned string section.
+  EXPECT_FALSE(contains_test_string(boot_image_spaces[boot_image_spaces.size() - 1u].get()));
+
+  // Reload extensions in reverse order and test for the presence of the test string.
+  std::swap(bcp[bcp.size() - 2u], bcp[bcp.size() - 1u]);
+  std::swap(bcp_locations[bcp_locations.size() - 2u], bcp_locations[bcp_locations.size() - 1u]);
+  full_image_locations = base_image_location +
+                             ImageSpace::kComponentSeparator + extension_image_locations[1] +
+                             ImageSpace::kComponentSeparator + extension_image_locations[0];
+  success = load_boot_image();
+  ASSERT_TRUE(success);
+  ASSERT_EQ(bcp.size(), boot_image_spaces.size());
+  EXPECT_TRUE(contains_test_string(boot_image_spaces[boot_image_spaces.size() - 2u].get()));
+  // The string in the second extension should be replaced and removed from interned string section.
+  EXPECT_FALSE(contains_test_string(boot_image_spaces[boot_image_spaces.size() - 1u].get()));
+
+  // Reload the image without the second extension.
+  bcp.erase(bcp.end() - 2u);
+  bcp_locations.erase(bcp_locations.end() - 2u);
+  full_image_locations =
+      base_image_location + ImageSpace::kComponentSeparator + extension_image_locations[0];
+  success = load_boot_image();
+  ASSERT_TRUE(success);
+  ASSERT_EQ(bcp.size(), boot_image_spaces.size());
+  ASSERT_TRUE(contains_test_string(boot_image_spaces[boot_image_spaces.size() - 1u].get()));
+
+  // Load the app odex file and app image.
+  std::string error_msg;
+  std::unique_ptr<OatFile> odex_file(OatFile::Open(/*zip_fd=*/ -1,
+                                                   app_odex_name.c_str(),
+                                                   app_odex_name.c_str(),
+                                                   /*executable=*/ false,
+                                                   /*low_4gb=*/ false,
+                                                   app_jar_name,
+                                                   &error_msg));
+  ASSERT_TRUE(odex_file != nullptr) << error_msg;
+  std::vector<ImageSpace*> non_owning_boot_image_spaces =
+      MakeNonOwningPointerVector(boot_image_spaces);
+  std::unique_ptr<ImageSpace> app_image_space = ImageSpace::CreateFromAppImage(
+      app_image_name.c_str(),
+      odex_file.get(),
+      ArrayRef<ImageSpace* const>(non_owning_boot_image_spaces),
+      &error_msg);
+  ASSERT_TRUE(app_image_space != nullptr) << error_msg;
+
+  // The string in the app image should be replaced and removed from interned string section.
+  EXPECT_FALSE(contains_test_string(app_image_space.get()));
+}
+
 TEST_F(DexoptTest, ValidateOatFile) {
   std::string dex1 = GetScratchDir() + "/Dex1.jar";
   std::string multidex1 = GetScratchDir() + "/MultiDex1.jar";
@@ -234,6 +427,8 @@ TEST_F(ImageSpaceNoRelocateNoDex2oatTest, Test) {
 
 class NoAccessAndroidDataTest : public ImageSpaceLoadingTest<false, true, true> {
  protected:
+  NoAccessAndroidDataTest() : quiet_(LogSeverity::FATAL) {}
+
   void SetUpRuntimeOptions(RuntimeOptions* options) override {
     const char* android_data = getenv("ANDROID_DATA");
     CHECK(android_data != nullptr);
@@ -265,6 +460,7 @@ class NoAccessAndroidDataTest : public ImageSpaceLoadingTest<false, true, true>
   }
 
  private:
+  ScopedLogSeverity quiet_;
   std::string old_android_data_;
   std::string bad_android_data_;
   std::string bad_dalvik_cache_;
diff --git a/runtime/image.h b/runtime/image.h
index 896a83bb6a..637bf1c1ac 100644
--- a/runtime/image.h
+++ b/runtime/image.h
@@ -579,8 +579,8 @@ T ClearDexCacheNativeRefTags(T val) {
   return val & ~3u;
 }
 
-std::ostream& operator<<(std::ostream& os, const ImageHeader::ImageMethod& policy);
-std::ostream& operator<<(std::ostream& os, const ImageHeader::ImageRoot& policy);
+std::ostream& operator<<(std::ostream& os, const ImageHeader::ImageMethod& method);
+std::ostream& operator<<(std::ostream& os, const ImageHeader::ImageRoot& root);
 std::ostream& operator<<(std::ostream& os, const ImageHeader::ImageSections& section);
 std::ostream& operator<<(std::ostream& os, const ImageSection& section);
 std::ostream& operator<<(std::ostream& os, const ImageHeader::StorageMode& mode);
diff --git a/runtime/intern_table-inl.h b/runtime/intern_table-inl.h
index 6fc53e9f20..687f5ee6ba 100644
--- a/runtime/intern_table-inl.h
+++ b/runtime/intern_table-inl.h
@@ -19,8 +19,9 @@
 
 #include "intern_table.h"
 
-// Required for ToModifiedUtf8 below.
-#include "mirror/string-inl.h"
+#include "gc/space/image_space.h"
+#include "image.h"
+#include "mirror/string-inl.h"  // Required for ToModifiedUtf8 below.
 
 namespace art {
 
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index a5301a5908..7065015a13 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -17,9 +17,6 @@
 #ifndef ART_RUNTIME_INTERN_TABLE_H_
 #define ART_RUNTIME_INTERN_TABLE_H_
 
-#include <unordered_set>
-
-#include "base/atomic.h"
 #include "base/allocator.h"
 #include "base/hash_set.h"
 #include "base/mutex.h"
diff --git a/test/Android.bp b/test/Android.bp
index 024e55e814..db213390ad 100644
--- a/test/Android.bp
+++ b/test/Android.bp
@@ -950,6 +950,8 @@ filegroup {
         ":art-gtest-jars-ErroneousA",
         ":art-gtest-jars-ErroneousB",
         ":art-gtest-jars-ErroneousInit",
+        ":art-gtest-jars-Extension1",
+        ":art-gtest-jars-Extension2",
         ":art-gtest-jars-ForClassLoaderA",
         ":art-gtest-jars-ForClassLoaderB",
         ":art-gtest-jars-ForClassLoaderC",
@@ -1050,6 +1052,18 @@ java_library {
 }
 
 java_library {
+    name: "art-gtest-jars-Extension1",
+    srcs: ["Extension1/**/*.java"],
+    defaults: ["art-gtest-jars-defaults"],
+}
+
+java_library {
+    name: "art-gtest-jars-Extension2",
+    srcs: ["Extension2/**/*.java"],
+    defaults: ["art-gtest-jars-defaults"],
+}
+
+java_library {
     name: "art-gtest-jars-ForClassLoaderA",
     srcs: ["ForClassLoaderA/**/*.java"],
     defaults: ["art-gtest-jars-defaults"],
diff --git a/test/Extension1/ExtensionClass1.java b/test/Extension1/ExtensionClass1.java
new file mode 100644
index 0000000000..b59643a639
--- /dev/null
+++ b/test/Extension1/ExtensionClass1.java
@@ -0,0 +1,20 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+class ExtensionClass1 {
+    public static String sharedString = "SharedBootImageExtensionTestString";
+    public static String uniqueString = "UniqueExtension1String";
+}
diff --git a/test/Extension2/ExtensionClass2.java b/test/Extension2/ExtensionClass2.java
new file mode 100644
index 0000000000..437341d74d
--- /dev/null
+++ b/test/Extension2/ExtensionClass2.java
@@ -0,0 +1,21 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+class ExtensionClass2 {
+    public static String sharedString = "SharedBootImageExtensionTestString";
+    public static String uniqueString1 = "UniqueExtension2String1";
+    public static String uniqueString2 = "UniqueExtension2String2";
+}