diff --git a/cmds/installd/InstalldNativeService.cpp b/cmds/installd/InstalldNativeService.cpp
index c3256fc..89d4868 100644
--- a/cmds/installd/InstalldNativeService.cpp
+++ b/cmds/installd/InstalldNativeService.cpp
@@ -968,13 +968,13 @@
     binder::Status res = ok();
     if (flags & FLAG_STORAGE_CE) {
         auto path = create_data_user_ce_package_path(uuid_, userId, pkgname, ceDataInode);
-        if (delete_dir_contents_and_dir(path) != 0) {
+        if (rename_delete_dir_contents_and_dir(path) != 0) {
             res = error("Failed to delete " + path);
         }
     }
     if (flags & FLAG_STORAGE_DE) {
         auto path = create_data_user_de_package_path(uuid_, userId, pkgname);
-        if (delete_dir_contents_and_dir(path) != 0) {
+        if (rename_delete_dir_contents_and_dir(path) != 0) {
             res = error("Failed to delete " + path);
         }
         if ((flags & FLAG_CLEAR_APP_DATA_KEEP_ART_PROFILES) == 0) {
@@ -1005,16 +1005,15 @@
             }
 
             auto path = StringPrintf("%s/Android/data/%s", extPath.c_str(), pkgname);
-            if (delete_dir_contents_and_dir(path, true) != 0) {
+            if (rename_delete_dir_contents_and_dir(path, true) != 0) {
                 res = error("Failed to delete contents of " + path);
             }
-
             path = StringPrintf("%s/Android/media/%s", extPath.c_str(), pkgname);
-            if (delete_dir_contents_and_dir(path, true) != 0) {
+            if (rename_delete_dir_contents_and_dir(path, true) != 0) {
                 res = error("Failed to delete contents of " + path);
             }
             path = StringPrintf("%s/Android/obb/%s", extPath.c_str(), pkgname);
-            if (delete_dir_contents_and_dir(path, true) != 0) {
+            if (rename_delete_dir_contents_and_dir(path, true) != 0) {
                 res = error("Failed to delete contents of " + path);
             }
         }
@@ -1562,27 +1561,27 @@
     binder::Status res = ok();
     if (flags & FLAG_STORAGE_DE) {
         auto path = create_data_user_de_path(uuid_, userId);
-        if (delete_dir_contents_and_dir(path, true) != 0) {
+        if (rename_delete_dir_contents_and_dir(path, true) != 0) {
             res = error("Failed to delete " + path);
         }
         if (uuid_ == nullptr) {
             path = create_data_misc_legacy_path(userId);
-            if (delete_dir_contents_and_dir(path, true) != 0) {
+            if (rename_delete_dir_contents_and_dir(path, true) != 0) {
                 res = error("Failed to delete " + path);
             }
             path = create_primary_cur_profile_dir_path(userId);
-            if (delete_dir_contents_and_dir(path, true) != 0) {
+            if (rename_delete_dir_contents_and_dir(path, true) != 0) {
                 res = error("Failed to delete " + path);
             }
         }
     }
     if (flags & FLAG_STORAGE_CE) {
         auto path = create_data_user_ce_path(uuid_, userId);
-        if (delete_dir_contents_and_dir(path, true) != 0) {
+        if (rename_delete_dir_contents_and_dir(path, true) != 0) {
             res = error("Failed to delete " + path);
         }
         path = findDataMediaPath(uuid, userId);
-        if (delete_dir_contents_and_dir(path, true) != 0) {
+        if (rename_delete_dir_contents_and_dir(path, true) != 0) {
             res = error("Failed to delete " + path);
         }
     }
@@ -3324,5 +3323,18 @@
     return ok();
 }
 
+binder::Status InstalldNativeService::cleanupDeletedDirs(const std::optional<std::string>& uuid) {
+    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);
+    }
+    return ok();
+}
+
 }  // namespace installd
 }  // namespace android