diff --git a/cmds/installd/commands.cpp b/cmds/installd/commands.cpp
index 6533ab1..2df48aa 100644
--- a/cmds/installd/commands.cpp
+++ b/cmds/installd/commands.cpp
@@ -99,23 +99,64 @@
     return StringPrintf("%s/%s", profile_dir.c_str(), PRIMARY_PROFILE_NAME);
 }
 
-static int prepare_app_dir(const std::string& path, mode_t target_mode, uid_t uid,
-        const char* pkgname, const char* seinfo) {
+/**
+ * Perform restorecon of the given path, but only perform recursive restorecon
+ * if the label of that top-level file actually changed.  This can save us
+ * significant time by avoiding no-op traversals of large filesystem trees.
+ */
+static int restorecon_app_data_lazy(const char* path, const char* seinfo, uid_t uid) {
+    int res = 0;
+    char* before = nullptr;
+    char* after = nullptr;
+
+    // Note that SELINUX_ANDROID_RESTORECON_DATADATA flag is set by
+    // libselinux. Not needed here.
+
+    if (lgetfilecon(path, &before) < 0) {
+        PLOG(ERROR) << "Failed before getfilecon for " << path;
+        goto fail;
+    }
+    if (selinux_android_restorecon_pkgdir(path, seinfo, uid, 0) < 0) {
+        PLOG(ERROR) << "Failed top-level restorecon for " << path;
+        goto fail;
+    }
+    if (lgetfilecon(path, &after) < 0) {
+        PLOG(ERROR) << "Failed after getfilecon for " << path;
+        goto fail;
+    }
+
+    // If the initial top-level restorecon above changed the label, then go
+    // back and restorecon everything recursively
+    if (strcmp(before, after)) {
+        LOG(DEBUG) << "Detected label change from " << before << " to " << after << " at " << path
+                << "; running recursive restorecon";
+        if (selinux_android_restorecon_pkgdir(path, seinfo, uid,
+                SELINUX_ANDROID_RESTORECON_RECURSE) < 0) {
+            PLOG(ERROR) << "Failed recursive restorecon for " << path;
+            goto fail;
+        }
+    }
+
+    goto done;
+fail:
+    res = -1;
+done:
+    free(before);
+    free(after);
+    return res;
+}
+
+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;
         return -1;
     }
-    if (selinux_android_setfilecon(path.c_str(), pkgname, seinfo, uid) < 0) {
-        PLOG(ERROR) << "Failed to setfilecon " << path;
-        return -1;
-    }
     return 0;
 }
 
 static int prepare_app_dir(const std::string& parent, const char* name, mode_t target_mode,
-        uid_t uid, const char* pkgname, const char* seinfo) {
-    return prepare_app_dir(StringPrintf("%s/%s", parent.c_str(), name), target_mode, uid, pkgname,
-            seinfo);
+        uid_t uid) {
+    return prepare_app_dir(StringPrintf("%s/%s", parent.c_str(), name), target_mode, uid);
 }
 
 int create_app_data(const char *uuid, const char *pkgname, userid_t userid, int flags,
@@ -124,9 +165,14 @@
     mode_t target_mode = target_sdk_version >= MIN_RESTRICTED_HOME_SDK_VERSION ? 0700 : 0751;
     if (flags & FLAG_STORAGE_CE) {
         auto path = create_data_user_ce_package_path(uuid, userid, pkgname);
-        if (prepare_app_dir(path, target_mode, uid, pkgname, seinfo) ||
-                prepare_app_dir(path, "cache", 0771, uid, pkgname, seinfo) ||
-                prepare_app_dir(path, "code_cache", 0771, uid, pkgname, seinfo)) {
+        if (prepare_app_dir(path, target_mode, uid) ||
+                prepare_app_dir(path, "cache", 0771, uid) ||
+                prepare_app_dir(path, "code_cache", 0771, uid)) {
+            return -1;
+        }
+
+        // Consider restorecon over contents if label changed
+        if (restorecon_app_data_lazy(path.c_str(), seinfo, uid)) {
             return -1;
         }
 
@@ -139,11 +185,16 @@
     }
     if (flags & FLAG_STORAGE_DE) {
         auto path = create_data_user_de_package_path(uuid, userid, pkgname);
-        if (prepare_app_dir(path, target_mode, uid, pkgname, seinfo)) {
+        if (prepare_app_dir(path, target_mode, uid)) {
             // TODO: include result once 25796509 is fixed
             return 0;
         }
 
+        // Consider restorecon over contents if label changed
+        if (restorecon_app_data_lazy(path.c_str(), seinfo, uid)) {
+            return -1;
+        }
+
         if (property_get_bool("dalvik.vm.usejitprofiles")) {
             const std::string profile_path = create_data_user_profile_package_path(userid, pkgname);
             // read-write-execute only for the app user.