Re: low-overhead mpsc queue
Dmitriy Vyukov
On Apr 18 2008, 12:15 pm, "Dmitriy V'jukov" <dvyu...@gmail.com> wrote:
> On Apr 18, 6:45 pm, "Dmitriy V'jukov" <dvyu...@gmail.com> wrote:
>
> > -------------------------------------------------------------
> > Here is intrusive version:
> > -------------------------------------------------------------
>
> Here is another version. It doesn't use stub node, but uses CAS. I
> don't know which is better. They really very similar.
>
> struct mpscq_node_t
> {
> mpscq_node_t* volatile next;
>
> };
>
> struct mpscq_t
> {
> mpscq_node_t* volatile head;
> mpscq_node_t tail;
>
> };
>
> #define MPSCQ_STATIC_INIT(self) {&self.tail, 0}
>
> void mpscq_create(mpscq_t* self)
> {
> self->head = &self->tail;
> self->tail.next = 0;
>
> }
>
> void mpscq_push(mpscq_t* self, mpscq_node_t* n)
> {
> n->next = 0;
> mpscq_node_t* prev = XCHG(&self->head, n);
XXX - can be preempted here
> prev->next = n;
>
> }
>
> mpscq_node_t* mpscq_pop(mpscq_t* self)
> {
> mpscq_node_t* tail = self->tail.next;
> if (0 == tail)
> return 0;
> mpscq_node_t* next = tail->next;
> if (next)
> {
> self->tail.next = next;
> return tail;
> }
> mpscq_node_t* head = self->head;
> if (tail != head)
> return 0;
> self->tail.next = 0;
> if (CAS(&self->head, head, &self->tail))
> {
> return tail;
> }
If the code below executes it means that CAS failed to set self->head
to &self->tail, which
can happen only if a push is in progress. If push gets preempted at
XXX exactly when
the popping thread is here then the next in the following assignment
will end up being NULL
as the pushing thread has not yet written the new head into the head-
>next. Hence,
from then on self->tail.next remains NULL while self->head is not.
> next = tail->next;
> if (next)
> {
> self->tail.next = next;
> return tail;
> }
> return 0;
>
> }
Dmitriy Vyukov
Hi whetaver,
But what is the problem? Consumer will just return 0 in such case,
because producer does not finish push yet. What I am missing?
Yes, XXX preemption point is 'problematic' for the algorithm. But it
is handled by returning 0 from pop (other possible solution is to wait
inside of pop() for producer preempted in XXX).
Thank you.
--
Dmitriy V'jukov
whetaver
YYY: pop gets preempted here
Actually on a closer look the race is a bit more complex. Consider
this.
Queue contains one item and there are racing push() and pop() calls.
Pop() manages to get past (tail != head) comparison and gets
preempted
at YYY. Push() keeps going, sets self->head to a new item and gets
preempted
at XXX. Pop() wakes up, sets self->tail.next to 0 and sees that CAS
fails
(since self->head has been changed). It reads tail->next, however it
is
0 as push() has not completed yet. Pop() leaves self->tail.next set to
0
and returns. Push() wakes up and writes a new head value into prev-
>next.
From then on, push() will grow the queue but pop() will not see the
changes
as self->head is different from &self->tail but self->tail.next is 0.
I think, it can be fixed either by setting self->tail.next back to
tail
in case tail->next is still 0 after CAS fails or, as you noted,
waiting
until tail->next is set.
Regards,
Alex
Dmitriy Vyukov
> Actually on a closer look the race is a bit more complex. Consider
> this.
> Queue contains one item and there are racing push() and pop() calls.
> Pop() manages to get past (tail != head) comparison and gets
> preempted
> at YYY. Push() keeps going, sets self->head to a new item and gets
> preempted
> at XXX. Pop() wakes up, sets self->tail.next to 0 and sees that CAS
> fails
> (since self->head has been changed). It reads tail->next, however it
> is
> 0 as push() has not completed yet. Pop() leaves self->tail.next set to
> 0
> and returns. Push() wakes up and writes a new head value into prev-
>
> >next.
>
> From then on, push() will grow the queue but pop() will not see the
> changes
> as self->head is different from &self->tail but self->tail.next is 0.
>
> I think, it can be fixed either by setting self->tail.next back to
> tail
> in case tail->next is still 0 after CAS fails or, as you noted,
> waiting
> until tail->next is set.
Hi Alex,
Ah, now I see. I think you are right regarding the race.
Consumer resets self->tail.next to 0 (hoping that CAS will succeed),
but then if CAS fails he "forgets" to restore self->tail.next to the
previous value.
The issue can be fixed this way right?
mpscq_node_t* mpscq_pop(mpscq_t* self)
{
mpscq_node_t* tail = self->tail.next;
if (0 == tail)
return 0;
mpscq_node_t* next = tail->next;
if (next)
{
self->tail.next = next;
return tail;
}
mpscq_node_t* head = self->head;
if (tail != head)
return 0;
self->tail.next = 0;
if (CAS(&self->head, head, &self->tail))
{
return tail;
}
next = tail->next;
if (next)
{
self->tail.next = next;
return tail;
}
///////////////////////
self->tail.next = tail;
///////////////////////
return 0;
}
Ah, you mean my queue posted on c.p.t:
http://groups.google.ru/group/comp.programming.threads/browse_frm/thread/33f79c75146582f3
Initially I though that you mean my queue posted in this group:
http://groups.google.ru/group/lock-free/browse_thread/thread/55df71b87acb8201
It seems that queue posted in this group is free of the issue, because
it does not use CAS, it uses XCHG instead.
Thank you, Alex.
--
Dmitriy V'jukov