diff --git a/cmds/installd/InstalldNativeService.cpp b/cmds/installd/InstalldNativeService.cpp
index 39ef0b5..b5ae5c6 100644
--- a/cmds/installd/InstalldNativeService.cpp
+++ b/cmds/installd/InstalldNativeService.cpp
@@ -321,10 +321,17 @@
     int res = 0;
     char* before = nullptr;
     char* after = nullptr;
+    if (!existing) {
+        if (selinux_android_restorecon_pkgdir(path.c_str(), seInfo.c_str(), uid,
+                SELINUX_ANDROID_RESTORECON_RECURSE) < 0) {
+            PLOG(ERROR) << "Failed recursive restorecon for " << path;
+            goto fail;
+        }
+        return res;
+    }
 
     // Note that SELINUX_ANDROID_RESTORECON_DATADATA flag is set by
     // libselinux. Not needed here.
-
     if (lgetfilecon(path.c_str(), &before) < 0) {
         PLOG(ERROR) << "Failed before getfilecon for " << path;
         goto fail;
@@ -361,12 +368,6 @@
     return res;
 }
 
-static int restorecon_app_data_lazy(const std::string& parent, const char* name,
-        const std::string& seInfo, uid_t uid, bool existing) {
-    return restorecon_app_data_lazy(StringPrintf("%s/%s", parent.c_str(), name), seInfo, uid,
-            existing);
-}
-
 static int prepare_app_dir(const std::string& path, mode_t target_mode, uid_t uid) {
     if (fs_prepare_dir_strict(path.c_str(), target_mode, uid, uid) != 0) {
         PLOG(ERROR) << "Failed to prepare " << path;
@@ -512,8 +513,14 @@
         int32_t uid, int32_t* previousUid, int32_t cacheGid,
         const std::string& seInfo, mode_t targetMode) {
     struct stat st{};
-    bool existing = (stat(path.c_str(), &st) == 0);
-    if (existing) {
+    bool parent_dir_exists = (stat(path.c_str(), &st) == 0);
+
+    auto cache_path = StringPrintf("%s/%s", path.c_str(), "cache");
+    auto code_cache_path = StringPrintf("%s/%s", path.c_str(), "code_cache");
+    bool cache_exists = (access(cache_path.c_str(), F_OK) == 0);
+    bool code_cache_exists = (access(code_cache_path.c_str(), F_OK) == 0);
+
+    if (parent_dir_exists) {
         if (*previousUid < 0) {
             // If previousAppId is -1 in CreateAppDataArgs, we will assume the current owner
             // of the directory as previousUid. This is required because it is not always possible
@@ -527,6 +534,7 @@
         }
     }
 
+    // Prepare only the parent app directory
     if (prepare_app_dir(path, targetMode, uid) ||
             prepare_app_cache_dir(path, "cache", 02771, uid, cacheGid) ||
             prepare_app_cache_dir(path, "code_cache", 02771, uid, cacheGid)) {
@@ -534,12 +542,23 @@
     }
 
     // Consider restorecon over contents if label changed
-    if (restorecon_app_data_lazy(path, seInfo, uid, existing) ||
-            restorecon_app_data_lazy(path, "cache", seInfo, uid, existing) ||
-            restorecon_app_data_lazy(path, "code_cache", seInfo, uid, existing)) {
+    if (restorecon_app_data_lazy(path, seInfo, uid, parent_dir_exists)) {
         return error("Failed to restorecon " + path);
     }
 
+    // If the parent dir exists, the restorecon would already have been done
+    // as a part of the recursive restorecon above
+    if (parent_dir_exists && !cache_exists
+            && restorecon_app_data_lazy(cache_path, seInfo, uid, false)) {
+        return error("Failed to restorecon " + cache_path);
+    }
+
+    // If the parent dir exists, the restorecon would already have been done
+    // as a part of the recursive restorecon above
+    if (parent_dir_exists && !code_cache_exists
+            && restorecon_app_data_lazy(code_cache_path, seInfo, uid, false)) {
+        return error("Failed to restorecon " + code_cache_path);
+    }
     return ok();
 }