diff --git a/adb/adb_utils.cpp b/adb/adb_utils.cpp
index 12208cd..ca843bd 100644
--- a/adb/adb_utils.cpp
+++ b/adb/adb_utils.cpp
@@ -18,6 +18,7 @@
 
 #include "adb_utils.h"
 
+#include <libgen.h>
 #include <stdlib.h>
 #include <sys/stat.h>
 #include <sys/types.h>
@@ -32,6 +33,8 @@
 #include "adb_trace.h"
 #include "sysdeps.h"
 
+ADB_MUTEX_DEFINE(dirname_lock);
+
 bool getcwd(std::string* s) {
   char* cwd = getcwd(nullptr, 0);
   if (cwd != nullptr) *s = cwd;
@@ -66,35 +69,86 @@
 }
 
 std::string adb_basename(const std::string& path) {
-    size_t base = path.find_last_of(OS_PATH_SEPARATORS);
-    return (base != std::string::npos) ? path.substr(base + 1) : path;
+  size_t base = path.find_last_of(OS_PATH_SEPARATORS);
+  return (base != std::string::npos) ? path.substr(base + 1) : path;
 }
 
-static bool real_mkdirs(const std::string& path) {
-    std::vector<std::string> path_components = android::base::Split(path, OS_PATH_SEPARATOR_STR);
-    // TODO: all the callers do unlink && mkdirs && adb_creat ---
-    // that's probably the operation we should expose.
-    path_components.pop_back();
-    std::string partial_path;
-    for (const auto& path_component : path_components) {
-        if (partial_path.back() != OS_PATH_SEPARATOR) partial_path += OS_PATH_SEPARATOR;
-        partial_path += path_component;
-        if (adb_mkdir(partial_path.c_str(), 0775) == -1 && errno != EEXIST) {
-            return false;
-        }
-    }
-    return true;
+std::string adb_dirname(const std::string& path) {
+  // Copy path because dirname may modify the string passed in.
+  std::string parent_storage(path);
+
+  // Use lock because dirname() may write to a process global and return a
+  // pointer to that. Note that this locking strategy only works if all other
+  // callers to dirname in the process also grab this same lock.
+  adb_mutex_lock(&dirname_lock);
+
+  // Note that if std::string uses copy-on-write strings, &str[0] will cause
+  // the copy to be made, so there is no chance of us accidentally writing to
+  // the storage for 'path'.
+  char* parent = dirname(&parent_storage[0]);
+
+  // In case dirname returned a pointer to a process global, copy that string
+  // before leaving the lock.
+  const std::string result(parent);
+
+  adb_mutex_unlock(&dirname_lock);
+
+  return result;
 }
 
+// Given a relative or absolute filepath, create the parent directory hierarchy
+// as needed. Returns true if the hierarchy is/was setup.
 bool mkdirs(const std::string& path) {
-#if defined(_WIN32)
-    // Replace '/' with '\\' so we can share the code.
-    std::string clean_path = path;
-    std::replace(clean_path.begin(), clean_path.end(), '/', '\\');
-    return real_mkdirs(clean_path);
-#else
-    return real_mkdirs(path);
-#endif
+  // TODO: all the callers do unlink && mkdirs && adb_creat ---
+  // that's probably the operation we should expose.
+
+  // Implementation Notes:
+  //
+  // Pros:
+  // - Uses dirname, so does not need to deal with OS_PATH_SEPARATOR.
+  // - On Windows, uses mingw dirname which accepts '/' and '\\', drive letters
+  //   (C:\foo), UNC paths (\\server\share\dir\dir\file), and Unicode (when
+  //   combined with our adb_mkdir() which takes UTF-8).
+  // - Is optimistic wrt thinking that a deep directory hierarchy will exist.
+  //   So it does as few stat()s as possible before doing mkdir()s.
+  // Cons:
+  // - Recursive, so it uses stack space relative to number of directory
+  //   components.
+
+  const std::string parent(adb_dirname(path));
+
+  if (directory_exists(parent)) {
+    return true;
+  }
+
+  // If dirname returned the same path as what we passed in, don't go recursive.
+  // This can happen on Windows when walking up the directory hierarchy and not
+  // finding anything that already exists (unlike POSIX that will eventually
+  // find . or /).
+  if (parent == path) {
+    errno = ENOENT;
+    return false;
+  }
+
+  // Recursively make parent directories of 'parent'.
+  if (!mkdirs(parent)) {
+    return false;
+  }
+
+  // Now that the parent directory hierarchy of 'parent' has been ensured,
+  // create parent itself.
+  if (adb_mkdir(parent, 0775) == -1) {
+    // Can't just check for errno == EEXIST because it might be a file that
+    // exists.
+    const int saved_errno = errno;
+    if (directory_exists(parent)) {
+      return true;
+    }
+    errno = saved_errno;
+    return false;
+  }
+
+  return true;
 }
 
 void dump_hex(const void* data, size_t byte_count) {
diff --git a/adb/adb_utils.h b/adb/adb_utils.h
index 8c5208c..739efcc 100644
--- a/adb/adb_utils.h
+++ b/adb/adb_utils.h
@@ -21,7 +21,11 @@
 
 bool getcwd(std::string* cwd);
 bool directory_exists(const std::string& path);
+
+// Like the regular basename and dirname, but thread-safe on all
+// platforms and capable of correctly handling exotic Windows paths.
 std::string adb_basename(const std::string& path);
+std::string adb_dirname(const std::string& path);
 
 bool mkdirs(const std::string& path);
 
diff --git a/adb/adb_utils_test.cpp b/adb/adb_utils_test.cpp
index 9c9f85c..34b54e7 100644
--- a/adb/adb_utils_test.cpp
+++ b/adb/adb_utils_test.cpp
@@ -186,10 +186,19 @@
   EXPECT_FALSE(parse_host_and_port("1.2.3.4:65536", &canonical_address, &host, &port, &error));
 }
 
+void test_mkdirs(const std::string basepath) {
+  EXPECT_TRUE(mkdirs(basepath));
+  EXPECT_NE(-1, adb_creat(basepath.c_str(), 0600));
+  EXPECT_FALSE(mkdirs(basepath + "/subdir/"));
+}
+
 TEST(adb_utils, mkdirs) {
   TemporaryDir td;
-  std::string path = std::string(td.path) + "/dir/subdir/file";
-  EXPECT_TRUE(mkdirs(path));
-  EXPECT_NE(-1, adb_creat(path.c_str(), 0600));
-  EXPECT_FALSE(mkdirs(path + "/subdir/"));
+
+  // Absolute paths.
+  test_mkdirs(std::string(td.path) + "/dir/subdir/file");
+
+  // Relative paths.
+  ASSERT_EQ(0, chdir(td.path)) << strerror(errno);
+  test_mkdirs(std::string("relative/subrel/file"));
 }
diff --git a/adb/mutex_list.h b/adb/mutex_list.h
index ff72751..9003361 100644
--- a/adb/mutex_list.h
+++ b/adb/mutex_list.h
@@ -6,6 +6,7 @@
 #ifndef ADB_MUTEX
 #error ADB_MUTEX not defined when including this file
 #endif
+ADB_MUTEX(dirname_lock)
 ADB_MUTEX(socket_list_lock)
 ADB_MUTEX(transport_lock)
 #if ADB_HOST