MPMC Unbounded FIFO Queue w/ 1 CAS/Operation. No jokes. - comp.programming.threads

COMPGROUPS.NET

Post Question

Groups

About

Contact Register | Login

MPMC Unbounded FIFO Queue w/ 1 CAS/Operation. No jokes. Subscribe

First I provide some primary points and then code sketch.

There is no limitations on queue size and producer/consumer count.
Implementation requires only CAS instruction. Values must be of word
size (if DWCAS supported then values can be of dword size). There must
be some reserved value that never enqueued (currently 0).

The main point is: for underlying data-structure I use nested-list,
i.e. values organized in continuous buffers of some constant size
(nests), nests linked in single-linked list. Nest filled with values
only once and only once consumed, then nest is recycled. So there is
no cyclic buffers like in bounded queue on top of vector.

Schema of dequeue operation:
1. Get current tail nest
2. Read current dequeue position in this nest
3. If current tail nest if fully consumed and there is next nest then
recycle the nest and try to move to next nest
4. If current tail nest if fully consumed and there is no next nest
then return 0
5. Read value in current dequeue position
6. If value == 0 then return 0
7. Try to increment current dequeue position with CAS
8. If success then return value
9. If fail then goto 2

Important points about enqueue operation: I don't maintain current
enqueue position in nest at all. Instead I use enqueue position hint
and some sophisticated oracle to determine actual enqueue position.
Nest is zeroized after allocation, so I use CAS(&enqueue_position,
value, 0) to enqueue value. After successful enqueue I update enqueue
position hint with plain store operation.

Algorithm of oracle to determine actual enqueue position (subject for
modifications and improvements):
1. Check current enqueue position hint
2. If fail then check several next positions
3. If fail then use binary search in [enqueue_position_hint,
end_of_nest] to find right position
Note: hint can't point to position after actual enqueue position, only
before.

Schema of enqueue operation:
1. Get current head nest
2. Read current enqueue position hint in this nest
3. If nest is fully filled then allocate new nest and link this new
node as head
4. Try to write value with CAS(&enqueue_position, value, 0)
5. If success then return
6. If fail then use oracle to predict right enqueue position and goto
3

Implementation notes.
1. For managing nest life time and prevent ABA I use PDR scheme for
nests. I cache current nest in TLS, so atomic RMW issued only once for
nest. Head and tail pointers is strong PDR pointers, all other
pointers to nests is normal PDR pointers.
Maybe other scheme can be used here to prevent ABA and premature node
reusing. But I use PDR here for simplicity.
2. For allocation/deallocation of nests I use lock-free stack-based
freelist. Before nest is placed to freelist, nest is cleared, i.e.
buffer zeroized and enqueue/dequeue positions set to 0. If there are
no nests in freelist, allocation requests forwarded to system
allocator.

Here is code sketch:

unsigned const nest_size = 1000;

struct nest_t
{
// can be incorrect
unsigned enqueue_pos_hint_;
// always maintained in correct state
unsigned dequeue_pos_;
void* buffer_[nest_size];
nest_t* next_;

nest_t()
{
next_ = 0;
enqueue_pos_hint_ = 0;
dequeue_pos_ = 0;
memset(buffer_, 0, sizeof(buffer_));
}
};

struct mpmc_queue_t
{
global_ptr<nest_t> head_;
global_ptr<nest_t> tail_;

mpmc_queue_t()
{
head_ = tail_ = alloc_node();
}

void enqueue(void* value)
{
// here strong acquire of head
// cached in tls, so atomic rmw issued
// only once for nest
local_ptr nest (head_);
unsigned pos = nest->enqueue_pos_hint_;
do
{
if (nest_is_over(nest.get(), pos))
{
// current nest is full
// have to allocate new nest and link it
nest_t* new_nest = alloc_node();
nest_t* old_nest = CAS(nest->next_, new_nest, (nest_t*)0);
if (!old_nest)
{
head_.CAS(new_nest, nest.get());
}
else
{
head_.CAS(old_nest, nest.get());
free_node(new_nest);
}
// update current nest
nest = head_;
pos = nest->enqueue_pos_hint_;
}
// check whether current pos is empty
if (check_enqueue_pos(nest.get(), pos))
{
// try to write the value
if (!CAS_fail(nest->buffer_[pos], value, 0))
{
// plain store to enqueue_pos_hint_
nest->enqueue_pos_hint_ = pos + 1;
return;
}
}
// here some sophisticated logic
// to determine enqueue pos
// involves look-ahead, binary-search etc...
pos = enqueue_pos_oracle(nest.get(), pos);
} while (true);
}

void* dequeue()
{
// here strong acquire of head
// cached in tls, so atomic rmw issued
// only once for nest
local_ptr nest (tail_);
char* value;
unsigned pos;
do
{
pos = nest->dequeue_pos_;
if (nest_is_over(nest.get(), pos))
{
// current nest is fully consumed
// try to switch to next nest
nest_t* next = nest->next_;
if (!next) return 0;
tail_.CAS(next, nest.get());
nest = tail_;
}
// read current value
value = nest->buffer_[pos];
if (!value) return 0;
}
// try to increment dequeue pos
while (CAS_fail(nest->dequeue_pos_, pos + 1, pos));
return value;
}
};

I think that nested-list based lock-free data structures are very
interesting and perspective. I haven't seen it before. Definitely some
other lock-free data structures can be build on top of nested-list...

Comments/suggestions/thoughts are welcome ;)

Dmitriy V'jukov

dvyukov

5/18/2007 12:38:11 PM

Header