Reland: Enable patchoat to write image relocation files

This adds an off by default feature to patchoat whereby it can write
image relocation information (i.e., which offsets are patched up by
patchoat) to .rel files. .rel file writing is enabled by specifying
the name of boot.art.rel file using command-line parameter
--output-image-relocation-file=...

The currently intended use case is to make the Android build process
store these files on the system image next to boot*.art files. At boot
time, in follow-up commits, these .rel files will then be used to
verify that all differences between /system boot*.art and
/data/dalvik-cache boot*.art files can be explained by relocation. The
goal is to mitigate /data/dalvik-cache boot*.art being a persistence
vector.

Test: ./art/test/testrunner/run_build_test_target.py art-gtest-debug-gc
Test: make test-art-host-gtest-patchoat_test
Test: ART_HEAP_POISONING=true make test-art-host-gtest-patchoat_test
Test: make test-art-target-gtest-patchoat_test
Test: ANDROID_ROOT=out/target/product/sailfish/system \
        ANDROID_DATA=out/target/product/sailfish/dex_bootjars/system/framework/arm64/ \
        out/host/linux-x86/bin/patchoat \
        --input-image-location=<full path to>/out/target/product/sailfish/dex_bootjars/system/framework/boot.art \
        --output-image-file=out/target/product/sailfish/dex_bootjars/system/framework/arm64/boot.art \
        --instruction-set=arm64 --base-offset-delta=0x10000000
        produces same boot*.art files as prior to this change
Test: ANDROID_ROOT=out/target/product/sailfish/system \
        ANDROID_DATA=out/target/product/sailfish/dex_bootjars/system/framework/arm64/ \
        out/host/linux-x86/bin/patchoat \
        --input-image-location=<full path to>/out/target/product/sailfish/dex_bootjars/system/framework/boot.art \
        --output-image-relocation-file=out/target/product/sailfish/dex_bootjars/system/framework/arm64/boot.art.rel \
        --instruction-set=arm64 --base-offset-delta=0x10000000
        produces no boot*.art files, but produces expected boot.art.rel files
Bug: 66697305

Change-Id: Ia6b548c61429c61a62706d4021f8e6f22c49082e

5 files changed, 528 insertions, 62 deletions

diff --git a/patchoat/Android.bp b/patchoat/Android.bp
index 0902823644..0e8e517cd4 100644
--- a/patchoat/Android.bp
+++ b/patchoat/Android.bp
@@ -26,6 +26,7 @@ cc_defaults {
     },
     shared_libs: [
         "libbase",
+        "libcrypto", // For computing the digest of image file
     ],
 }
 
@@ -58,5 +59,6 @@ art_cc_test {
     ],
     shared_libs: [
         "libartd",
+        "libcrypto", // For computing the digest of image file
     ],
 }
diff --git a/patchoat/patchoat.cc b/patchoat/patchoat.cc
index eb648cba18..6c9cf864b3 100644
--- a/patchoat/patchoat.cc
+++ b/patchoat/patchoat.cc
@@ -15,6 +15,7 @@
  */
 #include "patchoat.h"
 
+#include <openssl/sha.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <sys/file.h>
@@ -42,6 +43,7 @@
 #include "gc/space/image_space.h"
 #include "image-inl.h"
 #include "intern_table.h"
+#include "leb128.h"
 #include "mirror/dex_cache.h"
 #include "mirror/executable.h"
 #include "mirror/method.h"
@@ -58,6 +60,8 @@
 
 namespace art {
 
+using android::base::StringPrintf;
+
 static const OatHeader* GetOatHeader(const ElfFile* elf_file) {
   uint64_t off = 0;
   if (!elf_file->GetSectionOffsetAndSize(".rodata", &off, nullptr)) {
@@ -120,11 +124,134 @@ static bool SymlinkFile(const std::string& input_filename, const std::string& ou
   return true;
 }
 
+bool PatchOat::GeneratePatch(
+    const MemMap& original,
+    const MemMap& relocated,
+    std::vector<uint8_t>* output,
+    std::string* error_msg) {
+  // FORMAT of the patch (aka image relocation) file:
+  // * SHA-256 digest (32 bytes) of original/unrelocated file (e.g., the one from /system)
+  // * List of monotonically increasing offsets (max value defined by uint32_t) at which relocations
+  //   occur.
+  //   Each element is represented as the delta from the previous offset in the list (first element
+  //   is a delta from 0). Each delta is encoded using unsigned LEB128: little-endian
+  //   variable-length 7 bits per byte encoding, where all bytes have the highest bit (0x80) set
+  //   except for the final byte which does not have that bit set. For example, 0x3f is offset 0x3f,
+  //   whereas 0xbf 0x05 is offset (0x3f & 0x7f) | (0x5 << 7) which is 0x2bf. Most deltas end up
+  //   being encoding using just one byte, achieving ~4x decrease in relocation file size compared
+  //   to the encoding where offsets are stored verbatim, as uint32_t.
+
+  size_t original_size = original.Size();
+  size_t relocated_size = relocated.Size();
+  if (original_size != relocated_size) {
+    *error_msg =
+        StringPrintf(
+            "Original and relocated image sizes differ: %zu vs %zu", original_size, relocated_size);
+    return false;
+  }
+  if ((original_size % 4) != 0) {
+    *error_msg = StringPrintf("Image size not multiple of 4: %zu", original_size);
+    return false;
+  }
+  if (original_size > UINT32_MAX) {
+    *error_msg = StringPrintf("Image too large: %zu" , original_size);
+    return false;
+  }
+
+  const ImageHeader& relocated_header =
+      *reinterpret_cast<const ImageHeader*>(relocated.Begin());
+  // Offsets are supposed to differ between original and relocated by this value
+  off_t expected_diff = relocated_header.GetPatchDelta();
+  if (expected_diff == 0) {
+    // Can't identify offsets which are supposed to differ due to relocation
+    *error_msg = "Relocation delta is 0";
+    return false;
+  }
+
+  // Output the SHA-256 digest of the original
+  output->resize(SHA256_DIGEST_LENGTH);
+  const uint8_t* original_bytes = original.Begin();
+  SHA256(original_bytes, original_size, output->data());
+
+  // Output the list of offsets at which the original and patched images differ
+  size_t last_diff_offset = 0;
+  size_t diff_offset_count = 0;
+  const uint8_t* relocated_bytes = relocated.Begin();
+  for (size_t offset = 0; offset < original_size; offset += 4) {
+    uint32_t original_value = *reinterpret_cast<const uint32_t*>(original_bytes + offset);
+    uint32_t relocated_value = *reinterpret_cast<const uint32_t*>(relocated_bytes + offset);
+    off_t diff = relocated_value - original_value;
+    if (diff == 0) {
+      continue;
+    } else if (diff != expected_diff) {
+      *error_msg =
+          StringPrintf(
+              "Unexpected diff at offset %zu. Expected: %jd, but was: %jd",
+              offset,
+              (intmax_t) expected_diff,
+              (intmax_t) diff);
+      return false;
+    }
+
+    uint32_t offset_diff = offset - last_diff_offset;
+    last_diff_offset = offset;
+    diff_offset_count++;
+
+    EncodeUnsignedLeb128(output, offset_diff);
+  }
+
+  if (diff_offset_count == 0) {
+    *error_msg = "Original and patched images are identical";
+    return false;
+  }
+
+  return true;
+}
+
+static bool WriteRelFile(
+    const MemMap& original,
+    const MemMap& relocated,
+    const std::string& rel_filename,
+    std::string* error_msg) {
+  std::vector<uint8_t> output;
+  if (!PatchOat::GeneratePatch(original, relocated, &output, error_msg)) {
+    return false;
+  }
+
+  std::unique_ptr<File> rel_file(OS::CreateEmptyFileWriteOnly(rel_filename.c_str()));
+  if (rel_file.get() == nullptr) {
+    *error_msg = StringPrintf("Failed to create/open output file %s", rel_filename.c_str());
+    return false;
+  }
+  if (!rel_file->WriteFully(output.data(), output.size())) {
+    *error_msg = StringPrintf("Failed to write to %s", rel_filename.c_str());
+    return false;
+  }
+  if (rel_file->FlushCloseOrErase() != 0) {
+    *error_msg = StringPrintf("Failed to flush and close %s", rel_filename.c_str());
+    return false;
+  }
+
+  return true;
+}
+
 bool PatchOat::Patch(const std::string& image_location,
                      off_t delta,
-                     const std::string& output_directory,
+                     const std::string& output_image_directory,
+                     const std::string& output_image_relocation_directory,
                      InstructionSet isa,
                      TimingLogger* timings) {
+  bool output_image = !output_image_directory.empty();
+  bool output_image_relocation = !output_image_relocation_directory.empty();
+  if ((!output_image) && (!output_image_relocation)) {
+    // Nothing to do
+    return true;
+  }
+  if ((output_image_relocation) && (delta == 0)) {
+    LOG(ERROR) << "Cannot output image relocation information when requested relocation delta is 0";
+    return false;
+  }
+
   CHECK(Runtime::Current() == nullptr);
   CHECK(!image_location.empty()) << "image file must have a filename.";
 
@@ -221,32 +348,35 @@ bool PatchOat::Patch(const std::string& image_location,
       return false;
     }
 
-    MaybePic is_oat_pic = IsOatPic(elf.get());
-    if (is_oat_pic >= ERROR_FIRST) {
-      // Error logged by IsOatPic
-      return false;
-    } else if (is_oat_pic == NOT_PIC) {
-      LOG(ERROR) << "patchoat cannot be used on non-PIC oat file: " << input_oat_file->GetPath();
-      return false;
-    } else {
-      CHECK(is_oat_pic == PIC);
-
-      // Create a symlink.
-      std::string converted_image_filename = space->GetImageLocation();
-      std::replace(converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
-      std::string output_image_filename = output_directory +
-          (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
-          converted_image_filename;
-      std::string output_vdex_filename =
-          ImageHeader::GetVdexLocationFromImageLocation(output_image_filename);
-      std::string output_oat_filename =
-          ImageHeader::GetOatLocationFromImageLocation(output_image_filename);
-
-      if (!ReplaceOatFileWithSymlink(input_oat_file->GetPath(),
-                                     output_oat_filename) ||
-          !SymlinkFile(input_vdex_filename, output_vdex_filename)) {
-        // Errors already logged by above call.
+    if (output_image) {
+      MaybePic is_oat_pic = IsOatPic(elf.get());
+      if (is_oat_pic >= ERROR_FIRST) {
+        // Error logged by IsOatPic
         return false;
+      } else if (is_oat_pic == NOT_PIC) {
+        LOG(ERROR) << "patchoat cannot be used on non-PIC oat file: " << input_oat_file->GetPath();
+        return false;
+      } else {
+        CHECK(is_oat_pic == PIC);
+
+        // Create a symlink.
+        std::string converted_image_filename = space->GetImageLocation();
+        std::replace(
+            converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
+        std::string output_image_filename = output_image_directory +
+            (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
+            converted_image_filename;
+        std::string output_vdex_filename =
+            ImageHeader::GetVdexLocationFromImageLocation(output_image_filename);
+        std::string output_oat_filename =
+            ImageHeader::GetOatLocationFromImageLocation(output_image_filename);
+
+        if (!ReplaceOatFileWithSymlink(input_oat_file->GetPath(),
+                                       output_oat_filename) ||
+            !SymlinkFile(input_vdex_filename, output_vdex_filename)) {
+          // Errors already logged by above call.
+          return false;
+        }
       }
     }
 
@@ -267,28 +397,72 @@ bool PatchOat::Patch(const std::string& image_location,
     }
   }
 
-  // Write the patched image spaces.
-  for (size_t i = 0; i < spaces.size(); ++i) {
-    gc::space::ImageSpace* space = spaces[i];
+  if (output_image) {
+    // Write the patched image spaces.
+    for (size_t i = 0; i < spaces.size(); ++i) {
+      gc::space::ImageSpace* space = spaces[i];
 
-    t.NewTiming("Writing image");
-    std::string converted_image_filename = space->GetImageLocation();
-    std::replace(converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
-    std::string output_image_filename = output_directory +
-        (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
-        converted_image_filename;
-    std::unique_ptr<File> output_image_file(CreateOrOpen(output_image_filename.c_str()));
-    if (output_image_file.get() == nullptr) {
-      LOG(ERROR) << "Failed to open output image file at " << output_image_filename;
-      return false;
+      t.NewTiming("Writing image");
+      std::string converted_image_filename = space->GetImageLocation();
+      std::replace(converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
+      std::string output_image_filename = output_image_directory +
+          (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
+          converted_image_filename;
+      std::unique_ptr<File> output_image_file(CreateOrOpen(output_image_filename.c_str()));
+      if (output_image_file.get() == nullptr) {
+        LOG(ERROR) << "Failed to open output image file at " << output_image_filename;
+        return false;
+      }
+
+      PatchOat& p = space_to_patchoat_map.find(space)->second;
+
+      bool success = p.WriteImage(output_image_file.get());
+      success = FinishFile(output_image_file.get(), success);
+      if (!success) {
+        return false;
+      }
     }
+  }
 
-    PatchOat& p = space_to_patchoat_map.find(space)->second;
+  if (output_image_relocation) {
+    // Write the image relocation information for each space.
+    for (size_t i = 0; i < spaces.size(); ++i) {
+      gc::space::ImageSpace* space = spaces[i];
+
+      t.NewTiming("Writing image relocation");
+      std::string original_image_filename(space->GetImageLocation() + ".rel");
+      std::string image_relocation_filename =
+          output_image_relocation_directory
+              + (android::base::StartsWith(original_image_filename, "/") ? "" : "/")
+              + original_image_filename.substr(original_image_filename.find_last_of("/"));
+      File& input_image = *space_to_file_map.find(space)->second;
+      int64_t input_image_size = input_image.GetLength();
+      if (input_image_size < 0) {
+        LOG(ERROR) << "Error while getting input image size";
+        return false;
+      }
+      std::string error_msg;
+      std::unique_ptr<MemMap> original(MemMap::MapFile(input_image_size,
+                                                       PROT_READ,
+                                                       MAP_PRIVATE,
+                                                       input_image.Fd(),
+                                                       0,
+                                                       /*low_4gb*/false,
+                                                       input_image.GetPath().c_str(),
+                                                       &error_msg));
+      if (original.get() == nullptr) {
+        LOG(ERROR) << "Unable to map image file " << input_image.GetPath() << " : " << error_msg;
+        return false;
+      }
 
-    bool success = p.WriteImage(output_image_file.get());
-    success = FinishFile(output_image_file.get(), success);
-    if (!success) {
-      return false;
+      PatchOat& p = space_to_patchoat_map.find(space)->second;
+      const MemMap* relocated = p.image_;
+
+      if (!WriteRelFile(*original, *relocated, image_relocation_filename, &error_msg)) {
+        LOG(ERROR) << "Failed to create image relocation file " << image_relocation_filename
+            << ": " << error_msg;
+        return false;
+      }
     }
   }
 
@@ -739,6 +913,9 @@ NO_RETURN static void Usage(const char *fmt, ...) {
   UsageError("  --output-image-file=<file.art>: Specifies the exact file to write the patched");
   UsageError("      image file to.");
   UsageError("");
+  UsageError("  --output-image-relocation-file=<file.art.rel>: Specifies the exact file to write");
+  UsageError("      the image relocation information to.");
+  UsageError("");
   UsageError("  --base-offset-delta=<delta>: Specify the amount to change the old base-offset by.");
   UsageError("      This value may be negative.");
   UsageError("");
@@ -754,12 +931,13 @@ static int patchoat_image(TimingLogger& timings,
                           InstructionSet isa,
                           const std::string& input_image_location,
                           const std::string& output_image_filename,
+                          const std::string& output_image_relocation_filename,
                           off_t base_delta,
                           bool base_delta_set,
                           bool debug) {
   CHECK(!input_image_location.empty());
-  if (output_image_filename.empty()) {
-    Usage("Image patching requires --output-image-file");
+  if ((output_image_filename.empty()) && (output_image_relocation_filename.empty())) {
+    Usage("Image patching requires --output-image-file or --output-image-relocation-file");
   }
 
   if (!base_delta_set) {
@@ -778,9 +956,19 @@ static int patchoat_image(TimingLogger& timings,
 
   TimingLogger::ScopedTiming pt("patch image and oat", &timings);
 
-  std::string output_directory =
+  std::string output_image_directory =
       output_image_filename.substr(0, output_image_filename.find_last_of('/'));
-  bool ret = PatchOat::Patch(input_image_location, base_delta, output_directory, isa, &timings);
+  std::string output_image_relocation_directory =
+      output_image_relocation_filename.substr(
+          0, output_image_relocation_filename.find_last_of('/'));
+  bool ret =
+      PatchOat::Patch(
+          input_image_location,
+          base_delta,
+          output_image_directory,
+          output_image_relocation_directory,
+          isa,
+          &timings);
 
   if (kIsDebugBuild) {
     LOG(INFO) << "Exiting with return ... " << ret;
@@ -811,6 +999,7 @@ static int patchoat(int argc, char **argv) {
   InstructionSet isa = InstructionSet::kNone;
   std::string input_image_location;
   std::string output_image_filename;
+  std::string output_image_relocation_filename;
   off_t base_delta = 0;
   bool base_delta_set = false;
   bool dump_timings = kIsDebugBuild;
@@ -832,6 +1021,9 @@ static int patchoat(int argc, char **argv) {
       input_image_location = option.substr(strlen("--input-image-location=")).data();
     } else if (option.starts_with("--output-image-file=")) {
       output_image_filename = option.substr(strlen("--output-image-file=")).data();
+    } else if (option.starts_with("--output-image-relocation-file=")) {
+      output_image_relocation_filename =
+          option.substr(strlen("--output-image-relocation-file=")).data();
     } else if (option.starts_with("--base-offset-delta=")) {
       const char* base_delta_str = option.substr(strlen("--base-offset-delta=")).data();
       base_delta_set = true;
@@ -856,6 +1048,7 @@ static int patchoat(int argc, char **argv) {
                            isa,
                            input_image_location,
                            output_image_filename,
+                           output_image_relocation_filename,
                            base_delta,
                            base_delta_set,
                            debug);
diff --git a/patchoat/patchoat.h b/patchoat/patchoat.h
index 83516845d8..1033a2e5e1 100644
--- a/patchoat/patchoat.h
+++ b/patchoat/patchoat.h
@@ -44,12 +44,25 @@ class Class;
 
 class PatchOat {
  public:
+  // Relocates the provided image by the specified offset. If output_image_directory is non-empty,
+  // outputs the relocated image into that directory. If output_image_relocation_directory is
+  // non-empty, outputs image relocation files (see GeneratePatch) into that directory.
   static bool Patch(const std::string& image_location,
                     off_t delta,
-                    const std::string& output_directory,
+                    const std::string& output_image_directory,
+                    const std::string& output_image_relocation_directory,
                     InstructionSet isa,
                     TimingLogger* timings);
 
+  // Generates a patch which can be used to efficiently relocate the original file or to check that
+  // a relocated file matches the original. The patch is generated from the difference of the
+  // |original| and the already |relocated| image, and written to |output| in the form of unsigned
+  // LEB128 for each relocation position.
+  static bool GeneratePatch(const MemMap& original,
+                            const MemMap& relocated,
+                            std::vector<uint8_t>* output,
+                            std::string* error_msg);
+
   ~PatchOat() {}
   PatchOat(PatchOat&&) = default;
 
diff --git a/patchoat/patchoat_test.cc b/patchoat/patchoat_test.cc
index 86e851c72b..90cb4f8310 100644
--- a/patchoat/patchoat_test.cc
+++ b/patchoat/patchoat_test.cc
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+#include <openssl/sha.h>
 #include <dirent.h>
 #include <sys/types.h>
 
@@ -24,6 +25,7 @@
 #include "android-base/strings.h"
 
 #include "dexopt_test.h"
+#include "leb128.h"
 #include "runtime.h"
 
 #include <gtest/gtest.h>
@@ -137,6 +139,21 @@ class PatchoatTest : public DexoptTest {
     return RunDex2OatOrPatchoat(argv, error_msg);
   }
 
+  bool GenerateBootImageRelFile(const std::string& input_image_location,
+                                const std::string& output_rel_filename,
+                                off_t base_offset_delta,
+                                std::string* error_msg) {
+    Runtime* const runtime = Runtime::Current();
+    std::vector<std::string> argv;
+    argv.push_back(runtime->GetPatchoatExecutable());
+    argv.push_back("--input-image-location=" + input_image_location);
+    argv.push_back("--output-image-relocation-file=" + output_rel_filename);
+    argv.push_back(StringPrintf("--base-offset-delta=0x%jx", (intmax_t) base_offset_delta));
+    argv.push_back(StringPrintf("--instruction-set=%s", GetInstructionSetString(kRuntimeISA)));
+
+    return RunDex2OatOrPatchoat(argv, error_msg);
+  }
+
   bool RunDex2OatOrPatchoat(const std::vector<std::string>& args, std::string* error_msg) {
     int link[2];
 
@@ -263,6 +280,34 @@ class PatchoatTest : public DexoptTest {
   }
 
   bool BinaryDiff(
+      const std::string& filename1,
+      const std::vector<uint8_t>& data1,
+      const std::string& filename2,
+      const std::vector<uint8_t>& data2,
+      std::string* error_msg) {
+    if (data1.size() != data1.size()) {
+      *error_msg =
+          StringPrintf(
+              "%s and %s are of different size: %zu vs %zu",
+              filename1.c_str(),
+              filename2.c_str(),
+              data1.size(),
+              data2.size());
+      return true;
+    }
+    size_t size = data1.size();
+    for (size_t i = 0; i < size; i++) {
+      if (data1[i] != data2[i]) {
+        *error_msg =
+            StringPrintf("%s and %s differ at offset %zu", filename1.c_str(), filename2.c_str(), i);
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+  bool BinaryDiff(
       const std::string& filename1, const std::string& filename2, std::string* error_msg) {
     std::string read_error_msg;
     std::vector<uint8_t> image1;
@@ -275,26 +320,97 @@ class PatchoatTest : public DexoptTest {
       *error_msg = StringPrintf("Failed to read %s: %s", filename2.c_str(), read_error_msg.c_str());
       return true;
     }
-    if (image1.size() != image2.size()) {
+    return BinaryDiff(filename1, image1, filename2, image2, error_msg);
+  }
+
+  bool IsImageIdenticalToOriginalExceptForRelocation(
+      const std::string& relocated_filename,
+      const std::string& original_filename,
+      const std::string& rel_filename,
+      std::string* error_msg) {
+    *error_msg = "";
+    std::string read_error_msg;
+    std::vector<uint8_t> rel;
+    if (!ReadFully(rel_filename, &rel, &read_error_msg)) {
+      *error_msg =
+          StringPrintf("Failed to read %s: %s", rel_filename.c_str(), read_error_msg.c_str());
+      return false;
+    }
+    std::vector<uint8_t> relocated;
+    if (!ReadFully(relocated_filename, &relocated, &read_error_msg)) {
+      *error_msg =
+          StringPrintf("Failed to read %s: %s", relocated_filename.c_str(), read_error_msg.c_str());
+      return false;
+    }
+
+    size_t image_size = relocated.size();
+    if ((image_size % 4) != 0) {
       *error_msg =
           StringPrintf(
-              "%s and %s are of different size: %zu vs %zu",
-              filename1.c_str(),
-              filename2.c_str(),
-              image1.size(),
-              image2.size());
-      return true;
+              "Relocated image file %s size not multiple of 4: %zu",
+                  relocated_filename.c_str(), image_size);
+      return false;
     }
-    size_t size = image1.size();
-    for (size_t i = 0; i < size; i++) {
-      if (image1[i] != image2[i]) {
+    if (image_size > UINT32_MAX) {
+      *error_msg =
+          StringPrintf(
+              "Relocated image file %s too large: %zu" , relocated_filename.c_str(), image_size);
+      return false;
+    }
+
+    const ImageHeader& relocated_header = *reinterpret_cast<const ImageHeader*>(relocated.data());
+    off_t expected_diff = relocated_header.GetPatchDelta();
+
+    if (expected_diff != 0) {
+      // Relocated image is expected to differ from the original due to relocation.
+      // Unrelocate the image in memory to compensate.
+      uint8_t* image_start = relocated.data();
+      const uint8_t* rel_end = &rel[rel.size()];
+      if (rel.size() < SHA256_DIGEST_LENGTH) {
         *error_msg =
-            StringPrintf("%s and %s differ at offset %zu", filename1.c_str(), filename2.c_str(), i);
-        return true;
+            StringPrintf("Malformed image relocation file %s: too short", rel_filename.c_str());
+        return false;
+      }
+      const uint8_t* rel_ptr = &rel[SHA256_DIGEST_LENGTH];
+      // The remaining .rel file consists of offsets at which relocation should've occurred.
+      // For each offset, we "unrelocate" the image by subtracting the expected relocation
+      // diff value (as specified in the image header).
+      //
+      // Each offset is encoded as a delta/diff relative to the previous offset. With the
+      // very first offset being encoded relative to offset 0.
+      // Deltas are encoded using little-endian 7 bits per byte encoding, with all bytes except
+      // the last one having the highest bit set.
+      uint32_t offset = 0;
+      while (rel_ptr != rel_end) {
+        uint32_t offset_delta = 0;
+        if (DecodeUnsignedLeb128Checked(&rel_ptr, rel_end, &offset_delta)) {
+          offset += offset_delta;
+          uint32_t *image_value = reinterpret_cast<uint32_t*>(image_start + offset);
+          *image_value -= expected_diff;
+        } else {
+            *error_msg =
+                StringPrintf(
+                    "Malformed image relocation file %s: "
+                    "last byte has it's most significant bit set",
+                    rel_filename.c_str());
+            return false;
+        }
       }
     }
 
-    return false;
+    // Image in memory is now supposed to be identical to the original. Compare it to the original.
+    std::vector<uint8_t> original;
+    if (!ReadFully(original_filename, &original, &read_error_msg)) {
+      *error_msg =
+          StringPrintf("Failed to read %s: %s", original_filename.c_str(), read_error_msg.c_str());
+      return false;
+    }
+    if (BinaryDiff(relocated_filename, relocated, original_filename, original, error_msg)) {
+      return false;
+    }
+
+    // Relocated image is identical to the original, once relocations are taken into account
+    return true;
   }
 };
 
@@ -408,4 +524,140 @@ TEST_F(PatchoatTest, PatchoatRelocationSameAsDex2oatRelocation) {
 #endif
 }
 
+TEST_F(PatchoatTest, RelFileSufficientToUnpatch) {
+  // This test checks that a boot image relocated using patchoat can be unrelocated using the .rel
+  // file created by patchoat.
+
+  // This test doesn't work when heap poisoning is enabled because some of the
+  // references are negated. b/72117833 is tracking the effort to have patchoat
+  // and its tests support heap poisoning.
+  TEST_DISABLED_FOR_HEAP_POISONING();
+
+  // Compile boot image into a random directory using dex2oat
+  ScratchFile dex2oat_orig_scratch;
+  dex2oat_orig_scratch.Unlink();
+  std::string dex2oat_orig_dir = dex2oat_orig_scratch.GetFilename();
+  ASSERT_EQ(0, mkdir(dex2oat_orig_dir.c_str(), 0700));
+  const uint32_t orig_base_addr = 0x60000000;
+  std::vector<std::string> dex2oat_extra_args;
+  std::string error_msg;
+  if (!CompileBootImageToDir(dex2oat_orig_dir, dex2oat_extra_args, orig_base_addr, &error_msg)) {
+    FAIL() << "CompileBootImage1 failed: " << error_msg;
+  }
+
+  // Generate image relocation file for the original boot image
+  ScratchFile rel_scratch;
+  rel_scratch.Unlink();
+  std::string rel_dir = rel_scratch.GetFilename();
+  ASSERT_EQ(0, mkdir(rel_dir.c_str(), 0700));
+  std::string dex2oat_orig_with_arch_dir =
+      dex2oat_orig_dir + "/" + GetInstructionSetString(kRuntimeISA);
+  // The arch-including symlink is needed by patchoat
+  ASSERT_EQ(0, symlink(dex2oat_orig_dir.c_str(), dex2oat_orig_with_arch_dir.c_str()));
+  off_t base_addr_delta = 0x100000;
+  if (!GenerateBootImageRelFile(
+      dex2oat_orig_dir + "/boot.art",
+      rel_dir + "/boot.art.rel",
+      base_addr_delta,
+      &error_msg)) {
+    FAIL() << "RelocateBootImage failed: " << error_msg;
+  }
+
+  // Relocate the original boot image using patchoat
+  ScratchFile relocated_scratch;
+  relocated_scratch.Unlink();
+  std::string relocated_dir = relocated_scratch.GetFilename();
+  ASSERT_EQ(0, mkdir(relocated_dir.c_str(), 0700));
+  // Use a different relocation delta from the one used when generating .rel files above. This is
+  // to make sure .rel files are not specific to a particular relocation delta.
+  base_addr_delta -= 0x10000;
+  if (!RelocateBootImage(
+      dex2oat_orig_dir + "/boot.art",
+      relocated_dir + "/boot.art",
+      base_addr_delta,
+      &error_msg)) {
+    FAIL() << "RelocateBootImage failed: " << error_msg;
+  }
+
+  // Assert that patchoat created the same set of .art and .art.rel files
+  std::vector<std::string> rel_basenames;
+  std::vector<std::string> relocated_image_basenames;
+  if (!ListDirFilesEndingWith(rel_dir, "", &rel_basenames, &error_msg)) {
+    FAIL() << "Failed to list *.art.rel files in " << rel_dir << ": " << error_msg;
+  }
+  if (!ListDirFilesEndingWith(relocated_dir, ".art", &relocated_image_basenames, &error_msg)) {
+    FAIL() << "Failed to list *.art files in " << relocated_dir << ": " << error_msg;
+  }
+  std::sort(rel_basenames.begin(), rel_basenames.end());
+  std::sort(relocated_image_basenames.begin(), relocated_image_basenames.end());
+
+  // .art and .art.rel file names output by patchoat look like
+  // tmp@art-data-<random>-<random>@boot*.art, encoding the name of the directory in their name.
+  // To compare these with each other, we retain only the part of the file name after the last @,
+  // and we also drop the extension.
+  std::vector<std::string> rel_shortened_basenames(rel_basenames.size());
+  std::vector<std::string> relocated_image_shortened_basenames(relocated_image_basenames.size());
+  for (size_t i = 0; i < rel_basenames.size(); i++) {
+    rel_shortened_basenames[i] = rel_basenames[i].substr(rel_basenames[i].find_last_of("@") + 1);
+    rel_shortened_basenames[i] =
+        rel_shortened_basenames[i].substr(0, rel_shortened_basenames[i].find("."));
+  }
+  for (size_t i = 0; i < relocated_image_basenames.size(); i++) {
+    relocated_image_shortened_basenames[i] =
+        relocated_image_basenames[i].substr(relocated_image_basenames[i].find_last_of("@") + 1);
+    relocated_image_shortened_basenames[i] =
+        relocated_image_shortened_basenames[i].substr(
+            0, relocated_image_shortened_basenames[i].find("."));
+  }
+  ASSERT_EQ(rel_shortened_basenames, relocated_image_shortened_basenames);
+
+  // For each image file, assert that unrelocating the image produces its original version
+  for (size_t i = 0; i < relocated_image_basenames.size(); i++) {
+    const std::string& original_image_filename =
+        dex2oat_orig_dir + "/" + relocated_image_shortened_basenames[i] + ".art";
+    const std::string& relocated_image_filename =
+        relocated_dir + "/" + relocated_image_basenames[i];
+    const std::string& rel_filename = rel_dir + "/" + rel_basenames[i];
+
+    // Assert that relocated image differs from the original
+    if (!BinaryDiff(original_image_filename, relocated_image_filename, &error_msg)) {
+      FAIL() << "Relocated image " << relocated_image_filename
+          << " identical to the original image " << original_image_filename;
+    }
+
+    // Assert that relocated image is identical to the original except for relocations described in
+    // the .rel file
+    if (!IsImageIdenticalToOriginalExceptForRelocation(
+        relocated_image_filename, original_image_filename, rel_filename, &error_msg)) {
+      FAIL() << "Unrelocating " << relocated_image_filename << " using " << rel_filename
+          << " did not produce the same output as " << original_image_filename << ": " << error_msg;
+    }
+
+    // Assert that the digest of original image in .rel file is as expected
+    std::vector<uint8_t> original;
+    if (!ReadFully(original_image_filename, &original, &error_msg)) {
+      FAIL() << "Failed to read original image " << original_image_filename;
+    }
+    std::vector<uint8_t> rel;
+    if (!ReadFully(rel_filename, &rel, &error_msg)) {
+      FAIL() << "Failed to read image relocation file " << rel_filename;
+    }
+    uint8_t original_image_digest[SHA256_DIGEST_LENGTH];
+    SHA256(original.data(), original.size(), original_image_digest);
+    const uint8_t* original_image_digest_in_rel_file = rel.data();
+    if (memcmp(original_image_digest_in_rel_file, original_image_digest, SHA256_DIGEST_LENGTH)) {
+      FAIL() << "Digest of original image in " << rel_filename << " does not match the original"
+          " image " << original_image_filename;
+    }
+  }
+
+  ClearDirectory(dex2oat_orig_dir.c_str(), /*recursive*/ true);
+  ClearDirectory(rel_dir.c_str(), /*recursive*/ true);
+  ClearDirectory(relocated_dir.c_str(), /*recursive*/ true);
+
+  rmdir(dex2oat_orig_dir.c_str());
+  rmdir(rel_dir.c_str());
+  rmdir(relocated_dir.c_str());
+}
+
 }  // namespace art
diff --git a/runtime/common_runtime_test.h b/runtime/common_runtime_test.h
index 1c73240eea..0aed70a330 100644
--- a/runtime/common_runtime_test.h
+++ b/runtime/common_runtime_test.h
@@ -311,6 +311,12 @@ class CheckJniAbortCatcher {
     printf("WARNING: TEST DISABLED FOR COMPACT DEX\n"); \
     return; \
   }
+
+#define TEST_DISABLED_FOR_HEAP_POISONING() \
+  if (kPoisonHeapReferences) { \
+    printf("WARNING: TEST DISABLED FOR HEAP POISONING\n"); \
+    return; \
+  }
 }  // namespace art
 
 #endif  // ART_RUNTIME_COMMON_RUNTIME_TEST_H_