lock-free job queue without size restriction (multiple read/write)

Question

I've since come up with an improved version, which isn't technically lock-free, but might be as close as you can get (nearly) lock-free job queue of dynamic size (multiple read/write)

code below is not thread safe

---

I was looking for a *simple lock-free job-queue which can be used in a generic way, cross-platform.

_{* no external dependencies, only few calls to interface, no exotic compiler tricks which may break from compiler to compiler, preferably header only.}

Either I suck at Googling, or this isn't available ( they are not mutually exclusive, but you get the point ).

---

This is what I eventually came up with.

It's a linked list, which allocates a fifo_node_type on the heap for each item pushed. This items gets destroyed in the pop function.

fifo.h

/**
 * This is a lock free fifo, which can be used for multi-producer, multi-consumer
 * type job queue
 */
template < typename Value >
struct fifo_node_type
{
 fifo_node_type( const Value &original ) :
 value( original ),
 next( nullptr ) { }
 Value value;
 fifo_node_type *next;
};
template < typename Value, typename Allocator = std::allocator< fifo_node_type< Value > > >
class fifo
{
 public:
 typedef Value value_type;
 typedef Allocator allocator_type;
 typedef std::vector< value_type, allocator_type > vector_type;
 fifo() :
 start_(),
 end_(),
 allocator_() {}
 ~fifo()
 {
 clear();
 }
 /**
 * pushes an item into the job queue, may throw if allocation fails
 * leaving the queue unchanged
 */
 template < typename T >
 void push( T &&val )
 {
 node_ptr newnode = create_node( std::forward< T >( val ) );
 node_ptr tmp = nullptr;
 start_.compare_exchange_strong( tmp, newnode );
 node_ptr prev_end = end_.exchange( newnode );
 if ( prev_end )
 {
 prev_end->next = newnode;
 }
 }
 /**
 * retrieves an item from the job queue.
 * if no item was available, func is untouched and pop returns false
 */
 bool pop( value_type &func )
 {
 auto assign = [ & ]( node_ptr ptr, value_type &value)
 {
 std::swap( value, ptr->value );
 destroy_node( ptr );
 };
 return pop_generic( func, assign );
 }
 /**
 * clears the job queue, storing all pending jobs in the supplied vector.
 * the vector is also returned for convenience
 */
 vector_type& pop_all( vector_type &unfinished )
 {
 value_type tmp;
 while ( pop( tmp ) )
 {
 unfinished.push_back( tmp );
 }
 return unfinished;
 }
 /**
 * clears the job queue.
 */
 void clear()
 {
 auto del = [ & ]( node_ptr ptr, value_type& )
 {
 destroy_node( ptr );
 };
 value_type tmp;
 while ( pop_generic( tmp, del ) )
 {
 // empty
 }
 }
 /**
 * returns true if there are no pending jobs
 */
 bool empty() const
 {
 return start_ == nullptr;
 }
 private:
 typedef fifo_node_type< value_type > node_type;
 typedef node_type* node_ptr;
 typedef std::atomic< node_ptr > node;
 fifo( const fifo& );
 fifo& operator = ( const fifo& );
 template < typename Assign >
 bool pop_generic( value_type &func, Assign assign )
 {
 node_ptr tmp = start_;
 while ( tmp )
 {
 if ( start_.compare_exchange_weak( tmp, tmp->next ) )
 {
 assign( tmp, func );
 return true;
 }
 // if we got here, tmp was set to the value of start_, so we try again
 }
 return false;
 }
 template < typename T >
 node_ptr create_node( T &&t )
 {
 node_ptr result = reinterpret_cast< node_ptr >( allocator_.allocate( 1 ) );
 new ( result ) node_type( std::forward< T >( t ) );
 return result;
 }
 void destroy_node( node_ptr &t )
 {
 allocator_.destroy( t );
 allocator_.deallocate( t, 1 );
 }
 node start_, end_;
 allocator_type allocator_;
};

Here's a silly example of how to use it.

If it proves to be useful, I'll put it up on GitHub in a more sensible way.

Please let me know if you see any issues with it, or feel things could be done smarter!

• Arjan: at least one issue was pointed out in the original thread: stackoverflow.com/a/22963691/1078274 another issue I have since identified is the fact that there can be race conditions when destroying nodes

Answer 1

Herb Sutter has written a series of articles about lock-free queues:

• "Lock-Free Code: A False Sense of Security": explaining why STL containers are not suitable for lock-free code.

• "Writing a Generalized Concurrent Queue": a supposedly lock-free multi-producer multi-consumer queue that does contain two mutexes.

A reason that the approach that you and Herb are using cannot be truly lock-free in the multi-producer or -consumer case is that both the start_ or end_ variables and the start or end of the list need to be changed in a single atomic operation, which is not possible on existing architectures. I wonder if an implementation without start_ and end_ variables, where each thread traverses the queue by itself, could work?

• Travis Snoozy: What you can do is swap pointers, and replace the entire structure that needs to be under atomic control by precalculating your change, and then executing the swap transaciton if and only if no changes occurred. (i.e., put start_ and end_ in an allocated struct, atomic-read the pointer to that struct, calculate new structure, atomic-exchange with expected-old-ptr/calculated-new-ptr). This is still technically "lock free," but you MUST use pointers.