diff --git a/Android.mk b/Android.mk
index e22bf0f..f1804b6 100644
--- a/Android.mk
+++ b/Android.mk
@@ -88,7 +88,7 @@
 vold_conlyflags := -std=c11
 vold_cflags := -Werror -Wall -Wno-missing-field-initializers -Wno-unused-variable -Wno-unused-parameter
 
-required_modules :=
+required_modules := vold_prepare_subdirs
 ifeq ($(TARGET_USERIMAGES_USE_EXT4), true)
   required_modules += mke2fs
 endif
@@ -181,4 +181,30 @@
 
 include $(BUILD_EXECUTABLE)
 
+include $(CLEAR_VARS)
+
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+LOCAL_CLANG := true
+LOCAL_TIDY := $(common_local_tidy_enabled)
+LOCAL_TIDY_FLAGS := $(common_local_tidy_flags)
+LOCAL_TIDY_CHECKS := $(common_local_tidy_checks)
+LOCAL_SRC_FILES:= \
+    prepare_dir.cpp \
+
+LOCAL_MODULE:= prepare_dir
+LOCAL_SHARED_LIBRARIES := libbase libcutils libselinux
+LOCAL_CFLAGS := $(vold_cflags)
+LOCAL_CONLYFLAGS := $(vold_conlyflags)
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_MODULE:= vold_prepare_subdirs
+LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_SRC_FILES := vold_prepare_subdirs
+LOCAL_REQUIRED_MODULES := prepare_dir
+
+include $(BUILD_PREBUILT)
+
 include $(LOCAL_PATH)/tests/Android.mk
diff --git a/Ext4Crypt.cpp b/Ext4Crypt.cpp
index 48957c8..646a032 100644
--- a/Ext4Crypt.cpp
+++ b/Ext4Crypt.cpp
@@ -594,6 +594,18 @@
     return true;
 }
 
+static bool prepare_subdirs(const std::string& action, const std::string& dirtype,
+                            const std::string& volume_uuid, userid_t user_id,
+                            const std::string& path) {
+    if (0 != android::vold::ForkExecvp(std::vector<std::string>{"/system/bin/vold_prepare_subdirs",
+                                                                action, dirtype, volume_uuid,
+                                                                std::to_string(user_id), path})) {
+        LOG(ERROR) << "vold_prepare_subdirs failed on: " << path;
+        return false;
+    }
+    return true;
+}
+
 bool e4crypt_prepare_user_storage(const std::string& volume_uuid, userid_t user_id, int serial,
                                   int flags) {
     LOG(DEBUG) << "e4crypt_prepare_user_storage for volume " << escape_empty(volume_uuid)
@@ -632,6 +644,11 @@
             }
             if (!ensure_policy(de_raw_ref, user_de_path)) return false;
         }
+
+        if (volume_uuid.empty()) {
+            if (!prepare_subdirs("prepare", "misc_de", volume_uuid, user_id, misc_de_path))
+                return false;
+        }
     }
 
     if (flags & FLAG_STORAGE_CE) {
@@ -655,15 +672,20 @@
                 if (!ensure_policy(ce_raw_ref, system_ce_path)) return false;
                 if (!ensure_policy(ce_raw_ref, misc_ce_path)) return false;
 
-                // Now that credentials have been installed, we can run restorecon
-                // over these paths
-                // NOTE: these paths need to be kept in sync with libselinux
-                android::vold::RestoreconRecursive(system_ce_path);
-                android::vold::RestoreconRecursive(misc_ce_path);
             }
             if (!ensure_policy(ce_raw_ref, media_ce_path)) return false;
             if (!ensure_policy(ce_raw_ref, user_ce_path)) return false;
         }
+
+        if (volume_uuid.empty()) {
+            if (!prepare_subdirs("prepare", "misc_ce", volume_uuid, user_id, misc_ce_path))
+                return false;
+            // Now that credentials have been installed, we can run restorecon
+            // over these paths
+            // NOTE: these paths need to be kept in sync with libselinux
+            android::vold::RestoreconRecursive(system_ce_path);
+            android::vold::RestoreconRecursive(misc_ce_path);
+        }
     }
 
     return true;
@@ -674,6 +696,22 @@
                << ", user " << user_id << ", flags " << flags;
     bool res = true;
 
+    if (flags & FLAG_STORAGE_CE) {
+        // CE_n key
+        auto system_ce_path = android::vold::BuildDataSystemCePath(user_id);
+        auto misc_ce_path = android::vold::BuildDataMiscCePath(user_id);
+        auto media_ce_path = android::vold::BuildDataMediaCePath(volume_uuid, user_id);
+        auto user_ce_path = android::vold::BuildDataUserCePath(volume_uuid, user_id);
+
+        res &= destroy_dir(media_ce_path);
+        res &= destroy_dir(user_ce_path);
+        if (volume_uuid.empty()) {
+            res &= prepare_subdirs("destroy", "misc_ce", volume_uuid, user_id, misc_ce_path);
+            res &= destroy_dir(system_ce_path);
+            res &= destroy_dir(misc_ce_path);
+        }
+    }
+
     if (flags & FLAG_STORAGE_DE) {
         // DE_sys key
         auto system_legacy_path = android::vold::BuildDataSystemLegacyPath(user_id);
@@ -685,7 +723,9 @@
         auto misc_de_path = android::vold::BuildDataMiscDePath(user_id);
         auto user_de_path = android::vold::BuildDataUserDePath(volume_uuid, user_id);
 
+        res &= destroy_dir(user_de_path);
         if (volume_uuid.empty()) {
+            res &= prepare_subdirs("destroy", "misc_de", volume_uuid, user_id, misc_de_path);
             res &= destroy_dir(system_legacy_path);
 #if MANAGE_MISC_DIRS
             res &= destroy_dir(misc_legacy_path);
@@ -694,22 +734,6 @@
             res &= destroy_dir(system_de_path);
             res &= destroy_dir(misc_de_path);
         }
-        res &= destroy_dir(user_de_path);
-    }
-
-    if (flags & FLAG_STORAGE_CE) {
-        // CE_n key
-        auto system_ce_path = android::vold::BuildDataSystemCePath(user_id);
-        auto misc_ce_path = android::vold::BuildDataMiscCePath(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()) {
-            res &= destroy_dir(system_ce_path);
-            res &= destroy_dir(misc_ce_path);
-        }
-        res &= destroy_dir(media_ce_path);
-        res &= destroy_dir(user_ce_path);
     }
 
     return res;
diff --git a/VoldNativeService.cpp b/VoldNativeService.cpp
index d1986ef..c82eb92 100644
--- a/VoldNativeService.cpp
+++ b/VoldNativeService.cpp
@@ -691,20 +691,22 @@
 binder::Status VoldNativeService::prepareUserStorage(const std::unique_ptr<std::string>& uuid,
         int32_t userId, int32_t userSerial, int32_t flags) {
     ENFORCE_UID(AID_SYSTEM);
-    ACQUIRE_CRYPT_LOCK;
-
     std::string empty_string = "";
     auto uuid_ = uuid ? *uuid : empty_string;
+    CHECK_ARGUMENT_HEX(uuid_);
+
+    ACQUIRE_CRYPT_LOCK;
     return translateBool(e4crypt_prepare_user_storage(uuid_, userId, userSerial, flags));
 }
 
 binder::Status VoldNativeService::destroyUserStorage(const std::unique_ptr<std::string>& uuid,
         int32_t userId, int32_t flags) {
     ENFORCE_UID(AID_SYSTEM);
-    ACQUIRE_CRYPT_LOCK;
-
     std::string empty_string = "";
     auto uuid_ = uuid ? *uuid : empty_string;
+    CHECK_ARGUMENT_HEX(uuid_);
+
+    ACQUIRE_CRYPT_LOCK;
     return translateBool(e4crypt_destroy_user_storage(uuid_, userId, flags));
 }
 
diff --git a/prepare_dir.cpp b/prepare_dir.cpp
new file mode 100644
index 0000000..1d91458
--- /dev/null
+++ b/prepare_dir.cpp
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+/*
+ * Tool to create a directory with the right SELinux context applied, or
+ * apply the context if it's absent. Also fixes mode, uid, gid.
+ */
+
+#include <string>
+#include <vector>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/stat.h>
+
+#include <android-base/logging.h>
+
+#include <cutils/fs.h>
+#include <selinux/android.h>
+
+void usage(const char* progname) {
+    fprintf(stderr, "Usage: %s --mode MODE --uid UID --gid GID -- <path>\n", progname);
+}
+
+bool small_int(const std::string& s) {
+    return !s.empty() && s.size() < 7 && s.find_first_not_of("0123456789") == std::string::npos;
+}
+
+int main(int argc, const char* const argv[]) {
+    setenv("ANDROID_LOG_TAGS", "*:v", 1);
+    android::base::InitLogging(const_cast<char**>(argv));
+    std::vector<std::string> args(argv + 1, argv + argc);
+    // Enforce exact format of arguments. You can always loosen but you can never tighten :)
+    if (args.size() != 8 || args[0] != "--mode" || !small_int(args[1]) || args[2] != "--uid" ||
+        !small_int(args[3]) || args[4] != "--gid" || !small_int(args[5]) || args[6] != "--") {
+        usage(argv[0]);
+        return -1;
+    }
+    mode_t mode = (mode_t)stoi(args[1], nullptr, 8);
+    uid_t uid = (uid_t)stoi(args[3]);
+    gid_t gid = (gid_t)stoi(args[5]);
+    const char* path = args[7].c_str();
+
+    struct selabel_handle* sehandle = selinux_android_file_context_handle();
+    char* secontext = nullptr;
+    if (sehandle) {
+        if (selabel_lookup(sehandle, &secontext, path, S_IFDIR) == 0) {
+            setfscreatecon(secontext);
+        }
+    }
+
+    if (fs_prepare_dir(path, mode, uid, gid) != 0) {
+        return -1;
+    }
+    if (secontext) {
+        char* oldsecontext = nullptr;
+        if (lgetfilecon(path, &oldsecontext) < 0) {
+            PLOG(ERROR) << "Unable to read secontext for: " << path;
+            return -1;
+        }
+        if (strcmp(secontext, oldsecontext) != 0) {
+            LOG(INFO) << "Relabelling from " << oldsecontext << " to " << secontext << ": " << path;
+            if (lsetfilecon(path, secontext) != 0) {
+                PLOG(ERROR) << "Relabelling failed for: " << path;
+            }
+        }
+    }
+    return 0;
+}
diff --git a/vold_prepare_subdirs b/vold_prepare_subdirs
new file mode 100644
index 0000000..cdea243
--- /dev/null
+++ b/vold_prepare_subdirs
@@ -0,0 +1,67 @@
+#!/system/bin/sh
+#
+# Copyright (C) 2017 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.
+
+# Set up or tear down subdirectories of vold-created directories.
+#
+# This is kept separate from vold because under the SELinux rules, it has privileges vold doesn't
+# have. In particular, prepare_dir sets SELinux labels on subdirectories based on file_contexts,
+# so this script has some relabelling privileges.
+
+
+set -e
+action="$1"
+dirtype="$2"
+volume_uuid="$3"
+user_id="$4"
+path="$5"
+
+case "$user_id" in
+    *[!0-9]* | '')
+        echo "Invalid user id"
+        exit -1
+        ;;
+esac
+
+if [ x"$volume_uuid" != x ] ; then
+    echo "Volume must be root volume"
+    exit -1;
+fi
+
+case "$dirtype" in
+    misc_de|misc_ce)
+        computed_path="/data/$dirtype/$user_id"
+        if [ x"$computed_path" != x"$path" ] ; then
+            echo "Parameter path didn't match computed path: " $computed_path
+            exit -1;
+        fi
+        case "$action" in
+            prepare)
+                /system/bin/prepare_dir --mode 700 --uid 0 --gid 0 -- "$computed_path"/vold
+                ;;
+            destroy)
+                rm -rf "$computed_path"/*
+                ;;
+            *)
+                echo "Unknown action: $action"
+                exit -1
+                ;;
+        esac
+        ;;
+    *)
+        echo "Unknown type: $dirtype"
+        exit -1
+        ;;
+esac