Ring buffer with non-atomic reads and writes

Question

Context: Real-time embedded ARM microcontroller.

Writing a lock-free, wait-free SPSC ring buffer is straight forward if the data in the buffer can be read or written atomically. But, in many cases, the buffer needs to be read over many ops, or written through many ops. How can a SPSC lock-free ring buffer be implemented? (The goal is for the ring-buffer to overwrite oldest data on overflow, not block.)

Imagine that the read of entry N is in process. Now, the write pointer catches up to N. If the read of N hadn't started, we'd simply overwrite N, and advance the read ptr to N+1; N becomes the last entry (most recently written) and N+1 the first entry (least recently written). But, now, since the read is in progress, we don't want to overwrite N. Instead, we need to make the write ptr N + 1 and the read ptr N + 2.

Likewise, if the write ptr is at N, and the read ptr advances to N-1. If the write to N-1 is complete, we can read N-1. But what if the write is in progress.

It seems like in addition to write ptr and read ptr, we also need to know if write is in progress and read is in progress. However, using those two extra information to construct invariants that keep the ring buffer correct is very difficult.

Questions:

For a lock-free, wait-free, SPSC ring buffer with overflow, that does not allow reading an item until write is complete, and does not allow overwriting an item that is in progress of reading:

1. What data do we need (besides read ptr and write ptr)?
2. What invariants apply to that data?
3. How do we use that to construct the buffer?

Answer 1

I'm not sure what exactly you're looking for and it's not clear what you mean by non-atomic reads/writes. However, I think you can implement such a data structure using sequence locks.

Both the reader and the writer maintain their own current item pointers.

Each item has an associated sequence number, which is initially zero. The writer first increments the sequence number of the item it wishes to overwrite (setting some odd value). Then it modifies the item. Finally, the writer increments the sequence number one more time (setting it to the next even value), and progresses to the next item.

On the other hand the reader starts by checking the sequence number of the current item. If the number is odd, the item is being modified right now, so the reader goes to item no. N+1. Otherwise, the reader makes a copy of the item's data and then checks the sequence number one more time. If the number didn't change in the meantime, the reader reads the copy made a moment ago. If it did change, the reader discards the copy and goes to item no. N+1.

Additionally, if the sequence number is even, the reader may also check if it's not too big, which can occur when the writer has advanced past the reader and already finished writing. For that the reader keeps an epoch number, initially two (assuming zero means an empty item), and increases it by two after each full buffer was read. The reader only reads items whose sequence number is equal to the current epoch, and progresses forward to the next item every time it sees an item from the next epoch too early.

This is a little bit different than what you requested, because you said you don't want to interrupt the reader, but want the writer to skip to N+1 directly when a read is in progress, but I don't understand what's the point of this requirement. A read of a single item can be considered to be executed instantaneously if the copy of data is already made, so it cannot be interrupted. If the approach given above does not satisfy your goals, please provide more details about what you expect from the buffer (besides it being non-blocking, and the writer overwriting on overflow).

Answer 2

For single-producer, single-consumer, the simplest way to handle these sorts of things is to add another bit to the write pointer. Shift it to the left, and then use bit 0 to indicate that the write to this item is in progress.

The write operation then looks like this:

1. Atomically set the low bit on the write pointer to indicate that the write to the target item is in progress;
2. Write the item;
3. Atomically increment the write pointer (will clear the low bit) to indicate that the write is done and the new write pointer.

Now the guarantees you provide to the reader should be limited to what you can do with this information.

This part of your question is problematic:

Now, the write pointer catches up to N. [...] since the read is in progress, we don't want to overwrite N. Instead, we need to make the write ptr N + 1 and the read ptr N + 2.

You can manage something like this, but what useful guarantees are you providing to the reader here? Depending on the relative timing, the reader will either get a new item or an old item. Yes, you have guaranteed that the item it read is valid, but only one of those cases is going to satisfy its purpose, and so it will still need to abort or retry when it gets the wrong one.

So my suggestion is just that the reader should check the write pointer before and after the read. From the difference in the pointers, you can determine all the states that the writer went through while the read was in progress, and you can therefore know whether the item you read is new, old, or invalid.

If you really need to give the reader some item, then you can do it like this:

1. Try to read the item at the read pointer.
2. If you got an invalid item (partial overwrite), then read the next item instead;
3. If you got an invalid item, then go back and read the initial item again, because it must be done by now.
4. If it's possible that the writer is super fast and overwrote the whole buffer while you were trying to read the initial item, then it might be invalid again, so go back to (2).

But again, the extra guarantee you provide in this case is probably not really worth the extra complexity. I would be better to adjust your reader interface to indicate invalid reads.