diff --git a/VoldNativeService.cpp b/VoldNativeService.cpp
index 11a9398..5529f67 100644
--- a/VoldNativeService.cpp
+++ b/VoldNativeService.cpp
@@ -358,12 +358,16 @@
 }
 
 binder::Status VoldNativeService::onUserStarted(int32_t userId,
-                                                const std::vector<std::string>& packageNames) {
+                                                const std::vector<std::string>& packageNames,
+                                                const std::vector<int>& appIds,
+                                                const std::vector<std::string>& sandboxIds) {
     ENFORCE_UID(AID_SYSTEM);
     CHECK_ARGUMENT_PACKAGE_NAMES(packageNames);
+    CHECK_ARGUMENT_SANDBOX_IDS(sandboxIds);
     ACQUIRE_LOCK;
 
-    return translate(VolumeManager::Instance()->onUserStarted(userId, packageNames));
+    return translate(
+        VolumeManager::Instance()->onUserStarted(userId, packageNames, appIds, sandboxIds));
 }
 
 binder::Status VoldNativeService::onUserStopped(int32_t userId) {
@@ -899,7 +903,7 @@
 }
 
 binder::Status VoldNativeService::destroySandboxForApp(const std::string& packageName,
-                                                       int32_t appId, const std::string& sandboxId,
+                                                       const std::string& sandboxId,
                                                        int32_t userId) {
     ENFORCE_UID(AID_SYSTEM);
     CHECK_ARGUMENT_PACKAGE_NAME(packageName);
@@ -907,7 +911,7 @@
     ACQUIRE_LOCK;
 
     return translate(
-        VolumeManager::Instance()->destroySandboxForApp(packageName, appId, sandboxId, userId));
+        VolumeManager::Instance()->destroySandboxForApp(packageName, sandboxId, userId));
 }
 
 binder::Status VoldNativeService::startCheckpoint(int32_t retry) {
diff --git a/VoldNativeService.h b/VoldNativeService.h
index 8a3ac00..aea0f1a 100644
--- a/VoldNativeService.h
+++ b/VoldNativeService.h
@@ -39,7 +39,9 @@
 
     binder::Status onUserAdded(int32_t userId, int32_t userSerial);
     binder::Status onUserRemoved(int32_t userId);
-    binder::Status onUserStarted(int32_t userId, const std::vector<std::string>& packageNames);
+    binder::Status onUserStarted(int32_t userId, const std::vector<std::string>& packageNames,
+                                 const std::vector<int>& appIds,
+                                 const std::vector<std::string>& sandboxIds);
     binder::Status onUserStopped(int32_t userId);
 
     binder::Status addAppIds(const std::vector<std::string>& packageNames,
@@ -118,7 +120,7 @@
 
     binder::Status prepareSandboxForApp(const std::string& packageName, int32_t appId,
                                         const std::string& sandboxId, int32_t userId);
-    binder::Status destroySandboxForApp(const std::string& packageName, int32_t appId,
+    binder::Status destroySandboxForApp(const std::string& packageName,
                                         const std::string& sandboxId, int32_t userId);
 
     binder::Status startCheckpoint(int32_t retry);
diff --git a/VolumeManager.cpp b/VolumeManager.cpp
index 5b0f073..d38052d 100644
--- a/VolumeManager.cpp
+++ b/VolumeManager.cpp
@@ -761,7 +761,9 @@
     return 0;
 }
 
-int VolumeManager::onUserStarted(userid_t userId, const std::vector<std::string>& packageNames) {
+int VolumeManager::onUserStarted(userid_t userId, const std::vector<std::string>& packageNames,
+                                 const std::vector<int>& appIds,
+                                 const std::vector<std::string>& sandboxIds) {
     LOG(VERBOSE) << "onUserStarted: " << userId;
     // Note that sometimes the system will spin up processes from Zygote
     // before actually starting the user, so we're okay if Zygote
@@ -771,6 +773,10 @@
 
     mStartedUsers.insert(userId);
     mUserPackages[userId] = packageNames;
+    for (size_t i = 0; i < packageNames.size(); ++i) {
+        mAppIds[packageNames[i]] = appIds[i];
+        mSandboxIds[appIds[i]] = sandboxIds[i];
+    }
     if (mPrimary) {
         linkPrimary(userId);
     }
@@ -852,13 +858,13 @@
     return prepareSandboxes(userId, {packageName}, visibleVolLabels);
 }
 
-int VolumeManager::destroySandboxForApp(const std::string& packageName, appid_t appId,
+int VolumeManager::destroySandboxForApp(const std::string& packageName,
                                         const std::string& sandboxId, userid_t userId) {
     if (!GetBoolProperty(kIsolatedStorage, false)) {
         return 0;
     }
-    LOG(VERBOSE) << "destroySandboxForApp: " << packageName << ", appId=" << appId
-                 << ", sandboxId=" << sandboxId << ", userId=" << userId;
+    LOG(VERBOSE) << "destroySandboxForApp: " << packageName << ", sandboxId=" << sandboxId
+                 << ", userId=" << userId;
     auto& userPackages = mUserPackages[userId];
     std::remove(userPackages.begin(), userPackages.end(), packageName);
     // If the package is not uninstalled in any other users, remove appId and sandboxId
@@ -872,8 +878,11 @@
         }
     }
     if (!installedInAnyUser) {
-        mAppIds.erase(packageName);
-        mSandboxIds.erase(appId);
+        const auto& entry = mAppIds.find(packageName);
+        if (entry != mAppIds.end()) {
+            mSandboxIds.erase(entry->second);
+            mAppIds.erase(entry);
+        }
     }
 
     std::vector<std::string> visibleVolLabels;
diff --git a/VolumeManager.h b/VolumeManager.h
index 8982d8f..1cbc4bf 100644
--- a/VolumeManager.h
+++ b/VolumeManager.h
@@ -90,7 +90,8 @@
 
     int onUserAdded(userid_t userId, int userSerialNumber);
     int onUserRemoved(userid_t userId);
-    int onUserStarted(userid_t userId, const std::vector<std::string>& packageNames);
+    int onUserStarted(userid_t userId, const std::vector<std::string>& packageNames,
+                      const std::vector<int>& appIds, const std::vector<std::string>& sandboxIds);
     int onUserStopped(userid_t userId);
 
     int addAppIds(const std::vector<std::string>& packageNames, const std::vector<int32_t>& appIds);
@@ -98,8 +99,8 @@
                       const std::vector<std::string>& sandboxIds);
     int prepareSandboxForApp(const std::string& packageName, appid_t appId,
                              const std::string& sandboxId, userid_t userId);
-    int destroySandboxForApp(const std::string& packageName, appid_t appId,
-                             const std::string& sandboxId, userid_t userId);
+    int destroySandboxForApp(const std::string& packageName, const std::string& sandboxId,
+                             userid_t userId);
 
     int onVolumeMounted(android::vold::VolumeBase* vol);
     int onVolumeUnmounted(android::vold::VolumeBase* vol);
diff --git a/binder/android/os/IVold.aidl b/binder/android/os/IVold.aidl
index 96301b3..b1846d0 100644
--- a/binder/android/os/IVold.aidl
+++ b/binder/android/os/IVold.aidl
@@ -29,7 +29,8 @@
 
     void onUserAdded(int userId, int userSerial);
     void onUserRemoved(int userId);
-    void onUserStarted(int userId, in @utf8InCpp String[] packageNames);
+    void onUserStarted(int userId, in @utf8InCpp String[] packageNames, in int[] appIds,
+            in @utf8InCpp String[] sandboxIds);
     void onUserStopped(int userId);
 
     void addAppIds(in @utf8InCpp String[] packageNames, in int[] appIds);
@@ -101,7 +102,7 @@
 
     void prepareSandboxForApp(in @utf8InCpp String packageName, int appId,
                               in @utf8InCpp String sandboxId, int userId);
-    void destroySandboxForApp(in @utf8InCpp String packageName, int appId,
+    void destroySandboxForApp(in @utf8InCpp String packageName,
                               in @utf8InCpp String sandboxId, int userId);
 
     void startCheckpoint(int retry);