diff --git a/cmds/installd/InstalldNativeService.cpp b/cmds/installd/InstalldNativeService.cpp
index 5051132..953847e 100644
--- a/cmds/installd/InstalldNativeService.cpp
+++ b/cmds/installd/InstalldNativeService.cpp
@@ -3176,16 +3176,20 @@
     return ok();
 }
 
-binder::Status InstalldNativeService::cleanupDeletedDirs(const std::optional<std::string>& uuid) {
+binder::Status InstalldNativeService::cleanupInvalidPackageDirs(
+        const std::optional<std::string>& uuid, int32_t userId, int32_t flags) {
     const char* uuid_cstr = uuid ? uuid->c_str() : nullptr;
-    const auto users = get_known_users(uuid_cstr);
-    for (auto userId : users) {
-        auto ce_path = create_data_user_ce_path(uuid_cstr, userId);
-        auto de_path = create_data_user_de_path(uuid_cstr, userId);
 
-        find_and_delete_renamed_deleted_dirs_under_path(ce_path);
-        find_and_delete_renamed_deleted_dirs_under_path(de_path);
+    if (flags & FLAG_STORAGE_CE) {
+        auto ce_path = create_data_user_ce_path(uuid_cstr, userId);
+        cleanup_invalid_package_dirs_under_path(ce_path);
     }
+
+    if (flags & FLAG_STORAGE_DE) {
+        auto de_path = create_data_user_de_path(uuid_cstr, userId);
+        cleanup_invalid_package_dirs_under_path(de_path);
+    }
+
     return ok();
 }
 
diff --git a/cmds/installd/InstalldNativeService.h b/cmds/installd/InstalldNativeService.h
index 4310319..96783c3 100644
--- a/cmds/installd/InstalldNativeService.h
+++ b/cmds/installd/InstalldNativeService.h
@@ -184,7 +184,8 @@
 
     binder::Status migrateLegacyObbData();
 
-    binder::Status cleanupDeletedDirs(const std::optional<std::string>& uuid);
+    binder::Status cleanupInvalidPackageDirs(const std::optional<std::string>& uuid, int32_t userId,
+                                             int32_t flags);
 
 private:
     std::recursive_mutex mLock;
diff --git a/cmds/installd/binder/android/os/IInstalld.aidl b/cmds/installd/binder/android/os/IInstalld.aidl
index cd47f50..f4fd9a9 100644
--- a/cmds/installd/binder/android/os/IInstalld.aidl
+++ b/cmds/installd/binder/android/os/IInstalld.aidl
@@ -126,7 +126,7 @@
 
     void migrateLegacyObbData();
 
-    void cleanupDeletedDirs(@nullable @utf8InCpp String uuid);
+    void cleanupInvalidPackageDirs(@nullable @utf8InCpp String uuid, int userId, int flags);
 
     const int FLAG_STORAGE_DE = 0x1;
     const int FLAG_STORAGE_CE = 0x2;
diff --git a/cmds/installd/tests/installd_service_test.cpp b/cmds/installd/tests/installd_service_test.cpp
index 69166c3..806797f 100644
--- a/cmds/installd/tests/installd_service_test.cpp
+++ b/cmds/installd/tests/installd_service_test.cpp
@@ -275,8 +275,8 @@
     EXPECT_FALSE(exists_renamed_deleted_dir());
 }
 
-TEST_F(ServiceTest, CleanupDeletedDirs) {
-    LOG(INFO) << "CleanupDeletedDirs";
+TEST_F(ServiceTest, CleanupInvalidPackageDirs) {
+    LOG(INFO) << "CleanupInvalidPackageDirs";
 
     mkdir("5b14b6458a44==deleted==", 10000, 10000, 0700);
     mkdir("5b14b6458a44==deleted==/foo", 10000, 10000, 0700);
@@ -286,11 +286,11 @@
 
     auto fd = create("5b14b6458a44==deleted==/bar/opened_file", 10000, 20000, 0700);
 
-    mkdir("5b14b6458a44==NOTdeleted==", 10000, 10000, 0700);
-    mkdir("5b14b6458a44==NOTdeleted==/foo", 10000, 10000, 0700);
-    touch("5b14b6458a44==NOTdeleted==/foo/file", 10000, 20000, 0700);
-    mkdir("5b14b6458a44==NOTdeleted==/bar", 10000, 20000, 0700);
-    touch("5b14b6458a44==NOTdeleted==/bar/file", 10000, 20000, 0700);
+    mkdir("b14b6458a44NOTdeleted", 10000, 10000, 0700);
+    mkdir("b14b6458a44NOTdeleted/foo", 10000, 10000, 0700);
+    touch("b14b6458a44NOTdeleted/foo/file", 10000, 20000, 0700);
+    mkdir("b14b6458a44NOTdeleted/bar", 10000, 20000, 0700);
+    touch("b14b6458a44NOTdeleted/bar/file", 10000, 20000, 0700);
 
     mkdir("com.example", 10000, 10000, 0700);
     mkdir("com.example/foo", 10000, 10000, 0700);
@@ -310,10 +310,10 @@
     EXPECT_TRUE(exists("5b14b6458a44==deleted==/bar/file"));
     EXPECT_TRUE(exists("5b14b6458a44==deleted==/bar/opened_file"));
 
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/foo"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/foo/file"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/bar"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/bar/file"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/foo"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/foo/file"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/bar"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/bar/file"));
 
     EXPECT_TRUE(exists("com.example/foo"));
     EXPECT_TRUE(exists("com.example/foo/file"));
@@ -327,7 +327,7 @@
 
     EXPECT_TRUE(exists_renamed_deleted_dir());
 
-    service->cleanupDeletedDirs(testUuid);
+    service->cleanupInvalidPackageDirs(testUuid, 0, FLAG_STORAGE_CE | FLAG_STORAGE_DE);
 
     EXPECT_EQ(::close(fd), 0);
 
@@ -337,10 +337,10 @@
     EXPECT_FALSE(exists("5b14b6458a44==deleted==/bar/file"));
     EXPECT_FALSE(exists("5b14b6458a44==deleted==/bar/opened_file"));
 
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/foo"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/foo/file"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/bar"));
-    EXPECT_TRUE(exists("5b14b6458a44==NOTdeleted==/bar/file"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/foo"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/foo/file"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/bar"));
+    EXPECT_TRUE(exists("b14b6458a44NOTdeleted/bar/file"));
 
     EXPECT_TRUE(exists("com.example/foo"));
     EXPECT_TRUE(exists("com.example/foo/file"));
diff --git a/cmds/installd/utils.cpp b/cmds/installd/utils.cpp
index a4a21b7..8a00be9 100644
--- a/cmds/installd/utils.cpp
+++ b/cmds/installd/utils.cpp
@@ -652,7 +652,7 @@
     return std::unique_ptr<DIR, DirCloser>(::opendir(dir));
 }
 
-void find_and_delete_renamed_deleted_dirs_under_path(const std::string& pathname) {
+void cleanup_invalid_package_dirs_under_path(const std::string& pathname) {
     auto dir = open_dir(pathname.c_str());
     if (!dir) {
         return;
@@ -668,14 +668,21 @@
         if (de->d_type != DT_DIR) {
             continue;
         }
-        const char* name = de->d_name;
-        if (is_renamed_deleted_dir({name})) {
-            LOG(INFO) << "Deleting renamed data directory: " << name;
+
+        std::string name{de->d_name};
+        // always skip "." and ".."
+        if (name == "." || name == "..") {
+            continue;
+        }
+
+        if (is_renamed_deleted_dir(name) || !is_valid_filename(name) ||
+            !is_valid_package_name(name)) {
+            ALOGI("Deleting renamed or invalid data directory: %s\n", name.c_str());
             // Deleting the content.
-            delete_dir_contents_fd(dfd, name);
+            delete_dir_contents_fd(dfd, name.c_str());
             // Deleting the directory
-            if (unlinkat(dfd, name, AT_REMOVEDIR) < 0) {
-                ALOGE("Couldn't unlinkat %s: %s\n", name, strerror(errno));
+            if (unlinkat(dfd, name.c_str(), AT_REMOVEDIR) < 0) {
+                ALOGE("Couldn't unlinkat %s: %s\n", name.c_str(), strerror(errno));
             }
         }
     }
diff --git a/cmds/installd/utils.h b/cmds/installd/utils.h
index 986080d..ffde562 100644
--- a/cmds/installd/utils.h
+++ b/cmds/installd/utils.h
@@ -121,9 +121,9 @@
 int delete_dir_contents_and_dir(const std::string& pathname, bool ignore_if_missing = false);
 
 bool is_renamed_deleted_dir(std::string_view path);
-
 int rename_delete_dir_contents_and_dir(const std::string& pathname, bool ignore_if_missing = false);
-void find_and_delete_renamed_deleted_dirs_under_path(const std::string& pathname);
+
+void cleanup_invalid_package_dirs_under_path(const std::string& pathname);
 
 int delete_dir_contents(const char *pathname,
                         int also_delete_dir,