Detecting invalid iterators for a circular buffer
I am trying to implement a circular buffer (or circular buffer). As with most of these implementations, it should be as fast and lightweight as possible, while still providing sufficient security to be robust enough for production use. It's a tricky balance to strike. Specifically, I ran into the following problem.
I want to use the specified buffer to store the last n system events. As new events come to the oldest, they are removed. Other parts of my software can then access those stored events and process them at their own pace. Some systems can consume events almost as quickly as they arrive, others can only check sporadically. Each system will store the iterator in a buffer so they know where they left off the last time they checked. This is not a problem as they often check quite often, but especially slow systems can often encounter an old iterator that points to a buffer item that has since been overwritten without being able to detect it.
Is there a good (not too expensive) way to check if any given iterator is preserved?
Things I have come up with so far:
- keep a list of all iterators and keep their actual state (quite expensive)
- stores not only the iterator in the calling systems, but also a copy of the sharpened element in the client buffer. On each access, check if the element remains the same. It may not be reliable. If an item has been overwritten by an identical item, it is impossible to check whether it has changed or not. Also, it is the client's responsibility to find a good way to validate elements, which is not ideal for me.
Many buffer buffer implementations don't bother with this at all or use the one-read-one-write idiom where the read is deleted.
source to share
I agree with Roger Lipscomb , use serial numbers.
But you don't need to store (value, sequence_num) pairs: just store the values and keep track of the highest ordinal so far. Since this is a circular buffer, you can print seq num for all records.
Thus, iterators are simply composed of an ordinal.
Given the Obj
type of object you store in a circular buffer, if you are using a simple array, your buffer buffer will look like this:
struct RingBuffer {
Obj buf[ RINGBUFFER_SIZE ] ;
size_t idx_last_element ;
uint32_t seqnum_last_element ;
void Append( const Obj& obj ) { // TODO: Locking needed if multithreaded
if ( idx_last_element == RINGBUFFER_SIZE - 1 )
idx_last_element = 0 ;
else
++idx_last_element ;
buf[ idx_last_element ] = obj ; // copy.
++ seqnum_last_element ;
}
}
The iterator will look like this:
struct RingBufferIterator {
const RingBuffer* ringbuf ;
uint32_t seqnum ;
bool IsValid() {
return ringbuf &&
seqnum <= ringbuf->seqnum_last_element &&
seqnum > ringbuf->seqnum_last_element - RINGBUFFER_SIZE ; //TODO: handle seqnum rollover.
}
Obj* ToPointer() {
if ( ! IsValid() ) return NULL ;
size_t idx = ringbuf->idx_last_element - (ringbuf->seqnum_last_element-seqnum) ; //TODO: handle seqnum rollover.
// handle wrap around:
if ( idx < 0 ) return ringbuf->buf + RINGBUFFER_SIZE- idx ;
return ringbuf->buf + idx ;
}
}
source to share
Store pairs instead of storing values (value, sequence_num)
. When you press a new one value
, always make sure it is using the other one sequence_num
. You can use a monotonically increasing integer for sequence_num
.
The iterator then remembers the sequence_num
item it last looked at. If it doesn't match, it has been overwritten.
source to share
A variation on Roger Lipscomb 's answer is to use an ordinal as an iterator. The sequence number must be monotonically increasing (pay special attention to when an integer overflow occurs) with a fixed step (for example, 1).
The ring buffer itself will store the data as normal and keep track of the oldest sequence number it currently contains (at the tail position).
When dereferencing an iterator, the iterator sequence number is checked against the most significant sequence number of the buffer. If it is greater than or equal to (again, be especially careful about integer overflow), the data can be retrieved with a simple index computation. If it is less, it means that the data has been overwritten, and instead you need to retrieve the current tail data (update the iterator ordinal accordingly).
source to share