diff --git a/services/core/java/com/android/server/policy/PermissionPolicyService.java b/services/core/java/com/android/server/policy/PermissionPolicyService.java
index c13cb38..ec8e1a0 100644
--- a/services/core/java/com/android/server/policy/PermissionPolicyService.java
+++ b/services/core/java/com/android/server/policy/PermissionPolicyService.java
@@ -39,7 +39,9 @@
 import android.content.pm.PackageManagerInternal;
 import android.content.pm.PackageManagerInternal.PackageListObserver;
 import android.content.pm.PermissionInfo;
+import android.content.pm.parsing.AndroidPackage;
 import android.os.Build;
+import android.os.Process;
 import android.os.RemoteException;
 import android.os.ServiceManager;
 import android.os.UserHandle;
@@ -50,15 +52,14 @@
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.LongSparseLongArray;
+import android.util.Pair;
 import android.util.Slog;
-import android.util.SparseArray;
 import android.util.SparseBooleanArray;
 
 import com.android.internal.annotations.GuardedBy;
 import com.android.internal.app.IAppOpsCallback;
 import com.android.internal.app.IAppOpsService;
 import com.android.internal.infra.AndroidFuture;
-import com.android.internal.util.ArrayUtils;
 import com.android.internal.util.IntPair;
 import com.android.internal.util.function.pooled.PooledLambda;
 import com.android.server.FgThread;
@@ -69,7 +70,6 @@
 
 import java.util.ArrayList;
 import java.util.List;
-import java.util.Objects;
 import java.util.concurrent.ExecutionException;
 
 /**
@@ -100,7 +100,7 @@
      * scheduled for a package/user.
      */
     @GuardedBy("mLock")
-    private final ArraySet<Integer> mIsPackageSyncsScheduled = new ArraySet<>();
+    private final ArraySet<Pair<String, Integer>> mIsPackageSyncsScheduled = new ArraySet<>();
 
     public PermissionPolicyService(@NonNull Context context) {
         super(context);
@@ -125,8 +125,10 @@
 
             @Override
             public void onPackageChanged(String packageName, int uid) {
-                if (isStarted(UserHandle.getUserId(uid))) {
-                    synchronizePackagePermissionsAndAppOpsForUser(uid);
+                final int userId = UserHandle.getUserId(uid);
+
+                if (isStarted(userId)) {
+                    synchronizePackagePermissionsAndAppOpsForUser(packageName, userId);
                 }
             }
 
@@ -137,21 +139,12 @@
         });
 
         permManagerInternal.addOnRuntimePermissionStateChangedListener(
-                (packageName, userId) -> {
-                    int uid;
-                    try {
-                        uid = getContext().getPackageManager().getPackageUidAsUser(packageName, 0,
-                                userId);
-                    } catch (NameNotFoundException e) {
-                        Slog.e(LOG_TAG, "Cannot synchronize changed package " + packageName, e);
-                        return;
-                    }
-                    synchronizeUidPermissionsAndAppOpsAsync(uid);
-                });
+                this::synchronizePackagePermissionsAndAppOpsAsyncForUser);
 
         mAppOpsCallback = new IAppOpsCallback.Stub() {
             public void opChanged(int op, int uid, String packageName) {
-                synchronizeUidPermissionsAndAppOpsAsync(uid);
+                synchronizePackagePermissionsAndAppOpsAsyncForUser(packageName,
+                        UserHandle.getUserId(uid));
             }
         };
 
@@ -201,17 +194,19 @@
         return AppOpsManager.opToSwitch(op);
     }
 
-    private void synchronizeUidPermissionsAndAppOpsAsync(int uid) {
-        if (isStarted(UserHandle.getUserId(uid))) {
+    private void synchronizePackagePermissionsAndAppOpsAsyncForUser(@NonNull String packageName,
+            @UserIdInt int changedUserId) {
+        if (isStarted(changedUserId)) {
             synchronized (mLock) {
-                if (mIsPackageSyncsScheduled.add(uid)) {
+                if (mIsPackageSyncsScheduled.add(new Pair<>(packageName, changedUserId))) {
                     FgThread.getHandler().sendMessage(PooledLambda.obtainMessage(
                             PermissionPolicyService
                                     ::synchronizePackagePermissionsAndAppOpsForUser,
-                            this, uid));
+                            this, packageName, changedUserId));
                 } else {
                     if (DEBUG) {
-                        Slog.v(LOG_TAG, "sync for " + uid + " already scheduled");
+                        Slog.v(LOG_TAG, "sync for " + packageName + "/" + changedUserId
+                                + " already scheduled");
                     }
                 }
             }
@@ -340,20 +335,39 @@
     /**
      * Synchronize a single package.
      */
-    private void synchronizePackagePermissionsAndAppOpsForUser(int uid) {
+    private void synchronizePackagePermissionsAndAppOpsForUser(@NonNull String packageName,
+            @UserIdInt int userId) {
         synchronized (mLock) {
-            mIsPackageSyncsScheduled.remove(uid);
+            mIsPackageSyncsScheduled.remove(new Pair<>(packageName, userId));
         }
 
         if (DEBUG) {
             Slog.v(LOG_TAG,
-                    "synchronizePackagePermissionsAndAppOpsForUser(" + uid + ")");
+                    "synchronizePackagePermissionsAndAppOpsForUser(" + packageName + ", "
+                            + userId + ")");
         }
 
+        final PackageManagerInternal packageManagerInternal = LocalServices.getService(
+                PackageManagerInternal.class);
+        final PackageInfo pkg = packageManagerInternal.getPackageInfo(packageName, 0,
+                Process.SYSTEM_UID, userId);
+        if (pkg == null) {
+            return;
+        }
         final PermissionToOpSynchroniser synchroniser = new PermissionToOpSynchroniser(
-                getUserContext(getContext(), UserHandle.getUserHandleForUid(uid)));
-        synchroniser.addUid(uid);
-        synchroniser.syncUids();
+                getUserContext(getContext(), UserHandle.of(userId)));
+        synchroniser.addPackage(pkg.packageName);
+        final String[] sharedPkgNames = packageManagerInternal.getSharedUserPackagesForPackage(
+                pkg.packageName, userId);
+
+        for (String sharedPkgName : sharedPkgNames) {
+            final AndroidPackage sharedPkg = packageManagerInternal
+                    .getPackage(sharedPkgName);
+            if (sharedPkg != null) {
+                synchroniser.addPackage(sharedPkg.getPackageName());
+            }
+        }
+        synchroniser.syncPackages();
     }
 
     /**
@@ -367,8 +381,8 @@
         final PermissionToOpSynchroniser synchronizer = new PermissionToOpSynchroniser(
                 getUserContext(getContext(), UserHandle.of(userId)));
         packageManagerInternal.forEachPackage(
-                (pkg) -> synchronizer.addUid(pkg.getUid()));
-        synchronizer.syncUids();
+                (pkg) -> synchronizer.addPackage(pkg.getPackageName()));
+        synchronizer.syncPackages();
     }
 
     /**
@@ -383,51 +397,37 @@
 
         private final @NonNull ArrayMap<String, PermissionInfo> mRuntimePermissionInfos;
 
-        // Cache uid -> packageNames
-        private SparseArray<String[]> mUidToPkg = new SparseArray<>();
-
         /**
          * All ops that need to be flipped to allow.
          *
-         * @see #syncUids
+         * @see #syncPackages
          */
-        private final @NonNull ArraySet<OpToChange> mOpsToAllow = new ArraySet<>();
+        private final @NonNull ArrayList<OpToChange> mOpsToAllow = new ArrayList<>();
 
         /**
          * All ops that need to be flipped to ignore.
          *
-         * @see #syncUids
+         * @see #syncPackages
          */
-        private final @NonNull ArraySet<OpToChange> mOpsToIgnore = new ArraySet<>();
+        private final @NonNull ArrayList<OpToChange> mOpsToIgnore = new ArrayList<>();
 
         /**
          * All ops that need to be flipped to ignore if not allowed.
          *
          * Currently, only used by soft restricted permissions logic.
          *
-         * @see #syncUids
+         * @see #syncPackages
          */
-        private final @NonNull ArraySet<OpToChange> mOpsToIgnoreIfNotAllowed = new ArraySet<>();
+        private final @NonNull ArrayList<OpToChange> mOpsToIgnoreIfNotAllowed = new ArrayList<>();
 
         /**
          * All ops that need to be flipped to foreground.
          *
          * Currently, only used by the foreground/background permissions logic.
          *
-         * @see #syncUids
+         * @see #syncPackages
          */
-        private final @NonNull ArraySet<OpToChange> mOpsToForeground = new ArraySet<>();
-
-        private @Nullable String[] getPackageNamesForUid(int uid) {
-            String[] pkgs = mUidToPkg.get(uid);
-            if (pkgs != null) {
-                return pkgs;
-            }
-
-            pkgs = mPackageManager.getPackagesForUid(uid);
-            mUidToPkg.put(uid, pkgs);
-            return pkgs;
-        }
+        private final @NonNull ArrayList<OpToChange> mOpsToForeground = new ArrayList<>();
 
         PermissionToOpSynchroniser(@NonNull Context context) {
             mContext = context;
@@ -449,11 +449,11 @@
         }
 
         /**
-         * Set app ops that were added in {@link #addUid}.
+         * Set app ops that were added in {@link #addPackage}.
          *
          * <p>This processes ops previously added by {@link #addAppOps(PackageInfo, String)}
          */
-        private void syncUids() {
+        private void syncPackages() {
             // Remember which ops were already set. This makes sure that we always set the most
             // permissive mode if two OpChanges are scheduled. This can e.g. happen if two
             // permissions change the same op. See {@link #getSwitchOp}.
@@ -461,42 +461,42 @@
 
             final int allowCount = mOpsToAllow.size();
             for (int i = 0; i < allowCount; i++) {
-                final OpToChange op = mOpsToAllow.valueAt(i);
+                final OpToChange op = mOpsToAllow.get(i);
 
-                setUidModeAllowed(op.code, op.uid);
+                setUidModeAllowed(op.code, op.uid, op.packageName);
                 alreadySetAppOps.put(IntPair.of(op.uid, op.code), 1);
             }
 
             final int foregroundCount = mOpsToForeground.size();
             for (int i = 0; i < foregroundCount; i++) {
-                final OpToChange op = mOpsToForeground.valueAt(i);
+                final OpToChange op = mOpsToForeground.get(i);
                 if (alreadySetAppOps.indexOfKey(IntPair.of(op.uid, op.code)) >= 0) {
                     continue;
                 }
 
-                setUidModeForeground(op.code, op.uid);
+                setUidModeForeground(op.code, op.uid, op.packageName);
                 alreadySetAppOps.put(IntPair.of(op.uid, op.code), 1);
             }
 
             final int ignoreCount = mOpsToIgnore.size();
             for (int i = 0; i < ignoreCount; i++) {
-                final OpToChange op = mOpsToIgnore.valueAt(i);
+                final OpToChange op = mOpsToIgnore.get(i);
                 if (alreadySetAppOps.indexOfKey(IntPair.of(op.uid, op.code)) >= 0) {
                     continue;
                 }
 
-                setUidModeIgnored(op.code, op.uid);
+                setUidModeIgnored(op.code, op.uid, op.packageName);
                 alreadySetAppOps.put(IntPair.of(op.uid, op.code), 1);
             }
 
             final int ignoreIfNotAllowedCount = mOpsToIgnoreIfNotAllowed.size();
             for (int i = 0; i < ignoreIfNotAllowedCount; i++) {
-                final OpToChange op = mOpsToIgnoreIfNotAllowed.valueAt(i);
+                final OpToChange op = mOpsToIgnoreIfNotAllowed.get(i);
                 if (alreadySetAppOps.indexOfKey(IntPair.of(op.uid, op.code)) >= 0) {
                     continue;
                 }
 
-                boolean wasSet = setUidModeIgnoredIfNotAllowed(op.code, op.uid);
+                boolean wasSet = setUidModeIgnoredIfNotAllowed(op.code, op.uid, op.packageName);
                 if (wasSet) {
                     alreadySetAppOps.put(IntPair.of(op.uid, op.code), 1);
                 }
@@ -555,7 +555,7 @@
             }
 
             int uid = packageInfo.applicationInfo.uid;
-            OpToChange opToChange = new OpToChange(uid, appOpCode);
+            OpToChange opToChange = new OpToChange(uid, packageName, appOpCode);
             switch (appOpMode) {
                 case MODE_ALLOWED:
                     mOpsToAllow.add(opToChange);
@@ -618,7 +618,8 @@
             }
 
             int uid = packageInfo.applicationInfo.uid;
-            OpToChange extraOpToChange = new OpToChange(uid, extraOpCode);
+            String packageName = packageInfo.packageName;
+            OpToChange extraOpToChange = new OpToChange(uid, packageName, extraOpCode);
             if (policy.mayAllowExtraAppOp()) {
                 mOpsToAllow.add(extraOpToChange);
             } else {
@@ -631,56 +632,45 @@
         }
 
         /**
-         * Add a Uid for {@link #syncUids() processing} later.
+         * Add a package for {@link #syncPackages() processing} later.
          *
          * <p>Note: Called with the package lock held. Do <u>not</u> call into app-op manager.
          *
-         * @param uid The uid to add for later processing.
+         * @param pkgName The package to add for later processing.
          */
-        void addUid(int uid) {
-            String[] pkgNames = getPackageNamesForUid(uid);
-            if (pkgNames == null) {
+        void addPackage(@NonNull String pkgName) {
+            final PackageInfo pkg;
+            try {
+                pkg = mPackageManager.getPackageInfo(pkgName, GET_PERMISSIONS);
+            } catch (NameNotFoundException e) {
                 return;
             }
 
-            for (String pkgName : pkgNames) {
-                final PackageInfo pkg;
-                try {
-                    pkg = mPackageManager.getPackageInfo(pkgName, GET_PERMISSIONS);
-                } catch (NameNotFoundException e) {
-                    continue;
-                }
+            if (pkg.requestedPermissions == null) {
+                return;
+            }
 
-                if (pkg.requestedPermissions == null) {
-                    continue;
-                }
-
-                for (String permission : pkg.requestedPermissions) {
-                    addAppOps(pkg, permission);
-                }
+            for (String permission : pkg.requestedPermissions) {
+                addAppOps(pkg, permission);
             }
         }
 
-        private void setUidModeAllowed(int opCode, int uid) {
-            setUidMode(opCode, uid, MODE_ALLOWED);
+        private void setUidModeAllowed(int opCode, int uid, @NonNull String packageName) {
+            setUidMode(opCode, uid, MODE_ALLOWED, packageName);
         }
 
-        private void setUidModeForeground(int opCode, int uid) {
-            setUidMode(opCode, uid, MODE_FOREGROUND);
+        private void setUidModeForeground(int opCode, int uid, @NonNull String packageName) {
+            setUidMode(opCode, uid, MODE_FOREGROUND, packageName);
         }
 
-        private void setUidModeIgnored(int opCode, int uid) {
-            setUidMode(opCode, uid, MODE_IGNORED);
+        private void setUidModeIgnored(int opCode, int uid, @NonNull String packageName) {
+            setUidMode(opCode, uid, MODE_IGNORED, packageName);
         }
 
-        private boolean setUidModeIgnoredIfNotAllowed(int opCode, int uid) {
-            String[] pkgsOfUid = getPackageNamesForUid(uid);
-            if (ArrayUtils.isEmpty(pkgsOfUid)) {
-                return false;
-            }
-
+        private boolean setUidModeIgnoredIfNotAllowed(int opCode, int uid,
+                @NonNull String packageName) {
             final int currentMode = mAppOpsManager.unsafeCheckOpRaw(AppOpsManager.opToPublicName(
-                    opCode), uid, pkgsOfUid[0]);
+                    opCode), uid, packageName);
             if (currentMode != MODE_ALLOWED) {
                 if (currentMode != MODE_IGNORED) {
                     mAppOpsManagerInternal.setUidModeFromPermissionPolicy(opCode, uid, MODE_IGNORED,
@@ -691,24 +681,20 @@
             return false;
         }
 
-        private void setUidMode(int opCode, int uid, int mode) {
-            String[] pkgsOfUid = getPackageNamesForUid(uid);
-            if (ArrayUtils.isEmpty(pkgsOfUid)) {
-                return;
-            }
-
+        private void setUidMode(int opCode, int uid, int mode,
+                @NonNull String packageName) {
             final int oldMode = mAppOpsManager.unsafeCheckOpRaw(AppOpsManager.opToPublicName(
-                    opCode), uid, pkgsOfUid[0]);
+                    opCode), uid, packageName);
             if (oldMode != mode) {
                 mAppOpsManagerInternal.setUidModeFromPermissionPolicy(opCode, uid, mode,
                         mAppOpsCallback);
                 final int newMode = mAppOpsManager.unsafeCheckOpRaw(AppOpsManager.opToPublicName(
-                        opCode), uid, pkgsOfUid[0]);
+                        opCode), uid, packageName);
                 if (newMode != mode) {
                     // Work around incorrectly-set package mode. It never makes sense for app ops
                     // related to runtime permissions, but can get in the way and we have to reset
                     // it.
-                    mAppOpsManagerInternal.setModeFromPermissionPolicy(opCode, uid, pkgsOfUid[0],
+                    mAppOpsManagerInternal.setModeFromPermissionPolicy(opCode, uid, packageName,
                             AppOpsManager.opToDefaultMode(opCode), mAppOpsCallback);
                 }
             }
@@ -716,30 +702,14 @@
 
         private class OpToChange {
             final int uid;
+            final @NonNull String packageName;
             final int code;
 
-            OpToChange(int uid, int code) {
+            OpToChange(int uid, @NonNull String packageName, int code) {
                 this.uid = uid;
+                this.packageName = packageName;
                 this.code = code;
             }
-
-            @Override
-            public boolean equals(Object o) {
-                if (this == o) {
-                    return true;
-                }
-                if (o == null || getClass() != o.getClass()) {
-                    return false;
-                }
-
-                OpToChange other = (OpToChange) o;
-                return uid == other.uid && code == other.code;
-            }
-
-            @Override
-            public int hashCode() {
-                return Objects.hash(uid, code);
-            }
         }
     }