Shared Memory Ring Buffer

This is a toy implementation of a lock-free shared-memory based ring buffer, shmringbuf aka SHMRB. It was written largely as a learning excercise with the following goals in mind

1. no need for a master or coordinating process
2. can be used by multiple independent processes to share data

Design

Data Structures

SHMRB

Each SHMRB consists of metadata and a list of Entry:

• max_entries: maximum number of entries, aka the ring buffer size
• num_entries: number of populated entries in the ring buffer. Until the first write is made to this number is 0 and increments up to max_entries
• write_count: tracks the number of writes to the ring buffer. Each write updates one and only one Entry
• max_entry_data_size: the maximum size of data that can be stored in an Entry, in bytes. This is configured on SHMRB creation and cannot be changed after without migration of some kind.
• version: an integer that identifies the version of SHRMB on-disk format. Starts at 100.
• entries: max_entries number of Entry
• status: a 64 bit integer that atomically updated and serves to coordinate reads and writes.

When the above is written as bytes, the first 5 bytes shall be SBIAN which serves as a signature.

Entry

Each Entry consists of metadata and a fixed size buffer for storing data:

• data_size: size of data stored in the fixed size buffer
• sequence_number: a monotonically increasing number that increases by 1 or more each time the the buffer is updated. It is intended to allow readers to discover those entries which has been added since last-read by identifying those entries whose sequence-number is larger than the last one encountered. Sequence number starts at 0 for entries that have never been written.
• data: a fixed size buffer. Size is equal to max_entry_data_size.

When an Entry is written as bytes, the first two bytes shall be SB to serve as delimiters between one Entry and the next.

Read/Write Coordination

With shared memory data structures we want to coordinate readers and writers so that readers don't read while a writer is writing and writers don't write while a reader is reading. Failure to do so leads to inconsistent information being seen by readers. Additionally since we do not have a central coordinating process, we need to take care only one process is initialising the in-memory data structures.

To do all of this, we use the status 64 bit integer.

The status 64bit integer where the bits are interpreted as follows (bit 0 = LSB):

• 0..31: 32bit integer called R tracking the number of readers

• 32: a flag called `W` which is set to 1 when one or more writer is active
  

• 33: a flag called `Wx` which is set to 1 when a writer is writing and 0 otherwise.
  

• 34: a flag called `I` which is set to 1 when the SHMRB is initialised
  

• 35: a flag called `Ix` which is set to 1 when SHMRB is initialising and 0 otherwise.
  36: a flag called `D` which indicates the SHMRB is being deinitialised and incoming writers
      and readers should immediate exit and act as if SHMRB is no longer available.
  

• other: reserved

Initialisation

When SHRMB is instantiated against a shared-memory region which may either be zero-filled if it is the first instantiation, or contains an existing SHRMB. In either case, status is read and if I and Ix are both zero, then we shall attempt an atomic compare-and-exchange (cmpxchg) to update Ix to 1. Only one process will succeed, and that process will go on to initialise the memory region. All other processes will loop until I is set.

Deinitialisation

The process which won the race to initialise is also responsible for cleaning up and removing the shared memory. Deinitialisation occurs as follows:

1. Load status
2. Set D flag using cmpxchg
3. Wait for R, W and Wx to be 0 or timeout occurs
4. Remove the shared memory

Reads

When a process wishes to read, it will first enter a loop where:

1. load status
2. If D is 1, return error
3. If W is 1, continue
4. Use cmpxchg to increment R, break on success. Expected value for cmpxchg is W = Wx = 0.

Once out of the loop we are guarantee that:

1. R reflects the number of readers
2. There is no writer "ahead" of us, b/c cmpxchg will only succeed if W and Wx are both zero

On completion of reads, R is decremented using cmpxchg whilst preserving W and Wx.

Writes

When a processes wishes to read, it will first enter a loop where:

1. load status
2. If D is 1, return error
3. If R > 0, continue
4. Use cmpxchg to set W and Wx, break on success. Expected value for cmpxchg is R = 0, W = (W or 1) and Wx = 0

(4) ensures that only one writer is active at any one time, and because we set W, no readers will exit their loop as long as W is set b/c their cmpxchg to increment R will fail.

Once the write is done, unset Wx, which will then let one of the pending writers to continue.

Note that there is no way to enforce the order of writes if there are multiple writers pending. This is not considered a bug because there is no way to enforce that in the first place. Even if we implement FIFO queue for writers, there is no guarantee writers arrive in order due to scheduling. We will rely on writes being much faster than arrival of writers that this is never a signifcant issue.

Timeouts

Not Implemented

In the process described above, it is possible for a crashing reader or writer to block futures reads or writes, e.g. if Wx is never de-asserted then W is always 1 and no further reads can occur. As such on timeout we reset status such that Wx, W and R are all zero. Any pending readers and writers can then race to execute their cmpxchg with the winner proceeding as normal.

e.g. suppose a writer crashes leaving W = 1, Wx = 1 and R = 0. By setting all to zero, a reader that wins the race will set R > 0, preventing writers from writing until it is done. Similarly a writer that wins the race will set W = 1, Wx = 1 and stalling readers until the write is done.

The use of cmpxchg ensures only one reset is done.

Implications of Current Design

Writers are prioritised

Writers are given priority over readers because as soon as W is set to indicate waiting writers all new readers will wait until no writers are active before proceeding to increment R which blocks writers from writing.

Writers can have high contention

When a writer is done, it unsets Wx and all pending writers will race to set Wx and the winner gets to go ahead. This can be made nicer by having a mechanism by which writers can "queue" and avoid the data race. This can reduce the number of cmpxchg operations required.