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..1a84e30 100644
--- a/Ext4Crypt.cpp
+++ b/Ext4Crypt.cpp
@@ -632,6 +632,15 @@
             }
             if (!ensure_policy(de_raw_ref, user_de_path)) return false;
         }
+
+        if (volume_uuid.empty()) {
+            if (0 != android::vold::ForkExecvp(
+                         std::vector<std::string>{"/system/bin/vold_prepare_subdirs", "misc_de",
+                                                  misc_de_path, std::to_string(user_id), ""})) {
+                LOG(ERROR) << "vold_prepare_subdirs failed on: " << misc_de_path;
+                return false;
+            }
+        }
     }
 
     if (flags & FLAG_STORAGE_CE) {
@@ -664,6 +673,15 @@
             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 (0 != android::vold::ForkExecvp(
+                         std::vector<std::string>{"/system/bin/vold_prepare_subdirs", "misc_ce",
+                                                  misc_ce_path, std::to_string(user_id), ""})) {
+                LOG(ERROR) << "vold_prepare_subdirs failed on: " << misc_ce_path;
+                return false;
+            }
+        }
     }
 
     return true;
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..f436ca2
--- /dev/null
+++ b/vold_prepare_subdirs
@@ -0,0 +1,44 @@
+#!/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 -e
+
+case "$3" in
+  *[!0-9]* | '')
+    echo "Invalid user id"
+    exit -1
+    ;;
+esac
+
+if [ x"$4" != x ] ; then
+    echo "Volume must be root volume"
+    exit -1;
+fi
+
+case "$1" in
+    misc_de|misc_ce)
+        computed_path="/data/$1/$3"
+        if [ x"$computed_path" != x"$2" ] ; then
+            echo "Parameter path didn't match computed path: " $computed_path
+            exit -1;
+        fi
+        /system/bin/prepare_dir --mode 700 --uid 0 --gid 0 -- "$computed_path"/vold
+        ;;
+    *)
+        echo "Unknown type: $1"
+        exit -1;
+        ;;
+esac