cbuff.h Circular Byte Buffer For Embedded Applications

Malloc free, minimum overhead implementation of a circular buffer.

Static inlined handlers for speed and ease of usage in various projects.

This is based on harshkn's circular buffer: https://gist.github.com/harshkn/909546

Design Considerations Applied

• Favor index approach over pointer approach

  • This is because I previously written a circular buffer implementation in github gist as Pointer Approach vs Index Approach
  • According to GodBolt compiler explorer, index approach has less lines of code over pointer approach. Pointer Approach vs Index Approach
  • This might be due to the need to copy over the pointer address value to the main register

• This circular buffer uses a bunch of strategies to be more thread safe

  • Use of volatile keyword to avoid compilation optimization of the head and tail pointers
  • Reader and Writer function usage of the head and tail volatile values are atomic and separated.

• Functions are static inlined so that it's easier to include in various project as a header file

• Functions are written in such a way that each function can be deleted if developer seeks to simplify the code for easier review by removing unused code for their project

• Malloc free. You can easily add it in externally if you really need to anyway via your own a wrapper function. By excluding it, it would be easier to integrate in microcontroller projects.

• Some circular buffer implementation has fixed buffer predefined. Opted against it to ensure this code can be used for multiple different buffer to reduce code size. Also it's not too hard for users to directly edit with capacity value hardcoded.

Circular Buffer In Memory Representation

  0                                      X Capacity
 [ ][ ][ ][ ][ ][D][C][B][A][ ][ ][ ][ ][ ]
                 |--->>---|
                HEAD     TAIL
               INPUT     OUTPUT

This Implementation Lock Free Approach (No Mutex Thread Safety)

The issue with wrapping the index by X for empty/full detection (e.g. god233012yamil/Circular-Buffer implementation uses this approach) is that to maintain lock free thread safety you would need to leave one slot free to disambiguate between the full and empty state.

We can solve this issue by projecting the index beyond X so we have a virtual index beyond our memory capacity. The actual reading/writing of memory slots is still between 0 to X, however our buffer size count will be projected across a virtual buffer twice the actual capacity.

How this helps with determining full/empty state is that the TAIL index and the HEAD index will never overlap

  0                             X :X+0                           2*X
 [B][A][ ][ ][ ][ ][ ][ ][ ][ ][ ]:[ ][ ][ ][ ][ ][ ][ ][ ][ ][D][C]
 >---|                            :                            |--->
     TAIL                         :MIRRORED                    HEAD
     OUTPUT                       :INDEX                       INPUT

Other Circular Buffer Implementations To Consider

• god233012yamil/Circular-Buffer
  • Appreciated god233012yamil's Technical Writeup since I learned more about consideration needed to add lock-free thread safety.
  • Ultimately opted against this approach as it relies on a slot that must always remain empty to ensure clear disambiguation between empty and full buffer state (one slot empty).

Recommended Readings

• https://www.codeproject.com/articles/43510/lock-free-single-producer-single-consumer-circular
• https://andrea.lattuada.me/blog/2019/the-design-and-implementation-of-a-lock-free-ring-buffer-with-contiguous-reservations.html

History:

Originally from:

• This Gist (Pointer): https://gist.github.com/mofosyne/d7a4a8d6a567133561c18aaddfd82e6f
• This Gist (Index): https://gist.github.com/mofosyne/82020d5c0e1e11af0eb9b05c73734956