Dynamic MPMCQueue: Eliminate cases of enqueue indefinite blocking and failure in...
authorMaged Michael <magedmichael@fb.com>
Wed, 30 Aug 2017 19:53:16 +0000 (12:53 -0700)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Wed, 30 Aug 2017 20:09:17 +0000 (13:09 -0700)
commit9ce176b1e0587a698d5930b70be86ca63a139af8
treeb91a465becc33eb106b7db1248092f7cd676f773
parentf7ec2efe1923edf6365c04e3596a32d1b41d3a7f
Dynamic MPMCQueue: Eliminate cases of enqueue indefinite blocking and failure in the extensible version that impossible under the default pre-allocated version

Summary:
Currently under the extensible version (Dynamic == true), some enqueue operations may block indefinitely or fail (return false) even though such outcomes are impossible under the default (Dynamic == false) pre-allocated version.

This diff eliminates such cases by changing the algorithms for the extensible version. Some of the high-level changes:
- The offset formula for an expansion guarantees that no enqueue operation left behind in a closed array does not have an existing dequeue operation that unblocks it. The old formula was 1 + max(head, tail). The new formula is max(head, current offset) + current capacity.
- Conditional operations validate state after the success of CAS.

Reviewed By: djwatson

Differential Revision: D5701013

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