Ringbuffer

Source Files

└───liblfds700
    ├───inc
    │   └───liblfds700
    │           lfds700_ringbuffer.h
    └───src
        └───lfds700_ringbuffer
                lfds700_ringbuffer_cleanup.c
                lfds700_ringbuffer_init.c
                lfds700_ringbuffer_internal.h
                lfds700_ringbuffer_query.c
                lfds700_ringbuffer_read.c
                lfds700_ringbuffer_write.c

Enums

enum lfds700_ringbuffer_query
{
  LFDS700_RINGBUFFER_QUERY_SINGLETHREADED_GET_COUNT,
  LFDS700_RINGBUFFER_QUERY_SINGLETHREADED_VALIDATE
};

Opaque Structures

struct lfds700_misc_prng_state;
struct lfds700_ringbuffer_element;
struct lfds700_ringbuffer_state;

Macros

#define LFDS700_RINGBUFFER_GET_USER_STATE_FROM_STATE( ringbuffer_state )

Prototypes

void lfds700_ringbuffer_init_valid_on_current_logical_core( struct lfds700_ringbuffer_state *rs,
                                                            struct lfds700_ringbuffer_element *re_array_inc_dummy,
                                                            lfds700_pal_uint_t number_elements,
                                                            struct lfds700_misc_prng_state *ps,
                                                            void *user_state );

void lfds700_ringbuffer_cleanup( struct lfds700_ringbuffer_state *rs,
                                 void (*element_cleanup_callback)(struct lfds700_ringbuffer_state *rs, void *key, void *value, enum lfds700_misc_flag unread_flag) );

int lfds700_ringbuffer_read( struct lfds700_ringbuffer_state *rs,
                             void **key,
                             void **value,
                             struct lfds700_misc_prng_state *ps );

void lfds700_ringbuffer_write( struct lfds700_ringbuffer_state *rs,
                               void *key,
                               void *value,
                               enum lfds700_liblfds_flag *overwrite_occurred_flag,
                               void **overwritten_key,
                               void **overwritten_value,
                               struct lfds700_misc_prng_state *ps );

void lfds700_ringbuffer_query( struct lfds700_ringbuffer_state *rs,
                               enum lfds700_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 lfds700_ringbuffer_init_valid_on_current_logical_core to initialize a struct lfds700_ringbuffer_state, and then calls lfds700_ringbuffer_read and lfds700_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 lfds700_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, lfds700_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 LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE, which will do that which its name suggests.

The struct lfds700_misc_prng_state argument is the state for a single-threaded, fast, high quality random number generator, required by the exponential backoff code. Each thread should allocate and initialize one of these structures, and then it can be used for all API calls which take this argument.

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.

Example

#include <stdio.h>
#include "liblfds700.h"

int main()
{
  enum lfds700_misc_flag
    overwrite_occurred_flag;

  int long long unsigned
    loop,
    overwrite_count = 0;

  struct lfds700_misc_prng_state
    ps;

  struct lfds700_ringbuffer_element
    *re;

  struct lfds700_ringbuffer_state
    rs;

  void
    *key;

  lfds700_misc_library_init_valid_on_current_logical_core();

  lfds700_misc_prng_init( &ps );

  re = malloc( sizeof(struct lfds700_ringbuffer_element) * 11 );

  lfds700_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++ )
  {
    lfds700_ringbuffer_write( &rs, (void *) (lfds700_pal_uint_t) loop, NULL, &overwrite_occurred_flag, NULL, NULL, &ps );

    if( overwrite_occurred_flag == LFDS700_MISC_RAISED )
      overwrite_count++;
  }

  if( overwrite_count != 5 )
    printf( "Oh bugger!\n" );

  for( loop = 0 ; loop < 10 ; loop++ )
  {
    lfds700_ringbuffer_read( &rs, &key, NULL, &ps );
    // TRD : this will print 5 to 14
    printf( "key = %llu\n", (int long long unigned) key );
  }

  lfds700_ringbuffer_cleanup( rs, NULL );

  free( re );

  lfds700_misc_library_cleanup();

  return( EXIT_SUCCESS );
}

See Also

• Release 7.0.0 Documentation