Ringbuffer

From liblfds.org
Revision as of 20:16, 17 February 2017 by Admin (talk | contribs) (1 revision imported)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 );
}

See Also