diff --git a/services/core/java/com/android/server/net/NetworkPolicyManagerService.java b/services/core/java/com/android/server/net/NetworkPolicyManagerService.java
index 73ddf04..71ff523 100644
--- a/services/core/java/com/android/server/net/NetworkPolicyManagerService.java
+++ b/services/core/java/com/android/server/net/NetworkPolicyManagerService.java
@@ -1252,7 +1252,7 @@
                 if (isUidStateChangeRelevant(callbackInfo, procState, procStateSeq, capability)) {
                     callbackInfo.update(uid, procState, procStateSeq, capability);
                     if (!callbackInfo.isPending) {
-                        mUidEventHandler.obtainMessage(UID_MSG_STATE_CHANGED, callbackInfo)
+                        mUidEventHandler.obtainMessage(UID_MSG_STATE_CHANGED, uid, 0)
                                 .sendToTarget();
                         callbackInfo.isPending = true;
                     }
@@ -1264,7 +1264,6 @@
             synchronized (mUidStateCallbackInfos) {
                 mUidStateCallbackInfos.remove(uid);
             }
-            // TODO: b/327058756 - Remove any pending UID_MSG_STATE_CHANGED on the handler.
             mUidEventHandler.obtainMessage(UID_MSG_GONE, uid, 0).sendToTarget();
         }
     };
@@ -5864,13 +5863,13 @@
     private final Handler.Callback mUidEventHandlerCallback = new Handler.Callback() {
         @Override
         public boolean handleMessage(Message msg) {
+            final int uid = msg.arg1;
             switch (msg.what) {
                 case UID_MSG_STATE_CHANGED: {
-                    handleUidChanged((UidStateCallbackInfo) msg.obj);
+                    handleUidChanged(uid);
                     return true;
                 }
                 case UID_MSG_GONE: {
-                    final int uid = msg.arg1;
                     handleUidGone(uid);
                     return true;
                 }
@@ -5881,23 +5880,27 @@
         }
     };
 
-    void handleUidChanged(@NonNull UidStateCallbackInfo uidStateCallbackInfo) {
+    void handleUidChanged(int uid) {
         Trace.traceBegin(Trace.TRACE_TAG_NETWORK, "onUidStateChanged");
         try {
-            boolean updated;
-            final int uid;
             final int procState;
             final long procStateSeq;
             final int capability;
-            synchronized (mUidRulesFirstLock) {
-                synchronized (mUidStateCallbackInfos) {
-                    uid = uidStateCallbackInfo.uid;
-                    procState = uidStateCallbackInfo.procState;
-                    procStateSeq = uidStateCallbackInfo.procStateSeq;
-                    capability = uidStateCallbackInfo.capability;
-                    uidStateCallbackInfo.isPending = false;
+            synchronized (mUidStateCallbackInfos) {
+                final UidStateCallbackInfo uidStateCallbackInfo = mUidStateCallbackInfos.get(uid);
+                if (uidStateCallbackInfo == null) {
+                    // This can happen if UidObserver#onUidGone gets called before we reach
+                    // here. In this case, there is no point in processing this change as this
+                    // will immediately be followed by a call to handleUidGone anyway.
+                    return;
                 }
-
+                procState = uidStateCallbackInfo.procState;
+                procStateSeq = uidStateCallbackInfo.procStateSeq;
+                capability = uidStateCallbackInfo.capability;
+                uidStateCallbackInfo.isPending = false;
+            }
+            final boolean updated;
+            synchronized (mUidRulesFirstLock) {
                 // We received a uid state change callback, add it to the history so that it
                 // will be useful for debugging.
                 mLogger.uidStateChanged(uid, procState, procStateSeq, capability);
@@ -5920,6 +5923,14 @@
     void handleUidGone(int uid) {
         Trace.traceBegin(Trace.TRACE_TAG_NETWORK, "onUidGone");
         try {
+            synchronized (mUidStateCallbackInfos) {
+                if (mUidStateCallbackInfos.contains(uid)) {
+                    // This can happen if UidObserver#onUidStateChanged gets called before we
+                    // reach here. In this case, there is no point in processing this change as this
+                    // will immediately be followed by a call to handleUidChanged anyway.
+                    return;
+                }
+            }
             final boolean updated;
             synchronized (mUidRulesFirstLock) {
                 updated = removeUidStateUL(uid);
diff --git a/services/tests/servicestests/src/com/android/server/net/NetworkPolicyManagerServiceTest.java b/services/tests/servicestests/src/com/android/server/net/NetworkPolicyManagerServiceTest.java
index 15cd511..a5f7963 100644
--- a/services/tests/servicestests/src/com/android/server/net/NetworkPolicyManagerServiceTest.java
+++ b/services/tests/servicestests/src/com/android/server/net/NetworkPolicyManagerServiceTest.java
@@ -2404,6 +2404,45 @@
     }
 
     @Test
+    public void testObsoleteHandleUidGone() throws Exception {
+        callAndWaitOnUidStateChanged(UID_A, PROCESS_STATE_TOP, 51);
+        assertFalse(mService.isUidNetworkingBlocked(UID_A, false));
+
+        clearInvocations(mNetworkManager);
+
+        // In the service, handleUidGone is only called from mUidEventHandler. Then a call to it may
+        // be rendered obsolete by a newer uid change posted on the handler. The latest uid state
+        // change is always reflected in the current UidStateChangeCallbackInfo for the uid, so to
+        // simulate an obsolete call for test, we directly call handleUidGone and leave the state in
+        // UidStateChangeCallbackInfo set by the previous call to onUidStateChanged(TOP). This call
+        // should then do nothing.
+        mService.handleUidGone(UID_A);
+
+        verify(mNetworkManager, times(0)).setFirewallUidRule(anyInt(), anyInt(), anyInt());
+        assertFalse(mService.isUidNetworkingBlocked(UID_A, false));
+    }
+
+    @Test
+    @RequiresFlagsEnabled(Flags.FLAG_NETWORK_BLOCKED_FOR_TOP_SLEEPING_AND_ABOVE)
+    public void testObsoleteHandleUidChanged() throws Exception {
+        callAndWaitOnUidGone(UID_A);
+        assertTrue(mService.isUidNetworkingBlocked(UID_A, false));
+
+        clearInvocations(mNetworkManager);
+
+        // In the service, handleUidChanged is only called from mUidEventHandler. Then a call to it
+        // may be rendered obsolete by an immediate uid-gone posted on the handler. The latest uid
+        // state change is always reflected in the current UidStateChangeCallbackInfo for the uid,
+        // so to simulate an obsolete call for test, we directly call handleUidChanged and leave the
+        // state in UidStateChangeCallbackInfo as null as it would get removed by the previous call
+        // to onUidGone(). This call should then do nothing.
+        mService.handleUidChanged(UID_A);
+
+        verify(mNetworkManager, times(0)).setFirewallUidRule(anyInt(), anyInt(), anyInt());
+        assertTrue(mService.isUidNetworkingBlocked(UID_A, false));
+    }
+
+    @Test
     public void testLowPowerStandbyAllowlist() throws Exception {
         // Chain background is also enabled but these procstates are important enough to be exempt.
         callAndWaitOnUidStateChanged(UID_A, PROCESS_STATE_TOP, 0);