diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index 477db7c..8df438f 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"
@@ -112,6 +113,9 @@
 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
@@ -214,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;
         }
@@ -676,6 +681,7 @@
                 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);
@@ -815,13 +821,37 @@
     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, *auth, ce_key)) return false;
-    if (!fixate_user_ce_key(directory_path, ce_key_path, paths)) 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;
+    }
+
     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) {