How to set up safe, portable interprocess communication without interrupt locks

The approach described here allows non-blocking interprocess communication to take place on a single CPU, via a FIFO, circular buffer. I originally encountered this method of interprocess communication as part of the MASCOT design methodology, as a way of implementing the channel IDA.

To meet the requirements of providing safe interprocess communication without interrupt locks, the following must be true:

• Both processes can access common memory
• Communication is one-way, and occurs from one process/thread to another
• It is possible to write the in/out indices as an atomic action (i.e. as one machine instruction)
• It is possible to read the in/out indices as an atomic action
• Writer never attempts to write to a full buffer
• Reader never attempts to read from a buffer that doesn't contain valid data
• Adding data into the buffer does not need to be atomic. That is, it is safe to store records or arrays into the queue

The approach relies upon a circular buffer consists of the following elements:

buffer: array of data with 2^n elements 
in, out: unsigned integers as indices with range 0 to (2^(n+1))-1 

Before reading and writing, it is important to test whether the queue is empty or full, respectively. All queue conditions can be found by looking at the result of the following expression:

 buffer_contents = (in - out) % (2^(n+1)) 

The results of this expression are as follows:

buffer_contents == 0: Queue empty
buffer_contents > 0 && buffer_contents < 2^n: Queue
        contains valid data 
buffer_contents == 2^n: Queue is full 
buffer_contents > 2^n: overrun has occurred 

Writing must only take place when the queue is empty or contains some data (buffer_contents is less than 2^n). If this is the case, the following is done:

buffer[in % (2^n)] = data 
in = (in + 1) % (2^(n+1)) 

Reading must only take place if the queue is full or if it contains valid data (buffer_contents is not 0 and is less than or equal to 2^n). To read, the following actions are performed:

data = buffer[out % (2^n)] 
out = (out + 1) % (2^(n+1)) 

How can we be sure this is safe for interprocess communication?

Writing to a queue

If the writer starts by ensuring that the queue is not full (or overrun), the queue will never overrun after the test, because you are the only one capable of filling up the queue.

If the reader can preempt the writer, there are two possible behaviours:

The reader preempts the writer before the incremented value of 'in' is written

or:

The reader preempts the writer after the incremented value of 'in' is written.

Both of these behaviours are safe (i.e. will not result in the reader attempting to read a partly written value).

Reading from a queue

If the reader starts by ensuring the queue is not empty, the queue will never underrun after the test, because the reader is the only thread capable of emptying the queue.

If the writer can preempt the reader, there are two possible behaviours:

The writer preempts the reader before the incremented value of 'out' is written

or:

The writer preempts the reader after the incremented value of 'out' is written.

Both of these behaviours are safe (i.e. will not result in the writer attempting to overwrite a partly read value). Short C implementation:

#define N 4
#define buffer_contents ((in-out)%(1<<(N+1)))

void * buffer[1<<N];
unsigned int in;
unsigned int out;

void enqueue (void * data)
{
	if (buffer_contents==(1<<N)) return; // full
	buffer[in % (1<<N)] = data;
	in = (in + 1) % (1<<(N+1));
}


void * dequeue (void)
{
	void * data;
	if (buffer_contents==0) return NULL; // empty
	data = buffer[out % (1<<N)];
	out = (out + 1) % (1<<(N+1));
	return data;
}