diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index 31533c7..a56d196 100644
--- a/FsCrypt.cpp
+++ b/FsCrypt.cpp
@@ -652,18 +652,12 @@
         if (!android::vold::readSecdiscardable(secdiscardable_path, &secdiscardable_hash))
             return false;
     } else {
-        if (fs_mkdirs(secdiscardable_path.c_str(), 0700) != 0) {
-            PLOG(ERROR) << "Creating directories for: " << secdiscardable_path;
-            return false;
-        }
+        if (!android::vold::MkdirsSync(secdiscardable_path, 0700)) return false;
         if (!android::vold::createSecdiscardable(secdiscardable_path, &secdiscardable_hash))
             return false;
     }
     auto key_path = volkey_path(misc_path, volume_uuid);
-    if (fs_mkdirs(key_path.c_str(), 0700) != 0) {
-        PLOG(ERROR) << "Creating directories for: " << key_path;
-        return false;
-    }
+    if (!android::vold::MkdirsSync(key_path, 0700)) return false;
     android::vold::KeyAuthentication auth("", secdiscardable_hash);
 
     EncryptionOptions options;
diff --git a/MetadataCrypt.cpp b/MetadataCrypt.cpp
index 24c7476..dc50679 100644
--- a/MetadataCrypt.cpp
+++ b/MetadataCrypt.cpp
@@ -111,10 +111,7 @@
     std::string sKey;
     auto dir = metadata_key_dir + "/key";
     LOG(DEBUG) << "metadata_key_dir/key: " << dir;
-    if (fs_mkdirs(dir.c_str(), 0700)) {
-        PLOG(ERROR) << "Creating directories: " << dir;
-        return false;
-    }
+    if (!MkdirsSync(dir, 0700)) return false;
     auto temp = metadata_key_dir + "/tmp";
     return retrieveOrGenerateKey(dir, temp, kEmptyAuthentication, gen, key);
 }
diff --git a/Utils.cpp b/Utils.cpp
index c1fbf8f..cef0f39 100644
--- a/Utils.cpp
+++ b/Utils.cpp
@@ -1375,6 +1375,36 @@
     return FsyncDirectory(android::base::Dirname(path));
 }
 
+// Creates all parent directories of |path| that don't already exist.  Assigns
+// the specified |mode| to any new directories, and also fsync()s their parent
+// directories so that the new directories get written to disk right away.
+bool MkdirsSync(const std::string& path, mode_t mode) {
+    if (path[0] != '/') {
+        LOG(ERROR) << "MkdirsSync() needs an absolute path, but got " << path;
+        return false;
+    }
+    std::vector<std::string> components = android::base::Split(android::base::Dirname(path), "/");
+
+    std::string current_dir = "/";
+    for (const std::string& component : components) {
+        if (component.empty()) continue;
+
+        std::string parent_dir = current_dir;
+        if (current_dir != "/") current_dir += "/";
+        current_dir += component;
+
+        if (!pathExists(current_dir)) {
+            if (mkdir(current_dir.c_str(), mode) != 0) {
+                PLOG(ERROR) << "Failed to create " << current_dir;
+                return false;
+            }
+            if (!FsyncDirectory(parent_dir)) return false;
+            LOG(DEBUG) << "Created directory " << current_dir;
+        }
+    }
+    return true;
+}
+
 bool writeStringToFile(const std::string& payload, const std::string& filename) {
     android::base::unique_fd fd(TEMP_FAILURE_RETRY(
         open(filename.c_str(), O_WRONLY | O_CREAT | O_NOFOLLOW | O_TRUNC | O_CLOEXEC, 0666)));
diff --git a/Utils.h b/Utils.h
index 87beced..4771593 100644
--- a/Utils.h
+++ b/Utils.h
@@ -185,6 +185,8 @@
 
 bool FsyncParentDirectory(const std::string& path);
 
+bool MkdirsSync(const std::string& path, mode_t mode);
+
 bool writeStringToFile(const std::string& payload, const std::string& filename);
 
 void ConfigureMaxDirtyRatioForFuse(const std::string& fuse_mount, unsigned int max_ratio);
diff --git a/tests/Utils_test.cpp b/tests/Utils_test.cpp
index d18dc67..35b40cd 100644
--- a/tests/Utils_test.cpp
+++ b/tests/Utils_test.cpp
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+#include <android-base/file.h>
 #include <gtest/gtest.h>
 
 #include "../Utils.h"
@@ -43,5 +44,23 @@
     ASSERT_EQ("QUUX", tmp);
 }
 
+TEST_F(UtilsTest, MkdirsSyncTest) {
+    TemporaryDir temp_dir;
+    std::string temp_dir_path;
+
+    ASSERT_TRUE(android::base::Realpath(temp_dir.path, &temp_dir_path));
+
+    ASSERT_FALSE(pathExists(temp_dir_path + "/a"));
+    ASSERT_TRUE(MkdirsSync(temp_dir_path + "/a/b/c", 0700));
+    ASSERT_TRUE(pathExists(temp_dir_path + "/a"));
+    ASSERT_TRUE(pathExists(temp_dir_path + "/a/b"));
+    // The final component of the path should not be created; only the previous
+    // components should be.
+    ASSERT_FALSE(pathExists(temp_dir_path + "/a/b/c"));
+
+    // Currently, MkdirsSync() only supports absolute paths.
+    ASSERT_FALSE(MkdirsSync("foo", 0700));
+}
+
 }  // namespace vold
 }  // namespace android