Circular Buffer Libraries inside the Nordic NRF5 SDK

In this blog, I would like to describe 3 difference libraries as the circular buffer inside the Nordic NRF5 SDK.

  • app_fifo (app_uart_fifo)
  • nrf_ringbuf (official release after SDK 15.0, ble_cli_uart module uses this library)
  • nrf_queue

Ring Buffer

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as a FIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a linked list approach may be preferred instead.

In some situations, overwriting circular buffer can be used, e.g. in multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Also, the LZ77 family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in the stream. Implementations store the most recent data in a circular buffer.

https://en.wikipedia.org/wiki/Circular_buffer

The libraries have been developed over time for similar use cases. The best is to look at them and find which quits you, but here is a short list of differences:

  • app_fifo does not use atomic operations or critical sections, so it is not thread safe.
  • nrf_queue and nrf_ringbuf handle this, but do it differently.
  • nrf_ringbuf use atomic operations using nrf_atomic, which uses LDREX/STREX. this is probably the best for most use cases. It uses arbitrary sized elements / objects.nrf_queue si a older library, that is extensively used in SDK libraries and examples. It uses critical sections. It uses fixed size elements.

Usage

  • nrf_queue use fixed size elements.
  • nrf_ringbuf on the other hand can handle elements of varying size.
  • app_fifo operate on byte elements, but provides ways to read and write chunks as well.

The nrf_ringbuf library is a better app_fifo, and the queue library incorporates an abstraction layer that handles things like putting structs and arrays and considers them as single elements.

nrf_ringbuf

  • void nrf_ringbuf_init (nrf_ringbuf_t const *p_ringbuf)
  • ret_code_t nrf_ringbuf_alloc (nrf_ringbuf_t const *p_ringbuf, uint8_t **pp_data, size_t *p_length, bool start)
  • ret_code_t nrf_ringbuf_put (nrf_ringbuf_t const *p_ringbuf, size_t length)
  • ret_code_t nrf_ringbuf_cpy_put (nrf_ringbuf_t const *p_ringbuf, uint8_t const *p_data, size_t *p_length)
  • ret_code_t nrf_ringbuf_get (nrf_ringbuf_t const *p_ringbuf, uint8_t **pp_data, size_t *p_length, bool start)
  • ret_code_t nrf_ringbuf_free (nrf_ringbuf_t const *p_ringbuf, size_t length)
  • ret_code_t nrf_ringbuf_cpy_get (nrf_ringbuf_t const *p_ringbuf, uint8_t *p_data, size_t *p_length)

https://infocenter.nordicsemi.com/topic/com.nordic.infocenter.sdk5.v15.2.0/lib_ringbuf.html

Initialization

The NRF_RINGBUF_DEF macro creates an instance of the ring buffer. The size of the ring buffer must be a power of 2. It must be first initialized before it can be used.

NRF_RINGBUF_DEF(m_ringbuf, 256);
void foo(void)
{
    nrf_ringbuf_init(&m_ringbuf);
}

Access through copying

Data can be copied into the ring buffer using nrf_ringbuf_cpy_put. If another ‘put’ operation on the instance was interrupted, the attempt returns NRF_ERROR_BUSY. The nrf_ringbuf_cpy_put function returns the amount of data written to the buffer. It can be smaller than requested if there is no space available to copy all data.

Data can be copied out from the ring buffer using nrf_ringbuf_cpy_get. If another ‘get’ operation on the instance was interrupted, the attempt returns NRF_ERROR_BUSY. The nrf_ringbuf_cpy_get function returns the amount of data read from the buffer. It can be smaller than requested if there is less data available to copy.

void foo(void)
{
    ret_code_t err_code;
    uint8_t data_in[] = {1,2,3,4};
    uint8_t data_out[5];
    size_t  len_in = sizeof(data_in);
    size_t  len_out = sizeof(data_out);
    err_code = nrf_ringbuf_cpy_put(&m_ringbuf, data_in, &len_in);
    err_code = nrf_ringbuf_cpy_get(&m_ringbuf, data_out, &len_out);
    ASSERT(len_out == len_in);
    ASSERT(memcmp(data_in, data_out, sizeof(data_in)) == 0);
} 

Direct access to the memory

The ring buffer library allows for working directly on the memory within the buffer. A portion of the buffer can be allocated for use. Once used, it can be put back (the put amount can be smaller than the allocated one). A similar approach can be used for getting data from the buffer. You can get it and then free it. The amount of freed data can be smaller than the one that was got.

Putting data to the ring buffer consists of the following steps.

  1. Request allocation of N bytes (nrf_ringbuf_alloc) – get M (where M <= N) bytes and the pointer to the buffer. M is smaller or equal to N.
  2. Write P bytes to the buffer where P is smaller or equal to M.
  3. Indicate to the ring buffer that P bytes are valid (nrf_ringbuf_put).
void foo(void)
{
    uint8_t * p_buffer;
    size_t    len = 16;
    // Allocate buffer for uart RX
    err_code = nrf_ringbuf_alloc(&m_ringbuf, &p_buffer, &len, true);
    // Start uart RX. Uart driver has inactivity timeout and returns on receiving requested amount of bytes or less.
    size_t rx_len = uart_rx(p_buffer, len);
    //Indicate number of valid bytes in the ring buffer
    err_code = nrf_ringbuf_put(&m_ringbuf, rx_len);
}

Getting data from the ring buffer consists of the following steps:

  1. Attempt to get N bytes of data from the ring buffer (nrf_ringbuf_get) – get M (where M <= N) bytes and the pointer to the buffer.
  2. Process P bytes of data where P is smaller or equal to M.
  3. Indicate to the ring buffer that P bytes can be freed (nrf_ringbuf_free).
void foo(void)
{
    uint8_t * p_buffer;
    size_t    len = 16;
    // Get available data from the buffer 
    err_code = nrf_ringbuf_get(&m_ringbuf, &p_buffer, &len, true);
    // Process data
    size_t processed_len = packet_process(p_buffer, len);
    //Indicate number of bytes that can be freed
    err_code = nrf_ringbuf_free(&m_ringbuf, processed_len);
}

Access to the ring buffer can be exclusive. It means that an attempt to allocate another buffer between nrf_ringbuf_alloc and nrf_ringbuf_put or an attempt to get data from the ring buffer between nrf_ringbuf_get and nrf_ringbuf_free can be detected. However, it is also possible to allocate or get more data with disabled exclusion check.

ret_code_t foo2(void)
{
    uint8_t * p_buffer;
    size_t    len = 16;
    err_code = nrf_ringbuf_alloc(&m_ringbuf, &p_buffer, &len, exclusive); 
    if (err_code == NRF_SUCCESS)
    {
        //Write data
        err_code = nrf_ringbuf_put(&m_ringbuf, len);
    }
    else
    {
        return err_code;
    }
}
void foo(void)
{
    uint8_t * p_buffer;
    uint8_t * p_buffer2;
    size_t    len  = 16;
    size_t    len2 = 16;
    // Allocate buffer 
    bool exclusive = true;
    err_code = nrf_ringbuf_alloc(&m_ringbuf, &p_buffer, &len, exclusive); 
    err_code = foo2(); //NRF_ERROR_BUSY is returned
    // Allocate more data without access control
    err_code = nrf_ringbuf_alloc(&m_ringbuf, &p_buffer2, &len2, false);
    //Write data
    err_code = nrf_ringbuf_put(&m_ringbuf, len + len2);
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.