diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index 7a5178d..e253aa9 100644
--- a/FsCrypt.cpp
+++ b/FsCrypt.cpp
@@ -314,6 +314,9 @@
     return true;
 }
 
+// Prepare a directory without assigning it an encryption policy.  The directory
+// will inherit the encryption policy of its parent directory, or will be
+// unencrypted if the parent directory is unencrypted.
 static bool prepare_dir(const std::string& dir, mode_t mode, uid_t uid, gid_t gid) {
     LOG(DEBUG) << "Preparing: " << dir;
     if (android::vold::PrepareDir(dir, mode, uid, gid, 0) != 0) {
@@ -323,6 +326,14 @@
     return true;
 }
 
+// Prepare a directory and assign it the given encryption policy.
+static bool prepare_dir_with_policy(const std::string& dir, mode_t mode, uid_t uid, gid_t gid,
+                                    const EncryptionPolicy& policy) {
+    if (!prepare_dir(dir, mode, uid, gid)) return false;
+    if (fscrypt_is_native() && !EnsurePolicy(policy, dir)) return false;
+    return true;
+}
+
 static bool destroy_dir(const std::string& dir) {
     LOG(DEBUG) << "Destroying: " << dir;
     if (rmdir(dir.c_str()) != 0 && errno != ENOENT) {
@@ -372,7 +383,6 @@
                           EncryptionPolicy* policy) {
     auto refi = key_map.find(user_id);
     if (refi == key_map.end()) {
-        LOG(DEBUG) << "Cannot find key for " << user_id;
         return false;
     }
     *policy = refi->second;
@@ -479,18 +489,29 @@
 }
 
 static bool prepare_special_dirs() {
-    // Create /data/user/0 and its bind-mount alias /data/data.  This *should*
-    // happen in fscrypt_prepare_user_storage().  However, it actually must be
-    // done early, before the rest of user 0's CE storage is prepared.  This is
-    // because zygote may need to set up app data isolation before then, which
-    // requires mounting a tmpfs over /data/data to ensure it remains hidden.
-    // This issue arises due to /data/data being in the top-level directory.
-    //
+    // Ensure that /data/data and its "alias" /data/user/0 exist, and create the
+    // bind mount of /data/data onto /data/user/0.  This *should* happen in
+    // fscrypt_prepare_user_storage().  However, it actually must be done early,
+    // before the rest of user 0's CE storage is prepared.  This is because
+    // zygote may need to set up app data isolation before then, which requires
+    // mounting a tmpfs over /data/data to ensure it remains hidden.  This issue
+    // arises due to /data/data being in the top-level directory.
+
     // /data/user/0 used to be a symlink to /data/data, so we must first delete
     // the old symlink if present.
     if (android::vold::IsSymlink(data_user_0_dir) && android::vold::Unlink(data_user_0_dir) != 0)
         return false;
-    if (!prepare_dir(data_data_dir, 0771, AID_SYSTEM, AID_SYSTEM)) return false;
+    // 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 (!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().
+    }
     if (!prepare_dir(data_user_0_dir, 0700, AID_SYSTEM, AID_SYSTEM)) return false;
     if (android::vold::BindMount(data_data_dir, data_user_0_dir) != 0) return false;
 
@@ -503,9 +524,13 @@
     //
     // We must tolerate /data/media/obb being unencrypted if it already exists
     // on-disk, since it used to be unencrypted (b/64566063).
-    bool encrypt_obb = !android::vold::pathExists(media_obb_dir) && fscrypt_is_native();
-    if (!prepare_dir(media_obb_dir, 0770, AID_MEDIA_RW, AID_MEDIA_RW)) return false;
-    if (encrypt_obb && !EnsurePolicy(s_device_policy, media_obb_dir)) return false;
+    if (android::vold::pathExists(media_obb_dir)) {
+        if (!prepare_dir(media_obb_dir, 0770, AID_MEDIA_RW, AID_MEDIA_RW)) return false;
+    } else {
+        if (!prepare_dir_with_policy(media_obb_dir, 0770, AID_MEDIA_RW, AID_MEDIA_RW,
+                                     s_device_policy))
+            return false;
+    }
     return true;
 }
 
@@ -514,25 +539,23 @@
 bool fscrypt_init_user0() {
     LOG(DEBUG) << "fscrypt_init_user0";
 
-    if (!prepare_special_dirs()) return false;
-
     if (fscrypt_is_native()) {
         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;
-            // Since /data/user/0 was created already, and directory creation
-            // and encryption should always happen together, encrypt
-            // /data/user/0 right away without waiting for the request to
-            // prepare user 0's CE storage.
-            if (!EnsurePolicy(s_ce_policies[0], data_user_0_dir)) 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;
     }
-    // We only prepare DE storage here, since user 0's CE key won't be installed
+
+    // Now that user 0's CE key has been created, we can prepare /data/data.
+    if (!prepare_special_dirs()) return false;
+
+    // With the exception of what is done by prepare_special_dirs() above, we
+    // only prepare DE storage here, since user 0's CE key won't be installed
     // yet unless it was just created.  The framework will prepare the user's CE
     // storage later, once their CE key is installed.
     if (!fscrypt_prepare_user_storage("", 0, 0, android::os::IVold::STORAGE_FLAG_DE)) {
@@ -883,11 +906,26 @@
         auto profiles_de_path = android::vold::BuildDataProfilesDePath(user_id);
 
         // DE_n key
+        EncryptionPolicy de_policy;
         auto system_de_path = android::vold::BuildDataSystemDePath(user_id);
         auto misc_de_path = android::vold::BuildDataMiscDePath(volume_uuid, user_id);
         auto vendor_de_path = android::vold::BuildDataVendorDePath(user_id);
         auto user_de_path = android::vold::BuildDataUserDePath(volume_uuid, user_id);
 
+        if (fscrypt_is_native()) {
+            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;
+                }
+            } 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)) {
+                    return false;
+                }
+            }
+        }
+
         if (volume_uuid.empty()) {
             if (!prepare_dir(system_legacy_path, 0700, AID_SYSTEM, AID_SYSTEM)) return false;
 #if MANAGE_MISC_DIRS
@@ -897,43 +935,49 @@
 #endif
             if (!prepare_dir(profiles_de_path, 0771, AID_SYSTEM, AID_SYSTEM)) return false;
 
-            if (!prepare_dir(system_de_path, 0770, AID_SYSTEM, AID_SYSTEM)) return false;
-            if (!prepare_dir(vendor_de_path, 0771, AID_ROOT, AID_ROOT)) return false;
+            if (!prepare_dir_with_policy(system_de_path, 0770, AID_SYSTEM, AID_SYSTEM, de_policy))
+                return false;
+            if (!prepare_dir_with_policy(vendor_de_path, 0771, AID_ROOT, AID_ROOT, de_policy))
+                return false;
         }
 
-        if (!prepare_dir(misc_de_path, 01771, AID_SYSTEM, AID_MISC)) return false;
-        if (!prepare_dir(user_de_path, 0771, AID_SYSTEM, AID_SYSTEM)) return false;
-
-        if (fscrypt_is_native()) {
-            EncryptionPolicy de_policy;
-            if (volume_uuid.empty()) {
-                if (!lookup_policy(s_de_policies, user_id, &de_policy)) return false;
-                if (!EnsurePolicy(de_policy, system_de_path)) return false;
-                if (!EnsurePolicy(de_policy, vendor_de_path)) return false;
-            } 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)) {
-                    return false;
-                }
-            }
-            if (!EnsurePolicy(de_policy, misc_de_path)) return false;
-            if (!EnsurePolicy(de_policy, user_de_path)) return false;
-        }
+        if (!prepare_dir_with_policy(misc_de_path, 01771, AID_SYSTEM, AID_MISC, de_policy))
+            return false;
+        if (!prepare_dir_with_policy(user_de_path, 0771, AID_SYSTEM, AID_SYSTEM, de_policy))
+            return false;
     }
 
     if (flags & android::os::IVold::STORAGE_FLAG_CE) {
         // CE_n key
+        EncryptionPolicy ce_policy;
         auto system_ce_path = android::vold::BuildDataSystemCePath(user_id);
         auto misc_ce_path = android::vold::BuildDataMiscCePath(volume_uuid, user_id);
         auto vendor_ce_path = android::vold::BuildDataVendorCePath(user_id);
         auto media_ce_path = android::vold::BuildDataMediaCePath(volume_uuid, user_id);
         auto user_ce_path = android::vold::BuildDataUserCePath(volume_uuid, user_id);
 
-        if (volume_uuid.empty()) {
-            if (!prepare_dir(system_ce_path, 0770, AID_SYSTEM, AID_SYSTEM)) return false;
-            if (!prepare_dir(vendor_ce_path, 0771, AID_ROOT, AID_ROOT)) return false;
+        if (fscrypt_is_native()) {
+            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;
+                }
+            } 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)) {
+                    return false;
+                }
+            }
         }
-        if (!prepare_dir(media_ce_path, 02770, AID_MEDIA_RW, AID_MEDIA_RW)) return false;
+
+        if (volume_uuid.empty()) {
+            if (!prepare_dir_with_policy(system_ce_path, 0770, AID_SYSTEM, AID_SYSTEM, ce_policy))
+                return false;
+            if (!prepare_dir_with_policy(vendor_ce_path, 0771, AID_ROOT, AID_ROOT, ce_policy))
+                return false;
+        }
+        if (!prepare_dir_with_policy(media_ce_path, 02770, AID_MEDIA_RW, AID_MEDIA_RW, ce_policy))
+            return false;
         // On devices without sdcardfs (kernel 5.4+), the path permissions aren't fixed
         // up automatically; therefore, use a default ACL, to ensure apps with MEDIA_RW
         // can keep reading external storage; in particular, this allows app cloning
@@ -942,26 +986,10 @@
         if (ret != android::OK) {
             return false;
         }
-
-        if (!prepare_dir(misc_ce_path, 01771, AID_SYSTEM, AID_MISC)) return false;
-        if (!prepare_dir(user_ce_path, 0771, AID_SYSTEM, AID_SYSTEM)) return false;
-
-        if (fscrypt_is_native()) {
-            EncryptionPolicy ce_policy;
-            if (volume_uuid.empty()) {
-                if (!lookup_policy(s_ce_policies, user_id, &ce_policy)) return false;
-                if (!EnsurePolicy(ce_policy, system_ce_path)) return false;
-                if (!EnsurePolicy(ce_policy, vendor_ce_path)) return false;
-            } 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)) {
-                    return false;
-                }
-            }
-            if (!EnsurePolicy(ce_policy, media_ce_path)) return false;
-            if (!EnsurePolicy(ce_policy, misc_ce_path)) return false;
-            if (!EnsurePolicy(ce_policy, user_ce_path)) return false;
-        }
+        if (!prepare_dir_with_policy(misc_ce_path, 01771, AID_SYSTEM, AID_MISC, ce_policy))
+            return false;
+        if (!prepare_dir_with_policy(user_ce_path, 0771, AID_SYSTEM, AID_SYSTEM, ce_policy))
+            return false;
 
         if (volume_uuid.empty()) {
             // Now that credentials have been installed, we can run restorecon