diff --git a/core/res/AndroidManifest.xml b/core/res/AndroidManifest.xml
index eda6cd0..a3fccd9 100644
--- a/core/res/AndroidManifest.xml
+++ b/core/res/AndroidManifest.xml
@@ -4986,6 +4986,7 @@
         <service
                 android:name="com.android.server.autofill.AutofillCompatAccessibilityService"
                 android:permission="android.permission.BIND_ACCESSIBILITY_SERVICE"
+                android:visibleToInstantApps="true"
                 android:exported="true">
             <meta-data
                     android:name="android.accessibilityservice"
diff --git a/services/core/java/com/android/server/policy/SoftRestrictedPermissionPolicy.java b/services/core/java/com/android/server/policy/SoftRestrictedPermissionPolicy.java
index d53f685..c1a6dbd 100644
--- a/services/core/java/com/android/server/policy/SoftRestrictedPermissionPolicy.java
+++ b/services/core/java/com/android/server/policy/SoftRestrictedPermissionPolicy.java
@@ -28,11 +28,14 @@
 import static android.content.pm.PackageManager.FLAG_PERMISSION_RESTRICTION_SYSTEM_EXEMPT;
 import static android.content.pm.PackageManager.FLAG_PERMISSION_RESTRICTION_UPGRADE_EXEMPT;
 
+import static java.lang.Integer.min;
+
 import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.app.AppOpsManager;
 import android.content.Context;
 import android.content.pm.ApplicationInfo;
+import android.content.pm.PackageManager;
 import android.os.Build;
 import android.os.UserHandle;
 
@@ -73,6 +76,41 @@
             };
 
     /**
+     * TargetSDK is per package. To make sure two apps int the same shared UID do not fight over
+     * what to set, always compute the combined targetSDK.
+     *
+     * @param context A context
+     * @param appInfo The app that is changed
+     * @param user The user the app belongs to
+     *
+     * @return The minimum targetSDK of all apps sharing the uid of the app
+     */
+    private static int getMinimumTargetSDK(@NonNull Context context,
+            @NonNull ApplicationInfo appInfo, @NonNull UserHandle user) {
+        PackageManager pm = context.getPackageManager();
+
+        int minimumTargetSDK = appInfo.targetSdkVersion;
+
+        String[] uidPkgs = pm.getPackagesForUid(appInfo.uid);
+        if (uidPkgs != null) {
+            for (String uidPkg : uidPkgs) {
+                if (!uidPkg.equals(appInfo.packageName)) {
+                    ApplicationInfo uidPkgInfo;
+                    try {
+                        uidPkgInfo = pm.getApplicationInfoAsUser(uidPkg, 0, user);
+                    } catch (PackageManager.NameNotFoundException e) {
+                        continue;
+                    }
+
+                    minimumTargetSDK = min(minimumTargetSDK, uidPkgInfo.targetSdkVersion);
+                }
+            }
+        }
+
+        return minimumTargetSDK;
+    }
+
+    /**
      * Get the policy for a soft restricted permission.
      *
      * @param context A context to use
@@ -99,12 +137,36 @@
                 final int targetSDK;
 
                 if (appInfo != null) {
-                    flags = context.getPackageManager().getPermissionFlags(permission,
-                            appInfo.packageName, user);
+                    PackageManager pm = context.getPackageManager();
+                    flags = pm.getPermissionFlags(permission, appInfo.packageName, user);
                     applyRestriction = (flags & FLAG_PERMISSION_APPLY_RESTRICTION) != 0;
                     isWhiteListed = (flags & FLAGS_PERMISSION_RESTRICTION_ANY_EXEMPT) != 0;
-                    hasRequestedLegacyExternalStorage = appInfo.hasRequestedLegacyExternalStorage();
-                    targetSDK = appInfo.targetSdkVersion;
+                    targetSDK = getMinimumTargetSDK(context, appInfo, user);
+
+                    boolean hasAnyRequestedLegacyExternalStorage =
+                            appInfo.hasRequestedLegacyExternalStorage();
+
+                    // hasRequestedLegacyExternalStorage is per package. To make sure two apps in
+                    // the same shared UID do not fight over what to set, always compute the
+                    // combined hasRequestedLegacyExternalStorage
+                    String[] uidPkgs = pm.getPackagesForUid(appInfo.uid);
+                    if (uidPkgs != null) {
+                        for (String uidPkg : uidPkgs) {
+                            if (!uidPkg.equals(appInfo.packageName)) {
+                                ApplicationInfo uidPkgInfo;
+                                try {
+                                    uidPkgInfo = pm.getApplicationInfoAsUser(uidPkg, 0, user);
+                                } catch (PackageManager.NameNotFoundException e) {
+                                    continue;
+                                }
+
+                                hasAnyRequestedLegacyExternalStorage |=
+                                        uidPkgInfo.hasRequestedLegacyExternalStorage();
+                            }
+                        }
+                    }
+
+                    hasRequestedLegacyExternalStorage = hasAnyRequestedLegacyExternalStorage;
                 } else {
                     flags = 0;
                     applyRestriction = false;
@@ -155,7 +217,7 @@
                     final int flags = context.getPackageManager().getPermissionFlags(permission,
                             appInfo.packageName, user);
                     isWhiteListed = (flags & FLAGS_PERMISSION_RESTRICTION_ANY_EXEMPT) != 0;
-                    targetSDK = appInfo.targetSdkVersion;
+                    targetSDK = getMinimumTargetSDK(context, appInfo, user);
                 } else {
                     isWhiteListed = false;
                     targetSDK = 0;
diff --git a/services/core/java/com/android/server/policy/TEST_MAPPING b/services/core/java/com/android/server/policy/TEST_MAPPING
index c7e241b..17392e0 100644
--- a/services/core/java/com/android/server/policy/TEST_MAPPING
+++ b/services/core/java/com/android/server/policy/TEST_MAPPING
@@ -33,6 +33,9 @@
       "options": [
         {
           "include-filter": "android.permission2.cts.RestrictedPermissionsTest"
+        },
+        {
+          "include-filter": "android.permission2.cts.RestrictedStoragePermissionSharedUidTest"
         }
       ]
     },