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 <https://github.com/winksaville/test-mpscfifo-intrusive/commit/e269f21f10fa2a8aeee051b0f5d0e8133a0d36c4>. 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() <https://github.com/winksaville/test-mpscfifo-intrusive/commit/867b949a3d2c87e8455ba741381ac3b7b662631b> 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 <http://www.1024cores.net/home/relacy-race-detector/rrd-introduction> and SPIN <http://spinroot.com> in the future, thanks for the tip. Actually, what does "Relacy" mean? -- Wink On Wednesday, August 10, 2016 at 2:56:36 AM UTC-7, Dmitry Vyukov wrote: > > 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 > > > > > > On Wed, Aug 10, 2016 at 4:41 AM, Wink Saville <[email protected] > <javascript:>> 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 [email protected] <javascript:>. > > 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 > -- --- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/789e1e43-e410-45a1-9683-13ccf80cc188%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
