diff --git a/services/core/java/com/android/server/appop/AppOpsService.java b/services/core/java/com/android/server/appop/AppOpsService.java
index 5c95d43..fe36170 100644
--- a/services/core/java/com/android/server/appop/AppOpsService.java
+++ b/services/core/java/com/android/server/appop/AppOpsService.java
@@ -1034,7 +1034,7 @@
                                 new Ops(pkgName, uidState));
                     }
 
-                    createSandboxUidStateIfNotExistsForAppLocked(uid);
+                    createSandboxUidStateIfNotExistsForAppLocked(uid, null);
                 }
             } else if (action.equals(ACTION_PACKAGE_REMOVED) && !intent.hasExtra(EXTRA_REPLACING)) {
                 synchronized (AppOpsService.this) {
@@ -1253,19 +1253,33 @@
     void initializeUidStates() {
         UserManagerInternal umi = getUserManagerInternal();
         synchronized (this) {
+            SparseBooleanArray knownUids = new SparseBooleanArray();
+
+            for (int uid : NON_PACKAGE_UIDS) {
+                if (!mUidStates.contains(uid)) {
+                    mUidStates.put(uid, new UidState(uid));
+                }
+                knownUids.put(uid, true);
+            }
+
             int[] userIds = umi.getUserIds();
             try (PackageManagerLocal.UnfilteredSnapshot snapshot =
                          getPackageManagerLocal().withUnfilteredSnapshot()) {
                 Map<String, PackageState> packageStates = snapshot.getPackageStates();
                 for (int i = 0; i < userIds.length; i++) {
                     int userId = userIds[i];
-                    initializeUserUidStatesLocked(userId, packageStates);
+                    initializeUserUidStatesLocked(userId, packageStates, knownUids);
                 }
             }
 
-            for (int uid : NON_PACKAGE_UIDS) {
-                mUidStates.put(uid, new UidState(uid));
+            // Remove what may have been added during persistence parsing
+            for (int i = mUidStates.size() - 1; i >= 0; i--) {
+                int uid = mUidStates.keyAt(i);
+                if (!knownUids.get(uid, false)) {
+                    mUidStates.removeAt(i);
+                }
             }
+
             mUidStatesInitialized = true;
         }
     }
@@ -1274,26 +1288,34 @@
         synchronized (this) {
             try (PackageManagerLocal.UnfilteredSnapshot snapshot =
                     getPackageManagerLocal().withUnfilteredSnapshot()) {
-                initializeUserUidStatesLocked(userId, snapshot.getPackageStates());
+                initializeUserUidStatesLocked(userId, snapshot.getPackageStates(), null);
             }
         }
     }
 
     private void initializeUserUidStatesLocked(int userId, Map<String,
-            PackageState> packageStates) {
+            PackageState> packageStates, SparseBooleanArray knownUids) {
         for (Map.Entry<String, PackageState> entry : packageStates.entrySet()) {
-            int appId = entry.getValue().getAppId();
+            PackageState packageState = entry.getValue();
+            if (packageState.isApex()) {
+                continue;
+            }
+            int appId = packageState.getAppId();
             String packageName = entry.getKey();
 
-            initializePackageUidStateLocked(userId, appId, packageName);
+            initializePackageUidStateLocked(userId, appId, packageName, knownUids);
         }
     }
 
     /*
       Be careful not to clear any existing data; only want to add objects that don't already exist.
      */
-    private void initializePackageUidStateLocked(int userId, int appId, String packageName) {
+    private void initializePackageUidStateLocked(int userId, int appId, String packageName,
+            SparseBooleanArray knownUids) {
         int uid = UserHandle.getUid(userId, appId);
+        if (knownUids != null) {
+            knownUids.put(uid, true);
+        }
         UidState uidState = getUidStateLocked(uid, true);
         Ops ops = uidState.pkgOps.get(packageName);
         if (ops == null) {
@@ -1311,7 +1333,7 @@
             }
         }
 
-        createSandboxUidStateIfNotExistsForAppLocked(uid);
+        createSandboxUidStateIfNotExistsForAppLocked(uid, knownUids);
     }
 
     /**
@@ -4246,8 +4268,15 @@
         return uidState;
     }
 
-    private void createSandboxUidStateIfNotExistsForAppLocked(int uid) {
+    private void createSandboxUidStateIfNotExistsForAppLocked(int uid,
+            SparseBooleanArray knownUids) {
+        if (UserHandle.getAppId(uid) < Process.FIRST_APPLICATION_UID) {
+            return;
+        }
         final int sandboxUid = Process.toSdkSandboxUid(uid);
+        if (knownUids != null) {
+            knownUids.put(sandboxUid, true);
+        }
         getUidStateLocked(sandboxUid, true);
     }