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();
diff --git a/Utils.h b/Utils.h
index b35250d..a7dda7a 100644
--- a/Utils.h
+++ b/Utils.h
@@ -36,11 +36,6 @@
 
 static const char* kPropFuse = "persist.sys.fuse";
 
-static const char* kAndroidDir = "/Android/";
-static const char* kAppDataDir = "/Android/data/";
-static const char* kAppMediaDir = "/Android/media/";
-static const char* kAppObbDir = "/Android/obb/";
-
 /* SELinux contexts used depending on the block device type */
 extern security_context_t sBlkidContext;
 extern security_context_t sBlkidUntrustedContext;
@@ -56,13 +51,13 @@
 int SetQuotaInherit(const std::string& path);
 int SetQuotaProjectId(const std::string& path, long projectId);
 /*
- * Recursively calls fs_prepare_dir() on all components in 'path', starting at 'root'.
- * 'path' must start with 'root'. Sets up quota project IDs correctly.
+ * Creates and sets up an application-specific path on external
+ * storage with the correct ACL and project ID (if needed).
  *
  * ONLY for use with app-specific data directories on external storage!
  * (eg, /Android/data/com.foo, /Android/obb/com.foo, etc.)
  */
-int PrepareAppDirsFromRoot(std::string path, std::string root, mode_t mode, uid_t uid, gid_t gid);
+int PrepareAppDirFromRoot(std::string path, int appUid);
 
 /* fs_prepare_dir wrapper that creates with SELinux context */
 status_t PrepareDir(const std::string& path, mode_t mode, uid_t uid, gid_t gid);
diff --git a/VolumeManager.cpp b/VolumeManager.cpp
index 4427c9b..c141d2a 100644
--- a/VolumeManager.cpp
+++ b/VolumeManager.cpp
@@ -82,7 +82,7 @@
 using android::vold::DeleteDirContentsAndDir;
 using android::vold::IsFilesystemSupported;
 using android::vold::PrepareAndroidDirs;
-using android::vold::PrepareAppDirsFromRoot;
+using android::vold::PrepareAppDirFromRoot;
 using android::vold::PrivateVolume;
 using android::vold::Symlink;
 using android::vold::Unlink;
@@ -823,29 +823,6 @@
     return 0;
 }
 
-static gid_t getAppDirGid(const std::string& appDir) {
-    // Create app-specific dirs with the correct UID/GID
-    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;
-}
-
-static bool isValidAppDirRoot(const std::string& appDirRoot) {
-    return appDirRoot == android::vold::kAppDataDir || appDirRoot == android::vold::kAppMediaDir ||
-           appDirRoot == android::vold::kAppObbDir;
-}
-
 int VolumeManager::setupAppDir(const std::string& path, const std::string& appDirRoot,
                                int32_t appUid) {
     // Only offer to create directories for paths managed by vold
@@ -889,19 +866,10 @@
     // on /storage/emulated/10 means /mnt/user/0/emulated/10
     const std::string lowerPath =
             volume->getInternalPath() + path.substr(volume->getPath().length());
-    const std::string lowerAppDirRoot =
-            volume->getInternalPath() + appDirRoot.substr(volume->getPath().length());
 
     // Do some sanity checking on the app dir (relative from root)
     const std::string volumeRoot = volume->getRootPath();  // eg /data/media/0
 
-    // eg, if lowerAppDirRoot = /data/media/0/Android/data, this is /Android/data
-    const std::string relativeAppRoot = lowerAppDirRoot.substr(volumeRoot.length());
-    if (!isValidAppDirRoot(relativeAppRoot)) {
-        LOG(ERROR) << path << " is not a valid application directory.";
-        return -EINVAL;
-    }
-
     // Make sure the Android/ directories exist and are setup correctly
     int ret = PrepareAndroidDirs(volumeRoot);
     if (ret != 0) {
@@ -909,8 +877,8 @@
         return ret;
     }
 
-    gid_t gid = getAppDirGid(relativeAppRoot);
-    return PrepareAppDirsFromRoot(lowerPath, lowerAppDirRoot, 0770, appUid, gid);
+    // Finally, create the app paths we need
+    return PrepareAppDirFromRoot(lowerPath, appUid);
 }
 
 int VolumeManager::createObb(const std::string& sourcePath, const std::string& sourceKey,