diff --git a/Checkpoint.cpp b/Checkpoint.cpp
index 4766d79..eca49ef 100644
--- a/Checkpoint.cpp
+++ b/Checkpoint.cpp
@@ -16,6 +16,8 @@
 
 #define LOG_TAG "Checkpoint"
 #include "Checkpoint.h"
+#include "FsCrypt.h"
+#include "KeyStorage.h"
 #include "VoldUtil.h"
 #include "VolumeManager.h"
 
@@ -78,6 +80,18 @@
     return true;
 }
 
+// Do any work that was deferred until the userdata filesystem checkpoint was
+// committed.  This work involves the deletion of resources that aren't covered
+// by the userdata filesystem checkpoint, e.g. Keystore keys.
+void DoCheckpointCommittedWork() {
+    // Take the crypt lock to provide synchronization with the Binder calls that
+    // operate on key directories.
+    std::lock_guard<std::mutex> lock(VolumeManager::Instance()->getCryptLock());
+
+    DeferredCommitKeystoreKeys();
+    fscrypt_deferred_fixate_ce_keys();
+}
+
 }  // namespace
 
 Status cp_supportsCheckpoint(bool& result) {
@@ -206,6 +220,7 @@
     if (!android::base::RemoveFileIfExists(kMetadataCPFile, &err_str))
         return error(err_str.c_str());
 
+    std::thread(DoCheckpointCommittedWork).detach();
     return Status::ok();
 }
 
@@ -582,21 +597,31 @@
 
 // Read from the device
 // If we are validating, the read occurs as though the relocations had happened
+// returns the amount asked for or an empty buffer on error. Partial reads are considered a failure
 std::vector<char> relocatedRead(int device_fd, Relocations const& relocations, bool validating,
                                 sector_t sector, uint32_t size, uint32_t block_size) {
     if (!validating) {
         std::vector<char> buffer(size);
-        lseek64(device_fd, sector * kSectorSize, SEEK_SET);
-        read(device_fd, &buffer[0], size);
+        off64_t offset = sector * kSectorSize;
+        if (lseek64(device_fd, offset, SEEK_SET) != offset) {
+            return std::vector<char>();
+        }
+        if (read(device_fd, &buffer[0], size) != static_cast<ssize_t>(size)) {
+            return std::vector<char>();
+        }
         return buffer;
     }
 
     std::vector<char> buffer(size);
     for (uint32_t i = 0; i < size; i += block_size, sector += block_size / kSectorSize) {
         auto relocation = --relocations.upper_bound(sector);
-        lseek64(device_fd, (sector + relocation->second - relocation->first) * kSectorSize,
-                SEEK_SET);
-        read(device_fd, &buffer[i], block_size);
+        off64_t offset = (sector + relocation->second - relocation->first) * kSectorSize;
+        if (lseek64(device_fd, offset, SEEK_SET) != offset) {
+            return std::vector<char>();
+        }
+        if (read(device_fd, &buffer[i], block_size) != static_cast<ssize_t>(block_size)) {
+            return std::vector<char>();
+        }
     }
 
     return buffer;
@@ -619,7 +644,10 @@
         if (device_fd < 0) return error("Cannot open " + blockDevice);
 
         log_sector_v1_0 original_ls;
-        read(device_fd, reinterpret_cast<char*>(&original_ls), sizeof(original_ls));
+        if (read(device_fd, reinterpret_cast<char*>(&original_ls), sizeof(original_ls)) !=
+            sizeof(original_ls)) {
+            return error(EINVAL, "Cannot read sector");
+        }
         if (original_ls.magic == kPartialRestoreMagic) {
             validating = false;
             action = "Restoring";
@@ -627,11 +655,19 @@
             return error(EINVAL, "No magic");
         }
 
+        if (original_ls.block_size < sizeof(log_sector_v1_0)) {
+            return error(EINVAL, "Block size is invalid");
+        }
+
         LOG(INFO) << action << " " << original_ls.sequence << " log sectors";
 
         for (int sequence = original_ls.sequence; sequence >= 0 && status.isOk(); sequence--) {
             auto ls_buffer = relocatedRead(device_fd, relocations, validating, 0,
                                            original_ls.block_size, original_ls.block_size);
+            if (ls_buffer.size() != original_ls.block_size) {
+                status = error(EINVAL, "Failed to read log sector");
+                break;
+            }
             log_sector_v1_0& ls = *reinterpret_cast<log_sector_v1_0*>(&ls_buffer[0]);
 
             Used_Sectors used_sectors;
@@ -653,6 +689,14 @@
                 break;
             }
 
+            if (ls.header_size < sizeof(log_sector_v1_0) || ls.header_size > ls.block_size) {
+                status = error(EINVAL, "Log sector header size is invalid");
+                break;
+            }
+            if (ls.count < 1 || ls.count > (ls.block_size - ls.header_size) / sizeof(log_entry)) {
+                status = error(EINVAL, "Log sector count is invalid");
+                break;
+            }
             LOG(INFO) << action << " from log sector " << ls.sequence;
             for (log_entry* le =
                      reinterpret_cast<log_entry*>(&ls_buffer[ls.header_size]) + ls.count - 1;
@@ -662,8 +706,16 @@
                              << " to " << le->source << " with checksum " << std::hex
                              << le->checksum;
 
+                if (ls.block_size > UINT_MAX - le->size || le->size < ls.block_size) {
+                    status = error(EINVAL, "log entry is invalid");
+                    break;
+                }
                 auto buffer = relocatedRead(device_fd, relocations, validating, le->dest, le->size,
                                             ls.block_size);
+                if (buffer.size() != le->size) {
+                    status = error(EINVAL, "Failed to read sector");
+                    break;
+                }
                 uint32_t checksum = le->source / (ls.block_size / kSectorSize);
                 for (size_t i = 0; i < le->size; i += ls.block_size) {
                     crc32(&buffer[i], ls.block_size, &checksum);
@@ -696,8 +748,17 @@
             LOG(WARNING) << "Checkpoint validation failed - attempting to roll forward";
             auto buffer = relocatedRead(device_fd, relocations, false, original_ls.sector0,
                                         original_ls.block_size, original_ls.block_size);
-            lseek64(device_fd, 0, SEEK_SET);
-            write(device_fd, &buffer[0], original_ls.block_size);
+            if (buffer.size() != original_ls.block_size) {
+                return error(EINVAL, "Failed to read original sector");
+            }
+
+            if (lseek64(device_fd, 0, SEEK_SET) != 0) {
+                return error(EINVAL, "Failed to seek to sector 0");
+            }
+            if (write(device_fd, &buffer[0], original_ls.block_size) !=
+                static_cast<ssize_t>(original_ls.block_size)) {
+                return error(EINVAL, "Failed to write original sector");
+            }
             return Status::ok();
         }
 
diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index f871a32..903d36b 100644
--- a/FsCrypt.cpp
+++ b/FsCrypt.cpp
@@ -16,6 +16,7 @@
 
 #include "FsCrypt.h"
 
+#include "Checkpoint.h"
 #include "KeyStorage.h"
 #include "KeyUtil.h"
 #include "Utils.h"
@@ -96,9 +97,15 @@
 const std::string data_user_0_dir = std::string() + DATA_MNT_POINT + "/user/0";
 const std::string media_obb_dir = std::string() + DATA_MNT_POINT + "/media/obb";
 
-// Some users are ephemeral, don't try to wipe their keys from disk
+// The file encryption options to use on the /data filesystem
+EncryptionOptions s_data_options;
+
+// Some users are ephemeral; don't try to store or wipe their keys on disk.
 std::set<userid_t> s_ephemeral_users;
 
+// New CE keys that haven't been committed to disk yet
+std::map<userid_t, KeyBuffer> s_new_ce_keys;
+
 // The system DE encryption policy
 EncryptionPolicy s_device_policy;
 
@@ -106,10 +113,17 @@
 std::map<userid_t, EncryptionPolicy> s_de_policies;
 std::map<userid_t, EncryptionPolicy> s_ce_policies;
 
+// CE key fixation operations that have been deferred to checkpoint commit
+std::map<std::string, std::string> s_deferred_fixations;
+
 }  // namespace
 
 // Returns KeyGeneration suitable for key as described in EncryptionOptions
 static KeyGeneration makeGen(const EncryptionOptions& options) {
+    if (options.version == 0) {
+        LOG(ERROR) << "EncryptionOptions not initialized";
+        return android::vold::neverGen();
+    }
     return KeyGeneration{FSCRYPT_MAX_KEY_SIZE, true, options.use_hw_wrapped_key};
 }
 
@@ -176,20 +190,23 @@
 }
 
 // Discard all keys but the named one; rename it to canonical name.
-// No point in acting on errors in this; ignore them.
-static void fixate_user_ce_key(const std::string& directory_path, const std::string& to_fix,
+static bool fixate_user_ce_key(const std::string& directory_path, const std::string& to_fix,
                                const std::vector<std::string>& paths) {
+    bool need_sync = false;
     for (auto const other_path : paths) {
         if (other_path != to_fix) {
             android::vold::destroyKey(other_path);
+            need_sync = true;
         }
     }
     auto const current_path = get_ce_key_current_path(directory_path);
     if (to_fix != current_path) {
         LOG(DEBUG) << "Renaming " << to_fix << " to " << current_path;
-        if (!android::vold::RenameKeyDir(to_fix, current_path)) return;
+        if (!android::vold::RenameKeyDir(to_fix, current_path)) return false;
+        need_sync = true;
     }
-    android::vold::FsyncDirectory(directory_path);
+    if (need_sync && !android::vold::FsyncDirectory(directory_path)) return false;
+    return true;
 }
 
 static bool read_and_fixate_user_ce_key(userid_t user_id,
@@ -201,6 +218,7 @@
         LOG(DEBUG) << "Trying user CE key " << ce_key_path;
         if (retrieveKey(ce_key_path, auth, ce_key)) {
             LOG(DEBUG) << "Successfully retrieved key";
+            s_deferred_fixations.erase(directory_path);
             fixate_user_ce_key(directory_path, ce_key_path, paths);
             return true;
         }
@@ -236,19 +254,19 @@
            StartsWith(name, "vd");
 }
 
-// Retrieve the options to use for encryption policies on the /data filesystem.
-static bool get_data_file_encryption_options(EncryptionOptions* options) {
+// Sets s_data_options to the file encryption options for the /data filesystem.
+static bool init_data_file_encryption_options() {
     auto entry = GetEntryForMountPoint(&fstab_default, DATA_MNT_POINT);
     if (entry == nullptr) {
         LOG(ERROR) << "No mount point entry for " << DATA_MNT_POINT;
         return false;
     }
-    if (!ParseOptions(entry->encryption_options, options)) {
+    if (!ParseOptions(entry->encryption_options, &s_data_options)) {
         LOG(ERROR) << "Unable to parse encryption options for " << DATA_MNT_POINT ": "
                    << entry->encryption_options;
         return false;
     }
-    if ((options->flags & FSCRYPT_POLICY_FLAG_IV_INO_LBLK_32) &&
+    if ((s_data_options.flags & FSCRYPT_POLICY_FLAG_IV_INO_LBLK_32) &&
         !MightBeEmmcStorage(entry->blk_device)) {
         LOG(ERROR) << "The emmc_optimized encryption flag is only allowed on eMMC storage.  Remove "
                       "this flag from the device's fstab";
@@ -259,6 +277,10 @@
 
 static bool install_storage_key(const std::string& mountpoint, const EncryptionOptions& options,
                                 const KeyBuffer& key, EncryptionPolicy* policy) {
+    if (options.version == 0) {
+        LOG(ERROR) << "EncryptionOptions not initialized";
+        return false;
+    }
     KeyBuffer ephemeral_wrapped_key;
     if (options.use_hw_wrapped_key) {
         if (!exportWrappedStorageKey(key, &ephemeral_wrapped_key)) {
@@ -297,12 +319,10 @@
 static bool read_and_install_user_ce_key(userid_t user_id,
                                          const android::vold::KeyAuthentication& auth) {
     if (s_ce_policies.count(user_id) != 0) return true;
-    EncryptionOptions options;
-    if (!get_data_file_encryption_options(&options)) return false;
     KeyBuffer ce_key;
     if (!read_and_fixate_user_ce_key(user_id, auth, &ce_key)) return false;
     EncryptionPolicy ce_policy;
-    if (!install_storage_key(DATA_MNT_POINT, options, ce_key, &ce_policy)) return false;
+    if (!install_storage_key(DATA_MNT_POINT, s_data_options, ce_key, &ce_policy)) return false;
     s_ce_policies[user_id] = ce_policy;
     LOG(DEBUG) << "Installed ce key for user " << user_id;
     return true;
@@ -337,39 +357,50 @@
     return true;
 }
 
-// NB this assumes that there is only one thread listening for crypt commands, because
-// it creates keys in a fixed location.
-static bool create_and_install_user_keys(userid_t user_id, bool create_ephemeral) {
-    EncryptionOptions options;
-    if (!get_data_file_encryption_options(&options)) return false;
-    KeyBuffer de_key, ce_key;
-    if (!generateStorageKey(makeGen(options), &de_key)) return false;
-    if (!generateStorageKey(makeGen(options), &ce_key)) return false;
-    if (create_ephemeral) {
-        // If the key should be created as ephemeral, don't store it.
-        s_ephemeral_users.insert(user_id);
-    } else {
-        auto const directory_path = get_ce_key_directory_path(user_id);
-        if (!prepare_dir(directory_path, 0700, AID_ROOT, AID_ROOT)) return false;
-        auto const paths = get_ce_key_paths(directory_path);
-        std::string ce_key_path;
-        if (!get_ce_key_new_path(directory_path, paths, &ce_key_path)) return false;
-        if (!android::vold::storeKeyAtomically(ce_key_path, user_key_temp, kEmptyAuthentication,
-                                               ce_key))
-            return false;
-        fixate_user_ce_key(directory_path, ce_key_path, paths);
-        // Write DE key second; once this is written, all is good.
-        if (!android::vold::storeKeyAtomically(get_de_key_path(user_id), user_key_temp,
-                                               kEmptyAuthentication, de_key))
-            return false;
-    }
+// Checks whether the DE key directory exists for the given user.
+static bool de_key_exists(userid_t user_id) {
+    return android::vold::pathExists(get_de_key_path(user_id));
+}
+
+// Checks whether at least one CE key subdirectory exists for the given user.
+static bool ce_key_exists(userid_t user_id) {
+    auto directory_path = get_ce_key_directory_path(user_id);
+    // The common case is that "$dir/current" exists, so check for that first.
+    if (android::vold::pathExists(get_ce_key_current_path(directory_path))) return true;
+
+    // Else, there could still be another subdirectory of $dir (if a crash
+    // occurred during fixate_user_ce_key()), so check for one.
+    return android::vold::pathExists(directory_path) && !get_ce_key_paths(directory_path).empty();
+}
+
+static bool create_de_key(userid_t user_id, bool ephemeral) {
+    KeyBuffer de_key;
+    if (!generateStorageKey(makeGen(s_data_options), &de_key)) return false;
+    if (!ephemeral && !android::vold::storeKeyAtomically(get_de_key_path(user_id), user_key_temp,
+                                                         kEmptyAuthentication, de_key))
+        return false;
     EncryptionPolicy de_policy;
-    if (!install_storage_key(DATA_MNT_POINT, options, de_key, &de_policy)) return false;
+    if (!install_storage_key(DATA_MNT_POINT, s_data_options, de_key, &de_policy)) return false;
     s_de_policies[user_id] = de_policy;
+    LOG(INFO) << "Created DE key for user " << user_id;
+    return true;
+}
+
+static bool create_ce_key(userid_t user_id, bool ephemeral) {
+    KeyBuffer ce_key;
+    if (!generateStorageKey(makeGen(s_data_options), &ce_key)) return false;
+    if (!ephemeral) {
+        if (!prepare_dir(get_ce_key_directory_path(user_id), 0700, AID_ROOT, AID_ROOT))
+            return false;
+        // We don't store the CE key on disk here, since here we don't have the
+        // secret needed to do so securely.  Instead, we cache it in memory for
+        // now, and we store it later in fscrypt_set_user_key_protection().
+        s_new_ce_keys.insert({user_id, ce_key});
+    }
     EncryptionPolicy ce_policy;
-    if (!install_storage_key(DATA_MNT_POINT, options, ce_key, &ce_policy)) return false;
+    if (!install_storage_key(DATA_MNT_POINT, s_data_options, ce_key, &ce_policy)) return false;
     s_ce_policies[user_id] = ce_policy;
-    LOG(DEBUG) << "Created keys for user " << user_id;
+    LOG(INFO) << "Created CE key for user " << user_id;
     return true;
 }
 
@@ -391,8 +422,6 @@
 }
 
 static bool load_all_de_keys() {
-    EncryptionOptions options;
-    if (!get_data_file_encryption_options(&options)) return false;
     auto de_dir = user_key_dir + "/de";
     auto dirp = std::unique_ptr<DIR, int (*)(DIR*)>(opendir(de_dir.c_str()), closedir);
     if (!dirp) {
@@ -423,7 +452,7 @@
             return false;
         }
         EncryptionPolicy de_policy;
-        if (!install_storage_key(DATA_MNT_POINT, options, de_key, &de_policy)) return false;
+        if (!install_storage_key(DATA_MNT_POINT, s_data_options, de_key, &de_policy)) return false;
         auto ret = s_de_policies.insert({user_id, de_policy});
         if (!ret.second && ret.first->second != de_policy) {
             LOG(ERROR) << "DE policy for user" << user_id << " changed";
@@ -450,17 +479,17 @@
 bool fscrypt_initialize_systemwide_keys() {
     LOG(INFO) << "fscrypt_initialize_systemwide_keys";
 
-    EncryptionOptions options;
-    if (!get_data_file_encryption_options(&options)) return false;
+    if (!init_data_file_encryption_options()) return false;
 
     KeyBuffer device_key;
     if (!retrieveOrGenerateKey(device_key_path, device_key_temp, kEmptyAuthentication,
-                               makeGen(options), &device_key))
+                               makeGen(s_data_options), &device_key))
         return false;
 
     // This initializes s_device_policy, which is a global variable so that
     // fscrypt_init_user0() can access it later.
-    if (!install_storage_key(DATA_MNT_POINT, options, device_key, &s_device_policy)) return false;
+    if (!install_storage_key(DATA_MNT_POINT, s_data_options, device_key, &s_device_policy))
+        return false;
 
     std::string options_string;
     if (!OptionsToString(s_device_policy.options, &options_string)) {
@@ -475,9 +504,10 @@
     LOG(INFO) << "Wrote system DE key reference to:" << ref_filename;
 
     KeyBuffer per_boot_key;
-    if (!generateStorageKey(makeGen(options), &per_boot_key)) return false;
+    if (!generateStorageKey(makeGen(s_data_options), &per_boot_key)) return false;
     EncryptionPolicy per_boot_policy;
-    if (!install_storage_key(DATA_MNT_POINT, options, per_boot_key, &per_boot_policy)) return false;
+    if (!install_storage_key(DATA_MNT_POINT, s_data_options, per_boot_key, &per_boot_policy))
+        return false;
     std::string per_boot_ref_filename = std::string("/data") + fscrypt_key_per_boot_ref;
     if (!android::vold::writeStringToFile(per_boot_policy.key_raw_ref, per_boot_ref_filename))
         return false;
@@ -504,8 +534,17 @@
     // opportunity to also set the encryption policy of /data/data right away.
     EncryptionPolicy ce_policy;
     if (lookup_policy(s_ce_policies, 0, &ce_policy)) {
-        if (!prepare_dir_with_policy(data_data_dir, 0771, AID_SYSTEM, AID_SYSTEM, ce_policy))
-            return false;
+        if (!prepare_dir_with_policy(data_data_dir, 0771, AID_SYSTEM, AID_SYSTEM, ce_policy)) {
+            // Preparing /data/data failed, yet we had just generated a new CE
+            // key because one wasn't stored.  Before erroring out, try deleting
+            // the directory and retrying, as it's possible that the directory
+            // exists with different CE policy from an interrupted first boot.
+            if (rmdir(data_data_dir.c_str()) != 0) {
+                PLOG(ERROR) << "rmdir " << data_data_dir << " failed";
+            }
+            if (!prepare_dir_with_policy(data_data_dir, 0771, AID_SYSTEM, AID_SYSTEM, ce_policy))
+                return false;
+        }
     } else {
         if (!prepare_dir(data_data_dir, 0771, AID_SYSTEM, AID_SYSTEM)) return false;
         // EnsurePolicy() will have to happen later, in fscrypt_prepare_user_storage().
@@ -541,9 +580,13 @@
         if (!prepare_dir(user_key_dir, 0700, AID_ROOT, AID_ROOT)) return false;
         if (!prepare_dir(user_key_dir + "/ce", 0700, AID_ROOT, AID_ROOT)) return false;
         if (!prepare_dir(user_key_dir + "/de", 0700, AID_ROOT, AID_ROOT)) return false;
-        if (!android::vold::pathExists(get_de_key_path(0))) {
-            if (!create_and_install_user_keys(0, false)) return false;
-        }
+
+        // Create user 0's DE and CE keys if they don't already exist.  Check
+        // each key independently, since if the first boot was interrupted it is
+        // possible that the DE key exists but the CE key does not.
+        if (!de_key_exists(0) && !create_de_key(0, false)) return false;
+        if (!ce_key_exists(0) && !create_ce_key(0, false)) return false;
+
         // TODO: switch to loading only DE_0 here once framework makes
         // explicit calls to install DE keys for secondary users
         if (!load_all_de_keys()) return false;
@@ -584,9 +627,9 @@
         // FIXME should we fail the command?
         return true;
     }
-    if (!create_and_install_user_keys(user_id, ephemeral)) {
-        return false;
-    }
+    if (!create_de_key(user_id, ephemeral)) return false;
+    if (!create_ce_key(user_id, ephemeral)) return false;
+    if (ephemeral) s_ephemeral_users.insert(user_id);
     return true;
 }
 
@@ -620,6 +663,7 @@
         drop_caches_if_needed();
     }
     s_ce_policies.erase(user_id);
+    s_new_ce_keys.erase(user_id);
     return success;
 }
 
@@ -634,14 +678,14 @@
     success &= lookup_policy(s_de_policies, user_id, &de_policy) &&
                android::vold::evictKey(DATA_MNT_POINT, de_policy);
     s_de_policies.erase(user_id);
-    auto it = s_ephemeral_users.find(user_id);
-    if (it != s_ephemeral_users.end()) {
-        s_ephemeral_users.erase(it);
-    } else {
+    if (!s_ephemeral_users.erase(user_id)) {
         auto ce_path = get_ce_key_directory_path(user_id);
-        for (auto const path : get_ce_key_paths(ce_path)) {
-            success &= android::vold::destroyKey(path);
+        if (!s_new_ce_keys.erase(user_id)) {
+            for (auto const path : get_ce_key_paths(ce_path)) {
+                success &= android::vold::destroyKey(path);
+            }
         }
+        s_deferred_fixations.erase(ce_path);
         success &= destroy_dir(ce_path);
 
         auto de_key_path = get_de_key_path(user_id);
@@ -716,62 +760,102 @@
     return android::vold::destroyKey(path);
 }
 
-static bool fscrypt_rewrap_user_key(userid_t user_id, int serial,
-                                    const android::vold::KeyAuthentication& retrieve_auth,
-                                    const android::vold::KeyAuthentication& store_auth) {
-    if (s_ephemeral_users.count(user_id) != 0) return true;
-    auto const directory_path = get_ce_key_directory_path(user_id);
-    KeyBuffer ce_key;
-    std::string ce_key_current_path = get_ce_key_current_path(directory_path);
-    if (retrieveKey(ce_key_current_path, retrieve_auth, &ce_key)) {
-        LOG(DEBUG) << "Successfully retrieved key";
-        // TODO(147732812): Remove this once Locksettingservice is fixed.
-        // Currently it calls fscrypt_clear_user_key_auth with a secret when lockscreen is
-        // changed from swipe to none or vice-versa
-    } else if (retrieveKey(ce_key_current_path, kEmptyAuthentication, &ce_key)) {
-        LOG(DEBUG) << "Successfully retrieved key with empty auth";
-    } else {
-        LOG(ERROR) << "Failed to retrieve key for user " << user_id;
+// (Re-)encrypts the user's CE key with the given secret.  This function handles
+// storing the CE key for a new user for the first time.  It also handles
+// re-encrypting the CE key upon upgrade from an Android version where the CE
+// key was stored with kEmptyAuthentication when the user didn't have an LSKF.
+// See the comments below for the different cases handled.
+bool fscrypt_set_user_key_protection(userid_t user_id, const std::string& secret_hex) {
+    LOG(DEBUG) << "fscrypt_set_user_key_protection " << user_id;
+    if (!IsFbeEnabled()) return true;
+    auto auth = authentication_from_hex(secret_hex);
+    if (!auth) return false;
+    if (auth->secret.empty()) {
+        LOG(ERROR) << "fscrypt_set_user_key_protection: secret must be nonempty";
         return false;
     }
+    // We shouldn't store any keys for ephemeral users.
+    if (s_ephemeral_users.count(user_id) != 0) {
+        LOG(DEBUG) << "Not storing key because user is ephemeral";
+        return true;
+    }
+    KeyBuffer ce_key;
+    auto it = s_new_ce_keys.find(user_id);
+    if (it != s_new_ce_keys.end()) {
+        // If the key exists in s_new_ce_keys, then the key is a
+        // not-yet-committed key for a new user, and we are committing it here.
+        // This happens when the user's synthetic password is created.
+        ce_key = it->second;
+    } else if (ce_key_exists(user_id)) {
+        // If the key doesn't exist in s_new_ce_keys but does exist on-disk,
+        // then we are setting the protection on an existing key.  This happens
+        // at upgrade time, when CE keys that were previously protected by
+        // kEmptyAuthentication are encrypted by the user's synthetic password.
+        LOG(DEBUG) << "CE key already exists on-disk; re-protecting it with the given secret";
+        if (!read_and_fixate_user_ce_key(user_id, kEmptyAuthentication, &ce_key)) {
+            LOG(ERROR) << "Failed to retrieve CE key for user " << user_id << " using empty auth";
+            // Before failing, also check whether the key is already protected
+            // with the given secret.  This isn't expected, but in theory it
+            // could happen if an upgrade is requested for a user more than once
+            // due to a power-off or other interruption.
+            if (read_and_fixate_user_ce_key(user_id, *auth, &ce_key)) {
+                LOG(WARNING) << "CE key is already protected by given secret";
+                return true;
+            }
+            // The key isn't protected by either kEmptyAuthentication or by
+            // |auth|.  This should never happen, and there's nothing we can do
+            // besides return an error.
+            return false;
+        }
+    } else {
+        // If the key doesn't exist in memory or on-disk, then we need to
+        // generate it here, then commit it to disk.  This is needed after the
+        // unusual case where a non-system user was created during early boot,
+        // and then the device was force-rebooted before the boot completed.  In
+        // that case, the Android user record was committed but the CE key was
+        // not.  So the CE key was lost, and we need to regenerate it.  This
+        // should be fine, since the key should not have been used yet.
+        LOG(WARNING) << "CE key not found!  Regenerating it";
+        if (!create_ce_key(user_id, false)) return false;
+        ce_key = s_new_ce_keys.find(user_id)->second;
+    }
+
+    auto const directory_path = get_ce_key_directory_path(user_id);
     auto const paths = get_ce_key_paths(directory_path);
     std::string ce_key_path;
     if (!get_ce_key_new_path(directory_path, paths, &ce_key_path)) return false;
-    if (!android::vold::storeKeyAtomically(ce_key_path, user_key_temp, store_auth, ce_key))
-        return false;
-    return true;
-}
+    if (!android::vold::storeKeyAtomically(ce_key_path, user_key_temp, *auth, ce_key)) return false;
 
-bool fscrypt_add_user_key_auth(userid_t user_id, int serial, const std::string& secret_hex) {
-    LOG(DEBUG) << "fscrypt_add_user_key_auth " << user_id << " serial=" << serial;
-    if (!IsFbeEnabled()) return true;
-    auto auth = authentication_from_hex(secret_hex);
-    if (!auth) return false;
-    return fscrypt_rewrap_user_key(user_id, serial, kEmptyAuthentication, *auth);
-}
-
-bool fscrypt_clear_user_key_auth(userid_t user_id, int serial, const std::string& secret_hex) {
-    LOG(DEBUG) << "fscrypt_clear_user_key_auth " << user_id << " serial=" << serial;
-    if (!IsFbeEnabled()) return true;
-    auto auth = authentication_from_hex(secret_hex);
-    if (!auth) return false;
-    return fscrypt_rewrap_user_key(user_id, serial, *auth, kEmptyAuthentication);
-}
-
-bool fscrypt_fixate_newest_user_key_auth(userid_t user_id) {
-    LOG(DEBUG) << "fscrypt_fixate_newest_user_key_auth " << user_id;
-    if (!IsFbeEnabled()) return true;
-    if (s_ephemeral_users.count(user_id) != 0) return true;
-    auto const directory_path = get_ce_key_directory_path(user_id);
-    auto const paths = get_ce_key_paths(directory_path);
-    if (paths.empty()) {
-        LOG(ERROR) << "No ce keys present, cannot fixate for user " << user_id;
-        return false;
+    // Fixate the key, i.e. delete all other bindings of it.  (In practice this
+    // just means the kEmptyAuthentication binding, if there is one.)  However,
+    // if a userdata filesystem checkpoint is pending, then we need to delay the
+    // fixation until the checkpoint has been committed, since deleting keys
+    // from Keystore cannot be rolled back.
+    if (android::vold::cp_needsCheckpoint()) {
+        LOG(INFO) << "Deferring fixation of " << directory_path << " until checkpoint is committed";
+        s_deferred_fixations[directory_path] = ce_key_path;
+    } else {
+        s_deferred_fixations.erase(directory_path);
+        if (!fixate_user_ce_key(directory_path, ce_key_path, paths)) return false;
     }
-    fixate_user_ce_key(directory_path, paths[0], paths);
+
+    if (s_new_ce_keys.erase(user_id)) {
+        LOG(INFO) << "Stored CE key for new user " << user_id;
+    }
     return true;
 }
 
+void fscrypt_deferred_fixate_ce_keys() {
+    for (const auto& it : s_deferred_fixations) {
+        const auto& directory_path = it.first;
+        const auto& to_fix = it.second;
+        LOG(INFO) << "Doing deferred fixation of " << directory_path;
+        fixate_user_ce_key(directory_path, to_fix, get_ce_key_paths(directory_path));
+        // Continue on error.
+    }
+    s_deferred_fixations.clear();
+}
+
 std::vector<int> fscrypt_get_unlocked_users() {
     std::vector<int> user_ids;
     for (const auto& it : s_ce_policies) {
diff --git a/FsCrypt.h b/FsCrypt.h
index e5af487..8d84bdc 100644
--- a/FsCrypt.h
+++ b/FsCrypt.h
@@ -25,9 +25,8 @@
 extern bool fscrypt_init_user0_done;
 bool fscrypt_vold_create_user_key(userid_t user_id, int serial, bool ephemeral);
 bool fscrypt_destroy_user_key(userid_t user_id);
-bool fscrypt_add_user_key_auth(userid_t user_id, int serial, const std::string& secret);
-bool fscrypt_clear_user_key_auth(userid_t user_id, int serial, const std::string& secret);
-bool fscrypt_fixate_newest_user_key_auth(userid_t user_id);
+bool fscrypt_set_user_key_protection(userid_t user_id, const std::string& secret);
+void fscrypt_deferred_fixate_ce_keys();
 
 std::vector<int> fscrypt_get_unlocked_users();
 bool fscrypt_unlock_user_key(userid_t user_id, int serial, const std::string& secret);
diff --git a/KeyStorage.cpp b/KeyStorage.cpp
index 837bb1a..5090b4e 100644
--- a/KeyStorage.cpp
+++ b/KeyStorage.cpp
@@ -23,7 +23,6 @@
 #include <algorithm>
 #include <memory>
 #include <mutex>
-#include <thread>
 #include <vector>
 
 #include <errno.h>
@@ -231,9 +230,8 @@
     return true;
 }
 
-static void DeferredCommitKeys() {
-    android::base::WaitForProperty("vold.checkpoint_committed", "1");
-    LOG(INFO) << "Committing upgraded keys";
+void DeferredCommitKeystoreKeys() {
+    LOG(INFO) << "Committing upgraded Keystore keys";
     Keystore keystore;
     if (!keystore) {
         LOG(ERROR) << "Failed to open Keystore; old keys won't be deleted from Keystore";
@@ -241,10 +239,11 @@
     }
     std::lock_guard<std::mutex> lock(key_upgrade_lock);
     for (auto& dir : key_dirs_to_commit) {
-        LOG(INFO) << "Committing upgraded key " << dir;
+        LOG(INFO) << "Committing upgraded Keystore key for " << dir;
         CommitUpgradedKey(keystore, dir);
     }
     key_dirs_to_commit.clear();
+    LOG(INFO) << "Done committing upgraded Keystore keys";
 }
 
 // Returns true if the Keystore key in |dir| has already been upgraded and is
@@ -260,7 +259,6 @@
 // that key_upgrade_lock is held and that a commit isn't already pending for the
 // directory.
 static void ScheduleKeyCommit(const std::string& dir) {
-    if (key_dirs_to_commit.empty()) std::thread(DeferredCommitKeys).detach();
     key_dirs_to_commit.push_back(dir);
 }
 
@@ -592,7 +590,7 @@
     if (!RenameKeyDir(tmp_path, key_path)) return false;
 
     if (!FsyncParentDirectory(key_path)) return false;
-    LOG(DEBUG) << "Created key: " << key_path;
+    LOG(DEBUG) << "Stored key " << key_path;
     return true;
 }
 
diff --git a/KeyStorage.h b/KeyStorage.h
index cc2f549..22453ea 100644
--- a/KeyStorage.h
+++ b/KeyStorage.h
@@ -41,6 +41,8 @@
 bool createSecdiscardable(const std::string& path, std::string* hash);
 bool readSecdiscardable(const std::string& path, std::string* hash);
 
+void DeferredCommitKeystoreKeys();
+
 // Renames a key directory while also managing deferred commits appropriately.
 // This method should be used whenever a key directory needs to be moved/renamed.
 bool RenameKeyDir(const std::string& old_name, const std::string& new_name);
diff --git a/VoldNativeService.cpp b/VoldNativeService.cpp
index 601323f..5a89ea7 100644
--- a/VoldNativeService.cpp
+++ b/VoldNativeService.cpp
@@ -612,27 +612,11 @@
     return translateBool(fscrypt_destroy_user_key(userId));
 }
 
-binder::Status VoldNativeService::addUserKeyAuth(int32_t userId, int32_t userSerial,
-                                                 const std::string& secret) {
+binder::Status VoldNativeService::setUserKeyProtection(int32_t userId, const std::string& secret) {
     ENFORCE_SYSTEM_OR_ROOT;
     ACQUIRE_CRYPT_LOCK;
 
-    return translateBool(fscrypt_add_user_key_auth(userId, userSerial, secret));
-}
-
-binder::Status VoldNativeService::clearUserKeyAuth(int32_t userId, int32_t userSerial,
-                                                   const std::string& secret) {
-    ENFORCE_SYSTEM_OR_ROOT;
-    ACQUIRE_CRYPT_LOCK;
-
-    return translateBool(fscrypt_clear_user_key_auth(userId, userSerial, secret));
-}
-
-binder::Status VoldNativeService::fixateNewestUserKeyAuth(int32_t userId) {
-    ENFORCE_SYSTEM_OR_ROOT;
-    ACQUIRE_CRYPT_LOCK;
-
-    return translateBool(fscrypt_fixate_newest_user_key_auth(userId));
+    return translateBool(fscrypt_set_user_key_protection(userId, secret));
 }
 
 binder::Status VoldNativeService::getUnlockedUsers(std::vector<int>* _aidl_return) {
diff --git a/VoldNativeService.h b/VoldNativeService.h
index 12a93f5..b3b4411 100644
--- a/VoldNativeService.h
+++ b/VoldNativeService.h
@@ -115,9 +115,7 @@
     binder::Status createUserKey(int32_t userId, int32_t userSerial, bool ephemeral);
     binder::Status destroyUserKey(int32_t userId);
 
-    binder::Status addUserKeyAuth(int32_t userId, int32_t userSerial, const std::string& secret);
-    binder::Status clearUserKeyAuth(int32_t userId, int32_t userSerial, const std::string& secret);
-    binder::Status fixateNewestUserKeyAuth(int32_t userId);
+    binder::Status setUserKeyProtection(int32_t userId, const std::string& secret);
 
     binder::Status getUnlockedUsers(std::vector<int>* _aidl_return);
     binder::Status unlockUserKey(int32_t userId, int32_t userSerial, const std::string& secret);
diff --git a/binder/android/os/IVold.aidl b/binder/android/os/IVold.aidl
index c798959..25dcb32 100644
--- a/binder/android/os/IVold.aidl
+++ b/binder/android/os/IVold.aidl
@@ -88,9 +88,7 @@
     void createUserKey(int userId, int userSerial, boolean ephemeral);
     void destroyUserKey(int userId);
 
-    void addUserKeyAuth(int userId, int userSerial, @utf8InCpp String secret);
-    void clearUserKeyAuth(int userId, int userSerial, @utf8InCpp String secret);
-    void fixateNewestUserKeyAuth(int userId);
+    void setUserKeyProtection(int userId, @utf8InCpp String secret);
 
     int[] getUnlockedUsers();
     void unlockUserKey(int userId, int userSerial, @utf8InCpp String secret);