r6.1.1:lfds611_ringbuffer

Source Files

/liblfds611/src/lfds611_ringbuffer/lfds611_ringbuffer_delete.c
/liblfds611/src/lfds611_ringbuffer/lfds611_ringbuffer_get_and_put.c
/liblfds611/src/lfds611_ringbuffer/lfds611_ringbuffer_new.c
/liblfds611/src/lfds611_ringbuffer/lfds611_ringbuffer_query.c
/liblfds611/src/lfds611_ringbuffer/lfds611_ringbuffer_internal.h
/liblfds611/inc/liblfds611.h

Incomplete Types

struct lfds611_ringbuffer_state;

Enums

enum lfds611_ringbuffer_query_type
{
  LFDS611_RINGBUFFER_QUERY_VALIDATE
};

Prototypes

int lfds611_ringbuffer_new( struct lfds611_ringbuffer_state **rs, lfds611_atom_t number_elements,
                            int (*user_data_init_function)(void **user_data, void *user_state),
                            void *user_state );
void lfds611_ringbuffer_use( struct lfds611_ringbuffer_state *rs );
void lfds611_ringbuffer_delete( struct lfds611_ringbuffer_state *rs,
                                void (*user_data_delete_function)(void *user_data, void *user_state),
                                void *user_state );

struct lfds611_freelist_element *lfds611_ringbuffer_get_read_element( struct lfds611_ringbuffer_state *rs, struct lfds611_freelist_element **fe );
struct lfds611_freelist_element *lfds611_ringbuffer_get_write_element( struct lfds611_ringbuffer_state *rs, struct lfds611_freelist_element **fe, int *overwrite_flag );

void lfds611_ringbuffer_put_read_element( struct lfds611_ringbuffer_state *rs, struct lfds611_freelist_element *fe );
void lfds611_ringbuffer_put_write_element( struct lfds611_ringbuffer_state *rs, struct lfds611_freelist_element *fe );

void lfds611_ringbuffer_query( struct lfds611_ringbuffer_state *rs, enum lfds611_ringbuffer_query_type query_type, void *query_input, void *query_output );

Overview

Yes, you read it right - the ringbuffer returns lfds611_freelist_elements. Think of say a connection class returning instances of socket classes. I could have done a bunch of extra code to disguise this and make it look like ringbuffer elements, but it's messy and has no other benefit and the fact is these elements are what they are and I'm assuming the user here is going to be a good enough programmer to handle without going crazy the idea of an API instantiating and returning publically defined entities from another API. It's not rocket science! The freelist in use is not your own - it's internal to the ringbuffer. All you do is what you would normally do, instantiate a ringbuffer.

This API implements a ringbuffer. A new ringbuffer is instantiated by the lfds611_ringbuffer_new function, where the argument number_elements is the number of elements in the ringbuffer. The caller then uses the ringbuffer by reading or writing, via the lfds611_ringbuffer_get_read_element, lfds611_ringbuffer_get_write_element, lfds611_ringbuffer_put_read_element and lfds611_ringbuffer_put_write_element functions, respectively; which is to say the caller gets a read element, reads the user data from it and then puts the element back (not as a data bearing element, but rather for future use by the ringbuffer to service requests for write elements, otherwise you'd leak an element) and likewise, gets a write element, sets the user data in it and then puts that write element into the ringbuffer (in this case, that element being a proper data bearing element which will eventually be read from the ringbuffer).

The get and put operations get and put single lfds611_freelist_elements, each of which contain a single void pointer of user data, which is read and written using the functions lfds611_freelist_get_user_data_from_element and lfds611_freelist_get_user_data_from_element, respectively. These void pointers are expected to point to user allocated state although of course they can be used directly to store a single value.

These freelist elements come from a freelist which is internal to the ringbuffer; you merely see the elements. You have nothing to do with the instantiation or cleanup of the freelist.

Finally, the ringbuffer is deleted using lfds611_ringbuffer_delete.

This API implements the semantics of a multiple reader, multiple writer ringbuffer where all readers read from the single read point and all writers write to the single write point. When a read occurs, by any thread, the read point moves ahead by one element. As such, each element placed into the ringbuffer is read once, by a single thread, rather than each element being read once by each reading thread (which is what occurs when each reading thread maintains its own read point).

Semantics

There are a number of variations in ringbuffer semantics, revolving around whether single or multiple readers and/or writers are supported and the way in which they are supported.

Single reader, single writer ringbuffer semantics are that there are fixed, finite number of elements arranged in a ring; that there is a reader and a writer which begin pointing at the same element; that the reader can read up to the writer but no further; that the writer can reach the reader and when doing so, bumps the reader forward by one, which has the effect to destroying one element of data, since that data has been over-written before it was read.

It is then possible to have multiple readers and a single writer, but there are two variants; firstly, that although there are multiple readers, they all read from the current read element - which is to say, they do not maintain individual positions in the ringbuffer - secondly, that there are multiple readers and they all do indeed maintain their own individual positions in the ringbuffer (so, for example, whenever the writer catches up to a reader, must bump that particular reader forward by one).

In the first variant, where all readers read from the current read element, each element is only read by a single reader. In the second variant, where readers maintain their own individual positions in the ringbuffer, all elements are read by all readers.

It is possible to have multiple writers (regardless of the number of type of readers), but this always means that all writers write at the current write element; if writers maintained their own individual write positions in the ringbuffer, there would be much unpredictable over-writing of elements.

As far as I know, there is no lock-free algorithm which implements a ringbuffer (of any kind). However, the semantics of a multiple reader, multiple writer ringbuffer where all readers read from the single read point and all writers write to the single write point can be duplicated by combining a freelist and a queue and lock-free algorithms exist for both freelists and queues.

Read/writing elements safety without locks

In a locking ringbuffer, a reader or writer can hold a lock on an element to ensure the read or write operation is performed safely, without being interference from other writers. Locking is not available in a lock-free algorithm. The solution here is that to perform a read, the current read element is detached from the ringbuffer and given to the reader, who, once reading is complete, returns it to the ringbuffer; and to perform a write, the writer detaches an unused element from the ringbuffer, populates it, and then attaches it to the ringbuffer at the current write position.

The elements, by being detached from the ringbuffer, become secure; they cannot be accessed (and so potentially overwritten) by other threads.

Usage

When a writer wishes to write, he calls lfds611_ringbuffer_get_write_element. This function detaches the current write element from the ringbuffer. If the ringbuffer is full, the element detached will be the oldest unread element, causing data loss. If the ringbuffer is not full, an element is taken from the internal freelist to service this request. The caller then populates the element with user data and then calls lfds611_ringbuffer_put_write_element; by doing so, the element then enters the ringbuffer as its newest element and will in its turn be read by a reader.

When a reader wishes to read, he calls lfds611_ringbuffer_get_read_element. This function detaches the current read element from the ringbuffer. If there are no read elements - the reader is up to the current write element - the function will return NULL. Assuming an element is obtained, the reader reads the element and then when he is done calls lfds611_ringbuffer_put_read_element, which returns the element to the ringbuffer internal freelist for future use.

Lock-free Specific Behaviour

Any number of readers and writers can operate in parallel. Since a thread after a get temporarily removes an element from the ringbuffer, the number of elements in the ringbuffer should be equal to the number you wish for, plus one per outstanding concurrent get operation.

Algorithm

The ringbuffer blends a freelist and a queue. The freelist used implements Treiber's stack algorithm. The queue used implements Maged M. Michael and Michael L. Scott's queue algorithm, from their 1996 paper, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms".

At initialisation, the freelist is fully populated and the queue empty. When a writer wishes to write, he obtains an element from the freelist, populates that element with data and places it into the queue. When a reader wishes to read, he dequeues. Multiple writers therefore appear to be writing serially at the write element; multiple readers all read serially from the read point. If a writer wishes to write and the freelist is empty, the writer dequeues an element from the queue and uses that element. This of course causes data loss; it is the situation where a writer, in a normal ringbuffer, overtakes a reader.

In all cases, an element being read or written has been detached from the ringbuffer (by being popped from the freelist or dequeued from the queue) and so is visible only to the owning thread, ensuring thread-safety during the read or write operation.