Add a barrier mechanism to the MessageQueue.

The synchronization barrier enables selectively blocking
execution of synchronous messages until the barrier is released.
Asynchronous messages may continue running in the meantime.

The barrier is intended to be used to implement more sophisticated
scheduling policies related to view hierarchy traversals.  While
traversals are pending, most messages posted to the message queue
must be held up.  This is to satisfy the invariant that traversals
will occur before subsequently posted messages are handled.

The exception to this rule are "asynchronous" messages that represent
external events or interrupts that come from other components such
as VSYNC pulses, input events or sensor events.  Because these messages
are typically delivered at arbitrary times, they are independent of
traversals or other typical synchronization boundaries.

Messages can now be flagged as asynchronous to indicate that they
are weakly ordered.

Bug: 5721047
Change-Id: I1446dcfbc896f33b48355adc28967ace8c8c9b9b

2 files changed, 136 insertions, 18 deletions

diff --git a/core/java/android/os/Message.java b/core/java/android/os/Message.java
index 844ed6a..b816b11 100644
--- a/core/java/android/os/Message.java
+++ b/core/java/android/os/Message.java
@@ -75,13 +75,13 @@ public final class Message implements Parcelable {
     public Messenger replyTo;
 
     /** If set message is in use */
-    /*package*/ static final int FLAG_IN_USE = 1;
+    /*package*/ static final int FLAG_IN_USE = 1 << 0;
 
-    /** Flags reserved for future use (All are reserved for now) */
-    /*package*/ static final int FLAGS_RESERVED = ~FLAG_IN_USE;
+    /** If set message is asynchronous */
+    /*package*/ static final int FLAG_ASYNCHRONOUS = 1 << 1;
 
     /** Flags to clear in the copyFrom method */
-    /*package*/ static final int FLAGS_TO_CLEAR_ON_COPY_FROM = FLAGS_RESERVED | FLAG_IN_USE;
+    /*package*/ static final int FLAGS_TO_CLEAR_ON_COPY_FROM = FLAG_IN_USE;
 
     /*package*/ int flags;
 
@@ -363,6 +363,48 @@ public final class Message implements Parcelable {
         target.sendMessage(this);
     }
 
+    /**
+     * Returns true if the message is asynchronous.
+     *
+     * Asynchronous messages represent interrupts or events that do not require global ordering
+     * with represent to synchronous messages.  Asynchronous messages are not subject to
+     * the synchronization barriers introduced by {@link MessageQueue#acquireSyncBarrier()}.
+     *
+     * @return True if the message is asynchronous.
+     *
+     * @see #setAsynchronous(boolean)
+     * @see MessageQueue#acquireSyncBarrier()
+     * @see MessageQueue#releaseSyncBarrier()
+     *
+     * @hide
+     */
+    public boolean isAsynchronous() {
+        return (flags & FLAG_ASYNCHRONOUS) != 0;
+    }
+
+    /**
+     * Sets whether the message is asynchronous.
+     *
+     * Asynchronous messages represent interrupts or events that do not require global ordering
+     * with represent to synchronous messages.  Asynchronous messages are not subject to
+     * the synchronization barriers introduced by {@link MessageQueue#acquireSyncBarrier()}.
+     *
+     * @param async True if the message is asynchronous.
+     *
+     * @see #isAsynchronous()
+     * @see MessageQueue#acquireSyncBarrier()
+     * @see MessageQueue#releaseSyncBarrier()
+     *
+     * @hide
+     */
+    public void setAsynchronous(boolean async) {
+        if (async) {
+            flags |= FLAG_ASYNCHRONOUS;
+        } else {
+            flags &= ~FLAG_ASYNCHRONOUS;
+        }
+    }
+
     /*package*/ void clearForRecycle() {
         flags = 0;
         what = 0;
diff --git a/core/java/android/os/MessageQueue.java b/core/java/android/os/MessageQueue.java
index a658fc4..11dc124 100644
--- a/core/java/android/os/MessageQueue.java
+++ b/core/java/android/os/MessageQueue.java
@@ -39,6 +39,9 @@ public class MessageQueue {
     // Indicates whether next() is blocked waiting in pollOnce() with a non-zero timeout.
     private boolean mBlocked;
 
+    // Indicates the barrier nesting level.
+    private int mBarrierNestCount;
+
     @SuppressWarnings("unused")
     private int mPtr; // used by native code
     
@@ -93,7 +96,53 @@ public class MessageQueue {
             mIdleHandlers.remove(handler);
         }
     }
-    
+
+    /**
+     * Acquires a synchronization barrier.
+     *
+     * While a synchronization barrier is active, only asynchronous messages are
+     * permitted to execute.  Synchronous messages are retained but are not executed
+     * until the synchronization barrier is released.
+     *
+     * This method is used to immediately postpone execution of all synchronous messages
+     * until a condition is met that releases the barrier.  Asynchronous messages are
+     * exempt from the barrier and continue to be executed as usual.
+     *
+     * This call nests and must be matched by an equal number of calls to
+     * {@link #releaseSyncBarrier}.
+     *
+     * @hide
+     */
+    public final void acquireSyncBarrier() {
+        synchronized (this) {
+            mBarrierNestCount += 1;
+        }
+    }
+
+    /**
+     * Releases a synchronization barrier.
+     *
+     * This class undoes one invocation of {@link #acquireSyncBarrier}.
+     *
+     * @throws IllegalStateException if the barrier is not acquired.
+     *
+     * @hide
+     */
+    public final void releaseSyncBarrier() {
+        synchronized (this) {
+            if (mBarrierNestCount == 0) {
+                throw new IllegalStateException("The message queue synchronization barrier "
+                        + "has not been acquired.");
+            }
+
+            mBarrierNestCount -= 1;
+            if (!mBlocked || mMessages == null) {
+                return;
+            }
+        }
+        nativeWake(mPtr);
+    }
+
     MessageQueue() {
         nativeInit();
     }
@@ -120,28 +169,49 @@ public class MessageQueue {
             synchronized (this) {
                 // Try to retrieve the next message.  Return if found.
                 final long now = SystemClock.uptimeMillis();
-                final Message msg = mMessages;
-                if (msg != null) {
+
+                Message prevMsg = null;
+                Message msg = mMessages;
+                for (;;) {
+                    if (msg == null) {
+                        // No more messages.
+                        nextPollTimeoutMillis = -1;
+                        break;
+                    }
+
                     final long when = msg.when;
-                    if (now >= when) {
+                    if (now < when) {
+                        // Next message is not ready.  Set a timeout to wake up when it is ready.
+                        nextPollTimeoutMillis = (int) Math.min(when - now, Integer.MAX_VALUE);
+                        break;
+                    }
+
+                    if (mBarrierNestCount == 0 || msg.isAsynchronous()) {
+                        // Got a message.
                         mBlocked = false;
-                        mMessages = msg.next;
+                        if (prevMsg != null) {
+                            prevMsg.next = msg.next;
+                        } else {
+                            mMessages = msg.next;
+                        }
                         msg.next = null;
                         if (false) Log.v("MessageQueue", "Returning message: " + msg);
                         msg.markInUse();
                         return msg;
-                    } else {
-                        nextPollTimeoutMillis = (int) Math.min(when - now, Integer.MAX_VALUE);
                     }
-                } else {
-                    nextPollTimeoutMillis = -1;
+
+                    // We have a message that we could return except that it is
+                    // blocked by the sync barrier.  In particular, this means that
+                    // we are not idle yet, so we do not want to run the idle handlers.
+                    prevMsg = msg;
+                    msg = msg.next;
                 }
 
-                // If first time, then get the number of idlers to run.
-                if (pendingIdleHandlerCount < 0) {
+                // If first time idle, then get the number of idlers to run.
+                if (pendingIdleHandlerCount < 0 && msg == mMessages) {
                     pendingIdleHandlerCount = mIdleHandlers.size();
                 }
-                if (pendingIdleHandlerCount == 0) {
+                if (pendingIdleHandlerCount <= 0) {
                     // No idle handlers to run.  Loop and wait some more.
                     mBlocked = true;
                     continue;
@@ -205,10 +275,15 @@ public class MessageQueue {
             //Log.d("MessageQueue", "Enqueing: " + msg);
             Message p = mMessages;
             if (p == null || when == 0 || when < p.when) {
+                // New head, wake up the event queue if blocked.
                 msg.next = p;
                 mMessages = msg;
-                needWake = mBlocked; // new head, might need to wake up
+                needWake = mBlocked;
             } else {
+                // Inserted within the middle of the queue.  Usually we don't have to wake
+                // up the event queue unless the message is asynchronous and it might be
+                // possible for it to be returned out of sequence relative to an earlier
+                // synchronous message at the head of the queue.
                 Message prev = null;
                 while (p != null && p.when <= when) {
                     prev = p;
@@ -216,7 +291,8 @@ public class MessageQueue {
                 }
                 msg.next = prev.next;
                 prev.next = msg;
-                needWake = false; // still waiting on head, no need to wake up
+                needWake = mBlocked && mBarrierNestCount != 0 && msg.isAsynchronous()
+                        && !mMessages.isAsynchronous();
             }
         }
         if (needWake) {