diff --git a/libs/gui/BufferQueueConsumer.cpp b/libs/gui/BufferQueueConsumer.cpp
index 526c3b7..c7d5e00 100644
--- a/libs/gui/BufferQueueConsumer.cpp
+++ b/libs/gui/BufferQueueConsumer.cpp
@@ -120,6 +120,7 @@
             if (mCore->stillTracking(front)) {
                 // Front buffer is still in mSlots, so mark the slot as free
                 mSlots[front->mSlot].mBufferState = BufferSlot::FREE;
+                mCore->mFreeBuffers.push_back(front->mSlot);
             }
             mCore->mQueue.erase(front);
             front = mCore->mQueue.begin();
@@ -173,6 +174,8 @@
 
     ATRACE_INT(mCore->mConsumerName.string(), mCore->mQueue.size());
 
+    mCore->validateConsistencyLocked();
+
     return NO_ERROR;
 }
 
@@ -199,6 +202,7 @@
 
     mCore->freeBufferLocked(slot);
     mCore->mDequeueCondition.broadcast();
+    mCore->validateConsistencyLocked();
 
     return NO_ERROR;
 }
@@ -217,18 +221,11 @@
 
     Mutex::Autolock lock(mCore->mMutex);
 
-    // Make sure we don't have too many acquired buffers and find a free slot
-    // to put the buffer into (the oldest if there are multiple).
+    // Make sure we don't have too many acquired buffers
     int numAcquiredBuffers = 0;
-    int found = BufferQueueCore::INVALID_BUFFER_SLOT;
     for (int s = 0; s < BufferQueueDefs::NUM_BUFFER_SLOTS; ++s) {
         if (mSlots[s].mBufferState == BufferSlot::ACQUIRED) {
             ++numAcquiredBuffers;
-        } else if (mSlots[s].mBufferState == BufferSlot::FREE) {
-            if (found == BufferQueueCore::INVALID_BUFFER_SLOT ||
-                    mSlots[s].mFrameNumber < mSlots[found].mFrameNumber) {
-                found = s;
-            }
         }
     }
 
@@ -238,6 +235,17 @@
                 mCore->mMaxAcquiredBufferCount);
         return INVALID_OPERATION;
     }
+
+    // Find a free slot to put the buffer into
+    int found = BufferQueueCore::INVALID_BUFFER_SLOT;
+    if (!mCore->mFreeSlots.empty()) {
+        auto slot = mCore->mFreeSlots.begin();
+        found = *slot;
+        mCore->mFreeSlots.erase(slot);
+    } else if (!mCore->mFreeBuffers.empty()) {
+        found = mCore->mFreeBuffers.front();
+        mCore->mFreeBuffers.remove(found);
+    }
     if (found == BufferQueueCore::INVALID_BUFFER_SLOT) {
         BQ_LOGE("attachBuffer(P): could not find free buffer slot");
         return NO_MEMORY;
@@ -271,6 +279,8 @@
     // for attached buffers.
     mSlots[*outSlot].mAcquireCalled = false;
 
+    mCore->validateConsistencyLocked();
+
     return NO_ERROR;
 }
 
@@ -311,6 +321,7 @@
             mSlots[slot].mEglFence = eglFence;
             mSlots[slot].mFence = releaseFence;
             mSlots[slot].mBufferState = BufferSlot::FREE;
+            mCore->mFreeBuffers.push_back(slot);
             listener = mCore->mConnectedProducerListener;
             BQ_LOGV("releaseBuffer: releasing slot %d", slot);
         } else if (mSlots[slot].mNeedsCleanupOnRelease) {
@@ -325,6 +336,7 @@
         }
 
         mCore->mDequeueCondition.broadcast();
+        mCore->validateConsistencyLocked();
     } // Autolock scope
 
     // Call back without lock held