diff --git a/fs_mgr/Android.bp b/fs_mgr/Android.bp
index 34c64d2..7a88aa3 100644
--- a/fs_mgr/Android.bp
+++ b/fs_mgr/Android.bp
@@ -91,6 +91,7 @@
     },
     header_libs: [
         "libfiemap_headers",
+        "libstorage_literals_headers",
     ],
     export_header_lib_headers: [
         "libfiemap_headers",
@@ -165,7 +166,7 @@
         "libcrypto",
         "libext4_utils",
         "libfec",
-        "libfs_mgr",
+        "libfs_mgr_binder",
         "liblog",
         "liblp",
         "libselinux",
@@ -187,4 +188,26 @@
             ],
         },
     },
+    required: [
+        "clean_scratch_files",
+    ],
+}
+
+cc_binary {
+    name: "clean_scratch_files",
+    defaults: ["fs_mgr_defaults"],
+    shared_libs: [
+        "libbase",
+        "libfs_mgr_binder",
+    ],
+    srcs: [
+        "clean_scratch_files.cpp",
+    ],
+    product_variables: {
+        debuggable: {
+            init_rc: [
+                "clean_scratch_files.rc",
+            ],
+        },
+    },
 }
diff --git a/fs_mgr/clean_scratch_files.cpp b/fs_mgr/clean_scratch_files.cpp
new file mode 100644
index 0000000..42fe35a
--- /dev/null
+++ b/fs_mgr/clean_scratch_files.cpp
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+#include <fs_mgr_overlayfs.h>
+
+int main() {
+    android::fs_mgr::CleanupOldScratchFiles();
+    return 0;
+}
diff --git a/fs_mgr/clean_scratch_files.rc b/fs_mgr/clean_scratch_files.rc
new file mode 100644
index 0000000..738d1aa
--- /dev/null
+++ b/fs_mgr/clean_scratch_files.rc
@@ -0,0 +1,2 @@
+on post-fs-data && property:ro.debuggable=1
+    exec_background - root root -- clean_scratch_files
diff --git a/fs_mgr/fs_mgr_overlayfs.cpp b/fs_mgr/fs_mgr_overlayfs.cpp
index c043754..ca19782 100644
--- a/fs_mgr/fs_mgr_overlayfs.cpp
+++ b/fs_mgr/fs_mgr_overlayfs.cpp
@@ -48,15 +48,21 @@
 #include <fs_mgr_overlayfs.h>
 #include <fstab/fstab.h>
 #include <libdm/dm.h>
+#include <libfiemap/image_manager.h>
 #include <libgsi/libgsi.h>
 #include <liblp/builder.h>
 #include <liblp/liblp.h>
+#include <storage_literals/storage_literals.h>
 
 #include "fs_mgr_priv.h"
+#include "libfiemap/utility.h"
 
 using namespace std::literals;
 using namespace android::dm;
 using namespace android::fs_mgr;
+using namespace android::storage_literals;
+using android::fiemap::FilesystemHasReliablePinning;
+using android::fiemap::IImageManager;
 
 namespace {
 
@@ -104,6 +110,14 @@
     return false;
 }
 
+namespace android {
+namespace fs_mgr {
+
+void MapScratchPartitionIfNeeded(Fstab*, const std::function<bool(const std::string&)>&) {}
+
+}  // namespace fs_mgr
+}  // namespace android
+
 #else  // ALLOW_ADBD_DISABLE_VERITY == 0
 
 namespace {
@@ -153,6 +167,12 @@
 }
 
 const auto kPhysicalDevice = "/dev/block/by-name/"s;
+constexpr char kScratchImageMetadata[] = "/metadata/gsi/remount/lp_metadata";
+
+// Note: this is meant only for recovery/first-stage init.
+bool ScratchIsOnData() {
+    return fs_mgr_access(kScratchImageMetadata);
+}
 
 bool fs_mgr_update_blk_device(FstabEntry* entry) {
     if (entry->fs_mgr_flags.logical) {
@@ -443,20 +463,37 @@
 bool fs_mgr_overlayfs_teardown_scratch(const std::string& overlay, bool* change) {
     // umount and delete kScratchMountPoint storage if we have logical partitions
     if (overlay != kScratchMountPoint) return true;
-    auto slot_number = fs_mgr_overlayfs_slot_number();
-    auto super_device = fs_mgr_overlayfs_super_device(slot_number);
-    if (!fs_mgr_rw_access(super_device)) return true;
 
     auto save_errno = errno;
     if (fs_mgr_overlayfs_already_mounted(kScratchMountPoint, false)) {
         fs_mgr_overlayfs_umount_scratch();
     }
+
+    const auto partition_name = android::base::Basename(kScratchMountPoint);
+
+    auto images = IImageManager::Open("remount", 10s);
+    if (images && images->BackingImageExists(partition_name)) {
+#if defined __ANDROID_RECOVERY__
+        if (!images->DisableImage(partition_name)) {
+            return false;
+        }
+#else
+        if (!images->UnmapImageIfExists(partition_name) ||
+            !images->DeleteBackingImage(partition_name)) {
+            return false;
+        }
+#endif
+    }
+
+    auto slot_number = fs_mgr_overlayfs_slot_number();
+    auto super_device = fs_mgr_overlayfs_super_device(slot_number);
+    if (!fs_mgr_rw_access(super_device)) return true;
+
     auto builder = MetadataBuilder::New(super_device, slot_number);
     if (!builder) {
         errno = save_errno;
         return true;
     }
-    const auto partition_name = android::base::Basename(kScratchMountPoint);
     if (builder->FindPartition(partition_name) == nullptr) {
         errno = save_errno;
         return true;
@@ -836,7 +873,8 @@
 // This returns the scratch device that was detected during early boot (first-
 // stage init). If the device was created later, for example during setup for
 // the adb remount command, it can return an empty string since it does not
-// query ImageManager.
+// query ImageManager. (Note that ImageManager in first-stage init will always
+// use device-mapper, since /data is not available to use loop devices.)
 static std::string GetBootScratchDevice() {
     auto& dm = DeviceMapper::Instance();
 
@@ -992,12 +1030,66 @@
     return true;
 }
 
-static bool CanUseSuperPartition(const Fstab& fstab) {
+static bool CreateScratchOnData(std::string* scratch_device, bool* partition_exists, bool* change) {
+    *partition_exists = false;
+    *change = false;
+
+    auto images = IImageManager::Open("remount", 10s);
+    if (!images) {
+        return false;
+    }
+
+    auto partition_name = android::base::Basename(kScratchMountPoint);
+    if (images->GetMappedImageDevice(partition_name, scratch_device)) {
+        *partition_exists = true;
+        return true;
+    }
+
+    BlockDeviceInfo info;
+    PartitionOpener opener;
+    if (!opener.GetInfo(fs_mgr_get_super_partition_name(), &info)) {
+        LERROR << "could not get block device info for super";
+        return false;
+    }
+
+    *change = true;
+
+    // Note: calling RemoveDisabledImages here ensures that we do not race with
+    // clean_scratch_files and accidentally try to map an image that will be
+    // deleted.
+    if (!images->RemoveDisabledImages()) {
+        return false;
+    }
+    if (!images->BackingImageExists(partition_name)) {
+        static constexpr uint64_t kMinimumSize = 16_MiB;
+        static constexpr uint64_t kMaximumSize = 2_GiB;
+
+        uint64_t size = std::clamp(info.size / 2, kMinimumSize, kMaximumSize);
+        auto flags = IImageManager::CREATE_IMAGE_DEFAULT;
+
+        if (!images->CreateBackingImage(partition_name, size, flags)) {
+            LERROR << "could not create scratch image of " << size << " bytes";
+            return false;
+        }
+    }
+    if (!images->MapImageDevice(partition_name, 10s, scratch_device)) {
+        LERROR << "could not map scratch image";
+        return false;
+    }
+    return true;
+}
+
+static bool CanUseSuperPartition(const Fstab& fstab, bool* is_virtual_ab) {
     auto slot_number = fs_mgr_overlayfs_slot_number();
     auto super_device = fs_mgr_overlayfs_super_device(slot_number);
     if (!fs_mgr_rw_access(super_device) || !fs_mgr_overlayfs_has_logical(fstab)) {
         return false;
     }
+    auto metadata = ReadMetadata(super_device, slot_number);
+    if (!metadata) {
+        return false;
+    }
+    *is_virtual_ab = !!(metadata->header.flags & LP_HEADER_FLAG_VIRTUAL_AB_DEVICE);
     return true;
 }
 
@@ -1011,7 +1103,12 @@
     }
 
     // If that fails, see if we can land on super.
-    if (CanUseSuperPartition(fstab)) {
+    bool is_virtual_ab;
+    if (CanUseSuperPartition(fstab, &is_virtual_ab)) {
+        bool can_use_data = false;
+        if (is_virtual_ab && FilesystemHasReliablePinning("/data", &can_use_data) && can_use_data) {
+            return CreateScratchOnData(scratch_device, partition_exists, change);
+        }
         return CreateDynamicScratch(scratch_device, partition_exists, change);
     }
 
@@ -1053,19 +1150,6 @@
     return fs_mgr_overlayfs_mount_scratch(scratch_device, mnt_type);
 }
 
-bool fs_mgr_overlayfs_scratch_can_be_mounted(const std::string& scratch_device) {
-    if (scratch_device.empty()) return false;
-    if (fs_mgr_overlayfs_already_mounted(kScratchMountPoint, false)) return false;
-    if (android::base::StartsWith(scratch_device, kPhysicalDevice)) return true;
-    if (fs_mgr_rw_access(scratch_device)) return true;
-    auto slot_number = fs_mgr_overlayfs_slot_number();
-    auto super_device = fs_mgr_overlayfs_super_device(slot_number);
-    if (!fs_mgr_rw_access(super_device)) return false;
-    auto builder = MetadataBuilder::New(super_device, slot_number);
-    if (!builder) return false;
-    return builder->FindPartition(android::base::Basename(kScratchMountPoint)) != nullptr;
-}
-
 bool fs_mgr_overlayfs_invalid() {
     if (fs_mgr_overlayfs_valid() == OverlayfsValidResult::kNotSupported) return true;
 
@@ -1114,7 +1198,7 @@
     // if verity is still disabled, i.e. no reboot occurred), and skips calling
     // fs_mgr_overlayfs_mount_all().
     auto scratch_device = GetBootScratchDevice();
-    if (!fs_mgr_overlayfs_scratch_can_be_mounted(scratch_device)) {
+    if (!fs_mgr_rw_access(scratch_device)) {
         return;
     }
     if (!WaitForFile(scratch_device, 10s)) {
@@ -1152,35 +1236,6 @@
     return ret;
 }
 
-std::vector<std::string> fs_mgr_overlayfs_required_devices(Fstab* fstab) {
-    if (fs_mgr_overlayfs_invalid()) return {};
-
-    if (GetEntryForMountPoint(fstab, kScratchMountPoint) != nullptr) {
-        return {};
-    }
-
-    bool want_scratch = false;
-    for (const auto& entry : fs_mgr_overlayfs_candidate_list(*fstab)) {
-        if (fs_mgr_is_verity_enabled(entry)) {
-            continue;
-        }
-        if (fs_mgr_overlayfs_already_mounted(fs_mgr_mount_point(entry.mount_point))) {
-            continue;
-        }
-        want_scratch = true;
-        break;
-    }
-    if (!want_scratch) {
-        return {};
-    }
-
-    auto device = GetBootScratchDevice();
-    if (!device.empty()) {
-        return {device};
-    }
-    return {};
-}
-
 // Returns false if setup not permitted, errno set to last error.
 // If something is altered, set *change.
 bool fs_mgr_overlayfs_setup(const char* backing, const char* mount_point, bool* change,
@@ -1246,13 +1301,27 @@
     return ret;
 }
 
-static bool GetAndMapScratchDeviceIfNeeded(std::string* device, bool* mapped) {
+static bool EnsureScratchMapped(std::string* device, bool* mapped) {
     *mapped = false;
     *device = GetBootScratchDevice();
     if (!device->empty()) {
         return true;
     }
 
+    auto partition_name = android::base::Basename(kScratchMountPoint);
+
+    // Check for scratch on /data first, before looking for a modified super
+    // partition. We should only reach this code in recovery, because scratch
+    // would otherwise always be mapped.
+    auto images = IImageManager::Open("remount", 10s);
+    if (images && images->BackingImageExists(partition_name)) {
+        if (!images->MapImageDevice(partition_name, 10s, device)) {
+            return false;
+        }
+        *mapped = true;
+        return true;
+    }
+
     // Avoid uart spam by first checking for a scratch partition.
     auto metadata_slot = fs_mgr_overlayfs_slot_number();
     auto super_device = fs_mgr_overlayfs_super_device(metadata_slot);
@@ -1261,7 +1330,6 @@
         return false;
     }
 
-    auto partition_name = android::base::Basename(kScratchMountPoint);
     auto partition = FindPartition(*metadata.get(), partition_name);
     if (!partition) {
         return false;
@@ -1281,6 +1349,12 @@
     return true;
 }
 
+static void UnmapScratchDevice() {
+    // This should only be reachable in recovery, where scratch is not
+    // automatically mapped and therefore can be unmapped.
+    DestroyLogicalPartition(android::base::Basename(kScratchMountPoint));
+}
+
 // Returns false if teardown not permitted, errno set to last error.
 // If something is altered, set *change.
 bool fs_mgr_overlayfs_teardown(const char* mount_point, bool* change) {
@@ -1293,7 +1367,7 @@
     bool unmap = false;
     if ((mount_point != nullptr) && !fs_mgr_overlayfs_already_mounted(kScratchMountPoint, false)) {
         std::string scratch_device;
-        if (GetAndMapScratchDeviceIfNeeded(&scratch_device, &unmap)) {
+        if (EnsureScratchMapped(&scratch_device, &unmap)) {
             mount_scratch = fs_mgr_overlayfs_mount_scratch(scratch_device,
                                                            fs_mgr_overlayfs_scratch_mount_type());
         }
@@ -1319,7 +1393,7 @@
         fs_mgr_overlayfs_umount_scratch();
     }
     if (unmap) {
-        DestroyLogicalPartition(android::base::Basename(kScratchMountPoint));
+        UnmapScratchDevice();
     }
     return ret;
 }
@@ -1338,6 +1412,59 @@
     return false;
 }
 
+namespace android {
+namespace fs_mgr {
+
+void MapScratchPartitionIfNeeded(Fstab* fstab,
+                                 const std::function<bool(const std::set<std::string>&)>& init) {
+    if (fs_mgr_overlayfs_invalid()) {
+        return;
+    }
+    if (GetEntryForMountPoint(fstab, kScratchMountPoint) != nullptr) {
+        return;
+    }
+
+    bool want_scratch = false;
+    for (const auto& entry : fs_mgr_overlayfs_candidate_list(*fstab)) {
+        if (fs_mgr_is_verity_enabled(entry)) {
+            continue;
+        }
+        if (fs_mgr_overlayfs_already_mounted(fs_mgr_mount_point(entry.mount_point))) {
+            continue;
+        }
+        want_scratch = true;
+        break;
+    }
+    if (!want_scratch) {
+        return;
+    }
+
+    if (ScratchIsOnData()) {
+        if (auto images = IImageManager::Open("remount", 0ms)) {
+            images->MapAllImages(init);
+        }
+    }
+
+    // Physical or logical partitions will have already been mapped here,
+    // so just ensure /dev/block symlinks exist.
+    auto device = GetBootScratchDevice();
+    if (!device.empty()) {
+        init({android::base::Basename(device)});
+    }
+}
+
+void CleanupOldScratchFiles() {
+    if (!ScratchIsOnData()) {
+        return;
+    }
+    if (auto images = IImageManager::Open("remount", 0ms)) {
+        images->RemoveDisabledImages();
+    }
+}
+
+}  // namespace fs_mgr
+}  // namespace android
+
 #endif  // ALLOW_ADBD_DISABLE_VERITY != 0
 
 bool fs_mgr_has_shared_blocks(const std::string& mount_point, const std::string& dev) {
diff --git a/fs_mgr/include/fs_mgr_overlayfs.h b/fs_mgr/include/fs_mgr_overlayfs.h
index 9a7381f..34aded9 100644
--- a/fs_mgr/include/fs_mgr_overlayfs.h
+++ b/fs_mgr/include/fs_mgr_overlayfs.h
@@ -16,8 +16,11 @@
 
 #pragma once
 
+#include <functional>
+
 #include <fstab/fstab.h>
 
+#include <set>
 #include <string>
 #include <vector>
 
@@ -38,3 +41,13 @@
     kOverrideCredsRequired,
 };
 OverlayfsValidResult fs_mgr_overlayfs_valid();
+
+namespace android {
+namespace fs_mgr {
+
+void MapScratchPartitionIfNeeded(Fstab* fstab,
+                                 const std::function<bool(const std::set<std::string>&)>& init);
+void CleanupOldScratchFiles();
+
+}  // namespace fs_mgr
+}  // namespace android
diff --git a/fs_mgr/libfiemap/image_manager.cpp b/fs_mgr/libfiemap/image_manager.cpp
index 280318e..0195716 100644
--- a/fs_mgr/libfiemap/image_manager.cpp
+++ b/fs_mgr/libfiemap/image_manager.cpp
@@ -124,7 +124,7 @@
     return images;
 }
 
-bool ImageManager::PartitionExists(const std::string& name) {
+bool ImageManager::BackingImageExists(const std::string& name) {
     if (!MetadataExists(metadata_dir_)) {
         return false;
     }
@@ -135,11 +135,6 @@
     return !!FindPartition(*metadata.get(), name);
 }
 
-bool ImageManager::BackingImageExists(const std::string& name) {
-    auto header_file = GetImageHeaderPath(name);
-    return access(header_file.c_str(), F_OK) == 0;
-}
-
 static bool IsUnreliablePinningAllowed(const std::string& path) {
     return android::base::StartsWith(path, "/data/gsi/dsu/") ||
            android::base::StartsWith(path, "/data/gsi/test/") ||
@@ -261,6 +256,10 @@
         return false;
     }
 
+#if defined __ANDROID_RECOVERY__
+    LOG(ERROR) << "Cannot remove images backed by /data in recovery";
+    return false;
+#else
     std::string message;
     auto header_file = GetImageHeaderPath(name);
     if (!SplitFiemap::RemoveSplitFiles(header_file, &message)) {
@@ -274,6 +273,7 @@
         LOG(ERROR) << "Error removing " << status_file << ": " << message;
     }
     return RemoveImageMetadata(metadata_dir_, name);
+#endif
 }
 
 // Create a block device for an image file, using its extents in its
@@ -507,6 +507,7 @@
 
     auto image_header = GetImageHeaderPath(name);
 
+#if !defined __ANDROID_RECOVERY__
     // If there is a device-mapper node wrapping the block device, then we're
     // able to create another node around it; the dm layer does not carry the
     // exclusion lock down the stack when a mount occurs.
@@ -530,6 +531,13 @@
     } else if (!MapWithLoopDevice(name, timeout_ms, path)) {
         return false;
     }
+#else
+    // In recovery, we can *only* use device-mapper, since partitions aren't
+    // mounted. That also means we cannot call GetBlockDeviceForFile.
+    if (!MapWithDmLinear(*partition_opener_.get(), name, timeout_ms, path)) {
+        return false;
+    }
+#endif
 
     // Set a property so we remember this is mapped.
     auto prop_name = GetStatusPropertyName(name);
diff --git a/fs_mgr/libfiemap/include/libfiemap/image_manager.h b/fs_mgr/libfiemap/include/libfiemap/image_manager.h
index 2c13229..60b98dc 100644
--- a/fs_mgr/libfiemap/include/libfiemap/image_manager.h
+++ b/fs_mgr/libfiemap/include/libfiemap/image_manager.h
@@ -76,7 +76,9 @@
     // Unmap a block device previously mapped with mapBackingImage.
     virtual bool UnmapImageDevice(const std::string& name) = 0;
 
-    // Returns true whether the named backing image exists.
+    // Returns true whether the named backing image exists. This does not check
+    // consistency with the /data partition, so that it can return true in
+    // recovery.
     virtual bool BackingImageExists(const std::string& name) = 0;
 
     // Returns true if the specified image is mapped to a device.
@@ -154,10 +156,6 @@
 
     std::vector<std::string> GetAllBackingImages();
 
-    // Returns true if the named partition exists. This does not check the
-    // consistency of the backing image/data file.
-    bool PartitionExists(const std::string& name);
-
     // Validates that all images still have pinned extents. This will be removed
     // once b/134588268 is fixed.
     bool Validate();
diff --git a/fs_mgr/libstorage_literals/Android.bp b/fs_mgr/libstorage_literals/Android.bp
index 11611dd..beb18ef 100644
--- a/fs_mgr/libstorage_literals/Android.bp
+++ b/fs_mgr/libstorage_literals/Android.bp
@@ -2,5 +2,6 @@
 cc_library_headers {
     name: "libstorage_literals_headers",
     host_supported: true,
+    recovery_available: true,
     export_include_dirs: ["."],
 }
diff --git a/fs_mgr/tests/adb-remount-test.sh b/fs_mgr/tests/adb-remount-test.sh
index 4226e95..c66f307 100755
--- a/fs_mgr/tests/adb-remount-test.sh
+++ b/fs_mgr/tests/adb-remount-test.sh
@@ -1160,13 +1160,16 @@
 ret=${?}
 uses_dynamic_scratch=false
 scratch_partition=
+virtual_ab=`get_property ro.virtual_ab.enabled`
 if ${overlayfs_needed}; then
   if [ ${ret} != 0 ]; then
     die -t ${T} "overlay takeover failed"
   fi
   echo "${D}" | grep "^overlay .* /system\$" >/dev/null ||
    echo "${ORANGE}[  WARNING ]${NORMAL} overlay takeover not complete" >&2
-  scratch_partition=scratch
+  if [ -z "${virtual_ab}" ]; then
+    scratch_partition=scratch
+  fi
   if echo "${D}" | grep " /mnt/scratch" >/dev/null; then
     echo "${BLUE}[     INFO ]${NORMAL} using ${scratch_partition} dynamic partition for overrides" >&2
   fi
diff --git a/init/first_stage_mount.cpp b/init/first_stage_mount.cpp
index 9da32e4..d8c4843 100644
--- a/init/first_stage_mount.cpp
+++ b/init/first_stage_mount.cpp
@@ -591,14 +591,18 @@
     }
 
     // heads up for instantiating required device(s) for overlayfs logic
-    const auto devices = fs_mgr_overlayfs_required_devices(&fstab_);
-    for (auto const& device : devices) {
-        if (android::base::StartsWith(device, "/dev/block/by-name/")) {
-            InitRequiredDevices({basename(device.c_str())});
-        } else {
-            InitMappedDevice(device);
+    auto init_devices = [this](std::set<std::string> devices) -> bool {
+        for (auto iter = devices.begin(); iter != devices.end();) {
+            if (android::base::StartsWith(*iter, "/dev/block/dm-")) {
+                if (!InitMappedDevice(*iter)) return false;
+                iter = devices.erase(iter);
+            } else {
+                iter++;
+            }
         }
-    }
+        return InitRequiredDevices(std::move(devices));
+    };
+    MapScratchPartitionIfNeeded(&fstab_, init_devices);
 
     fs_mgr_overlayfs_mount_all(&fstab_);