diff --git a/service/java/com/android/server/appsearch/AppSearchManagerService.java b/service/java/com/android/server/appsearch/AppSearchManagerService.java
index 0c07fa0..0709ff5 100644
--- a/service/java/com/android/server/appsearch/AppSearchManagerService.java
+++ b/service/java/com/android/server/appsearch/AppSearchManagerService.java
@@ -17,11 +17,10 @@
 
 import static android.app.appsearch.AppSearchResult.throwableToFailedResult;
 import static android.os.Process.INVALID_UID;
-import static android.os.UserHandle.USER_NULL;
 
+import android.Manifest;
 import android.annotation.ElapsedRealtimeLong;
 import android.annotation.NonNull;
-import android.app.ActivityManager;
 import android.app.appsearch.AppSearchBatchResult;
 import android.app.appsearch.AppSearchMigrationHelper;
 import android.app.appsearch.AppSearchResult;
@@ -63,6 +62,7 @@
 import com.android.server.appsearch.external.localstorage.stats.CallStats;
 import com.android.server.appsearch.stats.LoggerInstanceManager;
 import com.android.server.appsearch.stats.PlatformLogger;
+import com.android.server.appsearch.util.PackageUtil;
 import com.android.server.usage.StorageStatsManagerLocal;
 import com.android.server.usage.StorageStatsManagerLocal.StorageStatsAugmenter;
 
@@ -124,8 +124,10 @@
     }
 
     private void registerReceivers() {
-        mContext.registerReceiverAsUser(new UserActionReceiver(), UserHandle.ALL,
-                new IntentFilter(Intent.ACTION_USER_REMOVED), /*broadcastPermission=*/ null,
+        mContext.registerReceiverForAllUsers(
+                new UserActionReceiver(),
+                new IntentFilter(Intent.ACTION_USER_REMOVED),
+                /*broadcastPermission=*/ null,
                 /*scheduler=*/ null);
 
         //TODO(b/145759910) Add a direct callback when user clears the data instead of relying on
@@ -135,8 +137,10 @@
         packageChangedFilter.addAction(Intent.ACTION_PACKAGE_DATA_CLEARED);
         packageChangedFilter.addDataScheme("package");
         packageChangedFilter.setPriority(IntentFilter.SYSTEM_HIGH_PRIORITY);
-        mContext.registerReceiverAsUser(new PackageChangedReceiver(), UserHandle.ALL,
-                packageChangedFilter, /*broadcastPermission=*/ null,
+        mContext.registerReceiverForAllUsers(
+                new PackageChangedReceiver(),
+                packageChangedFilter,
+                /*broadcastPermission=*/ null,
                 /*scheduler=*/ null);
     }
 
@@ -148,12 +152,13 @@
 
             switch (intent.getAction()) {
                 case Intent.ACTION_USER_REMOVED:
-                    int userId = intent.getIntExtra(Intent.EXTRA_USER_HANDLE, USER_NULL);
-                    if (userId == USER_NULL) {
-                        Log.e(TAG, "userId is missing in the intent: " + intent);
+                    UserHandle userHandle = intent.getParcelableExtra(Intent.EXTRA_USER);
+                    if (userHandle == null) {
+                        Log.e(TAG, "Extra "
+                                + Intent.EXTRA_USER + " is missing in the intent: " + intent);
                         return;
                     }
-                    handleUserRemoved(UserHandle.of(userId));
+                    handleUserRemoved(userHandle);
                     break;
                 default:
                     Log.e(TAG, "Received unknown intent: " + intent);
@@ -1183,13 +1188,9 @@
             Objects.requireNonNull(actualCallingUser);
             Objects.requireNonNull(claimedCallingPackage);
 
-            int claimedCallingUid;
-            try {
-                Context claimedCallingContext =
-                        mContext.createContextAsUser(actualCallingUser, /*flags=*/ 0);
-                claimedCallingUid = claimedCallingContext.getPackageManager().getPackageUid(
-                        claimedCallingPackage, /*flags=*/ 0);
-            } catch (PackageManager.NameNotFoundException e) {
+            int claimedCallingUid = PackageUtil.getPackageUidAsUser(
+                    mContext, claimedCallingPackage, actualCallingUser);
+            if (claimedCallingUid == INVALID_UID) {
                 throw new SecurityException(
                         "Specified calling package [" + claimedCallingPackage + "] not found");
             }
@@ -1257,23 +1258,44 @@
      *
      * <p>Takes care of checking permissions and converting USER_CURRENT to the actual current user.
      *
+     * @param requestedUser The user which the caller is requesting to execute as.
+     * @param callingUid The actual uid of the caller as determined by Binder.
      * @return the user handle that the call should run as. Will always be a concrete user.
      */
     // TODO(b/173553485) verifying that the caller has permission to access target user's data
     // TODO(b/173553485) Handle ACTION_USER_REMOVED broadcast
     // TODO(b/173553485) Implement SystemService.onUserStopping()
     @NonNull
-    private static UserHandle handleIncomingUser(@NonNull UserHandle userHandle, int callingUid) {
+    private UserHandle handleIncomingUser(@NonNull UserHandle requestedUser, int callingUid) {
         int callingPid = Binder.getCallingPid();
-        int finalUserId = ActivityManager.handleIncomingUser(
+        UserHandle callingUser = UserHandle.getUserHandleForUid(callingUid);
+        if (callingUser.equals(requestedUser)) {
+            return requestedUser;
+        }
+        // Duplicates UserController#ensureNotSpecialUser
+        if (requestedUser.getIdentifier() < 0) {
+            throw new IllegalArgumentException(
+                    "Call does not support special user " + requestedUser);
+        }
+        boolean canInteractAcrossUsers = mContext.checkPermission(
+                Manifest.permission.INTERACT_ACROSS_USERS,
                 callingPid,
-                callingUid,
-                userHandle.getIdentifier(),
-                /*allowAll=*/ false,
-                /*requireFull=*/ false,
-                /*name=*/ null,
-                /*callerPackage=*/ null);
-        return UserHandle.of(finalUserId);
+                callingUid) == PackageManager.PERMISSION_GRANTED;
+        if (!canInteractAcrossUsers) {
+            canInteractAcrossUsers = mContext.checkPermission(
+                    Manifest.permission.INTERACT_ACROSS_USERS_FULL,
+                    callingPid,
+                    callingUid) == PackageManager.PERMISSION_GRANTED;
+        }
+        if (canInteractAcrossUsers) {
+            return requestedUser;
+        }
+        throw new SecurityException(
+                "Permission denied while calling from uid " + callingUid
+                        + " with " + requestedUser + "; Need to run as either the calling user ("
+                        + callingUser + "), or with one of the following permissions: "
+                        + Manifest.permission.INTERACT_ACROSS_USERS + " or "
+                        + Manifest.permission.INTERACT_ACROSS_USERS_FULL);
     }
 
     // TODO(b/179160886): Cache the previous storage stats.
diff --git a/service/java/com/android/server/appsearch/ImplInstanceManager.java b/service/java/com/android/server/appsearch/ImplInstanceManager.java
index beb4d24..0775272 100644
--- a/service/java/com/android/server/appsearch/ImplInstanceManager.java
+++ b/service/java/com/android/server/appsearch/ImplInstanceManager.java
@@ -172,11 +172,6 @@
             @Nullable AppSearchLogger logger)
             throws AppSearchException {
         File appSearchDir = getAppSearchDir(userHandle);
-        // TODO(b/181787682): Swap AppSearchImpl and VisibilityStore to accept a UserHandle too
-        return AppSearchImpl.create(
-                appSearchDir,
-                userContext,
-                userHandle.getIdentifier(),
-                /*logger=*/ null);
+        return AppSearchImpl.create(appSearchDir, userContext, /*logger=*/ null);
     }
 }
diff --git a/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java b/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
index a940dde..29cb57c 100644
--- a/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
+++ b/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
@@ -201,7 +201,6 @@
     public static AppSearchImpl create(
             @NonNull File icingDir,
             @NonNull Context userContext,
-            int userId,
             @Nullable AppSearchLogger logger)
             throws AppSearchException {
         Objects.requireNonNull(icingDir);
@@ -213,8 +212,7 @@
             initStatsBuilder = new InitializeStats.Builder();
         }
 
-        AppSearchImpl appSearchImpl =
-                new AppSearchImpl(icingDir, userContext, userId, initStatsBuilder);
+        AppSearchImpl appSearchImpl = new AppSearchImpl(icingDir, userContext, initStatsBuilder);
 
         long prepareVisibilityStoreLatencyStartMillis = SystemClock.elapsedRealtime();
         appSearchImpl.initializeVisibilityStore();
@@ -238,7 +236,6 @@
     private AppSearchImpl(
             @NonNull File icingDir,
             @NonNull Context userContext,
-            int userId,
             @Nullable InitializeStats.Builder initStatsBuilder)
             throws AppSearchException {
         mReadWriteLock.writeLock().lock();
@@ -256,7 +253,7 @@
                     "Constructing IcingSearchEngine, response",
                     Objects.hashCode(mIcingSearchEngineLocked));
 
-            mVisibilityStoreLocked = new VisibilityStore(this, userContext, userId);
+            mVisibilityStoreLocked = new VisibilityStore(this, userContext);
 
             // The core initialization procedure. If any part of this fails, we bail into
             // resetLocked(), deleting all data (but hopefully allowing AppSearchImpl to come up).
diff --git a/service/java/com/android/server/appsearch/stats/PlatformLogger.java b/service/java/com/android/server/appsearch/stats/PlatformLogger.java
index 7d0ce41..c857fb6 100644
--- a/service/java/com/android/server/appsearch/stats/PlatformLogger.java
+++ b/service/java/com/android/server/appsearch/stats/PlatformLogger.java
@@ -20,7 +20,6 @@
 import android.annotation.Nullable;
 import android.app.appsearch.exceptions.AppSearchException;
 import android.content.Context;
-import android.content.pm.PackageManager;
 import android.os.Process;
 import android.os.SystemClock;
 import android.os.UserHandle;
@@ -36,6 +35,7 @@
 import com.android.server.appsearch.external.localstorage.stats.PutDocumentStats;
 import com.android.server.appsearch.external.localstorage.stats.RemoveStats;
 import com.android.server.appsearch.external.localstorage.stats.SearchStats;
+import com.android.server.appsearch.util.PackageUtil;
 
 import java.io.UnsupportedEncodingException;
 import java.security.MessageDigest;
@@ -493,21 +493,13 @@
     @GuardedBy("mLock")
     private int getPackageUidAsUserLocked(@NonNull String packageName) {
         Integer packageUid = mPackageUidCacheLocked.get(packageName);
-        if (packageUid != null) {
-            return packageUid;
+        if (packageUid == null) {
+            packageUid = PackageUtil.getPackageUidAsUser(mContext, packageName, mUserHandle);
+            if (packageUid != Process.INVALID_UID) {
+                mPackageUidCacheLocked.put(packageName, packageUid);
+            }
         }
-
-        // TODO(b/173532925) since VisibilityStore has the same method, we can make this a
-        //  utility function
-        try {
-            packageUid = mContext.getPackageManager().getPackageUidAsUser(
-                    packageName, mUserHandle.getIdentifier());
-            mPackageUidCacheLocked.put(packageName, packageUid);
-            return packageUid;
-        } catch (PackageManager.NameNotFoundException e) {
-            // Package doesn't exist, continue
-        }
-        return Process.INVALID_UID;
+        return packageUid;
     }
 
     //
diff --git a/service/java/com/android/server/appsearch/util/PackageUtil.java b/service/java/com/android/server/appsearch/util/PackageUtil.java
new file mode 100644
index 0000000..53a1bed
--- /dev/null
+++ b/service/java/com/android/server/appsearch/util/PackageUtil.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.appsearch.util;
+
+import android.annotation.NonNull;
+import android.content.Context;
+import android.content.pm.PackageManager;
+import android.os.Process;
+import android.os.UserHandle;
+
+/**
+ * Utilities for interacting with {@link android.content.pm.PackageManager},
+ * {@link android.os.UserHandle}, and other parts of dealing with apps and binder.
+ *
+ * @hide
+ */
+public class PackageUtil {
+    private PackageUtil() {}
+
+    /**
+     * Finds the UID of the {@code packageName}. Returns {@link Process#INVALID_UID} if unable to
+     * find the UID.
+     */
+    public static int getPackageUidAsUser(
+            @NonNull Context context, @NonNull String packageName, @NonNull UserHandle user) {
+        Context userContext = context.createContextAsUser(user, /*flags=*/ 0);
+        return getPackageUid(userContext, packageName);
+    }
+
+    /**
+     * Finds the UID of the {@code packageName} in the given {@code context}. Returns
+     * {@link Process#INVALID_UID} if unable to find the UID.
+     */
+    public static int getPackageUid(@NonNull Context context, @NonNull String packageName) {
+        try {
+            return context.getPackageManager().getPackageUid(packageName, /*flags=*/ 0);
+        } catch (PackageManager.NameNotFoundException e) {
+            return Process.INVALID_UID;
+        }
+    }
+}
diff --git a/service/java/com/android/server/appsearch/visibilitystore/VisibilityStore.java b/service/java/com/android/server/appsearch/visibilitystore/VisibilityStore.java
index acff792..95ed368 100644
--- a/service/java/com/android/server/appsearch/visibilitystore/VisibilityStore.java
+++ b/service/java/com/android/server/appsearch/visibilitystore/VisibilityStore.java
@@ -18,7 +18,6 @@
 import static android.Manifest.permission.READ_GLOBAL_APP_SEARCH_DATA;
 
 import android.annotation.NonNull;
-import android.annotation.UserIdInt;
 import android.app.appsearch.AppSearchResult;
 import android.app.appsearch.AppSearchSchema;
 import android.app.appsearch.GenericDocument;
@@ -27,7 +26,6 @@
 import android.app.appsearch.exceptions.AppSearchException;
 import android.content.Context;
 import android.content.pm.PackageManager;
-import android.os.Process;
 import android.os.UserHandle;
 import android.util.ArrayMap;
 import android.util.ArraySet;
@@ -35,6 +33,7 @@
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.server.appsearch.external.localstorage.AppSearchImpl;
 import com.android.server.appsearch.external.localstorage.util.PrefixUtil;
+import com.android.server.appsearch.util.PackageUtil;
 
 import com.google.android.icing.proto.PersistType;
 
@@ -67,9 +66,6 @@
  * @hide
  */
 public class VisibilityStore {
-
-    private static final String TAG = "AppSearchVisibilityStore";
-
     /** No-op user id that won't have any visibility settings. */
     public static final int NO_OP_USER_ID = -1;
 
@@ -95,9 +91,6 @@
     // Context of the user that the call is being made as.
     private final Context mUserContext;
 
-    // User ID of the caller who we're checking visibility settings for.
-    private final int mUserId;
-
     /** Stores the schemas that are platform-hidden. All values are prefixed. */
     private final NotPlatformSurfaceableMap mNotPlatformSurfaceableMap =
             new NotPlatformSurfaceableMap();
@@ -112,13 +105,9 @@
      * @param appSearchImpl AppSearchImpl instance
      * @param userContext Context of the user that the call is being made as
      */
-    public VisibilityStore(
-            @NonNull AppSearchImpl appSearchImpl,
-            @NonNull Context userContext,
-            @UserIdInt int userId) {
+    public VisibilityStore(@NonNull AppSearchImpl appSearchImpl, @NonNull Context userContext) {
         mAppSearchImpl = appSearchImpl;
-        mUserContext = userContext;
-        mUserId = userId;
+        mUserContext = Objects.requireNonNull(userContext);
     }
 
     /**
@@ -348,6 +337,9 @@
         Set<PackageIdentifier> packageIdentifiers =
                 mPackageAccessibleMap.getAccessiblePackages(
                         packageName, databaseName, prefixedSchema);
+        if (packageIdentifiers.isEmpty()) {
+            return false;
+        }
         for (PackageIdentifier packageIdentifier : packageIdentifiers) {
             // TODO(b/169883602): Consider caching the UIDs of packages. Looking this up in the
             // package manager could be costly. We would also need to update the cache on
@@ -357,9 +349,10 @@
             // the callerUid since clients can createContextAsUser with some other user, and then
             // make calls to us. So just check if the appId portion of the uid is the same. This is
             // essentially UserHandle.isSameApp, but that's not a system API for us to use.
-            int callerAppId = UserHandle.getAppId((callerUid));
-            int userAppId =
-                    UserHandle.getAppId(getPackageUidAsUser(packageIdentifier.getPackageName()));
+            int callerAppId = UserHandle.getAppId(callerUid);
+            int packageUid =
+                    PackageUtil.getPackageUid(mUserContext, packageIdentifier.getPackageName());
+            int userAppId = UserHandle.getAppId(packageUid);
             if (callerAppId != userAppId) {
                 continue;
             }
@@ -401,17 +394,4 @@
             @NonNull String packageName, @NonNull String databaseName) {
         return ID_PREFIX + PrefixUtil.createPrefix(packageName, databaseName);
     }
-
-    /**
-     * Finds the UID of the {@code packageName}. Returns {@link Process#INVALID_UID} if unable to
-     * find the UID.
-     */
-    private int getPackageUidAsUser(@NonNull String packageName) {
-        try {
-            return mUserContext.getPackageManager().getPackageUidAsUser(packageName, mUserId);
-        } catch (PackageManager.NameNotFoundException e) {
-            // Package doesn't exist, continue
-        }
-        return Process.INVALID_UID;
-    }
 }