diff options
6 files changed, 139 insertions, 36 deletions
diff --git a/services/surfaceflinger/LocklessQueue.h b/services/surfaceflinger/LocklessQueue.h new file mode 100644 index 0000000000..6b633607ae --- /dev/null +++ b/services/surfaceflinger/LocklessQueue.h @@ -0,0 +1,82 @@ +/* + * Copyright 2022 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. + */ + +#pragma once +#include <atomic> +#include <optional> + +template <typename T> +// Single consumer multi producer stack. We can understand the two operations independently to see +// why they are without race condition. +// +// push is responsible for maintaining a linked list stored in mPush, and called from multiple +// threads without lock. We can see that if two threads never observe the same value from +// mPush.load, it just functions as a normal linked list. In the case where two threads observe the +// same value, one of them has to execute the compare_exchange first. The one that doesn't execute +// the compare exchange first, will receive false from compare_exchange. previousHead is updated (by +// compare_exchange) to the most recent value of mPush, and we try again. It's relatively clear to +// see that the process can repeat with an arbitrary number of threads. +// +// Pop is much simpler. If mPop is empty (as it begins) it atomically exchanges +// the entire push list with null. This is safe, since the only other reader (push) +// of mPush will retry if it changes in between it's read and atomic compare. We +// then store the list and pop one element. +// +// If we already had something in the pop list we just pop directly. +class LocklessQueue { +public: + class Entry { + public: + T mValue; + std::atomic<Entry*> mNext; + Entry(T value) : mValue(value) {} + }; + std::atomic<Entry*> mPush = nullptr; + std::atomic<Entry*> mPop = nullptr; + bool isEmpty() { return (mPush.load() == nullptr) && (mPop.load() == nullptr); } + + void push(T value) { + Entry* entry = new Entry(value); + Entry* previousHead = mPush.load(/*std::memory_order_relaxed*/); + do { + entry->mNext = previousHead; + } while (!mPush.compare_exchange_weak(previousHead, entry)); /*std::memory_order_release*/ + } + std::optional<T> pop() { + Entry* popped = mPop.load(/*std::memory_order_acquire*/); + if (popped) { + // Single consumer so this is fine + mPop.store(popped->mNext /* , std::memory_order_release */); + auto value = popped->mValue; + delete popped; + return std::move(value); + } else { + Entry* grabbedList = mPush.exchange(nullptr /* , std::memory_order_acquire */); + if (!grabbedList) return std::nullopt; + // Reverse the list + while (grabbedList->mNext) { + Entry* next = grabbedList->mNext; + grabbedList->mNext = popped; + popped = grabbedList; + grabbedList = next; + } + mPop.store(popped /* , std::memory_order_release */); + auto value = grabbedList->mValue; + delete grabbedList; + return std::move(value); + } + } +}; diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp index 9ef8e7b5f3..ce54f50bde 100644 --- a/services/surfaceflinger/SurfaceFlinger.cpp +++ b/services/surfaceflinger/SurfaceFlinger.cpp @@ -3753,6 +3753,8 @@ int SurfaceFlinger::flushPendingTransactionQueues( transactions.emplace_back(std::move(transaction)); transactionQueue.pop(); + mPendingTransactionCount--; + ATRACE_INT("TransactionQueue", mPendingTransactionCount.load()); } if (transactionQueue.empty()) { @@ -3776,8 +3778,6 @@ bool SurfaceFlinger::flushTransactionQueues(int64_t vsyncId) { { Mutex::Autolock _l(mStateLock); { - Mutex::Autolock _l(mQueueLock); - int lastTransactionsPendingBarrier = 0; int transactionsPendingBarrier = 0; // First collect transactions from the pending transaction queues. @@ -3790,8 +3790,12 @@ bool SurfaceFlinger::flushTransactionQueues(int64_t vsyncId) { // Second, collect transactions from the transaction queue. // Here as well we are not allowing unsignaled buffers for the same // reason as above. - while (!mTransactionQueue.empty()) { - auto& transaction = mTransactionQueue.front(); + while (!mLocklessTransactionQueue.isEmpty()) { + auto maybeTransaction = mLocklessTransactionQueue.pop(); + if (!maybeTransaction.has_value()) { + break; + } + auto transaction = maybeTransaction.value(); const bool pendingTransactions = mPendingTransactionQueues.find(transaction.applyToken) != mPendingTransactionQueues.end(); @@ -3829,9 +3833,9 @@ bool SurfaceFlinger::flushTransactionQueues(int64_t vsyncId) { } }); transactions.emplace_back(std::move(transaction)); + mPendingTransactionCount--; + ATRACE_INT("TransactionQueue", mPendingTransactionCount.load()); } - mTransactionQueue.pop_front(); - ATRACE_INT("TransactionQueue", mTransactionQueue.size()); } // Transactions with a buffer pending on a barrier may be on a different applyToken @@ -3892,8 +3896,7 @@ bool SurfaceFlinger::applyTransactions(std::vector<TransactionState>& transactio } bool SurfaceFlinger::transactionFlushNeeded() { - Mutex::Autolock _l(mQueueLock); - return !mPendingTransactionQueues.empty() || !mTransactionQueue.empty(); + return !mPendingTransactionQueues.empty() || !mLocklessTransactionQueue.isEmpty(); } bool SurfaceFlinger::frameIsEarly(nsecs_t expectedPresentTime, int64_t vsyncId) const { @@ -4060,17 +4063,15 @@ auto SurfaceFlinger::transactionIsReadyToBeApplied(TransactionState& transaction void SurfaceFlinger::queueTransaction(TransactionState& state) { state.queueTime = systemTime(); - - Mutex::Autolock lock(mQueueLock); - // Generate a CountDownLatch pending state if this is a synchronous transaction. if (state.flags & eSynchronous) { state.transactionCommittedSignal = std::make_shared<CountDownLatch>(CountDownLatch::eSyncTransaction); } - mTransactionQueue.emplace_back(state); - ATRACE_INT("TransactionQueue", mTransactionQueue.size()); + mLocklessTransactionQueue.push(state); + mPendingTransactionCount++; + ATRACE_INT("TransactionQueue", mPendingTransactionCount.load()); const auto schedule = [](uint32_t flags) { if (flags & eEarlyWakeupEnd) return TransactionSchedule::EarlyEnd; diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h index 7d23c3c58f..1e4fae77f5 100644 --- a/services/surfaceflinger/SurfaceFlinger.h +++ b/services/surfaceflinger/SurfaceFlinger.h @@ -65,6 +65,7 @@ #include "FlagManager.h" #include "FrameTracker.h" #include "LayerVector.h" +#include "LocklessQueue.h" #include "Scheduler/RefreshRateConfigs.h" #include "Scheduler/RefreshRateStats.h" #include "Scheduler/Scheduler.h" @@ -762,13 +763,13 @@ private: std::vector<TransactionState>& transactions, std::unordered_map<sp<IBinder>, uint64_t, SpHash<IBinder>>& bufferLayersReadyToPresent, std::unordered_set<sp<IBinder>, SpHash<IBinder>>& applyTokensWithUnsignaledTransactions, - bool tryApplyUnsignaled) REQUIRES(mStateLock, mQueueLock); + bool tryApplyUnsignaled) REQUIRES(mStateLock); int flushUnsignaledPendingTransactionQueues( std::vector<TransactionState>& transactions, std::unordered_map<sp<IBinder>, uint64_t, SpHash<IBinder>>& bufferLayersReadyToPresent, std::unordered_set<sp<IBinder>, SpHash<IBinder>>& applyTokensWithUnsignaledTransactions) - REQUIRES(mStateLock, mQueueLock); + REQUIRES(mStateLock); uint32_t setClientStateLocked(const FrameTimelineInfo&, ComposerState&, int64_t desiredPresentTime, bool isAutoTimestamp, @@ -1098,7 +1099,7 @@ private: status_t CheckTransactCodeCredentials(uint32_t code); // Add transaction to the Transaction Queue - void queueTransaction(TransactionState& state) EXCLUDES(mQueueLock); + void queueTransaction(TransactionState& state); void waitForSynchronousTransaction(const CountDownLatch& transactionCommittedSignal); void signalSynchronousTransactions(const uint32_t flag); @@ -1262,11 +1263,11 @@ private: uint32_t mTexturePoolSize = 0; std::vector<uint32_t> mTexturePool; - mutable Mutex mQueueLock; Condition mTransactionQueueCV; std::unordered_map<sp<IBinder>, std::queue<TransactionState>, IListenerHash> - mPendingTransactionQueues GUARDED_BY(mQueueLock); - std::deque<TransactionState> mTransactionQueue GUARDED_BY(mQueueLock); + mPendingTransactionQueues; + LocklessQueue<TransactionState> mLocklessTransactionQueue; + std::atomic<size_t> mPendingTransactionCount = 0; /* * Feature prototyping */ diff --git a/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h b/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h index 3338da012a..de04592dc6 100644 --- a/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h +++ b/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h @@ -727,7 +727,7 @@ public: return mFlinger->setPowerModeInternal(display, mode); } - auto &getTransactionQueue() { return mFlinger->mTransactionQueue; } + auto &getTransactionQueue() { return mFlinger->mLocklessTransactionQueue; } auto &getPendingTransactionQueue() { return mFlinger->mPendingTransactionQueues; } auto setTransactionState( diff --git a/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h b/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h index 60285f98f4..eae5f827c4 100644 --- a/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h +++ b/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h @@ -421,7 +421,7 @@ public: return mFlinger->SurfaceFlinger::getDisplayNativePrimaries(displayToken, primaries); } - auto& getTransactionQueue() { return mFlinger->mTransactionQueue; } + auto& getTransactionQueue() { return mFlinger->mLocklessTransactionQueue; } auto& getPendingTransactionQueue() { return mFlinger->mPendingTransactionQueues; } auto& getTransactionCommittedSignals() { return mFlinger->mTransactionCommittedSignals; } diff --git a/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp b/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp index 84f11704d0..b2da34e213 100644 --- a/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp +++ b/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp @@ -117,7 +117,7 @@ public: } void NotPlacedOnTransactionQueue(uint32_t flags) { - ASSERT_EQ(0u, mFlinger.getTransactionQueue().size()); + ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty()); EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1); TransactionInfo transaction; setupSingle(transaction, flags, @@ -140,12 +140,12 @@ public: EXPECT_LE(returnedTime, applicationTime + mFlinger.getAnimationTransactionTimeout()); } // Each transaction should have been placed on the transaction queue - auto transactionQueue = mFlinger.getTransactionQueue(); - EXPECT_EQ(1u, transactionQueue.size()); + auto& transactionQueue = mFlinger.getTransactionQueue(); + EXPECT_FALSE(transactionQueue.isEmpty()); } void PlaceOnTransactionQueue(uint32_t flags) { - ASSERT_EQ(0u, mFlinger.getTransactionQueue().size()); + ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty()); EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1); // first check will see desired present time has not passed, @@ -171,12 +171,12 @@ public: applicationSentTime + mFlinger.getAnimationTransactionTimeout()); } // This transaction should have been placed on the transaction queue - auto transactionQueue = mFlinger.getTransactionQueue(); - EXPECT_EQ(1u, transactionQueue.size()); + auto& transactionQueue = mFlinger.getTransactionQueue(); + EXPECT_FALSE(transactionQueue.isEmpty()); } void BlockedByPriorTransaction(uint32_t flags) { - ASSERT_EQ(0u, mFlinger.getTransactionQueue().size()); + ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty()); nsecs_t time = systemTime(); EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(2); @@ -239,8 +239,8 @@ public: int mTransactionNumber = 0; }; -TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) { - ASSERT_EQ(0u, mFlinger.getTransactionQueue().size()); +TEST_F(TransactionApplicationTest, AddToPendingQueue) { + ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty()); EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1); TransactionInfo transactionA; // transaction to go on pending queue @@ -253,10 +253,27 @@ TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) { mHasListenerCallbacks, mCallbacks, transactionA.id); auto& transactionQueue = mFlinger.getTransactionQueue(); - ASSERT_EQ(1u, transactionQueue.size()); + ASSERT_FALSE(transactionQueue.isEmpty()); - auto& transactionState = transactionQueue.front(); + auto transactionState = transactionQueue.pop().value(); checkEqual(transactionA, transactionState); +} + +TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) { + ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty()); + EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1); + + TransactionInfo transactionA; // transaction to go on pending queue + setupSingle(transactionA, /*flags*/ 0, /*desiredPresentTime*/ s2ns(1), false, + FrameTimelineInfo{}); + mFlinger.setTransactionState(transactionA.frameTimelineInfo, transactionA.states, + transactionA.displays, transactionA.flags, transactionA.applyToken, + transactionA.inputWindowCommands, transactionA.desiredPresentTime, + transactionA.isAutoTimestamp, transactionA.uncacheBuffer, + mHasListenerCallbacks, mCallbacks, transactionA.id); + + auto& transactionQueue = mFlinger.getTransactionQueue(); + ASSERT_FALSE(transactionQueue.isEmpty()); // because flushing uses the cached expected present time, we send an empty // transaction here (sending a null applyToken to fake it as from a @@ -272,7 +289,7 @@ TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) { // passed mFlinger.flushTransactionQueues(); - EXPECT_EQ(0u, transactionQueue.size()); + EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty()); } TEST_F(TransactionApplicationTest, NotPlacedOnTransactionQueue_Synchronous) { @@ -306,7 +323,9 @@ public: void TearDown() override { // Clear all transaction queues to release all transactions we sent // in the tests. Otherwise, gmock complains about memory leaks. - mFlinger.getTransactionQueue().clear(); + while (!mFlinger.getTransactionQueue().isEmpty()) { + mFlinger.getTransactionQueue().pop(); + } mFlinger.getPendingTransactionQueue().clear(); mFlinger.getTransactionCommittedSignals().clear(); mFlinger.commitTransactionsLocked(eTransactionMask); @@ -358,7 +377,7 @@ public: void setTransactionStates(const std::vector<TransactionInfo>& transactions, size_t expectedTransactionsApplied, size_t expectedTransactionsPending) { - EXPECT_EQ(0u, mFlinger.getTransactionQueue().size()); + EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty()); EXPECT_EQ(0u, mFlinger.getPendingTransactionQueue().size()); for (const auto& transaction : transactions) { @@ -370,7 +389,7 @@ public: mHasListenerCallbacks, mCallbacks, transaction.id); } mFlinger.flushTransactionQueues(); - EXPECT_EQ(0u, mFlinger.getTransactionQueue().size()); + EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty()); EXPECT_EQ(expectedTransactionsPending, mFlinger.getPendingTransactionQueue().size()); EXPECT_EQ(expectedTransactionsApplied, mFlinger.getTransactionCommittedSignals().size()); } |