MessageStack: add quitting sentinel node

We use the timestamp of the quitting message to tell
DeliQueue whether it should remove all messages or just
remove messages past a given time ("removeAllFutureMessages").

Test: atest android.os.MessageStackTest
Bug: 421623328
Flag: EXEMPT new data structure isn't used yet; usages will be flagged.
Change-Id: I7caf36e9a5fc1efec1be7f733b4b2d7f2f176f92

core/java/android/os/MessageStack.java

diff --git a/core/java/android/os/MessageStack.java b/core/java/android/os/MessageStack.java
index 5424d05..be71ad1 100644
--- a/core/java/android/os/MessageStack.java
+++ b/core/java/android/os/MessageStack.java
@@ -41,7 +41,7 @@
     private final MessageHeap mAsyncHeap = new MessageHeap();
 
     // This points to the most-recently processed message. Comparison with mTopValue will indicate
-    // whether some messages still need to be processed.
+    // whether some messages still need to be processed. This value excludes the quitting sentinel.
     private Message mLooperProcessed = null;
 
     static {
@@ -56,17 +56,65 @@
         }
     }
 
+    private static final Object QUITTING_NODE_OBJ = new Object();
+
+    private boolean isQuittingMessage(Message m) {
+        return m != null && m.obj == QUITTING_NODE_OBJ;
+    }
+
     /**
      * Pushes a message onto the top of the stack with a CAS.
+     * @return true if successfully pushed; false if the stack is quitting.
      */
-    public void pushMessage(Message m) {
-        // TODO: This should fail if the current top value is the shutdown sentinel.
+    public boolean pushMessage(Message m) {
         Message current;
         do {
             current = mTopValue;
+            if (isQuittingMessage(current)) {
+                return false;
+            }
             m.next = current;
         } while (!sTop.weakCompareAndSetRelease(this, current, m));
+        return true;
+    }
 
+    /**
+     * Pushes a quitting message onto the top of the stack.
+     * After this call no more messages can be pushed onto the stack.
+     * @return true if pushed, false if there was already a quitting message
+     */
+    public boolean pushQuitting(long when) {
+        Message quittingMsg = Message.obtain();
+        quittingMsg.obj = QUITTING_NODE_OBJ;
+        quittingMsg.when = when;
+        /* Should never go into the heap, initialize idx to an impossible value */
+        quittingMsg.heapIndex = -1;
+        final boolean ret = pushMessage(quittingMsg);
+        if (!ret) {
+            quittingMsg.recycleUnchecked();
+        }
+
+        return ret;
+    }
+
+    /**
+     * Query if we are in a quitting state.
+     * @return true if we have a quitting message on top of the stack.
+     */
+    public boolean isQuitting() {
+        return isQuittingMessage((Message) sTop.getAcquire(this));
+    }
+
+    /**
+     * Gets timestamp of quitting message.
+     * @return timestamp, or throws an exception if no quitting message exists.
+     */
+    public long getQuittingTimestamp() throws IllegalStateException {
+        Message m = (Message) sTop.getAcquire(this);
+        if (!isQuittingMessage(m)) {
+            throw new IllegalStateException();
+        }
+        return m.when;
     }
 
     /**
@@ -80,7 +128,8 @@
 
         while (current != null) {
             // Check that the message hasn't already been removed or processed elsewhere.
-            if (!current.isRemoved()
+            if (!isQuittingMessage(current)
+                    && !current.isRemoved()
                     && compare.compareMessage(current, h, what, object, r, when)
                     && current.markRemoved()) {
                 if (firstRemoved == null) {
@@ -107,6 +156,14 @@
      */
     public void heapSweep() {
         Message current = (Message) sTop.getAcquire(this);
+
+        if (current != null && isQuittingMessage(current)) {
+            if (current.next != null) {
+                current.next.prev = current;
+            }
+            current = current.next;
+        }
+
         Message prevLooperProcessed = mLooperProcessed;
         mLooperProcessed = current;
 

core/tests/coretests/src/android/os/MessageStackTest.java

diff --git a/core/tests/coretests/src/android/os/MessageStackTest.java b/core/tests/coretests/src/android/os/MessageStackTest.java
index 6e4238c..015e0ba 100644
--- a/core/tests/coretests/src/android/os/MessageStackTest.java
+++ b/core/tests/coretests/src/android/os/MessageStackTest.java
@@ -17,7 +17,9 @@
 package android.os;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
 
 import androidx.test.runner.AndroidJUnit4;
 
@@ -46,6 +48,24 @@
     }
 
     /**
+     * Verify quitting state
+     */
+    @Test
+    public void testQuitting() {
+        MessageStack stack = new MessageStack();
+        for (int i = 0; i < 10; i++) {
+            stack.pushMessage(new Message());
+        }
+
+        assertFalse(stack.isQuitting());
+
+        stack.pushQuitting(42);
+        assertFalse(stack.pushMessage(new Message()));
+        assertTrue(stack.isQuitting());
+        assertEquals(stack.getQuittingTimestamp(), 42);
+    }
+
+    /**
      * Verify heap size after sweeping messages from a MessageStack.
      */
     @Test