diff --git a/service/src/com/android/server/connectivity/CarrierPrivilegeAuthenticator.java b/service/src/com/android/server/connectivity/CarrierPrivilegeAuthenticator.java
index ef07201..ab7b1a7 100644
--- a/service/src/com/android/server/connectivity/CarrierPrivilegeAuthenticator.java
+++ b/service/src/com/android/server/connectivity/CarrierPrivilegeAuthenticator.java
@@ -21,6 +21,7 @@
 import static com.android.server.connectivity.ConnectivityFlags.CARRIER_SERVICE_CHANGED_USE_CALLBACK;
 
 import android.annotation.NonNull;
+import android.annotation.Nullable;
 import android.content.BroadcastReceiver;
 import android.content.Context;
 import android.content.Intent;
@@ -72,9 +73,7 @@
     private final Object mLock = new Object();
     private final Handler mHandler;
     @NonNull
-    @GuardedBy("mLock")
-    private final List<CarrierPrivilegesListenerShim> mCarrierPrivilegesChangedListeners =
-            new ArrayList<>();
+    private final List<PrivilegeListener> mCarrierPrivilegesChangedListeners = new ArrayList<>();
     private final boolean mUseCallbacksForServiceChanged;
 
     public CarrierPrivilegeAuthenticator(@NonNull final Context c,
@@ -119,32 +118,49 @@
         synchronized (mLock) {
             unregisterCarrierPrivilegesListeners();
             mModemCount = mTelephonyManager.getActiveModemCount();
-            registerCarrierPrivilegesListeners();
-            updateCarrierServiceUid();
+            registerCarrierPrivilegesListeners(mModemCount);
+            if (!mUseCallbacksForServiceChanged) updateCarrierServiceUid();
         }
     }
 
-    private void registerCarrierPrivilegesListeners() {
-        final HandlerExecutor executor = new HandlerExecutor(mHandler);
-        int modemCount;
-        synchronized (mLock) {
-            modemCount = mModemCount;
+    private class PrivilegeListener implements CarrierPrivilegesListenerShim {
+        public final int mLogicalSlot;
+        PrivilegeListener(final int logicalSlot) {
+            mLogicalSlot = logicalSlot;
         }
+
+        @Override public void onCarrierPrivilegesChanged(
+                @NonNull List<String> privilegedPackageNames,
+                @NonNull int[] privilegedUids) {
+            if (mUseCallbacksForServiceChanged) return;
+            // Re-trigger the synchronous check (which is also very cheap due
+            // to caching in CarrierPrivilegesTracker). This allows consistency
+            // with the onSubscriptionsChangedListener and broadcasts.
+            updateCarrierServiceUid();
+        }
+
+        @Override
+        public void onCarrierServiceChanged(@Nullable final String carrierServicePackageName,
+                final int carrierServiceUid) {
+            if (!mUseCallbacksForServiceChanged) {
+                // Re-trigger the synchronous check (which is also very cheap due
+                // to caching in CarrierPrivilegesTracker). This allows consistency
+                // with the onSubscriptionsChangedListener and broadcasts.
+                updateCarrierServiceUid();
+                return;
+            }
+            synchronized (mLock) {
+                mCarrierServiceUid.put(mLogicalSlot, carrierServiceUid);
+            }
+        }
+    }
+
+    private void registerCarrierPrivilegesListeners(final int modemCount) {
+        final HandlerExecutor executor = new HandlerExecutor(mHandler);
         try {
             for (int i = 0; i < modemCount; i++) {
-                CarrierPrivilegesListenerShim carrierPrivilegesListener =
-                        new CarrierPrivilegesListenerShim() {
-                            @Override
-                            public void onCarrierPrivilegesChanged(
-                                    @NonNull List<String> privilegedPackageNames,
-                                    @NonNull int[] privilegedUids) {
-                                // Re-trigger the synchronous check (which is also very cheap due
-                                // to caching in CarrierPrivilegesTracker). This allows consistency
-                                // with the onSubscriptionsChangedListener and broadcasts.
-                                updateCarrierServiceUid();
-                            }
-                        };
-                addCarrierPrivilegesListener(i, executor, carrierPrivilegesListener);
+                PrivilegeListener carrierPrivilegesListener = new PrivilegeListener(i);
+                addCarrierPrivilegesListener(executor, carrierPrivilegesListener);
                 mCarrierPrivilegesChangedListeners.add(carrierPrivilegesListener);
             }
         } catch (IllegalArgumentException e) {
@@ -152,24 +168,13 @@
         }
     }
 
-    private void addCarrierPrivilegesListener(int logicalSlotIndex, Executor executor,
-            CarrierPrivilegesListenerShim listener) {
-        try {
-            mTelephonyManagerShim.addCarrierPrivilegesListener(
-                    logicalSlotIndex, executor, listener);
-        } catch (UnsupportedApiLevelException unsupportedApiLevelException) {
-            // Should not happen since CarrierPrivilegeAuthenticator is only used on T+
-            Log.e(TAG, "addCarrierPrivilegesListener API is not available");
+    @GuardedBy("mLock")
+    private void unregisterCarrierPrivilegesListeners() {
+        for (PrivilegeListener carrierPrivilegesListener : mCarrierPrivilegesChangedListeners) {
+            removeCarrierPrivilegesListener(carrierPrivilegesListener);
+            mCarrierServiceUid.delete(carrierPrivilegesListener.mLogicalSlot);
         }
-    }
-
-    private void removeCarrierPrivilegesListener(CarrierPrivilegesListenerShim listener) {
-        try {
-            mTelephonyManagerShim.removeCarrierPrivilegesListener(listener);
-        } catch (UnsupportedApiLevelException unsupportedApiLevelException) {
-            // Should not happen since CarrierPrivilegeAuthenticator is only used on T+
-            Log.e(TAG, "removeCarrierPrivilegesListener API is not available");
-        }
+        mCarrierPrivilegesChangedListeners.clear();
     }
 
     private String getCarrierServicePackageNameForLogicalSlot(int logicalSlotIndex) {
@@ -183,14 +188,6 @@
         return null;
     }
 
-    private void unregisterCarrierPrivilegesListeners() {
-        for (CarrierPrivilegesListenerShim carrierPrivilegesListener :
-                mCarrierPrivilegesChangedListeners) {
-            removeCarrierPrivilegesListener(carrierPrivilegesListener);
-        }
-        mCarrierPrivilegesChangedListeners.clear();
-    }
-
     /**
      * Check if a UID is the carrier service app of the subscription ID in the provided capabilities
      *
@@ -273,4 +270,26 @@
     int getCarrierServicePackageUidForSlot(int slotId) {
         return getUidForPackage(getCarrierServicePackageNameForLogicalSlot(slotId));
     }
+
+    // Helper methods to avoid having to deal with UnsupportedApiLevelException.
+
+    private void addCarrierPrivilegesListener(@NonNull final Executor executor,
+            @NonNull final PrivilegeListener listener) {
+        try {
+            mTelephonyManagerShim.addCarrierPrivilegesListener(listener.mLogicalSlot, executor,
+                    listener);
+        } catch (UnsupportedApiLevelException unsupportedApiLevelException) {
+            // Should not happen since CarrierPrivilegeAuthenticator is only used on T+
+            Log.e(TAG, "addCarrierPrivilegesListener API is not available");
+        }
+    }
+
+    private void removeCarrierPrivilegesListener(PrivilegeListener listener) {
+        try {
+            mTelephonyManagerShim.removeCarrierPrivilegesListener(listener);
+        } catch (UnsupportedApiLevelException unsupportedApiLevelException) {
+            // Should not happen since CarrierPrivilegeAuthenticator is only used on T+
+            Log.e(TAG, "removeCarrierPrivilegesListener API is not available");
+        }
+    }
 }
diff --git a/tests/unit/java/com/android/server/connectivity/CarrierPrivilegeAuthenticatorTest.java b/tests/unit/java/com/android/server/connectivity/CarrierPrivilegeAuthenticatorTest.java
index 2ecd2a1..8113626 100644
--- a/tests/unit/java/com/android/server/connectivity/CarrierPrivilegeAuthenticatorTest.java
+++ b/tests/unit/java/com/android/server/connectivity/CarrierPrivilegeAuthenticatorTest.java
@@ -158,6 +158,8 @@
         assertNotNull(initialListeners.get(1));
         assertEquals(2, initialListeners.size());
 
+        initialListeners.get(0).onCarrierServiceChanged(null, mCarrierConfigPkgUid);
+
         final NetworkCapabilities.Builder ncBuilder = new NetworkCapabilities.Builder()
                 .addTransportType(TRANSPORT_CELLULAR)
                 .setNetworkSpecifier(new TelephonyNetworkSpecifier(0));
@@ -194,6 +196,8 @@
         assertNotNull(newListeners.get(0));
         assertEquals(1, newListeners.size());
 
+        newListeners.get(0).onCarrierServiceChanged(null, mCarrierConfigPkgUid);
+
         final TelephonyNetworkSpecifier specifier = new TelephonyNetworkSpecifier(0);
         final NetworkCapabilities nc = new NetworkCapabilities.Builder()
                 .addTransportType(TRANSPORT_CELLULAR)
@@ -219,6 +223,7 @@
         applicationInfo.uid = mCarrierConfigPkgUid + 1;
         doReturn(applicationInfo).when(mPackageManager).getApplicationInfo(eq(mTestPkg), anyInt());
         listener.onCarrierPrivilegesChanged(Collections.emptyList(), new int[] {});
+        listener.onCarrierServiceChanged(null, applicationInfo.uid);
 
         assertFalse(mCarrierPrivilegeAuthenticator.hasCarrierPrivilegeForNetworkCapabilities(
                 mCarrierConfigPkgUid, nc));
@@ -228,6 +233,9 @@
 
     @Test
     public void testDefaultSubscription() throws Exception {
+        final CarrierPrivilegesListenerShim listener = getCarrierPrivilegesListeners().get(0);
+        listener.onCarrierServiceChanged(null, mCarrierConfigPkgUid);
+
         final NetworkCapabilities.Builder ncBuilder = new NetworkCapabilities.Builder();
         ncBuilder.addTransportType(TRANSPORT_CELLULAR);
         assertFalse(mCarrierPrivilegeAuthenticator.hasCarrierPrivilegeForNetworkCapabilities(