Questions regarding intrusive mpsc FIFO

[Wink Saville]

I've been trying to understand your intrusive mpsc FIFO http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue and find it quite a bit more complex than the non-intrusive version.

My questions are; how did you test/prove its correctness? And secondly, are you or others using this algorithm?

-- wink

[Wink Saville]

I believe I understand how the instrustive mpsc FIFO works and I've got an implementation here. I'd still like to know how correctness is tested and if any one else is using the code.

[Edward Lam]

You can try using this:

Relacy Race Detector - 1024cores

Relacy Race Detector - 1024cores All about lockfree, waitfree, obstruction-free synchronization algorithms and data structures, memory models, sc...

On Tuesday, August 9, 2016 10:41 PM, Wink Saville <wi...@saville.com> wrote:

I believe I understand how the instrustive mpsc FIFO works and I've got an implementation here. I'd still like to know how correctness is tested and if any one else is using the code.

On Saturday, August 6, 2016 at 12:29:31 PM UTC-7, Wink Saville wrote:

I've been trying to understand your intrusive mpsc FIFO http://www.1024cores.net/ home/lock-free-algorithms/ queues/intrusive-mpsc-node- based-queue and find it quite a bit more complex than the non-intrusive version.

My questions are; how did you test/prove its correctness? And secondly, are you or others using this algorithm?

-- wink

--

---
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/1e239caf-7514-46f5-b277-11447aab9606%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Dmitry Vyukov]

Hi Wink,

Re correctness: I don't remember if I passes through Relacy Race
Detector or not. I don't see any bugs in it, which is a good sign. I
also passed review of several experienced developers.
If you want more guarantees you can test with Relacy Race Detector or
write a SPIN model and test it.

Re usage: I don't explicitly track all uses. And it's generally
impossible since its open on the internet. There was a number of
inquiries about this queue. E.g.:
https://groups.google.com/forum/#!msg/lock-free/nvjCNJgb0bA/9eDuTeDcMXQJ
Probably also some of these:
https://groups.google.com/forum/#!searchin/lock-free/%22MPSC%22$20%22XCHG%22%7Csort:relevance

> --
>
> ---
> 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/1e239caf-7514-46f5-b277-11447aab9606%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]

Txs I'll look into that.

To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/CAEeQi3um5AksFh6v8sDB%3DznPVZbQH0zt%2BhWPhT8PXxC1tsAOiQ%40mail.gmail.com.

[Wink Saville]

I don't see any bugs either, although it took me several days to

get my the version that stalls working. In fact I got it working by first

changing my test code so I could use rmv_non_stalling() everywhere.

And then got the idea to call  rmv_non_stalling() from my

stall routine and low and behold rmv() started working. I then looked

at the debug traces and figured out the real problem, I wasn't actually

removing the node when after stalling.

In my current version of rmv() I changed the code paths so there

is one stall point and I remove the node at the end:

mpscq_node_t* rmv(mpscq_t* self)

{

  mpscq_node_t* tail = self->tail;

  mpscq_node_t* next = tail->next;

  if (tail == &self->stub)

  {

    if (0 == next)

      return 0;

    self->tail = next;

    tail = next;

    next = next->next;

  }

  if (0 == next)

  {

    if (tail == self->head)

      mpscq_push(self, &self->stub);

    next = tail->next;

    while (0 == next)

    {

      sched_yield();

      next = tail->next;

    }

  }

  self->tail = next;

  return tail;

}

Anyway, I'll look into RRD and SPIN in the future, thanks for the tip.

Actually, what does "Relacy" mean?

-- Wink

[Dmitry Vyukov]

On Wed, Aug 10, 2016 at 9:43 PM, Wink Saville <wi...@saville.com> wrote:
> I don't see any bugs either, although it took me several days to
> get my the version that stalls working. In fact I got it working by first
> changing my test code so I could use rmv_non_stalling() everywhere.

Hi Wink,

Well, non-blocking algorithms are hard. A proof for the original
algorithm won't help you with your new version.

It stands for RELAxed ConsistencY.

[Wink Saville]

I understand, txs for the reply.

--

---
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/CAEeQi3vL6FpBrf0dnxBT64efM7hUbu7L5qG7w%2B5611a97k6uhg%40mail.gmail.com.