Merge "SF: Fix a scheduler related mock leak"
diff --git a/cmds/dumpstate/dumpstate.cpp b/cmds/dumpstate/dumpstate.cpp
index 7443cb3..eb2dad5 100644
--- a/cmds/dumpstate/dumpstate.cpp
+++ b/cmds/dumpstate/dumpstate.cpp
@@ -1546,6 +1546,8 @@
 static void DumpstateRadioCommon() {
     DumpIpTablesAsRoot();
 
+    ds.AddDir(LOGPERSIST_DATA_DIR, false);
+
     if (!DropRootUser()) {
         return;
     }
@@ -1556,6 +1558,7 @@
     DoKmsg();
     DumpIpAddrAndRules();
     dump_route_tables();
+    DumpHals();
 
     RunDumpsys("NETWORK DIAGNOSTICS", {"connectivity", "--diag"},
                CommandOptions::WithTimeout(10).Build());
@@ -1625,8 +1628,6 @@
     RunDumpsys("DUMPSYS", {"wifi"}, CommandOptions::WithTimeout(90).Build(),
                SEC_TO_MSEC(10));
 
-    DumpHals();
-
     printf("========================================================\n");
     printf("== dumpstate: done (id %d)\n", ds.id_);
     printf("========================================================\n");
diff --git a/include/android/bitmap.h b/include/android/bitmap.h
index 2def64d..6fba0ac 100644
--- a/include/android/bitmap.h
+++ b/include/android/bitmap.h
@@ -60,6 +60,8 @@
     ANDROID_BITMAP_FORMAT_RGBA_4444 = 7,
     /** Alpha: 8 bits. */
     ANDROID_BITMAP_FORMAT_A_8       = 8,
+    /** Each component is stored as a half float. **/
+    ANDROID_BITMAP_FORMAT_RGBA_F16  = 9,
 };
 
 /** Bitmap info, see AndroidBitmap_getInfo(). */
diff --git a/libs/cputimeinstate/cputimeinstate.cpp b/libs/cputimeinstate/cputimeinstate.cpp
index 0e68e62..4c8d52e 100644
--- a/libs/cputimeinstate/cputimeinstate.cpp
+++ b/libs/cputimeinstate/cputimeinstate.cpp
@@ -22,6 +22,7 @@
 #include <dirent.h>
 #include <errno.h>
 #include <inttypes.h>
+#include <sys/sysinfo.h>
 
 #include <mutex>
 #include <optional>
@@ -48,6 +49,7 @@
 static std::mutex gInitializedMutex;
 static bool gInitialized = false;
 static uint32_t gNPolicies = 0;
+static uint32_t gNCpus = 0;
 static std::vector<std::vector<uint32_t>> gPolicyFreqs;
 static std::vector<std::vector<uint32_t>> gPolicyCpus;
 static std::set<uint32_t> gAllFreqs;
@@ -85,6 +87,8 @@
     std::lock_guard<std::mutex> guard(gInitializedMutex);
     if (gInitialized) return true;
 
+    gNCpus = get_nprocs_conf();
+
     struct dirent **dirlist;
     const char basepath[] = "/sys/devices/system/cpu/cpufreq";
     int ret = scandir(basepath, &dirlist, isPolicyFile, comparePolicyFiles);
@@ -140,6 +144,32 @@
 // This function should *not* be called while tracking is already active; doing so is unnecessary
 // and can lead to accounting errors.
 bool startTrackingUidCpuFreqTimes() {
+    if (!initGlobals()) return false;
+
+    unique_fd fd(bpf_obj_get(BPF_FS_PATH "map_time_in_state_cpu_policy_map"));
+    if (fd < 0) return false;
+
+    for (uint32_t i = 0; i < gPolicyCpus.size(); ++i) {
+        for (auto &cpu : gPolicyCpus[i]) {
+            if (writeToMapEntry(fd, &cpu, &i, BPF_ANY)) return false;
+        }
+    }
+
+    unique_fd fd2(bpf_obj_get(BPF_FS_PATH "map_time_in_state_freq_to_idx_map"));
+    if (fd2 < 0) return false;
+    freq_idx_key_t key;
+    for (uint32_t i = 0; i < gNPolicies; ++i) {
+        key.policy = i;
+        for (uint32_t j = 0; j < gPolicyFreqs[i].size(); ++j) {
+            key.freq = gPolicyFreqs[i][j];
+            // Start indexes at 1 so that uninitialized state is distinguishable from lowest freq.
+            // The uid_times map still uses 0-based indexes, and the sched_switch program handles
+            // conversion between them, so this does not affect our map reading code.
+            uint32_t idx = j + 1;
+            if (writeToMapEntry(fd2, &key, &idx, BPF_ANY)) return false;
+        }
+    }
+
     return attachTracepointProgram("sched", "sched_switch") &&
             attachTracepointProgram("power", "cpu_frequency");
 }
@@ -151,27 +181,33 @@
 // where ti_j is the ns that uid spent running on the ith cluster at that cluster's jth lowest freq.
 std::optional<std::vector<std::vector<uint64_t>>> getUidCpuFreqTimes(uint32_t uid) {
     if (!gInitialized && !initGlobals()) return {};
-    time_key_t key = {.uid = uid, .freq = 0};
 
-    std::vector<std::vector<uint64_t>> out(gNPolicies);
-    std::vector<uint32_t> idxs(gNPolicies, 0);
+    std::vector<std::vector<uint64_t>> out;
+    uint32_t maxFreqCount = 0;
+    for (const auto &freqList : gPolicyFreqs) {
+        if (freqList.size() > maxFreqCount) maxFreqCount = freqList.size();
+        out.emplace_back(freqList.size(), 0);
+    }
 
-    val_t value;
-    for (uint32_t freq : gAllFreqs) {
-        key.freq = freq;
-        int ret = findMapEntry(gMapFd, &key, &value);
-        if (ret) {
-            if (errno == ENOENT)
-                memset(&value.ar, 0, sizeof(value.ar));
-            else
-                return {};
+    std::vector<val_t> vals(gNCpus);
+    time_key_t key = {.uid = uid};
+    for (uint32_t i = 0; i <= (maxFreqCount - 1) / FREQS_PER_ENTRY; ++i) {
+        key.bucket = i;
+        if (findMapEntry(gMapFd, &key, vals.data())) {
+            if (errno != ENOENT) return {};
+            continue;
         }
-        for (uint32_t i = 0; i < gNPolicies; ++i) {
-            if (idxs[i] == gPolicyFreqs[i].size() || freq != gPolicyFreqs[i][idxs[i]]) continue;
-            uint64_t time = 0;
-            for (uint32_t cpu : gPolicyCpus[i]) time += value.ar[cpu];
-            idxs[i] += 1;
-            out[i].emplace_back(time);
+
+        auto offset = i * FREQS_PER_ENTRY;
+        auto nextOffset = (i + 1) * FREQS_PER_ENTRY;
+        for (uint32_t j = 0; j < gNPolicies; ++j) {
+            if (offset >= gPolicyFreqs[j].size()) continue;
+            auto begin = out[j].begin() + offset;
+            auto end = nextOffset < gPolicyFreqs[j].size() ? begin + FREQS_PER_ENTRY : out[j].end();
+
+            for (const auto &cpu : gPolicyCpus[j]) {
+                std::transform(begin, end, std::begin(vals[cpu].ar), begin, std::plus<uint64_t>());
+            }
         }
     }
 
@@ -187,47 +223,53 @@
 std::optional<std::unordered_map<uint32_t, std::vector<std::vector<uint64_t>>>>
 getUidsCpuFreqTimes() {
     if (!gInitialized && !initGlobals()) return {};
-
-    int fd = bpf_obj_get(BPF_FS_PATH "map_time_in_state_uid_times_map");
-    if (fd < 0) return {};
-    BpfMap<time_key_t, val_t> m(fd);
-
-    std::vector<std::unordered_map<uint32_t, uint32_t>> policyFreqIdxs;
-    for (uint32_t i = 0; i < gNPolicies; ++i) {
-        std::unordered_map<uint32_t, uint32_t> freqIdxs;
-        for (size_t j = 0; j < gPolicyFreqs[i].size(); ++j) freqIdxs[gPolicyFreqs[i][j]] = j;
-        policyFreqIdxs.emplace_back(freqIdxs);
-    }
+    time_key_t key, prevKey;
     std::unordered_map<uint32_t, std::vector<std::vector<uint64_t>>> map;
-    auto fn = [&map, &policyFreqIdxs](const time_key_t &key, const val_t &val,
-                                             const BpfMap<time_key_t, val_t> &) {
-        if (map.find(key.uid) == map.end()) {
-            map[key.uid].resize(gNPolicies);
-            for (uint32_t i = 0; i < gNPolicies; ++i) {
-                map[key.uid][i].resize(gPolicyFreqs[i].size(), 0);
-            }
-        }
+    if (getFirstMapKey(gMapFd, &key)) {
+        if (errno == ENOENT) return map;
+        return std::nullopt;
+    }
 
-        for (size_t policy = 0; policy < gNPolicies; ++policy) {
-            for (const auto &cpu : gPolicyCpus[policy]) {
-                auto freqIdx = policyFreqIdxs[policy][key.freq];
-                map[key.uid][policy][freqIdx] += val.ar[cpu];
+    std::vector<std::vector<uint64_t>> mapFormat;
+    for (const auto &freqList : gPolicyFreqs) mapFormat.emplace_back(freqList.size(), 0);
+
+    std::vector<val_t> vals(gNCpus);
+    do {
+        if (findMapEntry(gMapFd, &key, vals.data())) return {};
+        if (map.find(key.uid) == map.end()) map.emplace(key.uid, mapFormat);
+
+        auto offset = key.bucket * FREQS_PER_ENTRY;
+        auto nextOffset = (key.bucket + 1) * FREQS_PER_ENTRY;
+        for (uint32_t i = 0; i < gNPolicies; ++i) {
+            if (offset >= gPolicyFreqs[i].size()) continue;
+            auto begin = map[key.uid][i].begin() + offset;
+            auto end = nextOffset < gPolicyFreqs[i].size() ? begin + FREQS_PER_ENTRY :
+                map[key.uid][i].end();
+            for (const auto &cpu : gPolicyCpus[i]) {
+                std::transform(begin, end, std::begin(vals[cpu].ar), begin, std::plus<uint64_t>());
             }
         }
-        return android::netdutils::status::ok;
-    };
-    if (isOk(m.iterateWithValue(fn))) return map;
-    return {};
+        prevKey = key;
+    } while (!getNextMapKey(gMapFd, &prevKey, &key));
+    if (errno != ENOENT) return {};
+    return map;
 }
 
 // Clear all time in state data for a given uid. Returns false on error, true otherwise.
 bool clearUidCpuFreqTimes(uint32_t uid) {
     if (!gInitialized && !initGlobals()) return false;
-    time_key_t key = {.uid = uid, .freq = 0};
 
-    std::vector<uint32_t> idxs(gNPolicies, 0);
-    for (auto freq : gAllFreqs) {
-        key.freq = freq;
+    time_key_t key = {.uid = uid};
+
+    uint32_t maxFreqCount = 0;
+    for (const auto &freqList : gPolicyFreqs) {
+        if (freqList.size() > maxFreqCount) maxFreqCount = freqList.size();
+    }
+
+    val_t zeros = {0};
+    std::vector<val_t> vals(gNCpus, zeros);
+    for (key.bucket = 0; key.bucket <= (maxFreqCount - 1) / FREQS_PER_ENTRY; ++key.bucket) {
+        if (writeToMapEntry(gMapFd, &key, vals.data(), BPF_EXIST) && errno != ENOENT) return false;
         if (deleteMapEntry(gMapFd, &key) && errno != ENOENT) return false;
     }
     return true;
diff --git a/libs/cputimeinstate/testtimeinstate.cpp b/libs/cputimeinstate/testtimeinstate.cpp
index 6347de1..39007e4 100644
--- a/libs/cputimeinstate/testtimeinstate.cpp
+++ b/libs/cputimeinstate/testtimeinstate.cpp
@@ -126,10 +126,10 @@
         ASSERT_GE(fd, 0);
         time_key_t k;
         ASSERT_FALSE(getFirstMapKey(fd, &k));
-        val_t val;
-        ASSERT_FALSE(findMapEntry(fd, &k, &val));
+        std::vector<val_t> vals(get_nprocs_conf());
+        ASSERT_FALSE(findMapEntry(fd, &k, vals.data()));
         k.uid = uid;
-        ASSERT_FALSE(writeToMapEntry(fd, &k, &val, BPF_NOEXIST));
+        ASSERT_FALSE(writeToMapEntry(fd, &k, vals.data(), BPF_NOEXIST));
     }
     auto times = getUidCpuFreqTimes(uid);
     ASSERT_TRUE(times.has_value());
diff --git a/libs/cputimeinstate/timeinstate.h b/libs/cputimeinstate/timeinstate.h
index cf66ae7..41d0af0 100644
--- a/libs/cputimeinstate/timeinstate.h
+++ b/libs/cputimeinstate/timeinstate.h
@@ -18,11 +18,18 @@
 
 #define BPF_FS_PATH "/sys/fs/bpf/"
 
+#define FREQS_PER_ENTRY 32
+
 struct time_key_t {
     uint32_t uid;
-    uint32_t freq;
+    uint32_t bucket;
 };
 
 struct val_t {
-    uint64_t ar[100];
+    uint64_t ar[FREQS_PER_ENTRY];
+};
+
+struct freq_idx_key_t {
+    uint32_t policy;
+    uint32_t freq;
 };
diff --git a/services/inputflinger/InputDispatcher.cpp b/services/inputflinger/InputDispatcher.cpp
index 32cb04e..1eb979e 100644
--- a/services/inputflinger/InputDispatcher.cpp
+++ b/services/inputflinger/InputDispatcher.cpp
@@ -48,10 +48,11 @@
 #include <errno.h>
 #include <inttypes.h>
 #include <limits.h>
-#include <sstream>
 #include <stddef.h>
 #include <time.h>
 #include <unistd.h>
+#include <queue>
+#include <sstream>
 
 #include <android-base/chrono_utils.h>
 #include <android-base/stringprintf.h>
@@ -358,7 +359,7 @@
     // Ready to start a new event.
     // If we don't already have a pending event, go grab one.
     if (! mPendingEvent) {
-        if (mInboundQueue.isEmpty()) {
+        if (mInboundQueue.empty()) {
             if (isAppSwitchDue) {
                 // The inbound queue is empty so the app switch key we were waiting
                 // for will never arrive.  Stop waiting for it.
@@ -383,7 +384,8 @@
             }
         } else {
             // Inbound queue has at least one entry.
-            mPendingEvent = mInboundQueue.dequeueAtHead();
+            mPendingEvent = mInboundQueue.front();
+            mInboundQueue.pop_front();
             traceInboundQueueLengthLocked();
         }
 
@@ -483,8 +485,8 @@
 }
 
 bool InputDispatcher::enqueueInboundEventLocked(EventEntry* entry) {
-    bool needWake = mInboundQueue.isEmpty();
-    mInboundQueue.enqueueAtTail(entry);
+    bool needWake = mInboundQueue.empty();
+    mInboundQueue.push_back(entry);
     traceInboundQueueLengthLocked();
 
     switch (entry->type) {
@@ -544,9 +546,10 @@
 
 void InputDispatcher::addRecentEventLocked(EventEntry* entry) {
     entry->refCount += 1;
-    mRecentQueue.enqueueAtTail(entry);
-    if (mRecentQueue.count() > RECENT_QUEUE_MAX_SIZE) {
-        mRecentQueue.dequeueAtHead()->release();
+    mRecentQueue.push_back(entry);
+    if (mRecentQueue.size() > RECENT_QUEUE_MAX_SIZE) {
+        mRecentQueue.front()->release();
+        mRecentQueue.pop_front();
     }
 }
 
@@ -703,35 +706,33 @@
 }
 
 bool InputDispatcher::haveCommandsLocked() const {
-    return !mCommandQueue.isEmpty();
+    return !mCommandQueue.empty();
 }
 
 bool InputDispatcher::runCommandsLockedInterruptible() {
-    if (mCommandQueue.isEmpty()) {
+    if (mCommandQueue.empty()) {
         return false;
     }
 
     do {
-        CommandEntry* commandEntry = mCommandQueue.dequeueAtHead();
-
+        std::unique_ptr<CommandEntry> commandEntry = std::move(mCommandQueue.front());
+        mCommandQueue.pop_front();
         Command command = commandEntry->command;
-        command(*this, commandEntry); // commands are implicitly 'LockedInterruptible'
+        command(*this, commandEntry.get()); // commands are implicitly 'LockedInterruptible'
 
         commandEntry->connection.clear();
-        delete commandEntry;
-    } while (! mCommandQueue.isEmpty());
+    } while (!mCommandQueue.empty());
     return true;
 }
 
-InputDispatcher::CommandEntry* InputDispatcher::postCommandLocked(Command command) {
-    CommandEntry* commandEntry = new CommandEntry(command);
-    mCommandQueue.enqueueAtTail(commandEntry);
-    return commandEntry;
+void InputDispatcher::postCommandLocked(std::unique_ptr<CommandEntry> commandEntry) {
+    mCommandQueue.push_back(std::move(commandEntry));
 }
 
 void InputDispatcher::drainInboundQueueLocked() {
-    while (! mInboundQueue.isEmpty()) {
-        EventEntry* entry = mInboundQueue.dequeueAtHead();
+    while (!mInboundQueue.empty()) {
+        EventEntry* entry = mInboundQueue.front();
+        mInboundQueue.pop_front();
         releaseInboundEventLocked(entry);
     }
     traceInboundQueueLengthLocked();
@@ -809,9 +810,10 @@
     resetKeyRepeatLocked();
 
     // Enqueue a command to run outside the lock to tell the policy that the configuration changed.
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doNotifyConfigurationChangedLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
+            &InputDispatcher::doNotifyConfigurationChangedLockedInterruptible);
     commandEntry->eventTime = entry->eventTime;
+    postCommandLocked(std::move(commandEntry));
     return true;
 }
 
@@ -883,7 +885,7 @@
     // Give the policy a chance to intercept the key.
     if (entry->interceptKeyResult == KeyEntry::INTERCEPT_KEY_RESULT_UNKNOWN) {
         if (entry->policyFlags & POLICY_FLAG_PASS_TO_USER) {
-            CommandEntry* commandEntry = postCommandLocked(
+            std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
                     &InputDispatcher::doInterceptKeyBeforeDispatchingLockedInterruptible);
             sp<InputWindowHandle> focusedWindowHandle =
                     getValueByKey(mFocusedWindowHandlesByDisplay, getTargetDisplayId(entry));
@@ -892,6 +894,7 @@
                     getInputChannelLocked(focusedWindowHandle->getToken());
             }
             commandEntry->keyEntry = entry;
+            postCommandLocked(std::move(commandEntry));
             entry->refCount += 1;
             return false; // wait for the command to run
         } else {
@@ -1988,10 +1991,11 @@
     }
     }
 
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doPokeUserActivityLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry =
+            std::make_unique<CommandEntry>(&InputDispatcher::doPokeUserActivityLockedInterruptible);
     commandEntry->eventTime = eventEntry->eventTime;
     commandEntry->userActivityEventType = eventType;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::prepareDispatchCycleLocked(nsecs_t currentTime,
@@ -2206,9 +2210,10 @@
         return;
     }
 
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doOnPointerDownOutsideFocusLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
+            &InputDispatcher::doOnPointerDownOutsideFocusLockedInterruptible);
     commandEntry->newToken = newToken;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::startDispatchCycleLocked(nsecs_t currentTime,
@@ -2915,8 +2920,7 @@
         policyFlags |= POLICY_FLAG_TRUSTED;
     }
 
-    EventEntry* firstInjectedEntry;
-    EventEntry* lastInjectedEntry;
+    std::queue<EventEntry*> injectedEntries;
     switch (event->getType()) {
     case AINPUT_EVENT_TYPE_KEY: {
         KeyEvent keyEvent;
@@ -2949,12 +2953,13 @@
         }
 
         mLock.lock();
-        firstInjectedEntry = new KeyEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, keyEvent.getEventTime(),
-                keyEvent.getDeviceId(), keyEvent.getSource(), keyEvent.getDisplayId(),
-                policyFlags, action, flags,
-                keyEvent.getKeyCode(), keyEvent.getScanCode(), keyEvent.getMetaState(),
-                keyEvent.getRepeatCount(), keyEvent.getDownTime());
-        lastInjectedEntry = firstInjectedEntry;
+        KeyEntry* injectedEntry =
+                new KeyEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, keyEvent.getEventTime(),
+                             keyEvent.getDeviceId(), keyEvent.getSource(), keyEvent.getDisplayId(),
+                             policyFlags, action, flags, keyEvent.getKeyCode(),
+                             keyEvent.getScanCode(), keyEvent.getMetaState(),
+                             keyEvent.getRepeatCount(), keyEvent.getDownTime());
+        injectedEntries.push(injectedEntry);
         break;
     }
 
@@ -2982,7 +2987,7 @@
         mLock.lock();
         const nsecs_t* sampleEventTimes = motionEvent->getSampleEventTimes();
         const PointerCoords* samplePointerCoords = motionEvent->getSamplePointerCoords();
-        firstInjectedEntry =
+        MotionEntry* injectedEntry =
                 new MotionEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, *sampleEventTimes,
                                 motionEvent->getDeviceId(), motionEvent->getSource(),
                                 motionEvent->getDisplayId(), policyFlags, action, actionButton,
@@ -2993,7 +2998,7 @@
                                 motionEvent->getRawYCursorPosition(), motionEvent->getDownTime(),
                                 uint32_t(pointerCount), pointerProperties, samplePointerCoords,
                                 motionEvent->getXOffset(), motionEvent->getYOffset());
-        lastInjectedEntry = firstInjectedEntry;
+        injectedEntries.push(injectedEntry);
         for (size_t i = motionEvent->getHistorySize(); i > 0; i--) {
             sampleEventTimes += 1;
             samplePointerCoords += pointerCount;
@@ -3010,8 +3015,7 @@
                                     motionEvent->getDownTime(), uint32_t(pointerCount),
                                     pointerProperties, samplePointerCoords,
                                     motionEvent->getXOffset(), motionEvent->getYOffset());
-            lastInjectedEntry->next = nextInjectedEntry;
-            lastInjectedEntry = nextInjectedEntry;
+            injectedEntries.push(nextInjectedEntry);
         }
         break;
     }
@@ -3027,13 +3031,12 @@
     }
 
     injectionState->refCount += 1;
-    lastInjectedEntry->injectionState = injectionState;
+    injectedEntries.back()->injectionState = injectionState;
 
     bool needWake = false;
-    for (EventEntry* entry = firstInjectedEntry; entry != nullptr; ) {
-        EventEntry* nextEntry = entry->next;
-        needWake |= enqueueInboundEventLocked(entry);
-        entry = nextEntry;
+    while (!injectedEntries.empty()) {
+        needWake |= enqueueInboundEventLocked(injectedEntries.front());
+        injectedEntries.pop();
     }
 
     mLock.unlock();
@@ -3764,9 +3767,9 @@
     nsecs_t currentTime = now();
 
     // Dump recently dispatched or dropped events from oldest to newest.
-    if (!mRecentQueue.isEmpty()) {
-        dump += StringPrintf(INDENT "RecentQueue: length=%u\n", mRecentQueue.count());
-        for (EventEntry* entry = mRecentQueue.head; entry; entry = entry->next) {
+    if (!mRecentQueue.empty()) {
+        dump += StringPrintf(INDENT "RecentQueue: length=%zu\n", mRecentQueue.size());
+        for (EventEntry* entry : mRecentQueue) {
             dump += INDENT2;
             entry->appendDescription(dump);
             dump += StringPrintf(", age=%0.1fms\n",
@@ -3788,9 +3791,9 @@
     }
 
     // Dump inbound events from oldest to newest.
-    if (!mInboundQueue.isEmpty()) {
-        dump += StringPrintf(INDENT "InboundQueue: length=%u\n", mInboundQueue.count());
-        for (EventEntry* entry = mInboundQueue.head; entry; entry = entry->next) {
+    if (!mInboundQueue.empty()) {
+        dump += StringPrintf(INDENT "InboundQueue: length=%zu\n", mInboundQueue.size());
+        for (EventEntry* entry : mInboundQueue) {
             dump += INDENT2;
             entry->appendDescription(dump);
             dump += StringPrintf(", age=%0.1fms\n",
@@ -4093,12 +4096,13 @@
 
 void InputDispatcher::onDispatchCycleFinishedLocked(
         nsecs_t currentTime, const sp<Connection>& connection, uint32_t seq, bool handled) {
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doDispatchCycleFinishedLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
+            &InputDispatcher::doDispatchCycleFinishedLockedInterruptible);
     commandEntry->connection = connection;
     commandEntry->eventTime = currentTime;
     commandEntry->seq = seq;
     commandEntry->handled = handled;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::onDispatchCycleBrokenLocked(
@@ -4106,19 +4110,21 @@
     ALOGE("channel '%s' ~ Channel is unrecoverably broken and will be disposed!",
             connection->getInputChannelName().c_str());
 
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doNotifyInputChannelBrokenLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
+            &InputDispatcher::doNotifyInputChannelBrokenLockedInterruptible);
     commandEntry->connection = connection;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::onFocusChangedLocked(const sp<InputWindowHandle>& oldFocus,
         const sp<InputWindowHandle>& newFocus) {
     sp<IBinder> oldToken = oldFocus != nullptr ? oldFocus->getToken() : nullptr;
     sp<IBinder> newToken = newFocus != nullptr ? newFocus->getToken() : nullptr;
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doNotifyFocusChangedLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry = std::make_unique<CommandEntry>(
+            &InputDispatcher::doNotifyFocusChangedLockedInterruptible);
     commandEntry->oldToken = oldToken;
     commandEntry->newToken = newToken;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::onANRLocked(
@@ -4148,12 +4154,13 @@
     mLastANRState += StringPrintf(INDENT2 "Reason: %s\n", reason);
     dumpDispatchStateLocked(mLastANRState);
 
-    CommandEntry* commandEntry =
-            postCommandLocked(&InputDispatcher::doNotifyANRLockedInterruptible);
+    std::unique_ptr<CommandEntry> commandEntry =
+            std::make_unique<CommandEntry>(&InputDispatcher::doNotifyANRLockedInterruptible);
     commandEntry->inputApplicationHandle = applicationHandle;
     commandEntry->inputChannel = windowHandle != nullptr ?
             getInputChannelLocked(windowHandle->getToken()) : nullptr;
     commandEntry->reason = reason;
+    postCommandLocked(std::move(commandEntry));
 }
 
 void InputDispatcher::doNotifyConfigurationChangedLockedInterruptible (
@@ -4506,7 +4513,7 @@
 
 void InputDispatcher::traceInboundQueueLengthLocked() {
     if (ATRACE_ENABLED()) {
-        ATRACE_INT("iq", mInboundQueue.count());
+        ATRACE_INT("iq", mInboundQueue.size());
     }
 }
 
diff --git a/services/inputflinger/InputDispatcher.h b/services/inputflinger/InputDispatcher.h
index d73c4d6..92e1e5f 100644
--- a/services/inputflinger/InputDispatcher.h
+++ b/services/inputflinger/InputDispatcher.h
@@ -451,14 +451,6 @@
     virtual status_t pilferPointers(const sp<IBinder>& token) override;
 
 private:
-    template <typename T>
-    struct Link {
-        T* next;
-        T* prev;
-
-    protected:
-        inline Link() : next(nullptr), prev(nullptr) { }
-    };
 
     struct InjectionState {
         mutable int32_t refCount;
@@ -476,7 +468,7 @@
         ~InjectionState();
     };
 
-    struct EventEntry : Link<EventEntry> {
+    struct EventEntry {
         enum {
             TYPE_CONFIGURATION_CHANGED,
             TYPE_DEVICE_RESET,
@@ -648,7 +640,7 @@
     typedef std::function<void(InputDispatcher&, CommandEntry*)> Command;
 
     class Connection;
-    struct CommandEntry : Link<CommandEntry> {
+    struct CommandEntry {
         explicit CommandEntry(Command command);
         ~CommandEntry();
 
@@ -668,75 +660,6 @@
         sp<IBinder> newToken;
     };
 
-    // Generic queue implementation.
-    template <typename T>
-    struct Queue {
-        T* head;
-        T* tail;
-        uint32_t entryCount;
-
-        inline Queue() : head(nullptr), tail(nullptr), entryCount(0) {
-        }
-
-        inline bool isEmpty() const {
-            return !head;
-        }
-
-        inline void enqueueAtTail(T* entry) {
-            entryCount++;
-            entry->prev = tail;
-            if (tail) {
-                tail->next = entry;
-            } else {
-                head = entry;
-            }
-            entry->next = nullptr;
-            tail = entry;
-        }
-
-        inline void enqueueAtHead(T* entry) {
-            entryCount++;
-            entry->next = head;
-            if (head) {
-                head->prev = entry;
-            } else {
-                tail = entry;
-            }
-            entry->prev = nullptr;
-            head = entry;
-        }
-
-        inline void dequeue(T* entry) {
-            entryCount--;
-            if (entry->prev) {
-                entry->prev->next = entry->next;
-            } else {
-                head = entry->next;
-            }
-            if (entry->next) {
-                entry->next->prev = entry->prev;
-            } else {
-                tail = entry->prev;
-            }
-        }
-
-        inline T* dequeueAtHead() {
-            entryCount--;
-            T* entry = head;
-            head = entry->next;
-            if (head) {
-                head->prev = nullptr;
-            } else {
-                tail = nullptr;
-            }
-            return entry;
-        }
-
-        uint32_t count() const {
-            return entryCount;
-        }
-    };
-
     /* Specifies which events are to be canceled and why. */
     struct CancelationOptions {
         enum Mode {
@@ -928,9 +851,9 @@
     sp<Looper> mLooper;
 
     EventEntry* mPendingEvent GUARDED_BY(mLock);
-    Queue<EventEntry> mInboundQueue GUARDED_BY(mLock);
-    Queue<EventEntry> mRecentQueue GUARDED_BY(mLock);
-    Queue<CommandEntry> mCommandQueue GUARDED_BY(mLock);
+    std::deque<EventEntry*> mInboundQueue GUARDED_BY(mLock);
+    std::deque<EventEntry*> mRecentQueue GUARDED_BY(mLock);
+    std::deque<std::unique_ptr<CommandEntry>> mCommandQueue GUARDED_BY(mLock);
 
     DropReason mLastDropReason GUARDED_BY(mLock);
 
@@ -1030,7 +953,7 @@
     // Deferred command processing.
     bool haveCommandsLocked() const REQUIRES(mLock);
     bool runCommandsLockedInterruptible() REQUIRES(mLock);
-    CommandEntry* postCommandLocked(Command command) REQUIRES(mLock);
+    void postCommandLocked(std::unique_ptr<CommandEntry> commandEntry) REQUIRES(mLock);
 
     // Input filter processing.
     bool shouldSendKeyToInputFilterLocked(const NotifyKeyArgs* args) REQUIRES(mLock);