Merge "Dispatch key events to multiple a11y services."

2 files changed, 303 insertions, 217 deletions

diff --git a/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java b/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
index 9f1dc0a96559..3d358ec5e8eb 100644
--- a/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
+++ b/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
@@ -64,21 +64,17 @@ import android.os.UserManager;
 import android.provider.Settings;
 import android.text.TextUtils;
 import android.text.TextUtils.SimpleStringSplitter;
-import android.util.Pools.Pool;
-import android.util.Pools.SimplePool;
 import android.util.Slog;
 import android.util.SparseArray;
 import android.view.Display;
 import android.view.IWindow;
 import android.view.InputDevice;
-import android.view.InputEventConsistencyVerifier;
 import android.view.KeyCharacterMap;
 import android.view.KeyEvent;
 import android.view.MagnificationSpec;
 import android.view.WindowInfo;
 import android.view.WindowManager;
 import android.view.WindowManagerInternal;
-import android.view.WindowManagerPolicy;
 import android.view.accessibility.AccessibilityEvent;
 import android.view.accessibility.AccessibilityInteractionClient;
 import android.view.accessibility.AccessibilityManager;
@@ -146,8 +142,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
     private static final int OWN_PROCESS_ID = android.os.Process.myPid();
 
-    private static final int MAX_POOL_SIZE = 10;
-
     private static final int WINDOW_ID_UNKNOWN = -1;
 
     private static int sIdCounter = 0;
@@ -158,9 +152,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
     private final Object mLock = new Object();
 
-    private final Pool<PendingEvent> mPendingEventPool =
-            new SimplePool<>(MAX_POOL_SIZE);
-
     private final SimpleStringSplitter mStringColonSplitter =
             new SimpleStringSplitter(COMPONENT_NAME_SEPARATOR);
 
@@ -193,6 +184,8 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
     private boolean mHasInputFilter;
 
+    private KeyEventDispatcher mKeyEventDispatcher;
+
     private final Set<ComponentName> mTempComponentNameSet = new HashSet<>();
 
     private final List<AccessibilityServiceInfo> mTempAccessibilityServiceInfoList =
@@ -756,12 +749,11 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
     boolean notifyKeyEvent(KeyEvent event, int policyFlags) {
         synchronized (mLock) {
-            KeyEvent localClone = KeyEvent.obtain(event);
-            boolean handled = notifyKeyEventLocked(localClone, policyFlags, false);
-            if (!handled) {
-                handled = notifyKeyEventLocked(localClone, policyFlags, true);
+            List<Service> boundServices = getCurrentUserStateLocked().mBoundServices;
+            if (boundServices.isEmpty()) {
+                return false;
             }
-            return handled;
+            return getKeyEventDispatcher().notifyKeyEventLocked(event, policyFlags, boundServices);
         }
     }
 
@@ -935,31 +927,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
         return false;
     }
 
-    private boolean notifyKeyEventLocked(KeyEvent event, int policyFlags, boolean isDefault) {
-        // TODO: Now we are giving the key events to the last enabled
-        //       service that can handle them Ideally, the user should
-        //       make the call which service handles key events. However,
-        //       only one service should handle key events to avoid user
-        //       frustration when different behavior is observed from
-        //       different combinations of enabled accessibility services.
-        UserState state = getCurrentUserStateLocked();
-        for (int i = state.mBoundServices.size() - 1; i >= 0; i--) {
-            Service service = state.mBoundServices.get(i);
-            // Key events are handled only by services that declared
-            // this capability and requested to filter key events.
-            if (!service.mRequestFilterKeyEvents ||
-                    (service.mAccessibilityServiceInfo.getCapabilities() & AccessibilityServiceInfo
-                            .CAPABILITY_CAN_REQUEST_FILTER_KEY_EVENTS) == 0) {
-                continue;
-            }
-            if (service.mIsDefault == isDefault) {
-                service.notifyKeyEvent(event, policyFlags);
-                return true;
-            }
-        }
-        return false;
-    }
-
     private void notifyClearAccessibilityCacheLocked() {
         UserState state = getCurrentUserStateLocked();
         for (int i = state.mBoundServices.size() - 1; i >= 0; i--) {
@@ -1754,6 +1721,14 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
         return null;
     }
 
+    private KeyEventDispatcher getKeyEventDispatcher() {
+        if (mKeyEventDispatcher == null) {
+            mKeyEventDispatcher = new KeyEventDispatcher(
+                    mMainHandler, MainHandler.MSG_SEND_KEY_EVENT_TO_INPUT_FILTER, mLock);
+        }
+        return mKeyEventDispatcher;
+    }
+
     @Override
     public void dump(FileDescriptor fd, final PrintWriter pw, String[] args) {
         mSecurityPolicy.enforceCallingPermission(Manifest.permission.DUMP, FUNCTION_DUMP);
@@ -1954,22 +1929,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
         }
     }
 
-    private PendingEvent obtainPendingEventLocked(KeyEvent event, int policyFlags, int sequence) {
-        PendingEvent pendingEvent = mPendingEventPool.acquire();
-        if (pendingEvent == null) {
-            pendingEvent = new PendingEvent();
-        }
-        pendingEvent.event = event;
-        pendingEvent.policyFlags = policyFlags;
-        pendingEvent.sequence = sequence;
-        return pendingEvent;
-    }
-
-    private void recyclePendingEventLocked(PendingEvent pendingEvent) {
-        pendingEvent.clear();
-        mPendingEventPool.release(pendingEvent);
-    }
-
     private int findWindowIdLocked(IBinder token) {
         final int globalIndex = mGlobalWindowTokens.indexOfValue(token);
         if (globalIndex >= 0) {
@@ -2082,8 +2041,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
         final SparseArray<AccessibilityEvent> mPendingEvents =
             new SparseArray<>();
 
-        final KeyEventDispatcher mKeyEventDispatcher = new KeyEventDispatcher();
-
         boolean mWasConnectedAndDied;
 
         // Handler only for dispatching accessibility events since we use event
@@ -2195,7 +2152,7 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
                 return false;
             }
             UserState userState = getUserStateLocked(mUserId);
-            mKeyEventDispatcher.flush();
+            getKeyEventDispatcher().flush(this);
             if (!mIsAutomation) {
                 mContext.unbindService(this);
             } else {
@@ -2212,7 +2169,7 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
         @Override
         public void setOnKeyEventResult(boolean handled, int sequence) {
-            mKeyEventDispatcher.setOnKeyEventResult(handled, sequence);
+            getKeyEventDispatcher().setOnKeyEventResult(this, handled, sequence);
         }
 
         @Override
@@ -2926,7 +2883,7 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
                     return;
                 }
                 mWasConnectedAndDied = true;
-                mKeyEventDispatcher.flush();
+                getKeyEventDispatcher().flush(this);
                 UserState userState = getUserStateLocked(mUserId);
                 // The death recipient is unregistered in removeServiceLocked
                 removeServiceLocked(this, userState);
@@ -3035,11 +2992,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
                     gestureId, 0).sendToTarget();
         }
 
-        public void notifyKeyEvent(KeyEvent event, int policyFlags) {
-            mInvocationHandler.obtainMessage(InvocationHandler.MSG_ON_KEY_EVENT,
-                    policyFlags, 0, event).sendToTarget();
-        }
-
         public void notifyClearAccessibilityNodeInfoCache() {
             mInvocationHandler.sendEmptyMessage(
                     InvocationHandler.MSG_CLEAR_ACCESSIBILITY_CACHE);
@@ -3084,10 +3036,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
             }
         }
 
-        private void notifyKeyEventInternal(KeyEvent event, int policyFlags) {
-            mKeyEventDispatcher.notifyKeyEvent(event, policyFlags);
-        }
-
         private void notifyClearAccessibilityCacheInternal() {
             final IAccessibilityServiceClient listener;
             synchronized (mLock) {
@@ -3205,9 +3153,7 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
 
         private final class InvocationHandler extends Handler {
             public static final int MSG_ON_GESTURE = 1;
-            public static final int MSG_ON_KEY_EVENT = 2;
-            public static final int MSG_CLEAR_ACCESSIBILITY_CACHE = 3;
-            public static final int MSG_ON_KEY_EVENT_TIMEOUT = 4;
+            public static final int MSG_CLEAR_ACCESSIBILITY_CACHE = 2;
 
             private static final int MSG_ON_MAGNIFICATION_CHANGED = 5;
 
@@ -3226,21 +3172,10 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
                         notifyGestureInternal(gestureId);
                     } break;
 
-                    case MSG_ON_KEY_EVENT: {
-                        KeyEvent event = (KeyEvent) message.obj;
-                        final int policyFlags = message.arg1;
-                        notifyKeyEventInternal(event, policyFlags);
-                    } break;
-
                     case MSG_CLEAR_ACCESSIBILITY_CACHE: {
                         notifyClearAccessibilityCacheInternal();
                     } break;
 
-                    case MSG_ON_KEY_EVENT_TIMEOUT: {
-                        PendingEvent eventState = (PendingEvent) message.obj;
-                        setOnKeyEventResult(false, eventState.sequence);
-                    } break;
-
                     case MSG_ON_MAGNIFICATION_CHANGED: {
                         final SomeArgs args = (SomeArgs) message.obj;
                         final Region region = (Region) args.arg1;
@@ -3278,140 +3213,6 @@ public class AccessibilityManagerService extends IAccessibilityManager.Stub {
             }
         }
 
-        private final class KeyEventDispatcher {
-
-            private static final long ON_KEY_EVENT_TIMEOUT_MILLIS = 500;
-
-            private PendingEvent mPendingEvents;
-
-            private final InputEventConsistencyVerifier mSentEventsVerifier =
-                    InputEventConsistencyVerifier.isInstrumentationEnabled()
-                            ? new InputEventConsistencyVerifier(
-                                    this, 0, KeyEventDispatcher.class.getSimpleName()) : null;
-
-            public void notifyKeyEvent(KeyEvent event, int policyFlags) {
-                final PendingEvent pendingEvent;
-
-                synchronized (mLock) {
-                    pendingEvent = addPendingEventLocked(event, policyFlags);
-                }
-
-                Message message = mInvocationHandler.obtainMessage(
-                        InvocationHandler.MSG_ON_KEY_EVENT_TIMEOUT, pendingEvent);
-                mInvocationHandler.sendMessageDelayed(message, ON_KEY_EVENT_TIMEOUT_MILLIS);
-
-                try {
-                    // Accessibility services are exclusively not in the system
-                    // process, therefore no need to clone the motion event to
-                    // prevent tampering. It will be cloned in the IPC call.
-                    mServiceInterface.onKeyEvent(pendingEvent.event, pendingEvent.sequence);
-                } catch (RemoteException re) {
-                    setOnKeyEventResult(false, pendingEvent.sequence);
-                }
-            }
-
-            public void setOnKeyEventResult(boolean handled, int sequence) {
-                synchronized (mLock) {
-                    PendingEvent pendingEvent = removePendingEventLocked(sequence);
-                    if (pendingEvent != null) {
-                        mInvocationHandler.removeMessages(
-                                InvocationHandler.MSG_ON_KEY_EVENT_TIMEOUT,
-                                pendingEvent);
-                        pendingEvent.handled = handled;
-                        finishPendingEventLocked(pendingEvent);
-                    }
-                }
-            }
-
-            public void flush() {
-                synchronized (mLock) {
-                    cancelAllPendingEventsLocked();
-                    if (mSentEventsVerifier != null) {
-                        mSentEventsVerifier.reset();
-                    }
-                }
-            }
-
-            private PendingEvent addPendingEventLocked(KeyEvent event, int policyFlags) {
-                final int sequence = event.getSequenceNumber();
-                PendingEvent pendingEvent = obtainPendingEventLocked(event, policyFlags, sequence);
-                pendingEvent.next = mPendingEvents;
-                mPendingEvents = pendingEvent;
-                return pendingEvent;
-            }
-
-            private PendingEvent removePendingEventLocked(int sequence) {
-                PendingEvent previous = null;
-                PendingEvent current = mPendingEvents;
-
-                while (current != null) {
-                    if (current.sequence == sequence) {
-                        if (previous != null) {
-                            previous.next = current.next;
-                        } else {
-                            mPendingEvents = current.next;
-                        }
-                        current.next = null;
-                        return current;
-                    }
-                    previous = current;
-                    current = current.next;
-                }
-                return null;
-            }
-
-            private void finishPendingEventLocked(PendingEvent pendingEvent) {
-                if (!pendingEvent.handled) {
-                    sendKeyEventToInputFilter(pendingEvent.event, pendingEvent.policyFlags);
-                }
-                // Nullify the event since we do not want it to be
-                // recycled yet. It will be sent to the input filter.
-                pendingEvent.event = null;
-                recyclePendingEventLocked(pendingEvent);
-            }
-
-            private void sendKeyEventToInputFilter(KeyEvent event, int policyFlags) {
-                if (DEBUG) {
-                    Slog.i(LOG_TAG, "Injecting event: " + event);
-                }
-                if (mSentEventsVerifier != null) {
-                    mSentEventsVerifier.onKeyEvent(event, 0);
-                }
-                policyFlags |= WindowManagerPolicy.FLAG_PASS_TO_USER;
-                mMainHandler.obtainMessage(MainHandler.MSG_SEND_KEY_EVENT_TO_INPUT_FILTER,
-                        policyFlags, 0, event).sendToTarget();
-            }
-
-            private void cancelAllPendingEventsLocked() {
-                while (mPendingEvents != null) {
-                    PendingEvent pendingEvent = removePendingEventLocked(mPendingEvents.sequence);
-                    pendingEvent.handled = false;
-                    mInvocationHandler.removeMessages(InvocationHandler.MSG_ON_KEY_EVENT_TIMEOUT,
-                            pendingEvent);
-                    finishPendingEventLocked(pendingEvent);
-                }
-            }
-        }
-    }
-
-    private static final class PendingEvent {
-        PendingEvent next;
-
-        KeyEvent event;
-        int policyFlags;
-        int sequence;
-        boolean handled;
-
-        public void clear() {
-            if (event != null) {
-                event.recycle();
-                event = null;
-            }
-            next = null;
-            policyFlags = 0;
-            sequence = 0;
-            handled = false;
-        }
     }
 
     final class WindowsForAccessibilityCallback implements
diff --git a/services/accessibility/java/com/android/server/accessibility/KeyEventDispatcher.java b/services/accessibility/java/com/android/server/accessibility/KeyEventDispatcher.java
new file mode 100644
index 000000000000..34695654c6f7
--- /dev/null
+++ b/services/accessibility/java/com/android/server/accessibility/KeyEventDispatcher.java
@@ -0,0 +1,285 @@
+/*
+ ** Copyright 2015, The Android Open Source Project
+ **
+ ** Licensed under the Apache License, Version 2.0 (the "License");
+ ** you may not use this file except in compliance with the License.
+ ** You may obtain a copy of the License at
+ **
+ **     http://www.apache.org/licenses/LICENSE-2.0
+ **
+ ** Unless required by applicable law or agreed to in writing, software
+ ** distributed under the License is distributed on an "AS IS" BASIS,
+ ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ ** See the License for the specific language governing permissions and
+ ** limitations under the License.
+ */
+
+package com.android.server.accessibility;
+
+import android.accessibilityservice.AccessibilityServiceInfo;
+import android.os.Handler;
+import android.os.Message;
+import android.os.RemoteException;
+import android.util.ArrayMap;
+import android.util.Pools;
+import android.util.Pools.Pool;
+import android.util.Slog;
+import android.view.InputEventConsistencyVerifier;
+import android.view.KeyEvent;
+import android.view.WindowManagerPolicy;
+
+import com.android.server.accessibility.AccessibilityManagerService.Service;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Dispatcher to send KeyEvents to all accessibility services that are able to process them.
+ * Events that are handled by one or more services are consumed. Events that are not processed
+ * by any service (or time out before a service reports them as handled) are passed along to
+ * the rest of the system.
+ *
+ * The class assumes that services report their return values in order, which is valid because
+ * they process each call to {@code AccessibilityService.onKeyEvent} on a single thread, and so
+ * don't see the N+1th event until they have processed the Nth event.
+ */
+public class KeyEventDispatcher {
+    // Debugging
+    private static final String LOG_TAG = "KeyEventDispatcher";
+    private static final boolean DEBUG = false;
+    /* KeyEvents must be processed in this time interval */
+    private static final long ON_KEY_EVENT_TIMEOUT_MILLIS = 500;
+    private static final int MSG_ON_KEY_EVENT_TIMEOUT = 1;
+    private static final int MAX_POOL_SIZE = 10;
+
+    private final Pool<PendingKeyEvent> mPendingEventPool = new Pools.SimplePool<>(MAX_POOL_SIZE);
+    private final Object mLock;
+
+    /*
+     * Track events sent to each service. If a KeyEvent is to be sent to at least one service,
+     * a corresponding PendingKeyEvent is created for it. This PendingKeyEvent is placed in
+     * the list for each service its KeyEvent is sent to. It is removed from the list when
+     * the service calls setOnKeyEventResult, or when we time out waiting for the service to
+     * respond.
+     */
+    private final Map<Service, ArrayList<PendingKeyEvent>> mPendingEventsMap = new ArrayMap<>();
+
+    private final InputEventConsistencyVerifier mSentEventsVerifier;
+    private final Handler mHandlerToSendKeyEventsToInputFilter;
+    private final int mMessageTypeForSendKeyEvent;
+    private final Handler mKeyEventTimeoutHandler;
+
+    /**
+     * @param handlerToSendKeyEventsToInputFilter The handler to which to post {@code KeyEvent}s
+     * that have not been handled by any accessibility service.
+     * @param messageTypeForSendKeyEvent The field to populate {@code message.what} for the
+     * message that carries a {@code KeyEvent} to be sent to the input filter
+     * @param lock The lock used for all synchronization in this package. This lock must be held
+     * when calling {@code notifyKeyEventLocked}
+     */
+    public KeyEventDispatcher(Handler handlerToSendKeyEventsToInputFilter,
+                              int messageTypeForSendKeyEvent, Object lock) {
+        if (InputEventConsistencyVerifier.isInstrumentationEnabled()) {
+            mSentEventsVerifier = new InputEventConsistencyVerifier(
+                    this, 0, KeyEventDispatcher.class.getSimpleName());
+        } else {
+            mSentEventsVerifier = null;
+        }
+        mHandlerToSendKeyEventsToInputFilter = handlerToSendKeyEventsToInputFilter;
+        mMessageTypeForSendKeyEvent = messageTypeForSendKeyEvent;
+        mKeyEventTimeoutHandler =
+                new Handler(mHandlerToSendKeyEventsToInputFilter.getLooper(), new Callback());
+        mLock = lock;
+    }
+
+    /**
+     * Notify that a new KeyEvent is available to accessibility services. Must be called with the
+     * lock used to construct this object held. The boundServices list must also be protected
+     * by a lock.
+     *
+     * @param event The new key event
+     * @param policyFlags Flags for the event
+     * @param boundServices A list of currently bound AccessibilityServices
+     *
+     * @return {@code true} if the event was passed to at least one AccessibilityService,
+     * {@code false} otherwise.
+     */
+    // TODO: The locking policy for boundServices needs some thought.
+    public boolean notifyKeyEventLocked(
+            KeyEvent event, int policyFlags, List<Service> boundServices) {
+        PendingKeyEvent pendingKeyEvent = null;
+        KeyEvent localClone = KeyEvent.obtain(event);
+        for (int i = 0; i < boundServices.size(); i++) {
+            Service service = boundServices.get(i);
+            // Key events are handled only by services that declared
+            // this capability and requested to filter key events.
+            if (!service.mRequestFilterKeyEvents) {
+                continue;
+            }
+            int filterKeyEventBit = service.mAccessibilityServiceInfo.getCapabilities()
+                    & AccessibilityServiceInfo.CAPABILITY_CAN_REQUEST_FILTER_KEY_EVENTS;
+            if (filterKeyEventBit == 0) {
+                continue;
+            }
+
+            try {
+                // The event will be cloned in the IPC call, so it doesn't need to be here.
+                service.mServiceInterface.onKeyEvent(localClone, localClone.getSequenceNumber());
+            } catch (RemoteException re) {
+                continue;
+            }
+
+            if (pendingKeyEvent == null) {
+                pendingKeyEvent = obtainPendingEventLocked(localClone, policyFlags);
+            }
+            ArrayList<PendingKeyEvent> pendingEventList = mPendingEventsMap.get(service);
+            if (pendingEventList == null) {
+                pendingEventList = new ArrayList<>();
+                mPendingEventsMap.put(service, pendingEventList);
+            }
+            pendingEventList.add(pendingKeyEvent);
+            pendingKeyEvent.referenceCount++;
+        }
+
+        if (pendingKeyEvent == null) {
+            localClone.recycle();
+            return false;
+        }
+
+        Message message = mKeyEventTimeoutHandler.obtainMessage(
+                MSG_ON_KEY_EVENT_TIMEOUT, pendingKeyEvent);
+        mKeyEventTimeoutHandler.sendMessageDelayed(message, ON_KEY_EVENT_TIMEOUT_MILLIS);
+        return true;
+    }
+
+    /**
+     * Set the result from onKeyEvent from one service.
+     *
+     * @param service The service setting the result
+     * @param handled {@code true} if the service handled the {@code KeyEvent}
+     * @param sequence The sequence number of the {@code KeyEvent}
+     */
+    public void setOnKeyEventResult(Service service, boolean handled, int sequence) {
+        synchronized (mLock) {
+            PendingKeyEvent pendingEvent =
+                    removeEventFromListLocked(mPendingEventsMap.get(service), sequence);
+            if (pendingEvent != null) {
+                pendingEvent.handled |= handled;
+                removeReferenceToPendingEventLocked(pendingEvent);
+            }
+        }
+    }
+
+    /**
+     * Flush all pending key events for a service, treating all of them as unhandled
+     *
+     * @param service The service for which to flush events
+     */
+    public void flush(Service service) {
+        synchronized (mLock) {
+            List<PendingKeyEvent> pendingEvents = mPendingEventsMap.get(service);
+            if (pendingEvents != null) {
+                for (int i = 0; i < pendingEvents.size(); i++) {
+                    PendingKeyEvent pendingEvent = pendingEvents.get(i);
+                    removeReferenceToPendingEventLocked(pendingEvent);
+                }
+                mPendingEventsMap.remove(service);
+            }
+        }
+    }
+
+    private PendingKeyEvent obtainPendingEventLocked(KeyEvent event, int policyFlags) {
+        PendingKeyEvent pendingEvent = mPendingEventPool.acquire();
+        if (pendingEvent == null) {
+            pendingEvent = new PendingKeyEvent();
+        }
+        pendingEvent.event = event;
+        pendingEvent.policyFlags = policyFlags;
+        pendingEvent.referenceCount = 0;
+        pendingEvent.handled = false;
+        return pendingEvent;
+    }
+
+    private static PendingKeyEvent removeEventFromListLocked(
+            List<PendingKeyEvent> listOfEvents, int sequence) {
+        /* In normal operation, the event should be first */
+        for (int i = 0; i < listOfEvents.size(); i++) {
+            PendingKeyEvent pendingKeyEvent = listOfEvents.get(i);
+            if (pendingKeyEvent.event.getSequenceNumber() == sequence) {
+                    /*
+                     * Removing the first element of the ArrayList can be slow if there are a lot
+                     * of events backed up, but for a handful of events it's better than incurring
+                     * the fixed overhead of LinkedList. An ArrayList optimized for removing the
+                     * first element (by treating the underlying array as a circular buffer) would
+                     * be ideal.
+                     */
+                listOfEvents.remove(pendingKeyEvent);
+                return pendingKeyEvent;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * @param pendingEvent The event whose reference count should be decreased
+     * @return {@code true} if the event was release, {@code false} if not.
+     */
+    private boolean removeReferenceToPendingEventLocked(PendingKeyEvent pendingEvent) {
+        if (--pendingEvent.referenceCount > 0) {
+            return false;
+        }
+        mKeyEventTimeoutHandler.removeMessages(MSG_ON_KEY_EVENT_TIMEOUT, pendingEvent);
+        if (!pendingEvent.handled) {
+                /* Pass event to input filter */
+            if (DEBUG) {
+                Slog.i(LOG_TAG, "Injecting event: " + pendingEvent.event);
+            }
+            if (mSentEventsVerifier != null) {
+                mSentEventsVerifier.onKeyEvent(pendingEvent.event, 0);
+            }
+            int policyFlags = pendingEvent.policyFlags | WindowManagerPolicy.FLAG_PASS_TO_USER;
+            mHandlerToSendKeyEventsToInputFilter
+                    .obtainMessage(mMessageTypeForSendKeyEvent, policyFlags, 0, pendingEvent.event)
+                            .sendToTarget();
+        } else {
+            pendingEvent.event.recycle();
+        }
+        mPendingEventPool.release(pendingEvent);
+        return true;
+    }
+
+    private static final class PendingKeyEvent {
+        /* Event and policyFlag provided in notifyKeyEventLocked */
+        KeyEvent event;
+        int policyFlags;
+        /*
+         * The referenceCount optimizes the process of determining the number of services
+         * still holding a KeyEvent. It must be equal to the number of times the PendingEvent
+         * appears in mPendingEventsMap, or PendingEvents will leak.
+         */
+        int referenceCount;
+        /* Whether or not at least one service had handled this event */
+        boolean handled;
+    }
+
+    private class Callback implements Handler.Callback {
+        @Override
+        public boolean handleMessage(Message message) {
+            if (message.what != MSG_ON_KEY_EVENT_TIMEOUT) {
+                throw new IllegalArgumentException("Unknown message: " + message.what);
+            }
+            PendingKeyEvent pendingKeyEvent = (PendingKeyEvent) message.obj;
+            synchronized (mLock) {
+                for (ArrayList<PendingKeyEvent> listForService : mPendingEventsMap.values()) {
+                    if (listForService.remove(pendingKeyEvent)) {
+                        if(removeReferenceToPendingEventLocked(pendingKeyEvent)) {
+                            break;
+                        }
+                    }
+                }
+            }
+            return true;
+        }
+    }
+}