circular_buffer.hpp File Reference

Buffer for queuing received bytes. More...

#include "types.hpp"
#include "ndebug.hpp"
#include <stddef.h>
#include <stdint.h>
#include <array>
#include <bit>
#include <optional>
#include <type_traits>
#include <utility>
#include "debug_end.hpp"

Go to the source code of this file.

Classes
class	CircularBuffer< Value, Size, MaxPacketSize >
class	CircularBuffer< Value, Size, MaxPacketSize >::Iterator
class	CircularBuffer< Value, Size, MaxPacketSize >::Frame

Detailed Description

Buffer for queuing received bytes.

Circular buffer

As data arrives in the interrupt of the driver, it needs to be queued for an application thread to process it. This class is a simple circular buffer that can support either bytes for a pre-allocated buffer, or pointers for a dynamically sized buffer.

Though because it includes the size of the data, it is optimised for storing data not pointers – as it would just waste half of the space for pointers as size of a pointer is known. This is done because even though we know the total readable size of the buffer, the buffer might contain multiple packets, and we want to know where each packet starts and ends.

The basis of the circular buffer is based on the Lamport Queue, the basic Lamport Queue uses two cursors, one for read and one for write, and a buffer which is a size of power of two (see XXX). It is a concurrent, single producer single consumer queue, which means there are some subtle considerations:

1. the queue may be pushed to and popped from concurrently (though not pushed by multiple different threads concurrently, or popped from concurrently);
2. because the queue size is a power of two, the difference between the write and read cursors is always valid even if one or both of them have wrapped. Strictly speaking the requirement is that the queue size and the cursors wrap to zero at the same time, but it is easiest to acheive by having the cursors wrap naturally at a power of two, and having the queue size a power of two is probably not a huge restriction.

The modification we have done to the standard Lamport Queue is having another cursor which is always bounded by the read and write cursors, and is used to keep track of where the next packet is which we haven't notified the consumer of. This allows us to store the length of the packet at the start of the packet, and also to drop packets which cannot fit into the buffer.

This does mean that we need to know how big a packet can be (specifically, how many bytes to allocate for the packet size pointer), but this is fine for now.

Todo

Currently this was written for architectures which don't reorder reads/writes, in my case small microcontrollers without caches and write buffers, but needs to be fixed by using atomics on the cursors and the buffer to ensure the cursors point to valid data (by the time the updated cursor is read, the value at that location has been written).

Todo

This does not expose an interface for DMA engines, but this could fairly easily be added by getting the current next contiguous unused part of the buffer (i.e. the part before any wrapping) and passing that to the DMA engine.

Todo

Forward and bidirectional iterator/range for Iterator/Frame.