diff --git a/libs/gui/BufferQueueProducer.cpp b/libs/gui/BufferQueueProducer.cpp
index 6452cdd..a27d5f0 100644
--- a/libs/gui/BufferQueueProducer.cpp
+++ b/libs/gui/BufferQueueProducer.cpp
@@ -161,8 +161,6 @@
             }
         }
 
-        // Look for a free buffer to give to the client
-        *found = BufferQueueCore::INVALID_BUFFER_SLOT;
         int dequeuedCount = 0;
         int acquiredCount = 0;
         for (int s = 0; s < maxBufferCount; ++s) {
@@ -173,15 +171,6 @@
                 case BufferSlot::ACQUIRED:
                     ++acquiredCount;
                     break;
-                case BufferSlot::FREE:
-                    // We return the oldest of the free buffers to avoid
-                    // stalling the producer if possible, since the consumer
-                    // may still have pending reads of in-flight buffers
-                    if (*found == BufferQueueCore::INVALID_BUFFER_SLOT ||
-                            mSlots[s].mFrameNumber < mSlots[*found].mFrameNumber) {
-                        *found = s;
-                    }
-                    break;
                 default:
                     break;
             }
@@ -214,6 +203,8 @@
             }
         }
 
+        *found = BufferQueueCore::INVALID_BUFFER_SLOT;
+
         // If we disconnect and reconnect quickly, we can be in a state where
         // our slots are empty but we have many buffers in the queue. This can
         // cause us to run out of memory if we outrun the consumer. Wait here if
@@ -223,6 +214,19 @@
         if (tooManyBuffers) {
             BQ_LOGV("%s: queue size is %zu, waiting", caller,
                     mCore->mQueue.size());
+        } else {
+            if (!mCore->mFreeBuffers.empty()) {
+                auto slot = mCore->mFreeBuffers.begin();
+                *found = *slot;
+                mCore->mFreeBuffers.erase(slot);
+            } else if (!mCore->mFreeSlots.empty()) {
+                auto slot = mCore->mFreeSlots.begin();
+                // Only return free slots up to the max buffer count
+                if (*slot < maxBufferCount) {
+                    *found = *slot;
+                    mCore->mFreeSlots.erase(slot);
+                }
+            }
         }
 
         // If no buffer is found, or if the queue has too many buffers
@@ -335,6 +339,8 @@
         *outFence = mSlots[found].mFence;
         mSlots[found].mEglFence = EGL_NO_SYNC_KHR;
         mSlots[found].mFence = Fence::NO_FENCE;
+
+        mCore->validateConsistencyLocked();
     } // Autolock scope
 
     if (returnFlags & BUFFER_NEEDS_REALLOCATION) {
@@ -355,7 +361,6 @@
                 return NO_INIT;
             }
 
-            mSlots[*outSlot].mFrameNumber = UINT32_MAX;
             mSlots[*outSlot].mGraphicBuffer = graphicBuffer;
         } // Autolock scope
     }
@@ -414,6 +419,7 @@
 
     mCore->freeBufferLocked(slot);
     mCore->mDequeueCondition.broadcast();
+    mCore->validateConsistencyLocked();
 
     return NO_ERROR;
 }
@@ -438,27 +444,19 @@
         return NO_INIT;
     }
 
-    // Find the oldest valid slot
-    int found = BufferQueueCore::INVALID_BUFFER_SLOT;
-    for (int s = 0; s < BufferQueueDefs::NUM_BUFFER_SLOTS; ++s) {
-        if (mSlots[s].mBufferState == BufferSlot::FREE &&
-                mSlots[s].mGraphicBuffer != NULL) {
-            if (found == BufferQueueCore::INVALID_BUFFER_SLOT ||
-                    mSlots[s].mFrameNumber < mSlots[found].mFrameNumber) {
-                found = s;
-            }
-        }
-    }
-
-    if (found == BufferQueueCore::INVALID_BUFFER_SLOT) {
+    if (mCore->mFreeBuffers.empty()) {
         return NO_MEMORY;
     }
 
+    int found = mCore->mFreeBuffers.front();
+    mCore->mFreeBuffers.remove(found);
+
     BQ_LOGV("detachNextBuffer detached slot %d", found);
 
     *outBuffer = mSlots[found].mGraphicBuffer;
     *outFence = mSlots[found].mFence;
     mCore->freeBufferLocked(found);
+    mCore->validateConsistencyLocked();
 
     return NO_ERROR;
 }
@@ -506,6 +504,8 @@
     mSlots[*outSlot].mFence = Fence::NO_FENCE;
     mSlots[*outSlot].mRequestBufferCalled = true;
 
+    mCore->validateConsistencyLocked();
+
     return returnFlags;
 }
 
@@ -640,9 +640,7 @@
                 // mark it as freed
                 if (mCore->stillTracking(front)) {
                     mSlots[front->mSlot].mBufferState = BufferSlot::FREE;
-                    // Reset the frame number of the freed buffer so that it is
-                    // the first in line to be dequeued again
-                    mSlots[front->mSlot].mFrameNumber = 0;
+                    mCore->mFreeBuffers.push_front(front->mSlot);
                 }
                 // Overwrite the droppable buffer with the incoming one
                 *front = item;
@@ -664,6 +662,8 @@
 
         // Take a ticket for the callback functions
         callbackTicket = mNextCallbackTicket++;
+
+        mCore->validateConsistencyLocked();
     } // Autolock scope
 
     // Wait without lock held
@@ -724,10 +724,11 @@
         return;
     }
 
+    mCore->mFreeBuffers.push_front(slot);
     mSlots[slot].mBufferState = BufferSlot::FREE;
-    mSlots[slot].mFrameNumber = 0;
     mSlots[slot].mFence = fence;
     mCore->mDequeueCondition.broadcast();
+    mCore->validateConsistencyLocked();
 }
 
 int BufferQueueProducer::query(int what, int *outValue) {
@@ -1009,13 +1010,19 @@
                 }
                 mCore->freeBufferLocked(slot); // Clean up the slot first
                 mSlots[slot].mGraphicBuffer = buffers[i];
-                mSlots[slot].mFrameNumber = 0;
                 mSlots[slot].mFence = Fence::NO_FENCE;
+
+                // freeBufferLocked puts this slot on the free slots list. Since
+                // we then attached a buffer, move the slot to free buffer list.
+                mCore->mFreeSlots.erase(slot);
+                mCore->mFreeBuffers.push_front(slot);
+
                 BQ_LOGV("allocateBuffers: allocated a new buffer in slot %d", slot);
             }
 
             mCore->mIsAllocating = false;
             mCore->mIsAllocatingCondition.broadcast();
+            mCore->validateConsistencyLocked();
         } // Autolock scope
     }
 }