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: 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: If18814f03dba3d72ae15981625473f4da303b1d6
diff --git a/patchoat/Android.bp b/patchoat/Android.bp
index 0902823..0e8e517 100644
--- a/patchoat/Android.bp
+++ b/patchoat/Android.bp
@@ -26,6 +26,7 @@
     },
     shared_libs: [
         "libbase",
+        "libcrypto", // For computing the digest of image file
     ],
 }
 
@@ -58,5 +59,6 @@
     ],
     shared_libs: [
         "libartd",
+        "libcrypto", // For computing the digest of image file
     ],
 }
diff --git a/patchoat/patchoat.cc b/patchoat/patchoat.cc
index eb648cb..6c9cf86 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 @@
   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 @@
       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 @@
     }
   }
 
-  // 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];
 
-    bool success = p.WriteImage(output_image_file.get());
-    success = FinishFile(output_image_file.get(), success);
-    if (!success) {
-      return false;
+      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;
+      }
+
+      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 @@
   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 @@
                           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 @@
 
   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 @@
   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 @@
       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 @@
                            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 8351684..1033a2e 100644
--- a/patchoat/patchoat.h
+++ b/patchoat/patchoat.h
@@ -44,12 +44,25 @@
 
 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 86e851c..fdd8fc4 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>
 
@@ -137,6 +138,21 @@
     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 +279,34 @@
   }
 
   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 +319,127 @@
       *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_start = rel.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) {
+        size_t offset_offset_in_rel = rel_ptr - rel_start;
+        uint32_t offset_delta = 0;
+        uint32_t shift = 0;
+        while (true) {
+          uint8_t b = *rel_ptr;
+          rel_ptr++;
+          offset_delta |= (b & 0x7f) << shift;
+          shift += 7;
+          if ((b & 0x80) == 0) {
+            // This is the last byte of the encoded offset delta
+            break;
+          }
+          // There are more bytes encoding this offset delta
+          if (rel_ptr == rel_end) {
+            *error_msg =
+                StringPrintf(
+                      "Malformed image relocation file %s: truncated delta at %zu",
+                          rel_filename.c_str(), offset_offset_in_rel);
+            return false;
+          }
+          if (shift > 22) {
+            *error_msg =
+                StringPrintf(
+                      "Malformed image relocation file %s: delta encoding too long at %zu",
+                      rel_filename.c_str(), offset_offset_in_rel);
+            return false;
+          }
+        }
+        offset += offset_delta;
+        if (offset >= image_size) {
+          *error_msg =
+              StringPrintf(
+                  "Malformed image relocation file %s: offset at %zu (%" PRIu32
+                      ") >= image size (%zu)",
+                  rel_filename.c_str(),
+                  offset_offset_in_rel,
+                  offset,
+                  image_size);
+          return false;
+        }
+        uint32_t *image_value = reinterpret_cast<uint32_t*>(image_start + offset);
+        *image_value -= expected_diff;
       }
     }
 
-    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 +553,135 @@
 #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.
+
+  // 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