Real-Time MP/SC Lock Free Ring

This is (the significant) part of an implementation of a logging mechanism for recording events in a real-time control system. The basic requirements are:

• No dynamic memory on either side (producers or consumer),

• Lock-free

• variable length event entries

• strictly sequential timestamps

• multi-processor safe

• tolerant of overruns/data drops

• usable from both kernel and user space code

As I've never written a lock free algorithm before, I'm hoping for some comment on any concurrency problems.I have this running, but I am very occasionally seeing a corrupted log message, which seems to have been published (tail moved forwards) before the body is completed. I'm hoping I'm missing something simple.

The system holds log data in a shared memory area (or several, depending on the use case). Typically each process in the system will create one log buffer of the form:

typedef atomic_uint_least32_t LogIndex_t;
typedef uint32_t LogVar_t;

struct LogInfo_struct
{
    LogIndex_t m_need;                     //declaration of space needed
    LogIndex_t m_head;                     //current head of buffered log data
    LogIndex_t m_alloc;                    //allocated out beyond working area
    LogIndex_t m_filled;                   //committed complete data
    LogIndex_t m_tail;                     //safe location at tail of buffered log data
    uint8_t    m_logBuffer[LOG_SIZE];      //head of log buffer
    char       m_strings[1<<12][64];       //copied and validated table of strings
} *g_log = 0;

Where LOG_SIZE is a power of 2, and the string table is used to encode longer, reused items. I won't be discussing the shared memory setup or the actual content of the message body, since this is unimportant here. The structure of each log entry is:

• 1 byte length of body

• 2-16 byte timestamp (depending on requirements)

• X bytes of arbitrary data (0-255 bytes)

Logging involves computing the body length and content, calling openEntry, writi

Consumer bug

Unless I am misunderstanding something, there seems to be a big problem in the consumer. Your variables m_head and m_tail appear to start at 0 and move forward indefinitely, without wrapping around at LOG_SIZE (which is fine). But the way the consumer interprets head and tail looks like it expected them to wrap around. For example, I don't see how this if could ever be true:

else if ( head > tail )

And when the code inevitably falls into the next case:

else
    {
        len = 0;
        tmps = &m_log->m_logBuffer[head & LOG_SIZE_MASK];
        addLen = (tail - head) & LOG_SIZE_MASK;
    }

    if (addLen > 1000 - len) addLen = 1000 - len;
    if (addLen) memcpy(&work[len], tmps, addLen);
    len += addLen;

You will be copying past the end of m_logBuffer whenever head gets close to the end of the buffer. For example, suppose LOG_SIZE is 32768, head is 32700, and tail is 32800. The above code will copy 33 bytes past the end of the buffer.

I'm surprised that you haven't noticed this problem. I wonder if your producer also copies past the end of the buffer? You never showed us the part where the producer copies the body. If that code had a similar problem, it could explain why the code might appear to be working.
Memory barriers

Normally, you would need to use memory barriers on both the producer and consumer sides to ensure that the content and tail updates are seen in the correct order. However, I'm assuming this program is running on an x86 target, where these barriers are not needed due to the strong memory ordering guarantees on that architecture.

StackExchange Code Review Q#104280, answer score: 2