Explain Michael & Scott lock-free queue alorigthm

Question

I am studying Michael & Scott's lock-free queue algorithm and trying to implemented it in C++.

But I produced a race in my code and think there may be a race in the algorithm.

I read the paper here: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms and the original Dequeue pseudo-code is as following:

dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1:   loop                          // Keep trying until Dequeue is done
D2:      head = Q->Head             // Read Head
D3:      tail = Q->Tail             // Read Tail
D4:      next = head.ptr->next      // Read Head.ptr->next
D5:      if head == Q->Head         // Are head, tail, and next consistent?
D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
D7:            if next.ptr == NULL  // Is queue empty?
D8:               return FALSE      // Queue is empty, couldn't dequeue
D9:            endif
                // Tail is falling behind.  Try to advance it
D10:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11:         else                    // No need to deal with Tail
               // Read value before CAS
               // Otherwise, another dequeue might free the next node
D12:            *pvalue = next.ptr->value
               // Try to swing Head to the next node
D13:            if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14:               break             // Dequeue is done.  Exit loop
D15:            endif
D16:         endif
D17:      endif
D18:   endloop
D19:   free(head.ptr)                // It is safe now to free the old node
D20:   return TRUE                   // Queue was not empty, dequeue succeeded

In my view, the race is like this:

1. Thread 1 advanced to D3 and then stop.
2. Thread 2 advanced to D3, read the same head as Thread 1.
3. Thread 2 luckily advanced all the way to D20, at D19 it freed head.ptr
4. Thread 1 continues and advanced to D4, trying to read head.ptr->next, but as head.ptr is already freed by Thread 1, crash happens.

And my C++ code really always crashes at D4 for Thread 1.

Can anyone please point out my mistake and give some explanation ?

Liking

Answer 1

Thank you, very interesting subject! It's definitely looks like a bug, but one of the authors of the paper assert that their free() is not normal free() we all live with, but some magic free(), so there is no bug. Fantastic.

See https://web.archive.org/web/20190905090735/http://blog.shealevy.com/2015/04/23/use-after-free-bug-in-maged-m-michael-and-michael-l-scotts-non-blocking-concurrent-queue-algorithm/

Hope no one put this into production without thorough analysis.

Lederman

As far as I can tell, the free list mentioned in their paper is one implemented using DCAS, which is basically an imaginary operation. – Frida

I think that explains the origin of this Java memory leak bug then... the memory leak is a workaround for the dangerous free: bugs.java.com/bugdatabase/view_bug.do?bug_id=8137185 – Shotten

Answer 2

This is actually the non-blocking memory reclamation problem that’s being explored years since Maged Michael, one of the authors of MS queue, introduced Hazard Pointers [1].

Hazard Pointers allow the thread to reserve blocks so that other threads won't really reclaim them before it finishes. However, this mechanism incurs nontrivial performance overhead.

There're also many epoch-based reclamation variants such as RCU [2,3], and most recently, interval-based reclamation (IBR) [4]. They avoid use-after-free by reserving epochs and are faster than Hazard Pointers. As far as I know, epoch-based reclamations are widely adopted to handle this problem.

You can take a look at these papers referred below for more details. The paper of Interval-Based Memory Reclamation has much background discussed.

This is a general problem in non-blocking data structures and we generally don't consider it as the bug of the data structure itself---after all it only occurs in languages using manual memory management like C/C++ but not in those like Java (BTW, Michael & Scott Queue has been adopted in Java Concurrency for years).

Reference:

[1] Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, Maged M. Michael, IEEE Transactions on Parallel and Distributed Systems, 2004.

[2] Performance of Memory Reclamation for Lockless Synchronization, Thomas E. Hart et al., Journal of Parallel and Distributed Computing, 2007.

[3] Read Copy Update, Paul E. McKenney et al., Ottawa Linux Symposium, 2002.

[4] Interval-Based Memory Reclamation, Haosen Wen et al., Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018.

Radom

Answer 3

Yes, the problem might be in D19.

As the accepted answer points out is not normal free().

This is stated in the introduction §1

A node is freed only when no pointers in the data structure or temporary variables point to it.

Nabal

The quotation you've given is related to Valois's algorithm mentioned by Michael & Scott. The previous sentences of introduction §1 paragraph are as follows: Valois therefore proposes a special mechanism to free and allocate memory. The mechanism associates a reference counter with each node. ... When it does not intend to access a node that it has accessed before, it decrements the associated reference counter atomically. ... A node is freed only when no pointers in the data structure or temporary variables point to it. We do not see decrementing counters in Michael & Scott queue, do we? – Mangosteen