diff --git a/Utils.cpp b/Utils.cpp
index d483418..67c48ad 100644
--- a/Utils.cpp
+++ b/Utils.cpp
@@ -55,6 +55,7 @@
 
 using namespace std::chrono_literals;
 using android::base::ReadFileToString;
+using android::base::StartsWith;
 using android::base::StringPrintf;
 
 namespace android {
@@ -114,6 +115,27 @@
     }
 }
 
+int PrepareDirsFromRoot(std::string path, std::string root, mode_t mode, uid_t uid, gid_t gid) {
+    int ret = 0;
+    if (!StartsWith(path, root)) {
+        return -1;
+    }
+    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;
+        }
+    }
+
+    return ret;
+}
+
 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 4c0114a..056a635 100644
--- a/Utils.h
+++ b/Utils.h
@@ -48,6 +48,12 @@
 status_t CreateDeviceNode(const std::string& path, dev_t dev);
 status_t DestroyDeviceNode(const std::string& path);
 
+/*
+ * Recursively calls fs_prepare_dir() on all components in 'path', starting at 'root'.
+ * 'path' must start with 'root'
+ */
+int PrepareDirsFromRoot(std::string path, std::string root, mode_t mode, uid_t uid, gid_t gid);
+
 /* 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/VoldNativeService.cpp b/VoldNativeService.cpp
index b82ea06..78d7ed3 100644
--- a/VoldNativeService.cpp
+++ b/VoldNativeService.cpp
@@ -456,12 +456,14 @@
     return translate(VolumeManager::Instance()->remountUid(uid, remountMode));
 }
 
-binder::Status VoldNativeService::mkdirs(const std::string& path) {
+binder::Status VoldNativeService::setupAppDir(const std::string& path,
+                                              const std::string& appDirRoot, int32_t appUid) {
     ENFORCE_SYSTEM_OR_ROOT;
     CHECK_ARGUMENT_PATH(path);
+    CHECK_ARGUMENT_PATH(appDirRoot);
     ACQUIRE_LOCK;
 
-    return translate(VolumeManager::Instance()->mkdirs(path));
+    return translate(VolumeManager::Instance()->setupAppDir(path, appDirRoot, appUid));
 }
 
 binder::Status VoldNativeService::createObb(const std::string& sourcePath,
diff --git a/VoldNativeService.h b/VoldNativeService.h
index ebd9041..5753b0b 100644
--- a/VoldNativeService.h
+++ b/VoldNativeService.h
@@ -65,7 +65,8 @@
 
     binder::Status remountUid(int32_t uid, int32_t remountMode);
 
-    binder::Status mkdirs(const std::string& path);
+    binder::Status setupAppDir(const std::string& path, const std::string& appDirRoot,
+                               int32_t appUid);
 
     binder::Status createObb(const std::string& sourcePath, const std::string& sourceKey,
                              int32_t ownerGid, std::string* _aidl_return);
diff --git a/VolumeManager.cpp b/VolumeManager.cpp
index 143f53c..bc843b4 100644
--- a/VolumeManager.cpp
+++ b/VolumeManager.cpp
@@ -81,6 +81,7 @@
 using android::vold::CreateDir;
 using android::vold::DeleteDirContents;
 using android::vold::DeleteDirContentsAndDir;
+using android::vold::PrepareDirsFromRoot;
 using android::vold::PrivateVolume;
 using android::vold::Symlink;
 using android::vold::Unlink;
@@ -806,16 +807,21 @@
     return 0;
 }
 
-int VolumeManager::mkdirs(const std::string& path) {
+int VolumeManager::setupAppDir(const std::string& path, const std::string& appDirRoot,
+                               int32_t appUid) {
     // Only offer to create directories for paths managed by vold
-    if (StartsWith(path, "/storage/")) {
-        std::string lower_path = "/mnt/runtime/default/" + path.substr(9);
-        // fs_mkdirs() does symlink checking and relative path enforcement
-        return fs_mkdirs(lower_path.c_str(), 0700);
-    } else {
+    if (!StartsWith(path, "/storage/")) {
         LOG(ERROR) << "Failed to find mounted volume for " << path;
         return -EINVAL;
     }
+
+    // First create the root which holds app dirs, if needed.
+    int ret = PrepareDirsFromRoot(appDirRoot, "/storage/", 0771, AID_MEDIA_RW, AID_MEDIA_RW);
+    if (ret != 0) {
+        return ret;
+    }
+    // Then, create app-specific dirs with the correct UID/GID
+    return PrepareDirsFromRoot(path, appDirRoot, 0770, appUid, AID_MEDIA_RW);
 }
 
 int VolumeManager::createObb(const std::string& sourcePath, const std::string& sourceKey,
diff --git a/VolumeManager.h b/VolumeManager.h
index fad3c00..db32ecd 100644
--- a/VolumeManager.h
+++ b/VolumeManager.h
@@ -113,13 +113,30 @@
     static VolumeManager* Instance();
 
     /*
-     * Ensure that all directories along given path exist, creating parent
-     * directories as needed.  Validates that given path is absolute and that
-     * it contains no relative "." or ".." paths or symlinks.  Last path segment
-     * is treated as filename and ignored, unless the path ends with "/".  Also
-     * ensures that path belongs to a volume managed by vold.
+     * Creates a directory 'path' for an application, automatically creating
+     * directories along the given path if they don't exist yet. 'appDirRoot'
+     * is the "root" directory for app-specific directories of this kind;
+     * 'path' must always start with 'appDirRoot'.
+     *
+     * Example:
+     *   path = /storage/emulated/0/Android/data/com.foo/files/
+     *   appDirRoot = /storage/emulated/0/Android/data/
+     *
+     * This function will set the UID of all app-specific directories below
+     * 'appDirRoot' to the 'appUid' argument. In the given example, the UID
+     * of /storage/emulated/0/Android/data/com.foo and
+     * /storage/emulated/0/Android/data/com.foo/files would be set to 'appUid'.
+     *
+     * The UID of the parent directories will be set according to the
+     * requirements of the underlying filesystem and are of no concern to the
+     * caller.
+     *
+     * Validates that given paths are absolute and that they contain no relative
+     * "." or ".." paths or symlinks.  Last path segment is treated as filename
+     * and ignored, unless the path ends with "/".  Also ensures that path
+     * belongs to a volume managed by vold.
      */
-    int mkdirs(const std::string& path);
+    int setupAppDir(const std::string& path, const std::string& appDirRoot, int32_t appUid);
 
     int createObb(const std::string& path, const std::string& key, int32_t ownerGid,
                   std::string* outVolId);
diff --git a/binder/android/os/IVold.aidl b/binder/android/os/IVold.aidl
index 975d94c..cec38c5 100644
--- a/binder/android/os/IVold.aidl
+++ b/binder/android/os/IVold.aidl
@@ -54,7 +54,7 @@
 
     void remountUid(int uid, int remountMode);
 
-    void mkdirs(@utf8InCpp String path);
+    void setupAppDir(@utf8InCpp String path, @utf8InCpp String appDirRoot, int appUid);
 
     @utf8InCpp String createObb(@utf8InCpp String sourcePath, @utf8InCpp String sourceKey,
                                 int ownerGid);