diff --git a/Utils.cpp b/Utils.cpp
index b2a1992..04a61d0 100644
--- a/Utils.cpp
+++ b/Utils.cpp
@@ -47,6 +47,7 @@
 
 #include <list>
 #include <mutex>
+#include <regex>
 #include <thread>
 
 #ifndef UMOUNT_NOFOLLOW
@@ -74,6 +75,11 @@
 
 static const char* kProcFilesystems = "/proc/filesystems";
 
+static const char* kAndroidDir = "/Android/";
+static const char* kAppDataDir = "/Android/data/";
+static const char* kAppMediaDir = "/Android/media/";
+static const char* kAppObbDir = "/Android/obb/";
+
 // Lock used to protect process-level SELinux changes from racing with each
 // other between multiple threads.
 static std::mutex kSecurityLock;
@@ -161,46 +167,83 @@
     return ioctl(fd, FS_IOC_FSSETXATTR, &fsx);
 }
 
-int PrepareAppDirsFromRoot(std::string path, std::string root, mode_t mode, uid_t uid, gid_t gid) {
-    int ret = 0;
-    bool isCacheDir = false;
-    if (!StartsWith(path, root)) {
-        return -1;
+int PrepareDirWithProjectId(const std::string& path, mode_t mode, uid_t uid, gid_t gid,
+                            long projectId) {
+    int ret = fs_prepare_dir(path.c_str(), mode, uid, gid);
+
+    if (ret != 0) {
+        return ret;
     }
-    // Cache directories (eg "/storage/emulated/Android/data/com.foo/cache/") need special treatment
-    isCacheDir = EndsWith(root, "/Android/data/") && EndsWith(path, "cache/");
 
-    std::string to_create_from_root = path.substr(root.length());
-
-    size_t pos = 0;
-    while ((pos = to_create_from_root.find('/')) != std::string::npos) {
-        auto component = to_create_from_root.substr(0, pos);
-        to_create_from_root.erase(0, pos + 1);
-        root = root + component + "/";
-        ret = fs_prepare_dir(root.c_str(), mode, uid, gid);
-        if (ret) {
-            break;
-        }
-        if (!IsFilesystemSupported("sdcardfs")) {
-            long projectId;
-            // All app-specific directories share the same project-ID, except
-            // the cache directory
-            if (isCacheDir && component == "cache") {
-                // Note that this also matches paths like:
-                // /Android/data/com.foo/bar/cache/
-                // This is currently safe because we're never asked to create
-                // such directories.
-                projectId = uid - AID_APP_START + AID_CACHE_GID_START;
-            } else {
-                projectId = uid - AID_APP_START + AID_EXT_GID_START;
-            }
-            ret = SetQuotaProjectId(root, projectId);
-        }
+    if (!IsFilesystemSupported("sdcardfs")) {
+        ret = SetQuotaProjectId(path, projectId);
     }
 
     return ret;
 }
 
+static gid_t getAppDirGid(const std::string& appDir) {
+    gid_t gid = AID_MEDIA_RW;
+    if (!IsFilesystemSupported("sdcardfs")) {
+        if (appDir == android::vold::kAppDataDir) {
+            gid = AID_EXT_DATA_RW;
+        } else if (appDir == android::vold::kAppObbDir) {
+            gid = AID_EXT_OBB_RW;
+        } else if (appDir == android::vold::kAppMediaDir) {
+            gid = AID_MEDIA_RW;
+        } else {
+            gid = AID_MEDIA_RW;
+        }
+    }
+
+    return gid;
+}
+
+int PrepareAppDirFromRoot(std::string path, int appUid) {
+    int ret = 0;
+    // Extract various parts of the path to setup correctly
+    // Sample path:
+    // /data/media/0/Android/data/com.foo/files
+    // [1]: path in which to create app-specific dir, eg. /data/media/0/Android/data/
+    // [2]: the part of [1] starting from /Android, eg. /Android/data/
+    // [3]: the package name part of the path, eg. com.foo
+    // [4]: the directory to create within [3], eg files
+    std::regex re("(^/.*(/Android/(?:data|media|obb|sandbox)/))([^/]+)/([^/]+)?/?");
+
+    std::smatch match;
+    bool is_match = regex_match(path, match, re);
+
+    if (!is_match) {
+        LOG(ERROR) << "Invalid application directory: " << path;
+        return -EINVAL;
+    }
+
+    uid_t uid = appUid;
+    gid_t gid = getAppDirGid(match.str(2));
+    // mode = 770, plus sticky bit on directory to inherit GID when apps
+    // create subdirs
+    mode_t mode = S_IRWXU | S_IRWXG | S_ISGID;
+    long projectId = uid - AID_APP_START + AID_EXT_GID_START;
+
+    // First, create the package-path
+    std::string package_path = match.str(1) + match.str(3);
+    ret = PrepareDirWithProjectId(package_path, mode, uid, gid, projectId);
+    if (ret) {
+        return ret;
+    }
+
+    // Next, create the directory within the package, if needed
+    if (match.size() <= 4) {
+        return OK;
+    }
+
+    if (match.str(4) == "cache") {
+        // All dirs use the "app" project ID, except for the cache dir
+        projectId = uid - AID_APP_START + AID_CACHE_GID_START;
+    }
+    return PrepareDirWithProjectId(path.c_str(), mode, uid, gid, projectId);
+}
+
 status_t PrepareDir(const std::string& path, mode_t mode, uid_t uid, gid_t gid) {
     std::lock_guard<std::mutex> lock(kSecurityLock);
     const char* cpath = path.c_str();