diff --git a/FsCrypt.cpp b/FsCrypt.cpp
index 988d2a7..82a2012 100644
--- a/FsCrypt.cpp
+++ b/FsCrypt.cpp
@@ -462,7 +462,6 @@
         return false;
     LOG(INFO) << "Wrote per boot key reference to:" << per_boot_ref_filename;
 
-    if (!android::vold::FsyncDirectory(device_key_dir)) return false;
     return true;
 }
 
@@ -652,18 +651,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;
@@ -704,7 +697,6 @@
     if (!get_ce_key_new_path(directory_path, paths, &ce_key_path)) return false;
     if (!android::vold::storeKeyAtomically(ce_key_path, user_key_temp, store_auth, ce_key))
         return false;
-    if (!android::vold::FsyncDirectory(directory_path)) return false;
     return true;
 }
 
diff --git a/KeyStorage.cpp b/KeyStorage.cpp
index 89844aa..457bb66 100644
--- a/KeyStorage.cpp
+++ b/KeyStorage.cpp
@@ -606,10 +606,6 @@
     return true;
 }
 
-bool pathExists(const std::string& path) {
-    return access(path.c_str(), F_OK) == 0;
-}
-
 bool storeKey(const std::string& dir, const KeyAuthentication& auth, const KeyBuffer& key) {
     if (TEMP_FAILURE_RETRY(mkdir(dir.c_str(), 0700)) == -1) {
         PLOG(ERROR) << "key mkdir " << dir;
@@ -665,6 +661,7 @@
         PLOG(ERROR) << "Unable to move new key to location: " << key_path;
         return false;
     }
+    if (!FsyncParentDirectory(key_path)) return false;
     LOG(DEBUG) << "Created key: " << key_path;
     return true;
 }
diff --git a/KeyStorage.h b/KeyStorage.h
index a69dbf7..5fded41 100644
--- a/KeyStorage.h
+++ b/KeyStorage.h
@@ -43,9 +43,6 @@
 
 extern const KeyAuthentication kEmptyAuthentication;
 
-// Checks if path "path" exists.
-bool pathExists(const std::string& path);
-
 bool createSecdiscardable(const std::string& path, std::string* hash);
 bool readSecdiscardable(const std::string& path, std::string* hash);
 
@@ -58,7 +55,8 @@
 // Create a directory at the named path, and store "key" in it as storeKey
 // This version creates the key in "tmp_path" then atomically renames "tmp_path"
 // to "key_path" thereby ensuring that the key is either stored entirely or
-// not at all.
+// not at all.  All the needed files and directories are also fsync'ed to ensure
+// that the key is actually persisted to disk.
 bool storeKeyAtomically(const std::string& key_path, const std::string& tmp_path,
                         const KeyAuthentication& auth, const KeyBuffer& key);
 
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 d5648f7..973908a 100644
--- a/Utils.cpp
+++ b/Utils.cpp
@@ -1349,6 +1349,10 @@
     return -1;
 }
 
+bool pathExists(const std::string& path) {
+    return access(path.c_str(), F_OK) == 0;
+}
+
 bool FsyncDirectory(const std::string& dirname) {
     android::base::unique_fd fd(TEMP_FAILURE_RETRY(open(dirname.c_str(), O_RDONLY | O_CLOEXEC)));
     if (fd == -1) {
@@ -1367,6 +1371,40 @@
     return true;
 }
 
+bool FsyncParentDirectory(const std::string& path) {
+    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 49901c8..53e09ba 100644
--- a/Utils.h
+++ b/Utils.h
@@ -176,8 +176,14 @@
 
 status_t WaitForFile(const char* filename, std::chrono::nanoseconds timeout);
 
+bool pathExists(const std::string& path);
+
 bool FsyncDirectory(const std::string& dirname);
 
+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