[Boost-users] circular buffer in a multithreaded program

Subject: [Boost-users] circular buffer in a multithreaded program
From: Sebastian Gesemann (s.gesemann_at_[hidden])
Date: 2014-04-22 07:47:06

Hello!

I had some troubles with using boost::circular_buffer in a
multithreaded application and I'm not really sure whether I actually
ran into a bug or wether I expected just too much that wasn't promised
in the thread-safety section.

Anyhow, I wanted to share my story and a theory of what possibly went
wrong. Maybe this posting even contains some ideas of how
circular_buffer could be made a little more thread-safe without ading
any mutex- or atomics-based synchronization.

What I tried to do: I tried to grant one thread write access to a
sub-range in a circular_buffer while another thread had read-access to
a non-overlapping sub-range. At no time any capacity change was
needed. Occasionally, in a reader thread I would "consume" some of the
values that were already "committed" by a writer and make more room
for the writer to store new data by

  - locking a mutex
  - calling cb.erase_first(n);
  - calling cb.resize(cb.capacity());
  - notify writer that there is new free space to write stuff into
  - unlocking the mutex

As for iterator invalidation, erase_first just invalidates iterators
to the elements being removed. And resize in this case just increases
the size again to the capacity which should not invalidate any
iterators If I understand correctly.

But the program did not work. The first thing that came to my
attention was that the checked iterators of circular_buffer don't
support this kind of multithreading as they register and unregister
themselves into a linked list without any synchronization.

But even after disabling the checked iterators via
BOOST_CB_DISABLE_DEBUG, the program still did not work. I could not
figure out why (with enough certainty) and eventually replaced
circular_buffer with a custom vector-based data structure.

My guess is that the iterators of a circular_buffer somehow depend on
some part of the state of the buffer that is modifed by erase_first.
Then, I would have a data race. But such a dependency does not really
have to be there. In my own implementation, an iterator is
"self-sufficient" in the sense that it does not need to access any of
the buffer's state (indices, counters and whatnot) to access the right
elements. And this way, erasing some unneeded elements from the buffer
while some other thread still works on other values in the buffer via
iterators does not cause a data race. In my opinion, it's reasonable
to expect something like this to work using a circular_buffer.

Maybe someone knows more about how circular_buffer iterators are
implemented and/or wants to improve the circular_buffer implementation
w.r.t. thread-safety to support this kind of use. Since I switched to
a custom data structure that is able to deal with this situation, I
did not investiage this issue with circular_buffer any further. I
already lost about a day because of this.

I hope, this is of interest to somebody who wants to avoid exessive
copying in the standard "producer-consumer / bounded-buffer pattern".

Cheers!
Sebastian