Re: Regarding Non-intrusive MPSC node-based queue

[Dmitry Vyukov]

On Tue, Jul 5, 2016 at 1:36 AM, Wink Saville <wi...@saville.com> wrote:
> Dmitry,
>
> I've been using your non-intrusive mpsc fifo in a project and its been
> working well, but now I've reached the point where I'm stressing it with
> many threads on a multicore CPU and I'm running into at least one problem.
> To diagnose the problem I've created another implementation for testing here
> and I'm still seeing a problem. The problem is even though the fifo is NOT
> empty "rmv" infrequently returns NULL!!!
>
> See the README.md file for more information.
>
> Any help much appreciated.


Hello Wink,

This algorithm is not lock-free and is not linearizable.
If a producer is preempted between XCHG and next link update, the
linked list of nodes is temporary broken and all subsequent enqueues
are not visible to consumer until the list is restored.
This condition can be detected by looking at head/tail/next, and then
consumer can spin if necessary.

[Wink Saville]

I think I now understand (see slides).

In mpsq_push from your algorithm you state in the "Disadvantages"  that "Push function is blocking wrt consumer".

So I now see if a producer, T1, is preempted after the XCHG(&self->head, n); and before the

prev->next = n (I've marked below) the consumer is blocked:

void mpscq_push(mpscq_t* self, mpscq_node_t* n)
{
  n->next = 0;
  mpscq_node_t* prev = XCHG(&self->head, n); // serialization-point wrt producers, acquire-release

    // (*) If producer is preempted here, consumer is "blocked" 

  prev->next = n; // serialization-point wrt consumer, release
}

But in your code consumer isn't "blocked", I think the code should be something like:

mpscq_node_t* mpscq_pop(mpscq_t* self)
{
  mpscq_node_t* tail = self->tail;
  mpscq_node_t* next = tail->next; // serialization-point wrt producers, acquire
  if (next)
  {

    // Not empty
    self->tail = next;
    tail->state = next->state;
    return tail;
  }

  else if (tail == self->head)

  {

    // Empty

    return 0;

  }

  else

  {

    // Bad luck producer was preempted

    while ((next = tail->next) == NULL) {

      sched_yield();

    }    
    self->tail = next; 
    tail->state = next->state; 
    return tail; 

  }
}

[Dmitry Vyukov]

It may be that way, but it does not always need to be. If caller has
nothing else to do then it will probably spin himself, if he has
something else to do then he better do that something else rather than
spin in the queue.

> mpscq_node_t* mpscq_pop(mpscq_t* self)
> {
> mpscq_node_t* tail = self->tail;
> mpscq_node_t* next = tail->next; // serialization-point wrt producers,
> acquire
> if (next)
> {
> // Not empty
> self->tail = next;
> tail->state = next->state;
> return tail;
> }
> else if (tail == self->head)
> {
> // Empty
> return 0;
> }
> else
> {
> // Bad luck producer was preempted
> while ((next = tail->next) == NULL) {
> sched_yield();
> }
> self->tail = next;
> tail->state = next->state;
> return tail;
> }
> }
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Scalable Synchronization Algorithms" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to lock-free+...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/lock-free/456a739f-e52e-4ab3-abab-04177f85dca0%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--
Dmitry Vyukov

All about lockfree/waitfree algorithms, multicore, scalability,
parallel computing and related topics:
http://www.1024cores.net

[Wink Saville]

Agreed, in my test code https://github.com/winksaville/test-mpscfifo/blob/master/mpscfifo.c
I've implemented, rmv_non_blocking.

In any case, I suggest a little more info in your example would be helpful for neophytes like me.