Fix dynamic MPMCQueue tryObtainPromisedPushTicket() to prevent tryWriteUntil() and...
authorMaged Michael <magedmichael@fb.com>
Tue, 10 Jan 2017 02:31:20 +0000 (18:31 -0800)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Tue, 10 Jan 2017 02:33:00 +0000 (18:33 -0800)
commit232f650cce09c371810d8b1d9fd94143896eceac
tree619f3a154be6ac0b63b1f3d7b55fb53ff735b126
parent410f652b4efe12ec98d7c15879e0c947867de09f
Fix dynamic MPMCQueue tryObtainPromisedPushTicket() to prevent tryWriteUntil() and writeIfNotFull() from blocking indefinitely for a matching read.

Summary:
The bug was reported by Alexander Pronchenkov in https://fb.facebook.com/groups/560979627394613/permalink/837052843120622/

Under certain conditions a `tryWriteUntil()`--and also `writeIfNotFull()`--operation may block indefinitely awaiting a matching read. This could happen because in each dynamic MPMCQueue expansion, typically one or two tickets are associated with the closed array not the new one. In the incorrect code, a `tryWriteUntil()` operation that induced expansion but gets a ticket associated with the closed array, incorrectly assumes that because the expansion succeeded then there is space for it. However because the ticket is associated with the closed array, the operation needs to wait (possibly indefinitely) for space to open in the closed array.

The fix: Changed the code in tryObtainPromisedPushTicket() such that the operation tries to acquire a ticket only if there is promised space in the array associated with that ticket. If there is no space, an expansion is attempted if the ticket is not associated with a closed array. If not or if expansion fails because of reaching maximum capacity or for being out-of-memory, then the operation returns false without attempting to acquire the ticket.

Other changes:
- Added a note about this difference in semantic between the dynamic and non-dynamic version to the main comment about the dynamic version.
- Changed `oldCap` to `curCap` because the value is actually current not old.
- Added two tests for checking that tryWriteUntil() never blocks indefinitely for both dynamic and non-dynamic versions.
- Removed all the `never_fail` tests for the dynamic version, because such operations may fails as described above.
- Added `asm_volatile_pause` when spinning on the seqlock.

Reviewed By: djwatson

Differential Revision: D4389347

fbshipit-source-id: c46dbefc9fe08e146250d2ad8ba68b0887f97436
folly/MPMCQueue.h
folly/test/MPMCQueueTest.cpp