From 9ec5a371f5c05fda8ddeac3470be6fc5c67d44e9 Mon Sep 17 00:00:00 2001
From: Determinant <ted.sybil@gmail.com>
Date: Sun, 14 Apr 2019 21:56:10 -0400
Subject: fix item skipping bug in lock-free queue

---
 include/salticidae/queue.h | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

(limited to 'include/salticidae/queue.h')

diff --git a/include/salticidae/queue.h b/include/salticidae/queue.h
index 0417750..da11e8a 100644
--- a/include/salticidae/queue.h
+++ b/include/salticidae/queue.h
@@ -15,7 +15,8 @@ class FreeList {
     struct Node {
         std::atomic<Node *> next;
         std::atomic<size_t> refcnt;
-        Node(): next(nullptr), refcnt(1) {}
+        std::atomic<bool> freed;
+        Node(): next(nullptr), refcnt(1), freed(false) {}
     };
 
     private:
@@ -37,15 +38,16 @@ class FreeList {
             // the replacement is ok even if ABA happens
             if (top.compare_exchange_weak(t, u, std::memory_order_release))
             {
+                // must have seen freed == true
                 u->refcnt.store(1, std::memory_order_relaxed);
                 break;
             }
         }
     }
 
-    bool push(Node *u) {
+    inline void push(Node *u) {
+        u->freed.store(true, std::memory_order_relaxed);
         release_ref(u);
-        return true;
     }
 
     bool pop(Node *&r) {
@@ -110,6 +112,11 @@ class MPMCQueue {
             if (!tcnt) continue;
             if (!t->refcnt.compare_exchange_weak(tcnt, tcnt + 1, std::memory_order_relaxed))
                 continue;
+            if (t->freed.load(std::memory_order_relaxed))
+            {
+                blks.release_ref(t);
+                continue;
+            }
             auto tt = t->tail.load(std::memory_order_relaxed);
             if (tt >= MPMCQ_SIZE)
             {
@@ -130,9 +137,12 @@ class MPMCQueue {
                     nblk->next.store(nullptr, std::memory_order_relaxed);
                     Block *tnext = nullptr;
                     if (!t->next.compare_exchange_weak(tnext, nblk, std::memory_order_acq_rel))
-                        blks.push(_nblk);
+                        blks.push(nblk);
                     else
-                        tail.store(nblk, std::memory_order_relaxed);
+                    {
+                        tail.store(nblk, std::memory_order_release);
+                        nblk->freed.store(false, std::memory_order_release);
+                    }
                 }
                 blks.release_ref(t);
                 continue;
-- 
cgit v1.2.3