Is it possible for Boost's lockfree queue to lose elements?

Question

I have a single-threaded application that uses boost::lockfree::queue (from Boost 1.57). (The reason I'm using the queue is that it's part of a library that's also used in a multi-threaded application.)

It appears that the queue is somehow losing elements.

The class that uses the queue behaves as follows:

• There are two separate functions that call push on the queue. There is no thread-safety logic beyond what is provided by the queue itself.
• There is one function that consumes elements from the queue; it consumes all elements, using a while(my_queue.pop(temp_element)) loop. This function is protected by a mutex to ensure that all elements go to a single consumer. However, if two duplicate elements (compared with ==) are detected in a row, the second element is skipped.

I observed that elements appeared not to be consistently propagated through the system, so using std::atomic_uints, I created some counters to check that the same number of alerts are leaving the queue as entering it:

• There are separate counters for each of the two pushing methods. We'll call these pushed_method1 and pushed_method2.

• There are separate counters for "processed" elements and "skipped" elements. We'll call these consumed and skipped. In the loop, they're updated as follows (with variables renamed, and with descriptive pseudocode in [square brackets]):

  ElementType previous{[ initialize in invalid state ]};
  while (my_queue.pop(temp_element))
  {
    if (! [ check if `previous` is valid ]
        || previous != temp_element)
    {
      [ ... log a message ]
      [ ... insert the element into a vector to be returned ]
  
      ++consumed;
    }
    else
    {
      // ... log a message
  
      ++skipped;
    }
  
    previous = temp_element;
  }
  

Following the loop, I check the state of the counters and the queue and do my sanity checking:

auto postconsume_pushed_method1 = pushed_method1.load();
auto postconsume_pushed_method2 = pushed_method2.load();
auto all_consumed = my_queue.empty();

assert(
    !all_consumed
  ||  postconsume_pushed_method1 + postconsume_pushed_method2
        == consumed + skipped);

This assertion usually passes--but it sometimes fails in my single-threaded app. (It also sometimes fails in the multi-threaded case, but I would expect focusing on the single-threaded case to simplify the problem.)

In the multi-threaded case, I could imagine that the operations are being re-ordered so that one or more loads occur after the .empty() check, but I'd hope that's not the case since I'd expect std::atomic and boost::lockfree to include memory fences for that sort of thing.

However, in the single-threaded case, this shouldn't matter, because elements should never be pushed while the app is executing the "consume" method, and the alert-queue should always be empty following the loop (since the loop won't break until pop returns false).

Am I misunderstanding something? Is there an error in my logic? Is there even a small chance that I've found a bug in boost::lockfree::queue?

Answer 1

The queue is lock-free, so that push does not block when the queue if full.

lockfree::queue::push returns a boolean telling whether the element has made it into the queue. When the queue is full push returns false, so you may like to check for this condition.