diff --git a/proto/src/metrics_constants/metrics_constants.proto b/proto/src/metrics_constants/metrics_constants.proto
index 66d64b1..529d78f 100644
--- a/proto/src/metrics_constants/metrics_constants.proto
+++ b/proto/src/metrics_constants/metrics_constants.proto
@@ -6649,6 +6649,21 @@
     // OS: Q
     QS_SENSOR_PRIVACY = 1598;
 
+    // Tagged data for SMART_REPLY_VISIBLE. Count of number of smart actions.
+    // OS: Q
+    NOTIFICATION_SMART_ACTION_COUNT = 1599;
+
+    // Tagged data for SMART_REPLY_VISIBLE and NOTIFICATION_ITEM_ACTION.
+    // Whether the notification has notification-assistant generated
+    // actions/replies.
+    // OS: Q
+    NOTIFICATION_SMART_SUGGESTION_ASSISTANT_GENERATED = 1600;
+
+    // Tagged data for NOTIFICATION_ITEM_ACTION. Whether the action is a smart
+    // action.
+    // OS: Q
+    NOTIFICATION_ACTION_IS_SMART = 1601;
+
     // ---- End Q Constants, all Q constants go above this line ----
 
     // Add new aosp constants above this line.
diff --git a/services/backup/java/com/android/server/backup/BackupManagerService.java b/services/backup/java/com/android/server/backup/BackupManagerService.java
index 2cbab49..a533640 100644
--- a/services/backup/java/com/android/server/backup/BackupManagerService.java
+++ b/services/backup/java/com/android/server/backup/BackupManagerService.java
@@ -16,10 +16,13 @@
 
 package com.android.server.backup;
 
+import static com.android.internal.util.Preconditions.checkNotNull;
+
 import android.Manifest;
 import android.annotation.Nullable;
 import android.annotation.UserIdInt;
 import android.app.ActivityManager;
+import android.app.backup.BackupManager;
 import android.app.backup.IBackupManagerMonitor;
 import android.app.backup.IBackupObserver;
 import android.app.backup.IFullBackupRestoreObserver;
@@ -41,6 +44,7 @@
 import android.os.Trace;
 import android.os.UserHandle;
 import android.util.Slog;
+import android.util.SparseArray;
 
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.server.SystemConfig;
@@ -83,22 +87,27 @@
     }
 
     private final Context mContext;
-    private UserBackupManagerService mUserBackupManagerService;
+    private final Trampoline mTrampoline;
+    private final HandlerThread mBackupThread;
+
+    // Keeps track of all unlocked users registered with this service. Indexed by user id.
+    private final SparseArray<UserBackupManagerService> mServiceUsers = new SparseArray<>();
+
+    private Set<ComponentName> mTransportWhitelist;
 
     /** Instantiate a new instance of {@link BackupManagerService}. */
     public BackupManagerService(
             Context context, Trampoline trampoline, HandlerThread backupThread) {
-        // Set up our transport options and initialize the default transport
-        SystemConfig systemConfig = SystemConfig.getInstance();
-        Set<ComponentName> transportWhitelist = systemConfig.getBackupTransportWhitelist();
-        if (transportWhitelist == null) {
-            transportWhitelist = Collections.emptySet();
-        }
+        mContext = checkNotNull(context);
+        mTrampoline = checkNotNull(trampoline);
+        mBackupThread = checkNotNull(backupThread);
 
-        mContext = context;
-        mUserBackupManagerService =
-                UserBackupManagerService.createAndInitializeService(
-                        context, trampoline, backupThread, transportWhitelist);
+        // Set up our transport options.
+        SystemConfig systemConfig = SystemConfig.getInstance();
+        mTransportWhitelist = systemConfig.getBackupTransportWhitelist();
+        if (mTransportWhitelist == null) {
+            mTransportWhitelist = Collections.emptySet();
+        }
     }
 
     /**
@@ -115,12 +124,6 @@
         }
     }
 
-    // TODO(b/118520567): Remove when tests are modified to use per-user instance.
-    @VisibleForTesting
-    void setUserBackupManagerService(UserBackupManagerService userBackupManagerService) {
-        mUserBackupManagerService = userBackupManagerService;
-    }
-
     /**
      * Called through Trampoline from {@link Lifecycle#onUnlockUser(int)}. We run the heavy work on
      * a background thread to keep the unlock time down.
@@ -139,9 +142,42 @@
      * Starts the backup service for user {@code userId} by creating a new instance of {@link
      * UserBackupManagerService} and registering it with this service.
      */
-    // TODO(b/120212806): Add UserBackupManagerService initialization logic.
-    void startServiceForUser(int userId) {
-        // Intentionally empty.
+    @VisibleForTesting
+    protected void startServiceForUser(int userId) {
+        UserBackupManagerService userBackupManagerService =
+                UserBackupManagerService.createAndInitializeService(
+                        mContext, mTrampoline, mBackupThread, mTransportWhitelist);
+        startServiceForUser(userId, userBackupManagerService);
+    }
+
+    /**
+     * Starts the backup service for user {@code userId} by registering its instance of {@link
+     * UserBackupManagerService} with this service.
+     */
+    void startServiceForUser(int userId, UserBackupManagerService userBackupManagerService) {
+        mServiceUsers.put(userId, userBackupManagerService);
+    }
+
+    SparseArray<UserBackupManagerService> getServiceUsers() {
+        return mServiceUsers;
+    }
+
+    /**
+     * Returns the {@link UserBackupManagerService} instance for the specified user {@code userId}.
+     * If the user is not registered with the service (either the user is locked or not eligible for
+     * the backup service) then return {@code null}.
+     *
+     * @param userId The id of the user to retrieve its instance of {@link
+     *     UserBackupManagerService}.
+     * @param caller A {@link String} identifying the caller for logging purposes.
+     */
+    @Nullable
+    private UserBackupManagerService getServiceForUser(@UserIdInt int userId, String caller) {
+        UserBackupManagerService userBackupManagerService = mServiceUsers.get(userId);
+        if (userBackupManagerService == null) {
+            Slog.w(TAG, "Called " + caller + " for unknown user: " + userId);
+        }
+        return userBackupManagerService;
     }
 
     /*
@@ -149,7 +185,7 @@
      * They delegate to the appropriate per-user instance of UserBackupManagerService to perform the
      * action on the passed in user. Currently this is a straight redirection (see TODO).
      */
-    // TODO (b/118520567): Take in user id and call per-user instance of UserBackupManagerService.
+    // TODO (b/118520567): Stop hardcoding system user when we pass in user id as a parameter
 
     // ---------------------------------------------
     // BACKUP AGENT OPERATIONS
@@ -161,7 +197,12 @@
      * backup.
      */
     public void dataChanged(String packageName) {
-        mUserBackupManagerService.dataChanged(packageName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "dataChanged()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.dataChanged(packageName);
+        }
     }
 
     /**
@@ -169,7 +210,12 @@
      * {@link ActivityManager}.
      */
     public void agentConnected(String packageName, IBinder agentBinder) {
-        mUserBackupManagerService.agentConnected(packageName, agentBinder);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "agentConnected()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.agentConnected(packageName, agentBinder);
+        }
     }
 
     /**
@@ -177,7 +223,12 @@
      * called from the {@link ActivityManager}.
      */
     public void agentDisconnected(String packageName) {
-        mUserBackupManagerService.agentDisconnected(packageName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "agentDisconnected()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.agentDisconnected(packageName);
+        }
     }
 
     /**
@@ -185,7 +236,12 @@
      * outstanding asynchronous backup/restore operation.
      */
     public void opComplete(int token, long result) {
-        mUserBackupManagerService.opComplete(token, result);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "opComplete()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.opComplete(token, result);
+        }
     }
 
     // ---------------------------------------------
@@ -194,7 +250,12 @@
 
     /** Run an initialize operation for the given transports {@code transportNames}. */
     public void initializeTransports(String[] transportNames, IBackupObserver observer) {
-        mUserBackupManagerService.initializeTransports(transportNames, observer);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "initializeTransports()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.initializeTransports(transportNames, observer);
+        }
     }
 
     /**
@@ -202,35 +263,70 @@
      * transportName}.
      */
     public void clearBackupData(String transportName, String packageName) {
-        mUserBackupManagerService.clearBackupData(transportName, packageName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "clearBackupData()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.clearBackupData(transportName, packageName);
+        }
     }
 
     /** Return the name of the currently active transport. */
+    @Nullable
     public String getCurrentTransport() {
-        return mUserBackupManagerService.getCurrentTransport();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getCurrentTransport()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getCurrentTransport();
     }
 
     /**
      * Returns the {@link ComponentName} of the host service of the selected transport or {@code
      * null} if no transport selected or if the transport selected is not registered.
      */
+    @Nullable
     public ComponentName getCurrentTransportComponent() {
-        return mUserBackupManagerService.getCurrentTransportComponent();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getCurrentTransportComponent()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getCurrentTransportComponent();
     }
 
     /** Report all known, available backup transports by name. */
+    @Nullable
     public String[] listAllTransports() {
-        return mUserBackupManagerService.listAllTransports();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "listAllTransports()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.listAllTransports();
     }
 
     /** Report all known, available backup transports by {@link ComponentName}. */
+    @Nullable
     public ComponentName[] listAllTransportComponents() {
-        return mUserBackupManagerService.listAllTransportComponents();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "listAllTransportComponents()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.listAllTransportComponents();
     }
 
     /** Report all system whitelisted transports. */
+    @Nullable
     public String[] getTransportWhitelist() {
-        return mUserBackupManagerService.getTransportWhitelist();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getTransportWhitelist()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getTransportWhitelist();
     }
 
     /**
@@ -263,13 +359,18 @@
             String currentDestinationString,
             @Nullable Intent dataManagementIntent,
             String dataManagementLabel) {
-        mUserBackupManagerService.updateTransportAttributes(
-                transportComponent,
-                name,
-                configurationIntent,
-                currentDestinationString,
-                dataManagementIntent,
-                dataManagementLabel);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "updateTransportAttributes()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.updateTransportAttributes(
+                    transportComponent,
+                    name,
+                    configurationIntent,
+                    currentDestinationString,
+                    dataManagementIntent,
+                    dataManagementLabel);
+        }
     }
 
     /**
@@ -281,7 +382,12 @@
     @Deprecated
     @Nullable
     public String selectBackupTransport(String transportName) {
-        return mUserBackupManagerService.selectBackupTransport(transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "selectBackupTransport()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.selectBackupTransport(transportName);
     }
 
     /**
@@ -290,7 +396,12 @@
      */
     public void selectBackupTransportAsync(
             ComponentName transportComponent, ISelectBackupTransportCallback listener) {
-        mUserBackupManagerService.selectBackupTransportAsync(transportComponent, listener);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "selectBackupTransportAsync()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.selectBackupTransportAsync(transportComponent, listener);
+        }
     }
 
     /**
@@ -298,8 +409,14 @@
      * available transports, or if the transport does not supply any configuration UI, the method
      * returns {@code null}.
      */
+    @Nullable
     public Intent getConfigurationIntent(String transportName) {
-        return mUserBackupManagerService.getConfigurationIntent(transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getConfigurationIntent()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getConfigurationIntent(transportName);
     }
 
     /**
@@ -311,21 +428,39 @@
      * @param transportName The name of the registered transport.
      * @return The current destination string or null if the transport is not registered.
      */
+    @Nullable
     public String getDestinationString(String transportName) {
-        return mUserBackupManagerService.getDestinationString(transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getDestinationString()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getDestinationString(transportName);
     }
 
     /** Supply the manage-data intent for the given transport. */
+    @Nullable
     public Intent getDataManagementIntent(String transportName) {
-        return mUserBackupManagerService.getDataManagementIntent(transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getDataManagementIntent()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getDataManagementIntent(transportName);
     }
 
     /**
      * Supply the menu label for affordances that fire the manage-data intent for the given
      * transport.
      */
+    @Nullable
     public String getDataManagementLabel(String transportName) {
-        return mUserBackupManagerService.getDataManagementLabel(transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getDataManagementLabel()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.getDataManagementLabel(transportName);
     }
 
     // ---------------------------------------------
@@ -335,17 +470,32 @@
     /** Enable/disable the backup service. This is user-configurable via backup settings. */
     public void setBackupEnabled(@UserIdInt int userId, boolean enable) {
         enforceCallingPermissionOnUserId(userId, "setBackupEnabled");
-        mUserBackupManagerService.setBackupEnabled(enable);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "setBackupEnabled()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.setBackupEnabled(enable);
+        }
     }
 
     /** Enable/disable automatic restore of app data at install time. */
     public void setAutoRestore(boolean autoRestore) {
-        mUserBackupManagerService.setAutoRestore(autoRestore);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "setAutoRestore()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.setAutoRestore(autoRestore);
+        }
     }
 
     /** Mark the backup service as having been provisioned (device has gone through SUW). */
     public void setBackupProvisioned(boolean provisioned) {
-        mUserBackupManagerService.setBackupProvisioned(provisioned);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "setBackupProvisioned()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.setBackupProvisioned(provisioned);
+        }
     }
 
     /**
@@ -353,7 +503,10 @@
      */
     public boolean isBackupEnabled(@UserIdInt int userId) {
         enforceCallingPermissionOnUserId(userId, "isBackupEnabled");
-        return mUserBackupManagerService.isBackupEnabled();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "isBackupEnabled()");
+
+        return userBackupManagerService != null && userBackupManagerService.isBackupEnabled();
     }
 
     // ---------------------------------------------
@@ -362,14 +515,24 @@
 
     /** Checks if the given package {@code packageName} is eligible for backup. */
     public boolean isAppEligibleForBackup(String packageName) {
-        return mUserBackupManagerService.isAppEligibleForBackup(packageName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "isAppEligibleForBackup()");
+
+        return userBackupManagerService != null
+                && userBackupManagerService.isAppEligibleForBackup(packageName);
     }
 
     /**
      * Returns from the inputted packages {@code packages}, the ones that are eligible for backup.
      */
+    @Nullable
     public String[] filterAppsEligibleForBackup(String[] packages) {
-        return mUserBackupManagerService.filterAppsEligibleForBackup(packages);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "filterAppsEligibleForBackup()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.filterAppsEligibleForBackup(packages);
     }
 
     /**
@@ -378,7 +541,12 @@
      */
     public void backupNow(@UserIdInt int userId) {
         enforceCallingPermissionOnUserId(userId, "backupNow");
-        mUserBackupManagerService.backupNow();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "backupNow()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.backupNow();
+        }
     }
 
     /**
@@ -392,13 +560,23 @@
             IBackupManagerMonitor monitor,
             int flags) {
         enforceCallingPermissionOnUserId(userId, "requestBackup");
-        return mUserBackupManagerService.requestBackup(packages, observer, monitor, flags);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "requestBackup()");
+
+        return userBackupManagerService == null
+                ? BackupManager.ERROR_BACKUP_NOT_ALLOWED
+                : userBackupManagerService.requestBackup(packages, observer, monitor, flags);
     }
 
     /** Cancel all running backup operations. */
     public void cancelBackups(@UserIdInt int userId) {
         enforceCallingPermissionOnUserId(userId, "cancelBackups");
-        mUserBackupManagerService.cancelBackups();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "cancelBackups()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.cancelBackups();
+        }
     }
 
     /**
@@ -410,7 +588,11 @@
      *     return value to the callback {@link JobService#onStartJob(JobParameters)}.
      */
     public boolean beginFullBackup(FullBackupJob scheduledJob) {
-        return mUserBackupManagerService.beginFullBackup(scheduledJob);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "beginFullBackup()");
+
+        return userBackupManagerService != null
+                && userBackupManagerService.beginFullBackup(scheduledJob);
     }
 
     /**
@@ -418,14 +600,24 @@
      * longer met for running the full backup job.
      */
     public void endFullBackup() {
-        mUserBackupManagerService.endFullBackup();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "endFullBackup()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.endFullBackup();
+        }
     }
 
     /**
      * Run a full backup pass for the given packages {@code packageNames}. Used by 'adb shell bmgr'.
      */
     public void fullTransportBackup(String[] packageNames) {
-        mUserBackupManagerService.fullTransportBackup(packageNames);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "fullTransportBackup()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.fullTransportBackup(packageNames);
+        }
     }
 
     // ---------------------------------------------
@@ -437,15 +629,26 @@
      * called from the {@link PackageManager}.
      */
     public void restoreAtInstall(String packageName, int token) {
-        mUserBackupManagerService.restoreAtInstall(packageName, token);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "restoreAtInstall()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.restoreAtInstall(packageName, token);
+        }
     }
 
     /**
      * Begin a restore for the specified package {@code packageName} using the specified transport
      * {@code transportName}.
      */
+    @Nullable
     public IRestoreSession beginRestoreSession(String packageName, String transportName) {
-        return mUserBackupManagerService.beginRestoreSession(packageName, transportName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "beginRestoreSession()");
+
+        return userBackupManagerService == null
+                ? null
+                : userBackupManagerService.beginRestoreSession(packageName, transportName);
     }
 
     /**
@@ -453,7 +656,12 @@
      * the active set if possible, else the ancestral one. Returns zero if none available.
      */
     public long getAvailableRestoreToken(String packageName) {
-        return mUserBackupManagerService.getAvailableRestoreToken(packageName);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "getAvailableRestoreToken()");
+
+        return userBackupManagerService == null
+                ? 0
+                : userBackupManagerService.getAvailableRestoreToken(packageName);
     }
 
     // ---------------------------------------------
@@ -462,12 +670,19 @@
 
     /** Sets the backup password used when running adb backup. */
     public boolean setBackupPassword(String currentPassword, String newPassword) {
-        return mUserBackupManagerService.setBackupPassword(currentPassword, newPassword);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "setBackupPassword()");
+
+        return userBackupManagerService != null
+                && userBackupManagerService.setBackupPassword(currentPassword, newPassword);
     }
 
     /** Returns {@code true} if adb backup was run with a password, else returns {@code false}. */
     public boolean hasBackupPassword() {
-        return mUserBackupManagerService.hasBackupPassword();
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "hasBackupPassword()");
+
+        return userBackupManagerService != null && userBackupManagerService.hasBackupPassword();
     }
 
     /**
@@ -489,18 +704,22 @@
             boolean doKeyValue,
             String[] packageNames) {
         enforceCallingPermissionOnUserId(userId, "adbBackup");
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "adbBackup()");
 
-        mUserBackupManagerService.adbBackup(
-                fd,
-                includeApks,
-                includeObbs,
-                includeShared,
-                doWidgets,
-                doAllApps,
-                includeSystem,
-                doCompress,
-                doKeyValue,
-                packageNames);
+        if (userBackupManagerService != null) {
+            userBackupManagerService.adbBackup(
+                    fd,
+                    includeApks,
+                    includeObbs,
+                    includeShared,
+                    doWidgets,
+                    doAllApps,
+                    includeSystem,
+                    doCompress,
+                    doKeyValue,
+                    packageNames);
+        }
     }
 
     /**
@@ -510,8 +729,12 @@
      */
     public void adbRestore(@UserIdInt int userId, ParcelFileDescriptor fd) {
         enforceCallingPermissionOnUserId(userId, "setBackupEnabled");
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(userId, "adbRestore()");
 
-        mUserBackupManagerService.adbRestore(fd);
+        if (userBackupManagerService != null) {
+            userBackupManagerService.adbRestore(fd);
+        }
     }
 
     /**
@@ -524,8 +747,13 @@
             String currentPassword,
             String encryptionPassword,
             IFullBackupRestoreObserver observer) {
-        mUserBackupManagerService.acknowledgeAdbBackupOrRestore(
-                token, allow, currentPassword, encryptionPassword, observer);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "acknowledgeAdbBackupOrRestore()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.acknowledgeAdbBackupOrRestore(
+                    token, allow, currentPassword, encryptionPassword, observer);
+        }
     }
 
     // ---------------------------------------------
@@ -534,7 +762,12 @@
 
     /** Prints service state for 'dumpsys backup'. */
     public void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
-        mUserBackupManagerService.dump(fd, pw, args);
+        UserBackupManagerService userBackupManagerService =
+                getServiceForUser(UserHandle.USER_SYSTEM, "dump()");
+
+        if (userBackupManagerService != null) {
+            userBackupManagerService.dump(fd, pw, args);
+        }
     }
 
     private static boolean readBackupEnableState(int userId) {
@@ -592,7 +825,7 @@
             if (userId == UserHandle.USER_SYSTEM) {
                 sInstance.initializeServiceAndUnlockSystemUser();
             } else {
-                sInstance.startServiceForUser(userId);
+                sInstance.unlockUser(userId);
             }
         }
     }
diff --git a/services/backup/java/com/android/server/backup/Trampoline.java b/services/backup/java/com/android/server/backup/Trampoline.java
index 4acd5c4..59b72f9 100644
--- a/services/backup/java/com/android/server/backup/Trampoline.java
+++ b/services/backup/java/com/android/server/backup/Trampoline.java
@@ -116,7 +116,7 @@
         return SystemProperties.getBoolean(BACKUP_DISABLE_PROPERTY, false);
     }
 
-    protected boolean isMultiUserEnabled() {
+    private boolean isMultiUserEnabled() {
         return Settings.Global.getInt(
                 mContext.getContentResolver(),
                 Settings.Global.BACKUP_MULTI_USER_ENABLED,
@@ -145,6 +145,10 @@
         return new BackupManagerService(mContext, this, mHandlerThread);
     }
 
+    protected void postToHandler(Runnable runnable) {
+        mHandler.post(runnable);
+    }
+
     /**
      * Initialize {@link BackupManagerService} if the backup service is not disabled. Only the
      * system user can initialize the service.
@@ -174,14 +178,18 @@
      * to initialize {@link BackupManagerService} and set backup state for the system user.
      */
     void initializeServiceAndUnlockSystemUser() {
-        mHandler.post(
+        postToHandler(
                 () -> {
+                    // Initialize the backup service.
                     Trace.traceBegin(Trace.TRACE_TAG_ACTIVITY_MANAGER, "backup init");
                     initializeService(UserHandle.USER_SYSTEM);
                     Trace.traceEnd(Trace.TRACE_TAG_ACTIVITY_MANAGER);
 
+                    // Start the service for the system user.
                     BackupManagerService service = mService;
                     if (service != null) {
+                        Slog.i(TAG, "Starting service for system user");
+                        service.startServiceForUser(UserHandle.USER_SYSTEM);
                         Slog.i(TAG, "Unlocking system user");
                         service.unlockSystemUser();
                     }
@@ -195,20 +203,21 @@
      */
     // TODO(b/120212806): Consolidate service start for system and non-system users when system
     // user-only logic is removed.
-    void startServiceForUser(int userId) {
+    void unlockUser(int userId) {
         if (!isMultiUserEnabled()) {
             Slog.i(TAG, "Multi-user disabled, cannot start service for user: " + userId);
             return;
         }
 
-        mHandler.post(
-                () -> {
-                    BackupManagerService service = mService;
-                    if (service != null) {
-                        Slog.i(TAG, "Starting service for user: " + userId);
-                        service.startServiceForUser(userId);
-                    }
-                });
+        postToHandler(() -> startServiceForUser(userId));
+    }
+
+    private void startServiceForUser(int userId) {
+        BackupManagerService service = mService;
+        if (service != null) {
+            Slog.i(TAG, "Starting service for user: " + userId);
+            service.startServiceForUser(userId);
+        }
     }
 
     /**
@@ -242,6 +251,7 @@
             if (makeActive) {
                 mService = createBackupManagerService();
                 mSuppressFile.delete();
+                startServiceForUser(userId);
             } else {
                 mService = null;
                 try {
diff --git a/services/core/java/com/android/server/pm/dex/PackageDexUsage.java b/services/core/java/com/android/server/pm/dex/PackageDexUsage.java
index 519a20d..33a9650 100644
--- a/services/core/java/com/android/server/pm/dex/PackageDexUsage.java
+++ b/services/core/java/com/android/server/pm/dex/PackageDexUsage.java
@@ -16,9 +16,9 @@
 
 package com.android.server.pm.dex;
 
+import android.os.Build;
 import android.util.AtomicFile;
 import android.util.Slog;
-import android.os.Build;
 
 import com.android.internal.annotations.GuardedBy;
 import com.android.internal.annotations.VisibleForTesting;
@@ -26,26 +26,27 @@
 import com.android.server.pm.AbstractStatsBase;
 import com.android.server.pm.PackageManagerServiceUtils;
 
+import dalvik.system.VMRuntime;
+
+import libcore.io.IoUtils;
+
 import java.io.BufferedReader;
 import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
-import java.io.InputStreamReader;
 import java.io.IOException;
+import java.io.InputStreamReader;
 import java.io.OutputStreamWriter;
 import java.io.Reader;
 import java.io.StringWriter;
 import java.io.Writer;
 import java.util.Collections;
-import java.util.Iterator;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
 
-import dalvik.system.VMRuntime;
-import libcore.io.IoUtils;
-
 /**
  * Stat file which store usage information about dex files.
  */
@@ -86,6 +87,13 @@
     private static final String UNSUPPORTED_CLASS_LOADER_CONTEXT =
             "=UnsupportedClassLoaderContext=";
 
+    /**
+     * Limit on how many secondary DEX paths we store for a single owner, to avoid one app causing
+     * unbounded memory consumption.
+     */
+    @VisibleForTesting
+    /* package */ static final int MAX_SECONDARY_FILES_PER_OWNER = 100;
+
     // Map which structures the information we have on a package.
     // Maps package name to package data (which stores info about UsedByOtherApps and
     // secondary dex files.).
@@ -164,8 +172,12 @@
                     DexUseInfo existingData = packageUseInfo.mDexUseInfoMap.get(dexPath);
                     if (existingData == null) {
                         // It's the first time we see this dex file.
-                        packageUseInfo.mDexUseInfoMap.put(dexPath, newData);
-                        return true;
+                        if (packageUseInfo.mDexUseInfoMap.size() < MAX_SECONDARY_FILES_PER_OWNER) {
+                            packageUseInfo.mDexUseInfoMap.put(dexPath, newData);
+                            return true;
+                        } else {
+                            return updateLoadingPackages;
+                        }
                     } else {
                         if (ownerUserId != existingData.mOwnerUserId) {
                             // Oups, this should never happen, the DexManager who calls this should
diff --git a/services/robotests/src/com/android/server/backup/BackupManagerServiceTest.java b/services/robotests/src/com/android/server/backup/BackupManagerServiceTest.java
index 58bce1c..83f66c5 100644
--- a/services/robotests/src/com/android/server/backup/BackupManagerServiceTest.java
+++ b/services/robotests/src/com/android/server/backup/BackupManagerServiceTest.java
@@ -16,11 +16,15 @@
 
 package com.android.server.backup;
 
+import static android.Manifest.permission.INTERACT_ACROSS_USERS_FULL;
+
+import static com.android.server.backup.testing.BackupManagerServiceTestUtils.startBackupThread;
 import static com.android.server.backup.testing.TransportData.backupTransport;
 
 import static com.google.common.truth.Truth.assertThat;
 
 import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.never;
 import static org.mockito.Mockito.verify;
 import static org.robolectric.Shadows.shadowOf;
 import static org.testng.Assert.expectThrows;
@@ -37,8 +41,8 @@
 import android.os.ParcelFileDescriptor;
 import android.os.UserHandle;
 import android.platform.test.annotations.Presubmit;
+import android.util.SparseArray;
 
-import com.android.server.backup.testing.BackupManagerServiceTestUtils;
 import com.android.server.backup.testing.TransportData;
 import com.android.server.testing.shadows.ShadowBinder;
 
@@ -64,16 +68,14 @@
 public class BackupManagerServiceTest {
     private static final String TEST_PACKAGE = "package";
     private static final String TEST_TRANSPORT = "transport";
-
     private static final String[] ADB_TEST_PACKAGES = {TEST_PACKAGE};
 
-    private static final int NON_USER_SYSTEM = UserHandle.USER_SYSTEM + 1;
-
     private ShadowContextWrapper mShadowContext;
-    @Mock private UserBackupManagerService mUserBackupManagerService;
-    private BackupManagerService mBackupManagerService;
     private Context mContext;
-    @UserIdInt private int mUserId;
+    @UserIdInt private int mUserOneId;
+    @UserIdInt private int mUserTwoId;
+    @Mock private UserBackupManagerService mUserOneService;
+    @Mock private UserBackupManagerService mUserTwoService;
 
     /** Initialize {@link BackupManagerService}. */
     @Before
@@ -83,13 +85,11 @@
         Application application = RuntimeEnvironment.application;
         mContext = application;
         mShadowContext = shadowOf(application);
-        mUserId = NON_USER_SYSTEM;
-        mBackupManagerService =
-                new BackupManagerService(
-                        application,
-                        new Trampoline(application),
-                        BackupManagerServiceTestUtils.startBackupThread(null));
-        mBackupManagerService.setUserBackupManagerService(mUserBackupManagerService);
+
+        // TODO(b/120212806): Hardcoding system user for now since most methods in BMS don't yet
+        // take an user parameter (and instead hardcode the system user).
+        mUserOneId = UserHandle.USER_SYSTEM;
+        mUserTwoId = mUserOneId + 1;
     }
 
     /**
@@ -102,8 +102,8 @@
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#MORE_DEBUG} is set to {@code false}.
-     * This is specifically to prevent overloading the logs in production.
+     * Test verifying that {@link BackupManagerService#MORE_DEBUG} is set to {@code false}. This is
+     * specifically to prevent overloading the logs in production.
      */
     @Test
     public void testMoreDebug_isFalse() throws Exception {
@@ -112,9 +112,73 @@
         assertThat(moreDebug).isFalse();
     }
 
-    // TODO(b/118520567): Change the following tests to use the per-user instance of
-    // UserBackupManagerService once it's implemented. Currently these tests only test the straight
-    // forward redirection.
+    /** Test that the constructor does not create {@link UserBackupManagerService} instances. */
+    @Test
+    public void testConstructor_doesNotRegisterUsers() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        assertThat(backupManagerService.getServiceUsers().size()).isEqualTo(0);
+    }
+
+    /** Test that the constructor handles {@code null} parameters. */
+    @Test
+    public void testConstructor_withNullContext_throws() throws Exception {
+        expectThrows(
+                NullPointerException.class,
+                () ->
+                        new BackupManagerService(
+                                /* context */ null,
+                                new Trampoline(mContext),
+                                startBackupThread(null)));
+    }
+
+    /** Test that the constructor handles {@code null} parameters. */
+    @Test
+    public void testConstructor_withNullTrampoline_throws() throws Exception {
+        expectThrows(
+                NullPointerException.class,
+                () ->
+                        new BackupManagerService(
+                                mContext, /* trampoline */ null, startBackupThread(null)));
+    }
+
+    /** Test that the constructor handles {@code null} parameters. */
+    @Test
+    public void testConstructor_withNullBackupThread_throws() throws Exception {
+        expectThrows(
+                NullPointerException.class,
+                () ->
+                        new BackupManagerService(
+                                mContext, new Trampoline(mContext), /* backupThread */ null));
+    }
+
+    /** Test that the service registers users. */
+    @Test
+    public void testStartServiceForUser_registersUser() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.startServiceForUser(mUserOneId);
+
+        SparseArray<UserBackupManagerService> serviceUsers = backupManagerService.getServiceUsers();
+        assertThat(serviceUsers.size()).isEqualTo(1);
+        assertThat(serviceUsers.get(mUserOneId)).isNotNull();
+    }
+
+    /** Test that the service registers users. */
+    @Test
+    public void testStartServiceForUser_withServiceInstance_registersUser() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.startServiceForUser(mUserOneId, mUserOneService);
+
+        SparseArray<UserBackupManagerService> serviceUsers = backupManagerService.getServiceUsers();
+        assertThat(serviceUsers.size()).isEqualTo(1);
+        assertThat(serviceUsers.get(mUserOneId)).isEqualTo(mUserOneService);
+    }
+
+    // TODO(b/120212806): When BMS methods take in a user parameter, modify unknown user tests to
+    // check that that we don't call the method on another registered user. Currently these tests
+    // have no registered users since we hardcode the system user in BMS.
 
     // ---------------------------------------------
     // Backup agent tests
@@ -122,36 +186,88 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testDataChanged_callsDataChangedForUser() throws Exception {
-        mBackupManagerService.dataChanged(TEST_PACKAGE);
+    public void testDataChanged_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).dataChanged(TEST_PACKAGE);
+        backupManagerService.dataChanged(TEST_PACKAGE);
+
+        verify(mUserOneService).dataChanged(TEST_PACKAGE);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testDataChanged_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.dataChanged(TEST_PACKAGE);
+
+        verify(mUserOneService, never()).dataChanged(TEST_PACKAGE);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testAgentConnected_callsAgentConnectedForUser() throws Exception {
+    public void testAgentConnected_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         IBinder agentBinder = mock(IBinder.class);
 
-        mBackupManagerService.agentConnected(TEST_PACKAGE, agentBinder);
+        backupManagerService.agentConnected(TEST_PACKAGE, agentBinder);
 
-        verify(mUserBackupManagerService).agentConnected(TEST_PACKAGE, agentBinder);
+        verify(mUserOneService).agentConnected(TEST_PACKAGE, agentBinder);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testAgentConnected_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+        IBinder agentBinder = mock(IBinder.class);
+
+        backupManagerService.agentConnected(TEST_PACKAGE, agentBinder);
+
+        verify(mUserOneService, never()).agentConnected(TEST_PACKAGE, agentBinder);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testAgentDisconnected_callsAgentDisconnectedForUser() throws Exception {
-        mBackupManagerService.agentDisconnected(TEST_PACKAGE);
+    public void testAgentDisconnected_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).agentDisconnected(TEST_PACKAGE);
+        backupManagerService.agentDisconnected(TEST_PACKAGE);
+
+        verify(mUserOneService).agentDisconnected(TEST_PACKAGE);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testAgentDisconnected_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.agentDisconnected(TEST_PACKAGE);
+
+        verify(mUserOneService, never()).agentDisconnected(TEST_PACKAGE);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testOpComplete_callsOpCompleteForUser() throws Exception {
-        mBackupManagerService.opComplete(/* token */ 0, /* result */ 0L);
+    public void testOpComplete_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).opComplete(/* token */ 0, /* result */ 0L);
+        backupManagerService.opComplete(/* token */ 0, /* result */ 0L);
+
+        verify(mUserOneService).opComplete(/* token */ 0, /* result */ 0L);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testOpComplete_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.opComplete(/* token */ 0, /* result */ 0L);
+
+        verify(mUserOneService, never()).opComplete(/* token */ 0, /* result */ 0L);
     }
 
     // ---------------------------------------------
@@ -160,73 +276,168 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testInitializeTransports_callsInitializeTransportsForUser() throws Exception {
+    public void testInitializeTransports_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         String[] transports = {TEST_TRANSPORT};
 
-        mBackupManagerService.initializeTransports(transports, /* observer */ null);
+        backupManagerService.initializeTransports(transports, /* observer */ null);
 
-        verify(mUserBackupManagerService).initializeTransports(transports, /* observer */ null);
+        verify(mUserOneService).initializeTransports(transports, /* observer */ null);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testInitializeTransports_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+        String[] transports = {TEST_TRANSPORT};
+
+        backupManagerService.initializeTransports(transports, /* observer */ null);
+
+        verify(mUserOneService, never()).initializeTransports(transports, /* observer */ null);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testClearBackupData_callsClearBackupDataForUser() throws Exception {
-        mBackupManagerService.clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
+    public void testClearBackupData_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
+        backupManagerService.clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
+
+        verify(mUserOneService).clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testClearBackupData_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
+
+        verify(mUserOneService, never()).clearBackupData(TEST_TRANSPORT, TEST_PACKAGE);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetCurrentTransport_callsGetCurrentTransportForUser() throws Exception {
-        mBackupManagerService.getCurrentTransport();
+    public void testGetCurrentTransport_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getCurrentTransport();
+        backupManagerService.getCurrentTransport();
+
+        verify(mUserOneService).getCurrentTransport();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetCurrentTransport_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getCurrentTransport();
+
+        verify(mUserOneService, never()).getCurrentTransport();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetCurrentTransportComponent_callsGetCurrentTransportComponentForUser()
+    public void testGetCurrentTransportComponent_onRegisteredUser_callsMethodForUser()
             throws Exception {
-        mBackupManagerService.getCurrentTransportComponent();
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getCurrentTransportComponent();
+        backupManagerService.getCurrentTransportComponent();
+
+        verify(mUserOneService).getCurrentTransportComponent();
     }
 
-    /** Test that the backup service routes methods correctly to the user that requests it. */
+    /** Test that the backup service does not route methods for non-registered users. */
     @Test
-    public void testListAllTransports_callsListAllTransportsForUser() throws Exception {
-        mBackupManagerService.listAllTransports();
-
-        verify(mUserBackupManagerService).listAllTransports();
-    }
-
-    /** Test that the backup service routes methods correctly to the user that requests it. */
-    @Test
-    public void testListAllTransportComponents_callsListAllTransportComponentsForUser()
+    public void testGetCurrentTransportComponent_onUnknownUser_doesNotPropagateCall()
             throws Exception {
-        mBackupManagerService.listAllTransportComponents();
+        BackupManagerService backupManagerService = createService();
 
-        verify(mUserBackupManagerService).listAllTransportComponents();
+        backupManagerService.getCurrentTransportComponent();
+
+        verify(mUserOneService, never()).getCurrentTransportComponent();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetTransportWhitelist_callsGetTransportWhitelistForUser() throws Exception {
-        mBackupManagerService.getTransportWhitelist();
+    public void testListAllTransports_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getTransportWhitelist();
+        backupManagerService.listAllTransports();
+
+        verify(mUserOneService).listAllTransports();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testListAllTransports_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.listAllTransports();
+
+        verify(mUserOneService, never()).listAllTransports();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testUpdateTransportAttributes_callsUpdateTransportAttributesForUser()
+    public void testListAllTransportComponents_onRegisteredUser_callsMethodForUser()
             throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+
+        backupManagerService.listAllTransportComponents();
+
+        verify(mUserOneService).listAllTransportComponents();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testListAllTransportComponents_onUnknownUser_doesNotPropagateCall()
+            throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.listAllTransportComponents();
+
+        verify(mUserOneService, never()).listAllTransportComponents();
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testGetTransportWhitelist_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+
+        backupManagerService.getTransportWhitelist();
+
+        verify(mUserOneService).getTransportWhitelist();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetTransportWhitelist_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getTransportWhitelist();
+
+        verify(mUserOneService, never()).getTransportWhitelist();
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testUpdateTransportAttributes_onRegisteredUser_callsMethodForUser()
+            throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         TransportData transport = backupTransport();
         Intent configurationIntent = new Intent();
         Intent dataManagementIntent = new Intent();
 
-        mBackupManagerService.updateTransportAttributes(
+        backupManagerService.updateTransportAttributes(
                 transport.getTransportComponent(),
                 transport.transportName,
                 configurationIntent,
@@ -234,7 +445,34 @@
                 dataManagementIntent,
                 "dataManagementLabel");
 
-        verify(mUserBackupManagerService)
+        verify(mUserOneService)
+                .updateTransportAttributes(
+                        transport.getTransportComponent(),
+                        transport.transportName,
+                        configurationIntent,
+                        "currentDestinationString",
+                        dataManagementIntent,
+                        "dataManagementLabel");
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testUpdateTransportAttributes_onUnknownUser_doesNotPropagateCall()
+            throws Exception {
+        BackupManagerService backupManagerService = createService();
+        TransportData transport = backupTransport();
+        Intent configurationIntent = new Intent();
+        Intent dataManagementIntent = new Intent();
+
+        backupManagerService.updateTransportAttributes(
+                transport.getTransportComponent(),
+                transport.transportName,
+                configurationIntent,
+                "currentDestinationString",
+                dataManagementIntent,
+                "dataManagementLabel");
+
+        verify(mUserOneService, never())
                 .updateTransportAttributes(
                         transport.getTransportComponent(),
                         transport.transportName,
@@ -246,136 +484,292 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testSelectBackupTransport_callsSelectBackupTransportForUser() throws Exception {
-        mBackupManagerService.selectBackupTransport(TEST_TRANSPORT);
+    public void testSelectBackupTransport_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).selectBackupTransport(TEST_TRANSPORT);
+        backupManagerService.selectBackupTransport(TEST_TRANSPORT);
+
+        verify(mUserOneService).selectBackupTransport(TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSelectBackupTransport_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.selectBackupTransport(TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).selectBackupTransport(TEST_TRANSPORT);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testSelectTransportAsync_callsSelectTransportAsyncForUser() throws Exception {
+    public void testSelectTransportAsync_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         TransportData transport = backupTransport();
         ISelectBackupTransportCallback callback = mock(ISelectBackupTransportCallback.class);
 
-        mBackupManagerService.selectBackupTransportAsync(
+        backupManagerService.selectBackupTransportAsync(
                 transport.getTransportComponent(), callback);
 
-        verify(mUserBackupManagerService)
+        verify(mUserOneService)
+                .selectBackupTransportAsync(transport.getTransportComponent(), callback);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSelectBackupTransportAsync_onUnknownUser_doesNotPropagateCall()
+            throws Exception {
+        BackupManagerService backupManagerService = createService();
+        TransportData transport = backupTransport();
+        ISelectBackupTransportCallback callback = mock(ISelectBackupTransportCallback.class);
+
+        backupManagerService.selectBackupTransportAsync(
+                transport.getTransportComponent(), callback);
+
+        verify(mUserOneService, never())
                 .selectBackupTransportAsync(transport.getTransportComponent(), callback);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetConfigurationIntent_callsGetConfigurationIntentForUser() throws Exception {
-        mBackupManagerService.getConfigurationIntent(TEST_TRANSPORT);
+    public void testGetConfigurationIntent_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getConfigurationIntent(TEST_TRANSPORT);
+        backupManagerService.getConfigurationIntent(TEST_TRANSPORT);
+
+        verify(mUserOneService).getConfigurationIntent(TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetConfigurationIntent_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getConfigurationIntent(TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).getConfigurationIntent(TEST_TRANSPORT);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetDestinationString_callsGetDestinationStringForUser() throws Exception {
-        mBackupManagerService.getDestinationString(TEST_TRANSPORT);
+    public void testGetDestinationString_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getDestinationString(TEST_TRANSPORT);
+        backupManagerService.getDestinationString(TEST_TRANSPORT);
+
+        verify(mUserOneService).getDestinationString(TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetDestinationString_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getDestinationString(TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).getDestinationString(TEST_TRANSPORT);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetDataManagementIntent_callsGetDataManagementIntentForUser() throws Exception {
-        mBackupManagerService.getDataManagementIntent(TEST_TRANSPORT);
+    public void testGetDataManagementIntent_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getDataManagementIntent(TEST_TRANSPORT);
+        backupManagerService.getDataManagementIntent(TEST_TRANSPORT);
+
+        verify(mUserOneService).getDataManagementIntent(TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetDataManagementIntent_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getDataManagementIntent(TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).getDataManagementIntent(TEST_TRANSPORT);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetDataManagementLabel_callsGetDataManagementLabelForUser() throws Exception {
-        mBackupManagerService.getDataManagementLabel(TEST_TRANSPORT);
+    public void testGetDataManagementLabel_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getDataManagementLabel(TEST_TRANSPORT);
+        backupManagerService.getDataManagementLabel(TEST_TRANSPORT);
+
+        verify(mUserOneService).getDataManagementLabel(TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetDataManagementLabel_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getDataManagementLabel(TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).getDataManagementLabel(TEST_TRANSPORT);
     }
 
     // ---------------------------------------------
     // Settings tests
     // ---------------------------------------------
+
     /**
-     * Test verifying that {@link BackupManagerService#setBackupEnabled(int, boolean)} throws a
-     * {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     * Test that the backup services throws a {@link SecurityException} if the caller does not have
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void setBackupEnabled_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testSetBackupEnabled_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
         expectThrows(
                 SecurityException.class,
-                () -> mBackupManagerService.setBackupEnabled(mUserId, true));
+                () -> backupManagerService.setBackupEnabled(mUserTwoId, true));
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#setBackupEnabled(int, boolean)} does not
-     * require the caller to have INTERACT_ACROSS_USERS_FULL permission when the calling user id is
-     * the same as the target user id.
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void setBackupEnabled_whenCallingUserIsTargetUser_doesntNeedPermission() {
-        ShadowBinder.setCallingUserHandle(UserHandle.of(mUserId));
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testSetBackupEnabled_withPermission_propagatesForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
 
-        mBackupManagerService.setBackupEnabled(mUserId, true);
+        backupManagerService.setBackupEnabled(mUserTwoId, true);
 
-        verify(mUserBackupManagerService).setBackupEnabled(true);
-    }
-
-
-    /** Test that the backup service routes methods correctly to the user that requests it. */
-    @Test
-    public void setBackupEnabled_callsSetBackupEnabledForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
-        mBackupManagerService.setBackupEnabled(mUserId, true);
-
-        verify(mUserBackupManagerService).setBackupEnabled(true);
+        verify(mUserTwoService).setBackupEnabled(true);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void setAutoRestore_callsSetAutoRestoreForUser() throws Exception {
-        mBackupManagerService.setAutoRestore(true);
+    public void testSetBackupEnabled_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        verify(mUserBackupManagerService).setAutoRestore(true);
+        backupManagerService.setBackupEnabled(mUserOneId, true);
+
+        verify(mUserOneService).setBackupEnabled(true);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSetBackupEnabled_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.setBackupEnabled(mUserTwoId, true);
+
+        verify(mUserOneService, never()).setBackupEnabled(true);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testSetBackupProvisioned_callsSetBackupProvisionedForUser() throws Exception {
-        mBackupManagerService.setBackupProvisioned(true);
+    public void testSetAutoRestore_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).setBackupProvisioned(true);
+        backupManagerService.setAutoRestore(true);
+
+        verify(mUserOneService).setAutoRestore(true);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSetAutoRestore_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.setAutoRestore(true);
+
+        verify(mUserOneService, never()).setAutoRestore(true);
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testSetBackupProvisioned_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+
+        backupManagerService.setBackupProvisioned(true);
+
+        verify(mUserOneService).setBackupProvisioned(true);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSetBackupProvisioned_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.setBackupProvisioned(true);
+
+        verify(mUserOneService, never()).setBackupProvisioned(true);
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#isBackupEnabled(int)} throws a
-     * {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     * Test that the backup services throws a {@link SecurityException} if the caller does not have
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testIsBackupEnabled_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testIsBackupEnabled_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
         expectThrows(
-                SecurityException.class,
-                () -> mBackupManagerService.isBackupEnabled(mUserId));
+                SecurityException.class, () -> backupManagerService.isBackupEnabled(mUserTwoId));
+    }
+
+    /**
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
+     */
+    @Test
+    public void testIsBackupEnabled_withPermission_propagatesForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
+
+        backupManagerService.isBackupEnabled(mUserTwoId);
+
+        verify(mUserTwoService).isBackupEnabled();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testIsBackupEnabled_callsIsBackupEnabledForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testIsBackupEnabled_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        mBackupManagerService.isBackupEnabled(mUserId);
+        backupManagerService.isBackupEnabled(mUserOneId);
 
-        verify(mUserBackupManagerService).isBackupEnabled();
+        verify(mUserOneService).isBackupEnabled();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testIsBackupEnabled_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.isBackupEnabled(mUserTwoId);
+
+        verify(mUserOneService, never()).isBackupEnabled();
     }
 
     // ---------------------------------------------
@@ -384,128 +778,290 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testIsAppEligibleForBackup_callsIsAppEligibleForBackupForUser() throws Exception {
-        mBackupManagerService.isAppEligibleForBackup(TEST_PACKAGE);
+    public void testIsAppEligibleForBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).isAppEligibleForBackup(TEST_PACKAGE);
+        backupManagerService.isAppEligibleForBackup(TEST_PACKAGE);
+
+        verify(mUserOneService).isAppEligibleForBackup(TEST_PACKAGE);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testIsAppEligibleForBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.isAppEligibleForBackup(TEST_PACKAGE);
+
+        verify(mUserOneService, never()).isAppEligibleForBackup(TEST_PACKAGE);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testFilterAppsEligibleForBackup_callsFilterAppsEligibleForBackupForUser()
+    public void testFilterAppsEligibleForBackup_onRegisteredUser_callsMethodForUser()
             throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         String[] packages = {TEST_PACKAGE};
 
-        mBackupManagerService.filterAppsEligibleForBackup(packages);
+        backupManagerService.filterAppsEligibleForBackup(packages);
 
-        verify(mUserBackupManagerService).filterAppsEligibleForBackup(packages);
+        verify(mUserOneService).filterAppsEligibleForBackup(packages);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testFilterAppsEligibleForBackup_onUnknownUser_doesNotPropagateCall()
+            throws Exception {
+        BackupManagerService backupManagerService = createService();
+        String[] packages = {TEST_PACKAGE};
+
+        backupManagerService.filterAppsEligibleForBackup(packages);
+
+        verify(mUserOneService, never()).filterAppsEligibleForBackup(packages);
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#backupNow(int)} throws a
-     * {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     * Test verifying that {@link BackupManagerService#backupNow(int)} throws a {@link
+     * SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
      */
     @Test
-    public void testBackupNow_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testBackupNow_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        expectThrows(
-                SecurityException.class,
-                () -> mBackupManagerService.backupNow(mUserId));
+        expectThrows(SecurityException.class, () -> backupManagerService.backupNow(mUserTwoId));
+    }
+
+    /**
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
+     */
+    @Test
+    public void testBackupNow_withPermission_propagatesForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
+
+        backupManagerService.backupNow(mUserTwoId);
+
+        verify(mUserTwoService).backupNow();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testBackupNow_callsBackupNowForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testBackupNow_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        mBackupManagerService.backupNow(mUserId);
+        backupManagerService.backupNow(mUserOneId);
 
-        verify(mUserBackupManagerService).backupNow();
+        verify(mUserOneService).backupNow();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testBackupNow_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.backupNow(mUserTwoId);
+
+        verify(mUserOneService, never()).backupNow();
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#requestBackup(int, String[], IBackupObserver,
-     * IBackupManagerMonitor, int)} throws a {@link SecurityException} if the caller does not have
-     * INTERACT_ACROSS_USERS_FULL permission.
+     * Test that the backup services throws a {@link SecurityException} if the caller does not have
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testRequestBackup_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testRequestBackup_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
         String[] packages = {TEST_PACKAGE};
         IBackupObserver observer = mock(IBackupObserver.class);
         IBackupManagerMonitor monitor = mock(IBackupManagerMonitor.class);
 
         expectThrows(
                 SecurityException.class,
-                () -> mBackupManagerService.requestBackup(mUserId, packages, observer, monitor, 0));
-    }
-
-
-    /** Test that the backup service routes methods correctly to the user that requests it. */
-    @Test
-    public void testRequestBackup_callsRequestBackupForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-        String[] packages = {TEST_PACKAGE};
-        IBackupObserver observer = mock(IBackupObserver.class);
-        IBackupManagerMonitor monitor = mock(IBackupManagerMonitor.class);
-
-        mBackupManagerService.requestBackup(mUserId, packages, observer, monitor,
-                /* flags */ 0);
-
-        verify(mUserBackupManagerService).requestBackup(packages, observer, monitor, /* flags */ 0);
+                () ->
+                        backupManagerService.requestBackup(
+                                mUserTwoId, packages, observer, monitor, 0));
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#cancelBackups(int)} throws a
-     * {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testCancelBackups_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testRequestBackup_withPermission_propagatesForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
+        String[] packages = {TEST_PACKAGE};
+        IBackupObserver observer = mock(IBackupObserver.class);
+        IBackupManagerMonitor monitor = mock(IBackupManagerMonitor.class);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
 
-        expectThrows(
-                SecurityException.class,
-                () -> mBackupManagerService.cancelBackups(mUserId));
-    }
+        backupManagerService.requestBackup(mUserTwoId, packages, observer, monitor, /* flags */ 0);
 
-
-    /** Test that the backup service routes methods correctly to the user that requests it. */
-    @Test
-    public void testCancelBackups_callsCancelBackupsForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
-        mBackupManagerService.cancelBackups(mUserId);
-
-        verify(mUserBackupManagerService).cancelBackups();
+        verify(mUserTwoService).requestBackup(packages, observer, monitor, /* flags */ 0);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testBeginFullBackup_callsBeginFullBackupForUser() throws Exception {
+    public void testRequestBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        String[] packages = {TEST_PACKAGE};
+        IBackupObserver observer = mock(IBackupObserver.class);
+        IBackupManagerMonitor monitor = mock(IBackupManagerMonitor.class);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
+
+        backupManagerService.requestBackup(mUserOneId, packages, observer, monitor, /* flags */ 0);
+
+        verify(mUserOneService).requestBackup(packages, observer, monitor, /* flags */ 0);
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testRequestBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        String[] packages = {TEST_PACKAGE};
+        IBackupObserver observer = mock(IBackupObserver.class);
+        IBackupManagerMonitor monitor = mock(IBackupManagerMonitor.class);
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.requestBackup(mUserTwoId, packages, observer, monitor, /* flags */ 0);
+
+        verify(mUserOneService, never()).requestBackup(packages, observer, monitor, /* flags */ 0);
+    }
+
+    /**
+     * Test verifying that {@link BackupManagerService#cancelBackups(int)} throws a {@link
+     * SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     */
+    @Test
+    public void testCancelBackups_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
+
+        expectThrows(SecurityException.class, () -> backupManagerService.cancelBackups(mUserTwoId));
+    }
+
+    /**
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
+     */
+    @Test
+    public void testCancelBackups_withPermission_propagatesForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
+
+        backupManagerService.cancelBackups(mUserTwoId);
+
+        verify(mUserTwoService).cancelBackups();
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testCancelBackups_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
+
+        backupManagerService.cancelBackups(mUserOneId);
+
+        verify(mUserOneService).cancelBackups();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testCancelBackups_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.cancelBackups(mUserTwoId);
+
+        verify(mUserOneService, never()).cancelBackups();
+    }
+
+    /** Test that the backup service routes methods correctly to the user that requests it. */
+    @Test
+    public void testBeginFullBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         FullBackupJob job = new FullBackupJob();
 
-        mBackupManagerService.beginFullBackup(job);
+        backupManagerService.beginFullBackup(job);
 
-        verify(mUserBackupManagerService).beginFullBackup(job);
+        verify(mUserOneService).beginFullBackup(job);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testBeginFullBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+        FullBackupJob job = new FullBackupJob();
+
+        backupManagerService.beginFullBackup(job);
+
+        verify(mUserOneService, never()).beginFullBackup(job);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testEndFullBackup_callsEndFullBackupForUser() throws Exception {
-        mBackupManagerService.endFullBackup();
+    public void testEndFullBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).endFullBackup();
+        backupManagerService.endFullBackup();
+
+        verify(mUserOneService).endFullBackup();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testEndFullBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.endFullBackup();
+
+        verify(mUserOneService, never()).endFullBackup();
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testFullTransportBackup_callsFullTransportBackupForUser() throws Exception {
+    public void testFullTransportBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         String[] packages = {TEST_PACKAGE};
 
-        mBackupManagerService.fullTransportBackup(packages);
+        backupManagerService.fullTransportBackup(packages);
 
-        verify(mUserBackupManagerService).fullTransportBackup(packages);
+        verify(mUserOneService).fullTransportBackup(packages);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testFullTransportBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+        String[] packages = {TEST_PACKAGE};
+
+        backupManagerService.fullTransportBackup(packages);
+
+        verify(mUserOneService, never()).fullTransportBackup(packages);
     }
 
     // ---------------------------------------------
@@ -514,27 +1070,66 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testRestoreAtInstall_callsRestoreAtInstallForUser() throws Exception {
-        mBackupManagerService.restoreAtInstall(TEST_PACKAGE, /* token */ 0);
+    public void testRestoreAtInstall_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).restoreAtInstall(TEST_PACKAGE, /* token */ 0);
+        backupManagerService.restoreAtInstall(TEST_PACKAGE, /* token */ 0);
+
+        verify(mUserOneService).restoreAtInstall(TEST_PACKAGE, /* token */ 0);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testRestoreAtInstall_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.restoreAtInstall(TEST_PACKAGE, /* token */ 0);
+
+        verify(mUserOneService, never()).restoreAtInstall(TEST_PACKAGE, /* token */ 0);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testBeginRestoreSession_callsBeginRestoreSessionForUser() throws Exception {
-        mBackupManagerService.beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
+    public void testBeginRestoreSession_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
+        backupManagerService.beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
+
+        verify(mUserOneService).beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testBeginRestoreSession_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
+
+        verify(mUserOneService, never()).beginRestoreSession(TEST_PACKAGE, TEST_TRANSPORT);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testGetAvailableRestoreToken_callsGetAvailableRestoreTokenForUser()
+    public void testGetAvailableRestoreToken_onRegisteredUser_callsMethodForUser()
             throws Exception {
-        mBackupManagerService.getAvailableRestoreToken(TEST_PACKAGE);
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).getAvailableRestoreToken(TEST_PACKAGE);
+        backupManagerService.getAvailableRestoreToken(TEST_PACKAGE);
+
+        verify(mUserOneService).getAvailableRestoreToken(TEST_PACKAGE);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testGetAvailableRestoreToken_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.getAvailableRestoreToken(TEST_PACKAGE);
+
+        verify(mUserOneService, never()).getAvailableRestoreToken(TEST_PACKAGE);
     }
 
     // ---------------------------------------------
@@ -543,33 +1138,61 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testSetBackupPassword_callsSetBackupPasswordForUser() throws Exception {
-        mBackupManagerService.setBackupPassword("currentPassword", "newPassword");
+    public void testSetBackupPassword_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).setBackupPassword("currentPassword", "newPassword");
+        backupManagerService.setBackupPassword("currentPassword", "newPassword");
+
+        verify(mUserOneService).setBackupPassword("currentPassword", "newPassword");
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testSetBackupPassword_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.setBackupPassword("currentPassword", "newPassword");
+
+        verify(mUserOneService, never()).setBackupPassword("currentPassword", "newPassword");
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testHasBackupPassword_callsHasBackupPasswordForUser() throws Exception {
-        mBackupManagerService.hasBackupPassword();
+    public void testHasBackupPassword_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
 
-        verify(mUserBackupManagerService).hasBackupPassword();
+        backupManagerService.hasBackupPassword();
+
+        verify(mUserOneService).hasBackupPassword();
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testHasBackupPassword_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+
+        backupManagerService.hasBackupPassword();
+
+        verify(mUserOneService, never()).hasBackupPassword();
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#adbBackup(ParcelFileDescriptor, int, boolean,
-     * boolean, boolean, boolean, boolean, boolean, boolean, boolean, String[])} throws a
-     * {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL permission.
+     * Test that the backup services throws a {@link SecurityException} if the caller does not have
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testAdbBackup_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testAdbBackup_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        expectThrows(SecurityException.class,
+        expectThrows(
+                SecurityException.class,
                 () ->
-                        mBackupManagerService.adbBackup(
-                                /* userId */ mUserId,
+                        backupManagerService.adbBackup(
+                                mUserTwoId,
                                 /* parcelFileDescriptor*/ null,
                                 /* includeApks */ true,
                                 /* includeObbs */ true,
@@ -580,24 +1203,22 @@
                                 /* doCompress */ true,
                                 /* doKeyValue */ true,
                                 null));
-
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#adbBackup(ParcelFileDescriptor, int, boolean,
-     * boolean, boolean, boolean, boolean, boolean, boolean, boolean, String[])} does not require
-     * the caller to have INTERACT_ACROSS_USERS_FULL permission when the calling user id is the
-     * same as the target user id.
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testAdbBackup_whenCallingUserIsTargetUser_doesntNeedPermission() throws Exception {
-        ShadowBinder.setCallingUserHandle(UserHandle.of(mUserId));
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
+    public void testAdbBackup_withPermission_propagatesForNonCallingUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
         ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
 
-        mBackupManagerService.adbBackup(
-                /* userId */ mUserId,
+        backupManagerService.adbBackup(
+                mUserTwoId,
                 parcelFileDescriptor,
                 /* includeApks */ true,
                 /* includeObbs */ true,
@@ -609,7 +1230,7 @@
                 /* doKeyValue */ true,
                 ADB_TEST_PACKAGES);
 
-        verify(mUserBackupManagerService)
+        verify(mUserTwoService)
                 .adbBackup(
                         parcelFileDescriptor,
                         /* includeApks */ true,
@@ -625,13 +1246,14 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testAdbBackup_callsAdbBackupForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
+    public void testAdbBackup_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        mBackupManagerService.adbBackup(
-                /* userId */ mUserId,
+        backupManagerService.adbBackup(
+                mUserOneId,
                 parcelFileDescriptor,
                 /* includeApks */ true,
                 /* includeObbs */ true,
@@ -643,7 +1265,42 @@
                 /* doKeyValue */ true,
                 ADB_TEST_PACKAGES);
 
-        verify(mUserBackupManagerService)
+        verify(mUserOneService)
+                .adbBackup(
+                        parcelFileDescriptor,
+                        /* includeApks */ true,
+                        /* includeObbs */ true,
+                        /* includeShared */ true,
+                        /* doWidgets */ true,
+                        /* doAllApps */ true,
+                        /* includeSystem */ true,
+                        /* doCompress */ true,
+                        /* doKeyValue */ true,
+                        ADB_TEST_PACKAGES);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testAdbBackup_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.adbBackup(
+                mUserTwoId,
+                parcelFileDescriptor,
+                /* includeApks */ true,
+                /* includeObbs */ true,
+                /* includeShared */ true,
+                /* doWidgets */ true,
+                /* doAllApps */ true,
+                /* includeSystem */ true,
+                /* doCompress */ true,
+                /* doKeyValue */ true,
+                ADB_TEST_PACKAGES);
+
+        verify(mUserOneService, never())
                 .adbBackup(
                         parcelFileDescriptor,
                         /* includeApks */ true,
@@ -658,58 +1315,93 @@
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#adbRestore(ParcelFileDescriptor, int)} throws
-     * a {@link SecurityException} if the caller does not have INTERACT_ACROSS_USERS_FULL
-     * permission.
+     * Test that the backup services throws a {@link SecurityException} if the caller does not have
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testAdbRestore_withoutPermission_throwsSecurityException() {
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
+    public void testAdbRestore_withoutPermission_throwsSecurityExceptionForNonCallingUser() {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        expectThrows(SecurityException.class,
-                () -> mBackupManagerService.adbRestore(mUserId, null));
-
+        expectThrows(
+                SecurityException.class, () -> backupManagerService.adbRestore(mUserTwoId, null));
     }
 
     /**
-     * Test verifying that {@link BackupManagerService#adbRestore(ParcelFileDescriptor, int)} does
-     * not require the caller to have INTERACT_ACROSS_USERS_FULL permission when the calling user id
-     * is the same as the target user id.
+     * Test that the backup service does not throw a {@link SecurityException} if the caller has
+     * INTERACT_ACROSS_USERS_FULL permission and passes a different user id.
      */
     @Test
-    public void testAdbRestore_whenCallingUserIsTargetUser_doesntNeedPermission() throws Exception {
-        ShadowBinder.setCallingUserHandle(UserHandle.of(mUserId));
-        mShadowContext.denyPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
+    public void testAdbRestore_withPermission_propagatesForNonCallingUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        backupManagerService.startServiceForUser(mUserTwoId, mUserTwoService);
         ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ true);
 
-        mBackupManagerService.adbRestore(mUserId, parcelFileDescriptor);
+        backupManagerService.adbRestore(mUserTwoId, parcelFileDescriptor);
 
-        verify(mUserBackupManagerService).adbRestore(parcelFileDescriptor);
+        verify(mUserTwoService).adbRestore(parcelFileDescriptor);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testAdbRestore_callsAdbRestoreForUser() throws Exception {
-        mShadowContext.grantPermissions(android.Manifest.permission.INTERACT_ACROSS_USERS_FULL);
-
+    public void testAdbRestore_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserOneId, /* shouldGrantPermission */ false);
 
-        mBackupManagerService.adbRestore(mUserId, parcelFileDescriptor);
+        backupManagerService.adbRestore(mUserOneId, parcelFileDescriptor);
 
-        verify(mUserBackupManagerService).adbRestore(parcelFileDescriptor);
+        verify(mUserOneService).adbRestore(parcelFileDescriptor);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testAdbRestore_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
+        ParcelFileDescriptor parcelFileDescriptor = getFileDescriptorForAdbTest();
+        setCallerAndGrantInteractUserPermission(mUserTwoId, /* shouldGrantPermission */ false);
+
+        backupManagerService.adbRestore(mUserTwoId, parcelFileDescriptor);
+
+        verify(mUserOneService, never()).adbRestore(parcelFileDescriptor);
     }
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testAcknowledgeAdbBackupOrRestore_callsAcknowledgeAdbBackupOrRestoreForUser()
+    public void testAcknowledgeAdbBackupOrRestore_onRegisteredUser_callsMethodForUser()
             throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         IFullBackupRestoreObserver observer = mock(IFullBackupRestoreObserver.class);
 
-        mBackupManagerService.acknowledgeAdbBackupOrRestore(
+        backupManagerService.acknowledgeAdbBackupOrRestore(
                 /* token */ 0, /* allow */ true, "currentPassword", "encryptionPassword", observer);
 
-        verify(mUserBackupManagerService)
+        verify(mUserOneService)
+                .acknowledgeAdbBackupOrRestore(
+                        /* token */ 0,
+                        /* allow */ true,
+                        "currentPassword",
+                        "encryptionPassword",
+                        observer);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testAcknowledgeAdbBackupOrRestore_onUnknownUser_doesNotPropagateCall()
+            throws Exception {
+        BackupManagerService backupManagerService = createService();
+        IFullBackupRestoreObserver observer = mock(IFullBackupRestoreObserver.class);
+
+        backupManagerService.acknowledgeAdbBackupOrRestore(
+                /* token */ 0, /* allow */ true, "currentPassword", "encryptionPassword", observer);
+
+        verify(mUserOneService, never())
                 .acknowledgeAdbBackupOrRestore(
                         /* token */ 0,
                         /* allow */ true,
@@ -724,16 +1416,60 @@
 
     /** Test that the backup service routes methods correctly to the user that requests it. */
     @Test
-    public void testDump_callsDumpForUser() throws Exception {
+    public void testDump_onRegisteredUser_callsMethodForUser() throws Exception {
+        BackupManagerService backupManagerService =
+                createServiceAndRegisterUser(mUserOneId, mUserOneService);
         File testFile = new File(mContext.getFilesDir(), "test");
         testFile.createNewFile();
         FileDescriptor fileDescriptor = new FileDescriptor();
         PrintWriter printWriter = new PrintWriter(testFile);
         String[] args = {"1", "2"};
 
-        mBackupManagerService.dump(fileDescriptor, printWriter, args);
+        backupManagerService.dump(fileDescriptor, printWriter, args);
 
-        verify(mUserBackupManagerService).dump(fileDescriptor, printWriter, args);
+        verify(mUserOneService).dump(fileDescriptor, printWriter, args);
+    }
+
+    /** Test that the backup service does not route methods for non-registered users. */
+    @Test
+    public void testDump_onUnknownUser_doesNotPropagateCall() throws Exception {
+        BackupManagerService backupManagerService = createService();
+        File testFile = new File(mContext.getFilesDir(), "test");
+        testFile.createNewFile();
+        FileDescriptor fileDescriptor = new FileDescriptor();
+        PrintWriter printWriter = new PrintWriter(testFile);
+        String[] args = {"1", "2"};
+
+        backupManagerService.dump(fileDescriptor, printWriter, args);
+
+        verify(mUserOneService, never()).dump(fileDescriptor, printWriter, args);
+    }
+
+    private BackupManagerService createService() {
+        return new BackupManagerService(
+                mContext, new Trampoline(mContext), startBackupThread(null));
+    }
+
+    private BackupManagerService createServiceAndRegisterUser(
+            int userId, UserBackupManagerService userBackupManagerService) {
+        BackupManagerService backupManagerService = createService();
+        backupManagerService.startServiceForUser(userId, userBackupManagerService);
+        return backupManagerService;
+    }
+
+    /**
+     * Sets the calling user to {@code userId} and grants the permission INTERACT_ACROSS_USERS_FULL
+     * to the caller if {@code shouldGrantPermission} is {@code true}, else it denies the
+     * permission.
+     */
+    private void setCallerAndGrantInteractUserPermission(
+            @UserIdInt int userId, boolean shouldGrantPermission) {
+        ShadowBinder.setCallingUserHandle(UserHandle.of(userId));
+        if (shouldGrantPermission) {
+            mShadowContext.grantPermissions(INTERACT_ACROSS_USERS_FULL);
+        } else {
+            mShadowContext.denyPermissions(INTERACT_ACROSS_USERS_FULL);
+        }
     }
 
     private ParcelFileDescriptor getFileDescriptorForAdbTest() throws Exception {
diff --git a/services/tests/servicestests/src/com/android/server/backup/TrampolineTest.java b/services/tests/servicestests/src/com/android/server/backup/TrampolineTest.java
index d7a398e..ff31435 100644
--- a/services/tests/servicestests/src/com/android/server/backup/TrampolineTest.java
+++ b/services/tests/servicestests/src/com/android/server/backup/TrampolineTest.java
@@ -132,19 +132,21 @@
     }
 
     @Test
-    public void startServiceForUser_whenMultiUserSettingDisabled_isIgnored() {
+    public void unlockUser_whenMultiUserSettingDisabled_isIgnoredForNonSystemUser() {
         Settings.Global.putInt(mContentResolver, Settings.Global.BACKUP_MULTI_USER_ENABLED, 0);
+        mTrampoline.initializeService(UserHandle.USER_SYSTEM);
 
-        mTrampoline.startServiceForUser(10);
+        mTrampoline.unlockUser(10);
 
         verify(mBackupManagerServiceMock, never()).startServiceForUser(10);
     }
 
     @Test
-    public void startServiceForUser_whenMultiUserSettingEnabled_callsBackupManagerService() {
+    public void unlockUser_whenMultiUserSettingEnabled_callsBackupManagerServiceForNonSystemUser() {
         Settings.Global.putInt(mContentResolver, Settings.Global.BACKUP_MULTI_USER_ENABLED, 1);
+        mTrampoline.initializeService(UserHandle.USER_SYSTEM);
 
-        mTrampoline.startServiceForUser(10);
+        mTrampoline.unlockUser(10);
 
         verify(mBackupManagerServiceMock).startServiceForUser(10);
     }
@@ -989,6 +991,11 @@
             return sBackupManagerServiceMock;
         }
 
+        @Override
+        protected void postToHandler(Runnable runnable) {
+            runnable.run();
+        }
+
         int getCreateServiceCallsCount() {
             return mCreateServiceCallsCount;
         }
diff --git a/services/tests/servicestests/src/com/android/server/pm/dex/PackageDexUsageTests.java b/services/tests/servicestests/src/com/android/server/pm/dex/PackageDexUsageTests.java
index 7755e94..5df4509 100644
--- a/services/tests/servicestests/src/com/android/server/pm/dex/PackageDexUsageTests.java
+++ b/services/tests/servicestests/src/com/android/server/pm/dex/PackageDexUsageTests.java
@@ -17,6 +17,7 @@
 package com.android.server.pm.dex;
 
 import static com.android.server.pm.dex.PackageDexUsage.DexUseInfo;
+import static com.android.server.pm.dex.PackageDexUsage.MAX_SECONDARY_FILES_PER_OWNER;
 import static com.android.server.pm.dex.PackageDexUsage.PackageUseInfo;
 
 import static org.junit.Assert.assertEquals;
@@ -31,24 +32,28 @@
 import androidx.test.filters.SmallTest;
 import androidx.test.runner.AndroidJUnit4;
 
+import dalvik.system.VMRuntime;
+
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
-import dalvik.system.VMRuntime;
-
 import java.io.IOException;
 import java.io.StringReader;
 import java.io.StringWriter;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 @RunWith(AndroidJUnit4.class)
 @SmallTest
 public class PackageDexUsageTests {
+    private static final String ISA = VMRuntime.getInstructionSet(Build.SUPPORTED_ABIS[0]);
+
     private PackageDexUsage mPackageDexUsage;
 
     private TestData mFooBaseUser0;
@@ -71,25 +76,23 @@
         String fooCodeDir = "/data/app/com.google.foo/";
         String fooDataDir = "/data/user/0/com.google.foo/";
 
-        String isa = VMRuntime.getInstructionSet(Build.SUPPORTED_ABIS[0]);
-
         mFooBaseUser0 = new TestData(fooPackageName,
-                fooCodeDir + "base.apk", 0, isa, false, true, fooPackageName);
+                fooCodeDir + "base.apk", 0, ISA, false, true, fooPackageName);
 
         mFooSplit1User0 = new TestData(fooPackageName,
-                fooCodeDir + "split-1.apk", 0, isa, false, true, fooPackageName);
+                fooCodeDir + "split-1.apk", 0, ISA, false, true, fooPackageName);
 
         mFooSplit2UsedByOtherApps0 = new TestData(fooPackageName,
-                fooCodeDir + "split-2.apk", 0, isa, true, true, "used.by.other.com");
+                fooCodeDir + "split-2.apk", 0, ISA, true, true, "used.by.other.com");
 
         mFooSecondary1User0 = new TestData(fooPackageName,
-                fooDataDir + "sec-1.dex", 0, isa, false, false, fooPackageName);
+                fooDataDir + "sec-1.dex", 0, ISA, false, false, fooPackageName);
 
         mFooSecondary1User1 = new TestData(fooPackageName,
-                fooDataDir + "sec-1.dex", 1, isa, false, false, fooPackageName);
+                fooDataDir + "sec-1.dex", 1, ISA, false, false, fooPackageName);
 
         mFooSecondary2UsedByOtherApps0 = new TestData(fooPackageName,
-                fooDataDir + "sec-2.dex", 0, isa, true, false, "used.by.other.com");
+                fooDataDir + "sec-2.dex", 0, ISA, true, false, "used.by.other.com");
 
         mInvalidIsa = new TestData(fooPackageName,
                 fooCodeDir + "base.apk", 0, "INVALID_ISA", false, true, "INALID_USER");
@@ -100,11 +103,11 @@
         String barDataDir1 = "/data/user/1/com.google.bar/";
 
         mBarBaseUser0 = new TestData(barPackageName,
-                barCodeDir + "base.apk", 0, isa, false, true, barPackageName);
+                barCodeDir + "base.apk", 0, ISA, false, true, barPackageName);
         mBarSecondary1User0 = new TestData(barPackageName,
-                barDataDir + "sec-1.dex", 0, isa, false, false, barPackageName);
+                barDataDir + "sec-1.dex", 0, ISA, false, false, barPackageName);
         mBarSecondary2User1 = new TestData(barPackageName,
-                barDataDir1 + "sec-2.dex", 1, isa, false, false, barPackageName);
+                barDataDir1 + "sec-2.dex", 1, ISA, false, false, barPackageName);
     }
 
     @Test
@@ -183,6 +186,25 @@
     }
 
     @Test
+    public void testRecordTooManySecondaries() {
+        int tooManyFiles = MAX_SECONDARY_FILES_PER_OWNER + 1;
+        List<TestData> expectedSecondaries = new ArrayList<>();
+        for (int i = 1; i <= tooManyFiles; i++) {
+            String fooPackageName = "com.google.foo";
+            TestData testData = new TestData(fooPackageName,
+                    "/data/user/0/" + fooPackageName + "/sec-" + i + "1.dex", 0, ISA, false, false,
+                    fooPackageName);
+            if (i < tooManyFiles) {
+                assertTrue("Adding " + testData.mDexFile, record(testData));
+                expectedSecondaries.add(testData);
+            } else {
+                assertFalse("Adding " + testData.mDexFile, record(testData));
+            }
+            assertPackageDexUsage(mPackageDexUsage, null, null, expectedSecondaries);
+        }
+    }
+
+    @Test
     public void testMultiplePackages() {
         assertTrue(record(mFooBaseUser0));
         assertTrue(record(mFooSecondary1User0));
@@ -540,7 +562,14 @@
 
     private void assertPackageDexUsage(PackageDexUsage packageDexUsage, Set<String> users,
             TestData primary, TestData... secondaries) {
-        String packageName = primary == null ? secondaries[0].mPackageName : primary.mPackageName;
+        assertPackageDexUsage(packageDexUsage, users, primary, Arrays.asList(secondaries));
+    }
+
+    private void assertPackageDexUsage(PackageDexUsage packageDexUsage, Set<String> users,
+            TestData primary, List<TestData> secondaries) {
+        String packageName = primary == null
+                ? secondaries.get(0).mPackageName
+                : primary.mPackageName;
         boolean primaryUsedByOtherApps = primary != null && primary.mUsedByOtherApps;
         PackageUseInfo pInfo = packageDexUsage.getPackageUseInfo(packageName);
 
@@ -554,7 +583,7 @@
         }
 
         Map<String, DexUseInfo> dexUseInfoMap = pInfo.getDexUseInfoMap();
-        assertEquals(secondaries.length, dexUseInfoMap.size());
+        assertEquals(secondaries.size(), dexUseInfoMap.size());
 
         // Check dex use info
         for (TestData testData : secondaries) {