Revring: A circular buffer with zero memory waste

2015.06.18 12:00

For my purposes I just needed a simple FIFO buffer that would work well on my MSP430G2553, which lacks DMA and only has 512 bytes of RAM. Circular or ring buffers are a class of FIFO (first in/first out) buffers that were a good approach for my needs. Ring buffer implementations I researched either wasted a byte of buffer space, required extra fields or were not very performant. revring, the solution I developed, has none of these drawbacks, using just the typical head and tail field.

Update 2015-06-18 17:50 EST: As sharp minds on reddit and HN have pointed out, there are concurrency issues in this approach. In my application, revring_add_byte() runs in interrupt context while revring_remove_byte() runs in my main loop. I have patched the concurrency issue for my application only by disabling/enabling interrupts in revring_remove_byte().

revring Specification

I'll specify revring in C:

typedef struct revring_s{
	/* Pointer to buffer data */
	uint8_t* buffer;

	/* size of buffer */
	unsigned size;

	/* Indication of where to place incoming data. */
	unsigned head;

	/* Indication of where to read incoming data. */
	unsigned tail;
} revring;

/* Initialize buffer. */
void revring_init(revring* rr, uint8_t* buffer, unsigned size){
	rr->buffer = buffer;
	rr->size = size;
	rr->head = size;
	rr->tail = size;
}

/* Test if buffer is empty. */
unsigned revring_empty(const revring* rr){
	return rr->head == rr->tail;
}

/* Test if buffer is full. */
unsigned revring_full(const revring* rr){
	return rr->head == 0;
}

void revring_add_byte(revring* rr, uint8_t byte){
	assert(!revring_full(rr));

	register unsigned head_tmp = rr->head;

	/* Place byte at position preceding head. */
	--head_tmp;
	rr->buffer[head_tmp] = byte;

	/* If byte just went to position 0, wrap next head index around. */
	if(0 == head_tmp)
		head_tmp = rr->size;

	/* If next head index caught up to tail, then buffer is full. */
	if(rr->tail == head_tmp)
		head_tmp = 0;

	/* Update head index. */
	rr->head = head_tmp;
}

uint8_t revring_remove_byte(revring* rr){
	assert(!revring_empty(rr));

	register unsigned tail_tmp = rr->tail;

	/* Read byte preceding tail. */
	--tail_tmp;
	const uint8_t byte = rr->buffer[tail_tmp];

	/* Wrap next tail index around if byte was at 0. */
	if(0 == tail_tmp)
		tail_tmp = rr->size;

	/* If buffer was full before...it is no longer.
	Point head to where tail is currently.
	Disable/enable interrupts for safety. */
	__dint();
	if(revring_full(rr))
		rr->head = rr->tail;

	/* Update tail index. */
	rr->tail = tail_tmp;
	__eint();

	return byte;
}

Some superficial differences from typical ring buffer implementations are:

Normally head and tail are initialized to 0; revring initializes at the end of the buffer
Normally head and tail increment; revring indices decrement
Normally head and tail point directly to the bytes to add/remove; revring offsets them by 1
Normally 0 is a valid head index; revring reserves it as a special value
Normally 0 is a valid tail index; revring never sets the tail to 0
Normally head and tail are constrained to valid indices; revring allows head to become a reserved value

The mistake other ring buffers make is that when they are full, they redundantly store the same index twice in head and tail. Another consequence of a full buffer is if we know the value of tail, then we know the value of head of must match. So when adding a byte to a revring buffer makes it full, revring just sets its head to reserved value 0. When a byte is removed from a full buffer, the head is recovered from the value of the tail.

Why decrement the indices?

The purpose of going backwards is opportunistic: using 0 as the sentinel value means buffer full and end of buffer checks are very cheap on the MSP430. In particular, using the Constant Generator register value 0 is much cheaper than looking up the size value in RAM. Since characters are read in serially, they are generally processed 1 by 1 in the application code. So it does not matter if the buffer indices increment or decrement as this detail hides behind abstraction.

Future work

This buffer will be a component in a UART MSP430 driver I am writing. The driver will not only handle typical I/O, but will also handle RX errors, serial breaks and other border conditions not found handled in other frameworks/source codes.