diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index 3d86ab8..ecb3c81 100644
--- a/FsCrypt.cpp
+++ b/FsCrypt.cpp
@@ -106,15 +106,25 @@
 // New CE keys that haven't been committed to disk yet
 std::map<userid_t, KeyBuffer> s_new_ce_keys;
 
+// CE key fixation operations that have been deferred to checkpoint commit
+std::map<std::string, std::string> s_deferred_fixations;
+
 // The system DE encryption policy
 EncryptionPolicy s_device_policy;
 
-// Map user ids to encryption policies
-std::map<userid_t, EncryptionPolicy> s_de_policies;
-std::map<userid_t, EncryptionPolicy> s_ce_policies;
+// Struct that holds the EncryptionPolicy for each CE or DE key that is currently installed
+// (added to the kernel) for a particular user
+struct UserPolicies {
+    // Internal storage policy.  Exists whenever a user's UserPolicies exists at all, and used
+    // instead of a map entry keyed by an empty UUID to make this invariant explicit.
+    EncryptionPolicy internal;
+    // Adoptable storage policies, indexed by (nonempty) volume UUID
+    std::map<std::string, EncryptionPolicy> adoptable;
+};
 
-// CE key fixation operations that have been deferred to checkpoint commit
-std::map<std::string, std::string> s_deferred_fixations;
+// The currently installed CE and DE keys for each user.  Protected by VolumeManager::mCryptLock.
+std::map<userid_t, UserPolicies> s_ce_policies;
+std::map<userid_t, UserPolicies> s_de_policies;
 
 }  // namespace
 
@@ -398,7 +408,7 @@
         return false;
     EncryptionPolicy de_policy;
     if (!install_storage_key(DATA_MNT_POINT, s_data_options, de_key, &de_policy)) return false;
-    s_de_policies[user_id] = de_policy;
+    s_de_policies[user_id].internal = de_policy;
     LOG(INFO) << "Created DE key for user " << user_id;
     return true;
 }
@@ -416,21 +426,11 @@
     }
     EncryptionPolicy ce_policy;
     if (!install_storage_key(DATA_MNT_POINT, s_data_options, ce_key, &ce_policy)) return false;
-    s_ce_policies[user_id] = ce_policy;
+    s_ce_policies[user_id].internal = ce_policy;
     LOG(INFO) << "Created CE key for user " << user_id;
     return true;
 }
 
-static bool lookup_policy(const std::map<userid_t, EncryptionPolicy>& key_map, userid_t user_id,
-                          EncryptionPolicy* policy) {
-    auto refi = key_map.find(user_id);
-    if (refi == key_map.end()) {
-        return false;
-    }
-    *policy = refi->second;
-    return true;
-}
-
 static bool is_numeric(const char* name) {
     for (const char* p = name; *p != '\0'; p++) {
         if (!isdigit(*p)) return false;
@@ -470,8 +470,8 @@
         }
         EncryptionPolicy de_policy;
         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) {
+        const auto& [existing, is_new] = s_de_policies.insert({user_id, {de_policy, {}}});
+        if (!is_new && existing->second.internal != de_policy) {
             LOG(ERROR) << "DE policy for user" << user_id << " changed";
             return false;
         }
@@ -484,9 +484,9 @@
 
 // Attempt to reinstall CE keys for users that we think are unlocked.
 static bool try_reload_ce_keys() {
-    for (const auto& it : s_ce_policies) {
-        if (!android::vold::reloadKeyFromSessionKeyring(DATA_MNT_POINT, it.second)) {
-            LOG(ERROR) << "Failed to load CE key from session keyring for user " << it.first;
+    for (const auto& [user_id, user_policies] : s_ce_policies) {
+        if (!android::vold::reloadKeyFromSessionKeyring(DATA_MNT_POINT, user_policies.internal)) {
+            LOG(ERROR) << "Failed to load CE key from session keyring for user " << user_id;
             return false;
         }
     }
@@ -549,8 +549,8 @@
     // On first boot, we'll be creating /data/data for the first time, and user
     // 0's CE key will be installed already since it was just created.  Take the
     // 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 (s_ce_policies.count(0) != 0) {
+        const EncryptionPolicy& ce_policy = s_ce_policies[0].internal;
         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
@@ -671,29 +671,34 @@
     }
 }
 
-static bool evict_ce_key(userid_t user_id) {
+// Evicts all the user's keys of one type from all volumes (internal and adoptable).
+// This evicts either CE keys or DE keys, depending on which map is passed.
+static bool evict_user_keys(std::map<userid_t, UserPolicies>& policy_map, userid_t user_id) {
     bool success = true;
-    EncryptionPolicy policy;
-    // If we haven't loaded the CE key, no need to evict it.
-    if (lookup_policy(s_ce_policies, user_id, &policy)) {
-        success &= android::vold::evictKey(DATA_MNT_POINT, policy);
+    auto it = policy_map.find(user_id);
+    if (it != policy_map.end()) {
+        const UserPolicies& policies = it->second;
+        success &= android::vold::evictKey(BuildDataPath(""), policies.internal);
+        for (const auto& [volume_uuid, policy] : policies.adoptable) {
+            success &= android::vold::evictKey(BuildDataPath(volume_uuid), policy);
+        }
+        policy_map.erase(it);
         drop_caches_if_needed();
     }
-    s_ce_policies.erase(user_id);
     return success;
 }
 
+// Evicts and destroys all CE and DE keys for a user.  This is called when the user is removed.
 bool fscrypt_destroy_user_key(userid_t user_id) {
     LOG(DEBUG) << "fscrypt_destroy_user_key(" << user_id << ")";
     if (!IsFbeEnabled()) {
         return true;
     }
     bool success = true;
-    success &= evict_ce_key(user_id);
-    EncryptionPolicy de_policy;
-    success &= lookup_policy(s_de_policies, user_id, &de_policy) &&
-               android::vold::evictKey(DATA_MNT_POINT, de_policy);
-    s_de_policies.erase(user_id);
+
+    success &= evict_user_keys(s_ce_policies, user_id);
+    success &= evict_user_keys(s_de_policies, user_id);
+
     if (!s_ephemeral_users.erase(user_id)) {
         auto ce_path = get_ce_key_directory_path(user_id);
         if (!s_new_ce_keys.erase(user_id)) {
@@ -746,7 +751,7 @@
 }
 
 static bool read_or_create_volkey(const std::string& misc_path, const std::string& volume_uuid,
-                                  EncryptionPolicy* policy) {
+                                  UserPolicies& user_policies, EncryptionPolicy* policy) {
     auto secdiscardable_path = volume_secdiscardable_path(volume_uuid);
     std::string secdiscardable_hash;
     if (android::vold::pathExists(secdiscardable_path)) {
@@ -767,6 +772,7 @@
     if (!retrieveOrGenerateKey(key_path, key_path + "_tmp", auth, makeGen(options), &key))
         return false;
     if (!install_storage_key(BuildDataPath(volume_uuid), options, key, policy)) return false;
+    user_policies.adoptable[volume_uuid] = *policy;
     return true;
 }
 
@@ -874,13 +880,15 @@
 
 std::vector<int> fscrypt_get_unlocked_users() {
     std::vector<int> user_ids;
-    for (const auto& it : s_ce_policies) {
-        user_ids.push_back(it.first);
+    for (const auto& [user_id, user_policies] : s_ce_policies) {
+        user_ids.push_back(user_id);
     }
     return user_ids;
 }
 
-// TODO: rename to 'install' for consistency, and take flags to know which keys to install
+// Unlocks internal CE storage for the given user.  This only unlocks internal storage, since
+// fscrypt_prepare_user_storage() has to be called for each adoptable storage volume anyway (since
+// the volume might have been absent when the user was created), and that handles the unlocking.
 bool fscrypt_unlock_user_key(userid_t user_id, int serial, const std::string& secret_hex) {
     LOG(DEBUG) << "fscrypt_unlock_user_key " << user_id << " serial=" << serial;
     if (!IsFbeEnabled()) return true;
@@ -894,18 +902,16 @@
     if (!read_and_fixate_user_ce_key(user_id, *auth, &ce_key)) return false;
     EncryptionPolicy ce_policy;
     if (!install_storage_key(DATA_MNT_POINT, s_data_options, ce_key, &ce_policy)) return false;
-    s_ce_policies[user_id] = ce_policy;
+    s_ce_policies[user_id].internal = ce_policy;
     LOG(DEBUG) << "Installed ce key for user " << user_id;
     return true;
 }
 
-// TODO: rename to 'evict' for consistency
+// Locks CE storage for the given user.  This locks both internal and adoptable storage.
 bool fscrypt_lock_user_key(userid_t user_id) {
     LOG(DEBUG) << "fscrypt_lock_user_key " << user_id;
-    if (IsFbeEnabled()) {
-        return evict_ce_key(user_id);
-    }
-    return true;
+    if (!IsFbeEnabled()) return true;
+    return evict_user_keys(s_ce_policies, user_id);
 }
 
 static bool prepare_subdirs(const std::string& action, const std::string& volume_uuid,
@@ -955,14 +961,18 @@
         auto user_de_path = android::vold::BuildDataUserDePath(volume_uuid, user_id);
 
         if (IsFbeEnabled()) {
+            auto it = s_de_policies.find(user_id);
+            if (it == s_de_policies.end()) {
+                LOG(ERROR) << "Cannot find DE policy for user " << user_id;
+                return false;
+            }
+            UserPolicies& user_de_policies = it->second;
             if (volume_uuid.empty()) {
-                if (!lookup_policy(s_de_policies, user_id, &de_policy)) {
-                    LOG(ERROR) << "Cannot find DE policy for user " << user_id;
-                    return false;
-                }
+                de_policy = user_de_policies.internal;
             } else {
                 auto misc_de_empty_volume_path = android::vold::BuildDataMiscDePath("", user_id);
-                if (!read_or_create_volkey(misc_de_empty_volume_path, volume_uuid, &de_policy)) {
+                if (!read_or_create_volkey(misc_de_empty_volume_path, volume_uuid, user_de_policies,
+                                           &de_policy)) {
                     return false;
                 }
             }
@@ -999,14 +1009,18 @@
         auto user_ce_path = android::vold::BuildDataUserCePath(volume_uuid, user_id);
 
         if (IsFbeEnabled()) {
+            auto it = s_ce_policies.find(user_id);
+            if (it == s_ce_policies.end()) {
+                LOG(ERROR) << "Cannot find CE policy for user " << user_id;
+                return false;
+            }
+            UserPolicies& user_ce_policies = it->second;
             if (volume_uuid.empty()) {
-                if (!lookup_policy(s_ce_policies, user_id, &ce_policy)) {
-                    LOG(ERROR) << "Cannot find CE policy for user " << user_id;
-                    return false;
-                }
+                ce_policy = user_ce_policies.internal;
             } else {
                 auto misc_ce_empty_volume_path = android::vold::BuildDataMiscCePath("", user_id);
-                if (!read_or_create_volkey(misc_ce_empty_volume_path, volume_uuid, &ce_policy)) {
+                if (!read_or_create_volkey(misc_ce_empty_volume_path, volume_uuid, user_ce_policies,
+                                           &ce_policy)) {
                     return false;
                 }
             }
@@ -1136,6 +1150,13 @@
     return res;
 }
 
+static void erase_volume_policies(std::map<userid_t, UserPolicies>& policy_map,
+                                  const std::string& volume_uuid) {
+    for (auto& [user_id, user_policies] : policy_map) {
+        user_policies.adoptable.erase(volume_uuid);
+    }
+}
+
 // Destroys all CE and DE keys for an adoptable storage volume that is permanently going away.
 // Requires VolumeManager::mCryptLock.
 bool fscrypt_destroy_volume_keys(const std::string& volume_uuid) {
@@ -1146,5 +1167,10 @@
     res &= android::vold::runSecdiscardSingle(secdiscardable_path);
     res &= destroy_volume_keys("/data/misc_ce", volume_uuid);
     res &= destroy_volume_keys("/data/misc_de", volume_uuid);
+    // Drop the CE and DE policies stored in memory, as they are not needed anymore.  Note that it's
+    // not necessary to also evict the corresponding keys from the kernel, as that happens
+    // automatically as a result of the volume being unmounted.
+    erase_volume_policies(s_ce_policies, volume_uuid);
+    erase_volume_policies(s_de_policies, volume_uuid);
     return res;
 }