Ringbuffer
Source Files
└───liblfds711
├───inc
│ └───liblfds711
│ lfds711_ringbuffer.h
└───src
└───lfds711_ringbuffer
lfds711_ringbuffer_cleanup.c
lfds711_ringbuffer_init.c
lfds711_ringbuffer_internal.h
lfds711_ringbuffer_query.c
lfds711_ringbuffer_read.c
lfds711_ringbuffer_write.c
Enums
enum lfds711_ringbuffer_query;
Opaque Structures
struct lfds711_ringbuffer_element; struct lfds711_ringbuffer_state;
Macros
#define LFDS711_RINGBUFFER_GET_USER_STATE_FROM_STATE( ringbuffer_state )
Prototypes
void lfds711_ringbuffer_init_valid_on_current_logical_core( struct lfds711_ringbuffer_state *rs, struct lfds711_ringbuffer_element *re_array, lfds711_pal_uint_t number_elements, void *user_state ); void lfds711_ringbuffer_cleanup( struct lfds711_ringbuffer_state *rs, void (*element_cleanup_callback)(struct lfds711_ringbuffer_state *rs, void *key, void *value, enum lfds711_misc_flag unread_flag) ); int lfds711_ringbuffer_read( struct lfds711_ringbuffer_state *rs, void **key, void **value ); void lfds711_ringbuffer_write( struct lfds711_ringbuffer_state *rs, void *key, void *value, enum lfds711_liblfds_flag *overwrite_occurred_flag, void **overwritten_key, void **overwritten_value ); void lfds711_ringbuffer_query( struct lfds711_ringbuffer_state *rs, enum lfds711_ringbuffer_query query_type, void *query_input, void *query_output );
Overview
This data structure implements a ringbuffer. It supports any number of concurrent users, and internally implements exponential backoff to help deal with high load and so improve scalability. The ringbuffer "type" is that an element written into the ringbuffer is read by one and only one reader.
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.
General usage is that the user calls lfds711_ringbuffer_init_valid_on_current_logical_core to initialize a struct lfds711_ringbuffer_state, and then calls lfds711_ringbuffer_read and lfds711_ringbuffer_write to read and write key/value pairs. The key is not used in any way by the ringbuffer (and of course the value neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key. The ringbuffer requires a dummy element, so the call to init when providing store for ringbuffer elements must pass in an extra element; the count of elements passed into the init function includes the dummy element, i.e. it is the actual number of elements in the array.
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)
The state and element structures are both public, present in the lfds711_ringbuffer.h header file, so that users can embed them in their own structures (and where necessary pass them to sizeof). This approach permits zero run-time allocation of store and also ensures the stack element is normally in the same memory page as the user data it refers to.
When a read is performed, the reader receives a copy of the key and value in the read element. That element then by the act of being read becomes available for writing to. If we imagine then a use case where the ringbuffer is having audio buffers placed into it, then there needs to be a freelist of audio buffers, where when a buffer is needed it is popped from the freelist, filled, and then a pointer to it is placed into the ringbuffer. A reader will in time come to read that element and obtain that pointer. If a writer however overwrites an element before it is read, the writer will be given the key and value pair that have been overwritten (so that something can be done with them).
Lock-free Specific Behaviour
The state initialization function, lfds711_ringbuffer_init_valid_on_current_logical_core, as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE, which will do that which its name suggests.
White Paper
There is no white paper for this data structure; it is native to liblfds.
The internal design is actually a freelist and a queue. When the ringbuffer is initialized, and all the elements are present but unwritten to, they are all in the freelist. When an element is "written" to, it is popped from the freelist, given its key and value, and placed in the queue. When an element is "read", it is dequeued from the queue. If when writing, there are no elements in the freelist, an element is dequeued from the queue - this is the act of overwriting the oldest unread element.
License
The ringbuffer consists of a stack and a queue. These have their own licenses; the stack has the standard liblfds license. The queue license is unclear - the design comes from the 1998 white paper by Michael and Scott. No patent is known, and the queue is widely used - Java uses it, for example, for ConcurrentLinkedQueue.
Example
#include <stdio.h>
#include <stdlib.h>
#include "liblfds711.h"
int main()
{
enum lfds711_misc_flag
overwrite_occurred_flag;
int long long unsigned
loop,
overwrite_count = 0;
struct lfds711_ringbuffer_element
*re;
struct lfds711_ringbuffer_state
rs;
void
*key;
// TRD : ten elements, plus one extra for the necessary dummy element
re = malloc( sizeof(struct lfds711_ringbuffer_element) * 11 );
lfds711_ringbuffer_init_valid_on_current_logical_core( &rs, re, 11, NULL );
// TRD : the ringbuffer has ten elements, we write fifteen times; we will overwrite the first five elements
for( loop = 0 ; loop < 15 ; loop++ )
{
lfds711_ringbuffer_write( &rs, (void *) (lfds711_pal_uint_t) loop, NULL, &overwrite_occurred_flag, NULL, NULL );
if( overwrite_occurred_flag == LFDS711_MISC_RAISED )
overwrite_count++;
}
if( overwrite_count != 5 )
printf( "Oh bugger!\n" );
for( loop = 0 ; loop < 10 ; loop++ )
{
lfds711_ringbuffer_read( &rs, &key, NULL );
// TRD : this will print 5 to 14
printf( "key = %llu\n", (int long long unigned) key );
}
lfds711_ringbuffer_cleanup( &rs, NULL );
free( re );
return( EXIT_SUCCESS );
}