diff --git a/fs_mgr/Android.bp b/fs_mgr/Android.bp
index 3d3503c..65f0eff 100644
--- a/fs_mgr/Android.bp
+++ b/fs_mgr/Android.bp
@@ -73,6 +73,7 @@
     whole_static_libs: [
         "liblogwrap",
         "libdm",
+        "libext2_uuid",
         "libfstab",
     ],
     cppflags: [
diff --git a/fs_mgr/fs_mgr_dm_linear.cpp b/fs_mgr/fs_mgr_dm_linear.cpp
index 1f21a71..cd089dc 100644
--- a/fs_mgr/fs_mgr_dm_linear.cpp
+++ b/fs_mgr/fs_mgr_dm_linear.cpp
@@ -122,19 +122,9 @@
         table.set_readonly(false);
     }
     std::string name = GetPartitionName(partition);
-    if (!dm.CreateDevice(name, table)) {
+    if (!dm.CreateDevice(name, table, path, timeout_ms)) {
         return false;
     }
-    if (!dm.GetDmDevicePathByName(name, path)) {
-        return false;
-    }
-    if (timeout_ms > std::chrono::milliseconds::zero()) {
-        if (!WaitForFile(*path, timeout_ms)) {
-            DestroyLogicalPartition(name, {});
-            LERROR << "Timed out waiting for device path: " << *path;
-            return false;
-        }
-    }
     LINFO << "Created logical partition " << name << " on device " << *path;
     return true;
 }
diff --git a/fs_mgr/libdm/Android.bp b/fs_mgr/libdm/Android.bp
index 21255df..e429d9f 100644
--- a/fs_mgr/libdm/Android.bp
+++ b/fs_mgr/libdm/Android.bp
@@ -29,6 +29,9 @@
         "loop_control.cpp",
     ],
 
+    static_libs: [
+        "libext2_uuid",
+    ],
     header_libs: [
         "libbase_headers",
         "liblog_headers",
@@ -46,6 +49,7 @@
     static_libs: [
         "libdm",
         "libbase",
+        "libext2_uuid",
         "libfs_mgr",
         "liblog",
     ],
diff --git a/fs_mgr/libdm/dm.cpp b/fs_mgr/libdm/dm.cpp
index d54b6ef..d56a4b1 100644
--- a/fs_mgr/libdm/dm.cpp
+++ b/fs_mgr/libdm/dm.cpp
@@ -20,12 +20,20 @@
 #include <sys/sysmacros.h>
 #include <sys/types.h>
 
+#include <functional>
+#include <thread>
+
+#include <android-base/file.h>
 #include <android-base/logging.h>
 #include <android-base/macros.h>
+#include <android-base/strings.h>
+#include <uuid/uuid.h>
 
 namespace android {
 namespace dm {
 
+using namespace std::literals;
+
 DeviceMapper::DeviceMapper() : fd_(-1) {
     fd_ = TEMP_FAILURE_RETRY(open("/dev/device-mapper", O_RDWR | O_CLOEXEC));
     if (fd_ < 0) {
@@ -37,13 +45,13 @@
     static DeviceMapper instance;
     return instance;
 }
+
 // Creates a new device mapper device
-bool DeviceMapper::CreateDevice(const std::string& name) {
+bool DeviceMapper::CreateDevice(const std::string& name, const std::string& uuid) {
     if (name.empty()) {
         LOG(ERROR) << "Unnamed device mapper device creation is not supported";
         return false;
     }
-
     if (name.size() >= DM_NAME_LEN) {
         LOG(ERROR) << "[" << name << "] is too long to be device mapper name";
         return false;
@@ -51,6 +59,9 @@
 
     struct dm_ioctl io;
     InitIo(&io, name);
+    if (!uuid.empty()) {
+        snprintf(io.uuid, sizeof(io.uuid), "%s", uuid.c_str());
+    }
 
     if (ioctl(fd_, DM_DEV_CREATE, &io)) {
         PLOG(ERROR) << "DM_DEV_CREATE failed for [" << name << "]";
@@ -67,16 +78,6 @@
 }
 
 bool DeviceMapper::DeleteDevice(const std::string& name) {
-    if (name.empty()) {
-        LOG(ERROR) << "Unnamed device mapper device creation is not supported";
-        return false;
-    }
-
-    if (name.size() >= DM_NAME_LEN) {
-        LOG(ERROR) << "[" << name << "] is too long to be device mapper name";
-        return false;
-    }
-
     struct dm_ioctl io;
     InitIo(&io, name);
 
@@ -93,9 +94,81 @@
     return true;
 }
 
-const std::unique_ptr<DmTable> DeviceMapper::table(const std::string& /* name */) const {
-    // TODO(b/110035986): Return the table, as read from the kernel instead
-    return nullptr;
+bool WaitForCondition(const std::function<bool()>& condition,
+                      const std::chrono::milliseconds& timeout_ms) {
+    auto start_time = std::chrono::steady_clock::now();
+    while (true) {
+        if (condition()) return true;
+
+        std::this_thread::sleep_for(20ms);
+
+        auto now = std::chrono::steady_clock::now();
+        auto time_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time);
+        if (time_elapsed > timeout_ms) return false;
+    }
+}
+
+static std::string GenerateUuid() {
+    uuid_t uuid_bytes;
+    uuid_generate(uuid_bytes);
+
+    char uuid_chars[37] = {};
+    uuid_unparse_lower(uuid_bytes, uuid_chars);
+
+    return std::string{uuid_chars};
+}
+
+bool DeviceMapper::CreateDevice(const std::string& name, const DmTable& table, std::string* path,
+                                const std::chrono::milliseconds& timeout_ms) {
+    std::string uuid = GenerateUuid();
+    if (!CreateDevice(name, uuid)) {
+        return false;
+    }
+
+    // We use the unique path for testing whether the device is ready. After
+    // that, it's safe to use the dm-N path which is compatible with callers
+    // that expect it to be formatted as such.
+    std::string unique_path;
+    if (!LoadTableAndActivate(name, table) || !GetDeviceUniquePath(name, &unique_path) ||
+        !GetDmDevicePathByName(name, path)) {
+        DeleteDevice(name);
+        return false;
+    }
+
+    if (timeout_ms <= std::chrono::milliseconds::zero()) {
+        return true;
+    }
+
+    auto condition = [&]() -> bool {
+        // If the file exists but returns EPERM or something, we consider the
+        // condition met.
+        if (access(unique_path.c_str(), F_OK) != 0) {
+            if (errno == ENOENT) return false;
+        }
+        return true;
+    };
+    if (!WaitForCondition(condition, timeout_ms)) {
+        LOG(ERROR) << "Timed out waiting for device path: " << unique_path;
+        DeleteDevice(name);
+        return false;
+    }
+    return true;
+}
+
+bool DeviceMapper::GetDeviceUniquePath(const std::string& name, std::string* path) {
+    struct dm_ioctl io;
+    InitIo(&io, name);
+    if (ioctl(fd_, DM_DEV_STATUS, &io) < 0) {
+        PLOG(ERROR) << "Failed to get device path: " << name;
+        return false;
+    }
+
+    if (io.uuid[0] == '\0') {
+        LOG(ERROR) << "Device does not have a unique path: " << name;
+        return false;
+    }
+    *path = "/dev/block/mapper/by-uuid/"s + io.uuid;
+    return true;
 }
 
 DmDeviceState DeviceMapper::GetState(const std::string& name) const {
@@ -111,11 +184,8 @@
 }
 
 bool DeviceMapper::CreateDevice(const std::string& name, const DmTable& table) {
-    if (!CreateDevice(name)) {
-        return false;
-    }
-    if (!LoadTableAndActivate(name, table)) {
-        DeleteDevice(name);
+    std::string ignore_path;
+    if (!CreateDevice(name, table, &ignore_path, 0ms)) {
         return false;
     }
     return true;
diff --git a/fs_mgr/libdm/dm_test.cpp b/fs_mgr/libdm/dm_test.cpp
index c5881dd..7a834e2 100644
--- a/fs_mgr/libdm/dm_test.cpp
+++ b/fs_mgr/libdm/dm_test.cpp
@@ -52,10 +52,10 @@
   public:
     TempDevice(const std::string& name, const DmTable& table)
         : dm_(DeviceMapper::Instance()), name_(name), valid_(false) {
-        valid_ = dm_.CreateDevice(name, table);
+        valid_ = dm_.CreateDevice(name, table, &path_, 5s);
     }
     TempDevice(TempDevice&& other) noexcept
-        : dm_(other.dm_), name_(other.name_), valid_(other.valid_) {
+        : dm_(other.dm_), name_(other.name_), path_(other.path_), valid_(other.valid_) {
         other.valid_ = false;
     }
     ~TempDevice() {
@@ -70,29 +70,7 @@
         valid_ = false;
         return dm_.DeleteDevice(name_);
     }
-    bool WaitForUdev() const {
-        auto start_time = std::chrono::steady_clock::now();
-        while (true) {
-            if (!access(path().c_str(), F_OK)) {
-                return true;
-            }
-            if (errno != ENOENT) {
-                return false;
-            }
-            std::this_thread::sleep_for(50ms);
-            std::chrono::duration elapsed = std::chrono::steady_clock::now() - start_time;
-            if (elapsed >= 5s) {
-                return false;
-            }
-        }
-    }
-    std::string path() const {
-        std::string device_path;
-        if (!dm_.GetDmDevicePathByName(name_, &device_path)) {
-            return "";
-        }
-        return device_path;
-    }
+    std::string path() const { return path_; }
     const std::string& name() const { return name_; }
     bool valid() const { return valid_; }
 
@@ -109,6 +87,7 @@
   private:
     DeviceMapper& dm_;
     std::string name_;
+    std::string path_;
     bool valid_;
 };
 
@@ -139,7 +118,6 @@
     TempDevice dev("libdm-test-dm-linear", table);
     ASSERT_TRUE(dev.valid());
     ASSERT_FALSE(dev.path().empty());
-    ASSERT_TRUE(dev.WaitForUdev());
 
     auto& dm = DeviceMapper::Instance();
 
@@ -290,7 +268,6 @@
     origin_dev_ = std::make_unique<TempDevice>("libdm-test-dm-snapshot-origin", origin_table);
     ASSERT_TRUE(origin_dev_->valid());
     ASSERT_FALSE(origin_dev_->path().empty());
-    ASSERT_TRUE(origin_dev_->WaitForUdev());
 
     // chunk size = 4K blocks.
     DmTable snap_table;
@@ -302,7 +279,6 @@
     snapshot_dev_ = std::make_unique<TempDevice>("libdm-test-dm-snapshot", snap_table);
     ASSERT_TRUE(snapshot_dev_->valid());
     ASSERT_FALSE(snapshot_dev_->path().empty());
-    ASSERT_TRUE(snapshot_dev_->WaitForUdev());
 
     setup_ok_ = true;
 }
diff --git a/fs_mgr/libdm/include/libdm/dm.h b/fs_mgr/libdm/include/libdm/dm.h
index 08376c0..9c0c2f3 100644
--- a/fs_mgr/libdm/include/libdm/dm.h
+++ b/fs_mgr/libdm/include/libdm/dm.h
@@ -25,6 +25,7 @@
 #include <sys/sysmacros.h>
 #include <unistd.h>
 
+#include <chrono>
 #include <memory>
 #include <string>
 #include <utility>
@@ -73,10 +74,6 @@
     // Returns 'true' on success, false otherwise.
     bool DeleteDevice(const std::string& name);
 
-    // Reads the device mapper table from the device with given anme and
-    // returns it in a DmTable object.
-    const std::unique_ptr<DmTable> table(const std::string& name) const;
-
     // Returns the current state of the underlying device mapper device
     // with given name.
     // One of INVALID, SUSPENDED or ACTIVE.
@@ -84,6 +81,33 @@
 
     // Creates a device, loads the given table, and activates it. If the device
     // is not able to be activated, it is destroyed, and false is returned.
+    // After creation, |path| contains the result of calling
+    // GetDmDevicePathByName, and the path is guaranteed to exist. If after
+    // |timeout_ms| the path is not available, the device will be deleted and
+    // this function will return false.
+    //
+    // This variant must be used when depending on the device path. The
+    // following manual sequence should not be used:
+    //
+    //   1. CreateDevice(name, table)
+    //   2. GetDmDevicePathByName(name, &path)
+    //   3. fs_mgr::WaitForFile(path, <timeout>)
+    //
+    // This sequence has a race condition where, if another process deletes a
+    // device, CreateDevice may acquire the same path. When this happens, the
+    // WaitForFile() may early-return since ueventd has not yet processed all
+    // of the outstanding udev events. The caller may unexpectedly get an
+    // ENOENT on a system call using the affected path.
+    //
+    // If |timeout_ms| is 0ms, then this function will return true whether or
+    // not |path| is available. It is the caller's responsibility to ensure
+    // there are no races.
+    bool CreateDevice(const std::string& name, const DmTable& table, std::string* path,
+                      const std::chrono::milliseconds& timeout_ms);
+
+    // Create a device and activate the given table, without waiting to acquire
+    // a valid path. If the caller will use GetDmDevicePathByName(), it should
+    // use the timeout variant above.
     bool CreateDevice(const std::string& name, const DmTable& table);
 
     // Loads the device mapper table from parameter into the underlying device
@@ -110,8 +134,21 @@
     // Returns the path to the device mapper device node in '/dev' corresponding to
     // 'name'. If the device does not exist, false is returned, and the path
     // parameter is not set.
+    //
+    // This returns a path in the format "/dev/block/dm-N" that can be easily
+    // re-used with sysfs.
+    //
+    // WaitForFile() should not be used in conjunction with this call, since it
+    // could race with ueventd.
     bool GetDmDevicePathByName(const std::string& name, std::string* path);
 
+    // Returns a device's unique path as generated by ueventd. This will return
+    // true as long as the device has been created, even if ueventd has not
+    // processed it yet.
+    //
+    // The formatting of this path is /dev/block/mapper/by-uuid/<uuid>.
+    bool GetDeviceUniquePath(const std::string& name, std::string* path);
+
     // Returns the dev_t for the named device-mapper node.
     bool GetDeviceNumber(const std::string& name, dev_t* dev);
 
@@ -158,18 +195,12 @@
     // limit we are imposing here of 256.
     static constexpr uint32_t kMaxPossibleDmDevices = 256;
 
+    bool CreateDevice(const std::string& name, const std::string& uuid = {});
     bool GetTable(const std::string& name, uint32_t flags, std::vector<TargetInfo>* table);
-
     void InitIo(struct dm_ioctl* io, const std::string& name = std::string()) const;
 
     DeviceMapper();
 
-    // Creates a device mapper device with given name.
-    // Return 'true' on success and 'false' on failure to
-    // create OR if a device mapper device with the same name already
-    // exists.
-    bool CreateDevice(const std::string& name);
-
     int fd_;
     // Non-copyable & Non-movable
     DeviceMapper(const DeviceMapper&) = delete;
diff --git a/fs_mgr/libfs_avb/Android.bp b/fs_mgr/libfs_avb/Android.bp
index a3c76ab..414a186 100644
--- a/fs_mgr/libfs_avb/Android.bp
+++ b/fs_mgr/libfs_avb/Android.bp
@@ -61,6 +61,7 @@
         "libavb",
         "libavb_host_sysdeps",
         "libdm",
+        "libext2_uuid",
         "libfs_avb",
         "libfstab",
         "libgtest_host",
diff --git a/fs_mgr/libfs_avb/avb_util.cpp b/fs_mgr/libfs_avb/avb_util.cpp
index d9650f3..4505382 100644
--- a/fs_mgr/libfs_avb/avb_util.cpp
+++ b/fs_mgr/libfs_avb/avb_util.cpp
@@ -104,31 +104,23 @@
     }
     table.set_readonly(true);
 
+    std::chrono::milliseconds timeout = {};
+    if (wait_for_verity_dev) timeout = 1s;
+
+    std::string dev_path;
     const std::string mount_point(Basename(fstab_entry->mount_point));
     const std::string device_name(GetVerityDeviceName(*fstab_entry));
     android::dm::DeviceMapper& dm = android::dm::DeviceMapper::Instance();
-    if (!dm.CreateDevice(device_name, table)) {
+    if (!dm.CreateDevice(device_name, table, &dev_path, timeout)) {
         LERROR << "Couldn't create verity device!";
         return false;
     }
 
-    std::string dev_path;
-    if (!dm.GetDmDevicePathByName(device_name, &dev_path)) {
-        LERROR << "Couldn't get verity device path!";
-        return false;
-    }
-
     // Marks the underlying block device as read-only.
     SetBlockDeviceReadOnly(fstab_entry->blk_device);
 
     // Updates fstab_rec->blk_device to verity device name.
     fstab_entry->blk_device = dev_path;
-
-    // Makes sure we've set everything up properly.
-    if (wait_for_verity_dev && !WaitForFile(dev_path, 1s)) {
-        return false;
-    }
-
     return true;
 }
 
diff --git a/init/Android.mk b/init/Android.mk
index 9017772..006e1bf 100644
--- a/init/Android.mk
+++ b/init/Android.mk
@@ -113,6 +113,7 @@
     libunwindstack \
     libbacktrace \
     libmodprobe \
+    libext2_uuid \
 
 LOCAL_SANITIZE := signed-integer-overflow
 # First stage init is weird: it may start without stdout/stderr, and no /proc.
diff --git a/init/devices.cpp b/init/devices.cpp
index e8e6cd7..f6e453a 100644
--- a/init/devices.cpp
+++ b/init/devices.cpp
@@ -22,7 +22,6 @@
 #include <unistd.h>
 
 #include <chrono>
-#include <map>
 #include <memory>
 #include <string>
 #include <thread>
@@ -111,24 +110,16 @@
 // the supplied buffer with the dm module's instantiated name.
 // If it doesn't start with a virtual block device, or there is some
 // error, return false.
-static bool FindDmDevicePartition(const std::string& path, std::string* result) {
-    result->clear();
+static bool FindDmDevice(const std::string& path, std::string* name, std::string* uuid) {
     if (!StartsWith(path, "/devices/virtual/block/dm-")) return false;
-    if (getpid() == 1) return false;  // first_stage_init has no sepolicy needs
 
-    static std::map<std::string, std::string> cache;
-    // wait_for_file will not work, the content is also delayed ...
-    for (android::base::Timer t; t.duration() < 200ms; std::this_thread::sleep_for(10ms)) {
-        if (ReadFileToString("/sys" + path + "/dm/name", result) && !result->empty()) {
-            // Got it, set cache with result, when node arrives
-            cache[path] = *result = Trim(*result);
-            return true;
-        }
+    if (!ReadFileToString("/sys" + path + "/dm/name", name)) {
+        return false;
     }
-    auto it = cache.find(path);
-    if ((it == cache.end()) || (it->second.empty())) return false;
-    // Return cached results, when node goes away
-    *result = it->second;
+    ReadFileToString("/sys" + path + "/dm/uuid", uuid);
+
+    *name = android::base::Trim(*name);
+    *uuid = android::base::Trim(*uuid);
     return true;
 }
 
@@ -325,6 +316,7 @@
     std::string device;
     std::string type;
     std::string partition;
+    std::string uuid;
 
     if (FindPlatformDevice(uevent.path, &device)) {
         // Skip /devices/platform or /devices/ if present
@@ -342,8 +334,12 @@
         type = "pci";
     } else if (FindVbdDevicePrefix(uevent.path, &device)) {
         type = "vbd";
-    } else if (FindDmDevicePartition(uevent.path, &partition)) {
-        return {"/dev/block/mapper/" + partition};
+    } else if (FindDmDevice(uevent.path, &partition, &uuid)) {
+        std::vector<std::string> symlinks = {"/dev/block/mapper/" + partition};
+        if (!uuid.empty()) {
+            symlinks.emplace_back("/dev/block/mapper/by-uuid/" + uuid);
+        }
+        return symlinks;
     } else {
         return {};
     }
@@ -379,10 +375,41 @@
     return links;
 }
 
+static void RemoveDeviceMapperLinks(const std::string& devpath) {
+    std::vector<std::string> dirs = {
+            "/dev/block/mapper",
+            "/dev/block/mapper/by-uuid",
+    };
+    for (const auto& dir : dirs) {
+        if (access(dir.c_str(), F_OK) != 0) continue;
+
+        std::unique_ptr<DIR, decltype(&closedir)> dh(opendir(dir.c_str()), closedir);
+        if (!dh) {
+            PLOG(ERROR) << "Failed to open directory " << dir;
+            continue;
+        }
+
+        struct dirent* dp;
+        std::string link_path;
+        while ((dp = readdir(dh.get())) != nullptr) {
+            if (dp->d_type != DT_LNK) continue;
+
+            auto path = dir + "/" + dp->d_name;
+            if (Readlink(path, &link_path) && link_path == devpath) {
+                unlink(path.c_str());
+            }
+        }
+    }
+}
+
 void DeviceHandler::HandleDevice(const std::string& action, const std::string& devpath, bool block,
                                  int major, int minor, const std::vector<std::string>& links) const {
     if (action == "add") {
         MakeDevice(devpath, block, major, minor, links);
+    }
+
+    // We don't have full device-mapper information until a change event is fired.
+    if (action == "add" || (action == "change" && StartsWith(devpath, "/dev/block/dm-"))) {
         for (const auto& link : links) {
             if (!mkdir_recursive(Dirname(link), 0755)) {
                 PLOG(ERROR) << "Failed to create directory " << Dirname(link);
@@ -401,6 +428,9 @@
     }
 
     if (action == "remove") {
+        if (StartsWith(devpath, "/dev/block/dm-")) {
+            RemoveDeviceMapperLinks(devpath);
+        }
         for (const auto& link : links) {
             std::string link_path;
             if (Readlink(link, &link_path) && link_path == devpath) {